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 /* Replace the (explicit) children of "tree" by "children"?
410 __isl_give isl_schedule_tree
*isl_schedule_tree_set_children(
411 __isl_take isl_schedule_tree
*tree
,
412 __isl_take isl_schedule_tree_list
*children
)
414 tree
= isl_schedule_tree_cow(tree
);
415 if (!tree
|| !children
)
417 isl_schedule_tree_list_free(tree
->children
);
418 tree
->children
= children
;
421 isl_schedule_tree_free(tree
);
422 isl_schedule_tree_list_free(children
);
426 /* Create a new band schedule tree referring to "band"
427 * with "tree" as single child.
429 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_band(
430 __isl_take isl_schedule_tree
*tree
, __isl_take isl_schedule_band
*band
)
432 isl_schedule_tree
*res
;
434 res
= isl_schedule_tree_from_band(band
);
435 return isl_schedule_tree_replace_child(res
, 0, tree
);
438 /* Create a new domain schedule tree with the given domain and
439 * with "tree" as single child.
441 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_domain(
442 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
444 isl_schedule_tree
*res
;
446 res
= isl_schedule_tree_from_domain(domain
);
447 return isl_schedule_tree_replace_child(res
, 0, tree
);
450 /* Create a new filter schedule tree with the given filter and single child.
452 * If the root of "tree" is itself a filter node, then the two
453 * filter nodes are merged into one node.
455 __isl_give isl_schedule_tree
*isl_schedule_tree_insert_filter(
456 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
458 isl_schedule_tree
*res
;
460 if (isl_schedule_tree_get_type(tree
) == isl_schedule_node_filter
) {
461 isl_union_set
*tree_filter
;
463 tree_filter
= isl_schedule_tree_filter_get_filter(tree
);
464 tree_filter
= isl_union_set_intersect(tree_filter
, filter
);
465 tree
= isl_schedule_tree_filter_set_filter(tree
, tree_filter
);
469 res
= isl_schedule_tree_from_filter(filter
);
470 return isl_schedule_tree_replace_child(res
, 0, tree
);
473 /* Return the number of members in the band tree root.
475 unsigned isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree
*tree
)
480 if (tree
->type
!= isl_schedule_node_band
)
481 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
482 "not a band node", return 0);
484 return isl_schedule_band_n_member(tree
->band
);
487 /* Is the band member at position "pos" of the band tree root
490 int isl_schedule_tree_band_member_get_coincident(
491 __isl_keep isl_schedule_tree
*tree
, int pos
)
496 if (tree
->type
!= isl_schedule_node_band
)
497 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
498 "not a band node", return -1);
500 return isl_schedule_band_member_get_coincident(tree
->band
, pos
);
503 /* Mark the given band member as being coincident or not
504 * according to "coincident".
506 __isl_give isl_schedule_tree
*isl_schedule_tree_band_member_set_coincident(
507 __isl_take isl_schedule_tree
*tree
, int pos
, int coincident
)
511 if (tree
->type
!= isl_schedule_node_band
)
512 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
513 "not a band node", return isl_schedule_tree_free(tree
));
514 if (isl_schedule_tree_band_member_get_coincident(tree
, pos
) ==
517 tree
= isl_schedule_tree_cow(tree
);
521 tree
->band
= isl_schedule_band_member_set_coincident(tree
->band
, pos
,
524 return isl_schedule_tree_free(tree
);
528 /* Is the band tree root marked permutable?
530 int isl_schedule_tree_band_get_permutable(__isl_keep isl_schedule_tree
*tree
)
535 if (tree
->type
!= isl_schedule_node_band
)
536 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
537 "not a band node", return -1);
539 return isl_schedule_band_get_permutable(tree
->band
);
542 /* Mark the band tree root permutable or not according to "permutable"?
544 __isl_give isl_schedule_tree
*isl_schedule_tree_band_set_permutable(
545 __isl_take isl_schedule_tree
*tree
, int permutable
)
549 if (tree
->type
!= isl_schedule_node_band
)
550 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
551 "not a band node", return isl_schedule_tree_free(tree
));
552 if (isl_schedule_tree_band_get_permutable(tree
) == permutable
)
554 tree
= isl_schedule_tree_cow(tree
);
558 tree
->band
= isl_schedule_band_set_permutable(tree
->band
, permutable
);
560 return isl_schedule_tree_free(tree
);
564 /* Return the schedule space of the band tree root.
566 __isl_give isl_space
*isl_schedule_tree_band_get_space(
567 __isl_keep isl_schedule_tree
*tree
)
572 if (tree
->type
!= isl_schedule_node_band
)
573 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
574 "not a band node", return NULL
);
576 return isl_schedule_band_get_space(tree
->band
);
579 /* Return the schedule of the band tree root in isolation.
581 __isl_give isl_multi_union_pw_aff
*isl_schedule_tree_band_get_partial_schedule(
582 __isl_keep isl_schedule_tree
*tree
)
587 if (tree
->type
!= isl_schedule_node_band
)
588 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
589 "not a band node", return NULL
);
591 return isl_schedule_band_get_partial_schedule(tree
->band
);
594 /* Return the domain of the domain tree root.
596 __isl_give isl_union_set
*isl_schedule_tree_domain_get_domain(
597 __isl_keep isl_schedule_tree
*tree
)
602 if (tree
->type
!= isl_schedule_node_domain
)
603 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
604 "not a domain node", return NULL
);
606 return isl_union_set_copy(tree
->domain
);
609 /* Replace the domain of domain tree root "tree" by "domain".
611 __isl_give isl_schedule_tree
*isl_schedule_tree_domain_set_domain(
612 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*domain
)
614 tree
= isl_schedule_tree_cow(tree
);
615 if (!tree
|| !domain
)
618 if (tree
->type
!= isl_schedule_node_domain
)
619 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
620 "not a domain node", goto error
);
622 isl_union_set_free(tree
->domain
);
623 tree
->domain
= domain
;
627 isl_schedule_tree_free(tree
);
628 isl_union_set_free(domain
);
632 /* Return the filter of the filter tree root.
634 __isl_give isl_union_set
*isl_schedule_tree_filter_get_filter(
635 __isl_keep isl_schedule_tree
*tree
)
640 if (tree
->type
!= isl_schedule_node_filter
)
641 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
642 "not a filter node", return NULL
);
644 return isl_union_set_copy(tree
->filter
);
647 /* Replace the filter of the filter tree root by "filter".
649 __isl_give isl_schedule_tree
*isl_schedule_tree_filter_set_filter(
650 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
)
652 tree
= isl_schedule_tree_cow(tree
);
653 if (!tree
|| !filter
)
656 if (tree
->type
!= isl_schedule_node_filter
)
657 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
658 "not a filter node", return NULL
);
660 isl_union_set_free(tree
->filter
);
661 tree
->filter
= filter
;
665 isl_schedule_tree_free(tree
);
666 isl_union_set_free(filter
);
670 /* Set dim to the range dimension of "map" and abort the search.
672 static int set_range_dim(__isl_take isl_map
*map
, void *user
)
676 *dim
= isl_map_dim(map
, isl_dim_out
);
682 /* Return the dimension of the range of "umap".
683 * "umap" is assumed not to be empty and
684 * all maps inside "umap" are assumed to have the same range.
686 * We extract the range dimension from the first map in "umap".
688 static int range_dim(__isl_keep isl_union_map
*umap
)
694 if (isl_union_map_n_map(umap
) == 0)
695 isl_die(isl_union_map_get_ctx(umap
), isl_error_internal
,
696 "unexpected empty input", return -1);
698 isl_union_map_foreach_map(umap
, &set_range_dim
, &dim
);
703 /* Append an "extra" number of zeros to the range of "umap" and
706 static __isl_give isl_union_map
*append_range(__isl_take isl_union_map
*umap
,
712 isl_union_pw_multi_aff
*suffix
;
713 isl_union_map
*universe
;
714 isl_union_map
*suffix_umap
;
716 universe
= isl_union_map_universe(isl_union_map_copy(umap
));
717 dom
= isl_union_map_domain(universe
);
718 space
= isl_union_set_get_space(dom
);
719 space
= isl_space_set_from_params(space
);
720 space
= isl_space_add_dims(space
, isl_dim_set
, extra
);
721 mv
= isl_multi_val_zero(space
);
723 suffix
= isl_union_pw_multi_aff_multi_val_on_domain(dom
, mv
);
724 suffix_umap
= isl_union_map_from_union_pw_multi_aff(suffix
);
725 umap
= isl_union_map_flat_range_product(umap
, suffix_umap
);
730 /* Move down to the first descendant of "tree" that contains any schedule
731 * information or return "leaf" if there is no such descendant.
733 __isl_give isl_schedule_tree
*isl_schedule_tree_first_schedule_descendant(
734 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_tree
*leaf
)
736 while (isl_schedule_tree_get_type(tree
) == isl_schedule_node_band
&&
737 isl_schedule_tree_band_n_member(tree
) == 0) {
738 if (!isl_schedule_tree_has_children(tree
)) {
739 isl_schedule_tree_free(tree
);
740 return isl_schedule_tree_copy(leaf
);
742 tree
= isl_schedule_tree_child(tree
, 0);
748 static __isl_give isl_union_map
*subtree_schedule_extend(
749 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
);
751 /* Extend the schedule map "outer" with the subtree schedule
752 * of the (single) child of "tree", if any.
754 * If "tree" does not have any descendants (apart from those that
755 * do not carry any schedule information), then we simply return "outer".
756 * Otherwise, we extend the schedule map "outer" with the subtree schedule
757 * of the single child.
759 static __isl_give isl_union_map
*subtree_schedule_extend_child(
760 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
762 isl_schedule_tree
*child
;
766 return isl_union_map_free(outer
);
767 if (!isl_schedule_tree_has_children(tree
))
769 child
= isl_schedule_tree_get_child(tree
, 0);
771 return isl_union_map_free(outer
);
772 res
= subtree_schedule_extend(child
, outer
);
773 isl_schedule_tree_free(child
);
777 /* Extract the parameter space from one of the children of "tree",
778 * which are assumed to be filters.
780 static __isl_give isl_space
*extract_space_from_filter_child(
781 __isl_keep isl_schedule_tree
*tree
)
785 isl_schedule_tree
*child
;
787 child
= isl_schedule_tree_list_get_schedule_tree(tree
->children
, 0);
788 dom
= isl_schedule_tree_filter_get_filter(child
);
789 space
= isl_union_set_get_space(dom
);
790 isl_union_set_free(dom
);
791 isl_schedule_tree_free(child
);
796 /* Extend the schedule map "outer" with the subtree schedule
797 * of a set or sequence node.
799 * The schedule for the set or sequence node itself is composed of
808 * The first form is used if there is only a single child or
809 * if the current node is a set node and the schedule_separate_components
812 * Each of the pieces above is extended with the subtree schedule of
813 * the child of the corresponding filter, if any, padded with zeros
814 * to ensure that all pieces have the same range dimension.
816 static __isl_give isl_union_map
*subtree_schedule_extend_from_children(
817 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
831 ctx
= isl_schedule_tree_get_ctx(tree
);
833 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
834 "missing children", return NULL
);
835 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
837 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
838 "missing children", return NULL
);
840 separate
= n
> 1 && (tree
->type
== isl_schedule_node_sequence
||
841 isl_options_get_schedule_separate_components(ctx
));
843 space
= extract_space_from_filter_child(tree
);
845 umap
= isl_union_map_empty(isl_space_copy(space
));
846 space
= isl_space_set_from_params(space
);
848 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
849 v
= isl_val_zero(ctx
);
851 mv
= isl_multi_val_zero(space
);
853 dim
= isl_multi_val_dim(mv
, isl_dim_set
);
854 for (i
= 0; i
< n
; ++i
) {
855 isl_union_pw_multi_aff
*upma
;
856 isl_union_map
*umap_i
;
858 isl_schedule_tree
*child
;
862 child
= isl_schedule_tree_list_get_schedule_tree(
864 dom
= isl_schedule_tree_filter_get_filter(child
);
867 mv
= isl_multi_val_set_val(mv
, 0, isl_val_copy(v
));
868 v
= isl_val_add_ui(v
, 1);
870 upma
= isl_union_pw_multi_aff_multi_val_on_domain(dom
,
871 isl_multi_val_copy(mv
));
872 umap_i
= isl_union_map_from_union_pw_multi_aff(upma
);
873 umap_i
= isl_union_map_flat_range_product(
874 isl_union_map_copy(outer
), umap_i
);
875 umap_i
= subtree_schedule_extend_child(child
, umap_i
);
876 isl_schedule_tree_free(child
);
878 empty
= isl_union_map_is_empty(umap_i
);
880 umap_i
= isl_union_map_free(umap_i
);
882 isl_union_map_free(umap_i
);
886 dim_i
= range_dim(umap_i
);
888 umap
= isl_union_map_free(umap
);
889 } else if (dim
< dim_i
) {
890 umap
= append_range(umap
, dim_i
- dim
);
892 } else if (dim_i
< dim
) {
893 umap_i
= append_range(umap_i
, dim
- dim_i
);
895 umap
= isl_union_map_union(umap
, umap_i
);
899 isl_multi_val_free(mv
);
900 isl_union_map_free(outer
);
905 /* Extend the schedule map "outer" with the subtree schedule of "tree".
907 * If the root of the tree is a set or a sequence, then we extend
908 * the schedule map in subtree_schedule_extend_from_children.
909 * Otherwise, we extend the schedule map with the partial schedule
910 * corresponding to the root of the tree and then continue with
911 * the single child of this root.
913 static __isl_give isl_union_map
*subtree_schedule_extend(
914 __isl_keep isl_schedule_tree
*tree
, __isl_take isl_union_map
*outer
)
916 isl_multi_union_pw_aff
*mupa
;
918 isl_union_set
*domain
;
923 switch (tree
->type
) {
924 case isl_schedule_node_error
:
925 return isl_union_map_free(outer
);
926 case isl_schedule_node_band
:
927 if (isl_schedule_tree_band_n_member(tree
) == 0)
928 return subtree_schedule_extend_child(tree
, outer
);
929 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
930 umap
= isl_union_map_from_multi_union_pw_aff(mupa
);
931 outer
= isl_union_map_flat_range_product(outer
, umap
);
932 umap
= subtree_schedule_extend_child(tree
, outer
);
934 case isl_schedule_node_domain
:
935 domain
= isl_schedule_tree_domain_get_domain(tree
);
936 umap
= isl_union_map_from_domain(domain
);
937 outer
= isl_union_map_flat_range_product(outer
, umap
);
938 umap
= subtree_schedule_extend_child(tree
, outer
);
940 case isl_schedule_node_filter
:
941 domain
= isl_schedule_tree_filter_get_filter(tree
);
942 umap
= isl_union_map_from_domain(domain
);
943 outer
= isl_union_map_flat_range_product(outer
, umap
);
944 umap
= subtree_schedule_extend_child(tree
, outer
);
946 case isl_schedule_node_leaf
:
947 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
948 "leaf node should be handled by caller", return NULL
);
949 case isl_schedule_node_set
:
950 case isl_schedule_node_sequence
:
951 umap
= subtree_schedule_extend_from_children(tree
, outer
);
958 static __isl_give isl_union_set
*initial_domain(
959 __isl_keep isl_schedule_tree
*tree
);
961 /* Extract a universe domain from the children of the tree root "tree",
962 * which is a set or sequence, meaning that its children are filters.
963 * In particular, return the union of the universes of the filters.
965 static __isl_give isl_union_set
*initial_domain_from_children(
966 __isl_keep isl_schedule_tree
*tree
)
970 isl_union_set
*domain
;
973 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
974 "missing children", return NULL
);
975 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
977 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
978 "missing children", return NULL
);
980 space
= extract_space_from_filter_child(tree
);
981 domain
= isl_union_set_empty(space
);
983 for (i
= 0; i
< n
; ++i
) {
984 isl_schedule_tree
*child
;
985 isl_union_set
*domain_i
;
987 child
= isl_schedule_tree_get_child(tree
, i
);
988 domain_i
= initial_domain(child
);
989 domain
= isl_union_set_union(domain
, domain_i
);
990 isl_schedule_tree_free(child
);
996 /* Extract a universe domain from the tree root "tree".
997 * The caller is responsible for making sure that this node
998 * would not be skipped by isl_schedule_tree_first_schedule_descendant
999 * and that it is not a leaf node.
1001 static __isl_give isl_union_set
*initial_domain(
1002 __isl_keep isl_schedule_tree
*tree
)
1004 isl_multi_union_pw_aff
*mupa
;
1005 isl_union_set
*domain
;
1010 switch (tree
->type
) {
1011 case isl_schedule_node_error
:
1013 case isl_schedule_node_band
:
1014 if (isl_schedule_tree_band_n_member(tree
) == 0)
1015 isl_die(isl_schedule_tree_get_ctx(tree
),
1017 "0D band should be handled by caller",
1019 mupa
= isl_schedule_band_get_partial_schedule(tree
->band
);
1020 domain
= isl_multi_union_pw_aff_domain(mupa
);
1021 domain
= isl_union_set_universe(domain
);
1023 case isl_schedule_node_domain
:
1024 domain
= isl_schedule_tree_domain_get_domain(tree
);
1025 domain
= isl_union_set_universe(domain
);
1027 case isl_schedule_node_filter
:
1028 domain
= isl_schedule_tree_filter_get_filter(tree
);
1029 domain
= isl_union_set_universe(domain
);
1031 case isl_schedule_node_leaf
:
1032 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
1033 "leaf node should be handled by caller", return NULL
);
1034 case isl_schedule_node_set
:
1035 case isl_schedule_node_sequence
:
1036 domain
= initial_domain_from_children(tree
);
1043 /* Return the subtree schedule of a node that contains some schedule
1044 * information, i.e., a node that would not be skipped by
1045 * isl_schedule_tree_first_schedule_descendant and that is not a leaf.
1047 * We start with an initial zero-dimensional subtree schedule based
1048 * on the domain information in the root node and then extend it
1049 * based on the schedule information in the root node and its descendants.
1051 __isl_give isl_union_map
*isl_schedule_tree_get_subtree_schedule_union_map(
1052 __isl_keep isl_schedule_tree
*tree
)
1054 isl_union_set
*domain
;
1055 isl_union_map
*umap
;
1057 domain
= initial_domain(tree
);
1058 umap
= isl_union_map_from_domain(domain
);
1059 return subtree_schedule_extend(tree
, umap
);
1062 /* Multiply the partial schedule of the band root node of "tree"
1063 * with the factors in "mv".
1065 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale(
1066 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
1070 if (tree
->type
!= isl_schedule_node_band
)
1071 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1072 "not a band node", goto error
);
1074 tree
= isl_schedule_tree_cow(tree
);
1078 tree
->band
= isl_schedule_band_scale(tree
->band
, mv
);
1080 return isl_schedule_tree_free(tree
);
1084 isl_schedule_tree_free(tree
);
1085 isl_multi_val_free(mv
);
1089 /* Divide the partial schedule of the band root node of "tree"
1090 * by the factors in "mv".
1092 __isl_give isl_schedule_tree
*isl_schedule_tree_band_scale_down(
1093 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*mv
)
1097 if (tree
->type
!= isl_schedule_node_band
)
1098 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1099 "not a band node", goto error
);
1101 tree
= isl_schedule_tree_cow(tree
);
1105 tree
->band
= isl_schedule_band_scale_down(tree
->band
, mv
);
1107 return isl_schedule_tree_free(tree
);
1111 isl_schedule_tree_free(tree
);
1112 isl_multi_val_free(mv
);
1116 /* Tile the band root node of "tree" with tile sizes "sizes".
1118 * We duplicate the band node, change the schedule of one of them
1119 * to the tile schedule and the other to the point schedule and then
1120 * attach the point band as a child to the tile band.
1122 __isl_give isl_schedule_tree
*isl_schedule_tree_band_tile(
1123 __isl_take isl_schedule_tree
*tree
, __isl_take isl_multi_val
*sizes
)
1125 isl_schedule_tree
*child
= NULL
;
1127 if (!tree
|| !sizes
)
1129 if (tree
->type
!= isl_schedule_node_band
)
1130 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1131 "not a band node", goto error
);
1133 child
= isl_schedule_tree_copy(tree
);
1134 tree
= isl_schedule_tree_cow(tree
);
1135 child
= isl_schedule_tree_cow(child
);
1136 if (!tree
|| !child
)
1139 tree
->band
= isl_schedule_band_tile(tree
->band
,
1140 isl_multi_val_copy(sizes
));
1143 child
->band
= isl_schedule_band_point(child
->band
, tree
->band
, sizes
);
1145 child
= isl_schedule_tree_free(child
);
1147 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
1151 isl_schedule_tree_free(child
);
1152 isl_schedule_tree_free(tree
);
1153 isl_multi_val_free(sizes
);
1157 /* Split the band root node of "tree" into two nested band nodes,
1158 * one with the first "pos" dimensions and
1159 * one with the remaining dimensions.
1161 __isl_give isl_schedule_tree
*isl_schedule_tree_band_split(
1162 __isl_take isl_schedule_tree
*tree
, int pos
)
1165 isl_schedule_tree
*child
;
1169 if (tree
->type
!= isl_schedule_node_band
)
1170 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1171 "not a band node", return isl_schedule_tree_free(tree
));
1173 n
= isl_schedule_tree_band_n_member(tree
);
1174 if (pos
< 0 || pos
> n
)
1175 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
1176 "position out of bounds",
1177 return isl_schedule_tree_free(tree
));
1179 child
= isl_schedule_tree_copy(tree
);
1180 tree
= isl_schedule_tree_cow(tree
);
1181 child
= isl_schedule_tree_cow(child
);
1182 if (!tree
|| !child
)
1185 child
->band
= isl_schedule_band_drop(child
->band
, 0, pos
);
1186 tree
->band
= isl_schedule_band_drop(tree
->band
, pos
, n
- pos
);
1187 if (!child
->band
|| !tree
->band
)
1190 tree
= isl_schedule_tree_replace_child(tree
, 0, child
);
1194 isl_schedule_tree_free(child
);
1195 isl_schedule_tree_free(tree
);
1199 /* Attach "tree2" at each of the leaves of "tree1".
1201 * If "tree1" does not have any explicit children, then make "tree2"
1202 * its single child. Otherwise, attach "tree2" to the leaves of
1203 * each of the children of "tree1".
1205 __isl_give isl_schedule_tree
*isl_schedule_tree_append_to_leaves(
1206 __isl_take isl_schedule_tree
*tree1
,
1207 __isl_take isl_schedule_tree
*tree2
)
1211 if (!tree1
|| !tree2
)
1213 n
= isl_schedule_tree_n_children(tree1
);
1215 isl_schedule_tree_list
*list
;
1216 list
= isl_schedule_tree_list_from_schedule_tree(tree2
);
1217 tree1
= isl_schedule_tree_set_children(tree1
, list
);
1220 for (i
= 0; i
< n
; ++i
) {
1221 isl_schedule_tree
*child
;
1223 child
= isl_schedule_tree_get_child(tree1
, i
);
1224 child
= isl_schedule_tree_append_to_leaves(child
,
1225 isl_schedule_tree_copy(tree2
));
1226 tree1
= isl_schedule_tree_replace_child(tree1
, i
, child
);
1229 isl_schedule_tree_free(tree2
);
1232 isl_schedule_tree_free(tree1
);
1233 isl_schedule_tree_free(tree2
);
1237 /* Are any members in "band" marked coincident?
1239 static int any_coincident(__isl_keep isl_schedule_band
*band
)
1243 n
= isl_schedule_band_n_member(band
);
1244 for (i
= 0; i
< n
; ++i
)
1245 if (isl_schedule_band_member_get_coincident(band
, i
))
1251 /* Print the band node "band" to "p".
1253 * The permutable and coincident properties are only printed if they
1254 * are different from the defaults.
1255 * The coincident property is always printed in YAML flow style.
1257 static __isl_give isl_printer
*print_tree_band(__isl_take isl_printer
*p
,
1258 __isl_keep isl_schedule_band
*band
)
1260 p
= isl_printer_print_str(p
, "schedule");
1261 p
= isl_printer_yaml_next(p
);
1262 p
= isl_printer_print_str(p
, "\"");
1263 p
= isl_printer_print_multi_union_pw_aff(p
, band
->mupa
);
1264 p
= isl_printer_print_str(p
, "\"");
1265 if (isl_schedule_band_get_permutable(band
)) {
1266 p
= isl_printer_yaml_next(p
);
1267 p
= isl_printer_print_str(p
, "permutable");
1268 p
= isl_printer_yaml_next(p
);
1269 p
= isl_printer_print_int(p
, 1);
1271 if (any_coincident(band
)) {
1275 p
= isl_printer_yaml_next(p
);
1276 p
= isl_printer_print_str(p
, "coincident");
1277 p
= isl_printer_yaml_next(p
);
1278 style
= isl_printer_get_yaml_style(p
);
1279 p
= isl_printer_set_yaml_style(p
, ISL_YAML_STYLE_FLOW
);
1280 p
= isl_printer_yaml_start_sequence(p
);
1281 n
= isl_schedule_band_n_member(band
);
1282 for (i
= 0; i
< n
; ++i
) {
1283 p
= isl_printer_print_int(p
,
1284 isl_schedule_band_member_get_coincident(band
, i
));
1285 p
= isl_printer_yaml_next(p
);
1287 p
= isl_printer_yaml_end_sequence(p
);
1288 p
= isl_printer_set_yaml_style(p
, style
);
1294 /* Print "tree" to "p".
1296 * If "n_ancestor" is non-negative, then "child_pos" contains the child
1297 * positions of a descendant of the current node that should be marked
1298 * (by the comment "YOU ARE HERE"). In particular, if "n_ancestor"
1299 * is zero, then the current node should be marked.
1300 * The marking is only printed in YAML block format.
1302 * Implicit leaf nodes are not printed, except if they correspond
1303 * to the node that should be marked.
1305 __isl_give isl_printer
*isl_printer_print_schedule_tree_mark(
1306 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
,
1307 int n_ancestor
, int *child_pos
)
1313 block
= isl_printer_get_yaml_style(p
) == ISL_YAML_STYLE_BLOCK
;
1315 p
= isl_printer_yaml_start_mapping(p
);
1316 if (n_ancestor
== 0 && block
) {
1317 p
= isl_printer_print_str(p
, "# YOU ARE HERE");
1318 p
= isl_printer_end_line(p
);
1319 p
= isl_printer_start_line(p
);
1321 switch (tree
->type
) {
1322 case isl_schedule_node_error
:
1323 p
= isl_printer_print_str(p
, "ERROR");
1325 case isl_schedule_node_leaf
:
1326 p
= isl_printer_print_str(p
, "leaf");
1328 case isl_schedule_node_sequence
:
1329 p
= isl_printer_print_str(p
, "sequence");
1332 case isl_schedule_node_set
:
1333 p
= isl_printer_print_str(p
, "set");
1336 case isl_schedule_node_domain
:
1337 p
= isl_printer_print_str(p
, "domain");
1338 p
= isl_printer_yaml_next(p
);
1339 p
= isl_printer_print_str(p
, "\"");
1340 p
= isl_printer_print_union_set(p
, tree
->domain
);
1341 p
= isl_printer_print_str(p
, "\"");
1343 case isl_schedule_node_filter
:
1344 p
= isl_printer_print_str(p
, "filter");
1345 p
= isl_printer_yaml_next(p
);
1346 p
= isl_printer_print_str(p
, "\"");
1347 p
= isl_printer_print_union_set(p
, tree
->filter
);
1348 p
= isl_printer_print_str(p
, "\"");
1350 case isl_schedule_node_band
:
1351 p
= print_tree_band(p
, tree
->band
);
1354 p
= isl_printer_yaml_next(p
);
1356 if (!tree
->children
) {
1357 if (n_ancestor
> 0 && block
) {
1358 isl_schedule_tree
*leaf
;
1360 p
= isl_printer_print_str(p
, "child");
1361 p
= isl_printer_yaml_next(p
);
1362 leaf
= isl_schedule_tree_leaf(isl_printer_get_ctx(p
));
1363 p
= isl_printer_print_schedule_tree_mark(p
,
1365 isl_schedule_tree_free(leaf
);
1366 p
= isl_printer_yaml_next(p
);
1368 return isl_printer_yaml_end_mapping(p
);
1372 p
= isl_printer_yaml_start_sequence(p
);
1374 p
= isl_printer_print_str(p
, "child");
1375 p
= isl_printer_yaml_next(p
);
1378 n
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1379 for (i
= 0; i
< n
; ++i
) {
1380 isl_schedule_tree
*t
;
1382 t
= isl_schedule_tree_get_child(tree
, i
);
1383 if (n_ancestor
> 0 && child_pos
[0] == i
)
1384 p
= isl_printer_print_schedule_tree_mark(p
, t
,
1385 n_ancestor
- 1, child_pos
+ 1);
1387 p
= isl_printer_print_schedule_tree_mark(p
, t
,
1389 isl_schedule_tree_free(t
);
1391 p
= isl_printer_yaml_next(p
);
1395 p
= isl_printer_yaml_end_sequence(p
);
1396 p
= isl_printer_yaml_end_mapping(p
);
1401 /* Print "tree" to "p".
1403 __isl_give isl_printer
*isl_printer_print_schedule_tree(
1404 __isl_take isl_printer
*p
, __isl_keep isl_schedule_tree
*tree
)
1406 return isl_printer_print_schedule_tree_mark(p
, tree
, -1, NULL
);
1409 void isl_schedule_tree_dump(__isl_keep isl_schedule_tree
*tree
)
1412 isl_printer
*printer
;
1417 ctx
= isl_schedule_tree_get_ctx(tree
);
1418 printer
= isl_printer_to_file(ctx
, stderr
);
1419 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
1420 printer
= isl_printer_print_schedule_tree(printer
, tree
);
1422 isl_printer_free(printer
);