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