2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2014 Ecole Normale Superieure. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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
36 #include <isl/constraint.h>
37 #include <isl/union_set.h>
41 #include "expr_access_type.h"
48 #include "value_bounds.h"
50 /* pet_scop with extra information that is used during parsing and printing.
52 * In particular, we keep track of conditions under which we want
53 * to skip the rest of the current loop iteration (skip[pet_skip_now])
54 * and of conditions under which we want to skip subsequent
55 * loop iterations (skip[pet_skip_later]).
57 * The conditions are represented as index expressions defined
58 * over the outer loop iterators. The index expression is either
59 * a boolean affine expression or an access to a variable, which
60 * is assumed to attain values zero and one. The condition holds
61 * if the variable has value one or if the affine expression
62 * has value one (typically for only part of the domain).
64 * A missing condition (skip[type] == NULL) means that we don't want
67 * Additionally, we keep track of the original input file
68 * inside pet_transform_C_source.
73 isl_multi_pw_aff
*skip
[2];
77 /* Construct a pet_stmt with given domain and statement number from a pet_tree.
78 * The input domain is anonymous and is the same as the domains
79 * of the access expressions inside "tree".
80 * These domains are modified to include the name of the statement.
81 * This name is given by tree->label if it is non-NULL.
82 * Otherwise, the name is constructed as S_<id>.
84 struct pet_stmt
*pet_stmt_from_pet_tree(__isl_take isl_set
*domain
,
85 int id
, __isl_take pet_tree
*tree
)
87 struct pet_stmt
*stmt
;
93 isl_multi_pw_aff
*add_name
;
99 ctx
= pet_tree_get_ctx(tree
);
100 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
105 label
= isl_id_copy(tree
->label
);
107 snprintf(name
, sizeof(name
), "S_%d", id
);
108 label
= isl_id_alloc(ctx
, name
, NULL
);
110 domain
= isl_set_set_tuple_id(domain
, label
);
111 space
= isl_set_get_space(domain
);
112 space
= pet_nested_remove_from_space(space
);
113 sched
= isl_map_universe(isl_space_from_domain(isl_space_copy(space
)));
114 ma
= pet_prefix_projection(space
, isl_space_dim(space
, isl_dim_set
));
116 add_name
= isl_multi_pw_aff_from_multi_aff(ma
);
117 tree
= pet_tree_update_domain(tree
, add_name
);
119 stmt
->loc
= pet_tree_get_loc(tree
);
120 stmt
->domain
= domain
;
121 stmt
->schedule
= sched
;
124 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
125 return pet_stmt_free(stmt
);
129 isl_set_free(domain
);
134 void *pet_stmt_free(struct pet_stmt
*stmt
)
141 pet_loc_free(stmt
->loc
);
142 isl_set_free(stmt
->domain
);
143 isl_map_free(stmt
->schedule
);
144 pet_tree_free(stmt
->body
);
146 for (i
= 0; i
< stmt
->n_arg
; ++i
)
147 pet_expr_free(stmt
->args
[i
]);
154 /* Return the iteration space of "stmt".
156 * If the statement has arguments, then stmt->domain is a wrapped map
157 * mapping the iteration domain to the values of the arguments
158 * for which this statement is executed.
159 * In this case, we need to extract the domain space of this wrapped map.
161 __isl_give isl_space
*pet_stmt_get_space(struct pet_stmt
*stmt
)
168 space
= isl_set_get_space(stmt
->domain
);
169 if (isl_space_is_wrapping(space
))
170 space
= isl_space_domain(isl_space_unwrap(space
));
175 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
182 fprintf(stderr
, "%*s%d\n", indent
, "", pet_loc_get_line(stmt
->loc
));
183 fprintf(stderr
, "%*s", indent
, "");
184 isl_set_dump(stmt
->domain
);
185 fprintf(stderr
, "%*s", indent
, "");
186 isl_map_dump(stmt
->schedule
);
187 pet_tree_dump_with_indent(stmt
->body
, indent
);
188 for (i
= 0; i
< stmt
->n_arg
; ++i
)
189 pet_expr_dump_with_indent(stmt
->args
[i
], indent
+ 2);
192 void pet_stmt_dump(struct pet_stmt
*stmt
)
197 /* Allocate a new pet_type with the given "name" and "definition".
199 struct pet_type
*pet_type_alloc(isl_ctx
*ctx
, const char *name
,
200 const char *definition
)
202 struct pet_type
*type
;
204 type
= isl_alloc_type(ctx
, struct pet_type
);
208 type
->name
= strdup(name
);
209 type
->definition
= strdup(definition
);
211 if (!type
->name
|| !type
->definition
)
212 return pet_type_free(type
);
217 /* Free "type" and return NULL.
219 struct pet_type
*pet_type_free(struct pet_type
*type
)
225 free(type
->definition
);
231 struct pet_array
*pet_array_free(struct pet_array
*array
)
236 isl_set_free(array
->context
);
237 isl_set_free(array
->extent
);
238 isl_set_free(array
->value_bounds
);
239 free(array
->element_type
);
245 void pet_array_dump(struct pet_array
*array
)
250 isl_set_dump(array
->context
);
251 isl_set_dump(array
->extent
);
252 isl_set_dump(array
->value_bounds
);
253 fprintf(stderr
, "%s%s%s\n", array
->element_type
,
254 array
->element_is_record
? " element-is-record" : "",
255 array
->live_out
? " live-out" : "");
258 /* Alloc a pet_scop structure, with extra room for information that
259 * is only used during parsing.
261 struct pet_scop
*pet_scop_alloc(isl_ctx
*ctx
)
263 return &isl_calloc_type(ctx
, struct pet_scop_ext
)->scop
;
266 /* Construct a pet_scop in the given space and with room for n statements.
268 * The context is initialized as a universe set in "space".
270 * Since no information on the location is known at this point,
271 * scop->loc is initialized with pet_loc_dummy.
273 static struct pet_scop
*scop_alloc(__isl_take isl_space
*space
, int n
)
276 struct pet_scop
*scop
;
281 ctx
= isl_space_get_ctx(space
);
282 scop
= pet_scop_alloc(ctx
);
286 scop
->context
= isl_set_universe(isl_space_copy(space
));
287 scop
->context_value
= isl_set_universe(isl_space_params(space
));
288 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
289 if (!scop
->context
|| !scop
->stmts
)
290 return pet_scop_free(scop
);
292 scop
->loc
= &pet_loc_dummy
;
297 isl_space_free(space
);
301 /* Construct a pet_scop in the given space containing 0 statements.
303 struct pet_scop
*pet_scop_empty(__isl_take isl_space
*space
)
305 return scop_alloc(space
, 0);
308 /* Given either an iteration domain or a wrapped map with
309 * the iteration domain in the domain and some arguments
310 * in the range, return the iteration domain.
311 * That is, drop the arguments if there are any.
313 static __isl_give isl_set
*drop_arguments(__isl_take isl_set
*domain
)
315 if (isl_set_is_wrapping(domain
))
316 domain
= isl_map_domain(isl_set_unwrap(domain
));
320 /* Update "context" with the constraints imposed on the outer iteration
321 * domain by access expression "expr".
322 * "context" lives in an anonymous space, while the domain of the access
323 * relation of "expr" refers to a particular statement.
324 * This reference therefore needs to be stripped off.
326 static __isl_give isl_set
*access_extract_context(__isl_keep pet_expr
*expr
,
327 __isl_take isl_set
*context
)
329 isl_multi_pw_aff
*mpa
;
332 mpa
= pet_expr_access_get_index(expr
);
333 domain
= drop_arguments(isl_multi_pw_aff_domain(mpa
));
334 domain
= isl_set_reset_tuple_id(domain
);
335 context
= isl_set_intersect(context
, domain
);
339 /* Update "context" with the constraints imposed on the outer iteration
342 * "context" lives in an anonymous space, while the domains of
343 * the access relations in "expr" refer to a particular statement.
344 * This reference therefore needs to be stripped off.
346 * If "expr" represents a conditional operator, then a parameter or outer
347 * iterator value needs to be valid for the condition and
348 * for at least one of the remaining two arguments.
349 * If the condition is an affine expression, then we can be a bit more specific.
350 * The value then has to be valid for the second argument for
351 * non-zero accesses and valid for the third argument for zero accesses.
353 * If "expr" represents a kill statement, then its argument is the entire
354 * extent of the array being killed. Do not update "context" based
355 * on this argument as that would impose constraints that ensure that
356 * the array is non-empty.
358 static __isl_give isl_set
*expr_extract_context(__isl_keep pet_expr
*expr
,
359 __isl_take isl_set
*context
)
363 if (expr
->type
== pet_expr_op
&& expr
->op
== pet_op_kill
)
366 if (expr
->type
== pet_expr_op
&& expr
->op
== pet_op_cond
) {
368 isl_set
*context1
, *context2
;
370 is_aff
= pet_expr_is_affine(expr
->args
[0]);
374 context
= expr_extract_context(expr
->args
[0], context
);
375 context1
= expr_extract_context(expr
->args
[1],
376 isl_set_copy(context
));
377 context2
= expr_extract_context(expr
->args
[2], context
);
380 isl_multi_pw_aff
*mpa
;
384 mpa
= pet_expr_access_get_index(expr
->args
[0]);
385 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, 0);
386 isl_multi_pw_aff_free(mpa
);
387 zero_set
= drop_arguments(isl_pw_aff_zero_set(pa
));
388 zero_set
= isl_set_reset_tuple_id(zero_set
);
389 context1
= isl_set_subtract(context1
,
390 isl_set_copy(zero_set
));
391 context2
= isl_set_intersect(context2
, zero_set
);
394 context
= isl_set_union(context1
, context2
);
395 context
= isl_set_coalesce(context
);
400 for (i
= 0; i
< expr
->n_arg
; ++i
)
401 context
= expr_extract_context(expr
->args
[i
], context
);
403 if (expr
->type
== pet_expr_access
)
404 context
= access_extract_context(expr
, context
);
408 isl_set_free(context
);
412 /* Is "stmt" an assume statement with an affine assumption?
414 int pet_stmt_is_affine_assume(struct pet_stmt
*stmt
)
418 return pet_tree_is_affine_assume(stmt
->body
);
421 /* Given an assume statement "stmt" with an access argument,
422 * return the index expression of the argument.
424 __isl_give isl_multi_pw_aff
*pet_stmt_assume_get_index(struct pet_stmt
*stmt
)
428 return pet_tree_assume_get_index(stmt
->body
);
431 /* Update "context" with the constraints imposed on the outer iteration
434 * If the statement is an assume statement with an affine expression,
435 * then intersect "context" with that expression.
436 * Otherwise, if the statement body is an expression tree,
437 * then intersect "context" with the context of this expression.
438 * Note that we cannot safely extract a context from subtrees
439 * of the statement body since we cannot tell when those subtrees
440 * are executed, if at all.
442 static __isl_give isl_set
*stmt_extract_context(struct pet_stmt
*stmt
,
443 __isl_take isl_set
*context
)
448 if (pet_stmt_is_affine_assume(stmt
)) {
449 isl_multi_pw_aff
*index
;
453 index
= pet_stmt_assume_get_index(stmt
);
454 pa
= isl_multi_pw_aff_get_pw_aff(index
, 0);
455 isl_multi_pw_aff_free(index
);
456 cond
= isl_pw_aff_non_zero_set(pa
);
457 cond
= isl_set_reset_tuple_id(cond
);
458 return isl_set_intersect(context
, cond
);
461 for (i
= 0; i
< stmt
->n_arg
; ++i
)
462 context
= expr_extract_context(stmt
->args
[i
], context
);
464 if (pet_tree_get_type(stmt
->body
) != pet_tree_expr
)
467 body
= pet_tree_expr_get_expr(stmt
->body
);
468 context
= expr_extract_context(body
, context
);
474 /* Construct a pet_scop in the given space that contains the given pet_stmt.
476 struct pet_scop
*pet_scop_from_pet_stmt(__isl_take isl_space
*space
,
477 struct pet_stmt
*stmt
)
479 struct pet_scop
*scop
;
482 space
= isl_space_free(space
);
484 scop
= scop_alloc(space
, 1);
488 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
492 scop
->stmts
[0] = stmt
;
493 scop
->loc
= pet_loc_copy(stmt
->loc
);
496 return pet_scop_free(scop
);
505 /* Does "mpa" represent an access to an element of an unnamed space, i.e.,
506 * does it represent an affine expression?
508 static int multi_pw_aff_is_affine(__isl_keep isl_multi_pw_aff
*mpa
)
512 has_id
= isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
);
519 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
521 static __isl_give isl_pw_aff
*indicator_function(__isl_take isl_set
*set
,
522 __isl_take isl_set
*dom
)
525 pa
= isl_set_indicator_function(set
);
526 pa
= isl_pw_aff_intersect_domain(pa
, dom
);
530 /* Return "lhs || rhs", defined on the shared definition domain.
532 static __isl_give isl_pw_aff
*pw_aff_or(__isl_take isl_pw_aff
*lhs
,
533 __isl_take isl_pw_aff
*rhs
)
538 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs
)),
539 isl_pw_aff_domain(isl_pw_aff_copy(rhs
)));
540 cond
= isl_set_union(isl_pw_aff_non_zero_set(lhs
),
541 isl_pw_aff_non_zero_set(rhs
));
542 cond
= isl_set_coalesce(cond
);
543 return indicator_function(cond
, dom
);
546 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
547 * ext may be equal to either ext1 or ext2.
549 * The two skips that need to be combined are assumed to be affine expressions.
551 * We need to skip in ext if we need to skip in either ext1 or ext2.
552 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
554 static struct pet_scop_ext
*combine_skips(struct pet_scop_ext
*ext
,
555 struct pet_scop_ext
*ext1
, struct pet_scop_ext
*ext2
,
558 isl_pw_aff
*skip
, *skip1
, *skip2
;
562 if (!ext1
->skip
[type
] && !ext2
->skip
[type
])
564 if (!ext1
->skip
[type
]) {
567 ext
->skip
[type
] = ext2
->skip
[type
];
568 ext2
->skip
[type
] = NULL
;
571 if (!ext2
->skip
[type
]) {
574 ext
->skip
[type
] = ext1
->skip
[type
];
575 ext1
->skip
[type
] = NULL
;
579 if (!multi_pw_aff_is_affine(ext1
->skip
[type
]) ||
580 !multi_pw_aff_is_affine(ext2
->skip
[type
]))
581 isl_die(isl_multi_pw_aff_get_ctx(ext1
->skip
[type
]),
582 isl_error_internal
, "can only combine affine skips",
585 skip1
= isl_multi_pw_aff_get_pw_aff(ext1
->skip
[type
], 0);
586 skip2
= isl_multi_pw_aff_get_pw_aff(ext2
->skip
[type
], 0);
587 skip
= pw_aff_or(skip1
, skip2
);
588 isl_multi_pw_aff_free(ext1
->skip
[type
]);
589 ext1
->skip
[type
] = NULL
;
590 isl_multi_pw_aff_free(ext2
->skip
[type
]);
591 ext2
->skip
[type
] = NULL
;
592 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
593 if (!ext
->skip
[type
])
598 pet_scop_free(&ext
->scop
);
602 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
603 * where type takes on the values pet_skip_now and pet_skip_later.
604 * scop may be equal to either scop1 or scop2.
606 static struct pet_scop
*scop_combine_skips(struct pet_scop
*scop
,
607 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
609 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
610 struct pet_scop_ext
*ext1
= (struct pet_scop_ext
*) scop1
;
611 struct pet_scop_ext
*ext2
= (struct pet_scop_ext
*) scop2
;
613 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_now
);
614 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_later
);
618 /* Update start and end of scop->loc to include the region from "start"
619 * to "end". In particular, if scop->loc == &pet_loc_dummy, then "scop"
620 * does not have any offset information yet and we simply take the information
621 * from "start" and "end". Otherwise, we update loc using "start" and "end".
623 struct pet_scop
*pet_scop_update_start_end(struct pet_scop
*scop
,
624 unsigned start
, unsigned end
)
629 if (scop
->loc
== &pet_loc_dummy
)
630 scop
->loc
= pet_loc_alloc(isl_set_get_ctx(scop
->context
),
631 start
, end
, -1, strdup(""));
633 scop
->loc
= pet_loc_update_start_end(scop
->loc
, start
, end
);
636 return pet_scop_free(scop
);
641 /* Update start and end of scop->loc to include the region identified
644 struct pet_scop
*pet_scop_update_start_end_from_loc(struct pet_scop
*scop
,
645 __isl_keep pet_loc
*loc
)
647 return pet_scop_update_start_end(scop
, pet_loc_get_start(loc
),
648 pet_loc_get_end(loc
));
651 /* Replace the location of "scop" by "loc".
653 struct pet_scop
*pet_scop_set_loc(struct pet_scop
*scop
,
654 __isl_take pet_loc
*loc
)
659 pet_loc_free(scop
->loc
);
669 /* Does "implication" appear in the list of implications of "scop"?
671 static int is_known_implication(struct pet_scop
*scop
,
672 struct pet_implication
*implication
)
676 for (i
= 0; i
< scop
->n_implication
; ++i
) {
677 struct pet_implication
*pi
= scop
->implications
[i
];
680 if (pi
->satisfied
!= implication
->satisfied
)
682 equal
= isl_map_is_equal(pi
->extension
, implication
->extension
);
692 /* Store the concatenation of the implications of "scop1" and "scop2"
693 * in "scop", removing duplicates (i.e., implications in "scop2" that
694 * already appear in "scop1").
696 static struct pet_scop
*scop_collect_implications(isl_ctx
*ctx
,
697 struct pet_scop
*scop
, struct pet_scop
*scop1
, struct pet_scop
*scop2
)
704 if (scop2
->n_implication
== 0) {
705 scop
->n_implication
= scop1
->n_implication
;
706 scop
->implications
= scop1
->implications
;
707 scop1
->n_implication
= 0;
708 scop1
->implications
= NULL
;
712 if (scop1
->n_implication
== 0) {
713 scop
->n_implication
= scop2
->n_implication
;
714 scop
->implications
= scop2
->implications
;
715 scop2
->n_implication
= 0;
716 scop2
->implications
= NULL
;
720 scop
->implications
= isl_calloc_array(ctx
, struct pet_implication
*,
721 scop1
->n_implication
+ scop2
->n_implication
);
722 if (!scop
->implications
)
723 return pet_scop_free(scop
);
725 for (i
= 0; i
< scop1
->n_implication
; ++i
) {
726 scop
->implications
[i
] = scop1
->implications
[i
];
727 scop1
->implications
[i
] = NULL
;
730 scop
->n_implication
= scop1
->n_implication
;
731 j
= scop1
->n_implication
;
732 for (i
= 0; i
< scop2
->n_implication
; ++i
) {
735 known
= is_known_implication(scop
, scop2
->implications
[i
]);
737 return pet_scop_free(scop
);
740 scop
->implications
[j
++] = scop2
->implications
[i
];
741 scop2
->implications
[i
] = NULL
;
743 scop
->n_implication
= j
;
748 /* Combine the offset information of "scop1" and "scop2" into "scop".
750 static struct pet_scop
*scop_combine_start_end(struct pet_scop
*scop
,
751 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
753 if (scop1
->loc
!= &pet_loc_dummy
)
754 scop
= pet_scop_update_start_end_from_loc(scop
, scop1
->loc
);
755 if (scop2
->loc
!= &pet_loc_dummy
)
756 scop
= pet_scop_update_start_end_from_loc(scop
, scop2
->loc
);
760 /* Create and return an independence that filters out the dependences
761 * in "filter" with local variables "local".
763 static struct pet_independence
*new_independence(
764 __isl_take isl_union_map
*filter
, __isl_take isl_union_set
*local
)
767 struct pet_independence
*independence
;
769 if (!filter
|| !local
)
771 ctx
= isl_union_map_get_ctx(filter
);
772 independence
= isl_alloc_type(ctx
, struct pet_independence
);
776 independence
->filter
= filter
;
777 independence
->local
= local
;
781 isl_union_map_free(filter
);
782 isl_union_set_free(local
);
786 /* Add an independence that filters out the dependences
787 * in "filter" with local variables "local" to "scop".
789 struct pet_scop
*pet_scop_add_independence(struct pet_scop
*scop
,
790 __isl_take isl_union_map
*filter
, __isl_take isl_union_set
*local
)
793 struct pet_independence
*independence
;
794 struct pet_independence
**independences
;
796 ctx
= isl_union_map_get_ctx(filter
);
797 independence
= new_independence(filter
, local
);
798 if (!scop
|| !independence
)
801 independences
= isl_realloc_array(ctx
, scop
->independences
,
802 struct pet_independence
*,
803 scop
->n_independence
+ 1);
806 scop
->independences
= independences
;
807 scop
->independences
[scop
->n_independence
] = independence
;
808 scop
->n_independence
++;
812 pet_independence_free(independence
);
817 /* Store the concatenation of the independences of "scop1" and "scop2"
820 static struct pet_scop
*scop_collect_independences(isl_ctx
*ctx
,
821 struct pet_scop
*scop
, struct pet_scop
*scop1
, struct pet_scop
*scop2
)
828 if (scop2
->n_independence
== 0) {
829 scop
->n_independence
= scop1
->n_independence
;
830 scop
->independences
= scop1
->independences
;
831 scop1
->n_independence
= 0;
832 scop1
->independences
= NULL
;
836 if (scop1
->n_independence
== 0) {
837 scop
->n_independence
= scop2
->n_independence
;
838 scop
->independences
= scop2
->independences
;
839 scop2
->n_independence
= 0;
840 scop2
->independences
= NULL
;
844 scop
->independences
= isl_calloc_array(ctx
, struct pet_independence
*,
845 scop1
->n_independence
+ scop2
->n_independence
);
846 if (!scop
->independences
)
847 return pet_scop_free(scop
);
849 for (i
= 0; i
< scop1
->n_independence
; ++i
) {
850 scop
->independences
[i
] = scop1
->independences
[i
];
851 scop1
->independences
[i
] = NULL
;
854 off
= scop1
->n_independence
;
855 for (i
= 0; i
< scop2
->n_independence
; ++i
) {
856 scop
->independences
[off
+ i
] = scop2
->independences
[i
];
857 scop2
->independences
[i
] = NULL
;
859 scop
->n_independence
= scop1
->n_independence
+ scop2
->n_independence
;
864 /* Construct a pet_scop that contains the offset information,
865 * arrays, statements and skip information in "scop1" and "scop2".
867 static struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
868 struct pet_scop
*scop2
)
872 struct pet_scop
*scop
= NULL
;
874 if (!scop1
|| !scop2
)
877 if (scop1
->n_stmt
== 0) {
878 scop2
= scop_combine_skips(scop2
, scop1
, scop2
);
879 pet_scop_free(scop1
);
883 if (scop2
->n_stmt
== 0) {
884 scop1
= scop_combine_skips(scop1
, scop1
, scop2
);
885 pet_scop_free(scop2
);
889 space
= isl_set_get_space(scop1
->context
);
890 scop
= scop_alloc(space
, scop1
->n_stmt
+ scop2
->n_stmt
);
894 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
895 scop1
->n_array
+ scop2
->n_array
);
898 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
900 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
901 scop
->stmts
[i
] = scop1
->stmts
[i
];
902 scop1
->stmts
[i
] = NULL
;
905 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
906 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
907 scop2
->stmts
[i
] = NULL
;
910 for (i
= 0; i
< scop1
->n_array
; ++i
) {
911 scop
->arrays
[i
] = scop1
->arrays
[i
];
912 scop1
->arrays
[i
] = NULL
;
915 for (i
= 0; i
< scop2
->n_array
; ++i
) {
916 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
917 scop2
->arrays
[i
] = NULL
;
920 scop
= scop_collect_implications(ctx
, scop
, scop1
, scop2
);
921 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop1
->context
));
922 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop2
->context
));
923 scop
= scop_combine_skips(scop
, scop1
, scop2
);
924 scop
= scop_combine_start_end(scop
, scop1
, scop2
);
925 scop
= scop_collect_independences(ctx
, scop
, scop1
, scop2
);
927 pet_scop_free(scop1
);
928 pet_scop_free(scop2
);
931 pet_scop_free(scop1
);
932 pet_scop_free(scop2
);
937 /* Apply the skip condition "skip" to "scop".
938 * That is, make sure "scop" is not executed when the condition holds.
940 * If "skip" is an affine expression, we add the conditions under
941 * which the expression is zero to the context and the skip conditions
943 * Otherwise, we add a filter on the variable attaining the value zero.
945 static struct pet_scop
*restrict_skip(struct pet_scop
*scop
,
946 __isl_take isl_multi_pw_aff
*skip
)
955 is_aff
= multi_pw_aff_is_affine(skip
);
960 return pet_scop_filter(scop
, skip
, 0);
962 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
963 isl_multi_pw_aff_free(skip
);
964 zero
= isl_pw_aff_zero_set(pa
);
965 scop
= pet_scop_restrict(scop
, zero
);
969 isl_multi_pw_aff_free(skip
);
970 return pet_scop_free(scop
);
973 /* Construct a pet_scop that contains the arrays, statements and
974 * skip information in "scop1" and "scop2", where the two scops
975 * are executed "in sequence". That is, breaks and continues
976 * in scop1 have an effect on scop2.
978 struct pet_scop
*pet_scop_add_seq(isl_ctx
*ctx
, struct pet_scop
*scop1
,
979 struct pet_scop
*scop2
)
981 if (scop1
&& pet_scop_has_skip(scop1
, pet_skip_now
))
982 scop2
= restrict_skip(scop2
,
983 pet_scop_get_skip(scop1
, pet_skip_now
));
984 return pet_scop_add(ctx
, scop1
, scop2
);
987 /* Construct a pet_scop that contains the arrays, statements and
988 * skip information in "scop1" and "scop2", where the two scops
989 * are executed "in parallel". That is, any break or continue
990 * in scop1 has no effect on scop2.
992 struct pet_scop
*pet_scop_add_par(isl_ctx
*ctx
, struct pet_scop
*scop1
,
993 struct pet_scop
*scop2
)
995 return pet_scop_add(ctx
, scop1
, scop2
);
998 void *pet_implication_free(struct pet_implication
*implication
)
1005 isl_map_free(implication
->extension
);
1011 void *pet_independence_free(struct pet_independence
*independence
)
1016 isl_union_map_free(independence
->filter
);
1017 isl_union_set_free(independence
->local
);
1023 struct pet_scop
*pet_scop_free(struct pet_scop
*scop
)
1026 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1030 pet_loc_free(scop
->loc
);
1031 isl_set_free(scop
->context
);
1032 isl_set_free(scop
->context_value
);
1034 for (i
= 0; i
< scop
->n_type
; ++i
)
1035 pet_type_free(scop
->types
[i
]);
1038 for (i
= 0; i
< scop
->n_array
; ++i
)
1039 pet_array_free(scop
->arrays
[i
]);
1042 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1043 pet_stmt_free(scop
->stmts
[i
]);
1045 if (scop
->implications
)
1046 for (i
= 0; i
< scop
->n_implication
; ++i
)
1047 pet_implication_free(scop
->implications
[i
]);
1048 free(scop
->implications
);
1049 if (scop
->independences
)
1050 for (i
= 0; i
< scop
->n_independence
; ++i
)
1051 pet_independence_free(scop
->independences
[i
]);
1052 free(scop
->independences
);
1053 isl_multi_pw_aff_free(ext
->skip
[pet_skip_now
]);
1054 isl_multi_pw_aff_free(ext
->skip
[pet_skip_later
]);
1059 void pet_type_dump(struct pet_type
*type
)
1064 fprintf(stderr
, "%s -> %s\n", type
->name
, type
->definition
);
1067 void pet_implication_dump(struct pet_implication
*implication
)
1072 fprintf(stderr
, "%d\n", implication
->satisfied
);
1073 isl_map_dump(implication
->extension
);
1076 void pet_scop_dump(struct pet_scop
*scop
)
1079 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1084 isl_set_dump(scop
->context
);
1085 isl_set_dump(scop
->context_value
);
1086 for (i
= 0; i
< scop
->n_type
; ++i
)
1087 pet_type_dump(scop
->types
[i
]);
1088 for (i
= 0; i
< scop
->n_array
; ++i
)
1089 pet_array_dump(scop
->arrays
[i
]);
1090 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1091 pet_stmt_dump(scop
->stmts
[i
]);
1092 for (i
= 0; i
< scop
->n_implication
; ++i
)
1093 pet_implication_dump(scop
->implications
[i
]);
1096 fprintf(stderr
, "skip\n");
1097 isl_multi_pw_aff_dump(ext
->skip
[0]);
1098 isl_multi_pw_aff_dump(ext
->skip
[1]);
1102 /* Return 1 if the two pet_arrays are equivalent.
1104 * We don't compare element_size as this may be target dependent.
1106 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
1108 if (!array1
|| !array2
)
1111 if (!isl_set_is_equal(array1
->context
, array2
->context
))
1113 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
1115 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
1117 if (array1
->value_bounds
&&
1118 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
1120 if (strcmp(array1
->element_type
, array2
->element_type
))
1122 if (array1
->element_is_record
!= array2
->element_is_record
)
1124 if (array1
->live_out
!= array2
->live_out
)
1126 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
1128 if (array1
->declared
!= array2
->declared
)
1130 if (array1
->exposed
!= array2
->exposed
)
1136 /* Return 1 if the two pet_stmts are equivalent.
1138 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
1142 if (!stmt1
|| !stmt2
)
1145 if (pet_loc_get_line(stmt1
->loc
) != pet_loc_get_line(stmt2
->loc
))
1147 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
1149 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
1151 if (!pet_tree_is_equal(stmt1
->body
, stmt2
->body
))
1153 if (stmt1
->n_arg
!= stmt2
->n_arg
)
1155 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
1156 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
1163 /* Return 1 if the two pet_types are equivalent.
1165 * We only compare the names of the types since the exact representation
1166 * of the definition may depend on the version of clang being used.
1168 int pet_type_is_equal(struct pet_type
*type1
, struct pet_type
*type2
)
1170 if (!type1
|| !type2
)
1173 if (strcmp(type1
->name
, type2
->name
))
1179 /* Return 1 if the two pet_implications are equivalent.
1181 int pet_implication_is_equal(struct pet_implication
*implication1
,
1182 struct pet_implication
*implication2
)
1184 if (!implication1
|| !implication2
)
1187 if (implication1
->satisfied
!= implication2
->satisfied
)
1189 if (!isl_map_is_equal(implication1
->extension
, implication2
->extension
))
1195 /* Return 1 if the two pet_independences are equivalent.
1197 int pet_independence_is_equal(struct pet_independence
*independence1
,
1198 struct pet_independence
*independence2
)
1200 if (!independence1
|| !independence2
)
1203 if (!isl_union_map_is_equal(independence1
->filter
,
1204 independence2
->filter
))
1206 if (!isl_union_set_is_equal(independence1
->local
, independence2
->local
))
1212 /* Return 1 if the two pet_scops are equivalent.
1214 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1218 if (!scop1
|| !scop2
)
1221 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
1223 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
1226 if (scop1
->n_type
!= scop2
->n_type
)
1228 for (i
= 0; i
< scop1
->n_type
; ++i
)
1229 if (!pet_type_is_equal(scop1
->types
[i
], scop2
->types
[i
]))
1232 if (scop1
->n_array
!= scop2
->n_array
)
1234 for (i
= 0; i
< scop1
->n_array
; ++i
)
1235 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
1238 if (scop1
->n_stmt
!= scop2
->n_stmt
)
1240 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
1241 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
1244 if (scop1
->n_implication
!= scop2
->n_implication
)
1246 for (i
= 0; i
< scop1
->n_implication
; ++i
)
1247 if (!pet_implication_is_equal(scop1
->implications
[i
],
1248 scop2
->implications
[i
]))
1251 if (scop1
->n_independence
!= scop2
->n_independence
)
1253 for (i
= 0; i
< scop1
->n_independence
; ++i
)
1254 if (!pet_independence_is_equal(scop1
->independences
[i
],
1255 scop2
->independences
[i
]))
1261 /* Does the set "extent" reference a virtual array, i.e.,
1262 * one with user pointer equal to NULL?
1263 * A virtual array does not have any members.
1265 static int extent_is_virtual_array(__isl_keep isl_set
*extent
)
1270 if (!isl_set_has_tuple_id(extent
))
1272 if (isl_set_is_wrapping(extent
))
1274 id
= isl_set_get_tuple_id(extent
);
1275 is_virtual
= !isl_id_get_user(id
);
1281 /* Intersect the initial dimensions of "array" with "domain", provided
1282 * that "array" represents a virtual array.
1284 * If "array" is virtual, then We take the preimage of "domain"
1285 * over the projection of the extent of "array" onto its initial dimensions
1286 * and intersect this extent with the result.
1288 static struct pet_array
*virtual_array_intersect_domain_prefix(
1289 struct pet_array
*array
, __isl_take isl_set
*domain
)
1295 if (!array
|| !extent_is_virtual_array(array
->extent
)) {
1296 isl_set_free(domain
);
1300 space
= isl_set_get_space(array
->extent
);
1301 n
= isl_set_dim(domain
, isl_dim_set
);
1302 ma
= pet_prefix_projection(space
, n
);
1303 domain
= isl_set_preimage_multi_aff(domain
, ma
);
1305 array
->extent
= isl_set_intersect(array
->extent
, domain
);
1307 return pet_array_free(array
);
1312 /* Intersect the initial dimensions of the domain of "stmt"
1315 * We take the preimage of "domain" over the projection of the
1316 * domain of "stmt" onto its initial dimensions and intersect
1317 * the domain of "stmt" with the result.
1319 static struct pet_stmt
*stmt_intersect_domain_prefix(struct pet_stmt
*stmt
,
1320 __isl_take isl_set
*domain
)
1329 space
= isl_set_get_space(stmt
->domain
);
1330 n
= isl_set_dim(domain
, isl_dim_set
);
1331 ma
= pet_prefix_projection(space
, n
);
1332 domain
= isl_set_preimage_multi_aff(domain
, ma
);
1334 stmt
->domain
= isl_set_intersect(stmt
->domain
, domain
);
1336 return pet_stmt_free(stmt
);
1340 isl_set_free(domain
);
1341 return pet_stmt_free(stmt
);
1344 /* Intersect the initial dimensions of the domain of "implication"
1347 * We take the preimage of "domain" over the projection of the
1348 * domain of "implication" onto its initial dimensions and intersect
1349 * the domain of "implication" with the result.
1351 static struct pet_implication
*implication_intersect_domain_prefix(
1352 struct pet_implication
*implication
, __isl_take isl_set
*domain
)
1361 space
= isl_map_get_space(implication
->extension
);
1362 n
= isl_set_dim(domain
, isl_dim_set
);
1363 ma
= pet_prefix_projection(isl_space_domain(space
), n
);
1364 domain
= isl_set_preimage_multi_aff(domain
, ma
);
1366 implication
->extension
=
1367 isl_map_intersect_domain(implication
->extension
, domain
);
1368 if (!implication
->extension
)
1369 return pet_implication_free(implication
);
1373 isl_set_free(domain
);
1374 return pet_implication_free(implication
);
1377 /* Intersect the initial dimensions of the domains in "scop" with "domain".
1379 * The extents of the virtual arrays match the iteration domains,
1380 * so if the iteration domain changes, we need to change those extents too.
1382 struct pet_scop
*pet_scop_intersect_domain_prefix(struct pet_scop
*scop
,
1383 __isl_take isl_set
*domain
)
1390 for (i
= 0; i
< scop
->n_array
; ++i
) {
1391 scop
->arrays
[i
] = virtual_array_intersect_domain_prefix(
1392 scop
->arrays
[i
], isl_set_copy(domain
));
1393 if (!scop
->arrays
[i
])
1397 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1398 scop
->stmts
[i
] = stmt_intersect_domain_prefix(scop
->stmts
[i
],
1399 isl_set_copy(domain
));
1400 if (!scop
->stmts
[i
])
1404 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1405 scop
->implications
[i
] =
1406 implication_intersect_domain_prefix(scop
->implications
[i
],
1407 isl_set_copy(domain
));
1408 if (!scop
->implications
[i
])
1409 return pet_scop_free(scop
);
1412 isl_set_free(domain
);
1415 isl_set_free(domain
);
1416 return pet_scop_free(scop
);
1419 /* Prefix the schedule of "stmt" with an extra dimension with constant
1422 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
1427 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
1428 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
1429 if (!stmt
->schedule
)
1430 return pet_stmt_free(stmt
);
1435 /* Prefix the schedules of all statements in "scop" with an extra
1436 * dimension with constant value "pos".
1438 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
1445 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1446 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
1447 if (!scop
->stmts
[i
])
1448 return pet_scop_free(scop
);
1454 /* Prefix the schedule of "stmt" with "sched".
1456 * The domain of "sched" refers the current outer loop iterators and
1457 * needs to be mapped to the iteration domain of "stmt" first
1458 * before being prepended to the schedule of "stmt".
1460 static struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
,
1461 __isl_take isl_map
*sched
)
1470 space
= pet_stmt_get_space(stmt
);
1471 n
= isl_map_dim(sched
, isl_dim_in
);
1472 ma
= pet_prefix_projection(space
, n
);
1473 sched
= isl_map_preimage_domain_multi_aff(sched
, ma
);
1474 stmt
->schedule
= isl_map_flat_range_product(sched
, stmt
->schedule
);
1475 if (!stmt
->schedule
)
1476 return pet_stmt_free(stmt
);
1480 isl_map_free(sched
);
1484 /* Update the context with respect to an embedding into a loop
1485 * with iteration domain "dom".
1486 * The input context lives in the same space as "dom".
1487 * The output context has the inner dimension removed.
1489 * An outer loop iterator value is invalid for the embedding if
1490 * any of the corresponding inner iterator values is invalid.
1491 * That is, an outer loop iterator value is valid only if all the corresponding
1492 * inner iterator values are valid.
1493 * We therefore compute the set of outer loop iterators l
1495 * forall i: dom(l,i) => valid(l,i)
1499 * forall i: not dom(l,i) or valid(l,i)
1503 * not exists i: dom(l,i) and not valid(l,i)
1507 * not exists i: (dom \ valid)(l,i)
1509 * If there are any unnamed parameters in "dom", then we consider
1510 * a parameter value to be valid if it is valid for any value of those
1511 * unnamed parameters. They are therefore projected out at the end.
1513 static __isl_give isl_set
*context_embed(__isl_take isl_set
*context
,
1514 __isl_keep isl_set
*dom
)
1518 pos
= isl_set_dim(context
, isl_dim_set
) - 1;
1519 context
= isl_set_subtract(isl_set_copy(dom
), context
);
1520 context
= isl_set_project_out(context
, isl_dim_set
, pos
, 1);
1521 context
= isl_set_complement(context
);
1522 context
= pet_nested_remove_from_set(context
);
1527 /* Update the implication with respect to an embedding into a loop
1528 * with iteration domain "dom".
1530 * Since embed_access extends virtual arrays along with the domain
1531 * of the access, we need to do the same with domain and range
1532 * of the implication. Since the original implication is only valid
1533 * within a given iteration of the loop, the extended implication
1534 * maps the extra array dimension corresponding to the extra loop
1537 static struct pet_implication
*pet_implication_embed(
1538 struct pet_implication
*implication
, __isl_take isl_set
*dom
)
1546 map
= isl_set_identity(dom
);
1547 id
= isl_map_get_tuple_id(implication
->extension
, isl_dim_in
);
1548 map
= isl_map_flat_product(map
, implication
->extension
);
1549 map
= isl_map_set_tuple_id(map
, isl_dim_in
, isl_id_copy(id
));
1550 map
= isl_map_set_tuple_id(map
, isl_dim_out
, id
);
1551 implication
->extension
= map
;
1552 if (!implication
->extension
)
1553 return pet_implication_free(implication
);
1561 /* Adjust the context and statement schedules according to an embedding
1562 * in a loop with iteration domain "dom" and schedule "sched".
1564 * Any skip conditions within the loop have no effect outside of the loop.
1565 * The caller is responsible for making sure skip[pet_skip_later] has been
1566 * taken into account.
1568 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
1569 __isl_take isl_aff
*sched
)
1574 sched_map
= isl_map_from_aff(sched
);
1579 pet_scop_reset_skip(scop
, pet_skip_now
);
1580 pet_scop_reset_skip(scop
, pet_skip_later
);
1582 scop
->context
= context_embed(scop
->context
, dom
);
1586 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1587 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
1588 isl_map_copy(sched_map
));
1589 if (!scop
->stmts
[i
])
1594 isl_map_free(sched_map
);
1598 isl_map_free(sched_map
);
1599 return pet_scop_free(scop
);
1602 /* Add extra conditions to scop->skip[type].
1604 * The new skip condition only holds if it held before
1605 * and the condition is true. It does not hold if it did not hold
1606 * before or the condition is false.
1608 * The skip condition is assumed to be an affine expression.
1610 static struct pet_scop
*pet_scop_restrict_skip(struct pet_scop
*scop
,
1611 enum pet_skip type
, __isl_keep isl_set
*cond
)
1613 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1619 if (!ext
->skip
[type
])
1622 if (!multi_pw_aff_is_affine(ext
->skip
[type
]))
1623 isl_die(isl_multi_pw_aff_get_ctx(ext
->skip
[type
]),
1624 isl_error_internal
, "can only restrict affine skips",
1625 return pet_scop_free(scop
));
1627 skip
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
1628 dom
= isl_pw_aff_domain(isl_pw_aff_copy(skip
));
1629 cond
= isl_set_copy(cond
);
1630 cond
= isl_set_intersect(cond
, isl_pw_aff_non_zero_set(skip
));
1631 skip
= indicator_function(cond
, dom
);
1632 isl_multi_pw_aff_free(ext
->skip
[type
]);
1633 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
1634 if (!ext
->skip
[type
])
1635 return pet_scop_free(scop
);
1640 /* Adjust the context and the skip conditions to the fact that
1641 * the scop was created in a context where "cond" holds.
1643 * An outer loop iterator or parameter value is valid for the result
1644 * if it was valid for the original scop and satisfies "cond" or if it does
1645 * not satisfy "cond" as in this case the scop is not executed
1646 * and the original constraints on these values are irrelevant.
1648 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
1649 __isl_take isl_set
*cond
)
1653 scop
= pet_scop_restrict_skip(scop
, pet_skip_now
, cond
);
1654 scop
= pet_scop_restrict_skip(scop
, pet_skip_later
, cond
);
1659 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
1660 scop
->context
= isl_set_union(scop
->context
,
1661 isl_set_complement(isl_set_copy(cond
)));
1662 scop
->context
= isl_set_coalesce(scop
->context
);
1663 scop
->context
= pet_nested_remove_from_set(scop
->context
);
1671 return pet_scop_free(scop
);
1674 /* Insert an argument expression corresponding to "test" in front
1675 * of the list of arguments described by *n_arg and *args.
1677 static int args_insert_access(unsigned *n_arg
, pet_expr
***args
,
1678 __isl_keep isl_multi_pw_aff
*test
)
1681 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
1687 *args
= isl_calloc_array(ctx
, pet_expr
*, 1);
1692 ext
= isl_calloc_array(ctx
, pet_expr
*, 1 + *n_arg
);
1695 for (i
= 0; i
< *n_arg
; ++i
)
1696 ext
[1 + i
] = (*args
)[i
];
1701 (*args
)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
1708 /* Look through the applications in "scop" for any that can be
1709 * applied to the filter expressed by "map" and "satisified".
1710 * If there is any, then apply it to "map" and return the result.
1711 * Otherwise, return "map".
1712 * "id" is the identifier of the virtual array.
1714 * We only introduce at most one implication for any given virtual array,
1715 * so we can apply the implication and return as soon as we find one.
1717 static __isl_give isl_map
*apply_implications(struct pet_scop
*scop
,
1718 __isl_take isl_map
*map
, __isl_keep isl_id
*id
, int satisfied
)
1722 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1723 struct pet_implication
*pi
= scop
->implications
[i
];
1726 if (pi
->satisfied
!= satisfied
)
1728 pi_id
= isl_map_get_tuple_id(pi
->extension
, isl_dim_in
);
1733 return isl_map_apply_range(map
, isl_map_copy(pi
->extension
));
1739 /* Is the filter expressed by "test" and "satisfied" implied
1740 * by filter "pos" on "domain", with filter "expr", taking into
1741 * account the implications of "scop"?
1743 * For filter on domain implying that expressed by "test" and "satisfied",
1744 * the filter needs to be an access to the same (virtual) array as "test" and
1745 * the filter value needs to be equal to "satisfied".
1746 * Moreover, the filter access relation, possibly extended by
1747 * the implications in "scop" needs to contain "test".
1749 static int implies_filter(struct pet_scop
*scop
,
1750 __isl_keep isl_map
*domain
, int pos
, __isl_keep pet_expr
*expr
,
1751 __isl_keep isl_map
*test
, int satisfied
)
1753 isl_id
*test_id
, *arg_id
;
1760 if (expr
->type
!= pet_expr_access
)
1762 test_id
= isl_map_get_tuple_id(test
, isl_dim_out
);
1763 arg_id
= pet_expr_access_get_id(expr
);
1764 isl_id_free(arg_id
);
1765 isl_id_free(test_id
);
1766 if (test_id
!= arg_id
)
1768 val
= isl_map_plain_get_val_if_fixed(domain
, isl_dim_out
, pos
);
1769 is_int
= isl_val_is_int(val
);
1771 s
= isl_val_get_num_si(val
);
1780 implied
= isl_map_from_multi_pw_aff(pet_expr_access_get_index(expr
));
1781 implied
= apply_implications(scop
, implied
, test_id
, satisfied
);
1782 is_subset
= isl_map_is_subset(test
, implied
);
1783 isl_map_free(implied
);
1788 /* Is the filter expressed by "test" and "satisfied" implied
1789 * by any of the filters on the domain of "stmt", taking into
1790 * account the implications of "scop"?
1792 static int filter_implied(struct pet_scop
*scop
,
1793 struct pet_stmt
*stmt
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
1801 if (!scop
|| !stmt
|| !test
)
1803 if (scop
->n_implication
== 0)
1805 if (stmt
->n_arg
== 0)
1808 domain
= isl_set_unwrap(isl_set_copy(stmt
->domain
));
1809 test_map
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test
));
1812 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
1813 implied
= implies_filter(scop
, domain
, i
, stmt
->args
[i
],
1814 test_map
, satisfied
);
1815 if (implied
< 0 || implied
)
1819 isl_map_free(test_map
);
1820 isl_map_free(domain
);
1824 /* Make the statement "stmt" depend on the value of "test"
1825 * being equal to "satisfied" by adjusting stmt->domain.
1827 * The domain of "test" corresponds to the (zero or more) outer dimensions
1828 * of the iteration domain.
1830 * We first extend "test" to apply to the entire iteration domain and
1831 * then check if the filter that we are about to add is implied
1832 * by any of the current filters, possibly taking into account
1833 * the implications in "scop". If so, we leave "stmt" untouched and return.
1835 * Otherwise, we insert an argument corresponding to a read to "test"
1836 * from the iteration domain of "stmt" in front of the list of arguments.
1837 * We also insert a corresponding output dimension in the wrapped
1838 * map contained in stmt->domain, with value set to "satisfied".
1840 static struct pet_stmt
*stmt_filter(struct pet_scop
*scop
,
1841 struct pet_stmt
*stmt
, __isl_take isl_multi_pw_aff
*test
, int satisfied
)
1847 isl_pw_multi_aff
*pma
;
1848 isl_multi_aff
*add_dom
;
1850 isl_local_space
*ls
;
1856 space
= pet_stmt_get_space(stmt
);
1857 n_test_dom
= isl_multi_pw_aff_dim(test
, isl_dim_in
);
1858 space
= isl_space_from_domain(space
);
1859 space
= isl_space_add_dims(space
, isl_dim_out
, n_test_dom
);
1860 add_dom
= isl_multi_aff_zero(isl_space_copy(space
));
1861 ls
= isl_local_space_from_space(isl_space_domain(space
));
1862 for (i
= 0; i
< n_test_dom
; ++i
) {
1864 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
1866 add_dom
= isl_multi_aff_set_aff(add_dom
, i
, aff
);
1868 isl_local_space_free(ls
);
1869 test
= isl_multi_pw_aff_pullback_multi_aff(test
, add_dom
);
1871 implied
= filter_implied(scop
, stmt
, test
, satisfied
);
1875 isl_multi_pw_aff_free(test
);
1879 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
1880 pma
= pet_filter_insert_pma(isl_set_get_space(stmt
->domain
),
1882 stmt
->domain
= isl_set_preimage_pw_multi_aff(stmt
->domain
, pma
);
1884 if (args_insert_access(&stmt
->n_arg
, &stmt
->args
, test
) < 0)
1887 isl_multi_pw_aff_free(test
);
1890 isl_multi_pw_aff_free(test
);
1891 return pet_stmt_free(stmt
);
1894 /* Does "scop" have a skip condition of the given "type"?
1896 int pet_scop_has_skip(struct pet_scop
*scop
, enum pet_skip type
)
1898 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1902 return ext
->skip
[type
] != NULL
;
1905 /* Does "scop" have a skip condition of the given "type" that
1906 * is an affine expression?
1908 int pet_scop_has_affine_skip(struct pet_scop
*scop
, enum pet_skip type
)
1910 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1914 if (!ext
->skip
[type
])
1916 return multi_pw_aff_is_affine(ext
->skip
[type
]);
1919 /* Does "scop" have a skip condition of the given "type" that
1920 * is not an affine expression?
1922 int pet_scop_has_var_skip(struct pet_scop
*scop
, enum pet_skip type
)
1924 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1929 if (!ext
->skip
[type
])
1931 aff
= multi_pw_aff_is_affine(ext
->skip
[type
]);
1937 /* Does "scop" have a skip condition of the given "type" that
1938 * is affine and holds on the entire domain?
1940 int pet_scop_has_universal_skip(struct pet_scop
*scop
, enum pet_skip type
)
1942 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1948 is_aff
= pet_scop_has_affine_skip(scop
, type
);
1949 if (is_aff
< 0 || !is_aff
)
1952 pa
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
1953 set
= isl_pw_aff_non_zero_set(pa
);
1954 is_univ
= isl_set_plain_is_universe(set
);
1960 /* Replace scop->skip[type] by "skip".
1962 struct pet_scop
*pet_scop_set_skip(struct pet_scop
*scop
,
1963 enum pet_skip type
, __isl_take isl_multi_pw_aff
*skip
)
1965 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1970 isl_multi_pw_aff_free(ext
->skip
[type
]);
1971 ext
->skip
[type
] = skip
;
1975 isl_multi_pw_aff_free(skip
);
1976 return pet_scop_free(scop
);
1979 /* Return a copy of scop->skip[type].
1981 __isl_give isl_multi_pw_aff
*pet_scop_get_skip(struct pet_scop
*scop
,
1984 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1989 return isl_multi_pw_aff_copy(ext
->skip
[type
]);
1992 /* Assuming scop->skip[type] is an affine expression,
1993 * return the constraints on the outer loop domain for which the skip condition
1996 __isl_give isl_set
*pet_scop_get_affine_skip_domain(struct pet_scop
*scop
,
1999 isl_multi_pw_aff
*skip
;
2002 skip
= pet_scop_get_skip(scop
, type
);
2003 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
2004 isl_multi_pw_aff_free(skip
);
2005 return isl_pw_aff_non_zero_set(pa
);
2008 /* Return the identifier of the variable that is accessed by
2009 * the skip condition of the given type.
2011 * The skip condition is assumed not to be an affine condition.
2013 __isl_give isl_id
*pet_scop_get_skip_id(struct pet_scop
*scop
,
2016 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2021 return isl_multi_pw_aff_get_tuple_id(ext
->skip
[type
], isl_dim_out
);
2024 /* Return an access pet_expr corresponding to the skip condition
2025 * of the given type.
2027 __isl_give pet_expr
*pet_scop_get_skip_expr(struct pet_scop
*scop
,
2030 return pet_expr_from_index(pet_scop_get_skip(scop
, type
));
2033 /* Drop the skip condition scop->skip[type].
2035 void pet_scop_reset_skip(struct pet_scop
*scop
, enum pet_skip type
)
2037 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2042 isl_multi_pw_aff_free(ext
->skip
[type
]);
2043 ext
->skip
[type
] = NULL
;
2046 /* Make the skip condition (if any) depend on the value of "test" being
2047 * equal to "satisfied".
2049 * We only support the case where the original skip condition is universal,
2050 * i.e., where skipping is unconditional, and where satisfied == 1.
2051 * In this case, the skip condition is changed to skip only when
2052 * "test" is equal to one.
2054 static struct pet_scop
*pet_scop_filter_skip(struct pet_scop
*scop
,
2055 enum pet_skip type
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
2061 if (!pet_scop_has_skip(scop
, type
))
2065 is_univ
= pet_scop_has_universal_skip(scop
, type
);
2067 return pet_scop_free(scop
);
2068 if (satisfied
&& is_univ
) {
2069 isl_multi_pw_aff
*skip
;
2070 skip
= isl_multi_pw_aff_copy(test
);
2071 scop
= pet_scop_set_skip(scop
, type
, skip
);
2075 isl_die(isl_multi_pw_aff_get_ctx(test
), isl_error_internal
,
2076 "skip expression cannot be filtered",
2077 return pet_scop_free(scop
));
2083 /* Make all statements in "scop" depend on the value of "test"
2084 * being equal to "satisfied" by adjusting their domains.
2086 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
2087 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2091 scop
= pet_scop_filter_skip(scop
, pet_skip_now
, test
, satisfied
);
2092 scop
= pet_scop_filter_skip(scop
, pet_skip_later
, test
, satisfied
);
2097 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2098 scop
->stmts
[i
] = stmt_filter(scop
, scop
->stmts
[i
],
2099 isl_multi_pw_aff_copy(test
), satisfied
);
2100 if (!scop
->stmts
[i
])
2104 isl_multi_pw_aff_free(test
);
2107 isl_multi_pw_aff_free(test
);
2108 return pet_scop_free(scop
);
2111 /* Add the parameters of the access expression "expr" to "space".
2113 static int access_collect_params(__isl_keep pet_expr
*expr
, void *user
)
2116 isl_space
*expr_space
;
2117 isl_space
**space
= user
;
2119 expr_space
= pet_expr_access_get_parameter_space(expr
);
2120 *space
= isl_space_align_params(*space
, expr_space
);
2122 return *space
? 0 : -1;
2125 /* Add all parameters in "stmt" to "space" and return the result.
2127 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
2128 __isl_take isl_space
*space
)
2133 return isl_space_free(space
);
2135 space
= isl_space_align_params(space
, isl_set_get_space(stmt
->domain
));
2136 space
= isl_space_align_params(space
,
2137 isl_map_get_space(stmt
->schedule
));
2138 for (i
= 0; i
< stmt
->n_arg
; ++i
)
2139 if (pet_expr_foreach_access_expr(stmt
->args
[i
],
2140 &access_collect_params
, &space
) < 0)
2141 space
= isl_space_free(space
);
2142 if (pet_tree_foreach_access_expr(stmt
->body
, &access_collect_params
,
2144 space
= isl_space_free(space
);
2149 /* Add all parameters in "array" to "space" and return the result.
2151 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
2152 __isl_take isl_space
*space
)
2155 return isl_space_free(space
);
2157 space
= isl_space_align_params(space
,
2158 isl_set_get_space(array
->context
));
2159 space
= isl_space_align_params(space
, isl_set_get_space(array
->extent
));
2164 /* Add all parameters in "independence" to "space" and return the result.
2166 static __isl_give isl_space
*independence_collect_params(
2167 struct pet_independence
*independence
, __isl_take isl_space
*space
)
2170 return isl_space_free(space
);
2172 space
= isl_space_align_params(space
,
2173 isl_union_map_get_space(independence
->filter
));
2174 space
= isl_space_align_params(space
,
2175 isl_union_set_get_space(independence
->local
));
2180 /* Add all parameters in "scop" to "space" and return the result.
2182 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
2183 __isl_take isl_space
*space
)
2188 return isl_space_free(space
);
2190 for (i
= 0; i
< scop
->n_array
; ++i
)
2191 space
= array_collect_params(scop
->arrays
[i
], space
);
2193 for (i
= 0; i
< scop
->n_stmt
; ++i
)
2194 space
= stmt_collect_params(scop
->stmts
[i
], space
);
2196 for (i
= 0; i
< scop
->n_independence
; ++i
)
2197 space
= independence_collect_params(scop
->independences
[i
],
2203 /* Add all parameters in "space" to the domain, schedule and
2204 * all access relations in "stmt".
2206 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
2207 __isl_take isl_space
*space
)
2214 stmt
->domain
= isl_set_align_params(stmt
->domain
,
2215 isl_space_copy(space
));
2216 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
2217 isl_space_copy(space
));
2219 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2220 stmt
->args
[i
] = pet_expr_align_params(stmt
->args
[i
],
2221 isl_space_copy(space
));
2225 stmt
->body
= pet_tree_align_params(stmt
->body
, isl_space_copy(space
));
2227 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2230 isl_space_free(space
);
2233 isl_space_free(space
);
2234 return pet_stmt_free(stmt
);
2237 /* Add all parameters in "space" to "array".
2239 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
2240 __isl_take isl_space
*space
)
2245 array
->context
= isl_set_align_params(array
->context
,
2246 isl_space_copy(space
));
2247 array
->extent
= isl_set_align_params(array
->extent
,
2248 isl_space_copy(space
));
2249 if (array
->value_bounds
) {
2250 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
2251 isl_space_copy(space
));
2252 if (!array
->value_bounds
)
2256 if (!array
->context
|| !array
->extent
)
2259 isl_space_free(space
);
2262 isl_space_free(space
);
2263 return pet_array_free(array
);
2266 /* Add all parameters in "space" to "independence".
2268 static struct pet_independence
*independence_propagate_params(
2269 struct pet_independence
*independence
, __isl_take isl_space
*space
)
2274 independence
->filter
= isl_union_map_align_params(independence
->filter
,
2275 isl_space_copy(space
));
2276 independence
->local
= isl_union_set_align_params(independence
->local
,
2277 isl_space_copy(space
));
2278 if (!independence
->filter
|| !independence
->local
)
2281 isl_space_free(space
);
2282 return independence
;
2284 isl_space_free(space
);
2285 return pet_independence_free(independence
);
2288 /* Add all parameters in "space" to "scop".
2290 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
2291 __isl_take isl_space
*space
)
2298 for (i
= 0; i
< scop
->n_array
; ++i
) {
2299 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
2300 isl_space_copy(space
));
2301 if (!scop
->arrays
[i
])
2305 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2306 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
2307 isl_space_copy(space
));
2308 if (!scop
->stmts
[i
])
2312 for (i
= 0; i
< scop
->n_independence
; ++i
) {
2313 scop
->independences
[i
] = independence_propagate_params(
2314 scop
->independences
[i
], isl_space_copy(space
));
2315 if (!scop
->independences
[i
])
2319 isl_space_free(space
);
2322 isl_space_free(space
);
2323 return pet_scop_free(scop
);
2326 /* Update all isl_sets and isl_maps in "scop" such that they all
2327 * have the same parameters.
2329 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
2336 space
= isl_set_get_space(scop
->context
);
2337 space
= scop_collect_params(scop
, space
);
2339 scop
->context
= isl_set_align_params(scop
->context
,
2340 isl_space_copy(space
));
2341 scop
= scop_propagate_params(scop
, space
);
2343 if (scop
&& !scop
->context
)
2344 return pet_scop_free(scop
);
2349 /* Add the access relation of the give "type" of the access expression "expr"
2350 * to "accesses" and return the result.
2351 * The domain of the access relation is intersected with "domain".
2352 * If "tag" is set, then the access relation is tagged with
2353 * the corresponding reference identifier.
2355 static __isl_give isl_union_map
*expr_collect_access(__isl_keep pet_expr
*expr
,
2356 enum pet_expr_access_type type
, int tag
,
2357 __isl_take isl_union_map
*accesses
, __isl_keep isl_union_set
*domain
)
2359 isl_union_map
*access
;
2361 access
= pet_expr_access_get_access(expr
, type
);
2362 access
= isl_union_map_intersect_domain(access
,
2363 isl_union_set_copy(domain
));
2365 access
= pet_expr_tag_access(expr
, access
);
2366 return isl_union_map_union(accesses
, access
);
2369 /* Internal data structure for expr_collect_accesses.
2371 * "type" is the type of accesses we want to collect.
2372 * "tag" is set if the access relations should be tagged with
2373 * the corresponding reference identifiers.
2374 * "domain" are constraints on the domain of the access relations.
2375 * "accesses" collects the results.
2377 struct pet_expr_collect_accesses_data
{
2378 enum pet_expr_access_type type
;
2380 isl_union_set
*domain
;
2382 isl_union_map
*accesses
;
2385 /* Add the access relation of the access expression "expr"
2386 * to data->accesses if the access expression is a read and we are collecting
2387 * reads and/or it is a write and we are collecting writes.
2388 * The domains of the access relations are intersected with data->domain.
2389 * If data->tag is set, then the access relations are tagged with
2390 * the corresponding reference identifiers.
2392 * If data->type is pet_expr_access_must_write, then we only add
2393 * the accesses that are definitely performed. Otherwise, we add
2394 * all potential accesses.
2395 * In particular, if the access has any arguments, then in case of
2396 * pet_expr_access_must_write we currently skip the access completely.
2397 * In other cases, we project out the values of the access arguments.
2399 static int expr_collect_accesses(__isl_keep pet_expr
*expr
, void *user
)
2401 struct pet_expr_collect_accesses_data
*data
= user
;
2409 if (pet_expr_is_affine(expr
))
2411 if (data
->type
== pet_expr_access_must_write
&& expr
->n_arg
!= 0)
2414 if ((data
->type
== pet_expr_access_may_read
&& expr
->acc
.read
) ||
2415 ((data
->type
== pet_expr_access_may_write
||
2416 data
->type
== pet_expr_access_must_write
) && expr
->acc
.write
))
2417 data
->accesses
= expr_collect_access(expr
,
2418 data
->type
, data
->tag
,
2419 data
->accesses
, data
->domain
);
2421 return data
->accesses
? 0 : -1;
2424 /* Collect and return all access relations of the given "type" in "stmt".
2425 * If "tag" is set, then the access relations are tagged with
2426 * the corresponding reference identifiers.
2427 * If "type" is pet_expr_access_killed, then "stmt" is a kill statement and
2428 * we simply add the argument of the kill operation.
2430 * If we are looking for definite accesses (pet_expr_access_must_write
2431 * or pet_expr_access_killed), then we only add the accesses that are
2432 * definitely performed. Otherwise, we add all potential accesses.
2433 * In particular, if the statement has any arguments, then if we are looking
2434 * for definite accesses we currently skip the statement completely. Othewise,
2435 * we project out the values of the statement arguments.
2436 * If the statement body is not an expression tree, then we cannot
2437 * know for sure if/when the accesses inside the tree are performed.
2438 * We therefore ignore such statements when we are looking for
2439 * definite accesses.
2441 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
2442 enum pet_expr_access_type type
, int tag
, __isl_take isl_space
*dim
)
2444 struct pet_expr_collect_accesses_data data
= { type
, tag
};
2451 data
.accesses
= isl_union_map_empty(dim
);
2453 if (type
== pet_expr_access_must_write
||
2454 type
== pet_expr_access_killed
)
2459 if (must
&& stmt
->n_arg
> 0)
2460 return data
.accesses
;
2461 if (must
&& pet_tree_get_type(stmt
->body
) != pet_tree_expr
)
2462 return data
.accesses
;
2464 domain
= drop_arguments(isl_set_copy(stmt
->domain
));
2465 data
.domain
= isl_union_set_from_set(domain
);
2467 if (type
== pet_expr_access_killed
) {
2468 pet_expr
*body
, *arg
;
2470 body
= pet_tree_expr_get_expr(stmt
->body
);
2471 arg
= pet_expr_get_arg(body
, 0);
2472 data
.accesses
= expr_collect_access(arg
,
2473 pet_expr_access_killed
, tag
,
2474 data
.accesses
, data
.domain
);
2476 pet_expr_free(body
);
2477 } else if (pet_tree_foreach_access_expr(stmt
->body
,
2478 &expr_collect_accesses
, &data
) < 0)
2479 data
.accesses
= isl_union_map_free(data
.accesses
);
2481 isl_union_set_free(data
.domain
);
2483 return data
.accesses
;
2486 /* Is "stmt" an assignment statement?
2488 int pet_stmt_is_assign(struct pet_stmt
*stmt
)
2492 return pet_tree_is_assign(stmt
->body
);
2495 /* Is "stmt" a kill statement?
2497 int pet_stmt_is_kill(struct pet_stmt
*stmt
)
2501 return pet_tree_is_kill(stmt
->body
);
2504 /* Is "stmt" an assume statement?
2506 int pet_stmt_is_assume(struct pet_stmt
*stmt
)
2510 return pet_tree_is_assume(stmt
->body
);
2513 /* Helper function to add a domain gisted copy of "map" (wrt "set") to "umap".
2515 static __isl_give isl_union_map
*add_gisted(__isl_take isl_union_map
*umap
,
2516 __isl_keep isl_map
*map
, __isl_keep isl_set
*set
)
2520 gist
= isl_map_copy(map
);
2521 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
2522 return isl_union_map_add_map(umap
, gist
);
2525 /* Compute a mapping from all arrays (of structs) in scop
2528 * If "from_outermost" is set, then the domain only consists
2529 * of outermost arrays.
2530 * If "to_innermost" is set, then the range only consists
2531 * of innermost arrays.
2533 static __isl_give isl_union_map
*compute_to_inner(struct pet_scop
*scop
,
2534 int from_outermost
, int to_innermost
)
2537 isl_union_map
*to_inner
;
2542 to_inner
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2544 for (i
= 0; i
< scop
->n_array
; ++i
) {
2545 struct pet_array
*array
= scop
->arrays
[i
];
2549 if (to_innermost
&& array
->element_is_record
)
2552 set
= isl_set_copy(array
->extent
);
2553 map
= isl_set_identity(isl_set_copy(set
));
2555 while (set
&& isl_set_is_wrapping(set
)) {
2559 if (!from_outermost
)
2560 to_inner
= add_gisted(to_inner
, map
, set
);
2562 id
= isl_set_get_tuple_id(set
);
2563 wrapped
= isl_set_unwrap(set
);
2564 wrapped
= isl_map_domain_map(wrapped
);
2565 wrapped
= isl_map_set_tuple_id(wrapped
, isl_dim_in
, id
);
2566 map
= isl_map_apply_domain(map
, wrapped
);
2567 set
= isl_map_domain(isl_map_copy(map
));
2570 map
= isl_map_gist_domain(map
, set
);
2571 to_inner
= isl_union_map_add_map(to_inner
, map
);
2577 /* Compute a mapping from all arrays (of structs) in scop
2578 * to their innermost arrays.
2580 * In particular, for each array of a primitive type, the result
2581 * contains the identity mapping on that array.
2582 * For each array involving member accesses, the result
2583 * contains a mapping from the elements of any intermediate array of structs
2584 * to all corresponding elements of the innermost nested arrays.
2586 static __isl_give isl_union_map
*pet_scop_compute_any_to_inner(
2587 struct pet_scop
*scop
)
2589 return compute_to_inner(scop
, 0, 1);
2592 /* Compute a mapping from all outermost arrays (of structs) in scop
2593 * to their innermost members.
2595 __isl_give isl_union_map
*pet_scop_compute_outer_to_inner(struct pet_scop
*scop
)
2597 return compute_to_inner(scop
, 1, 1);
2600 /* Compute a mapping from all outermost arrays (of structs) in scop
2601 * to their members, including the outermost arrays themselves.
2603 __isl_give isl_union_map
*pet_scop_compute_outer_to_any(struct pet_scop
*scop
)
2605 return compute_to_inner(scop
, 1, 0);
2608 /* Collect and return all access relations of the given "type" in "scop".
2609 * If "type" is pet_expr_access_killed, then we only add the arguments of
2611 * If we are looking for definite accesses (pet_expr_access_must_write
2612 * or pet_expr_access_killed), then we only add the accesses that are
2613 * definitely performed. Otherwise, we add all potential accesses.
2614 * If "tag" is set, then the access relations are tagged with
2615 * the corresponding reference identifiers.
2616 * For accesses to structures, the returned access relation accesses
2617 * all individual fields in the structures.
2619 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
2620 enum pet_expr_access_type type
, int tag
)
2623 isl_union_map
*accesses
;
2624 isl_union_set
*arrays
;
2625 isl_union_map
*to_inner
;
2630 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2632 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2633 struct pet_stmt
*stmt
= scop
->stmts
[i
];
2634 isl_union_map
*accesses_i
;
2637 if (type
== pet_expr_access_killed
&& !pet_stmt_is_kill(stmt
))
2640 space
= isl_set_get_space(scop
->context
);
2641 accesses_i
= stmt_collect_accesses(stmt
, type
, tag
, space
);
2642 accesses
= isl_union_map_union(accesses
, accesses_i
);
2645 arrays
= isl_union_set_empty(isl_union_map_get_space(accesses
));
2646 for (i
= 0; i
< scop
->n_array
; ++i
) {
2647 isl_set
*extent
= isl_set_copy(scop
->arrays
[i
]->extent
);
2648 arrays
= isl_union_set_add_set(arrays
, extent
);
2650 accesses
= isl_union_map_intersect_range(accesses
, arrays
);
2652 to_inner
= pet_scop_compute_any_to_inner(scop
);
2653 accesses
= isl_union_map_apply_range(accesses
, to_inner
);
2658 /* Collect all potential read access relations.
2660 __isl_give isl_union_map
*pet_scop_collect_may_reads(struct pet_scop
*scop
)
2662 return scop_collect_accesses(scop
, pet_expr_access_may_read
, 0);
2665 /* Collect all potential write access relations.
2667 __isl_give isl_union_map
*pet_scop_collect_may_writes(struct pet_scop
*scop
)
2669 return scop_collect_accesses(scop
, pet_expr_access_may_write
, 0);
2672 /* Collect all definite write access relations.
2674 __isl_give isl_union_map
*pet_scop_collect_must_writes(struct pet_scop
*scop
)
2676 return scop_collect_accesses(scop
, pet_expr_access_must_write
, 0);
2679 /* Collect all definite kill access relations.
2681 __isl_give isl_union_map
*pet_scop_collect_must_kills(struct pet_scop
*scop
)
2683 return scop_collect_accesses(scop
, pet_expr_access_killed
, 0);
2686 /* Collect all tagged potential read access relations.
2688 __isl_give isl_union_map
*pet_scop_collect_tagged_may_reads(
2689 struct pet_scop
*scop
)
2691 return scop_collect_accesses(scop
, pet_expr_access_may_read
, 1);
2694 /* Collect all tagged potential write access relations.
2696 __isl_give isl_union_map
*pet_scop_collect_tagged_may_writes(
2697 struct pet_scop
*scop
)
2699 return scop_collect_accesses(scop
, pet_expr_access_may_write
, 1);
2702 /* Collect all tagged definite write access relations.
2704 __isl_give isl_union_map
*pet_scop_collect_tagged_must_writes(
2705 struct pet_scop
*scop
)
2707 return scop_collect_accesses(scop
, pet_expr_access_must_write
, 1);
2710 /* Collect all tagged definite kill access relations.
2712 __isl_give isl_union_map
*pet_scop_collect_tagged_must_kills(
2713 struct pet_scop
*scop
)
2715 return scop_collect_accesses(scop
, pet_expr_access_killed
, 1);
2718 /* Collect and return the union of iteration domains in "scop".
2720 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
2724 isl_union_set
*domain
;
2729 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
2731 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2732 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
2733 if (scop
->stmts
[i
]->n_arg
> 0)
2734 domain_i
= isl_map_domain(isl_set_unwrap(domain_i
));
2735 domain
= isl_union_set_add_set(domain
, domain_i
);
2741 /* Collect and return the schedules of the statements in "scop".
2742 * The range is normalized to the maximal number of scheduling
2745 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
2748 isl_map
*schedule_i
;
2749 isl_union_map
*schedule
;
2750 int depth
, max_depth
= 0;
2755 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2757 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2758 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
2759 if (depth
> max_depth
)
2763 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2764 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
2765 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
2766 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
2768 for (j
= depth
; j
< max_depth
; ++j
)
2769 schedule_i
= isl_map_fix_si(schedule_i
,
2771 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
2777 /* Add a reference identifier to all access expressions in "stmt".
2778 * "n_ref" points to an integer that contains the sequence number
2779 * of the next reference.
2781 static struct pet_stmt
*stmt_add_ref_ids(struct pet_stmt
*stmt
, int *n_ref
)
2788 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2789 stmt
->args
[i
] = pet_expr_add_ref_ids(stmt
->args
[i
], n_ref
);
2791 return pet_stmt_free(stmt
);
2794 stmt
->body
= pet_tree_add_ref_ids(stmt
->body
, n_ref
);
2796 return pet_stmt_free(stmt
);
2801 /* Add a reference identifier to all access expressions in "scop".
2803 struct pet_scop
*pet_scop_add_ref_ids(struct pet_scop
*scop
)
2812 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2813 scop
->stmts
[i
] = stmt_add_ref_ids(scop
->stmts
[i
], &n_ref
);
2814 if (!scop
->stmts
[i
])
2815 return pet_scop_free(scop
);
2821 /* Reset the user pointer on all parameter ids in "array".
2823 static struct pet_array
*array_anonymize(struct pet_array
*array
)
2828 array
->context
= isl_set_reset_user(array
->context
);
2829 array
->extent
= isl_set_reset_user(array
->extent
);
2830 if (!array
->context
|| !array
->extent
)
2831 return pet_array_free(array
);
2836 /* Reset the user pointer on all parameter and tuple ids in "stmt".
2838 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
2847 stmt
->domain
= isl_set_reset_user(stmt
->domain
);
2848 stmt
->schedule
= isl_map_reset_user(stmt
->schedule
);
2849 if (!stmt
->domain
|| !stmt
->schedule
)
2850 return pet_stmt_free(stmt
);
2852 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2853 stmt
->args
[i
] = pet_expr_anonymize(stmt
->args
[i
]);
2855 return pet_stmt_free(stmt
);
2858 stmt
->body
= pet_tree_anonymize(stmt
->body
);
2860 return pet_stmt_free(stmt
);
2865 /* Reset the user pointer on the tuple ids and all parameter ids
2868 static struct pet_implication
*implication_anonymize(
2869 struct pet_implication
*implication
)
2874 implication
->extension
= isl_map_reset_user(implication
->extension
);
2875 if (!implication
->extension
)
2876 return pet_implication_free(implication
);
2881 /* Reset the user pointer on the tuple ids and all parameter ids
2882 * in "independence".
2884 static struct pet_independence
*independence_anonymize(
2885 struct pet_independence
*independence
)
2890 independence
->filter
= isl_union_map_reset_user(independence
->filter
);
2891 independence
->local
= isl_union_set_reset_user(independence
->local
);
2892 if (!independence
->filter
|| !independence
->local
)
2893 return pet_independence_free(independence
);
2895 return independence
;
2898 /* Reset the user pointer on all parameter and tuple ids in "scop".
2900 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
2907 scop
->context
= isl_set_reset_user(scop
->context
);
2908 scop
->context_value
= isl_set_reset_user(scop
->context_value
);
2909 if (!scop
->context
|| !scop
->context_value
)
2910 return pet_scop_free(scop
);
2912 for (i
= 0; i
< scop
->n_array
; ++i
) {
2913 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
2914 if (!scop
->arrays
[i
])
2915 return pet_scop_free(scop
);
2918 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2919 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
2920 if (!scop
->stmts
[i
])
2921 return pet_scop_free(scop
);
2924 for (i
= 0; i
< scop
->n_implication
; ++i
) {
2925 scop
->implications
[i
] =
2926 implication_anonymize(scop
->implications
[i
]);
2927 if (!scop
->implications
[i
])
2928 return pet_scop_free(scop
);
2931 for (i
= 0; i
< scop
->n_independence
; ++i
) {
2932 scop
->independences
[i
] =
2933 independence_anonymize(scop
->independences
[i
]);
2934 if (!scop
->independences
[i
])
2935 return pet_scop_free(scop
);
2941 /* Compute the gist of the iteration domain and all access relations
2942 * of "stmt" based on the constraints on the parameters specified by "context"
2943 * and the constraints on the values of nested accesses specified
2944 * by "value_bounds".
2946 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
2947 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
2955 domain
= isl_set_copy(stmt
->domain
);
2956 if (stmt
->n_arg
> 0)
2957 domain
= isl_map_domain(isl_set_unwrap(domain
));
2959 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
2961 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2962 stmt
->args
[i
] = pet_expr_gist(stmt
->args
[i
],
2963 domain
, value_bounds
);
2968 stmt
->body
= pet_tree_gist(stmt
->body
, domain
, value_bounds
);
2972 isl_set_free(domain
);
2974 domain
= isl_set_universe(pet_stmt_get_space(stmt
));
2975 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
2976 if (stmt
->n_arg
> 0)
2977 domain
= pet_value_bounds_apply(domain
, stmt
->n_arg
, stmt
->args
,
2979 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
2981 return pet_stmt_free(stmt
);
2985 isl_set_free(domain
);
2986 return pet_stmt_free(stmt
);
2989 /* Compute the gist of the extent of the array
2990 * based on the constraints on the parameters specified by "context".
2992 static struct pet_array
*array_gist(struct pet_array
*array
,
2993 __isl_keep isl_set
*context
)
2998 array
->extent
= isl_set_gist_params(array
->extent
,
2999 isl_set_copy(context
));
3001 return pet_array_free(array
);
3006 /* Compute the gist of all sets and relations in "scop"
3007 * based on the constraints on the parameters specified by "scop->context"
3008 * and the constraints on the values of nested accesses specified
3009 * by "value_bounds".
3011 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
3012 __isl_keep isl_union_map
*value_bounds
)
3019 scop
->context
= isl_set_coalesce(scop
->context
);
3021 return pet_scop_free(scop
);
3023 for (i
= 0; i
< scop
->n_array
; ++i
) {
3024 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
3025 if (!scop
->arrays
[i
])
3026 return pet_scop_free(scop
);
3029 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3030 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
3032 if (!scop
->stmts
[i
])
3033 return pet_scop_free(scop
);
3039 /* Intersect the context of "scop" with "context".
3040 * To ensure that we don't introduce any unnamed parameters in
3041 * the context of "scop", we first remove the unnamed parameters
3044 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
3045 __isl_take isl_set
*context
)
3050 context
= pet_nested_remove_from_set(context
);
3051 scop
->context
= isl_set_intersect(scop
->context
, context
);
3053 return pet_scop_free(scop
);
3057 isl_set_free(context
);
3058 return pet_scop_free(scop
);
3061 /* Drop the current context of "scop". That is, replace the context
3062 * by a universal set.
3064 struct pet_scop
*pet_scop_reset_context(struct pet_scop
*scop
)
3071 space
= isl_set_get_space(scop
->context
);
3072 isl_set_free(scop
->context
);
3073 scop
->context
= isl_set_universe(space
);
3075 return pet_scop_free(scop
);
3080 /* Append "array" to the arrays of "scop".
3082 struct pet_scop
*pet_scop_add_array(struct pet_scop
*scop
,
3083 struct pet_array
*array
)
3086 struct pet_array
**arrays
;
3088 if (!array
|| !scop
)
3091 ctx
= isl_set_get_ctx(scop
->context
);
3092 arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
3096 scop
->arrays
= arrays
;
3097 scop
->arrays
[scop
->n_array
] = array
;
3102 pet_array_free(array
);
3103 return pet_scop_free(scop
);
3106 /* Create an index expression for an access to a virtual array
3107 * representing the result of a condition.
3108 * Unlike other accessed data, the id of the array is NULL as
3109 * there is no ValueDecl in the program corresponding to the virtual
3111 * The index expression is created as an identity mapping on "space".
3112 * That is, the dimension of the array is the same as that of "space".
3114 __isl_give isl_multi_pw_aff
*pet_create_test_index(__isl_take isl_space
*space
,
3120 snprintf(name
, sizeof(name
), "__pet_test_%d", test_nr
);
3121 id
= isl_id_alloc(isl_space_get_ctx(space
), name
, NULL
);
3122 space
= isl_space_map_from_set(space
);
3123 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
3124 return isl_multi_pw_aff_identity(space
);
3127 /* Add an array with the given extent to the list
3128 * of arrays in "scop" and return the extended pet_scop.
3129 * Specifically, the extent is determined by the image of "domain"
3131 * "int_size" is the number of bytes needed to represent values of type "int".
3132 * The array is marked as attaining values 0 and 1 only and
3133 * as each element being assigned at most once.
3135 struct pet_scop
*pet_scop_add_boolean_array(struct pet_scop
*scop
,
3136 __isl_take isl_set
*domain
, __isl_take isl_multi_pw_aff
*index
,
3141 struct pet_array
*array
;
3144 if (!scop
|| !domain
|| !index
)
3147 ctx
= isl_multi_pw_aff_get_ctx(index
);
3148 array
= isl_calloc_type(ctx
, struct pet_array
);
3152 access
= isl_map_from_multi_pw_aff(index
);
3153 access
= isl_map_intersect_domain(access
, domain
);
3154 array
->extent
= isl_map_range(access
);
3155 space
= isl_space_params_alloc(ctx
, 0);
3156 array
->context
= isl_set_universe(space
);
3157 space
= isl_space_set_alloc(ctx
, 0, 1);
3158 array
->value_bounds
= isl_set_universe(space
);
3159 array
->value_bounds
= isl_set_lower_bound_si(array
->value_bounds
,
3161 array
->value_bounds
= isl_set_upper_bound_si(array
->value_bounds
,
3163 array
->element_type
= strdup("int");
3164 array
->element_size
= int_size
;
3165 array
->uniquely_defined
= 1;
3167 if (!array
->extent
|| !array
->context
)
3168 array
= pet_array_free(array
);
3170 scop
= pet_scop_add_array(scop
, array
);
3174 isl_set_free(domain
);
3175 isl_multi_pw_aff_free(index
);
3176 return pet_scop_free(scop
);
3179 /* Create and return an implication on filter values equal to "satisfied"
3180 * with extension "map".
3182 static struct pet_implication
*new_implication(__isl_take isl_map
*map
,
3186 struct pet_implication
*implication
;
3190 ctx
= isl_map_get_ctx(map
);
3191 implication
= isl_alloc_type(ctx
, struct pet_implication
);
3195 implication
->extension
= map
;
3196 implication
->satisfied
= satisfied
;
3204 /* Add an implication on filter values equal to "satisfied"
3205 * with extension "map" to "scop".
3207 struct pet_scop
*pet_scop_add_implication(struct pet_scop
*scop
,
3208 __isl_take isl_map
*map
, int satisfied
)
3211 struct pet_implication
*implication
;
3212 struct pet_implication
**implications
;
3214 implication
= new_implication(map
, satisfied
);
3215 if (!scop
|| !implication
)
3218 ctx
= isl_set_get_ctx(scop
->context
);
3219 implications
= isl_realloc_array(ctx
, scop
->implications
,
3220 struct pet_implication
*,
3221 scop
->n_implication
+ 1);
3224 scop
->implications
= implications
;
3225 scop
->implications
[scop
->n_implication
] = implication
;
3226 scop
->n_implication
++;
3230 pet_implication_free(implication
);
3231 return pet_scop_free(scop
);
3234 /* Create and return a function that maps the iteration domains
3235 * of the statements in "scop" onto their outer "n" dimensions.
3236 * "space" is the parameters space of the created function.
3238 static __isl_give isl_union_pw_multi_aff
*outer_projection(
3239 struct pet_scop
*scop
, __isl_take isl_space
*space
, int n
)
3242 isl_union_pw_multi_aff
*res
;
3244 res
= isl_union_pw_multi_aff_empty(space
);
3247 return isl_union_pw_multi_aff_free(res
);
3249 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3250 struct pet_stmt
*stmt
= scop
->stmts
[i
];
3253 isl_pw_multi_aff
*pma
;
3255 space
= pet_stmt_get_space(stmt
);
3256 ma
= pet_prefix_projection(space
, n
);
3257 pma
= isl_pw_multi_aff_from_multi_aff(ma
);
3258 res
= isl_union_pw_multi_aff_add_pw_multi_aff(res
, pma
);
3264 /* Add an independence to "scop" for the inner iterator of "domain"
3265 * with local variables "local", where "domain" represents the outer
3266 * loop iterators of all statements in "scop".
3267 * If "sign" is positive, then the inner iterator increases.
3268 * Otherwise it decreases.
3270 * The independence is supposed to filter out any dependence of
3271 * an iteration of domain on a previous iteration along the inner dimension.
3272 * We therefore create a mapping from an iteration to later iterations and
3273 * then plug in the projection of the iterations domains of "scop"
3274 * onto the outer loop iterators.
3276 struct pet_scop
*pet_scop_set_independent(struct pet_scop
*scop
,
3277 __isl_keep isl_set
*domain
, __isl_take isl_union_set
*local
, int sign
)
3282 isl_union_map
*independence
;
3283 isl_union_pw_multi_aff
*proj
;
3285 if (!scop
|| !domain
|| !local
)
3288 dim
= isl_set_dim(domain
, isl_dim_set
);
3289 space
= isl_space_map_from_set(isl_set_get_space(domain
));
3290 map
= isl_map_universe(space
);
3291 for (i
= 0; i
+ 1 < dim
; ++i
)
3292 map
= isl_map_equate(map
, isl_dim_in
, i
, isl_dim_out
, i
);
3294 map
= isl_map_order_lt(map
,
3295 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
3297 map
= isl_map_order_gt(map
,
3298 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
3300 independence
= isl_union_map_from_map(map
);
3301 space
= isl_space_params(isl_set_get_space(domain
));
3302 proj
= outer_projection(scop
, space
, dim
);
3303 independence
= isl_union_map_preimage_domain_union_pw_multi_aff(
3304 independence
, isl_union_pw_multi_aff_copy(proj
));
3305 independence
= isl_union_map_preimage_range_union_pw_multi_aff(
3306 independence
, proj
);
3308 scop
= pet_scop_add_independence(scop
, independence
, local
);
3312 isl_union_set_free(local
);
3313 return pet_scop_free(scop
);
3316 /* Given an access expression, check if it is data dependent.
3317 * If so, set *found and abort the search.
3319 static int is_data_dependent(__isl_keep pet_expr
*expr
, void *user
)
3323 if (pet_expr_get_n_arg(expr
) > 0) {
3331 /* Does "scop" contain any data dependent accesses?
3333 * Check the body of each statement for such accesses.
3335 int pet_scop_has_data_dependent_accesses(struct pet_scop
*scop
)
3343 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3344 int r
= pet_tree_foreach_access_expr(scop
->stmts
[i
]->body
,
3345 &is_data_dependent
, &found
);
3346 if (r
< 0 && !found
)
3355 /* Does "scop" contain and data dependent conditions?
3357 int pet_scop_has_data_dependent_conditions(struct pet_scop
*scop
)
3364 for (i
= 0; i
< scop
->n_stmt
; ++i
)
3365 if (scop
->stmts
[i
]->n_arg
> 0)
3371 /* Keep track of the "input" file inside the (extended) "scop".
3373 struct pet_scop
*pet_scop_set_input_file(struct pet_scop
*scop
, FILE *input
)
3375 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
3385 /* Print the original code corresponding to "scop" to printer "p".
3387 * pet_scop_print_original can only be called from
3388 * a pet_transform_C_source callback. This means that the input
3389 * file is stored in the extended scop and that the printer prints
3392 __isl_give isl_printer
*pet_scop_print_original(struct pet_scop
*scop
,
3393 __isl_take isl_printer
*p
)
3395 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
3397 unsigned start
, end
;
3400 return isl_printer_free(p
);
3403 isl_die(isl_printer_get_ctx(p
), isl_error_invalid
,
3404 "no input file stored in scop",
3405 return isl_printer_free(p
));
3407 output
= isl_printer_get_file(p
);
3409 return isl_printer_free(p
);
3411 start
= pet_loc_get_start(scop
->loc
);
3412 end
= pet_loc_get_end(scop
->loc
);
3413 if (copy(ext
->input
, output
, start
, end
) < 0)
3414 return isl_printer_free(p
);