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 /* Return the number of members in the given band node.
811 unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node
*node
)
813 return node
? isl_schedule_tree_band_n_member(node
->tree
) : 0;
816 /* Is the band member at position "pos" of the band node "node"
819 int isl_schedule_node_band_member_get_coincident(
820 __isl_keep isl_schedule_node
*node
, int pos
)
824 return isl_schedule_tree_band_member_get_coincident(node
->tree
, pos
);
827 /* Mark the band member at position "pos" the band node "node"
828 * as being coincident or not according to "coincident".
830 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_coincident(
831 __isl_take isl_schedule_node
*node
, int pos
, int coincident
)
834 isl_schedule_tree
*tree
;
838 c
= isl_schedule_node_band_member_get_coincident(node
, pos
);
842 tree
= isl_schedule_tree_copy(node
->tree
);
843 tree
= isl_schedule_tree_band_member_set_coincident(tree
, pos
,
845 node
= isl_schedule_node_graft_tree(node
, tree
);
850 /* Is the band node "node" marked permutable?
852 int isl_schedule_node_band_get_permutable(__isl_keep isl_schedule_node
*node
)
857 return isl_schedule_tree_band_get_permutable(node
->tree
);
860 /* Mark the band node "node" permutable or not according to "permutable"?
862 __isl_give isl_schedule_node
*isl_schedule_node_band_set_permutable(
863 __isl_take isl_schedule_node
*node
, int permutable
)
865 isl_schedule_tree
*tree
;
869 if (isl_schedule_node_band_get_permutable(node
) == permutable
)
872 tree
= isl_schedule_tree_copy(node
->tree
);
873 tree
= isl_schedule_tree_band_set_permutable(tree
, permutable
);
874 node
= isl_schedule_node_graft_tree(node
, tree
);
879 /* Return the schedule space of the band node.
881 __isl_give isl_space
*isl_schedule_node_band_get_space(
882 __isl_keep isl_schedule_node
*node
)
887 return isl_schedule_tree_band_get_space(node
->tree
);
890 /* Return the schedule of the band node in isolation.
892 __isl_give isl_multi_union_pw_aff
*isl_schedule_node_band_get_partial_schedule(
893 __isl_keep isl_schedule_node
*node
)
898 return isl_schedule_tree_band_get_partial_schedule(node
->tree
);
901 /* Return the schedule of the band node in isolation in the form of
904 * If the band does not have any members, then we construct a universe map
905 * with the universe of the domain elements reaching the node as domain.
906 * Otherwise, we extract an isl_multi_union_pw_aff representation and
907 * convert that to an isl_union_map.
909 __isl_give isl_union_map
*isl_schedule_node_band_get_partial_schedule_union_map(
910 __isl_keep isl_schedule_node
*node
)
912 isl_multi_union_pw_aff
*mupa
;
917 if (isl_schedule_node_get_type(node
) != isl_schedule_node_band
)
918 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
919 "not a band node", return NULL
);
920 if (isl_schedule_node_band_n_member(node
) == 0) {
921 isl_union_set
*domain
;
923 domain
= isl_schedule_node_get_universe_domain(node
);
924 return isl_union_map_from_domain(domain
);
927 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
928 return isl_union_map_from_multi_union_pw_aff(mupa
);
931 /* Make sure that that spaces of "node" and "mv" are the same.
932 * Return -1 on error, reporting the error to the user.
934 static int check_space_multi_val(__isl_keep isl_schedule_node
*node
,
935 __isl_keep isl_multi_val
*mv
)
937 isl_space
*node_space
, *mv_space
;
940 node_space
= isl_schedule_node_band_get_space(node
);
941 mv_space
= isl_multi_val_get_space(mv
);
942 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
943 mv_space
, isl_dim_set
);
944 isl_space_free(mv_space
);
945 isl_space_free(node_space
);
949 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
950 "spaces don't match", return -1);
955 /* Multiply the partial schedule of the band node "node"
956 * with the factors in "mv".
958 __isl_give isl_schedule_node
*isl_schedule_node_band_scale(
959 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
961 isl_schedule_tree
*tree
;
965 if (check_space_multi_val(node
, mv
) < 0)
968 tree
= isl_schedule_node_get_tree(node
);
969 tree
= isl_schedule_tree_band_scale(tree
, mv
);
970 return isl_schedule_node_graft_tree(node
, tree
);
972 isl_multi_val_free(mv
);
973 isl_schedule_node_free(node
);
977 /* Divide the partial schedule of the band node "node"
978 * by the factors in "mv".
980 __isl_give isl_schedule_node
*isl_schedule_node_band_scale_down(
981 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
983 isl_schedule_tree
*tree
;
987 if (check_space_multi_val(node
, mv
) < 0)
990 tree
= isl_schedule_node_get_tree(node
);
991 tree
= isl_schedule_tree_band_scale_down(tree
, mv
);
992 return isl_schedule_node_graft_tree(node
, tree
);
994 isl_multi_val_free(mv
);
995 isl_schedule_node_free(node
);
999 /* Tile "node" with tile sizes "sizes".
1001 * The current node is replaced by two nested nodes corresponding
1002 * to the tile dimensions and the point dimensions.
1004 * Return a pointer to the outer (tile) node.
1006 * If the scale tile loops option is set, then the tile loops
1007 * are scaled by the tile sizes. If the shift point loops option is set,
1008 * then the point loops are shifted to start at zero.
1009 * In particular, these options affect the tile and point loop schedules
1012 * scale shift original tile point
1014 * 0 0 i floor(i/s) i
1015 * 1 0 i s * floor(i/s) i
1016 * 0 1 i floor(i/s) i - s * floor(i/s)
1017 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1019 __isl_give isl_schedule_node
*isl_schedule_node_band_tile(
1020 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*sizes
)
1022 isl_schedule_tree
*tree
;
1024 if (!node
|| !sizes
)
1027 if (check_space_multi_val(node
, sizes
) < 0)
1030 tree
= isl_schedule_node_get_tree(node
);
1031 tree
= isl_schedule_tree_band_tile(tree
, sizes
);
1032 return isl_schedule_node_graft_tree(node
, tree
);
1034 isl_multi_val_free(sizes
);
1035 isl_schedule_node_free(node
);
1039 /* Move the band node "node" down to all the leaves in the subtree
1041 * Return a pointer to the node in the resulting tree that is in the same
1042 * position as the node pointed to by "node" in the original tree.
1044 * If the node only has a leaf child, then nothing needs to be done.
1045 * Otherwise, the child of the node is removed and the result is
1046 * appended to all the leaves in the subtree rooted at the original child.
1047 * The original node is then replaced by the result of this operation.
1049 __isl_give isl_schedule_node
*isl_schedule_node_band_sink(
1050 __isl_take isl_schedule_node
*node
)
1052 enum isl_schedule_node_type type
;
1053 isl_schedule_tree
*tree
, *child
;
1058 type
= isl_schedule_node_get_type(node
);
1059 if (type
!= isl_schedule_node_band
)
1060 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1061 "not a band node", isl_schedule_node_free(node
));
1062 if (isl_schedule_tree_n_children(node
->tree
) == 0)
1065 tree
= isl_schedule_node_get_tree(node
);
1066 child
= isl_schedule_tree_get_child(tree
, 0);
1067 tree
= isl_schedule_tree_reset_children(tree
);
1068 tree
= isl_schedule_tree_append_to_leaves(child
, tree
);
1070 return isl_schedule_node_graft_tree(node
, tree
);
1073 /* Split "node" into two nested band nodes, one with the first "pos"
1074 * dimensions and one with the remaining dimensions.
1075 * The schedules of the two band nodes live in anonymous spaces.
1077 __isl_give isl_schedule_node
*isl_schedule_node_band_split(
1078 __isl_take isl_schedule_node
*node
, int pos
)
1080 isl_schedule_tree
*tree
;
1082 tree
= isl_schedule_node_get_tree(node
);
1083 tree
= isl_schedule_tree_band_split(tree
, pos
);
1084 return isl_schedule_node_graft_tree(node
, tree
);
1087 /* Return the domain of the domain node "node".
1089 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
1090 __isl_keep isl_schedule_node
*node
)
1095 return isl_schedule_tree_domain_get_domain(node
->tree
);
1098 /* Return the filter of the filter node "node".
1100 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
1101 __isl_keep isl_schedule_node
*node
)
1106 return isl_schedule_tree_filter_get_filter(node
->tree
);
1109 /* Replace the filter of filter node "node" by "filter".
1111 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
1112 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
1114 isl_schedule_tree
*tree
;
1116 if (!node
|| !filter
)
1119 tree
= isl_schedule_tree_copy(node
->tree
);
1120 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
1121 return isl_schedule_node_graft_tree(node
, tree
);
1123 isl_schedule_node_free(node
);
1124 isl_union_set_free(filter
);
1128 /* Update the ancestors of "node" to point to the tree that "node"
1130 * That is, replace the child in the original parent that corresponds
1131 * to the current tree position by node->tree and continue updating
1132 * the ancestors in the same way until the root is reached.
1134 * If "node" originally points to a leaf of the schedule tree, then make sure
1135 * that in the end it points to a leaf in the updated schedule tree.
1137 static __isl_give isl_schedule_node
*update_ancestors(
1138 __isl_take isl_schedule_node
*node
)
1143 isl_schedule_tree
*tree
;
1145 node
= isl_schedule_node_cow(node
);
1149 ctx
= isl_schedule_node_get_ctx(node
);
1150 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1151 tree
= isl_schedule_tree_copy(node
->tree
);
1153 for (i
= n
- 1; i
>= 0; --i
) {
1154 isl_schedule_tree
*parent
;
1156 parent
= isl_schedule_tree_list_get_schedule_tree(
1157 node
->ancestors
, i
);
1158 parent
= isl_schedule_tree_replace_child(parent
,
1159 node
->child_pos
[i
], tree
);
1160 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
1161 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
1166 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
1167 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
1169 isl_schedule_tree_free(node
->tree
);
1170 node
->tree
= isl_schedule_node_get_leaf(node
);
1173 if (!node
->schedule
|| !node
->ancestors
)
1174 return isl_schedule_node_free(node
);
1179 /* Replace the subtree that "pos" points to by "tree", updating
1180 * the ancestors to maintain a consistent state.
1182 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
1183 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
1187 if (pos
->tree
== tree
) {
1188 isl_schedule_tree_free(tree
);
1192 pos
= isl_schedule_node_cow(pos
);
1196 isl_schedule_tree_free(pos
->tree
);
1199 return update_ancestors(pos
);
1201 isl_schedule_node_free(pos
);
1202 isl_schedule_tree_free(tree
);
1206 /* Make sure we can insert a node between "node" and its parent.
1207 * Return -1 on error, reporting the reason why we cannot insert a node.
1209 static int check_insert(__isl_keep isl_schedule_node
*node
)
1212 enum isl_schedule_node_type type
;
1214 has_parent
= isl_schedule_node_has_parent(node
);
1218 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1219 "cannot insert node outside of root", return -1);
1221 type
= isl_schedule_node_get_parent_type(node
);
1222 if (type
== isl_schedule_node_error
)
1224 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
1225 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1226 "cannot insert node between set or sequence node "
1227 "and its filter children", return -1);
1232 /* Insert a band node with partial schedule "mupa" between "node" and
1234 * Return a pointer to the new band node.
1236 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
1237 __isl_take isl_schedule_node
*node
,
1238 __isl_take isl_multi_union_pw_aff
*mupa
)
1240 isl_schedule_band
*band
;
1241 isl_schedule_tree
*tree
;
1243 if (check_insert(node
) < 0)
1244 node
= isl_schedule_node_free(node
);
1246 tree
= isl_schedule_node_get_tree(node
);
1247 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
1248 tree
= isl_schedule_tree_insert_band(tree
, band
);
1249 node
= isl_schedule_node_graft_tree(node
, tree
);
1254 /* Insert a filter node with filter "filter" between "node" and its parent.
1255 * Return a pointer to the new filter node.
1257 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
1258 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
1260 isl_schedule_tree
*tree
;
1262 if (check_insert(node
) < 0)
1263 node
= isl_schedule_node_free(node
);
1265 tree
= isl_schedule_node_get_tree(node
);
1266 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
1267 node
= isl_schedule_node_graft_tree(node
, tree
);
1272 /* Attach the current subtree of "node" to a sequence of filter tree nodes
1273 * with filters described by "filters", attach this sequence
1274 * of filter tree nodes as children to a new tree of type "type" and
1275 * replace the original subtree of "node" by this new tree.
1277 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
1278 __isl_take isl_schedule_node
*node
,
1279 enum isl_schedule_node_type type
,
1280 __isl_take isl_union_set_list
*filters
)
1284 isl_schedule_tree
*tree
;
1285 isl_schedule_tree_list
*list
;
1287 if (check_insert(node
) < 0)
1288 node
= isl_schedule_node_free(node
);
1290 if (!node
|| !filters
)
1293 ctx
= isl_schedule_node_get_ctx(node
);
1294 n
= isl_union_set_list_n_union_set(filters
);
1295 list
= isl_schedule_tree_list_alloc(ctx
, n
);
1296 for (i
= 0; i
< n
; ++i
) {
1297 isl_schedule_tree
*tree
;
1298 isl_union_set
*filter
;
1300 tree
= isl_schedule_node_get_tree(node
);
1301 filter
= isl_union_set_list_get_union_set(filters
, i
);
1302 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
1303 list
= isl_schedule_tree_list_add(list
, tree
);
1305 tree
= isl_schedule_tree_from_children(type
, list
);
1306 node
= isl_schedule_node_graft_tree(node
, tree
);
1308 isl_union_set_list_free(filters
);
1311 isl_union_set_list_free(filters
);
1312 isl_schedule_node_free(node
);
1316 /* Insert a sequence node with child filters "filters" between "node" and
1317 * its parent. That is, the tree that "node" points to is attached
1318 * to each of the child nodes of the filter nodes.
1319 * Return a pointer to the new sequence node.
1321 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
1322 __isl_take isl_schedule_node
*node
,
1323 __isl_take isl_union_set_list
*filters
)
1325 return isl_schedule_node_insert_children(node
,
1326 isl_schedule_node_sequence
, filters
);
1329 /* Insert a set node with child filters "filters" between "node" and
1330 * its parent. That is, the tree that "node" points to is attached
1331 * to each of the child nodes of the filter nodes.
1332 * Return a pointer to the new set node.
1334 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
1335 __isl_take isl_schedule_node
*node
,
1336 __isl_take isl_union_set_list
*filters
)
1338 return isl_schedule_node_insert_children(node
,
1339 isl_schedule_node_set
, filters
);
1342 /* Print "node" to "p".
1344 __isl_give isl_printer
*isl_printer_print_schedule_node(
1345 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
1348 return isl_printer_free(p
);
1349 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
,
1350 isl_schedule_tree_list_n_schedule_tree(node
->ancestors
),
1354 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
1357 isl_printer
*printer
;
1362 ctx
= isl_schedule_node_get_ctx(node
);
1363 printer
= isl_printer_to_file(ctx
, stderr
);
1364 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
1365 printer
= isl_printer_print_schedule_node(printer
, node
);
1367 isl_printer_free(printer
);