2 * Copyright 2013-2014 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
4 * Copyright 2016 INRIA Paris
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege,
9 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
10 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
11 * B.P. 105 - 78153 Le Chesnay, France
12 * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12,
13 * CS 42112, 75589 Paris Cedex 12, France
18 #include <isl/space.h>
20 #include <isl_schedule_band.h>
21 #include <isl_schedule_private.h>
24 #define EL isl_schedule_tree
26 #include <isl_list_templ.h>
29 #define BASE schedule_tree
31 #include <isl_list_templ.c>
33 /* Is "tree" the leaf of a schedule tree?
35 int isl_schedule_tree_is_leaf(__isl_keep isl_schedule_tree
*tree
)
37 return isl_schedule_tree_get_type(tree
) == isl_schedule_node_leaf
;
40 /* Create a new schedule tree of type "type".
41 * The caller is responsible for filling in the type specific fields and
44 * By default, the single node tree does not have any anchored nodes.
45 * The caller is responsible for updating the anchored field if needed.
47 static __isl_give isl_schedule_tree
*isl_schedule_tree_alloc(isl_ctx
*ctx
,
48 enum isl_schedule_node_type type
)
50 isl_schedule_tree
*tree
;
52 if (type
== isl_schedule_node_error
)
55 tree
= isl_calloc_type(ctx
, isl_schedule_tree
);
68 /* Return a fresh copy of "tree".
70 __isl_take isl_schedule_tree
*isl_schedule_tree_dup(
71 __isl_keep isl_schedule_tree
*tree
)
74 isl_schedule_tree
*dup
;
79 ctx
= isl_schedule_tree_get_ctx(tree
);
80 dup
= isl_schedule_tree_alloc(ctx
, tree
->type
);
85 case isl_schedule_node_error
:
86 isl_die(ctx
, isl_error_internal
,
87 "allocation should have failed",
88 return isl_schedule_tree_free(dup
));
89 case isl_schedule_node_band
:
90 dup
->band
= isl_schedule_band_copy(tree
->band
);
92 return isl_schedule_tree_free(dup
);
94 case isl_schedule_node_context
:
95 dup
->context
= isl_set_copy(tree
->context
);
97 return isl_schedule_tree_free(dup
);
99 case isl_schedule_node_domain
:
100 dup
->domain
= isl_union_set_copy(tree
->domain
);
102 return isl_schedule_tree_free(dup
);
104 case isl_schedule_node_expansion
:
106 isl_union_pw_multi_aff_copy(tree
->contraction
);
107 dup
->expansion
= isl_union_map_copy(tree
->expansion
);
108 if (!dup
->contraction
|| !dup
->expansion
)
109 return isl_schedule_tree_free(dup
);
111 case isl_schedule_node_extension
:
112 dup
->extension
= isl_union_map_copy(tree
->extension
);
114 return isl_schedule_tree_free(dup
);
116 case isl_schedule_node_filter
:
117 dup
->filter
= isl_union_set_copy(tree
->filter
);
119 return isl_schedule_tree_free(dup
);
121 case isl_schedule_node_guard
:
122 dup
->guard
= isl_set_copy(tree
->guard
);
124 return isl_schedule_tree_free(dup
);
126 case isl_schedule_node_mark
:
127 dup
->mark
= isl_id_copy(tree
->mark
);
129 return isl_schedule_tree_free(dup
);
131 case isl_schedule_node_leaf
:
132 case isl_schedule_node_sequence
:
133 case isl_schedule_node_set
:
137 if (tree
->children
) {
138 dup
->children
= isl_schedule_tree_list_copy(tree
->children
);
140 return isl_schedule_tree_free(dup
);
142 dup
->anchored
= tree
->anchored
;
147 /* Return an isl_schedule_tree that is equal to "tree" and that has only
148 * a single reference.
150 __isl_give isl_schedule_tree
*isl_schedule_tree_cow(
151 __isl_take isl_schedule_tree
*tree
)
159 return isl_schedule_tree_dup(tree
);
162 /* Return a new reference to "tree".
164 __isl_give isl_schedule_tree
*isl_schedule_tree_copy(
165 __isl_keep isl_schedule_tree
*tree
)
174 /* Free "tree" and return NULL.
176 __isl_null isl_schedule_tree
*isl_schedule_tree_free(
177 __isl_take isl_schedule_tree
*tree
)
184 switch (tree
->type
) {
185 case isl_schedule_node_band
:
186 isl_schedule_band_free(tree
->band
);
188 case isl_schedule_node_context
:
189 isl_set_free(tree
->context
);
191 case isl_schedule_node_domain
:
192 isl_union_set_free(tree
->domain
);
194 case isl_schedule_node_expansion
:
195 isl_union_pw_multi_aff_free(tree
->contraction
);
196 isl_union_map_free(tree
->expansion
);
198 case isl_schedule_node_extension
:
199 isl_union_map_free(tree
->extension
);
201 case isl_schedule_node_filter
:
202 isl_union_set_free(tree
->filter
);
204 case isl_schedule_node_guard
:
205 isl_set_free(tree
->guard
);
207 case isl_schedule_node_mark
:
208 isl_id_free(tree
->mark
);
210 case isl_schedule_node_sequence
:
211 case isl_schedule_node_set
:
212 case isl_schedule_node_error
:
213 case isl_schedule_node_leaf
:
216 isl_schedule_tree_list_free(tree
->children
);
217 isl_ctx_deref(tree
->ctx
);
223 /* Create and return a new leaf schedule tree.
225 __isl_give isl_schedule_tree
*isl_schedule_tree_leaf(isl_ctx
*ctx
)
227 return isl_schedule_tree_alloc(ctx
, isl_schedule_node_leaf
);
230 /* Create a new band schedule tree referring to "band"
233 __isl_give isl_schedule_tree
*isl_schedule_tree_from_band(
234 __isl_take isl_schedule_band
*band
)
237 isl_schedule_tree
*tree
;
242 ctx
= isl_schedule_band_get_ctx(band
);
243 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_band
);
248 tree
->anchored
= isl_schedule_band_is_anchored(band
);
252 isl_schedule_band_free(band
);
256 /* Create a new context schedule tree with the given context and no children.
257 * Since the context references the outer schedule dimension,
258 * the tree is anchored.
260 __isl_give isl_schedule_tree
*isl_schedule_tree_from_context(
261 __isl_take isl_set
*context
)
264 isl_schedule_tree
*tree
;
269 ctx
= isl_set_get_ctx(context
);
270 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_context
);
274 tree
->context
= context
;
279 isl_set_free(context
);
283 /* Create a new domain schedule tree with the given domain and no children.
285 __isl_give isl_schedule_tree
*isl_schedule_tree_from_domain(
286 __isl_take isl_union_set
*domain
)
289 isl_schedule_tree
*tree
;
294 ctx
= isl_union_set_get_ctx(domain
);
295 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_domain
);
299 tree
->domain
= domain
;
303 isl_union_set_free(domain
);
307 /* Create a new expansion schedule tree with the given contraction and
308 * expansion and no children.
310 __isl_give isl_schedule_tree
*isl_schedule_tree_from_expansion(
311 __isl_take isl_union_pw_multi_aff
*contraction
,
312 __isl_take isl_union_map
*expansion
)
315 isl_schedule_tree
*tree
;
317 if (!contraction
|| !expansion
)
320 ctx
= isl_union_map_get_ctx(expansion
);
321 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_expansion
);
325 tree
->contraction
= contraction
;
326 tree
->expansion
= expansion
;
330 isl_union_pw_multi_aff_free(contraction
);
331 isl_union_map_free(expansion
);
335 /* Create a new extension schedule tree with the given extension and
337 * Since the domain of the extension refers to the outer schedule dimension,
338 * the tree is anchored.
340 __isl_give isl_schedule_tree
*isl_schedule_tree_from_extension(
341 __isl_take isl_union_map
*extension
)
344 isl_schedule_tree
*tree
;
349 ctx
= isl_union_map_get_ctx(extension
);
350 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_extension
);
354 tree
->extension
= extension
;
359 isl_union_map_free(extension
);
363 /* Create a new filter schedule tree with the given filter and no children.
365 __isl_give isl_schedule_tree
*isl_schedule_tree_from_filter(
366 __isl_take isl_union_set
*filter
)
369 isl_schedule_tree
*tree
;
374 ctx
= isl_union_set_get_ctx(filter
);
375 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_filter
);
379 tree
->filter
= filter
;
383 isl_union_set_free(filter
);
387 /* Create a new guard schedule tree with the given guard and no children.
388 * Since the guard references the outer schedule dimension,
389 * the tree is anchored.
391 __isl_give isl_schedule_tree
*isl_schedule_tree_from_guard(
392 __isl_take isl_set
*guard
)
395 isl_schedule_tree
*tree
;
400 ctx
= isl_set_get_ctx(guard
);
401 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_guard
);
414 /* Create a new mark schedule tree with the given mark identifier and
417 __isl_give isl_schedule_tree
*isl_schedule_tree_from_mark(
418 __isl_take isl_id
*mark
)
421 isl_schedule_tree
*tree
;
426 ctx
= isl_id_get_ctx(mark
);
427 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_mark
);
439 /* Does "tree" have any node that depends on its position
440 * in the complete schedule tree?
442 isl_bool
isl_schedule_tree_is_subtree_anchored(
443 __isl_keep isl_schedule_tree
*tree
)
445 return tree
? tree
->anchored
: isl_bool_error
;
448 /* Does the root node of "tree" depend on its position in the complete
450 * Band nodes may be anchored depending on the associated AST build options.
451 * Context, extension and guard nodes are always anchored.
453 int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree
*tree
)
458 switch (isl_schedule_tree_get_type(tree
)) {
459 case isl_schedule_node_error
:
461 case isl_schedule_node_band
:
462 return isl_schedule_band_is_anchored(tree
->band
);
463 case isl_schedule_node_context
:
464 case isl_schedule_node_extension
:
465 case isl_schedule_node_guard
:
467 case isl_schedule_node_domain
:
468 case isl_schedule_node_expansion
:
469 case isl_schedule_node_filter
:
470 case isl_schedule_node_leaf
:
471 case isl_schedule_node_mark
:
472 case isl_schedule_node_sequence
:
473 case isl_schedule_node_set
:
477 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
478 "unhandled case", return -1);
481 /* Update the anchored field of "tree" based on whether the root node
482 * itself in anchored and the anchored fields of the children.
484 * This function should be called whenever the children of a tree node
485 * are changed or the anchoredness of the tree root itself changes.
487 __isl_give isl_schedule_tree
*isl_schedule_tree_update_anchored(
488 __isl_take isl_schedule_tree
*tree
)
493 anchored
= isl_schedule_tree_is_anchored(tree
);
494 n
= isl_schedule_tree_n_children(tree
);
495 if (anchored
< 0 || n
< 0)
496 return isl_schedule_tree_free(tree
);
498 for (i
= 0; !anchored
&& i
< n
; ++i
) {
499 isl_schedule_tree
*child
;
501 child
= isl_schedule_tree_get_child(tree
, i
);
503 return isl_schedule_tree_free(tree
);
504 anchored
= child
->anchored
;
505 isl_schedule_tree_free(child
);
508 if (anchored
== tree
->anchored
)
510 tree
= isl_schedule_tree_cow(tree
);
513 tree
->anchored
= anchored
;
517 /* Create a new tree of the given type (isl_schedule_node_sequence or
518 * isl_schedule_node_set) with the given children.
520 __isl_give isl_schedule_tree
*isl_schedule_tree_from_children(
521 enum isl_schedule_node_type type
,
522 __isl_take isl_schedule_tree_list
*list
)
525 isl_schedule_tree
*tree
;
530 ctx
= isl_schedule_tree_list_get_ctx(list
);
531 tree
= isl_schedule_tree_alloc(ctx
, type
);
535 tree
->children
= list
;
536 tree
= isl_schedule_tree_update_anchored(tree
);
540 isl_schedule_tree_list_free(list
);
544 /* Construct a tree with a root node of type "type" and as children
545 * "tree1" and "tree2".
546 * If the root of one (or both) of the input trees is itself of type "type",
547 * then the tree is replaced by its children.
549 __isl_give isl_schedule_tree
*isl_schedule_tree_from_pair(
550 enum isl_schedule_node_type type
, __isl_take isl_schedule_tree
*tree1
,
551 __isl_take isl_schedule_tree
*tree2
)
554 isl_schedule_tree_list
*list
;
556 if (!tree1
|| !tree2
)
559 ctx
= isl_schedule_tree_get_ctx(tree1
);
560 if (isl_schedule_tree_get_type(tree1
) == type
) {
561 list
= isl_schedule_tree_list_copy(tree1
->children
);
562 isl_schedule_tree_free(tree1
);
564 list
= isl_schedule_tree_list_alloc(ctx
, 2);
565 list
= isl_schedule_tree_list_add(list
, tree1
);
567 if (isl_schedule_tree_get_type(tree2
) == type
) {
568 isl_schedule_tree_list
*children
;
570 children
= isl_schedule_tree_list_copy(tree2
->children
);
571 list
= isl_schedule_tree_list_concat(list
, children
);
572 isl_schedule_tree_free(tree2
);
574 list
= isl_schedule_tree_list_add(list
, tree2
);
577 return isl_schedule_tree_from_children(type
, list
);
579 isl_schedule_tree_free(tree1
);
580 isl_schedule_tree_free(tree2
);
584 /* Construct a tree with a sequence root node and as children
585 * "tree1" and "tree2".
586 * If the root of one (or both) of the input trees is itself a sequence,
587 * then the tree is replaced by its children.
589 __isl_give isl_schedule_tree
*isl_schedule_tree_sequence_pair(
590 __isl_take isl_schedule_tree
*tree1
,
591 __isl_take isl_schedule_tree
*tree2
)
593 return isl_schedule_tree_from_pair(isl_schedule_node_sequence
,
597 /* Construct a tree with a set root node and as children
598 * "tree1" and "tree2".
599 * If the root of one (or both) of the input trees is itself a set,
600 * then the tree is replaced by its children.
602 __isl_give isl_schedule_tree
*isl_schedule_tree_set_pair(
603 __isl_take isl_schedule_tree
*tree1
,
604 __isl_take isl_schedule_tree
*tree2
)
606 return isl_schedule_tree_from_pair(isl_schedule_node_set
, tree1
, tree2
);
609 /* Return the isl_ctx to which "tree" belongs.
611 isl_ctx
*isl_schedule_tree_get_ctx(__isl_keep isl_schedule_tree
*tree
)
613 return tree
? tree
->ctx
: NULL
;
616 /* Return the type of the root of the tree or isl_schedule_node_error
619 enum isl_schedule_node_type
isl_schedule_tree_get_type(
620 __isl_keep isl_schedule_tree
*tree
)
622 return tree
? tree
->type
: isl_schedule_node_error
;
625 /* Are "tree1" and "tree2" obviously equal to each other?
627 isl_bool
isl_schedule_tree_plain_is_equal(__isl_keep isl_schedule_tree
*tree1
,
628 __isl_keep isl_schedule_tree
*tree2
)
633 if (!tree1
|| !tree2
)
634 return isl_bool_error
;
636 return isl_bool_true
;
637 if (tree1
->type
!= tree2
->type
)
638 return isl_bool_false
;
640 switch (tree1
->type
) {
641 case isl_schedule_node_band
:
642 equal
= isl_schedule_band_plain_is_equal(tree1
->band
,
645 case isl_schedule_node_context
:
646 equal
= isl_set_is_equal(tree1
->context
, tree2
->context
);
648 case isl_schedule_node_domain
:
649 equal
= isl_union_set_is_equal(tree1
->domain
, tree2
->domain
);
651 case isl_schedule_node_expansion
:
652 equal
= isl_union_map_is_equal(tree1
->expansion
,
654 if (equal
>= 0 && equal
)
655 equal
= isl_union_pw_multi_aff_plain_is_equal(
656 tree1
->contraction
, tree2
->contraction
);
658 case isl_schedule_node_extension
:
659 equal
= isl_union_map_is_equal(tree1
->extension
,
662 case isl_schedule_node_filter
:
663 equal
= isl_union_set_is_equal(tree1
->filter
, tree2
->filter
);
665 case isl_schedule_node_guard
:
666 equal
= isl_set_is_equal(tree1
->guard
, tree2
->guard
);
668 case isl_schedule_node_mark
:
669 equal
= tree1
->mark
== tree2
->mark
;
671 case isl_schedule_node_leaf
:
672 case isl_schedule_node_sequence
:
673 case isl_schedule_node_set
:
674 equal
= isl_bool_true
;
676 case isl_schedule_node_error
:
677 equal
= isl_bool_error
;
681 if (equal
< 0 || !equal
)
684 n
= isl_schedule_tree_n_children(tree1
);
685 if (n
!= isl_schedule_tree_n_children(tree2
))
686 return isl_bool_false
;
687 for (i
= 0; i
< n
; ++i
) {
688 isl_schedule_tree
*child1
, *child2
;
690 child1
= isl_schedule_tree_get_child(tree1
, i
);
691 child2
= isl_schedule_tree_get_child(tree2
, i
);
692 equal
= isl_schedule_tree_plain_is_equal(child1
, child2
);
693 isl_schedule_tree_free(child1
);
694 isl_schedule_tree_free(child2
);
696 if (equal
< 0 || !equal
)
700 return isl_bool_true
;
703 /* Does "tree" have any children, other than an implicit leaf.
705 int isl_schedule_tree_has_children(__isl_keep isl_schedule_tree
*tree
)
710 return tree
->children
!= NULL
;
713 /* Return the number of children of "tree", excluding implicit leaves.
714 * The "children" field is NULL if there are
715 * no children (except for the implicit leaves).
717 int isl_schedule_tree_n_children(__isl_keep isl_schedule_tree
*tree
)
724 return isl_schedule_tree_list_n_schedule_tree(tree
->children
);
727 /* Return a copy of the (explicit) child at position "pos" of "tree".
729 __isl_give isl_schedule_tree
*isl_schedule_tree_get_child(
730 __isl_keep isl_schedule_tree
*tree
, int pos
)
735 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
736 "schedule tree has no explicit children", return NULL
);
737 return isl_schedule_tree_list_get_schedule_tree(tree
->children
, pos
);
740 /* Return a copy of the (explicit) child at position "pos" of "tree" and
743 __isl_give isl_schedule_tree
*isl_schedule_tree_child(
744 __isl_take isl_schedule_tree
*tree
, int pos
)
746 isl_schedule_tree
*child
;
748 child
= isl_schedule_tree_get_child(tree
, pos
);
749 isl_schedule_tree_free(tree
);
753 /* Remove all (explicit) children from "tree".
755 __isl_give isl_schedule_tree
*isl_schedule_tree_reset_children(
756 __isl_take isl_schedule_tree
*tree
)
758 tree
= isl_schedule_tree_cow(tree
);
761 tree
->children
= isl_schedule_tree_list_free(tree
->children
);
765 /* Remove the child at position "pos" from the children of "tree".
766 * If there was only one child to begin with, then remove all children.
768 __isl_give isl_schedule_tree
*isl_schedule_tree_drop_child(
769 __isl_take isl_schedule_tree
*tree
, int pos
)
773 tree
= isl_schedule_tree_cow(tree
);
775 n
= isl_schedule_tree_n_children(tree
);
777 return isl_schedule_tree_free(tree
);
779 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
780 "tree does not have any explicit children",
781 return isl_schedule_tree_free(tree
));
782 if (pos
< 0 || pos
>= n
)
783 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
784 "position out of bounds",
785 return isl_schedule_tree_free(tree
));
787 return isl_schedule_tree_reset_children(tree
);
789 tree
->children
= isl_schedule_tree_list_drop(tree
->children
, pos
, 1);
791 return isl_schedule_tree_free(tree
);
796 /* Replace the child at position "pos" of "tree" by "child".
798 * If the new child is a leaf, then it is not explicitly
799 * recorded in the list of children. Instead, the list of children
800 * (which is assumed to have only one element) is removed.
801 * Note that the children of set and sequence nodes are always
802 * filters, so they cannot be replaced by empty trees.
804 __isl_give isl_schedule_tree
*isl_schedule_tree_replace_child(
805 __isl_take isl_schedule_tree
*tree
, int pos
,
806 __isl_take isl_schedule_tree
*child
)
808 tree
= isl_schedule_tree_cow(tree
);
812 if (isl_schedule_tree_is_leaf(child
)) {
813 isl_schedule_tree_free(child
);
814 if (!tree
->children
&& pos
== 0)
816 if (isl_schedule_tree_n_children(tree
) != 1)
817 isl_die(isl_schedule_tree_get_ctx(tree
),
819 "can only replace single child by leaf",
821 return isl_schedule_tree_reset_children(tree
);
824 if (!tree
->children
&& pos
== 0)
826 isl_schedule_tree_list_from_schedule_tree(child
);
828 tree
->children
= isl_schedule_tree_list_set_schedule_tree(
829 tree
->children
, pos
, child
);
832 return isl_schedule_tree_free(tree
);
833 tree
= isl_schedule_tree_update_anchored(tree
);
837 isl_schedule_tree_free(tree
);
838 isl_schedule_tree_free(child
);
842 /* Replace the (explicit) children of "tree" by "children"?
844 __isl_give isl_schedule_tree
*isl_schedule_tree_set_children(
845 __isl_take isl_schedule_tree
*tree
,
846 __isl_take isl_schedule_tree_list
*children
)
848 tree
= isl_schedule_tree_cow(tree
);
849 if (!tree
|| !children
)
851 isl_schedule_tree_list_free(tree
->children
);
852 tree
->children
= children
;
855 isl_schedule_tree_free(tree
);
856 isl_schedule_tree_list_free(children
);
860 /* Create a new band schedule tree referring to "band"
861 * with "tree" as single child.
863 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_band(
864 __isl_take isl_schedule_tree
*tree
, __isl_take isl_schedule_band
*band
)
866 isl_schedule_tree
*res
;
868 res
= isl_schedule_tree_from_band(band
);
869 return isl_schedule_tree_replace_child(res
, 0, tree
);
872 /* Create a new context schedule tree with the given context and
873 * with "tree" as single child.
875 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_context(
876 __isl_take isl_schedule_tree
*tree
, __isl_take isl_set
*context
)
878 isl_schedule_tree
*res
;
880 res
= isl_schedule_tree_from_context(context
);
881 return isl_schedule_tree_replace_child(res
, 0, tree
);
884 /* Create a new domain schedule tree with the given domain and
885 * with "tree" as single child.
887 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_domain(
888 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
890 isl_schedule_tree
*res
;
892 res
= isl_schedule_tree_from_domain(domain
);
893 return isl_schedule_tree_replace_child(res
, 0, tree
);
896 /* Create a new expansion schedule tree with the given contraction and
897 * expansion and with "tree" as single child.
899 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_expansion(
900 __isl_take isl_schedule_tree
*tree
,
901 __isl_take isl_union_pw_multi_aff
*contraction
,
902 __isl_take isl_union_map
*expansion
)
904 isl_schedule_tree
*res
;
906 res
= isl_schedule_tree_from_expansion(contraction
, expansion
);
907 return isl_schedule_tree_replace_child(res
, 0, tree
);
910 /* Create a new extension schedule tree with the given extension and
911 * with "tree" as single child.
913 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_extension(
914 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_map
*extension
)
916 isl_schedule_tree
*res
;
918 res
= isl_schedule_tree_from_extension(extension
);
919 return isl_schedule_tree_replace_child(res
, 0, tree
);
922 /* Create a new filter schedule tree with the given filter and single child.
924 * If the root of "tree" is itself a filter node, then the two
925 * filter nodes are merged into one node.
927 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_filter(
928 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
930 isl_schedule_tree
*res
;
932 if (isl_schedule_tree_get_type(tree
) == isl_schedule_node_filter
) {
933 isl_union_set
*tree_filter
;
935 tree_filter
= isl_schedule_tree_filter_get_filter(tree
);
936 tree_filter
= isl_union_set_intersect(tree_filter
, filter
);
937 tree
= isl_schedule_tree_filter_set_filter(tree
, tree_filter
);
941 res
= isl_schedule_tree_from_filter(filter
);
942 return isl_schedule_tree_replace_child(res
, 0, tree
);
945 /* Insert a filter node with filter set "filter"
946 * in each of the children of "tree".
948 __isl_give isl_schedule_tree
*isl_schedule_tree_children_insert_filter(
949 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
953 if (!tree
|| !filter
)
956 n
= isl_schedule_tree_n_children(tree
);
957 for (i
= 0; i
< n
; ++i
) {
958 isl_schedule_tree
*child
;
960 child
= isl_schedule_tree_get_child(tree
, i
);
961 child
= isl_schedule_tree_insert_filter(child
,
962 isl_union_set_copy(filter
));
963 tree
= isl_schedule_tree_replace_child(tree
, i
, child
);
966 isl_union_set_free(filter
);
969 isl_union_set_free(filter
);
970 isl_schedule_tree_free(tree
);
974 /* Create a new guard schedule tree with the given guard and
975 * with "tree" as single child.
977 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_guard(
978 __isl_take isl_schedule_tree
*tree
, __isl_take isl_set
*guard
)
980 isl_schedule_tree
*res
;
982 res
= isl_schedule_tree_from_guard(guard
);
983 return isl_schedule_tree_replace_child(res
, 0, tree
);
986 /* Create a new mark schedule tree with the given mark identifier and
989 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_mark(
990 __isl_take isl_schedule_tree
*tree
, __isl_take isl_id
*mark
)
992 isl_schedule_tree
*res
;
994 res
= isl_schedule_tree_from_mark(mark
);
995 return isl_schedule_tree_replace_child(res
, 0, tree
);
998 /* Return the number of members in the band tree root.
1000 unsigned isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree
*tree
)
1005 if (tree
->type
!= isl_schedule_node_band
)
1006 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1007 "not a band node", return 0);
1009 return isl_schedule_band_n_member(tree
->band
);
1012 /* Is the band member at position "pos" of the band tree root
1013 * marked coincident?
1015 isl_bool
isl_schedule_tree_band_member_get_coincident(
1016 __isl_keep isl_schedule_tree
*tree
, int pos
)
1019 return isl_bool_error
;
1021 if (tree
->type
!= isl_schedule_node_band
)
1022 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1023 "not a band node", return isl_bool_error
);
1025 return isl_schedule_band_member_get_coincident(tree
->band
, pos
);
1028 /* Mark the given band member as being coincident or not
1029 * according to "coincident".
1031 __isl_give isl_schedule_tree
*isl_schedule_tree_band_member_set_coincident(
1032 __isl_take isl_schedule_tree
*tree
, int pos
, int coincident
)
1036 if (tree
->type
!= isl_schedule_node_band
)
1037 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1038 "not a band node", return isl_schedule_tree_free(tree
));
1039 if (isl_schedule_tree_band_member_get_coincident(tree
, pos
) ==
1042 tree
= isl_schedule_tree_cow(tree
);
1046 tree
->band
= isl_schedule_band_member_set_coincident(tree
->band
, pos
,
1049 return isl_schedule_tree_free(tree
);
1053 /* Is the band tree root marked permutable?
1055 isl_bool
isl_schedule_tree_band_get_permutable(
1056 __isl_keep isl_schedule_tree
*tree
)
1059 return isl_bool_error
;
1061 if (tree
->type
!= isl_schedule_node_band
)
1062 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1063 "not a band node", return isl_bool_error
);
1065 return isl_schedule_band_get_permutable(tree
->band
);
1068 /* Mark the band tree root permutable or not according to "permutable"?
1070 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_permutable(
1071 __isl_take isl_schedule_tree
*tree
, int permutable
)
1075 if (tree
->type
!= isl_schedule_node_band
)
1076 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1077 "not a band node", return isl_schedule_tree_free(tree
));
1078 if (isl_schedule_tree_band_get_permutable(tree
) == permutable
)
1080 tree
= isl_schedule_tree_cow(tree
);
1084 tree
->band
= isl_schedule_band_set_permutable(tree
->band
, permutable
);
1086 return isl_schedule_tree_free(tree
);
1090 /* Return the schedule space of the band tree root.
1092 __isl_give isl_space
*isl_schedule_tree_band_get_space(
1093 __isl_keep isl_schedule_tree
*tree
)
1098 if (tree
->type
!= isl_schedule_node_band
)
1099 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1100 "not a band node", return NULL
);
1102 return isl_schedule_band_get_space(tree
->band
);
1105 /* Intersect the domain of the band schedule of the band tree root
1108 __isl_give isl_schedule_tree
*isl_schedule_tree_band_intersect_domain(
1109 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
1111 if (!tree
|| !domain
)
1114 if (tree
->type
!= isl_schedule_node_band
)
1115 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1116 "not a band node", goto error
);
1118 tree
->band
= isl_schedule_band_intersect_domain(tree
->band
, domain
);
1120 return isl_schedule_tree_free(tree
);
1124 isl_schedule_tree_free(tree
);
1125 isl_union_set_free(domain
);
1129 /* Return the schedule of the band tree root in isolation.
1131 __isl_give isl_multi_union_pw_aff
*isl_schedule_tree_band_get_partial_schedule(
1132 __isl_keep isl_schedule_tree
*tree
)
1137 if (tree
->type
!= isl_schedule_node_band
)
1138 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1139 "not a band node", return NULL
);
1141 return isl_schedule_band_get_partial_schedule(tree
->band
);
1144 /* Replace the schedule of the band tree root by "schedule".
1146 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_partial_schedule(
1147 __isl_take isl_schedule_tree
*tree
,
1148 __isl_take isl_multi_union_pw_aff
*schedule
)
1150 tree
= isl_schedule_tree_cow(tree
);
1151 if (!tree
|| !schedule
)
1154 if (tree
->type
!= isl_schedule_node_band
)
1155 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1156 "not a band node", return NULL
);
1157 tree
->band
= isl_schedule_band_set_partial_schedule(tree
->band
,
1162 isl_schedule_tree_free(tree
);
1163 isl_multi_union_pw_aff_free(schedule
);
1167 /* Return the loop AST generation type for the band member
1168 * of the band tree root at position "pos".
1170 enum isl_ast_loop_type
isl_schedule_tree_band_member_get_ast_loop_type(
1171 __isl_keep isl_schedule_tree
*tree
, int pos
)
1174 return isl_ast_loop_error
;
1176 if (tree
->type
!= isl_schedule_node_band
)
1177 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1178 "not a band node", return isl_ast_loop_error
);
1180 return isl_schedule_band_member_get_ast_loop_type(tree
->band
, pos
);
1183 /* Set the loop AST generation type for the band member of the band tree root
1184 * at position "pos" to "type".
1186 __isl_give isl_schedule_tree
*isl_schedule_tree_band_member_set_ast_loop_type(
1187 __isl_take isl_schedule_tree
*tree
, int pos
,
1188 enum isl_ast_loop_type type
)
1190 tree
= isl_schedule_tree_cow(tree
);
1194 if (tree
->type
!= isl_schedule_node_band
)
1195 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1196 "not a band node", return isl_schedule_tree_free(tree
));
1198 tree
->band
= isl_schedule_band_member_set_ast_loop_type(tree
->band
,
1201 return isl_schedule_tree_free(tree
);
1206 /* Return the loop AST generation type for the band member
1207 * of the band tree root at position "pos" for the isolated part.
1209 enum isl_ast_loop_type
isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1210 __isl_keep isl_schedule_tree
*tree
, int pos
)
1213 return isl_ast_loop_error
;
1215 if (tree
->type
!= isl_schedule_node_band
)
1216 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1217 "not a band node", return isl_ast_loop_error
);
1219 return isl_schedule_band_member_get_isolate_ast_loop_type(tree
->band
,
1223 /* Set the loop AST generation type for the band member of the band tree root
1224 * at position "pos" for the isolated part to "type".
1226 __isl_give isl_schedule_tree
*
1227 isl_schedule_tree_band_member_set_isolate_ast_loop_type(
1228 __isl_take isl_schedule_tree
*tree
, int pos
,
1229 enum isl_ast_loop_type type
)
1231 tree
= isl_schedule_tree_cow(tree
);
1235 if (tree
->type
!= isl_schedule_node_band
)
1236 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1237 "not a band node", return isl_schedule_tree_free(tree
));
1239 tree
->band
= isl_schedule_band_member_set_isolate_ast_loop_type(
1240 tree
->band
, pos
, type
);
1242 return isl_schedule_tree_free(tree
);
1247 /* Return the AST build options associated to the band tree root.
1249 __isl_give isl_union_set
*isl_schedule_tree_band_get_ast_build_options(
1250 __isl_keep isl_schedule_tree
*tree
)
1255 if (tree
->type
!= isl_schedule_node_band
)
1256 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1257 "not a band node", return NULL
);
1259 return isl_schedule_band_get_ast_build_options(tree
->band
);
1262 /* Replace the AST build options associated to band tree root by "options".
1263 * Updated the anchored field if the anchoredness of the root node itself
1266 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_ast_build_options(
1267 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*options
)
1271 tree
= isl_schedule_tree_cow(tree
);
1272 if (!tree
|| !options
)
1275 if (tree
->type
!= isl_schedule_node_band
)
1276 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1277 "not a band node", goto error
);
1279 was_anchored
= isl_schedule_tree_is_anchored(tree
);
1280 tree
->band
= isl_schedule_band_set_ast_build_options(tree
->band
,
1283 return isl_schedule_tree_free(tree
);
1284 if (isl_schedule_tree_is_anchored(tree
) != was_anchored
)
1285 tree
= isl_schedule_tree_update_anchored(tree
);
1289 isl_schedule_tree_free(tree
);
1290 isl_union_set_free(options
);
1294 /* Return the "isolate" option associated to the band tree root of "tree",
1295 * which is assumed to appear at schedule depth "depth".
1297 __isl_give isl_set
*isl_schedule_tree_band_get_ast_isolate_option(
1298 __isl_keep isl_schedule_tree
*tree
, int depth
)
1303 if (tree
->type
!= isl_schedule_node_band
)
1304 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1305 "not a band node", return NULL
);
1307 return isl_schedule_band_get_ast_isolate_option(tree
->band
, depth
);
1310 /* Return the context of the context tree root.
1312 __isl_give isl_set
*isl_schedule_tree_context_get_context(
1313 __isl_keep isl_schedule_tree
*tree
)
1318 if (tree
->type
!= isl_schedule_node_context
)
1319 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1320 "not a context node", return NULL
);
1322 return isl_set_copy(tree
->context
);
1325 /* Return the domain of the domain tree root.
1327 __isl_give isl_union_set
*isl_schedule_tree_domain_get_domain(
1328 __isl_keep isl_schedule_tree
*tree
)
1333 if (tree
->type
!= isl_schedule_node_domain
)
1334 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1335 "not a domain node", return NULL
);
1337 return isl_union_set_copy(tree
->domain
);
1340 /* Replace the domain of domain tree root "tree" by "domain".
1342 __isl_give isl_schedule_tree
*isl_schedule_tree_domain_set_domain(
1343 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
1345 tree
= isl_schedule_tree_cow(tree
);
1346 if (!tree
|| !domain
)
1349 if (tree
->type
!= isl_schedule_node_domain
)
1350 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1351 "not a domain node", goto error
);
1353 isl_union_set_free(tree
->domain
);
1354 tree
->domain
= domain
;
1358 isl_schedule_tree_free(tree
);
1359 isl_union_set_free(domain
);
1363 /* Return the contraction of the expansion tree root.
1365 __isl_give isl_union_pw_multi_aff
*isl_schedule_tree_expansion_get_contraction(
1366 __isl_keep isl_schedule_tree
*tree
)
1371 if (tree
->type
!= isl_schedule_node_expansion
)
1372 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1373 "not an expansion node", return NULL
);
1375 return isl_union_pw_multi_aff_copy(tree
->contraction
);
1378 /* Return the expansion of the expansion tree root.
1380 __isl_give isl_union_map
*isl_schedule_tree_expansion_get_expansion(
1381 __isl_keep isl_schedule_tree
*tree
)
1386 if (tree
->type
!= isl_schedule_node_expansion
)
1387 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1388 "not an expansion node", return NULL
);
1390 return isl_union_map_copy(tree
->expansion
);
1393 /* Replace the contraction and the expansion of the expansion tree root "tree"
1394 * by "contraction" and "expansion".
1396 __isl_give isl_schedule_tree
*
1397 isl_schedule_tree_expansion_set_contraction_and_expansion(
1398 __isl_take isl_schedule_tree
*tree
,
1399 __isl_take isl_union_pw_multi_aff
*contraction
,
1400 __isl_take isl_union_map
*expansion
)
1402 tree
= isl_schedule_tree_cow(tree
);
1403 if (!tree
|| !contraction
|| !expansion
)
1406 if (tree
->type
!= isl_schedule_node_expansion
)
1407 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1408 "not an expansion node", return NULL
);
1410 isl_union_pw_multi_aff_free(tree
->contraction
);
1411 tree
->contraction
= contraction
;
1412 isl_union_map_free(tree
->expansion
);
1413 tree
->expansion
= expansion
;
1417 isl_schedule_tree_free(tree
);
1418 isl_union_pw_multi_aff_free(contraction
);
1419 isl_union_map_free(expansion
);
1423 /* Return the extension of the extension tree root.
1425 __isl_give isl_union_map
*isl_schedule_tree_extension_get_extension(
1426 __isl_take isl_schedule_tree
*tree
)
1431 if (tree
->type
!= isl_schedule_node_extension
)
1432 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1433 "not an extension node", return NULL
);
1435 return isl_union_map_copy(tree
->extension
);
1438 /* Replace the extension of extension tree root "tree" by "extension".
1440 __isl_give isl_schedule_tree
*isl_schedule_tree_extension_set_extension(
1441 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_map
*extension
)
1443 tree
= isl_schedule_tree_cow(tree
);
1444 if (!tree
|| !extension
)
1447 if (tree
->type
!= isl_schedule_node_extension
)
1448 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1449 "not an extension node", return NULL
);
1450 isl_union_map_free(tree
->extension
);
1451 tree
->extension
= extension
;
1455 isl_schedule_tree_free(tree
);
1456 isl_union_map_free(extension
);
1460 /* Return the filter of the filter tree root.
1462 __isl_give isl_union_set
*isl_schedule_tree_filter_get_filter(
1463 __isl_keep isl_schedule_tree
*tree
)
1468 if (tree
->type
!= isl_schedule_node_filter
)
1469 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1470 "not a filter node", return NULL
);
1472 return isl_union_set_copy(tree
->filter
);
1475 /* Replace the filter of the filter tree root by "filter".
1477 __isl_give isl_schedule_tree
*isl_schedule_tree_filter_set_filter(
1478 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
1480 tree
= isl_schedule_tree_cow(tree
);
1481 if (!tree
|| !filter
)
1484 if (tree
->type
!= isl_schedule_node_filter
)
1485 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1486 "not a filter node", return NULL
);
1488 isl_union_set_free(tree
->filter
);
1489 tree
->filter
= filter
;
1493 isl_schedule_tree_free(tree
);
1494 isl_union_set_free(filter
);
1498 /* Return the guard of the guard tree root.
1500 __isl_give isl_set
*isl_schedule_tree_guard_get_guard(
1501 __isl_take isl_schedule_tree
*tree
)
1506 if (tree
->type
!= isl_schedule_node_guard
)
1507 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1508 "not a guard node", return NULL
);
1510 return isl_set_copy(tree
->guard
);
1513 /* Return the mark identifier of the mark tree root "tree".
1515 __isl_give isl_id
*isl_schedule_tree_mark_get_id(
1516 __isl_keep isl_schedule_tree
*tree
)
1521 if (tree
->type
!= isl_schedule_node_mark
)
1522 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1523 "not a mark node", return NULL
);
1525 return isl_id_copy(tree
->mark
);
1528 /* Set dim to the range dimension of "map" and abort the search.
1530 static isl_stat
set_range_dim(__isl_take isl_map
*map
, void *user
)
1532 isl_size
*dim
= user
;
1534 *dim
= isl_map_dim(map
, isl_dim_out
);
1537 return isl_stat_error
;
1540 /* Return the dimension of the range of "umap".
1541 * "umap" is assumed not to be empty and
1542 * all maps inside "umap" are assumed to have the same range.
1544 * We extract the range dimension from the first map in "umap".
1546 static isl_size
range_dim(__isl_keep isl_union_map
*umap
)
1548 isl_size dim
= isl_size_error
;
1551 n
= isl_union_map_n_map(umap
);
1553 return isl_size_error
;
1555 isl_die(isl_union_map_get_ctx(umap
), isl_error_internal
,
1556 "unexpected empty input", return isl_size_error
);
1558 isl_union_map_foreach_map(umap
, &set_range_dim
, &dim
);
1563 /* Append an "extra" number of zeros to the range of "umap" and
1564 * return the result.
1566 static __isl_give isl_union_map
*append_range(__isl_take isl_union_map
*umap
,
1572 isl_union_pw_multi_aff
*suffix
;
1573 isl_union_map
*universe
;
1574 isl_union_map
*suffix_umap
;
1576 universe
= isl_union_map_universe(isl_union_map_copy(umap
));
1577 dom
= isl_union_map_domain(universe
);
1578 space
= isl_union_set_get_space(dom
);
1579 space
= isl_space_set_from_params(space
);
1580 space
= isl_space_add_dims(space
, isl_dim_set
, extra
);
1581 mv
= isl_multi_val_zero(space
);
1583 suffix
= isl_union_pw_multi_aff_multi_val_on_domain(dom
, mv
);
1584 suffix_umap
= isl_union_map_from_union_pw_multi_aff(suffix
);
1585 umap
= isl_union_map_flat_range_product(umap
, suffix_umap
);
1590 /* Should we skip the root of "tree" while looking for the first
1591 * descendant with schedule information?
1592 * That is, is it impossible to derive any information about
1593 * the iteration domain from this node?
1595 * We do not want to skip leaf or error nodes because there is
1596 * no point in looking any deeper from these nodes.
1597 * We can only extract partial iteration domain information
1598 * from an extension node, but extension nodes are not supported
1599 * by the caller and it will error out on them.
1601 static isl_bool
domain_less(__isl_keep isl_schedule_tree
*tree
)
1603 enum isl_schedule_node_type type
;
1605 type
= isl_schedule_tree_get_type(tree
);
1607 case isl_schedule_node_band
:
1608 return isl_schedule_tree_band_n_member(tree
) == 0;
1609 case isl_schedule_node_context
:
1610 case isl_schedule_node_guard
:
1611 case isl_schedule_node_mark
:
1612 return isl_bool_true
;
1613 case isl_schedule_node_leaf
:
1614 case isl_schedule_node_error
:
1615 case isl_schedule_node_domain
:
1616 case isl_schedule_node_expansion
:
1617 case isl_schedule_node_extension
:
1618 case isl_schedule_node_filter
:
1619 case isl_schedule_node_set
:
1620 case isl_schedule_node_sequence
:
1621 return isl_bool_false
;
1624 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1625 "unhandled case", return isl_bool_error
);
1628 /* Move down to the first descendant of "tree" that contains any schedule
1629 * information or return "leaf" if there is no such descendant.
1631 __isl_give isl_schedule_tree
*isl_schedule_tree_first_schedule_descendant(
1632 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_tree
*leaf
)
1636 while ((down
= domain_less(tree
)) == isl_bool_true
) {
1637 if (!isl_schedule_tree_has_children(tree
)) {
1638 isl_schedule_tree_free(tree
);
1639 return isl_schedule_tree_copy(leaf
);
1641 tree
= isl_schedule_tree_child(tree
, 0);
1645 return isl_schedule_tree_free(tree
);
1650 static __isl_give isl_union_map
*subtree_schedule_extend(
1651 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
);
1653 /* Extend the schedule map "outer" with the subtree schedule
1654 * of the (single) child of "tree", if any.
1656 * If "tree" does not have any descendants (apart from those that
1657 * do not carry any schedule information), then we simply return "outer".
1658 * Otherwise, we extend the schedule map "outer" with the subtree schedule
1659 * of the single child.
1661 static __isl_give isl_union_map
*subtree_schedule_extend_child(
1662 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1664 isl_schedule_tree
*child
;
1668 return isl_union_map_free(outer
);
1669 if (!isl_schedule_tree_has_children(tree
))
1671 child
= isl_schedule_tree_get_child(tree
, 0);
1673 return isl_union_map_free(outer
);
1674 res
= subtree_schedule_extend(child
, outer
);
1675 isl_schedule_tree_free(child
);
1679 /* Extract the parameter space from one of the children of "tree",
1680 * which are assumed to be filters.
1682 static __isl_give isl_space
*extract_space_from_filter_child(
1683 __isl_keep isl_schedule_tree
*tree
)
1687 isl_schedule_tree
*child
;
1689 child
= isl_schedule_tree_list_get_schedule_tree(tree
->children
, 0);
1690 dom
= isl_schedule_tree_filter_get_filter(child
);
1691 space
= isl_union_set_get_space(dom
);
1692 isl_union_set_free(dom
);
1693 isl_schedule_tree_free(child
);
1698 /* Extend the schedule map "outer" with the subtree schedule
1699 * of a set or sequence node.
1701 * The schedule for the set or sequence node itself is composed of
1702 * pieces of the form
1710 * The first form is used if there is only a single child or
1711 * if the current node is a set node and the schedule_separate_components
1712 * option is not set.
1714 * Each of the pieces above is extended with the subtree schedule of
1715 * the child of the corresponding filter, if any, padded with zeros
1716 * to ensure that all pieces have the same range dimension.
1718 static __isl_give isl_union_map
*subtree_schedule_extend_from_children(
1719 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1728 isl_union_map
*umap
;
1730 n
= isl_schedule_tree_n_children(tree
);
1732 return isl_union_map_free(outer
);
1734 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1735 "missing children", return isl_union_map_free(outer
));
1737 ctx
= isl_schedule_tree_get_ctx(tree
);
1738 separate
= n
> 1 && (tree
->type
== isl_schedule_node_sequence
||
1739 isl_options_get_schedule_separate_components(ctx
));
1741 space
= isl_space_params_alloc(ctx
, 0);
1743 umap
= isl_union_map_empty(isl_space_copy(space
));
1744 space
= isl_space_set_from_params(space
);
1746 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1747 v
= isl_val_zero(ctx
);
1749 mv
= isl_multi_val_zero(space
);
1751 dim
= isl_multi_val_dim(mv
, isl_dim_set
);
1753 umap
= isl_union_map_free(umap
);
1754 for (i
= 0; i
< n
; ++i
) {
1755 isl_multi_val
*mv_copy
;
1756 isl_union_pw_multi_aff
*upma
;
1757 isl_union_map
*umap_i
;
1759 isl_schedule_tree
*child
;
1763 child
= isl_schedule_tree_list_get_schedule_tree(
1765 dom
= isl_schedule_tree_filter_get_filter(child
);
1768 mv
= isl_multi_val_set_val(mv
, 0, isl_val_copy(v
));
1769 v
= isl_val_add_ui(v
, 1);
1771 mv_copy
= isl_multi_val_copy(mv
);
1772 space
= isl_union_set_get_space(dom
);
1773 mv_copy
= isl_multi_val_align_params(mv_copy
, space
);
1774 upma
= isl_union_pw_multi_aff_multi_val_on_domain(dom
, mv_copy
);
1775 umap_i
= isl_union_map_from_union_pw_multi_aff(upma
);
1776 umap_i
= isl_union_map_flat_range_product(
1777 isl_union_map_copy(outer
), umap_i
);
1778 umap_i
= subtree_schedule_extend_child(child
, umap_i
);
1779 isl_schedule_tree_free(child
);
1781 empty
= isl_union_map_is_empty(umap_i
);
1783 umap_i
= isl_union_map_free(umap_i
);
1785 isl_union_map_free(umap_i
);
1789 dim_i
= range_dim(umap_i
);
1791 umap
= isl_union_map_free(umap
);
1792 } else if (dim
< dim_i
) {
1793 umap
= append_range(umap
, dim_i
- dim
);
1795 } else if (dim_i
< dim
) {
1796 umap_i
= append_range(umap_i
, dim
- dim_i
);
1798 umap
= isl_union_map_union(umap
, umap_i
);
1802 isl_multi_val_free(mv
);
1803 isl_union_map_free(outer
);
1808 /* Extend the schedule map "outer" with the subtree schedule of "tree".
1810 * If the root of the tree is a set or a sequence, then we extend
1811 * the schedule map in subtree_schedule_extend_from_children.
1812 * Otherwise, we extend the schedule map with the partial schedule
1813 * corresponding to the root of the tree and then continue with
1814 * the single child of this root.
1815 * In the special case of an expansion, the schedule map is "extended"
1816 * by applying the expansion to the domain of the schedule map.
1818 static __isl_give isl_union_map
*subtree_schedule_extend(
1819 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1821 isl_multi_union_pw_aff
*mupa
;
1822 isl_union_map
*umap
;
1823 isl_union_set
*domain
;
1828 switch (tree
->type
) {
1829 case isl_schedule_node_error
:
1830 return isl_union_map_free(outer
);
1831 case isl_schedule_node_extension
:
1832 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1833 "cannot construct subtree schedule of tree "
1834 "with extension nodes",
1835 return isl_union_map_free(outer
));
1836 case isl_schedule_node_context
:
1837 case isl_schedule_node_guard
:
1838 case isl_schedule_node_mark
:
1839 return subtree_schedule_extend_child(tree
, outer
);
1840 case isl_schedule_node_band
:
1841 if (isl_schedule_tree_band_n_member(tree
) == 0)
1842 return subtree_schedule_extend_child(tree
, outer
);
1843 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1844 umap
= isl_union_map_from_multi_union_pw_aff(mupa
);
1845 outer
= isl_union_map_flat_range_product(outer
, umap
);
1846 umap
= subtree_schedule_extend_child(tree
, outer
);
1848 case isl_schedule_node_domain
:
1849 domain
= isl_schedule_tree_domain_get_domain(tree
);
1850 umap
= isl_union_map_from_domain(domain
);
1851 outer
= isl_union_map_flat_range_product(outer
, umap
);
1852 umap
= subtree_schedule_extend_child(tree
, outer
);
1854 case isl_schedule_node_expansion
:
1855 umap
= isl_schedule_tree_expansion_get_expansion(tree
);
1856 outer
= isl_union_map_apply_domain(outer
, umap
);
1857 umap
= subtree_schedule_extend_child(tree
, outer
);
1859 case isl_schedule_node_filter
:
1860 domain
= isl_schedule_tree_filter_get_filter(tree
);
1861 umap
= isl_union_map_from_domain(domain
);
1862 outer
= isl_union_map_flat_range_product(outer
, umap
);
1863 umap
= subtree_schedule_extend_child(tree
, outer
);
1865 case isl_schedule_node_leaf
:
1866 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1867 "leaf node should be handled by caller", return NULL
);
1868 case isl_schedule_node_set
:
1869 case isl_schedule_node_sequence
:
1870 umap
= subtree_schedule_extend_from_children(tree
, outer
);
1877 static __isl_give isl_union_set
*initial_domain(
1878 __isl_keep isl_schedule_tree
*tree
);
1880 /* Extract a universe domain from the children of the tree root "tree",
1881 * which is a set or sequence, meaning that its children are filters.
1882 * In particular, return the union of the universes of the filters.
1884 static __isl_give isl_union_set
*initial_domain_from_children(
1885 __isl_keep isl_schedule_tree
*tree
)
1889 isl_union_set
*domain
;
1891 n
= isl_schedule_tree_n_children(tree
);
1895 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1896 "missing children", return NULL
);
1898 space
= extract_space_from_filter_child(tree
);
1899 domain
= isl_union_set_empty(space
);
1901 for (i
= 0; i
< n
; ++i
) {
1902 isl_schedule_tree
*child
;
1903 isl_union_set
*domain_i
;
1905 child
= isl_schedule_tree_get_child(tree
, i
);
1906 domain_i
= initial_domain(child
);
1907 domain
= isl_union_set_union(domain
, domain_i
);
1908 isl_schedule_tree_free(child
);
1914 /* Extract a universe domain from the tree root "tree".
1915 * The caller is responsible for making sure that this node
1916 * would not be skipped by isl_schedule_tree_first_schedule_descendant
1917 * and that it is not a leaf node.
1919 static __isl_give isl_union_set
*initial_domain(
1920 __isl_keep isl_schedule_tree
*tree
)
1922 isl_multi_union_pw_aff
*mupa
;
1923 isl_union_set
*domain
;
1929 switch (tree
->type
) {
1930 case isl_schedule_node_error
:
1932 case isl_schedule_node_context
:
1933 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1934 "context node should be handled by caller",
1936 case isl_schedule_node_guard
:
1937 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1938 "guard node should be handled by caller",
1940 case isl_schedule_node_mark
:
1941 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1942 "mark node should be handled by caller",
1944 case isl_schedule_node_extension
:
1945 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1946 "cannot construct subtree schedule of tree "
1947 "with extension nodes", return NULL
);
1948 case isl_schedule_node_band
:
1949 if (isl_schedule_tree_band_n_member(tree
) == 0)
1950 isl_die(isl_schedule_tree_get_ctx(tree
),
1952 "0D band should be handled by caller",
1954 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1955 domain
= isl_multi_union_pw_aff_domain(mupa
);
1956 domain
= isl_union_set_universe(domain
);
1958 case isl_schedule_node_domain
:
1959 domain
= isl_schedule_tree_domain_get_domain(tree
);
1960 domain
= isl_union_set_universe(domain
);
1962 case isl_schedule_node_expansion
:
1963 exp
= isl_schedule_tree_expansion_get_expansion(tree
);
1964 exp
= isl_union_map_universe(exp
);
1965 domain
= isl_union_map_domain(exp
);
1967 case isl_schedule_node_filter
:
1968 domain
= isl_schedule_tree_filter_get_filter(tree
);
1969 domain
= isl_union_set_universe(domain
);
1971 case isl_schedule_node_leaf
:
1972 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1973 "leaf node should be handled by caller", return NULL
);
1974 case isl_schedule_node_set
:
1975 case isl_schedule_node_sequence
:
1976 domain
= initial_domain_from_children(tree
);
1983 /* Return the subtree schedule of a node that contains some schedule
1984 * information, i.e., a node that would not be skipped by
1985 * isl_schedule_tree_first_schedule_descendant and that is not a leaf.
1987 * If the tree contains any expansions, then the returned subtree
1988 * schedule is formulated in terms of the expanded domains.
1989 * The tree is not allowed to contain any extension nodes.
1991 * We start with an initial zero-dimensional subtree schedule based
1992 * on the domain information in the root node and then extend it
1993 * based on the schedule information in the root node and its descendants.
1995 __isl_give isl_union_map
*isl_schedule_tree_get_subtree_schedule_union_map(
1996 __isl_keep isl_schedule_tree
*tree
)
1998 isl_union_set
*domain
;
1999 isl_union_map
*umap
;
2001 domain
= initial_domain(tree
);
2002 umap
= isl_union_map_from_domain(domain
);
2003 return subtree_schedule_extend(tree
, umap
);
2006 /* Multiply the partial schedule of the band root node of "tree"
2007 * with the factors in "mv".
2009 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale(
2010 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
2014 if (tree
->type
!= isl_schedule_node_band
)
2015 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2016 "not a band node", goto error
);
2018 tree
= isl_schedule_tree_cow(tree
);
2022 tree
->band
= isl_schedule_band_scale(tree
->band
, mv
);
2024 return isl_schedule_tree_free(tree
);
2028 isl_schedule_tree_free(tree
);
2029 isl_multi_val_free(mv
);
2033 /* Divide the partial schedule of the band root node of "tree"
2034 * by the factors in "mv".
2036 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale_down(
2037 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
2041 if (tree
->type
!= isl_schedule_node_band
)
2042 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2043 "not a band node", goto error
);
2045 tree
= isl_schedule_tree_cow(tree
);
2049 tree
->band
= isl_schedule_band_scale_down(tree
->band
, mv
);
2051 return isl_schedule_tree_free(tree
);
2055 isl_schedule_tree_free(tree
);
2056 isl_multi_val_free(mv
);
2060 /* Reduce the partial schedule of the band root node of "tree"
2061 * modulo the factors in "mv".
2063 __isl_give isl_schedule_tree
*isl_schedule_tree_band_mod(
2064 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
2068 if (tree
->type
!= isl_schedule_node_band
)
2069 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2070 "not a band node", goto error
);
2072 tree
= isl_schedule_tree_cow(tree
);
2076 tree
->band
= isl_schedule_band_mod(tree
->band
, mv
);
2078 return isl_schedule_tree_free(tree
);
2082 isl_schedule_tree_free(tree
);
2083 isl_multi_val_free(mv
);
2087 /* Shift the partial schedule of the band root node of "tree" by "shift".
2089 __isl_give isl_schedule_tree
*isl_schedule_tree_band_shift(
2090 __isl_take isl_schedule_tree
*tree
,
2091 __isl_take isl_multi_union_pw_aff
*shift
)
2093 if (!tree
|| !shift
)
2095 if (tree
->type
!= isl_schedule_node_band
)
2096 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2097 "not a band node", goto error
);
2099 tree
= isl_schedule_tree_cow(tree
);
2103 tree
->band
= isl_schedule_band_shift(tree
->band
, shift
);
2105 return isl_schedule_tree_free(tree
);
2109 isl_schedule_tree_free(tree
);
2110 isl_multi_union_pw_aff_free(shift
);
2114 /* Given two trees with sequence roots, replace the child at position
2115 * "pos" of "tree" with the children of "child".
2117 __isl_give isl_schedule_tree
*isl_schedule_tree_sequence_splice(
2118 __isl_take isl_schedule_tree
*tree
, int pos
,
2119 __isl_take isl_schedule_tree
*child
)
2122 isl_schedule_tree_list
*list1
, *list2
;
2124 tree
= isl_schedule_tree_cow(tree
);
2125 if (!tree
|| !child
)
2127 if (isl_schedule_tree_get_type(tree
) != isl_schedule_node_sequence
)
2128 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2129 "not a sequence node", goto error
);
2130 n
= isl_schedule_tree_n_children(tree
);
2131 if (pos
< 0 || pos
>= n
)
2132 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2133 "position out of bounds", goto error
);
2134 if (isl_schedule_tree_get_type(child
) != isl_schedule_node_sequence
)
2135 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2136 "not a sequence node", goto error
);
2138 list1
= isl_schedule_tree_list_copy(tree
->children
);
2139 list1
= isl_schedule_tree_list_drop(list1
, pos
, n
- pos
);
2140 list2
= isl_schedule_tree_list_copy(tree
->children
);
2141 list2
= isl_schedule_tree_list_drop(list2
, 0, pos
+ 1);
2142 list1
= isl_schedule_tree_list_concat(list1
,
2143 isl_schedule_tree_list_copy(child
->children
));
2144 list1
= isl_schedule_tree_list_concat(list1
, list2
);
2146 isl_schedule_tree_free(tree
);
2147 isl_schedule_tree_free(child
);
2148 return isl_schedule_tree_from_children(isl_schedule_node_sequence
,
2151 isl_schedule_tree_free(tree
);
2152 isl_schedule_tree_free(child
);
2156 /* Tile the band root node of "tree" with tile sizes "sizes".
2158 * We duplicate the band node, change the schedule of one of them
2159 * to the tile schedule and the other to the point schedule and then
2160 * attach the point band as a child to the tile band.
2162 __isl_give isl_schedule_tree
*isl_schedule_tree_band_tile(
2163 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*sizes
)
2165 isl_schedule_tree
*child
= NULL
;
2167 if (!tree
|| !sizes
)
2169 if (tree
->type
!= isl_schedule_node_band
)
2170 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2171 "not a band node", goto error
);
2173 child
= isl_schedule_tree_copy(tree
);
2174 tree
= isl_schedule_tree_cow(tree
);
2175 child
= isl_schedule_tree_cow(child
);
2176 if (!tree
|| !child
)
2179 tree
->band
= isl_schedule_band_tile(tree
->band
,
2180 isl_multi_val_copy(sizes
));
2183 child
->band
= isl_schedule_band_point(child
->band
, tree
->band
, sizes
);
2185 child
= isl_schedule_tree_free(child
);
2187 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
2191 isl_schedule_tree_free(child
);
2192 isl_schedule_tree_free(tree
);
2193 isl_multi_val_free(sizes
);
2197 /* Given an isolate AST generation option "isolate" for a band of size pos + n,
2198 * return the corresponding option for a band covering the first "pos"
2201 * The input isolate option is of the form
2203 * isolate[[flattened outer bands] -> [pos; n]]
2205 * The output isolate option is of the form
2207 * isolate[[flattened outer bands] -> [pos]]
2209 static __isl_give isl_set
*isolate_initial(__isl_keep isl_set
*isolate
,
2215 isolate
= isl_set_copy(isolate
);
2216 id
= isl_set_get_tuple_id(isolate
);
2217 map
= isl_set_unwrap(isolate
);
2218 map
= isl_map_project_out(map
, isl_dim_out
, pos
, n
);
2219 isolate
= isl_map_wrap(map
);
2220 isolate
= isl_set_set_tuple_id(isolate
, id
);
2225 /* Given an isolate AST generation option "isolate" for a band of size pos + n,
2226 * return the corresponding option for a band covering the final "n"
2227 * members within a band covering the first "pos" members.
2229 * The input isolate option is of the form
2231 * isolate[[flattened outer bands] -> [pos; n]]
2233 * The output isolate option is of the form
2235 * isolate[[flattened outer bands; pos] -> [n]]
2238 * The range is first split into
2240 * isolate[[flattened outer bands] -> [[pos] -> [n]]]
2242 * and then the first pos members are moved to the domain
2244 * isolate[[[flattened outer bands] -> [pos]] -> [n]]
2246 * after which the domain is flattened to obtain the desired output.
2248 static __isl_give isl_set
*isolate_final(__isl_keep isl_set
*isolate
,
2253 isl_multi_aff
*ma1
, *ma2
;
2256 isolate
= isl_set_copy(isolate
);
2257 id
= isl_set_get_tuple_id(isolate
);
2258 map
= isl_set_unwrap(isolate
);
2259 space
= isl_space_range(isl_map_get_space(map
));
2260 ma1
= isl_multi_aff_project_out_map(isl_space_copy(space
),
2261 isl_dim_set
, pos
, n
);
2262 ma2
= isl_multi_aff_project_out_map(space
, isl_dim_set
, 0, pos
);
2263 ma1
= isl_multi_aff_range_product(ma1
, ma2
);
2264 map
= isl_map_apply_range(map
, isl_map_from_multi_aff(ma1
));
2265 map
= isl_map_uncurry(map
);
2266 map
= isl_map_flatten_domain(map
);
2267 isolate
= isl_map_wrap(map
);
2268 isolate
= isl_set_set_tuple_id(isolate
, id
);
2273 /* Split the band root node of "tree" into two nested band nodes,
2274 * one with the first "pos" dimensions and
2275 * one with the remaining dimensions.
2276 * The tree is itself positioned at schedule depth "depth".
2278 * The loop AST generation type options and the isolate option
2279 * are split over the two band nodes.
2281 __isl_give isl_schedule_tree
*isl_schedule_tree_band_split(
2282 __isl_take isl_schedule_tree
*tree
, int pos
, int depth
)
2285 isl_set
*isolate
, *tree_isolate
, *child_isolate
;
2286 isl_schedule_tree
*child
;
2290 if (tree
->type
!= isl_schedule_node_band
)
2291 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2292 "not a band node", return isl_schedule_tree_free(tree
));
2294 n
= isl_schedule_tree_band_n_member(tree
);
2295 if (pos
< 0 || pos
> n
)
2296 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2297 "position out of bounds",
2298 return isl_schedule_tree_free(tree
));
2300 child
= isl_schedule_tree_copy(tree
);
2301 tree
= isl_schedule_tree_cow(tree
);
2302 child
= isl_schedule_tree_cow(child
);
2303 if (!tree
|| !child
)
2306 isolate
= isl_schedule_tree_band_get_ast_isolate_option(tree
, depth
);
2307 tree_isolate
= isolate_initial(isolate
, pos
, n
- pos
);
2308 child_isolate
= isolate_final(isolate
, pos
, n
- pos
);
2309 child
->band
= isl_schedule_band_drop(child
->band
, 0, pos
);
2310 child
->band
= isl_schedule_band_replace_ast_build_option(child
->band
,
2311 isl_set_copy(isolate
), child_isolate
);
2312 tree
->band
= isl_schedule_band_drop(tree
->band
, pos
, n
- pos
);
2313 tree
->band
= isl_schedule_band_replace_ast_build_option(tree
->band
,
2314 isl_set_copy(isolate
), tree_isolate
);
2315 isl_set_free(isolate
);
2316 if (!child
->band
|| !tree
->band
)
2319 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
2323 isl_schedule_tree_free(child
);
2324 isl_schedule_tree_free(tree
);
2328 /* Attach "tree2" at each of the leaves of "tree1".
2330 * If "tree1" does not have any explicit children, then make "tree2"
2331 * its single child. Otherwise, attach "tree2" to the leaves of
2332 * each of the children of "tree1".
2334 __isl_give isl_schedule_tree
*isl_schedule_tree_append_to_leaves(
2335 __isl_take isl_schedule_tree
*tree1
,
2336 __isl_take isl_schedule_tree
*tree2
)
2340 if (!tree1
|| !tree2
)
2342 n
= isl_schedule_tree_n_children(tree1
);
2344 isl_schedule_tree_list
*list
;
2345 list
= isl_schedule_tree_list_from_schedule_tree(tree2
);
2346 tree1
= isl_schedule_tree_set_children(tree1
, list
);
2349 for (i
= 0; i
< n
; ++i
) {
2350 isl_schedule_tree
*child
;
2352 child
= isl_schedule_tree_get_child(tree1
, i
);
2353 child
= isl_schedule_tree_append_to_leaves(child
,
2354 isl_schedule_tree_copy(tree2
));
2355 tree1
= isl_schedule_tree_replace_child(tree1
, i
, child
);
2358 isl_schedule_tree_free(tree2
);
2361 isl_schedule_tree_free(tree1
);
2362 isl_schedule_tree_free(tree2
);
2366 /* Reset the user pointer on all identifiers of parameters and tuples
2367 * in the root of "tree".
2369 __isl_give isl_schedule_tree
*isl_schedule_tree_reset_user(
2370 __isl_take isl_schedule_tree
*tree
)
2372 if (isl_schedule_tree_is_leaf(tree
))
2375 tree
= isl_schedule_tree_cow(tree
);
2379 switch (tree
->type
) {
2380 case isl_schedule_node_error
:
2381 return isl_schedule_tree_free(tree
);
2382 case isl_schedule_node_band
:
2383 tree
->band
= isl_schedule_band_reset_user(tree
->band
);
2385 return isl_schedule_tree_free(tree
);
2387 case isl_schedule_node_context
:
2388 tree
->context
= isl_set_reset_user(tree
->context
);
2390 return isl_schedule_tree_free(tree
);
2392 case isl_schedule_node_domain
:
2393 tree
->domain
= isl_union_set_reset_user(tree
->domain
);
2395 return isl_schedule_tree_free(tree
);
2397 case isl_schedule_node_expansion
:
2399 isl_union_pw_multi_aff_reset_user(tree
->contraction
);
2400 tree
->expansion
= isl_union_map_reset_user(tree
->expansion
);
2401 if (!tree
->contraction
|| !tree
->expansion
)
2402 return isl_schedule_tree_free(tree
);
2404 case isl_schedule_node_extension
:
2405 tree
->extension
= isl_union_map_reset_user(tree
->extension
);
2406 if (!tree
->extension
)
2407 return isl_schedule_tree_free(tree
);
2409 case isl_schedule_node_filter
:
2410 tree
->filter
= isl_union_set_reset_user(tree
->filter
);
2412 return isl_schedule_tree_free(tree
);
2414 case isl_schedule_node_guard
:
2415 tree
->guard
= isl_set_reset_user(tree
->guard
);
2417 return isl_schedule_tree_free(tree
);
2419 case isl_schedule_node_leaf
:
2420 case isl_schedule_node_mark
:
2421 case isl_schedule_node_sequence
:
2422 case isl_schedule_node_set
:
2429 /* Align the parameters of the root of "tree" to those of "space".
2431 __isl_give isl_schedule_tree
*isl_schedule_tree_align_params(
2432 __isl_take isl_schedule_tree
*tree
, __isl_take isl_space
*space
)
2437 if (isl_schedule_tree_is_leaf(tree
)) {
2438 isl_space_free(space
);
2442 tree
= isl_schedule_tree_cow(tree
);
2446 switch (tree
->type
) {
2447 case isl_schedule_node_error
:
2449 case isl_schedule_node_band
:
2450 tree
->band
= isl_schedule_band_align_params(tree
->band
, space
);
2452 return isl_schedule_tree_free(tree
);
2454 case isl_schedule_node_context
:
2455 tree
->context
= isl_set_align_params(tree
->context
, space
);
2457 return isl_schedule_tree_free(tree
);
2459 case isl_schedule_node_domain
:
2460 tree
->domain
= isl_union_set_align_params(tree
->domain
, space
);
2462 return isl_schedule_tree_free(tree
);
2464 case isl_schedule_node_expansion
:
2466 isl_union_pw_multi_aff_align_params(tree
->contraction
,
2467 isl_space_copy(space
));
2468 tree
->expansion
= isl_union_map_align_params(tree
->expansion
,
2470 if (!tree
->contraction
|| !tree
->expansion
)
2471 return isl_schedule_tree_free(tree
);
2473 case isl_schedule_node_extension
:
2474 tree
->extension
= isl_union_map_align_params(tree
->extension
,
2476 if (!tree
->extension
)
2477 return isl_schedule_tree_free(tree
);
2479 case isl_schedule_node_filter
:
2480 tree
->filter
= isl_union_set_align_params(tree
->filter
, space
);
2482 return isl_schedule_tree_free(tree
);
2484 case isl_schedule_node_guard
:
2485 tree
->guard
= isl_set_align_params(tree
->guard
, space
);
2487 return isl_schedule_tree_free(tree
);
2489 case isl_schedule_node_leaf
:
2490 case isl_schedule_node_mark
:
2491 case isl_schedule_node_sequence
:
2492 case isl_schedule_node_set
:
2493 isl_space_free(space
);
2499 isl_space_free(space
);
2500 isl_schedule_tree_free(tree
);
2504 /* Does "tree" involve the iteration domain?
2505 * That is, does it need to be modified
2506 * by isl_schedule_tree_pullback_union_pw_multi_aff?
2508 static int involves_iteration_domain(__isl_keep isl_schedule_tree
*tree
)
2513 switch (tree
->type
) {
2514 case isl_schedule_node_error
:
2516 case isl_schedule_node_band
:
2517 case isl_schedule_node_domain
:
2518 case isl_schedule_node_expansion
:
2519 case isl_schedule_node_extension
:
2520 case isl_schedule_node_filter
:
2522 case isl_schedule_node_context
:
2523 case isl_schedule_node_leaf
:
2524 case isl_schedule_node_guard
:
2525 case isl_schedule_node_mark
:
2526 case isl_schedule_node_sequence
:
2527 case isl_schedule_node_set
:
2531 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2532 "unhandled case", return -1);
2535 /* Compute the pullback of the root node of "tree" by the function
2536 * represented by "upma".
2537 * In other words, plug in "upma" in the iteration domains of
2538 * the root node of "tree".
2539 * We currently do not handle expansion nodes.
2541 * We first check if the root node involves any iteration domains.
2542 * If so, we handle the specific cases.
2544 __isl_give isl_schedule_tree
*isl_schedule_tree_pullback_union_pw_multi_aff(
2545 __isl_take isl_schedule_tree
*tree
,
2546 __isl_take isl_union_pw_multi_aff
*upma
)
2553 involves
= involves_iteration_domain(tree
);
2557 isl_union_pw_multi_aff_free(upma
);
2561 tree
= isl_schedule_tree_cow(tree
);
2565 if (tree
->type
== isl_schedule_node_band
) {
2566 tree
->band
= isl_schedule_band_pullback_union_pw_multi_aff(
2569 return isl_schedule_tree_free(tree
);
2570 } else if (tree
->type
== isl_schedule_node_domain
) {
2572 isl_union_set_preimage_union_pw_multi_aff(tree
->domain
,
2575 return isl_schedule_tree_free(tree
);
2576 } else if (tree
->type
== isl_schedule_node_expansion
) {
2577 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_unsupported
,
2578 "cannot pullback expansion node", goto error
);
2579 } else if (tree
->type
== isl_schedule_node_extension
) {
2581 isl_union_map_preimage_range_union_pw_multi_aff(
2582 tree
->extension
, upma
);
2583 if (!tree
->extension
)
2584 return isl_schedule_tree_free(tree
);
2585 } else if (tree
->type
== isl_schedule_node_filter
) {
2587 isl_union_set_preimage_union_pw_multi_aff(tree
->filter
,
2590 return isl_schedule_tree_free(tree
);
2595 isl_union_pw_multi_aff_free(upma
);
2596 isl_schedule_tree_free(tree
);
2600 /* Compute the gist of the band tree root with respect to "context".
2602 __isl_give isl_schedule_tree
*isl_schedule_tree_band_gist(
2603 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*context
)
2607 if (tree
->type
!= isl_schedule_node_band
)
2608 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
2609 "not a band node", goto error
);
2610 tree
= isl_schedule_tree_cow(tree
);
2614 tree
->band
= isl_schedule_band_gist(tree
->band
, context
);
2616 return isl_schedule_tree_free(tree
);
2619 isl_union_set_free(context
);
2620 isl_schedule_tree_free(tree
);
2624 /* Are any members in "band" marked coincident?
2626 static isl_bool
any_coincident(__isl_keep isl_schedule_band
*band
)
2630 n
= isl_schedule_band_n_member(band
);
2631 for (i
= 0; i
< n
; ++i
) {
2632 isl_bool coincident
;
2634 coincident
= isl_schedule_band_member_get_coincident(band
, i
);
2635 if (coincident
< 0 || coincident
)
2639 return isl_bool_false
;
2642 /* Print the band node "band" to "p".
2644 * The permutable and coincident properties are only printed if they
2645 * are different from the defaults.
2646 * The coincident property is always printed in YAML flow style.
2648 static __isl_give isl_printer
*print_tree_band(__isl_take isl_printer
*p
,
2649 __isl_keep isl_schedule_band
*band
)
2651 isl_union_set
*options
;
2653 isl_bool coincident
;
2655 p
= isl_printer_print_str(p
, "schedule");
2656 p
= isl_printer_yaml_next(p
);
2657 p
= isl_printer_print_str(p
, "\"");
2658 p
= isl_printer_print_multi_union_pw_aff(p
, band
->mupa
);
2659 p
= isl_printer_print_str(p
, "\"");
2660 if (isl_schedule_band_get_permutable(band
)) {
2661 p
= isl_printer_yaml_next(p
);
2662 p
= isl_printer_print_str(p
, "permutable");
2663 p
= isl_printer_yaml_next(p
);
2664 p
= isl_printer_print_int(p
, 1);
2666 coincident
= any_coincident(band
);
2668 return isl_printer_free(p
);
2673 p
= isl_printer_yaml_next(p
);
2674 p
= isl_printer_print_str(p
, "coincident");
2675 p
= isl_printer_yaml_next(p
);
2676 style
= isl_printer_get_yaml_style(p
);
2677 p
= isl_printer_set_yaml_style(p
, ISL_YAML_STYLE_FLOW
);
2678 p
= isl_printer_yaml_start_sequence(p
);
2679 n
= isl_schedule_band_n_member(band
);
2680 for (i
= 0; i
< n
; ++i
) {
2681 p
= isl_printer_print_int(p
,
2682 isl_schedule_band_member_get_coincident(band
, i
));
2683 p
= isl_printer_yaml_next(p
);
2685 p
= isl_printer_yaml_end_sequence(p
);
2686 p
= isl_printer_set_yaml_style(p
, style
);
2688 options
= isl_schedule_band_get_ast_build_options(band
);
2689 empty
= isl_union_set_is_empty(options
);
2691 p
= isl_printer_free(p
);
2693 p
= isl_printer_yaml_next(p
);
2694 p
= isl_printer_print_str(p
, "options");
2695 p
= isl_printer_yaml_next(p
);
2696 p
= isl_printer_print_str(p
, "\"");
2697 p
= isl_printer_print_union_set(p
, options
);
2698 p
= isl_printer_print_str(p
, "\"");
2700 isl_union_set_free(options
);
2705 /* Print "tree" to "p".
2707 * If "n_ancestor" is non-negative, then "child_pos" contains the child
2708 * positions of a descendant of the current node that should be marked
2709 * (by the comment "YOU ARE HERE"). In particular, if "n_ancestor"
2710 * is zero, then the current node should be marked.
2711 * The marking is only printed in YAML block format.
2713 * Implicit leaf nodes are not printed, except if they correspond
2714 * to the node that should be marked.
2716 __isl_give isl_printer
*isl_printer_print_schedule_tree_mark(
2717 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
,
2718 int n_ancestor
, int *child_pos
)
2724 block
= isl_printer_get_yaml_style(p
) == ISL_YAML_STYLE_BLOCK
;
2726 p
= isl_printer_yaml_start_mapping(p
);
2727 if (n_ancestor
== 0 && block
) {
2728 p
= isl_printer_print_str(p
, "# YOU ARE HERE");
2729 p
= isl_printer_end_line(p
);
2730 p
= isl_printer_start_line(p
);
2732 switch (tree
->type
) {
2733 case isl_schedule_node_error
:
2734 p
= isl_printer_print_str(p
, "ERROR");
2736 case isl_schedule_node_leaf
:
2737 p
= isl_printer_print_str(p
, "leaf");
2739 case isl_schedule_node_sequence
:
2740 p
= isl_printer_print_str(p
, "sequence");
2743 case isl_schedule_node_set
:
2744 p
= isl_printer_print_str(p
, "set");
2747 case isl_schedule_node_context
:
2748 p
= isl_printer_print_str(p
, "context");
2749 p
= isl_printer_yaml_next(p
);
2750 p
= isl_printer_print_str(p
, "\"");
2751 p
= isl_printer_print_set(p
, tree
->context
);
2752 p
= isl_printer_print_str(p
, "\"");
2754 case isl_schedule_node_domain
:
2755 p
= isl_printer_print_str(p
, "domain");
2756 p
= isl_printer_yaml_next(p
);
2757 p
= isl_printer_print_str(p
, "\"");
2758 p
= isl_printer_print_union_set(p
, tree
->domain
);
2759 p
= isl_printer_print_str(p
, "\"");
2761 case isl_schedule_node_expansion
:
2762 p
= isl_printer_print_str(p
, "contraction");
2763 p
= isl_printer_yaml_next(p
);
2764 p
= isl_printer_print_str(p
, "\"");
2765 p
= isl_printer_print_union_pw_multi_aff(p
, tree
->contraction
);
2766 p
= isl_printer_print_str(p
, "\"");
2767 p
= isl_printer_yaml_next(p
);
2768 p
= isl_printer_print_str(p
, "expansion");
2769 p
= isl_printer_yaml_next(p
);
2770 p
= isl_printer_print_str(p
, "\"");
2771 p
= isl_printer_print_union_map(p
, tree
->expansion
);
2772 p
= isl_printer_print_str(p
, "\"");
2774 case isl_schedule_node_extension
:
2775 p
= isl_printer_print_str(p
, "extension");
2776 p
= isl_printer_yaml_next(p
);
2777 p
= isl_printer_print_str(p
, "\"");
2778 p
= isl_printer_print_union_map(p
, tree
->extension
);
2779 p
= isl_printer_print_str(p
, "\"");
2781 case isl_schedule_node_filter
:
2782 p
= isl_printer_print_str(p
, "filter");
2783 p
= isl_printer_yaml_next(p
);
2784 p
= isl_printer_print_str(p
, "\"");
2785 p
= isl_printer_print_union_set(p
, tree
->filter
);
2786 p
= isl_printer_print_str(p
, "\"");
2788 case isl_schedule_node_guard
:
2789 p
= isl_printer_print_str(p
, "guard");
2790 p
= isl_printer_yaml_next(p
);
2791 p
= isl_printer_print_str(p
, "\"");
2792 p
= isl_printer_print_set(p
, tree
->guard
);
2793 p
= isl_printer_print_str(p
, "\"");
2795 case isl_schedule_node_mark
:
2796 p
= isl_printer_print_str(p
, "mark");
2797 p
= isl_printer_yaml_next(p
);
2798 p
= isl_printer_print_str(p
, "\"");
2799 p
= isl_printer_print_str(p
, isl_id_get_name(tree
->mark
));
2800 p
= isl_printer_print_str(p
, "\"");
2802 case isl_schedule_node_band
:
2803 p
= print_tree_band(p
, tree
->band
);
2806 p
= isl_printer_yaml_next(p
);
2808 n
= isl_schedule_tree_n_children(tree
);
2810 return isl_printer_free(p
);
2812 if (n_ancestor
> 0 && block
) {
2813 isl_schedule_tree
*leaf
;
2815 p
= isl_printer_print_str(p
, "child");
2816 p
= isl_printer_yaml_next(p
);
2817 leaf
= isl_schedule_tree_leaf(isl_printer_get_ctx(p
));
2818 p
= isl_printer_print_schedule_tree_mark(p
,
2820 isl_schedule_tree_free(leaf
);
2821 p
= isl_printer_yaml_next(p
);
2823 return isl_printer_yaml_end_mapping(p
);
2827 p
= isl_printer_yaml_start_sequence(p
);
2829 p
= isl_printer_print_str(p
, "child");
2830 p
= isl_printer_yaml_next(p
);
2833 for (i
= 0; i
< n
; ++i
) {
2834 isl_schedule_tree
*t
;
2836 t
= isl_schedule_tree_get_child(tree
, i
);
2837 if (n_ancestor
> 0 && child_pos
[0] == i
)
2838 p
= isl_printer_print_schedule_tree_mark(p
, t
,
2839 n_ancestor
- 1, child_pos
+ 1);
2841 p
= isl_printer_print_schedule_tree_mark(p
, t
,
2843 isl_schedule_tree_free(t
);
2845 p
= isl_printer_yaml_next(p
);
2849 p
= isl_printer_yaml_end_sequence(p
);
2850 p
= isl_printer_yaml_end_mapping(p
);
2855 /* Print "tree" to "p".
2857 __isl_give isl_printer
*isl_printer_print_schedule_tree(
2858 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
)
2860 return isl_printer_print_schedule_tree_mark(p
, tree
, -1, NULL
);
2863 void isl_schedule_tree_dump(__isl_keep isl_schedule_tree
*tree
)
2866 isl_printer
*printer
;
2871 ctx
= isl_schedule_tree_get_ctx(tree
);
2872 printer
= isl_printer_to_file(ctx
, stderr
);
2873 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
2874 printer
= isl_printer_print_schedule_tree(printer
, tree
);
2876 isl_printer_free(printer
);