include/pet.h: fix typo in documentation
[pet.git] / scop.c
blobc221992de2c5466e988e2007c7f19fe584a7d15c
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 /* pet_scop with extra information that is only used during parsing.
75 * In particular, we keep track of conditions under which we want
76 * to skip the rest of the current loop iteration (skip[pet_skip_now])
77 * and of conditions under which we want to skip subsequent
78 * loop iterations (skip[pet_skip_later]).
80 * The conditions are represented either by a variable, which
81 * is assumed to attain values zero and one, or by a boolean affine
82 * expression. The condition holds if the variable has value one
83 * or if the affine expression has value one (typically for only
84 * part of the parameter space).
86 * A missing condition (skip[type] == NULL) means that we don't want
87 * to skip anything.
89 struct pet_scop_ext {
90 struct pet_scop scop;
92 isl_set *skip[2];
95 const char *pet_op_str(enum pet_op_type op)
97 return op_str[op];
100 int pet_op_is_inc_dec(enum pet_op_type op)
102 return op == pet_op_post_inc || op == pet_op_post_dec ||
103 op == pet_op_pre_inc || op == pet_op_pre_dec;
106 const char *pet_type_str(enum pet_expr_type type)
108 return type_str[type];
111 enum pet_op_type pet_str_op(const char *str)
113 int i;
115 for (i = 0; i < ARRAY_SIZE(op_str); ++i)
116 if (!strcmp(op_str[i], str))
117 return i;
119 return -1;
122 enum pet_expr_type pet_str_type(const char *str)
124 int i;
126 for (i = 0; i < ARRAY_SIZE(type_str); ++i)
127 if (!strcmp(type_str[i], str))
128 return i;
130 return -1;
133 /* Construct a pet_expr from an access relation.
134 * By default, it is considered to be a read access.
136 struct pet_expr *pet_expr_from_access(__isl_take isl_map *access)
138 isl_ctx *ctx = isl_map_get_ctx(access);
139 struct pet_expr *expr;
141 if (!access)
142 return NULL;
143 expr = isl_calloc_type(ctx, struct pet_expr);
144 if (!expr)
145 goto error;
147 expr->type = pet_expr_access;
148 expr->acc.access = access;
149 expr->acc.read = 1;
150 expr->acc.write = 0;
152 return expr;
153 error:
154 isl_map_free(access);
155 return NULL;
158 /* Construct a unary pet_expr that performs "op" on "arg".
160 struct pet_expr *pet_expr_new_unary(isl_ctx *ctx, enum pet_op_type op,
161 struct pet_expr *arg)
163 struct pet_expr *expr;
165 if (!arg)
166 goto error;
167 expr = isl_alloc_type(ctx, struct pet_expr);
168 if (!expr)
169 goto error;
171 expr->type = pet_expr_unary;
172 expr->op = op;
173 expr->n_arg = 1;
174 expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
175 if (!expr->args)
176 goto error;
177 expr->args[pet_un_arg] = arg;
179 return expr;
180 error:
181 pet_expr_free(arg);
182 return NULL;
185 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
187 struct pet_expr *pet_expr_new_binary(isl_ctx *ctx, enum pet_op_type op,
188 struct pet_expr *lhs, struct pet_expr *rhs)
190 struct pet_expr *expr;
192 if (!lhs || !rhs)
193 goto error;
194 expr = isl_alloc_type(ctx, struct pet_expr);
195 if (!expr)
196 goto error;
198 expr->type = pet_expr_binary;
199 expr->op = op;
200 expr->n_arg = 2;
201 expr->args = isl_calloc_array(ctx, struct pet_expr *, 2);
202 if (!expr->args)
203 goto error;
204 expr->args[pet_bin_lhs] = lhs;
205 expr->args[pet_bin_rhs] = rhs;
207 return expr;
208 error:
209 pet_expr_free(lhs);
210 pet_expr_free(rhs);
211 return NULL;
214 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
216 struct pet_expr *pet_expr_new_ternary(isl_ctx *ctx, struct pet_expr *cond,
217 struct pet_expr *lhs, struct pet_expr *rhs)
219 struct pet_expr *expr;
221 if (!cond || !lhs || !rhs)
222 goto error;
223 expr = isl_alloc_type(ctx, struct pet_expr);
224 if (!expr)
225 goto error;
227 expr->type = pet_expr_ternary;
228 expr->n_arg = 3;
229 expr->args = isl_calloc_array(ctx, struct pet_expr *, 3);
230 if (!expr->args)
231 goto error;
232 expr->args[pet_ter_cond] = cond;
233 expr->args[pet_ter_true] = lhs;
234 expr->args[pet_ter_false] = rhs;
236 return expr;
237 error:
238 pet_expr_free(cond);
239 pet_expr_free(lhs);
240 pet_expr_free(rhs);
241 return NULL;
244 /* Construct a call pet_expr that calls function "name" with "n_arg"
245 * arguments. The caller is responsible for filling in the arguments.
247 struct pet_expr *pet_expr_new_call(isl_ctx *ctx, const char *name,
248 unsigned n_arg)
250 struct pet_expr *expr;
252 expr = isl_alloc_type(ctx, struct pet_expr);
253 if (!expr)
254 return NULL;
256 expr->type = pet_expr_call;
257 expr->n_arg = n_arg;
258 expr->name = strdup(name);
259 expr->args = isl_calloc_array(ctx, struct pet_expr *, n_arg);
260 if (!expr->name || !expr->args)
261 return pet_expr_free(expr);
263 return expr;
266 /* Construct a pet_expr that represents the double "d".
268 struct pet_expr *pet_expr_new_double(isl_ctx *ctx, double d)
270 struct pet_expr *expr;
272 expr = isl_calloc_type(ctx, struct pet_expr);
273 if (!expr)
274 return NULL;
276 expr->type = pet_expr_double;
277 expr->d = d;
279 return expr;
282 void *pet_expr_free(struct pet_expr *expr)
284 int i;
286 if (!expr)
287 return NULL;
289 for (i = 0; i < expr->n_arg; ++i)
290 pet_expr_free(expr->args[i]);
291 free(expr->args);
293 switch (expr->type) {
294 case pet_expr_access:
295 isl_map_free(expr->acc.access);
296 break;
297 case pet_expr_call:
298 free(expr->name);
299 break;
300 case pet_expr_double:
301 case pet_expr_unary:
302 case pet_expr_binary:
303 case pet_expr_ternary:
304 break;
307 free(expr);
308 return NULL;
311 static void expr_dump(struct pet_expr *expr, int indent)
313 int i;
315 if (!expr)
316 return;
318 fprintf(stderr, "%*s", indent, "");
320 switch (expr->type) {
321 case pet_expr_double:
322 fprintf(stderr, "%g\n", expr->d);
323 break;
324 case pet_expr_access:
325 isl_map_dump(expr->acc.access);
326 fprintf(stderr, "%*sread: %d\n", indent + 2,
327 "", expr->acc.read);
328 fprintf(stderr, "%*swrite: %d\n", indent + 2,
329 "", expr->acc.write);
330 for (i = 0; i < expr->n_arg; ++i)
331 expr_dump(expr->args[i], indent + 2);
332 break;
333 case pet_expr_unary:
334 fprintf(stderr, "%s\n", op_str[expr->op]);
335 expr_dump(expr->args[pet_un_arg], indent + 2);
336 break;
337 case pet_expr_binary:
338 fprintf(stderr, "%s\n", op_str[expr->op]);
339 expr_dump(expr->args[pet_bin_lhs], indent + 2);
340 expr_dump(expr->args[pet_bin_rhs], indent + 2);
341 break;
342 case pet_expr_ternary:
343 fprintf(stderr, "?:\n");
344 expr_dump(expr->args[pet_ter_cond], indent + 2);
345 expr_dump(expr->args[pet_ter_true], indent + 2);
346 expr_dump(expr->args[pet_ter_false], indent + 2);
347 break;
348 case pet_expr_call:
349 fprintf(stderr, "%s/%d\n", expr->name, expr->n_arg);
350 for (i = 0; i < expr->n_arg; ++i)
351 expr_dump(expr->args[i], indent + 2);
352 break;
356 void pet_expr_dump(struct pet_expr *expr)
358 expr_dump(expr, 0);
361 /* Does "expr" represent an access to an unnamed space, i.e.,
362 * does it represent an affine expression?
364 int pet_expr_is_affine(struct pet_expr *expr)
366 int has_id;
368 if (!expr)
369 return -1;
370 if (expr->type != pet_expr_access)
371 return 0;
373 has_id = isl_map_has_tuple_id(expr->acc.access, isl_dim_out);
374 if (has_id < 0)
375 return -1;
377 return !has_id;
380 /* Return 1 if the two pet_exprs are equivalent.
382 int pet_expr_is_equal(struct pet_expr *expr1, struct pet_expr *expr2)
384 int i;
386 if (!expr1 || !expr2)
387 return 0;
389 if (expr1->type != expr2->type)
390 return 0;
391 if (expr1->n_arg != expr2->n_arg)
392 return 0;
393 for (i = 0; i < expr1->n_arg; ++i)
394 if (!pet_expr_is_equal(expr1->args[i], expr2->args[i]))
395 return 0;
396 switch (expr1->type) {
397 case pet_expr_double:
398 if (expr1->d != expr2->d)
399 return 0;
400 break;
401 case pet_expr_access:
402 if (expr1->acc.read != expr2->acc.read)
403 return 0;
404 if (expr1->acc.write != expr2->acc.write)
405 return 0;
406 if (!expr1->acc.access || !expr2->acc.access)
407 return 0;
408 if (!isl_map_is_equal(expr1->acc.access, expr2->acc.access))
409 return 0;
410 break;
411 case pet_expr_unary:
412 case pet_expr_binary:
413 case pet_expr_ternary:
414 if (expr1->op != expr2->op)
415 return 0;
416 break;
417 case pet_expr_call:
418 if (strcmp(expr1->name, expr2->name))
419 return 0;
420 break;
423 return 1;
426 /* Add extra conditions on the parameters to all access relations in "expr".
428 struct pet_expr *pet_expr_restrict(struct pet_expr *expr,
429 __isl_take isl_set *cond)
431 int i;
433 if (!expr)
434 goto error;
436 for (i = 0; i < expr->n_arg; ++i) {
437 expr->args[i] = pet_expr_restrict(expr->args[i],
438 isl_set_copy(cond));
439 if (!expr->args[i])
440 goto error;
443 if (expr->type == pet_expr_access) {
444 expr->acc.access = isl_map_intersect_params(expr->acc.access,
445 isl_set_copy(cond));
446 if (!expr->acc.access)
447 goto error;
450 isl_set_free(cond);
451 return expr;
452 error:
453 isl_set_free(cond);
454 return pet_expr_free(expr);
457 /* Modify all access relations in "expr" by calling "fn" on them.
459 struct pet_expr *pet_expr_foreach_access(struct pet_expr *expr,
460 __isl_give isl_map *(*fn)(__isl_take isl_map *access, void *user),
461 void *user)
463 int i;
465 if (!expr)
466 return NULL;
468 for (i = 0; i < expr->n_arg; ++i) {
469 expr->args[i] = pet_expr_foreach_access(expr->args[i], fn, user);
470 if (!expr->args[i])
471 return pet_expr_free(expr);
474 if (expr->type == pet_expr_access) {
475 expr->acc.access = fn(expr->acc.access, user);
476 if (!expr->acc.access)
477 return pet_expr_free(expr);
480 return expr;
483 /* Modify all expressions of type pet_expr_access in "expr"
484 * by calling "fn" on them.
486 struct pet_expr *pet_expr_foreach_access_expr(struct pet_expr *expr,
487 struct pet_expr *(*fn)(struct pet_expr *expr, void *user),
488 void *user)
490 int i;
492 if (!expr)
493 return NULL;
495 for (i = 0; i < expr->n_arg; ++i) {
496 expr->args[i] = pet_expr_foreach_access_expr(expr->args[i],
497 fn, user);
498 if (!expr->args[i])
499 return pet_expr_free(expr);
502 if (expr->type == pet_expr_access)
503 expr = fn(expr, user);
505 return expr;
508 /* Modify the given access relation based on the given iteration space
509 * transformation.
510 * If the access has any arguments then the domain of the access relation
511 * is a wrapped mapping from the iteration space to the space of
512 * argument values. We only need to change the domain of this wrapped
513 * mapping, so we extend the input transformation with an identity mapping
514 * on the space of argument values.
516 static __isl_give isl_map *update_domain(__isl_take isl_map *access,
517 void *user)
519 isl_map *update = user;
520 isl_space *dim;
522 update = isl_map_copy(update);
524 dim = isl_map_get_space(access);
525 dim = isl_space_domain(dim);
526 if (!isl_space_is_wrapping(dim))
527 isl_space_free(dim);
528 else {
529 isl_map *id;
530 dim = isl_space_unwrap(dim);
531 dim = isl_space_range(dim);
532 dim = isl_space_map_from_set(dim);
533 id = isl_map_identity(dim);
534 update = isl_map_product(update, id);
537 return isl_map_apply_domain(access, update);
540 /* Modify all access relations in "expr" based on the given iteration space
541 * transformation.
543 static struct pet_expr *expr_update_domain(struct pet_expr *expr,
544 __isl_take isl_map *update)
546 expr = pet_expr_foreach_access(expr, &update_domain, update);
547 isl_map_free(update);
548 return expr;
551 /* Construct a pet_stmt with given line number and statement
552 * number from a pet_expr.
553 * The initial iteration domain is the zero-dimensional universe.
554 * The name of the domain is given by "label" if it is non-NULL.
555 * Otherwise, the name is constructed as S_<id>.
556 * The domains of all access relations are modified to refer
557 * to the statement iteration domain.
559 struct pet_stmt *pet_stmt_from_pet_expr(isl_ctx *ctx, int line,
560 __isl_take isl_id *label, int id, struct pet_expr *expr)
562 struct pet_stmt *stmt;
563 isl_space *dim;
564 isl_set *dom;
565 isl_map *sched;
566 isl_map *add_name;
567 char name[50];
569 if (!expr)
570 goto error;
572 stmt = isl_calloc_type(ctx, struct pet_stmt);
573 if (!stmt)
574 goto error;
576 dim = isl_space_set_alloc(ctx, 0, 0);
577 if (label)
578 dim = isl_space_set_tuple_id(dim, isl_dim_set, label);
579 else {
580 snprintf(name, sizeof(name), "S_%d", id);
581 dim = isl_space_set_tuple_name(dim, isl_dim_set, name);
583 dom = isl_set_universe(isl_space_copy(dim));
584 sched = isl_map_from_domain(isl_set_copy(dom));
586 dim = isl_space_from_range(dim);
587 add_name = isl_map_universe(dim);
588 expr = expr_update_domain(expr, add_name);
590 stmt->line = line;
591 stmt->domain = dom;
592 stmt->schedule = sched;
593 stmt->body = expr;
595 if (!stmt->domain || !stmt->schedule || !stmt->body)
596 return pet_stmt_free(stmt);
598 return stmt;
599 error:
600 isl_id_free(label);
601 return pet_expr_free(expr);
604 void *pet_stmt_free(struct pet_stmt *stmt)
606 int i;
608 if (!stmt)
609 return NULL;
611 isl_set_free(stmt->domain);
612 isl_map_free(stmt->schedule);
613 pet_expr_free(stmt->body);
615 for (i = 0; i < stmt->n_arg; ++i)
616 pet_expr_free(stmt->args[i]);
617 free(stmt->args);
619 free(stmt);
620 return NULL;
623 static void stmt_dump(struct pet_stmt *stmt, int indent)
625 int i;
627 if (!stmt)
628 return;
630 fprintf(stderr, "%*s%d\n", indent, "", stmt->line);
631 fprintf(stderr, "%*s", indent, "");
632 isl_set_dump(stmt->domain);
633 fprintf(stderr, "%*s", indent, "");
634 isl_map_dump(stmt->schedule);
635 expr_dump(stmt->body, indent);
636 for (i = 0; i < stmt->n_arg; ++i)
637 expr_dump(stmt->args[i], indent + 2);
640 void pet_stmt_dump(struct pet_stmt *stmt)
642 stmt_dump(stmt, 0);
645 void *pet_array_free(struct pet_array *array)
647 if (!array)
648 return NULL;
650 isl_set_free(array->context);
651 isl_set_free(array->extent);
652 isl_set_free(array->value_bounds);
653 free(array->element_type);
655 free(array);
656 return NULL;
659 void pet_array_dump(struct pet_array *array)
661 if (!array)
662 return;
664 isl_set_dump(array->context);
665 isl_set_dump(array->extent);
666 isl_set_dump(array->value_bounds);
667 fprintf(stderr, "%s %s\n", array->element_type,
668 array->live_out ? "live-out" : "");
671 /* Alloc a pet_scop structure, with extra room for information that
672 * is only used during parsing.
674 struct pet_scop *pet_scop_alloc(isl_ctx *ctx)
676 return &isl_calloc_type(ctx, struct pet_scop_ext)->scop;
679 /* Construct a pet_scop with room for n statements.
681 static struct pet_scop *scop_alloc(isl_ctx *ctx, int n)
683 isl_space *space;
684 struct pet_scop *scop;
686 scop = pet_scop_alloc(ctx);
687 if (!scop)
688 return NULL;
690 space = isl_space_params_alloc(ctx, 0);
691 scop->context = isl_set_universe(isl_space_copy(space));
692 scop->context_value = isl_set_universe(space);
693 scop->stmts = isl_calloc_array(ctx, struct pet_stmt *, n);
694 if (!scop->context || !scop->stmts)
695 return pet_scop_free(scop);
697 scop->n_stmt = n;
699 return scop;
702 struct pet_scop *pet_scop_empty(isl_ctx *ctx)
704 return scop_alloc(ctx, 0);
707 /* Update "context" with respect to the valid parameter values for "access".
709 static __isl_give isl_set *access_extract_context(__isl_keep isl_map *access,
710 __isl_take isl_set *context)
712 context = isl_set_intersect(context,
713 isl_map_params(isl_map_copy(access)));
714 return context;
717 /* Update "context" with respect to the valid parameter values for "expr".
719 * If "expr" represents a ternary operator, then a parameter value
720 * needs to be valid for the condition and for at least one of the
721 * remaining two arguments.
722 * If the condition is an affine expression, then we can be a bit more specific.
723 * The parameter then has to be valid for the second argument for
724 * non-zero accesses and valid for the third argument for zero accesses.
726 static __isl_give isl_set *expr_extract_context(struct pet_expr *expr,
727 __isl_take isl_set *context)
729 int i;
731 if (expr->type == pet_expr_ternary) {
732 int is_aff;
733 isl_set *context1, *context2;
735 is_aff = pet_expr_is_affine(expr->args[0]);
736 if (is_aff < 0)
737 goto error;
739 context = expr_extract_context(expr->args[0], context);
740 context1 = expr_extract_context(expr->args[1],
741 isl_set_copy(context));
742 context2 = expr_extract_context(expr->args[2], context);
744 if (is_aff) {
745 isl_map *access;
746 isl_set *zero_set;
748 access = isl_map_copy(expr->args[0]->acc.access);
749 access = isl_map_fix_si(access, isl_dim_out, 0, 0);
750 zero_set = isl_map_params(access);
751 context1 = isl_set_subtract(context1,
752 isl_set_copy(zero_set));
753 context2 = isl_set_intersect(context2, zero_set);
756 context = isl_set_union(context1, context2);
757 context = isl_set_coalesce(context);
759 return context;
762 for (i = 0; i < expr->n_arg; ++i)
763 context = expr_extract_context(expr->args[i], context);
765 if (expr->type == pet_expr_access)
766 context = access_extract_context(expr->acc.access, context);
768 return context;
769 error:
770 isl_set_free(context);
771 return NULL;
774 /* Update "context" with respect to the valid parameter values for "stmt".
776 static __isl_give isl_set *stmt_extract_context(struct pet_stmt *stmt,
777 __isl_take isl_set *context)
779 int i;
781 for (i = 0; i < stmt->n_arg; ++i)
782 context = expr_extract_context(stmt->args[i], context);
784 context = expr_extract_context(stmt->body, context);
786 return context;
789 /* Construct a pet_scop that contains the given pet_stmt.
791 struct pet_scop *pet_scop_from_pet_stmt(isl_ctx *ctx, struct pet_stmt *stmt)
793 struct pet_scop *scop;
795 if (!stmt)
796 return NULL;
798 scop = scop_alloc(ctx, 1);
800 scop->context = stmt_extract_context(stmt, scop->context);
801 if (!scop->context)
802 goto error;
804 scop->stmts[0] = stmt;
806 return scop;
807 error:
808 pet_stmt_free(stmt);
809 pet_scop_free(scop);
810 return NULL;
813 /* Does "set" represent an element of an unnamed space, i.e.,
814 * does it represent an affine expression?
816 static int set_is_affine(__isl_keep isl_set *set)
818 int has_id;
820 has_id = isl_set_has_tuple_id(set);
821 if (has_id < 0)
822 return -1;
824 return !has_id;
827 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
828 * ext may be equal to either ext1 or ext2.
830 * The two skips that need to be combined are assumed to be affine expressions.
832 * We need to skip in ext if we need to skip in either ext1 or ext2.
833 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
835 static struct pet_scop_ext *combine_skips(struct pet_scop_ext *ext,
836 struct pet_scop_ext *ext1, struct pet_scop_ext *ext2,
837 enum pet_skip type)
839 isl_set *set, *skip1, *skip2;
841 if (!ext)
842 return NULL;
843 if (!ext1->skip[type] && !ext2->skip[type])
844 return ext;
845 if (!ext1->skip[type]) {
846 if (ext == ext2)
847 return ext;
848 ext->skip[type] = ext2->skip[type];
849 ext2->skip[type] = NULL;
850 return ext;
852 if (!ext2->skip[type]) {
853 if (ext == ext1)
854 return ext;
855 ext->skip[type] = ext1->skip[type];
856 ext1->skip[type] = NULL;
857 return ext;
860 if (!set_is_affine(ext1->skip[type]) ||
861 !set_is_affine(ext2->skip[type]))
862 isl_die(isl_set_get_ctx(ext1->skip[type]), isl_error_internal,
863 "can only combine affine skips",
864 return pet_scop_free(&ext->scop));
866 skip1 = isl_set_copy(ext1->skip[type]);
867 skip2 = isl_set_copy(ext2->skip[type]);
868 set = isl_set_intersect(
869 isl_set_fix_si(isl_set_copy(skip1), isl_dim_set, 0, 0),
870 isl_set_fix_si(isl_set_copy(skip2), isl_dim_set, 0, 0));
871 set = isl_set_union(set, isl_set_fix_si(skip1, isl_dim_set, 0, 1));
872 set = isl_set_union(set, isl_set_fix_si(skip2, isl_dim_set, 0, 1));
873 set = isl_set_coalesce(set);
874 isl_set_free(ext1->skip[type]);
875 ext1->skip[type] = NULL;
876 isl_set_free(ext2->skip[type]);
877 ext2->skip[type] = NULL;
878 ext->skip[type] = set;
879 if (!ext->skip[type])
880 return pet_scop_free(&ext->scop);
882 return ext;
885 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
886 * where type takes on the values pet_skip_now and pet_skip_later.
887 * scop may be equal to either scop1 or scop2.
889 static struct pet_scop *scop_combine_skips(struct pet_scop *scop,
890 struct pet_scop *scop1, struct pet_scop *scop2)
892 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
893 struct pet_scop_ext *ext1 = (struct pet_scop_ext *) scop1;
894 struct pet_scop_ext *ext2 = (struct pet_scop_ext *) scop2;
896 ext = combine_skips(ext, ext1, ext2, pet_skip_now);
897 ext = combine_skips(ext, ext1, ext2, pet_skip_later);
898 return &ext->scop;
901 /* Construct a pet_scop that contains the arrays, statements and
902 * skip information in "scop1" and "scop2".
904 static struct pet_scop *pet_scop_add(isl_ctx *ctx, struct pet_scop *scop1,
905 struct pet_scop *scop2)
907 int i;
908 struct pet_scop *scop;
910 if (!scop1 || !scop2)
911 goto error;
913 if (scop1->n_stmt == 0) {
914 scop2 = scop_combine_skips(scop2, scop1, scop2);
915 pet_scop_free(scop1);
916 return scop2;
919 if (scop2->n_stmt == 0) {
920 scop1 = scop_combine_skips(scop1, scop1, scop2);
921 pet_scop_free(scop2);
922 return scop1;
925 scop = scop_alloc(ctx, scop1->n_stmt + scop2->n_stmt);
926 if (!scop)
927 goto error;
929 scop->arrays = isl_calloc_array(ctx, struct pet_array *,
930 scop1->n_array + scop2->n_array);
931 if (!scop->arrays)
932 goto error;
933 scop->n_array = scop1->n_array + scop2->n_array;
935 for (i = 0; i < scop1->n_stmt; ++i) {
936 scop->stmts[i] = scop1->stmts[i];
937 scop1->stmts[i] = NULL;
940 for (i = 0; i < scop2->n_stmt; ++i) {
941 scop->stmts[scop1->n_stmt + i] = scop2->stmts[i];
942 scop2->stmts[i] = NULL;
945 for (i = 0; i < scop1->n_array; ++i) {
946 scop->arrays[i] = scop1->arrays[i];
947 scop1->arrays[i] = NULL;
950 for (i = 0; i < scop2->n_array; ++i) {
951 scop->arrays[scop1->n_array + i] = scop2->arrays[i];
952 scop2->arrays[i] = NULL;
955 scop = pet_scop_restrict_context(scop, isl_set_copy(scop1->context));
956 scop = pet_scop_restrict_context(scop, isl_set_copy(scop2->context));
957 scop = scop_combine_skips(scop, scop1, scop2);
959 pet_scop_free(scop1);
960 pet_scop_free(scop2);
961 return scop;
962 error:
963 pet_scop_free(scop1);
964 pet_scop_free(scop2);
965 return NULL;
968 /* Apply the skip condition "skip" to "scop".
969 * That is, make sure "scop" is not executed when the condition holds.
971 * If "skip" is an affine expression, we add the conditions under
972 * which the expression is zero to the iteration domains.
973 * Otherwise, we add a filter on the variable attaining the value zero.
975 static struct pet_scop *restrict_skip(struct pet_scop *scop,
976 __isl_take isl_set *skip)
978 isl_map *skip_map;
979 int is_aff;
981 if (!scop || !skip)
982 goto error;
984 is_aff = set_is_affine(skip);
985 if (is_aff < 0)
986 goto error;
988 if (!is_aff)
989 return pet_scop_filter(scop, isl_map_from_range(skip), 0);
991 skip = isl_set_fix_si(skip, isl_dim_set, 0, 0);
992 scop = pet_scop_restrict(scop, isl_set_params(skip));
994 return scop;
995 error:
996 isl_set_free(skip);
997 return pet_scop_free(scop);
1000 /* Construct a pet_scop that contains the arrays, statements and
1001 * skip information in "scop1" and "scop2", where the two scops
1002 * are executed "in sequence". That is, breaks and continues
1003 * in scop1 have an effect on scop2.
1005 struct pet_scop *pet_scop_add_seq(isl_ctx *ctx, struct pet_scop *scop1,
1006 struct pet_scop *scop2)
1008 if (scop1 && pet_scop_has_skip(scop1, pet_skip_now))
1009 scop2 = restrict_skip(scop2,
1010 pet_scop_get_skip(scop1, pet_skip_now));
1011 return pet_scop_add(ctx, scop1, scop2);
1014 /* Construct a pet_scop that contains the arrays, statements and
1015 * skip information in "scop1" and "scop2", where the two scops
1016 * are executed "in parallel". That is, any break or continue
1017 * in scop1 has no effect on scop2.
1019 struct pet_scop *pet_scop_add_par(isl_ctx *ctx, struct pet_scop *scop1,
1020 struct pet_scop *scop2)
1022 return pet_scop_add(ctx, scop1, scop2);
1025 void *pet_scop_free(struct pet_scop *scop)
1027 int i;
1028 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1030 if (!scop)
1031 return NULL;
1032 isl_set_free(scop->context);
1033 isl_set_free(scop->context_value);
1034 if (scop->arrays)
1035 for (i = 0; i < scop->n_array; ++i)
1036 pet_array_free(scop->arrays[i]);
1037 free(scop->arrays);
1038 if (scop->stmts)
1039 for (i = 0; i < scop->n_stmt; ++i)
1040 pet_stmt_free(scop->stmts[i]);
1041 free(scop->stmts);
1042 isl_set_free(ext->skip[pet_skip_now]);
1043 isl_set_free(ext->skip[pet_skip_later]);
1044 free(scop);
1045 return NULL;
1048 void pet_scop_dump(struct pet_scop *scop)
1050 int i;
1051 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1053 if (!scop)
1054 return;
1056 isl_set_dump(scop->context);
1057 isl_set_dump(scop->context_value);
1058 for (i = 0; i < scop->n_array; ++i)
1059 pet_array_dump(scop->arrays[i]);
1060 for (i = 0; i < scop->n_stmt; ++i)
1061 pet_stmt_dump(scop->stmts[i]);
1063 if (ext->skip[0]) {
1064 fprintf(stderr, "skip\n");
1065 isl_set_dump(ext->skip[0]);
1066 isl_set_dump(ext->skip[1]);
1070 /* Return 1 if the two pet_arrays are equivalent.
1072 * We don't compare element_size as this may be target dependent.
1074 int pet_array_is_equal(struct pet_array *array1, struct pet_array *array2)
1076 if (!array1 || !array2)
1077 return 0;
1079 if (!isl_set_is_equal(array1->context, array2->context))
1080 return 0;
1081 if (!isl_set_is_equal(array1->extent, array2->extent))
1082 return 0;
1083 if (!!array1->value_bounds != !!array2->value_bounds)
1084 return 0;
1085 if (array1->value_bounds &&
1086 !isl_set_is_equal(array1->value_bounds, array2->value_bounds))
1087 return 0;
1088 if (strcmp(array1->element_type, array2->element_type))
1089 return 0;
1090 if (array1->live_out != array2->live_out)
1091 return 0;
1092 if (array1->uniquely_defined != array2->uniquely_defined)
1093 return 0;
1095 return 1;
1098 /* Return 1 if the two pet_stmts are equivalent.
1100 int pet_stmt_is_equal(struct pet_stmt *stmt1, struct pet_stmt *stmt2)
1102 int i;
1104 if (!stmt1 || !stmt2)
1105 return 0;
1107 if (stmt1->line != stmt2->line)
1108 return 0;
1109 if (!isl_set_is_equal(stmt1->domain, stmt2->domain))
1110 return 0;
1111 if (!isl_map_is_equal(stmt1->schedule, stmt2->schedule))
1112 return 0;
1113 if (!pet_expr_is_equal(stmt1->body, stmt2->body))
1114 return 0;
1115 if (stmt1->n_arg != stmt2->n_arg)
1116 return 0;
1117 for (i = 0; i < stmt1->n_arg; ++i) {
1118 if (!pet_expr_is_equal(stmt1->args[i], stmt2->args[i]))
1119 return 0;
1122 return 1;
1125 /* Return 1 if the two pet_scops are equivalent.
1127 int pet_scop_is_equal(struct pet_scop *scop1, struct pet_scop *scop2)
1129 int i;
1131 if (!scop1 || !scop2)
1132 return 0;
1134 if (!isl_set_is_equal(scop1->context, scop2->context))
1135 return 0;
1136 if (!isl_set_is_equal(scop1->context_value, scop2->context_value))
1137 return 0;
1139 if (scop1->n_array != scop2->n_array)
1140 return 0;
1141 for (i = 0; i < scop1->n_array; ++i)
1142 if (!pet_array_is_equal(scop1->arrays[i], scop2->arrays[i]))
1143 return 0;
1145 if (scop1->n_stmt != scop2->n_stmt)
1146 return 0;
1147 for (i = 0; i < scop1->n_stmt; ++i)
1148 if (!pet_stmt_is_equal(scop1->stmts[i], scop2->stmts[i]))
1149 return 0;
1151 return 1;
1154 /* Prefix the schedule of "stmt" with an extra dimension with constant
1155 * value "pos".
1157 struct pet_stmt *pet_stmt_prefix(struct pet_stmt *stmt, int pos)
1159 if (!stmt)
1160 return NULL;
1162 stmt->schedule = isl_map_insert_dims(stmt->schedule, isl_dim_out, 0, 1);
1163 stmt->schedule = isl_map_fix_si(stmt->schedule, isl_dim_out, 0, pos);
1164 if (!stmt->schedule)
1165 return pet_stmt_free(stmt);
1167 return stmt;
1170 /* Prefix the schedules of all statements in "scop" with an extra
1171 * dimension with constant value "pos".
1173 struct pet_scop *pet_scop_prefix(struct pet_scop *scop, int pos)
1175 int i;
1177 if (!scop)
1178 return NULL;
1180 for (i = 0; i < scop->n_stmt; ++i) {
1181 scop->stmts[i] = pet_stmt_prefix(scop->stmts[i], pos);
1182 if (!scop->stmts[i])
1183 return pet_scop_free(scop);
1186 return scop;
1189 /* Given a set with a parameter at "param_pos" that refers to the
1190 * iterator, "move" the iterator to the first set dimension.
1191 * That is, essentially equate the parameter to the first set dimension
1192 * and then project it out.
1194 * The first set dimension may however refer to a virtual iterator,
1195 * while the parameter refers to the "real" iterator.
1196 * We therefore need to take into account the mapping "iv_map", which
1197 * maps the virtual iterator to the real iterator.
1198 * In particular, we equate the set dimension to the input of the map
1199 * and the parameter to the output of the map and then project out
1200 * everything we don't need anymore.
1202 static __isl_give isl_set *internalize_iv(__isl_take isl_set *set,
1203 int param_pos, __isl_take isl_map *iv_map)
1205 isl_map *map;
1206 map = isl_map_from_domain(set);
1207 map = isl_map_add_dims(map, isl_dim_out, 1);
1208 map = isl_map_equate(map, isl_dim_in, 0, isl_dim_out, 0);
1209 iv_map = isl_map_align_params(iv_map, isl_map_get_space(map));
1210 map = isl_map_apply_range(map, iv_map);
1211 map = isl_map_equate(map, isl_dim_param, param_pos, isl_dim_out, 0);
1212 map = isl_map_project_out(map, isl_dim_param, param_pos, 1);
1213 return isl_map_domain(map);
1216 /* Data used in embed_access.
1217 * extend adds an iterator to the iteration domain
1218 * iv_map maps the virtual iterator to the real iterator
1219 * var_id represents the induction variable of the corresponding loop
1221 struct pet_embed_access {
1222 isl_map *extend;
1223 isl_map *iv_map;
1224 isl_id *var_id;
1227 /* Embed the access relation in an extra outer loop.
1229 * We first update the iteration domain to insert the extra dimension.
1231 * If the access refers to the induction variable, then it is
1232 * turned into an access to the set of integers with index (and value)
1233 * equal to the induction variable.
1235 * If the induction variable appears in the constraints (as a parameter),
1236 * then the parameter is equated to the newly introduced iteration
1237 * domain dimension and subsequently projected out.
1239 * Similarly, if the accessed array is a virtual array (with user
1240 * pointer equal to NULL), as created by create_test_access,
1241 * then it is extended along with the domain of the access.
1243 static __isl_give isl_map *embed_access(__isl_take isl_map *access,
1244 void *user)
1246 struct pet_embed_access *data = user;
1247 isl_id *array_id = NULL;
1248 int pos;
1250 access = update_domain(access, data->extend);
1252 if (isl_map_has_tuple_id(access, isl_dim_out))
1253 array_id = isl_map_get_tuple_id(access, isl_dim_out);
1254 if (array_id == data->var_id ||
1255 (array_id && !isl_id_get_user(array_id))) {
1256 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
1257 access = isl_map_equate(access,
1258 isl_dim_in, 0, isl_dim_out, 0);
1259 if (array_id == data->var_id)
1260 access = isl_map_apply_range(access,
1261 isl_map_copy(data->iv_map));
1262 else
1263 access = isl_map_set_tuple_id(access, isl_dim_out,
1264 isl_id_copy(array_id));
1266 isl_id_free(array_id);
1268 pos = isl_map_find_dim_by_id(access, isl_dim_param, data->var_id);
1269 if (pos >= 0) {
1270 isl_set *set = isl_map_wrap(access);
1271 set = internalize_iv(set, pos, isl_map_copy(data->iv_map));
1272 access = isl_set_unwrap(set);
1274 access = isl_map_set_dim_id(access, isl_dim_in, 0,
1275 isl_id_copy(data->var_id));
1277 return access;
1280 /* Embed all access relations in "expr" in an extra loop.
1281 * "extend" inserts an outer loop iterator in the iteration domains.
1282 * "iv_map" maps the virtual iterator to the real iterator
1283 * "var_id" represents the induction variable.
1285 static struct pet_expr *expr_embed(struct pet_expr *expr,
1286 __isl_take isl_map *extend, __isl_take isl_map *iv_map,
1287 __isl_keep isl_id *var_id)
1289 struct pet_embed_access data =
1290 { .extend = extend, .iv_map = iv_map, .var_id = var_id };
1292 expr = pet_expr_foreach_access(expr, &embed_access, &data);
1293 isl_map_free(iv_map);
1294 isl_map_free(extend);
1295 return expr;
1298 /* Embed the given pet_stmt in an extra outer loop with iteration domain
1299 * "dom" and schedule "sched". "var_id" represents the induction variable
1300 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
1301 * That is, it maps the iterator used in "dom" and the domain of "sched"
1302 * to the iterator that some of the parameters in "stmt" may refer to.
1304 * The iteration domain and schedule of the statement are updated
1305 * according to the iteration domain and schedule of the new loop.
1306 * If stmt->domain is a wrapped map, then the iteration domain
1307 * is the domain of this map, so we need to be careful to adjust
1308 * this domain.
1310 * If the induction variable appears in the constraints (as a parameter)
1311 * of the current iteration domain or the schedule of the statement,
1312 * then the parameter is equated to the newly introduced iteration
1313 * domain dimension and subsequently projected out.
1315 * Finally, all access relations are updated based on the extra loop.
1317 static struct pet_stmt *pet_stmt_embed(struct pet_stmt *stmt,
1318 __isl_take isl_set *dom, __isl_take isl_map *sched,
1319 __isl_take isl_map *iv_map, __isl_take isl_id *var_id)
1321 int i;
1322 int pos;
1323 isl_id *stmt_id;
1324 isl_space *dim;
1325 isl_map *extend;
1327 if (!stmt)
1328 goto error;
1330 if (isl_set_is_wrapping(stmt->domain)) {
1331 isl_map *map;
1332 isl_map *ext;
1333 isl_space *ran_dim;
1335 map = isl_set_unwrap(stmt->domain);
1336 stmt_id = isl_map_get_tuple_id(map, isl_dim_in);
1337 ran_dim = isl_space_range(isl_map_get_space(map));
1338 ext = isl_map_from_domain_and_range(isl_set_copy(dom),
1339 isl_set_universe(ran_dim));
1340 map = isl_map_flat_domain_product(ext, map);
1341 map = isl_map_set_tuple_id(map, isl_dim_in,
1342 isl_id_copy(stmt_id));
1343 dim = isl_space_domain(isl_map_get_space(map));
1344 stmt->domain = isl_map_wrap(map);
1345 } else {
1346 stmt_id = isl_set_get_tuple_id(stmt->domain);
1347 stmt->domain = isl_set_flat_product(isl_set_copy(dom),
1348 stmt->domain);
1349 stmt->domain = isl_set_set_tuple_id(stmt->domain,
1350 isl_id_copy(stmt_id));
1351 dim = isl_set_get_space(stmt->domain);
1354 pos = isl_set_find_dim_by_id(stmt->domain, isl_dim_param, var_id);
1355 if (pos >= 0)
1356 stmt->domain = internalize_iv(stmt->domain, pos,
1357 isl_map_copy(iv_map));
1359 stmt->schedule = isl_map_flat_product(sched, stmt->schedule);
1360 stmt->schedule = isl_map_set_tuple_id(stmt->schedule,
1361 isl_dim_in, stmt_id);
1363 pos = isl_map_find_dim_by_id(stmt->schedule, isl_dim_param, var_id);
1364 if (pos >= 0) {
1365 isl_set *set = isl_map_wrap(stmt->schedule);
1366 set = internalize_iv(set, pos, isl_map_copy(iv_map));
1367 stmt->schedule = isl_set_unwrap(set);
1370 dim = isl_space_map_from_set(dim);
1371 extend = isl_map_identity(dim);
1372 extend = isl_map_remove_dims(extend, isl_dim_in, 0, 1);
1373 extend = isl_map_set_tuple_id(extend, isl_dim_in,
1374 isl_map_get_tuple_id(extend, isl_dim_out));
1375 for (i = 0; i < stmt->n_arg; ++i)
1376 stmt->args[i] = expr_embed(stmt->args[i], isl_map_copy(extend),
1377 isl_map_copy(iv_map), var_id);
1378 stmt->body = expr_embed(stmt->body, extend, iv_map, var_id);
1380 isl_set_free(dom);
1381 isl_id_free(var_id);
1383 for (i = 0; i < stmt->n_arg; ++i)
1384 if (!stmt->args[i])
1385 return pet_stmt_free(stmt);
1386 if (!stmt->domain || !stmt->schedule || !stmt->body)
1387 return pet_stmt_free(stmt);
1388 return stmt;
1389 error:
1390 isl_set_free(dom);
1391 isl_map_free(sched);
1392 isl_map_free(iv_map);
1393 isl_id_free(var_id);
1394 return NULL;
1397 /* Embed the given pet_array in an extra outer loop with iteration domain
1398 * "dom".
1399 * This embedding only has an effect on virtual arrays (those with
1400 * user pointer equal to NULL), which need to be extended along with
1401 * the iteration domain.
1403 static struct pet_array *pet_array_embed(struct pet_array *array,
1404 __isl_take isl_set *dom)
1406 isl_id *array_id = NULL;
1408 if (!array)
1409 goto error;
1411 if (isl_set_has_tuple_id(array->extent))
1412 array_id = isl_set_get_tuple_id(array->extent);
1414 if (array_id && !isl_id_get_user(array_id)) {
1415 array->extent = isl_set_flat_product(dom, array->extent);
1416 array->extent = isl_set_set_tuple_id(array->extent, array_id);
1417 } else {
1418 isl_set_free(dom);
1419 isl_id_free(array_id);
1422 return array;
1423 error:
1424 isl_set_free(dom);
1425 return NULL;
1428 /* Project out all unnamed parameters from "set" and return the result.
1430 static __isl_give isl_set *set_project_out_unnamed_params(
1431 __isl_take isl_set *set)
1433 int i, n;
1435 n = isl_set_dim(set, isl_dim_param);
1436 for (i = n - 1; i >= 0; --i) {
1437 if (isl_set_has_dim_name(set, isl_dim_param, i))
1438 continue;
1439 set = isl_set_project_out(set, isl_dim_param, i, 1);
1442 return set;
1445 /* Update the context with respect to an embedding into a loop
1446 * with iteration domain "dom" and induction variable "id".
1447 * "iv_map" maps a possibly virtual iterator (used in "dom")
1448 * to the real iterator (parameter "id").
1450 * If the current context is independent of "id", we don't need
1451 * to do anything.
1452 * Otherwise, a parameter value is invalid for the embedding if
1453 * any of the corresponding iterator values is invalid.
1454 * That is, a parameter value is valid only if all the corresponding
1455 * iterator values are valid.
1456 * We therefore compute the set of parameters
1458 * forall i in dom : valid (i)
1460 * or
1462 * not exists i in dom : not valid(i)
1464 * i.e.,
1466 * not exists i in dom \ valid(i)
1468 * Before we subtract valid(i) from dom, we first need to map
1469 * the real iterator to the virtual iterator.
1471 * If there are any unnamed parameters in "dom", then we consider
1472 * a parameter value to be valid if it is valid for any value of those
1473 * unnamed parameters. They are therefore projected out at the end.
1475 static __isl_give isl_set *context_embed(__isl_take isl_set *context,
1476 __isl_keep isl_set *dom, __isl_keep isl_map *iv_map,
1477 __isl_keep isl_id *id)
1479 int pos;
1481 pos = isl_set_find_dim_by_id(context, isl_dim_param, id);
1482 if (pos < 0)
1483 return context;
1485 context = isl_set_from_params(context);
1486 context = isl_set_add_dims(context, isl_dim_set, 1);
1487 context = isl_set_equate(context, isl_dim_param, pos, isl_dim_set, 0);
1488 context = isl_set_project_out(context, isl_dim_param, pos, 1);
1489 context = isl_set_apply(context, isl_map_reverse(isl_map_copy(iv_map)));
1490 context = isl_set_subtract(isl_set_copy(dom), context);
1491 context = isl_set_params(context);
1492 context = isl_set_complement(context);
1493 context = set_project_out_unnamed_params(context);
1494 return context;
1497 /* Embed all statements and arrays in "scop" in an extra outer loop
1498 * with iteration domain "dom" and schedule "sched".
1499 * "id" represents the induction variable of the loop.
1500 * "iv_map" maps a possibly virtual iterator to the real iterator.
1501 * That is, it maps the iterator used in "dom" and the domain of "sched"
1502 * to the iterator that some of the parameters in "scop" may refer to.
1504 * Any skip conditions within the loop have no effect outside of the loop.
1505 * The caller is responsible for making sure skip[pet_skip_later] has been
1506 * taken into account.
1508 struct pet_scop *pet_scop_embed(struct pet_scop *scop, __isl_take isl_set *dom,
1509 __isl_take isl_map *sched, __isl_take isl_map *iv_map,
1510 __isl_take isl_id *id)
1512 int i;
1514 if (!scop)
1515 goto error;
1517 pet_scop_reset_skip(scop, pet_skip_now);
1518 pet_scop_reset_skip(scop, pet_skip_later);
1520 scop->context = context_embed(scop->context, dom, iv_map, id);
1521 if (!scop->context)
1522 goto error;
1524 for (i = 0; i < scop->n_stmt; ++i) {
1525 scop->stmts[i] = pet_stmt_embed(scop->stmts[i],
1526 isl_set_copy(dom), isl_map_copy(sched),
1527 isl_map_copy(iv_map), isl_id_copy(id));
1528 if (!scop->stmts[i])
1529 goto error;
1532 for (i = 0; i < scop->n_array; ++i) {
1533 scop->arrays[i] = pet_array_embed(scop->arrays[i],
1534 isl_set_copy(dom));
1535 if (!scop->arrays[i])
1536 goto error;
1539 isl_set_free(dom);
1540 isl_map_free(sched);
1541 isl_map_free(iv_map);
1542 isl_id_free(id);
1543 return scop;
1544 error:
1545 isl_set_free(dom);
1546 isl_map_free(sched);
1547 isl_map_free(iv_map);
1548 isl_id_free(id);
1549 return pet_scop_free(scop);
1552 /* Add extra conditions on the parameters to iteration domain of "stmt".
1554 static struct pet_stmt *stmt_restrict(struct pet_stmt *stmt,
1555 __isl_take isl_set *cond)
1557 if (!stmt)
1558 goto error;
1560 stmt->domain = isl_set_intersect_params(stmt->domain, cond);
1562 return stmt;
1563 error:
1564 isl_set_free(cond);
1565 return pet_stmt_free(stmt);
1568 /* Add extra conditions to scop->skip[type].
1570 * The new skip condition only holds if it held before
1571 * and the condition is true. It does not hold if it did not hold
1572 * before or the condition is false.
1574 * The skip condition is assumed to be an affine expression.
1576 static struct pet_scop *pet_scop_restrict_skip(struct pet_scop *scop,
1577 enum pet_skip type, __isl_keep isl_set *cond)
1579 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1580 isl_set *skip;
1581 isl_set *set;
1583 if (!scop)
1584 return NULL;
1585 if (!ext->skip[type])
1586 return scop;
1588 if (!set_is_affine(ext->skip[type]))
1589 isl_die(isl_set_get_ctx(ext->skip[type]), isl_error_internal,
1590 "can only resrict affine skips",
1591 return pet_scop_free(scop));
1593 skip = ext->skip[type];
1594 skip = isl_set_intersect_params(skip, isl_set_copy(cond));
1595 set = isl_set_from_params(isl_set_copy(cond));
1596 set = isl_set_complement(set);
1597 set = isl_set_add_dims(set, isl_dim_set, 1);
1598 set = isl_set_fix_si(set, isl_dim_set, 0, 0);
1599 skip = isl_set_union(skip, set);
1600 ext->skip[type] = skip;
1601 if (!ext->skip[type])
1602 return pet_scop_free(scop);
1604 return scop;
1607 /* Add extra conditions on the parameters to all iteration domains
1608 * and skip conditions.
1610 * A parameter value is valid for the result if it was valid
1611 * for the original scop and satisfies "cond" or if it does
1612 * not satisfy "cond" as in this case the scop is not executed
1613 * and the original constraints on the parameters are irrelevant.
1615 struct pet_scop *pet_scop_restrict(struct pet_scop *scop,
1616 __isl_take isl_set *cond)
1618 int i;
1620 scop = pet_scop_restrict_skip(scop, pet_skip_now, cond);
1621 scop = pet_scop_restrict_skip(scop, pet_skip_later, cond);
1623 if (!scop)
1624 goto error;
1626 scop->context = isl_set_intersect(scop->context, isl_set_copy(cond));
1627 scop->context = isl_set_union(scop->context,
1628 isl_set_complement(isl_set_copy(cond)));
1629 scop->context = isl_set_coalesce(scop->context);
1630 scop->context = set_project_out_unnamed_params(scop->context);
1631 if (!scop->context)
1632 goto error;
1634 for (i = 0; i < scop->n_stmt; ++i) {
1635 scop->stmts[i] = stmt_restrict(scop->stmts[i],
1636 isl_set_copy(cond));
1637 if (!scop->stmts[i])
1638 goto error;
1641 isl_set_free(cond);
1642 return scop;
1643 error:
1644 isl_set_free(cond);
1645 return pet_scop_free(scop);
1648 /* Construct a map that inserts a filter value with name "id" and value
1649 * "satisfied" in the list of filter values embedded in the set space "space".
1651 * If "space" does not contain any filter values yet, we first create
1652 * a map that inserts 0 filter values, i.e.,
1654 * space -> [space -> []]
1656 * We can now assume that space is of the form [dom -> [filters]]
1657 * We construct an identity mapping on dom and a mapping on filters
1658 * that inserts the new filter
1660 * dom -> dom
1661 * [filters] -> [satisfied, filters]
1663 * and then compute the cross product
1665 * [dom -> [filters]] -> [dom -> [satisfied, filters]]
1667 static __isl_give isl_map *insert_filter_map(__isl_take isl_space *space,
1668 __isl_take isl_id *id, int satisfied)
1670 isl_space *space2;
1671 isl_map *map, *map_dom, *map_ran;
1672 isl_set *dom;
1674 if (isl_space_is_wrapping(space)) {
1675 space2 = isl_space_map_from_set(isl_space_copy(space));
1676 map = isl_map_identity(space2);
1677 space = isl_space_unwrap(space);
1678 } else {
1679 space = isl_space_from_domain(space);
1680 map = isl_map_universe(isl_space_copy(space));
1681 map = isl_map_reverse(isl_map_domain_map(map));
1684 space2 = isl_space_domain(isl_space_copy(space));
1685 map_dom = isl_map_identity(isl_space_map_from_set(space2));
1686 space = isl_space_range(space);
1687 map_ran = isl_map_identity(isl_space_map_from_set(space));
1688 map_ran = isl_map_insert_dims(map_ran, isl_dim_out, 0, 1);
1689 map_ran = isl_map_set_dim_id(map_ran, isl_dim_out, 0, id);
1690 map_ran = isl_map_fix_si(map_ran, isl_dim_out, 0, satisfied);
1692 map = isl_map_apply_range(map, isl_map_product(map_dom, map_ran));
1694 return map;
1697 /* Insert an argument expression corresponding to "test" in front
1698 * of the list of arguments described by *n_arg and *args.
1700 static int args_insert_access(unsigned *n_arg, struct pet_expr ***args,
1701 __isl_keep isl_map *test)
1703 int i;
1704 isl_ctx *ctx = isl_map_get_ctx(test);
1706 if (!test)
1707 return -1;
1709 if (!*args) {
1710 *args = isl_calloc_array(ctx, struct pet_expr *, 1);
1711 if (!*args)
1712 return -1;
1713 } else {
1714 struct pet_expr **ext;
1715 ext = isl_calloc_array(ctx, struct pet_expr *, 1 + *n_arg);
1716 if (!ext)
1717 return -1;
1718 for (i = 0; i < *n_arg; ++i)
1719 ext[1 + i] = (*args)[i];
1720 free(*args);
1721 *args = ext;
1723 (*n_arg)++;
1724 (*args)[0] = pet_expr_from_access(isl_map_copy(test));
1725 if (!(*args)[0])
1726 return -1;
1728 return 0;
1731 /* Make the expression "expr" depend on the value of "test"
1732 * being equal to "satisfied".
1734 * If "test" is an affine expression, we simply add the conditions
1735 * on the expression have the value "satisfied" to all access relations.
1737 * Otherwise, we add a filter to "expr" (which is then assumed to be
1738 * an access expression) corresponding to "test" being equal to "satisfied".
1740 struct pet_expr *pet_expr_filter(struct pet_expr *expr,
1741 __isl_take isl_map *test, int satisfied)
1743 isl_id *id;
1744 isl_ctx *ctx;
1745 isl_space *space;
1746 isl_map *map;
1748 if (!expr || !test)
1749 goto error;
1751 if (!isl_map_has_tuple_id(test, isl_dim_out)) {
1752 test = isl_map_fix_si(test, isl_dim_out, 0, satisfied);
1753 return pet_expr_restrict(expr, isl_map_params(test));
1756 ctx = isl_map_get_ctx(test);
1757 if (expr->type != pet_expr_access)
1758 isl_die(ctx, isl_error_invalid,
1759 "can only filter access expressions", goto error);
1761 space = isl_space_domain(isl_map_get_space(expr->acc.access));
1762 id = isl_map_get_tuple_id(test, isl_dim_out);
1763 map = insert_filter_map(space, id, satisfied);
1765 expr->acc.access = isl_map_apply_domain(expr->acc.access, map);
1766 if (!expr->acc.access)
1767 goto error;
1769 if (args_insert_access(&expr->n_arg, &expr->args, test) < 0)
1770 goto error;
1772 isl_map_free(test);
1773 return expr;
1774 error:
1775 isl_map_free(test);
1776 return pet_expr_free(expr);
1779 /* Make the statement "stmt" depend on the value of "test"
1780 * being equal to "satisfied" by adjusting stmt->domain.
1782 * The domain of "test" corresponds to the (zero or more) outer dimensions
1783 * of the iteration domain.
1785 * We insert an argument corresponding to a read to "test"
1786 * from the iteration domain of "stmt" in front of the list of arguments.
1787 * We also insert a corresponding output dimension in the wrapped
1788 * map contained in stmt->domain, with value set to "satisfied".
1790 static struct pet_stmt *stmt_filter(struct pet_stmt *stmt,
1791 __isl_take isl_map *test, int satisfied)
1793 int i;
1794 isl_id *id;
1795 isl_ctx *ctx;
1796 isl_map *map, *add_dom;
1797 isl_space *space;
1798 isl_set *dom;
1799 int n_test_dom;
1801 if (!stmt || !test)
1802 goto error;
1804 id = isl_map_get_tuple_id(test, isl_dim_out);
1805 map = insert_filter_map(isl_set_get_space(stmt->domain), id, satisfied);
1806 stmt->domain = isl_set_apply(stmt->domain, map);
1808 space = isl_space_unwrap(isl_set_get_space(stmt->domain));
1809 dom = isl_set_universe(isl_space_domain(space));
1810 n_test_dom = isl_map_dim(test, isl_dim_in);
1811 add_dom = isl_map_from_range(dom);
1812 add_dom = isl_map_add_dims(add_dom, isl_dim_in, n_test_dom);
1813 for (i = 0; i < n_test_dom; ++i)
1814 add_dom = isl_map_equate(add_dom, isl_dim_in, i,
1815 isl_dim_out, i);
1816 test = isl_map_apply_domain(test, add_dom);
1818 if (args_insert_access(&stmt->n_arg, &stmt->args, test) < 0)
1819 goto error;
1821 isl_map_free(test);
1822 return stmt;
1823 error:
1824 isl_map_free(test);
1825 return pet_stmt_free(stmt);
1828 /* Does "scop" have a skip condition of the given "type"?
1830 int pet_scop_has_skip(struct pet_scop *scop, enum pet_skip type)
1832 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1834 if (!scop)
1835 return -1;
1836 return ext->skip[type] != NULL;
1839 /* Does "scop" have a skip condition of the given "type" that
1840 * is an affine expression?
1842 int pet_scop_has_affine_skip(struct pet_scop *scop, enum pet_skip type)
1844 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1846 if (!scop)
1847 return -1;
1848 if (!ext->skip[type])
1849 return 0;
1850 return set_is_affine(ext->skip[type]);
1853 /* Does "scop" have a skip condition of the given "type" that
1854 * is not an affine expression?
1856 int pet_scop_has_var_skip(struct pet_scop *scop, enum pet_skip type)
1858 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1859 int aff;
1861 if (!scop)
1862 return -1;
1863 if (!ext->skip[type])
1864 return 0;
1865 aff = set_is_affine(ext->skip[type]);
1866 if (aff < 0)
1867 return -1;
1868 return !aff;
1871 /* Does "scop" have a skip condition of the given "type" that
1872 * is affine and holds on the entire domain?
1874 int pet_scop_has_universal_skip(struct pet_scop *scop, enum pet_skip type)
1876 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1877 isl_set *set;
1878 int is_aff;
1879 int is_univ;
1881 is_aff = pet_scop_has_affine_skip(scop, type);
1882 if (is_aff < 0 || !is_aff)
1883 return is_aff;
1885 set = isl_set_copy(ext->skip[type]);
1886 set = isl_set_fix_si(set, isl_dim_set, 0, 1);
1887 set = isl_set_params(set);
1888 is_univ = isl_set_plain_is_universe(set);
1889 isl_set_free(set);
1891 return is_univ;
1894 /* Replace scop->skip[type] by "skip".
1896 struct pet_scop *pet_scop_set_skip(struct pet_scop *scop,
1897 enum pet_skip type, __isl_take isl_set *skip)
1899 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1901 if (!scop || !skip)
1902 goto error;
1904 isl_set_free(ext->skip[type]);
1905 ext->skip[type] = skip;
1907 return scop;
1908 error:
1909 isl_set_free(skip);
1910 return pet_scop_free(scop);
1913 /* Return a copy of scop->skip[type].
1915 __isl_give isl_set *pet_scop_get_skip(struct pet_scop *scop,
1916 enum pet_skip type)
1918 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1920 if (!scop)
1921 return NULL;
1923 return isl_set_copy(ext->skip[type]);
1926 /* Return a map to the skip condition of the given type.
1928 __isl_give isl_map *pet_scop_get_skip_map(struct pet_scop *scop,
1929 enum pet_skip type)
1931 return isl_map_from_range(pet_scop_get_skip(scop, type));
1934 /* Return an access pet_expr corresponding to the skip condition
1935 * of the given type.
1937 struct pet_expr *pet_scop_get_skip_expr(struct pet_scop *scop,
1938 enum pet_skip type)
1940 return pet_expr_from_access(pet_scop_get_skip_map(scop, type));
1943 /* Drop the the skip condition scop->skip[type].
1945 void pet_scop_reset_skip(struct pet_scop *scop, enum pet_skip type)
1947 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1949 if (!scop)
1950 return;
1952 isl_set_free(ext->skip[type]);
1953 ext->skip[type] = NULL;
1956 /* Make the skip condition (if any) depend on the value of "test" being
1957 * equal to "satisfied".
1959 * We only support the case where the original skip condition is universal,
1960 * i.e., where skipping is unconditional, and where satisfied == 1.
1961 * In this case, the skip condition is changed to skip only when
1962 * "test" is equal to one.
1964 static struct pet_scop *pet_scop_filter_skip(struct pet_scop *scop,
1965 enum pet_skip type, __isl_keep isl_map *test, int satisfied)
1967 int is_univ = 0;
1969 if (!scop)
1970 return NULL;
1971 if (!pet_scop_has_skip(scop, type))
1972 return scop;
1974 if (satisfied)
1975 is_univ = pet_scop_has_universal_skip(scop, type);
1976 if (is_univ < 0)
1977 return pet_scop_free(scop);
1978 if (satisfied && is_univ) {
1979 scop = pet_scop_set_skip(scop, type,
1980 isl_map_range(isl_map_copy(test)));
1981 if (!scop)
1982 return NULL;
1983 } else {
1984 isl_die(isl_map_get_ctx(test), isl_error_internal,
1985 "skip expression cannot be filtered",
1986 return pet_scop_free(scop));
1989 return scop;
1992 /* Make all statements in "scop" depend on the value of "test"
1993 * being equal to "satisfied" by adjusting their domains.
1995 struct pet_scop *pet_scop_filter(struct pet_scop *scop,
1996 __isl_take isl_map *test, int satisfied)
1998 int i;
2000 scop = pet_scop_filter_skip(scop, pet_skip_now, test, satisfied);
2001 scop = pet_scop_filter_skip(scop, pet_skip_later, test, satisfied);
2003 if (!scop || !test)
2004 goto error;
2006 for (i = 0; i < scop->n_stmt; ++i) {
2007 scop->stmts[i] = stmt_filter(scop->stmts[i],
2008 isl_map_copy(test), satisfied);
2009 if (!scop->stmts[i])
2010 goto error;
2013 isl_map_free(test);
2014 return scop;
2015 error:
2016 isl_map_free(test);
2017 return pet_scop_free(scop);
2020 /* Do the filters "i" and "j" always have the same value?
2022 static int equal_filter_values(__isl_keep isl_set *domain, int i, int j)
2024 isl_map *map, *test;
2025 int equal;
2027 map = isl_set_unwrap(isl_set_copy(domain));
2028 test = isl_map_universe(isl_map_get_space(map));
2029 test = isl_map_equate(test, isl_dim_out, i, isl_dim_out, j);
2030 equal = isl_map_is_subset(map, test);
2031 isl_map_free(map);
2032 isl_map_free(test);
2034 return equal;
2037 /* Merge filters "i" and "j" into a single filter ("i") with as filter
2038 * access relation, the union of the two access relations.
2040 static struct pet_stmt *merge_filter_pair(struct pet_stmt *stmt, int i, int j)
2042 int k;
2043 isl_map *map;
2045 if (!stmt)
2046 return NULL;
2048 stmt->args[i]->acc.access = isl_map_union(stmt->args[i]->acc.access,
2049 isl_map_copy(stmt->args[j]->acc.access));
2050 stmt->args[i]->acc.access = isl_map_coalesce(stmt->args[i]->acc.access);
2052 pet_expr_free(stmt->args[j]);
2053 for (k = j; k < stmt->n_arg - 1; ++k)
2054 stmt->args[k] = stmt->args[k + 1];
2055 stmt->n_arg--;
2057 map = isl_set_unwrap(stmt->domain);
2058 map = isl_map_project_out(map, isl_dim_out, j, 1);
2059 stmt->domain = isl_map_wrap(map);
2061 if (!stmt->domain || !stmt->args[i]->acc.access)
2062 return pet_stmt_free(stmt);
2064 return stmt;
2067 /* Look for any pair of filters that access the same filter variable
2068 * and that have the same filter value and merge them into a single
2069 * filter with as filter access relation the union of the filter access
2070 * relations.
2072 static struct pet_stmt *stmt_merge_filters(struct pet_stmt *stmt)
2074 int i, j;
2075 isl_space *space_i, *space_j;
2077 if (!stmt)
2078 return NULL;
2079 if (stmt->n_arg <= 1)
2080 return stmt;
2082 for (i = 0; i < stmt->n_arg - 1; ++i) {
2083 if (stmt->args[i]->type != pet_expr_access)
2084 continue;
2085 if (pet_expr_is_affine(stmt->args[i]))
2086 continue;
2088 space_i = isl_map_get_space(stmt->args[i]->acc.access);
2090 for (j = stmt->n_arg - 1; j > i; --j) {
2091 int eq;
2093 if (stmt->args[j]->type != pet_expr_access)
2094 continue;
2095 if (pet_expr_is_affine(stmt->args[j]))
2096 continue;
2098 space_j = isl_map_get_space(stmt->args[j]->acc.access);
2100 eq = isl_space_is_equal(space_i, space_j);
2101 if (eq >= 0 && eq)
2102 eq = equal_filter_values(stmt->domain, i, j);
2103 if (eq >= 0 && eq)
2104 stmt = merge_filter_pair(stmt, i, j);
2106 isl_space_free(space_j);
2108 if (eq < 0 || !stmt)
2109 break;
2112 isl_space_free(space_i);
2114 if (j > i || !stmt)
2115 return pet_stmt_free(stmt);
2118 return stmt;
2121 /* Look for any pair of filters that access the same filter variable
2122 * and that have the same filter value and merge them into a single
2123 * filter with as filter access relation the union of the filter access
2124 * relations.
2126 struct pet_scop *pet_scop_merge_filters(struct pet_scop *scop)
2128 int i;
2130 if (!scop)
2131 return NULL;
2133 for (i = 0; i < scop->n_stmt; ++i) {
2134 scop->stmts[i] = stmt_merge_filters(scop->stmts[i]);
2135 if (!scop->stmts[i])
2136 return pet_scop_free(scop);
2139 return scop;
2142 /* Add all parameters in "expr" to "dim" and return the result.
2144 static __isl_give isl_space *expr_collect_params(struct pet_expr *expr,
2145 __isl_take isl_space *dim)
2147 int i;
2149 if (!expr)
2150 goto error;
2151 for (i = 0; i < expr->n_arg; ++i)
2153 dim = expr_collect_params(expr->args[i], dim);
2155 if (expr->type == pet_expr_access)
2156 dim = isl_space_align_params(dim,
2157 isl_map_get_space(expr->acc.access));
2159 return dim;
2160 error:
2161 isl_space_free(dim);
2162 return pet_expr_free(expr);
2165 /* Add all parameters in "stmt" to "dim" and return the result.
2167 static __isl_give isl_space *stmt_collect_params(struct pet_stmt *stmt,
2168 __isl_take isl_space *dim)
2170 if (!stmt)
2171 goto error;
2173 dim = isl_space_align_params(dim, isl_set_get_space(stmt->domain));
2174 dim = isl_space_align_params(dim, isl_map_get_space(stmt->schedule));
2175 dim = expr_collect_params(stmt->body, dim);
2177 return dim;
2178 error:
2179 isl_space_free(dim);
2180 return pet_stmt_free(stmt);
2183 /* Add all parameters in "array" to "dim" and return the result.
2185 static __isl_give isl_space *array_collect_params(struct pet_array *array,
2186 __isl_take isl_space *dim)
2188 if (!array)
2189 goto error;
2191 dim = isl_space_align_params(dim, isl_set_get_space(array->context));
2192 dim = isl_space_align_params(dim, isl_set_get_space(array->extent));
2194 return dim;
2195 error:
2196 isl_space_free(dim);
2197 return pet_array_free(array);
2200 /* Add all parameters in "scop" to "dim" and return the result.
2202 static __isl_give isl_space *scop_collect_params(struct pet_scop *scop,
2203 __isl_take isl_space *dim)
2205 int i;
2207 if (!scop)
2208 goto error;
2210 for (i = 0; i < scop->n_array; ++i)
2211 dim = array_collect_params(scop->arrays[i], dim);
2213 for (i = 0; i < scop->n_stmt; ++i)
2214 dim = stmt_collect_params(scop->stmts[i], dim);
2216 return dim;
2217 error:
2218 isl_space_free(dim);
2219 return pet_scop_free(scop);
2222 /* Add all parameters in "dim" to all access relations in "expr".
2224 static struct pet_expr *expr_propagate_params(struct pet_expr *expr,
2225 __isl_take isl_space *dim)
2227 int i;
2229 if (!expr)
2230 goto error;
2232 for (i = 0; i < expr->n_arg; ++i) {
2233 expr->args[i] =
2234 expr_propagate_params(expr->args[i],
2235 isl_space_copy(dim));
2236 if (!expr->args[i])
2237 goto error;
2240 if (expr->type == pet_expr_access) {
2241 expr->acc.access = isl_map_align_params(expr->acc.access,
2242 isl_space_copy(dim));
2243 if (!expr->acc.access)
2244 goto error;
2247 isl_space_free(dim);
2248 return expr;
2249 error:
2250 isl_space_free(dim);
2251 return pet_expr_free(expr);
2254 /* Add all parameters in "dim" to the domain, schedule and
2255 * all access relations in "stmt".
2257 static struct pet_stmt *stmt_propagate_params(struct pet_stmt *stmt,
2258 __isl_take isl_space *dim)
2260 if (!stmt)
2261 goto error;
2263 stmt->domain = isl_set_align_params(stmt->domain, isl_space_copy(dim));
2264 stmt->schedule = isl_map_align_params(stmt->schedule,
2265 isl_space_copy(dim));
2266 stmt->body = expr_propagate_params(stmt->body, isl_space_copy(dim));
2268 if (!stmt->domain || !stmt->schedule || !stmt->body)
2269 goto error;
2271 isl_space_free(dim);
2272 return stmt;
2273 error:
2274 isl_space_free(dim);
2275 return pet_stmt_free(stmt);
2278 /* Add all parameters in "dim" to "array".
2280 static struct pet_array *array_propagate_params(struct pet_array *array,
2281 __isl_take isl_space *dim)
2283 if (!array)
2284 goto error;
2286 array->context = isl_set_align_params(array->context,
2287 isl_space_copy(dim));
2288 array->extent = isl_set_align_params(array->extent,
2289 isl_space_copy(dim));
2290 if (array->value_bounds) {
2291 array->value_bounds = isl_set_align_params(array->value_bounds,
2292 isl_space_copy(dim));
2293 if (!array->value_bounds)
2294 goto error;
2297 if (!array->context || !array->extent)
2298 goto error;
2300 isl_space_free(dim);
2301 return array;
2302 error:
2303 isl_space_free(dim);
2304 return pet_array_free(array);
2307 /* Add all parameters in "dim" to "scop".
2309 static struct pet_scop *scop_propagate_params(struct pet_scop *scop,
2310 __isl_take isl_space *dim)
2312 int i;
2314 if (!scop)
2315 goto error;
2317 for (i = 0; i < scop->n_array; ++i) {
2318 scop->arrays[i] = array_propagate_params(scop->arrays[i],
2319 isl_space_copy(dim));
2320 if (!scop->arrays[i])
2321 goto error;
2324 for (i = 0; i < scop->n_stmt; ++i) {
2325 scop->stmts[i] = stmt_propagate_params(scop->stmts[i],
2326 isl_space_copy(dim));
2327 if (!scop->stmts[i])
2328 goto error;
2331 isl_space_free(dim);
2332 return scop;
2333 error:
2334 isl_space_free(dim);
2335 return pet_scop_free(scop);
2338 /* Update all isl_sets and isl_maps in "scop" such that they all
2339 * have the same parameters.
2341 struct pet_scop *pet_scop_align_params(struct pet_scop *scop)
2343 isl_space *dim;
2345 if (!scop)
2346 return NULL;
2348 dim = isl_set_get_space(scop->context);
2349 dim = scop_collect_params(scop, dim);
2351 scop->context = isl_set_align_params(scop->context, isl_space_copy(dim));
2352 scop = scop_propagate_params(scop, dim);
2354 return scop;
2357 /* Check if the given access relation accesses a (0D) array that corresponds
2358 * to one of the parameters in "dim". If so, replace the array access
2359 * by an access to the set of integers with as index (and value)
2360 * that parameter.
2362 static __isl_give isl_map *access_detect_parameter(__isl_take isl_map *access,
2363 __isl_take isl_space *dim)
2365 isl_id *array_id = NULL;
2366 int pos = -1;
2368 if (isl_map_has_tuple_id(access, isl_dim_out)) {
2369 array_id = isl_map_get_tuple_id(access, isl_dim_out);
2370 pos = isl_space_find_dim_by_id(dim, isl_dim_param, array_id);
2372 isl_space_free(dim);
2374 if (pos < 0) {
2375 isl_id_free(array_id);
2376 return access;
2379 pos = isl_map_find_dim_by_id(access, isl_dim_param, array_id);
2380 if (pos < 0) {
2381 access = isl_map_insert_dims(access, isl_dim_param, 0, 1);
2382 access = isl_map_set_dim_id(access, isl_dim_param, 0, array_id);
2383 pos = 0;
2384 } else
2385 isl_id_free(array_id);
2387 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
2388 access = isl_map_equate(access, isl_dim_param, pos, isl_dim_out, 0);
2390 return access;
2393 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2394 * in "dim" by a value equal to the corresponding parameter.
2396 static struct pet_expr *expr_detect_parameter_accesses(struct pet_expr *expr,
2397 __isl_take isl_space *dim)
2399 int i;
2401 if (!expr)
2402 goto error;
2404 for (i = 0; i < expr->n_arg; ++i) {
2405 expr->args[i] =
2406 expr_detect_parameter_accesses(expr->args[i],
2407 isl_space_copy(dim));
2408 if (!expr->args[i])
2409 goto error;
2412 if (expr->type == pet_expr_access) {
2413 expr->acc.access = access_detect_parameter(expr->acc.access,
2414 isl_space_copy(dim));
2415 if (!expr->acc.access)
2416 goto error;
2419 isl_space_free(dim);
2420 return expr;
2421 error:
2422 isl_space_free(dim);
2423 return pet_expr_free(expr);
2426 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2427 * in "dim" by a value equal to the corresponding parameter.
2429 static struct pet_stmt *stmt_detect_parameter_accesses(struct pet_stmt *stmt,
2430 __isl_take isl_space *dim)
2432 if (!stmt)
2433 goto error;
2435 stmt->body = expr_detect_parameter_accesses(stmt->body,
2436 isl_space_copy(dim));
2438 if (!stmt->domain || !stmt->schedule || !stmt->body)
2439 goto error;
2441 isl_space_free(dim);
2442 return stmt;
2443 error:
2444 isl_space_free(dim);
2445 return pet_stmt_free(stmt);
2448 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2449 * in "dim" by a value equal to the corresponding parameter.
2451 static struct pet_scop *scop_detect_parameter_accesses(struct pet_scop *scop,
2452 __isl_take isl_space *dim)
2454 int i;
2456 if (!scop)
2457 goto error;
2459 for (i = 0; i < scop->n_stmt; ++i) {
2460 scop->stmts[i] = stmt_detect_parameter_accesses(scop->stmts[i],
2461 isl_space_copy(dim));
2462 if (!scop->stmts[i])
2463 goto error;
2466 isl_space_free(dim);
2467 return scop;
2468 error:
2469 isl_space_free(dim);
2470 return pet_scop_free(scop);
2473 /* Replace all accesses to (0D) arrays that correspond to any of
2474 * the parameters used in "scop" by a value equal
2475 * to the corresponding parameter.
2477 struct pet_scop *pet_scop_detect_parameter_accesses(struct pet_scop *scop)
2479 isl_space *dim;
2481 if (!scop)
2482 return NULL;
2484 dim = isl_set_get_space(scop->context);
2485 dim = scop_collect_params(scop, dim);
2487 scop = scop_detect_parameter_accesses(scop, dim);
2489 return scop;
2492 /* Add all read access relations (if "read" is set) and/or all write
2493 * access relations (if "write" is set) to "accesses" and return the result.
2495 static __isl_give isl_union_map *expr_collect_accesses(struct pet_expr *expr,
2496 int read, int write, __isl_take isl_union_map *accesses)
2498 int i;
2499 isl_id *id;
2500 isl_space *dim;
2502 if (!expr)
2503 return NULL;
2505 for (i = 0; i < expr->n_arg; ++i)
2506 accesses = expr_collect_accesses(expr->args[i],
2507 read, write, accesses);
2509 if (expr->type == pet_expr_access &&
2510 isl_map_has_tuple_id(expr->acc.access, isl_dim_out) &&
2511 ((read && expr->acc.read) || (write && expr->acc.write)))
2512 accesses = isl_union_map_add_map(accesses,
2513 isl_map_copy(expr->acc.access));
2515 return accesses;
2518 /* Collect and return all read access relations (if "read" is set)
2519 * and/or all write * access relations (if "write" is set) in "stmt".
2521 static __isl_give isl_union_map *stmt_collect_accesses(struct pet_stmt *stmt,
2522 int read, int write, __isl_take isl_space *dim)
2524 isl_union_map *accesses;
2526 if (!stmt)
2527 return NULL;
2529 accesses = isl_union_map_empty(dim);
2530 accesses = expr_collect_accesses(stmt->body, read, write, accesses);
2531 accesses = isl_union_map_intersect_domain(accesses,
2532 isl_union_set_from_set(isl_set_copy(stmt->domain)));
2534 return accesses;
2537 /* Collect and return all read access relations (if "read" is set)
2538 * and/or all write * access relations (if "write" is set) in "scop".
2540 static __isl_give isl_union_map *scop_collect_accesses(struct pet_scop *scop,
2541 int read, int write)
2543 int i;
2544 isl_union_map *accesses;
2546 if (!scop)
2547 return NULL;
2549 accesses = isl_union_map_empty(isl_set_get_space(scop->context));
2551 for (i = 0; i < scop->n_stmt; ++i) {
2552 isl_union_map *accesses_i;
2553 isl_space *dim = isl_set_get_space(scop->context);
2554 accesses_i = stmt_collect_accesses(scop->stmts[i],
2555 read, write, dim);
2556 accesses = isl_union_map_union(accesses, accesses_i);
2559 return accesses;
2562 __isl_give isl_union_map *pet_scop_collect_reads(struct pet_scop *scop)
2564 return scop_collect_accesses(scop, 1, 0);
2567 __isl_give isl_union_map *pet_scop_collect_writes(struct pet_scop *scop)
2569 return scop_collect_accesses(scop, 0, 1);
2572 /* Collect and return the union of iteration domains in "scop".
2574 __isl_give isl_union_set *pet_scop_collect_domains(struct pet_scop *scop)
2576 int i;
2577 isl_set *domain_i;
2578 isl_union_set *domain;
2580 if (!scop)
2581 return NULL;
2583 domain = isl_union_set_empty(isl_set_get_space(scop->context));
2585 for (i = 0; i < scop->n_stmt; ++i) {
2586 domain_i = isl_set_copy(scop->stmts[i]->domain);
2587 domain = isl_union_set_add_set(domain, domain_i);
2590 return domain;
2593 /* Collect and return the schedules of the statements in "scop".
2594 * The range is normalized to the maximal number of scheduling
2595 * dimensions.
2597 __isl_give isl_union_map *pet_scop_collect_schedule(struct pet_scop *scop)
2599 int i, j;
2600 isl_map *schedule_i;
2601 isl_union_map *schedule;
2602 int depth, max_depth = 0;
2604 if (!scop)
2605 return NULL;
2607 schedule = isl_union_map_empty(isl_set_get_space(scop->context));
2609 for (i = 0; i < scop->n_stmt; ++i) {
2610 depth = isl_map_dim(scop->stmts[i]->schedule, isl_dim_out);
2611 if (depth > max_depth)
2612 max_depth = depth;
2615 for (i = 0; i < scop->n_stmt; ++i) {
2616 schedule_i = isl_map_copy(scop->stmts[i]->schedule);
2617 depth = isl_map_dim(schedule_i, isl_dim_out);
2618 schedule_i = isl_map_add_dims(schedule_i, isl_dim_out,
2619 max_depth - depth);
2620 for (j = depth; j < max_depth; ++j)
2621 schedule_i = isl_map_fix_si(schedule_i,
2622 isl_dim_out, j, 0);
2623 schedule = isl_union_map_add_map(schedule, schedule_i);
2626 return schedule;
2629 /* Does expression "expr" write to "id"?
2631 static int expr_writes(struct pet_expr *expr, __isl_keep isl_id *id)
2633 int i;
2634 isl_id *write_id;
2636 for (i = 0; i < expr->n_arg; ++i) {
2637 int writes = expr_writes(expr->args[i], id);
2638 if (writes < 0 || writes)
2639 return writes;
2642 if (expr->type != pet_expr_access)
2643 return 0;
2644 if (!expr->acc.write)
2645 return 0;
2646 if (!isl_map_has_tuple_id(expr->acc.access, isl_dim_out))
2647 return 0;
2649 write_id = isl_map_get_tuple_id(expr->acc.access, isl_dim_out);
2650 isl_id_free(write_id);
2652 if (!write_id)
2653 return -1;
2655 return write_id == id;
2658 /* Does statement "stmt" write to "id"?
2660 static int stmt_writes(struct pet_stmt *stmt, __isl_keep isl_id *id)
2662 return expr_writes(stmt->body, id);
2665 /* Is there any write access in "scop" that accesses "id"?
2667 int pet_scop_writes(struct pet_scop *scop, __isl_keep isl_id *id)
2669 int i;
2671 if (!scop)
2672 return -1;
2674 for (i = 0; i < scop->n_stmt; ++i) {
2675 int writes = stmt_writes(scop->stmts[i], id);
2676 if (writes < 0 || writes)
2677 return writes;
2680 return 0;
2683 /* Reset the user pointer on all parameter ids in "set".
2685 static __isl_give isl_set *set_anonymize(__isl_take isl_set *set)
2687 int i, n;
2689 n = isl_set_dim(set, isl_dim_param);
2690 for (i = 0; i < n; ++i) {
2691 isl_id *id = isl_set_get_dim_id(set, isl_dim_param, i);
2692 const char *name = isl_id_get_name(id);
2693 set = isl_set_set_dim_name(set, isl_dim_param, i, name);
2694 isl_id_free(id);
2697 return set;
2700 /* Reset the user pointer on all parameter ids in "map".
2702 static __isl_give isl_map *map_anonymize(__isl_take isl_map *map)
2704 int i, n;
2706 n = isl_map_dim(map, isl_dim_param);
2707 for (i = 0; i < n; ++i) {
2708 isl_id *id = isl_map_get_dim_id(map, isl_dim_param, i);
2709 const char *name = isl_id_get_name(id);
2710 map = isl_map_set_dim_name(map, isl_dim_param, i, name);
2711 isl_id_free(id);
2714 return map;
2717 /* Reset the user pointer on all parameter ids in "array".
2719 static struct pet_array *array_anonymize(struct pet_array *array)
2721 if (!array)
2722 return NULL;
2724 array->context = set_anonymize(array->context);
2725 array->extent = set_anonymize(array->extent);
2726 if (!array->context || !array->extent)
2727 return pet_array_free(array);
2729 return array;
2732 /* Reset the user pointer on all parameter ids in "access".
2734 static __isl_give isl_map *access_anonymize(__isl_take isl_map *access,
2735 void *user)
2737 access = map_anonymize(access);
2739 return access;
2742 /* Reset the user pointer on all parameter ids in "stmt".
2744 static struct pet_stmt *stmt_anonymize(struct pet_stmt *stmt)
2746 int i;
2747 isl_space *space;
2748 isl_set *domain;
2750 if (!stmt)
2751 return NULL;
2753 stmt->domain = set_anonymize(stmt->domain);
2754 stmt->schedule = map_anonymize(stmt->schedule);
2755 if (!stmt->domain || !stmt->schedule)
2756 return pet_stmt_free(stmt);
2758 for (i = 0; i < stmt->n_arg; ++i) {
2759 stmt->args[i] = pet_expr_foreach_access(stmt->args[i],
2760 &access_anonymize, NULL);
2761 if (!stmt->args[i])
2762 return pet_stmt_free(stmt);
2765 stmt->body = pet_expr_foreach_access(stmt->body,
2766 &access_anonymize, NULL);
2767 if (!stmt->body)
2768 return pet_stmt_free(stmt);
2770 return stmt;
2773 /* Reset the user pointer on all parameter ids in "scop".
2775 struct pet_scop *pet_scop_anonymize(struct pet_scop *scop)
2777 int i;
2779 if (!scop)
2780 return NULL;
2782 scop->context = set_anonymize(scop->context);
2783 scop->context_value = set_anonymize(scop->context_value);
2784 if (!scop->context || !scop->context_value)
2785 return pet_scop_free(scop);
2787 for (i = 0; i < scop->n_array; ++i) {
2788 scop->arrays[i] = array_anonymize(scop->arrays[i]);
2789 if (!scop->arrays[i])
2790 return pet_scop_free(scop);
2793 for (i = 0; i < scop->n_stmt; ++i) {
2794 scop->stmts[i] = stmt_anonymize(scop->stmts[i]);
2795 if (!scop->stmts[i])
2796 return pet_scop_free(scop);
2799 return scop;
2802 /* Given a set "domain", return a wrapped relation with the given set
2803 * as domain and a range of dimension "n_arg", where each coordinate
2804 * is either unbounded or, if the corresponding element of args is of
2805 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
2807 static __isl_give isl_set *apply_value_bounds(__isl_take isl_set *domain,
2808 unsigned n_arg, struct pet_expr **args,
2809 __isl_keep isl_union_map *value_bounds)
2811 int i;
2812 isl_map *map;
2813 isl_space *space;
2814 isl_ctx *ctx = isl_set_get_ctx(domain);
2816 map = isl_map_from_domain(domain);
2817 space = isl_map_get_space(map);
2818 space = isl_space_add_dims(space, isl_dim_out, 1);
2820 for (i = 0; i < n_arg; ++i) {
2821 isl_map *map_i;
2822 struct pet_expr *arg = args[i];
2823 isl_id *id;
2824 isl_space *space2;
2826 map_i = isl_map_universe(isl_space_copy(space));
2827 if (arg->type == pet_expr_access) {
2828 isl_map *vb;
2829 id = isl_map_get_tuple_id(arg->acc.access, isl_dim_out);
2830 space2 = isl_space_alloc(ctx, 0, 0, 1);
2831 space2 = isl_space_set_tuple_id(space2, isl_dim_in, id);
2832 vb = isl_union_map_extract_map(value_bounds, space2);
2833 if (!isl_map_plain_is_empty(vb))
2834 map_i = isl_map_intersect_range(map_i,
2835 isl_map_range(vb));
2836 else
2837 isl_map_free(vb);
2839 map = isl_map_flat_range_product(map, map_i);
2841 isl_space_free(space);
2843 return isl_map_wrap(map);
2846 /* Data used in access_gist() callback.
2848 struct pet_access_gist_data {
2849 isl_set *domain;
2850 isl_union_map *value_bounds;
2853 /* Given an expression "expr" of type pet_expr_access, compute
2854 * the gist of the associated access relation with respect to
2855 * data->domain and the bounds on the values of the arguments
2856 * of the expression.
2858 static struct pet_expr *access_gist(struct pet_expr *expr, void *user)
2860 struct pet_access_gist_data *data = user;
2861 isl_set *domain;
2863 domain = isl_set_copy(data->domain);
2864 if (expr->n_arg > 0)
2865 domain = apply_value_bounds(domain, expr->n_arg, expr->args,
2866 data->value_bounds);
2868 expr->acc.access = isl_map_gist_domain(expr->acc.access, domain);
2869 if (!expr->acc.access)
2870 return pet_expr_free(expr);
2872 return expr;
2875 /* Compute the gist of the iteration domain and all access relations
2876 * of "stmt" based on the constraints on the parameters specified by "context"
2877 * and the constraints on the values of nested accesses specified
2878 * by "value_bounds".
2880 static struct pet_stmt *stmt_gist(struct pet_stmt *stmt,
2881 __isl_keep isl_set *context, __isl_keep isl_union_map *value_bounds)
2883 int i;
2884 isl_space *space;
2885 isl_set *domain;
2886 struct pet_access_gist_data data;
2888 if (!stmt)
2889 return NULL;
2891 data.domain = isl_set_copy(stmt->domain);
2892 data.value_bounds = value_bounds;
2893 if (stmt->n_arg > 0)
2894 data.domain = isl_map_domain(isl_set_unwrap(data.domain));
2896 data.domain = isl_set_intersect_params(data.domain,
2897 isl_set_copy(context));
2899 for (i = 0; i < stmt->n_arg; ++i) {
2900 stmt->args[i] = pet_expr_foreach_access_expr(stmt->args[i],
2901 &access_gist, &data);
2902 if (!stmt->args[i])
2903 goto error;
2906 stmt->body = pet_expr_foreach_access_expr(stmt->body,
2907 &access_gist, &data);
2908 if (!stmt->body)
2909 goto error;
2911 isl_set_free(data.domain);
2913 space = isl_set_get_space(stmt->domain);
2914 if (isl_space_is_wrapping(space))
2915 space = isl_space_domain(isl_space_unwrap(space));
2916 domain = isl_set_universe(space);
2917 domain = isl_set_intersect_params(domain, isl_set_copy(context));
2918 if (stmt->n_arg > 0)
2919 domain = apply_value_bounds(domain, stmt->n_arg, stmt->args,
2920 value_bounds);
2921 stmt->domain = isl_set_gist(stmt->domain, domain);
2922 if (!stmt->domain)
2923 return pet_stmt_free(stmt);
2925 return stmt;
2926 error:
2927 isl_set_free(data.domain);
2928 return pet_stmt_free(stmt);
2931 /* Compute the gist of the extent of the array
2932 * based on the constraints on the parameters specified by "context".
2934 static struct pet_array *array_gist(struct pet_array *array,
2935 __isl_keep isl_set *context)
2937 if (!array)
2938 return NULL;
2940 array->extent = isl_set_gist_params(array->extent,
2941 isl_set_copy(context));
2942 if (!array->extent)
2943 return pet_array_free(array);
2945 return array;
2948 /* Compute the gist of all sets and relations in "scop"
2949 * based on the constraints on the parameters specified by "scop->context"
2950 * and the constraints on the values of nested accesses specified
2951 * by "value_bounds".
2953 struct pet_scop *pet_scop_gist(struct pet_scop *scop,
2954 __isl_keep isl_union_map *value_bounds)
2956 int i;
2958 if (!scop)
2959 return NULL;
2961 scop->context = isl_set_coalesce(scop->context);
2962 if (!scop->context)
2963 return pet_scop_free(scop);
2965 for (i = 0; i < scop->n_array; ++i) {
2966 scop->arrays[i] = array_gist(scop->arrays[i], scop->context);
2967 if (!scop->arrays[i])
2968 return pet_scop_free(scop);
2971 for (i = 0; i < scop->n_stmt; ++i) {
2972 scop->stmts[i] = stmt_gist(scop->stmts[i], scop->context,
2973 value_bounds);
2974 if (!scop->stmts[i])
2975 return pet_scop_free(scop);
2978 return scop;
2981 /* Intersect the context of "scop" with "context".
2982 * To ensure that we don't introduce any unnamed parameters in
2983 * the context of "scop", we first remove the unnamed parameters
2984 * from "context".
2986 struct pet_scop *pet_scop_restrict_context(struct pet_scop *scop,
2987 __isl_take isl_set *context)
2989 if (!scop)
2990 goto error;
2992 context = set_project_out_unnamed_params(context);
2993 scop->context = isl_set_intersect(scop->context, context);
2994 if (!scop->context)
2995 return pet_scop_free(scop);
2997 return scop;
2998 error:
2999 isl_set_free(context);
3000 return pet_scop_free(scop);
3003 /* Drop the current context of "scop". That is, replace the context
3004 * by a universal set.
3006 struct pet_scop *pet_scop_reset_context(struct pet_scop *scop)
3008 isl_space *space;
3010 if (!scop)
3011 return NULL;
3013 space = isl_set_get_space(scop->context);
3014 isl_set_free(scop->context);
3015 scop->context = isl_set_universe(space);
3016 if (!scop->context)
3017 return pet_scop_free(scop);
3019 return scop;