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_extension
:
106 dup
->extension
= isl_union_map_copy(tree
->extension
);
108 return isl_schedule_tree_free(dup
);
110 case isl_schedule_node_filter
:
111 dup
->filter
= isl_union_set_copy(tree
->filter
);
113 return isl_schedule_tree_free(dup
);
115 case isl_schedule_node_guard
:
116 dup
->guard
= isl_set_copy(tree
->guard
);
118 return isl_schedule_tree_free(dup
);
120 case isl_schedule_node_mark
:
121 dup
->mark
= isl_id_copy(tree
->mark
);
123 return isl_schedule_tree_free(dup
);
125 case isl_schedule_node_leaf
:
126 case isl_schedule_node_sequence
:
127 case isl_schedule_node_set
:
131 if (tree
->children
) {
132 dup
->children
= isl_schedule_tree_list_copy(tree
->children
);
134 return isl_schedule_tree_free(dup
);
136 dup
->anchored
= tree
->anchored
;
141 /* Return an isl_schedule_tree that is equal to "tree" and that has only
142 * a single reference.
144 __isl_give isl_schedule_tree
*isl_schedule_tree_cow(
145 __isl_take isl_schedule_tree
*tree
)
153 return isl_schedule_tree_dup(tree
);
156 /* Return a new reference to "tree".
158 __isl_give isl_schedule_tree
*isl_schedule_tree_copy(
159 __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
)
178 switch (tree
->type
) {
179 case isl_schedule_node_band
:
180 isl_schedule_band_free(tree
->band
);
182 case isl_schedule_node_context
:
183 isl_set_free(tree
->context
);
185 case isl_schedule_node_domain
:
186 isl_union_set_free(tree
->domain
);
188 case isl_schedule_node_expansion
:
189 isl_union_pw_multi_aff_free(tree
->contraction
);
190 isl_union_map_free(tree
->expansion
);
192 case isl_schedule_node_extension
:
193 isl_union_map_free(tree
->extension
);
195 case isl_schedule_node_filter
:
196 isl_union_set_free(tree
->filter
);
198 case isl_schedule_node_guard
:
199 isl_set_free(tree
->guard
);
201 case isl_schedule_node_mark
:
202 isl_id_free(tree
->mark
);
204 case isl_schedule_node_sequence
:
205 case isl_schedule_node_set
:
206 case isl_schedule_node_error
:
207 case isl_schedule_node_leaf
:
210 isl_schedule_tree_list_free(tree
->children
);
211 isl_ctx_deref(tree
->ctx
);
217 /* Create and return a new leaf schedule tree.
219 __isl_give isl_schedule_tree
*isl_schedule_tree_leaf(isl_ctx
*ctx
)
221 return isl_schedule_tree_alloc(ctx
, isl_schedule_node_leaf
);
224 /* Create a new band schedule tree referring to "band"
227 __isl_give isl_schedule_tree
*isl_schedule_tree_from_band(
228 __isl_take isl_schedule_band
*band
)
231 isl_schedule_tree
*tree
;
236 ctx
= isl_schedule_band_get_ctx(band
);
237 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_band
);
242 tree
->anchored
= isl_schedule_band_is_anchored(band
);
246 isl_schedule_band_free(band
);
250 /* Create a new context schedule tree with the given context and no children.
251 * Since the context references the outer schedule dimension,
252 * the tree is anchored.
254 __isl_give isl_schedule_tree
*isl_schedule_tree_from_context(
255 __isl_take isl_set
*context
)
258 isl_schedule_tree
*tree
;
263 ctx
= isl_set_get_ctx(context
);
264 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_context
);
268 tree
->context
= context
;
273 isl_set_free(context
);
277 /* Create a new domain schedule tree with the given domain and no children.
279 __isl_give isl_schedule_tree
*isl_schedule_tree_from_domain(
280 __isl_take isl_union_set
*domain
)
283 isl_schedule_tree
*tree
;
288 ctx
= isl_union_set_get_ctx(domain
);
289 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_domain
);
293 tree
->domain
= domain
;
297 isl_union_set_free(domain
);
301 /* Create a new expansion schedule tree with the given contraction and
302 * expansion and no children.
304 __isl_give isl_schedule_tree
*isl_schedule_tree_from_expansion(
305 __isl_take isl_union_pw_multi_aff
*contraction
,
306 __isl_take isl_union_map
*expansion
)
309 isl_schedule_tree
*tree
;
311 if (!contraction
|| !expansion
)
314 ctx
= isl_union_map_get_ctx(expansion
);
315 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_expansion
);
319 tree
->contraction
= contraction
;
320 tree
->expansion
= expansion
;
324 isl_union_pw_multi_aff_free(contraction
);
325 isl_union_map_free(expansion
);
329 /* Create a new extension schedule tree with the given extension and
331 * Since the domain of the extension refers to the outer schedule dimension,
332 * the tree is anchored.
334 __isl_give isl_schedule_tree
*isl_schedule_tree_from_extension(
335 __isl_take isl_union_map
*extension
)
338 isl_schedule_tree
*tree
;
343 ctx
= isl_union_map_get_ctx(extension
);
344 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_extension
);
348 tree
->extension
= extension
;
353 isl_union_map_free(extension
);
357 /* Create a new filter schedule tree with the given filter and no children.
359 __isl_give isl_schedule_tree
*isl_schedule_tree_from_filter(
360 __isl_take isl_union_set
*filter
)
363 isl_schedule_tree
*tree
;
368 ctx
= isl_union_set_get_ctx(filter
);
369 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_filter
);
373 tree
->filter
= filter
;
377 isl_union_set_free(filter
);
381 /* Create a new guard schedule tree with the given guard and no children.
382 * Since the guard references the outer schedule dimension,
383 * the tree is anchored.
385 __isl_give isl_schedule_tree
*isl_schedule_tree_from_guard(
386 __isl_take isl_set
*guard
)
389 isl_schedule_tree
*tree
;
394 ctx
= isl_set_get_ctx(guard
);
395 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_guard
);
408 /* Create a new mark schedule tree with the given mark identifier and
411 __isl_give isl_schedule_tree
*isl_schedule_tree_from_mark(
412 __isl_take isl_id
*mark
)
415 isl_schedule_tree
*tree
;
420 ctx
= isl_id_get_ctx(mark
);
421 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_mark
);
433 /* Does "tree" have any node that depends on its position
434 * in the complete schedule tree?
436 isl_bool
isl_schedule_tree_is_subtree_anchored(
437 __isl_keep isl_schedule_tree
*tree
)
439 return tree
? tree
->anchored
: isl_bool_error
;
442 /* Does the root node of "tree" depend on its position in the complete
444 * Band nodes may be anchored depending on the associated AST build options.
445 * Context, extension and guard nodes are always anchored.
447 int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree
*tree
)
452 switch (isl_schedule_tree_get_type(tree
)) {
453 case isl_schedule_node_error
:
455 case isl_schedule_node_band
:
456 return isl_schedule_band_is_anchored(tree
->band
);
457 case isl_schedule_node_context
:
458 case isl_schedule_node_extension
:
459 case isl_schedule_node_guard
:
461 case isl_schedule_node_domain
:
462 case isl_schedule_node_expansion
:
463 case isl_schedule_node_filter
:
464 case isl_schedule_node_leaf
:
465 case isl_schedule_node_mark
:
466 case isl_schedule_node_sequence
:
467 case isl_schedule_node_set
:
471 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
472 "unhandled case", return -1);
475 /* Update the anchored field of "tree" based on whether the root node
476 * itself in anchored and the anchored fields of the children.
478 * This function should be called whenever the children of a tree node
479 * are changed or the anchoredness of the tree root itself changes.
481 __isl_give isl_schedule_tree
*isl_schedule_tree_update_anchored(
482 __isl_take isl_schedule_tree
*tree
)
490 anchored
= isl_schedule_tree_is_anchored(tree
);
492 return isl_schedule_tree_free(tree
);
494 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
495 for (i
= 0; !anchored
&& i
< n
; ++i
) {
496 isl_schedule_tree
*child
;
498 child
= isl_schedule_tree_get_child(tree
, i
);
500 return isl_schedule_tree_free(tree
);
501 anchored
= child
->anchored
;
502 isl_schedule_tree_free(child
);
505 if (anchored
== tree
->anchored
)
507 tree
= isl_schedule_tree_cow(tree
);
510 tree
->anchored
= anchored
;
514 /* Create a new tree of the given type (isl_schedule_node_sequence or
515 * isl_schedule_node_set) with the given children.
517 __isl_give isl_schedule_tree
*isl_schedule_tree_from_children(
518 enum isl_schedule_node_type type
,
519 __isl_take isl_schedule_tree_list
*list
)
522 isl_schedule_tree
*tree
;
527 ctx
= isl_schedule_tree_list_get_ctx(list
);
528 tree
= isl_schedule_tree_alloc(ctx
, type
);
532 tree
->children
= list
;
533 tree
= isl_schedule_tree_update_anchored(tree
);
537 isl_schedule_tree_list_free(list
);
541 /* Construct a tree with a root node of type "type" and as children
542 * "tree1" and "tree2".
543 * If the root of one (or both) of the input trees is itself of type "type",
544 * then the tree is replaced by its children.
546 __isl_give isl_schedule_tree
*isl_schedule_tree_from_pair(
547 enum isl_schedule_node_type type
, __isl_take isl_schedule_tree
*tree1
,
548 __isl_take isl_schedule_tree
*tree2
)
551 isl_schedule_tree_list
*list
;
553 if (!tree1
|| !tree2
)
556 ctx
= isl_schedule_tree_get_ctx(tree1
);
557 if (isl_schedule_tree_get_type(tree1
) == type
) {
558 list
= isl_schedule_tree_list_copy(tree1
->children
);
559 isl_schedule_tree_free(tree1
);
561 list
= isl_schedule_tree_list_alloc(ctx
, 2);
562 list
= isl_schedule_tree_list_add(list
, tree1
);
564 if (isl_schedule_tree_get_type(tree2
) == type
) {
565 isl_schedule_tree_list
*children
;
567 children
= isl_schedule_tree_list_copy(tree2
->children
);
568 list
= isl_schedule_tree_list_concat(list
, children
);
569 isl_schedule_tree_free(tree2
);
571 list
= isl_schedule_tree_list_add(list
, tree2
);
574 return isl_schedule_tree_from_children(type
, list
);
576 isl_schedule_tree_free(tree1
);
577 isl_schedule_tree_free(tree2
);
581 /* Construct a tree with a sequence root node and as children
582 * "tree1" and "tree2".
583 * If the root of one (or both) of the input trees is itself a sequence,
584 * then the tree is replaced by its children.
586 __isl_give isl_schedule_tree
*isl_schedule_tree_sequence_pair(
587 __isl_take isl_schedule_tree
*tree1
,
588 __isl_take isl_schedule_tree
*tree2
)
590 return isl_schedule_tree_from_pair(isl_schedule_node_sequence
,
594 /* Construct a tree with a set root node and as children
595 * "tree1" and "tree2".
596 * If the root of one (or both) of the input trees is itself a set,
597 * then the tree is replaced by its children.
599 __isl_give isl_schedule_tree
*isl_schedule_tree_set_pair(
600 __isl_take isl_schedule_tree
*tree1
,
601 __isl_take isl_schedule_tree
*tree2
)
603 return isl_schedule_tree_from_pair(isl_schedule_node_set
, tree1
, tree2
);
606 /* Return the isl_ctx to which "tree" belongs.
608 isl_ctx
*isl_schedule_tree_get_ctx(__isl_keep isl_schedule_tree
*tree
)
610 return tree
? tree
->ctx
: NULL
;
613 /* Return the type of the root of the tree or isl_schedule_node_error
616 enum isl_schedule_node_type
isl_schedule_tree_get_type(
617 __isl_keep isl_schedule_tree
*tree
)
619 return tree
? tree
->type
: isl_schedule_node_error
;
622 /* Are "tree1" and "tree2" obviously equal to each other?
624 isl_bool
isl_schedule_tree_plain_is_equal(__isl_keep isl_schedule_tree
*tree1
,
625 __isl_keep isl_schedule_tree
*tree2
)
630 if (!tree1
|| !tree2
)
631 return isl_bool_error
;
633 return isl_bool_true
;
634 if (tree1
->type
!= tree2
->type
)
635 return isl_bool_false
;
637 switch (tree1
->type
) {
638 case isl_schedule_node_band
:
639 equal
= isl_schedule_band_plain_is_equal(tree1
->band
,
642 case isl_schedule_node_context
:
643 equal
= isl_set_is_equal(tree1
->context
, tree2
->context
);
645 case isl_schedule_node_domain
:
646 equal
= isl_union_set_is_equal(tree1
->domain
, tree2
->domain
);
648 case isl_schedule_node_expansion
:
649 equal
= isl_union_map_is_equal(tree1
->expansion
,
651 if (equal
>= 0 && equal
)
652 equal
= isl_union_pw_multi_aff_plain_is_equal(
653 tree1
->contraction
, tree2
->contraction
);
655 case isl_schedule_node_extension
:
656 equal
= isl_union_map_is_equal(tree1
->extension
,
659 case isl_schedule_node_filter
:
660 equal
= isl_union_set_is_equal(tree1
->filter
, tree2
->filter
);
662 case isl_schedule_node_guard
:
663 equal
= isl_set_is_equal(tree1
->guard
, tree2
->guard
);
665 case isl_schedule_node_mark
:
666 equal
= tree1
->mark
== tree2
->mark
;
668 case isl_schedule_node_leaf
:
669 case isl_schedule_node_sequence
:
670 case isl_schedule_node_set
:
671 equal
= isl_bool_true
;
673 case isl_schedule_node_error
:
674 equal
= isl_bool_error
;
678 if (equal
< 0 || !equal
)
681 n
= isl_schedule_tree_n_children(tree1
);
682 if (n
!= isl_schedule_tree_n_children(tree2
))
683 return isl_bool_false
;
684 for (i
= 0; i
< n
; ++i
) {
685 isl_schedule_tree
*child1
, *child2
;
687 child1
= isl_schedule_tree_get_child(tree1
, i
);
688 child2
= isl_schedule_tree_get_child(tree2
, i
);
689 equal
= isl_schedule_tree_plain_is_equal(child1
, child2
);
690 isl_schedule_tree_free(child1
);
691 isl_schedule_tree_free(child2
);
693 if (equal
< 0 || !equal
)
697 return isl_bool_true
;
700 /* Does "tree" have any children, other than an implicit leaf.
702 int isl_schedule_tree_has_children(__isl_keep isl_schedule_tree
*tree
)
707 return tree
->children
!= NULL
;
710 /* Return the number of children of "tree", excluding implicit leaves.
712 int isl_schedule_tree_n_children(__isl_keep isl_schedule_tree
*tree
)
717 return isl_schedule_tree_list_n_schedule_tree(tree
->children
);
720 /* Return a copy of the (explicit) child at position "pos" of "tree".
722 __isl_give isl_schedule_tree
*isl_schedule_tree_get_child(
723 __isl_keep isl_schedule_tree
*tree
, int pos
)
728 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
729 "schedule tree has no explicit children", return NULL
);
730 return isl_schedule_tree_list_get_schedule_tree(tree
->children
, pos
);
733 /* Return a copy of the (explicit) child at position "pos" of "tree" and
736 __isl_give isl_schedule_tree
*isl_schedule_tree_child(
737 __isl_take isl_schedule_tree
*tree
, int pos
)
739 isl_schedule_tree
*child
;
741 child
= isl_schedule_tree_get_child(tree
, pos
);
742 isl_schedule_tree_free(tree
);
746 /* Remove all (explicit) children from "tree".
748 __isl_give isl_schedule_tree
*isl_schedule_tree_reset_children(
749 __isl_take isl_schedule_tree
*tree
)
751 tree
= isl_schedule_tree_cow(tree
);
754 tree
->children
= isl_schedule_tree_list_free(tree
->children
);
758 /* Remove the child at position "pos" from the children of "tree".
759 * If there was only one child to begin with, then remove all children.
761 __isl_give isl_schedule_tree
*isl_schedule_tree_drop_child(
762 __isl_take isl_schedule_tree
*tree
, int pos
)
766 tree
= isl_schedule_tree_cow(tree
);
770 if (!isl_schedule_tree_has_children(tree
))
771 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
772 "tree does not have any explicit children",
773 return isl_schedule_tree_free(tree
));
774 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
775 if (pos
< 0 || pos
>= n
)
776 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
777 "position out of bounds",
778 return isl_schedule_tree_free(tree
));
780 return isl_schedule_tree_reset_children(tree
);
782 tree
->children
= isl_schedule_tree_list_drop(tree
->children
, pos
, 1);
784 return isl_schedule_tree_free(tree
);
789 /* Replace the child at position "pos" of "tree" by "child".
791 * If the new child is a leaf, then it is not explicitly
792 * recorded in the list of children. Instead, the list of children
793 * (which is assumed to have only one element) is removed.
794 * Note that the children of set and sequence nodes are always
795 * filters, so they cannot be replaced by empty trees.
797 __isl_give isl_schedule_tree
*isl_schedule_tree_replace_child(
798 __isl_take isl_schedule_tree
*tree
, int pos
,
799 __isl_take isl_schedule_tree
*child
)
801 tree
= isl_schedule_tree_cow(tree
);
805 if (isl_schedule_tree_is_leaf(child
)) {
806 isl_schedule_tree_free(child
);
807 if (!tree
->children
&& pos
== 0)
809 if (isl_schedule_tree_n_children(tree
) != 1)
810 isl_die(isl_schedule_tree_get_ctx(tree
),
812 "can only replace single child by leaf",
814 return isl_schedule_tree_reset_children(tree
);
817 if (!tree
->children
&& pos
== 0)
819 isl_schedule_tree_list_from_schedule_tree(child
);
821 tree
->children
= isl_schedule_tree_list_set_schedule_tree(
822 tree
->children
, pos
, child
);
825 return isl_schedule_tree_free(tree
);
826 tree
= isl_schedule_tree_update_anchored(tree
);
830 isl_schedule_tree_free(tree
);
831 isl_schedule_tree_free(child
);
835 /* Replace the (explicit) children of "tree" by "children"?
837 __isl_give isl_schedule_tree
*isl_schedule_tree_set_children(
838 __isl_take isl_schedule_tree
*tree
,
839 __isl_take isl_schedule_tree_list
*children
)
841 tree
= isl_schedule_tree_cow(tree
);
842 if (!tree
|| !children
)
844 isl_schedule_tree_list_free(tree
->children
);
845 tree
->children
= children
;
848 isl_schedule_tree_free(tree
);
849 isl_schedule_tree_list_free(children
);
853 /* Create a new band schedule tree referring to "band"
854 * with "tree" as single child.
856 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_band(
857 __isl_take isl_schedule_tree
*tree
, __isl_take isl_schedule_band
*band
)
859 isl_schedule_tree
*res
;
861 res
= isl_schedule_tree_from_band(band
);
862 return isl_schedule_tree_replace_child(res
, 0, tree
);
865 /* Create a new context schedule tree with the given context and
866 * with "tree" as single child.
868 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_context(
869 __isl_take isl_schedule_tree
*tree
, __isl_take isl_set
*context
)
871 isl_schedule_tree
*res
;
873 res
= isl_schedule_tree_from_context(context
);
874 return isl_schedule_tree_replace_child(res
, 0, tree
);
877 /* Create a new domain schedule tree with the given domain and
878 * with "tree" as single child.
880 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_domain(
881 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
883 isl_schedule_tree
*res
;
885 res
= isl_schedule_tree_from_domain(domain
);
886 return isl_schedule_tree_replace_child(res
, 0, tree
);
889 /* Create a new expansion schedule tree with the given contraction and
890 * expansion and with "tree" as single child.
892 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_expansion(
893 __isl_take isl_schedule_tree
*tree
,
894 __isl_take isl_union_pw_multi_aff
*contraction
,
895 __isl_take isl_union_map
*expansion
)
897 isl_schedule_tree
*res
;
899 res
= isl_schedule_tree_from_expansion(contraction
, expansion
);
900 return isl_schedule_tree_replace_child(res
, 0, tree
);
903 /* Create a new extension schedule tree with the given extension and
904 * with "tree" as single child.
906 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_extension(
907 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_map
*extension
)
909 isl_schedule_tree
*res
;
911 res
= isl_schedule_tree_from_extension(extension
);
912 return isl_schedule_tree_replace_child(res
, 0, tree
);
915 /* Create a new filter schedule tree with the given filter and single child.
917 * If the root of "tree" is itself a filter node, then the two
918 * filter nodes are merged into one node.
920 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_filter(
921 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
923 isl_schedule_tree
*res
;
925 if (isl_schedule_tree_get_type(tree
) == isl_schedule_node_filter
) {
926 isl_union_set
*tree_filter
;
928 tree_filter
= isl_schedule_tree_filter_get_filter(tree
);
929 tree_filter
= isl_union_set_intersect(tree_filter
, filter
);
930 tree
= isl_schedule_tree_filter_set_filter(tree
, tree_filter
);
934 res
= isl_schedule_tree_from_filter(filter
);
935 return isl_schedule_tree_replace_child(res
, 0, tree
);
938 /* Insert a filter node with filter set "filter"
939 * in each of the children of "tree".
941 __isl_give isl_schedule_tree
*isl_schedule_tree_children_insert_filter(
942 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
946 if (!tree
|| !filter
)
949 n
= isl_schedule_tree_n_children(tree
);
950 for (i
= 0; i
< n
; ++i
) {
951 isl_schedule_tree
*child
;
953 child
= isl_schedule_tree_get_child(tree
, i
);
954 child
= isl_schedule_tree_insert_filter(child
,
955 isl_union_set_copy(filter
));
956 tree
= isl_schedule_tree_replace_child(tree
, i
, child
);
959 isl_union_set_free(filter
);
962 isl_union_set_free(filter
);
963 isl_schedule_tree_free(tree
);
967 /* Create a new guard schedule tree with the given guard and
968 * with "tree" as single child.
970 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_guard(
971 __isl_take isl_schedule_tree
*tree
, __isl_take isl_set
*guard
)
973 isl_schedule_tree
*res
;
975 res
= isl_schedule_tree_from_guard(guard
);
976 return isl_schedule_tree_replace_child(res
, 0, tree
);
979 /* Create a new mark schedule tree with the given mark identifier and
982 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_mark(
983 __isl_take isl_schedule_tree
*tree
, __isl_take isl_id
*mark
)
985 isl_schedule_tree
*res
;
987 res
= isl_schedule_tree_from_mark(mark
);
988 return isl_schedule_tree_replace_child(res
, 0, tree
);
991 /* Return the number of members in the band tree root.
993 unsigned isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree
*tree
)
998 if (tree
->type
!= isl_schedule_node_band
)
999 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1000 "not a band node", return 0);
1002 return isl_schedule_band_n_member(tree
->band
);
1005 /* Is the band member at position "pos" of the band tree root
1006 * marked coincident?
1008 isl_bool
isl_schedule_tree_band_member_get_coincident(
1009 __isl_keep isl_schedule_tree
*tree
, int pos
)
1012 return isl_bool_error
;
1014 if (tree
->type
!= isl_schedule_node_band
)
1015 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1016 "not a band node", return isl_bool_error
);
1018 return isl_schedule_band_member_get_coincident(tree
->band
, pos
);
1021 /* Mark the given band member as being coincident or not
1022 * according to "coincident".
1024 __isl_give isl_schedule_tree
*isl_schedule_tree_band_member_set_coincident(
1025 __isl_take isl_schedule_tree
*tree
, int pos
, int coincident
)
1029 if (tree
->type
!= isl_schedule_node_band
)
1030 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1031 "not a band node", return isl_schedule_tree_free(tree
));
1032 if (isl_schedule_tree_band_member_get_coincident(tree
, pos
) ==
1035 tree
= isl_schedule_tree_cow(tree
);
1039 tree
->band
= isl_schedule_band_member_set_coincident(tree
->band
, pos
,
1042 return isl_schedule_tree_free(tree
);
1046 /* Is the band tree root marked permutable?
1048 isl_bool
isl_schedule_tree_band_get_permutable(
1049 __isl_keep isl_schedule_tree
*tree
)
1052 return isl_bool_error
;
1054 if (tree
->type
!= isl_schedule_node_band
)
1055 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1056 "not a band node", return isl_bool_error
);
1058 return isl_schedule_band_get_permutable(tree
->band
);
1061 /* Mark the band tree root permutable or not according to "permutable"?
1063 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_permutable(
1064 __isl_take isl_schedule_tree
*tree
, int permutable
)
1068 if (tree
->type
!= isl_schedule_node_band
)
1069 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1070 "not a band node", return isl_schedule_tree_free(tree
));
1071 if (isl_schedule_tree_band_get_permutable(tree
) == permutable
)
1073 tree
= isl_schedule_tree_cow(tree
);
1077 tree
->band
= isl_schedule_band_set_permutable(tree
->band
, permutable
);
1079 return isl_schedule_tree_free(tree
);
1083 /* Return the schedule space of the band tree root.
1085 __isl_give isl_space
*isl_schedule_tree_band_get_space(
1086 __isl_keep isl_schedule_tree
*tree
)
1091 if (tree
->type
!= isl_schedule_node_band
)
1092 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1093 "not a band node", return NULL
);
1095 return isl_schedule_band_get_space(tree
->band
);
1098 /* Intersect the domain of the band schedule of the band tree root
1101 __isl_give isl_schedule_tree
*isl_schedule_tree_band_intersect_domain(
1102 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
1104 if (!tree
|| !domain
)
1107 if (tree
->type
!= isl_schedule_node_band
)
1108 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1109 "not a band node", goto error
);
1111 tree
->band
= isl_schedule_band_intersect_domain(tree
->band
, domain
);
1113 return isl_schedule_tree_free(tree
);
1117 isl_schedule_tree_free(tree
);
1118 isl_union_set_free(domain
);
1122 /* Return the schedule of the band tree root in isolation.
1124 __isl_give isl_multi_union_pw_aff
*isl_schedule_tree_band_get_partial_schedule(
1125 __isl_keep isl_schedule_tree
*tree
)
1130 if (tree
->type
!= isl_schedule_node_band
)
1131 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1132 "not a band node", return NULL
);
1134 return isl_schedule_band_get_partial_schedule(tree
->band
);
1137 /* Replace the schedule of the band tree root by "schedule".
1139 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_partial_schedule(
1140 __isl_take isl_schedule_tree
*tree
,
1141 __isl_take isl_multi_union_pw_aff
*schedule
)
1143 tree
= isl_schedule_tree_cow(tree
);
1144 if (!tree
|| !schedule
)
1147 if (tree
->type
!= isl_schedule_node_band
)
1148 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1149 "not a band node", return NULL
);
1150 tree
->band
= isl_schedule_band_set_partial_schedule(tree
->band
,
1155 isl_schedule_tree_free(tree
);
1156 isl_multi_union_pw_aff_free(schedule
);
1160 /* Return the loop AST generation type for the band member
1161 * of the band tree root at position "pos".
1163 enum isl_ast_loop_type
isl_schedule_tree_band_member_get_ast_loop_type(
1164 __isl_keep isl_schedule_tree
*tree
, int pos
)
1167 return isl_ast_loop_error
;
1169 if (tree
->type
!= isl_schedule_node_band
)
1170 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1171 "not a band node", return isl_ast_loop_error
);
1173 return isl_schedule_band_member_get_ast_loop_type(tree
->band
, pos
);
1176 /* Set the loop AST generation type for the band member of the band tree root
1177 * at position "pos" to "type".
1179 __isl_give isl_schedule_tree
*isl_schedule_tree_band_member_set_ast_loop_type(
1180 __isl_take isl_schedule_tree
*tree
, int pos
,
1181 enum isl_ast_loop_type type
)
1183 tree
= isl_schedule_tree_cow(tree
);
1187 if (tree
->type
!= isl_schedule_node_band
)
1188 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1189 "not a band node", return isl_schedule_tree_free(tree
));
1191 tree
->band
= isl_schedule_band_member_set_ast_loop_type(tree
->band
,
1194 return isl_schedule_tree_free(tree
);
1199 /* Return the loop AST generation type for the band member
1200 * of the band tree root at position "pos" for the isolated part.
1202 enum isl_ast_loop_type
isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1203 __isl_keep isl_schedule_tree
*tree
, int pos
)
1206 return isl_ast_loop_error
;
1208 if (tree
->type
!= isl_schedule_node_band
)
1209 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1210 "not a band node", return isl_ast_loop_error
);
1212 return isl_schedule_band_member_get_isolate_ast_loop_type(tree
->band
,
1216 /* Set the loop AST generation type for the band member of the band tree root
1217 * at position "pos" for the isolated part to "type".
1219 __isl_give isl_schedule_tree
*
1220 isl_schedule_tree_band_member_set_isolate_ast_loop_type(
1221 __isl_take isl_schedule_tree
*tree
, int pos
,
1222 enum isl_ast_loop_type type
)
1224 tree
= isl_schedule_tree_cow(tree
);
1228 if (tree
->type
!= isl_schedule_node_band
)
1229 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1230 "not a band node", return isl_schedule_tree_free(tree
));
1232 tree
->band
= isl_schedule_band_member_set_isolate_ast_loop_type(
1233 tree
->band
, pos
, type
);
1235 return isl_schedule_tree_free(tree
);
1240 /* Return the AST build options associated to the band tree root.
1242 __isl_give isl_union_set
*isl_schedule_tree_band_get_ast_build_options(
1243 __isl_keep isl_schedule_tree
*tree
)
1248 if (tree
->type
!= isl_schedule_node_band
)
1249 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1250 "not a band node", return NULL
);
1252 return isl_schedule_band_get_ast_build_options(tree
->band
);
1255 /* Replace the AST build options associated to band tree root by "options".
1256 * Updated the anchored field if the anchoredness of the root node itself
1259 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_ast_build_options(
1260 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*options
)
1264 tree
= isl_schedule_tree_cow(tree
);
1265 if (!tree
|| !options
)
1268 if (tree
->type
!= isl_schedule_node_band
)
1269 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1270 "not a band node", goto error
);
1272 was_anchored
= isl_schedule_tree_is_anchored(tree
);
1273 tree
->band
= isl_schedule_band_set_ast_build_options(tree
->band
,
1276 return isl_schedule_tree_free(tree
);
1277 if (isl_schedule_tree_is_anchored(tree
) != was_anchored
)
1278 tree
= isl_schedule_tree_update_anchored(tree
);
1282 isl_schedule_tree_free(tree
);
1283 isl_union_set_free(options
);
1287 /* Return the "isolate" option associated to the band tree root of "tree",
1288 * which is assumed to appear at schedule depth "depth".
1290 __isl_give isl_set
*isl_schedule_tree_band_get_ast_isolate_option(
1291 __isl_keep isl_schedule_tree
*tree
, int depth
)
1296 if (tree
->type
!= isl_schedule_node_band
)
1297 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1298 "not a band node", return NULL
);
1300 return isl_schedule_band_get_ast_isolate_option(tree
->band
, depth
);
1303 /* Return the context of the context tree root.
1305 __isl_give isl_set
*isl_schedule_tree_context_get_context(
1306 __isl_keep isl_schedule_tree
*tree
)
1311 if (tree
->type
!= isl_schedule_node_context
)
1312 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1313 "not a context node", return NULL
);
1315 return isl_set_copy(tree
->context
);
1318 /* Return the domain of the domain tree root.
1320 __isl_give isl_union_set
*isl_schedule_tree_domain_get_domain(
1321 __isl_keep isl_schedule_tree
*tree
)
1326 if (tree
->type
!= isl_schedule_node_domain
)
1327 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1328 "not a domain node", return NULL
);
1330 return isl_union_set_copy(tree
->domain
);
1333 /* Replace the domain of domain tree root "tree" by "domain".
1335 __isl_give isl_schedule_tree
*isl_schedule_tree_domain_set_domain(
1336 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
1338 tree
= isl_schedule_tree_cow(tree
);
1339 if (!tree
|| !domain
)
1342 if (tree
->type
!= isl_schedule_node_domain
)
1343 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1344 "not a domain node", goto error
);
1346 isl_union_set_free(tree
->domain
);
1347 tree
->domain
= domain
;
1351 isl_schedule_tree_free(tree
);
1352 isl_union_set_free(domain
);
1356 /* Return the contraction of the expansion tree root.
1358 __isl_give isl_union_pw_multi_aff
*isl_schedule_tree_expansion_get_contraction(
1359 __isl_keep isl_schedule_tree
*tree
)
1364 if (tree
->type
!= isl_schedule_node_expansion
)
1365 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1366 "not an expansion node", return NULL
);
1368 return isl_union_pw_multi_aff_copy(tree
->contraction
);
1371 /* Return the expansion of the expansion tree root.
1373 __isl_give isl_union_map
*isl_schedule_tree_expansion_get_expansion(
1374 __isl_keep isl_schedule_tree
*tree
)
1379 if (tree
->type
!= isl_schedule_node_expansion
)
1380 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1381 "not an expansion node", return NULL
);
1383 return isl_union_map_copy(tree
->expansion
);
1386 /* Replace the contraction and the expansion of the expansion tree root "tree"
1387 * by "contraction" and "expansion".
1389 __isl_give isl_schedule_tree
*
1390 isl_schedule_tree_expansion_set_contraction_and_expansion(
1391 __isl_take isl_schedule_tree
*tree
,
1392 __isl_take isl_union_pw_multi_aff
*contraction
,
1393 __isl_take isl_union_map
*expansion
)
1395 tree
= isl_schedule_tree_cow(tree
);
1396 if (!tree
|| !contraction
|| !expansion
)
1399 if (tree
->type
!= isl_schedule_node_expansion
)
1400 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1401 "not an expansion node", return NULL
);
1403 isl_union_pw_multi_aff_free(tree
->contraction
);
1404 tree
->contraction
= contraction
;
1405 isl_union_map_free(tree
->expansion
);
1406 tree
->expansion
= expansion
;
1410 isl_schedule_tree_free(tree
);
1411 isl_union_pw_multi_aff_free(contraction
);
1412 isl_union_map_free(expansion
);
1416 /* Return the extension of the extension tree root.
1418 __isl_give isl_union_map
*isl_schedule_tree_extension_get_extension(
1419 __isl_take isl_schedule_tree
*tree
)
1424 if (tree
->type
!= isl_schedule_node_extension
)
1425 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1426 "not an extension node", return NULL
);
1428 return isl_union_map_copy(tree
->extension
);
1431 /* Replace the extension of extension tree root "tree" by "extension".
1433 __isl_give isl_schedule_tree
*isl_schedule_tree_extension_set_extension(
1434 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_map
*extension
)
1436 tree
= isl_schedule_tree_cow(tree
);
1437 if (!tree
|| !extension
)
1440 if (tree
->type
!= isl_schedule_node_extension
)
1441 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1442 "not an extension node", return NULL
);
1443 isl_union_map_free(tree
->extension
);
1444 tree
->extension
= extension
;
1448 isl_schedule_tree_free(tree
);
1449 isl_union_map_free(extension
);
1453 /* Return the filter of the filter tree root.
1455 __isl_give isl_union_set
*isl_schedule_tree_filter_get_filter(
1456 __isl_keep isl_schedule_tree
*tree
)
1461 if (tree
->type
!= isl_schedule_node_filter
)
1462 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1463 "not a filter node", return NULL
);
1465 return isl_union_set_copy(tree
->filter
);
1468 /* Replace the filter of the filter tree root by "filter".
1470 __isl_give isl_schedule_tree
*isl_schedule_tree_filter_set_filter(
1471 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
1473 tree
= isl_schedule_tree_cow(tree
);
1474 if (!tree
|| !filter
)
1477 if (tree
->type
!= isl_schedule_node_filter
)
1478 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1479 "not a filter node", return NULL
);
1481 isl_union_set_free(tree
->filter
);
1482 tree
->filter
= filter
;
1486 isl_schedule_tree_free(tree
);
1487 isl_union_set_free(filter
);
1491 /* Return the guard of the guard tree root.
1493 __isl_give isl_set
*isl_schedule_tree_guard_get_guard(
1494 __isl_take isl_schedule_tree
*tree
)
1499 if (tree
->type
!= isl_schedule_node_guard
)
1500 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1501 "not a guard node", return NULL
);
1503 return isl_set_copy(tree
->guard
);
1506 /* Return the mark identifier of the mark tree root "tree".
1508 __isl_give isl_id
*isl_schedule_tree_mark_get_id(
1509 __isl_keep isl_schedule_tree
*tree
)
1514 if (tree
->type
!= isl_schedule_node_mark
)
1515 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1516 "not a mark node", return NULL
);
1518 return isl_id_copy(tree
->mark
);
1521 /* Set dim to the range dimension of "map" and abort the search.
1523 static isl_stat
set_range_dim(__isl_take isl_map
*map
, void *user
)
1527 *dim
= isl_map_dim(map
, isl_dim_out
);
1530 return isl_stat_error
;
1533 /* Return the dimension of the range of "umap".
1534 * "umap" is assumed not to be empty and
1535 * all maps inside "umap" are assumed to have the same range.
1537 * We extract the range dimension from the first map in "umap".
1539 static int range_dim(__isl_keep isl_union_map
*umap
)
1545 if (isl_union_map_n_map(umap
) == 0)
1546 isl_die(isl_union_map_get_ctx(umap
), isl_error_internal
,
1547 "unexpected empty input", return -1);
1549 isl_union_map_foreach_map(umap
, &set_range_dim
, &dim
);
1554 /* Append an "extra" number of zeros to the range of "umap" and
1555 * return the result.
1557 static __isl_give isl_union_map
*append_range(__isl_take isl_union_map
*umap
,
1563 isl_union_pw_multi_aff
*suffix
;
1564 isl_union_map
*universe
;
1565 isl_union_map
*suffix_umap
;
1567 universe
= isl_union_map_universe(isl_union_map_copy(umap
));
1568 dom
= isl_union_map_domain(universe
);
1569 space
= isl_union_set_get_space(dom
);
1570 space
= isl_space_set_from_params(space
);
1571 space
= isl_space_add_dims(space
, isl_dim_set
, extra
);
1572 mv
= isl_multi_val_zero(space
);
1574 suffix
= isl_union_pw_multi_aff_multi_val_on_domain(dom
, mv
);
1575 suffix_umap
= isl_union_map_from_union_pw_multi_aff(suffix
);
1576 umap
= isl_union_map_flat_range_product(umap
, suffix_umap
);
1581 /* Should we skip the root of "tree" while looking for the first
1582 * descendant with schedule information?
1583 * That is, is it impossible to derive any information about
1584 * the iteration domain from this node?
1586 * We do not want to skip leaf or error nodes because there is
1587 * no point in looking any deeper from these nodes.
1588 * We can only extract partial iteration domain information
1589 * from an extension node, but extension nodes are not supported
1590 * by the caller and it will error out on them.
1592 static int domain_less(__isl_keep isl_schedule_tree
*tree
)
1594 enum isl_schedule_node_type type
;
1596 type
= isl_schedule_tree_get_type(tree
);
1598 case isl_schedule_node_band
:
1599 return isl_schedule_tree_band_n_member(tree
) == 0;
1600 case isl_schedule_node_context
:
1601 case isl_schedule_node_guard
:
1602 case isl_schedule_node_mark
:
1604 case isl_schedule_node_leaf
:
1605 case isl_schedule_node_error
:
1606 case isl_schedule_node_domain
:
1607 case isl_schedule_node_expansion
:
1608 case isl_schedule_node_extension
:
1609 case isl_schedule_node_filter
:
1610 case isl_schedule_node_set
:
1611 case isl_schedule_node_sequence
:
1615 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1616 "unhandled case", return 0);
1619 /* Move down to the first descendant of "tree" that contains any schedule
1620 * information or return "leaf" if there is no such descendant.
1622 __isl_give isl_schedule_tree
*isl_schedule_tree_first_schedule_descendant(
1623 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_tree
*leaf
)
1625 while (domain_less(tree
)) {
1626 if (!isl_schedule_tree_has_children(tree
)) {
1627 isl_schedule_tree_free(tree
);
1628 return isl_schedule_tree_copy(leaf
);
1630 tree
= isl_schedule_tree_child(tree
, 0);
1636 static __isl_give isl_union_map
*subtree_schedule_extend(
1637 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
);
1639 /* Extend the schedule map "outer" with the subtree schedule
1640 * of the (single) child of "tree", if any.
1642 * If "tree" does not have any descendants (apart from those that
1643 * do not carry any schedule information), then we simply return "outer".
1644 * Otherwise, we extend the schedule map "outer" with the subtree schedule
1645 * of the single child.
1647 static __isl_give isl_union_map
*subtree_schedule_extend_child(
1648 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1650 isl_schedule_tree
*child
;
1654 return isl_union_map_free(outer
);
1655 if (!isl_schedule_tree_has_children(tree
))
1657 child
= isl_schedule_tree_get_child(tree
, 0);
1659 return isl_union_map_free(outer
);
1660 res
= subtree_schedule_extend(child
, outer
);
1661 isl_schedule_tree_free(child
);
1665 /* Extract the parameter space from one of the children of "tree",
1666 * which are assumed to be filters.
1668 static __isl_give isl_space
*extract_space_from_filter_child(
1669 __isl_keep isl_schedule_tree
*tree
)
1673 isl_schedule_tree
*child
;
1675 child
= isl_schedule_tree_list_get_schedule_tree(tree
->children
, 0);
1676 dom
= isl_schedule_tree_filter_get_filter(child
);
1677 space
= isl_union_set_get_space(dom
);
1678 isl_union_set_free(dom
);
1679 isl_schedule_tree_free(child
);
1684 /* Extend the schedule map "outer" with the subtree schedule
1685 * of a set or sequence node.
1687 * The schedule for the set or sequence node itself is composed of
1688 * pieces of the form
1696 * The first form is used if there is only a single child or
1697 * if the current node is a set node and the schedule_separate_components
1698 * option is not set.
1700 * Each of the pieces above is extended with the subtree schedule of
1701 * the child of the corresponding filter, if any, padded with zeros
1702 * to ensure that all pieces have the same range dimension.
1704 static __isl_give isl_union_map
*subtree_schedule_extend_from_children(
1705 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1714 isl_union_map
*umap
;
1719 ctx
= isl_schedule_tree_get_ctx(tree
);
1720 if (!tree
->children
)
1721 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1722 "missing children", return NULL
);
1723 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1725 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1726 "missing children", return NULL
);
1728 separate
= n
> 1 && (tree
->type
== isl_schedule_node_sequence
||
1729 isl_options_get_schedule_separate_components(ctx
));
1731 space
= extract_space_from_filter_child(tree
);
1733 umap
= isl_union_map_empty(isl_space_copy(space
));
1734 space
= isl_space_set_from_params(space
);
1736 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1737 v
= isl_val_zero(ctx
);
1739 mv
= isl_multi_val_zero(space
);
1741 dim
= isl_multi_val_dim(mv
, isl_dim_set
);
1742 for (i
= 0; i
< n
; ++i
) {
1743 isl_union_pw_multi_aff
*upma
;
1744 isl_union_map
*umap_i
;
1746 isl_schedule_tree
*child
;
1750 child
= isl_schedule_tree_list_get_schedule_tree(
1752 dom
= isl_schedule_tree_filter_get_filter(child
);
1755 mv
= isl_multi_val_set_val(mv
, 0, isl_val_copy(v
));
1756 v
= isl_val_add_ui(v
, 1);
1758 upma
= isl_union_pw_multi_aff_multi_val_on_domain(dom
,
1759 isl_multi_val_copy(mv
));
1760 umap_i
= isl_union_map_from_union_pw_multi_aff(upma
);
1761 umap_i
= isl_union_map_flat_range_product(
1762 isl_union_map_copy(outer
), umap_i
);
1763 umap_i
= subtree_schedule_extend_child(child
, umap_i
);
1764 isl_schedule_tree_free(child
);
1766 empty
= isl_union_map_is_empty(umap_i
);
1768 umap_i
= isl_union_map_free(umap_i
);
1770 isl_union_map_free(umap_i
);
1774 dim_i
= range_dim(umap_i
);
1776 umap
= isl_union_map_free(umap
);
1777 } else if (dim
< dim_i
) {
1778 umap
= append_range(umap
, dim_i
- dim
);
1780 } else if (dim_i
< dim
) {
1781 umap_i
= append_range(umap_i
, dim
- dim_i
);
1783 umap
= isl_union_map_union(umap
, umap_i
);
1787 isl_multi_val_free(mv
);
1788 isl_union_map_free(outer
);
1793 /* Extend the schedule map "outer" with the subtree schedule of "tree".
1795 * If the root of the tree is a set or a sequence, then we extend
1796 * the schedule map in subtree_schedule_extend_from_children.
1797 * Otherwise, we extend the schedule map with the partial schedule
1798 * corresponding to the root of the tree and then continue with
1799 * the single child of this root.
1800 * In the special case of an expansion, the schedule map is "extended"
1801 * by applying the expansion to the domain of the schedule map.
1803 static __isl_give isl_union_map
*subtree_schedule_extend(
1804 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1806 isl_multi_union_pw_aff
*mupa
;
1807 isl_union_map
*umap
;
1808 isl_union_set
*domain
;
1813 switch (tree
->type
) {
1814 case isl_schedule_node_error
:
1815 return isl_union_map_free(outer
);
1816 case isl_schedule_node_extension
:
1817 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1818 "cannot construct subtree schedule of tree "
1819 "with extension nodes",
1820 return isl_union_map_free(outer
));
1821 case isl_schedule_node_context
:
1822 case isl_schedule_node_guard
:
1823 case isl_schedule_node_mark
:
1824 return subtree_schedule_extend_child(tree
, outer
);
1825 case isl_schedule_node_band
:
1826 if (isl_schedule_tree_band_n_member(tree
) == 0)
1827 return subtree_schedule_extend_child(tree
, outer
);
1828 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1829 umap
= isl_union_map_from_multi_union_pw_aff(mupa
);
1830 outer
= isl_union_map_flat_range_product(outer
, umap
);
1831 umap
= subtree_schedule_extend_child(tree
, outer
);
1833 case isl_schedule_node_domain
:
1834 domain
= isl_schedule_tree_domain_get_domain(tree
);
1835 umap
= isl_union_map_from_domain(domain
);
1836 outer
= isl_union_map_flat_range_product(outer
, umap
);
1837 umap
= subtree_schedule_extend_child(tree
, outer
);
1839 case isl_schedule_node_expansion
:
1840 umap
= isl_schedule_tree_expansion_get_expansion(tree
);
1841 outer
= isl_union_map_apply_domain(outer
, umap
);
1842 umap
= subtree_schedule_extend_child(tree
, outer
);
1844 case isl_schedule_node_filter
:
1845 domain
= isl_schedule_tree_filter_get_filter(tree
);
1846 umap
= isl_union_map_from_domain(domain
);
1847 outer
= isl_union_map_flat_range_product(outer
, umap
);
1848 umap
= subtree_schedule_extend_child(tree
, outer
);
1850 case isl_schedule_node_leaf
:
1851 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1852 "leaf node should be handled by caller", return NULL
);
1853 case isl_schedule_node_set
:
1854 case isl_schedule_node_sequence
:
1855 umap
= subtree_schedule_extend_from_children(tree
, outer
);
1862 static __isl_give isl_union_set
*initial_domain(
1863 __isl_keep isl_schedule_tree
*tree
);
1865 /* Extract a universe domain from the children of the tree root "tree",
1866 * which is a set or sequence, meaning that its children are filters.
1867 * In particular, return the union of the universes of the filters.
1869 static __isl_give isl_union_set
*initial_domain_from_children(
1870 __isl_keep isl_schedule_tree
*tree
)
1874 isl_union_set
*domain
;
1876 if (!tree
->children
)
1877 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1878 "missing children", return NULL
);
1879 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1881 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1882 "missing children", return NULL
);
1884 space
= extract_space_from_filter_child(tree
);
1885 domain
= isl_union_set_empty(space
);
1887 for (i
= 0; i
< n
; ++i
) {
1888 isl_schedule_tree
*child
;
1889 isl_union_set
*domain_i
;
1891 child
= isl_schedule_tree_get_child(tree
, i
);
1892 domain_i
= initial_domain(child
);
1893 domain
= isl_union_set_union(domain
, domain_i
);
1894 isl_schedule_tree_free(child
);
1900 /* Extract a universe domain from the tree root "tree".
1901 * The caller is responsible for making sure that this node
1902 * would not be skipped by isl_schedule_tree_first_schedule_descendant
1903 * and that it is not a leaf node.
1905 static __isl_give isl_union_set
*initial_domain(
1906 __isl_keep isl_schedule_tree
*tree
)
1908 isl_multi_union_pw_aff
*mupa
;
1909 isl_union_set
*domain
;
1915 switch (tree
->type
) {
1916 case isl_schedule_node_error
:
1918 case isl_schedule_node_context
:
1919 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1920 "context node should be handled by caller",
1922 case isl_schedule_node_guard
:
1923 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1924 "guard node should be handled by caller",
1926 case isl_schedule_node_mark
:
1927 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1928 "mark node should be handled by caller",
1930 case isl_schedule_node_extension
:
1931 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1932 "cannot construct subtree schedule of tree "
1933 "with extension nodes", return NULL
);
1934 case isl_schedule_node_band
:
1935 if (isl_schedule_tree_band_n_member(tree
) == 0)
1936 isl_die(isl_schedule_tree_get_ctx(tree
),
1938 "0D band should be handled by caller",
1940 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1941 domain
= isl_multi_union_pw_aff_domain(mupa
);
1942 domain
= isl_union_set_universe(domain
);
1944 case isl_schedule_node_domain
:
1945 domain
= isl_schedule_tree_domain_get_domain(tree
);
1946 domain
= isl_union_set_universe(domain
);
1948 case isl_schedule_node_expansion
:
1949 exp
= isl_schedule_tree_expansion_get_expansion(tree
);
1950 exp
= isl_union_map_universe(exp
);
1951 domain
= isl_union_map_domain(exp
);
1953 case isl_schedule_node_filter
:
1954 domain
= isl_schedule_tree_filter_get_filter(tree
);
1955 domain
= isl_union_set_universe(domain
);
1957 case isl_schedule_node_leaf
:
1958 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1959 "leaf node should be handled by caller", return NULL
);
1960 case isl_schedule_node_set
:
1961 case isl_schedule_node_sequence
:
1962 domain
= initial_domain_from_children(tree
);
1969 /* Return the subtree schedule of a node that contains some schedule
1970 * information, i.e., a node that would not be skipped by
1971 * isl_schedule_tree_first_schedule_descendant and that is not a leaf.
1973 * If the tree contains any expansions, then the returned subtree
1974 * schedule is formulated in terms of the expanded domains.
1975 * The tree is not allowed to contain any extension nodes.
1977 * We start with an initial zero-dimensional subtree schedule based
1978 * on the domain information in the root node and then extend it
1979 * based on the schedule information in the root node and its descendants.
1981 __isl_give isl_union_map
*isl_schedule_tree_get_subtree_schedule_union_map(
1982 __isl_keep isl_schedule_tree
*tree
)
1984 isl_union_set
*domain
;
1985 isl_union_map
*umap
;
1987 domain
= initial_domain(tree
);
1988 umap
= isl_union_map_from_domain(domain
);
1989 return subtree_schedule_extend(tree
, umap
);
1992 /* Multiply the partial schedule of the band root node of "tree"
1993 * with the factors in "mv".
1995 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale(
1996 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
2000 if (tree
->type
!= isl_schedule_node_band
)
2001 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2002 "not a band node", goto error
);
2004 tree
= isl_schedule_tree_cow(tree
);
2008 tree
->band
= isl_schedule_band_scale(tree
->band
, mv
);
2010 return isl_schedule_tree_free(tree
);
2014 isl_schedule_tree_free(tree
);
2015 isl_multi_val_free(mv
);
2019 /* Divide the partial schedule of the band root node of "tree"
2020 * by the factors in "mv".
2022 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale_down(
2023 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
2027 if (tree
->type
!= isl_schedule_node_band
)
2028 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2029 "not a band node", goto error
);
2031 tree
= isl_schedule_tree_cow(tree
);
2035 tree
->band
= isl_schedule_band_scale_down(tree
->band
, mv
);
2037 return isl_schedule_tree_free(tree
);
2041 isl_schedule_tree_free(tree
);
2042 isl_multi_val_free(mv
);
2046 /* Reduce the partial schedule of the band root node of "tree"
2047 * modulo the factors in "mv".
2049 __isl_give isl_schedule_tree
*isl_schedule_tree_band_mod(
2050 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
2054 if (tree
->type
!= isl_schedule_node_band
)
2055 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2056 "not a band node", goto error
);
2058 tree
= isl_schedule_tree_cow(tree
);
2062 tree
->band
= isl_schedule_band_mod(tree
->band
, mv
);
2064 return isl_schedule_tree_free(tree
);
2068 isl_schedule_tree_free(tree
);
2069 isl_multi_val_free(mv
);
2073 /* Shift the partial schedule of the band root node of "tree" by "shift".
2075 __isl_give isl_schedule_tree
*isl_schedule_tree_band_shift(
2076 __isl_take isl_schedule_tree
*tree
,
2077 __isl_take isl_multi_union_pw_aff
*shift
)
2079 if (!tree
|| !shift
)
2081 if (tree
->type
!= isl_schedule_node_band
)
2082 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2083 "not a band node", goto error
);
2085 tree
= isl_schedule_tree_cow(tree
);
2089 tree
->band
= isl_schedule_band_shift(tree
->band
, shift
);
2091 return isl_schedule_tree_free(tree
);
2095 isl_schedule_tree_free(tree
);
2096 isl_multi_union_pw_aff_free(shift
);
2100 /* Given two trees with sequence roots, replace the child at position
2101 * "pos" of "tree" with the children of "child".
2103 __isl_give isl_schedule_tree
*isl_schedule_tree_sequence_splice(
2104 __isl_take isl_schedule_tree
*tree
, int pos
,
2105 __isl_take isl_schedule_tree
*child
)
2108 isl_schedule_tree_list
*list1
, *list2
;
2110 tree
= isl_schedule_tree_cow(tree
);
2111 if (!tree
|| !child
)
2113 if (isl_schedule_tree_get_type(tree
) != isl_schedule_node_sequence
)
2114 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2115 "not a sequence node", goto error
);
2116 n
= isl_schedule_tree_n_children(tree
);
2117 if (pos
< 0 || pos
>= n
)
2118 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2119 "position out of bounds", goto error
);
2120 if (isl_schedule_tree_get_type(child
) != isl_schedule_node_sequence
)
2121 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2122 "not a sequence node", goto error
);
2124 list1
= isl_schedule_tree_list_copy(tree
->children
);
2125 list1
= isl_schedule_tree_list_drop(list1
, pos
, n
- pos
);
2126 list2
= isl_schedule_tree_list_copy(tree
->children
);
2127 list2
= isl_schedule_tree_list_drop(list2
, 0, pos
+ 1);
2128 list1
= isl_schedule_tree_list_concat(list1
,
2129 isl_schedule_tree_list_copy(child
->children
));
2130 list1
= isl_schedule_tree_list_concat(list1
, list2
);
2132 isl_schedule_tree_free(tree
);
2133 isl_schedule_tree_free(child
);
2134 return isl_schedule_tree_from_children(isl_schedule_node_sequence
,
2137 isl_schedule_tree_free(tree
);
2138 isl_schedule_tree_free(child
);
2142 /* Tile the band root node of "tree" with tile sizes "sizes".
2144 * We duplicate the band node, change the schedule of one of them
2145 * to the tile schedule and the other to the point schedule and then
2146 * attach the point band as a child to the tile band.
2148 __isl_give isl_schedule_tree
*isl_schedule_tree_band_tile(
2149 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*sizes
)
2151 isl_schedule_tree
*child
= NULL
;
2153 if (!tree
|| !sizes
)
2155 if (tree
->type
!= isl_schedule_node_band
)
2156 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2157 "not a band node", goto error
);
2159 child
= isl_schedule_tree_copy(tree
);
2160 tree
= isl_schedule_tree_cow(tree
);
2161 child
= isl_schedule_tree_cow(child
);
2162 if (!tree
|| !child
)
2165 tree
->band
= isl_schedule_band_tile(tree
->band
,
2166 isl_multi_val_copy(sizes
));
2169 child
->band
= isl_schedule_band_point(child
->band
, tree
->band
, sizes
);
2171 child
= isl_schedule_tree_free(child
);
2173 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
2177 isl_schedule_tree_free(child
);
2178 isl_schedule_tree_free(tree
);
2179 isl_multi_val_free(sizes
);
2183 /* Split the band root node of "tree" into two nested band nodes,
2184 * one with the first "pos" dimensions and
2185 * one with the remaining dimensions.
2187 __isl_give isl_schedule_tree
*isl_schedule_tree_band_split(
2188 __isl_take isl_schedule_tree
*tree
, int pos
)
2191 isl_schedule_tree
*child
;
2195 if (tree
->type
!= isl_schedule_node_band
)
2196 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2197 "not a band node", return isl_schedule_tree_free(tree
));
2199 n
= isl_schedule_tree_band_n_member(tree
);
2200 if (pos
< 0 || pos
> n
)
2201 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2202 "position out of bounds",
2203 return isl_schedule_tree_free(tree
));
2205 child
= isl_schedule_tree_copy(tree
);
2206 tree
= isl_schedule_tree_cow(tree
);
2207 child
= isl_schedule_tree_cow(child
);
2208 if (!tree
|| !child
)
2211 child
->band
= isl_schedule_band_drop(child
->band
, 0, pos
);
2212 tree
->band
= isl_schedule_band_drop(tree
->band
, pos
, n
- pos
);
2213 if (!child
->band
|| !tree
->band
)
2216 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
2220 isl_schedule_tree_free(child
);
2221 isl_schedule_tree_free(tree
);
2225 /* Attach "tree2" at each of the leaves of "tree1".
2227 * If "tree1" does not have any explicit children, then make "tree2"
2228 * its single child. Otherwise, attach "tree2" to the leaves of
2229 * each of the children of "tree1".
2231 __isl_give isl_schedule_tree
*isl_schedule_tree_append_to_leaves(
2232 __isl_take isl_schedule_tree
*tree1
,
2233 __isl_take isl_schedule_tree
*tree2
)
2237 if (!tree1
|| !tree2
)
2239 n
= isl_schedule_tree_n_children(tree1
);
2241 isl_schedule_tree_list
*list
;
2242 list
= isl_schedule_tree_list_from_schedule_tree(tree2
);
2243 tree1
= isl_schedule_tree_set_children(tree1
, list
);
2246 for (i
= 0; i
< n
; ++i
) {
2247 isl_schedule_tree
*child
;
2249 child
= isl_schedule_tree_get_child(tree1
, i
);
2250 child
= isl_schedule_tree_append_to_leaves(child
,
2251 isl_schedule_tree_copy(tree2
));
2252 tree1
= isl_schedule_tree_replace_child(tree1
, i
, child
);
2255 isl_schedule_tree_free(tree2
);
2258 isl_schedule_tree_free(tree1
);
2259 isl_schedule_tree_free(tree2
);
2263 /* Reset the user pointer on all identifiers of parameters and tuples
2264 * in the root of "tree".
2266 __isl_give isl_schedule_tree
*isl_schedule_tree_reset_user(
2267 __isl_take isl_schedule_tree
*tree
)
2269 if (isl_schedule_tree_is_leaf(tree
))
2272 tree
= isl_schedule_tree_cow(tree
);
2276 switch (tree
->type
) {
2277 case isl_schedule_node_error
:
2278 return isl_schedule_tree_free(tree
);
2279 case isl_schedule_node_band
:
2280 tree
->band
= isl_schedule_band_reset_user(tree
->band
);
2282 return isl_schedule_tree_free(tree
);
2284 case isl_schedule_node_context
:
2285 tree
->context
= isl_set_reset_user(tree
->context
);
2287 return isl_schedule_tree_free(tree
);
2289 case isl_schedule_node_domain
:
2290 tree
->domain
= isl_union_set_reset_user(tree
->domain
);
2292 return isl_schedule_tree_free(tree
);
2294 case isl_schedule_node_expansion
:
2296 isl_union_pw_multi_aff_reset_user(tree
->contraction
);
2297 tree
->expansion
= isl_union_map_reset_user(tree
->expansion
);
2298 if (!tree
->contraction
|| !tree
->expansion
)
2299 return isl_schedule_tree_free(tree
);
2301 case isl_schedule_node_extension
:
2302 tree
->extension
= isl_union_map_reset_user(tree
->extension
);
2303 if (!tree
->extension
)
2304 return isl_schedule_tree_free(tree
);
2306 case isl_schedule_node_filter
:
2307 tree
->filter
= isl_union_set_reset_user(tree
->filter
);
2309 return isl_schedule_tree_free(tree
);
2311 case isl_schedule_node_guard
:
2312 tree
->guard
= isl_set_reset_user(tree
->guard
);
2314 return isl_schedule_tree_free(tree
);
2316 case isl_schedule_node_leaf
:
2317 case isl_schedule_node_mark
:
2318 case isl_schedule_node_sequence
:
2319 case isl_schedule_node_set
:
2326 /* Align the parameters of the root of "tree" to those of "space".
2328 __isl_give isl_schedule_tree
*isl_schedule_tree_align_params(
2329 __isl_take isl_schedule_tree
*tree
, __isl_take isl_space
*space
)
2334 if (isl_schedule_tree_is_leaf(tree
)) {
2335 isl_space_free(space
);
2339 tree
= isl_schedule_tree_cow(tree
);
2343 switch (tree
->type
) {
2344 case isl_schedule_node_error
:
2346 case isl_schedule_node_band
:
2347 tree
->band
= isl_schedule_band_align_params(tree
->band
, space
);
2349 return isl_schedule_tree_free(tree
);
2351 case isl_schedule_node_context
:
2352 tree
->context
= isl_set_align_params(tree
->context
, space
);
2354 return isl_schedule_tree_free(tree
);
2356 case isl_schedule_node_domain
:
2357 tree
->domain
= isl_union_set_align_params(tree
->domain
, space
);
2359 return isl_schedule_tree_free(tree
);
2361 case isl_schedule_node_expansion
:
2363 isl_union_pw_multi_aff_align_params(tree
->contraction
,
2364 isl_space_copy(space
));
2365 tree
->expansion
= isl_union_map_align_params(tree
->expansion
,
2367 if (!tree
->contraction
|| !tree
->expansion
)
2368 return isl_schedule_tree_free(tree
);
2370 case isl_schedule_node_extension
:
2371 tree
->extension
= isl_union_map_align_params(tree
->extension
,
2373 if (!tree
->extension
)
2374 return isl_schedule_tree_free(tree
);
2376 case isl_schedule_node_filter
:
2377 tree
->filter
= isl_union_set_align_params(tree
->filter
, space
);
2379 return isl_schedule_tree_free(tree
);
2381 case isl_schedule_node_guard
:
2382 tree
->guard
= isl_set_align_params(tree
->guard
, space
);
2384 return isl_schedule_tree_free(tree
);
2386 case isl_schedule_node_leaf
:
2387 case isl_schedule_node_mark
:
2388 case isl_schedule_node_sequence
:
2389 case isl_schedule_node_set
:
2390 isl_space_free(space
);
2396 isl_space_free(space
);
2397 isl_schedule_tree_free(tree
);
2401 /* Does "tree" involve the iteration domain?
2402 * That is, does it need to be modified
2403 * by isl_schedule_tree_pullback_union_pw_multi_aff?
2405 static int involves_iteration_domain(__isl_keep isl_schedule_tree
*tree
)
2410 switch (tree
->type
) {
2411 case isl_schedule_node_error
:
2413 case isl_schedule_node_band
:
2414 case isl_schedule_node_domain
:
2415 case isl_schedule_node_expansion
:
2416 case isl_schedule_node_extension
:
2417 case isl_schedule_node_filter
:
2419 case isl_schedule_node_context
:
2420 case isl_schedule_node_leaf
:
2421 case isl_schedule_node_guard
:
2422 case isl_schedule_node_mark
:
2423 case isl_schedule_node_sequence
:
2424 case isl_schedule_node_set
:
2428 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2429 "unhandled case", return -1);
2432 /* Compute the pullback of the root node of "tree" by the function
2433 * represented by "upma".
2434 * In other words, plug in "upma" in the iteration domains of
2435 * the root node of "tree".
2436 * We currently do not handle expansion nodes.
2438 * We first check if the root node involves any iteration domains.
2439 * If so, we handle the specific cases.
2441 __isl_give isl_schedule_tree
*isl_schedule_tree_pullback_union_pw_multi_aff(
2442 __isl_take isl_schedule_tree
*tree
,
2443 __isl_take isl_union_pw_multi_aff
*upma
)
2450 involves
= involves_iteration_domain(tree
);
2454 isl_union_pw_multi_aff_free(upma
);
2458 tree
= isl_schedule_tree_cow(tree
);
2462 if (tree
->type
== isl_schedule_node_band
) {
2463 tree
->band
= isl_schedule_band_pullback_union_pw_multi_aff(
2466 return isl_schedule_tree_free(tree
);
2467 } else if (tree
->type
== isl_schedule_node_domain
) {
2469 isl_union_set_preimage_union_pw_multi_aff(tree
->domain
,
2472 return isl_schedule_tree_free(tree
);
2473 } else if (tree
->type
== isl_schedule_node_expansion
) {
2474 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_unsupported
,
2475 "cannot pullback expansion node", goto error
);
2476 } else if (tree
->type
== isl_schedule_node_extension
) {
2478 isl_union_map_preimage_range_union_pw_multi_aff(
2479 tree
->extension
, upma
);
2480 if (!tree
->extension
)
2481 return isl_schedule_tree_free(tree
);
2482 } else if (tree
->type
== isl_schedule_node_filter
) {
2484 isl_union_set_preimage_union_pw_multi_aff(tree
->filter
,
2487 return isl_schedule_tree_free(tree
);
2492 isl_union_pw_multi_aff_free(upma
);
2493 isl_schedule_tree_free(tree
);
2497 /* Compute the gist of the band tree root with respect to "context".
2499 __isl_give isl_schedule_tree
*isl_schedule_tree_band_gist(
2500 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*context
)
2504 if (tree
->type
!= isl_schedule_node_band
)
2505 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2506 "not a band node", goto error
);
2507 tree
= isl_schedule_tree_cow(tree
);
2511 tree
->band
= isl_schedule_band_gist(tree
->band
, context
);
2513 return isl_schedule_tree_free(tree
);
2516 isl_union_set_free(context
);
2517 isl_schedule_tree_free(tree
);
2521 /* Are any members in "band" marked coincident?
2523 static int any_coincident(__isl_keep isl_schedule_band
*band
)
2527 n
= isl_schedule_band_n_member(band
);
2528 for (i
= 0; i
< n
; ++i
)
2529 if (isl_schedule_band_member_get_coincident(band
, i
))
2535 /* Print the band node "band" to "p".
2537 * The permutable and coincident properties are only printed if they
2538 * are different from the defaults.
2539 * The coincident property is always printed in YAML flow style.
2541 static __isl_give isl_printer
*print_tree_band(__isl_take isl_printer
*p
,
2542 __isl_keep isl_schedule_band
*band
)
2544 isl_union_set
*options
;
2547 p
= isl_printer_print_str(p
, "schedule");
2548 p
= isl_printer_yaml_next(p
);
2549 p
= isl_printer_print_str(p
, "\"");
2550 p
= isl_printer_print_multi_union_pw_aff(p
, band
->mupa
);
2551 p
= isl_printer_print_str(p
, "\"");
2552 if (isl_schedule_band_get_permutable(band
)) {
2553 p
= isl_printer_yaml_next(p
);
2554 p
= isl_printer_print_str(p
, "permutable");
2555 p
= isl_printer_yaml_next(p
);
2556 p
= isl_printer_print_int(p
, 1);
2558 if (any_coincident(band
)) {
2562 p
= isl_printer_yaml_next(p
);
2563 p
= isl_printer_print_str(p
, "coincident");
2564 p
= isl_printer_yaml_next(p
);
2565 style
= isl_printer_get_yaml_style(p
);
2566 p
= isl_printer_set_yaml_style(p
, ISL_YAML_STYLE_FLOW
);
2567 p
= isl_printer_yaml_start_sequence(p
);
2568 n
= isl_schedule_band_n_member(band
);
2569 for (i
= 0; i
< n
; ++i
) {
2570 p
= isl_printer_print_int(p
,
2571 isl_schedule_band_member_get_coincident(band
, i
));
2572 p
= isl_printer_yaml_next(p
);
2574 p
= isl_printer_yaml_end_sequence(p
);
2575 p
= isl_printer_set_yaml_style(p
, style
);
2577 options
= isl_schedule_band_get_ast_build_options(band
);
2578 empty
= isl_union_set_is_empty(options
);
2580 p
= isl_printer_free(p
);
2582 p
= isl_printer_yaml_next(p
);
2583 p
= isl_printer_print_str(p
, "options");
2584 p
= isl_printer_yaml_next(p
);
2585 p
= isl_printer_print_str(p
, "\"");
2586 p
= isl_printer_print_union_set(p
, options
);
2587 p
= isl_printer_print_str(p
, "\"");
2589 isl_union_set_free(options
);
2594 /* Print "tree" to "p".
2596 * If "n_ancestor" is non-negative, then "child_pos" contains the child
2597 * positions of a descendant of the current node that should be marked
2598 * (by the comment "YOU ARE HERE"). In particular, if "n_ancestor"
2599 * is zero, then the current node should be marked.
2600 * The marking is only printed in YAML block format.
2602 * Implicit leaf nodes are not printed, except if they correspond
2603 * to the node that should be marked.
2605 __isl_give isl_printer
*isl_printer_print_schedule_tree_mark(
2606 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
,
2607 int n_ancestor
, int *child_pos
)
2613 block
= isl_printer_get_yaml_style(p
) == ISL_YAML_STYLE_BLOCK
;
2615 p
= isl_printer_yaml_start_mapping(p
);
2616 if (n_ancestor
== 0 && block
) {
2617 p
= isl_printer_print_str(p
, "# YOU ARE HERE");
2618 p
= isl_printer_end_line(p
);
2619 p
= isl_printer_start_line(p
);
2621 switch (tree
->type
) {
2622 case isl_schedule_node_error
:
2623 p
= isl_printer_print_str(p
, "ERROR");
2625 case isl_schedule_node_leaf
:
2626 p
= isl_printer_print_str(p
, "leaf");
2628 case isl_schedule_node_sequence
:
2629 p
= isl_printer_print_str(p
, "sequence");
2632 case isl_schedule_node_set
:
2633 p
= isl_printer_print_str(p
, "set");
2636 case isl_schedule_node_context
:
2637 p
= isl_printer_print_str(p
, "context");
2638 p
= isl_printer_yaml_next(p
);
2639 p
= isl_printer_print_str(p
, "\"");
2640 p
= isl_printer_print_set(p
, tree
->context
);
2641 p
= isl_printer_print_str(p
, "\"");
2643 case isl_schedule_node_domain
:
2644 p
= isl_printer_print_str(p
, "domain");
2645 p
= isl_printer_yaml_next(p
);
2646 p
= isl_printer_print_str(p
, "\"");
2647 p
= isl_printer_print_union_set(p
, tree
->domain
);
2648 p
= isl_printer_print_str(p
, "\"");
2650 case isl_schedule_node_expansion
:
2651 p
= isl_printer_print_str(p
, "contraction");
2652 p
= isl_printer_yaml_next(p
);
2653 p
= isl_printer_print_str(p
, "\"");
2654 p
= isl_printer_print_union_pw_multi_aff(p
, tree
->contraction
);
2655 p
= isl_printer_print_str(p
, "\"");
2656 p
= isl_printer_yaml_next(p
);
2657 p
= isl_printer_print_str(p
, "expansion");
2658 p
= isl_printer_yaml_next(p
);
2659 p
= isl_printer_print_str(p
, "\"");
2660 p
= isl_printer_print_union_map(p
, tree
->expansion
);
2661 p
= isl_printer_print_str(p
, "\"");
2663 case isl_schedule_node_extension
:
2664 p
= isl_printer_print_str(p
, "extension");
2665 p
= isl_printer_yaml_next(p
);
2666 p
= isl_printer_print_str(p
, "\"");
2667 p
= isl_printer_print_union_map(p
, tree
->extension
);
2668 p
= isl_printer_print_str(p
, "\"");
2670 case isl_schedule_node_filter
:
2671 p
= isl_printer_print_str(p
, "filter");
2672 p
= isl_printer_yaml_next(p
);
2673 p
= isl_printer_print_str(p
, "\"");
2674 p
= isl_printer_print_union_set(p
, tree
->filter
);
2675 p
= isl_printer_print_str(p
, "\"");
2677 case isl_schedule_node_guard
:
2678 p
= isl_printer_print_str(p
, "guard");
2679 p
= isl_printer_yaml_next(p
);
2680 p
= isl_printer_print_str(p
, "\"");
2681 p
= isl_printer_print_set(p
, tree
->guard
);
2682 p
= isl_printer_print_str(p
, "\"");
2684 case isl_schedule_node_mark
:
2685 p
= isl_printer_print_str(p
, "mark");
2686 p
= isl_printer_yaml_next(p
);
2687 p
= isl_printer_print_str(p
, "\"");
2688 p
= isl_printer_print_str(p
, isl_id_get_name(tree
->mark
));
2689 p
= isl_printer_print_str(p
, "\"");
2691 case isl_schedule_node_band
:
2692 p
= print_tree_band(p
, tree
->band
);
2695 p
= isl_printer_yaml_next(p
);
2697 if (!tree
->children
) {
2698 if (n_ancestor
> 0 && block
) {
2699 isl_schedule_tree
*leaf
;
2701 p
= isl_printer_print_str(p
, "child");
2702 p
= isl_printer_yaml_next(p
);
2703 leaf
= isl_schedule_tree_leaf(isl_printer_get_ctx(p
));
2704 p
= isl_printer_print_schedule_tree_mark(p
,
2706 isl_schedule_tree_free(leaf
);
2707 p
= isl_printer_yaml_next(p
);
2709 return isl_printer_yaml_end_mapping(p
);
2713 p
= isl_printer_yaml_start_sequence(p
);
2715 p
= isl_printer_print_str(p
, "child");
2716 p
= isl_printer_yaml_next(p
);
2719 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
2720 for (i
= 0; i
< n
; ++i
) {
2721 isl_schedule_tree
*t
;
2723 t
= isl_schedule_tree_get_child(tree
, i
);
2724 if (n_ancestor
> 0 && child_pos
[0] == i
)
2725 p
= isl_printer_print_schedule_tree_mark(p
, t
,
2726 n_ancestor
- 1, child_pos
+ 1);
2728 p
= isl_printer_print_schedule_tree_mark(p
, t
,
2730 isl_schedule_tree_free(t
);
2732 p
= isl_printer_yaml_next(p
);
2736 p
= isl_printer_yaml_end_sequence(p
);
2737 p
= isl_printer_yaml_end_mapping(p
);
2742 /* Print "tree" to "p".
2744 __isl_give isl_printer
*isl_printer_print_schedule_tree(
2745 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
)
2747 return isl_printer_print_schedule_tree_mark(p
, tree
, -1, NULL
);
2750 void isl_schedule_tree_dump(__isl_keep isl_schedule_tree
*tree
)
2753 isl_printer
*printer
;
2758 ctx
= isl_schedule_tree_get_ctx(tree
);
2759 printer
= isl_printer_to_file(ctx
, stderr
);
2760 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
2761 printer
= isl_printer_print_schedule_tree(printer
, tree
);
2763 isl_printer_free(printer
);