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_domain
:
89 dup
->domain
= isl_union_set_copy(tree
->domain
);
91 return isl_schedule_tree_free(dup
);
93 case isl_schedule_node_filter
:
94 dup
->filter
= isl_union_set_copy(tree
->filter
);
96 return isl_schedule_tree_free(dup
);
98 case isl_schedule_node_leaf
:
99 case isl_schedule_node_sequence
:
100 case isl_schedule_node_set
:
104 if (tree
->children
) {
105 dup
->children
= isl_schedule_tree_list_copy(tree
->children
);
107 return isl_schedule_tree_free(dup
);
109 dup
->anchored
= tree
->anchored
;
114 /* Return an isl_schedule_tree that is equal to "tree" and that has only
115 * a single reference.
117 * This function is called before a tree is modified.
118 * A static tree (with negative reference count) should never be modified,
119 * so it is not allowed to call this function on a static tree.
121 __isl_give isl_schedule_tree
*isl_schedule_tree_cow(
122 __isl_take isl_schedule_tree
*tree
)
128 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
129 "static trees cannot be modified",
130 return isl_schedule_tree_free(tree
));
135 return isl_schedule_tree_dup(tree
);
138 /* Return a new reference to "tree".
140 * A static tree (with negative reference count) does not keep track
141 * of the number of references and should not be modified.
143 __isl_give isl_schedule_tree
*isl_schedule_tree_copy(
144 __isl_keep isl_schedule_tree
*tree
)
156 /* Free "tree" and return NULL.
158 __isl_null isl_schedule_tree
*isl_schedule_tree_free(
159 __isl_take isl_schedule_tree
*tree
)
168 switch (tree
->type
) {
169 case isl_schedule_node_band
:
170 isl_schedule_band_free(tree
->band
);
172 case isl_schedule_node_domain
:
173 isl_union_set_free(tree
->domain
);
175 case isl_schedule_node_filter
:
176 isl_union_set_free(tree
->filter
);
178 case isl_schedule_node_sequence
:
179 case isl_schedule_node_set
:
180 case isl_schedule_node_error
:
181 case isl_schedule_node_leaf
:
184 isl_schedule_tree_list_free(tree
->children
);
185 isl_ctx_deref(tree
->ctx
);
191 /* Create and return a new leaf schedule tree.
193 __isl_give isl_schedule_tree
*isl_schedule_tree_leaf(isl_ctx
*ctx
)
195 return isl_schedule_tree_alloc(ctx
, isl_schedule_node_leaf
);
198 /* Create a new band schedule tree referring to "band"
201 __isl_give isl_schedule_tree
*isl_schedule_tree_from_band(
202 __isl_take isl_schedule_band
*band
)
205 isl_schedule_tree
*tree
;
210 ctx
= isl_schedule_band_get_ctx(band
);
211 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_band
);
216 tree
->anchored
= isl_schedule_band_is_anchored(band
);
220 isl_schedule_band_free(band
);
224 /* Create a new domain schedule tree with the given domain and no children.
226 __isl_give isl_schedule_tree
*isl_schedule_tree_from_domain(
227 __isl_take isl_union_set
*domain
)
230 isl_schedule_tree
*tree
;
235 ctx
= isl_union_set_get_ctx(domain
);
236 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_domain
);
240 tree
->domain
= domain
;
244 isl_union_set_free(domain
);
248 /* Create a new filter schedule tree with the given filter and no children.
250 __isl_give isl_schedule_tree
*isl_schedule_tree_from_filter(
251 __isl_take isl_union_set
*filter
)
254 isl_schedule_tree
*tree
;
259 ctx
= isl_union_set_get_ctx(filter
);
260 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_filter
);
264 tree
->filter
= filter
;
268 isl_union_set_free(filter
);
272 /* Does "tree" have any node that depends on its position
273 * in the complete schedule tree?
275 int isl_schedule_tree_is_subtree_anchored(__isl_keep isl_schedule_tree
*tree
)
277 return tree
? tree
->anchored
: -1;
280 /* Does the root node of "tree" depend on its position in the complete
282 * Band nodes may be anchored depending on the associated AST build options.
284 int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree
*tree
)
289 switch (isl_schedule_tree_get_type(tree
)) {
290 case isl_schedule_node_error
:
292 case isl_schedule_node_band
:
293 return isl_schedule_band_is_anchored(tree
->band
);
294 case isl_schedule_node_domain
:
295 case isl_schedule_node_filter
:
296 case isl_schedule_node_leaf
:
297 case isl_schedule_node_sequence
:
298 case isl_schedule_node_set
:
303 /* Update the anchored field of "tree" based on whether the root node
304 * itself in anchored and the anchored fields of the children.
306 * This function should be called whenever the children of a tree node
307 * are changed or the anchoredness of the tree root itself changes.
309 __isl_give isl_schedule_tree
*isl_schedule_tree_update_anchored(
310 __isl_take isl_schedule_tree
*tree
)
318 anchored
= isl_schedule_tree_is_anchored(tree
);
320 return isl_schedule_tree_free(tree
);
322 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
323 for (i
= 0; !anchored
&& i
< n
; ++i
) {
324 isl_schedule_tree
*child
;
326 child
= isl_schedule_tree_get_child(tree
, i
);
328 return isl_schedule_tree_free(tree
);
329 anchored
= child
->anchored
;
330 isl_schedule_tree_free(child
);
333 if (anchored
== tree
->anchored
)
335 tree
= isl_schedule_tree_cow(tree
);
338 tree
->anchored
= anchored
;
342 /* Create a new tree of the given type (isl_schedule_node_sequence or
343 * isl_schedule_node_set) with the given children.
345 __isl_give isl_schedule_tree
*isl_schedule_tree_from_children(
346 enum isl_schedule_node_type type
,
347 __isl_take isl_schedule_tree_list
*list
)
350 isl_schedule_tree
*tree
;
355 ctx
= isl_schedule_tree_list_get_ctx(list
);
356 tree
= isl_schedule_tree_alloc(ctx
, type
);
360 tree
->children
= list
;
361 tree
= isl_schedule_tree_update_anchored(tree
);
365 isl_schedule_tree_list_free(list
);
369 /* Construct a tree with a root node of type "type" and as children
370 * "tree1" and "tree2".
371 * If the root of one (or both) of the input trees is itself of type "type",
372 * then the tree is replaced by its children.
374 __isl_give isl_schedule_tree
*isl_schedule_tree_from_pair(
375 enum isl_schedule_node_type type
, __isl_take isl_schedule_tree
*tree1
,
376 __isl_take isl_schedule_tree
*tree2
)
379 isl_schedule_tree_list
*list
;
381 if (!tree1
|| !tree2
)
384 ctx
= isl_schedule_tree_get_ctx(tree1
);
385 if (isl_schedule_tree_get_type(tree1
) == type
) {
386 list
= isl_schedule_tree_list_copy(tree1
->children
);
387 isl_schedule_tree_free(tree1
);
389 list
= isl_schedule_tree_list_alloc(ctx
, 2);
390 list
= isl_schedule_tree_list_add(list
, tree1
);
392 if (isl_schedule_tree_get_type(tree2
) == type
) {
393 isl_schedule_tree_list
*children
;
395 children
= isl_schedule_tree_list_copy(tree2
->children
);
396 list
= isl_schedule_tree_list_concat(list
, children
);
397 isl_schedule_tree_free(tree2
);
399 list
= isl_schedule_tree_list_add(list
, tree2
);
402 return isl_schedule_tree_from_children(type
, list
);
404 isl_schedule_tree_free(tree1
);
405 isl_schedule_tree_free(tree2
);
409 /* Return the isl_ctx to which "tree" belongs.
411 isl_ctx
*isl_schedule_tree_get_ctx(__isl_keep isl_schedule_tree
*tree
)
413 return tree
? tree
->ctx
: NULL
;
416 /* Return the type of the root of the tree or isl_schedule_node_error
419 enum isl_schedule_node_type
isl_schedule_tree_get_type(
420 __isl_keep isl_schedule_tree
*tree
)
422 return tree
? tree
->type
: isl_schedule_node_error
;
425 /* Are "tree1" and "tree2" obviously equal to each other?
427 int isl_schedule_tree_plain_is_equal(__isl_keep isl_schedule_tree
*tree1
,
428 __isl_keep isl_schedule_tree
*tree2
)
433 if (!tree1
|| !tree2
)
437 if (tree1
->type
!= tree2
->type
)
440 switch (tree1
->type
) {
441 case isl_schedule_node_band
:
442 equal
= isl_schedule_band_plain_is_equal(tree1
->band
,
445 case isl_schedule_node_domain
:
446 equal
= isl_union_set_is_equal(tree1
->domain
, tree2
->domain
);
448 case isl_schedule_node_filter
:
449 equal
= isl_union_set_is_equal(tree1
->filter
, tree2
->filter
);
451 case isl_schedule_node_leaf
:
452 case isl_schedule_node_sequence
:
453 case isl_schedule_node_set
:
456 case isl_schedule_node_error
:
461 if (equal
< 0 || !equal
)
464 n
= isl_schedule_tree_n_children(tree1
);
465 if (n
!= isl_schedule_tree_n_children(tree2
))
467 for (i
= 0; i
< n
; ++i
) {
468 isl_schedule_tree
*child1
, *child2
;
470 child1
= isl_schedule_tree_get_child(tree1
, i
);
471 child2
= isl_schedule_tree_get_child(tree2
, i
);
472 equal
= isl_schedule_tree_plain_is_equal(child1
, child2
);
473 isl_schedule_tree_free(child1
);
474 isl_schedule_tree_free(child2
);
476 if (equal
< 0 || !equal
)
483 /* Does "tree" have any children, other than an implicit leaf.
485 int isl_schedule_tree_has_children(__isl_keep isl_schedule_tree
*tree
)
490 return tree
->children
!= NULL
;
493 /* Return the number of children of "tree", excluding implicit leaves.
495 int isl_schedule_tree_n_children(__isl_keep isl_schedule_tree
*tree
)
500 return isl_schedule_tree_list_n_schedule_tree(tree
->children
);
503 /* Return a copy of the (explicit) child at position "pos" of "tree".
505 __isl_give isl_schedule_tree
*isl_schedule_tree_get_child(
506 __isl_keep isl_schedule_tree
*tree
, int pos
)
511 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
512 "schedule tree has no explicit children", return NULL
);
513 return isl_schedule_tree_list_get_schedule_tree(tree
->children
, pos
);
516 /* Return a copy of the (explicit) child at position "pos" of "tree" and
519 __isl_give isl_schedule_tree
*isl_schedule_tree_child(
520 __isl_take isl_schedule_tree
*tree
, int pos
)
522 isl_schedule_tree
*child
;
524 child
= isl_schedule_tree_get_child(tree
, pos
);
525 isl_schedule_tree_free(tree
);
529 /* Remove all (explicit) children from "tree".
531 __isl_give isl_schedule_tree
*isl_schedule_tree_reset_children(
532 __isl_take isl_schedule_tree
*tree
)
534 tree
= isl_schedule_tree_cow(tree
);
537 tree
->children
= isl_schedule_tree_list_free(tree
->children
);
541 /* Remove the child at position "pos" from the children of "tree".
542 * If there was only one child to begin with, then remove all children.
544 __isl_give isl_schedule_tree
*isl_schedule_tree_drop_child(
545 __isl_take isl_schedule_tree
*tree
, int pos
)
549 tree
= isl_schedule_tree_cow(tree
);
553 if (!isl_schedule_tree_has_children(tree
))
554 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
555 "tree does not have any explicit children",
556 return isl_schedule_tree_free(tree
));
557 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
558 if (pos
< 0 || pos
>= n
)
559 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
560 "position out of bounds",
561 return isl_schedule_tree_free(tree
));
563 return isl_schedule_tree_reset_children(tree
);
565 tree
->children
= isl_schedule_tree_list_drop(tree
->children
, pos
, 1);
567 return isl_schedule_tree_free(tree
);
572 /* Replace the child at position "pos" of "tree" by "child".
574 * If the new child is a leaf, then it is not explicitly
575 * recorded in the list of children. Instead, the list of children
576 * (which is assumed to have only one element) is removed.
577 * Note that the children of set and sequence nodes are always
578 * filters, so they cannot be replaced by empty trees.
580 __isl_give isl_schedule_tree
*isl_schedule_tree_replace_child(
581 __isl_take isl_schedule_tree
*tree
, int pos
,
582 __isl_take isl_schedule_tree
*child
)
584 tree
= isl_schedule_tree_cow(tree
);
588 if (isl_schedule_tree_is_leaf(child
)) {
589 isl_schedule_tree_free(child
);
590 if (!tree
->children
&& pos
== 0)
592 if (isl_schedule_tree_n_children(tree
) != 1)
593 isl_die(isl_schedule_tree_get_ctx(tree
),
595 "can only replace single child by leaf",
597 return isl_schedule_tree_reset_children(tree
);
600 if (!tree
->children
&& pos
== 0)
602 isl_schedule_tree_list_from_schedule_tree(child
);
604 tree
->children
= isl_schedule_tree_list_set_schedule_tree(
605 tree
->children
, pos
, child
);
608 return isl_schedule_tree_free(tree
);
609 tree
= isl_schedule_tree_update_anchored(tree
);
613 isl_schedule_tree_free(tree
);
614 isl_schedule_tree_free(child
);
618 /* Replace the (explicit) children of "tree" by "children"?
620 __isl_give isl_schedule_tree
*isl_schedule_tree_set_children(
621 __isl_take isl_schedule_tree
*tree
,
622 __isl_take isl_schedule_tree_list
*children
)
624 tree
= isl_schedule_tree_cow(tree
);
625 if (!tree
|| !children
)
627 isl_schedule_tree_list_free(tree
->children
);
628 tree
->children
= children
;
631 isl_schedule_tree_free(tree
);
632 isl_schedule_tree_list_free(children
);
636 /* Create a new band schedule tree referring to "band"
637 * with "tree" as single child.
639 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_band(
640 __isl_take isl_schedule_tree
*tree
, __isl_take isl_schedule_band
*band
)
642 isl_schedule_tree
*res
;
644 res
= isl_schedule_tree_from_band(band
);
645 return isl_schedule_tree_replace_child(res
, 0, tree
);
648 /* Create a new domain schedule tree with the given domain and
649 * with "tree" as single child.
651 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_domain(
652 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
654 isl_schedule_tree
*res
;
656 res
= isl_schedule_tree_from_domain(domain
);
657 return isl_schedule_tree_replace_child(res
, 0, tree
);
660 /* Create a new filter schedule tree with the given filter and single child.
662 * If the root of "tree" is itself a filter node, then the two
663 * filter nodes are merged into one node.
665 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_filter(
666 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
668 isl_schedule_tree
*res
;
670 if (isl_schedule_tree_get_type(tree
) == isl_schedule_node_filter
) {
671 isl_union_set
*tree_filter
;
673 tree_filter
= isl_schedule_tree_filter_get_filter(tree
);
674 tree_filter
= isl_union_set_intersect(tree_filter
, filter
);
675 tree
= isl_schedule_tree_filter_set_filter(tree
, tree_filter
);
679 res
= isl_schedule_tree_from_filter(filter
);
680 return isl_schedule_tree_replace_child(res
, 0, tree
);
683 /* Insert a filter node with filter set "filter"
684 * in each of the children of "tree".
686 __isl_give isl_schedule_tree
*isl_schedule_tree_children_insert_filter(
687 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
691 if (!tree
|| !filter
)
694 n
= isl_schedule_tree_n_children(tree
);
695 for (i
= 0; i
< n
; ++i
) {
696 isl_schedule_tree
*child
;
698 child
= isl_schedule_tree_get_child(tree
, i
);
699 child
= isl_schedule_tree_insert_filter(child
,
700 isl_union_set_copy(filter
));
701 tree
= isl_schedule_tree_replace_child(tree
, i
, child
);
704 isl_union_set_free(filter
);
707 isl_union_set_free(filter
);
708 isl_schedule_tree_free(tree
);
712 /* Return the number of members in the band tree root.
714 unsigned isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree
*tree
)
719 if (tree
->type
!= isl_schedule_node_band
)
720 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
721 "not a band node", return 0);
723 return isl_schedule_band_n_member(tree
->band
);
726 /* Is the band member at position "pos" of the band tree root
729 int isl_schedule_tree_band_member_get_coincident(
730 __isl_keep isl_schedule_tree
*tree
, int pos
)
735 if (tree
->type
!= isl_schedule_node_band
)
736 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
737 "not a band node", return -1);
739 return isl_schedule_band_member_get_coincident(tree
->band
, pos
);
742 /* Mark the given band member as being coincident or not
743 * according to "coincident".
745 __isl_give isl_schedule_tree
*isl_schedule_tree_band_member_set_coincident(
746 __isl_take isl_schedule_tree
*tree
, int pos
, int coincident
)
750 if (tree
->type
!= isl_schedule_node_band
)
751 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
752 "not a band node", return isl_schedule_tree_free(tree
));
753 if (isl_schedule_tree_band_member_get_coincident(tree
, pos
) ==
756 tree
= isl_schedule_tree_cow(tree
);
760 tree
->band
= isl_schedule_band_member_set_coincident(tree
->band
, pos
,
763 return isl_schedule_tree_free(tree
);
767 /* Is the band tree root marked permutable?
769 int isl_schedule_tree_band_get_permutable(__isl_keep isl_schedule_tree
*tree
)
774 if (tree
->type
!= isl_schedule_node_band
)
775 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
776 "not a band node", return -1);
778 return isl_schedule_band_get_permutable(tree
->band
);
781 /* Mark the band tree root permutable or not according to "permutable"?
783 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_permutable(
784 __isl_take isl_schedule_tree
*tree
, int permutable
)
788 if (tree
->type
!= isl_schedule_node_band
)
789 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
790 "not a band node", return isl_schedule_tree_free(tree
));
791 if (isl_schedule_tree_band_get_permutable(tree
) == permutable
)
793 tree
= isl_schedule_tree_cow(tree
);
797 tree
->band
= isl_schedule_band_set_permutable(tree
->band
, permutable
);
799 return isl_schedule_tree_free(tree
);
803 /* Return the schedule space of the band tree root.
805 __isl_give isl_space
*isl_schedule_tree_band_get_space(
806 __isl_keep isl_schedule_tree
*tree
)
811 if (tree
->type
!= isl_schedule_node_band
)
812 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
813 "not a band node", return NULL
);
815 return isl_schedule_band_get_space(tree
->band
);
818 /* Return the schedule of the band tree root in isolation.
820 __isl_give isl_multi_union_pw_aff
*isl_schedule_tree_band_get_partial_schedule(
821 __isl_keep isl_schedule_tree
*tree
)
826 if (tree
->type
!= isl_schedule_node_band
)
827 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
828 "not a band node", return NULL
);
830 return isl_schedule_band_get_partial_schedule(tree
->band
);
833 /* Return the loop AST generation type for the band member
834 * of the band tree root at position "pos".
836 enum isl_ast_loop_type
isl_schedule_tree_band_member_get_ast_loop_type(
837 __isl_keep isl_schedule_tree
*tree
, int pos
)
840 return isl_ast_loop_error
;
842 if (tree
->type
!= isl_schedule_node_band
)
843 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
844 "not a band node", return isl_ast_loop_error
);
846 return isl_schedule_band_member_get_ast_loop_type(tree
->band
, pos
);
849 /* Set the loop AST generation type for the band member of the band tree root
850 * at position "pos" to "type".
852 __isl_give isl_schedule_tree
*isl_schedule_tree_band_member_set_ast_loop_type(
853 __isl_take isl_schedule_tree
*tree
, int pos
,
854 enum isl_ast_loop_type type
)
856 tree
= isl_schedule_tree_cow(tree
);
860 if (tree
->type
!= isl_schedule_node_band
)
861 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
862 "not a band node", return isl_schedule_tree_free(tree
));
864 tree
->band
= isl_schedule_band_member_set_ast_loop_type(tree
->band
,
867 return isl_schedule_tree_free(tree
);
872 /* Return the loop AST generation type for the band member
873 * of the band tree root at position "pos" for the isolated part.
875 enum isl_ast_loop_type
isl_schedule_tree_band_member_get_isolate_ast_loop_type(
876 __isl_keep isl_schedule_tree
*tree
, int pos
)
879 return isl_ast_loop_error
;
881 if (tree
->type
!= isl_schedule_node_band
)
882 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
883 "not a band node", return isl_ast_loop_error
);
885 return isl_schedule_band_member_get_isolate_ast_loop_type(tree
->band
,
889 /* Set the loop AST generation type for the band member of the band tree root
890 * at position "pos" for the isolated part to "type".
892 __isl_give isl_schedule_tree
*
893 isl_schedule_tree_band_member_set_isolate_ast_loop_type(
894 __isl_take isl_schedule_tree
*tree
, int pos
,
895 enum isl_ast_loop_type type
)
897 tree
= isl_schedule_tree_cow(tree
);
901 if (tree
->type
!= isl_schedule_node_band
)
902 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
903 "not a band node", return isl_schedule_tree_free(tree
));
905 tree
->band
= isl_schedule_band_member_set_isolate_ast_loop_type(
906 tree
->band
, pos
, type
);
908 return isl_schedule_tree_free(tree
);
913 /* Return the AST build options associated to the band tree root.
915 __isl_give isl_union_set
*isl_schedule_tree_band_get_ast_build_options(
916 __isl_keep isl_schedule_tree
*tree
)
921 if (tree
->type
!= isl_schedule_node_band
)
922 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
923 "not a band node", return NULL
);
925 return isl_schedule_band_get_ast_build_options(tree
->band
);
928 /* Replace the AST build options associated to band tree root by "options".
929 * Updated the anchored field if the anchoredness of the root node itself
932 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_ast_build_options(
933 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*options
)
937 tree
= isl_schedule_tree_cow(tree
);
938 if (!tree
|| !options
)
941 if (tree
->type
!= isl_schedule_node_band
)
942 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
943 "not a band node", goto error
);
945 was_anchored
= isl_schedule_tree_is_anchored(tree
);
946 tree
->band
= isl_schedule_band_set_ast_build_options(tree
->band
,
949 return isl_schedule_tree_free(tree
);
950 if (isl_schedule_tree_is_anchored(tree
) != was_anchored
)
951 tree
= isl_schedule_tree_update_anchored(tree
);
955 isl_schedule_tree_free(tree
);
956 isl_union_set_free(options
);
960 /* Return the domain of the domain tree root.
962 __isl_give isl_union_set
*isl_schedule_tree_domain_get_domain(
963 __isl_keep isl_schedule_tree
*tree
)
968 if (tree
->type
!= isl_schedule_node_domain
)
969 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
970 "not a domain node", return NULL
);
972 return isl_union_set_copy(tree
->domain
);
975 /* Replace the domain of domain tree root "tree" by "domain".
977 __isl_give isl_schedule_tree
*isl_schedule_tree_domain_set_domain(
978 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
980 tree
= isl_schedule_tree_cow(tree
);
981 if (!tree
|| !domain
)
984 if (tree
->type
!= isl_schedule_node_domain
)
985 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
986 "not a domain node", goto error
);
988 isl_union_set_free(tree
->domain
);
989 tree
->domain
= domain
;
993 isl_schedule_tree_free(tree
);
994 isl_union_set_free(domain
);
998 /* Return the filter of the filter tree root.
1000 __isl_give isl_union_set
*isl_schedule_tree_filter_get_filter(
1001 __isl_keep isl_schedule_tree
*tree
)
1006 if (tree
->type
!= isl_schedule_node_filter
)
1007 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1008 "not a filter node", return NULL
);
1010 return isl_union_set_copy(tree
->filter
);
1013 /* Replace the filter of the filter tree root by "filter".
1015 __isl_give isl_schedule_tree
*isl_schedule_tree_filter_set_filter(
1016 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
1018 tree
= isl_schedule_tree_cow(tree
);
1019 if (!tree
|| !filter
)
1022 if (tree
->type
!= isl_schedule_node_filter
)
1023 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1024 "not a filter node", return NULL
);
1026 isl_union_set_free(tree
->filter
);
1027 tree
->filter
= filter
;
1031 isl_schedule_tree_free(tree
);
1032 isl_union_set_free(filter
);
1036 /* Set dim to the range dimension of "map" and abort the search.
1038 static int set_range_dim(__isl_take isl_map
*map
, void *user
)
1042 *dim
= isl_map_dim(map
, isl_dim_out
);
1048 /* Return the dimension of the range of "umap".
1049 * "umap" is assumed not to be empty and
1050 * all maps inside "umap" are assumed to have the same range.
1052 * We extract the range dimension from the first map in "umap".
1054 static int range_dim(__isl_keep isl_union_map
*umap
)
1060 if (isl_union_map_n_map(umap
) == 0)
1061 isl_die(isl_union_map_get_ctx(umap
), isl_error_internal
,
1062 "unexpected empty input", return -1);
1064 isl_union_map_foreach_map(umap
, &set_range_dim
, &dim
);
1069 /* Append an "extra" number of zeros to the range of "umap" and
1070 * return the result.
1072 static __isl_give isl_union_map
*append_range(__isl_take isl_union_map
*umap
,
1078 isl_union_pw_multi_aff
*suffix
;
1079 isl_union_map
*universe
;
1080 isl_union_map
*suffix_umap
;
1082 universe
= isl_union_map_universe(isl_union_map_copy(umap
));
1083 dom
= isl_union_map_domain(universe
);
1084 space
= isl_union_set_get_space(dom
);
1085 space
= isl_space_set_from_params(space
);
1086 space
= isl_space_add_dims(space
, isl_dim_set
, extra
);
1087 mv
= isl_multi_val_zero(space
);
1089 suffix
= isl_union_pw_multi_aff_multi_val_on_domain(dom
, mv
);
1090 suffix_umap
= isl_union_map_from_union_pw_multi_aff(suffix
);
1091 umap
= isl_union_map_flat_range_product(umap
, suffix_umap
);
1096 /* Move down to the first descendant of "tree" that contains any schedule
1097 * information or return "leaf" if there is no such descendant.
1099 __isl_give isl_schedule_tree
*isl_schedule_tree_first_schedule_descendant(
1100 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_tree
*leaf
)
1102 while (isl_schedule_tree_get_type(tree
) == isl_schedule_node_band
&&
1103 isl_schedule_tree_band_n_member(tree
) == 0) {
1104 if (!isl_schedule_tree_has_children(tree
)) {
1105 isl_schedule_tree_free(tree
);
1106 return isl_schedule_tree_copy(leaf
);
1108 tree
= isl_schedule_tree_child(tree
, 0);
1114 static __isl_give isl_union_map
*subtree_schedule_extend(
1115 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
);
1117 /* Extend the schedule map "outer" with the subtree schedule
1118 * of the (single) child of "tree", if any.
1120 * If "tree" does not have any descendants (apart from those that
1121 * do not carry any schedule information), then we simply return "outer".
1122 * Otherwise, we extend the schedule map "outer" with the subtree schedule
1123 * of the single child.
1125 static __isl_give isl_union_map
*subtree_schedule_extend_child(
1126 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1128 isl_schedule_tree
*child
;
1132 return isl_union_map_free(outer
);
1133 if (!isl_schedule_tree_has_children(tree
))
1135 child
= isl_schedule_tree_get_child(tree
, 0);
1137 return isl_union_map_free(outer
);
1138 res
= subtree_schedule_extend(child
, outer
);
1139 isl_schedule_tree_free(child
);
1143 /* Extract the parameter space from one of the children of "tree",
1144 * which are assumed to be filters.
1146 static __isl_give isl_space
*extract_space_from_filter_child(
1147 __isl_keep isl_schedule_tree
*tree
)
1151 isl_schedule_tree
*child
;
1153 child
= isl_schedule_tree_list_get_schedule_tree(tree
->children
, 0);
1154 dom
= isl_schedule_tree_filter_get_filter(child
);
1155 space
= isl_union_set_get_space(dom
);
1156 isl_union_set_free(dom
);
1157 isl_schedule_tree_free(child
);
1162 /* Extend the schedule map "outer" with the subtree schedule
1163 * of a set or sequence node.
1165 * The schedule for the set or sequence node itself is composed of
1166 * pieces of the form
1174 * The first form is used if there is only a single child or
1175 * if the current node is a set node and the schedule_separate_components
1176 * option is not set.
1178 * Each of the pieces above is extended with the subtree schedule of
1179 * the child of the corresponding filter, if any, padded with zeros
1180 * to ensure that all pieces have the same range dimension.
1182 static __isl_give isl_union_map
*subtree_schedule_extend_from_children(
1183 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1192 isl_union_map
*umap
;
1197 ctx
= isl_schedule_tree_get_ctx(tree
);
1198 if (!tree
->children
)
1199 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1200 "missing children", return NULL
);
1201 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1203 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1204 "missing children", return NULL
);
1206 separate
= n
> 1 && (tree
->type
== isl_schedule_node_sequence
||
1207 isl_options_get_schedule_separate_components(ctx
));
1209 space
= extract_space_from_filter_child(tree
);
1211 umap
= isl_union_map_empty(isl_space_copy(space
));
1212 space
= isl_space_set_from_params(space
);
1214 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1215 v
= isl_val_zero(ctx
);
1217 mv
= isl_multi_val_zero(space
);
1219 dim
= isl_multi_val_dim(mv
, isl_dim_set
);
1220 for (i
= 0; i
< n
; ++i
) {
1221 isl_union_pw_multi_aff
*upma
;
1222 isl_union_map
*umap_i
;
1224 isl_schedule_tree
*child
;
1228 child
= isl_schedule_tree_list_get_schedule_tree(
1230 dom
= isl_schedule_tree_filter_get_filter(child
);
1233 mv
= isl_multi_val_set_val(mv
, 0, isl_val_copy(v
));
1234 v
= isl_val_add_ui(v
, 1);
1236 upma
= isl_union_pw_multi_aff_multi_val_on_domain(dom
,
1237 isl_multi_val_copy(mv
));
1238 umap_i
= isl_union_map_from_union_pw_multi_aff(upma
);
1239 umap_i
= isl_union_map_flat_range_product(
1240 isl_union_map_copy(outer
), umap_i
);
1241 umap_i
= subtree_schedule_extend_child(child
, umap_i
);
1242 isl_schedule_tree_free(child
);
1244 empty
= isl_union_map_is_empty(umap_i
);
1246 umap_i
= isl_union_map_free(umap_i
);
1248 isl_union_map_free(umap_i
);
1252 dim_i
= range_dim(umap_i
);
1254 umap
= isl_union_map_free(umap
);
1255 } else if (dim
< dim_i
) {
1256 umap
= append_range(umap
, dim_i
- dim
);
1258 } else if (dim_i
< dim
) {
1259 umap_i
= append_range(umap_i
, dim
- dim_i
);
1261 umap
= isl_union_map_union(umap
, umap_i
);
1265 isl_multi_val_free(mv
);
1266 isl_union_map_free(outer
);
1271 /* Extend the schedule map "outer" with the subtree schedule of "tree".
1273 * If the root of the tree is a set or a sequence, then we extend
1274 * the schedule map in subtree_schedule_extend_from_children.
1275 * Otherwise, we extend the schedule map with the partial schedule
1276 * corresponding to the root of the tree and then continue with
1277 * the single child of this root.
1279 static __isl_give isl_union_map
*subtree_schedule_extend(
1280 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1282 isl_multi_union_pw_aff
*mupa
;
1283 isl_union_map
*umap
;
1284 isl_union_set
*domain
;
1289 switch (tree
->type
) {
1290 case isl_schedule_node_error
:
1291 return isl_union_map_free(outer
);
1292 case isl_schedule_node_band
:
1293 if (isl_schedule_tree_band_n_member(tree
) == 0)
1294 return subtree_schedule_extend_child(tree
, outer
);
1295 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1296 umap
= isl_union_map_from_multi_union_pw_aff(mupa
);
1297 outer
= isl_union_map_flat_range_product(outer
, umap
);
1298 umap
= subtree_schedule_extend_child(tree
, outer
);
1300 case isl_schedule_node_domain
:
1301 domain
= isl_schedule_tree_domain_get_domain(tree
);
1302 umap
= isl_union_map_from_domain(domain
);
1303 outer
= isl_union_map_flat_range_product(outer
, umap
);
1304 umap
= subtree_schedule_extend_child(tree
, outer
);
1306 case isl_schedule_node_filter
:
1307 domain
= isl_schedule_tree_filter_get_filter(tree
);
1308 umap
= isl_union_map_from_domain(domain
);
1309 outer
= isl_union_map_flat_range_product(outer
, umap
);
1310 umap
= subtree_schedule_extend_child(tree
, outer
);
1312 case isl_schedule_node_leaf
:
1313 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1314 "leaf node should be handled by caller", return NULL
);
1315 case isl_schedule_node_set
:
1316 case isl_schedule_node_sequence
:
1317 umap
= subtree_schedule_extend_from_children(tree
, outer
);
1324 static __isl_give isl_union_set
*initial_domain(
1325 __isl_keep isl_schedule_tree
*tree
);
1327 /* Extract a universe domain from the children of the tree root "tree",
1328 * which is a set or sequence, meaning that its children are filters.
1329 * In particular, return the union of the universes of the filters.
1331 static __isl_give isl_union_set
*initial_domain_from_children(
1332 __isl_keep isl_schedule_tree
*tree
)
1336 isl_union_set
*domain
;
1338 if (!tree
->children
)
1339 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1340 "missing children", return NULL
);
1341 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1343 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1344 "missing children", return NULL
);
1346 space
= extract_space_from_filter_child(tree
);
1347 domain
= isl_union_set_empty(space
);
1349 for (i
= 0; i
< n
; ++i
) {
1350 isl_schedule_tree
*child
;
1351 isl_union_set
*domain_i
;
1353 child
= isl_schedule_tree_get_child(tree
, i
);
1354 domain_i
= initial_domain(child
);
1355 domain
= isl_union_set_union(domain
, domain_i
);
1356 isl_schedule_tree_free(child
);
1362 /* Extract a universe domain from the tree root "tree".
1363 * The caller is responsible for making sure that this node
1364 * would not be skipped by isl_schedule_tree_first_schedule_descendant
1365 * and that it is not a leaf node.
1367 static __isl_give isl_union_set
*initial_domain(
1368 __isl_keep isl_schedule_tree
*tree
)
1370 isl_multi_union_pw_aff
*mupa
;
1371 isl_union_set
*domain
;
1376 switch (tree
->type
) {
1377 case isl_schedule_node_error
:
1379 case isl_schedule_node_band
:
1380 if (isl_schedule_tree_band_n_member(tree
) == 0)
1381 isl_die(isl_schedule_tree_get_ctx(tree
),
1383 "0D band should be handled by caller",
1385 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1386 domain
= isl_multi_union_pw_aff_domain(mupa
);
1387 domain
= isl_union_set_universe(domain
);
1389 case isl_schedule_node_domain
:
1390 domain
= isl_schedule_tree_domain_get_domain(tree
);
1391 domain
= isl_union_set_universe(domain
);
1393 case isl_schedule_node_filter
:
1394 domain
= isl_schedule_tree_filter_get_filter(tree
);
1395 domain
= isl_union_set_universe(domain
);
1397 case isl_schedule_node_leaf
:
1398 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1399 "leaf node should be handled by caller", return NULL
);
1400 case isl_schedule_node_set
:
1401 case isl_schedule_node_sequence
:
1402 domain
= initial_domain_from_children(tree
);
1409 /* Return the subtree schedule of a node that contains some schedule
1410 * information, i.e., a node that would not be skipped by
1411 * isl_schedule_tree_first_schedule_descendant and that is not a leaf.
1413 * We start with an initial zero-dimensional subtree schedule based
1414 * on the domain information in the root node and then extend it
1415 * based on the schedule information in the root node and its descendants.
1417 __isl_give isl_union_map
*isl_schedule_tree_get_subtree_schedule_union_map(
1418 __isl_keep isl_schedule_tree
*tree
)
1420 isl_union_set
*domain
;
1421 isl_union_map
*umap
;
1423 domain
= initial_domain(tree
);
1424 umap
= isl_union_map_from_domain(domain
);
1425 return subtree_schedule_extend(tree
, umap
);
1428 /* Multiply the partial schedule of the band root node of "tree"
1429 * with the factors in "mv".
1431 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale(
1432 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
1436 if (tree
->type
!= isl_schedule_node_band
)
1437 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1438 "not a band node", goto error
);
1440 tree
= isl_schedule_tree_cow(tree
);
1444 tree
->band
= isl_schedule_band_scale(tree
->band
, mv
);
1446 return isl_schedule_tree_free(tree
);
1450 isl_schedule_tree_free(tree
);
1451 isl_multi_val_free(mv
);
1455 /* Divide the partial schedule of the band root node of "tree"
1456 * by the factors in "mv".
1458 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale_down(
1459 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
1463 if (tree
->type
!= isl_schedule_node_band
)
1464 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1465 "not a band node", goto error
);
1467 tree
= isl_schedule_tree_cow(tree
);
1471 tree
->band
= isl_schedule_band_scale_down(tree
->band
, mv
);
1473 return isl_schedule_tree_free(tree
);
1477 isl_schedule_tree_free(tree
);
1478 isl_multi_val_free(mv
);
1482 /* Tile the band root node of "tree" with tile sizes "sizes".
1484 * We duplicate the band node, change the schedule of one of them
1485 * to the tile schedule and the other to the point schedule and then
1486 * attach the point band as a child to the tile band.
1488 __isl_give isl_schedule_tree
*isl_schedule_tree_band_tile(
1489 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*sizes
)
1491 isl_schedule_tree
*child
= NULL
;
1493 if (!tree
|| !sizes
)
1495 if (tree
->type
!= isl_schedule_node_band
)
1496 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1497 "not a band node", goto error
);
1499 child
= isl_schedule_tree_copy(tree
);
1500 tree
= isl_schedule_tree_cow(tree
);
1501 child
= isl_schedule_tree_cow(child
);
1502 if (!tree
|| !child
)
1505 tree
->band
= isl_schedule_band_tile(tree
->band
,
1506 isl_multi_val_copy(sizes
));
1509 child
->band
= isl_schedule_band_point(child
->band
, tree
->band
, sizes
);
1511 child
= isl_schedule_tree_free(child
);
1513 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
1517 isl_schedule_tree_free(child
);
1518 isl_schedule_tree_free(tree
);
1519 isl_multi_val_free(sizes
);
1523 /* Split the band root node of "tree" into two nested band nodes,
1524 * one with the first "pos" dimensions and
1525 * one with the remaining dimensions.
1527 __isl_give isl_schedule_tree
*isl_schedule_tree_band_split(
1528 __isl_take isl_schedule_tree
*tree
, int pos
)
1531 isl_schedule_tree
*child
;
1535 if (tree
->type
!= isl_schedule_node_band
)
1536 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1537 "not a band node", return isl_schedule_tree_free(tree
));
1539 n
= isl_schedule_tree_band_n_member(tree
);
1540 if (pos
< 0 || pos
> n
)
1541 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1542 "position out of bounds",
1543 return isl_schedule_tree_free(tree
));
1545 child
= isl_schedule_tree_copy(tree
);
1546 tree
= isl_schedule_tree_cow(tree
);
1547 child
= isl_schedule_tree_cow(child
);
1548 if (!tree
|| !child
)
1551 child
->band
= isl_schedule_band_drop(child
->band
, 0, pos
);
1552 tree
->band
= isl_schedule_band_drop(tree
->band
, pos
, n
- pos
);
1553 if (!child
->band
|| !tree
->band
)
1556 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
1560 isl_schedule_tree_free(child
);
1561 isl_schedule_tree_free(tree
);
1565 /* Attach "tree2" at each of the leaves of "tree1".
1567 * If "tree1" does not have any explicit children, then make "tree2"
1568 * its single child. Otherwise, attach "tree2" to the leaves of
1569 * each of the children of "tree1".
1571 __isl_give isl_schedule_tree
*isl_schedule_tree_append_to_leaves(
1572 __isl_take isl_schedule_tree
*tree1
,
1573 __isl_take isl_schedule_tree
*tree2
)
1577 if (!tree1
|| !tree2
)
1579 n
= isl_schedule_tree_n_children(tree1
);
1581 isl_schedule_tree_list
*list
;
1582 list
= isl_schedule_tree_list_from_schedule_tree(tree2
);
1583 tree1
= isl_schedule_tree_set_children(tree1
, list
);
1586 for (i
= 0; i
< n
; ++i
) {
1587 isl_schedule_tree
*child
;
1589 child
= isl_schedule_tree_get_child(tree1
, i
);
1590 child
= isl_schedule_tree_append_to_leaves(child
,
1591 isl_schedule_tree_copy(tree2
));
1592 tree1
= isl_schedule_tree_replace_child(tree1
, i
, child
);
1595 isl_schedule_tree_free(tree2
);
1598 isl_schedule_tree_free(tree1
);
1599 isl_schedule_tree_free(tree2
);
1603 /* Reset the user pointer on all identifiers of parameters and tuples
1604 * in the root of "tree".
1606 __isl_give isl_schedule_tree
*isl_schedule_tree_reset_user(
1607 __isl_take isl_schedule_tree
*tree
)
1609 if (isl_schedule_tree_is_leaf(tree
))
1612 tree
= isl_schedule_tree_cow(tree
);
1616 switch (tree
->type
) {
1617 case isl_schedule_node_error
:
1618 return isl_schedule_tree_free(tree
);
1619 case isl_schedule_node_band
:
1620 tree
->band
= isl_schedule_band_reset_user(tree
->band
);
1622 return isl_schedule_tree_free(tree
);
1624 case isl_schedule_node_domain
:
1625 tree
->domain
= isl_union_set_reset_user(tree
->domain
);
1627 return isl_schedule_tree_free(tree
);
1629 case isl_schedule_node_filter
:
1630 tree
->filter
= isl_union_set_reset_user(tree
->filter
);
1632 return isl_schedule_tree_free(tree
);
1634 case isl_schedule_node_leaf
:
1635 case isl_schedule_node_sequence
:
1636 case isl_schedule_node_set
:
1643 /* Align the parameters of the root of "tree" to those of "space".
1645 __isl_give isl_schedule_tree
*isl_schedule_tree_align_params(
1646 __isl_take isl_schedule_tree
*tree
, __isl_take isl_space
*space
)
1651 if (isl_schedule_tree_is_leaf(tree
)) {
1652 isl_space_free(space
);
1656 tree
= isl_schedule_tree_cow(tree
);
1660 switch (tree
->type
) {
1661 case isl_schedule_node_error
:
1663 case isl_schedule_node_band
:
1664 tree
->band
= isl_schedule_band_align_params(tree
->band
, space
);
1666 return isl_schedule_tree_free(tree
);
1668 case isl_schedule_node_domain
:
1669 tree
->domain
= isl_union_set_align_params(tree
->domain
, space
);
1671 return isl_schedule_tree_free(tree
);
1673 case isl_schedule_node_filter
:
1674 tree
->filter
= isl_union_set_align_params(tree
->filter
, space
);
1676 return isl_schedule_tree_free(tree
);
1678 case isl_schedule_node_leaf
:
1679 case isl_schedule_node_sequence
:
1680 case isl_schedule_node_set
:
1681 isl_space_free(space
);
1687 isl_space_free(space
);
1688 isl_schedule_tree_free(tree
);
1692 /* Does "tree" involve the iteration domain?
1693 * That is, does it need to be modified
1694 * by isl_schedule_tree_pullback_union_pw_multi_aff?
1696 static int involves_iteration_domain(__isl_keep isl_schedule_tree
*tree
)
1701 switch (tree
->type
) {
1702 case isl_schedule_node_error
:
1704 case isl_schedule_node_band
:
1705 case isl_schedule_node_domain
:
1706 case isl_schedule_node_filter
:
1708 case isl_schedule_node_leaf
:
1709 case isl_schedule_node_sequence
:
1710 case isl_schedule_node_set
:
1715 /* Compute the pullback of the root node of "tree" by the function
1716 * represented by "upma".
1717 * In other words, plug in "upma" in the iteration domains of
1718 * the root node of "tree".
1720 * We first check if the root node involves any iteration domains.
1721 * If so, we handle the specific cases.
1723 __isl_give isl_schedule_tree
*isl_schedule_tree_pullback_union_pw_multi_aff(
1724 __isl_take isl_schedule_tree
*tree
,
1725 __isl_take isl_union_pw_multi_aff
*upma
)
1732 involves
= involves_iteration_domain(tree
);
1736 isl_union_pw_multi_aff_free(upma
);
1740 tree
= isl_schedule_tree_cow(tree
);
1744 if (tree
->type
== isl_schedule_node_band
) {
1745 tree
->band
= isl_schedule_band_pullback_union_pw_multi_aff(
1748 return isl_schedule_tree_free(tree
);
1749 } else if (tree
->type
== isl_schedule_node_domain
) {
1751 isl_union_set_preimage_union_pw_multi_aff(tree
->domain
,
1754 return isl_schedule_tree_free(tree
);
1755 } else if (tree
->type
== isl_schedule_node_filter
) {
1757 isl_union_set_preimage_union_pw_multi_aff(tree
->filter
,
1760 return isl_schedule_tree_free(tree
);
1765 isl_union_pw_multi_aff_free(upma
);
1766 isl_schedule_tree_free(tree
);
1770 /* Compute the gist of the band tree root with respect to "context".
1772 __isl_give isl_schedule_tree
*isl_schedule_tree_band_gist(
1773 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*context
)
1777 if (tree
->type
!= isl_schedule_node_band
)
1778 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1779 "not a band node", goto error
);
1780 tree
= isl_schedule_tree_cow(tree
);
1784 tree
->band
= isl_schedule_band_gist(tree
->band
, context
);
1786 return isl_schedule_tree_free(tree
);
1789 isl_union_set_free(context
);
1790 isl_schedule_tree_free(tree
);
1794 /* Are any members in "band" marked coincident?
1796 static int any_coincident(__isl_keep isl_schedule_band
*band
)
1800 n
= isl_schedule_band_n_member(band
);
1801 for (i
= 0; i
< n
; ++i
)
1802 if (isl_schedule_band_member_get_coincident(band
, i
))
1808 /* Print the band node "band" to "p".
1810 * The permutable and coincident properties are only printed if they
1811 * are different from the defaults.
1812 * The coincident property is always printed in YAML flow style.
1814 static __isl_give isl_printer
*print_tree_band(__isl_take isl_printer
*p
,
1815 __isl_keep isl_schedule_band
*band
)
1817 isl_union_set
*options
;
1820 p
= isl_printer_print_str(p
, "schedule");
1821 p
= isl_printer_yaml_next(p
);
1822 p
= isl_printer_print_str(p
, "\"");
1823 p
= isl_printer_print_multi_union_pw_aff(p
, band
->mupa
);
1824 p
= isl_printer_print_str(p
, "\"");
1825 if (isl_schedule_band_get_permutable(band
)) {
1826 p
= isl_printer_yaml_next(p
);
1827 p
= isl_printer_print_str(p
, "permutable");
1828 p
= isl_printer_yaml_next(p
);
1829 p
= isl_printer_print_int(p
, 1);
1831 if (any_coincident(band
)) {
1835 p
= isl_printer_yaml_next(p
);
1836 p
= isl_printer_print_str(p
, "coincident");
1837 p
= isl_printer_yaml_next(p
);
1838 style
= isl_printer_get_yaml_style(p
);
1839 p
= isl_printer_set_yaml_style(p
, ISL_YAML_STYLE_FLOW
);
1840 p
= isl_printer_yaml_start_sequence(p
);
1841 n
= isl_schedule_band_n_member(band
);
1842 for (i
= 0; i
< n
; ++i
) {
1843 p
= isl_printer_print_int(p
,
1844 isl_schedule_band_member_get_coincident(band
, i
));
1845 p
= isl_printer_yaml_next(p
);
1847 p
= isl_printer_yaml_end_sequence(p
);
1848 p
= isl_printer_set_yaml_style(p
, style
);
1850 options
= isl_schedule_band_get_ast_build_options(band
);
1851 empty
= isl_union_set_is_empty(options
);
1853 p
= isl_printer_free(p
);
1855 p
= isl_printer_yaml_next(p
);
1856 p
= isl_printer_print_str(p
, "options");
1857 p
= isl_printer_yaml_next(p
);
1858 p
= isl_printer_print_str(p
, "\"");
1859 p
= isl_printer_print_union_set(p
, options
);
1860 p
= isl_printer_print_str(p
, "\"");
1862 isl_union_set_free(options
);
1867 /* Print "tree" to "p".
1869 * If "n_ancestor" is non-negative, then "child_pos" contains the child
1870 * positions of a descendant of the current node that should be marked
1871 * (by the comment "YOU ARE HERE"). In particular, if "n_ancestor"
1872 * is zero, then the current node should be marked.
1873 * The marking is only printed in YAML block format.
1875 * Implicit leaf nodes are not printed, except if they correspond
1876 * to the node that should be marked.
1878 __isl_give isl_printer
*isl_printer_print_schedule_tree_mark(
1879 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
,
1880 int n_ancestor
, int *child_pos
)
1886 block
= isl_printer_get_yaml_style(p
) == ISL_YAML_STYLE_BLOCK
;
1888 p
= isl_printer_yaml_start_mapping(p
);
1889 if (n_ancestor
== 0 && block
) {
1890 p
= isl_printer_print_str(p
, "# YOU ARE HERE");
1891 p
= isl_printer_end_line(p
);
1892 p
= isl_printer_start_line(p
);
1894 switch (tree
->type
) {
1895 case isl_schedule_node_error
:
1896 p
= isl_printer_print_str(p
, "ERROR");
1898 case isl_schedule_node_leaf
:
1899 p
= isl_printer_print_str(p
, "leaf");
1901 case isl_schedule_node_sequence
:
1902 p
= isl_printer_print_str(p
, "sequence");
1905 case isl_schedule_node_set
:
1906 p
= isl_printer_print_str(p
, "set");
1909 case isl_schedule_node_domain
:
1910 p
= isl_printer_print_str(p
, "domain");
1911 p
= isl_printer_yaml_next(p
);
1912 p
= isl_printer_print_str(p
, "\"");
1913 p
= isl_printer_print_union_set(p
, tree
->domain
);
1914 p
= isl_printer_print_str(p
, "\"");
1916 case isl_schedule_node_filter
:
1917 p
= isl_printer_print_str(p
, "filter");
1918 p
= isl_printer_yaml_next(p
);
1919 p
= isl_printer_print_str(p
, "\"");
1920 p
= isl_printer_print_union_set(p
, tree
->filter
);
1921 p
= isl_printer_print_str(p
, "\"");
1923 case isl_schedule_node_band
:
1924 p
= print_tree_band(p
, tree
->band
);
1927 p
= isl_printer_yaml_next(p
);
1929 if (!tree
->children
) {
1930 if (n_ancestor
> 0 && block
) {
1931 isl_schedule_tree
*leaf
;
1933 p
= isl_printer_print_str(p
, "child");
1934 p
= isl_printer_yaml_next(p
);
1935 leaf
= isl_schedule_tree_leaf(isl_printer_get_ctx(p
));
1936 p
= isl_printer_print_schedule_tree_mark(p
,
1938 isl_schedule_tree_free(leaf
);
1939 p
= isl_printer_yaml_next(p
);
1941 return isl_printer_yaml_end_mapping(p
);
1945 p
= isl_printer_yaml_start_sequence(p
);
1947 p
= isl_printer_print_str(p
, "child");
1948 p
= isl_printer_yaml_next(p
);
1951 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1952 for (i
= 0; i
< n
; ++i
) {
1953 isl_schedule_tree
*t
;
1955 t
= isl_schedule_tree_get_child(tree
, i
);
1956 if (n_ancestor
> 0 && child_pos
[0] == i
)
1957 p
= isl_printer_print_schedule_tree_mark(p
, t
,
1958 n_ancestor
- 1, child_pos
+ 1);
1960 p
= isl_printer_print_schedule_tree_mark(p
, t
,
1962 isl_schedule_tree_free(t
);
1964 p
= isl_printer_yaml_next(p
);
1968 p
= isl_printer_yaml_end_sequence(p
);
1969 p
= isl_printer_yaml_end_mapping(p
);
1974 /* Print "tree" to "p".
1976 __isl_give isl_printer
*isl_printer_print_schedule_tree(
1977 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
)
1979 return isl_printer_print_schedule_tree_mark(p
, tree
, -1, NULL
);
1982 void isl_schedule_tree_dump(__isl_keep isl_schedule_tree
*tree
)
1985 isl_printer
*printer
;
1990 ctx
= isl_schedule_tree_get_ctx(tree
);
1991 printer
= isl_printer_to_file(ctx
, stderr
);
1992 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
1993 printer
= isl_printer_print_schedule_tree(printer
, tree
);
1995 isl_printer_free(printer
);