?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
use isl_space_params_alloc
[pet.git] / scop.c
blobb042286a98c4a040342b3b92c5fb9ff9e33406ef
1 #include <isl/constraint.h>
2 #include <isl/union_set.h>
3
4 #include "scop.h"
5
6 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
7
8 static char *type_str[] = {
9 [pet_expr_access] = "access",
10 [pet_expr_call] = "call",
11 [pet_expr_double] = "double",
12 [pet_expr_unary] = "unary",
13 [pet_expr_binary] = "binary",
14 [pet_expr_ternary] = "ternary"
15 };
16
17 static char *op_str[] = {
18 [pet_op_add_assign] = "+=",
19 [pet_op_sub_assign] = "-=",
20 [pet_op_mul_assign] = "*=",
21 [pet_op_div_assign] = "/=",
22 [pet_op_assign] = "=",
23 [pet_op_add] = "+",
24 [pet_op_sub] = "-",
25 [pet_op_mul] = "*",
26 [pet_op_div] = "/",
27 [pet_op_eq] = "==",
28 [pet_op_le] = "<=",
29 [pet_op_lt] = "<",
30 [pet_op_gt] = ">",
31 [pet_op_minus] = "-"
32 };
33
34 const char *pet_op_str(enum pet_op_type op)
35 {
36 return op_str[op];
37 }
38
39 const char *pet_type_str(enum pet_expr_type type)
40 {
41 return type_str[type];
42 }
43
44 enum pet_op_type pet_str_op(const char *str)
45 {
46 int i;
47
48 for (i = 0; i < ARRAY_SIZE(op_str); ++i)
49 if (!strcmp(op_str[i], str))
50 return i;
51
52 return -1;
53 }
54
55 enum pet_expr_type pet_str_type(const char *str)
56 {
57 int i;
58
59 for (i = 0; i < ARRAY_SIZE(type_str); ++i)
60 if (!strcmp(type_str[i], str))
61 return i;
62
63 return -1;
64 }
65
66 /* Construct a pet_expr from an access relation.
67 * By default, it is considered to be a read access.
68 */
69 struct pet_expr *pet_expr_from_access(__isl_take isl_map *access)
70 {
71 isl_ctx *ctx = isl_map_get_ctx(access);
72 struct pet_expr *expr;
73
74 if (!access)
75 return NULL;
76 expr = isl_calloc_type(ctx, struct pet_expr);
77 if (!expr)
78 goto error;
79
80 expr->type = pet_expr_access;
81 expr->acc.access = access;
82 expr->acc.read = 1;
83 expr->acc.write = 0;
84
85 return expr;
86 error:
87 isl_map_free(access);
88 return NULL;
89 }
90
91 /* Construct a unary pet_expr that performs "op" on "arg".
92 */
93 struct pet_expr *pet_expr_new_unary(isl_ctx *ctx, enum pet_op_type op,
94 struct pet_expr *arg)
95 {
96 struct pet_expr *expr;
97
98 if (!arg)
99 goto error;
100 expr = isl_alloc_type(ctx, struct pet_expr);
101 if (!expr)
102 goto error;
103
104 expr->type = pet_expr_unary;
105 expr->op = op;
106 expr->n_arg = 1;
107 expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
108 if (!expr->args)
109 goto error;
110 expr->args[pet_un_arg] = arg;
111
112 return expr;
113 error:
114 pet_expr_free(arg);
115 return NULL;
116 }
117
118 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
119 */
120 struct pet_expr *pet_expr_new_binary(isl_ctx *ctx, enum pet_op_type op,
121 struct pet_expr *lhs, struct pet_expr *rhs)
122 {
123 struct pet_expr *expr;
124
125 if (!lhs || !rhs)
126 goto error;
127 expr = isl_alloc_type(ctx, struct pet_expr);
128 if (!expr)
129 goto error;
130
131 expr->type = pet_expr_binary;
132 expr->op = op;
133 expr->n_arg = 2;
134 expr->args = isl_calloc_array(ctx, struct pet_expr *, 2);
135 if (!expr->args)
136 goto error;
137 expr->args[pet_bin_lhs] = lhs;
138 expr->args[pet_bin_rhs] = rhs;
139
140 return expr;
141 error:
142 pet_expr_free(lhs);
143 pet_expr_free(rhs);
144 return NULL;
145 }
146
147 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
148 */
149 struct pet_expr *pet_expr_new_ternary(isl_ctx *ctx, struct pet_expr *cond,
150 struct pet_expr *lhs, struct pet_expr *rhs)
151 {
152 struct pet_expr *expr;
153
154 if (!cond || !lhs || !rhs)
155 goto error;
156 expr = isl_alloc_type(ctx, struct pet_expr);
157 if (!expr)
158 goto error;
159
160 expr->type = pet_expr_ternary;
161 expr->n_arg = 3;
162 expr->args = isl_calloc_array(ctx, struct pet_expr *, 3);
163 if (!expr->args)
164 goto error;
165 expr->args[pet_ter_cond] = cond;
166 expr->args[pet_ter_true] = lhs;
167 expr->args[pet_ter_false] = rhs;
168
169 return expr;
170 error:
171 pet_expr_free(cond);
172 pet_expr_free(lhs);
173 pet_expr_free(rhs);
174 return NULL;
175 }
176
177 /* Construct a call pet_expr that calls function "name" with "n_arg"
178 * arguments. The caller is responsible for filling in the arguments.
179 */
180 struct pet_expr *pet_expr_new_call(isl_ctx *ctx, const char *name,
181 unsigned n_arg)
182 {
183 struct pet_expr *expr;
184
185 expr = isl_alloc_type(ctx, struct pet_expr);
186 if (!expr)
187 return NULL;
188
189 expr->type = pet_expr_call;
190 expr->n_arg = n_arg;
191 expr->name = strdup(name);
192 expr->args = isl_calloc_array(ctx, struct pet_expr *, n_arg);
193 if (!expr->name || !expr->args)
194 return pet_expr_free(expr);
195
196 return expr;
197 }
198
199 /* Construct a pet_expr that represents the double "d".
200 */
201 struct pet_expr *pet_expr_new_double(isl_ctx *ctx, double d)
202 {
203 struct pet_expr *expr;
204
205 expr = isl_calloc_type(ctx, struct pet_expr);
206 if (!expr)
207 return NULL;
208
209 expr->type = pet_expr_double;
210 expr->d = d;
211
212 return expr;
213 }
214
215 void *pet_expr_free(struct pet_expr *expr)
216 {
217 int i;
218
219 if (!expr)
220 return NULL;
221
222 for (i = 0; i < expr->n_arg; ++i)
223 pet_expr_free(expr->args[i]);
224 free(expr->args);
225
226 switch (expr->type) {
227 case pet_expr_access:
228 isl_map_free(expr->acc.access);
229 break;
230 case pet_expr_call:
231 free(expr->name);
232 break;
233 case pet_expr_double:
234 case pet_expr_unary:
235 case pet_expr_binary:
236 case pet_expr_ternary:
237 break;
238 }
239
240 free(expr);
241 return NULL;
242 }
243
244 static void expr_dump(struct pet_expr *expr, int indent)
245 {
246 int i;
247
248 if (!expr)
249 return;
250
251 fprintf(stderr, "%*s", indent, "");
252
253 switch (expr->type) {
254 case pet_expr_double:
255 fprintf(stderr, "%g\n", expr->d);
256 break;
257 case pet_expr_access:
258 isl_map_dump(expr->acc.access);
259 fprintf(stderr, "%*sread: %d\n", indent + 2,
260 "", expr->acc.read);
261 fprintf(stderr, "%*swrite: %d\n", indent + 2,
262 "", expr->acc.write);
263 for (i = 0; i < expr->n_arg; ++i)
264 expr_dump(expr->args[i], indent + 2);
265 break;
266 case pet_expr_unary:
267 fprintf(stderr, "%s\n", op_str[expr->op]);
268 expr_dump(expr->args[pet_un_arg], indent + 2);
269 break;
270 case pet_expr_binary:
271 fprintf(stderr, "%s\n", op_str[expr->op]);
272 expr_dump(expr->args[pet_bin_lhs], indent + 2);
273 expr_dump(expr->args[pet_bin_rhs], indent + 2);
274 break;
275 case pet_expr_ternary:
276 fprintf(stderr, "?:\n");
277 expr_dump(expr->args[pet_ter_cond], indent + 2);
278 expr_dump(expr->args[pet_ter_true], indent + 2);
279 expr_dump(expr->args[pet_ter_false], indent + 2);
280 break;
281 case pet_expr_call:
282 fprintf(stderr, "%s/%d\n", expr->name, expr->n_arg);
283 for (i = 0; i < expr->n_arg; ++i)
284 expr_dump(expr->args[i], indent + 2);
285 break;
286 }
287 }
288
289 void pet_expr_dump(struct pet_expr *expr)
290 {
291 expr_dump(expr, 0);
292 }
293
294 /* Return 1 if the two pet_exprs are equivalent.
295 */
296 int pet_expr_is_equal(struct pet_expr *expr1, struct pet_expr *expr2)
297 {
298 int i;
299
300 if (!expr1 || !expr2)
301 return 0;
302
303 if (expr1->type != expr2->type)
304 return 0;
305 if (expr1->n_arg != expr2->n_arg)
306 return 0;
307 for (i = 0; i < expr1->n_arg; ++i)
308 if (!pet_expr_is_equal(expr1->args[i], expr2->args[i]))
309 return 0;
310 switch (expr1->type) {
311 case pet_expr_double:
312 if (expr1->d != expr2->d)
313 return 0;
314 break;
315 case pet_expr_access:
316 if (expr1->acc.read != expr2->acc.read)
317 return 0;
318 if (expr1->acc.write != expr2->acc.write)
319 return 0;
320 if (!isl_map_is_equal(expr1->acc.access, expr2->acc.access))
321 return 0;
322 break;
323 case pet_expr_unary:
324 case pet_expr_binary:
325 case pet_expr_ternary:
326 if (expr1->op != expr2->op)
327 return 0;
328 break;
329 case pet_expr_call:
330 if (strcmp(expr1->name, expr2->name))
331 return 0;
332 break;
333 }
334
335 return 1;
336 }
337
338 /* Add extra conditions on the parameters to all access relations in "expr".
339 */
340 struct pet_expr *pet_expr_restrict(struct pet_expr *expr,
341 __isl_take isl_set *cond)
342 {
343 int i;
344
345 if (!expr)
346 goto error;
347
348 for (i = 0; i < expr->n_arg; ++i) {
349 expr->args[i] = pet_expr_restrict(expr->args[i],
350 isl_set_copy(cond));
351 if (!expr->args[i])
352 goto error;
353 }
354
355 if (expr->type == pet_expr_access) {
356 expr->acc.access = isl_map_intersect_params(expr->acc.access,
357 isl_set_copy(cond));
358 if (!expr->acc.access)
359 goto error;
360 }
361
362 isl_set_free(cond);
363 return expr;
364 error:
365 isl_set_free(cond);
366 return pet_expr_free(expr);
367 }
368
369 /* Modify all access relations in "expr" by calling "fn" on them.
370 */
371 static struct pet_expr *expr_foreach_access(struct pet_expr *expr,
372 __isl_give isl_map *(*fn)(__isl_take isl_map *access, void *user),
373 void *user)
374 {
375 int i;
376
377 if (!expr)
378 return NULL;
379
380 for (i = 0; i < expr->n_arg; ++i) {
381 expr->args[i] = expr_foreach_access(expr->args[i], fn, user);
382 if (!expr->args[i])
383 return pet_expr_free(expr);
384 }
385
386 if (expr->type == pet_expr_access) {
387 expr->acc.access = fn(expr->acc.access, user);
388 if (!expr->acc.access)
389 return pet_expr_free(expr);
390 }
391
392 return expr;
393 }
394
395 /* Modify the given access relation based on the given iteration space
396 * transformation.
397 * If the access has any arguments then the domain of the access relation
398 * is a wrapped mapping from the iteration space to the space of
399 * argument values. We only need to change the domain of this wrapped
400 * mapping, so we extend the input transformation with an identity mapping
401 * on the space of argument values.
402 */
403 static __isl_give isl_map *update_domain(__isl_take isl_map *access,
404 void *user)
405 {
406 isl_map *update = user;
407 isl_space *dim;
408
409 update = isl_map_copy(update);
410
411 dim = isl_map_get_space(access);
412 dim = isl_space_domain(dim);
413 if (!isl_space_is_wrapping(dim))
414 isl_space_free(dim);
415 else {
416 isl_map *id;
417 dim = isl_space_unwrap(dim);
418 dim = isl_space_range(dim);
419 dim = isl_space_map_from_set(dim);
420 id = isl_map_identity(dim);
421 update = isl_map_product(update, id);
422 }
423
424 return isl_map_apply_domain(access, update);
425 }
426
427 /* Modify all access relations in "expr" based on the given iteration space
428 * transformation.
429 */
430 static struct pet_expr *expr_update_domain(struct pet_expr *expr,
431 __isl_take isl_map *update)
432 {
433 expr = expr_foreach_access(expr, &update_domain, update);
434 isl_map_free(update);
435 return expr;
436 }
437
438 /* Construct a pet_stmt with given line number and statement
439 * number from a pet_expr.
440 * The initial iteration domain is the zero-dimensional universe.
441 * The domains of all access relations are modified to refer
442 * to the statement iteration domain.
443 */
444 struct pet_stmt *pet_stmt_from_pet_expr(isl_ctx *ctx, int line, int id,
445 struct pet_expr *expr)
446 {
447 struct pet_stmt *stmt;
448 isl_space *dim;
449 isl_set *dom;
450 isl_map *sched;
451 isl_map *add_name;
452 char name[50];
453
454 if (!expr)
455 return NULL;
456
457 stmt = isl_alloc_type(ctx, struct pet_stmt);
458 if (!stmt)
459 return pet_expr_free(expr);
460
461 dim = isl_space_set_alloc(ctx, 0, 0);
462 snprintf(name, sizeof(name), "S_%d", id);
463 dim = isl_space_set_tuple_name(dim, isl_dim_set, name);
464 dom = isl_set_universe(isl_space_copy(dim));
465 sched = isl_map_from_domain(isl_set_copy(dom));
466
467 dim = isl_space_from_range(dim);
468 add_name = isl_map_universe(dim);
469 expr = expr_update_domain(expr, add_name);
470
471 stmt->line = line;
472 stmt->domain = dom;
473 stmt->schedule = sched;
474 stmt->body = expr;
475
476 if (!stmt->domain || !stmt->schedule || !stmt->body)
477 return pet_stmt_free(stmt);
478
479 return stmt;
480 }
481
482 void *pet_stmt_free(struct pet_stmt *stmt)
483 {
484 if (!stmt)
485 return NULL;
486
487 isl_set_free(stmt->domain);
488 isl_map_free(stmt->schedule);
489 pet_expr_free(stmt->body);
490
491 free(stmt);
492 return NULL;
493 }
494
495 static void stmt_dump(struct pet_stmt *stmt, int indent)
496 {
497 if (!stmt)
498 return;
499
500 fprintf(stderr, "%*s%d\n", indent, "", stmt->line);
501 fprintf(stderr, "%*s", indent, "");
502 isl_set_dump(stmt->domain);
503 fprintf(stderr, "%*s", indent, "");
504 isl_map_dump(stmt->schedule);
505 expr_dump(stmt->body, indent);
506 }
507
508 void pet_stmt_dump(struct pet_stmt *stmt)
509 {
510 stmt_dump(stmt, 0);
511 }
512
513 void *pet_array_free(struct pet_array *array)
514 {
515 if (!array)
516 return NULL;
517
518 isl_set_free(array->context);
519 isl_set_free(array->extent);
520 isl_set_free(array->value_bounds);
521 free(array->element_type);
522
523 free(array);
524 return NULL;
525 }
526
527 void pet_array_dump(struct pet_array *array)
528 {
529 if (!array)
530 return;
531
532 isl_set_dump(array->context);
533 isl_set_dump(array->extent);
534 isl_set_dump(array->value_bounds);
535 fprintf(stderr, "%s %s\n", array->element_type,
536 array->live_out ? "live-out" : "");
537 }
538
539 /* Construct a pet_scop with room for n statements.
540 */
541 static struct pet_scop *scop_alloc(isl_ctx *ctx, int n)
542 {
543 struct pet_scop *scop;
544
545 scop = isl_calloc_type(ctx, struct pet_scop);
546 if (!scop)
547 return NULL;
548
549 scop->context = isl_set_universe(isl_space_params_alloc(ctx, 0));
550 scop->stmts = isl_calloc_array(ctx, struct pet_stmt *, n);
551 if (!scop->context || !scop->stmts)
552 return pet_scop_free(scop);
553
554 scop->n_stmt = n;
555
556 return scop;
557 }
558
559 struct pet_scop *pet_scop_empty(isl_ctx *ctx)
560 {
561 return scop_alloc(ctx, 0);
562 }
563
564 /* Construct a pet_scop that contains the given pet_stmt.
565 */
566 struct pet_scop *pet_scop_from_pet_stmt(isl_ctx *ctx, struct pet_stmt *stmt)
567 {
568 struct pet_scop *scop;
569
570 if (!stmt)
571 return NULL;
572
573 scop = scop_alloc(ctx, 1);
574
575 scop->stmts[0] = stmt;
576
577 return scop;
578 error:
579 pet_stmt_free(stmt);
580 pet_scop_free(scop);
581 return NULL;
582 }
583
584 /* Construct a pet_scop that contains the statements in "scop1" and "scop2".
585 */
586 struct pet_scop *pet_scop_add(isl_ctx *ctx, struct pet_scop *scop1,
587 struct pet_scop *scop2)
588 {
589 int i;
590 struct pet_scop *scop;
591
592 if (!scop1 || !scop2)
593 goto error;
594
595 if (scop1->n_stmt == 0) {
596 pet_scop_free(scop1);
597 return scop2;
598 }
599
600 if (scop2->n_stmt == 0) {
601 pet_scop_free(scop2);
602 return scop1;
603 }
604
605 scop = scop_alloc(ctx, scop1->n_stmt + scop2->n_stmt);
606 if (!scop)
607 goto error;
608
609 for (i = 0; i < scop1->n_stmt; ++i) {
610 scop->stmts[i] = scop1->stmts[i];
611 scop1->stmts[i] = NULL;
612 }
613
614 for (i = 0; i < scop2->n_stmt; ++i) {
615 scop->stmts[scop1->n_stmt + i] = scop2->stmts[i];
616 scop2->stmts[i] = NULL;
617 }
618
619 pet_scop_free(scop1);
620 pet_scop_free(scop2);
621 return scop;
622 error:
623 pet_scop_free(scop1);
624 pet_scop_free(scop2);
625 return NULL;
626 }
627
628 void *pet_scop_free(struct pet_scop *scop)
629 {
630 int i;
631
632 if (!scop)
633 return NULL;
634 isl_set_free(scop->context);
635 if (scop->arrays)
636 for (i = 0; i < scop->n_array; ++i)
637 pet_array_free(scop->arrays[i]);
638 free(scop->arrays);
639 if (scop->stmts)
640 for (i = 0; i < scop->n_stmt; ++i)
641 pet_stmt_free(scop->stmts[i]);
642 free(scop->stmts);
643 free(scop);
644 return NULL;
645 }
646
647 void pet_scop_dump(struct pet_scop *scop)
648 {
649 int i;
650
651 if (!scop)
652 return;
653
654 isl_set_dump(scop->context);
655 for (i = 0; i < scop->n_array; ++i)
656 pet_array_dump(scop->arrays[i]);
657 for (i = 0; i < scop->n_stmt; ++i)
658 pet_stmt_dump(scop->stmts[i]);
659 }
660
661 /* Return 1 if the two pet_arrays are equivalent.
662 */
663 int pet_array_is_equal(struct pet_array *array1, struct pet_array *array2)
664 {
665 if (!array1 || !array2)
666 return 0;
667
668 if (!isl_set_is_equal(array1->context, array2->context))
669 return 0;
670 if (!isl_set_is_equal(array1->extent, array2->extent))
671 return 0;
672 if (!!array1->value_bounds != !!array2->value_bounds)
673 return 0;
674 if (array1->value_bounds &&
675 !isl_set_is_equal(array1->value_bounds, array2->value_bounds))
676 return 0;
677 if (strcmp(array1->element_type, array2->element_type))
678 return 0;
679 if (array1->live_out != array2->live_out)
680 return 0;
681
682 return 1;
683 }
684
685 /* Return 1 if the two pet_stmts are equivalent.
686 */
687 int pet_stmt_is_equal(struct pet_stmt *stmt1, struct pet_stmt *stmt2)
688 {
689 if (!stmt1 || !stmt2)
690 return 0;
691
692 if (stmt1->line != stmt2->line)
693 return 0;
694 if (!isl_set_is_equal(stmt1->domain, stmt2->domain))
695 return 0;
696 if (!isl_map_is_equal(stmt1->schedule, stmt2->schedule))
697 return 0;
698 if (!pet_expr_is_equal(stmt1->body, stmt2->body))
699 return 0;
700
701 return 1;
702 }
703
704 /* Return 1 if the two pet_scops are equivalent.
705 */
706 int pet_scop_is_equal(struct pet_scop *scop1, struct pet_scop *scop2)
707 {
708 int i;
709
710 if (!scop1 || !scop2)
711 return 0;
712
713 if (!isl_set_is_equal(scop1->context, scop2->context))
714 return 0;
715
716 if (scop1->n_array != scop2->n_array)
717 return 0;
718 for (i = 0; i < scop1->n_array; ++i)
719 if (!pet_array_is_equal(scop1->arrays[i], scop2->arrays[i]))
720 return 0;
721
722 if (scop1->n_stmt != scop2->n_stmt)
723 return 0;
724 for (i = 0; i < scop1->n_stmt; ++i)
725 if (!pet_stmt_is_equal(scop1->stmts[i], scop2->stmts[i]))
726 return 0;
727
728 return 1;
729 }
730
731 /* Prefix the schedule of "stmt" with an extra dimension with constant
732 * value "pos".
733 */
734 struct pet_stmt *pet_stmt_prefix(struct pet_stmt *stmt, int pos)
735 {
736 if (!stmt)
737 return NULL;
738
739 stmt->schedule = isl_map_insert_dims(stmt->schedule, isl_dim_out, 0, 1);
740 stmt->schedule = isl_map_fix_si(stmt->schedule, isl_dim_out, 0, pos);
741 if (!stmt->schedule)
742 return pet_stmt_free(stmt);
743
744 return stmt;
745 }
746
747 /* Prefix the schedules of all statements in "scop" with an extra
748 * dimension with constant value "pos".
749 */
750 struct pet_scop *pet_scop_prefix(struct pet_scop *scop, int pos)
751 {
752 int i;
753
754 if (!scop)
755 return NULL;
756
757 for (i = 0; i < scop->n_stmt; ++i) {
758 scop->stmts[i] = pet_stmt_prefix(scop->stmts[i], pos);
759 if (!scop->stmts[i])
760 return pet_scop_free(scop);
761 }
762
763 return scop;
764 }
765
766 /* Data used in embed_access.
767 * extend adds an iterator to the iteration domain
768 * var_id represents the induction variable of the corresponding loop
769 */
770 struct pet_embed_access {
771 isl_map *extend;
772 isl_id *var_id;
773 };
774
775 /* Embed the access relation in an extra outer loop.
776 *
777 * We first update the iteration domain to insert the extra dimension.
778 *
779 * If the access refers to the induction variable, then it is
780 * turned into an access to the set of integers with index (and value)
781 * equal to the induction variable.
782 *
783 * If the induction variable appears in the constraints (as a parameter),
784 * then the parameter is equated to the newly introduced iteration
785 * domain dimension and subsequently projected out.
786 */
787 static __isl_give isl_map *embed_access(__isl_take isl_map *access,
788 void *user)
789 {
790 struct pet_embed_access *data = user;
791 isl_id *array_id = NULL;
792 int pos;
793
794 access = update_domain(access, data->extend);
795
796 if (isl_map_has_tuple_id(access, isl_dim_out))
797 array_id = isl_map_get_tuple_id(access, isl_dim_out);
798 if (array_id == data->var_id) {
799 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
800 access = isl_map_equate(access,
801 isl_dim_in, 0, isl_dim_out, 0);
802 }
803 isl_id_free(array_id);
804
805 pos = isl_map_find_dim_by_id(access, isl_dim_param, data->var_id);
806 if (pos >= 0) {
807 access = isl_map_equate(access,
808 isl_dim_param, pos, isl_dim_in, 0);
809 access = isl_map_project_out(access, isl_dim_param, pos, 1);
810 }
811 access = isl_map_set_dim_id(access, isl_dim_in, 0,
812 isl_id_copy(data->var_id));
813
814 return access;
815 }
816
817 /* Embed all access relations in "expr" in an extra loop.
818 * "extend" inserts an outer loop iterator in the iteration domains.
819 * "var_id" represents the induction variable.
820 */
821 static struct pet_expr *expr_embed(struct pet_expr *expr,
822 __isl_take isl_map *extend, __isl_keep isl_id *var_id)
823 {
824 struct pet_embed_access data = { .extend = extend, .var_id = var_id };
825
826 expr = expr_foreach_access(expr, &embed_access, &data);
827 isl_map_free(extend);
828 return expr;
829 }
830
831 /* Embed the given pet_stmt in an extra outer loop with iteration domain
832 * "dom" and schedule "sched". "var_id" represents the induction variable
833 * of the loop.
834 *
835 * The iteration domain and schedule of the statement are updated
836 * according to the iteration domain and schedule of the new loop.
837 *
838 * If the induction variable appears in the constraints (as a parameter)
839 * of the current iteration domain or the schedule of the statement,
840 * then the parameter is equated to the newly introduced iteration
841 * domain dimension and subsequently projected out.
842 *
843 * Finally, all access relations are updated based on the extra loop.
844 */
845 struct pet_stmt *pet_stmt_embed(struct pet_stmt *stmt, __isl_take isl_set *dom,
846 __isl_take isl_map *sched, __isl_take isl_id *var_id)
847 {
848 int pos;
849 isl_id *stmt_id;
850 isl_space *dim;
851 isl_map *extend;
852
853 stmt_id = isl_set_get_tuple_id(stmt->domain);
854 stmt->domain = isl_set_flat_product(isl_set_copy(dom), stmt->domain);
855 stmt->domain = isl_set_set_tuple_id(stmt->domain, isl_id_copy(stmt_id));
856
857 pos = isl_set_find_dim_by_id(stmt->domain, isl_dim_param, var_id);
858 if (pos >= 0) {
859 stmt->domain = isl_set_equate(stmt->domain,
860 isl_dim_param, pos, isl_dim_set, 0);
861 stmt->domain = isl_set_project_out(stmt->domain,
862 isl_dim_param, pos, 1);
863 }
864
865 stmt->schedule = isl_map_flat_product(sched, stmt->schedule);
866 stmt->schedule = isl_map_set_tuple_id(stmt->schedule,
867 isl_dim_in, stmt_id);
868
869 pos = isl_map_find_dim_by_id(stmt->schedule, isl_dim_param, var_id);
870 if (pos >= 0) {
871 stmt->schedule = isl_map_equate(stmt->schedule,
872 isl_dim_param, pos, isl_dim_in, 0);
873 stmt->schedule = isl_map_project_out(stmt->schedule,
874 isl_dim_param, pos, 1);
875 }
876
877 dim = isl_space_map_from_set(isl_set_get_space(stmt->domain));
878 extend = isl_map_identity(dim);
879 extend = isl_map_remove_dims(extend, isl_dim_in, 0, 1);
880 extend = isl_map_set_tuple_id(extend, isl_dim_in,
881 isl_map_get_tuple_id(extend, isl_dim_out));
882 stmt->body = expr_embed(stmt->body, extend, var_id);
883
884 isl_set_free(dom);
885 isl_id_free(var_id);
886
887 if (!stmt->domain || !stmt->schedule || !stmt->body)
888 return pet_stmt_free(stmt);
889 return stmt;
890 }
891
892 /* Embed all statements in "scop" in an extra outer loop with iteration domain
893 * "dom" and schedule "sched". "var_id" represents the induction variable
894 * of the loop.
895 */
896 struct pet_scop *pet_scop_embed(struct pet_scop *scop, __isl_take isl_set *dom,
897 __isl_take isl_map *sched, __isl_take isl_id *id)
898 {
899 int i;
900
901 if (!scop)
902 goto error;
903
904 for (i = 0; i < scop->n_stmt; ++i) {
905 scop->stmts[i] = pet_stmt_embed(scop->stmts[i],
906 isl_set_copy(dom),
907 isl_map_copy(sched), isl_id_copy(id));
908 if (!scop->stmts[i])
909 goto error;
910 }
911
912 isl_set_free(dom);
913 isl_map_free(sched);
914 isl_id_free(id);
915 return scop;
916 error:
917 isl_set_free(dom);
918 isl_map_free(sched);
919 isl_id_free(id);
920 return pet_scop_free(scop);
921 }
922
923 /* Add extra conditions on the parameters to iteration domain of "stmt".
924 */
925 static struct pet_stmt *stmt_restrict(struct pet_stmt *stmt,
926 __isl_take isl_set *cond)
927 {
928 if (!stmt)
929 goto error;
930
931 stmt->domain = isl_set_intersect_params(stmt->domain, cond);
932
933 return stmt;
934 error:
935 isl_set_free(cond);
936 return pet_stmt_free(stmt);
937 }
938
939 /* Add extra conditions on the parameters to all iteration domains.
940 */
941 struct pet_scop *pet_scop_restrict(struct pet_scop *scop,
942 __isl_take isl_set *cond)
943 {
944 int i;
945
946 if (!scop)
947 goto error;
948
949 for (i = 0; i < scop->n_stmt; ++i) {
950 scop->stmts[i] = stmt_restrict(scop->stmts[i],
951 isl_set_copy(cond));
952 if (!scop->stmts[i])
953 goto error;
954 }
955
956 isl_set_free(cond);
957 return scop;
958 error:
959 isl_set_free(cond);
960 return pet_scop_free(scop);
961 }
962
963 /* Add all parameters in "expr" to "dim" and return the result.
964 */
965 static __isl_give isl_space *expr_collect_params(struct pet_expr *expr,
966 __isl_take isl_space *dim)
967 {
968 int i;
969
970 if (!expr)
971 goto error;
972 for (i = 0; i < expr->n_arg; ++i)
973
974 dim = expr_collect_params(expr->args[i], dim);
975
976 if (expr->type == pet_expr_access)
977 dim = isl_space_align_params(dim,
978 isl_map_get_space(expr->acc.access));
979
980 return dim;
981 error:
982 isl_space_free(dim);
983 return pet_expr_free(expr);
984 }
985
986 /* Add all parameters in "stmt" to "dim" and return the result.
987 */
988 static __isl_give isl_space *stmt_collect_params(struct pet_stmt *stmt,
989 __isl_take isl_space *dim)
990 {
991 if (!stmt)
992 goto error;
993
994 dim = isl_space_align_params(dim, isl_set_get_space(stmt->domain));
995 dim = isl_space_align_params(dim, isl_map_get_space(stmt->schedule));
996 dim = expr_collect_params(stmt->body, dim);
997
998 return dim;
999 error:
1000 isl_space_free(dim);
1001 return pet_stmt_free(stmt);
1002 }
1003
1004 /* Add all parameters in "array" to "dim" and return the result.
1005 */
1006 static __isl_give isl_space *array_collect_params(struct pet_array *array,
1007 __isl_take isl_space *dim)
1008 {
1009 if (!array)
1010 goto error;
1011
1012 dim = isl_space_align_params(dim, isl_set_get_space(array->context));
1013 dim = isl_space_align_params(dim, isl_set_get_space(array->extent));
1014
1015 return dim;
1016 error:
1017 isl_space_free(dim);
1018 return pet_array_free(array);
1019 }
1020
1021 /* Add all parameters in "scop" to "dim" and return the result.
1022 */
1023 static __isl_give isl_space *scop_collect_params(struct pet_scop *scop,
1024 __isl_take isl_space *dim)
1025 {
1026 int i;
1027
1028 if (!scop)
1029 goto error;
1030
1031 for (i = 0; i < scop->n_array; ++i)
1032 dim = array_collect_params(scop->arrays[i], dim);
1033
1034 for (i = 0; i < scop->n_stmt; ++i)
1035 dim = stmt_collect_params(scop->stmts[i], dim);
1036
1037 return dim;
1038 error:
1039 isl_space_free(dim);
1040 return pet_scop_free(scop);
1041 }
1042
1043 /* Add all parameters in "dim" to all access relations in "expr".
1044 */
1045 static struct pet_expr *expr_propagate_params(struct pet_expr *expr,
1046 __isl_take isl_space *dim)
1047 {
1048 int i;
1049
1050 if (!expr)
1051 goto error;
1052
1053 for (i = 0; i < expr->n_arg; ++i) {
1054 expr->args[i] =
1055 expr_propagate_params(expr->args[i],
1056 isl_space_copy(dim));
1057 if (!expr->args[i])
1058 goto error;
1059 }
1060
1061 if (expr->type == pet_expr_access) {
1062 expr->acc.access = isl_map_align_params(expr->acc.access,
1063 isl_space_copy(dim));
1064 if (!expr->acc.access)
1065 goto error;
1066 }
1067
1068 isl_space_free(dim);
1069 return expr;
1070 error:
1071 isl_space_free(dim);
1072 return pet_expr_free(expr);
1073 }
1074
1075 /* Add all parameters in "dim" to the domain, schedule and
1076 * all access relations in "stmt".
1077 */
1078 static struct pet_stmt *stmt_propagate_params(struct pet_stmt *stmt,
1079 __isl_take isl_space *dim)
1080 {
1081 if (!stmt)
1082 goto error;
1083
1084 stmt->domain = isl_set_align_params(stmt->domain, isl_space_copy(dim));
1085 stmt->schedule = isl_map_align_params(stmt->schedule,
1086 isl_space_copy(dim));
1087 stmt->body = expr_propagate_params(stmt->body, isl_space_copy(dim));
1088
1089 if (!stmt->domain || !stmt->schedule || !stmt->body)
1090 goto error;
1091
1092 isl_space_free(dim);
1093 return stmt;
1094 error:
1095 isl_space_free(dim);
1096 return pet_stmt_free(stmt);
1097 }
1098
1099 /* Add all parameters in "dim" to "array".
1100 */
1101 static struct pet_array *array_propagate_params(struct pet_array *array,
1102 __isl_take isl_space *dim)
1103 {
1104 if (!array)
1105 goto error;
1106
1107 array->context = isl_set_align_params(array->context,
1108 isl_space_copy(dim));
1109 array->extent = isl_set_align_params(array->extent,
1110 isl_space_copy(dim));
1111 if (array->value_bounds) {
1112 array->value_bounds = isl_set_align_params(array->value_bounds,
1113 isl_space_copy(dim));
1114 if (!array->value_bounds)
1115 goto error;
1116 }
1117
1118 if (!array->context || !array->extent)
1119 goto error;
1120
1121 isl_space_free(dim);
1122 return array;
1123 error:
1124 isl_space_free(dim);
1125 return pet_array_free(array);
1126 }
1127
1128 /* Add all parameters in "dim" to "scop".
1129 */
1130 static struct pet_scop *scop_propagate_params(struct pet_scop *scop,
1131 __isl_take isl_space *dim)
1132 {
1133 int i;
1134
1135 if (!scop)
1136 goto error;
1137
1138 for (i = 0; i < scop->n_array; ++i) {
1139 scop->arrays[i] = array_propagate_params(scop->arrays[i],
1140 isl_space_copy(dim));
1141 if (!scop->arrays[i])
1142 goto error;
1143 }
1144
1145 for (i = 0; i < scop->n_stmt; ++i) {
1146 scop->stmts[i] = stmt_propagate_params(scop->stmts[i],
1147 isl_space_copy(dim));
1148 if (!scop->stmts[i])
1149 goto error;
1150 }
1151
1152 isl_space_free(dim);
1153 return scop;
1154 error:
1155 isl_space_free(dim);
1156 return pet_scop_free(scop);
1157 }
1158
1159 /* Update all isl_sets and isl_maps in "scop" such that they all
1160 * have the same parameters.
1161 */
1162 struct pet_scop *pet_scop_align_params(struct pet_scop *scop)
1163 {
1164 isl_space *dim;
1165
1166 if (!scop)
1167 return NULL;
1168
1169 dim = isl_set_get_space(scop->context);
1170 dim = scop_collect_params(scop, dim);
1171
1172 scop->context = isl_set_align_params(scop->context, isl_space_copy(dim));
1173 scop = scop_propagate_params(scop, dim);
1174
1175 return scop;
1176 }
1177
1178 /* Check if the given access relation accesses a (0D) array that corresponds
1179 * to one of the parameters in "dim". If so, replace the array access
1180 * by an access to the set of integers with as index (and value)
1181 * that parameter.
1182 */
1183 static __isl_give isl_map *access_detect_parameter(__isl_take isl_map *access,
1184 __isl_take isl_space *dim)
1185 {
1186 isl_id *array_id = NULL;
1187 int pos = -1;
1188
1189 if (isl_map_has_tuple_id(access, isl_dim_out)) {
1190 array_id = isl_map_get_tuple_id(access, isl_dim_out);
1191 pos = isl_space_find_dim_by_id(dim, isl_dim_param, array_id);
1192 }
1193 isl_space_free(dim);
1194
1195 if (pos < 0) {
1196 isl_id_free(array_id);
1197 return access;
1198 }
1199
1200 pos = isl_map_find_dim_by_id(access, isl_dim_param, array_id);
1201 if (pos < 0) {
1202 access = isl_map_insert_dims(access, isl_dim_param, 0, 1);
1203 access = isl_map_set_dim_id(access, isl_dim_param, 0, array_id);
1204 pos = 0;
1205 } else
1206 isl_id_free(array_id);
1207
1208 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
1209 access = isl_map_equate(access, isl_dim_param, pos, isl_dim_out, 0);
1210
1211 return access;
1212 }
1213
1214 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1215 * in "dim" by a value equal to the corresponding parameter.
1216 */
1217 static struct pet_expr *expr_detect_parameter_accesses(struct pet_expr *expr,
1218 __isl_take isl_space *dim)
1219 {
1220 int i;
1221
1222 if (!expr)
1223 goto error;
1224
1225 for (i = 0; i < expr->n_arg; ++i) {
1226 expr->args[i] =
1227 expr_detect_parameter_accesses(expr->args[i],
1228 isl_space_copy(dim));
1229 if (!expr->args[i])
1230 goto error;
1231 }
1232
1233 if (expr->type == pet_expr_access) {
1234 expr->acc.access = access_detect_parameter(expr->acc.access,
1235 isl_space_copy(dim));
1236 if (!expr->acc.access)
1237 goto error;
1238 }
1239
1240 isl_space_free(dim);
1241 return expr;
1242 error:
1243 isl_space_free(dim);
1244 return pet_expr_free(expr);
1245 }
1246
1247 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1248 * in "dim" by a value equal to the corresponding parameter.
1249 */
1250 static struct pet_stmt *stmt_detect_parameter_accesses(struct pet_stmt *stmt,
1251 __isl_take isl_space *dim)
1252 {
1253 if (!stmt)
1254 goto error;
1255
1256 stmt->body = expr_detect_parameter_accesses(stmt->body,
1257 isl_space_copy(dim));
1258
1259 if (!stmt->domain || !stmt->schedule || !stmt->body)
1260 goto error;
1261
1262 isl_space_free(dim);
1263 return stmt;
1264 error:
1265 isl_space_free(dim);
1266 return pet_stmt_free(stmt);
1267 }
1268
1269 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1270 * in "dim" by a value equal to the corresponding parameter.
1271 */
1272 static struct pet_scop *scop_detect_parameter_accesses(struct pet_scop *scop,
1273 __isl_take isl_space *dim)
1274 {
1275 int i;
1276
1277 if (!scop)
1278 goto error;
1279
1280 for (i = 0; i < scop->n_stmt; ++i) {
1281 scop->stmts[i] = stmt_detect_parameter_accesses(scop->stmts[i],
1282 isl_space_copy(dim));
1283 if (!scop->stmts[i])
1284 goto error;
1285 }
1286
1287 isl_space_free(dim);
1288 return scop;
1289 error:
1290 isl_space_free(dim);
1291 return pet_scop_free(scop);
1292 }
1293
1294 /* Replace all accesses to (0D) arrays that correspond to any of
1295 * the parameters used in "scop" by a value equal
1296 * to the corresponding parameter.
1297 */
1298 struct pet_scop *pet_scop_detect_parameter_accesses(struct pet_scop *scop)
1299 {
1300 isl_space *dim;
1301
1302 if (!scop)
1303 return NULL;
1304
1305 dim = isl_set_get_space(scop->context);
1306 dim = scop_collect_params(scop, dim);
1307
1308 scop = scop_detect_parameter_accesses(scop, dim);
1309
1310 return scop;
1311 }
1312
1313 /* Add all read access relations (if "read" is set) and/or all write
1314 * access relations (if "write" is set) to "accesses" and return the result.
1315 */
1316 static __isl_give isl_union_map *expr_collect_accesses(struct pet_expr *expr,
1317 int read, int write, __isl_take isl_union_map *accesses)
1318 {
1319 int i;
1320 isl_id *id;
1321 isl_space *dim;
1322
1323 if (!expr)
1324 return NULL;
1325
1326 for (i = 0; i < expr->n_arg; ++i)
1327 accesses = expr_collect_accesses(expr->args[i],
1328 read, write, accesses);
1329
1330 if (expr->type == pet_expr_access &&
1331 isl_map_has_tuple_id(expr->acc.access, isl_dim_out) &&
1332 ((read && expr->acc.read) || (write && expr->acc.write)))
1333 accesses = isl_union_map_add_map(accesses,
1334 isl_map_copy(expr->acc.access));
1335
1336 return accesses;
1337 }
1338
1339 /* Collect and return all read access relations (if "read" is set)
1340 * and/or all write * access relations (if "write" is set) in "stmt".
1341 */
1342 static __isl_give isl_union_map *stmt_collect_accesses(struct pet_stmt *stmt,
1343 int read, int write, __isl_take isl_space *dim)
1344 {
1345 isl_union_map *accesses;
1346
1347 if (!stmt)
1348 return NULL;
1349
1350 accesses = isl_union_map_empty(dim);
1351 accesses = expr_collect_accesses(stmt->body, read, write, accesses);
1352 accesses = isl_union_map_intersect_domain(accesses,
1353 isl_union_set_from_set(isl_set_copy(stmt->domain)));
1354
1355 return accesses;
1356 }
1357
1358 /* Collect and return all read access relations (if "read" is set)
1359 * and/or all write * access relations (if "write" is set) in "scop".
1360 */
1361 static __isl_give isl_union_map *scop_collect_accesses(struct pet_scop *scop,
1362 int read, int write)
1363 {
1364 int i;
1365 isl_union_map *accesses;
1366
1367 if (!scop)
1368 return NULL;
1369
1370 accesses = isl_union_map_empty(isl_set_get_space(scop->context));
1371
1372 for (i = 0; i < scop->n_stmt; ++i) {
1373 isl_union_map *accesses_i;
1374 isl_space *dim = isl_set_get_space(scop->context);
1375 accesses_i = stmt_collect_accesses(scop->stmts[i],
1376 read, write, dim);
1377 accesses = isl_union_map_union(accesses, accesses_i);
1378 }
1379
1380 return accesses;
1381 }
1382
1383 __isl_give isl_union_map *pet_scop_collect_reads(struct pet_scop *scop)
1384 {
1385 return scop_collect_accesses(scop, 1, 0);
1386 }
1387
1388 __isl_give isl_union_map *pet_scop_collect_writes(struct pet_scop *scop)
1389 {
1390 return scop_collect_accesses(scop, 0, 1);
1391 }
1392
1393 /* Collect and return the union of iteration domains in "scop".
1394 */
1395 __isl_give isl_union_set *pet_scop_collect_domains(struct pet_scop *scop)
1396 {
1397 int i;
1398 isl_set *domain_i;
1399 isl_union_set *domain;
1400
1401 if (!scop)
1402 return NULL;
1403
1404 domain = isl_union_set_empty(isl_set_get_space(scop->context));
1405
1406 for (i = 0; i < scop->n_stmt; ++i) {
1407 domain_i = isl_set_copy(scop->stmts[i]->domain);
1408 domain = isl_union_set_add_set(domain, domain_i);
1409 }
1410
1411 return domain;
1412 }
1413
1414 /* Collect and return the schedules of the statements in "scop".
1415 * The range is normalized to the maximal number of scheduling
1416 * dimensions.
1417 */
1418 __isl_give isl_union_map *pet_scop_collect_schedule(struct pet_scop *scop)
1419 {
1420 int i, j;
1421 isl_map *schedule_i;
1422 isl_union_map *schedule;
1423 int depth, max_depth = 0;
1424
1425 if (!scop)
1426 return NULL;
1427
1428 schedule = isl_union_map_empty(isl_set_get_space(scop->context));
1429
1430 for (i = 0; i < scop->n_stmt; ++i) {
1431 depth = isl_map_dim(scop->stmts[i]->schedule, isl_dim_out);
1432 if (depth > max_depth)
1433 max_depth = depth;
1434 }
1435
1436 for (i = 0; i < scop->n_stmt; ++i) {
1437 schedule_i = isl_map_copy(scop->stmts[i]->schedule);
1438 depth = isl_map_dim(schedule_i, isl_dim_out);
1439 schedule_i = isl_map_add_dims(schedule_i, isl_dim_out,
1440 max_depth - depth);
1441 for (j = depth; j < max_depth; ++j)
1442 schedule_i = isl_map_fix_si(schedule_i,
1443 isl_dim_out, j, 0);
1444 schedule = isl_union_map_add_map(schedule, schedule_i);
1445 }
1446
1447 return schedule;
1448 }