isl 0.27
[isl.git] / isl_schedule_tree.c
blob8dfe1d728b650df0140b2245cd946ad889568c5a
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/id.h>
17 #include <isl/val.h>
18 #include <isl/space.h>
19 #include <isl/map.h>
20 #include <isl_schedule_band.h>
21 #include <isl_schedule_private.h>
23 #undef EL
24 #define EL isl_schedule_tree
26 #include <isl_list_templ.h>
28 #undef EL_BASE
29 #define EL_BASE schedule_tree
31 #include <isl_list_templ.c>
33 /* Is "tree" the leaf of a schedule tree?
35 int isl_schedule_tree_is_leaf(__isl_keep isl_schedule_tree *tree)
37 return isl_schedule_tree_get_type(tree) == isl_schedule_node_leaf;
40 /* Create a new schedule tree of type "type".
41 * The caller is responsible for filling in the type specific fields and
42 * the children.
44 * By default, the single node tree does not have any anchored nodes.
45 * The caller is responsible for updating the anchored field if needed.
47 static __isl_give isl_schedule_tree *isl_schedule_tree_alloc(isl_ctx *ctx,
48 enum isl_schedule_node_type type)
50 isl_schedule_tree *tree;
52 if (type == isl_schedule_node_error)
53 return NULL;
55 tree = isl_calloc_type(ctx, isl_schedule_tree);
56 if (!tree)
57 return NULL;
59 tree->ref = 1;
60 tree->ctx = ctx;
61 isl_ctx_ref(ctx);
62 tree->type = type;
63 tree->anchored = 0;
65 return tree;
68 /* Return a fresh copy of "tree".
70 __isl_give isl_schedule_tree *isl_schedule_tree_dup(
71 __isl_keep isl_schedule_tree *tree)
73 isl_ctx *ctx;
74 isl_schedule_tree *dup;
76 if (!tree)
77 return NULL;
79 ctx = isl_schedule_tree_get_ctx(tree);
80 dup = isl_schedule_tree_alloc(ctx, tree->type);
81 if (!dup)
82 return NULL;
84 switch (tree->type) {
85 case isl_schedule_node_error:
86 isl_die(ctx, isl_error_internal,
87 "allocation should have failed",
88 return isl_schedule_tree_free(dup));
89 case isl_schedule_node_band:
90 dup->band = isl_schedule_band_copy(tree->band);
91 if (!dup->band)
92 return isl_schedule_tree_free(dup);
93 break;
94 case isl_schedule_node_context:
95 dup->context = isl_set_copy(tree->context);
96 if (!dup->context)
97 return isl_schedule_tree_free(dup);
98 break;
99 case isl_schedule_node_domain:
100 dup->domain = isl_union_set_copy(tree->domain);
101 if (!dup->domain)
102 return isl_schedule_tree_free(dup);
103 break;
104 case isl_schedule_node_expansion:
105 dup->contraction =
106 isl_union_pw_multi_aff_copy(tree->contraction);
107 dup->expansion = isl_union_map_copy(tree->expansion);
108 if (!dup->contraction || !dup->expansion)
109 return isl_schedule_tree_free(dup);
110 break;
111 case isl_schedule_node_extension:
112 dup->extension = isl_union_map_copy(tree->extension);
113 if (!dup->extension)
114 return isl_schedule_tree_free(dup);
115 break;
116 case isl_schedule_node_filter:
117 dup->filter = isl_union_set_copy(tree->filter);
118 if (!dup->filter)
119 return isl_schedule_tree_free(dup);
120 break;
121 case isl_schedule_node_guard:
122 dup->guard = isl_set_copy(tree->guard);
123 if (!dup->guard)
124 return isl_schedule_tree_free(dup);
125 break;
126 case isl_schedule_node_mark:
127 dup->mark = isl_id_copy(tree->mark);
128 if (!dup->mark)
129 return isl_schedule_tree_free(dup);
130 break;
131 case isl_schedule_node_leaf:
132 case isl_schedule_node_sequence:
133 case isl_schedule_node_set:
134 break;
137 if (tree->children) {
138 dup->children = isl_schedule_tree_list_copy(tree->children);
139 if (!dup->children)
140 return isl_schedule_tree_free(dup);
142 dup->anchored = tree->anchored;
144 return dup;
147 /* Return an isl_schedule_tree that is equal to "tree" and that has only
148 * a single reference.
150 __isl_give isl_schedule_tree *isl_schedule_tree_cow(
151 __isl_take isl_schedule_tree *tree)
153 if (!tree)
154 return NULL;
156 if (tree->ref == 1)
157 return tree;
158 tree->ref--;
159 return isl_schedule_tree_dup(tree);
162 /* Return a new reference to "tree".
164 __isl_give isl_schedule_tree *isl_schedule_tree_copy(
165 __isl_keep isl_schedule_tree *tree)
167 if (!tree)
168 return NULL;
170 tree->ref++;
171 return tree;
174 /* Free "tree" and return NULL.
176 __isl_null isl_schedule_tree *isl_schedule_tree_free(
177 __isl_take isl_schedule_tree *tree)
179 if (!tree)
180 return NULL;
181 if (--tree->ref > 0)
182 return NULL;
184 switch (tree->type) {
185 case isl_schedule_node_band:
186 isl_schedule_band_free(tree->band);
187 break;
188 case isl_schedule_node_context:
189 isl_set_free(tree->context);
190 break;
191 case isl_schedule_node_domain:
192 isl_union_set_free(tree->domain);
193 break;
194 case isl_schedule_node_expansion:
195 isl_union_pw_multi_aff_free(tree->contraction);
196 isl_union_map_free(tree->expansion);
197 break;
198 case isl_schedule_node_extension:
199 isl_union_map_free(tree->extension);
200 break;
201 case isl_schedule_node_filter:
202 isl_union_set_free(tree->filter);
203 break;
204 case isl_schedule_node_guard:
205 isl_set_free(tree->guard);
206 break;
207 case isl_schedule_node_mark:
208 isl_id_free(tree->mark);
209 break;
210 case isl_schedule_node_sequence:
211 case isl_schedule_node_set:
212 case isl_schedule_node_error:
213 case isl_schedule_node_leaf:
214 break;
216 isl_schedule_tree_list_free(tree->children);
217 isl_ctx_deref(tree->ctx);
218 free(tree);
220 return NULL;
223 /* Create and return a new leaf schedule tree.
225 __isl_give isl_schedule_tree *isl_schedule_tree_leaf(isl_ctx *ctx)
227 return isl_schedule_tree_alloc(ctx, isl_schedule_node_leaf);
230 /* Create a new band schedule tree referring to "band"
231 * with no children.
233 __isl_give isl_schedule_tree *isl_schedule_tree_from_band(
234 __isl_take isl_schedule_band *band)
236 isl_ctx *ctx;
237 isl_schedule_tree *tree;
239 if (!band)
240 return NULL;
242 ctx = isl_schedule_band_get_ctx(band);
243 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_band);
244 if (!tree)
245 goto error;
247 tree->band = band;
248 tree->anchored = isl_schedule_band_is_anchored(band);
250 return tree;
251 error:
252 isl_schedule_band_free(band);
253 return NULL;
256 /* Create a new context schedule tree with the given context and no children.
257 * Since the context references the outer schedule dimension,
258 * the tree is anchored.
260 __isl_give isl_schedule_tree *isl_schedule_tree_from_context(
261 __isl_take isl_set *context)
263 isl_ctx *ctx;
264 isl_schedule_tree *tree;
266 if (!context)
267 return NULL;
269 ctx = isl_set_get_ctx(context);
270 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_context);
271 if (!tree)
272 goto error;
274 tree->context = context;
275 tree->anchored = 1;
277 return tree;
278 error:
279 isl_set_free(context);
280 return NULL;
283 /* Create a new domain schedule tree with the given domain and no children.
285 __isl_give isl_schedule_tree *isl_schedule_tree_from_domain(
286 __isl_take isl_union_set *domain)
288 isl_ctx *ctx;
289 isl_schedule_tree *tree;
291 if (!domain)
292 return NULL;
294 ctx = isl_union_set_get_ctx(domain);
295 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_domain);
296 if (!tree)
297 goto error;
299 tree->domain = domain;
301 return tree;
302 error:
303 isl_union_set_free(domain);
304 return NULL;
307 /* Create a new expansion schedule tree with the given contraction and
308 * expansion and no children.
310 __isl_give isl_schedule_tree *isl_schedule_tree_from_expansion(
311 __isl_take isl_union_pw_multi_aff *contraction,
312 __isl_take isl_union_map *expansion)
314 isl_ctx *ctx;
315 isl_schedule_tree *tree;
317 if (!contraction || !expansion)
318 goto error;
320 ctx = isl_union_map_get_ctx(expansion);
321 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_expansion);
322 if (!tree)
323 goto error;
325 tree->contraction = contraction;
326 tree->expansion = expansion;
328 return tree;
329 error:
330 isl_union_pw_multi_aff_free(contraction);
331 isl_union_map_free(expansion);
332 return NULL;
335 /* Create a new extension schedule tree with the given extension and
336 * no children.
337 * Since the domain of the extension refers to the outer schedule dimension,
338 * the tree is anchored.
340 __isl_give isl_schedule_tree *isl_schedule_tree_from_extension(
341 __isl_take isl_union_map *extension)
343 isl_ctx *ctx;
344 isl_schedule_tree *tree;
346 if (!extension)
347 return NULL;
349 ctx = isl_union_map_get_ctx(extension);
350 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_extension);
351 if (!tree)
352 goto error;
354 tree->extension = extension;
355 tree->anchored = 1;
357 return tree;
358 error:
359 isl_union_map_free(extension);
360 return NULL;
363 /* Create a new filter schedule tree with the given filter and no children.
365 __isl_give isl_schedule_tree *isl_schedule_tree_from_filter(
366 __isl_take isl_union_set *filter)
368 isl_ctx *ctx;
369 isl_schedule_tree *tree;
371 if (!filter)
372 return NULL;
374 ctx = isl_union_set_get_ctx(filter);
375 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_filter);
376 if (!tree)
377 goto error;
379 tree->filter = filter;
381 return tree;
382 error:
383 isl_union_set_free(filter);
384 return NULL;
387 /* Create a new guard schedule tree with the given guard and no children.
388 * Since the guard references the outer schedule dimension,
389 * the tree is anchored.
391 __isl_give isl_schedule_tree *isl_schedule_tree_from_guard(
392 __isl_take isl_set *guard)
394 isl_ctx *ctx;
395 isl_schedule_tree *tree;
397 if (!guard)
398 return NULL;
400 ctx = isl_set_get_ctx(guard);
401 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_guard);
402 if (!tree)
403 goto error;
405 tree->guard = guard;
406 tree->anchored = 1;
408 return tree;
409 error:
410 isl_set_free(guard);
411 return NULL;
414 /* Create a new mark schedule tree with the given mark identifier and
415 * no children.
417 __isl_give isl_schedule_tree *isl_schedule_tree_from_mark(
418 __isl_take isl_id *mark)
420 isl_ctx *ctx;
421 isl_schedule_tree *tree;
423 if (!mark)
424 return NULL;
426 ctx = isl_id_get_ctx(mark);
427 tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_mark);
428 if (!tree)
429 goto error;
431 tree->mark = mark;
433 return tree;
434 error:
435 isl_id_free(mark);
436 return NULL;
439 /* Does "tree" have any node that depends on its position
440 * in the complete schedule tree?
442 isl_bool isl_schedule_tree_is_subtree_anchored(
443 __isl_keep isl_schedule_tree *tree)
445 return tree ? isl_bool_ok(tree->anchored) : isl_bool_error;
448 /* Does the root node of "tree" depend on its position in the complete
449 * schedule tree?
450 * Band nodes may be anchored depending on the associated AST build options.
451 * Context, extension and guard nodes are always anchored.
453 int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree *tree)
455 if (!tree)
456 return -1;
458 switch (isl_schedule_tree_get_type(tree)) {
459 case isl_schedule_node_error:
460 return -1;
461 case isl_schedule_node_band:
462 return isl_schedule_band_is_anchored(tree->band);
463 case isl_schedule_node_context:
464 case isl_schedule_node_extension:
465 case isl_schedule_node_guard:
466 return 1;
467 case isl_schedule_node_domain:
468 case isl_schedule_node_expansion:
469 case isl_schedule_node_filter:
470 case isl_schedule_node_leaf:
471 case isl_schedule_node_mark:
472 case isl_schedule_node_sequence:
473 case isl_schedule_node_set:
474 return 0;
477 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
478 "unhandled case", return -1);
481 /* Update the anchored field of "tree" based on whether the root node
482 * itself in anchored and the anchored fields of the children.
484 * This function should be called whenever the children of a tree node
485 * are changed or the anchoredness of the tree root itself changes.
487 __isl_give isl_schedule_tree *isl_schedule_tree_update_anchored(
488 __isl_take isl_schedule_tree *tree)
490 int i;
491 isl_size n;
492 int anchored;
494 anchored = isl_schedule_tree_is_anchored(tree);
495 n = isl_schedule_tree_n_children(tree);
496 if (anchored < 0 || n < 0)
497 return isl_schedule_tree_free(tree);
499 for (i = 0; !anchored && i < n; ++i) {
500 isl_schedule_tree *child;
502 child = isl_schedule_tree_get_child(tree, i);
503 if (!child)
504 return isl_schedule_tree_free(tree);
505 anchored = child->anchored;
506 isl_schedule_tree_free(child);
509 if (anchored == tree->anchored)
510 return tree;
511 tree = isl_schedule_tree_cow(tree);
512 if (!tree)
513 return NULL;
514 tree->anchored = anchored;
515 return tree;
518 /* Create a new tree of the given type (isl_schedule_node_sequence or
519 * isl_schedule_node_set) with the given children.
521 __isl_give isl_schedule_tree *isl_schedule_tree_from_children(
522 enum isl_schedule_node_type type,
523 __isl_take isl_schedule_tree_list *list)
525 isl_ctx *ctx;
526 isl_schedule_tree *tree;
528 if (!list)
529 return NULL;
531 ctx = isl_schedule_tree_list_get_ctx(list);
532 tree = isl_schedule_tree_alloc(ctx, type);
533 if (!tree)
534 goto error;
536 tree->children = list;
537 tree = isl_schedule_tree_update_anchored(tree);
539 return tree;
540 error:
541 isl_schedule_tree_list_free(list);
542 return NULL;
545 /* Construct a tree with a root node of type "type" and as children
546 * "tree1" and "tree2".
547 * If the root of one (or both) of the input trees is itself of type "type",
548 * then the tree is replaced by its children.
550 __isl_give isl_schedule_tree *isl_schedule_tree_from_pair(
551 enum isl_schedule_node_type type, __isl_take isl_schedule_tree *tree1,
552 __isl_take isl_schedule_tree *tree2)
554 isl_ctx *ctx;
555 isl_schedule_tree_list *list;
557 if (!tree1 || !tree2)
558 goto error;
560 ctx = isl_schedule_tree_get_ctx(tree1);
561 if (isl_schedule_tree_get_type(tree1) == type) {
562 list = isl_schedule_tree_list_copy(tree1->children);
563 isl_schedule_tree_free(tree1);
564 } else {
565 list = isl_schedule_tree_list_alloc(ctx, 2);
566 list = isl_schedule_tree_list_add(list, tree1);
568 if (isl_schedule_tree_get_type(tree2) == type) {
569 isl_schedule_tree_list *children;
571 children = isl_schedule_tree_list_copy(tree2->children);
572 list = isl_schedule_tree_list_concat(list, children);
573 isl_schedule_tree_free(tree2);
574 } else {
575 list = isl_schedule_tree_list_add(list, tree2);
578 return isl_schedule_tree_from_children(type, list);
579 error:
580 isl_schedule_tree_free(tree1);
581 isl_schedule_tree_free(tree2);
582 return NULL;
585 /* Construct a tree with a sequence root node and as children
586 * "tree1" and "tree2".
587 * If the root of one (or both) of the input trees is itself a sequence,
588 * then the tree is replaced by its children.
590 __isl_give isl_schedule_tree *isl_schedule_tree_sequence_pair(
591 __isl_take isl_schedule_tree *tree1,
592 __isl_take isl_schedule_tree *tree2)
594 return isl_schedule_tree_from_pair(isl_schedule_node_sequence,
595 tree1, tree2);
598 /* Construct a tree with a set root node and as children
599 * "tree1" and "tree2".
600 * If the root of one (or both) of the input trees is itself a set,
601 * then the tree is replaced by its children.
603 __isl_give isl_schedule_tree *isl_schedule_tree_set_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_set, tree1, tree2);
610 /* Return the isl_ctx to which "tree" belongs.
612 isl_ctx *isl_schedule_tree_get_ctx(__isl_keep isl_schedule_tree *tree)
614 return tree ? tree->ctx : NULL;
617 /* Return the type of the root of the tree or isl_schedule_node_error
618 * on error.
620 enum isl_schedule_node_type isl_schedule_tree_get_type(
621 __isl_keep isl_schedule_tree *tree)
623 return tree ? tree->type : isl_schedule_node_error;
626 /* Are "tree1" and "tree2" obviously equal to each other?
628 isl_bool isl_schedule_tree_plain_is_equal(__isl_keep isl_schedule_tree *tree1,
629 __isl_keep isl_schedule_tree *tree2)
631 isl_bool equal;
632 int i;
633 isl_size n1, n2;
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 = isl_bool_ok(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 n1 = isl_schedule_tree_n_children(tree1);
687 n2 = isl_schedule_tree_n_children(tree2);
688 if (n1 < 0 || n2 < 0)
689 return isl_bool_error;
690 if (n1 != n2)
691 return isl_bool_false;
692 for (i = 0; i < n1; ++i) {
693 isl_schedule_tree *child1, *child2;
695 child1 = isl_schedule_tree_get_child(tree1, i);
696 child2 = isl_schedule_tree_get_child(tree2, i);
697 equal = isl_schedule_tree_plain_is_equal(child1, child2);
698 isl_schedule_tree_free(child1);
699 isl_schedule_tree_free(child2);
701 if (equal < 0 || !equal)
702 return equal;
705 return isl_bool_true;
708 /* Does "tree" have any children, other than an implicit leaf.
710 int isl_schedule_tree_has_children(__isl_keep isl_schedule_tree *tree)
712 if (!tree)
713 return -1;
715 return tree->children != NULL;
718 /* Return the number of children of "tree", excluding implicit leaves.
719 * The "children" field is NULL if there are
720 * no children (except for the implicit leaves).
722 isl_size isl_schedule_tree_n_children(__isl_keep isl_schedule_tree *tree)
724 if (!tree)
725 return isl_size_error;
727 if (!tree->children)
728 return 0;
729 return isl_schedule_tree_list_n_schedule_tree(tree->children);
732 /* Return a copy of the (explicit) child at position "pos" of "tree".
734 __isl_give isl_schedule_tree *isl_schedule_tree_get_child(
735 __isl_keep isl_schedule_tree *tree, int pos)
737 if (!tree)
738 return NULL;
739 if (!tree->children)
740 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
741 "schedule tree has no explicit children", return NULL);
742 return isl_schedule_tree_list_get_schedule_tree(tree->children, pos);
745 /* Return a copy of the (explicit) child at position "pos" of "tree" and
746 * free "tree".
748 __isl_give isl_schedule_tree *isl_schedule_tree_child(
749 __isl_take isl_schedule_tree *tree, int pos)
751 isl_schedule_tree *child;
753 child = isl_schedule_tree_get_child(tree, pos);
754 isl_schedule_tree_free(tree);
755 return child;
758 /* Remove all (explicit) children from "tree".
760 __isl_give isl_schedule_tree *isl_schedule_tree_reset_children(
761 __isl_take isl_schedule_tree *tree)
763 tree = isl_schedule_tree_cow(tree);
764 if (!tree)
765 return NULL;
766 tree->children = isl_schedule_tree_list_free(tree->children);
767 return tree;
770 /* Remove the child at position "pos" from the children of "tree".
771 * If there was only one child to begin with, then remove all children.
773 __isl_give isl_schedule_tree *isl_schedule_tree_drop_child(
774 __isl_take isl_schedule_tree *tree, int pos)
776 isl_size n;
778 tree = isl_schedule_tree_cow(tree);
780 n = isl_schedule_tree_n_children(tree);
781 if (n < 0)
782 return isl_schedule_tree_free(tree);
783 if (n == 0)
784 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
785 "tree does not have any explicit children",
786 return isl_schedule_tree_free(tree));
787 if (pos < 0 || pos >= n)
788 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
789 "position out of bounds",
790 return isl_schedule_tree_free(tree));
791 if (n == 1)
792 return isl_schedule_tree_reset_children(tree);
794 tree->children = isl_schedule_tree_list_drop(tree->children, pos, 1);
795 if (!tree->children)
796 return isl_schedule_tree_free(tree);
798 return tree;
801 /* Replace the child at position "pos" of "tree" by "child".
803 * If the new child is a leaf, then it is not explicitly
804 * recorded in the list of children. Instead, the list of children
805 * (which is assumed to have only one element) is removed.
806 * Note that the children of set and sequence nodes are always
807 * filters, so they cannot be replaced by empty trees.
809 __isl_give isl_schedule_tree *isl_schedule_tree_replace_child(
810 __isl_take isl_schedule_tree *tree, int pos,
811 __isl_take isl_schedule_tree *child)
813 tree = isl_schedule_tree_cow(tree);
814 if (!tree || !child)
815 goto error;
817 if (isl_schedule_tree_is_leaf(child)) {
818 isl_size n;
820 isl_schedule_tree_free(child);
821 if (!tree->children && pos == 0)
822 return tree;
823 n = isl_schedule_tree_n_children(tree);
824 if (n < 0)
825 return isl_schedule_tree_free(tree);
826 if (n != 1)
827 isl_die(isl_schedule_tree_get_ctx(tree),
828 isl_error_internal,
829 "can only replace single child by leaf",
830 goto error);
831 return isl_schedule_tree_reset_children(tree);
834 if (!tree->children && pos == 0)
835 tree->children =
836 isl_schedule_tree_list_from_schedule_tree(child);
837 else
838 tree->children = isl_schedule_tree_list_set_schedule_tree(
839 tree->children, pos, child);
841 if (!tree->children)
842 return isl_schedule_tree_free(tree);
843 tree = isl_schedule_tree_update_anchored(tree);
845 return tree;
846 error:
847 isl_schedule_tree_free(tree);
848 isl_schedule_tree_free(child);
849 return NULL;
852 /* Replace the (explicit) children of "tree" by "children"?
854 __isl_give isl_schedule_tree *isl_schedule_tree_set_children(
855 __isl_take isl_schedule_tree *tree,
856 __isl_take isl_schedule_tree_list *children)
858 tree = isl_schedule_tree_cow(tree);
859 if (!tree || !children)
860 goto error;
861 isl_schedule_tree_list_free(tree->children);
862 tree->children = children;
863 return tree;
864 error:
865 isl_schedule_tree_free(tree);
866 isl_schedule_tree_list_free(children);
867 return NULL;
870 /* Create a new band schedule tree referring to "band"
871 * with "tree" as single child.
873 __isl_give isl_schedule_tree *isl_schedule_tree_insert_band(
874 __isl_take isl_schedule_tree *tree, __isl_take isl_schedule_band *band)
876 isl_schedule_tree *res;
878 res = isl_schedule_tree_from_band(band);
879 return isl_schedule_tree_replace_child(res, 0, tree);
882 /* Create a new context schedule tree with the given context and
883 * with "tree" as single child.
885 __isl_give isl_schedule_tree *isl_schedule_tree_insert_context(
886 __isl_take isl_schedule_tree *tree, __isl_take isl_set *context)
888 isl_schedule_tree *res;
890 res = isl_schedule_tree_from_context(context);
891 return isl_schedule_tree_replace_child(res, 0, tree);
894 /* Create a new domain schedule tree with the given domain and
895 * with "tree" as single child.
897 __isl_give isl_schedule_tree *isl_schedule_tree_insert_domain(
898 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
900 isl_schedule_tree *res;
902 res = isl_schedule_tree_from_domain(domain);
903 return isl_schedule_tree_replace_child(res, 0, tree);
906 /* Create a new expansion schedule tree with the given contraction and
907 * expansion and with "tree" as single child.
909 __isl_give isl_schedule_tree *isl_schedule_tree_insert_expansion(
910 __isl_take isl_schedule_tree *tree,
911 __isl_take isl_union_pw_multi_aff *contraction,
912 __isl_take isl_union_map *expansion)
914 isl_schedule_tree *res;
916 res = isl_schedule_tree_from_expansion(contraction, expansion);
917 return isl_schedule_tree_replace_child(res, 0, tree);
920 /* Create a new extension schedule tree with the given extension and
921 * with "tree" as single child.
923 __isl_give isl_schedule_tree *isl_schedule_tree_insert_extension(
924 __isl_take isl_schedule_tree *tree, __isl_take isl_union_map *extension)
926 isl_schedule_tree *res;
928 res = isl_schedule_tree_from_extension(extension);
929 return isl_schedule_tree_replace_child(res, 0, tree);
932 /* Create a new filter schedule tree with the given filter and single child.
934 * If the root of "tree" is itself a filter node, then the two
935 * filter nodes are merged into one node.
937 __isl_give isl_schedule_tree *isl_schedule_tree_insert_filter(
938 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
940 isl_schedule_tree *res;
942 if (isl_schedule_tree_get_type(tree) == isl_schedule_node_filter) {
943 isl_union_set *tree_filter;
945 tree_filter = isl_schedule_tree_filter_get_filter(tree);
946 tree_filter = isl_union_set_intersect(tree_filter, filter);
947 tree = isl_schedule_tree_filter_set_filter(tree, tree_filter);
948 return tree;
951 res = isl_schedule_tree_from_filter(filter);
952 return isl_schedule_tree_replace_child(res, 0, tree);
955 /* Insert a filter node with filter set "filter"
956 * in each of the children of "tree".
958 __isl_give isl_schedule_tree *isl_schedule_tree_children_insert_filter(
959 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
961 int i;
962 isl_size n;
964 n = isl_schedule_tree_n_children(tree);
965 if (n < 0 || !filter)
966 goto error;
968 for (i = 0; i < n; ++i) {
969 isl_schedule_tree *child;
971 child = isl_schedule_tree_get_child(tree, i);
972 child = isl_schedule_tree_insert_filter(child,
973 isl_union_set_copy(filter));
974 tree = isl_schedule_tree_replace_child(tree, i, child);
977 isl_union_set_free(filter);
978 return tree;
979 error:
980 isl_union_set_free(filter);
981 isl_schedule_tree_free(tree);
982 return NULL;
985 /* Create a new guard schedule tree with the given guard and
986 * with "tree" as single child.
988 __isl_give isl_schedule_tree *isl_schedule_tree_insert_guard(
989 __isl_take isl_schedule_tree *tree, __isl_take isl_set *guard)
991 isl_schedule_tree *res;
993 res = isl_schedule_tree_from_guard(guard);
994 return isl_schedule_tree_replace_child(res, 0, tree);
997 /* Create a new mark schedule tree with the given mark identifier and
998 * single child.
1000 __isl_give isl_schedule_tree *isl_schedule_tree_insert_mark(
1001 __isl_take isl_schedule_tree *tree, __isl_take isl_id *mark)
1003 isl_schedule_tree *res;
1005 res = isl_schedule_tree_from_mark(mark);
1006 return isl_schedule_tree_replace_child(res, 0, tree);
1009 /* Return the number of members in the band tree root.
1011 isl_size isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree *tree)
1013 if (!tree)
1014 return isl_size_error;
1016 if (tree->type != isl_schedule_node_band)
1017 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1018 "not a band node", return isl_size_error);
1020 return isl_schedule_band_n_member(tree->band);
1023 /* Is the band member at position "pos" of the band tree root
1024 * marked coincident?
1026 isl_bool isl_schedule_tree_band_member_get_coincident(
1027 __isl_keep isl_schedule_tree *tree, int pos)
1029 if (!tree)
1030 return isl_bool_error;
1032 if (tree->type != isl_schedule_node_band)
1033 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1034 "not a band node", return isl_bool_error);
1036 return isl_schedule_band_member_get_coincident(tree->band, pos);
1039 /* Mark the given band member as being coincident or not
1040 * according to "coincident".
1042 __isl_give isl_schedule_tree *isl_schedule_tree_band_member_set_coincident(
1043 __isl_take isl_schedule_tree *tree, int pos, int coincident)
1045 if (!tree)
1046 return NULL;
1047 if (tree->type != isl_schedule_node_band)
1048 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1049 "not a band node", return isl_schedule_tree_free(tree));
1050 if (isl_schedule_tree_band_member_get_coincident(tree, pos) ==
1051 coincident)
1052 return tree;
1053 tree = isl_schedule_tree_cow(tree);
1054 if (!tree)
1055 return NULL;
1057 tree->band = isl_schedule_band_member_set_coincident(tree->band, pos,
1058 coincident);
1059 if (!tree->band)
1060 return isl_schedule_tree_free(tree);
1061 return tree;
1064 /* Is the band tree root marked permutable?
1066 isl_bool isl_schedule_tree_band_get_permutable(
1067 __isl_keep isl_schedule_tree *tree)
1069 if (!tree)
1070 return isl_bool_error;
1072 if (tree->type != isl_schedule_node_band)
1073 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1074 "not a band node", return isl_bool_error);
1076 return isl_schedule_band_get_permutable(tree->band);
1079 /* Mark the band tree root permutable or not according to "permutable"?
1081 __isl_give isl_schedule_tree *isl_schedule_tree_band_set_permutable(
1082 __isl_take isl_schedule_tree *tree, int permutable)
1084 if (!tree)
1085 return NULL;
1086 if (tree->type != isl_schedule_node_band)
1087 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1088 "not a band node", return isl_schedule_tree_free(tree));
1089 if (isl_schedule_tree_band_get_permutable(tree) == permutable)
1090 return tree;
1091 tree = isl_schedule_tree_cow(tree);
1092 if (!tree)
1093 return NULL;
1095 tree->band = isl_schedule_band_set_permutable(tree->band, permutable);
1096 if (!tree->band)
1097 return isl_schedule_tree_free(tree);
1098 return tree;
1101 /* Return the schedule space of the band tree root.
1103 __isl_give isl_space *isl_schedule_tree_band_get_space(
1104 __isl_keep isl_schedule_tree *tree)
1106 if (!tree)
1107 return NULL;
1109 if (tree->type != isl_schedule_node_band)
1110 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1111 "not a band node", return NULL);
1113 return isl_schedule_band_get_space(tree->band);
1116 /* Intersect the domain of the band schedule of the band tree root
1117 * with "domain".
1119 __isl_give isl_schedule_tree *isl_schedule_tree_band_intersect_domain(
1120 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
1122 if (!tree || !domain)
1123 goto error;
1125 if (tree->type != isl_schedule_node_band)
1126 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1127 "not a band node", goto error);
1129 tree->band = isl_schedule_band_intersect_domain(tree->band, domain);
1130 if (!tree->band)
1131 return isl_schedule_tree_free(tree);
1133 return tree;
1134 error:
1135 isl_schedule_tree_free(tree);
1136 isl_union_set_free(domain);
1137 return NULL;
1140 /* Return the schedule of the band tree root in isolation.
1142 __isl_give isl_multi_union_pw_aff *isl_schedule_tree_band_get_partial_schedule(
1143 __isl_keep isl_schedule_tree *tree)
1145 if (!tree)
1146 return NULL;
1148 if (tree->type != isl_schedule_node_band)
1149 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1150 "not a band node", return NULL);
1152 return isl_schedule_band_get_partial_schedule(tree->band);
1155 /* Replace the schedule of the band tree root by "schedule".
1157 __isl_give isl_schedule_tree *isl_schedule_tree_band_set_partial_schedule(
1158 __isl_take isl_schedule_tree *tree,
1159 __isl_take isl_multi_union_pw_aff *schedule)
1161 tree = isl_schedule_tree_cow(tree);
1162 if (!tree || !schedule)
1163 goto error;
1165 if (tree->type != isl_schedule_node_band)
1166 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1167 "not a band node", return NULL);
1168 tree->band = isl_schedule_band_set_partial_schedule(tree->band,
1169 schedule);
1171 return tree;
1172 error:
1173 isl_schedule_tree_free(tree);
1174 isl_multi_union_pw_aff_free(schedule);
1175 return NULL;
1178 /* Return the loop AST generation type for the band member
1179 * of the band tree root at position "pos".
1181 enum isl_ast_loop_type isl_schedule_tree_band_member_get_ast_loop_type(
1182 __isl_keep isl_schedule_tree *tree, int pos)
1184 if (!tree)
1185 return isl_ast_loop_error;
1187 if (tree->type != isl_schedule_node_band)
1188 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1189 "not a band node", return isl_ast_loop_error);
1191 return isl_schedule_band_member_get_ast_loop_type(tree->band, pos);
1194 /* Set the loop AST generation type for the band member of the band tree root
1195 * at position "pos" to "type".
1197 __isl_give isl_schedule_tree *isl_schedule_tree_band_member_set_ast_loop_type(
1198 __isl_take isl_schedule_tree *tree, int pos,
1199 enum isl_ast_loop_type type)
1201 tree = isl_schedule_tree_cow(tree);
1202 if (!tree)
1203 return NULL;
1205 if (tree->type != isl_schedule_node_band)
1206 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1207 "not a band node", return isl_schedule_tree_free(tree));
1209 tree->band = isl_schedule_band_member_set_ast_loop_type(tree->band,
1210 pos, type);
1211 if (!tree->band)
1212 return isl_schedule_tree_free(tree);
1214 return tree;
1217 /* Return the loop AST generation type for the band member
1218 * of the band tree root at position "pos" for the isolated part.
1220 enum isl_ast_loop_type isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1221 __isl_keep isl_schedule_tree *tree, int pos)
1223 if (!tree)
1224 return isl_ast_loop_error;
1226 if (tree->type != isl_schedule_node_band)
1227 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1228 "not a band node", return isl_ast_loop_error);
1230 return isl_schedule_band_member_get_isolate_ast_loop_type(tree->band,
1231 pos);
1234 /* Set the loop AST generation type for the band member of the band tree root
1235 * at position "pos" for the isolated part to "type".
1237 __isl_give isl_schedule_tree *
1238 isl_schedule_tree_band_member_set_isolate_ast_loop_type(
1239 __isl_take isl_schedule_tree *tree, int pos,
1240 enum isl_ast_loop_type type)
1242 tree = isl_schedule_tree_cow(tree);
1243 if (!tree)
1244 return NULL;
1246 if (tree->type != isl_schedule_node_band)
1247 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1248 "not a band node", return isl_schedule_tree_free(tree));
1250 tree->band = isl_schedule_band_member_set_isolate_ast_loop_type(
1251 tree->band, pos, type);
1252 if (!tree->band)
1253 return isl_schedule_tree_free(tree);
1255 return tree;
1258 /* Return the AST build options associated to the band tree root.
1260 __isl_give isl_union_set *isl_schedule_tree_band_get_ast_build_options(
1261 __isl_keep isl_schedule_tree *tree)
1263 if (!tree)
1264 return NULL;
1266 if (tree->type != isl_schedule_node_band)
1267 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1268 "not a band node", return NULL);
1270 return isl_schedule_band_get_ast_build_options(tree->band);
1273 /* Replace the AST build options associated to band tree root by "options".
1274 * Updated the anchored field if the anchoredness of the root node itself
1275 * changes.
1277 __isl_give isl_schedule_tree *isl_schedule_tree_band_set_ast_build_options(
1278 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *options)
1280 int was_anchored;
1282 tree = isl_schedule_tree_cow(tree);
1283 if (!tree || !options)
1284 goto error;
1286 if (tree->type != isl_schedule_node_band)
1287 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1288 "not a band node", goto error);
1290 was_anchored = isl_schedule_tree_is_anchored(tree);
1291 tree->band = isl_schedule_band_set_ast_build_options(tree->band,
1292 options);
1293 if (!tree->band)
1294 return isl_schedule_tree_free(tree);
1295 if (isl_schedule_tree_is_anchored(tree) != was_anchored)
1296 tree = isl_schedule_tree_update_anchored(tree);
1298 return tree;
1299 error:
1300 isl_schedule_tree_free(tree);
1301 isl_union_set_free(options);
1302 return NULL;
1305 /* Return the "isolate" option associated to the band tree root of "tree",
1306 * which is assumed to appear at schedule depth "depth".
1308 __isl_give isl_set *isl_schedule_tree_band_get_ast_isolate_option(
1309 __isl_keep isl_schedule_tree *tree, int depth)
1311 if (!tree)
1312 return NULL;
1314 if (tree->type != isl_schedule_node_band)
1315 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1316 "not a band node", return NULL);
1318 return isl_schedule_band_get_ast_isolate_option(tree->band, depth);
1321 /* Return the context of the context tree root.
1323 __isl_give isl_set *isl_schedule_tree_context_get_context(
1324 __isl_keep isl_schedule_tree *tree)
1326 if (!tree)
1327 return NULL;
1329 if (tree->type != isl_schedule_node_context)
1330 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1331 "not a context node", return NULL);
1333 return isl_set_copy(tree->context);
1336 /* Return the domain of the domain tree root.
1338 __isl_give isl_union_set *isl_schedule_tree_domain_get_domain(
1339 __isl_keep isl_schedule_tree *tree)
1341 if (!tree)
1342 return NULL;
1344 if (tree->type != isl_schedule_node_domain)
1345 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1346 "not a domain node", return NULL);
1348 return isl_union_set_copy(tree->domain);
1351 /* Replace the domain of domain tree root "tree" by "domain".
1353 __isl_give isl_schedule_tree *isl_schedule_tree_domain_set_domain(
1354 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
1356 tree = isl_schedule_tree_cow(tree);
1357 if (!tree || !domain)
1358 goto error;
1360 if (tree->type != isl_schedule_node_domain)
1361 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1362 "not a domain node", goto error);
1364 isl_union_set_free(tree->domain);
1365 tree->domain = domain;
1367 return tree;
1368 error:
1369 isl_schedule_tree_free(tree);
1370 isl_union_set_free(domain);
1371 return NULL;
1374 /* Return the contraction of the expansion tree root.
1376 __isl_give isl_union_pw_multi_aff *isl_schedule_tree_expansion_get_contraction(
1377 __isl_keep isl_schedule_tree *tree)
1379 if (!tree)
1380 return NULL;
1382 if (tree->type != isl_schedule_node_expansion)
1383 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1384 "not an expansion node", return NULL);
1386 return isl_union_pw_multi_aff_copy(tree->contraction);
1389 /* Return the expansion of the expansion tree root.
1391 __isl_give isl_union_map *isl_schedule_tree_expansion_get_expansion(
1392 __isl_keep isl_schedule_tree *tree)
1394 if (!tree)
1395 return NULL;
1397 if (tree->type != isl_schedule_node_expansion)
1398 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1399 "not an expansion node", return NULL);
1401 return isl_union_map_copy(tree->expansion);
1404 /* Replace the contraction and the expansion of the expansion tree root "tree"
1405 * by "contraction" and "expansion".
1407 __isl_give isl_schedule_tree *
1408 isl_schedule_tree_expansion_set_contraction_and_expansion(
1409 __isl_take isl_schedule_tree *tree,
1410 __isl_take isl_union_pw_multi_aff *contraction,
1411 __isl_take isl_union_map *expansion)
1413 tree = isl_schedule_tree_cow(tree);
1414 if (!tree || !contraction || !expansion)
1415 goto error;
1417 if (tree->type != isl_schedule_node_expansion)
1418 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1419 "not an expansion node", return NULL);
1421 isl_union_pw_multi_aff_free(tree->contraction);
1422 tree->contraction = contraction;
1423 isl_union_map_free(tree->expansion);
1424 tree->expansion = expansion;
1426 return tree;
1427 error:
1428 isl_schedule_tree_free(tree);
1429 isl_union_pw_multi_aff_free(contraction);
1430 isl_union_map_free(expansion);
1431 return NULL;
1434 /* Return the extension of the extension tree root.
1436 __isl_give isl_union_map *isl_schedule_tree_extension_get_extension(
1437 __isl_take isl_schedule_tree *tree)
1439 if (!tree)
1440 return NULL;
1442 if (tree->type != isl_schedule_node_extension)
1443 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1444 "not an extension node", return NULL);
1446 return isl_union_map_copy(tree->extension);
1449 /* Replace the extension of extension tree root "tree" by "extension".
1451 __isl_give isl_schedule_tree *isl_schedule_tree_extension_set_extension(
1452 __isl_take isl_schedule_tree *tree, __isl_take isl_union_map *extension)
1454 tree = isl_schedule_tree_cow(tree);
1455 if (!tree || !extension)
1456 goto error;
1458 if (tree->type != isl_schedule_node_extension)
1459 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1460 "not an extension node", return NULL);
1461 isl_union_map_free(tree->extension);
1462 tree->extension = extension;
1464 return tree;
1465 error:
1466 isl_schedule_tree_free(tree);
1467 isl_union_map_free(extension);
1468 return NULL;
1471 /* Return the filter of the filter tree root.
1473 __isl_give isl_union_set *isl_schedule_tree_filter_get_filter(
1474 __isl_keep isl_schedule_tree *tree)
1476 if (!tree)
1477 return NULL;
1479 if (tree->type != isl_schedule_node_filter)
1480 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1481 "not a filter node", return NULL);
1483 return isl_union_set_copy(tree->filter);
1486 /* Replace the filter of the filter tree root by "filter".
1488 __isl_give isl_schedule_tree *isl_schedule_tree_filter_set_filter(
1489 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
1491 tree = isl_schedule_tree_cow(tree);
1492 if (!tree || !filter)
1493 goto error;
1495 if (tree->type != isl_schedule_node_filter)
1496 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1497 "not a filter node", return NULL);
1499 isl_union_set_free(tree->filter);
1500 tree->filter = filter;
1502 return tree;
1503 error:
1504 isl_schedule_tree_free(tree);
1505 isl_union_set_free(filter);
1506 return NULL;
1509 /* Return the guard of the guard tree root.
1511 __isl_give isl_set *isl_schedule_tree_guard_get_guard(
1512 __isl_take isl_schedule_tree *tree)
1514 if (!tree)
1515 return NULL;
1517 if (tree->type != isl_schedule_node_guard)
1518 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1519 "not a guard node", return NULL);
1521 return isl_set_copy(tree->guard);
1524 /* Return the mark identifier of the mark tree root "tree".
1526 __isl_give isl_id *isl_schedule_tree_mark_get_id(
1527 __isl_keep isl_schedule_tree *tree)
1529 if (!tree)
1530 return NULL;
1532 if (tree->type != isl_schedule_node_mark)
1533 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1534 "not a mark node", return NULL);
1536 return isl_id_copy(tree->mark);
1539 /* Set dim to the range dimension of "map" and abort the search.
1541 static isl_stat set_range_dim(__isl_take isl_map *map, void *user)
1543 isl_size *dim = user;
1545 *dim = isl_map_dim(map, isl_dim_out);
1546 isl_map_free(map);
1548 return isl_stat_error;
1551 /* Return the dimension of the range of "umap".
1552 * "umap" is assumed not to be empty and
1553 * all maps inside "umap" are assumed to have the same range.
1555 * We extract the range dimension from the first map in "umap".
1557 static isl_size range_dim(__isl_keep isl_union_map *umap)
1559 isl_size dim = isl_size_error;
1560 isl_size n;
1562 n = isl_union_map_n_map(umap);
1563 if (n < 0)
1564 return isl_size_error;
1565 if (n == 0)
1566 isl_die(isl_union_map_get_ctx(umap), isl_error_internal,
1567 "unexpected empty input", return isl_size_error);
1569 isl_union_map_foreach_map(umap, &set_range_dim, &dim);
1571 return dim;
1574 /* Append an "extra" number of zeros to the range of "umap" and
1575 * return the result.
1577 static __isl_give isl_union_map *append_range(__isl_take isl_union_map *umap,
1578 int extra)
1580 isl_union_set *dom;
1581 isl_space *space;
1582 isl_multi_val *mv;
1583 isl_union_pw_multi_aff *suffix;
1584 isl_union_map *universe;
1585 isl_union_map *suffix_umap;
1587 universe = isl_union_map_universe(isl_union_map_copy(umap));
1588 dom = isl_union_map_domain(universe);
1589 space = isl_union_set_get_space(dom);
1590 space = isl_space_set_from_params(space);
1591 space = isl_space_add_dims(space, isl_dim_set, extra);
1592 mv = isl_multi_val_zero(space);
1594 suffix = isl_union_pw_multi_aff_multi_val_on_domain(dom, mv);
1595 suffix_umap = isl_union_map_from_union_pw_multi_aff(suffix);
1596 umap = isl_union_map_flat_range_product(umap, suffix_umap);
1598 return umap;
1601 /* Should we skip the root of "tree" while looking for the first
1602 * descendant with schedule information?
1603 * That is, is it impossible to derive any information about
1604 * the iteration domain from this node?
1606 * We do not want to skip leaf or error nodes because there is
1607 * no point in looking any deeper from these nodes.
1608 * We can only extract partial iteration domain information
1609 * from an extension node, but extension nodes are not supported
1610 * by the caller and it will error out on them.
1612 static isl_bool domain_less(__isl_keep isl_schedule_tree *tree)
1614 enum isl_schedule_node_type type;
1615 isl_size n;
1617 type = isl_schedule_tree_get_type(tree);
1618 switch (type) {
1619 case isl_schedule_node_band:
1620 n = isl_schedule_tree_band_n_member(tree);
1621 return n < 0 ? isl_bool_error : isl_bool_ok(n == 0);
1622 case isl_schedule_node_context:
1623 case isl_schedule_node_guard:
1624 case isl_schedule_node_mark:
1625 return isl_bool_true;
1626 case isl_schedule_node_leaf:
1627 case isl_schedule_node_error:
1628 case isl_schedule_node_domain:
1629 case isl_schedule_node_expansion:
1630 case isl_schedule_node_extension:
1631 case isl_schedule_node_filter:
1632 case isl_schedule_node_set:
1633 case isl_schedule_node_sequence:
1634 return isl_bool_false;
1637 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1638 "unhandled case", return isl_bool_error);
1641 /* Move down to the first descendant of "tree" that contains any schedule
1642 * information or return "leaf" if there is no such descendant.
1644 __isl_give isl_schedule_tree *isl_schedule_tree_first_schedule_descendant(
1645 __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_tree *leaf)
1647 isl_bool down;
1649 while ((down = domain_less(tree)) == isl_bool_true) {
1650 if (!isl_schedule_tree_has_children(tree)) {
1651 isl_schedule_tree_free(tree);
1652 return isl_schedule_tree_copy(leaf);
1654 tree = isl_schedule_tree_child(tree, 0);
1657 if (down < 0)
1658 return isl_schedule_tree_free(tree);
1660 return tree;
1663 static __isl_give isl_union_map *subtree_schedule_extend(
1664 __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer);
1666 /* Extend the schedule map "outer" with the subtree schedule
1667 * of the (single) child of "tree", if any.
1669 * If "tree" does not have any descendants (apart from those that
1670 * do not carry any schedule information), then we simply return "outer".
1671 * Otherwise, we extend the schedule map "outer" with the subtree schedule
1672 * of the single child.
1674 static __isl_give isl_union_map *subtree_schedule_extend_child(
1675 __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1677 isl_schedule_tree *child;
1678 isl_union_map *res;
1680 if (!tree)
1681 return isl_union_map_free(outer);
1682 if (!isl_schedule_tree_has_children(tree))
1683 return outer;
1684 child = isl_schedule_tree_get_child(tree, 0);
1685 if (!child)
1686 return isl_union_map_free(outer);
1687 res = subtree_schedule_extend(child, outer);
1688 isl_schedule_tree_free(child);
1689 return res;
1692 /* Extract the parameter space from one of the children of "tree",
1693 * which are assumed to be filters.
1695 static __isl_give isl_space *extract_space_from_filter_child(
1696 __isl_keep isl_schedule_tree *tree)
1698 isl_space *space;
1699 isl_union_set *dom;
1700 isl_schedule_tree *child;
1702 child = isl_schedule_tree_list_get_schedule_tree(tree->children, 0);
1703 dom = isl_schedule_tree_filter_get_filter(child);
1704 space = isl_union_set_get_space(dom);
1705 isl_union_set_free(dom);
1706 isl_schedule_tree_free(child);
1708 return space;
1711 /* Extend the schedule map "outer" with the subtree schedule
1712 * of a set or sequence node.
1714 * The schedule for the set or sequence node itself is composed of
1715 * pieces of the form
1717 * filter -> []
1719 * or
1721 * filter -> [index]
1723 * The first form is used if there is only a single child or
1724 * if the current node is a set node and the schedule_separate_components
1725 * option is not set.
1727 * Each of the pieces above is extended with the subtree schedule of
1728 * the child of the corresponding filter, if any, padded with zeros
1729 * to ensure that all pieces have the same range dimension.
1731 static __isl_give isl_union_map *subtree_schedule_extend_from_children(
1732 __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1734 int i;
1735 isl_size n;
1736 isl_size dim;
1737 int separate;
1738 isl_ctx *ctx;
1739 isl_val *v = NULL;
1740 isl_multi_val *mv;
1741 isl_space *space;
1742 isl_union_map *umap;
1744 n = isl_schedule_tree_n_children(tree);
1745 if (n < 0)
1746 return isl_union_map_free(outer);
1747 if (n == 0)
1748 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1749 "missing children", return isl_union_map_free(outer));
1751 ctx = isl_schedule_tree_get_ctx(tree);
1752 separate = n > 1 && (tree->type == isl_schedule_node_sequence ||
1753 isl_options_get_schedule_separate_components(ctx));
1755 space = isl_space_params_alloc(ctx, 0);
1757 umap = isl_union_map_empty(isl_space_copy(space));
1758 space = isl_space_set_from_params(space);
1759 if (separate) {
1760 space = isl_space_add_dims(space, isl_dim_set, 1);
1761 v = isl_val_zero(ctx);
1763 mv = isl_multi_val_zero(space);
1765 dim = isl_multi_val_dim(mv, isl_dim_set);
1766 if (dim < 0)
1767 umap = isl_union_map_free(umap);
1768 for (i = 0; i < n; ++i) {
1769 isl_multi_val *mv_copy;
1770 isl_union_pw_multi_aff *upma;
1771 isl_union_map *umap_i;
1772 isl_union_set *dom;
1773 isl_schedule_tree *child;
1774 isl_size dim_i;
1775 isl_bool empty;
1777 child = isl_schedule_tree_list_get_schedule_tree(
1778 tree->children, i);
1779 dom = isl_schedule_tree_filter_get_filter(child);
1781 if (separate) {
1782 mv = isl_multi_val_set_val(mv, 0, isl_val_copy(v));
1783 v = isl_val_add_ui(v, 1);
1785 mv_copy = isl_multi_val_copy(mv);
1786 space = isl_union_set_get_space(dom);
1787 mv_copy = isl_multi_val_align_params(mv_copy, space);
1788 upma = isl_union_pw_multi_aff_multi_val_on_domain(dom, mv_copy);
1789 umap_i = isl_union_map_from_union_pw_multi_aff(upma);
1790 umap_i = isl_union_map_flat_range_product(
1791 isl_union_map_copy(outer), umap_i);
1792 umap_i = subtree_schedule_extend_child(child, umap_i);
1793 isl_schedule_tree_free(child);
1795 empty = isl_union_map_is_empty(umap_i);
1796 if (empty < 0)
1797 umap_i = isl_union_map_free(umap_i);
1798 else if (empty) {
1799 isl_union_map_free(umap_i);
1800 continue;
1803 dim_i = range_dim(umap_i);
1804 if (dim_i < 0) {
1805 umap = isl_union_map_free(umap);
1806 } else if (dim < dim_i) {
1807 umap = append_range(umap, dim_i - dim);
1808 dim = dim_i;
1809 } else if (dim_i < dim) {
1810 umap_i = append_range(umap_i, dim - dim_i);
1812 umap = isl_union_map_union(umap, umap_i);
1815 isl_val_free(v);
1816 isl_multi_val_free(mv);
1817 isl_union_map_free(outer);
1819 return umap;
1822 /* Extend the schedule map "outer" with the subtree schedule of "tree".
1824 * If the root of the tree is a set or a sequence, then we extend
1825 * the schedule map in subtree_schedule_extend_from_children.
1826 * Otherwise, we extend the schedule map with the partial schedule
1827 * corresponding to the root of the tree and then continue with
1828 * the single child of this root.
1829 * In the special case of an expansion, the schedule map is "extended"
1830 * by applying the expansion to the domain of the schedule map.
1832 static __isl_give isl_union_map *subtree_schedule_extend(
1833 __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1835 isl_multi_union_pw_aff *mupa;
1836 isl_union_map *umap;
1837 isl_union_set *domain;
1838 isl_size n;
1840 if (!tree)
1841 return NULL;
1843 switch (tree->type) {
1844 case isl_schedule_node_error:
1845 return isl_union_map_free(outer);
1846 case isl_schedule_node_extension:
1847 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1848 "cannot construct subtree schedule of tree "
1849 "with extension nodes",
1850 return isl_union_map_free(outer));
1851 case isl_schedule_node_context:
1852 case isl_schedule_node_guard:
1853 case isl_schedule_node_mark:
1854 return subtree_schedule_extend_child(tree, outer);
1855 case isl_schedule_node_band:
1856 n = isl_schedule_tree_band_n_member(tree);
1857 if (n < 0)
1858 return isl_union_map_free(outer);
1859 if (n == 0)
1860 return subtree_schedule_extend_child(tree, outer);
1861 mupa = isl_schedule_band_get_partial_schedule(tree->band);
1862 umap = isl_union_map_from_multi_union_pw_aff(mupa);
1863 outer = isl_union_map_flat_range_product(outer, umap);
1864 umap = subtree_schedule_extend_child(tree, outer);
1865 break;
1866 case isl_schedule_node_domain:
1867 domain = isl_schedule_tree_domain_get_domain(tree);
1868 umap = isl_union_map_from_domain(domain);
1869 outer = isl_union_map_flat_range_product(outer, umap);
1870 umap = subtree_schedule_extend_child(tree, outer);
1871 break;
1872 case isl_schedule_node_expansion:
1873 umap = isl_schedule_tree_expansion_get_expansion(tree);
1874 outer = isl_union_map_apply_domain(outer, umap);
1875 umap = subtree_schedule_extend_child(tree, outer);
1876 break;
1877 case isl_schedule_node_filter:
1878 domain = isl_schedule_tree_filter_get_filter(tree);
1879 umap = isl_union_map_from_domain(domain);
1880 outer = isl_union_map_flat_range_product(outer, umap);
1881 umap = subtree_schedule_extend_child(tree, outer);
1882 break;
1883 case isl_schedule_node_leaf:
1884 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1885 "leaf node should be handled by caller", return NULL);
1886 case isl_schedule_node_set:
1887 case isl_schedule_node_sequence:
1888 umap = subtree_schedule_extend_from_children(tree, outer);
1889 break;
1892 return umap;
1895 static __isl_give isl_union_set *initial_domain(
1896 __isl_keep isl_schedule_tree *tree);
1898 /* Extract a universe domain from the children of the tree root "tree",
1899 * which is a set or sequence, meaning that its children are filters.
1900 * In particular, return the union of the universes of the filters.
1902 static __isl_give isl_union_set *initial_domain_from_children(
1903 __isl_keep isl_schedule_tree *tree)
1905 int i;
1906 isl_size n;
1907 isl_space *space;
1908 isl_union_set *domain;
1910 n = isl_schedule_tree_n_children(tree);
1911 if (n < 0)
1912 return NULL;
1913 if (n == 0)
1914 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1915 "missing children", return NULL);
1917 space = extract_space_from_filter_child(tree);
1918 domain = isl_union_set_empty(space);
1920 for (i = 0; i < n; ++i) {
1921 isl_schedule_tree *child;
1922 isl_union_set *domain_i;
1924 child = isl_schedule_tree_get_child(tree, i);
1925 domain_i = initial_domain(child);
1926 domain = isl_union_set_union(domain, domain_i);
1927 isl_schedule_tree_free(child);
1930 return domain;
1933 /* Extract a universe domain from the tree root "tree".
1934 * The caller is responsible for making sure that this node
1935 * would not be skipped by isl_schedule_tree_first_schedule_descendant
1936 * and that it is not a leaf node.
1938 static __isl_give isl_union_set *initial_domain(
1939 __isl_keep isl_schedule_tree *tree)
1941 isl_multi_union_pw_aff *mupa;
1942 isl_union_set *domain;
1943 isl_union_map *exp;
1944 isl_size n;
1946 if (!tree)
1947 return NULL;
1949 switch (tree->type) {
1950 case isl_schedule_node_error:
1951 return NULL;
1952 case isl_schedule_node_context:
1953 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1954 "context node should be handled by caller",
1955 return NULL);
1956 case isl_schedule_node_guard:
1957 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1958 "guard node should be handled by caller",
1959 return NULL);
1960 case isl_schedule_node_mark:
1961 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1962 "mark node should be handled by caller",
1963 return NULL);
1964 case isl_schedule_node_extension:
1965 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1966 "cannot construct subtree schedule of tree "
1967 "with extension nodes", return NULL);
1968 case isl_schedule_node_band:
1969 n = isl_schedule_tree_band_n_member(tree);
1970 if (n < 0)
1971 return NULL;
1972 if (n == 0)
1973 isl_die(isl_schedule_tree_get_ctx(tree),
1974 isl_error_internal,
1975 "0D band should be handled by caller",
1976 return NULL);
1977 mupa = isl_schedule_band_get_partial_schedule(tree->band);
1978 domain = isl_multi_union_pw_aff_domain(mupa);
1979 domain = isl_union_set_universe(domain);
1980 break;
1981 case isl_schedule_node_domain:
1982 domain = isl_schedule_tree_domain_get_domain(tree);
1983 domain = isl_union_set_universe(domain);
1984 break;
1985 case isl_schedule_node_expansion:
1986 exp = isl_schedule_tree_expansion_get_expansion(tree);
1987 exp = isl_union_map_universe(exp);
1988 domain = isl_union_map_domain(exp);
1989 break;
1990 case isl_schedule_node_filter:
1991 domain = isl_schedule_tree_filter_get_filter(tree);
1992 domain = isl_union_set_universe(domain);
1993 break;
1994 case isl_schedule_node_leaf:
1995 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1996 "leaf node should be handled by caller", return NULL);
1997 case isl_schedule_node_set:
1998 case isl_schedule_node_sequence:
1999 domain = initial_domain_from_children(tree);
2000 break;
2003 return domain;
2006 /* Return the subtree schedule of a node that contains some schedule
2007 * information, i.e., a node that would not be skipped by
2008 * isl_schedule_tree_first_schedule_descendant and that is not a leaf.
2010 * If the tree contains any expansions, then the returned subtree
2011 * schedule is formulated in terms of the expanded domains.
2012 * The tree is not allowed to contain any extension nodes.
2014 * We start with an initial zero-dimensional subtree schedule based
2015 * on the domain information in the root node and then extend it
2016 * based on the schedule information in the root node and its descendants.
2018 __isl_give isl_union_map *isl_schedule_tree_get_subtree_schedule_union_map(
2019 __isl_keep isl_schedule_tree *tree)
2021 isl_union_set *domain;
2022 isl_union_map *umap;
2024 domain = initial_domain(tree);
2025 umap = isl_union_map_from_domain(domain);
2026 return subtree_schedule_extend(tree, umap);
2029 /* Multiply the partial schedule of the band root node of "tree"
2030 * with the factors in "mv".
2032 __isl_give isl_schedule_tree *isl_schedule_tree_band_scale(
2033 __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
2035 if (!tree || !mv)
2036 goto error;
2037 if (tree->type != isl_schedule_node_band)
2038 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2039 "not a band node", goto error);
2041 tree = isl_schedule_tree_cow(tree);
2042 if (!tree)
2043 goto error;
2045 tree->band = isl_schedule_band_scale(tree->band, mv);
2046 if (!tree->band)
2047 return isl_schedule_tree_free(tree);
2049 return tree;
2050 error:
2051 isl_schedule_tree_free(tree);
2052 isl_multi_val_free(mv);
2053 return NULL;
2056 /* Divide the partial schedule of the band root node of "tree"
2057 * by the factors in "mv".
2059 __isl_give isl_schedule_tree *isl_schedule_tree_band_scale_down(
2060 __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
2062 if (!tree || !mv)
2063 goto error;
2064 if (tree->type != isl_schedule_node_band)
2065 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2066 "not a band node", goto error);
2068 tree = isl_schedule_tree_cow(tree);
2069 if (!tree)
2070 goto error;
2072 tree->band = isl_schedule_band_scale_down(tree->band, mv);
2073 if (!tree->band)
2074 return isl_schedule_tree_free(tree);
2076 return tree;
2077 error:
2078 isl_schedule_tree_free(tree);
2079 isl_multi_val_free(mv);
2080 return NULL;
2083 /* Reduce the partial schedule of the band root node of "tree"
2084 * modulo the factors in "mv".
2086 __isl_give isl_schedule_tree *isl_schedule_tree_band_mod(
2087 __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
2089 if (!tree || !mv)
2090 goto error;
2091 if (tree->type != isl_schedule_node_band)
2092 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2093 "not a band node", goto error);
2095 tree = isl_schedule_tree_cow(tree);
2096 if (!tree)
2097 goto error;
2099 tree->band = isl_schedule_band_mod(tree->band, mv);
2100 if (!tree->band)
2101 return isl_schedule_tree_free(tree);
2103 return tree;
2104 error:
2105 isl_schedule_tree_free(tree);
2106 isl_multi_val_free(mv);
2107 return NULL;
2110 /* Shift the partial schedule of the band root node of "tree" by "shift".
2112 __isl_give isl_schedule_tree *isl_schedule_tree_band_shift(
2113 __isl_take isl_schedule_tree *tree,
2114 __isl_take isl_multi_union_pw_aff *shift)
2116 if (!tree || !shift)
2117 goto error;
2118 if (tree->type != isl_schedule_node_band)
2119 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2120 "not a band node", goto error);
2122 tree = isl_schedule_tree_cow(tree);
2123 if (!tree)
2124 goto error;
2126 tree->band = isl_schedule_band_shift(tree->band, shift);
2127 if (!tree->band)
2128 return isl_schedule_tree_free(tree);
2130 return tree;
2131 error:
2132 isl_schedule_tree_free(tree);
2133 isl_multi_union_pw_aff_free(shift);
2134 return NULL;
2137 /* Given two trees with sequence roots, replace the child at position
2138 * "pos" of "tree" with the children of "child".
2140 __isl_give isl_schedule_tree *isl_schedule_tree_sequence_splice(
2141 __isl_take isl_schedule_tree *tree, int pos,
2142 __isl_take isl_schedule_tree *child)
2144 isl_size n;
2145 isl_schedule_tree_list *list1, *list2;
2147 tree = isl_schedule_tree_cow(tree);
2148 if (!tree || !child)
2149 goto error;
2150 if (isl_schedule_tree_get_type(tree) != isl_schedule_node_sequence)
2151 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2152 "not a sequence node", goto error);
2153 n = isl_schedule_tree_n_children(tree);
2154 if (n < 0)
2155 goto error;
2156 if (pos < 0 || pos >= n)
2157 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2158 "position out of bounds", goto error);
2159 if (isl_schedule_tree_get_type(child) != isl_schedule_node_sequence)
2160 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2161 "not a sequence node", goto error);
2163 list1 = isl_schedule_tree_list_copy(tree->children);
2164 list1 = isl_schedule_tree_list_drop(list1, pos, n - pos);
2165 list2 = isl_schedule_tree_list_copy(tree->children);
2166 list2 = isl_schedule_tree_list_drop(list2, 0, pos + 1);
2167 list1 = isl_schedule_tree_list_concat(list1,
2168 isl_schedule_tree_list_copy(child->children));
2169 list1 = isl_schedule_tree_list_concat(list1, list2);
2171 isl_schedule_tree_free(tree);
2172 isl_schedule_tree_free(child);
2173 return isl_schedule_tree_from_children(isl_schedule_node_sequence,
2174 list1);
2175 error:
2176 isl_schedule_tree_free(tree);
2177 isl_schedule_tree_free(child);
2178 return NULL;
2181 /* Tile the band root node of "tree" with tile sizes "sizes".
2183 * We duplicate the band node, change the schedule of one of them
2184 * to the tile schedule and the other to the point schedule and then
2185 * attach the point band as a child to the tile band.
2187 __isl_give isl_schedule_tree *isl_schedule_tree_band_tile(
2188 __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *sizes)
2190 isl_schedule_tree *child = NULL;
2192 if (!tree || !sizes)
2193 goto error;
2194 if (tree->type != isl_schedule_node_band)
2195 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2196 "not a band node", goto error);
2198 child = isl_schedule_tree_copy(tree);
2199 tree = isl_schedule_tree_cow(tree);
2200 child = isl_schedule_tree_cow(child);
2201 if (!tree || !child)
2202 goto error;
2204 tree->band = isl_schedule_band_tile(tree->band,
2205 isl_multi_val_copy(sizes));
2206 if (!tree->band)
2207 goto error;
2208 child->band = isl_schedule_band_point(child->band, tree->band, sizes);
2209 if (!child->band)
2210 child = isl_schedule_tree_free(child);
2212 tree = isl_schedule_tree_replace_child(tree, 0, child);
2214 return tree;
2215 error:
2216 isl_schedule_tree_free(child);
2217 isl_schedule_tree_free(tree);
2218 isl_multi_val_free(sizes);
2219 return NULL;
2222 /* Given an isolate AST generation option "isolate" for a band of size pos + n,
2223 * return the corresponding option for a band covering the first "pos"
2224 * members.
2226 * The input isolate option is of the form
2228 * isolate[[flattened outer bands] -> [pos; n]]
2230 * The output isolate option is of the form
2232 * isolate[[flattened outer bands] -> [pos]]
2234 static __isl_give isl_set *isolate_initial(__isl_keep isl_set *isolate,
2235 int pos, int n)
2237 isl_id *id;
2238 isl_map *map;
2240 isolate = isl_set_copy(isolate);
2241 id = isl_set_get_tuple_id(isolate);
2242 map = isl_set_unwrap(isolate);
2243 map = isl_map_project_out(map, isl_dim_out, pos, n);
2244 isolate = isl_map_wrap(map);
2245 isolate = isl_set_set_tuple_id(isolate, id);
2247 return isolate;
2250 /* Given an isolate AST generation option "isolate" for a band of size pos + n,
2251 * return the corresponding option for a band covering the final "n"
2252 * members within a band covering the first "pos" members.
2254 * The input isolate option is of the form
2256 * isolate[[flattened outer bands] -> [pos; n]]
2258 * The output isolate option is of the form
2260 * isolate[[flattened outer bands; pos] -> [n]]
2263 * The range is first split into
2265 * isolate[[flattened outer bands] -> [[pos] -> [n]]]
2267 * and then the first pos members are moved to the domain
2269 * isolate[[[flattened outer bands] -> [pos]] -> [n]]
2271 * after which the domain is flattened to obtain the desired output.
2273 static __isl_give isl_set *isolate_final(__isl_keep isl_set *isolate,
2274 int pos, int n)
2276 isl_id *id;
2277 isl_space *space;
2278 isl_multi_aff *ma1, *ma2;
2279 isl_map *map;
2281 isolate = isl_set_copy(isolate);
2282 id = isl_set_get_tuple_id(isolate);
2283 map = isl_set_unwrap(isolate);
2284 space = isl_space_range(isl_map_get_space(map));
2285 ma1 = isl_multi_aff_project_out_map(isl_space_copy(space),
2286 isl_dim_set, pos, n);
2287 ma2 = isl_multi_aff_project_out_map(space, isl_dim_set, 0, pos);
2288 ma1 = isl_multi_aff_range_product(ma1, ma2);
2289 map = isl_map_apply_range(map, isl_map_from_multi_aff(ma1));
2290 map = isl_map_uncurry(map);
2291 map = isl_map_flatten_domain(map);
2292 isolate = isl_map_wrap(map);
2293 isolate = isl_set_set_tuple_id(isolate, id);
2295 return isolate;
2298 /* Split the band root node of "tree" into two nested band nodes,
2299 * one with the first "pos" dimensions and
2300 * one with the remaining dimensions.
2301 * The tree is itself positioned at schedule depth "depth".
2303 * The loop AST generation type options and the isolate option
2304 * are split over the two band nodes.
2306 __isl_give isl_schedule_tree *isl_schedule_tree_band_split(
2307 __isl_take isl_schedule_tree *tree, int pos, int depth)
2309 isl_size n;
2310 isl_set *isolate, *tree_isolate, *child_isolate;
2311 isl_schedule_tree *child;
2313 if (!tree)
2314 return NULL;
2315 if (tree->type != isl_schedule_node_band)
2316 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2317 "not a band node", return isl_schedule_tree_free(tree));
2319 n = isl_schedule_tree_band_n_member(tree);
2320 if (n < 0)
2321 return isl_schedule_tree_free(tree);
2322 if (pos < 0 || pos > n)
2323 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2324 "position out of bounds",
2325 return isl_schedule_tree_free(tree));
2327 child = isl_schedule_tree_copy(tree);
2328 tree = isl_schedule_tree_cow(tree);
2329 child = isl_schedule_tree_cow(child);
2330 if (!tree || !child)
2331 goto error;
2333 isolate = isl_schedule_tree_band_get_ast_isolate_option(tree, depth);
2334 tree_isolate = isolate_initial(isolate, pos, n - pos);
2335 child_isolate = isolate_final(isolate, pos, n - pos);
2336 child->band = isl_schedule_band_drop(child->band, 0, pos);
2337 child->band = isl_schedule_band_replace_ast_build_option(child->band,
2338 isl_set_copy(isolate), child_isolate);
2339 tree->band = isl_schedule_band_drop(tree->band, pos, n - pos);
2340 tree->band = isl_schedule_band_replace_ast_build_option(tree->band,
2341 isl_set_copy(isolate), tree_isolate);
2342 isl_set_free(isolate);
2343 if (!child->band || !tree->band)
2344 goto error;
2346 tree = isl_schedule_tree_replace_child(tree, 0, child);
2348 return tree;
2349 error:
2350 isl_schedule_tree_free(child);
2351 isl_schedule_tree_free(tree);
2352 return NULL;
2355 /* Attach "tree2" at each of the leaves of "tree1".
2357 * If "tree1" does not have any explicit children, then make "tree2"
2358 * its single child. Otherwise, attach "tree2" to the leaves of
2359 * each of the children of "tree1".
2361 __isl_give isl_schedule_tree *isl_schedule_tree_append_to_leaves(
2362 __isl_take isl_schedule_tree *tree1,
2363 __isl_take isl_schedule_tree *tree2)
2365 int i;
2366 isl_size n;
2368 n = isl_schedule_tree_n_children(tree1);
2369 if (n < 0 || !tree2)
2370 goto error;
2371 if (n == 0) {
2372 isl_schedule_tree_list *list;
2373 list = isl_schedule_tree_list_from_schedule_tree(tree2);
2374 tree1 = isl_schedule_tree_set_children(tree1, list);
2375 return tree1;
2377 for (i = 0; i < n; ++i) {
2378 isl_schedule_tree *child;
2380 child = isl_schedule_tree_get_child(tree1, i);
2381 child = isl_schedule_tree_append_to_leaves(child,
2382 isl_schedule_tree_copy(tree2));
2383 tree1 = isl_schedule_tree_replace_child(tree1, i, child);
2386 isl_schedule_tree_free(tree2);
2387 return tree1;
2388 error:
2389 isl_schedule_tree_free(tree1);
2390 isl_schedule_tree_free(tree2);
2391 return NULL;
2394 /* Reset the user pointer on all identifiers of parameters and tuples
2395 * in the root of "tree".
2397 __isl_give isl_schedule_tree *isl_schedule_tree_reset_user(
2398 __isl_take isl_schedule_tree *tree)
2400 if (isl_schedule_tree_is_leaf(tree))
2401 return tree;
2403 tree = isl_schedule_tree_cow(tree);
2404 if (!tree)
2405 return NULL;
2407 switch (tree->type) {
2408 case isl_schedule_node_error:
2409 return isl_schedule_tree_free(tree);
2410 case isl_schedule_node_band:
2411 tree->band = isl_schedule_band_reset_user(tree->band);
2412 if (!tree->band)
2413 return isl_schedule_tree_free(tree);
2414 break;
2415 case isl_schedule_node_context:
2416 tree->context = isl_set_reset_user(tree->context);
2417 if (!tree->context)
2418 return isl_schedule_tree_free(tree);
2419 break;
2420 case isl_schedule_node_domain:
2421 tree->domain = isl_union_set_reset_user(tree->domain);
2422 if (!tree->domain)
2423 return isl_schedule_tree_free(tree);
2424 break;
2425 case isl_schedule_node_expansion:
2426 tree->contraction =
2427 isl_union_pw_multi_aff_reset_user(tree->contraction);
2428 tree->expansion = isl_union_map_reset_user(tree->expansion);
2429 if (!tree->contraction || !tree->expansion)
2430 return isl_schedule_tree_free(tree);
2431 break;
2432 case isl_schedule_node_extension:
2433 tree->extension = isl_union_map_reset_user(tree->extension);
2434 if (!tree->extension)
2435 return isl_schedule_tree_free(tree);
2436 break;
2437 case isl_schedule_node_filter:
2438 tree->filter = isl_union_set_reset_user(tree->filter);
2439 if (!tree->filter)
2440 return isl_schedule_tree_free(tree);
2441 break;
2442 case isl_schedule_node_guard:
2443 tree->guard = isl_set_reset_user(tree->guard);
2444 if (!tree->guard)
2445 return isl_schedule_tree_free(tree);
2446 break;
2447 case isl_schedule_node_leaf:
2448 case isl_schedule_node_mark:
2449 case isl_schedule_node_sequence:
2450 case isl_schedule_node_set:
2451 break;
2454 return tree;
2457 /* Align the parameters of the root of "tree" to those of "space".
2459 __isl_give isl_schedule_tree *isl_schedule_tree_align_params(
2460 __isl_take isl_schedule_tree *tree, __isl_take isl_space *space)
2462 if (!space)
2463 goto error;
2465 if (isl_schedule_tree_is_leaf(tree)) {
2466 isl_space_free(space);
2467 return tree;
2470 tree = isl_schedule_tree_cow(tree);
2471 if (!tree)
2472 goto error;
2474 switch (tree->type) {
2475 case isl_schedule_node_error:
2476 goto error;
2477 case isl_schedule_node_band:
2478 tree->band = isl_schedule_band_align_params(tree->band, space);
2479 if (!tree->band)
2480 return isl_schedule_tree_free(tree);
2481 break;
2482 case isl_schedule_node_context:
2483 tree->context = isl_set_align_params(tree->context, space);
2484 if (!tree->context)
2485 return isl_schedule_tree_free(tree);
2486 break;
2487 case isl_schedule_node_domain:
2488 tree->domain = isl_union_set_align_params(tree->domain, space);
2489 if (!tree->domain)
2490 return isl_schedule_tree_free(tree);
2491 break;
2492 case isl_schedule_node_expansion:
2493 tree->contraction =
2494 isl_union_pw_multi_aff_align_params(tree->contraction,
2495 isl_space_copy(space));
2496 tree->expansion = isl_union_map_align_params(tree->expansion,
2497 space);
2498 if (!tree->contraction || !tree->expansion)
2499 return isl_schedule_tree_free(tree);
2500 break;
2501 case isl_schedule_node_extension:
2502 tree->extension = isl_union_map_align_params(tree->extension,
2503 space);
2504 if (!tree->extension)
2505 return isl_schedule_tree_free(tree);
2506 break;
2507 case isl_schedule_node_filter:
2508 tree->filter = isl_union_set_align_params(tree->filter, space);
2509 if (!tree->filter)
2510 return isl_schedule_tree_free(tree);
2511 break;
2512 case isl_schedule_node_guard:
2513 tree->guard = isl_set_align_params(tree->guard, space);
2514 if (!tree->guard)
2515 return isl_schedule_tree_free(tree);
2516 break;
2517 case isl_schedule_node_leaf:
2518 case isl_schedule_node_mark:
2519 case isl_schedule_node_sequence:
2520 case isl_schedule_node_set:
2521 isl_space_free(space);
2522 break;
2525 return tree;
2526 error:
2527 isl_space_free(space);
2528 isl_schedule_tree_free(tree);
2529 return NULL;
2532 /* Does "tree" involve the iteration domain?
2533 * That is, does it need to be modified
2534 * by isl_schedule_tree_pullback_union_pw_multi_aff?
2536 static int involves_iteration_domain(__isl_keep isl_schedule_tree *tree)
2538 if (!tree)
2539 return -1;
2541 switch (tree->type) {
2542 case isl_schedule_node_error:
2543 return -1;
2544 case isl_schedule_node_band:
2545 case isl_schedule_node_domain:
2546 case isl_schedule_node_expansion:
2547 case isl_schedule_node_extension:
2548 case isl_schedule_node_filter:
2549 return 1;
2550 case isl_schedule_node_context:
2551 case isl_schedule_node_leaf:
2552 case isl_schedule_node_guard:
2553 case isl_schedule_node_mark:
2554 case isl_schedule_node_sequence:
2555 case isl_schedule_node_set:
2556 return 0;
2559 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
2560 "unhandled case", return -1);
2563 /* Compute the pullback of the root node of "tree" by the function
2564 * represented by "upma".
2565 * In other words, plug in "upma" in the iteration domains of
2566 * the root node of "tree".
2567 * We currently do not handle expansion nodes.
2569 * We first check if the root node involves any iteration domains.
2570 * If so, we handle the specific cases.
2572 __isl_give isl_schedule_tree *isl_schedule_tree_pullback_union_pw_multi_aff(
2573 __isl_take isl_schedule_tree *tree,
2574 __isl_take isl_union_pw_multi_aff *upma)
2576 int involves;
2578 if (!tree || !upma)
2579 goto error;
2581 involves = involves_iteration_domain(tree);
2582 if (involves < 0)
2583 goto error;
2584 if (!involves) {
2585 isl_union_pw_multi_aff_free(upma);
2586 return tree;
2589 tree = isl_schedule_tree_cow(tree);
2590 if (!tree)
2591 goto error;
2593 if (tree->type == isl_schedule_node_band) {
2594 tree->band = isl_schedule_band_pullback_union_pw_multi_aff(
2595 tree->band, upma);
2596 if (!tree->band)
2597 return isl_schedule_tree_free(tree);
2598 } else if (tree->type == isl_schedule_node_domain) {
2599 tree->domain =
2600 isl_union_set_preimage_union_pw_multi_aff(tree->domain,
2601 upma);
2602 if (!tree->domain)
2603 return isl_schedule_tree_free(tree);
2604 } else if (tree->type == isl_schedule_node_expansion) {
2605 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_unsupported,
2606 "cannot pullback expansion node", goto error);
2607 } else if (tree->type == isl_schedule_node_extension) {
2608 tree->extension =
2609 isl_union_map_preimage_range_union_pw_multi_aff(
2610 tree->extension, upma);
2611 if (!tree->extension)
2612 return isl_schedule_tree_free(tree);
2613 } else if (tree->type == isl_schedule_node_filter) {
2614 tree->filter =
2615 isl_union_set_preimage_union_pw_multi_aff(tree->filter,
2616 upma);
2617 if (!tree->filter)
2618 return isl_schedule_tree_free(tree);
2621 return tree;
2622 error:
2623 isl_union_pw_multi_aff_free(upma);
2624 isl_schedule_tree_free(tree);
2625 return NULL;
2628 /* Compute the gist of the band tree root with respect to "context".
2630 __isl_give isl_schedule_tree *isl_schedule_tree_band_gist(
2631 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *context)
2633 if (!tree)
2634 return NULL;
2635 if (tree->type != isl_schedule_node_band)
2636 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2637 "not a band node", goto error);
2638 tree = isl_schedule_tree_cow(tree);
2639 if (!tree)
2640 goto error;
2642 tree->band = isl_schedule_band_gist(tree->band, context);
2643 if (!tree->band)
2644 return isl_schedule_tree_free(tree);
2645 return tree;
2646 error:
2647 isl_union_set_free(context);
2648 isl_schedule_tree_free(tree);
2649 return NULL;
2652 /* Are any members in "band" marked coincident?
2654 static isl_bool any_coincident(__isl_keep isl_schedule_band *band)
2656 int i;
2657 isl_size n;
2659 n = isl_schedule_band_n_member(band);
2660 if (n < 0)
2661 return isl_bool_error;
2662 for (i = 0; i < n; ++i) {
2663 isl_bool coincident;
2665 coincident = isl_schedule_band_member_get_coincident(band, i);
2666 if (coincident < 0 || coincident)
2667 return coincident;
2670 return isl_bool_false;
2673 /* Print the band node "band" to "p".
2675 * The permutable and coincident properties are only printed if they
2676 * are different from the defaults.
2677 * The coincident property is always printed in YAML flow style.
2679 static __isl_give isl_printer *print_tree_band(__isl_take isl_printer *p,
2680 __isl_keep isl_schedule_band *band)
2682 isl_union_set *options;
2683 isl_bool empty;
2684 isl_bool coincident;
2686 p = isl_printer_print_str(p, "schedule");
2687 p = isl_printer_yaml_next(p);
2688 p = isl_printer_print_str(p, "\"");
2689 p = isl_printer_print_multi_union_pw_aff(p, band->mupa);
2690 p = isl_printer_print_str(p, "\"");
2691 if (isl_schedule_band_get_permutable(band)) {
2692 p = isl_printer_yaml_next(p);
2693 p = isl_printer_print_str(p, "permutable");
2694 p = isl_printer_yaml_next(p);
2695 p = isl_printer_print_int(p, 1);
2697 coincident = any_coincident(band);
2698 if (coincident < 0)
2699 return isl_printer_free(p);
2700 if (coincident) {
2701 int i;
2702 isl_size n;
2703 int style;
2705 p = isl_printer_yaml_next(p);
2706 p = isl_printer_print_str(p, "coincident");
2707 p = isl_printer_yaml_next(p);
2708 style = isl_printer_get_yaml_style(p);
2709 p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_FLOW);
2710 p = isl_printer_yaml_start_sequence(p);
2711 n = isl_schedule_band_n_member(band);
2712 if (n < 0)
2713 return isl_printer_free(p);
2714 for (i = 0; i < n; ++i) {
2715 p = isl_printer_print_int(p,
2716 isl_schedule_band_member_get_coincident(band, i));
2717 p = isl_printer_yaml_next(p);
2719 p = isl_printer_yaml_end_sequence(p);
2720 p = isl_printer_set_yaml_style(p, style);
2722 options = isl_schedule_band_get_ast_build_options(band);
2723 empty = isl_union_set_is_empty(options);
2724 if (empty < 0)
2725 p = isl_printer_free(p);
2726 if (!empty) {
2727 p = isl_printer_yaml_next(p);
2728 p = isl_printer_print_str(p, "options");
2729 p = isl_printer_yaml_next(p);
2730 p = isl_printer_print_str(p, "\"");
2731 p = isl_printer_print_union_set(p, options);
2732 p = isl_printer_print_str(p, "\"");
2734 isl_union_set_free(options);
2736 return p;
2739 #undef BASE
2740 #define BASE str
2741 #define isl_str const char
2742 #include "print_yaml_field_templ.c"
2744 #undef BASE
2745 #define BASE set
2746 #include "print_yaml_field_templ.c"
2748 #undef BASE
2749 #define BASE union_set
2750 #include "print_yaml_field_templ.c"
2752 #undef BASE
2753 #define BASE union_map
2754 #include "print_yaml_field_templ.c"
2756 #undef BASE
2757 #define BASE union_pw_multi_aff
2758 #include "print_yaml_field_templ.c"
2760 /* Print "tree" to "p".
2762 * If "n_ancestor" is non-negative, then "child_pos" contains the child
2763 * positions of a descendant of the current node that should be marked
2764 * (by the comment "YOU ARE HERE"). In particular, if "n_ancestor"
2765 * is zero, then the current node should be marked.
2766 * The marking is only printed in YAML block format.
2768 * Implicit leaf nodes are not printed, except if they correspond
2769 * to the node that should be marked.
2771 __isl_give isl_printer *isl_printer_print_schedule_tree_mark(
2772 __isl_take isl_printer *p, __isl_keep isl_schedule_tree *tree,
2773 int n_ancestor, int *child_pos)
2775 int i;
2776 isl_size n;
2777 int sequence = 0;
2778 int block;
2780 block = isl_printer_get_yaml_style(p) == ISL_YAML_STYLE_BLOCK;
2782 p = isl_printer_yaml_start_mapping(p);
2783 if (n_ancestor == 0 && block) {
2784 p = isl_printer_print_str(p, "# YOU ARE HERE");
2785 p = isl_printer_end_line(p);
2786 p = isl_printer_start_line(p);
2788 switch (tree->type) {
2789 case isl_schedule_node_error:
2790 p = isl_printer_print_str(p, "ERROR");
2791 p = isl_printer_yaml_next(p);
2792 break;
2793 case isl_schedule_node_leaf:
2794 p = isl_printer_print_str(p, "leaf");
2795 p = isl_printer_yaml_next(p);
2796 break;
2797 case isl_schedule_node_sequence:
2798 p = isl_printer_print_str(p, "sequence");
2799 p = isl_printer_yaml_next(p);
2800 sequence = 1;
2801 break;
2802 case isl_schedule_node_set:
2803 p = isl_printer_print_str(p, "set");
2804 p = isl_printer_yaml_next(p);
2805 sequence = 1;
2806 break;
2807 case isl_schedule_node_context:
2808 p = print_yaml_field_set(p, "context", tree->context);
2809 break;
2810 case isl_schedule_node_domain:
2811 p = print_yaml_field_union_set(p, "domain", tree->domain);
2812 break;
2813 case isl_schedule_node_expansion:
2814 p = print_yaml_field_union_pw_multi_aff(p, "contraction",
2815 tree->contraction);
2816 p = print_yaml_field_union_map(p, "expansion", tree->expansion);
2817 break;
2818 case isl_schedule_node_extension:
2819 p = print_yaml_field_union_map(p, "extension", tree->extension);
2820 break;
2821 case isl_schedule_node_filter:
2822 p = print_yaml_field_union_set(p, "filter", tree->filter);
2823 break;
2824 case isl_schedule_node_guard:
2825 p = print_yaml_field_set(p, "guard", tree->guard);
2826 break;
2827 case isl_schedule_node_mark:
2828 p = print_yaml_field_str(p, "mark",
2829 isl_id_get_name(tree->mark));
2830 break;
2831 case isl_schedule_node_band:
2832 p = print_tree_band(p, tree->band);
2833 p = isl_printer_yaml_next(p);
2834 break;
2837 n = isl_schedule_tree_n_children(tree);
2838 if (n < 0)
2839 return isl_printer_free(p);
2840 if (n == 0) {
2841 if (n_ancestor > 0 && block) {
2842 isl_schedule_tree *leaf;
2844 p = isl_printer_print_str(p, "child");
2845 p = isl_printer_yaml_next(p);
2846 leaf = isl_schedule_tree_leaf(isl_printer_get_ctx(p));
2847 p = isl_printer_print_schedule_tree_mark(p,
2848 leaf, 0, NULL);
2849 isl_schedule_tree_free(leaf);
2850 p = isl_printer_yaml_next(p);
2852 return isl_printer_yaml_end_mapping(p);
2855 if (sequence) {
2856 p = isl_printer_yaml_start_sequence(p);
2857 } else {
2858 p = isl_printer_print_str(p, "child");
2859 p = isl_printer_yaml_next(p);
2862 for (i = 0; i < n; ++i) {
2863 isl_schedule_tree *t;
2865 t = isl_schedule_tree_get_child(tree, i);
2866 if (n_ancestor > 0 && child_pos[0] == i)
2867 p = isl_printer_print_schedule_tree_mark(p, t,
2868 n_ancestor - 1, child_pos + 1);
2869 else
2870 p = isl_printer_print_schedule_tree_mark(p, t,
2871 -1, NULL);
2872 isl_schedule_tree_free(t);
2874 p = isl_printer_yaml_next(p);
2877 if (sequence)
2878 p = isl_printer_yaml_end_sequence(p);
2879 p = isl_printer_yaml_end_mapping(p);
2881 return p;
2884 /* Print "tree" to "p".
2886 __isl_give isl_printer *isl_printer_print_schedule_tree(
2887 __isl_take isl_printer *p, __isl_keep isl_schedule_tree *tree)
2889 return isl_printer_print_schedule_tree_mark(p, tree, -1, NULL);
2892 void isl_schedule_tree_dump(__isl_keep isl_schedule_tree *tree)
2894 isl_ctx *ctx;
2895 isl_printer *printer;
2897 if (!tree)
2898 return;
2900 ctx = isl_schedule_tree_get_ctx(tree);
2901 printer = isl_printer_to_file(ctx, stderr);
2902 printer = isl_printer_set_yaml_style(printer, ISL_YAML_STYLE_BLOCK);
2903 printer = isl_printer_print_schedule_tree(printer, tree);
2905 isl_printer_free(printer);