isl_output.c: print_disjunct: use names from space argument
[isl.git] / isl_schedule_tree.c
blob7b83f005d146dcb04c65ba590768bf7fab07aad3
1 /*
2 * Copyright 2013-2014 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/map.h>
14 #include <isl_schedule_band.h>
15 #include <isl_schedule_private.h>
17 #undef EL
18 #define EL isl_schedule_tree
20 #include <isl_list_templ.h>
22 #undef BASE
23 #define BASE schedule_tree
25 #include <isl_list_templ.c>
27 /* Is "tree" the leaf of a schedule tree?
29 int isl_schedule_tree_is_leaf(__isl_keep isl_schedule_tree *tree)
31 return isl_schedule_tree_get_type(tree) == isl_schedule_node_leaf;
34 /* Create a new schedule tree of type "type".
35 * The caller is responsible for filling in the type specific fields and
36 * the children.
38 * By default, the single node tree does not have any anchored nodes.
39 * The caller is responsible for updating the anchored field if needed.
41 static __isl_give isl_schedule_tree *isl_schedule_tree_alloc(isl_ctx *ctx,
42 enum isl_schedule_node_type type)
44 isl_schedule_tree *tree;
46 if (type == isl_schedule_node_error)
47 return NULL;
49 tree = isl_calloc_type(ctx, isl_schedule_tree);
50 if (!tree)
51 return NULL;
53 tree->ref = 1;
54 tree->ctx = ctx;
55 isl_ctx_ref(ctx);
56 tree->type = type;
57 tree->anchored = 0;
59 return tree;
62 /* Return a fresh copy of "tree".
64 __isl_take isl_schedule_tree *isl_schedule_tree_dup(
65 __isl_keep isl_schedule_tree *tree)
67 isl_ctx *ctx;
68 isl_schedule_tree *dup;
70 if (!tree)
71 return NULL;
73 ctx = isl_schedule_tree_get_ctx(tree);
74 dup = isl_schedule_tree_alloc(ctx, tree->type);
75 if (!dup)
76 return NULL;
78 switch (tree->type) {
79 case isl_schedule_node_error:
80 isl_die(ctx, isl_error_internal,
81 "allocation should have failed",
82 isl_schedule_tree_free(dup));
83 case isl_schedule_node_band:
84 dup->band = isl_schedule_band_copy(tree->band);
85 if (!dup->band)
86 return isl_schedule_tree_free(dup);
87 break;
88 case isl_schedule_node_context:
89 dup->context = isl_set_copy(tree->context);
90 if (!dup->context)
91 return isl_schedule_tree_free(dup);
92 break;
93 case isl_schedule_node_domain:
94 dup->domain = isl_union_set_copy(tree->domain);
95 if (!dup->domain)
96 return isl_schedule_tree_free(dup);
97 break;
98 case isl_schedule_node_expansion:
99 dup->contraction =
100 isl_union_pw_multi_aff_copy(tree->contraction);
101 dup->expansion = isl_union_map_copy(tree->expansion);
102 if (!dup->contraction || !dup->expansion)
103 return isl_schedule_tree_free(dup);
104 break;
105 case isl_schedule_node_extension:
106 dup->extension = isl_union_map_copy(tree->extension);
107 if (!dup->extension)
108 return isl_schedule_tree_free(dup);
109 break;
110 case isl_schedule_node_filter:
111 dup->filter = isl_union_set_copy(tree->filter);
112 if (!dup->filter)
113 return isl_schedule_tree_free(dup);
114 break;
115 case isl_schedule_node_guard:
116 dup->guard = isl_set_copy(tree->guard);
117 if (!dup->guard)
118 return isl_schedule_tree_free(dup);
119 break;
120 case isl_schedule_node_mark:
121 dup->mark = isl_id_copy(tree->mark);
122 if (!dup->mark)
123 return isl_schedule_tree_free(dup);
124 break;
125 case isl_schedule_node_leaf:
126 case isl_schedule_node_sequence:
127 case isl_schedule_node_set:
128 break;
131 if (tree->children) {
132 dup->children = isl_schedule_tree_list_copy(tree->children);
133 if (!dup->children)
134 return isl_schedule_tree_free(dup);
136 dup->anchored = tree->anchored;
138 return dup;
141 /* Return an isl_schedule_tree that is equal to "tree" and that has only
142 * a single reference.
144 * This function is called before a tree is modified.
145 * A static tree (with negative reference count) should never be modified,
146 * so it is not allowed to call this function on a static tree.
148 __isl_give isl_schedule_tree *isl_schedule_tree_cow(
149 __isl_take isl_schedule_tree *tree)
151 if (!tree)
152 return NULL;
154 if (tree->ref < 0)
155 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
156 "static trees cannot be modified",
157 return isl_schedule_tree_free(tree));
159 if (tree->ref == 1)
160 return tree;
161 tree->ref--;
162 return isl_schedule_tree_dup(tree);
165 /* Return a new reference to "tree".
167 * A static tree (with negative reference count) does not keep track
168 * of the number of references and should not be modified.
170 __isl_give isl_schedule_tree *isl_schedule_tree_copy(
171 __isl_keep isl_schedule_tree *tree)
173 if (!tree)
174 return NULL;
176 if (tree->ref < 0)
177 return tree;
179 tree->ref++;
180 return tree;
183 /* Free "tree" and return NULL.
185 __isl_null isl_schedule_tree *isl_schedule_tree_free(
186 __isl_take isl_schedule_tree *tree)
188 if (!tree)
189 return NULL;
190 if (tree->ref < 0)
191 return NULL;
192 if (--tree->ref > 0)
193 return NULL;
195 switch (tree->type) {
196 case isl_schedule_node_band:
197 isl_schedule_band_free(tree->band);
198 break;
199 case isl_schedule_node_context:
200 isl_set_free(tree->context);
201 break;
202 case isl_schedule_node_domain:
203 isl_union_set_free(tree->domain);
204 break;
205 case isl_schedule_node_expansion:
206 isl_union_pw_multi_aff_free(tree->contraction);
207 isl_union_map_free(tree->expansion);
208 break;
209 case isl_schedule_node_extension:
210 isl_union_map_free(tree->extension);
211 break;
212 case isl_schedule_node_filter:
213 isl_union_set_free(tree->filter);
214 break;
215 case isl_schedule_node_guard:
216 isl_set_free(tree->guard);
217 break;
218 case isl_schedule_node_mark:
219 isl_id_free(tree->mark);
220 break;
221 case isl_schedule_node_sequence:
222 case isl_schedule_node_set:
223 case isl_schedule_node_error:
224 case isl_schedule_node_leaf:
225 break;
227 isl_schedule_tree_list_free(tree->children);
228 isl_ctx_deref(tree->ctx);
229 free(tree);
231 return NULL;
234 /* Create and return a new leaf schedule tree.
236 __isl_give isl_schedule_tree *isl_schedule_tree_leaf(isl_ctx *ctx)
238 return isl_schedule_tree_alloc(ctx, isl_schedule_node_leaf);
241 /* Create a new band schedule tree referring to "band"
242 * with no children.
244 __isl_give isl_schedule_tree *isl_schedule_tree_from_band(
245 __isl_take isl_schedule_band *band)
247 isl_ctx *ctx;
248 isl_schedule_tree *tree;
250 if (!band)
251 return NULL;
253 ctx = isl_schedule_band_get_ctx(band);
254 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_band);
255 if (!tree)
256 goto error;
258 tree->band = band;
259 tree->anchored = isl_schedule_band_is_anchored(band);
261 return tree;
262 error:
263 isl_schedule_band_free(band);
264 return NULL;
267 /* Create a new context schedule tree with the given context and no children.
268 * Since the context references the outer schedule dimension,
269 * the tree is anchored.
271 __isl_give isl_schedule_tree *isl_schedule_tree_from_context(
272 __isl_take isl_set *context)
274 isl_ctx *ctx;
275 isl_schedule_tree *tree;
277 if (!context)
278 return NULL;
280 ctx = isl_set_get_ctx(context);
281 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_context);
282 if (!tree)
283 goto error;
285 tree->context = context;
286 tree->anchored = 1;
288 return tree;
289 error:
290 isl_set_free(context);
291 return NULL;
294 /* Create a new domain schedule tree with the given domain and no children.
296 __isl_give isl_schedule_tree *isl_schedule_tree_from_domain(
297 __isl_take isl_union_set *domain)
299 isl_ctx *ctx;
300 isl_schedule_tree *tree;
302 if (!domain)
303 return NULL;
305 ctx = isl_union_set_get_ctx(domain);
306 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_domain);
307 if (!tree)
308 goto error;
310 tree->domain = domain;
312 return tree;
313 error:
314 isl_union_set_free(domain);
315 return NULL;
318 /* Create a new expansion schedule tree with the given contraction and
319 * expansion and no children.
321 __isl_give isl_schedule_tree *isl_schedule_tree_from_expansion(
322 __isl_take isl_union_pw_multi_aff *contraction,
323 __isl_take isl_union_map *expansion)
325 isl_ctx *ctx;
326 isl_schedule_tree *tree;
328 if (!contraction || !expansion)
329 goto error;
331 ctx = isl_union_map_get_ctx(expansion);
332 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_expansion);
333 if (!tree)
334 goto error;
336 tree->contraction = contraction;
337 tree->expansion = expansion;
339 return tree;
340 error:
341 isl_union_pw_multi_aff_free(contraction);
342 isl_union_map_free(expansion);
343 return NULL;
346 /* Create a new extension schedule tree with the given extension and
347 * no children.
348 * Since the domain of the extension refers to the outer schedule dimension,
349 * the tree is anchored.
351 __isl_give isl_schedule_tree *isl_schedule_tree_from_extension(
352 __isl_take isl_union_map *extension)
354 isl_ctx *ctx;
355 isl_schedule_tree *tree;
357 if (!extension)
358 return NULL;
360 ctx = isl_union_map_get_ctx(extension);
361 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_extension);
362 if (!tree)
363 goto error;
365 tree->extension = extension;
366 tree->anchored = 1;
368 return tree;
369 error:
370 isl_union_map_free(extension);
371 return NULL;
374 /* Create a new filter schedule tree with the given filter and no children.
376 __isl_give isl_schedule_tree *isl_schedule_tree_from_filter(
377 __isl_take isl_union_set *filter)
379 isl_ctx *ctx;
380 isl_schedule_tree *tree;
382 if (!filter)
383 return NULL;
385 ctx = isl_union_set_get_ctx(filter);
386 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_filter);
387 if (!tree)
388 goto error;
390 tree->filter = filter;
392 return tree;
393 error:
394 isl_union_set_free(filter);
395 return NULL;
398 /* Create a new guard schedule tree with the given guard and no children.
399 * Since the guard references the outer schedule dimension,
400 * the tree is anchored.
402 __isl_give isl_schedule_tree *isl_schedule_tree_from_guard(
403 __isl_take isl_set *guard)
405 isl_ctx *ctx;
406 isl_schedule_tree *tree;
408 if (!guard)
409 return NULL;
411 ctx = isl_set_get_ctx(guard);
412 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_guard);
413 if (!tree)
414 goto error;
416 tree->guard = guard;
417 tree->anchored = 1;
419 return tree;
420 error:
421 isl_set_free(guard);
422 return NULL;
425 /* Create a new mark schedule tree with the given mark identifier and
426 * no children.
428 __isl_give isl_schedule_tree *isl_schedule_tree_from_mark(
429 __isl_take isl_id *mark)
431 isl_ctx *ctx;
432 isl_schedule_tree *tree;
434 if (!mark)
435 return NULL;
437 ctx = isl_id_get_ctx(mark);
438 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_mark);
439 if (!tree)
440 goto error;
442 tree->mark = mark;
444 return tree;
445 error:
446 isl_id_free(mark);
447 return NULL;
450 /* Does "tree" have any node that depends on its position
451 * in the complete schedule tree?
453 isl_bool isl_schedule_tree_is_subtree_anchored(
454 __isl_keep isl_schedule_tree *tree)
456 return tree ? tree->anchored : isl_bool_error;
459 /* Does the root node of "tree" depend on its position in the complete
460 * schedule tree?
461 * Band nodes may be anchored depending on the associated AST build options.
462 * Context, extension and guard nodes are always anchored.
464 int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree *tree)
466 if (!tree)
467 return -1;
469 switch (isl_schedule_tree_get_type(tree)) {
470 case isl_schedule_node_error:
471 return -1;
472 case isl_schedule_node_band:
473 return isl_schedule_band_is_anchored(tree->band);
474 case isl_schedule_node_context:
475 case isl_schedule_node_extension:
476 case isl_schedule_node_guard:
477 return 1;
478 case isl_schedule_node_domain:
479 case isl_schedule_node_expansion:
480 case isl_schedule_node_filter:
481 case isl_schedule_node_leaf:
482 case isl_schedule_node_mark:
483 case isl_schedule_node_sequence:
484 case isl_schedule_node_set:
485 return 0;
488 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
489 "unhandled case", return -1);
492 /* Update the anchored field of "tree" based on whether the root node
493 * itself in anchored and the anchored fields of the children.
495 * This function should be called whenever the children of a tree node
496 * are changed or the anchoredness of the tree root itself changes.
498 __isl_give isl_schedule_tree *isl_schedule_tree_update_anchored(
499 __isl_take isl_schedule_tree *tree)
501 int i, n;
502 int anchored;
504 if (!tree)
505 return NULL;
507 anchored = isl_schedule_tree_is_anchored(tree);
508 if (anchored < 0)
509 return isl_schedule_tree_free(tree);
511 n = isl_schedule_tree_list_n_schedule_tree(tree->children);
512 for (i = 0; !anchored && i < n; ++i) {
513 isl_schedule_tree *child;
515 child = isl_schedule_tree_get_child(tree, i);
516 if (!child)
517 return isl_schedule_tree_free(tree);
518 anchored = child->anchored;
519 isl_schedule_tree_free(child);
522 if (anchored == tree->anchored)
523 return tree;
524 tree = isl_schedule_tree_cow(tree);
525 if (!tree)
526 return NULL;
527 tree->anchored = anchored;
528 return tree;
531 /* Create a new tree of the given type (isl_schedule_node_sequence or
532 * isl_schedule_node_set) with the given children.
534 __isl_give isl_schedule_tree *isl_schedule_tree_from_children(
535 enum isl_schedule_node_type type,
536 __isl_take isl_schedule_tree_list *list)
538 isl_ctx *ctx;
539 isl_schedule_tree *tree;
541 if (!list)
542 return NULL;
544 ctx = isl_schedule_tree_list_get_ctx(list);
545 tree = isl_schedule_tree_alloc(ctx, type);
546 if (!tree)
547 goto error;
549 tree->children = list;
550 tree = isl_schedule_tree_update_anchored(tree);
552 return tree;
553 error:
554 isl_schedule_tree_list_free(list);
555 return NULL;
558 /* Construct a tree with a root node of type "type" and as children
559 * "tree1" and "tree2".
560 * If the root of one (or both) of the input trees is itself of type "type",
561 * then the tree is replaced by its children.
563 __isl_give isl_schedule_tree *isl_schedule_tree_from_pair(
564 enum isl_schedule_node_type type, __isl_take isl_schedule_tree *tree1,
565 __isl_take isl_schedule_tree *tree2)
567 isl_ctx *ctx;
568 isl_schedule_tree_list *list;
570 if (!tree1 || !tree2)
571 goto error;
573 ctx = isl_schedule_tree_get_ctx(tree1);
574 if (isl_schedule_tree_get_type(tree1) == type) {
575 list = isl_schedule_tree_list_copy(tree1->children);
576 isl_schedule_tree_free(tree1);
577 } else {
578 list = isl_schedule_tree_list_alloc(ctx, 2);
579 list = isl_schedule_tree_list_add(list, tree1);
581 if (isl_schedule_tree_get_type(tree2) == type) {
582 isl_schedule_tree_list *children;
584 children = isl_schedule_tree_list_copy(tree2->children);
585 list = isl_schedule_tree_list_concat(list, children);
586 isl_schedule_tree_free(tree2);
587 } else {
588 list = isl_schedule_tree_list_add(list, tree2);
591 return isl_schedule_tree_from_children(type, list);
592 error:
593 isl_schedule_tree_free(tree1);
594 isl_schedule_tree_free(tree2);
595 return NULL;
598 /* Construct a tree with a sequence root node and as children
599 * "tree1" and "tree2".
600 * If the root of one (or both) of the input trees is itself a sequence,
601 * then the tree is replaced by its children.
603 __isl_give isl_schedule_tree *isl_schedule_tree_sequence_pair(
604 __isl_take isl_schedule_tree *tree1,
605 __isl_take isl_schedule_tree *tree2)
607 return isl_schedule_tree_from_pair(isl_schedule_node_sequence,
608 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 context of the context tree root.
1294 __isl_give isl_set *isl_schedule_tree_context_get_context(
1295 __isl_keep isl_schedule_tree *tree)
1297 if (!tree)
1298 return NULL;
1300 if (tree->type != isl_schedule_node_context)
1301 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1302 "not a context node", return NULL);
1304 return isl_set_copy(tree->context);
1307 /* Return the domain of the domain tree root.
1309 __isl_give isl_union_set *isl_schedule_tree_domain_get_domain(
1310 __isl_keep isl_schedule_tree *tree)
1312 if (!tree)
1313 return NULL;
1315 if (tree->type != isl_schedule_node_domain)
1316 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1317 "not a domain node", return NULL);
1319 return isl_union_set_copy(tree->domain);
1322 /* Replace the domain of domain tree root "tree" by "domain".
1324 __isl_give isl_schedule_tree *isl_schedule_tree_domain_set_domain(
1325 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
1327 tree = isl_schedule_tree_cow(tree);
1328 if (!tree || !domain)
1329 goto error;
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", goto error);
1335 isl_union_set_free(tree->domain);
1336 tree->domain = domain;
1338 return tree;
1339 error:
1340 isl_schedule_tree_free(tree);
1341 isl_union_set_free(domain);
1342 return NULL;
1345 /* Return the contraction of the expansion tree root.
1347 __isl_give isl_union_pw_multi_aff *isl_schedule_tree_expansion_get_contraction(
1348 __isl_keep isl_schedule_tree *tree)
1350 if (!tree)
1351 return NULL;
1353 if (tree->type != isl_schedule_node_expansion)
1354 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1355 "not an expansion node", return NULL);
1357 return isl_union_pw_multi_aff_copy(tree->contraction);
1360 /* Return the expansion of the expansion tree root.
1362 __isl_give isl_union_map *isl_schedule_tree_expansion_get_expansion(
1363 __isl_keep isl_schedule_tree *tree)
1365 if (!tree)
1366 return NULL;
1368 if (tree->type != isl_schedule_node_expansion)
1369 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1370 "not an expansion node", return NULL);
1372 return isl_union_map_copy(tree->expansion);
1375 /* Replace the contraction and the expansion of the expansion tree root "tree"
1376 * by "contraction" and "expansion".
1378 __isl_give isl_schedule_tree *
1379 isl_schedule_tree_expansion_set_contraction_and_expansion(
1380 __isl_take isl_schedule_tree *tree,
1381 __isl_take isl_union_pw_multi_aff *contraction,
1382 __isl_take isl_union_map *expansion)
1384 tree = isl_schedule_tree_cow(tree);
1385 if (!tree || !contraction || !expansion)
1386 goto error;
1388 if (tree->type != isl_schedule_node_expansion)
1389 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1390 "not an expansion node", return NULL);
1392 isl_union_pw_multi_aff_free(tree->contraction);
1393 tree->contraction = contraction;
1394 isl_union_map_free(tree->expansion);
1395 tree->expansion = expansion;
1397 return tree;
1398 error:
1399 isl_schedule_tree_free(tree);
1400 isl_union_pw_multi_aff_free(contraction);
1401 isl_union_map_free(expansion);
1402 return NULL;
1405 /* Return the extension of the extension tree root.
1407 __isl_give isl_union_map *isl_schedule_tree_extension_get_extension(
1408 __isl_take isl_schedule_tree *tree)
1410 if (!tree)
1411 return NULL;
1413 if (tree->type != isl_schedule_node_extension)
1414 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1415 "not an extension node", return NULL);
1417 return isl_union_map_copy(tree->extension);
1420 /* Replace the extension of extension tree root "tree" by "extension".
1422 __isl_give isl_schedule_tree *isl_schedule_tree_extension_set_extension(
1423 __isl_take isl_schedule_tree *tree, __isl_take isl_union_map *extension)
1425 tree = isl_schedule_tree_cow(tree);
1426 if (!tree || !extension)
1427 goto error;
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);
1432 isl_union_map_free(tree->extension);
1433 tree->extension = extension;
1435 return tree;
1436 error:
1437 isl_schedule_tree_free(tree);
1438 isl_union_map_free(extension);
1439 return NULL;
1442 /* Return the filter of the filter tree root.
1444 __isl_give isl_union_set *isl_schedule_tree_filter_get_filter(
1445 __isl_keep isl_schedule_tree *tree)
1447 if (!tree)
1448 return NULL;
1450 if (tree->type != isl_schedule_node_filter)
1451 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1452 "not a filter node", return NULL);
1454 return isl_union_set_copy(tree->filter);
1457 /* Replace the filter of the filter tree root by "filter".
1459 __isl_give isl_schedule_tree *isl_schedule_tree_filter_set_filter(
1460 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
1462 tree = isl_schedule_tree_cow(tree);
1463 if (!tree || !filter)
1464 goto error;
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 isl_union_set_free(tree->filter);
1471 tree->filter = filter;
1473 return tree;
1474 error:
1475 isl_schedule_tree_free(tree);
1476 isl_union_set_free(filter);
1477 return NULL;
1480 /* Return the guard of the guard tree root.
1482 __isl_give isl_set *isl_schedule_tree_guard_get_guard(
1483 __isl_take isl_schedule_tree *tree)
1485 if (!tree)
1486 return NULL;
1488 if (tree->type != isl_schedule_node_guard)
1489 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1490 "not a guard node", return NULL);
1492 return isl_set_copy(tree->guard);
1495 /* Return the mark identifier of the mark tree root "tree".
1497 __isl_give isl_id *isl_schedule_tree_mark_get_id(
1498 __isl_keep isl_schedule_tree *tree)
1500 if (!tree)
1501 return NULL;
1503 if (tree->type != isl_schedule_node_mark)
1504 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1505 "not a mark node", return NULL);
1507 return isl_id_copy(tree->mark);
1510 /* Set dim to the range dimension of "map" and abort the search.
1512 static isl_stat set_range_dim(__isl_take isl_map *map, void *user)
1514 int *dim = user;
1516 *dim = isl_map_dim(map, isl_dim_out);
1517 isl_map_free(map);
1519 return isl_stat_error;
1522 /* Return the dimension of the range of "umap".
1523 * "umap" is assumed not to be empty and
1524 * all maps inside "umap" are assumed to have the same range.
1526 * We extract the range dimension from the first map in "umap".
1528 static int range_dim(__isl_keep isl_union_map *umap)
1530 int dim = -1;
1532 if (!umap)
1533 return -1;
1534 if (isl_union_map_n_map(umap) == 0)
1535 isl_die(isl_union_map_get_ctx(umap), isl_error_internal,
1536 "unexpected empty input", return -1);
1538 isl_union_map_foreach_map(umap, &set_range_dim, &dim);
1540 return dim;
1543 /* Append an "extra" number of zeros to the range of "umap" and
1544 * return the result.
1546 static __isl_give isl_union_map *append_range(__isl_take isl_union_map *umap,
1547 int extra)
1549 isl_union_set *dom;
1550 isl_space *space;
1551 isl_multi_val *mv;
1552 isl_union_pw_multi_aff *suffix;
1553 isl_union_map *universe;
1554 isl_union_map *suffix_umap;
1556 universe = isl_union_map_universe(isl_union_map_copy(umap));
1557 dom = isl_union_map_domain(universe);
1558 space = isl_union_set_get_space(dom);
1559 space = isl_space_set_from_params(space);
1560 space = isl_space_add_dims(space, isl_dim_set, extra);
1561 mv = isl_multi_val_zero(space);
1563 suffix = isl_union_pw_multi_aff_multi_val_on_domain(dom, mv);
1564 suffix_umap = isl_union_map_from_union_pw_multi_aff(suffix);
1565 umap = isl_union_map_flat_range_product(umap, suffix_umap);
1567 return umap;
1570 /* Should we skip the root of "tree" while looking for the first
1571 * descendant with schedule information?
1572 * That is, is it impossible to derive any information about
1573 * the iteration domain from this node?
1575 * We do not want to skip leaf or error nodes because there is
1576 * no point in looking any deeper from these nodes.
1577 * We can only extract partial iteration domain information
1578 * from an extension node, but extension nodes are not supported
1579 * by the caller and it will error out on them.
1581 static int domain_less(__isl_keep isl_schedule_tree *tree)
1583 enum isl_schedule_node_type type;
1585 type = isl_schedule_tree_get_type(tree);
1586 switch (type) {
1587 case isl_schedule_node_band:
1588 return isl_schedule_tree_band_n_member(tree) == 0;
1589 case isl_schedule_node_context:
1590 case isl_schedule_node_guard:
1591 case isl_schedule_node_mark:
1592 return 1;
1593 case isl_schedule_node_leaf:
1594 case isl_schedule_node_error:
1595 case isl_schedule_node_domain:
1596 case isl_schedule_node_expansion:
1597 case isl_schedule_node_extension:
1598 case isl_schedule_node_filter:
1599 case isl_schedule_node_set:
1600 case isl_schedule_node_sequence:
1601 return 0;
1604 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1605 "unhandled case", return 0);
1608 /* Move down to the first descendant of "tree" that contains any schedule
1609 * information or return "leaf" if there is no such descendant.
1611 __isl_give isl_schedule_tree *isl_schedule_tree_first_schedule_descendant(
1612 __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_tree *leaf)
1614 while (domain_less(tree)) {
1615 if (!isl_schedule_tree_has_children(tree)) {
1616 isl_schedule_tree_free(tree);
1617 return isl_schedule_tree_copy(leaf);
1619 tree = isl_schedule_tree_child(tree, 0);
1622 return tree;
1625 static __isl_give isl_union_map *subtree_schedule_extend(
1626 __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer);
1628 /* Extend the schedule map "outer" with the subtree schedule
1629 * of the (single) child of "tree", if any.
1631 * If "tree" does not have any descendants (apart from those that
1632 * do not carry any schedule information), then we simply return "outer".
1633 * Otherwise, we extend the schedule map "outer" with the subtree schedule
1634 * of the single child.
1636 static __isl_give isl_union_map *subtree_schedule_extend_child(
1637 __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1639 isl_schedule_tree *child;
1640 isl_union_map *res;
1642 if (!tree)
1643 return isl_union_map_free(outer);
1644 if (!isl_schedule_tree_has_children(tree))
1645 return outer;
1646 child = isl_schedule_tree_get_child(tree, 0);
1647 if (!child)
1648 return isl_union_map_free(outer);
1649 res = subtree_schedule_extend(child, outer);
1650 isl_schedule_tree_free(child);
1651 return res;
1654 /* Extract the parameter space from one of the children of "tree",
1655 * which are assumed to be filters.
1657 static __isl_give isl_space *extract_space_from_filter_child(
1658 __isl_keep isl_schedule_tree *tree)
1660 isl_space *space;
1661 isl_union_set *dom;
1662 isl_schedule_tree *child;
1664 child = isl_schedule_tree_list_get_schedule_tree(tree->children, 0);
1665 dom = isl_schedule_tree_filter_get_filter(child);
1666 space = isl_union_set_get_space(dom);
1667 isl_union_set_free(dom);
1668 isl_schedule_tree_free(child);
1670 return space;
1673 /* Extend the schedule map "outer" with the subtree schedule
1674 * of a set or sequence node.
1676 * The schedule for the set or sequence node itself is composed of
1677 * pieces of the form
1679 * filter -> []
1681 * or
1683 * filter -> [index]
1685 * The first form is used if there is only a single child or
1686 * if the current node is a set node and the schedule_separate_components
1687 * option is not set.
1689 * Each of the pieces above is extended with the subtree schedule of
1690 * the child of the corresponding filter, if any, padded with zeros
1691 * to ensure that all pieces have the same range dimension.
1693 static __isl_give isl_union_map *subtree_schedule_extend_from_children(
1694 __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1696 int i, n;
1697 int dim;
1698 int separate;
1699 isl_ctx *ctx;
1700 isl_val *v = NULL;
1701 isl_multi_val *mv;
1702 isl_space *space;
1703 isl_union_map *umap;
1705 if (!tree)
1706 return NULL;
1708 ctx = isl_schedule_tree_get_ctx(tree);
1709 if (!tree->children)
1710 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1711 "missing children", return NULL);
1712 n = isl_schedule_tree_list_n_schedule_tree(tree->children);
1713 if (n == 0)
1714 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1715 "missing children", return NULL);
1717 separate = n > 1 && (tree->type == isl_schedule_node_sequence ||
1718 isl_options_get_schedule_separate_components(ctx));
1720 space = extract_space_from_filter_child(tree);
1722 umap = isl_union_map_empty(isl_space_copy(space));
1723 space = isl_space_set_from_params(space);
1724 if (separate) {
1725 space = isl_space_add_dims(space, isl_dim_set, 1);
1726 v = isl_val_zero(ctx);
1728 mv = isl_multi_val_zero(space);
1730 dim = isl_multi_val_dim(mv, isl_dim_set);
1731 for (i = 0; i < n; ++i) {
1732 isl_union_pw_multi_aff *upma;
1733 isl_union_map *umap_i;
1734 isl_union_set *dom;
1735 isl_schedule_tree *child;
1736 int dim_i;
1737 int empty;
1739 child = isl_schedule_tree_list_get_schedule_tree(
1740 tree->children, i);
1741 dom = isl_schedule_tree_filter_get_filter(child);
1743 if (separate) {
1744 mv = isl_multi_val_set_val(mv, 0, isl_val_copy(v));
1745 v = isl_val_add_ui(v, 1);
1747 upma = isl_union_pw_multi_aff_multi_val_on_domain(dom,
1748 isl_multi_val_copy(mv));
1749 umap_i = isl_union_map_from_union_pw_multi_aff(upma);
1750 umap_i = isl_union_map_flat_range_product(
1751 isl_union_map_copy(outer), umap_i);
1752 umap_i = subtree_schedule_extend_child(child, umap_i);
1753 isl_schedule_tree_free(child);
1755 empty = isl_union_map_is_empty(umap_i);
1756 if (empty < 0)
1757 umap_i = isl_union_map_free(umap_i);
1758 else if (empty) {
1759 isl_union_map_free(umap_i);
1760 continue;
1763 dim_i = range_dim(umap_i);
1764 if (dim_i < 0) {
1765 umap = isl_union_map_free(umap);
1766 } else if (dim < dim_i) {
1767 umap = append_range(umap, dim_i - dim);
1768 dim = dim_i;
1769 } else if (dim_i < dim) {
1770 umap_i = append_range(umap_i, dim - dim_i);
1772 umap = isl_union_map_union(umap, umap_i);
1775 isl_val_free(v);
1776 isl_multi_val_free(mv);
1777 isl_union_map_free(outer);
1779 return umap;
1782 /* Extend the schedule map "outer" with the subtree schedule of "tree".
1784 * If the root of the tree is a set or a sequence, then we extend
1785 * the schedule map in subtree_schedule_extend_from_children.
1786 * Otherwise, we extend the schedule map with the partial schedule
1787 * corresponding to the root of the tree and then continue with
1788 * the single child of this root.
1789 * In the special case of an expansion, the schedule map is "extended"
1790 * by applying the expansion to the domain of the schedule map.
1792 static __isl_give isl_union_map *subtree_schedule_extend(
1793 __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1795 isl_multi_union_pw_aff *mupa;
1796 isl_union_map *umap;
1797 isl_union_set *domain;
1799 if (!tree)
1800 return NULL;
1802 switch (tree->type) {
1803 case isl_schedule_node_error:
1804 return isl_union_map_free(outer);
1805 case isl_schedule_node_extension:
1806 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1807 "cannot construct subtree schedule of tree "
1808 "with extension nodes",
1809 return isl_union_map_free(outer));
1810 case isl_schedule_node_context:
1811 case isl_schedule_node_guard:
1812 case isl_schedule_node_mark:
1813 return subtree_schedule_extend_child(tree, outer);
1814 case isl_schedule_node_band:
1815 if (isl_schedule_tree_band_n_member(tree) == 0)
1816 return subtree_schedule_extend_child(tree, outer);
1817 mupa = isl_schedule_band_get_partial_schedule(tree->band);
1818 umap = isl_union_map_from_multi_union_pw_aff(mupa);
1819 outer = isl_union_map_flat_range_product(outer, umap);
1820 umap = subtree_schedule_extend_child(tree, outer);
1821 break;
1822 case isl_schedule_node_domain:
1823 domain = isl_schedule_tree_domain_get_domain(tree);
1824 umap = isl_union_map_from_domain(domain);
1825 outer = isl_union_map_flat_range_product(outer, umap);
1826 umap = subtree_schedule_extend_child(tree, outer);
1827 break;
1828 case isl_schedule_node_expansion:
1829 umap = isl_schedule_tree_expansion_get_expansion(tree);
1830 outer = isl_union_map_apply_domain(outer, umap);
1831 umap = subtree_schedule_extend_child(tree, outer);
1832 break;
1833 case isl_schedule_node_filter:
1834 domain = isl_schedule_tree_filter_get_filter(tree);
1835 umap = isl_union_map_from_domain(domain);
1836 outer = isl_union_map_flat_range_product(outer, umap);
1837 umap = subtree_schedule_extend_child(tree, outer);
1838 break;
1839 case isl_schedule_node_leaf:
1840 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1841 "leaf node should be handled by caller", return NULL);
1842 case isl_schedule_node_set:
1843 case isl_schedule_node_sequence:
1844 umap = subtree_schedule_extend_from_children(tree, outer);
1845 break;
1848 return umap;
1851 static __isl_give isl_union_set *initial_domain(
1852 __isl_keep isl_schedule_tree *tree);
1854 /* Extract a universe domain from the children of the tree root "tree",
1855 * which is a set or sequence, meaning that its children are filters.
1856 * In particular, return the union of the universes of the filters.
1858 static __isl_give isl_union_set *initial_domain_from_children(
1859 __isl_keep isl_schedule_tree *tree)
1861 int i, n;
1862 isl_space *space;
1863 isl_union_set *domain;
1865 if (!tree->children)
1866 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1867 "missing children", return NULL);
1868 n = isl_schedule_tree_list_n_schedule_tree(tree->children);
1869 if (n == 0)
1870 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1871 "missing children", return NULL);
1873 space = extract_space_from_filter_child(tree);
1874 domain = isl_union_set_empty(space);
1876 for (i = 0; i < n; ++i) {
1877 isl_schedule_tree *child;
1878 isl_union_set *domain_i;
1880 child = isl_schedule_tree_get_child(tree, i);
1881 domain_i = initial_domain(child);
1882 domain = isl_union_set_union(domain, domain_i);
1883 isl_schedule_tree_free(child);
1886 return domain;
1889 /* Extract a universe domain from the tree root "tree".
1890 * The caller is responsible for making sure that this node
1891 * would not be skipped by isl_schedule_tree_first_schedule_descendant
1892 * and that it is not a leaf node.
1894 static __isl_give isl_union_set *initial_domain(
1895 __isl_keep isl_schedule_tree *tree)
1897 isl_multi_union_pw_aff *mupa;
1898 isl_union_set *domain;
1899 isl_union_map *exp;
1901 if (!tree)
1902 return NULL;
1904 switch (tree->type) {
1905 case isl_schedule_node_error:
1906 return NULL;
1907 case isl_schedule_node_context:
1908 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1909 "context node should be handled by caller",
1910 return NULL);
1911 case isl_schedule_node_guard:
1912 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1913 "guard node should be handled by caller",
1914 return NULL);
1915 case isl_schedule_node_mark:
1916 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1917 "mark node should be handled by caller",
1918 return NULL);
1919 case isl_schedule_node_extension:
1920 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1921 "cannot construct subtree schedule of tree "
1922 "with extension nodes", return NULL);
1923 case isl_schedule_node_band:
1924 if (isl_schedule_tree_band_n_member(tree) == 0)
1925 isl_die(isl_schedule_tree_get_ctx(tree),
1926 isl_error_internal,
1927 "0D band should be handled by caller",
1928 return NULL);
1929 mupa = isl_schedule_band_get_partial_schedule(tree->band);
1930 domain = isl_multi_union_pw_aff_domain(mupa);
1931 domain = isl_union_set_universe(domain);
1932 break;
1933 case isl_schedule_node_domain:
1934 domain = isl_schedule_tree_domain_get_domain(tree);
1935 domain = isl_union_set_universe(domain);
1936 break;
1937 case isl_schedule_node_expansion:
1938 exp = isl_schedule_tree_expansion_get_expansion(tree);
1939 exp = isl_union_map_universe(exp);
1940 domain = isl_union_map_domain(exp);
1941 break;
1942 case isl_schedule_node_filter:
1943 domain = isl_schedule_tree_filter_get_filter(tree);
1944 domain = isl_union_set_universe(domain);
1945 break;
1946 case isl_schedule_node_leaf:
1947 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1948 "leaf node should be handled by caller", return NULL);
1949 case isl_schedule_node_set:
1950 case isl_schedule_node_sequence:
1951 domain = initial_domain_from_children(tree);
1952 break;
1955 return domain;
1958 /* Return the subtree schedule of a node that contains some schedule
1959 * information, i.e., a node that would not be skipped by
1960 * isl_schedule_tree_first_schedule_descendant and that is not a leaf.
1962 * If the tree contains any expansions, then the returned subtree
1963 * schedule is formulated in terms of the expanded domains.
1964 * The tree is not allowed to contain any extension nodes.
1966 * We start with an initial zero-dimensional subtree schedule based
1967 * on the domain information in the root node and then extend it
1968 * based on the schedule information in the root node and its descendants.
1970 __isl_give isl_union_map *isl_schedule_tree_get_subtree_schedule_union_map(
1971 __isl_keep isl_schedule_tree *tree)
1973 isl_union_set *domain;
1974 isl_union_map *umap;
1976 domain = initial_domain(tree);
1977 umap = isl_union_map_from_domain(domain);
1978 return subtree_schedule_extend(tree, umap);
1981 /* Multiply the partial schedule of the band root node of "tree"
1982 * with the factors in "mv".
1984 __isl_give isl_schedule_tree *isl_schedule_tree_band_scale(
1985 __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
1987 if (!tree || !mv)
1988 goto error;
1989 if (tree->type != isl_schedule_node_band)
1990 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1991 "not a band node", goto error);
1993 tree = isl_schedule_tree_cow(tree);
1994 if (!tree)
1995 goto error;
1997 tree->band = isl_schedule_band_scale(tree->band, mv);
1998 if (!tree->band)
1999 return isl_schedule_tree_free(tree);
2001 return tree;
2002 error:
2003 isl_schedule_tree_free(tree);
2004 isl_multi_val_free(mv);
2005 return NULL;
2008 /* Divide the partial schedule of the band root node of "tree"
2009 * by the factors in "mv".
2011 __isl_give isl_schedule_tree *isl_schedule_tree_band_scale_down(
2012 __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
2014 if (!tree || !mv)
2015 goto error;
2016 if (tree->type != isl_schedule_node_band)
2017 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2018 "not a band node", goto error);
2020 tree = isl_schedule_tree_cow(tree);
2021 if (!tree)
2022 goto error;
2024 tree->band = isl_schedule_band_scale_down(tree->band, mv);
2025 if (!tree->band)
2026 return isl_schedule_tree_free(tree);
2028 return tree;
2029 error:
2030 isl_schedule_tree_free(tree);
2031 isl_multi_val_free(mv);
2032 return NULL;
2035 /* Given two trees with sequence roots, replace the child at position
2036 * "pos" of "tree" with the children of "child".
2038 __isl_give isl_schedule_tree *isl_schedule_tree_sequence_splice(
2039 __isl_take isl_schedule_tree *tree, int pos,
2040 __isl_take isl_schedule_tree *child)
2042 int n;
2043 isl_schedule_tree_list *list1, *list2;
2045 tree = isl_schedule_tree_cow(tree);
2046 if (!tree || !child)
2047 goto error;
2048 if (isl_schedule_tree_get_type(tree) != isl_schedule_node_sequence)
2049 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2050 "not a sequence node", goto error);
2051 n = isl_schedule_tree_n_children(tree);
2052 if (pos < 0 || pos >= n)
2053 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2054 "position out of bounds", goto error);
2055 if (isl_schedule_tree_get_type(child) != isl_schedule_node_sequence)
2056 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2057 "not a sequence node", goto error);
2059 list1 = isl_schedule_tree_list_copy(tree->children);
2060 list1 = isl_schedule_tree_list_drop(list1, pos, n - pos);
2061 list2 = isl_schedule_tree_list_copy(tree->children);
2062 list2 = isl_schedule_tree_list_drop(list2, 0, pos + 1);
2063 list1 = isl_schedule_tree_list_concat(list1,
2064 isl_schedule_tree_list_copy(child->children));
2065 list1 = isl_schedule_tree_list_concat(list1, list2);
2067 isl_schedule_tree_free(tree);
2068 isl_schedule_tree_free(child);
2069 return isl_schedule_tree_from_children(isl_schedule_node_sequence,
2070 list1);
2071 error:
2072 isl_schedule_tree_free(tree);
2073 isl_schedule_tree_free(child);
2074 return NULL;
2077 /* Tile the band root node of "tree" with tile sizes "sizes".
2079 * We duplicate the band node, change the schedule of one of them
2080 * to the tile schedule and the other to the point schedule and then
2081 * attach the point band as a child to the tile band.
2083 __isl_give isl_schedule_tree *isl_schedule_tree_band_tile(
2084 __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *sizes)
2086 isl_schedule_tree *child = NULL;
2088 if (!tree || !sizes)
2089 goto error;
2090 if (tree->type != isl_schedule_node_band)
2091 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2092 "not a band node", goto error);
2094 child = isl_schedule_tree_copy(tree);
2095 tree = isl_schedule_tree_cow(tree);
2096 child = isl_schedule_tree_cow(child);
2097 if (!tree || !child)
2098 goto error;
2100 tree->band = isl_schedule_band_tile(tree->band,
2101 isl_multi_val_copy(sizes));
2102 if (!tree->band)
2103 goto error;
2104 child->band = isl_schedule_band_point(child->band, tree->band, sizes);
2105 if (!child->band)
2106 child = isl_schedule_tree_free(child);
2108 tree = isl_schedule_tree_replace_child(tree, 0, child);
2110 return tree;
2111 error:
2112 isl_schedule_tree_free(child);
2113 isl_schedule_tree_free(tree);
2114 isl_multi_val_free(sizes);
2115 return NULL;
2118 /* Split the band root node of "tree" into two nested band nodes,
2119 * one with the first "pos" dimensions and
2120 * one with the remaining dimensions.
2122 __isl_give isl_schedule_tree *isl_schedule_tree_band_split(
2123 __isl_take isl_schedule_tree *tree, int pos)
2125 int n;
2126 isl_schedule_tree *child;
2128 if (!tree)
2129 return NULL;
2130 if (tree->type != isl_schedule_node_band)
2131 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2132 "not a band node", return isl_schedule_tree_free(tree));
2134 n = isl_schedule_tree_band_n_member(tree);
2135 if (pos < 0 || pos > n)
2136 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2137 "position out of bounds",
2138 return isl_schedule_tree_free(tree));
2140 child = isl_schedule_tree_copy(tree);
2141 tree = isl_schedule_tree_cow(tree);
2142 child = isl_schedule_tree_cow(child);
2143 if (!tree || !child)
2144 goto error;
2146 child->band = isl_schedule_band_drop(child->band, 0, pos);
2147 tree->band = isl_schedule_band_drop(tree->band, pos, n - pos);
2148 if (!child->band || !tree->band)
2149 goto error;
2151 tree = isl_schedule_tree_replace_child(tree, 0, child);
2153 return tree;
2154 error:
2155 isl_schedule_tree_free(child);
2156 isl_schedule_tree_free(tree);
2157 return NULL;
2160 /* Attach "tree2" at each of the leaves of "tree1".
2162 * If "tree1" does not have any explicit children, then make "tree2"
2163 * its single child. Otherwise, attach "tree2" to the leaves of
2164 * each of the children of "tree1".
2166 __isl_give isl_schedule_tree *isl_schedule_tree_append_to_leaves(
2167 __isl_take isl_schedule_tree *tree1,
2168 __isl_take isl_schedule_tree *tree2)
2170 int i, n;
2172 if (!tree1 || !tree2)
2173 goto error;
2174 n = isl_schedule_tree_n_children(tree1);
2175 if (n == 0) {
2176 isl_schedule_tree_list *list;
2177 list = isl_schedule_tree_list_from_schedule_tree(tree2);
2178 tree1 = isl_schedule_tree_set_children(tree1, list);
2179 return tree1;
2181 for (i = 0; i < n; ++i) {
2182 isl_schedule_tree *child;
2184 child = isl_schedule_tree_get_child(tree1, i);
2185 child = isl_schedule_tree_append_to_leaves(child,
2186 isl_schedule_tree_copy(tree2));
2187 tree1 = isl_schedule_tree_replace_child(tree1, i, child);
2190 isl_schedule_tree_free(tree2);
2191 return tree1;
2192 error:
2193 isl_schedule_tree_free(tree1);
2194 isl_schedule_tree_free(tree2);
2195 return NULL;
2198 /* Reset the user pointer on all identifiers of parameters and tuples
2199 * in the root of "tree".
2201 __isl_give isl_schedule_tree *isl_schedule_tree_reset_user(
2202 __isl_take isl_schedule_tree *tree)
2204 if (isl_schedule_tree_is_leaf(tree))
2205 return tree;
2207 tree = isl_schedule_tree_cow(tree);
2208 if (!tree)
2209 return NULL;
2211 switch (tree->type) {
2212 case isl_schedule_node_error:
2213 return isl_schedule_tree_free(tree);
2214 case isl_schedule_node_band:
2215 tree->band = isl_schedule_band_reset_user(tree->band);
2216 if (!tree->band)
2217 return isl_schedule_tree_free(tree);
2218 break;
2219 case isl_schedule_node_context:
2220 tree->context = isl_set_reset_user(tree->context);
2221 if (!tree->context)
2222 return isl_schedule_tree_free(tree);
2223 break;
2224 case isl_schedule_node_domain:
2225 tree->domain = isl_union_set_reset_user(tree->domain);
2226 if (!tree->domain)
2227 return isl_schedule_tree_free(tree);
2228 break;
2229 case isl_schedule_node_expansion:
2230 tree->contraction =
2231 isl_union_pw_multi_aff_reset_user(tree->contraction);
2232 tree->expansion = isl_union_map_reset_user(tree->expansion);
2233 if (!tree->contraction || !tree->expansion)
2234 return isl_schedule_tree_free(tree);
2235 break;
2236 case isl_schedule_node_extension:
2237 tree->extension = isl_union_map_reset_user(tree->extension);
2238 if (!tree->extension)
2239 return isl_schedule_tree_free(tree);
2240 break;
2241 case isl_schedule_node_filter:
2242 tree->filter = isl_union_set_reset_user(tree->filter);
2243 if (!tree->filter)
2244 return isl_schedule_tree_free(tree);
2245 break;
2246 case isl_schedule_node_guard:
2247 tree->guard = isl_set_reset_user(tree->guard);
2248 if (!tree->guard)
2249 return isl_schedule_tree_free(tree);
2250 break;
2251 case isl_schedule_node_leaf:
2252 case isl_schedule_node_mark:
2253 case isl_schedule_node_sequence:
2254 case isl_schedule_node_set:
2255 break;
2258 return tree;
2261 /* Align the parameters of the root of "tree" to those of "space".
2263 __isl_give isl_schedule_tree *isl_schedule_tree_align_params(
2264 __isl_take isl_schedule_tree *tree, __isl_take isl_space *space)
2266 if (!space)
2267 goto error;
2269 if (isl_schedule_tree_is_leaf(tree)) {
2270 isl_space_free(space);
2271 return tree;
2274 tree = isl_schedule_tree_cow(tree);
2275 if (!tree)
2276 goto error;
2278 switch (tree->type) {
2279 case isl_schedule_node_error:
2280 goto error;
2281 case isl_schedule_node_band:
2282 tree->band = isl_schedule_band_align_params(tree->band, space);
2283 if (!tree->band)
2284 return isl_schedule_tree_free(tree);
2285 break;
2286 case isl_schedule_node_context:
2287 tree->context = isl_set_align_params(tree->context, space);
2288 if (!tree->context)
2289 return isl_schedule_tree_free(tree);
2290 break;
2291 case isl_schedule_node_domain:
2292 tree->domain = isl_union_set_align_params(tree->domain, space);
2293 if (!tree->domain)
2294 return isl_schedule_tree_free(tree);
2295 break;
2296 case isl_schedule_node_expansion:
2297 tree->contraction =
2298 isl_union_pw_multi_aff_align_params(tree->contraction,
2299 isl_space_copy(space));
2300 tree->expansion = isl_union_map_align_params(tree->expansion,
2301 space);
2302 if (!tree->contraction || !tree->expansion)
2303 return isl_schedule_tree_free(tree);
2304 break;
2305 case isl_schedule_node_extension:
2306 tree->extension = isl_union_map_align_params(tree->extension,
2307 space);
2308 if (!tree->extension)
2309 return isl_schedule_tree_free(tree);
2310 break;
2311 case isl_schedule_node_filter:
2312 tree->filter = isl_union_set_align_params(tree->filter, space);
2313 if (!tree->filter)
2314 return isl_schedule_tree_free(tree);
2315 break;
2316 case isl_schedule_node_guard:
2317 tree->guard = isl_set_align_params(tree->guard, space);
2318 if (!tree->guard)
2319 return isl_schedule_tree_free(tree);
2320 break;
2321 case isl_schedule_node_leaf:
2322 case isl_schedule_node_mark:
2323 case isl_schedule_node_sequence:
2324 case isl_schedule_node_set:
2325 isl_space_free(space);
2326 break;
2329 return tree;
2330 error:
2331 isl_space_free(space);
2332 isl_schedule_tree_free(tree);
2333 return NULL;
2336 /* Does "tree" involve the iteration domain?
2337 * That is, does it need to be modified
2338 * by isl_schedule_tree_pullback_union_pw_multi_aff?
2340 static int involves_iteration_domain(__isl_keep isl_schedule_tree *tree)
2342 if (!tree)
2343 return -1;
2345 switch (tree->type) {
2346 case isl_schedule_node_error:
2347 return -1;
2348 case isl_schedule_node_band:
2349 case isl_schedule_node_domain:
2350 case isl_schedule_node_expansion:
2351 case isl_schedule_node_extension:
2352 case isl_schedule_node_filter:
2353 return 1;
2354 case isl_schedule_node_context:
2355 case isl_schedule_node_leaf:
2356 case isl_schedule_node_guard:
2357 case isl_schedule_node_mark:
2358 case isl_schedule_node_sequence:
2359 case isl_schedule_node_set:
2360 return 0;
2363 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
2364 "unhandled case", return -1);
2367 /* Compute the pullback of the root node of "tree" by the function
2368 * represented by "upma".
2369 * In other words, plug in "upma" in the iteration domains of
2370 * the root node of "tree".
2371 * We currently do not handle expansion nodes.
2373 * We first check if the root node involves any iteration domains.
2374 * If so, we handle the specific cases.
2376 __isl_give isl_schedule_tree *isl_schedule_tree_pullback_union_pw_multi_aff(
2377 __isl_take isl_schedule_tree *tree,
2378 __isl_take isl_union_pw_multi_aff *upma)
2380 int involves;
2382 if (!tree || !upma)
2383 goto error;
2385 involves = involves_iteration_domain(tree);
2386 if (involves < 0)
2387 goto error;
2388 if (!involves) {
2389 isl_union_pw_multi_aff_free(upma);
2390 return tree;
2393 tree = isl_schedule_tree_cow(tree);
2394 if (!tree)
2395 goto error;
2397 if (tree->type == isl_schedule_node_band) {
2398 tree->band = isl_schedule_band_pullback_union_pw_multi_aff(
2399 tree->band, upma);
2400 if (!tree->band)
2401 return isl_schedule_tree_free(tree);
2402 } else if (tree->type == isl_schedule_node_domain) {
2403 tree->domain =
2404 isl_union_set_preimage_union_pw_multi_aff(tree->domain,
2405 upma);
2406 if (!tree->domain)
2407 return isl_schedule_tree_free(tree);
2408 } else if (tree->type == isl_schedule_node_expansion) {
2409 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_unsupported,
2410 "cannot pullback expansion node", goto error);
2411 } else if (tree->type == isl_schedule_node_extension) {
2412 tree->extension =
2413 isl_union_map_preimage_range_union_pw_multi_aff(
2414 tree->extension, upma);
2415 if (!tree->extension)
2416 return isl_schedule_tree_free(tree);
2417 } else if (tree->type == isl_schedule_node_filter) {
2418 tree->filter =
2419 isl_union_set_preimage_union_pw_multi_aff(tree->filter,
2420 upma);
2421 if (!tree->filter)
2422 return isl_schedule_tree_free(tree);
2425 return tree;
2426 error:
2427 isl_union_pw_multi_aff_free(upma);
2428 isl_schedule_tree_free(tree);
2429 return NULL;
2432 /* Compute the gist of the band tree root with respect to "context".
2434 __isl_give isl_schedule_tree *isl_schedule_tree_band_gist(
2435 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *context)
2437 if (!tree)
2438 return NULL;
2439 if (tree->type != isl_schedule_node_band)
2440 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2441 "not a band node", goto error);
2442 tree = isl_schedule_tree_cow(tree);
2443 if (!tree)
2444 goto error;
2446 tree->band = isl_schedule_band_gist(tree->band, context);
2447 if (!tree->band)
2448 return isl_schedule_tree_free(tree);
2449 return tree;
2450 error:
2451 isl_union_set_free(context);
2452 isl_schedule_tree_free(tree);
2453 return NULL;
2456 /* Are any members in "band" marked coincident?
2458 static int any_coincident(__isl_keep isl_schedule_band *band)
2460 int i, n;
2462 n = isl_schedule_band_n_member(band);
2463 for (i = 0; i < n; ++i)
2464 if (isl_schedule_band_member_get_coincident(band, i))
2465 return 1;
2467 return 0;
2470 /* Print the band node "band" to "p".
2472 * The permutable and coincident properties are only printed if they
2473 * are different from the defaults.
2474 * The coincident property is always printed in YAML flow style.
2476 static __isl_give isl_printer *print_tree_band(__isl_take isl_printer *p,
2477 __isl_keep isl_schedule_band *band)
2479 isl_union_set *options;
2480 int empty;
2482 p = isl_printer_print_str(p, "schedule");
2483 p = isl_printer_yaml_next(p);
2484 p = isl_printer_print_str(p, "\"");
2485 p = isl_printer_print_multi_union_pw_aff(p, band->mupa);
2486 p = isl_printer_print_str(p, "\"");
2487 if (isl_schedule_band_get_permutable(band)) {
2488 p = isl_printer_yaml_next(p);
2489 p = isl_printer_print_str(p, "permutable");
2490 p = isl_printer_yaml_next(p);
2491 p = isl_printer_print_int(p, 1);
2493 if (any_coincident(band)) {
2494 int i, n;
2495 int style;
2497 p = isl_printer_yaml_next(p);
2498 p = isl_printer_print_str(p, "coincident");
2499 p = isl_printer_yaml_next(p);
2500 style = isl_printer_get_yaml_style(p);
2501 p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_FLOW);
2502 p = isl_printer_yaml_start_sequence(p);
2503 n = isl_schedule_band_n_member(band);
2504 for (i = 0; i < n; ++i) {
2505 p = isl_printer_print_int(p,
2506 isl_schedule_band_member_get_coincident(band, i));
2507 p = isl_printer_yaml_next(p);
2509 p = isl_printer_yaml_end_sequence(p);
2510 p = isl_printer_set_yaml_style(p, style);
2512 options = isl_schedule_band_get_ast_build_options(band);
2513 empty = isl_union_set_is_empty(options);
2514 if (empty < 0)
2515 p = isl_printer_free(p);
2516 if (!empty) {
2517 p = isl_printer_yaml_next(p);
2518 p = isl_printer_print_str(p, "options");
2519 p = isl_printer_yaml_next(p);
2520 p = isl_printer_print_str(p, "\"");
2521 p = isl_printer_print_union_set(p, options);
2522 p = isl_printer_print_str(p, "\"");
2524 isl_union_set_free(options);
2526 return p;
2529 /* Print "tree" to "p".
2531 * If "n_ancestor" is non-negative, then "child_pos" contains the child
2532 * positions of a descendant of the current node that should be marked
2533 * (by the comment "YOU ARE HERE"). In particular, if "n_ancestor"
2534 * is zero, then the current node should be marked.
2535 * The marking is only printed in YAML block format.
2537 * Implicit leaf nodes are not printed, except if they correspond
2538 * to the node that should be marked.
2540 __isl_give isl_printer *isl_printer_print_schedule_tree_mark(
2541 __isl_take isl_printer *p, __isl_keep isl_schedule_tree *tree,
2542 int n_ancestor, int *child_pos)
2544 int i, n;
2545 int sequence = 0;
2546 int block;
2548 block = isl_printer_get_yaml_style(p) == ISL_YAML_STYLE_BLOCK;
2550 p = isl_printer_yaml_start_mapping(p);
2551 if (n_ancestor == 0 && block) {
2552 p = isl_printer_print_str(p, "# YOU ARE HERE");
2553 p = isl_printer_end_line(p);
2554 p = isl_printer_start_line(p);
2556 switch (tree->type) {
2557 case isl_schedule_node_error:
2558 p = isl_printer_print_str(p, "ERROR");
2559 break;
2560 case isl_schedule_node_leaf:
2561 p = isl_printer_print_str(p, "leaf");
2562 break;
2563 case isl_schedule_node_sequence:
2564 p = isl_printer_print_str(p, "sequence");
2565 sequence = 1;
2566 break;
2567 case isl_schedule_node_set:
2568 p = isl_printer_print_str(p, "set");
2569 sequence = 1;
2570 break;
2571 case isl_schedule_node_context:
2572 p = isl_printer_print_str(p, "context");
2573 p = isl_printer_yaml_next(p);
2574 p = isl_printer_print_str(p, "\"");
2575 p = isl_printer_print_set(p, tree->context);
2576 p = isl_printer_print_str(p, "\"");
2577 break;
2578 case isl_schedule_node_domain:
2579 p = isl_printer_print_str(p, "domain");
2580 p = isl_printer_yaml_next(p);
2581 p = isl_printer_print_str(p, "\"");
2582 p = isl_printer_print_union_set(p, tree->domain);
2583 p = isl_printer_print_str(p, "\"");
2584 break;
2585 case isl_schedule_node_expansion:
2586 p = isl_printer_print_str(p, "contraction");
2587 p = isl_printer_yaml_next(p);
2588 p = isl_printer_print_str(p, "\"");
2589 p = isl_printer_print_union_pw_multi_aff(p, tree->contraction);
2590 p = isl_printer_print_str(p, "\"");
2591 p = isl_printer_yaml_next(p);
2592 p = isl_printer_print_str(p, "expansion");
2593 p = isl_printer_yaml_next(p);
2594 p = isl_printer_print_str(p, "\"");
2595 p = isl_printer_print_union_map(p, tree->expansion);
2596 p = isl_printer_print_str(p, "\"");
2597 break;
2598 case isl_schedule_node_extension:
2599 p = isl_printer_print_str(p, "extension");
2600 p = isl_printer_yaml_next(p);
2601 p = isl_printer_print_str(p, "\"");
2602 p = isl_printer_print_union_map(p, tree->extension);
2603 p = isl_printer_print_str(p, "\"");
2604 break;
2605 case isl_schedule_node_filter:
2606 p = isl_printer_print_str(p, "filter");
2607 p = isl_printer_yaml_next(p);
2608 p = isl_printer_print_str(p, "\"");
2609 p = isl_printer_print_union_set(p, tree->filter);
2610 p = isl_printer_print_str(p, "\"");
2611 break;
2612 case isl_schedule_node_guard:
2613 p = isl_printer_print_str(p, "guard");
2614 p = isl_printer_yaml_next(p);
2615 p = isl_printer_print_str(p, "\"");
2616 p = isl_printer_print_set(p, tree->guard);
2617 p = isl_printer_print_str(p, "\"");
2618 break;
2619 case isl_schedule_node_mark:
2620 p = isl_printer_print_str(p, "mark");
2621 p = isl_printer_yaml_next(p);
2622 p = isl_printer_print_str(p, "\"");
2623 p = isl_printer_print_str(p, isl_id_get_name(tree->mark));
2624 p = isl_printer_print_str(p, "\"");
2625 break;
2626 case isl_schedule_node_band:
2627 p = print_tree_band(p, tree->band);
2628 break;
2630 p = isl_printer_yaml_next(p);
2632 if (!tree->children) {
2633 if (n_ancestor > 0 && block) {
2634 isl_schedule_tree *leaf;
2636 p = isl_printer_print_str(p, "child");
2637 p = isl_printer_yaml_next(p);
2638 leaf = isl_schedule_tree_leaf(isl_printer_get_ctx(p));
2639 p = isl_printer_print_schedule_tree_mark(p,
2640 leaf, 0, NULL);
2641 isl_schedule_tree_free(leaf);
2642 p = isl_printer_yaml_next(p);
2644 return isl_printer_yaml_end_mapping(p);
2647 if (sequence) {
2648 p = isl_printer_yaml_start_sequence(p);
2649 } else {
2650 p = isl_printer_print_str(p, "child");
2651 p = isl_printer_yaml_next(p);
2654 n = isl_schedule_tree_list_n_schedule_tree(tree->children);
2655 for (i = 0; i < n; ++i) {
2656 isl_schedule_tree *t;
2658 t = isl_schedule_tree_get_child(tree, i);
2659 if (n_ancestor > 0 && child_pos[0] == i)
2660 p = isl_printer_print_schedule_tree_mark(p, t,
2661 n_ancestor - 1, child_pos + 1);
2662 else
2663 p = isl_printer_print_schedule_tree_mark(p, t,
2664 -1, NULL);
2665 isl_schedule_tree_free(t);
2667 p = isl_printer_yaml_next(p);
2670 if (sequence)
2671 p = isl_printer_yaml_end_sequence(p);
2672 p = isl_printer_yaml_end_mapping(p);
2674 return p;
2677 /* Print "tree" to "p".
2679 __isl_give isl_printer *isl_printer_print_schedule_tree(
2680 __isl_take isl_printer *p, __isl_keep isl_schedule_tree *tree)
2682 return isl_printer_print_schedule_tree_mark(p, tree, -1, NULL);
2685 void isl_schedule_tree_dump(__isl_keep isl_schedule_tree *tree)
2687 isl_ctx *ctx;
2688 isl_printer *printer;
2690 if (!tree)
2691 return;
2693 ctx = isl_schedule_tree_get_ctx(tree);
2694 printer = isl_printer_to_file(ctx, stderr);
2695 printer = isl_printer_set_yaml_style(printer, ISL_YAML_STYLE_BLOCK);
2696 printer = isl_printer_print_schedule_tree(printer, tree);
2698 isl_printer_free(printer);