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 /* Does "node" have a parent?
529 * That is, does it point to any node of the schedule other than the root?
531 int isl_schedule_node_has_parent(__isl_keep isl_schedule_node
*node
)
535 if (!node
->ancestors
)
538 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) != 0;
541 /* Return the position of "node" among the children of its parent.
543 int isl_schedule_node_get_child_position(__isl_keep isl_schedule_node
*node
)
550 has_parent
= isl_schedule_node_has_parent(node
);
554 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
555 "node has no parent", return -1);
557 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
558 return node
->child_pos
[n
- 1];
561 /* Does the parent (if any) of "node" have any children with a smaller child
562 * position than this one?
564 int isl_schedule_node_has_previous_sibling(__isl_keep isl_schedule_node
*node
)
571 has_parent
= isl_schedule_node_has_parent(node
);
572 if (has_parent
< 0 || !has_parent
)
575 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
577 return node
->child_pos
[n
- 1] > 0;
580 /* Does the parent (if any) of "node" have any children with a greater child
581 * position than this one?
583 int isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node
*node
)
587 isl_schedule_tree
*tree
;
591 has_parent
= isl_schedule_node_has_parent(node
);
592 if (has_parent
< 0 || !has_parent
)
595 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
596 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
599 n_child
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
600 isl_schedule_tree_free(tree
);
602 return node
->child_pos
[n
- 1] + 1 < n_child
;
605 /* Does "node" have any children?
607 * Any node other than the leaf nodes is considered to have at least
608 * one child, even if the corresponding isl_schedule_tree does not
611 int isl_schedule_node_has_children(__isl_keep isl_schedule_node
*node
)
615 return !isl_schedule_tree_is_leaf(node
->tree
);
618 /* Return the number of children of "node"?
620 * Any node other than the leaf nodes is considered to have at least
621 * one child, even if the corresponding isl_schedule_tree does not
622 * have any children. That is, the number of children of "node" is
623 * only zero if its tree is the explicit empty tree. Otherwise,
624 * if the isl_schedule_tree has any children, then it is equal
625 * to the number of children of "node". If it has zero children,
626 * then "node" still has a leaf node as child.
628 int isl_schedule_node_n_children(__isl_keep isl_schedule_node
*node
)
635 if (isl_schedule_tree_is_leaf(node
->tree
))
638 n
= isl_schedule_tree_n_children(node
->tree
);
645 /* Move the "node" pointer to the parent of the node it currently points to.
647 __isl_give isl_schedule_node
*isl_schedule_node_parent(
648 __isl_take isl_schedule_node
*node
)
651 isl_schedule_tree
*tree
;
653 node
= isl_schedule_node_cow(node
);
656 if (!isl_schedule_node_has_parent(node
))
657 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
658 "node has no parent",
659 return isl_schedule_node_free(node
));
660 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
661 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
662 isl_schedule_tree_free(node
->tree
);
664 node
->ancestors
= isl_schedule_tree_list_drop(node
->ancestors
,
666 if (!node
->ancestors
|| !node
->tree
)
667 return isl_schedule_node_free(node
);
672 /* Move the "node" pointer to the child at position "pos" of the node
673 * it currently points to.
675 __isl_give isl_schedule_node
*isl_schedule_node_child(
676 __isl_take isl_schedule_node
*node
, int pos
)
680 isl_schedule_tree
*tree
;
683 node
= isl_schedule_node_cow(node
);
686 if (!isl_schedule_node_has_children(node
))
687 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
688 "node has no children",
689 return isl_schedule_node_free(node
));
691 ctx
= isl_schedule_node_get_ctx(node
);
692 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
693 child_pos
= isl_realloc_array(ctx
, node
->child_pos
, int, n
+ 1);
695 return isl_schedule_node_free(node
);
696 node
->child_pos
= child_pos
;
697 node
->child_pos
[n
] = pos
;
699 node
->ancestors
= isl_schedule_tree_list_add(node
->ancestors
,
700 isl_schedule_tree_copy(node
->tree
));
702 if (isl_schedule_tree_has_children(tree
))
703 tree
= isl_schedule_tree_get_child(tree
, pos
);
705 tree
= isl_schedule_node_get_leaf(node
);
706 isl_schedule_tree_free(node
->tree
);
709 if (!node
->tree
|| !node
->ancestors
)
710 return isl_schedule_node_free(node
);
715 /* Move the "node" pointer to the first child of the node
716 * it currently points to.
718 __isl_give isl_schedule_node
*isl_schedule_node_first_child(
719 __isl_take isl_schedule_node
*node
)
721 return isl_schedule_node_child(node
, 0);
724 /* Move the "node" pointer to the child of this node's parent in
725 * the previous child position.
727 __isl_give isl_schedule_node
*isl_schedule_node_previous_sibling(
728 __isl_take isl_schedule_node
*node
)
731 isl_schedule_tree
*parent
, *tree
;
733 node
= isl_schedule_node_cow(node
);
736 if (!isl_schedule_node_has_previous_sibling(node
))
737 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
738 "node has no previous sibling",
739 return isl_schedule_node_free(node
));
741 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
742 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
745 return isl_schedule_node_free(node
);
746 node
->child_pos
[n
- 1]--;
747 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
748 node
->child_pos
[n
- 1]);
749 isl_schedule_tree_free(parent
);
751 return isl_schedule_node_free(node
);
752 isl_schedule_tree_free(node
->tree
);
758 /* Move the "node" pointer to the child of this node's parent in
759 * the next child position.
761 __isl_give isl_schedule_node
*isl_schedule_node_next_sibling(
762 __isl_take isl_schedule_node
*node
)
765 isl_schedule_tree
*parent
, *tree
;
767 node
= isl_schedule_node_cow(node
);
770 if (!isl_schedule_node_has_next_sibling(node
))
771 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
772 "node has no next sibling",
773 return isl_schedule_node_free(node
));
775 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
776 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
779 return isl_schedule_node_free(node
);
780 node
->child_pos
[n
- 1]++;
781 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
782 node
->child_pos
[n
- 1]);
783 isl_schedule_tree_free(parent
);
785 return isl_schedule_node_free(node
);
786 isl_schedule_tree_free(node
->tree
);
792 /* Return a copy to the child at position "pos" of "node".
794 __isl_give isl_schedule_node
*isl_schedule_node_get_child(
795 __isl_keep isl_schedule_node
*node
, int pos
)
797 return isl_schedule_node_child(isl_schedule_node_copy(node
), pos
);
800 /* Return the number of members in the given band node.
802 unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node
*node
)
804 return node
? isl_schedule_tree_band_n_member(node
->tree
) : 0;
807 /* Is the band member at position "pos" of the band node "node"
810 int isl_schedule_node_band_member_get_coincident(
811 __isl_keep isl_schedule_node
*node
, int pos
)
815 return isl_schedule_tree_band_member_get_coincident(node
->tree
, pos
);
818 /* Mark the band member at position "pos" the band node "node"
819 * as being coincident or not according to "coincident".
821 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_coincident(
822 __isl_take isl_schedule_node
*node
, int pos
, int coincident
)
825 isl_schedule_tree
*tree
;
829 c
= isl_schedule_node_band_member_get_coincident(node
, pos
);
833 tree
= isl_schedule_tree_copy(node
->tree
);
834 tree
= isl_schedule_tree_band_member_set_coincident(tree
, pos
,
836 node
= isl_schedule_node_graft_tree(node
, tree
);
841 /* Is the band node "node" marked permutable?
843 int isl_schedule_node_band_get_permutable(__isl_keep isl_schedule_node
*node
)
848 return isl_schedule_tree_band_get_permutable(node
->tree
);
851 /* Mark the band node "node" permutable or not according to "permutable"?
853 __isl_give isl_schedule_node
*isl_schedule_node_band_set_permutable(
854 __isl_take isl_schedule_node
*node
, int permutable
)
856 isl_schedule_tree
*tree
;
860 if (isl_schedule_node_band_get_permutable(node
) == permutable
)
863 tree
= isl_schedule_tree_copy(node
->tree
);
864 tree
= isl_schedule_tree_band_set_permutable(tree
, permutable
);
865 node
= isl_schedule_node_graft_tree(node
, tree
);
870 /* Return the schedule of the band node in isolation.
872 __isl_give isl_multi_union_pw_aff
*isl_schedule_node_band_get_partial_schedule(
873 __isl_keep isl_schedule_node
*node
)
878 return isl_schedule_tree_band_get_partial_schedule(node
->tree
);
881 /* Return the schedule of the band node in isolation in the form of
884 * If the band does not have any members, then we construct a universe map
885 * with the universe of the domain elements reaching the node as domain.
886 * Otherwise, we extract an isl_multi_union_pw_aff representation and
887 * convert that to an isl_union_map.
889 __isl_give isl_union_map
*isl_schedule_node_band_get_partial_schedule_union_map(
890 __isl_keep isl_schedule_node
*node
)
892 isl_multi_union_pw_aff
*mupa
;
897 if (isl_schedule_node_get_type(node
) != isl_schedule_node_band
)
898 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
899 "not a band node", return NULL
);
900 if (isl_schedule_node_band_n_member(node
) == 0) {
901 isl_union_set
*domain
;
903 domain
= isl_schedule_node_get_universe_domain(node
);
904 return isl_union_map_from_domain(domain
);
907 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
908 return isl_union_map_from_multi_union_pw_aff(mupa
);
911 /* Return the domain of the domain node "node".
913 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
914 __isl_keep isl_schedule_node
*node
)
919 return isl_schedule_tree_domain_get_domain(node
->tree
);
922 /* Return the filter of the filter node "node".
924 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
925 __isl_keep isl_schedule_node
*node
)
930 return isl_schedule_tree_filter_get_filter(node
->tree
);
933 /* Replace the filter of filter node "node" by "filter".
935 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
936 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
938 isl_schedule_tree
*tree
;
940 if (!node
|| !filter
)
943 tree
= isl_schedule_tree_copy(node
->tree
);
944 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
945 return isl_schedule_node_graft_tree(node
, tree
);
947 isl_schedule_node_free(node
);
948 isl_union_set_free(filter
);
952 /* Update the ancestors of "node" to point to the tree that "node"
954 * That is, replace the child in the original parent that corresponds
955 * to the current tree position by node->tree and continue updating
956 * the ancestors in the same way until the root is reached.
958 * If "node" originally points to a leaf of the schedule tree, then make sure
959 * that in the end it points to a leaf in the updated schedule tree.
961 static __isl_give isl_schedule_node
*update_ancestors(
962 __isl_take isl_schedule_node
*node
)
967 isl_schedule_tree
*tree
;
969 node
= isl_schedule_node_cow(node
);
973 ctx
= isl_schedule_node_get_ctx(node
);
974 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
975 tree
= isl_schedule_tree_copy(node
->tree
);
977 for (i
= n
- 1; i
>= 0; --i
) {
978 isl_schedule_tree
*parent
;
980 parent
= isl_schedule_tree_list_get_schedule_tree(
982 parent
= isl_schedule_tree_replace_child(parent
,
983 node
->child_pos
[i
], tree
);
984 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
985 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
990 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
991 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
993 isl_schedule_tree_free(node
->tree
);
994 node
->tree
= isl_schedule_node_get_leaf(node
);
997 if (!node
->schedule
|| !node
->ancestors
)
998 return isl_schedule_node_free(node
);
1003 /* Replace the subtree that "pos" points to by "tree", updating
1004 * the ancestors to maintain a consistent state.
1006 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
1007 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
1011 if (pos
->tree
== tree
) {
1012 isl_schedule_tree_free(tree
);
1016 pos
= isl_schedule_node_cow(pos
);
1020 isl_schedule_tree_free(pos
->tree
);
1023 return update_ancestors(pos
);
1025 isl_schedule_node_free(pos
);
1026 isl_schedule_tree_free(tree
);
1030 /* Make sure we can insert a node between "node" and its parent.
1031 * Return -1 on error, reporting the reason why we cannot insert a node.
1033 static int check_insert(__isl_keep isl_schedule_node
*node
)
1036 enum isl_schedule_node_type type
;
1038 has_parent
= isl_schedule_node_has_parent(node
);
1042 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1043 "cannot insert node outside of root", return -1);
1045 type
= isl_schedule_node_get_parent_type(node
);
1046 if (type
== isl_schedule_node_error
)
1048 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
1049 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1050 "cannot insert node between set or sequence node "
1051 "and its filter children", return -1);
1056 /* Insert a band node with partial schedule "mupa" between "node" and
1058 * Return a pointer to the new band node.
1060 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
1061 __isl_take isl_schedule_node
*node
,
1062 __isl_take isl_multi_union_pw_aff
*mupa
)
1064 isl_schedule_band
*band
;
1065 isl_schedule_tree
*tree
;
1067 if (check_insert(node
) < 0)
1068 node
= isl_schedule_node_free(node
);
1070 tree
= isl_schedule_node_get_tree(node
);
1071 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
1072 tree
= isl_schedule_tree_insert_band(tree
, band
);
1073 node
= isl_schedule_node_graft_tree(node
, tree
);
1078 /* Insert a filter node with filter "filter" between "node" and its parent.
1079 * Return a pointer to the new filter node.
1081 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
1082 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
1084 isl_schedule_tree
*tree
;
1086 if (check_insert(node
) < 0)
1087 node
= isl_schedule_node_free(node
);
1089 tree
= isl_schedule_node_get_tree(node
);
1090 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
1091 node
= isl_schedule_node_graft_tree(node
, tree
);
1096 /* Attach the current subtree of "node" to a sequence of filter tree nodes
1097 * with filters described by "filters", attach this sequence
1098 * of filter tree nodes as children to a new tree of type "type" and
1099 * replace the original subtree of "node" by this new tree.
1101 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
1102 __isl_take isl_schedule_node
*node
,
1103 enum isl_schedule_node_type type
,
1104 __isl_take isl_union_set_list
*filters
)
1108 isl_schedule_tree
*tree
;
1109 isl_schedule_tree_list
*list
;
1111 if (check_insert(node
) < 0)
1112 node
= isl_schedule_node_free(node
);
1114 if (!node
|| !filters
)
1117 ctx
= isl_schedule_node_get_ctx(node
);
1118 n
= isl_union_set_list_n_union_set(filters
);
1119 list
= isl_schedule_tree_list_alloc(ctx
, n
);
1120 for (i
= 0; i
< n
; ++i
) {
1121 isl_schedule_tree
*tree
;
1122 isl_union_set
*filter
;
1124 tree
= isl_schedule_node_get_tree(node
);
1125 filter
= isl_union_set_list_get_union_set(filters
, i
);
1126 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
1127 list
= isl_schedule_tree_list_add(list
, tree
);
1129 tree
= isl_schedule_tree_from_children(type
, list
);
1130 node
= isl_schedule_node_graft_tree(node
, tree
);
1132 isl_union_set_list_free(filters
);
1135 isl_union_set_list_free(filters
);
1136 isl_schedule_node_free(node
);
1140 /* Insert a sequence node with child filters "filters" between "node" and
1141 * its parent. That is, the tree that "node" points to is attached
1142 * to each of the child nodes of the filter nodes.
1143 * Return a pointer to the new sequence node.
1145 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
1146 __isl_take isl_schedule_node
*node
,
1147 __isl_take isl_union_set_list
*filters
)
1149 return isl_schedule_node_insert_children(node
,
1150 isl_schedule_node_sequence
, filters
);
1153 /* Insert a set node with child filters "filters" between "node" and
1154 * its parent. That is, the tree that "node" points to is attached
1155 * to each of the child nodes of the filter nodes.
1156 * Return a pointer to the new set node.
1158 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
1159 __isl_take isl_schedule_node
*node
,
1160 __isl_take isl_union_set_list
*filters
)
1162 return isl_schedule_node_insert_children(node
,
1163 isl_schedule_node_set
, filters
);
1166 /* Print "node" to "p".
1168 __isl_give isl_printer
*isl_printer_print_schedule_node(
1169 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
1172 return isl_printer_free(p
);
1173 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
,
1174 isl_schedule_tree_list_n_schedule_tree(node
->ancestors
),
1178 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
1181 isl_printer
*printer
;
1186 ctx
= isl_schedule_node_get_ctx(node
);
1187 printer
= isl_printer_to_file(ctx
, stderr
);
1188 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
1189 printer
= isl_printer_print_schedule_node(printer
, node
);
1191 isl_printer_free(printer
);