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>
13 #include <isl_schedule_node_private.h>
15 /* Create a new schedule node in the given schedule, point at the given
16 * tree with given ancestors and child positions.
17 * "child_pos" may be NULL if there are no ancestors.
19 __isl_give isl_schedule_node
*isl_schedule_node_alloc(
20 __isl_take isl_schedule
*schedule
, __isl_take isl_schedule_tree
*tree
,
21 __isl_take isl_schedule_tree_list
*ancestors
, int *child_pos
)
24 isl_schedule_node
*node
;
27 if (!schedule
|| !tree
|| !ancestors
)
29 n
= isl_schedule_tree_list_n_schedule_tree(ancestors
);
30 if (n
> 0 && !child_pos
)
32 ctx
= isl_schedule_get_ctx(schedule
);
33 node
= isl_calloc_type(ctx
, isl_schedule_node
);
37 node
->schedule
= schedule
;
39 node
->ancestors
= ancestors
;
40 node
->child_pos
= isl_alloc_array(ctx
, int, n
);
41 if (n
&& !node
->child_pos
)
42 return isl_schedule_node_free(node
);
43 for (i
= 0; i
< n
; ++i
)
44 node
->child_pos
[i
] = child_pos
[i
];
48 isl_schedule_free(schedule
);
49 isl_schedule_tree_free(tree
);
50 isl_schedule_tree_list_free(ancestors
);
54 /* Return a pointer to the root of a schedule tree with as single
55 * node a domain node with the given domain.
57 __isl_give isl_schedule_node
*isl_schedule_node_from_domain(
58 __isl_take isl_union_set
*domain
)
60 isl_schedule
*schedule
;
61 isl_schedule_node
*node
;
63 schedule
= isl_schedule_from_domain(domain
);
64 node
= isl_schedule_get_root(schedule
);
65 isl_schedule_free(schedule
);
70 /* Return the isl_ctx to which "node" belongs.
72 isl_ctx
*isl_schedule_node_get_ctx(__isl_keep isl_schedule_node
*node
)
74 return node
? isl_schedule_get_ctx(node
->schedule
) : NULL
;
77 /* Return a pointer to the leaf of the schedule into which "node" points.
79 * Even though these leaves are not reference counted, we still
80 * indicate that this function does not return a copy.
82 __isl_keep isl_schedule_tree
*isl_schedule_node_peek_leaf(
83 __isl_keep isl_schedule_node
*node
)
85 return node
? isl_schedule_peek_leaf(node
->schedule
) : NULL
;
88 /* Return a pointer to the leaf of the schedule into which "node" points.
90 * Even though these leaves are not reference counted, we still
91 * return a "copy" of the leaf here such that it can still be "freed"
94 __isl_give isl_schedule_tree
*isl_schedule_node_get_leaf(
95 __isl_keep isl_schedule_node
*node
)
97 return isl_schedule_tree_copy(isl_schedule_node_peek_leaf(node
));
100 /* Return the type of the node or isl_schedule_node_error on error.
102 enum isl_schedule_node_type
isl_schedule_node_get_type(
103 __isl_keep isl_schedule_node
*node
)
105 return node
? isl_schedule_tree_get_type(node
->tree
)
106 : isl_schedule_node_error
;
109 /* Return the type of the parent of "node" or isl_schedule_node_error on error.
111 enum isl_schedule_node_type
isl_schedule_node_get_parent_type(
112 __isl_keep isl_schedule_node
*node
)
116 isl_schedule_tree
*parent
;
117 enum isl_schedule_node_type type
;
120 return isl_schedule_node_error
;
121 has_parent
= isl_schedule_node_has_parent(node
);
123 return isl_schedule_node_error
;
125 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
126 "node has no parent", return isl_schedule_node_error
);
128 pos
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) - 1;
129 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, pos
);
130 type
= isl_schedule_tree_get_type(parent
);
131 isl_schedule_tree_free(parent
);
136 /* Return a copy of the subtree that this node points to.
138 __isl_give isl_schedule_tree
*isl_schedule_node_get_tree(
139 __isl_keep isl_schedule_node
*node
)
144 return isl_schedule_tree_copy(node
->tree
);
147 /* Return a copy of the schedule into which "node" points.
149 __isl_give isl_schedule
*isl_schedule_node_get_schedule(
150 __isl_keep isl_schedule_node
*node
)
154 return isl_schedule_copy(node
->schedule
);
157 /* Return a fresh copy of "node".
159 __isl_take isl_schedule_node
*isl_schedule_node_dup(
160 __isl_keep isl_schedule_node
*node
)
165 return isl_schedule_node_alloc(isl_schedule_copy(node
->schedule
),
166 isl_schedule_tree_copy(node
->tree
),
167 isl_schedule_tree_list_copy(node
->ancestors
),
171 /* Return an isl_schedule_node that is equal to "node" and that has only
172 * a single reference.
174 __isl_give isl_schedule_node
*isl_schedule_node_cow(
175 __isl_take isl_schedule_node
*node
)
183 return isl_schedule_node_dup(node
);
186 /* Return a new reference to "node".
188 __isl_give isl_schedule_node
*isl_schedule_node_copy(
189 __isl_keep isl_schedule_node
*node
)
198 /* Free "node" and return NULL.
200 * Since the node may point to a leaf of its schedule, which
201 * point to a field inside the schedule, we need to make sure
202 * we free the tree before freeing the schedule.
204 __isl_null isl_schedule_node
*isl_schedule_node_free(
205 __isl_take isl_schedule_node
*node
)
212 isl_schedule_tree_list_free(node
->ancestors
);
213 free(node
->child_pos
);
214 isl_schedule_tree_free(node
->tree
);
215 isl_schedule_free(node
->schedule
);
221 /* Internal data structure for
222 * isl_schedule_node_get_prefix_schedule_union_pw_multi_aff
224 * "initialized" is set if the filter field has been initialized.
225 * "universe_filter" is set if we are only collecting the universes of filters
226 * "collect_prefix" is set if we are collecting prefixes.
227 * "filter" collects all outer filters and is NULL until "initialized" is set.
228 * "prefix" collects all outer band partial schedules (if "collect_prefix"
229 * is set). If it is used, then it is initialized by the caller
230 * of collect_filter_prefix to a zero-dimensional function.
232 struct isl_schedule_node_get_filter_prefix_data
{
236 isl_union_set
*filter
;
237 isl_multi_union_pw_aff
*prefix
;
240 /* Update "data" based on the tree node "tree" in case "data" has
241 * not been initialized yet.
243 * Return 0 on success and -1 on error.
245 * If "tree" is a filter, then we set data->filter to this filter
247 * If "tree" is a domain, then this means we have reached the root
248 * of the schedule tree without being able to extract any information.
249 * We therefore initialize data->filter to the universe of the domain.
250 * If "tree" is a band with at least one member, then we set data->filter
251 * to the universe of the schedule domain and replace the zero-dimensional
252 * data->prefix by the band schedule (if data->collect_prefix is set).
254 static int collect_filter_prefix_init(__isl_keep isl_schedule_tree
*tree
,
255 struct isl_schedule_node_get_filter_prefix_data
*data
)
257 enum isl_schedule_node_type type
;
258 isl_multi_union_pw_aff
*mupa
;
259 isl_union_set
*filter
;
261 type
= isl_schedule_tree_get_type(tree
);
263 case isl_schedule_node_error
:
265 case isl_schedule_node_leaf
:
266 case isl_schedule_node_sequence
:
267 case isl_schedule_node_set
:
269 case isl_schedule_node_domain
:
270 filter
= isl_schedule_tree_domain_get_domain(tree
);
271 filter
= isl_union_set_universe(filter
);
272 data
->filter
= filter
;
274 case isl_schedule_node_band
:
275 if (isl_schedule_tree_band_n_member(tree
) == 0)
277 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
278 if (data
->collect_prefix
) {
279 isl_multi_union_pw_aff_free(data
->prefix
);
280 mupa
= isl_multi_union_pw_aff_reset_tuple_id(mupa
,
282 data
->prefix
= isl_multi_union_pw_aff_copy(mupa
);
284 filter
= isl_multi_union_pw_aff_domain(mupa
);
285 filter
= isl_union_set_universe(filter
);
286 data
->filter
= filter
;
288 case isl_schedule_node_filter
:
289 filter
= isl_schedule_tree_filter_get_filter(tree
);
290 if (data
->universe_filter
)
291 filter
= isl_union_set_universe(filter
);
292 data
->filter
= filter
;
296 if ((data
->collect_prefix
&& !data
->prefix
) || !data
->filter
)
299 data
->initialized
= 1;
304 /* Update "data" based on the tree node "tree" in case "data" has
305 * already been initialized.
307 * Return 0 on success and -1 on error.
309 * If "tree" is a filter, then we intersect data->filter with this filter
311 * If "tree" is a band with at least one member and data->collect_prefix
312 * is set, then we extend data->prefix with the band schedule.
314 static int collect_filter_prefix_update(__isl_keep isl_schedule_tree
*tree
,
315 struct isl_schedule_node_get_filter_prefix_data
*data
)
317 enum isl_schedule_node_type type
;
318 isl_multi_union_pw_aff
*mupa
;
319 isl_union_set
*filter
;
321 type
= isl_schedule_tree_get_type(tree
);
323 case isl_schedule_node_error
:
325 case isl_schedule_node_domain
:
326 case isl_schedule_node_leaf
:
327 case isl_schedule_node_sequence
:
328 case isl_schedule_node_set
:
330 case isl_schedule_node_band
:
331 if (isl_schedule_tree_band_n_member(tree
) == 0)
333 if (!data
->collect_prefix
)
335 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
336 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(mupa
,
341 case isl_schedule_node_filter
:
342 filter
= isl_schedule_tree_filter_get_filter(tree
);
343 if (data
->universe_filter
)
344 filter
= isl_union_set_universe(filter
);
345 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
354 /* Collect filter and/or prefix information from the elements
355 * in "list" (which represent the ancestors of a node).
356 * Store the results in "data".
358 * Return 0 on success and -1 on error.
360 * We traverse the list from innermost ancestor (last element)
361 * to outermost ancestor (first element), calling collect_filter_prefix_init
362 * on each node as long as we have not been able to extract any information
363 * yet and collect_filter_prefix_update afterwards.
364 * On successful return, data->initialized will be set since the outermost
365 * ancestor is a domain node, which always results in an initialization.
367 static int collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
368 struct isl_schedule_node_get_filter_prefix_data
*data
)
372 data
->initialized
= 0;
378 n
= isl_schedule_tree_list_n_schedule_tree(list
);
379 for (i
= n
- 1; i
>= 0; --i
) {
380 isl_schedule_tree
*tree
;
383 tree
= isl_schedule_tree_list_get_schedule_tree(list
, i
);
386 if (!data
->initialized
)
387 r
= collect_filter_prefix_init(tree
, data
);
389 r
= collect_filter_prefix_update(tree
, data
);
390 isl_schedule_tree_free(tree
);
398 /* Return the concatenation of the partial schedules of all outer band
399 * nodes of "node" interesected with all outer filters
400 * as an isl_union_pw_multi_aff.
402 * If "node" is pointing at the root of the schedule tree, then
403 * there are no domain elements reaching the current node, so
404 * we return an empty result.
406 * We collect all the filters and partial schedules in collect_filter_prefix.
407 * The partial schedules are collected as an isl_multi_union_pw_aff.
408 * If this isl_multi_union_pw_aff is zero-dimensional, then it does not
409 * contain any domain information, so we construct the isl_union_pw_multi_aff
410 * result as a zero-dimensional function on the collected filter.
411 * Otherwise, we convert the isl_multi_union_pw_aff to
412 * an isl_multi_union_pw_aff and intersect the domain with the filter.
414 __isl_give isl_union_pw_multi_aff
*
415 isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(
416 __isl_keep isl_schedule_node
*node
)
419 isl_union_pw_multi_aff
*prefix
;
420 struct isl_schedule_node_get_filter_prefix_data data
;
425 space
= isl_schedule_get_space(node
->schedule
);
426 if (node
->tree
== node
->schedule
->root
)
427 return isl_union_pw_multi_aff_empty(space
);
429 space
= isl_space_set_from_params(space
);
430 data
.universe_filter
= 0;
431 data
.collect_prefix
= 1;
432 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
434 if (collect_filter_prefix(node
->ancestors
, &data
) < 0)
435 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
438 isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
) == 0) {
439 isl_multi_union_pw_aff_free(data
.prefix
);
440 prefix
= isl_union_pw_multi_aff_from_domain(data
.filter
);
443 isl_union_pw_multi_aff_from_multi_union_pw_aff(data
.prefix
);
444 prefix
= isl_union_pw_multi_aff_intersect_domain(prefix
,
451 /* Return the concatenation of the partial schedules of all outer band
452 * nodes of "node" interesected with all outer filters
453 * as an isl_union_map.
455 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_union_map(
456 __isl_keep isl_schedule_node
*node
)
458 isl_union_pw_multi_aff
*upma
;
460 upma
= isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(node
);
461 return isl_union_map_from_union_pw_multi_aff(upma
);
464 /* Return the union of universe sets of the domain elements that reach "node".
466 * If "node" is pointing at the root of the schedule tree, then
467 * there are no domain elements reaching the current node, so
468 * we return an empty result.
470 * Otherwise, we collect the universes of all filters reaching the node
471 * in collect_filter_prefix.
473 __isl_give isl_union_set
*isl_schedule_node_get_universe_domain(
474 __isl_keep isl_schedule_node
*node
)
476 struct isl_schedule_node_get_filter_prefix_data data
;
481 if (node
->tree
== node
->schedule
->root
) {
484 space
= isl_schedule_get_space(node
->schedule
);
485 return isl_union_set_empty(space
);
488 data
.universe_filter
= 1;
489 data
.collect_prefix
= 0;
492 if (collect_filter_prefix(node
->ancestors
, &data
) < 0)
493 data
.filter
= isl_union_set_free(data
.filter
);
498 /* Return the subtree schedule of "node".
500 * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle
501 * trees that do not contain any schedule information, we first
502 * move down to the first relevant descendant and handle leaves ourselves.
504 __isl_give isl_union_map
*isl_schedule_node_get_subtree_schedule_union_map(
505 __isl_keep isl_schedule_node
*node
)
507 isl_schedule_tree
*tree
, *leaf
;
510 tree
= isl_schedule_node_get_tree(node
);
511 leaf
= isl_schedule_node_peek_leaf(node
);
512 tree
= isl_schedule_tree_first_schedule_descendant(tree
, leaf
);
516 isl_union_set
*domain
;
517 domain
= isl_schedule_node_get_universe_domain(node
);
518 isl_schedule_tree_free(tree
);
519 return isl_union_map_from_domain(domain
);
522 umap
= isl_schedule_tree_get_subtree_schedule_union_map(tree
);
523 isl_schedule_tree_free(tree
);
527 /* Return the number of ancestors of "node" in its schedule tree.
529 int isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node
*node
)
533 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
536 /* Does "node" have a parent?
538 * That is, does it point to any node of the schedule other than the root?
540 int isl_schedule_node_has_parent(__isl_keep isl_schedule_node
*node
)
544 if (!node
->ancestors
)
547 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) != 0;
550 /* Return the position of "node" among the children of its parent.
552 int isl_schedule_node_get_child_position(__isl_keep isl_schedule_node
*node
)
559 has_parent
= isl_schedule_node_has_parent(node
);
563 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
564 "node has no parent", return -1);
566 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
567 return node
->child_pos
[n
- 1];
570 /* Does the parent (if any) of "node" have any children with a smaller child
571 * position than this one?
573 int isl_schedule_node_has_previous_sibling(__isl_keep isl_schedule_node
*node
)
580 has_parent
= isl_schedule_node_has_parent(node
);
581 if (has_parent
< 0 || !has_parent
)
584 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
586 return node
->child_pos
[n
- 1] > 0;
589 /* Does the parent (if any) of "node" have any children with a greater child
590 * position than this one?
592 int isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node
*node
)
596 isl_schedule_tree
*tree
;
600 has_parent
= isl_schedule_node_has_parent(node
);
601 if (has_parent
< 0 || !has_parent
)
604 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
605 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
608 n_child
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
609 isl_schedule_tree_free(tree
);
611 return node
->child_pos
[n
- 1] + 1 < n_child
;
614 /* Does "node" have any children?
616 * Any node other than the leaf nodes is considered to have at least
617 * one child, even if the corresponding isl_schedule_tree does not
620 int isl_schedule_node_has_children(__isl_keep isl_schedule_node
*node
)
624 return !isl_schedule_tree_is_leaf(node
->tree
);
627 /* Return the number of children of "node"?
629 * Any node other than the leaf nodes is considered to have at least
630 * one child, even if the corresponding isl_schedule_tree does not
631 * have any children. That is, the number of children of "node" is
632 * only zero if its tree is the explicit empty tree. Otherwise,
633 * if the isl_schedule_tree has any children, then it is equal
634 * to the number of children of "node". If it has zero children,
635 * then "node" still has a leaf node as child.
637 int isl_schedule_node_n_children(__isl_keep isl_schedule_node
*node
)
644 if (isl_schedule_tree_is_leaf(node
->tree
))
647 n
= isl_schedule_tree_n_children(node
->tree
);
654 /* Move the "node" pointer to the parent of the node it currently points to.
656 __isl_give isl_schedule_node
*isl_schedule_node_parent(
657 __isl_take isl_schedule_node
*node
)
660 isl_schedule_tree
*tree
;
662 node
= isl_schedule_node_cow(node
);
665 if (!isl_schedule_node_has_parent(node
))
666 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
667 "node has no parent",
668 return isl_schedule_node_free(node
));
669 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
670 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
671 isl_schedule_tree_free(node
->tree
);
673 node
->ancestors
= isl_schedule_tree_list_drop(node
->ancestors
,
675 if (!node
->ancestors
|| !node
->tree
)
676 return isl_schedule_node_free(node
);
681 /* Move the "node" pointer to the child at position "pos" of the node
682 * it currently points to.
684 __isl_give isl_schedule_node
*isl_schedule_node_child(
685 __isl_take isl_schedule_node
*node
, int pos
)
689 isl_schedule_tree
*tree
;
692 node
= isl_schedule_node_cow(node
);
695 if (!isl_schedule_node_has_children(node
))
696 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
697 "node has no children",
698 return isl_schedule_node_free(node
));
700 ctx
= isl_schedule_node_get_ctx(node
);
701 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
702 child_pos
= isl_realloc_array(ctx
, node
->child_pos
, int, n
+ 1);
704 return isl_schedule_node_free(node
);
705 node
->child_pos
= child_pos
;
706 node
->child_pos
[n
] = pos
;
708 node
->ancestors
= isl_schedule_tree_list_add(node
->ancestors
,
709 isl_schedule_tree_copy(node
->tree
));
711 if (isl_schedule_tree_has_children(tree
))
712 tree
= isl_schedule_tree_get_child(tree
, pos
);
714 tree
= isl_schedule_node_get_leaf(node
);
715 isl_schedule_tree_free(node
->tree
);
718 if (!node
->tree
|| !node
->ancestors
)
719 return isl_schedule_node_free(node
);
724 /* Move the "node" pointer to the first child of the node
725 * it currently points to.
727 __isl_give isl_schedule_node
*isl_schedule_node_first_child(
728 __isl_take isl_schedule_node
*node
)
730 return isl_schedule_node_child(node
, 0);
733 /* Move the "node" pointer to the child of this node's parent in
734 * the previous child position.
736 __isl_give isl_schedule_node
*isl_schedule_node_previous_sibling(
737 __isl_take isl_schedule_node
*node
)
740 isl_schedule_tree
*parent
, *tree
;
742 node
= isl_schedule_node_cow(node
);
745 if (!isl_schedule_node_has_previous_sibling(node
))
746 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
747 "node has no previous sibling",
748 return isl_schedule_node_free(node
));
750 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
751 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
754 return isl_schedule_node_free(node
);
755 node
->child_pos
[n
- 1]--;
756 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
757 node
->child_pos
[n
- 1]);
758 isl_schedule_tree_free(parent
);
760 return isl_schedule_node_free(node
);
761 isl_schedule_tree_free(node
->tree
);
767 /* Move the "node" pointer to the child of this node's parent in
768 * the next child position.
770 __isl_give isl_schedule_node
*isl_schedule_node_next_sibling(
771 __isl_take isl_schedule_node
*node
)
774 isl_schedule_tree
*parent
, *tree
;
776 node
= isl_schedule_node_cow(node
);
779 if (!isl_schedule_node_has_next_sibling(node
))
780 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
781 "node has no next sibling",
782 return isl_schedule_node_free(node
));
784 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
785 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
788 return isl_schedule_node_free(node
);
789 node
->child_pos
[n
- 1]++;
790 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
791 node
->child_pos
[n
- 1]);
792 isl_schedule_tree_free(parent
);
794 return isl_schedule_node_free(node
);
795 isl_schedule_tree_free(node
->tree
);
801 /* Return a copy to the child at position "pos" of "node".
803 __isl_give isl_schedule_node
*isl_schedule_node_get_child(
804 __isl_keep isl_schedule_node
*node
, int pos
)
806 return isl_schedule_node_child(isl_schedule_node_copy(node
), pos
);
809 /* Traverse the descendant of "node" in depth-first order, including
810 * "node" itself. Call "enter" whenever a node is entered and "leave"
811 * whenever a node is left. The callback "enter" is responsible
812 * for moving to the deepest initial subtree of its argument that
813 * should be traversed.
815 static __isl_give isl_schedule_node
*traverse(
816 __isl_take isl_schedule_node
*node
,
817 __isl_give isl_schedule_node
*(*enter
)(
818 __isl_take isl_schedule_node
*node
, void *user
),
819 __isl_give isl_schedule_node
*(*leave
)(
820 __isl_take isl_schedule_node
*node
, void *user
),
828 depth
= isl_schedule_node_get_tree_depth(node
);
830 node
= enter(node
, user
);
831 node
= leave(node
, user
);
832 while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
&&
833 !isl_schedule_node_has_next_sibling(node
)) {
834 node
= isl_schedule_node_parent(node
);
835 node
= leave(node
, user
);
837 if (node
&& isl_schedule_node_get_tree_depth(node
) > depth
)
838 node
= isl_schedule_node_next_sibling(node
);
839 } while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
);
844 /* Internal data structure for isl_schedule_node_foreach_descendant.
846 * "fn" is the user-specified callback function.
847 * "user" is the user-specified argument for the callback.
849 struct isl_schedule_node_preorder_data
{
850 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
);
854 /* Callback for "traverse" to enter a node and to move
855 * to the deepest initial subtree that should be traversed
856 * for use in a preorder visit.
858 * If the user callback returns a negative value, then we abort
859 * the traversal. If this callback returns zero, then we skip
860 * the subtree rooted at the current node. Otherwise, we move
861 * down to the first child and repeat the process until a leaf
864 static __isl_give isl_schedule_node
*preorder_enter(
865 __isl_take isl_schedule_node
*node
, void *user
)
867 struct isl_schedule_node_preorder_data
*data
= user
;
875 r
= data
->fn(node
, data
->user
);
877 return isl_schedule_node_free(node
);
880 } while (isl_schedule_node_has_children(node
) &&
881 (node
= isl_schedule_node_first_child(node
)) != NULL
);
886 /* Callback for "traverse" to leave a node
887 * for use in a preorder visit.
888 * Since we already visited the node when we entered it,
889 * we do not need to do anything here.
891 static __isl_give isl_schedule_node
*preorder_leave(
892 __isl_take isl_schedule_node
*node
, void *user
)
897 /* Traverse the descendants of "node" (including the node itself)
898 * in depth first preorder.
900 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
901 * If "fn" returns 0 on any of the nodes, then the subtree rooted
902 * at that node is skipped.
904 * Return 0 on success and -1 on failure.
906 int isl_schedule_node_foreach_descendant(__isl_keep isl_schedule_node
*node
,
907 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
), void *user
)
909 struct isl_schedule_node_preorder_data data
= { fn
, user
};
911 node
= isl_schedule_node_copy(node
);
912 node
= traverse(node
, &preorder_enter
, &preorder_leave
, &data
);
913 isl_schedule_node_free(node
);
915 return node
? 0 : -1;
918 /* Internal data structure for isl_schedule_node_map_descendant.
920 * "fn" is the user-specified callback function.
921 * "user" is the user-specified argument for the callback.
923 struct isl_schedule_node_postorder_data
{
924 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
929 /* Callback for "traverse" to enter a node and to move
930 * to the deepest initial subtree that should be traversed
931 * for use in a postorder visit.
933 * Since we are performing a postorder visit, we only need
934 * to move to the deepest initial leaf here.
936 static __isl_give isl_schedule_node
*postorder_enter(
937 __isl_take isl_schedule_node
*node
, void *user
)
939 while (node
&& isl_schedule_node_has_children(node
))
940 node
= isl_schedule_node_first_child(node
);
945 /* Callback for "traverse" to leave a node
946 * for use in a postorder visit.
948 * Since we are performing a postorder visit, we need
949 * to call the user callback here.
951 static __isl_give isl_schedule_node
*postorder_leave(
952 __isl_take isl_schedule_node
*node
, void *user
)
954 struct isl_schedule_node_postorder_data
*data
= user
;
956 return data
->fn(node
, data
->user
);
959 /* Traverse the descendants of "node" (including the node itself)
960 * in depth first postorder, allowing the user to modify the visited node.
961 * The traversal continues from the node returned by the callback function.
962 * It is the responsibility of the user to ensure that this does not
963 * lead to an infinite loop. It is safest to always return a pointer
964 * to the same position (same ancestors and child positions) as the input node.
966 __isl_give isl_schedule_node
*isl_schedule_node_map_descendant(
967 __isl_take isl_schedule_node
*node
,
968 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
969 void *user
), void *user
)
971 struct isl_schedule_node_postorder_data data
= { fn
, user
};
973 return traverse(node
, &postorder_enter
, &postorder_leave
, &data
);
976 /* Return the number of members in the given band node.
978 unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node
*node
)
980 return node
? isl_schedule_tree_band_n_member(node
->tree
) : 0;
983 /* Is the band member at position "pos" of the band node "node"
986 int isl_schedule_node_band_member_get_coincident(
987 __isl_keep isl_schedule_node
*node
, int pos
)
991 return isl_schedule_tree_band_member_get_coincident(node
->tree
, pos
);
994 /* Mark the band member at position "pos" the band node "node"
995 * as being coincident or not according to "coincident".
997 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_coincident(
998 __isl_take isl_schedule_node
*node
, int pos
, int coincident
)
1001 isl_schedule_tree
*tree
;
1005 c
= isl_schedule_node_band_member_get_coincident(node
, pos
);
1006 if (c
== coincident
)
1009 tree
= isl_schedule_tree_copy(node
->tree
);
1010 tree
= isl_schedule_tree_band_member_set_coincident(tree
, pos
,
1012 node
= isl_schedule_node_graft_tree(node
, tree
);
1017 /* Is the band node "node" marked permutable?
1019 int isl_schedule_node_band_get_permutable(__isl_keep isl_schedule_node
*node
)
1024 return isl_schedule_tree_band_get_permutable(node
->tree
);
1027 /* Mark the band node "node" permutable or not according to "permutable"?
1029 __isl_give isl_schedule_node
*isl_schedule_node_band_set_permutable(
1030 __isl_take isl_schedule_node
*node
, int permutable
)
1032 isl_schedule_tree
*tree
;
1036 if (isl_schedule_node_band_get_permutable(node
) == permutable
)
1039 tree
= isl_schedule_tree_copy(node
->tree
);
1040 tree
= isl_schedule_tree_band_set_permutable(tree
, permutable
);
1041 node
= isl_schedule_node_graft_tree(node
, tree
);
1046 /* Return the schedule space of the band node.
1048 __isl_give isl_space
*isl_schedule_node_band_get_space(
1049 __isl_keep isl_schedule_node
*node
)
1054 return isl_schedule_tree_band_get_space(node
->tree
);
1057 /* Return the schedule of the band node in isolation.
1059 __isl_give isl_multi_union_pw_aff
*isl_schedule_node_band_get_partial_schedule(
1060 __isl_keep isl_schedule_node
*node
)
1065 return isl_schedule_tree_band_get_partial_schedule(node
->tree
);
1068 /* Return the schedule of the band node in isolation in the form of
1071 * If the band does not have any members, then we construct a universe map
1072 * with the universe of the domain elements reaching the node as domain.
1073 * Otherwise, we extract an isl_multi_union_pw_aff representation and
1074 * convert that to an isl_union_map.
1076 __isl_give isl_union_map
*isl_schedule_node_band_get_partial_schedule_union_map(
1077 __isl_keep isl_schedule_node
*node
)
1079 isl_multi_union_pw_aff
*mupa
;
1084 if (isl_schedule_node_get_type(node
) != isl_schedule_node_band
)
1085 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1086 "not a band node", return NULL
);
1087 if (isl_schedule_node_band_n_member(node
) == 0) {
1088 isl_union_set
*domain
;
1090 domain
= isl_schedule_node_get_universe_domain(node
);
1091 return isl_union_map_from_domain(domain
);
1094 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
1095 return isl_union_map_from_multi_union_pw_aff(mupa
);
1098 /* Make sure that that spaces of "node" and "mv" are the same.
1099 * Return -1 on error, reporting the error to the user.
1101 static int check_space_multi_val(__isl_keep isl_schedule_node
*node
,
1102 __isl_keep isl_multi_val
*mv
)
1104 isl_space
*node_space
, *mv_space
;
1107 node_space
= isl_schedule_node_band_get_space(node
);
1108 mv_space
= isl_multi_val_get_space(mv
);
1109 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1110 mv_space
, isl_dim_set
);
1111 isl_space_free(mv_space
);
1112 isl_space_free(node_space
);
1116 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1117 "spaces don't match", return -1);
1122 /* Multiply the partial schedule of the band node "node"
1123 * with the factors in "mv".
1125 __isl_give isl_schedule_node
*isl_schedule_node_band_scale(
1126 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1128 isl_schedule_tree
*tree
;
1132 if (check_space_multi_val(node
, mv
) < 0)
1135 tree
= isl_schedule_node_get_tree(node
);
1136 tree
= isl_schedule_tree_band_scale(tree
, mv
);
1137 return isl_schedule_node_graft_tree(node
, tree
);
1139 isl_multi_val_free(mv
);
1140 isl_schedule_node_free(node
);
1144 /* Divide the partial schedule of the band node "node"
1145 * by the factors in "mv".
1147 __isl_give isl_schedule_node
*isl_schedule_node_band_scale_down(
1148 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1150 isl_schedule_tree
*tree
;
1154 if (check_space_multi_val(node
, mv
) < 0)
1157 tree
= isl_schedule_node_get_tree(node
);
1158 tree
= isl_schedule_tree_band_scale_down(tree
, mv
);
1159 return isl_schedule_node_graft_tree(node
, tree
);
1161 isl_multi_val_free(mv
);
1162 isl_schedule_node_free(node
);
1166 /* Tile "node" with tile sizes "sizes".
1168 * The current node is replaced by two nested nodes corresponding
1169 * to the tile dimensions and the point dimensions.
1171 * Return a pointer to the outer (tile) node.
1173 * If the scale tile loops option is set, then the tile loops
1174 * are scaled by the tile sizes. If the shift point loops option is set,
1175 * then the point loops are shifted to start at zero.
1176 * In particular, these options affect the tile and point loop schedules
1179 * scale shift original tile point
1181 * 0 0 i floor(i/s) i
1182 * 1 0 i s * floor(i/s) i
1183 * 0 1 i floor(i/s) i - s * floor(i/s)
1184 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1186 __isl_give isl_schedule_node
*isl_schedule_node_band_tile(
1187 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*sizes
)
1189 isl_schedule_tree
*tree
;
1191 if (!node
|| !sizes
)
1194 if (check_space_multi_val(node
, sizes
) < 0)
1197 tree
= isl_schedule_node_get_tree(node
);
1198 tree
= isl_schedule_tree_band_tile(tree
, sizes
);
1199 return isl_schedule_node_graft_tree(node
, tree
);
1201 isl_multi_val_free(sizes
);
1202 isl_schedule_node_free(node
);
1206 /* Move the band node "node" down to all the leaves in the subtree
1208 * Return a pointer to the node in the resulting tree that is in the same
1209 * position as the node pointed to by "node" in the original tree.
1211 * If the node only has a leaf child, then nothing needs to be done.
1212 * Otherwise, the child of the node is removed and the result is
1213 * appended to all the leaves in the subtree rooted at the original child.
1214 * The original node is then replaced by the result of this operation.
1216 __isl_give isl_schedule_node
*isl_schedule_node_band_sink(
1217 __isl_take isl_schedule_node
*node
)
1219 enum isl_schedule_node_type type
;
1220 isl_schedule_tree
*tree
, *child
;
1225 type
= isl_schedule_node_get_type(node
);
1226 if (type
!= isl_schedule_node_band
)
1227 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1228 "not a band node", isl_schedule_node_free(node
));
1229 if (isl_schedule_tree_n_children(node
->tree
) == 0)
1232 tree
= isl_schedule_node_get_tree(node
);
1233 child
= isl_schedule_tree_get_child(tree
, 0);
1234 tree
= isl_schedule_tree_reset_children(tree
);
1235 tree
= isl_schedule_tree_append_to_leaves(child
, tree
);
1237 return isl_schedule_node_graft_tree(node
, tree
);
1240 /* Split "node" into two nested band nodes, one with the first "pos"
1241 * dimensions and one with the remaining dimensions.
1242 * The schedules of the two band nodes live in anonymous spaces.
1244 __isl_give isl_schedule_node
*isl_schedule_node_band_split(
1245 __isl_take isl_schedule_node
*node
, int pos
)
1247 isl_schedule_tree
*tree
;
1249 tree
= isl_schedule_node_get_tree(node
);
1250 tree
= isl_schedule_tree_band_split(tree
, pos
);
1251 return isl_schedule_node_graft_tree(node
, tree
);
1254 /* Return the domain of the domain node "node".
1256 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
1257 __isl_keep isl_schedule_node
*node
)
1262 return isl_schedule_tree_domain_get_domain(node
->tree
);
1265 /* Return the filter of the filter node "node".
1267 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
1268 __isl_keep isl_schedule_node
*node
)
1273 return isl_schedule_tree_filter_get_filter(node
->tree
);
1276 /* Replace the filter of filter node "node" by "filter".
1278 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
1279 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
1281 isl_schedule_tree
*tree
;
1283 if (!node
|| !filter
)
1286 tree
= isl_schedule_tree_copy(node
->tree
);
1287 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
1288 return isl_schedule_node_graft_tree(node
, tree
);
1290 isl_schedule_node_free(node
);
1291 isl_union_set_free(filter
);
1295 /* Update the ancestors of "node" to point to the tree that "node"
1297 * That is, replace the child in the original parent that corresponds
1298 * to the current tree position by node->tree and continue updating
1299 * the ancestors in the same way until the root is reached.
1301 * If "node" originally points to a leaf of the schedule tree, then make sure
1302 * that in the end it points to a leaf in the updated schedule tree.
1304 static __isl_give isl_schedule_node
*update_ancestors(
1305 __isl_take isl_schedule_node
*node
)
1310 isl_schedule_tree
*tree
;
1312 node
= isl_schedule_node_cow(node
);
1316 ctx
= isl_schedule_node_get_ctx(node
);
1317 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1318 tree
= isl_schedule_tree_copy(node
->tree
);
1320 for (i
= n
- 1; i
>= 0; --i
) {
1321 isl_schedule_tree
*parent
;
1323 parent
= isl_schedule_tree_list_get_schedule_tree(
1324 node
->ancestors
, i
);
1325 parent
= isl_schedule_tree_replace_child(parent
,
1326 node
->child_pos
[i
], tree
);
1327 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
1328 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
1333 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
1334 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
1336 isl_schedule_tree_free(node
->tree
);
1337 node
->tree
= isl_schedule_node_get_leaf(node
);
1340 if (!node
->schedule
|| !node
->ancestors
)
1341 return isl_schedule_node_free(node
);
1346 /* Replace the subtree that "pos" points to by "tree", updating
1347 * the ancestors to maintain a consistent state.
1349 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
1350 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
1354 if (pos
->tree
== tree
) {
1355 isl_schedule_tree_free(tree
);
1359 pos
= isl_schedule_node_cow(pos
);
1363 isl_schedule_tree_free(pos
->tree
);
1366 return update_ancestors(pos
);
1368 isl_schedule_node_free(pos
);
1369 isl_schedule_tree_free(tree
);
1373 /* Make sure we can insert a node between "node" and its parent.
1374 * Return -1 on error, reporting the reason why we cannot insert a node.
1376 static int check_insert(__isl_keep isl_schedule_node
*node
)
1379 enum isl_schedule_node_type type
;
1381 has_parent
= isl_schedule_node_has_parent(node
);
1385 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1386 "cannot insert node outside of root", return -1);
1388 type
= isl_schedule_node_get_parent_type(node
);
1389 if (type
== isl_schedule_node_error
)
1391 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
1392 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1393 "cannot insert node between set or sequence node "
1394 "and its filter children", return -1);
1399 /* Insert a band node with partial schedule "mupa" between "node" and
1401 * Return a pointer to the new band node.
1403 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
1404 __isl_take isl_schedule_node
*node
,
1405 __isl_take isl_multi_union_pw_aff
*mupa
)
1407 isl_schedule_band
*band
;
1408 isl_schedule_tree
*tree
;
1410 if (check_insert(node
) < 0)
1411 node
= isl_schedule_node_free(node
);
1413 tree
= isl_schedule_node_get_tree(node
);
1414 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
1415 tree
= isl_schedule_tree_insert_band(tree
, band
);
1416 node
= isl_schedule_node_graft_tree(node
, tree
);
1421 /* Insert a filter node with filter "filter" between "node" and its parent.
1422 * Return a pointer to the new filter node.
1424 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
1425 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
1427 isl_schedule_tree
*tree
;
1429 if (check_insert(node
) < 0)
1430 node
= isl_schedule_node_free(node
);
1432 tree
= isl_schedule_node_get_tree(node
);
1433 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
1434 node
= isl_schedule_node_graft_tree(node
, tree
);
1439 /* Attach the current subtree of "node" to a sequence of filter tree nodes
1440 * with filters described by "filters", attach this sequence
1441 * of filter tree nodes as children to a new tree of type "type" and
1442 * replace the original subtree of "node" by this new tree.
1444 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
1445 __isl_take isl_schedule_node
*node
,
1446 enum isl_schedule_node_type type
,
1447 __isl_take isl_union_set_list
*filters
)
1451 isl_schedule_tree
*tree
;
1452 isl_schedule_tree_list
*list
;
1454 if (check_insert(node
) < 0)
1455 node
= isl_schedule_node_free(node
);
1457 if (!node
|| !filters
)
1460 ctx
= isl_schedule_node_get_ctx(node
);
1461 n
= isl_union_set_list_n_union_set(filters
);
1462 list
= isl_schedule_tree_list_alloc(ctx
, n
);
1463 for (i
= 0; i
< n
; ++i
) {
1464 isl_schedule_tree
*tree
;
1465 isl_union_set
*filter
;
1467 tree
= isl_schedule_node_get_tree(node
);
1468 filter
= isl_union_set_list_get_union_set(filters
, i
);
1469 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
1470 list
= isl_schedule_tree_list_add(list
, tree
);
1472 tree
= isl_schedule_tree_from_children(type
, list
);
1473 node
= isl_schedule_node_graft_tree(node
, tree
);
1475 isl_union_set_list_free(filters
);
1478 isl_union_set_list_free(filters
);
1479 isl_schedule_node_free(node
);
1483 /* Insert a sequence node with child filters "filters" between "node" and
1484 * its parent. That is, the tree that "node" points to is attached
1485 * to each of the child nodes of the filter nodes.
1486 * Return a pointer to the new sequence node.
1488 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
1489 __isl_take isl_schedule_node
*node
,
1490 __isl_take isl_union_set_list
*filters
)
1492 return isl_schedule_node_insert_children(node
,
1493 isl_schedule_node_sequence
, filters
);
1496 /* Insert a set node with child filters "filters" between "node" and
1497 * its parent. That is, the tree that "node" points to is attached
1498 * to each of the child nodes of the filter nodes.
1499 * Return a pointer to the new set node.
1501 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
1502 __isl_take isl_schedule_node
*node
,
1503 __isl_take isl_union_set_list
*filters
)
1505 return isl_schedule_node_insert_children(node
,
1506 isl_schedule_node_set
, filters
);
1509 /* Print "node" to "p".
1511 __isl_give isl_printer
*isl_printer_print_schedule_node(
1512 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
1515 return isl_printer_free(p
);
1516 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
,
1517 isl_schedule_tree_list_n_schedule_tree(node
->ancestors
),
1521 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
1524 isl_printer
*printer
;
1529 ctx
= isl_schedule_node_get_ctx(node
);
1530 printer
= isl_printer_to_file(ctx
, stderr
);
1531 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
1532 printer
= isl_printer_print_schedule_node(printer
, node
);
1534 isl_printer_free(printer
);