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
38 #include <isl/space.h>
39 #include <isl/local_space.h>
40 #include <isl/constraint.h>
45 #include <isl/union_set.h>
46 #include <isl/union_map.h>
47 #include <isl/schedule_node.h>
51 #include "expr_access_type.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
77 * Additionally, we keep track of the original input file
78 * inside pet_transform_C_source.
83 isl_multi_pw_aff
*skip
[2];
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
;
102 isl_multi_pw_aff
*add_name
;
105 if (!domain
|| !tree
)
108 ctx
= pet_tree_get_ctx(tree
);
109 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
114 label
= isl_id_copy(tree
->label
);
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
;
131 if (!stmt
->domain
|| !stmt
->body
)
132 return pet_stmt_free(stmt
);
136 isl_set_free(domain
);
141 void *pet_stmt_free(struct pet_stmt
*stmt
)
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
]);
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
)
174 space
= isl_set_get_space(stmt
->domain
);
175 if (isl_space_is_wrapping(space
))
176 space
= isl_space_domain(isl_space_unwrap(space
));
181 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
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
)
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
);
212 type
->name
= strdup(name
);
213 type
->definition
= strdup(definition
);
215 if (!type
->name
|| !type
->definition
)
216 return pet_type_free(type
);
221 /* Free "type" and return NULL.
223 struct pet_type
*pet_type_free(struct pet_type
*type
)
229 free(type
->definition
);
235 struct pet_array
*pet_array_free(struct pet_array
*array
)
240 isl_set_free(array
->context
);
241 isl_set_free(array
->extent
);
242 isl_set_free(array
->value_bounds
);
243 free(array
->element_type
);
249 void pet_array_dump(struct pet_array
*array
)
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
)
282 struct pet_scop
*scop
;
284 if (!space
|| !schedule
)
287 ctx
= isl_space_get_ctx(space
);
288 scop
= pet_scop_alloc(ctx
);
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
;
304 isl_space_free(space
);
305 isl_schedule_free(schedule
);
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
));
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
;
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
);
352 /* Update "context" with the constraints imposed on the outer iteration
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
)
376 if (expr
->type
== pet_expr_op
&& expr
->op
== pet_op_kill
)
379 if (expr
->type
== pet_expr_op
&& expr
->op
== pet_op_cond
) {
381 isl_set
*context1
, *context2
;
383 is_aff
= pet_expr_is_affine(expr
->args
[0]);
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
);
393 isl_multi_pw_aff
*mpa
;
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
);
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
);
421 isl_set_free(context
);
425 /* Is "stmt" an assume statement with an affine assumption?
427 isl_bool
pet_stmt_is_affine_assume(struct pet_stmt
*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
)
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
;
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
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
)
476 affine
= pet_stmt_is_affine_assume(stmt
);
478 return isl_set_free(context
);
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
)
493 body
= pet_tree_expr_get_expr(stmt
->body
);
494 context
= expr_extract_context(body
, 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
;
508 isl_union_set
*domain
;
509 isl_schedule
*schedule
;
512 isl_space_free(space
);
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
);
524 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
528 scop
->stmts
[0] = stmt
;
529 scop
->loc
= pet_loc_copy(stmt
->loc
);
532 return pet_scop_free(scop
);
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
)
548 has_id
= isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
);
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
)
561 pa
= isl_set_indicator_function(set
);
562 pa
= isl_pw_aff_intersect_domain(pa
, dom
);
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
)
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
,
594 isl_pw_aff
*skip
, *skip1
, *skip2
;
598 if (!ext1
->skip
[type
] && !ext2
->skip
[type
])
600 if (!ext1
->skip
[type
]) {
603 ext
->skip
[type
] = ext2
->skip
[type
];
604 ext2
->skip
[type
] = NULL
;
607 if (!ext2
->skip
[type
]) {
610 ext
->skip
[type
] = ext1
->skip
[type
];
611 ext1
->skip
[type
] = NULL
;
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",
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
])
634 pet_scop_free(&ext
->scop
);
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
);
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
)
665 if (scop
->loc
== &pet_loc_dummy
)
666 scop
->loc
= pet_loc_alloc(isl_set_get_ctx(scop
->context
),
667 start
, end
, -1, strdup(""));
669 scop
->loc
= pet_loc_update_start_end(scop
->loc
, start
, end
);
672 return pet_scop_free(scop
);
677 /* Update start and end of scop->loc to include the region identified
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
)
695 pet_loc_free(scop
->loc
);
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
)
712 for (i
= 0; i
< scop
->n_implication
; ++i
) {
713 struct pet_implication
*pi
= scop
->implications
[i
];
716 if (pi
->satisfied
!= implication
->satisfied
)
718 equal
= isl_map_is_equal(pi
->extension
, implication
->extension
);
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
)
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
;
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
;
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
) {
771 known
= is_known_implication(scop
, scop2
->implications
[i
]);
773 return pet_scop_free(scop
);
776 scop
->implications
[j
++] = scop2
->implications
[i
];
777 scop2
->implications
[i
] = NULL
;
779 scop
->n_implication
= j
;
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
);
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
)
803 struct pet_independence
*independence
;
805 if (!filter
|| !local
)
807 ctx
= isl_union_map_get_ctx(filter
);
808 independence
= isl_alloc_type(ctx
, struct pet_independence
);
812 independence
->filter
= filter
;
813 independence
->local
= local
;
817 isl_union_map_free(filter
);
818 isl_union_set_free(local
);
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
)
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
)
837 independences
= isl_realloc_array(ctx
, scop
->independences
,
838 struct pet_independence
*,
839 scop
->n_independence
+ 1);
842 scop
->independences
= independences
;
843 scop
->independences
[scop
->n_independence
] = independence
;
844 scop
->n_independence
++;
848 pet_independence_free(independence
);
853 /* Store the concatenation of the independences of "scop1" and "scop2"
856 static struct pet_scop
*scop_collect_independences(isl_ctx
*ctx
,
857 struct pet_scop
*scop
, struct pet_scop
*scop1
, struct pet_scop
*scop2
)
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
;
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
;
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
;
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
)
910 struct pet_scop
*scop
= NULL
;
912 if (!scop1
|| !scop2
)
915 if (scop1
->n_stmt
== 0) {
916 scop2
= scop_combine_skips(scop2
, scop1
, scop2
);
917 pet_scop_free(scop1
);
918 isl_schedule_free(schedule
);
922 if (scop2
->n_stmt
== 0) {
923 scop1
= scop_combine_skips(scop1
, scop1
, scop2
);
924 pet_scop_free(scop2
);
925 isl_schedule_free(schedule
);
929 space
= isl_set_get_space(scop1
->context
);
930 scop
= scop_alloc(space
, scop1
->n_stmt
+ scop2
->n_stmt
,
931 isl_schedule_copy(schedule
));
935 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
936 scop1
->n_array
+ scop2
->n_array
);
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
);
973 pet_scop_free(scop1
);
974 pet_scop_free(scop2
);
976 isl_schedule_free(schedule
);
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
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
)
998 is_aff
= multi_pw_aff_is_affine(skip
);
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
);
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
)
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
);
1037 pet_scop_free(scop1
);
1038 pet_scop_free(scop2
);
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
)
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
);
1060 pet_scop_free(scop1
);
1061 pet_scop_free(scop2
);
1065 void *pet_implication_free(struct pet_implication
*implication
)
1072 isl_map_free(implication
->extension
);
1078 void *pet_independence_free(struct pet_independence
*independence
)
1083 isl_union_map_free(independence
->filter
);
1084 isl_union_set_free(independence
->local
);
1090 struct pet_scop
*pet_scop_free(struct pet_scop
*scop
)
1093 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1097 pet_loc_free(scop
->loc
);
1098 isl_set_free(scop
->context
);
1099 isl_set_free(scop
->context_value
);
1100 isl_schedule_free(scop
->schedule
);
1102 for (i
= 0; i
< scop
->n_type
; ++i
)
1103 pet_type_free(scop
->types
[i
]);
1106 for (i
= 0; i
< scop
->n_array
; ++i
)
1107 pet_array_free(scop
->arrays
[i
]);
1110 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1111 pet_stmt_free(scop
->stmts
[i
]);
1113 if (scop
->implications
)
1114 for (i
= 0; i
< scop
->n_implication
; ++i
)
1115 pet_implication_free(scop
->implications
[i
]);
1116 free(scop
->implications
);
1117 if (scop
->independences
)
1118 for (i
= 0; i
< scop
->n_independence
; ++i
)
1119 pet_independence_free(scop
->independences
[i
]);
1120 free(scop
->independences
);
1121 isl_multi_pw_aff_free(ext
->skip
[pet_skip_now
]);
1122 isl_multi_pw_aff_free(ext
->skip
[pet_skip_later
]);
1127 void pet_type_dump(struct pet_type
*type
)
1132 fprintf(stderr
, "%s -> %s\n", type
->name
, type
->definition
);
1135 void pet_implication_dump(struct pet_implication
*implication
)
1140 fprintf(stderr
, "%d\n", implication
->satisfied
);
1141 isl_map_dump(implication
->extension
);
1144 void pet_scop_dump(struct pet_scop
*scop
)
1147 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1152 isl_set_dump(scop
->context
);
1153 isl_set_dump(scop
->context_value
);
1154 isl_schedule_dump(scop
->schedule
);
1155 for (i
= 0; i
< scop
->n_type
; ++i
)
1156 pet_type_dump(scop
->types
[i
]);
1157 for (i
= 0; i
< scop
->n_array
; ++i
)
1158 pet_array_dump(scop
->arrays
[i
]);
1159 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1160 pet_stmt_dump(scop
->stmts
[i
]);
1161 for (i
= 0; i
< scop
->n_implication
; ++i
)
1162 pet_implication_dump(scop
->implications
[i
]);
1165 fprintf(stderr
, "skip\n");
1166 isl_multi_pw_aff_dump(ext
->skip
[0]);
1167 isl_multi_pw_aff_dump(ext
->skip
[1]);
1171 /* Return 1 if the two pet_arrays are equivalent.
1173 * We don't compare element_size as this may be target dependent.
1175 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
1177 if (!array1
|| !array2
)
1180 if (!isl_set_is_equal(array1
->context
, array2
->context
))
1182 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
1184 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
1186 if (array1
->value_bounds
&&
1187 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
1189 if (strcmp(array1
->element_type
, array2
->element_type
))
1191 if (array1
->element_is_record
!= array2
->element_is_record
)
1193 if (array1
->live_out
!= array2
->live_out
)
1195 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
1197 if (array1
->declared
!= array2
->declared
)
1199 if (array1
->exposed
!= array2
->exposed
)
1205 /* Return 1 if the two pet_stmts are equivalent.
1207 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
1211 if (!stmt1
|| !stmt2
)
1214 if (pet_loc_get_line(stmt1
->loc
) != pet_loc_get_line(stmt2
->loc
))
1216 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
1218 if (!pet_tree_is_equal(stmt1
->body
, stmt2
->body
))
1220 if (stmt1
->n_arg
!= stmt2
->n_arg
)
1222 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
1223 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
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
)
1240 if (strcmp(type1
->name
, type2
->name
))
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
)
1254 if (implication1
->satisfied
!= implication2
->satisfied
)
1256 if (!isl_map_is_equal(implication1
->extension
, implication2
->extension
))
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
)
1270 if (!isl_union_map_is_equal(independence1
->filter
,
1271 independence2
->filter
))
1273 if (!isl_union_set_is_equal(independence1
->local
, independence2
->local
))
1279 /* Return 1 if the two pet_scops are equivalent.
1281 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1286 if (!scop1
|| !scop2
)
1289 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
1291 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
1293 equal
= isl_schedule_plain_is_equal(scop1
->schedule
, scop2
->schedule
);
1299 if (scop1
->n_type
!= scop2
->n_type
)
1301 for (i
= 0; i
< scop1
->n_type
; ++i
)
1302 if (!pet_type_is_equal(scop1
->types
[i
], scop2
->types
[i
]))
1305 if (scop1
->n_array
!= scop2
->n_array
)
1307 for (i
= 0; i
< scop1
->n_array
; ++i
)
1308 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
1311 if (scop1
->n_stmt
!= scop2
->n_stmt
)
1313 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
1314 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
1317 if (scop1
->n_implication
!= scop2
->n_implication
)
1319 for (i
= 0; i
< scop1
->n_implication
; ++i
)
1320 if (!pet_implication_is_equal(scop1
->implications
[i
],
1321 scop2
->implications
[i
]))
1324 if (scop1
->n_independence
!= scop2
->n_independence
)
1326 for (i
= 0; i
< scop1
->n_independence
; ++i
)
1327 if (!pet_independence_is_equal(scop1
->independences
[i
],
1328 scop2
->independences
[i
]))
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
)
1343 if (!isl_set_has_tuple_id(extent
))
1345 if (isl_set_is_wrapping(extent
))
1347 id
= isl_set_get_tuple_id(extent
);
1348 is_virtual
= !isl_id_get_user(id
);
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
)
1368 if (!array
|| !extent_is_virtual_array(array
->extent
)) {
1369 isl_set_free(domain
);
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
);
1380 return pet_array_free(array
);
1385 /* Intersect the initial dimensions of the domain of "stmt"
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
)
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
);
1409 return pet_stmt_free(stmt
);
1413 isl_set_free(domain
);
1414 return pet_stmt_free(stmt
);
1417 /* Intersect the initial dimensions of the domain of "implication"
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
)
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
);
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
)
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
])
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
])
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
)
1493 isl_set_free(domain
);
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)
1515 * forall i: not dom(l,i) or valid(l,i)
1519 * not exists i: dom(l,i) and not valid(l,i)
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
)
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
);
1543 /* Update the implication with respect to an embedding into a loop
1544 * with iteration domain "dom".
1546 * Since embed_access extends virtual arrays along with the domain
1547 * of the access, we need to do the same with domain and range
1548 * of the implication. Since the original implication is only valid
1549 * within a given iteration of the loop, the extended implication
1550 * maps the extra array dimension corresponding to the extra loop
1553 static struct pet_implication
*pet_implication_embed(
1554 struct pet_implication
*implication
, __isl_take isl_set
*dom
)
1562 map
= isl_set_identity(dom
);
1563 id
= isl_map_get_tuple_id(implication
->extension
, isl_dim_in
);
1564 map
= isl_map_flat_product(map
, implication
->extension
);
1565 map
= isl_map_set_tuple_id(map
, isl_dim_in
, isl_id_copy(id
));
1566 map
= isl_map_set_tuple_id(map
, isl_dim_out
, id
);
1567 implication
->extension
= map
;
1568 if (!implication
->extension
)
1569 return pet_implication_free(implication
);
1577 /* Internal data structure for outer_projection_mupa.
1579 * "n" is the number of outer dimensions onto which to project.
1580 * "res" collects the result.
1582 struct pet_outer_projection_data
{
1584 isl_union_pw_multi_aff
*res
;
1587 /* Create a function that maps "set" onto its outer data->n dimensions and
1588 * add it to data->res.
1590 static isl_stat
add_outer_projection(__isl_take isl_set
*set
, void *user
)
1592 struct pet_outer_projection_data
*data
= user
;
1595 isl_pw_multi_aff
*pma
;
1597 dim
= isl_set_dim(set
, isl_dim_set
);
1598 space
= isl_set_get_space(set
);
1599 pma
= isl_pw_multi_aff_project_out_map(space
,
1600 isl_dim_set
, data
->n
, dim
- data
->n
);
1601 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma
);
1608 /* Create and return a function that maps the sets in "domain"
1609 * onto their outer "n" dimensions.
1611 static __isl_give isl_multi_union_pw_aff
*outer_projection_mupa(
1612 __isl_take isl_union_set
*domain
, int n
)
1614 struct pet_outer_projection_data data
;
1617 space
= isl_union_set_get_space(domain
);
1619 data
.res
= isl_union_pw_multi_aff_empty(space
);
1620 if (isl_union_set_foreach_set(domain
, &add_outer_projection
, &data
) < 0)
1621 data
.res
= isl_union_pw_multi_aff_free(data
.res
);
1623 isl_union_set_free(domain
);
1624 return isl_multi_union_pw_aff_from_union_pw_multi_aff(data
.res
);
1627 /* Embed "schedule" in a loop with schedule "prefix".
1628 * The domain of "prefix" corresponds to the outer dimensions
1629 * of the iteration domains.
1630 * We therefore construct a projection onto these outer dimensions,
1631 * compose it with "prefix" and then add the result as a band schedule.
1633 * If the domain of the schedule is empty, then there is no need
1634 * to insert any node.
1636 static __isl_give isl_schedule
*schedule_embed(
1637 __isl_take isl_schedule
*schedule
, __isl_keep isl_multi_aff
*prefix
)
1641 isl_union_set
*domain
;
1643 isl_multi_union_pw_aff
*mupa
;
1645 domain
= isl_schedule_get_domain(schedule
);
1646 empty
= isl_union_set_is_empty(domain
);
1647 if (empty
< 0 || empty
) {
1648 isl_union_set_free(domain
);
1649 return empty
< 0 ? isl_schedule_free(schedule
) : schedule
;
1652 n
= isl_multi_aff_dim(prefix
, isl_dim_in
);
1653 mupa
= outer_projection_mupa(domain
, n
);
1654 ma
= isl_multi_aff_copy(prefix
);
1655 mupa
= isl_multi_union_pw_aff_apply_multi_aff(mupa
, ma
);
1656 schedule
= isl_schedule_insert_partial_schedule(schedule
, mupa
);
1661 /* Adjust the context and the schedule according to an embedding
1662 * in a loop with iteration domain "dom" and schedule "sched".
1664 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
1665 __isl_take isl_multi_aff
*sched
)
1672 scop
->context
= context_embed(scop
->context
, dom
);
1676 scop
->schedule
= schedule_embed(scop
->schedule
, sched
);
1677 if (!scop
->schedule
)
1681 isl_multi_aff_free(sched
);
1685 isl_multi_aff_free(sched
);
1686 return pet_scop_free(scop
);
1689 /* Add extra conditions to scop->skip[type].
1691 * The new skip condition only holds if it held before
1692 * and the condition is true. It does not hold if it did not hold
1693 * before or the condition is false.
1695 * The skip condition is assumed to be an affine expression.
1697 static struct pet_scop
*pet_scop_restrict_skip(struct pet_scop
*scop
,
1698 enum pet_skip type
, __isl_keep isl_set
*cond
)
1700 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1706 if (!ext
->skip
[type
])
1709 if (!multi_pw_aff_is_affine(ext
->skip
[type
]))
1710 isl_die(isl_multi_pw_aff_get_ctx(ext
->skip
[type
]),
1711 isl_error_internal
, "can only restrict affine skips",
1712 return pet_scop_free(scop
));
1714 skip
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
1715 dom
= isl_pw_aff_domain(isl_pw_aff_copy(skip
));
1716 cond
= isl_set_copy(cond
);
1717 cond
= isl_set_intersect(cond
, isl_pw_aff_non_zero_set(skip
));
1718 skip
= indicator_function(cond
, dom
);
1719 isl_multi_pw_aff_free(ext
->skip
[type
]);
1720 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
1721 if (!ext
->skip
[type
])
1722 return pet_scop_free(scop
);
1727 /* Adjust the context and the skip conditions to the fact that
1728 * the scop was created in a context where "cond" holds.
1730 * An outer loop iterator or parameter value is valid for the result
1731 * if it was valid for the original scop and satisfies "cond" or if it does
1732 * not satisfy "cond" as in this case the scop is not executed
1733 * and the original constraints on these values are irrelevant.
1735 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
1736 __isl_take isl_set
*cond
)
1740 scop
= pet_scop_restrict_skip(scop
, pet_skip_now
, cond
);
1741 scop
= pet_scop_restrict_skip(scop
, pet_skip_later
, cond
);
1746 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
1747 scop
->context
= isl_set_union(scop
->context
,
1748 isl_set_complement(isl_set_copy(cond
)));
1749 scop
->context
= isl_set_coalesce(scop
->context
);
1750 scop
->context
= pet_nested_remove_from_set(scop
->context
);
1758 return pet_scop_free(scop
);
1761 /* Insert an argument expression corresponding to "test" in front
1762 * of the list of arguments described by *n_arg and *args.
1764 static int args_insert_access(unsigned *n_arg
, pet_expr
***args
,
1765 __isl_keep isl_multi_pw_aff
*test
)
1768 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
1774 *args
= isl_calloc_array(ctx
, pet_expr
*, 1);
1779 ext
= isl_calloc_array(ctx
, pet_expr
*, 1 + *n_arg
);
1782 for (i
= 0; i
< *n_arg
; ++i
)
1783 ext
[1 + i
] = (*args
)[i
];
1788 (*args
)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
1795 /* Look through the applications in "scop" for any that can be
1796 * applied to the filter expressed by "map" and "satisified".
1797 * If there is any, then apply it to "map" and return the result.
1798 * Otherwise, return "map".
1799 * "id" is the identifier of the virtual array.
1801 * We only introduce at most one implication for any given virtual array,
1802 * so we can apply the implication and return as soon as we find one.
1804 static __isl_give isl_map
*apply_implications(struct pet_scop
*scop
,
1805 __isl_take isl_map
*map
, __isl_keep isl_id
*id
, int satisfied
)
1809 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1810 struct pet_implication
*pi
= scop
->implications
[i
];
1813 if (pi
->satisfied
!= satisfied
)
1815 pi_id
= isl_map_get_tuple_id(pi
->extension
, isl_dim_in
);
1820 return isl_map_apply_range(map
, isl_map_copy(pi
->extension
));
1826 /* Is the filter expressed by "test" and "satisfied" implied
1827 * by filter "pos" on "domain", with filter "expr", taking into
1828 * account the implications of "scop"?
1830 * For filter on domain implying that expressed by "test" and "satisfied",
1831 * the filter needs to be an access to the same (virtual) array as "test" and
1832 * the filter value needs to be equal to "satisfied".
1833 * Moreover, the filter access relation, possibly extended by
1834 * the implications in "scop" needs to contain "test".
1836 static int implies_filter(struct pet_scop
*scop
,
1837 __isl_keep isl_map
*domain
, int pos
, __isl_keep pet_expr
*expr
,
1838 __isl_keep isl_map
*test
, int satisfied
)
1840 isl_id
*test_id
, *arg_id
;
1847 if (expr
->type
!= pet_expr_access
)
1849 test_id
= isl_map_get_tuple_id(test
, isl_dim_out
);
1850 arg_id
= pet_expr_access_get_id(expr
);
1851 isl_id_free(arg_id
);
1852 isl_id_free(test_id
);
1853 if (test_id
!= arg_id
)
1855 val
= isl_map_plain_get_val_if_fixed(domain
, isl_dim_out
, pos
);
1856 is_int
= isl_val_is_int(val
);
1858 s
= isl_val_get_num_si(val
);
1867 implied
= isl_map_from_multi_pw_aff(pet_expr_access_get_index(expr
));
1868 implied
= apply_implications(scop
, implied
, test_id
, satisfied
);
1869 is_subset
= isl_map_is_subset(test
, implied
);
1870 isl_map_free(implied
);
1875 /* Is the filter expressed by "test" and "satisfied" implied
1876 * by any of the filters on the domain of "stmt", taking into
1877 * account the implications of "scop"?
1879 static int filter_implied(struct pet_scop
*scop
,
1880 struct pet_stmt
*stmt
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
1888 if (!scop
|| !stmt
|| !test
)
1890 if (scop
->n_implication
== 0)
1892 if (stmt
->n_arg
== 0)
1895 domain
= isl_set_unwrap(isl_set_copy(stmt
->domain
));
1896 test_map
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test
));
1899 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
1900 implied
= implies_filter(scop
, domain
, i
, stmt
->args
[i
],
1901 test_map
, satisfied
);
1902 if (implied
< 0 || implied
)
1906 isl_map_free(test_map
);
1907 isl_map_free(domain
);
1911 /* Make the statement "stmt" depend on the value of "test"
1912 * being equal to "satisfied" by adjusting stmt->domain.
1914 * The domain of "test" corresponds to the (zero or more) outer dimensions
1915 * of the iteration domain.
1917 * We first extend "test" to apply to the entire iteration domain and
1918 * then check if the filter that we are about to add is implied
1919 * by any of the current filters, possibly taking into account
1920 * the implications in "scop". If so, we leave "stmt" untouched and return.
1922 * Otherwise, we insert an argument corresponding to a read to "test"
1923 * from the iteration domain of "stmt" in front of the list of arguments.
1924 * We also insert a corresponding output dimension in the wrapped
1925 * map contained in stmt->domain, with value set to "satisfied".
1927 static struct pet_stmt
*stmt_filter(struct pet_scop
*scop
,
1928 struct pet_stmt
*stmt
, __isl_take isl_multi_pw_aff
*test
, int satisfied
)
1934 isl_pw_multi_aff
*pma
;
1935 isl_multi_aff
*add_dom
;
1937 isl_local_space
*ls
;
1943 space
= pet_stmt_get_space(stmt
);
1944 n_test_dom
= isl_multi_pw_aff_dim(test
, isl_dim_in
);
1945 space
= isl_space_from_domain(space
);
1946 space
= isl_space_add_dims(space
, isl_dim_out
, n_test_dom
);
1947 add_dom
= isl_multi_aff_zero(isl_space_copy(space
));
1948 ls
= isl_local_space_from_space(isl_space_domain(space
));
1949 for (i
= 0; i
< n_test_dom
; ++i
) {
1951 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
1953 add_dom
= isl_multi_aff_set_aff(add_dom
, i
, aff
);
1955 isl_local_space_free(ls
);
1956 test
= isl_multi_pw_aff_pullback_multi_aff(test
, add_dom
);
1958 implied
= filter_implied(scop
, stmt
, test
, satisfied
);
1962 isl_multi_pw_aff_free(test
);
1966 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
1967 pma
= pet_filter_insert_pma(isl_set_get_space(stmt
->domain
),
1969 stmt
->domain
= isl_set_preimage_pw_multi_aff(stmt
->domain
, pma
);
1971 if (args_insert_access(&stmt
->n_arg
, &stmt
->args
, test
) < 0)
1974 isl_multi_pw_aff_free(test
);
1977 isl_multi_pw_aff_free(test
);
1978 return pet_stmt_free(stmt
);
1981 /* Does "scop" have a skip condition of the given "type"?
1983 int pet_scop_has_skip(struct pet_scop
*scop
, enum pet_skip type
)
1985 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1989 return ext
->skip
[type
] != NULL
;
1992 /* Does "scop" have a skip condition of the given "type" that
1993 * is an affine expression?
1995 int pet_scop_has_affine_skip(struct pet_scop
*scop
, enum pet_skip type
)
1997 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2001 if (!ext
->skip
[type
])
2003 return multi_pw_aff_is_affine(ext
->skip
[type
]);
2006 /* Does "scop" have a skip condition of the given "type" that
2007 * is not an affine expression?
2009 int pet_scop_has_var_skip(struct pet_scop
*scop
, enum pet_skip type
)
2011 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2016 if (!ext
->skip
[type
])
2018 aff
= multi_pw_aff_is_affine(ext
->skip
[type
]);
2024 /* Does "scop" have a skip condition of the given "type" that
2025 * is affine and holds on the entire domain?
2027 int pet_scop_has_universal_skip(struct pet_scop
*scop
, enum pet_skip type
)
2029 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2035 is_aff
= pet_scop_has_affine_skip(scop
, type
);
2036 if (is_aff
< 0 || !is_aff
)
2039 pa
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
2040 set
= isl_pw_aff_non_zero_set(pa
);
2041 is_univ
= isl_set_plain_is_universe(set
);
2047 /* Replace scop->skip[type] by "skip".
2049 struct pet_scop
*pet_scop_set_skip(struct pet_scop
*scop
,
2050 enum pet_skip type
, __isl_take isl_multi_pw_aff
*skip
)
2052 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2057 isl_multi_pw_aff_free(ext
->skip
[type
]);
2058 ext
->skip
[type
] = skip
;
2062 isl_multi_pw_aff_free(skip
);
2063 return pet_scop_free(scop
);
2066 /* Return a copy of scop->skip[type].
2068 __isl_give isl_multi_pw_aff
*pet_scop_get_skip(struct pet_scop
*scop
,
2071 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2076 return isl_multi_pw_aff_copy(ext
->skip
[type
]);
2079 /* Assuming scop->skip[type] is an affine expression,
2080 * return the constraints on the outer loop domain for which the skip condition
2083 __isl_give isl_set
*pet_scop_get_affine_skip_domain(struct pet_scop
*scop
,
2086 isl_multi_pw_aff
*skip
;
2089 skip
= pet_scop_get_skip(scop
, type
);
2090 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
2091 isl_multi_pw_aff_free(skip
);
2092 return isl_pw_aff_non_zero_set(pa
);
2095 /* Return the identifier of the variable that is accessed by
2096 * the skip condition of the given type.
2098 * The skip condition is assumed not to be an affine condition.
2100 __isl_give isl_id
*pet_scop_get_skip_id(struct pet_scop
*scop
,
2103 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2108 return isl_multi_pw_aff_get_tuple_id(ext
->skip
[type
], isl_dim_out
);
2111 /* Return an access pet_expr corresponding to the skip condition
2112 * of the given type.
2114 __isl_give pet_expr
*pet_scop_get_skip_expr(struct pet_scop
*scop
,
2117 return pet_expr_from_index(pet_scop_get_skip(scop
, type
));
2120 /* Drop the skip condition scop->skip[type].
2122 void pet_scop_reset_skip(struct pet_scop
*scop
, enum pet_skip type
)
2124 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2129 isl_multi_pw_aff_free(ext
->skip
[type
]);
2130 ext
->skip
[type
] = NULL
;
2133 /* Drop all skip conditions on "scop".
2135 struct pet_scop
*pet_scop_reset_skips(struct pet_scop
*scop
)
2137 pet_scop_reset_skip(scop
, pet_skip_now
);
2138 pet_scop_reset_skip(scop
, pet_skip_later
);
2143 /* Make the skip condition (if any) depend on the value of "test" being
2144 * equal to "satisfied".
2146 * We only support the case where the original skip condition is universal,
2147 * i.e., where skipping is unconditional, and where satisfied == 1.
2148 * In this case, the skip condition is changed to skip only when
2149 * "test" is equal to one.
2151 static struct pet_scop
*pet_scop_filter_skip(struct pet_scop
*scop
,
2152 enum pet_skip type
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
2158 if (!pet_scop_has_skip(scop
, type
))
2162 is_univ
= pet_scop_has_universal_skip(scop
, type
);
2164 return pet_scop_free(scop
);
2165 if (satisfied
&& is_univ
) {
2166 isl_multi_pw_aff
*skip
;
2167 skip
= isl_multi_pw_aff_copy(test
);
2168 scop
= pet_scop_set_skip(scop
, type
, skip
);
2172 isl_die(isl_multi_pw_aff_get_ctx(test
), isl_error_internal
,
2173 "skip expression cannot be filtered",
2174 return pet_scop_free(scop
));
2180 /* Make all statements in "scop" depend on the value of "test"
2181 * being equal to "satisfied" by adjusting their domains.
2183 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
2184 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2188 scop
= pet_scop_filter_skip(scop
, pet_skip_now
, test
, satisfied
);
2189 scop
= pet_scop_filter_skip(scop
, pet_skip_later
, test
, satisfied
);
2194 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2195 scop
->stmts
[i
] = stmt_filter(scop
, scop
->stmts
[i
],
2196 isl_multi_pw_aff_copy(test
), satisfied
);
2197 if (!scop
->stmts
[i
])
2201 isl_multi_pw_aff_free(test
);
2204 isl_multi_pw_aff_free(test
);
2205 return pet_scop_free(scop
);
2208 /* Add the parameters of the access expression "expr" to "space".
2210 static int access_collect_params(__isl_keep pet_expr
*expr
, void *user
)
2213 isl_space
*expr_space
;
2214 isl_space
**space
= user
;
2216 expr_space
= pet_expr_access_get_parameter_space(expr
);
2217 *space
= isl_space_align_params(*space
, expr_space
);
2219 return *space
? 0 : -1;
2222 /* Add all parameters in "stmt" to "space" and return the result.
2224 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
2225 __isl_take isl_space
*space
)
2230 return isl_space_free(space
);
2232 space
= isl_space_align_params(space
, isl_set_get_space(stmt
->domain
));
2233 for (i
= 0; i
< stmt
->n_arg
; ++i
)
2234 if (pet_expr_foreach_access_expr(stmt
->args
[i
],
2235 &access_collect_params
, &space
) < 0)
2236 space
= isl_space_free(space
);
2237 if (pet_tree_foreach_access_expr(stmt
->body
, &access_collect_params
,
2239 space
= isl_space_free(space
);
2244 /* Add all parameters in "array" to "space" and return the result.
2246 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
2247 __isl_take isl_space
*space
)
2250 return isl_space_free(space
);
2252 space
= isl_space_align_params(space
,
2253 isl_set_get_space(array
->context
));
2254 space
= isl_space_align_params(space
, isl_set_get_space(array
->extent
));
2259 /* Add all parameters in "independence" to "space" and return the result.
2261 static __isl_give isl_space
*independence_collect_params(
2262 struct pet_independence
*independence
, __isl_take isl_space
*space
)
2265 return isl_space_free(space
);
2267 space
= isl_space_align_params(space
,
2268 isl_union_map_get_space(independence
->filter
));
2269 space
= isl_space_align_params(space
,
2270 isl_union_set_get_space(independence
->local
));
2275 /* Collect all parameters in "scop" in a parameter space and return the result.
2277 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
)
2285 space
= isl_set_get_space(scop
->context
);
2287 for (i
= 0; i
< scop
->n_array
; ++i
)
2288 space
= array_collect_params(scop
->arrays
[i
], space
);
2290 for (i
= 0; i
< scop
->n_stmt
; ++i
)
2291 space
= stmt_collect_params(scop
->stmts
[i
], space
);
2293 for (i
= 0; i
< scop
->n_independence
; ++i
)
2294 space
= independence_collect_params(scop
->independences
[i
],
2300 /* Add all parameters in "space" to the domain and
2301 * all access relations in "stmt".
2303 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
2304 __isl_take isl_space
*space
)
2311 stmt
->domain
= isl_set_align_params(stmt
->domain
,
2312 isl_space_copy(space
));
2314 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2315 stmt
->args
[i
] = pet_expr_align_params(stmt
->args
[i
],
2316 isl_space_copy(space
));
2320 stmt
->body
= pet_tree_align_params(stmt
->body
, isl_space_copy(space
));
2322 if (!stmt
->domain
|| !stmt
->body
)
2325 isl_space_free(space
);
2328 isl_space_free(space
);
2329 return pet_stmt_free(stmt
);
2332 /* Add all parameters in "space" to "array".
2334 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
2335 __isl_take isl_space
*space
)
2340 array
->context
= isl_set_align_params(array
->context
,
2341 isl_space_copy(space
));
2342 array
->extent
= isl_set_align_params(array
->extent
,
2343 isl_space_copy(space
));
2344 if (array
->value_bounds
) {
2345 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
2346 isl_space_copy(space
));
2347 if (!array
->value_bounds
)
2351 if (!array
->context
|| !array
->extent
)
2354 isl_space_free(space
);
2357 isl_space_free(space
);
2358 return pet_array_free(array
);
2361 /* Add all parameters in "space" to "independence".
2363 static struct pet_independence
*independence_propagate_params(
2364 struct pet_independence
*independence
, __isl_take isl_space
*space
)
2369 independence
->filter
= isl_union_map_align_params(independence
->filter
,
2370 isl_space_copy(space
));
2371 independence
->local
= isl_union_set_align_params(independence
->local
,
2372 isl_space_copy(space
));
2373 if (!independence
->filter
|| !independence
->local
)
2376 isl_space_free(space
);
2377 return independence
;
2379 isl_space_free(space
);
2380 return pet_independence_free(independence
);
2383 /* Add all parameters in "space" to "scop".
2385 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
2386 __isl_take isl_space
*space
)
2393 scop
->context
= isl_set_align_params(scop
->context
,
2394 isl_space_copy(space
));
2395 scop
->schedule
= isl_schedule_align_params(scop
->schedule
,
2396 isl_space_copy(space
));
2397 if (!scop
->context
|| !scop
->schedule
)
2400 for (i
= 0; i
< scop
->n_array
; ++i
) {
2401 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
2402 isl_space_copy(space
));
2403 if (!scop
->arrays
[i
])
2407 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2408 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
2409 isl_space_copy(space
));
2410 if (!scop
->stmts
[i
])
2414 for (i
= 0; i
< scop
->n_independence
; ++i
) {
2415 scop
->independences
[i
] = independence_propagate_params(
2416 scop
->independences
[i
], isl_space_copy(space
));
2417 if (!scop
->independences
[i
])
2421 isl_space_free(space
);
2424 isl_space_free(space
);
2425 return pet_scop_free(scop
);
2428 /* Update all isl_sets and isl_maps in "scop" such that they all
2429 * have the same parameters.
2431 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
2438 space
= scop_collect_params(scop
);
2440 scop
= scop_propagate_params(scop
, space
);
2445 /* Add the access relation of the give "type" of the access expression "expr"
2446 * to "accesses" and return the result.
2447 * The domain of the access relation is intersected with "domain".
2448 * If "tag" is set, then the access relation is tagged with
2449 * the corresponding reference identifier.
2451 static __isl_give isl_union_map
*expr_collect_access(__isl_keep pet_expr
*expr
,
2452 enum pet_expr_access_type type
, int tag
,
2453 __isl_take isl_union_map
*accesses
, __isl_keep isl_union_set
*domain
)
2455 isl_union_map
*access
;
2457 access
= pet_expr_access_get_access(expr
, type
);
2458 access
= isl_union_map_intersect_domain(access
,
2459 isl_union_set_copy(domain
));
2461 access
= pet_expr_tag_access(expr
, access
);
2462 return isl_union_map_union(accesses
, access
);
2465 /* Internal data structure for expr_collect_accesses.
2467 * "type" is the type of accesses we want to collect.
2468 * "tag" is set if the access relations should be tagged with
2469 * the corresponding reference identifiers.
2470 * "domain" are constraints on the domain of the access relations.
2471 * "accesses" collects the results.
2473 struct pet_expr_collect_accesses_data
{
2474 enum pet_expr_access_type type
;
2476 isl_union_set
*domain
;
2478 isl_union_map
*accesses
;
2481 /* Add the access relation of the access expression "expr"
2482 * to data->accesses if the access expression is a read and we are collecting
2483 * reads and/or it is a write and we are collecting writes.
2484 * The domains of the access relations are intersected with data->domain.
2485 * If data->tag is set, then the access relations are tagged with
2486 * the corresponding reference identifiers.
2488 * If data->type is pet_expr_access_must_write, then we only add
2489 * the accesses that are definitely performed. Otherwise, we add
2490 * all potential accesses.
2491 * In particular, if the access has any arguments, then in case of
2492 * pet_expr_access_must_write we currently skip the access completely.
2493 * In other cases, we project out the values of the access arguments.
2495 static int expr_collect_accesses(__isl_keep pet_expr
*expr
, void *user
)
2497 struct pet_expr_collect_accesses_data
*data
= user
;
2505 if (pet_expr_is_affine(expr
))
2507 if (data
->type
== pet_expr_access_must_write
&& expr
->n_arg
!= 0)
2510 if ((data
->type
== pet_expr_access_may_read
&& expr
->acc
.read
) ||
2511 ((data
->type
== pet_expr_access_may_write
||
2512 data
->type
== pet_expr_access_must_write
) && expr
->acc
.write
))
2513 data
->accesses
= expr_collect_access(expr
,
2514 data
->type
, data
->tag
,
2515 data
->accesses
, data
->domain
);
2517 return data
->accesses
? 0 : -1;
2520 /* Collect and return all access relations of the given "type" in "stmt".
2521 * If "tag" is set, then the access relations are tagged with
2522 * the corresponding reference identifiers.
2523 * If "type" is pet_expr_access_killed, then "stmt" is a kill statement and
2524 * we simply add the argument of the kill operation.
2526 * If we are looking for definite accesses (pet_expr_access_must_write
2527 * or pet_expr_access_killed), then we only add the accesses that are
2528 * definitely performed. Otherwise, we add all potential accesses.
2529 * In particular, if the statement has any arguments, then if we are looking
2530 * for definite accesses we currently skip the statement completely. Othewise,
2531 * we project out the values of the statement arguments.
2532 * If the statement body is not an expression tree, then we cannot
2533 * know for sure if/when the accesses inside the tree are performed.
2534 * We therefore ignore such statements when we are looking for
2535 * definite accesses.
2537 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
2538 enum pet_expr_access_type type
, int tag
, __isl_take isl_space
*dim
)
2540 struct pet_expr_collect_accesses_data data
= { type
, tag
};
2547 data
.accesses
= isl_union_map_empty(dim
);
2549 if (type
== pet_expr_access_must_write
||
2550 type
== pet_expr_access_killed
)
2555 if (must
&& stmt
->n_arg
> 0)
2556 return data
.accesses
;
2557 if (must
&& pet_tree_get_type(stmt
->body
) != pet_tree_expr
)
2558 return data
.accesses
;
2560 domain
= drop_arguments(isl_set_copy(stmt
->domain
));
2561 data
.domain
= isl_union_set_from_set(domain
);
2563 if (type
== pet_expr_access_killed
) {
2564 pet_expr
*body
, *arg
;
2566 body
= pet_tree_expr_get_expr(stmt
->body
);
2567 arg
= pet_expr_get_arg(body
, 0);
2568 data
.accesses
= expr_collect_access(arg
,
2569 pet_expr_access_killed
, tag
,
2570 data
.accesses
, data
.domain
);
2572 pet_expr_free(body
);
2573 } else if (pet_tree_foreach_access_expr(stmt
->body
,
2574 &expr_collect_accesses
, &data
) < 0)
2575 data
.accesses
= isl_union_map_free(data
.accesses
);
2577 isl_union_set_free(data
.domain
);
2579 return data
.accesses
;
2582 /* Is "stmt" an assignment statement?
2584 int pet_stmt_is_assign(struct pet_stmt
*stmt
)
2588 return pet_tree_is_assign(stmt
->body
);
2591 /* Is "stmt" a kill statement?
2593 int pet_stmt_is_kill(struct pet_stmt
*stmt
)
2597 return pet_tree_is_kill(stmt
->body
);
2600 /* Is "stmt" an assume statement?
2602 int pet_stmt_is_assume(struct pet_stmt
*stmt
)
2606 return pet_tree_is_assume(stmt
->body
);
2609 /* Helper function to add a domain gisted copy of "map" (wrt "set") to "umap".
2611 static __isl_give isl_union_map
*add_gisted(__isl_take isl_union_map
*umap
,
2612 __isl_keep isl_map
*map
, __isl_keep isl_set
*set
)
2616 gist
= isl_map_copy(map
);
2617 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
2618 return isl_union_map_add_map(umap
, gist
);
2621 /* Compute a mapping from all arrays (of structs) in scop
2624 * If "from_outermost" is set, then the domain only consists
2625 * of outermost arrays.
2626 * If "to_innermost" is set, then the range only consists
2627 * of innermost arrays.
2629 static __isl_give isl_union_map
*compute_to_inner(struct pet_scop
*scop
,
2630 int from_outermost
, int to_innermost
)
2633 isl_union_map
*to_inner
;
2638 to_inner
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2640 for (i
= 0; i
< scop
->n_array
; ++i
) {
2641 struct pet_array
*array
= scop
->arrays
[i
];
2645 if (to_innermost
&& array
->element_is_record
)
2648 set
= isl_set_copy(array
->extent
);
2649 map
= isl_set_identity(isl_set_copy(set
));
2651 while (set
&& isl_set_is_wrapping(set
)) {
2655 if (!from_outermost
)
2656 to_inner
= add_gisted(to_inner
, map
, set
);
2658 id
= isl_set_get_tuple_id(set
);
2659 wrapped
= isl_set_unwrap(set
);
2660 wrapped
= isl_map_domain_map(wrapped
);
2661 wrapped
= isl_map_set_tuple_id(wrapped
, isl_dim_in
, id
);
2662 map
= isl_map_apply_domain(map
, wrapped
);
2663 set
= isl_map_domain(isl_map_copy(map
));
2666 map
= isl_map_gist_domain(map
, set
);
2667 to_inner
= isl_union_map_add_map(to_inner
, map
);
2673 /* Compute a mapping from all arrays (of structs) in scop
2674 * to their innermost arrays.
2676 * In particular, for each array of a primitive type, the result
2677 * contains the identity mapping on that array.
2678 * For each array involving member accesses, the result
2679 * contains a mapping from the elements of any intermediate array of structs
2680 * to all corresponding elements of the innermost nested arrays.
2682 static __isl_give isl_union_map
*pet_scop_compute_any_to_inner(
2683 struct pet_scop
*scop
)
2685 return compute_to_inner(scop
, 0, 1);
2688 /* Compute a mapping from all outermost arrays (of structs) in scop
2689 * to their innermost members.
2691 __isl_give isl_union_map
*pet_scop_compute_outer_to_inner(struct pet_scop
*scop
)
2693 return compute_to_inner(scop
, 1, 1);
2696 /* Compute a mapping from all outermost arrays (of structs) in scop
2697 * to their members, including the outermost arrays themselves.
2699 __isl_give isl_union_map
*pet_scop_compute_outer_to_any(struct pet_scop
*scop
)
2701 return compute_to_inner(scop
, 1, 0);
2704 /* Collect and return all access relations of the given "type" in "scop".
2705 * If "type" is pet_expr_access_killed, then we only add the arguments of
2707 * If we are looking for definite accesses (pet_expr_access_must_write
2708 * or pet_expr_access_killed), then we only add the accesses that are
2709 * definitely performed. Otherwise, we add all potential accesses.
2710 * If "tag" is set, then the access relations are tagged with
2711 * the corresponding reference identifiers.
2712 * For accesses to structures, the returned access relation accesses
2713 * all individual fields in the structures.
2715 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
2716 enum pet_expr_access_type type
, int tag
)
2719 isl_union_map
*accesses
;
2720 isl_union_set
*arrays
;
2721 isl_union_map
*to_inner
;
2726 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2728 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2729 struct pet_stmt
*stmt
= scop
->stmts
[i
];
2730 isl_union_map
*accesses_i
;
2733 if (type
== pet_expr_access_killed
&& !pet_stmt_is_kill(stmt
))
2736 space
= isl_set_get_space(scop
->context
);
2737 accesses_i
= stmt_collect_accesses(stmt
, type
, tag
, space
);
2738 accesses
= isl_union_map_union(accesses
, accesses_i
);
2741 arrays
= isl_union_set_empty(isl_union_map_get_space(accesses
));
2742 for (i
= 0; i
< scop
->n_array
; ++i
) {
2743 isl_set
*extent
= isl_set_copy(scop
->arrays
[i
]->extent
);
2744 arrays
= isl_union_set_add_set(arrays
, extent
);
2746 accesses
= isl_union_map_intersect_range(accesses
, arrays
);
2748 to_inner
= pet_scop_compute_any_to_inner(scop
);
2749 accesses
= isl_union_map_apply_range(accesses
, to_inner
);
2754 /* Return the potential read access relation.
2756 __isl_give isl_union_map
*pet_scop_get_may_reads(struct pet_scop
*scop
)
2758 return scop_collect_accesses(scop
, pet_expr_access_may_read
, 0);
2761 /* Return the potential write access relation.
2763 __isl_give isl_union_map
*pet_scop_get_may_writes(struct pet_scop
*scop
)
2765 return scop_collect_accesses(scop
, pet_expr_access_may_write
, 0);
2768 /* Return the definite write access relation.
2770 __isl_give isl_union_map
*pet_scop_get_must_writes(struct pet_scop
*scop
)
2772 return scop_collect_accesses(scop
, pet_expr_access_must_write
, 0);
2775 /* Return the definite kill access relation.
2777 __isl_give isl_union_map
*pet_scop_get_must_kills(struct pet_scop
*scop
)
2779 return scop_collect_accesses(scop
, pet_expr_access_killed
, 0);
2782 /* Return the tagged potential read access relation.
2784 __isl_give isl_union_map
*pet_scop_get_tagged_may_reads(
2785 struct pet_scop
*scop
)
2787 return scop_collect_accesses(scop
, pet_expr_access_may_read
, 1);
2790 /* Return the tagged potential write access relation.
2792 __isl_give isl_union_map
*pet_scop_get_tagged_may_writes(
2793 struct pet_scop
*scop
)
2795 return scop_collect_accesses(scop
, pet_expr_access_may_write
, 1);
2798 /* Return the tagged definite write access relation.
2800 __isl_give isl_union_map
*pet_scop_get_tagged_must_writes(
2801 struct pet_scop
*scop
)
2803 return scop_collect_accesses(scop
, pet_expr_access_must_write
, 1);
2806 /* Return the tagged definite kill access relation.
2808 __isl_give isl_union_map
*pet_scop_get_tagged_must_kills(
2809 struct pet_scop
*scop
)
2811 return scop_collect_accesses(scop
, pet_expr_access_killed
, 1);
2814 /* Collect and return the set of all statement instances in "scop".
2816 __isl_give isl_union_set
*pet_scop_get_instance_set(struct pet_scop
*scop
)
2820 isl_union_set
*domain
;
2825 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
2827 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2828 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
2829 if (scop
->stmts
[i
]->n_arg
> 0)
2830 domain_i
= isl_map_domain(isl_set_unwrap(domain_i
));
2831 domain
= isl_union_set_add_set(domain
, domain_i
);
2837 /* Return the context of "scop".
2839 __isl_give isl_set
*pet_scop_get_context(__isl_keep pet_scop
*scop
)
2844 return isl_set_copy(scop
->context
);
2847 /* Return the schedule of "scop".
2849 __isl_give isl_schedule
*pet_scop_get_schedule(__isl_keep pet_scop
*scop
)
2854 return isl_schedule_copy(scop
->schedule
);
2857 /* Add a reference identifier to all access expressions in "stmt".
2858 * "n_ref" points to an integer that contains the sequence number
2859 * of the next reference.
2861 static struct pet_stmt
*stmt_add_ref_ids(struct pet_stmt
*stmt
, int *n_ref
)
2868 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2869 stmt
->args
[i
] = pet_expr_add_ref_ids(stmt
->args
[i
], n_ref
);
2871 return pet_stmt_free(stmt
);
2874 stmt
->body
= pet_tree_add_ref_ids(stmt
->body
, n_ref
);
2876 return pet_stmt_free(stmt
);
2881 /* Add a reference identifier to all access expressions in "scop".
2883 struct pet_scop
*pet_scop_add_ref_ids(struct pet_scop
*scop
)
2892 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2893 scop
->stmts
[i
] = stmt_add_ref_ids(scop
->stmts
[i
], &n_ref
);
2894 if (!scop
->stmts
[i
])
2895 return pet_scop_free(scop
);
2901 /* Reset the user pointer on all parameter ids in "array".
2903 static struct pet_array
*array_anonymize(struct pet_array
*array
)
2908 array
->context
= isl_set_reset_user(array
->context
);
2909 array
->extent
= isl_set_reset_user(array
->extent
);
2910 if (!array
->context
|| !array
->extent
)
2911 return pet_array_free(array
);
2916 /* Reset the user pointer on all parameter and tuple ids in "stmt".
2918 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
2927 stmt
->domain
= isl_set_reset_user(stmt
->domain
);
2929 return pet_stmt_free(stmt
);
2931 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2932 stmt
->args
[i
] = pet_expr_anonymize(stmt
->args
[i
]);
2934 return pet_stmt_free(stmt
);
2937 stmt
->body
= pet_tree_anonymize(stmt
->body
);
2939 return pet_stmt_free(stmt
);
2944 /* Reset the user pointer on the tuple ids and all parameter ids
2947 static struct pet_implication
*implication_anonymize(
2948 struct pet_implication
*implication
)
2953 implication
->extension
= isl_map_reset_user(implication
->extension
);
2954 if (!implication
->extension
)
2955 return pet_implication_free(implication
);
2960 /* Reset the user pointer on the tuple ids and all parameter ids
2961 * in "independence".
2963 static struct pet_independence
*independence_anonymize(
2964 struct pet_independence
*independence
)
2969 independence
->filter
= isl_union_map_reset_user(independence
->filter
);
2970 independence
->local
= isl_union_set_reset_user(independence
->local
);
2971 if (!independence
->filter
|| !independence
->local
)
2972 return pet_independence_free(independence
);
2974 return independence
;
2977 /* Reset the user pointer on all parameter and tuple ids in "scop".
2979 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
2986 scop
->context
= isl_set_reset_user(scop
->context
);
2987 scop
->context_value
= isl_set_reset_user(scop
->context_value
);
2988 scop
->schedule
= isl_schedule_reset_user(scop
->schedule
);
2989 if (!scop
->context
|| !scop
->context_value
|| !scop
->schedule
)
2990 return pet_scop_free(scop
);
2992 for (i
= 0; i
< scop
->n_array
; ++i
) {
2993 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
2994 if (!scop
->arrays
[i
])
2995 return pet_scop_free(scop
);
2998 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2999 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
3000 if (!scop
->stmts
[i
])
3001 return pet_scop_free(scop
);
3004 for (i
= 0; i
< scop
->n_implication
; ++i
) {
3005 scop
->implications
[i
] =
3006 implication_anonymize(scop
->implications
[i
]);
3007 if (!scop
->implications
[i
])
3008 return pet_scop_free(scop
);
3011 for (i
= 0; i
< scop
->n_independence
; ++i
) {
3012 scop
->independences
[i
] =
3013 independence_anonymize(scop
->independences
[i
]);
3014 if (!scop
->independences
[i
])
3015 return pet_scop_free(scop
);
3021 /* Compute the gist of the iteration domain and all access relations
3022 * of "stmt" based on the constraints on the parameters specified by "context"
3023 * and the constraints on the values of nested accesses specified
3024 * by "value_bounds".
3026 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
3027 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
3035 domain
= isl_set_copy(stmt
->domain
);
3036 if (stmt
->n_arg
> 0)
3037 domain
= isl_map_domain(isl_set_unwrap(domain
));
3039 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
3041 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
3042 stmt
->args
[i
] = pet_expr_gist(stmt
->args
[i
],
3043 domain
, value_bounds
);
3048 stmt
->body
= pet_tree_gist(stmt
->body
, domain
, value_bounds
);
3052 isl_set_free(domain
);
3054 domain
= isl_set_universe(pet_stmt_get_space(stmt
));
3055 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
3056 if (stmt
->n_arg
> 0)
3057 domain
= pet_value_bounds_apply(domain
, stmt
->n_arg
, stmt
->args
,
3059 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
3061 return pet_stmt_free(stmt
);
3065 isl_set_free(domain
);
3066 return pet_stmt_free(stmt
);
3069 /* Compute the gist of the extent of the array
3070 * based on the constraints on the parameters specified by "context".
3072 static struct pet_array
*array_gist(struct pet_array
*array
,
3073 __isl_keep isl_set
*context
)
3078 array
->extent
= isl_set_gist_params(array
->extent
,
3079 isl_set_copy(context
));
3081 return pet_array_free(array
);
3086 /* Compute the gist of all sets and relations in "scop"
3087 * based on the constraints on the parameters specified by "scop->context"
3088 * and the constraints on the values of nested accesses specified
3089 * by "value_bounds".
3091 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
3092 __isl_keep isl_union_map
*value_bounds
)
3099 scop
->context
= isl_set_coalesce(scop
->context
);
3101 return pet_scop_free(scop
);
3103 scop
->schedule
= isl_schedule_gist_domain_params(scop
->schedule
,
3104 isl_set_copy(scop
->context
));
3105 if (!scop
->schedule
)
3106 return pet_scop_free(scop
);
3108 for (i
= 0; i
< scop
->n_array
; ++i
) {
3109 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
3110 if (!scop
->arrays
[i
])
3111 return pet_scop_free(scop
);
3114 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3115 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
3117 if (!scop
->stmts
[i
])
3118 return pet_scop_free(scop
);
3124 /* Intersect the context of "scop" with "context".
3125 * To ensure that we don't introduce any unnamed parameters in
3126 * the context of "scop", we first remove the unnamed parameters
3129 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
3130 __isl_take isl_set
*context
)
3135 context
= pet_nested_remove_from_set(context
);
3136 scop
->context
= isl_set_intersect(scop
->context
, context
);
3138 return pet_scop_free(scop
);
3142 isl_set_free(context
);
3143 return pet_scop_free(scop
);
3146 /* Drop the current context of "scop". That is, replace the context
3147 * by a universal set.
3149 struct pet_scop
*pet_scop_reset_context(struct pet_scop
*scop
)
3156 space
= isl_set_get_space(scop
->context
);
3157 isl_set_free(scop
->context
);
3158 scop
->context
= isl_set_universe(space
);
3160 return pet_scop_free(scop
);
3165 /* Append "array" to the arrays of "scop".
3167 struct pet_scop
*pet_scop_add_array(struct pet_scop
*scop
,
3168 struct pet_array
*array
)
3171 struct pet_array
**arrays
;
3173 if (!array
|| !scop
)
3176 ctx
= isl_set_get_ctx(scop
->context
);
3177 arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
3181 scop
->arrays
= arrays
;
3182 scop
->arrays
[scop
->n_array
] = array
;
3184 scop
->context
= isl_set_intersect_params(scop
->context
,
3185 isl_set_copy(array
->context
));
3187 return pet_scop_free(scop
);
3191 pet_array_free(array
);
3192 return pet_scop_free(scop
);
3195 /* Create an index expression for an access to a virtual array
3196 * representing the result of a condition.
3197 * Unlike other accessed data, the id of the array is NULL as
3198 * there is no ValueDecl in the program corresponding to the virtual
3200 * The index expression is created as an identity mapping on "space".
3201 * That is, the dimension of the array is the same as that of "space".
3203 __isl_give isl_multi_pw_aff
*pet_create_test_index(__isl_take isl_space
*space
,
3209 snprintf(name
, sizeof(name
), "__pet_test_%d", test_nr
);
3210 id
= isl_id_alloc(isl_space_get_ctx(space
), name
, NULL
);
3211 space
= isl_space_map_from_set(space
);
3212 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
3213 return isl_multi_pw_aff_identity(space
);
3216 /* Add an array with the given extent to the list
3217 * of arrays in "scop" and return the extended pet_scop.
3218 * Specifically, the extent is determined by the image of "domain"
3220 * "int_size" is the number of bytes needed to represent values of type "int".
3221 * The array is marked as attaining values 0 and 1 only and
3222 * as each element being assigned at most once.
3224 struct pet_scop
*pet_scop_add_boolean_array(struct pet_scop
*scop
,
3225 __isl_take isl_set
*domain
, __isl_take isl_multi_pw_aff
*index
,
3230 struct pet_array
*array
;
3233 if (!scop
|| !domain
|| !index
)
3236 ctx
= isl_multi_pw_aff_get_ctx(index
);
3237 array
= isl_calloc_type(ctx
, struct pet_array
);
3241 access
= isl_map_from_multi_pw_aff(index
);
3242 access
= isl_map_intersect_domain(access
, domain
);
3243 array
->extent
= isl_map_range(access
);
3244 space
= isl_space_params_alloc(ctx
, 0);
3245 array
->context
= isl_set_universe(space
);
3246 space
= isl_space_set_alloc(ctx
, 0, 1);
3247 array
->value_bounds
= isl_set_universe(space
);
3248 array
->value_bounds
= isl_set_lower_bound_si(array
->value_bounds
,
3250 array
->value_bounds
= isl_set_upper_bound_si(array
->value_bounds
,
3252 array
->element_type
= strdup("int");
3253 array
->element_size
= int_size
;
3254 array
->uniquely_defined
= 1;
3256 if (!array
->extent
|| !array
->context
)
3257 array
= pet_array_free(array
);
3259 scop
= pet_scop_add_array(scop
, array
);
3263 isl_set_free(domain
);
3264 isl_multi_pw_aff_free(index
);
3265 return pet_scop_free(scop
);
3268 /* Create and return an implication on filter values equal to "satisfied"
3269 * with extension "map".
3271 static struct pet_implication
*new_implication(__isl_take isl_map
*map
,
3275 struct pet_implication
*implication
;
3279 ctx
= isl_map_get_ctx(map
);
3280 implication
= isl_alloc_type(ctx
, struct pet_implication
);
3284 implication
->extension
= map
;
3285 implication
->satisfied
= satisfied
;
3293 /* Add an implication on filter values equal to "satisfied"
3294 * with extension "map" to "scop".
3296 struct pet_scop
*pet_scop_add_implication(struct pet_scop
*scop
,
3297 __isl_take isl_map
*map
, int satisfied
)
3300 struct pet_implication
*implication
;
3301 struct pet_implication
**implications
;
3303 implication
= new_implication(map
, satisfied
);
3304 if (!scop
|| !implication
)
3307 ctx
= isl_set_get_ctx(scop
->context
);
3308 implications
= isl_realloc_array(ctx
, scop
->implications
,
3309 struct pet_implication
*,
3310 scop
->n_implication
+ 1);
3313 scop
->implications
= implications
;
3314 scop
->implications
[scop
->n_implication
] = implication
;
3315 scop
->n_implication
++;
3319 pet_implication_free(implication
);
3320 return pet_scop_free(scop
);
3323 /* Create and return a function that maps the iteration domains
3324 * of the statements in "scop" onto their outer "n" dimensions.
3325 * "space" is the parameters space of the created function.
3327 static __isl_give isl_union_pw_multi_aff
*outer_projection(
3328 struct pet_scop
*scop
, __isl_take isl_space
*space
, int n
)
3331 isl_union_pw_multi_aff
*res
;
3333 res
= isl_union_pw_multi_aff_empty(space
);
3336 return isl_union_pw_multi_aff_free(res
);
3338 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3339 struct pet_stmt
*stmt
= scop
->stmts
[i
];
3342 isl_pw_multi_aff
*pma
;
3344 space
= pet_stmt_get_space(stmt
);
3345 ma
= pet_prefix_projection(space
, n
);
3346 pma
= isl_pw_multi_aff_from_multi_aff(ma
);
3347 res
= isl_union_pw_multi_aff_add_pw_multi_aff(res
, pma
);
3353 /* Add an independence to "scop" for the inner iterator of "domain"
3354 * with local variables "local", where "domain" represents the outer
3355 * loop iterators of all statements in "scop".
3356 * If "sign" is positive, then the inner iterator increases.
3357 * Otherwise it decreases.
3359 * The independence is supposed to filter out any dependence of
3360 * an iteration of domain on a previous iteration along the inner dimension.
3361 * We therefore create a mapping from an iteration to later iterations and
3362 * then plug in the projection of the iterations domains of "scop"
3363 * onto the outer loop iterators.
3365 struct pet_scop
*pet_scop_set_independent(struct pet_scop
*scop
,
3366 __isl_keep isl_set
*domain
, __isl_take isl_union_set
*local
, int sign
)
3371 isl_union_map
*independence
;
3372 isl_union_pw_multi_aff
*proj
;
3374 if (!scop
|| !domain
|| !local
)
3377 dim
= isl_set_dim(domain
, isl_dim_set
);
3378 space
= isl_space_map_from_set(isl_set_get_space(domain
));
3379 map
= isl_map_universe(space
);
3380 for (i
= 0; i
+ 1 < dim
; ++i
)
3381 map
= isl_map_equate(map
, isl_dim_in
, i
, isl_dim_out
, i
);
3383 map
= isl_map_order_lt(map
,
3384 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
3386 map
= isl_map_order_gt(map
,
3387 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
3389 independence
= isl_union_map_from_map(map
);
3390 space
= isl_space_params(isl_set_get_space(domain
));
3391 proj
= outer_projection(scop
, space
, dim
);
3392 independence
= isl_union_map_preimage_domain_union_pw_multi_aff(
3393 independence
, isl_union_pw_multi_aff_copy(proj
));
3394 independence
= isl_union_map_preimage_range_union_pw_multi_aff(
3395 independence
, proj
);
3397 scop
= pet_scop_add_independence(scop
, independence
, local
);
3401 isl_union_set_free(local
);
3402 return pet_scop_free(scop
);
3405 /* Given an access expression, check if it is data dependent.
3406 * If so, set *found and abort the search.
3408 static int is_data_dependent(__isl_keep pet_expr
*expr
, void *user
)
3412 if (pet_expr_get_n_arg(expr
) > 0) {
3420 /* Does "scop" contain any data dependent accesses?
3422 * Check the body of each statement for such accesses.
3424 int pet_scop_has_data_dependent_accesses(struct pet_scop
*scop
)
3432 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3433 int r
= pet_tree_foreach_access_expr(scop
->stmts
[i
]->body
,
3434 &is_data_dependent
, &found
);
3435 if (r
< 0 && !found
)
3444 /* Does "scop" contain and data dependent conditions?
3446 int pet_scop_has_data_dependent_conditions(struct pet_scop
*scop
)
3453 for (i
= 0; i
< scop
->n_stmt
; ++i
)
3454 if (scop
->stmts
[i
]->n_arg
> 0)
3460 /* Keep track of the "input" file inside the (extended) "scop".
3462 struct pet_scop
*pet_scop_set_input_file(struct pet_scop
*scop
, FILE *input
)
3464 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
3474 /* Print the original code corresponding to "scop" to printer "p".
3476 * pet_scop_print_original can only be called from
3477 * a pet_transform_C_source callback. This means that the input
3478 * file is stored in the extended scop and that the printer prints
3481 __isl_give isl_printer
*pet_scop_print_original(struct pet_scop
*scop
,
3482 __isl_take isl_printer
*p
)
3484 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
3486 unsigned start
, end
;
3489 return isl_printer_free(p
);
3492 isl_die(isl_printer_get_ctx(p
), isl_error_invalid
,
3493 "no input file stored in scop",
3494 return isl_printer_free(p
));
3496 output
= isl_printer_get_file(p
);
3498 return isl_printer_free(p
);
3500 start
= pet_loc_get_start(scop
->loc
);
3501 end
= pet_loc_get_end(scop
->loc
);
3502 if (copy(ext
->input
, output
, start
, end
) < 0)
3503 return isl_printer_free(p
);