2 * Copyright 2012 Ecole Normale Superieure
4 * Use of this software is governed by the MIT license
6 * Written by Sven Verdoolaege,
7 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
10 #include <isl_list_private.h>
11 #include <isl_ast_private.h>
12 #include <isl_ast_build_expr.h>
13 #include <isl_ast_build_private.h>
14 #include <isl_ast_graft_private.h>
16 static __isl_give isl_ast_graft
*isl_ast_graft_copy(
17 __isl_keep isl_ast_graft
*graft
);
20 #define BASE ast_graft
22 #include <isl_list_templ.c>
25 #define BASE ast_graft
26 #include <print_templ.c>
28 isl_ctx
*isl_ast_graft_get_ctx(__isl_keep isl_ast_graft
*graft
)
32 return isl_basic_set_get_ctx(graft
->enforced
);
35 __isl_give isl_ast_node
*isl_ast_graft_get_node(
36 __isl_keep isl_ast_graft
*graft
)
38 return graft
? isl_ast_node_copy(graft
->node
) : NULL
;
41 /* Create a graft for "node" with no guards and no enforced conditions.
43 __isl_give isl_ast_graft
*isl_ast_graft_alloc(
44 __isl_take isl_ast_node
*node
, __isl_keep isl_ast_build
*build
)
53 ctx
= isl_ast_node_get_ctx(node
);
54 graft
= isl_calloc_type(ctx
, isl_ast_graft
);
58 space
= isl_ast_build_get_space(build
, 1);
62 graft
->guard
= isl_set_universe(isl_space_copy(space
));
63 graft
->enforced
= isl_basic_set_universe(space
);
65 if (!graft
->guard
|| !graft
->enforced
)
66 return isl_ast_graft_free(graft
);
70 isl_ast_node_free(node
);
74 /* Create a graft with no guards and no enforced conditions
75 * encapsulating a call to the domain element specified by "executed".
76 * "executed" is assumed to be single-valued.
78 __isl_give isl_ast_graft
*isl_ast_graft_alloc_domain(
79 __isl_take isl_map
*executed
, __isl_keep isl_ast_build
*build
)
83 node
= isl_ast_build_call_from_executed(build
, executed
);
85 return isl_ast_graft_alloc(node
, build
);
88 static __isl_give isl_ast_graft
*isl_ast_graft_copy(
89 __isl_keep isl_ast_graft
*graft
)
98 /* Do all the grafts in "list" have the same guard and is this guard
99 * independent of the current depth?
101 static int equal_independent_guards(__isl_keep isl_ast_graft_list
*list
,
102 __isl_keep isl_ast_build
*build
)
106 isl_ast_graft
*graft_0
;
110 graft_0
= isl_ast_graft_list_get_ast_graft(list
, 0);
114 depth
= isl_ast_build_get_depth(build
);
115 skip
= isl_set_involves_dims(graft_0
->guard
, isl_dim_set
, depth
, 1);
116 if (skip
< 0 || skip
) {
117 isl_ast_graft_free(graft_0
);
118 return skip
< 0 ? -1 : 0;
121 n
= isl_ast_graft_list_n_ast_graft(list
);
122 for (i
= 1; i
< n
; ++i
) {
123 isl_ast_graft
*graft
;
124 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
128 equal
= isl_set_is_equal(graft_0
->guard
, graft
->guard
);
129 isl_ast_graft_free(graft
);
130 if (equal
< 0 || !equal
)
134 isl_ast_graft_free(graft_0
);
139 /* Extract a common guard from the grafts in "list" that can be hoisted
140 * out of the current level. If no such guard can be found, then return
143 * If all the grafts in the list have the same guard and if this guard
144 * is independent of the current level, then it can be hoisted out.
145 * Otherwise, we return the unshifted simple hull of the guards.
147 * The special case for equal guards is needed in case those guards
148 * are non-convex. Taking the simple hull would remove information
149 * and would not allow for these guards to be hoisted completely.
151 static __isl_give isl_set
*extract_hoistable_guard(
152 __isl_keep isl_ast_graft_list
*list
, __isl_keep isl_ast_build
*build
)
156 isl_ast_graft
*graft_0
;
163 n
= isl_ast_graft_list_n_ast_graft(list
);
165 return isl_set_universe(isl_ast_build_get_space(build
, 1));
167 equal
= equal_independent_guards(list
, build
);
171 graft_0
= isl_ast_graft_list_get_ast_graft(list
, 0);
174 guard
= isl_set_copy(graft_0
->guard
);
175 isl_ast_graft_free(graft_0
);
179 depth
= isl_ast_build_get_depth(build
);
180 if (depth
< isl_set_dim(guard
, isl_dim_set
)) {
181 guard
= isl_set_eliminate(guard
, isl_dim_set
, depth
, 1);
182 guard
= isl_set_compute_divs(guard
);
185 for (i
= 1; i
< n
; ++i
) {
186 isl_ast_graft
*graft
;
190 is_universe
= isl_set_plain_is_universe(guard
);
192 guard
= isl_set_free(guard
);
196 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
198 guard
= isl_set_free(guard
);
201 guard
= isl_set_union(guard
, isl_set_copy(graft
->guard
));
202 hull
= isl_set_unshifted_simple_hull(guard
);
203 guard
= isl_set_from_basic_set(hull
);
204 isl_ast_graft_free(graft
);
210 /* Insert an if node around graft->node testing the condition encoded
211 * in guard "guard", assuming guard involves any conditions.
213 static __isl_give isl_ast_graft
*insert_if_node(
214 __isl_take isl_ast_graft
*graft
, __isl_take isl_set
*guard
,
215 __isl_keep isl_ast_build
*build
)
224 univ
= isl_set_plain_is_universe(guard
);
232 build
= isl_ast_build_copy(build
);
233 build
= isl_ast_build_set_enforced(build
,
234 isl_ast_graft_get_enforced(graft
));
235 expr
= isl_ast_build_expr_from_set(build
, guard
);
236 isl_ast_build_free(build
);
238 node
= isl_ast_node_alloc_if(expr
);
239 graft
->node
= isl_ast_node_if_set_then(node
, graft
->node
);
242 return isl_ast_graft_free(graft
);
247 return isl_ast_graft_free(graft
);
250 /* Insert an if node around graft->node testing the condition encoded
251 * in graft->guard, assuming graft->guard involves any conditions.
253 static __isl_give isl_ast_graft
*insert_pending_guard_node(
254 __isl_take isl_ast_graft
*graft
, __isl_keep isl_ast_build
*build
)
259 return insert_if_node(graft
, isl_set_copy(graft
->guard
), build
);
262 /* Replace graft->enforced by "enforced".
264 __isl_give isl_ast_graft
*isl_ast_graft_set_enforced(
265 __isl_take isl_ast_graft
*graft
, __isl_take isl_basic_set
*enforced
)
267 if (!graft
|| !enforced
)
270 isl_basic_set_free(graft
->enforced
);
271 graft
->enforced
= enforced
;
275 isl_basic_set_free(enforced
);
276 return isl_ast_graft_free(graft
);
279 /* Update "enforced" such that it only involves constraints that are
280 * also enforced by "graft".
282 static __isl_give isl_basic_set
*update_enforced(
283 __isl_take isl_basic_set
*enforced
, __isl_keep isl_ast_graft
*graft
,
286 isl_basic_set
*enforced_g
;
288 enforced_g
= isl_ast_graft_get_enforced(graft
);
289 if (depth
< isl_basic_set_dim(enforced_g
, isl_dim_set
))
290 enforced_g
= isl_basic_set_eliminate(enforced_g
,
291 isl_dim_set
, depth
, 1);
292 enforced_g
= isl_basic_set_remove_unknown_divs(enforced_g
);
293 enforced_g
= isl_basic_set_align_params(enforced_g
,
294 isl_basic_set_get_space(enforced
));
295 enforced
= isl_basic_set_align_params(enforced
,
296 isl_basic_set_get_space(enforced_g
));
297 enforced
= isl_set_simple_hull(isl_basic_set_union(enforced
,
303 /* Extend the node at *body with node.
305 * If body points to the else branch, then *body may still be NULL.
306 * If so, we simply attach node to this else branch.
307 * Otherwise, we attach a list containing the statements already
308 * attached at *body followed by node.
310 static void extend_body(__isl_keep isl_ast_node
**body
,
311 __isl_take isl_ast_node
*node
)
313 isl_ast_node_list
*list
;
320 if ((*body
)->type
== isl_ast_node_block
) {
321 list
= isl_ast_node_block_get_children(*body
);
322 isl_ast_node_free(*body
);
324 list
= isl_ast_node_list_from_ast_node(*body
);
325 list
= isl_ast_node_list_add(list
, node
);
326 *body
= isl_ast_node_alloc_block(list
);
329 /* Merge "graft" into the last graft of "list".
330 * body points to the then or else branch of an if node in that last graft.
332 * We attach graft->node to this branch and update the enforced
333 * set of the last graft of "list" to take into account the enforced
336 static __isl_give isl_ast_graft_list
*graft_extend_body(
337 __isl_take isl_ast_graft_list
*list
,
338 __isl_keep isl_ast_node
**body
, __isl_take isl_ast_graft
*graft
,
339 __isl_keep isl_ast_build
*build
)
345 isl_basic_set
*enforced
;
349 extend_body(body
, isl_ast_node_copy(graft
->node
));
353 n
= isl_ast_graft_list_n_ast_graft(list
);
354 last
= isl_ast_graft_list_get_ast_graft(list
, n
- 1);
356 depth
= isl_ast_build_get_depth(build
);
357 space
= isl_ast_build_get_space(build
, 1);
358 enforced
= isl_basic_set_empty(space
);
359 enforced
= update_enforced(enforced
, last
, depth
);
360 enforced
= update_enforced(enforced
, graft
, depth
);
361 last
= isl_ast_graft_set_enforced(last
, enforced
);
363 list
= isl_ast_graft_list_set_ast_graft(list
, n
- 1, last
);
364 isl_ast_graft_free(graft
);
367 isl_ast_graft_free(graft
);
368 return isl_ast_graft_list_free(list
);
371 /* Merge "graft" into the last graft of "list", attaching graft->node
372 * to the then branch of "last_if".
374 static __isl_give isl_ast_graft_list
*extend_then(
375 __isl_take isl_ast_graft_list
*list
,
376 __isl_keep isl_ast_node
*last_if
, __isl_take isl_ast_graft
*graft
,
377 __isl_keep isl_ast_build
*build
)
379 return graft_extend_body(list
, &last_if
->u
.i
.then
, graft
, build
);
382 /* Merge "graft" into the last graft of "list", attaching graft->node
383 * to the else branch of "last_if".
385 static __isl_give isl_ast_graft_list
*extend_else(
386 __isl_take isl_ast_graft_list
*list
,
387 __isl_keep isl_ast_node
*last_if
, __isl_take isl_ast_graft
*graft
,
388 __isl_keep isl_ast_build
*build
)
390 return graft_extend_body(list
, &last_if
->u
.i
.else_node
, graft
, build
);
393 /* This data structure keeps track of an if node.
395 * "node" is the actual if-node
396 * "guard" is the original, non-simplified guard of the node
397 * "complement" is the complement of "guard" in the context of outer if nodes
405 /* Given a list of "n" if nodes, clear those starting at "first"
406 * and return "first" (i.e., the updated size of the array).
408 static int clear_if_nodes(struct isl_if_node
*if_node
, int first
, int n
)
412 for (i
= first
; i
< n
; ++i
) {
413 isl_set_free(if_node
[i
].guard
);
414 isl_set_free(if_node
[i
].complement
);
420 /* For each graft in "list",
421 * insert an if node around graft->node testing the condition encoded
422 * in graft->guard, assuming graft->guard involves any conditions.
424 * We keep track of a list of generated if nodes that can be extended
425 * without changing the order of the elements in "list".
426 * If the guard of a graft is a subset of either the guard or its complement
427 * of one of those if nodes, then the node
428 * of the new graft is inserted into the then or else branch of the last graft
429 * and the current graft is discarded.
430 * The guard of the node is then simplified based on the conditions
431 * enforced at that then or else branch.
432 * Otherwise, the current graft is appended to the list.
434 * We only construct else branches if allowed by the user.
436 static __isl_give isl_ast_graft_list
*insert_pending_guard_nodes(
437 __isl_take isl_ast_graft_list
*list
,
438 __isl_keep isl_ast_build
*build
)
443 isl_ast_graft_list
*res
;
444 struct isl_if_node
*if_node
= NULL
;
447 return isl_ast_graft_list_free(list
);
449 ctx
= isl_ast_build_get_ctx(build
);
450 n
= isl_ast_graft_list_n_ast_graft(list
);
452 allow_else
= isl_options_get_ast_build_allow_else(ctx
);
456 if_node
= isl_alloc_array(ctx
, struct isl_if_node
, n
- 1);
458 return isl_ast_graft_list_free(list
);
461 res
= isl_ast_graft_list_alloc(ctx
, n
);
463 for (i
= 0; i
< n
; ++i
) {
465 isl_ast_graft
*graft
;
466 int subset
, found_then
, found_else
;
469 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
473 found_then
= found_else
= -1;
476 test
= isl_set_copy(graft
->guard
);
477 test
= isl_set_intersect(test
,
478 isl_set_copy(build
->domain
));
479 for (j
= n_if
- 1; j
>= 0; --j
) {
480 subset
= isl_set_is_subset(test
,
482 if (subset
< 0 || subset
) {
488 subset
= isl_set_is_subset(test
,
489 if_node
[j
].complement
);
490 if (subset
< 0 || subset
) {
495 n_if
= clear_if_nodes(if_node
, j
+ 1, n_if
);
499 graft
= isl_ast_graft_free(graft
);
503 guard
= isl_set_copy(graft
->guard
);
505 graft
->guard
= isl_set_gist(graft
->guard
,
506 isl_set_copy(if_node
[found_then
].guard
));
507 else if (found_else
>= 0)
508 graft
->guard
= isl_set_gist(graft
->guard
,
509 isl_set_copy(if_node
[found_else
].complement
));
513 graft
= isl_ast_graft_free(graft
);
514 graft
= insert_pending_guard_node(graft
, build
);
515 if (graft
&& graft
->node
!= node
&& i
!= n
- 1) {
517 if_node
[n_if
].node
= graft
->node
;
518 if_node
[n_if
].guard
= guard
;
520 set
= if_node
[found_then
].guard
;
521 else if (found_else
>= 0)
522 set
= if_node
[found_else
].complement
;
525 set
= isl_set_copy(set
);
526 set
= isl_set_subtract(set
, isl_set_copy(guard
));
527 if_node
[n_if
].complement
= set
;
535 res
= extend_then(res
, if_node
[found_then
].node
,
537 else if (found_else
>= 0)
538 res
= extend_else(res
, if_node
[found_else
].node
,
541 res
= isl_ast_graft_list_add(res
, graft
);
544 res
= isl_ast_graft_list_free(res
);
546 isl_ast_graft_list_free(list
);
547 clear_if_nodes(if_node
, 0, n_if
);
552 /* Collect the nodes contained in the grafts in "list" in a node list.
554 static __isl_give isl_ast_node_list
*extract_node_list(
555 __isl_keep isl_ast_graft_list
*list
)
559 isl_ast_node_list
*node_list
;
563 ctx
= isl_ast_graft_list_get_ctx(list
);
564 n
= isl_ast_graft_list_n_ast_graft(list
);
565 node_list
= isl_ast_node_list_alloc(ctx
, n
);
566 for (i
= 0; i
< n
; ++i
) {
568 isl_ast_graft
*graft
;
570 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
571 node
= isl_ast_graft_get_node(graft
);
572 node_list
= isl_ast_node_list_add(node_list
, node
);
573 isl_ast_graft_free(graft
);
579 /* Look for shared enforced constraints by all the elements in "list"
580 * on outer loops (with respect to the current depth) and return the result.
582 * We assume that the number of children is at least one.
584 static __isl_give isl_basic_set
*extract_shared_enforced(
585 __isl_keep isl_ast_graft_list
*list
,
586 __isl_keep isl_ast_build
*build
)
591 isl_basic_set
*enforced
;
596 n
= isl_ast_graft_list_n_ast_graft(list
);
598 isl_die(isl_ast_graft_list_get_ctx(list
), isl_error_invalid
,
599 "for node should have at least one child",
602 space
= isl_ast_build_get_space(build
, 1);
603 enforced
= isl_basic_set_empty(space
);
605 depth
= isl_ast_build_get_depth(build
);
606 for (i
= 0; i
< n
; ++i
) {
607 isl_ast_graft
*graft
;
609 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
610 enforced
= update_enforced(enforced
, graft
, depth
);
611 isl_ast_graft_free(graft
);
617 /* Record "guard" in "graft" so that it will be enforced somewhere
618 * up the tree. If the graft already has a guard, then it may be partially
619 * redundant in combination with the new guard and in the context
620 * of build->domain. We therefore (re)compute the gist of the intersection.
622 static __isl_give isl_ast_graft
*store_guard(__isl_take isl_ast_graft
*graft
,
623 __isl_take isl_set
*guard
, __isl_keep isl_ast_build
*build
)
630 is_universe
= isl_set_plain_is_universe(guard
);
638 graft
->guard
= isl_set_intersect(graft
->guard
, guard
);
639 graft
->guard
= isl_ast_build_compute_gist(build
, graft
->guard
);
641 return isl_ast_graft_free(graft
);
646 return isl_ast_graft_free(graft
);
649 /* For each graft in "list", replace its guard with the gist with
650 * respect to "context".
652 static __isl_give isl_ast_graft_list
*gist_guards(
653 __isl_take isl_ast_graft_list
*list
, __isl_keep isl_set
*context
)
660 n
= isl_ast_graft_list_n_ast_graft(list
);
661 for (i
= 0; i
< n
; ++i
) {
662 isl_ast_graft
*graft
;
664 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
667 graft
->guard
= isl_set_gist(graft
->guard
,
668 isl_set_copy(context
));
670 graft
= isl_ast_graft_free(graft
);
671 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
674 return isl_ast_graft_list_free(list
);
679 /* Combine the grafts in the list into a single graft.
681 * If "up" is set then the resulting graft will be used at an outer level.
682 * In this case, "build" refers to the outer level, while "sub_build"
683 * refers to the inner level. If "up" is not set, then the same build
684 * should be passed to both arguments.
686 * The guard is initialized to the shared guard of the list elements (if any),
687 * provided it does not depend on the current dimension.
688 * The guards in the elements are then simplified with respect to the
689 * hoisted guard and materialized as if nodes around the contained AST nodes
690 * in the context of "sub_build".
692 * The enforced set is initialized to the simple hull of the enforced sets
693 * of the elements, provided the ast_build_exploit_nested_bounds option is set
694 * or the new graft will be used at the same level.
696 * The node is initialized to either a block containing the nodes of "list"
697 * or, if there is only a single element, the node of that element.
699 static __isl_give isl_ast_graft
*ast_graft_list_fuse(
700 __isl_take isl_ast_graft_list
*list
, __isl_keep isl_ast_build
*build
,
701 __isl_keep isl_ast_build
*sub_build
, int up
)
705 isl_ast_graft
*graft
;
706 isl_ast_node_list
*node_list
;
712 ctx
= isl_ast_build_get_ctx(build
);
713 guard
= extract_hoistable_guard(list
, build
);
714 list
= gist_guards(list
, guard
);
715 list
= insert_pending_guard_nodes(list
, sub_build
);
717 node_list
= extract_node_list(list
);
718 node
= isl_ast_node_from_ast_node_list(node_list
);
720 graft
= isl_ast_graft_alloc(node
, build
);
722 if (!up
|| isl_options_get_ast_build_exploit_nested_bounds(ctx
)) {
723 isl_basic_set
*enforced
;
724 enforced
= extract_shared_enforced(list
, build
);
725 graft
= isl_ast_graft_enforce(graft
, enforced
);
728 graft
= store_guard(graft
, guard
, build
);
730 isl_ast_graft_list_free(list
);
734 /* Combine the grafts in the list into a single graft.
735 * Return a list containing this single graft.
736 * If the original list is empty, then return an empty list.
738 __isl_give isl_ast_graft_list
*isl_ast_graft_list_fuse(
739 __isl_take isl_ast_graft_list
*list
,
740 __isl_keep isl_ast_build
*build
)
742 isl_ast_graft
*graft
;
746 if (isl_ast_graft_list_n_ast_graft(list
) <= 1)
748 graft
= ast_graft_list_fuse(list
, build
, build
, 0);
749 return isl_ast_graft_list_from_ast_graft(graft
);
752 /* Combine the two grafts into a single graft.
753 * Return a list containing this single graft.
755 static __isl_give isl_ast_graft
*isl_ast_graft_fuse(
756 __isl_take isl_ast_graft
*graft1
, __isl_take isl_ast_graft
*graft2
,
757 __isl_keep isl_ast_build
*build
)
760 isl_ast_graft_list
*list
;
762 ctx
= isl_ast_build_get_ctx(build
);
764 list
= isl_ast_graft_list_alloc(ctx
, 2);
765 list
= isl_ast_graft_list_add(list
, graft1
);
766 list
= isl_ast_graft_list_add(list
, graft2
);
768 return ast_graft_list_fuse(list
, build
, build
, 0);
771 /* Allocate a graft for the current level based on the list of grafts
772 * of the inner level.
773 * "build" represents the context of the current level.
774 * "sub_build" represents the context of the inner level.
776 * The node is initialized to either a block containing the nodes of "children"
777 * or, if there is only a single child, the node of that child.
778 * If the current level requires a for node, it should be inserted by
779 * a subsequent call to isl_ast_graft_insert_for.
781 __isl_give isl_ast_graft
*isl_ast_graft_alloc_level(
782 __isl_take isl_ast_graft_list
*children
,
783 __isl_keep isl_ast_build
*build
, __isl_keep isl_ast_build
*sub_build
)
785 return ast_graft_list_fuse(children
, build
, sub_build
, 1);
788 /* Insert a for node enclosing the current graft->node.
790 __isl_give isl_ast_graft
*isl_ast_graft_insert_for(
791 __isl_take isl_ast_graft
*graft
, __isl_take isl_ast_node
*node
)
796 graft
->node
= isl_ast_node_for_set_body(node
, graft
->node
);
798 return isl_ast_graft_free(graft
);
802 isl_ast_node_free(node
);
803 isl_ast_graft_free(graft
);
807 /* Represent the graft list as an AST node.
808 * This operation drops the information about guards in the grafts, so
809 * if there are any pending guards, then they are materialized as if nodes.
811 __isl_give isl_ast_node
*isl_ast_node_from_graft_list(
812 __isl_take isl_ast_graft_list
*list
,
813 __isl_keep isl_ast_build
*build
)
815 isl_ast_node_list
*node_list
;
817 list
= insert_pending_guard_nodes(list
, build
);
818 node_list
= extract_node_list(list
);
819 isl_ast_graft_list_free(list
);
821 return isl_ast_node_from_ast_node_list(node_list
);
824 void *isl_ast_graft_free(__isl_take isl_ast_graft
*graft
)
829 if (--graft
->ref
> 0)
832 isl_ast_node_free(graft
->node
);
833 isl_set_free(graft
->guard
);
834 isl_basic_set_free(graft
->enforced
);
840 /* Record that the grafted tree enforces
841 * "enforced" by intersecting graft->enforced with "enforced".
843 __isl_give isl_ast_graft
*isl_ast_graft_enforce(
844 __isl_take isl_ast_graft
*graft
, __isl_take isl_basic_set
*enforced
)
846 if (!graft
|| !enforced
)
849 enforced
= isl_basic_set_align_params(enforced
,
850 isl_basic_set_get_space(graft
->enforced
));
851 graft
->enforced
= isl_basic_set_align_params(graft
->enforced
,
852 isl_basic_set_get_space(enforced
));
853 graft
->enforced
= isl_basic_set_intersect(graft
->enforced
, enforced
);
854 if (!graft
->enforced
)
855 return isl_ast_graft_free(graft
);
859 isl_basic_set_free(enforced
);
860 return isl_ast_graft_free(graft
);
863 __isl_give isl_basic_set
*isl_ast_graft_get_enforced(
864 __isl_keep isl_ast_graft
*graft
)
866 return graft
? isl_basic_set_copy(graft
->enforced
) : NULL
;
869 __isl_give isl_set
*isl_ast_graft_get_guard(__isl_keep isl_ast_graft
*graft
)
871 return graft
? isl_set_copy(graft
->guard
) : NULL
;
874 /* Record that "guard" needs to be inserted in "graft".
876 * We first simplify the guard in the context of the enforced set and
877 * then we store the guard in case we may be able
878 * to hoist it to higher levels and/or combine it with those of other grafts.
880 __isl_give isl_ast_graft
*isl_ast_graft_add_guard(
881 __isl_take isl_ast_graft
*graft
,
882 __isl_take isl_set
*guard
, __isl_keep isl_ast_build
*build
)
884 isl_basic_set
*enforced
;
886 if (!graft
|| !build
)
889 enforced
= isl_basic_set_copy(graft
->enforced
);
890 guard
= isl_set_gist(guard
, isl_set_from_basic_set(enforced
));
892 graft
= store_guard(graft
, guard
, build
);
897 isl_ast_graft_free(graft
);
901 /* Reformulate the "graft", which was generated in the context
902 * of an inner code generation, in terms of the outer code generation
905 * If "product" is set, then the domain of the inner code generation build is
909 * with O the domain of the outer code generation build.
910 * We essentially need to project out S.
912 * If "product" is not set, then we need to project the domains onto
913 * their parameter spaces.
915 __isl_give isl_ast_graft
*isl_ast_graft_unembed(__isl_take isl_ast_graft
*graft
,
918 isl_basic_set
*enforced
;
924 enforced
= graft
->enforced
;
925 enforced
= isl_basic_map_domain(isl_basic_set_unwrap(enforced
));
926 graft
->enforced
= enforced
;
927 graft
->guard
= isl_map_domain(isl_set_unwrap(graft
->guard
));
929 graft
->enforced
= isl_basic_set_params(graft
->enforced
);
930 graft
->guard
= isl_set_params(graft
->guard
);
932 graft
->guard
= isl_set_compute_divs(graft
->guard
);
934 if (!graft
->enforced
|| !graft
->guard
)
935 return isl_ast_graft_free(graft
);
940 /* Reformulate the grafts in "list", which were generated in the context
941 * of an inner code generation, in terms of the outer code generation
944 __isl_give isl_ast_graft_list
*isl_ast_graft_list_unembed(
945 __isl_take isl_ast_graft_list
*list
, int product
)
949 n
= isl_ast_graft_list_n_ast_graft(list
);
950 for (i
= 0; i
< n
; ++i
) {
951 isl_ast_graft
*graft
;
953 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
954 graft
= isl_ast_graft_unembed(graft
, product
);
955 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
961 /* Compute the preimage of "graft" under the function represented by "ma".
962 * In other words, plug in "ma" in "enforced" and "guard" fields of "graft".
964 __isl_give isl_ast_graft
*isl_ast_graft_preimage_multi_aff(
965 __isl_take isl_ast_graft
*graft
, __isl_take isl_multi_aff
*ma
)
967 isl_basic_set
*enforced
;
972 enforced
= graft
->enforced
;
973 graft
->enforced
= isl_basic_set_preimage_multi_aff(enforced
,
974 isl_multi_aff_copy(ma
));
975 graft
->guard
= isl_set_preimage_multi_aff(graft
->guard
, ma
);
977 if (!graft
->enforced
|| !graft
->guard
)
978 return isl_ast_graft_free(graft
);
983 /* Compute the preimage of all the grafts in "list" under
984 * the function represented by "ma".
986 __isl_give isl_ast_graft_list
*isl_ast_graft_list_preimage_multi_aff(
987 __isl_take isl_ast_graft_list
*list
, __isl_take isl_multi_aff
*ma
)
991 n
= isl_ast_graft_list_n_ast_graft(list
);
992 for (i
= 0; i
< n
; ++i
) {
993 isl_ast_graft
*graft
;
995 graft
= isl_ast_graft_list_get_ast_graft(list
, i
);
996 graft
= isl_ast_graft_preimage_multi_aff(graft
,
997 isl_multi_aff_copy(ma
));
998 list
= isl_ast_graft_list_set_ast_graft(list
, i
, graft
);
1001 isl_multi_aff_free(ma
);
1005 /* Compare two grafts based on their guards.
1007 static int cmp_graft(const void *a
, const void *b
)
1009 isl_ast_graft
* const *g1
= a
;
1010 isl_ast_graft
* const *g2
= b
;
1012 return isl_set_plain_cmp((*g1
)->guard
, (*g2
)->guard
);
1015 /* Order the elements in "list" based on their guards.
1017 __isl_give isl_ast_graft_list
*isl_ast_graft_list_sort(
1018 __isl_take isl_ast_graft_list
*list
)
1025 qsort(list
->p
, list
->n
, sizeof(list
->p
[0]), &cmp_graft
);
1030 /* Merge the given two lists into a single list of grafts,
1031 * merging grafts with the same guard into a single graft.
1033 * "list2" has been sorted using isl_ast_graft_list_sort.
1034 * "list1" may be the result of a previous call to isl_ast_graft_list_merge
1035 * and may therefore not be completely sorted.
1037 * The elements in "list2" need to be executed after those in "list1",
1038 * but if the guard of a graft in "list2" is disjoint from the guards
1039 * of some final elements in "list1", then it can be moved up to before
1040 * those final elements.
1042 * In particular, we look at each element g of "list2" in turn
1043 * and move it up beyond elements of "list1" that would be sorted
1044 * after g as long as each of these elements has a guard that is disjoint
1047 * We do not allow the second or any later element of "list2" to be moved
1048 * before a previous elements of "list2" even if the reason that
1049 * that element didn't move up further was that its guard was not disjoint
1050 * from that of the previous element in "list1".
1052 __isl_give isl_ast_graft_list
*isl_ast_graft_list_merge(
1053 __isl_take isl_ast_graft_list
*list1
,
1054 __isl_take isl_ast_graft_list
*list2
,
1055 __isl_keep isl_ast_build
*build
)
1059 if (!list1
|| !list2
|| !build
)
1061 if (list2
->n
== 0) {
1062 isl_ast_graft_list_free(list2
);
1065 if (list1
->n
== 0) {
1066 isl_ast_graft_list_free(list1
);
1071 for (i
= 0; i
< list2
->n
; ++i
) {
1072 isl_ast_graft
*graft
;
1073 graft
= isl_ast_graft_list_get_ast_graft(list2
, i
);
1077 for (j
= list1
->n
; j
>= 0; --j
) {
1079 isl_ast_graft
*graft_j
;
1084 cmp
= isl_set_plain_cmp(list1
->p
[j
- 1]->guard
,
1087 disjoint
= isl_set_is_disjoint(graft
->guard
,
1088 list1
->p
[j
- 1]->guard
);
1090 list1
= isl_ast_graft_list_free(list1
);
1099 list1
= isl_ast_graft_list_insert(list1
, j
,
1106 graft_j
= isl_ast_graft_list_get_ast_graft(list1
, j
);
1107 graft_j
= isl_ast_graft_fuse(graft_j
, graft
, build
);
1108 list1
= isl_ast_graft_list_set_ast_graft(list1
, j
,
1114 isl_die(isl_ast_build_get_ctx(build
),
1116 "element failed to get inserted", break);
1123 list1
= isl_ast_graft_list_free(list1
);
1124 isl_ast_graft_list_free(list2
);
1128 isl_ast_graft_list_free(list1
);
1129 isl_ast_graft_list_free(list2
);
1133 __isl_give isl_printer
*isl_printer_print_ast_graft(__isl_take isl_printer
*p
,
1134 __isl_keep isl_ast_graft
*graft
)
1139 return isl_printer_free(p
);
1141 p
= isl_printer_print_str(p
, "(");
1142 p
= isl_printer_print_str(p
, "guard: ");
1143 p
= isl_printer_print_set(p
, graft
->guard
);
1144 p
= isl_printer_print_str(p
, ", ");
1145 p
= isl_printer_print_str(p
, "enforced: ");
1146 p
= isl_printer_print_basic_set(p
, graft
->enforced
);
1147 p
= isl_printer_print_str(p
, ", ");
1148 p
= isl_printer_print_str(p
, "node: ");
1149 p
= isl_printer_print_ast_node(p
, graft
->node
);
1150 p
= isl_printer_print_str(p
, ")");