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_leaf
:
111 case isl_schedule_node_sequence
:
112 case isl_schedule_node_set
:
116 if (tree
->children
) {
117 dup
->children
= isl_schedule_tree_list_copy(tree
->children
);
119 return isl_schedule_tree_free(dup
);
121 dup
->anchored
= tree
->anchored
;
126 /* Return an isl_schedule_tree that is equal to "tree" and that has only
127 * a single reference.
129 * This function is called before a tree is modified.
130 * A static tree (with negative reference count) should never be modified,
131 * so it is not allowed to call this function on a static tree.
133 __isl_give isl_schedule_tree
*isl_schedule_tree_cow(
134 __isl_take isl_schedule_tree
*tree
)
140 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
141 "static trees cannot be modified",
142 return isl_schedule_tree_free(tree
));
147 return isl_schedule_tree_dup(tree
);
150 /* Return a new reference to "tree".
152 * A static tree (with negative reference count) does not keep track
153 * of the number of references and should not be modified.
155 __isl_give isl_schedule_tree
*isl_schedule_tree_copy(
156 __isl_keep isl_schedule_tree
*tree
)
168 /* Free "tree" and return NULL.
170 __isl_null isl_schedule_tree
*isl_schedule_tree_free(
171 __isl_take isl_schedule_tree
*tree
)
180 switch (tree
->type
) {
181 case isl_schedule_node_band
:
182 isl_schedule_band_free(tree
->band
);
184 case isl_schedule_node_context
:
185 isl_set_free(tree
->context
);
187 case isl_schedule_node_domain
:
188 isl_union_set_free(tree
->domain
);
190 case isl_schedule_node_expansion
:
191 isl_union_pw_multi_aff_free(tree
->contraction
);
192 isl_union_map_free(tree
->expansion
);
194 case isl_schedule_node_filter
:
195 isl_union_set_free(tree
->filter
);
197 case isl_schedule_node_sequence
:
198 case isl_schedule_node_set
:
199 case isl_schedule_node_error
:
200 case isl_schedule_node_leaf
:
203 isl_schedule_tree_list_free(tree
->children
);
204 isl_ctx_deref(tree
->ctx
);
210 /* Create and return a new leaf schedule tree.
212 __isl_give isl_schedule_tree
*isl_schedule_tree_leaf(isl_ctx
*ctx
)
214 return isl_schedule_tree_alloc(ctx
, isl_schedule_node_leaf
);
217 /* Create a new band schedule tree referring to "band"
220 __isl_give isl_schedule_tree
*isl_schedule_tree_from_band(
221 __isl_take isl_schedule_band
*band
)
224 isl_schedule_tree
*tree
;
229 ctx
= isl_schedule_band_get_ctx(band
);
230 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_band
);
235 tree
->anchored
= isl_schedule_band_is_anchored(band
);
239 isl_schedule_band_free(band
);
243 /* Create a new context schedule tree with the given context and no children.
244 * Since the context references the outer schedule dimension,
245 * the tree is anchored.
247 __isl_give isl_schedule_tree
*isl_schedule_tree_from_context(
248 __isl_take isl_set
*context
)
251 isl_schedule_tree
*tree
;
256 ctx
= isl_set_get_ctx(context
);
257 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_context
);
261 tree
->context
= context
;
266 isl_set_free(context
);
270 /* Create a new domain schedule tree with the given domain and no children.
272 __isl_give isl_schedule_tree
*isl_schedule_tree_from_domain(
273 __isl_take isl_union_set
*domain
)
276 isl_schedule_tree
*tree
;
281 ctx
= isl_union_set_get_ctx(domain
);
282 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_domain
);
286 tree
->domain
= domain
;
290 isl_union_set_free(domain
);
294 /* Create a new expansion schedule tree with the given contraction and
295 * expansion and no children.
297 __isl_give isl_schedule_tree
*isl_schedule_tree_from_expansion(
298 __isl_take isl_union_pw_multi_aff
*contraction
,
299 __isl_take isl_union_map
*expansion
)
302 isl_schedule_tree
*tree
;
304 if (!contraction
|| !expansion
)
307 ctx
= isl_union_map_get_ctx(expansion
);
308 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_expansion
);
312 tree
->contraction
= contraction
;
313 tree
->expansion
= expansion
;
317 isl_union_pw_multi_aff_free(contraction
);
318 isl_union_map_free(expansion
);
322 /* Create a new filter schedule tree with the given filter and no children.
324 __isl_give isl_schedule_tree
*isl_schedule_tree_from_filter(
325 __isl_take isl_union_set
*filter
)
328 isl_schedule_tree
*tree
;
333 ctx
= isl_union_set_get_ctx(filter
);
334 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_filter
);
338 tree
->filter
= filter
;
342 isl_union_set_free(filter
);
346 /* Does "tree" have any node that depends on its position
347 * in the complete schedule tree?
349 int isl_schedule_tree_is_subtree_anchored(__isl_keep isl_schedule_tree
*tree
)
351 return tree
? tree
->anchored
: -1;
354 /* Does the root node of "tree" depend on its position in the complete
356 * Band nodes may be anchored depending on the associated AST build options.
357 * Context nodes are always anchored.
359 int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree
*tree
)
364 switch (isl_schedule_tree_get_type(tree
)) {
365 case isl_schedule_node_error
:
367 case isl_schedule_node_band
:
368 return isl_schedule_band_is_anchored(tree
->band
);
369 case isl_schedule_node_context
:
371 case isl_schedule_node_domain
:
372 case isl_schedule_node_expansion
:
373 case isl_schedule_node_filter
:
374 case isl_schedule_node_leaf
:
375 case isl_schedule_node_sequence
:
376 case isl_schedule_node_set
:
381 /* Update the anchored field of "tree" based on whether the root node
382 * itself in anchored and the anchored fields of the children.
384 * This function should be called whenever the children of a tree node
385 * are changed or the anchoredness of the tree root itself changes.
387 __isl_give isl_schedule_tree
*isl_schedule_tree_update_anchored(
388 __isl_take isl_schedule_tree
*tree
)
396 anchored
= isl_schedule_tree_is_anchored(tree
);
398 return isl_schedule_tree_free(tree
);
400 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
401 for (i
= 0; !anchored
&& i
< n
; ++i
) {
402 isl_schedule_tree
*child
;
404 child
= isl_schedule_tree_get_child(tree
, i
);
406 return isl_schedule_tree_free(tree
);
407 anchored
= child
->anchored
;
408 isl_schedule_tree_free(child
);
411 if (anchored
== tree
->anchored
)
413 tree
= isl_schedule_tree_cow(tree
);
416 tree
->anchored
= anchored
;
420 /* Create a new tree of the given type (isl_schedule_node_sequence or
421 * isl_schedule_node_set) with the given children.
423 __isl_give isl_schedule_tree
*isl_schedule_tree_from_children(
424 enum isl_schedule_node_type type
,
425 __isl_take isl_schedule_tree_list
*list
)
428 isl_schedule_tree
*tree
;
433 ctx
= isl_schedule_tree_list_get_ctx(list
);
434 tree
= isl_schedule_tree_alloc(ctx
, type
);
438 tree
->children
= list
;
439 tree
= isl_schedule_tree_update_anchored(tree
);
443 isl_schedule_tree_list_free(list
);
447 /* Construct a tree with a root node of type "type" and as children
448 * "tree1" and "tree2".
449 * If the root of one (or both) of the input trees is itself of type "type",
450 * then the tree is replaced by its children.
452 __isl_give isl_schedule_tree
*isl_schedule_tree_from_pair(
453 enum isl_schedule_node_type type
, __isl_take isl_schedule_tree
*tree1
,
454 __isl_take isl_schedule_tree
*tree2
)
457 isl_schedule_tree_list
*list
;
459 if (!tree1
|| !tree2
)
462 ctx
= isl_schedule_tree_get_ctx(tree1
);
463 if (isl_schedule_tree_get_type(tree1
) == type
) {
464 list
= isl_schedule_tree_list_copy(tree1
->children
);
465 isl_schedule_tree_free(tree1
);
467 list
= isl_schedule_tree_list_alloc(ctx
, 2);
468 list
= isl_schedule_tree_list_add(list
, tree1
);
470 if (isl_schedule_tree_get_type(tree2
) == type
) {
471 isl_schedule_tree_list
*children
;
473 children
= isl_schedule_tree_list_copy(tree2
->children
);
474 list
= isl_schedule_tree_list_concat(list
, children
);
475 isl_schedule_tree_free(tree2
);
477 list
= isl_schedule_tree_list_add(list
, tree2
);
480 return isl_schedule_tree_from_children(type
, list
);
482 isl_schedule_tree_free(tree1
);
483 isl_schedule_tree_free(tree2
);
487 /* Return the isl_ctx to which "tree" belongs.
489 isl_ctx
*isl_schedule_tree_get_ctx(__isl_keep isl_schedule_tree
*tree
)
491 return tree
? tree
->ctx
: NULL
;
494 /* Return the type of the root of the tree or isl_schedule_node_error
497 enum isl_schedule_node_type
isl_schedule_tree_get_type(
498 __isl_keep isl_schedule_tree
*tree
)
500 return tree
? tree
->type
: isl_schedule_node_error
;
503 /* Are "tree1" and "tree2" obviously equal to each other?
505 int isl_schedule_tree_plain_is_equal(__isl_keep isl_schedule_tree
*tree1
,
506 __isl_keep isl_schedule_tree
*tree2
)
511 if (!tree1
|| !tree2
)
515 if (tree1
->type
!= tree2
->type
)
518 switch (tree1
->type
) {
519 case isl_schedule_node_band
:
520 equal
= isl_schedule_band_plain_is_equal(tree1
->band
,
523 case isl_schedule_node_context
:
524 equal
= isl_set_is_equal(tree1
->context
, tree2
->context
);
526 case isl_schedule_node_domain
:
527 equal
= isl_union_set_is_equal(tree1
->domain
, tree2
->domain
);
529 case isl_schedule_node_expansion
:
530 equal
= isl_union_map_is_equal(tree1
->expansion
,
532 if (equal
>= 0 && equal
)
533 equal
= isl_union_pw_multi_aff_plain_is_equal(
534 tree1
->contraction
, tree2
->contraction
);
536 case isl_schedule_node_filter
:
537 equal
= isl_union_set_is_equal(tree1
->filter
, tree2
->filter
);
539 case isl_schedule_node_leaf
:
540 case isl_schedule_node_sequence
:
541 case isl_schedule_node_set
:
544 case isl_schedule_node_error
:
549 if (equal
< 0 || !equal
)
552 n
= isl_schedule_tree_n_children(tree1
);
553 if (n
!= isl_schedule_tree_n_children(tree2
))
555 for (i
= 0; i
< n
; ++i
) {
556 isl_schedule_tree
*child1
, *child2
;
558 child1
= isl_schedule_tree_get_child(tree1
, i
);
559 child2
= isl_schedule_tree_get_child(tree2
, i
);
560 equal
= isl_schedule_tree_plain_is_equal(child1
, child2
);
561 isl_schedule_tree_free(child1
);
562 isl_schedule_tree_free(child2
);
564 if (equal
< 0 || !equal
)
571 /* Does "tree" have any children, other than an implicit leaf.
573 int isl_schedule_tree_has_children(__isl_keep isl_schedule_tree
*tree
)
578 return tree
->children
!= NULL
;
581 /* Return the number of children of "tree", excluding implicit leaves.
583 int isl_schedule_tree_n_children(__isl_keep isl_schedule_tree
*tree
)
588 return isl_schedule_tree_list_n_schedule_tree(tree
->children
);
591 /* Return a copy of the (explicit) child at position "pos" of "tree".
593 __isl_give isl_schedule_tree
*isl_schedule_tree_get_child(
594 __isl_keep isl_schedule_tree
*tree
, int pos
)
599 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
600 "schedule tree has no explicit children", return NULL
);
601 return isl_schedule_tree_list_get_schedule_tree(tree
->children
, pos
);
604 /* Return a copy of the (explicit) child at position "pos" of "tree" and
607 __isl_give isl_schedule_tree
*isl_schedule_tree_child(
608 __isl_take isl_schedule_tree
*tree
, int pos
)
610 isl_schedule_tree
*child
;
612 child
= isl_schedule_tree_get_child(tree
, pos
);
613 isl_schedule_tree_free(tree
);
617 /* Remove all (explicit) children from "tree".
619 __isl_give isl_schedule_tree
*isl_schedule_tree_reset_children(
620 __isl_take isl_schedule_tree
*tree
)
622 tree
= isl_schedule_tree_cow(tree
);
625 tree
->children
= isl_schedule_tree_list_free(tree
->children
);
629 /* Remove the child at position "pos" from the children of "tree".
630 * If there was only one child to begin with, then remove all children.
632 __isl_give isl_schedule_tree
*isl_schedule_tree_drop_child(
633 __isl_take isl_schedule_tree
*tree
, int pos
)
637 tree
= isl_schedule_tree_cow(tree
);
641 if (!isl_schedule_tree_has_children(tree
))
642 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
643 "tree does not have any explicit children",
644 return isl_schedule_tree_free(tree
));
645 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
646 if (pos
< 0 || pos
>= n
)
647 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
648 "position out of bounds",
649 return isl_schedule_tree_free(tree
));
651 return isl_schedule_tree_reset_children(tree
);
653 tree
->children
= isl_schedule_tree_list_drop(tree
->children
, pos
, 1);
655 return isl_schedule_tree_free(tree
);
660 /* Replace the child at position "pos" of "tree" by "child".
662 * If the new child is a leaf, then it is not explicitly
663 * recorded in the list of children. Instead, the list of children
664 * (which is assumed to have only one element) is removed.
665 * Note that the children of set and sequence nodes are always
666 * filters, so they cannot be replaced by empty trees.
668 __isl_give isl_schedule_tree
*isl_schedule_tree_replace_child(
669 __isl_take isl_schedule_tree
*tree
, int pos
,
670 __isl_take isl_schedule_tree
*child
)
672 tree
= isl_schedule_tree_cow(tree
);
676 if (isl_schedule_tree_is_leaf(child
)) {
677 isl_schedule_tree_free(child
);
678 if (!tree
->children
&& pos
== 0)
680 if (isl_schedule_tree_n_children(tree
) != 1)
681 isl_die(isl_schedule_tree_get_ctx(tree
),
683 "can only replace single child by leaf",
685 return isl_schedule_tree_reset_children(tree
);
688 if (!tree
->children
&& pos
== 0)
690 isl_schedule_tree_list_from_schedule_tree(child
);
692 tree
->children
= isl_schedule_tree_list_set_schedule_tree(
693 tree
->children
, pos
, child
);
696 return isl_schedule_tree_free(tree
);
697 tree
= isl_schedule_tree_update_anchored(tree
);
701 isl_schedule_tree_free(tree
);
702 isl_schedule_tree_free(child
);
706 /* Replace the (explicit) children of "tree" by "children"?
708 __isl_give isl_schedule_tree
*isl_schedule_tree_set_children(
709 __isl_take isl_schedule_tree
*tree
,
710 __isl_take isl_schedule_tree_list
*children
)
712 tree
= isl_schedule_tree_cow(tree
);
713 if (!tree
|| !children
)
715 isl_schedule_tree_list_free(tree
->children
);
716 tree
->children
= children
;
719 isl_schedule_tree_free(tree
);
720 isl_schedule_tree_list_free(children
);
724 /* Create a new band schedule tree referring to "band"
725 * with "tree" as single child.
727 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_band(
728 __isl_take isl_schedule_tree
*tree
, __isl_take isl_schedule_band
*band
)
730 isl_schedule_tree
*res
;
732 res
= isl_schedule_tree_from_band(band
);
733 return isl_schedule_tree_replace_child(res
, 0, tree
);
736 /* Create a new context schedule tree with the given context and
737 * with "tree" as single child.
739 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_context(
740 __isl_take isl_schedule_tree
*tree
, __isl_take isl_set
*context
)
742 isl_schedule_tree
*res
;
744 res
= isl_schedule_tree_from_context(context
);
745 return isl_schedule_tree_replace_child(res
, 0, tree
);
748 /* Create a new domain schedule tree with the given domain and
749 * with "tree" as single child.
751 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_domain(
752 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
754 isl_schedule_tree
*res
;
756 res
= isl_schedule_tree_from_domain(domain
);
757 return isl_schedule_tree_replace_child(res
, 0, tree
);
760 /* Create a new expansion schedule tree with the given contraction and
761 * expansion and with "tree" as single child.
763 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_expansion(
764 __isl_take isl_schedule_tree
*tree
,
765 __isl_take isl_union_pw_multi_aff
*contraction
,
766 __isl_take isl_union_map
*expansion
)
768 isl_schedule_tree
*res
;
770 res
= isl_schedule_tree_from_expansion(contraction
, expansion
);
771 return isl_schedule_tree_replace_child(res
, 0, tree
);
774 /* Create a new filter schedule tree with the given filter and single child.
776 * If the root of "tree" is itself a filter node, then the two
777 * filter nodes are merged into one node.
779 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_filter(
780 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
782 isl_schedule_tree
*res
;
784 if (isl_schedule_tree_get_type(tree
) == isl_schedule_node_filter
) {
785 isl_union_set
*tree_filter
;
787 tree_filter
= isl_schedule_tree_filter_get_filter(tree
);
788 tree_filter
= isl_union_set_intersect(tree_filter
, filter
);
789 tree
= isl_schedule_tree_filter_set_filter(tree
, tree_filter
);
793 res
= isl_schedule_tree_from_filter(filter
);
794 return isl_schedule_tree_replace_child(res
, 0, tree
);
797 /* Insert a filter node with filter set "filter"
798 * in each of the children of "tree".
800 __isl_give isl_schedule_tree
*isl_schedule_tree_children_insert_filter(
801 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
805 if (!tree
|| !filter
)
808 n
= isl_schedule_tree_n_children(tree
);
809 for (i
= 0; i
< n
; ++i
) {
810 isl_schedule_tree
*child
;
812 child
= isl_schedule_tree_get_child(tree
, i
);
813 child
= isl_schedule_tree_insert_filter(child
,
814 isl_union_set_copy(filter
));
815 tree
= isl_schedule_tree_replace_child(tree
, i
, child
);
818 isl_union_set_free(filter
);
821 isl_union_set_free(filter
);
822 isl_schedule_tree_free(tree
);
826 /* Return the number of members in the band tree root.
828 unsigned isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree
*tree
)
833 if (tree
->type
!= isl_schedule_node_band
)
834 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
835 "not a band node", return 0);
837 return isl_schedule_band_n_member(tree
->band
);
840 /* Is the band member at position "pos" of the band tree root
843 int isl_schedule_tree_band_member_get_coincident(
844 __isl_keep isl_schedule_tree
*tree
, int pos
)
849 if (tree
->type
!= isl_schedule_node_band
)
850 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
851 "not a band node", return -1);
853 return isl_schedule_band_member_get_coincident(tree
->band
, pos
);
856 /* Mark the given band member as being coincident or not
857 * according to "coincident".
859 __isl_give isl_schedule_tree
*isl_schedule_tree_band_member_set_coincident(
860 __isl_take isl_schedule_tree
*tree
, int pos
, int coincident
)
864 if (tree
->type
!= isl_schedule_node_band
)
865 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
866 "not a band node", return isl_schedule_tree_free(tree
));
867 if (isl_schedule_tree_band_member_get_coincident(tree
, pos
) ==
870 tree
= isl_schedule_tree_cow(tree
);
874 tree
->band
= isl_schedule_band_member_set_coincident(tree
->band
, pos
,
877 return isl_schedule_tree_free(tree
);
881 /* Is the band tree root marked permutable?
883 int isl_schedule_tree_band_get_permutable(__isl_keep isl_schedule_tree
*tree
)
888 if (tree
->type
!= isl_schedule_node_band
)
889 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
890 "not a band node", return -1);
892 return isl_schedule_band_get_permutable(tree
->band
);
895 /* Mark the band tree root permutable or not according to "permutable"?
897 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_permutable(
898 __isl_take isl_schedule_tree
*tree
, int permutable
)
902 if (tree
->type
!= isl_schedule_node_band
)
903 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
904 "not a band node", return isl_schedule_tree_free(tree
));
905 if (isl_schedule_tree_band_get_permutable(tree
) == permutable
)
907 tree
= isl_schedule_tree_cow(tree
);
911 tree
->band
= isl_schedule_band_set_permutable(tree
->band
, permutable
);
913 return isl_schedule_tree_free(tree
);
917 /* Return the schedule space of the band tree root.
919 __isl_give isl_space
*isl_schedule_tree_band_get_space(
920 __isl_keep isl_schedule_tree
*tree
)
925 if (tree
->type
!= isl_schedule_node_band
)
926 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
927 "not a band node", return NULL
);
929 return isl_schedule_band_get_space(tree
->band
);
932 /* Return the schedule of the band tree root in isolation.
934 __isl_give isl_multi_union_pw_aff
*isl_schedule_tree_band_get_partial_schedule(
935 __isl_keep isl_schedule_tree
*tree
)
940 if (tree
->type
!= isl_schedule_node_band
)
941 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
942 "not a band node", return NULL
);
944 return isl_schedule_band_get_partial_schedule(tree
->band
);
947 /* Return the loop AST generation type for the band member
948 * of the band tree root at position "pos".
950 enum isl_ast_loop_type
isl_schedule_tree_band_member_get_ast_loop_type(
951 __isl_keep isl_schedule_tree
*tree
, int pos
)
954 return isl_ast_loop_error
;
956 if (tree
->type
!= isl_schedule_node_band
)
957 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
958 "not a band node", return isl_ast_loop_error
);
960 return isl_schedule_band_member_get_ast_loop_type(tree
->band
, pos
);
963 /* Set the loop AST generation type for the band member of the band tree root
964 * at position "pos" to "type".
966 __isl_give isl_schedule_tree
*isl_schedule_tree_band_member_set_ast_loop_type(
967 __isl_take isl_schedule_tree
*tree
, int pos
,
968 enum isl_ast_loop_type type
)
970 tree
= isl_schedule_tree_cow(tree
);
974 if (tree
->type
!= isl_schedule_node_band
)
975 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
976 "not a band node", return isl_schedule_tree_free(tree
));
978 tree
->band
= isl_schedule_band_member_set_ast_loop_type(tree
->band
,
981 return isl_schedule_tree_free(tree
);
986 /* Return the loop AST generation type for the band member
987 * of the band tree root at position "pos" for the isolated part.
989 enum isl_ast_loop_type
isl_schedule_tree_band_member_get_isolate_ast_loop_type(
990 __isl_keep isl_schedule_tree
*tree
, int pos
)
993 return isl_ast_loop_error
;
995 if (tree
->type
!= isl_schedule_node_band
)
996 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
997 "not a band node", return isl_ast_loop_error
);
999 return isl_schedule_band_member_get_isolate_ast_loop_type(tree
->band
,
1003 /* Set the loop AST generation type for the band member of the band tree root
1004 * at position "pos" for the isolated part to "type".
1006 __isl_give isl_schedule_tree
*
1007 isl_schedule_tree_band_member_set_isolate_ast_loop_type(
1008 __isl_take isl_schedule_tree
*tree
, int pos
,
1009 enum isl_ast_loop_type type
)
1011 tree
= isl_schedule_tree_cow(tree
);
1015 if (tree
->type
!= isl_schedule_node_band
)
1016 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1017 "not a band node", return isl_schedule_tree_free(tree
));
1019 tree
->band
= isl_schedule_band_member_set_isolate_ast_loop_type(
1020 tree
->band
, pos
, type
);
1022 return isl_schedule_tree_free(tree
);
1027 /* Return the AST build options associated to the band tree root.
1029 __isl_give isl_union_set
*isl_schedule_tree_band_get_ast_build_options(
1030 __isl_keep isl_schedule_tree
*tree
)
1035 if (tree
->type
!= isl_schedule_node_band
)
1036 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1037 "not a band node", return NULL
);
1039 return isl_schedule_band_get_ast_build_options(tree
->band
);
1042 /* Replace the AST build options associated to band tree root by "options".
1043 * Updated the anchored field if the anchoredness of the root node itself
1046 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_ast_build_options(
1047 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*options
)
1051 tree
= isl_schedule_tree_cow(tree
);
1052 if (!tree
|| !options
)
1055 if (tree
->type
!= isl_schedule_node_band
)
1056 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1057 "not a band node", goto error
);
1059 was_anchored
= isl_schedule_tree_is_anchored(tree
);
1060 tree
->band
= isl_schedule_band_set_ast_build_options(tree
->band
,
1063 return isl_schedule_tree_free(tree
);
1064 if (isl_schedule_tree_is_anchored(tree
) != was_anchored
)
1065 tree
= isl_schedule_tree_update_anchored(tree
);
1069 isl_schedule_tree_free(tree
);
1070 isl_union_set_free(options
);
1074 /* Return the context of the context tree root.
1076 __isl_give isl_set
*isl_schedule_tree_context_get_context(
1077 __isl_keep isl_schedule_tree
*tree
)
1082 if (tree
->type
!= isl_schedule_node_context
)
1083 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1084 "not a context node", return NULL
);
1086 return isl_set_copy(tree
->context
);
1089 /* Return the domain of the domain tree root.
1091 __isl_give isl_union_set
*isl_schedule_tree_domain_get_domain(
1092 __isl_keep isl_schedule_tree
*tree
)
1097 if (tree
->type
!= isl_schedule_node_domain
)
1098 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1099 "not a domain node", return NULL
);
1101 return isl_union_set_copy(tree
->domain
);
1104 /* Replace the domain of domain tree root "tree" by "domain".
1106 __isl_give isl_schedule_tree
*isl_schedule_tree_domain_set_domain(
1107 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
1109 tree
= isl_schedule_tree_cow(tree
);
1110 if (!tree
|| !domain
)
1113 if (tree
->type
!= isl_schedule_node_domain
)
1114 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1115 "not a domain node", goto error
);
1117 isl_union_set_free(tree
->domain
);
1118 tree
->domain
= domain
;
1122 isl_schedule_tree_free(tree
);
1123 isl_union_set_free(domain
);
1127 /* Return the contraction of the expansion tree root.
1129 __isl_give isl_union_pw_multi_aff
*isl_schedule_tree_expansion_get_contraction(
1130 __isl_keep isl_schedule_tree
*tree
)
1135 if (tree
->type
!= isl_schedule_node_expansion
)
1136 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1137 "not an expansion node", return NULL
);
1139 return isl_union_pw_multi_aff_copy(tree
->contraction
);
1142 /* Return the expansion of the expansion tree root.
1144 __isl_give isl_union_map
*isl_schedule_tree_expansion_get_expansion(
1145 __isl_keep isl_schedule_tree
*tree
)
1150 if (tree
->type
!= isl_schedule_node_expansion
)
1151 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1152 "not an expansion node", return NULL
);
1154 return isl_union_map_copy(tree
->expansion
);
1157 /* Replace the contraction and the expansion of the expansion tree root "tree"
1158 * by "contraction" and "expansion".
1160 __isl_give isl_schedule_tree
*
1161 isl_schedule_tree_expansion_set_contraction_and_expansion(
1162 __isl_take isl_schedule_tree
*tree
,
1163 __isl_take isl_union_pw_multi_aff
*contraction
,
1164 __isl_take isl_union_map
*expansion
)
1166 tree
= isl_schedule_tree_cow(tree
);
1167 if (!tree
|| !contraction
|| !expansion
)
1170 if (tree
->type
!= isl_schedule_node_expansion
)
1171 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1172 "not an expansion node", return NULL
);
1174 isl_union_pw_multi_aff_free(tree
->contraction
);
1175 tree
->contraction
= contraction
;
1176 isl_union_map_free(tree
->expansion
);
1177 tree
->expansion
= expansion
;
1181 isl_schedule_tree_free(tree
);
1182 isl_union_pw_multi_aff_free(contraction
);
1183 isl_union_map_free(expansion
);
1187 /* Return the filter of the filter tree root.
1189 __isl_give isl_union_set
*isl_schedule_tree_filter_get_filter(
1190 __isl_keep isl_schedule_tree
*tree
)
1195 if (tree
->type
!= isl_schedule_node_filter
)
1196 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1197 "not a filter node", return NULL
);
1199 return isl_union_set_copy(tree
->filter
);
1202 /* Replace the filter of the filter tree root by "filter".
1204 __isl_give isl_schedule_tree
*isl_schedule_tree_filter_set_filter(
1205 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
1207 tree
= isl_schedule_tree_cow(tree
);
1208 if (!tree
|| !filter
)
1211 if (tree
->type
!= isl_schedule_node_filter
)
1212 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1213 "not a filter node", return NULL
);
1215 isl_union_set_free(tree
->filter
);
1216 tree
->filter
= filter
;
1220 isl_schedule_tree_free(tree
);
1221 isl_union_set_free(filter
);
1225 /* Set dim to the range dimension of "map" and abort the search.
1227 static int set_range_dim(__isl_take isl_map
*map
, void *user
)
1231 *dim
= isl_map_dim(map
, isl_dim_out
);
1237 /* Return the dimension of the range of "umap".
1238 * "umap" is assumed not to be empty and
1239 * all maps inside "umap" are assumed to have the same range.
1241 * We extract the range dimension from the first map in "umap".
1243 static int range_dim(__isl_keep isl_union_map
*umap
)
1249 if (isl_union_map_n_map(umap
) == 0)
1250 isl_die(isl_union_map_get_ctx(umap
), isl_error_internal
,
1251 "unexpected empty input", return -1);
1253 isl_union_map_foreach_map(umap
, &set_range_dim
, &dim
);
1258 /* Append an "extra" number of zeros to the range of "umap" and
1259 * return the result.
1261 static __isl_give isl_union_map
*append_range(__isl_take isl_union_map
*umap
,
1267 isl_union_pw_multi_aff
*suffix
;
1268 isl_union_map
*universe
;
1269 isl_union_map
*suffix_umap
;
1271 universe
= isl_union_map_universe(isl_union_map_copy(umap
));
1272 dom
= isl_union_map_domain(universe
);
1273 space
= isl_union_set_get_space(dom
);
1274 space
= isl_space_set_from_params(space
);
1275 space
= isl_space_add_dims(space
, isl_dim_set
, extra
);
1276 mv
= isl_multi_val_zero(space
);
1278 suffix
= isl_union_pw_multi_aff_multi_val_on_domain(dom
, mv
);
1279 suffix_umap
= isl_union_map_from_union_pw_multi_aff(suffix
);
1280 umap
= isl_union_map_flat_range_product(umap
, suffix_umap
);
1285 /* Should we skip the root of "tree" while looking for the first
1286 * descendant with schedule information?
1287 * That is, is it impossible to derive any information about
1288 * the iteration domain from this node?
1290 * We do not want to skip leaf or error nodes because there is
1291 * no point in looking any deeper from these nodes.
1293 static int domain_less(__isl_keep isl_schedule_tree
*tree
)
1295 enum isl_schedule_node_type type
;
1297 type
= isl_schedule_tree_get_type(tree
);
1299 case isl_schedule_node_band
:
1300 return isl_schedule_tree_band_n_member(tree
) == 0;
1301 case isl_schedule_node_context
:
1303 case isl_schedule_node_leaf
:
1304 case isl_schedule_node_error
:
1305 case isl_schedule_node_domain
:
1306 case isl_schedule_node_expansion
:
1307 case isl_schedule_node_filter
:
1308 case isl_schedule_node_set
:
1309 case isl_schedule_node_sequence
:
1314 /* Move down to the first descendant of "tree" that contains any schedule
1315 * information or return "leaf" if there is no such descendant.
1317 __isl_give isl_schedule_tree
*isl_schedule_tree_first_schedule_descendant(
1318 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_tree
*leaf
)
1320 while (domain_less(tree
)) {
1321 if (!isl_schedule_tree_has_children(tree
)) {
1322 isl_schedule_tree_free(tree
);
1323 return isl_schedule_tree_copy(leaf
);
1325 tree
= isl_schedule_tree_child(tree
, 0);
1331 static __isl_give isl_union_map
*subtree_schedule_extend(
1332 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
);
1334 /* Extend the schedule map "outer" with the subtree schedule
1335 * of the (single) child of "tree", if any.
1337 * If "tree" does not have any descendants (apart from those that
1338 * do not carry any schedule information), then we simply return "outer".
1339 * Otherwise, we extend the schedule map "outer" with the subtree schedule
1340 * of the single child.
1342 static __isl_give isl_union_map
*subtree_schedule_extend_child(
1343 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1345 isl_schedule_tree
*child
;
1349 return isl_union_map_free(outer
);
1350 if (!isl_schedule_tree_has_children(tree
))
1352 child
= isl_schedule_tree_get_child(tree
, 0);
1354 return isl_union_map_free(outer
);
1355 res
= subtree_schedule_extend(child
, outer
);
1356 isl_schedule_tree_free(child
);
1360 /* Extract the parameter space from one of the children of "tree",
1361 * which are assumed to be filters.
1363 static __isl_give isl_space
*extract_space_from_filter_child(
1364 __isl_keep isl_schedule_tree
*tree
)
1368 isl_schedule_tree
*child
;
1370 child
= isl_schedule_tree_list_get_schedule_tree(tree
->children
, 0);
1371 dom
= isl_schedule_tree_filter_get_filter(child
);
1372 space
= isl_union_set_get_space(dom
);
1373 isl_union_set_free(dom
);
1374 isl_schedule_tree_free(child
);
1379 /* Extend the schedule map "outer" with the subtree schedule
1380 * of a set or sequence node.
1382 * The schedule for the set or sequence node itself is composed of
1383 * pieces of the form
1391 * The first form is used if there is only a single child or
1392 * if the current node is a set node and the schedule_separate_components
1393 * option is not set.
1395 * Each of the pieces above is extended with the subtree schedule of
1396 * the child of the corresponding filter, if any, padded with zeros
1397 * to ensure that all pieces have the same range dimension.
1399 static __isl_give isl_union_map
*subtree_schedule_extend_from_children(
1400 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1409 isl_union_map
*umap
;
1414 ctx
= isl_schedule_tree_get_ctx(tree
);
1415 if (!tree
->children
)
1416 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1417 "missing children", return NULL
);
1418 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1420 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1421 "missing children", return NULL
);
1423 separate
= n
> 1 && (tree
->type
== isl_schedule_node_sequence
||
1424 isl_options_get_schedule_separate_components(ctx
));
1426 space
= extract_space_from_filter_child(tree
);
1428 umap
= isl_union_map_empty(isl_space_copy(space
));
1429 space
= isl_space_set_from_params(space
);
1431 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1432 v
= isl_val_zero(ctx
);
1434 mv
= isl_multi_val_zero(space
);
1436 dim
= isl_multi_val_dim(mv
, isl_dim_set
);
1437 for (i
= 0; i
< n
; ++i
) {
1438 isl_union_pw_multi_aff
*upma
;
1439 isl_union_map
*umap_i
;
1441 isl_schedule_tree
*child
;
1445 child
= isl_schedule_tree_list_get_schedule_tree(
1447 dom
= isl_schedule_tree_filter_get_filter(child
);
1450 mv
= isl_multi_val_set_val(mv
, 0, isl_val_copy(v
));
1451 v
= isl_val_add_ui(v
, 1);
1453 upma
= isl_union_pw_multi_aff_multi_val_on_domain(dom
,
1454 isl_multi_val_copy(mv
));
1455 umap_i
= isl_union_map_from_union_pw_multi_aff(upma
);
1456 umap_i
= isl_union_map_flat_range_product(
1457 isl_union_map_copy(outer
), umap_i
);
1458 umap_i
= subtree_schedule_extend_child(child
, umap_i
);
1459 isl_schedule_tree_free(child
);
1461 empty
= isl_union_map_is_empty(umap_i
);
1463 umap_i
= isl_union_map_free(umap_i
);
1465 isl_union_map_free(umap_i
);
1469 dim_i
= range_dim(umap_i
);
1471 umap
= isl_union_map_free(umap
);
1472 } else if (dim
< dim_i
) {
1473 umap
= append_range(umap
, dim_i
- dim
);
1475 } else if (dim_i
< dim
) {
1476 umap_i
= append_range(umap_i
, dim
- dim_i
);
1478 umap
= isl_union_map_union(umap
, umap_i
);
1482 isl_multi_val_free(mv
);
1483 isl_union_map_free(outer
);
1488 /* Extend the schedule map "outer" with the subtree schedule of "tree".
1490 * If the root of the tree is a set or a sequence, then we extend
1491 * the schedule map in subtree_schedule_extend_from_children.
1492 * Otherwise, we extend the schedule map with the partial schedule
1493 * corresponding to the root of the tree and then continue with
1494 * the single child of this root.
1495 * In the special case of an expansion, the schedule map is "extended"
1496 * by applying the expansion to the domain of the schedule map.
1498 static __isl_give isl_union_map
*subtree_schedule_extend(
1499 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1501 isl_multi_union_pw_aff
*mupa
;
1502 isl_union_map
*umap
;
1503 isl_union_set
*domain
;
1508 switch (tree
->type
) {
1509 case isl_schedule_node_error
:
1510 return isl_union_map_free(outer
);
1511 case isl_schedule_node_context
:
1512 return subtree_schedule_extend_child(tree
, outer
);
1513 case isl_schedule_node_band
:
1514 if (isl_schedule_tree_band_n_member(tree
) == 0)
1515 return subtree_schedule_extend_child(tree
, outer
);
1516 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1517 umap
= isl_union_map_from_multi_union_pw_aff(mupa
);
1518 outer
= isl_union_map_flat_range_product(outer
, umap
);
1519 umap
= subtree_schedule_extend_child(tree
, outer
);
1521 case isl_schedule_node_domain
:
1522 domain
= isl_schedule_tree_domain_get_domain(tree
);
1523 umap
= isl_union_map_from_domain(domain
);
1524 outer
= isl_union_map_flat_range_product(outer
, umap
);
1525 umap
= subtree_schedule_extend_child(tree
, outer
);
1527 case isl_schedule_node_expansion
:
1528 umap
= isl_schedule_tree_expansion_get_expansion(tree
);
1529 outer
= isl_union_map_apply_domain(outer
, umap
);
1530 umap
= subtree_schedule_extend_child(tree
, outer
);
1532 case isl_schedule_node_filter
:
1533 domain
= isl_schedule_tree_filter_get_filter(tree
);
1534 umap
= isl_union_map_from_domain(domain
);
1535 outer
= isl_union_map_flat_range_product(outer
, umap
);
1536 umap
= subtree_schedule_extend_child(tree
, outer
);
1538 case isl_schedule_node_leaf
:
1539 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1540 "leaf node should be handled by caller", return NULL
);
1541 case isl_schedule_node_set
:
1542 case isl_schedule_node_sequence
:
1543 umap
= subtree_schedule_extend_from_children(tree
, outer
);
1550 static __isl_give isl_union_set
*initial_domain(
1551 __isl_keep isl_schedule_tree
*tree
);
1553 /* Extract a universe domain from the children of the tree root "tree",
1554 * which is a set or sequence, meaning that its children are filters.
1555 * In particular, return the union of the universes of the filters.
1557 static __isl_give isl_union_set
*initial_domain_from_children(
1558 __isl_keep isl_schedule_tree
*tree
)
1562 isl_union_set
*domain
;
1564 if (!tree
->children
)
1565 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1566 "missing children", return NULL
);
1567 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1569 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1570 "missing children", return NULL
);
1572 space
= extract_space_from_filter_child(tree
);
1573 domain
= isl_union_set_empty(space
);
1575 for (i
= 0; i
< n
; ++i
) {
1576 isl_schedule_tree
*child
;
1577 isl_union_set
*domain_i
;
1579 child
= isl_schedule_tree_get_child(tree
, i
);
1580 domain_i
= initial_domain(child
);
1581 domain
= isl_union_set_union(domain
, domain_i
);
1582 isl_schedule_tree_free(child
);
1588 /* Extract a universe domain from the tree root "tree".
1589 * The caller is responsible for making sure that this node
1590 * would not be skipped by isl_schedule_tree_first_schedule_descendant
1591 * and that it is not a leaf node.
1593 static __isl_give isl_union_set
*initial_domain(
1594 __isl_keep isl_schedule_tree
*tree
)
1596 isl_multi_union_pw_aff
*mupa
;
1597 isl_union_set
*domain
;
1603 switch (tree
->type
) {
1604 case isl_schedule_node_error
:
1606 case isl_schedule_node_context
:
1607 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1608 "context node should be handled by caller",
1610 case isl_schedule_node_band
:
1611 if (isl_schedule_tree_band_n_member(tree
) == 0)
1612 isl_die(isl_schedule_tree_get_ctx(tree
),
1614 "0D band should be handled by caller",
1616 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1617 domain
= isl_multi_union_pw_aff_domain(mupa
);
1618 domain
= isl_union_set_universe(domain
);
1620 case isl_schedule_node_domain
:
1621 domain
= isl_schedule_tree_domain_get_domain(tree
);
1622 domain
= isl_union_set_universe(domain
);
1624 case isl_schedule_node_expansion
:
1625 exp
= isl_schedule_tree_expansion_get_expansion(tree
);
1626 exp
= isl_union_map_universe(exp
);
1627 domain
= isl_union_map_domain(exp
);
1629 case isl_schedule_node_filter
:
1630 domain
= isl_schedule_tree_filter_get_filter(tree
);
1631 domain
= isl_union_set_universe(domain
);
1633 case isl_schedule_node_leaf
:
1634 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1635 "leaf node should be handled by caller", return NULL
);
1636 case isl_schedule_node_set
:
1637 case isl_schedule_node_sequence
:
1638 domain
= initial_domain_from_children(tree
);
1645 /* Return the subtree schedule of a node that contains some schedule
1646 * information, i.e., a node that would not be skipped by
1647 * isl_schedule_tree_first_schedule_descendant and that is not a leaf.
1649 * If the tree contains any expansions, then the returned subtree
1650 * schedule is formulated in terms of the expanded domains.
1652 * We start with an initial zero-dimensional subtree schedule based
1653 * on the domain information in the root node and then extend it
1654 * based on the schedule information in the root node and its descendants.
1656 __isl_give isl_union_map
*isl_schedule_tree_get_subtree_schedule_union_map(
1657 __isl_keep isl_schedule_tree
*tree
)
1659 isl_union_set
*domain
;
1660 isl_union_map
*umap
;
1662 domain
= initial_domain(tree
);
1663 umap
= isl_union_map_from_domain(domain
);
1664 return subtree_schedule_extend(tree
, umap
);
1667 /* Multiply the partial schedule of the band root node of "tree"
1668 * with the factors in "mv".
1670 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale(
1671 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
1675 if (tree
->type
!= isl_schedule_node_band
)
1676 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1677 "not a band node", goto error
);
1679 tree
= isl_schedule_tree_cow(tree
);
1683 tree
->band
= isl_schedule_band_scale(tree
->band
, mv
);
1685 return isl_schedule_tree_free(tree
);
1689 isl_schedule_tree_free(tree
);
1690 isl_multi_val_free(mv
);
1694 /* Divide the partial schedule of the band root node of "tree"
1695 * by the factors in "mv".
1697 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale_down(
1698 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
1702 if (tree
->type
!= isl_schedule_node_band
)
1703 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1704 "not a band node", goto error
);
1706 tree
= isl_schedule_tree_cow(tree
);
1710 tree
->band
= isl_schedule_band_scale_down(tree
->band
, mv
);
1712 return isl_schedule_tree_free(tree
);
1716 isl_schedule_tree_free(tree
);
1717 isl_multi_val_free(mv
);
1721 /* Tile the band root node of "tree" with tile sizes "sizes".
1723 * We duplicate the band node, change the schedule of one of them
1724 * to the tile schedule and the other to the point schedule and then
1725 * attach the point band as a child to the tile band.
1727 __isl_give isl_schedule_tree
*isl_schedule_tree_band_tile(
1728 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*sizes
)
1730 isl_schedule_tree
*child
= NULL
;
1732 if (!tree
|| !sizes
)
1734 if (tree
->type
!= isl_schedule_node_band
)
1735 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1736 "not a band node", goto error
);
1738 child
= isl_schedule_tree_copy(tree
);
1739 tree
= isl_schedule_tree_cow(tree
);
1740 child
= isl_schedule_tree_cow(child
);
1741 if (!tree
|| !child
)
1744 tree
->band
= isl_schedule_band_tile(tree
->band
,
1745 isl_multi_val_copy(sizes
));
1748 child
->band
= isl_schedule_band_point(child
->band
, tree
->band
, sizes
);
1750 child
= isl_schedule_tree_free(child
);
1752 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
1756 isl_schedule_tree_free(child
);
1757 isl_schedule_tree_free(tree
);
1758 isl_multi_val_free(sizes
);
1762 /* Split the band root node of "tree" into two nested band nodes,
1763 * one with the first "pos" dimensions and
1764 * one with the remaining dimensions.
1766 __isl_give isl_schedule_tree
*isl_schedule_tree_band_split(
1767 __isl_take isl_schedule_tree
*tree
, int pos
)
1770 isl_schedule_tree
*child
;
1774 if (tree
->type
!= isl_schedule_node_band
)
1775 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1776 "not a band node", return isl_schedule_tree_free(tree
));
1778 n
= isl_schedule_tree_band_n_member(tree
);
1779 if (pos
< 0 || pos
> n
)
1780 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1781 "position out of bounds",
1782 return isl_schedule_tree_free(tree
));
1784 child
= isl_schedule_tree_copy(tree
);
1785 tree
= isl_schedule_tree_cow(tree
);
1786 child
= isl_schedule_tree_cow(child
);
1787 if (!tree
|| !child
)
1790 child
->band
= isl_schedule_band_drop(child
->band
, 0, pos
);
1791 tree
->band
= isl_schedule_band_drop(tree
->band
, pos
, n
- pos
);
1792 if (!child
->band
|| !tree
->band
)
1795 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
1799 isl_schedule_tree_free(child
);
1800 isl_schedule_tree_free(tree
);
1804 /* Attach "tree2" at each of the leaves of "tree1".
1806 * If "tree1" does not have any explicit children, then make "tree2"
1807 * its single child. Otherwise, attach "tree2" to the leaves of
1808 * each of the children of "tree1".
1810 __isl_give isl_schedule_tree
*isl_schedule_tree_append_to_leaves(
1811 __isl_take isl_schedule_tree
*tree1
,
1812 __isl_take isl_schedule_tree
*tree2
)
1816 if (!tree1
|| !tree2
)
1818 n
= isl_schedule_tree_n_children(tree1
);
1820 isl_schedule_tree_list
*list
;
1821 list
= isl_schedule_tree_list_from_schedule_tree(tree2
);
1822 tree1
= isl_schedule_tree_set_children(tree1
, list
);
1825 for (i
= 0; i
< n
; ++i
) {
1826 isl_schedule_tree
*child
;
1828 child
= isl_schedule_tree_get_child(tree1
, i
);
1829 child
= isl_schedule_tree_append_to_leaves(child
,
1830 isl_schedule_tree_copy(tree2
));
1831 tree1
= isl_schedule_tree_replace_child(tree1
, i
, child
);
1834 isl_schedule_tree_free(tree2
);
1837 isl_schedule_tree_free(tree1
);
1838 isl_schedule_tree_free(tree2
);
1842 /* Reset the user pointer on all identifiers of parameters and tuples
1843 * in the root of "tree".
1845 __isl_give isl_schedule_tree
*isl_schedule_tree_reset_user(
1846 __isl_take isl_schedule_tree
*tree
)
1848 if (isl_schedule_tree_is_leaf(tree
))
1851 tree
= isl_schedule_tree_cow(tree
);
1855 switch (tree
->type
) {
1856 case isl_schedule_node_error
:
1857 return isl_schedule_tree_free(tree
);
1858 case isl_schedule_node_band
:
1859 tree
->band
= isl_schedule_band_reset_user(tree
->band
);
1861 return isl_schedule_tree_free(tree
);
1863 case isl_schedule_node_context
:
1864 tree
->context
= isl_set_reset_user(tree
->context
);
1866 return isl_schedule_tree_free(tree
);
1868 case isl_schedule_node_domain
:
1869 tree
->domain
= isl_union_set_reset_user(tree
->domain
);
1871 return isl_schedule_tree_free(tree
);
1873 case isl_schedule_node_expansion
:
1875 isl_union_pw_multi_aff_reset_user(tree
->contraction
);
1876 tree
->expansion
= isl_union_map_reset_user(tree
->expansion
);
1877 if (!tree
->contraction
|| !tree
->expansion
)
1878 return isl_schedule_tree_free(tree
);
1880 case isl_schedule_node_filter
:
1881 tree
->filter
= isl_union_set_reset_user(tree
->filter
);
1883 return isl_schedule_tree_free(tree
);
1885 case isl_schedule_node_leaf
:
1886 case isl_schedule_node_sequence
:
1887 case isl_schedule_node_set
:
1894 /* Align the parameters of the root of "tree" to those of "space".
1896 __isl_give isl_schedule_tree
*isl_schedule_tree_align_params(
1897 __isl_take isl_schedule_tree
*tree
, __isl_take isl_space
*space
)
1902 if (isl_schedule_tree_is_leaf(tree
)) {
1903 isl_space_free(space
);
1907 tree
= isl_schedule_tree_cow(tree
);
1911 switch (tree
->type
) {
1912 case isl_schedule_node_error
:
1914 case isl_schedule_node_band
:
1915 tree
->band
= isl_schedule_band_align_params(tree
->band
, space
);
1917 return isl_schedule_tree_free(tree
);
1919 case isl_schedule_node_context
:
1920 tree
->context
= isl_set_align_params(tree
->context
, space
);
1922 return isl_schedule_tree_free(tree
);
1924 case isl_schedule_node_domain
:
1925 tree
->domain
= isl_union_set_align_params(tree
->domain
, space
);
1927 return isl_schedule_tree_free(tree
);
1929 case isl_schedule_node_expansion
:
1931 isl_union_pw_multi_aff_align_params(tree
->contraction
,
1932 isl_space_copy(space
));
1933 tree
->expansion
= isl_union_map_align_params(tree
->expansion
,
1935 if (!tree
->contraction
|| !tree
->expansion
)
1936 return isl_schedule_tree_free(tree
);
1938 case isl_schedule_node_filter
:
1939 tree
->filter
= isl_union_set_align_params(tree
->filter
, space
);
1941 return isl_schedule_tree_free(tree
);
1943 case isl_schedule_node_leaf
:
1944 case isl_schedule_node_sequence
:
1945 case isl_schedule_node_set
:
1946 isl_space_free(space
);
1952 isl_space_free(space
);
1953 isl_schedule_tree_free(tree
);
1957 /* Does "tree" involve the iteration domain?
1958 * That is, does it need to be modified
1959 * by isl_schedule_tree_pullback_union_pw_multi_aff?
1961 static int involves_iteration_domain(__isl_keep isl_schedule_tree
*tree
)
1966 switch (tree
->type
) {
1967 case isl_schedule_node_error
:
1969 case isl_schedule_node_band
:
1970 case isl_schedule_node_domain
:
1971 case isl_schedule_node_expansion
:
1972 case isl_schedule_node_filter
:
1974 case isl_schedule_node_context
:
1975 case isl_schedule_node_leaf
:
1976 case isl_schedule_node_sequence
:
1977 case isl_schedule_node_set
:
1982 /* Compute the pullback of the root node of "tree" by the function
1983 * represented by "upma".
1984 * In other words, plug in "upma" in the iteration domains of
1985 * the root node of "tree".
1986 * We currently do not handle expansion nodes.
1988 * We first check if the root node involves any iteration domains.
1989 * If so, we handle the specific cases.
1991 __isl_give isl_schedule_tree
*isl_schedule_tree_pullback_union_pw_multi_aff(
1992 __isl_take isl_schedule_tree
*tree
,
1993 __isl_take isl_union_pw_multi_aff
*upma
)
2000 involves
= involves_iteration_domain(tree
);
2004 isl_union_pw_multi_aff_free(upma
);
2008 tree
= isl_schedule_tree_cow(tree
);
2012 if (tree
->type
== isl_schedule_node_band
) {
2013 tree
->band
= isl_schedule_band_pullback_union_pw_multi_aff(
2016 return isl_schedule_tree_free(tree
);
2017 } else if (tree
->type
== isl_schedule_node_domain
) {
2019 isl_union_set_preimage_union_pw_multi_aff(tree
->domain
,
2022 return isl_schedule_tree_free(tree
);
2023 } else if (tree
->type
== isl_schedule_node_expansion
) {
2024 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_unsupported
,
2025 "cannot pullback expansion node", goto error
);
2026 } else if (tree
->type
== isl_schedule_node_filter
) {
2028 isl_union_set_preimage_union_pw_multi_aff(tree
->filter
,
2031 return isl_schedule_tree_free(tree
);
2036 isl_union_pw_multi_aff_free(upma
);
2037 isl_schedule_tree_free(tree
);
2041 /* Compute the gist of the band tree root with respect to "context".
2043 __isl_give isl_schedule_tree
*isl_schedule_tree_band_gist(
2044 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*context
)
2048 if (tree
->type
!= isl_schedule_node_band
)
2049 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2050 "not a band node", goto error
);
2051 tree
= isl_schedule_tree_cow(tree
);
2055 tree
->band
= isl_schedule_band_gist(tree
->band
, context
);
2057 return isl_schedule_tree_free(tree
);
2060 isl_union_set_free(context
);
2061 isl_schedule_tree_free(tree
);
2065 /* Are any members in "band" marked coincident?
2067 static int any_coincident(__isl_keep isl_schedule_band
*band
)
2071 n
= isl_schedule_band_n_member(band
);
2072 for (i
= 0; i
< n
; ++i
)
2073 if (isl_schedule_band_member_get_coincident(band
, i
))
2079 /* Print the band node "band" to "p".
2081 * The permutable and coincident properties are only printed if they
2082 * are different from the defaults.
2083 * The coincident property is always printed in YAML flow style.
2085 static __isl_give isl_printer
*print_tree_band(__isl_take isl_printer
*p
,
2086 __isl_keep isl_schedule_band
*band
)
2088 isl_union_set
*options
;
2091 p
= isl_printer_print_str(p
, "schedule");
2092 p
= isl_printer_yaml_next(p
);
2093 p
= isl_printer_print_str(p
, "\"");
2094 p
= isl_printer_print_multi_union_pw_aff(p
, band
->mupa
);
2095 p
= isl_printer_print_str(p
, "\"");
2096 if (isl_schedule_band_get_permutable(band
)) {
2097 p
= isl_printer_yaml_next(p
);
2098 p
= isl_printer_print_str(p
, "permutable");
2099 p
= isl_printer_yaml_next(p
);
2100 p
= isl_printer_print_int(p
, 1);
2102 if (any_coincident(band
)) {
2106 p
= isl_printer_yaml_next(p
);
2107 p
= isl_printer_print_str(p
, "coincident");
2108 p
= isl_printer_yaml_next(p
);
2109 style
= isl_printer_get_yaml_style(p
);
2110 p
= isl_printer_set_yaml_style(p
, ISL_YAML_STYLE_FLOW
);
2111 p
= isl_printer_yaml_start_sequence(p
);
2112 n
= isl_schedule_band_n_member(band
);
2113 for (i
= 0; i
< n
; ++i
) {
2114 p
= isl_printer_print_int(p
,
2115 isl_schedule_band_member_get_coincident(band
, i
));
2116 p
= isl_printer_yaml_next(p
);
2118 p
= isl_printer_yaml_end_sequence(p
);
2119 p
= isl_printer_set_yaml_style(p
, style
);
2121 options
= isl_schedule_band_get_ast_build_options(band
);
2122 empty
= isl_union_set_is_empty(options
);
2124 p
= isl_printer_free(p
);
2126 p
= isl_printer_yaml_next(p
);
2127 p
= isl_printer_print_str(p
, "options");
2128 p
= isl_printer_yaml_next(p
);
2129 p
= isl_printer_print_str(p
, "\"");
2130 p
= isl_printer_print_union_set(p
, options
);
2131 p
= isl_printer_print_str(p
, "\"");
2133 isl_union_set_free(options
);
2138 /* Print "tree" to "p".
2140 * If "n_ancestor" is non-negative, then "child_pos" contains the child
2141 * positions of a descendant of the current node that should be marked
2142 * (by the comment "YOU ARE HERE"). In particular, if "n_ancestor"
2143 * is zero, then the current node should be marked.
2144 * The marking is only printed in YAML block format.
2146 * Implicit leaf nodes are not printed, except if they correspond
2147 * to the node that should be marked.
2149 __isl_give isl_printer
*isl_printer_print_schedule_tree_mark(
2150 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
,
2151 int n_ancestor
, int *child_pos
)
2157 block
= isl_printer_get_yaml_style(p
) == ISL_YAML_STYLE_BLOCK
;
2159 p
= isl_printer_yaml_start_mapping(p
);
2160 if (n_ancestor
== 0 && block
) {
2161 p
= isl_printer_print_str(p
, "# YOU ARE HERE");
2162 p
= isl_printer_end_line(p
);
2163 p
= isl_printer_start_line(p
);
2165 switch (tree
->type
) {
2166 case isl_schedule_node_error
:
2167 p
= isl_printer_print_str(p
, "ERROR");
2169 case isl_schedule_node_leaf
:
2170 p
= isl_printer_print_str(p
, "leaf");
2172 case isl_schedule_node_sequence
:
2173 p
= isl_printer_print_str(p
, "sequence");
2176 case isl_schedule_node_set
:
2177 p
= isl_printer_print_str(p
, "set");
2180 case isl_schedule_node_context
:
2181 p
= isl_printer_print_str(p
, "context");
2182 p
= isl_printer_yaml_next(p
);
2183 p
= isl_printer_print_str(p
, "\"");
2184 p
= isl_printer_print_set(p
, tree
->context
);
2185 p
= isl_printer_print_str(p
, "\"");
2187 case isl_schedule_node_domain
:
2188 p
= isl_printer_print_str(p
, "domain");
2189 p
= isl_printer_yaml_next(p
);
2190 p
= isl_printer_print_str(p
, "\"");
2191 p
= isl_printer_print_union_set(p
, tree
->domain
);
2192 p
= isl_printer_print_str(p
, "\"");
2194 case isl_schedule_node_expansion
:
2195 p
= isl_printer_print_str(p
, "contraction");
2196 p
= isl_printer_yaml_next(p
);
2197 p
= isl_printer_print_str(p
, "\"");
2198 p
= isl_printer_print_union_pw_multi_aff(p
, tree
->contraction
);
2199 p
= isl_printer_print_str(p
, "\"");
2200 p
= isl_printer_yaml_next(p
);
2201 p
= isl_printer_print_str(p
, "expansion");
2202 p
= isl_printer_yaml_next(p
);
2203 p
= isl_printer_print_str(p
, "\"");
2204 p
= isl_printer_print_union_map(p
, tree
->expansion
);
2205 p
= isl_printer_print_str(p
, "\"");
2207 case isl_schedule_node_filter
:
2208 p
= isl_printer_print_str(p
, "filter");
2209 p
= isl_printer_yaml_next(p
);
2210 p
= isl_printer_print_str(p
, "\"");
2211 p
= isl_printer_print_union_set(p
, tree
->filter
);
2212 p
= isl_printer_print_str(p
, "\"");
2214 case isl_schedule_node_band
:
2215 p
= print_tree_band(p
, tree
->band
);
2218 p
= isl_printer_yaml_next(p
);
2220 if (!tree
->children
) {
2221 if (n_ancestor
> 0 && block
) {
2222 isl_schedule_tree
*leaf
;
2224 p
= isl_printer_print_str(p
, "child");
2225 p
= isl_printer_yaml_next(p
);
2226 leaf
= isl_schedule_tree_leaf(isl_printer_get_ctx(p
));
2227 p
= isl_printer_print_schedule_tree_mark(p
,
2229 isl_schedule_tree_free(leaf
);
2230 p
= isl_printer_yaml_next(p
);
2232 return isl_printer_yaml_end_mapping(p
);
2236 p
= isl_printer_yaml_start_sequence(p
);
2238 p
= isl_printer_print_str(p
, "child");
2239 p
= isl_printer_yaml_next(p
);
2242 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
2243 for (i
= 0; i
< n
; ++i
) {
2244 isl_schedule_tree
*t
;
2246 t
= isl_schedule_tree_get_child(tree
, i
);
2247 if (n_ancestor
> 0 && child_pos
[0] == i
)
2248 p
= isl_printer_print_schedule_tree_mark(p
, t
,
2249 n_ancestor
- 1, child_pos
+ 1);
2251 p
= isl_printer_print_schedule_tree_mark(p
, t
,
2253 isl_schedule_tree_free(t
);
2255 p
= isl_printer_yaml_next(p
);
2259 p
= isl_printer_yaml_end_sequence(p
);
2260 p
= isl_printer_yaml_end_mapping(p
);
2265 /* Print "tree" to "p".
2267 __isl_give isl_printer
*isl_printer_print_schedule_tree(
2268 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
)
2270 return isl_printer_print_schedule_tree_mark(p
, tree
, -1, NULL
);
2273 void isl_schedule_tree_dump(__isl_keep isl_schedule_tree
*tree
)
2276 isl_printer
*printer
;
2281 ctx
= isl_schedule_tree_get_ctx(tree
);
2282 printer
= isl_printer_to_file(ctx
, stderr
);
2283 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
2284 printer
= isl_printer_print_schedule_tree(printer
, tree
);
2286 isl_printer_free(printer
);