isl_tab_basic_set_non_trivial_lexmin: extract out update_outer_levels
[isl.git] / isl_schedule_tree.c
blob50bf2d8ef2f36b5d617e94467c9ca10eb0a9be5f
1 /*
2 * Copyright 2013-2014 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
4 * Copyright 2016 INRIA Paris
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege,
9 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
10 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
11 * B.P. 105 - 78153 Le Chesnay, France
12 * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12,
13 * CS 42112, 75589 Paris Cedex 12, France
16 #include <isl/val.h>
17 #include <isl/space.h>
18 #include <isl/map.h>
19 #include <isl_schedule_band.h>
20 #include <isl_schedule_private.h>
22 #undef EL
23 #define EL isl_schedule_tree
25 #include <isl_list_templ.h>
27 #undef BASE
28 #define BASE schedule_tree
30 #include <isl_list_templ.c>
32 /* Is "tree" the leaf of a schedule tree?
34 int isl_schedule_tree_is_leaf(__isl_keep isl_schedule_tree *tree)
36 return isl_schedule_tree_get_type(tree) == isl_schedule_node_leaf;
39 /* Create a new schedule tree of type "type".
40 * The caller is responsible for filling in the type specific fields and
41 * the children.
43 * By default, the single node tree does not have any anchored nodes.
44 * The caller is responsible for updating the anchored field if needed.
46 static __isl_give isl_schedule_tree *isl_schedule_tree_alloc(isl_ctx *ctx,
47 enum isl_schedule_node_type type)
49 isl_schedule_tree *tree;
51 if (type == isl_schedule_node_error)
52 return NULL;
54 tree = isl_calloc_type(ctx, isl_schedule_tree);
55 if (!tree)
56 return NULL;
58 tree->ref = 1;
59 tree->ctx = ctx;
60 isl_ctx_ref(ctx);
61 tree->type = type;
62 tree->anchored = 0;
64 return tree;
67 /* Return a fresh copy of "tree".
69 __isl_take isl_schedule_tree *isl_schedule_tree_dup(
70 __isl_keep isl_schedule_tree *tree)
72 isl_ctx *ctx;
73 isl_schedule_tree *dup;
75 if (!tree)
76 return NULL;
78 ctx = isl_schedule_tree_get_ctx(tree);
79 dup = isl_schedule_tree_alloc(ctx, tree->type);
80 if (!dup)
81 return NULL;
83 switch (tree->type) {
84 case isl_schedule_node_error:
85 isl_die(ctx, isl_error_internal,
86 "allocation should have failed",
87 return isl_schedule_tree_free(dup));
88 case isl_schedule_node_band:
89 dup->band = isl_schedule_band_copy(tree->band);
90 if (!dup->band)
91 return isl_schedule_tree_free(dup);
92 break;
93 case isl_schedule_node_context:
94 dup->context = isl_set_copy(tree->context);
95 if (!dup->context)
96 return isl_schedule_tree_free(dup);
97 break;
98 case isl_schedule_node_domain:
99 dup->domain = isl_union_set_copy(tree->domain);
100 if (!dup->domain)
101 return isl_schedule_tree_free(dup);
102 break;
103 case isl_schedule_node_expansion:
104 dup->contraction =
105 isl_union_pw_multi_aff_copy(tree->contraction);
106 dup->expansion = isl_union_map_copy(tree->expansion);
107 if (!dup->contraction || !dup->expansion)
108 return isl_schedule_tree_free(dup);
109 break;
110 case isl_schedule_node_extension:
111 dup->extension = isl_union_map_copy(tree->extension);
112 if (!dup->extension)
113 return isl_schedule_tree_free(dup);
114 break;
115 case isl_schedule_node_filter:
116 dup->filter = isl_union_set_copy(tree->filter);
117 if (!dup->filter)
118 return isl_schedule_tree_free(dup);
119 break;
120 case isl_schedule_node_guard:
121 dup->guard = isl_set_copy(tree->guard);
122 if (!dup->guard)
123 return isl_schedule_tree_free(dup);
124 break;
125 case isl_schedule_node_mark:
126 dup->mark = isl_id_copy(tree->mark);
127 if (!dup->mark)
128 return isl_schedule_tree_free(dup);
129 break;
130 case isl_schedule_node_leaf:
131 case isl_schedule_node_sequence:
132 case isl_schedule_node_set:
133 break;
136 if (tree->children) {
137 dup->children = isl_schedule_tree_list_copy(tree->children);
138 if (!dup->children)
139 return isl_schedule_tree_free(dup);
141 dup->anchored = tree->anchored;
143 return dup;
146 /* Return an isl_schedule_tree that is equal to "tree" and that has only
147 * a single reference.
149 __isl_give isl_schedule_tree *isl_schedule_tree_cow(
150 __isl_take isl_schedule_tree *tree)
152 if (!tree)
153 return NULL;
155 if (tree->ref == 1)
156 return tree;
157 tree->ref--;
158 return isl_schedule_tree_dup(tree);
161 /* Return a new reference to "tree".
163 __isl_give isl_schedule_tree *isl_schedule_tree_copy(
164 __isl_keep isl_schedule_tree *tree)
166 if (!tree)
167 return NULL;
169 tree->ref++;
170 return tree;
173 /* Free "tree" and return NULL.
175 __isl_null isl_schedule_tree *isl_schedule_tree_free(
176 __isl_take isl_schedule_tree *tree)
178 if (!tree)
179 return NULL;
180 if (--tree->ref > 0)
181 return NULL;
183 switch (tree->type) {
184 case isl_schedule_node_band:
185 isl_schedule_band_free(tree->band);
186 break;
187 case isl_schedule_node_context:
188 isl_set_free(tree->context);
189 break;
190 case isl_schedule_node_domain:
191 isl_union_set_free(tree->domain);
192 break;
193 case isl_schedule_node_expansion:
194 isl_union_pw_multi_aff_free(tree->contraction);
195 isl_union_map_free(tree->expansion);
196 break;
197 case isl_schedule_node_extension:
198 isl_union_map_free(tree->extension);
199 break;
200 case isl_schedule_node_filter:
201 isl_union_set_free(tree->filter);
202 break;
203 case isl_schedule_node_guard:
204 isl_set_free(tree->guard);
205 break;
206 case isl_schedule_node_mark:
207 isl_id_free(tree->mark);
208 break;
209 case isl_schedule_node_sequence:
210 case isl_schedule_node_set:
211 case isl_schedule_node_error:
212 case isl_schedule_node_leaf:
213 break;
215 isl_schedule_tree_list_free(tree->children);
216 isl_ctx_deref(tree->ctx);
217 free(tree);
219 return NULL;
222 /* Create and return a new leaf schedule tree.
224 __isl_give isl_schedule_tree *isl_schedule_tree_leaf(isl_ctx *ctx)
226 return isl_schedule_tree_alloc(ctx, isl_schedule_node_leaf);
229 /* Create a new band schedule tree referring to "band"
230 * with no children.
232 __isl_give isl_schedule_tree *isl_schedule_tree_from_band(
233 __isl_take isl_schedule_band *band)
235 isl_ctx *ctx;
236 isl_schedule_tree *tree;
238 if (!band)
239 return NULL;
241 ctx = isl_schedule_band_get_ctx(band);
242 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_band);
243 if (!tree)
244 goto error;
246 tree->band = band;
247 tree->anchored = isl_schedule_band_is_anchored(band);
249 return tree;
250 error:
251 isl_schedule_band_free(band);
252 return NULL;
255 /* Create a new context schedule tree with the given context and no children.
256 * Since the context references the outer schedule dimension,
257 * the tree is anchored.
259 __isl_give isl_schedule_tree *isl_schedule_tree_from_context(
260 __isl_take isl_set *context)
262 isl_ctx *ctx;
263 isl_schedule_tree *tree;
265 if (!context)
266 return NULL;
268 ctx = isl_set_get_ctx(context);
269 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_context);
270 if (!tree)
271 goto error;
273 tree->context = context;
274 tree->anchored = 1;
276 return tree;
277 error:
278 isl_set_free(context);
279 return NULL;
282 /* Create a new domain schedule tree with the given domain and no children.
284 __isl_give isl_schedule_tree *isl_schedule_tree_from_domain(
285 __isl_take isl_union_set *domain)
287 isl_ctx *ctx;
288 isl_schedule_tree *tree;
290 if (!domain)
291 return NULL;
293 ctx = isl_union_set_get_ctx(domain);
294 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_domain);
295 if (!tree)
296 goto error;
298 tree->domain = domain;
300 return tree;
301 error:
302 isl_union_set_free(domain);
303 return NULL;
306 /* Create a new expansion schedule tree with the given contraction and
307 * expansion and no children.
309 __isl_give isl_schedule_tree *isl_schedule_tree_from_expansion(
310 __isl_take isl_union_pw_multi_aff *contraction,
311 __isl_take isl_union_map *expansion)
313 isl_ctx *ctx;
314 isl_schedule_tree *tree;
316 if (!contraction || !expansion)
317 goto error;
319 ctx = isl_union_map_get_ctx(expansion);
320 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_expansion);
321 if (!tree)
322 goto error;
324 tree->contraction = contraction;
325 tree->expansion = expansion;
327 return tree;
328 error:
329 isl_union_pw_multi_aff_free(contraction);
330 isl_union_map_free(expansion);
331 return NULL;
334 /* Create a new extension schedule tree with the given extension and
335 * no children.
336 * Since the domain of the extension refers to the outer schedule dimension,
337 * the tree is anchored.
339 __isl_give isl_schedule_tree *isl_schedule_tree_from_extension(
340 __isl_take isl_union_map *extension)
342 isl_ctx *ctx;
343 isl_schedule_tree *tree;
345 if (!extension)
346 return NULL;
348 ctx = isl_union_map_get_ctx(extension);
349 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_extension);
350 if (!tree)
351 goto error;
353 tree->extension = extension;
354 tree->anchored = 1;
356 return tree;
357 error:
358 isl_union_map_free(extension);
359 return NULL;
362 /* Create a new filter schedule tree with the given filter and no children.
364 __isl_give isl_schedule_tree *isl_schedule_tree_from_filter(
365 __isl_take isl_union_set *filter)
367 isl_ctx *ctx;
368 isl_schedule_tree *tree;
370 if (!filter)
371 return NULL;
373 ctx = isl_union_set_get_ctx(filter);
374 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_filter);
375 if (!tree)
376 goto error;
378 tree->filter = filter;
380 return tree;
381 error:
382 isl_union_set_free(filter);
383 return NULL;
386 /* Create a new guard schedule tree with the given guard and no children.
387 * Since the guard references the outer schedule dimension,
388 * the tree is anchored.
390 __isl_give isl_schedule_tree *isl_schedule_tree_from_guard(
391 __isl_take isl_set *guard)
393 isl_ctx *ctx;
394 isl_schedule_tree *tree;
396 if (!guard)
397 return NULL;
399 ctx = isl_set_get_ctx(guard);
400 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_guard);
401 if (!tree)
402 goto error;
404 tree->guard = guard;
405 tree->anchored = 1;
407 return tree;
408 error:
409 isl_set_free(guard);
410 return NULL;
413 /* Create a new mark schedule tree with the given mark identifier and
414 * no children.
416 __isl_give isl_schedule_tree *isl_schedule_tree_from_mark(
417 __isl_take isl_id *mark)
419 isl_ctx *ctx;
420 isl_schedule_tree *tree;
422 if (!mark)
423 return NULL;
425 ctx = isl_id_get_ctx(mark);
426 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_mark);
427 if (!tree)
428 goto error;
430 tree->mark = mark;
432 return tree;
433 error:
434 isl_id_free(mark);
435 return NULL;
438 /* Does "tree" have any node that depends on its position
439 * in the complete schedule tree?
441 isl_bool isl_schedule_tree_is_subtree_anchored(
442 __isl_keep isl_schedule_tree *tree)
444 return tree ? tree->anchored : isl_bool_error;
447 /* Does the root node of "tree" depend on its position in the complete
448 * schedule tree?
449 * Band nodes may be anchored depending on the associated AST build options.
450 * Context, extension and guard nodes are always anchored.
452 int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree *tree)
454 if (!tree)
455 return -1;
457 switch (isl_schedule_tree_get_type(tree)) {
458 case isl_schedule_node_error:
459 return -1;
460 case isl_schedule_node_band:
461 return isl_schedule_band_is_anchored(tree->band);
462 case isl_schedule_node_context:
463 case isl_schedule_node_extension:
464 case isl_schedule_node_guard:
465 return 1;
466 case isl_schedule_node_domain:
467 case isl_schedule_node_expansion:
468 case isl_schedule_node_filter:
469 case isl_schedule_node_leaf:
470 case isl_schedule_node_mark:
471 case isl_schedule_node_sequence:
472 case isl_schedule_node_set:
473 return 0;
476 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
477 "unhandled case", return -1);
480 /* Update the anchored field of "tree" based on whether the root node
481 * itself in anchored and the anchored fields of the children.
483 * This function should be called whenever the children of a tree node
484 * are changed or the anchoredness of the tree root itself changes.
486 __isl_give isl_schedule_tree *isl_schedule_tree_update_anchored(
487 __isl_take isl_schedule_tree *tree)
489 int i, n;
490 int anchored;
492 if (!tree)
493 return NULL;
495 anchored = isl_schedule_tree_is_anchored(tree);
496 if (anchored < 0)
497 return isl_schedule_tree_free(tree);
499 n = isl_schedule_tree_list_n_schedule_tree(tree->children);
500 for (i = 0; !anchored && i < n; ++i) {
501 isl_schedule_tree *child;
503 child = isl_schedule_tree_get_child(tree, i);
504 if (!child)
505 return isl_schedule_tree_free(tree);
506 anchored = child->anchored;
507 isl_schedule_tree_free(child);
510 if (anchored == tree->anchored)
511 return tree;
512 tree = isl_schedule_tree_cow(tree);
513 if (!tree)
514 return NULL;
515 tree->anchored = anchored;
516 return tree;
519 /* Create a new tree of the given type (isl_schedule_node_sequence or
520 * isl_schedule_node_set) with the given children.
522 __isl_give isl_schedule_tree *isl_schedule_tree_from_children(
523 enum isl_schedule_node_type type,
524 __isl_take isl_schedule_tree_list *list)
526 isl_ctx *ctx;
527 isl_schedule_tree *tree;
529 if (!list)
530 return NULL;
532 ctx = isl_schedule_tree_list_get_ctx(list);
533 tree = isl_schedule_tree_alloc(ctx, type);
534 if (!tree)
535 goto error;
537 tree->children = list;
538 tree = isl_schedule_tree_update_anchored(tree);
540 return tree;
541 error:
542 isl_schedule_tree_list_free(list);
543 return NULL;
546 /* Construct a tree with a root node of type "type" and as children
547 * "tree1" and "tree2".
548 * If the root of one (or both) of the input trees is itself of type "type",
549 * then the tree is replaced by its children.
551 __isl_give isl_schedule_tree *isl_schedule_tree_from_pair(
552 enum isl_schedule_node_type type, __isl_take isl_schedule_tree *tree1,
553 __isl_take isl_schedule_tree *tree2)
555 isl_ctx *ctx;
556 isl_schedule_tree_list *list;
558 if (!tree1 || !tree2)
559 goto error;
561 ctx = isl_schedule_tree_get_ctx(tree1);
562 if (isl_schedule_tree_get_type(tree1) == type) {
563 list = isl_schedule_tree_list_copy(tree1->children);
564 isl_schedule_tree_free(tree1);
565 } else {
566 list = isl_schedule_tree_list_alloc(ctx, 2);
567 list = isl_schedule_tree_list_add(list, tree1);
569 if (isl_schedule_tree_get_type(tree2) == type) {
570 isl_schedule_tree_list *children;
572 children = isl_schedule_tree_list_copy(tree2->children);
573 list = isl_schedule_tree_list_concat(list, children);
574 isl_schedule_tree_free(tree2);
575 } else {
576 list = isl_schedule_tree_list_add(list, tree2);
579 return isl_schedule_tree_from_children(type, list);
580 error:
581 isl_schedule_tree_free(tree1);
582 isl_schedule_tree_free(tree2);
583 return NULL;
586 /* Construct a tree with a sequence root node and as children
587 * "tree1" and "tree2".
588 * If the root of one (or both) of the input trees is itself a sequence,
589 * then the tree is replaced by its children.
591 __isl_give isl_schedule_tree *isl_schedule_tree_sequence_pair(
592 __isl_take isl_schedule_tree *tree1,
593 __isl_take isl_schedule_tree *tree2)
595 return isl_schedule_tree_from_pair(isl_schedule_node_sequence,
596 tree1, tree2);
599 /* Construct a tree with a set root node and as children
600 * "tree1" and "tree2".
601 * If the root of one (or both) of the input trees is itself a set,
602 * then the tree is replaced by its children.
604 __isl_give isl_schedule_tree *isl_schedule_tree_set_pair(
605 __isl_take isl_schedule_tree *tree1,
606 __isl_take isl_schedule_tree *tree2)
608 return isl_schedule_tree_from_pair(isl_schedule_node_set, tree1, tree2);
611 /* Return the isl_ctx to which "tree" belongs.
613 isl_ctx *isl_schedule_tree_get_ctx(__isl_keep isl_schedule_tree *tree)
615 return tree ? tree->ctx : NULL;
618 /* Return the type of the root of the tree or isl_schedule_node_error
619 * on error.
621 enum isl_schedule_node_type isl_schedule_tree_get_type(
622 __isl_keep isl_schedule_tree *tree)
624 return tree ? tree->type : isl_schedule_node_error;
627 /* Are "tree1" and "tree2" obviously equal to each other?
629 isl_bool isl_schedule_tree_plain_is_equal(__isl_keep isl_schedule_tree *tree1,
630 __isl_keep isl_schedule_tree *tree2)
632 isl_bool equal;
633 int i, n;
635 if (!tree1 || !tree2)
636 return isl_bool_error;
637 if (tree1 == tree2)
638 return isl_bool_true;
639 if (tree1->type != tree2->type)
640 return isl_bool_false;
642 switch (tree1->type) {
643 case isl_schedule_node_band:
644 equal = isl_schedule_band_plain_is_equal(tree1->band,
645 tree2->band);
646 break;
647 case isl_schedule_node_context:
648 equal = isl_set_is_equal(tree1->context, tree2->context);
649 break;
650 case isl_schedule_node_domain:
651 equal = isl_union_set_is_equal(tree1->domain, tree2->domain);
652 break;
653 case isl_schedule_node_expansion:
654 equal = isl_union_map_is_equal(tree1->expansion,
655 tree2->expansion);
656 if (equal >= 0 && equal)
657 equal = isl_union_pw_multi_aff_plain_is_equal(
658 tree1->contraction, tree2->contraction);
659 break;
660 case isl_schedule_node_extension:
661 equal = isl_union_map_is_equal(tree1->extension,
662 tree2->extension);
663 break;
664 case isl_schedule_node_filter:
665 equal = isl_union_set_is_equal(tree1->filter, tree2->filter);
666 break;
667 case isl_schedule_node_guard:
668 equal = isl_set_is_equal(tree1->guard, tree2->guard);
669 break;
670 case isl_schedule_node_mark:
671 equal = tree1->mark == tree2->mark;
672 break;
673 case isl_schedule_node_leaf:
674 case isl_schedule_node_sequence:
675 case isl_schedule_node_set:
676 equal = isl_bool_true;
677 break;
678 case isl_schedule_node_error:
679 equal = isl_bool_error;
680 break;
683 if (equal < 0 || !equal)
684 return equal;
686 n = isl_schedule_tree_n_children(tree1);
687 if (n != isl_schedule_tree_n_children(tree2))
688 return isl_bool_false;
689 for (i = 0; i < n; ++i) {
690 isl_schedule_tree *child1, *child2;
692 child1 = isl_schedule_tree_get_child(tree1, i);
693 child2 = isl_schedule_tree_get_child(tree2, i);
694 equal = isl_schedule_tree_plain_is_equal(child1, child2);
695 isl_schedule_tree_free(child1);
696 isl_schedule_tree_free(child2);
698 if (equal < 0 || !equal)
699 return equal;
702 return isl_bool_true;
705 /* Does "tree" have any children, other than an implicit leaf.
707 int isl_schedule_tree_has_children(__isl_keep isl_schedule_tree *tree)
709 if (!tree)
710 return -1;
712 return tree->children != NULL;
715 /* Return the number of children of "tree", excluding implicit leaves.
717 int isl_schedule_tree_n_children(__isl_keep isl_schedule_tree *tree)
719 if (!tree)
720 return -1;
722 return isl_schedule_tree_list_n_schedule_tree(tree->children);
725 /* Return a copy of the (explicit) child at position "pos" of "tree".
727 __isl_give isl_schedule_tree *isl_schedule_tree_get_child(
728 __isl_keep isl_schedule_tree *tree, int pos)
730 if (!tree)
731 return NULL;
732 if (!tree->children)
733 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
734 "schedule tree has no explicit children", return NULL);
735 return isl_schedule_tree_list_get_schedule_tree(tree->children, pos);
738 /* Return a copy of the (explicit) child at position "pos" of "tree" and
739 * free "tree".
741 __isl_give isl_schedule_tree *isl_schedule_tree_child(
742 __isl_take isl_schedule_tree *tree, int pos)
744 isl_schedule_tree *child;
746 child = isl_schedule_tree_get_child(tree, pos);
747 isl_schedule_tree_free(tree);
748 return child;
751 /* Remove all (explicit) children from "tree".
753 __isl_give isl_schedule_tree *isl_schedule_tree_reset_children(
754 __isl_take isl_schedule_tree *tree)
756 tree = isl_schedule_tree_cow(tree);
757 if (!tree)
758 return NULL;
759 tree->children = isl_schedule_tree_list_free(tree->children);
760 return tree;
763 /* Remove the child at position "pos" from the children of "tree".
764 * If there was only one child to begin with, then remove all children.
766 __isl_give isl_schedule_tree *isl_schedule_tree_drop_child(
767 __isl_take isl_schedule_tree *tree, int pos)
769 int n;
771 tree = isl_schedule_tree_cow(tree);
772 if (!tree)
773 return NULL;
775 if (!isl_schedule_tree_has_children(tree))
776 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
777 "tree does not have any explicit children",
778 return isl_schedule_tree_free(tree));
779 n = isl_schedule_tree_list_n_schedule_tree(tree->children);
780 if (pos < 0 || pos >= n)
781 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
782 "position out of bounds",
783 return isl_schedule_tree_free(tree));
784 if (n == 1)
785 return isl_schedule_tree_reset_children(tree);
787 tree->children = isl_schedule_tree_list_drop(tree->children, pos, 1);
788 if (!tree->children)
789 return isl_schedule_tree_free(tree);
791 return tree;
794 /* Replace the child at position "pos" of "tree" by "child".
796 * If the new child is a leaf, then it is not explicitly
797 * recorded in the list of children. Instead, the list of children
798 * (which is assumed to have only one element) is removed.
799 * Note that the children of set and sequence nodes are always
800 * filters, so they cannot be replaced by empty trees.
802 __isl_give isl_schedule_tree *isl_schedule_tree_replace_child(
803 __isl_take isl_schedule_tree *tree, int pos,
804 __isl_take isl_schedule_tree *child)
806 tree = isl_schedule_tree_cow(tree);
807 if (!tree || !child)
808 goto error;
810 if (isl_schedule_tree_is_leaf(child)) {
811 isl_schedule_tree_free(child);
812 if (!tree->children && pos == 0)
813 return tree;
814 if (isl_schedule_tree_n_children(tree) != 1)
815 isl_die(isl_schedule_tree_get_ctx(tree),
816 isl_error_internal,
817 "can only replace single child by leaf",
818 goto error);
819 return isl_schedule_tree_reset_children(tree);
822 if (!tree->children && pos == 0)
823 tree->children =
824 isl_schedule_tree_list_from_schedule_tree(child);
825 else
826 tree->children = isl_schedule_tree_list_set_schedule_tree(
827 tree->children, pos, child);
829 if (!tree->children)
830 return isl_schedule_tree_free(tree);
831 tree = isl_schedule_tree_update_anchored(tree);
833 return tree;
834 error:
835 isl_schedule_tree_free(tree);
836 isl_schedule_tree_free(child);
837 return NULL;
840 /* Replace the (explicit) children of "tree" by "children"?
842 __isl_give isl_schedule_tree *isl_schedule_tree_set_children(
843 __isl_take isl_schedule_tree *tree,
844 __isl_take isl_schedule_tree_list *children)
846 tree = isl_schedule_tree_cow(tree);
847 if (!tree || !children)
848 goto error;
849 isl_schedule_tree_list_free(tree->children);
850 tree->children = children;
851 return tree;
852 error:
853 isl_schedule_tree_free(tree);
854 isl_schedule_tree_list_free(children);
855 return NULL;
858 /* Create a new band schedule tree referring to "band"
859 * with "tree" as single child.
861 __isl_give isl_schedule_tree *isl_schedule_tree_insert_band(
862 __isl_take isl_schedule_tree *tree, __isl_take isl_schedule_band *band)
864 isl_schedule_tree *res;
866 res = isl_schedule_tree_from_band(band);
867 return isl_schedule_tree_replace_child(res, 0, tree);
870 /* Create a new context schedule tree with the given context and
871 * with "tree" as single child.
873 __isl_give isl_schedule_tree *isl_schedule_tree_insert_context(
874 __isl_take isl_schedule_tree *tree, __isl_take isl_set *context)
876 isl_schedule_tree *res;
878 res = isl_schedule_tree_from_context(context);
879 return isl_schedule_tree_replace_child(res, 0, tree);
882 /* Create a new domain schedule tree with the given domain and
883 * with "tree" as single child.
885 __isl_give isl_schedule_tree *isl_schedule_tree_insert_domain(
886 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
888 isl_schedule_tree *res;
890 res = isl_schedule_tree_from_domain(domain);
891 return isl_schedule_tree_replace_child(res, 0, tree);
894 /* Create a new expansion schedule tree with the given contraction and
895 * expansion and with "tree" as single child.
897 __isl_give isl_schedule_tree *isl_schedule_tree_insert_expansion(
898 __isl_take isl_schedule_tree *tree,
899 __isl_take isl_union_pw_multi_aff *contraction,
900 __isl_take isl_union_map *expansion)
902 isl_schedule_tree *res;
904 res = isl_schedule_tree_from_expansion(contraction, expansion);
905 return isl_schedule_tree_replace_child(res, 0, tree);
908 /* Create a new extension schedule tree with the given extension and
909 * with "tree" as single child.
911 __isl_give isl_schedule_tree *isl_schedule_tree_insert_extension(
912 __isl_take isl_schedule_tree *tree, __isl_take isl_union_map *extension)
914 isl_schedule_tree *res;
916 res = isl_schedule_tree_from_extension(extension);
917 return isl_schedule_tree_replace_child(res, 0, tree);
920 /* Create a new filter schedule tree with the given filter and single child.
922 * If the root of "tree" is itself a filter node, then the two
923 * filter nodes are merged into one node.
925 __isl_give isl_schedule_tree *isl_schedule_tree_insert_filter(
926 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
928 isl_schedule_tree *res;
930 if (isl_schedule_tree_get_type(tree) == isl_schedule_node_filter) {
931 isl_union_set *tree_filter;
933 tree_filter = isl_schedule_tree_filter_get_filter(tree);
934 tree_filter = isl_union_set_intersect(tree_filter, filter);
935 tree = isl_schedule_tree_filter_set_filter(tree, tree_filter);
936 return tree;
939 res = isl_schedule_tree_from_filter(filter);
940 return isl_schedule_tree_replace_child(res, 0, tree);
943 /* Insert a filter node with filter set "filter"
944 * in each of the children of "tree".
946 __isl_give isl_schedule_tree *isl_schedule_tree_children_insert_filter(
947 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
949 int i, n;
951 if (!tree || !filter)
952 goto error;
954 n = isl_schedule_tree_n_children(tree);
955 for (i = 0; i < n; ++i) {
956 isl_schedule_tree *child;
958 child = isl_schedule_tree_get_child(tree, i);
959 child = isl_schedule_tree_insert_filter(child,
960 isl_union_set_copy(filter));
961 tree = isl_schedule_tree_replace_child(tree, i, child);
964 isl_union_set_free(filter);
965 return tree;
966 error:
967 isl_union_set_free(filter);
968 isl_schedule_tree_free(tree);
969 return NULL;
972 /* Create a new guard schedule tree with the given guard and
973 * with "tree" as single child.
975 __isl_give isl_schedule_tree *isl_schedule_tree_insert_guard(
976 __isl_take isl_schedule_tree *tree, __isl_take isl_set *guard)
978 isl_schedule_tree *res;
980 res = isl_schedule_tree_from_guard(guard);
981 return isl_schedule_tree_replace_child(res, 0, tree);
984 /* Create a new mark schedule tree with the given mark identifier and
985 * single child.
987 __isl_give isl_schedule_tree *isl_schedule_tree_insert_mark(
988 __isl_take isl_schedule_tree *tree, __isl_take isl_id *mark)
990 isl_schedule_tree *res;
992 res = isl_schedule_tree_from_mark(mark);
993 return isl_schedule_tree_replace_child(res, 0, tree);
996 /* Return the number of members in the band tree root.
998 unsigned isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree *tree)
1000 if (!tree)
1001 return 0;
1003 if (tree->type != isl_schedule_node_band)
1004 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1005 "not a band node", return 0);
1007 return isl_schedule_band_n_member(tree->band);
1010 /* Is the band member at position "pos" of the band tree root
1011 * marked coincident?
1013 isl_bool isl_schedule_tree_band_member_get_coincident(
1014 __isl_keep isl_schedule_tree *tree, int pos)
1016 if (!tree)
1017 return isl_bool_error;
1019 if (tree->type != isl_schedule_node_band)
1020 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1021 "not a band node", return isl_bool_error);
1023 return isl_schedule_band_member_get_coincident(tree->band, pos);
1026 /* Mark the given band member as being coincident or not
1027 * according to "coincident".
1029 __isl_give isl_schedule_tree *isl_schedule_tree_band_member_set_coincident(
1030 __isl_take isl_schedule_tree *tree, int pos, int coincident)
1032 if (!tree)
1033 return NULL;
1034 if (tree->type != isl_schedule_node_band)
1035 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1036 "not a band node", return isl_schedule_tree_free(tree));
1037 if (isl_schedule_tree_band_member_get_coincident(tree, pos) ==
1038 coincident)
1039 return tree;
1040 tree = isl_schedule_tree_cow(tree);
1041 if (!tree)
1042 return NULL;
1044 tree->band = isl_schedule_band_member_set_coincident(tree->band, pos,
1045 coincident);
1046 if (!tree->band)
1047 return isl_schedule_tree_free(tree);
1048 return tree;
1051 /* Is the band tree root marked permutable?
1053 isl_bool isl_schedule_tree_band_get_permutable(
1054 __isl_keep isl_schedule_tree *tree)
1056 if (!tree)
1057 return isl_bool_error;
1059 if (tree->type != isl_schedule_node_band)
1060 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1061 "not a band node", return isl_bool_error);
1063 return isl_schedule_band_get_permutable(tree->band);
1066 /* Mark the band tree root permutable or not according to "permutable"?
1068 __isl_give isl_schedule_tree *isl_schedule_tree_band_set_permutable(
1069 __isl_take isl_schedule_tree *tree, int permutable)
1071 if (!tree)
1072 return NULL;
1073 if (tree->type != isl_schedule_node_band)
1074 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1075 "not a band node", return isl_schedule_tree_free(tree));
1076 if (isl_schedule_tree_band_get_permutable(tree) == permutable)
1077 return tree;
1078 tree = isl_schedule_tree_cow(tree);
1079 if (!tree)
1080 return NULL;
1082 tree->band = isl_schedule_band_set_permutable(tree->band, permutable);
1083 if (!tree->band)
1084 return isl_schedule_tree_free(tree);
1085 return tree;
1088 /* Return the schedule space of the band tree root.
1090 __isl_give isl_space *isl_schedule_tree_band_get_space(
1091 __isl_keep isl_schedule_tree *tree)
1093 if (!tree)
1094 return NULL;
1096 if (tree->type != isl_schedule_node_band)
1097 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1098 "not a band node", return NULL);
1100 return isl_schedule_band_get_space(tree->band);
1103 /* Intersect the domain of the band schedule of the band tree root
1104 * with "domain".
1106 __isl_give isl_schedule_tree *isl_schedule_tree_band_intersect_domain(
1107 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
1109 if (!tree || !domain)
1110 goto error;
1112 if (tree->type != isl_schedule_node_band)
1113 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1114 "not a band node", goto error);
1116 tree->band = isl_schedule_band_intersect_domain(tree->band, domain);
1117 if (!tree->band)
1118 return isl_schedule_tree_free(tree);
1120 return tree;
1121 error:
1122 isl_schedule_tree_free(tree);
1123 isl_union_set_free(domain);
1124 return NULL;
1127 /* Return the schedule of the band tree root in isolation.
1129 __isl_give isl_multi_union_pw_aff *isl_schedule_tree_band_get_partial_schedule(
1130 __isl_keep isl_schedule_tree *tree)
1132 if (!tree)
1133 return NULL;
1135 if (tree->type != isl_schedule_node_band)
1136 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1137 "not a band node", return NULL);
1139 return isl_schedule_band_get_partial_schedule(tree->band);
1142 /* Replace the schedule of the band tree root by "schedule".
1144 __isl_give isl_schedule_tree *isl_schedule_tree_band_set_partial_schedule(
1145 __isl_take isl_schedule_tree *tree,
1146 __isl_take isl_multi_union_pw_aff *schedule)
1148 tree = isl_schedule_tree_cow(tree);
1149 if (!tree || !schedule)
1150 goto error;
1152 if (tree->type != isl_schedule_node_band)
1153 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1154 "not a band node", return NULL);
1155 tree->band = isl_schedule_band_set_partial_schedule(tree->band,
1156 schedule);
1158 return tree;
1159 error:
1160 isl_schedule_tree_free(tree);
1161 isl_multi_union_pw_aff_free(schedule);
1162 return NULL;
1165 /* Return the loop AST generation type for the band member
1166 * of the band tree root at position "pos".
1168 enum isl_ast_loop_type isl_schedule_tree_band_member_get_ast_loop_type(
1169 __isl_keep isl_schedule_tree *tree, int pos)
1171 if (!tree)
1172 return isl_ast_loop_error;
1174 if (tree->type != isl_schedule_node_band)
1175 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1176 "not a band node", return isl_ast_loop_error);
1178 return isl_schedule_band_member_get_ast_loop_type(tree->band, pos);
1181 /* Set the loop AST generation type for the band member of the band tree root
1182 * at position "pos" to "type".
1184 __isl_give isl_schedule_tree *isl_schedule_tree_band_member_set_ast_loop_type(
1185 __isl_take isl_schedule_tree *tree, int pos,
1186 enum isl_ast_loop_type type)
1188 tree = isl_schedule_tree_cow(tree);
1189 if (!tree)
1190 return NULL;
1192 if (tree->type != isl_schedule_node_band)
1193 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1194 "not a band node", return isl_schedule_tree_free(tree));
1196 tree->band = isl_schedule_band_member_set_ast_loop_type(tree->band,
1197 pos, type);
1198 if (!tree->band)
1199 return isl_schedule_tree_free(tree);
1201 return tree;
1204 /* Return the loop AST generation type for the band member
1205 * of the band tree root at position "pos" for the isolated part.
1207 enum isl_ast_loop_type isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1208 __isl_keep isl_schedule_tree *tree, int pos)
1210 if (!tree)
1211 return isl_ast_loop_error;
1213 if (tree->type != isl_schedule_node_band)
1214 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1215 "not a band node", return isl_ast_loop_error);
1217 return isl_schedule_band_member_get_isolate_ast_loop_type(tree->band,
1218 pos);
1221 /* Set the loop AST generation type for the band member of the band tree root
1222 * at position "pos" for the isolated part to "type".
1224 __isl_give isl_schedule_tree *
1225 isl_schedule_tree_band_member_set_isolate_ast_loop_type(
1226 __isl_take isl_schedule_tree *tree, int pos,
1227 enum isl_ast_loop_type type)
1229 tree = isl_schedule_tree_cow(tree);
1230 if (!tree)
1231 return NULL;
1233 if (tree->type != isl_schedule_node_band)
1234 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1235 "not a band node", return isl_schedule_tree_free(tree));
1237 tree->band = isl_schedule_band_member_set_isolate_ast_loop_type(
1238 tree->band, pos, type);
1239 if (!tree->band)
1240 return isl_schedule_tree_free(tree);
1242 return tree;
1245 /* Return the AST build options associated to the band tree root.
1247 __isl_give isl_union_set *isl_schedule_tree_band_get_ast_build_options(
1248 __isl_keep isl_schedule_tree *tree)
1250 if (!tree)
1251 return NULL;
1253 if (tree->type != isl_schedule_node_band)
1254 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1255 "not a band node", return NULL);
1257 return isl_schedule_band_get_ast_build_options(tree->band);
1260 /* Replace the AST build options associated to band tree root by "options".
1261 * Updated the anchored field if the anchoredness of the root node itself
1262 * changes.
1264 __isl_give isl_schedule_tree *isl_schedule_tree_band_set_ast_build_options(
1265 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *options)
1267 int was_anchored;
1269 tree = isl_schedule_tree_cow(tree);
1270 if (!tree || !options)
1271 goto error;
1273 if (tree->type != isl_schedule_node_band)
1274 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1275 "not a band node", goto error);
1277 was_anchored = isl_schedule_tree_is_anchored(tree);
1278 tree->band = isl_schedule_band_set_ast_build_options(tree->band,
1279 options);
1280 if (!tree->band)
1281 return isl_schedule_tree_free(tree);
1282 if (isl_schedule_tree_is_anchored(tree) != was_anchored)
1283 tree = isl_schedule_tree_update_anchored(tree);
1285 return tree;
1286 error:
1287 isl_schedule_tree_free(tree);
1288 isl_union_set_free(options);
1289 return NULL;
1292 /* Return the "isolate" option associated to the band tree root of "tree",
1293 * which is assumed to appear at schedule depth "depth".
1295 __isl_give isl_set *isl_schedule_tree_band_get_ast_isolate_option(
1296 __isl_keep isl_schedule_tree *tree, int depth)
1298 if (!tree)
1299 return NULL;
1301 if (tree->type != isl_schedule_node_band)
1302 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1303 "not a band node", return NULL);
1305 return isl_schedule_band_get_ast_isolate_option(tree->band, depth);
1308 /* Return the context of the context tree root.
1310 __isl_give isl_set *isl_schedule_tree_context_get_context(
1311 __isl_keep isl_schedule_tree *tree)
1313 if (!tree)
1314 return NULL;
1316 if (tree->type != isl_schedule_node_context)
1317 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1318 "not a context node", return NULL);
1320 return isl_set_copy(tree->context);
1323 /* Return the domain of the domain tree root.
1325 __isl_give isl_union_set *isl_schedule_tree_domain_get_domain(
1326 __isl_keep isl_schedule_tree *tree)
1328 if (!tree)
1329 return NULL;
1331 if (tree->type != isl_schedule_node_domain)
1332 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1333 "not a domain node", return NULL);
1335 return isl_union_set_copy(tree->domain);
1338 /* Replace the domain of domain tree root "tree" by "domain".
1340 __isl_give isl_schedule_tree *isl_schedule_tree_domain_set_domain(
1341 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
1343 tree = isl_schedule_tree_cow(tree);
1344 if (!tree || !domain)
1345 goto error;
1347 if (tree->type != isl_schedule_node_domain)
1348 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1349 "not a domain node", goto error);
1351 isl_union_set_free(tree->domain);
1352 tree->domain = domain;
1354 return tree;
1355 error:
1356 isl_schedule_tree_free(tree);
1357 isl_union_set_free(domain);
1358 return NULL;
1361 /* Return the contraction of the expansion tree root.
1363 __isl_give isl_union_pw_multi_aff *isl_schedule_tree_expansion_get_contraction(
1364 __isl_keep isl_schedule_tree *tree)
1366 if (!tree)
1367 return NULL;
1369 if (tree->type != isl_schedule_node_expansion)
1370 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1371 "not an expansion node", return NULL);
1373 return isl_union_pw_multi_aff_copy(tree->contraction);
1376 /* Return the expansion of the expansion tree root.
1378 __isl_give isl_union_map *isl_schedule_tree_expansion_get_expansion(
1379 __isl_keep isl_schedule_tree *tree)
1381 if (!tree)
1382 return NULL;
1384 if (tree->type != isl_schedule_node_expansion)
1385 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1386 "not an expansion node", return NULL);
1388 return isl_union_map_copy(tree->expansion);
1391 /* Replace the contraction and the expansion of the expansion tree root "tree"
1392 * by "contraction" and "expansion".
1394 __isl_give isl_schedule_tree *
1395 isl_schedule_tree_expansion_set_contraction_and_expansion(
1396 __isl_take isl_schedule_tree *tree,
1397 __isl_take isl_union_pw_multi_aff *contraction,
1398 __isl_take isl_union_map *expansion)
1400 tree = isl_schedule_tree_cow(tree);
1401 if (!tree || !contraction || !expansion)
1402 goto error;
1404 if (tree->type != isl_schedule_node_expansion)
1405 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1406 "not an expansion node", return NULL);
1408 isl_union_pw_multi_aff_free(tree->contraction);
1409 tree->contraction = contraction;
1410 isl_union_map_free(tree->expansion);
1411 tree->expansion = expansion;
1413 return tree;
1414 error:
1415 isl_schedule_tree_free(tree);
1416 isl_union_pw_multi_aff_free(contraction);
1417 isl_union_map_free(expansion);
1418 return NULL;
1421 /* Return the extension of the extension tree root.
1423 __isl_give isl_union_map *isl_schedule_tree_extension_get_extension(
1424 __isl_take isl_schedule_tree *tree)
1426 if (!tree)
1427 return NULL;
1429 if (tree->type != isl_schedule_node_extension)
1430 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1431 "not an extension node", return NULL);
1433 return isl_union_map_copy(tree->extension);
1436 /* Replace the extension of extension tree root "tree" by "extension".
1438 __isl_give isl_schedule_tree *isl_schedule_tree_extension_set_extension(
1439 __isl_take isl_schedule_tree *tree, __isl_take isl_union_map *extension)
1441 tree = isl_schedule_tree_cow(tree);
1442 if (!tree || !extension)
1443 goto error;
1445 if (tree->type != isl_schedule_node_extension)
1446 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1447 "not an extension node", return NULL);
1448 isl_union_map_free(tree->extension);
1449 tree->extension = extension;
1451 return tree;
1452 error:
1453 isl_schedule_tree_free(tree);
1454 isl_union_map_free(extension);
1455 return NULL;
1458 /* Return the filter of the filter tree root.
1460 __isl_give isl_union_set *isl_schedule_tree_filter_get_filter(
1461 __isl_keep isl_schedule_tree *tree)
1463 if (!tree)
1464 return NULL;
1466 if (tree->type != isl_schedule_node_filter)
1467 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1468 "not a filter node", return NULL);
1470 return isl_union_set_copy(tree->filter);
1473 /* Replace the filter of the filter tree root by "filter".
1475 __isl_give isl_schedule_tree *isl_schedule_tree_filter_set_filter(
1476 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
1478 tree = isl_schedule_tree_cow(tree);
1479 if (!tree || !filter)
1480 goto error;
1482 if (tree->type != isl_schedule_node_filter)
1483 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1484 "not a filter node", return NULL);
1486 isl_union_set_free(tree->filter);
1487 tree->filter = filter;
1489 return tree;
1490 error:
1491 isl_schedule_tree_free(tree);
1492 isl_union_set_free(filter);
1493 return NULL;
1496 /* Return the guard of the guard tree root.
1498 __isl_give isl_set *isl_schedule_tree_guard_get_guard(
1499 __isl_take isl_schedule_tree *tree)
1501 if (!tree)
1502 return NULL;
1504 if (tree->type != isl_schedule_node_guard)
1505 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1506 "not a guard node", return NULL);
1508 return isl_set_copy(tree->guard);
1511 /* Return the mark identifier of the mark tree root "tree".
1513 __isl_give isl_id *isl_schedule_tree_mark_get_id(
1514 __isl_keep isl_schedule_tree *tree)
1516 if (!tree)
1517 return NULL;
1519 if (tree->type != isl_schedule_node_mark)
1520 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1521 "not a mark node", return NULL);
1523 return isl_id_copy(tree->mark);
1526 /* Set dim to the range dimension of "map" and abort the search.
1528 static isl_stat set_range_dim(__isl_take isl_map *map, void *user)
1530 int *dim = user;
1532 *dim = isl_map_dim(map, isl_dim_out);
1533 isl_map_free(map);
1535 return isl_stat_error;
1538 /* Return the dimension of the range of "umap".
1539 * "umap" is assumed not to be empty and
1540 * all maps inside "umap" are assumed to have the same range.
1542 * We extract the range dimension from the first map in "umap".
1544 static int range_dim(__isl_keep isl_union_map *umap)
1546 int dim = -1;
1548 if (!umap)
1549 return -1;
1550 if (isl_union_map_n_map(umap) == 0)
1551 isl_die(isl_union_map_get_ctx(umap), isl_error_internal,
1552 "unexpected empty input", return -1);
1554 isl_union_map_foreach_map(umap, &set_range_dim, &dim);
1556 return dim;
1559 /* Append an "extra" number of zeros to the range of "umap" and
1560 * return the result.
1562 static __isl_give isl_union_map *append_range(__isl_take isl_union_map *umap,
1563 int extra)
1565 isl_union_set *dom;
1566 isl_space *space;
1567 isl_multi_val *mv;
1568 isl_union_pw_multi_aff *suffix;
1569 isl_union_map *universe;
1570 isl_union_map *suffix_umap;
1572 universe = isl_union_map_universe(isl_union_map_copy(umap));
1573 dom = isl_union_map_domain(universe);
1574 space = isl_union_set_get_space(dom);
1575 space = isl_space_set_from_params(space);
1576 space = isl_space_add_dims(space, isl_dim_set, extra);
1577 mv = isl_multi_val_zero(space);
1579 suffix = isl_union_pw_multi_aff_multi_val_on_domain(dom, mv);
1580 suffix_umap = isl_union_map_from_union_pw_multi_aff(suffix);
1581 umap = isl_union_map_flat_range_product(umap, suffix_umap);
1583 return umap;
1586 /* Should we skip the root of "tree" while looking for the first
1587 * descendant with schedule information?
1588 * That is, is it impossible to derive any information about
1589 * the iteration domain from this node?
1591 * We do not want to skip leaf or error nodes because there is
1592 * no point in looking any deeper from these nodes.
1593 * We can only extract partial iteration domain information
1594 * from an extension node, but extension nodes are not supported
1595 * by the caller and it will error out on them.
1597 static int domain_less(__isl_keep isl_schedule_tree *tree)
1599 enum isl_schedule_node_type type;
1601 type = isl_schedule_tree_get_type(tree);
1602 switch (type) {
1603 case isl_schedule_node_band:
1604 return isl_schedule_tree_band_n_member(tree) == 0;
1605 case isl_schedule_node_context:
1606 case isl_schedule_node_guard:
1607 case isl_schedule_node_mark:
1608 return 1;
1609 case isl_schedule_node_leaf:
1610 case isl_schedule_node_error:
1611 case isl_schedule_node_domain:
1612 case isl_schedule_node_expansion:
1613 case isl_schedule_node_extension:
1614 case isl_schedule_node_filter:
1615 case isl_schedule_node_set:
1616 case isl_schedule_node_sequence:
1617 return 0;
1620 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1621 "unhandled case", return 0);
1624 /* Move down to the first descendant of "tree" that contains any schedule
1625 * information or return "leaf" if there is no such descendant.
1627 __isl_give isl_schedule_tree *isl_schedule_tree_first_schedule_descendant(
1628 __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_tree *leaf)
1630 while (domain_less(tree)) {
1631 if (!isl_schedule_tree_has_children(tree)) {
1632 isl_schedule_tree_free(tree);
1633 return isl_schedule_tree_copy(leaf);
1635 tree = isl_schedule_tree_child(tree, 0);
1638 return tree;
1641 static __isl_give isl_union_map *subtree_schedule_extend(
1642 __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer);
1644 /* Extend the schedule map "outer" with the subtree schedule
1645 * of the (single) child of "tree", if any.
1647 * If "tree" does not have any descendants (apart from those that
1648 * do not carry any schedule information), then we simply return "outer".
1649 * Otherwise, we extend the schedule map "outer" with the subtree schedule
1650 * of the single child.
1652 static __isl_give isl_union_map *subtree_schedule_extend_child(
1653 __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1655 isl_schedule_tree *child;
1656 isl_union_map *res;
1658 if (!tree)
1659 return isl_union_map_free(outer);
1660 if (!isl_schedule_tree_has_children(tree))
1661 return outer;
1662 child = isl_schedule_tree_get_child(tree, 0);
1663 if (!child)
1664 return isl_union_map_free(outer);
1665 res = subtree_schedule_extend(child, outer);
1666 isl_schedule_tree_free(child);
1667 return res;
1670 /* Extract the parameter space from one of the children of "tree",
1671 * which are assumed to be filters.
1673 static __isl_give isl_space *extract_space_from_filter_child(
1674 __isl_keep isl_schedule_tree *tree)
1676 isl_space *space;
1677 isl_union_set *dom;
1678 isl_schedule_tree *child;
1680 child = isl_schedule_tree_list_get_schedule_tree(tree->children, 0);
1681 dom = isl_schedule_tree_filter_get_filter(child);
1682 space = isl_union_set_get_space(dom);
1683 isl_union_set_free(dom);
1684 isl_schedule_tree_free(child);
1686 return space;
1689 /* Extend the schedule map "outer" with the subtree schedule
1690 * of a set or sequence node.
1692 * The schedule for the set or sequence node itself is composed of
1693 * pieces of the form
1695 * filter -> []
1697 * or
1699 * filter -> [index]
1701 * The first form is used if there is only a single child or
1702 * if the current node is a set node and the schedule_separate_components
1703 * option is not set.
1705 * Each of the pieces above is extended with the subtree schedule of
1706 * the child of the corresponding filter, if any, padded with zeros
1707 * to ensure that all pieces have the same range dimension.
1709 static __isl_give isl_union_map *subtree_schedule_extend_from_children(
1710 __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1712 int i, n;
1713 int dim;
1714 int separate;
1715 isl_ctx *ctx;
1716 isl_val *v = NULL;
1717 isl_multi_val *mv;
1718 isl_space *space;
1719 isl_union_map *umap;
1721 if (!tree)
1722 return NULL;
1724 ctx = isl_schedule_tree_get_ctx(tree);
1725 if (!tree->children)
1726 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1727 "missing children", return NULL);
1728 n = isl_schedule_tree_list_n_schedule_tree(tree->children);
1729 if (n == 0)
1730 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1731 "missing children", return NULL);
1733 separate = n > 1 && (tree->type == isl_schedule_node_sequence ||
1734 isl_options_get_schedule_separate_components(ctx));
1736 space = extract_space_from_filter_child(tree);
1738 umap = isl_union_map_empty(isl_space_copy(space));
1739 space = isl_space_set_from_params(space);
1740 if (separate) {
1741 space = isl_space_add_dims(space, isl_dim_set, 1);
1742 v = isl_val_zero(ctx);
1744 mv = isl_multi_val_zero(space);
1746 dim = isl_multi_val_dim(mv, isl_dim_set);
1747 for (i = 0; i < n; ++i) {
1748 isl_union_pw_multi_aff *upma;
1749 isl_union_map *umap_i;
1750 isl_union_set *dom;
1751 isl_schedule_tree *child;
1752 int dim_i;
1753 int empty;
1755 child = isl_schedule_tree_list_get_schedule_tree(
1756 tree->children, i);
1757 dom = isl_schedule_tree_filter_get_filter(child);
1759 if (separate) {
1760 mv = isl_multi_val_set_val(mv, 0, isl_val_copy(v));
1761 v = isl_val_add_ui(v, 1);
1763 upma = isl_union_pw_multi_aff_multi_val_on_domain(dom,
1764 isl_multi_val_copy(mv));
1765 umap_i = isl_union_map_from_union_pw_multi_aff(upma);
1766 umap_i = isl_union_map_flat_range_product(
1767 isl_union_map_copy(outer), umap_i);
1768 umap_i = subtree_schedule_extend_child(child, umap_i);
1769 isl_schedule_tree_free(child);
1771 empty = isl_union_map_is_empty(umap_i);
1772 if (empty < 0)
1773 umap_i = isl_union_map_free(umap_i);
1774 else if (empty) {
1775 isl_union_map_free(umap_i);
1776 continue;
1779 dim_i = range_dim(umap_i);
1780 if (dim_i < 0) {
1781 umap = isl_union_map_free(umap);
1782 } else if (dim < dim_i) {
1783 umap = append_range(umap, dim_i - dim);
1784 dim = dim_i;
1785 } else if (dim_i < dim) {
1786 umap_i = append_range(umap_i, dim - dim_i);
1788 umap = isl_union_map_union(umap, umap_i);
1791 isl_val_free(v);
1792 isl_multi_val_free(mv);
1793 isl_union_map_free(outer);
1795 return umap;
1798 /* Extend the schedule map "outer" with the subtree schedule of "tree".
1800 * If the root of the tree is a set or a sequence, then we extend
1801 * the schedule map in subtree_schedule_extend_from_children.
1802 * Otherwise, we extend the schedule map with the partial schedule
1803 * corresponding to the root of the tree and then continue with
1804 * the single child of this root.
1805 * In the special case of an expansion, the schedule map is "extended"
1806 * by applying the expansion to the domain of the schedule map.
1808 static __isl_give isl_union_map *subtree_schedule_extend(
1809 __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1811 isl_multi_union_pw_aff *mupa;
1812 isl_union_map *umap;
1813 isl_union_set *domain;
1815 if (!tree)
1816 return NULL;
1818 switch (tree->type) {
1819 case isl_schedule_node_error:
1820 return isl_union_map_free(outer);
1821 case isl_schedule_node_extension:
1822 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1823 "cannot construct subtree schedule of tree "
1824 "with extension nodes",
1825 return isl_union_map_free(outer));
1826 case isl_schedule_node_context:
1827 case isl_schedule_node_guard:
1828 case isl_schedule_node_mark:
1829 return subtree_schedule_extend_child(tree, outer);
1830 case isl_schedule_node_band:
1831 if (isl_schedule_tree_band_n_member(tree) == 0)
1832 return subtree_schedule_extend_child(tree, outer);
1833 mupa = isl_schedule_band_get_partial_schedule(tree->band);
1834 umap = isl_union_map_from_multi_union_pw_aff(mupa);
1835 outer = isl_union_map_flat_range_product(outer, umap);
1836 umap = subtree_schedule_extend_child(tree, outer);
1837 break;
1838 case isl_schedule_node_domain:
1839 domain = isl_schedule_tree_domain_get_domain(tree);
1840 umap = isl_union_map_from_domain(domain);
1841 outer = isl_union_map_flat_range_product(outer, umap);
1842 umap = subtree_schedule_extend_child(tree, outer);
1843 break;
1844 case isl_schedule_node_expansion:
1845 umap = isl_schedule_tree_expansion_get_expansion(tree);
1846 outer = isl_union_map_apply_domain(outer, umap);
1847 umap = subtree_schedule_extend_child(tree, outer);
1848 break;
1849 case isl_schedule_node_filter:
1850 domain = isl_schedule_tree_filter_get_filter(tree);
1851 umap = isl_union_map_from_domain(domain);
1852 outer = isl_union_map_flat_range_product(outer, umap);
1853 umap = subtree_schedule_extend_child(tree, outer);
1854 break;
1855 case isl_schedule_node_leaf:
1856 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1857 "leaf node should be handled by caller", return NULL);
1858 case isl_schedule_node_set:
1859 case isl_schedule_node_sequence:
1860 umap = subtree_schedule_extend_from_children(tree, outer);
1861 break;
1864 return umap;
1867 static __isl_give isl_union_set *initial_domain(
1868 __isl_keep isl_schedule_tree *tree);
1870 /* Extract a universe domain from the children of the tree root "tree",
1871 * which is a set or sequence, meaning that its children are filters.
1872 * In particular, return the union of the universes of the filters.
1874 static __isl_give isl_union_set *initial_domain_from_children(
1875 __isl_keep isl_schedule_tree *tree)
1877 int i, n;
1878 isl_space *space;
1879 isl_union_set *domain;
1881 if (!tree->children)
1882 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1883 "missing children", return NULL);
1884 n = isl_schedule_tree_list_n_schedule_tree(tree->children);
1885 if (n == 0)
1886 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1887 "missing children", return NULL);
1889 space = extract_space_from_filter_child(tree);
1890 domain = isl_union_set_empty(space);
1892 for (i = 0; i < n; ++i) {
1893 isl_schedule_tree *child;
1894 isl_union_set *domain_i;
1896 child = isl_schedule_tree_get_child(tree, i);
1897 domain_i = initial_domain(child);
1898 domain = isl_union_set_union(domain, domain_i);
1899 isl_schedule_tree_free(child);
1902 return domain;
1905 /* Extract a universe domain from the tree root "tree".
1906 * The caller is responsible for making sure that this node
1907 * would not be skipped by isl_schedule_tree_first_schedule_descendant
1908 * and that it is not a leaf node.
1910 static __isl_give isl_union_set *initial_domain(
1911 __isl_keep isl_schedule_tree *tree)
1913 isl_multi_union_pw_aff *mupa;
1914 isl_union_set *domain;
1915 isl_union_map *exp;
1917 if (!tree)
1918 return NULL;
1920 switch (tree->type) {
1921 case isl_schedule_node_error:
1922 return NULL;
1923 case isl_schedule_node_context:
1924 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1925 "context node should be handled by caller",
1926 return NULL);
1927 case isl_schedule_node_guard:
1928 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1929 "guard node should be handled by caller",
1930 return NULL);
1931 case isl_schedule_node_mark:
1932 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1933 "mark node should be handled by caller",
1934 return NULL);
1935 case isl_schedule_node_extension:
1936 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1937 "cannot construct subtree schedule of tree "
1938 "with extension nodes", return NULL);
1939 case isl_schedule_node_band:
1940 if (isl_schedule_tree_band_n_member(tree) == 0)
1941 isl_die(isl_schedule_tree_get_ctx(tree),
1942 isl_error_internal,
1943 "0D band should be handled by caller",
1944 return NULL);
1945 mupa = isl_schedule_band_get_partial_schedule(tree->band);
1946 domain = isl_multi_union_pw_aff_domain(mupa);
1947 domain = isl_union_set_universe(domain);
1948 break;
1949 case isl_schedule_node_domain:
1950 domain = isl_schedule_tree_domain_get_domain(tree);
1951 domain = isl_union_set_universe(domain);
1952 break;
1953 case isl_schedule_node_expansion:
1954 exp = isl_schedule_tree_expansion_get_expansion(tree);
1955 exp = isl_union_map_universe(exp);
1956 domain = isl_union_map_domain(exp);
1957 break;
1958 case isl_schedule_node_filter:
1959 domain = isl_schedule_tree_filter_get_filter(tree);
1960 domain = isl_union_set_universe(domain);
1961 break;
1962 case isl_schedule_node_leaf:
1963 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1964 "leaf node should be handled by caller", return NULL);
1965 case isl_schedule_node_set:
1966 case isl_schedule_node_sequence:
1967 domain = initial_domain_from_children(tree);
1968 break;
1971 return domain;
1974 /* Return the subtree schedule of a node that contains some schedule
1975 * information, i.e., a node that would not be skipped by
1976 * isl_schedule_tree_first_schedule_descendant and that is not a leaf.
1978 * If the tree contains any expansions, then the returned subtree
1979 * schedule is formulated in terms of the expanded domains.
1980 * The tree is not allowed to contain any extension nodes.
1982 * We start with an initial zero-dimensional subtree schedule based
1983 * on the domain information in the root node and then extend it
1984 * based on the schedule information in the root node and its descendants.
1986 __isl_give isl_union_map *isl_schedule_tree_get_subtree_schedule_union_map(
1987 __isl_keep isl_schedule_tree *tree)
1989 isl_union_set *domain;
1990 isl_union_map *umap;
1992 domain = initial_domain(tree);
1993 umap = isl_union_map_from_domain(domain);
1994 return subtree_schedule_extend(tree, umap);
1997 /* Multiply the partial schedule of the band root node of "tree"
1998 * with the factors in "mv".
2000 __isl_give isl_schedule_tree *isl_schedule_tree_band_scale(
2001 __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
2003 if (!tree || !mv)
2004 goto error;
2005 if (tree->type != isl_schedule_node_band)
2006 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2007 "not a band node", goto error);
2009 tree = isl_schedule_tree_cow(tree);
2010 if (!tree)
2011 goto error;
2013 tree->band = isl_schedule_band_scale(tree->band, mv);
2014 if (!tree->band)
2015 return isl_schedule_tree_free(tree);
2017 return tree;
2018 error:
2019 isl_schedule_tree_free(tree);
2020 isl_multi_val_free(mv);
2021 return NULL;
2024 /* Divide the partial schedule of the band root node of "tree"
2025 * by the factors in "mv".
2027 __isl_give isl_schedule_tree *isl_schedule_tree_band_scale_down(
2028 __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
2030 if (!tree || !mv)
2031 goto error;
2032 if (tree->type != isl_schedule_node_band)
2033 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2034 "not a band node", goto error);
2036 tree = isl_schedule_tree_cow(tree);
2037 if (!tree)
2038 goto error;
2040 tree->band = isl_schedule_band_scale_down(tree->band, mv);
2041 if (!tree->band)
2042 return isl_schedule_tree_free(tree);
2044 return tree;
2045 error:
2046 isl_schedule_tree_free(tree);
2047 isl_multi_val_free(mv);
2048 return NULL;
2051 /* Reduce the partial schedule of the band root node of "tree"
2052 * modulo the factors in "mv".
2054 __isl_give isl_schedule_tree *isl_schedule_tree_band_mod(
2055 __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
2057 if (!tree || !mv)
2058 goto error;
2059 if (tree->type != isl_schedule_node_band)
2060 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2061 "not a band node", goto error);
2063 tree = isl_schedule_tree_cow(tree);
2064 if (!tree)
2065 goto error;
2067 tree->band = isl_schedule_band_mod(tree->band, mv);
2068 if (!tree->band)
2069 return isl_schedule_tree_free(tree);
2071 return tree;
2072 error:
2073 isl_schedule_tree_free(tree);
2074 isl_multi_val_free(mv);
2075 return NULL;
2078 /* Shift the partial schedule of the band root node of "tree" by "shift".
2080 __isl_give isl_schedule_tree *isl_schedule_tree_band_shift(
2081 __isl_take isl_schedule_tree *tree,
2082 __isl_take isl_multi_union_pw_aff *shift)
2084 if (!tree || !shift)
2085 goto error;
2086 if (tree->type != isl_schedule_node_band)
2087 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2088 "not a band node", goto error);
2090 tree = isl_schedule_tree_cow(tree);
2091 if (!tree)
2092 goto error;
2094 tree->band = isl_schedule_band_shift(tree->band, shift);
2095 if (!tree->band)
2096 return isl_schedule_tree_free(tree);
2098 return tree;
2099 error:
2100 isl_schedule_tree_free(tree);
2101 isl_multi_union_pw_aff_free(shift);
2102 return NULL;
2105 /* Given two trees with sequence roots, replace the child at position
2106 * "pos" of "tree" with the children of "child".
2108 __isl_give isl_schedule_tree *isl_schedule_tree_sequence_splice(
2109 __isl_take isl_schedule_tree *tree, int pos,
2110 __isl_take isl_schedule_tree *child)
2112 int n;
2113 isl_schedule_tree_list *list1, *list2;
2115 tree = isl_schedule_tree_cow(tree);
2116 if (!tree || !child)
2117 goto error;
2118 if (isl_schedule_tree_get_type(tree) != isl_schedule_node_sequence)
2119 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2120 "not a sequence node", goto error);
2121 n = isl_schedule_tree_n_children(tree);
2122 if (pos < 0 || pos >= n)
2123 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2124 "position out of bounds", goto error);
2125 if (isl_schedule_tree_get_type(child) != isl_schedule_node_sequence)
2126 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2127 "not a sequence node", goto error);
2129 list1 = isl_schedule_tree_list_copy(tree->children);
2130 list1 = isl_schedule_tree_list_drop(list1, pos, n - pos);
2131 list2 = isl_schedule_tree_list_copy(tree->children);
2132 list2 = isl_schedule_tree_list_drop(list2, 0, pos + 1);
2133 list1 = isl_schedule_tree_list_concat(list1,
2134 isl_schedule_tree_list_copy(child->children));
2135 list1 = isl_schedule_tree_list_concat(list1, list2);
2137 isl_schedule_tree_free(tree);
2138 isl_schedule_tree_free(child);
2139 return isl_schedule_tree_from_children(isl_schedule_node_sequence,
2140 list1);
2141 error:
2142 isl_schedule_tree_free(tree);
2143 isl_schedule_tree_free(child);
2144 return NULL;
2147 /* Tile the band root node of "tree" with tile sizes "sizes".
2149 * We duplicate the band node, change the schedule of one of them
2150 * to the tile schedule and the other to the point schedule and then
2151 * attach the point band as a child to the tile band.
2153 __isl_give isl_schedule_tree *isl_schedule_tree_band_tile(
2154 __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *sizes)
2156 isl_schedule_tree *child = NULL;
2158 if (!tree || !sizes)
2159 goto error;
2160 if (tree->type != isl_schedule_node_band)
2161 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2162 "not a band node", goto error);
2164 child = isl_schedule_tree_copy(tree);
2165 tree = isl_schedule_tree_cow(tree);
2166 child = isl_schedule_tree_cow(child);
2167 if (!tree || !child)
2168 goto error;
2170 tree->band = isl_schedule_band_tile(tree->band,
2171 isl_multi_val_copy(sizes));
2172 if (!tree->band)
2173 goto error;
2174 child->band = isl_schedule_band_point(child->band, tree->band, sizes);
2175 if (!child->band)
2176 child = isl_schedule_tree_free(child);
2178 tree = isl_schedule_tree_replace_child(tree, 0, child);
2180 return tree;
2181 error:
2182 isl_schedule_tree_free(child);
2183 isl_schedule_tree_free(tree);
2184 isl_multi_val_free(sizes);
2185 return NULL;
2188 /* Given an isolate AST generation option "isolate" for a band of size pos + n,
2189 * return the corresponding option for a band covering the first "pos"
2190 * members.
2192 * The input isolate option is of the form
2194 * isolate[[flattened outer bands] -> [pos; n]]
2196 * The output isolate option is of the form
2198 * isolate[[flattened outer bands] -> [pos]]
2200 static __isl_give isl_set *isolate_initial(__isl_keep isl_set *isolate,
2201 int pos, int n)
2203 isl_id *id;
2204 isl_map *map;
2206 isolate = isl_set_copy(isolate);
2207 id = isl_set_get_tuple_id(isolate);
2208 map = isl_set_unwrap(isolate);
2209 map = isl_map_project_out(map, isl_dim_out, pos, n);
2210 isolate = isl_map_wrap(map);
2211 isolate = isl_set_set_tuple_id(isolate, id);
2213 return isolate;
2216 /* Given an isolate AST generation option "isolate" for a band of size pos + n,
2217 * return the corresponding option for a band covering the final "n"
2218 * members within a band covering the first "pos" members.
2220 * The input isolate option is of the form
2222 * isolate[[flattened outer bands] -> [pos; n]]
2224 * The output isolate option is of the form
2226 * isolate[[flattened outer bands; pos] -> [n]]
2229 * The range is first split into
2231 * isolate[[flattened outer bands] -> [[pos] -> [n]]]
2233 * and then the first pos members are moved to the domain
2235 * isolate[[[flattened outer bands] -> [pos]] -> [n]]
2237 * after which the domain is flattened to obtain the desired output.
2239 static __isl_give isl_set *isolate_final(__isl_keep isl_set *isolate,
2240 int pos, int n)
2242 isl_id *id;
2243 isl_space *space;
2244 isl_multi_aff *ma1, *ma2;
2245 isl_map *map;
2247 isolate = isl_set_copy(isolate);
2248 id = isl_set_get_tuple_id(isolate);
2249 map = isl_set_unwrap(isolate);
2250 space = isl_space_range(isl_map_get_space(map));
2251 ma1 = isl_multi_aff_project_out_map(isl_space_copy(space),
2252 isl_dim_set, pos, n);
2253 ma2 = isl_multi_aff_project_out_map(space, isl_dim_set, 0, pos);
2254 ma1 = isl_multi_aff_range_product(ma1, ma2);
2255 map = isl_map_apply_range(map, isl_map_from_multi_aff(ma1));
2256 map = isl_map_uncurry(map);
2257 map = isl_map_flatten_domain(map);
2258 isolate = isl_map_wrap(map);
2259 isolate = isl_set_set_tuple_id(isolate, id);
2261 return isolate;
2264 /* Split the band root node of "tree" into two nested band nodes,
2265 * one with the first "pos" dimensions and
2266 * one with the remaining dimensions.
2267 * The tree is itself positioned at schedule depth "depth".
2269 * The loop AST generation type options and the isolate option
2270 * are split over the the two band nodes.
2272 __isl_give isl_schedule_tree *isl_schedule_tree_band_split(
2273 __isl_take isl_schedule_tree *tree, int pos, int depth)
2275 int n;
2276 isl_set *isolate, *tree_isolate, *child_isolate;
2277 isl_schedule_tree *child;
2279 if (!tree)
2280 return NULL;
2281 if (tree->type != isl_schedule_node_band)
2282 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2283 "not a band node", return isl_schedule_tree_free(tree));
2285 n = isl_schedule_tree_band_n_member(tree);
2286 if (pos < 0 || pos > n)
2287 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2288 "position out of bounds",
2289 return isl_schedule_tree_free(tree));
2291 child = isl_schedule_tree_copy(tree);
2292 tree = isl_schedule_tree_cow(tree);
2293 child = isl_schedule_tree_cow(child);
2294 if (!tree || !child)
2295 goto error;
2297 isolate = isl_schedule_tree_band_get_ast_isolate_option(tree, depth);
2298 tree_isolate = isolate_initial(isolate, pos, n - pos);
2299 child_isolate = isolate_final(isolate, pos, n - pos);
2300 child->band = isl_schedule_band_drop(child->band, 0, pos);
2301 child->band = isl_schedule_band_replace_ast_build_option(child->band,
2302 isl_set_copy(isolate), child_isolate);
2303 tree->band = isl_schedule_band_drop(tree->band, pos, n - pos);
2304 tree->band = isl_schedule_band_replace_ast_build_option(tree->band,
2305 isl_set_copy(isolate), tree_isolate);
2306 isl_set_free(isolate);
2307 if (!child->band || !tree->band)
2308 goto error;
2310 tree = isl_schedule_tree_replace_child(tree, 0, child);
2312 return tree;
2313 error:
2314 isl_schedule_tree_free(child);
2315 isl_schedule_tree_free(tree);
2316 return NULL;
2319 /* Attach "tree2" at each of the leaves of "tree1".
2321 * If "tree1" does not have any explicit children, then make "tree2"
2322 * its single child. Otherwise, attach "tree2" to the leaves of
2323 * each of the children of "tree1".
2325 __isl_give isl_schedule_tree *isl_schedule_tree_append_to_leaves(
2326 __isl_take isl_schedule_tree *tree1,
2327 __isl_take isl_schedule_tree *tree2)
2329 int i, n;
2331 if (!tree1 || !tree2)
2332 goto error;
2333 n = isl_schedule_tree_n_children(tree1);
2334 if (n == 0) {
2335 isl_schedule_tree_list *list;
2336 list = isl_schedule_tree_list_from_schedule_tree(tree2);
2337 tree1 = isl_schedule_tree_set_children(tree1, list);
2338 return tree1;
2340 for (i = 0; i < n; ++i) {
2341 isl_schedule_tree *child;
2343 child = isl_schedule_tree_get_child(tree1, i);
2344 child = isl_schedule_tree_append_to_leaves(child,
2345 isl_schedule_tree_copy(tree2));
2346 tree1 = isl_schedule_tree_replace_child(tree1, i, child);
2349 isl_schedule_tree_free(tree2);
2350 return tree1;
2351 error:
2352 isl_schedule_tree_free(tree1);
2353 isl_schedule_tree_free(tree2);
2354 return NULL;
2357 /* Reset the user pointer on all identifiers of parameters and tuples
2358 * in the root of "tree".
2360 __isl_give isl_schedule_tree *isl_schedule_tree_reset_user(
2361 __isl_take isl_schedule_tree *tree)
2363 if (isl_schedule_tree_is_leaf(tree))
2364 return tree;
2366 tree = isl_schedule_tree_cow(tree);
2367 if (!tree)
2368 return NULL;
2370 switch (tree->type) {
2371 case isl_schedule_node_error:
2372 return isl_schedule_tree_free(tree);
2373 case isl_schedule_node_band:
2374 tree->band = isl_schedule_band_reset_user(tree->band);
2375 if (!tree->band)
2376 return isl_schedule_tree_free(tree);
2377 break;
2378 case isl_schedule_node_context:
2379 tree->context = isl_set_reset_user(tree->context);
2380 if (!tree->context)
2381 return isl_schedule_tree_free(tree);
2382 break;
2383 case isl_schedule_node_domain:
2384 tree->domain = isl_union_set_reset_user(tree->domain);
2385 if (!tree->domain)
2386 return isl_schedule_tree_free(tree);
2387 break;
2388 case isl_schedule_node_expansion:
2389 tree->contraction =
2390 isl_union_pw_multi_aff_reset_user(tree->contraction);
2391 tree->expansion = isl_union_map_reset_user(tree->expansion);
2392 if (!tree->contraction || !tree->expansion)
2393 return isl_schedule_tree_free(tree);
2394 break;
2395 case isl_schedule_node_extension:
2396 tree->extension = isl_union_map_reset_user(tree->extension);
2397 if (!tree->extension)
2398 return isl_schedule_tree_free(tree);
2399 break;
2400 case isl_schedule_node_filter:
2401 tree->filter = isl_union_set_reset_user(tree->filter);
2402 if (!tree->filter)
2403 return isl_schedule_tree_free(tree);
2404 break;
2405 case isl_schedule_node_guard:
2406 tree->guard = isl_set_reset_user(tree->guard);
2407 if (!tree->guard)
2408 return isl_schedule_tree_free(tree);
2409 break;
2410 case isl_schedule_node_leaf:
2411 case isl_schedule_node_mark:
2412 case isl_schedule_node_sequence:
2413 case isl_schedule_node_set:
2414 break;
2417 return tree;
2420 /* Align the parameters of the root of "tree" to those of "space".
2422 __isl_give isl_schedule_tree *isl_schedule_tree_align_params(
2423 __isl_take isl_schedule_tree *tree, __isl_take isl_space *space)
2425 if (!space)
2426 goto error;
2428 if (isl_schedule_tree_is_leaf(tree)) {
2429 isl_space_free(space);
2430 return tree;
2433 tree = isl_schedule_tree_cow(tree);
2434 if (!tree)
2435 goto error;
2437 switch (tree->type) {
2438 case isl_schedule_node_error:
2439 goto error;
2440 case isl_schedule_node_band:
2441 tree->band = isl_schedule_band_align_params(tree->band, space);
2442 if (!tree->band)
2443 return isl_schedule_tree_free(tree);
2444 break;
2445 case isl_schedule_node_context:
2446 tree->context = isl_set_align_params(tree->context, space);
2447 if (!tree->context)
2448 return isl_schedule_tree_free(tree);
2449 break;
2450 case isl_schedule_node_domain:
2451 tree->domain = isl_union_set_align_params(tree->domain, space);
2452 if (!tree->domain)
2453 return isl_schedule_tree_free(tree);
2454 break;
2455 case isl_schedule_node_expansion:
2456 tree->contraction =
2457 isl_union_pw_multi_aff_align_params(tree->contraction,
2458 isl_space_copy(space));
2459 tree->expansion = isl_union_map_align_params(tree->expansion,
2460 space);
2461 if (!tree->contraction || !tree->expansion)
2462 return isl_schedule_tree_free(tree);
2463 break;
2464 case isl_schedule_node_extension:
2465 tree->extension = isl_union_map_align_params(tree->extension,
2466 space);
2467 if (!tree->extension)
2468 return isl_schedule_tree_free(tree);
2469 break;
2470 case isl_schedule_node_filter:
2471 tree->filter = isl_union_set_align_params(tree->filter, space);
2472 if (!tree->filter)
2473 return isl_schedule_tree_free(tree);
2474 break;
2475 case isl_schedule_node_guard:
2476 tree->guard = isl_set_align_params(tree->guard, space);
2477 if (!tree->guard)
2478 return isl_schedule_tree_free(tree);
2479 break;
2480 case isl_schedule_node_leaf:
2481 case isl_schedule_node_mark:
2482 case isl_schedule_node_sequence:
2483 case isl_schedule_node_set:
2484 isl_space_free(space);
2485 break;
2488 return tree;
2489 error:
2490 isl_space_free(space);
2491 isl_schedule_tree_free(tree);
2492 return NULL;
2495 /* Does "tree" involve the iteration domain?
2496 * That is, does it need to be modified
2497 * by isl_schedule_tree_pullback_union_pw_multi_aff?
2499 static int involves_iteration_domain(__isl_keep isl_schedule_tree *tree)
2501 if (!tree)
2502 return -1;
2504 switch (tree->type) {
2505 case isl_schedule_node_error:
2506 return -1;
2507 case isl_schedule_node_band:
2508 case isl_schedule_node_domain:
2509 case isl_schedule_node_expansion:
2510 case isl_schedule_node_extension:
2511 case isl_schedule_node_filter:
2512 return 1;
2513 case isl_schedule_node_context:
2514 case isl_schedule_node_leaf:
2515 case isl_schedule_node_guard:
2516 case isl_schedule_node_mark:
2517 case isl_schedule_node_sequence:
2518 case isl_schedule_node_set:
2519 return 0;
2522 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
2523 "unhandled case", return -1);
2526 /* Compute the pullback of the root node of "tree" by the function
2527 * represented by "upma".
2528 * In other words, plug in "upma" in the iteration domains of
2529 * the root node of "tree".
2530 * We currently do not handle expansion nodes.
2532 * We first check if the root node involves any iteration domains.
2533 * If so, we handle the specific cases.
2535 __isl_give isl_schedule_tree *isl_schedule_tree_pullback_union_pw_multi_aff(
2536 __isl_take isl_schedule_tree *tree,
2537 __isl_take isl_union_pw_multi_aff *upma)
2539 int involves;
2541 if (!tree || !upma)
2542 goto error;
2544 involves = involves_iteration_domain(tree);
2545 if (involves < 0)
2546 goto error;
2547 if (!involves) {
2548 isl_union_pw_multi_aff_free(upma);
2549 return tree;
2552 tree = isl_schedule_tree_cow(tree);
2553 if (!tree)
2554 goto error;
2556 if (tree->type == isl_schedule_node_band) {
2557 tree->band = isl_schedule_band_pullback_union_pw_multi_aff(
2558 tree->band, upma);
2559 if (!tree->band)
2560 return isl_schedule_tree_free(tree);
2561 } else if (tree->type == isl_schedule_node_domain) {
2562 tree->domain =
2563 isl_union_set_preimage_union_pw_multi_aff(tree->domain,
2564 upma);
2565 if (!tree->domain)
2566 return isl_schedule_tree_free(tree);
2567 } else if (tree->type == isl_schedule_node_expansion) {
2568 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_unsupported,
2569 "cannot pullback expansion node", goto error);
2570 } else if (tree->type == isl_schedule_node_extension) {
2571 tree->extension =
2572 isl_union_map_preimage_range_union_pw_multi_aff(
2573 tree->extension, upma);
2574 if (!tree->extension)
2575 return isl_schedule_tree_free(tree);
2576 } else if (tree->type == isl_schedule_node_filter) {
2577 tree->filter =
2578 isl_union_set_preimage_union_pw_multi_aff(tree->filter,
2579 upma);
2580 if (!tree->filter)
2581 return isl_schedule_tree_free(tree);
2584 return tree;
2585 error:
2586 isl_union_pw_multi_aff_free(upma);
2587 isl_schedule_tree_free(tree);
2588 return NULL;
2591 /* Compute the gist of the band tree root with respect to "context".
2593 __isl_give isl_schedule_tree *isl_schedule_tree_band_gist(
2594 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *context)
2596 if (!tree)
2597 return NULL;
2598 if (tree->type != isl_schedule_node_band)
2599 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2600 "not a band node", goto error);
2601 tree = isl_schedule_tree_cow(tree);
2602 if (!tree)
2603 goto error;
2605 tree->band = isl_schedule_band_gist(tree->band, context);
2606 if (!tree->band)
2607 return isl_schedule_tree_free(tree);
2608 return tree;
2609 error:
2610 isl_union_set_free(context);
2611 isl_schedule_tree_free(tree);
2612 return NULL;
2615 /* Are any members in "band" marked coincident?
2617 static int any_coincident(__isl_keep isl_schedule_band *band)
2619 int i, n;
2621 n = isl_schedule_band_n_member(band);
2622 for (i = 0; i < n; ++i)
2623 if (isl_schedule_band_member_get_coincident(band, i))
2624 return 1;
2626 return 0;
2629 /* Print the band node "band" to "p".
2631 * The permutable and coincident properties are only printed if they
2632 * are different from the defaults.
2633 * The coincident property is always printed in YAML flow style.
2635 static __isl_give isl_printer *print_tree_band(__isl_take isl_printer *p,
2636 __isl_keep isl_schedule_band *band)
2638 isl_union_set *options;
2639 int empty;
2641 p = isl_printer_print_str(p, "schedule");
2642 p = isl_printer_yaml_next(p);
2643 p = isl_printer_print_str(p, "\"");
2644 p = isl_printer_print_multi_union_pw_aff(p, band->mupa);
2645 p = isl_printer_print_str(p, "\"");
2646 if (isl_schedule_band_get_permutable(band)) {
2647 p = isl_printer_yaml_next(p);
2648 p = isl_printer_print_str(p, "permutable");
2649 p = isl_printer_yaml_next(p);
2650 p = isl_printer_print_int(p, 1);
2652 if (any_coincident(band)) {
2653 int i, n;
2654 int style;
2656 p = isl_printer_yaml_next(p);
2657 p = isl_printer_print_str(p, "coincident");
2658 p = isl_printer_yaml_next(p);
2659 style = isl_printer_get_yaml_style(p);
2660 p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_FLOW);
2661 p = isl_printer_yaml_start_sequence(p);
2662 n = isl_schedule_band_n_member(band);
2663 for (i = 0; i < n; ++i) {
2664 p = isl_printer_print_int(p,
2665 isl_schedule_band_member_get_coincident(band, i));
2666 p = isl_printer_yaml_next(p);
2668 p = isl_printer_yaml_end_sequence(p);
2669 p = isl_printer_set_yaml_style(p, style);
2671 options = isl_schedule_band_get_ast_build_options(band);
2672 empty = isl_union_set_is_empty(options);
2673 if (empty < 0)
2674 p = isl_printer_free(p);
2675 if (!empty) {
2676 p = isl_printer_yaml_next(p);
2677 p = isl_printer_print_str(p, "options");
2678 p = isl_printer_yaml_next(p);
2679 p = isl_printer_print_str(p, "\"");
2680 p = isl_printer_print_union_set(p, options);
2681 p = isl_printer_print_str(p, "\"");
2683 isl_union_set_free(options);
2685 return p;
2688 /* Print "tree" to "p".
2690 * If "n_ancestor" is non-negative, then "child_pos" contains the child
2691 * positions of a descendant of the current node that should be marked
2692 * (by the comment "YOU ARE HERE"). In particular, if "n_ancestor"
2693 * is zero, then the current node should be marked.
2694 * The marking is only printed in YAML block format.
2696 * Implicit leaf nodes are not printed, except if they correspond
2697 * to the node that should be marked.
2699 __isl_give isl_printer *isl_printer_print_schedule_tree_mark(
2700 __isl_take isl_printer *p, __isl_keep isl_schedule_tree *tree,
2701 int n_ancestor, int *child_pos)
2703 int i, n;
2704 int sequence = 0;
2705 int block;
2707 block = isl_printer_get_yaml_style(p) == ISL_YAML_STYLE_BLOCK;
2709 p = isl_printer_yaml_start_mapping(p);
2710 if (n_ancestor == 0 && block) {
2711 p = isl_printer_print_str(p, "# YOU ARE HERE");
2712 p = isl_printer_end_line(p);
2713 p = isl_printer_start_line(p);
2715 switch (tree->type) {
2716 case isl_schedule_node_error:
2717 p = isl_printer_print_str(p, "ERROR");
2718 break;
2719 case isl_schedule_node_leaf:
2720 p = isl_printer_print_str(p, "leaf");
2721 break;
2722 case isl_schedule_node_sequence:
2723 p = isl_printer_print_str(p, "sequence");
2724 sequence = 1;
2725 break;
2726 case isl_schedule_node_set:
2727 p = isl_printer_print_str(p, "set");
2728 sequence = 1;
2729 break;
2730 case isl_schedule_node_context:
2731 p = isl_printer_print_str(p, "context");
2732 p = isl_printer_yaml_next(p);
2733 p = isl_printer_print_str(p, "\"");
2734 p = isl_printer_print_set(p, tree->context);
2735 p = isl_printer_print_str(p, "\"");
2736 break;
2737 case isl_schedule_node_domain:
2738 p = isl_printer_print_str(p, "domain");
2739 p = isl_printer_yaml_next(p);
2740 p = isl_printer_print_str(p, "\"");
2741 p = isl_printer_print_union_set(p, tree->domain);
2742 p = isl_printer_print_str(p, "\"");
2743 break;
2744 case isl_schedule_node_expansion:
2745 p = isl_printer_print_str(p, "contraction");
2746 p = isl_printer_yaml_next(p);
2747 p = isl_printer_print_str(p, "\"");
2748 p = isl_printer_print_union_pw_multi_aff(p, tree->contraction);
2749 p = isl_printer_print_str(p, "\"");
2750 p = isl_printer_yaml_next(p);
2751 p = isl_printer_print_str(p, "expansion");
2752 p = isl_printer_yaml_next(p);
2753 p = isl_printer_print_str(p, "\"");
2754 p = isl_printer_print_union_map(p, tree->expansion);
2755 p = isl_printer_print_str(p, "\"");
2756 break;
2757 case isl_schedule_node_extension:
2758 p = isl_printer_print_str(p, "extension");
2759 p = isl_printer_yaml_next(p);
2760 p = isl_printer_print_str(p, "\"");
2761 p = isl_printer_print_union_map(p, tree->extension);
2762 p = isl_printer_print_str(p, "\"");
2763 break;
2764 case isl_schedule_node_filter:
2765 p = isl_printer_print_str(p, "filter");
2766 p = isl_printer_yaml_next(p);
2767 p = isl_printer_print_str(p, "\"");
2768 p = isl_printer_print_union_set(p, tree->filter);
2769 p = isl_printer_print_str(p, "\"");
2770 break;
2771 case isl_schedule_node_guard:
2772 p = isl_printer_print_str(p, "guard");
2773 p = isl_printer_yaml_next(p);
2774 p = isl_printer_print_str(p, "\"");
2775 p = isl_printer_print_set(p, tree->guard);
2776 p = isl_printer_print_str(p, "\"");
2777 break;
2778 case isl_schedule_node_mark:
2779 p = isl_printer_print_str(p, "mark");
2780 p = isl_printer_yaml_next(p);
2781 p = isl_printer_print_str(p, "\"");
2782 p = isl_printer_print_str(p, isl_id_get_name(tree->mark));
2783 p = isl_printer_print_str(p, "\"");
2784 break;
2785 case isl_schedule_node_band:
2786 p = print_tree_band(p, tree->band);
2787 break;
2789 p = isl_printer_yaml_next(p);
2791 if (!tree->children) {
2792 if (n_ancestor > 0 && block) {
2793 isl_schedule_tree *leaf;
2795 p = isl_printer_print_str(p, "child");
2796 p = isl_printer_yaml_next(p);
2797 leaf = isl_schedule_tree_leaf(isl_printer_get_ctx(p));
2798 p = isl_printer_print_schedule_tree_mark(p,
2799 leaf, 0, NULL);
2800 isl_schedule_tree_free(leaf);
2801 p = isl_printer_yaml_next(p);
2803 return isl_printer_yaml_end_mapping(p);
2806 if (sequence) {
2807 p = isl_printer_yaml_start_sequence(p);
2808 } else {
2809 p = isl_printer_print_str(p, "child");
2810 p = isl_printer_yaml_next(p);
2813 n = isl_schedule_tree_list_n_schedule_tree(tree->children);
2814 for (i = 0; i < n; ++i) {
2815 isl_schedule_tree *t;
2817 t = isl_schedule_tree_get_child(tree, i);
2818 if (n_ancestor > 0 && child_pos[0] == i)
2819 p = isl_printer_print_schedule_tree_mark(p, t,
2820 n_ancestor - 1, child_pos + 1);
2821 else
2822 p = isl_printer_print_schedule_tree_mark(p, t,
2823 -1, NULL);
2824 isl_schedule_tree_free(t);
2826 p = isl_printer_yaml_next(p);
2829 if (sequence)
2830 p = isl_printer_yaml_end_sequence(p);
2831 p = isl_printer_yaml_end_mapping(p);
2833 return p;
2836 /* Print "tree" to "p".
2838 __isl_give isl_printer *isl_printer_print_schedule_tree(
2839 __isl_take isl_printer *p, __isl_keep isl_schedule_tree *tree)
2841 return isl_printer_print_schedule_tree_mark(p, tree, -1, NULL);
2844 void isl_schedule_tree_dump(__isl_keep isl_schedule_tree *tree)
2846 isl_ctx *ctx;
2847 isl_printer *printer;
2849 if (!tree)
2850 return;
2852 ctx = isl_schedule_tree_get_ctx(tree);
2853 printer = isl_printer_to_file(ctx, stderr);
2854 printer = isl_printer_set_yaml_style(printer, ISL_YAML_STYLE_BLOCK);
2855 printer = isl_printer_print_schedule_tree(printer, tree);
2857 isl_printer_free(printer);