update isl for improved support for isl_multi_pw_aff
[pet.git] / scop.c
blobed33fbcb25f7f64562a623cdd50e37b7eaefcc9d
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 either by a variable, which
85 * is assumed to attain values zero and one, or by a boolean affine
86 * expression. The condition holds if the variable has value one
87 * or if the affine expression has value one (typically for only
88 * part of the parameter space).
90 * A missing condition (skip[type] == NULL) means that we don't want
91 * to skip anything.
93 struct pet_scop_ext {
94 struct pet_scop scop;
96 isl_set *skip[2];
99 const char *pet_op_str(enum pet_op_type op)
101 return op_str[op];
104 int pet_op_is_inc_dec(enum pet_op_type op)
106 return op == pet_op_post_inc || op == pet_op_post_dec ||
107 op == pet_op_pre_inc || op == pet_op_pre_dec;
110 const char *pet_type_str(enum pet_expr_type type)
112 return type_str[type];
115 enum pet_op_type pet_str_op(const char *str)
117 int i;
119 for (i = 0; i < ARRAY_SIZE(op_str); ++i)
120 if (!strcmp(op_str[i], str))
121 return i;
123 return -1;
126 enum pet_expr_type pet_str_type(const char *str)
128 int i;
130 for (i = 0; i < ARRAY_SIZE(type_str); ++i)
131 if (!strcmp(type_str[i], str))
132 return i;
134 return -1;
137 /* Construct a pet_expr from an access relation.
138 * By default, it is considered to be a read access.
140 struct pet_expr *pet_expr_from_access(__isl_take isl_map *access)
142 isl_ctx *ctx = isl_map_get_ctx(access);
143 struct pet_expr *expr;
145 if (!access)
146 return NULL;
147 expr = isl_calloc_type(ctx, struct pet_expr);
148 if (!expr)
149 goto error;
151 expr->type = pet_expr_access;
152 expr->acc.access = access;
153 expr->acc.read = 1;
154 expr->acc.write = 0;
156 return expr;
157 error:
158 isl_map_free(access);
159 return NULL;
162 /* Construct a pet_expr that kills the elements specified by "access".
164 struct pet_expr *pet_expr_kill_from_access(__isl_take isl_map *access)
166 isl_ctx *ctx;
167 struct pet_expr *expr;
169 ctx = isl_map_get_ctx(access);
170 expr = pet_expr_from_access(access);
171 if (!expr)
172 return NULL;
173 expr->acc.read = 0;
174 return pet_expr_new_unary(ctx, pet_op_kill, expr);
177 /* Construct a unary pet_expr that performs "op" on "arg".
179 struct pet_expr *pet_expr_new_unary(isl_ctx *ctx, enum pet_op_type op,
180 struct pet_expr *arg)
182 struct pet_expr *expr;
184 if (!arg)
185 goto error;
186 expr = isl_alloc_type(ctx, struct pet_expr);
187 if (!expr)
188 goto error;
190 expr->type = pet_expr_unary;
191 expr->op = op;
192 expr->n_arg = 1;
193 expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
194 if (!expr->args)
195 goto error;
196 expr->args[pet_un_arg] = arg;
198 return expr;
199 error:
200 pet_expr_free(arg);
201 return NULL;
204 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
206 struct pet_expr *pet_expr_new_binary(isl_ctx *ctx, enum pet_op_type op,
207 struct pet_expr *lhs, struct pet_expr *rhs)
209 struct pet_expr *expr;
211 if (!lhs || !rhs)
212 goto error;
213 expr = isl_alloc_type(ctx, struct pet_expr);
214 if (!expr)
215 goto error;
217 expr->type = pet_expr_binary;
218 expr->op = op;
219 expr->n_arg = 2;
220 expr->args = isl_calloc_array(ctx, struct pet_expr *, 2);
221 if (!expr->args)
222 goto error;
223 expr->args[pet_bin_lhs] = lhs;
224 expr->args[pet_bin_rhs] = rhs;
226 return expr;
227 error:
228 pet_expr_free(lhs);
229 pet_expr_free(rhs);
230 return NULL;
233 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
235 struct pet_expr *pet_expr_new_ternary(isl_ctx *ctx, struct pet_expr *cond,
236 struct pet_expr *lhs, struct pet_expr *rhs)
238 struct pet_expr *expr;
240 if (!cond || !lhs || !rhs)
241 goto error;
242 expr = isl_alloc_type(ctx, struct pet_expr);
243 if (!expr)
244 goto error;
246 expr->type = pet_expr_ternary;
247 expr->n_arg = 3;
248 expr->args = isl_calloc_array(ctx, struct pet_expr *, 3);
249 if (!expr->args)
250 goto error;
251 expr->args[pet_ter_cond] = cond;
252 expr->args[pet_ter_true] = lhs;
253 expr->args[pet_ter_false] = rhs;
255 return expr;
256 error:
257 pet_expr_free(cond);
258 pet_expr_free(lhs);
259 pet_expr_free(rhs);
260 return NULL;
263 /* Construct a call pet_expr that calls function "name" with "n_arg"
264 * arguments. The caller is responsible for filling in the arguments.
266 struct pet_expr *pet_expr_new_call(isl_ctx *ctx, const char *name,
267 unsigned n_arg)
269 struct pet_expr *expr;
271 expr = isl_alloc_type(ctx, struct pet_expr);
272 if (!expr)
273 return NULL;
275 expr->type = pet_expr_call;
276 expr->n_arg = n_arg;
277 expr->name = strdup(name);
278 expr->args = isl_calloc_array(ctx, struct pet_expr *, n_arg);
279 if (!expr->name || !expr->args)
280 return pet_expr_free(expr);
282 return expr;
285 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
287 struct pet_expr *pet_expr_new_cast(isl_ctx *ctx, const char *type_name,
288 struct pet_expr *arg)
290 struct pet_expr *expr;
292 if (!arg)
293 return NULL;
295 expr = isl_alloc_type(ctx, struct pet_expr);
296 if (!expr)
297 goto error;
299 expr->type = pet_expr_cast;
300 expr->n_arg = 1;
301 expr->type_name = strdup(type_name);
302 expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
303 if (!expr->type_name || !expr->args)
304 goto error;
306 expr->args[0] = arg;
308 return expr;
309 error:
310 pet_expr_free(arg);
311 pet_expr_free(expr);
312 return NULL;
315 /* Construct a pet_expr that represents the double "d".
317 struct pet_expr *pet_expr_new_double(isl_ctx *ctx, double val, const char *s)
319 struct pet_expr *expr;
321 expr = isl_calloc_type(ctx, struct pet_expr);
322 if (!expr)
323 return NULL;
325 expr->type = pet_expr_double;
326 expr->d.val = val;
327 expr->d.s = strdup(s);
328 if (!expr->d.s)
329 return pet_expr_free(expr);
331 return expr;
334 void *pet_expr_free(struct pet_expr *expr)
336 int i;
338 if (!expr)
339 return NULL;
341 for (i = 0; i < expr->n_arg; ++i)
342 pet_expr_free(expr->args[i]);
343 free(expr->args);
345 switch (expr->type) {
346 case pet_expr_access:
347 isl_id_free(expr->acc.ref_id);
348 isl_map_free(expr->acc.access);
349 break;
350 case pet_expr_call:
351 free(expr->name);
352 break;
353 case pet_expr_cast:
354 free(expr->type_name);
355 break;
356 case pet_expr_double:
357 free(expr->d.s);
358 break;
359 case pet_expr_unary:
360 case pet_expr_binary:
361 case pet_expr_ternary:
362 break;
365 free(expr);
366 return NULL;
369 static void expr_dump(struct pet_expr *expr, int indent)
371 int i;
373 if (!expr)
374 return;
376 fprintf(stderr, "%*s", indent, "");
378 switch (expr->type) {
379 case pet_expr_double:
380 fprintf(stderr, "%s\n", expr->d.s);
381 break;
382 case pet_expr_access:
383 isl_id_dump(expr->acc.ref_id);
384 fprintf(stderr, "%*s", indent, "");
385 isl_map_dump(expr->acc.access);
386 fprintf(stderr, "%*sread: %d\n", indent + 2,
387 "", expr->acc.read);
388 fprintf(stderr, "%*swrite: %d\n", indent + 2,
389 "", expr->acc.write);
390 for (i = 0; i < expr->n_arg; ++i)
391 expr_dump(expr->args[i], indent + 2);
392 break;
393 case pet_expr_unary:
394 fprintf(stderr, "%s\n", op_str[expr->op]);
395 expr_dump(expr->args[pet_un_arg], indent + 2);
396 break;
397 case pet_expr_binary:
398 fprintf(stderr, "%s\n", op_str[expr->op]);
399 expr_dump(expr->args[pet_bin_lhs], indent + 2);
400 expr_dump(expr->args[pet_bin_rhs], indent + 2);
401 break;
402 case pet_expr_ternary:
403 fprintf(stderr, "?:\n");
404 expr_dump(expr->args[pet_ter_cond], indent + 2);
405 expr_dump(expr->args[pet_ter_true], indent + 2);
406 expr_dump(expr->args[pet_ter_false], indent + 2);
407 break;
408 case pet_expr_call:
409 fprintf(stderr, "%s/%d\n", expr->name, expr->n_arg);
410 for (i = 0; i < expr->n_arg; ++i)
411 expr_dump(expr->args[i], indent + 2);
412 break;
413 case pet_expr_cast:
414 fprintf(stderr, "(%s)\n", expr->type_name);
415 for (i = 0; i < expr->n_arg; ++i)
416 expr_dump(expr->args[i], indent + 2);
417 break;
421 void pet_expr_dump(struct pet_expr *expr)
423 expr_dump(expr, 0);
426 /* Does "expr" represent an access to an unnamed space, i.e.,
427 * does it represent an affine expression?
429 int pet_expr_is_affine(struct pet_expr *expr)
431 int has_id;
433 if (!expr)
434 return -1;
435 if (expr->type != pet_expr_access)
436 return 0;
438 has_id = isl_map_has_tuple_id(expr->acc.access, isl_dim_out);
439 if (has_id < 0)
440 return -1;
442 return !has_id;
445 /* Return the identifier of the array accessed by "expr".
447 __isl_give isl_id *pet_expr_access_get_id(struct pet_expr *expr)
449 if (!expr)
450 return NULL;
451 if (expr->type != pet_expr_access)
452 return NULL;
453 return isl_map_get_tuple_id(expr->acc.access, isl_dim_out);
456 /* Does "expr" represent an access to a scalar, i.e., zero-dimensional array?
458 int pet_expr_is_scalar_access(struct pet_expr *expr)
460 if (!expr)
461 return -1;
462 if (expr->type != pet_expr_access)
463 return 0;
465 return isl_map_dim(expr->acc.access, isl_dim_out) == 0;
468 /* Return 1 if the two pet_exprs are equivalent.
470 int pet_expr_is_equal(struct pet_expr *expr1, struct pet_expr *expr2)
472 int i;
474 if (!expr1 || !expr2)
475 return 0;
477 if (expr1->type != expr2->type)
478 return 0;
479 if (expr1->n_arg != expr2->n_arg)
480 return 0;
481 for (i = 0; i < expr1->n_arg; ++i)
482 if (!pet_expr_is_equal(expr1->args[i], expr2->args[i]))
483 return 0;
484 switch (expr1->type) {
485 case pet_expr_double:
486 if (strcmp(expr1->d.s, expr2->d.s))
487 return 0;
488 if (expr1->d.val != expr2->d.val)
489 return 0;
490 break;
491 case pet_expr_access:
492 if (expr1->acc.read != expr2->acc.read)
493 return 0;
494 if (expr1->acc.write != expr2->acc.write)
495 return 0;
496 if (expr1->acc.ref_id != expr2->acc.ref_id)
497 return 0;
498 if (!expr1->acc.access || !expr2->acc.access)
499 return 0;
500 if (!isl_map_is_equal(expr1->acc.access, expr2->acc.access))
501 return 0;
502 break;
503 case pet_expr_unary:
504 case pet_expr_binary:
505 case pet_expr_ternary:
506 if (expr1->op != expr2->op)
507 return 0;
508 break;
509 case pet_expr_call:
510 if (strcmp(expr1->name, expr2->name))
511 return 0;
512 break;
513 case pet_expr_cast:
514 if (strcmp(expr1->type_name, expr2->type_name))
515 return 0;
516 break;
519 return 1;
522 /* Add extra conditions on the parameters to all access relations in "expr".
524 struct pet_expr *pet_expr_restrict(struct pet_expr *expr,
525 __isl_take isl_set *cond)
527 int i;
529 if (!expr)
530 goto error;
532 for (i = 0; i < expr->n_arg; ++i) {
533 expr->args[i] = pet_expr_restrict(expr->args[i],
534 isl_set_copy(cond));
535 if (!expr->args[i])
536 goto error;
539 if (expr->type == pet_expr_access) {
540 expr->acc.access = isl_map_intersect_params(expr->acc.access,
541 isl_set_copy(cond));
542 if (!expr->acc.access)
543 goto error;
546 isl_set_free(cond);
547 return expr;
548 error:
549 isl_set_free(cond);
550 return pet_expr_free(expr);
553 /* Modify all expressions of type pet_expr_access in "expr"
554 * by calling "fn" on them.
556 struct pet_expr *pet_expr_map_access(struct pet_expr *expr,
557 struct pet_expr *(*fn)(struct pet_expr *expr, void *user),
558 void *user)
560 int i;
562 if (!expr)
563 return NULL;
565 for (i = 0; i < expr->n_arg; ++i) {
566 expr->args[i] = pet_expr_map_access(expr->args[i], fn, user);
567 if (!expr->args[i])
568 return pet_expr_free(expr);
571 if (expr->type == pet_expr_access)
572 expr = fn(expr, user);
574 return expr;
577 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
579 * Return -1 on error (where fn return a negative value is treated as an error).
580 * Otherwise return 0.
582 int pet_expr_foreach_access_expr(struct pet_expr *expr,
583 int (*fn)(struct pet_expr *expr, void *user), void *user)
585 int i;
587 if (!expr)
588 return -1;
590 for (i = 0; i < expr->n_arg; ++i)
591 if (pet_expr_foreach_access_expr(expr->args[i], fn, user) < 0)
592 return -1;
594 if (expr->type == pet_expr_access)
595 return fn(expr, user);
597 return 0;
600 /* Modify the access relation of the given access expression
601 * based on the given iteration space transformation.
602 * If the access has any arguments then the domain of the access relation
603 * is a wrapped mapping from the iteration space to the space of
604 * argument values. We only need to change the domain of this wrapped
605 * mapping, so we extend the input transformation with an identity mapping
606 * on the space of argument values.
608 static struct pet_expr *update_domain(struct pet_expr *expr, void *user)
610 isl_map *update = user;
611 isl_space *dim;
613 update = isl_map_copy(update);
615 dim = isl_map_get_space(expr->acc.access);
616 dim = isl_space_domain(dim);
617 if (!isl_space_is_wrapping(dim))
618 isl_space_free(dim);
619 else {
620 isl_map *id;
621 dim = isl_space_unwrap(dim);
622 dim = isl_space_range(dim);
623 dim = isl_space_map_from_set(dim);
624 id = isl_map_identity(dim);
625 update = isl_map_product(update, id);
628 expr->acc.access = isl_map_apply_domain(expr->acc.access, update);
629 if (!expr->acc.access)
630 return pet_expr_free(expr);
632 return expr;
635 /* Modify all access relations in "expr" based on the given iteration space
636 * transformation.
638 static struct pet_expr *expr_update_domain(struct pet_expr *expr,
639 __isl_take isl_map *update)
641 expr = pet_expr_map_access(expr, &update_domain, update);
642 isl_map_free(update);
643 return expr;
646 /* Construct a pet_stmt with given line number and statement
647 * number from a pet_expr.
648 * The initial iteration domain is the zero-dimensional universe.
649 * The name of the domain is given by "label" if it is non-NULL.
650 * Otherwise, the name is constructed as S_<id>.
651 * The domains of all access relations are modified to refer
652 * to the statement iteration domain.
654 struct pet_stmt *pet_stmt_from_pet_expr(isl_ctx *ctx, int line,
655 __isl_take isl_id *label, int id, struct pet_expr *expr)
657 struct pet_stmt *stmt;
658 isl_space *dim;
659 isl_set *dom;
660 isl_map *sched;
661 isl_map *add_name;
662 char name[50];
664 if (!expr)
665 goto error;
667 stmt = isl_calloc_type(ctx, struct pet_stmt);
668 if (!stmt)
669 goto error;
671 dim = isl_space_set_alloc(ctx, 0, 0);
672 if (label)
673 dim = isl_space_set_tuple_id(dim, isl_dim_set, label);
674 else {
675 snprintf(name, sizeof(name), "S_%d", id);
676 dim = isl_space_set_tuple_name(dim, isl_dim_set, name);
678 dom = isl_set_universe(isl_space_copy(dim));
679 sched = isl_map_from_domain(isl_set_copy(dom));
681 dim = isl_space_from_range(dim);
682 add_name = isl_map_universe(dim);
683 expr = expr_update_domain(expr, add_name);
685 stmt->line = line;
686 stmt->domain = dom;
687 stmt->schedule = sched;
688 stmt->body = expr;
690 if (!stmt->domain || !stmt->schedule || !stmt->body)
691 return pet_stmt_free(stmt);
693 return stmt;
694 error:
695 isl_id_free(label);
696 return pet_expr_free(expr);
699 void *pet_stmt_free(struct pet_stmt *stmt)
701 int i;
703 if (!stmt)
704 return NULL;
706 isl_set_free(stmt->domain);
707 isl_map_free(stmt->schedule);
708 pet_expr_free(stmt->body);
710 for (i = 0; i < stmt->n_arg; ++i)
711 pet_expr_free(stmt->args[i]);
712 free(stmt->args);
714 free(stmt);
715 return NULL;
718 static void stmt_dump(struct pet_stmt *stmt, int indent)
720 int i;
722 if (!stmt)
723 return;
725 fprintf(stderr, "%*s%d\n", indent, "", stmt->line);
726 fprintf(stderr, "%*s", indent, "");
727 isl_set_dump(stmt->domain);
728 fprintf(stderr, "%*s", indent, "");
729 isl_map_dump(stmt->schedule);
730 expr_dump(stmt->body, indent);
731 for (i = 0; i < stmt->n_arg; ++i)
732 expr_dump(stmt->args[i], indent + 2);
735 void pet_stmt_dump(struct pet_stmt *stmt)
737 stmt_dump(stmt, 0);
740 struct pet_array *pet_array_free(struct pet_array *array)
742 if (!array)
743 return NULL;
745 isl_set_free(array->context);
746 isl_set_free(array->extent);
747 isl_set_free(array->value_bounds);
748 free(array->element_type);
750 free(array);
751 return NULL;
754 void pet_array_dump(struct pet_array *array)
756 if (!array)
757 return;
759 isl_set_dump(array->context);
760 isl_set_dump(array->extent);
761 isl_set_dump(array->value_bounds);
762 fprintf(stderr, "%s %s\n", array->element_type,
763 array->live_out ? "live-out" : "");
766 /* Alloc a pet_scop structure, with extra room for information that
767 * is only used during parsing.
769 struct pet_scop *pet_scop_alloc(isl_ctx *ctx)
771 return &isl_calloc_type(ctx, struct pet_scop_ext)->scop;
774 /* Construct a pet_scop with room for n statements.
776 static struct pet_scop *scop_alloc(isl_ctx *ctx, int n)
778 isl_space *space;
779 struct pet_scop *scop;
781 scop = pet_scop_alloc(ctx);
782 if (!scop)
783 return NULL;
785 space = isl_space_params_alloc(ctx, 0);
786 scop->context = isl_set_universe(isl_space_copy(space));
787 scop->context_value = isl_set_universe(space);
788 scop->stmts = isl_calloc_array(ctx, struct pet_stmt *, n);
789 if (!scop->context || !scop->stmts)
790 return pet_scop_free(scop);
792 scop->n_stmt = n;
794 return scop;
797 struct pet_scop *pet_scop_empty(isl_ctx *ctx)
799 return scop_alloc(ctx, 0);
802 /* Update "context" with respect to the valid parameter values for "access".
804 static __isl_give isl_set *access_extract_context(__isl_keep isl_map *access,
805 __isl_take isl_set *context)
807 context = isl_set_intersect(context,
808 isl_map_params(isl_map_copy(access)));
809 return context;
812 /* Update "context" with respect to the valid parameter values for "expr".
814 * If "expr" represents a ternary operator, then a parameter value
815 * needs to be valid for the condition and for at least one of the
816 * remaining two arguments.
817 * If the condition is an affine expression, then we can be a bit more specific.
818 * The parameter then has to be valid for the second argument for
819 * non-zero accesses and valid for the third argument for zero accesses.
821 static __isl_give isl_set *expr_extract_context(struct pet_expr *expr,
822 __isl_take isl_set *context)
824 int i;
826 if (expr->type == pet_expr_ternary) {
827 int is_aff;
828 isl_set *context1, *context2;
830 is_aff = pet_expr_is_affine(expr->args[0]);
831 if (is_aff < 0)
832 goto error;
834 context = expr_extract_context(expr->args[0], context);
835 context1 = expr_extract_context(expr->args[1],
836 isl_set_copy(context));
837 context2 = expr_extract_context(expr->args[2], context);
839 if (is_aff) {
840 isl_map *access;
841 isl_set *zero_set;
843 access = isl_map_copy(expr->args[0]->acc.access);
844 access = isl_map_fix_si(access, isl_dim_out, 0, 0);
845 zero_set = isl_map_params(access);
846 context1 = isl_set_subtract(context1,
847 isl_set_copy(zero_set));
848 context2 = isl_set_intersect(context2, zero_set);
851 context = isl_set_union(context1, context2);
852 context = isl_set_coalesce(context);
854 return context;
857 for (i = 0; i < expr->n_arg; ++i)
858 context = expr_extract_context(expr->args[i], context);
860 if (expr->type == pet_expr_access)
861 context = access_extract_context(expr->acc.access, context);
863 return context;
864 error:
865 isl_set_free(context);
866 return NULL;
869 /* Update "context" with respect to the valid parameter values for "stmt".
871 static __isl_give isl_set *stmt_extract_context(struct pet_stmt *stmt,
872 __isl_take isl_set *context)
874 int i;
876 for (i = 0; i < stmt->n_arg; ++i)
877 context = expr_extract_context(stmt->args[i], context);
879 context = expr_extract_context(stmt->body, context);
881 return context;
884 /* Construct a pet_scop that contains the given pet_stmt.
886 struct pet_scop *pet_scop_from_pet_stmt(isl_ctx *ctx, struct pet_stmt *stmt)
888 struct pet_scop *scop;
890 if (!stmt)
891 return NULL;
893 scop = scop_alloc(ctx, 1);
894 if (!scop)
895 goto error;
897 scop->context = stmt_extract_context(stmt, scop->context);
898 if (!scop->context)
899 goto error;
901 scop->stmts[0] = stmt;
903 return scop;
904 error:
905 pet_stmt_free(stmt);
906 pet_scop_free(scop);
907 return NULL;
910 /* Does "set" represent an element of an unnamed space, i.e.,
911 * does it represent an affine expression?
913 static int set_is_affine(__isl_keep isl_set *set)
915 int has_id;
917 has_id = isl_set_has_tuple_id(set);
918 if (has_id < 0)
919 return -1;
921 return !has_id;
924 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
925 * ext may be equal to either ext1 or ext2.
927 * The two skips that need to be combined are assumed to be affine expressions.
929 * We need to skip in ext if we need to skip in either ext1 or ext2.
930 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
932 static struct pet_scop_ext *combine_skips(struct pet_scop_ext *ext,
933 struct pet_scop_ext *ext1, struct pet_scop_ext *ext2,
934 enum pet_skip type)
936 isl_set *set, *skip1, *skip2;
938 if (!ext)
939 return NULL;
940 if (!ext1->skip[type] && !ext2->skip[type])
941 return ext;
942 if (!ext1->skip[type]) {
943 if (ext == ext2)
944 return ext;
945 ext->skip[type] = ext2->skip[type];
946 ext2->skip[type] = NULL;
947 return ext;
949 if (!ext2->skip[type]) {
950 if (ext == ext1)
951 return ext;
952 ext->skip[type] = ext1->skip[type];
953 ext1->skip[type] = NULL;
954 return ext;
957 if (!set_is_affine(ext1->skip[type]) ||
958 !set_is_affine(ext2->skip[type]))
959 isl_die(isl_set_get_ctx(ext1->skip[type]), isl_error_internal,
960 "can only combine affine skips",
961 return pet_scop_free(&ext->scop));
963 skip1 = isl_set_copy(ext1->skip[type]);
964 skip2 = isl_set_copy(ext2->skip[type]);
965 set = isl_set_intersect(
966 isl_set_fix_si(isl_set_copy(skip1), isl_dim_set, 0, 0),
967 isl_set_fix_si(isl_set_copy(skip2), isl_dim_set, 0, 0));
968 set = isl_set_union(set, isl_set_fix_si(skip1, isl_dim_set, 0, 1));
969 set = isl_set_union(set, isl_set_fix_si(skip2, isl_dim_set, 0, 1));
970 set = isl_set_coalesce(set);
971 isl_set_free(ext1->skip[type]);
972 ext1->skip[type] = NULL;
973 isl_set_free(ext2->skip[type]);
974 ext2->skip[type] = NULL;
975 ext->skip[type] = set;
976 if (!ext->skip[type])
977 return pet_scop_free(&ext->scop);
979 return ext;
982 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
983 * where type takes on the values pet_skip_now and pet_skip_later.
984 * scop may be equal to either scop1 or scop2.
986 static struct pet_scop *scop_combine_skips(struct pet_scop *scop,
987 struct pet_scop *scop1, struct pet_scop *scop2)
989 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
990 struct pet_scop_ext *ext1 = (struct pet_scop_ext *) scop1;
991 struct pet_scop_ext *ext2 = (struct pet_scop_ext *) scop2;
993 ext = combine_skips(ext, ext1, ext2, pet_skip_now);
994 ext = combine_skips(ext, ext1, ext2, pet_skip_later);
995 return &ext->scop;
998 /* Update scop->start and scop->end to include the region from "start"
999 * to "end". In particular, if scop->end == 0, then "scop" does not
1000 * have any offset information yet and we simply take the information
1001 * from "start" and "end". Otherwise, we update the fields if the
1002 * region from "start" to "end" is not already included.
1004 struct pet_scop *pet_scop_update_start_end(struct pet_scop *scop,
1005 unsigned start, unsigned end)
1007 if (!scop)
1008 return NULL;
1009 if (scop->end == 0) {
1010 scop->start = start;
1011 scop->end = end;
1012 } else {
1013 if (start < scop->start)
1014 scop->start = start;
1015 if (end > scop->end)
1016 scop->end = end;
1019 return scop;
1022 /* Does "implication" appear in the list of implications of "scop"?
1024 static int is_known_implication(struct pet_scop *scop,
1025 struct pet_implication *implication)
1027 int i;
1029 for (i = 0; i < scop->n_implication; ++i) {
1030 struct pet_implication *pi = scop->implications[i];
1031 int equal;
1033 if (pi->satisfied != implication->satisfied)
1034 continue;
1035 equal = isl_map_is_equal(pi->extension, implication->extension);
1036 if (equal < 0)
1037 return -1;
1038 if (equal)
1039 return 1;
1042 return 0;
1045 /* Store the concatenation of the impliciations of "scop1" and "scop2"
1046 * in "scop", removing duplicates (i.e., implications in "scop2" that
1047 * already appear in "scop1").
1049 static struct pet_scop *scop_collect_implications(isl_ctx *ctx,
1050 struct pet_scop *scop, struct pet_scop *scop1, struct pet_scop *scop2)
1052 int i, j;
1054 if (!scop)
1055 return NULL;
1057 if (scop2->n_implication == 0) {
1058 scop->n_implication = scop1->n_implication;
1059 scop->implications = scop1->implications;
1060 scop1->n_implication = 0;
1061 scop1->implications = NULL;
1062 return scop;
1065 if (scop1->n_implication == 0) {
1066 scop->n_implication = scop2->n_implication;
1067 scop->implications = scop2->implications;
1068 scop2->n_implication = 0;
1069 scop2->implications = NULL;
1070 return scop;
1073 scop->implications = isl_calloc_array(ctx, struct pet_implication *,
1074 scop1->n_implication + scop2->n_implication);
1075 if (!scop->implications)
1076 return pet_scop_free(scop);
1078 for (i = 0; i < scop1->n_implication; ++i) {
1079 scop->implications[i] = scop1->implications[i];
1080 scop1->implications[i] = NULL;
1083 scop->n_implication = scop1->n_implication;
1084 j = scop1->n_implication;
1085 for (i = 0; i < scop2->n_implication; ++i) {
1086 int known;
1088 known = is_known_implication(scop, scop2->implications[i]);
1089 if (known < 0)
1090 return pet_scop_free(scop);
1091 if (known)
1092 continue;
1093 scop->implications[j++] = scop2->implications[i];
1094 scop2->implications[i] = NULL;
1096 scop->n_implication = j;
1098 return scop;
1101 /* Combine the offset information of "scop1" and "scop2" into "scop".
1103 static struct pet_scop *scop_combine_start_end(struct pet_scop *scop,
1104 struct pet_scop *scop1, struct pet_scop *scop2)
1106 if (scop1->end)
1107 scop = pet_scop_update_start_end(scop,
1108 scop1->start, scop1->end);
1109 if (scop2->end)
1110 scop = pet_scop_update_start_end(scop,
1111 scop2->start, scop2->end);
1112 return scop;
1115 /* Construct a pet_scop that contains the offset information,
1116 * arrays, statements and skip information in "scop1" and "scop2".
1118 static struct pet_scop *pet_scop_add(isl_ctx *ctx, struct pet_scop *scop1,
1119 struct pet_scop *scop2)
1121 int i;
1122 struct pet_scop *scop = NULL;
1124 if (!scop1 || !scop2)
1125 goto error;
1127 if (scop1->n_stmt == 0) {
1128 scop2 = scop_combine_skips(scop2, scop1, scop2);
1129 pet_scop_free(scop1);
1130 return scop2;
1133 if (scop2->n_stmt == 0) {
1134 scop1 = scop_combine_skips(scop1, scop1, scop2);
1135 pet_scop_free(scop2);
1136 return scop1;
1139 scop = scop_alloc(ctx, scop1->n_stmt + scop2->n_stmt);
1140 if (!scop)
1141 goto error;
1143 scop->arrays = isl_calloc_array(ctx, struct pet_array *,
1144 scop1->n_array + scop2->n_array);
1145 if (!scop->arrays)
1146 goto error;
1147 scop->n_array = scop1->n_array + scop2->n_array;
1149 for (i = 0; i < scop1->n_stmt; ++i) {
1150 scop->stmts[i] = scop1->stmts[i];
1151 scop1->stmts[i] = NULL;
1154 for (i = 0; i < scop2->n_stmt; ++i) {
1155 scop->stmts[scop1->n_stmt + i] = scop2->stmts[i];
1156 scop2->stmts[i] = NULL;
1159 for (i = 0; i < scop1->n_array; ++i) {
1160 scop->arrays[i] = scop1->arrays[i];
1161 scop1->arrays[i] = NULL;
1164 for (i = 0; i < scop2->n_array; ++i) {
1165 scop->arrays[scop1->n_array + i] = scop2->arrays[i];
1166 scop2->arrays[i] = NULL;
1169 scop = scop_collect_implications(ctx, scop, scop1, scop2);
1170 scop = pet_scop_restrict_context(scop, isl_set_copy(scop1->context));
1171 scop = pet_scop_restrict_context(scop, isl_set_copy(scop2->context));
1172 scop = scop_combine_skips(scop, scop1, scop2);
1173 scop = scop_combine_start_end(scop, scop1, scop2);
1175 pet_scop_free(scop1);
1176 pet_scop_free(scop2);
1177 return scop;
1178 error:
1179 pet_scop_free(scop1);
1180 pet_scop_free(scop2);
1181 pet_scop_free(scop);
1182 return NULL;
1185 /* Apply the skip condition "skip" to "scop".
1186 * That is, make sure "scop" is not executed when the condition holds.
1188 * If "skip" is an affine expression, we add the conditions under
1189 * which the expression is zero to the iteration domains.
1190 * Otherwise, we add a filter on the variable attaining the value zero.
1192 static struct pet_scop *restrict_skip(struct pet_scop *scop,
1193 __isl_take isl_set *skip)
1195 isl_map *skip_map;
1196 int is_aff;
1198 if (!scop || !skip)
1199 goto error;
1201 is_aff = set_is_affine(skip);
1202 if (is_aff < 0)
1203 goto error;
1205 if (!is_aff)
1206 return pet_scop_filter(scop, isl_map_from_range(skip), 0);
1208 skip = isl_set_fix_si(skip, isl_dim_set, 0, 0);
1209 scop = pet_scop_restrict(scop, isl_set_params(skip));
1211 return scop;
1212 error:
1213 isl_set_free(skip);
1214 return pet_scop_free(scop);
1217 /* Construct a pet_scop that contains the arrays, statements and
1218 * skip information in "scop1" and "scop2", where the two scops
1219 * are executed "in sequence". That is, breaks and continues
1220 * in scop1 have an effect on scop2.
1222 struct pet_scop *pet_scop_add_seq(isl_ctx *ctx, struct pet_scop *scop1,
1223 struct pet_scop *scop2)
1225 if (scop1 && pet_scop_has_skip(scop1, pet_skip_now))
1226 scop2 = restrict_skip(scop2,
1227 pet_scop_get_skip(scop1, pet_skip_now));
1228 return pet_scop_add(ctx, scop1, scop2);
1231 /* Construct a pet_scop that contains the arrays, statements and
1232 * skip information in "scop1" and "scop2", where the two scops
1233 * are executed "in parallel". That is, any break or continue
1234 * in scop1 has no effect on scop2.
1236 struct pet_scop *pet_scop_add_par(isl_ctx *ctx, struct pet_scop *scop1,
1237 struct pet_scop *scop2)
1239 return pet_scop_add(ctx, scop1, scop2);
1242 void *pet_implication_free(struct pet_implication *implication)
1244 int i;
1246 if (!implication)
1247 return NULL;
1249 isl_map_free(implication->extension);
1251 free(implication);
1252 return NULL;
1255 void *pet_scop_free(struct pet_scop *scop)
1257 int i;
1258 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1260 if (!scop)
1261 return NULL;
1262 isl_set_free(scop->context);
1263 isl_set_free(scop->context_value);
1264 if (scop->arrays)
1265 for (i = 0; i < scop->n_array; ++i)
1266 pet_array_free(scop->arrays[i]);
1267 free(scop->arrays);
1268 if (scop->stmts)
1269 for (i = 0; i < scop->n_stmt; ++i)
1270 pet_stmt_free(scop->stmts[i]);
1271 free(scop->stmts);
1272 if (scop->implications)
1273 for (i = 0; i < scop->n_implication; ++i)
1274 pet_implication_free(scop->implications[i]);
1275 free(scop->implications);
1276 isl_set_free(ext->skip[pet_skip_now]);
1277 isl_set_free(ext->skip[pet_skip_later]);
1278 free(scop);
1279 return NULL;
1282 void pet_implication_dump(struct pet_implication *implication)
1284 if (!implication)
1285 return;
1287 fprintf(stderr, "%d\n", implication->satisfied);
1288 isl_map_dump(implication->extension);
1291 void pet_scop_dump(struct pet_scop *scop)
1293 int i;
1294 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1296 if (!scop)
1297 return;
1299 isl_set_dump(scop->context);
1300 isl_set_dump(scop->context_value);
1301 for (i = 0; i < scop->n_array; ++i)
1302 pet_array_dump(scop->arrays[i]);
1303 for (i = 0; i < scop->n_stmt; ++i)
1304 pet_stmt_dump(scop->stmts[i]);
1305 for (i = 0; i < scop->n_implication; ++i)
1306 pet_implication_dump(scop->implications[i]);
1308 if (ext->skip[0]) {
1309 fprintf(stderr, "skip\n");
1310 isl_set_dump(ext->skip[0]);
1311 isl_set_dump(ext->skip[1]);
1315 /* Return 1 if the two pet_arrays are equivalent.
1317 * We don't compare element_size as this may be target dependent.
1319 int pet_array_is_equal(struct pet_array *array1, struct pet_array *array2)
1321 if (!array1 || !array2)
1322 return 0;
1324 if (!isl_set_is_equal(array1->context, array2->context))
1325 return 0;
1326 if (!isl_set_is_equal(array1->extent, array2->extent))
1327 return 0;
1328 if (!!array1->value_bounds != !!array2->value_bounds)
1329 return 0;
1330 if (array1->value_bounds &&
1331 !isl_set_is_equal(array1->value_bounds, array2->value_bounds))
1332 return 0;
1333 if (strcmp(array1->element_type, array2->element_type))
1334 return 0;
1335 if (array1->live_out != array2->live_out)
1336 return 0;
1337 if (array1->uniquely_defined != array2->uniquely_defined)
1338 return 0;
1339 if (array1->declared != array2->declared)
1340 return 0;
1341 if (array1->exposed != array2->exposed)
1342 return 0;
1344 return 1;
1347 /* Return 1 if the two pet_stmts are equivalent.
1349 int pet_stmt_is_equal(struct pet_stmt *stmt1, struct pet_stmt *stmt2)
1351 int i;
1353 if (!stmt1 || !stmt2)
1354 return 0;
1356 if (stmt1->line != stmt2->line)
1357 return 0;
1358 if (!isl_set_is_equal(stmt1->domain, stmt2->domain))
1359 return 0;
1360 if (!isl_map_is_equal(stmt1->schedule, stmt2->schedule))
1361 return 0;
1362 if (!pet_expr_is_equal(stmt1->body, stmt2->body))
1363 return 0;
1364 if (stmt1->n_arg != stmt2->n_arg)
1365 return 0;
1366 for (i = 0; i < stmt1->n_arg; ++i) {
1367 if (!pet_expr_is_equal(stmt1->args[i], stmt2->args[i]))
1368 return 0;
1371 return 1;
1374 /* Return 1 if the two pet_implications are equivalent.
1376 int pet_implication_is_equal(struct pet_implication *implication1,
1377 struct pet_implication *implication2)
1379 if (!implication1 || !implication2)
1380 return 0;
1382 if (implication1->satisfied != implication2->satisfied)
1383 return 0;
1384 if (!isl_map_is_equal(implication1->extension, implication2->extension))
1385 return 0;
1387 return 1;
1390 /* Return 1 if the two pet_scops are equivalent.
1392 int pet_scop_is_equal(struct pet_scop *scop1, struct pet_scop *scop2)
1394 int i;
1396 if (!scop1 || !scop2)
1397 return 0;
1399 if (!isl_set_is_equal(scop1->context, scop2->context))
1400 return 0;
1401 if (!isl_set_is_equal(scop1->context_value, scop2->context_value))
1402 return 0;
1404 if (scop1->n_array != scop2->n_array)
1405 return 0;
1406 for (i = 0; i < scop1->n_array; ++i)
1407 if (!pet_array_is_equal(scop1->arrays[i], scop2->arrays[i]))
1408 return 0;
1410 if (scop1->n_stmt != scop2->n_stmt)
1411 return 0;
1412 for (i = 0; i < scop1->n_stmt; ++i)
1413 if (!pet_stmt_is_equal(scop1->stmts[i], scop2->stmts[i]))
1414 return 0;
1416 if (scop1->n_implication != scop2->n_implication)
1417 return 0;
1418 for (i = 0; i < scop1->n_implication; ++i)
1419 if (!pet_implication_is_equal(scop1->implications[i],
1420 scop2->implications[i]))
1421 return 0;
1423 return 1;
1426 /* Prefix the schedule of "stmt" with an extra dimension with constant
1427 * value "pos".
1429 struct pet_stmt *pet_stmt_prefix(struct pet_stmt *stmt, int pos)
1431 if (!stmt)
1432 return NULL;
1434 stmt->schedule = isl_map_insert_dims(stmt->schedule, isl_dim_out, 0, 1);
1435 stmt->schedule = isl_map_fix_si(stmt->schedule, isl_dim_out, 0, pos);
1436 if (!stmt->schedule)
1437 return pet_stmt_free(stmt);
1439 return stmt;
1442 /* Prefix the schedules of all statements in "scop" with an extra
1443 * dimension with constant value "pos".
1445 struct pet_scop *pet_scop_prefix(struct pet_scop *scop, int pos)
1447 int i;
1449 if (!scop)
1450 return NULL;
1452 for (i = 0; i < scop->n_stmt; ++i) {
1453 scop->stmts[i] = pet_stmt_prefix(scop->stmts[i], pos);
1454 if (!scop->stmts[i])
1455 return pet_scop_free(scop);
1458 return scop;
1461 /* Given a set with a parameter at "param_pos" that refers to the
1462 * iterator, "move" the iterator to the first set dimension.
1463 * That is, essentially equate the parameter to the first set dimension
1464 * and then project it out.
1466 * The first set dimension may however refer to a virtual iterator,
1467 * while the parameter refers to the "real" iterator.
1468 * We therefore need to take into account the affine expression "iv_map", which
1469 * expresses the real iterator in terms of the virtual iterator.
1470 * In particular, we equate the set dimension to the input of the map
1471 * and the parameter to the output of the map and then project out
1472 * everything we don't need anymore.
1474 static __isl_give isl_set *internalize_iv(__isl_take isl_set *set,
1475 int param_pos, __isl_take isl_aff *iv_map)
1477 isl_map *map, *map2;
1478 map = isl_map_from_domain(set);
1479 map = isl_map_add_dims(map, isl_dim_out, 1);
1480 map = isl_map_equate(map, isl_dim_in, 0, isl_dim_out, 0);
1481 map2 = isl_map_from_aff(iv_map);
1482 map2 = isl_map_align_params(map2, isl_map_get_space(map));
1483 map = isl_map_apply_range(map, map2);
1484 map = isl_map_equate(map, isl_dim_param, param_pos, isl_dim_out, 0);
1485 map = isl_map_project_out(map, isl_dim_param, param_pos, 1);
1486 return isl_map_domain(map);
1489 /* Data used in embed_access.
1490 * extend adds an iterator to the iteration domain
1491 * iv_map expresses the real iterator in terms of the virtual iterator
1492 * var_id represents the induction variable of the corresponding loop
1494 struct pet_embed_access {
1495 isl_map *extend;
1496 isl_aff *iv_map;
1497 isl_id *var_id;
1500 /* Given an access expression, embed the associated access relation
1501 * in an extra outer loop.
1503 * We first update the iteration domain to insert the extra dimension.
1505 * If the access refers to the induction variable, then it is
1506 * turned into an access to the set of integers with index (and value)
1507 * equal to the induction variable.
1509 * If the induction variable appears in the constraints (as a parameter),
1510 * then the parameter is equated to the newly introduced iteration
1511 * domain dimension and subsequently projected out.
1513 * Similarly, if the accessed array is a virtual array (with user
1514 * pointer equal to NULL), as created by create_test_access,
1515 * then it is extended along with the domain of the access.
1517 static struct pet_expr *embed_access(struct pet_expr *expr, void *user)
1519 struct pet_embed_access *data = user;
1520 isl_map *access;
1521 isl_id *array_id = NULL;
1522 int pos;
1524 expr = update_domain(expr, data->extend);
1525 if (!expr)
1526 return NULL;
1528 access = expr->acc.access;
1530 if (isl_map_has_tuple_id(access, isl_dim_out))
1531 array_id = isl_map_get_tuple_id(access, isl_dim_out);
1532 if (array_id == data->var_id ||
1533 (array_id && !isl_id_get_user(array_id))) {
1534 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
1535 access = isl_map_equate(access,
1536 isl_dim_in, 0, isl_dim_out, 0);
1537 if (array_id == data->var_id)
1538 access = isl_map_apply_range(access,
1539 isl_map_from_aff(isl_aff_copy(data->iv_map)));
1540 else
1541 access = isl_map_set_tuple_id(access, isl_dim_out,
1542 isl_id_copy(array_id));
1544 isl_id_free(array_id);
1546 pos = isl_map_find_dim_by_id(access, isl_dim_param, data->var_id);
1547 if (pos >= 0) {
1548 isl_set *set = isl_map_wrap(access);
1549 set = internalize_iv(set, pos, isl_aff_copy(data->iv_map));
1550 access = isl_set_unwrap(set);
1552 expr->acc.access = isl_map_set_dim_id(access, isl_dim_in, 0,
1553 isl_id_copy(data->var_id));
1554 if (!expr->acc.access)
1555 return pet_expr_free(expr);
1557 return expr;
1560 /* Embed all access subexpressions of "expr" in an extra loop.
1561 * "extend" inserts an outer loop iterator in the iteration domains.
1562 * "iv_map" expresses the real iterator in terms of the virtual iterator
1563 * "var_id" represents the induction variable.
1565 static struct pet_expr *expr_embed(struct pet_expr *expr,
1566 __isl_take isl_map *extend, __isl_take isl_aff *iv_map,
1567 __isl_keep isl_id *var_id)
1569 struct pet_embed_access data =
1570 { .extend = extend, .iv_map = iv_map, .var_id = var_id };
1572 expr = pet_expr_map_access(expr, &embed_access, &data);
1573 isl_aff_free(iv_map);
1574 isl_map_free(extend);
1575 return expr;
1578 /* Embed the given pet_stmt in an extra outer loop with iteration domain
1579 * "dom" and schedule "sched". "var_id" represents the induction variable
1580 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
1581 * That is, it expresses the iterator that some of the parameters in "stmt"
1582 * may refer to in terms of the iterator used in "dom" and
1583 * the domain of "sched".
1585 * The iteration domain and schedule of the statement are updated
1586 * according to the iteration domain and schedule of the new loop.
1587 * If stmt->domain is a wrapped map, then the iteration domain
1588 * is the domain of this map, so we need to be careful to adjust
1589 * this domain.
1591 * If the induction variable appears in the constraints (as a parameter)
1592 * of the current iteration domain or the schedule of the statement,
1593 * then the parameter is equated to the newly introduced iteration
1594 * domain dimension and subsequently projected out.
1596 * Finally, all access relations are updated based on the extra loop.
1598 static struct pet_stmt *pet_stmt_embed(struct pet_stmt *stmt,
1599 __isl_take isl_set *dom, __isl_take isl_map *sched,
1600 __isl_take isl_aff *iv_map, __isl_take isl_id *var_id)
1602 int i;
1603 int pos;
1604 isl_id *stmt_id;
1605 isl_space *dim;
1606 isl_map *extend;
1608 if (!stmt)
1609 goto error;
1611 if (isl_set_is_wrapping(stmt->domain)) {
1612 isl_map *map;
1613 isl_map *ext;
1614 isl_space *ran_dim;
1616 map = isl_set_unwrap(stmt->domain);
1617 stmt_id = isl_map_get_tuple_id(map, isl_dim_in);
1618 ran_dim = isl_space_range(isl_map_get_space(map));
1619 ext = isl_map_from_domain_and_range(isl_set_copy(dom),
1620 isl_set_universe(ran_dim));
1621 map = isl_map_flat_domain_product(ext, map);
1622 map = isl_map_set_tuple_id(map, isl_dim_in,
1623 isl_id_copy(stmt_id));
1624 dim = isl_space_domain(isl_map_get_space(map));
1625 stmt->domain = isl_map_wrap(map);
1626 } else {
1627 stmt_id = isl_set_get_tuple_id(stmt->domain);
1628 stmt->domain = isl_set_flat_product(isl_set_copy(dom),
1629 stmt->domain);
1630 stmt->domain = isl_set_set_tuple_id(stmt->domain,
1631 isl_id_copy(stmt_id));
1632 dim = isl_set_get_space(stmt->domain);
1635 pos = isl_set_find_dim_by_id(stmt->domain, isl_dim_param, var_id);
1636 if (pos >= 0)
1637 stmt->domain = internalize_iv(stmt->domain, pos,
1638 isl_aff_copy(iv_map));
1640 stmt->schedule = isl_map_flat_product(sched, stmt->schedule);
1641 stmt->schedule = isl_map_set_tuple_id(stmt->schedule,
1642 isl_dim_in, stmt_id);
1644 pos = isl_map_find_dim_by_id(stmt->schedule, isl_dim_param, var_id);
1645 if (pos >= 0) {
1646 isl_set *set = isl_map_wrap(stmt->schedule);
1647 set = internalize_iv(set, pos, isl_aff_copy(iv_map));
1648 stmt->schedule = isl_set_unwrap(set);
1651 dim = isl_space_map_from_set(dim);
1652 extend = isl_map_identity(dim);
1653 extend = isl_map_remove_dims(extend, isl_dim_in, 0, 1);
1654 extend = isl_map_set_tuple_id(extend, isl_dim_in,
1655 isl_map_get_tuple_id(extend, isl_dim_out));
1656 for (i = 0; i < stmt->n_arg; ++i)
1657 stmt->args[i] = expr_embed(stmt->args[i], isl_map_copy(extend),
1658 isl_aff_copy(iv_map), var_id);
1659 stmt->body = expr_embed(stmt->body, extend, iv_map, var_id);
1661 isl_set_free(dom);
1662 isl_id_free(var_id);
1664 for (i = 0; i < stmt->n_arg; ++i)
1665 if (!stmt->args[i])
1666 return pet_stmt_free(stmt);
1667 if (!stmt->domain || !stmt->schedule || !stmt->body)
1668 return pet_stmt_free(stmt);
1669 return stmt;
1670 error:
1671 isl_set_free(dom);
1672 isl_map_free(sched);
1673 isl_aff_free(iv_map);
1674 isl_id_free(var_id);
1675 return NULL;
1678 /* Embed the given pet_array in an extra outer loop with iteration domain
1679 * "dom".
1680 * This embedding only has an effect on virtual arrays (those with
1681 * user pointer equal to NULL), which need to be extended along with
1682 * the iteration domain.
1684 static struct pet_array *pet_array_embed(struct pet_array *array,
1685 __isl_take isl_set *dom)
1687 isl_id *array_id = NULL;
1689 if (!array)
1690 goto error;
1692 if (isl_set_has_tuple_id(array->extent))
1693 array_id = isl_set_get_tuple_id(array->extent);
1695 if (array_id && !isl_id_get_user(array_id)) {
1696 array->extent = isl_set_flat_product(dom, array->extent);
1697 array->extent = isl_set_set_tuple_id(array->extent, array_id);
1698 if (!array->extent)
1699 return pet_array_free(array);
1700 } else {
1701 isl_set_free(dom);
1702 isl_id_free(array_id);
1705 return array;
1706 error:
1707 isl_set_free(dom);
1708 return NULL;
1711 /* Project out all unnamed parameters from "set" and return the result.
1713 static __isl_give isl_set *set_project_out_unnamed_params(
1714 __isl_take isl_set *set)
1716 int i, n;
1718 n = isl_set_dim(set, isl_dim_param);
1719 for (i = n - 1; i >= 0; --i) {
1720 if (isl_set_has_dim_name(set, isl_dim_param, i))
1721 continue;
1722 set = isl_set_project_out(set, isl_dim_param, i, 1);
1725 return set;
1728 /* Update the context with respect to an embedding into a loop
1729 * with iteration domain "dom" and induction variable "id".
1730 * "iv_map" expresses the real iterator (parameter "id") in terms
1731 * of a possibly virtual iterator (used in "dom").
1733 * If the current context is independent of "id", we don't need
1734 * to do anything.
1735 * Otherwise, a parameter value is invalid for the embedding if
1736 * any of the corresponding iterator values is invalid.
1737 * That is, a parameter value is valid only if all the corresponding
1738 * iterator values are valid.
1739 * We therefore compute the set of parameters
1741 * forall i in dom : valid (i)
1743 * or
1745 * not exists i in dom : not valid(i)
1747 * i.e.,
1749 * not exists i in dom \ valid(i)
1751 * Before we subtract valid(i) from dom, we first need to substitute
1752 * the real iterator for the virtual iterator.
1754 * If there are any unnamed parameters in "dom", then we consider
1755 * a parameter value to be valid if it is valid for any value of those
1756 * unnamed parameters. They are therefore projected out at the end.
1758 static __isl_give isl_set *context_embed(__isl_take isl_set *context,
1759 __isl_keep isl_set *dom, __isl_keep isl_aff *iv_map,
1760 __isl_keep isl_id *id)
1762 int pos;
1763 isl_multi_aff *ma;
1765 pos = isl_set_find_dim_by_id(context, isl_dim_param, id);
1766 if (pos < 0)
1767 return context;
1769 context = isl_set_from_params(context);
1770 context = isl_set_add_dims(context, isl_dim_set, 1);
1771 context = isl_set_equate(context, isl_dim_param, pos, isl_dim_set, 0);
1772 context = isl_set_project_out(context, isl_dim_param, pos, 1);
1773 ma = isl_multi_aff_from_aff(isl_aff_copy(iv_map));
1774 context = isl_set_preimage_multi_aff(context, ma);
1775 context = isl_set_subtract(isl_set_copy(dom), context);
1776 context = isl_set_params(context);
1777 context = isl_set_complement(context);
1778 context = set_project_out_unnamed_params(context);
1779 return context;
1782 /* Update the implication with respect to an embedding into a loop
1783 * with iteration domain "dom".
1785 * Since embed_access extends virtual arrays along with the domain
1786 * of the access, we need to do the same with domain and range
1787 * of the implication. Since the original implication is only valid
1788 * within a given iteration of the loop, the extended implication
1789 * maps the extra array dimension corresponding to the extra loop
1790 * to itself.
1792 static struct pet_implication *pet_implication_embed(
1793 struct pet_implication *implication, __isl_take isl_set *dom)
1795 isl_id *id;
1796 isl_map *map;
1798 if (!implication)
1799 goto error;
1801 map = isl_set_identity(dom);
1802 id = isl_map_get_tuple_id(implication->extension, isl_dim_in);
1803 map = isl_map_flat_product(map, implication->extension);
1804 map = isl_map_set_tuple_id(map, isl_dim_in, isl_id_copy(id));
1805 map = isl_map_set_tuple_id(map, isl_dim_out, id);
1806 implication->extension = map;
1807 if (!implication->extension)
1808 return pet_implication_free(implication);
1810 return implication;
1811 error:
1812 isl_set_free(dom);
1813 return NULL;
1816 /* Embed all statements and arrays in "scop" in an extra outer loop
1817 * with iteration domain "dom" and schedule "sched".
1818 * "id" represents the induction variable of the loop.
1819 * "iv_map" maps a possibly virtual iterator to the real iterator.
1820 * That is, it expresses the iterator that some of the parameters in "scop"
1821 * may refer to in terms of the iterator used in "dom" and
1822 * the domain of "sched".
1824 * Any skip conditions within the loop have no effect outside of the loop.
1825 * The caller is responsible for making sure skip[pet_skip_later] has been
1826 * taken into account.
1828 struct pet_scop *pet_scop_embed(struct pet_scop *scop, __isl_take isl_set *dom,
1829 __isl_take isl_map *sched, __isl_take isl_aff *iv_map,
1830 __isl_take isl_id *id)
1832 int i;
1834 if (!scop)
1835 goto error;
1837 pet_scop_reset_skip(scop, pet_skip_now);
1838 pet_scop_reset_skip(scop, pet_skip_later);
1840 scop->context = context_embed(scop->context, dom, iv_map, id);
1841 if (!scop->context)
1842 goto error;
1844 for (i = 0; i < scop->n_stmt; ++i) {
1845 scop->stmts[i] = pet_stmt_embed(scop->stmts[i],
1846 isl_set_copy(dom), isl_map_copy(sched),
1847 isl_aff_copy(iv_map), isl_id_copy(id));
1848 if (!scop->stmts[i])
1849 goto error;
1852 for (i = 0; i < scop->n_array; ++i) {
1853 scop->arrays[i] = pet_array_embed(scop->arrays[i],
1854 isl_set_copy(dom));
1855 if (!scop->arrays[i])
1856 goto error;
1859 for (i = 0; i < scop->n_implication; ++i) {
1860 scop->implications[i] =
1861 pet_implication_embed(scop->implications[i],
1862 isl_set_copy(dom));
1863 if (!scop->implications[i])
1864 goto error;
1867 isl_set_free(dom);
1868 isl_map_free(sched);
1869 isl_aff_free(iv_map);
1870 isl_id_free(id);
1871 return scop;
1872 error:
1873 isl_set_free(dom);
1874 isl_map_free(sched);
1875 isl_aff_free(iv_map);
1876 isl_id_free(id);
1877 return pet_scop_free(scop);
1880 /* Add extra conditions on the parameters to iteration domain of "stmt".
1882 static struct pet_stmt *stmt_restrict(struct pet_stmt *stmt,
1883 __isl_take isl_set *cond)
1885 if (!stmt)
1886 goto error;
1888 stmt->domain = isl_set_intersect_params(stmt->domain, cond);
1890 return stmt;
1891 error:
1892 isl_set_free(cond);
1893 return pet_stmt_free(stmt);
1896 /* Add extra conditions to scop->skip[type].
1898 * The new skip condition only holds if it held before
1899 * and the condition is true. It does not hold if it did not hold
1900 * before or the condition is false.
1902 * The skip condition is assumed to be an affine expression.
1904 static struct pet_scop *pet_scop_restrict_skip(struct pet_scop *scop,
1905 enum pet_skip type, __isl_keep isl_set *cond)
1907 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1908 isl_set *skip;
1909 isl_set *set;
1911 if (!scop)
1912 return NULL;
1913 if (!ext->skip[type])
1914 return scop;
1916 if (!set_is_affine(ext->skip[type]))
1917 isl_die(isl_set_get_ctx(ext->skip[type]), isl_error_internal,
1918 "can only resrict affine skips",
1919 return pet_scop_free(scop));
1921 skip = ext->skip[type];
1922 skip = isl_set_intersect_params(skip, isl_set_copy(cond));
1923 set = isl_set_from_params(isl_set_copy(cond));
1924 set = isl_set_complement(set);
1925 set = isl_set_add_dims(set, isl_dim_set, 1);
1926 set = isl_set_fix_si(set, isl_dim_set, 0, 0);
1927 skip = isl_set_union(skip, set);
1928 ext->skip[type] = skip;
1929 if (!ext->skip[type])
1930 return pet_scop_free(scop);
1932 return scop;
1935 /* Add extra conditions on the parameters to all iteration domains
1936 * and skip conditions.
1938 * A parameter value is valid for the result if it was valid
1939 * for the original scop and satisfies "cond" or if it does
1940 * not satisfy "cond" as in this case the scop is not executed
1941 * and the original constraints on the parameters are irrelevant.
1943 struct pet_scop *pet_scop_restrict(struct pet_scop *scop,
1944 __isl_take isl_set *cond)
1946 int i;
1948 scop = pet_scop_restrict_skip(scop, pet_skip_now, cond);
1949 scop = pet_scop_restrict_skip(scop, pet_skip_later, cond);
1951 if (!scop)
1952 goto error;
1954 scop->context = isl_set_intersect(scop->context, isl_set_copy(cond));
1955 scop->context = isl_set_union(scop->context,
1956 isl_set_complement(isl_set_copy(cond)));
1957 scop->context = isl_set_coalesce(scop->context);
1958 scop->context = set_project_out_unnamed_params(scop->context);
1959 if (!scop->context)
1960 goto error;
1962 for (i = 0; i < scop->n_stmt; ++i) {
1963 scop->stmts[i] = stmt_restrict(scop->stmts[i],
1964 isl_set_copy(cond));
1965 if (!scop->stmts[i])
1966 goto error;
1969 isl_set_free(cond);
1970 return scop;
1971 error:
1972 isl_set_free(cond);
1973 return pet_scop_free(scop);
1976 /* Construct a map that inserts a filter value with name "id" and value
1977 * "satisfied" in the list of filter values embedded in the set space "space".
1979 * If "space" does not contain any filter values yet, we first create
1980 * a map that inserts 0 filter values, i.e.,
1982 * space -> [space -> []]
1984 * We can now assume that space is of the form [dom -> [filters]]
1985 * We construct an identity mapping on dom and a mapping on filters
1986 * that inserts the new filter
1988 * dom -> dom
1989 * [filters] -> [satisfied, filters]
1991 * and then compute the cross product
1993 * [dom -> [filters]] -> [dom -> [satisfied, filters]]
1995 static __isl_give isl_map *insert_filter_map(__isl_take isl_space *space,
1996 __isl_take isl_id *id, int satisfied)
1998 isl_space *space2;
1999 isl_map *map, *map_dom, *map_ran;
2000 isl_set *dom;
2002 if (isl_space_is_wrapping(space)) {
2003 space2 = isl_space_map_from_set(isl_space_copy(space));
2004 map = isl_map_identity(space2);
2005 space = isl_space_unwrap(space);
2006 } else {
2007 space = isl_space_from_domain(space);
2008 map = isl_map_universe(isl_space_copy(space));
2009 map = isl_map_reverse(isl_map_domain_map(map));
2012 space2 = isl_space_domain(isl_space_copy(space));
2013 map_dom = isl_map_identity(isl_space_map_from_set(space2));
2014 space = isl_space_range(space);
2015 map_ran = isl_map_identity(isl_space_map_from_set(space));
2016 map_ran = isl_map_insert_dims(map_ran, isl_dim_out, 0, 1);
2017 map_ran = isl_map_set_dim_id(map_ran, isl_dim_out, 0, id);
2018 map_ran = isl_map_fix_si(map_ran, isl_dim_out, 0, satisfied);
2020 map = isl_map_apply_range(map, isl_map_product(map_dom, map_ran));
2022 return map;
2025 /* Insert an argument expression corresponding to "test" in front
2026 * of the list of arguments described by *n_arg and *args.
2028 static int args_insert_access(unsigned *n_arg, struct pet_expr ***args,
2029 __isl_keep isl_map *test)
2031 int i;
2032 isl_ctx *ctx = isl_map_get_ctx(test);
2034 if (!test)
2035 return -1;
2037 if (!*args) {
2038 *args = isl_calloc_array(ctx, struct pet_expr *, 1);
2039 if (!*args)
2040 return -1;
2041 } else {
2042 struct pet_expr **ext;
2043 ext = isl_calloc_array(ctx, struct pet_expr *, 1 + *n_arg);
2044 if (!ext)
2045 return -1;
2046 for (i = 0; i < *n_arg; ++i)
2047 ext[1 + i] = (*args)[i];
2048 free(*args);
2049 *args = ext;
2051 (*n_arg)++;
2052 (*args)[0] = pet_expr_from_access(isl_map_copy(test));
2053 if (!(*args)[0])
2054 return -1;
2056 return 0;
2059 /* Make the expression "expr" depend on the value of "test"
2060 * being equal to "satisfied".
2062 * If "test" is an affine expression, we simply add the conditions
2063 * on the expression have the value "satisfied" to all access relations.
2065 * Otherwise, we add a filter to "expr" (which is then assumed to be
2066 * an access expression) corresponding to "test" being equal to "satisfied".
2068 struct pet_expr *pet_expr_filter(struct pet_expr *expr,
2069 __isl_take isl_map *test, int satisfied)
2071 isl_id *id;
2072 isl_ctx *ctx;
2073 isl_space *space;
2074 isl_map *map;
2076 if (!expr || !test)
2077 goto error;
2079 if (!isl_map_has_tuple_id(test, isl_dim_out)) {
2080 test = isl_map_fix_si(test, isl_dim_out, 0, satisfied);
2081 return pet_expr_restrict(expr, isl_map_params(test));
2084 ctx = isl_map_get_ctx(test);
2085 if (expr->type != pet_expr_access)
2086 isl_die(ctx, isl_error_invalid,
2087 "can only filter access expressions", goto error);
2089 space = isl_space_domain(isl_map_get_space(expr->acc.access));
2090 id = isl_map_get_tuple_id(test, isl_dim_out);
2091 map = insert_filter_map(space, id, satisfied);
2093 expr->acc.access = isl_map_apply_domain(expr->acc.access, map);
2094 if (!expr->acc.access)
2095 goto error;
2097 if (args_insert_access(&expr->n_arg, &expr->args, test) < 0)
2098 goto error;
2100 isl_map_free(test);
2101 return expr;
2102 error:
2103 isl_map_free(test);
2104 return pet_expr_free(expr);
2107 /* Look through the applications in "scop" for any that can be
2108 * applied to the filter expressed by "map" and "satisified".
2109 * If there is any, then apply it to "map" and return the result.
2110 * Otherwise, return "map".
2111 * "id" is the identifier of the virtual array.
2113 * We only introduce at most one implication for any given virtual array,
2114 * so we can apply the implication and return as soon as we find one.
2116 static __isl_give isl_map *apply_implications(struct pet_scop *scop,
2117 __isl_take isl_map *map, __isl_keep isl_id *id, int satisfied)
2119 int i;
2121 for (i = 0; i < scop->n_implication; ++i) {
2122 struct pet_implication *pi = scop->implications[i];
2123 isl_id *pi_id;
2125 if (pi->satisfied != satisfied)
2126 continue;
2127 pi_id = isl_map_get_tuple_id(pi->extension, isl_dim_in);
2128 isl_id_free(pi_id);
2129 if (pi_id != id)
2130 continue;
2132 return isl_map_apply_range(map, isl_map_copy(pi->extension));
2135 return map;
2138 /* Is the filter expressed by "test" and "satisfied" implied
2139 * by filter "pos" on "domain", with filter "expr", taking into
2140 * account the implications of "scop"?
2142 * For filter on domain implying that expressed by "test" and "satisfied",
2143 * the filter needs to be an access to the same (virtual) array as "test" and
2144 * the filter value needs to be equal to "satisfied".
2145 * Moreover, the filter access relation, possibly extended by
2146 * the implications in "scop" needs to contain "test".
2148 static int implies_filter(struct pet_scop *scop,
2149 __isl_keep isl_map *domain, int pos, struct pet_expr *expr,
2150 __isl_keep isl_map *test, int satisfied)
2152 isl_id *test_id, *arg_id;
2153 isl_val *val;
2154 int is_int;
2155 int s;
2156 int is_subset;
2157 isl_map *implied;
2159 if (expr->type != pet_expr_access)
2160 return 0;
2161 test_id = isl_map_get_tuple_id(test, isl_dim_out);
2162 arg_id = pet_expr_access_get_id(expr);
2163 isl_id_free(arg_id);
2164 isl_id_free(test_id);
2165 if (test_id != arg_id)
2166 return 0;
2167 val = isl_map_plain_get_val_if_fixed(domain, isl_dim_out, pos);
2168 is_int = isl_val_is_int(val);
2169 if (is_int)
2170 s = isl_val_get_num_si(val);
2171 isl_val_free(val);
2172 if (!val)
2173 return -1;
2174 if (!is_int)
2175 return 0;
2176 if (s != satisfied)
2177 return 0;
2179 implied = isl_map_copy(expr->acc.access);
2180 implied = apply_implications(scop, implied, test_id, satisfied);
2181 is_subset = isl_map_is_subset(test, implied);
2182 isl_map_free(implied);
2184 return is_subset;
2187 /* Is the filter expressed by "test" and "satisfied" implied
2188 * by any of the filters on the domain of "stmt", taking into
2189 * account the implications of "scop"?
2191 static int filter_implied(struct pet_scop *scop,
2192 struct pet_stmt *stmt, __isl_keep isl_map *test, int satisfied)
2194 int i;
2195 int implied;
2196 isl_id *test_id;
2197 isl_map *domain;
2199 if (!scop || !stmt || !test)
2200 return -1;
2201 if (scop->n_implication == 0)
2202 return 0;
2203 if (stmt->n_arg == 0)
2204 return 0;
2206 domain = isl_set_unwrap(isl_set_copy(stmt->domain));
2208 implied = 0;
2209 for (i = 0; i < stmt->n_arg; ++i) {
2210 implied = implies_filter(scop, domain, i, stmt->args[i],
2211 test, satisfied);
2212 if (implied < 0 || implied)
2213 break;
2216 isl_map_free(domain);
2217 return implied;
2220 /* Make the statement "stmt" depend on the value of "test"
2221 * being equal to "satisfied" by adjusting stmt->domain.
2223 * The domain of "test" corresponds to the (zero or more) outer dimensions
2224 * of the iteration domain.
2226 * We first extend "test" to apply to the entire iteration domain and
2227 * then check if the filter that we are about to add is implied
2228 * by any of the current filters, possibly taking into account
2229 * the implications in "scop". If so, we leave "stmt" untouched and return.
2231 * Otherwise, we insert an argument corresponding to a read to "test"
2232 * from the iteration domain of "stmt" in front of the list of arguments.
2233 * We also insert a corresponding output dimension in the wrapped
2234 * map contained in stmt->domain, with value set to "satisfied".
2236 static struct pet_stmt *stmt_filter(struct pet_scop *scop,
2237 struct pet_stmt *stmt, __isl_take isl_map *test, int satisfied)
2239 int i;
2240 int implied;
2241 isl_id *id;
2242 isl_ctx *ctx;
2243 isl_map *map, *add_dom;
2244 isl_space *space;
2245 isl_set *dom;
2246 int n_test_dom;
2248 if (!stmt || !test)
2249 goto error;
2251 space = isl_set_get_space(stmt->domain);
2252 if (isl_space_is_wrapping(space))
2253 space = isl_space_domain(isl_space_unwrap(space));
2254 dom = isl_set_universe(space);
2255 n_test_dom = isl_map_dim(test, isl_dim_in);
2256 add_dom = isl_map_from_range(dom);
2257 add_dom = isl_map_add_dims(add_dom, isl_dim_in, n_test_dom);
2258 for (i = 0; i < n_test_dom; ++i)
2259 add_dom = isl_map_equate(add_dom, isl_dim_in, i,
2260 isl_dim_out, i);
2261 test = isl_map_apply_domain(test, add_dom);
2263 implied = filter_implied(scop, stmt, test, satisfied);
2264 if (implied < 0)
2265 goto error;
2266 if (implied) {
2267 isl_map_free(test);
2268 return stmt;
2271 id = isl_map_get_tuple_id(test, isl_dim_out);
2272 map = insert_filter_map(isl_set_get_space(stmt->domain), id, satisfied);
2273 stmt->domain = isl_set_apply(stmt->domain, map);
2275 if (args_insert_access(&stmt->n_arg, &stmt->args, test) < 0)
2276 goto error;
2278 isl_map_free(test);
2279 return stmt;
2280 error:
2281 isl_map_free(test);
2282 return pet_stmt_free(stmt);
2285 /* Does "scop" have a skip condition of the given "type"?
2287 int pet_scop_has_skip(struct pet_scop *scop, enum pet_skip type)
2289 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2291 if (!scop)
2292 return -1;
2293 return ext->skip[type] != NULL;
2296 /* Does "scop" have a skip condition of the given "type" that
2297 * is an affine expression?
2299 int pet_scop_has_affine_skip(struct pet_scop *scop, enum pet_skip type)
2301 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2303 if (!scop)
2304 return -1;
2305 if (!ext->skip[type])
2306 return 0;
2307 return set_is_affine(ext->skip[type]);
2310 /* Does "scop" have a skip condition of the given "type" that
2311 * is not an affine expression?
2313 int pet_scop_has_var_skip(struct pet_scop *scop, enum pet_skip type)
2315 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2316 int aff;
2318 if (!scop)
2319 return -1;
2320 if (!ext->skip[type])
2321 return 0;
2322 aff = set_is_affine(ext->skip[type]);
2323 if (aff < 0)
2324 return -1;
2325 return !aff;
2328 /* Does "scop" have a skip condition of the given "type" that
2329 * is affine and holds on the entire domain?
2331 int pet_scop_has_universal_skip(struct pet_scop *scop, enum pet_skip type)
2333 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2334 isl_set *set;
2335 int is_aff;
2336 int is_univ;
2338 is_aff = pet_scop_has_affine_skip(scop, type);
2339 if (is_aff < 0 || !is_aff)
2340 return is_aff;
2342 set = isl_set_copy(ext->skip[type]);
2343 set = isl_set_fix_si(set, isl_dim_set, 0, 1);
2344 set = isl_set_params(set);
2345 is_univ = isl_set_plain_is_universe(set);
2346 isl_set_free(set);
2348 return is_univ;
2351 /* Replace scop->skip[type] by "skip".
2353 struct pet_scop *pet_scop_set_skip(struct pet_scop *scop,
2354 enum pet_skip type, __isl_take isl_set *skip)
2356 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2358 if (!scop || !skip)
2359 goto error;
2361 isl_set_free(ext->skip[type]);
2362 ext->skip[type] = skip;
2364 return scop;
2365 error:
2366 isl_set_free(skip);
2367 return pet_scop_free(scop);
2370 /* Return a copy of scop->skip[type].
2372 __isl_give isl_set *pet_scop_get_skip(struct pet_scop *scop,
2373 enum pet_skip type)
2375 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2377 if (!scop)
2378 return NULL;
2380 return isl_set_copy(ext->skip[type]);
2383 /* Assuming scop->skip[type] is an affine expression,
2384 * return the constraints on the parameters for which the skip condition
2385 * holds.
2387 __isl_give isl_set *pet_scop_get_affine_skip_domain(struct pet_scop *scop,
2388 enum pet_skip type)
2390 isl_set *skip;
2392 skip = pet_scop_get_skip(scop, type);
2393 skip = isl_set_fix_si(skip, isl_dim_set, 0, 1);
2394 skip = isl_set_params(skip);
2396 return skip;
2399 /* Return a map to the skip condition of the given type.
2401 __isl_give isl_map *pet_scop_get_skip_map(struct pet_scop *scop,
2402 enum pet_skip type)
2404 return isl_map_from_range(pet_scop_get_skip(scop, type));
2407 /* Return the identifier of the variable that is accessed by
2408 * the skip condition of the given type.
2410 * The skip condition is assumed not to be an affine condition.
2412 __isl_give isl_id *pet_scop_get_skip_id(struct pet_scop *scop,
2413 enum pet_skip type)
2415 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2417 if (!scop)
2418 return NULL;
2420 return isl_set_get_tuple_id(ext->skip[type]);
2423 /* Return an access pet_expr corresponding to the skip condition
2424 * of the given type.
2426 struct pet_expr *pet_scop_get_skip_expr(struct pet_scop *scop,
2427 enum pet_skip type)
2429 return pet_expr_from_access(pet_scop_get_skip_map(scop, type));
2432 /* Drop the the skip condition scop->skip[type].
2434 void pet_scop_reset_skip(struct pet_scop *scop, enum pet_skip type)
2436 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2438 if (!scop)
2439 return;
2441 isl_set_free(ext->skip[type]);
2442 ext->skip[type] = NULL;
2445 /* Make the skip condition (if any) depend on the value of "test" being
2446 * equal to "satisfied".
2448 * We only support the case where the original skip condition is universal,
2449 * i.e., where skipping is unconditional, and where satisfied == 1.
2450 * In this case, the skip condition is changed to skip only when
2451 * "test" is equal to one.
2453 static struct pet_scop *pet_scop_filter_skip(struct pet_scop *scop,
2454 enum pet_skip type, __isl_keep isl_map *test, int satisfied)
2456 int is_univ = 0;
2458 if (!scop)
2459 return NULL;
2460 if (!pet_scop_has_skip(scop, type))
2461 return scop;
2463 if (satisfied)
2464 is_univ = pet_scop_has_universal_skip(scop, type);
2465 if (is_univ < 0)
2466 return pet_scop_free(scop);
2467 if (satisfied && is_univ) {
2468 scop = pet_scop_set_skip(scop, type,
2469 isl_map_range(isl_map_copy(test)));
2470 if (!scop)
2471 return NULL;
2472 } else {
2473 isl_die(isl_map_get_ctx(test), isl_error_internal,
2474 "skip expression cannot be filtered",
2475 return pet_scop_free(scop));
2478 return scop;
2481 /* Make all statements in "scop" depend on the value of "test"
2482 * being equal to "satisfied" by adjusting their domains.
2484 struct pet_scop *pet_scop_filter(struct pet_scop *scop,
2485 __isl_take isl_map *test, int satisfied)
2487 int i;
2489 scop = pet_scop_filter_skip(scop, pet_skip_now, test, satisfied);
2490 scop = pet_scop_filter_skip(scop, pet_skip_later, test, satisfied);
2492 if (!scop || !test)
2493 goto error;
2495 for (i = 0; i < scop->n_stmt; ++i) {
2496 scop->stmts[i] = stmt_filter(scop, scop->stmts[i],
2497 isl_map_copy(test), satisfied);
2498 if (!scop->stmts[i])
2499 goto error;
2502 isl_map_free(test);
2503 return scop;
2504 error:
2505 isl_map_free(test);
2506 return pet_scop_free(scop);
2509 /* Add all parameters in "expr" to "dim" and return the result.
2511 static __isl_give isl_space *expr_collect_params(struct pet_expr *expr,
2512 __isl_take isl_space *dim)
2514 int i;
2516 if (!expr)
2517 goto error;
2518 for (i = 0; i < expr->n_arg; ++i)
2520 dim = expr_collect_params(expr->args[i], dim);
2522 if (expr->type == pet_expr_access)
2523 dim = isl_space_align_params(dim,
2524 isl_map_get_space(expr->acc.access));
2526 return dim;
2527 error:
2528 isl_space_free(dim);
2529 return pet_expr_free(expr);
2532 /* Add all parameters in "stmt" to "dim" and return the result.
2534 static __isl_give isl_space *stmt_collect_params(struct pet_stmt *stmt,
2535 __isl_take isl_space *dim)
2537 if (!stmt)
2538 goto error;
2540 dim = isl_space_align_params(dim, isl_set_get_space(stmt->domain));
2541 dim = isl_space_align_params(dim, isl_map_get_space(stmt->schedule));
2542 dim = expr_collect_params(stmt->body, dim);
2544 return dim;
2545 error:
2546 isl_space_free(dim);
2547 return pet_stmt_free(stmt);
2550 /* Add all parameters in "array" to "dim" and return the result.
2552 static __isl_give isl_space *array_collect_params(struct pet_array *array,
2553 __isl_take isl_space *dim)
2555 if (!array)
2556 goto error;
2558 dim = isl_space_align_params(dim, isl_set_get_space(array->context));
2559 dim = isl_space_align_params(dim, isl_set_get_space(array->extent));
2561 return dim;
2562 error:
2563 pet_array_free(array);
2564 return isl_space_free(dim);
2567 /* Add all parameters in "scop" to "dim" and return the result.
2569 static __isl_give isl_space *scop_collect_params(struct pet_scop *scop,
2570 __isl_take isl_space *dim)
2572 int i;
2574 if (!scop)
2575 goto error;
2577 for (i = 0; i < scop->n_array; ++i)
2578 dim = array_collect_params(scop->arrays[i], dim);
2580 for (i = 0; i < scop->n_stmt; ++i)
2581 dim = stmt_collect_params(scop->stmts[i], dim);
2583 return dim;
2584 error:
2585 isl_space_free(dim);
2586 return pet_scop_free(scop);
2589 /* Add all parameters in "dim" to all access relations in "expr".
2591 static struct pet_expr *expr_propagate_params(struct pet_expr *expr,
2592 __isl_take isl_space *dim)
2594 int i;
2596 if (!expr)
2597 goto error;
2599 for (i = 0; i < expr->n_arg; ++i) {
2600 expr->args[i] =
2601 expr_propagate_params(expr->args[i],
2602 isl_space_copy(dim));
2603 if (!expr->args[i])
2604 goto error;
2607 if (expr->type == pet_expr_access) {
2608 expr->acc.access = isl_map_align_params(expr->acc.access,
2609 isl_space_copy(dim));
2610 if (!expr->acc.access)
2611 goto error;
2614 isl_space_free(dim);
2615 return expr;
2616 error:
2617 isl_space_free(dim);
2618 return pet_expr_free(expr);
2621 /* Add all parameters in "dim" to the domain, schedule and
2622 * all access relations in "stmt".
2624 static struct pet_stmt *stmt_propagate_params(struct pet_stmt *stmt,
2625 __isl_take isl_space *dim)
2627 if (!stmt)
2628 goto error;
2630 stmt->domain = isl_set_align_params(stmt->domain, isl_space_copy(dim));
2631 stmt->schedule = isl_map_align_params(stmt->schedule,
2632 isl_space_copy(dim));
2633 stmt->body = expr_propagate_params(stmt->body, isl_space_copy(dim));
2635 if (!stmt->domain || !stmt->schedule || !stmt->body)
2636 goto error;
2638 isl_space_free(dim);
2639 return stmt;
2640 error:
2641 isl_space_free(dim);
2642 return pet_stmt_free(stmt);
2645 /* Add all parameters in "dim" to "array".
2647 static struct pet_array *array_propagate_params(struct pet_array *array,
2648 __isl_take isl_space *dim)
2650 if (!array)
2651 goto error;
2653 array->context = isl_set_align_params(array->context,
2654 isl_space_copy(dim));
2655 array->extent = isl_set_align_params(array->extent,
2656 isl_space_copy(dim));
2657 if (array->value_bounds) {
2658 array->value_bounds = isl_set_align_params(array->value_bounds,
2659 isl_space_copy(dim));
2660 if (!array->value_bounds)
2661 goto error;
2664 if (!array->context || !array->extent)
2665 goto error;
2667 isl_space_free(dim);
2668 return array;
2669 error:
2670 isl_space_free(dim);
2671 return pet_array_free(array);
2674 /* Add all parameters in "dim" to "scop".
2676 static struct pet_scop *scop_propagate_params(struct pet_scop *scop,
2677 __isl_take isl_space *dim)
2679 int i;
2681 if (!scop)
2682 goto error;
2684 for (i = 0; i < scop->n_array; ++i) {
2685 scop->arrays[i] = array_propagate_params(scop->arrays[i],
2686 isl_space_copy(dim));
2687 if (!scop->arrays[i])
2688 goto error;
2691 for (i = 0; i < scop->n_stmt; ++i) {
2692 scop->stmts[i] = stmt_propagate_params(scop->stmts[i],
2693 isl_space_copy(dim));
2694 if (!scop->stmts[i])
2695 goto error;
2698 isl_space_free(dim);
2699 return scop;
2700 error:
2701 isl_space_free(dim);
2702 return pet_scop_free(scop);
2705 /* Update all isl_sets and isl_maps in "scop" such that they all
2706 * have the same parameters.
2708 struct pet_scop *pet_scop_align_params(struct pet_scop *scop)
2710 isl_space *dim;
2712 if (!scop)
2713 return NULL;
2715 dim = isl_set_get_space(scop->context);
2716 dim = scop_collect_params(scop, dim);
2718 scop->context = isl_set_align_params(scop->context, isl_space_copy(dim));
2719 scop = scop_propagate_params(scop, dim);
2721 return scop;
2724 /* Check if the given access relation accesses a (0D) array that corresponds
2725 * to one of the parameters in "dim". If so, replace the array access
2726 * by an access to the set of integers with as index (and value)
2727 * that parameter.
2729 static __isl_give isl_map *access_detect_parameter(__isl_take isl_map *access,
2730 __isl_take isl_space *dim)
2732 isl_id *array_id = NULL;
2733 int pos = -1;
2735 if (isl_map_has_tuple_id(access, isl_dim_out)) {
2736 array_id = isl_map_get_tuple_id(access, isl_dim_out);
2737 pos = isl_space_find_dim_by_id(dim, isl_dim_param, array_id);
2739 isl_space_free(dim);
2741 if (pos < 0) {
2742 isl_id_free(array_id);
2743 return access;
2746 pos = isl_map_find_dim_by_id(access, isl_dim_param, array_id);
2747 if (pos < 0) {
2748 access = isl_map_insert_dims(access, isl_dim_param, 0, 1);
2749 access = isl_map_set_dim_id(access, isl_dim_param, 0, array_id);
2750 pos = 0;
2751 } else
2752 isl_id_free(array_id);
2754 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
2755 access = isl_map_equate(access, isl_dim_param, pos, isl_dim_out, 0);
2757 return access;
2760 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2761 * in "dim" by a value equal to the corresponding parameter.
2763 static struct pet_expr *expr_detect_parameter_accesses(struct pet_expr *expr,
2764 __isl_take isl_space *dim)
2766 int i;
2768 if (!expr)
2769 goto error;
2771 for (i = 0; i < expr->n_arg; ++i) {
2772 expr->args[i] =
2773 expr_detect_parameter_accesses(expr->args[i],
2774 isl_space_copy(dim));
2775 if (!expr->args[i])
2776 goto error;
2779 if (expr->type == pet_expr_access) {
2780 expr->acc.access = access_detect_parameter(expr->acc.access,
2781 isl_space_copy(dim));
2782 if (!expr->acc.access)
2783 goto error;
2786 isl_space_free(dim);
2787 return expr;
2788 error:
2789 isl_space_free(dim);
2790 return pet_expr_free(expr);
2793 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2794 * in "dim" by a value equal to the corresponding parameter.
2796 static struct pet_stmt *stmt_detect_parameter_accesses(struct pet_stmt *stmt,
2797 __isl_take isl_space *dim)
2799 if (!stmt)
2800 goto error;
2802 stmt->body = expr_detect_parameter_accesses(stmt->body,
2803 isl_space_copy(dim));
2805 if (!stmt->domain || !stmt->schedule || !stmt->body)
2806 goto error;
2808 isl_space_free(dim);
2809 return stmt;
2810 error:
2811 isl_space_free(dim);
2812 return pet_stmt_free(stmt);
2815 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2816 * in "dim" by a value equal to the corresponding parameter.
2818 static struct pet_scop *scop_detect_parameter_accesses(struct pet_scop *scop,
2819 __isl_take isl_space *dim)
2821 int i;
2823 if (!scop)
2824 goto error;
2826 for (i = 0; i < scop->n_stmt; ++i) {
2827 scop->stmts[i] = stmt_detect_parameter_accesses(scop->stmts[i],
2828 isl_space_copy(dim));
2829 if (!scop->stmts[i])
2830 goto error;
2833 isl_space_free(dim);
2834 return scop;
2835 error:
2836 isl_space_free(dim);
2837 return pet_scop_free(scop);
2840 /* Replace all accesses to (0D) arrays that correspond to any of
2841 * the parameters used in "scop" by a value equal
2842 * to the corresponding parameter.
2844 struct pet_scop *pet_scop_detect_parameter_accesses(struct pet_scop *scop)
2846 isl_space *dim;
2848 if (!scop)
2849 return NULL;
2851 dim = isl_set_get_space(scop->context);
2852 dim = scop_collect_params(scop, dim);
2854 scop = scop_detect_parameter_accesses(scop, dim);
2856 return scop;
2859 /* Add all read access relations (if "read" is set) and/or all write
2860 * access relations (if "write" is set) to "accesses" and return the result.
2862 static __isl_give isl_union_map *expr_collect_accesses(struct pet_expr *expr,
2863 int read, int write, __isl_take isl_union_map *accesses)
2865 int i;
2866 isl_id *id;
2867 isl_space *dim;
2869 if (!expr)
2870 return NULL;
2872 for (i = 0; i < expr->n_arg; ++i)
2873 accesses = expr_collect_accesses(expr->args[i],
2874 read, write, accesses);
2876 if (expr->type == pet_expr_access && !pet_expr_is_affine(expr) &&
2877 ((read && expr->acc.read) || (write && expr->acc.write)))
2878 accesses = isl_union_map_add_map(accesses,
2879 isl_map_copy(expr->acc.access));
2881 return accesses;
2884 /* Collect and return all read access relations (if "read" is set)
2885 * and/or all write access relations (if "write" is set) in "stmt".
2887 static __isl_give isl_union_map *stmt_collect_accesses(struct pet_stmt *stmt,
2888 int read, int write, __isl_take isl_space *dim)
2890 isl_union_map *accesses;
2892 if (!stmt)
2893 return NULL;
2895 accesses = isl_union_map_empty(dim);
2896 accesses = expr_collect_accesses(stmt->body, read, write, accesses);
2897 accesses = isl_union_map_intersect_domain(accesses,
2898 isl_union_set_from_set(isl_set_copy(stmt->domain)));
2900 return accesses;
2903 /* Collect and return all read access relations (if "read" is set)
2904 * and/or all write access relations (if "write" is set) in "scop".
2906 static __isl_give isl_union_map *scop_collect_accesses(struct pet_scop *scop,
2907 int read, int write)
2909 int i;
2910 isl_union_map *accesses;
2912 if (!scop)
2913 return NULL;
2915 accesses = isl_union_map_empty(isl_set_get_space(scop->context));
2917 for (i = 0; i < scop->n_stmt; ++i) {
2918 isl_union_map *accesses_i;
2919 isl_space *dim = isl_set_get_space(scop->context);
2920 accesses_i = stmt_collect_accesses(scop->stmts[i],
2921 read, write, dim);
2922 accesses = isl_union_map_union(accesses, accesses_i);
2925 return accesses;
2928 __isl_give isl_union_map *pet_scop_collect_reads(struct pet_scop *scop)
2930 return scop_collect_accesses(scop, 1, 0);
2933 __isl_give isl_union_map *pet_scop_collect_writes(struct pet_scop *scop)
2935 return scop_collect_accesses(scop, 0, 1);
2938 /* Collect and return the union of iteration domains in "scop".
2940 __isl_give isl_union_set *pet_scop_collect_domains(struct pet_scop *scop)
2942 int i;
2943 isl_set *domain_i;
2944 isl_union_set *domain;
2946 if (!scop)
2947 return NULL;
2949 domain = isl_union_set_empty(isl_set_get_space(scop->context));
2951 for (i = 0; i < scop->n_stmt; ++i) {
2952 domain_i = isl_set_copy(scop->stmts[i]->domain);
2953 domain = isl_union_set_add_set(domain, domain_i);
2956 return domain;
2959 /* Collect and return the schedules of the statements in "scop".
2960 * The range is normalized to the maximal number of scheduling
2961 * dimensions.
2963 __isl_give isl_union_map *pet_scop_collect_schedule(struct pet_scop *scop)
2965 int i, j;
2966 isl_map *schedule_i;
2967 isl_union_map *schedule;
2968 int depth, max_depth = 0;
2970 if (!scop)
2971 return NULL;
2973 schedule = isl_union_map_empty(isl_set_get_space(scop->context));
2975 for (i = 0; i < scop->n_stmt; ++i) {
2976 depth = isl_map_dim(scop->stmts[i]->schedule, isl_dim_out);
2977 if (depth > max_depth)
2978 max_depth = depth;
2981 for (i = 0; i < scop->n_stmt; ++i) {
2982 schedule_i = isl_map_copy(scop->stmts[i]->schedule);
2983 depth = isl_map_dim(schedule_i, isl_dim_out);
2984 schedule_i = isl_map_add_dims(schedule_i, isl_dim_out,
2985 max_depth - depth);
2986 for (j = depth; j < max_depth; ++j)
2987 schedule_i = isl_map_fix_si(schedule_i,
2988 isl_dim_out, j, 0);
2989 schedule = isl_union_map_add_map(schedule, schedule_i);
2992 return schedule;
2995 /* Does expression "expr" write to "id"?
2997 static int expr_writes(struct pet_expr *expr, __isl_keep isl_id *id)
2999 int i;
3000 isl_id *write_id;
3002 for (i = 0; i < expr->n_arg; ++i) {
3003 int writes = expr_writes(expr->args[i], id);
3004 if (writes < 0 || writes)
3005 return writes;
3008 if (expr->type != pet_expr_access)
3009 return 0;
3010 if (!expr->acc.write)
3011 return 0;
3012 if (pet_expr_is_affine(expr))
3013 return 0;
3015 write_id = pet_expr_access_get_id(expr);
3016 isl_id_free(write_id);
3018 if (!write_id)
3019 return -1;
3021 return write_id == id;
3024 /* Does statement "stmt" write to "id"?
3026 static int stmt_writes(struct pet_stmt *stmt, __isl_keep isl_id *id)
3028 return expr_writes(stmt->body, id);
3031 /* Is there any write access in "scop" that accesses "id"?
3033 int pet_scop_writes(struct pet_scop *scop, __isl_keep isl_id *id)
3035 int i;
3037 if (!scop)
3038 return -1;
3040 for (i = 0; i < scop->n_stmt; ++i) {
3041 int writes = stmt_writes(scop->stmts[i], id);
3042 if (writes < 0 || writes)
3043 return writes;
3046 return 0;
3049 /* Add a reference identifier to access expression "expr".
3050 * "user" points to an integer that contains the sequence number
3051 * of the next reference.
3053 static struct pet_expr *access_add_ref_id(struct pet_expr *expr, void *user)
3055 isl_ctx *ctx;
3056 char name[50];
3057 int *n_ref = user;
3059 if (!expr)
3060 return expr;
3062 ctx = isl_map_get_ctx(expr->acc.access);
3063 snprintf(name, sizeof(name), "__pet_ref_%d", (*n_ref)++);
3064 expr->acc.ref_id = isl_id_alloc(ctx, name, NULL);
3065 if (!expr->acc.ref_id)
3066 return pet_expr_free(expr);
3068 return expr;
3071 /* Add a reference identifier to all access expressions in "stmt".
3072 * "n_ref" points to an integer that contains the sequence number
3073 * of the next reference.
3075 static struct pet_stmt *stmt_add_ref_ids(struct pet_stmt *stmt, int *n_ref)
3077 int i;
3079 if (!stmt)
3080 return NULL;
3082 for (i = 0; i < stmt->n_arg; ++i) {
3083 stmt->args[i] = pet_expr_map_access(stmt->args[i],
3084 &access_add_ref_id, n_ref);
3085 if (!stmt->args[i])
3086 return pet_stmt_free(stmt);
3089 stmt->body = pet_expr_map_access(stmt->body, &access_add_ref_id, n_ref);
3090 if (!stmt->body)
3091 return pet_stmt_free(stmt);
3093 return stmt;
3096 /* Add a reference identifier to all access expressions in "scop".
3098 struct pet_scop *pet_scop_add_ref_ids(struct pet_scop *scop)
3100 int i;
3101 int n_ref;
3103 if (!scop)
3104 return NULL;
3106 n_ref = 0;
3107 for (i = 0; i < scop->n_stmt; ++i) {
3108 scop->stmts[i] = stmt_add_ref_ids(scop->stmts[i], &n_ref);
3109 if (!scop->stmts[i])
3110 return pet_scop_free(scop);
3113 return scop;
3116 /* Reset the user pointer on the tuple id and all parameter ids in "set".
3118 static __isl_give isl_set *set_anonymize(__isl_take isl_set *set)
3120 int i, n;
3122 n = isl_set_dim(set, isl_dim_param);
3123 for (i = 0; i < n; ++i) {
3124 isl_id *id = isl_set_get_dim_id(set, isl_dim_param, i);
3125 const char *name = isl_id_get_name(id);
3126 set = isl_set_set_dim_name(set, isl_dim_param, i, name);
3127 isl_id_free(id);
3130 if (!isl_set_is_params(set) && isl_set_has_tuple_id(set)) {
3131 isl_id *id = isl_set_get_tuple_id(set);
3132 const char *name = isl_id_get_name(id);
3133 set = isl_set_set_tuple_name(set, name);
3134 isl_id_free(id);
3137 return set;
3140 /* Reset the user pointer on the tuple ids and all parameter ids in "map".
3142 static __isl_give isl_map *map_anonymize(__isl_take isl_map *map)
3144 int i, n;
3146 n = isl_map_dim(map, isl_dim_param);
3147 for (i = 0; i < n; ++i) {
3148 isl_id *id = isl_map_get_dim_id(map, isl_dim_param, i);
3149 const char *name = isl_id_get_name(id);
3150 map = isl_map_set_dim_name(map, isl_dim_param, i, name);
3151 isl_id_free(id);
3154 if (isl_map_has_tuple_id(map, isl_dim_in)) {
3155 isl_id *id = isl_map_get_tuple_id(map, isl_dim_in);
3156 const char *name = isl_id_get_name(id);
3157 map = isl_map_set_tuple_name(map, isl_dim_in, name);
3158 isl_id_free(id);
3161 if (isl_map_has_tuple_id(map, isl_dim_out)) {
3162 isl_id *id = isl_map_get_tuple_id(map, isl_dim_out);
3163 const char *name = isl_id_get_name(id);
3164 map = isl_map_set_tuple_name(map, isl_dim_out, name);
3165 isl_id_free(id);
3168 return map;
3171 /* Reset the user pointer on all parameter ids in "array".
3173 static struct pet_array *array_anonymize(struct pet_array *array)
3175 if (!array)
3176 return NULL;
3178 array->context = set_anonymize(array->context);
3179 array->extent = set_anonymize(array->extent);
3180 if (!array->context || !array->extent)
3181 return pet_array_free(array);
3183 return array;
3186 /* Reset the user pointer on all parameter and tuple ids in
3187 * the access relation of the access expression "expr".
3189 static struct pet_expr *access_anonymize(struct pet_expr *expr, void *user)
3191 expr->acc.access = map_anonymize(expr->acc.access);
3192 if (!expr->acc.access)
3193 return pet_expr_free(expr);
3195 return expr;
3198 /* Reset the user pointer on all parameter and tuple ids in "stmt".
3200 static struct pet_stmt *stmt_anonymize(struct pet_stmt *stmt)
3202 int i;
3203 isl_space *space;
3204 isl_set *domain;
3206 if (!stmt)
3207 return NULL;
3209 stmt->domain = set_anonymize(stmt->domain);
3210 stmt->schedule = map_anonymize(stmt->schedule);
3211 if (!stmt->domain || !stmt->schedule)
3212 return pet_stmt_free(stmt);
3214 for (i = 0; i < stmt->n_arg; ++i) {
3215 stmt->args[i] = pet_expr_map_access(stmt->args[i],
3216 &access_anonymize, NULL);
3217 if (!stmt->args[i])
3218 return pet_stmt_free(stmt);
3221 stmt->body = pet_expr_map_access(stmt->body,
3222 &access_anonymize, NULL);
3223 if (!stmt->body)
3224 return pet_stmt_free(stmt);
3226 return stmt;
3229 /* Reset the user pointer on the tuple ids and all parameter ids
3230 * in "implication".
3232 static struct pet_implication *implication_anonymize(
3233 struct pet_implication *implication)
3235 if (!implication)
3236 return NULL;
3238 implication->extension = map_anonymize(implication->extension);
3239 if (!implication->extension)
3240 return pet_implication_free(implication);
3242 return implication;
3245 /* Reset the user pointer on all parameter and tuple ids in "scop".
3247 struct pet_scop *pet_scop_anonymize(struct pet_scop *scop)
3249 int i;
3251 if (!scop)
3252 return NULL;
3254 scop->context = set_anonymize(scop->context);
3255 scop->context_value = set_anonymize(scop->context_value);
3256 if (!scop->context || !scop->context_value)
3257 return pet_scop_free(scop);
3259 for (i = 0; i < scop->n_array; ++i) {
3260 scop->arrays[i] = array_anonymize(scop->arrays[i]);
3261 if (!scop->arrays[i])
3262 return pet_scop_free(scop);
3265 for (i = 0; i < scop->n_stmt; ++i) {
3266 scop->stmts[i] = stmt_anonymize(scop->stmts[i]);
3267 if (!scop->stmts[i])
3268 return pet_scop_free(scop);
3271 for (i = 0; i < scop->n_implication; ++i) {
3272 scop->implications[i] =
3273 implication_anonymize(scop->implications[i]);
3274 if (!scop->implications[i])
3275 return pet_scop_free(scop);
3278 return scop;
3281 /* If "value_bounds" contains any bounds on the variable accessed by "arg",
3282 * then intersect the range of "map" with the valid set of values.
3284 static __isl_give isl_map *access_apply_value_bounds(__isl_take isl_map *map,
3285 struct pet_expr *arg, __isl_keep isl_union_map *value_bounds)
3287 isl_id *id;
3288 isl_map *vb;
3289 isl_space *space;
3290 isl_ctx *ctx = isl_map_get_ctx(map);
3292 id = pet_expr_access_get_id(arg);
3293 space = isl_space_alloc(ctx, 0, 0, 1);
3294 space = isl_space_set_tuple_id(space, isl_dim_in, id);
3295 vb = isl_union_map_extract_map(value_bounds, space);
3296 if (!isl_map_plain_is_empty(vb))
3297 map = isl_map_intersect_range(map, isl_map_range(vb));
3298 else
3299 isl_map_free(vb);
3301 return map;
3304 /* Given a set "domain", return a wrapped relation with the given set
3305 * as domain and a range of dimension "n_arg", where each coordinate
3306 * is either unbounded or, if the corresponding element of args is of
3307 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
3309 static __isl_give isl_set *apply_value_bounds(__isl_take isl_set *domain,
3310 unsigned n_arg, struct pet_expr **args,
3311 __isl_keep isl_union_map *value_bounds)
3313 int i;
3314 isl_map *map;
3315 isl_space *space;
3317 map = isl_map_from_domain(domain);
3318 space = isl_map_get_space(map);
3319 space = isl_space_add_dims(space, isl_dim_out, 1);
3321 for (i = 0; i < n_arg; ++i) {
3322 isl_map *map_i;
3323 struct pet_expr *arg = args[i];
3325 map_i = isl_map_universe(isl_space_copy(space));
3326 if (arg->type == pet_expr_access)
3327 map_i = access_apply_value_bounds(map_i, arg,
3328 value_bounds);
3329 map = isl_map_flat_range_product(map, map_i);
3331 isl_space_free(space);
3333 return isl_map_wrap(map);
3336 /* Data used in access_gist() callback.
3338 struct pet_access_gist_data {
3339 isl_set *domain;
3340 isl_union_map *value_bounds;
3343 /* Given an expression "expr" of type pet_expr_access, compute
3344 * the gist of the associated access relation with respect to
3345 * data->domain and the bounds on the values of the arguments
3346 * of the expression.
3348 static struct pet_expr *access_gist(struct pet_expr *expr, void *user)
3350 struct pet_access_gist_data *data = user;
3351 isl_set *domain;
3353 domain = isl_set_copy(data->domain);
3354 if (expr->n_arg > 0)
3355 domain = apply_value_bounds(domain, expr->n_arg, expr->args,
3356 data->value_bounds);
3358 expr->acc.access = isl_map_gist_domain(expr->acc.access, domain);
3359 if (!expr->acc.access)
3360 return pet_expr_free(expr);
3362 return expr;
3365 /* Compute the gist of the iteration domain and all access relations
3366 * of "stmt" based on the constraints on the parameters specified by "context"
3367 * and the constraints on the values of nested accesses specified
3368 * by "value_bounds".
3370 static struct pet_stmt *stmt_gist(struct pet_stmt *stmt,
3371 __isl_keep isl_set *context, __isl_keep isl_union_map *value_bounds)
3373 int i;
3374 isl_space *space;
3375 isl_set *domain;
3376 struct pet_access_gist_data data;
3378 if (!stmt)
3379 return NULL;
3381 data.domain = isl_set_copy(stmt->domain);
3382 data.value_bounds = value_bounds;
3383 if (stmt->n_arg > 0)
3384 data.domain = isl_map_domain(isl_set_unwrap(data.domain));
3386 data.domain = isl_set_intersect_params(data.domain,
3387 isl_set_copy(context));
3389 for (i = 0; i < stmt->n_arg; ++i) {
3390 stmt->args[i] = pet_expr_map_access(stmt->args[i],
3391 &access_gist, &data);
3392 if (!stmt->args[i])
3393 goto error;
3396 stmt->body = pet_expr_map_access(stmt->body, &access_gist, &data);
3397 if (!stmt->body)
3398 goto error;
3400 isl_set_free(data.domain);
3402 space = isl_set_get_space(stmt->domain);
3403 if (isl_space_is_wrapping(space))
3404 space = isl_space_domain(isl_space_unwrap(space));
3405 domain = isl_set_universe(space);
3406 domain = isl_set_intersect_params(domain, isl_set_copy(context));
3407 if (stmt->n_arg > 0)
3408 domain = apply_value_bounds(domain, stmt->n_arg, stmt->args,
3409 value_bounds);
3410 stmt->domain = isl_set_gist(stmt->domain, domain);
3411 if (!stmt->domain)
3412 return pet_stmt_free(stmt);
3414 return stmt;
3415 error:
3416 isl_set_free(data.domain);
3417 return pet_stmt_free(stmt);
3420 /* Compute the gist of the extent of the array
3421 * based on the constraints on the parameters specified by "context".
3423 static struct pet_array *array_gist(struct pet_array *array,
3424 __isl_keep isl_set *context)
3426 if (!array)
3427 return NULL;
3429 array->extent = isl_set_gist_params(array->extent,
3430 isl_set_copy(context));
3431 if (!array->extent)
3432 return pet_array_free(array);
3434 return array;
3437 /* Compute the gist of all sets and relations in "scop"
3438 * based on the constraints on the parameters specified by "scop->context"
3439 * and the constraints on the values of nested accesses specified
3440 * by "value_bounds".
3442 struct pet_scop *pet_scop_gist(struct pet_scop *scop,
3443 __isl_keep isl_union_map *value_bounds)
3445 int i;
3447 if (!scop)
3448 return NULL;
3450 scop->context = isl_set_coalesce(scop->context);
3451 if (!scop->context)
3452 return pet_scop_free(scop);
3454 for (i = 0; i < scop->n_array; ++i) {
3455 scop->arrays[i] = array_gist(scop->arrays[i], scop->context);
3456 if (!scop->arrays[i])
3457 return pet_scop_free(scop);
3460 for (i = 0; i < scop->n_stmt; ++i) {
3461 scop->stmts[i] = stmt_gist(scop->stmts[i], scop->context,
3462 value_bounds);
3463 if (!scop->stmts[i])
3464 return pet_scop_free(scop);
3467 return scop;
3470 /* Intersect the context of "scop" with "context".
3471 * To ensure that we don't introduce any unnamed parameters in
3472 * the context of "scop", we first remove the unnamed parameters
3473 * from "context".
3475 struct pet_scop *pet_scop_restrict_context(struct pet_scop *scop,
3476 __isl_take isl_set *context)
3478 if (!scop)
3479 goto error;
3481 context = set_project_out_unnamed_params(context);
3482 scop->context = isl_set_intersect(scop->context, context);
3483 if (!scop->context)
3484 return pet_scop_free(scop);
3486 return scop;
3487 error:
3488 isl_set_free(context);
3489 return pet_scop_free(scop);
3492 /* Drop the current context of "scop". That is, replace the context
3493 * by a universal set.
3495 struct pet_scop *pet_scop_reset_context(struct pet_scop *scop)
3497 isl_space *space;
3499 if (!scop)
3500 return NULL;
3502 space = isl_set_get_space(scop->context);
3503 isl_set_free(scop->context);
3504 scop->context = isl_set_universe(space);
3505 if (!scop->context)
3506 return pet_scop_free(scop);
3508 return scop;
3511 /* Append "array" to the arrays of "scop".
3513 struct pet_scop *pet_scop_add_array(struct pet_scop *scop,
3514 struct pet_array *array)
3516 isl_ctx *ctx;
3517 struct pet_array **arrays;
3519 if (!array || !scop)
3520 goto error;
3522 ctx = isl_set_get_ctx(scop->context);
3523 arrays = isl_realloc_array(ctx, scop->arrays, struct pet_array *,
3524 scop->n_array + 1);
3525 if (!arrays)
3526 goto error;
3527 scop->arrays = arrays;
3528 scop->arrays[scop->n_array] = array;
3529 scop->n_array++;
3531 return scop;
3532 error:
3533 pet_array_free(array);
3534 return pet_scop_free(scop);
3537 /* Create and return an implication on filter values equal to "satisfied"
3538 * with extension "map".
3540 static struct pet_implication *new_implication(__isl_take isl_map *map,
3541 int satisfied)
3543 isl_ctx *ctx;
3544 struct pet_implication *implication;
3546 if (!map)
3547 return NULL;
3548 ctx = isl_map_get_ctx(map);
3549 implication = isl_alloc_type(ctx, struct pet_implication);
3550 if (!implication)
3551 goto error;
3553 implication->extension = map;
3554 implication->satisfied = satisfied;
3556 return implication;
3557 error:
3558 isl_map_free(map);
3559 return NULL;
3562 /* Add an implication on filter values equal to "satisfied"
3563 * with extension "map" to "scop".
3565 struct pet_scop *pet_scop_add_implication(struct pet_scop *scop,
3566 __isl_take isl_map *map, int satisfied)
3568 isl_ctx *ctx;
3569 struct pet_implication *implication;
3570 struct pet_implication **implications;
3572 implication = new_implication(map, satisfied);
3573 if (!scop || !implication)
3574 goto error;
3576 ctx = isl_set_get_ctx(scop->context);
3577 implications = isl_realloc_array(ctx, scop->implications,
3578 struct pet_implication *,
3579 scop->n_implication + 1);
3580 if (!implications)
3581 goto error;
3582 scop->implications = implications;
3583 scop->implications[scop->n_implication] = implication;
3584 scop->n_implication++;
3586 return scop;
3587 error:
3588 pet_implication_free(implication);
3589 return pet_scop_free(scop);