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
14 #include <isl/space.h>
15 #include <isl_ast_private.h>
16 #include <isl_ast_build_expr.h>
17 #include <isl_ast_build_private.h>
18 #include <isl_ast_graft_private.h>
20 static __isl_give isl_ast_graft
*isl_ast_graft_copy(
21 __isl_keep isl_ast_graft
*graft
);
24 #define BASE ast_graft
26 #include <isl_list_templ.c>
29 #define BASE ast_graft
30 #include <print_templ.c>
32 isl_ctx
*isl_ast_graft_get_ctx(__isl_keep isl_ast_graft
*graft
)
36 return isl_basic_set_get_ctx(graft
->enforced
);
39 __isl_give isl_ast_node
*isl_ast_graft_get_node(
40 __isl_keep isl_ast_graft
*graft
)
42 return graft
? isl_ast_node_copy(graft
->node
) : NULL
;
45 /* Create a graft for "node" with no guards and no enforced conditions.
47 __isl_give isl_ast_graft
*isl_ast_graft_alloc(
48 __isl_take isl_ast_node
*node
, __isl_keep isl_ast_build
*build
)
57 ctx
= isl_ast_node_get_ctx(node
);
58 graft
= isl_calloc_type(ctx
, isl_ast_graft
);
62 space
= isl_ast_build_get_space(build
, 1);
66 graft
->guard
= isl_set_universe(isl_space_copy(space
));
67 graft
->enforced
= isl_basic_set_universe(space
);
69 if (!graft
->guard
|| !graft
->enforced
)
70 return isl_ast_graft_free(graft
);
74 isl_ast_node_free(node
);
78 /* Create a graft with no guards and no enforced conditions
79 * encapsulating a call to the domain element specified by "executed".
80 * "executed" is assumed to be single-valued.
82 __isl_give isl_ast_graft
*isl_ast_graft_alloc_domain(
83 __isl_take isl_map
*executed
, __isl_keep isl_ast_build
*build
)
87 node
= isl_ast_build_call_from_executed(build
, executed
);
89 return isl_ast_graft_alloc(node
, build
);
92 static __isl_give isl_ast_graft
*isl_ast_graft_copy(
93 __isl_keep isl_ast_graft
*graft
)
102 /* Do all the grafts in "list" have the same guard and is this guard
103 * independent of the current depth?
105 static isl_bool
equal_independent_guards(__isl_keep isl_ast_graft_list
*list
,
106 __isl_keep isl_ast_build
*build
)
112 isl_ast_graft
*graft_0
;
113 isl_bool equal
= isl_bool_true
;
116 n
= isl_ast_graft_list_n_ast_graft(list
);
118 return isl_bool_error
;
119 graft_0
= isl_ast_graft_list_get_ast_graft(list
, 0);
121 return isl_bool_error
;
123 depth
= isl_ast_build_get_depth(build
);
124 dim
= isl_set_dim(graft_0
->guard
, isl_dim_set
);
126 return isl_bool_error
;
128 skip
= isl_bool_false
;
130 skip
= isl_set_involves_dims(graft_0
->guard
,
131 isl_dim_set
, depth
, 1);
132 if (skip
< 0 || skip
) {
133 isl_ast_graft_free(graft_0
);
134 return isl_bool_not(skip
);
137 for (i
= 1; i
< n
; ++i
) {
138 isl_ast_graft
*graft
;
139 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
141 equal
= isl_bool_error
;
143 equal
= isl_set_is_equal(graft_0
->guard
, graft
->guard
);
144 isl_ast_graft_free(graft
);
145 if (equal
< 0 || !equal
)
149 isl_ast_graft_free(graft_0
);
154 /* Hoist "guard" out of the current level (given by "build").
156 * In particular, eliminate the dimension corresponding to the current depth.
158 static __isl_give isl_set
*hoist_guard(__isl_take isl_set
*guard
,
159 __isl_keep isl_ast_build
*build
)
164 depth
= isl_ast_build_get_depth(build
);
165 dim
= isl_set_dim(guard
, isl_dim_set
);
167 return isl_set_free(guard
);
169 guard
= isl_set_remove_divs_involving_dims(guard
,
170 isl_dim_set
, depth
, 1);
171 guard
= isl_set_eliminate(guard
, isl_dim_set
, depth
, 1);
172 guard
= isl_set_compute_divs(guard
);
178 /* Extract a common guard from the grafts in "list" that can be hoisted
179 * out of the current level. If no such guard can be found, then return
182 * If all the grafts in the list have the same guard and if this guard
183 * is independent of the current level, then it can be hoisted out.
184 * If there is only one graft in the list and if its guard
185 * depends on the current level, then we eliminate this level and
188 * Otherwise, we return the unshifted simple hull of the guards.
189 * In order to be able to hoist as many constraints as possible,
190 * but at the same time avoid hoisting constraints that did not
191 * appear in the guards in the first place, we intersect the guards
192 * with all the information that is available (i.e., the domain
193 * from the build and the enforced constraints of the graft) and
194 * compute the unshifted hull of the result using only constraints
195 * from the original guards.
196 * In particular, intersecting the guards with other known information
197 * allows us to hoist guards that are only explicit is some of
198 * the grafts and implicit in the others.
200 * The special case for equal guards is needed in case those guards
201 * are non-convex. Taking the simple hull would remove information
202 * and would not allow for these guards to be hoisted completely.
204 __isl_give isl_set
*isl_ast_graft_list_extract_hoistable_guard(
205 __isl_keep isl_ast_graft_list
*list
, __isl_keep isl_ast_build
*build
)
212 isl_set_list
*set_list
;
218 n
= isl_ast_graft_list_n_ast_graft(list
);
222 return isl_set_universe(isl_ast_build_get_space(build
, 1));
224 equal
= equal_independent_guards(list
, build
);
228 if (equal
|| n
== 1) {
229 isl_ast_graft
*graft_0
;
231 graft_0
= isl_ast_graft_list_get_ast_graft(list
, 0);
234 guard
= isl_set_copy(graft_0
->guard
);
236 guard
= hoist_guard(guard
, build
);
237 isl_ast_graft_free(graft_0
);
241 ctx
= isl_ast_build_get_ctx(build
);
242 set_list
= isl_set_list_alloc(ctx
, n
);
243 guard
= isl_set_empty(isl_ast_build_get_space(build
, 1));
244 for (i
= 0; i
< n
; ++i
) {
245 isl_ast_graft
*graft
;
246 isl_basic_set
*enforced
;
249 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
250 enforced
= isl_ast_graft_get_enforced(graft
);
251 guard_i
= isl_set_copy(graft
->guard
);
252 isl_ast_graft_free(graft
);
253 set_list
= isl_set_list_add(set_list
, isl_set_copy(guard_i
));
254 guard_i
= isl_set_intersect(guard_i
,
255 isl_set_from_basic_set(enforced
));
256 guard_i
= isl_set_intersect(guard_i
,
257 isl_ast_build_get_domain(build
));
258 guard
= isl_set_union(guard
, guard_i
);
260 hull
= isl_set_unshifted_simple_hull_from_set_list(guard
, set_list
);
261 guard
= isl_set_from_basic_set(hull
);
262 return hoist_guard(guard
, build
);
265 /* Internal data structure used inside insert_if.
267 * list is the list of guarded nodes created by each call to insert_if.
268 * node is the original node that is guarded by insert_if.
269 * build is the build in which the AST is constructed.
271 struct isl_insert_if_data
{
272 isl_ast_node_list
*list
;
274 isl_ast_build
*build
;
277 static isl_stat
insert_if(__isl_take isl_basic_set
*bset
, void *user
);
279 /* Insert an if node around "node" testing the condition encoded
282 * If the user does not want any disjunctions in the if conditions
283 * and if "guard" does involve a disjunction, then we make the different
284 * disjuncts disjoint and insert an if node corresponding to each disjunct
285 * around a copy of "node". The result is then a block node containing
286 * this sequence of guarded copies of "node".
288 static __isl_give isl_ast_node
*ast_node_insert_if(
289 __isl_take isl_ast_node
*node
, __isl_take isl_set
*guard
,
290 __isl_keep isl_ast_build
*build
)
292 struct isl_insert_if_data data
;
296 n
= isl_set_n_basic_set(guard
);
299 ctx
= isl_ast_build_get_ctx(build
);
300 if (isl_options_get_ast_build_allow_or(ctx
) || n
<= 1) {
301 isl_ast_node
*if_node
;
304 expr
= isl_ast_build_expr_from_set_internal(build
, guard
);
306 if_node
= isl_ast_node_alloc_if(expr
);
307 return isl_ast_node_if_set_then(if_node
, node
);
310 guard
= isl_set_make_disjoint(guard
);
312 data
.list
= isl_ast_node_list_alloc(ctx
, 0);
315 if (isl_set_foreach_basic_set(guard
, &insert_if
, &data
) < 0)
316 data
.list
= isl_ast_node_list_free(data
.list
);
319 isl_ast_node_free(data
.node
);
320 return isl_ast_node_alloc_block(data
.list
);
323 isl_ast_node_free(node
);
327 /* Insert an if node around a copy of "data->node" testing the condition
328 * encoded in guard "bset" and add the result to data->list.
330 static isl_stat
insert_if(__isl_take isl_basic_set
*bset
, void *user
)
332 struct isl_insert_if_data
*data
= user
;
336 set
= isl_set_from_basic_set(bset
);
337 node
= isl_ast_node_copy(data
->node
);
338 node
= ast_node_insert_if(node
, set
, data
->build
);
339 data
->list
= isl_ast_node_list_add(data
->list
, node
);
344 /* Insert an if node around graft->node testing the condition encoded
345 * in guard "guard", assuming guard involves any conditions.
347 static __isl_give isl_ast_graft
*insert_if_node(
348 __isl_take isl_ast_graft
*graft
, __isl_take isl_set
*guard
,
349 __isl_keep isl_ast_build
*build
)
356 univ
= isl_set_plain_is_universe(guard
);
364 build
= isl_ast_build_copy(build
);
365 graft
->node
= ast_node_insert_if(graft
->node
, guard
, build
);
366 isl_ast_build_free(build
);
369 return isl_ast_graft_free(graft
);
374 return isl_ast_graft_free(graft
);
377 /* Insert an if node around graft->node testing the condition encoded
378 * in graft->guard, assuming graft->guard involves any conditions.
380 static __isl_give isl_ast_graft
*insert_pending_guard_node(
381 __isl_take isl_ast_graft
*graft
, __isl_keep isl_ast_build
*build
)
386 return insert_if_node(graft
, isl_set_copy(graft
->guard
), build
);
389 /* Replace graft->enforced by "enforced".
391 __isl_give isl_ast_graft
*isl_ast_graft_set_enforced(
392 __isl_take isl_ast_graft
*graft
, __isl_take isl_basic_set
*enforced
)
394 if (!graft
|| !enforced
)
397 isl_basic_set_free(graft
->enforced
);
398 graft
->enforced
= enforced
;
402 isl_basic_set_free(enforced
);
403 return isl_ast_graft_free(graft
);
406 /* Update "enforced" such that it only involves constraints that are
407 * also enforced by "graft".
409 static __isl_give isl_basic_set
*update_enforced(
410 __isl_take isl_basic_set
*enforced
, __isl_keep isl_ast_graft
*graft
,
414 isl_basic_set
*enforced_g
;
416 enforced_g
= isl_ast_graft_get_enforced(graft
);
417 dim
= isl_basic_set_dim(enforced_g
, isl_dim_set
);
419 enforced_g
= isl_basic_set_free(enforced_g
);
421 enforced_g
= isl_basic_set_eliminate(enforced_g
,
422 isl_dim_set
, depth
, 1);
423 enforced_g
= isl_basic_set_remove_unknown_divs(enforced_g
);
424 enforced_g
= isl_basic_set_align_params(enforced_g
,
425 isl_basic_set_get_space(enforced
));
426 enforced
= isl_basic_set_align_params(enforced
,
427 isl_basic_set_get_space(enforced_g
));
428 enforced
= isl_set_simple_hull(isl_basic_set_union(enforced
,
434 /* Extend the node at *body with node.
436 * If body points to the else branch, then *body may still be NULL.
437 * If so, we simply attach node to this else branch.
438 * Otherwise, we attach a list containing the statements already
439 * attached at *body followed by node.
441 static void extend_body(__isl_keep isl_ast_node
**body
,
442 __isl_take isl_ast_node
*node
)
444 isl_ast_node_list
*list
;
451 if ((*body
)->type
== isl_ast_node_block
) {
452 list
= isl_ast_node_block_get_children(*body
);
453 isl_ast_node_free(*body
);
455 list
= isl_ast_node_list_from_ast_node(*body
);
456 list
= isl_ast_node_list_add(list
, node
);
457 *body
= isl_ast_node_alloc_block(list
);
460 /* Merge "graft" into the last graft of "list".
461 * body points to the then or else branch of an if node in that last graft.
463 * We attach graft->node to this branch and update the enforced
464 * set of the last graft of "list" to take into account the enforced
467 static __isl_give isl_ast_graft_list
*graft_extend_body(
468 __isl_take isl_ast_graft_list
*list
,
469 __isl_keep isl_ast_node
**body
, __isl_take isl_ast_graft
*graft
,
470 __isl_keep isl_ast_build
*build
)
476 isl_basic_set
*enforced
;
478 n
= isl_ast_graft_list_n_ast_graft(list
);
481 extend_body(body
, isl_ast_node_copy(graft
->node
));
485 last
= isl_ast_graft_list_get_ast_graft(list
, n
- 1);
487 depth
= isl_ast_build_get_depth(build
);
488 space
= isl_ast_build_get_space(build
, 1);
489 enforced
= isl_basic_set_empty(space
);
490 enforced
= update_enforced(enforced
, last
, depth
);
491 enforced
= update_enforced(enforced
, graft
, depth
);
492 last
= isl_ast_graft_set_enforced(last
, enforced
);
494 list
= isl_ast_graft_list_set_ast_graft(list
, n
- 1, last
);
495 isl_ast_graft_free(graft
);
498 isl_ast_graft_free(graft
);
499 return isl_ast_graft_list_free(list
);
502 /* Merge "graft" into the last graft of "list", attaching graft->node
503 * to the then branch of "last_if".
505 static __isl_give isl_ast_graft_list
*extend_then(
506 __isl_take isl_ast_graft_list
*list
,
507 __isl_keep isl_ast_node
*last_if
, __isl_take isl_ast_graft
*graft
,
508 __isl_keep isl_ast_build
*build
)
510 return graft_extend_body(list
, &last_if
->u
.i
.then
, graft
, build
);
513 /* Merge "graft" into the last graft of "list", attaching graft->node
514 * to the else branch of "last_if".
516 static __isl_give isl_ast_graft_list
*extend_else(
517 __isl_take isl_ast_graft_list
*list
,
518 __isl_keep isl_ast_node
*last_if
, __isl_take isl_ast_graft
*graft
,
519 __isl_keep isl_ast_build
*build
)
521 return graft_extend_body(list
, &last_if
->u
.i
.else_node
, graft
, build
);
524 /* This data structure keeps track of an if node.
526 * "node" is the actual if-node
527 * "guard" is the original, non-simplified guard of the node
528 * "complement" is the complement of "guard" in the context of outer if nodes
536 /* Given a list of "n" if nodes, clear those starting at "first"
537 * and return "first" (i.e., the updated size of the array).
539 static int clear_if_nodes(struct isl_if_node
*if_node
, int first
, int n
)
543 for (i
= first
; i
< n
; ++i
) {
544 isl_set_free(if_node
[i
].guard
);
545 isl_set_free(if_node
[i
].complement
);
551 /* For each graft in "list",
552 * insert an if node around graft->node testing the condition encoded
553 * in graft->guard, assuming graft->guard involves any conditions.
555 * We keep track of a list of generated if nodes that can be extended
556 * without changing the order of the elements in "list".
557 * If the guard of a graft is a subset of either the guard or its complement
558 * of one of those if nodes, then the node
559 * of the new graft is inserted into the then or else branch of the last graft
560 * and the current graft is discarded.
561 * The guard of the node is then simplified based on the conditions
562 * enforced at that then or else branch.
563 * Otherwise, the current graft is appended to the list.
565 * We only construct else branches if allowed by the user.
567 static __isl_give isl_ast_graft_list
*insert_pending_guard_nodes(
568 __isl_take isl_ast_graft_list
*list
,
569 __isl_keep isl_ast_build
*build
)
575 isl_ast_graft_list
*res
;
576 struct isl_if_node
*if_node
= NULL
;
578 n
= isl_ast_graft_list_n_ast_graft(list
);
580 return isl_ast_graft_list_free(list
);
582 ctx
= isl_ast_build_get_ctx(build
);
584 allow_else
= isl_options_get_ast_build_allow_else(ctx
);
588 if_node
= isl_alloc_array(ctx
, struct isl_if_node
, n
- 1);
590 return isl_ast_graft_list_free(list
);
593 res
= isl_ast_graft_list_alloc(ctx
, n
);
595 for (i
= 0; i
< n
; ++i
) {
597 isl_ast_graft
*graft
;
598 int subset
, found_then
, found_else
;
601 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
605 found_then
= found_else
= -1;
608 test
= isl_set_copy(graft
->guard
);
609 test
= isl_set_intersect(test
,
610 isl_set_copy(build
->domain
));
611 for (j
= n_if
- 1; j
>= 0; --j
) {
612 subset
= isl_set_is_subset(test
,
614 if (subset
< 0 || subset
) {
620 subset
= isl_set_is_subset(test
,
621 if_node
[j
].complement
);
622 if (subset
< 0 || subset
) {
627 n_if
= clear_if_nodes(if_node
, j
+ 1, n_if
);
631 graft
= isl_ast_graft_free(graft
);
635 guard
= isl_set_copy(graft
->guard
);
637 graft
->guard
= isl_set_gist(graft
->guard
,
638 isl_set_copy(if_node
[found_then
].guard
));
639 else if (found_else
>= 0)
640 graft
->guard
= isl_set_gist(graft
->guard
,
641 isl_set_copy(if_node
[found_else
].complement
));
645 graft
= isl_ast_graft_free(graft
);
646 graft
= insert_pending_guard_node(graft
, build
);
647 if (graft
&& graft
->node
!= node
&& i
!= n
- 1) {
649 if_node
[n_if
].node
= graft
->node
;
650 if_node
[n_if
].guard
= guard
;
652 set
= if_node
[found_then
].guard
;
653 else if (found_else
>= 0)
654 set
= if_node
[found_else
].complement
;
657 set
= isl_set_copy(set
);
658 set
= isl_set_subtract(set
, isl_set_copy(guard
));
659 if_node
[n_if
].complement
= set
;
667 res
= extend_then(res
, if_node
[found_then
].node
,
669 else if (found_else
>= 0)
670 res
= extend_else(res
, if_node
[found_else
].node
,
673 res
= isl_ast_graft_list_add(res
, graft
);
676 res
= isl_ast_graft_list_free(res
);
678 isl_ast_graft_list_free(list
);
679 clear_if_nodes(if_node
, 0, n_if
);
684 /* For each graft in "list",
685 * insert an if node around graft->node testing the condition encoded
686 * in graft->guard, assuming graft->guard involves any conditions.
687 * Subsequently remove the guards from the grafts.
689 __isl_give isl_ast_graft_list
*isl_ast_graft_list_insert_pending_guard_nodes(
690 __isl_take isl_ast_graft_list
*list
, __isl_keep isl_ast_build
*build
)
696 list
= insert_pending_guard_nodes(list
, build
);
697 n
= isl_ast_graft_list_n_ast_graft(list
);
699 return isl_ast_graft_list_free(list
);
701 universe
= isl_set_universe(isl_ast_build_get_space(build
, 1));
702 for (i
= 0; i
< n
; ++i
) {
703 isl_ast_graft
*graft
;
705 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
708 isl_set_free(graft
->guard
);
709 graft
->guard
= isl_set_copy(universe
);
711 graft
= isl_ast_graft_free(graft
);
712 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
714 isl_set_free(universe
);
716 return isl_ast_graft_list_free(list
);
721 /* Collect the nodes contained in the grafts in "list" in a node list.
723 static __isl_give isl_ast_node_list
*extract_node_list(
724 __isl_keep isl_ast_graft_list
*list
)
729 isl_ast_node_list
*node_list
;
731 n
= isl_ast_graft_list_n_ast_graft(list
);
734 ctx
= isl_ast_graft_list_get_ctx(list
);
735 node_list
= isl_ast_node_list_alloc(ctx
, n
);
736 for (i
= 0; i
< n
; ++i
) {
738 isl_ast_graft
*graft
;
740 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
741 node
= isl_ast_graft_get_node(graft
);
742 node_list
= isl_ast_node_list_add(node_list
, node
);
743 isl_ast_graft_free(graft
);
749 /* Look for shared enforced constraints by all the elements in "list"
750 * on outer loops (with respect to the current depth) and return the result.
752 * If there are no elements in "list", then return the empty set.
754 __isl_give isl_basic_set
*isl_ast_graft_list_extract_shared_enforced(
755 __isl_keep isl_ast_graft_list
*list
,
756 __isl_keep isl_ast_build
*build
)
762 isl_basic_set
*enforced
;
764 n
= isl_ast_graft_list_n_ast_graft(list
);
768 space
= isl_ast_build_get_space(build
, 1);
769 enforced
= isl_basic_set_empty(space
);
771 depth
= isl_ast_build_get_depth(build
);
772 for (i
= 0; i
< n
; ++i
) {
773 isl_ast_graft
*graft
;
775 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
776 enforced
= update_enforced(enforced
, graft
, depth
);
777 isl_ast_graft_free(graft
);
783 /* Record "guard" in "graft" so that it will be enforced somewhere
784 * up the tree. If the graft already has a guard, then it may be partially
785 * redundant in combination with the new guard and in the context
786 * the generated constraints of "build". In fact, the new guard
787 * may in itself have some redundant constraints.
788 * We therefore (re)compute the gist of the intersection
789 * and coalesce the result.
791 static __isl_give isl_ast_graft
*store_guard(__isl_take isl_ast_graft
*graft
,
792 __isl_take isl_set
*guard
, __isl_keep isl_ast_build
*build
)
799 is_universe
= isl_set_plain_is_universe(guard
);
807 graft
->guard
= isl_set_intersect(graft
->guard
, guard
);
808 graft
->guard
= isl_set_gist(graft
->guard
,
809 isl_ast_build_get_generated(build
));
810 graft
->guard
= isl_set_coalesce(graft
->guard
);
812 return isl_ast_graft_free(graft
);
817 return isl_ast_graft_free(graft
);
820 /* For each graft in "list", replace its guard with the gist with
821 * respect to "context".
823 static __isl_give isl_ast_graft_list
*gist_guards(
824 __isl_take isl_ast_graft_list
*list
, __isl_keep isl_set
*context
)
829 n
= isl_ast_graft_list_n_ast_graft(list
);
831 return isl_ast_graft_list_free(list
);
833 for (i
= 0; i
< n
; ++i
) {
834 isl_ast_graft
*graft
;
836 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
839 graft
->guard
= isl_set_gist(graft
->guard
,
840 isl_set_copy(context
));
842 graft
= isl_ast_graft_free(graft
);
843 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
846 return isl_ast_graft_list_free(list
);
851 /* For each graft in "list", replace its guard with the gist with
852 * respect to "context".
854 __isl_give isl_ast_graft_list
*isl_ast_graft_list_gist_guards(
855 __isl_take isl_ast_graft_list
*list
, __isl_take isl_set
*context
)
857 list
= gist_guards(list
, context
);
858 isl_set_free(context
);
863 /* Allocate a graft in "build" based on the list of grafts in "sub_build".
864 * "guard" and "enforced" are the guard and enforced constraints
865 * of the allocated graft. The guard is used to simplify the guards
866 * of the elements in "list".
868 * The node is initialized to either a block containing the nodes of "children"
869 * or, if there is only a single child, the node of that child.
870 * If the current level requires a for node, it should be inserted by
871 * a subsequent call to isl_ast_graft_insert_for.
873 __isl_give isl_ast_graft
*isl_ast_graft_alloc_from_children(
874 __isl_take isl_ast_graft_list
*list
, __isl_take isl_set
*guard
,
875 __isl_take isl_basic_set
*enforced
, __isl_keep isl_ast_build
*build
,
876 __isl_keep isl_ast_build
*sub_build
)
878 isl_ast_build
*guard_build
;
880 isl_ast_node_list
*node_list
;
881 isl_ast_graft
*graft
;
883 guard_build
= isl_ast_build_copy(sub_build
);
884 guard_build
= isl_ast_build_replace_pending_by_guard(guard_build
,
885 isl_set_copy(guard
));
886 list
= gist_guards(list
, guard
);
887 list
= insert_pending_guard_nodes(list
, guard_build
);
888 isl_ast_build_free(guard_build
);
890 node_list
= extract_node_list(list
);
891 node
= isl_ast_node_from_ast_node_list(node_list
);
892 isl_ast_graft_list_free(list
);
894 graft
= isl_ast_graft_alloc(node
, build
);
895 graft
= store_guard(graft
, guard
, build
);
896 graft
= isl_ast_graft_enforce(graft
, enforced
);
901 /* Combine the grafts in the list into a single graft.
903 * The guard is initialized to the shared guard of the list elements (if any),
904 * provided it does not depend on the current dimension.
905 * The guards in the elements are then simplified with respect to the
906 * hoisted guard and materialized as if nodes around the contained AST nodes
907 * in the context of "sub_build".
909 * The enforced set is initialized to the simple hull of the enforced sets
910 * of the elements, provided the ast_build_exploit_nested_bounds option is set
911 * or the new graft will be used at the same level.
913 * The node is initialized to either a block containing the nodes of "list"
914 * or, if there is only a single element, the node of that element.
916 static __isl_give isl_ast_graft
*ast_graft_list_fuse(
917 __isl_take isl_ast_graft_list
*list
, __isl_keep isl_ast_build
*build
)
919 isl_ast_graft
*graft
;
920 isl_basic_set
*enforced
;
926 enforced
= isl_ast_graft_list_extract_shared_enforced(list
, build
);
927 guard
= isl_ast_graft_list_extract_hoistable_guard(list
, build
);
928 graft
= isl_ast_graft_alloc_from_children(list
, guard
, enforced
,
934 /* Combine the grafts in the list into a single graft.
935 * Return a list containing this single graft.
936 * If the original list is empty, then return an empty list.
938 __isl_give isl_ast_graft_list
*isl_ast_graft_list_fuse(
939 __isl_take isl_ast_graft_list
*list
,
940 __isl_keep isl_ast_build
*build
)
943 isl_ast_graft
*graft
;
945 n
= isl_ast_graft_list_n_ast_graft(list
);
947 return isl_ast_graft_list_free(list
);
950 graft
= ast_graft_list_fuse(list
, build
);
951 return isl_ast_graft_list_from_ast_graft(graft
);
954 /* Combine the two grafts into a single graft.
955 * Return a list containing this single graft.
957 static __isl_give isl_ast_graft
*isl_ast_graft_fuse(
958 __isl_take isl_ast_graft
*graft1
, __isl_take isl_ast_graft
*graft2
,
959 __isl_keep isl_ast_build
*build
)
962 isl_ast_graft_list
*list
;
964 ctx
= isl_ast_build_get_ctx(build
);
966 list
= isl_ast_graft_list_alloc(ctx
, 2);
967 list
= isl_ast_graft_list_add(list
, graft1
);
968 list
= isl_ast_graft_list_add(list
, graft2
);
970 return ast_graft_list_fuse(list
, build
);
973 /* Insert a for node enclosing the current graft->node.
975 __isl_give isl_ast_graft
*isl_ast_graft_insert_for(
976 __isl_take isl_ast_graft
*graft
, __isl_take isl_ast_node
*node
)
981 graft
->node
= isl_ast_node_for_set_body(node
, graft
->node
);
983 return isl_ast_graft_free(graft
);
987 isl_ast_node_free(node
);
988 isl_ast_graft_free(graft
);
992 /* Insert a mark governing the current graft->node.
994 __isl_give isl_ast_graft
*isl_ast_graft_insert_mark(
995 __isl_take isl_ast_graft
*graft
, __isl_take isl_id
*mark
)
1000 graft
->node
= isl_ast_node_alloc_mark(mark
, graft
->node
);
1002 return isl_ast_graft_free(graft
);
1007 isl_ast_graft_free(graft
);
1011 /* Represent the graft list as an AST node.
1012 * This operation drops the information about guards in the grafts, so
1013 * if there are any pending guards, then they are materialized as if nodes.
1015 __isl_give isl_ast_node
*isl_ast_node_from_graft_list(
1016 __isl_take isl_ast_graft_list
*list
,
1017 __isl_keep isl_ast_build
*build
)
1019 isl_ast_node_list
*node_list
;
1021 list
= insert_pending_guard_nodes(list
, build
);
1022 node_list
= extract_node_list(list
);
1023 isl_ast_graft_list_free(list
);
1025 return isl_ast_node_from_ast_node_list(node_list
);
1028 __isl_null isl_ast_graft
*isl_ast_graft_free(__isl_take isl_ast_graft
*graft
)
1033 if (--graft
->ref
> 0)
1036 isl_ast_node_free(graft
->node
);
1037 isl_set_free(graft
->guard
);
1038 isl_basic_set_free(graft
->enforced
);
1044 /* Record that the grafted tree enforces
1045 * "enforced" by intersecting graft->enforced with "enforced".
1047 __isl_give isl_ast_graft
*isl_ast_graft_enforce(
1048 __isl_take isl_ast_graft
*graft
, __isl_take isl_basic_set
*enforced
)
1050 if (!graft
|| !enforced
)
1053 enforced
= isl_basic_set_align_params(enforced
,
1054 isl_basic_set_get_space(graft
->enforced
));
1055 graft
->enforced
= isl_basic_set_align_params(graft
->enforced
,
1056 isl_basic_set_get_space(enforced
));
1057 graft
->enforced
= isl_basic_set_intersect(graft
->enforced
, enforced
);
1058 if (!graft
->enforced
)
1059 return isl_ast_graft_free(graft
);
1063 isl_basic_set_free(enforced
);
1064 return isl_ast_graft_free(graft
);
1067 __isl_give isl_basic_set
*isl_ast_graft_get_enforced(
1068 __isl_keep isl_ast_graft
*graft
)
1070 return graft
? isl_basic_set_copy(graft
->enforced
) : NULL
;
1073 __isl_give isl_set
*isl_ast_graft_get_guard(__isl_keep isl_ast_graft
*graft
)
1075 return graft
? isl_set_copy(graft
->guard
) : NULL
;
1078 /* Record that "guard" needs to be inserted in "graft".
1080 __isl_give isl_ast_graft
*isl_ast_graft_add_guard(
1081 __isl_take isl_ast_graft
*graft
,
1082 __isl_take isl_set
*guard
, __isl_keep isl_ast_build
*build
)
1084 return store_guard(graft
, guard
, build
);
1087 /* Reformulate the "graft", which was generated in the context
1088 * of an inner code generation, in terms of the outer code generation
1091 * If "product" is set, then the domain of the inner code generation build is
1095 * with O the domain of the outer code generation build.
1096 * We essentially need to project out S.
1098 * If "product" is not set, then we need to project the domains onto
1099 * their parameter spaces.
1101 __isl_give isl_ast_graft
*isl_ast_graft_unembed(__isl_take isl_ast_graft
*graft
,
1104 isl_basic_set
*enforced
;
1110 enforced
= graft
->enforced
;
1111 enforced
= isl_basic_map_domain(isl_basic_set_unwrap(enforced
));
1112 graft
->enforced
= enforced
;
1113 graft
->guard
= isl_map_domain(isl_set_unwrap(graft
->guard
));
1115 graft
->enforced
= isl_basic_set_params(graft
->enforced
);
1116 graft
->guard
= isl_set_params(graft
->guard
);
1118 graft
->guard
= isl_set_compute_divs(graft
->guard
);
1120 if (!graft
->enforced
|| !graft
->guard
)
1121 return isl_ast_graft_free(graft
);
1126 /* Reformulate the grafts in "list", which were generated in the context
1127 * of an inner code generation, in terms of the outer code generation
1130 __isl_give isl_ast_graft_list
*isl_ast_graft_list_unembed(
1131 __isl_take isl_ast_graft_list
*list
, int product
)
1136 n
= isl_ast_graft_list_n_ast_graft(list
);
1138 return isl_ast_graft_list_free(list
);
1139 for (i
= 0; i
< n
; ++i
) {
1140 isl_ast_graft
*graft
;
1142 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
1143 graft
= isl_ast_graft_unembed(graft
, product
);
1144 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
1150 /* Compute the preimage of "graft" under the function represented by "ma".
1151 * In other words, plug in "ma" in "enforced" and "guard" fields of "graft".
1153 __isl_give isl_ast_graft
*isl_ast_graft_preimage_multi_aff(
1154 __isl_take isl_ast_graft
*graft
, __isl_take isl_multi_aff
*ma
)
1156 isl_basic_set
*enforced
;
1161 enforced
= graft
->enforced
;
1162 graft
->enforced
= isl_basic_set_preimage_multi_aff(enforced
,
1163 isl_multi_aff_copy(ma
));
1164 graft
->guard
= isl_set_preimage_multi_aff(graft
->guard
, ma
);
1166 if (!graft
->enforced
|| !graft
->guard
)
1167 return isl_ast_graft_free(graft
);
1172 /* Compute the preimage of all the grafts in "list" under
1173 * the function represented by "ma".
1175 __isl_give isl_ast_graft_list
*isl_ast_graft_list_preimage_multi_aff(
1176 __isl_take isl_ast_graft_list
*list
, __isl_take isl_multi_aff
*ma
)
1181 n
= isl_ast_graft_list_n_ast_graft(list
);
1183 list
= isl_ast_graft_list_free(list
);
1184 for (i
= 0; i
< n
; ++i
) {
1185 isl_ast_graft
*graft
;
1187 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
1188 graft
= isl_ast_graft_preimage_multi_aff(graft
,
1189 isl_multi_aff_copy(ma
));
1190 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
1193 isl_multi_aff_free(ma
);
1197 /* Compare two grafts based on their guards.
1199 static int cmp_graft(__isl_keep isl_ast_graft
*a
, __isl_keep isl_ast_graft
*b
,
1202 return isl_set_plain_cmp(a
->guard
, b
->guard
);
1205 /* Order the elements in "list" based on their guards.
1207 __isl_give isl_ast_graft_list
*isl_ast_graft_list_sort_guard(
1208 __isl_take isl_ast_graft_list
*list
)
1210 return isl_ast_graft_list_sort(list
, &cmp_graft
, NULL
);
1213 /* Merge the given two lists into a single list of grafts,
1214 * merging grafts with the same guard into a single graft.
1216 * "list2" has been sorted using isl_ast_graft_list_sort.
1217 * "list1" may be the result of a previous call to isl_ast_graft_list_merge
1218 * and may therefore not be completely sorted.
1220 * The elements in "list2" need to be executed after those in "list1",
1221 * but if the guard of a graft in "list2" is disjoint from the guards
1222 * of some final elements in "list1", then it can be moved up to before
1223 * those final elements.
1225 * In particular, we look at each element g of "list2" in turn
1226 * and move it up beyond elements of "list1" that would be sorted
1227 * after g as long as each of these elements has a guard that is disjoint
1230 * We do not allow the second or any later element of "list2" to be moved
1231 * before a previous elements of "list2" even if the reason that
1232 * that element didn't move up further was that its guard was not disjoint
1233 * from that of the previous element in "list1".
1235 __isl_give isl_ast_graft_list
*isl_ast_graft_list_merge(
1236 __isl_take isl_ast_graft_list
*list1
,
1237 __isl_take isl_ast_graft_list
*list2
,
1238 __isl_keep isl_ast_build
*build
)
1242 if (!list1
|| !list2
|| !build
)
1244 if (list2
->n
== 0) {
1245 isl_ast_graft_list_free(list2
);
1248 if (list1
->n
== 0) {
1249 isl_ast_graft_list_free(list1
);
1254 for (i
= 0; i
< list2
->n
; ++i
) {
1255 isl_ast_graft
*graft
;
1256 graft
= isl_ast_graft_list_get_ast_graft(list2
, i
);
1260 for (j
= list1
->n
; j
>= 0; --j
) {
1262 isl_ast_graft
*graft_j
;
1267 cmp
= isl_set_plain_cmp(list1
->p
[j
- 1]->guard
,
1270 disjoint
= isl_set_is_disjoint(graft
->guard
,
1271 list1
->p
[j
- 1]->guard
);
1273 isl_ast_graft_free(graft
);
1274 list1
= isl_ast_graft_list_free(list1
);
1283 list1
= isl_ast_graft_list_insert(list1
, j
,
1290 graft_j
= isl_ast_graft_list_get_ast_graft(list1
, j
);
1291 graft_j
= isl_ast_graft_fuse(graft_j
, graft
, build
);
1292 list1
= isl_ast_graft_list_set_ast_graft(list1
, j
,
1298 isl_ast_graft_free(graft
);
1299 isl_die(isl_ast_build_get_ctx(build
),
1301 "element failed to get inserted", break);
1309 list1
= isl_ast_graft_list_free(list1
);
1310 isl_ast_graft_list_free(list2
);
1314 isl_ast_graft_list_free(list1
);
1315 isl_ast_graft_list_free(list2
);
1319 __isl_give isl_printer
*isl_printer_print_ast_graft(__isl_take isl_printer
*p
,
1320 __isl_keep isl_ast_graft
*graft
)
1325 return isl_printer_free(p
);
1327 p
= isl_printer_print_str(p
, "(");
1328 p
= isl_printer_print_str(p
, "guard: ");
1329 p
= isl_printer_print_set(p
, graft
->guard
);
1330 p
= isl_printer_print_str(p
, ", ");
1331 p
= isl_printer_print_str(p
, "enforced: ");
1332 p
= isl_printer_print_basic_set(p
, graft
->enforced
);
1333 p
= isl_printer_print_str(p
, ", ");
1334 p
= isl_printer_print_str(p
, "node: ");
1335 p
= isl_printer_print_ast_node(p
, graft
->node
);
1336 p
= isl_printer_print_str(p
, ")");