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_remove_divs_involving_dims(guard,
182 isl_dim_set, depth, 1);
183 guard = isl_set_eliminate(guard, isl_dim_set, depth, 1);
184 guard = isl_set_compute_divs(guard);
187 for (i = 1; i < n; ++i) {
188 isl_ast_graft *graft;
192 is_universe = isl_set_plain_is_universe(guard);
194 guard = isl_set_free(guard);
198 graft = isl_ast_graft_list_get_ast_graft(list, i);
200 guard = isl_set_free(guard);
203 guard = isl_set_union(guard, isl_set_copy(graft->guard));
204 hull = isl_set_unshifted_simple_hull(guard);
205 guard = isl_set_from_basic_set(hull);
206 isl_ast_graft_free(graft);
212 /* Internal data structure used inside insert_if.
214 * list is the list of guarded nodes created by each call to insert_if.
215 * node is the original node that is guarded by insert_if.
216 * build is the build in which the AST is constructed.
218 struct isl_insert_if_data {
219 isl_ast_node_list *list;
221 isl_ast_build *build;
224 static int insert_if(__isl_take isl_basic_set *bset, void *user);
226 /* Insert an if node around "node" testing the condition encoded
229 * If the user does not want any disjunctions in the if conditions
230 * and if "guard" does involve a disjunction, then we make the different
231 * disjuncts disjoint and insert an if node corresponding to each disjunct
232 * around a copy of "node". The result is then a block node containing
233 * this sequence of guarded copies of "node".
235 static __isl_give isl_ast_node *ast_node_insert_if(
236 __isl_take isl_ast_node *node, __isl_take isl_set *guard,
237 __isl_keep isl_ast_build *build)
239 struct isl_insert_if_data data;
242 ctx = isl_ast_build_get_ctx(build);
243 if (isl_options_get_ast_build_allow_or(ctx) ||
244 isl_set_n_basic_set(guard) <= 1) {
245 isl_ast_node *if_node;
248 expr = isl_ast_build_expr_from_set(build, guard);
250 if_node = isl_ast_node_alloc_if(expr);
251 return isl_ast_node_if_set_then(if_node, node);
254 guard = isl_set_make_disjoint(guard);
256 data.list = isl_ast_node_list_alloc(ctx, 0);
259 if (isl_set_foreach_basic_set(guard, &insert_if, &data) < 0)
260 data.list = isl_ast_node_list_free(data.list);
263 isl_ast_node_free(data.node);
264 return isl_ast_node_alloc_block(data.list);
267 /* Insert an if node around a copy of "data->node" testing the condition
268 * encoded in guard "bset" and add the result to data->list.
270 static int insert_if(__isl_take isl_basic_set *bset, void *user)
272 struct isl_insert_if_data *data = user;
276 set = isl_set_from_basic_set(bset);
277 node = isl_ast_node_copy(data->node);
278 node = ast_node_insert_if(node, set, data->build);
279 data->list = isl_ast_node_list_add(data->list, node);
284 /* Insert an if node around graft->node testing the condition encoded
285 * in guard "guard", assuming guard involves any conditions.
287 static __isl_give isl_ast_graft *insert_if_node(
288 __isl_take isl_ast_graft *graft, __isl_take isl_set *guard,
289 __isl_keep isl_ast_build *build)
296 univ = isl_set_plain_is_universe(guard);
304 build = isl_ast_build_copy(build);
305 build = isl_ast_build_set_enforced(build,
306 isl_ast_graft_get_enforced(graft));
307 graft->node = ast_node_insert_if(graft->node, guard, build);
308 isl_ast_build_free(build);
311 return isl_ast_graft_free(graft);
316 return isl_ast_graft_free(graft);
319 /* Insert an if node around graft->node testing the condition encoded
320 * in graft->guard, assuming graft->guard involves any conditions.
322 static __isl_give isl_ast_graft *insert_pending_guard_node(
323 __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build)
328 return insert_if_node(graft, isl_set_copy(graft->guard), build);
331 /* Replace graft->enforced by "enforced".
333 __isl_give isl_ast_graft *isl_ast_graft_set_enforced(
334 __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced)
336 if (!graft || !enforced)
339 isl_basic_set_free(graft->enforced);
340 graft->enforced = enforced;
344 isl_basic_set_free(enforced);
345 return isl_ast_graft_free(graft);
348 /* Update "enforced" such that it only involves constraints that are
349 * also enforced by "graft".
351 static __isl_give isl_basic_set *update_enforced(
352 __isl_take isl_basic_set *enforced, __isl_keep isl_ast_graft *graft,
355 isl_basic_set *enforced_g;
357 enforced_g = isl_ast_graft_get_enforced(graft);
358 if (depth < isl_basic_set_dim(enforced_g, isl_dim_set))
359 enforced_g = isl_basic_set_eliminate(enforced_g,
360 isl_dim_set, depth, 1);
361 enforced_g = isl_basic_set_remove_unknown_divs(enforced_g);
362 enforced_g = isl_basic_set_align_params(enforced_g,
363 isl_basic_set_get_space(enforced));
364 enforced = isl_basic_set_align_params(enforced,
365 isl_basic_set_get_space(enforced_g));
366 enforced = isl_set_simple_hull(isl_basic_set_union(enforced,
372 /* Extend the node at *body with node.
374 * If body points to the else branch, then *body may still be NULL.
375 * If so, we simply attach node to this else branch.
376 * Otherwise, we attach a list containing the statements already
377 * attached at *body followed by node.
379 static void extend_body(__isl_keep isl_ast_node **body,
380 __isl_take isl_ast_node *node)
382 isl_ast_node_list *list;
389 if ((*body)->type == isl_ast_node_block) {
390 list = isl_ast_node_block_get_children(*body);
391 isl_ast_node_free(*body);
393 list = isl_ast_node_list_from_ast_node(*body);
394 list = isl_ast_node_list_add(list, node);
395 *body = isl_ast_node_alloc_block(list);
398 /* Merge "graft" into the last graft of "list".
399 * body points to the then or else branch of an if node in that last graft.
401 * We attach graft->node to this branch and update the enforced
402 * set of the last graft of "list" to take into account the enforced
405 static __isl_give isl_ast_graft_list *graft_extend_body(
406 __isl_take isl_ast_graft_list *list,
407 __isl_keep isl_ast_node **body, __isl_take isl_ast_graft *graft,
408 __isl_keep isl_ast_build *build)
414 isl_basic_set *enforced;
418 extend_body(body, isl_ast_node_copy(graft->node));
422 n = isl_ast_graft_list_n_ast_graft(list);
423 last = isl_ast_graft_list_get_ast_graft(list, n - 1);
425 depth = isl_ast_build_get_depth(build);
426 space = isl_ast_build_get_space(build, 1);
427 enforced = isl_basic_set_empty(space);
428 enforced = update_enforced(enforced, last, depth);
429 enforced = update_enforced(enforced, graft, depth);
430 last = isl_ast_graft_set_enforced(last, enforced);
432 list = isl_ast_graft_list_set_ast_graft(list, n - 1, last);
433 isl_ast_graft_free(graft);
436 isl_ast_graft_free(graft);
437 return isl_ast_graft_list_free(list);
440 /* Merge "graft" into the last graft of "list", attaching graft->node
441 * to the then branch of "last_if".
443 static __isl_give isl_ast_graft_list *extend_then(
444 __isl_take isl_ast_graft_list *list,
445 __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft,
446 __isl_keep isl_ast_build *build)
448 return graft_extend_body(list, &last_if->u.i.then, graft, build);
451 /* Merge "graft" into the last graft of "list", attaching graft->node
452 * to the else branch of "last_if".
454 static __isl_give isl_ast_graft_list *extend_else(
455 __isl_take isl_ast_graft_list *list,
456 __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft,
457 __isl_keep isl_ast_build *build)
459 return graft_extend_body(list, &last_if->u.i.else_node, graft, build);
462 /* This data structure keeps track of an if node.
464 * "node" is the actual if-node
465 * "guard" is the original, non-simplified guard of the node
466 * "complement" is the complement of "guard" in the context of outer if nodes
474 /* Given a list of "n" if nodes, clear those starting at "first"
475 * and return "first" (i.e., the updated size of the array).
477 static int clear_if_nodes(struct isl_if_node *if_node, int first, int n)
481 for (i = first; i < n; ++i) {
482 isl_set_free(if_node[i].guard);
483 isl_set_free(if_node[i].complement);
489 /* For each graft in "list",
490 * insert an if node around graft->node testing the condition encoded
491 * in graft->guard, assuming graft->guard involves any conditions.
493 * We keep track of a list of generated if nodes that can be extended
494 * without changing the order of the elements in "list".
495 * If the guard of a graft is a subset of either the guard or its complement
496 * of one of those if nodes, then the node
497 * of the new graft is inserted into the then or else branch of the last graft
498 * and the current graft is discarded.
499 * The guard of the node is then simplified based on the conditions
500 * enforced at that then or else branch.
501 * Otherwise, the current graft is appended to the list.
503 * We only construct else branches if allowed by the user.
505 static __isl_give isl_ast_graft_list *insert_pending_guard_nodes(
506 __isl_take isl_ast_graft_list *list,
507 __isl_keep isl_ast_build *build)
512 isl_ast_graft_list *res;
513 struct isl_if_node *if_node = NULL;
516 return isl_ast_graft_list_free(list);
518 ctx = isl_ast_build_get_ctx(build);
519 n = isl_ast_graft_list_n_ast_graft(list);
521 allow_else = isl_options_get_ast_build_allow_else(ctx);
525 if_node = isl_alloc_array(ctx, struct isl_if_node, n - 1);
527 return isl_ast_graft_list_free(list);
530 res = isl_ast_graft_list_alloc(ctx, n);
532 for (i = 0; i < n; ++i) {
534 isl_ast_graft *graft;
535 int subset, found_then, found_else;
538 graft = isl_ast_graft_list_get_ast_graft(list, i);
542 found_then = found_else = -1;
545 test = isl_set_copy(graft->guard);
546 test = isl_set_intersect(test,
547 isl_set_copy(build->domain));
548 for (j = n_if - 1; j >= 0; --j) {
549 subset = isl_set_is_subset(test,
551 if (subset < 0 || subset) {
557 subset = isl_set_is_subset(test,
558 if_node[j].complement);
559 if (subset < 0 || subset) {
564 n_if = clear_if_nodes(if_node, j + 1, n_if);
568 graft = isl_ast_graft_free(graft);
572 guard = isl_set_copy(graft->guard);
574 graft->guard = isl_set_gist(graft->guard,
575 isl_set_copy(if_node[found_then].guard));
576 else if (found_else >= 0)
577 graft->guard = isl_set_gist(graft->guard,
578 isl_set_copy(if_node[found_else].complement));
582 graft = isl_ast_graft_free(graft);
583 graft = insert_pending_guard_node(graft, build);
584 if (graft && graft->node != node && i != n - 1) {
586 if_node[n_if].node = graft->node;
587 if_node[n_if].guard = guard;
589 set = if_node[found_then].guard;
590 else if (found_else >= 0)
591 set = if_node[found_else].complement;
594 set = isl_set_copy(set);
595 set = isl_set_subtract(set, isl_set_copy(guard));
596 if_node[n_if].complement = set;
604 res = extend_then(res, if_node[found_then].node,
606 else if (found_else >= 0)
607 res = extend_else(res, if_node[found_else].node,
610 res = isl_ast_graft_list_add(res, graft);
613 res = isl_ast_graft_list_free(res);
615 isl_ast_graft_list_free(list);
616 clear_if_nodes(if_node, 0, n_if);
621 /* Collect the nodes contained in the grafts in "list" in a node list.
623 static __isl_give isl_ast_node_list *extract_node_list(
624 __isl_keep isl_ast_graft_list *list)
628 isl_ast_node_list *node_list;
632 ctx = isl_ast_graft_list_get_ctx(list);
633 n = isl_ast_graft_list_n_ast_graft(list);
634 node_list = isl_ast_node_list_alloc(ctx, n);
635 for (i = 0; i < n; ++i) {
637 isl_ast_graft *graft;
639 graft = isl_ast_graft_list_get_ast_graft(list, i);
640 node = isl_ast_graft_get_node(graft);
641 node_list = isl_ast_node_list_add(node_list, node);
642 isl_ast_graft_free(graft);
648 /* Look for shared enforced constraints by all the elements in "list"
649 * on outer loops (with respect to the current depth) and return the result.
651 * We assume that the number of children is at least one.
653 static __isl_give isl_basic_set *extract_shared_enforced(
654 __isl_keep isl_ast_graft_list *list,
655 __isl_keep isl_ast_build *build)
660 isl_basic_set *enforced;
665 n = isl_ast_graft_list_n_ast_graft(list);
667 isl_die(isl_ast_graft_list_get_ctx(list), isl_error_invalid,
668 "for node should have at least one child",
671 space = isl_ast_build_get_space(build, 1);
672 enforced = isl_basic_set_empty(space);
674 depth = isl_ast_build_get_depth(build);
675 for (i = 0; i < n; ++i) {
676 isl_ast_graft *graft;
678 graft = isl_ast_graft_list_get_ast_graft(list, i);
679 enforced = update_enforced(enforced, graft, depth);
680 isl_ast_graft_free(graft);
686 /* Record "guard" in "graft" so that it will be enforced somewhere
687 * up the tree. If the graft already has a guard, then it may be partially
688 * redundant in combination with the new guard and in the context
689 * of build->domain. We therefore (re)compute the gist of the intersection
690 * and coalesce the result.
692 static __isl_give isl_ast_graft *store_guard(__isl_take isl_ast_graft *graft,
693 __isl_take isl_set *guard, __isl_keep isl_ast_build *build)
700 is_universe = isl_set_plain_is_universe(guard);
708 graft->guard = isl_set_intersect(graft->guard, guard);
709 graft->guard = isl_ast_build_compute_gist(build, graft->guard);
710 graft->guard = isl_set_coalesce(graft->guard);
712 return isl_ast_graft_free(graft);
717 return isl_ast_graft_free(graft);
720 /* For each graft in "list", replace its guard with the gist with
721 * respect to "context".
723 static __isl_give isl_ast_graft_list *gist_guards(
724 __isl_take isl_ast_graft_list *list, __isl_keep isl_set *context)
731 n = isl_ast_graft_list_n_ast_graft(list);
732 for (i = 0; i < n; ++i) {
733 isl_ast_graft *graft;
735 graft = isl_ast_graft_list_get_ast_graft(list, i);
738 graft->guard = isl_set_gist(graft->guard,
739 isl_set_copy(context));
741 graft = isl_ast_graft_free(graft);
742 list = isl_ast_graft_list_set_ast_graft(list, i, graft);
745 return isl_ast_graft_list_free(list);
750 /* Combine the grafts in the list into a single graft.
752 * If "up" is set then the resulting graft will be used at an outer level.
753 * In this case, "build" refers to the outer level, while "sub_build"
754 * refers to the inner level. If "up" is not set, then the same build
755 * should be passed to both arguments.
757 * The guard is initialized to the shared guard of the list elements (if any),
758 * provided it does not depend on the current dimension.
759 * The guards in the elements are then simplified with respect to the
760 * hoisted guard and materialized as if nodes around the contained AST nodes
761 * in the context of "sub_build".
763 * The enforced set is initialized to the simple hull of the enforced sets
764 * of the elements, provided the ast_build_exploit_nested_bounds option is set
765 * or the new graft will be used at the same level.
767 * The node is initialized to either a block containing the nodes of "list"
768 * or, if there is only a single element, the node of that element.
770 static __isl_give isl_ast_graft *ast_graft_list_fuse(
771 __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build,
772 __isl_keep isl_ast_build *sub_build, int up)
776 isl_ast_graft *graft;
777 isl_ast_node_list *node_list;
783 ctx = isl_ast_build_get_ctx(build);
784 guard = extract_hoistable_guard(list, build);
785 list = gist_guards(list, guard);
786 list = insert_pending_guard_nodes(list, sub_build);
788 node_list = extract_node_list(list);
789 node = isl_ast_node_from_ast_node_list(node_list);
791 graft = isl_ast_graft_alloc(node, build);
793 if (!up || isl_options_get_ast_build_exploit_nested_bounds(ctx)) {
794 isl_basic_set *enforced;
795 enforced = extract_shared_enforced(list, build);
796 graft = isl_ast_graft_enforce(graft, enforced);
799 graft = store_guard(graft, guard, build);
801 isl_ast_graft_list_free(list);
805 /* Combine the grafts in the list into a single graft.
806 * Return a list containing this single graft.
807 * If the original list is empty, then return an empty list.
809 __isl_give isl_ast_graft_list *isl_ast_graft_list_fuse(
810 __isl_take isl_ast_graft_list *list,
811 __isl_keep isl_ast_build *build)
813 isl_ast_graft *graft;
817 if (isl_ast_graft_list_n_ast_graft(list) <= 1)
819 graft = ast_graft_list_fuse(list, build, build, 0);
820 return isl_ast_graft_list_from_ast_graft(graft);
823 /* Combine the two grafts into a single graft.
824 * Return a list containing this single graft.
826 static __isl_give isl_ast_graft *isl_ast_graft_fuse(
827 __isl_take isl_ast_graft *graft1, __isl_take isl_ast_graft *graft2,
828 __isl_keep isl_ast_build *build)
831 isl_ast_graft_list *list;
833 ctx = isl_ast_build_get_ctx(build);
835 list = isl_ast_graft_list_alloc(ctx, 2);
836 list = isl_ast_graft_list_add(list, graft1);
837 list = isl_ast_graft_list_add(list, graft2);
839 return ast_graft_list_fuse(list, build, build, 0);
842 /* Allocate a graft for the current level based on the list of grafts
843 * of the inner level.
844 * "build" represents the context of the current level.
845 * "sub_build" represents the context of the inner level.
847 * The node is initialized to either a block containing the nodes of "children"
848 * or, if there is only a single child, the node of that child.
849 * If the current level requires a for node, it should be inserted by
850 * a subsequent call to isl_ast_graft_insert_for.
852 __isl_give isl_ast_graft *isl_ast_graft_alloc_level(
853 __isl_take isl_ast_graft_list *children,
854 __isl_keep isl_ast_build *build, __isl_keep isl_ast_build *sub_build)
856 return ast_graft_list_fuse(children, build, sub_build, 1);
859 /* Insert a for node enclosing the current graft->node.
861 __isl_give isl_ast_graft *isl_ast_graft_insert_for(
862 __isl_take isl_ast_graft *graft, __isl_take isl_ast_node *node)
867 graft->node = isl_ast_node_for_set_body(node, graft->node);
869 return isl_ast_graft_free(graft);
873 isl_ast_node_free(node);
874 isl_ast_graft_free(graft);
878 /* Represent the graft list as an AST node.
879 * This operation drops the information about guards in the grafts, so
880 * if there are any pending guards, then they are materialized as if nodes.
882 __isl_give isl_ast_node *isl_ast_node_from_graft_list(
883 __isl_take isl_ast_graft_list *list,
884 __isl_keep isl_ast_build *build)
886 isl_ast_node_list *node_list;
888 list = insert_pending_guard_nodes(list, build);
889 node_list = extract_node_list(list);
890 isl_ast_graft_list_free(list);
892 return isl_ast_node_from_ast_node_list(node_list);
895 void *isl_ast_graft_free(__isl_take isl_ast_graft *graft)
900 if (--graft->ref > 0)
903 isl_ast_node_free(graft->node);
904 isl_set_free(graft->guard);
905 isl_basic_set_free(graft->enforced);
911 /* Record that the grafted tree enforces
912 * "enforced" by intersecting graft->enforced with "enforced".
914 __isl_give isl_ast_graft *isl_ast_graft_enforce(
915 __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced)
917 if (!graft || !enforced)
920 enforced = isl_basic_set_align_params(enforced,
921 isl_basic_set_get_space(graft->enforced));
922 graft->enforced = isl_basic_set_align_params(graft->enforced,
923 isl_basic_set_get_space(enforced));
924 graft->enforced = isl_basic_set_intersect(graft->enforced, enforced);
925 if (!graft->enforced)
926 return isl_ast_graft_free(graft);
930 isl_basic_set_free(enforced);
931 return isl_ast_graft_free(graft);
934 __isl_give isl_basic_set *isl_ast_graft_get_enforced(
935 __isl_keep isl_ast_graft *graft)
937 return graft ? isl_basic_set_copy(graft->enforced) : NULL;
940 __isl_give isl_set *isl_ast_graft_get_guard(__isl_keep isl_ast_graft *graft)
942 return graft ? isl_set_copy(graft->guard) : NULL;
945 /* Record that "guard" needs to be inserted in "graft".
947 * We first simplify the guard in the context of the enforced set and
948 * then we store the guard in case we may be able
949 * to hoist it to higher levels and/or combine it with those of other grafts.
951 __isl_give isl_ast_graft *isl_ast_graft_add_guard(
952 __isl_take isl_ast_graft *graft,
953 __isl_take isl_set *guard, __isl_keep isl_ast_build *build)
955 isl_basic_set *enforced;
957 if (!graft || !build)
960 enforced = isl_basic_set_copy(graft->enforced);
961 guard = isl_set_gist(guard, isl_set_from_basic_set(enforced));
963 graft = store_guard(graft, guard, build);
968 isl_ast_graft_free(graft);
972 /* Reformulate the "graft", which was generated in the context
973 * of an inner code generation, in terms of the outer code generation
976 * If "product" is set, then the domain of the inner code generation build is
980 * with O the domain of the outer code generation build.
981 * We essentially need to project out S.
983 * If "product" is not set, then we need to project the domains onto
984 * their parameter spaces.
986 __isl_give isl_ast_graft *isl_ast_graft_unembed(__isl_take isl_ast_graft *graft,
989 isl_basic_set *enforced;
995 enforced = graft->enforced;
996 enforced = isl_basic_map_domain(isl_basic_set_unwrap(enforced));
997 graft->enforced = enforced;
998 graft->guard = isl_map_domain(isl_set_unwrap(graft->guard));
1000 graft->enforced = isl_basic_set_params(graft->enforced);
1001 graft->guard = isl_set_params(graft->guard);
1003 graft->guard = isl_set_compute_divs(graft->guard);
1005 if (!graft->enforced || !graft->guard)
1006 return isl_ast_graft_free(graft);
1011 /* Reformulate the grafts in "list", which were generated in the context
1012 * of an inner code generation, in terms of the outer code generation
1015 __isl_give isl_ast_graft_list *isl_ast_graft_list_unembed(
1016 __isl_take isl_ast_graft_list *list, int product)
1020 n = isl_ast_graft_list_n_ast_graft(list);
1021 for (i = 0; i < n; ++i) {
1022 isl_ast_graft *graft;
1024 graft = isl_ast_graft_list_get_ast_graft(list, i);
1025 graft = isl_ast_graft_unembed(graft, product);
1026 list = isl_ast_graft_list_set_ast_graft(list, i, graft);
1032 /* Compute the preimage of "graft" under the function represented by "ma".
1033 * In other words, plug in "ma" in "enforced" and "guard" fields of "graft".
1035 __isl_give isl_ast_graft *isl_ast_graft_preimage_multi_aff(
1036 __isl_take isl_ast_graft *graft, __isl_take isl_multi_aff *ma)
1038 isl_basic_set *enforced;
1043 enforced = graft->enforced;
1044 graft->enforced = isl_basic_set_preimage_multi_aff(enforced,
1045 isl_multi_aff_copy(ma));
1046 graft->guard = isl_set_preimage_multi_aff(graft->guard, ma);
1048 if (!graft->enforced || !graft->guard)
1049 return isl_ast_graft_free(graft);
1054 /* Compute the preimage of all the grafts in "list" under
1055 * the function represented by "ma".
1057 __isl_give isl_ast_graft_list *isl_ast_graft_list_preimage_multi_aff(
1058 __isl_take isl_ast_graft_list *list, __isl_take isl_multi_aff *ma)
1062 n = isl_ast_graft_list_n_ast_graft(list);
1063 for (i = 0; i < n; ++i) {
1064 isl_ast_graft *graft;
1066 graft = isl_ast_graft_list_get_ast_graft(list, i);
1067 graft = isl_ast_graft_preimage_multi_aff(graft,
1068 isl_multi_aff_copy(ma));
1069 list = isl_ast_graft_list_set_ast_graft(list, i, graft);
1072 isl_multi_aff_free(ma);
1076 /* Compare two grafts based on their guards.
1078 static int cmp_graft(__isl_keep isl_ast_graft *a, __isl_keep isl_ast_graft *b,
1081 return isl_set_plain_cmp(a->guard, b->guard);
1084 /* Order the elements in "list" based on their guards.
1086 __isl_give isl_ast_graft_list *isl_ast_graft_list_sort_guard(
1087 __isl_take isl_ast_graft_list *list)
1089 return isl_ast_graft_list_sort(list, &cmp_graft, NULL);
1092 /* Merge the given two lists into a single list of grafts,
1093 * merging grafts with the same guard into a single graft.
1095 * "list2" has been sorted using isl_ast_graft_list_sort.
1096 * "list1" may be the result of a previous call to isl_ast_graft_list_merge
1097 * and may therefore not be completely sorted.
1099 * The elements in "list2" need to be executed after those in "list1",
1100 * but if the guard of a graft in "list2" is disjoint from the guards
1101 * of some final elements in "list1", then it can be moved up to before
1102 * those final elements.
1104 * In particular, we look at each element g of "list2" in turn
1105 * and move it up beyond elements of "list1" that would be sorted
1106 * after g as long as each of these elements has a guard that is disjoint
1109 * We do not allow the second or any later element of "list2" to be moved
1110 * before a previous elements of "list2" even if the reason that
1111 * that element didn't move up further was that its guard was not disjoint
1112 * from that of the previous element in "list1".
1114 __isl_give isl_ast_graft_list *isl_ast_graft_list_merge(
1115 __isl_take isl_ast_graft_list *list1,
1116 __isl_take isl_ast_graft_list *list2,
1117 __isl_keep isl_ast_build *build)
1121 if (!list1 || !list2 || !build)
1123 if (list2->n == 0) {
1124 isl_ast_graft_list_free(list2);
1127 if (list1->n == 0) {
1128 isl_ast_graft_list_free(list1);
1133 for (i = 0; i < list2->n; ++i) {
1134 isl_ast_graft *graft;
1135 graft = isl_ast_graft_list_get_ast_graft(list2, i);
1139 for (j = list1->n; j >= 0; --j) {
1141 isl_ast_graft *graft_j;
1146 cmp = isl_set_plain_cmp(list1->p[j - 1]->guard,
1149 disjoint = isl_set_is_disjoint(graft->guard,
1150 list1->p[j - 1]->guard);
1152 list1 = isl_ast_graft_list_free(list1);
1161 list1 = isl_ast_graft_list_insert(list1, j,
1168 graft_j = isl_ast_graft_list_get_ast_graft(list1, j);
1169 graft_j = isl_ast_graft_fuse(graft_j, graft, build);
1170 list1 = isl_ast_graft_list_set_ast_graft(list1, j,
1176 isl_die(isl_ast_build_get_ctx(build),
1178 "element failed to get inserted", break);
1185 list1 = isl_ast_graft_list_free(list1);
1186 isl_ast_graft_list_free(list2);
1190 isl_ast_graft_list_free(list1);
1191 isl_ast_graft_list_free(list2);
1195 __isl_give isl_printer *isl_printer_print_ast_graft(__isl_take isl_printer *p,
1196 __isl_keep isl_ast_graft *graft)
1201 return isl_printer_free(p);
1203 p = isl_printer_print_str(p, "(");
1204 p = isl_printer_print_str(p, "guard: ");
1205 p = isl_printer_print_set(p, graft->guard);
1206 p = isl_printer_print_str(p, ", ");
1207 p = isl_printer_print_str(p, "enforced: ");
1208 p = isl_printer_print_basic_set(p, graft->enforced);
1209 p = isl_printer_print_str(p, ", ");
1210 p = isl_printer_print_str(p, "node: ");
1211 p = isl_printer_print_ast_node(p, graft->node);
1212 p = isl_printer_print_str(p, ")");