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 static __isl_give isl_schedule_tree
*isl_schedule_tree_alloc(isl_ctx
*ctx
,
39 enum isl_schedule_node_type type
)
41 isl_schedule_tree
*tree
;
43 if (type
== isl_schedule_node_error
)
46 tree
= isl_calloc_type(ctx
, isl_schedule_tree
);
58 /* Return a fresh copy of "tree".
60 __isl_take isl_schedule_tree
*isl_schedule_tree_dup(
61 __isl_keep isl_schedule_tree
*tree
)
64 isl_schedule_tree
*dup
;
69 ctx
= isl_schedule_tree_get_ctx(tree
);
70 dup
= isl_schedule_tree_alloc(ctx
, tree
->type
);
75 case isl_schedule_node_error
:
76 isl_die(ctx
, isl_error_internal
,
77 "allocation should have failed",
78 isl_schedule_tree_free(dup
));
79 case isl_schedule_node_band
:
80 dup
->band
= isl_schedule_band_copy(tree
->band
);
82 return isl_schedule_tree_free(dup
);
84 case isl_schedule_node_domain
:
85 dup
->domain
= isl_union_set_copy(tree
->domain
);
87 return isl_schedule_tree_free(dup
);
89 case isl_schedule_node_filter
:
90 dup
->filter
= isl_union_set_copy(tree
->filter
);
92 return isl_schedule_tree_free(dup
);
94 case isl_schedule_node_leaf
:
95 case isl_schedule_node_sequence
:
96 case isl_schedule_node_set
:
100 if (tree
->children
) {
101 dup
->children
= isl_schedule_tree_list_copy(tree
->children
);
103 return isl_schedule_tree_free(dup
);
109 /* Return an isl_schedule_tree that is equal to "tree" and that has only
110 * a single reference.
112 * This function is called before a tree is modified.
113 * A static tree (with negative reference count) should never be modified,
114 * so it is not allowed to call this function on a static tree.
116 __isl_give isl_schedule_tree
*isl_schedule_tree_cow(
117 __isl_take isl_schedule_tree
*tree
)
123 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
124 "static trees cannot be modified",
125 return isl_schedule_tree_free(tree
));
130 return isl_schedule_tree_dup(tree
);
133 /* Return a new reference to "tree".
135 * A static tree (with negative reference count) does not keep track
136 * of the number of references and should not be modified.
138 __isl_give isl_schedule_tree
*isl_schedule_tree_copy(
139 __isl_keep isl_schedule_tree
*tree
)
151 /* Free "tree" and return NULL.
153 __isl_null isl_schedule_tree
*isl_schedule_tree_free(
154 __isl_take isl_schedule_tree
*tree
)
163 switch (tree
->type
) {
164 case isl_schedule_node_band
:
165 isl_schedule_band_free(tree
->band
);
167 case isl_schedule_node_domain
:
168 isl_union_set_free(tree
->domain
);
170 case isl_schedule_node_filter
:
171 isl_union_set_free(tree
->filter
);
173 case isl_schedule_node_sequence
:
174 case isl_schedule_node_set
:
175 case isl_schedule_node_error
:
176 case isl_schedule_node_leaf
:
179 isl_schedule_tree_list_free(tree
->children
);
180 isl_ctx_deref(tree
->ctx
);
186 /* Create and return a new leaf schedule tree.
188 __isl_give isl_schedule_tree
*isl_schedule_tree_leaf(isl_ctx
*ctx
)
190 return isl_schedule_tree_alloc(ctx
, isl_schedule_node_leaf
);
193 /* Create a new band schedule tree referring to "band"
196 __isl_give isl_schedule_tree
*isl_schedule_tree_from_band(
197 __isl_take isl_schedule_band
*band
)
200 isl_schedule_tree
*tree
;
205 ctx
= isl_schedule_band_get_ctx(band
);
206 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_band
);
214 isl_schedule_band_free(band
);
218 /* Create a new domain schedule tree with the given domain and no children.
220 __isl_give isl_schedule_tree
*isl_schedule_tree_from_domain(
221 __isl_take isl_union_set
*domain
)
224 isl_schedule_tree
*tree
;
229 ctx
= isl_union_set_get_ctx(domain
);
230 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_domain
);
234 tree
->domain
= domain
;
238 isl_union_set_free(domain
);
242 /* Create a new filter schedule tree with the given filter and no children.
244 __isl_give isl_schedule_tree
*isl_schedule_tree_from_filter(
245 __isl_take isl_union_set
*filter
)
248 isl_schedule_tree
*tree
;
253 ctx
= isl_union_set_get_ctx(filter
);
254 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_filter
);
258 tree
->filter
= filter
;
262 isl_union_set_free(filter
);
266 /* Create a new tree of the given type (isl_schedule_node_sequence or
267 * isl_schedule_node_set) with the given children.
269 __isl_give isl_schedule_tree
*isl_schedule_tree_from_children(
270 enum isl_schedule_node_type type
,
271 __isl_take isl_schedule_tree_list
*list
)
274 isl_schedule_tree
*tree
;
279 ctx
= isl_schedule_tree_list_get_ctx(list
);
280 tree
= isl_schedule_tree_alloc(ctx
, type
);
284 tree
->children
= list
;
288 isl_schedule_tree_list_free(list
);
292 /* Construct a tree with a root node of type "type" and as children
293 * "tree1" and "tree2".
294 * If the root of one (or both) of the input trees is itself of type "type",
295 * then the tree is replaced by its children.
297 __isl_give isl_schedule_tree
*isl_schedule_tree_from_pair(
298 enum isl_schedule_node_type type
, __isl_take isl_schedule_tree
*tree1
,
299 __isl_take isl_schedule_tree
*tree2
)
302 isl_schedule_tree_list
*list
;
304 if (!tree1
|| !tree2
)
307 ctx
= isl_schedule_tree_get_ctx(tree1
);
308 if (isl_schedule_tree_get_type(tree1
) == type
) {
309 list
= isl_schedule_tree_list_copy(tree1
->children
);
310 isl_schedule_tree_free(tree1
);
312 list
= isl_schedule_tree_list_alloc(ctx
, 2);
313 list
= isl_schedule_tree_list_add(list
, tree1
);
315 if (isl_schedule_tree_get_type(tree2
) == type
) {
316 isl_schedule_tree_list
*children
;
318 children
= isl_schedule_tree_list_copy(tree2
->children
);
319 list
= isl_schedule_tree_list_concat(list
, children
);
320 isl_schedule_tree_free(tree2
);
322 list
= isl_schedule_tree_list_add(list
, tree2
);
325 return isl_schedule_tree_from_children(type
, list
);
327 isl_schedule_tree_free(tree1
);
328 isl_schedule_tree_free(tree2
);
332 /* Return the isl_ctx to which "tree" belongs.
334 isl_ctx
*isl_schedule_tree_get_ctx(__isl_keep isl_schedule_tree
*tree
)
336 return tree
? tree
->ctx
: NULL
;
339 /* Return the type of the root of the tree or isl_schedule_node_error
342 enum isl_schedule_node_type
isl_schedule_tree_get_type(
343 __isl_keep isl_schedule_tree
*tree
)
345 return tree
? tree
->type
: isl_schedule_node_error
;
348 /* Are "tree1" and "tree2" obviously equal to each other?
350 int isl_schedule_tree_plain_is_equal(__isl_keep isl_schedule_tree
*tree1
,
351 __isl_keep isl_schedule_tree
*tree2
)
356 if (!tree1
|| !tree2
)
360 if (tree1
->type
!= tree2
->type
)
363 switch (tree1
->type
) {
364 case isl_schedule_node_band
:
365 equal
= isl_schedule_band_plain_is_equal(tree1
->band
,
368 case isl_schedule_node_domain
:
369 equal
= isl_union_set_is_equal(tree1
->domain
, tree2
->domain
);
371 case isl_schedule_node_filter
:
372 equal
= isl_union_set_is_equal(tree1
->filter
, tree2
->filter
);
374 case isl_schedule_node_leaf
:
375 case isl_schedule_node_sequence
:
376 case isl_schedule_node_set
:
379 case isl_schedule_node_error
:
384 if (equal
< 0 || !equal
)
387 n
= isl_schedule_tree_n_children(tree1
);
388 if (n
!= isl_schedule_tree_n_children(tree2
))
390 for (i
= 0; i
< n
; ++i
) {
391 isl_schedule_tree
*child1
, *child2
;
393 child1
= isl_schedule_tree_get_child(tree1
, i
);
394 child2
= isl_schedule_tree_get_child(tree2
, i
);
395 equal
= isl_schedule_tree_plain_is_equal(child1
, child2
);
396 isl_schedule_tree_free(child1
);
397 isl_schedule_tree_free(child2
);
399 if (equal
< 0 || !equal
)
406 /* Does "tree" have any children, other than an implicit leaf.
408 int isl_schedule_tree_has_children(__isl_keep isl_schedule_tree
*tree
)
413 return tree
->children
!= NULL
;
416 /* Return the number of children of "tree", excluding implicit leaves.
418 int isl_schedule_tree_n_children(__isl_keep isl_schedule_tree
*tree
)
423 return isl_schedule_tree_list_n_schedule_tree(tree
->children
);
426 /* Return a copy of the (explicit) child at position "pos" of "tree".
428 __isl_give isl_schedule_tree
*isl_schedule_tree_get_child(
429 __isl_keep isl_schedule_tree
*tree
, int pos
)
434 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
435 "schedule tree has no explicit children", return NULL
);
436 return isl_schedule_tree_list_get_schedule_tree(tree
->children
, pos
);
439 /* Return a copy of the (explicit) child at position "pos" of "tree" and
442 __isl_give isl_schedule_tree
*isl_schedule_tree_child(
443 __isl_take isl_schedule_tree
*tree
, int pos
)
445 isl_schedule_tree
*child
;
447 child
= isl_schedule_tree_get_child(tree
, pos
);
448 isl_schedule_tree_free(tree
);
452 /* Remove all (explicit) children from "tree".
454 __isl_give isl_schedule_tree
*isl_schedule_tree_reset_children(
455 __isl_take isl_schedule_tree
*tree
)
457 tree
= isl_schedule_tree_cow(tree
);
460 tree
->children
= isl_schedule_tree_list_free(tree
->children
);
464 /* Remove the child at position "pos" from the children of "tree".
465 * If there was only one child to begin with, then remove all children.
467 __isl_give isl_schedule_tree
*isl_schedule_tree_drop_child(
468 __isl_take isl_schedule_tree
*tree
, int pos
)
472 tree
= isl_schedule_tree_cow(tree
);
476 if (!isl_schedule_tree_has_children(tree
))
477 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
478 "tree does not have any explicit children",
479 return isl_schedule_tree_free(tree
));
480 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
481 if (pos
< 0 || pos
>= n
)
482 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
483 "position out of bounds",
484 return isl_schedule_tree_free(tree
));
486 return isl_schedule_tree_reset_children(tree
);
488 tree
->children
= isl_schedule_tree_list_drop(tree
->children
, pos
, 1);
490 return isl_schedule_tree_free(tree
);
495 /* Replace the child at position "pos" of "tree" by "child".
497 * If the new child is a leaf, then it is not explicitly
498 * recorded in the list of children. Instead, the list of children
499 * (which is assumed to have only one element) is removed.
500 * Note that the children of set and sequence nodes are always
501 * filters, so they cannot be replaced by empty trees.
503 __isl_give isl_schedule_tree
*isl_schedule_tree_replace_child(
504 __isl_take isl_schedule_tree
*tree
, int pos
,
505 __isl_take isl_schedule_tree
*child
)
507 tree
= isl_schedule_tree_cow(tree
);
511 if (isl_schedule_tree_is_leaf(child
)) {
512 isl_schedule_tree_free(child
);
513 if (!tree
->children
&& pos
== 0)
515 if (isl_schedule_tree_n_children(tree
) != 1)
516 isl_die(isl_schedule_tree_get_ctx(tree
),
518 "can only replace single child by leaf",
520 return isl_schedule_tree_reset_children(tree
);
523 if (!tree
->children
&& pos
== 0)
525 isl_schedule_tree_list_from_schedule_tree(child
);
527 tree
->children
= isl_schedule_tree_list_set_schedule_tree(
528 tree
->children
, pos
, child
);
531 return isl_schedule_tree_free(tree
);
535 isl_schedule_tree_free(tree
);
536 isl_schedule_tree_free(child
);
540 /* Replace the (explicit) children of "tree" by "children"?
542 __isl_give isl_schedule_tree
*isl_schedule_tree_set_children(
543 __isl_take isl_schedule_tree
*tree
,
544 __isl_take isl_schedule_tree_list
*children
)
546 tree
= isl_schedule_tree_cow(tree
);
547 if (!tree
|| !children
)
549 isl_schedule_tree_list_free(tree
->children
);
550 tree
->children
= children
;
553 isl_schedule_tree_free(tree
);
554 isl_schedule_tree_list_free(children
);
558 /* Create a new band schedule tree referring to "band"
559 * with "tree" as single child.
561 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_band(
562 __isl_take isl_schedule_tree
*tree
, __isl_take isl_schedule_band
*band
)
564 isl_schedule_tree
*res
;
566 res
= isl_schedule_tree_from_band(band
);
567 return isl_schedule_tree_replace_child(res
, 0, tree
);
570 /* Create a new domain schedule tree with the given domain and
571 * with "tree" as single child.
573 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_domain(
574 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
576 isl_schedule_tree
*res
;
578 res
= isl_schedule_tree_from_domain(domain
);
579 return isl_schedule_tree_replace_child(res
, 0, tree
);
582 /* Create a new filter schedule tree with the given filter and single child.
584 * If the root of "tree" is itself a filter node, then the two
585 * filter nodes are merged into one node.
587 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_filter(
588 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
590 isl_schedule_tree
*res
;
592 if (isl_schedule_tree_get_type(tree
) == isl_schedule_node_filter
) {
593 isl_union_set
*tree_filter
;
595 tree_filter
= isl_schedule_tree_filter_get_filter(tree
);
596 tree_filter
= isl_union_set_intersect(tree_filter
, filter
);
597 tree
= isl_schedule_tree_filter_set_filter(tree
, tree_filter
);
601 res
= isl_schedule_tree_from_filter(filter
);
602 return isl_schedule_tree_replace_child(res
, 0, tree
);
605 /* Insert a filter node with filter set "filter"
606 * in each of the children of "tree".
608 __isl_give isl_schedule_tree
*isl_schedule_tree_children_insert_filter(
609 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
613 if (!tree
|| !filter
)
616 n
= isl_schedule_tree_n_children(tree
);
617 for (i
= 0; i
< n
; ++i
) {
618 isl_schedule_tree
*child
;
620 child
= isl_schedule_tree_get_child(tree
, i
);
621 child
= isl_schedule_tree_insert_filter(child
,
622 isl_union_set_copy(filter
));
623 tree
= isl_schedule_tree_replace_child(tree
, i
, child
);
626 isl_union_set_free(filter
);
629 isl_union_set_free(filter
);
630 isl_schedule_tree_free(tree
);
634 /* Return the number of members in the band tree root.
636 unsigned isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree
*tree
)
641 if (tree
->type
!= isl_schedule_node_band
)
642 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
643 "not a band node", return 0);
645 return isl_schedule_band_n_member(tree
->band
);
648 /* Is the band member at position "pos" of the band tree root
651 int isl_schedule_tree_band_member_get_coincident(
652 __isl_keep isl_schedule_tree
*tree
, int pos
)
657 if (tree
->type
!= isl_schedule_node_band
)
658 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
659 "not a band node", return -1);
661 return isl_schedule_band_member_get_coincident(tree
->band
, pos
);
664 /* Mark the given band member as being coincident or not
665 * according to "coincident".
667 __isl_give isl_schedule_tree
*isl_schedule_tree_band_member_set_coincident(
668 __isl_take isl_schedule_tree
*tree
, int pos
, int coincident
)
672 if (tree
->type
!= isl_schedule_node_band
)
673 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
674 "not a band node", return isl_schedule_tree_free(tree
));
675 if (isl_schedule_tree_band_member_get_coincident(tree
, pos
) ==
678 tree
= isl_schedule_tree_cow(tree
);
682 tree
->band
= isl_schedule_band_member_set_coincident(tree
->band
, pos
,
685 return isl_schedule_tree_free(tree
);
689 /* Is the band tree root marked permutable?
691 int isl_schedule_tree_band_get_permutable(__isl_keep isl_schedule_tree
*tree
)
696 if (tree
->type
!= isl_schedule_node_band
)
697 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
698 "not a band node", return -1);
700 return isl_schedule_band_get_permutable(tree
->band
);
703 /* Mark the band tree root permutable or not according to "permutable"?
705 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_permutable(
706 __isl_take isl_schedule_tree
*tree
, int permutable
)
710 if (tree
->type
!= isl_schedule_node_band
)
711 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
712 "not a band node", return isl_schedule_tree_free(tree
));
713 if (isl_schedule_tree_band_get_permutable(tree
) == permutable
)
715 tree
= isl_schedule_tree_cow(tree
);
719 tree
->band
= isl_schedule_band_set_permutable(tree
->band
, permutable
);
721 return isl_schedule_tree_free(tree
);
725 /* Return the schedule space of the band tree root.
727 __isl_give isl_space
*isl_schedule_tree_band_get_space(
728 __isl_keep isl_schedule_tree
*tree
)
733 if (tree
->type
!= isl_schedule_node_band
)
734 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
735 "not a band node", return NULL
);
737 return isl_schedule_band_get_space(tree
->band
);
740 /* Return the schedule of the band tree root in isolation.
742 __isl_give isl_multi_union_pw_aff
*isl_schedule_tree_band_get_partial_schedule(
743 __isl_keep isl_schedule_tree
*tree
)
748 if (tree
->type
!= isl_schedule_node_band
)
749 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
750 "not a band node", return NULL
);
752 return isl_schedule_band_get_partial_schedule(tree
->band
);
755 /* Return the loop AST generation type for the band member
756 * of the band tree root at position "pos".
758 enum isl_ast_loop_type
isl_schedule_tree_band_member_get_ast_loop_type(
759 __isl_keep isl_schedule_tree
*tree
, int pos
)
762 return isl_ast_loop_error
;
764 if (tree
->type
!= isl_schedule_node_band
)
765 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
766 "not a band node", return isl_ast_loop_error
);
768 return isl_schedule_band_member_get_ast_loop_type(tree
->band
, pos
);
771 /* Set the loop AST generation type for the band member of the band tree root
772 * at position "pos" to "type".
774 __isl_give isl_schedule_tree
*isl_schedule_tree_band_member_set_ast_loop_type(
775 __isl_take isl_schedule_tree
*tree
, int pos
,
776 enum isl_ast_loop_type type
)
778 tree
= isl_schedule_tree_cow(tree
);
782 if (tree
->type
!= isl_schedule_node_band
)
783 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
784 "not a band node", return isl_schedule_tree_free(tree
));
786 tree
->band
= isl_schedule_band_member_set_ast_loop_type(tree
->band
,
789 return isl_schedule_tree_free(tree
);
794 /* Return the AST build options associated to the band tree root.
796 __isl_give isl_union_set
*isl_schedule_tree_band_get_ast_build_options(
797 __isl_keep isl_schedule_tree
*tree
)
802 if (tree
->type
!= isl_schedule_node_band
)
803 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
804 "not a band node", return NULL
);
806 return isl_schedule_band_get_ast_build_options(tree
->band
);
809 /* Replace the AST build options associated to band tree root by "options".
811 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_ast_build_options(
812 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*options
)
814 tree
= isl_schedule_tree_cow(tree
);
815 if (!tree
|| !options
)
818 if (tree
->type
!= isl_schedule_node_band
)
819 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
820 "not a band node", goto error
);
822 tree
->band
= isl_schedule_band_set_ast_build_options(tree
->band
,
825 return isl_schedule_tree_free(tree
);
829 isl_schedule_tree_free(tree
);
830 isl_union_set_free(options
);
834 /* Return the domain of the domain tree root.
836 __isl_give isl_union_set
*isl_schedule_tree_domain_get_domain(
837 __isl_keep isl_schedule_tree
*tree
)
842 if (tree
->type
!= isl_schedule_node_domain
)
843 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
844 "not a domain node", return NULL
);
846 return isl_union_set_copy(tree
->domain
);
849 /* Replace the domain of domain tree root "tree" by "domain".
851 __isl_give isl_schedule_tree
*isl_schedule_tree_domain_set_domain(
852 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
854 tree
= isl_schedule_tree_cow(tree
);
855 if (!tree
|| !domain
)
858 if (tree
->type
!= isl_schedule_node_domain
)
859 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
860 "not a domain node", goto error
);
862 isl_union_set_free(tree
->domain
);
863 tree
->domain
= domain
;
867 isl_schedule_tree_free(tree
);
868 isl_union_set_free(domain
);
872 /* Return the filter of the filter tree root.
874 __isl_give isl_union_set
*isl_schedule_tree_filter_get_filter(
875 __isl_keep isl_schedule_tree
*tree
)
880 if (tree
->type
!= isl_schedule_node_filter
)
881 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
882 "not a filter node", return NULL
);
884 return isl_union_set_copy(tree
->filter
);
887 /* Replace the filter of the filter tree root by "filter".
889 __isl_give isl_schedule_tree
*isl_schedule_tree_filter_set_filter(
890 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
892 tree
= isl_schedule_tree_cow(tree
);
893 if (!tree
|| !filter
)
896 if (tree
->type
!= isl_schedule_node_filter
)
897 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
898 "not a filter node", return NULL
);
900 isl_union_set_free(tree
->filter
);
901 tree
->filter
= filter
;
905 isl_schedule_tree_free(tree
);
906 isl_union_set_free(filter
);
910 /* Set dim to the range dimension of "map" and abort the search.
912 static int set_range_dim(__isl_take isl_map
*map
, void *user
)
916 *dim
= isl_map_dim(map
, isl_dim_out
);
922 /* Return the dimension of the range of "umap".
923 * "umap" is assumed not to be empty and
924 * all maps inside "umap" are assumed to have the same range.
926 * We extract the range dimension from the first map in "umap".
928 static int range_dim(__isl_keep isl_union_map
*umap
)
934 if (isl_union_map_n_map(umap
) == 0)
935 isl_die(isl_union_map_get_ctx(umap
), isl_error_internal
,
936 "unexpected empty input", return -1);
938 isl_union_map_foreach_map(umap
, &set_range_dim
, &dim
);
943 /* Append an "extra" number of zeros to the range of "umap" and
946 static __isl_give isl_union_map
*append_range(__isl_take isl_union_map
*umap
,
952 isl_union_pw_multi_aff
*suffix
;
953 isl_union_map
*universe
;
954 isl_union_map
*suffix_umap
;
956 universe
= isl_union_map_universe(isl_union_map_copy(umap
));
957 dom
= isl_union_map_domain(universe
);
958 space
= isl_union_set_get_space(dom
);
959 space
= isl_space_set_from_params(space
);
960 space
= isl_space_add_dims(space
, isl_dim_set
, extra
);
961 mv
= isl_multi_val_zero(space
);
963 suffix
= isl_union_pw_multi_aff_multi_val_on_domain(dom
, mv
);
964 suffix_umap
= isl_union_map_from_union_pw_multi_aff(suffix
);
965 umap
= isl_union_map_flat_range_product(umap
, suffix_umap
);
970 /* Move down to the first descendant of "tree" that contains any schedule
971 * information or return "leaf" if there is no such descendant.
973 __isl_give isl_schedule_tree
*isl_schedule_tree_first_schedule_descendant(
974 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_tree
*leaf
)
976 while (isl_schedule_tree_get_type(tree
) == isl_schedule_node_band
&&
977 isl_schedule_tree_band_n_member(tree
) == 0) {
978 if (!isl_schedule_tree_has_children(tree
)) {
979 isl_schedule_tree_free(tree
);
980 return isl_schedule_tree_copy(leaf
);
982 tree
= isl_schedule_tree_child(tree
, 0);
988 static __isl_give isl_union_map
*subtree_schedule_extend(
989 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
);
991 /* Extend the schedule map "outer" with the subtree schedule
992 * of the (single) child of "tree", if any.
994 * If "tree" does not have any descendants (apart from those that
995 * do not carry any schedule information), then we simply return "outer".
996 * Otherwise, we extend the schedule map "outer" with the subtree schedule
997 * of the single child.
999 static __isl_give isl_union_map
*subtree_schedule_extend_child(
1000 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1002 isl_schedule_tree
*child
;
1006 return isl_union_map_free(outer
);
1007 if (!isl_schedule_tree_has_children(tree
))
1009 child
= isl_schedule_tree_get_child(tree
, 0);
1011 return isl_union_map_free(outer
);
1012 res
= subtree_schedule_extend(child
, outer
);
1013 isl_schedule_tree_free(child
);
1017 /* Extract the parameter space from one of the children of "tree",
1018 * which are assumed to be filters.
1020 static __isl_give isl_space
*extract_space_from_filter_child(
1021 __isl_keep isl_schedule_tree
*tree
)
1025 isl_schedule_tree
*child
;
1027 child
= isl_schedule_tree_list_get_schedule_tree(tree
->children
, 0);
1028 dom
= isl_schedule_tree_filter_get_filter(child
);
1029 space
= isl_union_set_get_space(dom
);
1030 isl_union_set_free(dom
);
1031 isl_schedule_tree_free(child
);
1036 /* Extend the schedule map "outer" with the subtree schedule
1037 * of a set or sequence node.
1039 * The schedule for the set or sequence node itself is composed of
1040 * pieces of the form
1048 * The first form is used if there is only a single child or
1049 * if the current node is a set node and the schedule_separate_components
1050 * option is not set.
1052 * Each of the pieces above is extended with the subtree schedule of
1053 * the child of the corresponding filter, if any, padded with zeros
1054 * to ensure that all pieces have the same range dimension.
1056 static __isl_give isl_union_map
*subtree_schedule_extend_from_children(
1057 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1066 isl_union_map
*umap
;
1071 ctx
= isl_schedule_tree_get_ctx(tree
);
1072 if (!tree
->children
)
1073 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1074 "missing children", return NULL
);
1075 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1077 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1078 "missing children", return NULL
);
1080 separate
= n
> 1 && (tree
->type
== isl_schedule_node_sequence
||
1081 isl_options_get_schedule_separate_components(ctx
));
1083 space
= extract_space_from_filter_child(tree
);
1085 umap
= isl_union_map_empty(isl_space_copy(space
));
1086 space
= isl_space_set_from_params(space
);
1088 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1089 v
= isl_val_zero(ctx
);
1091 mv
= isl_multi_val_zero(space
);
1093 dim
= isl_multi_val_dim(mv
, isl_dim_set
);
1094 for (i
= 0; i
< n
; ++i
) {
1095 isl_union_pw_multi_aff
*upma
;
1096 isl_union_map
*umap_i
;
1098 isl_schedule_tree
*child
;
1102 child
= isl_schedule_tree_list_get_schedule_tree(
1104 dom
= isl_schedule_tree_filter_get_filter(child
);
1107 mv
= isl_multi_val_set_val(mv
, 0, isl_val_copy(v
));
1108 v
= isl_val_add_ui(v
, 1);
1110 upma
= isl_union_pw_multi_aff_multi_val_on_domain(dom
,
1111 isl_multi_val_copy(mv
));
1112 umap_i
= isl_union_map_from_union_pw_multi_aff(upma
);
1113 umap_i
= isl_union_map_flat_range_product(
1114 isl_union_map_copy(outer
), umap_i
);
1115 umap_i
= subtree_schedule_extend_child(child
, umap_i
);
1116 isl_schedule_tree_free(child
);
1118 empty
= isl_union_map_is_empty(umap_i
);
1120 umap_i
= isl_union_map_free(umap_i
);
1122 isl_union_map_free(umap_i
);
1126 dim_i
= range_dim(umap_i
);
1128 umap
= isl_union_map_free(umap
);
1129 } else if (dim
< dim_i
) {
1130 umap
= append_range(umap
, dim_i
- dim
);
1132 } else if (dim_i
< dim
) {
1133 umap_i
= append_range(umap_i
, dim
- dim_i
);
1135 umap
= isl_union_map_union(umap
, umap_i
);
1139 isl_multi_val_free(mv
);
1140 isl_union_map_free(outer
);
1145 /* Extend the schedule map "outer" with the subtree schedule of "tree".
1147 * If the root of the tree is a set or a sequence, then we extend
1148 * the schedule map in subtree_schedule_extend_from_children.
1149 * Otherwise, we extend the schedule map with the partial schedule
1150 * corresponding to the root of the tree and then continue with
1151 * the single child of this root.
1153 static __isl_give isl_union_map
*subtree_schedule_extend(
1154 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
1156 isl_multi_union_pw_aff
*mupa
;
1157 isl_union_map
*umap
;
1158 isl_union_set
*domain
;
1163 switch (tree
->type
) {
1164 case isl_schedule_node_error
:
1165 return isl_union_map_free(outer
);
1166 case isl_schedule_node_band
:
1167 if (isl_schedule_tree_band_n_member(tree
) == 0)
1168 return subtree_schedule_extend_child(tree
, outer
);
1169 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1170 umap
= isl_union_map_from_multi_union_pw_aff(mupa
);
1171 outer
= isl_union_map_flat_range_product(outer
, umap
);
1172 umap
= subtree_schedule_extend_child(tree
, outer
);
1174 case isl_schedule_node_domain
:
1175 domain
= isl_schedule_tree_domain_get_domain(tree
);
1176 umap
= isl_union_map_from_domain(domain
);
1177 outer
= isl_union_map_flat_range_product(outer
, umap
);
1178 umap
= subtree_schedule_extend_child(tree
, outer
);
1180 case isl_schedule_node_filter
:
1181 domain
= isl_schedule_tree_filter_get_filter(tree
);
1182 umap
= isl_union_map_from_domain(domain
);
1183 outer
= isl_union_map_flat_range_product(outer
, umap
);
1184 umap
= subtree_schedule_extend_child(tree
, outer
);
1186 case isl_schedule_node_leaf
:
1187 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1188 "leaf node should be handled by caller", return NULL
);
1189 case isl_schedule_node_set
:
1190 case isl_schedule_node_sequence
:
1191 umap
= subtree_schedule_extend_from_children(tree
, outer
);
1198 static __isl_give isl_union_set
*initial_domain(
1199 __isl_keep isl_schedule_tree
*tree
);
1201 /* Extract a universe domain from the children of the tree root "tree",
1202 * which is a set or sequence, meaning that its children are filters.
1203 * In particular, return the union of the universes of the filters.
1205 static __isl_give isl_union_set
*initial_domain_from_children(
1206 __isl_keep isl_schedule_tree
*tree
)
1210 isl_union_set
*domain
;
1212 if (!tree
->children
)
1213 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1214 "missing children", return NULL
);
1215 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1217 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1218 "missing children", return NULL
);
1220 space
= extract_space_from_filter_child(tree
);
1221 domain
= isl_union_set_empty(space
);
1223 for (i
= 0; i
< n
; ++i
) {
1224 isl_schedule_tree
*child
;
1225 isl_union_set
*domain_i
;
1227 child
= isl_schedule_tree_get_child(tree
, i
);
1228 domain_i
= initial_domain(child
);
1229 domain
= isl_union_set_union(domain
, domain_i
);
1230 isl_schedule_tree_free(child
);
1236 /* Extract a universe domain from the tree root "tree".
1237 * The caller is responsible for making sure that this node
1238 * would not be skipped by isl_schedule_tree_first_schedule_descendant
1239 * and that it is not a leaf node.
1241 static __isl_give isl_union_set
*initial_domain(
1242 __isl_keep isl_schedule_tree
*tree
)
1244 isl_multi_union_pw_aff
*mupa
;
1245 isl_union_set
*domain
;
1250 switch (tree
->type
) {
1251 case isl_schedule_node_error
:
1253 case isl_schedule_node_band
:
1254 if (isl_schedule_tree_band_n_member(tree
) == 0)
1255 isl_die(isl_schedule_tree_get_ctx(tree
),
1257 "0D band should be handled by caller",
1259 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1260 domain
= isl_multi_union_pw_aff_domain(mupa
);
1261 domain
= isl_union_set_universe(domain
);
1263 case isl_schedule_node_domain
:
1264 domain
= isl_schedule_tree_domain_get_domain(tree
);
1265 domain
= isl_union_set_universe(domain
);
1267 case isl_schedule_node_filter
:
1268 domain
= isl_schedule_tree_filter_get_filter(tree
);
1269 domain
= isl_union_set_universe(domain
);
1271 case isl_schedule_node_leaf
:
1272 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1273 "leaf node should be handled by caller", return NULL
);
1274 case isl_schedule_node_set
:
1275 case isl_schedule_node_sequence
:
1276 domain
= initial_domain_from_children(tree
);
1283 /* Return the subtree schedule of a node that contains some schedule
1284 * information, i.e., a node that would not be skipped by
1285 * isl_schedule_tree_first_schedule_descendant and that is not a leaf.
1287 * We start with an initial zero-dimensional subtree schedule based
1288 * on the domain information in the root node and then extend it
1289 * based on the schedule information in the root node and its descendants.
1291 __isl_give isl_union_map
*isl_schedule_tree_get_subtree_schedule_union_map(
1292 __isl_keep isl_schedule_tree
*tree
)
1294 isl_union_set
*domain
;
1295 isl_union_map
*umap
;
1297 domain
= initial_domain(tree
);
1298 umap
= isl_union_map_from_domain(domain
);
1299 return subtree_schedule_extend(tree
, umap
);
1302 /* Multiply the partial schedule of the band root node of "tree"
1303 * with the factors in "mv".
1305 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale(
1306 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
1310 if (tree
->type
!= isl_schedule_node_band
)
1311 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1312 "not a band node", goto error
);
1314 tree
= isl_schedule_tree_cow(tree
);
1318 tree
->band
= isl_schedule_band_scale(tree
->band
, mv
);
1320 return isl_schedule_tree_free(tree
);
1324 isl_schedule_tree_free(tree
);
1325 isl_multi_val_free(mv
);
1329 /* Divide the partial schedule of the band root node of "tree"
1330 * by the factors in "mv".
1332 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale_down(
1333 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
1337 if (tree
->type
!= isl_schedule_node_band
)
1338 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1339 "not a band node", goto error
);
1341 tree
= isl_schedule_tree_cow(tree
);
1345 tree
->band
= isl_schedule_band_scale_down(tree
->band
, mv
);
1347 return isl_schedule_tree_free(tree
);
1351 isl_schedule_tree_free(tree
);
1352 isl_multi_val_free(mv
);
1356 /* Tile the band root node of "tree" with tile sizes "sizes".
1358 * We duplicate the band node, change the schedule of one of them
1359 * to the tile schedule and the other to the point schedule and then
1360 * attach the point band as a child to the tile band.
1362 __isl_give isl_schedule_tree
*isl_schedule_tree_band_tile(
1363 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*sizes
)
1365 isl_schedule_tree
*child
= NULL
;
1367 if (!tree
|| !sizes
)
1369 if (tree
->type
!= isl_schedule_node_band
)
1370 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1371 "not a band node", goto error
);
1373 child
= isl_schedule_tree_copy(tree
);
1374 tree
= isl_schedule_tree_cow(tree
);
1375 child
= isl_schedule_tree_cow(child
);
1376 if (!tree
|| !child
)
1379 tree
->band
= isl_schedule_band_tile(tree
->band
,
1380 isl_multi_val_copy(sizes
));
1383 child
->band
= isl_schedule_band_point(child
->band
, tree
->band
, sizes
);
1385 child
= isl_schedule_tree_free(child
);
1387 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
1391 isl_schedule_tree_free(child
);
1392 isl_schedule_tree_free(tree
);
1393 isl_multi_val_free(sizes
);
1397 /* Split the band root node of "tree" into two nested band nodes,
1398 * one with the first "pos" dimensions and
1399 * one with the remaining dimensions.
1401 __isl_give isl_schedule_tree
*isl_schedule_tree_band_split(
1402 __isl_take isl_schedule_tree
*tree
, int pos
)
1405 isl_schedule_tree
*child
;
1409 if (tree
->type
!= isl_schedule_node_band
)
1410 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1411 "not a band node", return isl_schedule_tree_free(tree
));
1413 n
= isl_schedule_tree_band_n_member(tree
);
1414 if (pos
< 0 || pos
> n
)
1415 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1416 "position out of bounds",
1417 return isl_schedule_tree_free(tree
));
1419 child
= isl_schedule_tree_copy(tree
);
1420 tree
= isl_schedule_tree_cow(tree
);
1421 child
= isl_schedule_tree_cow(child
);
1422 if (!tree
|| !child
)
1425 child
->band
= isl_schedule_band_drop(child
->band
, 0, pos
);
1426 tree
->band
= isl_schedule_band_drop(tree
->band
, pos
, n
- pos
);
1427 if (!child
->band
|| !tree
->band
)
1430 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
1434 isl_schedule_tree_free(child
);
1435 isl_schedule_tree_free(tree
);
1439 /* Attach "tree2" at each of the leaves of "tree1".
1441 * If "tree1" does not have any explicit children, then make "tree2"
1442 * its single child. Otherwise, attach "tree2" to the leaves of
1443 * each of the children of "tree1".
1445 __isl_give isl_schedule_tree
*isl_schedule_tree_append_to_leaves(
1446 __isl_take isl_schedule_tree
*tree1
,
1447 __isl_take isl_schedule_tree
*tree2
)
1451 if (!tree1
|| !tree2
)
1453 n
= isl_schedule_tree_n_children(tree1
);
1455 isl_schedule_tree_list
*list
;
1456 list
= isl_schedule_tree_list_from_schedule_tree(tree2
);
1457 tree1
= isl_schedule_tree_set_children(tree1
, list
);
1460 for (i
= 0; i
< n
; ++i
) {
1461 isl_schedule_tree
*child
;
1463 child
= isl_schedule_tree_get_child(tree1
, i
);
1464 child
= isl_schedule_tree_append_to_leaves(child
,
1465 isl_schedule_tree_copy(tree2
));
1466 tree1
= isl_schedule_tree_replace_child(tree1
, i
, child
);
1469 isl_schedule_tree_free(tree2
);
1472 isl_schedule_tree_free(tree1
);
1473 isl_schedule_tree_free(tree2
);
1477 /* Reset the user pointer on all identifiers of parameters and tuples
1478 * in the root of "tree".
1480 __isl_give isl_schedule_tree
*isl_schedule_tree_reset_user(
1481 __isl_take isl_schedule_tree
*tree
)
1483 if (isl_schedule_tree_is_leaf(tree
))
1486 tree
= isl_schedule_tree_cow(tree
);
1490 switch (tree
->type
) {
1491 case isl_schedule_node_error
:
1492 return isl_schedule_tree_free(tree
);
1493 case isl_schedule_node_band
:
1494 tree
->band
= isl_schedule_band_reset_user(tree
->band
);
1496 return isl_schedule_tree_free(tree
);
1498 case isl_schedule_node_domain
:
1499 tree
->domain
= isl_union_set_reset_user(tree
->domain
);
1501 return isl_schedule_tree_free(tree
);
1503 case isl_schedule_node_filter
:
1504 tree
->filter
= isl_union_set_reset_user(tree
->filter
);
1506 return isl_schedule_tree_free(tree
);
1508 case isl_schedule_node_leaf
:
1509 case isl_schedule_node_sequence
:
1510 case isl_schedule_node_set
:
1517 /* Align the parameters of the root of "tree" to those of "space".
1519 __isl_give isl_schedule_tree
*isl_schedule_tree_align_params(
1520 __isl_take isl_schedule_tree
*tree
, __isl_take isl_space
*space
)
1525 if (isl_schedule_tree_is_leaf(tree
)) {
1526 isl_space_free(space
);
1530 tree
= isl_schedule_tree_cow(tree
);
1534 switch (tree
->type
) {
1535 case isl_schedule_node_error
:
1537 case isl_schedule_node_band
:
1538 tree
->band
= isl_schedule_band_align_params(tree
->band
, space
);
1540 return isl_schedule_tree_free(tree
);
1542 case isl_schedule_node_domain
:
1543 tree
->domain
= isl_union_set_align_params(tree
->domain
, space
);
1545 return isl_schedule_tree_free(tree
);
1547 case isl_schedule_node_filter
:
1548 tree
->filter
= isl_union_set_align_params(tree
->filter
, space
);
1550 return isl_schedule_tree_free(tree
);
1552 case isl_schedule_node_leaf
:
1553 case isl_schedule_node_sequence
:
1554 case isl_schedule_node_set
:
1555 isl_space_free(space
);
1561 isl_space_free(space
);
1562 isl_schedule_tree_free(tree
);
1566 /* Does "tree" involve the iteration domain?
1567 * That is, does it need to be modified
1568 * by isl_schedule_tree_pullback_union_pw_multi_aff?
1570 static int involves_iteration_domain(__isl_keep isl_schedule_tree
*tree
)
1575 switch (tree
->type
) {
1576 case isl_schedule_node_error
:
1578 case isl_schedule_node_band
:
1579 case isl_schedule_node_domain
:
1580 case isl_schedule_node_filter
:
1582 case isl_schedule_node_leaf
:
1583 case isl_schedule_node_sequence
:
1584 case isl_schedule_node_set
:
1589 /* Compute the pullback of the root node of "tree" by the function
1590 * represented by "upma".
1591 * In other words, plug in "upma" in the iteration domains of
1592 * the root node of "tree".
1594 * We first check if the root node involves any iteration domains.
1595 * If so, we handle the specific cases.
1597 __isl_give isl_schedule_tree
*isl_schedule_tree_pullback_union_pw_multi_aff(
1598 __isl_take isl_schedule_tree
*tree
,
1599 __isl_take isl_union_pw_multi_aff
*upma
)
1606 involves
= involves_iteration_domain(tree
);
1610 isl_union_pw_multi_aff_free(upma
);
1614 tree
= isl_schedule_tree_cow(tree
);
1618 if (tree
->type
== isl_schedule_node_band
) {
1619 tree
->band
= isl_schedule_band_pullback_union_pw_multi_aff(
1622 return isl_schedule_tree_free(tree
);
1623 } else if (tree
->type
== isl_schedule_node_domain
) {
1625 isl_union_set_preimage_union_pw_multi_aff(tree
->domain
,
1628 return isl_schedule_tree_free(tree
);
1629 } else if (tree
->type
== isl_schedule_node_filter
) {
1631 isl_union_set_preimage_union_pw_multi_aff(tree
->filter
,
1634 return isl_schedule_tree_free(tree
);
1639 isl_union_pw_multi_aff_free(upma
);
1640 isl_schedule_tree_free(tree
);
1644 /* Compute the gist of the band tree root with respect to "context".
1646 __isl_give isl_schedule_tree
*isl_schedule_tree_band_gist(
1647 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*context
)
1651 if (tree
->type
!= isl_schedule_node_band
)
1652 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1653 "not a band node", goto error
);
1654 tree
= isl_schedule_tree_cow(tree
);
1658 tree
->band
= isl_schedule_band_gist(tree
->band
, context
);
1660 return isl_schedule_tree_free(tree
);
1663 isl_union_set_free(context
);
1664 isl_schedule_tree_free(tree
);
1668 /* Are any members in "band" marked coincident?
1670 static int any_coincident(__isl_keep isl_schedule_band
*band
)
1674 n
= isl_schedule_band_n_member(band
);
1675 for (i
= 0; i
< n
; ++i
)
1676 if (isl_schedule_band_member_get_coincident(band
, i
))
1682 /* Print the band node "band" to "p".
1684 * The permutable and coincident properties are only printed if they
1685 * are different from the defaults.
1686 * The coincident property is always printed in YAML flow style.
1688 static __isl_give isl_printer
*print_tree_band(__isl_take isl_printer
*p
,
1689 __isl_keep isl_schedule_band
*band
)
1691 isl_union_set
*options
;
1694 p
= isl_printer_print_str(p
, "schedule");
1695 p
= isl_printer_yaml_next(p
);
1696 p
= isl_printer_print_str(p
, "\"");
1697 p
= isl_printer_print_multi_union_pw_aff(p
, band
->mupa
);
1698 p
= isl_printer_print_str(p
, "\"");
1699 if (isl_schedule_band_get_permutable(band
)) {
1700 p
= isl_printer_yaml_next(p
);
1701 p
= isl_printer_print_str(p
, "permutable");
1702 p
= isl_printer_yaml_next(p
);
1703 p
= isl_printer_print_int(p
, 1);
1705 if (any_coincident(band
)) {
1709 p
= isl_printer_yaml_next(p
);
1710 p
= isl_printer_print_str(p
, "coincident");
1711 p
= isl_printer_yaml_next(p
);
1712 style
= isl_printer_get_yaml_style(p
);
1713 p
= isl_printer_set_yaml_style(p
, ISL_YAML_STYLE_FLOW
);
1714 p
= isl_printer_yaml_start_sequence(p
);
1715 n
= isl_schedule_band_n_member(band
);
1716 for (i
= 0; i
< n
; ++i
) {
1717 p
= isl_printer_print_int(p
,
1718 isl_schedule_band_member_get_coincident(band
, i
));
1719 p
= isl_printer_yaml_next(p
);
1721 p
= isl_printer_yaml_end_sequence(p
);
1722 p
= isl_printer_set_yaml_style(p
, style
);
1724 options
= isl_schedule_band_get_ast_build_options(band
);
1725 empty
= isl_union_set_is_empty(options
);
1727 p
= isl_printer_free(p
);
1729 p
= isl_printer_yaml_next(p
);
1730 p
= isl_printer_print_str(p
, "options");
1731 p
= isl_printer_yaml_next(p
);
1732 p
= isl_printer_print_str(p
, "\"");
1733 p
= isl_printer_print_union_set(p
, options
);
1734 p
= isl_printer_print_str(p
, "\"");
1736 isl_union_set_free(options
);
1741 /* Print "tree" to "p".
1743 * If "n_ancestor" is non-negative, then "child_pos" contains the child
1744 * positions of a descendant of the current node that should be marked
1745 * (by the comment "YOU ARE HERE"). In particular, if "n_ancestor"
1746 * is zero, then the current node should be marked.
1747 * The marking is only printed in YAML block format.
1749 * Implicit leaf nodes are not printed, except if they correspond
1750 * to the node that should be marked.
1752 __isl_give isl_printer
*isl_printer_print_schedule_tree_mark(
1753 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
,
1754 int n_ancestor
, int *child_pos
)
1760 block
= isl_printer_get_yaml_style(p
) == ISL_YAML_STYLE_BLOCK
;
1762 p
= isl_printer_yaml_start_mapping(p
);
1763 if (n_ancestor
== 0 && block
) {
1764 p
= isl_printer_print_str(p
, "# YOU ARE HERE");
1765 p
= isl_printer_end_line(p
);
1766 p
= isl_printer_start_line(p
);
1768 switch (tree
->type
) {
1769 case isl_schedule_node_error
:
1770 p
= isl_printer_print_str(p
, "ERROR");
1772 case isl_schedule_node_leaf
:
1773 p
= isl_printer_print_str(p
, "leaf");
1775 case isl_schedule_node_sequence
:
1776 p
= isl_printer_print_str(p
, "sequence");
1779 case isl_schedule_node_set
:
1780 p
= isl_printer_print_str(p
, "set");
1783 case isl_schedule_node_domain
:
1784 p
= isl_printer_print_str(p
, "domain");
1785 p
= isl_printer_yaml_next(p
);
1786 p
= isl_printer_print_str(p
, "\"");
1787 p
= isl_printer_print_union_set(p
, tree
->domain
);
1788 p
= isl_printer_print_str(p
, "\"");
1790 case isl_schedule_node_filter
:
1791 p
= isl_printer_print_str(p
, "filter");
1792 p
= isl_printer_yaml_next(p
);
1793 p
= isl_printer_print_str(p
, "\"");
1794 p
= isl_printer_print_union_set(p
, tree
->filter
);
1795 p
= isl_printer_print_str(p
, "\"");
1797 case isl_schedule_node_band
:
1798 p
= print_tree_band(p
, tree
->band
);
1801 p
= isl_printer_yaml_next(p
);
1803 if (!tree
->children
) {
1804 if (n_ancestor
> 0 && block
) {
1805 isl_schedule_tree
*leaf
;
1807 p
= isl_printer_print_str(p
, "child");
1808 p
= isl_printer_yaml_next(p
);
1809 leaf
= isl_schedule_tree_leaf(isl_printer_get_ctx(p
));
1810 p
= isl_printer_print_schedule_tree_mark(p
,
1812 isl_schedule_tree_free(leaf
);
1813 p
= isl_printer_yaml_next(p
);
1815 return isl_printer_yaml_end_mapping(p
);
1819 p
= isl_printer_yaml_start_sequence(p
);
1821 p
= isl_printer_print_str(p
, "child");
1822 p
= isl_printer_yaml_next(p
);
1825 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1826 for (i
= 0; i
< n
; ++i
) {
1827 isl_schedule_tree
*t
;
1829 t
= isl_schedule_tree_get_child(tree
, i
);
1830 if (n_ancestor
> 0 && child_pos
[0] == i
)
1831 p
= isl_printer_print_schedule_tree_mark(p
, t
,
1832 n_ancestor
- 1, child_pos
+ 1);
1834 p
= isl_printer_print_schedule_tree_mark(p
, t
,
1836 isl_schedule_tree_free(t
);
1838 p
= isl_printer_yaml_next(p
);
1842 p
= isl_printer_yaml_end_sequence(p
);
1843 p
= isl_printer_yaml_end_mapping(p
);
1848 /* Print "tree" to "p".
1850 __isl_give isl_printer
*isl_printer_print_schedule_tree(
1851 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
)
1853 return isl_printer_print_schedule_tree_mark(p
, tree
, -1, NULL
);
1856 void isl_schedule_tree_dump(__isl_keep isl_schedule_tree
*tree
)
1859 isl_printer
*printer
;
1864 ctx
= isl_schedule_tree_get_ctx(tree
);
1865 printer
= isl_printer_to_file(ctx
, stderr
);
1866 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
1867 printer
= isl_printer_print_schedule_tree(printer
, tree
);
1869 isl_printer_free(printer
);