declare isl_union_pw_multi_aff_gist
[isl.git] / isl_ast_graft.c
blob611ef5dcf6e737ea3e6f9eb340ae3623aead84d4
1 /*
2 * Copyright 2012 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
9 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
10 * B.P. 105 - 78153 Le Chesnay, France
13 #include <isl_ast_private.h>
14 #include <isl_ast_build_expr.h>
15 #include <isl_ast_build_private.h>
16 #include <isl_ast_graft_private.h>
18 static __isl_give isl_ast_graft *isl_ast_graft_copy(
19 __isl_keep isl_ast_graft *graft);
21 #undef BASE
22 #define BASE ast_graft
24 #include <isl_list_templ.c>
26 #undef BASE
27 #define BASE ast_graft
28 #include <print_templ.c>
30 isl_ctx *isl_ast_graft_get_ctx(__isl_keep isl_ast_graft *graft)
32 if (!graft)
33 return NULL;
34 return isl_basic_set_get_ctx(graft->enforced);
37 __isl_give isl_ast_node *isl_ast_graft_get_node(
38 __isl_keep isl_ast_graft *graft)
40 return graft ? isl_ast_node_copy(graft->node) : NULL;
43 /* Create a graft for "node" with no guards and no enforced conditions.
45 __isl_give isl_ast_graft *isl_ast_graft_alloc(
46 __isl_take isl_ast_node *node, __isl_keep isl_ast_build *build)
48 isl_ctx *ctx;
49 isl_space *space;
50 isl_ast_graft *graft;
52 if (!node)
53 return NULL;
55 ctx = isl_ast_node_get_ctx(node);
56 graft = isl_calloc_type(ctx, isl_ast_graft);
57 if (!graft)
58 goto error;
60 space = isl_ast_build_get_space(build, 1);
62 graft->ref = 1;
63 graft->node = node;
64 graft->guard = isl_set_universe(isl_space_copy(space));
65 graft->enforced = isl_basic_set_universe(space);
67 if (!graft->guard || !graft->enforced)
68 return isl_ast_graft_free(graft);
70 return graft;
71 error:
72 isl_ast_node_free(node);
73 return NULL;
76 /* Create a graft with no guards and no enforced conditions
77 * encapsulating a call to the domain element specified by "executed".
78 * "executed" is assumed to be single-valued.
80 __isl_give isl_ast_graft *isl_ast_graft_alloc_domain(
81 __isl_take isl_map *executed, __isl_keep isl_ast_build *build)
83 isl_ast_node *node;
85 node = isl_ast_build_call_from_executed(build, executed);
87 return isl_ast_graft_alloc(node, build);
90 static __isl_give isl_ast_graft *isl_ast_graft_copy(
91 __isl_keep isl_ast_graft *graft)
93 if (!graft)
94 return NULL;
96 graft->ref++;
97 return graft;
100 /* Do all the grafts in "list" have the same guard and is this guard
101 * independent of the current depth?
103 static int equal_independent_guards(__isl_keep isl_ast_graft_list *list,
104 __isl_keep isl_ast_build *build)
106 int i, n;
107 int depth;
108 isl_ast_graft *graft_0;
109 int equal = 1;
110 int skip;
112 graft_0 = isl_ast_graft_list_get_ast_graft(list, 0);
113 if (!graft_0)
114 return -1;
116 depth = isl_ast_build_get_depth(build);
117 skip = isl_set_involves_dims(graft_0->guard, isl_dim_set, depth, 1);
118 if (skip < 0 || skip) {
119 isl_ast_graft_free(graft_0);
120 return skip < 0 ? -1 : 0;
123 n = isl_ast_graft_list_n_ast_graft(list);
124 for (i = 1; i < n; ++i) {
125 isl_ast_graft *graft;
126 graft = isl_ast_graft_list_get_ast_graft(list, i);
127 if (!graft)
128 equal = -1;
129 else
130 equal = isl_set_is_equal(graft_0->guard, graft->guard);
131 isl_ast_graft_free(graft);
132 if (equal < 0 || !equal)
133 break;
136 isl_ast_graft_free(graft_0);
138 return equal;
141 /* Hoist "guard" out of the current level (given by "build").
143 * In particular, eliminate the dimension corresponding to the current depth.
145 static __isl_give isl_set *hoist_guard(__isl_take isl_set *guard,
146 __isl_keep isl_ast_build *build)
148 int depth;
150 depth = isl_ast_build_get_depth(build);
151 if (depth < isl_set_dim(guard, isl_dim_set)) {
152 guard = isl_set_remove_divs_involving_dims(guard,
153 isl_dim_set, depth, 1);
154 guard = isl_set_eliminate(guard, isl_dim_set, depth, 1);
155 guard = isl_set_compute_divs(guard);
158 return guard;
161 /* Extract a common guard from the grafts in "list" that can be hoisted
162 * out of the current level. If no such guard can be found, then return
163 * a universal set.
165 * If all the grafts in the list have the same guard and if this guard
166 * is independent of the current level, then it can be hoisted out.
167 * If there is only one graft in the list and if its guard
168 * depends on the current level, then we eliminate this level and
169 * return the result.
171 * Otherwise, we return the unshifted simple hull of the guards.
172 * In order to be able to hoist as many constraints as possible,
173 * but at the same time avoid hoisting constraints that did not
174 * appear in the guards in the first place, we intersect the guards
175 * with all the information that is available (i.e., the domain
176 * from the build and the enforced constraints of the graft) and
177 * compute the unshifted hull of the result using only constraints
178 * from the original guards.
179 * In particular, intersecting the guards with other known information
180 * allows us to hoist guards that are only explicit is some of
181 * the grafts and implicit in the others.
183 * The special case for equal guards is needed in case those guards
184 * are non-convex. Taking the simple hull would remove information
185 * and would not allow for these guards to be hoisted completely.
187 __isl_give isl_set *isl_ast_graft_list_extract_hoistable_guard(
188 __isl_keep isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
190 int i, n;
191 int equal;
192 isl_ctx *ctx;
193 isl_set *guard;
194 isl_set_list *set_list;
195 isl_basic_set *hull;
197 if (!list || !build)
198 return NULL;
200 n = isl_ast_graft_list_n_ast_graft(list);
201 if (n == 0)
202 return isl_set_universe(isl_ast_build_get_space(build, 1));
204 equal = equal_independent_guards(list, build);
205 if (equal < 0)
206 return NULL;
208 if (equal || n == 1) {
209 isl_ast_graft *graft_0;
211 graft_0 = isl_ast_graft_list_get_ast_graft(list, 0);
212 if (!graft_0)
213 return NULL;
214 guard = isl_set_copy(graft_0->guard);
215 if (!equal)
216 guard = hoist_guard(guard, build);
217 isl_ast_graft_free(graft_0);
218 return guard;
221 ctx = isl_ast_build_get_ctx(build);
222 set_list = isl_set_list_alloc(ctx, n);
223 guard = isl_set_empty(isl_ast_build_get_space(build, 1));
224 for (i = 0; i < n; ++i) {
225 isl_ast_graft *graft;
226 isl_basic_set *enforced;
227 isl_set *guard_i;
229 graft = isl_ast_graft_list_get_ast_graft(list, i);
230 enforced = isl_ast_graft_get_enforced(graft);
231 guard_i = isl_set_copy(graft->guard);
232 isl_ast_graft_free(graft);
233 set_list = isl_set_list_add(set_list, isl_set_copy(guard_i));
234 guard_i = isl_set_intersect(guard_i,
235 isl_set_from_basic_set(enforced));
236 guard_i = isl_set_intersect(guard_i,
237 isl_ast_build_get_domain(build));
238 guard = isl_set_union(guard, guard_i);
240 hull = isl_set_unshifted_simple_hull_from_set_list(guard, set_list);
241 guard = isl_set_from_basic_set(hull);
242 return hoist_guard(guard, build);
245 /* Internal data structure used inside insert_if.
247 * list is the list of guarded nodes created by each call to insert_if.
248 * node is the original node that is guarded by insert_if.
249 * build is the build in which the AST is constructed.
251 struct isl_insert_if_data {
252 isl_ast_node_list *list;
253 isl_ast_node *node;
254 isl_ast_build *build;
257 static int insert_if(__isl_take isl_basic_set *bset, void *user);
259 /* Insert an if node around "node" testing the condition encoded
260 * in guard "guard".
262 * If the user does not want any disjunctions in the if conditions
263 * and if "guard" does involve a disjunction, then we make the different
264 * disjuncts disjoint and insert an if node corresponding to each disjunct
265 * around a copy of "node". The result is then a block node containing
266 * this sequence of guarded copies of "node".
268 static __isl_give isl_ast_node *ast_node_insert_if(
269 __isl_take isl_ast_node *node, __isl_take isl_set *guard,
270 __isl_keep isl_ast_build *build)
272 struct isl_insert_if_data data;
273 isl_ctx *ctx;
275 ctx = isl_ast_build_get_ctx(build);
276 if (isl_options_get_ast_build_allow_or(ctx) ||
277 isl_set_n_basic_set(guard) <= 1) {
278 isl_ast_node *if_node;
279 isl_ast_expr *expr;
281 expr = isl_ast_build_expr_from_set(build, guard);
283 if_node = isl_ast_node_alloc_if(expr);
284 return isl_ast_node_if_set_then(if_node, node);
287 guard = isl_set_make_disjoint(guard);
289 data.list = isl_ast_node_list_alloc(ctx, 0);
290 data.node = node;
291 data.build = build;
292 if (isl_set_foreach_basic_set(guard, &insert_if, &data) < 0)
293 data.list = isl_ast_node_list_free(data.list);
295 isl_set_free(guard);
296 isl_ast_node_free(data.node);
297 return isl_ast_node_alloc_block(data.list);
300 /* Insert an if node around a copy of "data->node" testing the condition
301 * encoded in guard "bset" and add the result to data->list.
303 static int insert_if(__isl_take isl_basic_set *bset, void *user)
305 struct isl_insert_if_data *data = user;
306 isl_ast_node *node;
307 isl_set *set;
309 set = isl_set_from_basic_set(bset);
310 node = isl_ast_node_copy(data->node);
311 node = ast_node_insert_if(node, set, data->build);
312 data->list = isl_ast_node_list_add(data->list, node);
314 return 0;
317 /* Insert an if node around graft->node testing the condition encoded
318 * in guard "guard", assuming guard involves any conditions.
320 static __isl_give isl_ast_graft *insert_if_node(
321 __isl_take isl_ast_graft *graft, __isl_take isl_set *guard,
322 __isl_keep isl_ast_build *build)
324 int univ;
326 if (!graft)
327 goto error;
329 univ = isl_set_plain_is_universe(guard);
330 if (univ < 0)
331 goto error;
332 if (univ) {
333 isl_set_free(guard);
334 return graft;
337 build = isl_ast_build_copy(build);
338 graft->node = ast_node_insert_if(graft->node, guard, build);
339 isl_ast_build_free(build);
341 if (!graft->node)
342 return isl_ast_graft_free(graft);
344 return graft;
345 error:
346 isl_set_free(guard);
347 return isl_ast_graft_free(graft);
350 /* Insert an if node around graft->node testing the condition encoded
351 * in graft->guard, assuming graft->guard involves any conditions.
353 static __isl_give isl_ast_graft *insert_pending_guard_node(
354 __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build)
356 if (!graft)
357 return NULL;
359 return insert_if_node(graft, isl_set_copy(graft->guard), build);
362 /* Replace graft->enforced by "enforced".
364 __isl_give isl_ast_graft *isl_ast_graft_set_enforced(
365 __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced)
367 if (!graft || !enforced)
368 goto error;
370 isl_basic_set_free(graft->enforced);
371 graft->enforced = enforced;
373 return graft;
374 error:
375 isl_basic_set_free(enforced);
376 return isl_ast_graft_free(graft);
379 /* Update "enforced" such that it only involves constraints that are
380 * also enforced by "graft".
382 static __isl_give isl_basic_set *update_enforced(
383 __isl_take isl_basic_set *enforced, __isl_keep isl_ast_graft *graft,
384 int depth)
386 isl_basic_set *enforced_g;
388 enforced_g = isl_ast_graft_get_enforced(graft);
389 if (depth < isl_basic_set_dim(enforced_g, isl_dim_set))
390 enforced_g = isl_basic_set_eliminate(enforced_g,
391 isl_dim_set, depth, 1);
392 enforced_g = isl_basic_set_remove_unknown_divs(enforced_g);
393 enforced_g = isl_basic_set_align_params(enforced_g,
394 isl_basic_set_get_space(enforced));
395 enforced = isl_basic_set_align_params(enforced,
396 isl_basic_set_get_space(enforced_g));
397 enforced = isl_set_simple_hull(isl_basic_set_union(enforced,
398 enforced_g));
400 return enforced;
403 /* Extend the node at *body with node.
405 * If body points to the else branch, then *body may still be NULL.
406 * If so, we simply attach node to this else branch.
407 * Otherwise, we attach a list containing the statements already
408 * attached at *body followed by node.
410 static void extend_body(__isl_keep isl_ast_node **body,
411 __isl_take isl_ast_node *node)
413 isl_ast_node_list *list;
415 if (!*body) {
416 *body = node;
417 return;
420 if ((*body)->type == isl_ast_node_block) {
421 list = isl_ast_node_block_get_children(*body);
422 isl_ast_node_free(*body);
423 } else
424 list = isl_ast_node_list_from_ast_node(*body);
425 list = isl_ast_node_list_add(list, node);
426 *body = isl_ast_node_alloc_block(list);
429 /* Merge "graft" into the last graft of "list".
430 * body points to the then or else branch of an if node in that last graft.
432 * We attach graft->node to this branch and update the enforced
433 * set of the last graft of "list" to take into account the enforced
434 * set of "graft".
436 static __isl_give isl_ast_graft_list *graft_extend_body(
437 __isl_take isl_ast_graft_list *list,
438 __isl_keep isl_ast_node **body, __isl_take isl_ast_graft *graft,
439 __isl_keep isl_ast_build *build)
441 int n;
442 int depth;
443 isl_ast_graft *last;
444 isl_space *space;
445 isl_basic_set *enforced;
447 if (!list || !graft)
448 goto error;
449 extend_body(body, isl_ast_node_copy(graft->node));
450 if (!*body)
451 goto error;
453 n = isl_ast_graft_list_n_ast_graft(list);
454 last = isl_ast_graft_list_get_ast_graft(list, n - 1);
456 depth = isl_ast_build_get_depth(build);
457 space = isl_ast_build_get_space(build, 1);
458 enforced = isl_basic_set_empty(space);
459 enforced = update_enforced(enforced, last, depth);
460 enforced = update_enforced(enforced, graft, depth);
461 last = isl_ast_graft_set_enforced(last, enforced);
463 list = isl_ast_graft_list_set_ast_graft(list, n - 1, last);
464 isl_ast_graft_free(graft);
465 return list;
466 error:
467 isl_ast_graft_free(graft);
468 return isl_ast_graft_list_free(list);
471 /* Merge "graft" into the last graft of "list", attaching graft->node
472 * to the then branch of "last_if".
474 static __isl_give isl_ast_graft_list *extend_then(
475 __isl_take isl_ast_graft_list *list,
476 __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft,
477 __isl_keep isl_ast_build *build)
479 return graft_extend_body(list, &last_if->u.i.then, graft, build);
482 /* Merge "graft" into the last graft of "list", attaching graft->node
483 * to the else branch of "last_if".
485 static __isl_give isl_ast_graft_list *extend_else(
486 __isl_take isl_ast_graft_list *list,
487 __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft,
488 __isl_keep isl_ast_build *build)
490 return graft_extend_body(list, &last_if->u.i.else_node, graft, build);
493 /* This data structure keeps track of an if node.
495 * "node" is the actual if-node
496 * "guard" is the original, non-simplified guard of the node
497 * "complement" is the complement of "guard" in the context of outer if nodes
499 struct isl_if_node {
500 isl_ast_node *node;
501 isl_set *guard;
502 isl_set *complement;
505 /* Given a list of "n" if nodes, clear those starting at "first"
506 * and return "first" (i.e., the updated size of the array).
508 static int clear_if_nodes(struct isl_if_node *if_node, int first, int n)
510 int i;
512 for (i = first; i < n; ++i) {
513 isl_set_free(if_node[i].guard);
514 isl_set_free(if_node[i].complement);
517 return first;
520 /* For each graft in "list",
521 * insert an if node around graft->node testing the condition encoded
522 * in graft->guard, assuming graft->guard involves any conditions.
524 * We keep track of a list of generated if nodes that can be extended
525 * without changing the order of the elements in "list".
526 * If the guard of a graft is a subset of either the guard or its complement
527 * of one of those if nodes, then the node
528 * of the new graft is inserted into the then or else branch of the last graft
529 * and the current graft is discarded.
530 * The guard of the node is then simplified based on the conditions
531 * enforced at that then or else branch.
532 * Otherwise, the current graft is appended to the list.
534 * We only construct else branches if allowed by the user.
536 static __isl_give isl_ast_graft_list *insert_pending_guard_nodes(
537 __isl_take isl_ast_graft_list *list,
538 __isl_keep isl_ast_build *build)
540 int i, j, n, n_if;
541 int allow_else;
542 isl_ctx *ctx;
543 isl_ast_graft_list *res;
544 struct isl_if_node *if_node = NULL;
546 if (!build || !list)
547 return isl_ast_graft_list_free(list);
549 ctx = isl_ast_build_get_ctx(build);
550 n = isl_ast_graft_list_n_ast_graft(list);
552 allow_else = isl_options_get_ast_build_allow_else(ctx);
554 n_if = 0;
555 if (n > 1) {
556 if_node = isl_alloc_array(ctx, struct isl_if_node, n - 1);
557 if (!if_node)
558 return isl_ast_graft_list_free(list);
561 res = isl_ast_graft_list_alloc(ctx, n);
563 for (i = 0; i < n; ++i) {
564 isl_set *guard;
565 isl_ast_graft *graft;
566 int subset, found_then, found_else;
567 isl_ast_node *node;
569 graft = isl_ast_graft_list_get_ast_graft(list, i);
570 if (!graft)
571 break;
572 subset = 0;
573 found_then = found_else = -1;
574 if (n_if > 0) {
575 isl_set *test;
576 test = isl_set_copy(graft->guard);
577 test = isl_set_intersect(test,
578 isl_set_copy(build->domain));
579 for (j = n_if - 1; j >= 0; --j) {
580 subset = isl_set_is_subset(test,
581 if_node[j].guard);
582 if (subset < 0 || subset) {
583 found_then = j;
584 break;
586 if (!allow_else)
587 continue;
588 subset = isl_set_is_subset(test,
589 if_node[j].complement);
590 if (subset < 0 || subset) {
591 found_else = j;
592 break;
595 n_if = clear_if_nodes(if_node, j + 1, n_if);
596 isl_set_free(test);
598 if (subset < 0) {
599 graft = isl_ast_graft_free(graft);
600 break;
603 guard = isl_set_copy(graft->guard);
604 if (found_then >= 0)
605 graft->guard = isl_set_gist(graft->guard,
606 isl_set_copy(if_node[found_then].guard));
607 else if (found_else >= 0)
608 graft->guard = isl_set_gist(graft->guard,
609 isl_set_copy(if_node[found_else].complement));
611 node = graft->node;
612 if (!graft->guard)
613 graft = isl_ast_graft_free(graft);
614 graft = insert_pending_guard_node(graft, build);
615 if (graft && graft->node != node && i != n - 1) {
616 isl_set *set;
617 if_node[n_if].node = graft->node;
618 if_node[n_if].guard = guard;
619 if (found_then >= 0)
620 set = if_node[found_then].guard;
621 else if (found_else >= 0)
622 set = if_node[found_else].complement;
623 else
624 set = build->domain;
625 set = isl_set_copy(set);
626 set = isl_set_subtract(set, isl_set_copy(guard));
627 if_node[n_if].complement = set;
628 n_if++;
629 } else
630 isl_set_free(guard);
631 if (!graft)
632 break;
634 if (found_then >= 0)
635 res = extend_then(res, if_node[found_then].node,
636 graft, build);
637 else if (found_else >= 0)
638 res = extend_else(res, if_node[found_else].node,
639 graft, build);
640 else
641 res = isl_ast_graft_list_add(res, graft);
643 if (i < n)
644 res = isl_ast_graft_list_free(res);
646 isl_ast_graft_list_free(list);
647 clear_if_nodes(if_node, 0, n_if);
648 free(if_node);
649 return res;
652 /* Collect the nodes contained in the grafts in "list" in a node list.
654 static __isl_give isl_ast_node_list *extract_node_list(
655 __isl_keep isl_ast_graft_list *list)
657 int i, n;
658 isl_ctx *ctx;
659 isl_ast_node_list *node_list;
661 if (!list)
662 return NULL;
663 ctx = isl_ast_graft_list_get_ctx(list);
664 n = isl_ast_graft_list_n_ast_graft(list);
665 node_list = isl_ast_node_list_alloc(ctx, n);
666 for (i = 0; i < n; ++i) {
667 isl_ast_node *node;
668 isl_ast_graft *graft;
670 graft = isl_ast_graft_list_get_ast_graft(list, i);
671 node = isl_ast_graft_get_node(graft);
672 node_list = isl_ast_node_list_add(node_list, node);
673 isl_ast_graft_free(graft);
676 return node_list;
679 /* Look for shared enforced constraints by all the elements in "list"
680 * on outer loops (with respect to the current depth) and return the result.
682 * We assume that the number of children is at least one.
684 __isl_give isl_basic_set *isl_ast_graft_list_extract_shared_enforced(
685 __isl_keep isl_ast_graft_list *list,
686 __isl_keep isl_ast_build *build)
688 int i, n;
689 int depth;
690 isl_space *space;
691 isl_basic_set *enforced;
693 if (!list)
694 return NULL;
696 n = isl_ast_graft_list_n_ast_graft(list);
697 if (n == 0)
698 isl_die(isl_ast_graft_list_get_ctx(list), isl_error_invalid,
699 "for node should have at least one child",
700 return NULL);
702 space = isl_ast_build_get_space(build, 1);
703 enforced = isl_basic_set_empty(space);
705 depth = isl_ast_build_get_depth(build);
706 for (i = 0; i < n; ++i) {
707 isl_ast_graft *graft;
709 graft = isl_ast_graft_list_get_ast_graft(list, i);
710 enforced = update_enforced(enforced, graft, depth);
711 isl_ast_graft_free(graft);
714 return enforced;
717 /* Record "guard" in "graft" so that it will be enforced somewhere
718 * up the tree. If the graft already has a guard, then it may be partially
719 * redundant in combination with the new guard and in the context
720 * the generated constraints of "build". In fact, the new guard
721 * may in itself have some redundant constraints.
722 * We therefore (re)compute the gist of the intersection
723 * and coalesce the result.
725 static __isl_give isl_ast_graft *store_guard(__isl_take isl_ast_graft *graft,
726 __isl_take isl_set *guard, __isl_keep isl_ast_build *build)
728 int is_universe;
730 if (!graft)
731 goto error;
733 is_universe = isl_set_plain_is_universe(guard);
734 if (is_universe < 0)
735 goto error;
736 if (is_universe) {
737 isl_set_free(guard);
738 return graft;
741 graft->guard = isl_set_intersect(graft->guard, guard);
742 graft->guard = isl_set_gist(graft->guard,
743 isl_ast_build_get_generated(build));
744 graft->guard = isl_set_coalesce(graft->guard);
745 if (!graft->guard)
746 return isl_ast_graft_free(graft);
748 return graft;
749 error:
750 isl_set_free(guard);
751 return isl_ast_graft_free(graft);
754 /* For each graft in "list", replace its guard with the gist with
755 * respect to "context".
757 static __isl_give isl_ast_graft_list *gist_guards(
758 __isl_take isl_ast_graft_list *list, __isl_keep isl_set *context)
760 int i, n;
762 if (!list)
763 return NULL;
765 n = isl_ast_graft_list_n_ast_graft(list);
766 for (i = 0; i < n; ++i) {
767 isl_ast_graft *graft;
769 graft = isl_ast_graft_list_get_ast_graft(list, i);
770 if (!graft)
771 break;
772 graft->guard = isl_set_gist(graft->guard,
773 isl_set_copy(context));
774 if (!graft->guard)
775 graft = isl_ast_graft_free(graft);
776 list = isl_ast_graft_list_set_ast_graft(list, i, graft);
778 if (i < n)
779 return isl_ast_graft_list_free(list);
781 return list;
784 /* For each graft in "list", replace its guard with the gist with
785 * respect to "context".
787 __isl_give isl_ast_graft_list *isl_ast_graft_list_gist_guards(
788 __isl_take isl_ast_graft_list *list, __isl_take isl_set *context)
790 list = gist_guards(list, context);
791 isl_set_free(context);
793 return list;
796 /* Allocate a graft in "build" based on the list of grafts in "sub_build".
797 * "guard" and "enforced" are the guard and enforced constraints
798 * of the allocated graft. The guard is used to simplify the guards
799 * of the elements in "list".
801 * The node is initialized to either a block containing the nodes of "children"
802 * or, if there is only a single child, the node of that child.
803 * If the current level requires a for node, it should be inserted by
804 * a subsequent call to isl_ast_graft_insert_for.
806 __isl_give isl_ast_graft *isl_ast_graft_alloc_from_children(
807 __isl_take isl_ast_graft_list *list, __isl_take isl_set *guard,
808 __isl_take isl_basic_set *enforced, __isl_keep isl_ast_build *build,
809 __isl_keep isl_ast_build *sub_build)
811 isl_ast_build *guard_build;
812 isl_ast_node *node;
813 isl_ast_node_list *node_list;
814 isl_ast_graft *graft;
816 guard_build = isl_ast_build_copy(sub_build);
817 guard_build = isl_ast_build_replace_pending_by_guard(guard_build,
818 isl_set_copy(guard));
819 list = gist_guards(list, guard);
820 list = insert_pending_guard_nodes(list, guard_build);
821 isl_ast_build_free(guard_build);
823 node_list = extract_node_list(list);
824 node = isl_ast_node_from_ast_node_list(node_list);
825 isl_ast_graft_list_free(list);
827 graft = isl_ast_graft_alloc(node, build);
828 graft = store_guard(graft, guard, build);
829 graft = isl_ast_graft_enforce(graft, enforced);
831 return graft;
834 /* Combine the grafts in the list into a single graft.
836 * The guard is initialized to the shared guard of the list elements (if any),
837 * provided it does not depend on the current dimension.
838 * The guards in the elements are then simplified with respect to the
839 * hoisted guard and materialized as if nodes around the contained AST nodes
840 * in the context of "sub_build".
842 * The enforced set is initialized to the simple hull of the enforced sets
843 * of the elements, provided the ast_build_exploit_nested_bounds option is set
844 * or the new graft will be used at the same level.
846 * The node is initialized to either a block containing the nodes of "list"
847 * or, if there is only a single element, the node of that element.
849 static __isl_give isl_ast_graft *ast_graft_list_fuse(
850 __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
852 isl_ast_graft *graft;
853 isl_basic_set *enforced;
854 isl_set *guard;
856 if (!list)
857 return NULL;
859 enforced = isl_ast_graft_list_extract_shared_enforced(list, build);
860 guard = isl_ast_graft_list_extract_hoistable_guard(list, build);
861 graft = isl_ast_graft_alloc_from_children(list, guard, enforced,
862 build, build);
864 return graft;
867 /* Combine the grafts in the list into a single graft.
868 * Return a list containing this single graft.
869 * If the original list is empty, then return an empty list.
871 __isl_give isl_ast_graft_list *isl_ast_graft_list_fuse(
872 __isl_take isl_ast_graft_list *list,
873 __isl_keep isl_ast_build *build)
875 isl_ast_graft *graft;
877 if (!list)
878 return NULL;
879 if (isl_ast_graft_list_n_ast_graft(list) <= 1)
880 return list;
881 graft = ast_graft_list_fuse(list, build);
882 return isl_ast_graft_list_from_ast_graft(graft);
885 /* Combine the two grafts into a single graft.
886 * Return a list containing this single graft.
888 static __isl_give isl_ast_graft *isl_ast_graft_fuse(
889 __isl_take isl_ast_graft *graft1, __isl_take isl_ast_graft *graft2,
890 __isl_keep isl_ast_build *build)
892 isl_ctx *ctx;
893 isl_ast_graft_list *list;
895 ctx = isl_ast_build_get_ctx(build);
897 list = isl_ast_graft_list_alloc(ctx, 2);
898 list = isl_ast_graft_list_add(list, graft1);
899 list = isl_ast_graft_list_add(list, graft2);
901 return ast_graft_list_fuse(list, build);
904 /* Insert a for node enclosing the current graft->node.
906 __isl_give isl_ast_graft *isl_ast_graft_insert_for(
907 __isl_take isl_ast_graft *graft, __isl_take isl_ast_node *node)
909 if (!graft)
910 goto error;
912 graft->node = isl_ast_node_for_set_body(node, graft->node);
913 if (!graft->node)
914 return isl_ast_graft_free(graft);
916 return graft;
917 error:
918 isl_ast_node_free(node);
919 isl_ast_graft_free(graft);
920 return NULL;
923 /* Represent the graft list as an AST node.
924 * This operation drops the information about guards in the grafts, so
925 * if there are any pending guards, then they are materialized as if nodes.
927 __isl_give isl_ast_node *isl_ast_node_from_graft_list(
928 __isl_take isl_ast_graft_list *list,
929 __isl_keep isl_ast_build *build)
931 isl_ast_node_list *node_list;
933 list = insert_pending_guard_nodes(list, build);
934 node_list = extract_node_list(list);
935 isl_ast_graft_list_free(list);
937 return isl_ast_node_from_ast_node_list(node_list);
940 void *isl_ast_graft_free(__isl_take isl_ast_graft *graft)
942 if (!graft)
943 return NULL;
945 if (--graft->ref > 0)
946 return NULL;
948 isl_ast_node_free(graft->node);
949 isl_set_free(graft->guard);
950 isl_basic_set_free(graft->enforced);
951 free(graft);
953 return NULL;
956 /* Record that the grafted tree enforces
957 * "enforced" by intersecting graft->enforced with "enforced".
959 __isl_give isl_ast_graft *isl_ast_graft_enforce(
960 __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced)
962 if (!graft || !enforced)
963 goto error;
965 enforced = isl_basic_set_align_params(enforced,
966 isl_basic_set_get_space(graft->enforced));
967 graft->enforced = isl_basic_set_align_params(graft->enforced,
968 isl_basic_set_get_space(enforced));
969 graft->enforced = isl_basic_set_intersect(graft->enforced, enforced);
970 if (!graft->enforced)
971 return isl_ast_graft_free(graft);
973 return graft;
974 error:
975 isl_basic_set_free(enforced);
976 return isl_ast_graft_free(graft);
979 __isl_give isl_basic_set *isl_ast_graft_get_enforced(
980 __isl_keep isl_ast_graft *graft)
982 return graft ? isl_basic_set_copy(graft->enforced) : NULL;
985 __isl_give isl_set *isl_ast_graft_get_guard(__isl_keep isl_ast_graft *graft)
987 return graft ? isl_set_copy(graft->guard) : NULL;
990 /* Record that "guard" needs to be inserted in "graft".
992 __isl_give isl_ast_graft *isl_ast_graft_add_guard(
993 __isl_take isl_ast_graft *graft,
994 __isl_take isl_set *guard, __isl_keep isl_ast_build *build)
996 return store_guard(graft, guard, build);
999 /* Reformulate the "graft", which was generated in the context
1000 * of an inner code generation, in terms of the outer code generation
1001 * AST build.
1003 * If "product" is set, then the domain of the inner code generation build is
1005 * [O -> S]
1007 * with O the domain of the outer code generation build.
1008 * We essentially need to project out S.
1010 * If "product" is not set, then we need to project the domains onto
1011 * their parameter spaces.
1013 __isl_give isl_ast_graft *isl_ast_graft_unembed(__isl_take isl_ast_graft *graft,
1014 int product)
1016 isl_basic_set *enforced;
1018 if (!graft)
1019 return NULL;
1021 if (product) {
1022 enforced = graft->enforced;
1023 enforced = isl_basic_map_domain(isl_basic_set_unwrap(enforced));
1024 graft->enforced = enforced;
1025 graft->guard = isl_map_domain(isl_set_unwrap(graft->guard));
1026 } else {
1027 graft->enforced = isl_basic_set_params(graft->enforced);
1028 graft->guard = isl_set_params(graft->guard);
1030 graft->guard = isl_set_compute_divs(graft->guard);
1032 if (!graft->enforced || !graft->guard)
1033 return isl_ast_graft_free(graft);
1035 return graft;
1038 /* Reformulate the grafts in "list", which were generated in the context
1039 * of an inner code generation, in terms of the outer code generation
1040 * AST build.
1042 __isl_give isl_ast_graft_list *isl_ast_graft_list_unembed(
1043 __isl_take isl_ast_graft_list *list, int product)
1045 int i, n;
1047 n = isl_ast_graft_list_n_ast_graft(list);
1048 for (i = 0; i < n; ++i) {
1049 isl_ast_graft *graft;
1051 graft = isl_ast_graft_list_get_ast_graft(list, i);
1052 graft = isl_ast_graft_unembed(graft, product);
1053 list = isl_ast_graft_list_set_ast_graft(list, i, graft);
1056 return list;
1059 /* Compute the preimage of "graft" under the function represented by "ma".
1060 * In other words, plug in "ma" in "enforced" and "guard" fields of "graft".
1062 __isl_give isl_ast_graft *isl_ast_graft_preimage_multi_aff(
1063 __isl_take isl_ast_graft *graft, __isl_take isl_multi_aff *ma)
1065 isl_basic_set *enforced;
1067 if (!graft)
1068 return NULL;
1070 enforced = graft->enforced;
1071 graft->enforced = isl_basic_set_preimage_multi_aff(enforced,
1072 isl_multi_aff_copy(ma));
1073 graft->guard = isl_set_preimage_multi_aff(graft->guard, ma);
1075 if (!graft->enforced || !graft->guard)
1076 return isl_ast_graft_free(graft);
1078 return graft;
1081 /* Compute the preimage of all the grafts in "list" under
1082 * the function represented by "ma".
1084 __isl_give isl_ast_graft_list *isl_ast_graft_list_preimage_multi_aff(
1085 __isl_take isl_ast_graft_list *list, __isl_take isl_multi_aff *ma)
1087 int i, n;
1089 n = isl_ast_graft_list_n_ast_graft(list);
1090 for (i = 0; i < n; ++i) {
1091 isl_ast_graft *graft;
1093 graft = isl_ast_graft_list_get_ast_graft(list, i);
1094 graft = isl_ast_graft_preimage_multi_aff(graft,
1095 isl_multi_aff_copy(ma));
1096 list = isl_ast_graft_list_set_ast_graft(list, i, graft);
1099 isl_multi_aff_free(ma);
1100 return list;
1103 /* Compare two grafts based on their guards.
1105 static int cmp_graft(__isl_keep isl_ast_graft *a, __isl_keep isl_ast_graft *b,
1106 void *user)
1108 return isl_set_plain_cmp(a->guard, b->guard);
1111 /* Order the elements in "list" based on their guards.
1113 __isl_give isl_ast_graft_list *isl_ast_graft_list_sort_guard(
1114 __isl_take isl_ast_graft_list *list)
1116 return isl_ast_graft_list_sort(list, &cmp_graft, NULL);
1119 /* Merge the given two lists into a single list of grafts,
1120 * merging grafts with the same guard into a single graft.
1122 * "list2" has been sorted using isl_ast_graft_list_sort.
1123 * "list1" may be the result of a previous call to isl_ast_graft_list_merge
1124 * and may therefore not be completely sorted.
1126 * The elements in "list2" need to be executed after those in "list1",
1127 * but if the guard of a graft in "list2" is disjoint from the guards
1128 * of some final elements in "list1", then it can be moved up to before
1129 * those final elements.
1131 * In particular, we look at each element g of "list2" in turn
1132 * and move it up beyond elements of "list1" that would be sorted
1133 * after g as long as each of these elements has a guard that is disjoint
1134 * from that of g.
1136 * We do not allow the second or any later element of "list2" to be moved
1137 * before a previous elements of "list2" even if the reason that
1138 * that element didn't move up further was that its guard was not disjoint
1139 * from that of the previous element in "list1".
1141 __isl_give isl_ast_graft_list *isl_ast_graft_list_merge(
1142 __isl_take isl_ast_graft_list *list1,
1143 __isl_take isl_ast_graft_list *list2,
1144 __isl_keep isl_ast_build *build)
1146 int i, j, first;
1148 if (!list1 || !list2 || !build)
1149 goto error;
1150 if (list2->n == 0) {
1151 isl_ast_graft_list_free(list2);
1152 return list1;
1154 if (list1->n == 0) {
1155 isl_ast_graft_list_free(list1);
1156 return list2;
1159 first = 0;
1160 for (i = 0; i < list2->n; ++i) {
1161 isl_ast_graft *graft;
1162 graft = isl_ast_graft_list_get_ast_graft(list2, i);
1163 if (!graft)
1164 break;
1166 for (j = list1->n; j >= 0; --j) {
1167 int cmp, disjoint;
1168 isl_ast_graft *graft_j;
1170 if (j == first)
1171 cmp = -1;
1172 else
1173 cmp = isl_set_plain_cmp(list1->p[j - 1]->guard,
1174 graft->guard);
1175 if (cmp > 0) {
1176 disjoint = isl_set_is_disjoint(graft->guard,
1177 list1->p[j - 1]->guard);
1178 if (disjoint < 0) {
1179 list1 = isl_ast_graft_list_free(list1);
1180 break;
1182 if (!disjoint)
1183 cmp = -1;
1185 if (cmp > 0)
1186 continue;
1187 if (cmp < 0) {
1188 list1 = isl_ast_graft_list_insert(list1, j,
1189 graft);
1190 break;
1193 --j;
1195 graft_j = isl_ast_graft_list_get_ast_graft(list1, j);
1196 graft_j = isl_ast_graft_fuse(graft_j, graft, build);
1197 list1 = isl_ast_graft_list_set_ast_graft(list1, j,
1198 graft_j);
1199 break;
1202 if (j < 0)
1203 isl_die(isl_ast_build_get_ctx(build),
1204 isl_error_internal,
1205 "element failed to get inserted", break);
1207 first = j + 1;
1208 if (!list1)
1209 break;
1211 if (i < list2->n)
1212 list1 = isl_ast_graft_list_free(list1);
1213 isl_ast_graft_list_free(list2);
1215 return list1;
1216 error:
1217 isl_ast_graft_list_free(list1);
1218 isl_ast_graft_list_free(list2);
1219 return NULL;
1222 __isl_give isl_printer *isl_printer_print_ast_graft(__isl_take isl_printer *p,
1223 __isl_keep isl_ast_graft *graft)
1225 if (!p)
1226 return NULL;
1227 if (!graft)
1228 return isl_printer_free(p);
1230 p = isl_printer_print_str(p, "(");
1231 p = isl_printer_print_str(p, "guard: ");
1232 p = isl_printer_print_set(p, graft->guard);
1233 p = isl_printer_print_str(p, ", ");
1234 p = isl_printer_print_str(p, "enforced: ");
1235 p = isl_printer_print_basic_set(p, graft->enforced);
1236 p = isl_printer_print_str(p, ", ");
1237 p = isl_printer_print_str(p, "node: ");
1238 p = isl_printer_print_ast_node(p, graft->node);
1239 p = isl_printer_print_str(p, ")");
1241 return p;