scop.c: extract out insert_filter_map
[pet.git] / scop.c
blob1fc1a3b4cff8e8404a0b49a979bb3f60588a4a47
1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012 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 <isl/constraint.h>
36 #include <isl/union_set.h>
38 #include "scop.h"
40 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
42 static char *type_str[] = {
43 [pet_expr_access] = "access",
44 [pet_expr_call] = "call",
45 [pet_expr_double] = "double",
46 [pet_expr_unary] = "unary",
47 [pet_expr_binary] = "binary",
48 [pet_expr_ternary] = "ternary"
51 static char *op_str[] = {
52 [pet_op_add_assign] = "+=",
53 [pet_op_sub_assign] = "-=",
54 [pet_op_mul_assign] = "*=",
55 [pet_op_div_assign] = "/=",
56 [pet_op_assign] = "=",
57 [pet_op_add] = "+",
58 [pet_op_sub] = "-",
59 [pet_op_mul] = "*",
60 [pet_op_div] = "/",
61 [pet_op_eq] = "==",
62 [pet_op_le] = "<=",
63 [pet_op_lt] = "<",
64 [pet_op_gt] = ">",
65 [pet_op_minus] = "-",
66 [pet_op_post_inc] = "++",
67 [pet_op_post_dec] = "--",
68 [pet_op_pre_inc] = "++",
69 [pet_op_pre_dec] = "--",
70 [pet_op_address_of] = "&"
73 const char *pet_op_str(enum pet_op_type op)
75 return op_str[op];
78 int pet_op_is_inc_dec(enum pet_op_type op)
80 return op == pet_op_post_inc || op == pet_op_post_dec ||
81 op == pet_op_pre_inc || op == pet_op_pre_dec;
84 const char *pet_type_str(enum pet_expr_type type)
86 return type_str[type];
89 enum pet_op_type pet_str_op(const char *str)
91 int i;
93 for (i = 0; i < ARRAY_SIZE(op_str); ++i)
94 if (!strcmp(op_str[i], str))
95 return i;
97 return -1;
100 enum pet_expr_type pet_str_type(const char *str)
102 int i;
104 for (i = 0; i < ARRAY_SIZE(type_str); ++i)
105 if (!strcmp(type_str[i], str))
106 return i;
108 return -1;
111 /* Construct a pet_expr from an access relation.
112 * By default, it is considered to be a read access.
114 struct pet_expr *pet_expr_from_access(__isl_take isl_map *access)
116 isl_ctx *ctx = isl_map_get_ctx(access);
117 struct pet_expr *expr;
119 if (!access)
120 return NULL;
121 expr = isl_calloc_type(ctx, struct pet_expr);
122 if (!expr)
123 goto error;
125 expr->type = pet_expr_access;
126 expr->acc.access = access;
127 expr->acc.read = 1;
128 expr->acc.write = 0;
130 return expr;
131 error:
132 isl_map_free(access);
133 return NULL;
136 /* Construct a unary pet_expr that performs "op" on "arg".
138 struct pet_expr *pet_expr_new_unary(isl_ctx *ctx, enum pet_op_type op,
139 struct pet_expr *arg)
141 struct pet_expr *expr;
143 if (!arg)
144 goto error;
145 expr = isl_alloc_type(ctx, struct pet_expr);
146 if (!expr)
147 goto error;
149 expr->type = pet_expr_unary;
150 expr->op = op;
151 expr->n_arg = 1;
152 expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
153 if (!expr->args)
154 goto error;
155 expr->args[pet_un_arg] = arg;
157 return expr;
158 error:
159 pet_expr_free(arg);
160 return NULL;
163 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
165 struct pet_expr *pet_expr_new_binary(isl_ctx *ctx, enum pet_op_type op,
166 struct pet_expr *lhs, struct pet_expr *rhs)
168 struct pet_expr *expr;
170 if (!lhs || !rhs)
171 goto error;
172 expr = isl_alloc_type(ctx, struct pet_expr);
173 if (!expr)
174 goto error;
176 expr->type = pet_expr_binary;
177 expr->op = op;
178 expr->n_arg = 2;
179 expr->args = isl_calloc_array(ctx, struct pet_expr *, 2);
180 if (!expr->args)
181 goto error;
182 expr->args[pet_bin_lhs] = lhs;
183 expr->args[pet_bin_rhs] = rhs;
185 return expr;
186 error:
187 pet_expr_free(lhs);
188 pet_expr_free(rhs);
189 return NULL;
192 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
194 struct pet_expr *pet_expr_new_ternary(isl_ctx *ctx, struct pet_expr *cond,
195 struct pet_expr *lhs, struct pet_expr *rhs)
197 struct pet_expr *expr;
199 if (!cond || !lhs || !rhs)
200 goto error;
201 expr = isl_alloc_type(ctx, struct pet_expr);
202 if (!expr)
203 goto error;
205 expr->type = pet_expr_ternary;
206 expr->n_arg = 3;
207 expr->args = isl_calloc_array(ctx, struct pet_expr *, 3);
208 if (!expr->args)
209 goto error;
210 expr->args[pet_ter_cond] = cond;
211 expr->args[pet_ter_true] = lhs;
212 expr->args[pet_ter_false] = rhs;
214 return expr;
215 error:
216 pet_expr_free(cond);
217 pet_expr_free(lhs);
218 pet_expr_free(rhs);
219 return NULL;
222 /* Construct a call pet_expr that calls function "name" with "n_arg"
223 * arguments. The caller is responsible for filling in the arguments.
225 struct pet_expr *pet_expr_new_call(isl_ctx *ctx, const char *name,
226 unsigned n_arg)
228 struct pet_expr *expr;
230 expr = isl_alloc_type(ctx, struct pet_expr);
231 if (!expr)
232 return NULL;
234 expr->type = pet_expr_call;
235 expr->n_arg = n_arg;
236 expr->name = strdup(name);
237 expr->args = isl_calloc_array(ctx, struct pet_expr *, n_arg);
238 if (!expr->name || !expr->args)
239 return pet_expr_free(expr);
241 return expr;
244 /* Construct a pet_expr that represents the double "d".
246 struct pet_expr *pet_expr_new_double(isl_ctx *ctx, double d)
248 struct pet_expr *expr;
250 expr = isl_calloc_type(ctx, struct pet_expr);
251 if (!expr)
252 return NULL;
254 expr->type = pet_expr_double;
255 expr->d = d;
257 return expr;
260 void *pet_expr_free(struct pet_expr *expr)
262 int i;
264 if (!expr)
265 return NULL;
267 for (i = 0; i < expr->n_arg; ++i)
268 pet_expr_free(expr->args[i]);
269 free(expr->args);
271 switch (expr->type) {
272 case pet_expr_access:
273 isl_map_free(expr->acc.access);
274 break;
275 case pet_expr_call:
276 free(expr->name);
277 break;
278 case pet_expr_double:
279 case pet_expr_unary:
280 case pet_expr_binary:
281 case pet_expr_ternary:
282 break;
285 free(expr);
286 return NULL;
289 static void expr_dump(struct pet_expr *expr, int indent)
291 int i;
293 if (!expr)
294 return;
296 fprintf(stderr, "%*s", indent, "");
298 switch (expr->type) {
299 case pet_expr_double:
300 fprintf(stderr, "%g\n", expr->d);
301 break;
302 case pet_expr_access:
303 isl_map_dump(expr->acc.access);
304 fprintf(stderr, "%*sread: %d\n", indent + 2,
305 "", expr->acc.read);
306 fprintf(stderr, "%*swrite: %d\n", indent + 2,
307 "", expr->acc.write);
308 for (i = 0; i < expr->n_arg; ++i)
309 expr_dump(expr->args[i], indent + 2);
310 break;
311 case pet_expr_unary:
312 fprintf(stderr, "%s\n", op_str[expr->op]);
313 expr_dump(expr->args[pet_un_arg], indent + 2);
314 break;
315 case pet_expr_binary:
316 fprintf(stderr, "%s\n", op_str[expr->op]);
317 expr_dump(expr->args[pet_bin_lhs], indent + 2);
318 expr_dump(expr->args[pet_bin_rhs], indent + 2);
319 break;
320 case pet_expr_ternary:
321 fprintf(stderr, "?:\n");
322 expr_dump(expr->args[pet_ter_cond], indent + 2);
323 expr_dump(expr->args[pet_ter_true], indent + 2);
324 expr_dump(expr->args[pet_ter_false], indent + 2);
325 break;
326 case pet_expr_call:
327 fprintf(stderr, "%s/%d\n", expr->name, expr->n_arg);
328 for (i = 0; i < expr->n_arg; ++i)
329 expr_dump(expr->args[i], indent + 2);
330 break;
334 void pet_expr_dump(struct pet_expr *expr)
336 expr_dump(expr, 0);
339 /* Does "expr" represent an access to an unnamed space, i.e.,
340 * does it represent an affine expression?
342 int pet_expr_is_affine(struct pet_expr *expr)
344 int has_id;
346 if (!expr)
347 return -1;
348 if (expr->type != pet_expr_access)
349 return 0;
351 has_id = isl_map_has_tuple_id(expr->acc.access, isl_dim_out);
352 if (has_id < 0)
353 return -1;
355 return !has_id;
358 /* Return 1 if the two pet_exprs are equivalent.
360 int pet_expr_is_equal(struct pet_expr *expr1, struct pet_expr *expr2)
362 int i;
364 if (!expr1 || !expr2)
365 return 0;
367 if (expr1->type != expr2->type)
368 return 0;
369 if (expr1->n_arg != expr2->n_arg)
370 return 0;
371 for (i = 0; i < expr1->n_arg; ++i)
372 if (!pet_expr_is_equal(expr1->args[i], expr2->args[i]))
373 return 0;
374 switch (expr1->type) {
375 case pet_expr_double:
376 if (expr1->d != expr2->d)
377 return 0;
378 break;
379 case pet_expr_access:
380 if (expr1->acc.read != expr2->acc.read)
381 return 0;
382 if (expr1->acc.write != expr2->acc.write)
383 return 0;
384 if (!expr1->acc.access || !expr2->acc.access)
385 return 0;
386 if (!isl_map_is_equal(expr1->acc.access, expr2->acc.access))
387 return 0;
388 break;
389 case pet_expr_unary:
390 case pet_expr_binary:
391 case pet_expr_ternary:
392 if (expr1->op != expr2->op)
393 return 0;
394 break;
395 case pet_expr_call:
396 if (strcmp(expr1->name, expr2->name))
397 return 0;
398 break;
401 return 1;
404 /* Add extra conditions on the parameters to all access relations in "expr".
406 struct pet_expr *pet_expr_restrict(struct pet_expr *expr,
407 __isl_take isl_set *cond)
409 int i;
411 if (!expr)
412 goto error;
414 for (i = 0; i < expr->n_arg; ++i) {
415 expr->args[i] = pet_expr_restrict(expr->args[i],
416 isl_set_copy(cond));
417 if (!expr->args[i])
418 goto error;
421 if (expr->type == pet_expr_access) {
422 expr->acc.access = isl_map_intersect_params(expr->acc.access,
423 isl_set_copy(cond));
424 if (!expr->acc.access)
425 goto error;
428 isl_set_free(cond);
429 return expr;
430 error:
431 isl_set_free(cond);
432 return pet_expr_free(expr);
435 /* Modify all access relations in "expr" by calling "fn" on them.
437 struct pet_expr *pet_expr_foreach_access(struct pet_expr *expr,
438 __isl_give isl_map *(*fn)(__isl_take isl_map *access, void *user),
439 void *user)
441 int i;
443 if (!expr)
444 return NULL;
446 for (i = 0; i < expr->n_arg; ++i) {
447 expr->args[i] = pet_expr_foreach_access(expr->args[i], fn, user);
448 if (!expr->args[i])
449 return pet_expr_free(expr);
452 if (expr->type == pet_expr_access) {
453 expr->acc.access = fn(expr->acc.access, user);
454 if (!expr->acc.access)
455 return pet_expr_free(expr);
458 return expr;
461 /* Modify all expressions of type pet_expr_access in "expr"
462 * by calling "fn" on them.
464 struct pet_expr *pet_expr_foreach_access_expr(struct pet_expr *expr,
465 struct pet_expr *(*fn)(struct pet_expr *expr, void *user),
466 void *user)
468 int i;
470 if (!expr)
471 return NULL;
473 for (i = 0; i < expr->n_arg; ++i) {
474 expr->args[i] = pet_expr_foreach_access_expr(expr->args[i],
475 fn, user);
476 if (!expr->args[i])
477 return pet_expr_free(expr);
480 if (expr->type == pet_expr_access)
481 expr = fn(expr, user);
483 return expr;
486 /* Modify the given access relation based on the given iteration space
487 * transformation.
488 * If the access has any arguments then the domain of the access relation
489 * is a wrapped mapping from the iteration space to the space of
490 * argument values. We only need to change the domain of this wrapped
491 * mapping, so we extend the input transformation with an identity mapping
492 * on the space of argument values.
494 static __isl_give isl_map *update_domain(__isl_take isl_map *access,
495 void *user)
497 isl_map *update = user;
498 isl_space *dim;
500 update = isl_map_copy(update);
502 dim = isl_map_get_space(access);
503 dim = isl_space_domain(dim);
504 if (!isl_space_is_wrapping(dim))
505 isl_space_free(dim);
506 else {
507 isl_map *id;
508 dim = isl_space_unwrap(dim);
509 dim = isl_space_range(dim);
510 dim = isl_space_map_from_set(dim);
511 id = isl_map_identity(dim);
512 update = isl_map_product(update, id);
515 return isl_map_apply_domain(access, update);
518 /* Modify all access relations in "expr" based on the given iteration space
519 * transformation.
521 static struct pet_expr *expr_update_domain(struct pet_expr *expr,
522 __isl_take isl_map *update)
524 expr = pet_expr_foreach_access(expr, &update_domain, update);
525 isl_map_free(update);
526 return expr;
529 /* Construct a pet_stmt with given line number and statement
530 * number from a pet_expr.
531 * The initial iteration domain is the zero-dimensional universe.
532 * The name of the domain is given by "label" if it is non-NULL.
533 * Otherwise, the name is constructed as S_<id>.
534 * The domains of all access relations are modified to refer
535 * to the statement iteration domain.
537 struct pet_stmt *pet_stmt_from_pet_expr(isl_ctx *ctx, int line,
538 __isl_take isl_id *label, int id, struct pet_expr *expr)
540 struct pet_stmt *stmt;
541 isl_space *dim;
542 isl_set *dom;
543 isl_map *sched;
544 isl_map *add_name;
545 char name[50];
547 if (!expr)
548 goto error;
550 stmt = isl_calloc_type(ctx, struct pet_stmt);
551 if (!stmt)
552 goto error;
554 dim = isl_space_set_alloc(ctx, 0, 0);
555 if (label)
556 dim = isl_space_set_tuple_id(dim, isl_dim_set, label);
557 else {
558 snprintf(name, sizeof(name), "S_%d", id);
559 dim = isl_space_set_tuple_name(dim, isl_dim_set, name);
561 dom = isl_set_universe(isl_space_copy(dim));
562 sched = isl_map_from_domain(isl_set_copy(dom));
564 dim = isl_space_from_range(dim);
565 add_name = isl_map_universe(dim);
566 expr = expr_update_domain(expr, add_name);
568 stmt->line = line;
569 stmt->domain = dom;
570 stmt->schedule = sched;
571 stmt->body = expr;
573 if (!stmt->domain || !stmt->schedule || !stmt->body)
574 return pet_stmt_free(stmt);
576 return stmt;
577 error:
578 isl_id_free(label);
579 return pet_expr_free(expr);
582 void *pet_stmt_free(struct pet_stmt *stmt)
584 int i;
586 if (!stmt)
587 return NULL;
589 isl_set_free(stmt->domain);
590 isl_map_free(stmt->schedule);
591 pet_expr_free(stmt->body);
593 for (i = 0; i < stmt->n_arg; ++i)
594 pet_expr_free(stmt->args[i]);
595 free(stmt->args);
597 free(stmt);
598 return NULL;
601 static void stmt_dump(struct pet_stmt *stmt, int indent)
603 int i;
605 if (!stmt)
606 return;
608 fprintf(stderr, "%*s%d\n", indent, "", stmt->line);
609 fprintf(stderr, "%*s", indent, "");
610 isl_set_dump(stmt->domain);
611 fprintf(stderr, "%*s", indent, "");
612 isl_map_dump(stmt->schedule);
613 expr_dump(stmt->body, indent);
614 for (i = 0; i < stmt->n_arg; ++i)
615 expr_dump(stmt->args[i], indent + 2);
618 void pet_stmt_dump(struct pet_stmt *stmt)
620 stmt_dump(stmt, 0);
623 void *pet_array_free(struct pet_array *array)
625 if (!array)
626 return NULL;
628 isl_set_free(array->context);
629 isl_set_free(array->extent);
630 isl_set_free(array->value_bounds);
631 free(array->element_type);
633 free(array);
634 return NULL;
637 void pet_array_dump(struct pet_array *array)
639 if (!array)
640 return;
642 isl_set_dump(array->context);
643 isl_set_dump(array->extent);
644 isl_set_dump(array->value_bounds);
645 fprintf(stderr, "%s %s\n", array->element_type,
646 array->live_out ? "live-out" : "");
649 struct pet_scop *pet_scop_alloc(isl_ctx *ctx)
651 return isl_calloc_type(ctx, struct pet_scop);
654 /* Construct a pet_scop with room for n statements.
656 static struct pet_scop *scop_alloc(isl_ctx *ctx, int n)
658 isl_space *space;
659 struct pet_scop *scop;
661 scop = pet_scop_alloc(ctx);
662 if (!scop)
663 return NULL;
665 space = isl_space_params_alloc(ctx, 0);
666 scop->context = isl_set_universe(isl_space_copy(space));
667 scop->context_value = isl_set_universe(space);
668 scop->stmts = isl_calloc_array(ctx, struct pet_stmt *, n);
669 if (!scop->context || !scop->stmts)
670 return pet_scop_free(scop);
672 scop->n_stmt = n;
674 return scop;
677 struct pet_scop *pet_scop_empty(isl_ctx *ctx)
679 return scop_alloc(ctx, 0);
682 /* Update "context" with respect to the valid parameter values for "access".
684 static __isl_give isl_set *access_extract_context(__isl_keep isl_map *access,
685 __isl_take isl_set *context)
687 context = isl_set_intersect(context,
688 isl_map_params(isl_map_copy(access)));
689 return context;
692 /* Update "context" with respect to the valid parameter values for "expr".
694 * If "expr" represents a ternary operator, then a parameter value
695 * needs to be valid for the condition and for at least one of the
696 * remaining two arguments.
697 * If the condition is an affine expression, then we can be a bit more specific.
698 * The parameter then has to be valid for the second argument for
699 * non-zero accesses and valid for the third argument for zero accesses.
701 static __isl_give isl_set *expr_extract_context(struct pet_expr *expr,
702 __isl_take isl_set *context)
704 int i;
706 if (expr->type == pet_expr_ternary) {
707 int is_aff;
708 isl_set *context1, *context2;
710 is_aff = pet_expr_is_affine(expr->args[0]);
711 if (is_aff < 0)
712 goto error;
714 context = expr_extract_context(expr->args[0], context);
715 context1 = expr_extract_context(expr->args[1],
716 isl_set_copy(context));
717 context2 = expr_extract_context(expr->args[2], context);
719 if (is_aff) {
720 isl_map *access;
721 isl_set *zero_set;
723 access = isl_map_copy(expr->args[0]->acc.access);
724 access = isl_map_fix_si(access, isl_dim_out, 0, 0);
725 zero_set = isl_map_params(access);
726 context1 = isl_set_subtract(context1,
727 isl_set_copy(zero_set));
728 context2 = isl_set_intersect(context2, zero_set);
731 context = isl_set_union(context1, context2);
732 context = isl_set_coalesce(context);
734 return context;
737 for (i = 0; i < expr->n_arg; ++i)
738 context = expr_extract_context(expr->args[i], context);
740 if (expr->type == pet_expr_access)
741 context = access_extract_context(expr->acc.access, context);
743 return context;
744 error:
745 isl_set_free(context);
746 return NULL;
749 /* Update "context" with respect to the valid parameter values for "stmt".
751 static __isl_give isl_set *stmt_extract_context(struct pet_stmt *stmt,
752 __isl_take isl_set *context)
754 int i;
756 for (i = 0; i < stmt->n_arg; ++i)
757 context = expr_extract_context(stmt->args[i], context);
759 context = expr_extract_context(stmt->body, context);
761 return context;
764 /* Construct a pet_scop that contains the given pet_stmt.
766 struct pet_scop *pet_scop_from_pet_stmt(isl_ctx *ctx, struct pet_stmt *stmt)
768 struct pet_scop *scop;
770 if (!stmt)
771 return NULL;
773 scop = scop_alloc(ctx, 1);
775 scop->context = stmt_extract_context(stmt, scop->context);
776 if (!scop->context)
777 goto error;
779 scop->stmts[0] = stmt;
781 return scop;
782 error:
783 pet_stmt_free(stmt);
784 pet_scop_free(scop);
785 return NULL;
788 /* Construct a pet_scop that contains the arrays and the statements
789 * in "scop1" and "scop2".
791 struct pet_scop *pet_scop_add(isl_ctx *ctx, struct pet_scop *scop1,
792 struct pet_scop *scop2)
794 int i;
795 struct pet_scop *scop;
797 if (!scop1 || !scop2)
798 goto error;
800 if (scop1->n_stmt == 0) {
801 pet_scop_free(scop1);
802 return scop2;
805 if (scop2->n_stmt == 0) {
806 pet_scop_free(scop2);
807 return scop1;
810 scop = scop_alloc(ctx, scop1->n_stmt + scop2->n_stmt);
811 if (!scop)
812 goto error;
814 scop->arrays = isl_calloc_array(ctx, struct pet_array *,
815 scop1->n_array + scop2->n_array);
816 if (!scop->arrays)
817 goto error;
818 scop->n_array = scop1->n_array + scop2->n_array;
820 for (i = 0; i < scop1->n_stmt; ++i) {
821 scop->stmts[i] = scop1->stmts[i];
822 scop1->stmts[i] = NULL;
825 for (i = 0; i < scop2->n_stmt; ++i) {
826 scop->stmts[scop1->n_stmt + i] = scop2->stmts[i];
827 scop2->stmts[i] = NULL;
830 for (i = 0; i < scop1->n_array; ++i) {
831 scop->arrays[i] = scop1->arrays[i];
832 scop1->arrays[i] = NULL;
835 for (i = 0; i < scop2->n_array; ++i) {
836 scop->arrays[scop1->n_array + i] = scop2->arrays[i];
837 scop2->arrays[i] = NULL;
840 scop = pet_scop_restrict_context(scop, isl_set_copy(scop1->context));
841 scop = pet_scop_restrict_context(scop, isl_set_copy(scop2->context));
843 pet_scop_free(scop1);
844 pet_scop_free(scop2);
845 return scop;
846 error:
847 pet_scop_free(scop1);
848 pet_scop_free(scop2);
849 return NULL;
852 void *pet_scop_free(struct pet_scop *scop)
854 int i;
856 if (!scop)
857 return NULL;
858 isl_set_free(scop->context);
859 isl_set_free(scop->context_value);
860 if (scop->arrays)
861 for (i = 0; i < scop->n_array; ++i)
862 pet_array_free(scop->arrays[i]);
863 free(scop->arrays);
864 if (scop->stmts)
865 for (i = 0; i < scop->n_stmt; ++i)
866 pet_stmt_free(scop->stmts[i]);
867 free(scop->stmts);
868 free(scop);
869 return NULL;
872 void pet_scop_dump(struct pet_scop *scop)
874 int i;
876 if (!scop)
877 return;
879 isl_set_dump(scop->context);
880 isl_set_dump(scop->context_value);
881 for (i = 0; i < scop->n_array; ++i)
882 pet_array_dump(scop->arrays[i]);
883 for (i = 0; i < scop->n_stmt; ++i)
884 pet_stmt_dump(scop->stmts[i]);
887 /* Return 1 if the two pet_arrays are equivalent.
889 * We don't compare element_size as this may be target dependent.
891 int pet_array_is_equal(struct pet_array *array1, struct pet_array *array2)
893 if (!array1 || !array2)
894 return 0;
896 if (!isl_set_is_equal(array1->context, array2->context))
897 return 0;
898 if (!isl_set_is_equal(array1->extent, array2->extent))
899 return 0;
900 if (!!array1->value_bounds != !!array2->value_bounds)
901 return 0;
902 if (array1->value_bounds &&
903 !isl_set_is_equal(array1->value_bounds, array2->value_bounds))
904 return 0;
905 if (strcmp(array1->element_type, array2->element_type))
906 return 0;
907 if (array1->live_out != array2->live_out)
908 return 0;
909 if (array1->uniquely_defined != array2->uniquely_defined)
910 return 0;
912 return 1;
915 /* Return 1 if the two pet_stmts are equivalent.
917 int pet_stmt_is_equal(struct pet_stmt *stmt1, struct pet_stmt *stmt2)
919 int i;
921 if (!stmt1 || !stmt2)
922 return 0;
924 if (stmt1->line != stmt2->line)
925 return 0;
926 if (!isl_set_is_equal(stmt1->domain, stmt2->domain))
927 return 0;
928 if (!isl_map_is_equal(stmt1->schedule, stmt2->schedule))
929 return 0;
930 if (!pet_expr_is_equal(stmt1->body, stmt2->body))
931 return 0;
932 if (stmt1->n_arg != stmt2->n_arg)
933 return 0;
934 for (i = 0; i < stmt1->n_arg; ++i) {
935 if (!pet_expr_is_equal(stmt1->args[i], stmt2->args[i]))
936 return 0;
939 return 1;
942 /* Return 1 if the two pet_scops are equivalent.
944 int pet_scop_is_equal(struct pet_scop *scop1, struct pet_scop *scop2)
946 int i;
948 if (!scop1 || !scop2)
949 return 0;
951 if (!isl_set_is_equal(scop1->context, scop2->context))
952 return 0;
953 if (!isl_set_is_equal(scop1->context_value, scop2->context_value))
954 return 0;
956 if (scop1->n_array != scop2->n_array)
957 return 0;
958 for (i = 0; i < scop1->n_array; ++i)
959 if (!pet_array_is_equal(scop1->arrays[i], scop2->arrays[i]))
960 return 0;
962 if (scop1->n_stmt != scop2->n_stmt)
963 return 0;
964 for (i = 0; i < scop1->n_stmt; ++i)
965 if (!pet_stmt_is_equal(scop1->stmts[i], scop2->stmts[i]))
966 return 0;
968 return 1;
971 /* Prefix the schedule of "stmt" with an extra dimension with constant
972 * value "pos".
974 struct pet_stmt *pet_stmt_prefix(struct pet_stmt *stmt, int pos)
976 if (!stmt)
977 return NULL;
979 stmt->schedule = isl_map_insert_dims(stmt->schedule, isl_dim_out, 0, 1);
980 stmt->schedule = isl_map_fix_si(stmt->schedule, isl_dim_out, 0, pos);
981 if (!stmt->schedule)
982 return pet_stmt_free(stmt);
984 return stmt;
987 /* Prefix the schedules of all statements in "scop" with an extra
988 * dimension with constant value "pos".
990 struct pet_scop *pet_scop_prefix(struct pet_scop *scop, int pos)
992 int i;
994 if (!scop)
995 return NULL;
997 for (i = 0; i < scop->n_stmt; ++i) {
998 scop->stmts[i] = pet_stmt_prefix(scop->stmts[i], pos);
999 if (!scop->stmts[i])
1000 return pet_scop_free(scop);
1003 return scop;
1006 /* Given a set with a parameter at "param_pos" that refers to the
1007 * iterator, "move" the iterator to the first set dimension.
1008 * That is, essentially equate the parameter to the first set dimension
1009 * and then project it out.
1011 * The first set dimension may however refer to a virtual iterator,
1012 * while the parameter refers to the "real" iterator.
1013 * We therefore need to take into account the mapping "iv_map", which
1014 * maps the virtual iterator to the real iterator.
1015 * In particular, we equate the set dimension to the input of the map
1016 * and the parameter to the output of the map and then project out
1017 * everything we don't need anymore.
1019 static __isl_give isl_set *internalize_iv(__isl_take isl_set *set,
1020 int param_pos, __isl_take isl_map *iv_map)
1022 isl_map *map;
1023 map = isl_map_from_domain(set);
1024 map = isl_map_add_dims(map, isl_dim_out, 1);
1025 map = isl_map_equate(map, isl_dim_in, 0, isl_dim_out, 0);
1026 iv_map = isl_map_align_params(iv_map, isl_map_get_space(map));
1027 map = isl_map_apply_range(map, iv_map);
1028 map = isl_map_equate(map, isl_dim_param, param_pos, isl_dim_out, 0);
1029 map = isl_map_project_out(map, isl_dim_param, param_pos, 1);
1030 return isl_map_domain(map);
1033 /* Data used in embed_access.
1034 * extend adds an iterator to the iteration domain
1035 * iv_map maps the virtual iterator to the real iterator
1036 * var_id represents the induction variable of the corresponding loop
1038 struct pet_embed_access {
1039 isl_map *extend;
1040 isl_map *iv_map;
1041 isl_id *var_id;
1044 /* Embed the access relation in an extra outer loop.
1046 * We first update the iteration domain to insert the extra dimension.
1048 * If the access refers to the induction variable, then it is
1049 * turned into an access to the set of integers with index (and value)
1050 * equal to the induction variable.
1052 * If the induction variable appears in the constraints (as a parameter),
1053 * then the parameter is equated to the newly introduced iteration
1054 * domain dimension and subsequently projected out.
1056 * Similarly, if the accessed array is a virtual array (with user
1057 * pointer equal to NULL), as created by create_test_access,
1058 * then it is extended along with the domain of the access.
1060 static __isl_give isl_map *embed_access(__isl_take isl_map *access,
1061 void *user)
1063 struct pet_embed_access *data = user;
1064 isl_id *array_id = NULL;
1065 int pos;
1067 access = update_domain(access, data->extend);
1069 if (isl_map_has_tuple_id(access, isl_dim_out))
1070 array_id = isl_map_get_tuple_id(access, isl_dim_out);
1071 if (array_id == data->var_id ||
1072 (array_id && !isl_id_get_user(array_id))) {
1073 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
1074 access = isl_map_equate(access,
1075 isl_dim_in, 0, isl_dim_out, 0);
1076 if (array_id == data->var_id)
1077 access = isl_map_apply_range(access,
1078 isl_map_copy(data->iv_map));
1079 else
1080 access = isl_map_set_tuple_id(access, isl_dim_out,
1081 isl_id_copy(array_id));
1083 isl_id_free(array_id);
1085 pos = isl_map_find_dim_by_id(access, isl_dim_param, data->var_id);
1086 if (pos >= 0) {
1087 isl_set *set = isl_map_wrap(access);
1088 set = internalize_iv(set, pos, isl_map_copy(data->iv_map));
1089 access = isl_set_unwrap(set);
1091 access = isl_map_set_dim_id(access, isl_dim_in, 0,
1092 isl_id_copy(data->var_id));
1094 return access;
1097 /* Embed all access relations in "expr" in an extra loop.
1098 * "extend" inserts an outer loop iterator in the iteration domains.
1099 * "iv_map" maps the virtual iterator to the real iterator
1100 * "var_id" represents the induction variable.
1102 static struct pet_expr *expr_embed(struct pet_expr *expr,
1103 __isl_take isl_map *extend, __isl_take isl_map *iv_map,
1104 __isl_keep isl_id *var_id)
1106 struct pet_embed_access data =
1107 { .extend = extend, .iv_map = iv_map, .var_id = var_id };
1109 expr = pet_expr_foreach_access(expr, &embed_access, &data);
1110 isl_map_free(iv_map);
1111 isl_map_free(extend);
1112 return expr;
1115 /* Embed the given pet_stmt in an extra outer loop with iteration domain
1116 * "dom" and schedule "sched". "var_id" represents the induction variable
1117 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
1118 * That is, it maps the iterator used in "dom" and the domain of "sched"
1119 * to the iterator that some of the parameters in "stmt" may refer to.
1121 * The iteration domain and schedule of the statement are updated
1122 * according to the iteration domain and schedule of the new loop.
1123 * If stmt->domain is a wrapped map, then the iteration domain
1124 * is the domain of this map, so we need to be careful to adjust
1125 * this domain.
1127 * If the induction variable appears in the constraints (as a parameter)
1128 * of the current iteration domain or the schedule of the statement,
1129 * then the parameter is equated to the newly introduced iteration
1130 * domain dimension and subsequently projected out.
1132 * Finally, all access relations are updated based on the extra loop.
1134 static struct pet_stmt *pet_stmt_embed(struct pet_stmt *stmt,
1135 __isl_take isl_set *dom, __isl_take isl_map *sched,
1136 __isl_take isl_map *iv_map, __isl_take isl_id *var_id)
1138 int i;
1139 int pos;
1140 isl_id *stmt_id;
1141 isl_space *dim;
1142 isl_map *extend;
1144 if (!stmt)
1145 goto error;
1147 if (isl_set_is_wrapping(stmt->domain)) {
1148 isl_map *map;
1149 isl_map *ext;
1150 isl_space *ran_dim;
1152 map = isl_set_unwrap(stmt->domain);
1153 stmt_id = isl_map_get_tuple_id(map, isl_dim_in);
1154 ran_dim = isl_space_range(isl_map_get_space(map));
1155 ext = isl_map_from_domain_and_range(isl_set_copy(dom),
1156 isl_set_universe(ran_dim));
1157 map = isl_map_flat_domain_product(ext, map);
1158 map = isl_map_set_tuple_id(map, isl_dim_in,
1159 isl_id_copy(stmt_id));
1160 dim = isl_space_domain(isl_map_get_space(map));
1161 stmt->domain = isl_map_wrap(map);
1162 } else {
1163 stmt_id = isl_set_get_tuple_id(stmt->domain);
1164 stmt->domain = isl_set_flat_product(isl_set_copy(dom),
1165 stmt->domain);
1166 stmt->domain = isl_set_set_tuple_id(stmt->domain,
1167 isl_id_copy(stmt_id));
1168 dim = isl_set_get_space(stmt->domain);
1171 pos = isl_set_find_dim_by_id(stmt->domain, isl_dim_param, var_id);
1172 if (pos >= 0)
1173 stmt->domain = internalize_iv(stmt->domain, pos,
1174 isl_map_copy(iv_map));
1176 stmt->schedule = isl_map_flat_product(sched, stmt->schedule);
1177 stmt->schedule = isl_map_set_tuple_id(stmt->schedule,
1178 isl_dim_in, stmt_id);
1180 pos = isl_map_find_dim_by_id(stmt->schedule, isl_dim_param, var_id);
1181 if (pos >= 0) {
1182 isl_set *set = isl_map_wrap(stmt->schedule);
1183 set = internalize_iv(set, pos, isl_map_copy(iv_map));
1184 stmt->schedule = isl_set_unwrap(set);
1187 dim = isl_space_map_from_set(dim);
1188 extend = isl_map_identity(dim);
1189 extend = isl_map_remove_dims(extend, isl_dim_in, 0, 1);
1190 extend = isl_map_set_tuple_id(extend, isl_dim_in,
1191 isl_map_get_tuple_id(extend, isl_dim_out));
1192 for (i = 0; i < stmt->n_arg; ++i)
1193 stmt->args[i] = expr_embed(stmt->args[i], isl_map_copy(extend),
1194 isl_map_copy(iv_map), var_id);
1195 stmt->body = expr_embed(stmt->body, extend, iv_map, var_id);
1197 isl_set_free(dom);
1198 isl_id_free(var_id);
1200 for (i = 0; i < stmt->n_arg; ++i)
1201 if (!stmt->args[i])
1202 return pet_stmt_free(stmt);
1203 if (!stmt->domain || !stmt->schedule || !stmt->body)
1204 return pet_stmt_free(stmt);
1205 return stmt;
1206 error:
1207 isl_set_free(dom);
1208 isl_map_free(sched);
1209 isl_map_free(iv_map);
1210 isl_id_free(var_id);
1211 return NULL;
1214 /* Embed the given pet_array in an extra outer loop with iteration domain
1215 * "dom".
1216 * This embedding only has an effect on virtual arrays (those with
1217 * user pointer equal to NULL), which need to be extended along with
1218 * the iteration domain.
1220 static struct pet_array *pet_array_embed(struct pet_array *array,
1221 __isl_take isl_set *dom)
1223 isl_id *array_id = NULL;
1225 if (!array)
1226 goto error;
1228 if (isl_set_has_tuple_id(array->extent))
1229 array_id = isl_set_get_tuple_id(array->extent);
1231 if (array_id && !isl_id_get_user(array_id)) {
1232 array->extent = isl_set_flat_product(dom, array->extent);
1233 array->extent = isl_set_set_tuple_id(array->extent, array_id);
1234 } else {
1235 isl_set_free(dom);
1236 isl_id_free(array_id);
1239 return array;
1240 error:
1241 isl_set_free(dom);
1242 return NULL;
1245 /* Project out all unnamed parameters from "set" and return the result.
1247 static __isl_give isl_set *set_project_out_unnamed_params(
1248 __isl_take isl_set *set)
1250 int i, n;
1252 n = isl_set_dim(set, isl_dim_param);
1253 for (i = n - 1; i >= 0; --i) {
1254 if (isl_set_has_dim_name(set, isl_dim_param, i))
1255 continue;
1256 set = isl_set_project_out(set, isl_dim_param, i, 1);
1259 return set;
1262 /* Update the context with respect to an embedding into a loop
1263 * with iteration domain "dom" and induction variable "id".
1264 * "iv_map" maps a possibly virtual iterator (used in "dom")
1265 * to the real iterator (parameter "id").
1267 * If the current context is independent of "id", we don't need
1268 * to do anything.
1269 * Otherwise, a parameter value is invalid for the embedding if
1270 * any of the corresponding iterator values is invalid.
1271 * That is, a parameter value is valid only if all the corresponding
1272 * iterator values are valid.
1273 * We therefore compute the set of parameters
1275 * forall i in dom : valid (i)
1277 * or
1279 * not exists i in dom : not valid(i)
1281 * i.e.,
1283 * not exists i in dom \ valid(i)
1285 * Before we subtract valid(i) from dom, we first need to map
1286 * the real iterator to the virtual iterator.
1288 * If there are any unnamed parameters in "dom", then we consider
1289 * a parameter value to be valid if it is valid for any value of those
1290 * unnamed parameters. They are therefore projected out at the end.
1292 static __isl_give isl_set *context_embed(__isl_take isl_set *context,
1293 __isl_keep isl_set *dom, __isl_keep isl_map *iv_map,
1294 __isl_keep isl_id *id)
1296 int pos;
1298 pos = isl_set_find_dim_by_id(context, isl_dim_param, id);
1299 if (pos < 0)
1300 return context;
1302 context = isl_set_from_params(context);
1303 context = isl_set_add_dims(context, isl_dim_set, 1);
1304 context = isl_set_equate(context, isl_dim_param, pos, isl_dim_set, 0);
1305 context = isl_set_project_out(context, isl_dim_param, pos, 1);
1306 context = isl_set_apply(context, isl_map_reverse(isl_map_copy(iv_map)));
1307 context = isl_set_subtract(isl_set_copy(dom), context);
1308 context = isl_set_params(context);
1309 context = isl_set_complement(context);
1310 context = set_project_out_unnamed_params(context);
1311 return context;
1314 /* Embed all statements and arrays in "scop" in an extra outer loop
1315 * with iteration domain "dom" and schedule "sched".
1316 * "id" represents the induction variable of the loop.
1317 * "iv_map" maps a possibly virtual iterator to the real iterator.
1318 * That is, it maps the iterator used in "dom" and the domain of "sched"
1319 * to the iterator that some of the parameters in "scop" may refer to.
1321 struct pet_scop *pet_scop_embed(struct pet_scop *scop, __isl_take isl_set *dom,
1322 __isl_take isl_map *sched, __isl_take isl_map *iv_map,
1323 __isl_take isl_id *id)
1325 int i;
1327 if (!scop)
1328 goto error;
1330 scop->context = context_embed(scop->context, dom, iv_map, id);
1331 if (!scop->context)
1332 goto error;
1334 for (i = 0; i < scop->n_stmt; ++i) {
1335 scop->stmts[i] = pet_stmt_embed(scop->stmts[i],
1336 isl_set_copy(dom), isl_map_copy(sched),
1337 isl_map_copy(iv_map), isl_id_copy(id));
1338 if (!scop->stmts[i])
1339 goto error;
1342 for (i = 0; i < scop->n_array; ++i) {
1343 scop->arrays[i] = pet_array_embed(scop->arrays[i],
1344 isl_set_copy(dom));
1345 if (!scop->arrays[i])
1346 goto error;
1349 isl_set_free(dom);
1350 isl_map_free(sched);
1351 isl_map_free(iv_map);
1352 isl_id_free(id);
1353 return scop;
1354 error:
1355 isl_set_free(dom);
1356 isl_map_free(sched);
1357 isl_map_free(iv_map);
1358 isl_id_free(id);
1359 return pet_scop_free(scop);
1362 /* Add extra conditions on the parameters to iteration domain of "stmt".
1364 static struct pet_stmt *stmt_restrict(struct pet_stmt *stmt,
1365 __isl_take isl_set *cond)
1367 if (!stmt)
1368 goto error;
1370 stmt->domain = isl_set_intersect_params(stmt->domain, cond);
1372 return stmt;
1373 error:
1374 isl_set_free(cond);
1375 return pet_stmt_free(stmt);
1378 /* Add extra conditions on the parameters to all iteration domains.
1380 * A parameter value is valid for the result if it was valid
1381 * for the original scop and satisfies "cond" or if it does
1382 * not satisfy "cond" as in this case the scop is not executed
1383 * and the original constraints on the parameters are irrelevant.
1385 struct pet_scop *pet_scop_restrict(struct pet_scop *scop,
1386 __isl_take isl_set *cond)
1388 int i;
1390 if (!scop)
1391 goto error;
1393 scop->context = isl_set_intersect(scop->context, isl_set_copy(cond));
1394 scop->context = isl_set_union(scop->context,
1395 isl_set_complement(isl_set_copy(cond)));
1396 scop->context = isl_set_coalesce(scop->context);
1397 scop->context = set_project_out_unnamed_params(scop->context);
1398 if (!scop->context)
1399 goto error;
1401 for (i = 0; i < scop->n_stmt; ++i) {
1402 scop->stmts[i] = stmt_restrict(scop->stmts[i],
1403 isl_set_copy(cond));
1404 if (!scop->stmts[i])
1405 goto error;
1408 isl_set_free(cond);
1409 return scop;
1410 error:
1411 isl_set_free(cond);
1412 return pet_scop_free(scop);
1415 /* Construct a map that inserts a filter value with name "id" and value
1416 * "satisfied" in the list of filter values embedded in the set space "space".
1418 * If "space" does not contain any filter values yet, we first create
1419 * a map that inserts 0 filter values, i.e.,
1421 * space -> [space -> []]
1423 * We can now assume that space is of the form [dom -> [filters]]
1424 * We construct an identity mapping on dom and a mapping on filters
1425 * that inserts the new filter
1427 * dom -> dom
1428 * [filters] -> [satisfied, filters]
1430 * and then compute the cross product
1432 * [dom -> [filters]] -> [dom -> [satisfied, filters]]
1434 static __isl_give isl_map *insert_filter_map(__isl_take isl_space *space,
1435 __isl_take isl_id *id, int satisfied)
1437 isl_space *space2;
1438 isl_map *map, *map_dom, *map_ran;
1439 isl_set *dom;
1441 if (isl_space_is_wrapping(space)) {
1442 space2 = isl_space_map_from_set(isl_space_copy(space));
1443 map = isl_map_identity(space2);
1444 space = isl_space_unwrap(space);
1445 } else {
1446 space = isl_space_from_domain(space);
1447 map = isl_map_universe(isl_space_copy(space));
1448 map = isl_map_reverse(isl_map_domain_map(map));
1451 space2 = isl_space_domain(isl_space_copy(space));
1452 map_dom = isl_map_identity(isl_space_map_from_set(space2));
1453 space = isl_space_range(space);
1454 map_ran = isl_map_identity(isl_space_map_from_set(space));
1455 map_ran = isl_map_insert_dims(map_ran, isl_dim_out, 0, 1);
1456 map_ran = isl_map_set_dim_id(map_ran, isl_dim_out, 0, id);
1457 map_ran = isl_map_fix_si(map_ran, isl_dim_out, 0, satisfied);
1459 map = isl_map_apply_range(map, isl_map_product(map_dom, map_ran));
1461 return map;
1464 /* Insert an argument expression corresponding to "test" in front
1465 * of the list of arguments described by *n_arg and *args.
1467 static int args_insert_access(unsigned *n_arg, struct pet_expr ***args,
1468 __isl_keep isl_map *test)
1470 int i;
1471 isl_ctx *ctx = isl_map_get_ctx(test);
1473 if (!test)
1474 return -1;
1476 if (!*args) {
1477 *args = isl_calloc_array(ctx, struct pet_expr *, 1);
1478 if (!*args)
1479 return -1;
1480 } else {
1481 struct pet_expr **ext;
1482 ext = isl_calloc_array(ctx, struct pet_expr *, 1 + *n_arg);
1483 if (!ext)
1484 return -1;
1485 for (i = 0; i < *n_arg; ++i)
1486 ext[1 + i] = (*args)[i];
1487 free(*args);
1488 *args = ext;
1490 (*n_arg)++;
1491 (*args)[0] = pet_expr_from_access(isl_map_copy(test));
1492 if (!(*args)[0])
1493 return -1;
1495 return 0;
1498 /* Make the statement "stmt" depend on the value of "test"
1499 * being equal to "satisfied" by adjusting stmt->domain.
1501 * The domain of "test" corresponds to the (zero or more) outer dimensions
1502 * of the iteration domain.
1504 * We insert an argument corresponding to a read to "test"
1505 * from the iteration domain of "stmt" in front of the list of arguments.
1506 * We also insert a corresponding output dimension in the wrapped
1507 * map contained in stmt->domain, with value set to "satisfied".
1509 static struct pet_stmt *stmt_filter(struct pet_stmt *stmt,
1510 __isl_take isl_map *test, int satisfied)
1512 int i;
1513 isl_id *id;
1514 isl_ctx *ctx;
1515 isl_map *map, *add_dom;
1516 isl_space *space;
1517 isl_set *dom;
1518 int n_test_dom;
1520 if (!stmt || !test)
1521 goto error;
1523 id = isl_map_get_tuple_id(test, isl_dim_out);
1524 map = insert_filter_map(isl_set_get_space(stmt->domain), id, satisfied);
1525 stmt->domain = isl_set_apply(stmt->domain, map);
1527 space = isl_space_unwrap(isl_set_get_space(stmt->domain));
1528 dom = isl_set_universe(isl_space_domain(space));
1529 n_test_dom = isl_map_dim(test, isl_dim_in);
1530 add_dom = isl_map_from_range(dom);
1531 add_dom = isl_map_add_dims(add_dom, isl_dim_in, n_test_dom);
1532 for (i = 0; i < n_test_dom; ++i)
1533 add_dom = isl_map_equate(add_dom, isl_dim_in, i,
1534 isl_dim_out, i);
1535 test = isl_map_apply_domain(test, add_dom);
1537 if (args_insert_access(&stmt->n_arg, &stmt->args, test) < 0)
1538 goto error;
1540 isl_map_free(test);
1541 return stmt;
1542 error:
1543 isl_map_free(test);
1544 return pet_stmt_free(stmt);
1547 /* Make all statements in "scop" depend on the value of "test"
1548 * being equal to "satisfied" by adjusting their domains.
1550 struct pet_scop *pet_scop_filter(struct pet_scop *scop,
1551 __isl_take isl_map *test, int satisfied)
1553 int i;
1555 if (!scop)
1556 goto error;
1558 for (i = 0; i < scop->n_stmt; ++i) {
1559 scop->stmts[i] = stmt_filter(scop->stmts[i],
1560 isl_map_copy(test), satisfied);
1561 if (!scop->stmts[i])
1562 goto error;
1565 isl_map_free(test);
1566 return scop;
1567 error:
1568 isl_map_free(test);
1569 return pet_scop_free(scop);
1572 /* Add all parameters in "expr" to "dim" and return the result.
1574 static __isl_give isl_space *expr_collect_params(struct pet_expr *expr,
1575 __isl_take isl_space *dim)
1577 int i;
1579 if (!expr)
1580 goto error;
1581 for (i = 0; i < expr->n_arg; ++i)
1583 dim = expr_collect_params(expr->args[i], dim);
1585 if (expr->type == pet_expr_access)
1586 dim = isl_space_align_params(dim,
1587 isl_map_get_space(expr->acc.access));
1589 return dim;
1590 error:
1591 isl_space_free(dim);
1592 return pet_expr_free(expr);
1595 /* Add all parameters in "stmt" to "dim" and return the result.
1597 static __isl_give isl_space *stmt_collect_params(struct pet_stmt *stmt,
1598 __isl_take isl_space *dim)
1600 if (!stmt)
1601 goto error;
1603 dim = isl_space_align_params(dim, isl_set_get_space(stmt->domain));
1604 dim = isl_space_align_params(dim, isl_map_get_space(stmt->schedule));
1605 dim = expr_collect_params(stmt->body, dim);
1607 return dim;
1608 error:
1609 isl_space_free(dim);
1610 return pet_stmt_free(stmt);
1613 /* Add all parameters in "array" to "dim" and return the result.
1615 static __isl_give isl_space *array_collect_params(struct pet_array *array,
1616 __isl_take isl_space *dim)
1618 if (!array)
1619 goto error;
1621 dim = isl_space_align_params(dim, isl_set_get_space(array->context));
1622 dim = isl_space_align_params(dim, isl_set_get_space(array->extent));
1624 return dim;
1625 error:
1626 isl_space_free(dim);
1627 return pet_array_free(array);
1630 /* Add all parameters in "scop" to "dim" and return the result.
1632 static __isl_give isl_space *scop_collect_params(struct pet_scop *scop,
1633 __isl_take isl_space *dim)
1635 int i;
1637 if (!scop)
1638 goto error;
1640 for (i = 0; i < scop->n_array; ++i)
1641 dim = array_collect_params(scop->arrays[i], dim);
1643 for (i = 0; i < scop->n_stmt; ++i)
1644 dim = stmt_collect_params(scop->stmts[i], dim);
1646 return dim;
1647 error:
1648 isl_space_free(dim);
1649 return pet_scop_free(scop);
1652 /* Add all parameters in "dim" to all access relations in "expr".
1654 static struct pet_expr *expr_propagate_params(struct pet_expr *expr,
1655 __isl_take isl_space *dim)
1657 int i;
1659 if (!expr)
1660 goto error;
1662 for (i = 0; i < expr->n_arg; ++i) {
1663 expr->args[i] =
1664 expr_propagate_params(expr->args[i],
1665 isl_space_copy(dim));
1666 if (!expr->args[i])
1667 goto error;
1670 if (expr->type == pet_expr_access) {
1671 expr->acc.access = isl_map_align_params(expr->acc.access,
1672 isl_space_copy(dim));
1673 if (!expr->acc.access)
1674 goto error;
1677 isl_space_free(dim);
1678 return expr;
1679 error:
1680 isl_space_free(dim);
1681 return pet_expr_free(expr);
1684 /* Add all parameters in "dim" to the domain, schedule and
1685 * all access relations in "stmt".
1687 static struct pet_stmt *stmt_propagate_params(struct pet_stmt *stmt,
1688 __isl_take isl_space *dim)
1690 if (!stmt)
1691 goto error;
1693 stmt->domain = isl_set_align_params(stmt->domain, isl_space_copy(dim));
1694 stmt->schedule = isl_map_align_params(stmt->schedule,
1695 isl_space_copy(dim));
1696 stmt->body = expr_propagate_params(stmt->body, isl_space_copy(dim));
1698 if (!stmt->domain || !stmt->schedule || !stmt->body)
1699 goto error;
1701 isl_space_free(dim);
1702 return stmt;
1703 error:
1704 isl_space_free(dim);
1705 return pet_stmt_free(stmt);
1708 /* Add all parameters in "dim" to "array".
1710 static struct pet_array *array_propagate_params(struct pet_array *array,
1711 __isl_take isl_space *dim)
1713 if (!array)
1714 goto error;
1716 array->context = isl_set_align_params(array->context,
1717 isl_space_copy(dim));
1718 array->extent = isl_set_align_params(array->extent,
1719 isl_space_copy(dim));
1720 if (array->value_bounds) {
1721 array->value_bounds = isl_set_align_params(array->value_bounds,
1722 isl_space_copy(dim));
1723 if (!array->value_bounds)
1724 goto error;
1727 if (!array->context || !array->extent)
1728 goto error;
1730 isl_space_free(dim);
1731 return array;
1732 error:
1733 isl_space_free(dim);
1734 return pet_array_free(array);
1737 /* Add all parameters in "dim" to "scop".
1739 static struct pet_scop *scop_propagate_params(struct pet_scop *scop,
1740 __isl_take isl_space *dim)
1742 int i;
1744 if (!scop)
1745 goto error;
1747 for (i = 0; i < scop->n_array; ++i) {
1748 scop->arrays[i] = array_propagate_params(scop->arrays[i],
1749 isl_space_copy(dim));
1750 if (!scop->arrays[i])
1751 goto error;
1754 for (i = 0; i < scop->n_stmt; ++i) {
1755 scop->stmts[i] = stmt_propagate_params(scop->stmts[i],
1756 isl_space_copy(dim));
1757 if (!scop->stmts[i])
1758 goto error;
1761 isl_space_free(dim);
1762 return scop;
1763 error:
1764 isl_space_free(dim);
1765 return pet_scop_free(scop);
1768 /* Update all isl_sets and isl_maps in "scop" such that they all
1769 * have the same parameters.
1771 struct pet_scop *pet_scop_align_params(struct pet_scop *scop)
1773 isl_space *dim;
1775 if (!scop)
1776 return NULL;
1778 dim = isl_set_get_space(scop->context);
1779 dim = scop_collect_params(scop, dim);
1781 scop->context = isl_set_align_params(scop->context, isl_space_copy(dim));
1782 scop = scop_propagate_params(scop, dim);
1784 return scop;
1787 /* Check if the given access relation accesses a (0D) array that corresponds
1788 * to one of the parameters in "dim". If so, replace the array access
1789 * by an access to the set of integers with as index (and value)
1790 * that parameter.
1792 static __isl_give isl_map *access_detect_parameter(__isl_take isl_map *access,
1793 __isl_take isl_space *dim)
1795 isl_id *array_id = NULL;
1796 int pos = -1;
1798 if (isl_map_has_tuple_id(access, isl_dim_out)) {
1799 array_id = isl_map_get_tuple_id(access, isl_dim_out);
1800 pos = isl_space_find_dim_by_id(dim, isl_dim_param, array_id);
1802 isl_space_free(dim);
1804 if (pos < 0) {
1805 isl_id_free(array_id);
1806 return access;
1809 pos = isl_map_find_dim_by_id(access, isl_dim_param, array_id);
1810 if (pos < 0) {
1811 access = isl_map_insert_dims(access, isl_dim_param, 0, 1);
1812 access = isl_map_set_dim_id(access, isl_dim_param, 0, array_id);
1813 pos = 0;
1814 } else
1815 isl_id_free(array_id);
1817 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
1818 access = isl_map_equate(access, isl_dim_param, pos, isl_dim_out, 0);
1820 return access;
1823 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1824 * in "dim" by a value equal to the corresponding parameter.
1826 static struct pet_expr *expr_detect_parameter_accesses(struct pet_expr *expr,
1827 __isl_take isl_space *dim)
1829 int i;
1831 if (!expr)
1832 goto error;
1834 for (i = 0; i < expr->n_arg; ++i) {
1835 expr->args[i] =
1836 expr_detect_parameter_accesses(expr->args[i],
1837 isl_space_copy(dim));
1838 if (!expr->args[i])
1839 goto error;
1842 if (expr->type == pet_expr_access) {
1843 expr->acc.access = access_detect_parameter(expr->acc.access,
1844 isl_space_copy(dim));
1845 if (!expr->acc.access)
1846 goto error;
1849 isl_space_free(dim);
1850 return expr;
1851 error:
1852 isl_space_free(dim);
1853 return pet_expr_free(expr);
1856 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1857 * in "dim" by a value equal to the corresponding parameter.
1859 static struct pet_stmt *stmt_detect_parameter_accesses(struct pet_stmt *stmt,
1860 __isl_take isl_space *dim)
1862 if (!stmt)
1863 goto error;
1865 stmt->body = expr_detect_parameter_accesses(stmt->body,
1866 isl_space_copy(dim));
1868 if (!stmt->domain || !stmt->schedule || !stmt->body)
1869 goto error;
1871 isl_space_free(dim);
1872 return stmt;
1873 error:
1874 isl_space_free(dim);
1875 return pet_stmt_free(stmt);
1878 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1879 * in "dim" by a value equal to the corresponding parameter.
1881 static struct pet_scop *scop_detect_parameter_accesses(struct pet_scop *scop,
1882 __isl_take isl_space *dim)
1884 int i;
1886 if (!scop)
1887 goto error;
1889 for (i = 0; i < scop->n_stmt; ++i) {
1890 scop->stmts[i] = stmt_detect_parameter_accesses(scop->stmts[i],
1891 isl_space_copy(dim));
1892 if (!scop->stmts[i])
1893 goto error;
1896 isl_space_free(dim);
1897 return scop;
1898 error:
1899 isl_space_free(dim);
1900 return pet_scop_free(scop);
1903 /* Replace all accesses to (0D) arrays that correspond to any of
1904 * the parameters used in "scop" by a value equal
1905 * to the corresponding parameter.
1907 struct pet_scop *pet_scop_detect_parameter_accesses(struct pet_scop *scop)
1909 isl_space *dim;
1911 if (!scop)
1912 return NULL;
1914 dim = isl_set_get_space(scop->context);
1915 dim = scop_collect_params(scop, dim);
1917 scop = scop_detect_parameter_accesses(scop, dim);
1919 return scop;
1922 /* Add all read access relations (if "read" is set) and/or all write
1923 * access relations (if "write" is set) to "accesses" and return the result.
1925 static __isl_give isl_union_map *expr_collect_accesses(struct pet_expr *expr,
1926 int read, int write, __isl_take isl_union_map *accesses)
1928 int i;
1929 isl_id *id;
1930 isl_space *dim;
1932 if (!expr)
1933 return NULL;
1935 for (i = 0; i < expr->n_arg; ++i)
1936 accesses = expr_collect_accesses(expr->args[i],
1937 read, write, accesses);
1939 if (expr->type == pet_expr_access &&
1940 isl_map_has_tuple_id(expr->acc.access, isl_dim_out) &&
1941 ((read && expr->acc.read) || (write && expr->acc.write)))
1942 accesses = isl_union_map_add_map(accesses,
1943 isl_map_copy(expr->acc.access));
1945 return accesses;
1948 /* Collect and return all read access relations (if "read" is set)
1949 * and/or all write * access relations (if "write" is set) in "stmt".
1951 static __isl_give isl_union_map *stmt_collect_accesses(struct pet_stmt *stmt,
1952 int read, int write, __isl_take isl_space *dim)
1954 isl_union_map *accesses;
1956 if (!stmt)
1957 return NULL;
1959 accesses = isl_union_map_empty(dim);
1960 accesses = expr_collect_accesses(stmt->body, read, write, accesses);
1961 accesses = isl_union_map_intersect_domain(accesses,
1962 isl_union_set_from_set(isl_set_copy(stmt->domain)));
1964 return accesses;
1967 /* Collect and return all read access relations (if "read" is set)
1968 * and/or all write * access relations (if "write" is set) in "scop".
1970 static __isl_give isl_union_map *scop_collect_accesses(struct pet_scop *scop,
1971 int read, int write)
1973 int i;
1974 isl_union_map *accesses;
1976 if (!scop)
1977 return NULL;
1979 accesses = isl_union_map_empty(isl_set_get_space(scop->context));
1981 for (i = 0; i < scop->n_stmt; ++i) {
1982 isl_union_map *accesses_i;
1983 isl_space *dim = isl_set_get_space(scop->context);
1984 accesses_i = stmt_collect_accesses(scop->stmts[i],
1985 read, write, dim);
1986 accesses = isl_union_map_union(accesses, accesses_i);
1989 return accesses;
1992 __isl_give isl_union_map *pet_scop_collect_reads(struct pet_scop *scop)
1994 return scop_collect_accesses(scop, 1, 0);
1997 __isl_give isl_union_map *pet_scop_collect_writes(struct pet_scop *scop)
1999 return scop_collect_accesses(scop, 0, 1);
2002 /* Collect and return the union of iteration domains in "scop".
2004 __isl_give isl_union_set *pet_scop_collect_domains(struct pet_scop *scop)
2006 int i;
2007 isl_set *domain_i;
2008 isl_union_set *domain;
2010 if (!scop)
2011 return NULL;
2013 domain = isl_union_set_empty(isl_set_get_space(scop->context));
2015 for (i = 0; i < scop->n_stmt; ++i) {
2016 domain_i = isl_set_copy(scop->stmts[i]->domain);
2017 domain = isl_union_set_add_set(domain, domain_i);
2020 return domain;
2023 /* Collect and return the schedules of the statements in "scop".
2024 * The range is normalized to the maximal number of scheduling
2025 * dimensions.
2027 __isl_give isl_union_map *pet_scop_collect_schedule(struct pet_scop *scop)
2029 int i, j;
2030 isl_map *schedule_i;
2031 isl_union_map *schedule;
2032 int depth, max_depth = 0;
2034 if (!scop)
2035 return NULL;
2037 schedule = isl_union_map_empty(isl_set_get_space(scop->context));
2039 for (i = 0; i < scop->n_stmt; ++i) {
2040 depth = isl_map_dim(scop->stmts[i]->schedule, isl_dim_out);
2041 if (depth > max_depth)
2042 max_depth = depth;
2045 for (i = 0; i < scop->n_stmt; ++i) {
2046 schedule_i = isl_map_copy(scop->stmts[i]->schedule);
2047 depth = isl_map_dim(schedule_i, isl_dim_out);
2048 schedule_i = isl_map_add_dims(schedule_i, isl_dim_out,
2049 max_depth - depth);
2050 for (j = depth; j < max_depth; ++j)
2051 schedule_i = isl_map_fix_si(schedule_i,
2052 isl_dim_out, j, 0);
2053 schedule = isl_union_map_add_map(schedule, schedule_i);
2056 return schedule;
2059 /* Does expression "expr" write to "id"?
2061 static int expr_writes(struct pet_expr *expr, __isl_keep isl_id *id)
2063 int i;
2064 isl_id *write_id;
2066 for (i = 0; i < expr->n_arg; ++i) {
2067 int writes = expr_writes(expr->args[i], id);
2068 if (writes < 0 || writes)
2069 return writes;
2072 if (expr->type != pet_expr_access)
2073 return 0;
2074 if (!expr->acc.write)
2075 return 0;
2076 if (!isl_map_has_tuple_id(expr->acc.access, isl_dim_out))
2077 return 0;
2079 write_id = isl_map_get_tuple_id(expr->acc.access, isl_dim_out);
2080 isl_id_free(write_id);
2082 if (!write_id)
2083 return -1;
2085 return write_id == id;
2088 /* Does statement "stmt" write to "id"?
2090 static int stmt_writes(struct pet_stmt *stmt, __isl_keep isl_id *id)
2092 return expr_writes(stmt->body, id);
2095 /* Is there any write access in "scop" that accesses "id"?
2097 int pet_scop_writes(struct pet_scop *scop, __isl_keep isl_id *id)
2099 int i;
2101 if (!scop)
2102 return -1;
2104 for (i = 0; i < scop->n_stmt; ++i) {
2105 int writes = stmt_writes(scop->stmts[i], id);
2106 if (writes < 0 || writes)
2107 return writes;
2110 return 0;
2113 /* Reset the user pointer on all parameter ids in "set".
2115 static __isl_give isl_set *set_anonymize(__isl_take isl_set *set)
2117 int i, n;
2119 n = isl_set_dim(set, isl_dim_param);
2120 for (i = 0; i < n; ++i) {
2121 isl_id *id = isl_set_get_dim_id(set, isl_dim_param, i);
2122 const char *name = isl_id_get_name(id);
2123 set = isl_set_set_dim_name(set, isl_dim_param, i, name);
2124 isl_id_free(id);
2127 return set;
2130 /* Reset the user pointer on all parameter ids in "map".
2132 static __isl_give isl_map *map_anonymize(__isl_take isl_map *map)
2134 int i, n;
2136 n = isl_map_dim(map, isl_dim_param);
2137 for (i = 0; i < n; ++i) {
2138 isl_id *id = isl_map_get_dim_id(map, isl_dim_param, i);
2139 const char *name = isl_id_get_name(id);
2140 map = isl_map_set_dim_name(map, isl_dim_param, i, name);
2141 isl_id_free(id);
2144 return map;
2147 /* Reset the user pointer on all parameter ids in "array".
2149 static struct pet_array *array_anonymize(struct pet_array *array)
2151 if (!array)
2152 return NULL;
2154 array->context = set_anonymize(array->context);
2155 array->extent = set_anonymize(array->extent);
2156 if (!array->context || !array->extent)
2157 return pet_array_free(array);
2159 return array;
2162 /* Reset the user pointer on all parameter ids in "access".
2164 static __isl_give isl_map *access_anonymize(__isl_take isl_map *access,
2165 void *user)
2167 access = map_anonymize(access);
2169 return access;
2172 /* Reset the user pointer on all parameter ids in "stmt".
2174 static struct pet_stmt *stmt_anonymize(struct pet_stmt *stmt)
2176 int i;
2177 isl_space *space;
2178 isl_set *domain;
2180 if (!stmt)
2181 return NULL;
2183 stmt->domain = set_anonymize(stmt->domain);
2184 stmt->schedule = map_anonymize(stmt->schedule);
2185 if (!stmt->domain || !stmt->schedule)
2186 return pet_stmt_free(stmt);
2188 for (i = 0; i < stmt->n_arg; ++i) {
2189 stmt->args[i] = pet_expr_foreach_access(stmt->args[i],
2190 &access_anonymize, NULL);
2191 if (!stmt->args[i])
2192 return pet_stmt_free(stmt);
2195 stmt->body = pet_expr_foreach_access(stmt->body,
2196 &access_anonymize, NULL);
2197 if (!stmt->body)
2198 return pet_stmt_free(stmt);
2200 return stmt;
2203 /* Reset the user pointer on all parameter ids in "scop".
2205 struct pet_scop *pet_scop_anonymize(struct pet_scop *scop)
2207 int i;
2209 if (!scop)
2210 return NULL;
2212 scop->context = set_anonymize(scop->context);
2213 scop->context_value = set_anonymize(scop->context_value);
2214 if (!scop->context || !scop->context_value)
2215 return pet_scop_free(scop);
2217 for (i = 0; i < scop->n_array; ++i) {
2218 scop->arrays[i] = array_anonymize(scop->arrays[i]);
2219 if (!scop->arrays[i])
2220 return pet_scop_free(scop);
2223 for (i = 0; i < scop->n_stmt; ++i) {
2224 scop->stmts[i] = stmt_anonymize(scop->stmts[i]);
2225 if (!scop->stmts[i])
2226 return pet_scop_free(scop);
2229 return scop;
2232 /* Given a set "domain", return a wrapped relation with the given set
2233 * as domain and a range of dimension "n_arg", where each coordinate
2234 * is either unbounded or, if the corresponding element of args is of
2235 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
2237 static __isl_give isl_set *apply_value_bounds(__isl_take isl_set *domain,
2238 unsigned n_arg, struct pet_expr **args,
2239 __isl_keep isl_union_map *value_bounds)
2241 int i;
2242 isl_map *map;
2243 isl_space *space;
2244 isl_ctx *ctx = isl_set_get_ctx(domain);
2246 map = isl_map_from_domain(domain);
2247 space = isl_map_get_space(map);
2248 space = isl_space_add_dims(space, isl_dim_out, 1);
2250 for (i = 0; i < n_arg; ++i) {
2251 isl_map *map_i;
2252 struct pet_expr *arg = args[i];
2253 isl_id *id;
2254 isl_space *space2;
2256 map_i = isl_map_universe(isl_space_copy(space));
2257 if (arg->type == pet_expr_access) {
2258 isl_map *vb;
2259 id = isl_map_get_tuple_id(arg->acc.access, isl_dim_out);
2260 space2 = isl_space_alloc(ctx, 0, 0, 1);
2261 space2 = isl_space_set_tuple_id(space2, isl_dim_in, id);
2262 vb = isl_union_map_extract_map(value_bounds, space2);
2263 if (!isl_map_plain_is_empty(vb))
2264 map_i = isl_map_intersect_range(map_i,
2265 isl_map_range(vb));
2266 else
2267 isl_map_free(vb);
2269 map = isl_map_flat_range_product(map, map_i);
2271 isl_space_free(space);
2273 return isl_map_wrap(map);
2276 /* Data used in access_gist() callback.
2278 struct pet_access_gist_data {
2279 isl_set *domain;
2280 isl_union_map *value_bounds;
2283 /* Given an expression "expr" of type pet_expr_access, compute
2284 * the gist of the associated access relation with respect to
2285 * data->domain and the bounds on the values of the arguments
2286 * of the expression.
2288 static struct pet_expr *access_gist(struct pet_expr *expr, void *user)
2290 struct pet_access_gist_data *data = user;
2291 isl_set *domain;
2293 domain = isl_set_copy(data->domain);
2294 if (expr->n_arg > 0)
2295 domain = apply_value_bounds(domain, expr->n_arg, expr->args,
2296 data->value_bounds);
2298 expr->acc.access = isl_map_gist_domain(expr->acc.access, domain);
2299 if (!expr->acc.access)
2300 return pet_expr_free(expr);
2302 return expr;
2305 /* Compute the gist of the iteration domain and all access relations
2306 * of "stmt" based on the constraints on the parameters specified by "context"
2307 * and the constraints on the values of nested accesses specified
2308 * by "value_bounds".
2310 static struct pet_stmt *stmt_gist(struct pet_stmt *stmt,
2311 __isl_keep isl_set *context, __isl_keep isl_union_map *value_bounds)
2313 int i;
2314 isl_space *space;
2315 isl_set *domain;
2316 struct pet_access_gist_data data;
2318 if (!stmt)
2319 return NULL;
2321 data.domain = isl_set_copy(stmt->domain);
2322 data.value_bounds = value_bounds;
2323 if (stmt->n_arg > 0)
2324 data.domain = isl_map_domain(isl_set_unwrap(data.domain));
2326 data.domain = isl_set_intersect_params(data.domain,
2327 isl_set_copy(context));
2329 for (i = 0; i < stmt->n_arg; ++i) {
2330 stmt->args[i] = pet_expr_foreach_access_expr(stmt->args[i],
2331 &access_gist, &data);
2332 if (!stmt->args[i])
2333 goto error;
2336 stmt->body = pet_expr_foreach_access_expr(stmt->body,
2337 &access_gist, &data);
2338 if (!stmt->body)
2339 goto error;
2341 isl_set_free(data.domain);
2343 space = isl_set_get_space(stmt->domain);
2344 if (isl_space_is_wrapping(space))
2345 space = isl_space_domain(isl_space_unwrap(space));
2346 domain = isl_set_universe(space);
2347 domain = isl_set_intersect_params(domain, isl_set_copy(context));
2348 if (stmt->n_arg > 0)
2349 domain = apply_value_bounds(domain, stmt->n_arg, stmt->args,
2350 value_bounds);
2351 stmt->domain = isl_set_gist(stmt->domain, domain);
2352 if (!stmt->domain)
2353 return pet_stmt_free(stmt);
2355 return stmt;
2356 error:
2357 isl_set_free(data.domain);
2358 return pet_stmt_free(stmt);
2361 /* Compute the gist of the extent of the array
2362 * based on the constraints on the parameters specified by "context".
2364 static struct pet_array *array_gist(struct pet_array *array,
2365 __isl_keep isl_set *context)
2367 if (!array)
2368 return NULL;
2370 array->extent = isl_set_gist_params(array->extent,
2371 isl_set_copy(context));
2372 if (!array->extent)
2373 return pet_array_free(array);
2375 return array;
2378 /* Compute the gist of all sets and relations in "scop"
2379 * based on the constraints on the parameters specified by "scop->context"
2380 * and the constraints on the values of nested accesses specified
2381 * by "value_bounds".
2383 struct pet_scop *pet_scop_gist(struct pet_scop *scop,
2384 __isl_keep isl_union_map *value_bounds)
2386 int i;
2388 if (!scop)
2389 return NULL;
2391 scop->context = isl_set_coalesce(scop->context);
2392 if (!scop->context)
2393 return pet_scop_free(scop);
2395 for (i = 0; i < scop->n_array; ++i) {
2396 scop->arrays[i] = array_gist(scop->arrays[i], scop->context);
2397 if (!scop->arrays[i])
2398 return pet_scop_free(scop);
2401 for (i = 0; i < scop->n_stmt; ++i) {
2402 scop->stmts[i] = stmt_gist(scop->stmts[i], scop->context,
2403 value_bounds);
2404 if (!scop->stmts[i])
2405 return pet_scop_free(scop);
2408 return scop;
2411 /* Intersect the context of "scop" with "context".
2412 * To ensure that we don't introduce any unnamed parameters in
2413 * the context of "scop", we first remove the unnamed parameters
2414 * from "context".
2416 struct pet_scop *pet_scop_restrict_context(struct pet_scop *scop,
2417 __isl_take isl_set *context)
2419 if (!scop)
2420 goto error;
2422 context = set_project_out_unnamed_params(context);
2423 scop->context = isl_set_intersect(scop->context, context);
2424 if (!scop->context)
2425 return pet_scop_free(scop);
2427 return scop;
2428 error:
2429 isl_set_free(context);
2430 return pet_scop_free(scop);
2433 /* Drop the current context of "scop". That is, replace the context
2434 * by a universal set.
2436 struct pet_scop *pet_scop_reset_context(struct pet_scop *scop)
2438 isl_space *space;
2440 if (!scop)
2441 return NULL;
2443 space = isl_set_get_space(scop->context);
2444 isl_set_free(scop->context);
2445 scop->context = isl_set_universe(space);
2446 if (!scop->context)
2447 return pet_scop_free(scop);
2449 return scop;