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 /* Do "node1" and "node2" point to the same position in the same
224 int isl_schedule_node_is_equal(__isl_keep isl_schedule_node
*node1
,
225 __isl_keep isl_schedule_node
*node2
)
229 if (!node1
|| !node2
)
233 if (node1
->schedule
!= node2
->schedule
)
236 n1
= isl_schedule_node_get_tree_depth(node1
);
237 n2
= isl_schedule_node_get_tree_depth(node2
);
240 for (i
= 0; i
< n1
; ++i
)
241 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
247 /* Internal data structure for
248 * isl_schedule_node_get_prefix_schedule_union_pw_multi_aff
250 * "initialized" is set if the filter field has been initialized.
251 * "universe_filter" is set if we are only collecting the universes of filters
252 * "collect_prefix" is set if we are collecting prefixes.
253 * "filter" collects all outer filters and is NULL until "initialized" is set.
254 * "prefix" collects all outer band partial schedules (if "collect_prefix"
255 * is set). If it is used, then it is initialized by the caller
256 * of collect_filter_prefix to a zero-dimensional function.
258 struct isl_schedule_node_get_filter_prefix_data
{
262 isl_union_set
*filter
;
263 isl_multi_union_pw_aff
*prefix
;
266 /* Update "data" based on the tree node "tree" in case "data" has
267 * not been initialized yet.
269 * Return 0 on success and -1 on error.
271 * If "tree" is a filter, then we set data->filter to this filter
273 * If "tree" is a domain, then this means we have reached the root
274 * of the schedule tree without being able to extract any information.
275 * We therefore initialize data->filter to the universe of the domain.
276 * If "tree" is a band with at least one member, then we set data->filter
277 * to the universe of the schedule domain and replace the zero-dimensional
278 * data->prefix by the band schedule (if data->collect_prefix is set).
280 static int collect_filter_prefix_init(__isl_keep isl_schedule_tree
*tree
,
281 struct isl_schedule_node_get_filter_prefix_data
*data
)
283 enum isl_schedule_node_type type
;
284 isl_multi_union_pw_aff
*mupa
;
285 isl_union_set
*filter
;
287 type
= isl_schedule_tree_get_type(tree
);
289 case isl_schedule_node_error
:
291 case isl_schedule_node_leaf
:
292 case isl_schedule_node_sequence
:
293 case isl_schedule_node_set
:
295 case isl_schedule_node_domain
:
296 filter
= isl_schedule_tree_domain_get_domain(tree
);
297 filter
= isl_union_set_universe(filter
);
298 data
->filter
= filter
;
300 case isl_schedule_node_band
:
301 if (isl_schedule_tree_band_n_member(tree
) == 0)
303 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
304 if (data
->collect_prefix
) {
305 isl_multi_union_pw_aff_free(data
->prefix
);
306 mupa
= isl_multi_union_pw_aff_reset_tuple_id(mupa
,
308 data
->prefix
= isl_multi_union_pw_aff_copy(mupa
);
310 filter
= isl_multi_union_pw_aff_domain(mupa
);
311 filter
= isl_union_set_universe(filter
);
312 data
->filter
= filter
;
314 case isl_schedule_node_filter
:
315 filter
= isl_schedule_tree_filter_get_filter(tree
);
316 if (data
->universe_filter
)
317 filter
= isl_union_set_universe(filter
);
318 data
->filter
= filter
;
322 if ((data
->collect_prefix
&& !data
->prefix
) || !data
->filter
)
325 data
->initialized
= 1;
330 /* Update "data" based on the tree node "tree" in case "data" has
331 * already been initialized.
333 * Return 0 on success and -1 on error.
335 * If "tree" is a filter, then we intersect data->filter with this filter
337 * If "tree" is a band with at least one member and data->collect_prefix
338 * is set, then we extend data->prefix with the band schedule.
340 static int collect_filter_prefix_update(__isl_keep isl_schedule_tree
*tree
,
341 struct isl_schedule_node_get_filter_prefix_data
*data
)
343 enum isl_schedule_node_type type
;
344 isl_multi_union_pw_aff
*mupa
;
345 isl_union_set
*filter
;
347 type
= isl_schedule_tree_get_type(tree
);
349 case isl_schedule_node_error
:
351 case isl_schedule_node_domain
:
352 case isl_schedule_node_leaf
:
353 case isl_schedule_node_sequence
:
354 case isl_schedule_node_set
:
356 case isl_schedule_node_band
:
357 if (isl_schedule_tree_band_n_member(tree
) == 0)
359 if (!data
->collect_prefix
)
361 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
362 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(mupa
,
367 case isl_schedule_node_filter
:
368 filter
= isl_schedule_tree_filter_get_filter(tree
);
369 if (data
->universe_filter
)
370 filter
= isl_union_set_universe(filter
);
371 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
380 /* Collect filter and/or prefix information from the elements
381 * in "list" (which represent the ancestors of a node).
382 * Store the results in "data".
384 * Return 0 on success and -1 on error.
386 * We traverse the list from innermost ancestor (last element)
387 * to outermost ancestor (first element), calling collect_filter_prefix_init
388 * on each node as long as we have not been able to extract any information
389 * yet and collect_filter_prefix_update afterwards.
390 * On successful return, data->initialized will be set since the outermost
391 * ancestor is a domain node, which always results in an initialization.
393 static int collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
394 struct isl_schedule_node_get_filter_prefix_data
*data
)
398 data
->initialized
= 0;
404 n
= isl_schedule_tree_list_n_schedule_tree(list
);
405 for (i
= n
- 1; i
>= 0; --i
) {
406 isl_schedule_tree
*tree
;
409 tree
= isl_schedule_tree_list_get_schedule_tree(list
, i
);
412 if (!data
->initialized
)
413 r
= collect_filter_prefix_init(tree
, data
);
415 r
= collect_filter_prefix_update(tree
, data
);
416 isl_schedule_tree_free(tree
);
424 /* Return the concatenation of the partial schedules of all outer band
425 * nodes of "node" interesected with all outer filters
426 * as an isl_union_pw_multi_aff.
428 * If "node" is pointing at the root of the schedule tree, then
429 * there are no domain elements reaching the current node, so
430 * we return an empty result.
432 * We collect all the filters and partial schedules in collect_filter_prefix.
433 * The partial schedules are collected as an isl_multi_union_pw_aff.
434 * If this isl_multi_union_pw_aff is zero-dimensional, then it does not
435 * contain any domain information, so we construct the isl_union_pw_multi_aff
436 * result as a zero-dimensional function on the collected filter.
437 * Otherwise, we convert the isl_multi_union_pw_aff to
438 * an isl_multi_union_pw_aff and intersect the domain with the filter.
440 __isl_give isl_union_pw_multi_aff
*
441 isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(
442 __isl_keep isl_schedule_node
*node
)
445 isl_union_pw_multi_aff
*prefix
;
446 struct isl_schedule_node_get_filter_prefix_data data
;
451 space
= isl_schedule_get_space(node
->schedule
);
452 if (node
->tree
== node
->schedule
->root
)
453 return isl_union_pw_multi_aff_empty(space
);
455 space
= isl_space_set_from_params(space
);
456 data
.universe_filter
= 0;
457 data
.collect_prefix
= 1;
458 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
460 if (collect_filter_prefix(node
->ancestors
, &data
) < 0)
461 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
464 isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
) == 0) {
465 isl_multi_union_pw_aff_free(data
.prefix
);
466 prefix
= isl_union_pw_multi_aff_from_domain(data
.filter
);
469 isl_union_pw_multi_aff_from_multi_union_pw_aff(data
.prefix
);
470 prefix
= isl_union_pw_multi_aff_intersect_domain(prefix
,
477 /* Return the concatenation of the partial schedules of all outer band
478 * nodes of "node" interesected with all outer filters
479 * as an isl_union_map.
481 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_union_map(
482 __isl_keep isl_schedule_node
*node
)
484 isl_union_pw_multi_aff
*upma
;
486 upma
= isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(node
);
487 return isl_union_map_from_union_pw_multi_aff(upma
);
490 /* Return the union of universe sets of the domain elements that reach "node".
492 * If "node" is pointing at the root of the schedule tree, then
493 * there are no domain elements reaching the current node, so
494 * we return an empty result.
496 * Otherwise, we collect the universes of all filters reaching the node
497 * in collect_filter_prefix.
499 __isl_give isl_union_set
*isl_schedule_node_get_universe_domain(
500 __isl_keep isl_schedule_node
*node
)
502 struct isl_schedule_node_get_filter_prefix_data data
;
507 if (node
->tree
== node
->schedule
->root
) {
510 space
= isl_schedule_get_space(node
->schedule
);
511 return isl_union_set_empty(space
);
514 data
.universe_filter
= 1;
515 data
.collect_prefix
= 0;
518 if (collect_filter_prefix(node
->ancestors
, &data
) < 0)
519 data
.filter
= isl_union_set_free(data
.filter
);
524 /* Return the subtree schedule of "node".
526 * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle
527 * trees that do not contain any schedule information, we first
528 * move down to the first relevant descendant and handle leaves ourselves.
530 __isl_give isl_union_map
*isl_schedule_node_get_subtree_schedule_union_map(
531 __isl_keep isl_schedule_node
*node
)
533 isl_schedule_tree
*tree
, *leaf
;
536 tree
= isl_schedule_node_get_tree(node
);
537 leaf
= isl_schedule_node_peek_leaf(node
);
538 tree
= isl_schedule_tree_first_schedule_descendant(tree
, leaf
);
542 isl_union_set
*domain
;
543 domain
= isl_schedule_node_get_universe_domain(node
);
544 isl_schedule_tree_free(tree
);
545 return isl_union_map_from_domain(domain
);
548 umap
= isl_schedule_tree_get_subtree_schedule_union_map(tree
);
549 isl_schedule_tree_free(tree
);
553 /* Return the number of ancestors of "node" in its schedule tree.
555 int isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node
*node
)
559 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
562 /* Does "node" have a parent?
564 * That is, does it point to any node of the schedule other than the root?
566 int isl_schedule_node_has_parent(__isl_keep isl_schedule_node
*node
)
570 if (!node
->ancestors
)
573 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) != 0;
576 /* Return the position of "node" among the children of its parent.
578 int isl_schedule_node_get_child_position(__isl_keep isl_schedule_node
*node
)
585 has_parent
= isl_schedule_node_has_parent(node
);
589 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
590 "node has no parent", return -1);
592 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
593 return node
->child_pos
[n
- 1];
596 /* Does the parent (if any) of "node" have any children with a smaller child
597 * position than this one?
599 int isl_schedule_node_has_previous_sibling(__isl_keep isl_schedule_node
*node
)
606 has_parent
= isl_schedule_node_has_parent(node
);
607 if (has_parent
< 0 || !has_parent
)
610 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
612 return node
->child_pos
[n
- 1] > 0;
615 /* Does the parent (if any) of "node" have any children with a greater child
616 * position than this one?
618 int isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node
*node
)
622 isl_schedule_tree
*tree
;
626 has_parent
= isl_schedule_node_has_parent(node
);
627 if (has_parent
< 0 || !has_parent
)
630 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
631 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
634 n_child
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
635 isl_schedule_tree_free(tree
);
637 return node
->child_pos
[n
- 1] + 1 < n_child
;
640 /* Does "node" have any children?
642 * Any node other than the leaf nodes is considered to have at least
643 * one child, even if the corresponding isl_schedule_tree does not
646 int isl_schedule_node_has_children(__isl_keep isl_schedule_node
*node
)
650 return !isl_schedule_tree_is_leaf(node
->tree
);
653 /* Return the number of children of "node"?
655 * Any node other than the leaf nodes is considered to have at least
656 * one child, even if the corresponding isl_schedule_tree does not
657 * have any children. That is, the number of children of "node" is
658 * only zero if its tree is the explicit empty tree. Otherwise,
659 * if the isl_schedule_tree has any children, then it is equal
660 * to the number of children of "node". If it has zero children,
661 * then "node" still has a leaf node as child.
663 int isl_schedule_node_n_children(__isl_keep isl_schedule_node
*node
)
670 if (isl_schedule_tree_is_leaf(node
->tree
))
673 n
= isl_schedule_tree_n_children(node
->tree
);
680 /* Move the "node" pointer to the parent of the node it currently points to.
682 __isl_give isl_schedule_node
*isl_schedule_node_parent(
683 __isl_take isl_schedule_node
*node
)
686 isl_schedule_tree
*tree
;
688 node
= isl_schedule_node_cow(node
);
691 if (!isl_schedule_node_has_parent(node
))
692 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
693 "node has no parent",
694 return isl_schedule_node_free(node
));
695 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
696 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
697 isl_schedule_tree_free(node
->tree
);
699 node
->ancestors
= isl_schedule_tree_list_drop(node
->ancestors
,
701 if (!node
->ancestors
|| !node
->tree
)
702 return isl_schedule_node_free(node
);
707 /* Move the "node" pointer to the child at position "pos" of the node
708 * it currently points to.
710 __isl_give isl_schedule_node
*isl_schedule_node_child(
711 __isl_take isl_schedule_node
*node
, int pos
)
715 isl_schedule_tree
*tree
;
718 node
= isl_schedule_node_cow(node
);
721 if (!isl_schedule_node_has_children(node
))
722 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
723 "node has no children",
724 return isl_schedule_node_free(node
));
726 ctx
= isl_schedule_node_get_ctx(node
);
727 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
728 child_pos
= isl_realloc_array(ctx
, node
->child_pos
, int, n
+ 1);
730 return isl_schedule_node_free(node
);
731 node
->child_pos
= child_pos
;
732 node
->child_pos
[n
] = pos
;
734 node
->ancestors
= isl_schedule_tree_list_add(node
->ancestors
,
735 isl_schedule_tree_copy(node
->tree
));
737 if (isl_schedule_tree_has_children(tree
))
738 tree
= isl_schedule_tree_get_child(tree
, pos
);
740 tree
= isl_schedule_node_get_leaf(node
);
741 isl_schedule_tree_free(node
->tree
);
744 if (!node
->tree
|| !node
->ancestors
)
745 return isl_schedule_node_free(node
);
750 /* Move the "node" pointer to the first child of the node
751 * it currently points to.
753 __isl_give isl_schedule_node
*isl_schedule_node_first_child(
754 __isl_take isl_schedule_node
*node
)
756 return isl_schedule_node_child(node
, 0);
759 /* Move the "node" pointer to the child of this node's parent in
760 * the previous child position.
762 __isl_give isl_schedule_node
*isl_schedule_node_previous_sibling(
763 __isl_take isl_schedule_node
*node
)
766 isl_schedule_tree
*parent
, *tree
;
768 node
= isl_schedule_node_cow(node
);
771 if (!isl_schedule_node_has_previous_sibling(node
))
772 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
773 "node has no previous sibling",
774 return isl_schedule_node_free(node
));
776 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
777 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
780 return isl_schedule_node_free(node
);
781 node
->child_pos
[n
- 1]--;
782 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
783 node
->child_pos
[n
- 1]);
784 isl_schedule_tree_free(parent
);
786 return isl_schedule_node_free(node
);
787 isl_schedule_tree_free(node
->tree
);
793 /* Move the "node" pointer to the child of this node's parent in
794 * the next child position.
796 __isl_give isl_schedule_node
*isl_schedule_node_next_sibling(
797 __isl_take isl_schedule_node
*node
)
800 isl_schedule_tree
*parent
, *tree
;
802 node
= isl_schedule_node_cow(node
);
805 if (!isl_schedule_node_has_next_sibling(node
))
806 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
807 "node has no next sibling",
808 return isl_schedule_node_free(node
));
810 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
811 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
814 return isl_schedule_node_free(node
);
815 node
->child_pos
[n
- 1]++;
816 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
817 node
->child_pos
[n
- 1]);
818 isl_schedule_tree_free(parent
);
820 return isl_schedule_node_free(node
);
821 isl_schedule_tree_free(node
->tree
);
827 /* Return a copy to the child at position "pos" of "node".
829 __isl_give isl_schedule_node
*isl_schedule_node_get_child(
830 __isl_keep isl_schedule_node
*node
, int pos
)
832 return isl_schedule_node_child(isl_schedule_node_copy(node
), pos
);
835 /* Traverse the descendant of "node" in depth-first order, including
836 * "node" itself. Call "enter" whenever a node is entered and "leave"
837 * whenever a node is left. The callback "enter" is responsible
838 * for moving to the deepest initial subtree of its argument that
839 * should be traversed.
841 static __isl_give isl_schedule_node
*traverse(
842 __isl_take isl_schedule_node
*node
,
843 __isl_give isl_schedule_node
*(*enter
)(
844 __isl_take isl_schedule_node
*node
, void *user
),
845 __isl_give isl_schedule_node
*(*leave
)(
846 __isl_take isl_schedule_node
*node
, void *user
),
854 depth
= isl_schedule_node_get_tree_depth(node
);
856 node
= enter(node
, user
);
857 node
= leave(node
, user
);
858 while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
&&
859 !isl_schedule_node_has_next_sibling(node
)) {
860 node
= isl_schedule_node_parent(node
);
861 node
= leave(node
, user
);
863 if (node
&& isl_schedule_node_get_tree_depth(node
) > depth
)
864 node
= isl_schedule_node_next_sibling(node
);
865 } while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
);
870 /* Internal data structure for isl_schedule_node_foreach_descendant.
872 * "fn" is the user-specified callback function.
873 * "user" is the user-specified argument for the callback.
875 struct isl_schedule_node_preorder_data
{
876 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
);
880 /* Callback for "traverse" to enter a node and to move
881 * to the deepest initial subtree that should be traversed
882 * for use in a preorder visit.
884 * If the user callback returns a negative value, then we abort
885 * the traversal. If this callback returns zero, then we skip
886 * the subtree rooted at the current node. Otherwise, we move
887 * down to the first child and repeat the process until a leaf
890 static __isl_give isl_schedule_node
*preorder_enter(
891 __isl_take isl_schedule_node
*node
, void *user
)
893 struct isl_schedule_node_preorder_data
*data
= user
;
901 r
= data
->fn(node
, data
->user
);
903 return isl_schedule_node_free(node
);
906 } while (isl_schedule_node_has_children(node
) &&
907 (node
= isl_schedule_node_first_child(node
)) != NULL
);
912 /* Callback for "traverse" to leave a node
913 * for use in a preorder visit.
914 * Since we already visited the node when we entered it,
915 * we do not need to do anything here.
917 static __isl_give isl_schedule_node
*preorder_leave(
918 __isl_take isl_schedule_node
*node
, void *user
)
923 /* Traverse the descendants of "node" (including the node itself)
924 * in depth first preorder.
926 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
927 * If "fn" returns 0 on any of the nodes, then the subtree rooted
928 * at that node is skipped.
930 * Return 0 on success and -1 on failure.
932 int isl_schedule_node_foreach_descendant(__isl_keep isl_schedule_node
*node
,
933 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
), void *user
)
935 struct isl_schedule_node_preorder_data data
= { fn
, user
};
937 node
= isl_schedule_node_copy(node
);
938 node
= traverse(node
, &preorder_enter
, &preorder_leave
, &data
);
939 isl_schedule_node_free(node
);
941 return node
? 0 : -1;
944 /* Internal data structure for isl_schedule_node_map_descendant.
946 * "fn" is the user-specified callback function.
947 * "user" is the user-specified argument for the callback.
949 struct isl_schedule_node_postorder_data
{
950 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
955 /* Callback for "traverse" to enter a node and to move
956 * to the deepest initial subtree that should be traversed
957 * for use in a postorder visit.
959 * Since we are performing a postorder visit, we only need
960 * to move to the deepest initial leaf here.
962 static __isl_give isl_schedule_node
*postorder_enter(
963 __isl_take isl_schedule_node
*node
, void *user
)
965 while (node
&& isl_schedule_node_has_children(node
))
966 node
= isl_schedule_node_first_child(node
);
971 /* Callback for "traverse" to leave a node
972 * for use in a postorder visit.
974 * Since we are performing a postorder visit, we need
975 * to call the user callback here.
977 static __isl_give isl_schedule_node
*postorder_leave(
978 __isl_take isl_schedule_node
*node
, void *user
)
980 struct isl_schedule_node_postorder_data
*data
= user
;
982 return data
->fn(node
, data
->user
);
985 /* Traverse the descendants of "node" (including the node itself)
986 * in depth first postorder, allowing the user to modify the visited node.
987 * The traversal continues from the node returned by the callback function.
988 * It is the responsibility of the user to ensure that this does not
989 * lead to an infinite loop. It is safest to always return a pointer
990 * to the same position (same ancestors and child positions) as the input node.
992 __isl_give isl_schedule_node
*isl_schedule_node_map_descendant(
993 __isl_take isl_schedule_node
*node
,
994 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
995 void *user
), void *user
)
997 struct isl_schedule_node_postorder_data data
= { fn
, user
};
999 return traverse(node
, &postorder_enter
, &postorder_leave
, &data
);
1002 /* Return the number of members in the given band node.
1004 unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node
*node
)
1006 return node
? isl_schedule_tree_band_n_member(node
->tree
) : 0;
1009 /* Is the band member at position "pos" of the band node "node"
1010 * marked coincident?
1012 int isl_schedule_node_band_member_get_coincident(
1013 __isl_keep isl_schedule_node
*node
, int pos
)
1017 return isl_schedule_tree_band_member_get_coincident(node
->tree
, pos
);
1020 /* Mark the band member at position "pos" the band node "node"
1021 * as being coincident or not according to "coincident".
1023 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_coincident(
1024 __isl_take isl_schedule_node
*node
, int pos
, int coincident
)
1027 isl_schedule_tree
*tree
;
1031 c
= isl_schedule_node_band_member_get_coincident(node
, pos
);
1032 if (c
== coincident
)
1035 tree
= isl_schedule_tree_copy(node
->tree
);
1036 tree
= isl_schedule_tree_band_member_set_coincident(tree
, pos
,
1038 node
= isl_schedule_node_graft_tree(node
, tree
);
1043 /* Is the band node "node" marked permutable?
1045 int isl_schedule_node_band_get_permutable(__isl_keep isl_schedule_node
*node
)
1050 return isl_schedule_tree_band_get_permutable(node
->tree
);
1053 /* Mark the band node "node" permutable or not according to "permutable"?
1055 __isl_give isl_schedule_node
*isl_schedule_node_band_set_permutable(
1056 __isl_take isl_schedule_node
*node
, int permutable
)
1058 isl_schedule_tree
*tree
;
1062 if (isl_schedule_node_band_get_permutable(node
) == permutable
)
1065 tree
= isl_schedule_tree_copy(node
->tree
);
1066 tree
= isl_schedule_tree_band_set_permutable(tree
, permutable
);
1067 node
= isl_schedule_node_graft_tree(node
, tree
);
1072 /* Return the schedule space of the band node.
1074 __isl_give isl_space
*isl_schedule_node_band_get_space(
1075 __isl_keep isl_schedule_node
*node
)
1080 return isl_schedule_tree_band_get_space(node
->tree
);
1083 /* Return the schedule of the band node in isolation.
1085 __isl_give isl_multi_union_pw_aff
*isl_schedule_node_band_get_partial_schedule(
1086 __isl_keep isl_schedule_node
*node
)
1091 return isl_schedule_tree_band_get_partial_schedule(node
->tree
);
1094 /* Return the schedule of the band node in isolation in the form of
1097 * If the band does not have any members, then we construct a universe map
1098 * with the universe of the domain elements reaching the node as domain.
1099 * Otherwise, we extract an isl_multi_union_pw_aff representation and
1100 * convert that to an isl_union_map.
1102 __isl_give isl_union_map
*isl_schedule_node_band_get_partial_schedule_union_map(
1103 __isl_keep isl_schedule_node
*node
)
1105 isl_multi_union_pw_aff
*mupa
;
1110 if (isl_schedule_node_get_type(node
) != isl_schedule_node_band
)
1111 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1112 "not a band node", return NULL
);
1113 if (isl_schedule_node_band_n_member(node
) == 0) {
1114 isl_union_set
*domain
;
1116 domain
= isl_schedule_node_get_universe_domain(node
);
1117 return isl_union_map_from_domain(domain
);
1120 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
1121 return isl_union_map_from_multi_union_pw_aff(mupa
);
1124 /* Make sure that that spaces of "node" and "mv" are the same.
1125 * Return -1 on error, reporting the error to the user.
1127 static int check_space_multi_val(__isl_keep isl_schedule_node
*node
,
1128 __isl_keep isl_multi_val
*mv
)
1130 isl_space
*node_space
, *mv_space
;
1133 node_space
= isl_schedule_node_band_get_space(node
);
1134 mv_space
= isl_multi_val_get_space(mv
);
1135 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1136 mv_space
, isl_dim_set
);
1137 isl_space_free(mv_space
);
1138 isl_space_free(node_space
);
1142 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1143 "spaces don't match", return -1);
1148 /* Multiply the partial schedule of the band node "node"
1149 * with the factors in "mv".
1151 __isl_give isl_schedule_node
*isl_schedule_node_band_scale(
1152 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1154 isl_schedule_tree
*tree
;
1158 if (check_space_multi_val(node
, mv
) < 0)
1161 tree
= isl_schedule_node_get_tree(node
);
1162 tree
= isl_schedule_tree_band_scale(tree
, mv
);
1163 return isl_schedule_node_graft_tree(node
, tree
);
1165 isl_multi_val_free(mv
);
1166 isl_schedule_node_free(node
);
1170 /* Divide the partial schedule of the band node "node"
1171 * by the factors in "mv".
1173 __isl_give isl_schedule_node
*isl_schedule_node_band_scale_down(
1174 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1176 isl_schedule_tree
*tree
;
1180 if (check_space_multi_val(node
, mv
) < 0)
1183 tree
= isl_schedule_node_get_tree(node
);
1184 tree
= isl_schedule_tree_band_scale_down(tree
, mv
);
1185 return isl_schedule_node_graft_tree(node
, tree
);
1187 isl_multi_val_free(mv
);
1188 isl_schedule_node_free(node
);
1192 /* Tile "node" with tile sizes "sizes".
1194 * The current node is replaced by two nested nodes corresponding
1195 * to the tile dimensions and the point dimensions.
1197 * Return a pointer to the outer (tile) node.
1199 * If the scale tile loops option is set, then the tile loops
1200 * are scaled by the tile sizes. If the shift point loops option is set,
1201 * then the point loops are shifted to start at zero.
1202 * In particular, these options affect the tile and point loop schedules
1205 * scale shift original tile point
1207 * 0 0 i floor(i/s) i
1208 * 1 0 i s * floor(i/s) i
1209 * 0 1 i floor(i/s) i - s * floor(i/s)
1210 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1212 __isl_give isl_schedule_node
*isl_schedule_node_band_tile(
1213 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*sizes
)
1215 isl_schedule_tree
*tree
;
1217 if (!node
|| !sizes
)
1220 if (check_space_multi_val(node
, sizes
) < 0)
1223 tree
= isl_schedule_node_get_tree(node
);
1224 tree
= isl_schedule_tree_band_tile(tree
, sizes
);
1225 return isl_schedule_node_graft_tree(node
, tree
);
1227 isl_multi_val_free(sizes
);
1228 isl_schedule_node_free(node
);
1232 /* Move the band node "node" down to all the leaves in the subtree
1234 * Return a pointer to the node in the resulting tree that is in the same
1235 * position as the node pointed to by "node" in the original tree.
1237 * If the node only has a leaf child, then nothing needs to be done.
1238 * Otherwise, the child of the node is removed and the result is
1239 * appended to all the leaves in the subtree rooted at the original child.
1240 * The original node is then replaced by the result of this operation.
1242 __isl_give isl_schedule_node
*isl_schedule_node_band_sink(
1243 __isl_take isl_schedule_node
*node
)
1245 enum isl_schedule_node_type type
;
1246 isl_schedule_tree
*tree
, *child
;
1251 type
= isl_schedule_node_get_type(node
);
1252 if (type
!= isl_schedule_node_band
)
1253 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1254 "not a band node", isl_schedule_node_free(node
));
1255 if (isl_schedule_tree_n_children(node
->tree
) == 0)
1258 tree
= isl_schedule_node_get_tree(node
);
1259 child
= isl_schedule_tree_get_child(tree
, 0);
1260 tree
= isl_schedule_tree_reset_children(tree
);
1261 tree
= isl_schedule_tree_append_to_leaves(child
, tree
);
1263 return isl_schedule_node_graft_tree(node
, tree
);
1266 /* Split "node" into two nested band nodes, one with the first "pos"
1267 * dimensions and one with the remaining dimensions.
1268 * The schedules of the two band nodes live in anonymous spaces.
1270 __isl_give isl_schedule_node
*isl_schedule_node_band_split(
1271 __isl_take isl_schedule_node
*node
, int pos
)
1273 isl_schedule_tree
*tree
;
1275 tree
= isl_schedule_node_get_tree(node
);
1276 tree
= isl_schedule_tree_band_split(tree
, pos
);
1277 return isl_schedule_node_graft_tree(node
, tree
);
1280 /* Return the domain of the domain node "node".
1282 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
1283 __isl_keep isl_schedule_node
*node
)
1288 return isl_schedule_tree_domain_get_domain(node
->tree
);
1291 /* Return the filter of the filter node "node".
1293 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
1294 __isl_keep isl_schedule_node
*node
)
1299 return isl_schedule_tree_filter_get_filter(node
->tree
);
1302 /* Replace the filter of filter node "node" by "filter".
1304 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
1305 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
1307 isl_schedule_tree
*tree
;
1309 if (!node
|| !filter
)
1312 tree
= isl_schedule_tree_copy(node
->tree
);
1313 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
1314 return isl_schedule_node_graft_tree(node
, tree
);
1316 isl_schedule_node_free(node
);
1317 isl_union_set_free(filter
);
1321 /* Update the ancestors of "node" to point to the tree that "node"
1323 * That is, replace the child in the original parent that corresponds
1324 * to the current tree position by node->tree and continue updating
1325 * the ancestors in the same way until the root is reached.
1327 * If "node" originally points to a leaf of the schedule tree, then make sure
1328 * that in the end it points to a leaf in the updated schedule tree.
1330 static __isl_give isl_schedule_node
*update_ancestors(
1331 __isl_take isl_schedule_node
*node
)
1336 isl_schedule_tree
*tree
;
1338 node
= isl_schedule_node_cow(node
);
1342 ctx
= isl_schedule_node_get_ctx(node
);
1343 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1344 tree
= isl_schedule_tree_copy(node
->tree
);
1346 for (i
= n
- 1; i
>= 0; --i
) {
1347 isl_schedule_tree
*parent
;
1349 parent
= isl_schedule_tree_list_get_schedule_tree(
1350 node
->ancestors
, i
);
1351 parent
= isl_schedule_tree_replace_child(parent
,
1352 node
->child_pos
[i
], tree
);
1353 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
1354 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
1359 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
1360 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
1362 isl_schedule_tree_free(node
->tree
);
1363 node
->tree
= isl_schedule_node_get_leaf(node
);
1366 if (!node
->schedule
|| !node
->ancestors
)
1367 return isl_schedule_node_free(node
);
1372 /* Replace the subtree that "pos" points to by "tree", updating
1373 * the ancestors to maintain a consistent state.
1375 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
1376 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
1380 if (pos
->tree
== tree
) {
1381 isl_schedule_tree_free(tree
);
1385 pos
= isl_schedule_node_cow(pos
);
1389 isl_schedule_tree_free(pos
->tree
);
1392 return update_ancestors(pos
);
1394 isl_schedule_node_free(pos
);
1395 isl_schedule_tree_free(tree
);
1399 /* Make sure we can insert a node between "node" and its parent.
1400 * Return -1 on error, reporting the reason why we cannot insert a node.
1402 static int check_insert(__isl_keep isl_schedule_node
*node
)
1405 enum isl_schedule_node_type type
;
1407 has_parent
= isl_schedule_node_has_parent(node
);
1411 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1412 "cannot insert node outside of root", return -1);
1414 type
= isl_schedule_node_get_parent_type(node
);
1415 if (type
== isl_schedule_node_error
)
1417 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
1418 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1419 "cannot insert node between set or sequence node "
1420 "and its filter children", return -1);
1425 /* Insert a band node with partial schedule "mupa" between "node" and
1427 * Return a pointer to the new band node.
1429 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
1430 __isl_take isl_schedule_node
*node
,
1431 __isl_take isl_multi_union_pw_aff
*mupa
)
1433 isl_schedule_band
*band
;
1434 isl_schedule_tree
*tree
;
1436 if (check_insert(node
) < 0)
1437 node
= isl_schedule_node_free(node
);
1439 tree
= isl_schedule_node_get_tree(node
);
1440 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
1441 tree
= isl_schedule_tree_insert_band(tree
, band
);
1442 node
= isl_schedule_node_graft_tree(node
, tree
);
1447 /* Insert a filter node with filter "filter" between "node" and its parent.
1448 * Return a pointer to the new filter node.
1450 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
1451 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
1453 isl_schedule_tree
*tree
;
1455 if (check_insert(node
) < 0)
1456 node
= isl_schedule_node_free(node
);
1458 tree
= isl_schedule_node_get_tree(node
);
1459 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
1460 node
= isl_schedule_node_graft_tree(node
, tree
);
1465 /* Attach the current subtree of "node" to a sequence of filter tree nodes
1466 * with filters described by "filters", attach this sequence
1467 * of filter tree nodes as children to a new tree of type "type" and
1468 * replace the original subtree of "node" by this new tree.
1470 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
1471 __isl_take isl_schedule_node
*node
,
1472 enum isl_schedule_node_type type
,
1473 __isl_take isl_union_set_list
*filters
)
1477 isl_schedule_tree
*tree
;
1478 isl_schedule_tree_list
*list
;
1480 if (check_insert(node
) < 0)
1481 node
= isl_schedule_node_free(node
);
1483 if (!node
|| !filters
)
1486 ctx
= isl_schedule_node_get_ctx(node
);
1487 n
= isl_union_set_list_n_union_set(filters
);
1488 list
= isl_schedule_tree_list_alloc(ctx
, n
);
1489 for (i
= 0; i
< n
; ++i
) {
1490 isl_schedule_tree
*tree
;
1491 isl_union_set
*filter
;
1493 tree
= isl_schedule_node_get_tree(node
);
1494 filter
= isl_union_set_list_get_union_set(filters
, i
);
1495 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
1496 list
= isl_schedule_tree_list_add(list
, tree
);
1498 tree
= isl_schedule_tree_from_children(type
, list
);
1499 node
= isl_schedule_node_graft_tree(node
, tree
);
1501 isl_union_set_list_free(filters
);
1504 isl_union_set_list_free(filters
);
1505 isl_schedule_node_free(node
);
1509 /* Insert a sequence node with child filters "filters" between "node" and
1510 * its parent. That is, the tree that "node" points to is attached
1511 * to each of the child nodes of the filter nodes.
1512 * Return a pointer to the new sequence node.
1514 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
1515 __isl_take isl_schedule_node
*node
,
1516 __isl_take isl_union_set_list
*filters
)
1518 return isl_schedule_node_insert_children(node
,
1519 isl_schedule_node_sequence
, filters
);
1522 /* Insert a set node with child filters "filters" between "node" and
1523 * its parent. That is, the tree that "node" points to is attached
1524 * to each of the child nodes of the filter nodes.
1525 * Return a pointer to the new set node.
1527 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
1528 __isl_take isl_schedule_node
*node
,
1529 __isl_take isl_union_set_list
*filters
)
1531 return isl_schedule_node_insert_children(node
,
1532 isl_schedule_node_set
, filters
);
1535 /* Reset the user pointer on all identifiers of parameters and tuples
1536 * in the schedule node "node".
1538 __isl_give isl_schedule_node
*isl_schedule_node_reset_user(
1539 __isl_take isl_schedule_node
*node
)
1541 isl_schedule_tree
*tree
;
1543 tree
= isl_schedule_node_get_tree(node
);
1544 tree
= isl_schedule_tree_reset_user(tree
);
1545 node
= isl_schedule_node_graft_tree(node
, tree
);
1550 /* Align the parameters of the schedule node "node" to those of "space".
1552 __isl_give isl_schedule_node
*isl_schedule_node_align_params(
1553 __isl_take isl_schedule_node
*node
, __isl_take isl_space
*space
)
1555 isl_schedule_tree
*tree
;
1557 tree
= isl_schedule_node_get_tree(node
);
1558 tree
= isl_schedule_tree_align_params(tree
, space
);
1559 node
= isl_schedule_node_graft_tree(node
, tree
);
1564 /* Print "node" to "p".
1566 __isl_give isl_printer
*isl_printer_print_schedule_node(
1567 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
1570 return isl_printer_free(p
);
1571 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
,
1572 isl_schedule_tree_list_n_schedule_tree(node
->ancestors
),
1576 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
1579 isl_printer
*printer
;
1584 ctx
= isl_schedule_node_get_ctx(node
);
1585 printer
= isl_printer_to_file(ctx
, stderr
);
1586 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
1587 printer
= isl_printer_print_schedule_node(printer
, node
);
1589 isl_printer_free(printer
);