pet 0.11.8
[pet.git] / scop.c
blob9c27f31297c39dfd1a812bfdf11e0fbed08aca98
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;
1199 if (array1->outer != array2->outer)
1200 return 0;
1202 return 1;
1205 /* Return 1 if the two pet_stmts are equivalent.
1207 int pet_stmt_is_equal(struct pet_stmt *stmt1, struct pet_stmt *stmt2)
1209 int i;
1211 if (!stmt1 || !stmt2)
1212 return 0;
1214 if (pet_loc_get_line(stmt1->loc) != pet_loc_get_line(stmt2->loc))
1215 return 0;
1216 if (!isl_set_is_equal(stmt1->domain, stmt2->domain))
1217 return 0;
1218 if (!pet_tree_is_equal(stmt1->body, stmt2->body))
1219 return 0;
1220 if (stmt1->n_arg != stmt2->n_arg)
1221 return 0;
1222 for (i = 0; i < stmt1->n_arg; ++i) {
1223 if (!pet_expr_is_equal(stmt1->args[i], stmt2->args[i]))
1224 return 0;
1227 return 1;
1230 /* Return 1 if the two pet_types are equivalent.
1232 * We only compare the names of the types since the exact representation
1233 * of the definition may depend on the version of clang being used.
1235 int pet_type_is_equal(struct pet_type *type1, struct pet_type *type2)
1237 if (!type1 || !type2)
1238 return 0;
1240 if (strcmp(type1->name, type2->name))
1241 return 0;
1243 return 1;
1246 /* Return 1 if the two pet_implications are equivalent.
1248 int pet_implication_is_equal(struct pet_implication *implication1,
1249 struct pet_implication *implication2)
1251 if (!implication1 || !implication2)
1252 return 0;
1254 if (implication1->satisfied != implication2->satisfied)
1255 return 0;
1256 if (!isl_map_is_equal(implication1->extension, implication2->extension))
1257 return 0;
1259 return 1;
1262 /* Return 1 if the two pet_independences are equivalent.
1264 int pet_independence_is_equal(struct pet_independence *independence1,
1265 struct pet_independence *independence2)
1267 if (!independence1 || !independence2)
1268 return 0;
1270 if (!isl_union_map_is_equal(independence1->filter,
1271 independence2->filter))
1272 return 0;
1273 if (!isl_union_set_is_equal(independence1->local, independence2->local))
1274 return 0;
1276 return 1;
1279 /* Return 1 if the two pet_scops are equivalent.
1281 int pet_scop_is_equal(struct pet_scop *scop1, struct pet_scop *scop2)
1283 int i;
1284 int equal;
1286 if (!scop1 || !scop2)
1287 return 0;
1289 if (!isl_set_is_equal(scop1->context, scop2->context))
1290 return 0;
1291 if (!isl_set_is_equal(scop1->context_value, scop2->context_value))
1292 return 0;
1293 equal = isl_schedule_plain_is_equal(scop1->schedule, scop2->schedule);
1294 if (equal < 0)
1295 return -1;
1296 if (!equal)
1297 return 0;
1299 if (scop1->n_type != scop2->n_type)
1300 return 0;
1301 for (i = 0; i < scop1->n_type; ++i)
1302 if (!pet_type_is_equal(scop1->types[i], scop2->types[i]))
1303 return 0;
1305 if (scop1->n_array != scop2->n_array)
1306 return 0;
1307 for (i = 0; i < scop1->n_array; ++i)
1308 if (!pet_array_is_equal(scop1->arrays[i], scop2->arrays[i]))
1309 return 0;
1311 if (scop1->n_stmt != scop2->n_stmt)
1312 return 0;
1313 for (i = 0; i < scop1->n_stmt; ++i)
1314 if (!pet_stmt_is_equal(scop1->stmts[i], scop2->stmts[i]))
1315 return 0;
1317 if (scop1->n_implication != scop2->n_implication)
1318 return 0;
1319 for (i = 0; i < scop1->n_implication; ++i)
1320 if (!pet_implication_is_equal(scop1->implications[i],
1321 scop2->implications[i]))
1322 return 0;
1324 if (scop1->n_independence != scop2->n_independence)
1325 return 0;
1326 for (i = 0; i < scop1->n_independence; ++i)
1327 if (!pet_independence_is_equal(scop1->independences[i],
1328 scop2->independences[i]))
1329 return 0;
1331 return 1;
1334 /* Does the set "extent" reference a virtual array, i.e.,
1335 * one with user pointer equal to NULL?
1336 * A virtual array does not have any members.
1338 static int extent_is_virtual_array(__isl_keep isl_set *extent)
1340 isl_id *id;
1341 int is_virtual;
1343 if (!isl_set_has_tuple_id(extent))
1344 return 0;
1345 if (isl_set_is_wrapping(extent))
1346 return 0;
1347 id = isl_set_get_tuple_id(extent);
1348 is_virtual = !isl_id_get_user(id);
1349 isl_id_free(id);
1351 return is_virtual;
1354 /* Intersect the initial dimensions of "array" with "domain", provided
1355 * that "array" represents a virtual array.
1357 * If "array" is virtual, then We take the preimage of "domain"
1358 * over the projection of the extent of "array" onto its initial dimensions
1359 * and intersect this extent with the result.
1361 static struct pet_array *virtual_array_intersect_domain_prefix(
1362 struct pet_array *array, __isl_take isl_set *domain)
1364 int n;
1365 isl_space *space;
1366 isl_multi_aff *ma;
1368 if (!array || !extent_is_virtual_array(array->extent)) {
1369 isl_set_free(domain);
1370 return array;
1373 space = isl_set_get_space(array->extent);
1374 n = isl_set_dim(domain, isl_dim_set);
1375 ma = pet_prefix_projection(space, n);
1376 domain = isl_set_preimage_multi_aff(domain, ma);
1378 array->extent = isl_set_intersect(array->extent, domain);
1379 if (!array->extent)
1380 return pet_array_free(array);
1382 return array;
1385 /* Intersect the initial dimensions of the domain of "stmt"
1386 * with "domain".
1388 * We take the preimage of "domain" over the projection of the
1389 * domain of "stmt" onto its initial dimensions and intersect
1390 * the domain of "stmt" with the result.
1392 static struct pet_stmt *stmt_intersect_domain_prefix(struct pet_stmt *stmt,
1393 __isl_take isl_set *domain)
1395 int n;
1396 isl_space *space;
1397 isl_multi_aff *ma;
1399 if (!stmt)
1400 goto error;
1402 space = isl_set_get_space(stmt->domain);
1403 n = isl_set_dim(domain, isl_dim_set);
1404 ma = pet_prefix_projection(space, n);
1405 domain = isl_set_preimage_multi_aff(domain, ma);
1407 stmt->domain = isl_set_intersect(stmt->domain, domain);
1408 if (!stmt->domain)
1409 return pet_stmt_free(stmt);
1411 return stmt;
1412 error:
1413 isl_set_free(domain);
1414 return pet_stmt_free(stmt);
1417 /* Intersect the initial dimensions of the domain of "implication"
1418 * with "domain".
1420 * We take the preimage of "domain" over the projection of the
1421 * domain of "implication" onto its initial dimensions and intersect
1422 * the domain of "implication" with the result.
1424 static struct pet_implication *implication_intersect_domain_prefix(
1425 struct pet_implication *implication, __isl_take isl_set *domain)
1427 int n;
1428 isl_space *space;
1429 isl_multi_aff *ma;
1431 if (!implication)
1432 goto error;
1434 space = isl_map_get_space(implication->extension);
1435 n = isl_set_dim(domain, isl_dim_set);
1436 ma = pet_prefix_projection(isl_space_domain(space), n);
1437 domain = isl_set_preimage_multi_aff(domain, ma);
1439 implication->extension =
1440 isl_map_intersect_domain(implication->extension, domain);
1441 if (!implication->extension)
1442 return pet_implication_free(implication);
1444 return implication;
1445 error:
1446 isl_set_free(domain);
1447 return pet_implication_free(implication);
1450 /* Intersect the initial dimensions of the domains in "scop" with "domain".
1452 * The extents of the virtual arrays match the iteration domains,
1453 * so if the iteration domain changes, we need to change those extents too.
1455 * The domain of the schedule is intersected with (i.e., replaced by)
1456 * the union of the updated iteration domains.
1458 struct pet_scop *pet_scop_intersect_domain_prefix(struct pet_scop *scop,
1459 __isl_take isl_set *domain)
1461 int i;
1463 if (!scop)
1464 goto error;
1466 for (i = 0; i < scop->n_array; ++i) {
1467 scop->arrays[i] = virtual_array_intersect_domain_prefix(
1468 scop->arrays[i], isl_set_copy(domain));
1469 if (!scop->arrays[i])
1470 goto error;
1473 for (i = 0; i < scop->n_stmt; ++i) {
1474 scop->stmts[i] = stmt_intersect_domain_prefix(scop->stmts[i],
1475 isl_set_copy(domain));
1476 if (!scop->stmts[i])
1477 goto error;
1480 for (i = 0; i < scop->n_implication; ++i) {
1481 scop->implications[i] =
1482 implication_intersect_domain_prefix(scop->implications[i],
1483 isl_set_copy(domain));
1484 if (!scop->implications[i])
1485 return pet_scop_free(scop);
1488 scop->schedule = isl_schedule_intersect_domain(scop->schedule,
1489 pet_scop_get_instance_set(scop));
1490 if (!scop->schedule)
1491 goto error;
1493 isl_set_free(domain);
1494 return scop;
1495 error:
1496 isl_set_free(domain);
1497 return pet_scop_free(scop);
1500 /* Update the context with respect to an embedding into a loop
1501 * with iteration domain "dom".
1502 * The input context lives in the same space as "dom".
1503 * The output context has the inner dimension removed.
1505 * An outer loop iterator value is invalid for the embedding if
1506 * any of the corresponding inner iterator values is invalid.
1507 * That is, an outer loop iterator value is valid only if all the corresponding
1508 * inner iterator values are valid.
1509 * We therefore compute the set of outer loop iterators l
1511 * forall i: dom(l,i) => valid(l,i)
1513 * or
1515 * forall i: not dom(l,i) or valid(l,i)
1517 * or
1519 * not exists i: dom(l,i) and not valid(l,i)
1521 * i.e.,
1523 * not exists i: (dom \ valid)(l,i)
1525 * If there are any unnamed parameters in "dom", then we consider
1526 * a parameter value to be valid if it is valid for any value of those
1527 * unnamed parameters. They are therefore projected out at the end.
1529 static __isl_give isl_set *context_embed(__isl_take isl_set *context,
1530 __isl_keep isl_set *dom)
1532 int pos;
1534 pos = isl_set_dim(context, isl_dim_set) - 1;
1535 context = isl_set_subtract(isl_set_copy(dom), context);
1536 context = isl_set_project_out(context, isl_dim_set, pos, 1);
1537 context = isl_set_complement(context);
1538 context = pet_nested_remove_from_set(context);
1540 return context;
1543 /* Internal data structure for outer_projection_mupa.
1545 * "n" is the number of outer dimensions onto which to project.
1546 * "res" collects the result.
1548 struct pet_outer_projection_data {
1549 int n;
1550 isl_union_pw_multi_aff *res;
1553 /* Create a function that maps "set" onto its outer data->n dimensions and
1554 * add it to data->res.
1556 static isl_stat add_outer_projection(__isl_take isl_set *set, void *user)
1558 struct pet_outer_projection_data *data = user;
1559 int dim;
1560 isl_space *space;
1561 isl_pw_multi_aff *pma;
1563 dim = isl_set_dim(set, isl_dim_set);
1564 space = isl_set_get_space(set);
1565 pma = isl_pw_multi_aff_project_out_map(space,
1566 isl_dim_set, data->n, dim - data->n);
1567 data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma);
1569 isl_set_free(set);
1571 return isl_stat_ok;
1574 /* Create and return a function that maps the sets in "domain"
1575 * onto their outer "n" dimensions.
1577 static __isl_give isl_multi_union_pw_aff *outer_projection_mupa(
1578 __isl_take isl_union_set *domain, int n)
1580 struct pet_outer_projection_data data;
1581 isl_space *space;
1583 space = isl_union_set_get_space(domain);
1584 data.n = n;
1585 data.res = isl_union_pw_multi_aff_empty(space);
1586 if (isl_union_set_foreach_set(domain, &add_outer_projection, &data) < 0)
1587 data.res = isl_union_pw_multi_aff_free(data.res);
1589 isl_union_set_free(domain);
1590 return isl_multi_union_pw_aff_from_union_pw_multi_aff(data.res);
1593 /* Embed "schedule" in a loop with schedule "prefix".
1594 * The domain of "prefix" corresponds to the outer dimensions
1595 * of the iteration domains.
1596 * We therefore construct a projection onto these outer dimensions,
1597 * compose it with "prefix" and then add the result as a band schedule.
1599 * If the domain of the schedule is empty, then there is no need
1600 * to insert any node.
1602 static __isl_give isl_schedule *schedule_embed(
1603 __isl_take isl_schedule *schedule, __isl_keep isl_multi_aff *prefix)
1605 int n;
1606 int empty;
1607 isl_union_set *domain;
1608 isl_multi_aff *ma;
1609 isl_multi_union_pw_aff *mupa;
1611 domain = isl_schedule_get_domain(schedule);
1612 empty = isl_union_set_is_empty(domain);
1613 if (empty < 0 || empty) {
1614 isl_union_set_free(domain);
1615 return empty < 0 ? isl_schedule_free(schedule) : schedule;
1618 n = isl_multi_aff_dim(prefix, isl_dim_in);
1619 mupa = outer_projection_mupa(domain, n);
1620 ma = isl_multi_aff_copy(prefix);
1621 mupa = isl_multi_union_pw_aff_apply_multi_aff(mupa, ma);
1622 schedule = isl_schedule_insert_partial_schedule(schedule, mupa);
1624 return schedule;
1627 /* Adjust the context and the schedule according to an embedding
1628 * in a loop with iteration domain "dom" and schedule "sched".
1630 struct pet_scop *pet_scop_embed(struct pet_scop *scop, __isl_take isl_set *dom,
1631 __isl_take isl_multi_aff *sched)
1633 if (!scop)
1634 goto error;
1636 scop->context = context_embed(scop->context, dom);
1637 if (!scop->context)
1638 goto error;
1640 scop->schedule = schedule_embed(scop->schedule, sched);
1641 if (!scop->schedule)
1642 goto error;
1644 isl_set_free(dom);
1645 isl_multi_aff_free(sched);
1646 return scop;
1647 error:
1648 isl_set_free(dom);
1649 isl_multi_aff_free(sched);
1650 return pet_scop_free(scop);
1653 /* Add extra conditions to scop->skip[type].
1655 * The new skip condition only holds if it held before
1656 * and the condition is true. It does not hold if it did not hold
1657 * before or the condition is false.
1659 * The skip condition is assumed to be an affine expression.
1661 static struct pet_scop *pet_scop_restrict_skip(struct pet_scop *scop,
1662 enum pet_skip type, __isl_keep isl_set *cond)
1664 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1665 isl_pw_aff *skip;
1666 isl_set *dom;
1668 if (!scop)
1669 return NULL;
1670 if (!ext->skip[type])
1671 return scop;
1673 if (!multi_pw_aff_is_affine(ext->skip[type]))
1674 isl_die(isl_multi_pw_aff_get_ctx(ext->skip[type]),
1675 isl_error_internal, "can only restrict affine skips",
1676 return pet_scop_free(scop));
1678 skip = isl_multi_pw_aff_get_pw_aff(ext->skip[type], 0);
1679 dom = isl_pw_aff_domain(isl_pw_aff_copy(skip));
1680 cond = isl_set_copy(cond);
1681 cond = isl_set_intersect(cond, isl_pw_aff_non_zero_set(skip));
1682 skip = indicator_function(cond, dom);
1683 isl_multi_pw_aff_free(ext->skip[type]);
1684 ext->skip[type] = isl_multi_pw_aff_from_pw_aff(skip);
1685 if (!ext->skip[type])
1686 return pet_scop_free(scop);
1688 return scop;
1691 /* Adjust the context and the skip conditions to the fact that
1692 * the scop was created in a context where "cond" holds.
1694 * An outer loop iterator or parameter value is valid for the result
1695 * if it was valid for the original scop and satisfies "cond" or if it does
1696 * not satisfy "cond" as in this case the scop is not executed
1697 * and the original constraints on these values are irrelevant.
1699 struct pet_scop *pet_scop_restrict(struct pet_scop *scop,
1700 __isl_take isl_set *cond)
1702 scop = pet_scop_restrict_skip(scop, pet_skip_now, cond);
1703 scop = pet_scop_restrict_skip(scop, pet_skip_later, cond);
1705 if (!scop)
1706 goto error;
1708 scop->context = isl_set_intersect(scop->context, isl_set_copy(cond));
1709 scop->context = isl_set_union(scop->context,
1710 isl_set_complement(isl_set_copy(cond)));
1711 scop->context = isl_set_coalesce(scop->context);
1712 scop->context = pet_nested_remove_from_set(scop->context);
1713 if (!scop->context)
1714 goto error;
1716 isl_set_free(cond);
1717 return scop;
1718 error:
1719 isl_set_free(cond);
1720 return pet_scop_free(scop);
1723 /* Insert an argument expression corresponding to "test" in front
1724 * of the list of arguments described by *n_arg and *args.
1726 static int args_insert_access(unsigned *n_arg, pet_expr ***args,
1727 __isl_keep isl_multi_pw_aff *test)
1729 int i;
1730 isl_ctx *ctx = isl_multi_pw_aff_get_ctx(test);
1732 if (!test)
1733 return -1;
1735 if (!*args) {
1736 *args = isl_calloc_array(ctx, pet_expr *, 1);
1737 if (!*args)
1738 return -1;
1739 } else {
1740 pet_expr **ext;
1741 ext = isl_calloc_array(ctx, pet_expr *, 1 + *n_arg);
1742 if (!ext)
1743 return -1;
1744 for (i = 0; i < *n_arg; ++i)
1745 ext[1 + i] = (*args)[i];
1746 free(*args);
1747 *args = ext;
1749 (*n_arg)++;
1750 (*args)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test));
1751 if (!(*args)[0])
1752 return -1;
1754 return 0;
1757 /* Look through the applications in "scop" for any that can be
1758 * applied to the filter expressed by "map" and "satisified".
1759 * If there is any, then apply it to "map" and return the result.
1760 * Otherwise, return "map".
1761 * "id" is the identifier of the virtual array.
1763 * We only introduce at most one implication for any given virtual array,
1764 * so we can apply the implication and return as soon as we find one.
1766 static __isl_give isl_map *apply_implications(struct pet_scop *scop,
1767 __isl_take isl_map *map, __isl_keep isl_id *id, int satisfied)
1769 int i;
1771 for (i = 0; i < scop->n_implication; ++i) {
1772 struct pet_implication *pi = scop->implications[i];
1773 isl_id *pi_id;
1775 if (pi->satisfied != satisfied)
1776 continue;
1777 pi_id = isl_map_get_tuple_id(pi->extension, isl_dim_in);
1778 isl_id_free(pi_id);
1779 if (pi_id != id)
1780 continue;
1782 return isl_map_apply_range(map, isl_map_copy(pi->extension));
1785 return map;
1788 /* Is the filter expressed by "test" and "satisfied" implied
1789 * by filter "pos" on "domain", with filter "expr", taking into
1790 * account the implications of "scop"?
1792 * For filter on domain implying that expressed by "test" and "satisfied",
1793 * the filter needs to be an access to the same (virtual) array as "test" and
1794 * the filter value needs to be equal to "satisfied".
1795 * Moreover, the filter access relation, possibly extended by
1796 * the implications in "scop" needs to contain "test".
1798 static int implies_filter(struct pet_scop *scop,
1799 __isl_keep isl_map *domain, int pos, __isl_keep pet_expr *expr,
1800 __isl_keep isl_map *test, int satisfied)
1802 isl_id *test_id, *arg_id;
1803 isl_val *val;
1804 int is_int;
1805 int s;
1806 int is_subset;
1807 isl_map *implied;
1809 if (expr->type != pet_expr_access)
1810 return 0;
1811 test_id = isl_map_get_tuple_id(test, isl_dim_out);
1812 arg_id = pet_expr_access_get_id(expr);
1813 isl_id_free(arg_id);
1814 isl_id_free(test_id);
1815 if (test_id != arg_id)
1816 return 0;
1817 val = isl_map_plain_get_val_if_fixed(domain, isl_dim_out, pos);
1818 is_int = isl_val_is_int(val);
1819 if (is_int)
1820 s = isl_val_get_num_si(val);
1821 isl_val_free(val);
1822 if (!val)
1823 return -1;
1824 if (!is_int)
1825 return 0;
1826 if (s != satisfied)
1827 return 0;
1829 implied = isl_map_from_multi_pw_aff(pet_expr_access_get_index(expr));
1830 implied = apply_implications(scop, implied, test_id, satisfied);
1831 is_subset = isl_map_is_subset(test, implied);
1832 isl_map_free(implied);
1834 return is_subset;
1837 /* Is the filter expressed by "test" and "satisfied" implied
1838 * by any of the filters on the domain of "stmt", taking into
1839 * account the implications of "scop"?
1841 static int filter_implied(struct pet_scop *scop,
1842 struct pet_stmt *stmt, __isl_keep isl_multi_pw_aff *test, int satisfied)
1844 int i;
1845 int implied;
1846 isl_map *domain;
1847 isl_map *test_map;
1849 if (!scop || !stmt || !test)
1850 return -1;
1851 if (scop->n_implication == 0)
1852 return 0;
1853 if (stmt->n_arg == 0)
1854 return 0;
1856 domain = isl_set_unwrap(isl_set_copy(stmt->domain));
1857 test_map = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test));
1859 implied = 0;
1860 for (i = 0; i < stmt->n_arg; ++i) {
1861 implied = implies_filter(scop, domain, i, stmt->args[i],
1862 test_map, satisfied);
1863 if (implied < 0 || implied)
1864 break;
1867 isl_map_free(test_map);
1868 isl_map_free(domain);
1869 return implied;
1872 /* Make the statement "stmt" depend on the value of "test"
1873 * being equal to "satisfied" by adjusting stmt->domain.
1875 * The domain of "test" corresponds to the (zero or more) outer dimensions
1876 * of the iteration domain.
1878 * We first extend "test" to apply to the entire iteration domain and
1879 * then check if the filter that we are about to add is implied
1880 * by any of the current filters, possibly taking into account
1881 * the implications in "scop". If so, we leave "stmt" untouched and return.
1883 * Otherwise, we insert an argument corresponding to a read to "test"
1884 * from the iteration domain of "stmt" in front of the list of arguments.
1885 * We also insert a corresponding output dimension in the wrapped
1886 * map contained in stmt->domain, with value set to "satisfied".
1888 static struct pet_stmt *stmt_filter(struct pet_scop *scop,
1889 struct pet_stmt *stmt, __isl_take isl_multi_pw_aff *test, int satisfied)
1891 int i;
1892 int implied;
1893 isl_id *id;
1894 isl_pw_multi_aff *pma;
1895 isl_multi_aff *add_dom;
1896 isl_space *space;
1897 isl_local_space *ls;
1898 int n_test_dom;
1900 if (!stmt || !test)
1901 goto error;
1903 space = pet_stmt_get_space(stmt);
1904 n_test_dom = isl_multi_pw_aff_dim(test, isl_dim_in);
1905 space = isl_space_from_domain(space);
1906 space = isl_space_add_dims(space, isl_dim_out, n_test_dom);
1907 add_dom = isl_multi_aff_zero(isl_space_copy(space));
1908 ls = isl_local_space_from_space(isl_space_domain(space));
1909 for (i = 0; i < n_test_dom; ++i) {
1910 isl_aff *aff;
1911 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
1912 isl_dim_set, i);
1913 add_dom = isl_multi_aff_set_aff(add_dom, i, aff);
1915 isl_local_space_free(ls);
1916 test = isl_multi_pw_aff_pullback_multi_aff(test, add_dom);
1918 implied = filter_implied(scop, stmt, test, satisfied);
1919 if (implied < 0)
1920 goto error;
1921 if (implied) {
1922 isl_multi_pw_aff_free(test);
1923 return stmt;
1926 id = isl_multi_pw_aff_get_tuple_id(test, isl_dim_out);
1927 pma = pet_filter_insert_pma(isl_set_get_space(stmt->domain),
1928 id, satisfied);
1929 stmt->domain = isl_set_preimage_pw_multi_aff(stmt->domain, pma);
1931 if (args_insert_access(&stmt->n_arg, &stmt->args, test) < 0)
1932 goto error;
1934 isl_multi_pw_aff_free(test);
1935 return stmt;
1936 error:
1937 isl_multi_pw_aff_free(test);
1938 return pet_stmt_free(stmt);
1941 /* Does "scop" have a skip condition of the given "type"?
1943 int pet_scop_has_skip(struct pet_scop *scop, enum pet_skip type)
1945 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1947 if (!scop)
1948 return -1;
1949 return ext->skip[type] != NULL;
1952 /* Does "scop" have a skip condition of the given "type" that
1953 * is an affine expression?
1955 int pet_scop_has_affine_skip(struct pet_scop *scop, enum pet_skip type)
1957 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1959 if (!scop)
1960 return -1;
1961 if (!ext->skip[type])
1962 return 0;
1963 return multi_pw_aff_is_affine(ext->skip[type]);
1966 /* Does "scop" have a skip condition of the given "type" that
1967 * is not an affine expression?
1969 int pet_scop_has_var_skip(struct pet_scop *scop, enum pet_skip type)
1971 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1972 int aff;
1974 if (!scop)
1975 return -1;
1976 if (!ext->skip[type])
1977 return 0;
1978 aff = multi_pw_aff_is_affine(ext->skip[type]);
1979 if (aff < 0)
1980 return -1;
1981 return !aff;
1984 /* Does "scop" have a skip condition of the given "type" that
1985 * is affine and holds on the entire domain?
1987 int pet_scop_has_universal_skip(struct pet_scop *scop, enum pet_skip type)
1989 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
1990 isl_pw_aff *pa;
1991 isl_set *set;
1992 int is_aff;
1993 int is_univ;
1995 is_aff = pet_scop_has_affine_skip(scop, type);
1996 if (is_aff < 0 || !is_aff)
1997 return is_aff;
1999 pa = isl_multi_pw_aff_get_pw_aff(ext->skip[type], 0);
2000 set = isl_pw_aff_non_zero_set(pa);
2001 is_univ = isl_set_plain_is_universe(set);
2002 isl_set_free(set);
2004 return is_univ;
2007 /* Replace scop->skip[type] by "skip".
2009 struct pet_scop *pet_scop_set_skip(struct pet_scop *scop,
2010 enum pet_skip type, __isl_take isl_multi_pw_aff *skip)
2012 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2014 if (!scop || !skip)
2015 goto error;
2017 isl_multi_pw_aff_free(ext->skip[type]);
2018 ext->skip[type] = skip;
2020 return scop;
2021 error:
2022 isl_multi_pw_aff_free(skip);
2023 return pet_scop_free(scop);
2026 /* Return a copy of scop->skip[type].
2028 __isl_give isl_multi_pw_aff *pet_scop_get_skip(struct pet_scop *scop,
2029 enum pet_skip type)
2031 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2033 if (!scop)
2034 return NULL;
2036 return isl_multi_pw_aff_copy(ext->skip[type]);
2039 /* Assuming scop->skip[type] is an affine expression,
2040 * return the constraints on the outer loop domain for which the skip condition
2041 * holds.
2043 __isl_give isl_set *pet_scop_get_affine_skip_domain(struct pet_scop *scop,
2044 enum pet_skip type)
2046 isl_multi_pw_aff *skip;
2047 isl_pw_aff *pa;
2049 skip = pet_scop_get_skip(scop, type);
2050 pa = isl_multi_pw_aff_get_pw_aff(skip, 0);
2051 isl_multi_pw_aff_free(skip);
2052 return isl_pw_aff_non_zero_set(pa);
2055 /* Return the identifier of the variable that is accessed by
2056 * the skip condition of the given type.
2058 * The skip condition is assumed not to be an affine condition.
2060 __isl_give isl_id *pet_scop_get_skip_id(struct pet_scop *scop,
2061 enum pet_skip type)
2063 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2065 if (!scop)
2066 return NULL;
2068 return isl_multi_pw_aff_get_tuple_id(ext->skip[type], isl_dim_out);
2071 /* Return an access pet_expr corresponding to the skip condition
2072 * of the given type.
2074 __isl_give pet_expr *pet_scop_get_skip_expr(struct pet_scop *scop,
2075 enum pet_skip type)
2077 return pet_expr_from_index(pet_scop_get_skip(scop, type));
2080 /* Drop the skip condition scop->skip[type].
2082 void pet_scop_reset_skip(struct pet_scop *scop, enum pet_skip type)
2084 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
2086 if (!scop)
2087 return;
2089 isl_multi_pw_aff_free(ext->skip[type]);
2090 ext->skip[type] = NULL;
2093 /* Drop all skip conditions on "scop".
2095 struct pet_scop *pet_scop_reset_skips(struct pet_scop *scop)
2097 pet_scop_reset_skip(scop, pet_skip_now);
2098 pet_scop_reset_skip(scop, pet_skip_later);
2100 return scop;
2103 /* Make the skip condition (if any) depend on the value of "test" being
2104 * equal to "satisfied".
2106 * We only support the case where the original skip condition is universal,
2107 * i.e., where skipping is unconditional, and where satisfied == 1.
2108 * In this case, the skip condition is changed to skip only when
2109 * "test" is equal to one.
2111 static struct pet_scop *pet_scop_filter_skip(struct pet_scop *scop,
2112 enum pet_skip type, __isl_keep isl_multi_pw_aff *test, int satisfied)
2114 int is_univ = 0;
2116 if (!scop)
2117 return NULL;
2118 if (!pet_scop_has_skip(scop, type))
2119 return scop;
2121 if (satisfied)
2122 is_univ = pet_scop_has_universal_skip(scop, type);
2123 if (is_univ < 0)
2124 return pet_scop_free(scop);
2125 if (satisfied && is_univ) {
2126 isl_multi_pw_aff *skip;
2127 skip = isl_multi_pw_aff_copy(test);
2128 scop = pet_scop_set_skip(scop, type, skip);
2129 if (!scop)
2130 return NULL;
2131 } else {
2132 isl_die(isl_multi_pw_aff_get_ctx(test), isl_error_internal,
2133 "skip expression cannot be filtered",
2134 return pet_scop_free(scop));
2137 return scop;
2140 /* Make all statements in "scop" depend on the value of "test"
2141 * being equal to "satisfied" by adjusting their domains.
2143 struct pet_scop *pet_scop_filter(struct pet_scop *scop,
2144 __isl_take isl_multi_pw_aff *test, int satisfied)
2146 int i;
2148 scop = pet_scop_filter_skip(scop, pet_skip_now, test, satisfied);
2149 scop = pet_scop_filter_skip(scop, pet_skip_later, test, satisfied);
2151 if (!scop || !test)
2152 goto error;
2154 for (i = 0; i < scop->n_stmt; ++i) {
2155 scop->stmts[i] = stmt_filter(scop, scop->stmts[i],
2156 isl_multi_pw_aff_copy(test), satisfied);
2157 if (!scop->stmts[i])
2158 goto error;
2161 isl_multi_pw_aff_free(test);
2162 return scop;
2163 error:
2164 isl_multi_pw_aff_free(test);
2165 return pet_scop_free(scop);
2168 /* Add the parameters of the access expression "expr" to "space".
2170 static int access_collect_params(__isl_keep pet_expr *expr, void *user)
2172 isl_space *expr_space;
2173 isl_space **space = user;
2175 expr_space = pet_expr_access_get_parameter_space(expr);
2176 *space = isl_space_align_params(*space, expr_space);
2178 return *space ? 0 : -1;
2181 /* Add all parameters in "stmt" to "space" and return the result.
2183 static __isl_give isl_space *stmt_collect_params(struct pet_stmt *stmt,
2184 __isl_take isl_space *space)
2186 int i;
2188 if (!stmt)
2189 return isl_space_free(space);
2191 space = isl_space_align_params(space, isl_set_get_space(stmt->domain));
2192 for (i = 0; i < stmt->n_arg; ++i)
2193 if (pet_expr_foreach_access_expr(stmt->args[i],
2194 &access_collect_params, &space) < 0)
2195 space = isl_space_free(space);
2196 if (pet_tree_foreach_access_expr(stmt->body, &access_collect_params,
2197 &space) < 0)
2198 space = isl_space_free(space);
2200 return space;
2203 /* Add all parameters in "array" to "space" and return the result.
2205 static __isl_give isl_space *array_collect_params(struct pet_array *array,
2206 __isl_take isl_space *space)
2208 if (!array)
2209 return isl_space_free(space);
2211 space = isl_space_align_params(space,
2212 isl_set_get_space(array->context));
2213 space = isl_space_align_params(space, isl_set_get_space(array->extent));
2215 return space;
2218 /* Add all parameters in "independence" to "space" and return the result.
2220 static __isl_give isl_space *independence_collect_params(
2221 struct pet_independence *independence, __isl_take isl_space *space)
2223 if (!independence)
2224 return isl_space_free(space);
2226 space = isl_space_align_params(space,
2227 isl_union_map_get_space(independence->filter));
2228 space = isl_space_align_params(space,
2229 isl_union_set_get_space(independence->local));
2231 return space;
2234 /* Collect all parameters in "scop" in a parameter space and return the result.
2236 static __isl_give isl_space *scop_collect_params(struct pet_scop *scop)
2238 isl_space *space;
2239 int i;
2241 if (!scop)
2242 return NULL;
2244 space = isl_set_get_space(scop->context);
2246 for (i = 0; i < scop->n_array; ++i)
2247 space = array_collect_params(scop->arrays[i], space);
2249 for (i = 0; i < scop->n_stmt; ++i)
2250 space = stmt_collect_params(scop->stmts[i], space);
2252 for (i = 0; i < scop->n_independence; ++i)
2253 space = independence_collect_params(scop->independences[i],
2254 space);
2256 return space;
2259 /* Add all parameters in "space" to the domain and
2260 * all access relations in "stmt".
2262 static struct pet_stmt *stmt_propagate_params(struct pet_stmt *stmt,
2263 __isl_take isl_space *space)
2265 int i;
2267 if (!stmt)
2268 goto error;
2270 stmt->domain = isl_set_align_params(stmt->domain,
2271 isl_space_copy(space));
2273 for (i = 0; i < stmt->n_arg; ++i) {
2274 stmt->args[i] = pet_expr_align_params(stmt->args[i],
2275 isl_space_copy(space));
2276 if (!stmt->args[i])
2277 goto error;
2279 stmt->body = pet_tree_align_params(stmt->body, isl_space_copy(space));
2281 if (!stmt->domain || !stmt->body)
2282 goto error;
2284 isl_space_free(space);
2285 return stmt;
2286 error:
2287 isl_space_free(space);
2288 return pet_stmt_free(stmt);
2291 /* Add all parameters in "space" to "array".
2293 static struct pet_array *array_propagate_params(struct pet_array *array,
2294 __isl_take isl_space *space)
2296 if (!array)
2297 goto error;
2299 array->context = isl_set_align_params(array->context,
2300 isl_space_copy(space));
2301 array->extent = isl_set_align_params(array->extent,
2302 isl_space_copy(space));
2303 if (array->value_bounds) {
2304 array->value_bounds = isl_set_align_params(array->value_bounds,
2305 isl_space_copy(space));
2306 if (!array->value_bounds)
2307 goto error;
2310 if (!array->context || !array->extent)
2311 goto error;
2313 isl_space_free(space);
2314 return array;
2315 error:
2316 isl_space_free(space);
2317 return pet_array_free(array);
2320 /* Add all parameters in "space" to "independence".
2322 static struct pet_independence *independence_propagate_params(
2323 struct pet_independence *independence, __isl_take isl_space *space)
2325 if (!independence)
2326 goto error;
2328 independence->filter = isl_union_map_align_params(independence->filter,
2329 isl_space_copy(space));
2330 independence->local = isl_union_set_align_params(independence->local,
2331 isl_space_copy(space));
2332 if (!independence->filter || !independence->local)
2333 goto error;
2335 isl_space_free(space);
2336 return independence;
2337 error:
2338 isl_space_free(space);
2339 return pet_independence_free(independence);
2342 /* Add all parameters in "space" to "scop".
2344 static struct pet_scop *scop_propagate_params(struct pet_scop *scop,
2345 __isl_take isl_space *space)
2347 int i;
2349 if (!scop)
2350 goto error;
2352 scop->context = isl_set_align_params(scop->context,
2353 isl_space_copy(space));
2354 scop->schedule = isl_schedule_align_params(scop->schedule,
2355 isl_space_copy(space));
2356 if (!scop->context || !scop->schedule)
2357 goto error;
2359 for (i = 0; i < scop->n_array; ++i) {
2360 scop->arrays[i] = array_propagate_params(scop->arrays[i],
2361 isl_space_copy(space));
2362 if (!scop->arrays[i])
2363 goto error;
2366 for (i = 0; i < scop->n_stmt; ++i) {
2367 scop->stmts[i] = stmt_propagate_params(scop->stmts[i],
2368 isl_space_copy(space));
2369 if (!scop->stmts[i])
2370 goto error;
2373 for (i = 0; i < scop->n_independence; ++i) {
2374 scop->independences[i] = independence_propagate_params(
2375 scop->independences[i], isl_space_copy(space));
2376 if (!scop->independences[i])
2377 goto error;
2380 isl_space_free(space);
2381 return scop;
2382 error:
2383 isl_space_free(space);
2384 return pet_scop_free(scop);
2387 /* Update all isl_sets and isl_maps in "scop" such that they all
2388 * have the same parameters.
2390 struct pet_scop *pet_scop_align_params(struct pet_scop *scop)
2392 isl_space *space;
2394 if (!scop)
2395 return NULL;
2397 space = scop_collect_params(scop);
2399 scop = scop_propagate_params(scop, space);
2401 return scop;
2404 /* Add the access relation of the give "type" of the access expression "expr"
2405 * to "accesses" and return the result.
2406 * The domain of the access relation is intersected with "domain".
2407 * If "tag" is set, then the access relation is tagged with
2408 * the corresponding reference identifier.
2410 static __isl_give isl_union_map *expr_collect_access(__isl_keep pet_expr *expr,
2411 enum pet_expr_access_type type, int tag,
2412 __isl_take isl_union_map *accesses, __isl_keep isl_union_set *domain)
2414 isl_union_map *access;
2416 access = pet_expr_access_get_access(expr, type);
2417 access = isl_union_map_intersect_domain(access,
2418 isl_union_set_copy(domain));
2419 if (tag)
2420 access = pet_expr_tag_access(expr, access);
2421 return isl_union_map_union(accesses, access);
2424 /* Internal data structure for expr_collect_accesses.
2426 * "type" is the type of accesses we want to collect.
2427 * "tag" is set if the access relations should be tagged with
2428 * the corresponding reference identifiers.
2429 * "domain" are constraints on the domain of the access relations.
2430 * "accesses" collects the results.
2432 struct pet_expr_collect_accesses_data {
2433 enum pet_expr_access_type type;
2434 int tag;
2435 isl_union_set *domain;
2437 isl_union_map *accesses;
2440 /* Add the access relation of the access expression "expr"
2441 * to data->accesses if the access expression is a read and we are collecting
2442 * reads and/or it is a write and we are collecting writes.
2443 * The domains of the access relations are intersected with data->domain.
2444 * If data->tag is set, then the access relations are tagged with
2445 * the corresponding reference identifiers.
2447 * If data->type is pet_expr_access_must_write, then we only add
2448 * the accesses that are definitely performed. Otherwise, we add
2449 * all potential accesses.
2450 * In particular, if the access has any arguments, then in case of
2451 * pet_expr_access_must_write we currently skip the access completely.
2452 * In other cases, we project out the values of the access arguments.
2454 static int expr_collect_accesses(__isl_keep pet_expr *expr, void *user)
2456 struct pet_expr_collect_accesses_data *data = user;
2458 if (!expr)
2459 return -1;
2461 if (pet_expr_is_affine(expr))
2462 return 0;
2463 if (data->type == pet_expr_access_must_write && expr->n_arg != 0)
2464 return 0;
2466 if ((data->type == pet_expr_access_may_read && expr->acc.read) ||
2467 ((data->type == pet_expr_access_may_write ||
2468 data->type == pet_expr_access_must_write) && expr->acc.write))
2469 data->accesses = expr_collect_access(expr,
2470 data->type, data->tag,
2471 data->accesses, data->domain);
2473 return data->accesses ? 0 : -1;
2476 /* Collect and return all access relations of the given "type" in "stmt".
2477 * If "tag" is set, then the access relations are tagged with
2478 * the corresponding reference identifiers.
2479 * If "type" is pet_expr_access_killed, then "stmt" is a kill statement and
2480 * we simply add the argument of the kill operation.
2482 * If we are looking for definite accesses (pet_expr_access_must_write
2483 * or pet_expr_access_killed), then we only add the accesses that are
2484 * definitely performed. Otherwise, we add all potential accesses.
2485 * In particular, if the statement has any arguments, then if we are looking
2486 * for definite accesses we currently skip the statement completely. Otherwise,
2487 * we project out the values of the statement arguments.
2488 * If the statement body is not an expression tree, then we cannot
2489 * know for sure if/when the accesses inside the tree are performed.
2490 * We therefore ignore such statements when we are looking for
2491 * definite accesses.
2493 static __isl_give isl_union_map *stmt_collect_accesses(struct pet_stmt *stmt,
2494 enum pet_expr_access_type type, int tag, __isl_take isl_space *dim)
2496 struct pet_expr_collect_accesses_data data = { type, tag };
2497 int i;
2498 int must;
2499 isl_set *domain;
2501 if (!stmt)
2502 return NULL;
2504 data.accesses = isl_union_map_empty(dim);
2506 if (type == pet_expr_access_must_write ||
2507 type == pet_expr_access_killed)
2508 must = 1;
2509 else
2510 must = 0;
2512 if (must && stmt->n_arg > 0)
2513 return data.accesses;
2514 if (must && pet_tree_get_type(stmt->body) != pet_tree_expr)
2515 return data.accesses;
2517 domain = drop_arguments(isl_set_copy(stmt->domain));
2518 data.domain = isl_union_set_from_set(domain);
2520 if (type == pet_expr_access_killed) {
2521 pet_expr *body, *arg;
2523 body = pet_tree_expr_get_expr(stmt->body);
2524 arg = pet_expr_get_arg(body, 0);
2525 data.accesses = expr_collect_access(arg,
2526 pet_expr_access_killed, tag,
2527 data.accesses, data.domain);
2528 pet_expr_free(arg);
2529 pet_expr_free(body);
2530 } else {
2531 for (i = 0; i < stmt->n_arg; ++i)
2532 data.accesses = expr_collect_access(stmt->args[i],
2533 type, tag,
2534 data.accesses, data.domain);
2535 if (pet_tree_foreach_access_expr(stmt->body,
2536 &expr_collect_accesses, &data) < 0)
2537 data.accesses = isl_union_map_free(data.accesses);
2540 isl_union_set_free(data.domain);
2542 return data.accesses;
2545 /* Is "stmt" an assignment statement?
2547 int pet_stmt_is_assign(struct pet_stmt *stmt)
2549 if (!stmt)
2550 return 0;
2551 return pet_tree_is_assign(stmt->body);
2554 /* Is "stmt" a kill statement?
2556 int pet_stmt_is_kill(struct pet_stmt *stmt)
2558 if (!stmt)
2559 return 0;
2560 return pet_tree_is_kill(stmt->body);
2563 /* Is "stmt" an assume statement?
2565 int pet_stmt_is_assume(struct pet_stmt *stmt)
2567 if (!stmt)
2568 return 0;
2569 return pet_tree_is_assume(stmt->body);
2572 /* Given a map "map" that represents an expansion from a lower-dimensional
2573 * domain to the space of "set", add those constraints of "set" to the range
2574 * that cannot be derived from the corresponding constraints on the domain.
2575 * That is, add the constraints that apply to variables in the range
2576 * that do not appear in the domain.
2578 static __isl_give isl_map *set_inner_domain(__isl_take isl_map *map,
2579 __isl_keep isl_set *dom)
2581 isl_map *copy;
2583 copy = isl_map_copy(map);
2584 copy = isl_map_intersect_range(copy, isl_set_copy(dom));
2585 dom = isl_map_domain(isl_map_copy(copy));
2586 copy = isl_map_gist_domain(copy, dom);
2587 dom = isl_map_range(copy);
2588 map = isl_map_intersect_range(map, dom);
2590 return map;
2593 /* Compute a mapping from all arrays (of structs) in scop
2594 * to their members.
2596 * If "from_outermost" is set, then the domain only consists
2597 * of outermost arrays.
2598 * If "to_innermost" is set, then the range only consists
2599 * of innermost arrays.
2601 * For each array, the construction starts from an identity mapping
2602 * on the space in which the array lives.
2603 * The references to members are then successively removed from
2604 * the domain of this mapping until the domain refers to an outer array.
2605 * Whenever a nesting level is removed from the domain,
2606 * the corresponding constraints on the extent are added to the range.
2608 static __isl_give isl_union_map *compute_to_inner(struct pet_scop *scop,
2609 int from_outermost, int to_innermost)
2611 int i;
2612 isl_union_map *to_inner;
2614 if (!scop)
2615 return NULL;
2617 to_inner = isl_union_map_empty(isl_set_get_space(scop->context));
2619 for (i = 0; i < scop->n_array; ++i) {
2620 struct pet_array *array = scop->arrays[i];
2621 isl_space *space;
2622 isl_set *set;
2623 isl_map *map;
2625 if (to_innermost && array->outer)
2626 continue;
2628 set = isl_set_copy(array->extent);
2629 space = isl_set_get_space(set);
2630 map = isl_set_identity(isl_set_universe(space));
2632 while (map && isl_map_domain_is_wrapping(map)) {
2633 if (!from_outermost)
2634 to_inner = isl_union_map_add_map(to_inner,
2635 isl_map_copy(map));
2637 map = isl_map_domain_factor_domain(map);
2638 map = set_inner_domain(map, set);
2640 isl_set_free(set);
2642 to_inner = isl_union_map_add_map(to_inner, map);
2645 return to_inner;
2648 /* Compute a mapping from all arrays (of structs) in scop
2649 * to their innermost arrays.
2651 * In particular, for each array of a primitive type, the result
2652 * contains the identity mapping on that array.
2653 * For each array involving member accesses, the result
2654 * contains a mapping from the elements of any intermediate array of structs
2655 * to all corresponding elements of the innermost nested arrays.
2657 static __isl_give isl_union_map *pet_scop_compute_any_to_inner(
2658 struct pet_scop *scop)
2660 return compute_to_inner(scop, 0, 1);
2663 /* Compute a mapping from all outermost arrays (of structs) in scop
2664 * to their innermost members.
2666 __isl_give isl_union_map *pet_scop_compute_outer_to_inner(struct pet_scop *scop)
2668 return compute_to_inner(scop, 1, 1);
2671 /* Compute a mapping from all outermost arrays (of structs) in scop
2672 * to their members, including the outermost arrays themselves.
2674 __isl_give isl_union_map *pet_scop_compute_outer_to_any(struct pet_scop *scop)
2676 return compute_to_inner(scop, 1, 0);
2679 /* Collect and return all access relations of the given "type" in "scop".
2680 * If "type" is pet_expr_access_killed, then we only add the arguments of
2681 * kill operations.
2682 * If we are looking for definite accesses (pet_expr_access_must_write
2683 * or pet_expr_access_killed), then we only add the accesses that are
2684 * definitely performed. Otherwise, we add all potential accesses.
2685 * If "tag" is set, then the access relations are tagged with
2686 * the corresponding reference identifiers.
2687 * For accesses to structures, the returned access relation accesses
2688 * all individual fields in the structures.
2690 static __isl_give isl_union_map *scop_collect_accesses(struct pet_scop *scop,
2691 enum pet_expr_access_type type, int tag)
2693 int i;
2694 isl_union_map *accesses;
2695 isl_union_set *arrays;
2696 isl_union_map *to_inner;
2698 if (!scop)
2699 return NULL;
2701 accesses = isl_union_map_empty(isl_set_get_space(scop->context));
2703 for (i = 0; i < scop->n_stmt; ++i) {
2704 struct pet_stmt *stmt = scop->stmts[i];
2705 isl_union_map *accesses_i;
2706 isl_space *space;
2708 if (type == pet_expr_access_killed && !pet_stmt_is_kill(stmt))
2709 continue;
2711 space = isl_set_get_space(scop->context);
2712 accesses_i = stmt_collect_accesses(stmt, type, tag, space);
2713 accesses = isl_union_map_union(accesses, accesses_i);
2716 arrays = isl_union_set_empty(isl_union_map_get_space(accesses));
2717 for (i = 0; i < scop->n_array; ++i) {
2718 isl_set *extent = isl_set_copy(scop->arrays[i]->extent);
2719 arrays = isl_union_set_add_set(arrays, extent);
2721 accesses = isl_union_map_intersect_range(accesses, arrays);
2723 to_inner = pet_scop_compute_any_to_inner(scop);
2724 accesses = isl_union_map_apply_range(accesses, to_inner);
2726 return accesses;
2729 /* Return the potential read access relation.
2731 __isl_give isl_union_map *pet_scop_get_may_reads(struct pet_scop *scop)
2733 return scop_collect_accesses(scop, pet_expr_access_may_read, 0);
2736 /* Return the potential write access relation.
2738 __isl_give isl_union_map *pet_scop_get_may_writes(struct pet_scop *scop)
2740 return scop_collect_accesses(scop, pet_expr_access_may_write, 0);
2743 /* Return the definite write access relation.
2745 __isl_give isl_union_map *pet_scop_get_must_writes(struct pet_scop *scop)
2747 return scop_collect_accesses(scop, pet_expr_access_must_write, 0);
2750 /* Return the definite kill access relation.
2752 __isl_give isl_union_map *pet_scop_get_must_kills(struct pet_scop *scop)
2754 return scop_collect_accesses(scop, pet_expr_access_killed, 0);
2757 /* Return the tagged potential read access relation.
2759 __isl_give isl_union_map *pet_scop_get_tagged_may_reads(
2760 struct pet_scop *scop)
2762 return scop_collect_accesses(scop, pet_expr_access_may_read, 1);
2765 /* Return the tagged potential write access relation.
2767 __isl_give isl_union_map *pet_scop_get_tagged_may_writes(
2768 struct pet_scop *scop)
2770 return scop_collect_accesses(scop, pet_expr_access_may_write, 1);
2773 /* Return the tagged definite write access relation.
2775 __isl_give isl_union_map *pet_scop_get_tagged_must_writes(
2776 struct pet_scop *scop)
2778 return scop_collect_accesses(scop, pet_expr_access_must_write, 1);
2781 /* Return the tagged definite kill access relation.
2783 __isl_give isl_union_map *pet_scop_get_tagged_must_kills(
2784 struct pet_scop *scop)
2786 return scop_collect_accesses(scop, pet_expr_access_killed, 1);
2789 /* Collect and return the set of all statement instances in "scop".
2791 __isl_give isl_union_set *pet_scop_get_instance_set(struct pet_scop *scop)
2793 int i;
2794 isl_set *domain_i;
2795 isl_union_set *domain;
2797 if (!scop)
2798 return NULL;
2800 domain = isl_union_set_empty(isl_set_get_space(scop->context));
2802 for (i = 0; i < scop->n_stmt; ++i) {
2803 domain_i = isl_set_copy(scop->stmts[i]->domain);
2804 if (scop->stmts[i]->n_arg > 0)
2805 domain_i = isl_map_domain(isl_set_unwrap(domain_i));
2806 domain = isl_union_set_add_set(domain, domain_i);
2809 return domain;
2812 /* Return the context of "scop".
2814 __isl_give isl_set *pet_scop_get_context(__isl_keep pet_scop *scop)
2816 if (!scop)
2817 return NULL;
2819 return isl_set_copy(scop->context);
2822 /* Return the schedule of "scop".
2824 __isl_give isl_schedule *pet_scop_get_schedule(__isl_keep pet_scop *scop)
2826 if (!scop)
2827 return NULL;
2829 return isl_schedule_copy(scop->schedule);
2832 /* Add a reference identifier to all access expressions in "stmt".
2833 * "n_ref" points to an integer that contains the sequence number
2834 * of the next reference.
2836 static struct pet_stmt *stmt_add_ref_ids(struct pet_stmt *stmt, int *n_ref)
2838 int i;
2840 if (!stmt)
2841 return NULL;
2843 for (i = 0; i < stmt->n_arg; ++i) {
2844 stmt->args[i] = pet_expr_add_ref_ids(stmt->args[i], n_ref);
2845 if (!stmt->args[i])
2846 return pet_stmt_free(stmt);
2849 stmt->body = pet_tree_add_ref_ids(stmt->body, n_ref);
2850 if (!stmt->body)
2851 return pet_stmt_free(stmt);
2853 return stmt;
2856 /* Add a reference identifier to all access expressions in "scop".
2858 struct pet_scop *pet_scop_add_ref_ids(struct pet_scop *scop)
2860 int i;
2861 int n_ref;
2863 if (!scop)
2864 return NULL;
2866 n_ref = 0;
2867 for (i = 0; i < scop->n_stmt; ++i) {
2868 scop->stmts[i] = stmt_add_ref_ids(scop->stmts[i], &n_ref);
2869 if (!scop->stmts[i])
2870 return pet_scop_free(scop);
2873 return scop;
2876 /* Reset the user pointer on all parameter ids in "array".
2878 static struct pet_array *array_anonymize(struct pet_array *array)
2880 if (!array)
2881 return NULL;
2883 array->context = isl_set_reset_user(array->context);
2884 array->extent = isl_set_reset_user(array->extent);
2885 if (!array->context || !array->extent)
2886 return pet_array_free(array);
2888 return array;
2891 /* Reset the user pointer on all parameter and tuple ids in "stmt".
2893 static struct pet_stmt *stmt_anonymize(struct pet_stmt *stmt)
2895 int i;
2897 if (!stmt)
2898 return NULL;
2900 stmt->domain = isl_set_reset_user(stmt->domain);
2901 if (!stmt->domain)
2902 return pet_stmt_free(stmt);
2904 for (i = 0; i < stmt->n_arg; ++i) {
2905 stmt->args[i] = pet_expr_anonymize(stmt->args[i]);
2906 if (!stmt->args[i])
2907 return pet_stmt_free(stmt);
2910 stmt->body = pet_tree_anonymize(stmt->body);
2911 if (!stmt->body)
2912 return pet_stmt_free(stmt);
2914 return stmt;
2917 /* Reset the user pointer on the tuple ids and all parameter ids
2918 * in "implication".
2920 static struct pet_implication *implication_anonymize(
2921 struct pet_implication *implication)
2923 if (!implication)
2924 return NULL;
2926 implication->extension = isl_map_reset_user(implication->extension);
2927 if (!implication->extension)
2928 return pet_implication_free(implication);
2930 return implication;
2933 /* Reset the user pointer on the tuple ids and all parameter ids
2934 * in "independence".
2936 static struct pet_independence *independence_anonymize(
2937 struct pet_independence *independence)
2939 if (!independence)
2940 return NULL;
2942 independence->filter = isl_union_map_reset_user(independence->filter);
2943 independence->local = isl_union_set_reset_user(independence->local);
2944 if (!independence->filter || !independence->local)
2945 return pet_independence_free(independence);
2947 return independence;
2950 /* Reset the user pointer on all parameter and tuple ids in "scop".
2952 struct pet_scop *pet_scop_anonymize(struct pet_scop *scop)
2954 int i;
2956 if (!scop)
2957 return NULL;
2959 scop->context = isl_set_reset_user(scop->context);
2960 scop->context_value = isl_set_reset_user(scop->context_value);
2961 scop->schedule = isl_schedule_reset_user(scop->schedule);
2962 if (!scop->context || !scop->context_value || !scop->schedule)
2963 return pet_scop_free(scop);
2965 for (i = 0; i < scop->n_array; ++i) {
2966 scop->arrays[i] = array_anonymize(scop->arrays[i]);
2967 if (!scop->arrays[i])
2968 return pet_scop_free(scop);
2971 for (i = 0; i < scop->n_stmt; ++i) {
2972 scop->stmts[i] = stmt_anonymize(scop->stmts[i]);
2973 if (!scop->stmts[i])
2974 return pet_scop_free(scop);
2977 for (i = 0; i < scop->n_implication; ++i) {
2978 scop->implications[i] =
2979 implication_anonymize(scop->implications[i]);
2980 if (!scop->implications[i])
2981 return pet_scop_free(scop);
2984 for (i = 0; i < scop->n_independence; ++i) {
2985 scop->independences[i] =
2986 independence_anonymize(scop->independences[i]);
2987 if (!scop->independences[i])
2988 return pet_scop_free(scop);
2991 return scop;
2994 /* Compute the gist of the iteration domain and all access relations
2995 * of "stmt" based on the constraints on the parameters specified by "context"
2996 * and the constraints on the values of nested accesses specified
2997 * by "value_bounds".
2999 static struct pet_stmt *stmt_gist(struct pet_stmt *stmt,
3000 __isl_keep isl_set *context, __isl_keep isl_union_map *value_bounds)
3002 int i;
3003 isl_set *domain;
3005 if (!stmt)
3006 return NULL;
3008 domain = isl_set_copy(stmt->domain);
3009 if (stmt->n_arg > 0)
3010 domain = isl_map_domain(isl_set_unwrap(domain));
3012 domain = isl_set_intersect_params(domain, isl_set_copy(context));
3014 for (i = 0; i < stmt->n_arg; ++i) {
3015 stmt->args[i] = pet_expr_gist(stmt->args[i],
3016 domain, value_bounds);
3017 if (!stmt->args[i])
3018 goto error;
3021 stmt->body = pet_tree_gist(stmt->body, domain, value_bounds);
3022 if (!stmt->body)
3023 goto error;
3025 isl_set_free(domain);
3027 domain = isl_set_universe(pet_stmt_get_space(stmt));
3028 domain = isl_set_intersect_params(domain, isl_set_copy(context));
3029 if (stmt->n_arg > 0)
3030 domain = pet_value_bounds_apply(domain, stmt->n_arg, stmt->args,
3031 value_bounds);
3032 stmt->domain = isl_set_gist(stmt->domain, domain);
3033 if (!stmt->domain)
3034 return pet_stmt_free(stmt);
3036 return stmt;
3037 error:
3038 isl_set_free(domain);
3039 return pet_stmt_free(stmt);
3042 /* Compute the gist of the extent of the array
3043 * based on the constraints on the parameters specified by "context".
3045 * If "context" is empty then do not perform the gist
3046 * since that would drop any information about the extent.
3048 static struct pet_array *array_gist(struct pet_array *array,
3049 __isl_keep isl_set *context)
3051 isl_bool empty;
3053 empty = isl_set_is_empty(context);
3054 if (empty < 0)
3055 return pet_array_free(array);
3056 if (empty)
3057 return array;
3059 if (!array)
3060 return NULL;
3062 array->extent = isl_set_gist_params(array->extent,
3063 isl_set_copy(context));
3064 if (!array->extent)
3065 return pet_array_free(array);
3067 return array;
3070 /* Compute the gist of all sets and relations in "scop"
3071 * based on the constraints on the parameters specified by "scop->context"
3072 * and the constraints on the values of nested accesses specified
3073 * by "value_bounds".
3075 struct pet_scop *pet_scop_gist(struct pet_scop *scop,
3076 __isl_keep isl_union_map *value_bounds)
3078 int i;
3080 if (!scop)
3081 return NULL;
3083 scop->context = isl_set_coalesce(scop->context);
3084 if (!scop->context)
3085 return pet_scop_free(scop);
3087 scop->schedule = isl_schedule_gist_domain_params(scop->schedule,
3088 isl_set_copy(scop->context));
3089 if (!scop->schedule)
3090 return pet_scop_free(scop);
3092 for (i = 0; i < scop->n_array; ++i) {
3093 scop->arrays[i] = array_gist(scop->arrays[i], scop->context);
3094 if (!scop->arrays[i])
3095 return pet_scop_free(scop);
3098 for (i = 0; i < scop->n_stmt; ++i) {
3099 scop->stmts[i] = stmt_gist(scop->stmts[i], scop->context,
3100 value_bounds);
3101 if (!scop->stmts[i])
3102 return pet_scop_free(scop);
3105 return scop;
3108 /* Intersect the context of "scop" with "context".
3109 * To ensure that we don't introduce any unnamed parameters in
3110 * the context of "scop", we first remove the unnamed parameters
3111 * from "context".
3113 struct pet_scop *pet_scop_restrict_context(struct pet_scop *scop,
3114 __isl_take isl_set *context)
3116 if (!scop)
3117 goto error;
3119 context = pet_nested_remove_from_set(context);
3120 scop->context = isl_set_intersect(scop->context, context);
3121 if (!scop->context)
3122 return pet_scop_free(scop);
3124 return scop;
3125 error:
3126 isl_set_free(context);
3127 return pet_scop_free(scop);
3130 /* Drop the current context of "scop". That is, replace the context
3131 * by a universal set.
3133 struct pet_scop *pet_scop_reset_context(struct pet_scop *scop)
3135 isl_space *space;
3137 if (!scop)
3138 return NULL;
3140 space = isl_set_get_space(scop->context);
3141 isl_set_free(scop->context);
3142 scop->context = isl_set_universe(space);
3143 if (!scop->context)
3144 return pet_scop_free(scop);
3146 return scop;
3149 /* Append "array" to the arrays of "scop".
3151 struct pet_scop *pet_scop_add_array(struct pet_scop *scop,
3152 struct pet_array *array)
3154 isl_ctx *ctx;
3155 struct pet_array **arrays;
3157 if (!array || !scop)
3158 goto error;
3160 ctx = isl_set_get_ctx(scop->context);
3161 arrays = isl_realloc_array(ctx, scop->arrays, struct pet_array *,
3162 scop->n_array + 1);
3163 if (!arrays)
3164 goto error;
3165 scop->arrays = arrays;
3166 scop->arrays[scop->n_array] = array;
3167 scop->n_array++;
3168 scop->context = isl_set_intersect_params(scop->context,
3169 isl_set_copy(array->context));
3170 if (!scop->context)
3171 return pet_scop_free(scop);
3173 return scop;
3174 error:
3175 pet_array_free(array);
3176 return pet_scop_free(scop);
3179 /* Create an index expression for an access to a virtual array
3180 * representing the result of a condition.
3181 * Unlike other accessed data, the id of the array is NULL as
3182 * there is no ValueDecl in the program corresponding to the virtual
3183 * array.
3184 * The index expression is created as an identity mapping on "space".
3185 * That is, the dimension of the array is the same as that of "space".
3187 __isl_give isl_multi_pw_aff *pet_create_test_index(__isl_take isl_space *space,
3188 int test_nr)
3190 isl_id *id;
3191 char name[50];
3193 snprintf(name, sizeof(name), "__pet_test_%d", test_nr);
3194 id = isl_id_alloc(isl_space_get_ctx(space), name, NULL);
3195 space = isl_space_map_from_set(space);
3196 space = isl_space_set_tuple_id(space, isl_dim_out, id);
3197 return isl_multi_pw_aff_identity(space);
3200 /* Add an array with the given extent to the list
3201 * of arrays in "scop" and return the extended pet_scop.
3202 * Specifically, the extent is determined by the image of "domain"
3203 * under "index".
3204 * "int_size" is the number of bytes needed to represent values of type "int".
3205 * The array is marked as attaining values 0 and 1 only and
3206 * as each element being assigned at most once.
3208 struct pet_scop *pet_scop_add_boolean_array(struct pet_scop *scop,
3209 __isl_take isl_set *domain, __isl_take isl_multi_pw_aff *index,
3210 int int_size)
3212 isl_ctx *ctx;
3213 isl_space *space;
3214 struct pet_array *array;
3215 isl_map *access;
3217 if (!scop || !domain || !index)
3218 goto error;
3220 ctx = isl_multi_pw_aff_get_ctx(index);
3221 array = isl_calloc_type(ctx, struct pet_array);
3222 if (!array)
3223 goto error;
3225 access = isl_map_from_multi_pw_aff(index);
3226 access = isl_map_intersect_domain(access, domain);
3227 array->extent = isl_map_range(access);
3228 space = isl_space_params_alloc(ctx, 0);
3229 array->context = isl_set_universe(space);
3230 space = isl_space_set_alloc(ctx, 0, 1);
3231 array->value_bounds = isl_set_universe(space);
3232 array->value_bounds = isl_set_lower_bound_si(array->value_bounds,
3233 isl_dim_set, 0, 0);
3234 array->value_bounds = isl_set_upper_bound_si(array->value_bounds,
3235 isl_dim_set, 0, 1);
3236 array->element_type = strdup("int");
3237 array->element_size = int_size;
3238 array->uniquely_defined = 1;
3240 if (!array->extent || !array->context)
3241 array = pet_array_free(array);
3243 scop = pet_scop_add_array(scop, array);
3245 return scop;
3246 error:
3247 isl_set_free(domain);
3248 isl_multi_pw_aff_free(index);
3249 return pet_scop_free(scop);
3252 /* Create and return an implication on filter values equal to "satisfied"
3253 * with extension "map".
3255 static struct pet_implication *new_implication(__isl_take isl_map *map,
3256 int satisfied)
3258 isl_ctx *ctx;
3259 struct pet_implication *implication;
3261 if (!map)
3262 return NULL;
3263 ctx = isl_map_get_ctx(map);
3264 implication = isl_alloc_type(ctx, struct pet_implication);
3265 if (!implication)
3266 goto error;
3268 implication->extension = map;
3269 implication->satisfied = satisfied;
3271 return implication;
3272 error:
3273 isl_map_free(map);
3274 return NULL;
3277 /* Add an implication on filter values equal to "satisfied"
3278 * with extension "map" to "scop".
3280 struct pet_scop *pet_scop_add_implication(struct pet_scop *scop,
3281 __isl_take isl_map *map, int satisfied)
3283 isl_ctx *ctx;
3284 struct pet_implication *implication;
3285 struct pet_implication **implications;
3287 implication = new_implication(map, satisfied);
3288 if (!scop || !implication)
3289 goto error;
3291 ctx = isl_set_get_ctx(scop->context);
3292 implications = isl_realloc_array(ctx, scop->implications,
3293 struct pet_implication *,
3294 scop->n_implication + 1);
3295 if (!implications)
3296 goto error;
3297 scop->implications = implications;
3298 scop->implications[scop->n_implication] = implication;
3299 scop->n_implication++;
3301 return scop;
3302 error:
3303 pet_implication_free(implication);
3304 return pet_scop_free(scop);
3307 /* Create and return a function that maps the iteration domains
3308 * of the statements in "scop" onto their outer "n" dimensions.
3309 * "space" is the parameters space of the created function.
3311 static __isl_give isl_union_pw_multi_aff *outer_projection(
3312 struct pet_scop *scop, __isl_take isl_space *space, int n)
3314 int i;
3315 isl_union_pw_multi_aff *res;
3317 res = isl_union_pw_multi_aff_empty(space);
3319 if (!scop)
3320 return isl_union_pw_multi_aff_free(res);
3322 for (i = 0; i < scop->n_stmt; ++i) {
3323 struct pet_stmt *stmt = scop->stmts[i];
3324 isl_space *space;
3325 isl_multi_aff *ma;
3326 isl_pw_multi_aff *pma;
3328 space = pet_stmt_get_space(stmt);
3329 ma = pet_prefix_projection(space, n);
3330 pma = isl_pw_multi_aff_from_multi_aff(ma);
3331 res = isl_union_pw_multi_aff_add_pw_multi_aff(res, pma);
3334 return res;
3337 /* Add an independence to "scop" for the inner iterator of "domain"
3338 * with local variables "local", where "domain" represents the outer
3339 * loop iterators of all statements in "scop".
3340 * If "sign" is positive, then the inner iterator increases.
3341 * Otherwise it decreases.
3343 * The independence is supposed to filter out any dependence of
3344 * an iteration of domain on a previous iteration along the inner dimension.
3345 * We therefore create a mapping from an iteration to later iterations and
3346 * then plug in the projection of the iterations domains of "scop"
3347 * onto the outer loop iterators.
3349 struct pet_scop *pet_scop_set_independent(struct pet_scop *scop,
3350 __isl_keep isl_set *domain, __isl_take isl_union_set *local, int sign)
3352 int i, dim;
3353 isl_space *space;
3354 isl_map *map;
3355 isl_union_map *independence;
3356 isl_union_pw_multi_aff *proj;
3358 if (!scop || !domain || !local)
3359 goto error;
3361 dim = isl_set_dim(domain, isl_dim_set);
3362 space = isl_space_map_from_set(isl_set_get_space(domain));
3363 map = isl_map_universe(space);
3364 for (i = 0; i + 1 < dim; ++i)
3365 map = isl_map_equate(map, isl_dim_in, i, isl_dim_out, i);
3366 if (sign > 0)
3367 map = isl_map_order_lt(map,
3368 isl_dim_in, dim - 1, isl_dim_out, dim - 1);
3369 else
3370 map = isl_map_order_gt(map,
3371 isl_dim_in, dim - 1, isl_dim_out, dim - 1);
3373 independence = isl_union_map_from_map(map);
3374 space = isl_space_params(isl_set_get_space(domain));
3375 proj = outer_projection(scop, space, dim);
3376 independence = isl_union_map_preimage_domain_union_pw_multi_aff(
3377 independence, isl_union_pw_multi_aff_copy(proj));
3378 independence = isl_union_map_preimage_range_union_pw_multi_aff(
3379 independence, proj);
3381 scop = pet_scop_add_independence(scop, independence, local);
3383 return scop;
3384 error:
3385 isl_union_set_free(local);
3386 return pet_scop_free(scop);
3389 /* Given an access expression, check if it is data dependent.
3390 * If so, set *found and abort the search.
3392 static int is_data_dependent(__isl_keep pet_expr *expr, void *user)
3394 int *found = user;
3396 if (pet_expr_get_n_arg(expr) > 0) {
3397 *found = 1;
3398 return -1;
3401 return 0;
3404 /* Does "scop" contain any data dependent accesses?
3406 * Check the body of each statement for such accesses.
3408 int pet_scop_has_data_dependent_accesses(struct pet_scop *scop)
3410 int i;
3411 int found = 0;
3413 if (!scop)
3414 return -1;
3416 for (i = 0; i < scop->n_stmt; ++i) {
3417 int r = pet_tree_foreach_access_expr(scop->stmts[i]->body,
3418 &is_data_dependent, &found);
3419 if (r < 0 && !found)
3420 return -1;
3421 if (found)
3422 return found;
3425 return found;
3428 /* Does "scop" contain and data dependent conditions?
3430 int pet_scop_has_data_dependent_conditions(struct pet_scop *scop)
3432 int i;
3434 if (!scop)
3435 return -1;
3437 for (i = 0; i < scop->n_stmt; ++i)
3438 if (scop->stmts[i]->n_arg > 0)
3439 return 1;
3441 return 0;
3444 /* Keep track of the "input" file inside the (extended) "scop".
3446 struct pet_scop *pet_scop_set_input_file(struct pet_scop *scop, FILE *input)
3448 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
3450 if (!scop)
3451 return NULL;
3453 ext->input = input;
3455 return scop;
3458 /* Print the original code corresponding to "scop" to printer "p".
3460 * pet_scop_print_original can only be called from
3461 * a pet_transform_C_source callback. This means that the input
3462 * file is stored in the extended scop and that the printer prints
3463 * to a file.
3465 __isl_give isl_printer *pet_scop_print_original(struct pet_scop *scop,
3466 __isl_take isl_printer *p)
3468 struct pet_scop_ext *ext = (struct pet_scop_ext *) scop;
3469 FILE *output;
3470 unsigned start, end;
3472 if (!scop || !p)
3473 return isl_printer_free(p);
3475 if (!ext->input)
3476 isl_die(isl_printer_get_ctx(p), isl_error_invalid,
3477 "no input file stored in scop",
3478 return isl_printer_free(p));
3480 output = isl_printer_get_file(p);
3481 if (!output)
3482 return isl_printer_free(p);
3484 start = pet_loc_get_start(scop->loc);
3485 end = pet_loc_get_end(scop->loc);
3486 if (copy(ext->input, output, start, end) < 0)
3487 return isl_printer_free(p);
3489 return p;