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 /* Wrapper around pet_expr_resolve_assume
72 * for use as a callback to pet_tree_map_expr.
74 static __isl_give pet_expr
*resolve_assume(__isl_take pet_expr
*expr
,
77 pet_context
*pc
= user
;
79 return pet_expr_resolve_assume(expr
, pc
);
82 /* Check if any expression inside "tree" is an assume expression and
83 * if its single argument can be converted to an affine expression
84 * in the context of "pc".
85 * If so, replace the argument by the affine expression.
87 __isl_give pet_tree
*pet_tree_resolve_assume(__isl_take pet_tree
*tree
,
88 __isl_keep pet_context
*pc
)
90 return pet_tree_map_expr(tree
, &resolve_assume
, pc
);
93 /* Convert a pet_tree to a pet_scop with one statement within the context "pc".
94 * "tree" has already been evaluated in the context of "pc".
95 * This mainly involves resolving nested expression parameters
96 * and setting the name of the iteration space.
97 * The name is given by tree->label if it is non-NULL. Otherwise,
98 * it is of the form S_<stmt_nr>.
100 static struct pet_scop
*scop_from_evaluated_tree(__isl_take pet_tree
*tree
,
101 int stmt_nr
, __isl_keep pet_context
*pc
)
107 space
= pet_context_get_space(pc
);
109 tree
= pet_tree_resolve_nested(tree
, space
);
110 tree
= pet_tree_resolve_assume(tree
, pc
);
112 domain
= pet_context_get_domain(pc
);
113 ps
= pet_stmt_from_pet_tree(domain
, stmt_nr
, tree
);
114 return pet_scop_from_pet_stmt(space
, ps
);
117 /* Convert a top-level pet_expr to a pet_scop with one statement
118 * within the context "pc".
119 * "expr" has already been evaluated in the context of "pc".
120 * We construct a pet_tree from "expr" and continue with
121 * scop_from_evaluated_tree.
122 * The name is of the form S_<stmt_nr>.
123 * The location of the statement is set to "loc".
125 static struct pet_scop
*scop_from_evaluated_expr(__isl_take pet_expr
*expr
,
126 int stmt_nr
, __isl_take pet_loc
*loc
, __isl_keep pet_context
*pc
)
130 tree
= pet_tree_new_expr(expr
);
131 tree
= pet_tree_set_loc(tree
, loc
);
132 return scop_from_evaluated_tree(tree
, stmt_nr
, pc
);
135 /* Convert a pet_tree to a pet_scop with one statement within the context "pc".
136 * "tree" has not yet been evaluated in the context of "pc".
137 * We evaluate "tree" in the context of "pc" and continue with
138 * scop_from_evaluated_tree.
139 * The statement name is given by tree->label if it is non-NULL. Otherwise,
140 * it is of the form S_<stmt_nr>.
142 static struct pet_scop
*scop_from_unevaluated_tree(__isl_take pet_tree
*tree
,
143 int stmt_nr
, __isl_keep pet_context
*pc
)
145 tree
= pet_context_evaluate_tree(pc
, tree
);
146 return scop_from_evaluated_tree(tree
, stmt_nr
, pc
);
149 /* Convert a top-level pet_expr to a pet_scop with one statement
150 * within the context "pc", where "expr" has not yet been evaluated
151 * in the context of "pc".
152 * We construct a pet_tree from "expr" and continue with
153 * scop_from_unevaluated_tree.
154 * The statement name is of the form S_<stmt_nr>.
155 * The location of the statement is set to "loc".
157 static struct pet_scop
*scop_from_expr(__isl_take pet_expr
*expr
,
158 int stmt_nr
, __isl_take pet_loc
*loc
, __isl_keep pet_context
*pc
)
162 tree
= pet_tree_new_expr(expr
);
163 tree
= pet_tree_set_loc(tree
, loc
);
164 return scop_from_unevaluated_tree(tree
, stmt_nr
, pc
);
167 /* Construct a pet_scop with a single statement killing the entire
169 * The location of the statement is set to "loc".
171 static struct pet_scop
*kill(__isl_take pet_loc
*loc
, struct pet_array
*array
,
172 __isl_keep pet_context
*pc
, struct pet_state
*state
)
177 isl_multi_pw_aff
*index
;
180 struct pet_scop
*scop
;
184 ctx
= isl_set_get_ctx(array
->extent
);
185 access
= isl_map_from_range(isl_set_copy(array
->extent
));
186 id
= isl_set_get_tuple_id(array
->extent
);
187 space
= isl_space_alloc(ctx
, 0, 0, 0);
188 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
189 index
= isl_multi_pw_aff_zero(space
);
190 expr
= pet_expr_kill_from_access_and_index(access
, index
);
191 return scop_from_expr(expr
, state
->n_stmt
++, loc
, pc
);
197 /* Construct and return a pet_array corresponding to the variable
198 * accessed by "access" by calling the extract_array callback.
200 static struct pet_array
*extract_array(__isl_keep pet_expr
*access
,
201 __isl_keep pet_context
*pc
, struct pet_state
*state
)
203 return state
->extract_array(access
, pc
, state
->user
);
206 /* Construct a pet_scop for a (single) variable declaration
207 * within the context "pc".
209 * The scop contains the variable being declared (as an array)
210 * and a statement killing the array.
212 * If the declaration comes with an initialization, then the scop
213 * also contains an assignment to the variable.
215 static struct pet_scop
*scop_from_decl(__isl_keep pet_tree
*tree
,
216 __isl_keep pet_context
*pc
, struct pet_state
*state
)
220 struct pet_array
*array
;
221 struct pet_scop
*scop_decl
, *scop
;
222 pet_expr
*lhs
, *rhs
, *pe
;
224 array
= extract_array(tree
->u
.d
.var
, pc
, state
);
227 scop_decl
= kill(pet_tree_get_loc(tree
), array
, pc
, state
);
228 scop_decl
= pet_scop_add_array(scop_decl
, array
);
230 if (tree
->type
!= pet_tree_decl_init
)
233 lhs
= pet_expr_copy(tree
->u
.d
.var
);
234 rhs
= pet_expr_copy(tree
->u
.d
.init
);
235 type_size
= pet_expr_get_type_size(lhs
);
236 pe
= pet_expr_new_binary(type_size
, pet_op_assign
, lhs
, rhs
);
237 scop
= scop_from_expr(pe
, state
->n_stmt
++, pet_tree_get_loc(tree
), pc
);
239 scop_decl
= pet_scop_prefix(scop_decl
, 0);
240 scop
= pet_scop_prefix(scop
, 1);
242 ctx
= pet_tree_get_ctx(tree
);
243 scop
= pet_scop_add_seq(ctx
, scop_decl
, scop
);
248 /* Construct a pet_scop for an expression statement within the context "pc".
250 static struct pet_scop
*scop_from_tree_expr(__isl_keep pet_tree
*tree
,
251 __isl_keep pet_context
*pc
, struct pet_state
*state
)
253 return scop_from_unevaluated_tree(pet_tree_copy(tree
),
254 state
->n_stmt
++, pc
);
257 /* Return those elements in the space of "cond" that come after
258 * (based on "sign") an element in "cond" in the final dimension.
260 static __isl_give isl_set
*after(__isl_take isl_set
*cond
, int sign
)
263 isl_map
*previous_to_this
;
266 dim
= isl_set_dim(cond
, isl_dim_set
);
267 space
= isl_space_map_from_set(isl_set_get_space(cond
));
268 previous_to_this
= isl_map_universe(space
);
269 for (i
= 0; i
+ 1 < dim
; ++i
)
270 previous_to_this
= isl_map_equate(previous_to_this
,
271 isl_dim_in
, i
, isl_dim_out
, i
);
273 previous_to_this
= isl_map_order_lt(previous_to_this
,
274 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
276 previous_to_this
= isl_map_order_gt(previous_to_this
,
277 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
279 cond
= isl_set_apply(cond
, previous_to_this
);
284 /* Remove those iterations of "domain" that have an earlier iteration
285 * (based on "sign") in the final dimension where "skip" is satisfied.
286 * If "apply_skip_map" is set, then "skip_map" is first applied
287 * to the embedded skip condition before removing it from the domain.
289 static __isl_give isl_set
*apply_affine_break(__isl_take isl_set
*domain
,
290 __isl_take isl_set
*skip
, int sign
,
291 int apply_skip_map
, __isl_keep isl_map
*skip_map
)
294 skip
= isl_set_apply(skip
, isl_map_copy(skip_map
));
295 skip
= isl_set_intersect(skip
, isl_set_copy(domain
));
296 return isl_set_subtract(domain
, after(skip
, sign
));
299 /* Create an affine expression on the domain space of "pc" that
300 * is equal to the final dimension of this domain.
302 static __isl_give isl_aff
*map_to_last(__isl_keep pet_context
*pc
)
308 space
= pet_context_get_space(pc
);
309 pos
= isl_space_dim(space
, isl_dim_set
) - 1;
310 ls
= isl_local_space_from_space(space
);
311 return isl_aff_var_on_domain(ls
, isl_dim_set
, pos
);
314 /* Create an affine expression that maps elements
315 * of an array "id_test" to the previous element in the final dimension
316 * (according to "inc"), provided this element belongs to "domain".
317 * That is, create the affine expression
319 * { id[outer,x] -> id[outer,x - inc] : (outer,x - inc) in domain }
321 static __isl_give isl_multi_pw_aff
*map_to_previous(__isl_take isl_id
*id_test
,
322 __isl_take isl_set
*domain
, __isl_take isl_val
*inc
)
329 isl_multi_pw_aff
*prev
;
331 pos
= isl_set_dim(domain
, isl_dim_set
) - 1;
332 space
= isl_set_get_space(domain
);
333 space
= isl_space_map_from_set(space
);
334 ma
= isl_multi_aff_identity(space
);
335 aff
= isl_multi_aff_get_aff(ma
, pos
);
336 aff
= isl_aff_add_constant_val(aff
, isl_val_neg(inc
));
337 ma
= isl_multi_aff_set_aff(ma
, pos
, aff
);
338 domain
= isl_set_preimage_multi_aff(domain
, isl_multi_aff_copy(ma
));
339 prev
= isl_multi_pw_aff_from_multi_aff(ma
);
340 pa
= isl_multi_pw_aff_get_pw_aff(prev
, pos
);
341 pa
= isl_pw_aff_intersect_domain(pa
, domain
);
342 prev
= isl_multi_pw_aff_set_pw_aff(prev
, pos
, pa
);
343 prev
= isl_multi_pw_aff_set_tuple_id(prev
, isl_dim_out
, id_test
);
348 /* Add an implication to "scop" expressing that if an element of
349 * virtual array "id_test" has value "satisfied" then all previous elements
350 * of this array (in the final dimension) also have that value.
351 * The set of previous elements is bounded by "domain".
352 * If "sign" is negative then the iterator
353 * is decreasing and we express that all subsequent array elements
354 * (but still defined previously) have the same value.
356 static struct pet_scop
*add_implication(struct pet_scop
*scop
,
357 __isl_take isl_id
*id_test
, __isl_take isl_set
*domain
, int sign
,
364 dim
= isl_set_dim(domain
, isl_dim_set
);
365 domain
= isl_set_set_tuple_id(domain
, id_test
);
366 space
= isl_space_map_from_set(isl_set_get_space(domain
));
367 map
= isl_map_universe(space
);
368 for (i
= 0; i
+ 1 < dim
; ++i
)
369 map
= isl_map_equate(map
, isl_dim_in
, i
, isl_dim_out
, i
);
371 map
= isl_map_order_ge(map
,
372 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
374 map
= isl_map_order_le(map
,
375 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
376 map
= isl_map_intersect_range(map
, domain
);
377 scop
= pet_scop_add_implication(scop
, map
, satisfied
);
382 /* Add a filter to "scop" that imposes that it is only executed
383 * when the variable identified by "id_test" has a zero value
384 * for all previous iterations of "domain".
386 * In particular, add a filter that imposes that the array
387 * has a zero value at the previous iteration of domain and
388 * add an implication that implies that it then has that
389 * value for all previous iterations.
391 static struct pet_scop
*scop_add_break(struct pet_scop
*scop
,
392 __isl_take isl_id
*id_test
, __isl_take isl_set
*domain
,
393 __isl_take isl_val
*inc
)
395 isl_multi_pw_aff
*prev
;
396 int sign
= isl_val_sgn(inc
);
398 prev
= map_to_previous(isl_id_copy(id_test
), isl_set_copy(domain
), inc
);
399 scop
= add_implication(scop
, id_test
, domain
, sign
, 0);
400 scop
= pet_scop_filter(scop
, prev
, 0);
405 static struct pet_scop
*scop_from_tree(__isl_keep pet_tree
*tree
,
406 __isl_keep pet_context
*pc
, struct pet_state
*state
);
408 /* Construct a pet_scop for an infinite loop around the given body
409 * within the context "pc".
411 * The domain of "pc" has already been extended with an infinite loop
415 * We extract a pet_scop for the body and then embed it in a loop with
418 * { [outer,t] -> [t] }
420 * If the body contains any break, then it is taken into
421 * account in apply_affine_break (if the skip condition is affine)
422 * or in scop_add_break (if the skip condition is not affine).
424 * Note that in case of an affine skip condition,
425 * since we are dealing with a loop without loop iterator,
426 * the skip condition cannot refer to the current loop iterator and
427 * so effectively, the effect on the iteration domain is of the form
429 * { [outer,0]; [outer,t] : t >= 1 and not skip }
431 static struct pet_scop
*scop_from_infinite_loop(__isl_keep pet_tree
*body
,
432 __isl_keep pet_context
*pc
, struct pet_state
*state
)
439 struct pet_scop
*scop
;
440 int has_affine_break
;
443 ctx
= pet_tree_get_ctx(body
);
444 domain
= pet_context_get_domain(pc
);
445 sched
= map_to_last(pc
);
447 scop
= scop_from_tree(body
, pc
, state
);
449 has_affine_break
= pet_scop_has_affine_skip(scop
, pet_skip_later
);
450 if (has_affine_break
)
451 skip
= pet_scop_get_affine_skip_domain(scop
, pet_skip_later
);
452 has_var_break
= pet_scop_has_var_skip(scop
, pet_skip_later
);
454 id_test
= pet_scop_get_skip_id(scop
, pet_skip_later
);
456 scop
= pet_scop_embed(scop
, isl_set_copy(domain
), sched
);
457 if (has_affine_break
) {
458 domain
= apply_affine_break(domain
, skip
, 1, 0, NULL
);
459 scop
= pet_scop_intersect_domain_prefix(scop
,
460 isl_set_copy(domain
));
463 scop
= scop_add_break(scop
, id_test
, domain
, isl_val_one(ctx
));
465 isl_set_free(domain
);
470 /* Construct a pet_scop for an infinite loop, i.e., a loop of the form
475 * within the context "pc".
477 * Extend the domain of "pc" with an extra inner loop
481 * and construct the scop in scop_from_infinite_loop.
483 static struct pet_scop
*scop_from_infinite_for(__isl_keep pet_tree
*tree
,
484 __isl_keep pet_context
*pc
, struct pet_state
*state
)
486 struct pet_scop
*scop
;
488 pc
= pet_context_copy(pc
);
489 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.l
.body
);
491 pc
= pet_context_add_infinite_loop(pc
);
493 scop
= scop_from_infinite_loop(tree
->u
.l
.body
, pc
, state
);
495 pet_context_free(pc
);
500 /* Construct a pet_scop for a while loop of the form
505 * within the context "pc".
507 * The domain of "pc" has already been extended with an infinite loop
511 * Here, we add the constraints on the outer loop iterators
512 * implied by "pa" and construct the scop in scop_from_infinite_loop.
513 * Note that the intersection with these constraints
514 * may result in an empty loop.
516 static struct pet_scop
*scop_from_affine_while(__isl_keep pet_tree
*tree
,
517 __isl_take isl_pw_aff
*pa
, __isl_take pet_context
*pc
,
518 struct pet_state
*state
)
520 struct pet_scop
*scop
;
521 isl_set
*dom
, *local
;
524 valid
= isl_pw_aff_domain(isl_pw_aff_copy(pa
));
525 dom
= isl_pw_aff_non_zero_set(pa
);
526 local
= isl_set_add_dims(isl_set_copy(dom
), isl_dim_set
, 1);
527 pc
= pet_context_intersect_domain(pc
, local
);
528 scop
= scop_from_infinite_loop(tree
->u
.l
.body
, pc
, state
);
529 scop
= pet_scop_restrict(scop
, dom
);
530 scop
= pet_scop_restrict_context(scop
, valid
);
532 pet_context_free(pc
);
536 /* Construct a scop for a while, given the scops for the condition
537 * and the body, the filter identifier and the iteration domain of
540 * In particular, the scop for the condition is filtered to depend
541 * on "id_test" evaluating to true for all previous iterations
542 * of the loop, while the scop for the body is filtered to depend
543 * on "id_test" evaluating to true for all iterations up to the
545 * The actual filter only imposes that this virtual array has
546 * value one on the previous or the current iteration.
547 * The fact that this condition also applies to the previous
548 * iterations is enforced by an implication.
550 * These filtered scops are then combined into a single scop.
552 * "sign" is positive if the iterator increases and negative
555 static struct pet_scop
*scop_add_while(struct pet_scop
*scop_cond
,
556 struct pet_scop
*scop_body
, __isl_take isl_id
*id_test
,
557 __isl_take isl_set
*domain
, __isl_take isl_val
*inc
)
559 isl_ctx
*ctx
= isl_set_get_ctx(domain
);
561 isl_multi_pw_aff
*test_index
;
562 isl_multi_pw_aff
*prev
;
563 int sign
= isl_val_sgn(inc
);
564 struct pet_scop
*scop
;
566 prev
= map_to_previous(isl_id_copy(id_test
), isl_set_copy(domain
), inc
);
567 scop_cond
= pet_scop_filter(scop_cond
, prev
, 1);
569 space
= isl_space_map_from_set(isl_set_get_space(domain
));
570 test_index
= isl_multi_pw_aff_identity(space
);
571 test_index
= isl_multi_pw_aff_set_tuple_id(test_index
, isl_dim_out
,
572 isl_id_copy(id_test
));
573 scop_body
= pet_scop_filter(scop_body
, test_index
, 1);
575 scop
= pet_scop_add_seq(ctx
, scop_cond
, scop_body
);
576 scop
= add_implication(scop
, id_test
, domain
, sign
, 1);
581 /* Create a pet_scop with a single statement with name S_<stmt_nr>,
582 * evaluating "cond" and writing the result to a virtual scalar,
583 * as expressed by "index".
584 * The expression "cond" has not yet been evaluated in the context of "pc".
585 * Do so within the context "pc".
586 * The location of the statement is set to "loc".
588 static struct pet_scop
*scop_from_non_affine_condition(
589 __isl_take pet_expr
*cond
, int stmt_nr
,
590 __isl_take isl_multi_pw_aff
*index
,
591 __isl_take pet_loc
*loc
, __isl_keep pet_context
*pc
)
593 pet_expr
*expr
, *write
;
595 cond
= pet_context_evaluate_expr(pc
, cond
);
597 write
= pet_expr_from_index(index
);
598 write
= pet_expr_access_set_write(write
, 1);
599 write
= pet_expr_access_set_read(write
, 0);
600 expr
= pet_expr_new_binary(1, pet_op_assign
, write
, cond
);
602 return scop_from_evaluated_expr(expr
, stmt_nr
, loc
, pc
);
605 /* Given that "scop" has an affine skip condition of type pet_skip_now,
606 * apply this skip condition to the domain of "pc".
607 * That is, remove the elements satisfying the skip condition from
608 * the domain of "pc".
610 static __isl_give pet_context
*apply_affine_continue(__isl_take pet_context
*pc
,
611 struct pet_scop
*scop
)
613 isl_set
*domain
, *skip
;
615 skip
= pet_scop_get_affine_skip_domain(scop
, pet_skip_now
);
616 domain
= pet_context_get_domain(pc
);
617 domain
= isl_set_subtract(domain
, skip
);
618 pc
= pet_context_intersect_domain(pc
, domain
);
623 /* Add a scop for evaluating the loop increment "inc" add the end
624 * of a loop body "scop" within the context "pc".
626 * The skip conditions resulting from continue statements inside
627 * the body do not apply to "inc", but those resulting from break
628 * statements do need to get applied.
630 static struct pet_scop
*scop_add_inc(struct pet_scop
*scop
,
631 __isl_take pet_expr
*inc
, __isl_take pet_loc
*loc
,
632 __isl_keep pet_context
*pc
, struct pet_state
*state
)
634 struct pet_scop
*scop_inc
;
636 pc
= pet_context_copy(pc
);
638 if (pet_scop_has_skip(scop
, pet_skip_later
)) {
639 isl_multi_pw_aff
*skip
;
640 skip
= pet_scop_get_skip(scop
, pet_skip_later
);
641 scop
= pet_scop_set_skip(scop
, pet_skip_now
, skip
);
642 if (pet_scop_has_affine_skip(scop
, pet_skip_now
))
643 pc
= apply_affine_continue(pc
, scop
);
645 pet_scop_reset_skip(scop
, pet_skip_now
);
646 scop_inc
= scop_from_expr(inc
, state
->n_stmt
++, loc
, pc
);
647 scop_inc
= pet_scop_prefix(scop_inc
, 2);
648 scop
= pet_scop_add_seq(state
->ctx
, scop
, scop_inc
);
650 pet_context_free(pc
);
655 /* Construct a generic while scop, with iteration domain
656 * { [t] : t >= 0 } around the scop for "tree_body" within the context "pc".
657 * The domain of "pc" has already been extended with this infinite loop
661 * The scop consists of two parts,
662 * one for evaluating the condition "cond" and one for the body.
663 * If "expr_inc" is not NULL, then a scop for evaluating this expression
664 * is added at the end of the body,
665 * after replacing any skip conditions resulting from continue statements
666 * by the skip conditions resulting from break statements (if any).
668 * The schedule is adjusted to reflect that the condition is evaluated
669 * before the body is executed and the body is filtered to depend
670 * on the result of the condition evaluating to true on all iterations
671 * up to the current iteration, while the evaluation of the condition itself
672 * is filtered to depend on the result of the condition evaluating to true
673 * on all previous iterations.
674 * The context of the scop representing the body is dropped
675 * because we don't know how many times the body will be executed,
678 * If the body contains any break, then it is taken into
679 * account in apply_affine_break (if the skip condition is affine)
680 * or in scop_add_break (if the skip condition is not affine).
682 * Note that in case of an affine skip condition,
683 * since we are dealing with a loop without loop iterator,
684 * the skip condition cannot refer to the current loop iterator and
685 * so effectively, the effect on the iteration domain is of the form
687 * { [outer,0]; [outer,t] : t >= 1 and not skip }
689 static struct pet_scop
*scop_from_non_affine_while(__isl_take pet_expr
*cond
,
690 __isl_take pet_loc
*loc
, __isl_keep pet_tree
*tree_body
,
691 __isl_take pet_expr
*expr_inc
, __isl_take pet_context
*pc
,
692 struct pet_state
*state
)
695 isl_id
*id_test
, *id_break_test
;
697 isl_multi_pw_aff
*test_index
;
701 struct pet_scop
*scop
, *scop_body
;
702 int has_affine_break
;
706 space
= pet_context_get_space(pc
);
707 test_index
= pet_create_test_index(space
, state
->n_test
++);
708 scop
= scop_from_non_affine_condition(cond
, state
->n_stmt
++,
709 isl_multi_pw_aff_copy(test_index
),
710 pet_loc_copy(loc
), pc
);
711 id_test
= isl_multi_pw_aff_get_tuple_id(test_index
, isl_dim_out
);
712 domain
= pet_context_get_domain(pc
);
713 scop
= pet_scop_add_boolean_array(scop
, isl_set_copy(domain
),
714 test_index
, state
->int_size
);
716 sched
= map_to_last(pc
);
718 scop_body
= scop_from_tree(tree_body
, pc
, state
);
720 has_affine_break
= pet_scop_has_affine_skip(scop_body
, pet_skip_later
);
721 if (has_affine_break
)
722 skip
= pet_scop_get_affine_skip_domain(scop_body
,
724 has_var_break
= pet_scop_has_var_skip(scop_body
, pet_skip_later
);
726 id_break_test
= pet_scop_get_skip_id(scop_body
, pet_skip_later
);
728 scop
= pet_scop_prefix(scop
, 0);
729 scop
= pet_scop_embed(scop
, isl_set_copy(domain
), isl_aff_copy(sched
));
730 scop_body
= pet_scop_reset_context(scop_body
);
731 scop_body
= pet_scop_prefix(scop_body
, 1);
733 scop_body
= scop_add_inc(scop_body
, expr_inc
, loc
, pc
, state
);
736 scop_body
= pet_scop_embed(scop_body
, isl_set_copy(domain
), sched
);
738 if (has_affine_break
) {
739 domain
= apply_affine_break(domain
, skip
, 1, 0, NULL
);
740 scop
= pet_scop_intersect_domain_prefix(scop
,
741 isl_set_copy(domain
));
742 scop_body
= pet_scop_intersect_domain_prefix(scop_body
,
743 isl_set_copy(domain
));
746 scop
= scop_add_break(scop
, isl_id_copy(id_break_test
),
747 isl_set_copy(domain
), isl_val_one(ctx
));
748 scop_body
= scop_add_break(scop_body
, id_break_test
,
749 isl_set_copy(domain
), isl_val_one(ctx
));
751 scop
= scop_add_while(scop
, scop_body
, id_test
, domain
,
754 pet_context_free(pc
);
758 /* Check if the while loop is of the form
760 * while (affine expression)
763 * If so, call scop_from_affine_while to construct a scop.
765 * Otherwise, pass control to scop_from_non_affine_while.
767 * "pc" is the context in which the affine expressions in the scop are created.
768 * The domain of "pc" is extended with an infinite loop
772 * before passing control to scop_from_affine_while or
773 * scop_from_non_affine_while.
775 static struct pet_scop
*scop_from_while(__isl_keep pet_tree
*tree
,
776 __isl_keep pet_context
*pc
, struct pet_state
*state
)
784 pc
= pet_context_copy(pc
);
785 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.l
.body
);
787 cond_expr
= pet_expr_copy(tree
->u
.l
.cond
);
788 cond_expr
= pet_context_evaluate_expr(pc
, cond_expr
);
789 pa
= pet_expr_extract_affine_condition(cond_expr
, pc
);
790 pet_expr_free(cond_expr
);
792 pc
= pet_context_add_infinite_loop(pc
);
797 if (!isl_pw_aff_involves_nan(pa
))
798 return scop_from_affine_while(tree
, pa
, pc
, state
);
800 return scop_from_non_affine_while(pet_expr_copy(tree
->u
.l
.cond
),
801 pet_tree_get_loc(tree
), tree
->u
.l
.body
, NULL
,
804 pet_context_free(pc
);
808 /* Check whether "cond" expresses a simple loop bound
809 * on the final set dimension.
810 * In particular, if "up" is set then "cond" should contain only
811 * upper bounds on the final set dimension.
812 * Otherwise, it should contain only lower bounds.
814 static int is_simple_bound(__isl_keep isl_set
*cond
, __isl_keep isl_val
*inc
)
818 pos
= isl_set_dim(cond
, isl_dim_set
) - 1;
819 if (isl_val_is_pos(inc
))
820 return !isl_set_dim_has_any_lower_bound(cond
, isl_dim_set
, pos
);
822 return !isl_set_dim_has_any_upper_bound(cond
, isl_dim_set
, pos
);
825 /* Extend a condition on a given iteration of a loop to one that
826 * imposes the same condition on all previous iterations.
827 * "domain" expresses the lower [upper] bound on the iterations
828 * when inc is positive [negative] in its final dimension.
830 * In particular, we construct the condition (when inc is positive)
832 * forall i' : (domain(i') and i' <= i) => cond(i')
834 * (where "<=" applies to the final dimension)
835 * which is equivalent to
837 * not exists i' : domain(i') and i' <= i and not cond(i')
839 * We construct this set by subtracting the satisfying cond from domain,
842 * { [i'] -> [i] : i' <= i }
844 * and then subtracting the result from domain again.
846 static __isl_give isl_set
*valid_for_each_iteration(__isl_take isl_set
*cond
,
847 __isl_take isl_set
*domain
, __isl_take isl_val
*inc
)
850 isl_map
*previous_to_this
;
853 dim
= isl_set_dim(cond
, isl_dim_set
);
854 space
= isl_space_map_from_set(isl_set_get_space(cond
));
855 previous_to_this
= isl_map_universe(space
);
856 for (i
= 0; i
+ 1 < dim
; ++i
)
857 previous_to_this
= isl_map_equate(previous_to_this
,
858 isl_dim_in
, i
, isl_dim_out
, i
);
859 if (isl_val_is_pos(inc
))
860 previous_to_this
= isl_map_order_le(previous_to_this
,
861 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
863 previous_to_this
= isl_map_order_ge(previous_to_this
,
864 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
866 cond
= isl_set_subtract(isl_set_copy(domain
), cond
);
867 cond
= isl_set_apply(cond
, previous_to_this
);
868 cond
= isl_set_subtract(domain
, cond
);
875 /* Given an initial value of the form
877 * { [outer,i] -> init(outer) }
879 * construct a domain of the form
881 * { [outer,i] : exists a: i = init(outer) + a * inc and a >= 0 }
883 static __isl_give isl_set
*strided_domain(__isl_take isl_pw_aff
*init
,
884 __isl_take isl_val
*inc
)
892 dim
= isl_pw_aff_dim(init
, isl_dim_in
);
894 init
= isl_pw_aff_add_dims(init
, isl_dim_in
, 1);
895 space
= isl_pw_aff_get_domain_space(init
);
896 ls
= isl_local_space_from_space(space
);
897 aff
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
898 aff
= isl_aff_add_coefficient_val(aff
, isl_dim_in
, dim
, inc
);
899 init
= isl_pw_aff_add(init
, isl_pw_aff_from_aff(aff
));
901 aff
= isl_aff_var_on_domain(ls
, isl_dim_set
, dim
- 1);
902 set
= isl_pw_aff_eq_set(isl_pw_aff_from_aff(aff
), init
);
904 set
= isl_set_lower_bound_si(set
, isl_dim_set
, dim
, 0);
905 set
= isl_set_project_out(set
, isl_dim_set
, dim
, 1);
910 /* Assuming "cond" represents a bound on a loop where the loop
911 * iterator "iv" is incremented (or decremented) by one, check if wrapping
914 * Under the given assumptions, wrapping is only possible if "cond" allows
915 * for the last value before wrapping, i.e., 2^width - 1 in case of an
916 * increasing iterator and 0 in case of a decreasing iterator.
918 static int can_wrap(__isl_keep isl_set
*cond
, __isl_keep pet_expr
*iv
,
919 __isl_keep isl_val
*inc
)
926 test
= isl_set_copy(cond
);
928 ctx
= isl_set_get_ctx(test
);
929 if (isl_val_is_neg(inc
))
930 limit
= isl_val_zero(ctx
);
932 limit
= isl_val_int_from_ui(ctx
, pet_expr_get_type_size(iv
));
933 limit
= isl_val_2exp(limit
);
934 limit
= isl_val_sub_ui(limit
, 1);
937 test
= isl_set_fix_val(cond
, isl_dim_set
, 0, limit
);
938 cw
= !isl_set_is_empty(test
);
948 * construct the following affine expression on this space
950 * { [outer, v] -> [outer, v mod 2^width] }
952 * where width is the number of bits used to represent the values
953 * of the unsigned variable "iv".
955 static __isl_give isl_multi_aff
*compute_wrapping(__isl_take isl_space
*space
,
956 __isl_keep pet_expr
*iv
)
964 dim
= isl_space_dim(space
, isl_dim_set
);
966 ctx
= isl_space_get_ctx(space
);
967 mod
= isl_val_int_from_ui(ctx
, pet_expr_get_type_size(iv
));
968 mod
= isl_val_2exp(mod
);
970 space
= isl_space_map_from_set(space
);
971 ma
= isl_multi_aff_identity(space
);
973 aff
= isl_multi_aff_get_aff(ma
, dim
- 1);
974 aff
= isl_aff_mod_val(aff
, mod
);
975 ma
= isl_multi_aff_set_aff(ma
, dim
- 1, aff
);
980 /* Given two sets in the space
984 * where l represents the outer loop iterators, compute the set
985 * of values of l that ensure that "set1" is a subset of "set2".
987 * set1 is a subset of set2 if
989 * forall i: set1(l,i) => set2(l,i)
993 * not exists i: set1(l,i) and not set2(l,i)
997 * not exists i: (set1 \ set2)(l,i)
999 static __isl_give isl_set
*enforce_subset(__isl_take isl_set
*set1
,
1000 __isl_take isl_set
*set2
)
1004 pos
= isl_set_dim(set1
, isl_dim_set
) - 1;
1005 set1
= isl_set_subtract(set1
, set2
);
1006 set1
= isl_set_eliminate(set1
, isl_dim_set
, pos
, 1);
1007 return isl_set_complement(set1
);
1010 /* Compute the set of outer iterator values for which "cond" holds
1011 * on the next iteration of the inner loop for each element of "dom".
1013 * We first construct mapping { [l,i] -> [l,i + inc] } (where l refers
1014 * to the outer loop iterators), plug that into "cond"
1015 * and then compute the set of outer iterators for which "dom" is a subset
1018 static __isl_give isl_set
*valid_on_next(__isl_take isl_set
*cond
,
1019 __isl_take isl_set
*dom
, __isl_take isl_val
*inc
)
1026 pos
= isl_set_dim(dom
, isl_dim_set
) - 1;
1027 space
= isl_set_get_space(dom
);
1028 space
= isl_space_map_from_set(space
);
1029 ma
= isl_multi_aff_identity(space
);
1030 aff
= isl_multi_aff_get_aff(ma
, pos
);
1031 aff
= isl_aff_add_constant_val(aff
, inc
);
1032 ma
= isl_multi_aff_set_aff(ma
, pos
, aff
);
1033 cond
= isl_set_preimage_multi_aff(cond
, ma
);
1035 return enforce_subset(dom
, cond
);
1038 /* Extract the for loop "tree" as a while loop within the context "pc_init".
1039 * In particular, "pc_init" represents the context of the loop,
1040 * whereas "pc" represents the context of the body of the loop and
1041 * has already had its domain extended with an infinite loop
1045 * The for loop has the form
1047 * for (iv = init; cond; iv += inc)
1058 * except that the skips resulting from any continue statements
1059 * in body do not apply to the increment, but are replaced by the skips
1060 * resulting from break statements.
1062 * If the loop iterator is declared in the for loop, then it is killed before
1063 * and after the loop.
1065 static struct pet_scop
*scop_from_non_affine_for(__isl_keep pet_tree
*tree
,
1066 __isl_keep pet_context
*init_pc
, __isl_take pet_context
*pc
,
1067 struct pet_state
*state
)
1071 pet_expr
*expr_iv
, *init
, *inc
;
1072 struct pet_scop
*scop_init
, *scop
;
1074 struct pet_array
*array
;
1075 struct pet_scop
*scop_kill
;
1077 iv
= pet_expr_access_get_id(tree
->u
.l
.iv
);
1078 pc
= pet_context_clear_value(pc
, iv
);
1080 declared
= tree
->u
.l
.declared
;
1082 expr_iv
= pet_expr_copy(tree
->u
.l
.iv
);
1083 type_size
= pet_expr_get_type_size(expr_iv
);
1084 init
= pet_expr_copy(tree
->u
.l
.init
);
1085 init
= pet_expr_new_binary(type_size
, pet_op_assign
, expr_iv
, init
);
1086 scop_init
= scop_from_expr(init
, state
->n_stmt
++,
1087 pet_tree_get_loc(tree
), init_pc
);
1088 scop_init
= pet_scop_prefix(scop_init
, declared
);
1090 expr_iv
= pet_expr_copy(tree
->u
.l
.iv
);
1091 type_size
= pet_expr_get_type_size(expr_iv
);
1092 inc
= pet_expr_copy(tree
->u
.l
.inc
);
1093 inc
= pet_expr_new_binary(type_size
, pet_op_add_assign
, expr_iv
, inc
);
1095 scop
= scop_from_non_affine_while(pet_expr_copy(tree
->u
.l
.cond
),
1096 pet_tree_get_loc(tree
), tree
->u
.l
.body
, inc
,
1097 pet_context_copy(pc
), state
);
1099 scop
= pet_scop_prefix(scop
, declared
+ 1);
1100 scop
= pet_scop_add_seq(state
->ctx
, scop_init
, scop
);
1102 pet_context_free(pc
);
1107 array
= extract_array(tree
->u
.l
.iv
, init_pc
, state
);
1109 array
->declared
= 1;
1110 scop_kill
= kill(pet_tree_get_loc(tree
), array
, init_pc
, state
);
1111 scop_kill
= pet_scop_prefix(scop_kill
, 0);
1112 scop
= pet_scop_add_seq(state
->ctx
, scop_kill
, scop
);
1113 scop_kill
= kill(pet_tree_get_loc(tree
), array
, init_pc
, state
);
1114 scop_kill
= pet_scop_add_array(scop_kill
, array
);
1115 scop_kill
= pet_scop_prefix(scop_kill
, 3);
1116 scop
= pet_scop_add_seq(state
->ctx
, scop
, scop_kill
);
1121 /* Given an access expression "expr", is the variable accessed by
1122 * "expr" assigned anywhere inside "tree"?
1124 static int is_assigned(__isl_keep pet_expr
*expr
, __isl_keep pet_tree
*tree
)
1129 id
= pet_expr_access_get_id(expr
);
1130 assigned
= pet_tree_writes(tree
, id
);
1136 /* Are all nested access parameters in "pa" allowed given "tree".
1137 * In particular, is none of them written by anywhere inside "tree".
1139 * If "tree" has any continue or break nodes in the current loop level,
1140 * then no nested access parameters are allowed.
1141 * In particular, if there is any nested access in a guard
1142 * for a piece of code containing a "continue", then we want to introduce
1143 * a separate statement for evaluating this guard so that we can express
1144 * that the result is false for all previous iterations.
1146 static int is_nested_allowed(__isl_keep isl_pw_aff
*pa
,
1147 __isl_keep pet_tree
*tree
)
1154 if (!pet_nested_any_in_pw_aff(pa
))
1157 if (pet_tree_has_continue_or_break(tree
))
1160 nparam
= isl_pw_aff_dim(pa
, isl_dim_param
);
1161 for (i
= 0; i
< nparam
; ++i
) {
1162 isl_id
*id
= isl_pw_aff_get_dim_id(pa
, isl_dim_param
, i
);
1166 if (!pet_nested_in_id(id
)) {
1171 expr
= pet_nested_extract_expr(id
);
1172 allowed
= pet_expr_get_type(expr
) == pet_expr_access
&&
1173 !is_assigned(expr
, tree
);
1175 pet_expr_free(expr
);
1185 /* Internal data structure for collect_local.
1186 * "pc" and "state" are needed to extract pet_arrays for the local variables.
1187 * "local" collects the results.
1189 struct pet_tree_collect_local_data
{
1191 struct pet_state
*state
;
1192 isl_union_set
*local
;
1195 /* Add the variable accessed by "var" to data->local.
1196 * We extract a representation of the variable from
1197 * the pet_array constructed using extract_array
1198 * to ensure consistency with the rest of the scop.
1200 static int add_local(struct pet_tree_collect_local_data
*data
,
1201 __isl_keep pet_expr
*var
)
1203 struct pet_array
*array
;
1206 array
= extract_array(var
, data
->pc
, data
->state
);
1210 universe
= isl_set_universe(isl_set_get_space(array
->extent
));
1211 data
->local
= isl_union_set_add_set(data
->local
, universe
);
1212 pet_array_free(array
);
1217 /* If the node "tree" declares a variable, then add it to
1220 static int extract_local_var(__isl_keep pet_tree
*tree
, void *user
)
1222 enum pet_tree_type type
;
1223 struct pet_tree_collect_local_data
*data
= user
;
1225 type
= pet_tree_get_type(tree
);
1226 if (type
== pet_tree_decl
|| type
== pet_tree_decl_init
)
1227 return add_local(data
, tree
->u
.d
.var
);
1232 /* If the node "tree" is a for loop that declares its induction variable,
1233 * then add it this induction variable to data->local.
1235 static int extract_local_iterator(__isl_keep pet_tree
*tree
, void *user
)
1237 struct pet_tree_collect_local_data
*data
= user
;
1239 if (pet_tree_get_type(tree
) == pet_tree_for
&& tree
->u
.l
.declared
)
1240 return add_local(data
, tree
->u
.l
.iv
);
1245 /* Collect and return all local variables of the for loop represented
1246 * by "tree", with "scop" the corresponding pet_scop.
1247 * "pc" and "state" are needed to extract pet_arrays for the local variables.
1249 * We collect not only the variables that are declared inside "tree",
1250 * but also the loop iterators that are declared anywhere inside
1251 * any possible macro statements in "scop".
1252 * The latter also appear as declared variable in the scop,
1253 * whereas other declared loop iterators only appear implicitly
1254 * in the iteration domains.
1256 static __isl_give isl_union_set
*collect_local(struct pet_scop
*scop
,
1257 __isl_keep pet_tree
*tree
, __isl_keep pet_context
*pc
,
1258 struct pet_state
*state
)
1262 struct pet_tree_collect_local_data data
= { pc
, state
};
1264 ctx
= pet_tree_get_ctx(tree
);
1265 data
.local
= isl_union_set_empty(isl_space_params_alloc(ctx
, 0));
1267 if (pet_tree_foreach_sub_tree(tree
, &extract_local_var
, &data
) < 0)
1268 return isl_union_set_free(data
.local
);
1270 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
1271 pet_tree
*body
= scop
->stmts
[i
]->body
;
1272 if (pet_tree_foreach_sub_tree(body
, &extract_local_iterator
,
1274 return isl_union_set_free(data
.local
);
1280 /* Add an independence to "scop" if the for node "tree" was marked
1282 * "domain" is the set of loop iterators, with the current for loop
1283 * innermost. If "sign" is positive, then the inner iterator increases.
1284 * Otherwise it decreases.
1285 * "pc" and "state" are needed to extract pet_arrays for the local variables.
1287 * If the tree was marked, then collect all local variables and
1288 * add an independence.
1290 static struct pet_scop
*set_independence(struct pet_scop
*scop
,
1291 __isl_keep pet_tree
*tree
, __isl_keep isl_set
*domain
, int sign
,
1292 __isl_keep pet_context
*pc
, struct pet_state
*state
)
1294 isl_union_set
*local
;
1296 if (!tree
->u
.l
.independent
)
1299 local
= collect_local(scop
, tree
, pc
, state
);
1300 scop
= pet_scop_set_independent(scop
, domain
, local
, sign
);
1305 /* Construct a pet_scop for a for tree with static affine initialization
1306 * and constant increment within the context "pc".
1307 * The domain of "pc" has already been extended with an (at this point
1308 * unbounded) inner loop iterator corresponding to the current for loop.
1310 * The condition is allowed to contain nested accesses, provided
1311 * they are not being written to inside the body of the loop.
1312 * Otherwise, or if the condition is otherwise non-affine, the for loop is
1313 * essentially treated as a while loop, with iteration domain
1314 * { [l,i] : i >= init }, where l refers to the outer loop iterators.
1316 * We extract a pet_scop for the body after intersecting the domain of "pc"
1318 * { [l,i] : i >= init and condition' }
1322 * { [l,i] : i <= init and condition' }
1324 * Where condition' is equal to condition if the latter is
1325 * a simple upper [lower] bound and a condition that is extended
1326 * to apply to all previous iterations otherwise.
1327 * Afterwards, the schedule of the pet_scop is extended with
1335 * If the condition is non-affine, then we drop the condition from the
1336 * iteration domain and instead create a separate statement
1337 * for evaluating the condition. The body is then filtered to depend
1338 * on the result of the condition evaluating to true on all iterations
1339 * up to the current iteration, while the evaluation the condition itself
1340 * is filtered to depend on the result of the condition evaluating to true
1341 * on all previous iterations.
1342 * The context of the scop representing the body is dropped
1343 * because we don't know how many times the body will be executed,
1346 * If the stride of the loop is not 1, then "i >= init" is replaced by
1348 * (exists a: i = init + stride * a and a >= 0)
1350 * If the loop iterator i is unsigned, then wrapping may occur.
1351 * We therefore use a virtual iterator instead that does not wrap.
1352 * However, the condition in the code applies
1353 * to the wrapped value, so we need to change condition(l,i)
1354 * into condition([l,i % 2^width]). Similarly, we replace all accesses
1355 * to the original iterator by the wrapping of the virtual iterator.
1356 * Note that there may be no need to perform this final wrapping
1357 * if the loop condition (after wrapping) satisfies certain conditions.
1358 * However, the is_simple_bound condition is not enough since it doesn't
1359 * check if there even is an upper bound.
1361 * Wrapping on unsigned iterators can be avoided entirely if
1362 * loop condition is simple, the loop iterator is incremented
1363 * [decremented] by one and the last value before wrapping cannot
1364 * possibly satisfy the loop condition.
1366 * Valid outer iterators for a for loop are those for which the initial
1367 * value itself, the increment on each domain iteration and
1368 * the condition on both the initial value and
1369 * the result of incrementing the iterator for each iteration of the domain
1371 * If the loop condition is non-affine, then we only consider validity
1372 * of the initial value.
1374 * If the body contains any break, then we keep track of it in "skip"
1375 * (if the skip condition is affine) or it is handled in scop_add_break
1376 * (if the skip condition is not affine).
1377 * Note that the affine break condition needs to be considered with
1378 * respect to previous iterations in the virtual domain (if any).
1380 static struct pet_scop
*scop_from_affine_for(__isl_keep pet_tree
*tree
,
1381 __isl_take isl_pw_aff
*init_val
, __isl_take isl_pw_aff
*pa_inc
,
1382 __isl_take isl_val
*inc
, __isl_take pet_context
*pc
,
1383 struct pet_state
*state
)
1387 isl_set
*cond
= NULL
;
1388 isl_set
*skip
= NULL
;
1389 isl_id
*id_test
= NULL
, *id_break_test
;
1390 struct pet_scop
*scop
, *scop_cond
= NULL
;
1397 int has_affine_break
;
1399 isl_map
*rev_wrap
= NULL
;
1400 isl_map
*init_val_map
;
1402 isl_set
*valid_init
;
1403 isl_set
*valid_cond
;
1404 isl_set
*valid_cond_init
;
1405 isl_set
*valid_cond_next
;
1407 pet_expr
*cond_expr
;
1408 pet_context
*pc_nested
;
1410 pos
= pet_context_dim(pc
) - 1;
1412 domain
= pet_context_get_domain(pc
);
1413 cond_expr
= pet_expr_copy(tree
->u
.l
.cond
);
1414 cond_expr
= pet_context_evaluate_expr(pc
, cond_expr
);
1415 pc_nested
= pet_context_copy(pc
);
1416 pc_nested
= pet_context_set_allow_nested(pc_nested
, 1);
1417 pa
= pet_expr_extract_affine_condition(cond_expr
, pc_nested
);
1418 pet_context_free(pc_nested
);
1419 pet_expr_free(cond_expr
);
1421 valid_inc
= isl_pw_aff_domain(pa_inc
);
1423 is_unsigned
= pet_expr_get_type_size(tree
->u
.l
.iv
) > 0;
1425 is_non_affine
= isl_pw_aff_involves_nan(pa
) ||
1426 !is_nested_allowed(pa
, tree
->u
.l
.body
);
1428 pa
= isl_pw_aff_free(pa
);
1430 valid_cond
= isl_pw_aff_domain(isl_pw_aff_copy(pa
));
1431 cond
= isl_pw_aff_non_zero_set(pa
);
1433 cond
= isl_set_universe(isl_set_get_space(domain
));
1435 valid_cond
= isl_set_coalesce(valid_cond
);
1436 is_one
= isl_val_is_one(inc
) || isl_val_is_negone(inc
);
1437 is_virtual
= is_unsigned
&&
1438 (!is_one
|| can_wrap(cond
, tree
->u
.l
.iv
, inc
));
1440 init_val_map
= isl_map_from_pw_aff(isl_pw_aff_copy(init_val
));
1441 init_val_map
= isl_map_equate(init_val_map
, isl_dim_in
, pos
,
1443 valid_cond_init
= enforce_subset(isl_map_domain(init_val_map
),
1444 isl_set_copy(valid_cond
));
1445 if (is_one
&& !is_virtual
) {
1448 isl_pw_aff_free(init_val
);
1449 pa
= pet_expr_extract_comparison(
1450 isl_val_is_pos(inc
) ? pet_op_ge
: pet_op_le
,
1451 tree
->u
.l
.iv
, tree
->u
.l
.init
, pc
);
1452 valid_init
= isl_pw_aff_domain(isl_pw_aff_copy(pa
));
1453 valid_init
= isl_set_eliminate(valid_init
, isl_dim_set
,
1454 isl_set_dim(domain
, isl_dim_set
) - 1, 1);
1455 cond
= isl_pw_aff_non_zero_set(pa
);
1456 domain
= isl_set_intersect(domain
, cond
);
1460 valid_init
= isl_pw_aff_domain(isl_pw_aff_copy(init_val
));
1461 strided
= strided_domain(init_val
, isl_val_copy(inc
));
1462 domain
= isl_set_intersect(domain
, strided
);
1466 isl_multi_aff
*wrap
;
1467 wrap
= compute_wrapping(isl_set_get_space(cond
), tree
->u
.l
.iv
);
1468 pc
= pet_context_preimage_domain(pc
, wrap
);
1469 rev_wrap
= isl_map_from_multi_aff(wrap
);
1470 rev_wrap
= isl_map_reverse(rev_wrap
);
1471 cond
= isl_set_apply(cond
, isl_map_copy(rev_wrap
));
1472 valid_cond
= isl_set_apply(valid_cond
, isl_map_copy(rev_wrap
));
1473 valid_inc
= isl_set_apply(valid_inc
, isl_map_copy(rev_wrap
));
1475 is_simple
= is_simple_bound(cond
, inc
);
1477 cond
= isl_set_gist(cond
, isl_set_copy(domain
));
1478 is_simple
= is_simple_bound(cond
, inc
);
1481 cond
= valid_for_each_iteration(cond
,
1482 isl_set_copy(domain
), isl_val_copy(inc
));
1483 cond
= isl_set_align_params(cond
, isl_set_get_space(domain
));
1484 domain
= isl_set_intersect(domain
, cond
);
1485 sched
= map_to_last(pc
);
1486 if (isl_val_is_neg(inc
))
1487 sched
= isl_aff_neg(sched
);
1489 valid_cond_next
= valid_on_next(valid_cond
, isl_set_copy(domain
),
1491 valid_inc
= enforce_subset(isl_set_copy(domain
), valid_inc
);
1493 pc
= pet_context_intersect_domain(pc
, isl_set_copy(domain
));
1495 if (is_non_affine
) {
1497 isl_multi_pw_aff
*test_index
;
1498 space
= isl_set_get_space(domain
);
1499 test_index
= pet_create_test_index(space
, state
->n_test
++);
1500 scop_cond
= scop_from_non_affine_condition(
1501 pet_expr_copy(tree
->u
.l
.cond
), state
->n_stmt
++,
1502 isl_multi_pw_aff_copy(test_index
),
1503 pet_tree_get_loc(tree
), pc
);
1504 id_test
= isl_multi_pw_aff_get_tuple_id(test_index
,
1506 scop_cond
= pet_scop_add_boolean_array(scop_cond
,
1507 isl_set_copy(domain
), test_index
,
1509 scop_cond
= pet_scop_prefix(scop_cond
, 0);
1510 scop_cond
= pet_scop_embed(scop_cond
, isl_set_copy(domain
),
1511 isl_aff_copy(sched
));
1514 scop
= scop_from_tree(tree
->u
.l
.body
, pc
, state
);
1515 has_affine_break
= scop
&&
1516 pet_scop_has_affine_skip(scop
, pet_skip_later
);
1517 if (has_affine_break
)
1518 skip
= pet_scop_get_affine_skip_domain(scop
, pet_skip_later
);
1519 has_var_break
= scop
&& pet_scop_has_var_skip(scop
, pet_skip_later
);
1521 id_break_test
= pet_scop_get_skip_id(scop
, pet_skip_later
);
1522 if (is_non_affine
) {
1523 scop
= pet_scop_reset_context(scop
);
1524 scop
= pet_scop_prefix(scop
, 1);
1526 scop
= pet_scop_embed(scop
, isl_set_copy(domain
), sched
);
1527 scop
= pet_scop_resolve_nested(scop
);
1528 if (has_affine_break
) {
1529 domain
= apply_affine_break(domain
, skip
, isl_val_sgn(inc
),
1530 is_virtual
, rev_wrap
);
1531 scop
= pet_scop_intersect_domain_prefix(scop
,
1532 isl_set_copy(domain
));
1534 isl_map_free(rev_wrap
);
1536 scop
= scop_add_break(scop
, id_break_test
, isl_set_copy(domain
),
1538 if (is_non_affine
) {
1539 scop
= scop_add_while(scop_cond
, scop
, id_test
, domain
,
1541 isl_set_free(valid_inc
);
1543 valid_inc
= isl_set_intersect(valid_inc
, valid_cond_next
);
1544 valid_inc
= isl_set_intersect(valid_inc
, valid_cond_init
);
1545 valid_inc
= isl_set_project_out(valid_inc
, isl_dim_set
, pos
, 1);
1546 scop
= pet_scop_restrict_context(scop
, valid_inc
);
1547 scop
= set_independence(scop
, tree
, domain
, isl_val_sgn(inc
),
1549 isl_set_free(domain
);
1554 valid_init
= isl_set_project_out(valid_init
, isl_dim_set
, pos
, 1);
1555 scop
= pet_scop_restrict_context(scop
, valid_init
);
1557 pet_context_free(pc
);
1561 /* Construct a pet_scop for a for statement within the context of "pc".
1563 * We update the context to reflect the writes to the loop variable and
1564 * the writes inside the body.
1566 * Then we check if the initialization of the for loop
1567 * is a static affine value and the increment is a constant.
1568 * If so, we construct the pet_scop using scop_from_affine_for.
1569 * Otherwise, we treat the for loop as a while loop
1570 * in scop_from_non_affine_for.
1572 * Note that the initialization and the increment are extracted
1573 * in a context where the current loop iterator has been added
1574 * to the context. If these turn out not be affine, then we
1575 * have reconstruct the body context without an assignment
1576 * to this loop iterator, as this variable will then not be
1577 * treated as a dimension of the iteration domain, but as any
1580 static struct pet_scop
*scop_from_for(__isl_keep pet_tree
*tree
,
1581 __isl_keep pet_context
*init_pc
, struct pet_state
*state
)
1585 isl_pw_aff
*pa_inc
, *init_val
;
1586 pet_context
*pc
, *pc_init_val
;
1591 iv
= pet_expr_access_get_id(tree
->u
.l
.iv
);
1592 pc
= pet_context_copy(init_pc
);
1593 pc
= pet_context_add_inner_iterator(pc
, iv
);
1594 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.l
.body
);
1596 pc_init_val
= pet_context_copy(pc
);
1597 pc_init_val
= pet_context_clear_value(pc_init_val
, isl_id_copy(iv
));
1598 init_val
= pet_expr_extract_affine(tree
->u
.l
.init
, pc_init_val
);
1599 pet_context_free(pc_init_val
);
1600 pa_inc
= pet_expr_extract_affine(tree
->u
.l
.inc
, pc
);
1601 inc
= pet_extract_cst(pa_inc
);
1602 if (!pa_inc
|| !init_val
|| !inc
)
1604 if (!isl_pw_aff_involves_nan(pa_inc
) &&
1605 !isl_pw_aff_involves_nan(init_val
) && !isl_val_is_nan(inc
))
1606 return scop_from_affine_for(tree
, init_val
, pa_inc
, inc
,
1609 isl_pw_aff_free(pa_inc
);
1610 isl_pw_aff_free(init_val
);
1612 pet_context_free(pc
);
1614 pc
= pet_context_copy(init_pc
);
1615 pc
= pet_context_add_infinite_loop(pc
);
1616 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.l
.body
);
1617 return scop_from_non_affine_for(tree
, init_pc
, pc
, state
);
1619 isl_pw_aff_free(pa_inc
);
1620 isl_pw_aff_free(init_val
);
1622 pet_context_free(pc
);
1626 /* Check whether "expr" is an affine constraint within the context "pc".
1628 static int is_affine_condition(__isl_keep pet_expr
*expr
,
1629 __isl_keep pet_context
*pc
)
1634 pa
= pet_expr_extract_affine_condition(expr
, pc
);
1637 is_affine
= !isl_pw_aff_involves_nan(pa
);
1638 isl_pw_aff_free(pa
);
1643 /* Check if the given if statement is a conditional assignement
1644 * with a non-affine condition.
1646 * In particular we check if "stmt" is of the form
1653 * where the condition is non-affine and a is some array or scalar access.
1655 static int is_conditional_assignment(__isl_keep pet_tree
*tree
,
1656 __isl_keep pet_context
*pc
)
1660 pet_expr
*expr1
, *expr2
;
1662 ctx
= pet_tree_get_ctx(tree
);
1663 if (!pet_options_get_detect_conditional_assignment(ctx
))
1665 if (tree
->type
!= pet_tree_if_else
)
1667 if (tree
->u
.i
.then_body
->type
!= pet_tree_expr
)
1669 if (tree
->u
.i
.else_body
->type
!= pet_tree_expr
)
1671 expr1
= tree
->u
.i
.then_body
->u
.e
.expr
;
1672 expr2
= tree
->u
.i
.else_body
->u
.e
.expr
;
1673 if (pet_expr_get_type(expr1
) != pet_expr_op
)
1675 if (pet_expr_get_type(expr2
) != pet_expr_op
)
1677 if (pet_expr_op_get_type(expr1
) != pet_op_assign
)
1679 if (pet_expr_op_get_type(expr2
) != pet_op_assign
)
1681 expr1
= pet_expr_get_arg(expr1
, 0);
1682 expr2
= pet_expr_get_arg(expr2
, 0);
1683 equal
= pet_expr_is_equal(expr1
, expr2
);
1684 pet_expr_free(expr1
);
1685 pet_expr_free(expr2
);
1686 if (equal
< 0 || !equal
)
1688 if (is_affine_condition(tree
->u
.i
.cond
, pc
))
1694 /* Given that "tree" is of the form
1701 * where a is some array or scalar access, construct a pet_scop
1702 * corresponding to this conditional assignment within the context "pc".
1704 * The constructed pet_scop then corresponds to the expression
1706 * a = condition ? f(...) : g(...)
1708 * All access relations in f(...) are intersected with condition
1709 * while all access relation in g(...) are intersected with the complement.
1711 static struct pet_scop
*scop_from_conditional_assignment(
1712 __isl_keep pet_tree
*tree
, __isl_take pet_context
*pc
,
1713 struct pet_state
*state
)
1717 isl_set
*cond
, *comp
;
1718 isl_multi_pw_aff
*index
;
1719 pet_expr
*expr1
, *expr2
;
1720 pet_expr
*pe_cond
, *pe_then
, *pe_else
, *pe
, *pe_write
;
1721 pet_context
*pc_nested
;
1722 struct pet_scop
*scop
;
1724 pe_cond
= pet_expr_copy(tree
->u
.i
.cond
);
1725 pe_cond
= pet_context_evaluate_expr(pc
, pe_cond
);
1726 pc_nested
= pet_context_copy(pc
);
1727 pc_nested
= pet_context_set_allow_nested(pc_nested
, 1);
1728 pa
= pet_expr_extract_affine_condition(pe_cond
, pc_nested
);
1729 pet_context_free(pc_nested
);
1730 pet_expr_free(pe_cond
);
1731 cond
= isl_pw_aff_non_zero_set(isl_pw_aff_copy(pa
));
1732 comp
= isl_pw_aff_zero_set(isl_pw_aff_copy(pa
));
1733 index
= isl_multi_pw_aff_from_pw_aff(pa
);
1735 expr1
= tree
->u
.i
.then_body
->u
.e
.expr
;
1736 expr2
= tree
->u
.i
.else_body
->u
.e
.expr
;
1738 pe_cond
= pet_expr_from_index(index
);
1740 pe_then
= pet_expr_get_arg(expr1
, 1);
1741 pe_then
= pet_context_evaluate_expr(pc
, pe_then
);
1742 pe_then
= pet_expr_restrict(pe_then
, cond
);
1743 pe_else
= pet_expr_get_arg(expr2
, 1);
1744 pe_else
= pet_context_evaluate_expr(pc
, pe_else
);
1745 pe_else
= pet_expr_restrict(pe_else
, comp
);
1746 pe_write
= pet_expr_get_arg(expr1
, 0);
1747 pe_write
= pet_context_evaluate_expr(pc
, pe_write
);
1749 pe
= pet_expr_new_ternary(pe_cond
, pe_then
, pe_else
);
1750 type_size
= pet_expr_get_type_size(pe_write
);
1751 pe
= pet_expr_new_binary(type_size
, pet_op_assign
, pe_write
, pe
);
1753 scop
= scop_from_evaluated_expr(pe
, state
->n_stmt
++,
1754 pet_tree_get_loc(tree
), pc
);
1756 pet_context_free(pc
);
1761 /* Construct a pet_scop for a non-affine if statement within the context "pc".
1763 * We create a separate statement that writes the result
1764 * of the non-affine condition to a virtual scalar.
1765 * A constraint requiring the value of this virtual scalar to be one
1766 * is added to the iteration domains of the then branch.
1767 * Similarly, a constraint requiring the value of this virtual scalar
1768 * to be zero is added to the iteration domains of the else branch, if any.
1769 * We adjust the schedules to ensure that the virtual scalar is written
1770 * before it is read.
1772 * If there are any breaks or continues in the then and/or else
1773 * branches, then we may have to compute a new skip condition.
1774 * This is handled using a pet_skip_info object.
1775 * On initialization, the object checks if skip conditions need
1776 * to be computed. If so, it does so in pet_skip_info_if_extract_index and
1777 * adds them in pet_skip_info_if_add.
1779 static struct pet_scop
*scop_from_non_affine_if(__isl_keep pet_tree
*tree
,
1780 __isl_take pet_context
*pc
, struct pet_state
*state
)
1785 isl_multi_pw_aff
*test_index
;
1786 struct pet_skip_info skip
;
1787 struct pet_scop
*scop
, *scop_then
, *scop_else
= NULL
;
1789 has_else
= tree
->type
== pet_tree_if_else
;
1791 space
= pet_context_get_space(pc
);
1792 test_index
= pet_create_test_index(space
, state
->n_test
++);
1793 scop
= scop_from_non_affine_condition(pet_expr_copy(tree
->u
.i
.cond
),
1794 state
->n_stmt
++, isl_multi_pw_aff_copy(test_index
),
1795 pet_tree_get_loc(tree
), pc
);
1796 domain
= pet_context_get_domain(pc
);
1797 scop
= pet_scop_add_boolean_array(scop
, domain
,
1798 isl_multi_pw_aff_copy(test_index
), state
->int_size
);
1800 scop_then
= scop_from_tree(tree
->u
.i
.then_body
, pc
, state
);
1802 scop_else
= scop_from_tree(tree
->u
.i
.else_body
, pc
, state
);
1804 pet_skip_info_if_init(&skip
, state
->ctx
, scop_then
, scop_else
,
1806 pet_skip_info_if_extract_index(&skip
, test_index
, pc
, state
);
1808 scop
= pet_scop_prefix(scop
, 0);
1809 scop_then
= pet_scop_prefix(scop_then
, 1);
1810 scop_then
= pet_scop_filter(scop_then
,
1811 isl_multi_pw_aff_copy(test_index
), 1);
1813 scop_else
= pet_scop_prefix(scop_else
, 1);
1814 scop_else
= pet_scop_filter(scop_else
, test_index
, 0);
1815 scop_then
= pet_scop_add_par(state
->ctx
, scop_then
, scop_else
);
1817 isl_multi_pw_aff_free(test_index
);
1819 scop
= pet_scop_add_seq(state
->ctx
, scop
, scop_then
);
1821 scop
= pet_skip_info_if_add(&skip
, scop
, 2);
1823 pet_context_free(pc
);
1827 /* Construct a pet_scop for an affine if statement within the context "pc".
1829 * The condition is added to the iteration domains of the then branch,
1830 * while the opposite of the condition in added to the iteration domains
1831 * of the else branch, if any.
1833 * If there are any breaks or continues in the then and/or else
1834 * branches, then we may have to compute a new skip condition.
1835 * This is handled using a pet_skip_info_if object.
1836 * On initialization, the object checks if skip conditions need
1837 * to be computed. If so, it does so in pet_skip_info_if_extract_cond and
1838 * adds them in pet_skip_info_if_add.
1840 static struct pet_scop
*scop_from_affine_if(__isl_keep pet_tree
*tree
,
1841 __isl_take isl_pw_aff
*cond
, __isl_take pet_context
*pc
,
1842 struct pet_state
*state
)
1846 isl_set
*set
, *complement
;
1848 struct pet_skip_info skip
;
1849 struct pet_scop
*scop
, *scop_then
, *scop_else
= NULL
;
1850 pet_context
*pc_body
;
1852 ctx
= pet_tree_get_ctx(tree
);
1854 has_else
= tree
->type
== pet_tree_if_else
;
1856 valid
= isl_pw_aff_domain(isl_pw_aff_copy(cond
));
1857 set
= isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond
));
1859 pc_body
= pet_context_copy(pc
);
1860 pc_body
= pet_context_intersect_domain(pc_body
, isl_set_copy(set
));
1861 scop_then
= scop_from_tree(tree
->u
.i
.then_body
, pc_body
, state
);
1862 pet_context_free(pc_body
);
1864 pc_body
= pet_context_copy(pc
);
1865 complement
= isl_set_copy(valid
);
1866 complement
= isl_set_subtract(valid
, isl_set_copy(set
));
1867 pc_body
= pet_context_intersect_domain(pc_body
,
1868 isl_set_copy(complement
));
1869 scop_else
= scop_from_tree(tree
->u
.i
.else_body
, pc_body
, state
);
1870 pet_context_free(pc_body
);
1873 pet_skip_info_if_init(&skip
, ctx
, scop_then
, scop_else
, has_else
, 1);
1874 pet_skip_info_if_extract_cond(&skip
, cond
, pc
, state
);
1875 isl_pw_aff_free(cond
);
1877 scop
= pet_scop_restrict(scop_then
, set
);
1880 scop_else
= pet_scop_restrict(scop_else
, complement
);
1881 scop
= pet_scop_add_par(ctx
, scop
, scop_else
);
1883 scop
= pet_scop_resolve_nested(scop
);
1884 scop
= pet_scop_restrict_context(scop
, valid
);
1886 if (pet_skip_info_has_skip(&skip
))
1887 scop
= pet_scop_prefix(scop
, 0);
1888 scop
= pet_skip_info_if_add(&skip
, scop
, 1);
1890 pet_context_free(pc
);
1894 /* Construct a pet_scop for an if statement within the context "pc".
1896 * If the condition fits the pattern of a conditional assignment,
1897 * then it is handled by scop_from_conditional_assignment.
1899 * Otherwise, we check if the condition is affine.
1900 * If so, we construct the scop in scop_from_affine_if.
1901 * Otherwise, we construct the scop in scop_from_non_affine_if.
1903 * We allow the condition to be dynamic, i.e., to refer to
1904 * scalars or array elements that may be written to outside
1905 * of the given if statement. These nested accesses are then represented
1906 * as output dimensions in the wrapping iteration domain.
1907 * If it is also written _inside_ the then or else branch, then
1908 * we treat the condition as non-affine.
1909 * As explained in extract_non_affine_if, this will introduce
1910 * an extra statement.
1911 * For aesthetic reasons, we want this statement to have a statement
1912 * number that is lower than those of the then and else branches.
1913 * In order to evaluate if we will need such a statement, however, we
1914 * first construct scops for the then and else branches.
1915 * We therefore reserve a statement number if we might have to
1916 * introduce such an extra statement.
1918 static struct pet_scop
*scop_from_if(__isl_keep pet_tree
*tree
,
1919 __isl_keep pet_context
*pc
, struct pet_state
*state
)
1923 pet_expr
*cond_expr
;
1924 pet_context
*pc_nested
;
1929 has_else
= tree
->type
== pet_tree_if_else
;
1931 pc
= pet_context_copy(pc
);
1932 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.i
.then_body
);
1934 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.i
.else_body
);
1936 if (is_conditional_assignment(tree
, pc
))
1937 return scop_from_conditional_assignment(tree
, pc
, state
);
1939 cond_expr
= pet_expr_copy(tree
->u
.i
.cond
);
1940 cond_expr
= pet_context_evaluate_expr(pc
, cond_expr
);
1941 pc_nested
= pet_context_copy(pc
);
1942 pc_nested
= pet_context_set_allow_nested(pc_nested
, 1);
1943 cond
= pet_expr_extract_affine_condition(cond_expr
, pc_nested
);
1944 pet_context_free(pc_nested
);
1945 pet_expr_free(cond_expr
);
1948 pet_context_free(pc
);
1952 if (isl_pw_aff_involves_nan(cond
)) {
1953 isl_pw_aff_free(cond
);
1954 return scop_from_non_affine_if(tree
, pc
, state
);
1957 if ((!is_nested_allowed(cond
, tree
->u
.i
.then_body
) ||
1958 (has_else
&& !is_nested_allowed(cond
, tree
->u
.i
.else_body
)))) {
1959 isl_pw_aff_free(cond
);
1960 return scop_from_non_affine_if(tree
, pc
, state
);
1963 return scop_from_affine_if(tree
, cond
, pc
, state
);
1966 /* Return a one-dimensional multi piecewise affine expression that is equal
1967 * to the constant 1 and is defined over the given domain.
1969 static __isl_give isl_multi_pw_aff
*one_mpa(__isl_take isl_space
*space
)
1971 isl_local_space
*ls
;
1974 ls
= isl_local_space_from_space(space
);
1975 aff
= isl_aff_zero_on_domain(ls
);
1976 aff
= isl_aff_set_constant_si(aff
, 1);
1978 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1981 /* Construct a pet_scop for a continue statement with the given domain space.
1983 * We simply create an empty scop with a universal pet_skip_now
1984 * skip condition. This skip condition will then be taken into
1985 * account by the enclosing loop construct, possibly after
1986 * being incorporated into outer skip conditions.
1988 static struct pet_scop
*scop_from_continue(__isl_keep pet_tree
*tree
,
1989 __isl_take isl_space
*space
)
1991 struct pet_scop
*scop
;
1993 scop
= pet_scop_empty(isl_space_copy(space
));
1995 scop
= pet_scop_set_skip(scop
, pet_skip_now
, one_mpa(space
));
2000 /* Construct a pet_scop for a break statement with the given domain space.
2002 * We simply create an empty scop with both a universal pet_skip_now
2003 * skip condition and a universal pet_skip_later skip condition.
2004 * These skip conditions will then be taken into
2005 * account by the enclosing loop construct, possibly after
2006 * being incorporated into outer skip conditions.
2008 static struct pet_scop
*scop_from_break(__isl_keep pet_tree
*tree
,
2009 __isl_take isl_space
*space
)
2011 struct pet_scop
*scop
;
2012 isl_multi_pw_aff
*skip
;
2014 scop
= pet_scop_empty(isl_space_copy(space
));
2016 skip
= one_mpa(space
);
2017 scop
= pet_scop_set_skip(scop
, pet_skip_now
,
2018 isl_multi_pw_aff_copy(skip
));
2019 scop
= pet_scop_set_skip(scop
, pet_skip_later
, skip
);
2024 /* Extract a clone of the kill statement in "scop".
2025 * The domain of the clone is given by "domain".
2026 * "scop" is expected to have been created from a DeclStmt
2027 * and should have the kill as its first statement.
2029 static struct pet_scop
*extract_kill(__isl_keep isl_set
*domain
,
2030 struct pet_scop
*scop
, struct pet_state
*state
)
2033 struct pet_stmt
*stmt
;
2035 isl_multi_pw_aff
*mpa
;
2038 if (!domain
|| !scop
)
2040 if (scop
->n_stmt
< 1)
2041 isl_die(isl_set_get_ctx(domain
), isl_error_internal
,
2042 "expecting at least one statement", return NULL
);
2043 stmt
= scop
->stmts
[0];
2044 if (!pet_stmt_is_kill(stmt
))
2045 isl_die(isl_set_get_ctx(domain
), isl_error_internal
,
2046 "expecting kill statement", return NULL
);
2048 kill
= pet_tree_expr_get_expr(stmt
->body
);
2049 space
= pet_stmt_get_space(stmt
);
2050 space
= isl_space_map_from_set(space
);
2051 mpa
= isl_multi_pw_aff_identity(space
);
2052 mpa
= isl_multi_pw_aff_reset_tuple_id(mpa
, isl_dim_in
);
2053 kill
= pet_expr_update_domain(kill
, mpa
);
2054 tree
= pet_tree_new_expr(kill
);
2055 tree
= pet_tree_set_loc(tree
, pet_loc_copy(stmt
->loc
));
2056 stmt
= pet_stmt_from_pet_tree(isl_set_copy(domain
),
2057 state
->n_stmt
++, tree
);
2058 return pet_scop_from_pet_stmt(isl_set_get_space(domain
), stmt
);
2061 /* Does "tree" represent an assignment to a variable?
2063 * The assignment may be one of
2064 * - a declaration with initialization
2065 * - an expression with a top-level assignment operator
2067 static int is_assignment(__isl_keep pet_tree
*tree
)
2071 if (tree
->type
== pet_tree_decl_init
)
2073 return pet_tree_is_assign(tree
);
2076 /* Update "pc" by taking into account the assignment performed by "tree",
2077 * where "tree" satisfies is_assignment.
2079 * In particular, if the lhs of the assignment is a scalar variable and
2080 * if the rhs is an affine expression, then keep track of this value in "pc"
2081 * so that we can plug it in when we later come across the same variable.
2083 * Any previously assigned value to the variable has already been removed
2084 * by scop_handle_writes.
2086 static __isl_give pet_context
*handle_assignment(__isl_take pet_context
*pc
,
2087 __isl_keep pet_tree
*tree
)
2089 pet_expr
*var
, *val
;
2093 if (pet_tree_get_type(tree
) == pet_tree_decl_init
) {
2094 var
= pet_tree_decl_get_var(tree
);
2095 val
= pet_tree_decl_get_init(tree
);
2098 expr
= pet_tree_expr_get_expr(tree
);
2099 var
= pet_expr_get_arg(expr
, 0);
2100 val
= pet_expr_get_arg(expr
, 1);
2101 pet_expr_free(expr
);
2104 if (!pet_expr_is_scalar_access(var
)) {
2110 pa
= pet_expr_extract_affine(val
, pc
);
2112 pc
= pet_context_free(pc
);
2114 if (!isl_pw_aff_involves_nan(pa
)) {
2115 id
= pet_expr_access_get_id(var
);
2116 pc
= pet_context_set_value(pc
, id
, pa
);
2118 isl_pw_aff_free(pa
);
2126 /* Mark all arrays in "scop" as being exposed.
2128 static struct pet_scop
*mark_exposed(struct pet_scop
*scop
)
2134 for (i
= 0; i
< scop
->n_array
; ++i
)
2135 scop
->arrays
[i
]->exposed
= 1;
2139 /* Try and construct a pet_scop corresponding to (part of)
2140 * a sequence of statements within the context "pc".
2142 * After extracting a statement, we update "pc"
2143 * based on the top-level assignments in the statement
2144 * so that we can exploit them in subsequent statements in the same block.
2146 * If there are any breaks or continues in the individual statements,
2147 * then we may have to compute a new skip condition.
2148 * This is handled using a pet_skip_info object.
2149 * On initialization, the object checks if skip conditions need
2150 * to be computed. If so, it does so in pet_skip_info_seq_extract and
2151 * adds them in pet_skip_info_seq_add.
2153 * If "block" is set, then we need to insert kill statements at
2154 * the end of the block for any array that has been declared by
2155 * one of the statements in the sequence. Each of these declarations
2156 * results in the construction of a kill statement at the place
2157 * of the declaration, so we simply collect duplicates of
2158 * those kill statements and append these duplicates to the constructed scop.
2160 * If "block" is not set, then any array declared by one of the statements
2161 * in the sequence is marked as being exposed.
2163 * If autodetect is set, then we allow the extraction of only a subrange
2164 * of the sequence of statements. However, if there is at least one statement
2165 * for which we could not construct a scop and the final range contains
2166 * either no statements or at least one kill, then we discard the entire
2169 static struct pet_scop
*scop_from_block(__isl_keep pet_tree
*tree
,
2170 __isl_keep pet_context
*pc
, struct pet_state
*state
)
2176 struct pet_scop
*scop
, *kills
;
2178 ctx
= pet_tree_get_ctx(tree
);
2180 space
= pet_context_get_space(pc
);
2181 domain
= pet_context_get_domain(pc
);
2182 pc
= pet_context_copy(pc
);
2183 scop
= pet_scop_empty(isl_space_copy(space
));
2184 kills
= pet_scop_empty(space
);
2185 for (i
= 0; i
< tree
->u
.b
.n
; ++i
) {
2186 struct pet_scop
*scop_i
;
2188 if (pet_scop_has_affine_skip(scop
, pet_skip_now
))
2189 pc
= apply_affine_continue(pc
, scop
);
2190 scop_i
= scop_from_tree(tree
->u
.b
.child
[i
], pc
, state
);
2191 pc
= scop_handle_writes(scop_i
, pc
);
2192 if (is_assignment(tree
->u
.b
.child
[i
]))
2193 pc
= handle_assignment(pc
, tree
->u
.b
.child
[i
]);
2194 struct pet_skip_info skip
;
2195 pet_skip_info_seq_init(&skip
, ctx
, scop
, scop_i
);
2196 pet_skip_info_seq_extract(&skip
, pc
, state
);
2197 if (pet_skip_info_has_skip(&skip
))
2198 scop_i
= pet_scop_prefix(scop_i
, 0);
2199 if (scop_i
&& pet_tree_is_decl(tree
->u
.b
.child
[i
])) {
2200 if (tree
->u
.b
.block
) {
2201 struct pet_scop
*kill
;
2202 kill
= extract_kill(domain
, scop_i
, state
);
2203 kills
= pet_scop_add_par(ctx
, kills
, kill
);
2205 scop_i
= mark_exposed(scop_i
);
2207 scop_i
= pet_scop_prefix(scop_i
, i
);
2208 scop
= pet_scop_add_seq(ctx
, scop
, scop_i
);
2210 scop
= pet_skip_info_seq_add(&skip
, scop
, i
);
2215 isl_set_free(domain
);
2217 kills
= pet_scop_prefix(kills
, tree
->u
.b
.n
);
2218 scop
= pet_scop_add_seq(ctx
, scop
, kills
);
2220 pet_context_free(pc
);
2225 /* Internal data structure for extract_declared_arrays.
2227 * "pc" and "state" are used to create pet_array objects and kill statements.
2228 * "any" is initialized to 0 by the caller and set to 1 as soon as we have
2229 * found any declared array.
2230 * "scop" has been initialized by the caller and is used to attach
2231 * the created pet_array objects.
2232 * "kill_before" and "kill_after" are created and updated by
2233 * extract_declared_arrays to collect the kills of the arrays.
2235 struct pet_tree_extract_declared_arrays_data
{
2237 struct pet_state
*state
;
2242 struct pet_scop
*scop
;
2243 struct pet_scop
*kill_before
;
2244 struct pet_scop
*kill_after
;
2247 /* Check if the node "node" declares any array or scalar.
2248 * If so, create the corresponding pet_array and attach it to data->scop.
2249 * Additionally, create two kill statements for the array and add them
2250 * to data->kill_before and data->kill_after.
2252 static int extract_declared_arrays(__isl_keep pet_tree
*node
, void *user
)
2254 enum pet_tree_type type
;
2255 struct pet_tree_extract_declared_arrays_data
*data
= user
;
2256 struct pet_array
*array
;
2257 struct pet_scop
*scop_kill
;
2260 type
= pet_tree_get_type(node
);
2261 if (type
== pet_tree_decl
|| type
== pet_tree_decl_init
)
2262 var
= node
->u
.d
.var
;
2263 else if (type
== pet_tree_for
&& node
->u
.l
.declared
)
2268 array
= extract_array(var
, data
->pc
, data
->state
);
2270 array
->declared
= 1;
2271 data
->scop
= pet_scop_add_array(data
->scop
, array
);
2273 scop_kill
= kill(pet_tree_get_loc(node
), array
, data
->pc
, data
->state
);
2275 data
->kill_before
= scop_kill
;
2277 data
->kill_before
= pet_scop_add_par(data
->ctx
,
2278 data
->kill_before
, scop_kill
);
2280 scop_kill
= kill(pet_tree_get_loc(node
), array
, data
->pc
, data
->state
);
2282 data
->kill_after
= scop_kill
;
2284 data
->kill_after
= pet_scop_add_par(data
->ctx
,
2285 data
->kill_after
, scop_kill
);
2292 /* Convert a pet_tree that consists of more than a single leaf
2293 * to a pet_scop with a single statement encapsulating the entire pet_tree.
2294 * Do so within the context of "pc".
2296 * After constructing the core scop, we also look for any arrays (or scalars)
2297 * that are declared inside "tree". Each of those arrays is marked as
2298 * having been declared and kill statements for these arrays
2299 * are introduced before and after the core scop.
2300 * Note that the input tree is not a leaf so that the declaration
2301 * cannot occur at the outer level.
2303 static struct pet_scop
*scop_from_tree_macro(__isl_take pet_tree
*tree
,
2304 __isl_take isl_id
*label
, __isl_keep pet_context
*pc
,
2305 struct pet_state
*state
)
2307 struct pet_tree_extract_declared_arrays_data data
= { pc
, state
};
2309 data
.scop
= scop_from_unevaluated_tree(pet_tree_copy(tree
),
2310 state
->n_stmt
++, pc
);
2313 data
.ctx
= pet_context_get_ctx(pc
);
2314 if (pet_tree_foreach_sub_tree(tree
, &extract_declared_arrays
,
2316 data
.scop
= pet_scop_free(data
.scop
);
2317 pet_tree_free(tree
);
2322 data
.kill_before
= pet_scop_prefix(data
.kill_before
, 0);
2323 data
.scop
= pet_scop_prefix(data
.scop
, 1);
2324 data
.kill_after
= pet_scop_prefix(data
.kill_after
, 2);
2326 data
.scop
= pet_scop_add_seq(data
.ctx
, data
.kill_before
, data
.scop
);
2327 data
.scop
= pet_scop_add_seq(data
.ctx
, data
.scop
, data
.kill_after
);
2332 /* Construct a pet_scop that corresponds to the pet_tree "tree"
2333 * within the context "pc" by calling the appropriate function
2334 * based on the type of "tree".
2336 * If the initially constructed pet_scop turns out to involve
2337 * dynamic control and if the user has requested an encapsulation
2338 * of all dynamic control, then this pet_scop is discarded and
2339 * a new pet_scop is created with a single statement representing
2340 * the entire "tree".
2341 * However, if the scop contains any active continue or break,
2342 * then we need to include the loop containing the continue or break
2343 * in the encapsulation. We therefore postpone the encapsulation
2344 * until we have constructed a pet_scop for this enclosing loop.
2346 static struct pet_scop
*scop_from_tree(__isl_keep pet_tree
*tree
,
2347 __isl_keep pet_context
*pc
, struct pet_state
*state
)
2350 struct pet_scop
*scop
= NULL
;
2355 ctx
= pet_tree_get_ctx(tree
);
2356 switch (tree
->type
) {
2357 case pet_tree_error
:
2359 case pet_tree_block
:
2360 return scop_from_block(tree
, pc
, state
);
2361 case pet_tree_break
:
2362 return scop_from_break(tree
, pet_context_get_space(pc
));
2363 case pet_tree_continue
:
2364 return scop_from_continue(tree
, pet_context_get_space(pc
));
2366 case pet_tree_decl_init
:
2367 return scop_from_decl(tree
, pc
, state
);
2369 return scop_from_tree_expr(tree
, pc
, state
);
2371 case pet_tree_if_else
:
2372 scop
= scop_from_if(tree
, pc
, state
);
2375 scop
= scop_from_for(tree
, pc
, state
);
2377 case pet_tree_while
:
2378 scop
= scop_from_while(tree
, pc
, state
);
2380 case pet_tree_infinite_loop
:
2381 scop
= scop_from_infinite_for(tree
, pc
, state
);
2388 if (!pet_options_get_encapsulate_dynamic_control(ctx
) ||
2389 !pet_scop_has_data_dependent_conditions(scop
) ||
2390 pet_scop_has_var_skip(scop
, pet_skip_now
))
2393 pet_scop_free(scop
);
2394 return scop_from_tree_macro(pet_tree_copy(tree
),
2395 isl_id_copy(tree
->label
), pc
, state
);
2398 /* Construct a pet_scop that corresponds to the pet_tree "tree".
2399 * "int_size" is the number of bytes need to represent an integer.
2400 * "extract_array" is a callback that we can use to create a pet_array
2401 * that corresponds to the variable accessed by an expression.
2403 * Initialize the global state, construct a context and then
2404 * construct the pet_scop by recursively visiting the tree.
2406 struct pet_scop
*pet_scop_from_pet_tree(__isl_take pet_tree
*tree
, int int_size
,
2407 struct pet_array
*(*extract_array
)(__isl_keep pet_expr
*access
,
2408 __isl_keep pet_context
*pc
, void *user
), void *user
,
2409 __isl_keep pet_context
*pc
)
2411 struct pet_scop
*scop
;
2412 struct pet_state state
= { 0 };
2417 state
.ctx
= pet_tree_get_ctx(tree
);
2418 state
.int_size
= int_size
;
2419 state
.extract_array
= extract_array
;
2422 scop
= scop_from_tree(tree
, pc
, &state
);
2423 scop
= pet_scop_set_loc(scop
, pet_tree_get_loc(tree
));
2425 pet_tree_free(tree
);
2428 scop
->context
= isl_set_params(scop
->context
);