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
35 #include <isl/id_to_pw_aff.h>
44 #include "tree2scop.h"
46 /* Update "pc" by taking into account the writes in "stmt".
47 * That is, clear any previously assigned values to variables
48 * that are written by "stmt".
50 static __isl_give pet_context
*handle_writes(struct pet_stmt
*stmt
,
51 __isl_take pet_context
*pc
)
53 return pet_context_clear_writes_in_tree(pc
, stmt
->body
);
56 /* Update "pc" based on the write accesses in "scop".
58 static __isl_give pet_context
*scop_handle_writes(struct pet_scop
*scop
,
59 __isl_take pet_context
*pc
)
64 return pet_context_free(pc
);
65 for (i
= 0; i
< scop
->n_stmt
; ++i
)
66 pc
= handle_writes(scop
->stmts
[i
], pc
);
71 /* Convert a top-level pet_expr to a pet_scop with one statement
72 * within the context "pc".
73 * "expr" has already been evaluated in the context of "pc".
74 * This mainly involves resolving nested expression parameters
75 * and setting the name of the iteration space.
76 * The name is given by "label" if it is non-NULL. Otherwise,
77 * it is of the form S_<stmt_nr>.
78 * The location of the statement is set to "loc".
80 static struct pet_scop
*scop_from_evaluated_expr(__isl_take pet_expr
*expr
,
81 __isl_take isl_id
*label
, int stmt_nr
, __isl_take pet_loc
*loc
,
82 __isl_keep pet_context
*pc
)
89 space
= pet_context_get_space(pc
);
91 expr
= pet_expr_resolve_nested(expr
, space
);
92 expr
= pet_expr_resolve_assume(expr
, pc
);
93 tree
= pet_tree_new_expr(expr
);
94 tree
= pet_tree_set_loc(tree
, loc
);
96 tree
= pet_tree_set_label(tree
, label
);
97 domain
= pet_context_get_domain(pc
);
98 ps
= pet_stmt_from_pet_tree(domain
, stmt_nr
, tree
);
99 return pet_scop_from_pet_stmt(space
, ps
);
102 /* Convert a top-level pet_expr to a pet_scop with one statement
103 * within the context "pc", where "expr" has not yet been evaluated
104 * in the context of "pc".
105 * We evaluate "expr" in the context of "pc" and continue with
106 * scop_from_evaluated_expr.
107 * The statement name is given by "label" if it is non-NULL. Otherwise,
108 * it is of the form S_<stmt_nr>.
109 * The location of the statement is set to "loc".
111 static struct pet_scop
*scop_from_expr(__isl_take pet_expr
*expr
,
112 __isl_take isl_id
*label
, int stmt_nr
, __isl_take pet_loc
*loc
,
113 __isl_keep pet_context
*pc
)
115 expr
= pet_context_evaluate_expr(pc
, expr
);
116 return scop_from_evaluated_expr(expr
, label
, stmt_nr
, loc
, pc
);
119 /* Construct a pet_scop with a single statement killing the entire
121 * The location of the statement is set to "loc".
123 static struct pet_scop
*kill(__isl_take pet_loc
*loc
, struct pet_array
*array
,
124 __isl_keep pet_context
*pc
, struct pet_state
*state
)
129 isl_multi_pw_aff
*index
;
132 struct pet_scop
*scop
;
136 ctx
= isl_set_get_ctx(array
->extent
);
137 access
= isl_map_from_range(isl_set_copy(array
->extent
));
138 id
= isl_set_get_tuple_id(array
->extent
);
139 space
= isl_space_alloc(ctx
, 0, 0, 0);
140 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
141 index
= isl_multi_pw_aff_zero(space
);
142 expr
= pet_expr_kill_from_access_and_index(access
, index
);
143 return scop_from_expr(expr
, NULL
, state
->n_stmt
++, loc
, pc
);
149 /* Construct and return a pet_array corresponding to the variable
150 * accessed by "access" by calling the extract_array callback.
152 static struct pet_array
*extract_array(__isl_keep pet_expr
*access
,
153 __isl_keep pet_context
*pc
, struct pet_state
*state
)
155 return state
->extract_array(access
, pc
, state
->user
);
158 /* Construct a pet_scop for a (single) variable declaration
159 * within the context "pc".
161 * The scop contains the variable being declared (as an array)
162 * and a statement killing the array.
164 * If the declaration comes with an initialization, then the scop
165 * also contains an assignment to the variable.
167 static struct pet_scop
*scop_from_decl(__isl_keep pet_tree
*tree
,
168 __isl_keep pet_context
*pc
, struct pet_state
*state
)
172 struct pet_array
*array
;
173 struct pet_scop
*scop_decl
, *scop
;
174 pet_expr
*lhs
, *rhs
, *pe
;
176 array
= extract_array(tree
->u
.d
.var
, pc
, state
);
179 scop_decl
= kill(pet_tree_get_loc(tree
), array
, pc
, state
);
180 scop_decl
= pet_scop_add_array(scop_decl
, array
);
182 if (tree
->type
!= pet_tree_decl_init
)
185 lhs
= pet_expr_copy(tree
->u
.d
.var
);
186 rhs
= pet_expr_copy(tree
->u
.d
.init
);
187 type_size
= pet_expr_get_type_size(lhs
);
188 pe
= pet_expr_new_binary(type_size
, pet_op_assign
, lhs
, rhs
);
189 scop
= scop_from_expr(pe
, NULL
, state
->n_stmt
++,
190 pet_tree_get_loc(tree
), pc
);
192 scop_decl
= pet_scop_prefix(scop_decl
, 0);
193 scop
= pet_scop_prefix(scop
, 1);
195 ctx
= pet_tree_get_ctx(tree
);
196 scop
= pet_scop_add_seq(ctx
, scop_decl
, scop
);
201 /* Return those elements in the space of "cond" that come after
202 * (based on "sign") an element in "cond" in the final dimension.
204 static __isl_give isl_set
*after(__isl_take isl_set
*cond
, int sign
)
207 isl_map
*previous_to_this
;
210 dim
= isl_set_dim(cond
, isl_dim_set
);
211 space
= isl_space_map_from_set(isl_set_get_space(cond
));
212 previous_to_this
= isl_map_universe(space
);
213 for (i
= 0; i
+ 1 < dim
; ++i
)
214 previous_to_this
= isl_map_equate(previous_to_this
,
215 isl_dim_in
, i
, isl_dim_out
, i
);
217 previous_to_this
= isl_map_order_lt(previous_to_this
,
218 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
220 previous_to_this
= isl_map_order_gt(previous_to_this
,
221 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
223 cond
= isl_set_apply(cond
, previous_to_this
);
228 /* Remove those iterations of "domain" that have an earlier iteration
229 * (based on "sign") in the final dimension where "skip" is satisfied.
230 * If "apply_skip_map" is set, then "skip_map" is first applied
231 * to the embedded skip condition before removing it from the domain.
233 static __isl_give isl_set
*apply_affine_break(__isl_take isl_set
*domain
,
234 __isl_take isl_set
*skip
, int sign
,
235 int apply_skip_map
, __isl_keep isl_map
*skip_map
)
238 skip
= isl_set_apply(skip
, isl_map_copy(skip_map
));
239 skip
= isl_set_intersect(skip
, isl_set_copy(domain
));
240 return isl_set_subtract(domain
, after(skip
, sign
));
243 /* Create an affine expression on the domain space of "pc" that
244 * is equal to the final dimension of this domain.
246 static __isl_give isl_aff
*map_to_last(__isl_keep pet_context
*pc
)
252 space
= pet_context_get_space(pc
);
253 pos
= isl_space_dim(space
, isl_dim_set
) - 1;
254 ls
= isl_local_space_from_space(space
);
255 return isl_aff_var_on_domain(ls
, isl_dim_set
, pos
);
258 /* Create an affine expression that maps elements
259 * of an array "id_test" to the previous element in the final dimension
260 * (according to "inc"), provided this element belongs to "domain".
261 * That is, create the affine expression
263 * { id[outer,x] -> id[outer,x - inc] : (outer,x - inc) in domain }
265 static __isl_give isl_multi_pw_aff
*map_to_previous(__isl_take isl_id
*id_test
,
266 __isl_take isl_set
*domain
, __isl_take isl_val
*inc
)
273 isl_multi_pw_aff
*prev
;
275 pos
= isl_set_dim(domain
, isl_dim_set
) - 1;
276 space
= isl_set_get_space(domain
);
277 space
= isl_space_map_from_set(space
);
278 ma
= isl_multi_aff_identity(space
);
279 aff
= isl_multi_aff_get_aff(ma
, pos
);
280 aff
= isl_aff_add_constant_val(aff
, isl_val_neg(inc
));
281 ma
= isl_multi_aff_set_aff(ma
, pos
, aff
);
282 domain
= isl_set_preimage_multi_aff(domain
, isl_multi_aff_copy(ma
));
283 prev
= isl_multi_pw_aff_from_multi_aff(ma
);
284 pa
= isl_multi_pw_aff_get_pw_aff(prev
, pos
);
285 pa
= isl_pw_aff_intersect_domain(pa
, domain
);
286 prev
= isl_multi_pw_aff_set_pw_aff(prev
, pos
, pa
);
287 prev
= isl_multi_pw_aff_set_tuple_id(prev
, isl_dim_out
, id_test
);
292 /* Add an implication to "scop" expressing that if an element of
293 * virtual array "id_test" has value "satisfied" then all previous elements
294 * of this array (in the final dimension) also have that value.
295 * The set of previous elements is bounded by "domain".
296 * If "sign" is negative then the iterator
297 * is decreasing and we express that all subsequent array elements
298 * (but still defined previously) have the same value.
300 static struct pet_scop
*add_implication(struct pet_scop
*scop
,
301 __isl_take isl_id
*id_test
, __isl_take isl_set
*domain
, int sign
,
308 dim
= isl_set_dim(domain
, isl_dim_set
);
309 domain
= isl_set_set_tuple_id(domain
, id_test
);
310 space
= isl_space_map_from_set(isl_set_get_space(domain
));
311 map
= isl_map_universe(space
);
312 for (i
= 0; i
+ 1 < dim
; ++i
)
313 map
= isl_map_equate(map
, isl_dim_in
, i
, isl_dim_out
, i
);
315 map
= isl_map_order_ge(map
,
316 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
318 map
= isl_map_order_le(map
,
319 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
320 map
= isl_map_intersect_range(map
, domain
);
321 scop
= pet_scop_add_implication(scop
, map
, satisfied
);
326 /* Add a filter to "scop" that imposes that it is only executed
327 * when the variable identified by "id_test" has a zero value
328 * for all previous iterations of "domain".
330 * In particular, add a filter that imposes that the array
331 * has a zero value at the previous iteration of domain and
332 * add an implication that implies that it then has that
333 * value for all previous iterations.
335 static struct pet_scop
*scop_add_break(struct pet_scop
*scop
,
336 __isl_take isl_id
*id_test
, __isl_take isl_set
*domain
,
337 __isl_take isl_val
*inc
)
339 isl_multi_pw_aff
*prev
;
340 int sign
= isl_val_sgn(inc
);
342 prev
= map_to_previous(isl_id_copy(id_test
), isl_set_copy(domain
), inc
);
343 scop
= add_implication(scop
, id_test
, domain
, sign
, 0);
344 scop
= pet_scop_filter(scop
, prev
, 0);
349 static struct pet_scop
*scop_from_tree(__isl_keep pet_tree
*tree
,
350 __isl_keep pet_context
*pc
, struct pet_state
*state
);
352 /* Construct a pet_scop for an infinite loop around the given body
353 * within the context "pc".
355 * The domain of "pc" has already been extended with an infinite loop
359 * We extract a pet_scop for the body and then embed it in a loop with
362 * { [outer,t] -> [t] }
364 * If the body contains any break, then it is taken into
365 * account in apply_affine_break (if the skip condition is affine)
366 * or in scop_add_break (if the skip condition is not affine).
368 * Note that in case of an affine skip condition,
369 * since we are dealing with a loop without loop iterator,
370 * the skip condition cannot refer to the current loop iterator and
371 * so effectively, the effect on the iteration domain is of the form
373 * { [outer,0]; [outer,t] : t >= 1 and not skip }
375 static struct pet_scop
*scop_from_infinite_loop(__isl_keep pet_tree
*body
,
376 __isl_keep pet_context
*pc
, struct pet_state
*state
)
383 struct pet_scop
*scop
;
384 int has_affine_break
;
387 ctx
= pet_tree_get_ctx(body
);
388 domain
= pet_context_get_domain(pc
);
389 sched
= map_to_last(pc
);
391 scop
= scop_from_tree(body
, pc
, state
);
393 has_affine_break
= pet_scop_has_affine_skip(scop
, pet_skip_later
);
394 if (has_affine_break
)
395 skip
= pet_scop_get_affine_skip_domain(scop
, pet_skip_later
);
396 has_var_break
= pet_scop_has_var_skip(scop
, pet_skip_later
);
398 id_test
= pet_scop_get_skip_id(scop
, pet_skip_later
);
400 scop
= pet_scop_embed(scop
, isl_set_copy(domain
), sched
);
401 if (has_affine_break
) {
402 domain
= apply_affine_break(domain
, skip
, 1, 0, NULL
);
403 scop
= pet_scop_intersect_domain_prefix(scop
,
404 isl_set_copy(domain
));
407 scop
= scop_add_break(scop
, id_test
, domain
, isl_val_one(ctx
));
409 isl_set_free(domain
);
414 /* Construct a pet_scop for an infinite loop, i.e., a loop of the form
419 * within the context "pc".
421 * Extend the domain of "pc" with an extra inner loop
425 * and construct the scop in scop_from_infinite_loop.
427 static struct pet_scop
*scop_from_infinite_for(__isl_keep pet_tree
*tree
,
428 __isl_keep pet_context
*pc
, struct pet_state
*state
)
430 struct pet_scop
*scop
;
432 pc
= pet_context_copy(pc
);
433 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.l
.body
);
435 pc
= pet_context_add_infinite_loop(pc
);
437 scop
= scop_from_infinite_loop(tree
->u
.l
.body
, pc
, state
);
439 pet_context_free(pc
);
444 /* Construct a pet_scop for a while loop of the form
449 * within the context "pc".
451 * The domain of "pc" has already been extended with an infinite loop
455 * Here, we add the constraints on the outer loop iterators
456 * implied by "pa" and construct the scop in scop_from_infinite_loop.
457 * Note that the intersection with these constraints
458 * may result in an empty loop.
460 static struct pet_scop
*scop_from_affine_while(__isl_keep pet_tree
*tree
,
461 __isl_take isl_pw_aff
*pa
, __isl_take pet_context
*pc
,
462 struct pet_state
*state
)
464 struct pet_scop
*scop
;
465 isl_set
*dom
, *local
;
468 valid
= isl_pw_aff_domain(isl_pw_aff_copy(pa
));
469 dom
= isl_pw_aff_non_zero_set(pa
);
470 local
= isl_set_add_dims(isl_set_copy(dom
), isl_dim_set
, 1);
471 pc
= pet_context_intersect_domain(pc
, local
);
472 scop
= scop_from_infinite_loop(tree
->u
.l
.body
, pc
, state
);
473 scop
= pet_scop_restrict(scop
, dom
);
474 scop
= pet_scop_restrict_context(scop
, valid
);
476 pet_context_free(pc
);
480 /* Construct a scop for a while, given the scops for the condition
481 * and the body, the filter identifier and the iteration domain of
484 * In particular, the scop for the condition is filtered to depend
485 * on "id_test" evaluating to true for all previous iterations
486 * of the loop, while the scop for the body is filtered to depend
487 * on "id_test" evaluating to true for all iterations up to the
489 * The actual filter only imposes that this virtual array has
490 * value one on the previous or the current iteration.
491 * The fact that this condition also applies to the previous
492 * iterations is enforced by an implication.
494 * These filtered scops are then combined into a single scop.
496 * "sign" is positive if the iterator increases and negative
499 static struct pet_scop
*scop_add_while(struct pet_scop
*scop_cond
,
500 struct pet_scop
*scop_body
, __isl_take isl_id
*id_test
,
501 __isl_take isl_set
*domain
, __isl_take isl_val
*inc
)
503 isl_ctx
*ctx
= isl_set_get_ctx(domain
);
505 isl_multi_pw_aff
*test_index
;
506 isl_multi_pw_aff
*prev
;
507 int sign
= isl_val_sgn(inc
);
508 struct pet_scop
*scop
;
510 prev
= map_to_previous(isl_id_copy(id_test
), isl_set_copy(domain
), inc
);
511 scop_cond
= pet_scop_filter(scop_cond
, prev
, 1);
513 space
= isl_space_map_from_set(isl_set_get_space(domain
));
514 test_index
= isl_multi_pw_aff_identity(space
);
515 test_index
= isl_multi_pw_aff_set_tuple_id(test_index
, isl_dim_out
,
516 isl_id_copy(id_test
));
517 scop_body
= pet_scop_filter(scop_body
, test_index
, 1);
519 scop
= pet_scop_add_seq(ctx
, scop_cond
, scop_body
);
520 scop
= add_implication(scop
, id_test
, domain
, sign
, 1);
525 /* Create a pet_scop with a single statement with name S_<stmt_nr>,
526 * evaluating "cond" and writing the result to a virtual scalar,
527 * as expressed by "index".
528 * The expression "cond" has not yet been evaluated in the context of "pc".
529 * Do so within the context "pc".
530 * The location of the statement is set to "loc".
532 static struct pet_scop
*scop_from_non_affine_condition(
533 __isl_take pet_expr
*cond
, int stmt_nr
,
534 __isl_take isl_multi_pw_aff
*index
,
535 __isl_take pet_loc
*loc
, __isl_keep pet_context
*pc
)
537 pet_expr
*expr
, *write
;
539 cond
= pet_context_evaluate_expr(pc
, cond
);
541 write
= pet_expr_from_index(index
);
542 write
= pet_expr_access_set_write(write
, 1);
543 write
= pet_expr_access_set_read(write
, 0);
544 expr
= pet_expr_new_binary(1, pet_op_assign
, write
, cond
);
546 return scop_from_evaluated_expr(expr
, NULL
, stmt_nr
, loc
, pc
);
549 /* Construct a generic while scop, with iteration domain
550 * { [t] : t >= 0 } around the scop for "tree_body" within the context "pc".
551 * The domain of "pc" has already been extended with this infinite loop
555 * The scop consists of two parts,
556 * one for evaluating the condition "cond" and one for the body.
557 * If "expr_inc" is not NULL, then a scop for evaluating this expression
558 * is added at the end of the body,
559 * after replacing any skip conditions resulting from continue statements
560 * by the skip conditions resulting from break statements (if any).
562 * The schedule is adjusted to reflect that the condition is evaluated
563 * before the body is executed and the body is filtered to depend
564 * on the result of the condition evaluating to true on all iterations
565 * up to the current iteration, while the evaluation of the condition itself
566 * is filtered to depend on the result of the condition evaluating to true
567 * on all previous iterations.
568 * The context of the scop representing the body is dropped
569 * because we don't know how many times the body will be executed,
572 * If the body contains any break, then it is taken into
573 * account in apply_affine_break (if the skip condition is affine)
574 * or in scop_add_break (if the skip condition is not affine).
576 * Note that in case of an affine skip condition,
577 * since we are dealing with a loop without loop iterator,
578 * the skip condition cannot refer to the current loop iterator and
579 * so effectively, the effect on the iteration domain is of the form
581 * { [outer,0]; [outer,t] : t >= 1 and not skip }
583 static struct pet_scop
*scop_from_non_affine_while(__isl_take pet_expr
*cond
,
584 __isl_take pet_loc
*loc
, __isl_keep pet_tree
*tree_body
,
585 __isl_take pet_expr
*expr_inc
, __isl_take pet_context
*pc
,
586 struct pet_state
*state
)
589 isl_id
*id_test
, *id_break_test
;
591 isl_multi_pw_aff
*test_index
;
595 struct pet_scop
*scop
, *scop_body
;
596 int has_affine_break
;
600 space
= pet_context_get_space(pc
);
601 test_index
= pet_create_test_index(space
, state
->n_test
++);
602 scop
= scop_from_non_affine_condition(cond
, state
->n_stmt
++,
603 isl_multi_pw_aff_copy(test_index
),
604 pet_loc_copy(loc
), pc
);
605 id_test
= isl_multi_pw_aff_get_tuple_id(test_index
, isl_dim_out
);
606 domain
= pet_context_get_domain(pc
);
607 scop
= pet_scop_add_boolean_array(scop
, isl_set_copy(domain
),
608 test_index
, state
->int_size
);
610 sched
= map_to_last(pc
);
612 scop_body
= scop_from_tree(tree_body
, pc
, state
);
614 has_affine_break
= pet_scop_has_affine_skip(scop_body
, pet_skip_later
);
615 if (has_affine_break
)
616 skip
= pet_scop_get_affine_skip_domain(scop_body
,
618 has_var_break
= pet_scop_has_var_skip(scop_body
, pet_skip_later
);
620 id_break_test
= pet_scop_get_skip_id(scop_body
, pet_skip_later
);
622 scop
= pet_scop_prefix(scop
, 0);
623 scop
= pet_scop_embed(scop
, isl_set_copy(domain
), isl_aff_copy(sched
));
624 scop_body
= pet_scop_reset_context(scop_body
);
625 scop_body
= pet_scop_prefix(scop_body
, 1);
627 struct pet_scop
*scop_inc
;
628 scop_inc
= scop_from_expr(expr_inc
, NULL
, state
->n_stmt
++,
630 scop_inc
= pet_scop_prefix(scop_inc
, 2);
631 if (pet_scop_has_skip(scop_body
, pet_skip_later
)) {
632 isl_multi_pw_aff
*skip
;
633 skip
= pet_scop_get_skip(scop_body
, pet_skip_later
);
634 scop_body
= pet_scop_set_skip(scop_body
,
637 pet_scop_reset_skip(scop_body
, pet_skip_now
);
638 scop_body
= pet_scop_add_seq(ctx
, scop_body
, scop_inc
);
641 scop_body
= pet_scop_embed(scop_body
, isl_set_copy(domain
), sched
);
643 if (has_affine_break
) {
644 domain
= apply_affine_break(domain
, skip
, 1, 0, NULL
);
645 scop
= pet_scop_intersect_domain_prefix(scop
,
646 isl_set_copy(domain
));
647 scop_body
= pet_scop_intersect_domain_prefix(scop_body
,
648 isl_set_copy(domain
));
651 scop
= scop_add_break(scop
, isl_id_copy(id_break_test
),
652 isl_set_copy(domain
), isl_val_one(ctx
));
653 scop_body
= scop_add_break(scop_body
, id_break_test
,
654 isl_set_copy(domain
), isl_val_one(ctx
));
656 scop
= scop_add_while(scop
, scop_body
, id_test
, domain
,
659 pet_context_free(pc
);
663 /* Check if the while loop is of the form
665 * while (affine expression)
668 * If so, call scop_from_affine_while to construct a scop.
670 * Otherwise, pass control to scop_from_non_affine_while.
672 * "pc" is the context in which the affine expressions in the scop are created.
673 * The domain of "pc" is extended with an infinite loop
677 * before passing control to scop_from_affine_while or
678 * scop_from_non_affine_while.
680 static struct pet_scop
*scop_from_while(__isl_keep pet_tree
*tree
,
681 __isl_keep pet_context
*pc
, struct pet_state
*state
)
689 pc
= pet_context_copy(pc
);
690 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.l
.body
);
692 cond_expr
= pet_expr_copy(tree
->u
.l
.cond
);
693 cond_expr
= pet_context_evaluate_expr(pc
, cond_expr
);
694 pa
= pet_expr_extract_affine_condition(cond_expr
, pc
);
695 pet_expr_free(cond_expr
);
697 pc
= pet_context_add_infinite_loop(pc
);
702 if (!isl_pw_aff_involves_nan(pa
))
703 return scop_from_affine_while(tree
, pa
, pc
, state
);
705 return scop_from_non_affine_while(pet_expr_copy(tree
->u
.l
.cond
),
706 pet_tree_get_loc(tree
), tree
->u
.l
.body
, NULL
,
709 pet_context_free(pc
);
713 /* Check whether "cond" expresses a simple loop bound
714 * on the final set dimension.
715 * In particular, if "up" is set then "cond" should contain only
716 * upper bounds on the final set dimension.
717 * Otherwise, it should contain only lower bounds.
719 static int is_simple_bound(__isl_keep isl_set
*cond
, __isl_keep isl_val
*inc
)
723 pos
= isl_set_dim(cond
, isl_dim_set
) - 1;
724 if (isl_val_is_pos(inc
))
725 return !isl_set_dim_has_any_lower_bound(cond
, isl_dim_set
, pos
);
727 return !isl_set_dim_has_any_upper_bound(cond
, isl_dim_set
, pos
);
730 /* Extend a condition on a given iteration of a loop to one that
731 * imposes the same condition on all previous iterations.
732 * "domain" expresses the lower [upper] bound on the iterations
733 * when inc is positive [negative] in its final dimension.
735 * In particular, we construct the condition (when inc is positive)
737 * forall i' : (domain(i') and i' <= i) => cond(i')
739 * (where "<=" applies to the final dimension)
740 * which is equivalent to
742 * not exists i' : domain(i') and i' <= i and not cond(i')
744 * We construct this set by subtracting the satisfying cond from domain,
747 * { [i'] -> [i] : i' <= i }
749 * and then subtracting the result from domain again.
751 static __isl_give isl_set
*valid_for_each_iteration(__isl_take isl_set
*cond
,
752 __isl_take isl_set
*domain
, __isl_take isl_val
*inc
)
755 isl_map
*previous_to_this
;
758 dim
= isl_set_dim(cond
, isl_dim_set
);
759 space
= isl_space_map_from_set(isl_set_get_space(cond
));
760 previous_to_this
= isl_map_universe(space
);
761 for (i
= 0; i
+ 1 < dim
; ++i
)
762 previous_to_this
= isl_map_equate(previous_to_this
,
763 isl_dim_in
, i
, isl_dim_out
, i
);
764 if (isl_val_is_pos(inc
))
765 previous_to_this
= isl_map_order_le(previous_to_this
,
766 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
768 previous_to_this
= isl_map_order_ge(previous_to_this
,
769 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
771 cond
= isl_set_subtract(isl_set_copy(domain
), cond
);
772 cond
= isl_set_apply(cond
, previous_to_this
);
773 cond
= isl_set_subtract(domain
, cond
);
780 /* Given an initial value of the form
782 * { [outer,i] -> init(outer) }
784 * construct a domain of the form
786 * { [outer,i] : exists a: i = init(outer) + a * inc and a >= 0 }
788 static __isl_give isl_set
*strided_domain(__isl_take isl_pw_aff
*init
,
789 __isl_take isl_val
*inc
)
797 dim
= isl_pw_aff_dim(init
, isl_dim_in
);
799 init
= isl_pw_aff_add_dims(init
, isl_dim_in
, 1);
800 space
= isl_pw_aff_get_domain_space(init
);
801 ls
= isl_local_space_from_space(space
);
802 aff
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
803 aff
= isl_aff_add_coefficient_val(aff
, isl_dim_in
, dim
, inc
);
804 init
= isl_pw_aff_add(init
, isl_pw_aff_from_aff(aff
));
806 aff
= isl_aff_var_on_domain(ls
, isl_dim_set
, dim
- 1);
807 set
= isl_pw_aff_eq_set(isl_pw_aff_from_aff(aff
), init
);
809 set
= isl_set_lower_bound_si(set
, isl_dim_set
, dim
, 0);
810 set
= isl_set_project_out(set
, isl_dim_set
, dim
, 1);
815 /* Assuming "cond" represents a bound on a loop where the loop
816 * iterator "iv" is incremented (or decremented) by one, check if wrapping
819 * Under the given assumptions, wrapping is only possible if "cond" allows
820 * for the last value before wrapping, i.e., 2^width - 1 in case of an
821 * increasing iterator and 0 in case of a decreasing iterator.
823 static int can_wrap(__isl_keep isl_set
*cond
, __isl_keep pet_expr
*iv
,
824 __isl_keep isl_val
*inc
)
831 test
= isl_set_copy(cond
);
833 ctx
= isl_set_get_ctx(test
);
834 if (isl_val_is_neg(inc
))
835 limit
= isl_val_zero(ctx
);
837 limit
= isl_val_int_from_ui(ctx
, pet_expr_get_type_size(iv
));
838 limit
= isl_val_2exp(limit
);
839 limit
= isl_val_sub_ui(limit
, 1);
842 test
= isl_set_fix_val(cond
, isl_dim_set
, 0, limit
);
843 cw
= !isl_set_is_empty(test
);
853 * construct the following affine expression on this space
855 * { [outer, v] -> [outer, v mod 2^width] }
857 * where width is the number of bits used to represent the values
858 * of the unsigned variable "iv".
860 static __isl_give isl_multi_aff
*compute_wrapping(__isl_take isl_space
*space
,
861 __isl_keep pet_expr
*iv
)
869 dim
= isl_space_dim(space
, isl_dim_set
);
871 ctx
= isl_space_get_ctx(space
);
872 mod
= isl_val_int_from_ui(ctx
, pet_expr_get_type_size(iv
));
873 mod
= isl_val_2exp(mod
);
875 space
= isl_space_map_from_set(space
);
876 ma
= isl_multi_aff_identity(space
);
878 aff
= isl_multi_aff_get_aff(ma
, dim
- 1);
879 aff
= isl_aff_mod_val(aff
, mod
);
880 ma
= isl_multi_aff_set_aff(ma
, dim
- 1, aff
);
885 /* Given two sets in the space
889 * where l represents the outer loop iterators, compute the set
890 * of values of l that ensure that "set1" is a subset of "set2".
892 * set1 is a subset of set2 if
894 * forall i: set1(l,i) => set2(l,i)
898 * not exists i: set1(l,i) and not set2(l,i)
902 * not exists i: (set1 \ set2)(l,i)
904 static __isl_give isl_set
*enforce_subset(__isl_take isl_set
*set1
,
905 __isl_take isl_set
*set2
)
909 pos
= isl_set_dim(set1
, isl_dim_set
) - 1;
910 set1
= isl_set_subtract(set1
, set2
);
911 set1
= isl_set_eliminate(set1
, isl_dim_set
, pos
, 1);
912 return isl_set_complement(set1
);
915 /* Compute the set of outer iterator values for which "cond" holds
916 * on the next iteration of the inner loop for each element of "dom".
918 * We first construct mapping { [l,i] -> [l,i + inc] } (where l refers
919 * to the outer loop iterators), plug that into "cond"
920 * and then compute the set of outer iterators for which "dom" is a subset
923 static __isl_give isl_set
*valid_on_next(__isl_take isl_set
*cond
,
924 __isl_take isl_set
*dom
, __isl_take isl_val
*inc
)
931 pos
= isl_set_dim(dom
, isl_dim_set
) - 1;
932 space
= isl_set_get_space(dom
);
933 space
= isl_space_map_from_set(space
);
934 ma
= isl_multi_aff_identity(space
);
935 aff
= isl_multi_aff_get_aff(ma
, pos
);
936 aff
= isl_aff_add_constant_val(aff
, inc
);
937 ma
= isl_multi_aff_set_aff(ma
, pos
, aff
);
938 cond
= isl_set_preimage_multi_aff(cond
, ma
);
940 return enforce_subset(dom
, cond
);
943 /* Extract the for loop "tree" as a while loop within the context "pc_init".
944 * In particular, "pc_init" represents the context of the loop,
945 * whereas "pc" represents the context of the body of the loop and
946 * has already had its domain extended with an infinite loop
950 * The for loop has the form
952 * for (iv = init; cond; iv += inc)
963 * except that the skips resulting from any continue statements
964 * in body do not apply to the increment, but are replaced by the skips
965 * resulting from break statements.
967 * If the loop iterator is declared in the for loop, then it is killed before
968 * and after the loop.
970 static struct pet_scop
*scop_from_non_affine_for(__isl_keep pet_tree
*tree
,
971 __isl_keep pet_context
*init_pc
, __isl_take pet_context
*pc
,
972 struct pet_state
*state
)
976 pet_expr
*expr_iv
, *init
, *inc
;
977 struct pet_scop
*scop_init
, *scop
;
979 struct pet_array
*array
;
980 struct pet_scop
*scop_kill
;
982 iv
= pet_expr_access_get_id(tree
->u
.l
.iv
);
983 pc
= pet_context_clear_value(pc
, iv
);
985 declared
= tree
->u
.l
.declared
;
987 expr_iv
= pet_expr_copy(tree
->u
.l
.iv
);
988 type_size
= pet_expr_get_type_size(expr_iv
);
989 init
= pet_expr_copy(tree
->u
.l
.init
);
990 init
= pet_expr_new_binary(type_size
, pet_op_assign
, expr_iv
, init
);
991 scop_init
= scop_from_expr(init
, NULL
, state
->n_stmt
++,
992 pet_tree_get_loc(tree
), init_pc
);
993 scop_init
= pet_scop_prefix(scop_init
, declared
);
995 expr_iv
= pet_expr_copy(tree
->u
.l
.iv
);
996 type_size
= pet_expr_get_type_size(expr_iv
);
997 inc
= pet_expr_copy(tree
->u
.l
.inc
);
998 inc
= pet_expr_new_binary(type_size
, pet_op_add_assign
, expr_iv
, inc
);
1000 scop
= scop_from_non_affine_while(pet_expr_copy(tree
->u
.l
.cond
),
1001 pet_tree_get_loc(tree
), tree
->u
.l
.body
, inc
,
1002 pet_context_copy(pc
), state
);
1004 scop
= pet_scop_prefix(scop
, declared
+ 1);
1005 scop
= pet_scop_add_seq(state
->ctx
, scop_init
, scop
);
1007 pet_context_free(pc
);
1012 array
= extract_array(tree
->u
.l
.iv
, init_pc
, state
);
1014 array
->declared
= 1;
1015 scop_kill
= kill(pet_tree_get_loc(tree
), array
, init_pc
, state
);
1016 scop_kill
= pet_scop_prefix(scop_kill
, 0);
1017 scop
= pet_scop_add_seq(state
->ctx
, scop_kill
, scop
);
1018 scop_kill
= kill(pet_tree_get_loc(tree
), array
, init_pc
, state
);
1019 scop_kill
= pet_scop_add_array(scop_kill
, array
);
1020 scop_kill
= pet_scop_prefix(scop_kill
, 3);
1021 scop
= pet_scop_add_seq(state
->ctx
, scop
, scop_kill
);
1026 /* Given an access expression "expr", is the variable accessed by
1027 * "expr" assigned anywhere inside "tree"?
1029 static int is_assigned(__isl_keep pet_expr
*expr
, __isl_keep pet_tree
*tree
)
1034 id
= pet_expr_access_get_id(expr
);
1035 assigned
= pet_tree_writes(tree
, id
);
1041 /* Are all nested access parameters in "pa" allowed given "tree".
1042 * In particular, is none of them written by anywhere inside "tree".
1044 * If "tree" has any continue nodes in the current loop level,
1045 * then no nested access parameters are allowed.
1046 * In particular, if there is any nested access in a guard
1047 * for a piece of code containing a "continue", then we want to introduce
1048 * a separate statement for evaluating this guard so that we can express
1049 * that the result is false for all previous iterations.
1051 static int is_nested_allowed(__isl_keep isl_pw_aff
*pa
,
1052 __isl_keep pet_tree
*tree
)
1059 if (!pet_nested_any_in_pw_aff(pa
))
1062 if (pet_tree_has_continue(tree
))
1065 nparam
= isl_pw_aff_dim(pa
, isl_dim_param
);
1066 for (i
= 0; i
< nparam
; ++i
) {
1067 isl_id
*id
= isl_pw_aff_get_dim_id(pa
, isl_dim_param
, i
);
1071 if (!pet_nested_in_id(id
)) {
1076 expr
= pet_nested_extract_expr(id
);
1077 allowed
= pet_expr_get_type(expr
) == pet_expr_access
&&
1078 !is_assigned(expr
, tree
);
1080 pet_expr_free(expr
);
1090 /* Construct a pet_scop for a for tree with static affine initialization
1091 * and constant increment within the context "pc".
1092 * The domain of "pc" has already been extended with an (at this point
1093 * unbounded) inner loop iterator corresponding to the current for loop.
1095 * The condition is allowed to contain nested accesses, provided
1096 * they are not being written to inside the body of the loop.
1097 * Otherwise, or if the condition is otherwise non-affine, the for loop is
1098 * essentially treated as a while loop, with iteration domain
1099 * { [l,i] : i >= init }, where l refers to the outer loop iterators.
1101 * We extract a pet_scop for the body after intersecting the domain of "pc"
1103 * { [l,i] : i >= init and condition' }
1107 * { [l,i] : i <= init and condition' }
1109 * Where condition' is equal to condition if the latter is
1110 * a simple upper [lower] bound and a condition that is extended
1111 * to apply to all previous iterations otherwise.
1112 * Afterwards, the schedule of the pet_scop is extended with
1120 * If the condition is non-affine, then we drop the condition from the
1121 * iteration domain and instead create a separate statement
1122 * for evaluating the condition. The body is then filtered to depend
1123 * on the result of the condition evaluating to true on all iterations
1124 * up to the current iteration, while the evaluation the condition itself
1125 * is filtered to depend on the result of the condition evaluating to true
1126 * on all previous iterations.
1127 * The context of the scop representing the body is dropped
1128 * because we don't know how many times the body will be executed,
1131 * If the stride of the loop is not 1, then "i >= init" is replaced by
1133 * (exists a: i = init + stride * a and a >= 0)
1135 * If the loop iterator i is unsigned, then wrapping may occur.
1136 * We therefore use a virtual iterator instead that does not wrap.
1137 * However, the condition in the code applies
1138 * to the wrapped value, so we need to change condition(l,i)
1139 * into condition([l,i % 2^width]). Similarly, we replace all accesses
1140 * to the original iterator by the wrapping of the virtual iterator.
1141 * Note that there may be no need to perform this final wrapping
1142 * if the loop condition (after wrapping) satisfies certain conditions.
1143 * However, the is_simple_bound condition is not enough since it doesn't
1144 * check if there even is an upper bound.
1146 * Wrapping on unsigned iterators can be avoided entirely if
1147 * loop condition is simple, the loop iterator is incremented
1148 * [decremented] by one and the last value before wrapping cannot
1149 * possibly satisfy the loop condition.
1151 * Valid outer iterators for a for loop are those for which the initial
1152 * value itself, the increment on each domain iteration and
1153 * the condition on both the initial value and
1154 * the result of incrementing the iterator for each iteration of the domain
1156 * If the loop condition is non-affine, then we only consider validity
1157 * of the initial value.
1159 * If the body contains any break, then we keep track of it in "skip"
1160 * (if the skip condition is affine) or it is handled in scop_add_break
1161 * (if the skip condition is not affine).
1162 * Note that the affine break condition needs to be considered with
1163 * respect to previous iterations in the virtual domain (if any).
1165 static struct pet_scop
*scop_from_affine_for(__isl_keep pet_tree
*tree
,
1166 __isl_take isl_pw_aff
*init_val
, __isl_take isl_pw_aff
*pa_inc
,
1167 __isl_take isl_val
*inc
, __isl_take pet_context
*pc
,
1168 struct pet_state
*state
)
1172 isl_set
*cond
= NULL
;
1173 isl_set
*skip
= NULL
;
1174 isl_id
*id_test
= NULL
, *id_break_test
;
1175 struct pet_scop
*scop
, *scop_cond
= NULL
;
1182 int has_affine_break
;
1184 isl_map
*rev_wrap
= NULL
;
1185 isl_map
*init_val_map
;
1187 isl_set
*valid_init
;
1188 isl_set
*valid_cond
;
1189 isl_set
*valid_cond_init
;
1190 isl_set
*valid_cond_next
;
1192 pet_expr
*cond_expr
;
1193 pet_context
*pc_nested
;
1195 pos
= pet_context_dim(pc
) - 1;
1197 domain
= pet_context_get_domain(pc
);
1198 cond_expr
= pet_expr_copy(tree
->u
.l
.cond
);
1199 cond_expr
= pet_context_evaluate_expr(pc
, cond_expr
);
1200 pc_nested
= pet_context_copy(pc
);
1201 pc_nested
= pet_context_set_allow_nested(pc_nested
, 1);
1202 pa
= pet_expr_extract_affine_condition(cond_expr
, pc_nested
);
1203 pet_context_free(pc_nested
);
1204 pet_expr_free(cond_expr
);
1206 valid_inc
= isl_pw_aff_domain(pa_inc
);
1208 is_unsigned
= pet_expr_get_type_size(tree
->u
.l
.iv
) > 0;
1210 is_non_affine
= isl_pw_aff_involves_nan(pa
) ||
1211 !is_nested_allowed(pa
, tree
->u
.l
.body
);
1213 pa
= isl_pw_aff_free(pa
);
1215 valid_cond
= isl_pw_aff_domain(isl_pw_aff_copy(pa
));
1216 cond
= isl_pw_aff_non_zero_set(pa
);
1218 cond
= isl_set_universe(isl_set_get_space(domain
));
1220 valid_cond
= isl_set_coalesce(valid_cond
);
1221 is_one
= isl_val_is_one(inc
) || isl_val_is_negone(inc
);
1222 is_virtual
= is_unsigned
&&
1223 (!is_one
|| can_wrap(cond
, tree
->u
.l
.iv
, inc
));
1225 init_val_map
= isl_map_from_pw_aff(isl_pw_aff_copy(init_val
));
1226 init_val_map
= isl_map_equate(init_val_map
, isl_dim_in
, pos
,
1228 valid_cond_init
= enforce_subset(isl_map_domain(init_val_map
),
1229 isl_set_copy(valid_cond
));
1230 if (is_one
&& !is_virtual
) {
1233 isl_pw_aff_free(init_val
);
1234 pa
= pet_expr_extract_comparison(
1235 isl_val_is_pos(inc
) ? pet_op_ge
: pet_op_le
,
1236 tree
->u
.l
.iv
, tree
->u
.l
.init
, pc
);
1237 valid_init
= isl_pw_aff_domain(isl_pw_aff_copy(pa
));
1238 valid_init
= isl_set_eliminate(valid_init
, isl_dim_set
,
1239 isl_set_dim(domain
, isl_dim_set
) - 1, 1);
1240 cond
= isl_pw_aff_non_zero_set(pa
);
1241 domain
= isl_set_intersect(domain
, cond
);
1245 valid_init
= isl_pw_aff_domain(isl_pw_aff_copy(init_val
));
1246 strided
= strided_domain(init_val
, isl_val_copy(inc
));
1247 domain
= isl_set_intersect(domain
, strided
);
1251 isl_multi_aff
*wrap
;
1252 wrap
= compute_wrapping(isl_set_get_space(cond
), tree
->u
.l
.iv
);
1253 pc
= pet_context_preimage_domain(pc
, wrap
);
1254 rev_wrap
= isl_map_from_multi_aff(wrap
);
1255 rev_wrap
= isl_map_reverse(rev_wrap
);
1256 cond
= isl_set_apply(cond
, isl_map_copy(rev_wrap
));
1257 valid_cond
= isl_set_apply(valid_cond
, isl_map_copy(rev_wrap
));
1258 valid_inc
= isl_set_apply(valid_inc
, isl_map_copy(rev_wrap
));
1260 is_simple
= is_simple_bound(cond
, inc
);
1262 cond
= isl_set_gist(cond
, isl_set_copy(domain
));
1263 is_simple
= is_simple_bound(cond
, inc
);
1266 cond
= valid_for_each_iteration(cond
,
1267 isl_set_copy(domain
), isl_val_copy(inc
));
1268 cond
= isl_set_align_params(cond
, isl_set_get_space(domain
));
1269 domain
= isl_set_intersect(domain
, cond
);
1270 sched
= map_to_last(pc
);
1271 if (isl_val_is_neg(inc
))
1272 sched
= isl_aff_neg(sched
);
1274 valid_cond_next
= valid_on_next(valid_cond
, isl_set_copy(domain
),
1276 valid_inc
= enforce_subset(isl_set_copy(domain
), valid_inc
);
1278 pc
= pet_context_intersect_domain(pc
, isl_set_copy(domain
));
1280 if (is_non_affine
) {
1282 isl_multi_pw_aff
*test_index
;
1283 space
= isl_set_get_space(domain
);
1284 test_index
= pet_create_test_index(space
, state
->n_test
++);
1285 scop_cond
= scop_from_non_affine_condition(
1286 pet_expr_copy(tree
->u
.l
.cond
), state
->n_stmt
++,
1287 isl_multi_pw_aff_copy(test_index
),
1288 pet_tree_get_loc(tree
), pc
);
1289 id_test
= isl_multi_pw_aff_get_tuple_id(test_index
,
1291 scop_cond
= pet_scop_add_boolean_array(scop_cond
,
1292 isl_set_copy(domain
), test_index
,
1294 scop_cond
= pet_scop_prefix(scop_cond
, 0);
1295 scop_cond
= pet_scop_embed(scop_cond
, isl_set_copy(domain
),
1296 isl_aff_copy(sched
));
1299 scop
= scop_from_tree(tree
->u
.l
.body
, pc
, state
);
1300 has_affine_break
= scop
&&
1301 pet_scop_has_affine_skip(scop
, pet_skip_later
);
1302 if (has_affine_break
)
1303 skip
= pet_scop_get_affine_skip_domain(scop
, pet_skip_later
);
1304 has_var_break
= scop
&& pet_scop_has_var_skip(scop
, pet_skip_later
);
1306 id_break_test
= pet_scop_get_skip_id(scop
, pet_skip_later
);
1307 if (is_non_affine
) {
1308 scop
= pet_scop_reset_context(scop
);
1309 scop
= pet_scop_prefix(scop
, 1);
1311 scop
= pet_scop_embed(scop
, isl_set_copy(domain
), sched
);
1312 scop
= pet_scop_resolve_nested(scop
);
1313 if (has_affine_break
) {
1314 domain
= apply_affine_break(domain
, skip
, isl_val_sgn(inc
),
1315 is_virtual
, rev_wrap
);
1316 scop
= pet_scop_intersect_domain_prefix(scop
,
1317 isl_set_copy(domain
));
1319 isl_map_free(rev_wrap
);
1321 scop
= scop_add_break(scop
, id_break_test
, isl_set_copy(domain
),
1323 if (is_non_affine
) {
1324 scop
= scop_add_while(scop_cond
, scop
, id_test
, domain
,
1326 isl_set_free(valid_inc
);
1328 valid_inc
= isl_set_intersect(valid_inc
, valid_cond_next
);
1329 valid_inc
= isl_set_intersect(valid_inc
, valid_cond_init
);
1330 valid_inc
= isl_set_project_out(valid_inc
, isl_dim_set
, pos
, 1);
1331 scop
= pet_scop_restrict_context(scop
, valid_inc
);
1332 isl_set_free(domain
);
1337 valid_init
= isl_set_project_out(valid_init
, isl_dim_set
, pos
, 1);
1338 scop
= pet_scop_restrict_context(scop
, valid_init
);
1340 pet_context_free(pc
);
1344 /* Construct a pet_scop for a for statement within the context of "pc".
1346 * We update the context to reflect the writes to the loop variable and
1347 * the writes inside the body.
1349 * Then we check if the initialization of the for loop
1350 * is a static affine value and the increment is a constant.
1351 * If so, we construct the pet_scop using scop_from_affine_for.
1352 * Otherwise, we treat the for loop as a while loop
1353 * in scop_from_non_affine_for.
1355 * Note that the initialization and the increment are extracted
1356 * in a context where the current loop iterator has been added
1357 * to the context. If these turn out not be affine, then we
1358 * have reconstruct the body context without an assignment
1359 * to this loop iterator, as this variable will then not be
1360 * treated as a dimension of the iteration domain, but as any
1363 static struct pet_scop
*scop_from_for(__isl_keep pet_tree
*tree
,
1364 __isl_keep pet_context
*init_pc
, struct pet_state
*state
)
1368 isl_pw_aff
*pa_inc
, *init_val
;
1369 pet_context
*pc
, *pc_init_val
;
1374 iv
= pet_expr_access_get_id(tree
->u
.l
.iv
);
1375 pc
= pet_context_copy(init_pc
);
1376 pc
= pet_context_add_inner_iterator(pc
, iv
);
1377 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.l
.body
);
1379 pc_init_val
= pet_context_copy(pc
);
1380 pc_init_val
= pet_context_clear_value(pc_init_val
, isl_id_copy(iv
));
1381 init_val
= pet_expr_extract_affine(tree
->u
.l
.init
, pc_init_val
);
1382 pet_context_free(pc_init_val
);
1383 pa_inc
= pet_expr_extract_affine(tree
->u
.l
.inc
, pc
);
1384 inc
= pet_extract_cst(pa_inc
);
1385 if (!pa_inc
|| !init_val
|| !inc
)
1387 if (!isl_pw_aff_involves_nan(pa_inc
) &&
1388 !isl_pw_aff_involves_nan(init_val
) && !isl_val_is_nan(inc
))
1389 return scop_from_affine_for(tree
, init_val
, pa_inc
, inc
,
1392 isl_pw_aff_free(pa_inc
);
1393 isl_pw_aff_free(init_val
);
1395 pet_context_free(pc
);
1397 pc
= pet_context_copy(init_pc
);
1398 pc
= pet_context_add_infinite_loop(pc
);
1399 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.l
.body
);
1400 return scop_from_non_affine_for(tree
, init_pc
, pc
, state
);
1402 isl_pw_aff_free(pa_inc
);
1403 isl_pw_aff_free(init_val
);
1405 pet_context_free(pc
);
1409 /* Check whether "expr" is an affine constraint within the context "pc".
1411 static int is_affine_condition(__isl_keep pet_expr
*expr
,
1412 __isl_keep pet_context
*pc
)
1417 pa
= pet_expr_extract_affine_condition(expr
, pc
);
1420 is_affine
= !isl_pw_aff_involves_nan(pa
);
1421 isl_pw_aff_free(pa
);
1426 /* Check if the given if statement is a conditional assignement
1427 * with a non-affine condition.
1429 * In particular we check if "stmt" is of the form
1436 * where the condition is non-affine and a is some array or scalar access.
1438 static int is_conditional_assignment(__isl_keep pet_tree
*tree
,
1439 __isl_keep pet_context
*pc
)
1443 pet_expr
*expr1
, *expr2
;
1445 ctx
= pet_tree_get_ctx(tree
);
1446 if (!pet_options_get_detect_conditional_assignment(ctx
))
1448 if (tree
->type
!= pet_tree_if_else
)
1450 if (tree
->u
.i
.then_body
->type
!= pet_tree_expr
)
1452 if (tree
->u
.i
.else_body
->type
!= pet_tree_expr
)
1454 expr1
= tree
->u
.i
.then_body
->u
.e
.expr
;
1455 expr2
= tree
->u
.i
.else_body
->u
.e
.expr
;
1456 if (pet_expr_get_type(expr1
) != pet_expr_op
)
1458 if (pet_expr_get_type(expr2
) != pet_expr_op
)
1460 if (pet_expr_op_get_type(expr1
) != pet_op_assign
)
1462 if (pet_expr_op_get_type(expr2
) != pet_op_assign
)
1464 expr1
= pet_expr_get_arg(expr1
, 0);
1465 expr2
= pet_expr_get_arg(expr2
, 0);
1466 equal
= pet_expr_is_equal(expr1
, expr2
);
1467 pet_expr_free(expr1
);
1468 pet_expr_free(expr2
);
1469 if (equal
< 0 || !equal
)
1471 if (is_affine_condition(tree
->u
.i
.cond
, pc
))
1477 /* Given that "tree" is of the form
1484 * where a is some array or scalar access, construct a pet_scop
1485 * corresponding to this conditional assignment within the context "pc".
1487 * The constructed pet_scop then corresponds to the expression
1489 * a = condition ? f(...) : g(...)
1491 * All access relations in f(...) are intersected with condition
1492 * while all access relation in g(...) are intersected with the complement.
1494 static struct pet_scop
*scop_from_conditional_assignment(
1495 __isl_keep pet_tree
*tree
, __isl_take pet_context
*pc
,
1496 struct pet_state
*state
)
1500 isl_set
*cond
, *comp
;
1501 isl_multi_pw_aff
*index
;
1502 pet_expr
*expr1
, *expr2
;
1503 pet_expr
*pe_cond
, *pe_then
, *pe_else
, *pe
, *pe_write
;
1504 pet_context
*pc_nested
;
1505 struct pet_scop
*scop
;
1507 pe_cond
= pet_expr_copy(tree
->u
.i
.cond
);
1508 pe_cond
= pet_context_evaluate_expr(pc
, pe_cond
);
1509 pc_nested
= pet_context_copy(pc
);
1510 pc_nested
= pet_context_set_allow_nested(pc_nested
, 1);
1511 pa
= pet_expr_extract_affine_condition(pe_cond
, pc_nested
);
1512 pet_context_free(pc_nested
);
1513 pet_expr_free(pe_cond
);
1514 cond
= isl_pw_aff_non_zero_set(isl_pw_aff_copy(pa
));
1515 comp
= isl_pw_aff_zero_set(isl_pw_aff_copy(pa
));
1516 index
= isl_multi_pw_aff_from_pw_aff(pa
);
1518 expr1
= tree
->u
.i
.then_body
->u
.e
.expr
;
1519 expr2
= tree
->u
.i
.else_body
->u
.e
.expr
;
1521 pe_cond
= pet_expr_from_index(index
);
1523 pe_then
= pet_expr_get_arg(expr1
, 1);
1524 pe_then
= pet_context_evaluate_expr(pc
, pe_then
);
1525 pe_then
= pet_expr_restrict(pe_then
, cond
);
1526 pe_else
= pet_expr_get_arg(expr2
, 1);
1527 pe_else
= pet_context_evaluate_expr(pc
, pe_else
);
1528 pe_else
= pet_expr_restrict(pe_else
, comp
);
1529 pe_write
= pet_expr_get_arg(expr1
, 0);
1530 pe_write
= pet_context_evaluate_expr(pc
, pe_write
);
1532 pe
= pet_expr_new_ternary(pe_cond
, pe_then
, pe_else
);
1533 type_size
= pet_expr_get_type_size(pe_write
);
1534 pe
= pet_expr_new_binary(type_size
, pet_op_assign
, pe_write
, pe
);
1536 scop
= scop_from_evaluated_expr(pe
, NULL
, state
->n_stmt
++,
1537 pet_tree_get_loc(tree
), pc
);
1539 pet_context_free(pc
);
1544 /* Construct a pet_scop for a non-affine if statement within the context "pc".
1546 * We create a separate statement that writes the result
1547 * of the non-affine condition to a virtual scalar.
1548 * A constraint requiring the value of this virtual scalar to be one
1549 * is added to the iteration domains of the then branch.
1550 * Similarly, a constraint requiring the value of this virtual scalar
1551 * to be zero is added to the iteration domains of the else branch, if any.
1552 * We adjust the schedules to ensure that the virtual scalar is written
1553 * before it is read.
1555 * If there are any breaks or continues in the then and/or else
1556 * branches, then we may have to compute a new skip condition.
1557 * This is handled using a pet_skip_info object.
1558 * On initialization, the object checks if skip conditions need
1559 * to be computed. If so, it does so in pet_skip_info_if_extract_index and
1560 * adds them in pet_skip_info_if_add.
1562 static struct pet_scop
*scop_from_non_affine_if(__isl_keep pet_tree
*tree
,
1563 __isl_take pet_context
*pc
, struct pet_state
*state
)
1568 isl_multi_pw_aff
*test_index
;
1569 struct pet_skip_info skip
;
1570 struct pet_scop
*scop
, *scop_then
, *scop_else
= NULL
;
1572 has_else
= tree
->type
== pet_tree_if_else
;
1574 space
= pet_context_get_space(pc
);
1575 test_index
= pet_create_test_index(space
, state
->n_test
++);
1576 scop
= scop_from_non_affine_condition(pet_expr_copy(tree
->u
.i
.cond
),
1577 state
->n_stmt
++, isl_multi_pw_aff_copy(test_index
),
1578 pet_tree_get_loc(tree
), pc
);
1579 domain
= pet_context_get_domain(pc
);
1580 scop
= pet_scop_add_boolean_array(scop
, domain
,
1581 isl_multi_pw_aff_copy(test_index
), state
->int_size
);
1583 scop_then
= scop_from_tree(tree
->u
.i
.then_body
, pc
, state
);
1585 scop_else
= scop_from_tree(tree
->u
.i
.else_body
, pc
, state
);
1587 pet_skip_info_if_init(&skip
, state
->ctx
, scop_then
, scop_else
,
1589 pet_skip_info_if_extract_index(&skip
, test_index
, pc
, state
);
1591 scop
= pet_scop_prefix(scop
, 0);
1592 scop_then
= pet_scop_prefix(scop_then
, 1);
1593 scop_then
= pet_scop_filter(scop_then
,
1594 isl_multi_pw_aff_copy(test_index
), 1);
1596 scop_else
= pet_scop_prefix(scop_else
, 1);
1597 scop_else
= pet_scop_filter(scop_else
, test_index
, 0);
1598 scop_then
= pet_scop_add_par(state
->ctx
, scop_then
, scop_else
);
1600 isl_multi_pw_aff_free(test_index
);
1602 scop
= pet_scop_add_seq(state
->ctx
, scop
, scop_then
);
1604 scop
= pet_skip_info_if_add(&skip
, scop
, 2);
1606 pet_context_free(pc
);
1610 /* Construct a pet_scop for an affine if statement within the context "pc".
1612 * The condition is added to the iteration domains of the then branch,
1613 * while the opposite of the condition in added to the iteration domains
1614 * of the else branch, if any.
1616 * If there are any breaks or continues in the then and/or else
1617 * branches, then we may have to compute a new skip condition.
1618 * This is handled using a pet_skip_info_if object.
1619 * On initialization, the object checks if skip conditions need
1620 * to be computed. If so, it does so in pet_skip_info_if_extract_cond and
1621 * adds them in pet_skip_info_if_add.
1623 static struct pet_scop
*scop_from_affine_if(__isl_keep pet_tree
*tree
,
1624 __isl_take isl_pw_aff
*cond
, __isl_take pet_context
*pc
,
1625 struct pet_state
*state
)
1629 isl_set
*set
, *complement
;
1631 struct pet_skip_info skip
;
1632 struct pet_scop
*scop
, *scop_then
, *scop_else
= NULL
;
1633 pet_context
*pc_body
;
1635 ctx
= pet_tree_get_ctx(tree
);
1637 has_else
= tree
->type
== pet_tree_if_else
;
1639 valid
= isl_pw_aff_domain(isl_pw_aff_copy(cond
));
1640 set
= isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond
));
1642 pc_body
= pet_context_copy(pc
);
1643 pc_body
= pet_context_intersect_domain(pc_body
, isl_set_copy(set
));
1644 scop_then
= scop_from_tree(tree
->u
.i
.then_body
, pc_body
, state
);
1645 pet_context_free(pc_body
);
1647 pc_body
= pet_context_copy(pc
);
1648 complement
= isl_set_copy(valid
);
1649 complement
= isl_set_subtract(valid
, isl_set_copy(set
));
1650 pc_body
= pet_context_intersect_domain(pc_body
,
1651 isl_set_copy(complement
));
1652 scop_else
= scop_from_tree(tree
->u
.i
.else_body
, pc_body
, state
);
1653 pet_context_free(pc_body
);
1656 pet_skip_info_if_init(&skip
, ctx
, scop_then
, scop_else
, has_else
, 1);
1657 pet_skip_info_if_extract_cond(&skip
, cond
, pc
, state
);
1658 isl_pw_aff_free(cond
);
1660 scop
= pet_scop_restrict(scop_then
, set
);
1663 scop_else
= pet_scop_restrict(scop_else
, complement
);
1664 scop
= pet_scop_add_par(ctx
, scop
, scop_else
);
1666 scop
= pet_scop_resolve_nested(scop
);
1667 scop
= pet_scop_restrict_context(scop
, valid
);
1669 if (pet_skip_info_has_skip(&skip
))
1670 scop
= pet_scop_prefix(scop
, 0);
1671 scop
= pet_skip_info_if_add(&skip
, scop
, 1);
1673 pet_context_free(pc
);
1677 /* Construct a pet_scop for an if statement within the context "pc".
1679 * If the condition fits the pattern of a conditional assignment,
1680 * then it is handled by scop_from_conditional_assignment.
1682 * Otherwise, we check if the condition is affine.
1683 * If so, we construct the scop in scop_from_affine_if.
1684 * Otherwise, we construct the scop in scop_from_non_affine_if.
1686 * We allow the condition to be dynamic, i.e., to refer to
1687 * scalars or array elements that may be written to outside
1688 * of the given if statement. These nested accesses are then represented
1689 * as output dimensions in the wrapping iteration domain.
1690 * If it is also written _inside_ the then or else branch, then
1691 * we treat the condition as non-affine.
1692 * As explained in extract_non_affine_if, this will introduce
1693 * an extra statement.
1694 * For aesthetic reasons, we want this statement to have a statement
1695 * number that is lower than those of the then and else branches.
1696 * In order to evaluate if we will need such a statement, however, we
1697 * first construct scops for the then and else branches.
1698 * We therefore reserve a statement number if we might have to
1699 * introduce such an extra statement.
1701 static struct pet_scop
*scop_from_if(__isl_keep pet_tree
*tree
,
1702 __isl_keep pet_context
*pc
, struct pet_state
*state
)
1706 pet_expr
*cond_expr
;
1707 pet_context
*pc_nested
;
1712 has_else
= tree
->type
== pet_tree_if_else
;
1714 pc
= pet_context_copy(pc
);
1715 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.i
.then_body
);
1717 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.i
.else_body
);
1719 if (is_conditional_assignment(tree
, pc
))
1720 return scop_from_conditional_assignment(tree
, pc
, state
);
1722 cond_expr
= pet_expr_copy(tree
->u
.i
.cond
);
1723 cond_expr
= pet_context_evaluate_expr(pc
, cond_expr
);
1724 pc_nested
= pet_context_copy(pc
);
1725 pc_nested
= pet_context_set_allow_nested(pc_nested
, 1);
1726 cond
= pet_expr_extract_affine_condition(cond_expr
, pc_nested
);
1727 pet_context_free(pc_nested
);
1728 pet_expr_free(cond_expr
);
1731 pet_context_free(pc
);
1735 if (isl_pw_aff_involves_nan(cond
)) {
1736 isl_pw_aff_free(cond
);
1737 return scop_from_non_affine_if(tree
, pc
, state
);
1740 if ((!is_nested_allowed(cond
, tree
->u
.i
.then_body
) ||
1741 (has_else
&& !is_nested_allowed(cond
, tree
->u
.i
.else_body
)))) {
1742 isl_pw_aff_free(cond
);
1743 return scop_from_non_affine_if(tree
, pc
, state
);
1746 return scop_from_affine_if(tree
, cond
, pc
, state
);
1749 /* Return a one-dimensional multi piecewise affine expression that is equal
1750 * to the constant 1 and is defined over the given domain.
1752 static __isl_give isl_multi_pw_aff
*one_mpa(__isl_take isl_space
*space
)
1754 isl_local_space
*ls
;
1757 ls
= isl_local_space_from_space(space
);
1758 aff
= isl_aff_zero_on_domain(ls
);
1759 aff
= isl_aff_set_constant_si(aff
, 1);
1761 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1764 /* Construct a pet_scop for a continue statement with the given domain space.
1766 * We simply create an empty scop with a universal pet_skip_now
1767 * skip condition. This skip condition will then be taken into
1768 * account by the enclosing loop construct, possibly after
1769 * being incorporated into outer skip conditions.
1771 static struct pet_scop
*scop_from_continue(__isl_keep pet_tree
*tree
,
1772 __isl_take isl_space
*space
)
1774 struct pet_scop
*scop
;
1776 scop
= pet_scop_empty(isl_space_copy(space
));
1778 scop
= pet_scop_set_skip(scop
, pet_skip_now
, one_mpa(space
));
1783 /* Construct a pet_scop for a break statement with the given domain space.
1785 * We simply create an empty scop with both a universal pet_skip_now
1786 * skip condition and a universal pet_skip_later skip condition.
1787 * These skip conditions will then be taken into
1788 * account by the enclosing loop construct, possibly after
1789 * being incorporated into outer skip conditions.
1791 static struct pet_scop
*scop_from_break(__isl_keep pet_tree
*tree
,
1792 __isl_take isl_space
*space
)
1794 struct pet_scop
*scop
;
1795 isl_multi_pw_aff
*skip
;
1797 scop
= pet_scop_empty(isl_space_copy(space
));
1799 skip
= one_mpa(space
);
1800 scop
= pet_scop_set_skip(scop
, pet_skip_now
,
1801 isl_multi_pw_aff_copy(skip
));
1802 scop
= pet_scop_set_skip(scop
, pet_skip_later
, skip
);
1807 /* Extract a clone of the kill statement in "scop".
1808 * The domain of the clone is given by "domain".
1809 * "scop" is expected to have been created from a DeclStmt
1810 * and should have the kill as its first statement.
1812 static struct pet_scop
*extract_kill(__isl_keep isl_set
*domain
,
1813 struct pet_scop
*scop
, struct pet_state
*state
)
1816 struct pet_stmt
*stmt
;
1817 isl_multi_pw_aff
*index
;
1819 pet_expr
*expr
, *arg
;
1822 if (!domain
|| !scop
)
1824 if (scop
->n_stmt
< 1)
1825 isl_die(isl_set_get_ctx(domain
), isl_error_internal
,
1826 "expecting at least one statement", return NULL
);
1827 stmt
= scop
->stmts
[0];
1828 if (!pet_stmt_is_kill(stmt
))
1829 isl_die(isl_set_get_ctx(domain
), isl_error_internal
,
1830 "expecting kill statement", return NULL
);
1832 expr
= pet_tree_expr_get_expr(stmt
->body
);
1833 arg
= pet_expr_get_arg(expr
, 0);
1834 pet_expr_free(expr
);
1835 index
= pet_expr_access_get_index(arg
);
1836 access
= pet_expr_access_get_access(arg
);
1838 index
= isl_multi_pw_aff_reset_tuple_id(index
, isl_dim_in
);
1839 access
= isl_map_reset_tuple_id(access
, isl_dim_in
);
1840 kill
= pet_expr_kill_from_access_and_index(access
, index
);
1841 tree
= pet_tree_new_expr(kill
);
1842 tree
= pet_tree_set_loc(tree
, pet_loc_copy(stmt
->loc
));
1843 stmt
= pet_stmt_from_pet_tree(isl_set_copy(domain
),
1844 state
->n_stmt
++, tree
);
1845 return pet_scop_from_pet_stmt(isl_set_get_space(domain
), stmt
);
1848 /* Does "tree" represent an assignment to a variable?
1850 * The assignment may be one of
1851 * - a declaration with initialization
1852 * - an expression with a top-level assignment operator
1854 static int is_assignment(__isl_keep pet_tree
*tree
)
1858 if (tree
->type
== pet_tree_decl_init
)
1860 return pet_tree_is_assign(tree
);
1863 /* Update "pc" by taking into account the assignment performed by "tree",
1864 * where "tree" satisfies is_assignment.
1866 * In particular, if the lhs of the assignment is a scalar variable and
1867 * if the rhs is an affine expression, then keep track of this value in "pc"
1868 * so that we can plug it in when we later come across the same variable.
1870 * Any previously assigned value to the variable has already been removed
1871 * by scop_handle_writes.
1873 static __isl_give pet_context
*handle_assignment(__isl_take pet_context
*pc
,
1874 __isl_keep pet_tree
*tree
)
1876 pet_expr
*var
, *val
;
1880 if (pet_tree_get_type(tree
) == pet_tree_decl_init
) {
1881 var
= pet_tree_decl_get_var(tree
);
1882 val
= pet_tree_decl_get_init(tree
);
1885 expr
= pet_tree_expr_get_expr(tree
);
1886 var
= pet_expr_get_arg(expr
, 0);
1887 val
= pet_expr_get_arg(expr
, 1);
1888 pet_expr_free(expr
);
1891 if (!pet_expr_is_scalar_access(var
)) {
1897 pa
= pet_expr_extract_affine(val
, pc
);
1899 pc
= pet_context_free(pc
);
1901 if (!isl_pw_aff_involves_nan(pa
)) {
1902 id
= pet_expr_access_get_id(var
);
1903 pc
= pet_context_set_value(pc
, id
, pa
);
1905 isl_pw_aff_free(pa
);
1913 /* Mark all arrays in "scop" as being exposed.
1915 static struct pet_scop
*mark_exposed(struct pet_scop
*scop
)
1921 for (i
= 0; i
< scop
->n_array
; ++i
)
1922 scop
->arrays
[i
]->exposed
= 1;
1926 /* Given that "scop" has an affine skip condition of type pet_skip_now,
1927 * apply this skip condition to the domain of "pc".
1928 * That is, remove the elements satisfying the skip condition from
1929 * the domain of "pc".
1931 static __isl_give pet_context
*apply_affine_continue(__isl_take pet_context
*pc
,
1932 struct pet_scop
*scop
)
1934 isl_set
*domain
, *skip
;
1936 skip
= pet_scop_get_affine_skip_domain(scop
, pet_skip_now
);
1937 domain
= pet_context_get_domain(pc
);
1938 domain
= isl_set_subtract(domain
, skip
);
1939 pc
= pet_context_intersect_domain(pc
, domain
);
1944 /* Try and construct a pet_scop corresponding to (part of)
1945 * a sequence of statements within the context "pc".
1947 * After extracting a statement, we update "pc"
1948 * based on the top-level assignments in the statement
1949 * so that we can exploit them in subsequent statements in the same block.
1951 * If there are any breaks or continues in the individual statements,
1952 * then we may have to compute a new skip condition.
1953 * This is handled using a pet_skip_info object.
1954 * On initialization, the object checks if skip conditions need
1955 * to be computed. If so, it does so in pet_skip_info_seq_extract and
1956 * adds them in pet_skip_info_seq_add.
1958 * If "block" is set, then we need to insert kill statements at
1959 * the end of the block for any array that has been declared by
1960 * one of the statements in the sequence. Each of these declarations
1961 * results in the construction of a kill statement at the place
1962 * of the declaration, so we simply collect duplicates of
1963 * those kill statements and append these duplicates to the constructed scop.
1965 * If "block" is not set, then any array declared by one of the statements
1966 * in the sequence is marked as being exposed.
1968 * If autodetect is set, then we allow the extraction of only a subrange
1969 * of the sequence of statements. However, if there is at least one statement
1970 * for which we could not construct a scop and the final range contains
1971 * either no statements or at least one kill, then we discard the entire
1974 static struct pet_scop
*scop_from_block(__isl_keep pet_tree
*tree
,
1975 __isl_keep pet_context
*pc
, struct pet_state
*state
)
1981 struct pet_scop
*scop
, *kills
;
1983 ctx
= pet_tree_get_ctx(tree
);
1985 space
= pet_context_get_space(pc
);
1986 domain
= pet_context_get_domain(pc
);
1987 pc
= pet_context_copy(pc
);
1988 scop
= pet_scop_empty(isl_space_copy(space
));
1989 kills
= pet_scop_empty(space
);
1990 for (i
= 0; i
< tree
->u
.b
.n
; ++i
) {
1991 struct pet_scop
*scop_i
;
1993 if (pet_scop_has_affine_skip(scop
, pet_skip_now
))
1994 pc
= apply_affine_continue(pc
, scop
);
1995 scop_i
= scop_from_tree(tree
->u
.b
.child
[i
], pc
, state
);
1996 pc
= scop_handle_writes(scop_i
, pc
);
1997 if (is_assignment(tree
->u
.b
.child
[i
]))
1998 pc
= handle_assignment(pc
, tree
->u
.b
.child
[i
]);
1999 struct pet_skip_info skip
;
2000 pet_skip_info_seq_init(&skip
, ctx
, scop
, scop_i
);
2001 pet_skip_info_seq_extract(&skip
, pc
, state
);
2002 if (pet_skip_info_has_skip(&skip
))
2003 scop_i
= pet_scop_prefix(scop_i
, 0);
2004 if (scop_i
&& pet_tree_is_decl(tree
->u
.b
.child
[i
])) {
2005 if (tree
->u
.b
.block
) {
2006 struct pet_scop
*kill
;
2007 kill
= extract_kill(domain
, scop_i
, state
);
2008 kills
= pet_scop_add_par(ctx
, kills
, kill
);
2010 scop_i
= mark_exposed(scop_i
);
2012 scop_i
= pet_scop_prefix(scop_i
, i
);
2013 scop
= pet_scop_add_seq(ctx
, scop
, scop_i
);
2015 scop
= pet_skip_info_seq_add(&skip
, scop
, i
);
2020 isl_set_free(domain
);
2022 kills
= pet_scop_prefix(kills
, tree
->u
.b
.n
);
2023 scop
= pet_scop_add_seq(ctx
, scop
, kills
);
2025 pet_context_free(pc
);
2030 /* Construct a pet_scop that corresponds to the pet_tree "tree"
2031 * within the context "pc" by calling the appropriate function
2032 * based on the type of "tree".
2034 static struct pet_scop
*scop_from_tree(__isl_keep pet_tree
*tree
,
2035 __isl_keep pet_context
*pc
, struct pet_state
*state
)
2040 switch (tree
->type
) {
2041 case pet_tree_error
:
2043 case pet_tree_block
:
2044 return scop_from_block(tree
, pc
, state
);
2045 case pet_tree_break
:
2046 return scop_from_break(tree
, pet_context_get_space(pc
));
2047 case pet_tree_continue
:
2048 return scop_from_continue(tree
, pet_context_get_space(pc
));
2050 case pet_tree_decl_init
:
2051 return scop_from_decl(tree
, pc
, state
);
2053 return scop_from_expr(pet_expr_copy(tree
->u
.e
.expr
),
2054 isl_id_copy(tree
->label
),
2056 pet_tree_get_loc(tree
), pc
);
2058 case pet_tree_if_else
:
2059 return scop_from_if(tree
, pc
, state
);
2061 return scop_from_for(tree
, pc
, state
);
2062 case pet_tree_while
:
2063 return scop_from_while(tree
, pc
, state
);
2064 case pet_tree_infinite_loop
:
2065 return scop_from_infinite_for(tree
, pc
, state
);
2068 isl_die(tree
->ctx
, isl_error_internal
, "unhandled type",
2072 /* Construct a pet_scop that corresponds to the pet_tree "tree".
2073 * "int_size" is the number of bytes need to represent an integer.
2074 * "extract_array" is a callback that we can use to create a pet_array
2075 * that corresponds to the variable accessed by an expression.
2077 * Initialize the global state, construct a context and then
2078 * construct the pet_scop by recursively visiting the tree.
2080 struct pet_scop
*pet_scop_from_pet_tree(__isl_take pet_tree
*tree
, int int_size
,
2081 struct pet_array
*(*extract_array
)(__isl_keep pet_expr
*access
,
2082 __isl_keep pet_context
*pc
, void *user
), void *user
,
2083 __isl_keep pet_context
*pc
)
2085 struct pet_scop
*scop
;
2086 struct pet_state state
= { 0 };
2091 state
.ctx
= pet_tree_get_ctx(tree
);
2092 state
.int_size
= int_size
;
2093 state
.extract_array
= extract_array
;
2096 scop
= scop_from_tree(tree
, pc
, &state
);
2097 scop
= pet_scop_set_loc(scop
, pet_tree_get_loc(tree
));
2099 pet_tree_free(tree
);
2102 scop
->context
= isl_set_params(scop
->context
);