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
14 #include <isl_schedule_band.h>
15 #include <isl_schedule_private.h>
18 #define EL isl_schedule_tree
20 #include <isl_list_templ.h>
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
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
)
49 tree
= isl_calloc_type(ctx
, isl_schedule_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
)
68 isl_schedule_tree
*dup
;
73 ctx
= isl_schedule_tree_get_ctx(tree
);
74 dup
= isl_schedule_tree_alloc(ctx
, 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
);
86 return isl_schedule_tree_free(dup
);
88 case isl_schedule_node_context
:
89 dup
->context
= isl_set_copy(tree
->context
);
91 return isl_schedule_tree_free(dup
);
93 case isl_schedule_node_domain
:
94 dup
->domain
= isl_union_set_copy(tree
->domain
);
96 return isl_schedule_tree_free(dup
);
98 case isl_schedule_node_expansion
:
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
);
105 case isl_schedule_node_filter
:
106 dup
->filter
= isl_union_set_copy(tree
->filter
);
108 return isl_schedule_tree_free(dup
);
110 case isl_schedule_node_guard
:
111 dup
->guard
= isl_set_copy(tree
->guard
);
113 return isl_schedule_tree_free(dup
);
115 case isl_schedule_node_mark
:
116 dup
->mark
= isl_id_copy(tree
->mark
);
118 return isl_schedule_tree_free(dup
);
120 case isl_schedule_node_leaf
:
121 case isl_schedule_node_sequence
:
122 case isl_schedule_node_set
:
126 if (tree
->children
) {
127 dup
->children
= isl_schedule_tree_list_copy(tree
->children
);
129 return isl_schedule_tree_free(dup
);
131 dup
->anchored
= tree
->anchored
;
136 /* Return an isl_schedule_tree that is equal to "tree" and that has only
137 * a single reference.
139 * This function is called before a tree is modified.
140 * A static tree (with negative reference count) should never be modified,
141 * so it is not allowed to call this function on a static tree.
143 __isl_give isl_schedule_tree
*isl_schedule_tree_cow(
144 __isl_take isl_schedule_tree
*tree
)
150 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
151 "static trees cannot be modified",
152 return isl_schedule_tree_free(tree
));
157 return isl_schedule_tree_dup(tree
);
160 /* Return a new reference to "tree".
162 * A static tree (with negative reference count) does not keep track
163 * of the number of references and should not be modified.
165 __isl_give isl_schedule_tree
*isl_schedule_tree_copy(
166 __isl_keep isl_schedule_tree
*tree
)
178 /* Free "tree" and return NULL.
180 __isl_null isl_schedule_tree
*isl_schedule_tree_free(
181 __isl_take isl_schedule_tree
*tree
)
190 switch (tree
->type
) {
191 case isl_schedule_node_band
:
192 isl_schedule_band_free(tree
->band
);
194 case isl_schedule_node_context
:
195 isl_set_free(tree
->context
);
197 case isl_schedule_node_domain
:
198 isl_union_set_free(tree
->domain
);
200 case isl_schedule_node_expansion
:
201 isl_union_pw_multi_aff_free(tree
->contraction
);
202 isl_union_map_free(tree
->expansion
);
204 case isl_schedule_node_filter
:
205 isl_union_set_free(tree
->filter
);
207 case isl_schedule_node_guard
:
208 isl_set_free(tree
->guard
);
210 case isl_schedule_node_mark
:
211 isl_id_free(tree
->mark
);
213 case isl_schedule_node_sequence
:
214 case isl_schedule_node_set
:
215 case isl_schedule_node_error
:
216 case isl_schedule_node_leaf
:
219 isl_schedule_tree_list_free(tree
->children
);
220 isl_ctx_deref(tree
->ctx
);
226 /* Create and return a new leaf schedule tree.
228 __isl_give isl_schedule_tree
*isl_schedule_tree_leaf(isl_ctx
*ctx
)
230 return isl_schedule_tree_alloc(ctx
, isl_schedule_node_leaf
);
233 /* Create a new band schedule tree referring to "band"
236 __isl_give isl_schedule_tree
*isl_schedule_tree_from_band(
237 __isl_take isl_schedule_band
*band
)
240 isl_schedule_tree
*tree
;
245 ctx
= isl_schedule_band_get_ctx(band
);
246 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_band
);
251 tree
->anchored
= isl_schedule_band_is_anchored(band
);
255 isl_schedule_band_free(band
);
259 /* Create a new context schedule tree with the given context and no children.
260 * Since the context references the outer schedule dimension,
261 * the tree is anchored.
263 __isl_give isl_schedule_tree
*isl_schedule_tree_from_context(
264 __isl_take isl_set
*context
)
267 isl_schedule_tree
*tree
;
272 ctx
= isl_set_get_ctx(context
);
273 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_context
);
277 tree
->context
= context
;
282 isl_set_free(context
);
286 /* Create a new domain schedule tree with the given domain and no children.
288 __isl_give isl_schedule_tree
*isl_schedule_tree_from_domain(
289 __isl_take isl_union_set
*domain
)
292 isl_schedule_tree
*tree
;
297 ctx
= isl_union_set_get_ctx(domain
);
298 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_domain
);
302 tree
->domain
= domain
;
306 isl_union_set_free(domain
);
310 /* Create a new expansion schedule tree with the given contraction and
311 * expansion and no children.
313 __isl_give isl_schedule_tree
*isl_schedule_tree_from_expansion(
314 __isl_take isl_union_pw_multi_aff
*contraction
,
315 __isl_take isl_union_map
*expansion
)
318 isl_schedule_tree
*tree
;
320 if (!contraction
|| !expansion
)
323 ctx
= isl_union_map_get_ctx(expansion
);
324 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_expansion
);
328 tree
->contraction
= contraction
;
329 tree
->expansion
= expansion
;
333 isl_union_pw_multi_aff_free(contraction
);
334 isl_union_map_free(expansion
);
338 /* Create a new filter schedule tree with the given filter and no children.
340 __isl_give isl_schedule_tree
*isl_schedule_tree_from_filter(
341 __isl_take isl_union_set
*filter
)
344 isl_schedule_tree
*tree
;
349 ctx
= isl_union_set_get_ctx(filter
);
350 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_filter
);
354 tree
->filter
= filter
;
358 isl_union_set_free(filter
);
362 /* Create a new guard schedule tree with the given guard and no children.
363 * Since the guard references the outer schedule dimension,
364 * the tree is anchored.
366 __isl_give isl_schedule_tree
*isl_schedule_tree_from_guard(
367 __isl_take isl_set
*guard
)
370 isl_schedule_tree
*tree
;
375 ctx
= isl_set_get_ctx(guard
);
376 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_guard
);
389 /* Create a new mark schedule tree with the given mark identifier and
392 __isl_give isl_schedule_tree
*isl_schedule_tree_from_mark(
393 __isl_take isl_id
*mark
)
396 isl_schedule_tree
*tree
;
401 ctx
= isl_id_get_ctx(mark
);
402 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_mark
);
414 /* Does "tree" have any node that depends on its position
415 * in the complete schedule tree?
417 int isl_schedule_tree_is_subtree_anchored(__isl_keep isl_schedule_tree
*tree
)
419 return tree
? tree
->anchored
: -1;
422 /* Does the root node of "tree" depend on its position in the complete
424 * Band nodes may be anchored depending on the associated AST build options.
425 * Context and guard nodes are always anchored.
427 int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree
*tree
)
432 switch (isl_schedule_tree_get_type(tree
)) {
433 case isl_schedule_node_error
:
435 case isl_schedule_node_band
:
436 return isl_schedule_band_is_anchored(tree
->band
);
437 case isl_schedule_node_context
:
438 case isl_schedule_node_guard
:
440 case isl_schedule_node_domain
:
441 case isl_schedule_node_expansion
:
442 case isl_schedule_node_filter
:
443 case isl_schedule_node_leaf
:
444 case isl_schedule_node_mark
:
445 case isl_schedule_node_sequence
:
446 case isl_schedule_node_set
:
451 /* Update the anchored field of "tree" based on whether the root node
452 * itself in anchored and the anchored fields of the children.
454 * This function should be called whenever the children of a tree node
455 * are changed or the anchoredness of the tree root itself changes.
457 __isl_give isl_schedule_tree
*isl_schedule_tree_update_anchored(
458 __isl_take isl_schedule_tree
*tree
)
466 anchored
= isl_schedule_tree_is_anchored(tree
);
468 return isl_schedule_tree_free(tree
);
470 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
471 for (i
= 0; !anchored
&& i
< n
; ++i
) {
472 isl_schedule_tree
*child
;
474 child
= isl_schedule_tree_get_child(tree
, i
);
476 return isl_schedule_tree_free(tree
);
477 anchored
= child
->anchored
;
478 isl_schedule_tree_free(child
);
481 if (anchored
== tree
->anchored
)
483 tree
= isl_schedule_tree_cow(tree
);
486 tree
->anchored
= anchored
;
490 /* Create a new tree of the given type (isl_schedule_node_sequence or
491 * isl_schedule_node_set) with the given children.
493 __isl_give isl_schedule_tree
*isl_schedule_tree_from_children(
494 enum isl_schedule_node_type type
,
495 __isl_take isl_schedule_tree_list
*list
)
498 isl_schedule_tree
*tree
;
503 ctx
= isl_schedule_tree_list_get_ctx(list
);
504 tree
= isl_schedule_tree_alloc(ctx
, type
);
508 tree
->children
= list
;
509 tree
= isl_schedule_tree_update_anchored(tree
);
513 isl_schedule_tree_list_free(list
);
517 /* Construct a tree with a root node of type "type" and as children
518 * "tree1" and "tree2".
519 * If the root of one (or both) of the input trees is itself of type "type",
520 * then the tree is replaced by its children.
522 __isl_give isl_schedule_tree
*isl_schedule_tree_from_pair(
523 enum isl_schedule_node_type type
, __isl_take isl_schedule_tree
*tree1
,
524 __isl_take isl_schedule_tree
*tree2
)
527 isl_schedule_tree_list
*list
;
529 if (!tree1
|| !tree2
)
532 ctx
= isl_schedule_tree_get_ctx(tree1
);
533 if (isl_schedule_tree_get_type(tree1
) == type
) {
534 list
= isl_schedule_tree_list_copy(tree1
->children
);
535 isl_schedule_tree_free(tree1
);
537 list
= isl_schedule_tree_list_alloc(ctx
, 2);
538 list
= isl_schedule_tree_list_add(list
, tree1
);
540 if (isl_schedule_tree_get_type(tree2
) == type
) {
541 isl_schedule_tree_list
*children
;
543 children
= isl_schedule_tree_list_copy(tree2
->children
);
544 list
= isl_schedule_tree_list_concat(list
, children
);
545 isl_schedule_tree_free(tree2
);
547 list
= isl_schedule_tree_list_add(list
, tree2
);
550 return isl_schedule_tree_from_children(type
, list
);
552 isl_schedule_tree_free(tree1
);
553 isl_schedule_tree_free(tree2
);
557 /* Return the isl_ctx to which "tree" belongs.
559 isl_ctx
*isl_schedule_tree_get_ctx(__isl_keep isl_schedule_tree
*tree
)
561 return tree
? tree
->ctx
: NULL
;
564 /* Return the type of the root of the tree or isl_schedule_node_error
567 enum isl_schedule_node_type
isl_schedule_tree_get_type(
568 __isl_keep isl_schedule_tree
*tree
)
570 return tree
? tree
->type
: isl_schedule_node_error
;
573 /* Are "tree1" and "tree2" obviously equal to each other?
575 int isl_schedule_tree_plain_is_equal(__isl_keep isl_schedule_tree
*tree1
,
576 __isl_keep isl_schedule_tree
*tree2
)
581 if (!tree1
|| !tree2
)
585 if (tree1
->type
!= tree2
->type
)
588 switch (tree1
->type
) {
589 case isl_schedule_node_band
:
590 equal
= isl_schedule_band_plain_is_equal(tree1
->band
,
593 case isl_schedule_node_context
:
594 equal
= isl_set_is_equal(tree1
->context
, tree2
->context
);
596 case isl_schedule_node_domain
:
597 equal
= isl_union_set_is_equal(tree1
->domain
, tree2
->domain
);
599 case isl_schedule_node_expansion
:
600 equal
= isl_union_map_is_equal(tree1
->expansion
,
602 if (equal
>= 0 && equal
)
603 equal
= isl_union_pw_multi_aff_plain_is_equal(
604 tree1
->contraction
, tree2
->contraction
);
606 case isl_schedule_node_filter
:
607 equal
= isl_union_set_is_equal(tree1
->filter
, tree2
->filter
);
609 case isl_schedule_node_guard
:
610 equal
= isl_set_is_equal(tree1
->guard
, tree2
->guard
);
612 case isl_schedule_node_mark
:
613 equal
= tree1
->mark
== tree2
->mark
;
615 case isl_schedule_node_leaf
:
616 case isl_schedule_node_sequence
:
617 case isl_schedule_node_set
:
620 case isl_schedule_node_error
:
625 if (equal
< 0 || !equal
)
628 n
= isl_schedule_tree_n_children(tree1
);
629 if (n
!= isl_schedule_tree_n_children(tree2
))
631 for (i
= 0; i
< n
; ++i
) {
632 isl_schedule_tree
*child1
, *child2
;
634 child1
= isl_schedule_tree_get_child(tree1
, i
);
635 child2
= isl_schedule_tree_get_child(tree2
, i
);
636 equal
= isl_schedule_tree_plain_is_equal(child1
, child2
);
637 isl_schedule_tree_free(child1
);
638 isl_schedule_tree_free(child2
);
640 if (equal
< 0 || !equal
)
647 /* Does "tree" have any children, other than an implicit leaf.
649 int isl_schedule_tree_has_children(__isl_keep isl_schedule_tree
*tree
)
654 return tree
->children
!= NULL
;
657 /* Return the number of children of "tree", excluding implicit leaves.
659 int isl_schedule_tree_n_children(__isl_keep isl_schedule_tree
*tree
)
664 return isl_schedule_tree_list_n_schedule_tree(tree
->children
);
667 /* Return a copy of the (explicit) child at position "pos" of "tree".
669 __isl_give isl_schedule_tree
*isl_schedule_tree_get_child(
670 __isl_keep isl_schedule_tree
*tree
, int pos
)
675 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
676 "schedule tree has no explicit children", return NULL
);
677 return isl_schedule_tree_list_get_schedule_tree(tree
->children
, pos
);
680 /* Return a copy of the (explicit) child at position "pos" of "tree" and
683 __isl_give isl_schedule_tree
*isl_schedule_tree_child(
684 __isl_take isl_schedule_tree
*tree
, int pos
)
686 isl_schedule_tree
*child
;
688 child
= isl_schedule_tree_get_child(tree
, pos
);
689 isl_schedule_tree_free(tree
);
693 /* Remove all (explicit) children from "tree".
695 __isl_give isl_schedule_tree
*isl_schedule_tree_reset_children(
696 __isl_take isl_schedule_tree
*tree
)
698 tree
= isl_schedule_tree_cow(tree
);
701 tree
->children
= isl_schedule_tree_list_free(tree
->children
);
705 /* Remove the child at position "pos" from the children of "tree".
706 * If there was only one child to begin with, then remove all children.
708 __isl_give isl_schedule_tree
*isl_schedule_tree_drop_child(
709 __isl_take isl_schedule_tree
*tree
, int pos
)
713 tree
= isl_schedule_tree_cow(tree
);
717 if (!isl_schedule_tree_has_children(tree
))
718 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
719 "tree does not have any explicit children",
720 return isl_schedule_tree_free(tree
));
721 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
722 if (pos
< 0 || pos
>= n
)
723 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
724 "position out of bounds",
725 return isl_schedule_tree_free(tree
));
727 return isl_schedule_tree_reset_children(tree
);
729 tree
->children
= isl_schedule_tree_list_drop(tree
->children
, pos
, 1);
731 return isl_schedule_tree_free(tree
);
736 /* Replace the child at position "pos" of "tree" by "child".
738 * If the new child is a leaf, then it is not explicitly
739 * recorded in the list of children. Instead, the list of children
740 * (which is assumed to have only one element) is removed.
741 * Note that the children of set and sequence nodes are always
742 * filters, so they cannot be replaced by empty trees.
744 __isl_give isl_schedule_tree
*isl_schedule_tree_replace_child(
745 __isl_take isl_schedule_tree
*tree
, int pos
,
746 __isl_take isl_schedule_tree
*child
)
748 tree
= isl_schedule_tree_cow(tree
);
752 if (isl_schedule_tree_is_leaf(child
)) {
753 isl_schedule_tree_free(child
);
754 if (!tree
->children
&& pos
== 0)
756 if (isl_schedule_tree_n_children(tree
) != 1)
757 isl_die(isl_schedule_tree_get_ctx(tree
),
759 "can only replace single child by leaf",
761 return isl_schedule_tree_reset_children(tree
);
764 if (!tree
->children
&& pos
== 0)
766 isl_schedule_tree_list_from_schedule_tree(child
);
768 tree
->children
= isl_schedule_tree_list_set_schedule_tree(
769 tree
->children
, pos
, child
);
772 return isl_schedule_tree_free(tree
);
773 tree
= isl_schedule_tree_update_anchored(tree
);
777 isl_schedule_tree_free(tree
);
778 isl_schedule_tree_free(child
);
782 /* Replace the (explicit) children of "tree" by "children"?
784 __isl_give isl_schedule_tree
*isl_schedule_tree_set_children(
785 __isl_take isl_schedule_tree
*tree
,
786 __isl_take isl_schedule_tree_list
*children
)
788 tree
= isl_schedule_tree_cow(tree
);
789 if (!tree
|| !children
)
791 isl_schedule_tree_list_free(tree
->children
);
792 tree
->children
= children
;
795 isl_schedule_tree_free(tree
);
796 isl_schedule_tree_list_free(children
);
800 /* Create a new band schedule tree referring to "band"
801 * with "tree" as single child.
803 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_band(
804 __isl_take isl_schedule_tree
*tree
, __isl_take isl_schedule_band
*band
)
806 isl_schedule_tree
*res
;
808 res
= isl_schedule_tree_from_band(band
);
809 return isl_schedule_tree_replace_child(res
, 0, tree
);
812 /* Create a new context schedule tree with the given context and
813 * with "tree" as single child.
815 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_context(
816 __isl_take isl_schedule_tree
*tree
, __isl_take isl_set
*context
)
818 isl_schedule_tree
*res
;
820 res
= isl_schedule_tree_from_context(context
);
821 return isl_schedule_tree_replace_child(res
, 0, tree
);
824 /* Create a new domain schedule tree with the given domain and
825 * with "tree" as single child.
827 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_domain(
828 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
830 isl_schedule_tree
*res
;
832 res
= isl_schedule_tree_from_domain(domain
);
833 return isl_schedule_tree_replace_child(res
, 0, tree
);
836 /* Create a new expansion schedule tree with the given contraction and
837 * expansion and with "tree" as single child.
839 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_expansion(
840 __isl_take isl_schedule_tree
*tree
,
841 __isl_take isl_union_pw_multi_aff
*contraction
,
842 __isl_take isl_union_map
*expansion
)
844 isl_schedule_tree
*res
;
846 res
= isl_schedule_tree_from_expansion(contraction
, expansion
);
847 return isl_schedule_tree_replace_child(res
, 0, tree
);
850 /* Create a new filter schedule tree with the given filter and single child.
852 * If the root of "tree" is itself a filter node, then the two
853 * filter nodes are merged into one node.
855 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_filter(
856 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
858 isl_schedule_tree
*res
;
860 if (isl_schedule_tree_get_type(tree
) == isl_schedule_node_filter
) {
861 isl_union_set
*tree_filter
;
863 tree_filter
= isl_schedule_tree_filter_get_filter(tree
);
864 tree_filter
= isl_union_set_intersect(tree_filter
, filter
);
865 tree
= isl_schedule_tree_filter_set_filter(tree
, tree_filter
);
869 res
= isl_schedule_tree_from_filter(filter
);
870 return isl_schedule_tree_replace_child(res
, 0, tree
);
873 /* Insert a filter node with filter set "filter"
874 * in each of the children of "tree".
876 __isl_give isl_schedule_tree
*isl_schedule_tree_children_insert_filter(
877 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
881 if (!tree
|| !filter
)
884 n
= isl_schedule_tree_n_children(tree
);
885 for (i
= 0; i
< n
; ++i
) {
886 isl_schedule_tree
*child
;
888 child
= isl_schedule_tree_get_child(tree
, i
);
889 child
= isl_schedule_tree_insert_filter(child
,
890 isl_union_set_copy(filter
));
891 tree
= isl_schedule_tree_replace_child(tree
, i
, child
);
894 isl_union_set_free(filter
);
897 isl_union_set_free(filter
);
898 isl_schedule_tree_free(tree
);
902 /* Create a new guard schedule tree with the given guard and
903 * with "tree" as single child.
905 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_guard(
906 __isl_take isl_schedule_tree
*tree
, __isl_take isl_set
*guard
)
908 isl_schedule_tree
*res
;
910 res
= isl_schedule_tree_from_guard(guard
);
911 return isl_schedule_tree_replace_child(res
, 0, tree
);
914 /* Create a new mark schedule tree with the given mark identifier and
917 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_mark(
918 __isl_take isl_schedule_tree
*tree
, __isl_take isl_id
*mark
)
920 isl_schedule_tree
*res
;
922 res
= isl_schedule_tree_from_mark(mark
);
923 return isl_schedule_tree_replace_child(res
, 0, tree
);
926 /* Return the number of members in the band tree root.
928 unsigned isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree
*tree
)
933 if (tree
->type
!= isl_schedule_node_band
)
934 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
935 "not a band node", return 0);
937 return isl_schedule_band_n_member(tree
->band
);
940 /* Is the band member at position "pos" of the band tree root
943 int isl_schedule_tree_band_member_get_coincident(
944 __isl_keep isl_schedule_tree
*tree
, int pos
)
949 if (tree
->type
!= isl_schedule_node_band
)
950 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
951 "not a band node", return -1);
953 return isl_schedule_band_member_get_coincident(tree
->band
, pos
);
956 /* Mark the given band member as being coincident or not
957 * according to "coincident".
959 __isl_give isl_schedule_tree
*isl_schedule_tree_band_member_set_coincident(
960 __isl_take isl_schedule_tree
*tree
, int pos
, int coincident
)
964 if (tree
->type
!= isl_schedule_node_band
)
965 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
966 "not a band node", return isl_schedule_tree_free(tree
));
967 if (isl_schedule_tree_band_member_get_coincident(tree
, pos
) ==
970 tree
= isl_schedule_tree_cow(tree
);
974 tree
->band
= isl_schedule_band_member_set_coincident(tree
->band
, pos
,
977 return isl_schedule_tree_free(tree
);
981 /* Is the band tree root marked permutable?
983 int isl_schedule_tree_band_get_permutable(__isl_keep isl_schedule_tree
*tree
)
988 if (tree
->type
!= isl_schedule_node_band
)
989 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
990 "not a band node", return -1);
992 return isl_schedule_band_get_permutable(tree
->band
);
995 /* Mark the band tree root permutable or not according to "permutable"?
997 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_permutable(
998 __isl_take isl_schedule_tree
*tree
, int permutable
)
1002 if (tree
->type
!= isl_schedule_node_band
)
1003 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1004 "not a band node", return isl_schedule_tree_free(tree
));
1005 if (isl_schedule_tree_band_get_permutable(tree
) == permutable
)
1007 tree
= isl_schedule_tree_cow(tree
);
1011 tree
->band
= isl_schedule_band_set_permutable(tree
->band
, permutable
);
1013 return isl_schedule_tree_free(tree
);
1017 /* Return the schedule space of the band tree root.
1019 __isl_give isl_space
*isl_schedule_tree_band_get_space(
1020 __isl_keep isl_schedule_tree
*tree
)
1025 if (tree
->type
!= isl_schedule_node_band
)
1026 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1027 "not a band node", return NULL
);
1029 return isl_schedule_band_get_space(tree
->band
);
1032 /* Intersect the domain of the band schedule of the band tree root
1035 __isl_give isl_schedule_tree
*isl_schedule_tree_band_intersect_domain(
1036 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
1038 if (!tree
|| !domain
)
1041 if (tree
->type
!= isl_schedule_node_band
)
1042 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1043 "not a band node", goto error
);
1045 tree
->band
= isl_schedule_band_intersect_domain(tree
->band
, domain
);
1047 return isl_schedule_tree_free(tree
);
1051 isl_schedule_tree_free(tree
);
1052 isl_union_set_free(domain
);
1056 /* Return the schedule of the band tree root in isolation.
1058 __isl_give isl_multi_union_pw_aff
*isl_schedule_tree_band_get_partial_schedule(
1059 __isl_keep isl_schedule_tree
*tree
)
1064 if (tree
->type
!= isl_schedule_node_band
)
1065 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1066 "not a band node", return NULL
);
1068 return isl_schedule_band_get_partial_schedule(tree
->band
);
1071 /* Replace the schedule of the band tree root by "schedule".
1073 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_partial_schedule(
1074 __isl_take isl_schedule_tree
*tree
,
1075 __isl_take isl_multi_union_pw_aff
*schedule
)
1077 tree
= isl_schedule_tree_cow(tree
);
1078 if (!tree
|| !schedule
)
1081 if (tree
->type
!= isl_schedule_node_band
)
1082 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1083 "not a band node", return NULL
);
1084 tree
->band
= isl_schedule_band_set_partial_schedule(tree
->band
,
1089 isl_schedule_tree_free(tree
);
1090 isl_multi_union_pw_aff_free(schedule
);
1094 /* Return the loop AST generation type for the band member
1095 * of the band tree root at position "pos".
1097 enum isl_ast_loop_type
isl_schedule_tree_band_member_get_ast_loop_type(
1098 __isl_keep isl_schedule_tree
*tree
, int pos
)
1101 return isl_ast_loop_error
;
1103 if (tree
->type
!= isl_schedule_node_band
)
1104 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1105 "not a band node", return isl_ast_loop_error
);
1107 return isl_schedule_band_member_get_ast_loop_type(tree
->band
, pos
);
1110 /* Set the loop AST generation type for the band member of the band tree root
1111 * at position "pos" to "type".
1113 __isl_give isl_schedule_tree
*isl_schedule_tree_band_member_set_ast_loop_type(
1114 __isl_take isl_schedule_tree
*tree
, int pos
,
1115 enum isl_ast_loop_type type
)
1117 tree
= isl_schedule_tree_cow(tree
);
1121 if (tree
->type
!= isl_schedule_node_band
)
1122 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1123 "not a band node", return isl_schedule_tree_free(tree
));
1125 tree
->band
= isl_schedule_band_member_set_ast_loop_type(tree
->band
,
1128 return isl_schedule_tree_free(tree
);
1133 /* Return the loop AST generation type for the band member
1134 * of the band tree root at position "pos" for the isolated part.
1136 enum isl_ast_loop_type
isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1137 __isl_keep isl_schedule_tree
*tree
, int pos
)
1140 return isl_ast_loop_error
;
1142 if (tree
->type
!= isl_schedule_node_band
)
1143 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1144 "not a band node", return isl_ast_loop_error
);
1146 return isl_schedule_band_member_get_isolate_ast_loop_type(tree
->band
,
1150 /* Set the loop AST generation type for the band member of the band tree root
1151 * at position "pos" for the isolated part to "type".
1153 __isl_give isl_schedule_tree
*
1154 isl_schedule_tree_band_member_set_isolate_ast_loop_type(
1155 __isl_take isl_schedule_tree
*tree
, int pos
,
1156 enum isl_ast_loop_type type
)
1158 tree
= isl_schedule_tree_cow(tree
);
1162 if (tree
->type
!= isl_schedule_node_band
)
1163 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1164 "not a band node", return isl_schedule_tree_free(tree
));
1166 tree
->band
= isl_schedule_band_member_set_isolate_ast_loop_type(
1167 tree
->band
, pos
, type
);
1169 return isl_schedule_tree_free(tree
);
1174 /* Return the AST build options associated to the band tree root.
1176 __isl_give isl_union_set
*isl_schedule_tree_band_get_ast_build_options(
1177 __isl_keep isl_schedule_tree
*tree
)
1182 if (tree
->type
!= isl_schedule_node_band
)
1183 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1184 "not a band node", return NULL
);
1186 return isl_schedule_band_get_ast_build_options(tree
->band
);
1189 /* Replace the AST build options associated to band tree root by "options".
1190 * Updated the anchored field if the anchoredness of the root node itself
1193 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_ast_build_options(
1194 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*options
)
1198 tree
= isl_schedule_tree_cow(tree
);
1199 if (!tree
|| !options
)
1202 if (tree
->type
!= isl_schedule_node_band
)
1203 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1204 "not a band node", goto error
);
1206 was_anchored
= isl_schedule_tree_is_anchored(tree
);
1207 tree
->band
= isl_schedule_band_set_ast_build_options(tree
->band
,
1210 return isl_schedule_tree_free(tree
);
1211 if (isl_schedule_tree_is_anchored(tree
) != was_anchored
)
1212 tree
= isl_schedule_tree_update_anchored(tree
);
1216 isl_schedule_tree_free(tree
);
1217 isl_union_set_free(options
);
1221 /* Return the context of the context tree root.
1223 __isl_give isl_set
*isl_schedule_tree_context_get_context(
1224 __isl_keep isl_schedule_tree
*tree
)
1229 if (tree
->type
!= isl_schedule_node_context
)
1230 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1231 "not a context node", return NULL
);
1233 return isl_set_copy(tree
->context
);
1236 /* Return the domain of the domain tree root.
1238 __isl_give isl_union_set
*isl_schedule_tree_domain_get_domain(
1239 __isl_keep isl_schedule_tree
*tree
)
1244 if (tree
->type
!= isl_schedule_node_domain
)
1245 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1246 "not a domain node", return NULL
);
1248 return isl_union_set_copy(tree
->domain
);
1251 /* Replace the domain of domain tree root "tree" by "domain".
1253 __isl_give isl_schedule_tree
*isl_schedule_tree_domain_set_domain(
1254 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
1256 tree
= isl_schedule_tree_cow(tree
);
1257 if (!tree
|| !domain
)
1260 if (tree
->type
!= isl_schedule_node_domain
)
1261 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1262 "not a domain node", goto error
);
1264 isl_union_set_free(tree
->domain
);
1265 tree
->domain
= domain
;
1269 isl_schedule_tree_free(tree
);
1270 isl_union_set_free(domain
);
1274 /* Return the contraction of the expansion tree root.
1276 __isl_give isl_union_pw_multi_aff
*isl_schedule_tree_expansion_get_contraction(
1277 __isl_keep isl_schedule_tree
*tree
)
1282 if (tree
->type
!= isl_schedule_node_expansion
)
1283 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1284 "not an expansion node", return NULL
);
1286 return isl_union_pw_multi_aff_copy(tree
->contraction
);
1289 /* Return the expansion of the expansion tree root.
1291 __isl_give isl_union_map
*isl_schedule_tree_expansion_get_expansion(
1292 __isl_keep isl_schedule_tree
*tree
)
1297 if (tree
->type
!= isl_schedule_node_expansion
)
1298 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1299 "not an expansion node", return NULL
);
1301 return isl_union_map_copy(tree
->expansion
);
1304 /* Replace the contraction and the expansion of the expansion tree root "tree"
1305 * by "contraction" and "expansion".
1307 __isl_give isl_schedule_tree
*
1308 isl_schedule_tree_expansion_set_contraction_and_expansion(
1309 __isl_take isl_schedule_tree
*tree
,
1310 __isl_take isl_union_pw_multi_aff
*contraction
,
1311 __isl_take isl_union_map
*expansion
)
1313 tree
= isl_schedule_tree_cow(tree
);
1314 if (!tree
|| !contraction
|| !expansion
)
1317 if (tree
->type
!= isl_schedule_node_expansion
)
1318 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1319 "not an expansion node", return NULL
);
1321 isl_union_pw_multi_aff_free(tree
->contraction
);
1322 tree
->contraction
= contraction
;
1323 isl_union_map_free(tree
->expansion
);
1324 tree
->expansion
= expansion
;
1328 isl_schedule_tree_free(tree
);
1329 isl_union_pw_multi_aff_free(contraction
);
1330 isl_union_map_free(expansion
);
1334 /* Return the filter of the filter tree root.
1336 __isl_give isl_union_set
*isl_schedule_tree_filter_get_filter(
1337 __isl_keep isl_schedule_tree
*tree
)
1342 if (tree
->type
!= isl_schedule_node_filter
)
1343 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1344 "not a filter node", return NULL
);
1346 return isl_union_set_copy(tree
->filter
);
1349 /* Replace the filter of the filter tree root by "filter".
1351 __isl_give isl_schedule_tree
*isl_schedule_tree_filter_set_filter(
1352 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
1354 tree
= isl_schedule_tree_cow(tree
);
1355 if (!tree
|| !filter
)
1358 if (tree
->type
!= isl_schedule_node_filter
)
1359 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1360 "not a filter node", return NULL
);
1362 isl_union_set_free(tree
->filter
);
1363 tree
->filter
= filter
;
1367 isl_schedule_tree_free(tree
);
1368 isl_union_set_free(filter
);
1372 /* Return the guard of the guard tree root.
1374 __isl_give isl_set
*isl_schedule_tree_guard_get_guard(
1375 __isl_take isl_schedule_tree
*tree
)
1380 if (tree
->type
!= isl_schedule_node_guard
)
1381 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1382 "not a guard node", return NULL
);
1384 return isl_set_copy(tree
->guard
);
1387 /* Return the mark identifier of the mark tree root "tree".
1389 __isl_give isl_id
*isl_schedule_tree_mark_get_id(
1390 __isl_keep isl_schedule_tree
*tree
)
1395 if (tree
->type
!= isl_schedule_node_mark
)
1396 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1397 "not a mark node", return NULL
);
1399 return isl_id_copy(tree
->mark
);
1402 /* Set dim to the range dimension of "map" and abort the search.
1404 static int set_range_dim(__isl_take isl_map
*map
, void *user
)
1408 *dim
= isl_map_dim(map
, isl_dim_out
);
1414 /* Return the dimension of the range of "umap".
1415 * "umap" is assumed not to be empty and
1416 * all maps inside "umap" are assumed to have the same range.
1418 * We extract the range dimension from the first map in "umap".
1420 static int range_dim(__isl_keep isl_union_map
*umap
)
1426 if (isl_union_map_n_map(umap
) == 0)
1427 isl_die(isl_union_map_get_ctx(umap
), isl_error_internal
,
1428 "unexpected empty input", return -1);
1430 isl_union_map_foreach_map(umap
, &set_range_dim
, &dim
);
1435 /* Append an "extra" number of zeros to the range of "umap" and
1436 * return the result.
1438 static __isl_give isl_union_map
*append_range(__isl_take isl_union_map
*umap
,
1444 isl_union_pw_multi_aff
*suffix
;
1445 isl_union_map
*universe
;
1446 isl_union_map
*suffix_umap
;
1448 universe
= isl_union_map_universe(isl_union_map_copy(umap
));
1449 dom
= isl_union_map_domain(universe
);
1450 space
= isl_union_set_get_space(dom
);
1451 space
= isl_space_set_from_params(space
);
1452 space
= isl_space_add_dims(space
, isl_dim_set
, extra
);
1453 mv
= isl_multi_val_zero(space
);
1455 suffix
= isl_union_pw_multi_aff_multi_val_on_domain(dom
, mv
);
1456 suffix_umap
= isl_union_map_from_union_pw_multi_aff(suffix
);
1457 umap
= isl_union_map_flat_range_product(umap
, suffix_umap
);
1462 /* Should we skip the root of "tree" while looking for the first
1463 * descendant with schedule information?
1464 * That is, is it impossible to derive any information about
1465 * the iteration domain from this node?
1467 * We do not want to skip leaf or error nodes because there is
1468 * no point in looking any deeper from these nodes.
1470 static int domain_less(__isl_keep isl_schedule_tree
*tree
)
1472 enum isl_schedule_node_type type
;
1474 type
= isl_schedule_tree_get_type(tree
);
1476 case isl_schedule_node_band
:
1477 return isl_schedule_tree_band_n_member(tree
) == 0;
1478 case isl_schedule_node_context
:
1479 case isl_schedule_node_guard
:
1480 case isl_schedule_node_mark
:
1482 case isl_schedule_node_leaf
:
1483 case isl_schedule_node_error
:
1484 case isl_schedule_node_domain
:
1485 case isl_schedule_node_expansion
:
1486 case isl_schedule_node_filter
:
1487 case isl_schedule_node_set
:
1488 case isl_schedule_node_sequence
:
1493 /* Move down to the first descendant of "tree" that contains any schedule
1494 * information or return "leaf" if there is no such descendant.
1496 __isl_give isl_schedule_tree
*isl_schedule_tree_first_schedule_descendant(
1497 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_tree
*leaf
)
1499 while (domain_less(tree
)) {
1500 if (!isl_schedule_tree_has_children(tree
)) {
1501 isl_schedule_tree_free(tree
);
1502 return isl_schedule_tree_copy(leaf
);
1504 tree
= isl_schedule_tree_child(tree
, 0);
1510 static __isl_give isl_union_map
*subtree_schedule_extend(
1511 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
);
1513 /* Extend the schedule map "outer" with the subtree schedule
1514 * of the (single) child of "tree", if any.
1516 * If "tree" does not have any descendants (apart from those that
1517 * do not carry any schedule information), then we simply return "outer".
1518 * Otherwise, we extend the schedule map "outer" with the subtree schedule
1519 * of the single child.
1521 static __isl_give isl_union_map
*subtree_schedule_extend_child(
1522 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1524 isl_schedule_tree
*child
;
1528 return isl_union_map_free(outer
);
1529 if (!isl_schedule_tree_has_children(tree
))
1531 child
= isl_schedule_tree_get_child(tree
, 0);
1533 return isl_union_map_free(outer
);
1534 res
= subtree_schedule_extend(child
, outer
);
1535 isl_schedule_tree_free(child
);
1539 /* Extract the parameter space from one of the children of "tree",
1540 * which are assumed to be filters.
1542 static __isl_give isl_space
*extract_space_from_filter_child(
1543 __isl_keep isl_schedule_tree
*tree
)
1547 isl_schedule_tree
*child
;
1549 child
= isl_schedule_tree_list_get_schedule_tree(tree
->children
, 0);
1550 dom
= isl_schedule_tree_filter_get_filter(child
);
1551 space
= isl_union_set_get_space(dom
);
1552 isl_union_set_free(dom
);
1553 isl_schedule_tree_free(child
);
1558 /* Extend the schedule map "outer" with the subtree schedule
1559 * of a set or sequence node.
1561 * The schedule for the set or sequence node itself is composed of
1562 * pieces of the form
1570 * The first form is used if there is only a single child or
1571 * if the current node is a set node and the schedule_separate_components
1572 * option is not set.
1574 * Each of the pieces above is extended with the subtree schedule of
1575 * the child of the corresponding filter, if any, padded with zeros
1576 * to ensure that all pieces have the same range dimension.
1578 static __isl_give isl_union_map
*subtree_schedule_extend_from_children(
1579 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1588 isl_union_map
*umap
;
1593 ctx
= isl_schedule_tree_get_ctx(tree
);
1594 if (!tree
->children
)
1595 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1596 "missing children", return NULL
);
1597 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1599 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1600 "missing children", return NULL
);
1602 separate
= n
> 1 && (tree
->type
== isl_schedule_node_sequence
||
1603 isl_options_get_schedule_separate_components(ctx
));
1605 space
= extract_space_from_filter_child(tree
);
1607 umap
= isl_union_map_empty(isl_space_copy(space
));
1608 space
= isl_space_set_from_params(space
);
1610 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1611 v
= isl_val_zero(ctx
);
1613 mv
= isl_multi_val_zero(space
);
1615 dim
= isl_multi_val_dim(mv
, isl_dim_set
);
1616 for (i
= 0; i
< n
; ++i
) {
1617 isl_union_pw_multi_aff
*upma
;
1618 isl_union_map
*umap_i
;
1620 isl_schedule_tree
*child
;
1624 child
= isl_schedule_tree_list_get_schedule_tree(
1626 dom
= isl_schedule_tree_filter_get_filter(child
);
1629 mv
= isl_multi_val_set_val(mv
, 0, isl_val_copy(v
));
1630 v
= isl_val_add_ui(v
, 1);
1632 upma
= isl_union_pw_multi_aff_multi_val_on_domain(dom
,
1633 isl_multi_val_copy(mv
));
1634 umap_i
= isl_union_map_from_union_pw_multi_aff(upma
);
1635 umap_i
= isl_union_map_flat_range_product(
1636 isl_union_map_copy(outer
), umap_i
);
1637 umap_i
= subtree_schedule_extend_child(child
, umap_i
);
1638 isl_schedule_tree_free(child
);
1640 empty
= isl_union_map_is_empty(umap_i
);
1642 umap_i
= isl_union_map_free(umap_i
);
1644 isl_union_map_free(umap_i
);
1648 dim_i
= range_dim(umap_i
);
1650 umap
= isl_union_map_free(umap
);
1651 } else if (dim
< dim_i
) {
1652 umap
= append_range(umap
, dim_i
- dim
);
1654 } else if (dim_i
< dim
) {
1655 umap_i
= append_range(umap_i
, dim
- dim_i
);
1657 umap
= isl_union_map_union(umap
, umap_i
);
1661 isl_multi_val_free(mv
);
1662 isl_union_map_free(outer
);
1667 /* Extend the schedule map "outer" with the subtree schedule of "tree".
1669 * If the root of the tree is a set or a sequence, then we extend
1670 * the schedule map in subtree_schedule_extend_from_children.
1671 * Otherwise, we extend the schedule map with the partial schedule
1672 * corresponding to the root of the tree and then continue with
1673 * the single child of this root.
1674 * In the special case of an expansion, the schedule map is "extended"
1675 * by applying the expansion to the domain of the schedule map.
1677 static __isl_give isl_union_map
*subtree_schedule_extend(
1678 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1680 isl_multi_union_pw_aff
*mupa
;
1681 isl_union_map
*umap
;
1682 isl_union_set
*domain
;
1687 switch (tree
->type
) {
1688 case isl_schedule_node_error
:
1689 return isl_union_map_free(outer
);
1690 case isl_schedule_node_context
:
1691 case isl_schedule_node_guard
:
1692 case isl_schedule_node_mark
:
1693 return subtree_schedule_extend_child(tree
, outer
);
1694 case isl_schedule_node_band
:
1695 if (isl_schedule_tree_band_n_member(tree
) == 0)
1696 return subtree_schedule_extend_child(tree
, outer
);
1697 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1698 umap
= isl_union_map_from_multi_union_pw_aff(mupa
);
1699 outer
= isl_union_map_flat_range_product(outer
, umap
);
1700 umap
= subtree_schedule_extend_child(tree
, outer
);
1702 case isl_schedule_node_domain
:
1703 domain
= isl_schedule_tree_domain_get_domain(tree
);
1704 umap
= isl_union_map_from_domain(domain
);
1705 outer
= isl_union_map_flat_range_product(outer
, umap
);
1706 umap
= subtree_schedule_extend_child(tree
, outer
);
1708 case isl_schedule_node_expansion
:
1709 umap
= isl_schedule_tree_expansion_get_expansion(tree
);
1710 outer
= isl_union_map_apply_domain(outer
, umap
);
1711 umap
= subtree_schedule_extend_child(tree
, outer
);
1713 case isl_schedule_node_filter
:
1714 domain
= isl_schedule_tree_filter_get_filter(tree
);
1715 umap
= isl_union_map_from_domain(domain
);
1716 outer
= isl_union_map_flat_range_product(outer
, umap
);
1717 umap
= subtree_schedule_extend_child(tree
, outer
);
1719 case isl_schedule_node_leaf
:
1720 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1721 "leaf node should be handled by caller", return NULL
);
1722 case isl_schedule_node_set
:
1723 case isl_schedule_node_sequence
:
1724 umap
= subtree_schedule_extend_from_children(tree
, outer
);
1731 static __isl_give isl_union_set
*initial_domain(
1732 __isl_keep isl_schedule_tree
*tree
);
1734 /* Extract a universe domain from the children of the tree root "tree",
1735 * which is a set or sequence, meaning that its children are filters.
1736 * In particular, return the union of the universes of the filters.
1738 static __isl_give isl_union_set
*initial_domain_from_children(
1739 __isl_keep isl_schedule_tree
*tree
)
1743 isl_union_set
*domain
;
1745 if (!tree
->children
)
1746 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1747 "missing children", return NULL
);
1748 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1750 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1751 "missing children", return NULL
);
1753 space
= extract_space_from_filter_child(tree
);
1754 domain
= isl_union_set_empty(space
);
1756 for (i
= 0; i
< n
; ++i
) {
1757 isl_schedule_tree
*child
;
1758 isl_union_set
*domain_i
;
1760 child
= isl_schedule_tree_get_child(tree
, i
);
1761 domain_i
= initial_domain(child
);
1762 domain
= isl_union_set_union(domain
, domain_i
);
1763 isl_schedule_tree_free(child
);
1769 /* Extract a universe domain from the tree root "tree".
1770 * The caller is responsible for making sure that this node
1771 * would not be skipped by isl_schedule_tree_first_schedule_descendant
1772 * and that it is not a leaf node.
1774 static __isl_give isl_union_set
*initial_domain(
1775 __isl_keep isl_schedule_tree
*tree
)
1777 isl_multi_union_pw_aff
*mupa
;
1778 isl_union_set
*domain
;
1784 switch (tree
->type
) {
1785 case isl_schedule_node_error
:
1787 case isl_schedule_node_context
:
1788 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1789 "context node should be handled by caller",
1791 case isl_schedule_node_guard
:
1792 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1793 "guard node should be handled by caller",
1795 case isl_schedule_node_mark
:
1796 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1797 "mark node should be handled by caller",
1799 case isl_schedule_node_band
:
1800 if (isl_schedule_tree_band_n_member(tree
) == 0)
1801 isl_die(isl_schedule_tree_get_ctx(tree
),
1803 "0D band should be handled by caller",
1805 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1806 domain
= isl_multi_union_pw_aff_domain(mupa
);
1807 domain
= isl_union_set_universe(domain
);
1809 case isl_schedule_node_domain
:
1810 domain
= isl_schedule_tree_domain_get_domain(tree
);
1811 domain
= isl_union_set_universe(domain
);
1813 case isl_schedule_node_expansion
:
1814 exp
= isl_schedule_tree_expansion_get_expansion(tree
);
1815 exp
= isl_union_map_universe(exp
);
1816 domain
= isl_union_map_domain(exp
);
1818 case isl_schedule_node_filter
:
1819 domain
= isl_schedule_tree_filter_get_filter(tree
);
1820 domain
= isl_union_set_universe(domain
);
1822 case isl_schedule_node_leaf
:
1823 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1824 "leaf node should be handled by caller", return NULL
);
1825 case isl_schedule_node_set
:
1826 case isl_schedule_node_sequence
:
1827 domain
= initial_domain_from_children(tree
);
1834 /* Return the subtree schedule of a node that contains some schedule
1835 * information, i.e., a node that would not be skipped by
1836 * isl_schedule_tree_first_schedule_descendant and that is not a leaf.
1838 * If the tree contains any expansions, then the returned subtree
1839 * schedule is formulated in terms of the expanded domains.
1841 * We start with an initial zero-dimensional subtree schedule based
1842 * on the domain information in the root node and then extend it
1843 * based on the schedule information in the root node and its descendants.
1845 __isl_give isl_union_map
*isl_schedule_tree_get_subtree_schedule_union_map(
1846 __isl_keep isl_schedule_tree
*tree
)
1848 isl_union_set
*domain
;
1849 isl_union_map
*umap
;
1851 domain
= initial_domain(tree
);
1852 umap
= isl_union_map_from_domain(domain
);
1853 return subtree_schedule_extend(tree
, umap
);
1856 /* Multiply the partial schedule of the band root node of "tree"
1857 * with the factors in "mv".
1859 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale(
1860 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
1864 if (tree
->type
!= isl_schedule_node_band
)
1865 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1866 "not a band node", goto error
);
1868 tree
= isl_schedule_tree_cow(tree
);
1872 tree
->band
= isl_schedule_band_scale(tree
->band
, mv
);
1874 return isl_schedule_tree_free(tree
);
1878 isl_schedule_tree_free(tree
);
1879 isl_multi_val_free(mv
);
1883 /* Divide the partial schedule of the band root node of "tree"
1884 * by the factors in "mv".
1886 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale_down(
1887 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
1891 if (tree
->type
!= isl_schedule_node_band
)
1892 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1893 "not a band node", goto error
);
1895 tree
= isl_schedule_tree_cow(tree
);
1899 tree
->band
= isl_schedule_band_scale_down(tree
->band
, mv
);
1901 return isl_schedule_tree_free(tree
);
1905 isl_schedule_tree_free(tree
);
1906 isl_multi_val_free(mv
);
1910 /* Tile the band root node of "tree" with tile sizes "sizes".
1912 * We duplicate the band node, change the schedule of one of them
1913 * to the tile schedule and the other to the point schedule and then
1914 * attach the point band as a child to the tile band.
1916 __isl_give isl_schedule_tree
*isl_schedule_tree_band_tile(
1917 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*sizes
)
1919 isl_schedule_tree
*child
= NULL
;
1921 if (!tree
|| !sizes
)
1923 if (tree
->type
!= isl_schedule_node_band
)
1924 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1925 "not a band node", goto error
);
1927 child
= isl_schedule_tree_copy(tree
);
1928 tree
= isl_schedule_tree_cow(tree
);
1929 child
= isl_schedule_tree_cow(child
);
1930 if (!tree
|| !child
)
1933 tree
->band
= isl_schedule_band_tile(tree
->band
,
1934 isl_multi_val_copy(sizes
));
1937 child
->band
= isl_schedule_band_point(child
->band
, tree
->band
, sizes
);
1939 child
= isl_schedule_tree_free(child
);
1941 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
1945 isl_schedule_tree_free(child
);
1946 isl_schedule_tree_free(tree
);
1947 isl_multi_val_free(sizes
);
1951 /* Split the band root node of "tree" into two nested band nodes,
1952 * one with the first "pos" dimensions and
1953 * one with the remaining dimensions.
1955 __isl_give isl_schedule_tree
*isl_schedule_tree_band_split(
1956 __isl_take isl_schedule_tree
*tree
, int pos
)
1959 isl_schedule_tree
*child
;
1963 if (tree
->type
!= isl_schedule_node_band
)
1964 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1965 "not a band node", return isl_schedule_tree_free(tree
));
1967 n
= isl_schedule_tree_band_n_member(tree
);
1968 if (pos
< 0 || pos
> n
)
1969 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1970 "position out of bounds",
1971 return isl_schedule_tree_free(tree
));
1973 child
= isl_schedule_tree_copy(tree
);
1974 tree
= isl_schedule_tree_cow(tree
);
1975 child
= isl_schedule_tree_cow(child
);
1976 if (!tree
|| !child
)
1979 child
->band
= isl_schedule_band_drop(child
->band
, 0, pos
);
1980 tree
->band
= isl_schedule_band_drop(tree
->band
, pos
, n
- pos
);
1981 if (!child
->band
|| !tree
->band
)
1984 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
1988 isl_schedule_tree_free(child
);
1989 isl_schedule_tree_free(tree
);
1993 /* Attach "tree2" at each of the leaves of "tree1".
1995 * If "tree1" does not have any explicit children, then make "tree2"
1996 * its single child. Otherwise, attach "tree2" to the leaves of
1997 * each of the children of "tree1".
1999 __isl_give isl_schedule_tree
*isl_schedule_tree_append_to_leaves(
2000 __isl_take isl_schedule_tree
*tree1
,
2001 __isl_take isl_schedule_tree
*tree2
)
2005 if (!tree1
|| !tree2
)
2007 n
= isl_schedule_tree_n_children(tree1
);
2009 isl_schedule_tree_list
*list
;
2010 list
= isl_schedule_tree_list_from_schedule_tree(tree2
);
2011 tree1
= isl_schedule_tree_set_children(tree1
, list
);
2014 for (i
= 0; i
< n
; ++i
) {
2015 isl_schedule_tree
*child
;
2017 child
= isl_schedule_tree_get_child(tree1
, i
);
2018 child
= isl_schedule_tree_append_to_leaves(child
,
2019 isl_schedule_tree_copy(tree2
));
2020 tree1
= isl_schedule_tree_replace_child(tree1
, i
, child
);
2023 isl_schedule_tree_free(tree2
);
2026 isl_schedule_tree_free(tree1
);
2027 isl_schedule_tree_free(tree2
);
2031 /* Reset the user pointer on all identifiers of parameters and tuples
2032 * in the root of "tree".
2034 __isl_give isl_schedule_tree
*isl_schedule_tree_reset_user(
2035 __isl_take isl_schedule_tree
*tree
)
2037 if (isl_schedule_tree_is_leaf(tree
))
2040 tree
= isl_schedule_tree_cow(tree
);
2044 switch (tree
->type
) {
2045 case isl_schedule_node_error
:
2046 return isl_schedule_tree_free(tree
);
2047 case isl_schedule_node_band
:
2048 tree
->band
= isl_schedule_band_reset_user(tree
->band
);
2050 return isl_schedule_tree_free(tree
);
2052 case isl_schedule_node_context
:
2053 tree
->context
= isl_set_reset_user(tree
->context
);
2055 return isl_schedule_tree_free(tree
);
2057 case isl_schedule_node_domain
:
2058 tree
->domain
= isl_union_set_reset_user(tree
->domain
);
2060 return isl_schedule_tree_free(tree
);
2062 case isl_schedule_node_expansion
:
2064 isl_union_pw_multi_aff_reset_user(tree
->contraction
);
2065 tree
->expansion
= isl_union_map_reset_user(tree
->expansion
);
2066 if (!tree
->contraction
|| !tree
->expansion
)
2067 return isl_schedule_tree_free(tree
);
2069 case isl_schedule_node_filter
:
2070 tree
->filter
= isl_union_set_reset_user(tree
->filter
);
2072 return isl_schedule_tree_free(tree
);
2074 case isl_schedule_node_guard
:
2075 tree
->guard
= isl_set_reset_user(tree
->guard
);
2077 return isl_schedule_tree_free(tree
);
2079 case isl_schedule_node_leaf
:
2080 case isl_schedule_node_mark
:
2081 case isl_schedule_node_sequence
:
2082 case isl_schedule_node_set
:
2089 /* Align the parameters of the root of "tree" to those of "space".
2091 __isl_give isl_schedule_tree
*isl_schedule_tree_align_params(
2092 __isl_take isl_schedule_tree
*tree
, __isl_take isl_space
*space
)
2097 if (isl_schedule_tree_is_leaf(tree
)) {
2098 isl_space_free(space
);
2102 tree
= isl_schedule_tree_cow(tree
);
2106 switch (tree
->type
) {
2107 case isl_schedule_node_error
:
2109 case isl_schedule_node_band
:
2110 tree
->band
= isl_schedule_band_align_params(tree
->band
, space
);
2112 return isl_schedule_tree_free(tree
);
2114 case isl_schedule_node_context
:
2115 tree
->context
= isl_set_align_params(tree
->context
, space
);
2117 return isl_schedule_tree_free(tree
);
2119 case isl_schedule_node_domain
:
2120 tree
->domain
= isl_union_set_align_params(tree
->domain
, space
);
2122 return isl_schedule_tree_free(tree
);
2124 case isl_schedule_node_expansion
:
2126 isl_union_pw_multi_aff_align_params(tree
->contraction
,
2127 isl_space_copy(space
));
2128 tree
->expansion
= isl_union_map_align_params(tree
->expansion
,
2130 if (!tree
->contraction
|| !tree
->expansion
)
2131 return isl_schedule_tree_free(tree
);
2133 case isl_schedule_node_filter
:
2134 tree
->filter
= isl_union_set_align_params(tree
->filter
, space
);
2136 return isl_schedule_tree_free(tree
);
2138 case isl_schedule_node_guard
:
2139 tree
->guard
= isl_set_align_params(tree
->guard
, space
);
2141 return isl_schedule_tree_free(tree
);
2143 case isl_schedule_node_leaf
:
2144 case isl_schedule_node_mark
:
2145 case isl_schedule_node_sequence
:
2146 case isl_schedule_node_set
:
2147 isl_space_free(space
);
2153 isl_space_free(space
);
2154 isl_schedule_tree_free(tree
);
2158 /* Does "tree" involve the iteration domain?
2159 * That is, does it need to be modified
2160 * by isl_schedule_tree_pullback_union_pw_multi_aff?
2162 static int involves_iteration_domain(__isl_keep isl_schedule_tree
*tree
)
2167 switch (tree
->type
) {
2168 case isl_schedule_node_error
:
2170 case isl_schedule_node_band
:
2171 case isl_schedule_node_domain
:
2172 case isl_schedule_node_expansion
:
2173 case isl_schedule_node_filter
:
2175 case isl_schedule_node_context
:
2176 case isl_schedule_node_leaf
:
2177 case isl_schedule_node_guard
:
2178 case isl_schedule_node_mark
:
2179 case isl_schedule_node_sequence
:
2180 case isl_schedule_node_set
:
2185 /* Compute the pullback of the root node of "tree" by the function
2186 * represented by "upma".
2187 * In other words, plug in "upma" in the iteration domains of
2188 * the root node of "tree".
2189 * We currently do not handle expansion nodes.
2191 * We first check if the root node involves any iteration domains.
2192 * If so, we handle the specific cases.
2194 __isl_give isl_schedule_tree
*isl_schedule_tree_pullback_union_pw_multi_aff(
2195 __isl_take isl_schedule_tree
*tree
,
2196 __isl_take isl_union_pw_multi_aff
*upma
)
2203 involves
= involves_iteration_domain(tree
);
2207 isl_union_pw_multi_aff_free(upma
);
2211 tree
= isl_schedule_tree_cow(tree
);
2215 if (tree
->type
== isl_schedule_node_band
) {
2216 tree
->band
= isl_schedule_band_pullback_union_pw_multi_aff(
2219 return isl_schedule_tree_free(tree
);
2220 } else if (tree
->type
== isl_schedule_node_domain
) {
2222 isl_union_set_preimage_union_pw_multi_aff(tree
->domain
,
2225 return isl_schedule_tree_free(tree
);
2226 } else if (tree
->type
== isl_schedule_node_expansion
) {
2227 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_unsupported
,
2228 "cannot pullback expansion node", goto error
);
2229 } else if (tree
->type
== isl_schedule_node_filter
) {
2231 isl_union_set_preimage_union_pw_multi_aff(tree
->filter
,
2234 return isl_schedule_tree_free(tree
);
2239 isl_union_pw_multi_aff_free(upma
);
2240 isl_schedule_tree_free(tree
);
2244 /* Compute the gist of the band tree root with respect to "context".
2246 __isl_give isl_schedule_tree
*isl_schedule_tree_band_gist(
2247 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*context
)
2251 if (tree
->type
!= isl_schedule_node_band
)
2252 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2253 "not a band node", goto error
);
2254 tree
= isl_schedule_tree_cow(tree
);
2258 tree
->band
= isl_schedule_band_gist(tree
->band
, context
);
2260 return isl_schedule_tree_free(tree
);
2263 isl_union_set_free(context
);
2264 isl_schedule_tree_free(tree
);
2268 /* Are any members in "band" marked coincident?
2270 static int any_coincident(__isl_keep isl_schedule_band
*band
)
2274 n
= isl_schedule_band_n_member(band
);
2275 for (i
= 0; i
< n
; ++i
)
2276 if (isl_schedule_band_member_get_coincident(band
, i
))
2282 /* Print the band node "band" to "p".
2284 * The permutable and coincident properties are only printed if they
2285 * are different from the defaults.
2286 * The coincident property is always printed in YAML flow style.
2288 static __isl_give isl_printer
*print_tree_band(__isl_take isl_printer
*p
,
2289 __isl_keep isl_schedule_band
*band
)
2291 isl_union_set
*options
;
2294 p
= isl_printer_print_str(p
, "schedule");
2295 p
= isl_printer_yaml_next(p
);
2296 p
= isl_printer_print_str(p
, "\"");
2297 p
= isl_printer_print_multi_union_pw_aff(p
, band
->mupa
);
2298 p
= isl_printer_print_str(p
, "\"");
2299 if (isl_schedule_band_get_permutable(band
)) {
2300 p
= isl_printer_yaml_next(p
);
2301 p
= isl_printer_print_str(p
, "permutable");
2302 p
= isl_printer_yaml_next(p
);
2303 p
= isl_printer_print_int(p
, 1);
2305 if (any_coincident(band
)) {
2309 p
= isl_printer_yaml_next(p
);
2310 p
= isl_printer_print_str(p
, "coincident");
2311 p
= isl_printer_yaml_next(p
);
2312 style
= isl_printer_get_yaml_style(p
);
2313 p
= isl_printer_set_yaml_style(p
, ISL_YAML_STYLE_FLOW
);
2314 p
= isl_printer_yaml_start_sequence(p
);
2315 n
= isl_schedule_band_n_member(band
);
2316 for (i
= 0; i
< n
; ++i
) {
2317 p
= isl_printer_print_int(p
,
2318 isl_schedule_band_member_get_coincident(band
, i
));
2319 p
= isl_printer_yaml_next(p
);
2321 p
= isl_printer_yaml_end_sequence(p
);
2322 p
= isl_printer_set_yaml_style(p
, style
);
2324 options
= isl_schedule_band_get_ast_build_options(band
);
2325 empty
= isl_union_set_is_empty(options
);
2327 p
= isl_printer_free(p
);
2329 p
= isl_printer_yaml_next(p
);
2330 p
= isl_printer_print_str(p
, "options");
2331 p
= isl_printer_yaml_next(p
);
2332 p
= isl_printer_print_str(p
, "\"");
2333 p
= isl_printer_print_union_set(p
, options
);
2334 p
= isl_printer_print_str(p
, "\"");
2336 isl_union_set_free(options
);
2341 /* Print "tree" to "p".
2343 * If "n_ancestor" is non-negative, then "child_pos" contains the child
2344 * positions of a descendant of the current node that should be marked
2345 * (by the comment "YOU ARE HERE"). In particular, if "n_ancestor"
2346 * is zero, then the current node should be marked.
2347 * The marking is only printed in YAML block format.
2349 * Implicit leaf nodes are not printed, except if they correspond
2350 * to the node that should be marked.
2352 __isl_give isl_printer
*isl_printer_print_schedule_tree_mark(
2353 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
,
2354 int n_ancestor
, int *child_pos
)
2360 block
= isl_printer_get_yaml_style(p
) == ISL_YAML_STYLE_BLOCK
;
2362 p
= isl_printer_yaml_start_mapping(p
);
2363 if (n_ancestor
== 0 && block
) {
2364 p
= isl_printer_print_str(p
, "# YOU ARE HERE");
2365 p
= isl_printer_end_line(p
);
2366 p
= isl_printer_start_line(p
);
2368 switch (tree
->type
) {
2369 case isl_schedule_node_error
:
2370 p
= isl_printer_print_str(p
, "ERROR");
2372 case isl_schedule_node_leaf
:
2373 p
= isl_printer_print_str(p
, "leaf");
2375 case isl_schedule_node_sequence
:
2376 p
= isl_printer_print_str(p
, "sequence");
2379 case isl_schedule_node_set
:
2380 p
= isl_printer_print_str(p
, "set");
2383 case isl_schedule_node_context
:
2384 p
= isl_printer_print_str(p
, "context");
2385 p
= isl_printer_yaml_next(p
);
2386 p
= isl_printer_print_str(p
, "\"");
2387 p
= isl_printer_print_set(p
, tree
->context
);
2388 p
= isl_printer_print_str(p
, "\"");
2390 case isl_schedule_node_domain
:
2391 p
= isl_printer_print_str(p
, "domain");
2392 p
= isl_printer_yaml_next(p
);
2393 p
= isl_printer_print_str(p
, "\"");
2394 p
= isl_printer_print_union_set(p
, tree
->domain
);
2395 p
= isl_printer_print_str(p
, "\"");
2397 case isl_schedule_node_expansion
:
2398 p
= isl_printer_print_str(p
, "contraction");
2399 p
= isl_printer_yaml_next(p
);
2400 p
= isl_printer_print_str(p
, "\"");
2401 p
= isl_printer_print_union_pw_multi_aff(p
, tree
->contraction
);
2402 p
= isl_printer_print_str(p
, "\"");
2403 p
= isl_printer_yaml_next(p
);
2404 p
= isl_printer_print_str(p
, "expansion");
2405 p
= isl_printer_yaml_next(p
);
2406 p
= isl_printer_print_str(p
, "\"");
2407 p
= isl_printer_print_union_map(p
, tree
->expansion
);
2408 p
= isl_printer_print_str(p
, "\"");
2410 case isl_schedule_node_filter
:
2411 p
= isl_printer_print_str(p
, "filter");
2412 p
= isl_printer_yaml_next(p
);
2413 p
= isl_printer_print_str(p
, "\"");
2414 p
= isl_printer_print_union_set(p
, tree
->filter
);
2415 p
= isl_printer_print_str(p
, "\"");
2417 case isl_schedule_node_guard
:
2418 p
= isl_printer_print_str(p
, "guard");
2419 p
= isl_printer_yaml_next(p
);
2420 p
= isl_printer_print_str(p
, "\"");
2421 p
= isl_printer_print_set(p
, tree
->guard
);
2422 p
= isl_printer_print_str(p
, "\"");
2424 case isl_schedule_node_mark
:
2425 p
= isl_printer_print_str(p
, "mark");
2426 p
= isl_printer_yaml_next(p
);
2427 p
= isl_printer_print_str(p
, "\"");
2428 p
= isl_printer_print_str(p
, isl_id_get_name(tree
->mark
));
2429 p
= isl_printer_print_str(p
, "\"");
2431 case isl_schedule_node_band
:
2432 p
= print_tree_band(p
, tree
->band
);
2435 p
= isl_printer_yaml_next(p
);
2437 if (!tree
->children
) {
2438 if (n_ancestor
> 0 && block
) {
2439 isl_schedule_tree
*leaf
;
2441 p
= isl_printer_print_str(p
, "child");
2442 p
= isl_printer_yaml_next(p
);
2443 leaf
= isl_schedule_tree_leaf(isl_printer_get_ctx(p
));
2444 p
= isl_printer_print_schedule_tree_mark(p
,
2446 isl_schedule_tree_free(leaf
);
2447 p
= isl_printer_yaml_next(p
);
2449 return isl_printer_yaml_end_mapping(p
);
2453 p
= isl_printer_yaml_start_sequence(p
);
2455 p
= isl_printer_print_str(p
, "child");
2456 p
= isl_printer_yaml_next(p
);
2459 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
2460 for (i
= 0; i
< n
; ++i
) {
2461 isl_schedule_tree
*t
;
2463 t
= isl_schedule_tree_get_child(tree
, i
);
2464 if (n_ancestor
> 0 && child_pos
[0] == i
)
2465 p
= isl_printer_print_schedule_tree_mark(p
, t
,
2466 n_ancestor
- 1, child_pos
+ 1);
2468 p
= isl_printer_print_schedule_tree_mark(p
, t
,
2470 isl_schedule_tree_free(t
);
2472 p
= isl_printer_yaml_next(p
);
2476 p
= isl_printer_yaml_end_sequence(p
);
2477 p
= isl_printer_yaml_end_mapping(p
);
2482 /* Print "tree" to "p".
2484 __isl_give isl_printer
*isl_printer_print_schedule_tree(
2485 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
)
2487 return isl_printer_print_schedule_tree_mark(p
, tree
, -1, NULL
);
2490 void isl_schedule_tree_dump(__isl_keep isl_schedule_tree
*tree
)
2493 isl_printer
*printer
;
2498 ctx
= isl_schedule_tree_get_ctx(tree
);
2499 printer
= isl_printer_to_file(ctx
, stderr
);
2500 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
2501 printer
= isl_printer_print_schedule_tree(printer
, tree
);
2503 isl_printer_free(printer
);