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 /* Intersect the domain of the band schedule of the band tree root
935 __isl_give isl_schedule_tree
*isl_schedule_tree_band_intersect_domain(
936 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
938 if (!tree
|| !domain
)
941 if (tree
->type
!= isl_schedule_node_band
)
942 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
943 "not a band node", goto error
);
945 tree
->band
= isl_schedule_band_intersect_domain(tree
->band
, domain
);
947 return isl_schedule_tree_free(tree
);
951 isl_schedule_tree_free(tree
);
952 isl_union_set_free(domain
);
956 /* Return the schedule of the band tree root in isolation.
958 __isl_give isl_multi_union_pw_aff
*isl_schedule_tree_band_get_partial_schedule(
959 __isl_keep isl_schedule_tree
*tree
)
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 NULL
);
968 return isl_schedule_band_get_partial_schedule(tree
->band
);
971 /* Replace the schedule of the band tree root by "schedule".
973 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_partial_schedule(
974 __isl_take isl_schedule_tree
*tree
,
975 __isl_take isl_multi_union_pw_aff
*schedule
)
977 tree
= isl_schedule_tree_cow(tree
);
978 if (!tree
|| !schedule
)
981 if (tree
->type
!= isl_schedule_node_band
)
982 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
983 "not a band node", return NULL
);
984 tree
->band
= isl_schedule_band_set_partial_schedule(tree
->band
,
989 isl_schedule_tree_free(tree
);
990 isl_multi_union_pw_aff_free(schedule
);
994 /* Return the loop AST generation type for the band member
995 * of the band tree root at position "pos".
997 enum isl_ast_loop_type
isl_schedule_tree_band_member_get_ast_loop_type(
998 __isl_keep isl_schedule_tree
*tree
, int pos
)
1001 return isl_ast_loop_error
;
1003 if (tree
->type
!= isl_schedule_node_band
)
1004 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1005 "not a band node", return isl_ast_loop_error
);
1007 return isl_schedule_band_member_get_ast_loop_type(tree
->band
, pos
);
1010 /* Set the loop AST generation type for the band member of the band tree root
1011 * at position "pos" to "type".
1013 __isl_give isl_schedule_tree
*isl_schedule_tree_band_member_set_ast_loop_type(
1014 __isl_take isl_schedule_tree
*tree
, int pos
,
1015 enum isl_ast_loop_type type
)
1017 tree
= isl_schedule_tree_cow(tree
);
1021 if (tree
->type
!= isl_schedule_node_band
)
1022 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1023 "not a band node", return isl_schedule_tree_free(tree
));
1025 tree
->band
= isl_schedule_band_member_set_ast_loop_type(tree
->band
,
1028 return isl_schedule_tree_free(tree
);
1033 /* Return the loop AST generation type for the band member
1034 * of the band tree root at position "pos" for the isolated part.
1036 enum isl_ast_loop_type
isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1037 __isl_keep isl_schedule_tree
*tree
, int pos
)
1040 return isl_ast_loop_error
;
1042 if (tree
->type
!= isl_schedule_node_band
)
1043 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1044 "not a band node", return isl_ast_loop_error
);
1046 return isl_schedule_band_member_get_isolate_ast_loop_type(tree
->band
,
1050 /* Set the loop AST generation type for the band member of the band tree root
1051 * at position "pos" for the isolated part to "type".
1053 __isl_give isl_schedule_tree
*
1054 isl_schedule_tree_band_member_set_isolate_ast_loop_type(
1055 __isl_take isl_schedule_tree
*tree
, int pos
,
1056 enum isl_ast_loop_type type
)
1058 tree
= isl_schedule_tree_cow(tree
);
1062 if (tree
->type
!= isl_schedule_node_band
)
1063 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1064 "not a band node", return isl_schedule_tree_free(tree
));
1066 tree
->band
= isl_schedule_band_member_set_isolate_ast_loop_type(
1067 tree
->band
, pos
, type
);
1069 return isl_schedule_tree_free(tree
);
1074 /* Return the AST build options associated to the band tree root.
1076 __isl_give isl_union_set
*isl_schedule_tree_band_get_ast_build_options(
1077 __isl_keep isl_schedule_tree
*tree
)
1082 if (tree
->type
!= isl_schedule_node_band
)
1083 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1084 "not a band node", return NULL
);
1086 return isl_schedule_band_get_ast_build_options(tree
->band
);
1089 /* Replace the AST build options associated to band tree root by "options".
1090 * Updated the anchored field if the anchoredness of the root node itself
1093 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_ast_build_options(
1094 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*options
)
1098 tree
= isl_schedule_tree_cow(tree
);
1099 if (!tree
|| !options
)
1102 if (tree
->type
!= isl_schedule_node_band
)
1103 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1104 "not a band node", goto error
);
1106 was_anchored
= isl_schedule_tree_is_anchored(tree
);
1107 tree
->band
= isl_schedule_band_set_ast_build_options(tree
->band
,
1110 return isl_schedule_tree_free(tree
);
1111 if (isl_schedule_tree_is_anchored(tree
) != was_anchored
)
1112 tree
= isl_schedule_tree_update_anchored(tree
);
1116 isl_schedule_tree_free(tree
);
1117 isl_union_set_free(options
);
1121 /* Return the context of the context tree root.
1123 __isl_give isl_set
*isl_schedule_tree_context_get_context(
1124 __isl_keep isl_schedule_tree
*tree
)
1129 if (tree
->type
!= isl_schedule_node_context
)
1130 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1131 "not a context node", return NULL
);
1133 return isl_set_copy(tree
->context
);
1136 /* Return the domain of the domain tree root.
1138 __isl_give isl_union_set
*isl_schedule_tree_domain_get_domain(
1139 __isl_keep isl_schedule_tree
*tree
)
1144 if (tree
->type
!= isl_schedule_node_domain
)
1145 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1146 "not a domain node", return NULL
);
1148 return isl_union_set_copy(tree
->domain
);
1151 /* Replace the domain of domain tree root "tree" by "domain".
1153 __isl_give isl_schedule_tree
*isl_schedule_tree_domain_set_domain(
1154 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
1156 tree
= isl_schedule_tree_cow(tree
);
1157 if (!tree
|| !domain
)
1160 if (tree
->type
!= isl_schedule_node_domain
)
1161 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1162 "not a domain node", goto error
);
1164 isl_union_set_free(tree
->domain
);
1165 tree
->domain
= domain
;
1169 isl_schedule_tree_free(tree
);
1170 isl_union_set_free(domain
);
1174 /* Return the contraction of the expansion tree root.
1176 __isl_give isl_union_pw_multi_aff
*isl_schedule_tree_expansion_get_contraction(
1177 __isl_keep isl_schedule_tree
*tree
)
1182 if (tree
->type
!= isl_schedule_node_expansion
)
1183 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1184 "not an expansion node", return NULL
);
1186 return isl_union_pw_multi_aff_copy(tree
->contraction
);
1189 /* Return the expansion of the expansion tree root.
1191 __isl_give isl_union_map
*isl_schedule_tree_expansion_get_expansion(
1192 __isl_keep isl_schedule_tree
*tree
)
1197 if (tree
->type
!= isl_schedule_node_expansion
)
1198 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1199 "not an expansion node", return NULL
);
1201 return isl_union_map_copy(tree
->expansion
);
1204 /* Replace the contraction and the expansion of the expansion tree root "tree"
1205 * by "contraction" and "expansion".
1207 __isl_give isl_schedule_tree
*
1208 isl_schedule_tree_expansion_set_contraction_and_expansion(
1209 __isl_take isl_schedule_tree
*tree
,
1210 __isl_take isl_union_pw_multi_aff
*contraction
,
1211 __isl_take isl_union_map
*expansion
)
1213 tree
= isl_schedule_tree_cow(tree
);
1214 if (!tree
|| !contraction
|| !expansion
)
1217 if (tree
->type
!= isl_schedule_node_expansion
)
1218 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1219 "not an expansion node", return NULL
);
1221 isl_union_pw_multi_aff_free(tree
->contraction
);
1222 tree
->contraction
= contraction
;
1223 isl_union_map_free(tree
->expansion
);
1224 tree
->expansion
= expansion
;
1228 isl_schedule_tree_free(tree
);
1229 isl_union_pw_multi_aff_free(contraction
);
1230 isl_union_map_free(expansion
);
1234 /* Return the filter of the filter tree root.
1236 __isl_give isl_union_set
*isl_schedule_tree_filter_get_filter(
1237 __isl_keep isl_schedule_tree
*tree
)
1242 if (tree
->type
!= isl_schedule_node_filter
)
1243 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1244 "not a filter node", return NULL
);
1246 return isl_union_set_copy(tree
->filter
);
1249 /* Replace the filter of the filter tree root by "filter".
1251 __isl_give isl_schedule_tree
*isl_schedule_tree_filter_set_filter(
1252 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
1254 tree
= isl_schedule_tree_cow(tree
);
1255 if (!tree
|| !filter
)
1258 if (tree
->type
!= isl_schedule_node_filter
)
1259 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1260 "not a filter node", return NULL
);
1262 isl_union_set_free(tree
->filter
);
1263 tree
->filter
= filter
;
1267 isl_schedule_tree_free(tree
);
1268 isl_union_set_free(filter
);
1272 /* Set dim to the range dimension of "map" and abort the search.
1274 static int set_range_dim(__isl_take isl_map
*map
, void *user
)
1278 *dim
= isl_map_dim(map
, isl_dim_out
);
1284 /* Return the dimension of the range of "umap".
1285 * "umap" is assumed not to be empty and
1286 * all maps inside "umap" are assumed to have the same range.
1288 * We extract the range dimension from the first map in "umap".
1290 static int range_dim(__isl_keep isl_union_map
*umap
)
1296 if (isl_union_map_n_map(umap
) == 0)
1297 isl_die(isl_union_map_get_ctx(umap
), isl_error_internal
,
1298 "unexpected empty input", return -1);
1300 isl_union_map_foreach_map(umap
, &set_range_dim
, &dim
);
1305 /* Append an "extra" number of zeros to the range of "umap" and
1306 * return the result.
1308 static __isl_give isl_union_map
*append_range(__isl_take isl_union_map
*umap
,
1314 isl_union_pw_multi_aff
*suffix
;
1315 isl_union_map
*universe
;
1316 isl_union_map
*suffix_umap
;
1318 universe
= isl_union_map_universe(isl_union_map_copy(umap
));
1319 dom
= isl_union_map_domain(universe
);
1320 space
= isl_union_set_get_space(dom
);
1321 space
= isl_space_set_from_params(space
);
1322 space
= isl_space_add_dims(space
, isl_dim_set
, extra
);
1323 mv
= isl_multi_val_zero(space
);
1325 suffix
= isl_union_pw_multi_aff_multi_val_on_domain(dom
, mv
);
1326 suffix_umap
= isl_union_map_from_union_pw_multi_aff(suffix
);
1327 umap
= isl_union_map_flat_range_product(umap
, suffix_umap
);
1332 /* Should we skip the root of "tree" while looking for the first
1333 * descendant with schedule information?
1334 * That is, is it impossible to derive any information about
1335 * the iteration domain from this node?
1337 * We do not want to skip leaf or error nodes because there is
1338 * no point in looking any deeper from these nodes.
1340 static int domain_less(__isl_keep isl_schedule_tree
*tree
)
1342 enum isl_schedule_node_type type
;
1344 type
= isl_schedule_tree_get_type(tree
);
1346 case isl_schedule_node_band
:
1347 return isl_schedule_tree_band_n_member(tree
) == 0;
1348 case isl_schedule_node_context
:
1350 case isl_schedule_node_leaf
:
1351 case isl_schedule_node_error
:
1352 case isl_schedule_node_domain
:
1353 case isl_schedule_node_expansion
:
1354 case isl_schedule_node_filter
:
1355 case isl_schedule_node_set
:
1356 case isl_schedule_node_sequence
:
1361 /* Move down to the first descendant of "tree" that contains any schedule
1362 * information or return "leaf" if there is no such descendant.
1364 __isl_give isl_schedule_tree
*isl_schedule_tree_first_schedule_descendant(
1365 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_tree
*leaf
)
1367 while (domain_less(tree
)) {
1368 if (!isl_schedule_tree_has_children(tree
)) {
1369 isl_schedule_tree_free(tree
);
1370 return isl_schedule_tree_copy(leaf
);
1372 tree
= isl_schedule_tree_child(tree
, 0);
1378 static __isl_give isl_union_map
*subtree_schedule_extend(
1379 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
);
1381 /* Extend the schedule map "outer" with the subtree schedule
1382 * of the (single) child of "tree", if any.
1384 * If "tree" does not have any descendants (apart from those that
1385 * do not carry any schedule information), then we simply return "outer".
1386 * Otherwise, we extend the schedule map "outer" with the subtree schedule
1387 * of the single child.
1389 static __isl_give isl_union_map
*subtree_schedule_extend_child(
1390 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1392 isl_schedule_tree
*child
;
1396 return isl_union_map_free(outer
);
1397 if (!isl_schedule_tree_has_children(tree
))
1399 child
= isl_schedule_tree_get_child(tree
, 0);
1401 return isl_union_map_free(outer
);
1402 res
= subtree_schedule_extend(child
, outer
);
1403 isl_schedule_tree_free(child
);
1407 /* Extract the parameter space from one of the children of "tree",
1408 * which are assumed to be filters.
1410 static __isl_give isl_space
*extract_space_from_filter_child(
1411 __isl_keep isl_schedule_tree
*tree
)
1415 isl_schedule_tree
*child
;
1417 child
= isl_schedule_tree_list_get_schedule_tree(tree
->children
, 0);
1418 dom
= isl_schedule_tree_filter_get_filter(child
);
1419 space
= isl_union_set_get_space(dom
);
1420 isl_union_set_free(dom
);
1421 isl_schedule_tree_free(child
);
1426 /* Extend the schedule map "outer" with the subtree schedule
1427 * of a set or sequence node.
1429 * The schedule for the set or sequence node itself is composed of
1430 * pieces of the form
1438 * The first form is used if there is only a single child or
1439 * if the current node is a set node and the schedule_separate_components
1440 * option is not set.
1442 * Each of the pieces above is extended with the subtree schedule of
1443 * the child of the corresponding filter, if any, padded with zeros
1444 * to ensure that all pieces have the same range dimension.
1446 static __isl_give isl_union_map
*subtree_schedule_extend_from_children(
1447 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1456 isl_union_map
*umap
;
1461 ctx
= isl_schedule_tree_get_ctx(tree
);
1462 if (!tree
->children
)
1463 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1464 "missing children", return NULL
);
1465 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1467 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1468 "missing children", return NULL
);
1470 separate
= n
> 1 && (tree
->type
== isl_schedule_node_sequence
||
1471 isl_options_get_schedule_separate_components(ctx
));
1473 space
= extract_space_from_filter_child(tree
);
1475 umap
= isl_union_map_empty(isl_space_copy(space
));
1476 space
= isl_space_set_from_params(space
);
1478 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1479 v
= isl_val_zero(ctx
);
1481 mv
= isl_multi_val_zero(space
);
1483 dim
= isl_multi_val_dim(mv
, isl_dim_set
);
1484 for (i
= 0; i
< n
; ++i
) {
1485 isl_union_pw_multi_aff
*upma
;
1486 isl_union_map
*umap_i
;
1488 isl_schedule_tree
*child
;
1492 child
= isl_schedule_tree_list_get_schedule_tree(
1494 dom
= isl_schedule_tree_filter_get_filter(child
);
1497 mv
= isl_multi_val_set_val(mv
, 0, isl_val_copy(v
));
1498 v
= isl_val_add_ui(v
, 1);
1500 upma
= isl_union_pw_multi_aff_multi_val_on_domain(dom
,
1501 isl_multi_val_copy(mv
));
1502 umap_i
= isl_union_map_from_union_pw_multi_aff(upma
);
1503 umap_i
= isl_union_map_flat_range_product(
1504 isl_union_map_copy(outer
), umap_i
);
1505 umap_i
= subtree_schedule_extend_child(child
, umap_i
);
1506 isl_schedule_tree_free(child
);
1508 empty
= isl_union_map_is_empty(umap_i
);
1510 umap_i
= isl_union_map_free(umap_i
);
1512 isl_union_map_free(umap_i
);
1516 dim_i
= range_dim(umap_i
);
1518 umap
= isl_union_map_free(umap
);
1519 } else if (dim
< dim_i
) {
1520 umap
= append_range(umap
, dim_i
- dim
);
1522 } else if (dim_i
< dim
) {
1523 umap_i
= append_range(umap_i
, dim
- dim_i
);
1525 umap
= isl_union_map_union(umap
, umap_i
);
1529 isl_multi_val_free(mv
);
1530 isl_union_map_free(outer
);
1535 /* Extend the schedule map "outer" with the subtree schedule of "tree".
1537 * If the root of the tree is a set or a sequence, then we extend
1538 * the schedule map in subtree_schedule_extend_from_children.
1539 * Otherwise, we extend the schedule map with the partial schedule
1540 * corresponding to the root of the tree and then continue with
1541 * the single child of this root.
1542 * In the special case of an expansion, the schedule map is "extended"
1543 * by applying the expansion to the domain of the schedule map.
1545 static __isl_give isl_union_map
*subtree_schedule_extend(
1546 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1548 isl_multi_union_pw_aff
*mupa
;
1549 isl_union_map
*umap
;
1550 isl_union_set
*domain
;
1555 switch (tree
->type
) {
1556 case isl_schedule_node_error
:
1557 return isl_union_map_free(outer
);
1558 case isl_schedule_node_context
:
1559 return subtree_schedule_extend_child(tree
, outer
);
1560 case isl_schedule_node_band
:
1561 if (isl_schedule_tree_band_n_member(tree
) == 0)
1562 return subtree_schedule_extend_child(tree
, outer
);
1563 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1564 umap
= isl_union_map_from_multi_union_pw_aff(mupa
);
1565 outer
= isl_union_map_flat_range_product(outer
, umap
);
1566 umap
= subtree_schedule_extend_child(tree
, outer
);
1568 case isl_schedule_node_domain
:
1569 domain
= isl_schedule_tree_domain_get_domain(tree
);
1570 umap
= isl_union_map_from_domain(domain
);
1571 outer
= isl_union_map_flat_range_product(outer
, umap
);
1572 umap
= subtree_schedule_extend_child(tree
, outer
);
1574 case isl_schedule_node_expansion
:
1575 umap
= isl_schedule_tree_expansion_get_expansion(tree
);
1576 outer
= isl_union_map_apply_domain(outer
, umap
);
1577 umap
= subtree_schedule_extend_child(tree
, outer
);
1579 case isl_schedule_node_filter
:
1580 domain
= isl_schedule_tree_filter_get_filter(tree
);
1581 umap
= isl_union_map_from_domain(domain
);
1582 outer
= isl_union_map_flat_range_product(outer
, umap
);
1583 umap
= subtree_schedule_extend_child(tree
, outer
);
1585 case isl_schedule_node_leaf
:
1586 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1587 "leaf node should be handled by caller", return NULL
);
1588 case isl_schedule_node_set
:
1589 case isl_schedule_node_sequence
:
1590 umap
= subtree_schedule_extend_from_children(tree
, outer
);
1597 static __isl_give isl_union_set
*initial_domain(
1598 __isl_keep isl_schedule_tree
*tree
);
1600 /* Extract a universe domain from the children of the tree root "tree",
1601 * which is a set or sequence, meaning that its children are filters.
1602 * In particular, return the union of the universes of the filters.
1604 static __isl_give isl_union_set
*initial_domain_from_children(
1605 __isl_keep isl_schedule_tree
*tree
)
1609 isl_union_set
*domain
;
1611 if (!tree
->children
)
1612 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1613 "missing children", return NULL
);
1614 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1616 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1617 "missing children", return NULL
);
1619 space
= extract_space_from_filter_child(tree
);
1620 domain
= isl_union_set_empty(space
);
1622 for (i
= 0; i
< n
; ++i
) {
1623 isl_schedule_tree
*child
;
1624 isl_union_set
*domain_i
;
1626 child
= isl_schedule_tree_get_child(tree
, i
);
1627 domain_i
= initial_domain(child
);
1628 domain
= isl_union_set_union(domain
, domain_i
);
1629 isl_schedule_tree_free(child
);
1635 /* Extract a universe domain from the tree root "tree".
1636 * The caller is responsible for making sure that this node
1637 * would not be skipped by isl_schedule_tree_first_schedule_descendant
1638 * and that it is not a leaf node.
1640 static __isl_give isl_union_set
*initial_domain(
1641 __isl_keep isl_schedule_tree
*tree
)
1643 isl_multi_union_pw_aff
*mupa
;
1644 isl_union_set
*domain
;
1650 switch (tree
->type
) {
1651 case isl_schedule_node_error
:
1653 case isl_schedule_node_context
:
1654 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1655 "context node should be handled by caller",
1657 case isl_schedule_node_band
:
1658 if (isl_schedule_tree_band_n_member(tree
) == 0)
1659 isl_die(isl_schedule_tree_get_ctx(tree
),
1661 "0D band should be handled by caller",
1663 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1664 domain
= isl_multi_union_pw_aff_domain(mupa
);
1665 domain
= isl_union_set_universe(domain
);
1667 case isl_schedule_node_domain
:
1668 domain
= isl_schedule_tree_domain_get_domain(tree
);
1669 domain
= isl_union_set_universe(domain
);
1671 case isl_schedule_node_expansion
:
1672 exp
= isl_schedule_tree_expansion_get_expansion(tree
);
1673 exp
= isl_union_map_universe(exp
);
1674 domain
= isl_union_map_domain(exp
);
1676 case isl_schedule_node_filter
:
1677 domain
= isl_schedule_tree_filter_get_filter(tree
);
1678 domain
= isl_union_set_universe(domain
);
1680 case isl_schedule_node_leaf
:
1681 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1682 "leaf node should be handled by caller", return NULL
);
1683 case isl_schedule_node_set
:
1684 case isl_schedule_node_sequence
:
1685 domain
= initial_domain_from_children(tree
);
1692 /* Return the subtree schedule of a node that contains some schedule
1693 * information, i.e., a node that would not be skipped by
1694 * isl_schedule_tree_first_schedule_descendant and that is not a leaf.
1696 * If the tree contains any expansions, then the returned subtree
1697 * schedule is formulated in terms of the expanded domains.
1699 * We start with an initial zero-dimensional subtree schedule based
1700 * on the domain information in the root node and then extend it
1701 * based on the schedule information in the root node and its descendants.
1703 __isl_give isl_union_map
*isl_schedule_tree_get_subtree_schedule_union_map(
1704 __isl_keep isl_schedule_tree
*tree
)
1706 isl_union_set
*domain
;
1707 isl_union_map
*umap
;
1709 domain
= initial_domain(tree
);
1710 umap
= isl_union_map_from_domain(domain
);
1711 return subtree_schedule_extend(tree
, umap
);
1714 /* Multiply the partial schedule of the band root node of "tree"
1715 * with the factors in "mv".
1717 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale(
1718 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
1722 if (tree
->type
!= isl_schedule_node_band
)
1723 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1724 "not a band node", goto error
);
1726 tree
= isl_schedule_tree_cow(tree
);
1730 tree
->band
= isl_schedule_band_scale(tree
->band
, mv
);
1732 return isl_schedule_tree_free(tree
);
1736 isl_schedule_tree_free(tree
);
1737 isl_multi_val_free(mv
);
1741 /* Divide the partial schedule of the band root node of "tree"
1742 * by the factors in "mv".
1744 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale_down(
1745 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
1749 if (tree
->type
!= isl_schedule_node_band
)
1750 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1751 "not a band node", goto error
);
1753 tree
= isl_schedule_tree_cow(tree
);
1757 tree
->band
= isl_schedule_band_scale_down(tree
->band
, mv
);
1759 return isl_schedule_tree_free(tree
);
1763 isl_schedule_tree_free(tree
);
1764 isl_multi_val_free(mv
);
1768 /* Tile the band root node of "tree" with tile sizes "sizes".
1770 * We duplicate the band node, change the schedule of one of them
1771 * to the tile schedule and the other to the point schedule and then
1772 * attach the point band as a child to the tile band.
1774 __isl_give isl_schedule_tree
*isl_schedule_tree_band_tile(
1775 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*sizes
)
1777 isl_schedule_tree
*child
= NULL
;
1779 if (!tree
|| !sizes
)
1781 if (tree
->type
!= isl_schedule_node_band
)
1782 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1783 "not a band node", goto error
);
1785 child
= isl_schedule_tree_copy(tree
);
1786 tree
= isl_schedule_tree_cow(tree
);
1787 child
= isl_schedule_tree_cow(child
);
1788 if (!tree
|| !child
)
1791 tree
->band
= isl_schedule_band_tile(tree
->band
,
1792 isl_multi_val_copy(sizes
));
1795 child
->band
= isl_schedule_band_point(child
->band
, tree
->band
, sizes
);
1797 child
= isl_schedule_tree_free(child
);
1799 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
1803 isl_schedule_tree_free(child
);
1804 isl_schedule_tree_free(tree
);
1805 isl_multi_val_free(sizes
);
1809 /* Split the band root node of "tree" into two nested band nodes,
1810 * one with the first "pos" dimensions and
1811 * one with the remaining dimensions.
1813 __isl_give isl_schedule_tree
*isl_schedule_tree_band_split(
1814 __isl_take isl_schedule_tree
*tree
, int pos
)
1817 isl_schedule_tree
*child
;
1821 if (tree
->type
!= isl_schedule_node_band
)
1822 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1823 "not a band node", return isl_schedule_tree_free(tree
));
1825 n
= isl_schedule_tree_band_n_member(tree
);
1826 if (pos
< 0 || pos
> n
)
1827 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1828 "position out of bounds",
1829 return isl_schedule_tree_free(tree
));
1831 child
= isl_schedule_tree_copy(tree
);
1832 tree
= isl_schedule_tree_cow(tree
);
1833 child
= isl_schedule_tree_cow(child
);
1834 if (!tree
|| !child
)
1837 child
->band
= isl_schedule_band_drop(child
->band
, 0, pos
);
1838 tree
->band
= isl_schedule_band_drop(tree
->band
, pos
, n
- pos
);
1839 if (!child
->band
|| !tree
->band
)
1842 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
1846 isl_schedule_tree_free(child
);
1847 isl_schedule_tree_free(tree
);
1851 /* Attach "tree2" at each of the leaves of "tree1".
1853 * If "tree1" does not have any explicit children, then make "tree2"
1854 * its single child. Otherwise, attach "tree2" to the leaves of
1855 * each of the children of "tree1".
1857 __isl_give isl_schedule_tree
*isl_schedule_tree_append_to_leaves(
1858 __isl_take isl_schedule_tree
*tree1
,
1859 __isl_take isl_schedule_tree
*tree2
)
1863 if (!tree1
|| !tree2
)
1865 n
= isl_schedule_tree_n_children(tree1
);
1867 isl_schedule_tree_list
*list
;
1868 list
= isl_schedule_tree_list_from_schedule_tree(tree2
);
1869 tree1
= isl_schedule_tree_set_children(tree1
, list
);
1872 for (i
= 0; i
< n
; ++i
) {
1873 isl_schedule_tree
*child
;
1875 child
= isl_schedule_tree_get_child(tree1
, i
);
1876 child
= isl_schedule_tree_append_to_leaves(child
,
1877 isl_schedule_tree_copy(tree2
));
1878 tree1
= isl_schedule_tree_replace_child(tree1
, i
, child
);
1881 isl_schedule_tree_free(tree2
);
1884 isl_schedule_tree_free(tree1
);
1885 isl_schedule_tree_free(tree2
);
1889 /* Reset the user pointer on all identifiers of parameters and tuples
1890 * in the root of "tree".
1892 __isl_give isl_schedule_tree
*isl_schedule_tree_reset_user(
1893 __isl_take isl_schedule_tree
*tree
)
1895 if (isl_schedule_tree_is_leaf(tree
))
1898 tree
= isl_schedule_tree_cow(tree
);
1902 switch (tree
->type
) {
1903 case isl_schedule_node_error
:
1904 return isl_schedule_tree_free(tree
);
1905 case isl_schedule_node_band
:
1906 tree
->band
= isl_schedule_band_reset_user(tree
->band
);
1908 return isl_schedule_tree_free(tree
);
1910 case isl_schedule_node_context
:
1911 tree
->context
= isl_set_reset_user(tree
->context
);
1913 return isl_schedule_tree_free(tree
);
1915 case isl_schedule_node_domain
:
1916 tree
->domain
= isl_union_set_reset_user(tree
->domain
);
1918 return isl_schedule_tree_free(tree
);
1920 case isl_schedule_node_expansion
:
1922 isl_union_pw_multi_aff_reset_user(tree
->contraction
);
1923 tree
->expansion
= isl_union_map_reset_user(tree
->expansion
);
1924 if (!tree
->contraction
|| !tree
->expansion
)
1925 return isl_schedule_tree_free(tree
);
1927 case isl_schedule_node_filter
:
1928 tree
->filter
= isl_union_set_reset_user(tree
->filter
);
1930 return isl_schedule_tree_free(tree
);
1932 case isl_schedule_node_leaf
:
1933 case isl_schedule_node_sequence
:
1934 case isl_schedule_node_set
:
1941 /* Align the parameters of the root of "tree" to those of "space".
1943 __isl_give isl_schedule_tree
*isl_schedule_tree_align_params(
1944 __isl_take isl_schedule_tree
*tree
, __isl_take isl_space
*space
)
1949 if (isl_schedule_tree_is_leaf(tree
)) {
1950 isl_space_free(space
);
1954 tree
= isl_schedule_tree_cow(tree
);
1958 switch (tree
->type
) {
1959 case isl_schedule_node_error
:
1961 case isl_schedule_node_band
:
1962 tree
->band
= isl_schedule_band_align_params(tree
->band
, space
);
1964 return isl_schedule_tree_free(tree
);
1966 case isl_schedule_node_context
:
1967 tree
->context
= isl_set_align_params(tree
->context
, space
);
1969 return isl_schedule_tree_free(tree
);
1971 case isl_schedule_node_domain
:
1972 tree
->domain
= isl_union_set_align_params(tree
->domain
, space
);
1974 return isl_schedule_tree_free(tree
);
1976 case isl_schedule_node_expansion
:
1978 isl_union_pw_multi_aff_align_params(tree
->contraction
,
1979 isl_space_copy(space
));
1980 tree
->expansion
= isl_union_map_align_params(tree
->expansion
,
1982 if (!tree
->contraction
|| !tree
->expansion
)
1983 return isl_schedule_tree_free(tree
);
1985 case isl_schedule_node_filter
:
1986 tree
->filter
= isl_union_set_align_params(tree
->filter
, space
);
1988 return isl_schedule_tree_free(tree
);
1990 case isl_schedule_node_leaf
:
1991 case isl_schedule_node_sequence
:
1992 case isl_schedule_node_set
:
1993 isl_space_free(space
);
1999 isl_space_free(space
);
2000 isl_schedule_tree_free(tree
);
2004 /* Does "tree" involve the iteration domain?
2005 * That is, does it need to be modified
2006 * by isl_schedule_tree_pullback_union_pw_multi_aff?
2008 static int involves_iteration_domain(__isl_keep isl_schedule_tree
*tree
)
2013 switch (tree
->type
) {
2014 case isl_schedule_node_error
:
2016 case isl_schedule_node_band
:
2017 case isl_schedule_node_domain
:
2018 case isl_schedule_node_expansion
:
2019 case isl_schedule_node_filter
:
2021 case isl_schedule_node_context
:
2022 case isl_schedule_node_leaf
:
2023 case isl_schedule_node_sequence
:
2024 case isl_schedule_node_set
:
2029 /* Compute the pullback of the root node of "tree" by the function
2030 * represented by "upma".
2031 * In other words, plug in "upma" in the iteration domains of
2032 * the root node of "tree".
2033 * We currently do not handle expansion nodes.
2035 * We first check if the root node involves any iteration domains.
2036 * If so, we handle the specific cases.
2038 __isl_give isl_schedule_tree
*isl_schedule_tree_pullback_union_pw_multi_aff(
2039 __isl_take isl_schedule_tree
*tree
,
2040 __isl_take isl_union_pw_multi_aff
*upma
)
2047 involves
= involves_iteration_domain(tree
);
2051 isl_union_pw_multi_aff_free(upma
);
2055 tree
= isl_schedule_tree_cow(tree
);
2059 if (tree
->type
== isl_schedule_node_band
) {
2060 tree
->band
= isl_schedule_band_pullback_union_pw_multi_aff(
2063 return isl_schedule_tree_free(tree
);
2064 } else if (tree
->type
== isl_schedule_node_domain
) {
2066 isl_union_set_preimage_union_pw_multi_aff(tree
->domain
,
2069 return isl_schedule_tree_free(tree
);
2070 } else if (tree
->type
== isl_schedule_node_expansion
) {
2071 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_unsupported
,
2072 "cannot pullback expansion node", goto error
);
2073 } else if (tree
->type
== isl_schedule_node_filter
) {
2075 isl_union_set_preimage_union_pw_multi_aff(tree
->filter
,
2078 return isl_schedule_tree_free(tree
);
2083 isl_union_pw_multi_aff_free(upma
);
2084 isl_schedule_tree_free(tree
);
2088 /* Compute the gist of the band tree root with respect to "context".
2090 __isl_give isl_schedule_tree
*isl_schedule_tree_band_gist(
2091 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*context
)
2095 if (tree
->type
!= isl_schedule_node_band
)
2096 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2097 "not a band node", goto error
);
2098 tree
= isl_schedule_tree_cow(tree
);
2102 tree
->band
= isl_schedule_band_gist(tree
->band
, context
);
2104 return isl_schedule_tree_free(tree
);
2107 isl_union_set_free(context
);
2108 isl_schedule_tree_free(tree
);
2112 /* Are any members in "band" marked coincident?
2114 static int any_coincident(__isl_keep isl_schedule_band
*band
)
2118 n
= isl_schedule_band_n_member(band
);
2119 for (i
= 0; i
< n
; ++i
)
2120 if (isl_schedule_band_member_get_coincident(band
, i
))
2126 /* Print the band node "band" to "p".
2128 * The permutable and coincident properties are only printed if they
2129 * are different from the defaults.
2130 * The coincident property is always printed in YAML flow style.
2132 static __isl_give isl_printer
*print_tree_band(__isl_take isl_printer
*p
,
2133 __isl_keep isl_schedule_band
*band
)
2135 isl_union_set
*options
;
2138 p
= isl_printer_print_str(p
, "schedule");
2139 p
= isl_printer_yaml_next(p
);
2140 p
= isl_printer_print_str(p
, "\"");
2141 p
= isl_printer_print_multi_union_pw_aff(p
, band
->mupa
);
2142 p
= isl_printer_print_str(p
, "\"");
2143 if (isl_schedule_band_get_permutable(band
)) {
2144 p
= isl_printer_yaml_next(p
);
2145 p
= isl_printer_print_str(p
, "permutable");
2146 p
= isl_printer_yaml_next(p
);
2147 p
= isl_printer_print_int(p
, 1);
2149 if (any_coincident(band
)) {
2153 p
= isl_printer_yaml_next(p
);
2154 p
= isl_printer_print_str(p
, "coincident");
2155 p
= isl_printer_yaml_next(p
);
2156 style
= isl_printer_get_yaml_style(p
);
2157 p
= isl_printer_set_yaml_style(p
, ISL_YAML_STYLE_FLOW
);
2158 p
= isl_printer_yaml_start_sequence(p
);
2159 n
= isl_schedule_band_n_member(band
);
2160 for (i
= 0; i
< n
; ++i
) {
2161 p
= isl_printer_print_int(p
,
2162 isl_schedule_band_member_get_coincident(band
, i
));
2163 p
= isl_printer_yaml_next(p
);
2165 p
= isl_printer_yaml_end_sequence(p
);
2166 p
= isl_printer_set_yaml_style(p
, style
);
2168 options
= isl_schedule_band_get_ast_build_options(band
);
2169 empty
= isl_union_set_is_empty(options
);
2171 p
= isl_printer_free(p
);
2173 p
= isl_printer_yaml_next(p
);
2174 p
= isl_printer_print_str(p
, "options");
2175 p
= isl_printer_yaml_next(p
);
2176 p
= isl_printer_print_str(p
, "\"");
2177 p
= isl_printer_print_union_set(p
, options
);
2178 p
= isl_printer_print_str(p
, "\"");
2180 isl_union_set_free(options
);
2185 /* Print "tree" to "p".
2187 * If "n_ancestor" is non-negative, then "child_pos" contains the child
2188 * positions of a descendant of the current node that should be marked
2189 * (by the comment "YOU ARE HERE"). In particular, if "n_ancestor"
2190 * is zero, then the current node should be marked.
2191 * The marking is only printed in YAML block format.
2193 * Implicit leaf nodes are not printed, except if they correspond
2194 * to the node that should be marked.
2196 __isl_give isl_printer
*isl_printer_print_schedule_tree_mark(
2197 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
,
2198 int n_ancestor
, int *child_pos
)
2204 block
= isl_printer_get_yaml_style(p
) == ISL_YAML_STYLE_BLOCK
;
2206 p
= isl_printer_yaml_start_mapping(p
);
2207 if (n_ancestor
== 0 && block
) {
2208 p
= isl_printer_print_str(p
, "# YOU ARE HERE");
2209 p
= isl_printer_end_line(p
);
2210 p
= isl_printer_start_line(p
);
2212 switch (tree
->type
) {
2213 case isl_schedule_node_error
:
2214 p
= isl_printer_print_str(p
, "ERROR");
2216 case isl_schedule_node_leaf
:
2217 p
= isl_printer_print_str(p
, "leaf");
2219 case isl_schedule_node_sequence
:
2220 p
= isl_printer_print_str(p
, "sequence");
2223 case isl_schedule_node_set
:
2224 p
= isl_printer_print_str(p
, "set");
2227 case isl_schedule_node_context
:
2228 p
= isl_printer_print_str(p
, "context");
2229 p
= isl_printer_yaml_next(p
);
2230 p
= isl_printer_print_str(p
, "\"");
2231 p
= isl_printer_print_set(p
, tree
->context
);
2232 p
= isl_printer_print_str(p
, "\"");
2234 case isl_schedule_node_domain
:
2235 p
= isl_printer_print_str(p
, "domain");
2236 p
= isl_printer_yaml_next(p
);
2237 p
= isl_printer_print_str(p
, "\"");
2238 p
= isl_printer_print_union_set(p
, tree
->domain
);
2239 p
= isl_printer_print_str(p
, "\"");
2241 case isl_schedule_node_expansion
:
2242 p
= isl_printer_print_str(p
, "contraction");
2243 p
= isl_printer_yaml_next(p
);
2244 p
= isl_printer_print_str(p
, "\"");
2245 p
= isl_printer_print_union_pw_multi_aff(p
, tree
->contraction
);
2246 p
= isl_printer_print_str(p
, "\"");
2247 p
= isl_printer_yaml_next(p
);
2248 p
= isl_printer_print_str(p
, "expansion");
2249 p
= isl_printer_yaml_next(p
);
2250 p
= isl_printer_print_str(p
, "\"");
2251 p
= isl_printer_print_union_map(p
, tree
->expansion
);
2252 p
= isl_printer_print_str(p
, "\"");
2254 case isl_schedule_node_filter
:
2255 p
= isl_printer_print_str(p
, "filter");
2256 p
= isl_printer_yaml_next(p
);
2257 p
= isl_printer_print_str(p
, "\"");
2258 p
= isl_printer_print_union_set(p
, tree
->filter
);
2259 p
= isl_printer_print_str(p
, "\"");
2261 case isl_schedule_node_band
:
2262 p
= print_tree_band(p
, tree
->band
);
2265 p
= isl_printer_yaml_next(p
);
2267 if (!tree
->children
) {
2268 if (n_ancestor
> 0 && block
) {
2269 isl_schedule_tree
*leaf
;
2271 p
= isl_printer_print_str(p
, "child");
2272 p
= isl_printer_yaml_next(p
);
2273 leaf
= isl_schedule_tree_leaf(isl_printer_get_ctx(p
));
2274 p
= isl_printer_print_schedule_tree_mark(p
,
2276 isl_schedule_tree_free(leaf
);
2277 p
= isl_printer_yaml_next(p
);
2279 return isl_printer_yaml_end_mapping(p
);
2283 p
= isl_printer_yaml_start_sequence(p
);
2285 p
= isl_printer_print_str(p
, "child");
2286 p
= isl_printer_yaml_next(p
);
2289 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
2290 for (i
= 0; i
< n
; ++i
) {
2291 isl_schedule_tree
*t
;
2293 t
= isl_schedule_tree_get_child(tree
, i
);
2294 if (n_ancestor
> 0 && child_pos
[0] == i
)
2295 p
= isl_printer_print_schedule_tree_mark(p
, t
,
2296 n_ancestor
- 1, child_pos
+ 1);
2298 p
= isl_printer_print_schedule_tree_mark(p
, t
,
2300 isl_schedule_tree_free(t
);
2302 p
= isl_printer_yaml_next(p
);
2306 p
= isl_printer_yaml_end_sequence(p
);
2307 p
= isl_printer_yaml_end_mapping(p
);
2312 /* Print "tree" to "p".
2314 __isl_give isl_printer
*isl_printer_print_schedule_tree(
2315 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
)
2317 return isl_printer_print_schedule_tree_mark(p
, tree
, -1, NULL
);
2320 void isl_schedule_tree_dump(__isl_keep isl_schedule_tree
*tree
)
2323 isl_printer
*printer
;
2328 ctx
= isl_schedule_tree_get_ctx(tree
);
2329 printer
= isl_printer_to_file(ctx
, stderr
);
2330 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
2331 printer
= isl_printer_print_schedule_tree(printer
, tree
);
2333 isl_printer_free(printer
);