2 * Copyright 2012 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
4 * Copyright 2019 Cerebras Systems
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege,
9 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
10 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
11 * B.P. 105 - 78153 Le Chesnay, France
12 * and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA
16 #include <isl/space.h>
17 #include <isl_ast_private.h>
18 #include <isl_ast_build_expr.h>
19 #include <isl_ast_build_private.h>
20 #include <isl_ast_graft_private.h>
21 #include "isl_set_to_ast_graft_list.h"
23 static __isl_give isl_ast_graft
*isl_ast_graft_copy(
24 __isl_keep isl_ast_graft
*graft
);
27 #define EL_BASE ast_graft
29 #include <isl_list_templ.c>
32 #define BASE ast_graft
33 #include <print_templ.c>
35 isl_ctx
*isl_ast_graft_get_ctx(__isl_keep isl_ast_graft
*graft
)
39 return isl_basic_set_get_ctx(graft
->enforced
);
42 __isl_give isl_ast_node
*isl_ast_graft_get_node(
43 __isl_keep isl_ast_graft
*graft
)
45 return graft
? isl_ast_node_copy(graft
->node
) : NULL
;
48 /* Create a graft for "node" with no guards and no enforced conditions.
50 __isl_give isl_ast_graft
*isl_ast_graft_alloc(
51 __isl_take isl_ast_node
*node
, __isl_keep isl_ast_build
*build
)
60 ctx
= isl_ast_node_get_ctx(node
);
61 graft
= isl_calloc_type(ctx
, isl_ast_graft
);
65 space
= isl_ast_build_get_space(build
, 1);
69 graft
->guard
= isl_set_universe(isl_space_copy(space
));
70 graft
->enforced
= isl_basic_set_universe(space
);
72 if (!graft
->guard
|| !graft
->enforced
)
73 return isl_ast_graft_free(graft
);
77 isl_ast_node_free(node
);
81 /* Create a graft with no guards and no enforced conditions
82 * encapsulating a call to the domain element specified by "executed".
83 * "executed" is assumed to be single-valued.
85 __isl_give isl_ast_graft
*isl_ast_graft_alloc_domain(
86 __isl_take isl_map
*executed
, __isl_keep isl_ast_build
*build
)
90 node
= isl_ast_build_call_from_executed(build
, executed
);
92 return isl_ast_graft_alloc(node
, build
);
95 static __isl_give isl_ast_graft
*isl_ast_graft_copy(
96 __isl_keep isl_ast_graft
*graft
)
105 /* Do all the grafts in "list" have the same guard and is this guard
106 * independent of the current depth?
108 static isl_bool
equal_independent_guards(__isl_keep isl_ast_graft_list
*list
,
109 __isl_keep isl_ast_build
*build
)
115 isl_ast_graft
*graft_0
;
116 isl_bool equal
= isl_bool_true
;
119 n
= isl_ast_graft_list_n_ast_graft(list
);
120 depth
= isl_ast_build_get_depth(build
);
121 if (n
< 0 || depth
< 0)
122 return isl_bool_error
;
123 graft_0
= isl_ast_graft_list_get_ast_graft(list
, 0);
125 return isl_bool_error
;
127 dim
= isl_set_dim(graft_0
->guard
, isl_dim_set
);
129 skip
= isl_bool_error
;
130 else if (dim
<= depth
)
131 skip
= isl_bool_false
;
133 skip
= isl_set_involves_dims(graft_0
->guard
,
134 isl_dim_set
, depth
, 1);
135 if (skip
< 0 || skip
) {
136 isl_ast_graft_free(graft_0
);
137 return isl_bool_not(skip
);
140 for (i
= 1; i
< n
; ++i
) {
141 isl_ast_graft
*graft
;
142 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
144 equal
= isl_bool_error
;
146 equal
= isl_set_is_equal(graft_0
->guard
, graft
->guard
);
147 isl_ast_graft_free(graft
);
148 if (equal
< 0 || !equal
)
152 isl_ast_graft_free(graft_0
);
157 /* Hoist "guard" out of the current level (given by "build").
159 * In particular, eliminate the dimension corresponding to the current depth.
161 static __isl_give isl_set
*hoist_guard(__isl_take isl_set
*guard
,
162 __isl_keep isl_ast_build
*build
)
167 depth
= isl_ast_build_get_depth(build
);
168 dim
= isl_set_dim(guard
, isl_dim_set
);
169 if (depth
< 0 || dim
< 0)
170 return isl_set_free(guard
);
172 guard
= isl_set_remove_divs_involving_dims(guard
,
173 isl_dim_set
, depth
, 1);
174 guard
= isl_set_eliminate(guard
, isl_dim_set
, depth
, 1);
175 guard
= isl_set_compute_divs(guard
);
181 /* Extract a common guard from the grafts in "list" that can be hoisted
182 * out of the current level. If no such guard can be found, then return
185 * If all the grafts in the list have the same guard and if this guard
186 * is independent of the current level, then it can be hoisted out.
187 * If there is only one graft in the list and if its guard
188 * depends on the current level, then we eliminate this level and
191 * Otherwise, we return the unshifted simple hull of the guards.
192 * In order to be able to hoist as many constraints as possible,
193 * but at the same time avoid hoisting constraints that did not
194 * appear in the guards in the first place, we intersect the guards
195 * with all the information that is available (i.e., the domain
196 * from the build and the enforced constraints of the graft) and
197 * compute the unshifted hull of the result using only constraints
198 * from the original guards.
199 * In particular, intersecting the guards with other known information
200 * allows us to hoist guards that are only explicit is some of
201 * the grafts and implicit in the others.
203 * The special case for equal guards is needed in case those guards
204 * are non-convex. Taking the simple hull would remove information
205 * and would not allow for these guards to be hoisted completely.
207 __isl_give isl_set
*isl_ast_graft_list_extract_hoistable_guard(
208 __isl_keep isl_ast_graft_list
*list
, __isl_keep isl_ast_build
*build
)
215 isl_set_list
*set_list
;
221 n
= isl_ast_graft_list_n_ast_graft(list
);
225 return isl_set_universe(isl_ast_build_get_space(build
, 1));
227 equal
= equal_independent_guards(list
, build
);
231 if (equal
|| n
== 1) {
232 isl_ast_graft
*graft_0
;
234 graft_0
= isl_ast_graft_list_get_ast_graft(list
, 0);
237 guard
= isl_set_copy(graft_0
->guard
);
239 guard
= hoist_guard(guard
, build
);
240 isl_ast_graft_free(graft_0
);
244 ctx
= isl_ast_build_get_ctx(build
);
245 set_list
= isl_set_list_alloc(ctx
, n
);
246 guard
= isl_set_empty(isl_ast_build_get_space(build
, 1));
247 for (i
= 0; i
< n
; ++i
) {
248 isl_ast_graft
*graft
;
249 isl_basic_set
*enforced
;
252 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
253 enforced
= isl_ast_graft_get_enforced(graft
);
254 guard_i
= isl_set_copy(graft
->guard
);
255 isl_ast_graft_free(graft
);
256 set_list
= isl_set_list_add(set_list
, isl_set_copy(guard_i
));
257 guard_i
= isl_set_intersect(guard_i
,
258 isl_set_from_basic_set(enforced
));
259 guard_i
= isl_set_intersect(guard_i
,
260 isl_ast_build_get_domain(build
));
261 guard
= isl_set_union(guard
, guard_i
);
263 hull
= isl_set_unshifted_simple_hull_from_set_list(guard
, set_list
);
264 guard
= isl_set_from_basic_set(hull
);
265 return hoist_guard(guard
, build
);
268 /* Internal data structure used inside insert_if.
270 * list is the list of guarded nodes created by each call to insert_if.
271 * node is the original node that is guarded by insert_if.
272 * build is the build in which the AST is constructed.
274 struct isl_insert_if_data
{
275 isl_ast_node_list
*list
;
277 isl_ast_build
*build
;
280 static isl_stat
insert_if(__isl_take isl_basic_set
*bset
, void *user
);
282 /* Insert an if node around "node" testing the condition encoded
285 * If the user does not want any disjunctions in the if conditions
286 * and if "guard" does involve a disjunction, then we make the different
287 * disjuncts disjoint and insert an if node corresponding to each disjunct
288 * around a copy of "node". The result is then a block node containing
289 * this sequence of guarded copies of "node".
291 static __isl_give isl_ast_node
*ast_node_insert_if(
292 __isl_take isl_ast_node
*node
, __isl_take isl_set
*guard
,
293 __isl_keep isl_ast_build
*build
)
295 struct isl_insert_if_data data
;
299 n
= isl_set_n_basic_set(guard
);
302 ctx
= isl_ast_build_get_ctx(build
);
303 if (isl_options_get_ast_build_allow_or(ctx
) || n
<= 1) {
304 isl_ast_node
*if_node
;
307 expr
= isl_ast_build_expr_from_set_internal(build
, guard
);
309 if_node
= isl_ast_node_alloc_if(expr
);
310 return isl_ast_node_if_set_then(if_node
, node
);
313 guard
= isl_set_make_disjoint(guard
);
315 data
.list
= isl_ast_node_list_alloc(ctx
, 0);
318 if (isl_set_foreach_basic_set(guard
, &insert_if
, &data
) < 0)
319 data
.list
= isl_ast_node_list_free(data
.list
);
322 isl_ast_node_free(data
.node
);
323 return isl_ast_node_alloc_block(data
.list
);
326 isl_ast_node_free(node
);
330 /* Insert an if node around a copy of "data->node" testing the condition
331 * encoded in guard "bset" and add the result to data->list.
333 static isl_stat
insert_if(__isl_take isl_basic_set
*bset
, void *user
)
335 struct isl_insert_if_data
*data
= user
;
339 set
= isl_set_from_basic_set(bset
);
340 node
= isl_ast_node_copy(data
->node
);
341 node
= ast_node_insert_if(node
, set
, data
->build
);
342 data
->list
= isl_ast_node_list_add(data
->list
, node
);
347 /* Insert an if node around graft->node testing the condition encoded
348 * in guard "guard", assuming guard involves any conditions.
350 static __isl_give isl_ast_graft
*insert_if_node(
351 __isl_take isl_ast_graft
*graft
, __isl_take isl_set
*guard
,
352 __isl_keep isl_ast_build
*build
)
359 univ
= isl_set_plain_is_universe(guard
);
367 graft
->node
= ast_node_insert_if(graft
->node
, guard
, build
);
370 return isl_ast_graft_free(graft
);
375 return isl_ast_graft_free(graft
);
378 /* Insert an if node around graft->node testing the condition encoded
379 * in graft->guard, assuming graft->guard involves any conditions.
381 static __isl_give isl_ast_graft
*insert_pending_guard_node(
382 __isl_take isl_ast_graft
*graft
, __isl_keep isl_ast_build
*build
)
387 return insert_if_node(graft
, isl_set_copy(graft
->guard
), build
);
390 /* Replace graft->enforced by "enforced".
392 __isl_give isl_ast_graft
*isl_ast_graft_set_enforced(
393 __isl_take isl_ast_graft
*graft
, __isl_take isl_basic_set
*enforced
)
395 if (!graft
|| !enforced
)
398 isl_basic_set_free(graft
->enforced
);
399 graft
->enforced
= enforced
;
403 isl_basic_set_free(enforced
);
404 return isl_ast_graft_free(graft
);
407 /* Update "enforced" such that it only involves constraints that are
408 * also enforced by "graft".
410 static __isl_give isl_basic_set
*update_enforced(
411 __isl_take isl_basic_set
*enforced
, __isl_keep isl_ast_graft
*graft
,
415 isl_basic_set
*enforced_g
;
417 enforced_g
= isl_ast_graft_get_enforced(graft
);
418 dim
= isl_basic_set_dim(enforced_g
, isl_dim_set
);
420 enforced_g
= isl_basic_set_free(enforced_g
);
422 enforced_g
= isl_basic_set_eliminate(enforced_g
,
423 isl_dim_set
, depth
, 1);
424 enforced_g
= isl_basic_set_remove_unknown_divs(enforced_g
);
425 enforced_g
= isl_basic_set_align_params(enforced_g
,
426 isl_basic_set_get_space(enforced
));
427 enforced
= isl_basic_set_align_params(enforced
,
428 isl_basic_set_get_space(enforced_g
));
429 enforced
= isl_set_simple_hull(isl_basic_set_union(enforced
,
435 /* Extend the node at *body with node.
437 * If body points to the else branch, then *body may still be NULL.
438 * If so, we simply attach node to this else branch.
439 * Otherwise, we attach a list containing the statements already
440 * attached at *body followed by node.
442 static void extend_body(__isl_keep isl_ast_node
**body
,
443 __isl_take isl_ast_node
*node
)
445 isl_ast_node_list
*list
;
452 if ((*body
)->type
== isl_ast_node_block
) {
453 list
= isl_ast_node_block_get_children(*body
);
454 isl_ast_node_free(*body
);
456 list
= isl_ast_node_list_from_ast_node(*body
);
457 list
= isl_ast_node_list_add(list
, node
);
458 *body
= isl_ast_node_alloc_block(list
);
461 /* Merge "graft" into the last graft of "list".
462 * body points to the then or else branch of an if node in that last graft.
464 * We attach graft->node to this branch and update the enforced
465 * set of the last graft of "list" to take into account the enforced
468 static __isl_give isl_ast_graft_list
*graft_extend_body(
469 __isl_take isl_ast_graft_list
*list
,
470 __isl_keep isl_ast_node
**body
, __isl_take isl_ast_graft
*graft
,
471 __isl_keep isl_ast_build
*build
)
477 isl_basic_set
*enforced
;
479 n
= isl_ast_graft_list_n_ast_graft(list
);
480 depth
= isl_ast_build_get_depth(build
);
481 if (n
< 0 || depth
< 0 || !graft
)
483 extend_body(body
, isl_ast_node_copy(graft
->node
));
487 last
= isl_ast_graft_list_get_ast_graft(list
, n
- 1);
489 space
= isl_ast_build_get_space(build
, 1);
490 enforced
= isl_basic_set_empty(space
);
491 enforced
= update_enforced(enforced
, last
, depth
);
492 enforced
= update_enforced(enforced
, graft
, depth
);
493 last
= isl_ast_graft_set_enforced(last
, enforced
);
495 list
= isl_ast_graft_list_set_ast_graft(list
, n
- 1, last
);
496 isl_ast_graft_free(graft
);
499 isl_ast_graft_free(graft
);
500 return isl_ast_graft_list_free(list
);
503 /* Merge "graft" into the last graft of "list", attaching graft->node
504 * to the then branch of "last_if".
506 static __isl_give isl_ast_graft_list
*extend_then(
507 __isl_take isl_ast_graft_list
*list
,
508 __isl_keep isl_ast_node
*last_if
, __isl_take isl_ast_graft
*graft
,
509 __isl_keep isl_ast_build
*build
)
511 return graft_extend_body(list
, &last_if
->u
.i
.then
, graft
, build
);
514 /* Merge "graft" into the last graft of "list", attaching graft->node
515 * to the else branch of "last_if".
517 static __isl_give isl_ast_graft_list
*extend_else(
518 __isl_take isl_ast_graft_list
*list
,
519 __isl_keep isl_ast_node
*last_if
, __isl_take isl_ast_graft
*graft
,
520 __isl_keep isl_ast_build
*build
)
522 return graft_extend_body(list
, &last_if
->u
.i
.else_node
, graft
, build
);
525 /* This data structure keeps track of an if node.
527 * "node" is the actual if-node
528 * "guard" is the original, non-simplified guard of the node
529 * "complement" is the complement of "guard" in the context of outer if nodes
537 /* Given a list of "n" if nodes, clear those starting at "first"
538 * and return "first" (i.e., the updated size of the array).
540 static int clear_if_nodes(struct isl_if_node
*if_node
, int first
, int n
)
544 for (i
= first
; i
< n
; ++i
) {
545 isl_set_free(if_node
[i
].guard
);
546 isl_set_free(if_node
[i
].complement
);
552 /* For each graft in "list",
553 * insert an if node around graft->node testing the condition encoded
554 * in graft->guard, assuming graft->guard involves any conditions.
556 * We keep track of a list of generated if nodes that can be extended
557 * without changing the order of the elements in "list".
558 * If the guard of a graft is a subset of either the guard or its complement
559 * of one of those if nodes, then the node
560 * of the new graft is inserted into the then or else branch of the last graft
561 * and the current graft is discarded.
562 * The guard of the node is then simplified based on the conditions
563 * enforced at that then or else branch.
564 * Otherwise, the current graft is appended to the list.
566 * We only construct else branches if allowed by the user.
568 static __isl_give isl_ast_graft_list
*insert_pending_guard_nodes(
569 __isl_take isl_ast_graft_list
*list
,
570 __isl_keep isl_ast_build
*build
)
576 isl_ast_graft_list
*res
;
577 struct isl_if_node
*if_node
= NULL
;
579 n
= isl_ast_graft_list_n_ast_graft(list
);
581 return isl_ast_graft_list_free(list
);
583 ctx
= isl_ast_build_get_ctx(build
);
585 allow_else
= isl_options_get_ast_build_allow_else(ctx
);
589 if_node
= isl_alloc_array(ctx
, struct isl_if_node
, n
- 1);
591 return isl_ast_graft_list_free(list
);
594 res
= isl_ast_graft_list_alloc(ctx
, n
);
596 for (i
= 0; i
< n
; ++i
) {
598 isl_ast_graft
*graft
;
599 int subset
, found_then
, found_else
;
602 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
606 found_then
= found_else
= -1;
609 test
= isl_set_copy(graft
->guard
);
610 test
= isl_set_intersect(test
,
611 isl_set_copy(build
->domain
));
612 for (j
= n_if
- 1; j
>= 0; --j
) {
613 subset
= isl_set_is_subset(test
,
615 if (subset
< 0 || subset
) {
621 subset
= isl_set_is_subset(test
,
622 if_node
[j
].complement
);
623 if (subset
< 0 || subset
) {
628 n_if
= clear_if_nodes(if_node
, j
+ 1, n_if
);
632 graft
= isl_ast_graft_free(graft
);
636 guard
= isl_set_copy(graft
->guard
);
638 graft
->guard
= isl_set_gist(graft
->guard
,
639 isl_set_copy(if_node
[found_then
].guard
));
640 else if (found_else
>= 0)
641 graft
->guard
= isl_set_gist(graft
->guard
,
642 isl_set_copy(if_node
[found_else
].complement
));
646 graft
= isl_ast_graft_free(graft
);
647 graft
= insert_pending_guard_node(graft
, build
);
648 if (graft
&& graft
->node
!= node
&& i
!= n
- 1) {
650 if_node
[n_if
].node
= graft
->node
;
651 if_node
[n_if
].guard
= guard
;
653 set
= if_node
[found_then
].guard
;
654 else if (found_else
>= 0)
655 set
= if_node
[found_else
].complement
;
658 set
= isl_set_copy(set
);
659 set
= isl_set_subtract(set
, isl_set_copy(guard
));
660 if_node
[n_if
].complement
= set
;
668 res
= extend_then(res
, if_node
[found_then
].node
,
670 else if (found_else
>= 0)
671 res
= extend_else(res
, if_node
[found_else
].node
,
674 res
= isl_ast_graft_list_add(res
, graft
);
677 res
= isl_ast_graft_list_free(res
);
679 isl_ast_graft_list_free(list
);
680 clear_if_nodes(if_node
, 0, n_if
);
685 /* For each graft in "list",
686 * insert an if node around graft->node testing the condition encoded
687 * in graft->guard, assuming graft->guard involves any conditions.
688 * Subsequently remove the guards from the grafts.
690 __isl_give isl_ast_graft_list
*isl_ast_graft_list_insert_pending_guard_nodes(
691 __isl_take isl_ast_graft_list
*list
, __isl_keep isl_ast_build
*build
)
697 list
= insert_pending_guard_nodes(list
, build
);
698 n
= isl_ast_graft_list_n_ast_graft(list
);
700 return isl_ast_graft_list_free(list
);
702 universe
= isl_set_universe(isl_ast_build_get_space(build
, 1));
703 for (i
= 0; i
< n
; ++i
) {
704 isl_ast_graft
*graft
;
706 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
709 isl_set_free(graft
->guard
);
710 graft
->guard
= isl_set_copy(universe
);
712 graft
= isl_ast_graft_free(graft
);
713 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
715 isl_set_free(universe
);
717 return isl_ast_graft_list_free(list
);
722 /* Collect the nodes contained in the grafts in "list" in a node list.
724 static __isl_give isl_ast_node_list
*extract_node_list(
725 __isl_keep isl_ast_graft_list
*list
)
730 isl_ast_node_list
*node_list
;
732 n
= isl_ast_graft_list_n_ast_graft(list
);
735 ctx
= isl_ast_graft_list_get_ctx(list
);
736 node_list
= isl_ast_node_list_alloc(ctx
, n
);
737 for (i
= 0; i
< n
; ++i
) {
739 isl_ast_graft
*graft
;
741 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
742 node
= isl_ast_graft_get_node(graft
);
743 node_list
= isl_ast_node_list_add(node_list
, node
);
744 isl_ast_graft_free(graft
);
750 /* Look for shared enforced constraints by all the elements in "list"
751 * on outer loops (with respect to the current depth) and return the result.
753 * If there are no elements in "list", then return the empty set.
755 __isl_give isl_basic_set
*isl_ast_graft_list_extract_shared_enforced(
756 __isl_keep isl_ast_graft_list
*list
,
757 __isl_keep isl_ast_build
*build
)
763 isl_basic_set
*enforced
;
765 n
= isl_ast_graft_list_n_ast_graft(list
);
766 depth
= isl_ast_build_get_depth(build
);
767 if (n
< 0 || depth
< 0)
770 space
= isl_ast_build_get_space(build
, 1);
771 enforced
= isl_basic_set_empty(space
);
773 for (i
= 0; i
< n
; ++i
) {
774 isl_ast_graft
*graft
;
776 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
777 enforced
= update_enforced(enforced
, graft
, depth
);
778 isl_ast_graft_free(graft
);
784 /* Record "guard" in "graft" so that it will be enforced somewhere
785 * up the tree. If the graft already has a guard, then it may be partially
786 * redundant in combination with the new guard and in the context
787 * the generated constraints of "build". In fact, the new guard
788 * may in itself have some redundant constraints.
789 * We therefore (re)compute the gist of the intersection
790 * and coalesce the result.
792 static __isl_give isl_ast_graft
*store_guard(__isl_take isl_ast_graft
*graft
,
793 __isl_take isl_set
*guard
, __isl_keep isl_ast_build
*build
)
800 is_universe
= isl_set_plain_is_universe(guard
);
808 graft
->guard
= isl_set_intersect(graft
->guard
, guard
);
809 graft
->guard
= isl_set_gist(graft
->guard
,
810 isl_ast_build_get_generated(build
));
811 graft
->guard
= isl_set_coalesce(graft
->guard
);
813 return isl_ast_graft_free(graft
);
818 return isl_ast_graft_free(graft
);
821 /* For each graft in "list", replace its guard with the gist with
822 * respect to "context".
824 static __isl_give isl_ast_graft_list
*gist_guards(
825 __isl_take isl_ast_graft_list
*list
, __isl_keep isl_set
*context
)
830 n
= isl_ast_graft_list_n_ast_graft(list
);
832 return isl_ast_graft_list_free(list
);
834 for (i
= 0; i
< n
; ++i
) {
835 isl_ast_graft
*graft
;
837 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
840 graft
->guard
= isl_set_gist(graft
->guard
,
841 isl_set_copy(context
));
843 graft
= isl_ast_graft_free(graft
);
844 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
847 return isl_ast_graft_list_free(list
);
852 /* For each graft in "list", replace its guard with the gist with
853 * respect to "context".
855 __isl_give isl_ast_graft_list
*isl_ast_graft_list_gist_guards(
856 __isl_take isl_ast_graft_list
*list
, __isl_take isl_set
*context
)
858 list
= gist_guards(list
, context
);
859 isl_set_free(context
);
864 /* Allocate a graft in "build" based on the list of grafts in "sub_build".
865 * "guard" and "enforced" are the guard and enforced constraints
866 * of the allocated graft. The guard is used to simplify the guards
867 * of the elements in "list".
869 * The node is initialized to either a block containing the nodes of "children"
870 * or, if there is only a single child, the node of that child.
871 * If the current level requires a for node, it should be inserted by
872 * a subsequent call to isl_ast_graft_insert_for.
874 __isl_give isl_ast_graft
*isl_ast_graft_alloc_from_children(
875 __isl_take isl_ast_graft_list
*list
, __isl_take isl_set
*guard
,
876 __isl_take isl_basic_set
*enforced
, __isl_keep isl_ast_build
*build
,
877 __isl_keep isl_ast_build
*sub_build
)
879 isl_ast_build
*guard_build
;
881 isl_ast_node_list
*node_list
;
882 isl_ast_graft
*graft
;
884 guard_build
= isl_ast_build_copy(sub_build
);
885 guard_build
= isl_ast_build_replace_pending_by_guard(guard_build
,
886 isl_set_copy(guard
));
887 list
= gist_guards(list
, guard
);
888 list
= insert_pending_guard_nodes(list
, guard_build
);
889 isl_ast_build_free(guard_build
);
891 node_list
= extract_node_list(list
);
892 node
= isl_ast_node_from_ast_node_list(node_list
);
893 isl_ast_graft_list_free(list
);
895 graft
= isl_ast_graft_alloc(node
, build
);
896 graft
= store_guard(graft
, guard
, build
);
897 graft
= isl_ast_graft_enforce(graft
, enforced
);
902 /* Combine the grafts in the list into a single graft.
904 * The guard is initialized to the shared guard of the list elements (if any),
905 * provided it does not depend on the current dimension.
906 * The guards in the elements are then simplified with respect to the
907 * hoisted guard and materialized as if nodes around the contained AST nodes
908 * in the context of "sub_build".
910 * The enforced set is initialized to the simple hull of the enforced sets
911 * of the elements, provided the ast_build_exploit_nested_bounds option is set
912 * or the new graft will be used at the same level.
914 * The node is initialized to either a block containing the nodes of "list"
915 * or, if there is only a single element, the node of that element.
917 static __isl_give isl_ast_graft
*ast_graft_list_fuse(
918 __isl_take isl_ast_graft_list
*list
, __isl_keep isl_ast_build
*build
)
920 isl_ast_graft
*graft
;
921 isl_basic_set
*enforced
;
927 enforced
= isl_ast_graft_list_extract_shared_enforced(list
, build
);
928 guard
= isl_ast_graft_list_extract_hoistable_guard(list
, build
);
929 graft
= isl_ast_graft_alloc_from_children(list
, guard
, enforced
,
935 /* Combine the grafts in the list into a single graft.
936 * Return a list containing this single graft.
937 * If the original list is empty, then return an empty list.
939 __isl_give isl_ast_graft_list
*isl_ast_graft_list_fuse(
940 __isl_take isl_ast_graft_list
*list
,
941 __isl_keep isl_ast_build
*build
)
944 isl_ast_graft
*graft
;
946 n
= isl_ast_graft_list_n_ast_graft(list
);
948 return isl_ast_graft_list_free(list
);
951 graft
= ast_graft_list_fuse(list
, build
);
952 return isl_ast_graft_list_from_ast_graft(graft
);
955 /* Combine the two grafts into a single graft.
956 * Return a list containing this single graft.
958 static __isl_give isl_ast_graft
*isl_ast_graft_fuse(
959 __isl_take isl_ast_graft
*graft1
, __isl_take isl_ast_graft
*graft2
,
960 __isl_keep isl_ast_build
*build
)
963 isl_ast_graft_list
*list
;
965 ctx
= isl_ast_build_get_ctx(build
);
967 list
= isl_ast_graft_list_alloc(ctx
, 2);
968 list
= isl_ast_graft_list_add(list
, graft1
);
969 list
= isl_ast_graft_list_add(list
, graft2
);
971 return ast_graft_list_fuse(list
, build
);
974 /* Insert a for node enclosing the current graft->node.
976 __isl_give isl_ast_graft
*isl_ast_graft_insert_for(
977 __isl_take isl_ast_graft
*graft
, __isl_take isl_ast_node
*node
)
982 graft
->node
= isl_ast_node_for_set_body(node
, graft
->node
);
984 return isl_ast_graft_free(graft
);
988 isl_ast_node_free(node
);
989 isl_ast_graft_free(graft
);
993 /* Insert a mark governing the current graft->node.
995 __isl_give isl_ast_graft
*isl_ast_graft_insert_mark(
996 __isl_take isl_ast_graft
*graft
, __isl_take isl_id
*mark
)
1001 graft
->node
= isl_ast_node_alloc_mark(mark
, graft
->node
);
1003 return isl_ast_graft_free(graft
);
1008 isl_ast_graft_free(graft
);
1012 /* Represent the graft list as an AST node.
1013 * This operation drops the information about guards in the grafts, so
1014 * if there are any pending guards, then they are materialized as if nodes.
1016 __isl_give isl_ast_node
*isl_ast_node_from_graft_list(
1017 __isl_take isl_ast_graft_list
*list
,
1018 __isl_keep isl_ast_build
*build
)
1020 isl_ast_node_list
*node_list
;
1022 list
= insert_pending_guard_nodes(list
, build
);
1023 node_list
= extract_node_list(list
);
1024 isl_ast_graft_list_free(list
);
1026 return isl_ast_node_from_ast_node_list(node_list
);
1029 __isl_null isl_ast_graft
*isl_ast_graft_free(__isl_take isl_ast_graft
*graft
)
1034 if (--graft
->ref
> 0)
1037 isl_ast_node_free(graft
->node
);
1038 isl_set_free(graft
->guard
);
1039 isl_basic_set_free(graft
->enforced
);
1045 /* Record that the grafted tree enforces
1046 * "enforced" by intersecting graft->enforced with "enforced".
1048 __isl_give isl_ast_graft
*isl_ast_graft_enforce(
1049 __isl_take isl_ast_graft
*graft
, __isl_take isl_basic_set
*enforced
)
1051 if (!graft
|| !enforced
)
1054 enforced
= isl_basic_set_align_params(enforced
,
1055 isl_basic_set_get_space(graft
->enforced
));
1056 graft
->enforced
= isl_basic_set_align_params(graft
->enforced
,
1057 isl_basic_set_get_space(enforced
));
1058 graft
->enforced
= isl_basic_set_intersect(graft
->enforced
, enforced
);
1059 if (!graft
->enforced
)
1060 return isl_ast_graft_free(graft
);
1064 isl_basic_set_free(enforced
);
1065 return isl_ast_graft_free(graft
);
1068 __isl_give isl_basic_set
*isl_ast_graft_get_enforced(
1069 __isl_keep isl_ast_graft
*graft
)
1071 return graft
? isl_basic_set_copy(graft
->enforced
) : NULL
;
1074 __isl_give isl_set
*isl_ast_graft_get_guard(__isl_keep isl_ast_graft
*graft
)
1076 return graft
? isl_set_copy(graft
->guard
) : NULL
;
1079 /* Record that "guard" needs to be inserted in "graft".
1081 __isl_give isl_ast_graft
*isl_ast_graft_add_guard(
1082 __isl_take isl_ast_graft
*graft
,
1083 __isl_take isl_set
*guard
, __isl_keep isl_ast_build
*build
)
1085 return store_guard(graft
, guard
, build
);
1088 /* Reformulate the "graft", which was generated in the context
1089 * of an inner code generation, in terms of the outer code generation
1092 * If "product" is set, then the domain of the inner code generation build is
1096 * with O the domain of the outer code generation build.
1097 * We essentially need to project out S.
1099 * If "product" is not set, then we need to project the domains onto
1100 * their parameter spaces.
1102 __isl_give isl_ast_graft
*isl_ast_graft_unembed(__isl_take isl_ast_graft
*graft
,
1105 isl_basic_set
*enforced
;
1111 enforced
= graft
->enforced
;
1112 enforced
= isl_basic_map_domain(isl_basic_set_unwrap(enforced
));
1113 graft
->enforced
= enforced
;
1114 graft
->guard
= isl_map_domain(isl_set_unwrap(graft
->guard
));
1116 graft
->enforced
= isl_basic_set_params(graft
->enforced
);
1117 graft
->guard
= isl_set_params(graft
->guard
);
1119 graft
->guard
= isl_set_compute_divs(graft
->guard
);
1121 if (!graft
->enforced
|| !graft
->guard
)
1122 return isl_ast_graft_free(graft
);
1127 /* Reformulate the grafts in "list", which were generated in the context
1128 * of an inner code generation, in terms of the outer code generation
1131 __isl_give isl_ast_graft_list
*isl_ast_graft_list_unembed(
1132 __isl_take isl_ast_graft_list
*list
, int product
)
1137 n
= isl_ast_graft_list_n_ast_graft(list
);
1139 return isl_ast_graft_list_free(list
);
1140 for (i
= 0; i
< n
; ++i
) {
1141 isl_ast_graft
*graft
;
1143 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
1144 graft
= isl_ast_graft_unembed(graft
, product
);
1145 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
1151 /* Compute the preimage of "graft" under the function represented by "ma".
1152 * In other words, plug in "ma" in "enforced" and "guard" fields of "graft".
1154 __isl_give isl_ast_graft
*isl_ast_graft_preimage_multi_aff(
1155 __isl_take isl_ast_graft
*graft
, __isl_take isl_multi_aff
*ma
)
1157 isl_basic_set
*enforced
;
1162 enforced
= graft
->enforced
;
1163 graft
->enforced
= isl_basic_set_preimage_multi_aff(enforced
,
1164 isl_multi_aff_copy(ma
));
1165 graft
->guard
= isl_set_preimage_multi_aff(graft
->guard
, ma
);
1167 if (!graft
->enforced
|| !graft
->guard
)
1168 return isl_ast_graft_free(graft
);
1173 /* Compute the preimage of all the grafts in "list" under
1174 * the function represented by "ma".
1176 __isl_give isl_ast_graft_list
*isl_ast_graft_list_preimage_multi_aff(
1177 __isl_take isl_ast_graft_list
*list
, __isl_take isl_multi_aff
*ma
)
1182 n
= isl_ast_graft_list_n_ast_graft(list
);
1184 list
= isl_ast_graft_list_free(list
);
1185 for (i
= 0; i
< n
; ++i
) {
1186 isl_ast_graft
*graft
;
1188 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
1189 graft
= isl_ast_graft_preimage_multi_aff(graft
,
1190 isl_multi_aff_copy(ma
));
1191 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
1194 isl_multi_aff_free(ma
);
1198 /* Compare two grafts based on their guards.
1200 static int cmp_graft(__isl_keep isl_ast_graft
*a
, __isl_keep isl_ast_graft
*b
,
1203 return isl_set_plain_cmp(a
->guard
, b
->guard
);
1206 /* Order the elements in "list" based on their guards.
1208 __isl_give isl_ast_graft_list
*isl_ast_graft_list_sort_guard(
1209 __isl_take isl_ast_graft_list
*list
)
1211 return isl_ast_graft_list_sort(list
, &cmp_graft
, NULL
);
1214 /* Merge the given two lists into a single list of grafts,
1215 * merging grafts with the same guard into a single graft.
1217 * "list2" has been sorted using isl_ast_graft_list_sort.
1218 * "list1" may be the result of a previous call to isl_ast_graft_list_merge
1219 * and may therefore not be completely sorted.
1221 * The elements in "list2" need to be executed after those in "list1",
1222 * but if the guard of a graft in "list2" is disjoint from the guards
1223 * of some final elements in "list1", then it can be moved up to before
1224 * those final elements.
1226 * In particular, we look at each element g of "list2" in turn
1227 * and move it up beyond elements of "list1" that would be sorted
1228 * after g as long as each of these elements has a guard that is disjoint
1231 * We do not allow the second or any later element of "list2" to be moved
1232 * before a previous elements of "list2" even if the reason that
1233 * that element didn't move up further was that its guard was not disjoint
1234 * from that of the previous element in "list1".
1236 __isl_give isl_ast_graft_list
*isl_ast_graft_list_merge(
1237 __isl_take isl_ast_graft_list
*list1
,
1238 __isl_take isl_ast_graft_list
*list2
,
1239 __isl_keep isl_ast_build
*build
)
1243 if (!list1
|| !list2
|| !build
)
1245 if (list2
->n
== 0) {
1246 isl_ast_graft_list_free(list2
);
1249 if (list1
->n
== 0) {
1250 isl_ast_graft_list_free(list1
);
1255 for (i
= 0; i
< list2
->n
; ++i
) {
1256 isl_ast_graft
*graft
;
1257 graft
= isl_ast_graft_list_get_ast_graft(list2
, i
);
1261 for (j
= list1
->n
; j
>= 0; --j
) {
1263 isl_ast_graft
*graft_j
;
1268 cmp
= isl_set_plain_cmp(list1
->p
[j
- 1]->guard
,
1271 disjoint
= isl_set_is_disjoint(graft
->guard
,
1272 list1
->p
[j
- 1]->guard
);
1274 isl_ast_graft_free(graft
);
1275 list1
= isl_ast_graft_list_free(list1
);
1284 list1
= isl_ast_graft_list_insert(list1
, j
,
1291 graft_j
= isl_ast_graft_list_get_ast_graft(list1
, j
);
1292 graft_j
= isl_ast_graft_fuse(graft_j
, graft
, build
);
1293 list1
= isl_ast_graft_list_set_ast_graft(list1
, j
,
1299 isl_ast_graft_free(graft
);
1300 isl_die(isl_ast_build_get_ctx(build
),
1302 "element failed to get inserted", break);
1310 list1
= isl_ast_graft_list_free(list1
);
1311 isl_ast_graft_list_free(list2
);
1315 isl_ast_graft_list_free(list1
);
1316 isl_ast_graft_list_free(list2
);
1320 /* Internal data structure for split_on_guard.
1322 * "guard2list" is the constructed associative array.
1323 * "any_match" gets set if any guard was seen more than once.
1325 struct isl_split_on_guard_data
{
1326 isl_set_to_ast_graft_list
*guard2list
;
1330 /* Add "graft" to the list associated to its guard in data->guard2list.
1331 * If some other graft was already associated to this guard,
1332 * then set data->any_match.
1334 static isl_stat
add_to_guard_list(__isl_take isl_ast_graft
*graft
, void *user
)
1336 struct isl_split_on_guard_data
*data
= user
;
1338 isl_maybe_isl_ast_graft_list m
;
1341 return isl_stat_error
;
1342 m
= isl_set_to_ast_graft_list_try_get(data
->guard2list
, graft
->guard
);
1344 return isl_stat_non_null(isl_ast_graft_free(graft
));
1347 *data
->any_match
= 1;
1348 m
.value
= isl_ast_graft_list_add(m
.value
, graft
);
1350 m
.value
= isl_ast_graft_list_from_ast_graft(graft
);
1352 guard
= isl_set_copy(graft
->guard
);
1354 isl_set_to_ast_graft_list_set(data
->guard2list
, guard
, m
.value
);
1356 return isl_stat_non_null(data
->guard2list
);
1359 /* Construct an associative array that groups the elements
1360 * of "list" based on their guards.
1361 * If any guard appears more than once, then set "any_match".
1363 static __isl_give isl_set_to_ast_graft_list
*split_on_guard(
1364 __isl_keep isl_ast_graft_list
*list
, int *any_match
)
1366 struct isl_split_on_guard_data data
= { NULL
, any_match
};
1370 n
= isl_ast_graft_list_size(list
);
1374 ctx
= isl_ast_graft_list_get_ctx(list
);
1375 data
.guard2list
= isl_set_to_ast_graft_list_alloc(ctx
, n
);
1377 if (isl_ast_graft_list_foreach(list
, &add_to_guard_list
, &data
) < 0)
1378 return isl_set_to_ast_graft_list_free(data
.guard2list
);
1380 return data
.guard2list
;
1383 /* Add the elements of "guard_list" to "list".
1385 static isl_stat
add_same_guard(__isl_take isl_set
*guard
,
1386 __isl_take isl_ast_graft_list
*guard_list
, void *user
)
1388 isl_ast_graft_list
**list
= user
;
1390 isl_set_free(guard
);
1391 *list
= isl_ast_graft_list_concat(*list
, guard_list
);
1393 return isl_stat_non_null(*list
);
1396 /* Given an associative array "guard2list" containing the elements
1397 * of "list" grouped on common guards, reconstruct "list"
1398 * by placing elements with the same guard consecutively.
1400 static __isl_give isl_ast_graft_list
*reconstruct(
1401 __isl_take isl_ast_graft_list
*list
,
1402 __isl_keep isl_set_to_ast_graft_list
*guard2list
,
1403 __isl_keep isl_ast_build
*build
)
1405 list
= isl_ast_graft_list_clear(list
);
1406 if (isl_set_to_ast_graft_list_foreach(guard2list
,
1407 &add_same_guard
, &list
) < 0)
1408 list
= isl_ast_graft_list_free(list
);
1413 /* Group the grafts in "list" based on identical guards.
1415 * Note that there need to be a least three elements in the list
1416 * for the elements not to be grouped already.
1418 * Group the elements in an associative array based on their guards.
1419 * If any guard was seen more than once, then reconstruct the list
1420 * from the associative array. Otherwise, simply return the original list.
1422 __isl_give isl_ast_graft_list
*isl_ast_graft_list_group_on_guard(
1423 __isl_take isl_ast_graft_list
*list
, __isl_keep isl_ast_build
*build
)
1427 isl_set_to_ast_graft_list
*guard2list
;
1429 n
= isl_ast_graft_list_size(list
);
1431 return isl_ast_graft_list_free(list
);
1435 guard2list
= split_on_guard(list
, &any_match
);
1437 list
= reconstruct(list
, guard2list
, build
);
1439 isl_set_to_ast_graft_list_free(guard2list
);
1444 __isl_give isl_printer
*isl_printer_print_ast_graft(__isl_take isl_printer
*p
,
1445 __isl_keep isl_ast_graft
*graft
)
1450 return isl_printer_free(p
);
1452 p
= isl_printer_print_str(p
, "(");
1453 p
= isl_printer_print_str(p
, "guard: ");
1454 p
= isl_printer_print_set(p
, graft
->guard
);
1455 p
= isl_printer_print_str(p
, ", ");
1456 p
= isl_printer_print_str(p
, "enforced: ");
1457 p
= isl_printer_print_basic_set(p
, graft
->enforced
);
1458 p
= isl_printer_print_str(p
, ", ");
1459 p
= isl_printer_print_str(p
, "node: ");
1460 p
= isl_printer_print_ast_node(p
, graft
->node
);
1461 p
= isl_printer_print_str(p
, ")");