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
40 #include <isl/space.h>
41 #include <isl/local_space.h>
43 #include <isl/id_to_pw_aff.h>
46 #include <isl/union_set.h>
55 #include "tree2scop.h"
57 /* If "stmt" is an affine assumption, then record the assumption in "pc".
59 static __isl_give pet_context
*add_affine_assumption(struct pet_stmt
*stmt
,
60 __isl_take pet_context
*pc
)
65 affine
= pet_stmt_is_affine_assume(stmt
);
67 return pet_context_free(pc
);
70 cond
= pet_stmt_assume_get_affine_condition(stmt
);
71 cond
= isl_set_reset_tuple_id(cond
);
72 pc
= pet_context_intersect_domain(pc
, cond
);
76 /* Given a scop "scop" derived from an assumption statement,
77 * record the assumption in "pc", if it is affine.
78 * Note that "scop" should consist of exactly one statement.
80 static __isl_give pet_context
*scop_add_affine_assumption(
81 __isl_keep pet_scop
*scop
, __isl_take pet_context
*pc
)
86 return pet_context_free(pc
);
87 for (i
= 0; i
< scop
->n_stmt
; ++i
)
88 pc
= add_affine_assumption(scop
->stmts
[i
], pc
);
93 /* Update "pc" by taking into account the writes in "stmt".
94 * That is, clear any previously assigned values to variables
95 * that are written by "stmt".
97 static __isl_give pet_context
*handle_writes(struct pet_stmt
*stmt
,
98 __isl_take pet_context
*pc
)
100 return pet_context_clear_writes_in_tree(pc
, stmt
->body
);
103 /* Update "pc" based on the write accesses in "scop".
105 static __isl_give pet_context
*scop_handle_writes(struct pet_scop
*scop
,
106 __isl_take pet_context
*pc
)
111 return pet_context_free(pc
);
112 for (i
= 0; i
< scop
->n_stmt
; ++i
)
113 pc
= handle_writes(scop
->stmts
[i
], pc
);
118 /* Wrapper around pet_expr_resolve_assume
119 * for use as a callback to pet_tree_map_expr.
121 static __isl_give pet_expr
*resolve_assume(__isl_take pet_expr
*expr
,
124 pet_context
*pc
= user
;
126 return pet_expr_resolve_assume(expr
, pc
);
129 /* Check if any expression inside "tree" is an assume expression and
130 * if its single argument can be converted to an affine expression
131 * in the context of "pc".
132 * If so, replace the argument by the affine expression.
134 __isl_give pet_tree
*pet_tree_resolve_assume(__isl_take pet_tree
*tree
,
135 __isl_keep pet_context
*pc
)
137 return pet_tree_map_expr(tree
, &resolve_assume
, pc
);
140 /* Convert a pet_tree to a pet_scop with one statement within the context "pc".
141 * "tree" has already been evaluated in the context of "pc".
142 * This mainly involves resolving nested expression parameters
143 * and setting the name of the iteration space.
144 * The name is given by tree->label if it is non-NULL. Otherwise,
145 * it is of the form S_<stmt_nr>.
147 static struct pet_scop
*scop_from_evaluated_tree(__isl_take pet_tree
*tree
,
148 int stmt_nr
, __isl_keep pet_context
*pc
)
154 space
= pet_context_get_space(pc
);
156 tree
= pet_tree_resolve_nested(tree
, space
);
157 tree
= pet_tree_resolve_assume(tree
, pc
);
159 domain
= pet_context_get_domain(pc
);
160 ps
= pet_stmt_from_pet_tree(domain
, stmt_nr
, tree
);
161 return pet_scop_from_pet_stmt(space
, ps
);
164 /* Convert a top-level pet_expr to a pet_scop with one statement
165 * within the context "pc".
166 * "expr" has already been evaluated in the context of "pc".
167 * We construct a pet_tree from "expr" and continue with
168 * scop_from_evaluated_tree.
169 * The name is of the form S_<stmt_nr>.
170 * The location of the statement is set to "loc".
172 static struct pet_scop
*scop_from_evaluated_expr(__isl_take pet_expr
*expr
,
173 int stmt_nr
, __isl_take pet_loc
*loc
, __isl_keep pet_context
*pc
)
177 tree
= pet_tree_new_expr(expr
);
178 tree
= pet_tree_set_loc(tree
, loc
);
179 return scop_from_evaluated_tree(tree
, stmt_nr
, pc
);
182 /* Convert a pet_tree to a pet_scop with one statement within the context "pc".
183 * "tree" has not yet been evaluated in the context of "pc".
184 * We evaluate "tree" in the context of "pc" and continue with
185 * scop_from_evaluated_tree.
186 * The statement name is given by tree->label if it is non-NULL. Otherwise,
187 * it is of the form S_<stmt_nr>.
189 static struct pet_scop
*scop_from_unevaluated_tree(__isl_take pet_tree
*tree
,
190 int stmt_nr
, __isl_keep pet_context
*pc
)
192 tree
= pet_context_evaluate_tree(pc
, tree
);
193 return scop_from_evaluated_tree(tree
, stmt_nr
, pc
);
196 /* Convert a top-level pet_expr to a pet_scop with one statement
197 * within the context "pc", where "expr" has not yet been evaluated
198 * in the context of "pc".
199 * We construct a pet_tree from "expr" and continue with
200 * scop_from_unevaluated_tree.
201 * The statement name is of the form S_<stmt_nr>.
202 * The location of the statement is set to "loc".
204 static struct pet_scop
*scop_from_expr(__isl_take pet_expr
*expr
,
205 int stmt_nr
, __isl_take pet_loc
*loc
, __isl_keep pet_context
*pc
)
209 tree
= pet_tree_new_expr(expr
);
210 tree
= pet_tree_set_loc(tree
, loc
);
211 return scop_from_unevaluated_tree(tree
, stmt_nr
, pc
);
214 /* Construct a pet_scop with a single statement killing the entire
216 * The location of the statement is set to "loc".
218 static struct pet_scop
*kill(__isl_take pet_loc
*loc
, struct pet_array
*array
,
219 __isl_keep pet_context
*pc
, struct pet_state
*state
)
224 isl_multi_pw_aff
*index
;
230 ctx
= isl_set_get_ctx(array
->extent
);
231 access
= isl_map_from_range(isl_set_copy(array
->extent
));
232 id
= isl_set_get_tuple_id(array
->extent
);
233 space
= isl_space_alloc(ctx
, 0, 0, 0);
234 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
235 index
= isl_multi_pw_aff_zero(space
);
236 expr
= pet_expr_kill_from_access_and_index(access
, index
);
237 return scop_from_expr(expr
, state
->n_stmt
++, loc
, pc
);
243 /* Construct and return a pet_array corresponding to the variable
244 * accessed by "access" by calling the extract_array callback.
246 static struct pet_array
*extract_array(__isl_keep pet_expr
*access
,
247 __isl_keep pet_context
*pc
, struct pet_state
*state
)
249 return state
->extract_array(access
, pc
, state
->user
);
252 /* Construct a pet_scop for a (single) variable declaration
253 * within the context "pc".
255 * The scop contains the variable being declared (as an array)
256 * and a statement killing the array.
258 * If the declaration comes with an initialization, then the scop
259 * also contains an assignment to the variable.
261 static struct pet_scop
*scop_from_decl(__isl_keep pet_tree
*tree
,
262 __isl_keep pet_context
*pc
, struct pet_state
*state
)
266 struct pet_array
*array
;
267 struct pet_scop
*scop_decl
, *scop
;
268 pet_expr
*lhs
, *rhs
, *pe
;
270 array
= extract_array(tree
->u
.d
.var
, pc
, state
);
273 scop_decl
= kill(pet_tree_get_loc(tree
), array
, pc
, state
);
274 scop_decl
= pet_scop_add_array(scop_decl
, array
);
276 if (tree
->type
!= pet_tree_decl_init
)
279 lhs
= pet_expr_copy(tree
->u
.d
.var
);
280 rhs
= pet_expr_copy(tree
->u
.d
.init
);
281 type_size
= pet_expr_get_type_size(lhs
);
282 pe
= pet_expr_new_binary(type_size
, pet_op_assign
, lhs
, rhs
);
283 scop
= scop_from_expr(pe
, state
->n_stmt
++, pet_tree_get_loc(tree
), pc
);
285 ctx
= pet_tree_get_ctx(tree
);
286 scop
= pet_scop_add_seq(ctx
, scop_decl
, scop
);
291 /* Does "tree" represent a kill statement?
292 * That is, is it an expression statement that "calls" __pencil_kill?
294 static int is_pencil_kill(__isl_keep pet_tree
*tree
)
301 if (tree
->type
!= pet_tree_expr
)
303 expr
= tree
->u
.e
.expr
;
304 if (pet_expr_get_type(expr
) != pet_expr_call
)
306 name
= pet_expr_call_get_name(expr
);
309 return !strcmp(name
, "__pencil_kill");
312 /* Add a kill to "scop" that kills what is accessed by
313 * the access expression "expr".
315 * Mark the access as a write prior to evaluation to avoid
316 * the access being replaced by a possible known value
317 * during the evaluation.
319 * If the access expression has any arguments (after evaluation
320 * in the context of "pc"), then we ignore it, since we cannot
321 * tell which elements are definitely killed.
323 * Otherwise, we extend the index expression to the dimension
324 * of the accessed array and intersect with the extent of the array and
325 * add a kill expression that kills these array elements is added to "scop".
327 static struct pet_scop
*scop_add_kill(struct pet_scop
*scop
,
328 __isl_take pet_expr
*expr
, __isl_take pet_loc
*loc
,
329 __isl_keep pet_context
*pc
, struct pet_state
*state
)
333 isl_multi_pw_aff
*index
;
336 struct pet_array
*array
;
337 struct pet_scop
*scop_i
;
339 expr
= pet_expr_access_set_write(expr
, 1);
340 expr
= pet_context_evaluate_expr(pc
, expr
);
343 if (expr
->n_arg
!= 0) {
348 array
= extract_array(expr
, pc
, state
);
351 index
= pet_expr_access_get_index(expr
);
353 map
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index
));
354 id
= isl_map_get_tuple_id(map
, isl_dim_out
);
355 dim1
= isl_set_dim(array
->extent
, isl_dim_set
);
356 dim2
= isl_map_dim(map
, isl_dim_out
);
357 map
= isl_map_add_dims(map
, isl_dim_out
, dim1
- dim2
);
358 map
= isl_map_set_tuple_id(map
, isl_dim_out
, id
);
359 map
= isl_map_intersect_range(map
, isl_set_copy(array
->extent
));
360 pet_array_free(array
);
361 kill
= pet_expr_kill_from_access_and_index(map
, index
);
362 scop_i
= scop_from_evaluated_expr(kill
, state
->n_stmt
++, loc
, pc
);
363 scop
= pet_scop_add_par(state
->ctx
, scop
, scop_i
);
369 return pet_scop_free(scop
);
372 /* For each argument of the __pencil_kill call in "tree" that
373 * represents an access, add a kill statement to "scop" killing the accessed
376 static struct pet_scop
*scop_from_pencil_kill(__isl_keep pet_tree
*tree
,
377 __isl_keep pet_context
*pc
, struct pet_state
*state
)
380 struct pet_scop
*scop
;
383 call
= tree
->u
.e
.expr
;
385 scop
= pet_scop_empty(pet_context_get_space(pc
));
387 n
= pet_expr_get_n_arg(call
);
388 for (i
= 0; i
< n
; ++i
) {
392 arg
= pet_expr_get_arg(call
, i
);
394 return pet_scop_free(scop
);
395 if (pet_expr_get_type(arg
) != pet_expr_access
) {
399 loc
= pet_tree_get_loc(tree
);
400 scop
= scop_add_kill(scop
, arg
, loc
, pc
, state
);
406 /* Construct a pet_scop for an expression statement within the context "pc".
408 * If the expression calls __pencil_kill, then it needs to be converted
409 * into zero or more kill statements.
410 * Otherwise, a scop is extracted directly from the tree.
412 static struct pet_scop
*scop_from_tree_expr(__isl_keep pet_tree
*tree
,
413 __isl_keep pet_context
*pc
, struct pet_state
*state
)
417 is_kill
= is_pencil_kill(tree
);
421 return scop_from_pencil_kill(tree
, pc
, state
);
422 return scop_from_unevaluated_tree(pet_tree_copy(tree
),
423 state
->n_stmt
++, pc
);
426 /* Return those elements in the space of "cond" that come after
427 * (based on "sign") an element in "cond" in the final dimension.
429 static __isl_give isl_set
*after(__isl_take isl_set
*cond
, int sign
)
432 isl_map
*previous_to_this
;
435 dim
= isl_set_dim(cond
, isl_dim_set
);
436 space
= isl_space_map_from_set(isl_set_get_space(cond
));
437 previous_to_this
= isl_map_universe(space
);
438 for (i
= 0; i
+ 1 < dim
; ++i
)
439 previous_to_this
= isl_map_equate(previous_to_this
,
440 isl_dim_in
, i
, isl_dim_out
, i
);
442 previous_to_this
= isl_map_order_lt(previous_to_this
,
443 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
445 previous_to_this
= isl_map_order_gt(previous_to_this
,
446 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
448 cond
= isl_set_apply(cond
, previous_to_this
);
453 /* Remove those iterations of "domain" that have an earlier iteration
454 * (based on "sign") in the final dimension where "skip" is satisfied.
455 * If "apply_skip_map" is set, then "skip_map" is first applied
456 * to the embedded skip condition before removing it from the domain.
458 static __isl_give isl_set
*apply_affine_break(__isl_take isl_set
*domain
,
459 __isl_take isl_set
*skip
, int sign
,
460 int apply_skip_map
, __isl_keep isl_map
*skip_map
)
463 skip
= isl_set_apply(skip
, isl_map_copy(skip_map
));
464 skip
= isl_set_intersect(skip
, isl_set_copy(domain
));
465 return isl_set_subtract(domain
, after(skip
, sign
));
468 /* Create a single-dimensional multi-affine expression on the domain space
469 * of "pc" that is equal to the final dimension of this domain.
470 * "loop_nr" is the sequence number of the corresponding loop.
471 * If "id" is not NULL, then it is used as the output tuple name.
472 * Otherwise, the name is constructed as L_<loop_nr>.
474 static __isl_give isl_multi_aff
*map_to_last(__isl_keep pet_context
*pc
,
475 int loop_nr
, __isl_keep isl_id
*id
)
485 space
= pet_context_get_space(pc
);
486 pos
= isl_space_dim(space
, isl_dim_set
) - 1;
487 ls
= isl_local_space_from_space(space
);
488 aff
= isl_aff_var_on_domain(ls
, isl_dim_set
, pos
);
489 ma
= isl_multi_aff_from_aff(aff
);
492 label
= isl_id_copy(id
);
494 snprintf(name
, sizeof(name
), "L_%d", loop_nr
);
495 label
= isl_id_alloc(pet_context_get_ctx(pc
), name
, NULL
);
497 ma
= isl_multi_aff_set_tuple_id(ma
, isl_dim_out
, label
);
502 /* Create an affine expression that maps elements
503 * of an array "id_test" to the previous element in the final dimension
504 * (according to "inc"), provided this element belongs to "domain".
505 * That is, create the affine expression
507 * { id[outer,x] -> id[outer,x - inc] : (outer,x - inc) in domain }
509 static __isl_give isl_multi_pw_aff
*map_to_previous(__isl_take isl_id
*id_test
,
510 __isl_take isl_set
*domain
, __isl_take isl_val
*inc
)
517 isl_multi_pw_aff
*prev
;
519 pos
= isl_set_dim(domain
, isl_dim_set
) - 1;
520 space
= isl_set_get_space(domain
);
521 space
= isl_space_map_from_set(space
);
522 ma
= isl_multi_aff_identity(space
);
523 aff
= isl_multi_aff_get_aff(ma
, pos
);
524 aff
= isl_aff_add_constant_val(aff
, isl_val_neg(inc
));
525 ma
= isl_multi_aff_set_aff(ma
, pos
, aff
);
526 domain
= isl_set_preimage_multi_aff(domain
, isl_multi_aff_copy(ma
));
527 prev
= isl_multi_pw_aff_from_multi_aff(ma
);
528 pa
= isl_multi_pw_aff_get_pw_aff(prev
, pos
);
529 pa
= isl_pw_aff_intersect_domain(pa
, domain
);
530 prev
= isl_multi_pw_aff_set_pw_aff(prev
, pos
, pa
);
531 prev
= isl_multi_pw_aff_set_tuple_id(prev
, isl_dim_out
, id_test
);
536 /* Add an implication to "scop" expressing that if an element of
537 * virtual array "id_test" has value "satisfied" then all previous elements
538 * of this array (in the final dimension) also have that value.
539 * The set of previous elements is bounded by "domain".
540 * If "sign" is negative then the iterator
541 * is decreasing and we express that all subsequent array elements
542 * (but still defined previously) have the same value.
544 static struct pet_scop
*add_implication(struct pet_scop
*scop
,
545 __isl_take isl_id
*id_test
, __isl_take isl_set
*domain
, int sign
,
552 dim
= isl_set_dim(domain
, isl_dim_set
);
553 domain
= isl_set_set_tuple_id(domain
, id_test
);
554 space
= isl_space_map_from_set(isl_set_get_space(domain
));
555 map
= isl_map_universe(space
);
556 for (i
= 0; i
+ 1 < dim
; ++i
)
557 map
= isl_map_equate(map
, isl_dim_in
, i
, isl_dim_out
, i
);
559 map
= isl_map_order_ge(map
,
560 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
562 map
= isl_map_order_le(map
,
563 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
564 map
= isl_map_intersect_range(map
, domain
);
565 scop
= pet_scop_add_implication(scop
, map
, satisfied
);
570 /* Add a filter to "scop" that imposes that it is only executed
571 * when the variable identified by "id_test" has a zero value
572 * for all previous iterations of "domain".
574 * In particular, add a filter that imposes that the array
575 * has a zero value at the previous iteration of domain and
576 * add an implication that implies that it then has that
577 * value for all previous iterations.
579 static struct pet_scop
*scop_add_break(struct pet_scop
*scop
,
580 __isl_take isl_id
*id_test
, __isl_take isl_set
*domain
,
581 __isl_take isl_val
*inc
)
583 isl_multi_pw_aff
*prev
;
584 int sign
= isl_val_sgn(inc
);
586 prev
= map_to_previous(isl_id_copy(id_test
), isl_set_copy(domain
), inc
);
587 scop
= add_implication(scop
, id_test
, domain
, sign
, 0);
588 scop
= pet_scop_filter(scop
, prev
, 0);
593 static struct pet_scop
*scop_from_tree(__isl_keep pet_tree
*tree
,
594 __isl_keep pet_context
*pc
, struct pet_state
*state
);
596 /* Construct a pet_scop for an infinite loop around the given body
597 * within the context "pc".
598 * "loop_id" is the label on the loop or NULL if there is no such label.
600 * The domain of "pc" has already been extended with an infinite loop
604 * We extract a pet_scop for the body and then embed it in a loop with
607 * { [outer,t] -> [t] }
609 * If the body contains any break, then it is taken into
610 * account in apply_affine_break (if the skip condition is affine)
611 * or in scop_add_break (if the skip condition is not affine).
613 * Note that in case of an affine skip condition,
614 * since we are dealing with a loop without loop iterator,
615 * the skip condition cannot refer to the current loop iterator and
616 * so effectively, the effect on the iteration domain is of the form
618 * { [outer,0]; [outer,t] : t >= 1 and not skip }
620 static struct pet_scop
*scop_from_infinite_loop(__isl_keep pet_tree
*body
,
621 __isl_keep isl_id
*loop_id
, __isl_keep pet_context
*pc
,
622 struct pet_state
*state
)
628 isl_multi_aff
*sched
;
629 struct pet_scop
*scop
;
630 int has_affine_break
;
633 ctx
= pet_tree_get_ctx(body
);
634 domain
= pet_context_get_domain(pc
);
635 sched
= map_to_last(pc
, state
->n_loop
++, loop_id
);
637 scop
= scop_from_tree(body
, pc
, state
);
639 has_affine_break
= pet_scop_has_affine_skip(scop
, pet_skip_later
);
640 if (has_affine_break
)
641 skip
= pet_scop_get_affine_skip_domain(scop
, pet_skip_later
);
642 has_var_break
= pet_scop_has_var_skip(scop
, pet_skip_later
);
644 id_test
= pet_scop_get_skip_id(scop
, pet_skip_later
);
646 scop
= pet_scop_reset_skips(scop
);
647 scop
= pet_scop_embed(scop
, isl_set_copy(domain
), sched
);
648 if (has_affine_break
) {
649 domain
= apply_affine_break(domain
, skip
, 1, 0, NULL
);
650 scop
= pet_scop_intersect_domain_prefix(scop
,
651 isl_set_copy(domain
));
654 scop
= scop_add_break(scop
, id_test
, domain
, isl_val_one(ctx
));
656 isl_set_free(domain
);
661 /* Construct a pet_scop for an infinite loop, i.e., a loop of the form
666 * within the context "pc".
668 * Extend the domain of "pc" with an extra inner loop
672 * and construct the scop in scop_from_infinite_loop.
674 static struct pet_scop
*scop_from_infinite_for(__isl_keep pet_tree
*tree
,
675 __isl_keep pet_context
*pc
, struct pet_state
*state
)
677 struct pet_scop
*scop
;
679 pc
= pet_context_copy(pc
);
680 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.l
.body
);
682 pc
= pet_context_add_infinite_loop(pc
);
684 scop
= scop_from_infinite_loop(tree
->u
.l
.body
, tree
->label
, pc
, state
);
686 pet_context_free(pc
);
691 /* Construct a pet_scop for a while loop of the form
696 * within the context "pc".
698 * The domain of "pc" has already been extended with an infinite loop
702 * Here, we add the constraints on the outer loop iterators
703 * implied by "pa" and construct the scop in scop_from_infinite_loop.
704 * Note that the intersection with these constraints
705 * may result in an empty loop.
707 static struct pet_scop
*scop_from_affine_while(__isl_keep pet_tree
*tree
,
708 __isl_take isl_pw_aff
*pa
, __isl_take pet_context
*pc
,
709 struct pet_state
*state
)
711 struct pet_scop
*scop
;
712 isl_set
*dom
, *local
;
715 valid
= isl_pw_aff_domain(isl_pw_aff_copy(pa
));
716 dom
= isl_pw_aff_non_zero_set(pa
);
717 local
= isl_set_add_dims(isl_set_copy(dom
), isl_dim_set
, 1);
718 pc
= pet_context_intersect_domain(pc
, local
);
719 scop
= scop_from_infinite_loop(tree
->u
.l
.body
, tree
->label
, pc
, state
);
720 scop
= pet_scop_restrict(scop
, dom
);
721 scop
= pet_scop_restrict_context(scop
, valid
);
723 pet_context_free(pc
);
727 /* Construct a scop for a while, given the scops for the condition
728 * and the body, the filter identifier and the iteration domain of
731 * In particular, the scop for the condition is filtered to depend
732 * on "id_test" evaluating to true for all previous iterations
733 * of the loop, while the scop for the body is filtered to depend
734 * on "id_test" evaluating to true for all iterations up to the
736 * The actual filter only imposes that this virtual array has
737 * value one on the previous or the current iteration.
738 * The fact that this condition also applies to the previous
739 * iterations is enforced by an implication.
741 * These filtered scops are then combined into a single scop,
742 * with the condition scop scheduled before the body scop.
744 * "sign" is positive if the iterator increases and negative
747 static struct pet_scop
*scop_add_while(struct pet_scop
*scop_cond
,
748 struct pet_scop
*scop_body
, __isl_take isl_id
*id_test
,
749 __isl_take isl_set
*domain
, __isl_take isl_val
*inc
)
751 isl_ctx
*ctx
= isl_set_get_ctx(domain
);
753 isl_multi_pw_aff
*test_index
;
754 isl_multi_pw_aff
*prev
;
755 int sign
= isl_val_sgn(inc
);
756 struct pet_scop
*scop
;
758 prev
= map_to_previous(isl_id_copy(id_test
), isl_set_copy(domain
), inc
);
759 scop_cond
= pet_scop_filter(scop_cond
, prev
, 1);
761 space
= isl_space_map_from_set(isl_set_get_space(domain
));
762 test_index
= isl_multi_pw_aff_identity(space
);
763 test_index
= isl_multi_pw_aff_set_tuple_id(test_index
, isl_dim_out
,
764 isl_id_copy(id_test
));
765 scop_body
= pet_scop_filter(scop_body
, test_index
, 1);
767 scop
= pet_scop_add_seq(ctx
, scop_cond
, scop_body
);
768 scop
= add_implication(scop
, id_test
, domain
, sign
, 1);
773 /* Create a pet_scop with a single statement with name S_<stmt_nr>,
774 * evaluating "cond" and writing the result to a virtual scalar,
775 * as expressed by "index".
776 * The expression "cond" has not yet been evaluated in the context of "pc".
777 * Do so within the context "pc".
778 * The location of the statement is set to "loc".
780 static struct pet_scop
*scop_from_non_affine_condition(
781 __isl_take pet_expr
*cond
, int stmt_nr
,
782 __isl_take isl_multi_pw_aff
*index
,
783 __isl_take pet_loc
*loc
, __isl_keep pet_context
*pc
)
785 pet_expr
*expr
, *write
;
787 cond
= pet_context_evaluate_expr(pc
, cond
);
789 write
= pet_expr_from_index(index
);
790 write
= pet_expr_access_set_write(write
, 1);
791 write
= pet_expr_access_set_read(write
, 0);
792 expr
= pet_expr_new_binary(1, pet_op_assign
, write
, cond
);
794 return scop_from_evaluated_expr(expr
, stmt_nr
, loc
, pc
);
797 /* Given that "scop" has an affine skip condition of type pet_skip_now,
798 * apply this skip condition to the domain of "pc".
799 * That is, remove the elements satisfying the skip condition from
800 * the domain of "pc".
802 static __isl_give pet_context
*apply_affine_continue(__isl_take pet_context
*pc
,
803 struct pet_scop
*scop
)
805 isl_set
*domain
, *skip
;
807 skip
= pet_scop_get_affine_skip_domain(scop
, pet_skip_now
);
808 domain
= pet_context_get_domain(pc
);
809 domain
= isl_set_subtract(domain
, skip
);
810 pc
= pet_context_intersect_domain(pc
, domain
);
815 /* Add a scop for evaluating the loop increment "inc" at the end
816 * of a loop body "scop" within the context "pc".
818 * The skip conditions resulting from continue statements inside
819 * the body do not apply to "inc", but those resulting from break
820 * statements do need to get applied.
822 static struct pet_scop
*scop_add_inc(struct pet_scop
*scop
,
823 __isl_take pet_expr
*inc
, __isl_take pet_loc
*loc
,
824 __isl_keep pet_context
*pc
, struct pet_state
*state
)
826 struct pet_scop
*scop_inc
;
828 pc
= pet_context_copy(pc
);
830 if (pet_scop_has_skip(scop
, pet_skip_later
)) {
831 isl_multi_pw_aff
*skip
;
832 skip
= pet_scop_get_skip(scop
, pet_skip_later
);
833 scop
= pet_scop_set_skip(scop
, pet_skip_now
, skip
);
834 if (pet_scop_has_affine_skip(scop
, pet_skip_now
))
835 pc
= apply_affine_continue(pc
, scop
);
837 pet_scop_reset_skip(scop
, pet_skip_now
);
838 scop_inc
= scop_from_expr(inc
, state
->n_stmt
++, loc
, pc
);
839 scop
= pet_scop_add_seq(state
->ctx
, scop
, scop_inc
);
841 pet_context_free(pc
);
846 /* Construct a generic while scop, with iteration domain
847 * { [t] : t >= 0 } around the scop for "tree_body" within the context "pc".
848 * "loop_id" is the label on the loop or NULL if there is no such label.
849 * The domain of "pc" has already been extended with this infinite loop
853 * The scop consists of two parts,
854 * one for evaluating the condition "cond" and one for the body.
855 * If "expr_inc" is not NULL, then a scop for evaluating this expression
856 * is added at the end of the body,
857 * after replacing any skip conditions resulting from continue statements
858 * by the skip conditions resulting from break statements (if any).
860 * The schedules are combined as a sequence to reflect that the condition is
861 * evaluated before the body is executed and the body is filtered to depend
862 * on the result of the condition evaluating to true on all iterations
863 * up to the current iteration, while the evaluation of the condition itself
864 * is filtered to depend on the result of the condition evaluating to true
865 * on all previous iterations.
866 * The context of the scop representing the body is dropped
867 * because we don't know how many times the body will be executed,
870 * If the body contains any break, then it is taken into
871 * account in apply_affine_break (if the skip condition is affine)
872 * or in scop_add_break (if the skip condition is not affine).
874 * Note that in case of an affine skip condition,
875 * since we are dealing with a loop without loop iterator,
876 * the skip condition cannot refer to the current loop iterator and
877 * so effectively, the effect on the iteration domain is of the form
879 * { [outer,0]; [outer,t] : t >= 1 and not skip }
881 static struct pet_scop
*scop_from_non_affine_while(__isl_take pet_expr
*cond
,
882 __isl_take pet_loc
*loc
, __isl_keep pet_tree
*tree_body
,
883 __isl_keep isl_id
*loop_id
, __isl_take pet_expr
*expr_inc
,
884 __isl_take pet_context
*pc
, struct pet_state
*state
)
887 isl_id
*id_test
, *id_break_test
;
889 isl_multi_pw_aff
*test_index
;
892 isl_multi_aff
*sched
;
893 struct pet_scop
*scop
, *scop_body
;
894 int has_affine_break
;
898 space
= pet_context_get_space(pc
);
899 test_index
= pet_create_test_index(space
, state
->n_test
++);
900 scop
= scop_from_non_affine_condition(cond
, state
->n_stmt
++,
901 isl_multi_pw_aff_copy(test_index
),
902 pet_loc_copy(loc
), pc
);
903 id_test
= isl_multi_pw_aff_get_tuple_id(test_index
, isl_dim_out
);
904 domain
= pet_context_get_domain(pc
);
905 scop
= pet_scop_add_boolean_array(scop
, isl_set_copy(domain
),
906 test_index
, state
->int_size
);
908 sched
= map_to_last(pc
, state
->n_loop
++, loop_id
);
910 scop_body
= scop_from_tree(tree_body
, pc
, state
);
912 has_affine_break
= pet_scop_has_affine_skip(scop_body
, pet_skip_later
);
913 if (has_affine_break
)
914 skip
= pet_scop_get_affine_skip_domain(scop_body
,
916 has_var_break
= pet_scop_has_var_skip(scop_body
, pet_skip_later
);
918 id_break_test
= pet_scop_get_skip_id(scop_body
, pet_skip_later
);
920 scop_body
= pet_scop_reset_context(scop_body
);
922 scop_body
= scop_add_inc(scop_body
, expr_inc
, loc
, pc
, state
);
925 scop_body
= pet_scop_reset_skips(scop_body
);
927 if (has_affine_break
) {
928 domain
= apply_affine_break(domain
, skip
, 1, 0, NULL
);
929 scop
= pet_scop_intersect_domain_prefix(scop
,
930 isl_set_copy(domain
));
931 scop_body
= pet_scop_intersect_domain_prefix(scop_body
,
932 isl_set_copy(domain
));
935 scop
= scop_add_break(scop
, isl_id_copy(id_break_test
),
936 isl_set_copy(domain
), isl_val_one(ctx
));
937 scop_body
= scop_add_break(scop_body
, id_break_test
,
938 isl_set_copy(domain
), isl_val_one(ctx
));
940 scop
= scop_add_while(scop
, scop_body
, id_test
, isl_set_copy(domain
),
943 scop
= pet_scop_embed(scop
, domain
, sched
);
945 pet_context_free(pc
);
949 /* Check if the while loop is of the form
951 * while (affine expression)
954 * If so, call scop_from_affine_while to construct a scop.
956 * Otherwise, pass control to scop_from_non_affine_while.
958 * "pc" is the context in which the affine expressions in the scop are created.
959 * The domain of "pc" is extended with an infinite loop
963 * before passing control to scop_from_affine_while or
964 * scop_from_non_affine_while.
966 static struct pet_scop
*scop_from_while(__isl_keep pet_tree
*tree
,
967 __isl_keep pet_context
*pc
, struct pet_state
*state
)
975 pc
= pet_context_copy(pc
);
976 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.l
.body
);
978 cond_expr
= pet_expr_copy(tree
->u
.l
.cond
);
979 cond_expr
= pet_context_evaluate_expr(pc
, cond_expr
);
980 pa
= pet_expr_extract_affine_condition(cond_expr
, pc
);
981 pet_expr_free(cond_expr
);
983 pc
= pet_context_add_infinite_loop(pc
);
988 if (!isl_pw_aff_involves_nan(pa
))
989 return scop_from_affine_while(tree
, pa
, pc
, state
);
991 return scop_from_non_affine_while(pet_expr_copy(tree
->u
.l
.cond
),
992 pet_tree_get_loc(tree
), tree
->u
.l
.body
,
993 tree
->label
, NULL
, pc
, state
);
995 pet_context_free(pc
);
999 /* Check whether "cond" expresses a simple loop bound
1000 * on the final set dimension.
1001 * In particular, if "up" is set then "cond" should contain only
1002 * upper bounds on the final set dimension.
1003 * Otherwise, it should contain only lower bounds.
1005 static int is_simple_bound(__isl_keep isl_set
*cond
, __isl_keep isl_val
*inc
)
1009 pos
= isl_set_dim(cond
, isl_dim_set
) - 1;
1010 if (isl_val_is_pos(inc
))
1011 return !isl_set_dim_has_any_lower_bound(cond
, isl_dim_set
, pos
);
1013 return !isl_set_dim_has_any_upper_bound(cond
, isl_dim_set
, pos
);
1016 /* Extend a condition on a given iteration of a loop to one that
1017 * imposes the same condition on all previous iterations.
1018 * "domain" expresses the lower [upper] bound on the iterations
1019 * when inc is positive [negative] in its final dimension.
1021 * In particular, we construct the condition (when inc is positive)
1023 * forall i' : (domain(i') and i' <= i) => cond(i')
1025 * (where "<=" applies to the final dimension)
1026 * which is equivalent to
1028 * not exists i' : domain(i') and i' <= i and not cond(i')
1030 * We construct this set by subtracting the satisfying cond from domain,
1033 * { [i'] -> [i] : i' <= i }
1035 * and then subtracting the result from domain again.
1037 static __isl_give isl_set
*valid_for_each_iteration(__isl_take isl_set
*cond
,
1038 __isl_take isl_set
*domain
, __isl_take isl_val
*inc
)
1041 isl_map
*previous_to_this
;
1044 dim
= isl_set_dim(cond
, isl_dim_set
);
1045 space
= isl_space_map_from_set(isl_set_get_space(cond
));
1046 previous_to_this
= isl_map_universe(space
);
1047 for (i
= 0; i
+ 1 < dim
; ++i
)
1048 previous_to_this
= isl_map_equate(previous_to_this
,
1049 isl_dim_in
, i
, isl_dim_out
, i
);
1050 if (isl_val_is_pos(inc
))
1051 previous_to_this
= isl_map_order_le(previous_to_this
,
1052 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
1054 previous_to_this
= isl_map_order_ge(previous_to_this
,
1055 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
1057 cond
= isl_set_subtract(isl_set_copy(domain
), cond
);
1058 cond
= isl_set_apply(cond
, previous_to_this
);
1059 cond
= isl_set_subtract(domain
, cond
);
1066 /* Given an initial value of the form
1068 * { [outer,i] -> init(outer) }
1070 * construct a domain of the form
1072 * { [outer,i] : exists a: i = init(outer) + a * inc and a >= 0 }
1074 static __isl_give isl_set
*strided_domain(__isl_take isl_pw_aff
*init
,
1075 __isl_take isl_val
*inc
)
1080 isl_local_space
*ls
;
1083 dim
= isl_pw_aff_dim(init
, isl_dim_in
);
1085 init
= isl_pw_aff_add_dims(init
, isl_dim_in
, 1);
1086 space
= isl_pw_aff_get_domain_space(init
);
1087 ls
= isl_local_space_from_space(space
);
1088 aff
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
1089 aff
= isl_aff_add_coefficient_val(aff
, isl_dim_in
, dim
, inc
);
1090 init
= isl_pw_aff_add(init
, isl_pw_aff_from_aff(aff
));
1092 aff
= isl_aff_var_on_domain(ls
, isl_dim_set
, dim
- 1);
1093 set
= isl_pw_aff_eq_set(isl_pw_aff_from_aff(aff
), init
);
1095 set
= isl_set_lower_bound_si(set
, isl_dim_set
, dim
, 0);
1096 set
= isl_set_project_out(set
, isl_dim_set
, dim
, 1);
1101 /* Assuming "cond" represents a bound on a loop where the loop
1102 * iterator "iv" is incremented (or decremented) by one, check if wrapping
1105 * Under the given assumptions, wrapping is only possible if "cond" allows
1106 * for the last value before wrapping, i.e., 2^width - 1 in case of an
1107 * increasing iterator and 0 in case of a decreasing iterator.
1109 static int can_wrap(__isl_keep isl_set
*cond
, __isl_keep pet_expr
*iv
,
1110 __isl_keep isl_val
*inc
)
1117 test
= isl_set_copy(cond
);
1119 ctx
= isl_set_get_ctx(test
);
1120 if (isl_val_is_neg(inc
))
1121 limit
= isl_val_zero(ctx
);
1123 limit
= isl_val_int_from_ui(ctx
, pet_expr_get_type_size(iv
));
1124 limit
= isl_val_2exp(limit
);
1125 limit
= isl_val_sub_ui(limit
, 1);
1128 test
= isl_set_fix_val(cond
, isl_dim_set
, 0, limit
);
1129 cw
= !isl_set_is_empty(test
);
1139 * construct the following affine expression on this space
1141 * { [outer, v] -> [outer, v mod 2^width] }
1143 * where width is the number of bits used to represent the values
1144 * of the unsigned variable "iv".
1146 static __isl_give isl_multi_aff
*compute_wrapping(__isl_take isl_space
*space
,
1147 __isl_keep pet_expr
*iv
)
1153 dim
= isl_space_dim(space
, isl_dim_set
);
1155 space
= isl_space_map_from_set(space
);
1156 ma
= isl_multi_aff_identity(space
);
1158 aff
= isl_multi_aff_get_aff(ma
, dim
- 1);
1159 aff
= pet_wrap_aff(aff
, pet_expr_get_type_size(iv
));
1160 ma
= isl_multi_aff_set_aff(ma
, dim
- 1, aff
);
1165 /* Given two sets in the space
1169 * where l represents the outer loop iterators, compute the set
1170 * of values of l that ensure that "set1" is a subset of "set2".
1172 * set1 is a subset of set2 if
1174 * forall i: set1(l,i) => set2(l,i)
1178 * not exists i: set1(l,i) and not set2(l,i)
1182 * not exists i: (set1 \ set2)(l,i)
1184 static __isl_give isl_set
*enforce_subset(__isl_take isl_set
*set1
,
1185 __isl_take isl_set
*set2
)
1189 pos
= isl_set_dim(set1
, isl_dim_set
) - 1;
1190 set1
= isl_set_subtract(set1
, set2
);
1191 set1
= isl_set_eliminate(set1
, isl_dim_set
, pos
, 1);
1192 return isl_set_complement(set1
);
1195 /* Compute the set of outer iterator values for which "cond" holds
1196 * on the next iteration of the inner loop for each element of "dom".
1198 * We first construct mapping { [l,i] -> [l,i + inc] } (where l refers
1199 * to the outer loop iterators), plug that into "cond"
1200 * and then compute the set of outer iterators for which "dom" is a subset
1203 static __isl_give isl_set
*valid_on_next(__isl_take isl_set
*cond
,
1204 __isl_take isl_set
*dom
, __isl_take isl_val
*inc
)
1211 pos
= isl_set_dim(dom
, isl_dim_set
) - 1;
1212 space
= isl_set_get_space(dom
);
1213 space
= isl_space_map_from_set(space
);
1214 ma
= isl_multi_aff_identity(space
);
1215 aff
= isl_multi_aff_get_aff(ma
, pos
);
1216 aff
= isl_aff_add_constant_val(aff
, inc
);
1217 ma
= isl_multi_aff_set_aff(ma
, pos
, aff
);
1218 cond
= isl_set_preimage_multi_aff(cond
, ma
);
1220 return enforce_subset(dom
, cond
);
1223 /* Construct a pet_scop for the initialization of the iterator
1224 * of the for loop "tree" within the context "pc" (i.e., the context
1227 static __isl_give pet_scop
*scop_from_for_init(__isl_keep pet_tree
*tree
,
1228 __isl_keep pet_context
*pc
, struct pet_state
*state
)
1230 pet_expr
*expr_iv
, *init
;
1233 expr_iv
= pet_expr_copy(tree
->u
.l
.iv
);
1234 type_size
= pet_expr_get_type_size(expr_iv
);
1235 init
= pet_expr_copy(tree
->u
.l
.init
);
1236 init
= pet_expr_new_binary(type_size
, pet_op_assign
, expr_iv
, init
);
1237 return scop_from_expr(init
, state
->n_stmt
++,
1238 pet_tree_get_loc(tree
), pc
);
1241 /* Extract the for loop "tree" as a while loop within the context "pc_init".
1242 * In particular, "pc_init" represents the context of the loop,
1243 * whereas "pc" represents the context of the body of the loop and
1244 * has already had its domain extended with an infinite loop
1248 * The for loop has the form
1250 * for (iv = init; cond; iv += inc)
1261 * except that the skips resulting from any continue statements
1262 * in body do not apply to the increment, but are replaced by the skips
1263 * resulting from break statements.
1265 * If the loop iterator is declared in the for loop, then it is killed before
1266 * and after the loop.
1268 static struct pet_scop
*scop_from_non_affine_for(__isl_keep pet_tree
*tree
,
1269 __isl_keep pet_context
*pc_init
, __isl_take pet_context
*pc
,
1270 struct pet_state
*state
)
1274 pet_expr
*expr_iv
, *inc
;
1275 struct pet_scop
*scop_init
, *scop
;
1277 struct pet_array
*array
;
1278 struct pet_scop
*scop_kill
;
1280 iv
= pet_expr_access_get_id(tree
->u
.l
.iv
);
1281 pc
= pet_context_clear_value(pc
, iv
);
1283 declared
= tree
->u
.l
.declared
;
1285 scop_init
= scop_from_for_init(tree
, pc_init
, state
);
1287 expr_iv
= pet_expr_copy(tree
->u
.l
.iv
);
1288 type_size
= pet_expr_get_type_size(expr_iv
);
1289 inc
= pet_expr_copy(tree
->u
.l
.inc
);
1290 inc
= pet_expr_new_binary(type_size
, pet_op_add_assign
, expr_iv
, inc
);
1292 scop
= scop_from_non_affine_while(pet_expr_copy(tree
->u
.l
.cond
),
1293 pet_tree_get_loc(tree
), tree
->u
.l
.body
, tree
->label
,
1294 inc
, pet_context_copy(pc
), state
);
1296 scop
= pet_scop_add_seq(state
->ctx
, scop_init
, scop
);
1298 pet_context_free(pc
);
1303 array
= extract_array(tree
->u
.l
.iv
, pc_init
, state
);
1305 array
->declared
= 1;
1306 scop_kill
= kill(pet_tree_get_loc(tree
), array
, pc_init
, state
);
1307 scop
= pet_scop_add_seq(state
->ctx
, scop_kill
, scop
);
1308 scop_kill
= kill(pet_tree_get_loc(tree
), array
, pc_init
, state
);
1309 scop_kill
= pet_scop_add_array(scop_kill
, array
);
1310 scop
= pet_scop_add_seq(state
->ctx
, scop
, scop_kill
);
1315 /* Given an access expression "expr", is the variable accessed by
1316 * "expr" assigned anywhere inside "tree"?
1318 static int is_assigned(__isl_keep pet_expr
*expr
, __isl_keep pet_tree
*tree
)
1323 id
= pet_expr_access_get_id(expr
);
1324 assigned
= pet_tree_writes(tree
, id
);
1330 /* Are all nested access parameters in "pa" allowed given "tree".
1331 * In particular, is none of them written by anywhere inside "tree".
1333 * If "tree" has any continue or break nodes in the current loop level,
1334 * then no nested access parameters are allowed.
1335 * In particular, if there is any nested access in a guard
1336 * for a piece of code containing a "continue", then we want to introduce
1337 * a separate statement for evaluating this guard so that we can express
1338 * that the result is false for all previous iterations.
1340 static int is_nested_allowed(__isl_keep isl_pw_aff
*pa
,
1341 __isl_keep pet_tree
*tree
)
1348 if (!pet_nested_any_in_pw_aff(pa
))
1351 if (pet_tree_has_continue_or_break(tree
))
1354 nparam
= isl_pw_aff_dim(pa
, isl_dim_param
);
1355 for (i
= 0; i
< nparam
; ++i
) {
1356 isl_id
*id
= isl_pw_aff_get_dim_id(pa
, isl_dim_param
, i
);
1360 if (!pet_nested_in_id(id
)) {
1365 expr
= pet_nested_extract_expr(id
);
1366 allowed
= pet_expr_get_type(expr
) == pet_expr_access
&&
1367 !is_assigned(expr
, tree
);
1369 pet_expr_free(expr
);
1379 /* Internal data structure for collect_local.
1380 * "pc" and "state" are needed to extract pet_arrays for the local variables.
1381 * "local" collects the results.
1383 struct pet_tree_collect_local_data
{
1385 struct pet_state
*state
;
1386 isl_union_set
*local
;
1389 /* Add the variable accessed by "var" to data->local.
1390 * We extract a representation of the variable from
1391 * the pet_array constructed using extract_array
1392 * to ensure consistency with the rest of the scop.
1394 static int add_local(struct pet_tree_collect_local_data
*data
,
1395 __isl_keep pet_expr
*var
)
1397 struct pet_array
*array
;
1400 array
= extract_array(var
, data
->pc
, data
->state
);
1404 universe
= isl_set_universe(isl_set_get_space(array
->extent
));
1405 data
->local
= isl_union_set_add_set(data
->local
, universe
);
1406 pet_array_free(array
);
1411 /* If the node "tree" declares a variable, then add it to
1414 static int extract_local_var(__isl_keep pet_tree
*tree
, void *user
)
1416 enum pet_tree_type type
;
1417 struct pet_tree_collect_local_data
*data
= user
;
1419 type
= pet_tree_get_type(tree
);
1420 if (type
== pet_tree_decl
|| type
== pet_tree_decl_init
)
1421 return add_local(data
, tree
->u
.d
.var
);
1426 /* If the node "tree" is a for loop that declares its induction variable,
1427 * then add it this induction variable to data->local.
1429 static int extract_local_iterator(__isl_keep pet_tree
*tree
, void *user
)
1431 struct pet_tree_collect_local_data
*data
= user
;
1433 if (pet_tree_get_type(tree
) == pet_tree_for
&& tree
->u
.l
.declared
)
1434 return add_local(data
, tree
->u
.l
.iv
);
1439 /* Collect and return all local variables of the for loop represented
1440 * by "tree", with "scop" the corresponding pet_scop.
1441 * "pc" and "state" are needed to extract pet_arrays for the local variables.
1443 * We collect not only the variables that are declared inside "tree",
1444 * but also the loop iterators that are declared anywhere inside
1445 * any possible macro statements in "scop".
1446 * The latter also appear as declared variable in the scop,
1447 * whereas other declared loop iterators only appear implicitly
1448 * in the iteration domains.
1450 static __isl_give isl_union_set
*collect_local(struct pet_scop
*scop
,
1451 __isl_keep pet_tree
*tree
, __isl_keep pet_context
*pc
,
1452 struct pet_state
*state
)
1456 struct pet_tree_collect_local_data data
= { pc
, state
};
1458 ctx
= pet_tree_get_ctx(tree
);
1459 data
.local
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
1461 if (pet_tree_foreach_sub_tree(tree
, &extract_local_var
, &data
) < 0)
1462 return isl_union_set_free(data
.local
);
1464 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1465 pet_tree
*body
= scop
->stmts
[i
]->body
;
1466 if (pet_tree_foreach_sub_tree(body
, &extract_local_iterator
,
1468 return isl_union_set_free(data
.local
);
1474 /* Add an independence to "scop" if the for node "tree" was marked
1476 * "domain" is the set of loop iterators, with the current for loop
1477 * innermost. If "sign" is positive, then the inner iterator increases.
1478 * Otherwise it decreases.
1479 * "pc" and "state" are needed to extract pet_arrays for the local variables.
1481 * If the tree was marked, then collect all local variables and
1482 * add an independence.
1484 static struct pet_scop
*set_independence(struct pet_scop
*scop
,
1485 __isl_keep pet_tree
*tree
, __isl_keep isl_set
*domain
, int sign
,
1486 __isl_keep pet_context
*pc
, struct pet_state
*state
)
1488 isl_union_set
*local
;
1490 if (!tree
->u
.l
.independent
)
1493 local
= collect_local(scop
, tree
, pc
, state
);
1494 scop
= pet_scop_set_independent(scop
, domain
, local
, sign
);
1499 /* Add a scop for assigning to the variable corresponding to the loop
1500 * iterator the result of adding the increment to the loop iterator
1501 * at the end of a loop body "scop" within the context "pc".
1502 * "tree" represents the for loop.
1504 * The increment is of the form
1508 * Note that "iv" on the right hand side will be evaluated in terms
1509 * of the (possibly virtual) loop iterator, i.e., the inner dimension
1510 * of the domain, while "iv" on the left hand side will not be evaluated
1511 * (because it is a write) and will continue to refer to the original
1514 static __isl_give pet_scop
*add_iterator_assignment(__isl_take pet_scop
*scop
,
1515 __isl_keep pet_tree
*tree
, __isl_keep pet_context
*pc
,
1516 struct pet_state
*state
)
1519 pet_expr
*expr
, *iv
, *inc
;
1521 iv
= pet_expr_copy(tree
->u
.l
.iv
);
1522 type_size
= pet_expr_get_type_size(iv
);
1523 iv
= pet_expr_access_set_write(iv
, 0);
1524 iv
= pet_expr_access_set_read(iv
, 1);
1525 inc
= pet_expr_copy(tree
->u
.l
.inc
);
1526 expr
= pet_expr_new_binary(type_size
, pet_op_add
, iv
, inc
);
1527 iv
= pet_expr_copy(tree
->u
.l
.iv
);
1528 expr
= pet_expr_new_binary(type_size
, pet_op_assign
, iv
, expr
);
1530 scop
= scop_add_inc(scop
, expr
, pet_tree_get_loc(tree
), pc
, state
);
1535 /* Construct a pet_scop for a for tree with static affine initialization
1536 * and constant increment within the context "pc".
1537 * The domain of "pc" has already been extended with an (at this point
1538 * unbounded) inner loop iterator corresponding to the current for loop.
1540 * The condition is allowed to contain nested accesses, provided
1541 * they are not being written to inside the body of the loop.
1542 * Otherwise, or if the condition is otherwise non-affine, the for loop is
1543 * essentially treated as a while loop, with iteration domain
1544 * { [l,i] : i >= init }, where l refers to the outer loop iterators.
1546 * We extract a pet_scop for the body after intersecting the domain of "pc"
1548 * { [l,i] : i >= init and condition' }
1552 * { [l,i] : i <= init and condition' }
1554 * Where condition' is equal to condition if the latter is
1555 * a simple upper [lower] bound and a condition that is extended
1556 * to apply to all previous iterations otherwise.
1557 * Afterwards, the schedule of the pet_scop is extended with
1565 * If the condition is non-affine, then we drop the condition from the
1566 * iteration domain and instead create a separate statement
1567 * for evaluating the condition. The body is then filtered to depend
1568 * on the result of the condition evaluating to true on all iterations
1569 * up to the current iteration, while the evaluation the condition itself
1570 * is filtered to depend on the result of the condition evaluating to true
1571 * on all previous iterations.
1572 * The context of the scop representing the body is dropped
1573 * because we don't know how many times the body will be executed,
1576 * If the stride of the loop is not 1, then "i >= init" is replaced by
1578 * (exists a: i = init + stride * a and a >= 0)
1580 * If the loop iterator i is unsigned, then wrapping may occur.
1581 * We therefore use a virtual iterator instead that does not wrap.
1582 * However, the condition in the code applies
1583 * to the wrapped value, so we need to change condition(l,i)
1584 * into condition([l,i % 2^width]). Similarly, we replace all accesses
1585 * to the original iterator by the wrapping of the virtual iterator.
1586 * Note that there may be no need to perform this final wrapping
1587 * if the loop condition (after wrapping) satisfies certain conditions.
1588 * However, the is_simple_bound condition is not enough since it doesn't
1589 * check if there even is an upper bound.
1591 * Wrapping on unsigned iterators can be avoided entirely if
1592 * the loop condition is simple, the loop iterator is incremented
1593 * [decremented] by one and the last value before wrapping cannot
1594 * possibly satisfy the loop condition.
1596 * Valid outer iterators for a for loop are those for which the initial
1597 * value itself, the increment on each domain iteration and
1598 * the condition on both the initial value and
1599 * the result of incrementing the iterator for each iteration of the domain
1601 * If the loop condition is non-affine, then we only consider validity
1602 * of the initial value.
1604 * If the loop iterator was not declared inside the loop header,
1605 * then the variable corresponding to this loop iterator is assigned
1606 * the result of adding the increment at the end of the loop body.
1607 * The assignment of the initial value is taken care of by
1608 * scop_from_affine_for_init.
1610 * If the body contains any break, then we keep track of it in "skip"
1611 * (if the skip condition is affine) or it is handled in scop_add_break
1612 * (if the skip condition is not affine).
1613 * Note that the affine break condition needs to be considered with
1614 * respect to previous iterations in the virtual domain (if any).
1616 static struct pet_scop
*scop_from_affine_for(__isl_keep pet_tree
*tree
,
1617 __isl_take isl_pw_aff
*init_val
, __isl_take isl_pw_aff
*pa_inc
,
1618 __isl_take isl_val
*inc
, __isl_take pet_context
*pc
,
1619 struct pet_state
*state
)
1622 isl_multi_aff
*sched
;
1623 isl_set
*cond
= NULL
;
1624 isl_set
*skip
= NULL
;
1625 isl_id
*id_test
= NULL
, *id_break_test
;
1626 struct pet_scop
*scop
, *scop_cond
= NULL
;
1633 int has_affine_break
;
1635 isl_map
*rev_wrap
= NULL
;
1636 isl_map
*init_val_map
;
1638 isl_set
*valid_init
;
1639 isl_set
*valid_cond
;
1640 isl_set
*valid_cond_init
;
1641 isl_set
*valid_cond_next
;
1643 pet_expr
*cond_expr
;
1644 pet_context
*pc_nested
;
1646 pos
= pet_context_dim(pc
) - 1;
1648 domain
= pet_context_get_domain(pc
);
1649 cond_expr
= pet_expr_copy(tree
->u
.l
.cond
);
1650 cond_expr
= pet_context_evaluate_expr(pc
, cond_expr
);
1651 pc_nested
= pet_context_copy(pc
);
1652 pc_nested
= pet_context_set_allow_nested(pc_nested
, 1);
1653 pa
= pet_expr_extract_affine_condition(cond_expr
, pc_nested
);
1654 pet_context_free(pc_nested
);
1655 pet_expr_free(cond_expr
);
1657 valid_inc
= isl_pw_aff_domain(pa_inc
);
1659 is_unsigned
= pet_expr_get_type_size(tree
->u
.l
.iv
) > 0;
1661 is_non_affine
= isl_pw_aff_involves_nan(pa
) ||
1662 !is_nested_allowed(pa
, tree
->u
.l
.body
);
1664 pa
= isl_pw_aff_free(pa
);
1666 valid_cond
= isl_pw_aff_domain(isl_pw_aff_copy(pa
));
1667 cond
= isl_pw_aff_non_zero_set(pa
);
1669 cond
= isl_set_universe(isl_set_get_space(domain
));
1671 valid_cond
= isl_set_coalesce(valid_cond
);
1672 is_one
= isl_val_is_one(inc
) || isl_val_is_negone(inc
);
1673 is_virtual
= is_unsigned
&&
1674 (!is_one
|| can_wrap(cond
, tree
->u
.l
.iv
, inc
));
1676 init_val_map
= isl_map_from_pw_aff(isl_pw_aff_copy(init_val
));
1677 init_val_map
= isl_map_equate(init_val_map
, isl_dim_in
, pos
,
1679 valid_cond_init
= enforce_subset(isl_map_domain(init_val_map
),
1680 isl_set_copy(valid_cond
));
1681 if (is_one
&& !is_virtual
) {
1684 isl_pw_aff_free(init_val
);
1685 pa
= pet_expr_extract_comparison(
1686 isl_val_is_pos(inc
) ? pet_op_ge
: pet_op_le
,
1687 tree
->u
.l
.iv
, tree
->u
.l
.init
, pc
);
1688 valid_init
= isl_pw_aff_domain(isl_pw_aff_copy(pa
));
1689 valid_init
= isl_set_eliminate(valid_init
, isl_dim_set
,
1690 isl_set_dim(domain
, isl_dim_set
) - 1, 1);
1691 cond
= isl_pw_aff_non_zero_set(pa
);
1692 domain
= isl_set_intersect(domain
, cond
);
1696 valid_init
= isl_pw_aff_domain(isl_pw_aff_copy(init_val
));
1697 strided
= strided_domain(init_val
, isl_val_copy(inc
));
1698 domain
= isl_set_intersect(domain
, strided
);
1702 isl_multi_aff
*wrap
;
1703 wrap
= compute_wrapping(isl_set_get_space(cond
), tree
->u
.l
.iv
);
1704 pc
= pet_context_preimage_domain(pc
, wrap
);
1705 rev_wrap
= isl_map_from_multi_aff(wrap
);
1706 rev_wrap
= isl_map_reverse(rev_wrap
);
1707 cond
= isl_set_apply(cond
, isl_map_copy(rev_wrap
));
1708 valid_cond
= isl_set_apply(valid_cond
, isl_map_copy(rev_wrap
));
1709 valid_inc
= isl_set_apply(valid_inc
, isl_map_copy(rev_wrap
));
1711 is_simple
= is_simple_bound(cond
, inc
);
1713 cond
= isl_set_gist(cond
, isl_set_copy(domain
));
1714 is_simple
= is_simple_bound(cond
, inc
);
1717 cond
= valid_for_each_iteration(cond
,
1718 isl_set_copy(domain
), isl_val_copy(inc
));
1719 cond
= isl_set_align_params(cond
, isl_set_get_space(domain
));
1720 domain
= isl_set_intersect(domain
, cond
);
1721 sched
= map_to_last(pc
, state
->n_loop
++, tree
->label
);
1722 if (isl_val_is_neg(inc
))
1723 sched
= isl_multi_aff_neg(sched
);
1725 valid_cond_next
= valid_on_next(valid_cond
, isl_set_copy(domain
),
1727 valid_inc
= enforce_subset(isl_set_copy(domain
), valid_inc
);
1729 pc
= pet_context_intersect_domain(pc
, isl_set_copy(domain
));
1731 if (is_non_affine
) {
1733 isl_multi_pw_aff
*test_index
;
1734 space
= isl_set_get_space(domain
);
1735 test_index
= pet_create_test_index(space
, state
->n_test
++);
1736 scop_cond
= scop_from_non_affine_condition(
1737 pet_expr_copy(tree
->u
.l
.cond
), state
->n_stmt
++,
1738 isl_multi_pw_aff_copy(test_index
),
1739 pet_tree_get_loc(tree
), pc
);
1740 id_test
= isl_multi_pw_aff_get_tuple_id(test_index
,
1742 scop_cond
= pet_scop_add_boolean_array(scop_cond
,
1743 isl_set_copy(domain
), test_index
,
1747 scop
= scop_from_tree(tree
->u
.l
.body
, pc
, state
);
1748 has_affine_break
= scop
&&
1749 pet_scop_has_affine_skip(scop
, pet_skip_later
);
1750 if (has_affine_break
)
1751 skip
= pet_scop_get_affine_skip_domain(scop
, pet_skip_later
);
1752 has_var_break
= scop
&& pet_scop_has_var_skip(scop
, pet_skip_later
);
1754 id_break_test
= pet_scop_get_skip_id(scop
, pet_skip_later
);
1755 if (is_non_affine
) {
1756 scop
= pet_scop_reset_context(scop
);
1758 if (!tree
->u
.l
.declared
)
1759 scop
= add_iterator_assignment(scop
, tree
, pc
, state
);
1760 scop
= pet_scop_reset_skips(scop
);
1761 scop
= pet_scop_resolve_nested(scop
);
1762 if (has_affine_break
) {
1763 domain
= apply_affine_break(domain
, skip
, isl_val_sgn(inc
),
1764 is_virtual
, rev_wrap
);
1765 scop
= pet_scop_intersect_domain_prefix(scop
,
1766 isl_set_copy(domain
));
1768 isl_map_free(rev_wrap
);
1770 scop
= scop_add_break(scop
, id_break_test
, isl_set_copy(domain
),
1773 scop
= scop_add_while(scop_cond
, scop
, id_test
,
1774 isl_set_copy(domain
),
1777 scop
= set_independence(scop
, tree
, domain
, isl_val_sgn(inc
),
1779 scop
= pet_scop_embed(scop
, domain
, sched
);
1780 if (is_non_affine
) {
1781 isl_set_free(valid_inc
);
1783 valid_inc
= isl_set_intersect(valid_inc
, valid_cond_next
);
1784 valid_inc
= isl_set_intersect(valid_inc
, valid_cond_init
);
1785 valid_inc
= isl_set_project_out(valid_inc
, isl_dim_set
, pos
, 1);
1786 scop
= pet_scop_restrict_context(scop
, valid_inc
);
1791 valid_init
= isl_set_project_out(valid_init
, isl_dim_set
, pos
, 1);
1792 scop
= pet_scop_restrict_context(scop
, valid_init
);
1794 pet_context_free(pc
);
1798 /* Construct a pet_scop for a for tree with static affine initialization
1799 * and constant increment within the context "pc_init".
1800 * In particular, "pc_init" represents the context of the loop,
1801 * whereas the domain of "pc" has already been extended with an (at this point
1802 * unbounded) inner loop iterator corresponding to the current for loop.
1804 * If the loop iterator was not declared inside the loop header,
1805 * then add an assignment of the initial value to the loop iterator
1806 * before the loop. The construction of a pet_scop for the loop itself,
1807 * including updates to the loop iterator, is handled by scop_from_affine_for.
1809 static __isl_give pet_scop
*scop_from_affine_for_init(__isl_keep pet_tree
*tree
,
1810 __isl_take isl_pw_aff
*init_val
, __isl_take isl_pw_aff
*pa_inc
,
1811 __isl_take isl_val
*inc
, __isl_keep pet_context
*pc_init
,
1812 __isl_take pet_context
*pc
, struct pet_state
*state
)
1814 pet_scop
*scop_init
, *scop
;
1816 if (!tree
->u
.l
.declared
)
1817 scop_init
= scop_from_for_init(tree
, pc_init
, state
);
1819 scop
= scop_from_affine_for(tree
, init_val
, pa_inc
, inc
, pc
, state
);
1821 if (!tree
->u
.l
.declared
)
1822 scop
= pet_scop_add_seq(state
->ctx
, scop_init
, scop
);
1827 /* Construct a pet_scop for a for statement within the context of "pc".
1829 * We update the context to reflect the writes to the loop variable and
1830 * the writes inside the body.
1832 * Then we check if the initialization of the for loop
1833 * is a static affine value and the increment is a constant.
1834 * If so, we construct the pet_scop using scop_from_affine_for_init.
1835 * Otherwise, we treat the for loop as a while loop
1836 * in scop_from_non_affine_for.
1838 * Note that the initialization and the increment are extracted
1839 * in a context where the current loop iterator has been added
1840 * to the context. If these turn out not be affine, then we
1841 * have reconstruct the body context without an assignment
1842 * to this loop iterator, as this variable will then not be
1843 * treated as a dimension of the iteration domain, but as any
1846 static struct pet_scop
*scop_from_for(__isl_keep pet_tree
*tree
,
1847 __isl_keep pet_context
*init_pc
, struct pet_state
*state
)
1851 isl_pw_aff
*pa_inc
, *init_val
;
1852 pet_context
*pc
, *pc_init_val
;
1857 iv
= pet_expr_access_get_id(tree
->u
.l
.iv
);
1858 pc
= pet_context_copy(init_pc
);
1859 pc
= pet_context_add_inner_iterator(pc
, iv
);
1860 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.l
.body
);
1862 pc_init_val
= pet_context_copy(pc
);
1863 pc_init_val
= pet_context_clear_value(pc_init_val
, isl_id_copy(iv
));
1864 init_val
= pet_expr_extract_affine(tree
->u
.l
.init
, pc_init_val
);
1865 pet_context_free(pc_init_val
);
1866 pa_inc
= pet_expr_extract_affine(tree
->u
.l
.inc
, pc
);
1867 inc
= pet_extract_cst(pa_inc
);
1868 if (!pa_inc
|| !init_val
|| !inc
)
1870 if (!isl_pw_aff_involves_nan(pa_inc
) &&
1871 !isl_pw_aff_involves_nan(init_val
) && !isl_val_is_nan(inc
))
1872 return scop_from_affine_for_init(tree
, init_val
, pa_inc
, inc
,
1873 init_pc
, pc
, state
);
1875 isl_pw_aff_free(pa_inc
);
1876 isl_pw_aff_free(init_val
);
1878 pet_context_free(pc
);
1880 pc
= pet_context_copy(init_pc
);
1881 pc
= pet_context_add_infinite_loop(pc
);
1882 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.l
.body
);
1883 return scop_from_non_affine_for(tree
, init_pc
, pc
, state
);
1885 isl_pw_aff_free(pa_inc
);
1886 isl_pw_aff_free(init_val
);
1888 pet_context_free(pc
);
1892 /* Check whether "expr" is an affine constraint within the context "pc".
1894 static int is_affine_condition(__isl_keep pet_expr
*expr
,
1895 __isl_keep pet_context
*pc
)
1900 pa
= pet_expr_extract_affine_condition(expr
, pc
);
1903 is_affine
= !isl_pw_aff_involves_nan(pa
);
1904 isl_pw_aff_free(pa
);
1909 /* Check if the given if statement is a conditional assignement
1910 * with a non-affine condition.
1912 * In particular we check if "stmt" is of the form
1919 * where the condition is non-affine and a is some array or scalar access.
1921 static int is_conditional_assignment(__isl_keep pet_tree
*tree
,
1922 __isl_keep pet_context
*pc
)
1926 pet_expr
*expr1
, *expr2
;
1928 ctx
= pet_tree_get_ctx(tree
);
1929 if (!pet_options_get_detect_conditional_assignment(ctx
))
1931 if (tree
->type
!= pet_tree_if_else
)
1933 if (tree
->u
.i
.then_body
->type
!= pet_tree_expr
)
1935 if (tree
->u
.i
.else_body
->type
!= pet_tree_expr
)
1937 expr1
= tree
->u
.i
.then_body
->u
.e
.expr
;
1938 expr2
= tree
->u
.i
.else_body
->u
.e
.expr
;
1939 if (pet_expr_get_type(expr1
) != pet_expr_op
)
1941 if (pet_expr_get_type(expr2
) != pet_expr_op
)
1943 if (pet_expr_op_get_type(expr1
) != pet_op_assign
)
1945 if (pet_expr_op_get_type(expr2
) != pet_op_assign
)
1947 expr1
= pet_expr_get_arg(expr1
, 0);
1948 expr2
= pet_expr_get_arg(expr2
, 0);
1949 equal
= pet_expr_is_equal(expr1
, expr2
);
1950 pet_expr_free(expr1
);
1951 pet_expr_free(expr2
);
1952 if (equal
< 0 || !equal
)
1954 if (is_affine_condition(tree
->u
.i
.cond
, pc
))
1960 /* Given that "tree" is of the form
1967 * where a is some array or scalar access, construct a pet_scop
1968 * corresponding to this conditional assignment within the context "pc".
1969 * "cond_pa" is an affine expression with nested accesses representing
1972 * The constructed pet_scop then corresponds to the expression
1974 * a = condition ? f(...) : g(...)
1976 * All access relations in f(...) are intersected with condition
1977 * while all access relation in g(...) are intersected with the complement.
1979 static struct pet_scop
*scop_from_conditional_assignment(
1980 __isl_keep pet_tree
*tree
, __isl_take isl_pw_aff
*cond_pa
,
1981 __isl_take pet_context
*pc
, struct pet_state
*state
)
1984 isl_set
*cond
, *comp
;
1985 isl_multi_pw_aff
*index
;
1986 pet_expr
*expr1
, *expr2
;
1987 pet_expr
*pe_cond
, *pe_then
, *pe_else
, *pe
, *pe_write
;
1988 struct pet_scop
*scop
;
1990 cond
= isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond_pa
));
1991 comp
= isl_pw_aff_zero_set(isl_pw_aff_copy(cond_pa
));
1992 index
= isl_multi_pw_aff_from_pw_aff(cond_pa
);
1994 expr1
= tree
->u
.i
.then_body
->u
.e
.expr
;
1995 expr2
= tree
->u
.i
.else_body
->u
.e
.expr
;
1997 pe_cond
= pet_expr_from_index(index
);
1999 pe_then
= pet_expr_get_arg(expr1
, 1);
2000 pe_then
= pet_context_evaluate_expr(pc
, pe_then
);
2001 pe_then
= pet_expr_restrict(pe_then
, cond
);
2002 pe_else
= pet_expr_get_arg(expr2
, 1);
2003 pe_else
= pet_context_evaluate_expr(pc
, pe_else
);
2004 pe_else
= pet_expr_restrict(pe_else
, comp
);
2005 pe_write
= pet_expr_get_arg(expr1
, 0);
2006 pe_write
= pet_context_evaluate_expr(pc
, pe_write
);
2008 pe
= pet_expr_new_ternary(pe_cond
, pe_then
, pe_else
);
2009 type_size
= pet_expr_get_type_size(pe_write
);
2010 pe
= pet_expr_new_binary(type_size
, pet_op_assign
, pe_write
, pe
);
2012 scop
= scop_from_evaluated_expr(pe
, state
->n_stmt
++,
2013 pet_tree_get_loc(tree
), pc
);
2015 pet_context_free(pc
);
2020 /* Construct a pet_scop for a non-affine if statement within the context "pc".
2022 * We create a separate statement that writes the result
2023 * of the non-affine condition to a virtual scalar.
2024 * A constraint requiring the value of this virtual scalar to be one
2025 * is added to the iteration domains of the then branch.
2026 * Similarly, a constraint requiring the value of this virtual scalar
2027 * to be zero is added to the iteration domains of the else branch, if any.
2028 * We combine the schedules as a sequence to ensure that the virtual scalar
2029 * is written before it is read.
2031 * If there are any breaks or continues in the then and/or else
2032 * branches, then we may have to compute a new skip condition.
2033 * This is handled using a pet_skip_info object.
2034 * On initialization, the object checks if skip conditions need
2035 * to be computed. If so, it does so in pet_skip_info_if_extract_index and
2036 * adds them in pet_skip_info_add.
2038 static struct pet_scop
*scop_from_non_affine_if(__isl_keep pet_tree
*tree
,
2039 __isl_take pet_context
*pc
, struct pet_state
*state
)
2044 isl_multi_pw_aff
*test_index
;
2045 struct pet_skip_info skip
;
2046 struct pet_scop
*scop
, *scop_then
, *scop_else
= NULL
;
2048 has_else
= tree
->type
== pet_tree_if_else
;
2050 space
= pet_context_get_space(pc
);
2051 test_index
= pet_create_test_index(space
, state
->n_test
++);
2052 scop
= scop_from_non_affine_condition(pet_expr_copy(tree
->u
.i
.cond
),
2053 state
->n_stmt
++, isl_multi_pw_aff_copy(test_index
),
2054 pet_tree_get_loc(tree
), pc
);
2055 domain
= pet_context_get_domain(pc
);
2056 scop
= pet_scop_add_boolean_array(scop
, domain
,
2057 isl_multi_pw_aff_copy(test_index
), state
->int_size
);
2059 scop_then
= scop_from_tree(tree
->u
.i
.then_body
, pc
, state
);
2061 scop_else
= scop_from_tree(tree
->u
.i
.else_body
, pc
, state
);
2063 pet_skip_info_if_init(&skip
, state
->ctx
, scop_then
, scop_else
,
2065 pet_skip_info_if_extract_index(&skip
, test_index
, pc
, state
);
2067 scop_then
= pet_scop_filter(scop_then
,
2068 isl_multi_pw_aff_copy(test_index
), 1);
2070 scop_else
= pet_scop_filter(scop_else
, test_index
, 0);
2071 scop_then
= pet_scop_add_par(state
->ctx
, scop_then
, scop_else
);
2073 isl_multi_pw_aff_free(test_index
);
2075 scop
= pet_scop_add_seq(state
->ctx
, scop
, scop_then
);
2077 scop
= pet_skip_info_add(&skip
, scop
);
2079 pet_context_free(pc
);
2083 /* Construct a pet_scop for an affine if statement within the context "pc".
2085 * The condition is added to the iteration domains of the then branch,
2086 * while the opposite of the condition in added to the iteration domains
2087 * of the else branch, if any.
2089 * If there are any breaks or continues in the then and/or else
2090 * branches, then we may have to compute a new skip condition.
2091 * This is handled using a pet_skip_info_if object.
2092 * On initialization, the object checks if skip conditions need
2093 * to be computed. If so, it does so in pet_skip_info_if_extract_cond and
2094 * adds them in pet_skip_info_add.
2096 static struct pet_scop
*scop_from_affine_if(__isl_keep pet_tree
*tree
,
2097 __isl_take isl_pw_aff
*cond
, __isl_take pet_context
*pc
,
2098 struct pet_state
*state
)
2102 isl_set
*set
, *complement
;
2104 struct pet_skip_info skip
;
2105 struct pet_scop
*scop
, *scop_then
, *scop_else
= NULL
;
2106 pet_context
*pc_body
;
2108 ctx
= pet_tree_get_ctx(tree
);
2110 has_else
= tree
->type
== pet_tree_if_else
;
2112 valid
= isl_pw_aff_domain(isl_pw_aff_copy(cond
));
2113 set
= isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond
));
2115 pc_body
= pet_context_copy(pc
);
2116 pc_body
= pet_context_intersect_domain(pc_body
, isl_set_copy(set
));
2117 scop_then
= scop_from_tree(tree
->u
.i
.then_body
, pc_body
, state
);
2118 pet_context_free(pc_body
);
2120 pc_body
= pet_context_copy(pc
);
2121 complement
= isl_set_copy(valid
);
2122 complement
= isl_set_subtract(valid
, isl_set_copy(set
));
2123 pc_body
= pet_context_intersect_domain(pc_body
,
2124 isl_set_copy(complement
));
2125 scop_else
= scop_from_tree(tree
->u
.i
.else_body
, pc_body
, state
);
2126 pet_context_free(pc_body
);
2129 pet_skip_info_if_init(&skip
, ctx
, scop_then
, scop_else
, has_else
, 1);
2130 pet_skip_info_if_extract_cond(&skip
, cond
, pc
, state
);
2131 isl_pw_aff_free(cond
);
2133 scop
= pet_scop_restrict(scop_then
, set
);
2136 scop_else
= pet_scop_restrict(scop_else
, complement
);
2137 scop
= pet_scop_add_par(ctx
, scop
, scop_else
);
2139 scop
= pet_scop_resolve_nested(scop
);
2140 scop
= pet_scop_restrict_context(scop
, valid
);
2142 scop
= pet_skip_info_add(&skip
, scop
);
2144 pet_context_free(pc
);
2148 /* Construct a pet_scop for an if statement within the context "pc".
2150 * If the condition fits the pattern of a conditional assignment,
2151 * then it is handled by scop_from_conditional_assignment.
2152 * Note that the condition is only considered for a conditional assignment
2153 * if it is not static-affine. However, it should still convert
2154 * to an affine expression when nesting is allowed.
2156 * Otherwise, we check if the condition is affine.
2157 * If so, we construct the scop in scop_from_affine_if.
2158 * Otherwise, we construct the scop in scop_from_non_affine_if.
2160 * We allow the condition to be dynamic, i.e., to refer to
2161 * scalars or array elements that may be written to outside
2162 * of the given if statement. These nested accesses are then represented
2163 * as output dimensions in the wrapping iteration domain.
2164 * If it is also written _inside_ the then or else branch, then
2165 * we treat the condition as non-affine.
2166 * As explained in extract_non_affine_if, this will introduce
2167 * an extra statement.
2168 * For aesthetic reasons, we want this statement to have a statement
2169 * number that is lower than those of the then and else branches.
2170 * In order to evaluate if we will need such a statement, however, we
2171 * first construct scops for the then and else branches.
2172 * We therefore reserve a statement number if we might have to
2173 * introduce such an extra statement.
2175 static struct pet_scop
*scop_from_if(__isl_keep pet_tree
*tree
,
2176 __isl_keep pet_context
*pc
, struct pet_state
*state
)
2180 pet_expr
*cond_expr
;
2181 pet_context
*pc_nested
;
2186 has_else
= tree
->type
== pet_tree_if_else
;
2188 pc
= pet_context_copy(pc
);
2189 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.i
.then_body
);
2191 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.i
.else_body
);
2193 cond_expr
= pet_expr_copy(tree
->u
.i
.cond
);
2194 cond_expr
= pet_context_evaluate_expr(pc
, cond_expr
);
2195 pc_nested
= pet_context_copy(pc
);
2196 pc_nested
= pet_context_set_allow_nested(pc_nested
, 1);
2197 cond
= pet_expr_extract_affine_condition(cond_expr
, pc_nested
);
2198 pet_context_free(pc_nested
);
2199 pet_expr_free(cond_expr
);
2202 pet_context_free(pc
);
2206 if (isl_pw_aff_involves_nan(cond
)) {
2207 isl_pw_aff_free(cond
);
2208 return scop_from_non_affine_if(tree
, pc
, state
);
2211 if (is_conditional_assignment(tree
, pc
))
2212 return scop_from_conditional_assignment(tree
, cond
, pc
, state
);
2214 if ((!is_nested_allowed(cond
, tree
->u
.i
.then_body
) ||
2215 (has_else
&& !is_nested_allowed(cond
, tree
->u
.i
.else_body
)))) {
2216 isl_pw_aff_free(cond
);
2217 return scop_from_non_affine_if(tree
, pc
, state
);
2220 return scop_from_affine_if(tree
, cond
, pc
, state
);
2223 /* Return a one-dimensional multi piecewise affine expression that is equal
2224 * to the constant 1 and is defined over the given domain.
2226 static __isl_give isl_multi_pw_aff
*one_mpa(__isl_take isl_space
*space
)
2228 isl_local_space
*ls
;
2231 ls
= isl_local_space_from_space(space
);
2232 aff
= isl_aff_zero_on_domain(ls
);
2233 aff
= isl_aff_set_constant_si(aff
, 1);
2235 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
2238 /* Construct a pet_scop for a continue statement with the given domain space.
2240 * We simply create an empty scop with a universal pet_skip_now
2241 * skip condition. This skip condition will then be taken into
2242 * account by the enclosing loop construct, possibly after
2243 * being incorporated into outer skip conditions.
2245 static struct pet_scop
*scop_from_continue(__isl_keep pet_tree
*tree
,
2246 __isl_take isl_space
*space
)
2248 struct pet_scop
*scop
;
2250 scop
= pet_scop_empty(isl_space_copy(space
));
2252 scop
= pet_scop_set_skip(scop
, pet_skip_now
, one_mpa(space
));
2257 /* Construct a pet_scop for a break statement with the given domain space.
2259 * We simply create an empty scop with both a universal pet_skip_now
2260 * skip condition and a universal pet_skip_later skip condition.
2261 * These skip conditions will then be taken into
2262 * account by the enclosing loop construct, possibly after
2263 * being incorporated into outer skip conditions.
2265 static struct pet_scop
*scop_from_break(__isl_keep pet_tree
*tree
,
2266 __isl_take isl_space
*space
)
2268 struct pet_scop
*scop
;
2269 isl_multi_pw_aff
*skip
;
2271 scop
= pet_scop_empty(isl_space_copy(space
));
2273 skip
= one_mpa(space
);
2274 scop
= pet_scop_set_skip(scop
, pet_skip_now
,
2275 isl_multi_pw_aff_copy(skip
));
2276 scop
= pet_scop_set_skip(scop
, pet_skip_later
, skip
);
2281 /* Extract a clone of the kill statement "stmt".
2282 * The domain of the clone is given by "domain".
2284 static struct pet_scop
*extract_kill(__isl_keep isl_set
*domain
,
2285 struct pet_stmt
*stmt
, struct pet_state
*state
)
2289 isl_multi_pw_aff
*mpa
;
2292 if (!domain
|| !stmt
)
2295 kill
= pet_tree_expr_get_expr(stmt
->body
);
2296 space
= pet_stmt_get_space(stmt
);
2297 space
= isl_space_map_from_set(space
);
2298 mpa
= isl_multi_pw_aff_identity(space
);
2299 mpa
= isl_multi_pw_aff_reset_tuple_id(mpa
, isl_dim_in
);
2300 kill
= pet_expr_update_domain(kill
, mpa
);
2301 tree
= pet_tree_new_expr(kill
);
2302 tree
= pet_tree_set_loc(tree
, pet_loc_copy(stmt
->loc
));
2303 stmt
= pet_stmt_from_pet_tree(isl_set_copy(domain
),
2304 state
->n_stmt
++, tree
);
2305 return pet_scop_from_pet_stmt(isl_set_get_space(domain
), stmt
);
2308 /* Extract a clone of the kill statements in "scop".
2309 * The domain of each clone is given by "domain".
2310 * "scop" is expected to have been created from a DeclStmt
2311 * and should have (one of) the kill(s) as its first statement.
2312 * If "scop" was created from a declaration group, then there
2313 * may be multiple kill statements inside.
2315 static struct pet_scop
*extract_kills(__isl_keep isl_set
*domain
,
2316 struct pet_scop
*scop
, struct pet_state
*state
)
2319 struct pet_stmt
*stmt
;
2320 struct pet_scop
*kill
;
2323 if (!domain
|| !scop
)
2325 ctx
= isl_set_get_ctx(domain
);
2326 if (scop
->n_stmt
< 1)
2327 isl_die(ctx
, isl_error_internal
,
2328 "expecting at least one statement", return NULL
);
2329 stmt
= scop
->stmts
[0];
2330 if (!pet_stmt_is_kill(stmt
))
2331 isl_die(ctx
, isl_error_internal
,
2332 "expecting kill statement", return NULL
);
2334 kill
= extract_kill(domain
, stmt
, state
);
2336 for (i
= 1; i
< scop
->n_stmt
; ++i
) {
2337 struct pet_scop
*kill_i
;
2339 stmt
= scop
->stmts
[i
];
2340 if (!pet_stmt_is_kill(stmt
))
2343 kill_i
= extract_kill(domain
, stmt
, state
);
2344 kill
= pet_scop_add_par(ctx
, kill
, kill_i
);
2350 /* Has "tree" been created from a DeclStmt?
2351 * That is, is it either a declaration or a group of declarations?
2353 static int tree_is_decl(__isl_keep pet_tree
*tree
)
2360 is_decl
= pet_tree_is_decl(tree
);
2361 if (is_decl
< 0 || is_decl
)
2364 if (tree
->type
!= pet_tree_block
)
2366 if (pet_tree_block_get_block(tree
))
2368 if (tree
->u
.b
.n
== 0)
2371 for (i
= 0; i
< tree
->u
.b
.n
; ++i
) {
2372 is_decl
= tree_is_decl(tree
->u
.b
.child
[i
]);
2373 if (is_decl
< 0 || !is_decl
)
2380 /* Does "tree" represent an assignment to a variable?
2382 * The assignment may be one of
2383 * - a declaration with initialization
2384 * - an expression with a top-level assignment operator
2386 static int is_assignment(__isl_keep pet_tree
*tree
)
2390 if (tree
->type
== pet_tree_decl_init
)
2392 return pet_tree_is_assign(tree
);
2395 /* Update "pc" by taking into account the assignment performed by "tree",
2396 * where "tree" satisfies is_assignment.
2398 * In particular, if the lhs of the assignment is a scalar variable and
2399 * if the rhs is an affine expression, then keep track of this value in "pc"
2400 * so that we can plug it in when we later come across the same variable.
2402 * Any previously assigned value to the variable has already been removed
2403 * by scop_handle_writes.
2405 static __isl_give pet_context
*handle_assignment(__isl_take pet_context
*pc
,
2406 __isl_keep pet_tree
*tree
)
2408 pet_expr
*var
, *val
;
2412 if (pet_tree_get_type(tree
) == pet_tree_decl_init
) {
2413 var
= pet_tree_decl_get_var(tree
);
2414 val
= pet_tree_decl_get_init(tree
);
2417 expr
= pet_tree_expr_get_expr(tree
);
2418 var
= pet_expr_get_arg(expr
, 0);
2419 val
= pet_expr_get_arg(expr
, 1);
2420 pet_expr_free(expr
);
2423 if (!pet_expr_is_scalar_access(var
)) {
2429 pa
= pet_expr_extract_affine(val
, pc
);
2431 pc
= pet_context_free(pc
);
2433 if (!isl_pw_aff_involves_nan(pa
)) {
2434 id
= pet_expr_access_get_id(var
);
2435 pc
= pet_context_set_value(pc
, id
, pa
);
2437 isl_pw_aff_free(pa
);
2445 /* Mark all arrays in "scop" as being exposed.
2447 static struct pet_scop
*mark_exposed(struct pet_scop
*scop
)
2453 for (i
= 0; i
< scop
->n_array
; ++i
)
2454 scop
->arrays
[i
]->exposed
= 1;
2458 /* Try and construct a pet_scop corresponding to (part of)
2459 * a sequence of statements within the context "pc".
2461 * After extracting a statement, we update "pc"
2462 * based on the top-level assignments in the statement
2463 * so that we can exploit them in subsequent statements in the same block.
2464 * Top-level affine assumptions are also recorded in the context.
2466 * If there are any breaks or continues in the individual statements,
2467 * then we may have to compute a new skip condition.
2468 * This is handled using a pet_skip_info object.
2469 * On initialization, the object checks if skip conditions need
2470 * to be computed. If so, it does so in pet_skip_info_seq_extract and
2471 * adds them in pet_skip_info_add.
2473 * If "block" is set, then we need to insert kill statements at
2474 * the end of the block for any array that has been declared by
2475 * one of the statements in the sequence. Each of these declarations
2476 * results in the construction of a kill statement at the place
2477 * of the declaration, so we simply collect duplicates of
2478 * those kill statements and append these duplicates to the constructed scop.
2480 * If "block" is not set, then any array declared by one of the statements
2481 * in the sequence is marked as being exposed.
2483 * If autodetect is set, then we allow the extraction of only a subrange
2484 * of the sequence of statements. However, if there is at least one statement
2485 * for which we could not construct a scop and the final range contains
2486 * either no statements or at least one kill, then we discard the entire
2489 static struct pet_scop
*scop_from_block(__isl_keep pet_tree
*tree
,
2490 __isl_keep pet_context
*pc
, struct pet_state
*state
)
2496 struct pet_scop
*scop
, *kills
;
2498 ctx
= pet_tree_get_ctx(tree
);
2500 space
= pet_context_get_space(pc
);
2501 domain
= pet_context_get_domain(pc
);
2502 pc
= pet_context_copy(pc
);
2503 scop
= pet_scop_empty(isl_space_copy(space
));
2504 kills
= pet_scop_empty(space
);
2505 for (i
= 0; i
< tree
->u
.b
.n
; ++i
) {
2506 struct pet_scop
*scop_i
;
2508 if (pet_scop_has_affine_skip(scop
, pet_skip_now
))
2509 pc
= apply_affine_continue(pc
, scop
);
2510 scop_i
= scop_from_tree(tree
->u
.b
.child
[i
], pc
, state
);
2511 if (pet_tree_is_assume(tree
->u
.b
.child
[i
]))
2512 pc
= scop_add_affine_assumption(scop_i
, pc
);
2513 pc
= scop_handle_writes(scop_i
, pc
);
2514 if (is_assignment(tree
->u
.b
.child
[i
]))
2515 pc
= handle_assignment(pc
, tree
->u
.b
.child
[i
]);
2516 struct pet_skip_info skip
;
2517 pet_skip_info_seq_init(&skip
, ctx
, scop
, scop_i
);
2518 pet_skip_info_seq_extract(&skip
, pc
, state
);
2519 if (scop_i
&& tree_is_decl(tree
->u
.b
.child
[i
])) {
2520 if (tree
->u
.b
.block
) {
2521 struct pet_scop
*kill
;
2522 kill
= extract_kills(domain
, scop_i
, state
);
2523 kills
= pet_scop_add_par(ctx
, kills
, kill
);
2525 scop_i
= mark_exposed(scop_i
);
2527 scop
= pet_scop_add_seq(ctx
, scop
, scop_i
);
2529 scop
= pet_skip_info_add(&skip
, scop
);
2534 isl_set_free(domain
);
2536 scop
= pet_scop_add_seq(ctx
, scop
, kills
);
2538 pet_context_free(pc
);
2543 /* Internal data structure for extract_declared_arrays.
2545 * "pc" and "state" are used to create pet_array objects and kill statements.
2546 * "any" is initialized to 0 by the caller and set to 1 as soon as we have
2547 * found any declared array.
2548 * "scop" has been initialized by the caller and is used to attach
2549 * the created pet_array objects.
2550 * "kill_before" and "kill_after" are created and updated by
2551 * extract_declared_arrays to collect the kills of the arrays.
2553 struct pet_tree_extract_declared_arrays_data
{
2555 struct pet_state
*state
;
2560 struct pet_scop
*scop
;
2561 struct pet_scop
*kill_before
;
2562 struct pet_scop
*kill_after
;
2565 /* Check if the node "node" declares any array or scalar.
2566 * If so, create the corresponding pet_array and attach it to data->scop.
2567 * Additionally, create two kill statements for the array and add them
2568 * to data->kill_before and data->kill_after.
2570 static int extract_declared_arrays(__isl_keep pet_tree
*node
, void *user
)
2572 enum pet_tree_type type
;
2573 struct pet_tree_extract_declared_arrays_data
*data
= user
;
2574 struct pet_array
*array
;
2575 struct pet_scop
*scop_kill
;
2578 type
= pet_tree_get_type(node
);
2579 if (type
== pet_tree_decl
|| type
== pet_tree_decl_init
)
2580 var
= node
->u
.d
.var
;
2581 else if (type
== pet_tree_for
&& node
->u
.l
.declared
)
2586 array
= extract_array(var
, data
->pc
, data
->state
);
2588 array
->declared
= 1;
2589 data
->scop
= pet_scop_add_array(data
->scop
, array
);
2591 scop_kill
= kill(pet_tree_get_loc(node
), array
, data
->pc
, data
->state
);
2593 data
->kill_before
= scop_kill
;
2595 data
->kill_before
= pet_scop_add_par(data
->ctx
,
2596 data
->kill_before
, scop_kill
);
2598 scop_kill
= kill(pet_tree_get_loc(node
), array
, data
->pc
, data
->state
);
2600 data
->kill_after
= scop_kill
;
2602 data
->kill_after
= pet_scop_add_par(data
->ctx
,
2603 data
->kill_after
, scop_kill
);
2610 /* Convert a pet_tree that consists of more than a single leaf
2611 * to a pet_scop with a single statement encapsulating the entire pet_tree.
2612 * Do so within the context of "pc", taking into account the writes inside
2613 * "tree". That is, first clear any previously assigned values to variables
2614 * that are written by "tree".
2616 * After constructing the core scop, we also look for any arrays (or scalars)
2617 * that are declared inside "tree". Each of those arrays is marked as
2618 * having been declared and kill statements for these arrays
2619 * are introduced before and after the core scop.
2620 * Note that the input tree is not a leaf so that the declaration
2621 * cannot occur at the outer level.
2623 static struct pet_scop
*scop_from_tree_macro(__isl_take pet_tree
*tree
,
2624 __isl_keep pet_context
*pc
, struct pet_state
*state
)
2626 struct pet_tree_extract_declared_arrays_data data
= { pc
, state
};
2628 data
.pc
= pet_context_copy(data
.pc
);
2629 data
.pc
= pet_context_clear_writes_in_tree(data
.pc
, tree
);
2630 data
.scop
= scop_from_unevaluated_tree(pet_tree_copy(tree
),
2631 state
->n_stmt
++, data
.pc
);
2634 data
.ctx
= pet_context_get_ctx(data
.pc
);
2635 if (pet_tree_foreach_sub_tree(tree
, &extract_declared_arrays
,
2637 data
.scop
= pet_scop_free(data
.scop
);
2638 pet_tree_free(tree
);
2639 pet_context_free(data
.pc
);
2644 data
.scop
= pet_scop_add_seq(data
.ctx
, data
.kill_before
, data
.scop
);
2645 data
.scop
= pet_scop_add_seq(data
.ctx
, data
.scop
, data
.kill_after
);
2650 /* Construct a pet_scop that corresponds to the pet_tree "tree"
2651 * within the context "pc" by calling the appropriate function
2652 * based on the type of "tree".
2654 * If the initially constructed pet_scop turns out to involve
2655 * dynamic control and if the user has requested an encapsulation
2656 * of all dynamic control, then this pet_scop is discarded and
2657 * a new pet_scop is created with a single statement representing
2658 * the entire "tree".
2659 * However, if the scop contains any active continue or break,
2660 * then we need to include the loop containing the continue or break
2661 * in the encapsulation. We therefore postpone the encapsulation
2662 * until we have constructed a pet_scop for this enclosing loop.
2664 static struct pet_scop
*scop_from_tree(__isl_keep pet_tree
*tree
,
2665 __isl_keep pet_context
*pc
, struct pet_state
*state
)
2668 struct pet_scop
*scop
= NULL
;
2673 ctx
= pet_tree_get_ctx(tree
);
2674 switch (tree
->type
) {
2675 case pet_tree_error
:
2677 case pet_tree_block
:
2678 return scop_from_block(tree
, pc
, state
);
2679 case pet_tree_break
:
2680 return scop_from_break(tree
, pet_context_get_space(pc
));
2681 case pet_tree_continue
:
2682 return scop_from_continue(tree
, pet_context_get_space(pc
));
2684 case pet_tree_decl_init
:
2685 return scop_from_decl(tree
, pc
, state
);
2687 return scop_from_tree_expr(tree
, pc
, state
);
2689 case pet_tree_if_else
:
2690 scop
= scop_from_if(tree
, pc
, state
);
2693 scop
= scop_from_for(tree
, pc
, state
);
2695 case pet_tree_while
:
2696 scop
= scop_from_while(tree
, pc
, state
);
2698 case pet_tree_infinite_loop
:
2699 scop
= scop_from_infinite_for(tree
, pc
, state
);
2706 if (!pet_options_get_encapsulate_dynamic_control(ctx
) ||
2707 !pet_scop_has_data_dependent_conditions(scop
) ||
2708 pet_scop_has_var_skip(scop
, pet_skip_now
))
2711 pet_scop_free(scop
);
2712 return scop_from_tree_macro(pet_tree_copy(tree
), pc
, state
);
2715 /* If "tree" has a label that is of the form S_<nr>, then make
2716 * sure that state->n_stmt is greater than nr to ensure that
2717 * we will not generate S_<nr> ourselves.
2719 static int set_first_stmt(__isl_keep pet_tree
*tree
, void *user
)
2721 struct pet_state
*state
= user
;
2729 name
= isl_id_get_name(tree
->label
);
2730 if (strncmp(name
, "S_", 2) != 0)
2732 nr
= atoi(name
+ 2);
2733 if (nr
>= state
->n_stmt
)
2734 state
->n_stmt
= nr
+ 1;
2739 /* Construct a pet_scop that corresponds to the pet_tree "tree".
2740 * "int_size" is the number of bytes need to represent an integer.
2741 * "extract_array" is a callback that we can use to create a pet_array
2742 * that corresponds to the variable accessed by an expression.
2744 * Initialize the global state, construct a context and then
2745 * construct the pet_scop by recursively visiting the tree.
2747 * state.n_stmt is initialized to point beyond any explicit S_<nr> label.
2749 struct pet_scop
*pet_scop_from_pet_tree(__isl_take pet_tree
*tree
, int int_size
,
2750 struct pet_array
*(*extract_array
)(__isl_keep pet_expr
*access
,
2751 __isl_keep pet_context
*pc
, void *user
), void *user
,
2752 __isl_keep pet_context
*pc
)
2754 struct pet_scop
*scop
;
2755 struct pet_state state
= { 0 };
2760 state
.ctx
= pet_tree_get_ctx(tree
);
2761 state
.int_size
= int_size
;
2762 state
.extract_array
= extract_array
;
2764 if (pet_tree_foreach_sub_tree(tree
, &set_first_stmt
, &state
) < 0)
2765 tree
= pet_tree_free(tree
);
2767 scop
= scop_from_tree(tree
, pc
, &state
);
2768 scop
= pet_scop_set_loc(scop
, pet_tree_get_loc(tree
));
2770 pet_tree_free(tree
);
2773 scop
->context
= isl_set_params(scop
->context
);