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, mark all scalar variables that are written by "stmt"
48 * as having an unknown value.
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_expr(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
)
88 space
= pet_context_get_space(pc
);
90 expr
= pet_expr_resolve_nested(expr
, space
);
91 expr
= pet_expr_resolve_assume(expr
, pc
);
92 domain
= pet_context_get_domain(pc
);
93 ps
= pet_stmt_from_pet_expr(domain
, loc
, label
, stmt_nr
, expr
);
94 return pet_scop_from_pet_stmt(space
, ps
);
97 /* Convert a top-level pet_expr to a pet_scop with one statement
98 * within the context "pc", where "expr" has not yet been evaluated
99 * in the context of "pc".
100 * We evaluate "expr" in the context of "pc" and continue with
101 * scop_from_evaluated_expr.
102 * The statement name is given by "label" if it is non-NULL. Otherwise,
103 * it is of the form S_<stmt_nr>.
104 * The location of the statement is set to "loc".
106 static struct pet_scop
*scop_from_expr(__isl_take pet_expr
*expr
,
107 __isl_take isl_id
*label
, int stmt_nr
, __isl_take pet_loc
*loc
,
108 __isl_keep pet_context
*pc
)
110 expr
= pet_context_evaluate_expr(pc
, expr
);
111 return scop_from_evaluated_expr(expr
, label
, stmt_nr
, loc
, pc
);
114 /* Construct a pet_scop with a single statement killing the entire
116 * The location of the statement is set to "loc".
118 static struct pet_scop
*kill(__isl_take pet_loc
*loc
, struct pet_array
*array
,
119 __isl_keep pet_context
*pc
, struct pet_state
*state
)
124 isl_multi_pw_aff
*index
;
127 struct pet_scop
*scop
;
131 ctx
= isl_set_get_ctx(array
->extent
);
132 access
= isl_map_from_range(isl_set_copy(array
->extent
));
133 id
= isl_set_get_tuple_id(array
->extent
);
134 space
= isl_space_alloc(ctx
, 0, 0, 0);
135 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
136 index
= isl_multi_pw_aff_zero(space
);
137 expr
= pet_expr_kill_from_access_and_index(access
, index
);
138 return scop_from_expr(expr
, NULL
, state
->n_stmt
++, loc
, pc
);
144 /* Construct and return a pet_array corresponding to the variable
145 * accessed by "access" by calling the extract_array callback.
147 static struct pet_array
*extract_array(__isl_keep pet_expr
*access
,
148 __isl_keep pet_context
*pc
, struct pet_state
*state
)
150 return state
->extract_array(access
, pc
, state
->user
);
153 /* Construct a pet_scop for a (single) variable declaration
154 * within the context "pc".
156 * The scop contains the variable being declared (as an array)
157 * and a statement killing the array.
159 * If the declaration comes with an initialization, then the scop
160 * also contains an assignment to the variable.
162 static struct pet_scop
*scop_from_decl(__isl_keep pet_tree
*tree
,
163 __isl_keep pet_context
*pc
, struct pet_state
*state
)
167 struct pet_array
*array
;
168 struct pet_scop
*scop_decl
, *scop
;
169 pet_expr
*lhs
, *rhs
, *pe
;
171 array
= extract_array(tree
->u
.d
.var
, pc
, state
);
174 scop_decl
= kill(pet_tree_get_loc(tree
), array
, pc
, state
);
175 scop_decl
= pet_scop_add_array(scop_decl
, array
);
177 if (tree
->type
!= pet_tree_decl_init
)
180 lhs
= pet_expr_copy(tree
->u
.d
.var
);
181 rhs
= pet_expr_copy(tree
->u
.d
.init
);
182 type_size
= pet_expr_get_type_size(lhs
);
183 pe
= pet_expr_new_binary(type_size
, pet_op_assign
, lhs
, rhs
);
184 scop
= scop_from_expr(pe
, NULL
, state
->n_stmt
++,
185 pet_tree_get_loc(tree
), pc
);
187 scop_decl
= pet_scop_prefix(scop_decl
, 0);
188 scop
= pet_scop_prefix(scop
, 1);
190 ctx
= pet_tree_get_ctx(tree
);
191 scop
= pet_scop_add_seq(ctx
, scop_decl
, scop
);
196 /* Embed the given iteration domain in an extra outer loop
197 * with induction variable "var".
198 * If this variable appeared as a parameter in the constraints,
199 * it is replaced by the new outermost dimension.
201 static __isl_give isl_set
*embed(__isl_take isl_set
*set
,
202 __isl_take isl_id
*var
)
206 set
= isl_set_insert_dims(set
, isl_dim_set
, 0, 1);
207 pos
= isl_set_find_dim_by_id(set
, isl_dim_param
, var
);
209 set
= isl_set_equate(set
, isl_dim_param
, pos
, isl_dim_set
, 0);
210 set
= isl_set_project_out(set
, isl_dim_param
, pos
, 1);
217 /* Return those elements in the space of "cond" that come after
218 * (based on "sign") an element in "cond" in the final dimension.
220 static __isl_give isl_set
*after(__isl_take isl_set
*cond
, int sign
)
223 isl_map
*previous_to_this
;
226 dim
= isl_set_dim(cond
, isl_dim_set
);
227 space
= isl_space_map_from_set(isl_set_get_space(cond
));
228 previous_to_this
= isl_map_universe(space
);
229 for (i
= 0; i
+ 1 < dim
; ++i
)
230 previous_to_this
= isl_map_equate(previous_to_this
,
231 isl_dim_in
, i
, isl_dim_out
, i
);
233 previous_to_this
= isl_map_order_lt(previous_to_this
,
234 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
236 previous_to_this
= isl_map_order_gt(previous_to_this
,
237 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
239 cond
= isl_set_apply(cond
, previous_to_this
);
244 /* Remove those iterations of "domain" that have an earlier iteration
245 * (based on "sign") where "skip" is satisfied.
246 * "domain" has an extra outer loop compared to "skip".
247 * The skip condition is first embedded in the same space as "domain".
248 * If "apply_skip_map" is set, then "skip_map" is first applied
249 * to the embedded skip condition before removing it from the domain.
251 static __isl_give isl_set
*apply_affine_break(__isl_take isl_set
*domain
,
252 __isl_take isl_set
*skip
, int sign
,
253 int apply_skip_map
, __isl_keep isl_map
*skip_map
)
255 skip
= embed(skip
, isl_set_get_dim_id(domain
, isl_dim_set
, 0));
257 skip
= isl_set_apply(skip
, isl_map_copy(skip_map
));
258 skip
= isl_set_intersect(skip
, isl_set_copy(domain
));
259 return isl_set_subtract(domain
, after(skip
, sign
));
262 /* Create the infinite iteration domain
266 static __isl_give isl_set
*infinite_domain(__isl_take isl_id
*id
)
268 isl_ctx
*ctx
= isl_id_get_ctx(id
);
271 domain
= isl_set_nat_universe(isl_space_set_alloc(ctx
, 0, 1));
272 domain
= isl_set_set_dim_id(domain
, isl_dim_set
, 0, id
);
277 /* Create an identity affine expression on the space containing "domain",
278 * which is assumed to be one-dimensional.
280 static __isl_give isl_aff
*identity_aff(__isl_keep isl_set
*domain
)
284 ls
= isl_local_space_from_space(isl_set_get_space(domain
));
285 return isl_aff_var_on_domain(ls
, isl_dim_set
, 0);
288 /* Create an affine expression that maps elements
289 * of an array "id_test" to the previous element in the final dimension
290 * (according to "inc"), provided this element belongs to "domain".
291 * That is, create the affine expression
293 * { id[outer,x] -> id[outer,x - inc] : (outer,x - inc) in domain }
295 static __isl_give isl_multi_pw_aff
*map_to_previous(__isl_take isl_id
*id_test
,
296 __isl_take isl_set
*domain
, __isl_take isl_val
*inc
)
303 isl_multi_pw_aff
*prev
;
305 pos
= isl_set_dim(domain
, isl_dim_set
) - 1;
306 space
= isl_set_get_space(domain
);
307 space
= isl_space_map_from_set(space
);
308 ma
= isl_multi_aff_identity(space
);
309 aff
= isl_multi_aff_get_aff(ma
, pos
);
310 aff
= isl_aff_add_constant_val(aff
, isl_val_neg(inc
));
311 ma
= isl_multi_aff_set_aff(ma
, pos
, aff
);
312 domain
= isl_set_preimage_multi_aff(domain
, isl_multi_aff_copy(ma
));
313 prev
= isl_multi_pw_aff_from_multi_aff(ma
);
314 pa
= isl_multi_pw_aff_get_pw_aff(prev
, pos
);
315 pa
= isl_pw_aff_intersect_domain(pa
, domain
);
316 prev
= isl_multi_pw_aff_set_pw_aff(prev
, pos
, pa
);
317 prev
= isl_multi_pw_aff_set_tuple_id(prev
, isl_dim_out
, id_test
);
322 /* Add an implication to "scop" expressing that if an element of
323 * virtual array "id_test" has value "satisfied" then all previous elements
324 * of this array (in the final dimension) also have that value.
325 * The set of previous elements is bounded by "domain".
326 * If "sign" is negative then the iterator
327 * is decreasing and we express that all subsequent array elements
328 * (but still defined previously) have the same value.
330 static struct pet_scop
*add_implication(struct pet_scop
*scop
,
331 __isl_take isl_id
*id_test
, __isl_take isl_set
*domain
, int sign
,
338 dim
= isl_set_dim(domain
, isl_dim_set
);
339 domain
= isl_set_set_tuple_id(domain
, id_test
);
340 space
= isl_space_map_from_set(isl_set_get_space(domain
));
341 map
= isl_map_universe(space
);
342 for (i
= 0; i
+ 1 < dim
; ++i
)
343 map
= isl_map_equate(map
, isl_dim_in
, i
, isl_dim_out
, i
);
345 map
= isl_map_order_ge(map
,
346 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
348 map
= isl_map_order_le(map
,
349 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
350 map
= isl_map_intersect_range(map
, domain
);
351 scop
= pet_scop_add_implication(scop
, map
, satisfied
);
356 /* Add a filter to "scop" that imposes that it is only executed
357 * when the variable identified by "id_test" has a zero value
358 * for all previous iterations of "domain".
360 * In particular, add a filter that imposes that the array
361 * has a zero value at the previous iteration of domain and
362 * add an implication that implies that it then has that
363 * value for all previous iterations.
365 static struct pet_scop
*scop_add_break(struct pet_scop
*scop
,
366 __isl_take isl_id
*id_test
, __isl_take isl_set
*domain
,
367 __isl_take isl_val
*inc
)
369 isl_multi_pw_aff
*prev
;
370 int sign
= isl_val_sgn(inc
);
372 prev
= map_to_previous(isl_id_copy(id_test
), isl_set_copy(domain
), inc
);
373 scop
= add_implication(scop
, id_test
, domain
, sign
, 0);
374 scop
= pet_scop_filter(scop
, prev
, 0);
379 static struct pet_scop
*scop_from_tree(__isl_keep pet_tree
*tree
,
380 __isl_keep pet_context
*pc
, struct pet_state
*state
);
382 /* Construct a pet_scop for an infinite loop around the given body
383 * within the context "pc".
385 * We extract a pet_scop for the body and then embed it in a loop with
394 * If the body contains any break, then it is taken into
395 * account in apply_affine_break (if the skip condition is affine)
396 * or in scop_add_break (if the skip condition is not affine).
398 * Note that in case of an affine skip condition,
399 * since we are dealing with a loop without loop iterator,
400 * the skip condition cannot refer to the current loop iterator and
401 * so effectively, the iteration domain is of the form
403 * { [0]; [t] : t >= 1 and not skip }
405 static struct pet_scop
*scop_from_infinite_loop(__isl_keep pet_tree
*body
,
406 __isl_keep pet_context
*pc
, struct pet_state
*state
)
409 isl_id
*id
, *id_test
;
413 struct pet_scop
*scop
;
414 int has_affine_break
;
417 ctx
= pet_tree_get_ctx(body
);
418 id
= isl_id_alloc(ctx
, "t", NULL
);
419 domain
= infinite_domain(isl_id_copy(id
));
420 ident
= identity_aff(domain
);
422 scop
= scop_from_tree(body
, pc
, state
);
424 has_affine_break
= pet_scop_has_affine_skip(scop
, pet_skip_later
);
425 if (has_affine_break
)
426 skip
= pet_scop_get_affine_skip_domain(scop
, pet_skip_later
);
427 has_var_break
= pet_scop_has_var_skip(scop
, pet_skip_later
);
429 id_test
= pet_scop_get_skip_id(scop
, pet_skip_later
);
431 scop
= pet_scop_embed(scop
, isl_set_copy(domain
),
432 isl_aff_copy(ident
), ident
, id
);
433 if (has_affine_break
) {
434 domain
= apply_affine_break(domain
, skip
, 1, 0, NULL
);
435 scop
= pet_scop_intersect_domain_prefix(scop
,
436 isl_set_copy(domain
));
439 scop
= scop_add_break(scop
, id_test
, domain
, isl_val_one(ctx
));
441 isl_set_free(domain
);
446 /* Construct a pet_scop for an infinite loop, i.e., a loop of the form
451 * within the context "pc".
453 static struct pet_scop
*scop_from_infinite_for(__isl_keep pet_tree
*tree
,
454 __isl_keep pet_context
*pc
, struct pet_state
*state
)
456 struct pet_scop
*scop
;
458 pc
= pet_context_copy(pc
);
459 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.l
.body
);
461 scop
= scop_from_infinite_loop(tree
->u
.l
.body
, pc
, state
);
463 pet_context_free(pc
);
468 /* Construct a pet_scop for a while loop of the form
473 * within the context "pc".
474 * In particular, construct a scop for an infinite loop around body and
475 * intersect the domain with the affine expression.
476 * Note that this intersection may result in an empty loop.
478 static struct pet_scop
*scop_from_affine_while(__isl_keep pet_tree
*tree
,
479 __isl_take isl_pw_aff
*pa
, __isl_take pet_context
*pc
,
480 struct pet_state
*state
)
482 struct pet_scop
*scop
;
486 valid
= isl_pw_aff_domain(isl_pw_aff_copy(pa
));
487 dom
= isl_pw_aff_non_zero_set(pa
);
488 scop
= scop_from_infinite_loop(tree
->u
.l
.body
, pc
, state
);
489 scop
= pet_scop_restrict(scop
, isl_set_params(dom
));
490 scop
= pet_scop_restrict_context(scop
, isl_set_params(valid
));
492 pet_context_free(pc
);
496 /* Construct a scop for a while, given the scops for the condition
497 * and the body, the filter identifier and the iteration domain of
500 * In particular, the scop for the condition is filtered to depend
501 * on "id_test" evaluating to true for all previous iterations
502 * of the loop, while the scop for the body is filtered to depend
503 * on "id_test" evaluating to true for all iterations up to the
505 * The actual filter only imposes that this virtual array has
506 * value one on the previous or the current iteration.
507 * The fact that this condition also applies to the previous
508 * iterations is enforced by an implication.
510 * These filtered scops are then combined into a single scop.
512 * "sign" is positive if the iterator increases and negative
515 static struct pet_scop
*scop_add_while(struct pet_scop
*scop_cond
,
516 struct pet_scop
*scop_body
, __isl_take isl_id
*id_test
,
517 __isl_take isl_set
*domain
, __isl_take isl_val
*inc
)
519 isl_ctx
*ctx
= isl_set_get_ctx(domain
);
521 isl_multi_pw_aff
*test_index
;
522 isl_multi_pw_aff
*prev
;
523 int sign
= isl_val_sgn(inc
);
524 struct pet_scop
*scop
;
526 prev
= map_to_previous(isl_id_copy(id_test
), isl_set_copy(domain
), inc
);
527 scop_cond
= pet_scop_filter(scop_cond
, prev
, 1);
529 space
= isl_space_map_from_set(isl_set_get_space(domain
));
530 test_index
= isl_multi_pw_aff_identity(space
);
531 test_index
= isl_multi_pw_aff_set_tuple_id(test_index
, isl_dim_out
,
532 isl_id_copy(id_test
));
533 scop_body
= pet_scop_filter(scop_body
, test_index
, 1);
535 scop
= pet_scop_add_seq(ctx
, scop_cond
, scop_body
);
536 scop
= add_implication(scop
, id_test
, domain
, sign
, 1);
541 /* Create a pet_scop with a single statement with name S_<stmt_nr>,
542 * evaluating "cond" and writing the result to a virtual scalar,
543 * as expressed by "index".
544 * The expression "cond" has not yet been evaluated in the context of "pc".
545 * Do so within the context "pc".
546 * The location of the statement is set to "loc".
548 static struct pet_scop
*scop_from_non_affine_condition(
549 __isl_take pet_expr
*cond
, int stmt_nr
,
550 __isl_take isl_multi_pw_aff
*index
,
551 __isl_take pet_loc
*loc
, __isl_keep pet_context
*pc
)
553 pet_expr
*expr
, *write
;
555 cond
= pet_context_evaluate_expr(pc
, cond
);
557 write
= pet_expr_from_index(index
);
558 write
= pet_expr_access_set_write(write
, 1);
559 write
= pet_expr_access_set_read(write
, 0);
560 expr
= pet_expr_new_binary(1, pet_op_assign
, write
, cond
);
562 return scop_from_evaluated_expr(expr
, NULL
, stmt_nr
, loc
, pc
);
565 /* Construct a generic while scop, with iteration domain
566 * { [t] : t >= 0 } around the scop for "tree_body" within the context "pc".
567 * The scop consists of two parts,
568 * one for evaluating the condition "cond" and one for the body.
569 * If "expr_inc" is not NULL, then a scop for evaluating this expression
570 * is added at the end of the body,
571 * after replacing any skip conditions resulting from continue statements
572 * by the skip conditions resulting from break statements (if any).
574 * The schedule is adjusted to reflect that the condition is evaluated
575 * before the body is executed and the body is filtered to depend
576 * on the result of the condition evaluating to true on all iterations
577 * up to the current iteration, while the evaluation of the condition itself
578 * is filtered to depend on the result of the condition evaluating to true
579 * on all previous iterations.
580 * The context of the scop representing the body is dropped
581 * because we don't know how many times the body will be executed,
584 * If the body contains any break, then it is taken into
585 * account in apply_affine_break (if the skip condition is affine)
586 * or in scop_add_break (if the skip condition is not affine).
588 * Note that in case of an affine skip condition,
589 * since we are dealing with a loop without loop iterator,
590 * the skip condition cannot refer to the current loop iterator and
591 * so effectively, the iteration domain is of the form
593 * { [0]; [t] : t >= 1 and not skip }
595 static struct pet_scop
*scop_from_non_affine_while(__isl_take pet_expr
*cond
,
596 __isl_take pet_loc
*loc
, __isl_keep pet_tree
*tree_body
,
597 __isl_take pet_expr
*expr_inc
, __isl_take pet_context
*pc
,
598 struct pet_state
*state
)
601 isl_id
*id
, *id_test
, *id_break_test
;
603 isl_multi_pw_aff
*test_index
;
607 struct pet_scop
*scop
, *scop_body
;
608 int has_affine_break
;
612 space
= pet_context_get_space(pc
);
613 test_index
= pet_create_test_index(space
, state
->n_test
++);
614 scop
= scop_from_non_affine_condition(cond
, state
->n_stmt
++,
615 isl_multi_pw_aff_copy(test_index
),
616 pet_loc_copy(loc
), pc
);
617 id_test
= isl_multi_pw_aff_get_tuple_id(test_index
, isl_dim_out
);
618 domain
= pet_context_get_domain(pc
);
619 scop
= pet_scop_add_boolean_array(scop
, domain
,
620 test_index
, state
->int_size
);
622 id
= isl_id_alloc(ctx
, "t", NULL
);
623 domain
= infinite_domain(isl_id_copy(id
));
624 ident
= identity_aff(domain
);
626 scop_body
= scop_from_tree(tree_body
, pc
, state
);
628 has_affine_break
= pet_scop_has_affine_skip(scop_body
, pet_skip_later
);
629 if (has_affine_break
)
630 skip
= pet_scop_get_affine_skip_domain(scop_body
,
632 has_var_break
= pet_scop_has_var_skip(scop_body
, pet_skip_later
);
634 id_break_test
= pet_scop_get_skip_id(scop_body
, pet_skip_later
);
636 scop
= pet_scop_prefix(scop
, 0);
637 scop
= pet_scop_embed(scop
, isl_set_copy(domain
), isl_aff_copy(ident
),
638 isl_aff_copy(ident
), isl_id_copy(id
));
639 scop_body
= pet_scop_reset_context(scop_body
);
640 scop_body
= pet_scop_prefix(scop_body
, 1);
642 struct pet_scop
*scop_inc
;
643 scop_inc
= scop_from_expr(expr_inc
, NULL
, state
->n_stmt
++,
645 scop_inc
= pet_scop_prefix(scop_inc
, 2);
646 if (pet_scop_has_skip(scop_body
, pet_skip_later
)) {
647 isl_multi_pw_aff
*skip
;
648 skip
= pet_scop_get_skip(scop_body
, pet_skip_later
);
649 scop_body
= pet_scop_set_skip(scop_body
,
652 pet_scop_reset_skip(scop_body
, pet_skip_now
);
653 scop_body
= pet_scop_add_seq(ctx
, scop_body
, scop_inc
);
656 scop_body
= pet_scop_embed(scop_body
, isl_set_copy(domain
),
657 isl_aff_copy(ident
), ident
, id
);
659 if (has_affine_break
) {
660 domain
= apply_affine_break(domain
, skip
, 1, 0, NULL
);
661 scop
= pet_scop_intersect_domain_prefix(scop
,
662 isl_set_copy(domain
));
663 scop_body
= pet_scop_intersect_domain_prefix(scop_body
,
664 isl_set_copy(domain
));
667 scop
= scop_add_break(scop
, isl_id_copy(id_break_test
),
668 isl_set_copy(domain
), isl_val_one(ctx
));
669 scop_body
= scop_add_break(scop_body
, id_break_test
,
670 isl_set_copy(domain
), isl_val_one(ctx
));
672 scop
= scop_add_while(scop
, scop_body
, id_test
, domain
,
675 pet_context_free(pc
);
679 /* Check if the while loop is of the form
681 * while (affine expression)
684 * If so, call scop_from_affine_while to construct a scop.
686 * Otherwise, pass control to scop_from_non_affine_while.
688 * "pc" is the context in which the affine expressions in the scop are created.
690 static struct pet_scop
*scop_from_while(__isl_keep pet_tree
*tree
,
691 __isl_keep pet_context
*pc
, struct pet_state
*state
)
699 pc
= pet_context_copy(pc
);
700 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.l
.body
);
702 cond_expr
= pet_expr_copy(tree
->u
.l
.cond
);
703 cond_expr
= pet_context_evaluate_expr(pc
, cond_expr
);
704 pa
= pet_expr_extract_affine_condition(cond_expr
, pc
);
705 pet_expr_free(cond_expr
);
710 if (!isl_pw_aff_involves_nan(pa
))
711 return scop_from_affine_while(tree
, pa
, pc
, state
);
713 return scop_from_non_affine_while(pet_expr_copy(tree
->u
.l
.cond
),
714 pet_tree_get_loc(tree
), tree
->u
.l
.body
, NULL
,
717 pet_context_free(pc
);
721 /* Check whether "cond" expresses a simple loop bound
722 * on the final set dimension.
723 * In particular, if "up" is set then "cond" should contain only
724 * upper bounds on the final set dimension.
725 * Otherwise, it should contain only lower bounds.
727 static int is_simple_bound(__isl_keep isl_set
*cond
, __isl_keep isl_val
*inc
)
731 pos
= isl_set_dim(cond
, isl_dim_set
) - 1;
732 if (isl_val_is_pos(inc
))
733 return !isl_set_dim_has_any_lower_bound(cond
, isl_dim_set
, pos
);
735 return !isl_set_dim_has_any_upper_bound(cond
, isl_dim_set
, pos
);
738 /* Extend a condition on a given iteration of a loop to one that
739 * imposes the same condition on all previous iterations.
740 * "domain" expresses the lower [upper] bound on the iterations
741 * when inc is positive [negative] in its final dimension.
743 * In particular, we construct the condition (when inc is positive)
745 * forall i' : (domain(i') and i' <= i) => cond(i')
747 * (where "<=" applies to the final dimension)
748 * which is equivalent to
750 * not exists i' : domain(i') and i' <= i and not cond(i')
752 * We construct this set by subtracting the satisfying cond from domain,
755 * { [i'] -> [i] : i' <= i }
757 * and then subtracting the result from domain again.
759 static __isl_give isl_set
*valid_for_each_iteration(__isl_take isl_set
*cond
,
760 __isl_take isl_set
*domain
, __isl_take isl_val
*inc
)
763 isl_map
*previous_to_this
;
766 dim
= isl_set_dim(cond
, isl_dim_set
);
767 space
= isl_space_map_from_set(isl_set_get_space(cond
));
768 previous_to_this
= isl_map_universe(space
);
769 for (i
= 0; i
+ 1 < dim
; ++i
)
770 previous_to_this
= isl_map_equate(previous_to_this
,
771 isl_dim_in
, i
, isl_dim_out
, i
);
772 if (isl_val_is_pos(inc
))
773 previous_to_this
= isl_map_order_le(previous_to_this
,
774 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
776 previous_to_this
= isl_map_order_ge(previous_to_this
,
777 isl_dim_in
, dim
- 1, isl_dim_out
, dim
- 1);
779 cond
= isl_set_subtract(isl_set_copy(domain
), cond
);
780 cond
= isl_set_apply(cond
, previous_to_this
);
781 cond
= isl_set_subtract(domain
, cond
);
788 /* Construct a domain of the form
790 * [id] -> { : exists a: id = init + a * inc and a >= 0 }
792 static __isl_give isl_set
*strided_domain(__isl_take isl_id
*id
,
793 __isl_take isl_pw_aff
*init
, __isl_take isl_val
*inc
)
799 init
= isl_pw_aff_insert_dims(init
, isl_dim_in
, 0, 1);
800 dim
= isl_pw_aff_get_domain_space(init
);
801 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
802 aff
= isl_aff_add_coefficient_val(aff
, isl_dim_in
, 0, inc
);
803 init
= isl_pw_aff_add(init
, isl_pw_aff_from_aff(aff
));
805 dim
= isl_space_set_alloc(isl_pw_aff_get_ctx(init
), 1, 1);
806 dim
= isl_space_set_dim_id(dim
, isl_dim_param
, 0, id
);
807 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
808 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_param
, 0, 1);
810 set
= isl_pw_aff_eq_set(isl_pw_aff_from_aff(aff
), init
);
812 set
= isl_set_lower_bound_si(set
, isl_dim_set
, 0, 0);
814 return isl_set_params(set
);
817 /* Assuming "cond" represents a bound on a loop where the loop
818 * iterator "iv" is incremented (or decremented) by one, check if wrapping
821 * Under the given assumptions, wrapping is only possible if "cond" allows
822 * for the last value before wrapping, i.e., 2^width - 1 in case of an
823 * increasing iterator and 0 in case of a decreasing iterator.
825 static int can_wrap(__isl_keep isl_set
*cond
, __isl_keep pet_expr
*iv
,
826 __isl_keep isl_val
*inc
)
833 test
= isl_set_copy(cond
);
835 ctx
= isl_set_get_ctx(test
);
836 if (isl_val_is_neg(inc
))
837 limit
= isl_val_zero(ctx
);
839 limit
= isl_val_int_from_ui(ctx
, pet_expr_get_type_size(iv
));
840 limit
= isl_val_2exp(limit
);
841 limit
= isl_val_sub_ui(limit
, 1);
844 test
= isl_set_fix_val(cond
, isl_dim_set
, 0, limit
);
845 cw
= !isl_set_is_empty(test
);
851 /* Given a one-dimensional space, construct the following affine expression
854 * { [v] -> [v mod 2^width] }
856 * where width is the number of bits used to represent the values
857 * of the unsigned variable "iv".
859 static __isl_give isl_aff
*compute_wrapping(__isl_take isl_space
*dim
,
860 __isl_keep pet_expr
*iv
)
866 ctx
= isl_space_get_ctx(dim
);
867 mod
= isl_val_int_from_ui(ctx
, pet_expr_get_type_size(iv
));
868 mod
= isl_val_2exp(mod
);
870 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
871 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, 0, 1);
872 aff
= isl_aff_mod_val(aff
, mod
);
877 /* Project out the parameter "id" from "set".
879 static __isl_give isl_set
*set_project_out_by_id(__isl_take isl_set
*set
,
880 __isl_keep isl_id
*id
)
884 pos
= isl_set_find_dim_by_id(set
, isl_dim_param
, id
);
886 set
= isl_set_project_out(set
, isl_dim_param
, pos
, 1);
891 /* Compute the set of parameters for which "set1" is a subset of "set2".
893 * set1 is a subset of set2 if
895 * forall i in set1 : i in set2
899 * not exists i in set1 and i not in set2
903 * not exists i in set1 \ set2
905 static __isl_give isl_set
*enforce_subset(__isl_take isl_set
*set1
,
906 __isl_take isl_set
*set2
)
908 return isl_set_complement(isl_set_params(isl_set_subtract(set1
, set2
)));
911 /* Compute the set of parameter values for which "cond" holds
912 * on the next iteration for each element of "dom".
914 * We first construct mapping { [i] -> [i + inc] }, apply that to "dom"
915 * and then compute the set of parameters for which the result is a subset
918 static __isl_give isl_set
*valid_on_next(__isl_take isl_set
*cond
,
919 __isl_take isl_set
*dom
, __isl_take isl_val
*inc
)
925 space
= isl_set_get_space(dom
);
926 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(space
));
927 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, 0, 1);
928 aff
= isl_aff_add_constant_val(aff
, inc
);
929 next
= isl_map_from_basic_map(isl_basic_map_from_aff(aff
));
931 dom
= isl_set_apply(dom
, next
);
933 return enforce_subset(dom
, cond
);
936 /* Extract the for loop "tree" as a while loop within the context "pc".
938 * That is, the for loop has the form
940 * for (iv = init; cond; iv += inc)
951 * except that the skips resulting from any continue statements
952 * in body do not apply to the increment, but are replaced by the skips
953 * resulting from break statements.
955 * If the loop iterator is declared in the for loop, then it is killed before
956 * and after the loop.
958 static struct pet_scop
*scop_from_non_affine_for(__isl_keep pet_tree
*tree
,
959 __isl_take pet_context
*pc
, struct pet_state
*state
)
963 pet_expr
*expr_iv
, *init
, *inc
;
964 struct pet_scop
*scop_init
, *scop
;
966 struct pet_array
*array
;
967 struct pet_scop
*scop_kill
;
969 iv
= pet_expr_access_get_id(tree
->u
.l
.iv
);
970 pc
= pet_context_mark_unknown(pc
, iv
);
972 declared
= tree
->u
.l
.declared
;
974 expr_iv
= pet_expr_copy(tree
->u
.l
.iv
);
975 type_size
= pet_expr_get_type_size(expr_iv
);
976 init
= pet_expr_copy(tree
->u
.l
.init
);
977 init
= pet_expr_new_binary(type_size
, pet_op_assign
, expr_iv
, init
);
978 scop_init
= scop_from_expr(init
, NULL
, state
->n_stmt
++,
979 pet_tree_get_loc(tree
), pc
);
980 scop_init
= pet_scop_prefix(scop_init
, declared
);
982 expr_iv
= pet_expr_copy(tree
->u
.l
.iv
);
983 type_size
= pet_expr_get_type_size(expr_iv
);
984 inc
= pet_expr_copy(tree
->u
.l
.inc
);
985 inc
= pet_expr_new_binary(type_size
, pet_op_add_assign
, expr_iv
, inc
);
987 scop
= scop_from_non_affine_while(pet_expr_copy(tree
->u
.l
.cond
),
988 pet_tree_get_loc(tree
), tree
->u
.l
.body
, inc
,
989 pet_context_copy(pc
), state
);
991 scop
= pet_scop_prefix(scop
, declared
+ 1);
992 scop
= pet_scop_add_seq(state
->ctx
, scop_init
, scop
);
995 pet_context_free(pc
);
999 array
= extract_array(tree
->u
.l
.iv
, pc
, state
);
1001 array
->declared
= 1;
1002 scop_kill
= kill(pet_tree_get_loc(tree
), array
, pc
, state
);
1003 scop_kill
= pet_scop_prefix(scop_kill
, 0);
1004 scop
= pet_scop_add_seq(state
->ctx
, scop_kill
, scop
);
1005 scop_kill
= kill(pet_tree_get_loc(tree
), array
, pc
, state
);
1006 scop_kill
= pet_scop_add_array(scop_kill
, array
);
1007 scop_kill
= pet_scop_prefix(scop_kill
, 3);
1008 scop
= pet_scop_add_seq(state
->ctx
, scop
, scop_kill
);
1010 pet_context_free(pc
);
1014 /* Given an access expression "expr", is the variable accessed by
1015 * "expr" assigned anywhere inside "tree"?
1017 static int is_assigned(__isl_keep pet_expr
*expr
, __isl_keep pet_tree
*tree
)
1022 id
= pet_expr_access_get_id(expr
);
1023 assigned
= pet_tree_writes(tree
, id
);
1029 /* Are all nested access parameters in "pa" allowed given "tree".
1030 * In particular, is none of them written by anywhere inside "tree".
1032 * If "tree" has any continue nodes in the current loop level,
1033 * then no nested access parameters are allowed.
1034 * In particular, if there is any nested access in a guard
1035 * for a piece of code containing a "continue", then we want to introduce
1036 * a separate statement for evaluating this guard so that we can express
1037 * that the result is false for all previous iterations.
1039 static int is_nested_allowed(__isl_keep isl_pw_aff
*pa
,
1040 __isl_keep pet_tree
*tree
)
1047 if (!pet_nested_any_in_pw_aff(pa
))
1050 if (pet_tree_has_continue(tree
))
1053 nparam
= isl_pw_aff_dim(pa
, isl_dim_param
);
1054 for (i
= 0; i
< nparam
; ++i
) {
1055 isl_id
*id
= isl_pw_aff_get_dim_id(pa
, isl_dim_param
, i
);
1059 if (!pet_nested_in_id(id
)) {
1064 expr
= pet_nested_extract_expr(id
);
1065 allowed
= pet_expr_get_type(expr
) == pet_expr_access
&&
1066 !is_assigned(expr
, tree
);
1068 pet_expr_free(expr
);
1078 /* Construct a pet_scop for a for tree with static affine initialization
1079 * and constant increment within the context "pc".
1081 * The condition is allowed to contain nested accesses, provided
1082 * they are not being written to inside the body of the loop.
1083 * Otherwise, or if the condition is otherwise non-affine, the for loop is
1084 * essentially treated as a while loop, with iteration domain
1085 * { [i] : i >= init }.
1087 * We extract a pet_scop for the body and then embed it in a loop with
1088 * iteration domain and schedule
1090 * { [i] : i >= init and condition' }
1095 * { [i] : i <= init and condition' }
1098 * Where condition' is equal to condition if the latter is
1099 * a simple upper [lower] bound and a condition that is extended
1100 * to apply to all previous iterations otherwise.
1102 * If the condition is non-affine, then we drop the condition from the
1103 * iteration domain and instead create a separate statement
1104 * for evaluating the condition. The body is then filtered to depend
1105 * on the result of the condition evaluating to true on all iterations
1106 * up to the current iteration, while the evaluation the condition itself
1107 * is filtered to depend on the result of the condition evaluating to true
1108 * on all previous iterations.
1109 * The context of the scop representing the body is dropped
1110 * because we don't know how many times the body will be executed,
1113 * If the stride of the loop is not 1, then "i >= init" is replaced by
1115 * (exists a: i = init + stride * a and a >= 0)
1117 * If the loop iterator i is unsigned, then wrapping may occur.
1118 * We therefore use a virtual iterator instead that does not wrap.
1119 * However, the condition in the code applies
1120 * to the wrapped value, so we need to change condition(i)
1121 * into condition([i % 2^width]). Similarly, we replace all accesses
1122 * to the original iterator by the wrapping of the virtual iterator.
1123 * Note that there may be no need to perform this final wrapping
1124 * if the loop condition (after wrapping) satisfies certain conditions.
1125 * However, the is_simple_bound condition is not enough since it doesn't
1126 * check if there even is an upper bound.
1128 * Wrapping on unsigned iterators can be avoided entirely if
1129 * loop condition is simple, the loop iterator is incremented
1130 * [decremented] by one and the last value before wrapping cannot
1131 * possibly satisfy the loop condition.
1133 * Valid parameters for a for loop are those for which the initial
1134 * value itself, the increment on each domain iteration and
1135 * the condition on both the initial value and
1136 * the result of incrementing the iterator for each iteration of the domain
1138 * If the loop condition is non-affine, then we only consider validity
1139 * of the initial value.
1141 * If the body contains any break, then we keep track of it in "skip"
1142 * (if the skip condition is affine) or it is handled in scop_add_break
1143 * (if the skip condition is not affine).
1144 * Note that the affine break condition needs to be considered with
1145 * respect to previous iterations in the virtual domain (if any).
1147 static struct pet_scop
*scop_from_affine_for(__isl_keep pet_tree
*tree
,
1148 __isl_take isl_pw_aff
*init_val
, __isl_take isl_pw_aff
*pa_inc
,
1149 __isl_take isl_val
*inc
, __isl_take pet_context
*pc
,
1150 struct pet_state
*state
)
1152 isl_local_space
*ls
;
1155 isl_set
*cond
= NULL
;
1156 isl_set
*skip
= NULL
;
1157 isl_id
*id
, *id_test
= NULL
, *id_break_test
;
1158 struct pet_scop
*scop
, *scop_cond
= NULL
;
1164 int has_affine_break
;
1166 isl_map
*rev_wrap
= NULL
;
1167 isl_aff
*wrap
= NULL
;
1169 isl_set
*valid_init
;
1170 isl_set
*valid_cond
;
1171 isl_set
*valid_cond_init
;
1172 isl_set
*valid_cond_next
;
1174 pet_expr
*cond_expr
;
1175 pet_context
*pc_nested
;
1177 id
= pet_expr_access_get_id(tree
->u
.l
.iv
);
1179 cond_expr
= pet_expr_copy(tree
->u
.l
.cond
);
1180 cond_expr
= pet_context_evaluate_expr(pc
, cond_expr
);
1181 pc_nested
= pet_context_copy(pc
);
1182 pc_nested
= pet_context_set_allow_nested(pc_nested
, 1);
1183 pa
= pet_expr_extract_affine_condition(cond_expr
, pc_nested
);
1184 pet_context_free(pc_nested
);
1185 pet_expr_free(cond_expr
);
1187 valid_inc
= isl_pw_aff_domain(pa_inc
);
1189 is_unsigned
= pet_expr_get_type_size(tree
->u
.l
.iv
) > 0;
1191 is_non_affine
= isl_pw_aff_involves_nan(pa
) ||
1192 !is_nested_allowed(pa
, tree
->u
.l
.body
);
1194 pa
= isl_pw_aff_free(pa
);
1196 valid_cond
= isl_pw_aff_domain(isl_pw_aff_copy(pa
));
1197 cond
= isl_pw_aff_non_zero_set(pa
);
1199 cond
= isl_set_universe(isl_space_set_alloc(state
->ctx
, 0, 0));
1201 cond
= embed(cond
, isl_id_copy(id
));
1202 valid_cond
= isl_set_coalesce(valid_cond
);
1203 valid_cond
= embed(valid_cond
, isl_id_copy(id
));
1204 valid_inc
= embed(valid_inc
, isl_id_copy(id
));
1205 is_one
= isl_val_is_one(inc
) || isl_val_is_negone(inc
);
1206 is_virtual
= is_unsigned
&&
1207 (!is_one
|| can_wrap(cond
, tree
->u
.l
.iv
, inc
));
1209 valid_cond_init
= enforce_subset(
1210 isl_map_range(isl_map_from_pw_aff(isl_pw_aff_copy(init_val
))),
1211 isl_set_copy(valid_cond
));
1212 if (is_one
&& !is_virtual
) {
1213 isl_pw_aff_free(init_val
);
1214 pa
= pet_expr_extract_comparison(
1215 isl_val_is_pos(inc
) ? pet_op_ge
: pet_op_le
,
1216 tree
->u
.l
.iv
, tree
->u
.l
.init
, pc
);
1217 valid_init
= isl_pw_aff_domain(isl_pw_aff_copy(pa
));
1218 valid_init
= set_project_out_by_id(valid_init
, id
);
1219 domain
= isl_pw_aff_non_zero_set(pa
);
1221 valid_init
= isl_pw_aff_domain(isl_pw_aff_copy(init_val
));
1222 domain
= strided_domain(isl_id_copy(id
), init_val
,
1226 domain
= embed(domain
, isl_id_copy(id
));
1228 wrap
= compute_wrapping(isl_set_get_space(cond
), tree
->u
.l
.iv
);
1229 rev_wrap
= isl_map_from_aff(isl_aff_copy(wrap
));
1230 rev_wrap
= isl_map_reverse(rev_wrap
);
1231 cond
= isl_set_apply(cond
, isl_map_copy(rev_wrap
));
1232 valid_cond
= isl_set_apply(valid_cond
, isl_map_copy(rev_wrap
));
1233 valid_inc
= isl_set_apply(valid_inc
, isl_map_copy(rev_wrap
));
1235 is_simple
= is_simple_bound(cond
, inc
);
1237 cond
= isl_set_gist(cond
, isl_set_copy(domain
));
1238 is_simple
= is_simple_bound(cond
, inc
);
1241 cond
= valid_for_each_iteration(cond
,
1242 isl_set_copy(domain
), isl_val_copy(inc
));
1243 domain
= isl_set_intersect(domain
, cond
);
1244 domain
= isl_set_set_dim_id(domain
, isl_dim_set
, 0, isl_id_copy(id
));
1245 ls
= isl_local_space_from_space(isl_set_get_space(domain
));
1246 sched
= isl_aff_var_on_domain(ls
, isl_dim_set
, 0);
1247 if (isl_val_is_neg(inc
))
1248 sched
= isl_aff_neg(sched
);
1250 valid_cond_next
= valid_on_next(valid_cond
, isl_set_copy(domain
),
1252 valid_inc
= enforce_subset(isl_set_copy(domain
), valid_inc
);
1255 wrap
= identity_aff(domain
);
1257 if (is_non_affine
) {
1259 isl_multi_pw_aff
*test_index
;
1260 space
= pet_context_get_space(pc
);
1261 test_index
= pet_create_test_index(space
, state
->n_test
++);
1262 scop_cond
= scop_from_non_affine_condition(
1263 pet_expr_copy(tree
->u
.l
.cond
), state
->n_stmt
++,
1264 isl_multi_pw_aff_copy(test_index
),
1265 pet_tree_get_loc(tree
), pc
);
1266 id_test
= isl_multi_pw_aff_get_tuple_id(test_index
,
1268 scop_cond
= pet_scop_add_boolean_array(scop_cond
,
1269 pet_context_get_domain(pc
), test_index
,
1271 scop_cond
= pet_scop_prefix(scop_cond
, 0);
1272 scop_cond
= pet_scop_embed(scop_cond
, isl_set_copy(domain
),
1273 isl_aff_copy(sched
), isl_aff_copy(wrap
),
1277 scop
= scop_from_tree(tree
->u
.l
.body
, pc
, state
);
1278 has_affine_break
= scop
&&
1279 pet_scop_has_affine_skip(scop
, pet_skip_later
);
1280 if (has_affine_break
)
1281 skip
= pet_scop_get_affine_skip_domain(scop
, pet_skip_later
);
1282 has_var_break
= scop
&& pet_scop_has_var_skip(scop
, pet_skip_later
);
1284 id_break_test
= pet_scop_get_skip_id(scop
, pet_skip_later
);
1285 if (is_non_affine
) {
1286 scop
= pet_scop_reset_context(scop
);
1287 scop
= pet_scop_prefix(scop
, 1);
1289 scop
= pet_scop_embed(scop
, isl_set_copy(domain
), sched
, wrap
, id
);
1290 scop
= pet_scop_resolve_nested(scop
);
1291 if (has_affine_break
) {
1292 domain
= apply_affine_break(domain
, skip
, isl_val_sgn(inc
),
1293 is_virtual
, rev_wrap
);
1294 scop
= pet_scop_intersect_domain_prefix(scop
,
1295 isl_set_copy(domain
));
1297 isl_map_free(rev_wrap
);
1299 scop
= scop_add_break(scop
, id_break_test
, isl_set_copy(domain
),
1301 if (is_non_affine
) {
1302 scop
= scop_add_while(scop_cond
, scop
, id_test
, domain
,
1304 isl_set_free(valid_inc
);
1306 scop
= pet_scop_restrict_context(scop
, valid_inc
);
1307 scop
= pet_scop_restrict_context(scop
, valid_cond_next
);
1308 scop
= pet_scop_restrict_context(scop
, valid_cond_init
);
1309 isl_set_free(domain
);
1314 scop
= pet_scop_restrict_context(scop
, isl_set_params(valid_init
));
1316 pet_context_free(pc
);
1320 /* Construct a pet_scop for a for statement within the context of "pc".
1322 * We update the context to reflect the writes to the loop variable and
1323 * the writes inside the body.
1325 * Then we check if the initialization of the for loop
1326 * is a static affine value and the increment is a constant.
1327 * If so, we construct the pet_scop using scop_from_affine_for.
1328 * Otherwise, we treat the for loop as a while loop
1329 * in scop_from_non_affine_for.
1331 static struct pet_scop
*scop_from_for(__isl_keep pet_tree
*tree
,
1332 __isl_keep pet_context
*pc
, struct pet_state
*state
)
1336 isl_pw_aff
*pa_inc
, *init_val
;
1337 pet_context
*pc_init_val
;
1342 iv
= pet_expr_access_get_id(tree
->u
.l
.iv
);
1343 pc
= pet_context_copy(pc
);
1344 pc
= pet_context_clear_value(pc
, iv
);
1345 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.l
.body
);
1347 pc_init_val
= pet_context_copy(pc
);
1348 pc_init_val
= pet_context_mark_unknown(pc_init_val
, isl_id_copy(iv
));
1349 init_val
= pet_expr_extract_affine(tree
->u
.l
.init
, pc_init_val
);
1350 pet_context_free(pc_init_val
);
1351 pa_inc
= pet_expr_extract_affine(tree
->u
.l
.inc
, pc
);
1352 inc
= pet_extract_cst(pa_inc
);
1353 if (!pa_inc
|| !init_val
|| !inc
)
1355 if (!isl_pw_aff_involves_nan(pa_inc
) &&
1356 !isl_pw_aff_involves_nan(init_val
) && !isl_val_is_nan(inc
))
1357 return scop_from_affine_for(tree
, init_val
, pa_inc
, inc
,
1360 isl_pw_aff_free(pa_inc
);
1361 isl_pw_aff_free(init_val
);
1363 return scop_from_non_affine_for(tree
, pc
, state
);
1365 isl_pw_aff_free(pa_inc
);
1366 isl_pw_aff_free(init_val
);
1368 pet_context_free(pc
);
1372 /* Check whether "expr" is an affine constraint within the context "pc".
1374 static int is_affine_condition(__isl_keep pet_expr
*expr
,
1375 __isl_keep pet_context
*pc
)
1380 pa
= pet_expr_extract_affine_condition(expr
, pc
);
1383 is_affine
= !isl_pw_aff_involves_nan(pa
);
1384 isl_pw_aff_free(pa
);
1389 /* Check if the given if statement is a conditional assignement
1390 * with a non-affine condition.
1392 * In particular we check if "stmt" is of the form
1399 * where the condition is non-affine and a is some array or scalar access.
1401 static int is_conditional_assignment(__isl_keep pet_tree
*tree
,
1402 __isl_keep pet_context
*pc
)
1406 pet_expr
*expr1
, *expr2
;
1408 ctx
= pet_tree_get_ctx(tree
);
1409 if (!pet_options_get_detect_conditional_assignment(ctx
))
1411 if (tree
->type
!= pet_tree_if_else
)
1413 if (tree
->u
.i
.then_body
->type
!= pet_tree_expr
)
1415 if (tree
->u
.i
.else_body
->type
!= pet_tree_expr
)
1417 expr1
= tree
->u
.i
.then_body
->u
.e
.expr
;
1418 expr2
= tree
->u
.i
.else_body
->u
.e
.expr
;
1419 if (pet_expr_get_type(expr1
) != pet_expr_op
)
1421 if (pet_expr_get_type(expr2
) != pet_expr_op
)
1423 if (pet_expr_op_get_type(expr1
) != pet_op_assign
)
1425 if (pet_expr_op_get_type(expr2
) != pet_op_assign
)
1427 expr1
= pet_expr_get_arg(expr1
, 0);
1428 expr2
= pet_expr_get_arg(expr2
, 0);
1429 equal
= pet_expr_is_equal(expr1
, expr2
);
1430 pet_expr_free(expr1
);
1431 pet_expr_free(expr2
);
1432 if (equal
< 0 || !equal
)
1434 if (is_affine_condition(tree
->u
.i
.cond
, pc
))
1440 /* Given that "tree" is of the form
1447 * where a is some array or scalar access, construct a pet_scop
1448 * corresponding to this conditional assignment within the context "pc".
1450 * The constructed pet_scop then corresponds to the expression
1452 * a = condition ? f(...) : g(...)
1454 * All access relations in f(...) are intersected with condition
1455 * while all access relation in g(...) are intersected with the complement.
1457 static struct pet_scop
*scop_from_conditional_assignment(
1458 __isl_keep pet_tree
*tree
, __isl_take pet_context
*pc
,
1459 struct pet_state
*state
)
1463 isl_set
*cond
, *comp
;
1464 isl_multi_pw_aff
*index
;
1465 pet_expr
*expr1
, *expr2
;
1466 pet_expr
*pe_cond
, *pe_then
, *pe_else
, *pe
, *pe_write
;
1467 pet_context
*pc_nested
;
1468 struct pet_scop
*scop
;
1470 pe_cond
= pet_expr_copy(tree
->u
.i
.cond
);
1471 pe_cond
= pet_context_evaluate_expr(pc
, pe_cond
);
1472 pc_nested
= pet_context_copy(pc
);
1473 pc_nested
= pet_context_set_allow_nested(pc_nested
, 1);
1474 pa
= pet_expr_extract_affine_condition(pe_cond
, pc_nested
);
1475 pet_context_free(pc_nested
);
1476 pet_expr_free(pe_cond
);
1477 cond
= isl_pw_aff_non_zero_set(isl_pw_aff_copy(pa
));
1478 comp
= isl_pw_aff_zero_set(isl_pw_aff_copy(pa
));
1479 index
= isl_multi_pw_aff_from_pw_aff(pa
);
1481 expr1
= tree
->u
.i
.then_body
->u
.e
.expr
;
1482 expr2
= tree
->u
.i
.else_body
->u
.e
.expr
;
1484 pe_cond
= pet_expr_from_index(index
);
1486 pe_then
= pet_expr_get_arg(expr1
, 1);
1487 pe_then
= pet_context_evaluate_expr(pc
, pe_then
);
1488 pe_then
= pet_expr_restrict(pe_then
, cond
);
1489 pe_else
= pet_expr_get_arg(expr2
, 1);
1490 pe_else
= pet_context_evaluate_expr(pc
, pe_else
);
1491 pe_else
= pet_expr_restrict(pe_else
, comp
);
1492 pe_write
= pet_expr_get_arg(expr1
, 0);
1493 pe_write
= pet_context_evaluate_expr(pc
, pe_write
);
1495 pe
= pet_expr_new_ternary(pe_cond
, pe_then
, pe_else
);
1496 type_size
= pet_expr_get_type_size(pe_write
);
1497 pe
= pet_expr_new_binary(type_size
, pet_op_assign
, pe_write
, pe
);
1499 scop
= scop_from_evaluated_expr(pe
, NULL
, state
->n_stmt
++,
1500 pet_tree_get_loc(tree
), pc
);
1502 pet_context_free(pc
);
1507 /* Construct a pet_scop for a non-affine if statement within the context "pc".
1509 * We create a separate statement that writes the result
1510 * of the non-affine condition to a virtual scalar.
1511 * A constraint requiring the value of this virtual scalar to be one
1512 * is added to the iteration domains of the then branch.
1513 * Similarly, a constraint requiring the value of this virtual scalar
1514 * to be zero is added to the iteration domains of the else branch, if any.
1515 * We adjust the schedules to ensure that the virtual scalar is written
1516 * before it is read.
1518 * If there are any breaks or continues in the then and/or else
1519 * branches, then we may have to compute a new skip condition.
1520 * This is handled using a pet_skip_info object.
1521 * On initialization, the object checks if skip conditions need
1522 * to be computed. If so, it does so in pet_skip_info_if_extract_index and
1523 * adds them in pet_skip_info_if_add.
1525 static struct pet_scop
*scop_from_non_affine_if(__isl_keep pet_tree
*tree
,
1526 __isl_take pet_context
*pc
, struct pet_state
*state
)
1531 isl_multi_pw_aff
*test_index
;
1532 struct pet_skip_info skip
;
1533 struct pet_scop
*scop
, *scop_then
, *scop_else
= NULL
;
1535 has_else
= tree
->type
== pet_tree_if_else
;
1537 space
= pet_context_get_space(pc
);
1538 test_index
= pet_create_test_index(space
, state
->n_test
++);
1539 scop
= scop_from_non_affine_condition(pet_expr_copy(tree
->u
.i
.cond
),
1540 state
->n_stmt
++, isl_multi_pw_aff_copy(test_index
),
1541 pet_tree_get_loc(tree
), pc
);
1542 domain
= pet_context_get_domain(pc
);
1543 scop
= pet_scop_add_boolean_array(scop
, domain
,
1544 isl_multi_pw_aff_copy(test_index
), state
->int_size
);
1546 scop_then
= scop_from_tree(tree
->u
.i
.then_body
, pc
, state
);
1548 scop_else
= scop_from_tree(tree
->u
.i
.else_body
, pc
, state
);
1550 pet_skip_info_if_init(&skip
, state
->ctx
, scop_then
, scop_else
,
1552 pet_skip_info_if_extract_index(&skip
, test_index
, pc
, state
);
1554 scop
= pet_scop_prefix(scop
, 0);
1555 scop_then
= pet_scop_prefix(scop_then
, 1);
1556 scop_then
= pet_scop_filter(scop_then
,
1557 isl_multi_pw_aff_copy(test_index
), 1);
1559 scop_else
= pet_scop_prefix(scop_else
, 1);
1560 scop_else
= pet_scop_filter(scop_else
, test_index
, 0);
1561 scop_then
= pet_scop_add_par(state
->ctx
, scop_then
, scop_else
);
1563 isl_multi_pw_aff_free(test_index
);
1565 scop
= pet_scop_add_seq(state
->ctx
, scop
, scop_then
);
1567 scop
= pet_skip_info_if_add(&skip
, scop
, 2);
1569 pet_context_free(pc
);
1573 /* Construct a pet_scop for an affine if statement within the context "pc".
1575 * The condition is added to the iteration domains of the then branch,
1576 * while the opposite of the condition in added to the iteration domains
1577 * of the else branch, if any.
1579 * If there are any breaks or continues in the then and/or else
1580 * branches, then we may have to compute a new skip condition.
1581 * This is handled using a pet_skip_info_if object.
1582 * On initialization, the object checks if skip conditions need
1583 * to be computed. If so, it does so in pet_skip_info_if_extract_cond and
1584 * adds them in pet_skip_info_if_add.
1586 static struct pet_scop
*scop_from_affine_if(__isl_keep pet_tree
*tree
,
1587 __isl_take isl_pw_aff
*cond
, __isl_take pet_context
*pc
,
1588 struct pet_state
*state
)
1594 struct pet_skip_info skip
;
1595 struct pet_scop
*scop
, *scop_then
, *scop_else
= NULL
;
1597 ctx
= pet_tree_get_ctx(tree
);
1599 has_else
= tree
->type
== pet_tree_if_else
;
1601 scop_then
= scop_from_tree(tree
->u
.i
.then_body
, pc
, state
);
1603 scop_else
= scop_from_tree(tree
->u
.i
.else_body
, pc
, state
);
1605 pet_skip_info_if_init(&skip
, ctx
, scop_then
, scop_else
, has_else
, 1);
1606 pet_skip_info_if_extract_cond(&skip
, cond
, pc
, state
);
1608 valid
= isl_pw_aff_domain(isl_pw_aff_copy(cond
));
1609 set
= isl_pw_aff_non_zero_set(cond
);
1610 scop
= pet_scop_restrict(scop_then
, isl_set_params(isl_set_copy(set
)));
1613 set
= isl_set_subtract(isl_set_copy(valid
), set
);
1614 scop_else
= pet_scop_restrict(scop_else
, isl_set_params(set
));
1615 scop
= pet_scop_add_par(ctx
, scop
, scop_else
);
1618 scop
= pet_scop_resolve_nested(scop
);
1619 scop
= pet_scop_restrict_context(scop
, isl_set_params(valid
));
1621 if (pet_skip_info_has_skip(&skip
))
1622 scop
= pet_scop_prefix(scop
, 0);
1623 scop
= pet_skip_info_if_add(&skip
, scop
, 1);
1625 pet_context_free(pc
);
1629 /* Construct a pet_scop for an if statement within the context "pc".
1631 * If the condition fits the pattern of a conditional assignment,
1632 * then it is handled by scop_from_conditional_assignment.
1634 * Otherwise, we check if the condition is affine.
1635 * If so, we construct the scop in scop_from_affine_if.
1636 * Otherwise, we construct the scop in scop_from_non_affine_if.
1638 * We allow the condition to be dynamic, i.e., to refer to
1639 * scalars or array elements that may be written to outside
1640 * of the given if statement. These nested accesses are then represented
1641 * as output dimensions in the wrapping iteration domain.
1642 * If it is also written _inside_ the then or else branch, then
1643 * we treat the condition as non-affine.
1644 * As explained in extract_non_affine_if, this will introduce
1645 * an extra statement.
1646 * For aesthetic reasons, we want this statement to have a statement
1647 * number that is lower than those of the then and else branches.
1648 * In order to evaluate if we will need such a statement, however, we
1649 * first construct scops for the then and else branches.
1650 * We therefore reserve a statement number if we might have to
1651 * introduce such an extra statement.
1653 static struct pet_scop
*scop_from_if(__isl_keep pet_tree
*tree
,
1654 __isl_keep pet_context
*pc
, struct pet_state
*state
)
1658 pet_expr
*cond_expr
;
1659 pet_context
*pc_nested
;
1664 has_else
= tree
->type
== pet_tree_if_else
;
1666 pc
= pet_context_copy(pc
);
1667 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.i
.then_body
);
1669 pc
= pet_context_clear_writes_in_tree(pc
, tree
->u
.i
.else_body
);
1671 if (is_conditional_assignment(tree
, pc
))
1672 return scop_from_conditional_assignment(tree
, pc
, state
);
1674 cond_expr
= pet_expr_copy(tree
->u
.i
.cond
);
1675 cond_expr
= pet_context_evaluate_expr(pc
, cond_expr
);
1676 pc_nested
= pet_context_copy(pc
);
1677 pc_nested
= pet_context_set_allow_nested(pc_nested
, 1);
1678 cond
= pet_expr_extract_affine_condition(cond_expr
, pc_nested
);
1679 pet_context_free(pc_nested
);
1680 pet_expr_free(cond_expr
);
1683 pet_context_free(pc
);
1687 if (isl_pw_aff_involves_nan(cond
)) {
1688 isl_pw_aff_free(cond
);
1689 return scop_from_non_affine_if(tree
, pc
, state
);
1692 if ((!is_nested_allowed(cond
, tree
->u
.i
.then_body
) ||
1693 (has_else
&& !is_nested_allowed(cond
, tree
->u
.i
.else_body
)))) {
1694 isl_pw_aff_free(cond
);
1695 return scop_from_non_affine_if(tree
, pc
, state
);
1698 return scop_from_affine_if(tree
, cond
, pc
, state
);
1701 /* Return a one-dimensional multi piecewise affine expression that is equal
1702 * to the constant 1 and is defined over the given domain.
1704 static __isl_give isl_multi_pw_aff
*one_mpa(__isl_take isl_space
*space
)
1706 isl_local_space
*ls
;
1709 ls
= isl_local_space_from_space(space
);
1710 aff
= isl_aff_zero_on_domain(ls
);
1711 aff
= isl_aff_set_constant_si(aff
, 1);
1713 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1716 /* Construct a pet_scop for a continue statement with the given domain space.
1718 * We simply create an empty scop with a universal pet_skip_now
1719 * skip condition. This skip condition will then be taken into
1720 * account by the enclosing loop construct, possibly after
1721 * being incorporated into outer skip conditions.
1723 static struct pet_scop
*scop_from_continue(__isl_keep pet_tree
*tree
,
1724 __isl_take isl_space
*space
)
1726 struct pet_scop
*scop
;
1728 scop
= pet_scop_empty(isl_space_copy(space
));
1730 scop
= pet_scop_set_skip(scop
, pet_skip_now
, one_mpa(space
));
1735 /* Construct a pet_scop for a break statement with the given domain space.
1737 * We simply create an empty scop with both a universal pet_skip_now
1738 * skip condition and a universal pet_skip_later skip condition.
1739 * These skip conditions will then be taken into
1740 * account by the enclosing loop construct, possibly after
1741 * being incorporated into outer skip conditions.
1743 static struct pet_scop
*scop_from_break(__isl_keep pet_tree
*tree
,
1744 __isl_take isl_space
*space
)
1746 struct pet_scop
*scop
;
1747 isl_multi_pw_aff
*skip
;
1749 scop
= pet_scop_empty(isl_space_copy(space
));
1751 skip
= one_mpa(space
);
1752 scop
= pet_scop_set_skip(scop
, pet_skip_now
,
1753 isl_multi_pw_aff_copy(skip
));
1754 scop
= pet_scop_set_skip(scop
, pet_skip_later
, skip
);
1759 /* Extract a clone of the kill statement in "scop".
1760 * The domain of the clone is given by "domain".
1761 * "scop" is expected to have been created from a DeclStmt
1762 * and should have the kill as its first statement.
1764 static struct pet_scop
*extract_kill(__isl_keep isl_set
*domain
,
1765 struct pet_scop
*scop
, struct pet_state
*state
)
1768 struct pet_stmt
*stmt
;
1769 isl_multi_pw_aff
*index
;
1773 if (!domain
|| !scop
)
1775 if (scop
->n_stmt
< 1)
1776 isl_die(isl_set_get_ctx(domain
), isl_error_internal
,
1777 "expecting at least one statement", return NULL
);
1778 stmt
= scop
->stmts
[0];
1779 if (!pet_stmt_is_kill(stmt
))
1780 isl_die(isl_set_get_ctx(domain
), isl_error_internal
,
1781 "expecting kill statement", return NULL
);
1783 arg
= pet_expr_get_arg(stmt
->body
, 0);
1784 index
= pet_expr_access_get_index(arg
);
1785 access
= pet_expr_access_get_access(arg
);
1787 index
= isl_multi_pw_aff_reset_tuple_id(index
, isl_dim_in
);
1788 access
= isl_map_reset_tuple_id(access
, isl_dim_in
);
1789 kill
= pet_expr_kill_from_access_and_index(access
, index
);
1790 stmt
= pet_stmt_from_pet_expr(isl_set_copy(domain
),
1791 pet_loc_copy(stmt
->loc
), NULL
, state
->n_stmt
++, kill
);
1792 return pet_scop_from_pet_stmt(isl_set_get_space(domain
), stmt
);
1795 /* Does "tree" represent an assignment to a variable?
1797 * The assignment may be one of
1798 * - a declaration with initialization
1799 * - an expression with a top-level assignment operator
1801 static int is_assignment(__isl_keep pet_tree
*tree
)
1805 if (tree
->type
== pet_tree_decl_init
)
1807 return pet_tree_is_assign(tree
);
1810 /* Update "pc" by taking into account the assignment performed by "tree",
1811 * where "tree" satisfies is_assignment.
1813 * In particular, if the lhs of the assignment is a scalar variable and
1814 * if the rhs is an affine expression, then keep track of this value in "pc"
1815 * so that we can plug it in when we later come across the same variable.
1817 * The variable has already been marked as having been assigned
1818 * an unknown value by scop_handle_writes.
1820 static __isl_give pet_context
*handle_assignment(__isl_take pet_context
*pc
,
1821 __isl_keep pet_tree
*tree
)
1823 pet_expr
*var
, *val
;
1827 if (pet_tree_get_type(tree
) == pet_tree_decl_init
) {
1828 var
= pet_tree_decl_get_var(tree
);
1829 val
= pet_tree_decl_get_init(tree
);
1832 expr
= pet_tree_expr_get_expr(tree
);
1833 var
= pet_expr_get_arg(expr
, 0);
1834 val
= pet_expr_get_arg(expr
, 1);
1835 pet_expr_free(expr
);
1838 if (!pet_expr_is_scalar_access(var
)) {
1844 pa
= pet_expr_extract_affine(val
, pc
);
1846 pc
= pet_context_free(pc
);
1848 if (!isl_pw_aff_involves_nan(pa
)) {
1849 id
= pet_expr_access_get_id(var
);
1850 pc
= pet_context_set_value(pc
, id
, pa
);
1852 isl_pw_aff_free(pa
);
1860 /* Mark all arrays in "scop" as being exposed.
1862 static struct pet_scop
*mark_exposed(struct pet_scop
*scop
)
1868 for (i
= 0; i
< scop
->n_array
; ++i
)
1869 scop
->arrays
[i
]->exposed
= 1;
1873 /* Try and construct a pet_scop corresponding to (part of)
1874 * a sequence of statements within the context "pc".
1876 * After extracting a statement, we update "pc"
1877 * based on the top-level assignments in the statement
1878 * so that we can exploit them in subsequent statements in the same block.
1880 * If there are any breaks or continues in the individual statements,
1881 * then we may have to compute a new skip condition.
1882 * This is handled using a pet_skip_info object.
1883 * On initialization, the object checks if skip conditions need
1884 * to be computed. If so, it does so in pet_skip_info_seq_extract and
1885 * adds them in pet_skip_info_seq_add.
1887 * If "block" is set, then we need to insert kill statements at
1888 * the end of the block for any array that has been declared by
1889 * one of the statements in the sequence. Each of these declarations
1890 * results in the construction of a kill statement at the place
1891 * of the declaration, so we simply collect duplicates of
1892 * those kill statements and append these duplicates to the constructed scop.
1894 * If "block" is not set, then any array declared by one of the statements
1895 * in the sequence is marked as being exposed.
1897 * If autodetect is set, then we allow the extraction of only a subrange
1898 * of the sequence of statements. However, if there is at least one statement
1899 * for which we could not construct a scop and the final range contains
1900 * either no statements or at least one kill, then we discard the entire
1903 static struct pet_scop
*scop_from_block(__isl_keep pet_tree
*tree
,
1904 __isl_keep pet_context
*pc
, struct pet_state
*state
)
1910 struct pet_scop
*scop
, *kills
;
1912 ctx
= pet_tree_get_ctx(tree
);
1914 space
= pet_context_get_space(pc
);
1915 domain
= pet_context_get_domain(pc
);
1916 pc
= pet_context_copy(pc
);
1917 scop
= pet_scop_empty(isl_space_copy(space
));
1918 kills
= pet_scop_empty(space
);
1919 for (i
= 0; i
< tree
->u
.b
.n
; ++i
) {
1920 struct pet_scop
*scop_i
;
1922 scop_i
= scop_from_tree(tree
->u
.b
.child
[i
], pc
, state
);
1923 pc
= scop_handle_writes(scop_i
, pc
);
1924 if (is_assignment(tree
->u
.b
.child
[i
]))
1925 pc
= handle_assignment(pc
, tree
->u
.b
.child
[i
]);
1926 struct pet_skip_info skip
;
1927 pet_skip_info_seq_init(&skip
, ctx
, scop
, scop_i
);
1928 pet_skip_info_seq_extract(&skip
, pc
, state
);
1929 if (pet_skip_info_has_skip(&skip
))
1930 scop_i
= pet_scop_prefix(scop_i
, 0);
1931 if (scop_i
&& pet_tree_is_decl(tree
->u
.b
.child
[i
])) {
1932 if (tree
->u
.b
.block
) {
1933 struct pet_scop
*kill
;
1934 kill
= extract_kill(domain
, scop_i
, state
);
1935 kills
= pet_scop_add_par(ctx
, kills
, kill
);
1937 scop_i
= mark_exposed(scop_i
);
1939 scop_i
= pet_scop_prefix(scop_i
, i
);
1940 scop
= pet_scop_add_seq(ctx
, scop
, scop_i
);
1942 scop
= pet_skip_info_seq_add(&skip
, scop
, i
);
1947 isl_set_free(domain
);
1949 kills
= pet_scop_prefix(kills
, tree
->u
.b
.n
);
1950 scop
= pet_scop_add_seq(ctx
, scop
, kills
);
1952 pet_context_free(pc
);
1957 /* Construct a pet_scop that corresponds to the pet_tree "tree"
1958 * within the context "pc" by calling the appropriate function
1959 * based on the type of "tree".
1961 static struct pet_scop
*scop_from_tree(__isl_keep pet_tree
*tree
,
1962 __isl_keep pet_context
*pc
, struct pet_state
*state
)
1967 switch (tree
->type
) {
1968 case pet_tree_error
:
1970 case pet_tree_block
:
1971 return scop_from_block(tree
, pc
, state
);
1972 case pet_tree_break
:
1973 return scop_from_break(tree
, pet_context_get_space(pc
));
1974 case pet_tree_continue
:
1975 return scop_from_continue(tree
, pet_context_get_space(pc
));
1977 case pet_tree_decl_init
:
1978 return scop_from_decl(tree
, pc
, state
);
1980 return scop_from_expr(pet_expr_copy(tree
->u
.e
.expr
),
1981 isl_id_copy(tree
->label
),
1983 pet_tree_get_loc(tree
), pc
);
1985 case pet_tree_if_else
:
1986 return scop_from_if(tree
, pc
, state
);
1988 return scop_from_for(tree
, pc
, state
);
1989 case pet_tree_while
:
1990 return scop_from_while(tree
, pc
, state
);
1991 case pet_tree_infinite_loop
:
1992 return scop_from_infinite_for(tree
, pc
, state
);
1995 isl_die(tree
->ctx
, isl_error_internal
, "unhandled type",
1999 /* Construct a pet_scop that corresponds to the pet_tree "tree".
2000 * "int_size" is the number of bytes need to represent an integer.
2001 * "extract_array" is a callback that we can use to create a pet_array
2002 * that corresponds to the variable accessed by an expression.
2004 * Initialize the global state, construct a context and then
2005 * construct the pet_scop by recursively visiting the tree.
2007 struct pet_scop
*pet_scop_from_pet_tree(__isl_take pet_tree
*tree
, int int_size
,
2008 struct pet_array
*(*extract_array
)(__isl_keep pet_expr
*access
,
2009 __isl_keep pet_context
*pc
, void *user
), void *user
,
2010 __isl_keep pet_context
*pc
)
2012 struct pet_scop
*scop
;
2013 struct pet_state state
= { 0 };
2018 state
.ctx
= pet_tree_get_ctx(tree
);
2019 state
.int_size
= int_size
;
2020 state
.extract_array
= extract_array
;
2023 scop
= scop_from_tree(tree
, pc
, &state
);
2024 scop
= pet_scop_set_loc(scop
, pet_tree_get_loc(tree
));
2026 pet_tree_free(tree
);