scop.c: scop_collect_accesses: rename "dim" variable to "space"
[pet.git] / scop.c
blobbae84980e6e1e6ed432a5bf1eb521a88efd4c236
1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2013 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_eq] = "==",
66 [pet_op_le] = "<=",
67 [pet_op_lt] = "<",
68 [pet_op_gt] = ">",
69 [pet_op_minus] = "-",
70 [pet_op_post_inc] = "++",
71 [pet_op_post_dec] = "--",
72 [pet_op_pre_inc] = "++",
73 [pet_op_pre_dec] = "--",
74 [pet_op_address_of] = "&",
75 [pet_op_kill] = "kill"
78 /* pet_scop with extra information that is used during parsing and printing.
80 * In particular, we keep track of conditions under which we want
81 * to skip the rest of the current loop iteration (skip[pet_skip_now])
82 * and of conditions under which we want to skip subsequent
83 * loop iterations (skip[pet_skip_later]).
85 * The conditions are represented as index expressions defined
86 * over a zero-dimensiona domain. The index expression is either
87 * a boolean affine expression or an access to a variable, which
88 * is assumed to attain values zero and one. The condition holds
89 * if the variable has value one or if the affine expression
90 * has value one (typically for only part of the parameter space).
92 * A missing condition (skip[type] == NULL) means that we don't want
93 * to skip anything.
95 * Additionally, we keep track of the original input file
96 * inside pet_transform_C_source.
98 struct pet_scop_ext {
99 struct pet_scop scop;
101 isl_multi_pw_aff *skip[2];
102 FILE *input;
105 const char *pet_op_str(enum pet_op_type op)
107 return op_str[op];
110 int pet_op_is_inc_dec(enum pet_op_type op)
112 return op == pet_op_post_inc || op == pet_op_post_dec ||
113 op == pet_op_pre_inc || op == pet_op_pre_dec;
116 const char *pet_type_str(enum pet_expr_type type)
118 return type_str[type];
121 enum pet_op_type pet_str_op(const char *str)
123 int i;
125 for (i = 0; i < ARRAY_SIZE(op_str); ++i)
126 if (!strcmp(op_str[i], str))
127 return i;
129 return -1;
132 enum pet_expr_type pet_str_type(const char *str)
134 int i;
136 for (i = 0; i < ARRAY_SIZE(type_str); ++i)
137 if (!strcmp(type_str[i], str))
138 return i;
140 return -1;
143 /* Construct an access pet_expr from an access relation and an index expression.
144 * By default, it is considered to be a read access.
146 struct pet_expr *pet_expr_from_access_and_index( __isl_take isl_map *access,
147 __isl_take isl_multi_pw_aff *index)
149 isl_ctx *ctx = isl_map_get_ctx(access);
150 struct pet_expr *expr;
152 if (!index || !access)
153 goto error;
154 expr = isl_calloc_type(ctx, struct pet_expr);
155 if (!expr)
156 goto error;
158 expr->type = pet_expr_access;
159 expr->acc.access = access;
160 expr->acc.index = index;
161 expr->acc.read = 1;
162 expr->acc.write = 0;
164 return expr;
165 error:
166 isl_map_free(access);
167 isl_multi_pw_aff_free(index);
168 return NULL;
171 /* Construct an access pet_expr from an index expression.
172 * By default, the access is considered to be a read access.
174 struct pet_expr *pet_expr_from_index(__isl_take isl_multi_pw_aff *index)
176 isl_map *access;
178 access = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index));
179 return pet_expr_from_access_and_index(access, index);
182 /* Extend the range of "access" with "n" dimensions, retaining
183 * the tuple identifier on this range.
185 static __isl_give isl_map *extend_range(__isl_take isl_map *access, int n)
187 isl_id *id;
189 id = isl_map_get_tuple_id(access, isl_dim_out);
190 access = isl_map_add_dims(access, isl_dim_out, n);
191 access = isl_map_set_tuple_id(access, isl_dim_out, id);
193 return access;
196 /* Construct an access pet_expr from an index expression and
197 * the depth of the accessed array.
198 * By default, the access is considered to be a read access.
200 * If the number of indices is smaller than the depth of the array,
201 * then we assume that all elements of the remaining dimensions
202 * are accessed.
204 struct pet_expr *pet_expr_from_index_and_depth(
205 __isl_take isl_multi_pw_aff *index, int depth)
207 isl_map *access;
208 int dim;
210 access = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index));
211 if (!access)
212 goto error;
213 dim = isl_map_dim(access, isl_dim_out);
214 if (dim > depth)
215 isl_die(isl_map_get_ctx(access), isl_error_internal,
216 "number of indices greater than depth",
217 access = isl_map_free(access));
218 if (dim == depth)
219 return pet_expr_from_access_and_index(access, index);
221 access = extend_range(access, depth - dim);
223 return pet_expr_from_access_and_index(access, index);
224 error:
225 isl_multi_pw_aff_free(index);
226 return NULL;
229 /* Construct a pet_expr that kills the elements specified by
230 * the index expression "index" and the access relation "access".
232 struct pet_expr *pet_expr_kill_from_access_and_index(__isl_take isl_map *access,
233 __isl_take isl_multi_pw_aff *index)
235 isl_ctx *ctx;
236 struct pet_expr *expr;
238 if (!access || !index)
239 goto error;
241 ctx = isl_multi_pw_aff_get_ctx(index);
242 expr = pet_expr_from_access_and_index(access, index);
243 if (!expr)
244 return NULL;
245 expr->acc.read = 0;
246 return pet_expr_new_unary(ctx, pet_op_kill, expr);
247 error:
248 isl_map_free(access);
249 isl_multi_pw_aff_free(index);
250 return NULL;
253 /* Construct a unary pet_expr that performs "op" on "arg".
255 struct pet_expr *pet_expr_new_unary(isl_ctx *ctx, enum pet_op_type op,
256 struct pet_expr *arg)
258 struct pet_expr *expr;
260 if (!arg)
261 goto error;
262 expr = isl_alloc_type(ctx, struct pet_expr);
263 if (!expr)
264 goto error;
266 expr->type = pet_expr_unary;
267 expr->op = op;
268 expr->n_arg = 1;
269 expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
270 if (!expr->args)
271 goto error;
272 expr->args[pet_un_arg] = arg;
274 return expr;
275 error:
276 pet_expr_free(arg);
277 return NULL;
280 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
282 struct pet_expr *pet_expr_new_binary(isl_ctx *ctx, enum pet_op_type op,
283 struct pet_expr *lhs, struct pet_expr *rhs)
285 struct pet_expr *expr;
287 if (!lhs || !rhs)
288 goto error;
289 expr = isl_alloc_type(ctx, struct pet_expr);
290 if (!expr)
291 goto error;
293 expr->type = pet_expr_binary;
294 expr->op = op;
295 expr->n_arg = 2;
296 expr->args = isl_calloc_array(ctx, struct pet_expr *, 2);
297 if (!expr->args)
298 goto error;
299 expr->args[pet_bin_lhs] = lhs;
300 expr->args[pet_bin_rhs] = rhs;
302 return expr;
303 error:
304 pet_expr_free(lhs);
305 pet_expr_free(rhs);
306 return NULL;
309 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
311 struct pet_expr *pet_expr_new_ternary(isl_ctx *ctx, struct pet_expr *cond,
312 struct pet_expr *lhs, struct pet_expr *rhs)
314 struct pet_expr *expr;
316 if (!cond || !lhs || !rhs)
317 goto error;
318 expr = isl_alloc_type(ctx, struct pet_expr);
319 if (!expr)
320 goto error;
322 expr->type = pet_expr_ternary;
323 expr->n_arg = 3;
324 expr->args = isl_calloc_array(ctx, struct pet_expr *, 3);
325 if (!expr->args)
326 goto error;
327 expr->args[pet_ter_cond] = cond;
328 expr->args[pet_ter_true] = lhs;
329 expr->args[pet_ter_false] = rhs;
331 return expr;
332 error:
333 pet_expr_free(cond);
334 pet_expr_free(lhs);
335 pet_expr_free(rhs);
336 return NULL;
339 /* Construct a call pet_expr that calls function "name" with "n_arg"
340 * arguments. The caller is responsible for filling in the arguments.
342 struct pet_expr *pet_expr_new_call(isl_ctx *ctx, const char *name,
343 unsigned n_arg)
345 struct pet_expr *expr;
347 expr = isl_alloc_type(ctx, struct pet_expr);
348 if (!expr)
349 return NULL;
351 expr->type = pet_expr_call;
352 expr->n_arg = n_arg;
353 expr->name = strdup(name);
354 expr->args = isl_calloc_array(ctx, struct pet_expr *, n_arg);
355 if (!expr->name || !expr->args)
356 return pet_expr_free(expr);
358 return expr;
361 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
363 struct pet_expr *pet_expr_new_cast(isl_ctx *ctx, const char *type_name,
364 struct pet_expr *arg)
366 struct pet_expr *expr;
368 if (!arg)
369 return NULL;
371 expr = isl_alloc_type(ctx, struct pet_expr);
372 if (!expr)
373 goto error;
375 expr->type = pet_expr_cast;
376 expr->n_arg = 1;
377 expr->type_name = strdup(type_name);
378 expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
379 if (!expr->type_name || !expr->args)
380 goto error;
382 expr->args[0] = arg;
384 return expr;
385 error:
386 pet_expr_free(arg);
387 pet_expr_free(expr);
388 return NULL;
391 /* Construct a pet_expr that represents the double "d".
393 struct pet_expr *pet_expr_new_double(isl_ctx *ctx, double val, const char *s)
395 struct pet_expr *expr;
397 expr = isl_calloc_type(ctx, struct pet_expr);
398 if (!expr)
399 return NULL;
401 expr->type = pet_expr_double;
402 expr->d.val = val;
403 expr->d.s = strdup(s);
404 if (!expr->d.s)
405 return pet_expr_free(expr);
407 return expr;
410 struct pet_expr *pet_expr_free(struct pet_expr *expr)
412 int i;
414 if (!expr)
415 return NULL;
417 for (i = 0; i < expr->n_arg; ++i)
418 pet_expr_free(expr->args[i]);
419 free(expr->args);
421 switch (expr->type) {
422 case pet_expr_access:
423 isl_id_free(expr->acc.ref_id);
424 isl_map_free(expr->acc.access);
425 isl_multi_pw_aff_free(expr->acc.index);
426 break;
427 case pet_expr_call:
428 free(expr->name);
429 break;
430 case pet_expr_cast:
431 free(expr->type_name);
432 break;
433 case pet_expr_double:
434 free(expr->d.s);
435 break;
436 case pet_expr_unary:
437 case pet_expr_binary:
438 case pet_expr_ternary:
439 break;
442 free(expr);
443 return NULL;
446 static void expr_dump(struct pet_expr *expr, int indent)
448 int i;
450 if (!expr)
451 return;
453 fprintf(stderr, "%*s", indent, "");
455 switch (expr->type) {
456 case pet_expr_double:
457 fprintf(stderr, "%s\n", expr->d.s);
458 break;
459 case pet_expr_access:
460 isl_id_dump(expr->acc.ref_id);
461 fprintf(stderr, "%*s", indent, "");
462 isl_map_dump(expr->acc.access);
463 fprintf(stderr, "%*s", indent, "");
464 isl_multi_pw_aff_dump(expr->acc.index);
465 fprintf(stderr, "%*sread: %d\n", indent + 2,
466 "", expr->acc.read);
467 fprintf(stderr, "%*swrite: %d\n", indent + 2,
468 "", expr->acc.write);
469 for (i = 0; i < expr->n_arg; ++i)
470 expr_dump(expr->args[i], indent + 2);
471 break;
472 case pet_expr_unary:
473 fprintf(stderr, "%s\n", op_str[expr->op]);
474 expr_dump(expr->args[pet_un_arg], indent + 2);
475 break;
476 case pet_expr_binary:
477 fprintf(stderr, "%s\n", op_str[expr->op]);
478 expr_dump(expr->args[pet_bin_lhs], indent + 2);
479 expr_dump(expr->args[pet_bin_rhs], indent + 2);
480 break;
481 case pet_expr_ternary:
482 fprintf(stderr, "?:\n");
483 expr_dump(expr->args[pet_ter_cond], indent + 2);
484 expr_dump(expr->args[pet_ter_true], indent + 2);
485 expr_dump(expr->args[pet_ter_false], indent + 2);
486 break;
487 case pet_expr_call:
488 fprintf(stderr, "%s/%d\n", expr->name, expr->n_arg);
489 for (i = 0; i < expr->n_arg; ++i)
490 expr_dump(expr->args[i], indent + 2);
491 break;
492 case pet_expr_cast:
493 fprintf(stderr, "(%s)\n", expr->type_name);
494 for (i = 0; i < expr->n_arg; ++i)
495 expr_dump(expr->args[i], indent + 2);
496 break;
500 void pet_expr_dump(struct pet_expr *expr)
502 expr_dump(expr, 0);
505 /* Does "expr" represent an access to an unnamed space, i.e.,
506 * does it represent an affine expression?
508 int pet_expr_is_affine(struct pet_expr *expr)
510 int has_id;
512 if (!expr)
513 return -1;
514 if (expr->type != pet_expr_access)
515 return 0;
517 has_id = isl_map_has_tuple_id(expr->acc.access, isl_dim_out);
518 if (has_id < 0)
519 return -1;
521 return !has_id;
524 /* Return the identifier of the array accessed by "expr".
526 __isl_give isl_id *pet_expr_access_get_id(struct pet_expr *expr)
528 if (!expr)
529 return NULL;
530 if (expr->type != pet_expr_access)
531 return NULL;
532 return isl_map_get_tuple_id(expr->acc.access, isl_dim_out);
535 /* Align the parameters of expr->acc.index and expr->acc.access.
537 struct pet_expr *pet_expr_access_align_params(struct pet_expr *expr)
539 if (!expr)
540 return NULL;
541 if (expr->type != pet_expr_access)
542 return pet_expr_free(expr);
544 expr->acc.access = isl_map_align_params(expr->acc.access,
545 isl_multi_pw_aff_get_space(expr->acc.index));
546 expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
547 isl_map_get_space(expr->acc.access));
548 if (!expr->acc.access || !expr->acc.index)
549 return pet_expr_free(expr);
551 return expr;
554 /* Does "expr" represent an access to a scalar, i.e., zero-dimensional array?
556 int pet_expr_is_scalar_access(struct pet_expr *expr)
558 if (!expr)
559 return -1;
560 if (expr->type != pet_expr_access)
561 return 0;
563 return isl_map_dim(expr->acc.access, isl_dim_out) == 0;
566 /* Return 1 if the two pet_exprs are equivalent.
568 int pet_expr_is_equal(struct pet_expr *expr1, struct pet_expr *expr2)
570 int i;
572 if (!expr1 || !expr2)
573 return 0;
575 if (expr1->type != expr2->type)
576 return 0;
577 if (expr1->n_arg != expr2->n_arg)
578 return 0;
579 for (i = 0; i < expr1->n_arg; ++i)
580 if (!pet_expr_is_equal(expr1->args[i], expr2->args[i]))
581 return 0;
582 switch (expr1->type) {
583 case pet_expr_double:
584 if (strcmp(expr1->d.s, expr2->d.s))
585 return 0;
586 if (expr1->d.val != expr2->d.val)
587 return 0;
588 break;
589 case pet_expr_access:
590 if (expr1->acc.read != expr2->acc.read)
591 return 0;
592 if (expr1->acc.write != expr2->acc.write)
593 return 0;
594 if (expr1->acc.ref_id != expr2->acc.ref_id)
595 return 0;
596 if (!expr1->acc.access || !expr2->acc.access)
597 return 0;
598 if (!isl_map_is_equal(expr1->acc.access, expr2->acc.access))
599 return 0;
600 if (!expr1->acc.index || !expr2->acc.index)
601 return 0;
602 if (!isl_multi_pw_aff_plain_is_equal(expr1->acc.index,
603 expr2->acc.index))
604 return 0;
605 break;
606 case pet_expr_unary:
607 case pet_expr_binary:
608 case pet_expr_ternary:
609 if (expr1->op != expr2->op)
610 return 0;
611 break;
612 case pet_expr_call:
613 if (strcmp(expr1->name, expr2->name))
614 return 0;
615 break;
616 case pet_expr_cast:
617 if (strcmp(expr1->type_name, expr2->type_name))
618 return 0;
619 break;
622 return 1;
625 /* Add extra conditions on the parameters to all access relations in "expr".
627 * The conditions are not added to the index expression. Instead, they
628 * are used to try and simplifty the index expression.
630 struct pet_expr *pet_expr_restrict(struct pet_expr *expr,
631 __isl_take isl_set *cond)
633 int i;
635 if (!expr)
636 goto error;
638 for (i = 0; i < expr->n_arg; ++i) {
639 expr->args[i] = pet_expr_restrict(expr->args[i],
640 isl_set_copy(cond));
641 if (!expr->args[i])
642 goto error;
645 if (expr->type == pet_expr_access) {
646 expr->acc.access = isl_map_intersect_params(expr->acc.access,
647 isl_set_copy(cond));
648 expr->acc.index = isl_multi_pw_aff_gist_params(
649 expr->acc.index, isl_set_copy(cond));
650 if (!expr->acc.access || !expr->acc.index)
651 goto error;
654 isl_set_free(cond);
655 return expr;
656 error:
657 isl_set_free(cond);
658 return pet_expr_free(expr);
661 /* Tag the access relation "access" with "id".
662 * That is, insert the id as the range of a wrapped relation
663 * in the domain of "access".
665 * If "access" is of the form
667 * D[i] -> A[a]
669 * then the result is of the form
671 * [D[i] -> id[]] -> A[a]
673 static __isl_give isl_map *tag_access(__isl_take isl_map *access,
674 __isl_take isl_id *id)
676 isl_space *space;
677 isl_map *add_tag;
679 space = isl_space_range(isl_map_get_space(access));
680 space = isl_space_from_range(space);
681 space = isl_space_set_tuple_id(space, isl_dim_in, id);
682 add_tag = isl_map_universe(space);
683 access = isl_map_domain_product(access, add_tag);
685 return access;
688 /* Modify all expressions of type pet_expr_access in "expr"
689 * by calling "fn" on them.
691 struct pet_expr *pet_expr_map_access(struct pet_expr *expr,
692 struct pet_expr *(*fn)(struct pet_expr *expr, void *user),
693 void *user)
695 int i;
697 if (!expr)
698 return NULL;
700 for (i = 0; i < expr->n_arg; ++i) {
701 expr->args[i] = pet_expr_map_access(expr->args[i], fn, user);
702 if (!expr->args[i])
703 return pet_expr_free(expr);
706 if (expr->type == pet_expr_access)
707 expr = fn(expr, user);
709 return expr;
712 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
714 * Return -1 on error (where fn return a negative value is treated as an error).
715 * Otherwise return 0.
717 int pet_expr_foreach_access_expr(struct pet_expr *expr,
718 int (*fn)(struct pet_expr *expr, void *user), void *user)
720 int i;
722 if (!expr)
723 return -1;
725 for (i = 0; i < expr->n_arg; ++i)
726 if (pet_expr_foreach_access_expr(expr->args[i], fn, user) < 0)
727 return -1;
729 if (expr->type == pet_expr_access)
730 return fn(expr, user);
732 return 0;
735 /* Modify the access relation and index expression
736 * of the given access expression
737 * based on the given iteration space transformation.
738 * In particular, precompose the access relation and index expression
739 * with the update function.
741 * If the access has any arguments then the domain of the access relation
742 * is a wrapped mapping from the iteration space to the space of
743 * argument values. We only need to change the domain of this wrapped
744 * mapping, so we extend the input transformation with an identity mapping
745 * on the space of argument values.
747 static struct pet_expr *update_domain(struct pet_expr *expr, void *user)
749 isl_multi_pw_aff *update = user;
750 isl_space *space;
752 update = isl_multi_pw_aff_copy(update);
754 space = isl_map_get_space(expr->acc.access);
755 space = isl_space_domain(space);
756 if (!isl_space_is_wrapping(space))
757 isl_space_free(space);
758 else {
759 isl_multi_pw_aff *id;
760 space = isl_space_unwrap(space);
761 space = isl_space_range(space);
762 space = isl_space_map_from_set(space);
763 id = isl_multi_pw_aff_identity(space);
764 update = isl_multi_pw_aff_product(update, id);
767 expr->acc.access = isl_map_preimage_domain_multi_pw_aff(
768 expr->acc.access,
769 isl_multi_pw_aff_copy(update));
770 expr->acc.index = isl_multi_pw_aff_pullback_multi_pw_aff(
771 expr->acc.index, update);
772 if (!expr->acc.access || !expr->acc.index)
773 return pet_expr_free(expr);
775 return expr;
778 /* Modify all access relations in "expr" by precomposing them with
779 * the given iteration space transformation.
781 static struct pet_expr *expr_update_domain(struct pet_expr *expr,
782 __isl_take isl_multi_pw_aff *update)
784 expr = pet_expr_map_access(expr, &update_domain, update);
785 isl_multi_pw_aff_free(update);
786 return expr;
789 /* Construct a pet_stmt with given line number and statement
790 * number from a pet_expr.
791 * The initial iteration domain is the zero-dimensional universe.
792 * The name of the domain is given by "label" if it is non-NULL.
793 * Otherwise, the name is constructed as S_<id>.
794 * The domains of all access relations are modified to refer
795 * to the statement iteration domain.
797 struct pet_stmt *pet_stmt_from_pet_expr(isl_ctx *ctx, int line,
798 __isl_take isl_id *label, int id, struct pet_expr *expr)
800 struct pet_stmt *stmt;
801 isl_space *dim;
802 isl_set *dom;
803 isl_map *sched;
804 isl_multi_pw_aff *add_name;
805 char name[50];
807 if (!expr)
808 goto error;
810 stmt = isl_calloc_type(ctx, struct pet_stmt);
811 if (!stmt)
812 goto error;
814 dim = isl_space_set_alloc(ctx, 0, 0);
815 if (label)
816 dim = isl_space_set_tuple_id(dim, isl_dim_set, label);
817 else {
818 snprintf(name, sizeof(name), "S_%d", id);
819 dim = isl_space_set_tuple_name(dim, isl_dim_set, name);
821 dom = isl_set_universe(isl_space_copy(dim));
822 sched = isl_map_from_domain(isl_set_copy(dom));
824 dim = isl_space_from_domain(dim);
825 add_name = isl_multi_pw_aff_zero(dim);
826 expr = expr_update_domain(expr, add_name);
828 stmt->line = line;
829 stmt->domain = dom;
830 stmt->schedule = sched;
831 stmt->body = expr;
833 if (!stmt->domain || !stmt->schedule || !stmt->body)
834 return pet_stmt_free(stmt);
836 return stmt;
837 error:
838 isl_id_free(label);
839 pet_expr_free(expr);
840 return NULL;
843 void *pet_stmt_free(struct pet_stmt *stmt)
845 int i;
847 if (!stmt)
848 return NULL;
850 isl_set_free(stmt->domain);
851 isl_map_free(stmt->schedule);
852 pet_expr_free(stmt->body);
854 for (i = 0; i < stmt->n_arg; ++i)
855 pet_expr_free(stmt->args[i]);
856 free(stmt->args);
858 free(stmt);
859 return NULL;
862 static void stmt_dump(struct pet_stmt *stmt, int indent)
864 int i;
866 if (!stmt)
867 return;
869 fprintf(stderr, "%*s%d\n", indent, "", stmt->line);
870 fprintf(stderr, "%*s", indent, "");
871 isl_set_dump(stmt->domain);
872 fprintf(stderr, "%*s", indent, "");
873 isl_map_dump(stmt->schedule);
874 expr_dump(stmt->body, indent);
875 for (i = 0; i < stmt->n_arg; ++i)
876 expr_dump(stmt->args[i], indent + 2);
879 void pet_stmt_dump(struct pet_stmt *stmt)
881 stmt_dump(stmt, 0);
884 /* Allocate a new pet_type with the given "name" and "definition".
886 struct pet_type *pet_type_alloc(isl_ctx *ctx, const char *name,
887 const char *definition)
889 struct pet_type *type;
891 type = isl_alloc_type(ctx, struct pet_type);
892 if (!type)
893 return NULL;
895 type->name = strdup(name);
896 type->definition = strdup(definition);
898 if (!type->name || !type->definition)
899 return pet_type_free(type);
901 return type;
904 /* Free "type" and return NULL.
906 struct pet_type *pet_type_free(struct pet_type *type)
908 if (!type)
909 return NULL;
911 free(type->name);
912 free(type->definition);
914 free(type);
915 return NULL;
918 struct pet_array *pet_array_free(struct pet_array *array)
920 if (!array)
921 return NULL;
923 isl_set_free(array->context);
924 isl_set_free(array->extent);
925 isl_set_free(array->value_bounds);
926 free(array->element_type);
928 free(array);
929 return NULL;
932 void pet_array_dump(struct pet_array *array)
934 if (!array)
935 return;
937 isl_set_dump(array->context);
938 isl_set_dump(array->extent);
939 isl_set_dump(array->value_bounds);
940 fprintf(stderr, "%s %s\n", array->element_type,
941 array->live_out ? "live-out" : "");
944 /* Alloc a pet_scop structure, with extra room for information that
945 * is only used during parsing.
947 struct pet_scop *pet_scop_alloc(isl_ctx *ctx)
949 return &isl_calloc_type(ctx, struct pet_scop_ext)->scop;
952 /* Construct a pet_scop with room for n statements.
954 static struct pet_scop *scop_alloc(isl_ctx *ctx, int n)
956 isl_space *space;
957 struct pet_scop *scop;
959 scop = pet_scop_alloc(ctx);
960 if (!scop)
961 return NULL;
963 space = isl_space_params_alloc(ctx, 0);
964 scop->context = isl_set_universe(isl_space_copy(space));
965 scop->context_value = isl_set_universe(space);
966 scop->stmts = isl_calloc_array(ctx, struct pet_stmt *, n);
967 if (!scop->context || !scop->stmts)
968 return pet_scop_free(scop);
970 scop->n_stmt = n;
972 return scop;
975 struct pet_scop *pet_scop_empty(isl_ctx *ctx)
977 return scop_alloc(ctx, 0);
980 /* Update "context" with respect to the valid parameter values for "access".
982 static __isl_give isl_set *access_extract_context(__isl_keep isl_map *access,
983 __isl_take isl_set *context)
985 context = isl_set_intersect(context,
986 isl_map_params(isl_map_copy(access)));
987 return context;
990 /* Update "context" with respect to the valid parameter values for "expr".
992 * If "expr" represents a ternary operator, then a parameter value
993 * needs to be valid for the condition and for at least one of the
994 * remaining two arguments.
995 * If the condition is an affine expression, then we can be a bit more specific.
996 * The parameter then has to be valid for the second argument for
997 * non-zero accesses and valid for the third argument for zero accesses.
999 static __isl_give isl_set *expr_extract_context(struct pet_expr *expr,
1000 __isl_take isl_set *context)
1002 int i;
1004 if (expr->type == pet_expr_ternary) {
1005 int is_aff;
1006 isl_set *context1, *context2;
1008 is_aff = pet_expr_is_affine(expr->args[0]);
1009 if (is_aff < 0)
1010 goto error;
1012 context = expr_extract_context(expr->args[0], context);
1013 context1 = expr_extract_context(expr->args[1],
1014 isl_set_copy(context));
1015 context2 = expr_extract_context(expr->args[2], context);
1017 if (is_aff) {
1018 isl_map *access;
1019 isl_set *zero_set;
1021 access = isl_map_copy(expr->args[0]->acc.access);
1022 access = isl_map_fix_si(access, isl_dim_out, 0, 0);
1023 zero_set = isl_map_params(access);
1024 context1 = isl_set_subtract(context1,
1025 isl_set_copy(zero_set));
1026 context2 = isl_set_intersect(context2, zero_set);
1029 context = isl_set_union(context1, context2);
1030 context = isl_set_coalesce(context);
1032 return context;
1035 for (i = 0; i < expr->n_arg; ++i)
1036 context = expr_extract_context(expr->args[i], context);
1038 if (expr->type == pet_expr_access)
1039 context = access_extract_context(expr->acc.access, context);
1041 return context;
1042 error:
1043 isl_set_free(context);
1044 return NULL;
1047 /* Update "context" with respect to the valid parameter values for "stmt".
1049 static __isl_give isl_set *stmt_extract_context(struct pet_stmt *stmt,
1050 __isl_take isl_set *context)
1052 int i;
1054 for (i = 0; i < stmt->n_arg; ++i)
1055 context = expr_extract_context(stmt->args[i], context);
1057 context = expr_extract_context(stmt->body, context);
1059 return context;
1062 /* Construct a pet_scop that contains the given pet_stmt.
1064 struct pet_scop *pet_scop_from_pet_stmt(isl_ctx *ctx, struct pet_stmt *stmt)
1066 struct pet_scop *scop;
1068 if (!stmt)
1069 return NULL;
1071 scop = scop_alloc(ctx, 1);
1072 if (!scop)
1073 goto error;
1075 scop->context = stmt_extract_context(stmt, scop->context);
1076 if (!scop->context)
1077 goto error;
1079 scop->stmts[0] = stmt;
1081 return scop;
1082 error:
1083 pet_stmt_free(stmt);
1084 pet_scop_free(scop);
1085 return NULL;
1088 /* Does "mpa" represent an access to an element of an unnamed space, i.e.,
1089 * does it represent an affine expression?
1091 static int multi_pw_aff_is_affine(__isl_keep isl_multi_pw_aff *mpa)
1093 int has_id;
1095 has_id = isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out);
1096 if (has_id < 0)
1097 return -1;
1099 return !has_id;
1102 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
1104 static __isl_give isl_pw_aff *indicator_function(__isl_take isl_set *set,
1105 __isl_take isl_set *dom)
1107 isl_pw_aff *pa;
1108 pa = isl_set_indicator_function(set);
1109 pa = isl_pw_aff_intersect_domain(pa, dom);
1110 return pa;
1113 /* Return "lhs || rhs", defined on the shared definition domain.
1115 static __isl_give isl_pw_aff *pw_aff_or(__isl_take isl_pw_aff *lhs,
1116 __isl_take isl_pw_aff *rhs)
1118 isl_set *cond;
1119 isl_set *dom;
1121 dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs)),
1122 isl_pw_aff_domain(isl_pw_aff_copy(rhs)));
1123 cond = isl_set_union(isl_pw_aff_non_zero_set(lhs),
1124 isl_pw_aff_non_zero_set(rhs));
1125 cond = isl_set_coalesce(cond);
1126 return indicator_function(cond, dom);
1129 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
1130 * ext may be equal to either ext1 or ext2.
1132 * The two skips that need to be combined are assumed to be affine expressions.
1134 * We need to skip in ext if we need to skip in either ext1 or ext2.
1135 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
1137 static struct pet_scop_ext *combine_skips(struct pet_scop_ext *ext,
1138 struct pet_scop_ext *ext1, struct pet_scop_ext *ext2,
1139 enum pet_skip type)
1141 isl_pw_aff *skip, *skip1, *skip2;
1143 if (!ext)
1144 return NULL;
1145 if (!ext1->skip[type] && !ext2->skip[type])
1146 return ext;
1147 if (!ext1->skip[type]) {
1148 if (ext == ext2)
1149 return ext;
1150 ext->skip[type] = ext2->skip[type];
1151 ext2->skip[type] = NULL;
1152 return ext;
1154 if (!ext2->skip[type]) {
1155 if (ext == ext1)
1156 return ext;
1157 ext->skip[type] = ext1->skip[type];
1158 ext1->skip[type] = NULL;
1159 return ext;
1162 if (!multi_pw_aff_is_affine(ext1->skip[type]) ||
1163 !multi_pw_aff_is_affine(ext2->skip[type]))
1164 isl_die(isl_multi_pw_aff_get_ctx(ext1->skip[type]),
1165 isl_error_internal, "can only combine affine skips",
1166 goto error);
1168 skip1 = isl_multi_pw_aff_get_pw_aff(ext1->skip[type], 0);
1169 skip2 = isl_multi_pw_aff_get_pw_aff(ext2->skip[type], 0);
1170 skip = pw_aff_or(skip1, skip2);
1171 isl_multi_pw_aff_free(ext1->skip[type]);
1172 ext1->skip[type] = NULL;
1173 isl_multi_pw_aff_free(ext2->skip[type]);
1174 ext2->skip[type] = NULL;
1175 ext->skip[type] = isl_multi_pw_aff_from_pw_aff(skip);
1176 if (!ext->skip[type])
1177 goto error;
1179 return ext;
1180 error:
1181 pet_scop_free(&ext->scop);
1182 return NULL;
1185 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
1186 * where type takes on the values pet_skip_now and pet_skip_later.
1187 * scop may be equal to either scop1 or scop2.
1189 static struct pet_scop *scop_combine_skips(struct pet_scop *scop,
1190 struct pet_scop *scop1, struct pet_scop *scop2)
1192 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1193 struct pet_scop_ext *ext1 = (struct pet_scop_ext *) scop1;
1194 struct pet_scop_ext *ext2 = (struct pet_scop_ext *) scop2;
1196 ext = combine_skips(ext, ext1, ext2, pet_skip_now);
1197 ext = combine_skips(ext, ext1, ext2, pet_skip_later);
1198 return &ext->scop;
1201 /* Update scop->start and scop->end to include the region from "start"
1202 * to "end". In particular, if scop->end == 0, then "scop" does not
1203 * have any offset information yet and we simply take the information
1204 * from "start" and "end". Otherwise, we update the fields if the
1205 * region from "start" to "end" is not already included.
1207 struct pet_scop *pet_scop_update_start_end(struct pet_scop *scop,
1208 unsigned start, unsigned end)
1210 if (!scop)
1211 return NULL;
1212 if (scop->end == 0) {
1213 scop->start = start;
1214 scop->end = end;
1215 } else {
1216 if (start < scop->start)
1217 scop->start = start;
1218 if (end > scop->end)
1219 scop->end = end;
1222 return scop;
1225 /* Does "implication" appear in the list of implications of "scop"?
1227 static int is_known_implication(struct pet_scop *scop,
1228 struct pet_implication *implication)
1230 int i;
1232 for (i = 0; i < scop->n_implication; ++i) {
1233 struct pet_implication *pi = scop->implications[i];
1234 int equal;
1236 if (pi->satisfied != implication->satisfied)
1237 continue;
1238 equal = isl_map_is_equal(pi->extension, implication->extension);
1239 if (equal < 0)
1240 return -1;
1241 if (equal)
1242 return 1;
1245 return 0;
1248 /* Store the concatenation of the impliciations of "scop1" and "scop2"
1249 * in "scop", removing duplicates (i.e., implications in "scop2" that
1250 * already appear in "scop1").
1252 static struct pet_scop *scop_collect_implications(isl_ctx *ctx,
1253 struct pet_scop *scop, struct pet_scop *scop1, struct pet_scop *scop2)
1255 int i, j;
1257 if (!scop)
1258 return NULL;
1260 if (scop2->n_implication == 0) {
1261 scop->n_implication = scop1->n_implication;
1262 scop->implications = scop1->implications;
1263 scop1->n_implication = 0;
1264 scop1->implications = NULL;
1265 return scop;
1268 if (scop1->n_implication == 0) {
1269 scop->n_implication = scop2->n_implication;
1270 scop->implications = scop2->implications;
1271 scop2->n_implication = 0;
1272 scop2->implications = NULL;
1273 return scop;
1276 scop->implications = isl_calloc_array(ctx, struct pet_implication *,
1277 scop1->n_implication + scop2->n_implication);
1278 if (!scop->implications)
1279 return pet_scop_free(scop);
1281 for (i = 0; i < scop1->n_implication; ++i) {
1282 scop->implications[i] = scop1->implications[i];
1283 scop1->implications[i] = NULL;
1286 scop->n_implication = scop1->n_implication;
1287 j = scop1->n_implication;
1288 for (i = 0; i < scop2->n_implication; ++i) {
1289 int known;
1291 known = is_known_implication(scop, scop2->implications[i]);
1292 if (known < 0)
1293 return pet_scop_free(scop);
1294 if (known)
1295 continue;
1296 scop->implications[j++] = scop2->implications[i];
1297 scop2->implications[i] = NULL;
1299 scop->n_implication = j;
1301 return scop;
1304 /* Combine the offset information of "scop1" and "scop2" into "scop".
1306 static struct pet_scop *scop_combine_start_end(struct pet_scop *scop,
1307 struct pet_scop *scop1, struct pet_scop *scop2)
1309 if (scop1->end)
1310 scop = pet_scop_update_start_end(scop,
1311 scop1->start, scop1->end);
1312 if (scop2->end)
1313 scop = pet_scop_update_start_end(scop,
1314 scop2->start, scop2->end);
1315 return scop;
1318 /* Construct a pet_scop that contains the offset information,
1319 * arrays, statements and skip information in "scop1" and "scop2".
1321 static struct pet_scop *pet_scop_add(isl_ctx *ctx, struct pet_scop *scop1,
1322 struct pet_scop *scop2)
1324 int i;
1325 struct pet_scop *scop = NULL;
1327 if (!scop1 || !scop2)
1328 goto error;
1330 if (scop1->n_stmt == 0) {
1331 scop2 = scop_combine_skips(scop2, scop1, scop2);
1332 pet_scop_free(scop1);
1333 return scop2;
1336 if (scop2->n_stmt == 0) {
1337 scop1 = scop_combine_skips(scop1, scop1, scop2);
1338 pet_scop_free(scop2);
1339 return scop1;
1342 scop = scop_alloc(ctx, scop1->n_stmt + scop2->n_stmt);
1343 if (!scop)
1344 goto error;
1346 scop->arrays = isl_calloc_array(ctx, struct pet_array *,
1347 scop1->n_array + scop2->n_array);
1348 if (!scop->arrays)
1349 goto error;
1350 scop->n_array = scop1->n_array + scop2->n_array;
1352 for (i = 0; i < scop1->n_stmt; ++i) {
1353 scop->stmts[i] = scop1->stmts[i];
1354 scop1->stmts[i] = NULL;
1357 for (i = 0; i < scop2->n_stmt; ++i) {
1358 scop->stmts[scop1->n_stmt + i] = scop2->stmts[i];
1359 scop2->stmts[i] = NULL;
1362 for (i = 0; i < scop1->n_array; ++i) {
1363 scop->arrays[i] = scop1->arrays[i];
1364 scop1->arrays[i] = NULL;
1367 for (i = 0; i < scop2->n_array; ++i) {
1368 scop->arrays[scop1->n_array + i] = scop2->arrays[i];
1369 scop2->arrays[i] = NULL;
1372 scop = scop_collect_implications(ctx, scop, scop1, scop2);
1373 scop = pet_scop_restrict_context(scop, isl_set_copy(scop1->context));
1374 scop = pet_scop_restrict_context(scop, isl_set_copy(scop2->context));
1375 scop = scop_combine_skips(scop, scop1, scop2);
1376 scop = scop_combine_start_end(scop, scop1, scop2);
1378 pet_scop_free(scop1);
1379 pet_scop_free(scop2);
1380 return scop;
1381 error:
1382 pet_scop_free(scop1);
1383 pet_scop_free(scop2);
1384 pet_scop_free(scop);
1385 return NULL;
1388 /* Apply the skip condition "skip" to "scop".
1389 * That is, make sure "scop" is not executed when the condition holds.
1391 * If "skip" is an affine expression, we add the conditions under
1392 * which the expression is zero to the iteration domains.
1393 * Otherwise, we add a filter on the variable attaining the value zero.
1395 static struct pet_scop *restrict_skip(struct pet_scop *scop,
1396 __isl_take isl_multi_pw_aff *skip)
1398 isl_set *zero;
1399 isl_pw_aff *pa;
1400 int is_aff;
1402 if (!scop || !skip)
1403 goto error;
1405 is_aff = multi_pw_aff_is_affine(skip);
1406 if (is_aff < 0)
1407 goto error;
1409 if (!is_aff)
1410 return pet_scop_filter(scop, skip, 0);
1412 pa = isl_multi_pw_aff_get_pw_aff(skip, 0);
1413 isl_multi_pw_aff_free(skip);
1414 zero = isl_set_params(isl_pw_aff_zero_set(pa));
1415 scop = pet_scop_restrict(scop, zero);
1417 return scop;
1418 error:
1419 isl_multi_pw_aff_free(skip);
1420 return pet_scop_free(scop);
1423 /* Construct a pet_scop that contains the arrays, statements and
1424 * skip information in "scop1" and "scop2", where the two scops
1425 * are executed "in sequence". That is, breaks and continues
1426 * in scop1 have an effect on scop2.
1428 struct pet_scop *pet_scop_add_seq(isl_ctx *ctx, struct pet_scop *scop1,
1429 struct pet_scop *scop2)
1431 if (scop1 && pet_scop_has_skip(scop1, pet_skip_now))
1432 scop2 = restrict_skip(scop2,
1433 pet_scop_get_skip(scop1, pet_skip_now));
1434 return pet_scop_add(ctx, scop1, scop2);
1437 /* Construct a pet_scop that contains the arrays, statements and
1438 * skip information in "scop1" and "scop2", where the two scops
1439 * are executed "in parallel". That is, any break or continue
1440 * in scop1 has no effect on scop2.
1442 struct pet_scop *pet_scop_add_par(isl_ctx *ctx, struct pet_scop *scop1,
1443 struct pet_scop *scop2)
1445 return pet_scop_add(ctx, scop1, scop2);
1448 void *pet_implication_free(struct pet_implication *implication)
1450 int i;
1452 if (!implication)
1453 return NULL;
1455 isl_map_free(implication->extension);
1457 free(implication);
1458 return NULL;
1461 struct pet_scop *pet_scop_free(struct pet_scop *scop)
1463 int i;
1464 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1466 if (!scop)
1467 return NULL;
1468 isl_set_free(scop->context);
1469 isl_set_free(scop->context_value);
1470 if (scop->types)
1471 for (i = 0; i < scop->n_type; ++i)
1472 pet_type_free(scop->types[i]);
1473 free(scop->types);
1474 if (scop->arrays)
1475 for (i = 0; i < scop->n_array; ++i)
1476 pet_array_free(scop->arrays[i]);
1477 free(scop->arrays);
1478 if (scop->stmts)
1479 for (i = 0; i < scop->n_stmt; ++i)
1480 pet_stmt_free(scop->stmts[i]);
1481 free(scop->stmts);
1482 if (scop->implications)
1483 for (i = 0; i < scop->n_implication; ++i)
1484 pet_implication_free(scop->implications[i]);
1485 free(scop->implications);
1486 isl_multi_pw_aff_free(ext->skip[pet_skip_now]);
1487 isl_multi_pw_aff_free(ext->skip[pet_skip_later]);
1488 free(scop);
1489 return NULL;
1492 void pet_type_dump(struct pet_type *type)
1494 if (!type)
1495 return;
1497 fprintf(stderr, "%s -> %s\n", type->name, type->definition);
1500 void pet_implication_dump(struct pet_implication *implication)
1502 if (!implication)
1503 return;
1505 fprintf(stderr, "%d\n", implication->satisfied);
1506 isl_map_dump(implication->extension);
1509 void pet_scop_dump(struct pet_scop *scop)
1511 int i;
1512 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1514 if (!scop)
1515 return;
1517 isl_set_dump(scop->context);
1518 isl_set_dump(scop->context_value);
1519 for (i = 0; i < scop->n_type; ++i)
1520 pet_type_dump(scop->types[i]);
1521 for (i = 0; i < scop->n_array; ++i)
1522 pet_array_dump(scop->arrays[i]);
1523 for (i = 0; i < scop->n_stmt; ++i)
1524 pet_stmt_dump(scop->stmts[i]);
1525 for (i = 0; i < scop->n_implication; ++i)
1526 pet_implication_dump(scop->implications[i]);
1528 if (ext->skip[0]) {
1529 fprintf(stderr, "skip\n");
1530 isl_multi_pw_aff_dump(ext->skip[0]);
1531 isl_multi_pw_aff_dump(ext->skip[1]);
1535 /* Return 1 if the two pet_arrays are equivalent.
1537 * We don't compare element_size as this may be target dependent.
1539 int pet_array_is_equal(struct pet_array *array1, struct pet_array *array2)
1541 if (!array1 || !array2)
1542 return 0;
1544 if (!isl_set_is_equal(array1->context, array2->context))
1545 return 0;
1546 if (!isl_set_is_equal(array1->extent, array2->extent))
1547 return 0;
1548 if (!!array1->value_bounds != !!array2->value_bounds)
1549 return 0;
1550 if (array1->value_bounds &&
1551 !isl_set_is_equal(array1->value_bounds, array2->value_bounds))
1552 return 0;
1553 if (strcmp(array1->element_type, array2->element_type))
1554 return 0;
1555 if (array1->live_out != array2->live_out)
1556 return 0;
1557 if (array1->uniquely_defined != array2->uniquely_defined)
1558 return 0;
1559 if (array1->declared != array2->declared)
1560 return 0;
1561 if (array1->exposed != array2->exposed)
1562 return 0;
1564 return 1;
1567 /* Return 1 if the two pet_stmts are equivalent.
1569 int pet_stmt_is_equal(struct pet_stmt *stmt1, struct pet_stmt *stmt2)
1571 int i;
1573 if (!stmt1 || !stmt2)
1574 return 0;
1576 if (stmt1->line != stmt2->line)
1577 return 0;
1578 if (!isl_set_is_equal(stmt1->domain, stmt2->domain))
1579 return 0;
1580 if (!isl_map_is_equal(stmt1->schedule, stmt2->schedule))
1581 return 0;
1582 if (!pet_expr_is_equal(stmt1->body, stmt2->body))
1583 return 0;
1584 if (stmt1->n_arg != stmt2->n_arg)
1585 return 0;
1586 for (i = 0; i < stmt1->n_arg; ++i) {
1587 if (!pet_expr_is_equal(stmt1->args[i], stmt2->args[i]))
1588 return 0;
1591 return 1;
1594 /* Return 1 if the two pet_types are equivalent.
1596 * We only compare the names of the types since the exact representation
1597 * of the definition may depend on the version of clang being used.
1599 int pet_type_is_equal(struct pet_type *type1, struct pet_type *type2)
1601 if (!type1 || !type2)
1602 return 0;
1604 if (strcmp(type1->name, type2->name))
1605 return 0;
1607 return 1;
1610 /* Return 1 if the two pet_implications are equivalent.
1612 int pet_implication_is_equal(struct pet_implication *implication1,
1613 struct pet_implication *implication2)
1615 if (!implication1 || !implication2)
1616 return 0;
1618 if (implication1->satisfied != implication2->satisfied)
1619 return 0;
1620 if (!isl_map_is_equal(implication1->extension, implication2->extension))
1621 return 0;
1623 return 1;
1626 /* Return 1 if the two pet_scops are equivalent.
1628 int pet_scop_is_equal(struct pet_scop *scop1, struct pet_scop *scop2)
1630 int i;
1632 if (!scop1 || !scop2)
1633 return 0;
1635 if (!isl_set_is_equal(scop1->context, scop2->context))
1636 return 0;
1637 if (!isl_set_is_equal(scop1->context_value, scop2->context_value))
1638 return 0;
1640 if (scop1->n_type != scop2->n_type)
1641 return 0;
1642 for (i = 0; i < scop1->n_type; ++i)
1643 if (!pet_type_is_equal(scop1->types[i], scop2->types[i]))
1644 return 0;
1646 if (scop1->n_array != scop2->n_array)
1647 return 0;
1648 for (i = 0; i < scop1->n_array; ++i)
1649 if (!pet_array_is_equal(scop1->arrays[i], scop2->arrays[i]))
1650 return 0;
1652 if (scop1->n_stmt != scop2->n_stmt)
1653 return 0;
1654 for (i = 0; i < scop1->n_stmt; ++i)
1655 if (!pet_stmt_is_equal(scop1->stmts[i], scop2->stmts[i]))
1656 return 0;
1658 if (scop1->n_implication != scop2->n_implication)
1659 return 0;
1660 for (i = 0; i < scop1->n_implication; ++i)
1661 if (!pet_implication_is_equal(scop1->implications[i],
1662 scop2->implications[i]))
1663 return 0;
1665 return 1;
1668 /* Prefix the schedule of "stmt" with an extra dimension with constant
1669 * value "pos".
1671 struct pet_stmt *pet_stmt_prefix(struct pet_stmt *stmt, int pos)
1673 if (!stmt)
1674 return NULL;
1676 stmt->schedule = isl_map_insert_dims(stmt->schedule, isl_dim_out, 0, 1);
1677 stmt->schedule = isl_map_fix_si(stmt->schedule, isl_dim_out, 0, pos);
1678 if (!stmt->schedule)
1679 return pet_stmt_free(stmt);
1681 return stmt;
1684 /* Prefix the schedules of all statements in "scop" with an extra
1685 * dimension with constant value "pos".
1687 struct pet_scop *pet_scop_prefix(struct pet_scop *scop, int pos)
1689 int i;
1691 if (!scop)
1692 return NULL;
1694 for (i = 0; i < scop->n_stmt; ++i) {
1695 scop->stmts[i] = pet_stmt_prefix(scop->stmts[i], pos);
1696 if (!scop->stmts[i])
1697 return pet_scop_free(scop);
1700 return scop;
1703 /* Given a set with a parameter at "param_pos" that refers to the
1704 * iterator, "move" the iterator to the first set dimension.
1705 * That is, essentially equate the parameter to the first set dimension
1706 * and then project it out.
1708 * The first set dimension may however refer to a virtual iterator,
1709 * while the parameter refers to the "real" iterator.
1710 * We therefore need to take into account the affine expression "iv_map", which
1711 * expresses the real iterator in terms of the virtual iterator.
1712 * In particular, we equate the set dimension to the input of the map
1713 * and the parameter to the output of the map and then project out
1714 * everything we don't need anymore.
1716 static __isl_give isl_set *internalize_iv(__isl_take isl_set *set,
1717 int param_pos, __isl_take isl_aff *iv_map)
1719 isl_map *map, *map2;
1720 map = isl_map_from_domain(set);
1721 map = isl_map_add_dims(map, isl_dim_out, 1);
1722 map = isl_map_equate(map, isl_dim_in, 0, isl_dim_out, 0);
1723 map2 = isl_map_from_aff(iv_map);
1724 map2 = isl_map_align_params(map2, isl_map_get_space(map));
1725 map = isl_map_apply_range(map, map2);
1726 map = isl_map_equate(map, isl_dim_param, param_pos, isl_dim_out, 0);
1727 map = isl_map_project_out(map, isl_dim_param, param_pos, 1);
1728 return isl_map_domain(map);
1731 /* Data used in embed_access.
1732 * extend adds an iterator to the iteration domain (through precomposition).
1733 * iv_map expresses the real iterator in terms of the virtual iterator
1734 * var_id represents the induction variable of the corresponding loop
1736 struct pet_embed_access {
1737 isl_multi_pw_aff *extend;
1738 isl_aff *iv_map;
1739 isl_id *var_id;
1742 /* Given an index expression, return an expression for the outer iterator.
1744 static __isl_give isl_aff *index_outer_iterator(
1745 __isl_take isl_multi_pw_aff *index)
1747 isl_space *space;
1748 isl_local_space *ls;
1750 space = isl_multi_pw_aff_get_domain_space(index);
1751 isl_multi_pw_aff_free(index);
1753 ls = isl_local_space_from_space(space);
1754 return isl_aff_var_on_domain(ls, isl_dim_set, 0);
1757 /* Replace an index expression that references the new (outer) iterator variable
1758 * by one that references the corresponding (real) iterator.
1760 * The input index expression is of the form
1762 * { S[i',...] -> i[] }
1764 * where i' refers to the virtual iterator.
1766 * iv_map is of the form
1768 * { [i'] -> [i] }
1770 * Return the index expression
1772 * { S[i',...] -> [i] }
1774 static __isl_give isl_multi_pw_aff *replace_by_iterator(
1775 __isl_take isl_multi_pw_aff *index, __isl_take isl_aff *iv_map)
1777 isl_space *space;
1778 isl_aff *aff;
1780 aff = index_outer_iterator(index);
1781 space = isl_aff_get_space(aff);
1782 iv_map = isl_aff_align_params(iv_map, space);
1783 aff = isl_aff_pullback_aff(iv_map, aff);
1785 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
1788 /* Given an index expression "index" that refers to the (real) iterator
1789 * through the parameter at position "pos", plug in "iv_map", expressing
1790 * the real iterator in terms of the virtual (outer) iterator.
1792 * In particular, the index expression is of the form
1794 * [..., i, ...] -> { S[i',...] -> ... i ... }
1796 * where i refers to the real iterator and i' refers to the virtual iterator.
1798 * iv_map is of the form
1800 * { [i'] -> [i] }
1802 * Return the index expression
1804 * [..., ...] -> { S[i',...] -> ... iv_map(i') ... }
1807 * We first move the parameter to the input
1809 * [..., ...] -> { [i, i',...] -> ... i ... }
1811 * and construct
1813 * { S[i',...] -> [i=iv_map(i'), i', ...] }
1815 * and then combine the two to obtain the desired result.
1817 static __isl_give isl_multi_pw_aff *index_internalize_iv(
1818 __isl_take isl_multi_pw_aff *index, int pos, __isl_take isl_aff *iv_map)
1820 isl_space *space = isl_multi_pw_aff_get_domain_space(index);
1821 isl_multi_aff *ma;
1823 space = isl_space_drop_dims(space, isl_dim_param, pos, 1);
1824 index = isl_multi_pw_aff_move_dims(index, isl_dim_in, 0,
1825 isl_dim_param, pos, 1);
1827 space = isl_space_map_from_set(space);
1828 ma = isl_multi_aff_identity(isl_space_copy(space));
1829 iv_map = isl_aff_align_params(iv_map, space);
1830 iv_map = isl_aff_pullback_aff(iv_map, isl_multi_aff_get_aff(ma, 0));
1831 ma = isl_multi_aff_flat_range_product(
1832 isl_multi_aff_from_aff(iv_map), ma);
1833 index = isl_multi_pw_aff_pullback_multi_aff(index, ma);
1835 return index;
1838 /* Does the index expression "index" reference a virtual array, i.e.,
1839 * one with user pointer equal to NULL?
1841 static int index_is_virtual_array(__isl_keep isl_multi_pw_aff *index)
1843 isl_id *id;
1844 int is_virtual;
1846 if (!isl_multi_pw_aff_has_tuple_id(index, isl_dim_out))
1847 return 0;
1848 id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
1849 is_virtual = !isl_id_get_user(id);
1850 isl_id_free(id);
1852 return is_virtual;
1855 /* Does the access relation "access" reference a virtual array, i.e.,
1856 * one with user pointer equal to NULL?
1858 static int access_is_virtual_array(__isl_keep isl_map *access)
1860 isl_id *id;
1861 int is_virtual;
1863 if (!isl_map_has_tuple_id(access, isl_dim_out))
1864 return 0;
1865 id = isl_map_get_tuple_id(access, isl_dim_out);
1866 is_virtual = !isl_id_get_user(id);
1867 isl_id_free(id);
1869 return is_virtual;
1872 /* Embed the given index expression in an extra outer loop.
1873 * The domain of the index expression has already been updated.
1875 * If the access refers to the induction variable, then it is
1876 * turned into an access to the set of integers with index (and value)
1877 * equal to the induction variable.
1879 * If the accessed array is a virtual array (with user
1880 * pointer equal to NULL), as created by create_test_index,
1881 * then it is extended along with the domain of the index expression.
1883 static __isl_give isl_multi_pw_aff *embed_index_expression(
1884 __isl_take isl_multi_pw_aff *index, struct pet_embed_access *data)
1886 isl_id *array_id = NULL;
1887 int pos;
1889 if (isl_multi_pw_aff_has_tuple_id(index, isl_dim_out))
1890 array_id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
1891 if (array_id == data->var_id) {
1892 index = replace_by_iterator(index, isl_aff_copy(data->iv_map));
1893 } else if (index_is_virtual_array(index)) {
1894 isl_aff *aff;
1895 isl_multi_pw_aff *mpa;
1897 aff = index_outer_iterator(isl_multi_pw_aff_copy(index));
1898 mpa = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
1899 index = isl_multi_pw_aff_flat_range_product(mpa, index);
1900 index = isl_multi_pw_aff_set_tuple_id(index, isl_dim_out,
1901 isl_id_copy(array_id));
1903 isl_id_free(array_id);
1905 pos = isl_multi_pw_aff_find_dim_by_id(index,
1906 isl_dim_param, data->var_id);
1907 if (pos >= 0)
1908 index = index_internalize_iv(index, pos,
1909 isl_aff_copy(data->iv_map));
1910 index = isl_multi_pw_aff_set_dim_id(index, isl_dim_in, 0,
1911 isl_id_copy(data->var_id));
1913 return index;
1916 /* Embed the given access relation in an extra outer loop.
1917 * The domain of the access relation has already been updated.
1919 * If the access refers to the induction variable, then it is
1920 * turned into an access to the set of integers with index (and value)
1921 * equal to the induction variable.
1923 * If the induction variable appears in the constraints (as a parameter),
1924 * then the parameter is equated to the newly introduced iteration
1925 * domain dimension and subsequently projected out.
1927 * Similarly, if the accessed array is a virtual array (with user
1928 * pointer equal to NULL), as created by create_test_index,
1929 * then it is extended along with the domain of the access.
1931 static __isl_give isl_map *embed_access_relation(__isl_take isl_map *access,
1932 struct pet_embed_access *data)
1934 isl_id *array_id = NULL;
1935 int pos;
1937 if (isl_map_has_tuple_id(access, isl_dim_out))
1938 array_id = isl_map_get_tuple_id(access, isl_dim_out);
1939 if (array_id == data->var_id || access_is_virtual_array(access)) {
1940 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
1941 access = isl_map_equate(access,
1942 isl_dim_in, 0, isl_dim_out, 0);
1943 if (array_id == data->var_id)
1944 access = isl_map_apply_range(access,
1945 isl_map_from_aff(isl_aff_copy(data->iv_map)));
1946 else
1947 access = isl_map_set_tuple_id(access, isl_dim_out,
1948 isl_id_copy(array_id));
1950 isl_id_free(array_id);
1952 pos = isl_map_find_dim_by_id(access, isl_dim_param, data->var_id);
1953 if (pos >= 0) {
1954 isl_set *set = isl_map_wrap(access);
1955 set = internalize_iv(set, pos, isl_aff_copy(data->iv_map));
1956 access = isl_set_unwrap(set);
1958 access = isl_map_set_dim_id(access, isl_dim_in, 0,
1959 isl_id_copy(data->var_id));
1961 return access;
1964 /* Given an access expression, embed the associated access relation and
1965 * index expression in an extra outer loop.
1967 * We first update the domains to insert the extra dimension and
1968 * then update the access relation and index expression to take
1969 * into account the mapping "iv_map" from virtual iterator
1970 * to real iterator.
1972 static struct pet_expr *embed_access(struct pet_expr *expr, void *user)
1974 int dim;
1975 struct pet_embed_access *data = user;
1977 expr = update_domain(expr, data->extend);
1978 if (!expr)
1979 return NULL;
1981 expr->acc.access = embed_access_relation(expr->acc.access, data);
1982 expr->acc.index = embed_index_expression(expr->acc.index, data);
1983 if (!expr->acc.access || !expr->acc.index)
1984 return pet_expr_free(expr);
1986 return expr;
1989 /* Embed all access subexpressions of "expr" in an extra loop.
1990 * "extend" inserts an outer loop iterator in the iteration domains
1991 * (through precomposition).
1992 * "iv_map" expresses the real iterator in terms of the virtual iterator
1993 * "var_id" represents the induction variable.
1995 static struct pet_expr *expr_embed(struct pet_expr *expr,
1996 __isl_take isl_multi_pw_aff *extend, __isl_take isl_aff *iv_map,
1997 __isl_keep isl_id *var_id)
1999 struct pet_embed_access data =
2000 { .extend = extend, .iv_map = iv_map, .var_id = var_id };
2002 expr = pet_expr_map_access(expr, &embed_access, &data);
2003 isl_aff_free(iv_map);
2004 isl_multi_pw_aff_free(extend);
2005 return expr;
2008 /* Embed the given pet_stmt in an extra outer loop with iteration domain
2009 * "dom" and schedule "sched". "var_id" represents the induction variable
2010 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
2011 * That is, it expresses the iterator that some of the parameters in "stmt"
2012 * may refer to in terms of the iterator used in "dom" and
2013 * the domain of "sched".
2015 * The iteration domain and schedule of the statement are updated
2016 * according to the iteration domain and schedule of the new loop.
2017 * If stmt->domain is a wrapped map, then the iteration domain
2018 * is the domain of this map, so we need to be careful to adjust
2019 * this domain.
2021 * If the induction variable appears in the constraints (as a parameter)
2022 * of the current iteration domain or the schedule of the statement,
2023 * then the parameter is equated to the newly introduced iteration
2024 * domain dimension and subsequently projected out.
2026 * Finally, all access relations are updated based on the extra loop.
2028 static struct pet_stmt *pet_stmt_embed(struct pet_stmt *stmt,
2029 __isl_take isl_set *dom, __isl_take isl_map *sched,
2030 __isl_take isl_aff *iv_map, __isl_take isl_id *var_id)
2032 int i;
2033 int pos;
2034 isl_id *stmt_id;
2035 isl_space *dim;
2036 isl_multi_pw_aff *extend;
2038 if (!stmt)
2039 goto error;
2041 if (isl_set_is_wrapping(stmt->domain)) {
2042 isl_map *map;
2043 isl_map *ext;
2044 isl_space *ran_dim;
2046 map = isl_set_unwrap(stmt->domain);
2047 stmt_id = isl_map_get_tuple_id(map, isl_dim_in);
2048 ran_dim = isl_space_range(isl_map_get_space(map));
2049 ext = isl_map_from_domain_and_range(isl_set_copy(dom),
2050 isl_set_universe(ran_dim));
2051 map = isl_map_flat_domain_product(ext, map);
2052 map = isl_map_set_tuple_id(map, isl_dim_in,
2053 isl_id_copy(stmt_id));
2054 dim = isl_space_domain(isl_map_get_space(map));
2055 stmt->domain = isl_map_wrap(map);
2056 } else {
2057 stmt_id = isl_set_get_tuple_id(stmt->domain);
2058 stmt->domain = isl_set_flat_product(isl_set_copy(dom),
2059 stmt->domain);
2060 stmt->domain = isl_set_set_tuple_id(stmt->domain,
2061 isl_id_copy(stmt_id));
2062 dim = isl_set_get_space(stmt->domain);
2065 pos = isl_set_find_dim_by_id(stmt->domain, isl_dim_param, var_id);
2066 if (pos >= 0)
2067 stmt->domain = internalize_iv(stmt->domain, pos,
2068 isl_aff_copy(iv_map));
2070 stmt->schedule = isl_map_flat_product(sched, stmt->schedule);
2071 stmt->schedule = isl_map_set_tuple_id(stmt->schedule,
2072 isl_dim_in, stmt_id);
2074 pos = isl_map_find_dim_by_id(stmt->schedule, isl_dim_param, var_id);
2075 if (pos >= 0) {
2076 isl_set *set = isl_map_wrap(stmt->schedule);
2077 set = internalize_iv(set, pos, isl_aff_copy(iv_map));
2078 stmt->schedule = isl_set_unwrap(set);
2081 dim = isl_space_map_from_set(dim);
2082 extend = isl_multi_pw_aff_identity(dim);
2083 extend = isl_multi_pw_aff_drop_dims(extend, isl_dim_out, 0, 1);
2084 extend = isl_multi_pw_aff_set_tuple_id(extend, isl_dim_out,
2085 isl_multi_pw_aff_get_tuple_id(extend, isl_dim_in));
2086 for (i = 0; i < stmt->n_arg; ++i)
2087 stmt->args[i] = expr_embed(stmt->args[i],
2088 isl_multi_pw_aff_copy(extend),
2089 isl_aff_copy(iv_map), var_id);
2090 stmt->body = expr_embed(stmt->body, extend, iv_map, var_id);
2092 isl_set_free(dom);
2093 isl_id_free(var_id);
2095 for (i = 0; i < stmt->n_arg; ++i)
2096 if (!stmt->args[i])
2097 return pet_stmt_free(stmt);
2098 if (!stmt->domain || !stmt->schedule || !stmt->body)
2099 return pet_stmt_free(stmt);
2100 return stmt;
2101 error:
2102 isl_set_free(dom);
2103 isl_map_free(sched);
2104 isl_aff_free(iv_map);
2105 isl_id_free(var_id);
2106 return NULL;
2109 /* Embed the given pet_array in an extra outer loop with iteration domain
2110 * "dom".
2111 * This embedding only has an effect on virtual arrays (those with
2112 * user pointer equal to NULL), which need to be extended along with
2113 * the iteration domain.
2115 static struct pet_array *pet_array_embed(struct pet_array *array,
2116 __isl_take isl_set *dom)
2118 isl_id *array_id = NULL;
2120 if (!array)
2121 goto error;
2123 if (isl_set_has_tuple_id(array->extent))
2124 array_id = isl_set_get_tuple_id(array->extent);
2126 if (array_id && !isl_id_get_user(array_id)) {
2127 array->extent = isl_set_flat_product(dom, array->extent);
2128 array->extent = isl_set_set_tuple_id(array->extent, array_id);
2129 if (!array->extent)
2130 return pet_array_free(array);
2131 } else {
2132 isl_set_free(dom);
2133 isl_id_free(array_id);
2136 return array;
2137 error:
2138 isl_set_free(dom);
2139 return NULL;
2142 /* Project out all unnamed parameters from "set" and return the result.
2144 static __isl_give isl_set *set_project_out_unnamed_params(
2145 __isl_take isl_set *set)
2147 int i, n;
2149 n = isl_set_dim(set, isl_dim_param);
2150 for (i = n - 1; i >= 0; --i) {
2151 if (isl_set_has_dim_name(set, isl_dim_param, i))
2152 continue;
2153 set = isl_set_project_out(set, isl_dim_param, i, 1);
2156 return set;
2159 /* Update the context with respect to an embedding into a loop
2160 * with iteration domain "dom" and induction variable "id".
2161 * "iv_map" expresses the real iterator (parameter "id") in terms
2162 * of a possibly virtual iterator (used in "dom").
2164 * If the current context is independent of "id", we don't need
2165 * to do anything.
2166 * Otherwise, a parameter value is invalid for the embedding if
2167 * any of the corresponding iterator values is invalid.
2168 * That is, a parameter value is valid only if all the corresponding
2169 * iterator values are valid.
2170 * We therefore compute the set of parameters
2172 * forall i in dom : valid (i)
2174 * or
2176 * not exists i in dom : not valid(i)
2178 * i.e.,
2180 * not exists i in dom \ valid(i)
2182 * Before we subtract valid(i) from dom, we first need to substitute
2183 * the real iterator for the virtual iterator.
2185 * If there are any unnamed parameters in "dom", then we consider
2186 * a parameter value to be valid if it is valid for any value of those
2187 * unnamed parameters. They are therefore projected out at the end.
2189 static __isl_give isl_set *context_embed(__isl_take isl_set *context,
2190 __isl_keep isl_set *dom, __isl_keep isl_aff *iv_map,
2191 __isl_keep isl_id *id)
2193 int pos;
2194 isl_multi_aff *ma;
2196 pos = isl_set_find_dim_by_id(context, isl_dim_param, id);
2197 if (pos < 0)
2198 return context;
2200 context = isl_set_from_params(context);
2201 context = isl_set_add_dims(context, isl_dim_set, 1);
2202 context = isl_set_equate(context, isl_dim_param, pos, isl_dim_set, 0);
2203 context = isl_set_project_out(context, isl_dim_param, pos, 1);
2204 ma = isl_multi_aff_from_aff(isl_aff_copy(iv_map));
2205 context = isl_set_preimage_multi_aff(context, ma);
2206 context = isl_set_subtract(isl_set_copy(dom), context);
2207 context = isl_set_params(context);
2208 context = isl_set_complement(context);
2209 context = set_project_out_unnamed_params(context);
2210 return context;
2213 /* Update the implication with respect to an embedding into a loop
2214 * with iteration domain "dom".
2216 * Since embed_access extends virtual arrays along with the domain
2217 * of the access, we need to do the same with domain and range
2218 * of the implication. Since the original implication is only valid
2219 * within a given iteration of the loop, the extended implication
2220 * maps the extra array dimension corresponding to the extra loop
2221 * to itself.
2223 static struct pet_implication *pet_implication_embed(
2224 struct pet_implication *implication, __isl_take isl_set *dom)
2226 isl_id *id;
2227 isl_map *map;
2229 if (!implication)
2230 goto error;
2232 map = isl_set_identity(dom);
2233 id = isl_map_get_tuple_id(implication->extension, isl_dim_in);
2234 map = isl_map_flat_product(map, implication->extension);
2235 map = isl_map_set_tuple_id(map, isl_dim_in, isl_id_copy(id));
2236 map = isl_map_set_tuple_id(map, isl_dim_out, id);
2237 implication->extension = map;
2238 if (!implication->extension)
2239 return pet_implication_free(implication);
2241 return implication;
2242 error:
2243 isl_set_free(dom);
2244 return NULL;
2247 /* Embed all statements and arrays in "scop" in an extra outer loop
2248 * with iteration domain "dom" and schedule "sched".
2249 * "id" represents the induction variable of the loop.
2250 * "iv_map" maps a possibly virtual iterator to the real iterator.
2251 * That is, it expresses the iterator that some of the parameters in "scop"
2252 * may refer to in terms of the iterator used in "dom" and
2253 * the domain of "sched".
2255 * Any skip conditions within the loop have no effect outside of the loop.
2256 * The caller is responsible for making sure skip[pet_skip_later] has been
2257 * taken into account.
2259 struct pet_scop *pet_scop_embed(struct pet_scop *scop, __isl_take isl_set *dom,
2260 __isl_take isl_map *sched, __isl_take isl_aff *iv_map,
2261 __isl_take isl_id *id)
2263 int i;
2265 if (!scop)
2266 goto error;
2268 pet_scop_reset_skip(scop, pet_skip_now);
2269 pet_scop_reset_skip(scop, pet_skip_later);
2271 scop->context = context_embed(scop->context, dom, iv_map, id);
2272 if (!scop->context)
2273 goto error;
2275 for (i = 0; i < scop->n_stmt; ++i) {
2276 scop->stmts[i] = pet_stmt_embed(scop->stmts[i],
2277 isl_set_copy(dom), isl_map_copy(sched),
2278 isl_aff_copy(iv_map), isl_id_copy(id));
2279 if (!scop->stmts[i])
2280 goto error;
2283 for (i = 0; i < scop->n_array; ++i) {
2284 scop->arrays[i] = pet_array_embed(scop->arrays[i],
2285 isl_set_copy(dom));
2286 if (!scop->arrays[i])
2287 goto error;
2290 for (i = 0; i < scop->n_implication; ++i) {
2291 scop->implications[i] =
2292 pet_implication_embed(scop->implications[i],
2293 isl_set_copy(dom));
2294 if (!scop->implications[i])
2295 goto error;
2298 isl_set_free(dom);
2299 isl_map_free(sched);
2300 isl_aff_free(iv_map);
2301 isl_id_free(id);
2302 return scop;
2303 error:
2304 isl_set_free(dom);
2305 isl_map_free(sched);
2306 isl_aff_free(iv_map);
2307 isl_id_free(id);
2308 return pet_scop_free(scop);
2311 /* Add extra conditions on the parameters to iteration domain of "stmt".
2313 static struct pet_stmt *stmt_restrict(struct pet_stmt *stmt,
2314 __isl_take isl_set *cond)
2316 if (!stmt)
2317 goto error;
2319 stmt->domain = isl_set_intersect_params(stmt->domain, cond);
2321 return stmt;
2322 error:
2323 isl_set_free(cond);
2324 return pet_stmt_free(stmt);
2327 /* Add extra conditions to scop->skip[type].
2329 * The new skip condition only holds if it held before
2330 * and the condition is true. It does not hold if it did not hold
2331 * before or the condition is false.
2333 * The skip condition is assumed to be an affine expression.
2335 static struct pet_scop *pet_scop_restrict_skip(struct pet_scop *scop,
2336 enum pet_skip type, __isl_keep isl_set *cond)
2338 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2339 isl_pw_aff *skip;
2340 isl_set *dom;
2342 if (!scop)
2343 return NULL;
2344 if (!ext->skip[type])
2345 return scop;
2347 if (!multi_pw_aff_is_affine(ext->skip[type]))
2348 isl_die(isl_multi_pw_aff_get_ctx(ext->skip[type]),
2349 isl_error_internal, "can only resrict affine skips",
2350 return pet_scop_free(scop));
2352 skip = isl_multi_pw_aff_get_pw_aff(ext->skip[type], 0);
2353 dom = isl_pw_aff_domain(isl_pw_aff_copy(skip));
2354 cond = isl_set_copy(cond);
2355 cond = isl_set_from_params(cond);
2356 cond = isl_set_intersect(cond, isl_pw_aff_non_zero_set(skip));
2357 skip = indicator_function(cond, dom);
2358 isl_multi_pw_aff_free(ext->skip[type]);
2359 ext->skip[type] = isl_multi_pw_aff_from_pw_aff(skip);
2360 if (!ext->skip[type])
2361 return pet_scop_free(scop);
2363 return scop;
2366 /* Add extra conditions on the parameters to all iteration domains
2367 * and skip conditions.
2369 * A parameter value is valid for the result if it was valid
2370 * for the original scop and satisfies "cond" or if it does
2371 * not satisfy "cond" as in this case the scop is not executed
2372 * and the original constraints on the parameters are irrelevant.
2374 struct pet_scop *pet_scop_restrict(struct pet_scop *scop,
2375 __isl_take isl_set *cond)
2377 int i;
2379 scop = pet_scop_restrict_skip(scop, pet_skip_now, cond);
2380 scop = pet_scop_restrict_skip(scop, pet_skip_later, cond);
2382 if (!scop)
2383 goto error;
2385 scop->context = isl_set_intersect(scop->context, isl_set_copy(cond));
2386 scop->context = isl_set_union(scop->context,
2387 isl_set_complement(isl_set_copy(cond)));
2388 scop->context = isl_set_coalesce(scop->context);
2389 scop->context = set_project_out_unnamed_params(scop->context);
2390 if (!scop->context)
2391 goto error;
2393 for (i = 0; i < scop->n_stmt; ++i) {
2394 scop->stmts[i] = stmt_restrict(scop->stmts[i],
2395 isl_set_copy(cond));
2396 if (!scop->stmts[i])
2397 goto error;
2400 isl_set_free(cond);
2401 return scop;
2402 error:
2403 isl_set_free(cond);
2404 return pet_scop_free(scop);
2407 /* Construct a function that (upon precomposition) inserts
2408 * a filter value with name "id" and value "satisfied"
2409 * in the list of filter values embedded in the set space "space".
2411 * If "space" does not contain any filter values yet, we first create
2412 * a function that inserts 0 filter values, i.e.,
2414 * [space -> []] -> space
2416 * We can now assume that space is of the form [dom -> [filters]]
2417 * We construct an identity mapping on dom and a mapping on filters
2418 * that (upon precomposition) inserts the new filter
2420 * dom -> dom
2421 * [satisfied, filters] -> [filters]
2423 * and then compute the cross product
2425 * [dom -> [satisfied, filters]] -> [dom -> [filters]]
2427 static __isl_give isl_pw_multi_aff *insert_filter_pma(
2428 __isl_take isl_space *space, __isl_take isl_id *id, int satisfied)
2430 isl_space *space2;
2431 isl_multi_aff *ma;
2432 isl_pw_multi_aff *pma0, *pma, *pma_dom, *pma_ran;
2433 isl_set *dom;
2435 if (isl_space_is_wrapping(space)) {
2436 space2 = isl_space_map_from_set(isl_space_copy(space));
2437 ma = isl_multi_aff_identity(space2);
2438 space = isl_space_unwrap(space);
2439 } else {
2440 space = isl_space_from_domain(space);
2441 ma = isl_multi_aff_domain_map(isl_space_copy(space));
2444 space2 = isl_space_domain(isl_space_copy(space));
2445 pma_dom = isl_pw_multi_aff_identity(isl_space_map_from_set(space2));
2446 space = isl_space_range(space);
2447 space = isl_space_insert_dims(space, isl_dim_set, 0, 1);
2448 pma_ran = isl_pw_multi_aff_project_out_map(space, isl_dim_set, 0, 1);
2449 pma_ran = isl_pw_multi_aff_set_dim_id(pma_ran, isl_dim_in, 0, id);
2450 pma_ran = isl_pw_multi_aff_fix_si(pma_ran, isl_dim_in, 0, satisfied);
2451 pma = isl_pw_multi_aff_product(pma_dom, pma_ran);
2453 pma0 = isl_pw_multi_aff_from_multi_aff(ma);
2454 pma = isl_pw_multi_aff_pullback_pw_multi_aff(pma0, pma);
2456 return pma;
2459 /* Insert an argument expression corresponding to "test" in front
2460 * of the list of arguments described by *n_arg and *args.
2462 static int args_insert_access(unsigned *n_arg, struct pet_expr ***args,
2463 __isl_keep isl_multi_pw_aff *test)
2465 int i;
2466 isl_ctx *ctx = isl_multi_pw_aff_get_ctx(test);
2468 if (!test)
2469 return -1;
2471 if (!*args) {
2472 *args = isl_calloc_array(ctx, struct pet_expr *, 1);
2473 if (!*args)
2474 return -1;
2475 } else {
2476 struct pet_expr **ext;
2477 ext = isl_calloc_array(ctx, struct pet_expr *, 1 + *n_arg);
2478 if (!ext)
2479 return -1;
2480 for (i = 0; i < *n_arg; ++i)
2481 ext[1 + i] = (*args)[i];
2482 free(*args);
2483 *args = ext;
2485 (*n_arg)++;
2486 (*args)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test));
2487 if (!(*args)[0])
2488 return -1;
2490 return 0;
2493 /* Make the expression "expr" depend on the value of "test"
2494 * being equal to "satisfied".
2496 * If "test" is an affine expression, we simply add the conditions
2497 * on the expression having the value "satisfied" to all access relations
2498 * and index expressions.
2500 * Otherwise, we add a filter to "expr" (which is then assumed to be
2501 * an access expression) corresponding to "test" being equal to "satisfied".
2503 struct pet_expr *pet_expr_filter(struct pet_expr *expr,
2504 __isl_take isl_multi_pw_aff *test, int satisfied)
2506 isl_id *id;
2507 isl_ctx *ctx;
2508 isl_space *space;
2509 isl_pw_multi_aff *pma;
2511 if (!expr || !test)
2512 goto error;
2514 if (!isl_multi_pw_aff_has_tuple_id(test, isl_dim_out)) {
2515 isl_pw_aff *pa;
2516 isl_set *cond;
2518 pa = isl_multi_pw_aff_get_pw_aff(test, 0);
2519 isl_multi_pw_aff_free(test);
2520 if (satisfied)
2521 cond = isl_pw_aff_non_zero_set(pa);
2522 else
2523 cond = isl_pw_aff_zero_set(pa);
2524 return pet_expr_restrict(expr, isl_set_params(cond));
2527 ctx = isl_multi_pw_aff_get_ctx(test);
2528 if (expr->type != pet_expr_access)
2529 isl_die(ctx, isl_error_invalid,
2530 "can only filter access expressions", goto error);
2532 space = isl_space_domain(isl_map_get_space(expr->acc.access));
2533 id = isl_multi_pw_aff_get_tuple_id(test, isl_dim_out);
2534 pma = insert_filter_pma(space, id, satisfied);
2536 expr->acc.access = isl_map_preimage_domain_pw_multi_aff(
2537 expr->acc.access,
2538 isl_pw_multi_aff_copy(pma));
2539 expr->acc.index = isl_multi_pw_aff_pullback_pw_multi_aff(
2540 expr->acc.index, pma);
2541 if (!expr->acc.access || !expr->acc.index)
2542 goto error;
2544 if (args_insert_access(&expr->n_arg, &expr->args, test) < 0)
2545 goto error;
2547 isl_multi_pw_aff_free(test);
2548 return expr;
2549 error:
2550 isl_multi_pw_aff_free(test);
2551 return pet_expr_free(expr);
2554 /* Look through the applications in "scop" for any that can be
2555 * applied to the filter expressed by "map" and "satisified".
2556 * If there is any, then apply it to "map" and return the result.
2557 * Otherwise, return "map".
2558 * "id" is the identifier of the virtual array.
2560 * We only introduce at most one implication for any given virtual array,
2561 * so we can apply the implication and return as soon as we find one.
2563 static __isl_give isl_map *apply_implications(struct pet_scop *scop,
2564 __isl_take isl_map *map, __isl_keep isl_id *id, int satisfied)
2566 int i;
2568 for (i = 0; i < scop->n_implication; ++i) {
2569 struct pet_implication *pi = scop->implications[i];
2570 isl_id *pi_id;
2572 if (pi->satisfied != satisfied)
2573 continue;
2574 pi_id = isl_map_get_tuple_id(pi->extension, isl_dim_in);
2575 isl_id_free(pi_id);
2576 if (pi_id != id)
2577 continue;
2579 return isl_map_apply_range(map, isl_map_copy(pi->extension));
2582 return map;
2585 /* Is the filter expressed by "test" and "satisfied" implied
2586 * by filter "pos" on "domain", with filter "expr", taking into
2587 * account the implications of "scop"?
2589 * For filter on domain implying that expressed by "test" and "satisfied",
2590 * the filter needs to be an access to the same (virtual) array as "test" and
2591 * the filter value needs to be equal to "satisfied".
2592 * Moreover, the filter access relation, possibly extended by
2593 * the implications in "scop" needs to contain "test".
2595 static int implies_filter(struct pet_scop *scop,
2596 __isl_keep isl_map *domain, int pos, struct pet_expr *expr,
2597 __isl_keep isl_map *test, int satisfied)
2599 isl_id *test_id, *arg_id;
2600 isl_val *val;
2601 int is_int;
2602 int s;
2603 int is_subset;
2604 isl_map *implied;
2606 if (expr->type != pet_expr_access)
2607 return 0;
2608 test_id = isl_map_get_tuple_id(test, isl_dim_out);
2609 arg_id = pet_expr_access_get_id(expr);
2610 isl_id_free(arg_id);
2611 isl_id_free(test_id);
2612 if (test_id != arg_id)
2613 return 0;
2614 val = isl_map_plain_get_val_if_fixed(domain, isl_dim_out, pos);
2615 is_int = isl_val_is_int(val);
2616 if (is_int)
2617 s = isl_val_get_num_si(val);
2618 isl_val_free(val);
2619 if (!val)
2620 return -1;
2621 if (!is_int)
2622 return 0;
2623 if (s != satisfied)
2624 return 0;
2626 implied = isl_map_copy(expr->acc.access);
2627 implied = apply_implications(scop, implied, test_id, satisfied);
2628 is_subset = isl_map_is_subset(test, implied);
2629 isl_map_free(implied);
2631 return is_subset;
2634 /* Is the filter expressed by "test" and "satisfied" implied
2635 * by any of the filters on the domain of "stmt", taking into
2636 * account the implications of "scop"?
2638 static int filter_implied(struct pet_scop *scop,
2639 struct pet_stmt *stmt, __isl_keep isl_multi_pw_aff *test, int satisfied)
2641 int i;
2642 int implied;
2643 isl_id *test_id;
2644 isl_map *domain;
2645 isl_map *test_map;
2647 if (!scop || !stmt || !test)
2648 return -1;
2649 if (scop->n_implication == 0)
2650 return 0;
2651 if (stmt->n_arg == 0)
2652 return 0;
2654 domain = isl_set_unwrap(isl_set_copy(stmt->domain));
2655 test_map = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test));
2657 implied = 0;
2658 for (i = 0; i < stmt->n_arg; ++i) {
2659 implied = implies_filter(scop, domain, i, stmt->args[i],
2660 test_map, satisfied);
2661 if (implied < 0 || implied)
2662 break;
2665 isl_map_free(test_map);
2666 isl_map_free(domain);
2667 return implied;
2670 /* Make the statement "stmt" depend on the value of "test"
2671 * being equal to "satisfied" by adjusting stmt->domain.
2673 * The domain of "test" corresponds to the (zero or more) outer dimensions
2674 * of the iteration domain.
2676 * We first extend "test" to apply to the entire iteration domain and
2677 * then check if the filter that we are about to add is implied
2678 * by any of the current filters, possibly taking into account
2679 * the implications in "scop". If so, we leave "stmt" untouched and return.
2681 * Otherwise, we insert an argument corresponding to a read to "test"
2682 * from the iteration domain of "stmt" in front of the list of arguments.
2683 * We also insert a corresponding output dimension in the wrapped
2684 * map contained in stmt->domain, with value set to "satisfied".
2686 static struct pet_stmt *stmt_filter(struct pet_scop *scop,
2687 struct pet_stmt *stmt, __isl_take isl_multi_pw_aff *test, int satisfied)
2689 int i;
2690 int implied;
2691 isl_id *id;
2692 isl_ctx *ctx;
2693 isl_pw_multi_aff *pma;
2694 isl_multi_aff *add_dom;
2695 isl_space *space;
2696 isl_local_space *ls;
2697 int n_test_dom;
2699 if (!stmt || !test)
2700 goto error;
2702 space = isl_set_get_space(stmt->domain);
2703 if (isl_space_is_wrapping(space))
2704 space = isl_space_domain(isl_space_unwrap(space));
2705 n_test_dom = isl_multi_pw_aff_dim(test, isl_dim_in);
2706 space = isl_space_from_domain(space);
2707 space = isl_space_add_dims(space, isl_dim_out, n_test_dom);
2708 add_dom = isl_multi_aff_zero(isl_space_copy(space));
2709 ls = isl_local_space_from_space(isl_space_domain(space));
2710 for (i = 0; i < n_test_dom; ++i) {
2711 isl_aff *aff;
2712 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
2713 isl_dim_set, i);
2714 add_dom = isl_multi_aff_set_aff(add_dom, i, aff);
2716 isl_local_space_free(ls);
2717 test = isl_multi_pw_aff_pullback_multi_aff(test, add_dom);
2719 implied = filter_implied(scop, stmt, test, satisfied);
2720 if (implied < 0)
2721 goto error;
2722 if (implied) {
2723 isl_multi_pw_aff_free(test);
2724 return stmt;
2727 id = isl_multi_pw_aff_get_tuple_id(test, isl_dim_out);
2728 pma = insert_filter_pma(isl_set_get_space(stmt->domain), id, satisfied);
2729 stmt->domain = isl_set_preimage_pw_multi_aff(stmt->domain, pma);
2731 if (args_insert_access(&stmt->n_arg, &stmt->args, test) < 0)
2732 goto error;
2734 isl_multi_pw_aff_free(test);
2735 return stmt;
2736 error:
2737 isl_multi_pw_aff_free(test);
2738 return pet_stmt_free(stmt);
2741 /* Does "scop" have a skip condition of the given "type"?
2743 int pet_scop_has_skip(struct pet_scop *scop, enum pet_skip type)
2745 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2747 if (!scop)
2748 return -1;
2749 return ext->skip[type] != NULL;
2752 /* Does "scop" have a skip condition of the given "type" that
2753 * is an affine expression?
2755 int pet_scop_has_affine_skip(struct pet_scop *scop, enum pet_skip type)
2757 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2759 if (!scop)
2760 return -1;
2761 if (!ext->skip[type])
2762 return 0;
2763 return multi_pw_aff_is_affine(ext->skip[type]);
2766 /* Does "scop" have a skip condition of the given "type" that
2767 * is not an affine expression?
2769 int pet_scop_has_var_skip(struct pet_scop *scop, enum pet_skip type)
2771 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2772 int aff;
2774 if (!scop)
2775 return -1;
2776 if (!ext->skip[type])
2777 return 0;
2778 aff = multi_pw_aff_is_affine(ext->skip[type]);
2779 if (aff < 0)
2780 return -1;
2781 return !aff;
2784 /* Does "scop" have a skip condition of the given "type" that
2785 * is affine and holds on the entire domain?
2787 int pet_scop_has_universal_skip(struct pet_scop *scop, enum pet_skip type)
2789 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2790 isl_pw_aff *pa;
2791 isl_set *set;
2792 int is_aff;
2793 int is_univ;
2795 is_aff = pet_scop_has_affine_skip(scop, type);
2796 if (is_aff < 0 || !is_aff)
2797 return is_aff;
2799 pa = isl_multi_pw_aff_get_pw_aff(ext->skip[type], 0);
2800 set = isl_pw_aff_non_zero_set(pa);
2801 is_univ = isl_set_plain_is_universe(set);
2802 isl_set_free(set);
2804 return is_univ;
2807 /* Replace scop->skip[type] by "skip".
2809 struct pet_scop *pet_scop_set_skip(struct pet_scop *scop,
2810 enum pet_skip type, __isl_take isl_multi_pw_aff *skip)
2812 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2814 if (!scop || !skip)
2815 goto error;
2817 isl_multi_pw_aff_free(ext->skip[type]);
2818 ext->skip[type] = skip;
2820 return scop;
2821 error:
2822 isl_multi_pw_aff_free(skip);
2823 return pet_scop_free(scop);
2826 /* Return a copy of scop->skip[type].
2828 __isl_give isl_multi_pw_aff *pet_scop_get_skip(struct pet_scop *scop,
2829 enum pet_skip type)
2831 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2833 if (!scop)
2834 return NULL;
2836 return isl_multi_pw_aff_copy(ext->skip[type]);
2839 /* Assuming scop->skip[type] is an affine expression,
2840 * return the constraints on the parameters for which the skip condition
2841 * holds.
2843 __isl_give isl_set *pet_scop_get_affine_skip_domain(struct pet_scop *scop,
2844 enum pet_skip type)
2846 isl_multi_pw_aff *skip;
2847 isl_pw_aff *pa;
2849 skip = pet_scop_get_skip(scop, type);
2850 pa = isl_multi_pw_aff_get_pw_aff(skip, 0);
2851 isl_multi_pw_aff_free(skip);
2852 return isl_set_params(isl_pw_aff_non_zero_set(pa));
2855 /* Return the identifier of the variable that is accessed by
2856 * the skip condition of the given type.
2858 * The skip condition is assumed not to be an affine condition.
2860 __isl_give isl_id *pet_scop_get_skip_id(struct pet_scop *scop,
2861 enum pet_skip type)
2863 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2865 if (!scop)
2866 return NULL;
2868 return isl_multi_pw_aff_get_tuple_id(ext->skip[type], isl_dim_out);
2871 /* Return an access pet_expr corresponding to the skip condition
2872 * of the given type.
2874 struct pet_expr *pet_scop_get_skip_expr(struct pet_scop *scop,
2875 enum pet_skip type)
2877 return pet_expr_from_index(pet_scop_get_skip(scop, type));
2880 /* Drop the the skip condition scop->skip[type].
2882 void pet_scop_reset_skip(struct pet_scop *scop, enum pet_skip type)
2884 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2886 if (!scop)
2887 return;
2889 isl_multi_pw_aff_free(ext->skip[type]);
2890 ext->skip[type] = NULL;
2893 /* Make the skip condition (if any) depend on the value of "test" being
2894 * equal to "satisfied".
2896 * We only support the case where the original skip condition is universal,
2897 * i.e., where skipping is unconditional, and where satisfied == 1.
2898 * In this case, the skip condition is changed to skip only when
2899 * "test" is equal to one.
2901 static struct pet_scop *pet_scop_filter_skip(struct pet_scop *scop,
2902 enum pet_skip type, __isl_keep isl_multi_pw_aff *test, int satisfied)
2904 int is_univ = 0;
2906 if (!scop)
2907 return NULL;
2908 if (!pet_scop_has_skip(scop, type))
2909 return scop;
2911 if (satisfied)
2912 is_univ = pet_scop_has_universal_skip(scop, type);
2913 if (is_univ < 0)
2914 return pet_scop_free(scop);
2915 if (satisfied && is_univ) {
2916 isl_space *space = isl_multi_pw_aff_get_space(test);
2917 isl_multi_pw_aff *skip;
2918 skip = isl_multi_pw_aff_zero(space);
2919 scop = pet_scop_set_skip(scop, type, skip);
2920 if (!scop)
2921 return NULL;
2922 } else {
2923 isl_die(isl_multi_pw_aff_get_ctx(test), isl_error_internal,
2924 "skip expression cannot be filtered",
2925 return pet_scop_free(scop));
2928 return scop;
2931 /* Make all statements in "scop" depend on the value of "test"
2932 * being equal to "satisfied" by adjusting their domains.
2934 struct pet_scop *pet_scop_filter(struct pet_scop *scop,
2935 __isl_take isl_multi_pw_aff *test, int satisfied)
2937 int i;
2939 scop = pet_scop_filter_skip(scop, pet_skip_now, test, satisfied);
2940 scop = pet_scop_filter_skip(scop, pet_skip_later, test, satisfied);
2942 if (!scop || !test)
2943 goto error;
2945 for (i = 0; i < scop->n_stmt; ++i) {
2946 scop->stmts[i] = stmt_filter(scop, scop->stmts[i],
2947 isl_multi_pw_aff_copy(test), satisfied);
2948 if (!scop->stmts[i])
2949 goto error;
2952 isl_multi_pw_aff_free(test);
2953 return scop;
2954 error:
2955 isl_multi_pw_aff_free(test);
2956 return pet_scop_free(scop);
2959 /* Add all parameters in "expr" to "dim" and return the result.
2961 static __isl_give isl_space *expr_collect_params(struct pet_expr *expr,
2962 __isl_take isl_space *dim)
2964 int i;
2966 if (!expr)
2967 goto error;
2968 for (i = 0; i < expr->n_arg; ++i)
2970 dim = expr_collect_params(expr->args[i], dim);
2972 if (expr->type == pet_expr_access)
2973 dim = isl_space_align_params(dim,
2974 isl_map_get_space(expr->acc.access));
2976 return dim;
2977 error:
2978 pet_expr_free(expr);
2979 return isl_space_free(dim);
2982 /* Add all parameters in "stmt" to "dim" and return the result.
2984 static __isl_give isl_space *stmt_collect_params(struct pet_stmt *stmt,
2985 __isl_take isl_space *dim)
2987 if (!stmt)
2988 goto error;
2990 dim = isl_space_align_params(dim, isl_set_get_space(stmt->domain));
2991 dim = isl_space_align_params(dim, isl_map_get_space(stmt->schedule));
2992 dim = expr_collect_params(stmt->body, dim);
2994 return dim;
2995 error:
2996 isl_space_free(dim);
2997 return pet_stmt_free(stmt);
3000 /* Add all parameters in "array" to "dim" and return the result.
3002 static __isl_give isl_space *array_collect_params(struct pet_array *array,
3003 __isl_take isl_space *dim)
3005 if (!array)
3006 goto error;
3008 dim = isl_space_align_params(dim, isl_set_get_space(array->context));
3009 dim = isl_space_align_params(dim, isl_set_get_space(array->extent));
3011 return dim;
3012 error:
3013 pet_array_free(array);
3014 return isl_space_free(dim);
3017 /* Add all parameters in "scop" to "dim" and return the result.
3019 static __isl_give isl_space *scop_collect_params(struct pet_scop *scop,
3020 __isl_take isl_space *dim)
3022 int i;
3024 if (!scop)
3025 goto error;
3027 for (i = 0; i < scop->n_array; ++i)
3028 dim = array_collect_params(scop->arrays[i], dim);
3030 for (i = 0; i < scop->n_stmt; ++i)
3031 dim = stmt_collect_params(scop->stmts[i], dim);
3033 return dim;
3034 error:
3035 isl_space_free(dim);
3036 pet_scop_free(scop);
3037 return NULL;
3040 /* Add all parameters in "dim" to all access relations and index expressions
3041 * in "expr".
3043 static struct pet_expr *expr_propagate_params(struct pet_expr *expr,
3044 __isl_take isl_space *dim)
3046 int i;
3048 if (!expr)
3049 goto error;
3051 for (i = 0; i < expr->n_arg; ++i) {
3052 expr->args[i] =
3053 expr_propagate_params(expr->args[i],
3054 isl_space_copy(dim));
3055 if (!expr->args[i])
3056 goto error;
3059 if (expr->type == pet_expr_access) {
3060 expr->acc.access = isl_map_align_params(expr->acc.access,
3061 isl_space_copy(dim));
3062 expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
3063 isl_space_copy(dim));
3064 if (!expr->acc.access || !expr->acc.index)
3065 goto error;
3068 isl_space_free(dim);
3069 return expr;
3070 error:
3071 isl_space_free(dim);
3072 return pet_expr_free(expr);
3075 /* Add all parameters in "dim" to the domain, schedule and
3076 * all access relations in "stmt".
3078 static struct pet_stmt *stmt_propagate_params(struct pet_stmt *stmt,
3079 __isl_take isl_space *dim)
3081 if (!stmt)
3082 goto error;
3084 stmt->domain = isl_set_align_params(stmt->domain, isl_space_copy(dim));
3085 stmt->schedule = isl_map_align_params(stmt->schedule,
3086 isl_space_copy(dim));
3087 stmt->body = expr_propagate_params(stmt->body, isl_space_copy(dim));
3089 if (!stmt->domain || !stmt->schedule || !stmt->body)
3090 goto error;
3092 isl_space_free(dim);
3093 return stmt;
3094 error:
3095 isl_space_free(dim);
3096 return pet_stmt_free(stmt);
3099 /* Add all parameters in "dim" to "array".
3101 static struct pet_array *array_propagate_params(struct pet_array *array,
3102 __isl_take isl_space *dim)
3104 if (!array)
3105 goto error;
3107 array->context = isl_set_align_params(array->context,
3108 isl_space_copy(dim));
3109 array->extent = isl_set_align_params(array->extent,
3110 isl_space_copy(dim));
3111 if (array->value_bounds) {
3112 array->value_bounds = isl_set_align_params(array->value_bounds,
3113 isl_space_copy(dim));
3114 if (!array->value_bounds)
3115 goto error;
3118 if (!array->context || !array->extent)
3119 goto error;
3121 isl_space_free(dim);
3122 return array;
3123 error:
3124 isl_space_free(dim);
3125 return pet_array_free(array);
3128 /* Add all parameters in "dim" to "scop".
3130 static struct pet_scop *scop_propagate_params(struct pet_scop *scop,
3131 __isl_take isl_space *dim)
3133 int i;
3135 if (!scop)
3136 goto error;
3138 for (i = 0; i < scop->n_array; ++i) {
3139 scop->arrays[i] = array_propagate_params(scop->arrays[i],
3140 isl_space_copy(dim));
3141 if (!scop->arrays[i])
3142 goto error;
3145 for (i = 0; i < scop->n_stmt; ++i) {
3146 scop->stmts[i] = stmt_propagate_params(scop->stmts[i],
3147 isl_space_copy(dim));
3148 if (!scop->stmts[i])
3149 goto error;
3152 isl_space_free(dim);
3153 return scop;
3154 error:
3155 isl_space_free(dim);
3156 return pet_scop_free(scop);
3159 /* Update all isl_sets and isl_maps in "scop" such that they all
3160 * have the same parameters.
3162 struct pet_scop *pet_scop_align_params(struct pet_scop *scop)
3164 isl_space *dim;
3166 if (!scop)
3167 return NULL;
3169 dim = isl_set_get_space(scop->context);
3170 dim = scop_collect_params(scop, dim);
3172 scop->context = isl_set_align_params(scop->context, isl_space_copy(dim));
3173 scop = scop_propagate_params(scop, dim);
3175 return scop;
3178 /* Check if the given index expression accesses a (0D) array that corresponds
3179 * to one of the parameters in "dim". If so, replace the array access
3180 * by an access to the set of integers with as index (and value)
3181 * that parameter.
3183 static __isl_give isl_multi_pw_aff *index_detect_parameter(
3184 __isl_take isl_multi_pw_aff *index, __isl_take isl_space *space)
3186 isl_local_space *ls;
3187 isl_id *array_id = NULL;
3188 isl_aff *aff;
3189 int pos = -1;
3191 if (isl_multi_pw_aff_has_tuple_id(index, isl_dim_out)) {
3192 array_id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
3193 pos = isl_space_find_dim_by_id(space, isl_dim_param, array_id);
3195 isl_space_free(space);
3197 if (pos < 0) {
3198 isl_id_free(array_id);
3199 return index;
3202 space = isl_multi_pw_aff_get_domain_space(index);
3203 isl_multi_pw_aff_free(index);
3205 pos = isl_space_find_dim_by_id(space, isl_dim_param, array_id);
3206 if (pos < 0) {
3207 space = isl_space_insert_dims(space, isl_dim_param, 0, 1);
3208 space = isl_space_set_dim_id(space, isl_dim_param, 0, array_id);
3209 pos = 0;
3210 } else
3211 isl_id_free(array_id);
3213 ls = isl_local_space_from_space(space);
3214 aff = isl_aff_var_on_domain(ls, isl_dim_param, pos);
3215 index = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
3217 return index;
3220 /* Check if the given access relation accesses a (0D) array that corresponds
3221 * to one of the parameters in "dim". If so, replace the array access
3222 * by an access to the set of integers with as index (and value)
3223 * that parameter.
3225 static __isl_give isl_map *access_detect_parameter(__isl_take isl_map *access,
3226 __isl_take isl_space *dim)
3228 isl_id *array_id = NULL;
3229 int pos = -1;
3231 if (isl_map_has_tuple_id(access, isl_dim_out)) {
3232 array_id = isl_map_get_tuple_id(access, isl_dim_out);
3233 pos = isl_space_find_dim_by_id(dim, isl_dim_param, array_id);
3235 isl_space_free(dim);
3237 if (pos < 0) {
3238 isl_id_free(array_id);
3239 return access;
3242 pos = isl_map_find_dim_by_id(access, isl_dim_param, array_id);
3243 if (pos < 0) {
3244 access = isl_map_insert_dims(access, isl_dim_param, 0, 1);
3245 access = isl_map_set_dim_id(access, isl_dim_param, 0, array_id);
3246 pos = 0;
3247 } else
3248 isl_id_free(array_id);
3250 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
3251 access = isl_map_equate(access, isl_dim_param, pos, isl_dim_out, 0);
3253 return access;
3256 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3257 * in "dim" by a value equal to the corresponding parameter.
3259 static struct pet_expr *expr_detect_parameter_accesses(struct pet_expr *expr,
3260 __isl_take isl_space *dim)
3262 int i;
3264 if (!expr)
3265 goto error;
3267 for (i = 0; i < expr->n_arg; ++i) {
3268 expr->args[i] =
3269 expr_detect_parameter_accesses(expr->args[i],
3270 isl_space_copy(dim));
3271 if (!expr->args[i])
3272 goto error;
3275 if (expr->type == pet_expr_access) {
3276 expr->acc.access = access_detect_parameter(expr->acc.access,
3277 isl_space_copy(dim));
3278 expr->acc.index = index_detect_parameter(expr->acc.index,
3279 isl_space_copy(dim));
3280 if (!expr->acc.access || !expr->acc.index)
3281 goto error;
3284 isl_space_free(dim);
3285 return expr;
3286 error:
3287 isl_space_free(dim);
3288 return pet_expr_free(expr);
3291 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3292 * in "dim" by a value equal to the corresponding parameter.
3294 static struct pet_stmt *stmt_detect_parameter_accesses(struct pet_stmt *stmt,
3295 __isl_take isl_space *dim)
3297 if (!stmt)
3298 goto error;
3300 stmt->body = expr_detect_parameter_accesses(stmt->body,
3301 isl_space_copy(dim));
3303 if (!stmt->domain || !stmt->schedule || !stmt->body)
3304 goto error;
3306 isl_space_free(dim);
3307 return stmt;
3308 error:
3309 isl_space_free(dim);
3310 return pet_stmt_free(stmt);
3313 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3314 * in "dim" by a value equal to the corresponding parameter.
3316 static struct pet_scop *scop_detect_parameter_accesses(struct pet_scop *scop,
3317 __isl_take isl_space *dim)
3319 int i;
3321 if (!scop)
3322 goto error;
3324 for (i = 0; i < scop->n_stmt; ++i) {
3325 scop->stmts[i] = stmt_detect_parameter_accesses(scop->stmts[i],
3326 isl_space_copy(dim));
3327 if (!scop->stmts[i])
3328 goto error;
3331 isl_space_free(dim);
3332 return scop;
3333 error:
3334 isl_space_free(dim);
3335 return pet_scop_free(scop);
3338 /* Replace all accesses to (0D) arrays that correspond to any of
3339 * the parameters used in "scop" by a value equal
3340 * to the corresponding parameter.
3342 struct pet_scop *pet_scop_detect_parameter_accesses(struct pet_scop *scop)
3344 isl_space *dim;
3346 if (!scop)
3347 return NULL;
3349 dim = isl_set_get_space(scop->context);
3350 dim = scop_collect_params(scop, dim);
3352 scop = scop_detect_parameter_accesses(scop, dim);
3354 return scop;
3357 /* Return the relation mapping domain iterations to all possibly
3358 * accessed data elements.
3359 * In particular, take the access relation and project out the values
3360 * of the arguments, if any.
3362 __isl_give isl_map *pet_expr_access_get_may_access(struct pet_expr *expr)
3364 isl_map *access;
3365 isl_space *space;
3366 isl_map *map;
3368 if (!expr)
3369 return NULL;
3370 if (expr->type != pet_expr_access)
3371 return NULL;
3373 access = isl_map_copy(expr->acc.access);
3374 if (expr->n_arg == 0)
3375 return access;
3377 space = isl_space_domain(isl_map_get_space(access));
3378 map = isl_map_universe(isl_space_unwrap(space));
3379 map = isl_map_domain_map(map);
3380 access = isl_map_apply_domain(access, map);
3382 return access;
3385 /* Return the relation mapping domain iterations to all possibly
3386 * accessed data elements, with its domain tagged with the reference
3387 * identifier.
3389 __isl_give isl_map *pet_expr_access_get_tagged_may_access(
3390 struct pet_expr *expr)
3392 isl_map *access;
3394 if (!expr)
3395 return NULL;
3397 access = pet_expr_access_get_may_access(expr);
3398 access = tag_access(access, isl_id_copy(expr->acc.ref_id));
3400 return access;
3403 /* Add all read access relations (if "read" is set) and/or all write
3404 * access relations (if "write" is set) to "accesses" and return the result.
3405 * The domains of the access relations are intersected with "domain".
3406 * If "tag" is set, then the access relations are tagged with
3407 * the corresponding reference identifiers.
3409 * If "must" is set, then we only add the accesses that are definitely
3410 * performed. Otherwise, we add all potential accesses.
3411 * In particular, if the access has any arguments, then if "must" is
3412 * set we currently skip the access completely. If "must" is not set,
3413 * we project out the values of the access arguments.
3415 static __isl_give isl_union_map *expr_collect_accesses(struct pet_expr *expr,
3416 int read, int write, int must, int tag,
3417 __isl_take isl_union_map *accesses, __isl_keep isl_set *domain)
3419 int i;
3420 isl_id *id;
3421 isl_space *dim;
3423 if (!expr)
3424 return isl_union_map_free(accesses);
3426 for (i = 0; i < expr->n_arg; ++i)
3427 accesses = expr_collect_accesses(expr->args[i],
3428 read, write, must, tag, accesses, domain);
3430 if (expr->type == pet_expr_access && !pet_expr_is_affine(expr) &&
3431 ((read && expr->acc.read) || (write && expr->acc.write)) &&
3432 (!must || expr->n_arg == 0)) {
3433 isl_map *access;
3435 access = pet_expr_access_get_may_access(expr);
3436 access = isl_map_intersect_domain(access, isl_set_copy(domain));
3437 if (tag)
3438 access = tag_access(access,
3439 isl_id_copy(expr->acc.ref_id));
3440 accesses = isl_union_map_add_map(accesses, access);
3443 return accesses;
3446 /* Collect and return all read access relations (if "read" is set)
3447 * and/or all write access relations (if "write" is set) in "stmt".
3448 * If "tag" is set, then the access relations are tagged with
3449 * the corresponding reference identifiers.
3451 * If "must" is set, then we only add the accesses that are definitely
3452 * performed. Otherwise, we add all potential accesses.
3453 * In particular, if the statement has any arguments, then if "must" is
3454 * set we currently skip the statement completely. If "must" is not set,
3455 * we project out the values of the statement arguments.
3457 static __isl_give isl_union_map *stmt_collect_accesses(struct pet_stmt *stmt,
3458 int read, int write, int must, int tag, __isl_take isl_space *dim)
3460 isl_union_map *accesses;
3461 isl_set *domain;
3463 if (!stmt)
3464 return NULL;
3466 accesses = isl_union_map_empty(dim);
3468 if (must && stmt->n_arg > 0)
3469 return accesses;
3471 domain = isl_set_copy(stmt->domain);
3472 if (isl_set_is_wrapping(domain))
3473 domain = isl_map_domain(isl_set_unwrap(domain));
3475 accesses = expr_collect_accesses(stmt->body,
3476 read, write, must, tag, accesses, domain);
3477 isl_set_free(domain);
3479 return accesses;
3482 /* Collect and return all read access relations (if "read" is set)
3483 * and/or all write access relations (if "write" is set) in "scop".
3484 * If "must" is set, then we only add the accesses that are definitely
3485 * performed. Otherwise, we add all potential accesses.
3486 * If "tag" is set, then the access relations are tagged with
3487 * the corresponding reference identifiers.
3489 static __isl_give isl_union_map *scop_collect_accesses(struct pet_scop *scop,
3490 int read, int write, int must, int tag)
3492 int i;
3493 isl_union_map *accesses;
3494 isl_union_set *arrays;
3496 if (!scop)
3497 return NULL;
3499 accesses = isl_union_map_empty(isl_set_get_space(scop->context));
3501 for (i = 0; i < scop->n_stmt; ++i) {
3502 isl_union_map *accesses_i;
3503 isl_space *space = isl_set_get_space(scop->context);
3504 accesses_i = stmt_collect_accesses(scop->stmts[i],
3505 read, write, must, tag, space);
3506 accesses = isl_union_map_union(accesses, accesses_i);
3509 arrays = isl_union_set_empty(isl_union_map_get_space(accesses));
3510 for (i = 0; i < scop->n_array; ++i) {
3511 isl_set *extent = isl_set_copy(scop->arrays[i]->extent);
3512 arrays = isl_union_set_add_set(arrays, extent);
3514 accesses = isl_union_map_intersect_range(accesses, arrays);
3516 return accesses;
3519 /* Collect all potential read access relations.
3521 __isl_give isl_union_map *pet_scop_collect_may_reads(struct pet_scop *scop)
3523 return scop_collect_accesses(scop, 1, 0, 0, 0);
3526 /* Collect all potential write access relations.
3528 __isl_give isl_union_map *pet_scop_collect_may_writes(struct pet_scop *scop)
3530 return scop_collect_accesses(scop, 0, 1, 0, 0);
3533 /* Collect all definite write access relations.
3535 __isl_give isl_union_map *pet_scop_collect_must_writes(struct pet_scop *scop)
3537 return scop_collect_accesses(scop, 0, 1, 1, 0);
3540 /* Collect all tagged potential read access relations.
3542 __isl_give isl_union_map *pet_scop_collect_tagged_may_reads(
3543 struct pet_scop *scop)
3545 return scop_collect_accesses(scop, 1, 0, 0, 1);
3548 /* Collect all tagged potential write access relations.
3550 __isl_give isl_union_map *pet_scop_collect_tagged_may_writes(
3551 struct pet_scop *scop)
3553 return scop_collect_accesses(scop, 0, 1, 0, 1);
3556 /* Collect all tagged definite write access relations.
3558 __isl_give isl_union_map *pet_scop_collect_tagged_must_writes(
3559 struct pet_scop *scop)
3561 return scop_collect_accesses(scop, 0, 1, 1, 1);
3564 /* Collect and return the union of iteration domains in "scop".
3566 __isl_give isl_union_set *pet_scop_collect_domains(struct pet_scop *scop)
3568 int i;
3569 isl_set *domain_i;
3570 isl_union_set *domain;
3572 if (!scop)
3573 return NULL;
3575 domain = isl_union_set_empty(isl_set_get_space(scop->context));
3577 for (i = 0; i < scop->n_stmt; ++i) {
3578 domain_i = isl_set_copy(scop->stmts[i]->domain);
3579 domain = isl_union_set_add_set(domain, domain_i);
3582 return domain;
3585 /* Collect and return the schedules of the statements in "scop".
3586 * The range is normalized to the maximal number of scheduling
3587 * dimensions.
3589 __isl_give isl_union_map *pet_scop_collect_schedule(struct pet_scop *scop)
3591 int i, j;
3592 isl_map *schedule_i;
3593 isl_union_map *schedule;
3594 int depth, max_depth = 0;
3596 if (!scop)
3597 return NULL;
3599 schedule = isl_union_map_empty(isl_set_get_space(scop->context));
3601 for (i = 0; i < scop->n_stmt; ++i) {
3602 depth = isl_map_dim(scop->stmts[i]->schedule, isl_dim_out);
3603 if (depth > max_depth)
3604 max_depth = depth;
3607 for (i = 0; i < scop->n_stmt; ++i) {
3608 schedule_i = isl_map_copy(scop->stmts[i]->schedule);
3609 depth = isl_map_dim(schedule_i, isl_dim_out);
3610 schedule_i = isl_map_add_dims(schedule_i, isl_dim_out,
3611 max_depth - depth);
3612 for (j = depth; j < max_depth; ++j)
3613 schedule_i = isl_map_fix_si(schedule_i,
3614 isl_dim_out, j, 0);
3615 schedule = isl_union_map_add_map(schedule, schedule_i);
3618 return schedule;
3621 /* Does expression "expr" write to "id"?
3623 static int expr_writes(struct pet_expr *expr, __isl_keep isl_id *id)
3625 int i;
3626 isl_id *write_id;
3628 for (i = 0; i < expr->n_arg; ++i) {
3629 int writes = expr_writes(expr->args[i], id);
3630 if (writes < 0 || writes)
3631 return writes;
3634 if (expr->type != pet_expr_access)
3635 return 0;
3636 if (!expr->acc.write)
3637 return 0;
3638 if (pet_expr_is_affine(expr))
3639 return 0;
3641 write_id = pet_expr_access_get_id(expr);
3642 isl_id_free(write_id);
3644 if (!write_id)
3645 return -1;
3647 return write_id == id;
3650 /* Does statement "stmt" write to "id"?
3652 static int stmt_writes(struct pet_stmt *stmt, __isl_keep isl_id *id)
3654 return expr_writes(stmt->body, id);
3657 /* Is there any write access in "scop" that accesses "id"?
3659 int pet_scop_writes(struct pet_scop *scop, __isl_keep isl_id *id)
3661 int i;
3663 if (!scop)
3664 return -1;
3666 for (i = 0; i < scop->n_stmt; ++i) {
3667 int writes = stmt_writes(scop->stmts[i], id);
3668 if (writes < 0 || writes)
3669 return writes;
3672 return 0;
3675 /* Add a reference identifier to access expression "expr".
3676 * "user" points to an integer that contains the sequence number
3677 * of the next reference.
3679 static struct pet_expr *access_add_ref_id(struct pet_expr *expr, void *user)
3681 isl_ctx *ctx;
3682 char name[50];
3683 int *n_ref = user;
3685 if (!expr)
3686 return expr;
3688 ctx = isl_map_get_ctx(expr->acc.access);
3689 snprintf(name, sizeof(name), "__pet_ref_%d", (*n_ref)++);
3690 expr->acc.ref_id = isl_id_alloc(ctx, name, NULL);
3691 if (!expr->acc.ref_id)
3692 return pet_expr_free(expr);
3694 return expr;
3697 /* Add a reference identifier to all access expressions in "stmt".
3698 * "n_ref" points to an integer that contains the sequence number
3699 * of the next reference.
3701 static struct pet_stmt *stmt_add_ref_ids(struct pet_stmt *stmt, int *n_ref)
3703 int i;
3705 if (!stmt)
3706 return NULL;
3708 for (i = 0; i < stmt->n_arg; ++i) {
3709 stmt->args[i] = pet_expr_map_access(stmt->args[i],
3710 &access_add_ref_id, n_ref);
3711 if (!stmt->args[i])
3712 return pet_stmt_free(stmt);
3715 stmt->body = pet_expr_map_access(stmt->body, &access_add_ref_id, n_ref);
3716 if (!stmt->body)
3717 return pet_stmt_free(stmt);
3719 return stmt;
3722 /* Add a reference identifier to all access expressions in "scop".
3724 struct pet_scop *pet_scop_add_ref_ids(struct pet_scop *scop)
3726 int i;
3727 int n_ref;
3729 if (!scop)
3730 return NULL;
3732 n_ref = 0;
3733 for (i = 0; i < scop->n_stmt; ++i) {
3734 scop->stmts[i] = stmt_add_ref_ids(scop->stmts[i], &n_ref);
3735 if (!scop->stmts[i])
3736 return pet_scop_free(scop);
3739 return scop;
3742 /* Reset the user pointer on all parameter ids in "array".
3744 static struct pet_array *array_anonymize(struct pet_array *array)
3746 if (!array)
3747 return NULL;
3749 array->context = isl_set_reset_user(array->context);
3750 array->extent = isl_set_reset_user(array->extent);
3751 if (!array->context || !array->extent)
3752 return pet_array_free(array);
3754 return array;
3757 /* Reset the user pointer on all parameter and tuple ids in
3758 * the access relation and the index expressions
3759 * of the access expression "expr".
3761 static struct pet_expr *access_anonymize(struct pet_expr *expr, void *user)
3763 expr->acc.access = isl_map_reset_user(expr->acc.access);
3764 expr->acc.index = isl_multi_pw_aff_reset_user(expr->acc.index);
3765 if (!expr->acc.access || !expr->acc.index)
3766 return pet_expr_free(expr);
3768 return expr;
3771 /* Reset the user pointer on all parameter and tuple ids in "stmt".
3773 static struct pet_stmt *stmt_anonymize(struct pet_stmt *stmt)
3775 int i;
3776 isl_space *space;
3777 isl_set *domain;
3779 if (!stmt)
3780 return NULL;
3782 stmt->domain = isl_set_reset_user(stmt->domain);
3783 stmt->schedule = isl_map_reset_user(stmt->schedule);
3784 if (!stmt->domain || !stmt->schedule)
3785 return pet_stmt_free(stmt);
3787 for (i = 0; i < stmt->n_arg; ++i) {
3788 stmt->args[i] = pet_expr_map_access(stmt->args[i],
3789 &access_anonymize, NULL);
3790 if (!stmt->args[i])
3791 return pet_stmt_free(stmt);
3794 stmt->body = pet_expr_map_access(stmt->body,
3795 &access_anonymize, NULL);
3796 if (!stmt->body)
3797 return pet_stmt_free(stmt);
3799 return stmt;
3802 /* Reset the user pointer on the tuple ids and all parameter ids
3803 * in "implication".
3805 static struct pet_implication *implication_anonymize(
3806 struct pet_implication *implication)
3808 if (!implication)
3809 return NULL;
3811 implication->extension = isl_map_reset_user(implication->extension);
3812 if (!implication->extension)
3813 return pet_implication_free(implication);
3815 return implication;
3818 /* Reset the user pointer on all parameter and tuple ids in "scop".
3820 struct pet_scop *pet_scop_anonymize(struct pet_scop *scop)
3822 int i;
3824 if (!scop)
3825 return NULL;
3827 scop->context = isl_set_reset_user(scop->context);
3828 scop->context_value = isl_set_reset_user(scop->context_value);
3829 if (!scop->context || !scop->context_value)
3830 return pet_scop_free(scop);
3832 for (i = 0; i < scop->n_array; ++i) {
3833 scop->arrays[i] = array_anonymize(scop->arrays[i]);
3834 if (!scop->arrays[i])
3835 return pet_scop_free(scop);
3838 for (i = 0; i < scop->n_stmt; ++i) {
3839 scop->stmts[i] = stmt_anonymize(scop->stmts[i]);
3840 if (!scop->stmts[i])
3841 return pet_scop_free(scop);
3844 for (i = 0; i < scop->n_implication; ++i) {
3845 scop->implications[i] =
3846 implication_anonymize(scop->implications[i]);
3847 if (!scop->implications[i])
3848 return pet_scop_free(scop);
3851 return scop;
3854 /* If "value_bounds" contains any bounds on the variable accessed by "arg",
3855 * then intersect the range of "map" with the valid set of values.
3857 static __isl_give isl_map *access_apply_value_bounds(__isl_take isl_map *map,
3858 struct pet_expr *arg, __isl_keep isl_union_map *value_bounds)
3860 isl_id *id;
3861 isl_map *vb;
3862 isl_space *space;
3863 isl_ctx *ctx = isl_map_get_ctx(map);
3865 id = pet_expr_access_get_id(arg);
3866 space = isl_space_alloc(ctx, 0, 0, 1);
3867 space = isl_space_set_tuple_id(space, isl_dim_in, id);
3868 vb = isl_union_map_extract_map(value_bounds, space);
3869 if (!isl_map_plain_is_empty(vb))
3870 map = isl_map_intersect_range(map, isl_map_range(vb));
3871 else
3872 isl_map_free(vb);
3874 return map;
3877 /* Given a set "domain", return a wrapped relation with the given set
3878 * as domain and a range of dimension "n_arg", where each coordinate
3879 * is either unbounded or, if the corresponding element of args is of
3880 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
3882 static __isl_give isl_set *apply_value_bounds(__isl_take isl_set *domain,
3883 unsigned n_arg, struct pet_expr **args,
3884 __isl_keep isl_union_map *value_bounds)
3886 int i;
3887 isl_map *map;
3888 isl_space *space;
3890 map = isl_map_from_domain(domain);
3891 space = isl_map_get_space(map);
3892 space = isl_space_add_dims(space, isl_dim_out, 1);
3894 for (i = 0; i < n_arg; ++i) {
3895 isl_map *map_i;
3896 struct pet_expr *arg = args[i];
3898 map_i = isl_map_universe(isl_space_copy(space));
3899 if (arg->type == pet_expr_access)
3900 map_i = access_apply_value_bounds(map_i, arg,
3901 value_bounds);
3902 map = isl_map_flat_range_product(map, map_i);
3904 isl_space_free(space);
3906 return isl_map_wrap(map);
3909 /* Data used in access_gist() callback.
3911 struct pet_access_gist_data {
3912 isl_set *domain;
3913 isl_union_map *value_bounds;
3916 /* Given an expression "expr" of type pet_expr_access, compute
3917 * the gist of the associated access relation and index expression
3918 * with respect to data->domain and the bounds on the values of the arguments
3919 * of the expression.
3921 static struct pet_expr *access_gist(struct pet_expr *expr, void *user)
3923 struct pet_access_gist_data *data = user;
3924 isl_set *domain;
3926 domain = isl_set_copy(data->domain);
3927 if (expr->n_arg > 0)
3928 domain = apply_value_bounds(domain, expr->n_arg, expr->args,
3929 data->value_bounds);
3931 expr->acc.access = isl_map_gist_domain(expr->acc.access,
3932 isl_set_copy(domain));
3933 expr->acc.index = isl_multi_pw_aff_gist(expr->acc.index, domain);
3934 if (!expr->acc.access || !expr->acc.index)
3935 return pet_expr_free(expr);
3937 return expr;
3940 /* Compute the gist of the iteration domain and all access relations
3941 * of "stmt" based on the constraints on the parameters specified by "context"
3942 * and the constraints on the values of nested accesses specified
3943 * by "value_bounds".
3945 static struct pet_stmt *stmt_gist(struct pet_stmt *stmt,
3946 __isl_keep isl_set *context, __isl_keep isl_union_map *value_bounds)
3948 int i;
3949 isl_space *space;
3950 isl_set *domain;
3951 struct pet_access_gist_data data;
3953 if (!stmt)
3954 return NULL;
3956 data.domain = isl_set_copy(stmt->domain);
3957 data.value_bounds = value_bounds;
3958 if (stmt->n_arg > 0)
3959 data.domain = isl_map_domain(isl_set_unwrap(data.domain));
3961 data.domain = isl_set_intersect_params(data.domain,
3962 isl_set_copy(context));
3964 for (i = 0; i < stmt->n_arg; ++i) {
3965 stmt->args[i] = pet_expr_map_access(stmt->args[i],
3966 &access_gist, &data);
3967 if (!stmt->args[i])
3968 goto error;
3971 stmt->body = pet_expr_map_access(stmt->body, &access_gist, &data);
3972 if (!stmt->body)
3973 goto error;
3975 isl_set_free(data.domain);
3977 space = isl_set_get_space(stmt->domain);
3978 if (isl_space_is_wrapping(space))
3979 space = isl_space_domain(isl_space_unwrap(space));
3980 domain = isl_set_universe(space);
3981 domain = isl_set_intersect_params(domain, isl_set_copy(context));
3982 if (stmt->n_arg > 0)
3983 domain = apply_value_bounds(domain, stmt->n_arg, stmt->args,
3984 value_bounds);
3985 stmt->domain = isl_set_gist(stmt->domain, domain);
3986 if (!stmt->domain)
3987 return pet_stmt_free(stmt);
3989 return stmt;
3990 error:
3991 isl_set_free(data.domain);
3992 return pet_stmt_free(stmt);
3995 /* Compute the gist of the extent of the array
3996 * based on the constraints on the parameters specified by "context".
3998 static struct pet_array *array_gist(struct pet_array *array,
3999 __isl_keep isl_set *context)
4001 if (!array)
4002 return NULL;
4004 array->extent = isl_set_gist_params(array->extent,
4005 isl_set_copy(context));
4006 if (!array->extent)
4007 return pet_array_free(array);
4009 return array;
4012 /* Compute the gist of all sets and relations in "scop"
4013 * based on the constraints on the parameters specified by "scop->context"
4014 * and the constraints on the values of nested accesses specified
4015 * by "value_bounds".
4017 struct pet_scop *pet_scop_gist(struct pet_scop *scop,
4018 __isl_keep isl_union_map *value_bounds)
4020 int i;
4022 if (!scop)
4023 return NULL;
4025 scop->context = isl_set_coalesce(scop->context);
4026 if (!scop->context)
4027 return pet_scop_free(scop);
4029 for (i = 0; i < scop->n_array; ++i) {
4030 scop->arrays[i] = array_gist(scop->arrays[i], scop->context);
4031 if (!scop->arrays[i])
4032 return pet_scop_free(scop);
4035 for (i = 0; i < scop->n_stmt; ++i) {
4036 scop->stmts[i] = stmt_gist(scop->stmts[i], scop->context,
4037 value_bounds);
4038 if (!scop->stmts[i])
4039 return pet_scop_free(scop);
4042 return scop;
4045 /* Intersect the context of "scop" with "context".
4046 * To ensure that we don't introduce any unnamed parameters in
4047 * the context of "scop", we first remove the unnamed parameters
4048 * from "context".
4050 struct pet_scop *pet_scop_restrict_context(struct pet_scop *scop,
4051 __isl_take isl_set *context)
4053 if (!scop)
4054 goto error;
4056 context = set_project_out_unnamed_params(context);
4057 scop->context = isl_set_intersect(scop->context, context);
4058 if (!scop->context)
4059 return pet_scop_free(scop);
4061 return scop;
4062 error:
4063 isl_set_free(context);
4064 return pet_scop_free(scop);
4067 /* Drop the current context of "scop". That is, replace the context
4068 * by a universal set.
4070 struct pet_scop *pet_scop_reset_context(struct pet_scop *scop)
4072 isl_space *space;
4074 if (!scop)
4075 return NULL;
4077 space = isl_set_get_space(scop->context);
4078 isl_set_free(scop->context);
4079 scop->context = isl_set_universe(space);
4080 if (!scop->context)
4081 return pet_scop_free(scop);
4083 return scop;
4086 /* Append "array" to the arrays of "scop".
4088 struct pet_scop *pet_scop_add_array(struct pet_scop *scop,
4089 struct pet_array *array)
4091 isl_ctx *ctx;
4092 struct pet_array **arrays;
4094 if (!array || !scop)
4095 goto error;
4097 ctx = isl_set_get_ctx(scop->context);
4098 arrays = isl_realloc_array(ctx, scop->arrays, struct pet_array *,
4099 scop->n_array + 1);
4100 if (!arrays)
4101 goto error;
4102 scop->arrays = arrays;
4103 scop->arrays[scop->n_array] = array;
4104 scop->n_array++;
4106 return scop;
4107 error:
4108 pet_array_free(array);
4109 return pet_scop_free(scop);
4112 /* Create and return an implication on filter values equal to "satisfied"
4113 * with extension "map".
4115 static struct pet_implication *new_implication(__isl_take isl_map *map,
4116 int satisfied)
4118 isl_ctx *ctx;
4119 struct pet_implication *implication;
4121 if (!map)
4122 return NULL;
4123 ctx = isl_map_get_ctx(map);
4124 implication = isl_alloc_type(ctx, struct pet_implication);
4125 if (!implication)
4126 goto error;
4128 implication->extension = map;
4129 implication->satisfied = satisfied;
4131 return implication;
4132 error:
4133 isl_map_free(map);
4134 return NULL;
4137 /* Add an implication on filter values equal to "satisfied"
4138 * with extension "map" to "scop".
4140 struct pet_scop *pet_scop_add_implication(struct pet_scop *scop,
4141 __isl_take isl_map *map, int satisfied)
4143 isl_ctx *ctx;
4144 struct pet_implication *implication;
4145 struct pet_implication **implications;
4147 implication = new_implication(map, satisfied);
4148 if (!scop || !implication)
4149 goto error;
4151 ctx = isl_set_get_ctx(scop->context);
4152 implications = isl_realloc_array(ctx, scop->implications,
4153 struct pet_implication *,
4154 scop->n_implication + 1);
4155 if (!implications)
4156 goto error;
4157 scop->implications = implications;
4158 scop->implications[scop->n_implication] = implication;
4159 scop->n_implication++;
4161 return scop;
4162 error:
4163 pet_implication_free(implication);
4164 return pet_scop_free(scop);
4167 /* Given an access expression, check if it is data dependent.
4168 * If so, set *found and abort the search.
4170 static int is_data_dependent(struct pet_expr *expr, void *user)
4172 int *found = user;
4174 if (expr->n_arg) {
4175 *found = 1;
4176 return -1;
4179 return 0;
4182 /* Does "scop" contain any data dependent accesses?
4184 * Check the body of each statement for such accesses.
4186 int pet_scop_has_data_dependent_accesses(struct pet_scop *scop)
4188 int i;
4189 int found = 0;
4191 if (!scop)
4192 return -1;
4194 for (i = 0; i < scop->n_stmt; ++i) {
4195 int r = pet_expr_foreach_access_expr(scop->stmts[i]->body,
4196 &is_data_dependent, &found);
4197 if (r < 0 && !found)
4198 return -1;
4199 if (found)
4200 return found;
4203 return found;
4206 /* Does "scop" contain and data dependent conditions?
4208 int pet_scop_has_data_dependent_conditions(struct pet_scop *scop)
4210 int i;
4212 if (!scop)
4213 return -1;
4215 for (i = 0; i < scop->n_stmt; ++i)
4216 if (scop->stmts[i]->n_arg > 0)
4217 return 1;
4219 return 0;
4222 /* Keep track of the "input" file inside the (extended) "scop".
4224 struct pet_scop *pet_scop_set_input_file(struct pet_scop *scop, FILE *input)
4226 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
4228 if (!scop)
4229 return NULL;
4231 ext->input = input;
4233 return scop;
4236 /* Print the original code corresponding to "scop" to printer "p".
4238 * pet_scop_print_original can only be called from
4239 * a pet_transform_C_source callback. This means that the input
4240 * file is stored in the extended scop and that the printer prints
4241 * to a file.
4243 __isl_give isl_printer *pet_scop_print_original(struct pet_scop *scop,
4244 __isl_take isl_printer *p)
4246 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
4247 FILE *output;
4249 if (!scop || !p)
4250 return isl_printer_free(p);
4252 if (!ext->input)
4253 isl_die(isl_printer_get_ctx(p), isl_error_invalid,
4254 "no input file stored in scop",
4255 return isl_printer_free(p));
4257 output = isl_printer_get_file(p);
4258 if (!output)
4259 return isl_printer_free(p);
4261 if (copy(ext->input, output, scop->start, scop->end) < 0)
4262 return isl_printer_free(p);
4264 return p;