isl_tab_lexmin_add_eq: make sure the tableau has enough room
[isl.git] / isl_ast_graft.c
blob6d90dd2b49ee9b76a72c16e83cfda85f8da8b338
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 if (isl_set_dim(graft_0->guard, isl_dim_set) <= depth)
118 skip = 0;
119 else
120 skip = isl_set_involves_dims(graft_0->guard,
121 isl_dim_set, depth, 1);
122 if (skip < 0 || skip) {
123 isl_ast_graft_free(graft_0);
124 return skip < 0 ? -1 : 0;
127 n = isl_ast_graft_list_n_ast_graft(list);
128 for (i = 1; i < n; ++i) {
129 isl_ast_graft *graft;
130 graft = isl_ast_graft_list_get_ast_graft(list, i);
131 if (!graft)
132 equal = -1;
133 else
134 equal = isl_set_is_equal(graft_0->guard, graft->guard);
135 isl_ast_graft_free(graft);
136 if (equal < 0 || !equal)
137 break;
140 isl_ast_graft_free(graft_0);
142 return equal;
145 /* Hoist "guard" out of the current level (given by "build").
147 * In particular, eliminate the dimension corresponding to the current depth.
149 static __isl_give isl_set *hoist_guard(__isl_take isl_set *guard,
150 __isl_keep isl_ast_build *build)
152 int depth;
154 depth = isl_ast_build_get_depth(build);
155 if (depth < isl_set_dim(guard, isl_dim_set)) {
156 guard = isl_set_remove_divs_involving_dims(guard,
157 isl_dim_set, depth, 1);
158 guard = isl_set_eliminate(guard, isl_dim_set, depth, 1);
159 guard = isl_set_compute_divs(guard);
162 return guard;
165 /* Extract a common guard from the grafts in "list" that can be hoisted
166 * out of the current level. If no such guard can be found, then return
167 * a universal set.
169 * If all the grafts in the list have the same guard and if this guard
170 * is independent of the current level, then it can be hoisted out.
171 * If there is only one graft in the list and if its guard
172 * depends on the current level, then we eliminate this level and
173 * return the result.
175 * Otherwise, we return the unshifted simple hull of the guards.
176 * In order to be able to hoist as many constraints as possible,
177 * but at the same time avoid hoisting constraints that did not
178 * appear in the guards in the first place, we intersect the guards
179 * with all the information that is available (i.e., the domain
180 * from the build and the enforced constraints of the graft) and
181 * compute the unshifted hull of the result using only constraints
182 * from the original guards.
183 * In particular, intersecting the guards with other known information
184 * allows us to hoist guards that are only explicit is some of
185 * the grafts and implicit in the others.
187 * The special case for equal guards is needed in case those guards
188 * are non-convex. Taking the simple hull would remove information
189 * and would not allow for these guards to be hoisted completely.
191 __isl_give isl_set *isl_ast_graft_list_extract_hoistable_guard(
192 __isl_keep isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
194 int i, n;
195 int equal;
196 isl_ctx *ctx;
197 isl_set *guard;
198 isl_set_list *set_list;
199 isl_basic_set *hull;
201 if (!list || !build)
202 return NULL;
204 n = isl_ast_graft_list_n_ast_graft(list);
205 if (n == 0)
206 return isl_set_universe(isl_ast_build_get_space(build, 1));
208 equal = equal_independent_guards(list, build);
209 if (equal < 0)
210 return NULL;
212 if (equal || n == 1) {
213 isl_ast_graft *graft_0;
215 graft_0 = isl_ast_graft_list_get_ast_graft(list, 0);
216 if (!graft_0)
217 return NULL;
218 guard = isl_set_copy(graft_0->guard);
219 if (!equal)
220 guard = hoist_guard(guard, build);
221 isl_ast_graft_free(graft_0);
222 return guard;
225 ctx = isl_ast_build_get_ctx(build);
226 set_list = isl_set_list_alloc(ctx, n);
227 guard = isl_set_empty(isl_ast_build_get_space(build, 1));
228 for (i = 0; i < n; ++i) {
229 isl_ast_graft *graft;
230 isl_basic_set *enforced;
231 isl_set *guard_i;
233 graft = isl_ast_graft_list_get_ast_graft(list, i);
234 enforced = isl_ast_graft_get_enforced(graft);
235 guard_i = isl_set_copy(graft->guard);
236 isl_ast_graft_free(graft);
237 set_list = isl_set_list_add(set_list, isl_set_copy(guard_i));
238 guard_i = isl_set_intersect(guard_i,
239 isl_set_from_basic_set(enforced));
240 guard_i = isl_set_intersect(guard_i,
241 isl_ast_build_get_domain(build));
242 guard = isl_set_union(guard, guard_i);
244 hull = isl_set_unshifted_simple_hull_from_set_list(guard, set_list);
245 guard = isl_set_from_basic_set(hull);
246 return hoist_guard(guard, build);
249 /* Internal data structure used inside insert_if.
251 * list is the list of guarded nodes created by each call to insert_if.
252 * node is the original node that is guarded by insert_if.
253 * build is the build in which the AST is constructed.
255 struct isl_insert_if_data {
256 isl_ast_node_list *list;
257 isl_ast_node *node;
258 isl_ast_build *build;
261 static isl_stat insert_if(__isl_take isl_basic_set *bset, void *user);
263 /* Insert an if node around "node" testing the condition encoded
264 * in guard "guard".
266 * If the user does not want any disjunctions in the if conditions
267 * and if "guard" does involve a disjunction, then we make the different
268 * disjuncts disjoint and insert an if node corresponding to each disjunct
269 * around a copy of "node". The result is then a block node containing
270 * this sequence of guarded copies of "node".
272 static __isl_give isl_ast_node *ast_node_insert_if(
273 __isl_take isl_ast_node *node, __isl_take isl_set *guard,
274 __isl_keep isl_ast_build *build)
276 struct isl_insert_if_data data;
277 isl_ctx *ctx;
279 ctx = isl_ast_build_get_ctx(build);
280 if (isl_options_get_ast_build_allow_or(ctx) ||
281 isl_set_n_basic_set(guard) <= 1) {
282 isl_ast_node *if_node;
283 isl_ast_expr *expr;
285 expr = isl_ast_build_expr_from_set_internal(build, guard);
287 if_node = isl_ast_node_alloc_if(expr);
288 return isl_ast_node_if_set_then(if_node, node);
291 guard = isl_set_make_disjoint(guard);
293 data.list = isl_ast_node_list_alloc(ctx, 0);
294 data.node = node;
295 data.build = build;
296 if (isl_set_foreach_basic_set(guard, &insert_if, &data) < 0)
297 data.list = isl_ast_node_list_free(data.list);
299 isl_set_free(guard);
300 isl_ast_node_free(data.node);
301 return isl_ast_node_alloc_block(data.list);
304 /* Insert an if node around a copy of "data->node" testing the condition
305 * encoded in guard "bset" and add the result to data->list.
307 static isl_stat insert_if(__isl_take isl_basic_set *bset, void *user)
309 struct isl_insert_if_data *data = user;
310 isl_ast_node *node;
311 isl_set *set;
313 set = isl_set_from_basic_set(bset);
314 node = isl_ast_node_copy(data->node);
315 node = ast_node_insert_if(node, set, data->build);
316 data->list = isl_ast_node_list_add(data->list, node);
318 return isl_stat_ok;
321 /* Insert an if node around graft->node testing the condition encoded
322 * in guard "guard", assuming guard involves any conditions.
324 static __isl_give isl_ast_graft *insert_if_node(
325 __isl_take isl_ast_graft *graft, __isl_take isl_set *guard,
326 __isl_keep isl_ast_build *build)
328 int univ;
330 if (!graft)
331 goto error;
333 univ = isl_set_plain_is_universe(guard);
334 if (univ < 0)
335 goto error;
336 if (univ) {
337 isl_set_free(guard);
338 return graft;
341 build = isl_ast_build_copy(build);
342 graft->node = ast_node_insert_if(graft->node, guard, build);
343 isl_ast_build_free(build);
345 if (!graft->node)
346 return isl_ast_graft_free(graft);
348 return graft;
349 error:
350 isl_set_free(guard);
351 return isl_ast_graft_free(graft);
354 /* Insert an if node around graft->node testing the condition encoded
355 * in graft->guard, assuming graft->guard involves any conditions.
357 static __isl_give isl_ast_graft *insert_pending_guard_node(
358 __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build)
360 if (!graft)
361 return NULL;
363 return insert_if_node(graft, isl_set_copy(graft->guard), build);
366 /* Replace graft->enforced by "enforced".
368 __isl_give isl_ast_graft *isl_ast_graft_set_enforced(
369 __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced)
371 if (!graft || !enforced)
372 goto error;
374 isl_basic_set_free(graft->enforced);
375 graft->enforced = enforced;
377 return graft;
378 error:
379 isl_basic_set_free(enforced);
380 return isl_ast_graft_free(graft);
383 /* Update "enforced" such that it only involves constraints that are
384 * also enforced by "graft".
386 static __isl_give isl_basic_set *update_enforced(
387 __isl_take isl_basic_set *enforced, __isl_keep isl_ast_graft *graft,
388 int depth)
390 isl_basic_set *enforced_g;
392 enforced_g = isl_ast_graft_get_enforced(graft);
393 if (depth < isl_basic_set_dim(enforced_g, isl_dim_set))
394 enforced_g = isl_basic_set_eliminate(enforced_g,
395 isl_dim_set, depth, 1);
396 enforced_g = isl_basic_set_remove_unknown_divs(enforced_g);
397 enforced_g = isl_basic_set_align_params(enforced_g,
398 isl_basic_set_get_space(enforced));
399 enforced = isl_basic_set_align_params(enforced,
400 isl_basic_set_get_space(enforced_g));
401 enforced = isl_set_simple_hull(isl_basic_set_union(enforced,
402 enforced_g));
404 return enforced;
407 /* Extend the node at *body with node.
409 * If body points to the else branch, then *body may still be NULL.
410 * If so, we simply attach node to this else branch.
411 * Otherwise, we attach a list containing the statements already
412 * attached at *body followed by node.
414 static void extend_body(__isl_keep isl_ast_node **body,
415 __isl_take isl_ast_node *node)
417 isl_ast_node_list *list;
419 if (!*body) {
420 *body = node;
421 return;
424 if ((*body)->type == isl_ast_node_block) {
425 list = isl_ast_node_block_get_children(*body);
426 isl_ast_node_free(*body);
427 } else
428 list = isl_ast_node_list_from_ast_node(*body);
429 list = isl_ast_node_list_add(list, node);
430 *body = isl_ast_node_alloc_block(list);
433 /* Merge "graft" into the last graft of "list".
434 * body points to the then or else branch of an if node in that last graft.
436 * We attach graft->node to this branch and update the enforced
437 * set of the last graft of "list" to take into account the enforced
438 * set of "graft".
440 static __isl_give isl_ast_graft_list *graft_extend_body(
441 __isl_take isl_ast_graft_list *list,
442 __isl_keep isl_ast_node **body, __isl_take isl_ast_graft *graft,
443 __isl_keep isl_ast_build *build)
445 int n;
446 int depth;
447 isl_ast_graft *last;
448 isl_space *space;
449 isl_basic_set *enforced;
451 if (!list || !graft)
452 goto error;
453 extend_body(body, isl_ast_node_copy(graft->node));
454 if (!*body)
455 goto error;
457 n = isl_ast_graft_list_n_ast_graft(list);
458 last = isl_ast_graft_list_get_ast_graft(list, n - 1);
460 depth = isl_ast_build_get_depth(build);
461 space = isl_ast_build_get_space(build, 1);
462 enforced = isl_basic_set_empty(space);
463 enforced = update_enforced(enforced, last, depth);
464 enforced = update_enforced(enforced, graft, depth);
465 last = isl_ast_graft_set_enforced(last, enforced);
467 list = isl_ast_graft_list_set_ast_graft(list, n - 1, last);
468 isl_ast_graft_free(graft);
469 return list;
470 error:
471 isl_ast_graft_free(graft);
472 return isl_ast_graft_list_free(list);
475 /* Merge "graft" into the last graft of "list", attaching graft->node
476 * to the then branch of "last_if".
478 static __isl_give isl_ast_graft_list *extend_then(
479 __isl_take isl_ast_graft_list *list,
480 __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft,
481 __isl_keep isl_ast_build *build)
483 return graft_extend_body(list, &last_if->u.i.then, graft, build);
486 /* Merge "graft" into the last graft of "list", attaching graft->node
487 * to the else branch of "last_if".
489 static __isl_give isl_ast_graft_list *extend_else(
490 __isl_take isl_ast_graft_list *list,
491 __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft,
492 __isl_keep isl_ast_build *build)
494 return graft_extend_body(list, &last_if->u.i.else_node, graft, build);
497 /* This data structure keeps track of an if node.
499 * "node" is the actual if-node
500 * "guard" is the original, non-simplified guard of the node
501 * "complement" is the complement of "guard" in the context of outer if nodes
503 struct isl_if_node {
504 isl_ast_node *node;
505 isl_set *guard;
506 isl_set *complement;
509 /* Given a list of "n" if nodes, clear those starting at "first"
510 * and return "first" (i.e., the updated size of the array).
512 static int clear_if_nodes(struct isl_if_node *if_node, int first, int n)
514 int i;
516 for (i = first; i < n; ++i) {
517 isl_set_free(if_node[i].guard);
518 isl_set_free(if_node[i].complement);
521 return first;
524 /* For each graft in "list",
525 * insert an if node around graft->node testing the condition encoded
526 * in graft->guard, assuming graft->guard involves any conditions.
528 * We keep track of a list of generated if nodes that can be extended
529 * without changing the order of the elements in "list".
530 * If the guard of a graft is a subset of either the guard or its complement
531 * of one of those if nodes, then the node
532 * of the new graft is inserted into the then or else branch of the last graft
533 * and the current graft is discarded.
534 * The guard of the node is then simplified based on the conditions
535 * enforced at that then or else branch.
536 * Otherwise, the current graft is appended to the list.
538 * We only construct else branches if allowed by the user.
540 static __isl_give isl_ast_graft_list *insert_pending_guard_nodes(
541 __isl_take isl_ast_graft_list *list,
542 __isl_keep isl_ast_build *build)
544 int i, j, n, n_if;
545 int allow_else;
546 isl_ctx *ctx;
547 isl_ast_graft_list *res;
548 struct isl_if_node *if_node = NULL;
550 if (!build || !list)
551 return isl_ast_graft_list_free(list);
553 ctx = isl_ast_build_get_ctx(build);
554 n = isl_ast_graft_list_n_ast_graft(list);
556 allow_else = isl_options_get_ast_build_allow_else(ctx);
558 n_if = 0;
559 if (n > 1) {
560 if_node = isl_alloc_array(ctx, struct isl_if_node, n - 1);
561 if (!if_node)
562 return isl_ast_graft_list_free(list);
565 res = isl_ast_graft_list_alloc(ctx, n);
567 for (i = 0; i < n; ++i) {
568 isl_set *guard;
569 isl_ast_graft *graft;
570 int subset, found_then, found_else;
571 isl_ast_node *node;
573 graft = isl_ast_graft_list_get_ast_graft(list, i);
574 if (!graft)
575 break;
576 subset = 0;
577 found_then = found_else = -1;
578 if (n_if > 0) {
579 isl_set *test;
580 test = isl_set_copy(graft->guard);
581 test = isl_set_intersect(test,
582 isl_set_copy(build->domain));
583 for (j = n_if - 1; j >= 0; --j) {
584 subset = isl_set_is_subset(test,
585 if_node[j].guard);
586 if (subset < 0 || subset) {
587 found_then = j;
588 break;
590 if (!allow_else)
591 continue;
592 subset = isl_set_is_subset(test,
593 if_node[j].complement);
594 if (subset < 0 || subset) {
595 found_else = j;
596 break;
599 n_if = clear_if_nodes(if_node, j + 1, n_if);
600 isl_set_free(test);
602 if (subset < 0) {
603 graft = isl_ast_graft_free(graft);
604 break;
607 guard = isl_set_copy(graft->guard);
608 if (found_then >= 0)
609 graft->guard = isl_set_gist(graft->guard,
610 isl_set_copy(if_node[found_then].guard));
611 else if (found_else >= 0)
612 graft->guard = isl_set_gist(graft->guard,
613 isl_set_copy(if_node[found_else].complement));
615 node = graft->node;
616 if (!graft->guard)
617 graft = isl_ast_graft_free(graft);
618 graft = insert_pending_guard_node(graft, build);
619 if (graft && graft->node != node && i != n - 1) {
620 isl_set *set;
621 if_node[n_if].node = graft->node;
622 if_node[n_if].guard = guard;
623 if (found_then >= 0)
624 set = if_node[found_then].guard;
625 else if (found_else >= 0)
626 set = if_node[found_else].complement;
627 else
628 set = build->domain;
629 set = isl_set_copy(set);
630 set = isl_set_subtract(set, isl_set_copy(guard));
631 if_node[n_if].complement = set;
632 n_if++;
633 } else
634 isl_set_free(guard);
635 if (!graft)
636 break;
638 if (found_then >= 0)
639 res = extend_then(res, if_node[found_then].node,
640 graft, build);
641 else if (found_else >= 0)
642 res = extend_else(res, if_node[found_else].node,
643 graft, build);
644 else
645 res = isl_ast_graft_list_add(res, graft);
647 if (i < n)
648 res = isl_ast_graft_list_free(res);
650 isl_ast_graft_list_free(list);
651 clear_if_nodes(if_node, 0, n_if);
652 free(if_node);
653 return res;
656 /* For each graft in "list",
657 * insert an if node around graft->node testing the condition encoded
658 * in graft->guard, assuming graft->guard involves any conditions.
659 * Subsequently remove the guards from the grafts.
661 __isl_give isl_ast_graft_list *isl_ast_graft_list_insert_pending_guard_nodes(
662 __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
664 int i, n;
665 isl_set *universe;
667 list = insert_pending_guard_nodes(list, build);
668 if (!list)
669 return NULL;
671 universe = isl_set_universe(isl_ast_build_get_space(build, 1));
672 n = isl_ast_graft_list_n_ast_graft(list);
673 for (i = 0; i < n; ++i) {
674 isl_ast_graft *graft;
676 graft = isl_ast_graft_list_get_ast_graft(list, i);
677 if (!graft)
678 break;
679 isl_set_free(graft->guard);
680 graft->guard = isl_set_copy(universe);
681 if (!graft->guard)
682 graft = isl_ast_graft_free(graft);
683 list = isl_ast_graft_list_set_ast_graft(list, i, graft);
685 isl_set_free(universe);
686 if (i < n)
687 return isl_ast_graft_list_free(list);
689 return list;
692 /* Collect the nodes contained in the grafts in "list" in a node list.
694 static __isl_give isl_ast_node_list *extract_node_list(
695 __isl_keep isl_ast_graft_list *list)
697 int i, n;
698 isl_ctx *ctx;
699 isl_ast_node_list *node_list;
701 if (!list)
702 return NULL;
703 ctx = isl_ast_graft_list_get_ctx(list);
704 n = isl_ast_graft_list_n_ast_graft(list);
705 node_list = isl_ast_node_list_alloc(ctx, n);
706 for (i = 0; i < n; ++i) {
707 isl_ast_node *node;
708 isl_ast_graft *graft;
710 graft = isl_ast_graft_list_get_ast_graft(list, i);
711 node = isl_ast_graft_get_node(graft);
712 node_list = isl_ast_node_list_add(node_list, node);
713 isl_ast_graft_free(graft);
716 return node_list;
719 /* Look for shared enforced constraints by all the elements in "list"
720 * on outer loops (with respect to the current depth) and return the result.
722 * If there are no elements in "list", then return the empty set.
724 __isl_give isl_basic_set *isl_ast_graft_list_extract_shared_enforced(
725 __isl_keep isl_ast_graft_list *list,
726 __isl_keep isl_ast_build *build)
728 int i, n;
729 int depth;
730 isl_space *space;
731 isl_basic_set *enforced;
733 if (!list)
734 return NULL;
736 space = isl_ast_build_get_space(build, 1);
737 enforced = isl_basic_set_empty(space);
739 depth = isl_ast_build_get_depth(build);
740 n = isl_ast_graft_list_n_ast_graft(list);
741 for (i = 0; i < n; ++i) {
742 isl_ast_graft *graft;
744 graft = isl_ast_graft_list_get_ast_graft(list, i);
745 enforced = update_enforced(enforced, graft, depth);
746 isl_ast_graft_free(graft);
749 return enforced;
752 /* Record "guard" in "graft" so that it will be enforced somewhere
753 * up the tree. If the graft already has a guard, then it may be partially
754 * redundant in combination with the new guard and in the context
755 * the generated constraints of "build". In fact, the new guard
756 * may in itself have some redundant constraints.
757 * We therefore (re)compute the gist of the intersection
758 * and coalesce the result.
760 static __isl_give isl_ast_graft *store_guard(__isl_take isl_ast_graft *graft,
761 __isl_take isl_set *guard, __isl_keep isl_ast_build *build)
763 int is_universe;
765 if (!graft)
766 goto error;
768 is_universe = isl_set_plain_is_universe(guard);
769 if (is_universe < 0)
770 goto error;
771 if (is_universe) {
772 isl_set_free(guard);
773 return graft;
776 graft->guard = isl_set_intersect(graft->guard, guard);
777 graft->guard = isl_set_gist(graft->guard,
778 isl_ast_build_get_generated(build));
779 graft->guard = isl_set_coalesce(graft->guard);
780 if (!graft->guard)
781 return isl_ast_graft_free(graft);
783 return graft;
784 error:
785 isl_set_free(guard);
786 return isl_ast_graft_free(graft);
789 /* For each graft in "list", replace its guard with the gist with
790 * respect to "context".
792 static __isl_give isl_ast_graft_list *gist_guards(
793 __isl_take isl_ast_graft_list *list, __isl_keep isl_set *context)
795 int i, n;
797 if (!list)
798 return NULL;
800 n = isl_ast_graft_list_n_ast_graft(list);
801 for (i = 0; i < n; ++i) {
802 isl_ast_graft *graft;
804 graft = isl_ast_graft_list_get_ast_graft(list, i);
805 if (!graft)
806 break;
807 graft->guard = isl_set_gist(graft->guard,
808 isl_set_copy(context));
809 if (!graft->guard)
810 graft = isl_ast_graft_free(graft);
811 list = isl_ast_graft_list_set_ast_graft(list, i, graft);
813 if (i < n)
814 return isl_ast_graft_list_free(list);
816 return list;
819 /* For each graft in "list", replace its guard with the gist with
820 * respect to "context".
822 __isl_give isl_ast_graft_list *isl_ast_graft_list_gist_guards(
823 __isl_take isl_ast_graft_list *list, __isl_take isl_set *context)
825 list = gist_guards(list, context);
826 isl_set_free(context);
828 return list;
831 /* Allocate a graft in "build" based on the list of grafts in "sub_build".
832 * "guard" and "enforced" are the guard and enforced constraints
833 * of the allocated graft. The guard is used to simplify the guards
834 * of the elements in "list".
836 * The node is initialized to either a block containing the nodes of "children"
837 * or, if there is only a single child, the node of that child.
838 * If the current level requires a for node, it should be inserted by
839 * a subsequent call to isl_ast_graft_insert_for.
841 __isl_give isl_ast_graft *isl_ast_graft_alloc_from_children(
842 __isl_take isl_ast_graft_list *list, __isl_take isl_set *guard,
843 __isl_take isl_basic_set *enforced, __isl_keep isl_ast_build *build,
844 __isl_keep isl_ast_build *sub_build)
846 isl_ast_build *guard_build;
847 isl_ast_node *node;
848 isl_ast_node_list *node_list;
849 isl_ast_graft *graft;
851 guard_build = isl_ast_build_copy(sub_build);
852 guard_build = isl_ast_build_replace_pending_by_guard(guard_build,
853 isl_set_copy(guard));
854 list = gist_guards(list, guard);
855 list = insert_pending_guard_nodes(list, guard_build);
856 isl_ast_build_free(guard_build);
858 node_list = extract_node_list(list);
859 node = isl_ast_node_from_ast_node_list(node_list);
860 isl_ast_graft_list_free(list);
862 graft = isl_ast_graft_alloc(node, build);
863 graft = store_guard(graft, guard, build);
864 graft = isl_ast_graft_enforce(graft, enforced);
866 return graft;
869 /* Combine the grafts in the list into a single graft.
871 * The guard is initialized to the shared guard of the list elements (if any),
872 * provided it does not depend on the current dimension.
873 * The guards in the elements are then simplified with respect to the
874 * hoisted guard and materialized as if nodes around the contained AST nodes
875 * in the context of "sub_build".
877 * The enforced set is initialized to the simple hull of the enforced sets
878 * of the elements, provided the ast_build_exploit_nested_bounds option is set
879 * or the new graft will be used at the same level.
881 * The node is initialized to either a block containing the nodes of "list"
882 * or, if there is only a single element, the node of that element.
884 static __isl_give isl_ast_graft *ast_graft_list_fuse(
885 __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
887 isl_ast_graft *graft;
888 isl_basic_set *enforced;
889 isl_set *guard;
891 if (!list)
892 return NULL;
894 enforced = isl_ast_graft_list_extract_shared_enforced(list, build);
895 guard = isl_ast_graft_list_extract_hoistable_guard(list, build);
896 graft = isl_ast_graft_alloc_from_children(list, guard, enforced,
897 build, build);
899 return graft;
902 /* Combine the grafts in the list into a single graft.
903 * Return a list containing this single graft.
904 * If the original list is empty, then return an empty list.
906 __isl_give isl_ast_graft_list *isl_ast_graft_list_fuse(
907 __isl_take isl_ast_graft_list *list,
908 __isl_keep isl_ast_build *build)
910 isl_ast_graft *graft;
912 if (!list)
913 return NULL;
914 if (isl_ast_graft_list_n_ast_graft(list) <= 1)
915 return list;
916 graft = ast_graft_list_fuse(list, build);
917 return isl_ast_graft_list_from_ast_graft(graft);
920 /* Combine the two grafts into a single graft.
921 * Return a list containing this single graft.
923 static __isl_give isl_ast_graft *isl_ast_graft_fuse(
924 __isl_take isl_ast_graft *graft1, __isl_take isl_ast_graft *graft2,
925 __isl_keep isl_ast_build *build)
927 isl_ctx *ctx;
928 isl_ast_graft_list *list;
930 ctx = isl_ast_build_get_ctx(build);
932 list = isl_ast_graft_list_alloc(ctx, 2);
933 list = isl_ast_graft_list_add(list, graft1);
934 list = isl_ast_graft_list_add(list, graft2);
936 return ast_graft_list_fuse(list, build);
939 /* Insert a for node enclosing the current graft->node.
941 __isl_give isl_ast_graft *isl_ast_graft_insert_for(
942 __isl_take isl_ast_graft *graft, __isl_take isl_ast_node *node)
944 if (!graft)
945 goto error;
947 graft->node = isl_ast_node_for_set_body(node, graft->node);
948 if (!graft->node)
949 return isl_ast_graft_free(graft);
951 return graft;
952 error:
953 isl_ast_node_free(node);
954 isl_ast_graft_free(graft);
955 return NULL;
958 /* Insert a mark governing the current graft->node.
960 __isl_give isl_ast_graft *isl_ast_graft_insert_mark(
961 __isl_take isl_ast_graft *graft, __isl_take isl_id *mark)
963 if (!graft)
964 goto error;
966 graft->node = isl_ast_node_alloc_mark(mark, graft->node);
967 if (!graft->node)
968 return isl_ast_graft_free(graft);
970 return graft;
971 error:
972 isl_id_free(mark);
973 isl_ast_graft_free(graft);
974 return NULL;
977 /* Represent the graft list as an AST node.
978 * This operation drops the information about guards in the grafts, so
979 * if there are any pending guards, then they are materialized as if nodes.
981 __isl_give isl_ast_node *isl_ast_node_from_graft_list(
982 __isl_take isl_ast_graft_list *list,
983 __isl_keep isl_ast_build *build)
985 isl_ast_node_list *node_list;
987 list = insert_pending_guard_nodes(list, build);
988 node_list = extract_node_list(list);
989 isl_ast_graft_list_free(list);
991 return isl_ast_node_from_ast_node_list(node_list);
994 void *isl_ast_graft_free(__isl_take isl_ast_graft *graft)
996 if (!graft)
997 return NULL;
999 if (--graft->ref > 0)
1000 return NULL;
1002 isl_ast_node_free(graft->node);
1003 isl_set_free(graft->guard);
1004 isl_basic_set_free(graft->enforced);
1005 free(graft);
1007 return NULL;
1010 /* Record that the grafted tree enforces
1011 * "enforced" by intersecting graft->enforced with "enforced".
1013 __isl_give isl_ast_graft *isl_ast_graft_enforce(
1014 __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced)
1016 if (!graft || !enforced)
1017 goto error;
1019 enforced = isl_basic_set_align_params(enforced,
1020 isl_basic_set_get_space(graft->enforced));
1021 graft->enforced = isl_basic_set_align_params(graft->enforced,
1022 isl_basic_set_get_space(enforced));
1023 graft->enforced = isl_basic_set_intersect(graft->enforced, enforced);
1024 if (!graft->enforced)
1025 return isl_ast_graft_free(graft);
1027 return graft;
1028 error:
1029 isl_basic_set_free(enforced);
1030 return isl_ast_graft_free(graft);
1033 __isl_give isl_basic_set *isl_ast_graft_get_enforced(
1034 __isl_keep isl_ast_graft *graft)
1036 return graft ? isl_basic_set_copy(graft->enforced) : NULL;
1039 __isl_give isl_set *isl_ast_graft_get_guard(__isl_keep isl_ast_graft *graft)
1041 return graft ? isl_set_copy(graft->guard) : NULL;
1044 /* Record that "guard" needs to be inserted in "graft".
1046 __isl_give isl_ast_graft *isl_ast_graft_add_guard(
1047 __isl_take isl_ast_graft *graft,
1048 __isl_take isl_set *guard, __isl_keep isl_ast_build *build)
1050 return store_guard(graft, guard, build);
1053 /* Reformulate the "graft", which was generated in the context
1054 * of an inner code generation, in terms of the outer code generation
1055 * AST build.
1057 * If "product" is set, then the domain of the inner code generation build is
1059 * [O -> S]
1061 * with O the domain of the outer code generation build.
1062 * We essentially need to project out S.
1064 * If "product" is not set, then we need to project the domains onto
1065 * their parameter spaces.
1067 __isl_give isl_ast_graft *isl_ast_graft_unembed(__isl_take isl_ast_graft *graft,
1068 int product)
1070 isl_basic_set *enforced;
1072 if (!graft)
1073 return NULL;
1075 if (product) {
1076 enforced = graft->enforced;
1077 enforced = isl_basic_map_domain(isl_basic_set_unwrap(enforced));
1078 graft->enforced = enforced;
1079 graft->guard = isl_map_domain(isl_set_unwrap(graft->guard));
1080 } else {
1081 graft->enforced = isl_basic_set_params(graft->enforced);
1082 graft->guard = isl_set_params(graft->guard);
1084 graft->guard = isl_set_compute_divs(graft->guard);
1086 if (!graft->enforced || !graft->guard)
1087 return isl_ast_graft_free(graft);
1089 return graft;
1092 /* Reformulate the grafts in "list", which were generated in the context
1093 * of an inner code generation, in terms of the outer code generation
1094 * AST build.
1096 __isl_give isl_ast_graft_list *isl_ast_graft_list_unembed(
1097 __isl_take isl_ast_graft_list *list, int product)
1099 int i, n;
1101 n = isl_ast_graft_list_n_ast_graft(list);
1102 for (i = 0; i < n; ++i) {
1103 isl_ast_graft *graft;
1105 graft = isl_ast_graft_list_get_ast_graft(list, i);
1106 graft = isl_ast_graft_unembed(graft, product);
1107 list = isl_ast_graft_list_set_ast_graft(list, i, graft);
1110 return list;
1113 /* Compute the preimage of "graft" under the function represented by "ma".
1114 * In other words, plug in "ma" in "enforced" and "guard" fields of "graft".
1116 __isl_give isl_ast_graft *isl_ast_graft_preimage_multi_aff(
1117 __isl_take isl_ast_graft *graft, __isl_take isl_multi_aff *ma)
1119 isl_basic_set *enforced;
1121 if (!graft)
1122 return NULL;
1124 enforced = graft->enforced;
1125 graft->enforced = isl_basic_set_preimage_multi_aff(enforced,
1126 isl_multi_aff_copy(ma));
1127 graft->guard = isl_set_preimage_multi_aff(graft->guard, ma);
1129 if (!graft->enforced || !graft->guard)
1130 return isl_ast_graft_free(graft);
1132 return graft;
1135 /* Compute the preimage of all the grafts in "list" under
1136 * the function represented by "ma".
1138 __isl_give isl_ast_graft_list *isl_ast_graft_list_preimage_multi_aff(
1139 __isl_take isl_ast_graft_list *list, __isl_take isl_multi_aff *ma)
1141 int i, n;
1143 n = isl_ast_graft_list_n_ast_graft(list);
1144 for (i = 0; i < n; ++i) {
1145 isl_ast_graft *graft;
1147 graft = isl_ast_graft_list_get_ast_graft(list, i);
1148 graft = isl_ast_graft_preimage_multi_aff(graft,
1149 isl_multi_aff_copy(ma));
1150 list = isl_ast_graft_list_set_ast_graft(list, i, graft);
1153 isl_multi_aff_free(ma);
1154 return list;
1157 /* Compare two grafts based on their guards.
1159 static int cmp_graft(__isl_keep isl_ast_graft *a, __isl_keep isl_ast_graft *b,
1160 void *user)
1162 return isl_set_plain_cmp(a->guard, b->guard);
1165 /* Order the elements in "list" based on their guards.
1167 __isl_give isl_ast_graft_list *isl_ast_graft_list_sort_guard(
1168 __isl_take isl_ast_graft_list *list)
1170 return isl_ast_graft_list_sort(list, &cmp_graft, NULL);
1173 /* Merge the given two lists into a single list of grafts,
1174 * merging grafts with the same guard into a single graft.
1176 * "list2" has been sorted using isl_ast_graft_list_sort.
1177 * "list1" may be the result of a previous call to isl_ast_graft_list_merge
1178 * and may therefore not be completely sorted.
1180 * The elements in "list2" need to be executed after those in "list1",
1181 * but if the guard of a graft in "list2" is disjoint from the guards
1182 * of some final elements in "list1", then it can be moved up to before
1183 * those final elements.
1185 * In particular, we look at each element g of "list2" in turn
1186 * and move it up beyond elements of "list1" that would be sorted
1187 * after g as long as each of these elements has a guard that is disjoint
1188 * from that of g.
1190 * We do not allow the second or any later element of "list2" to be moved
1191 * before a previous elements of "list2" even if the reason that
1192 * that element didn't move up further was that its guard was not disjoint
1193 * from that of the previous element in "list1".
1195 __isl_give isl_ast_graft_list *isl_ast_graft_list_merge(
1196 __isl_take isl_ast_graft_list *list1,
1197 __isl_take isl_ast_graft_list *list2,
1198 __isl_keep isl_ast_build *build)
1200 int i, j, first;
1202 if (!list1 || !list2 || !build)
1203 goto error;
1204 if (list2->n == 0) {
1205 isl_ast_graft_list_free(list2);
1206 return list1;
1208 if (list1->n == 0) {
1209 isl_ast_graft_list_free(list1);
1210 return list2;
1213 first = 0;
1214 for (i = 0; i < list2->n; ++i) {
1215 isl_ast_graft *graft;
1216 graft = isl_ast_graft_list_get_ast_graft(list2, i);
1217 if (!graft)
1218 break;
1220 for (j = list1->n; j >= 0; --j) {
1221 int cmp, disjoint;
1222 isl_ast_graft *graft_j;
1224 if (j == first)
1225 cmp = -1;
1226 else
1227 cmp = isl_set_plain_cmp(list1->p[j - 1]->guard,
1228 graft->guard);
1229 if (cmp > 0) {
1230 disjoint = isl_set_is_disjoint(graft->guard,
1231 list1->p[j - 1]->guard);
1232 if (disjoint < 0) {
1233 list1 = isl_ast_graft_list_free(list1);
1234 break;
1236 if (!disjoint)
1237 cmp = -1;
1239 if (cmp > 0)
1240 continue;
1241 if (cmp < 0) {
1242 list1 = isl_ast_graft_list_insert(list1, j,
1243 graft);
1244 break;
1247 --j;
1249 graft_j = isl_ast_graft_list_get_ast_graft(list1, j);
1250 graft_j = isl_ast_graft_fuse(graft_j, graft, build);
1251 list1 = isl_ast_graft_list_set_ast_graft(list1, j,
1252 graft_j);
1253 break;
1256 if (j < 0)
1257 isl_die(isl_ast_build_get_ctx(build),
1258 isl_error_internal,
1259 "element failed to get inserted", break);
1261 first = j + 1;
1262 if (!list1)
1263 break;
1265 if (i < list2->n)
1266 list1 = isl_ast_graft_list_free(list1);
1267 isl_ast_graft_list_free(list2);
1269 return list1;
1270 error:
1271 isl_ast_graft_list_free(list1);
1272 isl_ast_graft_list_free(list2);
1273 return NULL;
1276 __isl_give isl_printer *isl_printer_print_ast_graft(__isl_take isl_printer *p,
1277 __isl_keep isl_ast_graft *graft)
1279 if (!p)
1280 return NULL;
1281 if (!graft)
1282 return isl_printer_free(p);
1284 p = isl_printer_print_str(p, "(");
1285 p = isl_printer_print_str(p, "guard: ");
1286 p = isl_printer_print_set(p, graft->guard);
1287 p = isl_printer_print_str(p, ", ");
1288 p = isl_printer_print_str(p, "enforced: ");
1289 p = isl_printer_print_basic_set(p, graft->enforced);
1290 p = isl_printer_print_str(p, ", ");
1291 p = isl_printer_print_str(p, "node: ");
1292 p = isl_printer_print_ast_node(p, graft->node);
1293 p = isl_printer_print_str(p, ")");
1295 return p;