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>
47 #include "value_bounds.h"
49 /* pet_scop with extra information that is used during parsing and printing.
51 * In particular, we keep track of conditions under which we want
52 * to skip the rest of the current loop iteration (skip[pet_skip_now])
53 * and of conditions under which we want to skip subsequent
54 * loop iterations (skip[pet_skip_later]).
56 * The conditions are represented as index expressions defined
57 * over the outer loop iterators. The index expression is either
58 * a boolean affine expression or an access to a variable, which
59 * is assumed to attain values zero and one. The condition holds
60 * if the variable has value one or if the affine expression
61 * has value one (typically for only part of the domain).
63 * A missing condition (skip[type] == NULL) means that we don't want
66 * Additionally, we keep track of the original input file
67 * inside pet_transform_C_source.
72 isl_multi_pw_aff
*skip
[2];
76 /* Construct a pet_stmt with given domain and statement number from a pet_tree.
77 * The input domain is anonymous and is the same as the domains
78 * of the access expressions inside "tree".
79 * These domains are modified to include the name of the statement.
80 * This name is given by tree->label if it is non-NULL.
81 * Otherwise, the name is constructed as S_<id>.
83 struct pet_stmt
*pet_stmt_from_pet_tree(__isl_take isl_set
*domain
,
84 int id
, __isl_take pet_tree
*tree
)
86 struct pet_stmt
*stmt
;
92 isl_multi_pw_aff
*add_name
;
98 ctx
= pet_tree_get_ctx(tree
);
99 stmt
= isl_calloc_type(ctx
, struct pet_stmt
);
104 label
= isl_id_copy(tree
->label
);
106 snprintf(name
, sizeof(name
), "S_%d", id
);
107 label
= isl_id_alloc(ctx
, name
, NULL
);
109 domain
= isl_set_set_tuple_id(domain
, label
);
110 space
= isl_set_get_space(domain
);
111 space
= pet_nested_remove_from_space(space
);
112 sched
= isl_map_universe(isl_space_from_domain(isl_space_copy(space
)));
113 ma
= pet_prefix_projection(space
, isl_space_dim(space
, isl_dim_set
));
115 add_name
= isl_multi_pw_aff_from_multi_aff(ma
);
116 tree
= pet_tree_update_domain(tree
, add_name
);
118 stmt
->loc
= pet_tree_get_loc(tree
);
119 stmt
->domain
= domain
;
120 stmt
->schedule
= sched
;
123 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
124 return pet_stmt_free(stmt
);
128 isl_set_free(domain
);
133 void *pet_stmt_free(struct pet_stmt
*stmt
)
140 pet_loc_free(stmt
->loc
);
141 isl_set_free(stmt
->domain
);
142 isl_map_free(stmt
->schedule
);
143 pet_tree_free(stmt
->body
);
145 for (i
= 0; i
< stmt
->n_arg
; ++i
)
146 pet_expr_free(stmt
->args
[i
]);
153 /* Return the iteration space of "stmt".
155 * If the statement has arguments, then stmt->domain is a wrapped map
156 * mapping the iteration domain to the values of the arguments
157 * for which this statement is executed.
158 * In this case, we need to extract the domain space of this wrapped map.
160 __isl_give isl_space
*pet_stmt_get_space(struct pet_stmt
*stmt
)
167 space
= isl_set_get_space(stmt
->domain
);
168 if (isl_space_is_wrapping(space
))
169 space
= isl_space_domain(isl_space_unwrap(space
));
174 static void stmt_dump(struct pet_stmt
*stmt
, int indent
)
181 fprintf(stderr
, "%*s%d\n", indent
, "", pet_loc_get_line(stmt
->loc
));
182 fprintf(stderr
, "%*s", indent
, "");
183 isl_set_dump(stmt
->domain
);
184 fprintf(stderr
, "%*s", indent
, "");
185 isl_map_dump(stmt
->schedule
);
186 pet_tree_dump_with_indent(stmt
->body
, indent
);
187 for (i
= 0; i
< stmt
->n_arg
; ++i
)
188 pet_expr_dump_with_indent(stmt
->args
[i
], indent
+ 2);
191 void pet_stmt_dump(struct pet_stmt
*stmt
)
196 /* Allocate a new pet_type with the given "name" and "definition".
198 struct pet_type
*pet_type_alloc(isl_ctx
*ctx
, const char *name
,
199 const char *definition
)
201 struct pet_type
*type
;
203 type
= isl_alloc_type(ctx
, struct pet_type
);
207 type
->name
= strdup(name
);
208 type
->definition
= strdup(definition
);
210 if (!type
->name
|| !type
->definition
)
211 return pet_type_free(type
);
216 /* Free "type" and return NULL.
218 struct pet_type
*pet_type_free(struct pet_type
*type
)
224 free(type
->definition
);
230 struct pet_array
*pet_array_free(struct pet_array
*array
)
235 isl_set_free(array
->context
);
236 isl_set_free(array
->extent
);
237 isl_set_free(array
->value_bounds
);
238 free(array
->element_type
);
244 void pet_array_dump(struct pet_array
*array
)
249 isl_set_dump(array
->context
);
250 isl_set_dump(array
->extent
);
251 isl_set_dump(array
->value_bounds
);
252 fprintf(stderr
, "%s%s%s\n", array
->element_type
,
253 array
->element_is_record
? " element-is-record" : "",
254 array
->live_out
? " live-out" : "");
257 /* Alloc a pet_scop structure, with extra room for information that
258 * is only used during parsing.
260 struct pet_scop
*pet_scop_alloc(isl_ctx
*ctx
)
262 return &isl_calloc_type(ctx
, struct pet_scop_ext
)->scop
;
265 /* Construct a pet_scop in the given space and with room for n statements.
267 * The context is initialized as a universe set in "space".
269 * Since no information on the location is known at this point,
270 * scop->loc is initialized with pet_loc_dummy.
272 static struct pet_scop
*scop_alloc(__isl_take isl_space
*space
, int n
)
275 struct pet_scop
*scop
;
280 ctx
= isl_space_get_ctx(space
);
281 scop
= pet_scop_alloc(ctx
);
285 scop
->context
= isl_set_universe(isl_space_copy(space
));
286 scop
->context_value
= isl_set_universe(isl_space_params(space
));
287 scop
->stmts
= isl_calloc_array(ctx
, struct pet_stmt
*, n
);
288 if (!scop
->context
|| !scop
->stmts
)
289 return pet_scop_free(scop
);
291 scop
->loc
= &pet_loc_dummy
;
297 /* Construct a pet_scop in the given space containing 0 statements.
299 struct pet_scop
*pet_scop_empty(__isl_take isl_space
*space
)
301 return scop_alloc(space
, 0);
304 /* Return the constraints on the iteration domain in the access relation
306 * If the corresponding access expression has arguments then the domain
307 * of "access" is a wrapped relation with the iteration domain in the domain
308 * and the arguments in the range.
310 static __isl_give isl_set
*access_domain(__isl_take isl_map
*access
)
314 domain
= isl_map_domain(access
);
315 if (isl_set_is_wrapping(domain
))
316 domain
= isl_map_domain(isl_set_unwrap(domain
));
321 /* Update "context" with the constraints imposed on the outer iteration
322 * domain by "access".
323 * "context" lives in an anonymous space, while the domain of "access"
324 * refers to a particular statement. This reference therefore needs to be
327 static __isl_give isl_set
*access_extract_context(__isl_keep isl_map
*access
,
328 __isl_take isl_set
*context
)
332 domain
= access_domain(isl_map_copy(access
));
333 domain
= isl_set_reset_tuple_id(domain
);
334 context
= isl_set_intersect(context
, domain
);
338 /* Update "context" with the constraints imposed on the outer iteration
341 * "context" lives in an anonymous space, while the domains of
342 * the access relations in "expr" refer to a particular statement.
343 * This reference therefore needs to be stripped off.
345 * If "expr" represents a conditional operator, then a parameter or outer
346 * iterator value needs to be valid for the condition and
347 * for at least one of the remaining two arguments.
348 * If the condition is an affine expression, then we can be a bit more specific.
349 * The value then has to be valid for the second argument for
350 * non-zero accesses and valid for the third argument for zero accesses.
352 * If "expr" represents a kill statement, then its argument is the entire
353 * extent of the array being killed. Do not update "context" based
354 * on this argument as that would impose constraints that ensure that
355 * the array is non-empty.
357 static __isl_give isl_set
*expr_extract_context(__isl_keep pet_expr
*expr
,
358 __isl_take isl_set
*context
)
362 if (expr
->type
== pet_expr_op
&& expr
->op
== pet_op_kill
)
365 if (expr
->type
== pet_expr_op
&& expr
->op
== pet_op_cond
) {
367 isl_set
*context1
, *context2
;
369 is_aff
= pet_expr_is_affine(expr
->args
[0]);
373 context
= expr_extract_context(expr
->args
[0], context
);
374 context1
= expr_extract_context(expr
->args
[1],
375 isl_set_copy(context
));
376 context2
= expr_extract_context(expr
->args
[2], context
);
382 access
= isl_map_copy(expr
->args
[0]->acc
.access
);
383 access
= isl_map_fix_si(access
, isl_dim_out
, 0, 0);
384 zero_set
= access_domain(access
);
385 zero_set
= isl_set_reset_tuple_id(zero_set
);
386 context1
= isl_set_subtract(context1
,
387 isl_set_copy(zero_set
));
388 context2
= isl_set_intersect(context2
, zero_set
);
391 context
= isl_set_union(context1
, context2
);
392 context
= isl_set_coalesce(context
);
397 for (i
= 0; i
< expr
->n_arg
; ++i
)
398 context
= expr_extract_context(expr
->args
[i
], context
);
400 if (expr
->type
== pet_expr_access
)
401 context
= access_extract_context(expr
->acc
.access
, context
);
405 isl_set_free(context
);
409 /* Is "stmt" an assume statement with an affine assumption?
411 int pet_stmt_is_affine_assume(struct pet_stmt
*stmt
)
415 return pet_tree_is_affine_assume(stmt
->body
);
418 /* Given an assume statement "stmt" with an access argument,
419 * return the index expression of the argument.
421 __isl_give isl_multi_pw_aff
*pet_stmt_assume_get_index(struct pet_stmt
*stmt
)
425 return pet_tree_assume_get_index(stmt
->body
);
428 /* Update "context" with the constraints imposed on the outer iteration
431 * If the statement is an assume statement with an affine expression,
432 * then intersect "context" with that expression.
433 * Otherwise, if the statement body is an expression tree,
434 * then intersect "context" with the context of this expression.
435 * Note that we cannot safely extract a context from subtrees
436 * of the statement body since we cannot tell when those subtrees
437 * are executed, if at all.
439 static __isl_give isl_set
*stmt_extract_context(struct pet_stmt
*stmt
,
440 __isl_take isl_set
*context
)
445 if (pet_stmt_is_affine_assume(stmt
)) {
446 isl_multi_pw_aff
*index
;
450 index
= pet_stmt_assume_get_index(stmt
);
451 pa
= isl_multi_pw_aff_get_pw_aff(index
, 0);
452 isl_multi_pw_aff_free(index
);
453 cond
= isl_pw_aff_non_zero_set(pa
);
454 cond
= isl_set_reset_tuple_id(cond
);
455 return isl_set_intersect(context
, cond
);
458 for (i
= 0; i
< stmt
->n_arg
; ++i
)
459 context
= expr_extract_context(stmt
->args
[i
], context
);
461 if (pet_tree_get_type(stmt
->body
) != pet_tree_expr
)
464 body
= pet_tree_expr_get_expr(stmt
->body
);
465 context
= expr_extract_context(body
, context
);
471 /* Construct a pet_scop in the given space that contains the given pet_stmt.
473 struct pet_scop
*pet_scop_from_pet_stmt(__isl_take isl_space
*space
,
474 struct pet_stmt
*stmt
)
476 struct pet_scop
*scop
;
479 space
= isl_space_free(space
);
481 scop
= scop_alloc(space
, 1);
485 scop
->context
= stmt_extract_context(stmt
, scop
->context
);
489 scop
->stmts
[0] = stmt
;
490 scop
->loc
= pet_loc_copy(stmt
->loc
);
493 return pet_scop_free(scop
);
502 /* Does "mpa" represent an access to an element of an unnamed space, i.e.,
503 * does it represent an affine expression?
505 static int multi_pw_aff_is_affine(__isl_keep isl_multi_pw_aff
*mpa
)
509 has_id
= isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
);
516 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
518 static __isl_give isl_pw_aff
*indicator_function(__isl_take isl_set
*set
,
519 __isl_take isl_set
*dom
)
522 pa
= isl_set_indicator_function(set
);
523 pa
= isl_pw_aff_intersect_domain(pa
, dom
);
527 /* Return "lhs || rhs", defined on the shared definition domain.
529 static __isl_give isl_pw_aff
*pw_aff_or(__isl_take isl_pw_aff
*lhs
,
530 __isl_take isl_pw_aff
*rhs
)
535 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs
)),
536 isl_pw_aff_domain(isl_pw_aff_copy(rhs
)));
537 cond
= isl_set_union(isl_pw_aff_non_zero_set(lhs
),
538 isl_pw_aff_non_zero_set(rhs
));
539 cond
= isl_set_coalesce(cond
);
540 return indicator_function(cond
, dom
);
543 /* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type].
544 * ext may be equal to either ext1 or ext2.
546 * The two skips that need to be combined are assumed to be affine expressions.
548 * We need to skip in ext if we need to skip in either ext1 or ext2.
549 * We don't need to skip in ext if we don't need to skip in both ext1 and ext2.
551 static struct pet_scop_ext
*combine_skips(struct pet_scop_ext
*ext
,
552 struct pet_scop_ext
*ext1
, struct pet_scop_ext
*ext2
,
555 isl_pw_aff
*skip
, *skip1
, *skip2
;
559 if (!ext1
->skip
[type
] && !ext2
->skip
[type
])
561 if (!ext1
->skip
[type
]) {
564 ext
->skip
[type
] = ext2
->skip
[type
];
565 ext2
->skip
[type
] = NULL
;
568 if (!ext2
->skip
[type
]) {
571 ext
->skip
[type
] = ext1
->skip
[type
];
572 ext1
->skip
[type
] = NULL
;
576 if (!multi_pw_aff_is_affine(ext1
->skip
[type
]) ||
577 !multi_pw_aff_is_affine(ext2
->skip
[type
]))
578 isl_die(isl_multi_pw_aff_get_ctx(ext1
->skip
[type
]),
579 isl_error_internal
, "can only combine affine skips",
582 skip1
= isl_multi_pw_aff_get_pw_aff(ext1
->skip
[type
], 0);
583 skip2
= isl_multi_pw_aff_get_pw_aff(ext2
->skip
[type
], 0);
584 skip
= pw_aff_or(skip1
, skip2
);
585 isl_multi_pw_aff_free(ext1
->skip
[type
]);
586 ext1
->skip
[type
] = NULL
;
587 isl_multi_pw_aff_free(ext2
->skip
[type
]);
588 ext2
->skip
[type
] = NULL
;
589 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
590 if (!ext
->skip
[type
])
595 pet_scop_free(&ext
->scop
);
599 /* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type],
600 * where type takes on the values pet_skip_now and pet_skip_later.
601 * scop may be equal to either scop1 or scop2.
603 static struct pet_scop
*scop_combine_skips(struct pet_scop
*scop
,
604 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
606 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
607 struct pet_scop_ext
*ext1
= (struct pet_scop_ext
*) scop1
;
608 struct pet_scop_ext
*ext2
= (struct pet_scop_ext
*) scop2
;
610 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_now
);
611 ext
= combine_skips(ext
, ext1
, ext2
, pet_skip_later
);
615 /* Update start and end of scop->loc to include the region from "start"
616 * to "end". In particular, if scop->loc == &pet_loc_dummy, then "scop"
617 * does not have any offset information yet and we simply take the information
618 * from "start" and "end". Otherwise, we update loc using "start" and "end".
620 struct pet_scop
*pet_scop_update_start_end(struct pet_scop
*scop
,
621 unsigned start
, unsigned end
)
626 if (scop
->loc
== &pet_loc_dummy
)
627 scop
->loc
= pet_loc_alloc(isl_set_get_ctx(scop
->context
),
628 start
, end
, -1, strdup(""));
630 scop
->loc
= pet_loc_update_start_end(scop
->loc
, start
, end
);
633 return pet_scop_free(scop
);
638 /* Update start and end of scop->loc to include the region identified
641 struct pet_scop
*pet_scop_update_start_end_from_loc(struct pet_scop
*scop
,
642 __isl_keep pet_loc
*loc
)
644 return pet_scop_update_start_end(scop
, pet_loc_get_start(loc
),
645 pet_loc_get_end(loc
));
648 /* Replace the location of "scop" by "loc".
650 struct pet_scop
*pet_scop_set_loc(struct pet_scop
*scop
,
651 __isl_take pet_loc
*loc
)
656 pet_loc_free(scop
->loc
);
666 /* Does "implication" appear in the list of implications of "scop"?
668 static int is_known_implication(struct pet_scop
*scop
,
669 struct pet_implication
*implication
)
673 for (i
= 0; i
< scop
->n_implication
; ++i
) {
674 struct pet_implication
*pi
= scop
->implications
[i
];
677 if (pi
->satisfied
!= implication
->satisfied
)
679 equal
= isl_map_is_equal(pi
->extension
, implication
->extension
);
689 /* Store the concatenation of the implications of "scop1" and "scop2"
690 * in "scop", removing duplicates (i.e., implications in "scop2" that
691 * already appear in "scop1").
693 static struct pet_scop
*scop_collect_implications(isl_ctx
*ctx
,
694 struct pet_scop
*scop
, struct pet_scop
*scop1
, struct pet_scop
*scop2
)
701 if (scop2
->n_implication
== 0) {
702 scop
->n_implication
= scop1
->n_implication
;
703 scop
->implications
= scop1
->implications
;
704 scop1
->n_implication
= 0;
705 scop1
->implications
= NULL
;
709 if (scop1
->n_implication
== 0) {
710 scop
->n_implication
= scop2
->n_implication
;
711 scop
->implications
= scop2
->implications
;
712 scop2
->n_implication
= 0;
713 scop2
->implications
= NULL
;
717 scop
->implications
= isl_calloc_array(ctx
, struct pet_implication
*,
718 scop1
->n_implication
+ scop2
->n_implication
);
719 if (!scop
->implications
)
720 return pet_scop_free(scop
);
722 for (i
= 0; i
< scop1
->n_implication
; ++i
) {
723 scop
->implications
[i
] = scop1
->implications
[i
];
724 scop1
->implications
[i
] = NULL
;
727 scop
->n_implication
= scop1
->n_implication
;
728 j
= scop1
->n_implication
;
729 for (i
= 0; i
< scop2
->n_implication
; ++i
) {
732 known
= is_known_implication(scop
, scop2
->implications
[i
]);
734 return pet_scop_free(scop
);
737 scop
->implications
[j
++] = scop2
->implications
[i
];
738 scop2
->implications
[i
] = NULL
;
740 scop
->n_implication
= j
;
745 /* Combine the offset information of "scop1" and "scop2" into "scop".
747 static struct pet_scop
*scop_combine_start_end(struct pet_scop
*scop
,
748 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
750 if (scop1
->loc
!= &pet_loc_dummy
)
751 scop
= pet_scop_update_start_end_from_loc(scop
, scop1
->loc
);
752 if (scop2
->loc
!= &pet_loc_dummy
)
753 scop
= pet_scop_update_start_end_from_loc(scop
, scop2
->loc
);
757 /* Create and return an independence that filters out the dependences
758 * in "filter" with local variables "local".
760 static struct pet_independence
*new_independence(
761 __isl_take isl_union_map
*filter
, __isl_take isl_union_set
*local
)
764 struct pet_independence
*independence
;
766 if (!filter
|| !local
)
768 ctx
= isl_union_map_get_ctx(filter
);
769 independence
= isl_alloc_type(ctx
, struct pet_independence
);
773 independence
->filter
= filter
;
774 independence
->local
= local
;
778 isl_union_map_free(filter
);
779 isl_union_set_free(local
);
783 /* Add an independence that filters out the dependences
784 * in "filter" with local variables "local" to "scop".
786 struct pet_scop
*pet_scop_add_independence(struct pet_scop
*scop
,
787 __isl_take isl_union_map
*filter
, __isl_take isl_union_set
*local
)
790 struct pet_independence
*independence
;
791 struct pet_independence
**independences
;
793 ctx
= isl_union_map_get_ctx(filter
);
794 independence
= new_independence(filter
, local
);
795 if (!scop
|| !independence
)
798 independences
= isl_realloc_array(ctx
, scop
->independences
,
799 struct pet_independence
*,
800 scop
->n_independence
+ 1);
803 scop
->independences
= independences
;
804 scop
->independences
[scop
->n_independence
] = independence
;
805 scop
->n_independence
++;
809 pet_independence_free(independence
);
814 /* Store the concatenation of the independences of "scop1" and "scop2"
817 static struct pet_scop
*scop_collect_independences(isl_ctx
*ctx
,
818 struct pet_scop
*scop
, struct pet_scop
*scop1
, struct pet_scop
*scop2
)
825 if (scop2
->n_independence
== 0) {
826 scop
->n_independence
= scop1
->n_independence
;
827 scop
->independences
= scop1
->independences
;
828 scop1
->n_independence
= 0;
829 scop1
->independences
= NULL
;
833 if (scop1
->n_independence
== 0) {
834 scop
->n_independence
= scop2
->n_independence
;
835 scop
->independences
= scop2
->independences
;
836 scop2
->n_independence
= 0;
837 scop2
->independences
= NULL
;
841 scop
->independences
= isl_calloc_array(ctx
, struct pet_independence
*,
842 scop1
->n_independence
+ scop2
->n_independence
);
843 if (!scop
->independences
)
844 return pet_scop_free(scop
);
846 for (i
= 0; i
< scop1
->n_independence
; ++i
) {
847 scop
->independences
[i
] = scop1
->independences
[i
];
848 scop1
->independences
[i
] = NULL
;
851 off
= scop1
->n_independence
;
852 for (i
= 0; i
< scop2
->n_independence
; ++i
) {
853 scop
->independences
[off
+ i
] = scop2
->independences
[i
];
854 scop2
->independences
[i
] = NULL
;
856 scop
->n_independence
= scop1
->n_independence
+ scop2
->n_independence
;
861 /* Construct a pet_scop that contains the offset information,
862 * arrays, statements and skip information in "scop1" and "scop2".
864 static struct pet_scop
*pet_scop_add(isl_ctx
*ctx
, struct pet_scop
*scop1
,
865 struct pet_scop
*scop2
)
869 struct pet_scop
*scop
= NULL
;
871 if (!scop1
|| !scop2
)
874 if (scop1
->n_stmt
== 0) {
875 scop2
= scop_combine_skips(scop2
, scop1
, scop2
);
876 pet_scop_free(scop1
);
880 if (scop2
->n_stmt
== 0) {
881 scop1
= scop_combine_skips(scop1
, scop1
, scop2
);
882 pet_scop_free(scop2
);
886 space
= isl_set_get_space(scop1
->context
);
887 scop
= scop_alloc(space
, scop1
->n_stmt
+ scop2
->n_stmt
);
891 scop
->arrays
= isl_calloc_array(ctx
, struct pet_array
*,
892 scop1
->n_array
+ scop2
->n_array
);
895 scop
->n_array
= scop1
->n_array
+ scop2
->n_array
;
897 for (i
= 0; i
< scop1
->n_stmt
; ++i
) {
898 scop
->stmts
[i
] = scop1
->stmts
[i
];
899 scop1
->stmts
[i
] = NULL
;
902 for (i
= 0; i
< scop2
->n_stmt
; ++i
) {
903 scop
->stmts
[scop1
->n_stmt
+ i
] = scop2
->stmts
[i
];
904 scop2
->stmts
[i
] = NULL
;
907 for (i
= 0; i
< scop1
->n_array
; ++i
) {
908 scop
->arrays
[i
] = scop1
->arrays
[i
];
909 scop1
->arrays
[i
] = NULL
;
912 for (i
= 0; i
< scop2
->n_array
; ++i
) {
913 scop
->arrays
[scop1
->n_array
+ i
] = scop2
->arrays
[i
];
914 scop2
->arrays
[i
] = NULL
;
917 scop
= scop_collect_implications(ctx
, scop
, scop1
, scop2
);
918 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop1
->context
));
919 scop
= pet_scop_restrict_context(scop
, isl_set_copy(scop2
->context
));
920 scop
= scop_combine_skips(scop
, scop1
, scop2
);
921 scop
= scop_combine_start_end(scop
, scop1
, scop2
);
922 scop
= scop_collect_independences(ctx
, scop
, scop1
, scop2
);
924 pet_scop_free(scop1
);
925 pet_scop_free(scop2
);
928 pet_scop_free(scop1
);
929 pet_scop_free(scop2
);
934 /* Apply the skip condition "skip" to "scop".
935 * That is, make sure "scop" is not executed when the condition holds.
937 * If "skip" is an affine expression, we add the conditions under
938 * which the expression is zero to the context and the skip conditions
940 * Otherwise, we add a filter on the variable attaining the value zero.
942 static struct pet_scop
*restrict_skip(struct pet_scop
*scop
,
943 __isl_take isl_multi_pw_aff
*skip
)
952 is_aff
= multi_pw_aff_is_affine(skip
);
957 return pet_scop_filter(scop
, skip
, 0);
959 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
960 isl_multi_pw_aff_free(skip
);
961 zero
= isl_pw_aff_zero_set(pa
);
962 scop
= pet_scop_restrict(scop
, zero
);
966 isl_multi_pw_aff_free(skip
);
967 return pet_scop_free(scop
);
970 /* Construct a pet_scop that contains the arrays, statements and
971 * skip information in "scop1" and "scop2", where the two scops
972 * are executed "in sequence". That is, breaks and continues
973 * in scop1 have an effect on scop2.
975 struct pet_scop
*pet_scop_add_seq(isl_ctx
*ctx
, struct pet_scop
*scop1
,
976 struct pet_scop
*scop2
)
978 if (scop1
&& pet_scop_has_skip(scop1
, pet_skip_now
))
979 scop2
= restrict_skip(scop2
,
980 pet_scop_get_skip(scop1
, pet_skip_now
));
981 return pet_scop_add(ctx
, scop1
, scop2
);
984 /* Construct a pet_scop that contains the arrays, statements and
985 * skip information in "scop1" and "scop2", where the two scops
986 * are executed "in parallel". That is, any break or continue
987 * in scop1 has no effect on scop2.
989 struct pet_scop
*pet_scop_add_par(isl_ctx
*ctx
, struct pet_scop
*scop1
,
990 struct pet_scop
*scop2
)
992 return pet_scop_add(ctx
, scop1
, scop2
);
995 void *pet_implication_free(struct pet_implication
*implication
)
1002 isl_map_free(implication
->extension
);
1008 void *pet_independence_free(struct pet_independence
*independence
)
1013 isl_union_map_free(independence
->filter
);
1014 isl_union_set_free(independence
->local
);
1020 struct pet_scop
*pet_scop_free(struct pet_scop
*scop
)
1023 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1027 pet_loc_free(scop
->loc
);
1028 isl_set_free(scop
->context
);
1029 isl_set_free(scop
->context_value
);
1031 for (i
= 0; i
< scop
->n_type
; ++i
)
1032 pet_type_free(scop
->types
[i
]);
1035 for (i
= 0; i
< scop
->n_array
; ++i
)
1036 pet_array_free(scop
->arrays
[i
]);
1039 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1040 pet_stmt_free(scop
->stmts
[i
]);
1042 if (scop
->implications
)
1043 for (i
= 0; i
< scop
->n_implication
; ++i
)
1044 pet_implication_free(scop
->implications
[i
]);
1045 free(scop
->implications
);
1046 if (scop
->independences
)
1047 for (i
= 0; i
< scop
->n_independence
; ++i
)
1048 pet_independence_free(scop
->independences
[i
]);
1049 free(scop
->independences
);
1050 isl_multi_pw_aff_free(ext
->skip
[pet_skip_now
]);
1051 isl_multi_pw_aff_free(ext
->skip
[pet_skip_later
]);
1056 void pet_type_dump(struct pet_type
*type
)
1061 fprintf(stderr
, "%s -> %s\n", type
->name
, type
->definition
);
1064 void pet_implication_dump(struct pet_implication
*implication
)
1069 fprintf(stderr
, "%d\n", implication
->satisfied
);
1070 isl_map_dump(implication
->extension
);
1073 void pet_scop_dump(struct pet_scop
*scop
)
1076 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1081 isl_set_dump(scop
->context
);
1082 isl_set_dump(scop
->context_value
);
1083 for (i
= 0; i
< scop
->n_type
; ++i
)
1084 pet_type_dump(scop
->types
[i
]);
1085 for (i
= 0; i
< scop
->n_array
; ++i
)
1086 pet_array_dump(scop
->arrays
[i
]);
1087 for (i
= 0; i
< scop
->n_stmt
; ++i
)
1088 pet_stmt_dump(scop
->stmts
[i
]);
1089 for (i
= 0; i
< scop
->n_implication
; ++i
)
1090 pet_implication_dump(scop
->implications
[i
]);
1093 fprintf(stderr
, "skip\n");
1094 isl_multi_pw_aff_dump(ext
->skip
[0]);
1095 isl_multi_pw_aff_dump(ext
->skip
[1]);
1099 /* Return 1 if the two pet_arrays are equivalent.
1101 * We don't compare element_size as this may be target dependent.
1103 int pet_array_is_equal(struct pet_array
*array1
, struct pet_array
*array2
)
1105 if (!array1
|| !array2
)
1108 if (!isl_set_is_equal(array1
->context
, array2
->context
))
1110 if (!isl_set_is_equal(array1
->extent
, array2
->extent
))
1112 if (!!array1
->value_bounds
!= !!array2
->value_bounds
)
1114 if (array1
->value_bounds
&&
1115 !isl_set_is_equal(array1
->value_bounds
, array2
->value_bounds
))
1117 if (strcmp(array1
->element_type
, array2
->element_type
))
1119 if (array1
->element_is_record
!= array2
->element_is_record
)
1121 if (array1
->live_out
!= array2
->live_out
)
1123 if (array1
->uniquely_defined
!= array2
->uniquely_defined
)
1125 if (array1
->declared
!= array2
->declared
)
1127 if (array1
->exposed
!= array2
->exposed
)
1133 /* Return 1 if the two pet_stmts are equivalent.
1135 int pet_stmt_is_equal(struct pet_stmt
*stmt1
, struct pet_stmt
*stmt2
)
1139 if (!stmt1
|| !stmt2
)
1142 if (pet_loc_get_line(stmt1
->loc
) != pet_loc_get_line(stmt2
->loc
))
1144 if (!isl_set_is_equal(stmt1
->domain
, stmt2
->domain
))
1146 if (!isl_map_is_equal(stmt1
->schedule
, stmt2
->schedule
))
1148 if (!pet_tree_is_equal(stmt1
->body
, stmt2
->body
))
1150 if (stmt1
->n_arg
!= stmt2
->n_arg
)
1152 for (i
= 0; i
< stmt1
->n_arg
; ++i
) {
1153 if (!pet_expr_is_equal(stmt1
->args
[i
], stmt2
->args
[i
]))
1160 /* Return 1 if the two pet_types are equivalent.
1162 * We only compare the names of the types since the exact representation
1163 * of the definition may depend on the version of clang being used.
1165 int pet_type_is_equal(struct pet_type
*type1
, struct pet_type
*type2
)
1167 if (!type1
|| !type2
)
1170 if (strcmp(type1
->name
, type2
->name
))
1176 /* Return 1 if the two pet_implications are equivalent.
1178 int pet_implication_is_equal(struct pet_implication
*implication1
,
1179 struct pet_implication
*implication2
)
1181 if (!implication1
|| !implication2
)
1184 if (implication1
->satisfied
!= implication2
->satisfied
)
1186 if (!isl_map_is_equal(implication1
->extension
, implication2
->extension
))
1192 /* Return 1 if the two pet_independences are equivalent.
1194 int pet_independence_is_equal(struct pet_independence
*independence1
,
1195 struct pet_independence
*independence2
)
1197 if (!independence1
|| !independence2
)
1200 if (!isl_union_map_is_equal(independence1
->filter
,
1201 independence2
->filter
))
1203 if (!isl_union_set_is_equal(independence1
->local
, independence2
->local
))
1209 /* Return 1 if the two pet_scops are equivalent.
1211 int pet_scop_is_equal(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
1215 if (!scop1
|| !scop2
)
1218 if (!isl_set_is_equal(scop1
->context
, scop2
->context
))
1220 if (!isl_set_is_equal(scop1
->context_value
, scop2
->context_value
))
1223 if (scop1
->n_type
!= scop2
->n_type
)
1225 for (i
= 0; i
< scop1
->n_type
; ++i
)
1226 if (!pet_type_is_equal(scop1
->types
[i
], scop2
->types
[i
]))
1229 if (scop1
->n_array
!= scop2
->n_array
)
1231 for (i
= 0; i
< scop1
->n_array
; ++i
)
1232 if (!pet_array_is_equal(scop1
->arrays
[i
], scop2
->arrays
[i
]))
1235 if (scop1
->n_stmt
!= scop2
->n_stmt
)
1237 for (i
= 0; i
< scop1
->n_stmt
; ++i
)
1238 if (!pet_stmt_is_equal(scop1
->stmts
[i
], scop2
->stmts
[i
]))
1241 if (scop1
->n_implication
!= scop2
->n_implication
)
1243 for (i
= 0; i
< scop1
->n_implication
; ++i
)
1244 if (!pet_implication_is_equal(scop1
->implications
[i
],
1245 scop2
->implications
[i
]))
1248 if (scop1
->n_independence
!= scop2
->n_independence
)
1250 for (i
= 0; i
< scop1
->n_independence
; ++i
)
1251 if (!pet_independence_is_equal(scop1
->independences
[i
],
1252 scop2
->independences
[i
]))
1258 /* Does the set "extent" reference a virtual array, i.e.,
1259 * one with user pointer equal to NULL?
1260 * A virtual array does not have any members.
1262 static int extent_is_virtual_array(__isl_keep isl_set
*extent
)
1267 if (!isl_set_has_tuple_id(extent
))
1269 if (isl_set_is_wrapping(extent
))
1271 id
= isl_set_get_tuple_id(extent
);
1272 is_virtual
= !isl_id_get_user(id
);
1278 /* Intersect the initial dimensions of "array" with "domain", provided
1279 * that "array" represents a virtual array.
1281 * If "array" is virtual, then We take the preimage of "domain"
1282 * over the projection of the extent of "array" onto its initial dimensions
1283 * and intersect this extent with the result.
1285 static struct pet_array
*virtual_array_intersect_domain_prefix(
1286 struct pet_array
*array
, __isl_take isl_set
*domain
)
1292 if (!array
|| !extent_is_virtual_array(array
->extent
)) {
1293 isl_set_free(domain
);
1297 space
= isl_set_get_space(array
->extent
);
1298 n
= isl_set_dim(domain
, isl_dim_set
);
1299 ma
= pet_prefix_projection(space
, n
);
1300 domain
= isl_set_preimage_multi_aff(domain
, ma
);
1302 array
->extent
= isl_set_intersect(array
->extent
, domain
);
1304 return pet_array_free(array
);
1309 /* Intersect the initial dimensions of the domain of "stmt"
1312 * We take the preimage of "domain" over the projection of the
1313 * domain of "stmt" onto its initial dimensions and intersect
1314 * the domain of "stmt" with the result.
1316 static struct pet_stmt
*stmt_intersect_domain_prefix(struct pet_stmt
*stmt
,
1317 __isl_take isl_set
*domain
)
1326 space
= isl_set_get_space(stmt
->domain
);
1327 n
= isl_set_dim(domain
, isl_dim_set
);
1328 ma
= pet_prefix_projection(space
, n
);
1329 domain
= isl_set_preimage_multi_aff(domain
, ma
);
1331 stmt
->domain
= isl_set_intersect(stmt
->domain
, domain
);
1333 return pet_stmt_free(stmt
);
1337 isl_set_free(domain
);
1338 return pet_stmt_free(stmt
);
1341 /* Intersect the initial dimensions of the domain of "implication"
1344 * We take the preimage of "domain" over the projection of the
1345 * domain of "implication" onto its initial dimensions and intersect
1346 * the domain of "implication" with the result.
1348 static struct pet_implication
*implication_intersect_domain_prefix(
1349 struct pet_implication
*implication
, __isl_take isl_set
*domain
)
1358 space
= isl_map_get_space(implication
->extension
);
1359 n
= isl_set_dim(domain
, isl_dim_set
);
1360 ma
= pet_prefix_projection(isl_space_domain(space
), n
);
1361 domain
= isl_set_preimage_multi_aff(domain
, ma
);
1363 implication
->extension
=
1364 isl_map_intersect_domain(implication
->extension
, domain
);
1365 if (!implication
->extension
)
1366 return pet_implication_free(implication
);
1370 isl_set_free(domain
);
1371 return pet_implication_free(implication
);
1374 /* Intersect the initial dimensions of the domains in "scop" with "domain".
1376 * The extents of the virtual arrays match the iteration domains,
1377 * so if the iteration domain changes, we need to change those extents too.
1379 struct pet_scop
*pet_scop_intersect_domain_prefix(struct pet_scop
*scop
,
1380 __isl_take isl_set
*domain
)
1387 for (i
= 0; i
< scop
->n_array
; ++i
) {
1388 scop
->arrays
[i
] = virtual_array_intersect_domain_prefix(
1389 scop
->arrays
[i
], isl_set_copy(domain
));
1390 if (!scop
->arrays
[i
])
1394 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1395 scop
->stmts
[i
] = stmt_intersect_domain_prefix(scop
->stmts
[i
],
1396 isl_set_copy(domain
));
1397 if (!scop
->stmts
[i
])
1401 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1402 scop
->implications
[i
] =
1403 implication_intersect_domain_prefix(scop
->implications
[i
],
1404 isl_set_copy(domain
));
1405 if (!scop
->implications
[i
])
1406 return pet_scop_free(scop
);
1409 isl_set_free(domain
);
1412 isl_set_free(domain
);
1413 return pet_scop_free(scop
);
1416 /* Prefix the schedule of "stmt" with an extra dimension with constant
1419 struct pet_stmt
*pet_stmt_prefix(struct pet_stmt
*stmt
, int pos
)
1424 stmt
->schedule
= isl_map_insert_dims(stmt
->schedule
, isl_dim_out
, 0, 1);
1425 stmt
->schedule
= isl_map_fix_si(stmt
->schedule
, isl_dim_out
, 0, pos
);
1426 if (!stmt
->schedule
)
1427 return pet_stmt_free(stmt
);
1432 /* Prefix the schedules of all statements in "scop" with an extra
1433 * dimension with constant value "pos".
1435 struct pet_scop
*pet_scop_prefix(struct pet_scop
*scop
, int pos
)
1442 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1443 scop
->stmts
[i
] = pet_stmt_prefix(scop
->stmts
[i
], pos
);
1444 if (!scop
->stmts
[i
])
1445 return pet_scop_free(scop
);
1451 /* Prefix the schedule of "stmt" with "sched".
1453 * The domain of "sched" refers the current outer loop iterators and
1454 * needs to be mapped to the iteration domain of "stmt" first
1455 * before being prepended to the schedule of "stmt".
1457 static struct pet_stmt
*pet_stmt_embed(struct pet_stmt
*stmt
,
1458 __isl_take isl_map
*sched
)
1467 space
= pet_stmt_get_space(stmt
);
1468 n
= isl_map_dim(sched
, isl_dim_in
);
1469 ma
= pet_prefix_projection(space
, n
);
1470 sched
= isl_map_preimage_domain_multi_aff(sched
, ma
);
1471 stmt
->schedule
= isl_map_flat_range_product(sched
, stmt
->schedule
);
1472 if (!stmt
->schedule
)
1473 return pet_stmt_free(stmt
);
1477 isl_map_free(sched
);
1481 /* Update the context with respect to an embedding into a loop
1482 * with iteration domain "dom".
1483 * The input context lives in the same space as "dom".
1484 * The output context has the inner dimension removed.
1486 * An outer loop iterator value is invalid for the embedding if
1487 * any of the corresponding inner iterator values is invalid.
1488 * That is, an outer loop iterator value is valid only if all the corresponding
1489 * inner iterator values are valid.
1490 * We therefore compute the set of outer loop iterators l
1492 * forall i: dom(l,i) => valid(l,i)
1496 * forall i: not dom(l,i) or valid(l,i)
1500 * not exists i: dom(l,i) and not valid(l,i)
1504 * not exists i: (dom \ valid)(l,i)
1506 * If there are any unnamed parameters in "dom", then we consider
1507 * a parameter value to be valid if it is valid for any value of those
1508 * unnamed parameters. They are therefore projected out at the end.
1510 static __isl_give isl_set
*context_embed(__isl_take isl_set
*context
,
1511 __isl_keep isl_set
*dom
)
1515 pos
= isl_set_dim(context
, isl_dim_set
) - 1;
1516 context
= isl_set_subtract(isl_set_copy(dom
), context
);
1517 context
= isl_set_project_out(context
, isl_dim_set
, pos
, 1);
1518 context
= isl_set_complement(context
);
1519 context
= pet_nested_remove_from_set(context
);
1524 /* Update the implication with respect to an embedding into a loop
1525 * with iteration domain "dom".
1527 * Since embed_access extends virtual arrays along with the domain
1528 * of the access, we need to do the same with domain and range
1529 * of the implication. Since the original implication is only valid
1530 * within a given iteration of the loop, the extended implication
1531 * maps the extra array dimension corresponding to the extra loop
1534 static struct pet_implication
*pet_implication_embed(
1535 struct pet_implication
*implication
, __isl_take isl_set
*dom
)
1543 map
= isl_set_identity(dom
);
1544 id
= isl_map_get_tuple_id(implication
->extension
, isl_dim_in
);
1545 map
= isl_map_flat_product(map
, implication
->extension
);
1546 map
= isl_map_set_tuple_id(map
, isl_dim_in
, isl_id_copy(id
));
1547 map
= isl_map_set_tuple_id(map
, isl_dim_out
, id
);
1548 implication
->extension
= map
;
1549 if (!implication
->extension
)
1550 return pet_implication_free(implication
);
1558 /* Adjust the context and statement schedules according to an embedding
1559 * in a loop with iteration domain "dom" and schedule "sched".
1561 * Any skip conditions within the loop have no effect outside of the loop.
1562 * The caller is responsible for making sure skip[pet_skip_later] has been
1563 * taken into account.
1565 struct pet_scop
*pet_scop_embed(struct pet_scop
*scop
, __isl_take isl_set
*dom
,
1566 __isl_take isl_aff
*sched
)
1571 sched_map
= isl_map_from_aff(sched
);
1576 pet_scop_reset_skip(scop
, pet_skip_now
);
1577 pet_scop_reset_skip(scop
, pet_skip_later
);
1579 scop
->context
= context_embed(scop
->context
, dom
);
1583 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1584 scop
->stmts
[i
] = pet_stmt_embed(scop
->stmts
[i
],
1585 isl_map_copy(sched_map
));
1586 if (!scop
->stmts
[i
])
1591 isl_map_free(sched_map
);
1595 isl_map_free(sched_map
);
1596 return pet_scop_free(scop
);
1599 /* Add extra conditions to scop->skip[type].
1601 * The new skip condition only holds if it held before
1602 * and the condition is true. It does not hold if it did not hold
1603 * before or the condition is false.
1605 * The skip condition is assumed to be an affine expression.
1607 static struct pet_scop
*pet_scop_restrict_skip(struct pet_scop
*scop
,
1608 enum pet_skip type
, __isl_keep isl_set
*cond
)
1610 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1616 if (!ext
->skip
[type
])
1619 if (!multi_pw_aff_is_affine(ext
->skip
[type
]))
1620 isl_die(isl_multi_pw_aff_get_ctx(ext
->skip
[type
]),
1621 isl_error_internal
, "can only restrict affine skips",
1622 return pet_scop_free(scop
));
1624 skip
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
1625 dom
= isl_pw_aff_domain(isl_pw_aff_copy(skip
));
1626 cond
= isl_set_copy(cond
);
1627 cond
= isl_set_intersect(cond
, isl_pw_aff_non_zero_set(skip
));
1628 skip
= indicator_function(cond
, dom
);
1629 isl_multi_pw_aff_free(ext
->skip
[type
]);
1630 ext
->skip
[type
] = isl_multi_pw_aff_from_pw_aff(skip
);
1631 if (!ext
->skip
[type
])
1632 return pet_scop_free(scop
);
1637 /* Adjust the context and the skip conditions to the fact that
1638 * the scop was created in a context where "cond" holds.
1640 * An outer loop iterator or parameter value is valid for the result
1641 * if it was valid for the original scop and satisfies "cond" or if it does
1642 * not satisfy "cond" as in this case the scop is not executed
1643 * and the original constraints on these values are irrelevant.
1645 struct pet_scop
*pet_scop_restrict(struct pet_scop
*scop
,
1646 __isl_take isl_set
*cond
)
1650 scop
= pet_scop_restrict_skip(scop
, pet_skip_now
, cond
);
1651 scop
= pet_scop_restrict_skip(scop
, pet_skip_later
, cond
);
1656 scop
->context
= isl_set_intersect(scop
->context
, isl_set_copy(cond
));
1657 scop
->context
= isl_set_union(scop
->context
,
1658 isl_set_complement(isl_set_copy(cond
)));
1659 scop
->context
= isl_set_coalesce(scop
->context
);
1660 scop
->context
= pet_nested_remove_from_set(scop
->context
);
1668 return pet_scop_free(scop
);
1671 /* Insert an argument expression corresponding to "test" in front
1672 * of the list of arguments described by *n_arg and *args.
1674 static int args_insert_access(unsigned *n_arg
, pet_expr
***args
,
1675 __isl_keep isl_multi_pw_aff
*test
)
1678 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
1684 *args
= isl_calloc_array(ctx
, pet_expr
*, 1);
1689 ext
= isl_calloc_array(ctx
, pet_expr
*, 1 + *n_arg
);
1692 for (i
= 0; i
< *n_arg
; ++i
)
1693 ext
[1 + i
] = (*args
)[i
];
1698 (*args
)[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
1705 /* Look through the applications in "scop" for any that can be
1706 * applied to the filter expressed by "map" and "satisified".
1707 * If there is any, then apply it to "map" and return the result.
1708 * Otherwise, return "map".
1709 * "id" is the identifier of the virtual array.
1711 * We only introduce at most one implication for any given virtual array,
1712 * so we can apply the implication and return as soon as we find one.
1714 static __isl_give isl_map
*apply_implications(struct pet_scop
*scop
,
1715 __isl_take isl_map
*map
, __isl_keep isl_id
*id
, int satisfied
)
1719 for (i
= 0; i
< scop
->n_implication
; ++i
) {
1720 struct pet_implication
*pi
= scop
->implications
[i
];
1723 if (pi
->satisfied
!= satisfied
)
1725 pi_id
= isl_map_get_tuple_id(pi
->extension
, isl_dim_in
);
1730 return isl_map_apply_range(map
, isl_map_copy(pi
->extension
));
1736 /* Is the filter expressed by "test" and "satisfied" implied
1737 * by filter "pos" on "domain", with filter "expr", taking into
1738 * account the implications of "scop"?
1740 * For filter on domain implying that expressed by "test" and "satisfied",
1741 * the filter needs to be an access to the same (virtual) array as "test" and
1742 * the filter value needs to be equal to "satisfied".
1743 * Moreover, the filter access relation, possibly extended by
1744 * the implications in "scop" needs to contain "test".
1746 static int implies_filter(struct pet_scop
*scop
,
1747 __isl_keep isl_map
*domain
, int pos
, __isl_keep pet_expr
*expr
,
1748 __isl_keep isl_map
*test
, int satisfied
)
1750 isl_id
*test_id
, *arg_id
;
1757 if (expr
->type
!= pet_expr_access
)
1759 test_id
= isl_map_get_tuple_id(test
, isl_dim_out
);
1760 arg_id
= pet_expr_access_get_id(expr
);
1761 isl_id_free(arg_id
);
1762 isl_id_free(test_id
);
1763 if (test_id
!= arg_id
)
1765 val
= isl_map_plain_get_val_if_fixed(domain
, isl_dim_out
, pos
);
1766 is_int
= isl_val_is_int(val
);
1768 s
= isl_val_get_num_si(val
);
1777 implied
= isl_map_copy(expr
->acc
.access
);
1778 implied
= apply_implications(scop
, implied
, test_id
, satisfied
);
1779 is_subset
= isl_map_is_subset(test
, implied
);
1780 isl_map_free(implied
);
1785 /* Is the filter expressed by "test" and "satisfied" implied
1786 * by any of the filters on the domain of "stmt", taking into
1787 * account the implications of "scop"?
1789 static int filter_implied(struct pet_scop
*scop
,
1790 struct pet_stmt
*stmt
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
1798 if (!scop
|| !stmt
|| !test
)
1800 if (scop
->n_implication
== 0)
1802 if (stmt
->n_arg
== 0)
1805 domain
= isl_set_unwrap(isl_set_copy(stmt
->domain
));
1806 test_map
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(test
));
1809 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
1810 implied
= implies_filter(scop
, domain
, i
, stmt
->args
[i
],
1811 test_map
, satisfied
);
1812 if (implied
< 0 || implied
)
1816 isl_map_free(test_map
);
1817 isl_map_free(domain
);
1821 /* Make the statement "stmt" depend on the value of "test"
1822 * being equal to "satisfied" by adjusting stmt->domain.
1824 * The domain of "test" corresponds to the (zero or more) outer dimensions
1825 * of the iteration domain.
1827 * We first extend "test" to apply to the entire iteration domain and
1828 * then check if the filter that we are about to add is implied
1829 * by any of the current filters, possibly taking into account
1830 * the implications in "scop". If so, we leave "stmt" untouched and return.
1832 * Otherwise, we insert an argument corresponding to a read to "test"
1833 * from the iteration domain of "stmt" in front of the list of arguments.
1834 * We also insert a corresponding output dimension in the wrapped
1835 * map contained in stmt->domain, with value set to "satisfied".
1837 static struct pet_stmt
*stmt_filter(struct pet_scop
*scop
,
1838 struct pet_stmt
*stmt
, __isl_take isl_multi_pw_aff
*test
, int satisfied
)
1844 isl_pw_multi_aff
*pma
;
1845 isl_multi_aff
*add_dom
;
1847 isl_local_space
*ls
;
1853 space
= pet_stmt_get_space(stmt
);
1854 n_test_dom
= isl_multi_pw_aff_dim(test
, isl_dim_in
);
1855 space
= isl_space_from_domain(space
);
1856 space
= isl_space_add_dims(space
, isl_dim_out
, n_test_dom
);
1857 add_dom
= isl_multi_aff_zero(isl_space_copy(space
));
1858 ls
= isl_local_space_from_space(isl_space_domain(space
));
1859 for (i
= 0; i
< n_test_dom
; ++i
) {
1861 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
1863 add_dom
= isl_multi_aff_set_aff(add_dom
, i
, aff
);
1865 isl_local_space_free(ls
);
1866 test
= isl_multi_pw_aff_pullback_multi_aff(test
, add_dom
);
1868 implied
= filter_implied(scop
, stmt
, test
, satisfied
);
1872 isl_multi_pw_aff_free(test
);
1876 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
1877 pma
= pet_filter_insert_pma(isl_set_get_space(stmt
->domain
),
1879 stmt
->domain
= isl_set_preimage_pw_multi_aff(stmt
->domain
, pma
);
1881 if (args_insert_access(&stmt
->n_arg
, &stmt
->args
, test
) < 0)
1884 isl_multi_pw_aff_free(test
);
1887 isl_multi_pw_aff_free(test
);
1888 return pet_stmt_free(stmt
);
1891 /* Does "scop" have a skip condition of the given "type"?
1893 int pet_scop_has_skip(struct pet_scop
*scop
, enum pet_skip type
)
1895 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1899 return ext
->skip
[type
] != NULL
;
1902 /* Does "scop" have a skip condition of the given "type" that
1903 * is an affine expression?
1905 int pet_scop_has_affine_skip(struct pet_scop
*scop
, enum pet_skip type
)
1907 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1911 if (!ext
->skip
[type
])
1913 return multi_pw_aff_is_affine(ext
->skip
[type
]);
1916 /* Does "scop" have a skip condition of the given "type" that
1917 * is not an affine expression?
1919 int pet_scop_has_var_skip(struct pet_scop
*scop
, enum pet_skip type
)
1921 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1926 if (!ext
->skip
[type
])
1928 aff
= multi_pw_aff_is_affine(ext
->skip
[type
]);
1934 /* Does "scop" have a skip condition of the given "type" that
1935 * is affine and holds on the entire domain?
1937 int pet_scop_has_universal_skip(struct pet_scop
*scop
, enum pet_skip type
)
1939 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1945 is_aff
= pet_scop_has_affine_skip(scop
, type
);
1946 if (is_aff
< 0 || !is_aff
)
1949 pa
= isl_multi_pw_aff_get_pw_aff(ext
->skip
[type
], 0);
1950 set
= isl_pw_aff_non_zero_set(pa
);
1951 is_univ
= isl_set_plain_is_universe(set
);
1957 /* Replace scop->skip[type] by "skip".
1959 struct pet_scop
*pet_scop_set_skip(struct pet_scop
*scop
,
1960 enum pet_skip type
, __isl_take isl_multi_pw_aff
*skip
)
1962 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1967 isl_multi_pw_aff_free(ext
->skip
[type
]);
1968 ext
->skip
[type
] = skip
;
1972 isl_multi_pw_aff_free(skip
);
1973 return pet_scop_free(scop
);
1976 /* Return a copy of scop->skip[type].
1978 __isl_give isl_multi_pw_aff
*pet_scop_get_skip(struct pet_scop
*scop
,
1981 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
1986 return isl_multi_pw_aff_copy(ext
->skip
[type
]);
1989 /* Assuming scop->skip[type] is an affine expression,
1990 * return the constraints on the outer loop domain for which the skip condition
1993 __isl_give isl_set
*pet_scop_get_affine_skip_domain(struct pet_scop
*scop
,
1996 isl_multi_pw_aff
*skip
;
1999 skip
= pet_scop_get_skip(scop
, type
);
2000 pa
= isl_multi_pw_aff_get_pw_aff(skip
, 0);
2001 isl_multi_pw_aff_free(skip
);
2002 return isl_pw_aff_non_zero_set(pa
);
2005 /* Return the identifier of the variable that is accessed by
2006 * the skip condition of the given type.
2008 * The skip condition is assumed not to be an affine condition.
2010 __isl_give isl_id
*pet_scop_get_skip_id(struct pet_scop
*scop
,
2013 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2018 return isl_multi_pw_aff_get_tuple_id(ext
->skip
[type
], isl_dim_out
);
2021 /* Return an access pet_expr corresponding to the skip condition
2022 * of the given type.
2024 __isl_give pet_expr
*pet_scop_get_skip_expr(struct pet_scop
*scop
,
2027 return pet_expr_from_index(pet_scop_get_skip(scop
, type
));
2030 /* Drop the the skip condition scop->skip[type].
2032 void pet_scop_reset_skip(struct pet_scop
*scop
, enum pet_skip type
)
2034 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
2039 isl_multi_pw_aff_free(ext
->skip
[type
]);
2040 ext
->skip
[type
] = NULL
;
2043 /* Make the skip condition (if any) depend on the value of "test" being
2044 * equal to "satisfied".
2046 * We only support the case where the original skip condition is universal,
2047 * i.e., where skipping is unconditional, and where satisfied == 1.
2048 * In this case, the skip condition is changed to skip only when
2049 * "test" is equal to one.
2051 static struct pet_scop
*pet_scop_filter_skip(struct pet_scop
*scop
,
2052 enum pet_skip type
, __isl_keep isl_multi_pw_aff
*test
, int satisfied
)
2058 if (!pet_scop_has_skip(scop
, type
))
2062 is_univ
= pet_scop_has_universal_skip(scop
, type
);
2064 return pet_scop_free(scop
);
2065 if (satisfied
&& is_univ
) {
2066 isl_multi_pw_aff
*skip
;
2067 skip
= isl_multi_pw_aff_copy(test
);
2068 scop
= pet_scop_set_skip(scop
, type
, skip
);
2072 isl_die(isl_multi_pw_aff_get_ctx(test
), isl_error_internal
,
2073 "skip expression cannot be filtered",
2074 return pet_scop_free(scop
));
2080 /* Make all statements in "scop" depend on the value of "test"
2081 * being equal to "satisfied" by adjusting their domains.
2083 struct pet_scop
*pet_scop_filter(struct pet_scop
*scop
,
2084 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
2088 scop
= pet_scop_filter_skip(scop
, pet_skip_now
, test
, satisfied
);
2089 scop
= pet_scop_filter_skip(scop
, pet_skip_later
, test
, satisfied
);
2094 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2095 scop
->stmts
[i
] = stmt_filter(scop
, scop
->stmts
[i
],
2096 isl_multi_pw_aff_copy(test
), satisfied
);
2097 if (!scop
->stmts
[i
])
2101 isl_multi_pw_aff_free(test
);
2104 isl_multi_pw_aff_free(test
);
2105 return pet_scop_free(scop
);
2108 /* Add the parameters of the access expression "expr" to "space".
2110 static int access_collect_params(__isl_keep pet_expr
*expr
, void *user
)
2113 isl_space
**space
= user
;
2115 *space
= isl_space_align_params(*space
,
2116 isl_map_get_space(expr
->acc
.access
));
2118 return *space
? 0 : -1;
2121 /* Add all parameters in "stmt" to "space" and return the result.
2123 static __isl_give isl_space
*stmt_collect_params(struct pet_stmt
*stmt
,
2124 __isl_take isl_space
*space
)
2129 return isl_space_free(space
);
2131 space
= isl_space_align_params(space
, isl_set_get_space(stmt
->domain
));
2132 space
= isl_space_align_params(space
,
2133 isl_map_get_space(stmt
->schedule
));
2134 for (i
= 0; i
< stmt
->n_arg
; ++i
)
2135 if (pet_expr_foreach_access_expr(stmt
->args
[i
],
2136 &access_collect_params
, &space
) < 0)
2137 space
= isl_space_free(space
);
2138 if (pet_tree_foreach_access_expr(stmt
->body
, &access_collect_params
,
2140 space
= isl_space_free(space
);
2145 /* Add all parameters in "array" to "space" and return the result.
2147 static __isl_give isl_space
*array_collect_params(struct pet_array
*array
,
2148 __isl_take isl_space
*space
)
2151 return isl_space_free(space
);
2153 space
= isl_space_align_params(space
,
2154 isl_set_get_space(array
->context
));
2155 space
= isl_space_align_params(space
, isl_set_get_space(array
->extent
));
2160 /* Add all parameters in "independence" to "space" and return the result.
2162 static __isl_give isl_space
*independence_collect_params(
2163 struct pet_independence
*independence
, __isl_take isl_space
*space
)
2166 return isl_space_free(space
);
2168 space
= isl_space_align_params(space
,
2169 isl_union_map_get_space(independence
->filter
));
2170 space
= isl_space_align_params(space
,
2171 isl_union_set_get_space(independence
->local
));
2176 /* Add all parameters in "scop" to "space" and return the result.
2178 static __isl_give isl_space
*scop_collect_params(struct pet_scop
*scop
,
2179 __isl_take isl_space
*space
)
2184 return isl_space_free(space
);
2186 for (i
= 0; i
< scop
->n_array
; ++i
)
2187 space
= array_collect_params(scop
->arrays
[i
], space
);
2189 for (i
= 0; i
< scop
->n_stmt
; ++i
)
2190 space
= stmt_collect_params(scop
->stmts
[i
], space
);
2192 for (i
= 0; i
< scop
->n_independence
; ++i
)
2193 space
= independence_collect_params(scop
->independences
[i
],
2199 /* Add all parameters in "space" to the domain, schedule and
2200 * all access relations in "stmt".
2202 static struct pet_stmt
*stmt_propagate_params(struct pet_stmt
*stmt
,
2203 __isl_take isl_space
*space
)
2210 stmt
->domain
= isl_set_align_params(stmt
->domain
,
2211 isl_space_copy(space
));
2212 stmt
->schedule
= isl_map_align_params(stmt
->schedule
,
2213 isl_space_copy(space
));
2215 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2216 stmt
->args
[i
] = pet_expr_align_params(stmt
->args
[i
],
2217 isl_space_copy(space
));
2221 stmt
->body
= pet_tree_align_params(stmt
->body
, isl_space_copy(space
));
2223 if (!stmt
->domain
|| !stmt
->schedule
|| !stmt
->body
)
2226 isl_space_free(space
);
2229 isl_space_free(space
);
2230 return pet_stmt_free(stmt
);
2233 /* Add all parameters in "space" to "array".
2235 static struct pet_array
*array_propagate_params(struct pet_array
*array
,
2236 __isl_take isl_space
*space
)
2241 array
->context
= isl_set_align_params(array
->context
,
2242 isl_space_copy(space
));
2243 array
->extent
= isl_set_align_params(array
->extent
,
2244 isl_space_copy(space
));
2245 if (array
->value_bounds
) {
2246 array
->value_bounds
= isl_set_align_params(array
->value_bounds
,
2247 isl_space_copy(space
));
2248 if (!array
->value_bounds
)
2252 if (!array
->context
|| !array
->extent
)
2255 isl_space_free(space
);
2258 isl_space_free(space
);
2259 return pet_array_free(array
);
2262 /* Add all parameters in "space" to "independence".
2264 static struct pet_independence
*independence_propagate_params(
2265 struct pet_independence
*independence
, __isl_take isl_space
*space
)
2270 independence
->filter
= isl_union_map_align_params(independence
->filter
,
2271 isl_space_copy(space
));
2272 independence
->local
= isl_union_set_align_params(independence
->local
,
2273 isl_space_copy(space
));
2274 if (!independence
->filter
|| !independence
->local
)
2277 isl_space_free(space
);
2278 return independence
;
2280 isl_space_free(space
);
2281 return pet_independence_free(independence
);
2284 /* Add all parameters in "space" to "scop".
2286 static struct pet_scop
*scop_propagate_params(struct pet_scop
*scop
,
2287 __isl_take isl_space
*space
)
2294 for (i
= 0; i
< scop
->n_array
; ++i
) {
2295 scop
->arrays
[i
] = array_propagate_params(scop
->arrays
[i
],
2296 isl_space_copy(space
));
2297 if (!scop
->arrays
[i
])
2301 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2302 scop
->stmts
[i
] = stmt_propagate_params(scop
->stmts
[i
],
2303 isl_space_copy(space
));
2304 if (!scop
->stmts
[i
])
2308 for (i
= 0; i
< scop
->n_independence
; ++i
) {
2309 scop
->independences
[i
] = independence_propagate_params(
2310 scop
->independences
[i
], isl_space_copy(space
));
2311 if (!scop
->independences
[i
])
2315 isl_space_free(space
);
2318 isl_space_free(space
);
2319 return pet_scop_free(scop
);
2322 /* Update all isl_sets and isl_maps in "scop" such that they all
2323 * have the same parameters.
2325 struct pet_scop
*pet_scop_align_params(struct pet_scop
*scop
)
2332 space
= isl_set_get_space(scop
->context
);
2333 space
= scop_collect_params(scop
, space
);
2335 scop
->context
= isl_set_align_params(scop
->context
,
2336 isl_space_copy(space
));
2337 scop
= scop_propagate_params(scop
, space
);
2339 if (scop
&& !scop
->context
)
2340 return pet_scop_free(scop
);
2345 /* Add the access relation of the access expression "expr" to "accesses" and
2346 * return the result.
2347 * The domain of the access relation is intersected with "domain".
2348 * If "tag" is set, then the access relation is tagged with
2349 * the corresponding reference identifier.
2351 static __isl_give isl_union_map
*expr_collect_access(__isl_keep pet_expr
*expr
,
2352 int tag
, __isl_take isl_union_map
*accesses
, __isl_keep isl_set
*domain
)
2356 access
= pet_expr_access_get_may_access(expr
);
2357 access
= isl_map_intersect_domain(access
, isl_set_copy(domain
));
2359 access
= pet_expr_tag_access(expr
, access
);
2360 return isl_union_map_add_map(accesses
, access
);
2363 /* Internal data structure for expr_collect_accesses.
2365 * "read" is set if we want to collect read accesses.
2366 * "write" is set if we want to collect write accesses.
2367 * "must" is set if we only want definite accesses.
2368 * "tag" is set if the access relations should be tagged with
2369 * the corresponding reference identifiers.
2370 * "domain" are constraints on the domain of the access relations.
2371 * "accesses" collects the results.
2373 struct pet_expr_collect_accesses_data
{
2380 isl_union_map
*accesses
;
2383 /* Add the access relation of the access expression "expr"
2384 * to data->accesses if the access expression is a read and data->read is set
2385 * and/or it is a write and data->write is set.
2386 * The domains of the access relations are intersected with data->domain.
2387 * If data->tag is set, then the access relations are tagged with
2388 * the corresponding reference identifiers.
2390 * If data->must is set, then we only add the accesses that are definitely
2391 * performed. Otherwise, we add all potential accesses.
2392 * In particular, if the access has any arguments, then if data->must is
2393 * set we currently skip the access completely. If data->must is not set,
2394 * we project out the values of the access arguments.
2396 static int expr_collect_accesses(__isl_keep pet_expr
*expr
, void *user
)
2398 struct pet_expr_collect_accesses_data
*data
= user
;
2406 if (pet_expr_is_affine(expr
))
2408 if (data
->must
&& expr
->n_arg
!= 0)
2411 if ((data
->read
&& expr
->acc
.read
) || (data
->write
&& expr
->acc
.write
))
2412 data
->accesses
= expr_collect_access(expr
, data
->tag
,
2413 data
->accesses
, data
->domain
);
2415 return data
->accesses
? 0 : -1;
2418 /* Collect and return all read access relations (if "read" is set)
2419 * and/or all write access relations (if "write" is set) in "stmt".
2420 * If "tag" is set, then the access relations are tagged with
2421 * the corresponding reference identifiers.
2422 * If "kill" is set, then "stmt" is a kill statement and we simply
2423 * add the argument of the kill operation.
2425 * If "must" is set, then we only add the accesses that are definitely
2426 * performed. Otherwise, we add all potential accesses.
2427 * In particular, if the statement has any arguments, then if "must" is
2428 * set we currently skip the statement completely. If "must" is not set,
2429 * we project out the values of the statement arguments.
2430 * If the statement body is not an expression tree, then we cannot
2431 * know for sure if/when the accesses inside the tree are performed.
2432 * We therefore ignore such statements when "must" is set.
2434 static __isl_give isl_union_map
*stmt_collect_accesses(struct pet_stmt
*stmt
,
2435 int read
, int write
, int kill
, int must
, int tag
,
2436 __isl_take isl_space
*dim
)
2438 struct pet_expr_collect_accesses_data data
= { read
, write
, must
, tag
};
2443 data
.accesses
= isl_union_map_empty(dim
);
2445 if (must
&& stmt
->n_arg
> 0)
2446 return data
.accesses
;
2447 if (must
&& pet_tree_get_type(stmt
->body
) != pet_tree_expr
)
2448 return data
.accesses
;
2450 data
.domain
= isl_set_copy(stmt
->domain
);
2451 if (isl_set_is_wrapping(data
.domain
))
2452 data
.domain
= isl_map_domain(isl_set_unwrap(data
.domain
));
2455 pet_expr
*body
, *arg
;
2457 body
= pet_tree_expr_get_expr(stmt
->body
);
2458 arg
= pet_expr_get_arg(body
, 0);
2459 data
.accesses
= expr_collect_access(arg
, tag
,
2460 data
.accesses
, data
.domain
);
2462 pet_expr_free(body
);
2463 } else if (pet_tree_foreach_access_expr(stmt
->body
,
2464 &expr_collect_accesses
, &data
) < 0)
2465 data
.accesses
= isl_union_map_free(data
.accesses
);
2467 isl_set_free(data
.domain
);
2469 return data
.accesses
;
2472 /* Is "stmt" an assignment statement?
2474 int pet_stmt_is_assign(struct pet_stmt
*stmt
)
2478 return pet_tree_is_assign(stmt
->body
);
2481 /* Is "stmt" a kill statement?
2483 int pet_stmt_is_kill(struct pet_stmt
*stmt
)
2487 return pet_tree_is_kill(stmt
->body
);
2490 /* Is "stmt" an assume statement?
2492 int pet_stmt_is_assume(struct pet_stmt
*stmt
)
2496 return pet_tree_is_assume(stmt
->body
);
2499 /* Compute a mapping from all arrays (of structs) in scop
2500 * to their innermost arrays.
2502 * In particular, for each array of a primitive type, the result
2503 * contains the identity mapping on that array.
2504 * For each array involving member accesses, the result
2505 * contains a mapping from the elements of any intermediate array of structs
2506 * to all corresponding elements of the innermost nested arrays.
2508 static __isl_give isl_union_map
*compute_to_inner(struct pet_scop
*scop
)
2511 isl_union_map
*to_inner
;
2513 to_inner
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2515 for (i
= 0; i
< scop
->n_array
; ++i
) {
2516 struct pet_array
*array
= scop
->arrays
[i
];
2518 isl_map
*map
, *gist
;
2520 if (array
->element_is_record
)
2523 set
= isl_set_copy(array
->extent
);
2524 map
= isl_set_identity(isl_set_copy(set
));
2526 gist
= isl_map_copy(map
);
2527 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
2528 to_inner
= isl_union_map_add_map(to_inner
, gist
);
2530 while (set
&& isl_set_is_wrapping(set
)) {
2534 id
= isl_set_get_tuple_id(set
);
2535 wrapped
= isl_set_unwrap(set
);
2536 wrapped
= isl_map_domain_map(wrapped
);
2537 wrapped
= isl_map_set_tuple_id(wrapped
, isl_dim_in
, id
);
2538 map
= isl_map_apply_domain(map
, wrapped
);
2539 set
= isl_map_domain(isl_map_copy(map
));
2540 gist
= isl_map_copy(map
);
2541 gist
= isl_map_gist_domain(gist
, isl_set_copy(set
));
2542 to_inner
= isl_union_map_add_map(to_inner
, gist
);
2552 /* Collect and return all read access relations (if "read" is set)
2553 * and/or all write access relations (if "write" is set) in "scop".
2554 * If "kill" is set, then we only add the arguments of kill operations.
2555 * If "must" is set, then we only add the accesses that are definitely
2556 * performed. Otherwise, we add all potential accesses.
2557 * If "tag" is set, then the access relations are tagged with
2558 * the corresponding reference identifiers.
2559 * For accesses to structures, the returned access relation accesses
2560 * all individual fields in the structures.
2562 static __isl_give isl_union_map
*scop_collect_accesses(struct pet_scop
*scop
,
2563 int read
, int write
, int kill
, int must
, int tag
)
2566 isl_union_map
*accesses
;
2567 isl_union_set
*arrays
;
2568 isl_union_map
*to_inner
;
2573 accesses
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2575 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2576 struct pet_stmt
*stmt
= scop
->stmts
[i
];
2577 isl_union_map
*accesses_i
;
2580 if (kill
&& !pet_stmt_is_kill(stmt
))
2583 space
= isl_set_get_space(scop
->context
);
2584 accesses_i
= stmt_collect_accesses(stmt
, read
, write
, kill
,
2586 accesses
= isl_union_map_union(accesses
, accesses_i
);
2589 arrays
= isl_union_set_empty(isl_union_map_get_space(accesses
));
2590 for (i
= 0; i
< scop
->n_array
; ++i
) {
2591 isl_set
*extent
= isl_set_copy(scop
->arrays
[i
]->extent
);
2592 arrays
= isl_union_set_add_set(arrays
, extent
);
2594 accesses
= isl_union_map_intersect_range(accesses
, arrays
);
2596 to_inner
= compute_to_inner(scop
);
2597 accesses
= isl_union_map_apply_range(accesses
, to_inner
);
2602 /* Collect all potential read access relations.
2604 __isl_give isl_union_map
*pet_scop_collect_may_reads(struct pet_scop
*scop
)
2606 return scop_collect_accesses(scop
, 1, 0, 0, 0, 0);
2609 /* Collect all potential write access relations.
2611 __isl_give isl_union_map
*pet_scop_collect_may_writes(struct pet_scop
*scop
)
2613 return scop_collect_accesses(scop
, 0, 1, 0, 0, 0);
2616 /* Collect all definite write access relations.
2618 __isl_give isl_union_map
*pet_scop_collect_must_writes(struct pet_scop
*scop
)
2620 return scop_collect_accesses(scop
, 0, 1, 0, 1, 0);
2623 /* Collect all definite kill access relations.
2625 __isl_give isl_union_map
*pet_scop_collect_must_kills(struct pet_scop
*scop
)
2627 return scop_collect_accesses(scop
, 0, 0, 1, 1, 0);
2630 /* Collect all tagged potential read access relations.
2632 __isl_give isl_union_map
*pet_scop_collect_tagged_may_reads(
2633 struct pet_scop
*scop
)
2635 return scop_collect_accesses(scop
, 1, 0, 0, 0, 1);
2638 /* Collect all tagged potential write access relations.
2640 __isl_give isl_union_map
*pet_scop_collect_tagged_may_writes(
2641 struct pet_scop
*scop
)
2643 return scop_collect_accesses(scop
, 0, 1, 0, 0, 1);
2646 /* Collect all tagged definite write access relations.
2648 __isl_give isl_union_map
*pet_scop_collect_tagged_must_writes(
2649 struct pet_scop
*scop
)
2651 return scop_collect_accesses(scop
, 0, 1, 0, 1, 1);
2654 /* Collect all tagged definite kill access relations.
2656 __isl_give isl_union_map
*pet_scop_collect_tagged_must_kills(
2657 struct pet_scop
*scop
)
2659 return scop_collect_accesses(scop
, 0, 0, 1, 1, 1);
2662 /* Collect and return the union of iteration domains in "scop".
2664 __isl_give isl_union_set
*pet_scop_collect_domains(struct pet_scop
*scop
)
2668 isl_union_set
*domain
;
2673 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
2675 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2676 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
2677 domain
= isl_union_set_add_set(domain
, domain_i
);
2683 /* Collect and return the schedules of the statements in "scop".
2684 * The range is normalized to the maximal number of scheduling
2687 __isl_give isl_union_map
*pet_scop_collect_schedule(struct pet_scop
*scop
)
2690 isl_map
*schedule_i
;
2691 isl_union_map
*schedule
;
2692 int depth
, max_depth
= 0;
2697 schedule
= isl_union_map_empty(isl_set_get_space(scop
->context
));
2699 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2700 depth
= isl_map_dim(scop
->stmts
[i
]->schedule
, isl_dim_out
);
2701 if (depth
> max_depth
)
2705 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2706 schedule_i
= isl_map_copy(scop
->stmts
[i
]->schedule
);
2707 depth
= isl_map_dim(schedule_i
, isl_dim_out
);
2708 schedule_i
= isl_map_add_dims(schedule_i
, isl_dim_out
,
2710 for (j
= depth
; j
< max_depth
; ++j
)
2711 schedule_i
= isl_map_fix_si(schedule_i
,
2713 schedule
= isl_union_map_add_map(schedule
, schedule_i
);
2719 /* Add a reference identifier to all access expressions in "stmt".
2720 * "n_ref" points to an integer that contains the sequence number
2721 * of the next reference.
2723 static struct pet_stmt
*stmt_add_ref_ids(struct pet_stmt
*stmt
, int *n_ref
)
2730 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2731 stmt
->args
[i
] = pet_expr_add_ref_ids(stmt
->args
[i
], n_ref
);
2733 return pet_stmt_free(stmt
);
2736 stmt
->body
= pet_tree_add_ref_ids(stmt
->body
, n_ref
);
2738 return pet_stmt_free(stmt
);
2743 /* Add a reference identifier to all access expressions in "scop".
2745 struct pet_scop
*pet_scop_add_ref_ids(struct pet_scop
*scop
)
2754 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2755 scop
->stmts
[i
] = stmt_add_ref_ids(scop
->stmts
[i
], &n_ref
);
2756 if (!scop
->stmts
[i
])
2757 return pet_scop_free(scop
);
2763 /* Reset the user pointer on all parameter ids in "array".
2765 static struct pet_array
*array_anonymize(struct pet_array
*array
)
2770 array
->context
= isl_set_reset_user(array
->context
);
2771 array
->extent
= isl_set_reset_user(array
->extent
);
2772 if (!array
->context
|| !array
->extent
)
2773 return pet_array_free(array
);
2778 /* Reset the user pointer on all parameter and tuple ids in "stmt".
2780 static struct pet_stmt
*stmt_anonymize(struct pet_stmt
*stmt
)
2789 stmt
->domain
= isl_set_reset_user(stmt
->domain
);
2790 stmt
->schedule
= isl_map_reset_user(stmt
->schedule
);
2791 if (!stmt
->domain
|| !stmt
->schedule
)
2792 return pet_stmt_free(stmt
);
2794 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2795 stmt
->args
[i
] = pet_expr_anonymize(stmt
->args
[i
]);
2797 return pet_stmt_free(stmt
);
2800 stmt
->body
= pet_tree_anonymize(stmt
->body
);
2802 return pet_stmt_free(stmt
);
2807 /* Reset the user pointer on the tuple ids and all parameter ids
2810 static struct pet_implication
*implication_anonymize(
2811 struct pet_implication
*implication
)
2816 implication
->extension
= isl_map_reset_user(implication
->extension
);
2817 if (!implication
->extension
)
2818 return pet_implication_free(implication
);
2823 /* Reset the user pointer on the tuple ids and all parameter ids
2824 * in "independence".
2826 static struct pet_independence
*independence_anonymize(
2827 struct pet_independence
*independence
)
2832 independence
->filter
= isl_union_map_reset_user(independence
->filter
);
2833 independence
->local
= isl_union_set_reset_user(independence
->local
);
2834 if (!independence
->filter
|| !independence
->local
)
2835 return pet_independence_free(independence
);
2837 return independence
;
2840 /* Reset the user pointer on all parameter and tuple ids in "scop".
2842 struct pet_scop
*pet_scop_anonymize(struct pet_scop
*scop
)
2849 scop
->context
= isl_set_reset_user(scop
->context
);
2850 scop
->context_value
= isl_set_reset_user(scop
->context_value
);
2851 if (!scop
->context
|| !scop
->context_value
)
2852 return pet_scop_free(scop
);
2854 for (i
= 0; i
< scop
->n_array
; ++i
) {
2855 scop
->arrays
[i
] = array_anonymize(scop
->arrays
[i
]);
2856 if (!scop
->arrays
[i
])
2857 return pet_scop_free(scop
);
2860 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2861 scop
->stmts
[i
] = stmt_anonymize(scop
->stmts
[i
]);
2862 if (!scop
->stmts
[i
])
2863 return pet_scop_free(scop
);
2866 for (i
= 0; i
< scop
->n_implication
; ++i
) {
2867 scop
->implications
[i
] =
2868 implication_anonymize(scop
->implications
[i
]);
2869 if (!scop
->implications
[i
])
2870 return pet_scop_free(scop
);
2873 for (i
= 0; i
< scop
->n_independence
; ++i
) {
2874 scop
->independences
[i
] =
2875 independence_anonymize(scop
->independences
[i
]);
2876 if (!scop
->independences
[i
])
2877 return pet_scop_free(scop
);
2883 /* Compute the gist of the iteration domain and all access relations
2884 * of "stmt" based on the constraints on the parameters specified by "context"
2885 * and the constraints on the values of nested accesses specified
2886 * by "value_bounds".
2888 static struct pet_stmt
*stmt_gist(struct pet_stmt
*stmt
,
2889 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
2897 domain
= isl_set_copy(stmt
->domain
);
2898 if (stmt
->n_arg
> 0)
2899 domain
= isl_map_domain(isl_set_unwrap(domain
));
2901 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
2903 for (i
= 0; i
< stmt
->n_arg
; ++i
) {
2904 stmt
->args
[i
] = pet_expr_gist(stmt
->args
[i
],
2905 domain
, value_bounds
);
2910 stmt
->body
= pet_tree_gist(stmt
->body
, domain
, value_bounds
);
2914 isl_set_free(domain
);
2916 domain
= isl_set_universe(pet_stmt_get_space(stmt
));
2917 domain
= isl_set_intersect_params(domain
, isl_set_copy(context
));
2918 if (stmt
->n_arg
> 0)
2919 domain
= pet_value_bounds_apply(domain
, stmt
->n_arg
, stmt
->args
,
2921 stmt
->domain
= isl_set_gist(stmt
->domain
, domain
);
2923 return pet_stmt_free(stmt
);
2927 isl_set_free(domain
);
2928 return pet_stmt_free(stmt
);
2931 /* Compute the gist of the extent of the array
2932 * based on the constraints on the parameters specified by "context".
2934 static struct pet_array
*array_gist(struct pet_array
*array
,
2935 __isl_keep isl_set
*context
)
2940 array
->extent
= isl_set_gist_params(array
->extent
,
2941 isl_set_copy(context
));
2943 return pet_array_free(array
);
2948 /* Compute the gist of all sets and relations in "scop"
2949 * based on the constraints on the parameters specified by "scop->context"
2950 * and the constraints on the values of nested accesses specified
2951 * by "value_bounds".
2953 struct pet_scop
*pet_scop_gist(struct pet_scop
*scop
,
2954 __isl_keep isl_union_map
*value_bounds
)
2961 scop
->context
= isl_set_coalesce(scop
->context
);
2963 return pet_scop_free(scop
);
2965 for (i
= 0; i
< scop
->n_array
; ++i
) {
2966 scop
->arrays
[i
] = array_gist(scop
->arrays
[i
], scop
->context
);
2967 if (!scop
->arrays
[i
])
2968 return pet_scop_free(scop
);
2971 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
2972 scop
->stmts
[i
] = stmt_gist(scop
->stmts
[i
], scop
->context
,
2974 if (!scop
->stmts
[i
])
2975 return pet_scop_free(scop
);
2981 /* Intersect the context of "scop" with "context".
2982 * To ensure that we don't introduce any unnamed parameters in
2983 * the context of "scop", we first remove the unnamed parameters
2986 struct pet_scop
*pet_scop_restrict_context(struct pet_scop
*scop
,
2987 __isl_take isl_set
*context
)
2992 context
= pet_nested_remove_from_set(context
);
2993 scop
->context
= isl_set_intersect(scop
->context
, context
);
2995 return pet_scop_free(scop
);
2999 isl_set_free(context
);
3000 return pet_scop_free(scop
);
3003 /* Drop the current context of "scop". That is, replace the context
3004 * by a universal set.
3006 struct pet_scop
*pet_scop_reset_context(struct pet_scop
*scop
)
3013 space
= isl_set_get_space(scop
->context
);
3014 isl_set_free(scop
->context
);
3015 scop
->context
= isl_set_universe(space
);
3017 return pet_scop_free(scop
);
3022 /* Append "array" to the arrays of "scop".
3024 struct pet_scop
*pet_scop_add_array(struct pet_scop
*scop
,
3025 struct pet_array
*array
)
3028 struct pet_array
**arrays
;
3030 if (!array
|| !scop
)
3033 ctx
= isl_set_get_ctx(scop
->context
);
3034 arrays
= isl_realloc_array(ctx
, scop
->arrays
, struct pet_array
*,
3038 scop
->arrays
= arrays
;
3039 scop
->arrays
[scop
->n_array
] = array
;
3044 pet_array_free(array
);
3045 return pet_scop_free(scop
);
3048 /* Create an index expression for an access to a virtual array
3049 * representing the result of a condition.
3050 * Unlike other accessed data, the id of the array is NULL as
3051 * there is no ValueDecl in the program corresponding to the virtual
3053 * The index expression is created as an identity mapping on "space".
3054 * That is, the dimension of the array is the same as that of "space".
3056 __isl_give isl_multi_pw_aff
*pet_create_test_index(__isl_take isl_space
*space
,
3062 snprintf(name
, sizeof(name
), "__pet_test_%d", test_nr
);
3063 id
= isl_id_alloc(isl_space_get_ctx(space
), name
, NULL
);
3064 space
= isl_space_map_from_set(space
);
3065 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
3066 return isl_multi_pw_aff_identity(space
);
3069 /* Add an array with the given extent to the list
3070 * of arrays in "scop" and return the extended pet_scop.
3071 * Specifically, the extent is determined by the image of "domain"
3073 * "int_size" is the number of bytes needed to represent values of type "int".
3074 * The array is marked as attaining values 0 and 1 only and
3075 * as each element being assigned at most once.
3077 struct pet_scop
*pet_scop_add_boolean_array(struct pet_scop
*scop
,
3078 __isl_take isl_set
*domain
, __isl_take isl_multi_pw_aff
*index
,
3083 struct pet_array
*array
;
3086 if (!scop
|| !domain
|| !index
)
3089 ctx
= isl_multi_pw_aff_get_ctx(index
);
3090 array
= isl_calloc_type(ctx
, struct pet_array
);
3094 access
= isl_map_from_multi_pw_aff(index
);
3095 access
= isl_map_intersect_domain(access
, domain
);
3096 array
->extent
= isl_map_range(access
);
3097 space
= isl_space_params_alloc(ctx
, 0);
3098 array
->context
= isl_set_universe(space
);
3099 space
= isl_space_set_alloc(ctx
, 0, 1);
3100 array
->value_bounds
= isl_set_universe(space
);
3101 array
->value_bounds
= isl_set_lower_bound_si(array
->value_bounds
,
3103 array
->value_bounds
= isl_set_upper_bound_si(array
->value_bounds
,
3105 array
->element_type
= strdup("int");
3106 array
->element_size
= int_size
;
3107 array
->uniquely_defined
= 1;
3109 if (!array
->extent
|| !array
->context
)
3110 array
= pet_array_free(array
);
3112 scop
= pet_scop_add_array(scop
, array
);
3116 isl_set_free(domain
);
3117 isl_multi_pw_aff_free(index
);
3118 return pet_scop_free(scop
);
3121 /* Create and return an implication on filter values equal to "satisfied"
3122 * with extension "map".
3124 static struct pet_implication
*new_implication(__isl_take isl_map
*map
,
3128 struct pet_implication
*implication
;
3132 ctx
= isl_map_get_ctx(map
);
3133 implication
= isl_alloc_type(ctx
, struct pet_implication
);
3137 implication
->extension
= map
;
3138 implication
->satisfied
= satisfied
;
3146 /* Add an implication on filter values equal to "satisfied"
3147 * with extension "map" to "scop".
3149 struct pet_scop
*pet_scop_add_implication(struct pet_scop
*scop
,
3150 __isl_take isl_map
*map
, int satisfied
)
3153 struct pet_implication
*implication
;
3154 struct pet_implication
**implications
;
3156 implication
= new_implication(map
, satisfied
);
3157 if (!scop
|| !implication
)
3160 ctx
= isl_set_get_ctx(scop
->context
);
3161 implications
= isl_realloc_array(ctx
, scop
->implications
,
3162 struct pet_implication
*,
3163 scop
->n_implication
+ 1);
3166 scop
->implications
= implications
;
3167 scop
->implications
[scop
->n_implication
] = implication
;
3168 scop
->n_implication
++;
3172 pet_implication_free(implication
);
3173 return pet_scop_free(scop
);
3176 /* Create and return a function that maps the iteration domains
3177 * of the statements in "scop" onto their outer "n" dimensions.
3178 * "space" is the parameters space of the created function.
3180 static __isl_give isl_union_pw_multi_aff
*outer_projection(
3181 struct pet_scop
*scop
, __isl_take isl_space
*space
, int n
)
3184 isl_union_pw_multi_aff
*res
;
3186 res
= isl_union_pw_multi_aff_empty(space
);
3189 return isl_union_pw_multi_aff_free(res
);
3191 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3192 struct pet_stmt
*stmt
= scop
->stmts
[i
];
3195 isl_pw_multi_aff
*pma
;
3197 space
= pet_stmt_get_space(stmt
);
3198 ma
= pet_prefix_projection(space
, n
);
3199 pma
= isl_pw_multi_aff_from_multi_aff(ma
);
3200 res
= isl_union_pw_multi_aff_add_pw_multi_aff(res
, pma
);
3206 /* Add an independence to "scop" for the inner iterator of "domain"
3207 * with local variables "local", where "domain" represents the outer
3208 * loop iterators of all statements in "scop".
3209 * If "sign" is positive, then the inner iterator increases.
3210 * Otherwise it decreases.
3212 * The independence is supposed to filter out any dependence of
3213 * an iteration of domain on a previous iteration along the inner dimension.
3214 * We therefore create a mapping from an iteration to later iterations and
3215 * then plug in the projection of the iterations domains of "scop"
3216 * onto the outer loop iterators.
3218 struct pet_scop
*pet_scop_set_independent(struct pet_scop
*scop
,
3219 __isl_keep isl_set
*domain
, __isl_take isl_union_set
*local
, int sign
)
3224 isl_union_map
*independence
;
3225 isl_union_pw_multi_aff
*proj
;
3227 if (!scop
|| !domain
|| !local
)
3230 dim
= isl_set_dim(domain
, isl_dim_set
);
3231 space
= isl_space_map_from_set(isl_set_get_space(domain
));
3232 map
= isl_map_universe(space
);
3233 for (i
= 0; i
+ 1 < dim
; ++i
)
3234 map
= isl_map_equate(map
, isl_dim_in
, i
, isl_dim_out
, i
);
3236 map
= isl_map_order_lt(map
,
3237 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
3239 map
= isl_map_order_gt(map
,
3240 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
3242 independence
= isl_union_map_from_map(map
);
3243 space
= isl_space_params(isl_set_get_space(domain
));
3244 proj
= outer_projection(scop
, space
, dim
);
3245 independence
= isl_union_map_preimage_domain_union_pw_multi_aff(
3246 independence
, isl_union_pw_multi_aff_copy(proj
));
3247 independence
= isl_union_map_preimage_range_union_pw_multi_aff(
3248 independence
, proj
);
3250 scop
= pet_scop_add_independence(scop
, independence
, local
);
3254 isl_union_set_free(local
);
3255 return pet_scop_free(scop
);
3258 /* Given an access expression, check if it is data dependent.
3259 * If so, set *found and abort the search.
3261 static int is_data_dependent(__isl_keep pet_expr
*expr
, void *user
)
3265 if (pet_expr_get_n_arg(expr
) > 0) {
3273 /* Does "scop" contain any data dependent accesses?
3275 * Check the body of each statement for such accesses.
3277 int pet_scop_has_data_dependent_accesses(struct pet_scop
*scop
)
3285 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
3286 int r
= pet_tree_foreach_access_expr(scop
->stmts
[i
]->body
,
3287 &is_data_dependent
, &found
);
3288 if (r
< 0 && !found
)
3297 /* Does "scop" contain and data dependent conditions?
3299 int pet_scop_has_data_dependent_conditions(struct pet_scop
*scop
)
3306 for (i
= 0; i
< scop
->n_stmt
; ++i
)
3307 if (scop
->stmts
[i
]->n_arg
> 0)
3313 /* Keep track of the "input" file inside the (extended) "scop".
3315 struct pet_scop
*pet_scop_set_input_file(struct pet_scop
*scop
, FILE *input
)
3317 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
3327 /* Print the original code corresponding to "scop" to printer "p".
3329 * pet_scop_print_original can only be called from
3330 * a pet_transform_C_source callback. This means that the input
3331 * file is stored in the extended scop and that the printer prints
3334 __isl_give isl_printer
*pet_scop_print_original(struct pet_scop
*scop
,
3335 __isl_take isl_printer
*p
)
3337 struct pet_scop_ext
*ext
= (struct pet_scop_ext
*) scop
;
3339 unsigned start
, end
;
3342 return isl_printer_free(p
);
3345 isl_die(isl_printer_get_ctx(p
), isl_error_invalid
,
3346 "no input file stored in scop",
3347 return isl_printer_free(p
));
3349 output
= isl_printer_get_file(p
);
3351 return isl_printer_free(p
);
3353 start
= pet_loc_get_start(scop
->loc
);
3354 end
= pet_loc_get_end(scop
->loc
);
3355 if (copy(ext
->input
, output
, start
, end
) < 0)
3356 return isl_printer_free(p
);