pet_check_code: dump iteration domains if they are different
[pet.git] / scop.c
blobb6ece21c775258117af55e0dae341eac2f001c10
1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2014 Ecole Normale Superieure. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer in the documentation and/or other materials provided
15 * with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 * The views and conclusions contained in the software and documentation
30 * are those of the authors and should not be interpreted as
31 * representing official policies, either expressed or implied, of
32 * Leiden University.
33 */
35 #include <string.h>
36 #include <isl/constraint.h>
37 #include <isl/union_set.h>
39 #include "scop.h"
40 #include "print.h"
42 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
44 static char *type_str[] = {
45 [pet_expr_access] = "access",
46 [pet_expr_call] = "call",
47 [pet_expr_cast] = "cast",
48 [pet_expr_double] = "double",
49 [pet_expr_unary] = "unary",
50 [pet_expr_binary] = "binary",
51 [pet_expr_ternary] = "ternary"
54 static char *op_str[] = {
55 [pet_op_add_assign] = "+=",
56 [pet_op_sub_assign] = "-=",
57 [pet_op_mul_assign] = "*=",
58 [pet_op_div_assign] = "/=",
59 [pet_op_assign] = "=",
60 [pet_op_add] = "+",
61 [pet_op_sub] = "-",
62 [pet_op_mul] = "*",
63 [pet_op_div] = "/",
64 [pet_op_mod] = "%",
65 [pet_op_shl] = "<<",
66 [pet_op_shr] = ">>",
67 [pet_op_eq] = "==",
68 [pet_op_ne] = "!=",
69 [pet_op_le] = "<=",
70 [pet_op_ge] = ">=",
71 [pet_op_lt] = "<",
72 [pet_op_gt] = ">",
73 [pet_op_minus] = "-",
74 [pet_op_post_inc] = "++",
75 [pet_op_post_dec] = "--",
76 [pet_op_pre_inc] = "++",
77 [pet_op_pre_dec] = "--",
78 [pet_op_address_of] = "&",
79 [pet_op_and] = "&",
80 [pet_op_xor] = "^",
81 [pet_op_or] = "|",
82 [pet_op_not] = "~",
83 [pet_op_assume] = "assume",
84 [pet_op_kill] = "kill"
87 /* pet_scop with extra information that is used during parsing and printing.
89 * In particular, we keep track of conditions under which we want
90 * to skip the rest of the current loop iteration (skip[pet_skip_now])
91 * and of conditions under which we want to skip subsequent
92 * loop iterations (skip[pet_skip_later]).
94 * The conditions are represented as index expressions defined
95 * over a zero-dimensional domain. The index expression is either
96 * a boolean affine expression or an access to a variable, which
97 * is assumed to attain values zero and one. The condition holds
98 * if the variable has value one or if the affine expression
99 * has value one (typically for only part of the parameter space).
101 * A missing condition (skip[type] == NULL) means that we don't want
102 * to skip anything.
104 * Additionally, we keep track of the original input file
105 * inside pet_transform_C_source.
107 struct pet_scop_ext {
108 struct pet_scop scop;
110 isl_multi_pw_aff *skip[2];
111 FILE *input;
114 const char *pet_op_str(enum pet_op_type op)
116 return op_str[op];
119 int pet_op_is_inc_dec(enum pet_op_type op)
121 return op == pet_op_post_inc || op == pet_op_post_dec ||
122 op == pet_op_pre_inc || op == pet_op_pre_dec;
125 const char *pet_type_str(enum pet_expr_type type)
127 return type_str[type];
130 enum pet_op_type pet_str_op(const char *str)
132 int i;
134 for (i = 0; i < ARRAY_SIZE(op_str); ++i)
135 if (!strcmp(op_str[i], str))
136 return i;
138 return -1;
141 enum pet_expr_type pet_str_type(const char *str)
143 int i;
145 for (i = 0; i < ARRAY_SIZE(type_str); ++i)
146 if (!strcmp(type_str[i], str))
147 return i;
149 return -1;
152 /* Construct an access pet_expr from an access relation and an index expression.
153 * By default, it is considered to be a read access.
155 struct pet_expr *pet_expr_from_access_and_index( __isl_take isl_map *access,
156 __isl_take isl_multi_pw_aff *index)
158 isl_ctx *ctx = isl_map_get_ctx(access);
159 struct pet_expr *expr;
161 if (!index || !access)
162 goto error;
163 expr = isl_calloc_type(ctx, struct pet_expr);
164 if (!expr)
165 goto error;
167 expr->type = pet_expr_access;
168 expr->acc.access = access;
169 expr->acc.index = index;
170 expr->acc.read = 1;
171 expr->acc.write = 0;
173 return expr;
174 error:
175 isl_map_free(access);
176 isl_multi_pw_aff_free(index);
177 return NULL;
180 /* Construct an access pet_expr from an index expression.
181 * By default, the access is considered to be a read access.
183 struct pet_expr *pet_expr_from_index(__isl_take isl_multi_pw_aff *index)
185 isl_map *access;
187 access = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index));
188 return pet_expr_from_access_and_index(access, index);
191 /* Extend the range of "access" with "n" dimensions, retaining
192 * the tuple identifier on this range.
194 * If "access" represents a member access, then extend the range
195 * of the member.
197 static __isl_give isl_map *extend_range(__isl_take isl_map *access, int n)
199 isl_id *id;
201 id = isl_map_get_tuple_id(access, isl_dim_out);
203 if (!isl_map_range_is_wrapping(access)) {
204 access = isl_map_add_dims(access, isl_dim_out, n);
205 } else {
206 isl_map *domain;
208 domain = isl_map_copy(access);
209 domain = isl_map_range_factor_domain(domain);
210 access = isl_map_range_factor_range(access);
211 access = extend_range(access, n);
212 access = isl_map_range_product(domain, access);
215 access = isl_map_set_tuple_id(access, isl_dim_out, id);
217 return access;
220 /* Construct an access pet_expr from an index expression and
221 * the depth of the accessed array.
222 * By default, the access is considered to be a read access.
224 * If the number of indices is smaller than the depth of the array,
225 * then we assume that all elements of the remaining dimensions
226 * are accessed.
228 struct pet_expr *pet_expr_from_index_and_depth(
229 __isl_take isl_multi_pw_aff *index, int depth)
231 isl_map *access;
232 int dim;
234 access = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index));
235 if (!access)
236 goto error;
237 dim = isl_map_dim(access, isl_dim_out);
238 if (dim > depth)
239 isl_die(isl_map_get_ctx(access), isl_error_internal,
240 "number of indices greater than depth",
241 access = isl_map_free(access));
242 if (dim == depth)
243 return pet_expr_from_access_and_index(access, index);
245 access = extend_range(access, depth - dim);
247 return pet_expr_from_access_and_index(access, index);
248 error:
249 isl_multi_pw_aff_free(index);
250 return NULL;
253 /* Construct a pet_expr that kills the elements specified by
254 * the index expression "index" and the access relation "access".
256 struct pet_expr *pet_expr_kill_from_access_and_index(__isl_take isl_map *access,
257 __isl_take isl_multi_pw_aff *index)
259 isl_ctx *ctx;
260 struct pet_expr *expr;
262 if (!access || !index)
263 goto error;
265 ctx = isl_multi_pw_aff_get_ctx(index);
266 expr = pet_expr_from_access_and_index(access, index);
267 if (!expr)
268 return NULL;
269 expr->acc.read = 0;
270 return pet_expr_new_unary(ctx, pet_op_kill, expr);
271 error:
272 isl_map_free(access);
273 isl_multi_pw_aff_free(index);
274 return NULL;
277 /* Construct a unary pet_expr that performs "op" on "arg".
279 struct pet_expr *pet_expr_new_unary(isl_ctx *ctx, enum pet_op_type op,
280 struct pet_expr *arg)
282 struct pet_expr *expr;
284 if (!arg)
285 goto error;
286 expr = isl_alloc_type(ctx, struct pet_expr);
287 if (!expr)
288 goto error;
290 expr->type = pet_expr_unary;
291 expr->op = op;
292 expr->n_arg = 1;
293 expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
294 if (!expr->args)
295 goto error;
296 expr->args[pet_un_arg] = arg;
298 return expr;
299 error:
300 pet_expr_free(arg);
301 return NULL;
304 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
306 struct pet_expr *pet_expr_new_binary(isl_ctx *ctx, enum pet_op_type op,
307 struct pet_expr *lhs, struct pet_expr *rhs)
309 struct pet_expr *expr;
311 if (!lhs || !rhs)
312 goto error;
313 expr = isl_alloc_type(ctx, struct pet_expr);
314 if (!expr)
315 goto error;
317 expr->type = pet_expr_binary;
318 expr->op = op;
319 expr->n_arg = 2;
320 expr->args = isl_calloc_array(ctx, struct pet_expr *, 2);
321 if (!expr->args)
322 goto error;
323 expr->args[pet_bin_lhs] = lhs;
324 expr->args[pet_bin_rhs] = rhs;
326 return expr;
327 error:
328 pet_expr_free(lhs);
329 pet_expr_free(rhs);
330 return NULL;
333 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
335 struct pet_expr *pet_expr_new_ternary(isl_ctx *ctx, struct pet_expr *cond,
336 struct pet_expr *lhs, struct pet_expr *rhs)
338 struct pet_expr *expr;
340 if (!cond || !lhs || !rhs)
341 goto error;
342 expr = isl_alloc_type(ctx, struct pet_expr);
343 if (!expr)
344 goto error;
346 expr->type = pet_expr_ternary;
347 expr->n_arg = 3;
348 expr->args = isl_calloc_array(ctx, struct pet_expr *, 3);
349 if (!expr->args)
350 goto error;
351 expr->args[pet_ter_cond] = cond;
352 expr->args[pet_ter_true] = lhs;
353 expr->args[pet_ter_false] = rhs;
355 return expr;
356 error:
357 pet_expr_free(cond);
358 pet_expr_free(lhs);
359 pet_expr_free(rhs);
360 return NULL;
363 /* Construct a call pet_expr that calls function "name" with "n_arg"
364 * arguments. The caller is responsible for filling in the arguments.
366 struct pet_expr *pet_expr_new_call(isl_ctx *ctx, const char *name,
367 unsigned n_arg)
369 struct pet_expr *expr;
371 expr = isl_alloc_type(ctx, struct pet_expr);
372 if (!expr)
373 return NULL;
375 expr->type = pet_expr_call;
376 expr->n_arg = n_arg;
377 expr->name = strdup(name);
378 expr->args = isl_calloc_array(ctx, struct pet_expr *, n_arg);
379 if (!expr->name || !expr->args)
380 return pet_expr_free(expr);
382 return expr;
385 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
387 struct pet_expr *pet_expr_new_cast(isl_ctx *ctx, const char *type_name,
388 struct pet_expr *arg)
390 struct pet_expr *expr;
392 if (!arg)
393 return NULL;
395 expr = isl_alloc_type(ctx, struct pet_expr);
396 if (!expr)
397 goto error;
399 expr->type = pet_expr_cast;
400 expr->n_arg = 1;
401 expr->type_name = strdup(type_name);
402 expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
403 if (!expr->type_name || !expr->args)
404 goto error;
406 expr->args[0] = arg;
408 return expr;
409 error:
410 pet_expr_free(arg);
411 pet_expr_free(expr);
412 return NULL;
415 /* Construct a pet_expr that represents the double "d".
417 struct pet_expr *pet_expr_new_double(isl_ctx *ctx, double val, const char *s)
419 struct pet_expr *expr;
421 expr = isl_calloc_type(ctx, struct pet_expr);
422 if (!expr)
423 return NULL;
425 expr->type = pet_expr_double;
426 expr->d.val = val;
427 expr->d.s = strdup(s);
428 if (!expr->d.s)
429 return pet_expr_free(expr);
431 return expr;
434 struct pet_expr *pet_expr_free(struct pet_expr *expr)
436 int i;
438 if (!expr)
439 return NULL;
441 for (i = 0; i < expr->n_arg; ++i)
442 pet_expr_free(expr->args[i]);
443 free(expr->args);
445 switch (expr->type) {
446 case pet_expr_access:
447 isl_id_free(expr->acc.ref_id);
448 isl_map_free(expr->acc.access);
449 isl_multi_pw_aff_free(expr->acc.index);
450 break;
451 case pet_expr_call:
452 free(expr->name);
453 break;
454 case pet_expr_cast:
455 free(expr->type_name);
456 break;
457 case pet_expr_double:
458 free(expr->d.s);
459 break;
460 case pet_expr_unary:
461 case pet_expr_binary:
462 case pet_expr_ternary:
463 break;
466 free(expr);
467 return NULL;
470 static void expr_dump(struct pet_expr *expr, int indent)
472 int i;
474 if (!expr)
475 return;
477 fprintf(stderr, "%*s", indent, "");
479 switch (expr->type) {
480 case pet_expr_double:
481 fprintf(stderr, "%s\n", expr->d.s);
482 break;
483 case pet_expr_access:
484 if (expr->acc.ref_id) {
485 isl_id_dump(expr->acc.ref_id);
486 fprintf(stderr, "%*s", indent, "");
488 isl_map_dump(expr->acc.access);
489 fprintf(stderr, "%*s", indent, "");
490 isl_multi_pw_aff_dump(expr->acc.index);
491 fprintf(stderr, "%*sread: %d\n", indent + 2,
492 "", expr->acc.read);
493 fprintf(stderr, "%*swrite: %d\n", indent + 2,
494 "", expr->acc.write);
495 for (i = 0; i < expr->n_arg; ++i)
496 expr_dump(expr->args[i], indent + 2);
497 break;
498 case pet_expr_unary:
499 fprintf(stderr, "%s\n", op_str[expr->op]);
500 expr_dump(expr->args[pet_un_arg], indent + 2);
501 break;
502 case pet_expr_binary:
503 fprintf(stderr, "%s\n", op_str[expr->op]);
504 expr_dump(expr->args[pet_bin_lhs], indent + 2);
505 expr_dump(expr->args[pet_bin_rhs], indent + 2);
506 break;
507 case pet_expr_ternary:
508 fprintf(stderr, "?:\n");
509 expr_dump(expr->args[pet_ter_cond], indent + 2);
510 expr_dump(expr->args[pet_ter_true], indent + 2);
511 expr_dump(expr->args[pet_ter_false], indent + 2);
512 break;
513 case pet_expr_call:
514 fprintf(stderr, "%s/%d\n", expr->name, expr->n_arg);
515 for (i = 0; i < expr->n_arg; ++i)
516 expr_dump(expr->args[i], indent + 2);
517 break;
518 case pet_expr_cast:
519 fprintf(stderr, "(%s)\n", expr->type_name);
520 for (i = 0; i < expr->n_arg; ++i)
521 expr_dump(expr->args[i], indent + 2);
522 break;
526 void pet_expr_dump(struct pet_expr *expr)
528 expr_dump(expr, 0);
531 /* Does "expr" represent an access to an unnamed space, i.e.,
532 * does it represent an affine expression?
534 int pet_expr_is_affine(struct pet_expr *expr)
536 int has_id;
538 if (!expr)
539 return -1;
540 if (expr->type != pet_expr_access)
541 return 0;
543 has_id = isl_map_has_tuple_id(expr->acc.access, isl_dim_out);
544 if (has_id < 0)
545 return -1;
547 return !has_id;
550 /* Return the identifier of the array accessed by "expr".
552 * If "expr" represents a member access, then return the identifier
553 * of the outer structure array.
555 __isl_give isl_id *pet_expr_access_get_id(struct pet_expr *expr)
557 if (!expr)
558 return NULL;
559 if (expr->type != pet_expr_access)
560 return NULL;
562 if (isl_map_range_is_wrapping(expr->acc.access)) {
563 isl_space *space;
564 isl_id *id;
566 space = isl_map_get_space(expr->acc.access);
567 space = isl_space_range(space);
568 while (space && isl_space_is_wrapping(space))
569 space = isl_space_domain(isl_space_unwrap(space));
570 id = isl_space_get_tuple_id(space, isl_dim_set);
571 isl_space_free(space);
573 return id;
576 return isl_map_get_tuple_id(expr->acc.access, isl_dim_out);
579 /* Align the parameters of expr->acc.index and expr->acc.access.
581 struct pet_expr *pet_expr_access_align_params(struct pet_expr *expr)
583 if (!expr)
584 return NULL;
585 if (expr->type != pet_expr_access)
586 return pet_expr_free(expr);
588 expr->acc.access = isl_map_align_params(expr->acc.access,
589 isl_multi_pw_aff_get_space(expr->acc.index));
590 expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
591 isl_map_get_space(expr->acc.access));
592 if (!expr->acc.access || !expr->acc.index)
593 return pet_expr_free(expr);
595 return expr;
598 /* Does "expr" represent an access to a scalar, i.e., zero-dimensional array?
600 int pet_expr_is_scalar_access(struct pet_expr *expr)
602 if (!expr)
603 return -1;
604 if (expr->type != pet_expr_access)
605 return 0;
607 return isl_map_dim(expr->acc.access, isl_dim_out) == 0;
610 /* Return 1 if the two pet_exprs are equivalent.
612 int pet_expr_is_equal(struct pet_expr *expr1, struct pet_expr *expr2)
614 int i;
616 if (!expr1 || !expr2)
617 return 0;
619 if (expr1->type != expr2->type)
620 return 0;
621 if (expr1->n_arg != expr2->n_arg)
622 return 0;
623 for (i = 0; i < expr1->n_arg; ++i)
624 if (!pet_expr_is_equal(expr1->args[i], expr2->args[i]))
625 return 0;
626 switch (expr1->type) {
627 case pet_expr_double:
628 if (strcmp(expr1->d.s, expr2->d.s))
629 return 0;
630 if (expr1->d.val != expr2->d.val)
631 return 0;
632 break;
633 case pet_expr_access:
634 if (expr1->acc.read != expr2->acc.read)
635 return 0;
636 if (expr1->acc.write != expr2->acc.write)
637 return 0;
638 if (expr1->acc.ref_id != expr2->acc.ref_id)
639 return 0;
640 if (!expr1->acc.access || !expr2->acc.access)
641 return 0;
642 if (!isl_map_is_equal(expr1->acc.access, expr2->acc.access))
643 return 0;
644 if (!expr1->acc.index || !expr2->acc.index)
645 return 0;
646 if (!isl_multi_pw_aff_plain_is_equal(expr1->acc.index,
647 expr2->acc.index))
648 return 0;
649 break;
650 case pet_expr_unary:
651 case pet_expr_binary:
652 case pet_expr_ternary:
653 if (expr1->op != expr2->op)
654 return 0;
655 break;
656 case pet_expr_call:
657 if (strcmp(expr1->name, expr2->name))
658 return 0;
659 break;
660 case pet_expr_cast:
661 if (strcmp(expr1->type_name, expr2->type_name))
662 return 0;
663 break;
666 return 1;
669 /* Add extra conditions on the parameters to all access relations in "expr".
671 * The conditions are not added to the index expression. Instead, they
672 * are used to try and simplify the index expression.
674 struct pet_expr *pet_expr_restrict(struct pet_expr *expr,
675 __isl_take isl_set *cond)
677 int i;
679 if (!expr)
680 goto error;
682 for (i = 0; i < expr->n_arg; ++i) {
683 expr->args[i] = pet_expr_restrict(expr->args[i],
684 isl_set_copy(cond));
685 if (!expr->args[i])
686 goto error;
689 if (expr->type == pet_expr_access) {
690 expr->acc.access = isl_map_intersect_params(expr->acc.access,
691 isl_set_copy(cond));
692 expr->acc.index = isl_multi_pw_aff_gist_params(
693 expr->acc.index, isl_set_copy(cond));
694 if (!expr->acc.access || !expr->acc.index)
695 goto error;
698 isl_set_free(cond);
699 return expr;
700 error:
701 isl_set_free(cond);
702 return pet_expr_free(expr);
705 /* Tag the access relation "access" with "id".
706 * That is, insert the id as the range of a wrapped relation
707 * in the domain of "access".
709 * If "access" is of the form
711 * D[i] -> A[a]
713 * then the result is of the form
715 * [D[i] -> id[]] -> A[a]
717 static __isl_give isl_map *tag_access(__isl_take isl_map *access,
718 __isl_take isl_id *id)
720 isl_space *space;
721 isl_map *add_tag;
723 space = isl_space_range(isl_map_get_space(access));
724 space = isl_space_from_range(space);
725 space = isl_space_set_tuple_id(space, isl_dim_in, id);
726 add_tag = isl_map_universe(space);
727 access = isl_map_domain_product(access, add_tag);
729 return access;
732 /* Modify all expressions of type pet_expr_access in "expr"
733 * by calling "fn" on them.
735 struct pet_expr *pet_expr_map_access(struct pet_expr *expr,
736 struct pet_expr *(*fn)(struct pet_expr *expr, void *user),
737 void *user)
739 int i;
741 if (!expr)
742 return NULL;
744 for (i = 0; i < expr->n_arg; ++i) {
745 expr->args[i] = pet_expr_map_access(expr->args[i], fn, user);
746 if (!expr->args[i])
747 return pet_expr_free(expr);
750 if (expr->type == pet_expr_access)
751 expr = fn(expr, user);
753 return expr;
756 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
758 * Return -1 on error (where fn return a negative value is treated as an error).
759 * Otherwise return 0.
761 int pet_expr_foreach_access_expr(struct pet_expr *expr,
762 int (*fn)(struct pet_expr *expr, void *user), void *user)
764 int i;
766 if (!expr)
767 return -1;
769 for (i = 0; i < expr->n_arg; ++i)
770 if (pet_expr_foreach_access_expr(expr->args[i], fn, user) < 0)
771 return -1;
773 if (expr->type == pet_expr_access)
774 return fn(expr, user);
776 return 0;
779 /* Modify the access relation and index expression
780 * of the given access expression
781 * based on the given iteration space transformation.
782 * In particular, precompose the access relation and index expression
783 * with the update function.
785 * If the access has any arguments then the domain of the access relation
786 * is a wrapped mapping from the iteration space to the space of
787 * argument values. We only need to change the domain of this wrapped
788 * mapping, so we extend the input transformation with an identity mapping
789 * on the space of argument values.
791 static struct pet_expr *update_domain(struct pet_expr *expr, void *user)
793 isl_multi_pw_aff *update = user;
794 isl_space *space;
796 update = isl_multi_pw_aff_copy(update);
798 space = isl_map_get_space(expr->acc.access);
799 space = isl_space_domain(space);
800 if (!isl_space_is_wrapping(space))
801 isl_space_free(space);
802 else {
803 isl_multi_pw_aff *id;
804 space = isl_space_unwrap(space);
805 space = isl_space_range(space);
806 space = isl_space_map_from_set(space);
807 id = isl_multi_pw_aff_identity(space);
808 update = isl_multi_pw_aff_product(update, id);
811 expr->acc.access = isl_map_preimage_domain_multi_pw_aff(
812 expr->acc.access,
813 isl_multi_pw_aff_copy(update));
814 expr->acc.index = isl_multi_pw_aff_pullback_multi_pw_aff(
815 expr->acc.index, update);
816 if (!expr->acc.access || !expr->acc.index)
817 return pet_expr_free(expr);
819 return expr;
822 /* Modify all access relations in "expr" by precomposing them with
823 * the given iteration space transformation.
825 static struct pet_expr *expr_update_domain(struct pet_expr *expr,
826 __isl_take isl_multi_pw_aff *update)
828 expr = pet_expr_map_access(expr, &update_domain, update);
829 isl_multi_pw_aff_free(update);
830 return expr;
833 /* Construct a pet_stmt with given line number and statement
834 * number from a pet_expr.
835 * The initial iteration domain is the zero-dimensional universe.
836 * The name of the domain is given by "label" if it is non-NULL.
837 * Otherwise, the name is constructed as S_<id>.
838 * The domains of all access relations are modified to refer
839 * to the statement iteration domain.
841 struct pet_stmt *pet_stmt_from_pet_expr(isl_ctx *ctx, int line,
842 __isl_take isl_id *label, int id, struct pet_expr *expr)
844 struct pet_stmt *stmt;
845 isl_space *dim;
846 isl_set *dom;
847 isl_map *sched;
848 isl_multi_pw_aff *add_name;
849 char name[50];
851 if (!expr)
852 goto error;
854 stmt = isl_calloc_type(ctx, struct pet_stmt);
855 if (!stmt)
856 goto error;
858 dim = isl_space_set_alloc(ctx, 0, 0);
859 if (label)
860 dim = isl_space_set_tuple_id(dim, isl_dim_set, label);
861 else {
862 snprintf(name, sizeof(name), "S_%d", id);
863 dim = isl_space_set_tuple_name(dim, isl_dim_set, name);
865 dom = isl_set_universe(isl_space_copy(dim));
866 sched = isl_map_from_domain(isl_set_copy(dom));
868 dim = isl_space_from_domain(dim);
869 add_name = isl_multi_pw_aff_zero(dim);
870 expr = expr_update_domain(expr, add_name);
872 stmt->line = line;
873 stmt->domain = dom;
874 stmt->schedule = sched;
875 stmt->body = expr;
877 if (!stmt->domain || !stmt->schedule || !stmt->body)
878 return pet_stmt_free(stmt);
880 return stmt;
881 error:
882 isl_id_free(label);
883 pet_expr_free(expr);
884 return NULL;
887 void *pet_stmt_free(struct pet_stmt *stmt)
889 int i;
891 if (!stmt)
892 return NULL;
894 isl_set_free(stmt->domain);
895 isl_map_free(stmt->schedule);
896 pet_expr_free(stmt->body);
898 for (i = 0; i < stmt->n_arg; ++i)
899 pet_expr_free(stmt->args[i]);
900 free(stmt->args);
902 free(stmt);
903 return NULL;
906 static void stmt_dump(struct pet_stmt *stmt, int indent)
908 int i;
910 if (!stmt)
911 return;
913 fprintf(stderr, "%*s%d\n", indent, "", stmt->line);
914 fprintf(stderr, "%*s", indent, "");
915 isl_set_dump(stmt->domain);
916 fprintf(stderr, "%*s", indent, "");
917 isl_map_dump(stmt->schedule);
918 expr_dump(stmt->body, indent);
919 for (i = 0; i < stmt->n_arg; ++i)
920 expr_dump(stmt->args[i], indent + 2);
923 void pet_stmt_dump(struct pet_stmt *stmt)
925 stmt_dump(stmt, 0);
928 /* Allocate a new pet_type with the given "name" and "definition".
930 struct pet_type *pet_type_alloc(isl_ctx *ctx, const char *name,
931 const char *definition)
933 struct pet_type *type;
935 type = isl_alloc_type(ctx, struct pet_type);
936 if (!type)
937 return NULL;
939 type->name = strdup(name);
940 type->definition = strdup(definition);
942 if (!type->name || !type->definition)
943 return pet_type_free(type);
945 return type;
948 /* Free "type" and return NULL.
950 struct pet_type *pet_type_free(struct pet_type *type)
952 if (!type)
953 return NULL;
955 free(type->name);
956 free(type->definition);
958 free(type);
959 return NULL;
962 struct pet_array *pet_array_free(struct pet_array *array)
964 if (!array)
965 return NULL;
967 isl_set_free(array->context);
968 isl_set_free(array->extent);
969 isl_set_free(array->value_bounds);
970 free(array->element_type);
972 free(array);
973 return NULL;
976 void pet_array_dump(struct pet_array *array)
978 if (!array)
979 return;
981 isl_set_dump(array->context);
982 isl_set_dump(array->extent);
983 isl_set_dump(array->value_bounds);
984 fprintf(stderr, "%s%s%s\n", array->element_type,
985 array->element_is_record ? " element-is-record" : "",
986 array->live_out ? " live-out" : "");
989 /* Alloc a pet_scop structure, with extra room for information that
990 * is only used during parsing.
992 struct pet_scop *pet_scop_alloc(isl_ctx *ctx)
994 return &isl_calloc_type(ctx, struct pet_scop_ext)->scop;
997 /* Construct a pet_scop with room for n statements.
999 static struct pet_scop *scop_alloc(isl_ctx *ctx, int n)
1001 isl_space *space;
1002 struct pet_scop *scop;
1004 scop = pet_scop_alloc(ctx);
1005 if (!scop)
1006 return NULL;
1008 space = isl_space_params_alloc(ctx, 0);
1009 scop->context = isl_set_universe(isl_space_copy(space));
1010 scop->context_value = isl_set_universe(space);
1011 scop->stmts = isl_calloc_array(ctx, struct pet_stmt *, n);
1012 if (!scop->context || !scop->stmts)
1013 return pet_scop_free(scop);
1015 scop->n_stmt = n;
1017 return scop;
1020 struct pet_scop *pet_scop_empty(isl_ctx *ctx)
1022 return scop_alloc(ctx, 0);
1025 /* Update "context" with respect to the valid parameter values for "access".
1027 static __isl_give isl_set *access_extract_context(__isl_keep isl_map *access,
1028 __isl_take isl_set *context)
1030 context = isl_set_intersect(context,
1031 isl_map_params(isl_map_copy(access)));
1032 return context;
1035 /* Update "context" with respect to the valid parameter values for "expr".
1037 * If "expr" represents a ternary operator, then a parameter value
1038 * needs to be valid for the condition and for at least one of the
1039 * remaining two arguments.
1040 * If the condition is an affine expression, then we can be a bit more specific.
1041 * The parameter then has to be valid for the second argument for
1042 * non-zero accesses and valid for the third argument for zero accesses.
1044 static __isl_give isl_set *expr_extract_context(struct pet_expr *expr,
1045 __isl_take isl_set *context)
1047 int i;
1049 if (expr->type == pet_expr_ternary) {
1050 int is_aff;
1051 isl_set *context1, *context2;
1053 is_aff = pet_expr_is_affine(expr->args[0]);
1054 if (is_aff < 0)
1055 goto error;
1057 context = expr_extract_context(expr->args[0], context);
1058 context1 = expr_extract_context(expr->args[1],
1059 isl_set_copy(context));
1060 context2 = expr_extract_context(expr->args[2], context);
1062 if (is_aff) {
1063 isl_map *access;
1064 isl_set *zero_set;
1066 access = isl_map_copy(expr->args[0]->acc.access);
1067 access = isl_map_fix_si(access, isl_dim_out, 0, 0);
1068 zero_set = isl_map_params(access);
1069 context1 = isl_set_subtract(context1,
1070 isl_set_copy(zero_set));
1071 context2 = isl_set_intersect(context2, zero_set);
1074 context = isl_set_union(context1, context2);
1075 context = isl_set_coalesce(context);
1077 return context;
1080 for (i = 0; i < expr->n_arg; ++i)
1081 context = expr_extract_context(expr->args[i], context);
1083 if (expr->type == pet_expr_access)
1084 context = access_extract_context(expr->acc.access, context);
1086 return context;
1087 error:
1088 isl_set_free(context);
1089 return NULL;
1092 /* Update "context" with respect to the valid parameter values for "stmt".
1094 * If the statement is an assume statement with an affine expression,
1095 * then intersect "context" with that expression.
1096 * Otherwise, intersect "context" with the contexts of the expressions
1097 * inside "stmt".
1099 static __isl_give isl_set *stmt_extract_context(struct pet_stmt *stmt,
1100 __isl_take isl_set *context)
1102 int i;
1104 if (pet_stmt_is_assume(stmt) &&
1105 pet_expr_is_affine(stmt->body->args[0])) {
1106 isl_multi_pw_aff *index;
1107 isl_pw_aff *pa;
1108 isl_set *cond;
1110 index = stmt->body->args[0]->acc.index;
1111 pa = isl_multi_pw_aff_get_pw_aff(index, 0);
1112 cond = isl_set_params(isl_pw_aff_non_zero_set(pa));
1113 return isl_set_intersect(context, cond);
1116 for (i = 0; i < stmt->n_arg; ++i)
1117 context = expr_extract_context(stmt->args[i], context);
1119 context = expr_extract_context(stmt->body, context);
1121 return context;
1124 /* Construct a pet_scop that contains the given pet_stmt.
1126 struct pet_scop *pet_scop_from_pet_stmt(isl_ctx *ctx, struct pet_stmt *stmt)
1128 struct pet_scop *scop;
1130 if (!stmt)
1131 return NULL;
1133 scop = scop_alloc(ctx, 1);
1134 if (!scop)
1135 goto error;
1137 scop->context = stmt_extract_context(stmt, scop->context);
1138 if (!scop->context)
1139 goto error;
1141 scop->stmts[0] = stmt;
1143 return scop;
1144 error:
1145 pet_stmt_free(stmt);
1146 pet_scop_free(scop);
1147 return NULL;
1150 /* Does "mpa" represent an access to an element of an unnamed space, i.e.,
1151 * does it represent an affine expression?
1153 static int multi_pw_aff_is_affine(__isl_keep isl_multi_pw_aff *mpa)
1155 int has_id;
1157 has_id = isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out);
1158 if (has_id < 0)
1159 return -1;
1161 return !has_id;
1164 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
1166 static __isl_give isl_pw_aff *indicator_function(__isl_take isl_set *set,
1167 __isl_take isl_set *dom)
1169 isl_pw_aff *pa;
1170 pa = isl_set_indicator_function(set);
1171 pa = isl_pw_aff_intersect_domain(pa, dom);
1172 return pa;
1175 /* Return "lhs || rhs", defined on the shared definition domain.
1177 static __isl_give isl_pw_aff *pw_aff_or(__isl_take isl_pw_aff *lhs,
1178 __isl_take isl_pw_aff *rhs)
1180 isl_set *cond;
1181 isl_set *dom;
1183 dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs)),
1184 isl_pw_aff_domain(isl_pw_aff_copy(rhs)));
1185 cond = isl_set_union(isl_pw_aff_non_zero_set(lhs),
1186 isl_pw_aff_non_zero_set(rhs));
1187 cond = isl_set_coalesce(cond);
1188 return indicator_function(cond, dom);
1191 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
1192 * ext may be equal to either ext1 or ext2.
1194 * The two skips that need to be combined are assumed to be affine expressions.
1196 * We need to skip in ext if we need to skip in either ext1 or ext2.
1197 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
1199 static struct pet_scop_ext *combine_skips(struct pet_scop_ext *ext,
1200 struct pet_scop_ext *ext1, struct pet_scop_ext *ext2,
1201 enum pet_skip type)
1203 isl_pw_aff *skip, *skip1, *skip2;
1205 if (!ext)
1206 return NULL;
1207 if (!ext1->skip[type] && !ext2->skip[type])
1208 return ext;
1209 if (!ext1->skip[type]) {
1210 if (ext == ext2)
1211 return ext;
1212 ext->skip[type] = ext2->skip[type];
1213 ext2->skip[type] = NULL;
1214 return ext;
1216 if (!ext2->skip[type]) {
1217 if (ext == ext1)
1218 return ext;
1219 ext->skip[type] = ext1->skip[type];
1220 ext1->skip[type] = NULL;
1221 return ext;
1224 if (!multi_pw_aff_is_affine(ext1->skip[type]) ||
1225 !multi_pw_aff_is_affine(ext2->skip[type]))
1226 isl_die(isl_multi_pw_aff_get_ctx(ext1->skip[type]),
1227 isl_error_internal, "can only combine affine skips",
1228 goto error);
1230 skip1 = isl_multi_pw_aff_get_pw_aff(ext1->skip[type], 0);
1231 skip2 = isl_multi_pw_aff_get_pw_aff(ext2->skip[type], 0);
1232 skip = pw_aff_or(skip1, skip2);
1233 isl_multi_pw_aff_free(ext1->skip[type]);
1234 ext1->skip[type] = NULL;
1235 isl_multi_pw_aff_free(ext2->skip[type]);
1236 ext2->skip[type] = NULL;
1237 ext->skip[type] = isl_multi_pw_aff_from_pw_aff(skip);
1238 if (!ext->skip[type])
1239 goto error;
1241 return ext;
1242 error:
1243 pet_scop_free(&ext->scop);
1244 return NULL;
1247 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
1248 * where type takes on the values pet_skip_now and pet_skip_later.
1249 * scop may be equal to either scop1 or scop2.
1251 static struct pet_scop *scop_combine_skips(struct pet_scop *scop,
1252 struct pet_scop *scop1, struct pet_scop *scop2)
1254 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1255 struct pet_scop_ext *ext1 = (struct pet_scop_ext *) scop1;
1256 struct pet_scop_ext *ext2 = (struct pet_scop_ext *) scop2;
1258 ext = combine_skips(ext, ext1, ext2, pet_skip_now);
1259 ext = combine_skips(ext, ext1, ext2, pet_skip_later);
1260 return &ext->scop;
1263 /* Update scop->start and scop->end to include the region from "start"
1264 * to "end". In particular, if scop->end == 0, then "scop" does not
1265 * have any offset information yet and we simply take the information
1266 * from "start" and "end". Otherwise, we update the fields if the
1267 * region from "start" to "end" is not already included.
1269 struct pet_scop *pet_scop_update_start_end(struct pet_scop *scop,
1270 unsigned start, unsigned end)
1272 if (!scop)
1273 return NULL;
1274 if (scop->end == 0) {
1275 scop->start = start;
1276 scop->end = end;
1277 } else {
1278 if (start < scop->start)
1279 scop->start = start;
1280 if (end > scop->end)
1281 scop->end = end;
1284 return scop;
1287 /* Does "implication" appear in the list of implications of "scop"?
1289 static int is_known_implication(struct pet_scop *scop,
1290 struct pet_implication *implication)
1292 int i;
1294 for (i = 0; i < scop->n_implication; ++i) {
1295 struct pet_implication *pi = scop->implications[i];
1296 int equal;
1298 if (pi->satisfied != implication->satisfied)
1299 continue;
1300 equal = isl_map_is_equal(pi->extension, implication->extension);
1301 if (equal < 0)
1302 return -1;
1303 if (equal)
1304 return 1;
1307 return 0;
1310 /* Store the concatenation of the implications of "scop1" and "scop2"
1311 * in "scop", removing duplicates (i.e., implications in "scop2" that
1312 * already appear in "scop1").
1314 static struct pet_scop *scop_collect_implications(isl_ctx *ctx,
1315 struct pet_scop *scop, struct pet_scop *scop1, struct pet_scop *scop2)
1317 int i, j;
1319 if (!scop)
1320 return NULL;
1322 if (scop2->n_implication == 0) {
1323 scop->n_implication = scop1->n_implication;
1324 scop->implications = scop1->implications;
1325 scop1->n_implication = 0;
1326 scop1->implications = NULL;
1327 return scop;
1330 if (scop1->n_implication == 0) {
1331 scop->n_implication = scop2->n_implication;
1332 scop->implications = scop2->implications;
1333 scop2->n_implication = 0;
1334 scop2->implications = NULL;
1335 return scop;
1338 scop->implications = isl_calloc_array(ctx, struct pet_implication *,
1339 scop1->n_implication + scop2->n_implication);
1340 if (!scop->implications)
1341 return pet_scop_free(scop);
1343 for (i = 0; i < scop1->n_implication; ++i) {
1344 scop->implications[i] = scop1->implications[i];
1345 scop1->implications[i] = NULL;
1348 scop->n_implication = scop1->n_implication;
1349 j = scop1->n_implication;
1350 for (i = 0; i < scop2->n_implication; ++i) {
1351 int known;
1353 known = is_known_implication(scop, scop2->implications[i]);
1354 if (known < 0)
1355 return pet_scop_free(scop);
1356 if (known)
1357 continue;
1358 scop->implications[j++] = scop2->implications[i];
1359 scop2->implications[i] = NULL;
1361 scop->n_implication = j;
1363 return scop;
1366 /* Combine the offset information of "scop1" and "scop2" into "scop".
1368 static struct pet_scop *scop_combine_start_end(struct pet_scop *scop,
1369 struct pet_scop *scop1, struct pet_scop *scop2)
1371 if (scop1->end)
1372 scop = pet_scop_update_start_end(scop,
1373 scop1->start, scop1->end);
1374 if (scop2->end)
1375 scop = pet_scop_update_start_end(scop,
1376 scop2->start, scop2->end);
1377 return scop;
1380 /* Construct a pet_scop that contains the offset information,
1381 * arrays, statements and skip information in "scop1" and "scop2".
1383 static struct pet_scop *pet_scop_add(isl_ctx *ctx, struct pet_scop *scop1,
1384 struct pet_scop *scop2)
1386 int i;
1387 struct pet_scop *scop = NULL;
1389 if (!scop1 || !scop2)
1390 goto error;
1392 if (scop1->n_stmt == 0) {
1393 scop2 = scop_combine_skips(scop2, scop1, scop2);
1394 pet_scop_free(scop1);
1395 return scop2;
1398 if (scop2->n_stmt == 0) {
1399 scop1 = scop_combine_skips(scop1, scop1, scop2);
1400 pet_scop_free(scop2);
1401 return scop1;
1404 scop = scop_alloc(ctx, scop1->n_stmt + scop2->n_stmt);
1405 if (!scop)
1406 goto error;
1408 scop->arrays = isl_calloc_array(ctx, struct pet_array *,
1409 scop1->n_array + scop2->n_array);
1410 if (!scop->arrays)
1411 goto error;
1412 scop->n_array = scop1->n_array + scop2->n_array;
1414 for (i = 0; i < scop1->n_stmt; ++i) {
1415 scop->stmts[i] = scop1->stmts[i];
1416 scop1->stmts[i] = NULL;
1419 for (i = 0; i < scop2->n_stmt; ++i) {
1420 scop->stmts[scop1->n_stmt + i] = scop2->stmts[i];
1421 scop2->stmts[i] = NULL;
1424 for (i = 0; i < scop1->n_array; ++i) {
1425 scop->arrays[i] = scop1->arrays[i];
1426 scop1->arrays[i] = NULL;
1429 for (i = 0; i < scop2->n_array; ++i) {
1430 scop->arrays[scop1->n_array + i] = scop2->arrays[i];
1431 scop2->arrays[i] = NULL;
1434 scop = scop_collect_implications(ctx, scop, scop1, scop2);
1435 scop = pet_scop_restrict_context(scop, isl_set_copy(scop1->context));
1436 scop = pet_scop_restrict_context(scop, isl_set_copy(scop2->context));
1437 scop = scop_combine_skips(scop, scop1, scop2);
1438 scop = scop_combine_start_end(scop, scop1, scop2);
1440 pet_scop_free(scop1);
1441 pet_scop_free(scop2);
1442 return scop;
1443 error:
1444 pet_scop_free(scop1);
1445 pet_scop_free(scop2);
1446 pet_scop_free(scop);
1447 return NULL;
1450 /* Apply the skip condition "skip" to "scop".
1451 * That is, make sure "scop" is not executed when the condition holds.
1453 * If "skip" is an affine expression, we add the conditions under
1454 * which the expression is zero to the iteration domains.
1455 * Otherwise, we add a filter on the variable attaining the value zero.
1457 static struct pet_scop *restrict_skip(struct pet_scop *scop,
1458 __isl_take isl_multi_pw_aff *skip)
1460 isl_set *zero;
1461 isl_pw_aff *pa;
1462 int is_aff;
1464 if (!scop || !skip)
1465 goto error;
1467 is_aff = multi_pw_aff_is_affine(skip);
1468 if (is_aff < 0)
1469 goto error;
1471 if (!is_aff)
1472 return pet_scop_filter(scop, skip, 0);
1474 pa = isl_multi_pw_aff_get_pw_aff(skip, 0);
1475 isl_multi_pw_aff_free(skip);
1476 zero = isl_set_params(isl_pw_aff_zero_set(pa));
1477 scop = pet_scop_restrict(scop, zero);
1479 return scop;
1480 error:
1481 isl_multi_pw_aff_free(skip);
1482 return pet_scop_free(scop);
1485 /* Construct a pet_scop that contains the arrays, statements and
1486 * skip information in "scop1" and "scop2", where the two scops
1487 * are executed "in sequence". That is, breaks and continues
1488 * in scop1 have an effect on scop2.
1490 struct pet_scop *pet_scop_add_seq(isl_ctx *ctx, struct pet_scop *scop1,
1491 struct pet_scop *scop2)
1493 if (scop1 && pet_scop_has_skip(scop1, pet_skip_now))
1494 scop2 = restrict_skip(scop2,
1495 pet_scop_get_skip(scop1, pet_skip_now));
1496 return pet_scop_add(ctx, scop1, scop2);
1499 /* Construct a pet_scop that contains the arrays, statements and
1500 * skip information in "scop1" and "scop2", where the two scops
1501 * are executed "in parallel". That is, any break or continue
1502 * in scop1 has no effect on scop2.
1504 struct pet_scop *pet_scop_add_par(isl_ctx *ctx, struct pet_scop *scop1,
1505 struct pet_scop *scop2)
1507 return pet_scop_add(ctx, scop1, scop2);
1510 void *pet_implication_free(struct pet_implication *implication)
1512 int i;
1514 if (!implication)
1515 return NULL;
1517 isl_map_free(implication->extension);
1519 free(implication);
1520 return NULL;
1523 struct pet_scop *pet_scop_free(struct pet_scop *scop)
1525 int i;
1526 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1528 if (!scop)
1529 return NULL;
1530 isl_set_free(scop->context);
1531 isl_set_free(scop->context_value);
1532 if (scop->types)
1533 for (i = 0; i < scop->n_type; ++i)
1534 pet_type_free(scop->types[i]);
1535 free(scop->types);
1536 if (scop->arrays)
1537 for (i = 0; i < scop->n_array; ++i)
1538 pet_array_free(scop->arrays[i]);
1539 free(scop->arrays);
1540 if (scop->stmts)
1541 for (i = 0; i < scop->n_stmt; ++i)
1542 pet_stmt_free(scop->stmts[i]);
1543 free(scop->stmts);
1544 if (scop->implications)
1545 for (i = 0; i < scop->n_implication; ++i)
1546 pet_implication_free(scop->implications[i]);
1547 free(scop->implications);
1548 isl_multi_pw_aff_free(ext->skip[pet_skip_now]);
1549 isl_multi_pw_aff_free(ext->skip[pet_skip_later]);
1550 free(scop);
1551 return NULL;
1554 void pet_type_dump(struct pet_type *type)
1556 if (!type)
1557 return;
1559 fprintf(stderr, "%s -> %s\n", type->name, type->definition);
1562 void pet_implication_dump(struct pet_implication *implication)
1564 if (!implication)
1565 return;
1567 fprintf(stderr, "%d\n", implication->satisfied);
1568 isl_map_dump(implication->extension);
1571 void pet_scop_dump(struct pet_scop *scop)
1573 int i;
1574 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1576 if (!scop)
1577 return;
1579 isl_set_dump(scop->context);
1580 isl_set_dump(scop->context_value);
1581 for (i = 0; i < scop->n_type; ++i)
1582 pet_type_dump(scop->types[i]);
1583 for (i = 0; i < scop->n_array; ++i)
1584 pet_array_dump(scop->arrays[i]);
1585 for (i = 0; i < scop->n_stmt; ++i)
1586 pet_stmt_dump(scop->stmts[i]);
1587 for (i = 0; i < scop->n_implication; ++i)
1588 pet_implication_dump(scop->implications[i]);
1590 if (ext->skip[0]) {
1591 fprintf(stderr, "skip\n");
1592 isl_multi_pw_aff_dump(ext->skip[0]);
1593 isl_multi_pw_aff_dump(ext->skip[1]);
1597 /* Return 1 if the two pet_arrays are equivalent.
1599 * We don't compare element_size as this may be target dependent.
1601 int pet_array_is_equal(struct pet_array *array1, struct pet_array *array2)
1603 if (!array1 || !array2)
1604 return 0;
1606 if (!isl_set_is_equal(array1->context, array2->context))
1607 return 0;
1608 if (!isl_set_is_equal(array1->extent, array2->extent))
1609 return 0;
1610 if (!!array1->value_bounds != !!array2->value_bounds)
1611 return 0;
1612 if (array1->value_bounds &&
1613 !isl_set_is_equal(array1->value_bounds, array2->value_bounds))
1614 return 0;
1615 if (strcmp(array1->element_type, array2->element_type))
1616 return 0;
1617 if (array1->element_is_record != array2->element_is_record)
1618 return 0;
1619 if (array1->live_out != array2->live_out)
1620 return 0;
1621 if (array1->uniquely_defined != array2->uniquely_defined)
1622 return 0;
1623 if (array1->declared != array2->declared)
1624 return 0;
1625 if (array1->exposed != array2->exposed)
1626 return 0;
1628 return 1;
1631 /* Return 1 if the two pet_stmts are equivalent.
1633 int pet_stmt_is_equal(struct pet_stmt *stmt1, struct pet_stmt *stmt2)
1635 int i;
1637 if (!stmt1 || !stmt2)
1638 return 0;
1640 if (stmt1->line != stmt2->line)
1641 return 0;
1642 if (!isl_set_is_equal(stmt1->domain, stmt2->domain))
1643 return 0;
1644 if (!isl_map_is_equal(stmt1->schedule, stmt2->schedule))
1645 return 0;
1646 if (!pet_expr_is_equal(stmt1->body, stmt2->body))
1647 return 0;
1648 if (stmt1->n_arg != stmt2->n_arg)
1649 return 0;
1650 for (i = 0; i < stmt1->n_arg; ++i) {
1651 if (!pet_expr_is_equal(stmt1->args[i], stmt2->args[i]))
1652 return 0;
1655 return 1;
1658 /* Return 1 if the two pet_types are equivalent.
1660 * We only compare the names of the types since the exact representation
1661 * of the definition may depend on the version of clang being used.
1663 int pet_type_is_equal(struct pet_type *type1, struct pet_type *type2)
1665 if (!type1 || !type2)
1666 return 0;
1668 if (strcmp(type1->name, type2->name))
1669 return 0;
1671 return 1;
1674 /* Return 1 if the two pet_implications are equivalent.
1676 int pet_implication_is_equal(struct pet_implication *implication1,
1677 struct pet_implication *implication2)
1679 if (!implication1 || !implication2)
1680 return 0;
1682 if (implication1->satisfied != implication2->satisfied)
1683 return 0;
1684 if (!isl_map_is_equal(implication1->extension, implication2->extension))
1685 return 0;
1687 return 1;
1690 /* Return 1 if the two pet_scops are equivalent.
1692 int pet_scop_is_equal(struct pet_scop *scop1, struct pet_scop *scop2)
1694 int i;
1696 if (!scop1 || !scop2)
1697 return 0;
1699 if (!isl_set_is_equal(scop1->context, scop2->context))
1700 return 0;
1701 if (!isl_set_is_equal(scop1->context_value, scop2->context_value))
1702 return 0;
1704 if (scop1->n_type != scop2->n_type)
1705 return 0;
1706 for (i = 0; i < scop1->n_type; ++i)
1707 if (!pet_type_is_equal(scop1->types[i], scop2->types[i]))
1708 return 0;
1710 if (scop1->n_array != scop2->n_array)
1711 return 0;
1712 for (i = 0; i < scop1->n_array; ++i)
1713 if (!pet_array_is_equal(scop1->arrays[i], scop2->arrays[i]))
1714 return 0;
1716 if (scop1->n_stmt != scop2->n_stmt)
1717 return 0;
1718 for (i = 0; i < scop1->n_stmt; ++i)
1719 if (!pet_stmt_is_equal(scop1->stmts[i], scop2->stmts[i]))
1720 return 0;
1722 if (scop1->n_implication != scop2->n_implication)
1723 return 0;
1724 for (i = 0; i < scop1->n_implication; ++i)
1725 if (!pet_implication_is_equal(scop1->implications[i],
1726 scop2->implications[i]))
1727 return 0;
1729 return 1;
1732 /* Prefix the schedule of "stmt" with an extra dimension with constant
1733 * value "pos".
1735 struct pet_stmt *pet_stmt_prefix(struct pet_stmt *stmt, int pos)
1737 if (!stmt)
1738 return NULL;
1740 stmt->schedule = isl_map_insert_dims(stmt->schedule, isl_dim_out, 0, 1);
1741 stmt->schedule = isl_map_fix_si(stmt->schedule, isl_dim_out, 0, pos);
1742 if (!stmt->schedule)
1743 return pet_stmt_free(stmt);
1745 return stmt;
1748 /* Prefix the schedules of all statements in "scop" with an extra
1749 * dimension with constant value "pos".
1751 struct pet_scop *pet_scop_prefix(struct pet_scop *scop, int pos)
1753 int i;
1755 if (!scop)
1756 return NULL;
1758 for (i = 0; i < scop->n_stmt; ++i) {
1759 scop->stmts[i] = pet_stmt_prefix(scop->stmts[i], pos);
1760 if (!scop->stmts[i])
1761 return pet_scop_free(scop);
1764 return scop;
1767 /* Given a set with a parameter at "param_pos" that refers to the
1768 * iterator, "move" the iterator to the first set dimension.
1769 * That is, essentially equate the parameter to the first set dimension
1770 * and then project it out.
1772 * The first set dimension may however refer to a virtual iterator,
1773 * while the parameter refers to the "real" iterator.
1774 * We therefore need to take into account the affine expression "iv_map", which
1775 * expresses the real iterator in terms of the virtual iterator.
1776 * In particular, we equate the set dimension to the input of the map
1777 * and the parameter to the output of the map and then project out
1778 * everything we don't need anymore.
1780 static __isl_give isl_set *internalize_iv(__isl_take isl_set *set,
1781 int param_pos, __isl_take isl_aff *iv_map)
1783 isl_map *map, *map2;
1784 map = isl_map_from_domain(set);
1785 map = isl_map_add_dims(map, isl_dim_out, 1);
1786 map = isl_map_equate(map, isl_dim_in, 0, isl_dim_out, 0);
1787 map2 = isl_map_from_aff(iv_map);
1788 map2 = isl_map_align_params(map2, isl_map_get_space(map));
1789 map = isl_map_apply_range(map, map2);
1790 map = isl_map_equate(map, isl_dim_param, param_pos, isl_dim_out, 0);
1791 map = isl_map_project_out(map, isl_dim_param, param_pos, 1);
1792 return isl_map_domain(map);
1795 /* Data used in embed_access.
1796 * extend adds an iterator to the iteration domain (through precomposition).
1797 * iv_map expresses the real iterator in terms of the virtual iterator
1798 * var_id represents the induction variable of the corresponding loop
1800 struct pet_embed_access {
1801 isl_multi_pw_aff *extend;
1802 isl_aff *iv_map;
1803 isl_id *var_id;
1806 /* Given an index expression, return an expression for the outer iterator.
1808 static __isl_give isl_aff *index_outer_iterator(
1809 __isl_take isl_multi_pw_aff *index)
1811 isl_space *space;
1812 isl_local_space *ls;
1814 space = isl_multi_pw_aff_get_domain_space(index);
1815 isl_multi_pw_aff_free(index);
1817 ls = isl_local_space_from_space(space);
1818 return isl_aff_var_on_domain(ls, isl_dim_set, 0);
1821 /* Replace an index expression that references the new (outer) iterator variable
1822 * by one that references the corresponding (real) iterator.
1824 * The input index expression is of the form
1826 * { S[i',...] -> i[] }
1828 * where i' refers to the virtual iterator.
1830 * iv_map is of the form
1832 * { [i'] -> [i] }
1834 * Return the index expression
1836 * { S[i',...] -> [i] }
1838 static __isl_give isl_multi_pw_aff *replace_by_iterator(
1839 __isl_take isl_multi_pw_aff *index, __isl_take isl_aff *iv_map)
1841 isl_space *space;
1842 isl_aff *aff;
1844 aff = index_outer_iterator(index);
1845 space = isl_aff_get_space(aff);
1846 iv_map = isl_aff_align_params(iv_map, space);
1847 aff = isl_aff_pullback_aff(iv_map, aff);
1849 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
1852 /* Given an index expression "index" that refers to the (real) iterator
1853 * through the parameter at position "pos", plug in "iv_map", expressing
1854 * the real iterator in terms of the virtual (outer) iterator.
1856 * In particular, the index expression is of the form
1858 * [..., i, ...] -> { S[i',...] -> ... i ... }
1860 * where i refers to the real iterator and i' refers to the virtual iterator.
1862 * iv_map is of the form
1864 * { [i'] -> [i] }
1866 * Return the index expression
1868 * [..., ...] -> { S[i',...] -> ... iv_map(i') ... }
1871 * We first move the parameter to the input
1873 * [..., ...] -> { [i, i',...] -> ... i ... }
1875 * and construct
1877 * { S[i',...] -> [i=iv_map(i'), i', ...] }
1879 * and then combine the two to obtain the desired result.
1881 static __isl_give isl_multi_pw_aff *index_internalize_iv(
1882 __isl_take isl_multi_pw_aff *index, int pos, __isl_take isl_aff *iv_map)
1884 isl_space *space = isl_multi_pw_aff_get_domain_space(index);
1885 isl_multi_aff *ma;
1887 space = isl_space_drop_dims(space, isl_dim_param, pos, 1);
1888 index = isl_multi_pw_aff_move_dims(index, isl_dim_in, 0,
1889 isl_dim_param, pos, 1);
1891 space = isl_space_map_from_set(space);
1892 ma = isl_multi_aff_identity(isl_space_copy(space));
1893 iv_map = isl_aff_align_params(iv_map, space);
1894 iv_map = isl_aff_pullback_aff(iv_map, isl_multi_aff_get_aff(ma, 0));
1895 ma = isl_multi_aff_flat_range_product(
1896 isl_multi_aff_from_aff(iv_map), ma);
1897 index = isl_multi_pw_aff_pullback_multi_aff(index, ma);
1899 return index;
1902 /* Does the index expression "index" reference a virtual array, i.e.,
1903 * one with user pointer equal to NULL?
1904 * A virtual array does not have any members.
1906 static int index_is_virtual_array(__isl_keep isl_multi_pw_aff *index)
1908 isl_id *id;
1909 int is_virtual;
1911 if (!isl_multi_pw_aff_has_tuple_id(index, isl_dim_out))
1912 return 0;
1913 if (isl_multi_pw_aff_range_is_wrapping(index))
1914 return 0;
1915 id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
1916 is_virtual = !isl_id_get_user(id);
1917 isl_id_free(id);
1919 return is_virtual;
1922 /* Does the access relation "access" reference a virtual array, i.e.,
1923 * one with user pointer equal to NULL?
1924 * A virtual array does not have any members.
1926 static int access_is_virtual_array(__isl_keep isl_map *access)
1928 isl_id *id;
1929 int is_virtual;
1931 if (!isl_map_has_tuple_id(access, isl_dim_out))
1932 return 0;
1933 if (isl_map_range_is_wrapping(access))
1934 return 0;
1935 id = isl_map_get_tuple_id(access, isl_dim_out);
1936 is_virtual = !isl_id_get_user(id);
1937 isl_id_free(id);
1939 return is_virtual;
1942 /* Embed the given index expression in an extra outer loop.
1943 * The domain of the index expression has already been updated.
1945 * If the access refers to the induction variable, then it is
1946 * turned into an access to the set of integers with index (and value)
1947 * equal to the induction variable.
1949 * If the accessed array is a virtual array (with user
1950 * pointer equal to NULL), as created by create_test_index,
1951 * then it is extended along with the domain of the index expression.
1953 static __isl_give isl_multi_pw_aff *embed_index_expression(
1954 __isl_take isl_multi_pw_aff *index, struct pet_embed_access *data)
1956 isl_id *array_id = NULL;
1957 int pos;
1959 if (isl_multi_pw_aff_has_tuple_id(index, isl_dim_out))
1960 array_id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
1961 if (array_id == data->var_id) {
1962 index = replace_by_iterator(index, isl_aff_copy(data->iv_map));
1963 } else if (index_is_virtual_array(index)) {
1964 isl_aff *aff;
1965 isl_multi_pw_aff *mpa;
1967 aff = index_outer_iterator(isl_multi_pw_aff_copy(index));
1968 mpa = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
1969 index = isl_multi_pw_aff_flat_range_product(mpa, index);
1970 index = isl_multi_pw_aff_set_tuple_id(index, isl_dim_out,
1971 isl_id_copy(array_id));
1973 isl_id_free(array_id);
1975 pos = isl_multi_pw_aff_find_dim_by_id(index,
1976 isl_dim_param, data->var_id);
1977 if (pos >= 0)
1978 index = index_internalize_iv(index, pos,
1979 isl_aff_copy(data->iv_map));
1980 index = isl_multi_pw_aff_set_dim_id(index, isl_dim_in, 0,
1981 isl_id_copy(data->var_id));
1983 return index;
1986 /* Embed the given access relation in an extra outer loop.
1987 * The domain of the access relation has already been updated.
1989 * If the access refers to the induction variable, then it is
1990 * turned into an access to the set of integers with index (and value)
1991 * equal to the induction variable.
1993 * If the induction variable appears in the constraints (as a parameter),
1994 * then the parameter is equated to the newly introduced iteration
1995 * domain dimension and subsequently projected out.
1997 * Similarly, if the accessed array is a virtual array (with user
1998 * pointer equal to NULL), as created by create_test_index,
1999 * then it is extended along with the domain of the access.
2001 static __isl_give isl_map *embed_access_relation(__isl_take isl_map *access,
2002 struct pet_embed_access *data)
2004 isl_id *array_id = NULL;
2005 int pos;
2007 if (isl_map_has_tuple_id(access, isl_dim_out))
2008 array_id = isl_map_get_tuple_id(access, isl_dim_out);
2009 if (array_id == data->var_id || access_is_virtual_array(access)) {
2010 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
2011 access = isl_map_equate(access,
2012 isl_dim_in, 0, isl_dim_out, 0);
2013 if (array_id == data->var_id)
2014 access = isl_map_apply_range(access,
2015 isl_map_from_aff(isl_aff_copy(data->iv_map)));
2016 else
2017 access = isl_map_set_tuple_id(access, isl_dim_out,
2018 isl_id_copy(array_id));
2020 isl_id_free(array_id);
2022 pos = isl_map_find_dim_by_id(access, isl_dim_param, data->var_id);
2023 if (pos >= 0) {
2024 isl_set *set = isl_map_wrap(access);
2025 set = internalize_iv(set, pos, isl_aff_copy(data->iv_map));
2026 access = isl_set_unwrap(set);
2028 access = isl_map_set_dim_id(access, isl_dim_in, 0,
2029 isl_id_copy(data->var_id));
2031 return access;
2034 /* Given an access expression, embed the associated access relation and
2035 * index expression in an extra outer loop.
2037 * We first update the domains to insert the extra dimension and
2038 * then update the access relation and index expression to take
2039 * into account the mapping "iv_map" from virtual iterator
2040 * to real iterator.
2042 static struct pet_expr *embed_access(struct pet_expr *expr, void *user)
2044 struct pet_embed_access *data = user;
2046 expr = update_domain(expr, data->extend);
2047 if (!expr)
2048 return NULL;
2050 expr->acc.access = embed_access_relation(expr->acc.access, data);
2051 expr->acc.index = embed_index_expression(expr->acc.index, data);
2052 if (!expr->acc.access || !expr->acc.index)
2053 return pet_expr_free(expr);
2055 return expr;
2058 /* Embed all access subexpressions of "expr" in an extra loop.
2059 * "extend" inserts an outer loop iterator in the iteration domains
2060 * (through precomposition).
2061 * "iv_map" expresses the real iterator in terms of the virtual iterator
2062 * "var_id" represents the induction variable.
2064 static struct pet_expr *expr_embed(struct pet_expr *expr,
2065 __isl_take isl_multi_pw_aff *extend, __isl_take isl_aff *iv_map,
2066 __isl_keep isl_id *var_id)
2068 struct pet_embed_access data =
2069 { .extend = extend, .iv_map = iv_map, .var_id = var_id };
2071 expr = pet_expr_map_access(expr, &embed_access, &data);
2072 isl_aff_free(iv_map);
2073 isl_multi_pw_aff_free(extend);
2074 return expr;
2077 /* Embed the given pet_stmt in an extra outer loop with iteration domain
2078 * "dom" and schedule "sched". "var_id" represents the induction variable
2079 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
2080 * That is, it expresses the iterator that some of the parameters in "stmt"
2081 * may refer to in terms of the iterator used in "dom" and
2082 * the domain of "sched".
2084 * The iteration domain and schedule of the statement are updated
2085 * according to the iteration domain and schedule of the new loop.
2086 * If stmt->domain is a wrapped map, then the iteration domain
2087 * is the domain of this map, so we need to be careful to adjust
2088 * this domain.
2090 * If the induction variable appears in the constraints (as a parameter)
2091 * of the current iteration domain or the schedule of the statement,
2092 * then the parameter is equated to the newly introduced iteration
2093 * domain dimension and subsequently projected out.
2095 * Finally, all access relations are updated based on the extra loop.
2097 static struct pet_stmt *pet_stmt_embed(struct pet_stmt *stmt,
2098 __isl_take isl_set *dom, __isl_take isl_map *sched,
2099 __isl_take isl_aff *iv_map, __isl_take isl_id *var_id)
2101 int i;
2102 int pos;
2103 isl_id *stmt_id;
2104 isl_space *dim;
2105 isl_multi_pw_aff *extend;
2107 if (!stmt)
2108 goto error;
2110 if (isl_set_is_wrapping(stmt->domain)) {
2111 isl_map *map;
2112 isl_map *ext;
2113 isl_space *ran_dim;
2115 map = isl_set_unwrap(stmt->domain);
2116 stmt_id = isl_map_get_tuple_id(map, isl_dim_in);
2117 ran_dim = isl_space_range(isl_map_get_space(map));
2118 ext = isl_map_from_domain_and_range(isl_set_copy(dom),
2119 isl_set_universe(ran_dim));
2120 map = isl_map_flat_domain_product(ext, map);
2121 map = isl_map_set_tuple_id(map, isl_dim_in,
2122 isl_id_copy(stmt_id));
2123 dim = isl_space_domain(isl_map_get_space(map));
2124 stmt->domain = isl_map_wrap(map);
2125 } else {
2126 stmt_id = isl_set_get_tuple_id(stmt->domain);
2127 stmt->domain = isl_set_flat_product(isl_set_copy(dom),
2128 stmt->domain);
2129 stmt->domain = isl_set_set_tuple_id(stmt->domain,
2130 isl_id_copy(stmt_id));
2131 dim = isl_set_get_space(stmt->domain);
2134 pos = isl_set_find_dim_by_id(stmt->domain, isl_dim_param, var_id);
2135 if (pos >= 0)
2136 stmt->domain = internalize_iv(stmt->domain, pos,
2137 isl_aff_copy(iv_map));
2139 stmt->schedule = isl_map_flat_product(sched, stmt->schedule);
2140 stmt->schedule = isl_map_set_tuple_id(stmt->schedule,
2141 isl_dim_in, stmt_id);
2143 pos = isl_map_find_dim_by_id(stmt->schedule, isl_dim_param, var_id);
2144 if (pos >= 0) {
2145 isl_set *set = isl_map_wrap(stmt->schedule);
2146 set = internalize_iv(set, pos, isl_aff_copy(iv_map));
2147 stmt->schedule = isl_set_unwrap(set);
2150 dim = isl_space_map_from_set(dim);
2151 extend = isl_multi_pw_aff_identity(dim);
2152 extend = isl_multi_pw_aff_drop_dims(extend, isl_dim_out, 0, 1);
2153 extend = isl_multi_pw_aff_set_tuple_id(extend, isl_dim_out,
2154 isl_multi_pw_aff_get_tuple_id(extend, isl_dim_in));
2155 for (i = 0; i < stmt->n_arg; ++i)
2156 stmt->args[i] = expr_embed(stmt->args[i],
2157 isl_multi_pw_aff_copy(extend),
2158 isl_aff_copy(iv_map), var_id);
2159 stmt->body = expr_embed(stmt->body, extend, iv_map, var_id);
2161 isl_set_free(dom);
2162 isl_id_free(var_id);
2164 for (i = 0; i < stmt->n_arg; ++i)
2165 if (!stmt->args[i])
2166 return pet_stmt_free(stmt);
2167 if (!stmt->domain || !stmt->schedule || !stmt->body)
2168 return pet_stmt_free(stmt);
2169 return stmt;
2170 error:
2171 isl_set_free(dom);
2172 isl_map_free(sched);
2173 isl_aff_free(iv_map);
2174 isl_id_free(var_id);
2175 return NULL;
2178 /* Embed the given pet_array in an extra outer loop with iteration domain
2179 * "dom".
2180 * This embedding only has an effect on virtual arrays (those with
2181 * user pointer equal to NULL), which need to be extended along with
2182 * the iteration domain.
2184 static struct pet_array *pet_array_embed(struct pet_array *array,
2185 __isl_take isl_set *dom)
2187 isl_id *array_id = NULL;
2189 if (!array)
2190 goto error;
2192 if (isl_set_has_tuple_id(array->extent))
2193 array_id = isl_set_get_tuple_id(array->extent);
2195 if (array_id && !isl_id_get_user(array_id)) {
2196 array->extent = isl_set_flat_product(dom, array->extent);
2197 array->extent = isl_set_set_tuple_id(array->extent, array_id);
2198 if (!array->extent)
2199 return pet_array_free(array);
2200 } else {
2201 isl_set_free(dom);
2202 isl_id_free(array_id);
2205 return array;
2206 error:
2207 isl_set_free(dom);
2208 return NULL;
2211 /* Project out all unnamed parameters from "set" and return the result.
2213 static __isl_give isl_set *set_project_out_unnamed_params(
2214 __isl_take isl_set *set)
2216 int i, n;
2218 n = isl_set_dim(set, isl_dim_param);
2219 for (i = n - 1; i >= 0; --i) {
2220 if (isl_set_has_dim_name(set, isl_dim_param, i))
2221 continue;
2222 set = isl_set_project_out(set, isl_dim_param, i, 1);
2225 return set;
2228 /* Update the context with respect to an embedding into a loop
2229 * with iteration domain "dom" and induction variable "id".
2230 * "iv_map" expresses the real iterator (parameter "id") in terms
2231 * of a possibly virtual iterator (used in "dom").
2233 * If the current context is independent of "id", we don't need
2234 * to do anything.
2235 * Otherwise, a parameter value is invalid for the embedding if
2236 * any of the corresponding iterator values is invalid.
2237 * That is, a parameter value is valid only if all the corresponding
2238 * iterator values are valid.
2239 * We therefore compute the set of parameters
2241 * forall i in dom : valid (i)
2243 * or
2245 * not exists i in dom : not valid(i)
2247 * i.e.,
2249 * not exists i in dom \ valid(i)
2251 * Before we subtract valid(i) from dom, we first need to substitute
2252 * the real iterator for the virtual iterator.
2254 * If there are any unnamed parameters in "dom", then we consider
2255 * a parameter value to be valid if it is valid for any value of those
2256 * unnamed parameters. They are therefore projected out at the end.
2258 static __isl_give isl_set *context_embed(__isl_take isl_set *context,
2259 __isl_keep isl_set *dom, __isl_keep isl_aff *iv_map,
2260 __isl_keep isl_id *id)
2262 int pos;
2263 isl_multi_aff *ma;
2265 pos = isl_set_find_dim_by_id(context, isl_dim_param, id);
2266 if (pos < 0)
2267 return context;
2269 context = isl_set_from_params(context);
2270 context = isl_set_add_dims(context, isl_dim_set, 1);
2271 context = isl_set_equate(context, isl_dim_param, pos, isl_dim_set, 0);
2272 context = isl_set_project_out(context, isl_dim_param, pos, 1);
2273 ma = isl_multi_aff_from_aff(isl_aff_copy(iv_map));
2274 context = isl_set_preimage_multi_aff(context, ma);
2275 context = isl_set_subtract(isl_set_copy(dom), context);
2276 context = isl_set_params(context);
2277 context = isl_set_complement(context);
2278 context = set_project_out_unnamed_params(context);
2279 return context;
2282 /* Update the implication with respect to an embedding into a loop
2283 * with iteration domain "dom".
2285 * Since embed_access extends virtual arrays along with the domain
2286 * of the access, we need to do the same with domain and range
2287 * of the implication. Since the original implication is only valid
2288 * within a given iteration of the loop, the extended implication
2289 * maps the extra array dimension corresponding to the extra loop
2290 * to itself.
2292 static struct pet_implication *pet_implication_embed(
2293 struct pet_implication *implication, __isl_take isl_set *dom)
2295 isl_id *id;
2296 isl_map *map;
2298 if (!implication)
2299 goto error;
2301 map = isl_set_identity(dom);
2302 id = isl_map_get_tuple_id(implication->extension, isl_dim_in);
2303 map = isl_map_flat_product(map, implication->extension);
2304 map = isl_map_set_tuple_id(map, isl_dim_in, isl_id_copy(id));
2305 map = isl_map_set_tuple_id(map, isl_dim_out, id);
2306 implication->extension = map;
2307 if (!implication->extension)
2308 return pet_implication_free(implication);
2310 return implication;
2311 error:
2312 isl_set_free(dom);
2313 return NULL;
2316 /* Embed all statements and arrays in "scop" in an extra outer loop
2317 * with iteration domain "dom" and schedule "sched".
2318 * "id" represents the induction variable of the loop.
2319 * "iv_map" maps a possibly virtual iterator to the real iterator.
2320 * That is, it expresses the iterator that some of the parameters in "scop"
2321 * may refer to in terms of the iterator used in "dom" and
2322 * the domain of "sched".
2324 * Any skip conditions within the loop have no effect outside of the loop.
2325 * The caller is responsible for making sure skip[pet_skip_later] has been
2326 * taken into account.
2328 struct pet_scop *pet_scop_embed(struct pet_scop *scop, __isl_take isl_set *dom,
2329 __isl_take isl_map *sched, __isl_take isl_aff *iv_map,
2330 __isl_take isl_id *id)
2332 int i;
2334 if (!scop)
2335 goto error;
2337 pet_scop_reset_skip(scop, pet_skip_now);
2338 pet_scop_reset_skip(scop, pet_skip_later);
2340 scop->context = context_embed(scop->context, dom, iv_map, id);
2341 if (!scop->context)
2342 goto error;
2344 for (i = 0; i < scop->n_stmt; ++i) {
2345 scop->stmts[i] = pet_stmt_embed(scop->stmts[i],
2346 isl_set_copy(dom), isl_map_copy(sched),
2347 isl_aff_copy(iv_map), isl_id_copy(id));
2348 if (!scop->stmts[i])
2349 goto error;
2352 for (i = 0; i < scop->n_array; ++i) {
2353 scop->arrays[i] = pet_array_embed(scop->arrays[i],
2354 isl_set_copy(dom));
2355 if (!scop->arrays[i])
2356 goto error;
2359 for (i = 0; i < scop->n_implication; ++i) {
2360 scop->implications[i] =
2361 pet_implication_embed(scop->implications[i],
2362 isl_set_copy(dom));
2363 if (!scop->implications[i])
2364 goto error;
2367 isl_set_free(dom);
2368 isl_map_free(sched);
2369 isl_aff_free(iv_map);
2370 isl_id_free(id);
2371 return scop;
2372 error:
2373 isl_set_free(dom);
2374 isl_map_free(sched);
2375 isl_aff_free(iv_map);
2376 isl_id_free(id);
2377 return pet_scop_free(scop);
2380 /* Add extra conditions on the parameters to the iteration domain of "stmt".
2382 static struct pet_stmt *stmt_restrict(struct pet_stmt *stmt,
2383 __isl_take isl_set *cond)
2385 if (!stmt)
2386 goto error;
2388 stmt->domain = isl_set_intersect_params(stmt->domain, cond);
2390 return stmt;
2391 error:
2392 isl_set_free(cond);
2393 return pet_stmt_free(stmt);
2396 /* Add extra conditions to scop->skip[type].
2398 * The new skip condition only holds if it held before
2399 * and the condition is true. It does not hold if it did not hold
2400 * before or the condition is false.
2402 * The skip condition is assumed to be an affine expression.
2404 static struct pet_scop *pet_scop_restrict_skip(struct pet_scop *scop,
2405 enum pet_skip type, __isl_keep isl_set *cond)
2407 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2408 isl_pw_aff *skip;
2409 isl_set *dom;
2411 if (!scop)
2412 return NULL;
2413 if (!ext->skip[type])
2414 return scop;
2416 if (!multi_pw_aff_is_affine(ext->skip[type]))
2417 isl_die(isl_multi_pw_aff_get_ctx(ext->skip[type]),
2418 isl_error_internal, "can only restrict affine skips",
2419 return pet_scop_free(scop));
2421 skip = isl_multi_pw_aff_get_pw_aff(ext->skip[type], 0);
2422 dom = isl_pw_aff_domain(isl_pw_aff_copy(skip));
2423 cond = isl_set_copy(cond);
2424 cond = isl_set_from_params(cond);
2425 cond = isl_set_intersect(cond, isl_pw_aff_non_zero_set(skip));
2426 skip = indicator_function(cond, dom);
2427 isl_multi_pw_aff_free(ext->skip[type]);
2428 ext->skip[type] = isl_multi_pw_aff_from_pw_aff(skip);
2429 if (!ext->skip[type])
2430 return pet_scop_free(scop);
2432 return scop;
2435 /* Add extra conditions on the parameters to all iteration domains
2436 * and skip conditions.
2438 * A parameter value is valid for the result if it was valid
2439 * for the original scop and satisfies "cond" or if it does
2440 * not satisfy "cond" as in this case the scop is not executed
2441 * and the original constraints on the parameters are irrelevant.
2443 struct pet_scop *pet_scop_restrict(struct pet_scop *scop,
2444 __isl_take isl_set *cond)
2446 int i;
2448 scop = pet_scop_restrict_skip(scop, pet_skip_now, cond);
2449 scop = pet_scop_restrict_skip(scop, pet_skip_later, cond);
2451 if (!scop)
2452 goto error;
2454 scop->context = isl_set_intersect(scop->context, isl_set_copy(cond));
2455 scop->context = isl_set_union(scop->context,
2456 isl_set_complement(isl_set_copy(cond)));
2457 scop->context = isl_set_coalesce(scop->context);
2458 scop->context = set_project_out_unnamed_params(scop->context);
2459 if (!scop->context)
2460 goto error;
2462 for (i = 0; i < scop->n_stmt; ++i) {
2463 scop->stmts[i] = stmt_restrict(scop->stmts[i],
2464 isl_set_copy(cond));
2465 if (!scop->stmts[i])
2466 goto error;
2469 isl_set_free(cond);
2470 return scop;
2471 error:
2472 isl_set_free(cond);
2473 return pet_scop_free(scop);
2476 /* Construct a function that (upon precomposition) inserts
2477 * a filter value with name "id" and value "satisfied"
2478 * in the list of filter values embedded in the set space "space".
2480 * If "space" does not contain any filter values yet, we first create
2481 * a function that inserts 0 filter values, i.e.,
2483 * [space -> []] -> space
2485 * We can now assume that space is of the form [dom -> [filters]]
2486 * We construct an identity mapping on dom and a mapping on filters
2487 * that (upon precomposition) inserts the new filter
2489 * dom -> dom
2490 * [satisfied, filters] -> [filters]
2492 * and then compute the cross product
2494 * [dom -> [satisfied, filters]] -> [dom -> [filters]]
2496 static __isl_give isl_pw_multi_aff *insert_filter_pma(
2497 __isl_take isl_space *space, __isl_take isl_id *id, int satisfied)
2499 isl_space *space2;
2500 isl_multi_aff *ma;
2501 isl_pw_multi_aff *pma0, *pma, *pma_dom, *pma_ran;
2502 isl_set *dom;
2504 if (isl_space_is_wrapping(space)) {
2505 space2 = isl_space_map_from_set(isl_space_copy(space));
2506 ma = isl_multi_aff_identity(space2);
2507 space = isl_space_unwrap(space);
2508 } else {
2509 space = isl_space_from_domain(space);
2510 ma = isl_multi_aff_domain_map(isl_space_copy(space));
2513 space2 = isl_space_domain(isl_space_copy(space));
2514 pma_dom = isl_pw_multi_aff_identity(isl_space_map_from_set(space2));
2515 space = isl_space_range(space);
2516 space = isl_space_insert_dims(space, isl_dim_set, 0, 1);
2517 pma_ran = isl_pw_multi_aff_project_out_map(space, isl_dim_set, 0, 1);
2518 pma_ran = isl_pw_multi_aff_set_dim_id(pma_ran, isl_dim_in, 0, id);
2519 pma_ran = isl_pw_multi_aff_fix_si(pma_ran, isl_dim_in, 0, satisfied);
2520 pma = isl_pw_multi_aff_product(pma_dom, pma_ran);
2522 pma0 = isl_pw_multi_aff_from_multi_aff(ma);
2523 pma = isl_pw_multi_aff_pullback_pw_multi_aff(pma0, pma);
2525 return pma;
2528 /* Insert an argument expression corresponding to "test" in front
2529 * of the list of arguments described by *n_arg and *args.
2531 static int args_insert_access(unsigned *n_arg, struct pet_expr ***args,
2532 __isl_keep isl_multi_pw_aff *test)
2534 int i;
2535 isl_ctx *ctx = isl_multi_pw_aff_get_ctx(test);
2537 if (!test)
2538 return -1;
2540 if (!*args) {
2541 *args = isl_calloc_array(ctx, struct pet_expr *, 1);
2542 if (!*args)
2543 return -1;
2544 } else {
2545 struct pet_expr **ext;
2546 ext = isl_calloc_array(ctx, struct pet_expr *, 1 + *n_arg);
2547 if (!ext)
2548 return -1;
2549 for (i = 0; i < *n_arg; ++i)
2550 ext[1 + i] = (*args)[i];
2551 free(*args);
2552 *args = ext;
2554 (*n_arg)++;
2555 (*args)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test));
2556 if (!(*args)[0])
2557 return -1;
2559 return 0;
2562 /* Make the expression "expr" depend on the value of "test"
2563 * being equal to "satisfied".
2565 * If "test" is an affine expression, we simply add the conditions
2566 * on the expression having the value "satisfied" to all access relations
2567 * and index expressions.
2569 * Otherwise, we add a filter to "expr" (which is then assumed to be
2570 * an access expression) corresponding to "test" being equal to "satisfied".
2572 struct pet_expr *pet_expr_filter(struct pet_expr *expr,
2573 __isl_take isl_multi_pw_aff *test, int satisfied)
2575 isl_id *id;
2576 isl_ctx *ctx;
2577 isl_space *space;
2578 isl_pw_multi_aff *pma;
2580 if (!expr || !test)
2581 goto error;
2583 if (!isl_multi_pw_aff_has_tuple_id(test, isl_dim_out)) {
2584 isl_pw_aff *pa;
2585 isl_set *cond;
2587 pa = isl_multi_pw_aff_get_pw_aff(test, 0);
2588 isl_multi_pw_aff_free(test);
2589 if (satisfied)
2590 cond = isl_pw_aff_non_zero_set(pa);
2591 else
2592 cond = isl_pw_aff_zero_set(pa);
2593 return pet_expr_restrict(expr, isl_set_params(cond));
2596 ctx = isl_multi_pw_aff_get_ctx(test);
2597 if (expr->type != pet_expr_access)
2598 isl_die(ctx, isl_error_invalid,
2599 "can only filter access expressions", goto error);
2601 space = isl_space_domain(isl_map_get_space(expr->acc.access));
2602 id = isl_multi_pw_aff_get_tuple_id(test, isl_dim_out);
2603 pma = insert_filter_pma(space, id, satisfied);
2605 expr->acc.access = isl_map_preimage_domain_pw_multi_aff(
2606 expr->acc.access,
2607 isl_pw_multi_aff_copy(pma));
2608 expr->acc.index = isl_multi_pw_aff_pullback_pw_multi_aff(
2609 expr->acc.index, pma);
2610 if (!expr->acc.access || !expr->acc.index)
2611 goto error;
2613 if (args_insert_access(&expr->n_arg, &expr->args, test) < 0)
2614 goto error;
2616 isl_multi_pw_aff_free(test);
2617 return expr;
2618 error:
2619 isl_multi_pw_aff_free(test);
2620 return pet_expr_free(expr);
2623 /* Look through the applications in "scop" for any that can be
2624 * applied to the filter expressed by "map" and "satisified".
2625 * If there is any, then apply it to "map" and return the result.
2626 * Otherwise, return "map".
2627 * "id" is the identifier of the virtual array.
2629 * We only introduce at most one implication for any given virtual array,
2630 * so we can apply the implication and return as soon as we find one.
2632 static __isl_give isl_map *apply_implications(struct pet_scop *scop,
2633 __isl_take isl_map *map, __isl_keep isl_id *id, int satisfied)
2635 int i;
2637 for (i = 0; i < scop->n_implication; ++i) {
2638 struct pet_implication *pi = scop->implications[i];
2639 isl_id *pi_id;
2641 if (pi->satisfied != satisfied)
2642 continue;
2643 pi_id = isl_map_get_tuple_id(pi->extension, isl_dim_in);
2644 isl_id_free(pi_id);
2645 if (pi_id != id)
2646 continue;
2648 return isl_map_apply_range(map, isl_map_copy(pi->extension));
2651 return map;
2654 /* Is the filter expressed by "test" and "satisfied" implied
2655 * by filter "pos" on "domain", with filter "expr", taking into
2656 * account the implications of "scop"?
2658 * For filter on domain implying that expressed by "test" and "satisfied",
2659 * the filter needs to be an access to the same (virtual) array as "test" and
2660 * the filter value needs to be equal to "satisfied".
2661 * Moreover, the filter access relation, possibly extended by
2662 * the implications in "scop" needs to contain "test".
2664 static int implies_filter(struct pet_scop *scop,
2665 __isl_keep isl_map *domain, int pos, struct pet_expr *expr,
2666 __isl_keep isl_map *test, int satisfied)
2668 isl_id *test_id, *arg_id;
2669 isl_val *val;
2670 int is_int;
2671 int s;
2672 int is_subset;
2673 isl_map *implied;
2675 if (expr->type != pet_expr_access)
2676 return 0;
2677 test_id = isl_map_get_tuple_id(test, isl_dim_out);
2678 arg_id = pet_expr_access_get_id(expr);
2679 isl_id_free(arg_id);
2680 isl_id_free(test_id);
2681 if (test_id != arg_id)
2682 return 0;
2683 val = isl_map_plain_get_val_if_fixed(domain, isl_dim_out, pos);
2684 is_int = isl_val_is_int(val);
2685 if (is_int)
2686 s = isl_val_get_num_si(val);
2687 isl_val_free(val);
2688 if (!val)
2689 return -1;
2690 if (!is_int)
2691 return 0;
2692 if (s != satisfied)
2693 return 0;
2695 implied = isl_map_copy(expr->acc.access);
2696 implied = apply_implications(scop, implied, test_id, satisfied);
2697 is_subset = isl_map_is_subset(test, implied);
2698 isl_map_free(implied);
2700 return is_subset;
2703 /* Is the filter expressed by "test" and "satisfied" implied
2704 * by any of the filters on the domain of "stmt", taking into
2705 * account the implications of "scop"?
2707 static int filter_implied(struct pet_scop *scop,
2708 struct pet_stmt *stmt, __isl_keep isl_multi_pw_aff *test, int satisfied)
2710 int i;
2711 int implied;
2712 isl_id *test_id;
2713 isl_map *domain;
2714 isl_map *test_map;
2716 if (!scop || !stmt || !test)
2717 return -1;
2718 if (scop->n_implication == 0)
2719 return 0;
2720 if (stmt->n_arg == 0)
2721 return 0;
2723 domain = isl_set_unwrap(isl_set_copy(stmt->domain));
2724 test_map = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test));
2726 implied = 0;
2727 for (i = 0; i < stmt->n_arg; ++i) {
2728 implied = implies_filter(scop, domain, i, stmt->args[i],
2729 test_map, satisfied);
2730 if (implied < 0 || implied)
2731 break;
2734 isl_map_free(test_map);
2735 isl_map_free(domain);
2736 return implied;
2739 /* Make the statement "stmt" depend on the value of "test"
2740 * being equal to "satisfied" by adjusting stmt->domain.
2742 * The domain of "test" corresponds to the (zero or more) outer dimensions
2743 * of the iteration domain.
2745 * We first extend "test" to apply to the entire iteration domain and
2746 * then check if the filter that we are about to add is implied
2747 * by any of the current filters, possibly taking into account
2748 * the implications in "scop". If so, we leave "stmt" untouched and return.
2750 * Otherwise, we insert an argument corresponding to a read to "test"
2751 * from the iteration domain of "stmt" in front of the list of arguments.
2752 * We also insert a corresponding output dimension in the wrapped
2753 * map contained in stmt->domain, with value set to "satisfied".
2755 static struct pet_stmt *stmt_filter(struct pet_scop *scop,
2756 struct pet_stmt *stmt, __isl_take isl_multi_pw_aff *test, int satisfied)
2758 int i;
2759 int implied;
2760 isl_id *id;
2761 isl_ctx *ctx;
2762 isl_pw_multi_aff *pma;
2763 isl_multi_aff *add_dom;
2764 isl_space *space;
2765 isl_local_space *ls;
2766 int n_test_dom;
2768 if (!stmt || !test)
2769 goto error;
2771 space = isl_set_get_space(stmt->domain);
2772 if (isl_space_is_wrapping(space))
2773 space = isl_space_domain(isl_space_unwrap(space));
2774 n_test_dom = isl_multi_pw_aff_dim(test, isl_dim_in);
2775 space = isl_space_from_domain(space);
2776 space = isl_space_add_dims(space, isl_dim_out, n_test_dom);
2777 add_dom = isl_multi_aff_zero(isl_space_copy(space));
2778 ls = isl_local_space_from_space(isl_space_domain(space));
2779 for (i = 0; i < n_test_dom; ++i) {
2780 isl_aff *aff;
2781 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
2782 isl_dim_set, i);
2783 add_dom = isl_multi_aff_set_aff(add_dom, i, aff);
2785 isl_local_space_free(ls);
2786 test = isl_multi_pw_aff_pullback_multi_aff(test, add_dom);
2788 implied = filter_implied(scop, stmt, test, satisfied);
2789 if (implied < 0)
2790 goto error;
2791 if (implied) {
2792 isl_multi_pw_aff_free(test);
2793 return stmt;
2796 id = isl_multi_pw_aff_get_tuple_id(test, isl_dim_out);
2797 pma = insert_filter_pma(isl_set_get_space(stmt->domain), id, satisfied);
2798 stmt->domain = isl_set_preimage_pw_multi_aff(stmt->domain, pma);
2800 if (args_insert_access(&stmt->n_arg, &stmt->args, test) < 0)
2801 goto error;
2803 isl_multi_pw_aff_free(test);
2804 return stmt;
2805 error:
2806 isl_multi_pw_aff_free(test);
2807 return pet_stmt_free(stmt);
2810 /* Does "scop" have a skip condition of the given "type"?
2812 int pet_scop_has_skip(struct pet_scop *scop, enum pet_skip type)
2814 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2816 if (!scop)
2817 return -1;
2818 return ext->skip[type] != NULL;
2821 /* Does "scop" have a skip condition of the given "type" that
2822 * is an affine expression?
2824 int pet_scop_has_affine_skip(struct pet_scop *scop, enum pet_skip type)
2826 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2828 if (!scop)
2829 return -1;
2830 if (!ext->skip[type])
2831 return 0;
2832 return multi_pw_aff_is_affine(ext->skip[type]);
2835 /* Does "scop" have a skip condition of the given "type" that
2836 * is not an affine expression?
2838 int pet_scop_has_var_skip(struct pet_scop *scop, enum pet_skip type)
2840 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2841 int aff;
2843 if (!scop)
2844 return -1;
2845 if (!ext->skip[type])
2846 return 0;
2847 aff = multi_pw_aff_is_affine(ext->skip[type]);
2848 if (aff < 0)
2849 return -1;
2850 return !aff;
2853 /* Does "scop" have a skip condition of the given "type" that
2854 * is affine and holds on the entire domain?
2856 int pet_scop_has_universal_skip(struct pet_scop *scop, enum pet_skip type)
2858 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2859 isl_pw_aff *pa;
2860 isl_set *set;
2861 int is_aff;
2862 int is_univ;
2864 is_aff = pet_scop_has_affine_skip(scop, type);
2865 if (is_aff < 0 || !is_aff)
2866 return is_aff;
2868 pa = isl_multi_pw_aff_get_pw_aff(ext->skip[type], 0);
2869 set = isl_pw_aff_non_zero_set(pa);
2870 is_univ = isl_set_plain_is_universe(set);
2871 isl_set_free(set);
2873 return is_univ;
2876 /* Replace scop->skip[type] by "skip".
2878 struct pet_scop *pet_scop_set_skip(struct pet_scop *scop,
2879 enum pet_skip type, __isl_take isl_multi_pw_aff *skip)
2881 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2883 if (!scop || !skip)
2884 goto error;
2886 isl_multi_pw_aff_free(ext->skip[type]);
2887 ext->skip[type] = skip;
2889 return scop;
2890 error:
2891 isl_multi_pw_aff_free(skip);
2892 return pet_scop_free(scop);
2895 /* Return a copy of scop->skip[type].
2897 __isl_give isl_multi_pw_aff *pet_scop_get_skip(struct pet_scop *scop,
2898 enum pet_skip type)
2900 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2902 if (!scop)
2903 return NULL;
2905 return isl_multi_pw_aff_copy(ext->skip[type]);
2908 /* Assuming scop->skip[type] is an affine expression,
2909 * return the constraints on the parameters for which the skip condition
2910 * holds.
2912 __isl_give isl_set *pet_scop_get_affine_skip_domain(struct pet_scop *scop,
2913 enum pet_skip type)
2915 isl_multi_pw_aff *skip;
2916 isl_pw_aff *pa;
2918 skip = pet_scop_get_skip(scop, type);
2919 pa = isl_multi_pw_aff_get_pw_aff(skip, 0);
2920 isl_multi_pw_aff_free(skip);
2921 return isl_set_params(isl_pw_aff_non_zero_set(pa));
2924 /* Return the identifier of the variable that is accessed by
2925 * the skip condition of the given type.
2927 * The skip condition is assumed not to be an affine condition.
2929 __isl_give isl_id *pet_scop_get_skip_id(struct pet_scop *scop,
2930 enum pet_skip type)
2932 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2934 if (!scop)
2935 return NULL;
2937 return isl_multi_pw_aff_get_tuple_id(ext->skip[type], isl_dim_out);
2940 /* Return an access pet_expr corresponding to the skip condition
2941 * of the given type.
2943 struct pet_expr *pet_scop_get_skip_expr(struct pet_scop *scop,
2944 enum pet_skip type)
2946 return pet_expr_from_index(pet_scop_get_skip(scop, type));
2949 /* Drop the the skip condition scop->skip[type].
2951 void pet_scop_reset_skip(struct pet_scop *scop, enum pet_skip type)
2953 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2955 if (!scop)
2956 return;
2958 isl_multi_pw_aff_free(ext->skip[type]);
2959 ext->skip[type] = NULL;
2962 /* Make the skip condition (if any) depend on the value of "test" being
2963 * equal to "satisfied".
2965 * We only support the case where the original skip condition is universal,
2966 * i.e., where skipping is unconditional, and where satisfied == 1.
2967 * In this case, the skip condition is changed to skip only when
2968 * "test" is equal to one.
2970 static struct pet_scop *pet_scop_filter_skip(struct pet_scop *scop,
2971 enum pet_skip type, __isl_keep isl_multi_pw_aff *test, int satisfied)
2973 int is_univ = 0;
2975 if (!scop)
2976 return NULL;
2977 if (!pet_scop_has_skip(scop, type))
2978 return scop;
2980 if (satisfied)
2981 is_univ = pet_scop_has_universal_skip(scop, type);
2982 if (is_univ < 0)
2983 return pet_scop_free(scop);
2984 if (satisfied && is_univ) {
2985 isl_multi_pw_aff *skip;
2986 skip = isl_multi_pw_aff_copy(test);
2987 scop = pet_scop_set_skip(scop, type, skip);
2988 if (!scop)
2989 return NULL;
2990 } else {
2991 isl_die(isl_multi_pw_aff_get_ctx(test), isl_error_internal,
2992 "skip expression cannot be filtered",
2993 return pet_scop_free(scop));
2996 return scop;
2999 /* Make all statements in "scop" depend on the value of "test"
3000 * being equal to "satisfied" by adjusting their domains.
3002 struct pet_scop *pet_scop_filter(struct pet_scop *scop,
3003 __isl_take isl_multi_pw_aff *test, int satisfied)
3005 int i;
3007 scop = pet_scop_filter_skip(scop, pet_skip_now, test, satisfied);
3008 scop = pet_scop_filter_skip(scop, pet_skip_later, test, satisfied);
3010 if (!scop || !test)
3011 goto error;
3013 for (i = 0; i < scop->n_stmt; ++i) {
3014 scop->stmts[i] = stmt_filter(scop, scop->stmts[i],
3015 isl_multi_pw_aff_copy(test), satisfied);
3016 if (!scop->stmts[i])
3017 goto error;
3020 isl_multi_pw_aff_free(test);
3021 return scop;
3022 error:
3023 isl_multi_pw_aff_free(test);
3024 return pet_scop_free(scop);
3027 /* Add all parameters in "expr" to "space" and return the result.
3029 static __isl_give isl_space *expr_collect_params(struct pet_expr *expr,
3030 __isl_take isl_space *space)
3032 int i;
3034 if (!expr)
3035 goto error;
3036 for (i = 0; i < expr->n_arg; ++i)
3037 space = expr_collect_params(expr->args[i], space);
3039 if (expr->type == pet_expr_access)
3040 space = isl_space_align_params(space,
3041 isl_map_get_space(expr->acc.access));
3043 return space;
3044 error:
3045 pet_expr_free(expr);
3046 return isl_space_free(space);
3049 /* Add all parameters in "stmt" to "space" and return the result.
3051 static __isl_give isl_space *stmt_collect_params(struct pet_stmt *stmt,
3052 __isl_take isl_space *space)
3054 int i;
3056 if (!stmt)
3057 return isl_space_free(space);
3059 space = isl_space_align_params(space, isl_set_get_space(stmt->domain));
3060 space = isl_space_align_params(space,
3061 isl_map_get_space(stmt->schedule));
3062 for (i = 0; i < stmt->n_arg; ++i)
3063 space = expr_collect_params(stmt->args[i], space);
3064 space = expr_collect_params(stmt->body, space);
3066 return space;
3069 /* Add all parameters in "array" to "space" and return the result.
3071 static __isl_give isl_space *array_collect_params(struct pet_array *array,
3072 __isl_take isl_space *space)
3074 if (!array)
3075 return isl_space_free(space);
3077 space = isl_space_align_params(space,
3078 isl_set_get_space(array->context));
3079 space = isl_space_align_params(space, isl_set_get_space(array->extent));
3081 return space;
3084 /* Add all parameters in "scop" to "space" and return the result.
3086 static __isl_give isl_space *scop_collect_params(struct pet_scop *scop,
3087 __isl_take isl_space *space)
3089 int i;
3091 if (!scop)
3092 return isl_space_free(space);
3094 for (i = 0; i < scop->n_array; ++i)
3095 space = array_collect_params(scop->arrays[i], space);
3097 for (i = 0; i < scop->n_stmt; ++i)
3098 space = stmt_collect_params(scop->stmts[i], space);
3100 return space;
3103 /* Add all parameters in "space" to all access relations and index expressions
3104 * in "expr".
3106 static struct pet_expr *expr_propagate_params(struct pet_expr *expr,
3107 __isl_take isl_space *space)
3109 int i;
3111 if (!expr)
3112 goto error;
3114 for (i = 0; i < expr->n_arg; ++i) {
3115 expr->args[i] =
3116 expr_propagate_params(expr->args[i],
3117 isl_space_copy(space));
3118 if (!expr->args[i])
3119 goto error;
3122 if (expr->type == pet_expr_access) {
3123 expr->acc.access = isl_map_align_params(expr->acc.access,
3124 isl_space_copy(space));
3125 expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
3126 isl_space_copy(space));
3127 if (!expr->acc.access || !expr->acc.index)
3128 goto error;
3131 isl_space_free(space);
3132 return expr;
3133 error:
3134 isl_space_free(space);
3135 return pet_expr_free(expr);
3138 /* Add all parameters in "space" to the domain, schedule and
3139 * all access relations in "stmt".
3141 static struct pet_stmt *stmt_propagate_params(struct pet_stmt *stmt,
3142 __isl_take isl_space *space)
3144 int i;
3146 if (!stmt)
3147 goto error;
3149 stmt->domain = isl_set_align_params(stmt->domain,
3150 isl_space_copy(space));
3151 stmt->schedule = isl_map_align_params(stmt->schedule,
3152 isl_space_copy(space));
3154 for (i = 0; i < stmt->n_arg; ++i) {
3155 stmt->args[i] = expr_propagate_params(stmt->args[i],
3156 isl_space_copy(space));
3157 if (!stmt->args[i])
3158 goto error;
3160 stmt->body = expr_propagate_params(stmt->body, isl_space_copy(space));
3162 if (!stmt->domain || !stmt->schedule || !stmt->body)
3163 goto error;
3165 isl_space_free(space);
3166 return stmt;
3167 error:
3168 isl_space_free(space);
3169 return pet_stmt_free(stmt);
3172 /* Add all parameters in "space" to "array".
3174 static struct pet_array *array_propagate_params(struct pet_array *array,
3175 __isl_take isl_space *space)
3177 if (!array)
3178 goto error;
3180 array->context = isl_set_align_params(array->context,
3181 isl_space_copy(space));
3182 array->extent = isl_set_align_params(array->extent,
3183 isl_space_copy(space));
3184 if (array->value_bounds) {
3185 array->value_bounds = isl_set_align_params(array->value_bounds,
3186 isl_space_copy(space));
3187 if (!array->value_bounds)
3188 goto error;
3191 if (!array->context || !array->extent)
3192 goto error;
3194 isl_space_free(space);
3195 return array;
3196 error:
3197 isl_space_free(space);
3198 return pet_array_free(array);
3201 /* Add all parameters in "space" to "scop".
3203 static struct pet_scop *scop_propagate_params(struct pet_scop *scop,
3204 __isl_take isl_space *space)
3206 int i;
3208 if (!scop)
3209 goto error;
3211 for (i = 0; i < scop->n_array; ++i) {
3212 scop->arrays[i] = array_propagate_params(scop->arrays[i],
3213 isl_space_copy(space));
3214 if (!scop->arrays[i])
3215 goto error;
3218 for (i = 0; i < scop->n_stmt; ++i) {
3219 scop->stmts[i] = stmt_propagate_params(scop->stmts[i],
3220 isl_space_copy(space));
3221 if (!scop->stmts[i])
3222 goto error;
3225 isl_space_free(space);
3226 return scop;
3227 error:
3228 isl_space_free(space);
3229 return pet_scop_free(scop);
3232 /* Update all isl_sets and isl_maps in "scop" such that they all
3233 * have the same parameters.
3235 struct pet_scop *pet_scop_align_params(struct pet_scop *scop)
3237 isl_space *space;
3239 if (!scop)
3240 return NULL;
3242 space = isl_set_get_space(scop->context);
3243 space = scop_collect_params(scop, space);
3245 scop->context = isl_set_align_params(scop->context,
3246 isl_space_copy(space));
3247 scop = scop_propagate_params(scop, space);
3249 if (scop && !scop->context)
3250 return pet_scop_free(scop);
3252 return scop;
3255 /* Check if the given index expression accesses a (0D) array that corresponds
3256 * to one of the parameters in "dim". If so, replace the array access
3257 * by an access to the set of integers with as index (and value)
3258 * that parameter.
3260 static __isl_give isl_multi_pw_aff *index_detect_parameter(
3261 __isl_take isl_multi_pw_aff *index, __isl_take isl_space *space)
3263 isl_local_space *ls;
3264 isl_id *array_id = NULL;
3265 isl_aff *aff;
3266 int pos = -1;
3268 if (isl_multi_pw_aff_has_tuple_id(index, isl_dim_out)) {
3269 array_id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
3270 pos = isl_space_find_dim_by_id(space, isl_dim_param, array_id);
3272 isl_space_free(space);
3274 if (pos < 0) {
3275 isl_id_free(array_id);
3276 return index;
3279 space = isl_multi_pw_aff_get_domain_space(index);
3280 isl_multi_pw_aff_free(index);
3282 pos = isl_space_find_dim_by_id(space, isl_dim_param, array_id);
3283 if (pos < 0) {
3284 space = isl_space_insert_dims(space, isl_dim_param, 0, 1);
3285 space = isl_space_set_dim_id(space, isl_dim_param, 0, array_id);
3286 pos = 0;
3287 } else
3288 isl_id_free(array_id);
3290 ls = isl_local_space_from_space(space);
3291 aff = isl_aff_var_on_domain(ls, isl_dim_param, pos);
3292 index = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
3294 return index;
3297 /* Check if the given access relation accesses a (0D) array that corresponds
3298 * to one of the parameters in "dim". If so, replace the array access
3299 * by an access to the set of integers with as index (and value)
3300 * that parameter.
3302 static __isl_give isl_map *access_detect_parameter(__isl_take isl_map *access,
3303 __isl_take isl_space *dim)
3305 isl_id *array_id = NULL;
3306 int pos = -1;
3308 if (isl_map_has_tuple_id(access, isl_dim_out)) {
3309 array_id = isl_map_get_tuple_id(access, isl_dim_out);
3310 pos = isl_space_find_dim_by_id(dim, isl_dim_param, array_id);
3312 isl_space_free(dim);
3314 if (pos < 0) {
3315 isl_id_free(array_id);
3316 return access;
3319 pos = isl_map_find_dim_by_id(access, isl_dim_param, array_id);
3320 if (pos < 0) {
3321 access = isl_map_insert_dims(access, isl_dim_param, 0, 1);
3322 access = isl_map_set_dim_id(access, isl_dim_param, 0, array_id);
3323 pos = 0;
3324 } else
3325 isl_id_free(array_id);
3327 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
3328 access = isl_map_equate(access, isl_dim_param, pos, isl_dim_out, 0);
3330 return access;
3333 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3334 * in "dim" by a value equal to the corresponding parameter.
3336 static struct pet_expr *expr_detect_parameter_accesses(struct pet_expr *expr,
3337 __isl_take isl_space *dim)
3339 int i;
3341 if (!expr)
3342 goto error;
3344 for (i = 0; i < expr->n_arg; ++i) {
3345 expr->args[i] =
3346 expr_detect_parameter_accesses(expr->args[i],
3347 isl_space_copy(dim));
3348 if (!expr->args[i])
3349 goto error;
3352 if (expr->type == pet_expr_access) {
3353 expr->acc.access = access_detect_parameter(expr->acc.access,
3354 isl_space_copy(dim));
3355 expr->acc.index = index_detect_parameter(expr->acc.index,
3356 isl_space_copy(dim));
3357 if (!expr->acc.access || !expr->acc.index)
3358 goto error;
3361 isl_space_free(dim);
3362 return expr;
3363 error:
3364 isl_space_free(dim);
3365 return pet_expr_free(expr);
3368 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3369 * in "dim" by a value equal to the corresponding parameter.
3371 static struct pet_stmt *stmt_detect_parameter_accesses(struct pet_stmt *stmt,
3372 __isl_take isl_space *dim)
3374 if (!stmt)
3375 goto error;
3377 stmt->body = expr_detect_parameter_accesses(stmt->body,
3378 isl_space_copy(dim));
3380 if (!stmt->domain || !stmt->schedule || !stmt->body)
3381 goto error;
3383 isl_space_free(dim);
3384 return stmt;
3385 error:
3386 isl_space_free(dim);
3387 return pet_stmt_free(stmt);
3390 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3391 * in "dim" by a value equal to the corresponding parameter.
3393 static struct pet_scop *scop_detect_parameter_accesses(struct pet_scop *scop,
3394 __isl_take isl_space *dim)
3396 int i;
3398 if (!scop)
3399 goto error;
3401 for (i = 0; i < scop->n_stmt; ++i) {
3402 scop->stmts[i] = stmt_detect_parameter_accesses(scop->stmts[i],
3403 isl_space_copy(dim));
3404 if (!scop->stmts[i])
3405 goto error;
3408 isl_space_free(dim);
3409 return scop;
3410 error:
3411 isl_space_free(dim);
3412 return pet_scop_free(scop);
3415 /* Replace all accesses to (0D) arrays that correspond to any of
3416 * the parameters used in "scop" by a value equal
3417 * to the corresponding parameter.
3419 struct pet_scop *pet_scop_detect_parameter_accesses(struct pet_scop *scop)
3421 isl_space *dim;
3423 if (!scop)
3424 return NULL;
3426 dim = isl_set_get_space(scop->context);
3427 dim = scop_collect_params(scop, dim);
3429 scop = scop_detect_parameter_accesses(scop, dim);
3431 return scop;
3434 /* Return the relation mapping domain iterations to all possibly
3435 * accessed data elements.
3436 * In particular, take the access relation and project out the values
3437 * of the arguments, if any.
3439 __isl_give isl_map *pet_expr_access_get_may_access(struct pet_expr *expr)
3441 isl_map *access;
3442 isl_space *space;
3443 isl_map *map;
3445 if (!expr)
3446 return NULL;
3447 if (expr->type != pet_expr_access)
3448 return NULL;
3450 access = isl_map_copy(expr->acc.access);
3451 if (expr->n_arg == 0)
3452 return access;
3454 space = isl_space_domain(isl_map_get_space(access));
3455 map = isl_map_universe(isl_space_unwrap(space));
3456 map = isl_map_domain_map(map);
3457 access = isl_map_apply_domain(access, map);
3459 return access;
3462 /* Return the relation mapping domain iterations to all possibly
3463 * accessed data elements, with its domain tagged with the reference
3464 * identifier.
3466 __isl_give isl_map *pet_expr_access_get_tagged_may_access(
3467 struct pet_expr *expr)
3469 isl_map *access;
3471 if (!expr)
3472 return NULL;
3474 access = pet_expr_access_get_may_access(expr);
3475 access = tag_access(access, isl_id_copy(expr->acc.ref_id));
3477 return access;
3480 /* Add the access relation of the access expression "expr" to "accesses" and
3481 * return the result.
3482 * The domain of the access relation is intersected with "domain".
3483 * If "tag" is set, then the access relation is tagged with
3484 * the corresponding reference identifier.
3486 static __isl_give isl_union_map *expr_collect_access(struct pet_expr *expr,
3487 int tag, __isl_take isl_union_map *accesses, __isl_keep isl_set *domain)
3489 isl_map *access;
3491 access = pet_expr_access_get_may_access(expr);
3492 access = isl_map_intersect_domain(access, isl_set_copy(domain));
3493 if (tag)
3494 access = tag_access(access, isl_id_copy(expr->acc.ref_id));
3495 return isl_union_map_add_map(accesses, access);
3498 /* Add all read access relations (if "read" is set) and/or all write
3499 * access relations (if "write" is set) to "accesses" and return the result.
3500 * The domains of the access relations are intersected with "domain".
3501 * If "tag" is set, then the access relations are tagged with
3502 * the corresponding reference identifiers.
3504 * If "must" is set, then we only add the accesses that are definitely
3505 * performed. Otherwise, we add all potential accesses.
3506 * In particular, if the access has any arguments, then if "must" is
3507 * set we currently skip the access completely. If "must" is not set,
3508 * we project out the values of the access arguments.
3510 static __isl_give isl_union_map *expr_collect_accesses(struct pet_expr *expr,
3511 int read, int write, int must, int tag,
3512 __isl_take isl_union_map *accesses, __isl_keep isl_set *domain)
3514 int i;
3515 isl_id *id;
3516 isl_space *dim;
3518 if (!expr)
3519 return isl_union_map_free(accesses);
3521 for (i = 0; i < expr->n_arg; ++i)
3522 accesses = expr_collect_accesses(expr->args[i],
3523 read, write, must, tag, accesses, domain);
3525 if (expr->type == pet_expr_access && !pet_expr_is_affine(expr) &&
3526 ((read && expr->acc.read) || (write && expr->acc.write)) &&
3527 (!must || expr->n_arg == 0)) {
3528 accesses = expr_collect_access(expr, tag, accesses, domain);
3531 return accesses;
3534 /* Collect and return all read access relations (if "read" is set)
3535 * and/or all write access relations (if "write" is set) in "stmt".
3536 * If "tag" is set, then the access relations are tagged with
3537 * the corresponding reference identifiers.
3538 * If "kill" is set, then "stmt" is a kill statement and we simply
3539 * add the argument of the kill operation.
3541 * If "must" is set, then we only add the accesses that are definitely
3542 * performed. Otherwise, we add all potential accesses.
3543 * In particular, if the statement has any arguments, then if "must" is
3544 * set we currently skip the statement completely. If "must" is not set,
3545 * we project out the values of the statement arguments.
3547 static __isl_give isl_union_map *stmt_collect_accesses(struct pet_stmt *stmt,
3548 int read, int write, int kill, int must, int tag,
3549 __isl_take isl_space *dim)
3551 isl_union_map *accesses;
3552 isl_set *domain;
3554 if (!stmt)
3555 return NULL;
3557 accesses = isl_union_map_empty(dim);
3559 if (must && stmt->n_arg > 0)
3560 return accesses;
3562 domain = isl_set_copy(stmt->domain);
3563 if (isl_set_is_wrapping(domain))
3564 domain = isl_map_domain(isl_set_unwrap(domain));
3566 if (kill)
3567 accesses = expr_collect_access(stmt->body->args[0], tag,
3568 accesses, domain);
3569 else
3570 accesses = expr_collect_accesses(stmt->body, read, write,
3571 must, tag, accesses, domain);
3572 isl_set_free(domain);
3574 return accesses;
3577 /* Is "stmt" a kill statement?
3579 static int is_kill(struct pet_stmt *stmt)
3581 if (stmt->body->type != pet_expr_unary)
3582 return 0;
3583 return stmt->body->op == pet_op_kill;
3586 /* Is "stmt" an assume statement?
3588 int pet_stmt_is_assume(struct pet_stmt *stmt)
3590 if (stmt->body->type != pet_expr_unary)
3591 return 0;
3592 return stmt->body->op == pet_op_assume;
3595 /* Compute a mapping from all arrays (of structs) in scop
3596 * to their innermost arrays.
3598 * In particular, for each array of a primitive type, the result
3599 * contains the identity mapping on that array.
3600 * For each array involving member accesses, the result
3601 * contains a mapping from the elements of any intermediate array of structs
3602 * to all corresponding elements of the innermost nested arrays.
3604 static __isl_give isl_union_map *compute_to_inner(struct pet_scop *scop)
3606 int i;
3607 isl_union_map *to_inner;
3609 to_inner = isl_union_map_empty(isl_set_get_space(scop->context));
3611 for (i = 0; i < scop->n_array; ++i) {
3612 struct pet_array *array = scop->arrays[i];
3613 isl_set *set;
3614 isl_map *map, *gist;
3616 if (array->element_is_record)
3617 continue;
3619 map = isl_set_identity(isl_set_copy(array->extent));
3621 set = isl_map_domain(isl_map_copy(map));
3622 gist = isl_map_copy(map);
3623 gist = isl_map_gist_domain(gist, isl_set_copy(set));
3624 to_inner = isl_union_map_add_map(to_inner, gist);
3626 while (set && isl_set_is_wrapping(set)) {
3627 isl_id *id;
3628 isl_map *wrapped;
3630 id = isl_set_get_tuple_id(set);
3631 wrapped = isl_set_unwrap(set);
3632 wrapped = isl_map_domain_map(wrapped);
3633 wrapped = isl_map_set_tuple_id(wrapped, isl_dim_in, id);
3634 map = isl_map_apply_domain(map, wrapped);
3635 set = isl_map_domain(isl_map_copy(map));
3636 gist = isl_map_copy(map);
3637 gist = isl_map_gist_domain(gist, isl_set_copy(set));
3638 to_inner = isl_union_map_add_map(to_inner, gist);
3641 isl_set_free(set);
3642 isl_map_free(map);
3645 return to_inner;
3648 /* Collect and return all read access relations (if "read" is set)
3649 * and/or all write access relations (if "write" is set) in "scop".
3650 * If "kill" is set, then we only add the arguments of kill operations.
3651 * If "must" is set, then we only add the accesses that are definitely
3652 * performed. Otherwise, we add all potential accesses.
3653 * If "tag" is set, then the access relations are tagged with
3654 * the corresponding reference identifiers.
3655 * For accesses to structures, the returned access relation accesses
3656 * all individual fields in the structures.
3658 static __isl_give isl_union_map *scop_collect_accesses(struct pet_scop *scop,
3659 int read, int write, int kill, int must, int tag)
3661 int i;
3662 isl_union_map *accesses;
3663 isl_union_set *arrays;
3664 isl_union_map *to_inner;
3666 if (!scop)
3667 return NULL;
3669 accesses = isl_union_map_empty(isl_set_get_space(scop->context));
3671 for (i = 0; i < scop->n_stmt; ++i) {
3672 struct pet_stmt *stmt = scop->stmts[i];
3673 isl_union_map *accesses_i;
3674 isl_space *space;
3676 if (kill && !is_kill(stmt))
3677 continue;
3679 space = isl_set_get_space(scop->context);
3680 accesses_i = stmt_collect_accesses(stmt, read, write, kill,
3681 must, tag, space);
3682 accesses = isl_union_map_union(accesses, accesses_i);
3685 arrays = isl_union_set_empty(isl_union_map_get_space(accesses));
3686 for (i = 0; i < scop->n_array; ++i) {
3687 isl_set *extent = isl_set_copy(scop->arrays[i]->extent);
3688 arrays = isl_union_set_add_set(arrays, extent);
3690 accesses = isl_union_map_intersect_range(accesses, arrays);
3692 to_inner = compute_to_inner(scop);
3693 accesses = isl_union_map_apply_range(accesses, to_inner);
3695 return accesses;
3698 /* Collect all potential read access relations.
3700 __isl_give isl_union_map *pet_scop_collect_may_reads(struct pet_scop *scop)
3702 return scop_collect_accesses(scop, 1, 0, 0, 0, 0);
3705 /* Collect all potential write access relations.
3707 __isl_give isl_union_map *pet_scop_collect_may_writes(struct pet_scop *scop)
3709 return scop_collect_accesses(scop, 0, 1, 0, 0, 0);
3712 /* Collect all definite write access relations.
3714 __isl_give isl_union_map *pet_scop_collect_must_writes(struct pet_scop *scop)
3716 return scop_collect_accesses(scop, 0, 1, 0, 1, 0);
3719 /* Collect all definite kill access relations.
3721 __isl_give isl_union_map *pet_scop_collect_must_kills(struct pet_scop *scop)
3723 return scop_collect_accesses(scop, 0, 0, 1, 1, 0);
3726 /* Collect all tagged potential read access relations.
3728 __isl_give isl_union_map *pet_scop_collect_tagged_may_reads(
3729 struct pet_scop *scop)
3731 return scop_collect_accesses(scop, 1, 0, 0, 0, 1);
3734 /* Collect all tagged potential write access relations.
3736 __isl_give isl_union_map *pet_scop_collect_tagged_may_writes(
3737 struct pet_scop *scop)
3739 return scop_collect_accesses(scop, 0, 1, 0, 0, 1);
3742 /* Collect all tagged definite write access relations.
3744 __isl_give isl_union_map *pet_scop_collect_tagged_must_writes(
3745 struct pet_scop *scop)
3747 return scop_collect_accesses(scop, 0, 1, 0, 1, 1);
3750 /* Collect all tagged definite kill access relations.
3752 __isl_give isl_union_map *pet_scop_collect_tagged_must_kills(
3753 struct pet_scop *scop)
3755 return scop_collect_accesses(scop, 0, 0, 1, 1, 1);
3758 /* Collect and return the union of iteration domains in "scop".
3760 __isl_give isl_union_set *pet_scop_collect_domains(struct pet_scop *scop)
3762 int i;
3763 isl_set *domain_i;
3764 isl_union_set *domain;
3766 if (!scop)
3767 return NULL;
3769 domain = isl_union_set_empty(isl_set_get_space(scop->context));
3771 for (i = 0; i < scop->n_stmt; ++i) {
3772 domain_i = isl_set_copy(scop->stmts[i]->domain);
3773 domain = isl_union_set_add_set(domain, domain_i);
3776 return domain;
3779 /* Collect and return the schedules of the statements in "scop".
3780 * The range is normalized to the maximal number of scheduling
3781 * dimensions.
3783 __isl_give isl_union_map *pet_scop_collect_schedule(struct pet_scop *scop)
3785 int i, j;
3786 isl_map *schedule_i;
3787 isl_union_map *schedule;
3788 int depth, max_depth = 0;
3790 if (!scop)
3791 return NULL;
3793 schedule = isl_union_map_empty(isl_set_get_space(scop->context));
3795 for (i = 0; i < scop->n_stmt; ++i) {
3796 depth = isl_map_dim(scop->stmts[i]->schedule, isl_dim_out);
3797 if (depth > max_depth)
3798 max_depth = depth;
3801 for (i = 0; i < scop->n_stmt; ++i) {
3802 schedule_i = isl_map_copy(scop->stmts[i]->schedule);
3803 depth = isl_map_dim(schedule_i, isl_dim_out);
3804 schedule_i = isl_map_add_dims(schedule_i, isl_dim_out,
3805 max_depth - depth);
3806 for (j = depth; j < max_depth; ++j)
3807 schedule_i = isl_map_fix_si(schedule_i,
3808 isl_dim_out, j, 0);
3809 schedule = isl_union_map_add_map(schedule, schedule_i);
3812 return schedule;
3815 /* Does expression "expr" write to "id"?
3817 static int expr_writes(struct pet_expr *expr, __isl_keep isl_id *id)
3819 int i;
3820 isl_id *write_id;
3822 for (i = 0; i < expr->n_arg; ++i) {
3823 int writes = expr_writes(expr->args[i], id);
3824 if (writes < 0 || writes)
3825 return writes;
3828 if (expr->type != pet_expr_access)
3829 return 0;
3830 if (!expr->acc.write)
3831 return 0;
3832 if (pet_expr_is_affine(expr))
3833 return 0;
3835 write_id = pet_expr_access_get_id(expr);
3836 isl_id_free(write_id);
3838 if (!write_id)
3839 return -1;
3841 return write_id == id;
3844 /* Does statement "stmt" write to "id"?
3846 static int stmt_writes(struct pet_stmt *stmt, __isl_keep isl_id *id)
3848 return expr_writes(stmt->body, id);
3851 /* Is there any write access in "scop" that accesses "id"?
3853 int pet_scop_writes(struct pet_scop *scop, __isl_keep isl_id *id)
3855 int i;
3857 if (!scop)
3858 return -1;
3860 for (i = 0; i < scop->n_stmt; ++i) {
3861 int writes = stmt_writes(scop->stmts[i], id);
3862 if (writes < 0 || writes)
3863 return writes;
3866 return 0;
3869 /* Add a reference identifier to access expression "expr".
3870 * "user" points to an integer that contains the sequence number
3871 * of the next reference.
3873 static struct pet_expr *access_add_ref_id(struct pet_expr *expr, void *user)
3875 isl_ctx *ctx;
3876 char name[50];
3877 int *n_ref = user;
3879 if (!expr)
3880 return expr;
3882 ctx = isl_map_get_ctx(expr->acc.access);
3883 snprintf(name, sizeof(name), "__pet_ref_%d", (*n_ref)++);
3884 expr->acc.ref_id = isl_id_alloc(ctx, name, NULL);
3885 if (!expr->acc.ref_id)
3886 return pet_expr_free(expr);
3888 return expr;
3891 /* Add a reference identifier to all access expressions in "stmt".
3892 * "n_ref" points to an integer that contains the sequence number
3893 * of the next reference.
3895 static struct pet_stmt *stmt_add_ref_ids(struct pet_stmt *stmt, int *n_ref)
3897 int i;
3899 if (!stmt)
3900 return NULL;
3902 for (i = 0; i < stmt->n_arg; ++i) {
3903 stmt->args[i] = pet_expr_map_access(stmt->args[i],
3904 &access_add_ref_id, n_ref);
3905 if (!stmt->args[i])
3906 return pet_stmt_free(stmt);
3909 stmt->body = pet_expr_map_access(stmt->body, &access_add_ref_id, n_ref);
3910 if (!stmt->body)
3911 return pet_stmt_free(stmt);
3913 return stmt;
3916 /* Add a reference identifier to all access expressions in "scop".
3918 struct pet_scop *pet_scop_add_ref_ids(struct pet_scop *scop)
3920 int i;
3921 int n_ref;
3923 if (!scop)
3924 return NULL;
3926 n_ref = 0;
3927 for (i = 0; i < scop->n_stmt; ++i) {
3928 scop->stmts[i] = stmt_add_ref_ids(scop->stmts[i], &n_ref);
3929 if (!scop->stmts[i])
3930 return pet_scop_free(scop);
3933 return scop;
3936 /* Reset the user pointer on all parameter ids in "array".
3938 static struct pet_array *array_anonymize(struct pet_array *array)
3940 if (!array)
3941 return NULL;
3943 array->context = isl_set_reset_user(array->context);
3944 array->extent = isl_set_reset_user(array->extent);
3945 if (!array->context || !array->extent)
3946 return pet_array_free(array);
3948 return array;
3951 /* Reset the user pointer on all parameter and tuple ids in
3952 * the access relation and the index expressions
3953 * of the access expression "expr".
3955 static struct pet_expr *access_anonymize(struct pet_expr *expr, void *user)
3957 expr->acc.access = isl_map_reset_user(expr->acc.access);
3958 expr->acc.index = isl_multi_pw_aff_reset_user(expr->acc.index);
3959 if (!expr->acc.access || !expr->acc.index)
3960 return pet_expr_free(expr);
3962 return expr;
3965 /* Reset the user pointer on all parameter and tuple ids in "stmt".
3967 static struct pet_stmt *stmt_anonymize(struct pet_stmt *stmt)
3969 int i;
3970 isl_space *space;
3971 isl_set *domain;
3973 if (!stmt)
3974 return NULL;
3976 stmt->domain = isl_set_reset_user(stmt->domain);
3977 stmt->schedule = isl_map_reset_user(stmt->schedule);
3978 if (!stmt->domain || !stmt->schedule)
3979 return pet_stmt_free(stmt);
3981 for (i = 0; i < stmt->n_arg; ++i) {
3982 stmt->args[i] = pet_expr_map_access(stmt->args[i],
3983 &access_anonymize, NULL);
3984 if (!stmt->args[i])
3985 return pet_stmt_free(stmt);
3988 stmt->body = pet_expr_map_access(stmt->body,
3989 &access_anonymize, NULL);
3990 if (!stmt->body)
3991 return pet_stmt_free(stmt);
3993 return stmt;
3996 /* Reset the user pointer on the tuple ids and all parameter ids
3997 * in "implication".
3999 static struct pet_implication *implication_anonymize(
4000 struct pet_implication *implication)
4002 if (!implication)
4003 return NULL;
4005 implication->extension = isl_map_reset_user(implication->extension);
4006 if (!implication->extension)
4007 return pet_implication_free(implication);
4009 return implication;
4012 /* Reset the user pointer on all parameter and tuple ids in "scop".
4014 struct pet_scop *pet_scop_anonymize(struct pet_scop *scop)
4016 int i;
4018 if (!scop)
4019 return NULL;
4021 scop->context = isl_set_reset_user(scop->context);
4022 scop->context_value = isl_set_reset_user(scop->context_value);
4023 if (!scop->context || !scop->context_value)
4024 return pet_scop_free(scop);
4026 for (i = 0; i < scop->n_array; ++i) {
4027 scop->arrays[i] = array_anonymize(scop->arrays[i]);
4028 if (!scop->arrays[i])
4029 return pet_scop_free(scop);
4032 for (i = 0; i < scop->n_stmt; ++i) {
4033 scop->stmts[i] = stmt_anonymize(scop->stmts[i]);
4034 if (!scop->stmts[i])
4035 return pet_scop_free(scop);
4038 for (i = 0; i < scop->n_implication; ++i) {
4039 scop->implications[i] =
4040 implication_anonymize(scop->implications[i]);
4041 if (!scop->implications[i])
4042 return pet_scop_free(scop);
4045 return scop;
4048 /* If "value_bounds" contains any bounds on the variable accessed by "arg",
4049 * then intersect the range of "map" with the valid set of values.
4051 static __isl_give isl_map *access_apply_value_bounds(__isl_take isl_map *map,
4052 struct pet_expr *arg, __isl_keep isl_union_map *value_bounds)
4054 isl_id *id;
4055 isl_map *vb;
4056 isl_space *space;
4057 isl_ctx *ctx = isl_map_get_ctx(map);
4059 id = pet_expr_access_get_id(arg);
4060 space = isl_space_alloc(ctx, 0, 0, 1);
4061 space = isl_space_set_tuple_id(space, isl_dim_in, id);
4062 vb = isl_union_map_extract_map(value_bounds, space);
4063 if (!isl_map_plain_is_empty(vb))
4064 map = isl_map_intersect_range(map, isl_map_range(vb));
4065 else
4066 isl_map_free(vb);
4068 return map;
4071 /* Given a set "domain", return a wrapped relation with the given set
4072 * as domain and a range of dimension "n_arg", where each coordinate
4073 * is either unbounded or, if the corresponding element of args is of
4074 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
4076 static __isl_give isl_set *apply_value_bounds(__isl_take isl_set *domain,
4077 unsigned n_arg, struct pet_expr **args,
4078 __isl_keep isl_union_map *value_bounds)
4080 int i;
4081 isl_map *map;
4082 isl_space *space;
4084 map = isl_map_from_domain(domain);
4085 space = isl_map_get_space(map);
4086 space = isl_space_add_dims(space, isl_dim_out, 1);
4088 for (i = 0; i < n_arg; ++i) {
4089 isl_map *map_i;
4090 struct pet_expr *arg = args[i];
4092 map_i = isl_map_universe(isl_space_copy(space));
4093 if (arg->type == pet_expr_access)
4094 map_i = access_apply_value_bounds(map_i, arg,
4095 value_bounds);
4096 map = isl_map_flat_range_product(map, map_i);
4098 isl_space_free(space);
4100 return isl_map_wrap(map);
4103 /* Data used in access_gist() callback.
4105 struct pet_access_gist_data {
4106 isl_set *domain;
4107 isl_union_map *value_bounds;
4110 /* Given an expression "expr" of type pet_expr_access, compute
4111 * the gist of the associated access relation and index expression
4112 * with respect to data->domain and the bounds on the values of the arguments
4113 * of the expression.
4115 static struct pet_expr *access_gist(struct pet_expr *expr, void *user)
4117 struct pet_access_gist_data *data = user;
4118 isl_set *domain;
4120 domain = isl_set_copy(data->domain);
4121 if (expr->n_arg > 0)
4122 domain = apply_value_bounds(domain, expr->n_arg, expr->args,
4123 data->value_bounds);
4125 expr->acc.access = isl_map_gist_domain(expr->acc.access,
4126 isl_set_copy(domain));
4127 expr->acc.index = isl_multi_pw_aff_gist(expr->acc.index, domain);
4128 if (!expr->acc.access || !expr->acc.index)
4129 return pet_expr_free(expr);
4131 return expr;
4134 /* Compute the gist of the iteration domain and all access relations
4135 * of "stmt" based on the constraints on the parameters specified by "context"
4136 * and the constraints on the values of nested accesses specified
4137 * by "value_bounds".
4139 static struct pet_stmt *stmt_gist(struct pet_stmt *stmt,
4140 __isl_keep isl_set *context, __isl_keep isl_union_map *value_bounds)
4142 int i;
4143 isl_space *space;
4144 isl_set *domain;
4145 struct pet_access_gist_data data;
4147 if (!stmt)
4148 return NULL;
4150 data.domain = isl_set_copy(stmt->domain);
4151 data.value_bounds = value_bounds;
4152 if (stmt->n_arg > 0)
4153 data.domain = isl_map_domain(isl_set_unwrap(data.domain));
4155 data.domain = isl_set_intersect_params(data.domain,
4156 isl_set_copy(context));
4158 for (i = 0; i < stmt->n_arg; ++i) {
4159 stmt->args[i] = pet_expr_map_access(stmt->args[i],
4160 &access_gist, &data);
4161 if (!stmt->args[i])
4162 goto error;
4165 stmt->body = pet_expr_map_access(stmt->body, &access_gist, &data);
4166 if (!stmt->body)
4167 goto error;
4169 isl_set_free(data.domain);
4171 space = isl_set_get_space(stmt->domain);
4172 if (isl_space_is_wrapping(space))
4173 space = isl_space_domain(isl_space_unwrap(space));
4174 domain = isl_set_universe(space);
4175 domain = isl_set_intersect_params(domain, isl_set_copy(context));
4176 if (stmt->n_arg > 0)
4177 domain = apply_value_bounds(domain, stmt->n_arg, stmt->args,
4178 value_bounds);
4179 stmt->domain = isl_set_gist(stmt->domain, domain);
4180 if (!stmt->domain)
4181 return pet_stmt_free(stmt);
4183 return stmt;
4184 error:
4185 isl_set_free(data.domain);
4186 return pet_stmt_free(stmt);
4189 /* Compute the gist of the extent of the array
4190 * based on the constraints on the parameters specified by "context".
4192 static struct pet_array *array_gist(struct pet_array *array,
4193 __isl_keep isl_set *context)
4195 if (!array)
4196 return NULL;
4198 array->extent = isl_set_gist_params(array->extent,
4199 isl_set_copy(context));
4200 if (!array->extent)
4201 return pet_array_free(array);
4203 return array;
4206 /* Compute the gist of all sets and relations in "scop"
4207 * based on the constraints on the parameters specified by "scop->context"
4208 * and the constraints on the values of nested accesses specified
4209 * by "value_bounds".
4211 struct pet_scop *pet_scop_gist(struct pet_scop *scop,
4212 __isl_keep isl_union_map *value_bounds)
4214 int i;
4216 if (!scop)
4217 return NULL;
4219 scop->context = isl_set_coalesce(scop->context);
4220 if (!scop->context)
4221 return pet_scop_free(scop);
4223 for (i = 0; i < scop->n_array; ++i) {
4224 scop->arrays[i] = array_gist(scop->arrays[i], scop->context);
4225 if (!scop->arrays[i])
4226 return pet_scop_free(scop);
4229 for (i = 0; i < scop->n_stmt; ++i) {
4230 scop->stmts[i] = stmt_gist(scop->stmts[i], scop->context,
4231 value_bounds);
4232 if (!scop->stmts[i])
4233 return pet_scop_free(scop);
4236 return scop;
4239 /* Intersect the context of "scop" with "context".
4240 * To ensure that we don't introduce any unnamed parameters in
4241 * the context of "scop", we first remove the unnamed parameters
4242 * from "context".
4244 struct pet_scop *pet_scop_restrict_context(struct pet_scop *scop,
4245 __isl_take isl_set *context)
4247 if (!scop)
4248 goto error;
4250 context = set_project_out_unnamed_params(context);
4251 scop->context = isl_set_intersect(scop->context, context);
4252 if (!scop->context)
4253 return pet_scop_free(scop);
4255 return scop;
4256 error:
4257 isl_set_free(context);
4258 return pet_scop_free(scop);
4261 /* Drop the current context of "scop". That is, replace the context
4262 * by a universal set.
4264 struct pet_scop *pet_scop_reset_context(struct pet_scop *scop)
4266 isl_space *space;
4268 if (!scop)
4269 return NULL;
4271 space = isl_set_get_space(scop->context);
4272 isl_set_free(scop->context);
4273 scop->context = isl_set_universe(space);
4274 if (!scop->context)
4275 return pet_scop_free(scop);
4277 return scop;
4280 /* Append "array" to the arrays of "scop".
4282 struct pet_scop *pet_scop_add_array(struct pet_scop *scop,
4283 struct pet_array *array)
4285 isl_ctx *ctx;
4286 struct pet_array **arrays;
4288 if (!array || !scop)
4289 goto error;
4291 ctx = isl_set_get_ctx(scop->context);
4292 arrays = isl_realloc_array(ctx, scop->arrays, struct pet_array *,
4293 scop->n_array + 1);
4294 if (!arrays)
4295 goto error;
4296 scop->arrays = arrays;
4297 scop->arrays[scop->n_array] = array;
4298 scop->n_array++;
4300 return scop;
4301 error:
4302 pet_array_free(array);
4303 return pet_scop_free(scop);
4306 /* Create and return an implication on filter values equal to "satisfied"
4307 * with extension "map".
4309 static struct pet_implication *new_implication(__isl_take isl_map *map,
4310 int satisfied)
4312 isl_ctx *ctx;
4313 struct pet_implication *implication;
4315 if (!map)
4316 return NULL;
4317 ctx = isl_map_get_ctx(map);
4318 implication = isl_alloc_type(ctx, struct pet_implication);
4319 if (!implication)
4320 goto error;
4322 implication->extension = map;
4323 implication->satisfied = satisfied;
4325 return implication;
4326 error:
4327 isl_map_free(map);
4328 return NULL;
4331 /* Add an implication on filter values equal to "satisfied"
4332 * with extension "map" to "scop".
4334 struct pet_scop *pet_scop_add_implication(struct pet_scop *scop,
4335 __isl_take isl_map *map, int satisfied)
4337 isl_ctx *ctx;
4338 struct pet_implication *implication;
4339 struct pet_implication **implications;
4341 implication = new_implication(map, satisfied);
4342 if (!scop || !implication)
4343 goto error;
4345 ctx = isl_set_get_ctx(scop->context);
4346 implications = isl_realloc_array(ctx, scop->implications,
4347 struct pet_implication *,
4348 scop->n_implication + 1);
4349 if (!implications)
4350 goto error;
4351 scop->implications = implications;
4352 scop->implications[scop->n_implication] = implication;
4353 scop->n_implication++;
4355 return scop;
4356 error:
4357 pet_implication_free(implication);
4358 return pet_scop_free(scop);
4361 /* Given an access expression, check if it is data dependent.
4362 * If so, set *found and abort the search.
4364 static int is_data_dependent(struct pet_expr *expr, void *user)
4366 int *found = user;
4368 if (expr->n_arg) {
4369 *found = 1;
4370 return -1;
4373 return 0;
4376 /* Does "scop" contain any data dependent accesses?
4378 * Check the body of each statement for such accesses.
4380 int pet_scop_has_data_dependent_accesses(struct pet_scop *scop)
4382 int i;
4383 int found = 0;
4385 if (!scop)
4386 return -1;
4388 for (i = 0; i < scop->n_stmt; ++i) {
4389 int r = pet_expr_foreach_access_expr(scop->stmts[i]->body,
4390 &is_data_dependent, &found);
4391 if (r < 0 && !found)
4392 return -1;
4393 if (found)
4394 return found;
4397 return found;
4400 /* Does "scop" contain and data dependent conditions?
4402 int pet_scop_has_data_dependent_conditions(struct pet_scop *scop)
4404 int i;
4406 if (!scop)
4407 return -1;
4409 for (i = 0; i < scop->n_stmt; ++i)
4410 if (scop->stmts[i]->n_arg > 0)
4411 return 1;
4413 return 0;
4416 /* Keep track of the "input" file inside the (extended) "scop".
4418 struct pet_scop *pet_scop_set_input_file(struct pet_scop *scop, FILE *input)
4420 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
4422 if (!scop)
4423 return NULL;
4425 ext->input = input;
4427 return scop;
4430 /* Print the original code corresponding to "scop" to printer "p".
4432 * pet_scop_print_original can only be called from
4433 * a pet_transform_C_source callback. This means that the input
4434 * file is stored in the extended scop and that the printer prints
4435 * to a file.
4437 __isl_give isl_printer *pet_scop_print_original(struct pet_scop *scop,
4438 __isl_take isl_printer *p)
4440 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
4441 FILE *output;
4443 if (!scop || !p)
4444 return isl_printer_free(p);
4446 if (!ext->input)
4447 isl_die(isl_printer_get_ctx(p), isl_error_invalid,
4448 "no input file stored in scop",
4449 return isl_printer_free(p));
4451 output = isl_printer_get_file(p);
4452 if (!output)
4453 return isl_printer_free(p);
4455 if (copy(ext->input, output, scop->start, scop->end) < 0)
4456 return isl_printer_free(p);
4458 return p;