PetScan::extract_for: move up extraction of constant increment
[pet.git] / scop.c
blob3b5c2b682bad7427d56e9ffd37fdf30b05683d78
1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2014 Ecole Normale Superieure. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer in the documentation and/or other materials provided
15 * with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 * The views and conclusions contained in the software and documentation
30 * are those of the authors and should not be interpreted as
31 * representing official policies, either expressed or implied, of
32 * Leiden University.
33 */
35 #include <string.h>
36 #include <isl/constraint.h>
37 #include <isl/union_set.h>
39 #include "expr.h"
40 #include "filter.h"
41 #include "nest.h"
42 #include "scop.h"
43 #include "print.h"
44 #include "value_bounds.h"
46 /* pet_scop with extra information that is used during parsing and printing.
48 * In particular, we keep track of conditions under which we want
49 * to skip the rest of the current loop iteration (skip[pet_skip_now])
50 * and of conditions under which we want to skip subsequent
51 * loop iterations (skip[pet_skip_later]).
53 * The conditions are represented as index expressions defined
54 * over a zero-dimensional domain. The index expression is either
55 * a boolean affine expression or an access to a variable, which
56 * is assumed to attain values zero and one. The condition holds
57 * if the variable has value one or if the affine expression
58 * has value one (typically for only part of the parameter space).
60 * A missing condition (skip[type] == NULL) means that we don't want
61 * to skip anything.
63 * Additionally, we keep track of the original input file
64 * inside pet_transform_C_source.
66 struct pet_scop_ext {
67 struct pet_scop scop;
69 isl_multi_pw_aff *skip[2];
70 FILE *input;
73 /* Construct a pet_stmt with given line number and statement
74 * number from a pet_expr.
75 * The initial iteration domain is the zero-dimensional universe.
76 * The name of the domain is given by "label" if it is non-NULL.
77 * Otherwise, the name is constructed as S_<id>.
78 * The domains of all access relations are modified to refer
79 * to the statement iteration domain.
81 struct pet_stmt *pet_stmt_from_pet_expr(int line, __isl_take isl_id *label,
82 int id, __isl_take pet_expr *expr)
84 struct pet_stmt *stmt;
85 isl_ctx *ctx;
86 isl_space *dim;
87 isl_set *dom;
88 isl_map *sched;
89 isl_multi_pw_aff *add_name;
90 char name[50];
92 if (!expr)
93 goto error;
95 ctx = pet_expr_get_ctx(expr);
96 stmt = isl_calloc_type(ctx, struct pet_stmt);
97 if (!stmt)
98 goto error;
100 dim = isl_space_set_alloc(ctx, 0, 0);
101 if (label)
102 dim = isl_space_set_tuple_id(dim, isl_dim_set, label);
103 else {
104 snprintf(name, sizeof(name), "S_%d", id);
105 dim = isl_space_set_tuple_name(dim, isl_dim_set, name);
107 dom = isl_set_universe(isl_space_copy(dim));
108 sched = isl_map_from_domain(isl_set_copy(dom));
110 dim = isl_space_from_domain(dim);
111 add_name = isl_multi_pw_aff_zero(dim);
112 expr = pet_expr_update_domain(expr, add_name);
114 stmt->line = line;
115 stmt->domain = dom;
116 stmt->schedule = sched;
117 stmt->body = expr;
119 if (!stmt->domain || !stmt->schedule || !stmt->body)
120 return pet_stmt_free(stmt);
122 return stmt;
123 error:
124 isl_id_free(label);
125 pet_expr_free(expr);
126 return NULL;
129 void *pet_stmt_free(struct pet_stmt *stmt)
131 int i;
133 if (!stmt)
134 return NULL;
136 isl_set_free(stmt->domain);
137 isl_map_free(stmt->schedule);
138 pet_expr_free(stmt->body);
140 for (i = 0; i < stmt->n_arg; ++i)
141 pet_expr_free(stmt->args[i]);
142 free(stmt->args);
144 free(stmt);
145 return NULL;
148 /* Return the iteration space of "stmt".
150 * If the statement has arguments, then stmt->domain is a wrapped map
151 * mapping the iteration domain to the values of the arguments
152 * for which this statement is executed.
153 * In this case, we need to extract the domain space of this wrapped map.
155 __isl_give isl_space *pet_stmt_get_space(struct pet_stmt *stmt)
157 isl_space *space;
159 if (!stmt)
160 return NULL;
162 space = isl_set_get_space(stmt->domain);
163 if (isl_space_is_wrapping(space))
164 space = isl_space_domain(isl_space_unwrap(space));
166 return space;
169 static void stmt_dump(struct pet_stmt *stmt, int indent)
171 int i;
173 if (!stmt)
174 return;
176 fprintf(stderr, "%*s%d\n", indent, "", stmt->line);
177 fprintf(stderr, "%*s", indent, "");
178 isl_set_dump(stmt->domain);
179 fprintf(stderr, "%*s", indent, "");
180 isl_map_dump(stmt->schedule);
181 pet_expr_dump_with_indent(stmt->body, indent);
182 for (i = 0; i < stmt->n_arg; ++i)
183 pet_expr_dump_with_indent(stmt->args[i], indent + 2);
186 void pet_stmt_dump(struct pet_stmt *stmt)
188 stmt_dump(stmt, 0);
191 /* Allocate a new pet_type with the given "name" and "definition".
193 struct pet_type *pet_type_alloc(isl_ctx *ctx, const char *name,
194 const char *definition)
196 struct pet_type *type;
198 type = isl_alloc_type(ctx, struct pet_type);
199 if (!type)
200 return NULL;
202 type->name = strdup(name);
203 type->definition = strdup(definition);
205 if (!type->name || !type->definition)
206 return pet_type_free(type);
208 return type;
211 /* Free "type" and return NULL.
213 struct pet_type *pet_type_free(struct pet_type *type)
215 if (!type)
216 return NULL;
218 free(type->name);
219 free(type->definition);
221 free(type);
222 return NULL;
225 struct pet_array *pet_array_free(struct pet_array *array)
227 if (!array)
228 return NULL;
230 isl_set_free(array->context);
231 isl_set_free(array->extent);
232 isl_set_free(array->value_bounds);
233 free(array->element_type);
235 free(array);
236 return NULL;
239 void pet_array_dump(struct pet_array *array)
241 if (!array)
242 return;
244 isl_set_dump(array->context);
245 isl_set_dump(array->extent);
246 isl_set_dump(array->value_bounds);
247 fprintf(stderr, "%s%s%s\n", array->element_type,
248 array->element_is_record ? " element-is-record" : "",
249 array->live_out ? " live-out" : "");
252 /* Alloc a pet_scop structure, with extra room for information that
253 * is only used during parsing.
255 struct pet_scop *pet_scop_alloc(isl_ctx *ctx)
257 return &isl_calloc_type(ctx, struct pet_scop_ext)->scop;
260 /* Construct a pet_scop with room for n statements.
262 static struct pet_scop *scop_alloc(isl_ctx *ctx, int n)
264 isl_space *space;
265 struct pet_scop *scop;
267 scop = pet_scop_alloc(ctx);
268 if (!scop)
269 return NULL;
271 space = isl_space_params_alloc(ctx, 0);
272 scop->context = isl_set_universe(isl_space_copy(space));
273 scop->context_value = isl_set_universe(space);
274 scop->stmts = isl_calloc_array(ctx, struct pet_stmt *, n);
275 if (!scop->context || !scop->stmts)
276 return pet_scop_free(scop);
278 scop->n_stmt = n;
280 return scop;
283 struct pet_scop *pet_scop_empty(isl_ctx *ctx)
285 return scop_alloc(ctx, 0);
288 /* Update "context" with respect to the valid parameter values for "access".
290 static __isl_give isl_set *access_extract_context(__isl_keep isl_map *access,
291 __isl_take isl_set *context)
293 context = isl_set_intersect(context,
294 isl_map_params(isl_map_copy(access)));
295 return context;
298 /* Update "context" with respect to the valid parameter values for "expr".
300 * If "expr" represents a conditional operator, then a parameter value
301 * needs to be valid for the condition and for at least one of the
302 * remaining two arguments.
303 * If the condition is an affine expression, then we can be a bit more specific.
304 * The parameter then has to be valid for the second argument for
305 * non-zero accesses and valid for the third argument for zero accesses.
307 static __isl_give isl_set *expr_extract_context(__isl_keep pet_expr *expr,
308 __isl_take isl_set *context)
310 int i;
312 if (expr->type == pet_expr_op && expr->op == pet_op_cond) {
313 int is_aff;
314 isl_set *context1, *context2;
316 is_aff = pet_expr_is_affine(expr->args[0]);
317 if (is_aff < 0)
318 goto error;
320 context = expr_extract_context(expr->args[0], context);
321 context1 = expr_extract_context(expr->args[1],
322 isl_set_copy(context));
323 context2 = expr_extract_context(expr->args[2], context);
325 if (is_aff) {
326 isl_map *access;
327 isl_set *zero_set;
329 access = isl_map_copy(expr->args[0]->acc.access);
330 access = isl_map_fix_si(access, isl_dim_out, 0, 0);
331 zero_set = isl_map_params(access);
332 context1 = isl_set_subtract(context1,
333 isl_set_copy(zero_set));
334 context2 = isl_set_intersect(context2, zero_set);
337 context = isl_set_union(context1, context2);
338 context = isl_set_coalesce(context);
340 return context;
343 for (i = 0; i < expr->n_arg; ++i)
344 context = expr_extract_context(expr->args[i], context);
346 if (expr->type == pet_expr_access)
347 context = access_extract_context(expr->acc.access, context);
349 return context;
350 error:
351 isl_set_free(context);
352 return NULL;
355 /* Update "context" with respect to the valid parameter values for "stmt".
357 * If the statement is an assume statement with an affine expression,
358 * then intersect "context" with that expression.
359 * Otherwise, intersect "context" with the contexts of the expressions
360 * inside "stmt".
362 static __isl_give isl_set *stmt_extract_context(struct pet_stmt *stmt,
363 __isl_take isl_set *context)
365 int i;
367 if (pet_stmt_is_assume(stmt) &&
368 pet_expr_is_affine(stmt->body->args[0])) {
369 isl_multi_pw_aff *index;
370 isl_pw_aff *pa;
371 isl_set *cond;
373 index = stmt->body->args[0]->acc.index;
374 pa = isl_multi_pw_aff_get_pw_aff(index, 0);
375 cond = isl_set_params(isl_pw_aff_non_zero_set(pa));
376 return isl_set_intersect(context, cond);
379 for (i = 0; i < stmt->n_arg; ++i)
380 context = expr_extract_context(stmt->args[i], context);
382 context = expr_extract_context(stmt->body, context);
384 return context;
387 /* Construct a pet_scop that contains the given pet_stmt.
389 struct pet_scop *pet_scop_from_pet_stmt(isl_ctx *ctx, struct pet_stmt *stmt)
391 struct pet_scop *scop;
393 if (!stmt)
394 return NULL;
396 scop = scop_alloc(ctx, 1);
397 if (!scop)
398 goto error;
400 scop->context = stmt_extract_context(stmt, scop->context);
401 if (!scop->context)
402 goto error;
404 scop->stmts[0] = stmt;
406 return scop;
407 error:
408 pet_stmt_free(stmt);
409 pet_scop_free(scop);
410 return NULL;
413 /* Does "mpa" represent an access to an element of an unnamed space, i.e.,
414 * does it represent an affine expression?
416 static int multi_pw_aff_is_affine(__isl_keep isl_multi_pw_aff *mpa)
418 int has_id;
420 has_id = isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out);
421 if (has_id < 0)
422 return -1;
424 return !has_id;
427 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
429 static __isl_give isl_pw_aff *indicator_function(__isl_take isl_set *set,
430 __isl_take isl_set *dom)
432 isl_pw_aff *pa;
433 pa = isl_set_indicator_function(set);
434 pa = isl_pw_aff_intersect_domain(pa, dom);
435 return pa;
438 /* Return "lhs || rhs", defined on the shared definition domain.
440 static __isl_give isl_pw_aff *pw_aff_or(__isl_take isl_pw_aff *lhs,
441 __isl_take isl_pw_aff *rhs)
443 isl_set *cond;
444 isl_set *dom;
446 dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs)),
447 isl_pw_aff_domain(isl_pw_aff_copy(rhs)));
448 cond = isl_set_union(isl_pw_aff_non_zero_set(lhs),
449 isl_pw_aff_non_zero_set(rhs));
450 cond = isl_set_coalesce(cond);
451 return indicator_function(cond, dom);
454 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
455 * ext may be equal to either ext1 or ext2.
457 * The two skips that need to be combined are assumed to be affine expressions.
459 * We need to skip in ext if we need to skip in either ext1 or ext2.
460 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
462 static struct pet_scop_ext *combine_skips(struct pet_scop_ext *ext,
463 struct pet_scop_ext *ext1, struct pet_scop_ext *ext2,
464 enum pet_skip type)
466 isl_pw_aff *skip, *skip1, *skip2;
468 if (!ext)
469 return NULL;
470 if (!ext1->skip[type] && !ext2->skip[type])
471 return ext;
472 if (!ext1->skip[type]) {
473 if (ext == ext2)
474 return ext;
475 ext->skip[type] = ext2->skip[type];
476 ext2->skip[type] = NULL;
477 return ext;
479 if (!ext2->skip[type]) {
480 if (ext == ext1)
481 return ext;
482 ext->skip[type] = ext1->skip[type];
483 ext1->skip[type] = NULL;
484 return ext;
487 if (!multi_pw_aff_is_affine(ext1->skip[type]) ||
488 !multi_pw_aff_is_affine(ext2->skip[type]))
489 isl_die(isl_multi_pw_aff_get_ctx(ext1->skip[type]),
490 isl_error_internal, "can only combine affine skips",
491 goto error);
493 skip1 = isl_multi_pw_aff_get_pw_aff(ext1->skip[type], 0);
494 skip2 = isl_multi_pw_aff_get_pw_aff(ext2->skip[type], 0);
495 skip = pw_aff_or(skip1, skip2);
496 isl_multi_pw_aff_free(ext1->skip[type]);
497 ext1->skip[type] = NULL;
498 isl_multi_pw_aff_free(ext2->skip[type]);
499 ext2->skip[type] = NULL;
500 ext->skip[type] = isl_multi_pw_aff_from_pw_aff(skip);
501 if (!ext->skip[type])
502 goto error;
504 return ext;
505 error:
506 pet_scop_free(&ext->scop);
507 return NULL;
510 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
511 * where type takes on the values pet_skip_now and pet_skip_later.
512 * scop may be equal to either scop1 or scop2.
514 static struct pet_scop *scop_combine_skips(struct pet_scop *scop,
515 struct pet_scop *scop1, struct pet_scop *scop2)
517 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
518 struct pet_scop_ext *ext1 = (struct pet_scop_ext *) scop1;
519 struct pet_scop_ext *ext2 = (struct pet_scop_ext *) scop2;
521 ext = combine_skips(ext, ext1, ext2, pet_skip_now);
522 ext = combine_skips(ext, ext1, ext2, pet_skip_later);
523 return &ext->scop;
526 /* Update scop->start and scop->end to include the region from "start"
527 * to "end". In particular, if scop->end == 0, then "scop" does not
528 * have any offset information yet and we simply take the information
529 * from "start" and "end". Otherwise, we update the fields if the
530 * region from "start" to "end" is not already included.
532 struct pet_scop *pet_scop_update_start_end(struct pet_scop *scop,
533 unsigned start, unsigned end)
535 if (!scop)
536 return NULL;
537 if (scop->end == 0) {
538 scop->start = start;
539 scop->end = end;
540 } else {
541 if (start < scop->start)
542 scop->start = start;
543 if (end > scop->end)
544 scop->end = end;
547 return scop;
550 /* Does "implication" appear in the list of implications of "scop"?
552 static int is_known_implication(struct pet_scop *scop,
553 struct pet_implication *implication)
555 int i;
557 for (i = 0; i < scop->n_implication; ++i) {
558 struct pet_implication *pi = scop->implications[i];
559 int equal;
561 if (pi->satisfied != implication->satisfied)
562 continue;
563 equal = isl_map_is_equal(pi->extension, implication->extension);
564 if (equal < 0)
565 return -1;
566 if (equal)
567 return 1;
570 return 0;
573 /* Store the concatenation of the implications of "scop1" and "scop2"
574 * in "scop", removing duplicates (i.e., implications in "scop2" that
575 * already appear in "scop1").
577 static struct pet_scop *scop_collect_implications(isl_ctx *ctx,
578 struct pet_scop *scop, struct pet_scop *scop1, struct pet_scop *scop2)
580 int i, j;
582 if (!scop)
583 return NULL;
585 if (scop2->n_implication == 0) {
586 scop->n_implication = scop1->n_implication;
587 scop->implications = scop1->implications;
588 scop1->n_implication = 0;
589 scop1->implications = NULL;
590 return scop;
593 if (scop1->n_implication == 0) {
594 scop->n_implication = scop2->n_implication;
595 scop->implications = scop2->implications;
596 scop2->n_implication = 0;
597 scop2->implications = NULL;
598 return scop;
601 scop->implications = isl_calloc_array(ctx, struct pet_implication *,
602 scop1->n_implication + scop2->n_implication);
603 if (!scop->implications)
604 return pet_scop_free(scop);
606 for (i = 0; i < scop1->n_implication; ++i) {
607 scop->implications[i] = scop1->implications[i];
608 scop1->implications[i] = NULL;
611 scop->n_implication = scop1->n_implication;
612 j = scop1->n_implication;
613 for (i = 0; i < scop2->n_implication; ++i) {
614 int known;
616 known = is_known_implication(scop, scop2->implications[i]);
617 if (known < 0)
618 return pet_scop_free(scop);
619 if (known)
620 continue;
621 scop->implications[j++] = scop2->implications[i];
622 scop2->implications[i] = NULL;
624 scop->n_implication = j;
626 return scop;
629 /* Combine the offset information of "scop1" and "scop2" into "scop".
631 static struct pet_scop *scop_combine_start_end(struct pet_scop *scop,
632 struct pet_scop *scop1, struct pet_scop *scop2)
634 if (scop1->end)
635 scop = pet_scop_update_start_end(scop,
636 scop1->start, scop1->end);
637 if (scop2->end)
638 scop = pet_scop_update_start_end(scop,
639 scop2->start, scop2->end);
640 return scop;
643 /* Construct a pet_scop that contains the offset information,
644 * arrays, statements and skip information in "scop1" and "scop2".
646 static struct pet_scop *pet_scop_add(isl_ctx *ctx, struct pet_scop *scop1,
647 struct pet_scop *scop2)
649 int i;
650 struct pet_scop *scop = NULL;
652 if (!scop1 || !scop2)
653 goto error;
655 if (scop1->n_stmt == 0) {
656 scop2 = scop_combine_skips(scop2, scop1, scop2);
657 pet_scop_free(scop1);
658 return scop2;
661 if (scop2->n_stmt == 0) {
662 scop1 = scop_combine_skips(scop1, scop1, scop2);
663 pet_scop_free(scop2);
664 return scop1;
667 scop = scop_alloc(ctx, scop1->n_stmt + scop2->n_stmt);
668 if (!scop)
669 goto error;
671 scop->arrays = isl_calloc_array(ctx, struct pet_array *,
672 scop1->n_array + scop2->n_array);
673 if (!scop->arrays)
674 goto error;
675 scop->n_array = scop1->n_array + scop2->n_array;
677 for (i = 0; i < scop1->n_stmt; ++i) {
678 scop->stmts[i] = scop1->stmts[i];
679 scop1->stmts[i] = NULL;
682 for (i = 0; i < scop2->n_stmt; ++i) {
683 scop->stmts[scop1->n_stmt + i] = scop2->stmts[i];
684 scop2->stmts[i] = NULL;
687 for (i = 0; i < scop1->n_array; ++i) {
688 scop->arrays[i] = scop1->arrays[i];
689 scop1->arrays[i] = NULL;
692 for (i = 0; i < scop2->n_array; ++i) {
693 scop->arrays[scop1->n_array + i] = scop2->arrays[i];
694 scop2->arrays[i] = NULL;
697 scop = scop_collect_implications(ctx, scop, scop1, scop2);
698 scop = pet_scop_restrict_context(scop, isl_set_copy(scop1->context));
699 scop = pet_scop_restrict_context(scop, isl_set_copy(scop2->context));
700 scop = scop_combine_skips(scop, scop1, scop2);
701 scop = scop_combine_start_end(scop, scop1, scop2);
703 pet_scop_free(scop1);
704 pet_scop_free(scop2);
705 return scop;
706 error:
707 pet_scop_free(scop1);
708 pet_scop_free(scop2);
709 pet_scop_free(scop);
710 return NULL;
713 /* Apply the skip condition "skip" to "scop".
714 * That is, make sure "scop" is not executed when the condition holds.
716 * If "skip" is an affine expression, we add the conditions under
717 * which the expression is zero to the iteration domains.
718 * Otherwise, we add a filter on the variable attaining the value zero.
720 static struct pet_scop *restrict_skip(struct pet_scop *scop,
721 __isl_take isl_multi_pw_aff *skip)
723 isl_set *zero;
724 isl_pw_aff *pa;
725 int is_aff;
727 if (!scop || !skip)
728 goto error;
730 is_aff = multi_pw_aff_is_affine(skip);
731 if (is_aff < 0)
732 goto error;
734 if (!is_aff)
735 return pet_scop_filter(scop, skip, 0);
737 pa = isl_multi_pw_aff_get_pw_aff(skip, 0);
738 isl_multi_pw_aff_free(skip);
739 zero = isl_set_params(isl_pw_aff_zero_set(pa));
740 scop = pet_scop_restrict(scop, zero);
742 return scop;
743 error:
744 isl_multi_pw_aff_free(skip);
745 return pet_scop_free(scop);
748 /* Construct a pet_scop that contains the arrays, statements and
749 * skip information in "scop1" and "scop2", where the two scops
750 * are executed "in sequence". That is, breaks and continues
751 * in scop1 have an effect on scop2.
753 struct pet_scop *pet_scop_add_seq(isl_ctx *ctx, struct pet_scop *scop1,
754 struct pet_scop *scop2)
756 if (scop1 && pet_scop_has_skip(scop1, pet_skip_now))
757 scop2 = restrict_skip(scop2,
758 pet_scop_get_skip(scop1, pet_skip_now));
759 return pet_scop_add(ctx, scop1, scop2);
762 /* Construct a pet_scop that contains the arrays, statements and
763 * skip information in "scop1" and "scop2", where the two scops
764 * are executed "in parallel". That is, any break or continue
765 * in scop1 has no effect on scop2.
767 struct pet_scop *pet_scop_add_par(isl_ctx *ctx, struct pet_scop *scop1,
768 struct pet_scop *scop2)
770 return pet_scop_add(ctx, scop1, scop2);
773 void *pet_implication_free(struct pet_implication *implication)
775 int i;
777 if (!implication)
778 return NULL;
780 isl_map_free(implication->extension);
782 free(implication);
783 return NULL;
786 struct pet_scop *pet_scop_free(struct pet_scop *scop)
788 int i;
789 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
791 if (!scop)
792 return NULL;
793 isl_set_free(scop->context);
794 isl_set_free(scop->context_value);
795 if (scop->types)
796 for (i = 0; i < scop->n_type; ++i)
797 pet_type_free(scop->types[i]);
798 free(scop->types);
799 if (scop->arrays)
800 for (i = 0; i < scop->n_array; ++i)
801 pet_array_free(scop->arrays[i]);
802 free(scop->arrays);
803 if (scop->stmts)
804 for (i = 0; i < scop->n_stmt; ++i)
805 pet_stmt_free(scop->stmts[i]);
806 free(scop->stmts);
807 if (scop->implications)
808 for (i = 0; i < scop->n_implication; ++i)
809 pet_implication_free(scop->implications[i]);
810 free(scop->implications);
811 isl_multi_pw_aff_free(ext->skip[pet_skip_now]);
812 isl_multi_pw_aff_free(ext->skip[pet_skip_later]);
813 free(scop);
814 return NULL;
817 void pet_type_dump(struct pet_type *type)
819 if (!type)
820 return;
822 fprintf(stderr, "%s -> %s\n", type->name, type->definition);
825 void pet_implication_dump(struct pet_implication *implication)
827 if (!implication)
828 return;
830 fprintf(stderr, "%d\n", implication->satisfied);
831 isl_map_dump(implication->extension);
834 void pet_scop_dump(struct pet_scop *scop)
836 int i;
837 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
839 if (!scop)
840 return;
842 isl_set_dump(scop->context);
843 isl_set_dump(scop->context_value);
844 for (i = 0; i < scop->n_type; ++i)
845 pet_type_dump(scop->types[i]);
846 for (i = 0; i < scop->n_array; ++i)
847 pet_array_dump(scop->arrays[i]);
848 for (i = 0; i < scop->n_stmt; ++i)
849 pet_stmt_dump(scop->stmts[i]);
850 for (i = 0; i < scop->n_implication; ++i)
851 pet_implication_dump(scop->implications[i]);
853 if (ext->skip[0]) {
854 fprintf(stderr, "skip\n");
855 isl_multi_pw_aff_dump(ext->skip[0]);
856 isl_multi_pw_aff_dump(ext->skip[1]);
860 /* Return 1 if the two pet_arrays are equivalent.
862 * We don't compare element_size as this may be target dependent.
864 int pet_array_is_equal(struct pet_array *array1, struct pet_array *array2)
866 if (!array1 || !array2)
867 return 0;
869 if (!isl_set_is_equal(array1->context, array2->context))
870 return 0;
871 if (!isl_set_is_equal(array1->extent, array2->extent))
872 return 0;
873 if (!!array1->value_bounds != !!array2->value_bounds)
874 return 0;
875 if (array1->value_bounds &&
876 !isl_set_is_equal(array1->value_bounds, array2->value_bounds))
877 return 0;
878 if (strcmp(array1->element_type, array2->element_type))
879 return 0;
880 if (array1->element_is_record != array2->element_is_record)
881 return 0;
882 if (array1->live_out != array2->live_out)
883 return 0;
884 if (array1->uniquely_defined != array2->uniquely_defined)
885 return 0;
886 if (array1->declared != array2->declared)
887 return 0;
888 if (array1->exposed != array2->exposed)
889 return 0;
891 return 1;
894 /* Return 1 if the two pet_stmts are equivalent.
896 int pet_stmt_is_equal(struct pet_stmt *stmt1, struct pet_stmt *stmt2)
898 int i;
900 if (!stmt1 || !stmt2)
901 return 0;
903 if (stmt1->line != stmt2->line)
904 return 0;
905 if (!isl_set_is_equal(stmt1->domain, stmt2->domain))
906 return 0;
907 if (!isl_map_is_equal(stmt1->schedule, stmt2->schedule))
908 return 0;
909 if (!pet_expr_is_equal(stmt1->body, stmt2->body))
910 return 0;
911 if (stmt1->n_arg != stmt2->n_arg)
912 return 0;
913 for (i = 0; i < stmt1->n_arg; ++i) {
914 if (!pet_expr_is_equal(stmt1->args[i], stmt2->args[i]))
915 return 0;
918 return 1;
921 /* Return 1 if the two pet_types are equivalent.
923 * We only compare the names of the types since the exact representation
924 * of the definition may depend on the version of clang being used.
926 int pet_type_is_equal(struct pet_type *type1, struct pet_type *type2)
928 if (!type1 || !type2)
929 return 0;
931 if (strcmp(type1->name, type2->name))
932 return 0;
934 return 1;
937 /* Return 1 if the two pet_implications are equivalent.
939 int pet_implication_is_equal(struct pet_implication *implication1,
940 struct pet_implication *implication2)
942 if (!implication1 || !implication2)
943 return 0;
945 if (implication1->satisfied != implication2->satisfied)
946 return 0;
947 if (!isl_map_is_equal(implication1->extension, implication2->extension))
948 return 0;
950 return 1;
953 /* Return 1 if the two pet_scops are equivalent.
955 int pet_scop_is_equal(struct pet_scop *scop1, struct pet_scop *scop2)
957 int i;
959 if (!scop1 || !scop2)
960 return 0;
962 if (!isl_set_is_equal(scop1->context, scop2->context))
963 return 0;
964 if (!isl_set_is_equal(scop1->context_value, scop2->context_value))
965 return 0;
967 if (scop1->n_type != scop2->n_type)
968 return 0;
969 for (i = 0; i < scop1->n_type; ++i)
970 if (!pet_type_is_equal(scop1->types[i], scop2->types[i]))
971 return 0;
973 if (scop1->n_array != scop2->n_array)
974 return 0;
975 for (i = 0; i < scop1->n_array; ++i)
976 if (!pet_array_is_equal(scop1->arrays[i], scop2->arrays[i]))
977 return 0;
979 if (scop1->n_stmt != scop2->n_stmt)
980 return 0;
981 for (i = 0; i < scop1->n_stmt; ++i)
982 if (!pet_stmt_is_equal(scop1->stmts[i], scop2->stmts[i]))
983 return 0;
985 if (scop1->n_implication != scop2->n_implication)
986 return 0;
987 for (i = 0; i < scop1->n_implication; ++i)
988 if (!pet_implication_is_equal(scop1->implications[i],
989 scop2->implications[i]))
990 return 0;
992 return 1;
995 /* Prefix the schedule of "stmt" with an extra dimension with constant
996 * value "pos".
998 struct pet_stmt *pet_stmt_prefix(struct pet_stmt *stmt, int pos)
1000 if (!stmt)
1001 return NULL;
1003 stmt->schedule = isl_map_insert_dims(stmt->schedule, isl_dim_out, 0, 1);
1004 stmt->schedule = isl_map_fix_si(stmt->schedule, isl_dim_out, 0, pos);
1005 if (!stmt->schedule)
1006 return pet_stmt_free(stmt);
1008 return stmt;
1011 /* Prefix the schedules of all statements in "scop" with an extra
1012 * dimension with constant value "pos".
1014 struct pet_scop *pet_scop_prefix(struct pet_scop *scop, int pos)
1016 int i;
1018 if (!scop)
1019 return NULL;
1021 for (i = 0; i < scop->n_stmt; ++i) {
1022 scop->stmts[i] = pet_stmt_prefix(scop->stmts[i], pos);
1023 if (!scop->stmts[i])
1024 return pet_scop_free(scop);
1027 return scop;
1030 /* Given a set with a parameter at "param_pos" that refers to the
1031 * iterator, "move" the iterator to the first set dimension.
1032 * That is, essentially equate the parameter to the first set dimension
1033 * and then project it out.
1035 * The first set dimension may however refer to a virtual iterator,
1036 * while the parameter refers to the "real" iterator.
1037 * We therefore need to take into account the affine expression "iv_map", which
1038 * expresses the real iterator in terms of the virtual iterator.
1039 * In particular, we equate the set dimension to the input of the map
1040 * and the parameter to the output of the map and then project out
1041 * everything we don't need anymore.
1043 static __isl_give isl_set *internalize_iv(__isl_take isl_set *set,
1044 int param_pos, __isl_take isl_aff *iv_map)
1046 isl_map *map, *map2;
1047 map = isl_map_from_domain(set);
1048 map = isl_map_add_dims(map, isl_dim_out, 1);
1049 map = isl_map_equate(map, isl_dim_in, 0, isl_dim_out, 0);
1050 map2 = isl_map_from_aff(iv_map);
1051 map2 = isl_map_align_params(map2, isl_map_get_space(map));
1052 map = isl_map_apply_range(map, map2);
1053 map = isl_map_equate(map, isl_dim_param, param_pos, isl_dim_out, 0);
1054 map = isl_map_project_out(map, isl_dim_param, param_pos, 1);
1055 return isl_map_domain(map);
1058 /* Data used in embed_access.
1059 * extend adds an iterator to the iteration domain (through precomposition).
1060 * iv_map expresses the real iterator in terms of the virtual iterator
1061 * var_id represents the induction variable of the corresponding loop
1063 struct pet_embed_access {
1064 isl_multi_pw_aff *extend;
1065 isl_aff *iv_map;
1066 isl_id *var_id;
1069 /* Given an index expression, return an expression for the outer iterator.
1071 static __isl_give isl_aff *index_outer_iterator(
1072 __isl_take isl_multi_pw_aff *index)
1074 isl_space *space;
1075 isl_local_space *ls;
1077 space = isl_multi_pw_aff_get_domain_space(index);
1078 isl_multi_pw_aff_free(index);
1080 ls = isl_local_space_from_space(space);
1081 return isl_aff_var_on_domain(ls, isl_dim_set, 0);
1084 /* Replace an index expression that references the new (outer) iterator variable
1085 * by one that references the corresponding (real) iterator.
1087 * The input index expression is of the form
1089 * { S[i',...] -> i[] }
1091 * where i' refers to the virtual iterator.
1093 * iv_map is of the form
1095 * { [i'] -> [i] }
1097 * Return the index expression
1099 * { S[i',...] -> [i] }
1101 static __isl_give isl_multi_pw_aff *replace_by_iterator(
1102 __isl_take isl_multi_pw_aff *index, __isl_take isl_aff *iv_map)
1104 isl_space *space;
1105 isl_aff *aff;
1107 aff = index_outer_iterator(index);
1108 space = isl_aff_get_space(aff);
1109 iv_map = isl_aff_align_params(iv_map, space);
1110 aff = isl_aff_pullback_aff(iv_map, aff);
1112 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
1115 /* Given an index expression "index" that refers to the (real) iterator
1116 * through the parameter at position "pos", plug in "iv_map", expressing
1117 * the real iterator in terms of the virtual (outer) iterator.
1119 * In particular, the index expression is of the form
1121 * [..., i, ...] -> { S[i',...] -> ... i ... }
1123 * where i refers to the real iterator and i' refers to the virtual iterator.
1125 * iv_map is of the form
1127 * { [i'] -> [i] }
1129 * Return the index expression
1131 * [..., ...] -> { S[i',...] -> ... iv_map(i') ... }
1134 * We first move the parameter to the input
1136 * [..., ...] -> { [i, i',...] -> ... i ... }
1138 * and construct
1140 * { S[i',...] -> [i=iv_map(i'), i', ...] }
1142 * and then combine the two to obtain the desired result.
1144 static __isl_give isl_multi_pw_aff *index_internalize_iv(
1145 __isl_take isl_multi_pw_aff *index, int pos, __isl_take isl_aff *iv_map)
1147 isl_space *space = isl_multi_pw_aff_get_domain_space(index);
1148 isl_multi_aff *ma;
1150 space = isl_space_drop_dims(space, isl_dim_param, pos, 1);
1151 index = isl_multi_pw_aff_move_dims(index, isl_dim_in, 0,
1152 isl_dim_param, pos, 1);
1154 space = isl_space_map_from_set(space);
1155 ma = isl_multi_aff_identity(isl_space_copy(space));
1156 iv_map = isl_aff_align_params(iv_map, space);
1157 iv_map = isl_aff_pullback_aff(iv_map, isl_multi_aff_get_aff(ma, 0));
1158 ma = isl_multi_aff_flat_range_product(
1159 isl_multi_aff_from_aff(iv_map), ma);
1160 index = isl_multi_pw_aff_pullback_multi_aff(index, ma);
1162 return index;
1165 /* Does the index expression "index" reference a virtual array, i.e.,
1166 * one with user pointer equal to NULL?
1167 * A virtual array does not have any members.
1169 static int index_is_virtual_array(__isl_keep isl_multi_pw_aff *index)
1171 isl_id *id;
1172 int is_virtual;
1174 if (!isl_multi_pw_aff_has_tuple_id(index, isl_dim_out))
1175 return 0;
1176 if (isl_multi_pw_aff_range_is_wrapping(index))
1177 return 0;
1178 id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
1179 is_virtual = !isl_id_get_user(id);
1180 isl_id_free(id);
1182 return is_virtual;
1185 /* Does the access relation "access" reference a virtual array, i.e.,
1186 * one with user pointer equal to NULL?
1187 * A virtual array does not have any members.
1189 static int access_is_virtual_array(__isl_keep isl_map *access)
1191 isl_id *id;
1192 int is_virtual;
1194 if (!isl_map_has_tuple_id(access, isl_dim_out))
1195 return 0;
1196 if (isl_map_range_is_wrapping(access))
1197 return 0;
1198 id = isl_map_get_tuple_id(access, isl_dim_out);
1199 is_virtual = !isl_id_get_user(id);
1200 isl_id_free(id);
1202 return is_virtual;
1205 /* Embed the given index expression in an extra outer loop.
1206 * The domain of the index expression has already been updated.
1208 * If the access refers to the induction variable, then it is
1209 * turned into an access to the set of integers with index (and value)
1210 * equal to the induction variable.
1212 * If the accessed array is a virtual array (with user
1213 * pointer equal to NULL), as created by create_test_index,
1214 * then it is extended along with the domain of the index expression.
1216 static __isl_give isl_multi_pw_aff *embed_index_expression(
1217 __isl_take isl_multi_pw_aff *index, struct pet_embed_access *data)
1219 isl_id *array_id = NULL;
1220 int pos;
1222 if (isl_multi_pw_aff_has_tuple_id(index, isl_dim_out))
1223 array_id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
1224 if (array_id == data->var_id) {
1225 index = replace_by_iterator(index, isl_aff_copy(data->iv_map));
1226 } else if (index_is_virtual_array(index)) {
1227 isl_aff *aff;
1228 isl_multi_pw_aff *mpa;
1230 aff = index_outer_iterator(isl_multi_pw_aff_copy(index));
1231 mpa = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
1232 index = isl_multi_pw_aff_flat_range_product(mpa, index);
1233 index = isl_multi_pw_aff_set_tuple_id(index, isl_dim_out,
1234 isl_id_copy(array_id));
1236 isl_id_free(array_id);
1238 pos = isl_multi_pw_aff_find_dim_by_id(index,
1239 isl_dim_param, data->var_id);
1240 if (pos >= 0)
1241 index = index_internalize_iv(index, pos,
1242 isl_aff_copy(data->iv_map));
1243 index = isl_multi_pw_aff_set_dim_id(index, isl_dim_in, 0,
1244 isl_id_copy(data->var_id));
1246 return index;
1249 /* Embed the given access relation in an extra outer loop.
1250 * The domain of the access relation has already been updated.
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_index,
1262 * then it is extended along with the domain of the access.
1264 static __isl_give isl_map *embed_access_relation(__isl_take isl_map *access,
1265 struct pet_embed_access *data)
1267 isl_id *array_id = NULL;
1268 int pos;
1270 if (isl_map_has_tuple_id(access, isl_dim_out))
1271 array_id = isl_map_get_tuple_id(access, isl_dim_out);
1272 if (array_id == data->var_id || access_is_virtual_array(access)) {
1273 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
1274 access = isl_map_equate(access,
1275 isl_dim_in, 0, isl_dim_out, 0);
1276 if (array_id == data->var_id)
1277 access = isl_map_apply_range(access,
1278 isl_map_from_aff(isl_aff_copy(data->iv_map)));
1279 else
1280 access = isl_map_set_tuple_id(access, isl_dim_out,
1281 isl_id_copy(array_id));
1283 isl_id_free(array_id);
1285 pos = isl_map_find_dim_by_id(access, isl_dim_param, data->var_id);
1286 if (pos >= 0) {
1287 isl_set *set = isl_map_wrap(access);
1288 set = internalize_iv(set, pos, isl_aff_copy(data->iv_map));
1289 access = isl_set_unwrap(set);
1291 access = isl_map_set_dim_id(access, isl_dim_in, 0,
1292 isl_id_copy(data->var_id));
1294 return access;
1297 /* Given an access expression, embed the associated access relation and
1298 * index expression in an extra outer loop.
1300 * We first update the domains to insert the extra dimension and
1301 * then update the access relation and index expression to take
1302 * into account the mapping "iv_map" from virtual iterator
1303 * to real iterator.
1305 static __isl_give pet_expr *embed_access(__isl_take pet_expr *expr, void *user)
1307 struct pet_embed_access *data = user;
1309 expr = pet_expr_cow(expr);
1310 expr = pet_expr_access_update_domain(expr, data->extend);
1311 if (!expr)
1312 return NULL;
1314 expr->acc.access = embed_access_relation(expr->acc.access, data);
1315 expr->acc.index = embed_index_expression(expr->acc.index, data);
1316 if (!expr->acc.access || !expr->acc.index)
1317 return pet_expr_free(expr);
1319 return expr;
1322 /* Embed all access subexpressions of "expr" in an extra loop.
1323 * "extend" inserts an outer loop iterator in the iteration domains
1324 * (through precomposition).
1325 * "iv_map" expresses the real iterator in terms of the virtual iterator
1326 * "var_id" represents the induction variable.
1328 static __isl_give pet_expr *expr_embed(__isl_take pet_expr *expr,
1329 __isl_take isl_multi_pw_aff *extend, __isl_take isl_aff *iv_map,
1330 __isl_keep isl_id *var_id)
1332 struct pet_embed_access data =
1333 { .extend = extend, .iv_map = iv_map, .var_id = var_id };
1335 expr = pet_expr_map_access(expr, &embed_access, &data);
1336 isl_aff_free(iv_map);
1337 isl_multi_pw_aff_free(extend);
1338 return expr;
1341 /* Embed the given pet_stmt in an extra outer loop with iteration domain
1342 * "dom" and schedule "sched". "var_id" represents the induction variable
1343 * of the loop. "iv_map" maps a possibly virtual iterator to the real iterator.
1344 * That is, it expresses the iterator that some of the parameters in "stmt"
1345 * may refer to in terms of the iterator used in "dom" and
1346 * the domain of "sched".
1348 * The iteration domain and schedule of the statement are updated
1349 * according to the iteration domain and schedule of the new loop.
1350 * If stmt->domain is a wrapped map, then the iteration domain
1351 * is the domain of this map, so we need to be careful to adjust
1352 * this domain.
1354 * If the induction variable appears in the constraints (as a parameter)
1355 * of the current iteration domain or the schedule of the statement,
1356 * then the parameter is equated to the newly introduced iteration
1357 * domain dimension and subsequently projected out.
1359 * Finally, all access relations are updated based on the extra loop.
1361 static struct pet_stmt *pet_stmt_embed(struct pet_stmt *stmt,
1362 __isl_take isl_set *dom, __isl_take isl_map *sched,
1363 __isl_take isl_aff *iv_map, __isl_take isl_id *var_id)
1365 int i;
1366 int pos;
1367 isl_id *stmt_id;
1368 isl_space *dim;
1369 isl_multi_pw_aff *extend;
1371 if (!stmt)
1372 goto error;
1374 if (isl_set_is_wrapping(stmt->domain)) {
1375 isl_map *map;
1376 isl_map *ext;
1377 isl_space *ran_dim;
1379 map = isl_set_unwrap(stmt->domain);
1380 stmt_id = isl_map_get_tuple_id(map, isl_dim_in);
1381 ran_dim = isl_space_range(isl_map_get_space(map));
1382 ext = isl_map_from_domain_and_range(isl_set_copy(dom),
1383 isl_set_universe(ran_dim));
1384 map = isl_map_flat_domain_product(ext, map);
1385 map = isl_map_set_tuple_id(map, isl_dim_in,
1386 isl_id_copy(stmt_id));
1387 dim = isl_space_domain(isl_map_get_space(map));
1388 stmt->domain = isl_map_wrap(map);
1389 } else {
1390 stmt_id = isl_set_get_tuple_id(stmt->domain);
1391 stmt->domain = isl_set_flat_product(isl_set_copy(dom),
1392 stmt->domain);
1393 stmt->domain = isl_set_set_tuple_id(stmt->domain,
1394 isl_id_copy(stmt_id));
1395 dim = isl_set_get_space(stmt->domain);
1398 pos = isl_set_find_dim_by_id(stmt->domain, isl_dim_param, var_id);
1399 if (pos >= 0)
1400 stmt->domain = internalize_iv(stmt->domain, pos,
1401 isl_aff_copy(iv_map));
1403 stmt->schedule = isl_map_flat_product(sched, stmt->schedule);
1404 stmt->schedule = isl_map_set_tuple_id(stmt->schedule,
1405 isl_dim_in, stmt_id);
1407 pos = isl_map_find_dim_by_id(stmt->schedule, isl_dim_param, var_id);
1408 if (pos >= 0) {
1409 isl_set *set = isl_map_wrap(stmt->schedule);
1410 set = internalize_iv(set, pos, isl_aff_copy(iv_map));
1411 stmt->schedule = isl_set_unwrap(set);
1414 dim = isl_space_map_from_set(dim);
1415 extend = isl_multi_pw_aff_identity(dim);
1416 extend = isl_multi_pw_aff_drop_dims(extend, isl_dim_out, 0, 1);
1417 extend = isl_multi_pw_aff_set_tuple_id(extend, isl_dim_out,
1418 isl_multi_pw_aff_get_tuple_id(extend, isl_dim_in));
1419 for (i = 0; i < stmt->n_arg; ++i)
1420 stmt->args[i] = expr_embed(stmt->args[i],
1421 isl_multi_pw_aff_copy(extend),
1422 isl_aff_copy(iv_map), var_id);
1423 stmt->body = expr_embed(stmt->body, extend, iv_map, var_id);
1425 isl_set_free(dom);
1426 isl_id_free(var_id);
1428 for (i = 0; i < stmt->n_arg; ++i)
1429 if (!stmt->args[i])
1430 return pet_stmt_free(stmt);
1431 if (!stmt->domain || !stmt->schedule || !stmt->body)
1432 return pet_stmt_free(stmt);
1433 return stmt;
1434 error:
1435 isl_set_free(dom);
1436 isl_map_free(sched);
1437 isl_aff_free(iv_map);
1438 isl_id_free(var_id);
1439 return NULL;
1442 /* Embed the given pet_array in an extra outer loop with iteration domain
1443 * "dom".
1444 * This embedding only has an effect on virtual arrays (those with
1445 * user pointer equal to NULL), which need to be extended along with
1446 * the iteration domain.
1448 static struct pet_array *pet_array_embed(struct pet_array *array,
1449 __isl_take isl_set *dom)
1451 isl_id *array_id = NULL;
1453 if (!array)
1454 goto error;
1456 if (isl_set_has_tuple_id(array->extent))
1457 array_id = isl_set_get_tuple_id(array->extent);
1459 if (array_id && !isl_id_get_user(array_id)) {
1460 array->extent = isl_set_flat_product(dom, array->extent);
1461 array->extent = isl_set_set_tuple_id(array->extent, array_id);
1462 if (!array->extent)
1463 return pet_array_free(array);
1464 } else {
1465 isl_set_free(dom);
1466 isl_id_free(array_id);
1469 return array;
1470 error:
1471 isl_set_free(dom);
1472 return NULL;
1475 /* Update the context with respect to an embedding into a loop
1476 * with iteration domain "dom" and induction variable "id".
1477 * "iv_map" expresses the real iterator (parameter "id") in terms
1478 * of a possibly virtual iterator (used in "dom").
1480 * If the current context is independent of "id", we don't need
1481 * to do anything.
1482 * Otherwise, a parameter value is invalid for the embedding if
1483 * any of the corresponding iterator values is invalid.
1484 * That is, a parameter value is valid only if all the corresponding
1485 * iterator values are valid.
1486 * We therefore compute the set of parameters
1488 * forall i in dom : valid (i)
1490 * or
1492 * not exists i in dom : not valid(i)
1494 * i.e.,
1496 * not exists i in dom \ valid(i)
1498 * Before we subtract valid(i) from dom, we first need to substitute
1499 * the real iterator for the virtual iterator.
1501 * If there are any unnamed parameters in "dom", then we consider
1502 * a parameter value to be valid if it is valid for any value of those
1503 * unnamed parameters. They are therefore projected out at the end.
1505 static __isl_give isl_set *context_embed(__isl_take isl_set *context,
1506 __isl_keep isl_set *dom, __isl_keep isl_aff *iv_map,
1507 __isl_keep isl_id *id)
1509 int pos;
1510 isl_multi_aff *ma;
1512 pos = isl_set_find_dim_by_id(context, isl_dim_param, id);
1513 if (pos < 0)
1514 return context;
1516 context = isl_set_from_params(context);
1517 context = isl_set_add_dims(context, isl_dim_set, 1);
1518 context = isl_set_equate(context, isl_dim_param, pos, isl_dim_set, 0);
1519 context = isl_set_project_out(context, isl_dim_param, pos, 1);
1520 ma = isl_multi_aff_from_aff(isl_aff_copy(iv_map));
1521 context = isl_set_preimage_multi_aff(context, ma);
1522 context = isl_set_subtract(isl_set_copy(dom), context);
1523 context = isl_set_params(context);
1524 context = isl_set_complement(context);
1525 context = pet_nested_remove_from_set(context);
1526 return context;
1529 /* Update the implication with respect to an embedding into a loop
1530 * with iteration domain "dom".
1532 * Since embed_access extends virtual arrays along with the domain
1533 * of the access, we need to do the same with domain and range
1534 * of the implication. Since the original implication is only valid
1535 * within a given iteration of the loop, the extended implication
1536 * maps the extra array dimension corresponding to the extra loop
1537 * to itself.
1539 static struct pet_implication *pet_implication_embed(
1540 struct pet_implication *implication, __isl_take isl_set *dom)
1542 isl_id *id;
1543 isl_map *map;
1545 if (!implication)
1546 goto error;
1548 map = isl_set_identity(dom);
1549 id = isl_map_get_tuple_id(implication->extension, isl_dim_in);
1550 map = isl_map_flat_product(map, implication->extension);
1551 map = isl_map_set_tuple_id(map, isl_dim_in, isl_id_copy(id));
1552 map = isl_map_set_tuple_id(map, isl_dim_out, id);
1553 implication->extension = map;
1554 if (!implication->extension)
1555 return pet_implication_free(implication);
1557 return implication;
1558 error:
1559 isl_set_free(dom);
1560 return NULL;
1563 /* Embed all statements and arrays in "scop" in an extra outer loop
1564 * with iteration domain "dom" and schedule "sched".
1565 * "id" represents the induction variable of the loop.
1566 * "iv_map" maps a possibly virtual iterator to the real iterator.
1567 * That is, it expresses the iterator that some of the parameters in "scop"
1568 * may refer to in terms of the iterator used in "dom" and
1569 * the domain of "sched".
1571 * Any skip conditions within the loop have no effect outside of the loop.
1572 * The caller is responsible for making sure skip[pet_skip_later] has been
1573 * taken into account.
1575 struct pet_scop *pet_scop_embed(struct pet_scop *scop, __isl_take isl_set *dom,
1576 __isl_take isl_aff *sched, __isl_take isl_aff *iv_map,
1577 __isl_take isl_id *id)
1579 int i;
1580 isl_map *sched_map;
1582 sched_map = isl_map_from_aff(sched);
1584 if (!scop)
1585 goto error;
1587 pet_scop_reset_skip(scop, pet_skip_now);
1588 pet_scop_reset_skip(scop, pet_skip_later);
1590 scop->context = context_embed(scop->context, dom, iv_map, id);
1591 if (!scop->context)
1592 goto error;
1594 for (i = 0; i < scop->n_stmt; ++i) {
1595 scop->stmts[i] = pet_stmt_embed(scop->stmts[i],
1596 isl_set_copy(dom), isl_map_copy(sched_map),
1597 isl_aff_copy(iv_map), isl_id_copy(id));
1598 if (!scop->stmts[i])
1599 goto error;
1602 for (i = 0; i < scop->n_array; ++i) {
1603 scop->arrays[i] = pet_array_embed(scop->arrays[i],
1604 isl_set_copy(dom));
1605 if (!scop->arrays[i])
1606 goto error;
1609 for (i = 0; i < scop->n_implication; ++i) {
1610 scop->implications[i] =
1611 pet_implication_embed(scop->implications[i],
1612 isl_set_copy(dom));
1613 if (!scop->implications[i])
1614 goto error;
1617 isl_set_free(dom);
1618 isl_map_free(sched_map);
1619 isl_aff_free(iv_map);
1620 isl_id_free(id);
1621 return scop;
1622 error:
1623 isl_set_free(dom);
1624 isl_map_free(sched_map);
1625 isl_aff_free(iv_map);
1626 isl_id_free(id);
1627 return pet_scop_free(scop);
1630 /* Add extra conditions on the parameters to the iteration domain of "stmt".
1632 static struct pet_stmt *stmt_restrict(struct pet_stmt *stmt,
1633 __isl_take isl_set *cond)
1635 if (!stmt)
1636 goto error;
1638 stmt->domain = isl_set_intersect_params(stmt->domain, cond);
1640 return stmt;
1641 error:
1642 isl_set_free(cond);
1643 return pet_stmt_free(stmt);
1646 /* Add extra conditions to scop->skip[type].
1648 * The new skip condition only holds if it held before
1649 * and the condition is true. It does not hold if it did not hold
1650 * before or the condition is false.
1652 * The skip condition is assumed to be an affine expression.
1654 static struct pet_scop *pet_scop_restrict_skip(struct pet_scop *scop,
1655 enum pet_skip type, __isl_keep isl_set *cond)
1657 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1658 isl_pw_aff *skip;
1659 isl_set *dom;
1661 if (!scop)
1662 return NULL;
1663 if (!ext->skip[type])
1664 return scop;
1666 if (!multi_pw_aff_is_affine(ext->skip[type]))
1667 isl_die(isl_multi_pw_aff_get_ctx(ext->skip[type]),
1668 isl_error_internal, "can only restrict affine skips",
1669 return pet_scop_free(scop));
1671 skip = isl_multi_pw_aff_get_pw_aff(ext->skip[type], 0);
1672 dom = isl_pw_aff_domain(isl_pw_aff_copy(skip));
1673 cond = isl_set_copy(cond);
1674 cond = isl_set_from_params(cond);
1675 cond = isl_set_intersect(cond, isl_pw_aff_non_zero_set(skip));
1676 skip = indicator_function(cond, dom);
1677 isl_multi_pw_aff_free(ext->skip[type]);
1678 ext->skip[type] = isl_multi_pw_aff_from_pw_aff(skip);
1679 if (!ext->skip[type])
1680 return pet_scop_free(scop);
1682 return scop;
1685 /* Add extra conditions on the parameters to all iteration domains
1686 * and skip conditions.
1688 * A parameter value is valid for the result if it was valid
1689 * for the original scop and satisfies "cond" or if it does
1690 * not satisfy "cond" as in this case the scop is not executed
1691 * and the original constraints on the parameters are irrelevant.
1693 struct pet_scop *pet_scop_restrict(struct pet_scop *scop,
1694 __isl_take isl_set *cond)
1696 int i;
1698 scop = pet_scop_restrict_skip(scop, pet_skip_now, cond);
1699 scop = pet_scop_restrict_skip(scop, pet_skip_later, cond);
1701 if (!scop)
1702 goto error;
1704 scop->context = isl_set_intersect(scop->context, isl_set_copy(cond));
1705 scop->context = isl_set_union(scop->context,
1706 isl_set_complement(isl_set_copy(cond)));
1707 scop->context = isl_set_coalesce(scop->context);
1708 scop->context = pet_nested_remove_from_set(scop->context);
1709 if (!scop->context)
1710 goto error;
1712 for (i = 0; i < scop->n_stmt; ++i) {
1713 scop->stmts[i] = stmt_restrict(scop->stmts[i],
1714 isl_set_copy(cond));
1715 if (!scop->stmts[i])
1716 goto error;
1719 isl_set_free(cond);
1720 return scop;
1721 error:
1722 isl_set_free(cond);
1723 return pet_scop_free(scop);
1726 /* Insert an argument expression corresponding to "test" in front
1727 * of the list of arguments described by *n_arg and *args.
1729 static int args_insert_access(unsigned *n_arg, pet_expr ***args,
1730 __isl_keep isl_multi_pw_aff *test)
1732 int i;
1733 isl_ctx *ctx = isl_multi_pw_aff_get_ctx(test);
1735 if (!test)
1736 return -1;
1738 if (!*args) {
1739 *args = isl_calloc_array(ctx, pet_expr *, 1);
1740 if (!*args)
1741 return -1;
1742 } else {
1743 pet_expr **ext;
1744 ext = isl_calloc_array(ctx, pet_expr *, 1 + *n_arg);
1745 if (!ext)
1746 return -1;
1747 for (i = 0; i < *n_arg; ++i)
1748 ext[1 + i] = (*args)[i];
1749 free(*args);
1750 *args = ext;
1752 (*n_arg)++;
1753 (*args)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test));
1754 if (!(*args)[0])
1755 return -1;
1757 return 0;
1760 /* Look through the applications in "scop" for any that can be
1761 * applied to the filter expressed by "map" and "satisified".
1762 * If there is any, then apply it to "map" and return the result.
1763 * Otherwise, return "map".
1764 * "id" is the identifier of the virtual array.
1766 * We only introduce at most one implication for any given virtual array,
1767 * so we can apply the implication and return as soon as we find one.
1769 static __isl_give isl_map *apply_implications(struct pet_scop *scop,
1770 __isl_take isl_map *map, __isl_keep isl_id *id, int satisfied)
1772 int i;
1774 for (i = 0; i < scop->n_implication; ++i) {
1775 struct pet_implication *pi = scop->implications[i];
1776 isl_id *pi_id;
1778 if (pi->satisfied != satisfied)
1779 continue;
1780 pi_id = isl_map_get_tuple_id(pi->extension, isl_dim_in);
1781 isl_id_free(pi_id);
1782 if (pi_id != id)
1783 continue;
1785 return isl_map_apply_range(map, isl_map_copy(pi->extension));
1788 return map;
1791 /* Is the filter expressed by "test" and "satisfied" implied
1792 * by filter "pos" on "domain", with filter "expr", taking into
1793 * account the implications of "scop"?
1795 * For filter on domain implying that expressed by "test" and "satisfied",
1796 * the filter needs to be an access to the same (virtual) array as "test" and
1797 * the filter value needs to be equal to "satisfied".
1798 * Moreover, the filter access relation, possibly extended by
1799 * the implications in "scop" needs to contain "test".
1801 static int implies_filter(struct pet_scop *scop,
1802 __isl_keep isl_map *domain, int pos, __isl_keep pet_expr *expr,
1803 __isl_keep isl_map *test, int satisfied)
1805 isl_id *test_id, *arg_id;
1806 isl_val *val;
1807 int is_int;
1808 int s;
1809 int is_subset;
1810 isl_map *implied;
1812 if (expr->type != pet_expr_access)
1813 return 0;
1814 test_id = isl_map_get_tuple_id(test, isl_dim_out);
1815 arg_id = pet_expr_access_get_id(expr);
1816 isl_id_free(arg_id);
1817 isl_id_free(test_id);
1818 if (test_id != arg_id)
1819 return 0;
1820 val = isl_map_plain_get_val_if_fixed(domain, isl_dim_out, pos);
1821 is_int = isl_val_is_int(val);
1822 if (is_int)
1823 s = isl_val_get_num_si(val);
1824 isl_val_free(val);
1825 if (!val)
1826 return -1;
1827 if (!is_int)
1828 return 0;
1829 if (s != satisfied)
1830 return 0;
1832 implied = isl_map_copy(expr->acc.access);
1833 implied = apply_implications(scop, implied, test_id, satisfied);
1834 is_subset = isl_map_is_subset(test, implied);
1835 isl_map_free(implied);
1837 return is_subset;
1840 /* Is the filter expressed by "test" and "satisfied" implied
1841 * by any of the filters on the domain of "stmt", taking into
1842 * account the implications of "scop"?
1844 static int filter_implied(struct pet_scop *scop,
1845 struct pet_stmt *stmt, __isl_keep isl_multi_pw_aff *test, int satisfied)
1847 int i;
1848 int implied;
1849 isl_id *test_id;
1850 isl_map *domain;
1851 isl_map *test_map;
1853 if (!scop || !stmt || !test)
1854 return -1;
1855 if (scop->n_implication == 0)
1856 return 0;
1857 if (stmt->n_arg == 0)
1858 return 0;
1860 domain = isl_set_unwrap(isl_set_copy(stmt->domain));
1861 test_map = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test));
1863 implied = 0;
1864 for (i = 0; i < stmt->n_arg; ++i) {
1865 implied = implies_filter(scop, domain, i, stmt->args[i],
1866 test_map, satisfied);
1867 if (implied < 0 || implied)
1868 break;
1871 isl_map_free(test_map);
1872 isl_map_free(domain);
1873 return implied;
1876 /* Make the statement "stmt" depend on the value of "test"
1877 * being equal to "satisfied" by adjusting stmt->domain.
1879 * The domain of "test" corresponds to the (zero or more) outer dimensions
1880 * of the iteration domain.
1882 * We first extend "test" to apply to the entire iteration domain and
1883 * then check if the filter that we are about to add is implied
1884 * by any of the current filters, possibly taking into account
1885 * the implications in "scop". If so, we leave "stmt" untouched and return.
1887 * Otherwise, we insert an argument corresponding to a read to "test"
1888 * from the iteration domain of "stmt" in front of the list of arguments.
1889 * We also insert a corresponding output dimension in the wrapped
1890 * map contained in stmt->domain, with value set to "satisfied".
1892 static struct pet_stmt *stmt_filter(struct pet_scop *scop,
1893 struct pet_stmt *stmt, __isl_take isl_multi_pw_aff *test, int satisfied)
1895 int i;
1896 int implied;
1897 isl_id *id;
1898 isl_ctx *ctx;
1899 isl_pw_multi_aff *pma;
1900 isl_multi_aff *add_dom;
1901 isl_space *space;
1902 isl_local_space *ls;
1903 int n_test_dom;
1905 if (!stmt || !test)
1906 goto error;
1908 space = pet_stmt_get_space(stmt);
1909 n_test_dom = isl_multi_pw_aff_dim(test, isl_dim_in);
1910 space = isl_space_from_domain(space);
1911 space = isl_space_add_dims(space, isl_dim_out, n_test_dom);
1912 add_dom = isl_multi_aff_zero(isl_space_copy(space));
1913 ls = isl_local_space_from_space(isl_space_domain(space));
1914 for (i = 0; i < n_test_dom; ++i) {
1915 isl_aff *aff;
1916 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
1917 isl_dim_set, i);
1918 add_dom = isl_multi_aff_set_aff(add_dom, i, aff);
1920 isl_local_space_free(ls);
1921 test = isl_multi_pw_aff_pullback_multi_aff(test, add_dom);
1923 implied = filter_implied(scop, stmt, test, satisfied);
1924 if (implied < 0)
1925 goto error;
1926 if (implied) {
1927 isl_multi_pw_aff_free(test);
1928 return stmt;
1931 id = isl_multi_pw_aff_get_tuple_id(test, isl_dim_out);
1932 pma = pet_filter_insert_pma(isl_set_get_space(stmt->domain),
1933 id, satisfied);
1934 stmt->domain = isl_set_preimage_pw_multi_aff(stmt->domain, pma);
1936 if (args_insert_access(&stmt->n_arg, &stmt->args, test) < 0)
1937 goto error;
1939 isl_multi_pw_aff_free(test);
1940 return stmt;
1941 error:
1942 isl_multi_pw_aff_free(test);
1943 return pet_stmt_free(stmt);
1946 /* Does "scop" have a skip condition of the given "type"?
1948 int pet_scop_has_skip(struct pet_scop *scop, enum pet_skip type)
1950 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1952 if (!scop)
1953 return -1;
1954 return ext->skip[type] != NULL;
1957 /* Does "scop" have a skip condition of the given "type" that
1958 * is an affine expression?
1960 int pet_scop_has_affine_skip(struct pet_scop *scop, enum pet_skip type)
1962 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1964 if (!scop)
1965 return -1;
1966 if (!ext->skip[type])
1967 return 0;
1968 return multi_pw_aff_is_affine(ext->skip[type]);
1971 /* Does "scop" have a skip condition of the given "type" that
1972 * is not an affine expression?
1974 int pet_scop_has_var_skip(struct pet_scop *scop, enum pet_skip type)
1976 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1977 int aff;
1979 if (!scop)
1980 return -1;
1981 if (!ext->skip[type])
1982 return 0;
1983 aff = multi_pw_aff_is_affine(ext->skip[type]);
1984 if (aff < 0)
1985 return -1;
1986 return !aff;
1989 /* Does "scop" have a skip condition of the given "type" that
1990 * is affine and holds on the entire domain?
1992 int pet_scop_has_universal_skip(struct pet_scop *scop, enum pet_skip type)
1994 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1995 isl_pw_aff *pa;
1996 isl_set *set;
1997 int is_aff;
1998 int is_univ;
2000 is_aff = pet_scop_has_affine_skip(scop, type);
2001 if (is_aff < 0 || !is_aff)
2002 return is_aff;
2004 pa = isl_multi_pw_aff_get_pw_aff(ext->skip[type], 0);
2005 set = isl_pw_aff_non_zero_set(pa);
2006 is_univ = isl_set_plain_is_universe(set);
2007 isl_set_free(set);
2009 return is_univ;
2012 /* Replace scop->skip[type] by "skip".
2014 struct pet_scop *pet_scop_set_skip(struct pet_scop *scop,
2015 enum pet_skip type, __isl_take isl_multi_pw_aff *skip)
2017 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2019 if (!scop || !skip)
2020 goto error;
2022 isl_multi_pw_aff_free(ext->skip[type]);
2023 ext->skip[type] = skip;
2025 return scop;
2026 error:
2027 isl_multi_pw_aff_free(skip);
2028 return pet_scop_free(scop);
2031 /* Return a copy of scop->skip[type].
2033 __isl_give isl_multi_pw_aff *pet_scop_get_skip(struct pet_scop *scop,
2034 enum pet_skip type)
2036 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2038 if (!scop)
2039 return NULL;
2041 return isl_multi_pw_aff_copy(ext->skip[type]);
2044 /* Assuming scop->skip[type] is an affine expression,
2045 * return the constraints on the parameters for which the skip condition
2046 * holds.
2048 __isl_give isl_set *pet_scop_get_affine_skip_domain(struct pet_scop *scop,
2049 enum pet_skip type)
2051 isl_multi_pw_aff *skip;
2052 isl_pw_aff *pa;
2054 skip = pet_scop_get_skip(scop, type);
2055 pa = isl_multi_pw_aff_get_pw_aff(skip, 0);
2056 isl_multi_pw_aff_free(skip);
2057 return isl_set_params(isl_pw_aff_non_zero_set(pa));
2060 /* Return the identifier of the variable that is accessed by
2061 * the skip condition of the given type.
2063 * The skip condition is assumed not to be an affine condition.
2065 __isl_give isl_id *pet_scop_get_skip_id(struct pet_scop *scop,
2066 enum pet_skip type)
2068 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2070 if (!scop)
2071 return NULL;
2073 return isl_multi_pw_aff_get_tuple_id(ext->skip[type], isl_dim_out);
2076 /* Return an access pet_expr corresponding to the skip condition
2077 * of the given type.
2079 __isl_give pet_expr *pet_scop_get_skip_expr(struct pet_scop *scop,
2080 enum pet_skip type)
2082 return pet_expr_from_index(pet_scop_get_skip(scop, type));
2085 /* Drop the the skip condition scop->skip[type].
2087 void pet_scop_reset_skip(struct pet_scop *scop, enum pet_skip type)
2089 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2091 if (!scop)
2092 return;
2094 isl_multi_pw_aff_free(ext->skip[type]);
2095 ext->skip[type] = NULL;
2098 /* Make the skip condition (if any) depend on the value of "test" being
2099 * equal to "satisfied".
2101 * We only support the case where the original skip condition is universal,
2102 * i.e., where skipping is unconditional, and where satisfied == 1.
2103 * In this case, the skip condition is changed to skip only when
2104 * "test" is equal to one.
2106 static struct pet_scop *pet_scop_filter_skip(struct pet_scop *scop,
2107 enum pet_skip type, __isl_keep isl_multi_pw_aff *test, int satisfied)
2109 int is_univ = 0;
2111 if (!scop)
2112 return NULL;
2113 if (!pet_scop_has_skip(scop, type))
2114 return scop;
2116 if (satisfied)
2117 is_univ = pet_scop_has_universal_skip(scop, type);
2118 if (is_univ < 0)
2119 return pet_scop_free(scop);
2120 if (satisfied && is_univ) {
2121 isl_multi_pw_aff *skip;
2122 skip = isl_multi_pw_aff_copy(test);
2123 scop = pet_scop_set_skip(scop, type, skip);
2124 if (!scop)
2125 return NULL;
2126 } else {
2127 isl_die(isl_multi_pw_aff_get_ctx(test), isl_error_internal,
2128 "skip expression cannot be filtered",
2129 return pet_scop_free(scop));
2132 return scop;
2135 /* Make all statements in "scop" depend on the value of "test"
2136 * being equal to "satisfied" by adjusting their domains.
2138 struct pet_scop *pet_scop_filter(struct pet_scop *scop,
2139 __isl_take isl_multi_pw_aff *test, int satisfied)
2141 int i;
2143 scop = pet_scop_filter_skip(scop, pet_skip_now, test, satisfied);
2144 scop = pet_scop_filter_skip(scop, pet_skip_later, test, satisfied);
2146 if (!scop || !test)
2147 goto error;
2149 for (i = 0; i < scop->n_stmt; ++i) {
2150 scop->stmts[i] = stmt_filter(scop, scop->stmts[i],
2151 isl_multi_pw_aff_copy(test), satisfied);
2152 if (!scop->stmts[i])
2153 goto error;
2156 isl_multi_pw_aff_free(test);
2157 return scop;
2158 error:
2159 isl_multi_pw_aff_free(test);
2160 return pet_scop_free(scop);
2163 /* Add all parameters in "expr" to "space" and return the result.
2165 static __isl_give isl_space *expr_collect_params(__isl_keep pet_expr *expr,
2166 __isl_take isl_space *space)
2168 int i;
2170 if (!expr)
2171 goto error;
2172 for (i = 0; i < expr->n_arg; ++i)
2173 space = expr_collect_params(expr->args[i], space);
2175 if (expr->type == pet_expr_access)
2176 space = isl_space_align_params(space,
2177 isl_map_get_space(expr->acc.access));
2179 return space;
2180 error:
2181 pet_expr_free(expr);
2182 return isl_space_free(space);
2185 /* Add all parameters in "stmt" to "space" and return the result.
2187 static __isl_give isl_space *stmt_collect_params(struct pet_stmt *stmt,
2188 __isl_take isl_space *space)
2190 int i;
2192 if (!stmt)
2193 return isl_space_free(space);
2195 space = isl_space_align_params(space, isl_set_get_space(stmt->domain));
2196 space = isl_space_align_params(space,
2197 isl_map_get_space(stmt->schedule));
2198 for (i = 0; i < stmt->n_arg; ++i)
2199 space = expr_collect_params(stmt->args[i], space);
2200 space = expr_collect_params(stmt->body, space);
2202 return space;
2205 /* Add all parameters in "array" to "space" and return the result.
2207 static __isl_give isl_space *array_collect_params(struct pet_array *array,
2208 __isl_take isl_space *space)
2210 if (!array)
2211 return isl_space_free(space);
2213 space = isl_space_align_params(space,
2214 isl_set_get_space(array->context));
2215 space = isl_space_align_params(space, isl_set_get_space(array->extent));
2217 return space;
2220 /* Add all parameters in "scop" to "space" and return the result.
2222 static __isl_give isl_space *scop_collect_params(struct pet_scop *scop,
2223 __isl_take isl_space *space)
2225 int i;
2227 if (!scop)
2228 return isl_space_free(space);
2230 for (i = 0; i < scop->n_array; ++i)
2231 space = array_collect_params(scop->arrays[i], space);
2233 for (i = 0; i < scop->n_stmt; ++i)
2234 space = stmt_collect_params(scop->stmts[i], space);
2236 return space;
2239 /* Add all parameters in "space" to the domain, schedule and
2240 * all access relations in "stmt".
2242 static struct pet_stmt *stmt_propagate_params(struct pet_stmt *stmt,
2243 __isl_take isl_space *space)
2245 int i;
2247 if (!stmt)
2248 goto error;
2250 stmt->domain = isl_set_align_params(stmt->domain,
2251 isl_space_copy(space));
2252 stmt->schedule = isl_map_align_params(stmt->schedule,
2253 isl_space_copy(space));
2255 for (i = 0; i < stmt->n_arg; ++i) {
2256 stmt->args[i] = pet_expr_align_params(stmt->args[i],
2257 isl_space_copy(space));
2258 if (!stmt->args[i])
2259 goto error;
2261 stmt->body = pet_expr_align_params(stmt->body, isl_space_copy(space));
2263 if (!stmt->domain || !stmt->schedule || !stmt->body)
2264 goto error;
2266 isl_space_free(space);
2267 return stmt;
2268 error:
2269 isl_space_free(space);
2270 return pet_stmt_free(stmt);
2273 /* Add all parameters in "space" to "array".
2275 static struct pet_array *array_propagate_params(struct pet_array *array,
2276 __isl_take isl_space *space)
2278 if (!array)
2279 goto error;
2281 array->context = isl_set_align_params(array->context,
2282 isl_space_copy(space));
2283 array->extent = isl_set_align_params(array->extent,
2284 isl_space_copy(space));
2285 if (array->value_bounds) {
2286 array->value_bounds = isl_set_align_params(array->value_bounds,
2287 isl_space_copy(space));
2288 if (!array->value_bounds)
2289 goto error;
2292 if (!array->context || !array->extent)
2293 goto error;
2295 isl_space_free(space);
2296 return array;
2297 error:
2298 isl_space_free(space);
2299 return pet_array_free(array);
2302 /* Add all parameters in "space" to "scop".
2304 static struct pet_scop *scop_propagate_params(struct pet_scop *scop,
2305 __isl_take isl_space *space)
2307 int i;
2309 if (!scop)
2310 goto error;
2312 for (i = 0; i < scop->n_array; ++i) {
2313 scop->arrays[i] = array_propagate_params(scop->arrays[i],
2314 isl_space_copy(space));
2315 if (!scop->arrays[i])
2316 goto error;
2319 for (i = 0; i < scop->n_stmt; ++i) {
2320 scop->stmts[i] = stmt_propagate_params(scop->stmts[i],
2321 isl_space_copy(space));
2322 if (!scop->stmts[i])
2323 goto error;
2326 isl_space_free(space);
2327 return scop;
2328 error:
2329 isl_space_free(space);
2330 return pet_scop_free(scop);
2333 /* Update all isl_sets and isl_maps in "scop" such that they all
2334 * have the same parameters.
2336 struct pet_scop *pet_scop_align_params(struct pet_scop *scop)
2338 isl_space *space;
2340 if (!scop)
2341 return NULL;
2343 space = isl_set_get_space(scop->context);
2344 space = scop_collect_params(scop, space);
2346 scop->context = isl_set_align_params(scop->context,
2347 isl_space_copy(space));
2348 scop = scop_propagate_params(scop, space);
2350 if (scop && !scop->context)
2351 return pet_scop_free(scop);
2353 return scop;
2356 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2357 * in "space" by a value equal to the corresponding parameter.
2359 static struct pet_stmt *stmt_detect_parameter_accesses(struct pet_stmt *stmt,
2360 __isl_take isl_space *space)
2362 if (!stmt)
2363 goto error;
2365 stmt->body = pet_expr_detect_parameter_accesses(stmt->body,
2366 isl_space_copy(space));
2368 if (!stmt->domain || !stmt->schedule || !stmt->body)
2369 goto error;
2371 isl_space_free(space);
2372 return stmt;
2373 error:
2374 isl_space_free(space);
2375 return pet_stmt_free(stmt);
2378 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
2379 * in "space" by a value equal to the corresponding parameter.
2381 static struct pet_scop *scop_detect_parameter_accesses(struct pet_scop *scop,
2382 __isl_take isl_space *space)
2384 int i;
2386 if (!scop)
2387 goto error;
2389 for (i = 0; i < scop->n_stmt; ++i) {
2390 scop->stmts[i] = stmt_detect_parameter_accesses(scop->stmts[i],
2391 isl_space_copy(space));
2392 if (!scop->stmts[i])
2393 goto error;
2396 isl_space_free(space);
2397 return scop;
2398 error:
2399 isl_space_free(space);
2400 return pet_scop_free(scop);
2403 /* Replace all accesses to (0D) arrays that correspond to any of
2404 * the parameters used in "scop" by a value equal
2405 * to the corresponding parameter.
2407 struct pet_scop *pet_scop_detect_parameter_accesses(struct pet_scop *scop)
2409 isl_space *space;
2411 if (!scop)
2412 return NULL;
2414 space = isl_set_get_space(scop->context);
2415 space = scop_collect_params(scop, space);
2417 scop = scop_detect_parameter_accesses(scop, space);
2419 return scop;
2422 /* Add the access relation of the access expression "expr" to "accesses" and
2423 * return the result.
2424 * The domain of the access relation is intersected with "domain".
2425 * If "tag" is set, then the access relation is tagged with
2426 * the corresponding reference identifier.
2428 static __isl_give isl_union_map *expr_collect_access(__isl_keep pet_expr *expr,
2429 int tag, __isl_take isl_union_map *accesses, __isl_keep isl_set *domain)
2431 isl_map *access;
2433 access = pet_expr_access_get_may_access(expr);
2434 access = isl_map_intersect_domain(access, isl_set_copy(domain));
2435 if (tag)
2436 access = pet_expr_tag_access(expr, access);
2437 return isl_union_map_add_map(accesses, access);
2440 /* Add all read access relations (if "read" is set) and/or all write
2441 * access relations (if "write" is set) to "accesses" and return the result.
2442 * The domains of the access relations are intersected with "domain".
2443 * If "tag" is set, then the access relations are tagged with
2444 * the corresponding reference identifiers.
2446 * If "must" is set, then we only add the accesses that are definitely
2447 * performed. Otherwise, we add all potential accesses.
2448 * In particular, if the access has any arguments, then if "must" is
2449 * set we currently skip the access completely. If "must" is not set,
2450 * we project out the values of the access arguments.
2452 static __isl_give isl_union_map *expr_collect_accesses(
2453 __isl_keep pet_expr *expr, int read, int write, int must, int tag,
2454 __isl_take isl_union_map *accesses, __isl_keep isl_set *domain)
2456 int i;
2457 isl_id *id;
2458 isl_space *dim;
2460 if (!expr)
2461 return isl_union_map_free(accesses);
2463 for (i = 0; i < expr->n_arg; ++i)
2464 accesses = expr_collect_accesses(expr->args[i],
2465 read, write, must, tag, accesses, domain);
2467 if (expr->type == pet_expr_access && !pet_expr_is_affine(expr) &&
2468 ((read && expr->acc.read) || (write && expr->acc.write)) &&
2469 (!must || expr->n_arg == 0)) {
2470 accesses = expr_collect_access(expr, tag, accesses, domain);
2473 return accesses;
2476 /* Collect and return all read access relations (if "read" is set)
2477 * and/or all write access relations (if "write" is set) in "stmt".
2478 * If "tag" is set, then the access relations are tagged with
2479 * the corresponding reference identifiers.
2480 * If "kill" is set, then "stmt" is a kill statement and we simply
2481 * add the argument of the kill operation.
2483 * If "must" is set, then we only add the accesses that are definitely
2484 * performed. Otherwise, we add all potential accesses.
2485 * In particular, if the statement has any arguments, then if "must" is
2486 * set we currently skip the statement completely. If "must" is not set,
2487 * we project out the values of the statement arguments.
2489 static __isl_give isl_union_map *stmt_collect_accesses(struct pet_stmt *stmt,
2490 int read, int write, int kill, int must, int tag,
2491 __isl_take isl_space *dim)
2493 isl_union_map *accesses;
2494 isl_set *domain;
2496 if (!stmt)
2497 return NULL;
2499 accesses = isl_union_map_empty(dim);
2501 if (must && stmt->n_arg > 0)
2502 return accesses;
2504 domain = isl_set_copy(stmt->domain);
2505 if (isl_set_is_wrapping(domain))
2506 domain = isl_map_domain(isl_set_unwrap(domain));
2508 if (kill)
2509 accesses = expr_collect_access(stmt->body->args[0], tag,
2510 accesses, domain);
2511 else
2512 accesses = expr_collect_accesses(stmt->body, read, write,
2513 must, tag, accesses, domain);
2514 isl_set_free(domain);
2516 return accesses;
2519 /* Is "stmt" an assignment statement?
2521 int pet_stmt_is_assign(struct pet_stmt *stmt)
2523 if (!stmt)
2524 return 0;
2525 if (stmt->body->type != pet_expr_op)
2526 return 0;
2527 return stmt->body->op == pet_op_assign;
2530 /* Is "stmt" a kill statement?
2532 int pet_stmt_is_kill(struct pet_stmt *stmt)
2534 if (!stmt)
2535 return 0;
2536 if (stmt->body->type != pet_expr_op)
2537 return 0;
2538 return stmt->body->op == pet_op_kill;
2541 /* Is "stmt" an assume statement?
2543 int pet_stmt_is_assume(struct pet_stmt *stmt)
2545 if (stmt->body->type != pet_expr_op)
2546 return 0;
2547 return stmt->body->op == pet_op_assume;
2550 /* Compute a mapping from all arrays (of structs) in scop
2551 * to their innermost arrays.
2553 * In particular, for each array of a primitive type, the result
2554 * contains the identity mapping on that array.
2555 * For each array involving member accesses, the result
2556 * contains a mapping from the elements of any intermediate array of structs
2557 * to all corresponding elements of the innermost nested arrays.
2559 static __isl_give isl_union_map *compute_to_inner(struct pet_scop *scop)
2561 int i;
2562 isl_union_map *to_inner;
2564 to_inner = isl_union_map_empty(isl_set_get_space(scop->context));
2566 for (i = 0; i < scop->n_array; ++i) {
2567 struct pet_array *array = scop->arrays[i];
2568 isl_set *set;
2569 isl_map *map, *gist;
2571 if (array->element_is_record)
2572 continue;
2574 map = isl_set_identity(isl_set_copy(array->extent));
2576 set = isl_map_domain(isl_map_copy(map));
2577 gist = isl_map_copy(map);
2578 gist = isl_map_gist_domain(gist, isl_set_copy(set));
2579 to_inner = isl_union_map_add_map(to_inner, gist);
2581 while (set && isl_set_is_wrapping(set)) {
2582 isl_id *id;
2583 isl_map *wrapped;
2585 id = isl_set_get_tuple_id(set);
2586 wrapped = isl_set_unwrap(set);
2587 wrapped = isl_map_domain_map(wrapped);
2588 wrapped = isl_map_set_tuple_id(wrapped, isl_dim_in, id);
2589 map = isl_map_apply_domain(map, wrapped);
2590 set = isl_map_domain(isl_map_copy(map));
2591 gist = isl_map_copy(map);
2592 gist = isl_map_gist_domain(gist, isl_set_copy(set));
2593 to_inner = isl_union_map_add_map(to_inner, gist);
2596 isl_set_free(set);
2597 isl_map_free(map);
2600 return to_inner;
2603 /* Collect and return all read access relations (if "read" is set)
2604 * and/or all write access relations (if "write" is set) in "scop".
2605 * If "kill" is set, then we only add the arguments of kill operations.
2606 * If "must" is set, then we only add the accesses that are definitely
2607 * performed. Otherwise, we add all potential accesses.
2608 * If "tag" is set, then the access relations are tagged with
2609 * the corresponding reference identifiers.
2610 * For accesses to structures, the returned access relation accesses
2611 * all individual fields in the structures.
2613 static __isl_give isl_union_map *scop_collect_accesses(struct pet_scop *scop,
2614 int read, int write, int kill, int must, int tag)
2616 int i;
2617 isl_union_map *accesses;
2618 isl_union_set *arrays;
2619 isl_union_map *to_inner;
2621 if (!scop)
2622 return NULL;
2624 accesses = isl_union_map_empty(isl_set_get_space(scop->context));
2626 for (i = 0; i < scop->n_stmt; ++i) {
2627 struct pet_stmt *stmt = scop->stmts[i];
2628 isl_union_map *accesses_i;
2629 isl_space *space;
2631 if (kill && !pet_stmt_is_kill(stmt))
2632 continue;
2634 space = isl_set_get_space(scop->context);
2635 accesses_i = stmt_collect_accesses(stmt, read, write, kill,
2636 must, tag, space);
2637 accesses = isl_union_map_union(accesses, accesses_i);
2640 arrays = isl_union_set_empty(isl_union_map_get_space(accesses));
2641 for (i = 0; i < scop->n_array; ++i) {
2642 isl_set *extent = isl_set_copy(scop->arrays[i]->extent);
2643 arrays = isl_union_set_add_set(arrays, extent);
2645 accesses = isl_union_map_intersect_range(accesses, arrays);
2647 to_inner = compute_to_inner(scop);
2648 accesses = isl_union_map_apply_range(accesses, to_inner);
2650 return accesses;
2653 /* Collect all potential read access relations.
2655 __isl_give isl_union_map *pet_scop_collect_may_reads(struct pet_scop *scop)
2657 return scop_collect_accesses(scop, 1, 0, 0, 0, 0);
2660 /* Collect all potential write access relations.
2662 __isl_give isl_union_map *pet_scop_collect_may_writes(struct pet_scop *scop)
2664 return scop_collect_accesses(scop, 0, 1, 0, 0, 0);
2667 /* Collect all definite write access relations.
2669 __isl_give isl_union_map *pet_scop_collect_must_writes(struct pet_scop *scop)
2671 return scop_collect_accesses(scop, 0, 1, 0, 1, 0);
2674 /* Collect all definite kill access relations.
2676 __isl_give isl_union_map *pet_scop_collect_must_kills(struct pet_scop *scop)
2678 return scop_collect_accesses(scop, 0, 0, 1, 1, 0);
2681 /* Collect all tagged potential read access relations.
2683 __isl_give isl_union_map *pet_scop_collect_tagged_may_reads(
2684 struct pet_scop *scop)
2686 return scop_collect_accesses(scop, 1, 0, 0, 0, 1);
2689 /* Collect all tagged potential write access relations.
2691 __isl_give isl_union_map *pet_scop_collect_tagged_may_writes(
2692 struct pet_scop *scop)
2694 return scop_collect_accesses(scop, 0, 1, 0, 0, 1);
2697 /* Collect all tagged definite write access relations.
2699 __isl_give isl_union_map *pet_scop_collect_tagged_must_writes(
2700 struct pet_scop *scop)
2702 return scop_collect_accesses(scop, 0, 1, 0, 1, 1);
2705 /* Collect all tagged definite kill access relations.
2707 __isl_give isl_union_map *pet_scop_collect_tagged_must_kills(
2708 struct pet_scop *scop)
2710 return scop_collect_accesses(scop, 0, 0, 1, 1, 1);
2713 /* Collect and return the union of iteration domains in "scop".
2715 __isl_give isl_union_set *pet_scop_collect_domains(struct pet_scop *scop)
2717 int i;
2718 isl_set *domain_i;
2719 isl_union_set *domain;
2721 if (!scop)
2722 return NULL;
2724 domain = isl_union_set_empty(isl_set_get_space(scop->context));
2726 for (i = 0; i < scop->n_stmt; ++i) {
2727 domain_i = isl_set_copy(scop->stmts[i]->domain);
2728 domain = isl_union_set_add_set(domain, domain_i);
2731 return domain;
2734 /* Collect and return the schedules of the statements in "scop".
2735 * The range is normalized to the maximal number of scheduling
2736 * dimensions.
2738 __isl_give isl_union_map *pet_scop_collect_schedule(struct pet_scop *scop)
2740 int i, j;
2741 isl_map *schedule_i;
2742 isl_union_map *schedule;
2743 int depth, max_depth = 0;
2745 if (!scop)
2746 return NULL;
2748 schedule = isl_union_map_empty(isl_set_get_space(scop->context));
2750 for (i = 0; i < scop->n_stmt; ++i) {
2751 depth = isl_map_dim(scop->stmts[i]->schedule, isl_dim_out);
2752 if (depth > max_depth)
2753 max_depth = depth;
2756 for (i = 0; i < scop->n_stmt; ++i) {
2757 schedule_i = isl_map_copy(scop->stmts[i]->schedule);
2758 depth = isl_map_dim(schedule_i, isl_dim_out);
2759 schedule_i = isl_map_add_dims(schedule_i, isl_dim_out,
2760 max_depth - depth);
2761 for (j = depth; j < max_depth; ++j)
2762 schedule_i = isl_map_fix_si(schedule_i,
2763 isl_dim_out, j, 0);
2764 schedule = isl_union_map_add_map(schedule, schedule_i);
2767 return schedule;
2770 /* Does statement "stmt" write to "id"?
2772 static int stmt_writes(struct pet_stmt *stmt, __isl_keep isl_id *id)
2774 return pet_expr_writes(stmt->body, id);
2777 /* Is there any write access in "scop" that accesses "id"?
2779 int pet_scop_writes(struct pet_scop *scop, __isl_keep isl_id *id)
2781 int i;
2783 if (!scop)
2784 return -1;
2786 for (i = 0; i < scop->n_stmt; ++i) {
2787 int writes = stmt_writes(scop->stmts[i], id);
2788 if (writes < 0 || writes)
2789 return writes;
2792 return 0;
2795 /* Add a reference identifier to all access expressions in "stmt".
2796 * "n_ref" points to an integer that contains the sequence number
2797 * of the next reference.
2799 static struct pet_stmt *stmt_add_ref_ids(struct pet_stmt *stmt, int *n_ref)
2801 int i;
2803 if (!stmt)
2804 return NULL;
2806 for (i = 0; i < stmt->n_arg; ++i) {
2807 stmt->args[i] = pet_expr_add_ref_ids(stmt->args[i], n_ref);
2808 if (!stmt->args[i])
2809 return pet_stmt_free(stmt);
2812 stmt->body = pet_expr_add_ref_ids(stmt->body, n_ref);
2813 if (!stmt->body)
2814 return pet_stmt_free(stmt);
2816 return stmt;
2819 /* Add a reference identifier to all access expressions in "scop".
2821 struct pet_scop *pet_scop_add_ref_ids(struct pet_scop *scop)
2823 int i;
2824 int n_ref;
2826 if (!scop)
2827 return NULL;
2829 n_ref = 0;
2830 for (i = 0; i < scop->n_stmt; ++i) {
2831 scop->stmts[i] = stmt_add_ref_ids(scop->stmts[i], &n_ref);
2832 if (!scop->stmts[i])
2833 return pet_scop_free(scop);
2836 return scop;
2839 /* Reset the user pointer on all parameter ids in "array".
2841 static struct pet_array *array_anonymize(struct pet_array *array)
2843 if (!array)
2844 return NULL;
2846 array->context = isl_set_reset_user(array->context);
2847 array->extent = isl_set_reset_user(array->extent);
2848 if (!array->context || !array->extent)
2849 return pet_array_free(array);
2851 return array;
2854 /* Reset the user pointer on all parameter and tuple ids in "stmt".
2856 static struct pet_stmt *stmt_anonymize(struct pet_stmt *stmt)
2858 int i;
2859 isl_space *space;
2860 isl_set *domain;
2862 if (!stmt)
2863 return NULL;
2865 stmt->domain = isl_set_reset_user(stmt->domain);
2866 stmt->schedule = isl_map_reset_user(stmt->schedule);
2867 if (!stmt->domain || !stmt->schedule)
2868 return pet_stmt_free(stmt);
2870 for (i = 0; i < stmt->n_arg; ++i) {
2871 stmt->args[i] = pet_expr_anonymize(stmt->args[i]);
2872 if (!stmt->args[i])
2873 return pet_stmt_free(stmt);
2876 stmt->body = pet_expr_anonymize(stmt->body);
2877 if (!stmt->body)
2878 return pet_stmt_free(stmt);
2880 return stmt;
2883 /* Reset the user pointer on the tuple ids and all parameter ids
2884 * in "implication".
2886 static struct pet_implication *implication_anonymize(
2887 struct pet_implication *implication)
2889 if (!implication)
2890 return NULL;
2892 implication->extension = isl_map_reset_user(implication->extension);
2893 if (!implication->extension)
2894 return pet_implication_free(implication);
2896 return implication;
2899 /* Reset the user pointer on all parameter and tuple ids in "scop".
2901 struct pet_scop *pet_scop_anonymize(struct pet_scop *scop)
2903 int i;
2905 if (!scop)
2906 return NULL;
2908 scop->context = isl_set_reset_user(scop->context);
2909 scop->context_value = isl_set_reset_user(scop->context_value);
2910 if (!scop->context || !scop->context_value)
2911 return pet_scop_free(scop);
2913 for (i = 0; i < scop->n_array; ++i) {
2914 scop->arrays[i] = array_anonymize(scop->arrays[i]);
2915 if (!scop->arrays[i])
2916 return pet_scop_free(scop);
2919 for (i = 0; i < scop->n_stmt; ++i) {
2920 scop->stmts[i] = stmt_anonymize(scop->stmts[i]);
2921 if (!scop->stmts[i])
2922 return pet_scop_free(scop);
2925 for (i = 0; i < scop->n_implication; ++i) {
2926 scop->implications[i] =
2927 implication_anonymize(scop->implications[i]);
2928 if (!scop->implications[i])
2929 return pet_scop_free(scop);
2932 return scop;
2935 /* Compute the gist of the iteration domain and all access relations
2936 * of "stmt" based on the constraints on the parameters specified by "context"
2937 * and the constraints on the values of nested accesses specified
2938 * by "value_bounds".
2940 static struct pet_stmt *stmt_gist(struct pet_stmt *stmt,
2941 __isl_keep isl_set *context, __isl_keep isl_union_map *value_bounds)
2943 int i;
2944 isl_set *domain;
2946 if (!stmt)
2947 return NULL;
2949 domain = isl_set_copy(stmt->domain);
2950 if (stmt->n_arg > 0)
2951 domain = isl_map_domain(isl_set_unwrap(domain));
2953 domain = isl_set_intersect_params(domain, isl_set_copy(context));
2955 for (i = 0; i < stmt->n_arg; ++i) {
2956 stmt->args[i] = pet_expr_gist(stmt->args[i],
2957 domain, value_bounds);
2958 if (!stmt->args[i])
2959 goto error;
2962 stmt->body = pet_expr_gist(stmt->body, domain, value_bounds);
2963 if (!stmt->body)
2964 goto error;
2966 isl_set_free(domain);
2968 domain = isl_set_universe(pet_stmt_get_space(stmt));
2969 domain = isl_set_intersect_params(domain, isl_set_copy(context));
2970 if (stmt->n_arg > 0)
2971 domain = pet_value_bounds_apply(domain, stmt->n_arg, stmt->args,
2972 value_bounds);
2973 stmt->domain = isl_set_gist(stmt->domain, domain);
2974 if (!stmt->domain)
2975 return pet_stmt_free(stmt);
2977 return stmt;
2978 error:
2979 isl_set_free(domain);
2980 return pet_stmt_free(stmt);
2983 /* Compute the gist of the extent of the array
2984 * based on the constraints on the parameters specified by "context".
2986 static struct pet_array *array_gist(struct pet_array *array,
2987 __isl_keep isl_set *context)
2989 if (!array)
2990 return NULL;
2992 array->extent = isl_set_gist_params(array->extent,
2993 isl_set_copy(context));
2994 if (!array->extent)
2995 return pet_array_free(array);
2997 return array;
3000 /* Compute the gist of all sets and relations in "scop"
3001 * based on the constraints on the parameters specified by "scop->context"
3002 * and the constraints on the values of nested accesses specified
3003 * by "value_bounds".
3005 struct pet_scop *pet_scop_gist(struct pet_scop *scop,
3006 __isl_keep isl_union_map *value_bounds)
3008 int i;
3010 if (!scop)
3011 return NULL;
3013 scop->context = isl_set_coalesce(scop->context);
3014 if (!scop->context)
3015 return pet_scop_free(scop);
3017 for (i = 0; i < scop->n_array; ++i) {
3018 scop->arrays[i] = array_gist(scop->arrays[i], scop->context);
3019 if (!scop->arrays[i])
3020 return pet_scop_free(scop);
3023 for (i = 0; i < scop->n_stmt; ++i) {
3024 scop->stmts[i] = stmt_gist(scop->stmts[i], scop->context,
3025 value_bounds);
3026 if (!scop->stmts[i])
3027 return pet_scop_free(scop);
3030 return scop;
3033 /* Intersect the context of "scop" with "context".
3034 * To ensure that we don't introduce any unnamed parameters in
3035 * the context of "scop", we first remove the unnamed parameters
3036 * from "context".
3038 struct pet_scop *pet_scop_restrict_context(struct pet_scop *scop,
3039 __isl_take isl_set *context)
3041 if (!scop)
3042 goto error;
3044 context = pet_nested_remove_from_set(context);
3045 scop->context = isl_set_intersect(scop->context, context);
3046 if (!scop->context)
3047 return pet_scop_free(scop);
3049 return scop;
3050 error:
3051 isl_set_free(context);
3052 return pet_scop_free(scop);
3055 /* Drop the current context of "scop". That is, replace the context
3056 * by a universal set.
3058 struct pet_scop *pet_scop_reset_context(struct pet_scop *scop)
3060 isl_space *space;
3062 if (!scop)
3063 return NULL;
3065 space = isl_set_get_space(scop->context);
3066 isl_set_free(scop->context);
3067 scop->context = isl_set_universe(space);
3068 if (!scop->context)
3069 return pet_scop_free(scop);
3071 return scop;
3074 /* Append "array" to the arrays of "scop".
3076 struct pet_scop *pet_scop_add_array(struct pet_scop *scop,
3077 struct pet_array *array)
3079 isl_ctx *ctx;
3080 struct pet_array **arrays;
3082 if (!array || !scop)
3083 goto error;
3085 ctx = isl_set_get_ctx(scop->context);
3086 arrays = isl_realloc_array(ctx, scop->arrays, struct pet_array *,
3087 scop->n_array + 1);
3088 if (!arrays)
3089 goto error;
3090 scop->arrays = arrays;
3091 scop->arrays[scop->n_array] = array;
3092 scop->n_array++;
3094 return scop;
3095 error:
3096 pet_array_free(array);
3097 return pet_scop_free(scop);
3100 /* Create an index expression for an access to a virtual array
3101 * representing the result of a condition.
3102 * Unlike other accessed data, the id of the array is NULL as
3103 * there is no ValueDecl in the program corresponding to the virtual
3104 * array.
3105 * The array starts out as a scalar, but grows along with the
3106 * statement writing to the array in pet_scop_embed.
3108 __isl_give isl_multi_pw_aff *pet_create_test_index(isl_ctx *ctx, int test_nr)
3110 isl_space *dim = isl_space_alloc(ctx, 0, 0, 0);
3111 isl_id *id;
3112 char name[50];
3114 snprintf(name, sizeof(name), "__pet_test_%d", test_nr);
3115 id = isl_id_alloc(ctx, name, NULL);
3116 dim = isl_space_set_tuple_id(dim, isl_dim_out, id);
3117 return isl_multi_pw_aff_zero(dim);
3120 /* Add an array with the given extent (range of "index") to the list
3121 * of arrays in "scop" and return the extended pet_scop.
3122 * "int_size" is the number of bytes needed to represent values of type "int".
3123 * The array is marked as attaining values 0 and 1 only and
3124 * as each element being assigned at most once.
3126 struct pet_scop *pet_scop_add_boolean_array(struct pet_scop *scop,
3127 __isl_take isl_multi_pw_aff *index, int int_size)
3129 isl_ctx *ctx;
3130 isl_space *space;
3131 struct pet_array *array;
3132 isl_map *access;
3134 if (!scop || !index)
3135 goto error;
3137 ctx = isl_multi_pw_aff_get_ctx(index);
3138 array = isl_calloc_type(ctx, struct pet_array);
3139 if (!array)
3140 goto error;
3142 access = isl_map_from_multi_pw_aff(index);
3143 array->extent = isl_map_range(access);
3144 space = isl_space_params_alloc(ctx, 0);
3145 array->context = isl_set_universe(space);
3146 space = isl_space_set_alloc(ctx, 0, 1);
3147 array->value_bounds = isl_set_universe(space);
3148 array->value_bounds = isl_set_lower_bound_si(array->value_bounds,
3149 isl_dim_set, 0, 0);
3150 array->value_bounds = isl_set_upper_bound_si(array->value_bounds,
3151 isl_dim_set, 0, 1);
3152 array->element_type = strdup("int");
3153 array->element_size = int_size;
3154 array->uniquely_defined = 1;
3156 if (!array->extent || !array->context)
3157 array = pet_array_free(array);
3159 scop = pet_scop_add_array(scop, array);
3161 return scop;
3162 error:
3163 isl_multi_pw_aff_free(index);
3164 return pet_scop_free(scop);
3167 /* Create and return an implication on filter values equal to "satisfied"
3168 * with extension "map".
3170 static struct pet_implication *new_implication(__isl_take isl_map *map,
3171 int satisfied)
3173 isl_ctx *ctx;
3174 struct pet_implication *implication;
3176 if (!map)
3177 return NULL;
3178 ctx = isl_map_get_ctx(map);
3179 implication = isl_alloc_type(ctx, struct pet_implication);
3180 if (!implication)
3181 goto error;
3183 implication->extension = map;
3184 implication->satisfied = satisfied;
3186 return implication;
3187 error:
3188 isl_map_free(map);
3189 return NULL;
3192 /* Add an implication on filter values equal to "satisfied"
3193 * with extension "map" to "scop".
3195 struct pet_scop *pet_scop_add_implication(struct pet_scop *scop,
3196 __isl_take isl_map *map, int satisfied)
3198 isl_ctx *ctx;
3199 struct pet_implication *implication;
3200 struct pet_implication **implications;
3202 implication = new_implication(map, satisfied);
3203 if (!scop || !implication)
3204 goto error;
3206 ctx = isl_set_get_ctx(scop->context);
3207 implications = isl_realloc_array(ctx, scop->implications,
3208 struct pet_implication *,
3209 scop->n_implication + 1);
3210 if (!implications)
3211 goto error;
3212 scop->implications = implications;
3213 scop->implications[scop->n_implication] = implication;
3214 scop->n_implication++;
3216 return scop;
3217 error:
3218 pet_implication_free(implication);
3219 return pet_scop_free(scop);
3222 /* Given an access expression, check if it is data dependent.
3223 * If so, set *found and abort the search.
3225 static int is_data_dependent(__isl_keep pet_expr *expr, void *user)
3227 int *found = user;
3229 if (pet_expr_get_n_arg(expr) > 0) {
3230 *found = 1;
3231 return -1;
3234 return 0;
3237 /* Does "scop" contain any data dependent accesses?
3239 * Check the body of each statement for such accesses.
3241 int pet_scop_has_data_dependent_accesses(struct pet_scop *scop)
3243 int i;
3244 int found = 0;
3246 if (!scop)
3247 return -1;
3249 for (i = 0; i < scop->n_stmt; ++i) {
3250 int r = pet_expr_foreach_access_expr(scop->stmts[i]->body,
3251 &is_data_dependent, &found);
3252 if (r < 0 && !found)
3253 return -1;
3254 if (found)
3255 return found;
3258 return found;
3261 /* Does "scop" contain and data dependent conditions?
3263 int pet_scop_has_data_dependent_conditions(struct pet_scop *scop)
3265 int i;
3267 if (!scop)
3268 return -1;
3270 for (i = 0; i < scop->n_stmt; ++i)
3271 if (scop->stmts[i]->n_arg > 0)
3272 return 1;
3274 return 0;
3277 /* Keep track of the "input" file inside the (extended) "scop".
3279 struct pet_scop *pet_scop_set_input_file(struct pet_scop *scop, FILE *input)
3281 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
3283 if (!scop)
3284 return NULL;
3286 ext->input = input;
3288 return scop;
3291 /* Print the original code corresponding to "scop" to printer "p".
3293 * pet_scop_print_original can only be called from
3294 * a pet_transform_C_source callback. This means that the input
3295 * file is stored in the extended scop and that the printer prints
3296 * to a file.
3298 __isl_give isl_printer *pet_scop_print_original(struct pet_scop *scop,
3299 __isl_take isl_printer *p)
3301 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
3302 FILE *output;
3304 if (!scop || !p)
3305 return isl_printer_free(p);
3307 if (!ext->input)
3308 isl_die(isl_printer_get_ctx(p), isl_error_invalid,
3309 "no input file stored in scop",
3310 return isl_printer_free(p));
3312 output = isl_printer_get_file(p);
3313 if (!output)
3314 return isl_printer_free(p);
3316 if (copy(ext->input, output, scop->start, scop->end) < 0)
3317 return isl_printer_free(p);
3319 return p;