add support for (single) declarations
[pet.git] / scop.c
blobfda228dc0a17a9a01a429e9ab64029619b4e132d
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_mod] = "%",
62 [pet_op_eq] = "==",
63 [pet_op_le] = "<=",
64 [pet_op_lt] = "<",
65 [pet_op_gt] = ">",
66 [pet_op_minus] = "-",
67 [pet_op_post_inc] = "++",
68 [pet_op_post_dec] = "--",
69 [pet_op_pre_inc] = "++",
70 [pet_op_pre_dec] = "--",
71 [pet_op_address_of] = "&",
72 [pet_op_kill] = "kill"
75 /* pet_scop with extra information that is only used during parsing.
77 * In particular, we keep track of conditions under which we want
78 * to skip the rest of the current loop iteration (skip[pet_skip_now])
79 * and of conditions under which we want to skip subsequent
80 * loop iterations (skip[pet_skip_later]).
82 * The conditions are represented either by a variable, which
83 * is assumed to attain values zero and one, or by a boolean affine
84 * expression. The condition holds if the variable has value one
85 * or if the affine expression has value one (typically for only
86 * part of the parameter space).
88 * A missing condition (skip[type] == NULL) means that we don't want
89 * to skip anything.
91 struct pet_scop_ext {
92 struct pet_scop scop;
94 isl_set *skip[2];
97 const char *pet_op_str(enum pet_op_type op)
99 return op_str[op];
102 int pet_op_is_inc_dec(enum pet_op_type op)
104 return op == pet_op_post_inc || op == pet_op_post_dec ||
105 op == pet_op_pre_inc || op == pet_op_pre_dec;
108 const char *pet_type_str(enum pet_expr_type type)
110 return type_str[type];
113 enum pet_op_type pet_str_op(const char *str)
115 int i;
117 for (i = 0; i < ARRAY_SIZE(op_str); ++i)
118 if (!strcmp(op_str[i], str))
119 return i;
121 return -1;
124 enum pet_expr_type pet_str_type(const char *str)
126 int i;
128 for (i = 0; i < ARRAY_SIZE(type_str); ++i)
129 if (!strcmp(type_str[i], str))
130 return i;
132 return -1;
135 /* Construct a pet_expr from an access relation.
136 * By default, it is considered to be a read access.
138 struct pet_expr *pet_expr_from_access(__isl_take isl_map *access)
140 isl_ctx *ctx = isl_map_get_ctx(access);
141 struct pet_expr *expr;
143 if (!access)
144 return NULL;
145 expr = isl_calloc_type(ctx, struct pet_expr);
146 if (!expr)
147 goto error;
149 expr->type = pet_expr_access;
150 expr->acc.access = access;
151 expr->acc.read = 1;
152 expr->acc.write = 0;
154 return expr;
155 error:
156 isl_map_free(access);
157 return NULL;
160 /* Construct a pet_expr that kills the elements specified by "access".
162 struct pet_expr *pet_expr_kill_from_access(__isl_take isl_map *access)
164 isl_ctx *ctx;
165 struct pet_expr *expr;
167 ctx = isl_map_get_ctx(access);
168 expr = pet_expr_from_access(access);
169 if (!expr)
170 return NULL;
171 expr->acc.read = 0;
172 return pet_expr_new_unary(ctx, pet_op_kill, expr);
175 /* Construct a unary pet_expr that performs "op" on "arg".
177 struct pet_expr *pet_expr_new_unary(isl_ctx *ctx, enum pet_op_type op,
178 struct pet_expr *arg)
180 struct pet_expr *expr;
182 if (!arg)
183 goto error;
184 expr = isl_alloc_type(ctx, struct pet_expr);
185 if (!expr)
186 goto error;
188 expr->type = pet_expr_unary;
189 expr->op = op;
190 expr->n_arg = 1;
191 expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
192 if (!expr->args)
193 goto error;
194 expr->args[pet_un_arg] = arg;
196 return expr;
197 error:
198 pet_expr_free(arg);
199 return NULL;
202 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
204 struct pet_expr *pet_expr_new_binary(isl_ctx *ctx, enum pet_op_type op,
205 struct pet_expr *lhs, struct pet_expr *rhs)
207 struct pet_expr *expr;
209 if (!lhs || !rhs)
210 goto error;
211 expr = isl_alloc_type(ctx, struct pet_expr);
212 if (!expr)
213 goto error;
215 expr->type = pet_expr_binary;
216 expr->op = op;
217 expr->n_arg = 2;
218 expr->args = isl_calloc_array(ctx, struct pet_expr *, 2);
219 if (!expr->args)
220 goto error;
221 expr->args[pet_bin_lhs] = lhs;
222 expr->args[pet_bin_rhs] = rhs;
224 return expr;
225 error:
226 pet_expr_free(lhs);
227 pet_expr_free(rhs);
228 return NULL;
231 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
233 struct pet_expr *pet_expr_new_ternary(isl_ctx *ctx, struct pet_expr *cond,
234 struct pet_expr *lhs, struct pet_expr *rhs)
236 struct pet_expr *expr;
238 if (!cond || !lhs || !rhs)
239 goto error;
240 expr = isl_alloc_type(ctx, struct pet_expr);
241 if (!expr)
242 goto error;
244 expr->type = pet_expr_ternary;
245 expr->n_arg = 3;
246 expr->args = isl_calloc_array(ctx, struct pet_expr *, 3);
247 if (!expr->args)
248 goto error;
249 expr->args[pet_ter_cond] = cond;
250 expr->args[pet_ter_true] = lhs;
251 expr->args[pet_ter_false] = rhs;
253 return expr;
254 error:
255 pet_expr_free(cond);
256 pet_expr_free(lhs);
257 pet_expr_free(rhs);
258 return NULL;
261 /* Construct a call pet_expr that calls function "name" with "n_arg"
262 * arguments. The caller is responsible for filling in the arguments.
264 struct pet_expr *pet_expr_new_call(isl_ctx *ctx, const char *name,
265 unsigned n_arg)
267 struct pet_expr *expr;
269 expr = isl_alloc_type(ctx, struct pet_expr);
270 if (!expr)
271 return NULL;
273 expr->type = pet_expr_call;
274 expr->n_arg = n_arg;
275 expr->name = strdup(name);
276 expr->args = isl_calloc_array(ctx, struct pet_expr *, n_arg);
277 if (!expr->name || !expr->args)
278 return pet_expr_free(expr);
280 return expr;
283 /* Construct a pet_expr that represents the double "d".
285 struct pet_expr *pet_expr_new_double(isl_ctx *ctx, double d)
287 struct pet_expr *expr;
289 expr = isl_calloc_type(ctx, struct pet_expr);
290 if (!expr)
291 return NULL;
293 expr->type = pet_expr_double;
294 expr->d = d;
296 return expr;
299 void *pet_expr_free(struct pet_expr *expr)
301 int i;
303 if (!expr)
304 return NULL;
306 for (i = 0; i < expr->n_arg; ++i)
307 pet_expr_free(expr->args[i]);
308 free(expr->args);
310 switch (expr->type) {
311 case pet_expr_access:
312 isl_map_free(expr->acc.access);
313 break;
314 case pet_expr_call:
315 free(expr->name);
316 break;
317 case pet_expr_double:
318 case pet_expr_unary:
319 case pet_expr_binary:
320 case pet_expr_ternary:
321 break;
324 free(expr);
325 return NULL;
328 static void expr_dump(struct pet_expr *expr, int indent)
330 int i;
332 if (!expr)
333 return;
335 fprintf(stderr, "%*s", indent, "");
337 switch (expr->type) {
338 case pet_expr_double:
339 fprintf(stderr, "%g\n", expr->d);
340 break;
341 case pet_expr_access:
342 isl_map_dump(expr->acc.access);
343 fprintf(stderr, "%*sread: %d\n", indent + 2,
344 "", expr->acc.read);
345 fprintf(stderr, "%*swrite: %d\n", indent + 2,
346 "", expr->acc.write);
347 for (i = 0; i < expr->n_arg; ++i)
348 expr_dump(expr->args[i], indent + 2);
349 break;
350 case pet_expr_unary:
351 fprintf(stderr, "%s\n", op_str[expr->op]);
352 expr_dump(expr->args[pet_un_arg], indent + 2);
353 break;
354 case pet_expr_binary:
355 fprintf(stderr, "%s\n", op_str[expr->op]);
356 expr_dump(expr->args[pet_bin_lhs], indent + 2);
357 expr_dump(expr->args[pet_bin_rhs], indent + 2);
358 break;
359 case pet_expr_ternary:
360 fprintf(stderr, "?:\n");
361 expr_dump(expr->args[pet_ter_cond], indent + 2);
362 expr_dump(expr->args[pet_ter_true], indent + 2);
363 expr_dump(expr->args[pet_ter_false], indent + 2);
364 break;
365 case pet_expr_call:
366 fprintf(stderr, "%s/%d\n", expr->name, expr->n_arg);
367 for (i = 0; i < expr->n_arg; ++i)
368 expr_dump(expr->args[i], indent + 2);
369 break;
373 void pet_expr_dump(struct pet_expr *expr)
375 expr_dump(expr, 0);
378 /* Does "expr" represent an access to an unnamed space, i.e.,
379 * does it represent an affine expression?
381 int pet_expr_is_affine(struct pet_expr *expr)
383 int has_id;
385 if (!expr)
386 return -1;
387 if (expr->type != pet_expr_access)
388 return 0;
390 has_id = isl_map_has_tuple_id(expr->acc.access, isl_dim_out);
391 if (has_id < 0)
392 return -1;
394 return !has_id;
397 /* Return 1 if the two pet_exprs are equivalent.
399 int pet_expr_is_equal(struct pet_expr *expr1, struct pet_expr *expr2)
401 int i;
403 if (!expr1 || !expr2)
404 return 0;
406 if (expr1->type != expr2->type)
407 return 0;
408 if (expr1->n_arg != expr2->n_arg)
409 return 0;
410 for (i = 0; i < expr1->n_arg; ++i)
411 if (!pet_expr_is_equal(expr1->args[i], expr2->args[i]))
412 return 0;
413 switch (expr1->type) {
414 case pet_expr_double:
415 if (expr1->d != expr2->d)
416 return 0;
417 break;
418 case pet_expr_access:
419 if (expr1->acc.read != expr2->acc.read)
420 return 0;
421 if (expr1->acc.write != expr2->acc.write)
422 return 0;
423 if (!expr1->acc.access || !expr2->acc.access)
424 return 0;
425 if (!isl_map_is_equal(expr1->acc.access, expr2->acc.access))
426 return 0;
427 break;
428 case pet_expr_unary:
429 case pet_expr_binary:
430 case pet_expr_ternary:
431 if (expr1->op != expr2->op)
432 return 0;
433 break;
434 case pet_expr_call:
435 if (strcmp(expr1->name, expr2->name))
436 return 0;
437 break;
440 return 1;
443 /* Add extra conditions on the parameters to all access relations in "expr".
445 struct pet_expr *pet_expr_restrict(struct pet_expr *expr,
446 __isl_take isl_set *cond)
448 int i;
450 if (!expr)
451 goto error;
453 for (i = 0; i < expr->n_arg; ++i) {
454 expr->args[i] = pet_expr_restrict(expr->args[i],
455 isl_set_copy(cond));
456 if (!expr->args[i])
457 goto error;
460 if (expr->type == pet_expr_access) {
461 expr->acc.access = isl_map_intersect_params(expr->acc.access,
462 isl_set_copy(cond));
463 if (!expr->acc.access)
464 goto error;
467 isl_set_free(cond);
468 return expr;
469 error:
470 isl_set_free(cond);
471 return pet_expr_free(expr);
474 /* Modify all access relations in "expr" by calling "fn" on them.
476 struct pet_expr *pet_expr_foreach_access(struct pet_expr *expr,
477 __isl_give isl_map *(*fn)(__isl_take isl_map *access, void *user),
478 void *user)
480 int i;
482 if (!expr)
483 return NULL;
485 for (i = 0; i < expr->n_arg; ++i) {
486 expr->args[i] = pet_expr_foreach_access(expr->args[i], fn, user);
487 if (!expr->args[i])
488 return pet_expr_free(expr);
491 if (expr->type == pet_expr_access) {
492 expr->acc.access = fn(expr->acc.access, user);
493 if (!expr->acc.access)
494 return pet_expr_free(expr);
497 return expr;
500 /* Modify all expressions of type pet_expr_access in "expr"
501 * by calling "fn" on them.
503 struct pet_expr *pet_expr_foreach_access_expr(struct pet_expr *expr,
504 struct pet_expr *(*fn)(struct pet_expr *expr, void *user),
505 void *user)
507 int i;
509 if (!expr)
510 return NULL;
512 for (i = 0; i < expr->n_arg; ++i) {
513 expr->args[i] = pet_expr_foreach_access_expr(expr->args[i],
514 fn, user);
515 if (!expr->args[i])
516 return pet_expr_free(expr);
519 if (expr->type == pet_expr_access)
520 expr = fn(expr, user);
522 return expr;
525 /* Modify the given access relation based on the given iteration space
526 * transformation.
527 * If the access has any arguments then the domain of the access relation
528 * is a wrapped mapping from the iteration space to the space of
529 * argument values. We only need to change the domain of this wrapped
530 * mapping, so we extend the input transformation with an identity mapping
531 * on the space of argument values.
533 static __isl_give isl_map *update_domain(__isl_take isl_map *access,
534 void *user)
536 isl_map *update = user;
537 isl_space *dim;
539 update = isl_map_copy(update);
541 dim = isl_map_get_space(access);
542 dim = isl_space_domain(dim);
543 if (!isl_space_is_wrapping(dim))
544 isl_space_free(dim);
545 else {
546 isl_map *id;
547 dim = isl_space_unwrap(dim);
548 dim = isl_space_range(dim);
549 dim = isl_space_map_from_set(dim);
550 id = isl_map_identity(dim);
551 update = isl_map_product(update, id);
554 return isl_map_apply_domain(access, update);
557 /* Modify all access relations in "expr" based on the given iteration space
558 * transformation.
560 static struct pet_expr *expr_update_domain(struct pet_expr *expr,
561 __isl_take isl_map *update)
563 expr = pet_expr_foreach_access(expr, &update_domain, update);
564 isl_map_free(update);
565 return expr;
568 /* Construct a pet_stmt with given line number and statement
569 * number from a pet_expr.
570 * The initial iteration domain is the zero-dimensional universe.
571 * The name of the domain is given by "label" if it is non-NULL.
572 * Otherwise, the name is constructed as S_<id>.
573 * The domains of all access relations are modified to refer
574 * to the statement iteration domain.
576 struct pet_stmt *pet_stmt_from_pet_expr(isl_ctx *ctx, int line,
577 __isl_take isl_id *label, int id, struct pet_expr *expr)
579 struct pet_stmt *stmt;
580 isl_space *dim;
581 isl_set *dom;
582 isl_map *sched;
583 isl_map *add_name;
584 char name[50];
586 if (!expr)
587 goto error;
589 stmt = isl_calloc_type(ctx, struct pet_stmt);
590 if (!stmt)
591 goto error;
593 dim = isl_space_set_alloc(ctx, 0, 0);
594 if (label)
595 dim = isl_space_set_tuple_id(dim, isl_dim_set, label);
596 else {
597 snprintf(name, sizeof(name), "S_%d", id);
598 dim = isl_space_set_tuple_name(dim, isl_dim_set, name);
600 dom = isl_set_universe(isl_space_copy(dim));
601 sched = isl_map_from_domain(isl_set_copy(dom));
603 dim = isl_space_from_range(dim);
604 add_name = isl_map_universe(dim);
605 expr = expr_update_domain(expr, add_name);
607 stmt->line = line;
608 stmt->domain = dom;
609 stmt->schedule = sched;
610 stmt->body = expr;
612 if (!stmt->domain || !stmt->schedule || !stmt->body)
613 return pet_stmt_free(stmt);
615 return stmt;
616 error:
617 isl_id_free(label);
618 return pet_expr_free(expr);
621 void *pet_stmt_free(struct pet_stmt *stmt)
623 int i;
625 if (!stmt)
626 return NULL;
628 isl_set_free(stmt->domain);
629 isl_map_free(stmt->schedule);
630 pet_expr_free(stmt->body);
632 for (i = 0; i < stmt->n_arg; ++i)
633 pet_expr_free(stmt->args[i]);
634 free(stmt->args);
636 free(stmt);
637 return NULL;
640 static void stmt_dump(struct pet_stmt *stmt, int indent)
642 int i;
644 if (!stmt)
645 return;
647 fprintf(stderr, "%*s%d\n", indent, "", stmt->line);
648 fprintf(stderr, "%*s", indent, "");
649 isl_set_dump(stmt->domain);
650 fprintf(stderr, "%*s", indent, "");
651 isl_map_dump(stmt->schedule);
652 expr_dump(stmt->body, indent);
653 for (i = 0; i < stmt->n_arg; ++i)
654 expr_dump(stmt->args[i], indent + 2);
657 void pet_stmt_dump(struct pet_stmt *stmt)
659 stmt_dump(stmt, 0);
662 struct pet_array *pet_array_free(struct pet_array *array)
664 if (!array)
665 return NULL;
667 isl_set_free(array->context);
668 isl_set_free(array->extent);
669 isl_set_free(array->value_bounds);
670 free(array->element_type);
672 free(array);
673 return NULL;
676 void pet_array_dump(struct pet_array *array)
678 if (!array)
679 return;
681 isl_set_dump(array->context);
682 isl_set_dump(array->extent);
683 isl_set_dump(array->value_bounds);
684 fprintf(stderr, "%s %s\n", array->element_type,
685 array->live_out ? "live-out" : "");
688 /* Alloc a pet_scop structure, with extra room for information that
689 * is only used during parsing.
691 struct pet_scop *pet_scop_alloc(isl_ctx *ctx)
693 return &isl_calloc_type(ctx, struct pet_scop_ext)->scop;
696 /* Construct a pet_scop with room for n statements.
698 static struct pet_scop *scop_alloc(isl_ctx *ctx, int n)
700 isl_space *space;
701 struct pet_scop *scop;
703 scop = pet_scop_alloc(ctx);
704 if (!scop)
705 return NULL;
707 space = isl_space_params_alloc(ctx, 0);
708 scop->context = isl_set_universe(isl_space_copy(space));
709 scop->context_value = isl_set_universe(space);
710 scop->stmts = isl_calloc_array(ctx, struct pet_stmt *, n);
711 if (!scop->context || !scop->stmts)
712 return pet_scop_free(scop);
714 scop->n_stmt = n;
716 return scop;
719 struct pet_scop *pet_scop_empty(isl_ctx *ctx)
721 return scop_alloc(ctx, 0);
724 /* Update "context" with respect to the valid parameter values for "access".
726 static __isl_give isl_set *access_extract_context(__isl_keep isl_map *access,
727 __isl_take isl_set *context)
729 context = isl_set_intersect(context,
730 isl_map_params(isl_map_copy(access)));
731 return context;
734 /* Update "context" with respect to the valid parameter values for "expr".
736 * If "expr" represents a ternary operator, then a parameter value
737 * needs to be valid for the condition and for at least one of the
738 * remaining two arguments.
739 * If the condition is an affine expression, then we can be a bit more specific.
740 * The parameter then has to be valid for the second argument for
741 * non-zero accesses and valid for the third argument for zero accesses.
743 static __isl_give isl_set *expr_extract_context(struct pet_expr *expr,
744 __isl_take isl_set *context)
746 int i;
748 if (expr->type == pet_expr_ternary) {
749 int is_aff;
750 isl_set *context1, *context2;
752 is_aff = pet_expr_is_affine(expr->args[0]);
753 if (is_aff < 0)
754 goto error;
756 context = expr_extract_context(expr->args[0], context);
757 context1 = expr_extract_context(expr->args[1],
758 isl_set_copy(context));
759 context2 = expr_extract_context(expr->args[2], context);
761 if (is_aff) {
762 isl_map *access;
763 isl_set *zero_set;
765 access = isl_map_copy(expr->args[0]->acc.access);
766 access = isl_map_fix_si(access, isl_dim_out, 0, 0);
767 zero_set = isl_map_params(access);
768 context1 = isl_set_subtract(context1,
769 isl_set_copy(zero_set));
770 context2 = isl_set_intersect(context2, zero_set);
773 context = isl_set_union(context1, context2);
774 context = isl_set_coalesce(context);
776 return context;
779 for (i = 0; i < expr->n_arg; ++i)
780 context = expr_extract_context(expr->args[i], context);
782 if (expr->type == pet_expr_access)
783 context = access_extract_context(expr->acc.access, context);
785 return context;
786 error:
787 isl_set_free(context);
788 return NULL;
791 /* Update "context" with respect to the valid parameter values for "stmt".
793 static __isl_give isl_set *stmt_extract_context(struct pet_stmt *stmt,
794 __isl_take isl_set *context)
796 int i;
798 for (i = 0; i < stmt->n_arg; ++i)
799 context = expr_extract_context(stmt->args[i], context);
801 context = expr_extract_context(stmt->body, context);
803 return context;
806 /* Construct a pet_scop that contains the given pet_stmt.
808 struct pet_scop *pet_scop_from_pet_stmt(isl_ctx *ctx, struct pet_stmt *stmt)
810 struct pet_scop *scop;
812 if (!stmt)
813 return NULL;
815 scop = scop_alloc(ctx, 1);
817 scop->context = stmt_extract_context(stmt, scop->context);
818 if (!scop->context)
819 goto error;
821 scop->stmts[0] = stmt;
823 return scop;
824 error:
825 pet_stmt_free(stmt);
826 pet_scop_free(scop);
827 return NULL;
830 /* Does "set" represent an element of an unnamed space, i.e.,
831 * does it represent an affine expression?
833 static int set_is_affine(__isl_keep isl_set *set)
835 int has_id;
837 has_id = isl_set_has_tuple_id(set);
838 if (has_id < 0)
839 return -1;
841 return !has_id;
844 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
845 * ext may be equal to either ext1 or ext2.
847 * The two skips that need to be combined are assumed to be affine expressions.
849 * We need to skip in ext if we need to skip in either ext1 or ext2.
850 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
852 static struct pet_scop_ext *combine_skips(struct pet_scop_ext *ext,
853 struct pet_scop_ext *ext1, struct pet_scop_ext *ext2,
854 enum pet_skip type)
856 isl_set *set, *skip1, *skip2;
858 if (!ext)
859 return NULL;
860 if (!ext1->skip[type] && !ext2->skip[type])
861 return ext;
862 if (!ext1->skip[type]) {
863 if (ext == ext2)
864 return ext;
865 ext->skip[type] = ext2->skip[type];
866 ext2->skip[type] = NULL;
867 return ext;
869 if (!ext2->skip[type]) {
870 if (ext == ext1)
871 return ext;
872 ext->skip[type] = ext1->skip[type];
873 ext1->skip[type] = NULL;
874 return ext;
877 if (!set_is_affine(ext1->skip[type]) ||
878 !set_is_affine(ext2->skip[type]))
879 isl_die(isl_set_get_ctx(ext1->skip[type]), isl_error_internal,
880 "can only combine affine skips",
881 return pet_scop_free(&ext->scop));
883 skip1 = isl_set_copy(ext1->skip[type]);
884 skip2 = isl_set_copy(ext2->skip[type]);
885 set = isl_set_intersect(
886 isl_set_fix_si(isl_set_copy(skip1), isl_dim_set, 0, 0),
887 isl_set_fix_si(isl_set_copy(skip2), isl_dim_set, 0, 0));
888 set = isl_set_union(set, isl_set_fix_si(skip1, isl_dim_set, 0, 1));
889 set = isl_set_union(set, isl_set_fix_si(skip2, isl_dim_set, 0, 1));
890 set = isl_set_coalesce(set);
891 isl_set_free(ext1->skip[type]);
892 ext1->skip[type] = NULL;
893 isl_set_free(ext2->skip[type]);
894 ext2->skip[type] = NULL;
895 ext->skip[type] = set;
896 if (!ext->skip[type])
897 return pet_scop_free(&ext->scop);
899 return ext;
902 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
903 * where type takes on the values pet_skip_now and pet_skip_later.
904 * scop may be equal to either scop1 or scop2.
906 static struct pet_scop *scop_combine_skips(struct pet_scop *scop,
907 struct pet_scop *scop1, struct pet_scop *scop2)
909 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
910 struct pet_scop_ext *ext1 = (struct pet_scop_ext *) scop1;
911 struct pet_scop_ext *ext2 = (struct pet_scop_ext *) scop2;
913 ext = combine_skips(ext, ext1, ext2, pet_skip_now);
914 ext = combine_skips(ext, ext1, ext2, pet_skip_later);
915 return &ext->scop;
918 /* Construct a pet_scop that contains the arrays, statements and
919 * skip information in "scop1" and "scop2".
921 static struct pet_scop *pet_scop_add(isl_ctx *ctx, struct pet_scop *scop1,
922 struct pet_scop *scop2)
924 int i;
925 struct pet_scop *scop;
927 if (!scop1 || !scop2)
928 goto error;
930 if (scop1->n_stmt == 0) {
931 scop2 = scop_combine_skips(scop2, scop1, scop2);
932 pet_scop_free(scop1);
933 return scop2;
936 if (scop2->n_stmt == 0) {
937 scop1 = scop_combine_skips(scop1, scop1, scop2);
938 pet_scop_free(scop2);
939 return scop1;
942 scop = scop_alloc(ctx, scop1->n_stmt + scop2->n_stmt);
943 if (!scop)
944 goto error;
946 scop->arrays = isl_calloc_array(ctx, struct pet_array *,
947 scop1->n_array + scop2->n_array);
948 if (!scop->arrays)
949 goto error;
950 scop->n_array = scop1->n_array + scop2->n_array;
952 for (i = 0; i < scop1->n_stmt; ++i) {
953 scop->stmts[i] = scop1->stmts[i];
954 scop1->stmts[i] = NULL;
957 for (i = 0; i < scop2->n_stmt; ++i) {
958 scop->stmts[scop1->n_stmt + i] = scop2->stmts[i];
959 scop2->stmts[i] = NULL;
962 for (i = 0; i < scop1->n_array; ++i) {
963 scop->arrays[i] = scop1->arrays[i];
964 scop1->arrays[i] = NULL;
967 for (i = 0; i < scop2->n_array; ++i) {
968 scop->arrays[scop1->n_array + i] = scop2->arrays[i];
969 scop2->arrays[i] = NULL;
972 scop = pet_scop_restrict_context(scop, isl_set_copy(scop1->context));
973 scop = pet_scop_restrict_context(scop, isl_set_copy(scop2->context));
974 scop = scop_combine_skips(scop, scop1, scop2);
976 pet_scop_free(scop1);
977 pet_scop_free(scop2);
978 return scop;
979 error:
980 pet_scop_free(scop1);
981 pet_scop_free(scop2);
982 return NULL;
985 /* Apply the skip condition "skip" to "scop".
986 * That is, make sure "scop" is not executed when the condition holds.
988 * If "skip" is an affine expression, we add the conditions under
989 * which the expression is zero to the iteration domains.
990 * Otherwise, we add a filter on the variable attaining the value zero.
992 static struct pet_scop *restrict_skip(struct pet_scop *scop,
993 __isl_take isl_set *skip)
995 isl_map *skip_map;
996 int is_aff;
998 if (!scop || !skip)
999 goto error;
1001 is_aff = set_is_affine(skip);
1002 if (is_aff < 0)
1003 goto error;
1005 if (!is_aff)
1006 return pet_scop_filter(scop, isl_map_from_range(skip), 0);
1008 skip = isl_set_fix_si(skip, isl_dim_set, 0, 0);
1009 scop = pet_scop_restrict(scop, isl_set_params(skip));
1011 return scop;
1012 error:
1013 isl_set_free(skip);
1014 return pet_scop_free(scop);
1017 /* Construct a pet_scop that contains the arrays, statements and
1018 * skip information in "scop1" and "scop2", where the two scops
1019 * are executed "in sequence". That is, breaks and continues
1020 * in scop1 have an effect on scop2.
1022 struct pet_scop *pet_scop_add_seq(isl_ctx *ctx, struct pet_scop *scop1,
1023 struct pet_scop *scop2)
1025 if (scop1 && pet_scop_has_skip(scop1, pet_skip_now))
1026 scop2 = restrict_skip(scop2,
1027 pet_scop_get_skip(scop1, pet_skip_now));
1028 return pet_scop_add(ctx, scop1, scop2);
1031 /* Construct a pet_scop that contains the arrays, statements and
1032 * skip information in "scop1" and "scop2", where the two scops
1033 * are executed "in parallel". That is, any break or continue
1034 * in scop1 has no effect on scop2.
1036 struct pet_scop *pet_scop_add_par(isl_ctx *ctx, struct pet_scop *scop1,
1037 struct pet_scop *scop2)
1039 return pet_scop_add(ctx, scop1, scop2);
1042 void *pet_scop_free(struct pet_scop *scop)
1044 int i;
1045 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1047 if (!scop)
1048 return NULL;
1049 isl_set_free(scop->context);
1050 isl_set_free(scop->context_value);
1051 if (scop->arrays)
1052 for (i = 0; i < scop->n_array; ++i)
1053 pet_array_free(scop->arrays[i]);
1054 free(scop->arrays);
1055 if (scop->stmts)
1056 for (i = 0; i < scop->n_stmt; ++i)
1057 pet_stmt_free(scop->stmts[i]);
1058 free(scop->stmts);
1059 isl_set_free(ext->skip[pet_skip_now]);
1060 isl_set_free(ext->skip[pet_skip_later]);
1061 free(scop);
1062 return NULL;
1065 void pet_scop_dump(struct pet_scop *scop)
1067 int i;
1068 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1070 if (!scop)
1071 return;
1073 isl_set_dump(scop->context);
1074 isl_set_dump(scop->context_value);
1075 for (i = 0; i < scop->n_array; ++i)
1076 pet_array_dump(scop->arrays[i]);
1077 for (i = 0; i < scop->n_stmt; ++i)
1078 pet_stmt_dump(scop->stmts[i]);
1080 if (ext->skip[0]) {
1081 fprintf(stderr, "skip\n");
1082 isl_set_dump(ext->skip[0]);
1083 isl_set_dump(ext->skip[1]);
1087 /* Return 1 if the two pet_arrays are equivalent.
1089 * We don't compare element_size as this may be target dependent.
1091 int pet_array_is_equal(struct pet_array *array1, struct pet_array *array2)
1093 if (!array1 || !array2)
1094 return 0;
1096 if (!isl_set_is_equal(array1->context, array2->context))
1097 return 0;
1098 if (!isl_set_is_equal(array1->extent, array2->extent))
1099 return 0;
1100 if (!!array1->value_bounds != !!array2->value_bounds)
1101 return 0;
1102 if (array1->value_bounds &&
1103 !isl_set_is_equal(array1->value_bounds, array2->value_bounds))
1104 return 0;
1105 if (strcmp(array1->element_type, array2->element_type))
1106 return 0;
1107 if (array1->live_out != array2->live_out)
1108 return 0;
1109 if (array1->uniquely_defined != array2->uniquely_defined)
1110 return 0;
1111 if (array1->declared != array2->declared)
1112 return 0;
1113 if (array1->exposed != array2->exposed)
1114 return 0;
1116 return 1;
1119 /* Return 1 if the two pet_stmts are equivalent.
1121 int pet_stmt_is_equal(struct pet_stmt *stmt1, struct pet_stmt *stmt2)
1123 int i;
1125 if (!stmt1 || !stmt2)
1126 return 0;
1128 if (stmt1->line != stmt2->line)
1129 return 0;
1130 if (!isl_set_is_equal(stmt1->domain, stmt2->domain))
1131 return 0;
1132 if (!isl_map_is_equal(stmt1->schedule, stmt2->schedule))
1133 return 0;
1134 if (!pet_expr_is_equal(stmt1->body, stmt2->body))
1135 return 0;
1136 if (stmt1->n_arg != stmt2->n_arg)
1137 return 0;
1138 for (i = 0; i < stmt1->n_arg; ++i) {
1139 if (!pet_expr_is_equal(stmt1->args[i], stmt2->args[i]))
1140 return 0;
1143 return 1;
1146 /* Return 1 if the two pet_scops are equivalent.
1148 int pet_scop_is_equal(struct pet_scop *scop1, struct pet_scop *scop2)
1150 int i;
1152 if (!scop1 || !scop2)
1153 return 0;
1155 if (!isl_set_is_equal(scop1->context, scop2->context))
1156 return 0;
1157 if (!isl_set_is_equal(scop1->context_value, scop2->context_value))
1158 return 0;
1160 if (scop1->n_array != scop2->n_array)
1161 return 0;
1162 for (i = 0; i < scop1->n_array; ++i)
1163 if (!pet_array_is_equal(scop1->arrays[i], scop2->arrays[i]))
1164 return 0;
1166 if (scop1->n_stmt != scop2->n_stmt)
1167 return 0;
1168 for (i = 0; i < scop1->n_stmt; ++i)
1169 if (!pet_stmt_is_equal(scop1->stmts[i], scop2->stmts[i]))
1170 return 0;
1172 return 1;
1175 /* Prefix the schedule of "stmt" with an extra dimension with constant
1176 * value "pos".
1178 struct pet_stmt *pet_stmt_prefix(struct pet_stmt *stmt, int pos)
1180 if (!stmt)
1181 return NULL;
1183 stmt->schedule = isl_map_insert_dims(stmt->schedule, isl_dim_out, 0, 1);
1184 stmt->schedule = isl_map_fix_si(stmt->schedule, isl_dim_out, 0, pos);
1185 if (!stmt->schedule)
1186 return pet_stmt_free(stmt);
1188 return stmt;
1191 /* Prefix the schedules of all statements in "scop" with an extra
1192 * dimension with constant value "pos".
1194 struct pet_scop *pet_scop_prefix(struct pet_scop *scop, int pos)
1196 int i;
1198 if (!scop)
1199 return NULL;
1201 for (i = 0; i < scop->n_stmt; ++i) {
1202 scop->stmts[i] = pet_stmt_prefix(scop->stmts[i], pos);
1203 if (!scop->stmts[i])
1204 return pet_scop_free(scop);
1207 return scop;
1210 /* Given a set with a parameter at "param_pos" that refers to the
1211 * iterator, "move" the iterator to the first set dimension.
1212 * That is, essentially equate the parameter to the first set dimension
1213 * and then project it out.
1215 * The first set dimension may however refer to a virtual iterator,
1216 * while the parameter refers to the "real" iterator.
1217 * We therefore need to take into account the mapping "iv_map", which
1218 * maps the virtual iterator to the real iterator.
1219 * In particular, we equate the set dimension to the input of the map
1220 * and the parameter to the output of the map and then project out
1221 * everything we don't need anymore.
1223 static __isl_give isl_set *internalize_iv(__isl_take isl_set *set,
1224 int param_pos, __isl_take isl_map *iv_map)
1226 isl_map *map;
1227 map = isl_map_from_domain(set);
1228 map = isl_map_add_dims(map, isl_dim_out, 1);
1229 map = isl_map_equate(map, isl_dim_in, 0, isl_dim_out, 0);
1230 iv_map = isl_map_align_params(iv_map, isl_map_get_space(map));
1231 map = isl_map_apply_range(map, iv_map);
1232 map = isl_map_equate(map, isl_dim_param, param_pos, isl_dim_out, 0);
1233 map = isl_map_project_out(map, isl_dim_param, param_pos, 1);
1234 return isl_map_domain(map);
1237 /* Data used in embed_access.
1238 * extend adds an iterator to the iteration domain
1239 * iv_map maps the virtual iterator to the real iterator
1240 * var_id represents the induction variable of the corresponding loop
1242 struct pet_embed_access {
1243 isl_map *extend;
1244 isl_map *iv_map;
1245 isl_id *var_id;
1248 /* Embed the access relation in an extra outer loop.
1250 * We first update the iteration domain to insert the extra dimension.
1252 * If the access refers to the induction variable, then it is
1253 * turned into an access to the set of integers with index (and value)
1254 * equal to the induction variable.
1256 * If the induction variable appears in the constraints (as a parameter),
1257 * then the parameter is equated to the newly introduced iteration
1258 * domain dimension and subsequently projected out.
1260 * Similarly, if the accessed array is a virtual array (with user
1261 * pointer equal to NULL), as created by create_test_access,
1262 * then it is extended along with the domain of the access.
1264 static __isl_give isl_map *embed_access(__isl_take isl_map *access,
1265 void *user)
1267 struct pet_embed_access *data = user;
1268 isl_id *array_id = NULL;
1269 int pos;
1271 access = update_domain(access, data->extend);
1273 if (isl_map_has_tuple_id(access, isl_dim_out))
1274 array_id = isl_map_get_tuple_id(access, isl_dim_out);
1275 if (array_id == data->var_id ||
1276 (array_id && !isl_id_get_user(array_id))) {
1277 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
1278 access = isl_map_equate(access,
1279 isl_dim_in, 0, isl_dim_out, 0);
1280 if (array_id == data->var_id)
1281 access = isl_map_apply_range(access,
1282 isl_map_copy(data->iv_map));
1283 else
1284 access = isl_map_set_tuple_id(access, isl_dim_out,
1285 isl_id_copy(array_id));
1287 isl_id_free(array_id);
1289 pos = isl_map_find_dim_by_id(access, isl_dim_param, data->var_id);
1290 if (pos >= 0) {
1291 isl_set *set = isl_map_wrap(access);
1292 set = internalize_iv(set, pos, isl_map_copy(data->iv_map));
1293 access = isl_set_unwrap(set);
1295 access = isl_map_set_dim_id(access, isl_dim_in, 0,
1296 isl_id_copy(data->var_id));
1298 return access;
1301 /* Embed all access relations in "expr" in an extra loop.
1302 * "extend" inserts an outer loop iterator in the iteration domains.
1303 * "iv_map" maps the virtual iterator to the real iterator
1304 * "var_id" represents the induction variable.
1306 static struct pet_expr *expr_embed(struct pet_expr *expr,
1307 __isl_take isl_map *extend, __isl_take isl_map *iv_map,
1308 __isl_keep isl_id *var_id)
1310 struct pet_embed_access data =
1311 { .extend = extend, .iv_map = iv_map, .var_id = var_id };
1313 expr = pet_expr_foreach_access(expr, &embed_access, &data);
1314 isl_map_free(iv_map);
1315 isl_map_free(extend);
1316 return expr;
1319 /* Embed the given pet_stmt in an extra outer loop with iteration domain
1320 * "dom" and schedule "sched". "var_id" represents the induction variable
1321 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
1322 * That is, it maps the iterator used in "dom" and the domain of "sched"
1323 * to the iterator that some of the parameters in "stmt" may refer to.
1325 * The iteration domain and schedule of the statement are updated
1326 * according to the iteration domain and schedule of the new loop.
1327 * If stmt->domain is a wrapped map, then the iteration domain
1328 * is the domain of this map, so we need to be careful to adjust
1329 * this domain.
1331 * If the induction variable appears in the constraints (as a parameter)
1332 * of the current iteration domain or the schedule of the statement,
1333 * then the parameter is equated to the newly introduced iteration
1334 * domain dimension and subsequently projected out.
1336 * Finally, all access relations are updated based on the extra loop.
1338 static struct pet_stmt *pet_stmt_embed(struct pet_stmt *stmt,
1339 __isl_take isl_set *dom, __isl_take isl_map *sched,
1340 __isl_take isl_map *iv_map, __isl_take isl_id *var_id)
1342 int i;
1343 int pos;
1344 isl_id *stmt_id;
1345 isl_space *dim;
1346 isl_map *extend;
1348 if (!stmt)
1349 goto error;
1351 if (isl_set_is_wrapping(stmt->domain)) {
1352 isl_map *map;
1353 isl_map *ext;
1354 isl_space *ran_dim;
1356 map = isl_set_unwrap(stmt->domain);
1357 stmt_id = isl_map_get_tuple_id(map, isl_dim_in);
1358 ran_dim = isl_space_range(isl_map_get_space(map));
1359 ext = isl_map_from_domain_and_range(isl_set_copy(dom),
1360 isl_set_universe(ran_dim));
1361 map = isl_map_flat_domain_product(ext, map);
1362 map = isl_map_set_tuple_id(map, isl_dim_in,
1363 isl_id_copy(stmt_id));
1364 dim = isl_space_domain(isl_map_get_space(map));
1365 stmt->domain = isl_map_wrap(map);
1366 } else {
1367 stmt_id = isl_set_get_tuple_id(stmt->domain);
1368 stmt->domain = isl_set_flat_product(isl_set_copy(dom),
1369 stmt->domain);
1370 stmt->domain = isl_set_set_tuple_id(stmt->domain,
1371 isl_id_copy(stmt_id));
1372 dim = isl_set_get_space(stmt->domain);
1375 pos = isl_set_find_dim_by_id(stmt->domain, isl_dim_param, var_id);
1376 if (pos >= 0)
1377 stmt->domain = internalize_iv(stmt->domain, pos,
1378 isl_map_copy(iv_map));
1380 stmt->schedule = isl_map_flat_product(sched, stmt->schedule);
1381 stmt->schedule = isl_map_set_tuple_id(stmt->schedule,
1382 isl_dim_in, stmt_id);
1384 pos = isl_map_find_dim_by_id(stmt->schedule, isl_dim_param, var_id);
1385 if (pos >= 0) {
1386 isl_set *set = isl_map_wrap(stmt->schedule);
1387 set = internalize_iv(set, pos, isl_map_copy(iv_map));
1388 stmt->schedule = isl_set_unwrap(set);
1391 dim = isl_space_map_from_set(dim);
1392 extend = isl_map_identity(dim);
1393 extend = isl_map_remove_dims(extend, isl_dim_in, 0, 1);
1394 extend = isl_map_set_tuple_id(extend, isl_dim_in,
1395 isl_map_get_tuple_id(extend, isl_dim_out));
1396 for (i = 0; i < stmt->n_arg; ++i)
1397 stmt->args[i] = expr_embed(stmt->args[i], isl_map_copy(extend),
1398 isl_map_copy(iv_map), var_id);
1399 stmt->body = expr_embed(stmt->body, extend, iv_map, var_id);
1401 isl_set_free(dom);
1402 isl_id_free(var_id);
1404 for (i = 0; i < stmt->n_arg; ++i)
1405 if (!stmt->args[i])
1406 return pet_stmt_free(stmt);
1407 if (!stmt->domain || !stmt->schedule || !stmt->body)
1408 return pet_stmt_free(stmt);
1409 return stmt;
1410 error:
1411 isl_set_free(dom);
1412 isl_map_free(sched);
1413 isl_map_free(iv_map);
1414 isl_id_free(var_id);
1415 return NULL;
1418 /* Embed the given pet_array in an extra outer loop with iteration domain
1419 * "dom".
1420 * This embedding only has an effect on virtual arrays (those with
1421 * user pointer equal to NULL), which need to be extended along with
1422 * the iteration domain.
1424 static struct pet_array *pet_array_embed(struct pet_array *array,
1425 __isl_take isl_set *dom)
1427 isl_id *array_id = NULL;
1429 if (!array)
1430 goto error;
1432 if (isl_set_has_tuple_id(array->extent))
1433 array_id = isl_set_get_tuple_id(array->extent);
1435 if (array_id && !isl_id_get_user(array_id)) {
1436 array->extent = isl_set_flat_product(dom, array->extent);
1437 array->extent = isl_set_set_tuple_id(array->extent, array_id);
1438 } else {
1439 isl_set_free(dom);
1440 isl_id_free(array_id);
1443 return array;
1444 error:
1445 isl_set_free(dom);
1446 return NULL;
1449 /* Project out all unnamed parameters from "set" and return the result.
1451 static __isl_give isl_set *set_project_out_unnamed_params(
1452 __isl_take isl_set *set)
1454 int i, n;
1456 n = isl_set_dim(set, isl_dim_param);
1457 for (i = n - 1; i >= 0; --i) {
1458 if (isl_set_has_dim_name(set, isl_dim_param, i))
1459 continue;
1460 set = isl_set_project_out(set, isl_dim_param, i, 1);
1463 return set;
1466 /* Update the context with respect to an embedding into a loop
1467 * with iteration domain "dom" and induction variable "id".
1468 * "iv_map" maps a possibly virtual iterator (used in "dom")
1469 * to the real iterator (parameter "id").
1471 * If the current context is independent of "id", we don't need
1472 * to do anything.
1473 * Otherwise, a parameter value is invalid for the embedding if
1474 * any of the corresponding iterator values is invalid.
1475 * That is, a parameter value is valid only if all the corresponding
1476 * iterator values are valid.
1477 * We therefore compute the set of parameters
1479 * forall i in dom : valid (i)
1481 * or
1483 * not exists i in dom : not valid(i)
1485 * i.e.,
1487 * not exists i in dom \ valid(i)
1489 * Before we subtract valid(i) from dom, we first need to map
1490 * the real iterator to the virtual iterator.
1492 * If there are any unnamed parameters in "dom", then we consider
1493 * a parameter value to be valid if it is valid for any value of those
1494 * unnamed parameters. They are therefore projected out at the end.
1496 static __isl_give isl_set *context_embed(__isl_take isl_set *context,
1497 __isl_keep isl_set *dom, __isl_keep isl_map *iv_map,
1498 __isl_keep isl_id *id)
1500 int pos;
1502 pos = isl_set_find_dim_by_id(context, isl_dim_param, id);
1503 if (pos < 0)
1504 return context;
1506 context = isl_set_from_params(context);
1507 context = isl_set_add_dims(context, isl_dim_set, 1);
1508 context = isl_set_equate(context, isl_dim_param, pos, isl_dim_set, 0);
1509 context = isl_set_project_out(context, isl_dim_param, pos, 1);
1510 context = isl_set_apply(context, isl_map_reverse(isl_map_copy(iv_map)));
1511 context = isl_set_subtract(isl_set_copy(dom), context);
1512 context = isl_set_params(context);
1513 context = isl_set_complement(context);
1514 context = set_project_out_unnamed_params(context);
1515 return context;
1518 /* Embed all statements and arrays in "scop" in an extra outer loop
1519 * with iteration domain "dom" and schedule "sched".
1520 * "id" represents the induction variable of the loop.
1521 * "iv_map" maps a possibly virtual iterator to the real iterator.
1522 * That is, it maps the iterator used in "dom" and the domain of "sched"
1523 * to the iterator that some of the parameters in "scop" may refer to.
1525 * Any skip conditions within the loop have no effect outside of the loop.
1526 * The caller is responsible for making sure skip[pet_skip_later] has been
1527 * taken into account.
1529 struct pet_scop *pet_scop_embed(struct pet_scop *scop, __isl_take isl_set *dom,
1530 __isl_take isl_map *sched, __isl_take isl_map *iv_map,
1531 __isl_take isl_id *id)
1533 int i;
1535 if (!scop)
1536 goto error;
1538 pet_scop_reset_skip(scop, pet_skip_now);
1539 pet_scop_reset_skip(scop, pet_skip_later);
1541 scop->context = context_embed(scop->context, dom, iv_map, id);
1542 if (!scop->context)
1543 goto error;
1545 for (i = 0; i < scop->n_stmt; ++i) {
1546 scop->stmts[i] = pet_stmt_embed(scop->stmts[i],
1547 isl_set_copy(dom), isl_map_copy(sched),
1548 isl_map_copy(iv_map), isl_id_copy(id));
1549 if (!scop->stmts[i])
1550 goto error;
1553 for (i = 0; i < scop->n_array; ++i) {
1554 scop->arrays[i] = pet_array_embed(scop->arrays[i],
1555 isl_set_copy(dom));
1556 if (!scop->arrays[i])
1557 goto error;
1560 isl_set_free(dom);
1561 isl_map_free(sched);
1562 isl_map_free(iv_map);
1563 isl_id_free(id);
1564 return scop;
1565 error:
1566 isl_set_free(dom);
1567 isl_map_free(sched);
1568 isl_map_free(iv_map);
1569 isl_id_free(id);
1570 return pet_scop_free(scop);
1573 /* Add extra conditions on the parameters to iteration domain of "stmt".
1575 static struct pet_stmt *stmt_restrict(struct pet_stmt *stmt,
1576 __isl_take isl_set *cond)
1578 if (!stmt)
1579 goto error;
1581 stmt->domain = isl_set_intersect_params(stmt->domain, cond);
1583 return stmt;
1584 error:
1585 isl_set_free(cond);
1586 return pet_stmt_free(stmt);
1589 /* Add extra conditions to scop->skip[type].
1591 * The new skip condition only holds if it held before
1592 * and the condition is true. It does not hold if it did not hold
1593 * before or the condition is false.
1595 * The skip condition is assumed to be an affine expression.
1597 static struct pet_scop *pet_scop_restrict_skip(struct pet_scop *scop,
1598 enum pet_skip type, __isl_keep isl_set *cond)
1600 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1601 isl_set *skip;
1602 isl_set *set;
1604 if (!scop)
1605 return NULL;
1606 if (!ext->skip[type])
1607 return scop;
1609 if (!set_is_affine(ext->skip[type]))
1610 isl_die(isl_set_get_ctx(ext->skip[type]), isl_error_internal,
1611 "can only resrict affine skips",
1612 return pet_scop_free(scop));
1614 skip = ext->skip[type];
1615 skip = isl_set_intersect_params(skip, isl_set_copy(cond));
1616 set = isl_set_from_params(isl_set_copy(cond));
1617 set = isl_set_complement(set);
1618 set = isl_set_add_dims(set, isl_dim_set, 1);
1619 set = isl_set_fix_si(set, isl_dim_set, 0, 0);
1620 skip = isl_set_union(skip, set);
1621 ext->skip[type] = skip;
1622 if (!ext->skip[type])
1623 return pet_scop_free(scop);
1625 return scop;
1628 /* Add extra conditions on the parameters to all iteration domains
1629 * and skip conditions.
1631 * A parameter value is valid for the result if it was valid
1632 * for the original scop and satisfies "cond" or if it does
1633 * not satisfy "cond" as in this case the scop is not executed
1634 * and the original constraints on the parameters are irrelevant.
1636 struct pet_scop *pet_scop_restrict(struct pet_scop *scop,
1637 __isl_take isl_set *cond)
1639 int i;
1641 scop = pet_scop_restrict_skip(scop, pet_skip_now, cond);
1642 scop = pet_scop_restrict_skip(scop, pet_skip_later, cond);
1644 if (!scop)
1645 goto error;
1647 scop->context = isl_set_intersect(scop->context, isl_set_copy(cond));
1648 scop->context = isl_set_union(scop->context,
1649 isl_set_complement(isl_set_copy(cond)));
1650 scop->context = isl_set_coalesce(scop->context);
1651 scop->context = set_project_out_unnamed_params(scop->context);
1652 if (!scop->context)
1653 goto error;
1655 for (i = 0; i < scop->n_stmt; ++i) {
1656 scop->stmts[i] = stmt_restrict(scop->stmts[i],
1657 isl_set_copy(cond));
1658 if (!scop->stmts[i])
1659 goto error;
1662 isl_set_free(cond);
1663 return scop;
1664 error:
1665 isl_set_free(cond);
1666 return pet_scop_free(scop);
1669 /* Construct a map that inserts a filter value with name "id" and value
1670 * "satisfied" in the list of filter values embedded in the set space "space".
1672 * If "space" does not contain any filter values yet, we first create
1673 * a map that inserts 0 filter values, i.e.,
1675 * space -> [space -> []]
1677 * We can now assume that space is of the form [dom -> [filters]]
1678 * We construct an identity mapping on dom and a mapping on filters
1679 * that inserts the new filter
1681 * dom -> dom
1682 * [filters] -> [satisfied, filters]
1684 * and then compute the cross product
1686 * [dom -> [filters]] -> [dom -> [satisfied, filters]]
1688 static __isl_give isl_map *insert_filter_map(__isl_take isl_space *space,
1689 __isl_take isl_id *id, int satisfied)
1691 isl_space *space2;
1692 isl_map *map, *map_dom, *map_ran;
1693 isl_set *dom;
1695 if (isl_space_is_wrapping(space)) {
1696 space2 = isl_space_map_from_set(isl_space_copy(space));
1697 map = isl_map_identity(space2);
1698 space = isl_space_unwrap(space);
1699 } else {
1700 space = isl_space_from_domain(space);
1701 map = isl_map_universe(isl_space_copy(space));
1702 map = isl_map_reverse(isl_map_domain_map(map));
1705 space2 = isl_space_domain(isl_space_copy(space));
1706 map_dom = isl_map_identity(isl_space_map_from_set(space2));
1707 space = isl_space_range(space);
1708 map_ran = isl_map_identity(isl_space_map_from_set(space));
1709 map_ran = isl_map_insert_dims(map_ran, isl_dim_out, 0, 1);
1710 map_ran = isl_map_set_dim_id(map_ran, isl_dim_out, 0, id);
1711 map_ran = isl_map_fix_si(map_ran, isl_dim_out, 0, satisfied);
1713 map = isl_map_apply_range(map, isl_map_product(map_dom, map_ran));
1715 return map;
1718 /* Insert an argument expression corresponding to "test" in front
1719 * of the list of arguments described by *n_arg and *args.
1721 static int args_insert_access(unsigned *n_arg, struct pet_expr ***args,
1722 __isl_keep isl_map *test)
1724 int i;
1725 isl_ctx *ctx = isl_map_get_ctx(test);
1727 if (!test)
1728 return -1;
1730 if (!*args) {
1731 *args = isl_calloc_array(ctx, struct pet_expr *, 1);
1732 if (!*args)
1733 return -1;
1734 } else {
1735 struct pet_expr **ext;
1736 ext = isl_calloc_array(ctx, struct pet_expr *, 1 + *n_arg);
1737 if (!ext)
1738 return -1;
1739 for (i = 0; i < *n_arg; ++i)
1740 ext[1 + i] = (*args)[i];
1741 free(*args);
1742 *args = ext;
1744 (*n_arg)++;
1745 (*args)[0] = pet_expr_from_access(isl_map_copy(test));
1746 if (!(*args)[0])
1747 return -1;
1749 return 0;
1752 /* Make the expression "expr" depend on the value of "test"
1753 * being equal to "satisfied".
1755 * If "test" is an affine expression, we simply add the conditions
1756 * on the expression have the value "satisfied" to all access relations.
1758 * Otherwise, we add a filter to "expr" (which is then assumed to be
1759 * an access expression) corresponding to "test" being equal to "satisfied".
1761 struct pet_expr *pet_expr_filter(struct pet_expr *expr,
1762 __isl_take isl_map *test, int satisfied)
1764 isl_id *id;
1765 isl_ctx *ctx;
1766 isl_space *space;
1767 isl_map *map;
1769 if (!expr || !test)
1770 goto error;
1772 if (!isl_map_has_tuple_id(test, isl_dim_out)) {
1773 test = isl_map_fix_si(test, isl_dim_out, 0, satisfied);
1774 return pet_expr_restrict(expr, isl_map_params(test));
1777 ctx = isl_map_get_ctx(test);
1778 if (expr->type != pet_expr_access)
1779 isl_die(ctx, isl_error_invalid,
1780 "can only filter access expressions", goto error);
1782 space = isl_space_domain(isl_map_get_space(expr->acc.access));
1783 id = isl_map_get_tuple_id(test, isl_dim_out);
1784 map = insert_filter_map(space, id, satisfied);
1786 expr->acc.access = isl_map_apply_domain(expr->acc.access, map);
1787 if (!expr->acc.access)
1788 goto error;
1790 if (args_insert_access(&expr->n_arg, &expr->args, test) < 0)
1791 goto error;
1793 isl_map_free(test);
1794 return expr;
1795 error:
1796 isl_map_free(test);
1797 return pet_expr_free(expr);
1800 /* Make the statement "stmt" depend on the value of "test"
1801 * being equal to "satisfied" by adjusting stmt->domain.
1803 * The domain of "test" corresponds to the (zero or more) outer dimensions
1804 * of the iteration domain.
1806 * We insert an argument corresponding to a read to "test"
1807 * from the iteration domain of "stmt" in front of the list of arguments.
1808 * We also insert a corresponding output dimension in the wrapped
1809 * map contained in stmt->domain, with value set to "satisfied".
1811 static struct pet_stmt *stmt_filter(struct pet_stmt *stmt,
1812 __isl_take isl_map *test, int satisfied)
1814 int i;
1815 isl_id *id;
1816 isl_ctx *ctx;
1817 isl_map *map, *add_dom;
1818 isl_space *space;
1819 isl_set *dom;
1820 int n_test_dom;
1822 if (!stmt || !test)
1823 goto error;
1825 id = isl_map_get_tuple_id(test, isl_dim_out);
1826 map = insert_filter_map(isl_set_get_space(stmt->domain), id, satisfied);
1827 stmt->domain = isl_set_apply(stmt->domain, map);
1829 space = isl_space_unwrap(isl_set_get_space(stmt->domain));
1830 dom = isl_set_universe(isl_space_domain(space));
1831 n_test_dom = isl_map_dim(test, isl_dim_in);
1832 add_dom = isl_map_from_range(dom);
1833 add_dom = isl_map_add_dims(add_dom, isl_dim_in, n_test_dom);
1834 for (i = 0; i < n_test_dom; ++i)
1835 add_dom = isl_map_equate(add_dom, isl_dim_in, i,
1836 isl_dim_out, i);
1837 test = isl_map_apply_domain(test, add_dom);
1839 if (args_insert_access(&stmt->n_arg, &stmt->args, test) < 0)
1840 goto error;
1842 isl_map_free(test);
1843 return stmt;
1844 error:
1845 isl_map_free(test);
1846 return pet_stmt_free(stmt);
1849 /* Does "scop" have a skip condition of the given "type"?
1851 int pet_scop_has_skip(struct pet_scop *scop, enum pet_skip type)
1853 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1855 if (!scop)
1856 return -1;
1857 return ext->skip[type] != NULL;
1860 /* Does "scop" have a skip condition of the given "type" that
1861 * is an affine expression?
1863 int pet_scop_has_affine_skip(struct pet_scop *scop, enum pet_skip type)
1865 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1867 if (!scop)
1868 return -1;
1869 if (!ext->skip[type])
1870 return 0;
1871 return set_is_affine(ext->skip[type]);
1874 /* Does "scop" have a skip condition of the given "type" that
1875 * is not an affine expression?
1877 int pet_scop_has_var_skip(struct pet_scop *scop, enum pet_skip type)
1879 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1880 int aff;
1882 if (!scop)
1883 return -1;
1884 if (!ext->skip[type])
1885 return 0;
1886 aff = set_is_affine(ext->skip[type]);
1887 if (aff < 0)
1888 return -1;
1889 return !aff;
1892 /* Does "scop" have a skip condition of the given "type" that
1893 * is affine and holds on the entire domain?
1895 int pet_scop_has_universal_skip(struct pet_scop *scop, enum pet_skip type)
1897 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1898 isl_set *set;
1899 int is_aff;
1900 int is_univ;
1902 is_aff = pet_scop_has_affine_skip(scop, type);
1903 if (is_aff < 0 || !is_aff)
1904 return is_aff;
1906 set = isl_set_copy(ext->skip[type]);
1907 set = isl_set_fix_si(set, isl_dim_set, 0, 1);
1908 set = isl_set_params(set);
1909 is_univ = isl_set_plain_is_universe(set);
1910 isl_set_free(set);
1912 return is_univ;
1915 /* Replace scop->skip[type] by "skip".
1917 struct pet_scop *pet_scop_set_skip(struct pet_scop *scop,
1918 enum pet_skip type, __isl_take isl_set *skip)
1920 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1922 if (!scop || !skip)
1923 goto error;
1925 isl_set_free(ext->skip[type]);
1926 ext->skip[type] = skip;
1928 return scop;
1929 error:
1930 isl_set_free(skip);
1931 return pet_scop_free(scop);
1934 /* Return a copy of scop->skip[type].
1936 __isl_give isl_set *pet_scop_get_skip(struct pet_scop *scop,
1937 enum pet_skip type)
1939 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1941 if (!scop)
1942 return NULL;
1944 return isl_set_copy(ext->skip[type]);
1947 /* Return a map to the skip condition of the given type.
1949 __isl_give isl_map *pet_scop_get_skip_map(struct pet_scop *scop,
1950 enum pet_skip type)
1952 return isl_map_from_range(pet_scop_get_skip(scop, type));
1955 /* Return an access pet_expr corresponding to the skip condition
1956 * of the given type.
1958 struct pet_expr *pet_scop_get_skip_expr(struct pet_scop *scop,
1959 enum pet_skip type)
1961 return pet_expr_from_access(pet_scop_get_skip_map(scop, type));
1964 /* Drop the the skip condition scop->skip[type].
1966 void pet_scop_reset_skip(struct pet_scop *scop, enum pet_skip type)
1968 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1970 if (!scop)
1971 return;
1973 isl_set_free(ext->skip[type]);
1974 ext->skip[type] = NULL;
1977 /* Make the skip condition (if any) depend on the value of "test" being
1978 * equal to "satisfied".
1980 * We only support the case where the original skip condition is universal,
1981 * i.e., where skipping is unconditional, and where satisfied == 1.
1982 * In this case, the skip condition is changed to skip only when
1983 * "test" is equal to one.
1985 static struct pet_scop *pet_scop_filter_skip(struct pet_scop *scop,
1986 enum pet_skip type, __isl_keep isl_map *test, int satisfied)
1988 int is_univ = 0;
1990 if (!scop)
1991 return NULL;
1992 if (!pet_scop_has_skip(scop, type))
1993 return scop;
1995 if (satisfied)
1996 is_univ = pet_scop_has_universal_skip(scop, type);
1997 if (is_univ < 0)
1998 return pet_scop_free(scop);
1999 if (satisfied && is_univ) {
2000 scop = pet_scop_set_skip(scop, type,
2001 isl_map_range(isl_map_copy(test)));
2002 if (!scop)
2003 return NULL;
2004 } else {
2005 isl_die(isl_map_get_ctx(test), isl_error_internal,
2006 "skip expression cannot be filtered",
2007 return pet_scop_free(scop));
2010 return scop;
2013 /* Make all statements in "scop" depend on the value of "test"
2014 * being equal to "satisfied" by adjusting their domains.
2016 struct pet_scop *pet_scop_filter(struct pet_scop *scop,
2017 __isl_take isl_map *test, int satisfied)
2019 int i;
2021 scop = pet_scop_filter_skip(scop, pet_skip_now, test, satisfied);
2022 scop = pet_scop_filter_skip(scop, pet_skip_later, test, satisfied);
2024 if (!scop || !test)
2025 goto error;
2027 for (i = 0; i < scop->n_stmt; ++i) {
2028 scop->stmts[i] = stmt_filter(scop->stmts[i],
2029 isl_map_copy(test), satisfied);
2030 if (!scop->stmts[i])
2031 goto error;
2034 isl_map_free(test);
2035 return scop;
2036 error:
2037 isl_map_free(test);
2038 return pet_scop_free(scop);
2041 /* Do the filters "i" and "j" always have the same value?
2043 static int equal_filter_values(__isl_keep isl_set *domain, int i, int j)
2045 isl_map *map, *test;
2046 int equal;
2048 map = isl_set_unwrap(isl_set_copy(domain));
2049 test = isl_map_universe(isl_map_get_space(map));
2050 test = isl_map_equate(test, isl_dim_out, i, isl_dim_out, j);
2051 equal = isl_map_is_subset(map, test);
2052 isl_map_free(map);
2053 isl_map_free(test);
2055 return equal;
2058 /* Merge filters "i" and "j" into a single filter ("i") with as filter
2059 * access relation, the union of the two access relations.
2061 static struct pet_stmt *merge_filter_pair(struct pet_stmt *stmt, int i, int j)
2063 int k;
2064 isl_map *map;
2066 if (!stmt)
2067 return NULL;
2069 stmt->args[i]->acc.access = isl_map_union(stmt->args[i]->acc.access,
2070 isl_map_copy(stmt->args[j]->acc.access));
2071 stmt->args[i]->acc.access = isl_map_coalesce(stmt->args[i]->acc.access);
2073 pet_expr_free(stmt->args[j]);
2074 for (k = j; k < stmt->n_arg - 1; ++k)
2075 stmt->args[k] = stmt->args[k + 1];
2076 stmt->n_arg--;
2078 map = isl_set_unwrap(stmt->domain);
2079 map = isl_map_project_out(map, isl_dim_out, j, 1);
2080 stmt->domain = isl_map_wrap(map);
2082 if (!stmt->domain || !stmt->args[i]->acc.access)
2083 return pet_stmt_free(stmt);
2085 return stmt;
2088 /* Look for any pair of filters that access the same filter variable
2089 * and that have the same filter value and merge them into a single
2090 * filter with as filter access relation the union of the filter access
2091 * relations.
2093 static struct pet_stmt *stmt_merge_filters(struct pet_stmt *stmt)
2095 int i, j;
2096 isl_space *space_i, *space_j;
2098 if (!stmt)
2099 return NULL;
2100 if (stmt->n_arg <= 1)
2101 return stmt;
2103 for (i = 0; i < stmt->n_arg - 1; ++i) {
2104 if (stmt->args[i]->type != pet_expr_access)
2105 continue;
2106 if (pet_expr_is_affine(stmt->args[i]))
2107 continue;
2109 space_i = isl_map_get_space(stmt->args[i]->acc.access);
2111 for (j = stmt->n_arg - 1; j > i; --j) {
2112 int eq;
2114 if (stmt->args[j]->type != pet_expr_access)
2115 continue;
2116 if (pet_expr_is_affine(stmt->args[j]))
2117 continue;
2119 space_j = isl_map_get_space(stmt->args[j]->acc.access);
2121 eq = isl_space_is_equal(space_i, space_j);
2122 if (eq >= 0 && eq)
2123 eq = equal_filter_values(stmt->domain, i, j);
2124 if (eq >= 0 && eq)
2125 stmt = merge_filter_pair(stmt, i, j);
2127 isl_space_free(space_j);
2129 if (eq < 0 || !stmt)
2130 break;
2133 isl_space_free(space_i);
2135 if (j > i || !stmt)
2136 return pet_stmt_free(stmt);
2139 return stmt;
2142 /* Look for any pair of filters that access the same filter variable
2143 * and that have the same filter value and merge them into a single
2144 * filter with as filter access relation the union of the filter access
2145 * relations.
2147 struct pet_scop *pet_scop_merge_filters(struct pet_scop *scop)
2149 int i;
2151 if (!scop)
2152 return NULL;
2154 for (i = 0; i < scop->n_stmt; ++i) {
2155 scop->stmts[i] = stmt_merge_filters(scop->stmts[i]);
2156 if (!scop->stmts[i])
2157 return pet_scop_free(scop);
2160 return scop;
2163 /* Add all parameters in "expr" to "dim" and return the result.
2165 static __isl_give isl_space *expr_collect_params(struct pet_expr *expr,
2166 __isl_take isl_space *dim)
2168 int i;
2170 if (!expr)
2171 goto error;
2172 for (i = 0; i < expr->n_arg; ++i)
2174 dim = expr_collect_params(expr->args[i], dim);
2176 if (expr->type == pet_expr_access)
2177 dim = isl_space_align_params(dim,
2178 isl_map_get_space(expr->acc.access));
2180 return dim;
2181 error:
2182 isl_space_free(dim);
2183 return pet_expr_free(expr);
2186 /* Add all parameters in "stmt" to "dim" and return the result.
2188 static __isl_give isl_space *stmt_collect_params(struct pet_stmt *stmt,
2189 __isl_take isl_space *dim)
2191 if (!stmt)
2192 goto error;
2194 dim = isl_space_align_params(dim, isl_set_get_space(stmt->domain));
2195 dim = isl_space_align_params(dim, isl_map_get_space(stmt->schedule));
2196 dim = expr_collect_params(stmt->body, dim);
2198 return dim;
2199 error:
2200 isl_space_free(dim);
2201 return pet_stmt_free(stmt);
2204 /* Add all parameters in "array" to "dim" and return the result.
2206 static __isl_give isl_space *array_collect_params(struct pet_array *array,
2207 __isl_take isl_space *dim)
2209 if (!array)
2210 goto error;
2212 dim = isl_space_align_params(dim, isl_set_get_space(array->context));
2213 dim = isl_space_align_params(dim, isl_set_get_space(array->extent));
2215 return dim;
2216 error:
2217 pet_array_free(array);
2218 return isl_space_free(dim);
2221 /* Add all parameters in "scop" to "dim" and return the result.
2223 static __isl_give isl_space *scop_collect_params(struct pet_scop *scop,
2224 __isl_take isl_space *dim)
2226 int i;
2228 if (!scop)
2229 goto error;
2231 for (i = 0; i < scop->n_array; ++i)
2232 dim = array_collect_params(scop->arrays[i], dim);
2234 for (i = 0; i < scop->n_stmt; ++i)
2235 dim = stmt_collect_params(scop->stmts[i], dim);
2237 return dim;
2238 error:
2239 isl_space_free(dim);
2240 return pet_scop_free(scop);
2243 /* Add all parameters in "dim" to all access relations in "expr".
2245 static struct pet_expr *expr_propagate_params(struct pet_expr *expr,
2246 __isl_take isl_space *dim)
2248 int i;
2250 if (!expr)
2251 goto error;
2253 for (i = 0; i < expr->n_arg; ++i) {
2254 expr->args[i] =
2255 expr_propagate_params(expr->args[i],
2256 isl_space_copy(dim));
2257 if (!expr->args[i])
2258 goto error;
2261 if (expr->type == pet_expr_access) {
2262 expr->acc.access = isl_map_align_params(expr->acc.access,
2263 isl_space_copy(dim));
2264 if (!expr->acc.access)
2265 goto error;
2268 isl_space_free(dim);
2269 return expr;
2270 error:
2271 isl_space_free(dim);
2272 return pet_expr_free(expr);
2275 /* Add all parameters in "dim" to the domain, schedule and
2276 * all access relations in "stmt".
2278 static struct pet_stmt *stmt_propagate_params(struct pet_stmt *stmt,
2279 __isl_take isl_space *dim)
2281 if (!stmt)
2282 goto error;
2284 stmt->domain = isl_set_align_params(stmt->domain, isl_space_copy(dim));
2285 stmt->schedule = isl_map_align_params(stmt->schedule,
2286 isl_space_copy(dim));
2287 stmt->body = expr_propagate_params(stmt->body, isl_space_copy(dim));
2289 if (!stmt->domain || !stmt->schedule || !stmt->body)
2290 goto error;
2292 isl_space_free(dim);
2293 return stmt;
2294 error:
2295 isl_space_free(dim);
2296 return pet_stmt_free(stmt);
2299 /* Add all parameters in "dim" to "array".
2301 static struct pet_array *array_propagate_params(struct pet_array *array,
2302 __isl_take isl_space *dim)
2304 if (!array)
2305 goto error;
2307 array->context = isl_set_align_params(array->context,
2308 isl_space_copy(dim));
2309 array->extent = isl_set_align_params(array->extent,
2310 isl_space_copy(dim));
2311 if (array->value_bounds) {
2312 array->value_bounds = isl_set_align_params(array->value_bounds,
2313 isl_space_copy(dim));
2314 if (!array->value_bounds)
2315 goto error;
2318 if (!array->context || !array->extent)
2319 goto error;
2321 isl_space_free(dim);
2322 return array;
2323 error:
2324 isl_space_free(dim);
2325 return pet_array_free(array);
2328 /* Add all parameters in "dim" to "scop".
2330 static struct pet_scop *scop_propagate_params(struct pet_scop *scop,
2331 __isl_take isl_space *dim)
2333 int i;
2335 if (!scop)
2336 goto error;
2338 for (i = 0; i < scop->n_array; ++i) {
2339 scop->arrays[i] = array_propagate_params(scop->arrays[i],
2340 isl_space_copy(dim));
2341 if (!scop->arrays[i])
2342 goto error;
2345 for (i = 0; i < scop->n_stmt; ++i) {
2346 scop->stmts[i] = stmt_propagate_params(scop->stmts[i],
2347 isl_space_copy(dim));
2348 if (!scop->stmts[i])
2349 goto error;
2352 isl_space_free(dim);
2353 return scop;
2354 error:
2355 isl_space_free(dim);
2356 return pet_scop_free(scop);
2359 /* Update all isl_sets and isl_maps in "scop" such that they all
2360 * have the same parameters.
2362 struct pet_scop *pet_scop_align_params(struct pet_scop *scop)
2364 isl_space *dim;
2366 if (!scop)
2367 return NULL;
2369 dim = isl_set_get_space(scop->context);
2370 dim = scop_collect_params(scop, dim);
2372 scop->context = isl_set_align_params(scop->context, isl_space_copy(dim));
2373 scop = scop_propagate_params(scop, dim);
2375 return scop;
2378 /* Check if the given access relation accesses a (0D) array that corresponds
2379 * to one of the parameters in "dim". If so, replace the array access
2380 * by an access to the set of integers with as index (and value)
2381 * that parameter.
2383 static __isl_give isl_map *access_detect_parameter(__isl_take isl_map *access,
2384 __isl_take isl_space *dim)
2386 isl_id *array_id = NULL;
2387 int pos = -1;
2389 if (isl_map_has_tuple_id(access, isl_dim_out)) {
2390 array_id = isl_map_get_tuple_id(access, isl_dim_out);
2391 pos = isl_space_find_dim_by_id(dim, isl_dim_param, array_id);
2393 isl_space_free(dim);
2395 if (pos < 0) {
2396 isl_id_free(array_id);
2397 return access;
2400 pos = isl_map_find_dim_by_id(access, isl_dim_param, array_id);
2401 if (pos < 0) {
2402 access = isl_map_insert_dims(access, isl_dim_param, 0, 1);
2403 access = isl_map_set_dim_id(access, isl_dim_param, 0, array_id);
2404 pos = 0;
2405 } else
2406 isl_id_free(array_id);
2408 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
2409 access = isl_map_equate(access, isl_dim_param, pos, isl_dim_out, 0);
2411 return access;
2414 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2415 * in "dim" by a value equal to the corresponding parameter.
2417 static struct pet_expr *expr_detect_parameter_accesses(struct pet_expr *expr,
2418 __isl_take isl_space *dim)
2420 int i;
2422 if (!expr)
2423 goto error;
2425 for (i = 0; i < expr->n_arg; ++i) {
2426 expr->args[i] =
2427 expr_detect_parameter_accesses(expr->args[i],
2428 isl_space_copy(dim));
2429 if (!expr->args[i])
2430 goto error;
2433 if (expr->type == pet_expr_access) {
2434 expr->acc.access = access_detect_parameter(expr->acc.access,
2435 isl_space_copy(dim));
2436 if (!expr->acc.access)
2437 goto error;
2440 isl_space_free(dim);
2441 return expr;
2442 error:
2443 isl_space_free(dim);
2444 return pet_expr_free(expr);
2447 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2448 * in "dim" by a value equal to the corresponding parameter.
2450 static struct pet_stmt *stmt_detect_parameter_accesses(struct pet_stmt *stmt,
2451 __isl_take isl_space *dim)
2453 if (!stmt)
2454 goto error;
2456 stmt->body = expr_detect_parameter_accesses(stmt->body,
2457 isl_space_copy(dim));
2459 if (!stmt->domain || !stmt->schedule || !stmt->body)
2460 goto error;
2462 isl_space_free(dim);
2463 return stmt;
2464 error:
2465 isl_space_free(dim);
2466 return pet_stmt_free(stmt);
2469 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2470 * in "dim" by a value equal to the corresponding parameter.
2472 static struct pet_scop *scop_detect_parameter_accesses(struct pet_scop *scop,
2473 __isl_take isl_space *dim)
2475 int i;
2477 if (!scop)
2478 goto error;
2480 for (i = 0; i < scop->n_stmt; ++i) {
2481 scop->stmts[i] = stmt_detect_parameter_accesses(scop->stmts[i],
2482 isl_space_copy(dim));
2483 if (!scop->stmts[i])
2484 goto error;
2487 isl_space_free(dim);
2488 return scop;
2489 error:
2490 isl_space_free(dim);
2491 return pet_scop_free(scop);
2494 /* Replace all accesses to (0D) arrays that correspond to any of
2495 * the parameters used in "scop" by a value equal
2496 * to the corresponding parameter.
2498 struct pet_scop *pet_scop_detect_parameter_accesses(struct pet_scop *scop)
2500 isl_space *dim;
2502 if (!scop)
2503 return NULL;
2505 dim = isl_set_get_space(scop->context);
2506 dim = scop_collect_params(scop, dim);
2508 scop = scop_detect_parameter_accesses(scop, dim);
2510 return scop;
2513 /* Add all read access relations (if "read" is set) and/or all write
2514 * access relations (if "write" is set) to "accesses" and return the result.
2516 static __isl_give isl_union_map *expr_collect_accesses(struct pet_expr *expr,
2517 int read, int write, __isl_take isl_union_map *accesses)
2519 int i;
2520 isl_id *id;
2521 isl_space *dim;
2523 if (!expr)
2524 return NULL;
2526 for (i = 0; i < expr->n_arg; ++i)
2527 accesses = expr_collect_accesses(expr->args[i],
2528 read, write, accesses);
2530 if (expr->type == pet_expr_access &&
2531 isl_map_has_tuple_id(expr->acc.access, isl_dim_out) &&
2532 ((read && expr->acc.read) || (write && expr->acc.write)))
2533 accesses = isl_union_map_add_map(accesses,
2534 isl_map_copy(expr->acc.access));
2536 return accesses;
2539 /* Collect and return all read access relations (if "read" is set)
2540 * and/or all write * access relations (if "write" is set) in "stmt".
2542 static __isl_give isl_union_map *stmt_collect_accesses(struct pet_stmt *stmt,
2543 int read, int write, __isl_take isl_space *dim)
2545 isl_union_map *accesses;
2547 if (!stmt)
2548 return NULL;
2550 accesses = isl_union_map_empty(dim);
2551 accesses = expr_collect_accesses(stmt->body, read, write, accesses);
2552 accesses = isl_union_map_intersect_domain(accesses,
2553 isl_union_set_from_set(isl_set_copy(stmt->domain)));
2555 return accesses;
2558 /* Collect and return all read access relations (if "read" is set)
2559 * and/or all write * access relations (if "write" is set) in "scop".
2561 static __isl_give isl_union_map *scop_collect_accesses(struct pet_scop *scop,
2562 int read, int write)
2564 int i;
2565 isl_union_map *accesses;
2567 if (!scop)
2568 return NULL;
2570 accesses = isl_union_map_empty(isl_set_get_space(scop->context));
2572 for (i = 0; i < scop->n_stmt; ++i) {
2573 isl_union_map *accesses_i;
2574 isl_space *dim = isl_set_get_space(scop->context);
2575 accesses_i = stmt_collect_accesses(scop->stmts[i],
2576 read, write, dim);
2577 accesses = isl_union_map_union(accesses, accesses_i);
2580 return accesses;
2583 __isl_give isl_union_map *pet_scop_collect_reads(struct pet_scop *scop)
2585 return scop_collect_accesses(scop, 1, 0);
2588 __isl_give isl_union_map *pet_scop_collect_writes(struct pet_scop *scop)
2590 return scop_collect_accesses(scop, 0, 1);
2593 /* Collect and return the union of iteration domains in "scop".
2595 __isl_give isl_union_set *pet_scop_collect_domains(struct pet_scop *scop)
2597 int i;
2598 isl_set *domain_i;
2599 isl_union_set *domain;
2601 if (!scop)
2602 return NULL;
2604 domain = isl_union_set_empty(isl_set_get_space(scop->context));
2606 for (i = 0; i < scop->n_stmt; ++i) {
2607 domain_i = isl_set_copy(scop->stmts[i]->domain);
2608 domain = isl_union_set_add_set(domain, domain_i);
2611 return domain;
2614 /* Collect and return the schedules of the statements in "scop".
2615 * The range is normalized to the maximal number of scheduling
2616 * dimensions.
2618 __isl_give isl_union_map *pet_scop_collect_schedule(struct pet_scop *scop)
2620 int i, j;
2621 isl_map *schedule_i;
2622 isl_union_map *schedule;
2623 int depth, max_depth = 0;
2625 if (!scop)
2626 return NULL;
2628 schedule = isl_union_map_empty(isl_set_get_space(scop->context));
2630 for (i = 0; i < scop->n_stmt; ++i) {
2631 depth = isl_map_dim(scop->stmts[i]->schedule, isl_dim_out);
2632 if (depth > max_depth)
2633 max_depth = depth;
2636 for (i = 0; i < scop->n_stmt; ++i) {
2637 schedule_i = isl_map_copy(scop->stmts[i]->schedule);
2638 depth = isl_map_dim(schedule_i, isl_dim_out);
2639 schedule_i = isl_map_add_dims(schedule_i, isl_dim_out,
2640 max_depth - depth);
2641 for (j = depth; j < max_depth; ++j)
2642 schedule_i = isl_map_fix_si(schedule_i,
2643 isl_dim_out, j, 0);
2644 schedule = isl_union_map_add_map(schedule, schedule_i);
2647 return schedule;
2650 /* Does expression "expr" write to "id"?
2652 static int expr_writes(struct pet_expr *expr, __isl_keep isl_id *id)
2654 int i;
2655 isl_id *write_id;
2657 for (i = 0; i < expr->n_arg; ++i) {
2658 int writes = expr_writes(expr->args[i], id);
2659 if (writes < 0 || writes)
2660 return writes;
2663 if (expr->type != pet_expr_access)
2664 return 0;
2665 if (!expr->acc.write)
2666 return 0;
2667 if (!isl_map_has_tuple_id(expr->acc.access, isl_dim_out))
2668 return 0;
2670 write_id = isl_map_get_tuple_id(expr->acc.access, isl_dim_out);
2671 isl_id_free(write_id);
2673 if (!write_id)
2674 return -1;
2676 return write_id == id;
2679 /* Does statement "stmt" write to "id"?
2681 static int stmt_writes(struct pet_stmt *stmt, __isl_keep isl_id *id)
2683 return expr_writes(stmt->body, id);
2686 /* Is there any write access in "scop" that accesses "id"?
2688 int pet_scop_writes(struct pet_scop *scop, __isl_keep isl_id *id)
2690 int i;
2692 if (!scop)
2693 return -1;
2695 for (i = 0; i < scop->n_stmt; ++i) {
2696 int writes = stmt_writes(scop->stmts[i], id);
2697 if (writes < 0 || writes)
2698 return writes;
2701 return 0;
2704 /* Reset the user pointer on all parameter ids in "set".
2706 static __isl_give isl_set *set_anonymize(__isl_take isl_set *set)
2708 int i, n;
2710 n = isl_set_dim(set, isl_dim_param);
2711 for (i = 0; i < n; ++i) {
2712 isl_id *id = isl_set_get_dim_id(set, isl_dim_param, i);
2713 const char *name = isl_id_get_name(id);
2714 set = isl_set_set_dim_name(set, isl_dim_param, i, name);
2715 isl_id_free(id);
2718 return set;
2721 /* Reset the user pointer on all parameter ids in "map".
2723 static __isl_give isl_map *map_anonymize(__isl_take isl_map *map)
2725 int i, n;
2727 n = isl_map_dim(map, isl_dim_param);
2728 for (i = 0; i < n; ++i) {
2729 isl_id *id = isl_map_get_dim_id(map, isl_dim_param, i);
2730 const char *name = isl_id_get_name(id);
2731 map = isl_map_set_dim_name(map, isl_dim_param, i, name);
2732 isl_id_free(id);
2735 return map;
2738 /* Reset the user pointer on all parameter ids in "array".
2740 static struct pet_array *array_anonymize(struct pet_array *array)
2742 if (!array)
2743 return NULL;
2745 array->context = set_anonymize(array->context);
2746 array->extent = set_anonymize(array->extent);
2747 if (!array->context || !array->extent)
2748 return pet_array_free(array);
2750 return array;
2753 /* Reset the user pointer on all parameter ids in "access".
2755 static __isl_give isl_map *access_anonymize(__isl_take isl_map *access,
2756 void *user)
2758 access = map_anonymize(access);
2760 return access;
2763 /* Reset the user pointer on all parameter ids in "stmt".
2765 static struct pet_stmt *stmt_anonymize(struct pet_stmt *stmt)
2767 int i;
2768 isl_space *space;
2769 isl_set *domain;
2771 if (!stmt)
2772 return NULL;
2774 stmt->domain = set_anonymize(stmt->domain);
2775 stmt->schedule = map_anonymize(stmt->schedule);
2776 if (!stmt->domain || !stmt->schedule)
2777 return pet_stmt_free(stmt);
2779 for (i = 0; i < stmt->n_arg; ++i) {
2780 stmt->args[i] = pet_expr_foreach_access(stmt->args[i],
2781 &access_anonymize, NULL);
2782 if (!stmt->args[i])
2783 return pet_stmt_free(stmt);
2786 stmt->body = pet_expr_foreach_access(stmt->body,
2787 &access_anonymize, NULL);
2788 if (!stmt->body)
2789 return pet_stmt_free(stmt);
2791 return stmt;
2794 /* Reset the user pointer on all parameter ids in "scop".
2796 struct pet_scop *pet_scop_anonymize(struct pet_scop *scop)
2798 int i;
2800 if (!scop)
2801 return NULL;
2803 scop->context = set_anonymize(scop->context);
2804 scop->context_value = set_anonymize(scop->context_value);
2805 if (!scop->context || !scop->context_value)
2806 return pet_scop_free(scop);
2808 for (i = 0; i < scop->n_array; ++i) {
2809 scop->arrays[i] = array_anonymize(scop->arrays[i]);
2810 if (!scop->arrays[i])
2811 return pet_scop_free(scop);
2814 for (i = 0; i < scop->n_stmt; ++i) {
2815 scop->stmts[i] = stmt_anonymize(scop->stmts[i]);
2816 if (!scop->stmts[i])
2817 return pet_scop_free(scop);
2820 return scop;
2823 /* Given a set "domain", return a wrapped relation with the given set
2824 * as domain and a range of dimension "n_arg", where each coordinate
2825 * is either unbounded or, if the corresponding element of args is of
2826 * type pet_expr_access, bounded by the bounds specified by "value_bounds".
2828 static __isl_give isl_set *apply_value_bounds(__isl_take isl_set *domain,
2829 unsigned n_arg, struct pet_expr **args,
2830 __isl_keep isl_union_map *value_bounds)
2832 int i;
2833 isl_map *map;
2834 isl_space *space;
2835 isl_ctx *ctx = isl_set_get_ctx(domain);
2837 map = isl_map_from_domain(domain);
2838 space = isl_map_get_space(map);
2839 space = isl_space_add_dims(space, isl_dim_out, 1);
2841 for (i = 0; i < n_arg; ++i) {
2842 isl_map *map_i;
2843 struct pet_expr *arg = args[i];
2844 isl_id *id;
2845 isl_space *space2;
2847 map_i = isl_map_universe(isl_space_copy(space));
2848 if (arg->type == pet_expr_access) {
2849 isl_map *vb;
2850 id = isl_map_get_tuple_id(arg->acc.access, isl_dim_out);
2851 space2 = isl_space_alloc(ctx, 0, 0, 1);
2852 space2 = isl_space_set_tuple_id(space2, isl_dim_in, id);
2853 vb = isl_union_map_extract_map(value_bounds, space2);
2854 if (!isl_map_plain_is_empty(vb))
2855 map_i = isl_map_intersect_range(map_i,
2856 isl_map_range(vb));
2857 else
2858 isl_map_free(vb);
2860 map = isl_map_flat_range_product(map, map_i);
2862 isl_space_free(space);
2864 return isl_map_wrap(map);
2867 /* Data used in access_gist() callback.
2869 struct pet_access_gist_data {
2870 isl_set *domain;
2871 isl_union_map *value_bounds;
2874 /* Given an expression "expr" of type pet_expr_access, compute
2875 * the gist of the associated access relation with respect to
2876 * data->domain and the bounds on the values of the arguments
2877 * of the expression.
2879 static struct pet_expr *access_gist(struct pet_expr *expr, void *user)
2881 struct pet_access_gist_data *data = user;
2882 isl_set *domain;
2884 domain = isl_set_copy(data->domain);
2885 if (expr->n_arg > 0)
2886 domain = apply_value_bounds(domain, expr->n_arg, expr->args,
2887 data->value_bounds);
2889 expr->acc.access = isl_map_gist_domain(expr->acc.access, domain);
2890 if (!expr->acc.access)
2891 return pet_expr_free(expr);
2893 return expr;
2896 /* Compute the gist of the iteration domain and all access relations
2897 * of "stmt" based on the constraints on the parameters specified by "context"
2898 * and the constraints on the values of nested accesses specified
2899 * by "value_bounds".
2901 static struct pet_stmt *stmt_gist(struct pet_stmt *stmt,
2902 __isl_keep isl_set *context, __isl_keep isl_union_map *value_bounds)
2904 int i;
2905 isl_space *space;
2906 isl_set *domain;
2907 struct pet_access_gist_data data;
2909 if (!stmt)
2910 return NULL;
2912 data.domain = isl_set_copy(stmt->domain);
2913 data.value_bounds = value_bounds;
2914 if (stmt->n_arg > 0)
2915 data.domain = isl_map_domain(isl_set_unwrap(data.domain));
2917 data.domain = isl_set_intersect_params(data.domain,
2918 isl_set_copy(context));
2920 for (i = 0; i < stmt->n_arg; ++i) {
2921 stmt->args[i] = pet_expr_foreach_access_expr(stmt->args[i],
2922 &access_gist, &data);
2923 if (!stmt->args[i])
2924 goto error;
2927 stmt->body = pet_expr_foreach_access_expr(stmt->body,
2928 &access_gist, &data);
2929 if (!stmt->body)
2930 goto error;
2932 isl_set_free(data.domain);
2934 space = isl_set_get_space(stmt->domain);
2935 if (isl_space_is_wrapping(space))
2936 space = isl_space_domain(isl_space_unwrap(space));
2937 domain = isl_set_universe(space);
2938 domain = isl_set_intersect_params(domain, isl_set_copy(context));
2939 if (stmt->n_arg > 0)
2940 domain = apply_value_bounds(domain, stmt->n_arg, stmt->args,
2941 value_bounds);
2942 stmt->domain = isl_set_gist(stmt->domain, domain);
2943 if (!stmt->domain)
2944 return pet_stmt_free(stmt);
2946 return stmt;
2947 error:
2948 isl_set_free(data.domain);
2949 return pet_stmt_free(stmt);
2952 /* Compute the gist of the extent of the array
2953 * based on the constraints on the parameters specified by "context".
2955 static struct pet_array *array_gist(struct pet_array *array,
2956 __isl_keep isl_set *context)
2958 if (!array)
2959 return NULL;
2961 array->extent = isl_set_gist_params(array->extent,
2962 isl_set_copy(context));
2963 if (!array->extent)
2964 return pet_array_free(array);
2966 return array;
2969 /* Compute the gist of all sets and relations in "scop"
2970 * based on the constraints on the parameters specified by "scop->context"
2971 * and the constraints on the values of nested accesses specified
2972 * by "value_bounds".
2974 struct pet_scop *pet_scop_gist(struct pet_scop *scop,
2975 __isl_keep isl_union_map *value_bounds)
2977 int i;
2979 if (!scop)
2980 return NULL;
2982 scop->context = isl_set_coalesce(scop->context);
2983 if (!scop->context)
2984 return pet_scop_free(scop);
2986 for (i = 0; i < scop->n_array; ++i) {
2987 scop->arrays[i] = array_gist(scop->arrays[i], scop->context);
2988 if (!scop->arrays[i])
2989 return pet_scop_free(scop);
2992 for (i = 0; i < scop->n_stmt; ++i) {
2993 scop->stmts[i] = stmt_gist(scop->stmts[i], scop->context,
2994 value_bounds);
2995 if (!scop->stmts[i])
2996 return pet_scop_free(scop);
2999 return scop;
3002 /* Intersect the context of "scop" with "context".
3003 * To ensure that we don't introduce any unnamed parameters in
3004 * the context of "scop", we first remove the unnamed parameters
3005 * from "context".
3007 struct pet_scop *pet_scop_restrict_context(struct pet_scop *scop,
3008 __isl_take isl_set *context)
3010 if (!scop)
3011 goto error;
3013 context = set_project_out_unnamed_params(context);
3014 scop->context = isl_set_intersect(scop->context, context);
3015 if (!scop->context)
3016 return pet_scop_free(scop);
3018 return scop;
3019 error:
3020 isl_set_free(context);
3021 return pet_scop_free(scop);
3024 /* Drop the current context of "scop". That is, replace the context
3025 * by a universal set.
3027 struct pet_scop *pet_scop_reset_context(struct pet_scop *scop)
3029 isl_space *space;
3031 if (!scop)
3032 return NULL;
3034 space = isl_set_get_space(scop->context);
3035 isl_set_free(scop->context);
3036 scop->context = isl_set_universe(space);
3037 if (!scop->context)
3038 return pet_scop_free(scop);
3040 return scop;
3043 /* Append "array" to the arrays of "scop".
3045 struct pet_scop *pet_scop_add_array(struct pet_scop *scop,
3046 struct pet_array *array)
3048 isl_ctx *ctx;
3049 struct pet_array **arrays;
3051 if (!array || !scop)
3052 goto error;
3054 ctx = isl_set_get_ctx(scop->context);
3055 arrays = isl_realloc_array(ctx, scop->arrays, struct pet_array *,
3056 scop->n_array + 1);
3057 if (!arrays)
3058 goto error;
3059 scop->arrays = arrays;
3060 scop->arrays[scop->n_array] = array;
3061 scop->n_array++;
3063 return scop;
3064 error:
3065 pet_array_free(array);
3066 return pet_scop_free(scop);