2 * Copyright 2013 Ecole Normale Superieure
4 * Use of this software is governed by the MIT license
6 * Written by Sven Verdoolaege,
7 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
11 #include <isl_schedule_band.h>
12 #include <isl_schedule_private.h>
15 #define EL isl_schedule_tree
17 #include <isl_list_templ.h>
20 #define BASE schedule_tree
22 #include <isl_list_templ.c>
24 /* Is "tree" the leaf of a schedule tree?
26 int isl_schedule_tree_is_leaf(__isl_keep isl_schedule_tree
*tree
)
28 return isl_schedule_tree_get_type(tree
) == isl_schedule_node_leaf
;
31 /* Create a new schedule tree of type "type".
32 * The caller is responsible for filling in the type specific fields and
35 static __isl_give isl_schedule_tree
*isl_schedule_tree_alloc(isl_ctx
*ctx
,
36 enum isl_schedule_node_type type
)
38 isl_schedule_tree
*tree
;
40 if (type
== isl_schedule_node_error
)
43 tree
= isl_calloc_type(ctx
, isl_schedule_tree
);
55 /* Return a fresh copy of "tree".
57 __isl_take isl_schedule_tree
*isl_schedule_tree_dup(
58 __isl_keep isl_schedule_tree
*tree
)
61 isl_schedule_tree
*dup
;
66 ctx
= isl_schedule_tree_get_ctx(tree
);
67 dup
= isl_schedule_tree_alloc(ctx
, tree
->type
);
72 case isl_schedule_node_error
:
73 isl_die(ctx
, isl_error_internal
,
74 "allocation should have failed",
75 isl_schedule_tree_free(dup
));
76 case isl_schedule_node_band
:
77 dup
->band
= isl_schedule_band_copy(tree
->band
);
79 return isl_schedule_tree_free(dup
);
81 case isl_schedule_node_domain
:
82 dup
->domain
= isl_union_set_copy(tree
->domain
);
84 return isl_schedule_tree_free(dup
);
86 case isl_schedule_node_filter
:
87 dup
->filter
= isl_union_set_copy(tree
->filter
);
89 return isl_schedule_tree_free(dup
);
91 case isl_schedule_node_leaf
:
92 case isl_schedule_node_sequence
:
93 case isl_schedule_node_set
:
98 dup
->children
= isl_schedule_tree_list_copy(tree
->children
);
100 return isl_schedule_tree_free(dup
);
106 /* Return an isl_schedule_tree that is equal to "tree" and that has only
107 * a single reference.
109 * This function is called before a tree is modified.
110 * A static tree (with negative reference count) should never be modified,
111 * so it is not allowed to call this function on a static tree.
113 __isl_give isl_schedule_tree
*isl_schedule_tree_cow(
114 __isl_take isl_schedule_tree
*tree
)
120 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
121 "static trees cannot be modified",
122 return isl_schedule_tree_free(tree
));
127 return isl_schedule_tree_dup(tree
);
130 /* Return a new reference to "tree".
132 * A static tree (with negative reference count) does not keep track
133 * of the number of references and should not be modified.
135 __isl_give isl_schedule_tree
*isl_schedule_tree_copy(
136 __isl_keep isl_schedule_tree
*tree
)
148 /* Free "tree" and return NULL.
150 __isl_null isl_schedule_tree
*isl_schedule_tree_free(
151 __isl_take isl_schedule_tree
*tree
)
160 switch (tree
->type
) {
161 case isl_schedule_node_band
:
162 isl_schedule_band_free(tree
->band
);
164 case isl_schedule_node_domain
:
165 isl_union_set_free(tree
->domain
);
167 case isl_schedule_node_filter
:
168 isl_union_set_free(tree
->filter
);
170 case isl_schedule_node_sequence
:
171 case isl_schedule_node_set
:
172 case isl_schedule_node_error
:
173 case isl_schedule_node_leaf
:
176 isl_schedule_tree_list_free(tree
->children
);
177 isl_ctx_deref(tree
->ctx
);
183 /* Create and return a new leaf schedule tree.
185 __isl_give isl_schedule_tree
*isl_schedule_tree_leaf(isl_ctx
*ctx
)
187 return isl_schedule_tree_alloc(ctx
, isl_schedule_node_leaf
);
190 /* Create a new band schedule tree referring to "band"
193 __isl_give isl_schedule_tree
*isl_schedule_tree_from_band(
194 __isl_take isl_schedule_band
*band
)
197 isl_schedule_tree
*tree
;
202 ctx
= isl_schedule_band_get_ctx(band
);
203 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_band
);
211 isl_schedule_band_free(band
);
215 /* Create a new domain schedule tree with the given domain and no children.
217 __isl_give isl_schedule_tree
*isl_schedule_tree_from_domain(
218 __isl_take isl_union_set
*domain
)
221 isl_schedule_tree
*tree
;
226 ctx
= isl_union_set_get_ctx(domain
);
227 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_domain
);
231 tree
->domain
= domain
;
235 isl_union_set_free(domain
);
239 /* Create a new filter schedule tree with the given filter and no children.
241 __isl_give isl_schedule_tree
*isl_schedule_tree_from_filter(
242 __isl_take isl_union_set
*filter
)
245 isl_schedule_tree
*tree
;
250 ctx
= isl_union_set_get_ctx(filter
);
251 tree
= isl_schedule_tree_alloc(ctx
, isl_schedule_node_filter
);
255 tree
->filter
= filter
;
259 isl_union_set_free(filter
);
263 /* Create a new tree of the given type (isl_schedule_node_sequence or
264 * isl_schedule_node_set) with the given children.
266 __isl_give isl_schedule_tree
*isl_schedule_tree_from_children(
267 enum isl_schedule_node_type type
,
268 __isl_take isl_schedule_tree_list
*list
)
271 isl_schedule_tree
*tree
;
276 ctx
= isl_schedule_tree_list_get_ctx(list
);
277 tree
= isl_schedule_tree_alloc(ctx
, type
);
281 tree
->children
= list
;
285 isl_schedule_tree_list_free(list
);
289 /* Return the isl_ctx to which "tree" belongs.
291 isl_ctx
*isl_schedule_tree_get_ctx(__isl_keep isl_schedule_tree
*tree
)
293 return tree
? tree
->ctx
: NULL
;
296 /* Return the type of the root of the tree or isl_schedule_node_error
299 enum isl_schedule_node_type
isl_schedule_tree_get_type(
300 __isl_keep isl_schedule_tree
*tree
)
302 return tree
? tree
->type
: isl_schedule_node_error
;
305 /* Does "tree" have any children, other than an implicit leaf.
307 int isl_schedule_tree_has_children(__isl_keep isl_schedule_tree
*tree
)
312 return tree
->children
!= NULL
;
315 /* Return the number of children of "tree", excluding implicit leaves.
317 int isl_schedule_tree_n_children(__isl_keep isl_schedule_tree
*tree
)
322 return isl_schedule_tree_list_n_schedule_tree(tree
->children
);
325 /* Return a copy of the (explicit) child at position "pos" of "tree".
327 __isl_give isl_schedule_tree
*isl_schedule_tree_get_child(
328 __isl_keep isl_schedule_tree
*tree
, int pos
)
333 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
334 "schedule tree has no explicit children", return NULL
);
335 return isl_schedule_tree_list_get_schedule_tree(tree
->children
, pos
);
338 /* Return a copy of the (explicit) child at position "pos" of "tree" and
341 __isl_give isl_schedule_tree
*isl_schedule_tree_child(
342 __isl_take isl_schedule_tree
*tree
, int pos
)
344 isl_schedule_tree
*child
;
346 child
= isl_schedule_tree_get_child(tree
, pos
);
347 isl_schedule_tree_free(tree
);
351 /* Remove all (explicit) children from "tree".
353 __isl_give isl_schedule_tree
*isl_schedule_tree_reset_children(
354 __isl_take isl_schedule_tree
*tree
)
356 tree
= isl_schedule_tree_cow(tree
);
359 tree
->children
= isl_schedule_tree_list_free(tree
->children
);
363 /* Replace the child at position "pos" of "tree" by "child".
365 * If the new child is a leaf, then it is not explicitly
366 * recorded in the list of children. Instead, the list of children
367 * (which is assumed to have only one element) is removed.
368 * Note that the children of set and sequence nodes are always
369 * filters, so they cannot be replaced by empty trees.
371 __isl_give isl_schedule_tree
*isl_schedule_tree_replace_child(
372 __isl_take isl_schedule_tree
*tree
, int pos
,
373 __isl_take isl_schedule_tree
*child
)
375 tree
= isl_schedule_tree_cow(tree
);
379 if (isl_schedule_tree_is_leaf(child
)) {
380 isl_schedule_tree_free(child
);
381 if (!tree
->children
&& pos
== 0)
383 if (isl_schedule_tree_n_children(tree
) != 1)
384 isl_die(isl_schedule_tree_get_ctx(tree
),
386 "can only replace single child by leaf",
388 return isl_schedule_tree_reset_children(tree
);
391 if (!tree
->children
&& pos
== 0)
393 isl_schedule_tree_list_from_schedule_tree(child
);
395 tree
->children
= isl_schedule_tree_list_set_schedule_tree(
396 tree
->children
, pos
, child
);
399 return isl_schedule_tree_free(tree
);
403 isl_schedule_tree_free(tree
);
404 isl_schedule_tree_free(child
);
408 /* Create a new band schedule tree referring to "band"
409 * with "tree" as single child.
411 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_band(
412 __isl_take isl_schedule_tree
*tree
, __isl_take isl_schedule_band
*band
)
414 isl_schedule_tree
*res
;
416 res
= isl_schedule_tree_from_band(band
);
417 return isl_schedule_tree_replace_child(res
, 0, tree
);
420 /* Create a new domain schedule tree with the given domain and
421 * with "tree" as single child.
423 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_domain(
424 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
426 isl_schedule_tree
*res
;
428 res
= isl_schedule_tree_from_domain(domain
);
429 return isl_schedule_tree_replace_child(res
, 0, tree
);
432 /* Create a new filter schedule tree with the given filter and single child.
434 * If the root of "tree" is itself a filter node, then the two
435 * filter nodes are merged into one node.
437 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_filter(
438 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
440 isl_schedule_tree
*res
;
442 if (isl_schedule_tree_get_type(tree
) == isl_schedule_node_filter
) {
443 isl_union_set
*tree_filter
;
445 tree_filter
= isl_schedule_tree_filter_get_filter(tree
);
446 tree_filter
= isl_union_set_intersect(tree_filter
, filter
);
447 tree
= isl_schedule_tree_filter_set_filter(tree
, tree_filter
);
451 res
= isl_schedule_tree_from_filter(filter
);
452 return isl_schedule_tree_replace_child(res
, 0, tree
);
455 /* Return the number of members in the band tree root.
457 unsigned isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree
*tree
)
462 if (tree
->type
!= isl_schedule_node_band
)
463 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
464 "not a band node", return 0);
466 return isl_schedule_band_n_member(tree
->band
);
469 /* Is the band member at position "pos" of the band tree root
472 int isl_schedule_tree_band_member_get_coincident(
473 __isl_keep isl_schedule_tree
*tree
, int pos
)
478 if (tree
->type
!= isl_schedule_node_band
)
479 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
480 "not a band node", return -1);
482 return isl_schedule_band_member_get_coincident(tree
->band
, pos
);
485 /* Mark the given band member as being coincident or not
486 * according to "coincident".
488 __isl_give isl_schedule_tree
*isl_schedule_tree_band_member_set_coincident(
489 __isl_take isl_schedule_tree
*tree
, int pos
, int coincident
)
493 if (tree
->type
!= isl_schedule_node_band
)
494 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
495 "not a band node", return isl_schedule_tree_free(tree
));
496 if (isl_schedule_tree_band_member_get_coincident(tree
, pos
) ==
499 tree
= isl_schedule_tree_cow(tree
);
503 tree
->band
= isl_schedule_band_member_set_coincident(tree
->band
, pos
,
506 return isl_schedule_tree_free(tree
);
510 /* Is the band tree root marked permutable?
512 int isl_schedule_tree_band_get_permutable(__isl_keep isl_schedule_tree
*tree
)
517 if (tree
->type
!= isl_schedule_node_band
)
518 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
519 "not a band node", return -1);
521 return isl_schedule_band_get_permutable(tree
->band
);
524 /* Mark the band tree root permutable or not according to "permutable"?
526 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_permutable(
527 __isl_take isl_schedule_tree
*tree
, int permutable
)
531 if (tree
->type
!= isl_schedule_node_band
)
532 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
533 "not a band node", return isl_schedule_tree_free(tree
));
534 if (isl_schedule_tree_band_get_permutable(tree
) == permutable
)
536 tree
= isl_schedule_tree_cow(tree
);
540 tree
->band
= isl_schedule_band_set_permutable(tree
->band
, permutable
);
542 return isl_schedule_tree_free(tree
);
546 /* Return the schedule space of the band tree root.
548 __isl_give isl_space
*isl_schedule_tree_band_get_space(
549 __isl_keep isl_schedule_tree
*tree
)
554 if (tree
->type
!= isl_schedule_node_band
)
555 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
556 "not a band node", return NULL
);
558 return isl_schedule_band_get_space(tree
->band
);
561 /* Return the schedule of the band tree root in isolation.
563 __isl_give isl_multi_union_pw_aff
*isl_schedule_tree_band_get_partial_schedule(
564 __isl_keep isl_schedule_tree
*tree
)
569 if (tree
->type
!= isl_schedule_node_band
)
570 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
571 "not a band node", return NULL
);
573 return isl_schedule_band_get_partial_schedule(tree
->band
);
576 /* Return the domain of the domain tree root.
578 __isl_give isl_union_set
*isl_schedule_tree_domain_get_domain(
579 __isl_keep isl_schedule_tree
*tree
)
584 if (tree
->type
!= isl_schedule_node_domain
)
585 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
586 "not a domain node", return NULL
);
588 return isl_union_set_copy(tree
->domain
);
591 /* Replace the domain of domain tree root "tree" by "domain".
593 __isl_give isl_schedule_tree
*isl_schedule_tree_domain_set_domain(
594 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
596 tree
= isl_schedule_tree_cow(tree
);
597 if (!tree
|| !domain
)
600 if (tree
->type
!= isl_schedule_node_domain
)
601 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
602 "not a domain node", goto error
);
604 isl_union_set_free(tree
->domain
);
605 tree
->domain
= domain
;
609 isl_schedule_tree_free(tree
);
610 isl_union_set_free(domain
);
614 /* Return the filter of the filter tree root.
616 __isl_give isl_union_set
*isl_schedule_tree_filter_get_filter(
617 __isl_keep isl_schedule_tree
*tree
)
622 if (tree
->type
!= isl_schedule_node_filter
)
623 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
624 "not a filter node", return NULL
);
626 return isl_union_set_copy(tree
->filter
);
629 /* Replace the filter of the filter tree root by "filter".
631 __isl_give isl_schedule_tree
*isl_schedule_tree_filter_set_filter(
632 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
634 tree
= isl_schedule_tree_cow(tree
);
635 if (!tree
|| !filter
)
638 if (tree
->type
!= isl_schedule_node_filter
)
639 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
640 "not a filter node", return NULL
);
642 isl_union_set_free(tree
->filter
);
643 tree
->filter
= filter
;
647 isl_schedule_tree_free(tree
);
648 isl_union_set_free(filter
);
652 /* Set dim to the range dimension of "map" and abort the search.
654 static int set_range_dim(__isl_take isl_map
*map
, void *user
)
658 *dim
= isl_map_dim(map
, isl_dim_out
);
664 /* Return the dimension of the range of "umap".
665 * "umap" is assumed not to be empty and
666 * all maps inside "umap" are assumed to have the same range.
668 * We extract the range dimension from the first map in "umap".
670 static int range_dim(__isl_keep isl_union_map
*umap
)
676 if (isl_union_map_n_map(umap
) == 0)
677 isl_die(isl_union_map_get_ctx(umap
), isl_error_internal
,
678 "unexpected empty input", return -1);
680 isl_union_map_foreach_map(umap
, &set_range_dim
, &dim
);
685 /* Append an "extra" number of zeros to the range of "umap" and
688 static __isl_give isl_union_map
*append_range(__isl_take isl_union_map
*umap
,
694 isl_union_pw_multi_aff
*suffix
;
695 isl_union_map
*universe
;
696 isl_union_map
*suffix_umap
;
698 universe
= isl_union_map_universe(isl_union_map_copy(umap
));
699 dom
= isl_union_map_domain(universe
);
700 space
= isl_union_set_get_space(dom
);
701 space
= isl_space_set_from_params(space
);
702 space
= isl_space_add_dims(space
, isl_dim_set
, extra
);
703 mv
= isl_multi_val_zero(space
);
705 suffix
= isl_union_pw_multi_aff_multi_val_on_domain(dom
, mv
);
706 suffix_umap
= isl_union_map_from_union_pw_multi_aff(suffix
);
707 umap
= isl_union_map_flat_range_product(umap
, suffix_umap
);
712 /* Move down to the first descendant of "tree" that contains any schedule
713 * information or return "leaf" if there is no such descendant.
715 __isl_give isl_schedule_tree
*isl_schedule_tree_first_schedule_descendant(
716 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_tree
*leaf
)
718 while (isl_schedule_tree_get_type(tree
) == isl_schedule_node_band
&&
719 isl_schedule_tree_band_n_member(tree
) == 0) {
720 if (!isl_schedule_tree_has_children(tree
)) {
721 isl_schedule_tree_free(tree
);
722 return isl_schedule_tree_copy(leaf
);
724 tree
= isl_schedule_tree_child(tree
, 0);
730 static __isl_give isl_union_map
*subtree_schedule_extend(
731 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
);
733 /* Extend the schedule map "outer" with the subtree schedule
734 * of the (single) child of "tree", if any.
736 * If "tree" does not have any descendants (apart from those that
737 * do not carry any schedule information), then we simply return "outer".
738 * Otherwise, we extend the schedule map "outer" with the subtree schedule
739 * of the single child.
741 static __isl_give isl_union_map
*subtree_schedule_extend_child(
742 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
744 isl_schedule_tree
*child
;
748 return isl_union_map_free(outer
);
749 if (!isl_schedule_tree_has_children(tree
))
751 child
= isl_schedule_tree_get_child(tree
, 0);
753 return isl_union_map_free(outer
);
754 res
= subtree_schedule_extend(child
, outer
);
755 isl_schedule_tree_free(child
);
759 /* Extract the parameter space from one of the children of "tree",
760 * which are assumed to be filters.
762 static __isl_give isl_space
*extract_space_from_filter_child(
763 __isl_keep isl_schedule_tree
*tree
)
767 isl_schedule_tree
*child
;
769 child
= isl_schedule_tree_list_get_schedule_tree(tree
->children
, 0);
770 dom
= isl_schedule_tree_filter_get_filter(child
);
771 space
= isl_union_set_get_space(dom
);
772 isl_union_set_free(dom
);
773 isl_schedule_tree_free(child
);
778 /* Extend the schedule map "outer" with the subtree schedule
779 * of a set or sequence node.
781 * The schedule for the set or sequence node itself is composed of
790 * The first form is used if there is only a single child or
791 * if the current node is a set node and the schedule_separate_components
794 * Each of the pieces above is extended with the subtree schedule of
795 * the child of the corresponding filter, if any, padded with zeros
796 * to ensure that all pieces have the same range dimension.
798 static __isl_give isl_union_map
*subtree_schedule_extend_from_children(
799 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
813 ctx
= isl_schedule_tree_get_ctx(tree
);
815 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
816 "missing children", return NULL
);
817 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
819 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
820 "missing children", return NULL
);
822 separate
= n
> 1 && (tree
->type
== isl_schedule_node_sequence
||
823 isl_options_get_schedule_separate_components(ctx
));
825 space
= extract_space_from_filter_child(tree
);
827 umap
= isl_union_map_empty(isl_space_copy(space
));
828 space
= isl_space_set_from_params(space
);
830 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
831 v
= isl_val_zero(ctx
);
833 mv
= isl_multi_val_zero(space
);
835 dim
= isl_multi_val_dim(mv
, isl_dim_set
);
836 for (i
= 0; i
< n
; ++i
) {
837 isl_union_pw_multi_aff
*upma
;
838 isl_union_map
*umap_i
;
840 isl_schedule_tree
*child
;
844 child
= isl_schedule_tree_list_get_schedule_tree(
846 dom
= isl_schedule_tree_filter_get_filter(child
);
849 mv
= isl_multi_val_set_val(mv
, 0, isl_val_copy(v
));
850 v
= isl_val_add_ui(v
, 1);
852 upma
= isl_union_pw_multi_aff_multi_val_on_domain(dom
,
853 isl_multi_val_copy(mv
));
854 umap_i
= isl_union_map_from_union_pw_multi_aff(upma
);
855 umap_i
= isl_union_map_flat_range_product(
856 isl_union_map_copy(outer
), umap_i
);
857 umap_i
= subtree_schedule_extend_child(child
, umap_i
);
858 isl_schedule_tree_free(child
);
860 empty
= isl_union_map_is_empty(umap_i
);
862 umap_i
= isl_union_map_free(umap_i
);
864 isl_union_map_free(umap_i
);
868 dim_i
= range_dim(umap_i
);
870 umap
= isl_union_map_free(umap
);
871 } else if (dim
< dim_i
) {
872 umap
= append_range(umap
, dim_i
- dim
);
874 } else if (dim_i
< dim
) {
875 umap_i
= append_range(umap_i
, dim
- dim_i
);
877 umap
= isl_union_map_union(umap
, umap_i
);
881 isl_multi_val_free(mv
);
882 isl_union_map_free(outer
);
887 /* Extend the schedule map "outer" with the subtree schedule of "tree".
889 * If the root of the tree is a set or a sequence, then we extend
890 * the schedule map in subtree_schedule_extend_from_children.
891 * Otherwise, we extend the schedule map with the partial schedule
892 * corresponding to the root of the tree and then continue with
893 * the single child of this root.
895 static __isl_give isl_union_map
*subtree_schedule_extend(
896 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
898 isl_multi_union_pw_aff
*mupa
;
900 isl_union_set
*domain
;
905 switch (tree
->type
) {
906 case isl_schedule_node_error
:
907 return isl_union_map_free(outer
);
908 case isl_schedule_node_band
:
909 if (isl_schedule_tree_band_n_member(tree
) == 0)
910 return subtree_schedule_extend_child(tree
, outer
);
911 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
912 umap
= isl_union_map_from_multi_union_pw_aff(mupa
);
913 outer
= isl_union_map_flat_range_product(outer
, umap
);
914 umap
= subtree_schedule_extend_child(tree
, outer
);
916 case isl_schedule_node_domain
:
917 domain
= isl_schedule_tree_domain_get_domain(tree
);
918 umap
= isl_union_map_from_domain(domain
);
919 outer
= isl_union_map_flat_range_product(outer
, umap
);
920 umap
= subtree_schedule_extend_child(tree
, outer
);
922 case isl_schedule_node_filter
:
923 domain
= isl_schedule_tree_filter_get_filter(tree
);
924 umap
= isl_union_map_from_domain(domain
);
925 outer
= isl_union_map_flat_range_product(outer
, umap
);
926 umap
= subtree_schedule_extend_child(tree
, outer
);
928 case isl_schedule_node_leaf
:
929 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
930 "leaf node should be handled by caller", return NULL
);
931 case isl_schedule_node_set
:
932 case isl_schedule_node_sequence
:
933 umap
= subtree_schedule_extend_from_children(tree
, outer
);
940 static __isl_give isl_union_set
*initial_domain(
941 __isl_keep isl_schedule_tree
*tree
);
943 /* Extract a universe domain from the children of the tree root "tree",
944 * which is a set or sequence, meaning that its children are filters.
945 * In particular, return the union of the universes of the filters.
947 static __isl_give isl_union_set
*initial_domain_from_children(
948 __isl_keep isl_schedule_tree
*tree
)
952 isl_union_set
*domain
;
955 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
956 "missing children", return NULL
);
957 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
959 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
960 "missing children", return NULL
);
962 space
= extract_space_from_filter_child(tree
);
963 domain
= isl_union_set_empty(space
);
965 for (i
= 0; i
< n
; ++i
) {
966 isl_schedule_tree
*child
;
967 isl_union_set
*domain_i
;
969 child
= isl_schedule_tree_get_child(tree
, i
);
970 domain_i
= initial_domain(child
);
971 domain
= isl_union_set_union(domain
, domain_i
);
972 isl_schedule_tree_free(child
);
978 /* Extract a universe domain from the tree root "tree".
979 * The caller is responsible for making sure that this node
980 * would not be skipped by isl_schedule_tree_first_schedule_descendant
981 * and that it is not a leaf node.
983 static __isl_give isl_union_set
*initial_domain(
984 __isl_keep isl_schedule_tree
*tree
)
986 isl_multi_union_pw_aff
*mupa
;
987 isl_union_set
*domain
;
992 switch (tree
->type
) {
993 case isl_schedule_node_error
:
995 case isl_schedule_node_band
:
996 if (isl_schedule_tree_band_n_member(tree
) == 0)
997 isl_die(isl_schedule_tree_get_ctx(tree
),
999 "0D band should be handled by caller",
1001 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1002 domain
= isl_multi_union_pw_aff_domain(mupa
);
1003 domain
= isl_union_set_universe(domain
);
1005 case isl_schedule_node_domain
:
1006 domain
= isl_schedule_tree_domain_get_domain(tree
);
1007 domain
= isl_union_set_universe(domain
);
1009 case isl_schedule_node_filter
:
1010 domain
= isl_schedule_tree_filter_get_filter(tree
);
1011 domain
= isl_union_set_universe(domain
);
1013 case isl_schedule_node_leaf
:
1014 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1015 "leaf node should be handled by caller", return NULL
);
1016 case isl_schedule_node_set
:
1017 case isl_schedule_node_sequence
:
1018 domain
= initial_domain_from_children(tree
);
1025 /* Return the subtree schedule of a node that contains some schedule
1026 * information, i.e., a node that would not be skipped by
1027 * isl_schedule_tree_first_schedule_descendant and that is not a leaf.
1029 * We start with an initial zero-dimensional subtree schedule based
1030 * on the domain information in the root node and then extend it
1031 * based on the schedule information in the root node and its descendants.
1033 __isl_give isl_union_map
*isl_schedule_tree_get_subtree_schedule_union_map(
1034 __isl_keep isl_schedule_tree
*tree
)
1036 isl_union_set
*domain
;
1037 isl_union_map
*umap
;
1039 domain
= initial_domain(tree
);
1040 umap
= isl_union_map_from_domain(domain
);
1041 return subtree_schedule_extend(tree
, umap
);
1044 /* Multiply the partial schedule of the band root node of "tree"
1045 * with the factors in "mv".
1047 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale(
1048 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
1052 if (tree
->type
!= isl_schedule_node_band
)
1053 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1054 "not a band node", goto error
);
1056 tree
= isl_schedule_tree_cow(tree
);
1060 tree
->band
= isl_schedule_band_scale(tree
->band
, mv
);
1062 return isl_schedule_tree_free(tree
);
1066 isl_schedule_tree_free(tree
);
1067 isl_multi_val_free(mv
);
1071 /* Divide the partial schedule of the band root node of "tree"
1072 * by the factors in "mv".
1074 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale_down(
1075 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
1079 if (tree
->type
!= isl_schedule_node_band
)
1080 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1081 "not a band node", goto error
);
1083 tree
= isl_schedule_tree_cow(tree
);
1087 tree
->band
= isl_schedule_band_scale_down(tree
->band
, mv
);
1089 return isl_schedule_tree_free(tree
);
1093 isl_schedule_tree_free(tree
);
1094 isl_multi_val_free(mv
);
1098 /* Tile the band root node of "tree" with tile sizes "sizes".
1100 * We duplicate the band node, change the schedule of one of them
1101 * to the tile schedule and the other to the point schedule and then
1102 * attach the point band as a child to the tile band.
1104 __isl_give isl_schedule_tree
*isl_schedule_tree_band_tile(
1105 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*sizes
)
1107 isl_schedule_tree
*child
= NULL
;
1109 if (!tree
|| !sizes
)
1111 if (tree
->type
!= isl_schedule_node_band
)
1112 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1113 "not a band node", goto error
);
1115 child
= isl_schedule_tree_copy(tree
);
1116 tree
= isl_schedule_tree_cow(tree
);
1117 child
= isl_schedule_tree_cow(child
);
1118 if (!tree
|| !child
)
1121 tree
->band
= isl_schedule_band_tile(tree
->band
,
1122 isl_multi_val_copy(sizes
));
1125 child
->band
= isl_schedule_band_point(child
->band
, tree
->band
, sizes
);
1127 child
= isl_schedule_tree_free(child
);
1129 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
1133 isl_schedule_tree_free(child
);
1134 isl_schedule_tree_free(tree
);
1135 isl_multi_val_free(sizes
);
1139 /* Split the band root node of "tree" into two nested band nodes,
1140 * one with the first "pos" dimensions and
1141 * one with the remaining dimensions.
1143 __isl_give isl_schedule_tree
*isl_schedule_tree_band_split(
1144 __isl_take isl_schedule_tree
*tree
, int pos
)
1147 isl_schedule_tree
*child
;
1151 if (tree
->type
!= isl_schedule_node_band
)
1152 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1153 "not a band node", return isl_schedule_tree_free(tree
));
1155 n
= isl_schedule_tree_band_n_member(tree
);
1156 if (pos
< 0 || pos
> n
)
1157 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1158 "position out of bounds",
1159 return isl_schedule_tree_free(tree
));
1161 child
= isl_schedule_tree_copy(tree
);
1162 tree
= isl_schedule_tree_cow(tree
);
1163 child
= isl_schedule_tree_cow(child
);
1164 if (!tree
|| !child
)
1167 child
->band
= isl_schedule_band_drop(child
->band
, 0, pos
);
1168 tree
->band
= isl_schedule_band_drop(tree
->band
, pos
, n
- pos
);
1169 if (!child
->band
|| !tree
->band
)
1172 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
1176 isl_schedule_tree_free(child
);
1177 isl_schedule_tree_free(tree
);
1181 /* Are any members in "band" marked coincident?
1183 static int any_coincident(__isl_keep isl_schedule_band
*band
)
1187 n
= isl_schedule_band_n_member(band
);
1188 for (i
= 0; i
< n
; ++i
)
1189 if (isl_schedule_band_member_get_coincident(band
, i
))
1195 /* Print the band node "band" to "p".
1197 * The permutable and coincident properties are only printed if they
1198 * are different from the defaults.
1199 * The coincident property is always printed in YAML flow style.
1201 static __isl_give isl_printer
*print_tree_band(__isl_take isl_printer
*p
,
1202 __isl_keep isl_schedule_band
*band
)
1204 p
= isl_printer_print_str(p
, "schedule");
1205 p
= isl_printer_yaml_next(p
);
1206 p
= isl_printer_print_str(p
, "\"");
1207 p
= isl_printer_print_multi_union_pw_aff(p
, band
->mupa
);
1208 p
= isl_printer_print_str(p
, "\"");
1209 if (isl_schedule_band_get_permutable(band
)) {
1210 p
= isl_printer_yaml_next(p
);
1211 p
= isl_printer_print_str(p
, "permutable");
1212 p
= isl_printer_yaml_next(p
);
1213 p
= isl_printer_print_int(p
, 1);
1215 if (any_coincident(band
)) {
1219 p
= isl_printer_yaml_next(p
);
1220 p
= isl_printer_print_str(p
, "coincident");
1221 p
= isl_printer_yaml_next(p
);
1222 style
= isl_printer_get_yaml_style(p
);
1223 p
= isl_printer_set_yaml_style(p
, ISL_YAML_STYLE_FLOW
);
1224 p
= isl_printer_yaml_start_sequence(p
);
1225 n
= isl_schedule_band_n_member(band
);
1226 for (i
= 0; i
< n
; ++i
) {
1227 p
= isl_printer_print_int(p
,
1228 isl_schedule_band_member_get_coincident(band
, i
));
1229 p
= isl_printer_yaml_next(p
);
1231 p
= isl_printer_yaml_end_sequence(p
);
1232 p
= isl_printer_set_yaml_style(p
, style
);
1238 /* Print "tree" to "p".
1240 * If "n_ancestor" is non-negative, then "child_pos" contains the child
1241 * positions of a descendant of the current node that should be marked
1242 * (by the comment "YOU ARE HERE"). In particular, if "n_ancestor"
1243 * is zero, then the current node should be marked.
1244 * The marking is only printed in YAML block format.
1246 * Implicit leaf nodes are not printed, except if they correspond
1247 * to the node that should be marked.
1249 __isl_give isl_printer
*isl_printer_print_schedule_tree_mark(
1250 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
,
1251 int n_ancestor
, int *child_pos
)
1257 block
= isl_printer_get_yaml_style(p
) == ISL_YAML_STYLE_BLOCK
;
1259 p
= isl_printer_yaml_start_mapping(p
);
1260 if (n_ancestor
== 0 && block
) {
1261 p
= isl_printer_print_str(p
, "# YOU ARE HERE");
1262 p
= isl_printer_end_line(p
);
1263 p
= isl_printer_start_line(p
);
1265 switch (tree
->type
) {
1266 case isl_schedule_node_error
:
1267 p
= isl_printer_print_str(p
, "ERROR");
1269 case isl_schedule_node_leaf
:
1270 p
= isl_printer_print_str(p
, "leaf");
1272 case isl_schedule_node_sequence
:
1273 p
= isl_printer_print_str(p
, "sequence");
1276 case isl_schedule_node_set
:
1277 p
= isl_printer_print_str(p
, "set");
1280 case isl_schedule_node_domain
:
1281 p
= isl_printer_print_str(p
, "domain");
1282 p
= isl_printer_yaml_next(p
);
1283 p
= isl_printer_print_str(p
, "\"");
1284 p
= isl_printer_print_union_set(p
, tree
->domain
);
1285 p
= isl_printer_print_str(p
, "\"");
1287 case isl_schedule_node_filter
:
1288 p
= isl_printer_print_str(p
, "filter");
1289 p
= isl_printer_yaml_next(p
);
1290 p
= isl_printer_print_str(p
, "\"");
1291 p
= isl_printer_print_union_set(p
, tree
->filter
);
1292 p
= isl_printer_print_str(p
, "\"");
1294 case isl_schedule_node_band
:
1295 p
= print_tree_band(p
, tree
->band
);
1298 p
= isl_printer_yaml_next(p
);
1300 if (!tree
->children
) {
1301 if (n_ancestor
> 0 && block
) {
1302 isl_schedule_tree
*leaf
;
1304 p
= isl_printer_print_str(p
, "child");
1305 p
= isl_printer_yaml_next(p
);
1306 leaf
= isl_schedule_tree_leaf(isl_printer_get_ctx(p
));
1307 p
= isl_printer_print_schedule_tree_mark(p
,
1309 isl_schedule_tree_free(leaf
);
1310 p
= isl_printer_yaml_next(p
);
1312 return isl_printer_yaml_end_mapping(p
);
1316 p
= isl_printer_yaml_start_sequence(p
);
1318 p
= isl_printer_print_str(p
, "child");
1319 p
= isl_printer_yaml_next(p
);
1322 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1323 for (i
= 0; i
< n
; ++i
) {
1324 isl_schedule_tree
*t
;
1326 t
= isl_schedule_tree_get_child(tree
, i
);
1327 if (n_ancestor
> 0 && child_pos
[0] == i
)
1328 p
= isl_printer_print_schedule_tree_mark(p
, t
,
1329 n_ancestor
- 1, child_pos
+ 1);
1331 p
= isl_printer_print_schedule_tree_mark(p
, t
,
1333 isl_schedule_tree_free(t
);
1335 p
= isl_printer_yaml_next(p
);
1339 p
= isl_printer_yaml_end_sequence(p
);
1340 p
= isl_printer_yaml_end_mapping(p
);
1345 /* Print "tree" to "p".
1347 __isl_give isl_printer
*isl_printer_print_schedule_tree(
1348 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
)
1350 return isl_printer_print_schedule_tree_mark(p
, tree
, -1, NULL
);
1353 void isl_schedule_tree_dump(__isl_keep isl_schedule_tree
*tree
)
1356 isl_printer
*printer
;
1361 ctx
= isl_schedule_tree_get_ctx(tree
);
1362 printer
= isl_printer_to_file(ctx
, stderr
);
1363 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
1364 printer
= isl_printer_print_schedule_tree(printer
, tree
);
1366 isl_printer_free(printer
);