2 * Copyright 2012 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
9 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
10 * B.P. 105 - 78153 Le Chesnay, France
13 #include <isl_ast_private.h>
14 #include <isl_ast_build_expr.h>
15 #include <isl_ast_build_private.h>
16 #include <isl_ast_graft_private.h>
18 static __isl_give isl_ast_graft
*isl_ast_graft_copy(
19 __isl_keep isl_ast_graft
*graft
);
22 #define BASE ast_graft
24 #include <isl_list_templ.c>
27 #define BASE ast_graft
28 #include <print_templ.c>
30 isl_ctx
*isl_ast_graft_get_ctx(__isl_keep isl_ast_graft
*graft
)
34 return isl_basic_set_get_ctx(graft
->enforced
);
37 __isl_give isl_ast_node
*isl_ast_graft_get_node(
38 __isl_keep isl_ast_graft
*graft
)
40 return graft
? isl_ast_node_copy(graft
->node
) : NULL
;
43 /* Create a graft for "node" with no guards and no enforced conditions.
45 __isl_give isl_ast_graft
*isl_ast_graft_alloc(
46 __isl_take isl_ast_node
*node
, __isl_keep isl_ast_build
*build
)
55 ctx
= isl_ast_node_get_ctx(node
);
56 graft
= isl_calloc_type(ctx
, isl_ast_graft
);
60 space
= isl_ast_build_get_space(build
, 1);
64 graft
->guard
= isl_set_universe(isl_space_copy(space
));
65 graft
->enforced
= isl_basic_set_universe(space
);
67 if (!graft
->guard
|| !graft
->enforced
)
68 return isl_ast_graft_free(graft
);
72 isl_ast_node_free(node
);
76 /* Create a graft with no guards and no enforced conditions
77 * encapsulating a call to the domain element specified by "executed".
78 * "executed" is assumed to be single-valued.
80 __isl_give isl_ast_graft
*isl_ast_graft_alloc_domain(
81 __isl_take isl_map
*executed
, __isl_keep isl_ast_build
*build
)
85 node
= isl_ast_build_call_from_executed(build
, executed
);
87 return isl_ast_graft_alloc(node
, build
);
90 static __isl_give isl_ast_graft
*isl_ast_graft_copy(
91 __isl_keep isl_ast_graft
*graft
)
100 /* Do all the grafts in "list" have the same guard and is this guard
101 * independent of the current depth?
103 static int equal_independent_guards(__isl_keep isl_ast_graft_list
*list
,
104 __isl_keep isl_ast_build
*build
)
108 isl_ast_graft
*graft_0
;
112 graft_0
= isl_ast_graft_list_get_ast_graft(list
, 0);
116 depth
= isl_ast_build_get_depth(build
);
117 if (isl_set_dim(graft_0
->guard
, isl_dim_set
) <= depth
)
120 skip
= isl_set_involves_dims(graft_0
->guard
,
121 isl_dim_set
, depth
, 1);
122 if (skip
< 0 || skip
) {
123 isl_ast_graft_free(graft_0
);
124 return skip
< 0 ? -1 : 0;
127 n
= isl_ast_graft_list_n_ast_graft(list
);
128 for (i
= 1; i
< n
; ++i
) {
129 isl_ast_graft
*graft
;
130 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
134 equal
= isl_set_is_equal(graft_0
->guard
, graft
->guard
);
135 isl_ast_graft_free(graft
);
136 if (equal
< 0 || !equal
)
140 isl_ast_graft_free(graft_0
);
145 /* Hoist "guard" out of the current level (given by "build").
147 * In particular, eliminate the dimension corresponding to the current depth.
149 static __isl_give isl_set
*hoist_guard(__isl_take isl_set
*guard
,
150 __isl_keep isl_ast_build
*build
)
154 depth
= isl_ast_build_get_depth(build
);
155 if (depth
< isl_set_dim(guard
, isl_dim_set
)) {
156 guard
= isl_set_remove_divs_involving_dims(guard
,
157 isl_dim_set
, depth
, 1);
158 guard
= isl_set_eliminate(guard
, isl_dim_set
, depth
, 1);
159 guard
= isl_set_compute_divs(guard
);
165 /* Extract a common guard from the grafts in "list" that can be hoisted
166 * out of the current level. If no such guard can be found, then return
169 * If all the grafts in the list have the same guard and if this guard
170 * is independent of the current level, then it can be hoisted out.
171 * If there is only one graft in the list and if its guard
172 * depends on the current level, then we eliminate this level and
175 * Otherwise, we return the unshifted simple hull of the guards.
176 * In order to be able to hoist as many constraints as possible,
177 * but at the same time avoid hoisting constraints that did not
178 * appear in the guards in the first place, we intersect the guards
179 * with all the information that is available (i.e., the domain
180 * from the build and the enforced constraints of the graft) and
181 * compute the unshifted hull of the result using only constraints
182 * from the original guards.
183 * In particular, intersecting the guards with other known information
184 * allows us to hoist guards that are only explicit is some of
185 * the grafts and implicit in the others.
187 * The special case for equal guards is needed in case those guards
188 * are non-convex. Taking the simple hull would remove information
189 * and would not allow for these guards to be hoisted completely.
191 __isl_give isl_set
*isl_ast_graft_list_extract_hoistable_guard(
192 __isl_keep isl_ast_graft_list
*list
, __isl_keep isl_ast_build
*build
)
198 isl_set_list
*set_list
;
204 n
= isl_ast_graft_list_n_ast_graft(list
);
206 return isl_set_universe(isl_ast_build_get_space(build
, 1));
208 equal
= equal_independent_guards(list
, build
);
212 if (equal
|| n
== 1) {
213 isl_ast_graft
*graft_0
;
215 graft_0
= isl_ast_graft_list_get_ast_graft(list
, 0);
218 guard
= isl_set_copy(graft_0
->guard
);
220 guard
= hoist_guard(guard
, build
);
221 isl_ast_graft_free(graft_0
);
225 ctx
= isl_ast_build_get_ctx(build
);
226 set_list
= isl_set_list_alloc(ctx
, n
);
227 guard
= isl_set_empty(isl_ast_build_get_space(build
, 1));
228 for (i
= 0; i
< n
; ++i
) {
229 isl_ast_graft
*graft
;
230 isl_basic_set
*enforced
;
233 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
234 enforced
= isl_ast_graft_get_enforced(graft
);
235 guard_i
= isl_set_copy(graft
->guard
);
236 isl_ast_graft_free(graft
);
237 set_list
= isl_set_list_add(set_list
, isl_set_copy(guard_i
));
238 guard_i
= isl_set_intersect(guard_i
,
239 isl_set_from_basic_set(enforced
));
240 guard_i
= isl_set_intersect(guard_i
,
241 isl_ast_build_get_domain(build
));
242 guard
= isl_set_union(guard
, guard_i
);
244 hull
= isl_set_unshifted_simple_hull_from_set_list(guard
, set_list
);
245 guard
= isl_set_from_basic_set(hull
);
246 return hoist_guard(guard
, build
);
249 /* Internal data structure used inside insert_if.
251 * list is the list of guarded nodes created by each call to insert_if.
252 * node is the original node that is guarded by insert_if.
253 * build is the build in which the AST is constructed.
255 struct isl_insert_if_data
{
256 isl_ast_node_list
*list
;
258 isl_ast_build
*build
;
261 static isl_stat
insert_if(__isl_take isl_basic_set
*bset
, void *user
);
263 /* Insert an if node around "node" testing the condition encoded
266 * If the user does not want any disjunctions in the if conditions
267 * and if "guard" does involve a disjunction, then we make the different
268 * disjuncts disjoint and insert an if node corresponding to each disjunct
269 * around a copy of "node". The result is then a block node containing
270 * this sequence of guarded copies of "node".
272 static __isl_give isl_ast_node
*ast_node_insert_if(
273 __isl_take isl_ast_node
*node
, __isl_take isl_set
*guard
,
274 __isl_keep isl_ast_build
*build
)
276 struct isl_insert_if_data data
;
279 ctx
= isl_ast_build_get_ctx(build
);
280 if (isl_options_get_ast_build_allow_or(ctx
) ||
281 isl_set_n_basic_set(guard
) <= 1) {
282 isl_ast_node
*if_node
;
285 expr
= isl_ast_build_expr_from_set_internal(build
, guard
);
287 if_node
= isl_ast_node_alloc_if(expr
);
288 return isl_ast_node_if_set_then(if_node
, node
);
291 guard
= isl_set_make_disjoint(guard
);
293 data
.list
= isl_ast_node_list_alloc(ctx
, 0);
296 if (isl_set_foreach_basic_set(guard
, &insert_if
, &data
) < 0)
297 data
.list
= isl_ast_node_list_free(data
.list
);
300 isl_ast_node_free(data
.node
);
301 return isl_ast_node_alloc_block(data
.list
);
304 /* Insert an if node around a copy of "data->node" testing the condition
305 * encoded in guard "bset" and add the result to data->list.
307 static isl_stat
insert_if(__isl_take isl_basic_set
*bset
, void *user
)
309 struct isl_insert_if_data
*data
= user
;
313 set
= isl_set_from_basic_set(bset
);
314 node
= isl_ast_node_copy(data
->node
);
315 node
= ast_node_insert_if(node
, set
, data
->build
);
316 data
->list
= isl_ast_node_list_add(data
->list
, node
);
321 /* Insert an if node around graft->node testing the condition encoded
322 * in guard "guard", assuming guard involves any conditions.
324 static __isl_give isl_ast_graft
*insert_if_node(
325 __isl_take isl_ast_graft
*graft
, __isl_take isl_set
*guard
,
326 __isl_keep isl_ast_build
*build
)
333 univ
= isl_set_plain_is_universe(guard
);
341 build
= isl_ast_build_copy(build
);
342 graft
->node
= ast_node_insert_if(graft
->node
, guard
, build
);
343 isl_ast_build_free(build
);
346 return isl_ast_graft_free(graft
);
351 return isl_ast_graft_free(graft
);
354 /* Insert an if node around graft->node testing the condition encoded
355 * in graft->guard, assuming graft->guard involves any conditions.
357 static __isl_give isl_ast_graft
*insert_pending_guard_node(
358 __isl_take isl_ast_graft
*graft
, __isl_keep isl_ast_build
*build
)
363 return insert_if_node(graft
, isl_set_copy(graft
->guard
), build
);
366 /* Replace graft->enforced by "enforced".
368 __isl_give isl_ast_graft
*isl_ast_graft_set_enforced(
369 __isl_take isl_ast_graft
*graft
, __isl_take isl_basic_set
*enforced
)
371 if (!graft
|| !enforced
)
374 isl_basic_set_free(graft
->enforced
);
375 graft
->enforced
= enforced
;
379 isl_basic_set_free(enforced
);
380 return isl_ast_graft_free(graft
);
383 /* Update "enforced" such that it only involves constraints that are
384 * also enforced by "graft".
386 static __isl_give isl_basic_set
*update_enforced(
387 __isl_take isl_basic_set
*enforced
, __isl_keep isl_ast_graft
*graft
,
390 isl_basic_set
*enforced_g
;
392 enforced_g
= isl_ast_graft_get_enforced(graft
);
393 if (depth
< isl_basic_set_dim(enforced_g
, isl_dim_set
))
394 enforced_g
= isl_basic_set_eliminate(enforced_g
,
395 isl_dim_set
, depth
, 1);
396 enforced_g
= isl_basic_set_remove_unknown_divs(enforced_g
);
397 enforced_g
= isl_basic_set_align_params(enforced_g
,
398 isl_basic_set_get_space(enforced
));
399 enforced
= isl_basic_set_align_params(enforced
,
400 isl_basic_set_get_space(enforced_g
));
401 enforced
= isl_set_simple_hull(isl_basic_set_union(enforced
,
407 /* Extend the node at *body with node.
409 * If body points to the else branch, then *body may still be NULL.
410 * If so, we simply attach node to this else branch.
411 * Otherwise, we attach a list containing the statements already
412 * attached at *body followed by node.
414 static void extend_body(__isl_keep isl_ast_node
**body
,
415 __isl_take isl_ast_node
*node
)
417 isl_ast_node_list
*list
;
424 if ((*body
)->type
== isl_ast_node_block
) {
425 list
= isl_ast_node_block_get_children(*body
);
426 isl_ast_node_free(*body
);
428 list
= isl_ast_node_list_from_ast_node(*body
);
429 list
= isl_ast_node_list_add(list
, node
);
430 *body
= isl_ast_node_alloc_block(list
);
433 /* Merge "graft" into the last graft of "list".
434 * body points to the then or else branch of an if node in that last graft.
436 * We attach graft->node to this branch and update the enforced
437 * set of the last graft of "list" to take into account the enforced
440 static __isl_give isl_ast_graft_list
*graft_extend_body(
441 __isl_take isl_ast_graft_list
*list
,
442 __isl_keep isl_ast_node
**body
, __isl_take isl_ast_graft
*graft
,
443 __isl_keep isl_ast_build
*build
)
449 isl_basic_set
*enforced
;
453 extend_body(body
, isl_ast_node_copy(graft
->node
));
457 n
= isl_ast_graft_list_n_ast_graft(list
);
458 last
= isl_ast_graft_list_get_ast_graft(list
, n
- 1);
460 depth
= isl_ast_build_get_depth(build
);
461 space
= isl_ast_build_get_space(build
, 1);
462 enforced
= isl_basic_set_empty(space
);
463 enforced
= update_enforced(enforced
, last
, depth
);
464 enforced
= update_enforced(enforced
, graft
, depth
);
465 last
= isl_ast_graft_set_enforced(last
, enforced
);
467 list
= isl_ast_graft_list_set_ast_graft(list
, n
- 1, last
);
468 isl_ast_graft_free(graft
);
471 isl_ast_graft_free(graft
);
472 return isl_ast_graft_list_free(list
);
475 /* Merge "graft" into the last graft of "list", attaching graft->node
476 * to the then branch of "last_if".
478 static __isl_give isl_ast_graft_list
*extend_then(
479 __isl_take isl_ast_graft_list
*list
,
480 __isl_keep isl_ast_node
*last_if
, __isl_take isl_ast_graft
*graft
,
481 __isl_keep isl_ast_build
*build
)
483 return graft_extend_body(list
, &last_if
->u
.i
.then
, graft
, build
);
486 /* Merge "graft" into the last graft of "list", attaching graft->node
487 * to the else branch of "last_if".
489 static __isl_give isl_ast_graft_list
*extend_else(
490 __isl_take isl_ast_graft_list
*list
,
491 __isl_keep isl_ast_node
*last_if
, __isl_take isl_ast_graft
*graft
,
492 __isl_keep isl_ast_build
*build
)
494 return graft_extend_body(list
, &last_if
->u
.i
.else_node
, graft
, build
);
497 /* This data structure keeps track of an if node.
499 * "node" is the actual if-node
500 * "guard" is the original, non-simplified guard of the node
501 * "complement" is the complement of "guard" in the context of outer if nodes
509 /* Given a list of "n" if nodes, clear those starting at "first"
510 * and return "first" (i.e., the updated size of the array).
512 static int clear_if_nodes(struct isl_if_node
*if_node
, int first
, int n
)
516 for (i
= first
; i
< n
; ++i
) {
517 isl_set_free(if_node
[i
].guard
);
518 isl_set_free(if_node
[i
].complement
);
524 /* For each graft in "list",
525 * insert an if node around graft->node testing the condition encoded
526 * in graft->guard, assuming graft->guard involves any conditions.
528 * We keep track of a list of generated if nodes that can be extended
529 * without changing the order of the elements in "list".
530 * If the guard of a graft is a subset of either the guard or its complement
531 * of one of those if nodes, then the node
532 * of the new graft is inserted into the then or else branch of the last graft
533 * and the current graft is discarded.
534 * The guard of the node is then simplified based on the conditions
535 * enforced at that then or else branch.
536 * Otherwise, the current graft is appended to the list.
538 * We only construct else branches if allowed by the user.
540 static __isl_give isl_ast_graft_list
*insert_pending_guard_nodes(
541 __isl_take isl_ast_graft_list
*list
,
542 __isl_keep isl_ast_build
*build
)
547 isl_ast_graft_list
*res
;
548 struct isl_if_node
*if_node
= NULL
;
551 return isl_ast_graft_list_free(list
);
553 ctx
= isl_ast_build_get_ctx(build
);
554 n
= isl_ast_graft_list_n_ast_graft(list
);
556 allow_else
= isl_options_get_ast_build_allow_else(ctx
);
560 if_node
= isl_alloc_array(ctx
, struct isl_if_node
, n
- 1);
562 return isl_ast_graft_list_free(list
);
565 res
= isl_ast_graft_list_alloc(ctx
, n
);
567 for (i
= 0; i
< n
; ++i
) {
569 isl_ast_graft
*graft
;
570 int subset
, found_then
, found_else
;
573 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
577 found_then
= found_else
= -1;
580 test
= isl_set_copy(graft
->guard
);
581 test
= isl_set_intersect(test
,
582 isl_set_copy(build
->domain
));
583 for (j
= n_if
- 1; j
>= 0; --j
) {
584 subset
= isl_set_is_subset(test
,
586 if (subset
< 0 || subset
) {
592 subset
= isl_set_is_subset(test
,
593 if_node
[j
].complement
);
594 if (subset
< 0 || subset
) {
599 n_if
= clear_if_nodes(if_node
, j
+ 1, n_if
);
603 graft
= isl_ast_graft_free(graft
);
607 guard
= isl_set_copy(graft
->guard
);
609 graft
->guard
= isl_set_gist(graft
->guard
,
610 isl_set_copy(if_node
[found_then
].guard
));
611 else if (found_else
>= 0)
612 graft
->guard
= isl_set_gist(graft
->guard
,
613 isl_set_copy(if_node
[found_else
].complement
));
617 graft
= isl_ast_graft_free(graft
);
618 graft
= insert_pending_guard_node(graft
, build
);
619 if (graft
&& graft
->node
!= node
&& i
!= n
- 1) {
621 if_node
[n_if
].node
= graft
->node
;
622 if_node
[n_if
].guard
= guard
;
624 set
= if_node
[found_then
].guard
;
625 else if (found_else
>= 0)
626 set
= if_node
[found_else
].complement
;
629 set
= isl_set_copy(set
);
630 set
= isl_set_subtract(set
, isl_set_copy(guard
));
631 if_node
[n_if
].complement
= set
;
639 res
= extend_then(res
, if_node
[found_then
].node
,
641 else if (found_else
>= 0)
642 res
= extend_else(res
, if_node
[found_else
].node
,
645 res
= isl_ast_graft_list_add(res
, graft
);
648 res
= isl_ast_graft_list_free(res
);
650 isl_ast_graft_list_free(list
);
651 clear_if_nodes(if_node
, 0, n_if
);
656 /* For each graft in "list",
657 * insert an if node around graft->node testing the condition encoded
658 * in graft->guard, assuming graft->guard involves any conditions.
659 * Subsequently remove the guards from the grafts.
661 __isl_give isl_ast_graft_list
*isl_ast_graft_list_insert_pending_guard_nodes(
662 __isl_take isl_ast_graft_list
*list
, __isl_keep isl_ast_build
*build
)
667 list
= insert_pending_guard_nodes(list
, build
);
671 universe
= isl_set_universe(isl_ast_build_get_space(build
, 1));
672 n
= isl_ast_graft_list_n_ast_graft(list
);
673 for (i
= 0; i
< n
; ++i
) {
674 isl_ast_graft
*graft
;
676 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
679 isl_set_free(graft
->guard
);
680 graft
->guard
= isl_set_copy(universe
);
682 graft
= isl_ast_graft_free(graft
);
683 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
685 isl_set_free(universe
);
687 return isl_ast_graft_list_free(list
);
692 /* Collect the nodes contained in the grafts in "list" in a node list.
694 static __isl_give isl_ast_node_list
*extract_node_list(
695 __isl_keep isl_ast_graft_list
*list
)
699 isl_ast_node_list
*node_list
;
703 ctx
= isl_ast_graft_list_get_ctx(list
);
704 n
= isl_ast_graft_list_n_ast_graft(list
);
705 node_list
= isl_ast_node_list_alloc(ctx
, n
);
706 for (i
= 0; i
< n
; ++i
) {
708 isl_ast_graft
*graft
;
710 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
711 node
= isl_ast_graft_get_node(graft
);
712 node_list
= isl_ast_node_list_add(node_list
, node
);
713 isl_ast_graft_free(graft
);
719 /* Look for shared enforced constraints by all the elements in "list"
720 * on outer loops (with respect to the current depth) and return the result.
722 * If there are no elements in "list", then return the empty set.
724 __isl_give isl_basic_set
*isl_ast_graft_list_extract_shared_enforced(
725 __isl_keep isl_ast_graft_list
*list
,
726 __isl_keep isl_ast_build
*build
)
731 isl_basic_set
*enforced
;
736 space
= isl_ast_build_get_space(build
, 1);
737 enforced
= isl_basic_set_empty(space
);
739 depth
= isl_ast_build_get_depth(build
);
740 n
= isl_ast_graft_list_n_ast_graft(list
);
741 for (i
= 0; i
< n
; ++i
) {
742 isl_ast_graft
*graft
;
744 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
745 enforced
= update_enforced(enforced
, graft
, depth
);
746 isl_ast_graft_free(graft
);
752 /* Record "guard" in "graft" so that it will be enforced somewhere
753 * up the tree. If the graft already has a guard, then it may be partially
754 * redundant in combination with the new guard and in the context
755 * the generated constraints of "build". In fact, the new guard
756 * may in itself have some redundant constraints.
757 * We therefore (re)compute the gist of the intersection
758 * and coalesce the result.
760 static __isl_give isl_ast_graft
*store_guard(__isl_take isl_ast_graft
*graft
,
761 __isl_take isl_set
*guard
, __isl_keep isl_ast_build
*build
)
768 is_universe
= isl_set_plain_is_universe(guard
);
776 graft
->guard
= isl_set_intersect(graft
->guard
, guard
);
777 graft
->guard
= isl_set_gist(graft
->guard
,
778 isl_ast_build_get_generated(build
));
779 graft
->guard
= isl_set_coalesce(graft
->guard
);
781 return isl_ast_graft_free(graft
);
786 return isl_ast_graft_free(graft
);
789 /* For each graft in "list", replace its guard with the gist with
790 * respect to "context".
792 static __isl_give isl_ast_graft_list
*gist_guards(
793 __isl_take isl_ast_graft_list
*list
, __isl_keep isl_set
*context
)
800 n
= isl_ast_graft_list_n_ast_graft(list
);
801 for (i
= 0; i
< n
; ++i
) {
802 isl_ast_graft
*graft
;
804 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
807 graft
->guard
= isl_set_gist(graft
->guard
,
808 isl_set_copy(context
));
810 graft
= isl_ast_graft_free(graft
);
811 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
814 return isl_ast_graft_list_free(list
);
819 /* For each graft in "list", replace its guard with the gist with
820 * respect to "context".
822 __isl_give isl_ast_graft_list
*isl_ast_graft_list_gist_guards(
823 __isl_take isl_ast_graft_list
*list
, __isl_take isl_set
*context
)
825 list
= gist_guards(list
, context
);
826 isl_set_free(context
);
831 /* Allocate a graft in "build" based on the list of grafts in "sub_build".
832 * "guard" and "enforced" are the guard and enforced constraints
833 * of the allocated graft. The guard is used to simplify the guards
834 * of the elements in "list".
836 * The node is initialized to either a block containing the nodes of "children"
837 * or, if there is only a single child, the node of that child.
838 * If the current level requires a for node, it should be inserted by
839 * a subsequent call to isl_ast_graft_insert_for.
841 __isl_give isl_ast_graft
*isl_ast_graft_alloc_from_children(
842 __isl_take isl_ast_graft_list
*list
, __isl_take isl_set
*guard
,
843 __isl_take isl_basic_set
*enforced
, __isl_keep isl_ast_build
*build
,
844 __isl_keep isl_ast_build
*sub_build
)
846 isl_ast_build
*guard_build
;
848 isl_ast_node_list
*node_list
;
849 isl_ast_graft
*graft
;
851 guard_build
= isl_ast_build_copy(sub_build
);
852 guard_build
= isl_ast_build_replace_pending_by_guard(guard_build
,
853 isl_set_copy(guard
));
854 list
= gist_guards(list
, guard
);
855 list
= insert_pending_guard_nodes(list
, guard_build
);
856 isl_ast_build_free(guard_build
);
858 node_list
= extract_node_list(list
);
859 node
= isl_ast_node_from_ast_node_list(node_list
);
860 isl_ast_graft_list_free(list
);
862 graft
= isl_ast_graft_alloc(node
, build
);
863 graft
= store_guard(graft
, guard
, build
);
864 graft
= isl_ast_graft_enforce(graft
, enforced
);
869 /* Combine the grafts in the list into a single graft.
871 * The guard is initialized to the shared guard of the list elements (if any),
872 * provided it does not depend on the current dimension.
873 * The guards in the elements are then simplified with respect to the
874 * hoisted guard and materialized as if nodes around the contained AST nodes
875 * in the context of "sub_build".
877 * The enforced set is initialized to the simple hull of the enforced sets
878 * of the elements, provided the ast_build_exploit_nested_bounds option is set
879 * or the new graft will be used at the same level.
881 * The node is initialized to either a block containing the nodes of "list"
882 * or, if there is only a single element, the node of that element.
884 static __isl_give isl_ast_graft
*ast_graft_list_fuse(
885 __isl_take isl_ast_graft_list
*list
, __isl_keep isl_ast_build
*build
)
887 isl_ast_graft
*graft
;
888 isl_basic_set
*enforced
;
894 enforced
= isl_ast_graft_list_extract_shared_enforced(list
, build
);
895 guard
= isl_ast_graft_list_extract_hoistable_guard(list
, build
);
896 graft
= isl_ast_graft_alloc_from_children(list
, guard
, enforced
,
902 /* Combine the grafts in the list into a single graft.
903 * Return a list containing this single graft.
904 * If the original list is empty, then return an empty list.
906 __isl_give isl_ast_graft_list
*isl_ast_graft_list_fuse(
907 __isl_take isl_ast_graft_list
*list
,
908 __isl_keep isl_ast_build
*build
)
910 isl_ast_graft
*graft
;
914 if (isl_ast_graft_list_n_ast_graft(list
) <= 1)
916 graft
= ast_graft_list_fuse(list
, build
);
917 return isl_ast_graft_list_from_ast_graft(graft
);
920 /* Combine the two grafts into a single graft.
921 * Return a list containing this single graft.
923 static __isl_give isl_ast_graft
*isl_ast_graft_fuse(
924 __isl_take isl_ast_graft
*graft1
, __isl_take isl_ast_graft
*graft2
,
925 __isl_keep isl_ast_build
*build
)
928 isl_ast_graft_list
*list
;
930 ctx
= isl_ast_build_get_ctx(build
);
932 list
= isl_ast_graft_list_alloc(ctx
, 2);
933 list
= isl_ast_graft_list_add(list
, graft1
);
934 list
= isl_ast_graft_list_add(list
, graft2
);
936 return ast_graft_list_fuse(list
, build
);
939 /* Insert a for node enclosing the current graft->node.
941 __isl_give isl_ast_graft
*isl_ast_graft_insert_for(
942 __isl_take isl_ast_graft
*graft
, __isl_take isl_ast_node
*node
)
947 graft
->node
= isl_ast_node_for_set_body(node
, graft
->node
);
949 return isl_ast_graft_free(graft
);
953 isl_ast_node_free(node
);
954 isl_ast_graft_free(graft
);
958 /* Insert a mark governing the current graft->node.
960 __isl_give isl_ast_graft
*isl_ast_graft_insert_mark(
961 __isl_take isl_ast_graft
*graft
, __isl_take isl_id
*mark
)
966 graft
->node
= isl_ast_node_alloc_mark(mark
, graft
->node
);
968 return isl_ast_graft_free(graft
);
973 isl_ast_graft_free(graft
);
977 /* Represent the graft list as an AST node.
978 * This operation drops the information about guards in the grafts, so
979 * if there are any pending guards, then they are materialized as if nodes.
981 __isl_give isl_ast_node
*isl_ast_node_from_graft_list(
982 __isl_take isl_ast_graft_list
*list
,
983 __isl_keep isl_ast_build
*build
)
985 isl_ast_node_list
*node_list
;
987 list
= insert_pending_guard_nodes(list
, build
);
988 node_list
= extract_node_list(list
);
989 isl_ast_graft_list_free(list
);
991 return isl_ast_node_from_ast_node_list(node_list
);
994 void *isl_ast_graft_free(__isl_take isl_ast_graft
*graft
)
999 if (--graft
->ref
> 0)
1002 isl_ast_node_free(graft
->node
);
1003 isl_set_free(graft
->guard
);
1004 isl_basic_set_free(graft
->enforced
);
1010 /* Record that the grafted tree enforces
1011 * "enforced" by intersecting graft->enforced with "enforced".
1013 __isl_give isl_ast_graft
*isl_ast_graft_enforce(
1014 __isl_take isl_ast_graft
*graft
, __isl_take isl_basic_set
*enforced
)
1016 if (!graft
|| !enforced
)
1019 enforced
= isl_basic_set_align_params(enforced
,
1020 isl_basic_set_get_space(graft
->enforced
));
1021 graft
->enforced
= isl_basic_set_align_params(graft
->enforced
,
1022 isl_basic_set_get_space(enforced
));
1023 graft
->enforced
= isl_basic_set_intersect(graft
->enforced
, enforced
);
1024 if (!graft
->enforced
)
1025 return isl_ast_graft_free(graft
);
1029 isl_basic_set_free(enforced
);
1030 return isl_ast_graft_free(graft
);
1033 __isl_give isl_basic_set
*isl_ast_graft_get_enforced(
1034 __isl_keep isl_ast_graft
*graft
)
1036 return graft
? isl_basic_set_copy(graft
->enforced
) : NULL
;
1039 __isl_give isl_set
*isl_ast_graft_get_guard(__isl_keep isl_ast_graft
*graft
)
1041 return graft
? isl_set_copy(graft
->guard
) : NULL
;
1044 /* Record that "guard" needs to be inserted in "graft".
1046 __isl_give isl_ast_graft
*isl_ast_graft_add_guard(
1047 __isl_take isl_ast_graft
*graft
,
1048 __isl_take isl_set
*guard
, __isl_keep isl_ast_build
*build
)
1050 return store_guard(graft
, guard
, build
);
1053 /* Reformulate the "graft", which was generated in the context
1054 * of an inner code generation, in terms of the outer code generation
1057 * If "product" is set, then the domain of the inner code generation build is
1061 * with O the domain of the outer code generation build.
1062 * We essentially need to project out S.
1064 * If "product" is not set, then we need to project the domains onto
1065 * their parameter spaces.
1067 __isl_give isl_ast_graft
*isl_ast_graft_unembed(__isl_take isl_ast_graft
*graft
,
1070 isl_basic_set
*enforced
;
1076 enforced
= graft
->enforced
;
1077 enforced
= isl_basic_map_domain(isl_basic_set_unwrap(enforced
));
1078 graft
->enforced
= enforced
;
1079 graft
->guard
= isl_map_domain(isl_set_unwrap(graft
->guard
));
1081 graft
->enforced
= isl_basic_set_params(graft
->enforced
);
1082 graft
->guard
= isl_set_params(graft
->guard
);
1084 graft
->guard
= isl_set_compute_divs(graft
->guard
);
1086 if (!graft
->enforced
|| !graft
->guard
)
1087 return isl_ast_graft_free(graft
);
1092 /* Reformulate the grafts in "list", which were generated in the context
1093 * of an inner code generation, in terms of the outer code generation
1096 __isl_give isl_ast_graft_list
*isl_ast_graft_list_unembed(
1097 __isl_take isl_ast_graft_list
*list
, int product
)
1101 n
= isl_ast_graft_list_n_ast_graft(list
);
1102 for (i
= 0; i
< n
; ++i
) {
1103 isl_ast_graft
*graft
;
1105 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
1106 graft
= isl_ast_graft_unembed(graft
, product
);
1107 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
1113 /* Compute the preimage of "graft" under the function represented by "ma".
1114 * In other words, plug in "ma" in "enforced" and "guard" fields of "graft".
1116 __isl_give isl_ast_graft
*isl_ast_graft_preimage_multi_aff(
1117 __isl_take isl_ast_graft
*graft
, __isl_take isl_multi_aff
*ma
)
1119 isl_basic_set
*enforced
;
1124 enforced
= graft
->enforced
;
1125 graft
->enforced
= isl_basic_set_preimage_multi_aff(enforced
,
1126 isl_multi_aff_copy(ma
));
1127 graft
->guard
= isl_set_preimage_multi_aff(graft
->guard
, ma
);
1129 if (!graft
->enforced
|| !graft
->guard
)
1130 return isl_ast_graft_free(graft
);
1135 /* Compute the preimage of all the grafts in "list" under
1136 * the function represented by "ma".
1138 __isl_give isl_ast_graft_list
*isl_ast_graft_list_preimage_multi_aff(
1139 __isl_take isl_ast_graft_list
*list
, __isl_take isl_multi_aff
*ma
)
1143 n
= isl_ast_graft_list_n_ast_graft(list
);
1144 for (i
= 0; i
< n
; ++i
) {
1145 isl_ast_graft
*graft
;
1147 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
1148 graft
= isl_ast_graft_preimage_multi_aff(graft
,
1149 isl_multi_aff_copy(ma
));
1150 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
1153 isl_multi_aff_free(ma
);
1157 /* Compare two grafts based on their guards.
1159 static int cmp_graft(__isl_keep isl_ast_graft
*a
, __isl_keep isl_ast_graft
*b
,
1162 return isl_set_plain_cmp(a
->guard
, b
->guard
);
1165 /* Order the elements in "list" based on their guards.
1167 __isl_give isl_ast_graft_list
*isl_ast_graft_list_sort_guard(
1168 __isl_take isl_ast_graft_list
*list
)
1170 return isl_ast_graft_list_sort(list
, &cmp_graft
, NULL
);
1173 /* Merge the given two lists into a single list of grafts,
1174 * merging grafts with the same guard into a single graft.
1176 * "list2" has been sorted using isl_ast_graft_list_sort.
1177 * "list1" may be the result of a previous call to isl_ast_graft_list_merge
1178 * and may therefore not be completely sorted.
1180 * The elements in "list2" need to be executed after those in "list1",
1181 * but if the guard of a graft in "list2" is disjoint from the guards
1182 * of some final elements in "list1", then it can be moved up to before
1183 * those final elements.
1185 * In particular, we look at each element g of "list2" in turn
1186 * and move it up beyond elements of "list1" that would be sorted
1187 * after g as long as each of these elements has a guard that is disjoint
1190 * We do not allow the second or any later element of "list2" to be moved
1191 * before a previous elements of "list2" even if the reason that
1192 * that element didn't move up further was that its guard was not disjoint
1193 * from that of the previous element in "list1".
1195 __isl_give isl_ast_graft_list
*isl_ast_graft_list_merge(
1196 __isl_take isl_ast_graft_list
*list1
,
1197 __isl_take isl_ast_graft_list
*list2
,
1198 __isl_keep isl_ast_build
*build
)
1202 if (!list1
|| !list2
|| !build
)
1204 if (list2
->n
== 0) {
1205 isl_ast_graft_list_free(list2
);
1208 if (list1
->n
== 0) {
1209 isl_ast_graft_list_free(list1
);
1214 for (i
= 0; i
< list2
->n
; ++i
) {
1215 isl_ast_graft
*graft
;
1216 graft
= isl_ast_graft_list_get_ast_graft(list2
, i
);
1220 for (j
= list1
->n
; j
>= 0; --j
) {
1222 isl_ast_graft
*graft_j
;
1227 cmp
= isl_set_plain_cmp(list1
->p
[j
- 1]->guard
,
1230 disjoint
= isl_set_is_disjoint(graft
->guard
,
1231 list1
->p
[j
- 1]->guard
);
1233 isl_ast_graft_free(graft
);
1234 list1
= isl_ast_graft_list_free(list1
);
1243 list1
= isl_ast_graft_list_insert(list1
, j
,
1250 graft_j
= isl_ast_graft_list_get_ast_graft(list1
, j
);
1251 graft_j
= isl_ast_graft_fuse(graft_j
, graft
, build
);
1252 list1
= isl_ast_graft_list_set_ast_graft(list1
, j
,
1258 isl_ast_graft_free(graft
);
1259 isl_die(isl_ast_build_get_ctx(build
),
1261 "element failed to get inserted", break);
1269 list1
= isl_ast_graft_list_free(list1
);
1270 isl_ast_graft_list_free(list2
);
1274 isl_ast_graft_list_free(list1
);
1275 isl_ast_graft_list_free(list2
);
1279 __isl_give isl_printer
*isl_printer_print_ast_graft(__isl_take isl_printer
*p
,
1280 __isl_keep isl_ast_graft
*graft
)
1285 return isl_printer_free(p
);
1287 p
= isl_printer_print_str(p
, "(");
1288 p
= isl_printer_print_str(p
, "guard: ");
1289 p
= isl_printer_print_set(p
, graft
->guard
);
1290 p
= isl_printer_print_str(p
, ", ");
1291 p
= isl_printer_print_str(p
, "enforced: ");
1292 p
= isl_printer_print_basic_set(p
, graft
->enforced
);
1293 p
= isl_printer_print_str(p
, ", ");
1294 p
= isl_printer_print_str(p
, "node: ");
1295 p
= isl_printer_print_ast_node(p
, graft
->node
);
1296 p
= isl_printer_print_str(p
, ")");