2 * Copyright 2012 Ecole Normale Superieure
4 * Use of this software is governed by the MIT license
6 * Written by Sven Verdoolaege,
7 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
10 #include <isl_ast_private.h>
11 #include <isl_ast_build_expr.h>
12 #include <isl_ast_build_private.h>
13 #include <isl_ast_graft_private.h>
15 static __isl_give isl_ast_graft
*isl_ast_graft_copy(
16 __isl_keep isl_ast_graft
*graft
);
19 #define BASE ast_graft
21 #include <isl_list_templ.c>
24 #define BASE ast_graft
25 #include <print_templ.c>
27 isl_ctx
*isl_ast_graft_get_ctx(__isl_keep isl_ast_graft
*graft
)
31 return isl_basic_set_get_ctx(graft
->enforced
);
34 __isl_give isl_ast_node
*isl_ast_graft_get_node(
35 __isl_keep isl_ast_graft
*graft
)
37 return graft
? isl_ast_node_copy(graft
->node
) : NULL
;
40 /* Create a graft for "node" with no guards and no enforced conditions.
42 __isl_give isl_ast_graft
*isl_ast_graft_alloc(
43 __isl_take isl_ast_node
*node
, __isl_keep isl_ast_build
*build
)
52 ctx
= isl_ast_node_get_ctx(node
);
53 graft
= isl_calloc_type(ctx
, isl_ast_graft
);
57 space
= isl_ast_build_get_space(build
, 1);
61 graft
->guard
= isl_set_universe(isl_space_copy(space
));
62 graft
->enforced
= isl_basic_set_universe(space
);
64 if (!graft
->guard
|| !graft
->enforced
)
65 return isl_ast_graft_free(graft
);
69 isl_ast_node_free(node
);
73 /* Create a graft with no guards and no enforced conditions
74 * encapsulating a call to the domain element specified by "executed".
75 * "executed" is assumed to be single-valued.
77 __isl_give isl_ast_graft
*isl_ast_graft_alloc_domain(
78 __isl_take isl_map
*executed
, __isl_keep isl_ast_build
*build
)
82 node
= isl_ast_build_call_from_executed(build
, executed
);
84 return isl_ast_graft_alloc(node
, build
);
87 static __isl_give isl_ast_graft
*isl_ast_graft_copy(
88 __isl_keep isl_ast_graft
*graft
)
97 /* Do all the grafts in "list" have the same guard and is this guard
98 * independent of the current depth?
100 static int equal_independent_guards(__isl_keep isl_ast_graft_list
*list
,
101 __isl_keep isl_ast_build
*build
)
105 isl_ast_graft
*graft_0
;
109 graft_0
= isl_ast_graft_list_get_ast_graft(list
, 0);
113 depth
= isl_ast_build_get_depth(build
);
114 skip
= isl_set_involves_dims(graft_0
->guard
, isl_dim_set
, depth
, 1);
115 if (skip
< 0 || skip
) {
116 isl_ast_graft_free(graft_0
);
117 return skip
< 0 ? -1 : 0;
120 n
= isl_ast_graft_list_n_ast_graft(list
);
121 for (i
= 1; i
< n
; ++i
) {
122 isl_ast_graft
*graft
;
123 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
127 equal
= isl_set_is_equal(graft_0
->guard
, graft
->guard
);
128 isl_ast_graft_free(graft
);
129 if (equal
< 0 || !equal
)
133 isl_ast_graft_free(graft_0
);
138 /* Hoist "guard" out of the current level (given by "build").
140 * In particular, eliminate the dimension corresponding to the current depth.
142 static __isl_give isl_set
*hoist_guard(__isl_take isl_set
*guard
,
143 __isl_keep isl_ast_build
*build
)
147 depth
= isl_ast_build_get_depth(build
);
148 if (depth
< isl_set_dim(guard
, isl_dim_set
)) {
149 guard
= isl_set_remove_divs_involving_dims(guard
,
150 isl_dim_set
, depth
, 1);
151 guard
= isl_set_eliminate(guard
, isl_dim_set
, depth
, 1);
152 guard
= isl_set_compute_divs(guard
);
158 /* Extract a common guard from the grafts in "list" that can be hoisted
159 * out of the current level. If no such guard can be found, then return
162 * If all the grafts in the list have the same guard and if this guard
163 * is independent of the current level, then it can be hoisted out.
164 * If there is only one graft in the list and if its guard
165 * depends on the current level, then we eliminate this level and
168 * Otherwise, we return the unshifted simple hull of the guards.
169 * In order to be able to hoist as many constraints as possible,
170 * but at the same time avoid hoisting constraints that did not
171 * appear in the guards in the first place, we intersect the guards
172 * with all the information that is available (i.e., the domain
173 * from the build and the enforced constraints of the graft) and
174 * compute the unshifted hull of the result using only constraints
175 * from the original guards.
176 * In particular, intersecting the guards with other known information
177 * allows us to hoist guards that are only explicit is some of
178 * the grafts and implicit in the others.
180 * The special case for equal guards is needed in case those guards
181 * are non-convex. Taking the simple hull would remove information
182 * and would not allow for these guards to be hoisted completely.
184 __isl_give isl_set
*isl_ast_graft_list_extract_hoistable_guard(
185 __isl_keep isl_ast_graft_list
*list
, __isl_keep isl_ast_build
*build
)
191 isl_set_list
*set_list
;
197 n
= isl_ast_graft_list_n_ast_graft(list
);
199 return isl_set_universe(isl_ast_build_get_space(build
, 1));
201 equal
= equal_independent_guards(list
, build
);
205 if (equal
|| n
== 1) {
206 isl_ast_graft
*graft_0
;
208 graft_0
= isl_ast_graft_list_get_ast_graft(list
, 0);
211 guard
= isl_set_copy(graft_0
->guard
);
213 guard
= hoist_guard(guard
, build
);
214 isl_ast_graft_free(graft_0
);
218 ctx
= isl_ast_build_get_ctx(build
);
219 set_list
= isl_set_list_alloc(ctx
, n
);
220 guard
= isl_set_empty(isl_ast_build_get_space(build
, 1));
221 for (i
= 0; i
< n
; ++i
) {
222 isl_ast_graft
*graft
;
223 isl_basic_set
*enforced
;
226 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
227 enforced
= isl_ast_graft_get_enforced(graft
);
228 guard_i
= isl_set_copy(graft
->guard
);
229 isl_ast_graft_free(graft
);
230 set_list
= isl_set_list_add(set_list
, isl_set_copy(guard_i
));
231 guard_i
= isl_set_intersect(guard_i
,
232 isl_set_from_basic_set(enforced
));
233 guard_i
= isl_set_intersect(guard_i
,
234 isl_ast_build_get_domain(build
));
235 guard
= isl_set_union(guard
, guard_i
);
237 hull
= isl_set_unshifted_simple_hull_from_set_list(guard
, set_list
);
238 guard
= isl_set_from_basic_set(hull
);
239 return hoist_guard(guard
, build
);
242 /* Internal data structure used inside insert_if.
244 * list is the list of guarded nodes created by each call to insert_if.
245 * node is the original node that is guarded by insert_if.
246 * build is the build in which the AST is constructed.
248 struct isl_insert_if_data
{
249 isl_ast_node_list
*list
;
251 isl_ast_build
*build
;
254 static int insert_if(__isl_take isl_basic_set
*bset
, void *user
);
256 /* Insert an if node around "node" testing the condition encoded
259 * If the user does not want any disjunctions in the if conditions
260 * and if "guard" does involve a disjunction, then we make the different
261 * disjuncts disjoint and insert an if node corresponding to each disjunct
262 * around a copy of "node". The result is then a block node containing
263 * this sequence of guarded copies of "node".
265 static __isl_give isl_ast_node
*ast_node_insert_if(
266 __isl_take isl_ast_node
*node
, __isl_take isl_set
*guard
,
267 __isl_keep isl_ast_build
*build
)
269 struct isl_insert_if_data data
;
272 ctx
= isl_ast_build_get_ctx(build
);
273 if (isl_options_get_ast_build_allow_or(ctx
) ||
274 isl_set_n_basic_set(guard
) <= 1) {
275 isl_ast_node
*if_node
;
278 expr
= isl_ast_build_expr_from_set(build
, guard
);
280 if_node
= isl_ast_node_alloc_if(expr
);
281 return isl_ast_node_if_set_then(if_node
, node
);
284 guard
= isl_set_make_disjoint(guard
);
286 data
.list
= isl_ast_node_list_alloc(ctx
, 0);
289 if (isl_set_foreach_basic_set(guard
, &insert_if
, &data
) < 0)
290 data
.list
= isl_ast_node_list_free(data
.list
);
293 isl_ast_node_free(data
.node
);
294 return isl_ast_node_alloc_block(data
.list
);
297 /* Insert an if node around a copy of "data->node" testing the condition
298 * encoded in guard "bset" and add the result to data->list.
300 static int insert_if(__isl_take isl_basic_set
*bset
, void *user
)
302 struct isl_insert_if_data
*data
= user
;
306 set
= isl_set_from_basic_set(bset
);
307 node
= isl_ast_node_copy(data
->node
);
308 node
= ast_node_insert_if(node
, set
, data
->build
);
309 data
->list
= isl_ast_node_list_add(data
->list
, node
);
314 /* Insert an if node around graft->node testing the condition encoded
315 * in guard "guard", assuming guard involves any conditions.
317 static __isl_give isl_ast_graft
*insert_if_node(
318 __isl_take isl_ast_graft
*graft
, __isl_take isl_set
*guard
,
319 __isl_keep isl_ast_build
*build
)
326 univ
= isl_set_plain_is_universe(guard
);
334 build
= isl_ast_build_copy(build
);
335 build
= isl_ast_build_set_enforced(build
,
336 isl_ast_graft_get_enforced(graft
));
337 graft
->node
= ast_node_insert_if(graft
->node
, guard
, build
);
338 isl_ast_build_free(build
);
341 return isl_ast_graft_free(graft
);
346 return isl_ast_graft_free(graft
);
349 /* Insert an if node around graft->node testing the condition encoded
350 * in graft->guard, assuming graft->guard involves any conditions.
352 static __isl_give isl_ast_graft
*insert_pending_guard_node(
353 __isl_take isl_ast_graft
*graft
, __isl_keep isl_ast_build
*build
)
358 return insert_if_node(graft
, isl_set_copy(graft
->guard
), build
);
361 /* Replace graft->enforced by "enforced".
363 __isl_give isl_ast_graft
*isl_ast_graft_set_enforced(
364 __isl_take isl_ast_graft
*graft
, __isl_take isl_basic_set
*enforced
)
366 if (!graft
|| !enforced
)
369 isl_basic_set_free(graft
->enforced
);
370 graft
->enforced
= enforced
;
374 isl_basic_set_free(enforced
);
375 return isl_ast_graft_free(graft
);
378 /* Update "enforced" such that it only involves constraints that are
379 * also enforced by "graft".
381 static __isl_give isl_basic_set
*update_enforced(
382 __isl_take isl_basic_set
*enforced
, __isl_keep isl_ast_graft
*graft
,
385 isl_basic_set
*enforced_g
;
387 enforced_g
= isl_ast_graft_get_enforced(graft
);
388 if (depth
< isl_basic_set_dim(enforced_g
, isl_dim_set
))
389 enforced_g
= isl_basic_set_eliminate(enforced_g
,
390 isl_dim_set
, depth
, 1);
391 enforced_g
= isl_basic_set_remove_unknown_divs(enforced_g
);
392 enforced_g
= isl_basic_set_align_params(enforced_g
,
393 isl_basic_set_get_space(enforced
));
394 enforced
= isl_basic_set_align_params(enforced
,
395 isl_basic_set_get_space(enforced_g
));
396 enforced
= isl_set_simple_hull(isl_basic_set_union(enforced
,
402 /* Extend the node at *body with node.
404 * If body points to the else branch, then *body may still be NULL.
405 * If so, we simply attach node to this else branch.
406 * Otherwise, we attach a list containing the statements already
407 * attached at *body followed by node.
409 static void extend_body(__isl_keep isl_ast_node
**body
,
410 __isl_take isl_ast_node
*node
)
412 isl_ast_node_list
*list
;
419 if ((*body
)->type
== isl_ast_node_block
) {
420 list
= isl_ast_node_block_get_children(*body
);
421 isl_ast_node_free(*body
);
423 list
= isl_ast_node_list_from_ast_node(*body
);
424 list
= isl_ast_node_list_add(list
, node
);
425 *body
= isl_ast_node_alloc_block(list
);
428 /* Merge "graft" into the last graft of "list".
429 * body points to the then or else branch of an if node in that last graft.
431 * We attach graft->node to this branch and update the enforced
432 * set of the last graft of "list" to take into account the enforced
435 static __isl_give isl_ast_graft_list
*graft_extend_body(
436 __isl_take isl_ast_graft_list
*list
,
437 __isl_keep isl_ast_node
**body
, __isl_take isl_ast_graft
*graft
,
438 __isl_keep isl_ast_build
*build
)
444 isl_basic_set
*enforced
;
448 extend_body(body
, isl_ast_node_copy(graft
->node
));
452 n
= isl_ast_graft_list_n_ast_graft(list
);
453 last
= isl_ast_graft_list_get_ast_graft(list
, n
- 1);
455 depth
= isl_ast_build_get_depth(build
);
456 space
= isl_ast_build_get_space(build
, 1);
457 enforced
= isl_basic_set_empty(space
);
458 enforced
= update_enforced(enforced
, last
, depth
);
459 enforced
= update_enforced(enforced
, graft
, depth
);
460 last
= isl_ast_graft_set_enforced(last
, enforced
);
462 list
= isl_ast_graft_list_set_ast_graft(list
, n
- 1, last
);
463 isl_ast_graft_free(graft
);
466 isl_ast_graft_free(graft
);
467 return isl_ast_graft_list_free(list
);
470 /* Merge "graft" into the last graft of "list", attaching graft->node
471 * to the then branch of "last_if".
473 static __isl_give isl_ast_graft_list
*extend_then(
474 __isl_take isl_ast_graft_list
*list
,
475 __isl_keep isl_ast_node
*last_if
, __isl_take isl_ast_graft
*graft
,
476 __isl_keep isl_ast_build
*build
)
478 return graft_extend_body(list
, &last_if
->u
.i
.then
, graft
, build
);
481 /* Merge "graft" into the last graft of "list", attaching graft->node
482 * to the else branch of "last_if".
484 static __isl_give isl_ast_graft_list
*extend_else(
485 __isl_take isl_ast_graft_list
*list
,
486 __isl_keep isl_ast_node
*last_if
, __isl_take isl_ast_graft
*graft
,
487 __isl_keep isl_ast_build
*build
)
489 return graft_extend_body(list
, &last_if
->u
.i
.else_node
, graft
, build
);
492 /* This data structure keeps track of an if node.
494 * "node" is the actual if-node
495 * "guard" is the original, non-simplified guard of the node
496 * "complement" is the complement of "guard" in the context of outer if nodes
504 /* Given a list of "n" if nodes, clear those starting at "first"
505 * and return "first" (i.e., the updated size of the array).
507 static int clear_if_nodes(struct isl_if_node
*if_node
, int first
, int n
)
511 for (i
= first
; i
< n
; ++i
) {
512 isl_set_free(if_node
[i
].guard
);
513 isl_set_free(if_node
[i
].complement
);
519 /* For each graft in "list",
520 * insert an if node around graft->node testing the condition encoded
521 * in graft->guard, assuming graft->guard involves any conditions.
523 * We keep track of a list of generated if nodes that can be extended
524 * without changing the order of the elements in "list".
525 * If the guard of a graft is a subset of either the guard or its complement
526 * of one of those if nodes, then the node
527 * of the new graft is inserted into the then or else branch of the last graft
528 * and the current graft is discarded.
529 * The guard of the node is then simplified based on the conditions
530 * enforced at that then or else branch.
531 * Otherwise, the current graft is appended to the list.
533 * We only construct else branches if allowed by the user.
535 static __isl_give isl_ast_graft_list
*insert_pending_guard_nodes(
536 __isl_take isl_ast_graft_list
*list
,
537 __isl_keep isl_ast_build
*build
)
542 isl_ast_graft_list
*res
;
543 struct isl_if_node
*if_node
= NULL
;
546 return isl_ast_graft_list_free(list
);
548 ctx
= isl_ast_build_get_ctx(build
);
549 n
= isl_ast_graft_list_n_ast_graft(list
);
551 allow_else
= isl_options_get_ast_build_allow_else(ctx
);
555 if_node
= isl_alloc_array(ctx
, struct isl_if_node
, n
- 1);
557 return isl_ast_graft_list_free(list
);
560 res
= isl_ast_graft_list_alloc(ctx
, n
);
562 for (i
= 0; i
< n
; ++i
) {
564 isl_ast_graft
*graft
;
565 int subset
, found_then
, found_else
;
568 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
572 found_then
= found_else
= -1;
575 test
= isl_set_copy(graft
->guard
);
576 test
= isl_set_intersect(test
,
577 isl_set_copy(build
->domain
));
578 for (j
= n_if
- 1; j
>= 0; --j
) {
579 subset
= isl_set_is_subset(test
,
581 if (subset
< 0 || subset
) {
587 subset
= isl_set_is_subset(test
,
588 if_node
[j
].complement
);
589 if (subset
< 0 || subset
) {
594 n_if
= clear_if_nodes(if_node
, j
+ 1, n_if
);
598 graft
= isl_ast_graft_free(graft
);
602 guard
= isl_set_copy(graft
->guard
);
604 graft
->guard
= isl_set_gist(graft
->guard
,
605 isl_set_copy(if_node
[found_then
].guard
));
606 else if (found_else
>= 0)
607 graft
->guard
= isl_set_gist(graft
->guard
,
608 isl_set_copy(if_node
[found_else
].complement
));
612 graft
= isl_ast_graft_free(graft
);
613 graft
= insert_pending_guard_node(graft
, build
);
614 if (graft
&& graft
->node
!= node
&& i
!= n
- 1) {
616 if_node
[n_if
].node
= graft
->node
;
617 if_node
[n_if
].guard
= guard
;
619 set
= if_node
[found_then
].guard
;
620 else if (found_else
>= 0)
621 set
= if_node
[found_else
].complement
;
624 set
= isl_set_copy(set
);
625 set
= isl_set_subtract(set
, isl_set_copy(guard
));
626 if_node
[n_if
].complement
= set
;
634 res
= extend_then(res
, if_node
[found_then
].node
,
636 else if (found_else
>= 0)
637 res
= extend_else(res
, if_node
[found_else
].node
,
640 res
= isl_ast_graft_list_add(res
, graft
);
643 res
= isl_ast_graft_list_free(res
);
645 isl_ast_graft_list_free(list
);
646 clear_if_nodes(if_node
, 0, n_if
);
651 /* Collect the nodes contained in the grafts in "list" in a node list.
653 static __isl_give isl_ast_node_list
*extract_node_list(
654 __isl_keep isl_ast_graft_list
*list
)
658 isl_ast_node_list
*node_list
;
662 ctx
= isl_ast_graft_list_get_ctx(list
);
663 n
= isl_ast_graft_list_n_ast_graft(list
);
664 node_list
= isl_ast_node_list_alloc(ctx
, n
);
665 for (i
= 0; i
< n
; ++i
) {
667 isl_ast_graft
*graft
;
669 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
670 node
= isl_ast_graft_get_node(graft
);
671 node_list
= isl_ast_node_list_add(node_list
, node
);
672 isl_ast_graft_free(graft
);
678 /* Look for shared enforced constraints by all the elements in "list"
679 * on outer loops (with respect to the current depth) and return the result.
681 * We assume that the number of children is at least one.
683 __isl_give isl_basic_set
*isl_ast_graft_list_extract_shared_enforced(
684 __isl_keep isl_ast_graft_list
*list
,
685 __isl_keep isl_ast_build
*build
)
690 isl_basic_set
*enforced
;
695 n
= isl_ast_graft_list_n_ast_graft(list
);
697 isl_die(isl_ast_graft_list_get_ctx(list
), isl_error_invalid
,
698 "for node should have at least one child",
701 space
= isl_ast_build_get_space(build
, 1);
702 enforced
= isl_basic_set_empty(space
);
704 depth
= isl_ast_build_get_depth(build
);
705 for (i
= 0; i
< n
; ++i
) {
706 isl_ast_graft
*graft
;
708 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
709 enforced
= update_enforced(enforced
, graft
, depth
);
710 isl_ast_graft_free(graft
);
716 /* Record "guard" in "graft" so that it will be enforced somewhere
717 * up the tree. If the graft already has a guard, then it may be partially
718 * redundant in combination with the new guard and in the context
719 * of build->domain. We therefore (re)compute the gist of the intersection
720 * and coalesce the result.
722 static __isl_give isl_ast_graft
*store_guard(__isl_take isl_ast_graft
*graft
,
723 __isl_take isl_set
*guard
, __isl_keep isl_ast_build
*build
)
730 is_universe
= isl_set_plain_is_universe(guard
);
738 graft
->guard
= isl_set_intersect(graft
->guard
, guard
);
739 graft
->guard
= isl_ast_build_compute_gist(build
, graft
->guard
);
740 graft
->guard
= isl_set_coalesce(graft
->guard
);
742 return isl_ast_graft_free(graft
);
747 return isl_ast_graft_free(graft
);
750 /* For each graft in "list", replace its guard with the gist with
751 * respect to "context".
753 static __isl_give isl_ast_graft_list
*gist_guards(
754 __isl_take isl_ast_graft_list
*list
, __isl_keep isl_set
*context
)
761 n
= isl_ast_graft_list_n_ast_graft(list
);
762 for (i
= 0; i
< n
; ++i
) {
763 isl_ast_graft
*graft
;
765 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
768 graft
->guard
= isl_set_gist(graft
->guard
,
769 isl_set_copy(context
));
771 graft
= isl_ast_graft_free(graft
);
772 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
775 return isl_ast_graft_list_free(list
);
780 /* Allocate a graft in "build" based on the list of grafts in "sub_build".
781 * "guard" and "enforced" are the guard and enforced constraints
782 * of the allocated graft. The guard is used to simplify the guards
783 * of the elements in "list".
785 * The node is initialized to either a block containing the nodes of "children"
786 * or, if there is only a single child, the node of that child.
787 * If the current level requires a for node, it should be inserted by
788 * a subsequent call to isl_ast_graft_insert_for.
790 __isl_give isl_ast_graft
*isl_ast_graft_alloc_from_children(
791 __isl_take isl_ast_graft_list
*list
, __isl_take isl_set
*guard
,
792 __isl_take isl_basic_set
*enforced
, __isl_keep isl_ast_build
*build
,
793 __isl_keep isl_ast_build
*sub_build
)
796 isl_ast_node_list
*node_list
;
797 isl_ast_graft
*graft
;
799 list
= gist_guards(list
, guard
);
800 list
= insert_pending_guard_nodes(list
, sub_build
);
802 node_list
= extract_node_list(list
);
803 node
= isl_ast_node_from_ast_node_list(node_list
);
804 isl_ast_graft_list_free(list
);
806 graft
= isl_ast_graft_alloc(node
, build
);
807 graft
= store_guard(graft
, guard
, build
);
808 graft
= isl_ast_graft_enforce(graft
, enforced
);
813 /* Combine the grafts in the list into a single graft.
815 * If "up" is set then the resulting graft will be used at an outer level.
816 * In this case, "build" refers to the outer level, while "sub_build"
817 * refers to the inner level. If "up" is not set, then the same build
818 * should be passed to both arguments.
820 * The guard is initialized to the shared guard of the list elements (if any),
821 * provided it does not depend on the current dimension.
822 * The guards in the elements are then simplified with respect to the
823 * hoisted guard and materialized as if nodes around the contained AST nodes
824 * in the context of "sub_build".
826 * The enforced set is initialized to the simple hull of the enforced sets
827 * of the elements, provided the ast_build_exploit_nested_bounds option is set
828 * or the new graft will be used at the same level.
830 * The node is initialized to either a block containing the nodes of "list"
831 * or, if there is only a single element, the node of that element.
833 static __isl_give isl_ast_graft
*ast_graft_list_fuse(
834 __isl_take isl_ast_graft_list
*list
, __isl_keep isl_ast_build
*build
,
835 __isl_keep isl_ast_build
*sub_build
, int up
)
838 isl_ast_graft
*graft
;
839 isl_basic_set
*enforced
;
845 ctx
= isl_ast_build_get_ctx(build
);
846 if (!up
|| isl_options_get_ast_build_exploit_nested_bounds(ctx
))
847 enforced
= isl_ast_graft_list_extract_shared_enforced(list
,
850 isl_space
*space
= isl_ast_build_get_space(build
, 1);
851 enforced
= isl_basic_set_universe(space
);
854 guard
= isl_ast_graft_list_extract_hoistable_guard(list
, build
);
855 graft
= isl_ast_graft_alloc_from_children(list
, guard
, enforced
,
861 /* Combine the grafts in the list into a single graft.
862 * Return a list containing this single graft.
863 * If the original list is empty, then return an empty list.
865 __isl_give isl_ast_graft_list
*isl_ast_graft_list_fuse(
866 __isl_take isl_ast_graft_list
*list
,
867 __isl_keep isl_ast_build
*build
)
869 isl_ast_graft
*graft
;
873 if (isl_ast_graft_list_n_ast_graft(list
) <= 1)
875 graft
= ast_graft_list_fuse(list
, build
, build
, 0);
876 return isl_ast_graft_list_from_ast_graft(graft
);
879 /* Combine the two grafts into a single graft.
880 * Return a list containing this single graft.
882 static __isl_give isl_ast_graft
*isl_ast_graft_fuse(
883 __isl_take isl_ast_graft
*graft1
, __isl_take isl_ast_graft
*graft2
,
884 __isl_keep isl_ast_build
*build
)
887 isl_ast_graft_list
*list
;
889 ctx
= isl_ast_build_get_ctx(build
);
891 list
= isl_ast_graft_list_alloc(ctx
, 2);
892 list
= isl_ast_graft_list_add(list
, graft1
);
893 list
= isl_ast_graft_list_add(list
, graft2
);
895 return ast_graft_list_fuse(list
, build
, build
, 0);
898 /* Allocate a graft for the current level based on the list of grafts
899 * of the inner level.
900 * "build" represents the context of the current level.
901 * "sub_build" represents the context of the inner level.
903 * The node is initialized to either a block containing the nodes of "children"
904 * or, if there is only a single child, the node of that child.
905 * If the current level requires a for node, it should be inserted by
906 * a subsequent call to isl_ast_graft_insert_for.
908 __isl_give isl_ast_graft
*isl_ast_graft_alloc_level(
909 __isl_take isl_ast_graft_list
*children
,
910 __isl_keep isl_ast_build
*build
, __isl_keep isl_ast_build
*sub_build
)
912 return ast_graft_list_fuse(children
, build
, sub_build
, 1);
915 /* Insert a for node enclosing the current graft->node.
917 __isl_give isl_ast_graft
*isl_ast_graft_insert_for(
918 __isl_take isl_ast_graft
*graft
, __isl_take isl_ast_node
*node
)
923 graft
->node
= isl_ast_node_for_set_body(node
, graft
->node
);
925 return isl_ast_graft_free(graft
);
929 isl_ast_node_free(node
);
930 isl_ast_graft_free(graft
);
934 /* Represent the graft list as an AST node.
935 * This operation drops the information about guards in the grafts, so
936 * if there are any pending guards, then they are materialized as if nodes.
938 __isl_give isl_ast_node
*isl_ast_node_from_graft_list(
939 __isl_take isl_ast_graft_list
*list
,
940 __isl_keep isl_ast_build
*build
)
942 isl_ast_node_list
*node_list
;
944 list
= insert_pending_guard_nodes(list
, build
);
945 node_list
= extract_node_list(list
);
946 isl_ast_graft_list_free(list
);
948 return isl_ast_node_from_ast_node_list(node_list
);
951 void *isl_ast_graft_free(__isl_take isl_ast_graft
*graft
)
956 if (--graft
->ref
> 0)
959 isl_ast_node_free(graft
->node
);
960 isl_set_free(graft
->guard
);
961 isl_basic_set_free(graft
->enforced
);
967 /* Record that the grafted tree enforces
968 * "enforced" by intersecting graft->enforced with "enforced".
970 __isl_give isl_ast_graft
*isl_ast_graft_enforce(
971 __isl_take isl_ast_graft
*graft
, __isl_take isl_basic_set
*enforced
)
973 if (!graft
|| !enforced
)
976 enforced
= isl_basic_set_align_params(enforced
,
977 isl_basic_set_get_space(graft
->enforced
));
978 graft
->enforced
= isl_basic_set_align_params(graft
->enforced
,
979 isl_basic_set_get_space(enforced
));
980 graft
->enforced
= isl_basic_set_intersect(graft
->enforced
, enforced
);
981 if (!graft
->enforced
)
982 return isl_ast_graft_free(graft
);
986 isl_basic_set_free(enforced
);
987 return isl_ast_graft_free(graft
);
990 __isl_give isl_basic_set
*isl_ast_graft_get_enforced(
991 __isl_keep isl_ast_graft
*graft
)
993 return graft
? isl_basic_set_copy(graft
->enforced
) : NULL
;
996 __isl_give isl_set
*isl_ast_graft_get_guard(__isl_keep isl_ast_graft
*graft
)
998 return graft
? isl_set_copy(graft
->guard
) : NULL
;
1001 /* Record that "guard" needs to be inserted in "graft".
1003 * We first simplify the guard in the context of the enforced set and
1004 * then we store the guard in case we may be able
1005 * to hoist it to higher levels and/or combine it with those of other grafts.
1007 __isl_give isl_ast_graft
*isl_ast_graft_add_guard(
1008 __isl_take isl_ast_graft
*graft
,
1009 __isl_take isl_set
*guard
, __isl_keep isl_ast_build
*build
)
1011 isl_basic_set
*enforced
;
1013 if (!graft
|| !build
)
1016 enforced
= isl_basic_set_copy(graft
->enforced
);
1017 guard
= isl_set_gist(guard
, isl_set_from_basic_set(enforced
));
1019 graft
= store_guard(graft
, guard
, build
);
1023 isl_set_free(guard
);
1024 isl_ast_graft_free(graft
);
1028 /* Reformulate the "graft", which was generated in the context
1029 * of an inner code generation, in terms of the outer code generation
1032 * If "product" is set, then the domain of the inner code generation build is
1036 * with O the domain of the outer code generation build.
1037 * We essentially need to project out S.
1039 * If "product" is not set, then we need to project the domains onto
1040 * their parameter spaces.
1042 __isl_give isl_ast_graft
*isl_ast_graft_unembed(__isl_take isl_ast_graft
*graft
,
1045 isl_basic_set
*enforced
;
1051 enforced
= graft
->enforced
;
1052 enforced
= isl_basic_map_domain(isl_basic_set_unwrap(enforced
));
1053 graft
->enforced
= enforced
;
1054 graft
->guard
= isl_map_domain(isl_set_unwrap(graft
->guard
));
1056 graft
->enforced
= isl_basic_set_params(graft
->enforced
);
1057 graft
->guard
= isl_set_params(graft
->guard
);
1059 graft
->guard
= isl_set_compute_divs(graft
->guard
);
1061 if (!graft
->enforced
|| !graft
->guard
)
1062 return isl_ast_graft_free(graft
);
1067 /* Reformulate the grafts in "list", which were generated in the context
1068 * of an inner code generation, in terms of the outer code generation
1071 __isl_give isl_ast_graft_list
*isl_ast_graft_list_unembed(
1072 __isl_take isl_ast_graft_list
*list
, int product
)
1076 n
= isl_ast_graft_list_n_ast_graft(list
);
1077 for (i
= 0; i
< n
; ++i
) {
1078 isl_ast_graft
*graft
;
1080 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
1081 graft
= isl_ast_graft_unembed(graft
, product
);
1082 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
1088 /* Compute the preimage of "graft" under the function represented by "ma".
1089 * In other words, plug in "ma" in "enforced" and "guard" fields of "graft".
1091 __isl_give isl_ast_graft
*isl_ast_graft_preimage_multi_aff(
1092 __isl_take isl_ast_graft
*graft
, __isl_take isl_multi_aff
*ma
)
1094 isl_basic_set
*enforced
;
1099 enforced
= graft
->enforced
;
1100 graft
->enforced
= isl_basic_set_preimage_multi_aff(enforced
,
1101 isl_multi_aff_copy(ma
));
1102 graft
->guard
= isl_set_preimage_multi_aff(graft
->guard
, ma
);
1104 if (!graft
->enforced
|| !graft
->guard
)
1105 return isl_ast_graft_free(graft
);
1110 /* Compute the preimage of all the grafts in "list" under
1111 * the function represented by "ma".
1113 __isl_give isl_ast_graft_list
*isl_ast_graft_list_preimage_multi_aff(
1114 __isl_take isl_ast_graft_list
*list
, __isl_take isl_multi_aff
*ma
)
1118 n
= isl_ast_graft_list_n_ast_graft(list
);
1119 for (i
= 0; i
< n
; ++i
) {
1120 isl_ast_graft
*graft
;
1122 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
1123 graft
= isl_ast_graft_preimage_multi_aff(graft
,
1124 isl_multi_aff_copy(ma
));
1125 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
1128 isl_multi_aff_free(ma
);
1132 /* Compare two grafts based on their guards.
1134 static int cmp_graft(__isl_keep isl_ast_graft
*a
, __isl_keep isl_ast_graft
*b
,
1137 return isl_set_plain_cmp(a
->guard
, b
->guard
);
1140 /* Order the elements in "list" based on their guards.
1142 __isl_give isl_ast_graft_list
*isl_ast_graft_list_sort_guard(
1143 __isl_take isl_ast_graft_list
*list
)
1145 return isl_ast_graft_list_sort(list
, &cmp_graft
, NULL
);
1148 /* Merge the given two lists into a single list of grafts,
1149 * merging grafts with the same guard into a single graft.
1151 * "list2" has been sorted using isl_ast_graft_list_sort.
1152 * "list1" may be the result of a previous call to isl_ast_graft_list_merge
1153 * and may therefore not be completely sorted.
1155 * The elements in "list2" need to be executed after those in "list1",
1156 * but if the guard of a graft in "list2" is disjoint from the guards
1157 * of some final elements in "list1", then it can be moved up to before
1158 * those final elements.
1160 * In particular, we look at each element g of "list2" in turn
1161 * and move it up beyond elements of "list1" that would be sorted
1162 * after g as long as each of these elements has a guard that is disjoint
1165 * We do not allow the second or any later element of "list2" to be moved
1166 * before a previous elements of "list2" even if the reason that
1167 * that element didn't move up further was that its guard was not disjoint
1168 * from that of the previous element in "list1".
1170 __isl_give isl_ast_graft_list
*isl_ast_graft_list_merge(
1171 __isl_take isl_ast_graft_list
*list1
,
1172 __isl_take isl_ast_graft_list
*list2
,
1173 __isl_keep isl_ast_build
*build
)
1177 if (!list1
|| !list2
|| !build
)
1179 if (list2
->n
== 0) {
1180 isl_ast_graft_list_free(list2
);
1183 if (list1
->n
== 0) {
1184 isl_ast_graft_list_free(list1
);
1189 for (i
= 0; i
< list2
->n
; ++i
) {
1190 isl_ast_graft
*graft
;
1191 graft
= isl_ast_graft_list_get_ast_graft(list2
, i
);
1195 for (j
= list1
->n
; j
>= 0; --j
) {
1197 isl_ast_graft
*graft_j
;
1202 cmp
= isl_set_plain_cmp(list1
->p
[j
- 1]->guard
,
1205 disjoint
= isl_set_is_disjoint(graft
->guard
,
1206 list1
->p
[j
- 1]->guard
);
1208 list1
= isl_ast_graft_list_free(list1
);
1217 list1
= isl_ast_graft_list_insert(list1
, j
,
1224 graft_j
= isl_ast_graft_list_get_ast_graft(list1
, j
);
1225 graft_j
= isl_ast_graft_fuse(graft_j
, graft
, build
);
1226 list1
= isl_ast_graft_list_set_ast_graft(list1
, j
,
1232 isl_die(isl_ast_build_get_ctx(build
),
1234 "element failed to get inserted", break);
1241 list1
= isl_ast_graft_list_free(list1
);
1242 isl_ast_graft_list_free(list2
);
1246 isl_ast_graft_list_free(list1
);
1247 isl_ast_graft_list_free(list2
);
1251 __isl_give isl_printer
*isl_printer_print_ast_graft(__isl_take isl_printer
*p
,
1252 __isl_keep isl_ast_graft
*graft
)
1257 return isl_printer_free(p
);
1259 p
= isl_printer_print_str(p
, "(");
1260 p
= isl_printer_print_str(p
, "guard: ");
1261 p
= isl_printer_print_set(p
, graft
->guard
);
1262 p
= isl_printer_print_str(p
, ", ");
1263 p
= isl_printer_print_str(p
, "enforced: ");
1264 p
= isl_printer_print_basic_set(p
, graft
->enforced
);
1265 p
= isl_printer_print_str(p
, ", ");
1266 p
= isl_printer_print_str(p
, "node: ");
1267 p
= isl_printer_print_ast_node(p
, graft
->node
);
1268 p
= isl_printer_print_str(p
, ")");