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_filter
:
99 dup
->filter
= isl_union_set_copy(tree
->filter
);
101 return isl_schedule_tree_free(dup
);
103 case isl_schedule_node_leaf
:
104 case isl_schedule_node_sequence
:
105 case isl_schedule_node_set
:
109 if (tree
->children
) {
110 dup
->children
= isl_schedule_tree_list_copy(tree
->children
);
112 return isl_schedule_tree_free(dup
);
114 dup
->anchored
= tree
->anchored
;
119 /* Return an isl_schedule_tree that is equal to "tree" and that has only
120 * a single reference.
122 * This function is called before a tree is modified.
123 * A static tree (with negative reference count) should never be modified,
124 * so it is not allowed to call this function on a static tree.
126 __isl_give isl_schedule_tree
*isl_schedule_tree_cow(
127 __isl_take isl_schedule_tree
*tree
)
133 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
134 "static trees cannot be modified",
135 return isl_schedule_tree_free(tree
));
140 return isl_schedule_tree_dup(tree
);
143 /* Return a new reference to "tree".
145 * A static tree (with negative reference count) does not keep track
146 * of the number of references and should not be modified.
148 __isl_give isl_schedule_tree
*isl_schedule_tree_copy(
149 __isl_keep isl_schedule_tree
*tree
)
161 /* Free "tree" and return NULL.
163 __isl_null isl_schedule_tree
*isl_schedule_tree_free(
164 __isl_take isl_schedule_tree
*tree
)
173 switch (tree
->type
) {
174 case isl_schedule_node_band
:
175 isl_schedule_band_free(tree
->band
);
177 case isl_schedule_node_context
:
178 isl_set_free(tree
->context
);
180 case isl_schedule_node_domain
:
181 isl_union_set_free(tree
->domain
);
183 case isl_schedule_node_filter
:
184 isl_union_set_free(tree
->filter
);
186 case isl_schedule_node_sequence
:
187 case isl_schedule_node_set
:
188 case isl_schedule_node_error
:
189 case isl_schedule_node_leaf
:
192 isl_schedule_tree_list_free(tree
->children
);
193 isl_ctx_deref(tree
->ctx
);
199 /* Create and return a new leaf schedule tree.
201 __isl_give isl_schedule_tree
*isl_schedule_tree_leaf(isl_ctx
*ctx
)
203 return isl_schedule_tree_alloc(ctx
, isl_schedule_node_leaf
);
206 /* Create a new band schedule tree referring to "band"
209 __isl_give isl_schedule_tree
*isl_schedule_tree_from_band(
210 __isl_take isl_schedule_band
*band
)
213 isl_schedule_tree
*tree
;
218 ctx
= isl_schedule_band_get_ctx(band
);
219 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_band
);
224 tree
->anchored
= isl_schedule_band_is_anchored(band
);
228 isl_schedule_band_free(band
);
232 /* Create a new context schedule tree with the given context and no children.
233 * Since the context references the outer schedule dimension,
234 * the tree is anchored.
236 __isl_give isl_schedule_tree
*isl_schedule_tree_from_context(
237 __isl_take isl_set
*context
)
240 isl_schedule_tree
*tree
;
245 ctx
= isl_set_get_ctx(context
);
246 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_context
);
250 tree
->context
= context
;
255 isl_set_free(context
);
259 /* Create a new domain schedule tree with the given domain and no children.
261 __isl_give isl_schedule_tree
*isl_schedule_tree_from_domain(
262 __isl_take isl_union_set
*domain
)
265 isl_schedule_tree
*tree
;
270 ctx
= isl_union_set_get_ctx(domain
);
271 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_domain
);
275 tree
->domain
= domain
;
279 isl_union_set_free(domain
);
283 /* Create a new filter schedule tree with the given filter and no children.
285 __isl_give isl_schedule_tree
*isl_schedule_tree_from_filter(
286 __isl_take isl_union_set
*filter
)
289 isl_schedule_tree
*tree
;
294 ctx
= isl_union_set_get_ctx(filter
);
295 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_filter
);
299 tree
->filter
= filter
;
303 isl_union_set_free(filter
);
307 /* Does "tree" have any node that depends on its position
308 * in the complete schedule tree?
310 int isl_schedule_tree_is_subtree_anchored(__isl_keep isl_schedule_tree
*tree
)
312 return tree
? tree
->anchored
: -1;
315 /* Does the root node of "tree" depend on its position in the complete
317 * Band nodes may be anchored depending on the associated AST build options.
318 * Context nodes are always anchored.
320 int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree
*tree
)
325 switch (isl_schedule_tree_get_type(tree
)) {
326 case isl_schedule_node_error
:
328 case isl_schedule_node_band
:
329 return isl_schedule_band_is_anchored(tree
->band
);
330 case isl_schedule_node_context
:
332 case isl_schedule_node_domain
:
333 case isl_schedule_node_filter
:
334 case isl_schedule_node_leaf
:
335 case isl_schedule_node_sequence
:
336 case isl_schedule_node_set
:
341 /* Update the anchored field of "tree" based on whether the root node
342 * itself in anchored and the anchored fields of the children.
344 * This function should be called whenever the children of a tree node
345 * are changed or the anchoredness of the tree root itself changes.
347 __isl_give isl_schedule_tree
*isl_schedule_tree_update_anchored(
348 __isl_take isl_schedule_tree
*tree
)
356 anchored
= isl_schedule_tree_is_anchored(tree
);
358 return isl_schedule_tree_free(tree
);
360 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
361 for (i
= 0; !anchored
&& i
< n
; ++i
) {
362 isl_schedule_tree
*child
;
364 child
= isl_schedule_tree_get_child(tree
, i
);
366 return isl_schedule_tree_free(tree
);
367 anchored
= child
->anchored
;
368 isl_schedule_tree_free(child
);
371 if (anchored
== tree
->anchored
)
373 tree
= isl_schedule_tree_cow(tree
);
376 tree
->anchored
= anchored
;
380 /* Create a new tree of the given type (isl_schedule_node_sequence or
381 * isl_schedule_node_set) with the given children.
383 __isl_give isl_schedule_tree
*isl_schedule_tree_from_children(
384 enum isl_schedule_node_type type
,
385 __isl_take isl_schedule_tree_list
*list
)
388 isl_schedule_tree
*tree
;
393 ctx
= isl_schedule_tree_list_get_ctx(list
);
394 tree
= isl_schedule_tree_alloc(ctx
, type
);
398 tree
->children
= list
;
399 tree
= isl_schedule_tree_update_anchored(tree
);
403 isl_schedule_tree_list_free(list
);
407 /* Construct a tree with a root node of type "type" and as children
408 * "tree1" and "tree2".
409 * If the root of one (or both) of the input trees is itself of type "type",
410 * then the tree is replaced by its children.
412 __isl_give isl_schedule_tree
*isl_schedule_tree_from_pair(
413 enum isl_schedule_node_type type
, __isl_take isl_schedule_tree
*tree1
,
414 __isl_take isl_schedule_tree
*tree2
)
417 isl_schedule_tree_list
*list
;
419 if (!tree1
|| !tree2
)
422 ctx
= isl_schedule_tree_get_ctx(tree1
);
423 if (isl_schedule_tree_get_type(tree1
) == type
) {
424 list
= isl_schedule_tree_list_copy(tree1
->children
);
425 isl_schedule_tree_free(tree1
);
427 list
= isl_schedule_tree_list_alloc(ctx
, 2);
428 list
= isl_schedule_tree_list_add(list
, tree1
);
430 if (isl_schedule_tree_get_type(tree2
) == type
) {
431 isl_schedule_tree_list
*children
;
433 children
= isl_schedule_tree_list_copy(tree2
->children
);
434 list
= isl_schedule_tree_list_concat(list
, children
);
435 isl_schedule_tree_free(tree2
);
437 list
= isl_schedule_tree_list_add(list
, tree2
);
440 return isl_schedule_tree_from_children(type
, list
);
442 isl_schedule_tree_free(tree1
);
443 isl_schedule_tree_free(tree2
);
447 /* Return the isl_ctx to which "tree" belongs.
449 isl_ctx
*isl_schedule_tree_get_ctx(__isl_keep isl_schedule_tree
*tree
)
451 return tree
? tree
->ctx
: NULL
;
454 /* Return the type of the root of the tree or isl_schedule_node_error
457 enum isl_schedule_node_type
isl_schedule_tree_get_type(
458 __isl_keep isl_schedule_tree
*tree
)
460 return tree
? tree
->type
: isl_schedule_node_error
;
463 /* Are "tree1" and "tree2" obviously equal to each other?
465 int isl_schedule_tree_plain_is_equal(__isl_keep isl_schedule_tree
*tree1
,
466 __isl_keep isl_schedule_tree
*tree2
)
471 if (!tree1
|| !tree2
)
475 if (tree1
->type
!= tree2
->type
)
478 switch (tree1
->type
) {
479 case isl_schedule_node_band
:
480 equal
= isl_schedule_band_plain_is_equal(tree1
->band
,
483 case isl_schedule_node_context
:
484 equal
= isl_set_is_equal(tree1
->context
, tree2
->context
);
486 case isl_schedule_node_domain
:
487 equal
= isl_union_set_is_equal(tree1
->domain
, tree2
->domain
);
489 case isl_schedule_node_filter
:
490 equal
= isl_union_set_is_equal(tree1
->filter
, tree2
->filter
);
492 case isl_schedule_node_leaf
:
493 case isl_schedule_node_sequence
:
494 case isl_schedule_node_set
:
497 case isl_schedule_node_error
:
502 if (equal
< 0 || !equal
)
505 n
= isl_schedule_tree_n_children(tree1
);
506 if (n
!= isl_schedule_tree_n_children(tree2
))
508 for (i
= 0; i
< n
; ++i
) {
509 isl_schedule_tree
*child1
, *child2
;
511 child1
= isl_schedule_tree_get_child(tree1
, i
);
512 child2
= isl_schedule_tree_get_child(tree2
, i
);
513 equal
= isl_schedule_tree_plain_is_equal(child1
, child2
);
514 isl_schedule_tree_free(child1
);
515 isl_schedule_tree_free(child2
);
517 if (equal
< 0 || !equal
)
524 /* Does "tree" have any children, other than an implicit leaf.
526 int isl_schedule_tree_has_children(__isl_keep isl_schedule_tree
*tree
)
531 return tree
->children
!= NULL
;
534 /* Return the number of children of "tree", excluding implicit leaves.
536 int isl_schedule_tree_n_children(__isl_keep isl_schedule_tree
*tree
)
541 return isl_schedule_tree_list_n_schedule_tree(tree
->children
);
544 /* Return a copy of the (explicit) child at position "pos" of "tree".
546 __isl_give isl_schedule_tree
*isl_schedule_tree_get_child(
547 __isl_keep isl_schedule_tree
*tree
, int pos
)
552 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
553 "schedule tree has no explicit children", return NULL
);
554 return isl_schedule_tree_list_get_schedule_tree(tree
->children
, pos
);
557 /* Return a copy of the (explicit) child at position "pos" of "tree" and
560 __isl_give isl_schedule_tree
*isl_schedule_tree_child(
561 __isl_take isl_schedule_tree
*tree
, int pos
)
563 isl_schedule_tree
*child
;
565 child
= isl_schedule_tree_get_child(tree
, pos
);
566 isl_schedule_tree_free(tree
);
570 /* Remove all (explicit) children from "tree".
572 __isl_give isl_schedule_tree
*isl_schedule_tree_reset_children(
573 __isl_take isl_schedule_tree
*tree
)
575 tree
= isl_schedule_tree_cow(tree
);
578 tree
->children
= isl_schedule_tree_list_free(tree
->children
);
582 /* Remove the child at position "pos" from the children of "tree".
583 * If there was only one child to begin with, then remove all children.
585 __isl_give isl_schedule_tree
*isl_schedule_tree_drop_child(
586 __isl_take isl_schedule_tree
*tree
, int pos
)
590 tree
= isl_schedule_tree_cow(tree
);
594 if (!isl_schedule_tree_has_children(tree
))
595 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
596 "tree does not have any explicit children",
597 return isl_schedule_tree_free(tree
));
598 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
599 if (pos
< 0 || pos
>= n
)
600 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
601 "position out of bounds",
602 return isl_schedule_tree_free(tree
));
604 return isl_schedule_tree_reset_children(tree
);
606 tree
->children
= isl_schedule_tree_list_drop(tree
->children
, pos
, 1);
608 return isl_schedule_tree_free(tree
);
613 /* Replace the child at position "pos" of "tree" by "child".
615 * If the new child is a leaf, then it is not explicitly
616 * recorded in the list of children. Instead, the list of children
617 * (which is assumed to have only one element) is removed.
618 * Note that the children of set and sequence nodes are always
619 * filters, so they cannot be replaced by empty trees.
621 __isl_give isl_schedule_tree
*isl_schedule_tree_replace_child(
622 __isl_take isl_schedule_tree
*tree
, int pos
,
623 __isl_take isl_schedule_tree
*child
)
625 tree
= isl_schedule_tree_cow(tree
);
629 if (isl_schedule_tree_is_leaf(child
)) {
630 isl_schedule_tree_free(child
);
631 if (!tree
->children
&& pos
== 0)
633 if (isl_schedule_tree_n_children(tree
) != 1)
634 isl_die(isl_schedule_tree_get_ctx(tree
),
636 "can only replace single child by leaf",
638 return isl_schedule_tree_reset_children(tree
);
641 if (!tree
->children
&& pos
== 0)
643 isl_schedule_tree_list_from_schedule_tree(child
);
645 tree
->children
= isl_schedule_tree_list_set_schedule_tree(
646 tree
->children
, pos
, child
);
649 return isl_schedule_tree_free(tree
);
650 tree
= isl_schedule_tree_update_anchored(tree
);
654 isl_schedule_tree_free(tree
);
655 isl_schedule_tree_free(child
);
659 /* Replace the (explicit) children of "tree" by "children"?
661 __isl_give isl_schedule_tree
*isl_schedule_tree_set_children(
662 __isl_take isl_schedule_tree
*tree
,
663 __isl_take isl_schedule_tree_list
*children
)
665 tree
= isl_schedule_tree_cow(tree
);
666 if (!tree
|| !children
)
668 isl_schedule_tree_list_free(tree
->children
);
669 tree
->children
= children
;
672 isl_schedule_tree_free(tree
);
673 isl_schedule_tree_list_free(children
);
677 /* Create a new band schedule tree referring to "band"
678 * with "tree" as single child.
680 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_band(
681 __isl_take isl_schedule_tree
*tree
, __isl_take isl_schedule_band
*band
)
683 isl_schedule_tree
*res
;
685 res
= isl_schedule_tree_from_band(band
);
686 return isl_schedule_tree_replace_child(res
, 0, tree
);
689 /* Create a new context schedule tree with the given context and
690 * with "tree" as single child.
692 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_context(
693 __isl_take isl_schedule_tree
*tree
, __isl_take isl_set
*context
)
695 isl_schedule_tree
*res
;
697 res
= isl_schedule_tree_from_context(context
);
698 return isl_schedule_tree_replace_child(res
, 0, tree
);
701 /* Create a new domain schedule tree with the given domain and
702 * with "tree" as single child.
704 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_domain(
705 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
707 isl_schedule_tree
*res
;
709 res
= isl_schedule_tree_from_domain(domain
);
710 return isl_schedule_tree_replace_child(res
, 0, tree
);
713 /* Create a new filter schedule tree with the given filter and single child.
715 * If the root of "tree" is itself a filter node, then the two
716 * filter nodes are merged into one node.
718 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_filter(
719 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
721 isl_schedule_tree
*res
;
723 if (isl_schedule_tree_get_type(tree
) == isl_schedule_node_filter
) {
724 isl_union_set
*tree_filter
;
726 tree_filter
= isl_schedule_tree_filter_get_filter(tree
);
727 tree_filter
= isl_union_set_intersect(tree_filter
, filter
);
728 tree
= isl_schedule_tree_filter_set_filter(tree
, tree_filter
);
732 res
= isl_schedule_tree_from_filter(filter
);
733 return isl_schedule_tree_replace_child(res
, 0, tree
);
736 /* Insert a filter node with filter set "filter"
737 * in each of the children of "tree".
739 __isl_give isl_schedule_tree
*isl_schedule_tree_children_insert_filter(
740 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
744 if (!tree
|| !filter
)
747 n
= isl_schedule_tree_n_children(tree
);
748 for (i
= 0; i
< n
; ++i
) {
749 isl_schedule_tree
*child
;
751 child
= isl_schedule_tree_get_child(tree
, i
);
752 child
= isl_schedule_tree_insert_filter(child
,
753 isl_union_set_copy(filter
));
754 tree
= isl_schedule_tree_replace_child(tree
, i
, child
);
757 isl_union_set_free(filter
);
760 isl_union_set_free(filter
);
761 isl_schedule_tree_free(tree
);
765 /* Return the number of members in the band tree root.
767 unsigned isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree
*tree
)
772 if (tree
->type
!= isl_schedule_node_band
)
773 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
774 "not a band node", return 0);
776 return isl_schedule_band_n_member(tree
->band
);
779 /* Is the band member at position "pos" of the band tree root
782 int isl_schedule_tree_band_member_get_coincident(
783 __isl_keep isl_schedule_tree
*tree
, int pos
)
788 if (tree
->type
!= isl_schedule_node_band
)
789 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
790 "not a band node", return -1);
792 return isl_schedule_band_member_get_coincident(tree
->band
, pos
);
795 /* Mark the given band member as being coincident or not
796 * according to "coincident".
798 __isl_give isl_schedule_tree
*isl_schedule_tree_band_member_set_coincident(
799 __isl_take isl_schedule_tree
*tree
, int pos
, int coincident
)
803 if (tree
->type
!= isl_schedule_node_band
)
804 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
805 "not a band node", return isl_schedule_tree_free(tree
));
806 if (isl_schedule_tree_band_member_get_coincident(tree
, pos
) ==
809 tree
= isl_schedule_tree_cow(tree
);
813 tree
->band
= isl_schedule_band_member_set_coincident(tree
->band
, pos
,
816 return isl_schedule_tree_free(tree
);
820 /* Is the band tree root marked permutable?
822 int isl_schedule_tree_band_get_permutable(__isl_keep isl_schedule_tree
*tree
)
827 if (tree
->type
!= isl_schedule_node_band
)
828 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
829 "not a band node", return -1);
831 return isl_schedule_band_get_permutable(tree
->band
);
834 /* Mark the band tree root permutable or not according to "permutable"?
836 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_permutable(
837 __isl_take isl_schedule_tree
*tree
, int permutable
)
841 if (tree
->type
!= isl_schedule_node_band
)
842 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
843 "not a band node", return isl_schedule_tree_free(tree
));
844 if (isl_schedule_tree_band_get_permutable(tree
) == permutable
)
846 tree
= isl_schedule_tree_cow(tree
);
850 tree
->band
= isl_schedule_band_set_permutable(tree
->band
, permutable
);
852 return isl_schedule_tree_free(tree
);
856 /* Return the schedule space of the band tree root.
858 __isl_give isl_space
*isl_schedule_tree_band_get_space(
859 __isl_keep isl_schedule_tree
*tree
)
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 NULL
);
868 return isl_schedule_band_get_space(tree
->band
);
871 /* Return the schedule of the band tree root in isolation.
873 __isl_give isl_multi_union_pw_aff
*isl_schedule_tree_band_get_partial_schedule(
874 __isl_keep isl_schedule_tree
*tree
)
879 if (tree
->type
!= isl_schedule_node_band
)
880 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
881 "not a band node", return NULL
);
883 return isl_schedule_band_get_partial_schedule(tree
->band
);
886 /* Return the loop AST generation type for the band member
887 * of the band tree root at position "pos".
889 enum isl_ast_loop_type
isl_schedule_tree_band_member_get_ast_loop_type(
890 __isl_keep isl_schedule_tree
*tree
, int pos
)
893 return isl_ast_loop_error
;
895 if (tree
->type
!= isl_schedule_node_band
)
896 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
897 "not a band node", return isl_ast_loop_error
);
899 return isl_schedule_band_member_get_ast_loop_type(tree
->band
, pos
);
902 /* Set the loop AST generation type for the band member of the band tree root
903 * at position "pos" to "type".
905 __isl_give isl_schedule_tree
*isl_schedule_tree_band_member_set_ast_loop_type(
906 __isl_take isl_schedule_tree
*tree
, int pos
,
907 enum isl_ast_loop_type type
)
909 tree
= isl_schedule_tree_cow(tree
);
913 if (tree
->type
!= isl_schedule_node_band
)
914 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
915 "not a band node", return isl_schedule_tree_free(tree
));
917 tree
->band
= isl_schedule_band_member_set_ast_loop_type(tree
->band
,
920 return isl_schedule_tree_free(tree
);
925 /* Return the loop AST generation type for the band member
926 * of the band tree root at position "pos" for the isolated part.
928 enum isl_ast_loop_type
isl_schedule_tree_band_member_get_isolate_ast_loop_type(
929 __isl_keep isl_schedule_tree
*tree
, int pos
)
932 return isl_ast_loop_error
;
934 if (tree
->type
!= isl_schedule_node_band
)
935 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
936 "not a band node", return isl_ast_loop_error
);
938 return isl_schedule_band_member_get_isolate_ast_loop_type(tree
->band
,
942 /* Set the loop AST generation type for the band member of the band tree root
943 * at position "pos" for the isolated part to "type".
945 __isl_give isl_schedule_tree
*
946 isl_schedule_tree_band_member_set_isolate_ast_loop_type(
947 __isl_take isl_schedule_tree
*tree
, int pos
,
948 enum isl_ast_loop_type type
)
950 tree
= isl_schedule_tree_cow(tree
);
954 if (tree
->type
!= isl_schedule_node_band
)
955 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
956 "not a band node", return isl_schedule_tree_free(tree
));
958 tree
->band
= isl_schedule_band_member_set_isolate_ast_loop_type(
959 tree
->band
, pos
, type
);
961 return isl_schedule_tree_free(tree
);
966 /* Return the AST build options associated to the band tree root.
968 __isl_give isl_union_set
*isl_schedule_tree_band_get_ast_build_options(
969 __isl_keep isl_schedule_tree
*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 NULL
);
978 return isl_schedule_band_get_ast_build_options(tree
->band
);
981 /* Replace the AST build options associated to band tree root by "options".
982 * Updated the anchored field if the anchoredness of the root node itself
985 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_ast_build_options(
986 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*options
)
990 tree
= isl_schedule_tree_cow(tree
);
991 if (!tree
|| !options
)
994 if (tree
->type
!= isl_schedule_node_band
)
995 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
996 "not a band node", goto error
);
998 was_anchored
= isl_schedule_tree_is_anchored(tree
);
999 tree
->band
= isl_schedule_band_set_ast_build_options(tree
->band
,
1002 return isl_schedule_tree_free(tree
);
1003 if (isl_schedule_tree_is_anchored(tree
) != was_anchored
)
1004 tree
= isl_schedule_tree_update_anchored(tree
);
1008 isl_schedule_tree_free(tree
);
1009 isl_union_set_free(options
);
1013 /* Return the context of the context tree root.
1015 __isl_give isl_set
*isl_schedule_tree_context_get_context(
1016 __isl_keep isl_schedule_tree
*tree
)
1021 if (tree
->type
!= isl_schedule_node_context
)
1022 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1023 "not a context node", return NULL
);
1025 return isl_set_copy(tree
->context
);
1028 /* Return the domain of the domain tree root.
1030 __isl_give isl_union_set
*isl_schedule_tree_domain_get_domain(
1031 __isl_keep isl_schedule_tree
*tree
)
1036 if (tree
->type
!= isl_schedule_node_domain
)
1037 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1038 "not a domain node", return NULL
);
1040 return isl_union_set_copy(tree
->domain
);
1043 /* Replace the domain of domain tree root "tree" by "domain".
1045 __isl_give isl_schedule_tree
*isl_schedule_tree_domain_set_domain(
1046 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
1048 tree
= isl_schedule_tree_cow(tree
);
1049 if (!tree
|| !domain
)
1052 if (tree
->type
!= isl_schedule_node_domain
)
1053 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1054 "not a domain node", goto error
);
1056 isl_union_set_free(tree
->domain
);
1057 tree
->domain
= domain
;
1061 isl_schedule_tree_free(tree
);
1062 isl_union_set_free(domain
);
1066 /* Return the filter of the filter tree root.
1068 __isl_give isl_union_set
*isl_schedule_tree_filter_get_filter(
1069 __isl_keep isl_schedule_tree
*tree
)
1074 if (tree
->type
!= isl_schedule_node_filter
)
1075 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1076 "not a filter node", return NULL
);
1078 return isl_union_set_copy(tree
->filter
);
1081 /* Replace the filter of the filter tree root by "filter".
1083 __isl_give isl_schedule_tree
*isl_schedule_tree_filter_set_filter(
1084 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
1086 tree
= isl_schedule_tree_cow(tree
);
1087 if (!tree
|| !filter
)
1090 if (tree
->type
!= isl_schedule_node_filter
)
1091 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1092 "not a filter node", return NULL
);
1094 isl_union_set_free(tree
->filter
);
1095 tree
->filter
= filter
;
1099 isl_schedule_tree_free(tree
);
1100 isl_union_set_free(filter
);
1104 /* Set dim to the range dimension of "map" and abort the search.
1106 static int set_range_dim(__isl_take isl_map
*map
, void *user
)
1110 *dim
= isl_map_dim(map
, isl_dim_out
);
1116 /* Return the dimension of the range of "umap".
1117 * "umap" is assumed not to be empty and
1118 * all maps inside "umap" are assumed to have the same range.
1120 * We extract the range dimension from the first map in "umap".
1122 static int range_dim(__isl_keep isl_union_map
*umap
)
1128 if (isl_union_map_n_map(umap
) == 0)
1129 isl_die(isl_union_map_get_ctx(umap
), isl_error_internal
,
1130 "unexpected empty input", return -1);
1132 isl_union_map_foreach_map(umap
, &set_range_dim
, &dim
);
1137 /* Append an "extra" number of zeros to the range of "umap" and
1138 * return the result.
1140 static __isl_give isl_union_map
*append_range(__isl_take isl_union_map
*umap
,
1146 isl_union_pw_multi_aff
*suffix
;
1147 isl_union_map
*universe
;
1148 isl_union_map
*suffix_umap
;
1150 universe
= isl_union_map_universe(isl_union_map_copy(umap
));
1151 dom
= isl_union_map_domain(universe
);
1152 space
= isl_union_set_get_space(dom
);
1153 space
= isl_space_set_from_params(space
);
1154 space
= isl_space_add_dims(space
, isl_dim_set
, extra
);
1155 mv
= isl_multi_val_zero(space
);
1157 suffix
= isl_union_pw_multi_aff_multi_val_on_domain(dom
, mv
);
1158 suffix_umap
= isl_union_map_from_union_pw_multi_aff(suffix
);
1159 umap
= isl_union_map_flat_range_product(umap
, suffix_umap
);
1164 /* Should we skip the root of "tree" while looking for the first
1165 * descendant with schedule information?
1166 * That is, is it impossible to derive any information about
1167 * the iteration domain from this node?
1169 * We do not want to skip leaf or error nodes because there is
1170 * no point in looking any deeper from these nodes.
1172 static int domain_less(__isl_keep isl_schedule_tree
*tree
)
1174 enum isl_schedule_node_type type
;
1176 type
= isl_schedule_tree_get_type(tree
);
1178 case isl_schedule_node_band
:
1179 return isl_schedule_tree_band_n_member(tree
) == 0;
1180 case isl_schedule_node_context
:
1182 case isl_schedule_node_leaf
:
1183 case isl_schedule_node_error
:
1184 case isl_schedule_node_domain
:
1185 case isl_schedule_node_filter
:
1186 case isl_schedule_node_set
:
1187 case isl_schedule_node_sequence
:
1192 /* Move down to the first descendant of "tree" that contains any schedule
1193 * information or return "leaf" if there is no such descendant.
1195 __isl_give isl_schedule_tree
*isl_schedule_tree_first_schedule_descendant(
1196 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_tree
*leaf
)
1198 while (domain_less(tree
)) {
1199 if (!isl_schedule_tree_has_children(tree
)) {
1200 isl_schedule_tree_free(tree
);
1201 return isl_schedule_tree_copy(leaf
);
1203 tree
= isl_schedule_tree_child(tree
, 0);
1209 static __isl_give isl_union_map
*subtree_schedule_extend(
1210 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
);
1212 /* Extend the schedule map "outer" with the subtree schedule
1213 * of the (single) child of "tree", if any.
1215 * If "tree" does not have any descendants (apart from those that
1216 * do not carry any schedule information), then we simply return "outer".
1217 * Otherwise, we extend the schedule map "outer" with the subtree schedule
1218 * of the single child.
1220 static __isl_give isl_union_map
*subtree_schedule_extend_child(
1221 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1223 isl_schedule_tree
*child
;
1227 return isl_union_map_free(outer
);
1228 if (!isl_schedule_tree_has_children(tree
))
1230 child
= isl_schedule_tree_get_child(tree
, 0);
1232 return isl_union_map_free(outer
);
1233 res
= subtree_schedule_extend(child
, outer
);
1234 isl_schedule_tree_free(child
);
1238 /* Extract the parameter space from one of the children of "tree",
1239 * which are assumed to be filters.
1241 static __isl_give isl_space
*extract_space_from_filter_child(
1242 __isl_keep isl_schedule_tree
*tree
)
1246 isl_schedule_tree
*child
;
1248 child
= isl_schedule_tree_list_get_schedule_tree(tree
->children
, 0);
1249 dom
= isl_schedule_tree_filter_get_filter(child
);
1250 space
= isl_union_set_get_space(dom
);
1251 isl_union_set_free(dom
);
1252 isl_schedule_tree_free(child
);
1257 /* Extend the schedule map "outer" with the subtree schedule
1258 * of a set or sequence node.
1260 * The schedule for the set or sequence node itself is composed of
1261 * pieces of the form
1269 * The first form is used if there is only a single child or
1270 * if the current node is a set node and the schedule_separate_components
1271 * option is not set.
1273 * Each of the pieces above is extended with the subtree schedule of
1274 * the child of the corresponding filter, if any, padded with zeros
1275 * to ensure that all pieces have the same range dimension.
1277 static __isl_give isl_union_map
*subtree_schedule_extend_from_children(
1278 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1287 isl_union_map
*umap
;
1292 ctx
= isl_schedule_tree_get_ctx(tree
);
1293 if (!tree
->children
)
1294 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1295 "missing children", return NULL
);
1296 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1298 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1299 "missing children", return NULL
);
1301 separate
= n
> 1 && (tree
->type
== isl_schedule_node_sequence
||
1302 isl_options_get_schedule_separate_components(ctx
));
1304 space
= extract_space_from_filter_child(tree
);
1306 umap
= isl_union_map_empty(isl_space_copy(space
));
1307 space
= isl_space_set_from_params(space
);
1309 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1310 v
= isl_val_zero(ctx
);
1312 mv
= isl_multi_val_zero(space
);
1314 dim
= isl_multi_val_dim(mv
, isl_dim_set
);
1315 for (i
= 0; i
< n
; ++i
) {
1316 isl_union_pw_multi_aff
*upma
;
1317 isl_union_map
*umap_i
;
1319 isl_schedule_tree
*child
;
1323 child
= isl_schedule_tree_list_get_schedule_tree(
1325 dom
= isl_schedule_tree_filter_get_filter(child
);
1328 mv
= isl_multi_val_set_val(mv
, 0, isl_val_copy(v
));
1329 v
= isl_val_add_ui(v
, 1);
1331 upma
= isl_union_pw_multi_aff_multi_val_on_domain(dom
,
1332 isl_multi_val_copy(mv
));
1333 umap_i
= isl_union_map_from_union_pw_multi_aff(upma
);
1334 umap_i
= isl_union_map_flat_range_product(
1335 isl_union_map_copy(outer
), umap_i
);
1336 umap_i
= subtree_schedule_extend_child(child
, umap_i
);
1337 isl_schedule_tree_free(child
);
1339 empty
= isl_union_map_is_empty(umap_i
);
1341 umap_i
= isl_union_map_free(umap_i
);
1343 isl_union_map_free(umap_i
);
1347 dim_i
= range_dim(umap_i
);
1349 umap
= isl_union_map_free(umap
);
1350 } else if (dim
< dim_i
) {
1351 umap
= append_range(umap
, dim_i
- dim
);
1353 } else if (dim_i
< dim
) {
1354 umap_i
= append_range(umap_i
, dim
- dim_i
);
1356 umap
= isl_union_map_union(umap
, umap_i
);
1360 isl_multi_val_free(mv
);
1361 isl_union_map_free(outer
);
1366 /* Extend the schedule map "outer" with the subtree schedule of "tree".
1368 * If the root of the tree is a set or a sequence, then we extend
1369 * the schedule map in subtree_schedule_extend_from_children.
1370 * Otherwise, we extend the schedule map with the partial schedule
1371 * corresponding to the root of the tree and then continue with
1372 * the single child of this root.
1374 static __isl_give isl_union_map
*subtree_schedule_extend(
1375 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1377 isl_multi_union_pw_aff
*mupa
;
1378 isl_union_map
*umap
;
1379 isl_union_set
*domain
;
1384 switch (tree
->type
) {
1385 case isl_schedule_node_error
:
1386 return isl_union_map_free(outer
);
1387 case isl_schedule_node_context
:
1388 return subtree_schedule_extend_child(tree
, outer
);
1389 case isl_schedule_node_band
:
1390 if (isl_schedule_tree_band_n_member(tree
) == 0)
1391 return subtree_schedule_extend_child(tree
, outer
);
1392 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1393 umap
= isl_union_map_from_multi_union_pw_aff(mupa
);
1394 outer
= isl_union_map_flat_range_product(outer
, umap
);
1395 umap
= subtree_schedule_extend_child(tree
, outer
);
1397 case isl_schedule_node_domain
:
1398 domain
= isl_schedule_tree_domain_get_domain(tree
);
1399 umap
= isl_union_map_from_domain(domain
);
1400 outer
= isl_union_map_flat_range_product(outer
, umap
);
1401 umap
= subtree_schedule_extend_child(tree
, outer
);
1403 case isl_schedule_node_filter
:
1404 domain
= isl_schedule_tree_filter_get_filter(tree
);
1405 umap
= isl_union_map_from_domain(domain
);
1406 outer
= isl_union_map_flat_range_product(outer
, umap
);
1407 umap
= subtree_schedule_extend_child(tree
, outer
);
1409 case isl_schedule_node_leaf
:
1410 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1411 "leaf node should be handled by caller", return NULL
);
1412 case isl_schedule_node_set
:
1413 case isl_schedule_node_sequence
:
1414 umap
= subtree_schedule_extend_from_children(tree
, outer
);
1421 static __isl_give isl_union_set
*initial_domain(
1422 __isl_keep isl_schedule_tree
*tree
);
1424 /* Extract a universe domain from the children of the tree root "tree",
1425 * which is a set or sequence, meaning that its children are filters.
1426 * In particular, return the union of the universes of the filters.
1428 static __isl_give isl_union_set
*initial_domain_from_children(
1429 __isl_keep isl_schedule_tree
*tree
)
1433 isl_union_set
*domain
;
1435 if (!tree
->children
)
1436 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1437 "missing children", return NULL
);
1438 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1440 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1441 "missing children", return NULL
);
1443 space
= extract_space_from_filter_child(tree
);
1444 domain
= isl_union_set_empty(space
);
1446 for (i
= 0; i
< n
; ++i
) {
1447 isl_schedule_tree
*child
;
1448 isl_union_set
*domain_i
;
1450 child
= isl_schedule_tree_get_child(tree
, i
);
1451 domain_i
= initial_domain(child
);
1452 domain
= isl_union_set_union(domain
, domain_i
);
1453 isl_schedule_tree_free(child
);
1459 /* Extract a universe domain from the tree root "tree".
1460 * The caller is responsible for making sure that this node
1461 * would not be skipped by isl_schedule_tree_first_schedule_descendant
1462 * and that it is not a leaf node.
1464 static __isl_give isl_union_set
*initial_domain(
1465 __isl_keep isl_schedule_tree
*tree
)
1467 isl_multi_union_pw_aff
*mupa
;
1468 isl_union_set
*domain
;
1473 switch (tree
->type
) {
1474 case isl_schedule_node_error
:
1476 case isl_schedule_node_context
:
1477 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1478 "context node should be handled by caller",
1480 case isl_schedule_node_band
:
1481 if (isl_schedule_tree_band_n_member(tree
) == 0)
1482 isl_die(isl_schedule_tree_get_ctx(tree
),
1484 "0D band should be handled by caller",
1486 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1487 domain
= isl_multi_union_pw_aff_domain(mupa
);
1488 domain
= isl_union_set_universe(domain
);
1490 case isl_schedule_node_domain
:
1491 domain
= isl_schedule_tree_domain_get_domain(tree
);
1492 domain
= isl_union_set_universe(domain
);
1494 case isl_schedule_node_filter
:
1495 domain
= isl_schedule_tree_filter_get_filter(tree
);
1496 domain
= isl_union_set_universe(domain
);
1498 case isl_schedule_node_leaf
:
1499 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1500 "leaf node should be handled by caller", return NULL
);
1501 case isl_schedule_node_set
:
1502 case isl_schedule_node_sequence
:
1503 domain
= initial_domain_from_children(tree
);
1510 /* Return the subtree schedule of a node that contains some schedule
1511 * information, i.e., a node that would not be skipped by
1512 * isl_schedule_tree_first_schedule_descendant and that is not a leaf.
1514 * We start with an initial zero-dimensional subtree schedule based
1515 * on the domain information in the root node and then extend it
1516 * based on the schedule information in the root node and its descendants.
1518 __isl_give isl_union_map
*isl_schedule_tree_get_subtree_schedule_union_map(
1519 __isl_keep isl_schedule_tree
*tree
)
1521 isl_union_set
*domain
;
1522 isl_union_map
*umap
;
1524 domain
= initial_domain(tree
);
1525 umap
= isl_union_map_from_domain(domain
);
1526 return subtree_schedule_extend(tree
, umap
);
1529 /* Multiply the partial schedule of the band root node of "tree"
1530 * with the factors in "mv".
1532 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale(
1533 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
1537 if (tree
->type
!= isl_schedule_node_band
)
1538 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1539 "not a band node", goto error
);
1541 tree
= isl_schedule_tree_cow(tree
);
1545 tree
->band
= isl_schedule_band_scale(tree
->band
, mv
);
1547 return isl_schedule_tree_free(tree
);
1551 isl_schedule_tree_free(tree
);
1552 isl_multi_val_free(mv
);
1556 /* Divide the partial schedule of the band root node of "tree"
1557 * by the factors in "mv".
1559 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale_down(
1560 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
1564 if (tree
->type
!= isl_schedule_node_band
)
1565 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1566 "not a band node", goto error
);
1568 tree
= isl_schedule_tree_cow(tree
);
1572 tree
->band
= isl_schedule_band_scale_down(tree
->band
, mv
);
1574 return isl_schedule_tree_free(tree
);
1578 isl_schedule_tree_free(tree
);
1579 isl_multi_val_free(mv
);
1583 /* Tile the band root node of "tree" with tile sizes "sizes".
1585 * We duplicate the band node, change the schedule of one of them
1586 * to the tile schedule and the other to the point schedule and then
1587 * attach the point band as a child to the tile band.
1589 __isl_give isl_schedule_tree
*isl_schedule_tree_band_tile(
1590 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*sizes
)
1592 isl_schedule_tree
*child
= NULL
;
1594 if (!tree
|| !sizes
)
1596 if (tree
->type
!= isl_schedule_node_band
)
1597 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1598 "not a band node", goto error
);
1600 child
= isl_schedule_tree_copy(tree
);
1601 tree
= isl_schedule_tree_cow(tree
);
1602 child
= isl_schedule_tree_cow(child
);
1603 if (!tree
|| !child
)
1606 tree
->band
= isl_schedule_band_tile(tree
->band
,
1607 isl_multi_val_copy(sizes
));
1610 child
->band
= isl_schedule_band_point(child
->band
, tree
->band
, sizes
);
1612 child
= isl_schedule_tree_free(child
);
1614 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
1618 isl_schedule_tree_free(child
);
1619 isl_schedule_tree_free(tree
);
1620 isl_multi_val_free(sizes
);
1624 /* Split the band root node of "tree" into two nested band nodes,
1625 * one with the first "pos" dimensions and
1626 * one with the remaining dimensions.
1628 __isl_give isl_schedule_tree
*isl_schedule_tree_band_split(
1629 __isl_take isl_schedule_tree
*tree
, int pos
)
1632 isl_schedule_tree
*child
;
1636 if (tree
->type
!= isl_schedule_node_band
)
1637 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1638 "not a band node", return isl_schedule_tree_free(tree
));
1640 n
= isl_schedule_tree_band_n_member(tree
);
1641 if (pos
< 0 || pos
> n
)
1642 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1643 "position out of bounds",
1644 return isl_schedule_tree_free(tree
));
1646 child
= isl_schedule_tree_copy(tree
);
1647 tree
= isl_schedule_tree_cow(tree
);
1648 child
= isl_schedule_tree_cow(child
);
1649 if (!tree
|| !child
)
1652 child
->band
= isl_schedule_band_drop(child
->band
, 0, pos
);
1653 tree
->band
= isl_schedule_band_drop(tree
->band
, pos
, n
- pos
);
1654 if (!child
->band
|| !tree
->band
)
1657 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
1661 isl_schedule_tree_free(child
);
1662 isl_schedule_tree_free(tree
);
1666 /* Attach "tree2" at each of the leaves of "tree1".
1668 * If "tree1" does not have any explicit children, then make "tree2"
1669 * its single child. Otherwise, attach "tree2" to the leaves of
1670 * each of the children of "tree1".
1672 __isl_give isl_schedule_tree
*isl_schedule_tree_append_to_leaves(
1673 __isl_take isl_schedule_tree
*tree1
,
1674 __isl_take isl_schedule_tree
*tree2
)
1678 if (!tree1
|| !tree2
)
1680 n
= isl_schedule_tree_n_children(tree1
);
1682 isl_schedule_tree_list
*list
;
1683 list
= isl_schedule_tree_list_from_schedule_tree(tree2
);
1684 tree1
= isl_schedule_tree_set_children(tree1
, list
);
1687 for (i
= 0; i
< n
; ++i
) {
1688 isl_schedule_tree
*child
;
1690 child
= isl_schedule_tree_get_child(tree1
, i
);
1691 child
= isl_schedule_tree_append_to_leaves(child
,
1692 isl_schedule_tree_copy(tree2
));
1693 tree1
= isl_schedule_tree_replace_child(tree1
, i
, child
);
1696 isl_schedule_tree_free(tree2
);
1699 isl_schedule_tree_free(tree1
);
1700 isl_schedule_tree_free(tree2
);
1704 /* Reset the user pointer on all identifiers of parameters and tuples
1705 * in the root of "tree".
1707 __isl_give isl_schedule_tree
*isl_schedule_tree_reset_user(
1708 __isl_take isl_schedule_tree
*tree
)
1710 if (isl_schedule_tree_is_leaf(tree
))
1713 tree
= isl_schedule_tree_cow(tree
);
1717 switch (tree
->type
) {
1718 case isl_schedule_node_error
:
1719 return isl_schedule_tree_free(tree
);
1720 case isl_schedule_node_band
:
1721 tree
->band
= isl_schedule_band_reset_user(tree
->band
);
1723 return isl_schedule_tree_free(tree
);
1725 case isl_schedule_node_context
:
1726 tree
->context
= isl_set_reset_user(tree
->context
);
1728 return isl_schedule_tree_free(tree
);
1730 case isl_schedule_node_domain
:
1731 tree
->domain
= isl_union_set_reset_user(tree
->domain
);
1733 return isl_schedule_tree_free(tree
);
1735 case isl_schedule_node_filter
:
1736 tree
->filter
= isl_union_set_reset_user(tree
->filter
);
1738 return isl_schedule_tree_free(tree
);
1740 case isl_schedule_node_leaf
:
1741 case isl_schedule_node_sequence
:
1742 case isl_schedule_node_set
:
1749 /* Align the parameters of the root of "tree" to those of "space".
1751 __isl_give isl_schedule_tree
*isl_schedule_tree_align_params(
1752 __isl_take isl_schedule_tree
*tree
, __isl_take isl_space
*space
)
1757 if (isl_schedule_tree_is_leaf(tree
)) {
1758 isl_space_free(space
);
1762 tree
= isl_schedule_tree_cow(tree
);
1766 switch (tree
->type
) {
1767 case isl_schedule_node_error
:
1769 case isl_schedule_node_band
:
1770 tree
->band
= isl_schedule_band_align_params(tree
->band
, space
);
1772 return isl_schedule_tree_free(tree
);
1774 case isl_schedule_node_context
:
1775 tree
->context
= isl_set_align_params(tree
->context
, space
);
1777 return isl_schedule_tree_free(tree
);
1779 case isl_schedule_node_domain
:
1780 tree
->domain
= isl_union_set_align_params(tree
->domain
, space
);
1782 return isl_schedule_tree_free(tree
);
1784 case isl_schedule_node_filter
:
1785 tree
->filter
= isl_union_set_align_params(tree
->filter
, space
);
1787 return isl_schedule_tree_free(tree
);
1789 case isl_schedule_node_leaf
:
1790 case isl_schedule_node_sequence
:
1791 case isl_schedule_node_set
:
1792 isl_space_free(space
);
1798 isl_space_free(space
);
1799 isl_schedule_tree_free(tree
);
1803 /* Does "tree" involve the iteration domain?
1804 * That is, does it need to be modified
1805 * by isl_schedule_tree_pullback_union_pw_multi_aff?
1807 static int involves_iteration_domain(__isl_keep isl_schedule_tree
*tree
)
1812 switch (tree
->type
) {
1813 case isl_schedule_node_error
:
1815 case isl_schedule_node_band
:
1816 case isl_schedule_node_domain
:
1817 case isl_schedule_node_filter
:
1819 case isl_schedule_node_context
:
1820 case isl_schedule_node_leaf
:
1821 case isl_schedule_node_sequence
:
1822 case isl_schedule_node_set
:
1827 /* Compute the pullback of the root node of "tree" by the function
1828 * represented by "upma".
1829 * In other words, plug in "upma" in the iteration domains of
1830 * the root node of "tree".
1832 * We first check if the root node involves any iteration domains.
1833 * If so, we handle the specific cases.
1835 __isl_give isl_schedule_tree
*isl_schedule_tree_pullback_union_pw_multi_aff(
1836 __isl_take isl_schedule_tree
*tree
,
1837 __isl_take isl_union_pw_multi_aff
*upma
)
1844 involves
= involves_iteration_domain(tree
);
1848 isl_union_pw_multi_aff_free(upma
);
1852 tree
= isl_schedule_tree_cow(tree
);
1856 if (tree
->type
== isl_schedule_node_band
) {
1857 tree
->band
= isl_schedule_band_pullback_union_pw_multi_aff(
1860 return isl_schedule_tree_free(tree
);
1861 } else if (tree
->type
== isl_schedule_node_domain
) {
1863 isl_union_set_preimage_union_pw_multi_aff(tree
->domain
,
1866 return isl_schedule_tree_free(tree
);
1867 } else if (tree
->type
== isl_schedule_node_filter
) {
1869 isl_union_set_preimage_union_pw_multi_aff(tree
->filter
,
1872 return isl_schedule_tree_free(tree
);
1877 isl_union_pw_multi_aff_free(upma
);
1878 isl_schedule_tree_free(tree
);
1882 /* Compute the gist of the band tree root with respect to "context".
1884 __isl_give isl_schedule_tree
*isl_schedule_tree_band_gist(
1885 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*context
)
1889 if (tree
->type
!= isl_schedule_node_band
)
1890 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1891 "not a band node", goto error
);
1892 tree
= isl_schedule_tree_cow(tree
);
1896 tree
->band
= isl_schedule_band_gist(tree
->band
, context
);
1898 return isl_schedule_tree_free(tree
);
1901 isl_union_set_free(context
);
1902 isl_schedule_tree_free(tree
);
1906 /* Are any members in "band" marked coincident?
1908 static int any_coincident(__isl_keep isl_schedule_band
*band
)
1912 n
= isl_schedule_band_n_member(band
);
1913 for (i
= 0; i
< n
; ++i
)
1914 if (isl_schedule_band_member_get_coincident(band
, i
))
1920 /* Print the band node "band" to "p".
1922 * The permutable and coincident properties are only printed if they
1923 * are different from the defaults.
1924 * The coincident property is always printed in YAML flow style.
1926 static __isl_give isl_printer
*print_tree_band(__isl_take isl_printer
*p
,
1927 __isl_keep isl_schedule_band
*band
)
1929 isl_union_set
*options
;
1932 p
= isl_printer_print_str(p
, "schedule");
1933 p
= isl_printer_yaml_next(p
);
1934 p
= isl_printer_print_str(p
, "\"");
1935 p
= isl_printer_print_multi_union_pw_aff(p
, band
->mupa
);
1936 p
= isl_printer_print_str(p
, "\"");
1937 if (isl_schedule_band_get_permutable(band
)) {
1938 p
= isl_printer_yaml_next(p
);
1939 p
= isl_printer_print_str(p
, "permutable");
1940 p
= isl_printer_yaml_next(p
);
1941 p
= isl_printer_print_int(p
, 1);
1943 if (any_coincident(band
)) {
1947 p
= isl_printer_yaml_next(p
);
1948 p
= isl_printer_print_str(p
, "coincident");
1949 p
= isl_printer_yaml_next(p
);
1950 style
= isl_printer_get_yaml_style(p
);
1951 p
= isl_printer_set_yaml_style(p
, ISL_YAML_STYLE_FLOW
);
1952 p
= isl_printer_yaml_start_sequence(p
);
1953 n
= isl_schedule_band_n_member(band
);
1954 for (i
= 0; i
< n
; ++i
) {
1955 p
= isl_printer_print_int(p
,
1956 isl_schedule_band_member_get_coincident(band
, i
));
1957 p
= isl_printer_yaml_next(p
);
1959 p
= isl_printer_yaml_end_sequence(p
);
1960 p
= isl_printer_set_yaml_style(p
, style
);
1962 options
= isl_schedule_band_get_ast_build_options(band
);
1963 empty
= isl_union_set_is_empty(options
);
1965 p
= isl_printer_free(p
);
1967 p
= isl_printer_yaml_next(p
);
1968 p
= isl_printer_print_str(p
, "options");
1969 p
= isl_printer_yaml_next(p
);
1970 p
= isl_printer_print_str(p
, "\"");
1971 p
= isl_printer_print_union_set(p
, options
);
1972 p
= isl_printer_print_str(p
, "\"");
1974 isl_union_set_free(options
);
1979 /* Print "tree" to "p".
1981 * If "n_ancestor" is non-negative, then "child_pos" contains the child
1982 * positions of a descendant of the current node that should be marked
1983 * (by the comment "YOU ARE HERE"). In particular, if "n_ancestor"
1984 * is zero, then the current node should be marked.
1985 * The marking is only printed in YAML block format.
1987 * Implicit leaf nodes are not printed, except if they correspond
1988 * to the node that should be marked.
1990 __isl_give isl_printer
*isl_printer_print_schedule_tree_mark(
1991 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
,
1992 int n_ancestor
, int *child_pos
)
1998 block
= isl_printer_get_yaml_style(p
) == ISL_YAML_STYLE_BLOCK
;
2000 p
= isl_printer_yaml_start_mapping(p
);
2001 if (n_ancestor
== 0 && block
) {
2002 p
= isl_printer_print_str(p
, "# YOU ARE HERE");
2003 p
= isl_printer_end_line(p
);
2004 p
= isl_printer_start_line(p
);
2006 switch (tree
->type
) {
2007 case isl_schedule_node_error
:
2008 p
= isl_printer_print_str(p
, "ERROR");
2010 case isl_schedule_node_leaf
:
2011 p
= isl_printer_print_str(p
, "leaf");
2013 case isl_schedule_node_sequence
:
2014 p
= isl_printer_print_str(p
, "sequence");
2017 case isl_schedule_node_set
:
2018 p
= isl_printer_print_str(p
, "set");
2021 case isl_schedule_node_context
:
2022 p
= isl_printer_print_str(p
, "context");
2023 p
= isl_printer_yaml_next(p
);
2024 p
= isl_printer_print_str(p
, "\"");
2025 p
= isl_printer_print_set(p
, tree
->context
);
2026 p
= isl_printer_print_str(p
, "\"");
2028 case isl_schedule_node_domain
:
2029 p
= isl_printer_print_str(p
, "domain");
2030 p
= isl_printer_yaml_next(p
);
2031 p
= isl_printer_print_str(p
, "\"");
2032 p
= isl_printer_print_union_set(p
, tree
->domain
);
2033 p
= isl_printer_print_str(p
, "\"");
2035 case isl_schedule_node_filter
:
2036 p
= isl_printer_print_str(p
, "filter");
2037 p
= isl_printer_yaml_next(p
);
2038 p
= isl_printer_print_str(p
, "\"");
2039 p
= isl_printer_print_union_set(p
, tree
->filter
);
2040 p
= isl_printer_print_str(p
, "\"");
2042 case isl_schedule_node_band
:
2043 p
= print_tree_band(p
, tree
->band
);
2046 p
= isl_printer_yaml_next(p
);
2048 if (!tree
->children
) {
2049 if (n_ancestor
> 0 && block
) {
2050 isl_schedule_tree
*leaf
;
2052 p
= isl_printer_print_str(p
, "child");
2053 p
= isl_printer_yaml_next(p
);
2054 leaf
= isl_schedule_tree_leaf(isl_printer_get_ctx(p
));
2055 p
= isl_printer_print_schedule_tree_mark(p
,
2057 isl_schedule_tree_free(leaf
);
2058 p
= isl_printer_yaml_next(p
);
2060 return isl_printer_yaml_end_mapping(p
);
2064 p
= isl_printer_yaml_start_sequence(p
);
2066 p
= isl_printer_print_str(p
, "child");
2067 p
= isl_printer_yaml_next(p
);
2070 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
2071 for (i
= 0; i
< n
; ++i
) {
2072 isl_schedule_tree
*t
;
2074 t
= isl_schedule_tree_get_child(tree
, i
);
2075 if (n_ancestor
> 0 && child_pos
[0] == i
)
2076 p
= isl_printer_print_schedule_tree_mark(p
, t
,
2077 n_ancestor
- 1, child_pos
+ 1);
2079 p
= isl_printer_print_schedule_tree_mark(p
, t
,
2081 isl_schedule_tree_free(t
);
2083 p
= isl_printer_yaml_next(p
);
2087 p
= isl_printer_yaml_end_sequence(p
);
2088 p
= isl_printer_yaml_end_mapping(p
);
2093 /* Print "tree" to "p".
2095 __isl_give isl_printer
*isl_printer_print_schedule_tree(
2096 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
)
2098 return isl_printer_print_schedule_tree_mark(p
, tree
, -1, NULL
);
2101 void isl_schedule_tree_dump(__isl_keep isl_schedule_tree
*tree
)
2104 isl_printer
*printer
;
2109 ctx
= isl_schedule_tree_get_ctx(tree
);
2110 printer
= isl_printer_to_file(ctx
, stderr
);
2111 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
2112 printer
= isl_printer_print_schedule_tree(printer
, tree
);
2114 isl_printer_free(printer
);