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 * "universe_filter" is set if we are only collecting the universes of filters
284 * "collect_prefix" is set if we are collecting prefixes.
285 * "filter" collects all outer filters and is NULL until "initialized" is set.
286 * "prefix" collects all outer band partial schedules (if "collect_prefix"
287 * is set). If it is used, then it is initialized by the caller
288 * of collect_filter_prefix to a zero-dimensional function.
290 struct isl_schedule_node_get_filter_prefix_data
{
294 isl_union_set
*filter
;
295 isl_multi_union_pw_aff
*prefix
;
298 /* Update "data" based on the tree node "tree" in case "data" has
299 * not been initialized yet.
301 * Return 0 on success and -1 on error.
303 * If "tree" is a filter, then we set data->filter to this filter
305 * If "tree" is a domain, then this means we have reached the root
306 * of the schedule tree without being able to extract any information.
307 * We therefore initialize data->filter to the universe of the domain.
308 * If "tree" is a band with at least one member, then we set data->filter
309 * to the universe of the schedule domain and replace the zero-dimensional
310 * data->prefix by the band schedule (if data->collect_prefix is set).
312 static int collect_filter_prefix_init(__isl_keep isl_schedule_tree
*tree
,
313 struct isl_schedule_node_get_filter_prefix_data
*data
)
315 enum isl_schedule_node_type type
;
316 isl_multi_union_pw_aff
*mupa
;
317 isl_union_set
*filter
;
319 type
= isl_schedule_tree_get_type(tree
);
321 case isl_schedule_node_error
:
323 case isl_schedule_node_leaf
:
324 case isl_schedule_node_sequence
:
325 case isl_schedule_node_set
:
327 case isl_schedule_node_domain
:
328 filter
= isl_schedule_tree_domain_get_domain(tree
);
329 filter
= isl_union_set_universe(filter
);
330 data
->filter
= filter
;
332 case isl_schedule_node_band
:
333 if (isl_schedule_tree_band_n_member(tree
) == 0)
335 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
336 if (data
->collect_prefix
) {
337 isl_multi_union_pw_aff_free(data
->prefix
);
338 mupa
= isl_multi_union_pw_aff_reset_tuple_id(mupa
,
340 data
->prefix
= isl_multi_union_pw_aff_copy(mupa
);
342 filter
= isl_multi_union_pw_aff_domain(mupa
);
343 filter
= isl_union_set_universe(filter
);
344 data
->filter
= filter
;
346 case isl_schedule_node_filter
:
347 filter
= isl_schedule_tree_filter_get_filter(tree
);
348 if (data
->universe_filter
)
349 filter
= isl_union_set_universe(filter
);
350 data
->filter
= filter
;
354 if ((data
->collect_prefix
&& !data
->prefix
) || !data
->filter
)
357 data
->initialized
= 1;
362 /* Update "data" based on the tree node "tree" in case "data" has
363 * already been initialized.
365 * Return 0 on success and -1 on error.
367 * If "tree" is a filter, then we intersect data->filter with this filter
369 * If "tree" is a band with at least one member and data->collect_prefix
370 * is set, then we extend data->prefix with the band schedule.
372 static int collect_filter_prefix_update(__isl_keep isl_schedule_tree
*tree
,
373 struct isl_schedule_node_get_filter_prefix_data
*data
)
375 enum isl_schedule_node_type type
;
376 isl_multi_union_pw_aff
*mupa
;
377 isl_union_set
*filter
;
379 type
= isl_schedule_tree_get_type(tree
);
381 case isl_schedule_node_error
:
383 case isl_schedule_node_domain
:
384 case isl_schedule_node_leaf
:
385 case isl_schedule_node_sequence
:
386 case isl_schedule_node_set
:
388 case isl_schedule_node_band
:
389 if (isl_schedule_tree_band_n_member(tree
) == 0)
391 if (!data
->collect_prefix
)
393 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
394 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(mupa
,
399 case isl_schedule_node_filter
:
400 filter
= isl_schedule_tree_filter_get_filter(tree
);
401 if (data
->universe_filter
)
402 filter
= isl_union_set_universe(filter
);
403 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
412 /* Collect filter and/or prefix information from the elements
413 * in "list" (which represent the ancestors of a node).
414 * Store the results in "data".
416 * Return 0 on success and -1 on error.
418 * We traverse the list from innermost ancestor (last element)
419 * to outermost ancestor (first element), calling collect_filter_prefix_init
420 * on each node as long as we have not been able to extract any information
421 * yet and collect_filter_prefix_update afterwards.
422 * On successful return, data->initialized will be set since the outermost
423 * ancestor is a domain node, which always results in an initialization.
425 static int collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
426 struct isl_schedule_node_get_filter_prefix_data
*data
)
430 data
->initialized
= 0;
436 n
= isl_schedule_tree_list_n_schedule_tree(list
);
437 for (i
= n
- 1; i
>= 0; --i
) {
438 isl_schedule_tree
*tree
;
441 tree
= isl_schedule_tree_list_get_schedule_tree(list
, i
);
444 if (!data
->initialized
)
445 r
= collect_filter_prefix_init(tree
, data
);
447 r
= collect_filter_prefix_update(tree
, data
);
448 isl_schedule_tree_free(tree
);
456 /* Return the concatenation of the partial schedules of all outer band
457 * nodes of "node" interesected with all outer filters
458 * as an isl_union_pw_multi_aff.
460 * If "node" is pointing at the root of the schedule tree, then
461 * there are no domain elements reaching the current node, so
462 * we return an empty result.
464 * We collect all the filters and partial schedules in collect_filter_prefix.
465 * The partial schedules are collected as an isl_multi_union_pw_aff.
466 * If this isl_multi_union_pw_aff is zero-dimensional, then it does not
467 * contain any domain information, so we construct the isl_union_pw_multi_aff
468 * result as a zero-dimensional function on the collected filter.
469 * Otherwise, we convert the isl_multi_union_pw_aff to
470 * an isl_multi_union_pw_aff and intersect the domain with the filter.
472 __isl_give isl_union_pw_multi_aff
*
473 isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(
474 __isl_keep isl_schedule_node
*node
)
477 isl_union_pw_multi_aff
*prefix
;
478 struct isl_schedule_node_get_filter_prefix_data data
;
483 space
= isl_schedule_get_space(node
->schedule
);
484 if (node
->tree
== node
->schedule
->root
)
485 return isl_union_pw_multi_aff_empty(space
);
487 space
= isl_space_set_from_params(space
);
488 data
.universe_filter
= 0;
489 data
.collect_prefix
= 1;
490 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
492 if (collect_filter_prefix(node
->ancestors
, &data
) < 0)
493 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
496 isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
) == 0) {
497 isl_multi_union_pw_aff_free(data
.prefix
);
498 prefix
= isl_union_pw_multi_aff_from_domain(data
.filter
);
501 isl_union_pw_multi_aff_from_multi_union_pw_aff(data
.prefix
);
502 prefix
= isl_union_pw_multi_aff_intersect_domain(prefix
,
509 /* Return the concatenation of the partial schedules of all outer band
510 * nodes of "node" interesected with all outer filters
511 * as an isl_union_map.
513 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_union_map(
514 __isl_keep isl_schedule_node
*node
)
516 isl_union_pw_multi_aff
*upma
;
518 upma
= isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(node
);
519 return isl_union_map_from_union_pw_multi_aff(upma
);
522 /* Return the union of universe sets of the domain elements that reach "node".
524 * If "node" is pointing at the root of the schedule tree, then
525 * there are no domain elements reaching the current node, so
526 * we return an empty result.
528 * Otherwise, we collect the universes of all filters reaching the node
529 * in collect_filter_prefix.
531 __isl_give isl_union_set
*isl_schedule_node_get_universe_domain(
532 __isl_keep isl_schedule_node
*node
)
534 struct isl_schedule_node_get_filter_prefix_data data
;
539 if (node
->tree
== node
->schedule
->root
) {
542 space
= isl_schedule_get_space(node
->schedule
);
543 return isl_union_set_empty(space
);
546 data
.universe_filter
= 1;
547 data
.collect_prefix
= 0;
550 if (collect_filter_prefix(node
->ancestors
, &data
) < 0)
551 data
.filter
= isl_union_set_free(data
.filter
);
556 /* Return the subtree schedule of "node".
558 * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle
559 * trees that do not contain any schedule information, we first
560 * move down to the first relevant descendant and handle leaves ourselves.
562 __isl_give isl_union_map
*isl_schedule_node_get_subtree_schedule_union_map(
563 __isl_keep isl_schedule_node
*node
)
565 isl_schedule_tree
*tree
, *leaf
;
568 tree
= isl_schedule_node_get_tree(node
);
569 leaf
= isl_schedule_node_peek_leaf(node
);
570 tree
= isl_schedule_tree_first_schedule_descendant(tree
, leaf
);
574 isl_union_set
*domain
;
575 domain
= isl_schedule_node_get_universe_domain(node
);
576 isl_schedule_tree_free(tree
);
577 return isl_union_map_from_domain(domain
);
580 umap
= isl_schedule_tree_get_subtree_schedule_union_map(tree
);
581 isl_schedule_tree_free(tree
);
585 /* Return the number of ancestors of "node" in its schedule tree.
587 int isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node
*node
)
591 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
594 /* Does "node" have a parent?
596 * That is, does it point to any node of the schedule other than the root?
598 int isl_schedule_node_has_parent(__isl_keep isl_schedule_node
*node
)
602 if (!node
->ancestors
)
605 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) != 0;
608 /* Return the position of "node" among the children of its parent.
610 int isl_schedule_node_get_child_position(__isl_keep isl_schedule_node
*node
)
617 has_parent
= isl_schedule_node_has_parent(node
);
621 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
622 "node has no parent", return -1);
624 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
625 return node
->child_pos
[n
- 1];
628 /* Does the parent (if any) of "node" have any children with a smaller child
629 * position than this one?
631 int isl_schedule_node_has_previous_sibling(__isl_keep isl_schedule_node
*node
)
638 has_parent
= isl_schedule_node_has_parent(node
);
639 if (has_parent
< 0 || !has_parent
)
642 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
644 return node
->child_pos
[n
- 1] > 0;
647 /* Does the parent (if any) of "node" have any children with a greater child
648 * position than this one?
650 int isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node
*node
)
654 isl_schedule_tree
*tree
;
658 has_parent
= isl_schedule_node_has_parent(node
);
659 if (has_parent
< 0 || !has_parent
)
662 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
663 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
666 n_child
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
667 isl_schedule_tree_free(tree
);
669 return node
->child_pos
[n
- 1] + 1 < n_child
;
672 /* Does "node" have any children?
674 * Any node other than the leaf nodes is considered to have at least
675 * one child, even if the corresponding isl_schedule_tree does not
678 int isl_schedule_node_has_children(__isl_keep isl_schedule_node
*node
)
682 return !isl_schedule_tree_is_leaf(node
->tree
);
685 /* Return the number of children of "node"?
687 * Any node other than the leaf nodes is considered to have at least
688 * one child, even if the corresponding isl_schedule_tree does not
689 * have any children. That is, the number of children of "node" is
690 * only zero if its tree is the explicit empty tree. Otherwise,
691 * if the isl_schedule_tree has any children, then it is equal
692 * to the number of children of "node". If it has zero children,
693 * then "node" still has a leaf node as child.
695 int isl_schedule_node_n_children(__isl_keep isl_schedule_node
*node
)
702 if (isl_schedule_tree_is_leaf(node
->tree
))
705 n
= isl_schedule_tree_n_children(node
->tree
);
712 /* Move the "node" pointer to the ancestor of the given generation
713 * of the node it currently points to, where generation 0 is the node
714 * itself and generation 1 is its parent.
716 __isl_give isl_schedule_node
*isl_schedule_node_ancestor(
717 __isl_take isl_schedule_node
*node
, int generation
)
720 isl_schedule_tree
*tree
;
726 n
= isl_schedule_node_get_tree_depth(node
);
728 return isl_schedule_node_free(node
);
729 if (generation
< 0 || generation
> n
)
730 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
731 "generation out of bounds",
732 return isl_schedule_node_free(node
));
733 node
= isl_schedule_node_cow(node
);
737 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
739 isl_schedule_tree_free(node
->tree
);
741 node
->ancestors
= isl_schedule_tree_list_drop(node
->ancestors
,
742 n
- generation
, generation
);
743 if (!node
->ancestors
|| !node
->tree
)
744 return isl_schedule_node_free(node
);
749 /* Move the "node" pointer to the parent of the node it currently points to.
751 __isl_give isl_schedule_node
*isl_schedule_node_parent(
752 __isl_take isl_schedule_node
*node
)
756 if (!isl_schedule_node_has_parent(node
))
757 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
758 "node has no parent",
759 return isl_schedule_node_free(node
));
760 return isl_schedule_node_ancestor(node
, 1);
763 /* Move the "node" pointer to the root of its schedule tree.
765 __isl_give isl_schedule_node
*isl_schedule_node_root(
766 __isl_take isl_schedule_node
*node
)
772 n
= isl_schedule_node_get_tree_depth(node
);
774 return isl_schedule_node_free(node
);
775 return isl_schedule_node_ancestor(node
, n
);
778 /* Move the "node" pointer to the child at position "pos" of the node
779 * it currently points to.
781 __isl_give isl_schedule_node
*isl_schedule_node_child(
782 __isl_take isl_schedule_node
*node
, int pos
)
786 isl_schedule_tree
*tree
;
789 node
= isl_schedule_node_cow(node
);
792 if (!isl_schedule_node_has_children(node
))
793 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
794 "node has no children",
795 return isl_schedule_node_free(node
));
797 ctx
= isl_schedule_node_get_ctx(node
);
798 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
799 child_pos
= isl_realloc_array(ctx
, node
->child_pos
, int, n
+ 1);
801 return isl_schedule_node_free(node
);
802 node
->child_pos
= child_pos
;
803 node
->child_pos
[n
] = pos
;
805 node
->ancestors
= isl_schedule_tree_list_add(node
->ancestors
,
806 isl_schedule_tree_copy(node
->tree
));
808 if (isl_schedule_tree_has_children(tree
))
809 tree
= isl_schedule_tree_get_child(tree
, pos
);
811 tree
= isl_schedule_node_get_leaf(node
);
812 isl_schedule_tree_free(node
->tree
);
815 if (!node
->tree
|| !node
->ancestors
)
816 return isl_schedule_node_free(node
);
821 /* Move the "node" pointer to the first child of the node
822 * it currently points to.
824 __isl_give isl_schedule_node
*isl_schedule_node_first_child(
825 __isl_take isl_schedule_node
*node
)
827 return isl_schedule_node_child(node
, 0);
830 /* Move the "node" pointer to the child of this node's parent in
831 * the previous child position.
833 __isl_give isl_schedule_node
*isl_schedule_node_previous_sibling(
834 __isl_take isl_schedule_node
*node
)
837 isl_schedule_tree
*parent
, *tree
;
839 node
= isl_schedule_node_cow(node
);
842 if (!isl_schedule_node_has_previous_sibling(node
))
843 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
844 "node has no previous sibling",
845 return isl_schedule_node_free(node
));
847 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
848 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
851 return isl_schedule_node_free(node
);
852 node
->child_pos
[n
- 1]--;
853 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
854 node
->child_pos
[n
- 1]);
855 isl_schedule_tree_free(parent
);
857 return isl_schedule_node_free(node
);
858 isl_schedule_tree_free(node
->tree
);
864 /* Move the "node" pointer to the child of this node's parent in
865 * the next child position.
867 __isl_give isl_schedule_node
*isl_schedule_node_next_sibling(
868 __isl_take isl_schedule_node
*node
)
871 isl_schedule_tree
*parent
, *tree
;
873 node
= isl_schedule_node_cow(node
);
876 if (!isl_schedule_node_has_next_sibling(node
))
877 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
878 "node has no next sibling",
879 return isl_schedule_node_free(node
));
881 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
882 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
885 return isl_schedule_node_free(node
);
886 node
->child_pos
[n
- 1]++;
887 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
888 node
->child_pos
[n
- 1]);
889 isl_schedule_tree_free(parent
);
891 return isl_schedule_node_free(node
);
892 isl_schedule_tree_free(node
->tree
);
898 /* Return a copy to the child at position "pos" of "node".
900 __isl_give isl_schedule_node
*isl_schedule_node_get_child(
901 __isl_keep isl_schedule_node
*node
, int pos
)
903 return isl_schedule_node_child(isl_schedule_node_copy(node
), pos
);
906 /* Traverse the descendant of "node" in depth-first order, including
907 * "node" itself. Call "enter" whenever a node is entered and "leave"
908 * whenever a node is left. The callback "enter" is responsible
909 * for moving to the deepest initial subtree of its argument that
910 * should be traversed.
912 static __isl_give isl_schedule_node
*traverse(
913 __isl_take isl_schedule_node
*node
,
914 __isl_give isl_schedule_node
*(*enter
)(
915 __isl_take isl_schedule_node
*node
, void *user
),
916 __isl_give isl_schedule_node
*(*leave
)(
917 __isl_take isl_schedule_node
*node
, void *user
),
925 depth
= isl_schedule_node_get_tree_depth(node
);
927 node
= enter(node
, user
);
928 node
= leave(node
, user
);
929 while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
&&
930 !isl_schedule_node_has_next_sibling(node
)) {
931 node
= isl_schedule_node_parent(node
);
932 node
= leave(node
, user
);
934 if (node
&& isl_schedule_node_get_tree_depth(node
) > depth
)
935 node
= isl_schedule_node_next_sibling(node
);
936 } while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
);
941 /* Internal data structure for isl_schedule_node_foreach_descendant.
943 * "fn" is the user-specified callback function.
944 * "user" is the user-specified argument for the callback.
946 struct isl_schedule_node_preorder_data
{
947 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
);
951 /* Callback for "traverse" to enter a node and to move
952 * to the deepest initial subtree that should be traversed
953 * for use in a preorder visit.
955 * If the user callback returns a negative value, then we abort
956 * the traversal. If this callback returns zero, then we skip
957 * the subtree rooted at the current node. Otherwise, we move
958 * down to the first child and repeat the process until a leaf
961 static __isl_give isl_schedule_node
*preorder_enter(
962 __isl_take isl_schedule_node
*node
, void *user
)
964 struct isl_schedule_node_preorder_data
*data
= user
;
972 r
= data
->fn(node
, data
->user
);
974 return isl_schedule_node_free(node
);
977 } while (isl_schedule_node_has_children(node
) &&
978 (node
= isl_schedule_node_first_child(node
)) != NULL
);
983 /* Callback for "traverse" to leave a node
984 * for use in a preorder visit.
985 * Since we already visited the node when we entered it,
986 * we do not need to do anything here.
988 static __isl_give isl_schedule_node
*preorder_leave(
989 __isl_take isl_schedule_node
*node
, void *user
)
994 /* Traverse the descendants of "node" (including the node itself)
995 * in depth first preorder.
997 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
998 * If "fn" returns 0 on any of the nodes, then the subtree rooted
999 * at that node is skipped.
1001 * Return 0 on success and -1 on failure.
1003 int isl_schedule_node_foreach_descendant(__isl_keep isl_schedule_node
*node
,
1004 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
), void *user
)
1006 struct isl_schedule_node_preorder_data data
= { fn
, user
};
1008 node
= isl_schedule_node_copy(node
);
1009 node
= traverse(node
, &preorder_enter
, &preorder_leave
, &data
);
1010 isl_schedule_node_free(node
);
1012 return node
? 0 : -1;
1015 /* Internal data structure for isl_schedule_node_map_descendant.
1017 * "fn" is the user-specified callback function.
1018 * "user" is the user-specified argument for the callback.
1020 struct isl_schedule_node_postorder_data
{
1021 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1026 /* Callback for "traverse" to enter a node and to move
1027 * to the deepest initial subtree that should be traversed
1028 * for use in a postorder visit.
1030 * Since we are performing a postorder visit, we only need
1031 * to move to the deepest initial leaf here.
1033 static __isl_give isl_schedule_node
*postorder_enter(
1034 __isl_take isl_schedule_node
*node
, void *user
)
1036 while (node
&& isl_schedule_node_has_children(node
))
1037 node
= isl_schedule_node_first_child(node
);
1042 /* Callback for "traverse" to leave a node
1043 * for use in a postorder visit.
1045 * Since we are performing a postorder visit, we need
1046 * to call the user callback here.
1048 static __isl_give isl_schedule_node
*postorder_leave(
1049 __isl_take isl_schedule_node
*node
, void *user
)
1051 struct isl_schedule_node_postorder_data
*data
= user
;
1053 return data
->fn(node
, data
->user
);
1056 /* Traverse the descendants of "node" (including the node itself)
1057 * in depth first postorder, allowing the user to modify the visited node.
1058 * The traversal continues from the node returned by the callback function.
1059 * It is the responsibility of the user to ensure that this does not
1060 * lead to an infinite loop. It is safest to always return a pointer
1061 * to the same position (same ancestors and child positions) as the input node.
1063 __isl_give isl_schedule_node
*isl_schedule_node_map_descendant(
1064 __isl_take isl_schedule_node
*node
,
1065 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1066 void *user
), void *user
)
1068 struct isl_schedule_node_postorder_data data
= { fn
, user
};
1070 return traverse(node
, &postorder_enter
, &postorder_leave
, &data
);
1073 /* Traverse the ancestors of "node" from the root down to and including
1074 * the parent of "node", calling "fn" on each of them.
1076 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1078 * Return 0 on success and -1 on failure.
1080 int isl_schedule_node_foreach_ancestor_top_down(
1081 __isl_keep isl_schedule_node
*node
,
1082 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
), void *user
)
1089 n
= isl_schedule_node_get_tree_depth(node
);
1090 for (i
= 0; i
< n
; ++i
) {
1091 isl_schedule_node
*ancestor
;
1094 ancestor
= isl_schedule_node_copy(node
);
1095 ancestor
= isl_schedule_node_ancestor(ancestor
, n
- i
);
1096 r
= fn(ancestor
, user
);
1097 isl_schedule_node_free(ancestor
);
1105 /* Return the number of members in the given band node.
1107 unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node
*node
)
1109 return node
? isl_schedule_tree_band_n_member(node
->tree
) : 0;
1112 /* Is the band member at position "pos" of the band node "node"
1113 * marked coincident?
1115 int isl_schedule_node_band_member_get_coincident(
1116 __isl_keep isl_schedule_node
*node
, int pos
)
1120 return isl_schedule_tree_band_member_get_coincident(node
->tree
, pos
);
1123 /* Mark the band member at position "pos" the band node "node"
1124 * as being coincident or not according to "coincident".
1126 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_coincident(
1127 __isl_take isl_schedule_node
*node
, int pos
, int coincident
)
1130 isl_schedule_tree
*tree
;
1134 c
= isl_schedule_node_band_member_get_coincident(node
, pos
);
1135 if (c
== coincident
)
1138 tree
= isl_schedule_tree_copy(node
->tree
);
1139 tree
= isl_schedule_tree_band_member_set_coincident(tree
, pos
,
1141 node
= isl_schedule_node_graft_tree(node
, tree
);
1146 /* Is the band node "node" marked permutable?
1148 int isl_schedule_node_band_get_permutable(__isl_keep isl_schedule_node
*node
)
1153 return isl_schedule_tree_band_get_permutable(node
->tree
);
1156 /* Mark the band node "node" permutable or not according to "permutable"?
1158 __isl_give isl_schedule_node
*isl_schedule_node_band_set_permutable(
1159 __isl_take isl_schedule_node
*node
, int permutable
)
1161 isl_schedule_tree
*tree
;
1165 if (isl_schedule_node_band_get_permutable(node
) == permutable
)
1168 tree
= isl_schedule_tree_copy(node
->tree
);
1169 tree
= isl_schedule_tree_band_set_permutable(tree
, permutable
);
1170 node
= isl_schedule_node_graft_tree(node
, tree
);
1175 /* Return the schedule space of the band node.
1177 __isl_give isl_space
*isl_schedule_node_band_get_space(
1178 __isl_keep isl_schedule_node
*node
)
1183 return isl_schedule_tree_band_get_space(node
->tree
);
1186 /* Return the schedule of the band node in isolation.
1188 __isl_give isl_multi_union_pw_aff
*isl_schedule_node_band_get_partial_schedule(
1189 __isl_keep isl_schedule_node
*node
)
1194 return isl_schedule_tree_band_get_partial_schedule(node
->tree
);
1197 /* Return the schedule of the band node in isolation in the form of
1200 * If the band does not have any members, then we construct a universe map
1201 * with the universe of the domain elements reaching the node as domain.
1202 * Otherwise, we extract an isl_multi_union_pw_aff representation and
1203 * convert that to an isl_union_map.
1205 __isl_give isl_union_map
*isl_schedule_node_band_get_partial_schedule_union_map(
1206 __isl_keep isl_schedule_node
*node
)
1208 isl_multi_union_pw_aff
*mupa
;
1213 if (isl_schedule_node_get_type(node
) != isl_schedule_node_band
)
1214 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1215 "not a band node", return NULL
);
1216 if (isl_schedule_node_band_n_member(node
) == 0) {
1217 isl_union_set
*domain
;
1219 domain
= isl_schedule_node_get_universe_domain(node
);
1220 return isl_union_map_from_domain(domain
);
1223 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
1224 return isl_union_map_from_multi_union_pw_aff(mupa
);
1227 /* Return the loop AST generation type for the band member of band node "node"
1228 * at position "pos".
1230 enum isl_ast_loop_type
isl_schedule_node_band_member_get_ast_loop_type(
1231 __isl_keep isl_schedule_node
*node
, int pos
)
1234 return isl_ast_loop_error
;
1236 return isl_schedule_tree_band_member_get_ast_loop_type(node
->tree
, pos
);
1239 /* Set the loop AST generation type for the band member of band node "node"
1240 * at position "pos" to "type".
1242 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_ast_loop_type(
1243 __isl_take isl_schedule_node
*node
, int pos
,
1244 enum isl_ast_loop_type type
)
1246 isl_schedule_tree
*tree
;
1251 tree
= isl_schedule_tree_copy(node
->tree
);
1252 tree
= isl_schedule_tree_band_member_set_ast_loop_type(tree
, pos
, type
);
1253 return isl_schedule_node_graft_tree(node
, tree
);
1256 /* Return the AST build options associated to band node "node".
1258 __isl_give isl_union_set
*isl_schedule_node_band_get_ast_build_options(
1259 __isl_keep isl_schedule_node
*node
)
1264 return isl_schedule_tree_band_get_ast_build_options(node
->tree
);
1267 /* Replace the AST build options associated to band node "node" by "options".
1269 __isl_give isl_schedule_node
*isl_schedule_node_band_set_ast_build_options(
1270 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*options
)
1272 isl_schedule_tree
*tree
;
1274 if (!node
|| !options
)
1277 tree
= isl_schedule_tree_copy(node
->tree
);
1278 tree
= isl_schedule_tree_band_set_ast_build_options(tree
, options
);
1279 return isl_schedule_node_graft_tree(node
, tree
);
1281 isl_schedule_node_free(node
);
1282 isl_union_set_free(options
);
1286 /* Make sure that that spaces of "node" and "mv" are the same.
1287 * Return -1 on error, reporting the error to the user.
1289 static int check_space_multi_val(__isl_keep isl_schedule_node
*node
,
1290 __isl_keep isl_multi_val
*mv
)
1292 isl_space
*node_space
, *mv_space
;
1295 node_space
= isl_schedule_node_band_get_space(node
);
1296 mv_space
= isl_multi_val_get_space(mv
);
1297 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1298 mv_space
, isl_dim_set
);
1299 isl_space_free(mv_space
);
1300 isl_space_free(node_space
);
1304 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1305 "spaces don't match", return -1);
1310 /* Multiply the partial schedule of the band node "node"
1311 * with the factors in "mv".
1313 __isl_give isl_schedule_node
*isl_schedule_node_band_scale(
1314 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1316 isl_schedule_tree
*tree
;
1320 if (check_space_multi_val(node
, mv
) < 0)
1323 tree
= isl_schedule_node_get_tree(node
);
1324 tree
= isl_schedule_tree_band_scale(tree
, mv
);
1325 return isl_schedule_node_graft_tree(node
, tree
);
1327 isl_multi_val_free(mv
);
1328 isl_schedule_node_free(node
);
1332 /* Divide the partial schedule of the band node "node"
1333 * by the factors in "mv".
1335 __isl_give isl_schedule_node
*isl_schedule_node_band_scale_down(
1336 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1338 isl_schedule_tree
*tree
;
1342 if (check_space_multi_val(node
, mv
) < 0)
1345 tree
= isl_schedule_node_get_tree(node
);
1346 tree
= isl_schedule_tree_band_scale_down(tree
, mv
);
1347 return isl_schedule_node_graft_tree(node
, tree
);
1349 isl_multi_val_free(mv
);
1350 isl_schedule_node_free(node
);
1354 /* Tile "node" with tile sizes "sizes".
1356 * The current node is replaced by two nested nodes corresponding
1357 * to the tile dimensions and the point dimensions.
1359 * Return a pointer to the outer (tile) node.
1361 * If the scale tile loops option is set, then the tile loops
1362 * are scaled by the tile sizes. If the shift point loops option is set,
1363 * then the point loops are shifted to start at zero.
1364 * In particular, these options affect the tile and point loop schedules
1367 * scale shift original tile point
1369 * 0 0 i floor(i/s) i
1370 * 1 0 i s * floor(i/s) i
1371 * 0 1 i floor(i/s) i - s * floor(i/s)
1372 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1374 __isl_give isl_schedule_node
*isl_schedule_node_band_tile(
1375 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*sizes
)
1377 isl_schedule_tree
*tree
;
1379 if (!node
|| !sizes
)
1382 if (check_space_multi_val(node
, sizes
) < 0)
1385 tree
= isl_schedule_node_get_tree(node
);
1386 tree
= isl_schedule_tree_band_tile(tree
, sizes
);
1387 return isl_schedule_node_graft_tree(node
, tree
);
1389 isl_multi_val_free(sizes
);
1390 isl_schedule_node_free(node
);
1394 /* Move the band node "node" down to all the leaves in the subtree
1396 * Return a pointer to the node in the resulting tree that is in the same
1397 * position as the node pointed to by "node" in the original tree.
1399 * If the node only has a leaf child, then nothing needs to be done.
1400 * Otherwise, the child of the node is removed and the result is
1401 * appended to all the leaves in the subtree rooted at the original child.
1402 * The original node is then replaced by the result of this operation.
1404 __isl_give isl_schedule_node
*isl_schedule_node_band_sink(
1405 __isl_take isl_schedule_node
*node
)
1407 enum isl_schedule_node_type type
;
1408 isl_schedule_tree
*tree
, *child
;
1413 type
= isl_schedule_node_get_type(node
);
1414 if (type
!= isl_schedule_node_band
)
1415 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1416 "not a band node", isl_schedule_node_free(node
));
1417 if (isl_schedule_tree_n_children(node
->tree
) == 0)
1420 tree
= isl_schedule_node_get_tree(node
);
1421 child
= isl_schedule_tree_get_child(tree
, 0);
1422 tree
= isl_schedule_tree_reset_children(tree
);
1423 tree
= isl_schedule_tree_append_to_leaves(child
, tree
);
1425 return isl_schedule_node_graft_tree(node
, tree
);
1428 /* Split "node" into two nested band nodes, one with the first "pos"
1429 * dimensions and one with the remaining dimensions.
1430 * The schedules of the two band nodes live in anonymous spaces.
1432 __isl_give isl_schedule_node
*isl_schedule_node_band_split(
1433 __isl_take isl_schedule_node
*node
, int pos
)
1435 isl_schedule_tree
*tree
;
1437 tree
= isl_schedule_node_get_tree(node
);
1438 tree
= isl_schedule_tree_band_split(tree
, pos
);
1439 return isl_schedule_node_graft_tree(node
, tree
);
1442 /* Return the domain of the domain node "node".
1444 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
1445 __isl_keep isl_schedule_node
*node
)
1450 return isl_schedule_tree_domain_get_domain(node
->tree
);
1453 /* Return the filter of the filter node "node".
1455 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
1456 __isl_keep isl_schedule_node
*node
)
1461 return isl_schedule_tree_filter_get_filter(node
->tree
);
1464 /* Replace the filter of filter node "node" by "filter".
1466 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
1467 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
1469 isl_schedule_tree
*tree
;
1471 if (!node
|| !filter
)
1474 tree
= isl_schedule_tree_copy(node
->tree
);
1475 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
1476 return isl_schedule_node_graft_tree(node
, tree
);
1478 isl_schedule_node_free(node
);
1479 isl_union_set_free(filter
);
1483 /* Update the ancestors of "node" to point to the tree that "node"
1485 * That is, replace the child in the original parent that corresponds
1486 * to the current tree position by node->tree and continue updating
1487 * the ancestors in the same way until the root is reached.
1489 * If "node" originally points to a leaf of the schedule tree, then make sure
1490 * that in the end it points to a leaf in the updated schedule tree.
1492 static __isl_give isl_schedule_node
*update_ancestors(
1493 __isl_take isl_schedule_node
*node
)
1498 isl_schedule_tree
*tree
;
1500 node
= isl_schedule_node_cow(node
);
1504 ctx
= isl_schedule_node_get_ctx(node
);
1505 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1506 tree
= isl_schedule_tree_copy(node
->tree
);
1508 for (i
= n
- 1; i
>= 0; --i
) {
1509 isl_schedule_tree
*parent
;
1511 parent
= isl_schedule_tree_list_get_schedule_tree(
1512 node
->ancestors
, i
);
1513 parent
= isl_schedule_tree_replace_child(parent
,
1514 node
->child_pos
[i
], tree
);
1515 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
1516 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
1521 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
1522 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
1524 isl_schedule_tree_free(node
->tree
);
1525 node
->tree
= isl_schedule_node_get_leaf(node
);
1528 if (!node
->schedule
|| !node
->ancestors
)
1529 return isl_schedule_node_free(node
);
1534 /* Replace the subtree that "pos" points to by "tree", updating
1535 * the ancestors to maintain a consistent state.
1537 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
1538 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
1542 if (pos
->tree
== tree
) {
1543 isl_schedule_tree_free(tree
);
1547 pos
= isl_schedule_node_cow(pos
);
1551 isl_schedule_tree_free(pos
->tree
);
1554 return update_ancestors(pos
);
1556 isl_schedule_node_free(pos
);
1557 isl_schedule_tree_free(tree
);
1561 /* Make sure we can insert a node between "node" and its parent.
1562 * Return -1 on error, reporting the reason why we cannot insert a node.
1564 static int check_insert(__isl_keep isl_schedule_node
*node
)
1567 enum isl_schedule_node_type type
;
1569 has_parent
= isl_schedule_node_has_parent(node
);
1573 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1574 "cannot insert node outside of root", return -1);
1576 type
= isl_schedule_node_get_parent_type(node
);
1577 if (type
== isl_schedule_node_error
)
1579 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
1580 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1581 "cannot insert node between set or sequence node "
1582 "and its filter children", return -1);
1587 /* Insert a band node with partial schedule "mupa" between "node" and
1589 * Return a pointer to the new band node.
1591 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
1592 __isl_take isl_schedule_node
*node
,
1593 __isl_take isl_multi_union_pw_aff
*mupa
)
1595 isl_schedule_band
*band
;
1596 isl_schedule_tree
*tree
;
1598 if (check_insert(node
) < 0)
1599 node
= isl_schedule_node_free(node
);
1601 tree
= isl_schedule_node_get_tree(node
);
1602 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
1603 tree
= isl_schedule_tree_insert_band(tree
, band
);
1604 node
= isl_schedule_node_graft_tree(node
, tree
);
1609 /* Insert a filter node with filter "filter" between "node" and its parent.
1610 * Return a pointer to the new filter node.
1612 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
1613 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
1615 isl_schedule_tree
*tree
;
1617 if (check_insert(node
) < 0)
1618 node
= isl_schedule_node_free(node
);
1620 tree
= isl_schedule_node_get_tree(node
);
1621 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
1622 node
= isl_schedule_node_graft_tree(node
, tree
);
1627 /* Attach the current subtree of "node" to a sequence of filter tree nodes
1628 * with filters described by "filters", attach this sequence
1629 * of filter tree nodes as children to a new tree of type "type" and
1630 * replace the original subtree of "node" by this new tree.
1632 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
1633 __isl_take isl_schedule_node
*node
,
1634 enum isl_schedule_node_type type
,
1635 __isl_take isl_union_set_list
*filters
)
1639 isl_schedule_tree
*tree
;
1640 isl_schedule_tree_list
*list
;
1642 if (check_insert(node
) < 0)
1643 node
= isl_schedule_node_free(node
);
1645 if (!node
|| !filters
)
1648 ctx
= isl_schedule_node_get_ctx(node
);
1649 n
= isl_union_set_list_n_union_set(filters
);
1650 list
= isl_schedule_tree_list_alloc(ctx
, n
);
1651 for (i
= 0; i
< n
; ++i
) {
1652 isl_schedule_tree
*tree
;
1653 isl_union_set
*filter
;
1655 tree
= isl_schedule_node_get_tree(node
);
1656 filter
= isl_union_set_list_get_union_set(filters
, i
);
1657 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
1658 list
= isl_schedule_tree_list_add(list
, tree
);
1660 tree
= isl_schedule_tree_from_children(type
, list
);
1661 node
= isl_schedule_node_graft_tree(node
, tree
);
1663 isl_union_set_list_free(filters
);
1666 isl_union_set_list_free(filters
);
1667 isl_schedule_node_free(node
);
1671 /* Insert a sequence node with child filters "filters" between "node" and
1672 * its parent. That is, the tree that "node" points to is attached
1673 * to each of the child nodes of the filter nodes.
1674 * Return a pointer to the new sequence node.
1676 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
1677 __isl_take isl_schedule_node
*node
,
1678 __isl_take isl_union_set_list
*filters
)
1680 return isl_schedule_node_insert_children(node
,
1681 isl_schedule_node_sequence
, filters
);
1684 /* Insert a set node with child filters "filters" between "node" and
1685 * its parent. That is, the tree that "node" points to is attached
1686 * to each of the child nodes of the filter nodes.
1687 * Return a pointer to the new set node.
1689 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
1690 __isl_take isl_schedule_node
*node
,
1691 __isl_take isl_union_set_list
*filters
)
1693 return isl_schedule_node_insert_children(node
,
1694 isl_schedule_node_set
, filters
);
1697 /* Remove "node" from its schedule tree and return a pointer
1698 * to the leaf at the same position in the updated schedule tree.
1700 * It is not allowed to remove the root of a schedule tree or
1701 * a child of a set or sequence node.
1703 __isl_give isl_schedule_node
*isl_schedule_node_cut(
1704 __isl_take isl_schedule_node
*node
)
1706 isl_schedule_tree
*leaf
;
1707 enum isl_schedule_node_type parent_type
;
1711 if (!isl_schedule_node_has_parent(node
))
1712 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1713 "cannot cut root", return isl_schedule_node_free(node
));
1715 parent_type
= isl_schedule_node_get_parent_type(node
);
1716 if (parent_type
== isl_schedule_node_set
||
1717 parent_type
== isl_schedule_node_sequence
)
1718 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1719 "cannot cut child of set or sequence",
1720 return isl_schedule_node_free(node
));
1722 leaf
= isl_schedule_node_get_leaf(node
);
1723 return isl_schedule_node_graft_tree(node
, leaf
);
1726 /* Remove a single node from the schedule tree, attaching the child
1727 * of "node" directly to its parent.
1728 * Return a pointer to this former child or to the leaf the position
1729 * of the original node if there was no child.
1730 * It is not allowed to remove the root of a schedule tree,
1731 * a set or sequence node or a child of a set or sequence node.
1733 __isl_give isl_schedule_node
*isl_schedule_node_delete(
1734 __isl_take isl_schedule_node
*node
)
1737 isl_schedule_tree
*tree
;
1738 enum isl_schedule_node_type type
;
1743 if (isl_schedule_node_get_tree_depth(node
) == 0)
1744 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1745 "cannot delete root node",
1746 return isl_schedule_node_free(node
));
1747 n
= isl_schedule_node_n_children(node
);
1749 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1750 "can only delete node with a single child",
1751 return isl_schedule_node_free(node
));
1752 type
= isl_schedule_node_get_parent_type(node
);
1753 if (type
== isl_schedule_node_sequence
|| type
== isl_schedule_node_set
)
1754 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1755 "cannot delete child of set or sequence",
1756 return isl_schedule_node_free(node
));
1758 tree
= isl_schedule_node_get_tree(node
);
1759 if (!tree
|| isl_schedule_tree_has_children(tree
)) {
1760 tree
= isl_schedule_tree_child(tree
, 0);
1762 isl_schedule_tree_free(tree
);
1763 tree
= isl_schedule_node_get_leaf(node
);
1765 node
= isl_schedule_node_graft_tree(node
, tree
);
1770 /* Compute the gist of the given band node with respect to "context".
1772 __isl_give isl_schedule_node
*isl_schedule_node_band_gist(
1773 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
1775 isl_schedule_tree
*tree
;
1777 tree
= isl_schedule_node_get_tree(node
);
1778 tree
= isl_schedule_tree_band_gist(tree
, context
);
1779 return isl_schedule_node_graft_tree(node
, tree
);
1782 /* Internal data structure for isl_schedule_node_gist.
1783 * "filters" contains an element for each outer filter node
1784 * with respect to the current position, each representing
1785 * the intersection of the previous element and the filter on the filter node.
1786 * The first element in the original context passed to isl_schedule_node_gist.
1788 struct isl_node_gist_data
{
1789 isl_union_set_list
*filters
;
1792 /* Can we finish gisting at this node?
1793 * That is, is the filter on the current filter node a subset of
1794 * the original context passed to isl_schedule_node_gist?
1796 static int gist_done(__isl_keep isl_schedule_node
*node
,
1797 struct isl_node_gist_data
*data
)
1799 isl_union_set
*filter
, *outer
;
1802 filter
= isl_schedule_node_filter_get_filter(node
);
1803 outer
= isl_union_set_list_get_union_set(data
->filters
, 0);
1804 subset
= isl_union_set_is_subset(filter
, outer
);
1805 isl_union_set_free(outer
);
1806 isl_union_set_free(filter
);
1811 /* Callback for "traverse" to enter a node and to move
1812 * to the deepest initial subtree that should be traversed
1813 * by isl_schedule_node_gist.
1815 * The "filters" list is extended by one element each time
1816 * we come across a filter node by the result of intersecting
1817 * the last element in the list with the filter on the filter node.
1819 * If the filter on the current filter node is a subset of
1820 * the original context passed to isl_schedule_node_gist,
1821 * then there is no need to go into its subtree since it cannot
1822 * be further simplified by the context. The "filters" list is
1823 * still extended for consistency, but the actual value of the
1824 * added element is immaterial since it will not be used.
1826 * Otherwise, the filter on the current filter node is replaced by
1827 * the gist of the original filter with respect to the intersection
1828 * of the original context with the intermediate filters.
1830 * If the new element in the "filters" list is empty, then no elements
1831 * can reach the descendants of the current filter node. The subtree
1832 * underneath the filter node is therefore removed.
1834 static __isl_give isl_schedule_node
*gist_enter(
1835 __isl_take isl_schedule_node
*node
, void *user
)
1837 struct isl_node_gist_data
*data
= user
;
1840 isl_union_set
*filter
, *inner
;
1844 switch (isl_schedule_node_get_type(node
)) {
1845 case isl_schedule_node_error
:
1846 return isl_schedule_node_free(node
);
1847 case isl_schedule_node_band
:
1848 case isl_schedule_node_domain
:
1849 case isl_schedule_node_leaf
:
1850 case isl_schedule_node_sequence
:
1851 case isl_schedule_node_set
:
1853 case isl_schedule_node_filter
:
1856 done
= gist_done(node
, data
);
1857 filter
= isl_schedule_node_filter_get_filter(node
);
1858 if (done
< 0 || done
) {
1859 data
->filters
= isl_union_set_list_add(data
->filters
,
1862 return isl_schedule_node_free(node
);
1865 n
= isl_union_set_list_n_union_set(data
->filters
);
1866 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
1867 filter
= isl_union_set_gist(filter
, isl_union_set_copy(inner
));
1868 node
= isl_schedule_node_filter_set_filter(node
,
1869 isl_union_set_copy(filter
));
1870 filter
= isl_union_set_intersect(filter
, inner
);
1871 empty
= isl_union_set_is_empty(filter
);
1872 data
->filters
= isl_union_set_list_add(data
->filters
, filter
);
1874 return isl_schedule_node_free(node
);
1877 node
= isl_schedule_node_child(node
, 0);
1878 node
= isl_schedule_node_cut(node
);
1879 node
= isl_schedule_node_parent(node
);
1881 } while (isl_schedule_node_has_children(node
) &&
1882 (node
= isl_schedule_node_first_child(node
)) != NULL
);
1887 /* Callback for "traverse" to leave a node for isl_schedule_node_gist.
1889 * In particular, if the current node is a filter node, then we remove
1890 * the element on the "filters" list that was added when we entered
1891 * the node. There is no need to compute any gist here, since we
1892 * already did that when we entered the node.
1894 * If the current node is a band node, then we compute the gist of
1895 * the band node with respect to the intersection of the original context
1896 * and the intermediate filters.
1898 * If the current node is a sequence or set node, then some of
1899 * the filter children may have become empty and so they are removed.
1900 * If only one child is left, then the set or sequence node along with
1901 * the single remaining child filter is removed. The filter can be
1902 * removed because the filters on a sequence or set node are supposed
1903 * to partition the incoming domain instances.
1904 * In principle, it should then be impossible for there to be zero
1905 * remaining children, but should this happen, we replace the entire
1906 * subtree with an empty filter.
1908 static __isl_give isl_schedule_node
*gist_leave(
1909 __isl_take isl_schedule_node
*node
, void *user
)
1911 struct isl_node_gist_data
*data
= user
;
1912 isl_schedule_tree
*tree
;
1914 isl_union_set
*filter
;
1916 switch (isl_schedule_node_get_type(node
)) {
1917 case isl_schedule_node_error
:
1918 return isl_schedule_node_free(node
);
1919 case isl_schedule_node_filter
:
1920 n
= isl_union_set_list_n_union_set(data
->filters
);
1921 data
->filters
= isl_union_set_list_drop(data
->filters
,
1924 case isl_schedule_node_band
:
1925 n
= isl_union_set_list_n_union_set(data
->filters
);
1926 filter
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
1927 node
= isl_schedule_node_band_gist(node
, filter
);
1929 case isl_schedule_node_set
:
1930 case isl_schedule_node_sequence
:
1931 tree
= isl_schedule_node_get_tree(node
);
1932 n
= isl_schedule_tree_n_children(tree
);
1933 for (i
= n
- 1; i
>= 0; --i
) {
1934 isl_schedule_tree
*child
;
1935 isl_union_set
*filter
;
1938 child
= isl_schedule_tree_get_child(tree
, i
);
1939 filter
= isl_schedule_tree_filter_get_filter(child
);
1940 empty
= isl_union_set_is_empty(filter
);
1941 isl_union_set_free(filter
);
1942 isl_schedule_tree_free(child
);
1944 tree
= isl_schedule_tree_free(tree
);
1946 tree
= isl_schedule_tree_drop_child(tree
, i
);
1948 n
= isl_schedule_tree_n_children(tree
);
1949 node
= isl_schedule_node_graft_tree(node
, tree
);
1951 node
= isl_schedule_node_delete(node
);
1952 node
= isl_schedule_node_delete(node
);
1953 } else if (n
== 0) {
1957 isl_union_set_list_get_union_set(data
->filters
, 0);
1958 space
= isl_union_set_get_space(filter
);
1959 isl_union_set_free(filter
);
1960 filter
= isl_union_set_empty(space
);
1961 node
= isl_schedule_node_cut(node
);
1962 node
= isl_schedule_node_insert_filter(node
, filter
);
1965 case isl_schedule_node_domain
:
1966 case isl_schedule_node_leaf
:
1973 /* Compute the gist of the subtree at "node" with respect to
1974 * the reaching domain elements in "context".
1975 * In particular, compute the gist of all band and filter nodes
1976 * in the subtree with respect to "context". Children of set or sequence
1977 * nodes that end up with an empty filter are removed completely.
1979 * We keep track of the intersection of "context" with all outer filters
1980 * of the current node within the subtree in the final element of "filters".
1981 * Initially, this list contains the single element "context" and it is
1982 * extended or shortened each time we enter or leave a filter node.
1984 __isl_give isl_schedule_node
*isl_schedule_node_gist(
1985 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
1987 struct isl_node_gist_data data
;
1989 data
.filters
= isl_union_set_list_from_union_set(context
);
1990 node
= traverse(node
, &gist_enter
, &gist_leave
, &data
);
1991 isl_union_set_list_free(data
.filters
);
1995 /* Intersect the domain of domain node "node" with "domain".
1997 * If the domain of "node" is already a subset of "domain",
1998 * then nothing needs to be changed.
2000 * Otherwise, we replace the domain of the domain node by the intersection
2001 * and simplify the subtree rooted at "node" with respect to this intersection.
2003 __isl_give isl_schedule_node
*isl_schedule_node_domain_intersect_domain(
2004 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
)
2006 isl_schedule_tree
*tree
;
2007 isl_union_set
*uset
;
2010 if (!node
|| !domain
)
2013 uset
= isl_schedule_tree_domain_get_domain(node
->tree
);
2014 is_subset
= isl_union_set_is_subset(uset
, domain
);
2015 isl_union_set_free(uset
);
2019 isl_union_set_free(domain
);
2023 tree
= isl_schedule_tree_copy(node
->tree
);
2024 uset
= isl_schedule_tree_domain_get_domain(tree
);
2025 uset
= isl_union_set_intersect(uset
, domain
);
2026 tree
= isl_schedule_tree_domain_set_domain(tree
,
2027 isl_union_set_copy(uset
));
2028 node
= isl_schedule_node_graft_tree(node
, tree
);
2030 node
= isl_schedule_node_child(node
, 0);
2031 node
= isl_schedule_node_gist(node
, uset
);
2032 node
= isl_schedule_node_parent(node
);
2036 isl_schedule_node_free(node
);
2037 isl_union_set_free(domain
);
2041 /* Reset the user pointer on all identifiers of parameters and tuples
2042 * in the schedule node "node".
2044 __isl_give isl_schedule_node
*isl_schedule_node_reset_user(
2045 __isl_take isl_schedule_node
*node
)
2047 isl_schedule_tree
*tree
;
2049 tree
= isl_schedule_node_get_tree(node
);
2050 tree
= isl_schedule_tree_reset_user(tree
);
2051 node
= isl_schedule_node_graft_tree(node
, tree
);
2056 /* Align the parameters of the schedule node "node" to those of "space".
2058 __isl_give isl_schedule_node
*isl_schedule_node_align_params(
2059 __isl_take isl_schedule_node
*node
, __isl_take isl_space
*space
)
2061 isl_schedule_tree
*tree
;
2063 tree
= isl_schedule_node_get_tree(node
);
2064 tree
= isl_schedule_tree_align_params(tree
, space
);
2065 node
= isl_schedule_node_graft_tree(node
, tree
);
2070 /* Compute the pullback of schedule node "node"
2071 * by the function represented by "upma".
2072 * In other words, plug in "upma" in the iteration domains
2073 * of schedule node "node".
2075 * Note that this is only a helper function for
2076 * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency,
2077 * this function should not be called on a single node without also
2078 * calling it on all the other nodes.
2080 __isl_give isl_schedule_node
*isl_schedule_node_pullback_union_pw_multi_aff(
2081 __isl_take isl_schedule_node
*node
,
2082 __isl_take isl_union_pw_multi_aff
*upma
)
2084 isl_schedule_tree
*tree
;
2086 tree
= isl_schedule_node_get_tree(node
);
2087 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, upma
);
2088 node
= isl_schedule_node_graft_tree(node
, tree
);
2093 /* Return the position of the subtree containing "node" among the children
2094 * of "ancestor". "node" is assumed to be a descendant of "ancestor".
2095 * In particular, both nodes should point to the same schedule tree.
2097 * Return -1 on error.
2099 int isl_schedule_node_get_ancestor_child_position(
2100 __isl_keep isl_schedule_node
*node
,
2101 __isl_keep isl_schedule_node
*ancestor
)
2104 isl_schedule_tree
*tree
;
2106 if (!node
|| !ancestor
)
2109 if (node
->schedule
!= ancestor
->schedule
)
2110 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2111 "not a descendant", return -1);
2113 n1
= isl_schedule_node_get_tree_depth(ancestor
);
2114 n2
= isl_schedule_node_get_tree_depth(node
);
2117 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2118 "not a descendant", return -1);
2119 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n1
);
2120 isl_schedule_tree_free(tree
);
2121 if (tree
!= ancestor
->tree
)
2122 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2123 "not a descendant", return -1);
2125 return node
->child_pos
[n1
];
2128 /* Given two nodes that point to the same schedule tree, return their
2129 * closest shared ancestor.
2131 * Since the two nodes point to the same schedule, they share at least
2132 * one ancestor, the root of the schedule. We move down from the root
2133 * to the first ancestor where the respective children have a different
2134 * child position. This is the requested ancestor.
2135 * If there is no ancestor where the children have a different position,
2136 * then one node is an ancestor of the other and then this node is
2137 * the requested ancestor.
2139 __isl_give isl_schedule_node
*isl_schedule_node_get_shared_ancestor(
2140 __isl_keep isl_schedule_node
*node1
,
2141 __isl_keep isl_schedule_node
*node2
)
2145 if (!node1
|| !node2
)
2147 if (node1
->schedule
!= node2
->schedule
)
2148 isl_die(isl_schedule_node_get_ctx(node1
), isl_error_invalid
,
2149 "not part of same schedule", return NULL
);
2150 n1
= isl_schedule_node_get_tree_depth(node1
);
2151 n2
= isl_schedule_node_get_tree_depth(node2
);
2153 return isl_schedule_node_get_shared_ancestor(node2
, node1
);
2155 return isl_schedule_node_copy(node1
);
2156 if (isl_schedule_node_is_equal(node1
, node2
))
2157 return isl_schedule_node_copy(node1
);
2159 for (i
= 0; i
< n1
; ++i
)
2160 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
2163 node1
= isl_schedule_node_copy(node1
);
2164 return isl_schedule_node_ancestor(node1
, n1
- i
);
2167 /* Print "node" to "p".
2169 __isl_give isl_printer
*isl_printer_print_schedule_node(
2170 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
2173 return isl_printer_free(p
);
2174 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
,
2175 isl_schedule_tree_list_n_schedule_tree(node
->ancestors
),
2179 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
2182 isl_printer
*printer
;
2187 ctx
= isl_schedule_node_get_ctx(node
);
2188 printer
= isl_printer_to_file(ctx
, stderr
);
2189 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
2190 printer
= isl_printer_print_schedule_node(printer
, node
);
2192 isl_printer_free(printer
);