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 first "n"
427 * elements 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 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
)
447 for (i
= n
- 1; i
>= 0; --i
) {
448 isl_schedule_tree
*tree
;
451 tree
= isl_schedule_tree_list_get_schedule_tree(list
, i
);
454 if (!data
->initialized
)
455 r
= collect_filter_prefix_init(tree
, data
);
457 r
= collect_filter_prefix_update(tree
, data
);
458 isl_schedule_tree_free(tree
);
466 /* Return the concatenation of the partial schedules of all outer band
467 * nodes of "node" interesected with all outer filters
468 * as an isl_union_pw_multi_aff.
470 * If "node" is pointing at the root of the schedule tree, then
471 * there are no domain elements reaching the current node, so
472 * we return an empty result.
474 * We collect all the filters and partial schedules in collect_filter_prefix.
475 * The partial schedules are collected as an isl_multi_union_pw_aff.
476 * If this isl_multi_union_pw_aff is zero-dimensional, then it does not
477 * contain any domain information, so we construct the isl_union_pw_multi_aff
478 * result as a zero-dimensional function on the collected filter.
479 * Otherwise, we convert the isl_multi_union_pw_aff to
480 * an isl_multi_union_pw_aff and intersect the domain with the filter.
482 __isl_give isl_union_pw_multi_aff
*
483 isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(
484 __isl_keep isl_schedule_node
*node
)
488 isl_union_pw_multi_aff
*prefix
;
489 struct isl_schedule_node_get_filter_prefix_data data
;
494 space
= isl_schedule_get_space(node
->schedule
);
495 if (node
->tree
== node
->schedule
->root
)
496 return isl_union_pw_multi_aff_empty(space
);
498 space
= isl_space_set_from_params(space
);
499 data
.initialized
= 0;
500 data
.universe_domain
= 1;
501 data
.universe_filter
= 0;
502 data
.collect_prefix
= 1;
504 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
506 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
507 if (collect_filter_prefix(node
->ancestors
, n
, &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
)
550 struct isl_schedule_node_get_filter_prefix_data data
;
555 if (node
->tree
== node
->schedule
->root
) {
558 space
= isl_schedule_get_space(node
->schedule
);
559 return isl_union_set_empty(space
);
562 data
.initialized
= 0;
563 data
.universe_domain
= 0;
564 data
.universe_filter
= 0;
565 data
.collect_prefix
= 0;
569 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
570 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
571 data
.filter
= isl_union_set_free(data
.filter
);
576 /* Return the union of universe sets of the domain elements that reach "node".
578 * If "node" is pointing at the root of the schedule tree, then
579 * there are no domain elements reaching the current node, so
580 * we return an empty result.
582 * Otherwise, we collect the universes of all filters reaching the node
583 * in collect_filter_prefix.
585 __isl_give isl_union_set
*isl_schedule_node_get_universe_domain(
586 __isl_keep isl_schedule_node
*node
)
589 struct isl_schedule_node_get_filter_prefix_data data
;
594 if (node
->tree
== node
->schedule
->root
) {
597 space
= isl_schedule_get_space(node
->schedule
);
598 return isl_union_set_empty(space
);
601 data
.initialized
= 0;
602 data
.universe_domain
= 1;
603 data
.universe_filter
= 1;
604 data
.collect_prefix
= 0;
608 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
609 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
610 data
.filter
= isl_union_set_free(data
.filter
);
615 /* Return the subtree schedule of "node".
617 * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle
618 * trees that do not contain any schedule information, we first
619 * move down to the first relevant descendant and handle leaves ourselves.
621 __isl_give isl_union_map
*isl_schedule_node_get_subtree_schedule_union_map(
622 __isl_keep isl_schedule_node
*node
)
624 isl_schedule_tree
*tree
, *leaf
;
627 tree
= isl_schedule_node_get_tree(node
);
628 leaf
= isl_schedule_node_peek_leaf(node
);
629 tree
= isl_schedule_tree_first_schedule_descendant(tree
, leaf
);
633 isl_union_set
*domain
;
634 domain
= isl_schedule_node_get_universe_domain(node
);
635 isl_schedule_tree_free(tree
);
636 return isl_union_map_from_domain(domain
);
639 umap
= isl_schedule_tree_get_subtree_schedule_union_map(tree
);
640 isl_schedule_tree_free(tree
);
644 /* Return the number of ancestors of "node" in its schedule tree.
646 int isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node
*node
)
650 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
653 /* Does "node" have a parent?
655 * That is, does it point to any node of the schedule other than the root?
657 int isl_schedule_node_has_parent(__isl_keep isl_schedule_node
*node
)
661 if (!node
->ancestors
)
664 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) != 0;
667 /* Return the position of "node" among the children of its parent.
669 int isl_schedule_node_get_child_position(__isl_keep isl_schedule_node
*node
)
676 has_parent
= isl_schedule_node_has_parent(node
);
680 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
681 "node has no parent", return -1);
683 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
684 return node
->child_pos
[n
- 1];
687 /* Does the parent (if any) of "node" have any children with a smaller child
688 * position than this one?
690 int isl_schedule_node_has_previous_sibling(__isl_keep isl_schedule_node
*node
)
697 has_parent
= isl_schedule_node_has_parent(node
);
698 if (has_parent
< 0 || !has_parent
)
701 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
703 return node
->child_pos
[n
- 1] > 0;
706 /* Does the parent (if any) of "node" have any children with a greater child
707 * position than this one?
709 int isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node
*node
)
713 isl_schedule_tree
*tree
;
717 has_parent
= isl_schedule_node_has_parent(node
);
718 if (has_parent
< 0 || !has_parent
)
721 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
722 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
725 n_child
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
726 isl_schedule_tree_free(tree
);
728 return node
->child_pos
[n
- 1] + 1 < n_child
;
731 /* Does "node" have any children?
733 * Any node other than the leaf nodes is considered to have at least
734 * one child, even if the corresponding isl_schedule_tree does not
737 int isl_schedule_node_has_children(__isl_keep isl_schedule_node
*node
)
741 return !isl_schedule_tree_is_leaf(node
->tree
);
744 /* Return the number of children of "node"?
746 * Any node other than the leaf nodes is considered to have at least
747 * one child, even if the corresponding isl_schedule_tree does not
748 * have any children. That is, the number of children of "node" is
749 * only zero if its tree is the explicit empty tree. Otherwise,
750 * if the isl_schedule_tree has any children, then it is equal
751 * to the number of children of "node". If it has zero children,
752 * then "node" still has a leaf node as child.
754 int isl_schedule_node_n_children(__isl_keep isl_schedule_node
*node
)
761 if (isl_schedule_tree_is_leaf(node
->tree
))
764 n
= isl_schedule_tree_n_children(node
->tree
);
771 /* Move the "node" pointer to the ancestor of the given generation
772 * of the node it currently points to, where generation 0 is the node
773 * itself and generation 1 is its parent.
775 __isl_give isl_schedule_node
*isl_schedule_node_ancestor(
776 __isl_take isl_schedule_node
*node
, int generation
)
779 isl_schedule_tree
*tree
;
785 n
= isl_schedule_node_get_tree_depth(node
);
787 return isl_schedule_node_free(node
);
788 if (generation
< 0 || generation
> n
)
789 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
790 "generation out of bounds",
791 return isl_schedule_node_free(node
));
792 node
= isl_schedule_node_cow(node
);
796 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
798 isl_schedule_tree_free(node
->tree
);
800 node
->ancestors
= isl_schedule_tree_list_drop(node
->ancestors
,
801 n
- generation
, generation
);
802 if (!node
->ancestors
|| !node
->tree
)
803 return isl_schedule_node_free(node
);
808 /* Move the "node" pointer to the parent of the node it currently points to.
810 __isl_give isl_schedule_node
*isl_schedule_node_parent(
811 __isl_take isl_schedule_node
*node
)
815 if (!isl_schedule_node_has_parent(node
))
816 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
817 "node has no parent",
818 return isl_schedule_node_free(node
));
819 return isl_schedule_node_ancestor(node
, 1);
822 /* Move the "node" pointer to the root of its schedule tree.
824 __isl_give isl_schedule_node
*isl_schedule_node_root(
825 __isl_take isl_schedule_node
*node
)
831 n
= isl_schedule_node_get_tree_depth(node
);
833 return isl_schedule_node_free(node
);
834 return isl_schedule_node_ancestor(node
, n
);
837 /* Move the "node" pointer to the child at position "pos" of the node
838 * it currently points to.
840 __isl_give isl_schedule_node
*isl_schedule_node_child(
841 __isl_take isl_schedule_node
*node
, int pos
)
845 isl_schedule_tree
*tree
;
848 node
= isl_schedule_node_cow(node
);
851 if (!isl_schedule_node_has_children(node
))
852 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
853 "node has no children",
854 return isl_schedule_node_free(node
));
856 ctx
= isl_schedule_node_get_ctx(node
);
857 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
858 child_pos
= isl_realloc_array(ctx
, node
->child_pos
, int, n
+ 1);
860 return isl_schedule_node_free(node
);
861 node
->child_pos
= child_pos
;
862 node
->child_pos
[n
] = pos
;
864 node
->ancestors
= isl_schedule_tree_list_add(node
->ancestors
,
865 isl_schedule_tree_copy(node
->tree
));
867 if (isl_schedule_tree_has_children(tree
))
868 tree
= isl_schedule_tree_get_child(tree
, pos
);
870 tree
= isl_schedule_node_get_leaf(node
);
871 isl_schedule_tree_free(node
->tree
);
874 if (!node
->tree
|| !node
->ancestors
)
875 return isl_schedule_node_free(node
);
880 /* Move the "node" pointer to the first child of the node
881 * it currently points to.
883 __isl_give isl_schedule_node
*isl_schedule_node_first_child(
884 __isl_take isl_schedule_node
*node
)
886 return isl_schedule_node_child(node
, 0);
889 /* Move the "node" pointer to the child of this node's parent in
890 * the previous child position.
892 __isl_give isl_schedule_node
*isl_schedule_node_previous_sibling(
893 __isl_take isl_schedule_node
*node
)
896 isl_schedule_tree
*parent
, *tree
;
898 node
= isl_schedule_node_cow(node
);
901 if (!isl_schedule_node_has_previous_sibling(node
))
902 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
903 "node has no previous sibling",
904 return isl_schedule_node_free(node
));
906 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
907 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
910 return isl_schedule_node_free(node
);
911 node
->child_pos
[n
- 1]--;
912 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
913 node
->child_pos
[n
- 1]);
914 isl_schedule_tree_free(parent
);
916 return isl_schedule_node_free(node
);
917 isl_schedule_tree_free(node
->tree
);
923 /* Move the "node" pointer to the child of this node's parent in
924 * the next child position.
926 __isl_give isl_schedule_node
*isl_schedule_node_next_sibling(
927 __isl_take isl_schedule_node
*node
)
930 isl_schedule_tree
*parent
, *tree
;
932 node
= isl_schedule_node_cow(node
);
935 if (!isl_schedule_node_has_next_sibling(node
))
936 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
937 "node has no next sibling",
938 return isl_schedule_node_free(node
));
940 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
941 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
944 return isl_schedule_node_free(node
);
945 node
->child_pos
[n
- 1]++;
946 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
947 node
->child_pos
[n
- 1]);
948 isl_schedule_tree_free(parent
);
950 return isl_schedule_node_free(node
);
951 isl_schedule_tree_free(node
->tree
);
957 /* Return a copy to the child at position "pos" of "node".
959 __isl_give isl_schedule_node
*isl_schedule_node_get_child(
960 __isl_keep isl_schedule_node
*node
, int pos
)
962 return isl_schedule_node_child(isl_schedule_node_copy(node
), pos
);
965 /* Traverse the descendant of "node" in depth-first order, including
966 * "node" itself. Call "enter" whenever a node is entered and "leave"
967 * whenever a node is left. The callback "enter" is responsible
968 * for moving to the deepest initial subtree of its argument that
969 * should be traversed.
971 static __isl_give isl_schedule_node
*traverse(
972 __isl_take isl_schedule_node
*node
,
973 __isl_give isl_schedule_node
*(*enter
)(
974 __isl_take isl_schedule_node
*node
, void *user
),
975 __isl_give isl_schedule_node
*(*leave
)(
976 __isl_take isl_schedule_node
*node
, void *user
),
984 depth
= isl_schedule_node_get_tree_depth(node
);
986 node
= enter(node
, user
);
987 node
= leave(node
, user
);
988 while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
&&
989 !isl_schedule_node_has_next_sibling(node
)) {
990 node
= isl_schedule_node_parent(node
);
991 node
= leave(node
, user
);
993 if (node
&& isl_schedule_node_get_tree_depth(node
) > depth
)
994 node
= isl_schedule_node_next_sibling(node
);
995 } while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
);
1000 /* Internal data structure for isl_schedule_node_foreach_descendant.
1002 * "fn" is the user-specified callback function.
1003 * "user" is the user-specified argument for the callback.
1005 struct isl_schedule_node_preorder_data
{
1006 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
);
1010 /* Callback for "traverse" to enter a node and to move
1011 * to the deepest initial subtree that should be traversed
1012 * for use in a preorder visit.
1014 * If the user callback returns a negative value, then we abort
1015 * the traversal. If this callback returns zero, then we skip
1016 * the subtree rooted at the current node. Otherwise, we move
1017 * down to the first child and repeat the process until a leaf
1020 static __isl_give isl_schedule_node
*preorder_enter(
1021 __isl_take isl_schedule_node
*node
, void *user
)
1023 struct isl_schedule_node_preorder_data
*data
= user
;
1031 r
= data
->fn(node
, data
->user
);
1033 return isl_schedule_node_free(node
);
1036 } while (isl_schedule_node_has_children(node
) &&
1037 (node
= isl_schedule_node_first_child(node
)) != NULL
);
1042 /* Callback for "traverse" to leave a node
1043 * for use in a preorder visit.
1044 * Since we already visited the node when we entered it,
1045 * we do not need to do anything here.
1047 static __isl_give isl_schedule_node
*preorder_leave(
1048 __isl_take isl_schedule_node
*node
, void *user
)
1053 /* Traverse the descendants of "node" (including the node itself)
1054 * in depth first preorder.
1056 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1057 * If "fn" returns 0 on any of the nodes, then the subtree rooted
1058 * at that node is skipped.
1060 * Return 0 on success and -1 on failure.
1062 int isl_schedule_node_foreach_descendant(__isl_keep isl_schedule_node
*node
,
1063 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
), void *user
)
1065 struct isl_schedule_node_preorder_data data
= { fn
, user
};
1067 node
= isl_schedule_node_copy(node
);
1068 node
= traverse(node
, &preorder_enter
, &preorder_leave
, &data
);
1069 isl_schedule_node_free(node
);
1071 return node
? 0 : -1;
1074 /* Internal data structure for isl_schedule_node_map_descendant.
1076 * "fn" is the user-specified callback function.
1077 * "user" is the user-specified argument for the callback.
1079 struct isl_schedule_node_postorder_data
{
1080 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1085 /* Callback for "traverse" to enter a node and to move
1086 * to the deepest initial subtree that should be traversed
1087 * for use in a postorder visit.
1089 * Since we are performing a postorder visit, we only need
1090 * to move to the deepest initial leaf here.
1092 static __isl_give isl_schedule_node
*postorder_enter(
1093 __isl_take isl_schedule_node
*node
, void *user
)
1095 while (node
&& isl_schedule_node_has_children(node
))
1096 node
= isl_schedule_node_first_child(node
);
1101 /* Callback for "traverse" to leave a node
1102 * for use in a postorder visit.
1104 * Since we are performing a postorder visit, we need
1105 * to call the user callback here.
1107 static __isl_give isl_schedule_node
*postorder_leave(
1108 __isl_take isl_schedule_node
*node
, void *user
)
1110 struct isl_schedule_node_postorder_data
*data
= user
;
1112 return data
->fn(node
, data
->user
);
1115 /* Traverse the descendants of "node" (including the node itself)
1116 * in depth first postorder, allowing the user to modify the visited node.
1117 * The traversal continues from the node returned by the callback function.
1118 * It is the responsibility of the user to ensure that this does not
1119 * lead to an infinite loop. It is safest to always return a pointer
1120 * to the same position (same ancestors and child positions) as the input node.
1122 __isl_give isl_schedule_node
*isl_schedule_node_map_descendant(
1123 __isl_take isl_schedule_node
*node
,
1124 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1125 void *user
), void *user
)
1127 struct isl_schedule_node_postorder_data data
= { fn
, user
};
1129 return traverse(node
, &postorder_enter
, &postorder_leave
, &data
);
1132 /* Traverse the ancestors of "node" from the root down to and including
1133 * the parent of "node", calling "fn" on each of them.
1135 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1137 * Return 0 on success and -1 on failure.
1139 int isl_schedule_node_foreach_ancestor_top_down(
1140 __isl_keep isl_schedule_node
*node
,
1141 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
), void *user
)
1148 n
= isl_schedule_node_get_tree_depth(node
);
1149 for (i
= 0; i
< n
; ++i
) {
1150 isl_schedule_node
*ancestor
;
1153 ancestor
= isl_schedule_node_copy(node
);
1154 ancestor
= isl_schedule_node_ancestor(ancestor
, n
- i
);
1155 r
= fn(ancestor
, user
);
1156 isl_schedule_node_free(ancestor
);
1164 /* Is any node in the subtree rooted at "node" anchored?
1165 * That is, do any of these nodes reference the outer band nodes?
1167 int isl_schedule_node_is_subtree_anchored(__isl_keep isl_schedule_node
*node
)
1171 return isl_schedule_tree_is_subtree_anchored(node
->tree
);
1174 /* Return the number of members in the given band node.
1176 unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node
*node
)
1178 return node
? isl_schedule_tree_band_n_member(node
->tree
) : 0;
1181 /* Is the band member at position "pos" of the band node "node"
1182 * marked coincident?
1184 int isl_schedule_node_band_member_get_coincident(
1185 __isl_keep isl_schedule_node
*node
, int pos
)
1189 return isl_schedule_tree_band_member_get_coincident(node
->tree
, pos
);
1192 /* Mark the band member at position "pos" the band node "node"
1193 * as being coincident or not according to "coincident".
1195 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_coincident(
1196 __isl_take isl_schedule_node
*node
, int pos
, int coincident
)
1199 isl_schedule_tree
*tree
;
1203 c
= isl_schedule_node_band_member_get_coincident(node
, pos
);
1204 if (c
== coincident
)
1207 tree
= isl_schedule_tree_copy(node
->tree
);
1208 tree
= isl_schedule_tree_band_member_set_coincident(tree
, pos
,
1210 node
= isl_schedule_node_graft_tree(node
, tree
);
1215 /* Is the band node "node" marked permutable?
1217 int isl_schedule_node_band_get_permutable(__isl_keep isl_schedule_node
*node
)
1222 return isl_schedule_tree_band_get_permutable(node
->tree
);
1225 /* Mark the band node "node" permutable or not according to "permutable"?
1227 __isl_give isl_schedule_node
*isl_schedule_node_band_set_permutable(
1228 __isl_take isl_schedule_node
*node
, int permutable
)
1230 isl_schedule_tree
*tree
;
1234 if (isl_schedule_node_band_get_permutable(node
) == permutable
)
1237 tree
= isl_schedule_tree_copy(node
->tree
);
1238 tree
= isl_schedule_tree_band_set_permutable(tree
, permutable
);
1239 node
= isl_schedule_node_graft_tree(node
, tree
);
1244 /* Return the schedule space of the band node.
1246 __isl_give isl_space
*isl_schedule_node_band_get_space(
1247 __isl_keep isl_schedule_node
*node
)
1252 return isl_schedule_tree_band_get_space(node
->tree
);
1255 /* Return the schedule of the band node in isolation.
1257 __isl_give isl_multi_union_pw_aff
*isl_schedule_node_band_get_partial_schedule(
1258 __isl_keep isl_schedule_node
*node
)
1263 return isl_schedule_tree_band_get_partial_schedule(node
->tree
);
1266 /* Return the schedule of the band node in isolation in the form of
1269 * If the band does not have any members, then we construct a universe map
1270 * with the universe of the domain elements reaching the node as domain.
1271 * Otherwise, we extract an isl_multi_union_pw_aff representation and
1272 * convert that to an isl_union_map.
1274 __isl_give isl_union_map
*isl_schedule_node_band_get_partial_schedule_union_map(
1275 __isl_keep isl_schedule_node
*node
)
1277 isl_multi_union_pw_aff
*mupa
;
1282 if (isl_schedule_node_get_type(node
) != isl_schedule_node_band
)
1283 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1284 "not a band node", return NULL
);
1285 if (isl_schedule_node_band_n_member(node
) == 0) {
1286 isl_union_set
*domain
;
1288 domain
= isl_schedule_node_get_universe_domain(node
);
1289 return isl_union_map_from_domain(domain
);
1292 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
1293 return isl_union_map_from_multi_union_pw_aff(mupa
);
1296 /* Return the loop AST generation type for the band member of band node "node"
1297 * at position "pos".
1299 enum isl_ast_loop_type
isl_schedule_node_band_member_get_ast_loop_type(
1300 __isl_keep isl_schedule_node
*node
, int pos
)
1303 return isl_ast_loop_error
;
1305 return isl_schedule_tree_band_member_get_ast_loop_type(node
->tree
, pos
);
1308 /* Set the loop AST generation type for the band member of band node "node"
1309 * at position "pos" to "type".
1311 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_ast_loop_type(
1312 __isl_take isl_schedule_node
*node
, int pos
,
1313 enum isl_ast_loop_type type
)
1315 isl_schedule_tree
*tree
;
1320 tree
= isl_schedule_tree_copy(node
->tree
);
1321 tree
= isl_schedule_tree_band_member_set_ast_loop_type(tree
, pos
, type
);
1322 return isl_schedule_node_graft_tree(node
, tree
);
1325 /* Return the loop AST generation type for the band member of band node "node"
1326 * at position "pos" for the isolated part.
1328 enum isl_ast_loop_type
isl_schedule_node_band_member_get_isolate_ast_loop_type(
1329 __isl_keep isl_schedule_node
*node
, int pos
)
1332 return isl_ast_loop_error
;
1334 return isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1338 /* Set the loop AST generation type for the band member of band node "node"
1339 * at position "pos" for the isolated part to "type".
1341 __isl_give isl_schedule_node
*
1342 isl_schedule_node_band_member_set_isolate_ast_loop_type(
1343 __isl_take isl_schedule_node
*node
, int pos
,
1344 enum isl_ast_loop_type type
)
1346 isl_schedule_tree
*tree
;
1351 tree
= isl_schedule_tree_copy(node
->tree
);
1352 tree
= isl_schedule_tree_band_member_set_isolate_ast_loop_type(tree
,
1354 return isl_schedule_node_graft_tree(node
, tree
);
1357 /* Return the AST build options associated to band node "node".
1359 __isl_give isl_union_set
*isl_schedule_node_band_get_ast_build_options(
1360 __isl_keep isl_schedule_node
*node
)
1365 return isl_schedule_tree_band_get_ast_build_options(node
->tree
);
1368 /* Replace the AST build options associated to band node "node" by "options".
1370 __isl_give isl_schedule_node
*isl_schedule_node_band_set_ast_build_options(
1371 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*options
)
1373 isl_schedule_tree
*tree
;
1375 if (!node
|| !options
)
1378 tree
= isl_schedule_tree_copy(node
->tree
);
1379 tree
= isl_schedule_tree_band_set_ast_build_options(tree
, options
);
1380 return isl_schedule_node_graft_tree(node
, tree
);
1382 isl_schedule_node_free(node
);
1383 isl_union_set_free(options
);
1387 /* Make sure that that spaces of "node" and "mv" are the same.
1388 * Return -1 on error, reporting the error to the user.
1390 static int check_space_multi_val(__isl_keep isl_schedule_node
*node
,
1391 __isl_keep isl_multi_val
*mv
)
1393 isl_space
*node_space
, *mv_space
;
1396 node_space
= isl_schedule_node_band_get_space(node
);
1397 mv_space
= isl_multi_val_get_space(mv
);
1398 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1399 mv_space
, isl_dim_set
);
1400 isl_space_free(mv_space
);
1401 isl_space_free(node_space
);
1405 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1406 "spaces don't match", return -1);
1411 /* Multiply the partial schedule of the band node "node"
1412 * with the factors in "mv".
1414 __isl_give isl_schedule_node
*isl_schedule_node_band_scale(
1415 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1417 isl_schedule_tree
*tree
;
1422 if (check_space_multi_val(node
, mv
) < 0)
1424 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1428 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1429 "cannot scale band node with anchored subtree",
1432 tree
= isl_schedule_node_get_tree(node
);
1433 tree
= isl_schedule_tree_band_scale(tree
, mv
);
1434 return isl_schedule_node_graft_tree(node
, tree
);
1436 isl_multi_val_free(mv
);
1437 isl_schedule_node_free(node
);
1441 /* Divide the partial schedule of the band node "node"
1442 * by the factors in "mv".
1444 __isl_give isl_schedule_node
*isl_schedule_node_band_scale_down(
1445 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1447 isl_schedule_tree
*tree
;
1452 if (check_space_multi_val(node
, mv
) < 0)
1454 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1458 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1459 "cannot scale down band node with anchored subtree",
1462 tree
= isl_schedule_node_get_tree(node
);
1463 tree
= isl_schedule_tree_band_scale_down(tree
, mv
);
1464 return isl_schedule_node_graft_tree(node
, tree
);
1466 isl_multi_val_free(mv
);
1467 isl_schedule_node_free(node
);
1471 /* Tile "node" with tile sizes "sizes".
1473 * The current node is replaced by two nested nodes corresponding
1474 * to the tile dimensions and the point dimensions.
1476 * Return a pointer to the outer (tile) node.
1478 * If any of the descendants of "node" depend on the set of outer band nodes,
1479 * then we refuse to tile the node.
1481 * If the scale tile loops option is set, then the tile loops
1482 * are scaled by the tile sizes. If the shift point loops option is set,
1483 * then the point loops are shifted to start at zero.
1484 * In particular, these options affect the tile and point loop schedules
1487 * scale shift original tile point
1489 * 0 0 i floor(i/s) i
1490 * 1 0 i s * floor(i/s) i
1491 * 0 1 i floor(i/s) i - s * floor(i/s)
1492 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1494 __isl_give isl_schedule_node
*isl_schedule_node_band_tile(
1495 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*sizes
)
1497 isl_schedule_tree
*tree
;
1500 if (!node
|| !sizes
)
1502 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1506 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1507 "cannot tile band node with anchored subtree",
1510 if (check_space_multi_val(node
, sizes
) < 0)
1513 tree
= isl_schedule_node_get_tree(node
);
1514 tree
= isl_schedule_tree_band_tile(tree
, sizes
);
1515 return isl_schedule_node_graft_tree(node
, tree
);
1517 isl_multi_val_free(sizes
);
1518 isl_schedule_node_free(node
);
1522 /* Move the band node "node" down to all the leaves in the subtree
1524 * Return a pointer to the node in the resulting tree that is in the same
1525 * position as the node pointed to by "node" in the original tree.
1527 * If the node only has a leaf child, then nothing needs to be done.
1528 * Otherwise, the child of the node is removed and the result is
1529 * appended to all the leaves in the subtree rooted at the original child.
1530 * The original node is then replaced by the result of this operation.
1532 * If any of the nodes in the subtree rooted at "node" depend on
1533 * the set of outer band nodes then we refuse to sink the band node.
1535 __isl_give isl_schedule_node
*isl_schedule_node_band_sink(
1536 __isl_take isl_schedule_node
*node
)
1538 enum isl_schedule_node_type type
;
1539 isl_schedule_tree
*tree
, *child
;
1545 type
= isl_schedule_node_get_type(node
);
1546 if (type
!= isl_schedule_node_band
)
1547 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1548 "not a band node", isl_schedule_node_free(node
));
1549 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1551 return isl_schedule_node_free(node
);
1553 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1554 "cannot sink band node in anchored subtree",
1555 isl_schedule_node_free(node
));
1556 if (isl_schedule_tree_n_children(node
->tree
) == 0)
1559 tree
= isl_schedule_node_get_tree(node
);
1560 child
= isl_schedule_tree_get_child(tree
, 0);
1561 tree
= isl_schedule_tree_reset_children(tree
);
1562 tree
= isl_schedule_tree_append_to_leaves(child
, tree
);
1564 return isl_schedule_node_graft_tree(node
, tree
);
1567 /* Split "node" into two nested band nodes, one with the first "pos"
1568 * dimensions and one with the remaining dimensions.
1569 * The schedules of the two band nodes live in anonymous spaces.
1571 __isl_give isl_schedule_node
*isl_schedule_node_band_split(
1572 __isl_take isl_schedule_node
*node
, int pos
)
1574 isl_schedule_tree
*tree
;
1576 tree
= isl_schedule_node_get_tree(node
);
1577 tree
= isl_schedule_tree_band_split(tree
, pos
);
1578 return isl_schedule_node_graft_tree(node
, tree
);
1581 /* Return the context of the context node "node".
1583 __isl_give isl_set
*isl_schedule_node_context_get_context(
1584 __isl_keep isl_schedule_node
*node
)
1589 return isl_schedule_tree_context_get_context(node
->tree
);
1592 /* Return the domain of the domain node "node".
1594 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
1595 __isl_keep isl_schedule_node
*node
)
1600 return isl_schedule_tree_domain_get_domain(node
->tree
);
1603 /* Return the filter of the filter node "node".
1605 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
1606 __isl_keep isl_schedule_node
*node
)
1611 return isl_schedule_tree_filter_get_filter(node
->tree
);
1614 /* Replace the filter of filter node "node" by "filter".
1616 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
1617 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
1619 isl_schedule_tree
*tree
;
1621 if (!node
|| !filter
)
1624 tree
= isl_schedule_tree_copy(node
->tree
);
1625 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
1626 return isl_schedule_node_graft_tree(node
, tree
);
1628 isl_schedule_node_free(node
);
1629 isl_union_set_free(filter
);
1633 /* Update the ancestors of "node" to point to the tree that "node"
1635 * That is, replace the child in the original parent that corresponds
1636 * to the current tree position by node->tree and continue updating
1637 * the ancestors in the same way until the root is reached.
1639 * If "node" originally points to a leaf of the schedule tree, then make sure
1640 * that in the end it points to a leaf in the updated schedule tree.
1642 static __isl_give isl_schedule_node
*update_ancestors(
1643 __isl_take isl_schedule_node
*node
)
1648 isl_schedule_tree
*tree
;
1650 node
= isl_schedule_node_cow(node
);
1654 ctx
= isl_schedule_node_get_ctx(node
);
1655 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1656 tree
= isl_schedule_tree_copy(node
->tree
);
1658 for (i
= n
- 1; i
>= 0; --i
) {
1659 isl_schedule_tree
*parent
;
1661 parent
= isl_schedule_tree_list_get_schedule_tree(
1662 node
->ancestors
, i
);
1663 parent
= isl_schedule_tree_replace_child(parent
,
1664 node
->child_pos
[i
], tree
);
1665 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
1666 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
1671 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
1672 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
1674 isl_schedule_tree_free(node
->tree
);
1675 node
->tree
= isl_schedule_node_get_leaf(node
);
1678 if (!node
->schedule
|| !node
->ancestors
)
1679 return isl_schedule_node_free(node
);
1684 /* Replace the subtree that "pos" points to by "tree", updating
1685 * the ancestors to maintain a consistent state.
1687 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
1688 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
1692 if (pos
->tree
== tree
) {
1693 isl_schedule_tree_free(tree
);
1697 pos
= isl_schedule_node_cow(pos
);
1701 isl_schedule_tree_free(pos
->tree
);
1704 return update_ancestors(pos
);
1706 isl_schedule_node_free(pos
);
1707 isl_schedule_tree_free(tree
);
1711 /* Make sure we can insert a node between "node" and its parent.
1712 * Return -1 on error, reporting the reason why we cannot insert a node.
1714 static int check_insert(__isl_keep isl_schedule_node
*node
)
1717 enum isl_schedule_node_type type
;
1719 has_parent
= isl_schedule_node_has_parent(node
);
1723 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1724 "cannot insert node outside of root", return -1);
1726 type
= isl_schedule_node_get_parent_type(node
);
1727 if (type
== isl_schedule_node_error
)
1729 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
1730 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1731 "cannot insert node between set or sequence node "
1732 "and its filter children", return -1);
1737 /* Insert a band node with partial schedule "mupa" between "node" and
1739 * Return a pointer to the new band node.
1741 * If any of the nodes in the subtree rooted at "node" depend on
1742 * the set of outer band nodes then we refuse to insert the band node.
1744 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
1745 __isl_take isl_schedule_node
*node
,
1746 __isl_take isl_multi_union_pw_aff
*mupa
)
1749 isl_schedule_band
*band
;
1750 isl_schedule_tree
*tree
;
1752 if (check_insert(node
) < 0)
1753 node
= isl_schedule_node_free(node
);
1754 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1758 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1759 "cannot insert band node in anchored subtree",
1762 tree
= isl_schedule_node_get_tree(node
);
1763 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
1764 tree
= isl_schedule_tree_insert_band(tree
, band
);
1765 node
= isl_schedule_node_graft_tree(node
, tree
);
1769 isl_schedule_node_free(node
);
1770 isl_multi_union_pw_aff_free(mupa
);
1774 /* Insert a context node with context "context" between "node" and its parent.
1775 * Return a pointer to the new context node.
1777 __isl_give isl_schedule_node
*isl_schedule_node_insert_context(
1778 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
1780 isl_schedule_tree
*tree
;
1782 if (check_insert(node
) < 0)
1783 node
= isl_schedule_node_free(node
);
1785 tree
= isl_schedule_node_get_tree(node
);
1786 tree
= isl_schedule_tree_insert_context(tree
, context
);
1787 node
= isl_schedule_node_graft_tree(node
, tree
);
1792 /* Insert a filter node with filter "filter" between "node" and its parent.
1793 * Return a pointer to the new filter node.
1795 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
1796 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
1798 isl_schedule_tree
*tree
;
1800 if (check_insert(node
) < 0)
1801 node
= isl_schedule_node_free(node
);
1803 tree
= isl_schedule_node_get_tree(node
);
1804 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
1805 node
= isl_schedule_node_graft_tree(node
, tree
);
1810 /* Attach the current subtree of "node" to a sequence of filter tree nodes
1811 * with filters described by "filters", attach this sequence
1812 * of filter tree nodes as children to a new tree of type "type" and
1813 * replace the original subtree of "node" by this new tree.
1815 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
1816 __isl_take isl_schedule_node
*node
,
1817 enum isl_schedule_node_type type
,
1818 __isl_take isl_union_set_list
*filters
)
1822 isl_schedule_tree
*tree
;
1823 isl_schedule_tree_list
*list
;
1825 if (check_insert(node
) < 0)
1826 node
= isl_schedule_node_free(node
);
1828 if (!node
|| !filters
)
1831 ctx
= isl_schedule_node_get_ctx(node
);
1832 n
= isl_union_set_list_n_union_set(filters
);
1833 list
= isl_schedule_tree_list_alloc(ctx
, n
);
1834 for (i
= 0; i
< n
; ++i
) {
1835 isl_schedule_tree
*tree
;
1836 isl_union_set
*filter
;
1838 tree
= isl_schedule_node_get_tree(node
);
1839 filter
= isl_union_set_list_get_union_set(filters
, i
);
1840 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
1841 list
= isl_schedule_tree_list_add(list
, tree
);
1843 tree
= isl_schedule_tree_from_children(type
, list
);
1844 node
= isl_schedule_node_graft_tree(node
, tree
);
1846 isl_union_set_list_free(filters
);
1849 isl_union_set_list_free(filters
);
1850 isl_schedule_node_free(node
);
1854 /* Insert a sequence node with child filters "filters" between "node" and
1855 * its parent. That is, the tree that "node" points to is attached
1856 * to each of the child nodes of the filter nodes.
1857 * Return a pointer to the new sequence node.
1859 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
1860 __isl_take isl_schedule_node
*node
,
1861 __isl_take isl_union_set_list
*filters
)
1863 return isl_schedule_node_insert_children(node
,
1864 isl_schedule_node_sequence
, filters
);
1867 /* Insert a set node with child filters "filters" between "node" and
1868 * its parent. That is, the tree that "node" points to is attached
1869 * to each of the child nodes of the filter nodes.
1870 * Return a pointer to the new set node.
1872 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
1873 __isl_take isl_schedule_node
*node
,
1874 __isl_take isl_union_set_list
*filters
)
1876 return isl_schedule_node_insert_children(node
,
1877 isl_schedule_node_set
, filters
);
1880 /* Remove "node" from its schedule tree and return a pointer
1881 * to the leaf at the same position in the updated schedule tree.
1883 * It is not allowed to remove the root of a schedule tree or
1884 * a child of a set or sequence node.
1886 __isl_give isl_schedule_node
*isl_schedule_node_cut(
1887 __isl_take isl_schedule_node
*node
)
1889 isl_schedule_tree
*leaf
;
1890 enum isl_schedule_node_type parent_type
;
1894 if (!isl_schedule_node_has_parent(node
))
1895 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1896 "cannot cut root", return isl_schedule_node_free(node
));
1898 parent_type
= isl_schedule_node_get_parent_type(node
);
1899 if (parent_type
== isl_schedule_node_set
||
1900 parent_type
== isl_schedule_node_sequence
)
1901 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1902 "cannot cut child of set or sequence",
1903 return isl_schedule_node_free(node
));
1905 leaf
= isl_schedule_node_get_leaf(node
);
1906 return isl_schedule_node_graft_tree(node
, leaf
);
1909 /* Remove a single node from the schedule tree, attaching the child
1910 * of "node" directly to its parent.
1911 * Return a pointer to this former child or to the leaf the position
1912 * of the original node if there was no child.
1913 * It is not allowed to remove the root of a schedule tree,
1914 * a set or sequence node, a child of a set or sequence node or
1915 * a band node with an anchored subtree.
1917 __isl_give isl_schedule_node
*isl_schedule_node_delete(
1918 __isl_take isl_schedule_node
*node
)
1921 isl_schedule_tree
*tree
;
1922 enum isl_schedule_node_type type
;
1927 if (isl_schedule_node_get_tree_depth(node
) == 0)
1928 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1929 "cannot delete root node",
1930 return isl_schedule_node_free(node
));
1931 n
= isl_schedule_node_n_children(node
);
1933 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1934 "can only delete node with a single child",
1935 return isl_schedule_node_free(node
));
1936 type
= isl_schedule_node_get_parent_type(node
);
1937 if (type
== isl_schedule_node_sequence
|| type
== isl_schedule_node_set
)
1938 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1939 "cannot delete child of set or sequence",
1940 return isl_schedule_node_free(node
));
1941 if (isl_schedule_node_get_type(node
) == isl_schedule_node_band
) {
1944 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1946 return isl_schedule_node_free(node
);
1948 isl_die(isl_schedule_node_get_ctx(node
),
1950 "cannot delete band node with anchored subtree",
1951 return isl_schedule_node_free(node
));
1954 tree
= isl_schedule_node_get_tree(node
);
1955 if (!tree
|| isl_schedule_tree_has_children(tree
)) {
1956 tree
= isl_schedule_tree_child(tree
, 0);
1958 isl_schedule_tree_free(tree
);
1959 tree
= isl_schedule_node_get_leaf(node
);
1961 node
= isl_schedule_node_graft_tree(node
, tree
);
1966 /* Compute the gist of the given band node with respect to "context".
1968 __isl_give isl_schedule_node
*isl_schedule_node_band_gist(
1969 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
1971 isl_schedule_tree
*tree
;
1973 tree
= isl_schedule_node_get_tree(node
);
1974 tree
= isl_schedule_tree_band_gist(tree
, context
);
1975 return isl_schedule_node_graft_tree(node
, tree
);
1978 /* Internal data structure for isl_schedule_node_gist.
1979 * "filters" contains an element for each outer filter node
1980 * with respect to the current position, each representing
1981 * the intersection of the previous element and the filter on the filter node.
1982 * The first element in the original context passed to isl_schedule_node_gist.
1984 struct isl_node_gist_data
{
1985 isl_union_set_list
*filters
;
1988 /* Can we finish gisting at this node?
1989 * That is, is the filter on the current filter node a subset of
1990 * the original context passed to isl_schedule_node_gist?
1992 static int gist_done(__isl_keep isl_schedule_node
*node
,
1993 struct isl_node_gist_data
*data
)
1995 isl_union_set
*filter
, *outer
;
1998 filter
= isl_schedule_node_filter_get_filter(node
);
1999 outer
= isl_union_set_list_get_union_set(data
->filters
, 0);
2000 subset
= isl_union_set_is_subset(filter
, outer
);
2001 isl_union_set_free(outer
);
2002 isl_union_set_free(filter
);
2007 /* Callback for "traverse" to enter a node and to move
2008 * to the deepest initial subtree that should be traversed
2009 * by isl_schedule_node_gist.
2011 * The "filters" list is extended by one element each time
2012 * we come across a filter node by the result of intersecting
2013 * the last element in the list with the filter on the filter node.
2015 * If the filter on the current filter node is a subset of
2016 * the original context passed to isl_schedule_node_gist,
2017 * then there is no need to go into its subtree since it cannot
2018 * be further simplified by the context. The "filters" list is
2019 * still extended for consistency, but the actual value of the
2020 * added element is immaterial since it will not be used.
2022 * Otherwise, the filter on the current filter node is replaced by
2023 * the gist of the original filter with respect to the intersection
2024 * of the original context with the intermediate filters.
2026 * If the new element in the "filters" list is empty, then no elements
2027 * can reach the descendants of the current filter node. The subtree
2028 * underneath the filter node is therefore removed.
2030 static __isl_give isl_schedule_node
*gist_enter(
2031 __isl_take isl_schedule_node
*node
, void *user
)
2033 struct isl_node_gist_data
*data
= user
;
2036 isl_union_set
*filter
, *inner
;
2040 switch (isl_schedule_node_get_type(node
)) {
2041 case isl_schedule_node_error
:
2042 return isl_schedule_node_free(node
);
2043 case isl_schedule_node_band
:
2044 case isl_schedule_node_context
:
2045 case isl_schedule_node_domain
:
2046 case isl_schedule_node_leaf
:
2047 case isl_schedule_node_sequence
:
2048 case isl_schedule_node_set
:
2050 case isl_schedule_node_filter
:
2053 done
= gist_done(node
, data
);
2054 filter
= isl_schedule_node_filter_get_filter(node
);
2055 if (done
< 0 || done
) {
2056 data
->filters
= isl_union_set_list_add(data
->filters
,
2059 return isl_schedule_node_free(node
);
2062 n
= isl_union_set_list_n_union_set(data
->filters
);
2063 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
2064 filter
= isl_union_set_gist(filter
, isl_union_set_copy(inner
));
2065 node
= isl_schedule_node_filter_set_filter(node
,
2066 isl_union_set_copy(filter
));
2067 filter
= isl_union_set_intersect(filter
, inner
);
2068 empty
= isl_union_set_is_empty(filter
);
2069 data
->filters
= isl_union_set_list_add(data
->filters
, filter
);
2071 return isl_schedule_node_free(node
);
2074 node
= isl_schedule_node_child(node
, 0);
2075 node
= isl_schedule_node_cut(node
);
2076 node
= isl_schedule_node_parent(node
);
2078 } while (isl_schedule_node_has_children(node
) &&
2079 (node
= isl_schedule_node_first_child(node
)) != NULL
);
2084 /* Callback for "traverse" to leave a node for isl_schedule_node_gist.
2086 * In particular, if the current node is a filter node, then we remove
2087 * the element on the "filters" list that was added when we entered
2088 * the node. There is no need to compute any gist here, since we
2089 * already did that when we entered the node.
2091 * If the current node is a band node, then we compute the gist of
2092 * the band node with respect to the intersection of the original context
2093 * and the intermediate filters.
2095 * If the current node is a sequence or set node, then some of
2096 * the filter children may have become empty and so they are removed.
2097 * If only one child is left, then the set or sequence node along with
2098 * the single remaining child filter is removed. The filter can be
2099 * removed because the filters on a sequence or set node are supposed
2100 * to partition the incoming domain instances.
2101 * In principle, it should then be impossible for there to be zero
2102 * remaining children, but should this happen, we replace the entire
2103 * subtree with an empty filter.
2105 static __isl_give isl_schedule_node
*gist_leave(
2106 __isl_take isl_schedule_node
*node
, void *user
)
2108 struct isl_node_gist_data
*data
= user
;
2109 isl_schedule_tree
*tree
;
2111 isl_union_set
*filter
;
2113 switch (isl_schedule_node_get_type(node
)) {
2114 case isl_schedule_node_error
:
2115 return isl_schedule_node_free(node
);
2116 case isl_schedule_node_filter
:
2117 n
= isl_union_set_list_n_union_set(data
->filters
);
2118 data
->filters
= isl_union_set_list_drop(data
->filters
,
2121 case isl_schedule_node_band
:
2122 n
= isl_union_set_list_n_union_set(data
->filters
);
2123 filter
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
2124 node
= isl_schedule_node_band_gist(node
, filter
);
2126 case isl_schedule_node_set
:
2127 case isl_schedule_node_sequence
:
2128 tree
= isl_schedule_node_get_tree(node
);
2129 n
= isl_schedule_tree_n_children(tree
);
2130 for (i
= n
- 1; i
>= 0; --i
) {
2131 isl_schedule_tree
*child
;
2132 isl_union_set
*filter
;
2135 child
= isl_schedule_tree_get_child(tree
, i
);
2136 filter
= isl_schedule_tree_filter_get_filter(child
);
2137 empty
= isl_union_set_is_empty(filter
);
2138 isl_union_set_free(filter
);
2139 isl_schedule_tree_free(child
);
2141 tree
= isl_schedule_tree_free(tree
);
2143 tree
= isl_schedule_tree_drop_child(tree
, i
);
2145 n
= isl_schedule_tree_n_children(tree
);
2146 node
= isl_schedule_node_graft_tree(node
, tree
);
2148 node
= isl_schedule_node_delete(node
);
2149 node
= isl_schedule_node_delete(node
);
2150 } else if (n
== 0) {
2154 isl_union_set_list_get_union_set(data
->filters
, 0);
2155 space
= isl_union_set_get_space(filter
);
2156 isl_union_set_free(filter
);
2157 filter
= isl_union_set_empty(space
);
2158 node
= isl_schedule_node_cut(node
);
2159 node
= isl_schedule_node_insert_filter(node
, filter
);
2162 case isl_schedule_node_context
:
2163 case isl_schedule_node_domain
:
2164 case isl_schedule_node_leaf
:
2171 /* Compute the gist of the subtree at "node" with respect to
2172 * the reaching domain elements in "context".
2173 * In particular, compute the gist of all band and filter nodes
2174 * in the subtree with respect to "context". Children of set or sequence
2175 * nodes that end up with an empty filter are removed completely.
2177 * We keep track of the intersection of "context" with all outer filters
2178 * of the current node within the subtree in the final element of "filters".
2179 * Initially, this list contains the single element "context" and it is
2180 * extended or shortened each time we enter or leave a filter node.
2182 __isl_give isl_schedule_node
*isl_schedule_node_gist(
2183 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
2185 struct isl_node_gist_data data
;
2187 data
.filters
= isl_union_set_list_from_union_set(context
);
2188 node
= traverse(node
, &gist_enter
, &gist_leave
, &data
);
2189 isl_union_set_list_free(data
.filters
);
2193 /* Intersect the domain of domain node "node" with "domain".
2195 * If the domain of "node" is already a subset of "domain",
2196 * then nothing needs to be changed.
2198 * Otherwise, we replace the domain of the domain node by the intersection
2199 * and simplify the subtree rooted at "node" with respect to this intersection.
2201 __isl_give isl_schedule_node
*isl_schedule_node_domain_intersect_domain(
2202 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
)
2204 isl_schedule_tree
*tree
;
2205 isl_union_set
*uset
;
2208 if (!node
|| !domain
)
2211 uset
= isl_schedule_tree_domain_get_domain(node
->tree
);
2212 is_subset
= isl_union_set_is_subset(uset
, domain
);
2213 isl_union_set_free(uset
);
2217 isl_union_set_free(domain
);
2221 tree
= isl_schedule_tree_copy(node
->tree
);
2222 uset
= isl_schedule_tree_domain_get_domain(tree
);
2223 uset
= isl_union_set_intersect(uset
, domain
);
2224 tree
= isl_schedule_tree_domain_set_domain(tree
,
2225 isl_union_set_copy(uset
));
2226 node
= isl_schedule_node_graft_tree(node
, tree
);
2228 node
= isl_schedule_node_child(node
, 0);
2229 node
= isl_schedule_node_gist(node
, uset
);
2230 node
= isl_schedule_node_parent(node
);
2234 isl_schedule_node_free(node
);
2235 isl_union_set_free(domain
);
2239 /* Reset the user pointer on all identifiers of parameters and tuples
2240 * in the schedule node "node".
2242 __isl_give isl_schedule_node
*isl_schedule_node_reset_user(
2243 __isl_take isl_schedule_node
*node
)
2245 isl_schedule_tree
*tree
;
2247 tree
= isl_schedule_node_get_tree(node
);
2248 tree
= isl_schedule_tree_reset_user(tree
);
2249 node
= isl_schedule_node_graft_tree(node
, tree
);
2254 /* Align the parameters of the schedule node "node" to those of "space".
2256 __isl_give isl_schedule_node
*isl_schedule_node_align_params(
2257 __isl_take isl_schedule_node
*node
, __isl_take isl_space
*space
)
2259 isl_schedule_tree
*tree
;
2261 tree
= isl_schedule_node_get_tree(node
);
2262 tree
= isl_schedule_tree_align_params(tree
, space
);
2263 node
= isl_schedule_node_graft_tree(node
, tree
);
2268 /* Compute the pullback of schedule node "node"
2269 * by the function represented by "upma".
2270 * In other words, plug in "upma" in the iteration domains
2271 * of schedule node "node".
2273 * Note that this is only a helper function for
2274 * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency,
2275 * this function should not be called on a single node without also
2276 * calling it on all the other nodes.
2278 __isl_give isl_schedule_node
*isl_schedule_node_pullback_union_pw_multi_aff(
2279 __isl_take isl_schedule_node
*node
,
2280 __isl_take isl_union_pw_multi_aff
*upma
)
2282 isl_schedule_tree
*tree
;
2284 tree
= isl_schedule_node_get_tree(node
);
2285 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, upma
);
2286 node
= isl_schedule_node_graft_tree(node
, tree
);
2291 /* Return the position of the subtree containing "node" among the children
2292 * of "ancestor". "node" is assumed to be a descendant of "ancestor".
2293 * In particular, both nodes should point to the same schedule tree.
2295 * Return -1 on error.
2297 int isl_schedule_node_get_ancestor_child_position(
2298 __isl_keep isl_schedule_node
*node
,
2299 __isl_keep isl_schedule_node
*ancestor
)
2302 isl_schedule_tree
*tree
;
2304 if (!node
|| !ancestor
)
2307 if (node
->schedule
!= ancestor
->schedule
)
2308 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2309 "not a descendant", return -1);
2311 n1
= isl_schedule_node_get_tree_depth(ancestor
);
2312 n2
= isl_schedule_node_get_tree_depth(node
);
2315 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2316 "not a descendant", return -1);
2317 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n1
);
2318 isl_schedule_tree_free(tree
);
2319 if (tree
!= ancestor
->tree
)
2320 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2321 "not a descendant", return -1);
2323 return node
->child_pos
[n1
];
2326 /* Given two nodes that point to the same schedule tree, return their
2327 * closest shared ancestor.
2329 * Since the two nodes point to the same schedule, they share at least
2330 * one ancestor, the root of the schedule. We move down from the root
2331 * to the first ancestor where the respective children have a different
2332 * child position. This is the requested ancestor.
2333 * If there is no ancestor where the children have a different position,
2334 * then one node is an ancestor of the other and then this node is
2335 * the requested ancestor.
2337 __isl_give isl_schedule_node
*isl_schedule_node_get_shared_ancestor(
2338 __isl_keep isl_schedule_node
*node1
,
2339 __isl_keep isl_schedule_node
*node2
)
2343 if (!node1
|| !node2
)
2345 if (node1
->schedule
!= node2
->schedule
)
2346 isl_die(isl_schedule_node_get_ctx(node1
), isl_error_invalid
,
2347 "not part of same schedule", return NULL
);
2348 n1
= isl_schedule_node_get_tree_depth(node1
);
2349 n2
= isl_schedule_node_get_tree_depth(node2
);
2351 return isl_schedule_node_get_shared_ancestor(node2
, node1
);
2353 return isl_schedule_node_copy(node1
);
2354 if (isl_schedule_node_is_equal(node1
, node2
))
2355 return isl_schedule_node_copy(node1
);
2357 for (i
= 0; i
< n1
; ++i
)
2358 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
2361 node1
= isl_schedule_node_copy(node1
);
2362 return isl_schedule_node_ancestor(node1
, n1
- i
);
2365 /* Print "node" to "p".
2367 __isl_give isl_printer
*isl_printer_print_schedule_node(
2368 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
2371 return isl_printer_free(p
);
2372 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
,
2373 isl_schedule_tree_list_n_schedule_tree(node
->ancestors
),
2377 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
2380 isl_printer
*printer
;
2385 ctx
= isl_schedule_node_get_ctx(node
);
2386 printer
= isl_printer_to_file(ctx
, stderr
);
2387 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
2388 printer
= isl_printer_print_schedule_node(printer
, node
);
2390 isl_printer_free(printer
);