scop.c: expr_collect_accesses: drop unused variable
[pet.git] / scop.c
blobdbcf7f432497c6c256522820e62f1b91546ec264
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/ctx.h>
37 #include <isl/id.h>
38 #include <isl/space.h>
39 #include <isl/local_space.h>
40 #include <isl/constraint.h>
41 #include <isl/val.h>
42 #include <isl/aff.h>
43 #include <isl/set.h>
44 #include <isl/map.h>
45 #include <isl/union_set.h>
46 #include <isl/union_map.h>
47 #include <isl/schedule_node.h>
49 #include "aff.h"
50 #include "expr.h"
51 #include "expr_access_type.h"
52 #include "filter.h"
53 #include "loc.h"
54 #include "nest.h"
55 #include "scop.h"
56 #include "tree.h"
57 #include "print.h"
58 #include "value_bounds.h"
60 /* pet_scop with extra information that is used during parsing and printing.
62 * In particular, we keep track of conditions under which we want
63 * to skip the rest of the current loop iteration (skip[pet_skip_now])
64 * and of conditions under which we want to skip subsequent
65 * loop iterations (skip[pet_skip_later]).
67 * The conditions are represented as index expressions defined
68 * over the outer loop iterators. The index expression is either
69 * a boolean affine expression or an access to a variable, which
70 * is assumed to attain values zero and one. The condition holds
71 * if the variable has value one or if the affine expression
72 * has value one (typically for only part of the domain).
74 * A missing condition (skip[type] == NULL) means that we don't want
75 * to skip anything.
77 * Additionally, we keep track of the original input file
78 * inside pet_transform_C_source.
80 struct pet_scop_ext {
81 struct pet_scop scop;
83 isl_multi_pw_aff *skip[2];
84 FILE *input;
87 /* Construct a pet_stmt with given domain and statement number from a pet_tree.
88 * The input domain is anonymous and is the same as the domains
89 * of the access expressions inside "tree".
90 * These domains are modified to include the name of the statement.
91 * This name is given by tree->label if it is non-NULL.
92 * Otherwise, the name is constructed as S_<id>.
94 struct pet_stmt *pet_stmt_from_pet_tree(__isl_take isl_set *domain,
95 int id, __isl_take pet_tree *tree)
97 struct pet_stmt *stmt;
98 isl_ctx *ctx;
99 isl_id *label;
100 isl_space *space;
101 isl_multi_aff *ma;
102 isl_multi_pw_aff *add_name;
103 char name[50];
105 if (!domain || !tree)
106 goto error;
108 ctx = pet_tree_get_ctx(tree);
109 stmt = isl_calloc_type(ctx, struct pet_stmt);
110 if (!stmt)
111 goto error;
113 if (tree->label) {
114 label = isl_id_copy(tree->label);
115 } else {
116 snprintf(name, sizeof(name), "S_%d", id);
117 label = isl_id_alloc(ctx, name, NULL);
119 domain = isl_set_set_tuple_id(domain, label);
120 space = isl_set_get_space(domain);
121 space = pet_nested_remove_from_space(space);
122 ma = pet_prefix_projection(space, isl_space_dim(space, isl_dim_set));
124 add_name = isl_multi_pw_aff_from_multi_aff(ma);
125 tree = pet_tree_update_domain(tree, add_name);
127 stmt->loc = pet_tree_get_loc(tree);
128 stmt->domain = domain;
129 stmt->body = tree;
131 if (!stmt->domain || !stmt->body)
132 return pet_stmt_free(stmt);
134 return stmt;
135 error:
136 isl_set_free(domain);
137 pet_tree_free(tree);
138 return NULL;
141 void *pet_stmt_free(struct pet_stmt *stmt)
143 int i;
145 if (!stmt)
146 return NULL;
148 pet_loc_free(stmt->loc);
149 isl_set_free(stmt->domain);
150 pet_tree_free(stmt->body);
152 for (i = 0; i < stmt->n_arg; ++i)
153 pet_expr_free(stmt->args[i]);
154 free(stmt->args);
156 free(stmt);
157 return NULL;
160 /* Return the iteration space of "stmt".
162 * If the statement has arguments, then stmt->domain is a wrapped map
163 * mapping the iteration domain to the values of the arguments
164 * for which this statement is executed.
165 * In this case, we need to extract the domain space of this wrapped map.
167 __isl_give isl_space *pet_stmt_get_space(struct pet_stmt *stmt)
169 isl_space *space;
171 if (!stmt)
172 return NULL;
174 space = isl_set_get_space(stmt->domain);
175 if (isl_space_is_wrapping(space))
176 space = isl_space_domain(isl_space_unwrap(space));
178 return space;
181 static void stmt_dump(struct pet_stmt *stmt, int indent)
183 int i;
185 if (!stmt)
186 return;
188 fprintf(stderr, "%*s%d\n", indent, "", pet_loc_get_line(stmt->loc));
189 fprintf(stderr, "%*s", indent, "");
190 isl_set_dump(stmt->domain);
191 pet_tree_dump_with_indent(stmt->body, indent);
192 for (i = 0; i < stmt->n_arg; ++i)
193 pet_expr_dump_with_indent(stmt->args[i], indent + 2);
196 void pet_stmt_dump(struct pet_stmt *stmt)
198 stmt_dump(stmt, 0);
201 /* Allocate a new pet_type with the given "name" and "definition".
203 struct pet_type *pet_type_alloc(isl_ctx *ctx, const char *name,
204 const char *definition)
206 struct pet_type *type;
208 type = isl_alloc_type(ctx, struct pet_type);
209 if (!type)
210 return NULL;
212 type->name = strdup(name);
213 type->definition = strdup(definition);
215 if (!type->name || !type->definition)
216 return pet_type_free(type);
218 return type;
221 /* Free "type" and return NULL.
223 struct pet_type *pet_type_free(struct pet_type *type)
225 if (!type)
226 return NULL;
228 free(type->name);
229 free(type->definition);
231 free(type);
232 return NULL;
235 struct pet_array *pet_array_free(struct pet_array *array)
237 if (!array)
238 return NULL;
240 isl_set_free(array->context);
241 isl_set_free(array->extent);
242 isl_set_free(array->value_bounds);
243 free(array->element_type);
245 free(array);
246 return NULL;
249 void pet_array_dump(struct pet_array *array)
251 if (!array)
252 return;
254 isl_set_dump(array->context);
255 isl_set_dump(array->extent);
256 isl_set_dump(array->value_bounds);
257 fprintf(stderr, "%s%s%s\n", array->element_type,
258 array->element_is_record ? " element-is-record" : "",
259 array->live_out ? " live-out" : "");
262 /* Alloc a pet_scop structure, with extra room for information that
263 * is only used during parsing.
265 struct pet_scop *pet_scop_alloc(isl_ctx *ctx)
267 return &isl_calloc_type(ctx, struct pet_scop_ext)->scop;
270 /* Construct a pet_scop in the given space, with the given schedule and
271 * room for n statements.
273 * The context is initialized as a universe set in "space".
275 * Since no information on the location is known at this point,
276 * scop->loc is initialized with pet_loc_dummy.
278 static struct pet_scop *scop_alloc(__isl_take isl_space *space, int n,
279 __isl_take isl_schedule *schedule)
281 isl_ctx *ctx;
282 struct pet_scop *scop;
284 if (!space || !schedule)
285 goto error;
287 ctx = isl_space_get_ctx(space);
288 scop = pet_scop_alloc(ctx);
289 if (!scop)
290 goto error;
292 scop->context = isl_set_universe(isl_space_copy(space));
293 scop->context_value = isl_set_universe(isl_space_params(space));
294 scop->stmts = isl_calloc_array(ctx, struct pet_stmt *, n);
295 scop->schedule = schedule;
296 if (!scop->context || !scop->stmts)
297 return pet_scop_free(scop);
299 scop->loc = &pet_loc_dummy;
300 scop->n_stmt = n;
302 return scop;
303 error:
304 isl_space_free(space);
305 isl_schedule_free(schedule);
306 return NULL;
309 /* Construct a pet_scop in the given space containing 0 statements
310 * (and therefore an empty iteration domain).
312 struct pet_scop *pet_scop_empty(__isl_take isl_space *space)
314 isl_schedule *schedule;
316 schedule = isl_schedule_empty(isl_space_copy(space));
318 return scop_alloc(space, 0, schedule);
321 /* Given either an iteration domain or a wrapped map with
322 * the iteration domain in the domain and some arguments
323 * in the range, return the iteration domain.
324 * That is, drop the arguments if there are any.
326 static __isl_give isl_set *drop_arguments(__isl_take isl_set *domain)
328 if (isl_set_is_wrapping(domain))
329 domain = isl_map_domain(isl_set_unwrap(domain));
330 return domain;
333 /* Update "context" with the constraints imposed on the outer iteration
334 * domain by access expression "expr".
335 * "context" lives in an anonymous space, while the domain of the access
336 * relation of "expr" refers to a particular statement.
337 * This reference therefore needs to be stripped off.
339 static __isl_give isl_set *access_extract_context(__isl_keep pet_expr *expr,
340 __isl_take isl_set *context)
342 isl_multi_pw_aff *mpa;
343 isl_set *domain;
345 mpa = pet_expr_access_get_index(expr);
346 domain = drop_arguments(isl_multi_pw_aff_domain(mpa));
347 domain = isl_set_reset_tuple_id(domain);
348 context = isl_set_intersect(context, domain);
349 return context;
352 /* Update "context" with the constraints imposed on the outer iteration
353 * domain by "expr".
355 * "context" lives in an anonymous space, while the domains of
356 * the access relations in "expr" refer to a particular statement.
357 * This reference therefore needs to be stripped off.
359 * If "expr" represents a conditional operator, then a parameter or outer
360 * iterator value needs to be valid for the condition and
361 * for at least one of the remaining two arguments.
362 * If the condition is an affine expression, then we can be a bit more specific.
363 * The value then has to be valid for the second argument for
364 * non-zero accesses and valid for the third argument for zero accesses.
366 * If "expr" represents a kill statement, then its argument is the entire
367 * extent of the array being killed. Do not update "context" based
368 * on this argument as that would impose constraints that ensure that
369 * the array is non-empty.
371 static __isl_give isl_set *expr_extract_context(__isl_keep pet_expr *expr,
372 __isl_take isl_set *context)
374 int i;
376 if (expr->type == pet_expr_op && expr->op == pet_op_kill)
377 return context;
379 if (expr->type == pet_expr_op && expr->op == pet_op_cond) {
380 int is_aff;
381 isl_set *context1, *context2;
383 is_aff = pet_expr_is_affine(expr->args[0]);
384 if (is_aff < 0)
385 goto error;
387 context = expr_extract_context(expr->args[0], context);
388 context1 = expr_extract_context(expr->args[1],
389 isl_set_copy(context));
390 context2 = expr_extract_context(expr->args[2], context);
392 if (is_aff) {
393 isl_multi_pw_aff *mpa;
394 isl_pw_aff *pa;
395 isl_set *zero_set;
397 mpa = pet_expr_access_get_index(expr->args[0]);
398 pa = isl_multi_pw_aff_get_pw_aff(mpa, 0);
399 isl_multi_pw_aff_free(mpa);
400 zero_set = drop_arguments(isl_pw_aff_zero_set(pa));
401 zero_set = isl_set_reset_tuple_id(zero_set);
402 context1 = isl_set_subtract(context1,
403 isl_set_copy(zero_set));
404 context2 = isl_set_intersect(context2, zero_set);
407 context = isl_set_union(context1, context2);
408 context = isl_set_coalesce(context);
410 return context;
413 for (i = 0; i < expr->n_arg; ++i)
414 context = expr_extract_context(expr->args[i], context);
416 if (expr->type == pet_expr_access)
417 context = access_extract_context(expr, context);
419 return context;
420 error:
421 isl_set_free(context);
422 return NULL;
425 /* Is "stmt" an assume statement with an affine assumption?
427 isl_bool pet_stmt_is_affine_assume(struct pet_stmt *stmt)
429 if (!stmt)
430 return isl_bool_error;
431 return pet_tree_is_affine_assume(stmt->body);
434 /* Given an assume statement "stmt" with an access argument,
435 * return the index expression of the argument.
437 __isl_give isl_multi_pw_aff *pet_stmt_assume_get_index(struct pet_stmt *stmt)
439 if (!stmt)
440 return NULL;
441 return pet_tree_assume_get_index(stmt->body);
444 /* Assuming "stmt" is an assume statement with an affine assumption,
445 * return the assumption as a set.
447 __isl_give isl_set *pet_stmt_assume_get_affine_condition(struct pet_stmt *stmt)
449 isl_multi_pw_aff *index;
450 isl_pw_aff *pa;
452 index = pet_stmt_assume_get_index(stmt);
453 pa = isl_multi_pw_aff_get_pw_aff(index, 0);
454 isl_multi_pw_aff_free(index);
455 return isl_pw_aff_non_zero_set(pa);
458 /* Update "context" with the constraints imposed on the outer iteration
459 * domain by "stmt".
461 * If the statement is an assume statement with an affine expression,
462 * then intersect "context" with that expression.
463 * Otherwise, if the statement body is an expression tree,
464 * then intersect "context" with the context of this expression.
465 * Note that we cannot safely extract a context from subtrees
466 * of the statement body since we cannot tell when those subtrees
467 * are executed, if at all.
469 static __isl_give isl_set *stmt_extract_context(struct pet_stmt *stmt,
470 __isl_take isl_set *context)
472 int i;
473 isl_bool affine;
474 pet_expr *body;
476 affine = pet_stmt_is_affine_assume(stmt);
477 if (affine < 0)
478 return isl_set_free(context);
479 if (affine) {
480 isl_set *cond;
482 cond = pet_stmt_assume_get_affine_condition(stmt);
483 cond = isl_set_reset_tuple_id(cond);
484 return isl_set_intersect(context, cond);
487 for (i = 0; i < stmt->n_arg; ++i)
488 context = expr_extract_context(stmt->args[i], context);
490 if (pet_tree_get_type(stmt->body) != pet_tree_expr)
491 return context;
493 body = pet_tree_expr_get_expr(stmt->body);
494 context = expr_extract_context(body, context);
495 pet_expr_free(body);
497 return context;
500 /* Construct a pet_scop in the given space that contains the given pet_stmt.
501 * The initial schedule consists of only the iteration domain.
503 struct pet_scop *pet_scop_from_pet_stmt(__isl_take isl_space *space,
504 struct pet_stmt *stmt)
506 struct pet_scop *scop;
507 isl_set *set;
508 isl_union_set *domain;
509 isl_schedule *schedule;
511 if (!stmt) {
512 isl_space_free(space);
513 return NULL;
516 set = pet_nested_remove_from_set(isl_set_copy(stmt->domain));
517 domain = isl_union_set_from_set(set);
518 schedule = isl_schedule_from_domain(domain);
520 scop = scop_alloc(space, 1, schedule);
521 if (!scop)
522 goto error;
524 scop->context = stmt_extract_context(stmt, scop->context);
525 if (!scop->context)
526 goto error;
528 scop->stmts[0] = stmt;
529 scop->loc = pet_loc_copy(stmt->loc);
531 if (!scop->loc)
532 return pet_scop_free(scop);
534 return scop;
535 error:
536 pet_stmt_free(stmt);
537 pet_scop_free(scop);
538 return NULL;
541 /* Does "mpa" represent an access to an element of an unnamed space, i.e.,
542 * does it represent an affine expression?
544 static int multi_pw_aff_is_affine(__isl_keep isl_multi_pw_aff *mpa)
546 int has_id;
548 has_id = isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out);
549 if (has_id < 0)
550 return -1;
552 return !has_id;
555 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
557 static __isl_give isl_pw_aff *indicator_function(__isl_take isl_set *set,
558 __isl_take isl_set *dom)
560 isl_pw_aff *pa;
561 pa = isl_set_indicator_function(set);
562 pa = isl_pw_aff_intersect_domain(pa, dom);
563 return pa;
566 /* Return "lhs || rhs", defined on the shared definition domain.
568 static __isl_give isl_pw_aff *pw_aff_or(__isl_take isl_pw_aff *lhs,
569 __isl_take isl_pw_aff *rhs)
571 isl_set *cond;
572 isl_set *dom;
574 dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs)),
575 isl_pw_aff_domain(isl_pw_aff_copy(rhs)));
576 cond = isl_set_union(isl_pw_aff_non_zero_set(lhs),
577 isl_pw_aff_non_zero_set(rhs));
578 cond = isl_set_coalesce(cond);
579 return indicator_function(cond, dom);
582 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
583 * ext may be equal to either ext1 or ext2.
585 * The two skips that need to be combined are assumed to be affine expressions.
587 * We need to skip in ext if we need to skip in either ext1 or ext2.
588 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
590 static struct pet_scop_ext *combine_skips(struct pet_scop_ext *ext,
591 struct pet_scop_ext *ext1, struct pet_scop_ext *ext2,
592 enum pet_skip type)
594 isl_pw_aff *skip, *skip1, *skip2;
596 if (!ext)
597 return NULL;
598 if (!ext1->skip[type] && !ext2->skip[type])
599 return ext;
600 if (!ext1->skip[type]) {
601 if (ext == ext2)
602 return ext;
603 ext->skip[type] = ext2->skip[type];
604 ext2->skip[type] = NULL;
605 return ext;
607 if (!ext2->skip[type]) {
608 if (ext == ext1)
609 return ext;
610 ext->skip[type] = ext1->skip[type];
611 ext1->skip[type] = NULL;
612 return ext;
615 if (!multi_pw_aff_is_affine(ext1->skip[type]) ||
616 !multi_pw_aff_is_affine(ext2->skip[type]))
617 isl_die(isl_multi_pw_aff_get_ctx(ext1->skip[type]),
618 isl_error_internal, "can only combine affine skips",
619 goto error);
621 skip1 = isl_multi_pw_aff_get_pw_aff(ext1->skip[type], 0);
622 skip2 = isl_multi_pw_aff_get_pw_aff(ext2->skip[type], 0);
623 skip = pw_aff_or(skip1, skip2);
624 isl_multi_pw_aff_free(ext1->skip[type]);
625 ext1->skip[type] = NULL;
626 isl_multi_pw_aff_free(ext2->skip[type]);
627 ext2->skip[type] = NULL;
628 ext->skip[type] = isl_multi_pw_aff_from_pw_aff(skip);
629 if (!ext->skip[type])
630 goto error;
632 return ext;
633 error:
634 pet_scop_free(&ext->scop);
635 return NULL;
638 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
639 * where type takes on the values pet_skip_now and pet_skip_later.
640 * scop may be equal to either scop1 or scop2.
642 static struct pet_scop *scop_combine_skips(struct pet_scop *scop,
643 struct pet_scop *scop1, struct pet_scop *scop2)
645 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
646 struct pet_scop_ext *ext1 = (struct pet_scop_ext *) scop1;
647 struct pet_scop_ext *ext2 = (struct pet_scop_ext *) scop2;
649 ext = combine_skips(ext, ext1, ext2, pet_skip_now);
650 ext = combine_skips(ext, ext1, ext2, pet_skip_later);
651 return &ext->scop;
654 /* Update start and end of scop->loc to include the region from "start"
655 * to "end". In particular, if scop->loc == &pet_loc_dummy, then "scop"
656 * does not have any offset information yet and we simply take the information
657 * from "start" and "end". Otherwise, we update loc using "start" and "end".
659 struct pet_scop *pet_scop_update_start_end(struct pet_scop *scop,
660 unsigned start, unsigned end)
662 if (!scop)
663 return NULL;
665 if (scop->loc == &pet_loc_dummy)
666 scop->loc = pet_loc_alloc(isl_set_get_ctx(scop->context),
667 start, end, -1, strdup(""));
668 else
669 scop->loc = pet_loc_update_start_end(scop->loc, start, end);
671 if (!scop->loc)
672 return pet_scop_free(scop);
674 return scop;
677 /* Update start and end of scop->loc to include the region identified
678 * by "loc".
680 struct pet_scop *pet_scop_update_start_end_from_loc(struct pet_scop *scop,
681 __isl_keep pet_loc *loc)
683 return pet_scop_update_start_end(scop, pet_loc_get_start(loc),
684 pet_loc_get_end(loc));
687 /* Replace the location of "scop" by "loc".
689 struct pet_scop *pet_scop_set_loc(struct pet_scop *scop,
690 __isl_take pet_loc *loc)
692 if (!scop || !loc)
693 goto error;
695 pet_loc_free(scop->loc);
696 scop->loc = loc;
698 return scop;
699 error:
700 pet_loc_free(loc);
701 pet_scop_free(scop);
702 return NULL;
705 /* Does "implication" appear in the list of implications of "scop"?
707 static int is_known_implication(struct pet_scop *scop,
708 struct pet_implication *implication)
710 int i;
712 for (i = 0; i < scop->n_implication; ++i) {
713 struct pet_implication *pi = scop->implications[i];
714 int equal;
716 if (pi->satisfied != implication->satisfied)
717 continue;
718 equal = isl_map_is_equal(pi->extension, implication->extension);
719 if (equal < 0)
720 return -1;
721 if (equal)
722 return 1;
725 return 0;
728 /* Store the concatenation of the implications of "scop1" and "scop2"
729 * in "scop", removing duplicates (i.e., implications in "scop2" that
730 * already appear in "scop1").
732 static struct pet_scop *scop_collect_implications(isl_ctx *ctx,
733 struct pet_scop *scop, struct pet_scop *scop1, struct pet_scop *scop2)
735 int i, j;
737 if (!scop)
738 return NULL;
740 if (scop2->n_implication == 0) {
741 scop->n_implication = scop1->n_implication;
742 scop->implications = scop1->implications;
743 scop1->n_implication = 0;
744 scop1->implications = NULL;
745 return scop;
748 if (scop1->n_implication == 0) {
749 scop->n_implication = scop2->n_implication;
750 scop->implications = scop2->implications;
751 scop2->n_implication = 0;
752 scop2->implications = NULL;
753 return scop;
756 scop->implications = isl_calloc_array(ctx, struct pet_implication *,
757 scop1->n_implication + scop2->n_implication);
758 if (!scop->implications)
759 return pet_scop_free(scop);
761 for (i = 0; i < scop1->n_implication; ++i) {
762 scop->implications[i] = scop1->implications[i];
763 scop1->implications[i] = NULL;
766 scop->n_implication = scop1->n_implication;
767 j = scop1->n_implication;
768 for (i = 0; i < scop2->n_implication; ++i) {
769 int known;
771 known = is_known_implication(scop, scop2->implications[i]);
772 if (known < 0)
773 return pet_scop_free(scop);
774 if (known)
775 continue;
776 scop->implications[j++] = scop2->implications[i];
777 scop2->implications[i] = NULL;
779 scop->n_implication = j;
781 return scop;
784 /* Combine the offset information of "scop1" and "scop2" into "scop".
786 static struct pet_scop *scop_combine_start_end(struct pet_scop *scop,
787 struct pet_scop *scop1, struct pet_scop *scop2)
789 if (scop1->loc != &pet_loc_dummy)
790 scop = pet_scop_update_start_end_from_loc(scop, scop1->loc);
791 if (scop2->loc != &pet_loc_dummy)
792 scop = pet_scop_update_start_end_from_loc(scop, scop2->loc);
793 return scop;
796 /* Create and return an independence that filters out the dependences
797 * in "filter" with local variables "local".
799 static struct pet_independence *new_independence(
800 __isl_take isl_union_map *filter, __isl_take isl_union_set *local)
802 isl_ctx *ctx;
803 struct pet_independence *independence;
805 if (!filter || !local)
806 goto error;
807 ctx = isl_union_map_get_ctx(filter);
808 independence = isl_alloc_type(ctx, struct pet_independence);
809 if (!independence)
810 goto error;
812 independence->filter = filter;
813 independence->local = local;
815 return independence;
816 error:
817 isl_union_map_free(filter);
818 isl_union_set_free(local);
819 return NULL;
822 /* Add an independence that filters out the dependences
823 * in "filter" with local variables "local" to "scop".
825 struct pet_scop *pet_scop_add_independence(struct pet_scop *scop,
826 __isl_take isl_union_map *filter, __isl_take isl_union_set *local)
828 isl_ctx *ctx;
829 struct pet_independence *independence;
830 struct pet_independence **independences;
832 ctx = isl_union_map_get_ctx(filter);
833 independence = new_independence(filter, local);
834 if (!scop || !independence)
835 goto error;
837 independences = isl_realloc_array(ctx, scop->independences,
838 struct pet_independence *,
839 scop->n_independence + 1);
840 if (!independences)
841 goto error;
842 scop->independences = independences;
843 scop->independences[scop->n_independence] = independence;
844 scop->n_independence++;
846 return scop;
847 error:
848 pet_independence_free(independence);
849 pet_scop_free(scop);
850 return NULL;
853 /* Store the concatenation of the independences of "scop1" and "scop2"
854 * in "scop".
856 static struct pet_scop *scop_collect_independences(isl_ctx *ctx,
857 struct pet_scop *scop, struct pet_scop *scop1, struct pet_scop *scop2)
859 int i, off;
861 if (!scop)
862 return NULL;
864 if (scop2->n_independence == 0) {
865 scop->n_independence = scop1->n_independence;
866 scop->independences = scop1->independences;
867 scop1->n_independence = 0;
868 scop1->independences = NULL;
869 return scop;
872 if (scop1->n_independence == 0) {
873 scop->n_independence = scop2->n_independence;
874 scop->independences = scop2->independences;
875 scop2->n_independence = 0;
876 scop2->independences = NULL;
877 return scop;
880 scop->independences = isl_calloc_array(ctx, struct pet_independence *,
881 scop1->n_independence + scop2->n_independence);
882 if (!scop->independences)
883 return pet_scop_free(scop);
885 for (i = 0; i < scop1->n_independence; ++i) {
886 scop->independences[i] = scop1->independences[i];
887 scop1->independences[i] = NULL;
890 off = scop1->n_independence;
891 for (i = 0; i < scop2->n_independence; ++i) {
892 scop->independences[off + i] = scop2->independences[i];
893 scop2->independences[i] = NULL;
895 scop->n_independence = scop1->n_independence + scop2->n_independence;
897 return scop;
900 /* Construct a pet_scop with the given schedule
901 * that contains the offset information,
902 * arrays, statements and skip information in "scop1" and "scop2".
904 static struct pet_scop *pet_scop_add(isl_ctx *ctx,
905 __isl_take isl_schedule *schedule, struct pet_scop *scop1,
906 struct pet_scop *scop2)
908 int i;
909 isl_space *space;
910 struct pet_scop *scop = NULL;
912 if (!scop1 || !scop2)
913 goto error;
915 if (scop1->n_stmt == 0) {
916 scop2 = scop_combine_skips(scop2, scop1, scop2);
917 pet_scop_free(scop1);
918 isl_schedule_free(schedule);
919 return scop2;
922 if (scop2->n_stmt == 0) {
923 scop1 = scop_combine_skips(scop1, scop1, scop2);
924 pet_scop_free(scop2);
925 isl_schedule_free(schedule);
926 return scop1;
929 space = isl_set_get_space(scop1->context);
930 scop = scop_alloc(space, scop1->n_stmt + scop2->n_stmt,
931 isl_schedule_copy(schedule));
932 if (!scop)
933 goto error;
935 scop->arrays = isl_calloc_array(ctx, struct pet_array *,
936 scop1->n_array + scop2->n_array);
937 if (!scop->arrays)
938 goto error;
939 scop->n_array = scop1->n_array + scop2->n_array;
941 for (i = 0; i < scop1->n_stmt; ++i) {
942 scop->stmts[i] = scop1->stmts[i];
943 scop1->stmts[i] = NULL;
946 for (i = 0; i < scop2->n_stmt; ++i) {
947 scop->stmts[scop1->n_stmt + i] = scop2->stmts[i];
948 scop2->stmts[i] = NULL;
951 for (i = 0; i < scop1->n_array; ++i) {
952 scop->arrays[i] = scop1->arrays[i];
953 scop1->arrays[i] = NULL;
956 for (i = 0; i < scop2->n_array; ++i) {
957 scop->arrays[scop1->n_array + i] = scop2->arrays[i];
958 scop2->arrays[i] = NULL;
961 scop = scop_collect_implications(ctx, scop, scop1, scop2);
962 scop = pet_scop_restrict_context(scop, isl_set_copy(scop1->context));
963 scop = pet_scop_restrict_context(scop, isl_set_copy(scop2->context));
964 scop = scop_combine_skips(scop, scop1, scop2);
965 scop = scop_combine_start_end(scop, scop1, scop2);
966 scop = scop_collect_independences(ctx, scop, scop1, scop2);
968 pet_scop_free(scop1);
969 pet_scop_free(scop2);
970 isl_schedule_free(schedule);
971 return scop;
972 error:
973 pet_scop_free(scop1);
974 pet_scop_free(scop2);
975 pet_scop_free(scop);
976 isl_schedule_free(schedule);
977 return NULL;
980 /* Apply the skip condition "skip" to "scop".
981 * That is, make sure "scop" is not executed when the condition holds.
983 * If "skip" is an affine expression, we add the conditions under
984 * which the expression is zero to the context and the skip conditions
985 * of "scop".
986 * Otherwise, we add a filter on the variable attaining the value zero.
988 static struct pet_scop *restrict_skip(struct pet_scop *scop,
989 __isl_take isl_multi_pw_aff *skip)
991 isl_set *zero;
992 isl_pw_aff *pa;
993 int is_aff;
995 if (!scop || !skip)
996 goto error;
998 is_aff = multi_pw_aff_is_affine(skip);
999 if (is_aff < 0)
1000 goto error;
1002 if (!is_aff)
1003 return pet_scop_filter(scop, skip, 0);
1005 pa = isl_multi_pw_aff_get_pw_aff(skip, 0);
1006 isl_multi_pw_aff_free(skip);
1007 zero = isl_pw_aff_zero_set(pa);
1008 scop = pet_scop_restrict(scop, zero);
1010 return scop;
1011 error:
1012 isl_multi_pw_aff_free(skip);
1013 return pet_scop_free(scop);
1016 /* Construct a pet_scop that contains the arrays, statements and
1017 * skip information in "scop1" and "scop2", where the two scops
1018 * are executed "in sequence". That is, breaks and continues
1019 * in scop1 have an effect on scop2 and the schedule of the result
1020 * is the sequence of the schedules of "scop1" and "scop2".
1022 struct pet_scop *pet_scop_add_seq(isl_ctx *ctx, struct pet_scop *scop1,
1023 struct pet_scop *scop2)
1025 isl_schedule *schedule;
1027 if (!scop1 || !scop2)
1028 goto error;
1030 if (scop1 && pet_scop_has_skip(scop1, pet_skip_now))
1031 scop2 = restrict_skip(scop2,
1032 pet_scop_get_skip(scop1, pet_skip_now));
1033 schedule = isl_schedule_sequence(isl_schedule_copy(scop1->schedule),
1034 isl_schedule_copy(scop2->schedule));
1035 return pet_scop_add(ctx, schedule, scop1, scop2);
1036 error:
1037 pet_scop_free(scop1);
1038 pet_scop_free(scop2);
1039 return NULL;
1042 /* Construct a pet_scop that contains the arrays, statements and
1043 * skip information in "scop1" and "scop2", where the two scops
1044 * are executed "in parallel". That is, any break or continue
1045 * in scop1 has no effect on scop2 and the schedule of the result
1046 * is the set of the schedules of "scop1" and "scop2".
1048 struct pet_scop *pet_scop_add_par(isl_ctx *ctx, struct pet_scop *scop1,
1049 struct pet_scop *scop2)
1051 isl_schedule *schedule;
1053 if (!scop1 || !scop2)
1054 goto error;
1056 schedule = isl_schedule_set(isl_schedule_copy(scop1->schedule),
1057 isl_schedule_copy(scop2->schedule));
1058 return pet_scop_add(ctx, schedule, scop1, scop2);
1059 error:
1060 pet_scop_free(scop1);
1061 pet_scop_free(scop2);
1062 return NULL;
1065 void *pet_implication_free(struct pet_implication *implication)
1067 if (!implication)
1068 return NULL;
1070 isl_map_free(implication->extension);
1072 free(implication);
1073 return NULL;
1076 void *pet_independence_free(struct pet_independence *independence)
1078 if (!independence)
1079 return NULL;
1081 isl_union_map_free(independence->filter);
1082 isl_union_set_free(independence->local);
1084 free(independence);
1085 return NULL;
1088 struct pet_scop *pet_scop_free(struct pet_scop *scop)
1090 int i;
1091 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1093 if (!scop)
1094 return NULL;
1095 pet_loc_free(scop->loc);
1096 isl_set_free(scop->context);
1097 isl_set_free(scop->context_value);
1098 isl_schedule_free(scop->schedule);
1099 if (scop->types)
1100 for (i = 0; i < scop->n_type; ++i)
1101 pet_type_free(scop->types[i]);
1102 free(scop->types);
1103 if (scop->arrays)
1104 for (i = 0; i < scop->n_array; ++i)
1105 pet_array_free(scop->arrays[i]);
1106 free(scop->arrays);
1107 if (scop->stmts)
1108 for (i = 0; i < scop->n_stmt; ++i)
1109 pet_stmt_free(scop->stmts[i]);
1110 free(scop->stmts);
1111 if (scop->implications)
1112 for (i = 0; i < scop->n_implication; ++i)
1113 pet_implication_free(scop->implications[i]);
1114 free(scop->implications);
1115 if (scop->independences)
1116 for (i = 0; i < scop->n_independence; ++i)
1117 pet_independence_free(scop->independences[i]);
1118 free(scop->independences);
1119 isl_multi_pw_aff_free(ext->skip[pet_skip_now]);
1120 isl_multi_pw_aff_free(ext->skip[pet_skip_later]);
1121 free(scop);
1122 return NULL;
1125 void pet_type_dump(struct pet_type *type)
1127 if (!type)
1128 return;
1130 fprintf(stderr, "%s -> %s\n", type->name, type->definition);
1133 void pet_implication_dump(struct pet_implication *implication)
1135 if (!implication)
1136 return;
1138 fprintf(stderr, "%d\n", implication->satisfied);
1139 isl_map_dump(implication->extension);
1142 void pet_scop_dump(struct pet_scop *scop)
1144 int i;
1145 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1147 if (!scop)
1148 return;
1150 isl_set_dump(scop->context);
1151 isl_set_dump(scop->context_value);
1152 isl_schedule_dump(scop->schedule);
1153 for (i = 0; i < scop->n_type; ++i)
1154 pet_type_dump(scop->types[i]);
1155 for (i = 0; i < scop->n_array; ++i)
1156 pet_array_dump(scop->arrays[i]);
1157 for (i = 0; i < scop->n_stmt; ++i)
1158 pet_stmt_dump(scop->stmts[i]);
1159 for (i = 0; i < scop->n_implication; ++i)
1160 pet_implication_dump(scop->implications[i]);
1162 if (ext->skip[0]) {
1163 fprintf(stderr, "skip\n");
1164 isl_multi_pw_aff_dump(ext->skip[0]);
1165 isl_multi_pw_aff_dump(ext->skip[1]);
1169 /* Return 1 if the two pet_arrays are equivalent.
1171 * We don't compare element_size as this may be target dependent.
1173 int pet_array_is_equal(struct pet_array *array1, struct pet_array *array2)
1175 if (!array1 || !array2)
1176 return 0;
1178 if (!isl_set_is_equal(array1->context, array2->context))
1179 return 0;
1180 if (!isl_set_is_equal(array1->extent, array2->extent))
1181 return 0;
1182 if (!!array1->value_bounds != !!array2->value_bounds)
1183 return 0;
1184 if (array1->value_bounds &&
1185 !isl_set_is_equal(array1->value_bounds, array2->value_bounds))
1186 return 0;
1187 if (strcmp(array1->element_type, array2->element_type))
1188 return 0;
1189 if (array1->element_is_record != array2->element_is_record)
1190 return 0;
1191 if (array1->live_out != array2->live_out)
1192 return 0;
1193 if (array1->uniquely_defined != array2->uniquely_defined)
1194 return 0;
1195 if (array1->declared != array2->declared)
1196 return 0;
1197 if (array1->exposed != array2->exposed)
1198 return 0;
1200 return 1;
1203 /* Return 1 if the two pet_stmts are equivalent.
1205 int pet_stmt_is_equal(struct pet_stmt *stmt1, struct pet_stmt *stmt2)
1207 int i;
1209 if (!stmt1 || !stmt2)
1210 return 0;
1212 if (pet_loc_get_line(stmt1->loc) != pet_loc_get_line(stmt2->loc))
1213 return 0;
1214 if (!isl_set_is_equal(stmt1->domain, stmt2->domain))
1215 return 0;
1216 if (!pet_tree_is_equal(stmt1->body, stmt2->body))
1217 return 0;
1218 if (stmt1->n_arg != stmt2->n_arg)
1219 return 0;
1220 for (i = 0; i < stmt1->n_arg; ++i) {
1221 if (!pet_expr_is_equal(stmt1->args[i], stmt2->args[i]))
1222 return 0;
1225 return 1;
1228 /* Return 1 if the two pet_types are equivalent.
1230 * We only compare the names of the types since the exact representation
1231 * of the definition may depend on the version of clang being used.
1233 int pet_type_is_equal(struct pet_type *type1, struct pet_type *type2)
1235 if (!type1 || !type2)
1236 return 0;
1238 if (strcmp(type1->name, type2->name))
1239 return 0;
1241 return 1;
1244 /* Return 1 if the two pet_implications are equivalent.
1246 int pet_implication_is_equal(struct pet_implication *implication1,
1247 struct pet_implication *implication2)
1249 if (!implication1 || !implication2)
1250 return 0;
1252 if (implication1->satisfied != implication2->satisfied)
1253 return 0;
1254 if (!isl_map_is_equal(implication1->extension, implication2->extension))
1255 return 0;
1257 return 1;
1260 /* Return 1 if the two pet_independences are equivalent.
1262 int pet_independence_is_equal(struct pet_independence *independence1,
1263 struct pet_independence *independence2)
1265 if (!independence1 || !independence2)
1266 return 0;
1268 if (!isl_union_map_is_equal(independence1->filter,
1269 independence2->filter))
1270 return 0;
1271 if (!isl_union_set_is_equal(independence1->local, independence2->local))
1272 return 0;
1274 return 1;
1277 /* Return 1 if the two pet_scops are equivalent.
1279 int pet_scop_is_equal(struct pet_scop *scop1, struct pet_scop *scop2)
1281 int i;
1282 int equal;
1284 if (!scop1 || !scop2)
1285 return 0;
1287 if (!isl_set_is_equal(scop1->context, scop2->context))
1288 return 0;
1289 if (!isl_set_is_equal(scop1->context_value, scop2->context_value))
1290 return 0;
1291 equal = isl_schedule_plain_is_equal(scop1->schedule, scop2->schedule);
1292 if (equal < 0)
1293 return -1;
1294 if (!equal)
1295 return 0;
1297 if (scop1->n_type != scop2->n_type)
1298 return 0;
1299 for (i = 0; i < scop1->n_type; ++i)
1300 if (!pet_type_is_equal(scop1->types[i], scop2->types[i]))
1301 return 0;
1303 if (scop1->n_array != scop2->n_array)
1304 return 0;
1305 for (i = 0; i < scop1->n_array; ++i)
1306 if (!pet_array_is_equal(scop1->arrays[i], scop2->arrays[i]))
1307 return 0;
1309 if (scop1->n_stmt != scop2->n_stmt)
1310 return 0;
1311 for (i = 0; i < scop1->n_stmt; ++i)
1312 if (!pet_stmt_is_equal(scop1->stmts[i], scop2->stmts[i]))
1313 return 0;
1315 if (scop1->n_implication != scop2->n_implication)
1316 return 0;
1317 for (i = 0; i < scop1->n_implication; ++i)
1318 if (!pet_implication_is_equal(scop1->implications[i],
1319 scop2->implications[i]))
1320 return 0;
1322 if (scop1->n_independence != scop2->n_independence)
1323 return 0;
1324 for (i = 0; i < scop1->n_independence; ++i)
1325 if (!pet_independence_is_equal(scop1->independences[i],
1326 scop2->independences[i]))
1327 return 0;
1329 return 1;
1332 /* Does the set "extent" reference a virtual array, i.e.,
1333 * one with user pointer equal to NULL?
1334 * A virtual array does not have any members.
1336 static int extent_is_virtual_array(__isl_keep isl_set *extent)
1338 isl_id *id;
1339 int is_virtual;
1341 if (!isl_set_has_tuple_id(extent))
1342 return 0;
1343 if (isl_set_is_wrapping(extent))
1344 return 0;
1345 id = isl_set_get_tuple_id(extent);
1346 is_virtual = !isl_id_get_user(id);
1347 isl_id_free(id);
1349 return is_virtual;
1352 /* Intersect the initial dimensions of "array" with "domain", provided
1353 * that "array" represents a virtual array.
1355 * If "array" is virtual, then We take the preimage of "domain"
1356 * over the projection of the extent of "array" onto its initial dimensions
1357 * and intersect this extent with the result.
1359 static struct pet_array *virtual_array_intersect_domain_prefix(
1360 struct pet_array *array, __isl_take isl_set *domain)
1362 int n;
1363 isl_space *space;
1364 isl_multi_aff *ma;
1366 if (!array || !extent_is_virtual_array(array->extent)) {
1367 isl_set_free(domain);
1368 return array;
1371 space = isl_set_get_space(array->extent);
1372 n = isl_set_dim(domain, isl_dim_set);
1373 ma = pet_prefix_projection(space, n);
1374 domain = isl_set_preimage_multi_aff(domain, ma);
1376 array->extent = isl_set_intersect(array->extent, domain);
1377 if (!array->extent)
1378 return pet_array_free(array);
1380 return array;
1383 /* Intersect the initial dimensions of the domain of "stmt"
1384 * with "domain".
1386 * We take the preimage of "domain" over the projection of the
1387 * domain of "stmt" onto its initial dimensions and intersect
1388 * the domain of "stmt" with the result.
1390 static struct pet_stmt *stmt_intersect_domain_prefix(struct pet_stmt *stmt,
1391 __isl_take isl_set *domain)
1393 int n;
1394 isl_space *space;
1395 isl_multi_aff *ma;
1397 if (!stmt)
1398 goto error;
1400 space = isl_set_get_space(stmt->domain);
1401 n = isl_set_dim(domain, isl_dim_set);
1402 ma = pet_prefix_projection(space, n);
1403 domain = isl_set_preimage_multi_aff(domain, ma);
1405 stmt->domain = isl_set_intersect(stmt->domain, domain);
1406 if (!stmt->domain)
1407 return pet_stmt_free(stmt);
1409 return stmt;
1410 error:
1411 isl_set_free(domain);
1412 return pet_stmt_free(stmt);
1415 /* Intersect the initial dimensions of the domain of "implication"
1416 * with "domain".
1418 * We take the preimage of "domain" over the projection of the
1419 * domain of "implication" onto its initial dimensions and intersect
1420 * the domain of "implication" with the result.
1422 static struct pet_implication *implication_intersect_domain_prefix(
1423 struct pet_implication *implication, __isl_take isl_set *domain)
1425 int n;
1426 isl_space *space;
1427 isl_multi_aff *ma;
1429 if (!implication)
1430 goto error;
1432 space = isl_map_get_space(implication->extension);
1433 n = isl_set_dim(domain, isl_dim_set);
1434 ma = pet_prefix_projection(isl_space_domain(space), n);
1435 domain = isl_set_preimage_multi_aff(domain, ma);
1437 implication->extension =
1438 isl_map_intersect_domain(implication->extension, domain);
1439 if (!implication->extension)
1440 return pet_implication_free(implication);
1442 return implication;
1443 error:
1444 isl_set_free(domain);
1445 return pet_implication_free(implication);
1448 /* Intersect the initial dimensions of the domains in "scop" with "domain".
1450 * The extents of the virtual arrays match the iteration domains,
1451 * so if the iteration domain changes, we need to change those extents too.
1453 * The domain of the schedule is intersected with (i.e., replaced by)
1454 * the union of the updated iteration domains.
1456 struct pet_scop *pet_scop_intersect_domain_prefix(struct pet_scop *scop,
1457 __isl_take isl_set *domain)
1459 int i;
1461 if (!scop)
1462 goto error;
1464 for (i = 0; i < scop->n_array; ++i) {
1465 scop->arrays[i] = virtual_array_intersect_domain_prefix(
1466 scop->arrays[i], isl_set_copy(domain));
1467 if (!scop->arrays[i])
1468 goto error;
1471 for (i = 0; i < scop->n_stmt; ++i) {
1472 scop->stmts[i] = stmt_intersect_domain_prefix(scop->stmts[i],
1473 isl_set_copy(domain));
1474 if (!scop->stmts[i])
1475 goto error;
1478 for (i = 0; i < scop->n_implication; ++i) {
1479 scop->implications[i] =
1480 implication_intersect_domain_prefix(scop->implications[i],
1481 isl_set_copy(domain));
1482 if (!scop->implications[i])
1483 return pet_scop_free(scop);
1486 scop->schedule = isl_schedule_intersect_domain(scop->schedule,
1487 pet_scop_get_instance_set(scop));
1488 if (!scop->schedule)
1489 goto error;
1491 isl_set_free(domain);
1492 return scop;
1493 error:
1494 isl_set_free(domain);
1495 return pet_scop_free(scop);
1498 /* Update the context with respect to an embedding into a loop
1499 * with iteration domain "dom".
1500 * The input context lives in the same space as "dom".
1501 * The output context has the inner dimension removed.
1503 * An outer loop iterator value is invalid for the embedding if
1504 * any of the corresponding inner iterator values is invalid.
1505 * That is, an outer loop iterator value is valid only if all the corresponding
1506 * inner iterator values are valid.
1507 * We therefore compute the set of outer loop iterators l
1509 * forall i: dom(l,i) => valid(l,i)
1511 * or
1513 * forall i: not dom(l,i) or valid(l,i)
1515 * or
1517 * not exists i: dom(l,i) and not valid(l,i)
1519 * i.e.,
1521 * not exists i: (dom \ valid)(l,i)
1523 * If there are any unnamed parameters in "dom", then we consider
1524 * a parameter value to be valid if it is valid for any value of those
1525 * unnamed parameters. They are therefore projected out at the end.
1527 static __isl_give isl_set *context_embed(__isl_take isl_set *context,
1528 __isl_keep isl_set *dom)
1530 int pos;
1532 pos = isl_set_dim(context, isl_dim_set) - 1;
1533 context = isl_set_subtract(isl_set_copy(dom), context);
1534 context = isl_set_project_out(context, isl_dim_set, pos, 1);
1535 context = isl_set_complement(context);
1536 context = pet_nested_remove_from_set(context);
1538 return context;
1541 /* Internal data structure for outer_projection_mupa.
1543 * "n" is the number of outer dimensions onto which to project.
1544 * "res" collects the result.
1546 struct pet_outer_projection_data {
1547 int n;
1548 isl_union_pw_multi_aff *res;
1551 /* Create a function that maps "set" onto its outer data->n dimensions and
1552 * add it to data->res.
1554 static isl_stat add_outer_projection(__isl_take isl_set *set, void *user)
1556 struct pet_outer_projection_data *data = user;
1557 int dim;
1558 isl_space *space;
1559 isl_pw_multi_aff *pma;
1561 dim = isl_set_dim(set, isl_dim_set);
1562 space = isl_set_get_space(set);
1563 pma = isl_pw_multi_aff_project_out_map(space,
1564 isl_dim_set, data->n, dim - data->n);
1565 data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma);
1567 isl_set_free(set);
1569 return isl_stat_ok;
1572 /* Create and return a function that maps the sets in "domain"
1573 * onto their outer "n" dimensions.
1575 static __isl_give isl_multi_union_pw_aff *outer_projection_mupa(
1576 __isl_take isl_union_set *domain, int n)
1578 struct pet_outer_projection_data data;
1579 isl_space *space;
1581 space = isl_union_set_get_space(domain);
1582 data.n = n;
1583 data.res = isl_union_pw_multi_aff_empty(space);
1584 if (isl_union_set_foreach_set(domain, &add_outer_projection, &data) < 0)
1585 data.res = isl_union_pw_multi_aff_free(data.res);
1587 isl_union_set_free(domain);
1588 return isl_multi_union_pw_aff_from_union_pw_multi_aff(data.res);
1591 /* Embed "schedule" in a loop with schedule "prefix".
1592 * The domain of "prefix" corresponds to the outer dimensions
1593 * of the iteration domains.
1594 * We therefore construct a projection onto these outer dimensions,
1595 * compose it with "prefix" and then add the result as a band schedule.
1597 * If the domain of the schedule is empty, then there is no need
1598 * to insert any node.
1600 static __isl_give isl_schedule *schedule_embed(
1601 __isl_take isl_schedule *schedule, __isl_keep isl_multi_aff *prefix)
1603 int n;
1604 int empty;
1605 isl_union_set *domain;
1606 isl_multi_aff *ma;
1607 isl_multi_union_pw_aff *mupa;
1609 domain = isl_schedule_get_domain(schedule);
1610 empty = isl_union_set_is_empty(domain);
1611 if (empty < 0 || empty) {
1612 isl_union_set_free(domain);
1613 return empty < 0 ? isl_schedule_free(schedule) : schedule;
1616 n = isl_multi_aff_dim(prefix, isl_dim_in);
1617 mupa = outer_projection_mupa(domain, n);
1618 ma = isl_multi_aff_copy(prefix);
1619 mupa = isl_multi_union_pw_aff_apply_multi_aff(mupa, ma);
1620 schedule = isl_schedule_insert_partial_schedule(schedule, mupa);
1622 return schedule;
1625 /* Adjust the context and the schedule according to an embedding
1626 * in a loop with iteration domain "dom" and schedule "sched".
1628 struct pet_scop *pet_scop_embed(struct pet_scop *scop, __isl_take isl_set *dom,
1629 __isl_take isl_multi_aff *sched)
1631 if (!scop)
1632 goto error;
1634 scop->context = context_embed(scop->context, dom);
1635 if (!scop->context)
1636 goto error;
1638 scop->schedule = schedule_embed(scop->schedule, sched);
1639 if (!scop->schedule)
1640 goto error;
1642 isl_set_free(dom);
1643 isl_multi_aff_free(sched);
1644 return scop;
1645 error:
1646 isl_set_free(dom);
1647 isl_multi_aff_free(sched);
1648 return pet_scop_free(scop);
1651 /* Add extra conditions to scop->skip[type].
1653 * The new skip condition only holds if it held before
1654 * and the condition is true. It does not hold if it did not hold
1655 * before or the condition is false.
1657 * The skip condition is assumed to be an affine expression.
1659 static struct pet_scop *pet_scop_restrict_skip(struct pet_scop *scop,
1660 enum pet_skip type, __isl_keep isl_set *cond)
1662 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1663 isl_pw_aff *skip;
1664 isl_set *dom;
1666 if (!scop)
1667 return NULL;
1668 if (!ext->skip[type])
1669 return scop;
1671 if (!multi_pw_aff_is_affine(ext->skip[type]))
1672 isl_die(isl_multi_pw_aff_get_ctx(ext->skip[type]),
1673 isl_error_internal, "can only restrict affine skips",
1674 return pet_scop_free(scop));
1676 skip = isl_multi_pw_aff_get_pw_aff(ext->skip[type], 0);
1677 dom = isl_pw_aff_domain(isl_pw_aff_copy(skip));
1678 cond = isl_set_copy(cond);
1679 cond = isl_set_intersect(cond, isl_pw_aff_non_zero_set(skip));
1680 skip = indicator_function(cond, dom);
1681 isl_multi_pw_aff_free(ext->skip[type]);
1682 ext->skip[type] = isl_multi_pw_aff_from_pw_aff(skip);
1683 if (!ext->skip[type])
1684 return pet_scop_free(scop);
1686 return scop;
1689 /* Adjust the context and the skip conditions to the fact that
1690 * the scop was created in a context where "cond" holds.
1692 * An outer loop iterator or parameter value is valid for the result
1693 * if it was valid for the original scop and satisfies "cond" or if it does
1694 * not satisfy "cond" as in this case the scop is not executed
1695 * and the original constraints on these values are irrelevant.
1697 struct pet_scop *pet_scop_restrict(struct pet_scop *scop,
1698 __isl_take isl_set *cond)
1700 scop = pet_scop_restrict_skip(scop, pet_skip_now, cond);
1701 scop = pet_scop_restrict_skip(scop, pet_skip_later, cond);
1703 if (!scop)
1704 goto error;
1706 scop->context = isl_set_intersect(scop->context, isl_set_copy(cond));
1707 scop->context = isl_set_union(scop->context,
1708 isl_set_complement(isl_set_copy(cond)));
1709 scop->context = isl_set_coalesce(scop->context);
1710 scop->context = pet_nested_remove_from_set(scop->context);
1711 if (!scop->context)
1712 goto error;
1714 isl_set_free(cond);
1715 return scop;
1716 error:
1717 isl_set_free(cond);
1718 return pet_scop_free(scop);
1721 /* Insert an argument expression corresponding to "test" in front
1722 * of the list of arguments described by *n_arg and *args.
1724 static int args_insert_access(unsigned *n_arg, pet_expr ***args,
1725 __isl_keep isl_multi_pw_aff *test)
1727 int i;
1728 isl_ctx *ctx = isl_multi_pw_aff_get_ctx(test);
1730 if (!test)
1731 return -1;
1733 if (!*args) {
1734 *args = isl_calloc_array(ctx, pet_expr *, 1);
1735 if (!*args)
1736 return -1;
1737 } else {
1738 pet_expr **ext;
1739 ext = isl_calloc_array(ctx, pet_expr *, 1 + *n_arg);
1740 if (!ext)
1741 return -1;
1742 for (i = 0; i < *n_arg; ++i)
1743 ext[1 + i] = (*args)[i];
1744 free(*args);
1745 *args = ext;
1747 (*n_arg)++;
1748 (*args)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test));
1749 if (!(*args)[0])
1750 return -1;
1752 return 0;
1755 /* Look through the applications in "scop" for any that can be
1756 * applied to the filter expressed by "map" and "satisified".
1757 * If there is any, then apply it to "map" and return the result.
1758 * Otherwise, return "map".
1759 * "id" is the identifier of the virtual array.
1761 * We only introduce at most one implication for any given virtual array,
1762 * so we can apply the implication and return as soon as we find one.
1764 static __isl_give isl_map *apply_implications(struct pet_scop *scop,
1765 __isl_take isl_map *map, __isl_keep isl_id *id, int satisfied)
1767 int i;
1769 for (i = 0; i < scop->n_implication; ++i) {
1770 struct pet_implication *pi = scop->implications[i];
1771 isl_id *pi_id;
1773 if (pi->satisfied != satisfied)
1774 continue;
1775 pi_id = isl_map_get_tuple_id(pi->extension, isl_dim_in);
1776 isl_id_free(pi_id);
1777 if (pi_id != id)
1778 continue;
1780 return isl_map_apply_range(map, isl_map_copy(pi->extension));
1783 return map;
1786 /* Is the filter expressed by "test" and "satisfied" implied
1787 * by filter "pos" on "domain", with filter "expr", taking into
1788 * account the implications of "scop"?
1790 * For filter on domain implying that expressed by "test" and "satisfied",
1791 * the filter needs to be an access to the same (virtual) array as "test" and
1792 * the filter value needs to be equal to "satisfied".
1793 * Moreover, the filter access relation, possibly extended by
1794 * the implications in "scop" needs to contain "test".
1796 static int implies_filter(struct pet_scop *scop,
1797 __isl_keep isl_map *domain, int pos, __isl_keep pet_expr *expr,
1798 __isl_keep isl_map *test, int satisfied)
1800 isl_id *test_id, *arg_id;
1801 isl_val *val;
1802 int is_int;
1803 int s;
1804 int is_subset;
1805 isl_map *implied;
1807 if (expr->type != pet_expr_access)
1808 return 0;
1809 test_id = isl_map_get_tuple_id(test, isl_dim_out);
1810 arg_id = pet_expr_access_get_id(expr);
1811 isl_id_free(arg_id);
1812 isl_id_free(test_id);
1813 if (test_id != arg_id)
1814 return 0;
1815 val = isl_map_plain_get_val_if_fixed(domain, isl_dim_out, pos);
1816 is_int = isl_val_is_int(val);
1817 if (is_int)
1818 s = isl_val_get_num_si(val);
1819 isl_val_free(val);
1820 if (!val)
1821 return -1;
1822 if (!is_int)
1823 return 0;
1824 if (s != satisfied)
1825 return 0;
1827 implied = isl_map_from_multi_pw_aff(pet_expr_access_get_index(expr));
1828 implied = apply_implications(scop, implied, test_id, satisfied);
1829 is_subset = isl_map_is_subset(test, implied);
1830 isl_map_free(implied);
1832 return is_subset;
1835 /* Is the filter expressed by "test" and "satisfied" implied
1836 * by any of the filters on the domain of "stmt", taking into
1837 * account the implications of "scop"?
1839 static int filter_implied(struct pet_scop *scop,
1840 struct pet_stmt *stmt, __isl_keep isl_multi_pw_aff *test, int satisfied)
1842 int i;
1843 int implied;
1844 isl_map *domain;
1845 isl_map *test_map;
1847 if (!scop || !stmt || !test)
1848 return -1;
1849 if (scop->n_implication == 0)
1850 return 0;
1851 if (stmt->n_arg == 0)
1852 return 0;
1854 domain = isl_set_unwrap(isl_set_copy(stmt->domain));
1855 test_map = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test));
1857 implied = 0;
1858 for (i = 0; i < stmt->n_arg; ++i) {
1859 implied = implies_filter(scop, domain, i, stmt->args[i],
1860 test_map, satisfied);
1861 if (implied < 0 || implied)
1862 break;
1865 isl_map_free(test_map);
1866 isl_map_free(domain);
1867 return implied;
1870 /* Make the statement "stmt" depend on the value of "test"
1871 * being equal to "satisfied" by adjusting stmt->domain.
1873 * The domain of "test" corresponds to the (zero or more) outer dimensions
1874 * of the iteration domain.
1876 * We first extend "test" to apply to the entire iteration domain and
1877 * then check if the filter that we are about to add is implied
1878 * by any of the current filters, possibly taking into account
1879 * the implications in "scop". If so, we leave "stmt" untouched and return.
1881 * Otherwise, we insert an argument corresponding to a read to "test"
1882 * from the iteration domain of "stmt" in front of the list of arguments.
1883 * We also insert a corresponding output dimension in the wrapped
1884 * map contained in stmt->domain, with value set to "satisfied".
1886 static struct pet_stmt *stmt_filter(struct pet_scop *scop,
1887 struct pet_stmt *stmt, __isl_take isl_multi_pw_aff *test, int satisfied)
1889 int i;
1890 int implied;
1891 isl_id *id;
1892 isl_pw_multi_aff *pma;
1893 isl_multi_aff *add_dom;
1894 isl_space *space;
1895 isl_local_space *ls;
1896 int n_test_dom;
1898 if (!stmt || !test)
1899 goto error;
1901 space = pet_stmt_get_space(stmt);
1902 n_test_dom = isl_multi_pw_aff_dim(test, isl_dim_in);
1903 space = isl_space_from_domain(space);
1904 space = isl_space_add_dims(space, isl_dim_out, n_test_dom);
1905 add_dom = isl_multi_aff_zero(isl_space_copy(space));
1906 ls = isl_local_space_from_space(isl_space_domain(space));
1907 for (i = 0; i < n_test_dom; ++i) {
1908 isl_aff *aff;
1909 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
1910 isl_dim_set, i);
1911 add_dom = isl_multi_aff_set_aff(add_dom, i, aff);
1913 isl_local_space_free(ls);
1914 test = isl_multi_pw_aff_pullback_multi_aff(test, add_dom);
1916 implied = filter_implied(scop, stmt, test, satisfied);
1917 if (implied < 0)
1918 goto error;
1919 if (implied) {
1920 isl_multi_pw_aff_free(test);
1921 return stmt;
1924 id = isl_multi_pw_aff_get_tuple_id(test, isl_dim_out);
1925 pma = pet_filter_insert_pma(isl_set_get_space(stmt->domain),
1926 id, satisfied);
1927 stmt->domain = isl_set_preimage_pw_multi_aff(stmt->domain, pma);
1929 if (args_insert_access(&stmt->n_arg, &stmt->args, test) < 0)
1930 goto error;
1932 isl_multi_pw_aff_free(test);
1933 return stmt;
1934 error:
1935 isl_multi_pw_aff_free(test);
1936 return pet_stmt_free(stmt);
1939 /* Does "scop" have a skip condition of the given "type"?
1941 int pet_scop_has_skip(struct pet_scop *scop, enum pet_skip type)
1943 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1945 if (!scop)
1946 return -1;
1947 return ext->skip[type] != NULL;
1950 /* Does "scop" have a skip condition of the given "type" that
1951 * is an affine expression?
1953 int pet_scop_has_affine_skip(struct pet_scop *scop, enum pet_skip type)
1955 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1957 if (!scop)
1958 return -1;
1959 if (!ext->skip[type])
1960 return 0;
1961 return multi_pw_aff_is_affine(ext->skip[type]);
1964 /* Does "scop" have a skip condition of the given "type" that
1965 * is not an affine expression?
1967 int pet_scop_has_var_skip(struct pet_scop *scop, enum pet_skip type)
1969 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1970 int aff;
1972 if (!scop)
1973 return -1;
1974 if (!ext->skip[type])
1975 return 0;
1976 aff = multi_pw_aff_is_affine(ext->skip[type]);
1977 if (aff < 0)
1978 return -1;
1979 return !aff;
1982 /* Does "scop" have a skip condition of the given "type" that
1983 * is affine and holds on the entire domain?
1985 int pet_scop_has_universal_skip(struct pet_scop *scop, enum pet_skip type)
1987 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1988 isl_pw_aff *pa;
1989 isl_set *set;
1990 int is_aff;
1991 int is_univ;
1993 is_aff = pet_scop_has_affine_skip(scop, type);
1994 if (is_aff < 0 || !is_aff)
1995 return is_aff;
1997 pa = isl_multi_pw_aff_get_pw_aff(ext->skip[type], 0);
1998 set = isl_pw_aff_non_zero_set(pa);
1999 is_univ = isl_set_plain_is_universe(set);
2000 isl_set_free(set);
2002 return is_univ;
2005 /* Replace scop->skip[type] by "skip".
2007 struct pet_scop *pet_scop_set_skip(struct pet_scop *scop,
2008 enum pet_skip type, __isl_take isl_multi_pw_aff *skip)
2010 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2012 if (!scop || !skip)
2013 goto error;
2015 isl_multi_pw_aff_free(ext->skip[type]);
2016 ext->skip[type] = skip;
2018 return scop;
2019 error:
2020 isl_multi_pw_aff_free(skip);
2021 return pet_scop_free(scop);
2024 /* Return a copy of scop->skip[type].
2026 __isl_give isl_multi_pw_aff *pet_scop_get_skip(struct pet_scop *scop,
2027 enum pet_skip type)
2029 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2031 if (!scop)
2032 return NULL;
2034 return isl_multi_pw_aff_copy(ext->skip[type]);
2037 /* Assuming scop->skip[type] is an affine expression,
2038 * return the constraints on the outer loop domain for which the skip condition
2039 * holds.
2041 __isl_give isl_set *pet_scop_get_affine_skip_domain(struct pet_scop *scop,
2042 enum pet_skip type)
2044 isl_multi_pw_aff *skip;
2045 isl_pw_aff *pa;
2047 skip = pet_scop_get_skip(scop, type);
2048 pa = isl_multi_pw_aff_get_pw_aff(skip, 0);
2049 isl_multi_pw_aff_free(skip);
2050 return isl_pw_aff_non_zero_set(pa);
2053 /* Return the identifier of the variable that is accessed by
2054 * the skip condition of the given type.
2056 * The skip condition is assumed not to be an affine condition.
2058 __isl_give isl_id *pet_scop_get_skip_id(struct pet_scop *scop,
2059 enum pet_skip type)
2061 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2063 if (!scop)
2064 return NULL;
2066 return isl_multi_pw_aff_get_tuple_id(ext->skip[type], isl_dim_out);
2069 /* Return an access pet_expr corresponding to the skip condition
2070 * of the given type.
2072 __isl_give pet_expr *pet_scop_get_skip_expr(struct pet_scop *scop,
2073 enum pet_skip type)
2075 return pet_expr_from_index(pet_scop_get_skip(scop, type));
2078 /* Drop the skip condition scop->skip[type].
2080 void pet_scop_reset_skip(struct pet_scop *scop, enum pet_skip type)
2082 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2084 if (!scop)
2085 return;
2087 isl_multi_pw_aff_free(ext->skip[type]);
2088 ext->skip[type] = NULL;
2091 /* Drop all skip conditions on "scop".
2093 struct pet_scop *pet_scop_reset_skips(struct pet_scop *scop)
2095 pet_scop_reset_skip(scop, pet_skip_now);
2096 pet_scop_reset_skip(scop, pet_skip_later);
2098 return scop;
2101 /* Make the skip condition (if any) depend on the value of "test" being
2102 * equal to "satisfied".
2104 * We only support the case where the original skip condition is universal,
2105 * i.e., where skipping is unconditional, and where satisfied == 1.
2106 * In this case, the skip condition is changed to skip only when
2107 * "test" is equal to one.
2109 static struct pet_scop *pet_scop_filter_skip(struct pet_scop *scop,
2110 enum pet_skip type, __isl_keep isl_multi_pw_aff *test, int satisfied)
2112 int is_univ = 0;
2114 if (!scop)
2115 return NULL;
2116 if (!pet_scop_has_skip(scop, type))
2117 return scop;
2119 if (satisfied)
2120 is_univ = pet_scop_has_universal_skip(scop, type);
2121 if (is_univ < 0)
2122 return pet_scop_free(scop);
2123 if (satisfied && is_univ) {
2124 isl_multi_pw_aff *skip;
2125 skip = isl_multi_pw_aff_copy(test);
2126 scop = pet_scop_set_skip(scop, type, skip);
2127 if (!scop)
2128 return NULL;
2129 } else {
2130 isl_die(isl_multi_pw_aff_get_ctx(test), isl_error_internal,
2131 "skip expression cannot be filtered",
2132 return pet_scop_free(scop));
2135 return scop;
2138 /* Make all statements in "scop" depend on the value of "test"
2139 * being equal to "satisfied" by adjusting their domains.
2141 struct pet_scop *pet_scop_filter(struct pet_scop *scop,
2142 __isl_take isl_multi_pw_aff *test, int satisfied)
2144 int i;
2146 scop = pet_scop_filter_skip(scop, pet_skip_now, test, satisfied);
2147 scop = pet_scop_filter_skip(scop, pet_skip_later, test, satisfied);
2149 if (!scop || !test)
2150 goto error;
2152 for (i = 0; i < scop->n_stmt; ++i) {
2153 scop->stmts[i] = stmt_filter(scop, scop->stmts[i],
2154 isl_multi_pw_aff_copy(test), satisfied);
2155 if (!scop->stmts[i])
2156 goto error;
2159 isl_multi_pw_aff_free(test);
2160 return scop;
2161 error:
2162 isl_multi_pw_aff_free(test);
2163 return pet_scop_free(scop);
2166 /* Add the parameters of the access expression "expr" to "space".
2168 static int access_collect_params(__isl_keep pet_expr *expr, void *user)
2170 isl_space *expr_space;
2171 isl_space **space = user;
2173 expr_space = pet_expr_access_get_parameter_space(expr);
2174 *space = isl_space_align_params(*space, expr_space);
2176 return *space ? 0 : -1;
2179 /* Add all parameters in "stmt" to "space" and return the result.
2181 static __isl_give isl_space *stmt_collect_params(struct pet_stmt *stmt,
2182 __isl_take isl_space *space)
2184 int i;
2186 if (!stmt)
2187 return isl_space_free(space);
2189 space = isl_space_align_params(space, isl_set_get_space(stmt->domain));
2190 for (i = 0; i < stmt->n_arg; ++i)
2191 if (pet_expr_foreach_access_expr(stmt->args[i],
2192 &access_collect_params, &space) < 0)
2193 space = isl_space_free(space);
2194 if (pet_tree_foreach_access_expr(stmt->body, &access_collect_params,
2195 &space) < 0)
2196 space = isl_space_free(space);
2198 return space;
2201 /* Add all parameters in "array" to "space" and return the result.
2203 static __isl_give isl_space *array_collect_params(struct pet_array *array,
2204 __isl_take isl_space *space)
2206 if (!array)
2207 return isl_space_free(space);
2209 space = isl_space_align_params(space,
2210 isl_set_get_space(array->context));
2211 space = isl_space_align_params(space, isl_set_get_space(array->extent));
2213 return space;
2216 /* Add all parameters in "independence" to "space" and return the result.
2218 static __isl_give isl_space *independence_collect_params(
2219 struct pet_independence *independence, __isl_take isl_space *space)
2221 if (!independence)
2222 return isl_space_free(space);
2224 space = isl_space_align_params(space,
2225 isl_union_map_get_space(independence->filter));
2226 space = isl_space_align_params(space,
2227 isl_union_set_get_space(independence->local));
2229 return space;
2232 /* Collect all parameters in "scop" in a parameter space and return the result.
2234 static __isl_give isl_space *scop_collect_params(struct pet_scop *scop)
2236 isl_space *space;
2237 int i;
2239 if (!scop)
2240 return NULL;
2242 space = isl_set_get_space(scop->context);
2244 for (i = 0; i < scop->n_array; ++i)
2245 space = array_collect_params(scop->arrays[i], space);
2247 for (i = 0; i < scop->n_stmt; ++i)
2248 space = stmt_collect_params(scop->stmts[i], space);
2250 for (i = 0; i < scop->n_independence; ++i)
2251 space = independence_collect_params(scop->independences[i],
2252 space);
2254 return space;
2257 /* Add all parameters in "space" to the domain and
2258 * all access relations in "stmt".
2260 static struct pet_stmt *stmt_propagate_params(struct pet_stmt *stmt,
2261 __isl_take isl_space *space)
2263 int i;
2265 if (!stmt)
2266 goto error;
2268 stmt->domain = isl_set_align_params(stmt->domain,
2269 isl_space_copy(space));
2271 for (i = 0; i < stmt->n_arg; ++i) {
2272 stmt->args[i] = pet_expr_align_params(stmt->args[i],
2273 isl_space_copy(space));
2274 if (!stmt->args[i])
2275 goto error;
2277 stmt->body = pet_tree_align_params(stmt->body, isl_space_copy(space));
2279 if (!stmt->domain || !stmt->body)
2280 goto error;
2282 isl_space_free(space);
2283 return stmt;
2284 error:
2285 isl_space_free(space);
2286 return pet_stmt_free(stmt);
2289 /* Add all parameters in "space" to "array".
2291 static struct pet_array *array_propagate_params(struct pet_array *array,
2292 __isl_take isl_space *space)
2294 if (!array)
2295 goto error;
2297 array->context = isl_set_align_params(array->context,
2298 isl_space_copy(space));
2299 array->extent = isl_set_align_params(array->extent,
2300 isl_space_copy(space));
2301 if (array->value_bounds) {
2302 array->value_bounds = isl_set_align_params(array->value_bounds,
2303 isl_space_copy(space));
2304 if (!array->value_bounds)
2305 goto error;
2308 if (!array->context || !array->extent)
2309 goto error;
2311 isl_space_free(space);
2312 return array;
2313 error:
2314 isl_space_free(space);
2315 return pet_array_free(array);
2318 /* Add all parameters in "space" to "independence".
2320 static struct pet_independence *independence_propagate_params(
2321 struct pet_independence *independence, __isl_take isl_space *space)
2323 if (!independence)
2324 goto error;
2326 independence->filter = isl_union_map_align_params(independence->filter,
2327 isl_space_copy(space));
2328 independence->local = isl_union_set_align_params(independence->local,
2329 isl_space_copy(space));
2330 if (!independence->filter || !independence->local)
2331 goto error;
2333 isl_space_free(space);
2334 return independence;
2335 error:
2336 isl_space_free(space);
2337 return pet_independence_free(independence);
2340 /* Add all parameters in "space" to "scop".
2342 static struct pet_scop *scop_propagate_params(struct pet_scop *scop,
2343 __isl_take isl_space *space)
2345 int i;
2347 if (!scop)
2348 goto error;
2350 scop->context = isl_set_align_params(scop->context,
2351 isl_space_copy(space));
2352 scop->schedule = isl_schedule_align_params(scop->schedule,
2353 isl_space_copy(space));
2354 if (!scop->context || !scop->schedule)
2355 goto error;
2357 for (i = 0; i < scop->n_array; ++i) {
2358 scop->arrays[i] = array_propagate_params(scop->arrays[i],
2359 isl_space_copy(space));
2360 if (!scop->arrays[i])
2361 goto error;
2364 for (i = 0; i < scop->n_stmt; ++i) {
2365 scop->stmts[i] = stmt_propagate_params(scop->stmts[i],
2366 isl_space_copy(space));
2367 if (!scop->stmts[i])
2368 goto error;
2371 for (i = 0; i < scop->n_independence; ++i) {
2372 scop->independences[i] = independence_propagate_params(
2373 scop->independences[i], isl_space_copy(space));
2374 if (!scop->independences[i])
2375 goto error;
2378 isl_space_free(space);
2379 return scop;
2380 error:
2381 isl_space_free(space);
2382 return pet_scop_free(scop);
2385 /* Update all isl_sets and isl_maps in "scop" such that they all
2386 * have the same parameters.
2388 struct pet_scop *pet_scop_align_params(struct pet_scop *scop)
2390 isl_space *space;
2392 if (!scop)
2393 return NULL;
2395 space = scop_collect_params(scop);
2397 scop = scop_propagate_params(scop, space);
2399 return scop;
2402 /* Add the access relation of the give "type" of the access expression "expr"
2403 * to "accesses" and return the result.
2404 * The domain of the access relation is intersected with "domain".
2405 * If "tag" is set, then the access relation is tagged with
2406 * the corresponding reference identifier.
2408 static __isl_give isl_union_map *expr_collect_access(__isl_keep pet_expr *expr,
2409 enum pet_expr_access_type type, int tag,
2410 __isl_take isl_union_map *accesses, __isl_keep isl_union_set *domain)
2412 isl_union_map *access;
2414 access = pet_expr_access_get_access(expr, type);
2415 access = isl_union_map_intersect_domain(access,
2416 isl_union_set_copy(domain));
2417 if (tag)
2418 access = pet_expr_tag_access(expr, access);
2419 return isl_union_map_union(accesses, access);
2422 /* Internal data structure for expr_collect_accesses.
2424 * "type" is the type of accesses we want to collect.
2425 * "tag" is set if the access relations should be tagged with
2426 * the corresponding reference identifiers.
2427 * "domain" are constraints on the domain of the access relations.
2428 * "accesses" collects the results.
2430 struct pet_expr_collect_accesses_data {
2431 enum pet_expr_access_type type;
2432 int tag;
2433 isl_union_set *domain;
2435 isl_union_map *accesses;
2438 /* Add the access relation of the access expression "expr"
2439 * to data->accesses if the access expression is a read and we are collecting
2440 * reads and/or it is a write and we are collecting writes.
2441 * The domains of the access relations are intersected with data->domain.
2442 * If data->tag is set, then the access relations are tagged with
2443 * the corresponding reference identifiers.
2445 * If data->type is pet_expr_access_must_write, then we only add
2446 * the accesses that are definitely performed. Otherwise, we add
2447 * all potential accesses.
2448 * In particular, if the access has any arguments, then in case of
2449 * pet_expr_access_must_write we currently skip the access completely.
2450 * In other cases, we project out the values of the access arguments.
2452 static int expr_collect_accesses(__isl_keep pet_expr *expr, void *user)
2454 struct pet_expr_collect_accesses_data *data = user;
2455 int i;
2457 if (!expr)
2458 return -1;
2460 if (pet_expr_is_affine(expr))
2461 return 0;
2462 if (data->type == pet_expr_access_must_write && expr->n_arg != 0)
2463 return 0;
2465 if ((data->type == pet_expr_access_may_read && expr->acc.read) ||
2466 ((data->type == pet_expr_access_may_write ||
2467 data->type == pet_expr_access_must_write) && expr->acc.write))
2468 data->accesses = expr_collect_access(expr,
2469 data->type, data->tag,
2470 data->accesses, data->domain);
2472 return data->accesses ? 0 : -1;
2475 /* Collect and return all access relations of the given "type" in "stmt".
2476 * If "tag" is set, then the access relations are tagged with
2477 * the corresponding reference identifiers.
2478 * If "type" is pet_expr_access_killed, then "stmt" is a kill statement and
2479 * we simply add the argument of the kill operation.
2481 * If we are looking for definite accesses (pet_expr_access_must_write
2482 * or pet_expr_access_killed), then we only add the accesses that are
2483 * definitely performed. Otherwise, we add all potential accesses.
2484 * In particular, if the statement has any arguments, then if we are looking
2485 * for definite accesses we currently skip the statement completely. Othewise,
2486 * we project out the values of the statement arguments.
2487 * If the statement body is not an expression tree, then we cannot
2488 * know for sure if/when the accesses inside the tree are performed.
2489 * We therefore ignore such statements when we are looking for
2490 * definite accesses.
2492 static __isl_give isl_union_map *stmt_collect_accesses(struct pet_stmt *stmt,
2493 enum pet_expr_access_type type, int tag, __isl_take isl_space *dim)
2495 struct pet_expr_collect_accesses_data data = { type, tag };
2496 int must;
2497 isl_set *domain;
2499 if (!stmt)
2500 return NULL;
2502 data.accesses = isl_union_map_empty(dim);
2504 if (type == pet_expr_access_must_write ||
2505 type == pet_expr_access_killed)
2506 must = 1;
2507 else
2508 must = 0;
2510 if (must && stmt->n_arg > 0)
2511 return data.accesses;
2512 if (must && pet_tree_get_type(stmt->body) != pet_tree_expr)
2513 return data.accesses;
2515 domain = drop_arguments(isl_set_copy(stmt->domain));
2516 data.domain = isl_union_set_from_set(domain);
2518 if (type == pet_expr_access_killed) {
2519 pet_expr *body, *arg;
2521 body = pet_tree_expr_get_expr(stmt->body);
2522 arg = pet_expr_get_arg(body, 0);
2523 data.accesses = expr_collect_access(arg,
2524 pet_expr_access_killed, tag,
2525 data.accesses, data.domain);
2526 pet_expr_free(arg);
2527 pet_expr_free(body);
2528 } else if (pet_tree_foreach_access_expr(stmt->body,
2529 &expr_collect_accesses, &data) < 0)
2530 data.accesses = isl_union_map_free(data.accesses);
2532 isl_union_set_free(data.domain);
2534 return data.accesses;
2537 /* Is "stmt" an assignment statement?
2539 int pet_stmt_is_assign(struct pet_stmt *stmt)
2541 if (!stmt)
2542 return 0;
2543 return pet_tree_is_assign(stmt->body);
2546 /* Is "stmt" a kill statement?
2548 int pet_stmt_is_kill(struct pet_stmt *stmt)
2550 if (!stmt)
2551 return 0;
2552 return pet_tree_is_kill(stmt->body);
2555 /* Is "stmt" an assume statement?
2557 int pet_stmt_is_assume(struct pet_stmt *stmt)
2559 if (!stmt)
2560 return 0;
2561 return pet_tree_is_assume(stmt->body);
2564 /* Helper function to add a domain gisted copy of "map" (wrt "set") to "umap".
2566 static __isl_give isl_union_map *add_gisted(__isl_take isl_union_map *umap,
2567 __isl_keep isl_map *map, __isl_keep isl_set *set)
2569 isl_map *gist;
2571 gist = isl_map_copy(map);
2572 gist = isl_map_gist_domain(gist, isl_set_copy(set));
2573 return isl_union_map_add_map(umap, gist);
2576 /* Compute a mapping from all arrays (of structs) in scop
2577 * to their members.
2579 * If "from_outermost" is set, then the domain only consists
2580 * of outermost arrays.
2581 * If "to_innermost" is set, then the range only consists
2582 * of innermost arrays.
2584 static __isl_give isl_union_map *compute_to_inner(struct pet_scop *scop,
2585 int from_outermost, int to_innermost)
2587 int i;
2588 isl_union_map *to_inner;
2590 if (!scop)
2591 return NULL;
2593 to_inner = isl_union_map_empty(isl_set_get_space(scop->context));
2595 for (i = 0; i < scop->n_array; ++i) {
2596 struct pet_array *array = scop->arrays[i];
2597 isl_set *set;
2598 isl_map *map;
2600 if (to_innermost && array->element_is_record)
2601 continue;
2603 set = isl_set_copy(array->extent);
2604 map = isl_set_identity(isl_set_copy(set));
2606 while (set && isl_set_is_wrapping(set)) {
2607 isl_id *id;
2608 isl_map *wrapped;
2610 if (!from_outermost)
2611 to_inner = add_gisted(to_inner, map, set);
2613 id = isl_set_get_tuple_id(set);
2614 wrapped = isl_set_unwrap(set);
2615 wrapped = isl_map_domain_map(wrapped);
2616 wrapped = isl_map_set_tuple_id(wrapped, isl_dim_in, id);
2617 map = isl_map_apply_domain(map, wrapped);
2618 set = isl_map_domain(isl_map_copy(map));
2621 map = isl_map_gist_domain(map, set);
2622 to_inner = isl_union_map_add_map(to_inner, map);
2625 return to_inner;
2628 /* Compute a mapping from all arrays (of structs) in scop
2629 * to their innermost arrays.
2631 * In particular, for each array of a primitive type, the result
2632 * contains the identity mapping on that array.
2633 * For each array involving member accesses, the result
2634 * contains a mapping from the elements of any intermediate array of structs
2635 * to all corresponding elements of the innermost nested arrays.
2637 static __isl_give isl_union_map *pet_scop_compute_any_to_inner(
2638 struct pet_scop *scop)
2640 return compute_to_inner(scop, 0, 1);
2643 /* Compute a mapping from all outermost arrays (of structs) in scop
2644 * to their innermost members.
2646 __isl_give isl_union_map *pet_scop_compute_outer_to_inner(struct pet_scop *scop)
2648 return compute_to_inner(scop, 1, 1);
2651 /* Compute a mapping from all outermost arrays (of structs) in scop
2652 * to their members, including the outermost arrays themselves.
2654 __isl_give isl_union_map *pet_scop_compute_outer_to_any(struct pet_scop *scop)
2656 return compute_to_inner(scop, 1, 0);
2659 /* Collect and return all access relations of the given "type" in "scop".
2660 * If "type" is pet_expr_access_killed, then we only add the arguments of
2661 * kill operations.
2662 * If we are looking for definite accesses (pet_expr_access_must_write
2663 * or pet_expr_access_killed), then we only add the accesses that are
2664 * definitely performed. Otherwise, we add all potential accesses.
2665 * If "tag" is set, then the access relations are tagged with
2666 * the corresponding reference identifiers.
2667 * For accesses to structures, the returned access relation accesses
2668 * all individual fields in the structures.
2670 static __isl_give isl_union_map *scop_collect_accesses(struct pet_scop *scop,
2671 enum pet_expr_access_type type, int tag)
2673 int i;
2674 isl_union_map *accesses;
2675 isl_union_set *arrays;
2676 isl_union_map *to_inner;
2678 if (!scop)
2679 return NULL;
2681 accesses = isl_union_map_empty(isl_set_get_space(scop->context));
2683 for (i = 0; i < scop->n_stmt; ++i) {
2684 struct pet_stmt *stmt = scop->stmts[i];
2685 isl_union_map *accesses_i;
2686 isl_space *space;
2688 if (type == pet_expr_access_killed && !pet_stmt_is_kill(stmt))
2689 continue;
2691 space = isl_set_get_space(scop->context);
2692 accesses_i = stmt_collect_accesses(stmt, type, tag, space);
2693 accesses = isl_union_map_union(accesses, accesses_i);
2696 arrays = isl_union_set_empty(isl_union_map_get_space(accesses));
2697 for (i = 0; i < scop->n_array; ++i) {
2698 isl_set *extent = isl_set_copy(scop->arrays[i]->extent);
2699 arrays = isl_union_set_add_set(arrays, extent);
2701 accesses = isl_union_map_intersect_range(accesses, arrays);
2703 to_inner = pet_scop_compute_any_to_inner(scop);
2704 accesses = isl_union_map_apply_range(accesses, to_inner);
2706 return accesses;
2709 /* Return the potential read access relation.
2711 __isl_give isl_union_map *pet_scop_get_may_reads(struct pet_scop *scop)
2713 return scop_collect_accesses(scop, pet_expr_access_may_read, 0);
2716 /* Return the potential write access relation.
2718 __isl_give isl_union_map *pet_scop_get_may_writes(struct pet_scop *scop)
2720 return scop_collect_accesses(scop, pet_expr_access_may_write, 0);
2723 /* Return the definite write access relation.
2725 __isl_give isl_union_map *pet_scop_get_must_writes(struct pet_scop *scop)
2727 return scop_collect_accesses(scop, pet_expr_access_must_write, 0);
2730 /* Return the definite kill access relation.
2732 __isl_give isl_union_map *pet_scop_get_must_kills(struct pet_scop *scop)
2734 return scop_collect_accesses(scop, pet_expr_access_killed, 0);
2737 /* Return the tagged potential read access relation.
2739 __isl_give isl_union_map *pet_scop_get_tagged_may_reads(
2740 struct pet_scop *scop)
2742 return scop_collect_accesses(scop, pet_expr_access_may_read, 1);
2745 /* Return the tagged potential write access relation.
2747 __isl_give isl_union_map *pet_scop_get_tagged_may_writes(
2748 struct pet_scop *scop)
2750 return scop_collect_accesses(scop, pet_expr_access_may_write, 1);
2753 /* Return the tagged definite write access relation.
2755 __isl_give isl_union_map *pet_scop_get_tagged_must_writes(
2756 struct pet_scop *scop)
2758 return scop_collect_accesses(scop, pet_expr_access_must_write, 1);
2761 /* Return the tagged definite kill access relation.
2763 __isl_give isl_union_map *pet_scop_get_tagged_must_kills(
2764 struct pet_scop *scop)
2766 return scop_collect_accesses(scop, pet_expr_access_killed, 1);
2769 /* Collect and return the set of all statement instances in "scop".
2771 __isl_give isl_union_set *pet_scop_get_instance_set(struct pet_scop *scop)
2773 int i;
2774 isl_set *domain_i;
2775 isl_union_set *domain;
2777 if (!scop)
2778 return NULL;
2780 domain = isl_union_set_empty(isl_set_get_space(scop->context));
2782 for (i = 0; i < scop->n_stmt; ++i) {
2783 domain_i = isl_set_copy(scop->stmts[i]->domain);
2784 if (scop->stmts[i]->n_arg > 0)
2785 domain_i = isl_map_domain(isl_set_unwrap(domain_i));
2786 domain = isl_union_set_add_set(domain, domain_i);
2789 return domain;
2792 /* Return the context of "scop".
2794 __isl_give isl_set *pet_scop_get_context(__isl_keep pet_scop *scop)
2796 if (!scop)
2797 return NULL;
2799 return isl_set_copy(scop->context);
2802 /* Return the schedule of "scop".
2804 __isl_give isl_schedule *pet_scop_get_schedule(__isl_keep pet_scop *scop)
2806 if (!scop)
2807 return NULL;
2809 return isl_schedule_copy(scop->schedule);
2812 /* Add a reference identifier to all access expressions in "stmt".
2813 * "n_ref" points to an integer that contains the sequence number
2814 * of the next reference.
2816 static struct pet_stmt *stmt_add_ref_ids(struct pet_stmt *stmt, int *n_ref)
2818 int i;
2820 if (!stmt)
2821 return NULL;
2823 for (i = 0; i < stmt->n_arg; ++i) {
2824 stmt->args[i] = pet_expr_add_ref_ids(stmt->args[i], n_ref);
2825 if (!stmt->args[i])
2826 return pet_stmt_free(stmt);
2829 stmt->body = pet_tree_add_ref_ids(stmt->body, n_ref);
2830 if (!stmt->body)
2831 return pet_stmt_free(stmt);
2833 return stmt;
2836 /* Add a reference identifier to all access expressions in "scop".
2838 struct pet_scop *pet_scop_add_ref_ids(struct pet_scop *scop)
2840 int i;
2841 int n_ref;
2843 if (!scop)
2844 return NULL;
2846 n_ref = 0;
2847 for (i = 0; i < scop->n_stmt; ++i) {
2848 scop->stmts[i] = stmt_add_ref_ids(scop->stmts[i], &n_ref);
2849 if (!scop->stmts[i])
2850 return pet_scop_free(scop);
2853 return scop;
2856 /* Reset the user pointer on all parameter ids in "array".
2858 static struct pet_array *array_anonymize(struct pet_array *array)
2860 if (!array)
2861 return NULL;
2863 array->context = isl_set_reset_user(array->context);
2864 array->extent = isl_set_reset_user(array->extent);
2865 if (!array->context || !array->extent)
2866 return pet_array_free(array);
2868 return array;
2871 /* Reset the user pointer on all parameter and tuple ids in "stmt".
2873 static struct pet_stmt *stmt_anonymize(struct pet_stmt *stmt)
2875 int i;
2876 isl_space *space;
2877 isl_set *domain;
2879 if (!stmt)
2880 return NULL;
2882 stmt->domain = isl_set_reset_user(stmt->domain);
2883 if (!stmt->domain)
2884 return pet_stmt_free(stmt);
2886 for (i = 0; i < stmt->n_arg; ++i) {
2887 stmt->args[i] = pet_expr_anonymize(stmt->args[i]);
2888 if (!stmt->args[i])
2889 return pet_stmt_free(stmt);
2892 stmt->body = pet_tree_anonymize(stmt->body);
2893 if (!stmt->body)
2894 return pet_stmt_free(stmt);
2896 return stmt;
2899 /* Reset the user pointer on the tuple ids and all parameter ids
2900 * in "implication".
2902 static struct pet_implication *implication_anonymize(
2903 struct pet_implication *implication)
2905 if (!implication)
2906 return NULL;
2908 implication->extension = isl_map_reset_user(implication->extension);
2909 if (!implication->extension)
2910 return pet_implication_free(implication);
2912 return implication;
2915 /* Reset the user pointer on the tuple ids and all parameter ids
2916 * in "independence".
2918 static struct pet_independence *independence_anonymize(
2919 struct pet_independence *independence)
2921 if (!independence)
2922 return NULL;
2924 independence->filter = isl_union_map_reset_user(independence->filter);
2925 independence->local = isl_union_set_reset_user(independence->local);
2926 if (!independence->filter || !independence->local)
2927 return pet_independence_free(independence);
2929 return independence;
2932 /* Reset the user pointer on all parameter and tuple ids in "scop".
2934 struct pet_scop *pet_scop_anonymize(struct pet_scop *scop)
2936 int i;
2938 if (!scop)
2939 return NULL;
2941 scop->context = isl_set_reset_user(scop->context);
2942 scop->context_value = isl_set_reset_user(scop->context_value);
2943 scop->schedule = isl_schedule_reset_user(scop->schedule);
2944 if (!scop->context || !scop->context_value || !scop->schedule)
2945 return pet_scop_free(scop);
2947 for (i = 0; i < scop->n_array; ++i) {
2948 scop->arrays[i] = array_anonymize(scop->arrays[i]);
2949 if (!scop->arrays[i])
2950 return pet_scop_free(scop);
2953 for (i = 0; i < scop->n_stmt; ++i) {
2954 scop->stmts[i] = stmt_anonymize(scop->stmts[i]);
2955 if (!scop->stmts[i])
2956 return pet_scop_free(scop);
2959 for (i = 0; i < scop->n_implication; ++i) {
2960 scop->implications[i] =
2961 implication_anonymize(scop->implications[i]);
2962 if (!scop->implications[i])
2963 return pet_scop_free(scop);
2966 for (i = 0; i < scop->n_independence; ++i) {
2967 scop->independences[i] =
2968 independence_anonymize(scop->independences[i]);
2969 if (!scop->independences[i])
2970 return pet_scop_free(scop);
2973 return scop;
2976 /* Compute the gist of the iteration domain and all access relations
2977 * of "stmt" based on the constraints on the parameters specified by "context"
2978 * and the constraints on the values of nested accesses specified
2979 * by "value_bounds".
2981 static struct pet_stmt *stmt_gist(struct pet_stmt *stmt,
2982 __isl_keep isl_set *context, __isl_keep isl_union_map *value_bounds)
2984 int i;
2985 isl_set *domain;
2987 if (!stmt)
2988 return NULL;
2990 domain = isl_set_copy(stmt->domain);
2991 if (stmt->n_arg > 0)
2992 domain = isl_map_domain(isl_set_unwrap(domain));
2994 domain = isl_set_intersect_params(domain, isl_set_copy(context));
2996 for (i = 0; i < stmt->n_arg; ++i) {
2997 stmt->args[i] = pet_expr_gist(stmt->args[i],
2998 domain, value_bounds);
2999 if (!stmt->args[i])
3000 goto error;
3003 stmt->body = pet_tree_gist(stmt->body, domain, value_bounds);
3004 if (!stmt->body)
3005 goto error;
3007 isl_set_free(domain);
3009 domain = isl_set_universe(pet_stmt_get_space(stmt));
3010 domain = isl_set_intersect_params(domain, isl_set_copy(context));
3011 if (stmt->n_arg > 0)
3012 domain = pet_value_bounds_apply(domain, stmt->n_arg, stmt->args,
3013 value_bounds);
3014 stmt->domain = isl_set_gist(stmt->domain, domain);
3015 if (!stmt->domain)
3016 return pet_stmt_free(stmt);
3018 return stmt;
3019 error:
3020 isl_set_free(domain);
3021 return pet_stmt_free(stmt);
3024 /* Compute the gist of the extent of the array
3025 * based on the constraints on the parameters specified by "context".
3027 static struct pet_array *array_gist(struct pet_array *array,
3028 __isl_keep isl_set *context)
3030 if (!array)
3031 return NULL;
3033 array->extent = isl_set_gist_params(array->extent,
3034 isl_set_copy(context));
3035 if (!array->extent)
3036 return pet_array_free(array);
3038 return array;
3041 /* Compute the gist of all sets and relations in "scop"
3042 * based on the constraints on the parameters specified by "scop->context"
3043 * and the constraints on the values of nested accesses specified
3044 * by "value_bounds".
3046 struct pet_scop *pet_scop_gist(struct pet_scop *scop,
3047 __isl_keep isl_union_map *value_bounds)
3049 int i;
3051 if (!scop)
3052 return NULL;
3054 scop->context = isl_set_coalesce(scop->context);
3055 if (!scop->context)
3056 return pet_scop_free(scop);
3058 scop->schedule = isl_schedule_gist_domain_params(scop->schedule,
3059 isl_set_copy(scop->context));
3060 if (!scop->schedule)
3061 return pet_scop_free(scop);
3063 for (i = 0; i < scop->n_array; ++i) {
3064 scop->arrays[i] = array_gist(scop->arrays[i], scop->context);
3065 if (!scop->arrays[i])
3066 return pet_scop_free(scop);
3069 for (i = 0; i < scop->n_stmt; ++i) {
3070 scop->stmts[i] = stmt_gist(scop->stmts[i], scop->context,
3071 value_bounds);
3072 if (!scop->stmts[i])
3073 return pet_scop_free(scop);
3076 return scop;
3079 /* Intersect the context of "scop" with "context".
3080 * To ensure that we don't introduce any unnamed parameters in
3081 * the context of "scop", we first remove the unnamed parameters
3082 * from "context".
3084 struct pet_scop *pet_scop_restrict_context(struct pet_scop *scop,
3085 __isl_take isl_set *context)
3087 if (!scop)
3088 goto error;
3090 context = pet_nested_remove_from_set(context);
3091 scop->context = isl_set_intersect(scop->context, context);
3092 if (!scop->context)
3093 return pet_scop_free(scop);
3095 return scop;
3096 error:
3097 isl_set_free(context);
3098 return pet_scop_free(scop);
3101 /* Drop the current context of "scop". That is, replace the context
3102 * by a universal set.
3104 struct pet_scop *pet_scop_reset_context(struct pet_scop *scop)
3106 isl_space *space;
3108 if (!scop)
3109 return NULL;
3111 space = isl_set_get_space(scop->context);
3112 isl_set_free(scop->context);
3113 scop->context = isl_set_universe(space);
3114 if (!scop->context)
3115 return pet_scop_free(scop);
3117 return scop;
3120 /* Append "array" to the arrays of "scop".
3122 struct pet_scop *pet_scop_add_array(struct pet_scop *scop,
3123 struct pet_array *array)
3125 isl_ctx *ctx;
3126 struct pet_array **arrays;
3128 if (!array || !scop)
3129 goto error;
3131 ctx = isl_set_get_ctx(scop->context);
3132 arrays = isl_realloc_array(ctx, scop->arrays, struct pet_array *,
3133 scop->n_array + 1);
3134 if (!arrays)
3135 goto error;
3136 scop->arrays = arrays;
3137 scop->arrays[scop->n_array] = array;
3138 scop->n_array++;
3139 scop->context = isl_set_intersect_params(scop->context,
3140 isl_set_copy(array->context));
3141 if (!scop->context)
3142 return pet_scop_free(scop);
3144 return scop;
3145 error:
3146 pet_array_free(array);
3147 return pet_scop_free(scop);
3150 /* Create an index expression for an access to a virtual array
3151 * representing the result of a condition.
3152 * Unlike other accessed data, the id of the array is NULL as
3153 * there is no ValueDecl in the program corresponding to the virtual
3154 * array.
3155 * The index expression is created as an identity mapping on "space".
3156 * That is, the dimension of the array is the same as that of "space".
3158 __isl_give isl_multi_pw_aff *pet_create_test_index(__isl_take isl_space *space,
3159 int test_nr)
3161 isl_id *id;
3162 char name[50];
3164 snprintf(name, sizeof(name), "__pet_test_%d", test_nr);
3165 id = isl_id_alloc(isl_space_get_ctx(space), name, NULL);
3166 space = isl_space_map_from_set(space);
3167 space = isl_space_set_tuple_id(space, isl_dim_out, id);
3168 return isl_multi_pw_aff_identity(space);
3171 /* Add an array with the given extent to the list
3172 * of arrays in "scop" and return the extended pet_scop.
3173 * Specifically, the extent is determined by the image of "domain"
3174 * under "index".
3175 * "int_size" is the number of bytes needed to represent values of type "int".
3176 * The array is marked as attaining values 0 and 1 only and
3177 * as each element being assigned at most once.
3179 struct pet_scop *pet_scop_add_boolean_array(struct pet_scop *scop,
3180 __isl_take isl_set *domain, __isl_take isl_multi_pw_aff *index,
3181 int int_size)
3183 isl_ctx *ctx;
3184 isl_space *space;
3185 struct pet_array *array;
3186 isl_map *access;
3188 if (!scop || !domain || !index)
3189 goto error;
3191 ctx = isl_multi_pw_aff_get_ctx(index);
3192 array = isl_calloc_type(ctx, struct pet_array);
3193 if (!array)
3194 goto error;
3196 access = isl_map_from_multi_pw_aff(index);
3197 access = isl_map_intersect_domain(access, domain);
3198 array->extent = isl_map_range(access);
3199 space = isl_space_params_alloc(ctx, 0);
3200 array->context = isl_set_universe(space);
3201 space = isl_space_set_alloc(ctx, 0, 1);
3202 array->value_bounds = isl_set_universe(space);
3203 array->value_bounds = isl_set_lower_bound_si(array->value_bounds,
3204 isl_dim_set, 0, 0);
3205 array->value_bounds = isl_set_upper_bound_si(array->value_bounds,
3206 isl_dim_set, 0, 1);
3207 array->element_type = strdup("int");
3208 array->element_size = int_size;
3209 array->uniquely_defined = 1;
3211 if (!array->extent || !array->context)
3212 array = pet_array_free(array);
3214 scop = pet_scop_add_array(scop, array);
3216 return scop;
3217 error:
3218 isl_set_free(domain);
3219 isl_multi_pw_aff_free(index);
3220 return pet_scop_free(scop);
3223 /* Create and return an implication on filter values equal to "satisfied"
3224 * with extension "map".
3226 static struct pet_implication *new_implication(__isl_take isl_map *map,
3227 int satisfied)
3229 isl_ctx *ctx;
3230 struct pet_implication *implication;
3232 if (!map)
3233 return NULL;
3234 ctx = isl_map_get_ctx(map);
3235 implication = isl_alloc_type(ctx, struct pet_implication);
3236 if (!implication)
3237 goto error;
3239 implication->extension = map;
3240 implication->satisfied = satisfied;
3242 return implication;
3243 error:
3244 isl_map_free(map);
3245 return NULL;
3248 /* Add an implication on filter values equal to "satisfied"
3249 * with extension "map" to "scop".
3251 struct pet_scop *pet_scop_add_implication(struct pet_scop *scop,
3252 __isl_take isl_map *map, int satisfied)
3254 isl_ctx *ctx;
3255 struct pet_implication *implication;
3256 struct pet_implication **implications;
3258 implication = new_implication(map, satisfied);
3259 if (!scop || !implication)
3260 goto error;
3262 ctx = isl_set_get_ctx(scop->context);
3263 implications = isl_realloc_array(ctx, scop->implications,
3264 struct pet_implication *,
3265 scop->n_implication + 1);
3266 if (!implications)
3267 goto error;
3268 scop->implications = implications;
3269 scop->implications[scop->n_implication] = implication;
3270 scop->n_implication++;
3272 return scop;
3273 error:
3274 pet_implication_free(implication);
3275 return pet_scop_free(scop);
3278 /* Create and return a function that maps the iteration domains
3279 * of the statements in "scop" onto their outer "n" dimensions.
3280 * "space" is the parameters space of the created function.
3282 static __isl_give isl_union_pw_multi_aff *outer_projection(
3283 struct pet_scop *scop, __isl_take isl_space *space, int n)
3285 int i;
3286 isl_union_pw_multi_aff *res;
3288 res = isl_union_pw_multi_aff_empty(space);
3290 if (!scop)
3291 return isl_union_pw_multi_aff_free(res);
3293 for (i = 0; i < scop->n_stmt; ++i) {
3294 struct pet_stmt *stmt = scop->stmts[i];
3295 isl_space *space;
3296 isl_multi_aff *ma;
3297 isl_pw_multi_aff *pma;
3299 space = pet_stmt_get_space(stmt);
3300 ma = pet_prefix_projection(space, n);
3301 pma = isl_pw_multi_aff_from_multi_aff(ma);
3302 res = isl_union_pw_multi_aff_add_pw_multi_aff(res, pma);
3305 return res;
3308 /* Add an independence to "scop" for the inner iterator of "domain"
3309 * with local variables "local", where "domain" represents the outer
3310 * loop iterators of all statements in "scop".
3311 * If "sign" is positive, then the inner iterator increases.
3312 * Otherwise it decreases.
3314 * The independence is supposed to filter out any dependence of
3315 * an iteration of domain on a previous iteration along the inner dimension.
3316 * We therefore create a mapping from an iteration to later iterations and
3317 * then plug in the projection of the iterations domains of "scop"
3318 * onto the outer loop iterators.
3320 struct pet_scop *pet_scop_set_independent(struct pet_scop *scop,
3321 __isl_keep isl_set *domain, __isl_take isl_union_set *local, int sign)
3323 int i, dim;
3324 isl_space *space;
3325 isl_map *map;
3326 isl_union_map *independence;
3327 isl_union_pw_multi_aff *proj;
3329 if (!scop || !domain || !local)
3330 goto error;
3332 dim = isl_set_dim(domain, isl_dim_set);
3333 space = isl_space_map_from_set(isl_set_get_space(domain));
3334 map = isl_map_universe(space);
3335 for (i = 0; i + 1 < dim; ++i)
3336 map = isl_map_equate(map, isl_dim_in, i, isl_dim_out, i);
3337 if (sign > 0)
3338 map = isl_map_order_lt(map,
3339 isl_dim_in, dim - 1, isl_dim_out, dim - 1);
3340 else
3341 map = isl_map_order_gt(map,
3342 isl_dim_in, dim - 1, isl_dim_out, dim - 1);
3344 independence = isl_union_map_from_map(map);
3345 space = isl_space_params(isl_set_get_space(domain));
3346 proj = outer_projection(scop, space, dim);
3347 independence = isl_union_map_preimage_domain_union_pw_multi_aff(
3348 independence, isl_union_pw_multi_aff_copy(proj));
3349 independence = isl_union_map_preimage_range_union_pw_multi_aff(
3350 independence, proj);
3352 scop = pet_scop_add_independence(scop, independence, local);
3354 return scop;
3355 error:
3356 isl_union_set_free(local);
3357 return pet_scop_free(scop);
3360 /* Given an access expression, check if it is data dependent.
3361 * If so, set *found and abort the search.
3363 static int is_data_dependent(__isl_keep pet_expr *expr, void *user)
3365 int *found = user;
3367 if (pet_expr_get_n_arg(expr) > 0) {
3368 *found = 1;
3369 return -1;
3372 return 0;
3375 /* Does "scop" contain any data dependent accesses?
3377 * Check the body of each statement for such accesses.
3379 int pet_scop_has_data_dependent_accesses(struct pet_scop *scop)
3381 int i;
3382 int found = 0;
3384 if (!scop)
3385 return -1;
3387 for (i = 0; i < scop->n_stmt; ++i) {
3388 int r = pet_tree_foreach_access_expr(scop->stmts[i]->body,
3389 &is_data_dependent, &found);
3390 if (r < 0 && !found)
3391 return -1;
3392 if (found)
3393 return found;
3396 return found;
3399 /* Does "scop" contain and data dependent conditions?
3401 int pet_scop_has_data_dependent_conditions(struct pet_scop *scop)
3403 int i;
3405 if (!scop)
3406 return -1;
3408 for (i = 0; i < scop->n_stmt; ++i)
3409 if (scop->stmts[i]->n_arg > 0)
3410 return 1;
3412 return 0;
3415 /* Keep track of the "input" file inside the (extended) "scop".
3417 struct pet_scop *pet_scop_set_input_file(struct pet_scop *scop, FILE *input)
3419 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
3421 if (!scop)
3422 return NULL;
3424 ext->input = input;
3426 return scop;
3429 /* Print the original code corresponding to "scop" to printer "p".
3431 * pet_scop_print_original can only be called from
3432 * a pet_transform_C_source callback. This means that the input
3433 * file is stored in the extended scop and that the printer prints
3434 * to a file.
3436 __isl_give isl_printer *pet_scop_print_original(struct pet_scop *scop,
3437 __isl_take isl_printer *p)
3439 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
3440 FILE *output;
3441 unsigned start, end;
3443 if (!scop || !p)
3444 return isl_printer_free(p);
3446 if (!ext->input)
3447 isl_die(isl_printer_get_ctx(p), isl_error_invalid,
3448 "no input file stored in scop",
3449 return isl_printer_free(p));
3451 output = isl_printer_get_file(p);
3452 if (!output)
3453 return isl_printer_free(p);
3455 start = pet_loc_get_start(scop->loc);
3456 end = pet_loc_get_end(scop->loc);
3457 if (copy(ext->input, output, start, end) < 0)
3458 return isl_printer_free(p);
3460 return p;