isl_map_union_disjoint: check spaces before handling special cases
[isl.git] / isl_ast_graft.c
blobfc97d1caa8a0bd533eeceb33c5981bf4a7d0ec3c
1 /*
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
8 */
10 #include <isl_ast_private.h>
11 #include <isl_ast_build_expr.h>
12 #include <isl_ast_build_private.h>
13 #include <isl_ast_graft_private.h>
15 static __isl_give isl_ast_graft *isl_ast_graft_copy(
16 __isl_keep isl_ast_graft *graft);
18 #undef BASE
19 #define BASE ast_graft
21 #include <isl_list_templ.c>
23 #undef BASE
24 #define BASE ast_graft
25 #include <print_templ.c>
27 isl_ctx *isl_ast_graft_get_ctx(__isl_keep isl_ast_graft *graft)
29 if (!graft)
30 return NULL;
31 return isl_basic_set_get_ctx(graft->enforced);
34 __isl_give isl_ast_node *isl_ast_graft_get_node(
35 __isl_keep isl_ast_graft *graft)
37 return graft ? isl_ast_node_copy(graft->node) : NULL;
40 /* Create a graft for "node" with no guards and no enforced conditions.
42 __isl_give isl_ast_graft *isl_ast_graft_alloc(
43 __isl_take isl_ast_node *node, __isl_keep isl_ast_build *build)
45 isl_ctx *ctx;
46 isl_space *space;
47 isl_ast_graft *graft;
49 if (!node)
50 return NULL;
52 ctx = isl_ast_node_get_ctx(node);
53 graft = isl_calloc_type(ctx, isl_ast_graft);
54 if (!graft)
55 goto error;
57 space = isl_ast_build_get_space(build, 1);
59 graft->ref = 1;
60 graft->node = node;
61 graft->guard = isl_set_universe(isl_space_copy(space));
62 graft->enforced = isl_basic_set_universe(space);
64 if (!graft->guard || !graft->enforced)
65 return isl_ast_graft_free(graft);
67 return graft;
68 error:
69 isl_ast_node_free(node);
70 return NULL;
73 /* Create a graft with no guards and no enforced conditions
74 * encapsulating a call to the domain element specified by "executed".
75 * "executed" is assumed to be single-valued.
77 __isl_give isl_ast_graft *isl_ast_graft_alloc_domain(
78 __isl_take isl_map *executed, __isl_keep isl_ast_build *build)
80 isl_ast_node *node;
82 node = isl_ast_build_call_from_executed(build, executed);
84 return isl_ast_graft_alloc(node, build);
87 static __isl_give isl_ast_graft *isl_ast_graft_copy(
88 __isl_keep isl_ast_graft *graft)
90 if (!graft)
91 return NULL;
93 graft->ref++;
94 return graft;
97 /* Do all the grafts in "list" have the same guard and is this guard
98 * independent of the current depth?
100 static int equal_independent_guards(__isl_keep isl_ast_graft_list *list,
101 __isl_keep isl_ast_build *build)
103 int i, n;
104 int depth;
105 isl_ast_graft *graft_0;
106 int equal = 1;
107 int skip;
109 graft_0 = isl_ast_graft_list_get_ast_graft(list, 0);
110 if (!graft_0)
111 return -1;
113 depth = isl_ast_build_get_depth(build);
114 skip = isl_set_involves_dims(graft_0->guard, isl_dim_set, depth, 1);
115 if (skip < 0 || skip) {
116 isl_ast_graft_free(graft_0);
117 return skip < 0 ? -1 : 0;
120 n = isl_ast_graft_list_n_ast_graft(list);
121 for (i = 1; i < n; ++i) {
122 isl_ast_graft *graft;
123 graft = isl_ast_graft_list_get_ast_graft(list, i);
124 if (!graft)
125 equal = -1;
126 else
127 equal = isl_set_is_equal(graft_0->guard, graft->guard);
128 isl_ast_graft_free(graft);
129 if (equal < 0 || !equal)
130 break;
133 isl_ast_graft_free(graft_0);
135 return equal;
138 /* Extract a common guard from the grafts in "list" that can be hoisted
139 * out of the current level. If no such guard can be found, then return
140 * a universal set.
142 * If all the grafts in the list have the same guard and if this guard
143 * is independent of the current level, then it can be hoisted out.
144 * Otherwise, we return the unshifted simple hull of the guards.
146 * The special case for equal guards is needed in case those guards
147 * are non-convex. Taking the simple hull would remove information
148 * and would not allow for these guards to be hoisted completely.
150 static __isl_give isl_set *extract_hoistable_guard(
151 __isl_keep isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
153 int i, n;
154 int depth;
155 isl_ast_graft *graft_0;
156 int equal;
157 isl_set *guard;
159 if (!list || !build)
160 return NULL;
162 n = isl_ast_graft_list_n_ast_graft(list);
163 if (n == 0)
164 return isl_set_universe(isl_ast_build_get_space(build, 1));
166 equal = equal_independent_guards(list, build);
167 if (equal < 0)
168 return NULL;
170 graft_0 = isl_ast_graft_list_get_ast_graft(list, 0);
171 if (!graft_0)
172 return NULL;
173 guard = isl_set_copy(graft_0->guard);
174 isl_ast_graft_free(graft_0);
175 if (equal)
176 return guard;
178 depth = isl_ast_build_get_depth(build);
179 if (depth < isl_set_dim(guard, isl_dim_set)) {
180 guard = isl_set_remove_divs_involving_dims(guard,
181 isl_dim_set, depth, 1);
182 guard = isl_set_eliminate(guard, isl_dim_set, depth, 1);
183 guard = isl_set_compute_divs(guard);
186 for (i = 1; i < n; ++i) {
187 isl_ast_graft *graft;
188 isl_basic_set *hull;
189 int is_universe;
191 is_universe = isl_set_plain_is_universe(guard);
192 if (is_universe < 0)
193 guard = isl_set_free(guard);
194 if (is_universe)
195 break;
197 graft = isl_ast_graft_list_get_ast_graft(list, i);
198 if (!graft) {
199 guard = isl_set_free(guard);
200 break;
202 guard = isl_set_union(guard, isl_set_copy(graft->guard));
203 hull = isl_set_unshifted_simple_hull(guard);
204 guard = isl_set_from_basic_set(hull);
205 isl_ast_graft_free(graft);
208 return guard;
211 /* Internal data structure used inside insert_if.
213 * list is the list of guarded nodes created by each call to insert_if.
214 * node is the original node that is guarded by insert_if.
215 * build is the build in which the AST is constructed.
217 struct isl_insert_if_data {
218 isl_ast_node_list *list;
219 isl_ast_node *node;
220 isl_ast_build *build;
223 static int insert_if(__isl_take isl_basic_set *bset, void *user);
225 /* Insert an if node around "node" testing the condition encoded
226 * in guard "guard".
228 * If the user does not want any disjunctions in the if conditions
229 * and if "guard" does involve a disjunction, then we make the different
230 * disjuncts disjoint and insert an if node corresponding to each disjunct
231 * around a copy of "node". The result is then a block node containing
232 * this sequence of guarded copies of "node".
234 static __isl_give isl_ast_node *ast_node_insert_if(
235 __isl_take isl_ast_node *node, __isl_take isl_set *guard,
236 __isl_keep isl_ast_build *build)
238 struct isl_insert_if_data data;
239 isl_ctx *ctx;
241 ctx = isl_ast_build_get_ctx(build);
242 if (isl_options_get_ast_build_allow_or(ctx) ||
243 isl_set_n_basic_set(guard) <= 1) {
244 isl_ast_node *if_node;
245 isl_ast_expr *expr;
247 expr = isl_ast_build_expr_from_set(build, guard);
249 if_node = isl_ast_node_alloc_if(expr);
250 return isl_ast_node_if_set_then(if_node, node);
253 guard = isl_set_make_disjoint(guard);
255 data.list = isl_ast_node_list_alloc(ctx, 0);
256 data.node = node;
257 data.build = build;
258 if (isl_set_foreach_basic_set(guard, &insert_if, &data) < 0)
259 data.list = isl_ast_node_list_free(data.list);
261 isl_set_free(guard);
262 isl_ast_node_free(data.node);
263 return isl_ast_node_alloc_block(data.list);
266 /* Insert an if node around a copy of "data->node" testing the condition
267 * encoded in guard "bset" and add the result to data->list.
269 static int insert_if(__isl_take isl_basic_set *bset, void *user)
271 struct isl_insert_if_data *data = user;
272 isl_ast_node *node;
273 isl_set *set;
275 set = isl_set_from_basic_set(bset);
276 node = isl_ast_node_copy(data->node);
277 node = ast_node_insert_if(node, set, data->build);
278 data->list = isl_ast_node_list_add(data->list, node);
280 return 0;
283 /* Insert an if node around graft->node testing the condition encoded
284 * in guard "guard", assuming guard involves any conditions.
286 static __isl_give isl_ast_graft *insert_if_node(
287 __isl_take isl_ast_graft *graft, __isl_take isl_set *guard,
288 __isl_keep isl_ast_build *build)
290 int univ;
292 if (!graft)
293 goto error;
295 univ = isl_set_plain_is_universe(guard);
296 if (univ < 0)
297 goto error;
298 if (univ) {
299 isl_set_free(guard);
300 return graft;
303 build = isl_ast_build_copy(build);
304 build = isl_ast_build_set_enforced(build,
305 isl_ast_graft_get_enforced(graft));
306 graft->node = ast_node_insert_if(graft->node, guard, build);
307 isl_ast_build_free(build);
309 if (!graft->node)
310 return isl_ast_graft_free(graft);
312 return graft;
313 error:
314 isl_set_free(guard);
315 return isl_ast_graft_free(graft);
318 /* Insert an if node around graft->node testing the condition encoded
319 * in graft->guard, assuming graft->guard involves any conditions.
321 static __isl_give isl_ast_graft *insert_pending_guard_node(
322 __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build)
324 if (!graft)
325 return NULL;
327 return insert_if_node(graft, isl_set_copy(graft->guard), build);
330 /* Replace graft->enforced by "enforced".
332 __isl_give isl_ast_graft *isl_ast_graft_set_enforced(
333 __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced)
335 if (!graft || !enforced)
336 goto error;
338 isl_basic_set_free(graft->enforced);
339 graft->enforced = enforced;
341 return graft;
342 error:
343 isl_basic_set_free(enforced);
344 return isl_ast_graft_free(graft);
347 /* Update "enforced" such that it only involves constraints that are
348 * also enforced by "graft".
350 static __isl_give isl_basic_set *update_enforced(
351 __isl_take isl_basic_set *enforced, __isl_keep isl_ast_graft *graft,
352 int depth)
354 isl_basic_set *enforced_g;
356 enforced_g = isl_ast_graft_get_enforced(graft);
357 if (depth < isl_basic_set_dim(enforced_g, isl_dim_set))
358 enforced_g = isl_basic_set_eliminate(enforced_g,
359 isl_dim_set, depth, 1);
360 enforced_g = isl_basic_set_remove_unknown_divs(enforced_g);
361 enforced_g = isl_basic_set_align_params(enforced_g,
362 isl_basic_set_get_space(enforced));
363 enforced = isl_basic_set_align_params(enforced,
364 isl_basic_set_get_space(enforced_g));
365 enforced = isl_set_simple_hull(isl_basic_set_union(enforced,
366 enforced_g));
368 return enforced;
371 /* Extend the node at *body with node.
373 * If body points to the else branch, then *body may still be NULL.
374 * If so, we simply attach node to this else branch.
375 * Otherwise, we attach a list containing the statements already
376 * attached at *body followed by node.
378 static void extend_body(__isl_keep isl_ast_node **body,
379 __isl_take isl_ast_node *node)
381 isl_ast_node_list *list;
383 if (!*body) {
384 *body = node;
385 return;
388 if ((*body)->type == isl_ast_node_block) {
389 list = isl_ast_node_block_get_children(*body);
390 isl_ast_node_free(*body);
391 } else
392 list = isl_ast_node_list_from_ast_node(*body);
393 list = isl_ast_node_list_add(list, node);
394 *body = isl_ast_node_alloc_block(list);
397 /* Merge "graft" into the last graft of "list".
398 * body points to the then or else branch of an if node in that last graft.
400 * We attach graft->node to this branch and update the enforced
401 * set of the last graft of "list" to take into account the enforced
402 * set of "graft".
404 static __isl_give isl_ast_graft_list *graft_extend_body(
405 __isl_take isl_ast_graft_list *list,
406 __isl_keep isl_ast_node **body, __isl_take isl_ast_graft *graft,
407 __isl_keep isl_ast_build *build)
409 int n;
410 int depth;
411 isl_ast_graft *last;
412 isl_space *space;
413 isl_basic_set *enforced;
415 if (!list || !graft)
416 goto error;
417 extend_body(body, isl_ast_node_copy(graft->node));
418 if (!*body)
419 goto error;
421 n = isl_ast_graft_list_n_ast_graft(list);
422 last = isl_ast_graft_list_get_ast_graft(list, n - 1);
424 depth = isl_ast_build_get_depth(build);
425 space = isl_ast_build_get_space(build, 1);
426 enforced = isl_basic_set_empty(space);
427 enforced = update_enforced(enforced, last, depth);
428 enforced = update_enforced(enforced, graft, depth);
429 last = isl_ast_graft_set_enforced(last, enforced);
431 list = isl_ast_graft_list_set_ast_graft(list, n - 1, last);
432 isl_ast_graft_free(graft);
433 return list;
434 error:
435 isl_ast_graft_free(graft);
436 return isl_ast_graft_list_free(list);
439 /* Merge "graft" into the last graft of "list", attaching graft->node
440 * to the then branch of "last_if".
442 static __isl_give isl_ast_graft_list *extend_then(
443 __isl_take isl_ast_graft_list *list,
444 __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft,
445 __isl_keep isl_ast_build *build)
447 return graft_extend_body(list, &last_if->u.i.then, graft, build);
450 /* Merge "graft" into the last graft of "list", attaching graft->node
451 * to the else branch of "last_if".
453 static __isl_give isl_ast_graft_list *extend_else(
454 __isl_take isl_ast_graft_list *list,
455 __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft,
456 __isl_keep isl_ast_build *build)
458 return graft_extend_body(list, &last_if->u.i.else_node, graft, build);
461 /* This data structure keeps track of an if node.
463 * "node" is the actual if-node
464 * "guard" is the original, non-simplified guard of the node
465 * "complement" is the complement of "guard" in the context of outer if nodes
467 struct isl_if_node {
468 isl_ast_node *node;
469 isl_set *guard;
470 isl_set *complement;
473 /* Given a list of "n" if nodes, clear those starting at "first"
474 * and return "first" (i.e., the updated size of the array).
476 static int clear_if_nodes(struct isl_if_node *if_node, int first, int n)
478 int i;
480 for (i = first; i < n; ++i) {
481 isl_set_free(if_node[i].guard);
482 isl_set_free(if_node[i].complement);
485 return first;
488 /* For each graft in "list",
489 * insert an if node around graft->node testing the condition encoded
490 * in graft->guard, assuming graft->guard involves any conditions.
492 * We keep track of a list of generated if nodes that can be extended
493 * without changing the order of the elements in "list".
494 * If the guard of a graft is a subset of either the guard or its complement
495 * of one of those if nodes, then the node
496 * of the new graft is inserted into the then or else branch of the last graft
497 * and the current graft is discarded.
498 * The guard of the node is then simplified based on the conditions
499 * enforced at that then or else branch.
500 * Otherwise, the current graft is appended to the list.
502 * We only construct else branches if allowed by the user.
504 static __isl_give isl_ast_graft_list *insert_pending_guard_nodes(
505 __isl_take isl_ast_graft_list *list,
506 __isl_keep isl_ast_build *build)
508 int i, j, n, n_if;
509 int allow_else;
510 isl_ctx *ctx;
511 isl_ast_graft_list *res;
512 struct isl_if_node *if_node = NULL;
514 if (!build || !list)
515 return isl_ast_graft_list_free(list);
517 ctx = isl_ast_build_get_ctx(build);
518 n = isl_ast_graft_list_n_ast_graft(list);
520 allow_else = isl_options_get_ast_build_allow_else(ctx);
522 n_if = 0;
523 if (n > 1) {
524 if_node = isl_alloc_array(ctx, struct isl_if_node, n - 1);
525 if (!if_node)
526 return isl_ast_graft_list_free(list);
529 res = isl_ast_graft_list_alloc(ctx, n);
531 for (i = 0; i < n; ++i) {
532 isl_set *guard;
533 isl_ast_graft *graft;
534 int subset, found_then, found_else;
535 isl_ast_node *node;
537 graft = isl_ast_graft_list_get_ast_graft(list, i);
538 if (!graft)
539 break;
540 subset = 0;
541 found_then = found_else = -1;
542 if (n_if > 0) {
543 isl_set *test;
544 test = isl_set_copy(graft->guard);
545 test = isl_set_intersect(test,
546 isl_set_copy(build->domain));
547 for (j = n_if - 1; j >= 0; --j) {
548 subset = isl_set_is_subset(test,
549 if_node[j].guard);
550 if (subset < 0 || subset) {
551 found_then = j;
552 break;
554 if (!allow_else)
555 continue;
556 subset = isl_set_is_subset(test,
557 if_node[j].complement);
558 if (subset < 0 || subset) {
559 found_else = j;
560 break;
563 n_if = clear_if_nodes(if_node, j + 1, n_if);
564 isl_set_free(test);
566 if (subset < 0) {
567 graft = isl_ast_graft_free(graft);
568 break;
571 guard = isl_set_copy(graft->guard);
572 if (found_then >= 0)
573 graft->guard = isl_set_gist(graft->guard,
574 isl_set_copy(if_node[found_then].guard));
575 else if (found_else >= 0)
576 graft->guard = isl_set_gist(graft->guard,
577 isl_set_copy(if_node[found_else].complement));
579 node = graft->node;
580 if (!graft->guard)
581 graft = isl_ast_graft_free(graft);
582 graft = insert_pending_guard_node(graft, build);
583 if (graft && graft->node != node && i != n - 1) {
584 isl_set *set;
585 if_node[n_if].node = graft->node;
586 if_node[n_if].guard = guard;
587 if (found_then >= 0)
588 set = if_node[found_then].guard;
589 else if (found_else >= 0)
590 set = if_node[found_else].complement;
591 else
592 set = build->domain;
593 set = isl_set_copy(set);
594 set = isl_set_subtract(set, isl_set_copy(guard));
595 if_node[n_if].complement = set;
596 n_if++;
597 } else
598 isl_set_free(guard);
599 if (!graft)
600 break;
602 if (found_then >= 0)
603 res = extend_then(res, if_node[found_then].node,
604 graft, build);
605 else if (found_else >= 0)
606 res = extend_else(res, if_node[found_else].node,
607 graft, build);
608 else
609 res = isl_ast_graft_list_add(res, graft);
611 if (i < n)
612 res = isl_ast_graft_list_free(res);
614 isl_ast_graft_list_free(list);
615 clear_if_nodes(if_node, 0, n_if);
616 free(if_node);
617 return res;
620 /* Collect the nodes contained in the grafts in "list" in a node list.
622 static __isl_give isl_ast_node_list *extract_node_list(
623 __isl_keep isl_ast_graft_list *list)
625 int i, n;
626 isl_ctx *ctx;
627 isl_ast_node_list *node_list;
629 if (!list)
630 return NULL;
631 ctx = isl_ast_graft_list_get_ctx(list);
632 n = isl_ast_graft_list_n_ast_graft(list);
633 node_list = isl_ast_node_list_alloc(ctx, n);
634 for (i = 0; i < n; ++i) {
635 isl_ast_node *node;
636 isl_ast_graft *graft;
638 graft = isl_ast_graft_list_get_ast_graft(list, i);
639 node = isl_ast_graft_get_node(graft);
640 node_list = isl_ast_node_list_add(node_list, node);
641 isl_ast_graft_free(graft);
644 return node_list;
647 /* Look for shared enforced constraints by all the elements in "list"
648 * on outer loops (with respect to the current depth) and return the result.
650 * We assume that the number of children is at least one.
652 static __isl_give isl_basic_set *extract_shared_enforced(
653 __isl_keep isl_ast_graft_list *list,
654 __isl_keep isl_ast_build *build)
656 int i, n;
657 int depth;
658 isl_space *space;
659 isl_basic_set *enforced;
661 if (!list)
662 return NULL;
664 n = isl_ast_graft_list_n_ast_graft(list);
665 if (n == 0)
666 isl_die(isl_ast_graft_list_get_ctx(list), isl_error_invalid,
667 "for node should have at least one child",
668 return NULL);
670 space = isl_ast_build_get_space(build, 1);
671 enforced = isl_basic_set_empty(space);
673 depth = isl_ast_build_get_depth(build);
674 for (i = 0; i < n; ++i) {
675 isl_ast_graft *graft;
677 graft = isl_ast_graft_list_get_ast_graft(list, i);
678 enforced = update_enforced(enforced, graft, depth);
679 isl_ast_graft_free(graft);
682 return enforced;
685 /* Record "guard" in "graft" so that it will be enforced somewhere
686 * up the tree. If the graft already has a guard, then it may be partially
687 * redundant in combination with the new guard and in the context
688 * of build->domain. We therefore (re)compute the gist of the intersection
689 * and coalesce the result.
691 static __isl_give isl_ast_graft *store_guard(__isl_take isl_ast_graft *graft,
692 __isl_take isl_set *guard, __isl_keep isl_ast_build *build)
694 int is_universe;
696 if (!graft)
697 goto error;
699 is_universe = isl_set_plain_is_universe(guard);
700 if (is_universe < 0)
701 goto error;
702 if (is_universe) {
703 isl_set_free(guard);
704 return graft;
707 graft->guard = isl_set_intersect(graft->guard, guard);
708 graft->guard = isl_ast_build_compute_gist(build, graft->guard);
709 graft->guard = isl_set_coalesce(graft->guard);
710 if (!graft->guard)
711 return isl_ast_graft_free(graft);
713 return graft;
714 error:
715 isl_set_free(guard);
716 return isl_ast_graft_free(graft);
719 /* For each graft in "list", replace its guard with the gist with
720 * respect to "context".
722 static __isl_give isl_ast_graft_list *gist_guards(
723 __isl_take isl_ast_graft_list *list, __isl_keep isl_set *context)
725 int i, n;
727 if (!list)
728 return NULL;
730 n = isl_ast_graft_list_n_ast_graft(list);
731 for (i = 0; i < n; ++i) {
732 isl_ast_graft *graft;
734 graft = isl_ast_graft_list_get_ast_graft(list, i);
735 if (!graft)
736 break;
737 graft->guard = isl_set_gist(graft->guard,
738 isl_set_copy(context));
739 if (!graft->guard)
740 graft = isl_ast_graft_free(graft);
741 list = isl_ast_graft_list_set_ast_graft(list, i, graft);
743 if (i < n)
744 return isl_ast_graft_list_free(list);
746 return list;
749 /* Combine the grafts in the list into a single graft.
751 * If "up" is set then the resulting graft will be used at an outer level.
752 * In this case, "build" refers to the outer level, while "sub_build"
753 * refers to the inner level. If "up" is not set, then the same build
754 * should be passed to both arguments.
756 * The guard is initialized to the shared guard of the list elements (if any),
757 * provided it does not depend on the current dimension.
758 * The guards in the elements are then simplified with respect to the
759 * hoisted guard and materialized as if nodes around the contained AST nodes
760 * in the context of "sub_build".
762 * The enforced set is initialized to the simple hull of the enforced sets
763 * of the elements, provided the ast_build_exploit_nested_bounds option is set
764 * or the new graft will be used at the same level.
766 * The node is initialized to either a block containing the nodes of "list"
767 * or, if there is only a single element, the node of that element.
769 static __isl_give isl_ast_graft *ast_graft_list_fuse(
770 __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build,
771 __isl_keep isl_ast_build *sub_build, int up)
773 isl_ctx *ctx;
774 isl_ast_node *node;
775 isl_ast_graft *graft;
776 isl_ast_node_list *node_list;
777 isl_set *guard;
779 if (!list)
780 return NULL;
782 ctx = isl_ast_build_get_ctx(build);
783 guard = extract_hoistable_guard(list, build);
784 list = gist_guards(list, guard);
785 list = insert_pending_guard_nodes(list, sub_build);
787 node_list = extract_node_list(list);
788 node = isl_ast_node_from_ast_node_list(node_list);
790 graft = isl_ast_graft_alloc(node, build);
792 if (!up || isl_options_get_ast_build_exploit_nested_bounds(ctx)) {
793 isl_basic_set *enforced;
794 enforced = extract_shared_enforced(list, build);
795 graft = isl_ast_graft_enforce(graft, enforced);
798 graft = store_guard(graft, guard, build);
800 isl_ast_graft_list_free(list);
801 return graft;
804 /* Combine the grafts in the list into a single graft.
805 * Return a list containing this single graft.
806 * If the original list is empty, then return an empty list.
808 __isl_give isl_ast_graft_list *isl_ast_graft_list_fuse(
809 __isl_take isl_ast_graft_list *list,
810 __isl_keep isl_ast_build *build)
812 isl_ast_graft *graft;
814 if (!list)
815 return NULL;
816 if (isl_ast_graft_list_n_ast_graft(list) <= 1)
817 return list;
818 graft = ast_graft_list_fuse(list, build, build, 0);
819 return isl_ast_graft_list_from_ast_graft(graft);
822 /* Combine the two grafts into a single graft.
823 * Return a list containing this single graft.
825 static __isl_give isl_ast_graft *isl_ast_graft_fuse(
826 __isl_take isl_ast_graft *graft1, __isl_take isl_ast_graft *graft2,
827 __isl_keep isl_ast_build *build)
829 isl_ctx *ctx;
830 isl_ast_graft_list *list;
832 ctx = isl_ast_build_get_ctx(build);
834 list = isl_ast_graft_list_alloc(ctx, 2);
835 list = isl_ast_graft_list_add(list, graft1);
836 list = isl_ast_graft_list_add(list, graft2);
838 return ast_graft_list_fuse(list, build, build, 0);
841 /* Allocate a graft for the current level based on the list of grafts
842 * of the inner level.
843 * "build" represents the context of the current level.
844 * "sub_build" represents the context of the inner level.
846 * The node is initialized to either a block containing the nodes of "children"
847 * or, if there is only a single child, the node of that child.
848 * If the current level requires a for node, it should be inserted by
849 * a subsequent call to isl_ast_graft_insert_for.
851 __isl_give isl_ast_graft *isl_ast_graft_alloc_level(
852 __isl_take isl_ast_graft_list *children,
853 __isl_keep isl_ast_build *build, __isl_keep isl_ast_build *sub_build)
855 return ast_graft_list_fuse(children, build, sub_build, 1);
858 /* Insert a for node enclosing the current graft->node.
860 __isl_give isl_ast_graft *isl_ast_graft_insert_for(
861 __isl_take isl_ast_graft *graft, __isl_take isl_ast_node *node)
863 if (!graft)
864 goto error;
866 graft->node = isl_ast_node_for_set_body(node, graft->node);
867 if (!graft->node)
868 return isl_ast_graft_free(graft);
870 return graft;
871 error:
872 isl_ast_node_free(node);
873 isl_ast_graft_free(graft);
874 return NULL;
877 /* Represent the graft list as an AST node.
878 * This operation drops the information about guards in the grafts, so
879 * if there are any pending guards, then they are materialized as if nodes.
881 __isl_give isl_ast_node *isl_ast_node_from_graft_list(
882 __isl_take isl_ast_graft_list *list,
883 __isl_keep isl_ast_build *build)
885 isl_ast_node_list *node_list;
887 list = insert_pending_guard_nodes(list, build);
888 node_list = extract_node_list(list);
889 isl_ast_graft_list_free(list);
891 return isl_ast_node_from_ast_node_list(node_list);
894 void *isl_ast_graft_free(__isl_take isl_ast_graft *graft)
896 if (!graft)
897 return NULL;
899 if (--graft->ref > 0)
900 return NULL;
902 isl_ast_node_free(graft->node);
903 isl_set_free(graft->guard);
904 isl_basic_set_free(graft->enforced);
905 free(graft);
907 return NULL;
910 /* Record that the grafted tree enforces
911 * "enforced" by intersecting graft->enforced with "enforced".
913 __isl_give isl_ast_graft *isl_ast_graft_enforce(
914 __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced)
916 if (!graft || !enforced)
917 goto error;
919 enforced = isl_basic_set_align_params(enforced,
920 isl_basic_set_get_space(graft->enforced));
921 graft->enforced = isl_basic_set_align_params(graft->enforced,
922 isl_basic_set_get_space(enforced));
923 graft->enforced = isl_basic_set_intersect(graft->enforced, enforced);
924 if (!graft->enforced)
925 return isl_ast_graft_free(graft);
927 return graft;
928 error:
929 isl_basic_set_free(enforced);
930 return isl_ast_graft_free(graft);
933 __isl_give isl_basic_set *isl_ast_graft_get_enforced(
934 __isl_keep isl_ast_graft *graft)
936 return graft ? isl_basic_set_copy(graft->enforced) : NULL;
939 __isl_give isl_set *isl_ast_graft_get_guard(__isl_keep isl_ast_graft *graft)
941 return graft ? isl_set_copy(graft->guard) : NULL;
944 /* Record that "guard" needs to be inserted in "graft".
946 * We first simplify the guard in the context of the enforced set and
947 * then we store the guard in case we may be able
948 * to hoist it to higher levels and/or combine it with those of other grafts.
950 __isl_give isl_ast_graft *isl_ast_graft_add_guard(
951 __isl_take isl_ast_graft *graft,
952 __isl_take isl_set *guard, __isl_keep isl_ast_build *build)
954 isl_basic_set *enforced;
956 if (!graft || !build)
957 goto error;
959 enforced = isl_basic_set_copy(graft->enforced);
960 guard = isl_set_gist(guard, isl_set_from_basic_set(enforced));
962 graft = store_guard(graft, guard, build);
964 return graft;
965 error:
966 isl_set_free(guard);
967 isl_ast_graft_free(graft);
968 return NULL;
971 /* Reformulate the "graft", which was generated in the context
972 * of an inner code generation, in terms of the outer code generation
973 * AST build.
975 * If "product" is set, then the domain of the inner code generation build is
977 * [O -> S]
979 * with O the domain of the outer code generation build.
980 * We essentially need to project out S.
982 * If "product" is not set, then we need to project the domains onto
983 * their parameter spaces.
985 __isl_give isl_ast_graft *isl_ast_graft_unembed(__isl_take isl_ast_graft *graft,
986 int product)
988 isl_basic_set *enforced;
990 if (!graft)
991 return NULL;
993 if (product) {
994 enforced = graft->enforced;
995 enforced = isl_basic_map_domain(isl_basic_set_unwrap(enforced));
996 graft->enforced = enforced;
997 graft->guard = isl_map_domain(isl_set_unwrap(graft->guard));
998 } else {
999 graft->enforced = isl_basic_set_params(graft->enforced);
1000 graft->guard = isl_set_params(graft->guard);
1002 graft->guard = isl_set_compute_divs(graft->guard);
1004 if (!graft->enforced || !graft->guard)
1005 return isl_ast_graft_free(graft);
1007 return graft;
1010 /* Reformulate the grafts in "list", which were generated in the context
1011 * of an inner code generation, in terms of the outer code generation
1012 * AST build.
1014 __isl_give isl_ast_graft_list *isl_ast_graft_list_unembed(
1015 __isl_take isl_ast_graft_list *list, int product)
1017 int i, n;
1019 n = isl_ast_graft_list_n_ast_graft(list);
1020 for (i = 0; i < n; ++i) {
1021 isl_ast_graft *graft;
1023 graft = isl_ast_graft_list_get_ast_graft(list, i);
1024 graft = isl_ast_graft_unembed(graft, product);
1025 list = isl_ast_graft_list_set_ast_graft(list, i, graft);
1028 return list;
1031 /* Compute the preimage of "graft" under the function represented by "ma".
1032 * In other words, plug in "ma" in "enforced" and "guard" fields of "graft".
1034 __isl_give isl_ast_graft *isl_ast_graft_preimage_multi_aff(
1035 __isl_take isl_ast_graft *graft, __isl_take isl_multi_aff *ma)
1037 isl_basic_set *enforced;
1039 if (!graft)
1040 return NULL;
1042 enforced = graft->enforced;
1043 graft->enforced = isl_basic_set_preimage_multi_aff(enforced,
1044 isl_multi_aff_copy(ma));
1045 graft->guard = isl_set_preimage_multi_aff(graft->guard, ma);
1047 if (!graft->enforced || !graft->guard)
1048 return isl_ast_graft_free(graft);
1050 return graft;
1053 /* Compute the preimage of all the grafts in "list" under
1054 * the function represented by "ma".
1056 __isl_give isl_ast_graft_list *isl_ast_graft_list_preimage_multi_aff(
1057 __isl_take isl_ast_graft_list *list, __isl_take isl_multi_aff *ma)
1059 int i, n;
1061 n = isl_ast_graft_list_n_ast_graft(list);
1062 for (i = 0; i < n; ++i) {
1063 isl_ast_graft *graft;
1065 graft = isl_ast_graft_list_get_ast_graft(list, i);
1066 graft = isl_ast_graft_preimage_multi_aff(graft,
1067 isl_multi_aff_copy(ma));
1068 list = isl_ast_graft_list_set_ast_graft(list, i, graft);
1071 isl_multi_aff_free(ma);
1072 return list;
1075 /* Compare two grafts based on their guards.
1077 static int cmp_graft(__isl_keep isl_ast_graft *a, __isl_keep isl_ast_graft *b,
1078 void *user)
1080 return isl_set_plain_cmp(a->guard, b->guard);
1083 /* Order the elements in "list" based on their guards.
1085 __isl_give isl_ast_graft_list *isl_ast_graft_list_sort_guard(
1086 __isl_take isl_ast_graft_list *list)
1088 return isl_ast_graft_list_sort(list, &cmp_graft, NULL);
1091 /* Merge the given two lists into a single list of grafts,
1092 * merging grafts with the same guard into a single graft.
1094 * "list2" has been sorted using isl_ast_graft_list_sort.
1095 * "list1" may be the result of a previous call to isl_ast_graft_list_merge
1096 * and may therefore not be completely sorted.
1098 * The elements in "list2" need to be executed after those in "list1",
1099 * but if the guard of a graft in "list2" is disjoint from the guards
1100 * of some final elements in "list1", then it can be moved up to before
1101 * those final elements.
1103 * In particular, we look at each element g of "list2" in turn
1104 * and move it up beyond elements of "list1" that would be sorted
1105 * after g as long as each of these elements has a guard that is disjoint
1106 * from that of g.
1108 * We do not allow the second or any later element of "list2" to be moved
1109 * before a previous elements of "list2" even if the reason that
1110 * that element didn't move up further was that its guard was not disjoint
1111 * from that of the previous element in "list1".
1113 __isl_give isl_ast_graft_list *isl_ast_graft_list_merge(
1114 __isl_take isl_ast_graft_list *list1,
1115 __isl_take isl_ast_graft_list *list2,
1116 __isl_keep isl_ast_build *build)
1118 int i, j, first;
1120 if (!list1 || !list2 || !build)
1121 goto error;
1122 if (list2->n == 0) {
1123 isl_ast_graft_list_free(list2);
1124 return list1;
1126 if (list1->n == 0) {
1127 isl_ast_graft_list_free(list1);
1128 return list2;
1131 first = 0;
1132 for (i = 0; i < list2->n; ++i) {
1133 isl_ast_graft *graft;
1134 graft = isl_ast_graft_list_get_ast_graft(list2, i);
1135 if (!graft)
1136 break;
1138 for (j = list1->n; j >= 0; --j) {
1139 int cmp, disjoint;
1140 isl_ast_graft *graft_j;
1142 if (j == first)
1143 cmp = -1;
1144 else
1145 cmp = isl_set_plain_cmp(list1->p[j - 1]->guard,
1146 graft->guard);
1147 if (cmp > 0) {
1148 disjoint = isl_set_is_disjoint(graft->guard,
1149 list1->p[j - 1]->guard);
1150 if (disjoint < 0) {
1151 list1 = isl_ast_graft_list_free(list1);
1152 break;
1154 if (!disjoint)
1155 cmp = -1;
1157 if (cmp > 0)
1158 continue;
1159 if (cmp < 0) {
1160 list1 = isl_ast_graft_list_insert(list1, j,
1161 graft);
1162 break;
1165 --j;
1167 graft_j = isl_ast_graft_list_get_ast_graft(list1, j);
1168 graft_j = isl_ast_graft_fuse(graft_j, graft, build);
1169 list1 = isl_ast_graft_list_set_ast_graft(list1, j,
1170 graft_j);
1171 break;
1174 if (j < 0)
1175 isl_die(isl_ast_build_get_ctx(build),
1176 isl_error_internal,
1177 "element failed to get inserted", break);
1179 first = j + 1;
1180 if (!list1)
1181 break;
1183 if (i < list2->n)
1184 list1 = isl_ast_graft_list_free(list1);
1185 isl_ast_graft_list_free(list2);
1187 return list1;
1188 error:
1189 isl_ast_graft_list_free(list1);
1190 isl_ast_graft_list_free(list2);
1191 return NULL;
1194 __isl_give isl_printer *isl_printer_print_ast_graft(__isl_take isl_printer *p,
1195 __isl_keep isl_ast_graft *graft)
1197 if (!p)
1198 return NULL;
1199 if (!graft)
1200 return isl_printer_free(p);
1202 p = isl_printer_print_str(p, "(");
1203 p = isl_printer_print_str(p, "guard: ");
1204 p = isl_printer_print_set(p, graft->guard);
1205 p = isl_printer_print_str(p, ", ");
1206 p = isl_printer_print_str(p, "enforced: ");
1207 p = isl_printer_print_basic_set(p, graft->enforced);
1208 p = isl_printer_print_str(p, ", ");
1209 p = isl_printer_print_str(p, "node: ");
1210 p = isl_printer_print_ast_node(p, graft->node);
1211 p = isl_printer_print_str(p, ")");
1213 return p;