scop_plus.cc: fix typo in comment
[pet.git] / tree2scop.c
blob38de5f6657293250057355bb058588e1e894a9d9
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 <stdlib.h>
36 #include <string.h>
38 #include <isl/id_to_pw_aff.h>
39 #include <isl/union_set.h>
41 #include "aff.h"
42 #include "expr.h"
43 #include "expr_arg.h"
44 #include "nest.h"
45 #include "scop.h"
46 #include "skip.h"
47 #include "state.h"
48 #include "tree2scop.h"
50 /* Update "pc" by taking into account the writes in "stmt".
51 * That is, clear any previously assigned values to variables
52 * that are written by "stmt".
54 static __isl_give pet_context *handle_writes(struct pet_stmt *stmt,
55 __isl_take pet_context *pc)
57 return pet_context_clear_writes_in_tree(pc, stmt->body);
60 /* Update "pc" based on the write accesses in "scop".
62 static __isl_give pet_context *scop_handle_writes(struct pet_scop *scop,
63 __isl_take pet_context *pc)
65 int i;
67 if (!scop)
68 return pet_context_free(pc);
69 for (i = 0; i < scop->n_stmt; ++i)
70 pc = handle_writes(scop->stmts[i], pc);
72 return pc;
75 /* Wrapper around pet_expr_resolve_assume
76 * for use as a callback to pet_tree_map_expr.
78 static __isl_give pet_expr *resolve_assume(__isl_take pet_expr *expr,
79 void *user)
81 pet_context *pc = user;
83 return pet_expr_resolve_assume(expr, pc);
86 /* Check if any expression inside "tree" is an assume expression and
87 * if its single argument can be converted to an affine expression
88 * in the context of "pc".
89 * If so, replace the argument by the affine expression.
91 __isl_give pet_tree *pet_tree_resolve_assume(__isl_take pet_tree *tree,
92 __isl_keep pet_context *pc)
94 return pet_tree_map_expr(tree, &resolve_assume, pc);
97 /* Convert a pet_tree to a pet_scop with one statement within the context "pc".
98 * "tree" has already been evaluated in the context of "pc".
99 * This mainly involves resolving nested expression parameters
100 * and setting the name of the iteration space.
101 * The name is given by tree->label if it is non-NULL. Otherwise,
102 * it is of the form S_<stmt_nr>.
104 static struct pet_scop *scop_from_evaluated_tree(__isl_take pet_tree *tree,
105 int stmt_nr, __isl_keep pet_context *pc)
107 isl_space *space;
108 isl_set *domain;
109 struct pet_stmt *ps;
111 space = pet_context_get_space(pc);
113 tree = pet_tree_resolve_nested(tree, space);
114 tree = pet_tree_resolve_assume(tree, pc);
116 domain = pet_context_get_domain(pc);
117 ps = pet_stmt_from_pet_tree(domain, stmt_nr, tree);
118 return pet_scop_from_pet_stmt(space, ps);
121 /* Convert a top-level pet_expr to a pet_scop with one statement
122 * within the context "pc".
123 * "expr" has already been evaluated in the context of "pc".
124 * We construct a pet_tree from "expr" and continue with
125 * scop_from_evaluated_tree.
126 * The name is of the form S_<stmt_nr>.
127 * The location of the statement is set to "loc".
129 static struct pet_scop *scop_from_evaluated_expr(__isl_take pet_expr *expr,
130 int stmt_nr, __isl_take pet_loc *loc, __isl_keep pet_context *pc)
132 pet_tree *tree;
134 tree = pet_tree_new_expr(expr);
135 tree = pet_tree_set_loc(tree, loc);
136 return scop_from_evaluated_tree(tree, stmt_nr, pc);
139 /* Convert a pet_tree to a pet_scop with one statement within the context "pc".
140 * "tree" has not yet been evaluated in the context of "pc".
141 * We evaluate "tree" in the context of "pc" and continue with
142 * scop_from_evaluated_tree.
143 * The statement name is given by tree->label if it is non-NULL. Otherwise,
144 * it is of the form S_<stmt_nr>.
146 static struct pet_scop *scop_from_unevaluated_tree(__isl_take pet_tree *tree,
147 int stmt_nr, __isl_keep pet_context *pc)
149 tree = pet_context_evaluate_tree(pc, tree);
150 return scop_from_evaluated_tree(tree, stmt_nr, pc);
153 /* Convert a top-level pet_expr to a pet_scop with one statement
154 * within the context "pc", where "expr" has not yet been evaluated
155 * in the context of "pc".
156 * We construct a pet_tree from "expr" and continue with
157 * scop_from_unevaluated_tree.
158 * The statement name is of the form S_<stmt_nr>.
159 * The location of the statement is set to "loc".
161 static struct pet_scop *scop_from_expr(__isl_take pet_expr *expr,
162 int stmt_nr, __isl_take pet_loc *loc, __isl_keep pet_context *pc)
164 pet_tree *tree;
166 tree = pet_tree_new_expr(expr);
167 tree = pet_tree_set_loc(tree, loc);
168 return scop_from_unevaluated_tree(tree, stmt_nr, pc);
171 /* Construct a pet_scop with a single statement killing the entire
172 * array "array".
173 * The location of the statement is set to "loc".
175 static struct pet_scop *kill(__isl_take pet_loc *loc, struct pet_array *array,
176 __isl_keep pet_context *pc, struct pet_state *state)
178 isl_ctx *ctx;
179 isl_id *id;
180 isl_space *space;
181 isl_multi_pw_aff *index;
182 isl_map *access;
183 pet_expr *expr;
184 struct pet_scop *scop;
186 if (!array)
187 goto error;
188 ctx = isl_set_get_ctx(array->extent);
189 access = isl_map_from_range(isl_set_copy(array->extent));
190 id = isl_set_get_tuple_id(array->extent);
191 space = isl_space_alloc(ctx, 0, 0, 0);
192 space = isl_space_set_tuple_id(space, isl_dim_out, id);
193 index = isl_multi_pw_aff_zero(space);
194 expr = pet_expr_kill_from_access_and_index(access, index);
195 return scop_from_expr(expr, state->n_stmt++, loc, pc);
196 error:
197 pet_loc_free(loc);
198 return NULL;
201 /* Construct and return a pet_array corresponding to the variable
202 * accessed by "access" by calling the extract_array callback.
204 static struct pet_array *extract_array(__isl_keep pet_expr *access,
205 __isl_keep pet_context *pc, struct pet_state *state)
207 return state->extract_array(access, pc, state->user);
210 /* Construct a pet_scop for a (single) variable declaration
211 * within the context "pc".
213 * The scop contains the variable being declared (as an array)
214 * and a statement killing the array.
216 * If the declaration comes with an initialization, then the scop
217 * also contains an assignment to the variable.
219 static struct pet_scop *scop_from_decl(__isl_keep pet_tree *tree,
220 __isl_keep pet_context *pc, struct pet_state *state)
222 int type_size;
223 isl_ctx *ctx;
224 struct pet_array *array;
225 struct pet_scop *scop_decl, *scop;
226 pet_expr *lhs, *rhs, *pe;
228 array = extract_array(tree->u.d.var, pc, state);
229 if (array)
230 array->declared = 1;
231 scop_decl = kill(pet_tree_get_loc(tree), array, pc, state);
232 scop_decl = pet_scop_add_array(scop_decl, array);
234 if (tree->type != pet_tree_decl_init)
235 return scop_decl;
237 lhs = pet_expr_copy(tree->u.d.var);
238 rhs = pet_expr_copy(tree->u.d.init);
239 type_size = pet_expr_get_type_size(lhs);
240 pe = pet_expr_new_binary(type_size, pet_op_assign, lhs, rhs);
241 scop = scop_from_expr(pe, state->n_stmt++, pet_tree_get_loc(tree), pc);
243 ctx = pet_tree_get_ctx(tree);
244 scop = pet_scop_add_seq(ctx, scop_decl, scop);
246 return scop;
249 /* Does "tree" represent a kill statement?
250 * That is, is it an expression statement that "calls" __pencil_kill?
252 static int is_pencil_kill(__isl_keep pet_tree *tree)
254 pet_expr *expr;
255 const char *name;
257 if (!tree)
258 return -1;
259 if (tree->type != pet_tree_expr)
260 return 0;
261 expr = tree->u.e.expr;
262 if (pet_expr_get_type(expr) != pet_expr_call)
263 return 0;
264 name = pet_expr_call_get_name(expr);
265 if (!name)
266 return -1;
267 return !strcmp(name, "__pencil_kill");
270 /* Add a kill to "scop" that kills what is accessed by
271 * the access expression "expr".
273 * If the access expression has any arguments (after evaluation
274 * in the context of "pc"), then we ignore it, since we cannot
275 * tell which elements are definitely killed.
277 * Otherwise, we extend the index expression to the dimension
278 * of the accessed array and intersect with the extent of the array and
279 * add a kill expression that kills these array elements is added to "scop".
281 static struct pet_scop *scop_add_kill(struct pet_scop *scop,
282 __isl_take pet_expr *expr, __isl_take pet_loc *loc,
283 __isl_keep pet_context *pc, struct pet_state *state)
285 int dim1, dim2;
286 isl_id *id;
287 isl_multi_pw_aff *index;
288 isl_map *map;
289 pet_expr *kill;
290 struct pet_array *array;
291 struct pet_scop *scop_i;
293 expr = pet_context_evaluate_expr(pc, expr);
294 if (!expr)
295 goto error;
296 if (expr->n_arg != 0) {
297 pet_expr_free(expr);
298 return scop;
300 array = extract_array(expr, pc, state);
301 if (!array)
302 goto error;
303 index = pet_expr_access_get_index(expr);
304 pet_expr_free(expr);
305 map = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index));
306 id = isl_map_get_tuple_id(map, isl_dim_out);
307 dim1 = isl_set_dim(array->extent, isl_dim_set);
308 dim2 = isl_map_dim(map, isl_dim_out);
309 map = isl_map_add_dims(map, isl_dim_out, dim1 - dim2);
310 map = isl_map_set_tuple_id(map, isl_dim_out, id);
311 map = isl_map_intersect_range(map, isl_set_copy(array->extent));
312 pet_array_free(array);
313 kill = pet_expr_kill_from_access_and_index(map, index);
314 scop_i = scop_from_evaluated_expr(kill, state->n_stmt++, loc, pc);
315 scop = pet_scop_add_par(state->ctx, scop, scop_i);
317 return scop;
318 error:
319 pet_expr_free(expr);
320 return pet_scop_free(scop);
323 /* For each argument of the __pencil_kill call in "tree" that
324 * represents an access, add a kill statement to "scop" killing the accessed
325 * elements.
327 static struct pet_scop *scop_from_pencil_kill(__isl_keep pet_tree *tree,
328 __isl_keep pet_context *pc, struct pet_state *state)
330 pet_expr *call;
331 struct pet_scop *scop;
332 int i, n;
334 call = tree->u.e.expr;
336 scop = pet_scop_empty(pet_context_get_space(pc));
338 n = pet_expr_get_n_arg(call);
339 for (i = 0; i < n; ++i) {
340 pet_expr *arg;
341 pet_loc *loc;
343 arg = pet_expr_get_arg(call, i);
344 if (!arg)
345 return pet_scop_free(scop);
346 if (pet_expr_get_type(arg) != pet_expr_access) {
347 pet_expr_free(arg);
348 continue;
350 loc = pet_tree_get_loc(tree);
351 scop = scop_add_kill(scop, arg, loc, pc, state);
354 return scop;
357 /* Construct a pet_scop for an expression statement within the context "pc".
359 * If the expression calls __pencil_kill, then it needs to be converted
360 * into zero or more kill statements.
361 * Otherwise, a scop is extracted directly from the tree.
363 static struct pet_scop *scop_from_tree_expr(__isl_keep pet_tree *tree,
364 __isl_keep pet_context *pc, struct pet_state *state)
366 int is_kill;
368 is_kill = is_pencil_kill(tree);
369 if (is_kill < 0)
370 return NULL;
371 if (is_kill)
372 return scop_from_pencil_kill(tree, pc, state);
373 return scop_from_unevaluated_tree(pet_tree_copy(tree),
374 state->n_stmt++, pc);
377 /* Return those elements in the space of "cond" that come after
378 * (based on "sign") an element in "cond" in the final dimension.
380 static __isl_give isl_set *after(__isl_take isl_set *cond, int sign)
382 isl_space *space;
383 isl_map *previous_to_this;
384 int i, dim;
386 dim = isl_set_dim(cond, isl_dim_set);
387 space = isl_space_map_from_set(isl_set_get_space(cond));
388 previous_to_this = isl_map_universe(space);
389 for (i = 0; i + 1 < dim; ++i)
390 previous_to_this = isl_map_equate(previous_to_this,
391 isl_dim_in, i, isl_dim_out, i);
392 if (sign > 0)
393 previous_to_this = isl_map_order_lt(previous_to_this,
394 isl_dim_in, dim - 1, isl_dim_out, dim - 1);
395 else
396 previous_to_this = isl_map_order_gt(previous_to_this,
397 isl_dim_in, dim - 1, isl_dim_out, dim - 1);
399 cond = isl_set_apply(cond, previous_to_this);
401 return cond;
404 /* Remove those iterations of "domain" that have an earlier iteration
405 * (based on "sign") in the final dimension where "skip" is satisfied.
406 * If "apply_skip_map" is set, then "skip_map" is first applied
407 * to the embedded skip condition before removing it from the domain.
409 static __isl_give isl_set *apply_affine_break(__isl_take isl_set *domain,
410 __isl_take isl_set *skip, int sign,
411 int apply_skip_map, __isl_keep isl_map *skip_map)
413 if (apply_skip_map)
414 skip = isl_set_apply(skip, isl_map_copy(skip_map));
415 skip = isl_set_intersect(skip , isl_set_copy(domain));
416 return isl_set_subtract(domain, after(skip, sign));
419 /* Create a single-dimensional multi-affine expression on the domain space
420 * of "pc" that is equal to the final dimension of this domain.
421 * "loop_nr" is the sequence number of the corresponding loop.
422 * If "id" is not NULL, then it is used as the output tuple name.
423 * Otherwise, the name is constructed as L_<loop_nr>.
425 static __isl_give isl_multi_aff *map_to_last(__isl_keep pet_context *pc,
426 int loop_nr, __isl_keep isl_id *id)
428 int pos;
429 isl_space *space;
430 isl_local_space *ls;
431 isl_aff *aff;
432 isl_multi_aff *ma;
433 char name[50];
434 isl_id *label;
436 space = pet_context_get_space(pc);
437 pos = isl_space_dim(space, isl_dim_set) - 1;
438 ls = isl_local_space_from_space(space);
439 aff = isl_aff_var_on_domain(ls, isl_dim_set, pos);
440 ma = isl_multi_aff_from_aff(aff);
442 if (id) {
443 label = isl_id_copy(id);
444 } else {
445 snprintf(name, sizeof(name), "L_%d", loop_nr);
446 label = isl_id_alloc(pet_context_get_ctx(pc), name, NULL);
448 ma = isl_multi_aff_set_tuple_id(ma, isl_dim_out, label);
450 return ma;
453 /* Create an affine expression that maps elements
454 * of an array "id_test" to the previous element in the final dimension
455 * (according to "inc"), provided this element belongs to "domain".
456 * That is, create the affine expression
458 * { id[outer,x] -> id[outer,x - inc] : (outer,x - inc) in domain }
460 static __isl_give isl_multi_pw_aff *map_to_previous(__isl_take isl_id *id_test,
461 __isl_take isl_set *domain, __isl_take isl_val *inc)
463 int pos;
464 isl_space *space;
465 isl_aff *aff;
466 isl_pw_aff *pa;
467 isl_multi_aff *ma;
468 isl_multi_pw_aff *prev;
470 pos = isl_set_dim(domain, isl_dim_set) - 1;
471 space = isl_set_get_space(domain);
472 space = isl_space_map_from_set(space);
473 ma = isl_multi_aff_identity(space);
474 aff = isl_multi_aff_get_aff(ma, pos);
475 aff = isl_aff_add_constant_val(aff, isl_val_neg(inc));
476 ma = isl_multi_aff_set_aff(ma, pos, aff);
477 domain = isl_set_preimage_multi_aff(domain, isl_multi_aff_copy(ma));
478 prev = isl_multi_pw_aff_from_multi_aff(ma);
479 pa = isl_multi_pw_aff_get_pw_aff(prev, pos);
480 pa = isl_pw_aff_intersect_domain(pa, domain);
481 prev = isl_multi_pw_aff_set_pw_aff(prev, pos, pa);
482 prev = isl_multi_pw_aff_set_tuple_id(prev, isl_dim_out, id_test);
484 return prev;
487 /* Add an implication to "scop" expressing that if an element of
488 * virtual array "id_test" has value "satisfied" then all previous elements
489 * of this array (in the final dimension) also have that value.
490 * The set of previous elements is bounded by "domain".
491 * If "sign" is negative then the iterator
492 * is decreasing and we express that all subsequent array elements
493 * (but still defined previously) have the same value.
495 static struct pet_scop *add_implication(struct pet_scop *scop,
496 __isl_take isl_id *id_test, __isl_take isl_set *domain, int sign,
497 int satisfied)
499 int i, dim;
500 isl_space *space;
501 isl_map *map;
503 dim = isl_set_dim(domain, isl_dim_set);
504 domain = isl_set_set_tuple_id(domain, id_test);
505 space = isl_space_map_from_set(isl_set_get_space(domain));
506 map = isl_map_universe(space);
507 for (i = 0; i + 1 < dim; ++i)
508 map = isl_map_equate(map, isl_dim_in, i, isl_dim_out, i);
509 if (sign > 0)
510 map = isl_map_order_ge(map,
511 isl_dim_in, dim - 1, isl_dim_out, dim - 1);
512 else
513 map = isl_map_order_le(map,
514 isl_dim_in, dim - 1, isl_dim_out, dim - 1);
515 map = isl_map_intersect_range(map, domain);
516 scop = pet_scop_add_implication(scop, map, satisfied);
518 return scop;
521 /* Add a filter to "scop" that imposes that it is only executed
522 * when the variable identified by "id_test" has a zero value
523 * for all previous iterations of "domain".
525 * In particular, add a filter that imposes that the array
526 * has a zero value at the previous iteration of domain and
527 * add an implication that implies that it then has that
528 * value for all previous iterations.
530 static struct pet_scop *scop_add_break(struct pet_scop *scop,
531 __isl_take isl_id *id_test, __isl_take isl_set *domain,
532 __isl_take isl_val *inc)
534 isl_multi_pw_aff *prev;
535 int sign = isl_val_sgn(inc);
537 prev = map_to_previous(isl_id_copy(id_test), isl_set_copy(domain), inc);
538 scop = add_implication(scop, id_test, domain, sign, 0);
539 scop = pet_scop_filter(scop, prev, 0);
541 return scop;
544 static struct pet_scop *scop_from_tree(__isl_keep pet_tree *tree,
545 __isl_keep pet_context *pc, struct pet_state *state);
547 /* Construct a pet_scop for an infinite loop around the given body
548 * within the context "pc".
549 * "loop_id" is the label on the loop or NULL if there is no such label.
551 * The domain of "pc" has already been extended with an infinite loop
553 * { [t] : t >= 0 }
555 * We extract a pet_scop for the body and then embed it in a loop with
556 * schedule
558 * { [outer,t] -> [t] }
560 * If the body contains any break, then it is taken into
561 * account in apply_affine_break (if the skip condition is affine)
562 * or in scop_add_break (if the skip condition is not affine).
564 * Note that in case of an affine skip condition,
565 * since we are dealing with a loop without loop iterator,
566 * the skip condition cannot refer to the current loop iterator and
567 * so effectively, the effect on the iteration domain is of the form
569 * { [outer,0]; [outer,t] : t >= 1 and not skip }
571 static struct pet_scop *scop_from_infinite_loop(__isl_keep pet_tree *body,
572 __isl_keep isl_id *loop_id, __isl_keep pet_context *pc,
573 struct pet_state *state)
575 isl_ctx *ctx;
576 isl_id *id_test;
577 isl_set *domain;
578 isl_set *skip;
579 isl_multi_aff *sched;
580 struct pet_scop *scop;
581 int has_affine_break;
582 int has_var_break;
584 ctx = pet_tree_get_ctx(body);
585 domain = pet_context_get_domain(pc);
586 sched = map_to_last(pc, state->n_loop++, loop_id);
588 scop = scop_from_tree(body, pc, state);
590 has_affine_break = pet_scop_has_affine_skip(scop, pet_skip_later);
591 if (has_affine_break)
592 skip = pet_scop_get_affine_skip_domain(scop, pet_skip_later);
593 has_var_break = pet_scop_has_var_skip(scop, pet_skip_later);
594 if (has_var_break)
595 id_test = pet_scop_get_skip_id(scop, pet_skip_later);
597 scop = pet_scop_reset_skips(scop);
598 scop = pet_scop_embed(scop, isl_set_copy(domain), sched);
599 if (has_affine_break) {
600 domain = apply_affine_break(domain, skip, 1, 0, NULL);
601 scop = pet_scop_intersect_domain_prefix(scop,
602 isl_set_copy(domain));
604 if (has_var_break)
605 scop = scop_add_break(scop, id_test, domain, isl_val_one(ctx));
606 else
607 isl_set_free(domain);
609 return scop;
612 /* Construct a pet_scop for an infinite loop, i.e., a loop of the form
614 * for (;;)
615 * body
617 * within the context "pc".
619 * Extend the domain of "pc" with an extra inner loop
621 * { [t] : t >= 0 }
623 * and construct the scop in scop_from_infinite_loop.
625 static struct pet_scop *scop_from_infinite_for(__isl_keep pet_tree *tree,
626 __isl_keep pet_context *pc, struct pet_state *state)
628 struct pet_scop *scop;
630 pc = pet_context_copy(pc);
631 pc = pet_context_clear_writes_in_tree(pc, tree->u.l.body);
633 pc = pet_context_add_infinite_loop(pc);
635 scop = scop_from_infinite_loop(tree->u.l.body, tree->label, pc, state);
637 pet_context_free(pc);
639 return scop;
642 /* Construct a pet_scop for a while loop of the form
644 * while (pa)
645 * body
647 * within the context "pc".
649 * The domain of "pc" has already been extended with an infinite loop
651 * { [t] : t >= 0 }
653 * Here, we add the constraints on the outer loop iterators
654 * implied by "pa" and construct the scop in scop_from_infinite_loop.
655 * Note that the intersection with these constraints
656 * may result in an empty loop.
658 static struct pet_scop *scop_from_affine_while(__isl_keep pet_tree *tree,
659 __isl_take isl_pw_aff *pa, __isl_take pet_context *pc,
660 struct pet_state *state)
662 struct pet_scop *scop;
663 isl_set *dom, *local;
664 isl_set *valid;
666 valid = isl_pw_aff_domain(isl_pw_aff_copy(pa));
667 dom = isl_pw_aff_non_zero_set(pa);
668 local = isl_set_add_dims(isl_set_copy(dom), isl_dim_set, 1);
669 pc = pet_context_intersect_domain(pc, local);
670 scop = scop_from_infinite_loop(tree->u.l.body, tree->label, pc, state);
671 scop = pet_scop_restrict(scop, dom);
672 scop = pet_scop_restrict_context(scop, valid);
674 pet_context_free(pc);
675 return scop;
678 /* Construct a scop for a while, given the scops for the condition
679 * and the body, the filter identifier and the iteration domain of
680 * the while loop.
682 * In particular, the scop for the condition is filtered to depend
683 * on "id_test" evaluating to true for all previous iterations
684 * of the loop, while the scop for the body is filtered to depend
685 * on "id_test" evaluating to true for all iterations up to the
686 * current iteration.
687 * The actual filter only imposes that this virtual array has
688 * value one on the previous or the current iteration.
689 * The fact that this condition also applies to the previous
690 * iterations is enforced by an implication.
692 * These filtered scops are then combined into a single scop,
693 * with the condition scop scheduled before the body scop.
695 * "sign" is positive if the iterator increases and negative
696 * if it decreases.
698 static struct pet_scop *scop_add_while(struct pet_scop *scop_cond,
699 struct pet_scop *scop_body, __isl_take isl_id *id_test,
700 __isl_take isl_set *domain, __isl_take isl_val *inc)
702 isl_ctx *ctx = isl_set_get_ctx(domain);
703 isl_space *space;
704 isl_multi_pw_aff *test_index;
705 isl_multi_pw_aff *prev;
706 int sign = isl_val_sgn(inc);
707 struct pet_scop *scop;
709 prev = map_to_previous(isl_id_copy(id_test), isl_set_copy(domain), inc);
710 scop_cond = pet_scop_filter(scop_cond, prev, 1);
712 space = isl_space_map_from_set(isl_set_get_space(domain));
713 test_index = isl_multi_pw_aff_identity(space);
714 test_index = isl_multi_pw_aff_set_tuple_id(test_index, isl_dim_out,
715 isl_id_copy(id_test));
716 scop_body = pet_scop_filter(scop_body, test_index, 1);
718 scop = pet_scop_add_seq(ctx, scop_cond, scop_body);
719 scop = add_implication(scop, id_test, domain, sign, 1);
721 return scop;
724 /* Create a pet_scop with a single statement with name S_<stmt_nr>,
725 * evaluating "cond" and writing the result to a virtual scalar,
726 * as expressed by "index".
727 * The expression "cond" has not yet been evaluated in the context of "pc".
728 * Do so within the context "pc".
729 * The location of the statement is set to "loc".
731 static struct pet_scop *scop_from_non_affine_condition(
732 __isl_take pet_expr *cond, int stmt_nr,
733 __isl_take isl_multi_pw_aff *index,
734 __isl_take pet_loc *loc, __isl_keep pet_context *pc)
736 pet_expr *expr, *write;
738 cond = pet_context_evaluate_expr(pc, cond);
740 write = pet_expr_from_index(index);
741 write = pet_expr_access_set_write(write, 1);
742 write = pet_expr_access_set_read(write, 0);
743 expr = pet_expr_new_binary(1, pet_op_assign, write, cond);
745 return scop_from_evaluated_expr(expr, stmt_nr, loc, pc);
748 /* Given that "scop" has an affine skip condition of type pet_skip_now,
749 * apply this skip condition to the domain of "pc".
750 * That is, remove the elements satisfying the skip condition from
751 * the domain of "pc".
753 static __isl_give pet_context *apply_affine_continue(__isl_take pet_context *pc,
754 struct pet_scop *scop)
756 isl_set *domain, *skip;
758 skip = pet_scop_get_affine_skip_domain(scop, pet_skip_now);
759 domain = pet_context_get_domain(pc);
760 domain = isl_set_subtract(domain, skip);
761 pc = pet_context_intersect_domain(pc, domain);
763 return pc;
766 /* Add a scop for evaluating the loop increment "inc" add the end
767 * of a loop body "scop" within the context "pc".
769 * The skip conditions resulting from continue statements inside
770 * the body do not apply to "inc", but those resulting from break
771 * statements do need to get applied.
773 static struct pet_scop *scop_add_inc(struct pet_scop *scop,
774 __isl_take pet_expr *inc, __isl_take pet_loc *loc,
775 __isl_keep pet_context *pc, struct pet_state *state)
777 struct pet_scop *scop_inc;
779 pc = pet_context_copy(pc);
781 if (pet_scop_has_skip(scop, pet_skip_later)) {
782 isl_multi_pw_aff *skip;
783 skip = pet_scop_get_skip(scop, pet_skip_later);
784 scop = pet_scop_set_skip(scop, pet_skip_now, skip);
785 if (pet_scop_has_affine_skip(scop, pet_skip_now))
786 pc = apply_affine_continue(pc, scop);
787 } else
788 pet_scop_reset_skip(scop, pet_skip_now);
789 scop_inc = scop_from_expr(inc, state->n_stmt++, loc, pc);
790 scop = pet_scop_add_seq(state->ctx, scop, scop_inc);
792 pet_context_free(pc);
794 return scop;
797 /* Construct a generic while scop, with iteration domain
798 * { [t] : t >= 0 } around the scop for "tree_body" within the context "pc".
799 * "loop_id" is the label on the loop or NULL if there is no such label.
800 * The domain of "pc" has already been extended with this infinite loop
802 * { [t] : t >= 0 }
804 * The scop consists of two parts,
805 * one for evaluating the condition "cond" and one for the body.
806 * If "expr_inc" is not NULL, then a scop for evaluating this expression
807 * is added at the end of the body,
808 * after replacing any skip conditions resulting from continue statements
809 * by the skip conditions resulting from break statements (if any).
811 * The schedules are combined as a sequence to reflect that the condition is
812 * evaluated before the body is executed and the body is filtered to depend
813 * on the result of the condition evaluating to true on all iterations
814 * up to the current iteration, while the evaluation of the condition itself
815 * is filtered to depend on the result of the condition evaluating to true
816 * on all previous iterations.
817 * The context of the scop representing the body is dropped
818 * because we don't know how many times the body will be executed,
819 * if at all.
821 * If the body contains any break, then it is taken into
822 * account in apply_affine_break (if the skip condition is affine)
823 * or in scop_add_break (if the skip condition is not affine).
825 * Note that in case of an affine skip condition,
826 * since we are dealing with a loop without loop iterator,
827 * the skip condition cannot refer to the current loop iterator and
828 * so effectively, the effect on the iteration domain is of the form
830 * { [outer,0]; [outer,t] : t >= 1 and not skip }
832 static struct pet_scop *scop_from_non_affine_while(__isl_take pet_expr *cond,
833 __isl_take pet_loc *loc, __isl_keep pet_tree *tree_body,
834 __isl_keep isl_id *loop_id, __isl_take pet_expr *expr_inc,
835 __isl_take pet_context *pc, struct pet_state *state)
837 isl_ctx *ctx;
838 isl_id *id_test, *id_break_test;
839 isl_space *space;
840 isl_multi_pw_aff *test_index;
841 isl_set *domain;
842 isl_set *skip;
843 isl_multi_aff *sched;
844 struct pet_scop *scop, *scop_body;
845 int has_affine_break;
846 int has_var_break;
848 ctx = state->ctx;
849 space = pet_context_get_space(pc);
850 test_index = pet_create_test_index(space, state->n_test++);
851 scop = scop_from_non_affine_condition(cond, state->n_stmt++,
852 isl_multi_pw_aff_copy(test_index),
853 pet_loc_copy(loc), pc);
854 id_test = isl_multi_pw_aff_get_tuple_id(test_index, isl_dim_out);
855 domain = pet_context_get_domain(pc);
856 scop = pet_scop_add_boolean_array(scop, isl_set_copy(domain),
857 test_index, state->int_size);
859 sched = map_to_last(pc, state->n_loop++, loop_id);
861 scop_body = scop_from_tree(tree_body, pc, state);
863 has_affine_break = pet_scop_has_affine_skip(scop_body, pet_skip_later);
864 if (has_affine_break)
865 skip = pet_scop_get_affine_skip_domain(scop_body,
866 pet_skip_later);
867 has_var_break = pet_scop_has_var_skip(scop_body, pet_skip_later);
868 if (has_var_break)
869 id_break_test = pet_scop_get_skip_id(scop_body, pet_skip_later);
871 scop_body = pet_scop_reset_context(scop_body);
872 if (expr_inc) {
873 scop_body = scop_add_inc(scop_body, expr_inc, loc, pc, state);
874 } else
875 pet_loc_free(loc);
876 scop_body = pet_scop_reset_skips(scop_body);
878 if (has_affine_break) {
879 domain = apply_affine_break(domain, skip, 1, 0, NULL);
880 scop = pet_scop_intersect_domain_prefix(scop,
881 isl_set_copy(domain));
882 scop_body = pet_scop_intersect_domain_prefix(scop_body,
883 isl_set_copy(domain));
885 if (has_var_break) {
886 scop = scop_add_break(scop, isl_id_copy(id_break_test),
887 isl_set_copy(domain), isl_val_one(ctx));
888 scop_body = scop_add_break(scop_body, id_break_test,
889 isl_set_copy(domain), isl_val_one(ctx));
891 scop = scop_add_while(scop, scop_body, id_test, isl_set_copy(domain),
892 isl_val_one(ctx));
894 scop = pet_scop_embed(scop, domain, sched);
896 pet_context_free(pc);
897 return scop;
900 /* Check if the while loop is of the form
902 * while (affine expression)
903 * body
905 * If so, call scop_from_affine_while to construct a scop.
907 * Otherwise, pass control to scop_from_non_affine_while.
909 * "pc" is the context in which the affine expressions in the scop are created.
910 * The domain of "pc" is extended with an infinite loop
912 * { [t] : t >= 0 }
914 * before passing control to scop_from_affine_while or
915 * scop_from_non_affine_while.
917 static struct pet_scop *scop_from_while(__isl_keep pet_tree *tree,
918 __isl_keep pet_context *pc, struct pet_state *state)
920 pet_expr *cond_expr;
921 isl_pw_aff *pa;
923 if (!tree)
924 return NULL;
926 pc = pet_context_copy(pc);
927 pc = pet_context_clear_writes_in_tree(pc, tree->u.l.body);
929 cond_expr = pet_expr_copy(tree->u.l.cond);
930 cond_expr = pet_context_evaluate_expr(pc, cond_expr);
931 pa = pet_expr_extract_affine_condition(cond_expr, pc);
932 pet_expr_free(cond_expr);
934 pc = pet_context_add_infinite_loop(pc);
936 if (!pa)
937 goto error;
939 if (!isl_pw_aff_involves_nan(pa))
940 return scop_from_affine_while(tree, pa, pc, state);
941 isl_pw_aff_free(pa);
942 return scop_from_non_affine_while(pet_expr_copy(tree->u.l.cond),
943 pet_tree_get_loc(tree), tree->u.l.body,
944 tree->label, NULL, pc, state);
945 error:
946 pet_context_free(pc);
947 return NULL;
950 /* Check whether "cond" expresses a simple loop bound
951 * on the final set dimension.
952 * In particular, if "up" is set then "cond" should contain only
953 * upper bounds on the final set dimension.
954 * Otherwise, it should contain only lower bounds.
956 static int is_simple_bound(__isl_keep isl_set *cond, __isl_keep isl_val *inc)
958 int pos;
960 pos = isl_set_dim(cond, isl_dim_set) - 1;
961 if (isl_val_is_pos(inc))
962 return !isl_set_dim_has_any_lower_bound(cond, isl_dim_set, pos);
963 else
964 return !isl_set_dim_has_any_upper_bound(cond, isl_dim_set, pos);
967 /* Extend a condition on a given iteration of a loop to one that
968 * imposes the same condition on all previous iterations.
969 * "domain" expresses the lower [upper] bound on the iterations
970 * when inc is positive [negative] in its final dimension.
972 * In particular, we construct the condition (when inc is positive)
974 * forall i' : (domain(i') and i' <= i) => cond(i')
976 * (where "<=" applies to the final dimension)
977 * which is equivalent to
979 * not exists i' : domain(i') and i' <= i and not cond(i')
981 * We construct this set by subtracting the satisfying cond from domain,
982 * applying a map
984 * { [i'] -> [i] : i' <= i }
986 * and then subtracting the result from domain again.
988 static __isl_give isl_set *valid_for_each_iteration(__isl_take isl_set *cond,
989 __isl_take isl_set *domain, __isl_take isl_val *inc)
991 isl_space *space;
992 isl_map *previous_to_this;
993 int i, dim;
995 dim = isl_set_dim(cond, isl_dim_set);
996 space = isl_space_map_from_set(isl_set_get_space(cond));
997 previous_to_this = isl_map_universe(space);
998 for (i = 0; i + 1 < dim; ++i)
999 previous_to_this = isl_map_equate(previous_to_this,
1000 isl_dim_in, i, isl_dim_out, i);
1001 if (isl_val_is_pos(inc))
1002 previous_to_this = isl_map_order_le(previous_to_this,
1003 isl_dim_in, dim - 1, isl_dim_out, dim - 1);
1004 else
1005 previous_to_this = isl_map_order_ge(previous_to_this,
1006 isl_dim_in, dim - 1, isl_dim_out, dim - 1);
1008 cond = isl_set_subtract(isl_set_copy(domain), cond);
1009 cond = isl_set_apply(cond, previous_to_this);
1010 cond = isl_set_subtract(domain, cond);
1012 isl_val_free(inc);
1014 return cond;
1017 /* Given an initial value of the form
1019 * { [outer,i] -> init(outer) }
1021 * construct a domain of the form
1023 * { [outer,i] : exists a: i = init(outer) + a * inc and a >= 0 }
1025 static __isl_give isl_set *strided_domain(__isl_take isl_pw_aff *init,
1026 __isl_take isl_val *inc)
1028 int dim;
1029 isl_aff *aff;
1030 isl_space *space;
1031 isl_local_space *ls;
1032 isl_set *set;
1034 dim = isl_pw_aff_dim(init, isl_dim_in);
1036 init = isl_pw_aff_add_dims(init, isl_dim_in, 1);
1037 space = isl_pw_aff_get_domain_space(init);
1038 ls = isl_local_space_from_space(space);
1039 aff = isl_aff_zero_on_domain(isl_local_space_copy(ls));
1040 aff = isl_aff_add_coefficient_val(aff, isl_dim_in, dim, inc);
1041 init = isl_pw_aff_add(init, isl_pw_aff_from_aff(aff));
1043 aff = isl_aff_var_on_domain(ls, isl_dim_set, dim - 1);
1044 set = isl_pw_aff_eq_set(isl_pw_aff_from_aff(aff), init);
1046 set = isl_set_lower_bound_si(set, isl_dim_set, dim, 0);
1047 set = isl_set_project_out(set, isl_dim_set, dim, 1);
1049 return set;
1052 /* Assuming "cond" represents a bound on a loop where the loop
1053 * iterator "iv" is incremented (or decremented) by one, check if wrapping
1054 * is possible.
1056 * Under the given assumptions, wrapping is only possible if "cond" allows
1057 * for the last value before wrapping, i.e., 2^width - 1 in case of an
1058 * increasing iterator and 0 in case of a decreasing iterator.
1060 static int can_wrap(__isl_keep isl_set *cond, __isl_keep pet_expr *iv,
1061 __isl_keep isl_val *inc)
1063 int cw;
1064 isl_ctx *ctx;
1065 isl_val *limit;
1066 isl_set *test;
1068 test = isl_set_copy(cond);
1070 ctx = isl_set_get_ctx(test);
1071 if (isl_val_is_neg(inc))
1072 limit = isl_val_zero(ctx);
1073 else {
1074 limit = isl_val_int_from_ui(ctx, pet_expr_get_type_size(iv));
1075 limit = isl_val_2exp(limit);
1076 limit = isl_val_sub_ui(limit, 1);
1079 test = isl_set_fix_val(cond, isl_dim_set, 0, limit);
1080 cw = !isl_set_is_empty(test);
1081 isl_set_free(test);
1083 return cw;
1086 /* Given a space
1088 * { [outer, v] },
1090 * construct the following affine expression on this space
1092 * { [outer, v] -> [outer, v mod 2^width] }
1094 * where width is the number of bits used to represent the values
1095 * of the unsigned variable "iv".
1097 static __isl_give isl_multi_aff *compute_wrapping(__isl_take isl_space *space,
1098 __isl_keep pet_expr *iv)
1100 int dim;
1101 isl_ctx *ctx;
1102 isl_val *mod;
1103 isl_aff *aff;
1104 isl_multi_aff *ma;
1106 dim = isl_space_dim(space, isl_dim_set);
1108 ctx = isl_space_get_ctx(space);
1109 mod = isl_val_int_from_ui(ctx, pet_expr_get_type_size(iv));
1110 mod = isl_val_2exp(mod);
1112 space = isl_space_map_from_set(space);
1113 ma = isl_multi_aff_identity(space);
1115 aff = isl_multi_aff_get_aff(ma, dim - 1);
1116 aff = isl_aff_mod_val(aff, mod);
1117 ma = isl_multi_aff_set_aff(ma, dim - 1, aff);
1119 return ma;
1122 /* Given two sets in the space
1124 * { [l,i] },
1126 * where l represents the outer loop iterators, compute the set
1127 * of values of l that ensure that "set1" is a subset of "set2".
1129 * set1 is a subset of set2 if
1131 * forall i: set1(l,i) => set2(l,i)
1133 * or
1135 * not exists i: set1(l,i) and not set2(l,i)
1137 * i.e.,
1139 * not exists i: (set1 \ set2)(l,i)
1141 static __isl_give isl_set *enforce_subset(__isl_take isl_set *set1,
1142 __isl_take isl_set *set2)
1144 int pos;
1146 pos = isl_set_dim(set1, isl_dim_set) - 1;
1147 set1 = isl_set_subtract(set1, set2);
1148 set1 = isl_set_eliminate(set1, isl_dim_set, pos, 1);
1149 return isl_set_complement(set1);
1152 /* Compute the set of outer iterator values for which "cond" holds
1153 * on the next iteration of the inner loop for each element of "dom".
1155 * We first construct mapping { [l,i] -> [l,i + inc] } (where l refers
1156 * to the outer loop iterators), plug that into "cond"
1157 * and then compute the set of outer iterators for which "dom" is a subset
1158 * of the result.
1160 static __isl_give isl_set *valid_on_next(__isl_take isl_set *cond,
1161 __isl_take isl_set *dom, __isl_take isl_val *inc)
1163 int pos;
1164 isl_space *space;
1165 isl_aff *aff;
1166 isl_multi_aff *ma;
1168 pos = isl_set_dim(dom, isl_dim_set) - 1;
1169 space = isl_set_get_space(dom);
1170 space = isl_space_map_from_set(space);
1171 ma = isl_multi_aff_identity(space);
1172 aff = isl_multi_aff_get_aff(ma, pos);
1173 aff = isl_aff_add_constant_val(aff, inc);
1174 ma = isl_multi_aff_set_aff(ma, pos, aff);
1175 cond = isl_set_preimage_multi_aff(cond, ma);
1177 return enforce_subset(dom, cond);
1180 /* Extract the for loop "tree" as a while loop within the context "pc_init".
1181 * In particular, "pc_init" represents the context of the loop,
1182 * whereas "pc" represents the context of the body of the loop and
1183 * has already had its domain extended with an infinite loop
1185 * { [t] : t >= 0 }
1187 * The for loop has the form
1189 * for (iv = init; cond; iv += inc)
1190 * body;
1192 * and is treated as
1194 * iv = init;
1195 * while (cond) {
1196 * body;
1197 * iv += inc;
1200 * except that the skips resulting from any continue statements
1201 * in body do not apply to the increment, but are replaced by the skips
1202 * resulting from break statements.
1204 * If the loop iterator is declared in the for loop, then it is killed before
1205 * and after the loop.
1207 static struct pet_scop *scop_from_non_affine_for(__isl_keep pet_tree *tree,
1208 __isl_keep pet_context *init_pc, __isl_take pet_context *pc,
1209 struct pet_state *state)
1211 int declared;
1212 isl_id *iv;
1213 pet_expr *expr_iv, *init, *inc;
1214 struct pet_scop *scop_init, *scop;
1215 int type_size;
1216 struct pet_array *array;
1217 struct pet_scop *scop_kill;
1219 iv = pet_expr_access_get_id(tree->u.l.iv);
1220 pc = pet_context_clear_value(pc, iv);
1222 declared = tree->u.l.declared;
1224 expr_iv = pet_expr_copy(tree->u.l.iv);
1225 type_size = pet_expr_get_type_size(expr_iv);
1226 init = pet_expr_copy(tree->u.l.init);
1227 init = pet_expr_new_binary(type_size, pet_op_assign, expr_iv, init);
1228 scop_init = scop_from_expr(init, state->n_stmt++,
1229 pet_tree_get_loc(tree), init_pc);
1231 expr_iv = pet_expr_copy(tree->u.l.iv);
1232 type_size = pet_expr_get_type_size(expr_iv);
1233 inc = pet_expr_copy(tree->u.l.inc);
1234 inc = pet_expr_new_binary(type_size, pet_op_add_assign, expr_iv, inc);
1236 scop = scop_from_non_affine_while(pet_expr_copy(tree->u.l.cond),
1237 pet_tree_get_loc(tree), tree->u.l.body, tree->label,
1238 inc, pet_context_copy(pc), state);
1240 scop = pet_scop_add_seq(state->ctx, scop_init, scop);
1242 pet_context_free(pc);
1244 if (!declared)
1245 return scop;
1247 array = extract_array(tree->u.l.iv, init_pc, state);
1248 if (array)
1249 array->declared = 1;
1250 scop_kill = kill(pet_tree_get_loc(tree), array, init_pc, state);
1251 scop = pet_scop_add_seq(state->ctx, scop_kill, scop);
1252 scop_kill = kill(pet_tree_get_loc(tree), array, init_pc, state);
1253 scop_kill = pet_scop_add_array(scop_kill, array);
1254 scop = pet_scop_add_seq(state->ctx, scop, scop_kill);
1256 return scop;
1259 /* Given an access expression "expr", is the variable accessed by
1260 * "expr" assigned anywhere inside "tree"?
1262 static int is_assigned(__isl_keep pet_expr *expr, __isl_keep pet_tree *tree)
1264 int assigned = 0;
1265 isl_id *id;
1267 id = pet_expr_access_get_id(expr);
1268 assigned = pet_tree_writes(tree, id);
1269 isl_id_free(id);
1271 return assigned;
1274 /* Are all nested access parameters in "pa" allowed given "tree".
1275 * In particular, is none of them written by anywhere inside "tree".
1277 * If "tree" has any continue or break nodes in the current loop level,
1278 * then no nested access parameters are allowed.
1279 * In particular, if there is any nested access in a guard
1280 * for a piece of code containing a "continue", then we want to introduce
1281 * a separate statement for evaluating this guard so that we can express
1282 * that the result is false for all previous iterations.
1284 static int is_nested_allowed(__isl_keep isl_pw_aff *pa,
1285 __isl_keep pet_tree *tree)
1287 int i, nparam;
1289 if (!tree)
1290 return -1;
1292 if (!pet_nested_any_in_pw_aff(pa))
1293 return 1;
1295 if (pet_tree_has_continue_or_break(tree))
1296 return 0;
1298 nparam = isl_pw_aff_dim(pa, isl_dim_param);
1299 for (i = 0; i < nparam; ++i) {
1300 isl_id *id = isl_pw_aff_get_dim_id(pa, isl_dim_param, i);
1301 pet_expr *expr;
1302 int allowed;
1304 if (!pet_nested_in_id(id)) {
1305 isl_id_free(id);
1306 continue;
1309 expr = pet_nested_extract_expr(id);
1310 allowed = pet_expr_get_type(expr) == pet_expr_access &&
1311 !is_assigned(expr, tree);
1313 pet_expr_free(expr);
1314 isl_id_free(id);
1316 if (!allowed)
1317 return 0;
1320 return 1;
1323 /* Internal data structure for collect_local.
1324 * "pc" and "state" are needed to extract pet_arrays for the local variables.
1325 * "local" collects the results.
1327 struct pet_tree_collect_local_data {
1328 pet_context *pc;
1329 struct pet_state *state;
1330 isl_union_set *local;
1333 /* Add the variable accessed by "var" to data->local.
1334 * We extract a representation of the variable from
1335 * the pet_array constructed using extract_array
1336 * to ensure consistency with the rest of the scop.
1338 static int add_local(struct pet_tree_collect_local_data *data,
1339 __isl_keep pet_expr *var)
1341 struct pet_array *array;
1342 isl_set *universe;
1344 array = extract_array(var, data->pc, data->state);
1345 if (!array)
1346 return -1;
1348 universe = isl_set_universe(isl_set_get_space(array->extent));
1349 data->local = isl_union_set_add_set(data->local, universe);
1350 pet_array_free(array);
1352 return 0;
1355 /* If the node "tree" declares a variable, then add it to
1356 * data->local.
1358 static int extract_local_var(__isl_keep pet_tree *tree, void *user)
1360 enum pet_tree_type type;
1361 struct pet_tree_collect_local_data *data = user;
1363 type = pet_tree_get_type(tree);
1364 if (type == pet_tree_decl || type == pet_tree_decl_init)
1365 return add_local(data, tree->u.d.var);
1367 return 0;
1370 /* If the node "tree" is a for loop that declares its induction variable,
1371 * then add it this induction variable to data->local.
1373 static int extract_local_iterator(__isl_keep pet_tree *tree, void *user)
1375 struct pet_tree_collect_local_data *data = user;
1377 if (pet_tree_get_type(tree) == pet_tree_for && tree->u.l.declared)
1378 return add_local(data, tree->u.l.iv);
1380 return 0;
1383 /* Collect and return all local variables of the for loop represented
1384 * by "tree", with "scop" the corresponding pet_scop.
1385 * "pc" and "state" are needed to extract pet_arrays for the local variables.
1387 * We collect not only the variables that are declared inside "tree",
1388 * but also the loop iterators that are declared anywhere inside
1389 * any possible macro statements in "scop".
1390 * The latter also appear as declared variable in the scop,
1391 * whereas other declared loop iterators only appear implicitly
1392 * in the iteration domains.
1394 static __isl_give isl_union_set *collect_local(struct pet_scop *scop,
1395 __isl_keep pet_tree *tree, __isl_keep pet_context *pc,
1396 struct pet_state *state)
1398 int i;
1399 isl_ctx *ctx;
1400 struct pet_tree_collect_local_data data = { pc, state };
1402 ctx = pet_tree_get_ctx(tree);
1403 data.local = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
1405 if (pet_tree_foreach_sub_tree(tree, &extract_local_var, &data) < 0)
1406 return isl_union_set_free(data.local);
1408 for (i = 0; i < scop->n_stmt; ++i) {
1409 pet_tree *body = scop->stmts[i]->body;
1410 if (pet_tree_foreach_sub_tree(body, &extract_local_iterator,
1411 &data) < 0)
1412 return isl_union_set_free(data.local);
1415 return data.local;
1418 /* Add an independence to "scop" if the for node "tree" was marked
1419 * independent.
1420 * "domain" is the set of loop iterators, with the current for loop
1421 * innermost. If "sign" is positive, then the inner iterator increases.
1422 * Otherwise it decreases.
1423 * "pc" and "state" are needed to extract pet_arrays for the local variables.
1425 * If the tree was marked, then collect all local variables and
1426 * add an independence.
1428 static struct pet_scop *set_independence(struct pet_scop *scop,
1429 __isl_keep pet_tree *tree, __isl_keep isl_set *domain, int sign,
1430 __isl_keep pet_context *pc, struct pet_state *state)
1432 isl_union_set *local;
1434 if (!tree->u.l.independent)
1435 return scop;
1437 local = collect_local(scop, tree, pc, state);
1438 scop = pet_scop_set_independent(scop, domain, local, sign);
1440 return scop;
1443 /* Construct a pet_scop for a for tree with static affine initialization
1444 * and constant increment within the context "pc".
1445 * The domain of "pc" has already been extended with an (at this point
1446 * unbounded) inner loop iterator corresponding to the current for loop.
1448 * The condition is allowed to contain nested accesses, provided
1449 * they are not being written to inside the body of the loop.
1450 * Otherwise, or if the condition is otherwise non-affine, the for loop is
1451 * essentially treated as a while loop, with iteration domain
1452 * { [l,i] : i >= init }, where l refers to the outer loop iterators.
1454 * We extract a pet_scop for the body after intersecting the domain of "pc"
1456 * { [l,i] : i >= init and condition' }
1458 * or
1460 * { [l,i] : i <= init and condition' }
1462 * Where condition' is equal to condition if the latter is
1463 * a simple upper [lower] bound and a condition that is extended
1464 * to apply to all previous iterations otherwise.
1465 * Afterwards, the schedule of the pet_scop is extended with
1467 * { [l,i] -> [i] }
1469 * or
1471 * { [l,i] -> [-i] }
1473 * If the condition is non-affine, then we drop the condition from the
1474 * iteration domain and instead create a separate statement
1475 * for evaluating the condition. The body is then filtered to depend
1476 * on the result of the condition evaluating to true on all iterations
1477 * up to the current iteration, while the evaluation the condition itself
1478 * is filtered to depend on the result of the condition evaluating to true
1479 * on all previous iterations.
1480 * The context of the scop representing the body is dropped
1481 * because we don't know how many times the body will be executed,
1482 * if at all.
1484 * If the stride of the loop is not 1, then "i >= init" is replaced by
1486 * (exists a: i = init + stride * a and a >= 0)
1488 * If the loop iterator i is unsigned, then wrapping may occur.
1489 * We therefore use a virtual iterator instead that does not wrap.
1490 * However, the condition in the code applies
1491 * to the wrapped value, so we need to change condition(l,i)
1492 * into condition([l,i % 2^width]). Similarly, we replace all accesses
1493 * to the original iterator by the wrapping of the virtual iterator.
1494 * Note that there may be no need to perform this final wrapping
1495 * if the loop condition (after wrapping) satisfies certain conditions.
1496 * However, the is_simple_bound condition is not enough since it doesn't
1497 * check if there even is an upper bound.
1499 * Wrapping on unsigned iterators can be avoided entirely if
1500 * loop condition is simple, the loop iterator is incremented
1501 * [decremented] by one and the last value before wrapping cannot
1502 * possibly satisfy the loop condition.
1504 * Valid outer iterators for a for loop are those for which the initial
1505 * value itself, the increment on each domain iteration and
1506 * the condition on both the initial value and
1507 * the result of incrementing the iterator for each iteration of the domain
1508 * can be evaluated.
1509 * If the loop condition is non-affine, then we only consider validity
1510 * of the initial value.
1512 * If the body contains any break, then we keep track of it in "skip"
1513 * (if the skip condition is affine) or it is handled in scop_add_break
1514 * (if the skip condition is not affine).
1515 * Note that the affine break condition needs to be considered with
1516 * respect to previous iterations in the virtual domain (if any).
1518 static struct pet_scop *scop_from_affine_for(__isl_keep pet_tree *tree,
1519 __isl_take isl_pw_aff *init_val, __isl_take isl_pw_aff *pa_inc,
1520 __isl_take isl_val *inc, __isl_take pet_context *pc,
1521 struct pet_state *state)
1523 isl_set *domain;
1524 isl_multi_aff *sched;
1525 isl_set *cond = NULL;
1526 isl_set *skip = NULL;
1527 isl_id *id_test = NULL, *id_break_test;
1528 struct pet_scop *scop, *scop_cond = NULL;
1529 int pos;
1530 int is_one;
1531 int is_unsigned;
1532 int is_simple;
1533 int is_virtual;
1534 int is_non_affine;
1535 int has_affine_break;
1536 int has_var_break;
1537 isl_map *rev_wrap = NULL;
1538 isl_map *init_val_map;
1539 isl_pw_aff *pa;
1540 isl_set *valid_init;
1541 isl_set *valid_cond;
1542 isl_set *valid_cond_init;
1543 isl_set *valid_cond_next;
1544 isl_set *valid_inc;
1545 pet_expr *cond_expr;
1546 pet_context *pc_nested;
1548 pos = pet_context_dim(pc) - 1;
1550 domain = pet_context_get_domain(pc);
1551 cond_expr = pet_expr_copy(tree->u.l.cond);
1552 cond_expr = pet_context_evaluate_expr(pc, cond_expr);
1553 pc_nested = pet_context_copy(pc);
1554 pc_nested = pet_context_set_allow_nested(pc_nested, 1);
1555 pa = pet_expr_extract_affine_condition(cond_expr, pc_nested);
1556 pet_context_free(pc_nested);
1557 pet_expr_free(cond_expr);
1559 valid_inc = isl_pw_aff_domain(pa_inc);
1561 is_unsigned = pet_expr_get_type_size(tree->u.l.iv) > 0;
1563 is_non_affine = isl_pw_aff_involves_nan(pa) ||
1564 !is_nested_allowed(pa, tree->u.l.body);
1565 if (is_non_affine)
1566 pa = isl_pw_aff_free(pa);
1568 valid_cond = isl_pw_aff_domain(isl_pw_aff_copy(pa));
1569 cond = isl_pw_aff_non_zero_set(pa);
1570 if (is_non_affine)
1571 cond = isl_set_universe(isl_set_get_space(domain));
1573 valid_cond = isl_set_coalesce(valid_cond);
1574 is_one = isl_val_is_one(inc) || isl_val_is_negone(inc);
1575 is_virtual = is_unsigned &&
1576 (!is_one || can_wrap(cond, tree->u.l.iv, inc));
1578 init_val_map = isl_map_from_pw_aff(isl_pw_aff_copy(init_val));
1579 init_val_map = isl_map_equate(init_val_map, isl_dim_in, pos,
1580 isl_dim_out, 0);
1581 valid_cond_init = enforce_subset(isl_map_domain(init_val_map),
1582 isl_set_copy(valid_cond));
1583 if (is_one && !is_virtual) {
1584 isl_set *cond;
1586 isl_pw_aff_free(init_val);
1587 pa = pet_expr_extract_comparison(
1588 isl_val_is_pos(inc) ? pet_op_ge : pet_op_le,
1589 tree->u.l.iv, tree->u.l.init, pc);
1590 valid_init = isl_pw_aff_domain(isl_pw_aff_copy(pa));
1591 valid_init = isl_set_eliminate(valid_init, isl_dim_set,
1592 isl_set_dim(domain, isl_dim_set) - 1, 1);
1593 cond = isl_pw_aff_non_zero_set(pa);
1594 domain = isl_set_intersect(domain, cond);
1595 } else {
1596 isl_set *strided;
1598 valid_init = isl_pw_aff_domain(isl_pw_aff_copy(init_val));
1599 strided = strided_domain(init_val, isl_val_copy(inc));
1600 domain = isl_set_intersect(domain, strided);
1603 if (is_virtual) {
1604 isl_multi_aff *wrap;
1605 wrap = compute_wrapping(isl_set_get_space(cond), tree->u.l.iv);
1606 pc = pet_context_preimage_domain(pc, wrap);
1607 rev_wrap = isl_map_from_multi_aff(wrap);
1608 rev_wrap = isl_map_reverse(rev_wrap);
1609 cond = isl_set_apply(cond, isl_map_copy(rev_wrap));
1610 valid_cond = isl_set_apply(valid_cond, isl_map_copy(rev_wrap));
1611 valid_inc = isl_set_apply(valid_inc, isl_map_copy(rev_wrap));
1613 is_simple = is_simple_bound(cond, inc);
1614 if (!is_simple) {
1615 cond = isl_set_gist(cond, isl_set_copy(domain));
1616 is_simple = is_simple_bound(cond, inc);
1618 if (!is_simple)
1619 cond = valid_for_each_iteration(cond,
1620 isl_set_copy(domain), isl_val_copy(inc));
1621 cond = isl_set_align_params(cond, isl_set_get_space(domain));
1622 domain = isl_set_intersect(domain, cond);
1623 sched = map_to_last(pc, state->n_loop++, tree->label);
1624 if (isl_val_is_neg(inc))
1625 sched = isl_multi_aff_neg(sched);
1627 valid_cond_next = valid_on_next(valid_cond, isl_set_copy(domain),
1628 isl_val_copy(inc));
1629 valid_inc = enforce_subset(isl_set_copy(domain), valid_inc);
1631 pc = pet_context_intersect_domain(pc, isl_set_copy(domain));
1633 if (is_non_affine) {
1634 isl_space *space;
1635 isl_multi_pw_aff *test_index;
1636 space = isl_set_get_space(domain);
1637 test_index = pet_create_test_index(space, state->n_test++);
1638 scop_cond = scop_from_non_affine_condition(
1639 pet_expr_copy(tree->u.l.cond), state->n_stmt++,
1640 isl_multi_pw_aff_copy(test_index),
1641 pet_tree_get_loc(tree), pc);
1642 id_test = isl_multi_pw_aff_get_tuple_id(test_index,
1643 isl_dim_out);
1644 scop_cond = pet_scop_add_boolean_array(scop_cond,
1645 isl_set_copy(domain), test_index,
1646 state->int_size);
1649 scop = scop_from_tree(tree->u.l.body, pc, state);
1650 has_affine_break = scop &&
1651 pet_scop_has_affine_skip(scop, pet_skip_later);
1652 if (has_affine_break)
1653 skip = pet_scop_get_affine_skip_domain(scop, pet_skip_later);
1654 has_var_break = scop && pet_scop_has_var_skip(scop, pet_skip_later);
1655 if (has_var_break)
1656 id_break_test = pet_scop_get_skip_id(scop, pet_skip_later);
1657 if (is_non_affine) {
1658 scop = pet_scop_reset_context(scop);
1660 scop = pet_scop_reset_skips(scop);
1661 scop = pet_scop_resolve_nested(scop);
1662 if (has_affine_break) {
1663 domain = apply_affine_break(domain, skip, isl_val_sgn(inc),
1664 is_virtual, rev_wrap);
1665 scop = pet_scop_intersect_domain_prefix(scop,
1666 isl_set_copy(domain));
1668 isl_map_free(rev_wrap);
1669 if (has_var_break)
1670 scop = scop_add_break(scop, id_break_test, isl_set_copy(domain),
1671 isl_val_copy(inc));
1672 if (is_non_affine)
1673 scop = scop_add_while(scop_cond, scop, id_test,
1674 isl_set_copy(domain),
1675 isl_val_copy(inc));
1676 else
1677 scop = set_independence(scop, tree, domain, isl_val_sgn(inc),
1678 pc, state);
1679 scop = pet_scop_embed(scop, domain, sched);
1680 if (is_non_affine) {
1681 isl_set_free(valid_inc);
1682 } else {
1683 valid_inc = isl_set_intersect(valid_inc, valid_cond_next);
1684 valid_inc = isl_set_intersect(valid_inc, valid_cond_init);
1685 valid_inc = isl_set_project_out(valid_inc, isl_dim_set, pos, 1);
1686 scop = pet_scop_restrict_context(scop, valid_inc);
1689 isl_val_free(inc);
1691 valid_init = isl_set_project_out(valid_init, isl_dim_set, pos, 1);
1692 scop = pet_scop_restrict_context(scop, valid_init);
1694 pet_context_free(pc);
1695 return scop;
1698 /* Construct a pet_scop for a for statement within the context of "pc".
1700 * We update the context to reflect the writes to the loop variable and
1701 * the writes inside the body.
1703 * Then we check if the initialization of the for loop
1704 * is a static affine value and the increment is a constant.
1705 * If so, we construct the pet_scop using scop_from_affine_for.
1706 * Otherwise, we treat the for loop as a while loop
1707 * in scop_from_non_affine_for.
1709 * Note that the initialization and the increment are extracted
1710 * in a context where the current loop iterator has been added
1711 * to the context. If these turn out not be affine, then we
1712 * have reconstruct the body context without an assignment
1713 * to this loop iterator, as this variable will then not be
1714 * treated as a dimension of the iteration domain, but as any
1715 * other variable.
1717 static struct pet_scop *scop_from_for(__isl_keep pet_tree *tree,
1718 __isl_keep pet_context *init_pc, struct pet_state *state)
1720 isl_id *iv;
1721 isl_val *inc;
1722 isl_pw_aff *pa_inc, *init_val;
1723 pet_context *pc, *pc_init_val;
1725 if (!tree)
1726 return NULL;
1728 iv = pet_expr_access_get_id(tree->u.l.iv);
1729 pc = pet_context_copy(init_pc);
1730 pc = pet_context_add_inner_iterator(pc, iv);
1731 pc = pet_context_clear_writes_in_tree(pc, tree->u.l.body);
1733 pc_init_val = pet_context_copy(pc);
1734 pc_init_val = pet_context_clear_value(pc_init_val, isl_id_copy(iv));
1735 init_val = pet_expr_extract_affine(tree->u.l.init, pc_init_val);
1736 pet_context_free(pc_init_val);
1737 pa_inc = pet_expr_extract_affine(tree->u.l.inc, pc);
1738 inc = pet_extract_cst(pa_inc);
1739 if (!pa_inc || !init_val || !inc)
1740 goto error;
1741 if (!isl_pw_aff_involves_nan(pa_inc) &&
1742 !isl_pw_aff_involves_nan(init_val) && !isl_val_is_nan(inc))
1743 return scop_from_affine_for(tree, init_val, pa_inc, inc,
1744 pc, state);
1746 isl_pw_aff_free(pa_inc);
1747 isl_pw_aff_free(init_val);
1748 isl_val_free(inc);
1749 pet_context_free(pc);
1751 pc = pet_context_copy(init_pc);
1752 pc = pet_context_add_infinite_loop(pc);
1753 pc = pet_context_clear_writes_in_tree(pc, tree->u.l.body);
1754 return scop_from_non_affine_for(tree, init_pc, pc, state);
1755 error:
1756 isl_pw_aff_free(pa_inc);
1757 isl_pw_aff_free(init_val);
1758 isl_val_free(inc);
1759 pet_context_free(pc);
1760 return NULL;
1763 /* Check whether "expr" is an affine constraint within the context "pc".
1765 static int is_affine_condition(__isl_keep pet_expr *expr,
1766 __isl_keep pet_context *pc)
1768 isl_pw_aff *pa;
1769 int is_affine;
1771 pa = pet_expr_extract_affine_condition(expr, pc);
1772 if (!pa)
1773 return -1;
1774 is_affine = !isl_pw_aff_involves_nan(pa);
1775 isl_pw_aff_free(pa);
1777 return is_affine;
1780 /* Check if the given if statement is a conditional assignement
1781 * with a non-affine condition.
1783 * In particular we check if "stmt" is of the form
1785 * if (condition)
1786 * a = f(...);
1787 * else
1788 * a = g(...);
1790 * where the condition is non-affine and a is some array or scalar access.
1792 static int is_conditional_assignment(__isl_keep pet_tree *tree,
1793 __isl_keep pet_context *pc)
1795 int equal;
1796 isl_ctx *ctx;
1797 pet_expr *expr1, *expr2;
1799 ctx = pet_tree_get_ctx(tree);
1800 if (!pet_options_get_detect_conditional_assignment(ctx))
1801 return 0;
1802 if (tree->type != pet_tree_if_else)
1803 return 0;
1804 if (tree->u.i.then_body->type != pet_tree_expr)
1805 return 0;
1806 if (tree->u.i.else_body->type != pet_tree_expr)
1807 return 0;
1808 expr1 = tree->u.i.then_body->u.e.expr;
1809 expr2 = tree->u.i.else_body->u.e.expr;
1810 if (pet_expr_get_type(expr1) != pet_expr_op)
1811 return 0;
1812 if (pet_expr_get_type(expr2) != pet_expr_op)
1813 return 0;
1814 if (pet_expr_op_get_type(expr1) != pet_op_assign)
1815 return 0;
1816 if (pet_expr_op_get_type(expr2) != pet_op_assign)
1817 return 0;
1818 expr1 = pet_expr_get_arg(expr1, 0);
1819 expr2 = pet_expr_get_arg(expr2, 0);
1820 equal = pet_expr_is_equal(expr1, expr2);
1821 pet_expr_free(expr1);
1822 pet_expr_free(expr2);
1823 if (equal < 0 || !equal)
1824 return 0;
1825 if (is_affine_condition(tree->u.i.cond, pc))
1826 return 0;
1828 return 1;
1831 /* Given that "tree" is of the form
1833 * if (condition)
1834 * a = f(...);
1835 * else
1836 * a = g(...);
1838 * where a is some array or scalar access, construct a pet_scop
1839 * corresponding to this conditional assignment within the context "pc".
1840 * "cond_pa" is an affine expression with nested accesses representing
1841 * the condition.
1843 * The constructed pet_scop then corresponds to the expression
1845 * a = condition ? f(...) : g(...)
1847 * All access relations in f(...) are intersected with condition
1848 * while all access relation in g(...) are intersected with the complement.
1850 static struct pet_scop *scop_from_conditional_assignment(
1851 __isl_keep pet_tree *tree, __isl_take isl_pw_aff *cond_pa,
1852 __isl_take pet_context *pc, struct pet_state *state)
1854 int type_size;
1855 isl_set *cond, *comp;
1856 isl_multi_pw_aff *index;
1857 pet_expr *expr1, *expr2;
1858 pet_expr *pe_cond, *pe_then, *pe_else, *pe, *pe_write;
1859 struct pet_scop *scop;
1861 cond = isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond_pa));
1862 comp = isl_pw_aff_zero_set(isl_pw_aff_copy(cond_pa));
1863 index = isl_multi_pw_aff_from_pw_aff(cond_pa);
1865 expr1 = tree->u.i.then_body->u.e.expr;
1866 expr2 = tree->u.i.else_body->u.e.expr;
1868 pe_cond = pet_expr_from_index(index);
1870 pe_then = pet_expr_get_arg(expr1, 1);
1871 pe_then = pet_context_evaluate_expr(pc, pe_then);
1872 pe_then = pet_expr_restrict(pe_then, cond);
1873 pe_else = pet_expr_get_arg(expr2, 1);
1874 pe_else = pet_context_evaluate_expr(pc, pe_else);
1875 pe_else = pet_expr_restrict(pe_else, comp);
1876 pe_write = pet_expr_get_arg(expr1, 0);
1877 pe_write = pet_context_evaluate_expr(pc, pe_write);
1879 pe = pet_expr_new_ternary(pe_cond, pe_then, pe_else);
1880 type_size = pet_expr_get_type_size(pe_write);
1881 pe = pet_expr_new_binary(type_size, pet_op_assign, pe_write, pe);
1883 scop = scop_from_evaluated_expr(pe, state->n_stmt++,
1884 pet_tree_get_loc(tree), pc);
1886 pet_context_free(pc);
1888 return scop;
1891 /* Construct a pet_scop for a non-affine if statement within the context "pc".
1893 * We create a separate statement that writes the result
1894 * of the non-affine condition to a virtual scalar.
1895 * A constraint requiring the value of this virtual scalar to be one
1896 * is added to the iteration domains of the then branch.
1897 * Similarly, a constraint requiring the value of this virtual scalar
1898 * to be zero is added to the iteration domains of the else branch, if any.
1899 * We combine the schedules as a sequence to ensure that the virtual scalar
1900 * is written before it is read.
1902 * If there are any breaks or continues in the then and/or else
1903 * branches, then we may have to compute a new skip condition.
1904 * This is handled using a pet_skip_info object.
1905 * On initialization, the object checks if skip conditions need
1906 * to be computed. If so, it does so in pet_skip_info_if_extract_index and
1907 * adds them in pet_skip_info_add.
1909 static struct pet_scop *scop_from_non_affine_if(__isl_keep pet_tree *tree,
1910 __isl_take pet_context *pc, struct pet_state *state)
1912 int has_else;
1913 isl_space *space;
1914 isl_set *domain;
1915 isl_multi_pw_aff *test_index;
1916 struct pet_skip_info skip;
1917 struct pet_scop *scop, *scop_then, *scop_else = NULL;
1919 has_else = tree->type == pet_tree_if_else;
1921 space = pet_context_get_space(pc);
1922 test_index = pet_create_test_index(space, state->n_test++);
1923 scop = scop_from_non_affine_condition(pet_expr_copy(tree->u.i.cond),
1924 state->n_stmt++, isl_multi_pw_aff_copy(test_index),
1925 pet_tree_get_loc(tree), pc);
1926 domain = pet_context_get_domain(pc);
1927 scop = pet_scop_add_boolean_array(scop, domain,
1928 isl_multi_pw_aff_copy(test_index), state->int_size);
1930 scop_then = scop_from_tree(tree->u.i.then_body, pc, state);
1931 if (has_else)
1932 scop_else = scop_from_tree(tree->u.i.else_body, pc, state);
1934 pet_skip_info_if_init(&skip, state->ctx, scop_then, scop_else,
1935 has_else, 0);
1936 pet_skip_info_if_extract_index(&skip, test_index, pc, state);
1938 scop_then = pet_scop_filter(scop_then,
1939 isl_multi_pw_aff_copy(test_index), 1);
1940 if (has_else) {
1941 scop_else = pet_scop_filter(scop_else, test_index, 0);
1942 scop_then = pet_scop_add_par(state->ctx, scop_then, scop_else);
1943 } else
1944 isl_multi_pw_aff_free(test_index);
1946 scop = pet_scop_add_seq(state->ctx, scop, scop_then);
1948 scop = pet_skip_info_add(&skip, scop);
1950 pet_context_free(pc);
1951 return scop;
1954 /* Construct a pet_scop for an affine if statement within the context "pc".
1956 * The condition is added to the iteration domains of the then branch,
1957 * while the opposite of the condition in added to the iteration domains
1958 * of the else branch, if any.
1960 * If there are any breaks or continues in the then and/or else
1961 * branches, then we may have to compute a new skip condition.
1962 * This is handled using a pet_skip_info_if object.
1963 * On initialization, the object checks if skip conditions need
1964 * to be computed. If so, it does so in pet_skip_info_if_extract_cond and
1965 * adds them in pet_skip_info_add.
1967 static struct pet_scop *scop_from_affine_if(__isl_keep pet_tree *tree,
1968 __isl_take isl_pw_aff *cond, __isl_take pet_context *pc,
1969 struct pet_state *state)
1971 int has_else;
1972 isl_ctx *ctx;
1973 isl_set *set, *complement;
1974 isl_set *valid;
1975 struct pet_skip_info skip;
1976 struct pet_scop *scop, *scop_then, *scop_else = NULL;
1977 pet_context *pc_body;
1979 ctx = pet_tree_get_ctx(tree);
1981 has_else = tree->type == pet_tree_if_else;
1983 valid = isl_pw_aff_domain(isl_pw_aff_copy(cond));
1984 set = isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond));
1986 pc_body = pet_context_copy(pc);
1987 pc_body = pet_context_intersect_domain(pc_body, isl_set_copy(set));
1988 scop_then = scop_from_tree(tree->u.i.then_body, pc_body, state);
1989 pet_context_free(pc_body);
1990 if (has_else) {
1991 pc_body = pet_context_copy(pc);
1992 complement = isl_set_copy(valid);
1993 complement = isl_set_subtract(valid, isl_set_copy(set));
1994 pc_body = pet_context_intersect_domain(pc_body,
1995 isl_set_copy(complement));
1996 scop_else = scop_from_tree(tree->u.i.else_body, pc_body, state);
1997 pet_context_free(pc_body);
2000 pet_skip_info_if_init(&skip, ctx, scop_then, scop_else, has_else, 1);
2001 pet_skip_info_if_extract_cond(&skip, cond, pc, state);
2002 isl_pw_aff_free(cond);
2004 scop = pet_scop_restrict(scop_then, set);
2006 if (has_else) {
2007 scop_else = pet_scop_restrict(scop_else, complement);
2008 scop = pet_scop_add_par(ctx, scop, scop_else);
2010 scop = pet_scop_resolve_nested(scop);
2011 scop = pet_scop_restrict_context(scop, valid);
2013 scop = pet_skip_info_add(&skip, scop);
2015 pet_context_free(pc);
2016 return scop;
2019 /* Construct a pet_scop for an if statement within the context "pc".
2021 * If the condition fits the pattern of a conditional assignment,
2022 * then it is handled by scop_from_conditional_assignment.
2023 * Note that the condition is only considered for a conditional assignment
2024 * if it is not static-affine. However, it should still convert
2025 * to an affine expression when nesting is allowed.
2027 * Otherwise, we check if the condition is affine.
2028 * If so, we construct the scop in scop_from_affine_if.
2029 * Otherwise, we construct the scop in scop_from_non_affine_if.
2031 * We allow the condition to be dynamic, i.e., to refer to
2032 * scalars or array elements that may be written to outside
2033 * of the given if statement. These nested accesses are then represented
2034 * as output dimensions in the wrapping iteration domain.
2035 * If it is also written _inside_ the then or else branch, then
2036 * we treat the condition as non-affine.
2037 * As explained in extract_non_affine_if, this will introduce
2038 * an extra statement.
2039 * For aesthetic reasons, we want this statement to have a statement
2040 * number that is lower than those of the then and else branches.
2041 * In order to evaluate if we will need such a statement, however, we
2042 * first construct scops for the then and else branches.
2043 * We therefore reserve a statement number if we might have to
2044 * introduce such an extra statement.
2046 static struct pet_scop *scop_from_if(__isl_keep pet_tree *tree,
2047 __isl_keep pet_context *pc, struct pet_state *state)
2049 int has_else;
2050 isl_pw_aff *cond;
2051 pet_expr *cond_expr;
2052 pet_context *pc_nested;
2054 if (!tree)
2055 return NULL;
2057 has_else = tree->type == pet_tree_if_else;
2059 pc = pet_context_copy(pc);
2060 pc = pet_context_clear_writes_in_tree(pc, tree->u.i.then_body);
2061 if (has_else)
2062 pc = pet_context_clear_writes_in_tree(pc, tree->u.i.else_body);
2064 cond_expr = pet_expr_copy(tree->u.i.cond);
2065 cond_expr = pet_context_evaluate_expr(pc, cond_expr);
2066 pc_nested = pet_context_copy(pc);
2067 pc_nested = pet_context_set_allow_nested(pc_nested, 1);
2068 cond = pet_expr_extract_affine_condition(cond_expr, pc_nested);
2069 pet_context_free(pc_nested);
2070 pet_expr_free(cond_expr);
2072 if (!cond) {
2073 pet_context_free(pc);
2074 return NULL;
2077 if (isl_pw_aff_involves_nan(cond)) {
2078 isl_pw_aff_free(cond);
2079 return scop_from_non_affine_if(tree, pc, state);
2082 if (is_conditional_assignment(tree, pc))
2083 return scop_from_conditional_assignment(tree, cond, pc, state);
2085 if ((!is_nested_allowed(cond, tree->u.i.then_body) ||
2086 (has_else && !is_nested_allowed(cond, tree->u.i.else_body)))) {
2087 isl_pw_aff_free(cond);
2088 return scop_from_non_affine_if(tree, pc, state);
2091 return scop_from_affine_if(tree, cond, pc, state);
2094 /* Return a one-dimensional multi piecewise affine expression that is equal
2095 * to the constant 1 and is defined over the given domain.
2097 static __isl_give isl_multi_pw_aff *one_mpa(__isl_take isl_space *space)
2099 isl_local_space *ls;
2100 isl_aff *aff;
2102 ls = isl_local_space_from_space(space);
2103 aff = isl_aff_zero_on_domain(ls);
2104 aff = isl_aff_set_constant_si(aff, 1);
2106 return isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
2109 /* Construct a pet_scop for a continue statement with the given domain space.
2111 * We simply create an empty scop with a universal pet_skip_now
2112 * skip condition. This skip condition will then be taken into
2113 * account by the enclosing loop construct, possibly after
2114 * being incorporated into outer skip conditions.
2116 static struct pet_scop *scop_from_continue(__isl_keep pet_tree *tree,
2117 __isl_take isl_space *space)
2119 struct pet_scop *scop;
2121 scop = pet_scop_empty(isl_space_copy(space));
2123 scop = pet_scop_set_skip(scop, pet_skip_now, one_mpa(space));
2125 return scop;
2128 /* Construct a pet_scop for a break statement with the given domain space.
2130 * We simply create an empty scop with both a universal pet_skip_now
2131 * skip condition and a universal pet_skip_later skip condition.
2132 * These skip conditions will then be taken into
2133 * account by the enclosing loop construct, possibly after
2134 * being incorporated into outer skip conditions.
2136 static struct pet_scop *scop_from_break(__isl_keep pet_tree *tree,
2137 __isl_take isl_space *space)
2139 struct pet_scop *scop;
2140 isl_multi_pw_aff *skip;
2142 scop = pet_scop_empty(isl_space_copy(space));
2144 skip = one_mpa(space);
2145 scop = pet_scop_set_skip(scop, pet_skip_now,
2146 isl_multi_pw_aff_copy(skip));
2147 scop = pet_scop_set_skip(scop, pet_skip_later, skip);
2149 return scop;
2152 /* Extract a clone of the kill statement "stmt".
2153 * The domain of the clone is given by "domain".
2155 static struct pet_scop *extract_kill(__isl_keep isl_set *domain,
2156 struct pet_stmt *stmt, struct pet_state *state)
2158 pet_expr *kill;
2159 isl_space *space;
2160 isl_multi_pw_aff *mpa;
2161 pet_tree *tree;
2163 if (!domain || !stmt)
2164 return NULL;
2166 kill = pet_tree_expr_get_expr(stmt->body);
2167 space = pet_stmt_get_space(stmt);
2168 space = isl_space_map_from_set(space);
2169 mpa = isl_multi_pw_aff_identity(space);
2170 mpa = isl_multi_pw_aff_reset_tuple_id(mpa, isl_dim_in);
2171 kill = pet_expr_update_domain(kill, mpa);
2172 tree = pet_tree_new_expr(kill);
2173 tree = pet_tree_set_loc(tree, pet_loc_copy(stmt->loc));
2174 stmt = pet_stmt_from_pet_tree(isl_set_copy(domain),
2175 state->n_stmt++, tree);
2176 return pet_scop_from_pet_stmt(isl_set_get_space(domain), stmt);
2179 /* Extract a clone of the kill statements in "scop".
2180 * The domain of each clone is given by "domain".
2181 * "scop" is expected to have been created from a DeclStmt
2182 * and should have (one of) the kill(s) as its first statement.
2183 * If "scop" was created from a declaration group, then there
2184 * may be multiple kill statements inside.
2186 static struct pet_scop *extract_kills(__isl_keep isl_set *domain,
2187 struct pet_scop *scop, struct pet_state *state)
2189 isl_ctx *ctx;
2190 struct pet_stmt *stmt;
2191 struct pet_scop *kill;
2192 int i;
2194 if (!domain || !scop)
2195 return NULL;
2196 ctx = isl_set_get_ctx(domain);
2197 if (scop->n_stmt < 1)
2198 isl_die(ctx, isl_error_internal,
2199 "expecting at least one statement", return NULL);
2200 stmt = scop->stmts[0];
2201 if (!pet_stmt_is_kill(stmt))
2202 isl_die(ctx, isl_error_internal,
2203 "expecting kill statement", return NULL);
2205 kill = extract_kill(domain, stmt, state);
2207 for (i = 1; i < scop->n_stmt; ++i) {
2208 struct pet_scop *kill_i;
2210 stmt = scop->stmts[i];
2211 if (!pet_stmt_is_kill(stmt))
2212 continue;
2214 kill_i = extract_kill(domain, stmt, state);
2215 kill = pet_scop_add_par(ctx, kill, kill_i);
2218 return kill;
2221 /* Has "tree" been created from a DeclStmt?
2222 * That is, is it either a declaration or a group of declarations?
2224 static int tree_is_decl(__isl_keep pet_tree *tree)
2226 int is_decl;
2227 int i;
2229 if (!tree)
2230 return -1;
2231 is_decl = pet_tree_is_decl(tree);
2232 if (is_decl < 0 || is_decl)
2233 return is_decl;
2235 if (tree->type != pet_tree_block)
2236 return 0;
2237 if (pet_tree_block_get_block(tree))
2238 return 0;
2240 for (i = 0; i < tree->u.b.n; ++i) {
2241 is_decl = tree_is_decl(tree->u.b.child[i]);
2242 if (is_decl < 0 || !is_decl)
2243 return is_decl;
2246 return 1;
2249 /* Does "tree" represent an assignment to a variable?
2251 * The assignment may be one of
2252 * - a declaration with initialization
2253 * - an expression with a top-level assignment operator
2255 static int is_assignment(__isl_keep pet_tree *tree)
2257 if (!tree)
2258 return 0;
2259 if (tree->type == pet_tree_decl_init)
2260 return 1;
2261 return pet_tree_is_assign(tree);
2264 /* Update "pc" by taking into account the assignment performed by "tree",
2265 * where "tree" satisfies is_assignment.
2267 * In particular, if the lhs of the assignment is a scalar variable and
2268 * if the rhs is an affine expression, then keep track of this value in "pc"
2269 * so that we can plug it in when we later come across the same variable.
2271 * Any previously assigned value to the variable has already been removed
2272 * by scop_handle_writes.
2274 static __isl_give pet_context *handle_assignment(__isl_take pet_context *pc,
2275 __isl_keep pet_tree *tree)
2277 pet_expr *var, *val;
2278 isl_id *id;
2279 isl_pw_aff *pa;
2281 if (pet_tree_get_type(tree) == pet_tree_decl_init) {
2282 var = pet_tree_decl_get_var(tree);
2283 val = pet_tree_decl_get_init(tree);
2284 } else {
2285 pet_expr *expr;
2286 expr = pet_tree_expr_get_expr(tree);
2287 var = pet_expr_get_arg(expr, 0);
2288 val = pet_expr_get_arg(expr, 1);
2289 pet_expr_free(expr);
2292 if (!pet_expr_is_scalar_access(var)) {
2293 pet_expr_free(var);
2294 pet_expr_free(val);
2295 return pc;
2298 pa = pet_expr_extract_affine(val, pc);
2299 if (!pa)
2300 pc = pet_context_free(pc);
2302 if (!isl_pw_aff_involves_nan(pa)) {
2303 id = pet_expr_access_get_id(var);
2304 pc = pet_context_set_value(pc, id, pa);
2305 } else {
2306 isl_pw_aff_free(pa);
2308 pet_expr_free(var);
2309 pet_expr_free(val);
2311 return pc;
2314 /* Mark all arrays in "scop" as being exposed.
2316 static struct pet_scop *mark_exposed(struct pet_scop *scop)
2318 int i;
2320 if (!scop)
2321 return NULL;
2322 for (i = 0; i < scop->n_array; ++i)
2323 scop->arrays[i]->exposed = 1;
2324 return scop;
2327 /* Try and construct a pet_scop corresponding to (part of)
2328 * a sequence of statements within the context "pc".
2330 * After extracting a statement, we update "pc"
2331 * based on the top-level assignments in the statement
2332 * so that we can exploit them in subsequent statements in the same block.
2334 * If there are any breaks or continues in the individual statements,
2335 * then we may have to compute a new skip condition.
2336 * This is handled using a pet_skip_info object.
2337 * On initialization, the object checks if skip conditions need
2338 * to be computed. If so, it does so in pet_skip_info_seq_extract and
2339 * adds them in pet_skip_info_add.
2341 * If "block" is set, then we need to insert kill statements at
2342 * the end of the block for any array that has been declared by
2343 * one of the statements in the sequence. Each of these declarations
2344 * results in the construction of a kill statement at the place
2345 * of the declaration, so we simply collect duplicates of
2346 * those kill statements and append these duplicates to the constructed scop.
2348 * If "block" is not set, then any array declared by one of the statements
2349 * in the sequence is marked as being exposed.
2351 * If autodetect is set, then we allow the extraction of only a subrange
2352 * of the sequence of statements. However, if there is at least one statement
2353 * for which we could not construct a scop and the final range contains
2354 * either no statements or at least one kill, then we discard the entire
2355 * range.
2357 static struct pet_scop *scop_from_block(__isl_keep pet_tree *tree,
2358 __isl_keep pet_context *pc, struct pet_state *state)
2360 int i;
2361 isl_ctx *ctx;
2362 isl_space *space;
2363 isl_set *domain;
2364 struct pet_scop *scop, *kills;
2366 ctx = pet_tree_get_ctx(tree);
2368 space = pet_context_get_space(pc);
2369 domain = pet_context_get_domain(pc);
2370 pc = pet_context_copy(pc);
2371 scop = pet_scop_empty(isl_space_copy(space));
2372 kills = pet_scop_empty(space);
2373 for (i = 0; i < tree->u.b.n; ++i) {
2374 struct pet_scop *scop_i;
2376 if (pet_scop_has_affine_skip(scop, pet_skip_now))
2377 pc = apply_affine_continue(pc, scop);
2378 scop_i = scop_from_tree(tree->u.b.child[i], pc, state);
2379 pc = scop_handle_writes(scop_i, pc);
2380 if (is_assignment(tree->u.b.child[i]))
2381 pc = handle_assignment(pc, tree->u.b.child[i]);
2382 struct pet_skip_info skip;
2383 pet_skip_info_seq_init(&skip, ctx, scop, scop_i);
2384 pet_skip_info_seq_extract(&skip, pc, state);
2385 if (scop_i && tree_is_decl(tree->u.b.child[i])) {
2386 if (tree->u.b.block) {
2387 struct pet_scop *kill;
2388 kill = extract_kills(domain, scop_i, state);
2389 kills = pet_scop_add_par(ctx, kills, kill);
2390 } else
2391 scop_i = mark_exposed(scop_i);
2393 scop = pet_scop_add_seq(ctx, scop, scop_i);
2395 scop = pet_skip_info_add(&skip, scop);
2397 if (!scop)
2398 break;
2400 isl_set_free(domain);
2402 scop = pet_scop_add_seq(ctx, scop, kills);
2404 pet_context_free(pc);
2406 return scop;
2409 /* Internal data structure for extract_declared_arrays.
2411 * "pc" and "state" are used to create pet_array objects and kill statements.
2412 * "any" is initialized to 0 by the caller and set to 1 as soon as we have
2413 * found any declared array.
2414 * "scop" has been initialized by the caller and is used to attach
2415 * the created pet_array objects.
2416 * "kill_before" and "kill_after" are created and updated by
2417 * extract_declared_arrays to collect the kills of the arrays.
2419 struct pet_tree_extract_declared_arrays_data {
2420 pet_context *pc;
2421 struct pet_state *state;
2423 isl_ctx *ctx;
2425 int any;
2426 struct pet_scop *scop;
2427 struct pet_scop *kill_before;
2428 struct pet_scop *kill_after;
2431 /* Check if the node "node" declares any array or scalar.
2432 * If so, create the corresponding pet_array and attach it to data->scop.
2433 * Additionally, create two kill statements for the array and add them
2434 * to data->kill_before and data->kill_after.
2436 static int extract_declared_arrays(__isl_keep pet_tree *node, void *user)
2438 enum pet_tree_type type;
2439 struct pet_tree_extract_declared_arrays_data *data = user;
2440 struct pet_array *array;
2441 struct pet_scop *scop_kill;
2442 pet_expr *var;
2444 type = pet_tree_get_type(node);
2445 if (type == pet_tree_decl || type == pet_tree_decl_init)
2446 var = node->u.d.var;
2447 else if (type == pet_tree_for && node->u.l.declared)
2448 var = node->u.l.iv;
2449 else
2450 return 0;
2452 array = extract_array(var, data->pc, data->state);
2453 if (array)
2454 array->declared = 1;
2455 data->scop = pet_scop_add_array(data->scop, array);
2457 scop_kill = kill(pet_tree_get_loc(node), array, data->pc, data->state);
2458 if (!data->any)
2459 data->kill_before = scop_kill;
2460 else
2461 data->kill_before = pet_scop_add_par(data->ctx,
2462 data->kill_before, scop_kill);
2464 scop_kill = kill(pet_tree_get_loc(node), array, data->pc, data->state);
2465 if (!data->any)
2466 data->kill_after = scop_kill;
2467 else
2468 data->kill_after = pet_scop_add_par(data->ctx,
2469 data->kill_after, scop_kill);
2471 data->any = 1;
2473 return 0;
2476 /* Convert a pet_tree that consists of more than a single leaf
2477 * to a pet_scop with a single statement encapsulating the entire pet_tree.
2478 * Do so within the context of "pc".
2480 * After constructing the core scop, we also look for any arrays (or scalars)
2481 * that are declared inside "tree". Each of those arrays is marked as
2482 * having been declared and kill statements for these arrays
2483 * are introduced before and after the core scop.
2484 * Note that the input tree is not a leaf so that the declaration
2485 * cannot occur at the outer level.
2487 static struct pet_scop *scop_from_tree_macro(__isl_take pet_tree *tree,
2488 __isl_keep pet_context *pc, struct pet_state *state)
2490 struct pet_tree_extract_declared_arrays_data data = { pc, state };
2492 data.scop = scop_from_unevaluated_tree(pet_tree_copy(tree),
2493 state->n_stmt++, pc);
2495 data.any = 0;
2496 data.ctx = pet_context_get_ctx(pc);
2497 if (pet_tree_foreach_sub_tree(tree, &extract_declared_arrays,
2498 &data) < 0)
2499 data.scop = pet_scop_free(data.scop);
2500 pet_tree_free(tree);
2502 if (!data.any)
2503 return data.scop;
2505 data.scop = pet_scop_add_seq(data.ctx, data.kill_before, data.scop);
2506 data.scop = pet_scop_add_seq(data.ctx, data.scop, data.kill_after);
2508 return data.scop;
2511 /* Construct a pet_scop that corresponds to the pet_tree "tree"
2512 * within the context "pc" by calling the appropriate function
2513 * based on the type of "tree".
2515 * If the initially constructed pet_scop turns out to involve
2516 * dynamic control and if the user has requested an encapsulation
2517 * of all dynamic control, then this pet_scop is discarded and
2518 * a new pet_scop is created with a single statement representing
2519 * the entire "tree".
2520 * However, if the scop contains any active continue or break,
2521 * then we need to include the loop containing the continue or break
2522 * in the encapsulation. We therefore postpone the encapsulation
2523 * until we have constructed a pet_scop for this enclosing loop.
2525 static struct pet_scop *scop_from_tree(__isl_keep pet_tree *tree,
2526 __isl_keep pet_context *pc, struct pet_state *state)
2528 isl_ctx *ctx;
2529 struct pet_scop *scop = NULL;
2531 if (!tree)
2532 return NULL;
2534 ctx = pet_tree_get_ctx(tree);
2535 switch (tree->type) {
2536 case pet_tree_error:
2537 return NULL;
2538 case pet_tree_block:
2539 return scop_from_block(tree, pc, state);
2540 case pet_tree_break:
2541 return scop_from_break(tree, pet_context_get_space(pc));
2542 case pet_tree_continue:
2543 return scop_from_continue(tree, pet_context_get_space(pc));
2544 case pet_tree_decl:
2545 case pet_tree_decl_init:
2546 return scop_from_decl(tree, pc, state);
2547 case pet_tree_expr:
2548 return scop_from_tree_expr(tree, pc, state);
2549 case pet_tree_if:
2550 case pet_tree_if_else:
2551 scop = scop_from_if(tree, pc, state);
2552 break;
2553 case pet_tree_for:
2554 scop = scop_from_for(tree, pc, state);
2555 break;
2556 case pet_tree_while:
2557 scop = scop_from_while(tree, pc, state);
2558 break;
2559 case pet_tree_infinite_loop:
2560 scop = scop_from_infinite_for(tree, pc, state);
2561 break;
2564 if (!scop)
2565 return NULL;
2567 if (!pet_options_get_encapsulate_dynamic_control(ctx) ||
2568 !pet_scop_has_data_dependent_conditions(scop) ||
2569 pet_scop_has_var_skip(scop, pet_skip_now))
2570 return scop;
2572 pet_scop_free(scop);
2573 return scop_from_tree_macro(pet_tree_copy(tree), pc, state);
2576 /* If "tree" has a label that is of the form S_<nr>, then make
2577 * sure that state->n_stmt is greater than nr to ensure that
2578 * we will not generate S_<nr> ourselves.
2580 static int set_first_stmt(__isl_keep pet_tree *tree, void *user)
2582 struct pet_state *state = user;
2583 const char *name;
2584 int nr;
2586 if (!tree)
2587 return -1;
2588 if (!tree->label)
2589 return 0;
2590 name = isl_id_get_name(tree->label);
2591 if (strncmp(name, "S_", 2) != 0)
2592 return 0;
2593 nr = atoi(name + 2);
2594 if (nr >= state->n_stmt)
2595 state->n_stmt = nr + 1;
2597 return 0;
2600 /* Construct a pet_scop that corresponds to the pet_tree "tree".
2601 * "int_size" is the number of bytes need to represent an integer.
2602 * "extract_array" is a callback that we can use to create a pet_array
2603 * that corresponds to the variable accessed by an expression.
2605 * Initialize the global state, construct a context and then
2606 * construct the pet_scop by recursively visiting the tree.
2608 * state.n_stmt is initialized to point beyond any explicit S_<nr> label.
2610 struct pet_scop *pet_scop_from_pet_tree(__isl_take pet_tree *tree, int int_size,
2611 struct pet_array *(*extract_array)(__isl_keep pet_expr *access,
2612 __isl_keep pet_context *pc, void *user), void *user,
2613 __isl_keep pet_context *pc)
2615 struct pet_scop *scop;
2616 struct pet_state state = { 0 };
2618 if (!tree)
2619 return NULL;
2621 state.ctx = pet_tree_get_ctx(tree);
2622 state.int_size = int_size;
2623 state.extract_array = extract_array;
2624 state.user = user;
2625 if (pet_tree_foreach_sub_tree(tree, &set_first_stmt, &state) < 0)
2626 tree = pet_tree_free(tree);
2628 scop = scop_from_tree(tree, pc, &state);
2629 scop = pet_scop_set_loc(scop, pet_tree_get_loc(tree));
2631 pet_tree_free(tree);
2633 if (scop)
2634 scop->context = isl_set_params(scop->context);
2636 return scop;