add pet_stmt_build_ast_exprs
[pet.git] / scop.c
blob5468d2d422a409ce14aa29628808fa3b04ec96e7
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"
41 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
43 static char *type_str[] = {
44 [pet_expr_access] = "access",
45 [pet_expr_call] = "call",
46 [pet_expr_cast] = "cast",
47 [pet_expr_double] = "double",
48 [pet_expr_unary] = "unary",
49 [pet_expr_binary] = "binary",
50 [pet_expr_ternary] = "ternary"
53 static char *op_str[] = {
54 [pet_op_add_assign] = "+=",
55 [pet_op_sub_assign] = "-=",
56 [pet_op_mul_assign] = "*=",
57 [pet_op_div_assign] = "/=",
58 [pet_op_assign] = "=",
59 [pet_op_add] = "+",
60 [pet_op_sub] = "-",
61 [pet_op_mul] = "*",
62 [pet_op_div] = "/",
63 [pet_op_mod] = "%",
64 [pet_op_eq] = "==",
65 [pet_op_le] = "<=",
66 [pet_op_lt] = "<",
67 [pet_op_gt] = ">",
68 [pet_op_minus] = "-",
69 [pet_op_post_inc] = "++",
70 [pet_op_post_dec] = "--",
71 [pet_op_pre_inc] = "++",
72 [pet_op_pre_dec] = "--",
73 [pet_op_address_of] = "&",
74 [pet_op_kill] = "kill"
77 /* pet_scop with extra information that is only used during parsing.
79 * In particular, we keep track of conditions under which we want
80 * to skip the rest of the current loop iteration (skip[pet_skip_now])
81 * and of conditions under which we want to skip subsequent
82 * loop iterations (skip[pet_skip_later]).
84 * The conditions are represented as index expressions defined
85 * over a zero-dimensiona domain. The index expression is either
86 * a boolean affine expression or an access to a variable, which
87 * is assumed to attain values zero and one. The condition holds
88 * if the variable has value one or if the affine expression
89 * has value one (typically for only part of the parameter space).
91 * A missing condition (skip[type] == NULL) means that we don't want
92 * to skip anything.
94 struct pet_scop_ext {
95 struct pet_scop scop;
97 isl_multi_pw_aff *skip[2];
100 const char *pet_op_str(enum pet_op_type op)
102 return op_str[op];
105 int pet_op_is_inc_dec(enum pet_op_type op)
107 return op == pet_op_post_inc || op == pet_op_post_dec ||
108 op == pet_op_pre_inc || op == pet_op_pre_dec;
111 const char *pet_type_str(enum pet_expr_type type)
113 return type_str[type];
116 enum pet_op_type pet_str_op(const char *str)
118 int i;
120 for (i = 0; i < ARRAY_SIZE(op_str); ++i)
121 if (!strcmp(op_str[i], str))
122 return i;
124 return -1;
127 enum pet_expr_type pet_str_type(const char *str)
129 int i;
131 for (i = 0; i < ARRAY_SIZE(type_str); ++i)
132 if (!strcmp(type_str[i], str))
133 return i;
135 return -1;
138 /* Construct an access pet_expr from an access relation and an index expression.
139 * By default, it is considered to be a read access.
141 struct pet_expr *pet_expr_from_access_and_index( __isl_take isl_map *access,
142 __isl_take isl_multi_pw_aff *index)
144 isl_ctx *ctx = isl_map_get_ctx(access);
145 struct pet_expr *expr;
147 if (!index || !access)
148 return NULL;
149 expr = isl_calloc_type(ctx, struct pet_expr);
150 if (!expr)
151 goto error;
153 expr->type = pet_expr_access;
154 expr->acc.access = access;
155 expr->acc.index = index;
156 expr->acc.read = 1;
157 expr->acc.write = 0;
159 return expr;
160 error:
161 isl_map_free(access);
162 isl_multi_pw_aff_free(index);
163 return NULL;
166 /* Construct an access pet_expr from an index expression.
167 * By default, the access is considered to be a read access.
169 struct pet_expr *pet_expr_from_index(__isl_take isl_multi_pw_aff *index)
171 isl_map *access;
173 access = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index));
174 return pet_expr_from_access_and_index(access, index);
177 /* Construct an access pet_expr from an index expression and
178 * the depth of the accessed array.
179 * By default, the access is considered to be a read access.
181 * If the number of indices is smaller than the depth of the array,
182 * then we assume that all elements of the remaining dimensions
183 * are accessed.
185 struct pet_expr *pet_expr_from_index_and_depth(
186 __isl_take isl_multi_pw_aff *index, int depth)
188 isl_id *id;
189 isl_map *access;
190 int dim;
192 access = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index));
193 if (!access)
194 goto error;
195 dim = isl_map_dim(access, isl_dim_out);
196 if (dim > depth)
197 isl_die(isl_map_get_ctx(access), isl_error_internal,
198 "number of indices greater than depth",
199 access = isl_map_free(access));
200 if (dim == depth)
201 return pet_expr_from_access_and_index(access, index);
203 id = isl_map_get_tuple_id(access, isl_dim_out);
204 access = isl_map_add_dims(access, isl_dim_out, depth - dim);
205 access = isl_map_set_tuple_id(access, isl_dim_out, id);
207 return pet_expr_from_access_and_index(access, index);
208 error:
209 isl_multi_pw_aff_free(index);
210 return NULL;
213 /* Construct a pet_expr that kills the elements specified by
214 * the index expression "index" and the access relation "access".
216 struct pet_expr *pet_expr_kill_from_access_and_index(__isl_take isl_map *access,
217 __isl_take isl_multi_pw_aff *index)
219 isl_ctx *ctx;
220 struct pet_expr *expr;
222 if (!access || !index)
223 goto error;
225 ctx = isl_multi_pw_aff_get_ctx(index);
226 expr = pet_expr_from_access_and_index(access, index);
227 if (!expr)
228 return NULL;
229 expr->acc.read = 0;
230 return pet_expr_new_unary(ctx, pet_op_kill, expr);
231 error:
232 isl_map_free(access);
233 isl_multi_pw_aff_free(index);
234 return NULL;
237 /* Construct a unary pet_expr that performs "op" on "arg".
239 struct pet_expr *pet_expr_new_unary(isl_ctx *ctx, enum pet_op_type op,
240 struct pet_expr *arg)
242 struct pet_expr *expr;
244 if (!arg)
245 goto error;
246 expr = isl_alloc_type(ctx, struct pet_expr);
247 if (!expr)
248 goto error;
250 expr->type = pet_expr_unary;
251 expr->op = op;
252 expr->n_arg = 1;
253 expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
254 if (!expr->args)
255 goto error;
256 expr->args[pet_un_arg] = arg;
258 return expr;
259 error:
260 pet_expr_free(arg);
261 return NULL;
264 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
266 struct pet_expr *pet_expr_new_binary(isl_ctx *ctx, enum pet_op_type op,
267 struct pet_expr *lhs, struct pet_expr *rhs)
269 struct pet_expr *expr;
271 if (!lhs || !rhs)
272 goto error;
273 expr = isl_alloc_type(ctx, struct pet_expr);
274 if (!expr)
275 goto error;
277 expr->type = pet_expr_binary;
278 expr->op = op;
279 expr->n_arg = 2;
280 expr->args = isl_calloc_array(ctx, struct pet_expr *, 2);
281 if (!expr->args)
282 goto error;
283 expr->args[pet_bin_lhs] = lhs;
284 expr->args[pet_bin_rhs] = rhs;
286 return expr;
287 error:
288 pet_expr_free(lhs);
289 pet_expr_free(rhs);
290 return NULL;
293 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
295 struct pet_expr *pet_expr_new_ternary(isl_ctx *ctx, struct pet_expr *cond,
296 struct pet_expr *lhs, struct pet_expr *rhs)
298 struct pet_expr *expr;
300 if (!cond || !lhs || !rhs)
301 goto error;
302 expr = isl_alloc_type(ctx, struct pet_expr);
303 if (!expr)
304 goto error;
306 expr->type = pet_expr_ternary;
307 expr->n_arg = 3;
308 expr->args = isl_calloc_array(ctx, struct pet_expr *, 3);
309 if (!expr->args)
310 goto error;
311 expr->args[pet_ter_cond] = cond;
312 expr->args[pet_ter_true] = lhs;
313 expr->args[pet_ter_false] = rhs;
315 return expr;
316 error:
317 pet_expr_free(cond);
318 pet_expr_free(lhs);
319 pet_expr_free(rhs);
320 return NULL;
323 /* Construct a call pet_expr that calls function "name" with "n_arg"
324 * arguments. The caller is responsible for filling in the arguments.
326 struct pet_expr *pet_expr_new_call(isl_ctx *ctx, const char *name,
327 unsigned n_arg)
329 struct pet_expr *expr;
331 expr = isl_alloc_type(ctx, struct pet_expr);
332 if (!expr)
333 return NULL;
335 expr->type = pet_expr_call;
336 expr->n_arg = n_arg;
337 expr->name = strdup(name);
338 expr->args = isl_calloc_array(ctx, struct pet_expr *, n_arg);
339 if (!expr->name || !expr->args)
340 return pet_expr_free(expr);
342 return expr;
345 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
347 struct pet_expr *pet_expr_new_cast(isl_ctx *ctx, const char *type_name,
348 struct pet_expr *arg)
350 struct pet_expr *expr;
352 if (!arg)
353 return NULL;
355 expr = isl_alloc_type(ctx, struct pet_expr);
356 if (!expr)
357 goto error;
359 expr->type = pet_expr_cast;
360 expr->n_arg = 1;
361 expr->type_name = strdup(type_name);
362 expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
363 if (!expr->type_name || !expr->args)
364 goto error;
366 expr->args[0] = arg;
368 return expr;
369 error:
370 pet_expr_free(arg);
371 pet_expr_free(expr);
372 return NULL;
375 /* Construct a pet_expr that represents the double "d".
377 struct pet_expr *pet_expr_new_double(isl_ctx *ctx, double val, const char *s)
379 struct pet_expr *expr;
381 expr = isl_calloc_type(ctx, struct pet_expr);
382 if (!expr)
383 return NULL;
385 expr->type = pet_expr_double;
386 expr->d.val = val;
387 expr->d.s = strdup(s);
388 if (!expr->d.s)
389 return pet_expr_free(expr);
391 return expr;
394 void *pet_expr_free(struct pet_expr *expr)
396 int i;
398 if (!expr)
399 return NULL;
401 for (i = 0; i < expr->n_arg; ++i)
402 pet_expr_free(expr->args[i]);
403 free(expr->args);
405 switch (expr->type) {
406 case pet_expr_access:
407 isl_id_free(expr->acc.ref_id);
408 isl_map_free(expr->acc.access);
409 isl_multi_pw_aff_free(expr->acc.index);
410 break;
411 case pet_expr_call:
412 free(expr->name);
413 break;
414 case pet_expr_cast:
415 free(expr->type_name);
416 break;
417 case pet_expr_double:
418 free(expr->d.s);
419 break;
420 case pet_expr_unary:
421 case pet_expr_binary:
422 case pet_expr_ternary:
423 break;
426 free(expr);
427 return NULL;
430 static void expr_dump(struct pet_expr *expr, int indent)
432 int i;
434 if (!expr)
435 return;
437 fprintf(stderr, "%*s", indent, "");
439 switch (expr->type) {
440 case pet_expr_double:
441 fprintf(stderr, "%s\n", expr->d.s);
442 break;
443 case pet_expr_access:
444 isl_id_dump(expr->acc.ref_id);
445 fprintf(stderr, "%*s", indent, "");
446 isl_map_dump(expr->acc.access);
447 fprintf(stderr, "%*s", indent, "");
448 isl_multi_pw_aff_dump(expr->acc.index);
449 fprintf(stderr, "%*sread: %d\n", indent + 2,
450 "", expr->acc.read);
451 fprintf(stderr, "%*swrite: %d\n", indent + 2,
452 "", expr->acc.write);
453 for (i = 0; i < expr->n_arg; ++i)
454 expr_dump(expr->args[i], indent + 2);
455 break;
456 case pet_expr_unary:
457 fprintf(stderr, "%s\n", op_str[expr->op]);
458 expr_dump(expr->args[pet_un_arg], indent + 2);
459 break;
460 case pet_expr_binary:
461 fprintf(stderr, "%s\n", op_str[expr->op]);
462 expr_dump(expr->args[pet_bin_lhs], indent + 2);
463 expr_dump(expr->args[pet_bin_rhs], indent + 2);
464 break;
465 case pet_expr_ternary:
466 fprintf(stderr, "?:\n");
467 expr_dump(expr->args[pet_ter_cond], indent + 2);
468 expr_dump(expr->args[pet_ter_true], indent + 2);
469 expr_dump(expr->args[pet_ter_false], indent + 2);
470 break;
471 case pet_expr_call:
472 fprintf(stderr, "%s/%d\n", expr->name, expr->n_arg);
473 for (i = 0; i < expr->n_arg; ++i)
474 expr_dump(expr->args[i], indent + 2);
475 break;
476 case pet_expr_cast:
477 fprintf(stderr, "(%s)\n", expr->type_name);
478 for (i = 0; i < expr->n_arg; ++i)
479 expr_dump(expr->args[i], indent + 2);
480 break;
484 void pet_expr_dump(struct pet_expr *expr)
486 expr_dump(expr, 0);
489 /* Does "expr" represent an access to an unnamed space, i.e.,
490 * does it represent an affine expression?
492 int pet_expr_is_affine(struct pet_expr *expr)
494 int has_id;
496 if (!expr)
497 return -1;
498 if (expr->type != pet_expr_access)
499 return 0;
501 has_id = isl_map_has_tuple_id(expr->acc.access, isl_dim_out);
502 if (has_id < 0)
503 return -1;
505 return !has_id;
508 /* Return the identifier of the array accessed by "expr".
510 __isl_give isl_id *pet_expr_access_get_id(struct pet_expr *expr)
512 if (!expr)
513 return NULL;
514 if (expr->type != pet_expr_access)
515 return NULL;
516 return isl_map_get_tuple_id(expr->acc.access, isl_dim_out);
519 /* Align the parameters of expr->acc.index and expr->acc.access.
521 struct pet_expr *pet_expr_access_align_params(struct pet_expr *expr)
523 if (!expr)
524 return NULL;
525 if (expr->type != pet_expr_access)
526 return pet_expr_free(expr);
528 expr->acc.access = isl_map_align_params(expr->acc.access,
529 isl_multi_pw_aff_get_space(expr->acc.index));
530 expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
531 isl_map_get_space(expr->acc.access));
532 if (!expr->acc.access || !expr->acc.index)
533 return pet_expr_free(expr);
535 return expr;
538 /* Does "expr" represent an access to a scalar, i.e., zero-dimensional array?
540 int pet_expr_is_scalar_access(struct pet_expr *expr)
542 if (!expr)
543 return -1;
544 if (expr->type != pet_expr_access)
545 return 0;
547 return isl_map_dim(expr->acc.access, isl_dim_out) == 0;
550 /* Return 1 if the two pet_exprs are equivalent.
552 int pet_expr_is_equal(struct pet_expr *expr1, struct pet_expr *expr2)
554 int i;
556 if (!expr1 || !expr2)
557 return 0;
559 if (expr1->type != expr2->type)
560 return 0;
561 if (expr1->n_arg != expr2->n_arg)
562 return 0;
563 for (i = 0; i < expr1->n_arg; ++i)
564 if (!pet_expr_is_equal(expr1->args[i], expr2->args[i]))
565 return 0;
566 switch (expr1->type) {
567 case pet_expr_double:
568 if (strcmp(expr1->d.s, expr2->d.s))
569 return 0;
570 if (expr1->d.val != expr2->d.val)
571 return 0;
572 break;
573 case pet_expr_access:
574 if (expr1->acc.read != expr2->acc.read)
575 return 0;
576 if (expr1->acc.write != expr2->acc.write)
577 return 0;
578 if (expr1->acc.ref_id != expr2->acc.ref_id)
579 return 0;
580 if (!expr1->acc.access || !expr2->acc.access)
581 return 0;
582 if (!isl_map_is_equal(expr1->acc.access, expr2->acc.access))
583 return 0;
584 if (!expr1->acc.index || !expr2->acc.index)
585 return 0;
586 if (!isl_multi_pw_aff_plain_is_equal(expr1->acc.index,
587 expr2->acc.index))
588 return 0;
589 break;
590 case pet_expr_unary:
591 case pet_expr_binary:
592 case pet_expr_ternary:
593 if (expr1->op != expr2->op)
594 return 0;
595 break;
596 case pet_expr_call:
597 if (strcmp(expr1->name, expr2->name))
598 return 0;
599 break;
600 case pet_expr_cast:
601 if (strcmp(expr1->type_name, expr2->type_name))
602 return 0;
603 break;
606 return 1;
609 /* Add extra conditions on the parameters to all access relations in "expr".
611 * The conditions are not added to the index expression. Instead, they
612 * are used to try and simplifty the index expression.
614 struct pet_expr *pet_expr_restrict(struct pet_expr *expr,
615 __isl_take isl_set *cond)
617 int i;
619 if (!expr)
620 goto error;
622 for (i = 0; i < expr->n_arg; ++i) {
623 expr->args[i] = pet_expr_restrict(expr->args[i],
624 isl_set_copy(cond));
625 if (!expr->args[i])
626 goto error;
629 if (expr->type == pet_expr_access) {
630 expr->acc.access = isl_map_intersect_params(expr->acc.access,
631 isl_set_copy(cond));
632 expr->acc.index = isl_multi_pw_aff_gist_params(
633 expr->acc.index, isl_set_copy(cond));
634 if (!expr->acc.access || !expr->acc.index)
635 goto error;
638 isl_set_free(cond);
639 return expr;
640 error:
641 isl_set_free(cond);
642 return pet_expr_free(expr);
645 /* Modify all expressions of type pet_expr_access in "expr"
646 * by calling "fn" on them.
648 struct pet_expr *pet_expr_map_access(struct pet_expr *expr,
649 struct pet_expr *(*fn)(struct pet_expr *expr, void *user),
650 void *user)
652 int i;
654 if (!expr)
655 return NULL;
657 for (i = 0; i < expr->n_arg; ++i) {
658 expr->args[i] = pet_expr_map_access(expr->args[i], fn, user);
659 if (!expr->args[i])
660 return pet_expr_free(expr);
663 if (expr->type == pet_expr_access)
664 expr = fn(expr, user);
666 return expr;
669 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
671 * Return -1 on error (where fn return a negative value is treated as an error).
672 * Otherwise return 0.
674 int pet_expr_foreach_access_expr(struct pet_expr *expr,
675 int (*fn)(struct pet_expr *expr, void *user), void *user)
677 int i;
679 if (!expr)
680 return -1;
682 for (i = 0; i < expr->n_arg; ++i)
683 if (pet_expr_foreach_access_expr(expr->args[i], fn, user) < 0)
684 return -1;
686 if (expr->type == pet_expr_access)
687 return fn(expr, user);
689 return 0;
692 /* Modify the access relation and index expression
693 * of the given access expression
694 * based on the given iteration space transformation.
695 * In particular, precompose the access relation and index expression
696 * with the update function.
698 * If the access has any arguments then the domain of the access relation
699 * is a wrapped mapping from the iteration space to the space of
700 * argument values. We only need to change the domain of this wrapped
701 * mapping, so we extend the input transformation with an identity mapping
702 * on the space of argument values.
704 static struct pet_expr *update_domain(struct pet_expr *expr, void *user)
706 isl_multi_pw_aff *update = user;
707 isl_space *space;
709 update = isl_multi_pw_aff_copy(update);
711 space = isl_map_get_space(expr->acc.access);
712 space = isl_space_domain(space);
713 if (!isl_space_is_wrapping(space))
714 isl_space_free(space);
715 else {
716 isl_multi_pw_aff *id;
717 space = isl_space_unwrap(space);
718 space = isl_space_range(space);
719 space = isl_space_map_from_set(space);
720 id = isl_multi_pw_aff_identity(space);
721 update = isl_multi_pw_aff_product(update, id);
724 expr->acc.access = isl_map_preimage_domain_multi_pw_aff(
725 expr->acc.access,
726 isl_multi_pw_aff_copy(update));
727 expr->acc.index = isl_multi_pw_aff_pullback_multi_pw_aff(
728 expr->acc.index, update);
729 if (!expr->acc.access || !expr->acc.index)
730 return pet_expr_free(expr);
732 return expr;
735 /* Modify all access relations in "expr" by precomposing them with
736 * the given iteration space transformation.
738 static struct pet_expr *expr_update_domain(struct pet_expr *expr,
739 __isl_take isl_multi_pw_aff *update)
741 expr = pet_expr_map_access(expr, &update_domain, update);
742 isl_multi_pw_aff_free(update);
743 return expr;
746 /* Construct a pet_stmt with given line number and statement
747 * number from a pet_expr.
748 * The initial iteration domain is the zero-dimensional universe.
749 * The name of the domain is given by "label" if it is non-NULL.
750 * Otherwise, the name is constructed as S_<id>.
751 * The domains of all access relations are modified to refer
752 * to the statement iteration domain.
754 struct pet_stmt *pet_stmt_from_pet_expr(isl_ctx *ctx, int line,
755 __isl_take isl_id *label, int id, struct pet_expr *expr)
757 struct pet_stmt *stmt;
758 isl_space *dim;
759 isl_set *dom;
760 isl_map *sched;
761 isl_multi_pw_aff *add_name;
762 char name[50];
764 if (!expr)
765 goto error;
767 stmt = isl_calloc_type(ctx, struct pet_stmt);
768 if (!stmt)
769 goto error;
771 dim = isl_space_set_alloc(ctx, 0, 0);
772 if (label)
773 dim = isl_space_set_tuple_id(dim, isl_dim_set, label);
774 else {
775 snprintf(name, sizeof(name), "S_%d", id);
776 dim = isl_space_set_tuple_name(dim, isl_dim_set, name);
778 dom = isl_set_universe(isl_space_copy(dim));
779 sched = isl_map_from_domain(isl_set_copy(dom));
781 dim = isl_space_from_domain(dim);
782 add_name = isl_multi_pw_aff_zero(dim);
783 expr = expr_update_domain(expr, add_name);
785 stmt->line = line;
786 stmt->domain = dom;
787 stmt->schedule = sched;
788 stmt->body = expr;
790 if (!stmt->domain || !stmt->schedule || !stmt->body)
791 return pet_stmt_free(stmt);
793 return stmt;
794 error:
795 isl_id_free(label);
796 return pet_expr_free(expr);
799 void *pet_stmt_free(struct pet_stmt *stmt)
801 int i;
803 if (!stmt)
804 return NULL;
806 isl_set_free(stmt->domain);
807 isl_map_free(stmt->schedule);
808 pet_expr_free(stmt->body);
810 for (i = 0; i < stmt->n_arg; ++i)
811 pet_expr_free(stmt->args[i]);
812 free(stmt->args);
814 free(stmt);
815 return NULL;
818 static void stmt_dump(struct pet_stmt *stmt, int indent)
820 int i;
822 if (!stmt)
823 return;
825 fprintf(stderr, "%*s%d\n", indent, "", stmt->line);
826 fprintf(stderr, "%*s", indent, "");
827 isl_set_dump(stmt->domain);
828 fprintf(stderr, "%*s", indent, "");
829 isl_map_dump(stmt->schedule);
830 expr_dump(stmt->body, indent);
831 for (i = 0; i < stmt->n_arg; ++i)
832 expr_dump(stmt->args[i], indent + 2);
835 void pet_stmt_dump(struct pet_stmt *stmt)
837 stmt_dump(stmt, 0);
840 struct pet_array *pet_array_free(struct pet_array *array)
842 if (!array)
843 return NULL;
845 isl_set_free(array->context);
846 isl_set_free(array->extent);
847 isl_set_free(array->value_bounds);
848 free(array->element_type);
850 free(array);
851 return NULL;
854 void pet_array_dump(struct pet_array *array)
856 if (!array)
857 return;
859 isl_set_dump(array->context);
860 isl_set_dump(array->extent);
861 isl_set_dump(array->value_bounds);
862 fprintf(stderr, "%s %s\n", array->element_type,
863 array->live_out ? "live-out" : "");
866 /* Alloc a pet_scop structure, with extra room for information that
867 * is only used during parsing.
869 struct pet_scop *pet_scop_alloc(isl_ctx *ctx)
871 return &isl_calloc_type(ctx, struct pet_scop_ext)->scop;
874 /* Construct a pet_scop with room for n statements.
876 static struct pet_scop *scop_alloc(isl_ctx *ctx, int n)
878 isl_space *space;
879 struct pet_scop *scop;
881 scop = pet_scop_alloc(ctx);
882 if (!scop)
883 return NULL;
885 space = isl_space_params_alloc(ctx, 0);
886 scop->context = isl_set_universe(isl_space_copy(space));
887 scop->context_value = isl_set_universe(space);
888 scop->stmts = isl_calloc_array(ctx, struct pet_stmt *, n);
889 if (!scop->context || !scop->stmts)
890 return pet_scop_free(scop);
892 scop->n_stmt = n;
894 return scop;
897 struct pet_scop *pet_scop_empty(isl_ctx *ctx)
899 return scop_alloc(ctx, 0);
902 /* Update "context" with respect to the valid parameter values for "access".
904 static __isl_give isl_set *access_extract_context(__isl_keep isl_map *access,
905 __isl_take isl_set *context)
907 context = isl_set_intersect(context,
908 isl_map_params(isl_map_copy(access)));
909 return context;
912 /* Update "context" with respect to the valid parameter values for "expr".
914 * If "expr" represents a ternary operator, then a parameter value
915 * needs to be valid for the condition and for at least one of the
916 * remaining two arguments.
917 * If the condition is an affine expression, then we can be a bit more specific.
918 * The parameter then has to be valid for the second argument for
919 * non-zero accesses and valid for the third argument for zero accesses.
921 static __isl_give isl_set *expr_extract_context(struct pet_expr *expr,
922 __isl_take isl_set *context)
924 int i;
926 if (expr->type == pet_expr_ternary) {
927 int is_aff;
928 isl_set *context1, *context2;
930 is_aff = pet_expr_is_affine(expr->args[0]);
931 if (is_aff < 0)
932 goto error;
934 context = expr_extract_context(expr->args[0], context);
935 context1 = expr_extract_context(expr->args[1],
936 isl_set_copy(context));
937 context2 = expr_extract_context(expr->args[2], context);
939 if (is_aff) {
940 isl_map *access;
941 isl_set *zero_set;
943 access = isl_map_copy(expr->args[0]->acc.access);
944 access = isl_map_fix_si(access, isl_dim_out, 0, 0);
945 zero_set = isl_map_params(access);
946 context1 = isl_set_subtract(context1,
947 isl_set_copy(zero_set));
948 context2 = isl_set_intersect(context2, zero_set);
951 context = isl_set_union(context1, context2);
952 context = isl_set_coalesce(context);
954 return context;
957 for (i = 0; i < expr->n_arg; ++i)
958 context = expr_extract_context(expr->args[i], context);
960 if (expr->type == pet_expr_access)
961 context = access_extract_context(expr->acc.access, context);
963 return context;
964 error:
965 isl_set_free(context);
966 return NULL;
969 /* Update "context" with respect to the valid parameter values for "stmt".
971 static __isl_give isl_set *stmt_extract_context(struct pet_stmt *stmt,
972 __isl_take isl_set *context)
974 int i;
976 for (i = 0; i < stmt->n_arg; ++i)
977 context = expr_extract_context(stmt->args[i], context);
979 context = expr_extract_context(stmt->body, context);
981 return context;
984 /* Construct a pet_scop that contains the given pet_stmt.
986 struct pet_scop *pet_scop_from_pet_stmt(isl_ctx *ctx, struct pet_stmt *stmt)
988 struct pet_scop *scop;
990 if (!stmt)
991 return NULL;
993 scop = scop_alloc(ctx, 1);
994 if (!scop)
995 goto error;
997 scop->context = stmt_extract_context(stmt, scop->context);
998 if (!scop->context)
999 goto error;
1001 scop->stmts[0] = stmt;
1003 return scop;
1004 error:
1005 pet_stmt_free(stmt);
1006 pet_scop_free(scop);
1007 return NULL;
1010 /* Does "mpa" represent an access to an element of an unnamed space, i.e.,
1011 * does it represent an affine expression?
1013 static int multi_pw_aff_is_affine(__isl_keep isl_multi_pw_aff *mpa)
1015 int has_id;
1017 has_id = isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out);
1018 if (has_id < 0)
1019 return -1;
1021 return !has_id;
1024 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
1026 static __isl_give isl_pw_aff *indicator_function(__isl_take isl_set *set,
1027 __isl_take isl_set *dom)
1029 isl_pw_aff *pa;
1030 pa = isl_set_indicator_function(set);
1031 pa = isl_pw_aff_intersect_domain(pa, dom);
1032 return pa;
1035 /* Return "lhs || rhs", defined on the shared definition domain.
1037 static __isl_give isl_pw_aff *pw_aff_or(__isl_take isl_pw_aff *lhs,
1038 __isl_take isl_pw_aff *rhs)
1040 isl_set *cond;
1041 isl_set *dom;
1043 dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs)),
1044 isl_pw_aff_domain(isl_pw_aff_copy(rhs)));
1045 cond = isl_set_union(isl_pw_aff_non_zero_set(lhs),
1046 isl_pw_aff_non_zero_set(rhs));
1047 cond = isl_set_coalesce(cond);
1048 return indicator_function(cond, dom);
1051 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
1052 * ext may be equal to either ext1 or ext2.
1054 * The two skips that need to be combined are assumed to be affine expressions.
1056 * We need to skip in ext if we need to skip in either ext1 or ext2.
1057 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
1059 static struct pet_scop_ext *combine_skips(struct pet_scop_ext *ext,
1060 struct pet_scop_ext *ext1, struct pet_scop_ext *ext2,
1061 enum pet_skip type)
1063 isl_pw_aff *skip, *skip1, *skip2;
1065 if (!ext)
1066 return NULL;
1067 if (!ext1->skip[type] && !ext2->skip[type])
1068 return ext;
1069 if (!ext1->skip[type]) {
1070 if (ext == ext2)
1071 return ext;
1072 ext->skip[type] = ext2->skip[type];
1073 ext2->skip[type] = NULL;
1074 return ext;
1076 if (!ext2->skip[type]) {
1077 if (ext == ext1)
1078 return ext;
1079 ext->skip[type] = ext1->skip[type];
1080 ext1->skip[type] = NULL;
1081 return ext;
1084 if (!multi_pw_aff_is_affine(ext1->skip[type]) ||
1085 !multi_pw_aff_is_affine(ext2->skip[type]))
1086 isl_die(isl_multi_pw_aff_get_ctx(ext1->skip[type]),
1087 isl_error_internal, "can only combine affine skips",
1088 return pet_scop_free(&ext->scop));
1090 skip1 = isl_multi_pw_aff_get_pw_aff(ext1->skip[type], 0);
1091 skip2 = isl_multi_pw_aff_get_pw_aff(ext2->skip[type], 0);
1092 skip = pw_aff_or(skip1, skip2);
1093 isl_multi_pw_aff_free(ext1->skip[type]);
1094 ext1->skip[type] = NULL;
1095 isl_multi_pw_aff_free(ext2->skip[type]);
1096 ext2->skip[type] = NULL;
1097 ext->skip[type] = isl_multi_pw_aff_from_pw_aff(skip);
1098 if (!ext->skip[type])
1099 return pet_scop_free(&ext->scop);
1101 return ext;
1104 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
1105 * where type takes on the values pet_skip_now and pet_skip_later.
1106 * scop may be equal to either scop1 or scop2.
1108 static struct pet_scop *scop_combine_skips(struct pet_scop *scop,
1109 struct pet_scop *scop1, struct pet_scop *scop2)
1111 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1112 struct pet_scop_ext *ext1 = (struct pet_scop_ext *) scop1;
1113 struct pet_scop_ext *ext2 = (struct pet_scop_ext *) scop2;
1115 ext = combine_skips(ext, ext1, ext2, pet_skip_now);
1116 ext = combine_skips(ext, ext1, ext2, pet_skip_later);
1117 return &ext->scop;
1120 /* Update scop->start and scop->end to include the region from "start"
1121 * to "end". In particular, if scop->end == 0, then "scop" does not
1122 * have any offset information yet and we simply take the information
1123 * from "start" and "end". Otherwise, we update the fields if the
1124 * region from "start" to "end" is not already included.
1126 struct pet_scop *pet_scop_update_start_end(struct pet_scop *scop,
1127 unsigned start, unsigned end)
1129 if (!scop)
1130 return NULL;
1131 if (scop->end == 0) {
1132 scop->start = start;
1133 scop->end = end;
1134 } else {
1135 if (start < scop->start)
1136 scop->start = start;
1137 if (end > scop->end)
1138 scop->end = end;
1141 return scop;
1144 /* Does "implication" appear in the list of implications of "scop"?
1146 static int is_known_implication(struct pet_scop *scop,
1147 struct pet_implication *implication)
1149 int i;
1151 for (i = 0; i < scop->n_implication; ++i) {
1152 struct pet_implication *pi = scop->implications[i];
1153 int equal;
1155 if (pi->satisfied != implication->satisfied)
1156 continue;
1157 equal = isl_map_is_equal(pi->extension, implication->extension);
1158 if (equal < 0)
1159 return -1;
1160 if (equal)
1161 return 1;
1164 return 0;
1167 /* Store the concatenation of the impliciations of "scop1" and "scop2"
1168 * in "scop", removing duplicates (i.e., implications in "scop2" that
1169 * already appear in "scop1").
1171 static struct pet_scop *scop_collect_implications(isl_ctx *ctx,
1172 struct pet_scop *scop, struct pet_scop *scop1, struct pet_scop *scop2)
1174 int i, j;
1176 if (!scop)
1177 return NULL;
1179 if (scop2->n_implication == 0) {
1180 scop->n_implication = scop1->n_implication;
1181 scop->implications = scop1->implications;
1182 scop1->n_implication = 0;
1183 scop1->implications = NULL;
1184 return scop;
1187 if (scop1->n_implication == 0) {
1188 scop->n_implication = scop2->n_implication;
1189 scop->implications = scop2->implications;
1190 scop2->n_implication = 0;
1191 scop2->implications = NULL;
1192 return scop;
1195 scop->implications = isl_calloc_array(ctx, struct pet_implication *,
1196 scop1->n_implication + scop2->n_implication);
1197 if (!scop->implications)
1198 return pet_scop_free(scop);
1200 for (i = 0; i < scop1->n_implication; ++i) {
1201 scop->implications[i] = scop1->implications[i];
1202 scop1->implications[i] = NULL;
1205 scop->n_implication = scop1->n_implication;
1206 j = scop1->n_implication;
1207 for (i = 0; i < scop2->n_implication; ++i) {
1208 int known;
1210 known = is_known_implication(scop, scop2->implications[i]);
1211 if (known < 0)
1212 return pet_scop_free(scop);
1213 if (known)
1214 continue;
1215 scop->implications[j++] = scop2->implications[i];
1216 scop2->implications[i] = NULL;
1218 scop->n_implication = j;
1220 return scop;
1223 /* Combine the offset information of "scop1" and "scop2" into "scop".
1225 static struct pet_scop *scop_combine_start_end(struct pet_scop *scop,
1226 struct pet_scop *scop1, struct pet_scop *scop2)
1228 if (scop1->end)
1229 scop = pet_scop_update_start_end(scop,
1230 scop1->start, scop1->end);
1231 if (scop2->end)
1232 scop = pet_scop_update_start_end(scop,
1233 scop2->start, scop2->end);
1234 return scop;
1237 /* Construct a pet_scop that contains the offset information,
1238 * arrays, statements and skip information in "scop1" and "scop2".
1240 static struct pet_scop *pet_scop_add(isl_ctx *ctx, struct pet_scop *scop1,
1241 struct pet_scop *scop2)
1243 int i;
1244 struct pet_scop *scop = NULL;
1246 if (!scop1 || !scop2)
1247 goto error;
1249 if (scop1->n_stmt == 0) {
1250 scop2 = scop_combine_skips(scop2, scop1, scop2);
1251 pet_scop_free(scop1);
1252 return scop2;
1255 if (scop2->n_stmt == 0) {
1256 scop1 = scop_combine_skips(scop1, scop1, scop2);
1257 pet_scop_free(scop2);
1258 return scop1;
1261 scop = scop_alloc(ctx, scop1->n_stmt + scop2->n_stmt);
1262 if (!scop)
1263 goto error;
1265 scop->arrays = isl_calloc_array(ctx, struct pet_array *,
1266 scop1->n_array + scop2->n_array);
1267 if (!scop->arrays)
1268 goto error;
1269 scop->n_array = scop1->n_array + scop2->n_array;
1271 for (i = 0; i < scop1->n_stmt; ++i) {
1272 scop->stmts[i] = scop1->stmts[i];
1273 scop1->stmts[i] = NULL;
1276 for (i = 0; i < scop2->n_stmt; ++i) {
1277 scop->stmts[scop1->n_stmt + i] = scop2->stmts[i];
1278 scop2->stmts[i] = NULL;
1281 for (i = 0; i < scop1->n_array; ++i) {
1282 scop->arrays[i] = scop1->arrays[i];
1283 scop1->arrays[i] = NULL;
1286 for (i = 0; i < scop2->n_array; ++i) {
1287 scop->arrays[scop1->n_array + i] = scop2->arrays[i];
1288 scop2->arrays[i] = NULL;
1291 scop = scop_collect_implications(ctx, scop, scop1, scop2);
1292 scop = pet_scop_restrict_context(scop, isl_set_copy(scop1->context));
1293 scop = pet_scop_restrict_context(scop, isl_set_copy(scop2->context));
1294 scop = scop_combine_skips(scop, scop1, scop2);
1295 scop = scop_combine_start_end(scop, scop1, scop2);
1297 pet_scop_free(scop1);
1298 pet_scop_free(scop2);
1299 return scop;
1300 error:
1301 pet_scop_free(scop1);
1302 pet_scop_free(scop2);
1303 pet_scop_free(scop);
1304 return NULL;
1307 /* Apply the skip condition "skip" to "scop".
1308 * That is, make sure "scop" is not executed when the condition holds.
1310 * If "skip" is an affine expression, we add the conditions under
1311 * which the expression is zero to the iteration domains.
1312 * Otherwise, we add a filter on the variable attaining the value zero.
1314 static struct pet_scop *restrict_skip(struct pet_scop *scop,
1315 __isl_take isl_multi_pw_aff *skip)
1317 isl_set *zero;
1318 isl_pw_aff *pa;
1319 int is_aff;
1321 if (!scop || !skip)
1322 goto error;
1324 is_aff = multi_pw_aff_is_affine(skip);
1325 if (is_aff < 0)
1326 goto error;
1328 if (!is_aff)
1329 return pet_scop_filter(scop, skip, 0);
1331 pa = isl_multi_pw_aff_get_pw_aff(skip, 0);
1332 isl_multi_pw_aff_free(skip);
1333 zero = isl_set_params(isl_pw_aff_zero_set(pa));
1334 scop = pet_scop_restrict(scop, zero);
1336 return scop;
1337 error:
1338 isl_multi_pw_aff_free(skip);
1339 return pet_scop_free(scop);
1342 /* Construct a pet_scop that contains the arrays, statements and
1343 * skip information in "scop1" and "scop2", where the two scops
1344 * are executed "in sequence". That is, breaks and continues
1345 * in scop1 have an effect on scop2.
1347 struct pet_scop *pet_scop_add_seq(isl_ctx *ctx, struct pet_scop *scop1,
1348 struct pet_scop *scop2)
1350 if (scop1 && pet_scop_has_skip(scop1, pet_skip_now))
1351 scop2 = restrict_skip(scop2,
1352 pet_scop_get_skip(scop1, pet_skip_now));
1353 return pet_scop_add(ctx, scop1, scop2);
1356 /* Construct a pet_scop that contains the arrays, statements and
1357 * skip information in "scop1" and "scop2", where the two scops
1358 * are executed "in parallel". That is, any break or continue
1359 * in scop1 has no effect on scop2.
1361 struct pet_scop *pet_scop_add_par(isl_ctx *ctx, struct pet_scop *scop1,
1362 struct pet_scop *scop2)
1364 return pet_scop_add(ctx, scop1, scop2);
1367 void *pet_implication_free(struct pet_implication *implication)
1369 int i;
1371 if (!implication)
1372 return NULL;
1374 isl_map_free(implication->extension);
1376 free(implication);
1377 return NULL;
1380 void *pet_scop_free(struct pet_scop *scop)
1382 int i;
1383 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1385 if (!scop)
1386 return NULL;
1387 isl_set_free(scop->context);
1388 isl_set_free(scop->context_value);
1389 if (scop->arrays)
1390 for (i = 0; i < scop->n_array; ++i)
1391 pet_array_free(scop->arrays[i]);
1392 free(scop->arrays);
1393 if (scop->stmts)
1394 for (i = 0; i < scop->n_stmt; ++i)
1395 pet_stmt_free(scop->stmts[i]);
1396 free(scop->stmts);
1397 if (scop->implications)
1398 for (i = 0; i < scop->n_implication; ++i)
1399 pet_implication_free(scop->implications[i]);
1400 free(scop->implications);
1401 isl_multi_pw_aff_free(ext->skip[pet_skip_now]);
1402 isl_multi_pw_aff_free(ext->skip[pet_skip_later]);
1403 free(scop);
1404 return NULL;
1407 void pet_implication_dump(struct pet_implication *implication)
1409 if (!implication)
1410 return;
1412 fprintf(stderr, "%d\n", implication->satisfied);
1413 isl_map_dump(implication->extension);
1416 void pet_scop_dump(struct pet_scop *scop)
1418 int i;
1419 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1421 if (!scop)
1422 return;
1424 isl_set_dump(scop->context);
1425 isl_set_dump(scop->context_value);
1426 for (i = 0; i < scop->n_array; ++i)
1427 pet_array_dump(scop->arrays[i]);
1428 for (i = 0; i < scop->n_stmt; ++i)
1429 pet_stmt_dump(scop->stmts[i]);
1430 for (i = 0; i < scop->n_implication; ++i)
1431 pet_implication_dump(scop->implications[i]);
1433 if (ext->skip[0]) {
1434 fprintf(stderr, "skip\n");
1435 isl_multi_pw_aff_dump(ext->skip[0]);
1436 isl_multi_pw_aff_dump(ext->skip[1]);
1440 /* Return 1 if the two pet_arrays are equivalent.
1442 * We don't compare element_size as this may be target dependent.
1444 int pet_array_is_equal(struct pet_array *array1, struct pet_array *array2)
1446 if (!array1 || !array2)
1447 return 0;
1449 if (!isl_set_is_equal(array1->context, array2->context))
1450 return 0;
1451 if (!isl_set_is_equal(array1->extent, array2->extent))
1452 return 0;
1453 if (!!array1->value_bounds != !!array2->value_bounds)
1454 return 0;
1455 if (array1->value_bounds &&
1456 !isl_set_is_equal(array1->value_bounds, array2->value_bounds))
1457 return 0;
1458 if (strcmp(array1->element_type, array2->element_type))
1459 return 0;
1460 if (array1->live_out != array2->live_out)
1461 return 0;
1462 if (array1->uniquely_defined != array2->uniquely_defined)
1463 return 0;
1464 if (array1->declared != array2->declared)
1465 return 0;
1466 if (array1->exposed != array2->exposed)
1467 return 0;
1469 return 1;
1472 /* Return 1 if the two pet_stmts are equivalent.
1474 int pet_stmt_is_equal(struct pet_stmt *stmt1, struct pet_stmt *stmt2)
1476 int i;
1478 if (!stmt1 || !stmt2)
1479 return 0;
1481 if (stmt1->line != stmt2->line)
1482 return 0;
1483 if (!isl_set_is_equal(stmt1->domain, stmt2->domain))
1484 return 0;
1485 if (!isl_map_is_equal(stmt1->schedule, stmt2->schedule))
1486 return 0;
1487 if (!pet_expr_is_equal(stmt1->body, stmt2->body))
1488 return 0;
1489 if (stmt1->n_arg != stmt2->n_arg)
1490 return 0;
1491 for (i = 0; i < stmt1->n_arg; ++i) {
1492 if (!pet_expr_is_equal(stmt1->args[i], stmt2->args[i]))
1493 return 0;
1496 return 1;
1499 /* Return 1 if the two pet_implications are equivalent.
1501 int pet_implication_is_equal(struct pet_implication *implication1,
1502 struct pet_implication *implication2)
1504 if (!implication1 || !implication2)
1505 return 0;
1507 if (implication1->satisfied != implication2->satisfied)
1508 return 0;
1509 if (!isl_map_is_equal(implication1->extension, implication2->extension))
1510 return 0;
1512 return 1;
1515 /* Return 1 if the two pet_scops are equivalent.
1517 int pet_scop_is_equal(struct pet_scop *scop1, struct pet_scop *scop2)
1519 int i;
1521 if (!scop1 || !scop2)
1522 return 0;
1524 if (!isl_set_is_equal(scop1->context, scop2->context))
1525 return 0;
1526 if (!isl_set_is_equal(scop1->context_value, scop2->context_value))
1527 return 0;
1529 if (scop1->n_array != scop2->n_array)
1530 return 0;
1531 for (i = 0; i < scop1->n_array; ++i)
1532 if (!pet_array_is_equal(scop1->arrays[i], scop2->arrays[i]))
1533 return 0;
1535 if (scop1->n_stmt != scop2->n_stmt)
1536 return 0;
1537 for (i = 0; i < scop1->n_stmt; ++i)
1538 if (!pet_stmt_is_equal(scop1->stmts[i], scop2->stmts[i]))
1539 return 0;
1541 if (scop1->n_implication != scop2->n_implication)
1542 return 0;
1543 for (i = 0; i < scop1->n_implication; ++i)
1544 if (!pet_implication_is_equal(scop1->implications[i],
1545 scop2->implications[i]))
1546 return 0;
1548 return 1;
1551 /* Prefix the schedule of "stmt" with an extra dimension with constant
1552 * value "pos".
1554 struct pet_stmt *pet_stmt_prefix(struct pet_stmt *stmt, int pos)
1556 if (!stmt)
1557 return NULL;
1559 stmt->schedule = isl_map_insert_dims(stmt->schedule, isl_dim_out, 0, 1);
1560 stmt->schedule = isl_map_fix_si(stmt->schedule, isl_dim_out, 0, pos);
1561 if (!stmt->schedule)
1562 return pet_stmt_free(stmt);
1564 return stmt;
1567 /* Prefix the schedules of all statements in "scop" with an extra
1568 * dimension with constant value "pos".
1570 struct pet_scop *pet_scop_prefix(struct pet_scop *scop, int pos)
1572 int i;
1574 if (!scop)
1575 return NULL;
1577 for (i = 0; i < scop->n_stmt; ++i) {
1578 scop->stmts[i] = pet_stmt_prefix(scop->stmts[i], pos);
1579 if (!scop->stmts[i])
1580 return pet_scop_free(scop);
1583 return scop;
1586 /* Given a set with a parameter at "param_pos" that refers to the
1587 * iterator, "move" the iterator to the first set dimension.
1588 * That is, essentially equate the parameter to the first set dimension
1589 * and then project it out.
1591 * The first set dimension may however refer to a virtual iterator,
1592 * while the parameter refers to the "real" iterator.
1593 * We therefore need to take into account the affine expression "iv_map", which
1594 * expresses the real iterator in terms of the virtual iterator.
1595 * In particular, we equate the set dimension to the input of the map
1596 * and the parameter to the output of the map and then project out
1597 * everything we don't need anymore.
1599 static __isl_give isl_set *internalize_iv(__isl_take isl_set *set,
1600 int param_pos, __isl_take isl_aff *iv_map)
1602 isl_map *map, *map2;
1603 map = isl_map_from_domain(set);
1604 map = isl_map_add_dims(map, isl_dim_out, 1);
1605 map = isl_map_equate(map, isl_dim_in, 0, isl_dim_out, 0);
1606 map2 = isl_map_from_aff(iv_map);
1607 map2 = isl_map_align_params(map2, isl_map_get_space(map));
1608 map = isl_map_apply_range(map, map2);
1609 map = isl_map_equate(map, isl_dim_param, param_pos, isl_dim_out, 0);
1610 map = isl_map_project_out(map, isl_dim_param, param_pos, 1);
1611 return isl_map_domain(map);
1614 /* Data used in embed_access.
1615 * extend adds an iterator to the iteration domain (through precomposition).
1616 * iv_map expresses the real iterator in terms of the virtual iterator
1617 * var_id represents the induction variable of the corresponding loop
1619 struct pet_embed_access {
1620 isl_multi_pw_aff *extend;
1621 isl_aff *iv_map;
1622 isl_id *var_id;
1625 /* Given an index expression, return an expression for the outer iterator.
1627 static __isl_give isl_aff *index_outer_iterator(
1628 __isl_take isl_multi_pw_aff *index)
1630 isl_space *space;
1631 isl_local_space *ls;
1633 space = isl_multi_pw_aff_get_domain_space(index);
1634 isl_multi_pw_aff_free(index);
1636 ls = isl_local_space_from_space(space);
1637 return isl_aff_var_on_domain(ls, isl_dim_set, 0);
1640 /* Replace an index expression that references the new (outer) iterator variable
1641 * by one that references the corresponding (real) iterator.
1643 * The input index expression is of the form
1645 * { S[i',...] -> i[] }
1647 * where i' refers to the virtual iterator.
1649 * iv_map is of the form
1651 * { [i'] -> [i] }
1653 * Return the index expression
1655 * { S[i',...] -> [i] }
1657 static __isl_give isl_multi_pw_aff *replace_by_iterator(
1658 __isl_take isl_multi_pw_aff *index, __isl_take isl_aff *iv_map)
1660 isl_space *space;
1661 isl_aff *aff;
1663 aff = index_outer_iterator(index);
1664 space = isl_aff_get_space(aff);
1665 iv_map = isl_aff_align_params(iv_map, space);
1666 aff = isl_aff_pullback_aff(iv_map, aff);
1668 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
1671 /* Given an index expression "index" that refers to the (real) iterator
1672 * through the parameter at position "pos", plug in "iv_map", expressing
1673 * the real iterator in terms of the virtual (outer) iterator.
1675 * In particular, the index expression is of the form
1677 * [..., i, ...] -> { S[i',...] -> ... i ... }
1679 * where i refers to the real iterator and i' refers to the virtual iterator.
1681 * iv_map is of the form
1683 * { [i'] -> [i] }
1685 * Return the index expression
1687 * [..., ...] -> { S[i',...] -> ... iv_map(i') ... }
1690 * We first move the parameter to the input
1692 * [..., ...] -> { [i, i',...] -> ... i ... }
1694 * and construct
1696 * { S[i',...] -> [i=iv_map(i'), i', ...] }
1698 * and then combine the two to obtain the desired result.
1700 static __isl_give isl_multi_pw_aff *index_internalize_iv(
1701 __isl_take isl_multi_pw_aff *index, int pos, __isl_take isl_aff *iv_map)
1703 isl_space *space = isl_multi_pw_aff_get_domain_space(index);
1704 isl_multi_aff *ma;
1706 space = isl_space_drop_dims(space, isl_dim_param, pos, 1);
1707 index = isl_multi_pw_aff_move_dims(index, isl_dim_in, 0,
1708 isl_dim_param, pos, 1);
1710 space = isl_space_map_from_set(space);
1711 ma = isl_multi_aff_identity(isl_space_copy(space));
1712 iv_map = isl_aff_align_params(iv_map, space);
1713 iv_map = isl_aff_pullback_aff(iv_map, isl_multi_aff_get_aff(ma, 0));
1714 ma = isl_multi_aff_flat_range_product(
1715 isl_multi_aff_from_aff(iv_map), ma);
1716 index = isl_multi_pw_aff_pullback_multi_aff(index, ma);
1718 return index;
1721 /* Embed the given index expression in an extra outer loop.
1722 * The domain of the index expression has already been updated.
1724 * If the access refers to the induction variable, then it is
1725 * turned into an access to the set of integers with index (and value)
1726 * equal to the induction variable.
1728 * If the accessed array is a virtual array (with user
1729 * pointer equal to NULL), as created by create_test_index,
1730 * then it is extended along with the domain of the index expression.
1732 static __isl_give isl_multi_pw_aff *embed_index_expression(
1733 __isl_take isl_multi_pw_aff *index, struct pet_embed_access *data)
1735 isl_id *array_id = NULL;
1736 int pos;
1738 if (isl_multi_pw_aff_has_tuple_id(index, isl_dim_out))
1739 array_id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
1740 if (array_id == data->var_id) {
1741 index = replace_by_iterator(index, isl_aff_copy(data->iv_map));
1742 } else if (array_id && !isl_id_get_user(array_id)) {
1743 isl_aff *aff;
1744 isl_multi_pw_aff *mpa;
1746 aff = index_outer_iterator(isl_multi_pw_aff_copy(index));
1747 mpa = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
1748 index = isl_multi_pw_aff_flat_range_product(mpa, index);
1749 index = isl_multi_pw_aff_set_tuple_id(index, isl_dim_out,
1750 isl_id_copy(array_id));
1752 isl_id_free(array_id);
1754 pos = isl_multi_pw_aff_find_dim_by_id(index,
1755 isl_dim_param, data->var_id);
1756 if (pos >= 0)
1757 index = index_internalize_iv(index, pos,
1758 isl_aff_copy(data->iv_map));
1759 index = isl_multi_pw_aff_set_dim_id(index, isl_dim_in, 0,
1760 isl_id_copy(data->var_id));
1762 return index;
1765 /* Embed the given access relation in an extra outer loop.
1766 * The domain of the access relation has already been updated.
1768 * If the access refers to the induction variable, then it is
1769 * turned into an access to the set of integers with index (and value)
1770 * equal to the induction variable.
1772 * If the induction variable appears in the constraints (as a parameter),
1773 * then the parameter is equated to the newly introduced iteration
1774 * domain dimension and subsequently projected out.
1776 * Similarly, if the accessed array is a virtual array (with user
1777 * pointer equal to NULL), as created by create_test_index,
1778 * then it is extended along with the domain of the access.
1780 static __isl_give isl_map *embed_access_relation(__isl_take isl_map *access,
1781 struct pet_embed_access *data)
1783 isl_id *array_id = NULL;
1784 int pos;
1786 if (isl_map_has_tuple_id(access, isl_dim_out))
1787 array_id = isl_map_get_tuple_id(access, isl_dim_out);
1788 if (array_id == data->var_id ||
1789 (array_id && !isl_id_get_user(array_id))) {
1790 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
1791 access = isl_map_equate(access,
1792 isl_dim_in, 0, isl_dim_out, 0);
1793 if (array_id == data->var_id)
1794 access = isl_map_apply_range(access,
1795 isl_map_from_aff(isl_aff_copy(data->iv_map)));
1796 else
1797 access = isl_map_set_tuple_id(access, isl_dim_out,
1798 isl_id_copy(array_id));
1800 isl_id_free(array_id);
1802 pos = isl_map_find_dim_by_id(access, isl_dim_param, data->var_id);
1803 if (pos >= 0) {
1804 isl_set *set = isl_map_wrap(access);
1805 set = internalize_iv(set, pos, isl_aff_copy(data->iv_map));
1806 access = isl_set_unwrap(set);
1808 access = isl_map_set_dim_id(access, isl_dim_in, 0,
1809 isl_id_copy(data->var_id));
1811 return access;
1814 /* Given an access expression, embed the associated access relation and
1815 * index expression in an extra outer loop.
1817 * We first update the domains to insert the extra dimension and
1818 * then update the access relation and index expression to take
1819 * into account the mapping "iv_map" from virtual iterator
1820 * to real iterator.
1822 static struct pet_expr *embed_access(struct pet_expr *expr, void *user)
1824 int dim;
1825 struct pet_embed_access *data = user;
1827 expr = update_domain(expr, data->extend);
1828 if (!expr)
1829 return NULL;
1831 expr->acc.access = embed_access_relation(expr->acc.access, data);
1832 expr->acc.index = embed_index_expression(expr->acc.index, data);
1833 if (!expr->acc.access || !expr->acc.index)
1834 return pet_expr_free(expr);
1836 return expr;
1839 /* Embed all access subexpressions of "expr" in an extra loop.
1840 * "extend" inserts an outer loop iterator in the iteration domains
1841 * (through precomposition).
1842 * "iv_map" expresses the real iterator in terms of the virtual iterator
1843 * "var_id" represents the induction variable.
1845 static struct pet_expr *expr_embed(struct pet_expr *expr,
1846 __isl_take isl_multi_pw_aff *extend, __isl_take isl_aff *iv_map,
1847 __isl_keep isl_id *var_id)
1849 struct pet_embed_access data =
1850 { .extend = extend, .iv_map = iv_map, .var_id = var_id };
1852 expr = pet_expr_map_access(expr, &embed_access, &data);
1853 isl_aff_free(iv_map);
1854 isl_multi_pw_aff_free(extend);
1855 return expr;
1858 /* Embed the given pet_stmt in an extra outer loop with iteration domain
1859 * "dom" and schedule "sched". "var_id" represents the induction variable
1860 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
1861 * That is, it expresses the iterator that some of the parameters in "stmt"
1862 * may refer to in terms of the iterator used in "dom" and
1863 * the domain of "sched".
1865 * The iteration domain and schedule of the statement are updated
1866 * according to the iteration domain and schedule of the new loop.
1867 * If stmt->domain is a wrapped map, then the iteration domain
1868 * is the domain of this map, so we need to be careful to adjust
1869 * this domain.
1871 * If the induction variable appears in the constraints (as a parameter)
1872 * of the current iteration domain or the schedule of the statement,
1873 * then the parameter is equated to the newly introduced iteration
1874 * domain dimension and subsequently projected out.
1876 * Finally, all access relations are updated based on the extra loop.
1878 static struct pet_stmt *pet_stmt_embed(struct pet_stmt *stmt,
1879 __isl_take isl_set *dom, __isl_take isl_map *sched,
1880 __isl_take isl_aff *iv_map, __isl_take isl_id *var_id)
1882 int i;
1883 int pos;
1884 isl_id *stmt_id;
1885 isl_space *dim;
1886 isl_multi_pw_aff *extend;
1888 if (!stmt)
1889 goto error;
1891 if (isl_set_is_wrapping(stmt->domain)) {
1892 isl_map *map;
1893 isl_map *ext;
1894 isl_space *ran_dim;
1896 map = isl_set_unwrap(stmt->domain);
1897 stmt_id = isl_map_get_tuple_id(map, isl_dim_in);
1898 ran_dim = isl_space_range(isl_map_get_space(map));
1899 ext = isl_map_from_domain_and_range(isl_set_copy(dom),
1900 isl_set_universe(ran_dim));
1901 map = isl_map_flat_domain_product(ext, map);
1902 map = isl_map_set_tuple_id(map, isl_dim_in,
1903 isl_id_copy(stmt_id));
1904 dim = isl_space_domain(isl_map_get_space(map));
1905 stmt->domain = isl_map_wrap(map);
1906 } else {
1907 stmt_id = isl_set_get_tuple_id(stmt->domain);
1908 stmt->domain = isl_set_flat_product(isl_set_copy(dom),
1909 stmt->domain);
1910 stmt->domain = isl_set_set_tuple_id(stmt->domain,
1911 isl_id_copy(stmt_id));
1912 dim = isl_set_get_space(stmt->domain);
1915 pos = isl_set_find_dim_by_id(stmt->domain, isl_dim_param, var_id);
1916 if (pos >= 0)
1917 stmt->domain = internalize_iv(stmt->domain, pos,
1918 isl_aff_copy(iv_map));
1920 stmt->schedule = isl_map_flat_product(sched, stmt->schedule);
1921 stmt->schedule = isl_map_set_tuple_id(stmt->schedule,
1922 isl_dim_in, stmt_id);
1924 pos = isl_map_find_dim_by_id(stmt->schedule, isl_dim_param, var_id);
1925 if (pos >= 0) {
1926 isl_set *set = isl_map_wrap(stmt->schedule);
1927 set = internalize_iv(set, pos, isl_aff_copy(iv_map));
1928 stmt->schedule = isl_set_unwrap(set);
1931 dim = isl_space_map_from_set(dim);
1932 extend = isl_multi_pw_aff_identity(dim);
1933 extend = isl_multi_pw_aff_drop_dims(extend, isl_dim_out, 0, 1);
1934 extend = isl_multi_pw_aff_set_tuple_id(extend, isl_dim_out,
1935 isl_multi_pw_aff_get_tuple_id(extend, isl_dim_in));
1936 for (i = 0; i < stmt->n_arg; ++i)
1937 stmt->args[i] = expr_embed(stmt->args[i],
1938 isl_multi_pw_aff_copy(extend),
1939 isl_aff_copy(iv_map), var_id);
1940 stmt->body = expr_embed(stmt->body, extend, iv_map, var_id);
1942 isl_set_free(dom);
1943 isl_id_free(var_id);
1945 for (i = 0; i < stmt->n_arg; ++i)
1946 if (!stmt->args[i])
1947 return pet_stmt_free(stmt);
1948 if (!stmt->domain || !stmt->schedule || !stmt->body)
1949 return pet_stmt_free(stmt);
1950 return stmt;
1951 error:
1952 isl_set_free(dom);
1953 isl_map_free(sched);
1954 isl_aff_free(iv_map);
1955 isl_id_free(var_id);
1956 return NULL;
1959 /* Embed the given pet_array in an extra outer loop with iteration domain
1960 * "dom".
1961 * This embedding only has an effect on virtual arrays (those with
1962 * user pointer equal to NULL), which need to be extended along with
1963 * the iteration domain.
1965 static struct pet_array *pet_array_embed(struct pet_array *array,
1966 __isl_take isl_set *dom)
1968 isl_id *array_id = NULL;
1970 if (!array)
1971 goto error;
1973 if (isl_set_has_tuple_id(array->extent))
1974 array_id = isl_set_get_tuple_id(array->extent);
1976 if (array_id && !isl_id_get_user(array_id)) {
1977 array->extent = isl_set_flat_product(dom, array->extent);
1978 array->extent = isl_set_set_tuple_id(array->extent, array_id);
1979 if (!array->extent)
1980 return pet_array_free(array);
1981 } else {
1982 isl_set_free(dom);
1983 isl_id_free(array_id);
1986 return array;
1987 error:
1988 isl_set_free(dom);
1989 return NULL;
1992 /* Project out all unnamed parameters from "set" and return the result.
1994 static __isl_give isl_set *set_project_out_unnamed_params(
1995 __isl_take isl_set *set)
1997 int i, n;
1999 n = isl_set_dim(set, isl_dim_param);
2000 for (i = n - 1; i >= 0; --i) {
2001 if (isl_set_has_dim_name(set, isl_dim_param, i))
2002 continue;
2003 set = isl_set_project_out(set, isl_dim_param, i, 1);
2006 return set;
2009 /* Update the context with respect to an embedding into a loop
2010 * with iteration domain "dom" and induction variable "id".
2011 * "iv_map" expresses the real iterator (parameter "id") in terms
2012 * of a possibly virtual iterator (used in "dom").
2014 * If the current context is independent of "id", we don't need
2015 * to do anything.
2016 * Otherwise, a parameter value is invalid for the embedding if
2017 * any of the corresponding iterator values is invalid.
2018 * That is, a parameter value is valid only if all the corresponding
2019 * iterator values are valid.
2020 * We therefore compute the set of parameters
2022 * forall i in dom : valid (i)
2024 * or
2026 * not exists i in dom : not valid(i)
2028 * i.e.,
2030 * not exists i in dom \ valid(i)
2032 * Before we subtract valid(i) from dom, we first need to substitute
2033 * the real iterator for the virtual iterator.
2035 * If there are any unnamed parameters in "dom", then we consider
2036 * a parameter value to be valid if it is valid for any value of those
2037 * unnamed parameters. They are therefore projected out at the end.
2039 static __isl_give isl_set *context_embed(__isl_take isl_set *context,
2040 __isl_keep isl_set *dom, __isl_keep isl_aff *iv_map,
2041 __isl_keep isl_id *id)
2043 int pos;
2044 isl_multi_aff *ma;
2046 pos = isl_set_find_dim_by_id(context, isl_dim_param, id);
2047 if (pos < 0)
2048 return context;
2050 context = isl_set_from_params(context);
2051 context = isl_set_add_dims(context, isl_dim_set, 1);
2052 context = isl_set_equate(context, isl_dim_param, pos, isl_dim_set, 0);
2053 context = isl_set_project_out(context, isl_dim_param, pos, 1);
2054 ma = isl_multi_aff_from_aff(isl_aff_copy(iv_map));
2055 context = isl_set_preimage_multi_aff(context, ma);
2056 context = isl_set_subtract(isl_set_copy(dom), context);
2057 context = isl_set_params(context);
2058 context = isl_set_complement(context);
2059 context = set_project_out_unnamed_params(context);
2060 return context;
2063 /* Update the implication with respect to an embedding into a loop
2064 * with iteration domain "dom".
2066 * Since embed_access extends virtual arrays along with the domain
2067 * of the access, we need to do the same with domain and range
2068 * of the implication. Since the original implication is only valid
2069 * within a given iteration of the loop, the extended implication
2070 * maps the extra array dimension corresponding to the extra loop
2071 * to itself.
2073 static struct pet_implication *pet_implication_embed(
2074 struct pet_implication *implication, __isl_take isl_set *dom)
2076 isl_id *id;
2077 isl_map *map;
2079 if (!implication)
2080 goto error;
2082 map = isl_set_identity(dom);
2083 id = isl_map_get_tuple_id(implication->extension, isl_dim_in);
2084 map = isl_map_flat_product(map, implication->extension);
2085 map = isl_map_set_tuple_id(map, isl_dim_in, isl_id_copy(id));
2086 map = isl_map_set_tuple_id(map, isl_dim_out, id);
2087 implication->extension = map;
2088 if (!implication->extension)
2089 return pet_implication_free(implication);
2091 return implication;
2092 error:
2093 isl_set_free(dom);
2094 return NULL;
2097 /* Embed all statements and arrays in "scop" in an extra outer loop
2098 * with iteration domain "dom" and schedule "sched".
2099 * "id" represents the induction variable of the loop.
2100 * "iv_map" maps a possibly virtual iterator to the real iterator.
2101 * That is, it expresses the iterator that some of the parameters in "scop"
2102 * may refer to in terms of the iterator used in "dom" and
2103 * the domain of "sched".
2105 * Any skip conditions within the loop have no effect outside of the loop.
2106 * The caller is responsible for making sure skip[pet_skip_later] has been
2107 * taken into account.
2109 struct pet_scop *pet_scop_embed(struct pet_scop *scop, __isl_take isl_set *dom,
2110 __isl_take isl_map *sched, __isl_take isl_aff *iv_map,
2111 __isl_take isl_id *id)
2113 int i;
2115 if (!scop)
2116 goto error;
2118 pet_scop_reset_skip(scop, pet_skip_now);
2119 pet_scop_reset_skip(scop, pet_skip_later);
2121 scop->context = context_embed(scop->context, dom, iv_map, id);
2122 if (!scop->context)
2123 goto error;
2125 for (i = 0; i < scop->n_stmt; ++i) {
2126 scop->stmts[i] = pet_stmt_embed(scop->stmts[i],
2127 isl_set_copy(dom), isl_map_copy(sched),
2128 isl_aff_copy(iv_map), isl_id_copy(id));
2129 if (!scop->stmts[i])
2130 goto error;
2133 for (i = 0; i < scop->n_array; ++i) {
2134 scop->arrays[i] = pet_array_embed(scop->arrays[i],
2135 isl_set_copy(dom));
2136 if (!scop->arrays[i])
2137 goto error;
2140 for (i = 0; i < scop->n_implication; ++i) {
2141 scop->implications[i] =
2142 pet_implication_embed(scop->implications[i],
2143 isl_set_copy(dom));
2144 if (!scop->implications[i])
2145 goto error;
2148 isl_set_free(dom);
2149 isl_map_free(sched);
2150 isl_aff_free(iv_map);
2151 isl_id_free(id);
2152 return scop;
2153 error:
2154 isl_set_free(dom);
2155 isl_map_free(sched);
2156 isl_aff_free(iv_map);
2157 isl_id_free(id);
2158 return pet_scop_free(scop);
2161 /* Add extra conditions on the parameters to iteration domain of "stmt".
2163 static struct pet_stmt *stmt_restrict(struct pet_stmt *stmt,
2164 __isl_take isl_set *cond)
2166 if (!stmt)
2167 goto error;
2169 stmt->domain = isl_set_intersect_params(stmt->domain, cond);
2171 return stmt;
2172 error:
2173 isl_set_free(cond);
2174 return pet_stmt_free(stmt);
2177 /* Add extra conditions to scop->skip[type].
2179 * The new skip condition only holds if it held before
2180 * and the condition is true. It does not hold if it did not hold
2181 * before or the condition is false.
2183 * The skip condition is assumed to be an affine expression.
2185 static struct pet_scop *pet_scop_restrict_skip(struct pet_scop *scop,
2186 enum pet_skip type, __isl_keep isl_set *cond)
2188 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2189 isl_pw_aff *skip;
2190 isl_set *dom;
2192 if (!scop)
2193 return NULL;
2194 if (!ext->skip[type])
2195 return scop;
2197 if (!multi_pw_aff_is_affine(ext->skip[type]))
2198 isl_die(isl_multi_pw_aff_get_ctx(ext->skip[type]),
2199 isl_error_internal, "can only resrict affine skips",
2200 return pet_scop_free(scop));
2202 skip = isl_multi_pw_aff_get_pw_aff(ext->skip[type], 0);
2203 dom = isl_pw_aff_domain(isl_pw_aff_copy(skip));
2204 cond = isl_set_copy(cond);
2205 cond = isl_set_from_params(cond);
2206 cond = isl_set_intersect(cond, isl_pw_aff_non_zero_set(skip));
2207 skip = indicator_function(cond, dom);
2208 isl_multi_pw_aff_free(ext->skip[type]);
2209 ext->skip[type] = isl_multi_pw_aff_from_pw_aff(skip);
2210 if (!ext->skip[type])
2211 return pet_scop_free(scop);
2213 return scop;
2216 /* Add extra conditions on the parameters to all iteration domains
2217 * and skip conditions.
2219 * A parameter value is valid for the result if it was valid
2220 * for the original scop and satisfies "cond" or if it does
2221 * not satisfy "cond" as in this case the scop is not executed
2222 * and the original constraints on the parameters are irrelevant.
2224 struct pet_scop *pet_scop_restrict(struct pet_scop *scop,
2225 __isl_take isl_set *cond)
2227 int i;
2229 scop = pet_scop_restrict_skip(scop, pet_skip_now, cond);
2230 scop = pet_scop_restrict_skip(scop, pet_skip_later, cond);
2232 if (!scop)
2233 goto error;
2235 scop->context = isl_set_intersect(scop->context, isl_set_copy(cond));
2236 scop->context = isl_set_union(scop->context,
2237 isl_set_complement(isl_set_copy(cond)));
2238 scop->context = isl_set_coalesce(scop->context);
2239 scop->context = set_project_out_unnamed_params(scop->context);
2240 if (!scop->context)
2241 goto error;
2243 for (i = 0; i < scop->n_stmt; ++i) {
2244 scop->stmts[i] = stmt_restrict(scop->stmts[i],
2245 isl_set_copy(cond));
2246 if (!scop->stmts[i])
2247 goto error;
2250 isl_set_free(cond);
2251 return scop;
2252 error:
2253 isl_set_free(cond);
2254 return pet_scop_free(scop);
2257 /* Construct a function that (upon precomposition) inserts
2258 * a filter value with name "id" and value "satisfied"
2259 * in the list of filter values embedded in the set space "space".
2261 * If "space" does not contain any filter values yet, we first create
2262 * a function that inserts 0 filter values, i.e.,
2264 * [space -> []] -> space
2266 * We can now assume that space is of the form [dom -> [filters]]
2267 * We construct an identity mapping on dom and a mapping on filters
2268 * that (upon precomposition) inserts the new filter
2270 * dom -> dom
2271 * [satisfied, filters] -> [filters]
2273 * and then compute the cross product
2275 * [dom -> [satisfied, filters]] -> [dom -> [filters]]
2277 static __isl_give isl_pw_multi_aff *insert_filter_pma(
2278 __isl_take isl_space *space, __isl_take isl_id *id, int satisfied)
2280 isl_space *space2;
2281 isl_multi_aff *ma;
2282 isl_pw_multi_aff *pma0, *pma, *pma_dom, *pma_ran;
2283 isl_set *dom;
2285 if (isl_space_is_wrapping(space)) {
2286 space2 = isl_space_map_from_set(isl_space_copy(space));
2287 ma = isl_multi_aff_identity(space2);
2288 space = isl_space_unwrap(space);
2289 } else {
2290 space = isl_space_from_domain(space);
2291 ma = isl_multi_aff_domain_map(isl_space_copy(space));
2294 space2 = isl_space_domain(isl_space_copy(space));
2295 pma_dom = isl_pw_multi_aff_identity(isl_space_map_from_set(space2));
2296 space = isl_space_range(space);
2297 space = isl_space_insert_dims(space, isl_dim_set, 0, 1);
2298 pma_ran = isl_pw_multi_aff_project_out_map(space, isl_dim_set, 0, 1);
2299 pma_ran = isl_pw_multi_aff_set_dim_id(pma_ran, isl_dim_in, 0, id);
2300 pma_ran = isl_pw_multi_aff_fix_si(pma_ran, isl_dim_in, 0, satisfied);
2301 pma = isl_pw_multi_aff_product(pma_dom, pma_ran);
2303 pma0 = isl_pw_multi_aff_from_multi_aff(ma);
2304 pma = isl_pw_multi_aff_pullback_pw_multi_aff(pma0, pma);
2306 return pma;
2309 /* Insert an argument expression corresponding to "test" in front
2310 * of the list of arguments described by *n_arg and *args.
2312 static int args_insert_access(unsigned *n_arg, struct pet_expr ***args,
2313 __isl_keep isl_multi_pw_aff *test)
2315 int i;
2316 isl_ctx *ctx = isl_multi_pw_aff_get_ctx(test);
2318 if (!test)
2319 return -1;
2321 if (!*args) {
2322 *args = isl_calloc_array(ctx, struct pet_expr *, 1);
2323 if (!*args)
2324 return -1;
2325 } else {
2326 struct pet_expr **ext;
2327 ext = isl_calloc_array(ctx, struct pet_expr *, 1 + *n_arg);
2328 if (!ext)
2329 return -1;
2330 for (i = 0; i < *n_arg; ++i)
2331 ext[1 + i] = (*args)[i];
2332 free(*args);
2333 *args = ext;
2335 (*n_arg)++;
2336 (*args)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test));
2337 if (!(*args)[0])
2338 return -1;
2340 return 0;
2343 /* Make the expression "expr" depend on the value of "test"
2344 * being equal to "satisfied".
2346 * If "test" is an affine expression, we simply add the conditions
2347 * on the expression having the value "satisfied" to all access relations
2348 * and index expressions.
2350 * Otherwise, we add a filter to "expr" (which is then assumed to be
2351 * an access expression) corresponding to "test" being equal to "satisfied".
2353 struct pet_expr *pet_expr_filter(struct pet_expr *expr,
2354 __isl_take isl_multi_pw_aff *test, int satisfied)
2356 isl_id *id;
2357 isl_ctx *ctx;
2358 isl_space *space;
2359 isl_pw_multi_aff *pma;
2361 if (!expr || !test)
2362 goto error;
2364 if (!isl_multi_pw_aff_has_tuple_id(test, isl_dim_out)) {
2365 isl_pw_aff *pa;
2366 isl_set *cond;
2368 pa = isl_multi_pw_aff_get_pw_aff(test, 0);
2369 isl_multi_pw_aff_free(test);
2370 if (satisfied)
2371 cond = isl_pw_aff_non_zero_set(pa);
2372 else
2373 cond = isl_pw_aff_zero_set(pa);
2374 return pet_expr_restrict(expr, isl_set_params(cond));
2377 ctx = isl_multi_pw_aff_get_ctx(test);
2378 if (expr->type != pet_expr_access)
2379 isl_die(ctx, isl_error_invalid,
2380 "can only filter access expressions", goto error);
2382 space = isl_space_domain(isl_map_get_space(expr->acc.access));
2383 id = isl_multi_pw_aff_get_tuple_id(test, isl_dim_out);
2384 pma = insert_filter_pma(space, id, satisfied);
2386 expr->acc.access = isl_map_preimage_domain_pw_multi_aff(
2387 expr->acc.access,
2388 isl_pw_multi_aff_copy(pma));
2389 expr->acc.index = isl_multi_pw_aff_pullback_pw_multi_aff(
2390 expr->acc.index, pma);
2391 if (!expr->acc.access || !expr->acc.index)
2392 goto error;
2394 if (args_insert_access(&expr->n_arg, &expr->args, test) < 0)
2395 goto error;
2397 isl_multi_pw_aff_free(test);
2398 return expr;
2399 error:
2400 isl_multi_pw_aff_free(test);
2401 return pet_expr_free(expr);
2404 /* Look through the applications in "scop" for any that can be
2405 * applied to the filter expressed by "map" and "satisified".
2406 * If there is any, then apply it to "map" and return the result.
2407 * Otherwise, return "map".
2408 * "id" is the identifier of the virtual array.
2410 * We only introduce at most one implication for any given virtual array,
2411 * so we can apply the implication and return as soon as we find one.
2413 static __isl_give isl_map *apply_implications(struct pet_scop *scop,
2414 __isl_take isl_map *map, __isl_keep isl_id *id, int satisfied)
2416 int i;
2418 for (i = 0; i < scop->n_implication; ++i) {
2419 struct pet_implication *pi = scop->implications[i];
2420 isl_id *pi_id;
2422 if (pi->satisfied != satisfied)
2423 continue;
2424 pi_id = isl_map_get_tuple_id(pi->extension, isl_dim_in);
2425 isl_id_free(pi_id);
2426 if (pi_id != id)
2427 continue;
2429 return isl_map_apply_range(map, isl_map_copy(pi->extension));
2432 return map;
2435 /* Is the filter expressed by "test" and "satisfied" implied
2436 * by filter "pos" on "domain", with filter "expr", taking into
2437 * account the implications of "scop"?
2439 * For filter on domain implying that expressed by "test" and "satisfied",
2440 * the filter needs to be an access to the same (virtual) array as "test" and
2441 * the filter value needs to be equal to "satisfied".
2442 * Moreover, the filter access relation, possibly extended by
2443 * the implications in "scop" needs to contain "test".
2445 static int implies_filter(struct pet_scop *scop,
2446 __isl_keep isl_map *domain, int pos, struct pet_expr *expr,
2447 __isl_keep isl_map *test, int satisfied)
2449 isl_id *test_id, *arg_id;
2450 isl_val *val;
2451 int is_int;
2452 int s;
2453 int is_subset;
2454 isl_map *implied;
2456 if (expr->type != pet_expr_access)
2457 return 0;
2458 test_id = isl_map_get_tuple_id(test, isl_dim_out);
2459 arg_id = pet_expr_access_get_id(expr);
2460 isl_id_free(arg_id);
2461 isl_id_free(test_id);
2462 if (test_id != arg_id)
2463 return 0;
2464 val = isl_map_plain_get_val_if_fixed(domain, isl_dim_out, pos);
2465 is_int = isl_val_is_int(val);
2466 if (is_int)
2467 s = isl_val_get_num_si(val);
2468 isl_val_free(val);
2469 if (!val)
2470 return -1;
2471 if (!is_int)
2472 return 0;
2473 if (s != satisfied)
2474 return 0;
2476 implied = isl_map_copy(expr->acc.access);
2477 implied = apply_implications(scop, implied, test_id, satisfied);
2478 is_subset = isl_map_is_subset(test, implied);
2479 isl_map_free(implied);
2481 return is_subset;
2484 /* Is the filter expressed by "test" and "satisfied" implied
2485 * by any of the filters on the domain of "stmt", taking into
2486 * account the implications of "scop"?
2488 static int filter_implied(struct pet_scop *scop,
2489 struct pet_stmt *stmt, __isl_keep isl_multi_pw_aff *test, int satisfied)
2491 int i;
2492 int implied;
2493 isl_id *test_id;
2494 isl_map *domain;
2495 isl_map *test_map;
2497 if (!scop || !stmt || !test)
2498 return -1;
2499 if (scop->n_implication == 0)
2500 return 0;
2501 if (stmt->n_arg == 0)
2502 return 0;
2504 domain = isl_set_unwrap(isl_set_copy(stmt->domain));
2505 test_map = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test));
2507 implied = 0;
2508 for (i = 0; i < stmt->n_arg; ++i) {
2509 implied = implies_filter(scop, domain, i, stmt->args[i],
2510 test_map, satisfied);
2511 if (implied < 0 || implied)
2512 break;
2515 isl_map_free(test_map);
2516 isl_map_free(domain);
2517 return implied;
2520 /* Make the statement "stmt" depend on the value of "test"
2521 * being equal to "satisfied" by adjusting stmt->domain.
2523 * The domain of "test" corresponds to the (zero or more) outer dimensions
2524 * of the iteration domain.
2526 * We first extend "test" to apply to the entire iteration domain and
2527 * then check if the filter that we are about to add is implied
2528 * by any of the current filters, possibly taking into account
2529 * the implications in "scop". If so, we leave "stmt" untouched and return.
2531 * Otherwise, we insert an argument corresponding to a read to "test"
2532 * from the iteration domain of "stmt" in front of the list of arguments.
2533 * We also insert a corresponding output dimension in the wrapped
2534 * map contained in stmt->domain, with value set to "satisfied".
2536 static struct pet_stmt *stmt_filter(struct pet_scop *scop,
2537 struct pet_stmt *stmt, __isl_take isl_multi_pw_aff *test, int satisfied)
2539 int i;
2540 int implied;
2541 isl_id *id;
2542 isl_ctx *ctx;
2543 isl_pw_multi_aff *pma;
2544 isl_multi_aff *add_dom;
2545 isl_space *space;
2546 isl_local_space *ls;
2547 int n_test_dom;
2549 if (!stmt || !test)
2550 goto error;
2552 space = isl_set_get_space(stmt->domain);
2553 if (isl_space_is_wrapping(space))
2554 space = isl_space_domain(isl_space_unwrap(space));
2555 n_test_dom = isl_multi_pw_aff_dim(test, isl_dim_in);
2556 space = isl_space_from_domain(space);
2557 space = isl_space_add_dims(space, isl_dim_out, n_test_dom);
2558 add_dom = isl_multi_aff_zero(isl_space_copy(space));
2559 ls = isl_local_space_from_space(isl_space_domain(space));
2560 for (i = 0; i < n_test_dom; ++i) {
2561 isl_aff *aff;
2562 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
2563 isl_dim_set, i);
2564 add_dom = isl_multi_aff_set_aff(add_dom, i, aff);
2566 isl_local_space_free(ls);
2567 test = isl_multi_pw_aff_pullback_multi_aff(test, add_dom);
2569 implied = filter_implied(scop, stmt, test, satisfied);
2570 if (implied < 0)
2571 goto error;
2572 if (implied) {
2573 isl_multi_pw_aff_free(test);
2574 return stmt;
2577 id = isl_multi_pw_aff_get_tuple_id(test, isl_dim_out);
2578 pma = insert_filter_pma(isl_set_get_space(stmt->domain), id, satisfied);
2579 stmt->domain = isl_set_preimage_pw_multi_aff(stmt->domain, pma);
2581 if (args_insert_access(&stmt->n_arg, &stmt->args, test) < 0)
2582 goto error;
2584 isl_multi_pw_aff_free(test);
2585 return stmt;
2586 error:
2587 isl_multi_pw_aff_free(test);
2588 return pet_stmt_free(stmt);
2591 /* Does "scop" have a skip condition of the given "type"?
2593 int pet_scop_has_skip(struct pet_scop *scop, enum pet_skip type)
2595 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2597 if (!scop)
2598 return -1;
2599 return ext->skip[type] != NULL;
2602 /* Does "scop" have a skip condition of the given "type" that
2603 * is an affine expression?
2605 int pet_scop_has_affine_skip(struct pet_scop *scop, enum pet_skip type)
2607 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2609 if (!scop)
2610 return -1;
2611 if (!ext->skip[type])
2612 return 0;
2613 return multi_pw_aff_is_affine(ext->skip[type]);
2616 /* Does "scop" have a skip condition of the given "type" that
2617 * is not an affine expression?
2619 int pet_scop_has_var_skip(struct pet_scop *scop, enum pet_skip type)
2621 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2622 int aff;
2624 if (!scop)
2625 return -1;
2626 if (!ext->skip[type])
2627 return 0;
2628 aff = multi_pw_aff_is_affine(ext->skip[type]);
2629 if (aff < 0)
2630 return -1;
2631 return !aff;
2634 /* Does "scop" have a skip condition of the given "type" that
2635 * is affine and holds on the entire domain?
2637 int pet_scop_has_universal_skip(struct pet_scop *scop, enum pet_skip type)
2639 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2640 isl_pw_aff *pa;
2641 isl_set *set;
2642 int is_aff;
2643 int is_univ;
2645 is_aff = pet_scop_has_affine_skip(scop, type);
2646 if (is_aff < 0 || !is_aff)
2647 return is_aff;
2649 pa = isl_multi_pw_aff_get_pw_aff(ext->skip[type], 0);
2650 set = isl_pw_aff_non_zero_set(pa);
2651 is_univ = isl_set_plain_is_universe(set);
2652 isl_set_free(set);
2654 return is_univ;
2657 /* Replace scop->skip[type] by "skip".
2659 struct pet_scop *pet_scop_set_skip(struct pet_scop *scop,
2660 enum pet_skip type, __isl_take isl_multi_pw_aff *skip)
2662 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2664 if (!scop || !skip)
2665 goto error;
2667 isl_multi_pw_aff_free(ext->skip[type]);
2668 ext->skip[type] = skip;
2670 return scop;
2671 error:
2672 isl_multi_pw_aff_free(skip);
2673 return pet_scop_free(scop);
2676 /* Return a copy of scop->skip[type].
2678 __isl_give isl_multi_pw_aff *pet_scop_get_skip(struct pet_scop *scop,
2679 enum pet_skip type)
2681 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2683 if (!scop)
2684 return NULL;
2686 return isl_multi_pw_aff_copy(ext->skip[type]);
2689 /* Assuming scop->skip[type] is an affine expression,
2690 * return the constraints on the parameters for which the skip condition
2691 * holds.
2693 __isl_give isl_set *pet_scop_get_affine_skip_domain(struct pet_scop *scop,
2694 enum pet_skip type)
2696 isl_multi_pw_aff *skip;
2697 isl_pw_aff *pa;
2699 skip = pet_scop_get_skip(scop, type);
2700 pa = isl_multi_pw_aff_get_pw_aff(skip, 0);
2701 isl_multi_pw_aff_free(skip);
2702 return isl_set_params(isl_pw_aff_non_zero_set(pa));
2705 /* Return the identifier of the variable that is accessed by
2706 * the skip condition of the given type.
2708 * The skip condition is assumed not to be an affine condition.
2710 __isl_give isl_id *pet_scop_get_skip_id(struct pet_scop *scop,
2711 enum pet_skip type)
2713 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2715 if (!scop)
2716 return NULL;
2718 return isl_multi_pw_aff_get_tuple_id(ext->skip[type], isl_dim_out);
2721 /* Return an access pet_expr corresponding to the skip condition
2722 * of the given type.
2724 struct pet_expr *pet_scop_get_skip_expr(struct pet_scop *scop,
2725 enum pet_skip type)
2727 return pet_expr_from_index(pet_scop_get_skip(scop, type));
2730 /* Drop the the skip condition scop->skip[type].
2732 void pet_scop_reset_skip(struct pet_scop *scop, enum pet_skip type)
2734 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2736 if (!scop)
2737 return;
2739 isl_multi_pw_aff_free(ext->skip[type]);
2740 ext->skip[type] = NULL;
2743 /* Make the skip condition (if any) depend on the value of "test" being
2744 * equal to "satisfied".
2746 * We only support the case where the original skip condition is universal,
2747 * i.e., where skipping is unconditional, and where satisfied == 1.
2748 * In this case, the skip condition is changed to skip only when
2749 * "test" is equal to one.
2751 static struct pet_scop *pet_scop_filter_skip(struct pet_scop *scop,
2752 enum pet_skip type, __isl_keep isl_multi_pw_aff *test, int satisfied)
2754 int is_univ = 0;
2756 if (!scop)
2757 return NULL;
2758 if (!pet_scop_has_skip(scop, type))
2759 return scop;
2761 if (satisfied)
2762 is_univ = pet_scop_has_universal_skip(scop, type);
2763 if (is_univ < 0)
2764 return pet_scop_free(scop);
2765 if (satisfied && is_univ) {
2766 isl_space *space = isl_multi_pw_aff_get_space(test);
2767 isl_multi_pw_aff *skip;
2768 skip = isl_multi_pw_aff_zero(space);
2769 scop = pet_scop_set_skip(scop, type, skip);
2770 if (!scop)
2771 return NULL;
2772 } else {
2773 isl_die(isl_multi_pw_aff_get_ctx(test), isl_error_internal,
2774 "skip expression cannot be filtered",
2775 return pet_scop_free(scop));
2778 return scop;
2781 /* Make all statements in "scop" depend on the value of "test"
2782 * being equal to "satisfied" by adjusting their domains.
2784 struct pet_scop *pet_scop_filter(struct pet_scop *scop,
2785 __isl_take isl_multi_pw_aff *test, int satisfied)
2787 int i;
2789 scop = pet_scop_filter_skip(scop, pet_skip_now, test, satisfied);
2790 scop = pet_scop_filter_skip(scop, pet_skip_later, test, satisfied);
2792 if (!scop || !test)
2793 goto error;
2795 for (i = 0; i < scop->n_stmt; ++i) {
2796 scop->stmts[i] = stmt_filter(scop, scop->stmts[i],
2797 isl_multi_pw_aff_copy(test), satisfied);
2798 if (!scop->stmts[i])
2799 goto error;
2802 isl_multi_pw_aff_free(test);
2803 return scop;
2804 error:
2805 isl_multi_pw_aff_free(test);
2806 return pet_scop_free(scop);
2809 /* Add all parameters in "expr" to "dim" and return the result.
2811 static __isl_give isl_space *expr_collect_params(struct pet_expr *expr,
2812 __isl_take isl_space *dim)
2814 int i;
2816 if (!expr)
2817 goto error;
2818 for (i = 0; i < expr->n_arg; ++i)
2820 dim = expr_collect_params(expr->args[i], dim);
2822 if (expr->type == pet_expr_access)
2823 dim = isl_space_align_params(dim,
2824 isl_map_get_space(expr->acc.access));
2826 return dim;
2827 error:
2828 isl_space_free(dim);
2829 return pet_expr_free(expr);
2832 /* Add all parameters in "stmt" to "dim" and return the result.
2834 static __isl_give isl_space *stmt_collect_params(struct pet_stmt *stmt,
2835 __isl_take isl_space *dim)
2837 if (!stmt)
2838 goto error;
2840 dim = isl_space_align_params(dim, isl_set_get_space(stmt->domain));
2841 dim = isl_space_align_params(dim, isl_map_get_space(stmt->schedule));
2842 dim = expr_collect_params(stmt->body, dim);
2844 return dim;
2845 error:
2846 isl_space_free(dim);
2847 return pet_stmt_free(stmt);
2850 /* Add all parameters in "array" to "dim" and return the result.
2852 static __isl_give isl_space *array_collect_params(struct pet_array *array,
2853 __isl_take isl_space *dim)
2855 if (!array)
2856 goto error;
2858 dim = isl_space_align_params(dim, isl_set_get_space(array->context));
2859 dim = isl_space_align_params(dim, isl_set_get_space(array->extent));
2861 return dim;
2862 error:
2863 pet_array_free(array);
2864 return isl_space_free(dim);
2867 /* Add all parameters in "scop" to "dim" and return the result.
2869 static __isl_give isl_space *scop_collect_params(struct pet_scop *scop,
2870 __isl_take isl_space *dim)
2872 int i;
2874 if (!scop)
2875 goto error;
2877 for (i = 0; i < scop->n_array; ++i)
2878 dim = array_collect_params(scop->arrays[i], dim);
2880 for (i = 0; i < scop->n_stmt; ++i)
2881 dim = stmt_collect_params(scop->stmts[i], dim);
2883 return dim;
2884 error:
2885 isl_space_free(dim);
2886 return pet_scop_free(scop);
2889 /* Add all parameters in "dim" to all access relations and index expressions
2890 * in "expr".
2892 static struct pet_expr *expr_propagate_params(struct pet_expr *expr,
2893 __isl_take isl_space *dim)
2895 int i;
2897 if (!expr)
2898 goto error;
2900 for (i = 0; i < expr->n_arg; ++i) {
2901 expr->args[i] =
2902 expr_propagate_params(expr->args[i],
2903 isl_space_copy(dim));
2904 if (!expr->args[i])
2905 goto error;
2908 if (expr->type == pet_expr_access) {
2909 expr->acc.access = isl_map_align_params(expr->acc.access,
2910 isl_space_copy(dim));
2911 expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
2912 isl_space_copy(dim));
2913 if (!expr->acc.access || !expr->acc.index)
2914 goto error;
2917 isl_space_free(dim);
2918 return expr;
2919 error:
2920 isl_space_free(dim);
2921 return pet_expr_free(expr);
2924 /* Add all parameters in "dim" to the domain, schedule and
2925 * all access relations in "stmt".
2927 static struct pet_stmt *stmt_propagate_params(struct pet_stmt *stmt,
2928 __isl_take isl_space *dim)
2930 if (!stmt)
2931 goto error;
2933 stmt->domain = isl_set_align_params(stmt->domain, isl_space_copy(dim));
2934 stmt->schedule = isl_map_align_params(stmt->schedule,
2935 isl_space_copy(dim));
2936 stmt->body = expr_propagate_params(stmt->body, isl_space_copy(dim));
2938 if (!stmt->domain || !stmt->schedule || !stmt->body)
2939 goto error;
2941 isl_space_free(dim);
2942 return stmt;
2943 error:
2944 isl_space_free(dim);
2945 return pet_stmt_free(stmt);
2948 /* Add all parameters in "dim" to "array".
2950 static struct pet_array *array_propagate_params(struct pet_array *array,
2951 __isl_take isl_space *dim)
2953 if (!array)
2954 goto error;
2956 array->context = isl_set_align_params(array->context,
2957 isl_space_copy(dim));
2958 array->extent = isl_set_align_params(array->extent,
2959 isl_space_copy(dim));
2960 if (array->value_bounds) {
2961 array->value_bounds = isl_set_align_params(array->value_bounds,
2962 isl_space_copy(dim));
2963 if (!array->value_bounds)
2964 goto error;
2967 if (!array->context || !array->extent)
2968 goto error;
2970 isl_space_free(dim);
2971 return array;
2972 error:
2973 isl_space_free(dim);
2974 return pet_array_free(array);
2977 /* Add all parameters in "dim" to "scop".
2979 static struct pet_scop *scop_propagate_params(struct pet_scop *scop,
2980 __isl_take isl_space *dim)
2982 int i;
2984 if (!scop)
2985 goto error;
2987 for (i = 0; i < scop->n_array; ++i) {
2988 scop->arrays[i] = array_propagate_params(scop->arrays[i],
2989 isl_space_copy(dim));
2990 if (!scop->arrays[i])
2991 goto error;
2994 for (i = 0; i < scop->n_stmt; ++i) {
2995 scop->stmts[i] = stmt_propagate_params(scop->stmts[i],
2996 isl_space_copy(dim));
2997 if (!scop->stmts[i])
2998 goto error;
3001 isl_space_free(dim);
3002 return scop;
3003 error:
3004 isl_space_free(dim);
3005 return pet_scop_free(scop);
3008 /* Update all isl_sets and isl_maps in "scop" such that they all
3009 * have the same parameters.
3011 struct pet_scop *pet_scop_align_params(struct pet_scop *scop)
3013 isl_space *dim;
3015 if (!scop)
3016 return NULL;
3018 dim = isl_set_get_space(scop->context);
3019 dim = scop_collect_params(scop, dim);
3021 scop->context = isl_set_align_params(scop->context, isl_space_copy(dim));
3022 scop = scop_propagate_params(scop, dim);
3024 return scop;
3027 /* Check if the given index expression accesses a (0D) array that corresponds
3028 * to one of the parameters in "dim". If so, replace the array access
3029 * by an access to the set of integers with as index (and value)
3030 * that parameter.
3032 static __isl_give isl_multi_pw_aff *index_detect_parameter(
3033 __isl_take isl_multi_pw_aff *index, __isl_take isl_space *space)
3035 isl_local_space *ls;
3036 isl_id *array_id = NULL;
3037 isl_aff *aff;
3038 int pos = -1;
3040 if (isl_multi_pw_aff_has_tuple_id(index, isl_dim_out)) {
3041 array_id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
3042 pos = isl_space_find_dim_by_id(space, isl_dim_param, array_id);
3044 isl_space_free(space);
3046 if (pos < 0) {
3047 isl_id_free(array_id);
3048 return index;
3051 space = isl_multi_pw_aff_get_domain_space(index);
3052 isl_multi_pw_aff_free(index);
3054 pos = isl_space_find_dim_by_id(space, isl_dim_param, array_id);
3055 if (pos < 0) {
3056 space = isl_space_insert_dims(space, isl_dim_param, 0, 1);
3057 space = isl_space_set_dim_id(space, isl_dim_param, 0, array_id);
3058 pos = 0;
3059 } else
3060 isl_id_free(array_id);
3062 ls = isl_local_space_from_space(space);
3063 aff = isl_aff_var_on_domain(ls, isl_dim_param, pos);
3064 index = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
3066 return index;
3069 /* Check if the given access relation accesses a (0D) array that corresponds
3070 * to one of the parameters in "dim". If so, replace the array access
3071 * by an access to the set of integers with as index (and value)
3072 * that parameter.
3074 static __isl_give isl_map *access_detect_parameter(__isl_take isl_map *access,
3075 __isl_take isl_space *dim)
3077 isl_id *array_id = NULL;
3078 int pos = -1;
3080 if (isl_map_has_tuple_id(access, isl_dim_out)) {
3081 array_id = isl_map_get_tuple_id(access, isl_dim_out);
3082 pos = isl_space_find_dim_by_id(dim, isl_dim_param, array_id);
3084 isl_space_free(dim);
3086 if (pos < 0) {
3087 isl_id_free(array_id);
3088 return access;
3091 pos = isl_map_find_dim_by_id(access, isl_dim_param, array_id);
3092 if (pos < 0) {
3093 access = isl_map_insert_dims(access, isl_dim_param, 0, 1);
3094 access = isl_map_set_dim_id(access, isl_dim_param, 0, array_id);
3095 pos = 0;
3096 } else
3097 isl_id_free(array_id);
3099 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
3100 access = isl_map_equate(access, isl_dim_param, pos, isl_dim_out, 0);
3102 return access;
3105 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3106 * in "dim" by a value equal to the corresponding parameter.
3108 static struct pet_expr *expr_detect_parameter_accesses(struct pet_expr *expr,
3109 __isl_take isl_space *dim)
3111 int i;
3113 if (!expr)
3114 goto error;
3116 for (i = 0; i < expr->n_arg; ++i) {
3117 expr->args[i] =
3118 expr_detect_parameter_accesses(expr->args[i],
3119 isl_space_copy(dim));
3120 if (!expr->args[i])
3121 goto error;
3124 if (expr->type == pet_expr_access) {
3125 expr->acc.access = access_detect_parameter(expr->acc.access,
3126 isl_space_copy(dim));
3127 expr->acc.index = index_detect_parameter(expr->acc.index,
3128 isl_space_copy(dim));
3129 if (!expr->acc.access || !expr->acc.index)
3130 goto error;
3133 isl_space_free(dim);
3134 return expr;
3135 error:
3136 isl_space_free(dim);
3137 return pet_expr_free(expr);
3140 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3141 * in "dim" by a value equal to the corresponding parameter.
3143 static struct pet_stmt *stmt_detect_parameter_accesses(struct pet_stmt *stmt,
3144 __isl_take isl_space *dim)
3146 if (!stmt)
3147 goto error;
3149 stmt->body = expr_detect_parameter_accesses(stmt->body,
3150 isl_space_copy(dim));
3152 if (!stmt->domain || !stmt->schedule || !stmt->body)
3153 goto error;
3155 isl_space_free(dim);
3156 return stmt;
3157 error:
3158 isl_space_free(dim);
3159 return pet_stmt_free(stmt);
3162 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
3163 * in "dim" by a value equal to the corresponding parameter.
3165 static struct pet_scop *scop_detect_parameter_accesses(struct pet_scop *scop,
3166 __isl_take isl_space *dim)
3168 int i;
3170 if (!scop)
3171 goto error;
3173 for (i = 0; i < scop->n_stmt; ++i) {
3174 scop->stmts[i] = stmt_detect_parameter_accesses(scop->stmts[i],
3175 isl_space_copy(dim));
3176 if (!scop->stmts[i])
3177 goto error;
3180 isl_space_free(dim);
3181 return scop;
3182 error:
3183 isl_space_free(dim);
3184 return pet_scop_free(scop);
3187 /* Replace all accesses to (0D) arrays that correspond to any of
3188 * the parameters used in "scop" by a value equal
3189 * to the corresponding parameter.
3191 struct pet_scop *pet_scop_detect_parameter_accesses(struct pet_scop *scop)
3193 isl_space *dim;
3195 if (!scop)
3196 return NULL;
3198 dim = isl_set_get_space(scop->context);
3199 dim = scop_collect_params(scop, dim);
3201 scop = scop_detect_parameter_accesses(scop, dim);
3203 return scop;
3206 /* Add all read access relations (if "read" is set) and/or all write
3207 * access relations (if "write" is set) to "accesses" and return the result.
3209 static __isl_give isl_union_map *expr_collect_accesses(struct pet_expr *expr,
3210 int read, int write, __isl_take isl_union_map *accesses)
3212 int i;
3213 isl_id *id;
3214 isl_space *dim;
3216 if (!expr)
3217 return NULL;
3219 for (i = 0; i < expr->n_arg; ++i)
3220 accesses = expr_collect_accesses(expr->args[i],
3221 read, write, accesses);
3223 if (expr->type == pet_expr_access && !pet_expr_is_affine(expr) &&
3224 ((read && expr->acc.read) || (write && expr->acc.write)))
3225 accesses = isl_union_map_add_map(accesses,
3226 isl_map_copy(expr->acc.access));
3228 return accesses;
3231 /* Collect and return all read access relations (if "read" is set)
3232 * and/or all write access relations (if "write" is set) in "stmt".
3234 static __isl_give isl_union_map *stmt_collect_accesses(struct pet_stmt *stmt,
3235 int read, int write, __isl_take isl_space *dim)
3237 isl_union_map *accesses;
3239 if (!stmt)
3240 return NULL;
3242 accesses = isl_union_map_empty(dim);
3243 accesses = expr_collect_accesses(stmt->body, read, write, accesses);
3244 accesses = isl_union_map_intersect_domain(accesses,
3245 isl_union_set_from_set(isl_set_copy(stmt->domain)));
3247 return accesses;
3250 /* Collect and return all read access relations (if "read" is set)
3251 * and/or all write access relations (if "write" is set) in "scop".
3253 static __isl_give isl_union_map *scop_collect_accesses(struct pet_scop *scop,
3254 int read, int write)
3256 int i;
3257 isl_union_map *accesses;
3259 if (!scop)
3260 return NULL;
3262 accesses = isl_union_map_empty(isl_set_get_space(scop->context));
3264 for (i = 0; i < scop->n_stmt; ++i) {
3265 isl_union_map *accesses_i;
3266 isl_space *dim = isl_set_get_space(scop->context);
3267 accesses_i = stmt_collect_accesses(scop->stmts[i],
3268 read, write, dim);
3269 accesses = isl_union_map_union(accesses, accesses_i);
3272 return accesses;
3275 __isl_give isl_union_map *pet_scop_collect_reads(struct pet_scop *scop)
3277 return scop_collect_accesses(scop, 1, 0);
3280 __isl_give isl_union_map *pet_scop_collect_writes(struct pet_scop *scop)
3282 return scop_collect_accesses(scop, 0, 1);
3285 /* Collect and return the union of iteration domains in "scop".
3287 __isl_give isl_union_set *pet_scop_collect_domains(struct pet_scop *scop)
3289 int i;
3290 isl_set *domain_i;
3291 isl_union_set *domain;
3293 if (!scop)
3294 return NULL;
3296 domain = isl_union_set_empty(isl_set_get_space(scop->context));
3298 for (i = 0; i < scop->n_stmt; ++i) {
3299 domain_i = isl_set_copy(scop->stmts[i]->domain);
3300 domain = isl_union_set_add_set(domain, domain_i);
3303 return domain;
3306 /* Collect and return the schedules of the statements in "scop".
3307 * The range is normalized to the maximal number of scheduling
3308 * dimensions.
3310 __isl_give isl_union_map *pet_scop_collect_schedule(struct pet_scop *scop)
3312 int i, j;
3313 isl_map *schedule_i;
3314 isl_union_map *schedule;
3315 int depth, max_depth = 0;
3317 if (!scop)
3318 return NULL;
3320 schedule = isl_union_map_empty(isl_set_get_space(scop->context));
3322 for (i = 0; i < scop->n_stmt; ++i) {
3323 depth = isl_map_dim(scop->stmts[i]->schedule, isl_dim_out);
3324 if (depth > max_depth)
3325 max_depth = depth;
3328 for (i = 0; i < scop->n_stmt; ++i) {
3329 schedule_i = isl_map_copy(scop->stmts[i]->schedule);
3330 depth = isl_map_dim(schedule_i, isl_dim_out);
3331 schedule_i = isl_map_add_dims(schedule_i, isl_dim_out,
3332 max_depth - depth);
3333 for (j = depth; j < max_depth; ++j)
3334 schedule_i = isl_map_fix_si(schedule_i,
3335 isl_dim_out, j, 0);
3336 schedule = isl_union_map_add_map(schedule, schedule_i);
3339 return schedule;
3342 /* Does expression "expr" write to "id"?
3344 static int expr_writes(struct pet_expr *expr, __isl_keep isl_id *id)
3346 int i;
3347 isl_id *write_id;
3349 for (i = 0; i < expr->n_arg; ++i) {
3350 int writes = expr_writes(expr->args[i], id);
3351 if (writes < 0 || writes)
3352 return writes;
3355 if (expr->type != pet_expr_access)
3356 return 0;
3357 if (!expr->acc.write)
3358 return 0;
3359 if (pet_expr_is_affine(expr))
3360 return 0;
3362 write_id = pet_expr_access_get_id(expr);
3363 isl_id_free(write_id);
3365 if (!write_id)
3366 return -1;
3368 return write_id == id;
3371 /* Does statement "stmt" write to "id"?
3373 static int stmt_writes(struct pet_stmt *stmt, __isl_keep isl_id *id)
3375 return expr_writes(stmt->body, id);
3378 /* Is there any write access in "scop" that accesses "id"?
3380 int pet_scop_writes(struct pet_scop *scop, __isl_keep isl_id *id)
3382 int i;
3384 if (!scop)
3385 return -1;
3387 for (i = 0; i < scop->n_stmt; ++i) {
3388 int writes = stmt_writes(scop->stmts[i], id);
3389 if (writes < 0 || writes)
3390 return writes;
3393 return 0;
3396 /* Add a reference identifier to access expression "expr".
3397 * "user" points to an integer that contains the sequence number
3398 * of the next reference.
3400 static struct pet_expr *access_add_ref_id(struct pet_expr *expr, void *user)
3402 isl_ctx *ctx;
3403 char name[50];
3404 int *n_ref = user;
3406 if (!expr)
3407 return expr;
3409 ctx = isl_map_get_ctx(expr->acc.access);
3410 snprintf(name, sizeof(name), "__pet_ref_%d", (*n_ref)++);
3411 expr->acc.ref_id = isl_id_alloc(ctx, name, NULL);
3412 if (!expr->acc.ref_id)
3413 return pet_expr_free(expr);
3415 return expr;
3418 /* Add a reference identifier to all access expressions in "stmt".
3419 * "n_ref" points to an integer that contains the sequence number
3420 * of the next reference.
3422 static struct pet_stmt *stmt_add_ref_ids(struct pet_stmt *stmt, int *n_ref)
3424 int i;
3426 if (!stmt)
3427 return NULL;
3429 for (i = 0; i < stmt->n_arg; ++i) {
3430 stmt->args[i] = pet_expr_map_access(stmt->args[i],
3431 &access_add_ref_id, n_ref);
3432 if (!stmt->args[i])
3433 return pet_stmt_free(stmt);
3436 stmt->body = pet_expr_map_access(stmt->body, &access_add_ref_id, n_ref);
3437 if (!stmt->body)
3438 return pet_stmt_free(stmt);
3440 return stmt;
3443 /* Add a reference identifier to all access expressions in "scop".
3445 struct pet_scop *pet_scop_add_ref_ids(struct pet_scop *scop)
3447 int i;
3448 int n_ref;
3450 if (!scop)
3451 return NULL;
3453 n_ref = 0;
3454 for (i = 0; i < scop->n_stmt; ++i) {
3455 scop->stmts[i] = stmt_add_ref_ids(scop->stmts[i], &n_ref);
3456 if (!scop->stmts[i])
3457 return pet_scop_free(scop);
3460 return scop;
3463 /* Reset the user pointer on the tuple id and all parameter ids in "set".
3465 static __isl_give isl_set *set_anonymize(__isl_take isl_set *set)
3467 int i, n;
3469 n = isl_set_dim(set, isl_dim_param);
3470 for (i = 0; i < n; ++i) {
3471 isl_id *id = isl_set_get_dim_id(set, isl_dim_param, i);
3472 const char *name = isl_id_get_name(id);
3473 set = isl_set_set_dim_name(set, isl_dim_param, i, name);
3474 isl_id_free(id);
3477 if (!isl_set_is_params(set) && isl_set_has_tuple_id(set)) {
3478 isl_id *id = isl_set_get_tuple_id(set);
3479 const char *name = isl_id_get_name(id);
3480 set = isl_set_set_tuple_name(set, name);
3481 isl_id_free(id);
3484 return set;
3487 /* Reset the user pointer on the tuple ids and all parameter ids in "map".
3489 static __isl_give isl_map *map_anonymize(__isl_take isl_map *map)
3491 int i, n;
3493 n = isl_map_dim(map, isl_dim_param);
3494 for (i = 0; i < n; ++i) {
3495 isl_id *id = isl_map_get_dim_id(map, isl_dim_param, i);
3496 const char *name = isl_id_get_name(id);
3497 map = isl_map_set_dim_name(map, isl_dim_param, i, name);
3498 isl_id_free(id);
3501 if (isl_map_has_tuple_id(map, isl_dim_in)) {
3502 isl_id *id = isl_map_get_tuple_id(map, isl_dim_in);
3503 const char *name = isl_id_get_name(id);
3504 map = isl_map_set_tuple_name(map, isl_dim_in, name);
3505 isl_id_free(id);
3508 if (isl_map_has_tuple_id(map, isl_dim_out)) {
3509 isl_id *id = isl_map_get_tuple_id(map, isl_dim_out);
3510 const char *name = isl_id_get_name(id);
3511 map = isl_map_set_tuple_name(map, isl_dim_out, name);
3512 isl_id_free(id);
3515 return map;
3518 /* Reset the user pointer on the tuple ids and all parameter ids in "mpa".
3520 static __isl_give isl_multi_pw_aff *multi_pw_aff_anonymize(
3521 __isl_take isl_multi_pw_aff *mpa)
3523 int i, n;
3525 n = isl_multi_pw_aff_dim(mpa, isl_dim_param);
3526 for (i = 0; i < n; ++i) {
3527 isl_id *id = isl_multi_pw_aff_get_dim_id(mpa, isl_dim_param, i);
3528 const char *name = isl_id_get_name(id);
3529 mpa = isl_multi_pw_aff_set_dim_name(mpa,
3530 isl_dim_param, i, name);
3531 isl_id_free(id);
3534 if (isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_in)) {
3535 isl_id *id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_in);
3536 const char *name = isl_id_get_name(id);
3537 mpa = isl_multi_pw_aff_set_tuple_name(mpa, isl_dim_in, name);
3538 isl_id_free(id);
3541 if (isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out)) {
3542 isl_id *id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_out);
3543 const char *name = isl_id_get_name(id);
3544 mpa = isl_multi_pw_aff_set_tuple_name(mpa, isl_dim_out, name);
3545 isl_id_free(id);
3548 return mpa;
3551 /* Reset the user pointer on all parameter ids in "array".
3553 static struct pet_array *array_anonymize(struct pet_array *array)
3555 if (!array)
3556 return NULL;
3558 array->context = set_anonymize(array->context);
3559 array->extent = set_anonymize(array->extent);
3560 if (!array->context || !array->extent)
3561 return pet_array_free(array);
3563 return array;
3566 /* Reset the user pointer on all parameter and tuple ids in
3567 * the access relation and the index expressions
3568 * of the access expression "expr".
3570 static struct pet_expr *access_anonymize(struct pet_expr *expr, void *user)
3572 expr->acc.access = map_anonymize(expr->acc.access);
3573 expr->acc.index = multi_pw_aff_anonymize(expr->acc.index);
3574 if (!expr->acc.access || !expr->acc.index)
3575 return pet_expr_free(expr);
3577 return expr;
3580 /* Reset the user pointer on all parameter and tuple ids in "stmt".
3582 static struct pet_stmt *stmt_anonymize(struct pet_stmt *stmt)
3584 int i;
3585 isl_space *space;
3586 isl_set *domain;
3588 if (!stmt)
3589 return NULL;
3591 stmt->domain = set_anonymize(stmt->domain);
3592 stmt->schedule = map_anonymize(stmt->schedule);
3593 if (!stmt->domain || !stmt->schedule)
3594 return pet_stmt_free(stmt);
3596 for (i = 0; i < stmt->n_arg; ++i) {
3597 stmt->args[i] = pet_expr_map_access(stmt->args[i],
3598 &access_anonymize, NULL);
3599 if (!stmt->args[i])
3600 return pet_stmt_free(stmt);
3603 stmt->body = pet_expr_map_access(stmt->body,
3604 &access_anonymize, NULL);
3605 if (!stmt->body)
3606 return pet_stmt_free(stmt);
3608 return stmt;
3611 /* Reset the user pointer on the tuple ids and all parameter ids
3612 * in "implication".
3614 static struct pet_implication *implication_anonymize(
3615 struct pet_implication *implication)
3617 if (!implication)
3618 return NULL;
3620 implication->extension = map_anonymize(implication->extension);
3621 if (!implication->extension)
3622 return pet_implication_free(implication);
3624 return implication;
3627 /* Reset the user pointer on all parameter and tuple ids in "scop".
3629 struct pet_scop *pet_scop_anonymize(struct pet_scop *scop)
3631 int i;
3633 if (!scop)
3634 return NULL;
3636 scop->context = set_anonymize(scop->context);
3637 scop->context_value = set_anonymize(scop->context_value);
3638 if (!scop->context || !scop->context_value)
3639 return pet_scop_free(scop);
3641 for (i = 0; i < scop->n_array; ++i) {
3642 scop->arrays[i] = array_anonymize(scop->arrays[i]);
3643 if (!scop->arrays[i])
3644 return pet_scop_free(scop);
3647 for (i = 0; i < scop->n_stmt; ++i) {
3648 scop->stmts[i] = stmt_anonymize(scop->stmts[i]);
3649 if (!scop->stmts[i])
3650 return pet_scop_free(scop);
3653 for (i = 0; i < scop->n_implication; ++i) {
3654 scop->implications[i] =
3655 implication_anonymize(scop->implications[i]);
3656 if (!scop->implications[i])
3657 return pet_scop_free(scop);
3660 return scop;
3663 /* If "value_bounds" contains any bounds on the variable accessed by "arg",
3664 * then intersect the range of "map" with the valid set of values.
3666 static __isl_give isl_map *access_apply_value_bounds(__isl_take isl_map *map,
3667 struct pet_expr *arg, __isl_keep isl_union_map *value_bounds)
3669 isl_id *id;
3670 isl_map *vb;
3671 isl_space *space;
3672 isl_ctx *ctx = isl_map_get_ctx(map);
3674 id = pet_expr_access_get_id(arg);
3675 space = isl_space_alloc(ctx, 0, 0, 1);
3676 space = isl_space_set_tuple_id(space, isl_dim_in, id);
3677 vb = isl_union_map_extract_map(value_bounds, space);
3678 if (!isl_map_plain_is_empty(vb))
3679 map = isl_map_intersect_range(map, isl_map_range(vb));
3680 else
3681 isl_map_free(vb);
3683 return map;
3686 /* Given a set "domain", return a wrapped relation with the given set
3687 * as domain and a range of dimension "n_arg", where each coordinate
3688 * is either unbounded or, if the corresponding element of args is of
3689 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
3691 static __isl_give isl_set *apply_value_bounds(__isl_take isl_set *domain,
3692 unsigned n_arg, struct pet_expr **args,
3693 __isl_keep isl_union_map *value_bounds)
3695 int i;
3696 isl_map *map;
3697 isl_space *space;
3699 map = isl_map_from_domain(domain);
3700 space = isl_map_get_space(map);
3701 space = isl_space_add_dims(space, isl_dim_out, 1);
3703 for (i = 0; i < n_arg; ++i) {
3704 isl_map *map_i;
3705 struct pet_expr *arg = args[i];
3707 map_i = isl_map_universe(isl_space_copy(space));
3708 if (arg->type == pet_expr_access)
3709 map_i = access_apply_value_bounds(map_i, arg,
3710 value_bounds);
3711 map = isl_map_flat_range_product(map, map_i);
3713 isl_space_free(space);
3715 return isl_map_wrap(map);
3718 /* Data used in access_gist() callback.
3720 struct pet_access_gist_data {
3721 isl_set *domain;
3722 isl_union_map *value_bounds;
3725 /* Given an expression "expr" of type pet_expr_access, compute
3726 * the gist of the associated access relation and index expression
3727 * with respect to data->domain and the bounds on the values of the arguments
3728 * of the expression.
3730 static struct pet_expr *access_gist(struct pet_expr *expr, void *user)
3732 struct pet_access_gist_data *data = user;
3733 isl_set *domain;
3735 domain = isl_set_copy(data->domain);
3736 if (expr->n_arg > 0)
3737 domain = apply_value_bounds(domain, expr->n_arg, expr->args,
3738 data->value_bounds);
3740 expr->acc.access = isl_map_gist_domain(expr->acc.access,
3741 isl_set_copy(domain));
3742 expr->acc.index = isl_multi_pw_aff_gist(expr->acc.index, domain);
3743 if (!expr->acc.access || !expr->acc.index)
3744 return pet_expr_free(expr);
3746 return expr;
3749 /* Compute the gist of the iteration domain and all access relations
3750 * of "stmt" based on the constraints on the parameters specified by "context"
3751 * and the constraints on the values of nested accesses specified
3752 * by "value_bounds".
3754 static struct pet_stmt *stmt_gist(struct pet_stmt *stmt,
3755 __isl_keep isl_set *context, __isl_keep isl_union_map *value_bounds)
3757 int i;
3758 isl_space *space;
3759 isl_set *domain;
3760 struct pet_access_gist_data data;
3762 if (!stmt)
3763 return NULL;
3765 data.domain = isl_set_copy(stmt->domain);
3766 data.value_bounds = value_bounds;
3767 if (stmt->n_arg > 0)
3768 data.domain = isl_map_domain(isl_set_unwrap(data.domain));
3770 data.domain = isl_set_intersect_params(data.domain,
3771 isl_set_copy(context));
3773 for (i = 0; i < stmt->n_arg; ++i) {
3774 stmt->args[i] = pet_expr_map_access(stmt->args[i],
3775 &access_gist, &data);
3776 if (!stmt->args[i])
3777 goto error;
3780 stmt->body = pet_expr_map_access(stmt->body, &access_gist, &data);
3781 if (!stmt->body)
3782 goto error;
3784 isl_set_free(data.domain);
3786 space = isl_set_get_space(stmt->domain);
3787 if (isl_space_is_wrapping(space))
3788 space = isl_space_domain(isl_space_unwrap(space));
3789 domain = isl_set_universe(space);
3790 domain = isl_set_intersect_params(domain, isl_set_copy(context));
3791 if (stmt->n_arg > 0)
3792 domain = apply_value_bounds(domain, stmt->n_arg, stmt->args,
3793 value_bounds);
3794 stmt->domain = isl_set_gist(stmt->domain, domain);
3795 if (!stmt->domain)
3796 return pet_stmt_free(stmt);
3798 return stmt;
3799 error:
3800 isl_set_free(data.domain);
3801 return pet_stmt_free(stmt);
3804 /* Compute the gist of the extent of the array
3805 * based on the constraints on the parameters specified by "context".
3807 static struct pet_array *array_gist(struct pet_array *array,
3808 __isl_keep isl_set *context)
3810 if (!array)
3811 return NULL;
3813 array->extent = isl_set_gist_params(array->extent,
3814 isl_set_copy(context));
3815 if (!array->extent)
3816 return pet_array_free(array);
3818 return array;
3821 /* Compute the gist of all sets and relations in "scop"
3822 * based on the constraints on the parameters specified by "scop->context"
3823 * and the constraints on the values of nested accesses specified
3824 * by "value_bounds".
3826 struct pet_scop *pet_scop_gist(struct pet_scop *scop,
3827 __isl_keep isl_union_map *value_bounds)
3829 int i;
3831 if (!scop)
3832 return NULL;
3834 scop->context = isl_set_coalesce(scop->context);
3835 if (!scop->context)
3836 return pet_scop_free(scop);
3838 for (i = 0; i < scop->n_array; ++i) {
3839 scop->arrays[i] = array_gist(scop->arrays[i], scop->context);
3840 if (!scop->arrays[i])
3841 return pet_scop_free(scop);
3844 for (i = 0; i < scop->n_stmt; ++i) {
3845 scop->stmts[i] = stmt_gist(scop->stmts[i], scop->context,
3846 value_bounds);
3847 if (!scop->stmts[i])
3848 return pet_scop_free(scop);
3851 return scop;
3854 /* Intersect the context of "scop" with "context".
3855 * To ensure that we don't introduce any unnamed parameters in
3856 * the context of "scop", we first remove the unnamed parameters
3857 * from "context".
3859 struct pet_scop *pet_scop_restrict_context(struct pet_scop *scop,
3860 __isl_take isl_set *context)
3862 if (!scop)
3863 goto error;
3865 context = set_project_out_unnamed_params(context);
3866 scop->context = isl_set_intersect(scop->context, context);
3867 if (!scop->context)
3868 return pet_scop_free(scop);
3870 return scop;
3871 error:
3872 isl_set_free(context);
3873 return pet_scop_free(scop);
3876 /* Drop the current context of "scop". That is, replace the context
3877 * by a universal set.
3879 struct pet_scop *pet_scop_reset_context(struct pet_scop *scop)
3881 isl_space *space;
3883 if (!scop)
3884 return NULL;
3886 space = isl_set_get_space(scop->context);
3887 isl_set_free(scop->context);
3888 scop->context = isl_set_universe(space);
3889 if (!scop->context)
3890 return pet_scop_free(scop);
3892 return scop;
3895 /* Append "array" to the arrays of "scop".
3897 struct pet_scop *pet_scop_add_array(struct pet_scop *scop,
3898 struct pet_array *array)
3900 isl_ctx *ctx;
3901 struct pet_array **arrays;
3903 if (!array || !scop)
3904 goto error;
3906 ctx = isl_set_get_ctx(scop->context);
3907 arrays = isl_realloc_array(ctx, scop->arrays, struct pet_array *,
3908 scop->n_array + 1);
3909 if (!arrays)
3910 goto error;
3911 scop->arrays = arrays;
3912 scop->arrays[scop->n_array] = array;
3913 scop->n_array++;
3915 return scop;
3916 error:
3917 pet_array_free(array);
3918 return pet_scop_free(scop);
3921 /* Create and return an implication on filter values equal to "satisfied"
3922 * with extension "map".
3924 static struct pet_implication *new_implication(__isl_take isl_map *map,
3925 int satisfied)
3927 isl_ctx *ctx;
3928 struct pet_implication *implication;
3930 if (!map)
3931 return NULL;
3932 ctx = isl_map_get_ctx(map);
3933 implication = isl_alloc_type(ctx, struct pet_implication);
3934 if (!implication)
3935 goto error;
3937 implication->extension = map;
3938 implication->satisfied = satisfied;
3940 return implication;
3941 error:
3942 isl_map_free(map);
3943 return NULL;
3946 /* Add an implication on filter values equal to "satisfied"
3947 * with extension "map" to "scop".
3949 struct pet_scop *pet_scop_add_implication(struct pet_scop *scop,
3950 __isl_take isl_map *map, int satisfied)
3952 isl_ctx *ctx;
3953 struct pet_implication *implication;
3954 struct pet_implication **implications;
3956 implication = new_implication(map, satisfied);
3957 if (!scop || !implication)
3958 goto error;
3960 ctx = isl_set_get_ctx(scop->context);
3961 implications = isl_realloc_array(ctx, scop->implications,
3962 struct pet_implication *,
3963 scop->n_implication + 1);
3964 if (!implications)
3965 goto error;
3966 scop->implications = implications;
3967 scop->implications[scop->n_implication] = implication;
3968 scop->n_implication++;
3970 return scop;
3971 error:
3972 pet_implication_free(implication);
3973 return pet_scop_free(scop);
3976 /* Given an access expression, check if it is data dependent.
3977 * If so, set *found and abort the search.
3979 static int is_data_dependent(struct pet_expr *expr, void *user)
3981 int *found = user;
3983 if (expr->n_arg) {
3984 *found = 1;
3985 return -1;
3988 return 0;
3991 /* Does "scop" contain any data dependent accesses?
3993 * Check the body of each statement for such accesses.
3995 int pet_scop_has_data_dependent_accesses(struct pet_scop *scop)
3997 int i;
3998 int found = 0;
4000 if (!scop)
4001 return -1;
4003 for (i = 0; i < scop->n_stmt; ++i) {
4004 int r = pet_expr_foreach_access_expr(scop->stmts[i]->body,
4005 &is_data_dependent, &found);
4006 if (r < 0 && !found)
4007 return -1;
4008 if (found)
4009 return found;
4012 return found;
4015 /* Does "scop" contain and data dependent conditions?
4017 int pet_scop_has_data_dependent_conditions(struct pet_scop *scop)
4019 int i;
4021 if (!scop)
4022 return -1;
4024 for (i = 0; i < scop->n_stmt; ++i)
4025 if (scop->stmts[i]->n_arg > 0)
4026 return 1;
4028 return 0;