2 * Copyright 2013-2014 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
9 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
10 * B.P. 105 - 78153 Le Chesnay, France
14 #include <isl_schedule_band.h>
15 #include <isl_schedule_private.h>
16 #include <isl_schedule_node_private.h>
18 /* Create a new schedule node in the given schedule, point at the given
19 * tree with given ancestors and child positions.
20 * "child_pos" may be NULL if there are no ancestors.
22 __isl_give isl_schedule_node
*isl_schedule_node_alloc(
23 __isl_take isl_schedule
*schedule
, __isl_take isl_schedule_tree
*tree
,
24 __isl_take isl_schedule_tree_list
*ancestors
, int *child_pos
)
27 isl_schedule_node
*node
;
30 if (!schedule
|| !tree
|| !ancestors
)
32 n
= isl_schedule_tree_list_n_schedule_tree(ancestors
);
33 if (n
> 0 && !child_pos
)
35 ctx
= isl_schedule_get_ctx(schedule
);
36 node
= isl_calloc_type(ctx
, isl_schedule_node
);
40 node
->schedule
= schedule
;
42 node
->ancestors
= ancestors
;
43 node
->child_pos
= isl_alloc_array(ctx
, int, n
);
44 if (n
&& !node
->child_pos
)
45 return isl_schedule_node_free(node
);
46 for (i
= 0; i
< n
; ++i
)
47 node
->child_pos
[i
] = child_pos
[i
];
51 isl_schedule_free(schedule
);
52 isl_schedule_tree_free(tree
);
53 isl_schedule_tree_list_free(ancestors
);
57 /* Return a pointer to the root of a schedule tree with as single
58 * node a domain node with the given domain.
60 __isl_give isl_schedule_node
*isl_schedule_node_from_domain(
61 __isl_take isl_union_set
*domain
)
63 isl_schedule
*schedule
;
64 isl_schedule_node
*node
;
66 schedule
= isl_schedule_from_domain(domain
);
67 node
= isl_schedule_get_root(schedule
);
68 isl_schedule_free(schedule
);
73 /* Return the isl_ctx to which "node" belongs.
75 isl_ctx
*isl_schedule_node_get_ctx(__isl_keep isl_schedule_node
*node
)
77 return node
? isl_schedule_get_ctx(node
->schedule
) : NULL
;
80 /* Return a pointer to the leaf of the schedule into which "node" points.
82 * Even though these leaves are not reference counted, we still
83 * indicate that this function does not return a copy.
85 __isl_keep isl_schedule_tree
*isl_schedule_node_peek_leaf(
86 __isl_keep isl_schedule_node
*node
)
88 return node
? isl_schedule_peek_leaf(node
->schedule
) : NULL
;
91 /* Return a pointer to the leaf of the schedule into which "node" points.
93 * Even though these leaves are not reference counted, we still
94 * return a "copy" of the leaf here such that it can still be "freed"
97 __isl_give isl_schedule_tree
*isl_schedule_node_get_leaf(
98 __isl_keep isl_schedule_node
*node
)
100 return isl_schedule_tree_copy(isl_schedule_node_peek_leaf(node
));
103 /* Return the type of the node or isl_schedule_node_error on error.
105 enum isl_schedule_node_type
isl_schedule_node_get_type(
106 __isl_keep isl_schedule_node
*node
)
108 return node
? isl_schedule_tree_get_type(node
->tree
)
109 : isl_schedule_node_error
;
112 /* Return the type of the parent of "node" or isl_schedule_node_error on error.
114 enum isl_schedule_node_type
isl_schedule_node_get_parent_type(
115 __isl_keep isl_schedule_node
*node
)
119 isl_schedule_tree
*parent
;
120 enum isl_schedule_node_type type
;
123 return isl_schedule_node_error
;
124 has_parent
= isl_schedule_node_has_parent(node
);
126 return isl_schedule_node_error
;
128 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
129 "node has no parent", return isl_schedule_node_error
);
131 pos
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) - 1;
132 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, pos
);
133 type
= isl_schedule_tree_get_type(parent
);
134 isl_schedule_tree_free(parent
);
139 /* Return a copy of the subtree that this node points to.
141 __isl_give isl_schedule_tree
*isl_schedule_node_get_tree(
142 __isl_keep isl_schedule_node
*node
)
147 return isl_schedule_tree_copy(node
->tree
);
150 /* Return a copy of the schedule into which "node" points.
152 __isl_give isl_schedule
*isl_schedule_node_get_schedule(
153 __isl_keep isl_schedule_node
*node
)
157 return isl_schedule_copy(node
->schedule
);
160 /* Return a fresh copy of "node".
162 __isl_take isl_schedule_node
*isl_schedule_node_dup(
163 __isl_keep isl_schedule_node
*node
)
168 return isl_schedule_node_alloc(isl_schedule_copy(node
->schedule
),
169 isl_schedule_tree_copy(node
->tree
),
170 isl_schedule_tree_list_copy(node
->ancestors
),
174 /* Return an isl_schedule_node that is equal to "node" and that has only
175 * a single reference.
177 __isl_give isl_schedule_node
*isl_schedule_node_cow(
178 __isl_take isl_schedule_node
*node
)
186 return isl_schedule_node_dup(node
);
189 /* Return a new reference to "node".
191 __isl_give isl_schedule_node
*isl_schedule_node_copy(
192 __isl_keep isl_schedule_node
*node
)
201 /* Free "node" and return NULL.
203 * Since the node may point to a leaf of its schedule, which
204 * point to a field inside the schedule, we need to make sure
205 * we free the tree before freeing the schedule.
207 __isl_null isl_schedule_node
*isl_schedule_node_free(
208 __isl_take isl_schedule_node
*node
)
215 isl_schedule_tree_list_free(node
->ancestors
);
216 free(node
->child_pos
);
217 isl_schedule_tree_free(node
->tree
);
218 isl_schedule_free(node
->schedule
);
224 /* Do "node1" and "node2" point to the same position in the same
227 int isl_schedule_node_is_equal(__isl_keep isl_schedule_node
*node1
,
228 __isl_keep isl_schedule_node
*node2
)
232 if (!node1
|| !node2
)
236 if (node1
->schedule
!= node2
->schedule
)
239 n1
= isl_schedule_node_get_tree_depth(node1
);
240 n2
= isl_schedule_node_get_tree_depth(node2
);
243 for (i
= 0; i
< n1
; ++i
)
244 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
250 /* Return the number of outer schedule dimensions of "node"
251 * in its schedule tree.
253 * Return -1 on error.
255 int isl_schedule_node_get_schedule_depth(__isl_keep isl_schedule_node
*node
)
263 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
264 for (i
= n
- 1; i
>= 0; --i
) {
265 isl_schedule_tree
*tree
;
267 tree
= isl_schedule_tree_list_get_schedule_tree(
271 if (tree
->type
== isl_schedule_node_band
)
272 depth
+= isl_schedule_tree_band_n_member(tree
);
273 isl_schedule_tree_free(tree
);
279 /* Internal data structure for
280 * isl_schedule_node_get_prefix_schedule_union_pw_multi_aff
282 * "initialized" is set if the filter field has been initialized.
283 * If "universe_domain" is not set, then the collected filter is intersected
284 * with the the domain of the root domain node.
285 * "universe_filter" is set if we are only collecting the universes of filters
286 * "collect_prefix" is set if we are collecting prefixes.
287 * "filter" collects all outer filters and is NULL until "initialized" is set.
288 * "prefix" collects all outer band partial schedules (if "collect_prefix"
289 * is set). If it is used, then it is initialized by the caller
290 * of collect_filter_prefix to a zero-dimensional function.
292 struct isl_schedule_node_get_filter_prefix_data
{
297 isl_union_set
*filter
;
298 isl_multi_union_pw_aff
*prefix
;
301 /* Update "data" based on the tree node "tree" in case "data" has
302 * not been initialized yet.
304 * Return 0 on success and -1 on error.
306 * If "tree" is a filter, then we set data->filter to this filter
308 * If "tree" is a domain, then this means we have reached the root
309 * of the schedule tree without being able to extract any information.
310 * We therefore initialize data->filter to the universe of the domain,
311 * or the domain itself if data->universe_domain is not set.
312 * If "tree" is a band with at least one member, then we set data->filter
313 * to the universe of the schedule domain and replace the zero-dimensional
314 * data->prefix by the band schedule (if data->collect_prefix is set).
316 static int collect_filter_prefix_init(__isl_keep isl_schedule_tree
*tree
,
317 struct isl_schedule_node_get_filter_prefix_data
*data
)
319 enum isl_schedule_node_type type
;
320 isl_multi_union_pw_aff
*mupa
;
321 isl_union_set
*filter
;
323 type
= isl_schedule_tree_get_type(tree
);
325 case isl_schedule_node_error
:
327 case isl_schedule_node_context
:
328 case isl_schedule_node_leaf
:
329 case isl_schedule_node_sequence
:
330 case isl_schedule_node_set
:
332 case isl_schedule_node_domain
:
333 filter
= isl_schedule_tree_domain_get_domain(tree
);
334 if (data
->universe_domain
)
335 filter
= isl_union_set_universe(filter
);
336 data
->filter
= filter
;
338 case isl_schedule_node_band
:
339 if (isl_schedule_tree_band_n_member(tree
) == 0)
341 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
342 if (data
->collect_prefix
) {
343 isl_multi_union_pw_aff_free(data
->prefix
);
344 mupa
= isl_multi_union_pw_aff_reset_tuple_id(mupa
,
346 data
->prefix
= isl_multi_union_pw_aff_copy(mupa
);
348 filter
= isl_multi_union_pw_aff_domain(mupa
);
349 filter
= isl_union_set_universe(filter
);
350 data
->filter
= filter
;
352 case isl_schedule_node_filter
:
353 filter
= isl_schedule_tree_filter_get_filter(tree
);
354 if (data
->universe_filter
)
355 filter
= isl_union_set_universe(filter
);
356 data
->filter
= filter
;
360 if ((data
->collect_prefix
&& !data
->prefix
) || !data
->filter
)
363 data
->initialized
= 1;
368 /* Update "data" based on the tree node "tree" in case "data" has
369 * already been initialized.
371 * Return 0 on success and -1 on error.
373 * If "tree" is a domain and data->universe_domain is not set, then
374 * intersect data->filter with the domain.
375 * If "tree" is a filter, then we intersect data->filter with this filter
377 * If "tree" is a band with at least one member and data->collect_prefix
378 * is set, then we extend data->prefix with the band schedule.
380 static int collect_filter_prefix_update(__isl_keep isl_schedule_tree
*tree
,
381 struct isl_schedule_node_get_filter_prefix_data
*data
)
383 enum isl_schedule_node_type type
;
384 isl_multi_union_pw_aff
*mupa
;
385 isl_union_set
*filter
;
387 type
= isl_schedule_tree_get_type(tree
);
389 case isl_schedule_node_error
:
391 case isl_schedule_node_context
:
392 case isl_schedule_node_leaf
:
393 case isl_schedule_node_sequence
:
394 case isl_schedule_node_set
:
396 case isl_schedule_node_domain
:
397 if (data
->universe_domain
)
399 filter
= isl_schedule_tree_domain_get_domain(tree
);
400 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
402 case isl_schedule_node_band
:
403 if (isl_schedule_tree_band_n_member(tree
) == 0)
405 if (!data
->collect_prefix
)
407 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
408 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(mupa
,
413 case isl_schedule_node_filter
:
414 filter
= isl_schedule_tree_filter_get_filter(tree
);
415 if (data
->universe_filter
)
416 filter
= isl_union_set_universe(filter
);
417 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
426 /* Collect filter and/or prefix information from the elements
427 * in "list" (which represent the ancestors of a node).
428 * Store the results in "data".
430 * Return 0 on success and -1 on error.
432 * We traverse the list from innermost ancestor (last element)
433 * to outermost ancestor (first element), calling collect_filter_prefix_init
434 * on each node as long as we have not been able to extract any information
435 * yet and collect_filter_prefix_update afterwards.
436 * On successful return, data->initialized will be set since the outermost
437 * ancestor is a domain node, which always results in an initialization.
439 static int collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
440 struct isl_schedule_node_get_filter_prefix_data
*data
)
444 data
->initialized
= 0;
450 n
= isl_schedule_tree_list_n_schedule_tree(list
);
451 for (i
= n
- 1; i
>= 0; --i
) {
452 isl_schedule_tree
*tree
;
455 tree
= isl_schedule_tree_list_get_schedule_tree(list
, i
);
458 if (!data
->initialized
)
459 r
= collect_filter_prefix_init(tree
, data
);
461 r
= collect_filter_prefix_update(tree
, data
);
462 isl_schedule_tree_free(tree
);
470 /* Return the concatenation of the partial schedules of all outer band
471 * nodes of "node" interesected with all outer filters
472 * as an isl_union_pw_multi_aff.
474 * If "node" is pointing at the root of the schedule tree, then
475 * there are no domain elements reaching the current node, so
476 * we return an empty result.
478 * We collect all the filters and partial schedules in collect_filter_prefix.
479 * The partial schedules are collected as an isl_multi_union_pw_aff.
480 * If this isl_multi_union_pw_aff is zero-dimensional, then it does not
481 * contain any domain information, so we construct the isl_union_pw_multi_aff
482 * result as a zero-dimensional function on the collected filter.
483 * Otherwise, we convert the isl_multi_union_pw_aff to
484 * an isl_multi_union_pw_aff and intersect the domain with the filter.
486 __isl_give isl_union_pw_multi_aff
*
487 isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(
488 __isl_keep isl_schedule_node
*node
)
491 isl_union_pw_multi_aff
*prefix
;
492 struct isl_schedule_node_get_filter_prefix_data data
;
497 space
= isl_schedule_get_space(node
->schedule
);
498 if (node
->tree
== node
->schedule
->root
)
499 return isl_union_pw_multi_aff_empty(space
);
501 space
= isl_space_set_from_params(space
);
502 data
.universe_domain
= 1;
503 data
.universe_filter
= 0;
504 data
.collect_prefix
= 1;
505 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
507 if (collect_filter_prefix(node
->ancestors
, &data
) < 0)
508 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
511 isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
) == 0) {
512 isl_multi_union_pw_aff_free(data
.prefix
);
513 prefix
= isl_union_pw_multi_aff_from_domain(data
.filter
);
516 isl_union_pw_multi_aff_from_multi_union_pw_aff(data
.prefix
);
517 prefix
= isl_union_pw_multi_aff_intersect_domain(prefix
,
524 /* Return the concatenation of the partial schedules of all outer band
525 * nodes of "node" interesected with all outer filters
526 * as an isl_union_map.
528 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_union_map(
529 __isl_keep isl_schedule_node
*node
)
531 isl_union_pw_multi_aff
*upma
;
533 upma
= isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(node
);
534 return isl_union_map_from_union_pw_multi_aff(upma
);
537 /* Return the domain elements that reach "node".
539 * If "node" is pointing at the root of the schedule tree, then
540 * there are no domain elements reaching the current node, so
541 * we return an empty result.
543 * Otherwise, we collect all filters reaching the node,
544 * intersected with the root domain in collect_filter_prefix.
546 __isl_give isl_union_set
*isl_schedule_node_get_domain(
547 __isl_keep isl_schedule_node
*node
)
549 struct isl_schedule_node_get_filter_prefix_data data
;
554 if (node
->tree
== node
->schedule
->root
) {
557 space
= isl_schedule_get_space(node
->schedule
);
558 return isl_union_set_empty(space
);
561 data
.universe_domain
= 0;
562 data
.universe_filter
= 0;
563 data
.collect_prefix
= 0;
566 if (collect_filter_prefix(node
->ancestors
, &data
) < 0)
567 data
.filter
= isl_union_set_free(data
.filter
);
572 /* Return the union of universe sets of the domain elements that reach "node".
574 * If "node" is pointing at the root of the schedule tree, then
575 * there are no domain elements reaching the current node, so
576 * we return an empty result.
578 * Otherwise, we collect the universes of all filters reaching the node
579 * in collect_filter_prefix.
581 __isl_give isl_union_set
*isl_schedule_node_get_universe_domain(
582 __isl_keep isl_schedule_node
*node
)
584 struct isl_schedule_node_get_filter_prefix_data data
;
589 if (node
->tree
== node
->schedule
->root
) {
592 space
= isl_schedule_get_space(node
->schedule
);
593 return isl_union_set_empty(space
);
596 data
.universe_domain
= 1;
597 data
.universe_filter
= 1;
598 data
.collect_prefix
= 0;
601 if (collect_filter_prefix(node
->ancestors
, &data
) < 0)
602 data
.filter
= isl_union_set_free(data
.filter
);
607 /* Return the subtree schedule of "node".
609 * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle
610 * trees that do not contain any schedule information, we first
611 * move down to the first relevant descendant and handle leaves ourselves.
613 __isl_give isl_union_map
*isl_schedule_node_get_subtree_schedule_union_map(
614 __isl_keep isl_schedule_node
*node
)
616 isl_schedule_tree
*tree
, *leaf
;
619 tree
= isl_schedule_node_get_tree(node
);
620 leaf
= isl_schedule_node_peek_leaf(node
);
621 tree
= isl_schedule_tree_first_schedule_descendant(tree
, leaf
);
625 isl_union_set
*domain
;
626 domain
= isl_schedule_node_get_universe_domain(node
);
627 isl_schedule_tree_free(tree
);
628 return isl_union_map_from_domain(domain
);
631 umap
= isl_schedule_tree_get_subtree_schedule_union_map(tree
);
632 isl_schedule_tree_free(tree
);
636 /* Return the number of ancestors of "node" in its schedule tree.
638 int isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node
*node
)
642 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
645 /* Does "node" have a parent?
647 * That is, does it point to any node of the schedule other than the root?
649 int isl_schedule_node_has_parent(__isl_keep isl_schedule_node
*node
)
653 if (!node
->ancestors
)
656 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) != 0;
659 /* Return the position of "node" among the children of its parent.
661 int isl_schedule_node_get_child_position(__isl_keep isl_schedule_node
*node
)
668 has_parent
= isl_schedule_node_has_parent(node
);
672 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
673 "node has no parent", return -1);
675 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
676 return node
->child_pos
[n
- 1];
679 /* Does the parent (if any) of "node" have any children with a smaller child
680 * position than this one?
682 int isl_schedule_node_has_previous_sibling(__isl_keep isl_schedule_node
*node
)
689 has_parent
= isl_schedule_node_has_parent(node
);
690 if (has_parent
< 0 || !has_parent
)
693 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
695 return node
->child_pos
[n
- 1] > 0;
698 /* Does the parent (if any) of "node" have any children with a greater child
699 * position than this one?
701 int isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node
*node
)
705 isl_schedule_tree
*tree
;
709 has_parent
= isl_schedule_node_has_parent(node
);
710 if (has_parent
< 0 || !has_parent
)
713 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
714 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
717 n_child
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
718 isl_schedule_tree_free(tree
);
720 return node
->child_pos
[n
- 1] + 1 < n_child
;
723 /* Does "node" have any children?
725 * Any node other than the leaf nodes is considered to have at least
726 * one child, even if the corresponding isl_schedule_tree does not
729 int isl_schedule_node_has_children(__isl_keep isl_schedule_node
*node
)
733 return !isl_schedule_tree_is_leaf(node
->tree
);
736 /* Return the number of children of "node"?
738 * Any node other than the leaf nodes is considered to have at least
739 * one child, even if the corresponding isl_schedule_tree does not
740 * have any children. That is, the number of children of "node" is
741 * only zero if its tree is the explicit empty tree. Otherwise,
742 * if the isl_schedule_tree has any children, then it is equal
743 * to the number of children of "node". If it has zero children,
744 * then "node" still has a leaf node as child.
746 int isl_schedule_node_n_children(__isl_keep isl_schedule_node
*node
)
753 if (isl_schedule_tree_is_leaf(node
->tree
))
756 n
= isl_schedule_tree_n_children(node
->tree
);
763 /* Move the "node" pointer to the ancestor of the given generation
764 * of the node it currently points to, where generation 0 is the node
765 * itself and generation 1 is its parent.
767 __isl_give isl_schedule_node
*isl_schedule_node_ancestor(
768 __isl_take isl_schedule_node
*node
, int generation
)
771 isl_schedule_tree
*tree
;
777 n
= isl_schedule_node_get_tree_depth(node
);
779 return isl_schedule_node_free(node
);
780 if (generation
< 0 || generation
> n
)
781 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
782 "generation out of bounds",
783 return isl_schedule_node_free(node
));
784 node
= isl_schedule_node_cow(node
);
788 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
790 isl_schedule_tree_free(node
->tree
);
792 node
->ancestors
= isl_schedule_tree_list_drop(node
->ancestors
,
793 n
- generation
, generation
);
794 if (!node
->ancestors
|| !node
->tree
)
795 return isl_schedule_node_free(node
);
800 /* Move the "node" pointer to the parent of the node it currently points to.
802 __isl_give isl_schedule_node
*isl_schedule_node_parent(
803 __isl_take isl_schedule_node
*node
)
807 if (!isl_schedule_node_has_parent(node
))
808 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
809 "node has no parent",
810 return isl_schedule_node_free(node
));
811 return isl_schedule_node_ancestor(node
, 1);
814 /* Move the "node" pointer to the root of its schedule tree.
816 __isl_give isl_schedule_node
*isl_schedule_node_root(
817 __isl_take isl_schedule_node
*node
)
823 n
= isl_schedule_node_get_tree_depth(node
);
825 return isl_schedule_node_free(node
);
826 return isl_schedule_node_ancestor(node
, n
);
829 /* Move the "node" pointer to the child at position "pos" of the node
830 * it currently points to.
832 __isl_give isl_schedule_node
*isl_schedule_node_child(
833 __isl_take isl_schedule_node
*node
, int pos
)
837 isl_schedule_tree
*tree
;
840 node
= isl_schedule_node_cow(node
);
843 if (!isl_schedule_node_has_children(node
))
844 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
845 "node has no children",
846 return isl_schedule_node_free(node
));
848 ctx
= isl_schedule_node_get_ctx(node
);
849 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
850 child_pos
= isl_realloc_array(ctx
, node
->child_pos
, int, n
+ 1);
852 return isl_schedule_node_free(node
);
853 node
->child_pos
= child_pos
;
854 node
->child_pos
[n
] = pos
;
856 node
->ancestors
= isl_schedule_tree_list_add(node
->ancestors
,
857 isl_schedule_tree_copy(node
->tree
));
859 if (isl_schedule_tree_has_children(tree
))
860 tree
= isl_schedule_tree_get_child(tree
, pos
);
862 tree
= isl_schedule_node_get_leaf(node
);
863 isl_schedule_tree_free(node
->tree
);
866 if (!node
->tree
|| !node
->ancestors
)
867 return isl_schedule_node_free(node
);
872 /* Move the "node" pointer to the first child of the node
873 * it currently points to.
875 __isl_give isl_schedule_node
*isl_schedule_node_first_child(
876 __isl_take isl_schedule_node
*node
)
878 return isl_schedule_node_child(node
, 0);
881 /* Move the "node" pointer to the child of this node's parent in
882 * the previous child position.
884 __isl_give isl_schedule_node
*isl_schedule_node_previous_sibling(
885 __isl_take isl_schedule_node
*node
)
888 isl_schedule_tree
*parent
, *tree
;
890 node
= isl_schedule_node_cow(node
);
893 if (!isl_schedule_node_has_previous_sibling(node
))
894 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
895 "node has no previous sibling",
896 return isl_schedule_node_free(node
));
898 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
899 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
902 return isl_schedule_node_free(node
);
903 node
->child_pos
[n
- 1]--;
904 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
905 node
->child_pos
[n
- 1]);
906 isl_schedule_tree_free(parent
);
908 return isl_schedule_node_free(node
);
909 isl_schedule_tree_free(node
->tree
);
915 /* Move the "node" pointer to the child of this node's parent in
916 * the next child position.
918 __isl_give isl_schedule_node
*isl_schedule_node_next_sibling(
919 __isl_take isl_schedule_node
*node
)
922 isl_schedule_tree
*parent
, *tree
;
924 node
= isl_schedule_node_cow(node
);
927 if (!isl_schedule_node_has_next_sibling(node
))
928 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
929 "node has no next sibling",
930 return isl_schedule_node_free(node
));
932 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
933 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
936 return isl_schedule_node_free(node
);
937 node
->child_pos
[n
- 1]++;
938 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
939 node
->child_pos
[n
- 1]);
940 isl_schedule_tree_free(parent
);
942 return isl_schedule_node_free(node
);
943 isl_schedule_tree_free(node
->tree
);
949 /* Return a copy to the child at position "pos" of "node".
951 __isl_give isl_schedule_node
*isl_schedule_node_get_child(
952 __isl_keep isl_schedule_node
*node
, int pos
)
954 return isl_schedule_node_child(isl_schedule_node_copy(node
), pos
);
957 /* Traverse the descendant of "node" in depth-first order, including
958 * "node" itself. Call "enter" whenever a node is entered and "leave"
959 * whenever a node is left. The callback "enter" is responsible
960 * for moving to the deepest initial subtree of its argument that
961 * should be traversed.
963 static __isl_give isl_schedule_node
*traverse(
964 __isl_take isl_schedule_node
*node
,
965 __isl_give isl_schedule_node
*(*enter
)(
966 __isl_take isl_schedule_node
*node
, void *user
),
967 __isl_give isl_schedule_node
*(*leave
)(
968 __isl_take isl_schedule_node
*node
, void *user
),
976 depth
= isl_schedule_node_get_tree_depth(node
);
978 node
= enter(node
, user
);
979 node
= leave(node
, user
);
980 while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
&&
981 !isl_schedule_node_has_next_sibling(node
)) {
982 node
= isl_schedule_node_parent(node
);
983 node
= leave(node
, user
);
985 if (node
&& isl_schedule_node_get_tree_depth(node
) > depth
)
986 node
= isl_schedule_node_next_sibling(node
);
987 } while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
);
992 /* Internal data structure for isl_schedule_node_foreach_descendant.
994 * "fn" is the user-specified callback function.
995 * "user" is the user-specified argument for the callback.
997 struct isl_schedule_node_preorder_data
{
998 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
);
1002 /* Callback for "traverse" to enter a node and to move
1003 * to the deepest initial subtree that should be traversed
1004 * for use in a preorder visit.
1006 * If the user callback returns a negative value, then we abort
1007 * the traversal. If this callback returns zero, then we skip
1008 * the subtree rooted at the current node. Otherwise, we move
1009 * down to the first child and repeat the process until a leaf
1012 static __isl_give isl_schedule_node
*preorder_enter(
1013 __isl_take isl_schedule_node
*node
, void *user
)
1015 struct isl_schedule_node_preorder_data
*data
= user
;
1023 r
= data
->fn(node
, data
->user
);
1025 return isl_schedule_node_free(node
);
1028 } while (isl_schedule_node_has_children(node
) &&
1029 (node
= isl_schedule_node_first_child(node
)) != NULL
);
1034 /* Callback for "traverse" to leave a node
1035 * for use in a preorder visit.
1036 * Since we already visited the node when we entered it,
1037 * we do not need to do anything here.
1039 static __isl_give isl_schedule_node
*preorder_leave(
1040 __isl_take isl_schedule_node
*node
, void *user
)
1045 /* Traverse the descendants of "node" (including the node itself)
1046 * in depth first preorder.
1048 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1049 * If "fn" returns 0 on any of the nodes, then the subtree rooted
1050 * at that node is skipped.
1052 * Return 0 on success and -1 on failure.
1054 int isl_schedule_node_foreach_descendant(__isl_keep isl_schedule_node
*node
,
1055 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
), void *user
)
1057 struct isl_schedule_node_preorder_data data
= { fn
, user
};
1059 node
= isl_schedule_node_copy(node
);
1060 node
= traverse(node
, &preorder_enter
, &preorder_leave
, &data
);
1061 isl_schedule_node_free(node
);
1063 return node
? 0 : -1;
1066 /* Internal data structure for isl_schedule_node_map_descendant.
1068 * "fn" is the user-specified callback function.
1069 * "user" is the user-specified argument for the callback.
1071 struct isl_schedule_node_postorder_data
{
1072 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1077 /* Callback for "traverse" to enter a node and to move
1078 * to the deepest initial subtree that should be traversed
1079 * for use in a postorder visit.
1081 * Since we are performing a postorder visit, we only need
1082 * to move to the deepest initial leaf here.
1084 static __isl_give isl_schedule_node
*postorder_enter(
1085 __isl_take isl_schedule_node
*node
, void *user
)
1087 while (node
&& isl_schedule_node_has_children(node
))
1088 node
= isl_schedule_node_first_child(node
);
1093 /* Callback for "traverse" to leave a node
1094 * for use in a postorder visit.
1096 * Since we are performing a postorder visit, we need
1097 * to call the user callback here.
1099 static __isl_give isl_schedule_node
*postorder_leave(
1100 __isl_take isl_schedule_node
*node
, void *user
)
1102 struct isl_schedule_node_postorder_data
*data
= user
;
1104 return data
->fn(node
, data
->user
);
1107 /* Traverse the descendants of "node" (including the node itself)
1108 * in depth first postorder, allowing the user to modify the visited node.
1109 * The traversal continues from the node returned by the callback function.
1110 * It is the responsibility of the user to ensure that this does not
1111 * lead to an infinite loop. It is safest to always return a pointer
1112 * to the same position (same ancestors and child positions) as the input node.
1114 __isl_give isl_schedule_node
*isl_schedule_node_map_descendant(
1115 __isl_take isl_schedule_node
*node
,
1116 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1117 void *user
), void *user
)
1119 struct isl_schedule_node_postorder_data data
= { fn
, user
};
1121 return traverse(node
, &postorder_enter
, &postorder_leave
, &data
);
1124 /* Traverse the ancestors of "node" from the root down to and including
1125 * the parent of "node", calling "fn" on each of them.
1127 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1129 * Return 0 on success and -1 on failure.
1131 int isl_schedule_node_foreach_ancestor_top_down(
1132 __isl_keep isl_schedule_node
*node
,
1133 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
), void *user
)
1140 n
= isl_schedule_node_get_tree_depth(node
);
1141 for (i
= 0; i
< n
; ++i
) {
1142 isl_schedule_node
*ancestor
;
1145 ancestor
= isl_schedule_node_copy(node
);
1146 ancestor
= isl_schedule_node_ancestor(ancestor
, n
- i
);
1147 r
= fn(ancestor
, user
);
1148 isl_schedule_node_free(ancestor
);
1156 /* Is any node in the subtree rooted at "node" anchored?
1157 * That is, do any of these nodes reference the outer band nodes?
1159 int isl_schedule_node_is_subtree_anchored(__isl_keep isl_schedule_node
*node
)
1163 return isl_schedule_tree_is_subtree_anchored(node
->tree
);
1166 /* Return the number of members in the given band node.
1168 unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node
*node
)
1170 return node
? isl_schedule_tree_band_n_member(node
->tree
) : 0;
1173 /* Is the band member at position "pos" of the band node "node"
1174 * marked coincident?
1176 int isl_schedule_node_band_member_get_coincident(
1177 __isl_keep isl_schedule_node
*node
, int pos
)
1181 return isl_schedule_tree_band_member_get_coincident(node
->tree
, pos
);
1184 /* Mark the band member at position "pos" the band node "node"
1185 * as being coincident or not according to "coincident".
1187 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_coincident(
1188 __isl_take isl_schedule_node
*node
, int pos
, int coincident
)
1191 isl_schedule_tree
*tree
;
1195 c
= isl_schedule_node_band_member_get_coincident(node
, pos
);
1196 if (c
== coincident
)
1199 tree
= isl_schedule_tree_copy(node
->tree
);
1200 tree
= isl_schedule_tree_band_member_set_coincident(tree
, pos
,
1202 node
= isl_schedule_node_graft_tree(node
, tree
);
1207 /* Is the band node "node" marked permutable?
1209 int isl_schedule_node_band_get_permutable(__isl_keep isl_schedule_node
*node
)
1214 return isl_schedule_tree_band_get_permutable(node
->tree
);
1217 /* Mark the band node "node" permutable or not according to "permutable"?
1219 __isl_give isl_schedule_node
*isl_schedule_node_band_set_permutable(
1220 __isl_take isl_schedule_node
*node
, int permutable
)
1222 isl_schedule_tree
*tree
;
1226 if (isl_schedule_node_band_get_permutable(node
) == permutable
)
1229 tree
= isl_schedule_tree_copy(node
->tree
);
1230 tree
= isl_schedule_tree_band_set_permutable(tree
, permutable
);
1231 node
= isl_schedule_node_graft_tree(node
, tree
);
1236 /* Return the schedule space of the band node.
1238 __isl_give isl_space
*isl_schedule_node_band_get_space(
1239 __isl_keep isl_schedule_node
*node
)
1244 return isl_schedule_tree_band_get_space(node
->tree
);
1247 /* Return the schedule of the band node in isolation.
1249 __isl_give isl_multi_union_pw_aff
*isl_schedule_node_band_get_partial_schedule(
1250 __isl_keep isl_schedule_node
*node
)
1255 return isl_schedule_tree_band_get_partial_schedule(node
->tree
);
1258 /* Return the schedule of the band node in isolation in the form of
1261 * If the band does not have any members, then we construct a universe map
1262 * with the universe of the domain elements reaching the node as domain.
1263 * Otherwise, we extract an isl_multi_union_pw_aff representation and
1264 * convert that to an isl_union_map.
1266 __isl_give isl_union_map
*isl_schedule_node_band_get_partial_schedule_union_map(
1267 __isl_keep isl_schedule_node
*node
)
1269 isl_multi_union_pw_aff
*mupa
;
1274 if (isl_schedule_node_get_type(node
) != isl_schedule_node_band
)
1275 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1276 "not a band node", return NULL
);
1277 if (isl_schedule_node_band_n_member(node
) == 0) {
1278 isl_union_set
*domain
;
1280 domain
= isl_schedule_node_get_universe_domain(node
);
1281 return isl_union_map_from_domain(domain
);
1284 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
1285 return isl_union_map_from_multi_union_pw_aff(mupa
);
1288 /* Return the loop AST generation type for the band member of band node "node"
1289 * at position "pos".
1291 enum isl_ast_loop_type
isl_schedule_node_band_member_get_ast_loop_type(
1292 __isl_keep isl_schedule_node
*node
, int pos
)
1295 return isl_ast_loop_error
;
1297 return isl_schedule_tree_band_member_get_ast_loop_type(node
->tree
, pos
);
1300 /* Set the loop AST generation type for the band member of band node "node"
1301 * at position "pos" to "type".
1303 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_ast_loop_type(
1304 __isl_take isl_schedule_node
*node
, int pos
,
1305 enum isl_ast_loop_type type
)
1307 isl_schedule_tree
*tree
;
1312 tree
= isl_schedule_tree_copy(node
->tree
);
1313 tree
= isl_schedule_tree_band_member_set_ast_loop_type(tree
, pos
, type
);
1314 return isl_schedule_node_graft_tree(node
, tree
);
1317 /* Return the loop AST generation type for the band member of band node "node"
1318 * at position "pos" for the isolated part.
1320 enum isl_ast_loop_type
isl_schedule_node_band_member_get_isolate_ast_loop_type(
1321 __isl_keep isl_schedule_node
*node
, int pos
)
1324 return isl_ast_loop_error
;
1326 return isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1330 /* Set the loop AST generation type for the band member of band node "node"
1331 * at position "pos" for the isolated part to "type".
1333 __isl_give isl_schedule_node
*
1334 isl_schedule_node_band_member_set_isolate_ast_loop_type(
1335 __isl_take isl_schedule_node
*node
, int pos
,
1336 enum isl_ast_loop_type type
)
1338 isl_schedule_tree
*tree
;
1343 tree
= isl_schedule_tree_copy(node
->tree
);
1344 tree
= isl_schedule_tree_band_member_set_isolate_ast_loop_type(tree
,
1346 return isl_schedule_node_graft_tree(node
, tree
);
1349 /* Return the AST build options associated to band node "node".
1351 __isl_give isl_union_set
*isl_schedule_node_band_get_ast_build_options(
1352 __isl_keep isl_schedule_node
*node
)
1357 return isl_schedule_tree_band_get_ast_build_options(node
->tree
);
1360 /* Replace the AST build options associated to band node "node" by "options".
1362 __isl_give isl_schedule_node
*isl_schedule_node_band_set_ast_build_options(
1363 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*options
)
1365 isl_schedule_tree
*tree
;
1367 if (!node
|| !options
)
1370 tree
= isl_schedule_tree_copy(node
->tree
);
1371 tree
= isl_schedule_tree_band_set_ast_build_options(tree
, options
);
1372 return isl_schedule_node_graft_tree(node
, tree
);
1374 isl_schedule_node_free(node
);
1375 isl_union_set_free(options
);
1379 /* Make sure that that spaces of "node" and "mv" are the same.
1380 * Return -1 on error, reporting the error to the user.
1382 static int check_space_multi_val(__isl_keep isl_schedule_node
*node
,
1383 __isl_keep isl_multi_val
*mv
)
1385 isl_space
*node_space
, *mv_space
;
1388 node_space
= isl_schedule_node_band_get_space(node
);
1389 mv_space
= isl_multi_val_get_space(mv
);
1390 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1391 mv_space
, isl_dim_set
);
1392 isl_space_free(mv_space
);
1393 isl_space_free(node_space
);
1397 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1398 "spaces don't match", return -1);
1403 /* Multiply the partial schedule of the band node "node"
1404 * with the factors in "mv".
1406 __isl_give isl_schedule_node
*isl_schedule_node_band_scale(
1407 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1409 isl_schedule_tree
*tree
;
1414 if (check_space_multi_val(node
, mv
) < 0)
1416 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1420 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1421 "cannot scale band node with anchored subtree",
1424 tree
= isl_schedule_node_get_tree(node
);
1425 tree
= isl_schedule_tree_band_scale(tree
, mv
);
1426 return isl_schedule_node_graft_tree(node
, tree
);
1428 isl_multi_val_free(mv
);
1429 isl_schedule_node_free(node
);
1433 /* Divide the partial schedule of the band node "node"
1434 * by the factors in "mv".
1436 __isl_give isl_schedule_node
*isl_schedule_node_band_scale_down(
1437 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1439 isl_schedule_tree
*tree
;
1444 if (check_space_multi_val(node
, mv
) < 0)
1446 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1450 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1451 "cannot scale down band node with anchored subtree",
1454 tree
= isl_schedule_node_get_tree(node
);
1455 tree
= isl_schedule_tree_band_scale_down(tree
, mv
);
1456 return isl_schedule_node_graft_tree(node
, tree
);
1458 isl_multi_val_free(mv
);
1459 isl_schedule_node_free(node
);
1463 /* Tile "node" with tile sizes "sizes".
1465 * The current node is replaced by two nested nodes corresponding
1466 * to the tile dimensions and the point dimensions.
1468 * Return a pointer to the outer (tile) node.
1470 * If any of the descendants of "node" depend on the set of outer band nodes,
1471 * then we refuse to tile the node.
1473 * If the scale tile loops option is set, then the tile loops
1474 * are scaled by the tile sizes. If the shift point loops option is set,
1475 * then the point loops are shifted to start at zero.
1476 * In particular, these options affect the tile and point loop schedules
1479 * scale shift original tile point
1481 * 0 0 i floor(i/s) i
1482 * 1 0 i s * floor(i/s) i
1483 * 0 1 i floor(i/s) i - s * floor(i/s)
1484 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1486 __isl_give isl_schedule_node
*isl_schedule_node_band_tile(
1487 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*sizes
)
1489 isl_schedule_tree
*tree
;
1492 if (!node
|| !sizes
)
1494 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1498 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1499 "cannot tile band node with anchored subtree",
1502 if (check_space_multi_val(node
, sizes
) < 0)
1505 tree
= isl_schedule_node_get_tree(node
);
1506 tree
= isl_schedule_tree_band_tile(tree
, sizes
);
1507 return isl_schedule_node_graft_tree(node
, tree
);
1509 isl_multi_val_free(sizes
);
1510 isl_schedule_node_free(node
);
1514 /* Move the band node "node" down to all the leaves in the subtree
1516 * Return a pointer to the node in the resulting tree that is in the same
1517 * position as the node pointed to by "node" in the original tree.
1519 * If the node only has a leaf child, then nothing needs to be done.
1520 * Otherwise, the child of the node is removed and the result is
1521 * appended to all the leaves in the subtree rooted at the original child.
1522 * The original node is then replaced by the result of this operation.
1524 * If any of the nodes in the subtree rooted at "node" depend on
1525 * the set of outer band nodes then we refuse to sink the band node.
1527 __isl_give isl_schedule_node
*isl_schedule_node_band_sink(
1528 __isl_take isl_schedule_node
*node
)
1530 enum isl_schedule_node_type type
;
1531 isl_schedule_tree
*tree
, *child
;
1537 type
= isl_schedule_node_get_type(node
);
1538 if (type
!= isl_schedule_node_band
)
1539 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1540 "not a band node", isl_schedule_node_free(node
));
1541 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1543 return isl_schedule_node_free(node
);
1545 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1546 "cannot sink band node in anchored subtree",
1547 isl_schedule_node_free(node
));
1548 if (isl_schedule_tree_n_children(node
->tree
) == 0)
1551 tree
= isl_schedule_node_get_tree(node
);
1552 child
= isl_schedule_tree_get_child(tree
, 0);
1553 tree
= isl_schedule_tree_reset_children(tree
);
1554 tree
= isl_schedule_tree_append_to_leaves(child
, tree
);
1556 return isl_schedule_node_graft_tree(node
, tree
);
1559 /* Split "node" into two nested band nodes, one with the first "pos"
1560 * dimensions and one with the remaining dimensions.
1561 * The schedules of the two band nodes live in anonymous spaces.
1563 __isl_give isl_schedule_node
*isl_schedule_node_band_split(
1564 __isl_take isl_schedule_node
*node
, int pos
)
1566 isl_schedule_tree
*tree
;
1568 tree
= isl_schedule_node_get_tree(node
);
1569 tree
= isl_schedule_tree_band_split(tree
, pos
);
1570 return isl_schedule_node_graft_tree(node
, tree
);
1573 /* Return the context of the context node "node".
1575 __isl_give isl_set
*isl_schedule_node_context_get_context(
1576 __isl_keep isl_schedule_node
*node
)
1581 return isl_schedule_tree_context_get_context(node
->tree
);
1584 /* Return the domain of the domain node "node".
1586 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
1587 __isl_keep isl_schedule_node
*node
)
1592 return isl_schedule_tree_domain_get_domain(node
->tree
);
1595 /* Return the filter of the filter node "node".
1597 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
1598 __isl_keep isl_schedule_node
*node
)
1603 return isl_schedule_tree_filter_get_filter(node
->tree
);
1606 /* Replace the filter of filter node "node" by "filter".
1608 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
1609 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
1611 isl_schedule_tree
*tree
;
1613 if (!node
|| !filter
)
1616 tree
= isl_schedule_tree_copy(node
->tree
);
1617 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
1618 return isl_schedule_node_graft_tree(node
, tree
);
1620 isl_schedule_node_free(node
);
1621 isl_union_set_free(filter
);
1625 /* Update the ancestors of "node" to point to the tree that "node"
1627 * That is, replace the child in the original parent that corresponds
1628 * to the current tree position by node->tree and continue updating
1629 * the ancestors in the same way until the root is reached.
1631 * If "node" originally points to a leaf of the schedule tree, then make sure
1632 * that in the end it points to a leaf in the updated schedule tree.
1634 static __isl_give isl_schedule_node
*update_ancestors(
1635 __isl_take isl_schedule_node
*node
)
1640 isl_schedule_tree
*tree
;
1642 node
= isl_schedule_node_cow(node
);
1646 ctx
= isl_schedule_node_get_ctx(node
);
1647 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1648 tree
= isl_schedule_tree_copy(node
->tree
);
1650 for (i
= n
- 1; i
>= 0; --i
) {
1651 isl_schedule_tree
*parent
;
1653 parent
= isl_schedule_tree_list_get_schedule_tree(
1654 node
->ancestors
, i
);
1655 parent
= isl_schedule_tree_replace_child(parent
,
1656 node
->child_pos
[i
], tree
);
1657 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
1658 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
1663 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
1664 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
1666 isl_schedule_tree_free(node
->tree
);
1667 node
->tree
= isl_schedule_node_get_leaf(node
);
1670 if (!node
->schedule
|| !node
->ancestors
)
1671 return isl_schedule_node_free(node
);
1676 /* Replace the subtree that "pos" points to by "tree", updating
1677 * the ancestors to maintain a consistent state.
1679 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
1680 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
1684 if (pos
->tree
== tree
) {
1685 isl_schedule_tree_free(tree
);
1689 pos
= isl_schedule_node_cow(pos
);
1693 isl_schedule_tree_free(pos
->tree
);
1696 return update_ancestors(pos
);
1698 isl_schedule_node_free(pos
);
1699 isl_schedule_tree_free(tree
);
1703 /* Make sure we can insert a node between "node" and its parent.
1704 * Return -1 on error, reporting the reason why we cannot insert a node.
1706 static int check_insert(__isl_keep isl_schedule_node
*node
)
1709 enum isl_schedule_node_type type
;
1711 has_parent
= isl_schedule_node_has_parent(node
);
1715 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1716 "cannot insert node outside of root", return -1);
1718 type
= isl_schedule_node_get_parent_type(node
);
1719 if (type
== isl_schedule_node_error
)
1721 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
1722 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1723 "cannot insert node between set or sequence node "
1724 "and its filter children", return -1);
1729 /* Insert a band node with partial schedule "mupa" between "node" and
1731 * Return a pointer to the new band node.
1733 * If any of the nodes in the subtree rooted at "node" depend on
1734 * the set of outer band nodes then we refuse to insert the band node.
1736 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
1737 __isl_take isl_schedule_node
*node
,
1738 __isl_take isl_multi_union_pw_aff
*mupa
)
1741 isl_schedule_band
*band
;
1742 isl_schedule_tree
*tree
;
1744 if (check_insert(node
) < 0)
1745 node
= isl_schedule_node_free(node
);
1746 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1750 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1751 "cannot insert band node in anchored subtree",
1754 tree
= isl_schedule_node_get_tree(node
);
1755 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
1756 tree
= isl_schedule_tree_insert_band(tree
, band
);
1757 node
= isl_schedule_node_graft_tree(node
, tree
);
1761 isl_schedule_node_free(node
);
1762 isl_multi_union_pw_aff_free(mupa
);
1766 /* Insert a context node with context "context" between "node" and its parent.
1767 * Return a pointer to the new context node.
1769 __isl_give isl_schedule_node
*isl_schedule_node_insert_context(
1770 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
1772 isl_schedule_tree
*tree
;
1774 if (check_insert(node
) < 0)
1775 node
= isl_schedule_node_free(node
);
1777 tree
= isl_schedule_node_get_tree(node
);
1778 tree
= isl_schedule_tree_insert_context(tree
, context
);
1779 node
= isl_schedule_node_graft_tree(node
, tree
);
1784 /* Insert a filter node with filter "filter" between "node" and its parent.
1785 * Return a pointer to the new filter node.
1787 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
1788 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
1790 isl_schedule_tree
*tree
;
1792 if (check_insert(node
) < 0)
1793 node
= isl_schedule_node_free(node
);
1795 tree
= isl_schedule_node_get_tree(node
);
1796 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
1797 node
= isl_schedule_node_graft_tree(node
, tree
);
1802 /* Attach the current subtree of "node" to a sequence of filter tree nodes
1803 * with filters described by "filters", attach this sequence
1804 * of filter tree nodes as children to a new tree of type "type" and
1805 * replace the original subtree of "node" by this new tree.
1807 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
1808 __isl_take isl_schedule_node
*node
,
1809 enum isl_schedule_node_type type
,
1810 __isl_take isl_union_set_list
*filters
)
1814 isl_schedule_tree
*tree
;
1815 isl_schedule_tree_list
*list
;
1817 if (check_insert(node
) < 0)
1818 node
= isl_schedule_node_free(node
);
1820 if (!node
|| !filters
)
1823 ctx
= isl_schedule_node_get_ctx(node
);
1824 n
= isl_union_set_list_n_union_set(filters
);
1825 list
= isl_schedule_tree_list_alloc(ctx
, n
);
1826 for (i
= 0; i
< n
; ++i
) {
1827 isl_schedule_tree
*tree
;
1828 isl_union_set
*filter
;
1830 tree
= isl_schedule_node_get_tree(node
);
1831 filter
= isl_union_set_list_get_union_set(filters
, i
);
1832 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
1833 list
= isl_schedule_tree_list_add(list
, tree
);
1835 tree
= isl_schedule_tree_from_children(type
, list
);
1836 node
= isl_schedule_node_graft_tree(node
, tree
);
1838 isl_union_set_list_free(filters
);
1841 isl_union_set_list_free(filters
);
1842 isl_schedule_node_free(node
);
1846 /* Insert a sequence node with child filters "filters" between "node" and
1847 * its parent. That is, the tree that "node" points to is attached
1848 * to each of the child nodes of the filter nodes.
1849 * Return a pointer to the new sequence node.
1851 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
1852 __isl_take isl_schedule_node
*node
,
1853 __isl_take isl_union_set_list
*filters
)
1855 return isl_schedule_node_insert_children(node
,
1856 isl_schedule_node_sequence
, filters
);
1859 /* Insert a set node with child filters "filters" between "node" and
1860 * its parent. That is, the tree that "node" points to is attached
1861 * to each of the child nodes of the filter nodes.
1862 * Return a pointer to the new set node.
1864 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
1865 __isl_take isl_schedule_node
*node
,
1866 __isl_take isl_union_set_list
*filters
)
1868 return isl_schedule_node_insert_children(node
,
1869 isl_schedule_node_set
, filters
);
1872 /* Remove "node" from its schedule tree and return a pointer
1873 * to the leaf at the same position in the updated schedule tree.
1875 * It is not allowed to remove the root of a schedule tree or
1876 * a child of a set or sequence node.
1878 __isl_give isl_schedule_node
*isl_schedule_node_cut(
1879 __isl_take isl_schedule_node
*node
)
1881 isl_schedule_tree
*leaf
;
1882 enum isl_schedule_node_type parent_type
;
1886 if (!isl_schedule_node_has_parent(node
))
1887 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1888 "cannot cut root", return isl_schedule_node_free(node
));
1890 parent_type
= isl_schedule_node_get_parent_type(node
);
1891 if (parent_type
== isl_schedule_node_set
||
1892 parent_type
== isl_schedule_node_sequence
)
1893 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1894 "cannot cut child of set or sequence",
1895 return isl_schedule_node_free(node
));
1897 leaf
= isl_schedule_node_get_leaf(node
);
1898 return isl_schedule_node_graft_tree(node
, leaf
);
1901 /* Remove a single node from the schedule tree, attaching the child
1902 * of "node" directly to its parent.
1903 * Return a pointer to this former child or to the leaf the position
1904 * of the original node if there was no child.
1905 * It is not allowed to remove the root of a schedule tree,
1906 * a set or sequence node, a child of a set or sequence node or
1907 * a band node with an anchored subtree.
1909 __isl_give isl_schedule_node
*isl_schedule_node_delete(
1910 __isl_take isl_schedule_node
*node
)
1913 isl_schedule_tree
*tree
;
1914 enum isl_schedule_node_type type
;
1919 if (isl_schedule_node_get_tree_depth(node
) == 0)
1920 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1921 "cannot delete root node",
1922 return isl_schedule_node_free(node
));
1923 n
= isl_schedule_node_n_children(node
);
1925 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1926 "can only delete node with a single child",
1927 return isl_schedule_node_free(node
));
1928 type
= isl_schedule_node_get_parent_type(node
);
1929 if (type
== isl_schedule_node_sequence
|| type
== isl_schedule_node_set
)
1930 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1931 "cannot delete child of set or sequence",
1932 return isl_schedule_node_free(node
));
1933 if (isl_schedule_node_get_type(node
) == isl_schedule_node_band
) {
1936 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1938 return isl_schedule_node_free(node
);
1940 isl_die(isl_schedule_node_get_ctx(node
),
1942 "cannot delete band node with anchored subtree",
1943 return isl_schedule_node_free(node
));
1946 tree
= isl_schedule_node_get_tree(node
);
1947 if (!tree
|| isl_schedule_tree_has_children(tree
)) {
1948 tree
= isl_schedule_tree_child(tree
, 0);
1950 isl_schedule_tree_free(tree
);
1951 tree
= isl_schedule_node_get_leaf(node
);
1953 node
= isl_schedule_node_graft_tree(node
, tree
);
1958 /* Compute the gist of the given band node with respect to "context".
1960 __isl_give isl_schedule_node
*isl_schedule_node_band_gist(
1961 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
1963 isl_schedule_tree
*tree
;
1965 tree
= isl_schedule_node_get_tree(node
);
1966 tree
= isl_schedule_tree_band_gist(tree
, context
);
1967 return isl_schedule_node_graft_tree(node
, tree
);
1970 /* Internal data structure for isl_schedule_node_gist.
1971 * "filters" contains an element for each outer filter node
1972 * with respect to the current position, each representing
1973 * the intersection of the previous element and the filter on the filter node.
1974 * The first element in the original context passed to isl_schedule_node_gist.
1976 struct isl_node_gist_data
{
1977 isl_union_set_list
*filters
;
1980 /* Can we finish gisting at this node?
1981 * That is, is the filter on the current filter node a subset of
1982 * the original context passed to isl_schedule_node_gist?
1984 static int gist_done(__isl_keep isl_schedule_node
*node
,
1985 struct isl_node_gist_data
*data
)
1987 isl_union_set
*filter
, *outer
;
1990 filter
= isl_schedule_node_filter_get_filter(node
);
1991 outer
= isl_union_set_list_get_union_set(data
->filters
, 0);
1992 subset
= isl_union_set_is_subset(filter
, outer
);
1993 isl_union_set_free(outer
);
1994 isl_union_set_free(filter
);
1999 /* Callback for "traverse" to enter a node and to move
2000 * to the deepest initial subtree that should be traversed
2001 * by isl_schedule_node_gist.
2003 * The "filters" list is extended by one element each time
2004 * we come across a filter node by the result of intersecting
2005 * the last element in the list with the filter on the filter node.
2007 * If the filter on the current filter node is a subset of
2008 * the original context passed to isl_schedule_node_gist,
2009 * then there is no need to go into its subtree since it cannot
2010 * be further simplified by the context. The "filters" list is
2011 * still extended for consistency, but the actual value of the
2012 * added element is immaterial since it will not be used.
2014 * Otherwise, the filter on the current filter node is replaced by
2015 * the gist of the original filter with respect to the intersection
2016 * of the original context with the intermediate filters.
2018 * If the new element in the "filters" list is empty, then no elements
2019 * can reach the descendants of the current filter node. The subtree
2020 * underneath the filter node is therefore removed.
2022 static __isl_give isl_schedule_node
*gist_enter(
2023 __isl_take isl_schedule_node
*node
, void *user
)
2025 struct isl_node_gist_data
*data
= user
;
2028 isl_union_set
*filter
, *inner
;
2032 switch (isl_schedule_node_get_type(node
)) {
2033 case isl_schedule_node_error
:
2034 return isl_schedule_node_free(node
);
2035 case isl_schedule_node_band
:
2036 case isl_schedule_node_context
:
2037 case isl_schedule_node_domain
:
2038 case isl_schedule_node_leaf
:
2039 case isl_schedule_node_sequence
:
2040 case isl_schedule_node_set
:
2042 case isl_schedule_node_filter
:
2045 done
= gist_done(node
, data
);
2046 filter
= isl_schedule_node_filter_get_filter(node
);
2047 if (done
< 0 || done
) {
2048 data
->filters
= isl_union_set_list_add(data
->filters
,
2051 return isl_schedule_node_free(node
);
2054 n
= isl_union_set_list_n_union_set(data
->filters
);
2055 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
2056 filter
= isl_union_set_gist(filter
, isl_union_set_copy(inner
));
2057 node
= isl_schedule_node_filter_set_filter(node
,
2058 isl_union_set_copy(filter
));
2059 filter
= isl_union_set_intersect(filter
, inner
);
2060 empty
= isl_union_set_is_empty(filter
);
2061 data
->filters
= isl_union_set_list_add(data
->filters
, filter
);
2063 return isl_schedule_node_free(node
);
2066 node
= isl_schedule_node_child(node
, 0);
2067 node
= isl_schedule_node_cut(node
);
2068 node
= isl_schedule_node_parent(node
);
2070 } while (isl_schedule_node_has_children(node
) &&
2071 (node
= isl_schedule_node_first_child(node
)) != NULL
);
2076 /* Callback for "traverse" to leave a node for isl_schedule_node_gist.
2078 * In particular, if the current node is a filter node, then we remove
2079 * the element on the "filters" list that was added when we entered
2080 * the node. There is no need to compute any gist here, since we
2081 * already did that when we entered the node.
2083 * If the current node is a band node, then we compute the gist of
2084 * the band node with respect to the intersection of the original context
2085 * and the intermediate filters.
2087 * If the current node is a sequence or set node, then some of
2088 * the filter children may have become empty and so they are removed.
2089 * If only one child is left, then the set or sequence node along with
2090 * the single remaining child filter is removed. The filter can be
2091 * removed because the filters on a sequence or set node are supposed
2092 * to partition the incoming domain instances.
2093 * In principle, it should then be impossible for there to be zero
2094 * remaining children, but should this happen, we replace the entire
2095 * subtree with an empty filter.
2097 static __isl_give isl_schedule_node
*gist_leave(
2098 __isl_take isl_schedule_node
*node
, void *user
)
2100 struct isl_node_gist_data
*data
= user
;
2101 isl_schedule_tree
*tree
;
2103 isl_union_set
*filter
;
2105 switch (isl_schedule_node_get_type(node
)) {
2106 case isl_schedule_node_error
:
2107 return isl_schedule_node_free(node
);
2108 case isl_schedule_node_filter
:
2109 n
= isl_union_set_list_n_union_set(data
->filters
);
2110 data
->filters
= isl_union_set_list_drop(data
->filters
,
2113 case isl_schedule_node_band
:
2114 n
= isl_union_set_list_n_union_set(data
->filters
);
2115 filter
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
2116 node
= isl_schedule_node_band_gist(node
, filter
);
2118 case isl_schedule_node_set
:
2119 case isl_schedule_node_sequence
:
2120 tree
= isl_schedule_node_get_tree(node
);
2121 n
= isl_schedule_tree_n_children(tree
);
2122 for (i
= n
- 1; i
>= 0; --i
) {
2123 isl_schedule_tree
*child
;
2124 isl_union_set
*filter
;
2127 child
= isl_schedule_tree_get_child(tree
, i
);
2128 filter
= isl_schedule_tree_filter_get_filter(child
);
2129 empty
= isl_union_set_is_empty(filter
);
2130 isl_union_set_free(filter
);
2131 isl_schedule_tree_free(child
);
2133 tree
= isl_schedule_tree_free(tree
);
2135 tree
= isl_schedule_tree_drop_child(tree
, i
);
2137 n
= isl_schedule_tree_n_children(tree
);
2138 node
= isl_schedule_node_graft_tree(node
, tree
);
2140 node
= isl_schedule_node_delete(node
);
2141 node
= isl_schedule_node_delete(node
);
2142 } else if (n
== 0) {
2146 isl_union_set_list_get_union_set(data
->filters
, 0);
2147 space
= isl_union_set_get_space(filter
);
2148 isl_union_set_free(filter
);
2149 filter
= isl_union_set_empty(space
);
2150 node
= isl_schedule_node_cut(node
);
2151 node
= isl_schedule_node_insert_filter(node
, filter
);
2154 case isl_schedule_node_context
:
2155 case isl_schedule_node_domain
:
2156 case isl_schedule_node_leaf
:
2163 /* Compute the gist of the subtree at "node" with respect to
2164 * the reaching domain elements in "context".
2165 * In particular, compute the gist of all band and filter nodes
2166 * in the subtree with respect to "context". Children of set or sequence
2167 * nodes that end up with an empty filter are removed completely.
2169 * We keep track of the intersection of "context" with all outer filters
2170 * of the current node within the subtree in the final element of "filters".
2171 * Initially, this list contains the single element "context" and it is
2172 * extended or shortened each time we enter or leave a filter node.
2174 __isl_give isl_schedule_node
*isl_schedule_node_gist(
2175 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
2177 struct isl_node_gist_data data
;
2179 data
.filters
= isl_union_set_list_from_union_set(context
);
2180 node
= traverse(node
, &gist_enter
, &gist_leave
, &data
);
2181 isl_union_set_list_free(data
.filters
);
2185 /* Intersect the domain of domain node "node" with "domain".
2187 * If the domain of "node" is already a subset of "domain",
2188 * then nothing needs to be changed.
2190 * Otherwise, we replace the domain of the domain node by the intersection
2191 * and simplify the subtree rooted at "node" with respect to this intersection.
2193 __isl_give isl_schedule_node
*isl_schedule_node_domain_intersect_domain(
2194 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
)
2196 isl_schedule_tree
*tree
;
2197 isl_union_set
*uset
;
2200 if (!node
|| !domain
)
2203 uset
= isl_schedule_tree_domain_get_domain(node
->tree
);
2204 is_subset
= isl_union_set_is_subset(uset
, domain
);
2205 isl_union_set_free(uset
);
2209 isl_union_set_free(domain
);
2213 tree
= isl_schedule_tree_copy(node
->tree
);
2214 uset
= isl_schedule_tree_domain_get_domain(tree
);
2215 uset
= isl_union_set_intersect(uset
, domain
);
2216 tree
= isl_schedule_tree_domain_set_domain(tree
,
2217 isl_union_set_copy(uset
));
2218 node
= isl_schedule_node_graft_tree(node
, tree
);
2220 node
= isl_schedule_node_child(node
, 0);
2221 node
= isl_schedule_node_gist(node
, uset
);
2222 node
= isl_schedule_node_parent(node
);
2226 isl_schedule_node_free(node
);
2227 isl_union_set_free(domain
);
2231 /* Reset the user pointer on all identifiers of parameters and tuples
2232 * in the schedule node "node".
2234 __isl_give isl_schedule_node
*isl_schedule_node_reset_user(
2235 __isl_take isl_schedule_node
*node
)
2237 isl_schedule_tree
*tree
;
2239 tree
= isl_schedule_node_get_tree(node
);
2240 tree
= isl_schedule_tree_reset_user(tree
);
2241 node
= isl_schedule_node_graft_tree(node
, tree
);
2246 /* Align the parameters of the schedule node "node" to those of "space".
2248 __isl_give isl_schedule_node
*isl_schedule_node_align_params(
2249 __isl_take isl_schedule_node
*node
, __isl_take isl_space
*space
)
2251 isl_schedule_tree
*tree
;
2253 tree
= isl_schedule_node_get_tree(node
);
2254 tree
= isl_schedule_tree_align_params(tree
, space
);
2255 node
= isl_schedule_node_graft_tree(node
, tree
);
2260 /* Compute the pullback of schedule node "node"
2261 * by the function represented by "upma".
2262 * In other words, plug in "upma" in the iteration domains
2263 * of schedule node "node".
2265 * Note that this is only a helper function for
2266 * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency,
2267 * this function should not be called on a single node without also
2268 * calling it on all the other nodes.
2270 __isl_give isl_schedule_node
*isl_schedule_node_pullback_union_pw_multi_aff(
2271 __isl_take isl_schedule_node
*node
,
2272 __isl_take isl_union_pw_multi_aff
*upma
)
2274 isl_schedule_tree
*tree
;
2276 tree
= isl_schedule_node_get_tree(node
);
2277 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, upma
);
2278 node
= isl_schedule_node_graft_tree(node
, tree
);
2283 /* Return the position of the subtree containing "node" among the children
2284 * of "ancestor". "node" is assumed to be a descendant of "ancestor".
2285 * In particular, both nodes should point to the same schedule tree.
2287 * Return -1 on error.
2289 int isl_schedule_node_get_ancestor_child_position(
2290 __isl_keep isl_schedule_node
*node
,
2291 __isl_keep isl_schedule_node
*ancestor
)
2294 isl_schedule_tree
*tree
;
2296 if (!node
|| !ancestor
)
2299 if (node
->schedule
!= ancestor
->schedule
)
2300 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2301 "not a descendant", return -1);
2303 n1
= isl_schedule_node_get_tree_depth(ancestor
);
2304 n2
= isl_schedule_node_get_tree_depth(node
);
2307 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2308 "not a descendant", return -1);
2309 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n1
);
2310 isl_schedule_tree_free(tree
);
2311 if (tree
!= ancestor
->tree
)
2312 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2313 "not a descendant", return -1);
2315 return node
->child_pos
[n1
];
2318 /* Given two nodes that point to the same schedule tree, return their
2319 * closest shared ancestor.
2321 * Since the two nodes point to the same schedule, they share at least
2322 * one ancestor, the root of the schedule. We move down from the root
2323 * to the first ancestor where the respective children have a different
2324 * child position. This is the requested ancestor.
2325 * If there is no ancestor where the children have a different position,
2326 * then one node is an ancestor of the other and then this node is
2327 * the requested ancestor.
2329 __isl_give isl_schedule_node
*isl_schedule_node_get_shared_ancestor(
2330 __isl_keep isl_schedule_node
*node1
,
2331 __isl_keep isl_schedule_node
*node2
)
2335 if (!node1
|| !node2
)
2337 if (node1
->schedule
!= node2
->schedule
)
2338 isl_die(isl_schedule_node_get_ctx(node1
), isl_error_invalid
,
2339 "not part of same schedule", return NULL
);
2340 n1
= isl_schedule_node_get_tree_depth(node1
);
2341 n2
= isl_schedule_node_get_tree_depth(node2
);
2343 return isl_schedule_node_get_shared_ancestor(node2
, node1
);
2345 return isl_schedule_node_copy(node1
);
2346 if (isl_schedule_node_is_equal(node1
, node2
))
2347 return isl_schedule_node_copy(node1
);
2349 for (i
= 0; i
< n1
; ++i
)
2350 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
2353 node1
= isl_schedule_node_copy(node1
);
2354 return isl_schedule_node_ancestor(node1
, n1
- i
);
2357 /* Print "node" to "p".
2359 __isl_give isl_printer
*isl_printer_print_schedule_node(
2360 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
2363 return isl_printer_free(p
);
2364 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
,
2365 isl_schedule_tree_list_n_schedule_tree(node
->ancestors
),
2369 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
2372 isl_printer
*printer
;
2377 ctx
= isl_schedule_node_get_ctx(node
);
2378 printer
= isl_printer_to_file(ctx
, stderr
);
2379 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
2380 printer
= isl_printer_print_schedule_node(printer
, node
);
2382 isl_printer_free(printer
);