scop.c: access_collect_params: avoid using access relation
[pet.git] / tree2scop.c
blob6e0377a54e18de1880aa4917eb7ea2a65d0e76dd
1 /*
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
7 * are met:
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
32 * Leiden University.
35 #include <isl/id_to_pw_aff.h>
37 #include "aff.h"
38 #include "expr.h"
39 #include "expr_arg.h"
40 #include "nest.h"
41 #include "scop.h"
42 #include "skip.h"
43 #include "state.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)
61 int i;
63 if (!scop)
64 return pet_context_free(pc);
65 for (i = 0; i < scop->n_stmt; ++i)
66 pc = handle_writes(scop->stmts[i], pc);
68 return 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,
75 void *user)
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)
103 isl_space *space;
104 isl_set *domain;
105 struct pet_stmt *ps;
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)
128 pet_tree *tree;
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)
160 pet_tree *tree;
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
168 * array "array".
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)
174 isl_ctx *ctx;
175 isl_id *id;
176 isl_space *space;
177 isl_multi_pw_aff *index;
178 isl_map *access;
179 pet_expr *expr;
180 struct pet_scop *scop;
182 if (!array)
183 goto error;
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);
192 error:
193 pet_loc_free(loc);
194 return NULL;
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)
218 int type_size;
219 isl_ctx *ctx;
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);
225 if (array)
226 array->declared = 1;
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)
231 return scop_decl;
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);
245 return scop;
248 /* Return those elements in the space of "cond" that come after
249 * (based on "sign") an element in "cond" in the final dimension.
251 static __isl_give isl_set *after(__isl_take isl_set *cond, int sign)
253 isl_space *space;
254 isl_map *previous_to_this;
255 int i, dim;
257 dim = isl_set_dim(cond, isl_dim_set);
258 space = isl_space_map_from_set(isl_set_get_space(cond));
259 previous_to_this = isl_map_universe(space);
260 for (i = 0; i + 1 < dim; ++i)
261 previous_to_this = isl_map_equate(previous_to_this,
262 isl_dim_in, i, isl_dim_out, i);
263 if (sign > 0)
264 previous_to_this = isl_map_order_lt(previous_to_this,
265 isl_dim_in, dim - 1, isl_dim_out, dim - 1);
266 else
267 previous_to_this = isl_map_order_gt(previous_to_this,
268 isl_dim_in, dim - 1, isl_dim_out, dim - 1);
270 cond = isl_set_apply(cond, previous_to_this);
272 return cond;
275 /* Remove those iterations of "domain" that have an earlier iteration
276 * (based on "sign") in the final dimension where "skip" is satisfied.
277 * If "apply_skip_map" is set, then "skip_map" is first applied
278 * to the embedded skip condition before removing it from the domain.
280 static __isl_give isl_set *apply_affine_break(__isl_take isl_set *domain,
281 __isl_take isl_set *skip, int sign,
282 int apply_skip_map, __isl_keep isl_map *skip_map)
284 if (apply_skip_map)
285 skip = isl_set_apply(skip, isl_map_copy(skip_map));
286 skip = isl_set_intersect(skip , isl_set_copy(domain));
287 return isl_set_subtract(domain, after(skip, sign));
290 /* Create an affine expression on the domain space of "pc" that
291 * is equal to the final dimension of this domain.
293 static __isl_give isl_aff *map_to_last(__isl_keep pet_context *pc)
295 int pos;
296 isl_space *space;
297 isl_local_space *ls;
299 space = pet_context_get_space(pc);
300 pos = isl_space_dim(space, isl_dim_set) - 1;
301 ls = isl_local_space_from_space(space);
302 return isl_aff_var_on_domain(ls, isl_dim_set, pos);
305 /* Create an affine expression that maps elements
306 * of an array "id_test" to the previous element in the final dimension
307 * (according to "inc"), provided this element belongs to "domain".
308 * That is, create the affine expression
310 * { id[outer,x] -> id[outer,x - inc] : (outer,x - inc) in domain }
312 static __isl_give isl_multi_pw_aff *map_to_previous(__isl_take isl_id *id_test,
313 __isl_take isl_set *domain, __isl_take isl_val *inc)
315 int pos;
316 isl_space *space;
317 isl_aff *aff;
318 isl_pw_aff *pa;
319 isl_multi_aff *ma;
320 isl_multi_pw_aff *prev;
322 pos = isl_set_dim(domain, isl_dim_set) - 1;
323 space = isl_set_get_space(domain);
324 space = isl_space_map_from_set(space);
325 ma = isl_multi_aff_identity(space);
326 aff = isl_multi_aff_get_aff(ma, pos);
327 aff = isl_aff_add_constant_val(aff, isl_val_neg(inc));
328 ma = isl_multi_aff_set_aff(ma, pos, aff);
329 domain = isl_set_preimage_multi_aff(domain, isl_multi_aff_copy(ma));
330 prev = isl_multi_pw_aff_from_multi_aff(ma);
331 pa = isl_multi_pw_aff_get_pw_aff(prev, pos);
332 pa = isl_pw_aff_intersect_domain(pa, domain);
333 prev = isl_multi_pw_aff_set_pw_aff(prev, pos, pa);
334 prev = isl_multi_pw_aff_set_tuple_id(prev, isl_dim_out, id_test);
336 return prev;
339 /* Add an implication to "scop" expressing that if an element of
340 * virtual array "id_test" has value "satisfied" then all previous elements
341 * of this array (in the final dimension) also have that value.
342 * The set of previous elements is bounded by "domain".
343 * If "sign" is negative then the iterator
344 * is decreasing and we express that all subsequent array elements
345 * (but still defined previously) have the same value.
347 static struct pet_scop *add_implication(struct pet_scop *scop,
348 __isl_take isl_id *id_test, __isl_take isl_set *domain, int sign,
349 int satisfied)
351 int i, dim;
352 isl_space *space;
353 isl_map *map;
355 dim = isl_set_dim(domain, isl_dim_set);
356 domain = isl_set_set_tuple_id(domain, id_test);
357 space = isl_space_map_from_set(isl_set_get_space(domain));
358 map = isl_map_universe(space);
359 for (i = 0; i + 1 < dim; ++i)
360 map = isl_map_equate(map, isl_dim_in, i, isl_dim_out, i);
361 if (sign > 0)
362 map = isl_map_order_ge(map,
363 isl_dim_in, dim - 1, isl_dim_out, dim - 1);
364 else
365 map = isl_map_order_le(map,
366 isl_dim_in, dim - 1, isl_dim_out, dim - 1);
367 map = isl_map_intersect_range(map, domain);
368 scop = pet_scop_add_implication(scop, map, satisfied);
370 return scop;
373 /* Add a filter to "scop" that imposes that it is only executed
374 * when the variable identified by "id_test" has a zero value
375 * for all previous iterations of "domain".
377 * In particular, add a filter that imposes that the array
378 * has a zero value at the previous iteration of domain and
379 * add an implication that implies that it then has that
380 * value for all previous iterations.
382 static struct pet_scop *scop_add_break(struct pet_scop *scop,
383 __isl_take isl_id *id_test, __isl_take isl_set *domain,
384 __isl_take isl_val *inc)
386 isl_multi_pw_aff *prev;
387 int sign = isl_val_sgn(inc);
389 prev = map_to_previous(isl_id_copy(id_test), isl_set_copy(domain), inc);
390 scop = add_implication(scop, id_test, domain, sign, 0);
391 scop = pet_scop_filter(scop, prev, 0);
393 return scop;
396 static struct pet_scop *scop_from_tree(__isl_keep pet_tree *tree,
397 __isl_keep pet_context *pc, struct pet_state *state);
399 /* Construct a pet_scop for an infinite loop around the given body
400 * within the context "pc".
402 * The domain of "pc" has already been extended with an infinite loop
404 * { [t] : t >= 0 }
406 * We extract a pet_scop for the body and then embed it in a loop with
407 * schedule
409 * { [outer,t] -> [t] }
411 * If the body contains any break, then it is taken into
412 * account in apply_affine_break (if the skip condition is affine)
413 * or in scop_add_break (if the skip condition is not affine).
415 * Note that in case of an affine skip condition,
416 * since we are dealing with a loop without loop iterator,
417 * the skip condition cannot refer to the current loop iterator and
418 * so effectively, the effect on the iteration domain is of the form
420 * { [outer,0]; [outer,t] : t >= 1 and not skip }
422 static struct pet_scop *scop_from_infinite_loop(__isl_keep pet_tree *body,
423 __isl_keep pet_context *pc, struct pet_state *state)
425 isl_ctx *ctx;
426 isl_id *id_test;
427 isl_set *domain;
428 isl_set *skip;
429 isl_aff *sched;
430 struct pet_scop *scop;
431 int has_affine_break;
432 int has_var_break;
434 ctx = pet_tree_get_ctx(body);
435 domain = pet_context_get_domain(pc);
436 sched = map_to_last(pc);
438 scop = scop_from_tree(body, pc, state);
440 has_affine_break = pet_scop_has_affine_skip(scop, pet_skip_later);
441 if (has_affine_break)
442 skip = pet_scop_get_affine_skip_domain(scop, pet_skip_later);
443 has_var_break = pet_scop_has_var_skip(scop, pet_skip_later);
444 if (has_var_break)
445 id_test = pet_scop_get_skip_id(scop, pet_skip_later);
447 scop = pet_scop_embed(scop, isl_set_copy(domain), sched);
448 if (has_affine_break) {
449 domain = apply_affine_break(domain, skip, 1, 0, NULL);
450 scop = pet_scop_intersect_domain_prefix(scop,
451 isl_set_copy(domain));
453 if (has_var_break)
454 scop = scop_add_break(scop, id_test, domain, isl_val_one(ctx));
455 else
456 isl_set_free(domain);
458 return scop;
461 /* Construct a pet_scop for an infinite loop, i.e., a loop of the form
463 * for (;;)
464 * body
466 * within the context "pc".
468 * Extend the domain of "pc" with an extra inner loop
470 * { [t] : t >= 0 }
472 * and construct the scop in scop_from_infinite_loop.
474 static struct pet_scop *scop_from_infinite_for(__isl_keep pet_tree *tree,
475 __isl_keep pet_context *pc, struct pet_state *state)
477 struct pet_scop *scop;
479 pc = pet_context_copy(pc);
480 pc = pet_context_clear_writes_in_tree(pc, tree->u.l.body);
482 pc = pet_context_add_infinite_loop(pc);
484 scop = scop_from_infinite_loop(tree->u.l.body, pc, state);
486 pet_context_free(pc);
488 return scop;
491 /* Construct a pet_scop for a while loop of the form
493 * while (pa)
494 * body
496 * within the context "pc".
498 * The domain of "pc" has already been extended with an infinite loop
500 * { [t] : t >= 0 }
502 * Here, we add the constraints on the outer loop iterators
503 * implied by "pa" and construct the scop in scop_from_infinite_loop.
504 * Note that the intersection with these constraints
505 * may result in an empty loop.
507 static struct pet_scop *scop_from_affine_while(__isl_keep pet_tree *tree,
508 __isl_take isl_pw_aff *pa, __isl_take pet_context *pc,
509 struct pet_state *state)
511 struct pet_scop *scop;
512 isl_set *dom, *local;
513 isl_set *valid;
515 valid = isl_pw_aff_domain(isl_pw_aff_copy(pa));
516 dom = isl_pw_aff_non_zero_set(pa);
517 local = isl_set_add_dims(isl_set_copy(dom), isl_dim_set, 1);
518 pc = pet_context_intersect_domain(pc, local);
519 scop = scop_from_infinite_loop(tree->u.l.body, pc, state);
520 scop = pet_scop_restrict(scop, dom);
521 scop = pet_scop_restrict_context(scop, valid);
523 pet_context_free(pc);
524 return scop;
527 /* Construct a scop for a while, given the scops for the condition
528 * and the body, the filter identifier and the iteration domain of
529 * the while loop.
531 * In particular, the scop for the condition is filtered to depend
532 * on "id_test" evaluating to true for all previous iterations
533 * of the loop, while the scop for the body is filtered to depend
534 * on "id_test" evaluating to true for all iterations up to the
535 * current iteration.
536 * The actual filter only imposes that this virtual array has
537 * value one on the previous or the current iteration.
538 * The fact that this condition also applies to the previous
539 * iterations is enforced by an implication.
541 * These filtered scops are then combined into a single scop.
543 * "sign" is positive if the iterator increases and negative
544 * if it decreases.
546 static struct pet_scop *scop_add_while(struct pet_scop *scop_cond,
547 struct pet_scop *scop_body, __isl_take isl_id *id_test,
548 __isl_take isl_set *domain, __isl_take isl_val *inc)
550 isl_ctx *ctx = isl_set_get_ctx(domain);
551 isl_space *space;
552 isl_multi_pw_aff *test_index;
553 isl_multi_pw_aff *prev;
554 int sign = isl_val_sgn(inc);
555 struct pet_scop *scop;
557 prev = map_to_previous(isl_id_copy(id_test), isl_set_copy(domain), inc);
558 scop_cond = pet_scop_filter(scop_cond, prev, 1);
560 space = isl_space_map_from_set(isl_set_get_space(domain));
561 test_index = isl_multi_pw_aff_identity(space);
562 test_index = isl_multi_pw_aff_set_tuple_id(test_index, isl_dim_out,
563 isl_id_copy(id_test));
564 scop_body = pet_scop_filter(scop_body, test_index, 1);
566 scop = pet_scop_add_seq(ctx, scop_cond, scop_body);
567 scop = add_implication(scop, id_test, domain, sign, 1);
569 return scop;
572 /* Create a pet_scop with a single statement with name S_<stmt_nr>,
573 * evaluating "cond" and writing the result to a virtual scalar,
574 * as expressed by "index".
575 * The expression "cond" has not yet been evaluated in the context of "pc".
576 * Do so within the context "pc".
577 * The location of the statement is set to "loc".
579 static struct pet_scop *scop_from_non_affine_condition(
580 __isl_take pet_expr *cond, int stmt_nr,
581 __isl_take isl_multi_pw_aff *index,
582 __isl_take pet_loc *loc, __isl_keep pet_context *pc)
584 pet_expr *expr, *write;
586 cond = pet_context_evaluate_expr(pc, cond);
588 write = pet_expr_from_index(index);
589 write = pet_expr_access_set_write(write, 1);
590 write = pet_expr_access_set_read(write, 0);
591 expr = pet_expr_new_binary(1, pet_op_assign, write, cond);
593 return scop_from_evaluated_expr(expr, stmt_nr, loc, pc);
596 /* Given that "scop" has an affine skip condition of type pet_skip_now,
597 * apply this skip condition to the domain of "pc".
598 * That is, remove the elements satisfying the skip condition from
599 * the domain of "pc".
601 static __isl_give pet_context *apply_affine_continue(__isl_take pet_context *pc,
602 struct pet_scop *scop)
604 isl_set *domain, *skip;
606 skip = pet_scop_get_affine_skip_domain(scop, pet_skip_now);
607 domain = pet_context_get_domain(pc);
608 domain = isl_set_subtract(domain, skip);
609 pc = pet_context_intersect_domain(pc, domain);
611 return pc;
614 /* Add a scop for evaluating the loop increment "inc" add the end
615 * of a loop body "scop" within the context "pc".
617 * The skip conditions resulting from continue statements inside
618 * the body do not apply to "inc", but those resulting from break
619 * statements do need to get applied.
621 static struct pet_scop *scop_add_inc(struct pet_scop *scop,
622 __isl_take pet_expr *inc, __isl_take pet_loc *loc,
623 __isl_keep pet_context *pc, struct pet_state *state)
625 struct pet_scop *scop_inc;
627 pc = pet_context_copy(pc);
629 if (pet_scop_has_skip(scop, pet_skip_later)) {
630 isl_multi_pw_aff *skip;
631 skip = pet_scop_get_skip(scop, pet_skip_later);
632 scop = pet_scop_set_skip(scop, pet_skip_now, skip);
633 if (pet_scop_has_affine_skip(scop, pet_skip_now))
634 pc = apply_affine_continue(pc, scop);
635 } else
636 pet_scop_reset_skip(scop, pet_skip_now);
637 scop_inc = scop_from_expr(inc, state->n_stmt++, loc, pc);
638 scop_inc = pet_scop_prefix(scop_inc, 2);
639 scop = pet_scop_add_seq(state->ctx, scop, scop_inc);
641 pet_context_free(pc);
643 return scop;
646 /* Construct a generic while scop, with iteration domain
647 * { [t] : t >= 0 } around the scop for "tree_body" within the context "pc".
648 * The domain of "pc" has already been extended with this infinite loop
650 * { [t] : t >= 0 }
652 * The scop consists of two parts,
653 * one for evaluating the condition "cond" and one for the body.
654 * If "expr_inc" is not NULL, then a scop for evaluating this expression
655 * is added at the end of the body,
656 * after replacing any skip conditions resulting from continue statements
657 * by the skip conditions resulting from break statements (if any).
659 * The schedule is adjusted to reflect that the condition is evaluated
660 * before the body is executed and the body is filtered to depend
661 * on the result of the condition evaluating to true on all iterations
662 * up to the current iteration, while the evaluation of the condition itself
663 * is filtered to depend on the result of the condition evaluating to true
664 * on all previous iterations.
665 * The context of the scop representing the body is dropped
666 * because we don't know how many times the body will be executed,
667 * if at all.
669 * If the body contains any break, then it is taken into
670 * account in apply_affine_break (if the skip condition is affine)
671 * or in scop_add_break (if the skip condition is not affine).
673 * Note that in case of an affine skip condition,
674 * since we are dealing with a loop without loop iterator,
675 * the skip condition cannot refer to the current loop iterator and
676 * so effectively, the effect on the iteration domain is of the form
678 * { [outer,0]; [outer,t] : t >= 1 and not skip }
680 static struct pet_scop *scop_from_non_affine_while(__isl_take pet_expr *cond,
681 __isl_take pet_loc *loc, __isl_keep pet_tree *tree_body,
682 __isl_take pet_expr *expr_inc, __isl_take pet_context *pc,
683 struct pet_state *state)
685 isl_ctx *ctx;
686 isl_id *id_test, *id_break_test;
687 isl_space *space;
688 isl_multi_pw_aff *test_index;
689 isl_set *domain;
690 isl_set *skip;
691 isl_aff *sched;
692 struct pet_scop *scop, *scop_body;
693 int has_affine_break;
694 int has_var_break;
696 ctx = state->ctx;
697 space = pet_context_get_space(pc);
698 test_index = pet_create_test_index(space, state->n_test++);
699 scop = scop_from_non_affine_condition(cond, state->n_stmt++,
700 isl_multi_pw_aff_copy(test_index),
701 pet_loc_copy(loc), pc);
702 id_test = isl_multi_pw_aff_get_tuple_id(test_index, isl_dim_out);
703 domain = pet_context_get_domain(pc);
704 scop = pet_scop_add_boolean_array(scop, isl_set_copy(domain),
705 test_index, state->int_size);
707 sched = map_to_last(pc);
709 scop_body = scop_from_tree(tree_body, pc, state);
711 has_affine_break = pet_scop_has_affine_skip(scop_body, pet_skip_later);
712 if (has_affine_break)
713 skip = pet_scop_get_affine_skip_domain(scop_body,
714 pet_skip_later);
715 has_var_break = pet_scop_has_var_skip(scop_body, pet_skip_later);
716 if (has_var_break)
717 id_break_test = pet_scop_get_skip_id(scop_body, pet_skip_later);
719 scop = pet_scop_prefix(scop, 0);
720 scop = pet_scop_embed(scop, isl_set_copy(domain), isl_aff_copy(sched));
721 scop_body = pet_scop_reset_context(scop_body);
722 scop_body = pet_scop_prefix(scop_body, 1);
723 if (expr_inc) {
724 scop_body = scop_add_inc(scop_body, expr_inc, loc, pc, state);
725 } else
726 pet_loc_free(loc);
727 scop_body = pet_scop_embed(scop_body, isl_set_copy(domain), sched);
729 if (has_affine_break) {
730 domain = apply_affine_break(domain, skip, 1, 0, NULL);
731 scop = pet_scop_intersect_domain_prefix(scop,
732 isl_set_copy(domain));
733 scop_body = pet_scop_intersect_domain_prefix(scop_body,
734 isl_set_copy(domain));
736 if (has_var_break) {
737 scop = scop_add_break(scop, isl_id_copy(id_break_test),
738 isl_set_copy(domain), isl_val_one(ctx));
739 scop_body = scop_add_break(scop_body, id_break_test,
740 isl_set_copy(domain), isl_val_one(ctx));
742 scop = scop_add_while(scop, scop_body, id_test, domain,
743 isl_val_one(ctx));
745 pet_context_free(pc);
746 return scop;
749 /* Check if the while loop is of the form
751 * while (affine expression)
752 * body
754 * If so, call scop_from_affine_while to construct a scop.
756 * Otherwise, pass control to scop_from_non_affine_while.
758 * "pc" is the context in which the affine expressions in the scop are created.
759 * The domain of "pc" is extended with an infinite loop
761 * { [t] : t >= 0 }
763 * before passing control to scop_from_affine_while or
764 * scop_from_non_affine_while.
766 static struct pet_scop *scop_from_while(__isl_keep pet_tree *tree,
767 __isl_keep pet_context *pc, struct pet_state *state)
769 pet_expr *cond_expr;
770 isl_pw_aff *pa;
772 if (!tree)
773 return NULL;
775 pc = pet_context_copy(pc);
776 pc = pet_context_clear_writes_in_tree(pc, tree->u.l.body);
778 cond_expr = pet_expr_copy(tree->u.l.cond);
779 cond_expr = pet_context_evaluate_expr(pc, cond_expr);
780 pa = pet_expr_extract_affine_condition(cond_expr, pc);
781 pet_expr_free(cond_expr);
783 pc = pet_context_add_infinite_loop(pc);
785 if (!pa)
786 goto error;
788 if (!isl_pw_aff_involves_nan(pa))
789 return scop_from_affine_while(tree, pa, pc, state);
790 isl_pw_aff_free(pa);
791 return scop_from_non_affine_while(pet_expr_copy(tree->u.l.cond),
792 pet_tree_get_loc(tree), tree->u.l.body, NULL,
793 pc, state);
794 error:
795 pet_context_free(pc);
796 return NULL;
799 /* Check whether "cond" expresses a simple loop bound
800 * on the final set dimension.
801 * In particular, if "up" is set then "cond" should contain only
802 * upper bounds on the final set dimension.
803 * Otherwise, it should contain only lower bounds.
805 static int is_simple_bound(__isl_keep isl_set *cond, __isl_keep isl_val *inc)
807 int pos;
809 pos = isl_set_dim(cond, isl_dim_set) - 1;
810 if (isl_val_is_pos(inc))
811 return !isl_set_dim_has_any_lower_bound(cond, isl_dim_set, pos);
812 else
813 return !isl_set_dim_has_any_upper_bound(cond, isl_dim_set, pos);
816 /* Extend a condition on a given iteration of a loop to one that
817 * imposes the same condition on all previous iterations.
818 * "domain" expresses the lower [upper] bound on the iterations
819 * when inc is positive [negative] in its final dimension.
821 * In particular, we construct the condition (when inc is positive)
823 * forall i' : (domain(i') and i' <= i) => cond(i')
825 * (where "<=" applies to the final dimension)
826 * which is equivalent to
828 * not exists i' : domain(i') and i' <= i and not cond(i')
830 * We construct this set by subtracting the satisfying cond from domain,
831 * applying a map
833 * { [i'] -> [i] : i' <= i }
835 * and then subtracting the result from domain again.
837 static __isl_give isl_set *valid_for_each_iteration(__isl_take isl_set *cond,
838 __isl_take isl_set *domain, __isl_take isl_val *inc)
840 isl_space *space;
841 isl_map *previous_to_this;
842 int i, dim;
844 dim = isl_set_dim(cond, isl_dim_set);
845 space = isl_space_map_from_set(isl_set_get_space(cond));
846 previous_to_this = isl_map_universe(space);
847 for (i = 0; i + 1 < dim; ++i)
848 previous_to_this = isl_map_equate(previous_to_this,
849 isl_dim_in, i, isl_dim_out, i);
850 if (isl_val_is_pos(inc))
851 previous_to_this = isl_map_order_le(previous_to_this,
852 isl_dim_in, dim - 1, isl_dim_out, dim - 1);
853 else
854 previous_to_this = isl_map_order_ge(previous_to_this,
855 isl_dim_in, dim - 1, isl_dim_out, dim - 1);
857 cond = isl_set_subtract(isl_set_copy(domain), cond);
858 cond = isl_set_apply(cond, previous_to_this);
859 cond = isl_set_subtract(domain, cond);
861 isl_val_free(inc);
863 return cond;
866 /* Given an initial value of the form
868 * { [outer,i] -> init(outer) }
870 * construct a domain of the form
872 * { [outer,i] : exists a: i = init(outer) + a * inc and a >= 0 }
874 static __isl_give isl_set *strided_domain(__isl_take isl_pw_aff *init,
875 __isl_take isl_val *inc)
877 int dim;
878 isl_aff *aff;
879 isl_space *space;
880 isl_local_space *ls;
881 isl_set *set;
883 dim = isl_pw_aff_dim(init, isl_dim_in);
885 init = isl_pw_aff_add_dims(init, isl_dim_in, 1);
886 space = isl_pw_aff_get_domain_space(init);
887 ls = isl_local_space_from_space(space);
888 aff = isl_aff_zero_on_domain(isl_local_space_copy(ls));
889 aff = isl_aff_add_coefficient_val(aff, isl_dim_in, dim, inc);
890 init = isl_pw_aff_add(init, isl_pw_aff_from_aff(aff));
892 aff = isl_aff_var_on_domain(ls, isl_dim_set, dim - 1);
893 set = isl_pw_aff_eq_set(isl_pw_aff_from_aff(aff), init);
895 set = isl_set_lower_bound_si(set, isl_dim_set, dim, 0);
896 set = isl_set_project_out(set, isl_dim_set, dim, 1);
898 return set;
901 /* Assuming "cond" represents a bound on a loop where the loop
902 * iterator "iv" is incremented (or decremented) by one, check if wrapping
903 * is possible.
905 * Under the given assumptions, wrapping is only possible if "cond" allows
906 * for the last value before wrapping, i.e., 2^width - 1 in case of an
907 * increasing iterator and 0 in case of a decreasing iterator.
909 static int can_wrap(__isl_keep isl_set *cond, __isl_keep pet_expr *iv,
910 __isl_keep isl_val *inc)
912 int cw;
913 isl_ctx *ctx;
914 isl_val *limit;
915 isl_set *test;
917 test = isl_set_copy(cond);
919 ctx = isl_set_get_ctx(test);
920 if (isl_val_is_neg(inc))
921 limit = isl_val_zero(ctx);
922 else {
923 limit = isl_val_int_from_ui(ctx, pet_expr_get_type_size(iv));
924 limit = isl_val_2exp(limit);
925 limit = isl_val_sub_ui(limit, 1);
928 test = isl_set_fix_val(cond, isl_dim_set, 0, limit);
929 cw = !isl_set_is_empty(test);
930 isl_set_free(test);
932 return cw;
935 /* Given a space
937 * { [outer, v] },
939 * construct the following affine expression on this space
941 * { [outer, v] -> [outer, v mod 2^width] }
943 * where width is the number of bits used to represent the values
944 * of the unsigned variable "iv".
946 static __isl_give isl_multi_aff *compute_wrapping(__isl_take isl_space *space,
947 __isl_keep pet_expr *iv)
949 int dim;
950 isl_ctx *ctx;
951 isl_val *mod;
952 isl_aff *aff;
953 isl_multi_aff *ma;
955 dim = isl_space_dim(space, isl_dim_set);
957 ctx = isl_space_get_ctx(space);
958 mod = isl_val_int_from_ui(ctx, pet_expr_get_type_size(iv));
959 mod = isl_val_2exp(mod);
961 space = isl_space_map_from_set(space);
962 ma = isl_multi_aff_identity(space);
964 aff = isl_multi_aff_get_aff(ma, dim - 1);
965 aff = isl_aff_mod_val(aff, mod);
966 ma = isl_multi_aff_set_aff(ma, dim - 1, aff);
968 return ma;
971 /* Given two sets in the space
973 * { [l,i] },
975 * where l represents the outer loop iterators, compute the set
976 * of values of l that ensure that "set1" is a subset of "set2".
978 * set1 is a subset of set2 if
980 * forall i: set1(l,i) => set2(l,i)
982 * or
984 * not exists i: set1(l,i) and not set2(l,i)
986 * i.e.,
988 * not exists i: (set1 \ set2)(l,i)
990 static __isl_give isl_set *enforce_subset(__isl_take isl_set *set1,
991 __isl_take isl_set *set2)
993 int pos;
995 pos = isl_set_dim(set1, isl_dim_set) - 1;
996 set1 = isl_set_subtract(set1, set2);
997 set1 = isl_set_eliminate(set1, isl_dim_set, pos, 1);
998 return isl_set_complement(set1);
1001 /* Compute the set of outer iterator values for which "cond" holds
1002 * on the next iteration of the inner loop for each element of "dom".
1004 * We first construct mapping { [l,i] -> [l,i + inc] } (where l refers
1005 * to the outer loop iterators), plug that into "cond"
1006 * and then compute the set of outer iterators for which "dom" is a subset
1007 * of the result.
1009 static __isl_give isl_set *valid_on_next(__isl_take isl_set *cond,
1010 __isl_take isl_set *dom, __isl_take isl_val *inc)
1012 int pos;
1013 isl_space *space;
1014 isl_aff *aff;
1015 isl_multi_aff *ma;
1017 pos = isl_set_dim(dom, isl_dim_set) - 1;
1018 space = isl_set_get_space(dom);
1019 space = isl_space_map_from_set(space);
1020 ma = isl_multi_aff_identity(space);
1021 aff = isl_multi_aff_get_aff(ma, pos);
1022 aff = isl_aff_add_constant_val(aff, inc);
1023 ma = isl_multi_aff_set_aff(ma, pos, aff);
1024 cond = isl_set_preimage_multi_aff(cond, ma);
1026 return enforce_subset(dom, cond);
1029 /* Extract the for loop "tree" as a while loop within the context "pc_init".
1030 * In particular, "pc_init" represents the context of the loop,
1031 * whereas "pc" represents the context of the body of the loop and
1032 * has already had its domain extended with an infinite loop
1034 * { [t] : t >= 0 }
1036 * The for loop has the form
1038 * for (iv = init; cond; iv += inc)
1039 * body;
1041 * and is treated as
1043 * iv = init;
1044 * while (cond) {
1045 * body;
1046 * iv += inc;
1049 * except that the skips resulting from any continue statements
1050 * in body do not apply to the increment, but are replaced by the skips
1051 * resulting from break statements.
1053 * If the loop iterator is declared in the for loop, then it is killed before
1054 * and after the loop.
1056 static struct pet_scop *scop_from_non_affine_for(__isl_keep pet_tree *tree,
1057 __isl_keep pet_context *init_pc, __isl_take pet_context *pc,
1058 struct pet_state *state)
1060 int declared;
1061 isl_id *iv;
1062 pet_expr *expr_iv, *init, *inc;
1063 struct pet_scop *scop_init, *scop;
1064 int type_size;
1065 struct pet_array *array;
1066 struct pet_scop *scop_kill;
1068 iv = pet_expr_access_get_id(tree->u.l.iv);
1069 pc = pet_context_clear_value(pc, iv);
1071 declared = tree->u.l.declared;
1073 expr_iv = pet_expr_copy(tree->u.l.iv);
1074 type_size = pet_expr_get_type_size(expr_iv);
1075 init = pet_expr_copy(tree->u.l.init);
1076 init = pet_expr_new_binary(type_size, pet_op_assign, expr_iv, init);
1077 scop_init = scop_from_expr(init, state->n_stmt++,
1078 pet_tree_get_loc(tree), init_pc);
1079 scop_init = pet_scop_prefix(scop_init, declared);
1081 expr_iv = pet_expr_copy(tree->u.l.iv);
1082 type_size = pet_expr_get_type_size(expr_iv);
1083 inc = pet_expr_copy(tree->u.l.inc);
1084 inc = pet_expr_new_binary(type_size, pet_op_add_assign, expr_iv, inc);
1086 scop = scop_from_non_affine_while(pet_expr_copy(tree->u.l.cond),
1087 pet_tree_get_loc(tree), tree->u.l.body, inc,
1088 pet_context_copy(pc), state);
1090 scop = pet_scop_prefix(scop, declared + 1);
1091 scop = pet_scop_add_seq(state->ctx, scop_init, scop);
1093 pet_context_free(pc);
1095 if (!declared)
1096 return scop;
1098 array = extract_array(tree->u.l.iv, init_pc, state);
1099 if (array)
1100 array->declared = 1;
1101 scop_kill = kill(pet_tree_get_loc(tree), array, init_pc, state);
1102 scop_kill = pet_scop_prefix(scop_kill, 0);
1103 scop = pet_scop_add_seq(state->ctx, scop_kill, scop);
1104 scop_kill = kill(pet_tree_get_loc(tree), array, init_pc, state);
1105 scop_kill = pet_scop_add_array(scop_kill, array);
1106 scop_kill = pet_scop_prefix(scop_kill, 3);
1107 scop = pet_scop_add_seq(state->ctx, scop, scop_kill);
1109 return scop;
1112 /* Given an access expression "expr", is the variable accessed by
1113 * "expr" assigned anywhere inside "tree"?
1115 static int is_assigned(__isl_keep pet_expr *expr, __isl_keep pet_tree *tree)
1117 int assigned = 0;
1118 isl_id *id;
1120 id = pet_expr_access_get_id(expr);
1121 assigned = pet_tree_writes(tree, id);
1122 isl_id_free(id);
1124 return assigned;
1127 /* Are all nested access parameters in "pa" allowed given "tree".
1128 * In particular, is none of them written by anywhere inside "tree".
1130 * If "tree" has any continue or break nodes in the current loop level,
1131 * then no nested access parameters are allowed.
1132 * In particular, if there is any nested access in a guard
1133 * for a piece of code containing a "continue", then we want to introduce
1134 * a separate statement for evaluating this guard so that we can express
1135 * that the result is false for all previous iterations.
1137 static int is_nested_allowed(__isl_keep isl_pw_aff *pa,
1138 __isl_keep pet_tree *tree)
1140 int i, nparam;
1142 if (!tree)
1143 return -1;
1145 if (!pet_nested_any_in_pw_aff(pa))
1146 return 1;
1148 if (pet_tree_has_continue_or_break(tree))
1149 return 0;
1151 nparam = isl_pw_aff_dim(pa, isl_dim_param);
1152 for (i = 0; i < nparam; ++i) {
1153 isl_id *id = isl_pw_aff_get_dim_id(pa, isl_dim_param, i);
1154 pet_expr *expr;
1155 int allowed;
1157 if (!pet_nested_in_id(id)) {
1158 isl_id_free(id);
1159 continue;
1162 expr = pet_nested_extract_expr(id);
1163 allowed = pet_expr_get_type(expr) == pet_expr_access &&
1164 !is_assigned(expr, tree);
1166 pet_expr_free(expr);
1167 isl_id_free(id);
1169 if (!allowed)
1170 return 0;
1173 return 1;
1176 /* Internal data structure for collect_local.
1177 * "pc" and "state" are needed to extract pet_arrays for the local variables.
1178 * "local" collects the results.
1180 struct pet_tree_collect_local_data {
1181 pet_context *pc;
1182 struct pet_state *state;
1183 isl_union_set *local;
1186 /* Add the variable accessed by "var" to data->local.
1187 * We extract a representation of the variable from
1188 * the pet_array constructed using extract_array
1189 * to ensure consistency with the rest of the scop.
1191 static int add_local(struct pet_tree_collect_local_data *data,
1192 __isl_keep pet_expr *var)
1194 struct pet_array *array;
1195 isl_set *universe;
1197 array = extract_array(var, data->pc, data->state);
1198 if (!array)
1199 return -1;
1201 universe = isl_set_universe(isl_set_get_space(array->extent));
1202 data->local = isl_union_set_add_set(data->local, universe);
1203 pet_array_free(array);
1205 return 0;
1208 /* If the node "tree" declares a variable, then add it to
1209 * data->local.
1211 static int extract_local_var(__isl_keep pet_tree *tree, void *user)
1213 enum pet_tree_type type;
1214 struct pet_tree_collect_local_data *data = user;
1216 type = pet_tree_get_type(tree);
1217 if (type == pet_tree_decl || type == pet_tree_decl_init)
1218 return add_local(data, tree->u.d.var);
1220 return 0;
1223 /* If the node "tree" is a for loop that declares its induction variable,
1224 * then add it this induction variable to data->local.
1226 static int extract_local_iterator(__isl_keep pet_tree *tree, void *user)
1228 struct pet_tree_collect_local_data *data = user;
1230 if (pet_tree_get_type(tree) == pet_tree_for && tree->u.l.declared)
1231 return add_local(data, tree->u.l.iv);
1233 return 0;
1236 /* Collect and return all local variables of the for loop represented
1237 * by "tree", with "scop" the corresponding pet_scop.
1238 * "pc" and "state" are needed to extract pet_arrays for the local variables.
1240 * We collect not only the variables that are declared inside "tree",
1241 * but also the loop iterators that are declared anywhere inside
1242 * any possible macro statements in "scop".
1243 * The latter also appear as declared variable in the scop,
1244 * whereas other declared loop iterators only appear implicitly
1245 * in the iteration domains.
1247 static __isl_give isl_union_set *collect_local(struct pet_scop *scop,
1248 __isl_keep pet_tree *tree, __isl_keep pet_context *pc,
1249 struct pet_state *state)
1251 int i;
1252 isl_ctx *ctx;
1253 struct pet_tree_collect_local_data data = { pc, state };
1255 ctx = pet_tree_get_ctx(tree);
1256 data.local = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
1258 if (pet_tree_foreach_sub_tree(tree, &extract_local_var, &data) < 0)
1259 return isl_union_set_free(data.local);
1261 for (i = 0; i < scop->n_stmt; ++i) {
1262 pet_tree *body = scop->stmts[i]->body;
1263 if (pet_tree_foreach_sub_tree(body, &extract_local_iterator,
1264 &data) < 0)
1265 return isl_union_set_free(data.local);
1268 return data.local;
1271 /* Add an independence to "scop" if the for node "tree" was marked
1272 * independent.
1273 * "domain" is the set of loop iterators, with the current for loop
1274 * innermost. If "sign" is positive, then the inner iterator increases.
1275 * Otherwise it decreases.
1276 * "pc" and "state" are needed to extract pet_arrays for the local variables.
1278 * If the tree was marked, then collect all local variables and
1279 * add an independence.
1281 static struct pet_scop *set_independence(struct pet_scop *scop,
1282 __isl_keep pet_tree *tree, __isl_keep isl_set *domain, int sign,
1283 __isl_keep pet_context *pc, struct pet_state *state)
1285 isl_union_set *local;
1287 if (!tree->u.l.independent)
1288 return scop;
1290 local = collect_local(scop, tree, pc, state);
1291 scop = pet_scop_set_independent(scop, domain, local, sign);
1293 return scop;
1296 /* Construct a pet_scop for a for tree with static affine initialization
1297 * and constant increment within the context "pc".
1298 * The domain of "pc" has already been extended with an (at this point
1299 * unbounded) inner loop iterator corresponding to the current for loop.
1301 * The condition is allowed to contain nested accesses, provided
1302 * they are not being written to inside the body of the loop.
1303 * Otherwise, or if the condition is otherwise non-affine, the for loop is
1304 * essentially treated as a while loop, with iteration domain
1305 * { [l,i] : i >= init }, where l refers to the outer loop iterators.
1307 * We extract a pet_scop for the body after intersecting the domain of "pc"
1309 * { [l,i] : i >= init and condition' }
1311 * or
1313 * { [l,i] : i <= init and condition' }
1315 * Where condition' is equal to condition if the latter is
1316 * a simple upper [lower] bound and a condition that is extended
1317 * to apply to all previous iterations otherwise.
1318 * Afterwards, the schedule of the pet_scop is extended with
1320 * { [l,i] -> [i] }
1322 * or
1324 * { [l,i] -> [-i] }
1326 * If the condition is non-affine, then we drop the condition from the
1327 * iteration domain and instead create a separate statement
1328 * for evaluating the condition. The body is then filtered to depend
1329 * on the result of the condition evaluating to true on all iterations
1330 * up to the current iteration, while the evaluation the condition itself
1331 * is filtered to depend on the result of the condition evaluating to true
1332 * on all previous iterations.
1333 * The context of the scop representing the body is dropped
1334 * because we don't know how many times the body will be executed,
1335 * if at all.
1337 * If the stride of the loop is not 1, then "i >= init" is replaced by
1339 * (exists a: i = init + stride * a and a >= 0)
1341 * If the loop iterator i is unsigned, then wrapping may occur.
1342 * We therefore use a virtual iterator instead that does not wrap.
1343 * However, the condition in the code applies
1344 * to the wrapped value, so we need to change condition(l,i)
1345 * into condition([l,i % 2^width]). Similarly, we replace all accesses
1346 * to the original iterator by the wrapping of the virtual iterator.
1347 * Note that there may be no need to perform this final wrapping
1348 * if the loop condition (after wrapping) satisfies certain conditions.
1349 * However, the is_simple_bound condition is not enough since it doesn't
1350 * check if there even is an upper bound.
1352 * Wrapping on unsigned iterators can be avoided entirely if
1353 * loop condition is simple, the loop iterator is incremented
1354 * [decremented] by one and the last value before wrapping cannot
1355 * possibly satisfy the loop condition.
1357 * Valid outer iterators for a for loop are those for which the initial
1358 * value itself, the increment on each domain iteration and
1359 * the condition on both the initial value and
1360 * the result of incrementing the iterator for each iteration of the domain
1361 * can be evaluated.
1362 * If the loop condition is non-affine, then we only consider validity
1363 * of the initial value.
1365 * If the body contains any break, then we keep track of it in "skip"
1366 * (if the skip condition is affine) or it is handled in scop_add_break
1367 * (if the skip condition is not affine).
1368 * Note that the affine break condition needs to be considered with
1369 * respect to previous iterations in the virtual domain (if any).
1371 static struct pet_scop *scop_from_affine_for(__isl_keep pet_tree *tree,
1372 __isl_take isl_pw_aff *init_val, __isl_take isl_pw_aff *pa_inc,
1373 __isl_take isl_val *inc, __isl_take pet_context *pc,
1374 struct pet_state *state)
1376 isl_set *domain;
1377 isl_aff *sched;
1378 isl_set *cond = NULL;
1379 isl_set *skip = NULL;
1380 isl_id *id_test = NULL, *id_break_test;
1381 struct pet_scop *scop, *scop_cond = NULL;
1382 int pos;
1383 int is_one;
1384 int is_unsigned;
1385 int is_simple;
1386 int is_virtual;
1387 int is_non_affine;
1388 int has_affine_break;
1389 int has_var_break;
1390 isl_map *rev_wrap = NULL;
1391 isl_map *init_val_map;
1392 isl_pw_aff *pa;
1393 isl_set *valid_init;
1394 isl_set *valid_cond;
1395 isl_set *valid_cond_init;
1396 isl_set *valid_cond_next;
1397 isl_set *valid_inc;
1398 pet_expr *cond_expr;
1399 pet_context *pc_nested;
1401 pos = pet_context_dim(pc) - 1;
1403 domain = pet_context_get_domain(pc);
1404 cond_expr = pet_expr_copy(tree->u.l.cond);
1405 cond_expr = pet_context_evaluate_expr(pc, cond_expr);
1406 pc_nested = pet_context_copy(pc);
1407 pc_nested = pet_context_set_allow_nested(pc_nested, 1);
1408 pa = pet_expr_extract_affine_condition(cond_expr, pc_nested);
1409 pet_context_free(pc_nested);
1410 pet_expr_free(cond_expr);
1412 valid_inc = isl_pw_aff_domain(pa_inc);
1414 is_unsigned = pet_expr_get_type_size(tree->u.l.iv) > 0;
1416 is_non_affine = isl_pw_aff_involves_nan(pa) ||
1417 !is_nested_allowed(pa, tree->u.l.body);
1418 if (is_non_affine)
1419 pa = isl_pw_aff_free(pa);
1421 valid_cond = isl_pw_aff_domain(isl_pw_aff_copy(pa));
1422 cond = isl_pw_aff_non_zero_set(pa);
1423 if (is_non_affine)
1424 cond = isl_set_universe(isl_set_get_space(domain));
1426 valid_cond = isl_set_coalesce(valid_cond);
1427 is_one = isl_val_is_one(inc) || isl_val_is_negone(inc);
1428 is_virtual = is_unsigned &&
1429 (!is_one || can_wrap(cond, tree->u.l.iv, inc));
1431 init_val_map = isl_map_from_pw_aff(isl_pw_aff_copy(init_val));
1432 init_val_map = isl_map_equate(init_val_map, isl_dim_in, pos,
1433 isl_dim_out, 0);
1434 valid_cond_init = enforce_subset(isl_map_domain(init_val_map),
1435 isl_set_copy(valid_cond));
1436 if (is_one && !is_virtual) {
1437 isl_set *cond;
1439 isl_pw_aff_free(init_val);
1440 pa = pet_expr_extract_comparison(
1441 isl_val_is_pos(inc) ? pet_op_ge : pet_op_le,
1442 tree->u.l.iv, tree->u.l.init, pc);
1443 valid_init = isl_pw_aff_domain(isl_pw_aff_copy(pa));
1444 valid_init = isl_set_eliminate(valid_init, isl_dim_set,
1445 isl_set_dim(domain, isl_dim_set) - 1, 1);
1446 cond = isl_pw_aff_non_zero_set(pa);
1447 domain = isl_set_intersect(domain, cond);
1448 } else {
1449 isl_set *strided;
1451 valid_init = isl_pw_aff_domain(isl_pw_aff_copy(init_val));
1452 strided = strided_domain(init_val, isl_val_copy(inc));
1453 domain = isl_set_intersect(domain, strided);
1456 if (is_virtual) {
1457 isl_multi_aff *wrap;
1458 wrap = compute_wrapping(isl_set_get_space(cond), tree->u.l.iv);
1459 pc = pet_context_preimage_domain(pc, wrap);
1460 rev_wrap = isl_map_from_multi_aff(wrap);
1461 rev_wrap = isl_map_reverse(rev_wrap);
1462 cond = isl_set_apply(cond, isl_map_copy(rev_wrap));
1463 valid_cond = isl_set_apply(valid_cond, isl_map_copy(rev_wrap));
1464 valid_inc = isl_set_apply(valid_inc, isl_map_copy(rev_wrap));
1466 is_simple = is_simple_bound(cond, inc);
1467 if (!is_simple) {
1468 cond = isl_set_gist(cond, isl_set_copy(domain));
1469 is_simple = is_simple_bound(cond, inc);
1471 if (!is_simple)
1472 cond = valid_for_each_iteration(cond,
1473 isl_set_copy(domain), isl_val_copy(inc));
1474 cond = isl_set_align_params(cond, isl_set_get_space(domain));
1475 domain = isl_set_intersect(domain, cond);
1476 sched = map_to_last(pc);
1477 if (isl_val_is_neg(inc))
1478 sched = isl_aff_neg(sched);
1480 valid_cond_next = valid_on_next(valid_cond, isl_set_copy(domain),
1481 isl_val_copy(inc));
1482 valid_inc = enforce_subset(isl_set_copy(domain), valid_inc);
1484 pc = pet_context_intersect_domain(pc, isl_set_copy(domain));
1486 if (is_non_affine) {
1487 isl_space *space;
1488 isl_multi_pw_aff *test_index;
1489 space = isl_set_get_space(domain);
1490 test_index = pet_create_test_index(space, state->n_test++);
1491 scop_cond = scop_from_non_affine_condition(
1492 pet_expr_copy(tree->u.l.cond), state->n_stmt++,
1493 isl_multi_pw_aff_copy(test_index),
1494 pet_tree_get_loc(tree), pc);
1495 id_test = isl_multi_pw_aff_get_tuple_id(test_index,
1496 isl_dim_out);
1497 scop_cond = pet_scop_add_boolean_array(scop_cond,
1498 isl_set_copy(domain), test_index,
1499 state->int_size);
1500 scop_cond = pet_scop_prefix(scop_cond, 0);
1501 scop_cond = pet_scop_embed(scop_cond, isl_set_copy(domain),
1502 isl_aff_copy(sched));
1505 scop = scop_from_tree(tree->u.l.body, pc, state);
1506 has_affine_break = scop &&
1507 pet_scop_has_affine_skip(scop, pet_skip_later);
1508 if (has_affine_break)
1509 skip = pet_scop_get_affine_skip_domain(scop, pet_skip_later);
1510 has_var_break = scop && pet_scop_has_var_skip(scop, pet_skip_later);
1511 if (has_var_break)
1512 id_break_test = pet_scop_get_skip_id(scop, pet_skip_later);
1513 if (is_non_affine) {
1514 scop = pet_scop_reset_context(scop);
1515 scop = pet_scop_prefix(scop, 1);
1517 scop = pet_scop_embed(scop, isl_set_copy(domain), sched);
1518 scop = pet_scop_resolve_nested(scop);
1519 if (has_affine_break) {
1520 domain = apply_affine_break(domain, skip, isl_val_sgn(inc),
1521 is_virtual, rev_wrap);
1522 scop = pet_scop_intersect_domain_prefix(scop,
1523 isl_set_copy(domain));
1525 isl_map_free(rev_wrap);
1526 if (has_var_break)
1527 scop = scop_add_break(scop, id_break_test, isl_set_copy(domain),
1528 isl_val_copy(inc));
1529 if (is_non_affine) {
1530 scop = scop_add_while(scop_cond, scop, id_test, domain,
1531 isl_val_copy(inc));
1532 isl_set_free(valid_inc);
1533 } else {
1534 valid_inc = isl_set_intersect(valid_inc, valid_cond_next);
1535 valid_inc = isl_set_intersect(valid_inc, valid_cond_init);
1536 valid_inc = isl_set_project_out(valid_inc, isl_dim_set, pos, 1);
1537 scop = pet_scop_restrict_context(scop, valid_inc);
1538 scop = set_independence(scop, tree, domain, isl_val_sgn(inc),
1539 pc, state);
1540 isl_set_free(domain);
1543 isl_val_free(inc);
1545 valid_init = isl_set_project_out(valid_init, isl_dim_set, pos, 1);
1546 scop = pet_scop_restrict_context(scop, valid_init);
1548 pet_context_free(pc);
1549 return scop;
1552 /* Construct a pet_scop for a for statement within the context of "pc".
1554 * We update the context to reflect the writes to the loop variable and
1555 * the writes inside the body.
1557 * Then we check if the initialization of the for loop
1558 * is a static affine value and the increment is a constant.
1559 * If so, we construct the pet_scop using scop_from_affine_for.
1560 * Otherwise, we treat the for loop as a while loop
1561 * in scop_from_non_affine_for.
1563 * Note that the initialization and the increment are extracted
1564 * in a context where the current loop iterator has been added
1565 * to the context. If these turn out not be affine, then we
1566 * have reconstruct the body context without an assignment
1567 * to this loop iterator, as this variable will then not be
1568 * treated as a dimension of the iteration domain, but as any
1569 * other variable.
1571 static struct pet_scop *scop_from_for(__isl_keep pet_tree *tree,
1572 __isl_keep pet_context *init_pc, struct pet_state *state)
1574 isl_id *iv;
1575 isl_val *inc;
1576 isl_pw_aff *pa_inc, *init_val;
1577 pet_context *pc, *pc_init_val;
1579 if (!tree)
1580 return NULL;
1582 iv = pet_expr_access_get_id(tree->u.l.iv);
1583 pc = pet_context_copy(init_pc);
1584 pc = pet_context_add_inner_iterator(pc, iv);
1585 pc = pet_context_clear_writes_in_tree(pc, tree->u.l.body);
1587 pc_init_val = pet_context_copy(pc);
1588 pc_init_val = pet_context_clear_value(pc_init_val, isl_id_copy(iv));
1589 init_val = pet_expr_extract_affine(tree->u.l.init, pc_init_val);
1590 pet_context_free(pc_init_val);
1591 pa_inc = pet_expr_extract_affine(tree->u.l.inc, pc);
1592 inc = pet_extract_cst(pa_inc);
1593 if (!pa_inc || !init_val || !inc)
1594 goto error;
1595 if (!isl_pw_aff_involves_nan(pa_inc) &&
1596 !isl_pw_aff_involves_nan(init_val) && !isl_val_is_nan(inc))
1597 return scop_from_affine_for(tree, init_val, pa_inc, inc,
1598 pc, state);
1600 isl_pw_aff_free(pa_inc);
1601 isl_pw_aff_free(init_val);
1602 isl_val_free(inc);
1603 pet_context_free(pc);
1605 pc = pet_context_copy(init_pc);
1606 pc = pet_context_add_infinite_loop(pc);
1607 pc = pet_context_clear_writes_in_tree(pc, tree->u.l.body);
1608 return scop_from_non_affine_for(tree, init_pc, pc, state);
1609 error:
1610 isl_pw_aff_free(pa_inc);
1611 isl_pw_aff_free(init_val);
1612 isl_val_free(inc);
1613 pet_context_free(pc);
1614 return NULL;
1617 /* Check whether "expr" is an affine constraint within the context "pc".
1619 static int is_affine_condition(__isl_keep pet_expr *expr,
1620 __isl_keep pet_context *pc)
1622 isl_pw_aff *pa;
1623 int is_affine;
1625 pa = pet_expr_extract_affine_condition(expr, pc);
1626 if (!pa)
1627 return -1;
1628 is_affine = !isl_pw_aff_involves_nan(pa);
1629 isl_pw_aff_free(pa);
1631 return is_affine;
1634 /* Check if the given if statement is a conditional assignement
1635 * with a non-affine condition.
1637 * In particular we check if "stmt" is of the form
1639 * if (condition)
1640 * a = f(...);
1641 * else
1642 * a = g(...);
1644 * where the condition is non-affine and a is some array or scalar access.
1646 static int is_conditional_assignment(__isl_keep pet_tree *tree,
1647 __isl_keep pet_context *pc)
1649 int equal;
1650 isl_ctx *ctx;
1651 pet_expr *expr1, *expr2;
1653 ctx = pet_tree_get_ctx(tree);
1654 if (!pet_options_get_detect_conditional_assignment(ctx))
1655 return 0;
1656 if (tree->type != pet_tree_if_else)
1657 return 0;
1658 if (tree->u.i.then_body->type != pet_tree_expr)
1659 return 0;
1660 if (tree->u.i.else_body->type != pet_tree_expr)
1661 return 0;
1662 expr1 = tree->u.i.then_body->u.e.expr;
1663 expr2 = tree->u.i.else_body->u.e.expr;
1664 if (pet_expr_get_type(expr1) != pet_expr_op)
1665 return 0;
1666 if (pet_expr_get_type(expr2) != pet_expr_op)
1667 return 0;
1668 if (pet_expr_op_get_type(expr1) != pet_op_assign)
1669 return 0;
1670 if (pet_expr_op_get_type(expr2) != pet_op_assign)
1671 return 0;
1672 expr1 = pet_expr_get_arg(expr1, 0);
1673 expr2 = pet_expr_get_arg(expr2, 0);
1674 equal = pet_expr_is_equal(expr1, expr2);
1675 pet_expr_free(expr1);
1676 pet_expr_free(expr2);
1677 if (equal < 0 || !equal)
1678 return 0;
1679 if (is_affine_condition(tree->u.i.cond, pc))
1680 return 0;
1682 return 1;
1685 /* Given that "tree" is of the form
1687 * if (condition)
1688 * a = f(...);
1689 * else
1690 * a = g(...);
1692 * where a is some array or scalar access, construct a pet_scop
1693 * corresponding to this conditional assignment within the context "pc".
1695 * The constructed pet_scop then corresponds to the expression
1697 * a = condition ? f(...) : g(...)
1699 * All access relations in f(...) are intersected with condition
1700 * while all access relation in g(...) are intersected with the complement.
1702 static struct pet_scop *scop_from_conditional_assignment(
1703 __isl_keep pet_tree *tree, __isl_take pet_context *pc,
1704 struct pet_state *state)
1706 int type_size;
1707 isl_pw_aff *pa;
1708 isl_set *cond, *comp;
1709 isl_multi_pw_aff *index;
1710 pet_expr *expr1, *expr2;
1711 pet_expr *pe_cond, *pe_then, *pe_else, *pe, *pe_write;
1712 pet_context *pc_nested;
1713 struct pet_scop *scop;
1715 pe_cond = pet_expr_copy(tree->u.i.cond);
1716 pe_cond = pet_context_evaluate_expr(pc, pe_cond);
1717 pc_nested = pet_context_copy(pc);
1718 pc_nested = pet_context_set_allow_nested(pc_nested, 1);
1719 pa = pet_expr_extract_affine_condition(pe_cond, pc_nested);
1720 pet_context_free(pc_nested);
1721 pet_expr_free(pe_cond);
1722 cond = isl_pw_aff_non_zero_set(isl_pw_aff_copy(pa));
1723 comp = isl_pw_aff_zero_set(isl_pw_aff_copy(pa));
1724 index = isl_multi_pw_aff_from_pw_aff(pa);
1726 expr1 = tree->u.i.then_body->u.e.expr;
1727 expr2 = tree->u.i.else_body->u.e.expr;
1729 pe_cond = pet_expr_from_index(index);
1731 pe_then = pet_expr_get_arg(expr1, 1);
1732 pe_then = pet_context_evaluate_expr(pc, pe_then);
1733 pe_then = pet_expr_restrict(pe_then, cond);
1734 pe_else = pet_expr_get_arg(expr2, 1);
1735 pe_else = pet_context_evaluate_expr(pc, pe_else);
1736 pe_else = pet_expr_restrict(pe_else, comp);
1737 pe_write = pet_expr_get_arg(expr1, 0);
1738 pe_write = pet_context_evaluate_expr(pc, pe_write);
1740 pe = pet_expr_new_ternary(pe_cond, pe_then, pe_else);
1741 type_size = pet_expr_get_type_size(pe_write);
1742 pe = pet_expr_new_binary(type_size, pet_op_assign, pe_write, pe);
1744 scop = scop_from_evaluated_expr(pe, state->n_stmt++,
1745 pet_tree_get_loc(tree), pc);
1747 pet_context_free(pc);
1749 return scop;
1752 /* Construct a pet_scop for a non-affine if statement within the context "pc".
1754 * We create a separate statement that writes the result
1755 * of the non-affine condition to a virtual scalar.
1756 * A constraint requiring the value of this virtual scalar to be one
1757 * is added to the iteration domains of the then branch.
1758 * Similarly, a constraint requiring the value of this virtual scalar
1759 * to be zero is added to the iteration domains of the else branch, if any.
1760 * We adjust the schedules to ensure that the virtual scalar is written
1761 * before it is read.
1763 * If there are any breaks or continues in the then and/or else
1764 * branches, then we may have to compute a new skip condition.
1765 * This is handled using a pet_skip_info object.
1766 * On initialization, the object checks if skip conditions need
1767 * to be computed. If so, it does so in pet_skip_info_if_extract_index and
1768 * adds them in pet_skip_info_if_add.
1770 static struct pet_scop *scop_from_non_affine_if(__isl_keep pet_tree *tree,
1771 __isl_take pet_context *pc, struct pet_state *state)
1773 int has_else;
1774 isl_space *space;
1775 isl_set *domain;
1776 isl_multi_pw_aff *test_index;
1777 struct pet_skip_info skip;
1778 struct pet_scop *scop, *scop_then, *scop_else = NULL;
1780 has_else = tree->type == pet_tree_if_else;
1782 space = pet_context_get_space(pc);
1783 test_index = pet_create_test_index(space, state->n_test++);
1784 scop = scop_from_non_affine_condition(pet_expr_copy(tree->u.i.cond),
1785 state->n_stmt++, isl_multi_pw_aff_copy(test_index),
1786 pet_tree_get_loc(tree), pc);
1787 domain = pet_context_get_domain(pc);
1788 scop = pet_scop_add_boolean_array(scop, domain,
1789 isl_multi_pw_aff_copy(test_index), state->int_size);
1791 scop_then = scop_from_tree(tree->u.i.then_body, pc, state);
1792 if (has_else)
1793 scop_else = scop_from_tree(tree->u.i.else_body, pc, state);
1795 pet_skip_info_if_init(&skip, state->ctx, scop_then, scop_else,
1796 has_else, 0);
1797 pet_skip_info_if_extract_index(&skip, test_index, pc, state);
1799 scop = pet_scop_prefix(scop, 0);
1800 scop_then = pet_scop_prefix(scop_then, 1);
1801 scop_then = pet_scop_filter(scop_then,
1802 isl_multi_pw_aff_copy(test_index), 1);
1803 if (has_else) {
1804 scop_else = pet_scop_prefix(scop_else, 1);
1805 scop_else = pet_scop_filter(scop_else, test_index, 0);
1806 scop_then = pet_scop_add_par(state->ctx, scop_then, scop_else);
1807 } else
1808 isl_multi_pw_aff_free(test_index);
1810 scop = pet_scop_add_seq(state->ctx, scop, scop_then);
1812 scop = pet_skip_info_if_add(&skip, scop, 2);
1814 pet_context_free(pc);
1815 return scop;
1818 /* Construct a pet_scop for an affine if statement within the context "pc".
1820 * The condition is added to the iteration domains of the then branch,
1821 * while the opposite of the condition in added to the iteration domains
1822 * of the else branch, if any.
1824 * If there are any breaks or continues in the then and/or else
1825 * branches, then we may have to compute a new skip condition.
1826 * This is handled using a pet_skip_info_if object.
1827 * On initialization, the object checks if skip conditions need
1828 * to be computed. If so, it does so in pet_skip_info_if_extract_cond and
1829 * adds them in pet_skip_info_if_add.
1831 static struct pet_scop *scop_from_affine_if(__isl_keep pet_tree *tree,
1832 __isl_take isl_pw_aff *cond, __isl_take pet_context *pc,
1833 struct pet_state *state)
1835 int has_else;
1836 isl_ctx *ctx;
1837 isl_set *set, *complement;
1838 isl_set *valid;
1839 struct pet_skip_info skip;
1840 struct pet_scop *scop, *scop_then, *scop_else = NULL;
1841 pet_context *pc_body;
1843 ctx = pet_tree_get_ctx(tree);
1845 has_else = tree->type == pet_tree_if_else;
1847 valid = isl_pw_aff_domain(isl_pw_aff_copy(cond));
1848 set = isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond));
1850 pc_body = pet_context_copy(pc);
1851 pc_body = pet_context_intersect_domain(pc_body, isl_set_copy(set));
1852 scop_then = scop_from_tree(tree->u.i.then_body, pc_body, state);
1853 pet_context_free(pc_body);
1854 if (has_else) {
1855 pc_body = pet_context_copy(pc);
1856 complement = isl_set_copy(valid);
1857 complement = isl_set_subtract(valid, isl_set_copy(set));
1858 pc_body = pet_context_intersect_domain(pc_body,
1859 isl_set_copy(complement));
1860 scop_else = scop_from_tree(tree->u.i.else_body, pc_body, state);
1861 pet_context_free(pc_body);
1864 pet_skip_info_if_init(&skip, ctx, scop_then, scop_else, has_else, 1);
1865 pet_skip_info_if_extract_cond(&skip, cond, pc, state);
1866 isl_pw_aff_free(cond);
1868 scop = pet_scop_restrict(scop_then, set);
1870 if (has_else) {
1871 scop_else = pet_scop_restrict(scop_else, complement);
1872 scop = pet_scop_add_par(ctx, scop, scop_else);
1874 scop = pet_scop_resolve_nested(scop);
1875 scop = pet_scop_restrict_context(scop, valid);
1877 if (pet_skip_info_has_skip(&skip))
1878 scop = pet_scop_prefix(scop, 0);
1879 scop = pet_skip_info_if_add(&skip, scop, 1);
1881 pet_context_free(pc);
1882 return scop;
1885 /* Construct a pet_scop for an if statement within the context "pc".
1887 * If the condition fits the pattern of a conditional assignment,
1888 * then it is handled by scop_from_conditional_assignment.
1890 * Otherwise, we check if the condition is affine.
1891 * If so, we construct the scop in scop_from_affine_if.
1892 * Otherwise, we construct the scop in scop_from_non_affine_if.
1894 * We allow the condition to be dynamic, i.e., to refer to
1895 * scalars or array elements that may be written to outside
1896 * of the given if statement. These nested accesses are then represented
1897 * as output dimensions in the wrapping iteration domain.
1898 * If it is also written _inside_ the then or else branch, then
1899 * we treat the condition as non-affine.
1900 * As explained in extract_non_affine_if, this will introduce
1901 * an extra statement.
1902 * For aesthetic reasons, we want this statement to have a statement
1903 * number that is lower than those of the then and else branches.
1904 * In order to evaluate if we will need such a statement, however, we
1905 * first construct scops for the then and else branches.
1906 * We therefore reserve a statement number if we might have to
1907 * introduce such an extra statement.
1909 static struct pet_scop *scop_from_if(__isl_keep pet_tree *tree,
1910 __isl_keep pet_context *pc, struct pet_state *state)
1912 int has_else;
1913 isl_pw_aff *cond;
1914 pet_expr *cond_expr;
1915 pet_context *pc_nested;
1917 if (!tree)
1918 return NULL;
1920 has_else = tree->type == pet_tree_if_else;
1922 pc = pet_context_copy(pc);
1923 pc = pet_context_clear_writes_in_tree(pc, tree->u.i.then_body);
1924 if (has_else)
1925 pc = pet_context_clear_writes_in_tree(pc, tree->u.i.else_body);
1927 if (is_conditional_assignment(tree, pc))
1928 return scop_from_conditional_assignment(tree, pc, state);
1930 cond_expr = pet_expr_copy(tree->u.i.cond);
1931 cond_expr = pet_context_evaluate_expr(pc, cond_expr);
1932 pc_nested = pet_context_copy(pc);
1933 pc_nested = pet_context_set_allow_nested(pc_nested, 1);
1934 cond = pet_expr_extract_affine_condition(cond_expr, pc_nested);
1935 pet_context_free(pc_nested);
1936 pet_expr_free(cond_expr);
1938 if (!cond) {
1939 pet_context_free(pc);
1940 return NULL;
1943 if (isl_pw_aff_involves_nan(cond)) {
1944 isl_pw_aff_free(cond);
1945 return scop_from_non_affine_if(tree, pc, state);
1948 if ((!is_nested_allowed(cond, tree->u.i.then_body) ||
1949 (has_else && !is_nested_allowed(cond, tree->u.i.else_body)))) {
1950 isl_pw_aff_free(cond);
1951 return scop_from_non_affine_if(tree, pc, state);
1954 return scop_from_affine_if(tree, cond, pc, state);
1957 /* Return a one-dimensional multi piecewise affine expression that is equal
1958 * to the constant 1 and is defined over the given domain.
1960 static __isl_give isl_multi_pw_aff *one_mpa(__isl_take isl_space *space)
1962 isl_local_space *ls;
1963 isl_aff *aff;
1965 ls = isl_local_space_from_space(space);
1966 aff = isl_aff_zero_on_domain(ls);
1967 aff = isl_aff_set_constant_si(aff, 1);
1969 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
1972 /* Construct a pet_scop for a continue statement with the given domain space.
1974 * We simply create an empty scop with a universal pet_skip_now
1975 * skip condition. This skip condition will then be taken into
1976 * account by the enclosing loop construct, possibly after
1977 * being incorporated into outer skip conditions.
1979 static struct pet_scop *scop_from_continue(__isl_keep pet_tree *tree,
1980 __isl_take isl_space *space)
1982 struct pet_scop *scop;
1984 scop = pet_scop_empty(isl_space_copy(space));
1986 scop = pet_scop_set_skip(scop, pet_skip_now, one_mpa(space));
1988 return scop;
1991 /* Construct a pet_scop for a break statement with the given domain space.
1993 * We simply create an empty scop with both a universal pet_skip_now
1994 * skip condition and a universal pet_skip_later skip condition.
1995 * These skip conditions will then be taken into
1996 * account by the enclosing loop construct, possibly after
1997 * being incorporated into outer skip conditions.
1999 static struct pet_scop *scop_from_break(__isl_keep pet_tree *tree,
2000 __isl_take isl_space *space)
2002 struct pet_scop *scop;
2003 isl_multi_pw_aff *skip;
2005 scop = pet_scop_empty(isl_space_copy(space));
2007 skip = one_mpa(space);
2008 scop = pet_scop_set_skip(scop, pet_skip_now,
2009 isl_multi_pw_aff_copy(skip));
2010 scop = pet_scop_set_skip(scop, pet_skip_later, skip);
2012 return scop;
2015 /* Extract a clone of the kill statement in "scop".
2016 * The domain of the clone is given by "domain".
2017 * "scop" is expected to have been created from a DeclStmt
2018 * and should have the kill as its first statement.
2020 static struct pet_scop *extract_kill(__isl_keep isl_set *domain,
2021 struct pet_scop *scop, struct pet_state *state)
2023 pet_expr *kill;
2024 struct pet_stmt *stmt;
2025 isl_multi_pw_aff *index;
2026 isl_map *access;
2027 pet_expr *expr, *arg;
2028 pet_tree *tree;
2030 if (!domain || !scop)
2031 return NULL;
2032 if (scop->n_stmt < 1)
2033 isl_die(isl_set_get_ctx(domain), isl_error_internal,
2034 "expecting at least one statement", return NULL);
2035 stmt = scop->stmts[0];
2036 if (!pet_stmt_is_kill(stmt))
2037 isl_die(isl_set_get_ctx(domain), isl_error_internal,
2038 "expecting kill statement", return NULL);
2040 expr = pet_tree_expr_get_expr(stmt->body);
2041 arg = pet_expr_get_arg(expr, 0);
2042 pet_expr_free(expr);
2043 index = pet_expr_access_get_index(arg);
2044 access = pet_expr_access_get_access(arg);
2045 pet_expr_free(arg);
2046 index = isl_multi_pw_aff_reset_tuple_id(index, isl_dim_in);
2047 access = isl_map_reset_tuple_id(access, isl_dim_in);
2048 kill = pet_expr_kill_from_access_and_index(access, index);
2049 tree = pet_tree_new_expr(kill);
2050 tree = pet_tree_set_loc(tree, pet_loc_copy(stmt->loc));
2051 stmt = pet_stmt_from_pet_tree(isl_set_copy(domain),
2052 state->n_stmt++, tree);
2053 return pet_scop_from_pet_stmt(isl_set_get_space(domain), stmt);
2056 /* Does "tree" represent an assignment to a variable?
2058 * The assignment may be one of
2059 * - a declaration with initialization
2060 * - an expression with a top-level assignment operator
2062 static int is_assignment(__isl_keep pet_tree *tree)
2064 if (!tree)
2065 return 0;
2066 if (tree->type == pet_tree_decl_init)
2067 return 1;
2068 return pet_tree_is_assign(tree);
2071 /* Update "pc" by taking into account the assignment performed by "tree",
2072 * where "tree" satisfies is_assignment.
2074 * In particular, if the lhs of the assignment is a scalar variable and
2075 * if the rhs is an affine expression, then keep track of this value in "pc"
2076 * so that we can plug it in when we later come across the same variable.
2078 * Any previously assigned value to the variable has already been removed
2079 * by scop_handle_writes.
2081 static __isl_give pet_context *handle_assignment(__isl_take pet_context *pc,
2082 __isl_keep pet_tree *tree)
2084 pet_expr *var, *val;
2085 isl_id *id;
2086 isl_pw_aff *pa;
2088 if (pet_tree_get_type(tree) == pet_tree_decl_init) {
2089 var = pet_tree_decl_get_var(tree);
2090 val = pet_tree_decl_get_init(tree);
2091 } else {
2092 pet_expr *expr;
2093 expr = pet_tree_expr_get_expr(tree);
2094 var = pet_expr_get_arg(expr, 0);
2095 val = pet_expr_get_arg(expr, 1);
2096 pet_expr_free(expr);
2099 if (!pet_expr_is_scalar_access(var)) {
2100 pet_expr_free(var);
2101 pet_expr_free(val);
2102 return pc;
2105 pa = pet_expr_extract_affine(val, pc);
2106 if (!pa)
2107 pc = pet_context_free(pc);
2109 if (!isl_pw_aff_involves_nan(pa)) {
2110 id = pet_expr_access_get_id(var);
2111 pc = pet_context_set_value(pc, id, pa);
2112 } else {
2113 isl_pw_aff_free(pa);
2115 pet_expr_free(var);
2116 pet_expr_free(val);
2118 return pc;
2121 /* Mark all arrays in "scop" as being exposed.
2123 static struct pet_scop *mark_exposed(struct pet_scop *scop)
2125 int i;
2127 if (!scop)
2128 return NULL;
2129 for (i = 0; i < scop->n_array; ++i)
2130 scop->arrays[i]->exposed = 1;
2131 return scop;
2134 /* Try and construct a pet_scop corresponding to (part of)
2135 * a sequence of statements within the context "pc".
2137 * After extracting a statement, we update "pc"
2138 * based on the top-level assignments in the statement
2139 * so that we can exploit them in subsequent statements in the same block.
2141 * If there are any breaks or continues in the individual statements,
2142 * then we may have to compute a new skip condition.
2143 * This is handled using a pet_skip_info object.
2144 * On initialization, the object checks if skip conditions need
2145 * to be computed. If so, it does so in pet_skip_info_seq_extract and
2146 * adds them in pet_skip_info_seq_add.
2148 * If "block" is set, then we need to insert kill statements at
2149 * the end of the block for any array that has been declared by
2150 * one of the statements in the sequence. Each of these declarations
2151 * results in the construction of a kill statement at the place
2152 * of the declaration, so we simply collect duplicates of
2153 * those kill statements and append these duplicates to the constructed scop.
2155 * If "block" is not set, then any array declared by one of the statements
2156 * in the sequence is marked as being exposed.
2158 * If autodetect is set, then we allow the extraction of only a subrange
2159 * of the sequence of statements. However, if there is at least one statement
2160 * for which we could not construct a scop and the final range contains
2161 * either no statements or at least one kill, then we discard the entire
2162 * range.
2164 static struct pet_scop *scop_from_block(__isl_keep pet_tree *tree,
2165 __isl_keep pet_context *pc, struct pet_state *state)
2167 int i;
2168 isl_ctx *ctx;
2169 isl_space *space;
2170 isl_set *domain;
2171 struct pet_scop *scop, *kills;
2173 ctx = pet_tree_get_ctx(tree);
2175 space = pet_context_get_space(pc);
2176 domain = pet_context_get_domain(pc);
2177 pc = pet_context_copy(pc);
2178 scop = pet_scop_empty(isl_space_copy(space));
2179 kills = pet_scop_empty(space);
2180 for (i = 0; i < tree->u.b.n; ++i) {
2181 struct pet_scop *scop_i;
2183 if (pet_scop_has_affine_skip(scop, pet_skip_now))
2184 pc = apply_affine_continue(pc, scop);
2185 scop_i = scop_from_tree(tree->u.b.child[i], pc, state);
2186 pc = scop_handle_writes(scop_i, pc);
2187 if (is_assignment(tree->u.b.child[i]))
2188 pc = handle_assignment(pc, tree->u.b.child[i]);
2189 struct pet_skip_info skip;
2190 pet_skip_info_seq_init(&skip, ctx, scop, scop_i);
2191 pet_skip_info_seq_extract(&skip, pc, state);
2192 if (pet_skip_info_has_skip(&skip))
2193 scop_i = pet_scop_prefix(scop_i, 0);
2194 if (scop_i && pet_tree_is_decl(tree->u.b.child[i])) {
2195 if (tree->u.b.block) {
2196 struct pet_scop *kill;
2197 kill = extract_kill(domain, scop_i, state);
2198 kills = pet_scop_add_par(ctx, kills, kill);
2199 } else
2200 scop_i = mark_exposed(scop_i);
2202 scop_i = pet_scop_prefix(scop_i, i);
2203 scop = pet_scop_add_seq(ctx, scop, scop_i);
2205 scop = pet_skip_info_seq_add(&skip, scop, i);
2207 if (!scop)
2208 break;
2210 isl_set_free(domain);
2212 kills = pet_scop_prefix(kills, tree->u.b.n);
2213 scop = pet_scop_add_seq(ctx, scop, kills);
2215 pet_context_free(pc);
2217 return scop;
2220 /* Internal data structure for extract_declared_arrays.
2222 * "pc" and "state" are used to create pet_array objects and kill statements.
2223 * "any" is initialized to 0 by the caller and set to 1 as soon as we have
2224 * found any declared array.
2225 * "scop" has been initialized by the caller and is used to attach
2226 * the created pet_array objects.
2227 * "kill_before" and "kill_after" are created and updated by
2228 * extract_declared_arrays to collect the kills of the arrays.
2230 struct pet_tree_extract_declared_arrays_data {
2231 pet_context *pc;
2232 struct pet_state *state;
2234 isl_ctx *ctx;
2236 int any;
2237 struct pet_scop *scop;
2238 struct pet_scop *kill_before;
2239 struct pet_scop *kill_after;
2242 /* Check if the node "node" declares any array or scalar.
2243 * If so, create the corresponding pet_array and attach it to data->scop.
2244 * Additionally, create two kill statements for the array and add them
2245 * to data->kill_before and data->kill_after.
2247 static int extract_declared_arrays(__isl_keep pet_tree *node, void *user)
2249 enum pet_tree_type type;
2250 struct pet_tree_extract_declared_arrays_data *data = user;
2251 struct pet_array *array;
2252 struct pet_scop *scop_kill;
2253 pet_expr *var;
2255 type = pet_tree_get_type(node);
2256 if (type == pet_tree_decl || type == pet_tree_decl_init)
2257 var = node->u.d.var;
2258 else if (type == pet_tree_for && node->u.l.declared)
2259 var = node->u.l.iv;
2260 else
2261 return 0;
2263 array = extract_array(var, data->pc, data->state);
2264 if (array)
2265 array->declared = 1;
2266 data->scop = pet_scop_add_array(data->scop, array);
2268 scop_kill = kill(pet_tree_get_loc(node), array, data->pc, data->state);
2269 if (!data->any)
2270 data->kill_before = scop_kill;
2271 else
2272 data->kill_before = pet_scop_add_par(data->ctx,
2273 data->kill_before, scop_kill);
2275 scop_kill = kill(pet_tree_get_loc(node), array, data->pc, data->state);
2276 if (!data->any)
2277 data->kill_after = scop_kill;
2278 else
2279 data->kill_after = pet_scop_add_par(data->ctx,
2280 data->kill_after, scop_kill);
2282 data->any = 1;
2284 return 0;
2287 /* Convert a pet_tree that consists of more than a single leaf
2288 * to a pet_scop with a single statement encapsulating the entire pet_tree.
2289 * Do so within the context of "pc".
2291 * After constructing the core scop, we also look for any arrays (or scalars)
2292 * that are declared inside "tree". Each of those arrays is marked as
2293 * having been declared and kill statements for these arrays
2294 * are introduced before and after the core scop.
2295 * Note that the input tree is not a leaf so that the declaration
2296 * cannot occur at the outer level.
2298 static struct pet_scop *scop_from_tree_macro(__isl_take pet_tree *tree,
2299 __isl_take isl_id *label, __isl_keep pet_context *pc,
2300 struct pet_state *state)
2302 struct pet_tree_extract_declared_arrays_data data = { pc, state };
2304 data.scop = scop_from_unevaluated_tree(pet_tree_copy(tree),
2305 state->n_stmt++, pc);
2307 data.any = 0;
2308 data.ctx = pet_context_get_ctx(pc);
2309 if (pet_tree_foreach_sub_tree(tree, &extract_declared_arrays,
2310 &data) < 0)
2311 data.scop = pet_scop_free(data.scop);
2312 pet_tree_free(tree);
2314 if (!data.any)
2315 return data.scop;
2317 data.kill_before = pet_scop_prefix(data.kill_before, 0);
2318 data.scop = pet_scop_prefix(data.scop, 1);
2319 data.kill_after = pet_scop_prefix(data.kill_after, 2);
2321 data.scop = pet_scop_add_seq(data.ctx, data.kill_before, data.scop);
2322 data.scop = pet_scop_add_seq(data.ctx, data.scop, data.kill_after);
2324 return data.scop;
2327 /* Construct a pet_scop that corresponds to the pet_tree "tree"
2328 * within the context "pc" by calling the appropriate function
2329 * based on the type of "tree".
2331 * If the initially constructed pet_scop turns out to involve
2332 * dynamic control and if the user has requested an encapsulation
2333 * of all dynamic control, then this pet_scop is discarded and
2334 * a new pet_scop is created with a single statement representing
2335 * the entire "tree".
2337 static struct pet_scop *scop_from_tree(__isl_keep pet_tree *tree,
2338 __isl_keep pet_context *pc, struct pet_state *state)
2340 isl_ctx *ctx;
2341 struct pet_scop *scop = NULL;
2343 if (!tree)
2344 return NULL;
2346 ctx = pet_tree_get_ctx(tree);
2347 switch (tree->type) {
2348 case pet_tree_error:
2349 return NULL;
2350 case pet_tree_block:
2351 return scop_from_block(tree, pc, state);
2352 case pet_tree_break:
2353 return scop_from_break(tree, pet_context_get_space(pc));
2354 case pet_tree_continue:
2355 return scop_from_continue(tree, pet_context_get_space(pc));
2356 case pet_tree_decl:
2357 case pet_tree_decl_init:
2358 return scop_from_decl(tree, pc, state);
2359 case pet_tree_expr:
2360 return scop_from_unevaluated_tree(pet_tree_copy(tree),
2361 state->n_stmt++, pc);
2362 case pet_tree_if:
2363 case pet_tree_if_else:
2364 scop = scop_from_if(tree, pc, state);
2365 break;
2366 case pet_tree_for:
2367 scop = scop_from_for(tree, pc, state);
2368 break;
2369 case pet_tree_while:
2370 scop = scop_from_while(tree, pc, state);
2371 break;
2372 case pet_tree_infinite_loop:
2373 scop = scop_from_infinite_for(tree, pc, state);
2374 break;
2377 if (!scop)
2378 return NULL;
2380 if (!pet_options_get_encapsulate_dynamic_control(ctx) ||
2381 !pet_scop_has_data_dependent_conditions(scop))
2382 return scop;
2384 pet_scop_free(scop);
2385 return scop_from_tree_macro(pet_tree_copy(tree),
2386 isl_id_copy(tree->label), pc, state);
2389 /* Construct a pet_scop that corresponds to the pet_tree "tree".
2390 * "int_size" is the number of bytes need to represent an integer.
2391 * "extract_array" is a callback that we can use to create a pet_array
2392 * that corresponds to the variable accessed by an expression.
2394 * Initialize the global state, construct a context and then
2395 * construct the pet_scop by recursively visiting the tree.
2397 struct pet_scop *pet_scop_from_pet_tree(__isl_take pet_tree *tree, int int_size,
2398 struct pet_array *(*extract_array)(__isl_keep pet_expr *access,
2399 __isl_keep pet_context *pc, void *user), void *user,
2400 __isl_keep pet_context *pc)
2402 struct pet_scop *scop;
2403 struct pet_state state = { 0 };
2405 if (!tree)
2406 return NULL;
2408 state.ctx = pet_tree_get_ctx(tree);
2409 state.int_size = int_size;
2410 state.extract_array = extract_array;
2411 state.user = user;
2413 scop = scop_from_tree(tree, pc, &state);
2414 scop = pet_scop_set_loc(scop, pet_tree_get_loc(tree));
2416 pet_tree_free(tree);
2418 if (scop)
2419 scop->context = isl_set_params(scop->context);
2421 return scop;