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 a pointer to the root of a schedule tree with as single
74 * node a extension node with the given extension.
76 __isl_give isl_schedule_node
*isl_schedule_node_from_extension(
77 __isl_take isl_union_map
*extension
)
80 isl_schedule
*schedule
;
81 isl_schedule_tree
*tree
;
82 isl_schedule_node
*node
;
87 ctx
= isl_union_map_get_ctx(extension
);
88 tree
= isl_schedule_tree_from_extension(extension
);
89 schedule
= isl_schedule_from_schedule_tree(ctx
, tree
);
90 node
= isl_schedule_get_root(schedule
);
91 isl_schedule_free(schedule
);
96 /* Return the isl_ctx to which "node" belongs.
98 isl_ctx
*isl_schedule_node_get_ctx(__isl_keep isl_schedule_node
*node
)
100 return node
? isl_schedule_get_ctx(node
->schedule
) : NULL
;
103 /* Return a pointer to the leaf of the schedule into which "node" points.
105 * Even though these leaves are not reference counted, we still
106 * indicate that this function does not return a copy.
108 __isl_keep isl_schedule_tree
*isl_schedule_node_peek_leaf(
109 __isl_keep isl_schedule_node
*node
)
111 return node
? isl_schedule_peek_leaf(node
->schedule
) : NULL
;
114 /* Return a pointer to the leaf of the schedule into which "node" points.
116 * Even though these leaves are not reference counted, we still
117 * return a "copy" of the leaf here such that it can still be "freed"
120 __isl_give isl_schedule_tree
*isl_schedule_node_get_leaf(
121 __isl_keep isl_schedule_node
*node
)
123 return isl_schedule_tree_copy(isl_schedule_node_peek_leaf(node
));
126 /* Return the type of the node or isl_schedule_node_error on error.
128 enum isl_schedule_node_type
isl_schedule_node_get_type(
129 __isl_keep isl_schedule_node
*node
)
131 return node
? isl_schedule_tree_get_type(node
->tree
)
132 : isl_schedule_node_error
;
135 /* Return the type of the parent of "node" or isl_schedule_node_error on error.
137 enum isl_schedule_node_type
isl_schedule_node_get_parent_type(
138 __isl_keep isl_schedule_node
*node
)
142 isl_schedule_tree
*parent
;
143 enum isl_schedule_node_type type
;
146 return isl_schedule_node_error
;
147 has_parent
= isl_schedule_node_has_parent(node
);
149 return isl_schedule_node_error
;
151 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
152 "node has no parent", return isl_schedule_node_error
);
154 pos
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) - 1;
155 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, pos
);
156 type
= isl_schedule_tree_get_type(parent
);
157 isl_schedule_tree_free(parent
);
162 /* Return a copy of the subtree that this node points to.
164 __isl_give isl_schedule_tree
*isl_schedule_node_get_tree(
165 __isl_keep isl_schedule_node
*node
)
170 return isl_schedule_tree_copy(node
->tree
);
173 /* Return a copy of the schedule into which "node" points.
175 __isl_give isl_schedule
*isl_schedule_node_get_schedule(
176 __isl_keep isl_schedule_node
*node
)
180 return isl_schedule_copy(node
->schedule
);
183 /* Return a fresh copy of "node".
185 __isl_take isl_schedule_node
*isl_schedule_node_dup(
186 __isl_keep isl_schedule_node
*node
)
191 return isl_schedule_node_alloc(isl_schedule_copy(node
->schedule
),
192 isl_schedule_tree_copy(node
->tree
),
193 isl_schedule_tree_list_copy(node
->ancestors
),
197 /* Return an isl_schedule_node that is equal to "node" and that has only
198 * a single reference.
200 __isl_give isl_schedule_node
*isl_schedule_node_cow(
201 __isl_take isl_schedule_node
*node
)
209 return isl_schedule_node_dup(node
);
212 /* Return a new reference to "node".
214 __isl_give isl_schedule_node
*isl_schedule_node_copy(
215 __isl_keep isl_schedule_node
*node
)
224 /* Free "node" and return NULL.
226 * Since the node may point to a leaf of its schedule, which
227 * point to a field inside the schedule, we need to make sure
228 * we free the tree before freeing the schedule.
230 __isl_null isl_schedule_node
*isl_schedule_node_free(
231 __isl_take isl_schedule_node
*node
)
238 isl_schedule_tree_list_free(node
->ancestors
);
239 free(node
->child_pos
);
240 isl_schedule_tree_free(node
->tree
);
241 isl_schedule_free(node
->schedule
);
247 /* Do "node1" and "node2" point to the same position in the same
250 isl_bool
isl_schedule_node_is_equal(__isl_keep isl_schedule_node
*node1
,
251 __isl_keep isl_schedule_node
*node2
)
255 if (!node1
|| !node2
)
256 return isl_bool_error
;
258 return isl_bool_true
;
259 if (node1
->schedule
!= node2
->schedule
)
260 return isl_bool_false
;
262 n1
= isl_schedule_node_get_tree_depth(node1
);
263 n2
= isl_schedule_node_get_tree_depth(node2
);
265 return isl_bool_false
;
266 for (i
= 0; i
< n1
; ++i
)
267 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
268 return isl_bool_false
;
270 return isl_bool_true
;
273 /* Return the number of outer schedule dimensions of "node"
274 * in its schedule tree.
276 * Return -1 on error.
278 int isl_schedule_node_get_schedule_depth(__isl_keep isl_schedule_node
*node
)
286 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
287 for (i
= n
- 1; i
>= 0; --i
) {
288 isl_schedule_tree
*tree
;
290 tree
= isl_schedule_tree_list_get_schedule_tree(
294 if (tree
->type
== isl_schedule_node_band
)
295 depth
+= isl_schedule_tree_band_n_member(tree
);
296 isl_schedule_tree_free(tree
);
302 /* Internal data structure for
303 * isl_schedule_node_get_prefix_schedule_union_pw_multi_aff
305 * "initialized" is set if the filter field has been initialized.
306 * If "universe_domain" is not set, then the collected filter is intersected
307 * with the the domain of the root domain node.
308 * "universe_filter" is set if we are only collecting the universes of filters
309 * "collect_prefix" is set if we are collecting prefixes.
310 * "filter" collects all outer filters and is NULL until "initialized" is set.
311 * "prefix" collects all outer band partial schedules (if "collect_prefix"
312 * is set). If it is used, then it is initialized by the caller
313 * of collect_filter_prefix to a zero-dimensional function.
315 struct isl_schedule_node_get_filter_prefix_data
{
320 isl_union_set
*filter
;
321 isl_multi_union_pw_aff
*prefix
;
324 static int collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
325 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
);
327 /* Update the filter and prefix information in "data" based on the first "n"
328 * elements in "list" and the expansion tree root "tree".
330 * We first collect the information from the elements in "list",
331 * initializing the filter based on the domain of the expansion.
332 * Then we map the results to the expanded space and combined them
333 * with the results already in "data".
335 static int collect_filter_prefix_expansion(__isl_take isl_schedule_tree
*tree
,
336 __isl_keep isl_schedule_tree_list
*list
, int n
,
337 struct isl_schedule_node_get_filter_prefix_data
*data
)
339 struct isl_schedule_node_get_filter_prefix_data contracted
;
340 isl_union_pw_multi_aff
*c
;
341 isl_union_map
*exp
, *universe
;
342 isl_union_set
*filter
;
344 c
= isl_schedule_tree_expansion_get_contraction(tree
);
345 exp
= isl_schedule_tree_expansion_get_expansion(tree
);
347 contracted
.initialized
= 1;
348 contracted
.universe_domain
= data
->universe_domain
;
349 contracted
.universe_filter
= data
->universe_filter
;
350 contracted
.collect_prefix
= data
->collect_prefix
;
351 universe
= isl_union_map_universe(isl_union_map_copy(exp
));
352 filter
= isl_union_map_domain(universe
);
353 if (data
->collect_prefix
) {
354 isl_space
*space
= isl_union_set_get_space(filter
);
355 space
= isl_space_set_from_params(space
);
356 contracted
.prefix
= isl_multi_union_pw_aff_zero(space
);
358 contracted
.filter
= filter
;
360 if (collect_filter_prefix(list
, n
, &contracted
) < 0)
361 contracted
.filter
= isl_union_set_free(contracted
.filter
);
362 if (data
->collect_prefix
) {
363 isl_multi_union_pw_aff
*prefix
;
365 prefix
= contracted
.prefix
;
367 isl_multi_union_pw_aff_pullback_union_pw_multi_aff(prefix
,
368 isl_union_pw_multi_aff_copy(c
));
369 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(
370 prefix
, data
->prefix
);
372 filter
= contracted
.filter
;
373 if (data
->universe_domain
)
374 filter
= isl_union_set_preimage_union_pw_multi_aff(filter
,
375 isl_union_pw_multi_aff_copy(c
));
377 filter
= isl_union_set_apply(filter
, isl_union_map_copy(exp
));
378 if (!data
->initialized
)
379 data
->filter
= filter
;
381 data
->filter
= isl_union_set_intersect(filter
, data
->filter
);
382 data
->initialized
= 1;
384 isl_union_pw_multi_aff_free(c
);
385 isl_union_map_free(exp
);
386 isl_schedule_tree_free(tree
);
391 /* Update the filter information in "data" based on the first "n"
392 * elements in "list" and the extension tree root "tree", in case
393 * data->universe_domain is set and data->collect_prefix is not.
395 * We collect the universe domain of the elements in "list" and
396 * add it to the universe range of the extension (intersected
397 * with the already collected filter, if any).
399 static int collect_universe_domain_extension(__isl_take isl_schedule_tree
*tree
,
400 __isl_keep isl_schedule_tree_list
*list
, int n
,
401 struct isl_schedule_node_get_filter_prefix_data
*data
)
403 struct isl_schedule_node_get_filter_prefix_data data_outer
;
404 isl_union_map
*extension
;
405 isl_union_set
*filter
;
407 data_outer
.initialized
= 0;
408 data_outer
.universe_domain
= 1;
409 data_outer
.universe_filter
= data
->universe_filter
;
410 data_outer
.collect_prefix
= 0;
411 data_outer
.filter
= NULL
;
412 data_outer
.prefix
= NULL
;
414 if (collect_filter_prefix(list
, n
, &data_outer
) < 0)
415 data_outer
.filter
= isl_union_set_free(data_outer
.filter
);
417 extension
= isl_schedule_tree_extension_get_extension(tree
);
418 extension
= isl_union_map_universe(extension
);
419 filter
= isl_union_map_range(extension
);
420 if (data_outer
.initialized
)
421 filter
= isl_union_set_union(filter
, data_outer
.filter
);
422 if (data
->initialized
)
423 filter
= isl_union_set_intersect(filter
, data
->filter
);
425 data
->filter
= filter
;
427 isl_schedule_tree_free(tree
);
432 /* Update "data" based on the tree node "tree" in case "data" has
433 * not been initialized yet.
435 * Return 0 on success and -1 on error.
437 * If "tree" is a filter, then we set data->filter to this filter
439 * If "tree" is a domain, then this means we have reached the root
440 * of the schedule tree without being able to extract any information.
441 * We therefore initialize data->filter to the universe of the domain,
442 * or the domain itself if data->universe_domain is not set.
443 * If "tree" is a band with at least one member, then we set data->filter
444 * to the universe of the schedule domain and replace the zero-dimensional
445 * data->prefix by the band schedule (if data->collect_prefix is set).
447 static int collect_filter_prefix_init(__isl_keep isl_schedule_tree
*tree
,
448 struct isl_schedule_node_get_filter_prefix_data
*data
)
450 enum isl_schedule_node_type type
;
451 isl_multi_union_pw_aff
*mupa
;
452 isl_union_set
*filter
;
454 type
= isl_schedule_tree_get_type(tree
);
456 case isl_schedule_node_error
:
458 case isl_schedule_node_expansion
:
459 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
460 "should be handled by caller", return -1);
461 case isl_schedule_node_extension
:
462 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
463 "cannot handle extension nodes", return -1);
464 case isl_schedule_node_context
:
465 case isl_schedule_node_leaf
:
466 case isl_schedule_node_guard
:
467 case isl_schedule_node_mark
:
468 case isl_schedule_node_sequence
:
469 case isl_schedule_node_set
:
471 case isl_schedule_node_domain
:
472 filter
= isl_schedule_tree_domain_get_domain(tree
);
473 if (data
->universe_domain
)
474 filter
= isl_union_set_universe(filter
);
475 data
->filter
= filter
;
477 case isl_schedule_node_band
:
478 if (isl_schedule_tree_band_n_member(tree
) == 0)
480 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
481 if (data
->collect_prefix
) {
482 isl_multi_union_pw_aff_free(data
->prefix
);
483 mupa
= isl_multi_union_pw_aff_reset_tuple_id(mupa
,
485 data
->prefix
= isl_multi_union_pw_aff_copy(mupa
);
487 filter
= isl_multi_union_pw_aff_domain(mupa
);
488 filter
= isl_union_set_universe(filter
);
489 data
->filter
= filter
;
491 case isl_schedule_node_filter
:
492 filter
= isl_schedule_tree_filter_get_filter(tree
);
493 if (data
->universe_filter
)
494 filter
= isl_union_set_universe(filter
);
495 data
->filter
= filter
;
499 if ((data
->collect_prefix
&& !data
->prefix
) || !data
->filter
)
502 data
->initialized
= 1;
507 /* Update "data" based on the tree node "tree" in case "data" has
508 * already been initialized.
510 * Return 0 on success and -1 on error.
512 * If "tree" is a domain and data->universe_domain is not set, then
513 * intersect data->filter with the domain.
514 * If "tree" is a filter, then we intersect data->filter with this filter
516 * If "tree" is a band with at least one member and data->collect_prefix
517 * is set, then we extend data->prefix with the band schedule.
518 * If "tree" is an extension, then we make sure that we are not collecting
519 * information on any extended domain elements.
521 static int collect_filter_prefix_update(__isl_keep isl_schedule_tree
*tree
,
522 struct isl_schedule_node_get_filter_prefix_data
*data
)
524 enum isl_schedule_node_type type
;
525 isl_multi_union_pw_aff
*mupa
;
526 isl_union_set
*filter
;
527 isl_union_map
*extension
;
530 type
= isl_schedule_tree_get_type(tree
);
532 case isl_schedule_node_error
:
534 case isl_schedule_node_expansion
:
535 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
536 "should be handled by caller", return -1);
537 case isl_schedule_node_extension
:
538 extension
= isl_schedule_tree_extension_get_extension(tree
);
539 extension
= isl_union_map_intersect_range(extension
,
540 isl_union_set_copy(data
->filter
));
541 empty
= isl_union_map_is_empty(extension
);
542 isl_union_map_free(extension
);
547 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
548 "cannot handle extension nodes", return -1);
549 case isl_schedule_node_context
:
550 case isl_schedule_node_leaf
:
551 case isl_schedule_node_guard
:
552 case isl_schedule_node_mark
:
553 case isl_schedule_node_sequence
:
554 case isl_schedule_node_set
:
556 case isl_schedule_node_domain
:
557 if (data
->universe_domain
)
559 filter
= isl_schedule_tree_domain_get_domain(tree
);
560 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
562 case isl_schedule_node_band
:
563 if (isl_schedule_tree_band_n_member(tree
) == 0)
565 if (!data
->collect_prefix
)
567 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
568 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(mupa
,
573 case isl_schedule_node_filter
:
574 filter
= isl_schedule_tree_filter_get_filter(tree
);
575 if (data
->universe_filter
)
576 filter
= isl_union_set_universe(filter
);
577 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
586 /* Collect filter and/or prefix information from the first "n"
587 * elements in "list" (which represent the ancestors of a node).
588 * Store the results in "data".
590 * Extension nodes are only supported if they do not affect the outcome,
591 * i.e., if we are collecting information on non-extended domain elements,
592 * or if we are collecting the universe domain (without prefix).
594 * Return 0 on success and -1 on error.
596 * We traverse the list from innermost ancestor (last element)
597 * to outermost ancestor (first element), calling collect_filter_prefix_init
598 * on each node as long as we have not been able to extract any information
599 * yet and collect_filter_prefix_update afterwards.
600 * If we come across an expansion node, then we interrupt the traversal
601 * and call collect_filter_prefix_expansion to restart the traversal
602 * over the remaining ancestors and to combine the results with those
603 * that have already been collected.
604 * If we come across an extension node and we are only computing
605 * the universe domain, then we interrupt the traversal and call
606 * collect_universe_domain_extension to restart the traversal
607 * over the remaining ancestors and to combine the results with those
608 * that have already been collected.
609 * On successful return, data->initialized will be set since the outermost
610 * ancestor is a domain node, which always results in an initialization.
612 static int collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
613 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
)
620 for (i
= n
- 1; i
>= 0; --i
) {
621 isl_schedule_tree
*tree
;
622 enum isl_schedule_node_type type
;
625 tree
= isl_schedule_tree_list_get_schedule_tree(list
, i
);
628 type
= isl_schedule_tree_get_type(tree
);
629 if (type
== isl_schedule_node_expansion
)
630 return collect_filter_prefix_expansion(tree
, list
, i
,
632 if (type
== isl_schedule_node_extension
&&
633 data
->universe_domain
&& !data
->collect_prefix
)
634 return collect_universe_domain_extension(tree
, list
, i
,
636 if (!data
->initialized
)
637 r
= collect_filter_prefix_init(tree
, data
);
639 r
= collect_filter_prefix_update(tree
, data
);
640 isl_schedule_tree_free(tree
);
648 /* Return the concatenation of the partial schedules of all outer band
649 * nodes of "node" interesected with all outer filters
650 * as an isl_multi_union_pw_aff.
651 * None of the ancestors of "node" may be an extension node, unless
652 * there is also a filter ancestor that filters out all the extended
655 * If "node" is pointing at the root of the schedule tree, then
656 * there are no domain elements reaching the current node, so
657 * we return an empty result.
659 * We collect all the filters and partial schedules in collect_filter_prefix
660 * and intersect the domain of the combined schedule with the combined filter.
662 __isl_give isl_multi_union_pw_aff
*
663 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(
664 __isl_keep isl_schedule_node
*node
)
668 struct isl_schedule_node_get_filter_prefix_data data
;
673 space
= isl_schedule_get_space(node
->schedule
);
674 space
= isl_space_set_from_params(space
);
675 if (node
->tree
== node
->schedule
->root
)
676 return isl_multi_union_pw_aff_zero(space
);
678 data
.initialized
= 0;
679 data
.universe_domain
= 1;
680 data
.universe_filter
= 0;
681 data
.collect_prefix
= 1;
683 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
685 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
686 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
687 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
689 data
.prefix
= isl_multi_union_pw_aff_intersect_domain(data
.prefix
,
695 /* Return the concatenation of the partial schedules of all outer band
696 * nodes of "node" interesected with all outer filters
697 * as an isl_union_pw_multi_aff.
698 * None of the ancestors of "node" may be an extension node, unless
699 * there is also a filter ancestor that filters out all the extended
702 * If "node" is pointing at the root of the schedule tree, then
703 * there are no domain elements reaching the current node, so
704 * we return an empty result.
706 * We collect all the filters and partial schedules in collect_filter_prefix.
707 * The partial schedules are collected as an isl_multi_union_pw_aff.
708 * If this isl_multi_union_pw_aff is zero-dimensional, then it does not
709 * contain any domain information, so we construct the isl_union_pw_multi_aff
710 * result as a zero-dimensional function on the collected filter.
711 * Otherwise, we convert the isl_multi_union_pw_aff to
712 * an isl_multi_union_pw_aff and intersect the domain with the filter.
714 __isl_give isl_union_pw_multi_aff
*
715 isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(
716 __isl_keep isl_schedule_node
*node
)
720 isl_union_pw_multi_aff
*prefix
;
721 struct isl_schedule_node_get_filter_prefix_data data
;
726 space
= isl_schedule_get_space(node
->schedule
);
727 if (node
->tree
== node
->schedule
->root
)
728 return isl_union_pw_multi_aff_empty(space
);
730 space
= isl_space_set_from_params(space
);
731 data
.initialized
= 0;
732 data
.universe_domain
= 1;
733 data
.universe_filter
= 0;
734 data
.collect_prefix
= 1;
736 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
738 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
739 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
740 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
743 isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
) == 0) {
744 isl_multi_union_pw_aff_free(data
.prefix
);
745 prefix
= isl_union_pw_multi_aff_from_domain(data
.filter
);
748 isl_union_pw_multi_aff_from_multi_union_pw_aff(data
.prefix
);
749 prefix
= isl_union_pw_multi_aff_intersect_domain(prefix
,
756 /* Return the concatenation of the partial schedules of all outer band
757 * nodes of "node" interesected with all outer filters
758 * as an isl_union_map.
760 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_union_map(
761 __isl_keep isl_schedule_node
*node
)
763 isl_union_pw_multi_aff
*upma
;
765 upma
= isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(node
);
766 return isl_union_map_from_union_pw_multi_aff(upma
);
769 /* Return the concatenation of the partial schedules of all outer band
770 * nodes of "node" intersected with all outer domain constraints.
771 * None of the ancestors of "node" may be an extension node, unless
772 * there is also a filter ancestor that filters out all the extended
775 * Essentially, this functions intersected the domain of the output
776 * of isl_schedule_node_get_prefix_schedule_union_map with the output
777 * of isl_schedule_node_get_domain, except that it only traverses
778 * the ancestors of "node" once.
780 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_relation(
781 __isl_keep isl_schedule_node
*node
)
785 isl_union_map
*prefix
;
786 struct isl_schedule_node_get_filter_prefix_data data
;
791 space
= isl_schedule_get_space(node
->schedule
);
792 if (node
->tree
== node
->schedule
->root
)
793 return isl_union_map_empty(space
);
795 space
= isl_space_set_from_params(space
);
796 data
.initialized
= 0;
797 data
.universe_domain
= 0;
798 data
.universe_filter
= 0;
799 data
.collect_prefix
= 1;
801 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
803 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
804 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
805 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
808 isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
) == 0) {
809 isl_multi_union_pw_aff_free(data
.prefix
);
810 prefix
= isl_union_map_from_domain(data
.filter
);
812 prefix
= isl_union_map_from_multi_union_pw_aff(data
.prefix
);
813 prefix
= isl_union_map_intersect_domain(prefix
, data
.filter
);
819 /* Return the domain elements that reach "node".
821 * If "node" is pointing at the root of the schedule tree, then
822 * there are no domain elements reaching the current node, so
823 * we return an empty result.
824 * None of the ancestors of "node" may be an extension node, unless
825 * there is also a filter ancestor that filters out all the extended
828 * Otherwise, we collect all filters reaching the node,
829 * intersected with the root domain in collect_filter_prefix.
831 __isl_give isl_union_set
*isl_schedule_node_get_domain(
832 __isl_keep isl_schedule_node
*node
)
835 struct isl_schedule_node_get_filter_prefix_data data
;
840 if (node
->tree
== node
->schedule
->root
) {
843 space
= isl_schedule_get_space(node
->schedule
);
844 return isl_union_set_empty(space
);
847 data
.initialized
= 0;
848 data
.universe_domain
= 0;
849 data
.universe_filter
= 0;
850 data
.collect_prefix
= 0;
854 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
855 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
856 data
.filter
= isl_union_set_free(data
.filter
);
861 /* Return the union of universe sets of the domain elements that reach "node".
863 * If "node" is pointing at the root of the schedule tree, then
864 * there are no domain elements reaching the current node, so
865 * we return an empty result.
867 * Otherwise, we collect the universes of all filters reaching the node
868 * in collect_filter_prefix.
870 __isl_give isl_union_set
*isl_schedule_node_get_universe_domain(
871 __isl_keep isl_schedule_node
*node
)
874 struct isl_schedule_node_get_filter_prefix_data data
;
879 if (node
->tree
== node
->schedule
->root
) {
882 space
= isl_schedule_get_space(node
->schedule
);
883 return isl_union_set_empty(space
);
886 data
.initialized
= 0;
887 data
.universe_domain
= 1;
888 data
.universe_filter
= 1;
889 data
.collect_prefix
= 0;
893 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
894 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
895 data
.filter
= isl_union_set_free(data
.filter
);
900 /* Return the subtree schedule of "node".
902 * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle
903 * trees that do not contain any schedule information, we first
904 * move down to the first relevant descendant and handle leaves ourselves.
906 * If the subtree rooted at "node" contains any expansion nodes, then
907 * the returned subtree schedule is formulated in terms of the expanded
909 * The subtree is not allowed to contain any extension nodes.
911 __isl_give isl_union_map
*isl_schedule_node_get_subtree_schedule_union_map(
912 __isl_keep isl_schedule_node
*node
)
914 isl_schedule_tree
*tree
, *leaf
;
917 tree
= isl_schedule_node_get_tree(node
);
918 leaf
= isl_schedule_node_peek_leaf(node
);
919 tree
= isl_schedule_tree_first_schedule_descendant(tree
, leaf
);
923 isl_union_set
*domain
;
924 domain
= isl_schedule_node_get_universe_domain(node
);
925 isl_schedule_tree_free(tree
);
926 return isl_union_map_from_domain(domain
);
929 umap
= isl_schedule_tree_get_subtree_schedule_union_map(tree
);
930 isl_schedule_tree_free(tree
);
934 /* Return the number of ancestors of "node" in its schedule tree.
936 int isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node
*node
)
940 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
943 /* Does "node" have a parent?
945 * That is, does it point to any node of the schedule other than the root?
947 isl_bool
isl_schedule_node_has_parent(__isl_keep isl_schedule_node
*node
)
950 return isl_bool_error
;
951 if (!node
->ancestors
)
952 return isl_bool_error
;
954 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) != 0;
957 /* Return the position of "node" among the children of its parent.
959 int isl_schedule_node_get_child_position(__isl_keep isl_schedule_node
*node
)
966 has_parent
= isl_schedule_node_has_parent(node
);
970 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
971 "node has no parent", return -1);
973 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
974 return node
->child_pos
[n
- 1];
977 /* Does the parent (if any) of "node" have any children with a smaller child
978 * position than this one?
980 isl_bool
isl_schedule_node_has_previous_sibling(
981 __isl_keep isl_schedule_node
*node
)
987 return isl_bool_error
;
988 has_parent
= isl_schedule_node_has_parent(node
);
989 if (has_parent
< 0 || !has_parent
)
992 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
994 return node
->child_pos
[n
- 1] > 0;
997 /* Does the parent (if any) of "node" have any children with a greater child
998 * position than this one?
1000 isl_bool
isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node
*node
)
1003 isl_bool has_parent
;
1004 isl_schedule_tree
*tree
;
1007 return isl_bool_error
;
1008 has_parent
= isl_schedule_node_has_parent(node
);
1009 if (has_parent
< 0 || !has_parent
)
1012 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1013 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
1015 return isl_bool_error
;
1016 n_child
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1017 isl_schedule_tree_free(tree
);
1019 return node
->child_pos
[n
- 1] + 1 < n_child
;
1022 /* Does "node" have any children?
1024 * Any node other than the leaf nodes is considered to have at least
1025 * one child, even if the corresponding isl_schedule_tree does not
1026 * have any children.
1028 isl_bool
isl_schedule_node_has_children(__isl_keep isl_schedule_node
*node
)
1031 return isl_bool_error
;
1032 return !isl_schedule_tree_is_leaf(node
->tree
);
1035 /* Return the number of children of "node"?
1037 * Any node other than the leaf nodes is considered to have at least
1038 * one child, even if the corresponding isl_schedule_tree does not
1039 * have any children. That is, the number of children of "node" is
1040 * only zero if its tree is the explicit empty tree. Otherwise,
1041 * if the isl_schedule_tree has any children, then it is equal
1042 * to the number of children of "node". If it has zero children,
1043 * then "node" still has a leaf node as child.
1045 int isl_schedule_node_n_children(__isl_keep isl_schedule_node
*node
)
1052 if (isl_schedule_tree_is_leaf(node
->tree
))
1055 n
= isl_schedule_tree_n_children(node
->tree
);
1062 /* Move the "node" pointer to the ancestor of the given generation
1063 * of the node it currently points to, where generation 0 is the node
1064 * itself and generation 1 is its parent.
1066 __isl_give isl_schedule_node
*isl_schedule_node_ancestor(
1067 __isl_take isl_schedule_node
*node
, int generation
)
1070 isl_schedule_tree
*tree
;
1074 if (generation
== 0)
1076 n
= isl_schedule_node_get_tree_depth(node
);
1078 return isl_schedule_node_free(node
);
1079 if (generation
< 0 || generation
> n
)
1080 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1081 "generation out of bounds",
1082 return isl_schedule_node_free(node
));
1083 node
= isl_schedule_node_cow(node
);
1087 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1089 isl_schedule_tree_free(node
->tree
);
1091 node
->ancestors
= isl_schedule_tree_list_drop(node
->ancestors
,
1092 n
- generation
, generation
);
1093 if (!node
->ancestors
|| !node
->tree
)
1094 return isl_schedule_node_free(node
);
1099 /* Move the "node" pointer to the parent of the node it currently points to.
1101 __isl_give isl_schedule_node
*isl_schedule_node_parent(
1102 __isl_take isl_schedule_node
*node
)
1106 if (!isl_schedule_node_has_parent(node
))
1107 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1108 "node has no parent",
1109 return isl_schedule_node_free(node
));
1110 return isl_schedule_node_ancestor(node
, 1);
1113 /* Move the "node" pointer to the root of its schedule tree.
1115 __isl_give isl_schedule_node
*isl_schedule_node_root(
1116 __isl_take isl_schedule_node
*node
)
1122 n
= isl_schedule_node_get_tree_depth(node
);
1124 return isl_schedule_node_free(node
);
1125 return isl_schedule_node_ancestor(node
, n
);
1128 /* Move the "node" pointer to the child at position "pos" of the node
1129 * it currently points to.
1131 __isl_give isl_schedule_node
*isl_schedule_node_child(
1132 __isl_take isl_schedule_node
*node
, int pos
)
1136 isl_schedule_tree
*tree
;
1139 node
= isl_schedule_node_cow(node
);
1142 if (!isl_schedule_node_has_children(node
))
1143 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1144 "node has no children",
1145 return isl_schedule_node_free(node
));
1147 ctx
= isl_schedule_node_get_ctx(node
);
1148 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1149 child_pos
= isl_realloc_array(ctx
, node
->child_pos
, int, n
+ 1);
1151 return isl_schedule_node_free(node
);
1152 node
->child_pos
= child_pos
;
1153 node
->child_pos
[n
] = pos
;
1155 node
->ancestors
= isl_schedule_tree_list_add(node
->ancestors
,
1156 isl_schedule_tree_copy(node
->tree
));
1158 if (isl_schedule_tree_has_children(tree
))
1159 tree
= isl_schedule_tree_get_child(tree
, pos
);
1161 tree
= isl_schedule_node_get_leaf(node
);
1162 isl_schedule_tree_free(node
->tree
);
1165 if (!node
->tree
|| !node
->ancestors
)
1166 return isl_schedule_node_free(node
);
1171 /* Move the "node" pointer to the first child of the node
1172 * it currently points to.
1174 __isl_give isl_schedule_node
*isl_schedule_node_first_child(
1175 __isl_take isl_schedule_node
*node
)
1177 return isl_schedule_node_child(node
, 0);
1180 /* Move the "node" pointer to the child of this node's parent in
1181 * the previous child position.
1183 __isl_give isl_schedule_node
*isl_schedule_node_previous_sibling(
1184 __isl_take isl_schedule_node
*node
)
1187 isl_schedule_tree
*parent
, *tree
;
1189 node
= isl_schedule_node_cow(node
);
1192 if (!isl_schedule_node_has_previous_sibling(node
))
1193 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1194 "node has no previous sibling",
1195 return isl_schedule_node_free(node
));
1197 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1198 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1201 return isl_schedule_node_free(node
);
1202 node
->child_pos
[n
- 1]--;
1203 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1204 node
->child_pos
[n
- 1]);
1205 isl_schedule_tree_free(parent
);
1207 return isl_schedule_node_free(node
);
1208 isl_schedule_tree_free(node
->tree
);
1214 /* Move the "node" pointer to the child of this node's parent in
1215 * the next child position.
1217 __isl_give isl_schedule_node
*isl_schedule_node_next_sibling(
1218 __isl_take isl_schedule_node
*node
)
1221 isl_schedule_tree
*parent
, *tree
;
1223 node
= isl_schedule_node_cow(node
);
1226 if (!isl_schedule_node_has_next_sibling(node
))
1227 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1228 "node has no next sibling",
1229 return isl_schedule_node_free(node
));
1231 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1232 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1235 return isl_schedule_node_free(node
);
1236 node
->child_pos
[n
- 1]++;
1237 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1238 node
->child_pos
[n
- 1]);
1239 isl_schedule_tree_free(parent
);
1241 return isl_schedule_node_free(node
);
1242 isl_schedule_tree_free(node
->tree
);
1248 /* Return a copy to the child at position "pos" of "node".
1250 __isl_give isl_schedule_node
*isl_schedule_node_get_child(
1251 __isl_keep isl_schedule_node
*node
, int pos
)
1253 return isl_schedule_node_child(isl_schedule_node_copy(node
), pos
);
1256 /* Traverse the descendant of "node" in depth-first order, including
1257 * "node" itself. Call "enter" whenever a node is entered and "leave"
1258 * whenever a node is left. The callback "enter" is responsible
1259 * for moving to the deepest initial subtree of its argument that
1260 * should be traversed.
1262 static __isl_give isl_schedule_node
*traverse(
1263 __isl_take isl_schedule_node
*node
,
1264 __isl_give isl_schedule_node
*(*enter
)(
1265 __isl_take isl_schedule_node
*node
, void *user
),
1266 __isl_give isl_schedule_node
*(*leave
)(
1267 __isl_take isl_schedule_node
*node
, void *user
),
1275 depth
= isl_schedule_node_get_tree_depth(node
);
1277 node
= enter(node
, user
);
1278 node
= leave(node
, user
);
1279 while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
&&
1280 !isl_schedule_node_has_next_sibling(node
)) {
1281 node
= isl_schedule_node_parent(node
);
1282 node
= leave(node
, user
);
1284 if (node
&& isl_schedule_node_get_tree_depth(node
) > depth
)
1285 node
= isl_schedule_node_next_sibling(node
);
1286 } while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
);
1291 /* Internal data structure for isl_schedule_node_foreach_descendant_top_down.
1293 * "fn" is the user-specified callback function.
1294 * "user" is the user-specified argument for the callback.
1296 struct isl_schedule_node_preorder_data
{
1297 isl_bool (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
);
1301 /* Callback for "traverse" to enter a node and to move
1302 * to the deepest initial subtree that should be traversed
1303 * for use in a preorder visit.
1305 * If the user callback returns a negative value, then we abort
1306 * the traversal. If this callback returns zero, then we skip
1307 * the subtree rooted at the current node. Otherwise, we move
1308 * down to the first child and repeat the process until a leaf
1311 static __isl_give isl_schedule_node
*preorder_enter(
1312 __isl_take isl_schedule_node
*node
, void *user
)
1314 struct isl_schedule_node_preorder_data
*data
= user
;
1322 r
= data
->fn(node
, data
->user
);
1324 return isl_schedule_node_free(node
);
1325 if (r
== isl_bool_false
)
1327 } while (isl_schedule_node_has_children(node
) &&
1328 (node
= isl_schedule_node_first_child(node
)) != NULL
);
1333 /* Callback for "traverse" to leave a node
1334 * for use in a preorder visit.
1335 * Since we already visited the node when we entered it,
1336 * we do not need to do anything here.
1338 static __isl_give isl_schedule_node
*preorder_leave(
1339 __isl_take isl_schedule_node
*node
, void *user
)
1344 /* Traverse the descendants of "node" (including the node itself)
1345 * in depth first preorder.
1347 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1348 * If "fn" returns 0 on any of the nodes, then the subtree rooted
1349 * at that node is skipped.
1351 * Return 0 on success and -1 on failure.
1353 isl_stat
isl_schedule_node_foreach_descendant_top_down(
1354 __isl_keep isl_schedule_node
*node
,
1355 isl_bool (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
),
1358 struct isl_schedule_node_preorder_data data
= { fn
, user
};
1360 node
= isl_schedule_node_copy(node
);
1361 node
= traverse(node
, &preorder_enter
, &preorder_leave
, &data
);
1362 isl_schedule_node_free(node
);
1364 return node
? isl_stat_ok
: isl_stat_error
;
1367 /* Internal data structure for isl_schedule_node_map_descendant_bottom_up.
1369 * "fn" is the user-specified callback function.
1370 * "user" is the user-specified argument for the callback.
1372 struct isl_schedule_node_postorder_data
{
1373 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1378 /* Callback for "traverse" to enter a node and to move
1379 * to the deepest initial subtree that should be traversed
1380 * for use in a postorder visit.
1382 * Since we are performing a postorder visit, we only need
1383 * to move to the deepest initial leaf here.
1385 static __isl_give isl_schedule_node
*postorder_enter(
1386 __isl_take isl_schedule_node
*node
, void *user
)
1388 while (node
&& isl_schedule_node_has_children(node
))
1389 node
= isl_schedule_node_first_child(node
);
1394 /* Callback for "traverse" to leave a node
1395 * for use in a postorder visit.
1397 * Since we are performing a postorder visit, we need
1398 * to call the user callback here.
1400 static __isl_give isl_schedule_node
*postorder_leave(
1401 __isl_take isl_schedule_node
*node
, void *user
)
1403 struct isl_schedule_node_postorder_data
*data
= user
;
1405 return data
->fn(node
, data
->user
);
1408 /* Traverse the descendants of "node" (including the node itself)
1409 * in depth first postorder, allowing the user to modify the visited node.
1410 * The traversal continues from the node returned by the callback function.
1411 * It is the responsibility of the user to ensure that this does not
1412 * lead to an infinite loop. It is safest to always return a pointer
1413 * to the same position (same ancestors and child positions) as the input node.
1415 __isl_give isl_schedule_node
*isl_schedule_node_map_descendant_bottom_up(
1416 __isl_take isl_schedule_node
*node
,
1417 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1418 void *user
), void *user
)
1420 struct isl_schedule_node_postorder_data data
= { fn
, user
};
1422 return traverse(node
, &postorder_enter
, &postorder_leave
, &data
);
1425 /* Traverse the ancestors of "node" from the root down to and including
1426 * the parent of "node", calling "fn" on each of them.
1428 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1430 * Return 0 on success and -1 on failure.
1432 isl_stat
isl_schedule_node_foreach_ancestor_top_down(
1433 __isl_keep isl_schedule_node
*node
,
1434 isl_stat (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
),
1440 return isl_stat_error
;
1442 n
= isl_schedule_node_get_tree_depth(node
);
1443 for (i
= 0; i
< n
; ++i
) {
1444 isl_schedule_node
*ancestor
;
1447 ancestor
= isl_schedule_node_copy(node
);
1448 ancestor
= isl_schedule_node_ancestor(ancestor
, n
- i
);
1449 r
= fn(ancestor
, user
);
1450 isl_schedule_node_free(ancestor
);
1452 return isl_stat_error
;
1458 /* Is any node in the subtree rooted at "node" anchored?
1459 * That is, do any of these nodes reference the outer band nodes?
1461 isl_bool
isl_schedule_node_is_subtree_anchored(
1462 __isl_keep isl_schedule_node
*node
)
1465 return isl_bool_error
;
1466 return isl_schedule_tree_is_subtree_anchored(node
->tree
);
1469 /* Return the number of members in the given band node.
1471 unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node
*node
)
1473 return node
? isl_schedule_tree_band_n_member(node
->tree
) : 0;
1476 /* Is the band member at position "pos" of the band node "node"
1477 * marked coincident?
1479 isl_bool
isl_schedule_node_band_member_get_coincident(
1480 __isl_keep isl_schedule_node
*node
, int pos
)
1483 return isl_bool_error
;
1484 return isl_schedule_tree_band_member_get_coincident(node
->tree
, pos
);
1487 /* Mark the band member at position "pos" the band node "node"
1488 * as being coincident or not according to "coincident".
1490 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_coincident(
1491 __isl_take isl_schedule_node
*node
, int pos
, int coincident
)
1494 isl_schedule_tree
*tree
;
1498 c
= isl_schedule_node_band_member_get_coincident(node
, pos
);
1499 if (c
== coincident
)
1502 tree
= isl_schedule_tree_copy(node
->tree
);
1503 tree
= isl_schedule_tree_band_member_set_coincident(tree
, pos
,
1505 node
= isl_schedule_node_graft_tree(node
, tree
);
1510 /* Is the band node "node" marked permutable?
1512 isl_bool
isl_schedule_node_band_get_permutable(
1513 __isl_keep isl_schedule_node
*node
)
1516 return isl_bool_error
;
1518 return isl_schedule_tree_band_get_permutable(node
->tree
);
1521 /* Mark the band node "node" permutable or not according to "permutable"?
1523 __isl_give isl_schedule_node
*isl_schedule_node_band_set_permutable(
1524 __isl_take isl_schedule_node
*node
, int permutable
)
1526 isl_schedule_tree
*tree
;
1530 if (isl_schedule_node_band_get_permutable(node
) == permutable
)
1533 tree
= isl_schedule_tree_copy(node
->tree
);
1534 tree
= isl_schedule_tree_band_set_permutable(tree
, permutable
);
1535 node
= isl_schedule_node_graft_tree(node
, tree
);
1540 /* Return the schedule space of the band node.
1542 __isl_give isl_space
*isl_schedule_node_band_get_space(
1543 __isl_keep isl_schedule_node
*node
)
1548 return isl_schedule_tree_band_get_space(node
->tree
);
1551 /* Return the schedule of the band node in isolation.
1553 __isl_give isl_multi_union_pw_aff
*isl_schedule_node_band_get_partial_schedule(
1554 __isl_keep isl_schedule_node
*node
)
1559 return isl_schedule_tree_band_get_partial_schedule(node
->tree
);
1562 /* Return the schedule of the band node in isolation in the form of
1565 * If the band does not have any members, then we construct a universe map
1566 * with the universe of the domain elements reaching the node as domain.
1567 * Otherwise, we extract an isl_multi_union_pw_aff representation and
1568 * convert that to an isl_union_map.
1570 __isl_give isl_union_map
*isl_schedule_node_band_get_partial_schedule_union_map(
1571 __isl_keep isl_schedule_node
*node
)
1573 isl_multi_union_pw_aff
*mupa
;
1578 if (isl_schedule_node_get_type(node
) != isl_schedule_node_band
)
1579 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1580 "not a band node", return NULL
);
1581 if (isl_schedule_node_band_n_member(node
) == 0) {
1582 isl_union_set
*domain
;
1584 domain
= isl_schedule_node_get_universe_domain(node
);
1585 return isl_union_map_from_domain(domain
);
1588 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
1589 return isl_union_map_from_multi_union_pw_aff(mupa
);
1592 /* Return the loop AST generation type for the band member of band node "node"
1593 * at position "pos".
1595 enum isl_ast_loop_type
isl_schedule_node_band_member_get_ast_loop_type(
1596 __isl_keep isl_schedule_node
*node
, int pos
)
1599 return isl_ast_loop_error
;
1601 return isl_schedule_tree_band_member_get_ast_loop_type(node
->tree
, pos
);
1604 /* Set the loop AST generation type for the band member of band node "node"
1605 * at position "pos" to "type".
1607 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_ast_loop_type(
1608 __isl_take isl_schedule_node
*node
, int pos
,
1609 enum isl_ast_loop_type type
)
1611 isl_schedule_tree
*tree
;
1616 tree
= isl_schedule_tree_copy(node
->tree
);
1617 tree
= isl_schedule_tree_band_member_set_ast_loop_type(tree
, pos
, type
);
1618 return isl_schedule_node_graft_tree(node
, tree
);
1621 /* Return the loop AST generation type for the band member of band node "node"
1622 * at position "pos" for the isolated part.
1624 enum isl_ast_loop_type
isl_schedule_node_band_member_get_isolate_ast_loop_type(
1625 __isl_keep isl_schedule_node
*node
, int pos
)
1628 return isl_ast_loop_error
;
1630 return isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1634 /* Set the loop AST generation type for the band member of band node "node"
1635 * at position "pos" for the isolated part to "type".
1637 __isl_give isl_schedule_node
*
1638 isl_schedule_node_band_member_set_isolate_ast_loop_type(
1639 __isl_take isl_schedule_node
*node
, int pos
,
1640 enum isl_ast_loop_type type
)
1642 isl_schedule_tree
*tree
;
1647 tree
= isl_schedule_tree_copy(node
->tree
);
1648 tree
= isl_schedule_tree_band_member_set_isolate_ast_loop_type(tree
,
1650 return isl_schedule_node_graft_tree(node
, tree
);
1653 /* Return the AST build options associated to band node "node".
1655 __isl_give isl_union_set
*isl_schedule_node_band_get_ast_build_options(
1656 __isl_keep isl_schedule_node
*node
)
1661 return isl_schedule_tree_band_get_ast_build_options(node
->tree
);
1664 /* Replace the AST build options associated to band node "node" by "options".
1666 __isl_give isl_schedule_node
*isl_schedule_node_band_set_ast_build_options(
1667 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*options
)
1669 isl_schedule_tree
*tree
;
1671 if (!node
|| !options
)
1674 tree
= isl_schedule_tree_copy(node
->tree
);
1675 tree
= isl_schedule_tree_band_set_ast_build_options(tree
, options
);
1676 return isl_schedule_node_graft_tree(node
, tree
);
1678 isl_schedule_node_free(node
);
1679 isl_union_set_free(options
);
1683 /* Make sure that that spaces of "node" and "mv" are the same.
1684 * Return -1 on error, reporting the error to the user.
1686 static int check_space_multi_val(__isl_keep isl_schedule_node
*node
,
1687 __isl_keep isl_multi_val
*mv
)
1689 isl_space
*node_space
, *mv_space
;
1692 node_space
= isl_schedule_node_band_get_space(node
);
1693 mv_space
= isl_multi_val_get_space(mv
);
1694 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1695 mv_space
, isl_dim_set
);
1696 isl_space_free(mv_space
);
1697 isl_space_free(node_space
);
1701 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1702 "spaces don't match", return -1);
1707 /* Multiply the partial schedule of the band node "node"
1708 * with the factors in "mv".
1710 __isl_give isl_schedule_node
*isl_schedule_node_band_scale(
1711 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1713 isl_schedule_tree
*tree
;
1718 if (check_space_multi_val(node
, mv
) < 0)
1720 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1724 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1725 "cannot scale band node with anchored subtree",
1728 tree
= isl_schedule_node_get_tree(node
);
1729 tree
= isl_schedule_tree_band_scale(tree
, mv
);
1730 return isl_schedule_node_graft_tree(node
, tree
);
1732 isl_multi_val_free(mv
);
1733 isl_schedule_node_free(node
);
1737 /* Divide the partial schedule of the band node "node"
1738 * by the factors in "mv".
1740 __isl_give isl_schedule_node
*isl_schedule_node_band_scale_down(
1741 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1743 isl_schedule_tree
*tree
;
1748 if (check_space_multi_val(node
, mv
) < 0)
1750 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1754 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1755 "cannot scale down band node with anchored subtree",
1758 tree
= isl_schedule_node_get_tree(node
);
1759 tree
= isl_schedule_tree_band_scale_down(tree
, mv
);
1760 return isl_schedule_node_graft_tree(node
, tree
);
1762 isl_multi_val_free(mv
);
1763 isl_schedule_node_free(node
);
1767 /* Reduce the partial schedule of the band node "node"
1768 * modulo the factors in "mv".
1770 __isl_give isl_schedule_node
*isl_schedule_node_band_mod(
1771 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1773 isl_schedule_tree
*tree
;
1778 if (check_space_multi_val(node
, mv
) < 0)
1780 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1784 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1785 "cannot perform mod on band node with anchored subtree",
1788 tree
= isl_schedule_node_get_tree(node
);
1789 tree
= isl_schedule_tree_band_mod(tree
, mv
);
1790 return isl_schedule_node_graft_tree(node
, tree
);
1792 isl_multi_val_free(mv
);
1793 isl_schedule_node_free(node
);
1797 /* Make sure that that spaces of "node" and "mupa" are the same.
1798 * Return isl_stat_error on error, reporting the error to the user.
1800 static isl_stat
check_space_multi_union_pw_aff(
1801 __isl_keep isl_schedule_node
*node
,
1802 __isl_keep isl_multi_union_pw_aff
*mupa
)
1804 isl_space
*node_space
, *mupa_space
;
1807 node_space
= isl_schedule_node_band_get_space(node
);
1808 mupa_space
= isl_multi_union_pw_aff_get_space(mupa
);
1809 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1810 mupa_space
, isl_dim_set
);
1811 isl_space_free(mupa_space
);
1812 isl_space_free(node_space
);
1814 return isl_stat_error
;
1816 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1817 "spaces don't match", return isl_stat_error
);
1822 /* Shift the partial schedule of the band node "node" by "shift".
1824 __isl_give isl_schedule_node
*isl_schedule_node_band_shift(
1825 __isl_take isl_schedule_node
*node
,
1826 __isl_take isl_multi_union_pw_aff
*shift
)
1828 isl_schedule_tree
*tree
;
1831 if (!node
|| !shift
)
1833 if (check_space_multi_union_pw_aff(node
, shift
) < 0)
1835 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1839 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1840 "cannot shift band node with anchored subtree",
1843 tree
= isl_schedule_node_get_tree(node
);
1844 tree
= isl_schedule_tree_band_shift(tree
, shift
);
1845 return isl_schedule_node_graft_tree(node
, tree
);
1847 isl_multi_union_pw_aff_free(shift
);
1848 isl_schedule_node_free(node
);
1852 /* Tile "node" with tile sizes "sizes".
1854 * The current node is replaced by two nested nodes corresponding
1855 * to the tile dimensions and the point dimensions.
1857 * Return a pointer to the outer (tile) node.
1859 * If any of the descendants of "node" depend on the set of outer band nodes,
1860 * then we refuse to tile the node.
1862 * If the scale tile loops option is set, then the tile loops
1863 * are scaled by the tile sizes. If the shift point loops option is set,
1864 * then the point loops are shifted to start at zero.
1865 * In particular, these options affect the tile and point loop schedules
1868 * scale shift original tile point
1870 * 0 0 i floor(i/s) i
1871 * 1 0 i s * floor(i/s) i
1872 * 0 1 i floor(i/s) i - s * floor(i/s)
1873 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1875 __isl_give isl_schedule_node
*isl_schedule_node_band_tile(
1876 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*sizes
)
1878 isl_schedule_tree
*tree
;
1881 if (!node
|| !sizes
)
1883 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1887 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1888 "cannot tile band node with anchored subtree",
1891 if (check_space_multi_val(node
, sizes
) < 0)
1894 tree
= isl_schedule_node_get_tree(node
);
1895 tree
= isl_schedule_tree_band_tile(tree
, sizes
);
1896 return isl_schedule_node_graft_tree(node
, tree
);
1898 isl_multi_val_free(sizes
);
1899 isl_schedule_node_free(node
);
1903 /* Move the band node "node" down to all the leaves in the subtree
1905 * Return a pointer to the node in the resulting tree that is in the same
1906 * position as the node pointed to by "node" in the original tree.
1908 * If the node only has a leaf child, then nothing needs to be done.
1909 * Otherwise, the child of the node is removed and the result is
1910 * appended to all the leaves in the subtree rooted at the original child.
1911 * The original node is then replaced by the result of this operation.
1913 * If any of the nodes in the subtree rooted at "node" depend on
1914 * the set of outer band nodes then we refuse to sink the band node.
1916 __isl_give isl_schedule_node
*isl_schedule_node_band_sink(
1917 __isl_take isl_schedule_node
*node
)
1919 enum isl_schedule_node_type type
;
1920 isl_schedule_tree
*tree
, *child
;
1926 type
= isl_schedule_node_get_type(node
);
1927 if (type
!= isl_schedule_node_band
)
1928 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1929 "not a band node", isl_schedule_node_free(node
));
1930 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1932 return isl_schedule_node_free(node
);
1934 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1935 "cannot sink band node in anchored subtree",
1936 isl_schedule_node_free(node
));
1937 if (isl_schedule_tree_n_children(node
->tree
) == 0)
1940 tree
= isl_schedule_node_get_tree(node
);
1941 child
= isl_schedule_tree_get_child(tree
, 0);
1942 tree
= isl_schedule_tree_reset_children(tree
);
1943 tree
= isl_schedule_tree_append_to_leaves(child
, tree
);
1945 return isl_schedule_node_graft_tree(node
, tree
);
1948 /* Split "node" into two nested band nodes, one with the first "pos"
1949 * dimensions and one with the remaining dimensions.
1950 * The schedules of the two band nodes live in anonymous spaces.
1952 __isl_give isl_schedule_node
*isl_schedule_node_band_split(
1953 __isl_take isl_schedule_node
*node
, int pos
)
1955 isl_schedule_tree
*tree
;
1957 tree
= isl_schedule_node_get_tree(node
);
1958 tree
= isl_schedule_tree_band_split(tree
, pos
);
1959 return isl_schedule_node_graft_tree(node
, tree
);
1962 /* Return the context of the context node "node".
1964 __isl_give isl_set
*isl_schedule_node_context_get_context(
1965 __isl_keep isl_schedule_node
*node
)
1970 return isl_schedule_tree_context_get_context(node
->tree
);
1973 /* Return the domain of the domain node "node".
1975 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
1976 __isl_keep isl_schedule_node
*node
)
1981 return isl_schedule_tree_domain_get_domain(node
->tree
);
1984 /* Return the expansion map of expansion node "node".
1986 __isl_give isl_union_map
*isl_schedule_node_expansion_get_expansion(
1987 __isl_keep isl_schedule_node
*node
)
1992 return isl_schedule_tree_expansion_get_expansion(node
->tree
);
1995 /* Return the contraction of expansion node "node".
1997 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_expansion_get_contraction(
1998 __isl_keep isl_schedule_node
*node
)
2003 return isl_schedule_tree_expansion_get_contraction(node
->tree
);
2006 /* Replace the contraction and the expansion of the expansion node "node"
2007 * by "contraction" and "expansion".
2009 __isl_give isl_schedule_node
*
2010 isl_schedule_node_expansion_set_contraction_and_expansion(
2011 __isl_take isl_schedule_node
*node
,
2012 __isl_take isl_union_pw_multi_aff
*contraction
,
2013 __isl_take isl_union_map
*expansion
)
2015 isl_schedule_tree
*tree
;
2017 if (!node
|| !contraction
|| !expansion
)
2020 tree
= isl_schedule_tree_copy(node
->tree
);
2021 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
2022 contraction
, expansion
);
2023 return isl_schedule_node_graft_tree(node
, tree
);
2025 isl_schedule_node_free(node
);
2026 isl_union_pw_multi_aff_free(contraction
);
2027 isl_union_map_free(expansion
);
2031 /* Return the extension of the extension node "node".
2033 __isl_give isl_union_map
*isl_schedule_node_extension_get_extension(
2034 __isl_keep isl_schedule_node
*node
)
2039 return isl_schedule_tree_extension_get_extension(node
->tree
);
2042 /* Replace the extension of extension node "node" by "extension".
2044 __isl_give isl_schedule_node
*isl_schedule_node_extension_set_extension(
2045 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
2047 isl_schedule_tree
*tree
;
2049 if (!node
|| !extension
)
2052 tree
= isl_schedule_tree_copy(node
->tree
);
2053 tree
= isl_schedule_tree_extension_set_extension(tree
, extension
);
2054 return isl_schedule_node_graft_tree(node
, tree
);
2056 isl_schedule_node_free(node
);
2057 isl_union_map_free(extension
);
2061 /* Return the filter of the filter node "node".
2063 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
2064 __isl_keep isl_schedule_node
*node
)
2069 return isl_schedule_tree_filter_get_filter(node
->tree
);
2072 /* Replace the filter of filter node "node" by "filter".
2074 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
2075 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2077 isl_schedule_tree
*tree
;
2079 if (!node
|| !filter
)
2082 tree
= isl_schedule_tree_copy(node
->tree
);
2083 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
2084 return isl_schedule_node_graft_tree(node
, tree
);
2086 isl_schedule_node_free(node
);
2087 isl_union_set_free(filter
);
2091 /* Return the guard of the guard node "node".
2093 __isl_give isl_set
*isl_schedule_node_guard_get_guard(
2094 __isl_keep isl_schedule_node
*node
)
2099 return isl_schedule_tree_guard_get_guard(node
->tree
);
2102 /* Return the mark identifier of the mark node "node".
2104 __isl_give isl_id
*isl_schedule_node_mark_get_id(
2105 __isl_keep isl_schedule_node
*node
)
2110 return isl_schedule_tree_mark_get_id(node
->tree
);
2113 /* Replace the child at position "pos" of the sequence node "node"
2114 * by the children of sequence root node of "tree".
2116 __isl_give isl_schedule_node
*isl_schedule_node_sequence_splice(
2117 __isl_take isl_schedule_node
*node
, int pos
,
2118 __isl_take isl_schedule_tree
*tree
)
2120 isl_schedule_tree
*node_tree
;
2124 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2125 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2126 "not a sequence node", goto error
);
2127 if (isl_schedule_tree_get_type(tree
) != isl_schedule_node_sequence
)
2128 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2129 "not a sequence node", goto error
);
2130 node_tree
= isl_schedule_node_get_tree(node
);
2131 node_tree
= isl_schedule_tree_sequence_splice(node_tree
, pos
, tree
);
2132 node
= isl_schedule_node_graft_tree(node
, node_tree
);
2136 isl_schedule_node_free(node
);
2137 isl_schedule_tree_free(tree
);
2141 /* Update the ancestors of "node" to point to the tree that "node"
2143 * That is, replace the child in the original parent that corresponds
2144 * to the current tree position by node->tree and continue updating
2145 * the ancestors in the same way until the root is reached.
2147 * If "fn" is not NULL, then it is called on each ancestor as we move up
2148 * the tree so that it can modify the ancestor before it is added
2149 * to the list of ancestors of the modified node.
2150 * The additional "pos" argument records the position
2151 * of the "tree" argument in the original schedule tree.
2153 * If "node" originally points to a leaf of the schedule tree, then make sure
2154 * that in the end it points to a leaf in the updated schedule tree.
2156 static __isl_give isl_schedule_node
*update_ancestors(
2157 __isl_take isl_schedule_node
*node
,
2158 __isl_give isl_schedule_tree
*(*fn
)(__isl_take isl_schedule_tree
*tree
,
2159 __isl_keep isl_schedule_node
*pos
, void *user
), void *user
)
2164 isl_schedule_tree
*tree
;
2165 isl_schedule_node
*pos
= NULL
;
2168 pos
= isl_schedule_node_copy(node
);
2170 node
= isl_schedule_node_cow(node
);
2172 return isl_schedule_node_free(pos
);
2174 ctx
= isl_schedule_node_get_ctx(node
);
2175 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
2176 tree
= isl_schedule_tree_copy(node
->tree
);
2178 for (i
= n
- 1; i
>= 0; --i
) {
2179 isl_schedule_tree
*parent
;
2181 parent
= isl_schedule_tree_list_get_schedule_tree(
2182 node
->ancestors
, i
);
2183 parent
= isl_schedule_tree_replace_child(parent
,
2184 node
->child_pos
[i
], tree
);
2186 pos
= isl_schedule_node_parent(pos
);
2187 parent
= fn(parent
, pos
, user
);
2189 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
2190 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
2196 isl_schedule_node_free(pos
);
2198 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
2199 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
2201 isl_schedule_tree_free(node
->tree
);
2202 node
->tree
= isl_schedule_node_get_leaf(node
);
2205 if (!node
->schedule
|| !node
->ancestors
)
2206 return isl_schedule_node_free(node
);
2211 /* Replace the subtree that "pos" points to by "tree", updating
2212 * the ancestors to maintain a consistent state.
2214 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
2215 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
2219 if (pos
->tree
== tree
) {
2220 isl_schedule_tree_free(tree
);
2224 pos
= isl_schedule_node_cow(pos
);
2228 isl_schedule_tree_free(pos
->tree
);
2231 return update_ancestors(pos
, NULL
, NULL
);
2233 isl_schedule_node_free(pos
);
2234 isl_schedule_tree_free(tree
);
2238 /* Make sure we can insert a node between "node" and its parent.
2239 * Return -1 on error, reporting the reason why we cannot insert a node.
2241 static int check_insert(__isl_keep isl_schedule_node
*node
)
2244 enum isl_schedule_node_type type
;
2246 has_parent
= isl_schedule_node_has_parent(node
);
2250 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2251 "cannot insert node outside of root", return -1);
2253 type
= isl_schedule_node_get_parent_type(node
);
2254 if (type
== isl_schedule_node_error
)
2256 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
2257 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2258 "cannot insert node between set or sequence node "
2259 "and its filter children", return -1);
2264 /* Insert a band node with partial schedule "mupa" between "node" and
2266 * Return a pointer to the new band node.
2268 * If any of the nodes in the subtree rooted at "node" depend on
2269 * the set of outer band nodes then we refuse to insert the band node.
2271 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
2272 __isl_take isl_schedule_node
*node
,
2273 __isl_take isl_multi_union_pw_aff
*mupa
)
2276 isl_schedule_band
*band
;
2277 isl_schedule_tree
*tree
;
2279 if (check_insert(node
) < 0)
2280 node
= isl_schedule_node_free(node
);
2281 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2285 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2286 "cannot insert band node in anchored subtree",
2289 tree
= isl_schedule_node_get_tree(node
);
2290 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
2291 tree
= isl_schedule_tree_insert_band(tree
, band
);
2292 node
= isl_schedule_node_graft_tree(node
, tree
);
2296 isl_schedule_node_free(node
);
2297 isl_multi_union_pw_aff_free(mupa
);
2301 /* Insert a context node with context "context" between "node" and its parent.
2302 * Return a pointer to the new context node.
2304 __isl_give isl_schedule_node
*isl_schedule_node_insert_context(
2305 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
2307 isl_schedule_tree
*tree
;
2309 if (check_insert(node
) < 0)
2310 node
= isl_schedule_node_free(node
);
2312 tree
= isl_schedule_node_get_tree(node
);
2313 tree
= isl_schedule_tree_insert_context(tree
, context
);
2314 node
= isl_schedule_node_graft_tree(node
, tree
);
2319 /* Insert an expansion node with the given "contraction" and "expansion"
2320 * between "node" and its parent.
2321 * Return a pointer to the new expansion node.
2323 * Typically the domain and range spaces of the expansion are different.
2324 * This means that only one of them can refer to the current domain space
2325 * in a consistent tree. It is up to the caller to ensure that the tree
2326 * returns to a consistent state.
2328 __isl_give isl_schedule_node
*isl_schedule_node_insert_expansion(
2329 __isl_take isl_schedule_node
*node
,
2330 __isl_take isl_union_pw_multi_aff
*contraction
,
2331 __isl_take isl_union_map
*expansion
)
2333 isl_schedule_tree
*tree
;
2335 if (check_insert(node
) < 0)
2336 node
= isl_schedule_node_free(node
);
2338 tree
= isl_schedule_node_get_tree(node
);
2339 tree
= isl_schedule_tree_insert_expansion(tree
, contraction
, expansion
);
2340 node
= isl_schedule_node_graft_tree(node
, tree
);
2345 /* Insert an extension node with extension "extension" between "node" and
2347 * Return a pointer to the new extension node.
2349 __isl_give isl_schedule_node
*isl_schedule_node_insert_extension(
2350 __isl_take isl_schedule_node
*node
,
2351 __isl_take isl_union_map
*extension
)
2353 isl_schedule_tree
*tree
;
2355 tree
= isl_schedule_node_get_tree(node
);
2356 tree
= isl_schedule_tree_insert_extension(tree
, extension
);
2357 node
= isl_schedule_node_graft_tree(node
, tree
);
2362 /* Insert a filter node with filter "filter" between "node" and its parent.
2363 * Return a pointer to the new filter node.
2365 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
2366 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2368 isl_schedule_tree
*tree
;
2370 if (check_insert(node
) < 0)
2371 node
= isl_schedule_node_free(node
);
2373 tree
= isl_schedule_node_get_tree(node
);
2374 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2375 node
= isl_schedule_node_graft_tree(node
, tree
);
2380 /* Insert a guard node with guard "guard" between "node" and its parent.
2381 * Return a pointer to the new guard node.
2383 __isl_give isl_schedule_node
*isl_schedule_node_insert_guard(
2384 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*guard
)
2386 isl_schedule_tree
*tree
;
2388 if (check_insert(node
) < 0)
2389 node
= isl_schedule_node_free(node
);
2391 tree
= isl_schedule_node_get_tree(node
);
2392 tree
= isl_schedule_tree_insert_guard(tree
, guard
);
2393 node
= isl_schedule_node_graft_tree(node
, tree
);
2398 /* Insert a mark node with mark identifier "mark" between "node" and
2400 * Return a pointer to the new mark node.
2402 __isl_give isl_schedule_node
*isl_schedule_node_insert_mark(
2403 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*mark
)
2405 isl_schedule_tree
*tree
;
2407 if (check_insert(node
) < 0)
2408 node
= isl_schedule_node_free(node
);
2410 tree
= isl_schedule_node_get_tree(node
);
2411 tree
= isl_schedule_tree_insert_mark(tree
, mark
);
2412 node
= isl_schedule_node_graft_tree(node
, tree
);
2417 /* Attach the current subtree of "node" to a sequence of filter tree nodes
2418 * with filters described by "filters", attach this sequence
2419 * of filter tree nodes as children to a new tree of type "type" and
2420 * replace the original subtree of "node" by this new tree.
2422 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
2423 __isl_take isl_schedule_node
*node
,
2424 enum isl_schedule_node_type type
,
2425 __isl_take isl_union_set_list
*filters
)
2429 isl_schedule_tree
*tree
;
2430 isl_schedule_tree_list
*list
;
2432 if (check_insert(node
) < 0)
2433 node
= isl_schedule_node_free(node
);
2435 if (!node
|| !filters
)
2438 ctx
= isl_schedule_node_get_ctx(node
);
2439 n
= isl_union_set_list_n_union_set(filters
);
2440 list
= isl_schedule_tree_list_alloc(ctx
, n
);
2441 for (i
= 0; i
< n
; ++i
) {
2442 isl_schedule_tree
*tree
;
2443 isl_union_set
*filter
;
2445 tree
= isl_schedule_node_get_tree(node
);
2446 filter
= isl_union_set_list_get_union_set(filters
, i
);
2447 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2448 list
= isl_schedule_tree_list_add(list
, tree
);
2450 tree
= isl_schedule_tree_from_children(type
, list
);
2451 node
= isl_schedule_node_graft_tree(node
, tree
);
2453 isl_union_set_list_free(filters
);
2456 isl_union_set_list_free(filters
);
2457 isl_schedule_node_free(node
);
2461 /* Insert a sequence node with child filters "filters" between "node" and
2462 * its parent. That is, the tree that "node" points to is attached
2463 * to each of the child nodes of the filter nodes.
2464 * Return a pointer to the new sequence node.
2466 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
2467 __isl_take isl_schedule_node
*node
,
2468 __isl_take isl_union_set_list
*filters
)
2470 return isl_schedule_node_insert_children(node
,
2471 isl_schedule_node_sequence
, filters
);
2474 /* Insert a set node with child filters "filters" between "node" and
2475 * its parent. That is, the tree that "node" points to is attached
2476 * to each of the child nodes of the filter nodes.
2477 * Return a pointer to the new set node.
2479 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
2480 __isl_take isl_schedule_node
*node
,
2481 __isl_take isl_union_set_list
*filters
)
2483 return isl_schedule_node_insert_children(node
,
2484 isl_schedule_node_set
, filters
);
2487 /* Remove "node" from its schedule tree and return a pointer
2488 * to the leaf at the same position in the updated schedule tree.
2490 * It is not allowed to remove the root of a schedule tree or
2491 * a child of a set or sequence node.
2493 __isl_give isl_schedule_node
*isl_schedule_node_cut(
2494 __isl_take isl_schedule_node
*node
)
2496 isl_schedule_tree
*leaf
;
2497 enum isl_schedule_node_type parent_type
;
2501 if (!isl_schedule_node_has_parent(node
))
2502 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2503 "cannot cut root", return isl_schedule_node_free(node
));
2505 parent_type
= isl_schedule_node_get_parent_type(node
);
2506 if (parent_type
== isl_schedule_node_set
||
2507 parent_type
== isl_schedule_node_sequence
)
2508 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2509 "cannot cut child of set or sequence",
2510 return isl_schedule_node_free(node
));
2512 leaf
= isl_schedule_node_get_leaf(node
);
2513 return isl_schedule_node_graft_tree(node
, leaf
);
2516 /* Remove a single node from the schedule tree, attaching the child
2517 * of "node" directly to its parent.
2518 * Return a pointer to this former child or to the leaf the position
2519 * of the original node if there was no child.
2520 * It is not allowed to remove the root of a schedule tree,
2521 * a set or sequence node, a child of a set or sequence node or
2522 * a band node with an anchored subtree.
2524 __isl_give isl_schedule_node
*isl_schedule_node_delete(
2525 __isl_take isl_schedule_node
*node
)
2528 isl_schedule_tree
*tree
;
2529 enum isl_schedule_node_type type
;
2534 if (isl_schedule_node_get_tree_depth(node
) == 0)
2535 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2536 "cannot delete root node",
2537 return isl_schedule_node_free(node
));
2538 n
= isl_schedule_node_n_children(node
);
2540 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2541 "can only delete node with a single child",
2542 return isl_schedule_node_free(node
));
2543 type
= isl_schedule_node_get_parent_type(node
);
2544 if (type
== isl_schedule_node_sequence
|| type
== isl_schedule_node_set
)
2545 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2546 "cannot delete child of set or sequence",
2547 return isl_schedule_node_free(node
));
2548 if (isl_schedule_node_get_type(node
) == isl_schedule_node_band
) {
2551 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2553 return isl_schedule_node_free(node
);
2555 isl_die(isl_schedule_node_get_ctx(node
),
2557 "cannot delete band node with anchored subtree",
2558 return isl_schedule_node_free(node
));
2561 tree
= isl_schedule_node_get_tree(node
);
2562 if (!tree
|| isl_schedule_tree_has_children(tree
)) {
2563 tree
= isl_schedule_tree_child(tree
, 0);
2565 isl_schedule_tree_free(tree
);
2566 tree
= isl_schedule_node_get_leaf(node
);
2568 node
= isl_schedule_node_graft_tree(node
, tree
);
2573 /* Internal data structure for the group_ancestor callback.
2575 * If "finished" is set, then we no longer need to modify
2576 * any further ancestors.
2578 * "contraction" and "expansion" represent the expansion
2579 * that reflects the grouping.
2581 * "domain" contains the domain elements that reach the position
2582 * where the grouping is performed. That is, it is the range
2583 * of the resulting expansion.
2584 * "domain_universe" is the universe of "domain".
2585 * "group" is the set of group elements, i.e., the domain
2586 * of the resulting expansion.
2587 * "group_universe" is the universe of "group".
2589 * "sched" is the schedule for the group elements, in pratice
2590 * an identity mapping on "group_universe".
2591 * "dim" is the dimension of "sched".
2593 struct isl_schedule_group_data
{
2596 isl_union_map
*expansion
;
2597 isl_union_pw_multi_aff
*contraction
;
2599 isl_union_set
*domain
;
2600 isl_union_set
*domain_universe
;
2601 isl_union_set
*group
;
2602 isl_union_set
*group_universe
;
2605 isl_multi_aff
*sched
;
2608 /* Is domain covered by data->domain within data->domain_universe?
2610 static int locally_covered_by_domain(__isl_keep isl_union_set
*domain
,
2611 struct isl_schedule_group_data
*data
)
2614 isl_union_set
*test
;
2616 test
= isl_union_set_copy(domain
);
2617 test
= isl_union_set_intersect(test
,
2618 isl_union_set_copy(data
->domain_universe
));
2619 is_subset
= isl_union_set_is_subset(test
, data
->domain
);
2620 isl_union_set_free(test
);
2625 /* Update the band tree root "tree" to refer to the group instances
2626 * in data->group rather than the original domain elements in data->domain.
2627 * "pos" is the position in the original schedule tree where the modified
2628 * "tree" will be attached.
2630 * Add the part of the identity schedule on the group instances data->sched
2631 * that corresponds to this band node to the band schedule.
2632 * If the domain elements that reach the node and that are part
2633 * of data->domain_universe are all elements of data->domain (and therefore
2634 * replaced by the group instances) then this data->domain_universe
2635 * is removed from the domain of the band schedule.
2637 static __isl_give isl_schedule_tree
*group_band(
2638 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2639 struct isl_schedule_group_data
*data
)
2641 isl_union_set
*domain
;
2643 isl_multi_union_pw_aff
*mupa
, *partial
;
2645 int depth
, n
, has_id
;
2647 domain
= isl_schedule_node_get_domain(pos
);
2648 is_covered
= locally_covered_by_domain(domain
, data
);
2649 if (is_covered
>= 0 && is_covered
) {
2650 domain
= isl_union_set_universe(domain
);
2651 domain
= isl_union_set_subtract(domain
,
2652 isl_union_set_copy(data
->domain_universe
));
2653 tree
= isl_schedule_tree_band_intersect_domain(tree
, domain
);
2655 isl_union_set_free(domain
);
2657 return isl_schedule_tree_free(tree
);
2658 depth
= isl_schedule_node_get_schedule_depth(pos
);
2659 n
= isl_schedule_tree_band_n_member(tree
);
2660 ma
= isl_multi_aff_copy(data
->sched
);
2661 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, depth
);
2662 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, n
, data
->dim
- depth
- n
);
2663 mupa
= isl_multi_union_pw_aff_from_multi_aff(ma
);
2664 partial
= isl_schedule_tree_band_get_partial_schedule(tree
);
2665 has_id
= isl_multi_union_pw_aff_has_tuple_id(partial
, isl_dim_set
);
2667 partial
= isl_multi_union_pw_aff_free(partial
);
2668 } else if (has_id
) {
2670 id
= isl_multi_union_pw_aff_get_tuple_id(partial
, isl_dim_set
);
2671 mupa
= isl_multi_union_pw_aff_set_tuple_id(mupa
,
2674 partial
= isl_multi_union_pw_aff_union_add(partial
, mupa
);
2675 tree
= isl_schedule_tree_band_set_partial_schedule(tree
, partial
);
2680 /* Drop the parameters in "uset" that are not also in "space".
2681 * "n" is the number of parameters in "space".
2683 static __isl_give isl_union_set
*union_set_drop_extra_params(
2684 __isl_take isl_union_set
*uset
, __isl_keep isl_space
*space
, int n
)
2688 uset
= isl_union_set_align_params(uset
, isl_space_copy(space
));
2689 n2
= isl_union_set_dim(uset
, isl_dim_param
);
2690 uset
= isl_union_set_project_out(uset
, isl_dim_param
, n
, n2
- n
);
2695 /* Update the context tree root "tree" to refer to the group instances
2696 * in data->group rather than the original domain elements in data->domain.
2697 * "pos" is the position in the original schedule tree where the modified
2698 * "tree" will be attached.
2700 * We do not actually need to update "tree" since a context node only
2701 * refers to the schedule space. However, we may need to update "data"
2702 * to not refer to any parameters introduced by the context node.
2704 static __isl_give isl_schedule_tree
*group_context(
2705 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2706 struct isl_schedule_group_data
*data
)
2709 isl_union_set
*domain
;
2713 if (isl_schedule_node_get_tree_depth(pos
) == 1)
2716 domain
= isl_schedule_node_get_universe_domain(pos
);
2717 space
= isl_union_set_get_space(domain
);
2718 isl_union_set_free(domain
);
2720 n1
= isl_space_dim(space
, isl_dim_param
);
2721 data
->expansion
= isl_union_map_align_params(data
->expansion
, space
);
2722 n2
= isl_union_map_dim(data
->expansion
, isl_dim_param
);
2724 if (!data
->expansion
)
2725 return isl_schedule_tree_free(tree
);
2729 involves
= isl_union_map_involves_dims(data
->expansion
,
2730 isl_dim_param
, n1
, n2
- n1
);
2732 return isl_schedule_tree_free(tree
);
2734 isl_die(isl_schedule_node_get_ctx(pos
), isl_error_invalid
,
2735 "grouping cannot only refer to global parameters",
2736 return isl_schedule_tree_free(tree
));
2738 data
->expansion
= isl_union_map_project_out(data
->expansion
,
2739 isl_dim_param
, n1
, n2
- n1
);
2740 space
= isl_union_map_get_space(data
->expansion
);
2742 data
->contraction
= isl_union_pw_multi_aff_align_params(
2743 data
->contraction
, isl_space_copy(space
));
2744 n2
= isl_union_pw_multi_aff_dim(data
->contraction
, isl_dim_param
);
2745 data
->contraction
= isl_union_pw_multi_aff_drop_dims(data
->contraction
,
2746 isl_dim_param
, n1
, n2
- n1
);
2748 data
->domain
= union_set_drop_extra_params(data
->domain
, space
, n1
);
2749 data
->domain_universe
=
2750 union_set_drop_extra_params(data
->domain_universe
, space
, n1
);
2751 data
->group
= union_set_drop_extra_params(data
->group
, space
, n1
);
2752 data
->group_universe
=
2753 union_set_drop_extra_params(data
->group_universe
, space
, n1
);
2755 data
->sched
= isl_multi_aff_align_params(data
->sched
,
2756 isl_space_copy(space
));
2757 n2
= isl_multi_aff_dim(data
->sched
, isl_dim_param
);
2758 data
->sched
= isl_multi_aff_drop_dims(data
->sched
,
2759 isl_dim_param
, n1
, n2
- n1
);
2761 isl_space_free(space
);
2766 /* Update the domain tree root "tree" to refer to the group instances
2767 * in data->group rather than the original domain elements in data->domain.
2768 * "pos" is the position in the original schedule tree where the modified
2769 * "tree" will be attached.
2771 * We first double-check that all grouped domain elements are actually
2772 * part of the root domain and then replace those elements by the group
2775 static __isl_give isl_schedule_tree
*group_domain(
2776 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2777 struct isl_schedule_group_data
*data
)
2779 isl_union_set
*domain
;
2782 domain
= isl_schedule_tree_domain_get_domain(tree
);
2783 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2784 isl_union_set_free(domain
);
2786 return isl_schedule_tree_free(tree
);
2788 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2789 "grouped domain should be part of outer domain",
2790 return isl_schedule_tree_free(tree
));
2791 domain
= isl_schedule_tree_domain_get_domain(tree
);
2792 domain
= isl_union_set_subtract(domain
,
2793 isl_union_set_copy(data
->domain
));
2794 domain
= isl_union_set_union(domain
, isl_union_set_copy(data
->group
));
2795 tree
= isl_schedule_tree_domain_set_domain(tree
, domain
);
2800 /* Update the expansion tree root "tree" to refer to the group instances
2801 * in data->group rather than the original domain elements in data->domain.
2802 * "pos" is the position in the original schedule tree where the modified
2803 * "tree" will be attached.
2805 * Let G_1 -> D_1 be the expansion of "tree" and G_2 -> D_2 the newly
2806 * introduced expansion in a descendant of "tree".
2807 * We first double-check that D_2 is a subset of D_1.
2808 * Then we remove D_2 from the range of G_1 -> D_1 and add the mapping
2809 * G_1 -> D_1 . D_2 -> G_2.
2810 * Simmilarly, we restrict the domain of the contraction to the universe
2811 * of the range of the updated expansion and add G_2 -> D_2 . D_1 -> G_1,
2812 * attempting to remove the domain constraints of this additional part.
2814 static __isl_give isl_schedule_tree
*group_expansion(
2815 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2816 struct isl_schedule_group_data
*data
)
2818 isl_union_set
*domain
;
2819 isl_union_map
*expansion
, *umap
;
2820 isl_union_pw_multi_aff
*contraction
, *upma
;
2823 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2824 domain
= isl_union_map_range(expansion
);
2825 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2826 isl_union_set_free(domain
);
2828 return isl_schedule_tree_free(tree
);
2830 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2831 "grouped domain should be part "
2832 "of outer expansion domain",
2833 return isl_schedule_tree_free(tree
));
2834 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2835 umap
= isl_union_map_from_union_pw_multi_aff(
2836 isl_union_pw_multi_aff_copy(data
->contraction
));
2837 umap
= isl_union_map_apply_range(expansion
, umap
);
2838 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2839 expansion
= isl_union_map_subtract_range(expansion
,
2840 isl_union_set_copy(data
->domain
));
2841 expansion
= isl_union_map_union(expansion
, umap
);
2842 umap
= isl_union_map_universe(isl_union_map_copy(expansion
));
2843 domain
= isl_union_map_range(umap
);
2844 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
2845 umap
= isl_union_map_from_union_pw_multi_aff(contraction
);
2846 umap
= isl_union_map_apply_range(isl_union_map_copy(data
->expansion
),
2848 upma
= isl_union_pw_multi_aff_from_union_map(umap
);
2849 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
2850 contraction
= isl_union_pw_multi_aff_intersect_domain(contraction
,
2852 domain
= isl_union_pw_multi_aff_domain(
2853 isl_union_pw_multi_aff_copy(upma
));
2854 upma
= isl_union_pw_multi_aff_gist(upma
, domain
);
2855 contraction
= isl_union_pw_multi_aff_union_add(contraction
, upma
);
2856 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
2857 contraction
, expansion
);
2862 /* Update the tree root "tree" to refer to the group instances
2863 * in data->group rather than the original domain elements in data->domain.
2864 * "pos" is the position in the original schedule tree where the modified
2865 * "tree" will be attached.
2867 * If we have come across a domain or expansion node before (data->finished
2868 * is set), then we no longer need perform any modifications.
2870 * If "tree" is a filter, then we add data->group_universe to the filter.
2871 * We also remove data->domain_universe from the filter if all the domain
2872 * elements in this universe that reach the filter node are part of
2873 * the elements that are being grouped by data->expansion.
2874 * If "tree" is a band, domain or expansion, then it is handled
2875 * in a separate function.
2877 static __isl_give isl_schedule_tree
*group_ancestor(
2878 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2881 struct isl_schedule_group_data
*data
= user
;
2882 isl_union_set
*domain
;
2886 return isl_schedule_tree_free(tree
);
2891 switch (isl_schedule_tree_get_type(tree
)) {
2892 case isl_schedule_node_error
:
2893 return isl_schedule_tree_free(tree
);
2894 case isl_schedule_node_extension
:
2895 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_unsupported
,
2896 "grouping not allowed in extended tree",
2897 return isl_schedule_tree_free(tree
));
2898 case isl_schedule_node_band
:
2899 tree
= group_band(tree
, pos
, data
);
2901 case isl_schedule_node_context
:
2902 tree
= group_context(tree
, pos
, data
);
2904 case isl_schedule_node_domain
:
2905 tree
= group_domain(tree
, pos
, data
);
2908 case isl_schedule_node_filter
:
2909 domain
= isl_schedule_node_get_domain(pos
);
2910 is_covered
= locally_covered_by_domain(domain
, data
);
2911 isl_union_set_free(domain
);
2913 return isl_schedule_tree_free(tree
);
2914 domain
= isl_schedule_tree_filter_get_filter(tree
);
2916 domain
= isl_union_set_subtract(domain
,
2917 isl_union_set_copy(data
->domain_universe
));
2918 domain
= isl_union_set_union(domain
,
2919 isl_union_set_copy(data
->group_universe
));
2920 tree
= isl_schedule_tree_filter_set_filter(tree
, domain
);
2922 case isl_schedule_node_expansion
:
2923 tree
= group_expansion(tree
, pos
, data
);
2926 case isl_schedule_node_leaf
:
2927 case isl_schedule_node_guard
:
2928 case isl_schedule_node_mark
:
2929 case isl_schedule_node_sequence
:
2930 case isl_schedule_node_set
:
2937 /* Group the domain elements that reach "node" into instances
2938 * of a single statement with identifier "group_id".
2939 * In particular, group the domain elements according to their
2942 * That is, introduce an expansion node with as contraction
2943 * the prefix schedule (with the target space replaced by "group_id")
2944 * and as expansion the inverse of this contraction (with its range
2945 * intersected with the domain elements that reach "node").
2946 * The outer nodes are then modified to refer to the group instances
2947 * instead of the original domain elements.
2949 * No instance of "group_id" is allowed to reach "node" prior
2951 * No ancestor of "node" is allowed to be an extension node.
2953 * Return a pointer to original node in tree, i.e., the child
2954 * of the newly introduced expansion node.
2956 __isl_give isl_schedule_node
*isl_schedule_node_group(
2957 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*group_id
)
2959 struct isl_schedule_group_data data
= { 0 };
2961 isl_union_set
*domain
;
2962 isl_union_pw_multi_aff
*contraction
;
2963 isl_union_map
*expansion
;
2966 if (!node
|| !group_id
)
2968 if (check_insert(node
) < 0)
2971 domain
= isl_schedule_node_get_domain(node
);
2972 data
.domain
= isl_union_set_copy(domain
);
2973 data
.domain_universe
= isl_union_set_copy(domain
);
2974 data
.domain_universe
= isl_union_set_universe(data
.domain_universe
);
2976 data
.dim
= isl_schedule_node_get_schedule_depth(node
);
2977 if (data
.dim
== 0) {
2980 isl_union_set
*group
;
2981 isl_union_map
*univ
;
2983 ctx
= isl_schedule_node_get_ctx(node
);
2984 space
= isl_space_set_alloc(ctx
, 0, 0);
2985 space
= isl_space_set_tuple_id(space
, isl_dim_set
, group_id
);
2986 set
= isl_set_universe(isl_space_copy(space
));
2987 group
= isl_union_set_from_set(set
);
2988 expansion
= isl_union_map_from_domain_and_range(domain
, group
);
2989 univ
= isl_union_map_universe(isl_union_map_copy(expansion
));
2990 contraction
= isl_union_pw_multi_aff_from_union_map(univ
);
2991 expansion
= isl_union_map_reverse(expansion
);
2993 isl_multi_union_pw_aff
*prefix
;
2994 isl_union_set
*univ
;
2997 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node
);
2998 prefix
= isl_multi_union_pw_aff_set_tuple_id(prefix
,
2999 isl_dim_set
, group_id
);
3000 space
= isl_multi_union_pw_aff_get_space(prefix
);
3001 contraction
= isl_union_pw_multi_aff_from_multi_union_pw_aff(
3003 univ
= isl_union_set_universe(isl_union_set_copy(domain
));
3005 isl_union_pw_multi_aff_intersect_domain(contraction
, univ
);
3006 expansion
= isl_union_map_from_union_pw_multi_aff(
3007 isl_union_pw_multi_aff_copy(contraction
));
3008 expansion
= isl_union_map_reverse(expansion
);
3009 expansion
= isl_union_map_intersect_range(expansion
, domain
);
3011 space
= isl_space_map_from_set(space
);
3012 data
.sched
= isl_multi_aff_identity(space
);
3013 data
.group
= isl_union_map_domain(isl_union_map_copy(expansion
));
3014 data
.group
= isl_union_set_coalesce(data
.group
);
3015 data
.group_universe
= isl_union_set_copy(data
.group
);
3016 data
.group_universe
= isl_union_set_universe(data
.group_universe
);
3017 data
.expansion
= isl_union_map_copy(expansion
);
3018 data
.contraction
= isl_union_pw_multi_aff_copy(contraction
);
3019 node
= isl_schedule_node_insert_expansion(node
, contraction
, expansion
);
3021 disjoint
= isl_union_set_is_disjoint(data
.domain_universe
,
3022 data
.group_universe
);
3024 node
= update_ancestors(node
, &group_ancestor
, &data
);
3026 isl_union_set_free(data
.domain
);
3027 isl_union_set_free(data
.domain_universe
);
3028 isl_union_set_free(data
.group
);
3029 isl_union_set_free(data
.group_universe
);
3030 isl_multi_aff_free(data
.sched
);
3031 isl_union_map_free(data
.expansion
);
3032 isl_union_pw_multi_aff_free(data
.contraction
);
3034 node
= isl_schedule_node_child(node
, 0);
3036 if (!node
|| disjoint
< 0)
3037 return isl_schedule_node_free(node
);
3039 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3040 "group instances already reach node",
3041 isl_schedule_node_free(node
));
3045 isl_schedule_node_free(node
);
3046 isl_id_free(group_id
);
3050 /* Compute the gist of the given band node with respect to "context".
3052 __isl_give isl_schedule_node
*isl_schedule_node_band_gist(
3053 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3055 isl_schedule_tree
*tree
;
3057 tree
= isl_schedule_node_get_tree(node
);
3058 tree
= isl_schedule_tree_band_gist(tree
, context
);
3059 return isl_schedule_node_graft_tree(node
, tree
);
3062 /* Internal data structure for isl_schedule_node_gist.
3063 * "n_expansion" is the number of outer expansion nodes
3064 * with respect to the current position
3065 * "filters" contains an element for each outer filter, expansion or
3066 * extension node with respect to the current position, each representing
3067 * the intersection of the previous element and the filter on the filter node
3068 * or the expansion/extension of the previous element.
3069 * The first element in the original context passed to isl_schedule_node_gist.
3071 struct isl_node_gist_data
{
3073 isl_union_set_list
*filters
;
3076 /* Enter the expansion node "node" during a isl_schedule_node_gist traversal.
3078 * In particular, add an extra element to data->filters containing
3079 * the expansion of the previous element and replace the expansion
3080 * and contraction on "node" by the gist with respect to these filters.
3081 * Also keep track of the fact that we have entered another expansion.
3083 static __isl_give isl_schedule_node
*gist_enter_expansion(
3084 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3087 isl_union_set
*inner
;
3088 isl_union_map
*expansion
;
3089 isl_union_pw_multi_aff
*contraction
;
3091 data
->n_expansion
++;
3093 n
= isl_union_set_list_n_union_set(data
->filters
);
3094 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3095 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3096 inner
= isl_union_set_apply(inner
, expansion
);
3098 contraction
= isl_schedule_node_expansion_get_contraction(node
);
3099 contraction
= isl_union_pw_multi_aff_gist(contraction
,
3100 isl_union_set_copy(inner
));
3102 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
3104 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3105 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3106 expansion
= isl_union_map_gist_domain(expansion
, inner
);
3107 node
= isl_schedule_node_expansion_set_contraction_and_expansion(node
,
3108 contraction
, expansion
);
3113 /* Enter the extension node "node" during a isl_schedule_node_gist traversal.
3115 * In particular, add an extra element to data->filters containing
3116 * the union of the previous element with the additional domain elements
3117 * introduced by the extension.
3119 static __isl_give isl_schedule_node
*gist_enter_extension(
3120 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3123 isl_union_set
*inner
, *extra
;
3124 isl_union_map
*extension
;
3126 n
= isl_union_set_list_n_union_set(data
->filters
);
3127 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3128 extension
= isl_schedule_node_extension_get_extension(node
);
3129 extra
= isl_union_map_range(extension
);
3130 inner
= isl_union_set_union(inner
, extra
);
3132 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
3137 /* Can we finish gisting at this node?
3138 * That is, is the filter on the current filter node a subset of
3139 * the original context passed to isl_schedule_node_gist?
3140 * If we have gone through any expansions, then we cannot perform
3141 * this test since the current domain elements are incomparable
3142 * to the domain elements in the original context.
3144 static int gist_done(__isl_keep isl_schedule_node
*node
,
3145 struct isl_node_gist_data
*data
)
3147 isl_union_set
*filter
, *outer
;
3150 if (data
->n_expansion
!= 0)
3153 filter
= isl_schedule_node_filter_get_filter(node
);
3154 outer
= isl_union_set_list_get_union_set(data
->filters
, 0);
3155 subset
= isl_union_set_is_subset(filter
, outer
);
3156 isl_union_set_free(outer
);
3157 isl_union_set_free(filter
);
3162 /* Callback for "traverse" to enter a node and to move
3163 * to the deepest initial subtree that should be traversed
3164 * by isl_schedule_node_gist.
3166 * The "filters" list is extended by one element each time
3167 * we come across a filter node by the result of intersecting
3168 * the last element in the list with the filter on the filter node.
3170 * If the filter on the current filter node is a subset of
3171 * the original context passed to isl_schedule_node_gist,
3172 * then there is no need to go into its subtree since it cannot
3173 * be further simplified by the context. The "filters" list is
3174 * still extended for consistency, but the actual value of the
3175 * added element is immaterial since it will not be used.
3177 * Otherwise, the filter on the current filter node is replaced by
3178 * the gist of the original filter with respect to the intersection
3179 * of the original context with the intermediate filters.
3181 * If the new element in the "filters" list is empty, then no elements
3182 * can reach the descendants of the current filter node. The subtree
3183 * underneath the filter node is therefore removed.
3185 * Each expansion node we come across is handled by
3186 * gist_enter_expansion.
3188 * Each extension node we come across is handled by
3189 * gist_enter_extension.
3191 static __isl_give isl_schedule_node
*gist_enter(
3192 __isl_take isl_schedule_node
*node
, void *user
)
3194 struct isl_node_gist_data
*data
= user
;
3197 isl_union_set
*filter
, *inner
;
3201 switch (isl_schedule_node_get_type(node
)) {
3202 case isl_schedule_node_error
:
3203 return isl_schedule_node_free(node
);
3204 case isl_schedule_node_expansion
:
3205 node
= gist_enter_expansion(node
, data
);
3207 case isl_schedule_node_extension
:
3208 node
= gist_enter_extension(node
, data
);
3210 case isl_schedule_node_band
:
3211 case isl_schedule_node_context
:
3212 case isl_schedule_node_domain
:
3213 case isl_schedule_node_guard
:
3214 case isl_schedule_node_leaf
:
3215 case isl_schedule_node_mark
:
3216 case isl_schedule_node_sequence
:
3217 case isl_schedule_node_set
:
3219 case isl_schedule_node_filter
:
3222 done
= gist_done(node
, data
);
3223 filter
= isl_schedule_node_filter_get_filter(node
);
3224 if (done
< 0 || done
) {
3225 data
->filters
= isl_union_set_list_add(data
->filters
,
3228 return isl_schedule_node_free(node
);
3231 n
= isl_union_set_list_n_union_set(data
->filters
);
3232 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3233 filter
= isl_union_set_gist(filter
, isl_union_set_copy(inner
));
3234 node
= isl_schedule_node_filter_set_filter(node
,
3235 isl_union_set_copy(filter
));
3236 filter
= isl_union_set_intersect(filter
, inner
);
3237 empty
= isl_union_set_is_empty(filter
);
3238 data
->filters
= isl_union_set_list_add(data
->filters
, filter
);
3240 return isl_schedule_node_free(node
);
3243 node
= isl_schedule_node_child(node
, 0);
3244 node
= isl_schedule_node_cut(node
);
3245 node
= isl_schedule_node_parent(node
);
3247 } while (isl_schedule_node_has_children(node
) &&
3248 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3253 /* Callback for "traverse" to leave a node for isl_schedule_node_gist.
3255 * In particular, if the current node is a filter node, then we remove
3256 * the element on the "filters" list that was added when we entered
3257 * the node. There is no need to compute any gist here, since we
3258 * already did that when we entered the node.
3260 * If the current node is an expansion, then we decrement
3261 * the number of outer expansions and remove the element
3262 * in data->filters that was added by gist_enter_expansion.
3264 * If the current node is an extension, then remove the element
3265 * in data->filters that was added by gist_enter_extension.
3267 * If the current node is a band node, then we compute the gist of
3268 * the band node with respect to the intersection of the original context
3269 * and the intermediate filters.
3271 * If the current node is a sequence or set node, then some of
3272 * the filter children may have become empty and so they are removed.
3273 * If only one child is left, then the set or sequence node along with
3274 * the single remaining child filter is removed. The filter can be
3275 * removed because the filters on a sequence or set node are supposed
3276 * to partition the incoming domain instances.
3277 * In principle, it should then be impossible for there to be zero
3278 * remaining children, but should this happen, we replace the entire
3279 * subtree with an empty filter.
3281 static __isl_give isl_schedule_node
*gist_leave(
3282 __isl_take isl_schedule_node
*node
, void *user
)
3284 struct isl_node_gist_data
*data
= user
;
3285 isl_schedule_tree
*tree
;
3287 isl_union_set
*filter
;
3289 switch (isl_schedule_node_get_type(node
)) {
3290 case isl_schedule_node_error
:
3291 return isl_schedule_node_free(node
);
3292 case isl_schedule_node_expansion
:
3293 data
->n_expansion
--;
3294 case isl_schedule_node_extension
:
3295 case isl_schedule_node_filter
:
3296 n
= isl_union_set_list_n_union_set(data
->filters
);
3297 data
->filters
= isl_union_set_list_drop(data
->filters
,
3300 case isl_schedule_node_band
:
3301 n
= isl_union_set_list_n_union_set(data
->filters
);
3302 filter
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3303 node
= isl_schedule_node_band_gist(node
, filter
);
3305 case isl_schedule_node_set
:
3306 case isl_schedule_node_sequence
:
3307 tree
= isl_schedule_node_get_tree(node
);
3308 n
= isl_schedule_tree_n_children(tree
);
3309 for (i
= n
- 1; i
>= 0; --i
) {
3310 isl_schedule_tree
*child
;
3311 isl_union_set
*filter
;
3314 child
= isl_schedule_tree_get_child(tree
, i
);
3315 filter
= isl_schedule_tree_filter_get_filter(child
);
3316 empty
= isl_union_set_is_empty(filter
);
3317 isl_union_set_free(filter
);
3318 isl_schedule_tree_free(child
);
3320 tree
= isl_schedule_tree_free(tree
);
3322 tree
= isl_schedule_tree_drop_child(tree
, i
);
3324 n
= isl_schedule_tree_n_children(tree
);
3325 node
= isl_schedule_node_graft_tree(node
, tree
);
3327 node
= isl_schedule_node_delete(node
);
3328 node
= isl_schedule_node_delete(node
);
3329 } else if (n
== 0) {
3333 isl_union_set_list_get_union_set(data
->filters
, 0);
3334 space
= isl_union_set_get_space(filter
);
3335 isl_union_set_free(filter
);
3336 filter
= isl_union_set_empty(space
);
3337 node
= isl_schedule_node_cut(node
);
3338 node
= isl_schedule_node_insert_filter(node
, filter
);
3341 case isl_schedule_node_context
:
3342 case isl_schedule_node_domain
:
3343 case isl_schedule_node_guard
:
3344 case isl_schedule_node_leaf
:
3345 case isl_schedule_node_mark
:
3352 /* Compute the gist of the subtree at "node" with respect to
3353 * the reaching domain elements in "context".
3354 * In particular, compute the gist of all band and filter nodes
3355 * in the subtree with respect to "context". Children of set or sequence
3356 * nodes that end up with an empty filter are removed completely.
3358 * We keep track of the intersection of "context" with all outer filters
3359 * of the current node within the subtree in the final element of "filters".
3360 * Initially, this list contains the single element "context" and it is
3361 * extended or shortened each time we enter or leave a filter node.
3363 __isl_give isl_schedule_node
*isl_schedule_node_gist(
3364 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3366 struct isl_node_gist_data data
;
3368 data
.n_expansion
= 0;
3369 data
.filters
= isl_union_set_list_from_union_set(context
);
3370 node
= traverse(node
, &gist_enter
, &gist_leave
, &data
);
3371 isl_union_set_list_free(data
.filters
);
3375 /* Intersect the domain of domain node "node" with "domain".
3377 * If the domain of "node" is already a subset of "domain",
3378 * then nothing needs to be changed.
3380 * Otherwise, we replace the domain of the domain node by the intersection
3381 * and simplify the subtree rooted at "node" with respect to this intersection.
3383 __isl_give isl_schedule_node
*isl_schedule_node_domain_intersect_domain(
3384 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
)
3386 isl_schedule_tree
*tree
;
3387 isl_union_set
*uset
;
3390 if (!node
|| !domain
)
3393 uset
= isl_schedule_tree_domain_get_domain(node
->tree
);
3394 is_subset
= isl_union_set_is_subset(uset
, domain
);
3395 isl_union_set_free(uset
);
3399 isl_union_set_free(domain
);
3403 tree
= isl_schedule_tree_copy(node
->tree
);
3404 uset
= isl_schedule_tree_domain_get_domain(tree
);
3405 uset
= isl_union_set_intersect(uset
, domain
);
3406 tree
= isl_schedule_tree_domain_set_domain(tree
,
3407 isl_union_set_copy(uset
));
3408 node
= isl_schedule_node_graft_tree(node
, tree
);
3410 node
= isl_schedule_node_child(node
, 0);
3411 node
= isl_schedule_node_gist(node
, uset
);
3412 node
= isl_schedule_node_parent(node
);
3416 isl_schedule_node_free(node
);
3417 isl_union_set_free(domain
);
3421 /* Internal data structure for isl_schedule_node_get_subtree_expansion.
3422 * "expansions" contains a list of accumulated expansions
3423 * for each outer expansion, set or sequence node. The first element
3424 * in the list is an identity mapping on the reaching domain elements.
3425 * "res" collects the results.
3427 struct isl_subtree_expansion_data
{
3428 isl_union_map_list
*expansions
;
3432 /* Callback for "traverse" to enter a node and to move
3433 * to the deepest initial subtree that should be traversed
3434 * by isl_schedule_node_get_subtree_expansion.
3436 * Whenever we come across an expansion node, the last element
3437 * of data->expansions is combined with the expansion
3438 * on the expansion node.
3440 * Whenever we come across a filter node that is the child
3441 * of a set or sequence node, data->expansions is extended
3442 * with a new element that restricts the previous element
3443 * to the elements selected by the filter.
3444 * The previous element can then be reused while backtracking.
3446 static __isl_give isl_schedule_node
*subtree_expansion_enter(
3447 __isl_take isl_schedule_node
*node
, void *user
)
3449 struct isl_subtree_expansion_data
*data
= user
;
3452 enum isl_schedule_node_type type
;
3453 isl_union_set
*filter
;
3454 isl_union_map
*inner
, *expansion
;
3457 switch (isl_schedule_node_get_type(node
)) {
3458 case isl_schedule_node_error
:
3459 return isl_schedule_node_free(node
);
3460 case isl_schedule_node_filter
:
3461 type
= isl_schedule_node_get_parent_type(node
);
3462 if (type
!= isl_schedule_node_set
&&
3463 type
!= isl_schedule_node_sequence
)
3465 filter
= isl_schedule_node_filter_get_filter(node
);
3466 n
= isl_union_map_list_n_union_map(data
->expansions
);
3468 isl_union_map_list_get_union_map(data
->expansions
,
3470 inner
= isl_union_map_intersect_range(inner
, filter
);
3472 isl_union_map_list_add(data
->expansions
, inner
);
3474 case isl_schedule_node_expansion
:
3475 n
= isl_union_map_list_n_union_map(data
->expansions
);
3477 isl_schedule_node_expansion_get_expansion(node
);
3479 isl_union_map_list_get_union_map(data
->expansions
,
3481 inner
= isl_union_map_apply_range(inner
, expansion
);
3483 isl_union_map_list_set_union_map(data
->expansions
,
3486 case isl_schedule_node_band
:
3487 case isl_schedule_node_context
:
3488 case isl_schedule_node_domain
:
3489 case isl_schedule_node_extension
:
3490 case isl_schedule_node_guard
:
3491 case isl_schedule_node_leaf
:
3492 case isl_schedule_node_mark
:
3493 case isl_schedule_node_sequence
:
3494 case isl_schedule_node_set
:
3497 } while (isl_schedule_node_has_children(node
) &&
3498 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3503 /* Callback for "traverse" to leave a node for
3504 * isl_schedule_node_get_subtree_expansion.
3506 * If we come across a filter node that is the child
3507 * of a set or sequence node, then we remove the element
3508 * of data->expansions that was added in subtree_expansion_enter.
3510 * If we reach a leaf node, then the accumulated expansion is
3511 * added to data->res.
3513 static __isl_give isl_schedule_node
*subtree_expansion_leave(
3514 __isl_take isl_schedule_node
*node
, void *user
)
3516 struct isl_subtree_expansion_data
*data
= user
;
3518 isl_union_map
*inner
;
3519 enum isl_schedule_node_type type
;
3521 switch (isl_schedule_node_get_type(node
)) {
3522 case isl_schedule_node_error
:
3523 return isl_schedule_node_free(node
);
3524 case isl_schedule_node_filter
:
3525 type
= isl_schedule_node_get_parent_type(node
);
3526 if (type
!= isl_schedule_node_set
&&
3527 type
!= isl_schedule_node_sequence
)
3529 n
= isl_union_map_list_n_union_map(data
->expansions
);
3530 data
->expansions
= isl_union_map_list_drop(data
->expansions
,
3533 case isl_schedule_node_leaf
:
3534 n
= isl_union_map_list_n_union_map(data
->expansions
);
3535 inner
= isl_union_map_list_get_union_map(data
->expansions
,
3537 data
->res
= isl_union_map_union(data
->res
, inner
);
3539 case isl_schedule_node_band
:
3540 case isl_schedule_node_context
:
3541 case isl_schedule_node_domain
:
3542 case isl_schedule_node_expansion
:
3543 case isl_schedule_node_extension
:
3544 case isl_schedule_node_guard
:
3545 case isl_schedule_node_mark
:
3546 case isl_schedule_node_sequence
:
3547 case isl_schedule_node_set
:
3554 /* Return a mapping from the domain elements that reach "node"
3555 * to the corresponding domain elements in the leaves of the subtree
3556 * rooted at "node" obtained by composing the intermediate expansions.
3558 * We start out with an identity mapping between the domain elements
3559 * that reach "node" and compose it with all the expansions
3560 * on a path from "node" to a leaf while traversing the subtree.
3561 * Within the children of an a sequence or set node, the
3562 * accumulated expansion is restricted to the elements selected
3563 * by the filter child.
3565 __isl_give isl_union_map
*isl_schedule_node_get_subtree_expansion(
3566 __isl_keep isl_schedule_node
*node
)
3568 struct isl_subtree_expansion_data data
;
3570 isl_union_set
*domain
;
3571 isl_union_map
*expansion
;
3576 domain
= isl_schedule_node_get_universe_domain(node
);
3577 space
= isl_union_set_get_space(domain
);
3578 expansion
= isl_union_set_identity(domain
);
3579 data
.res
= isl_union_map_empty(space
);
3580 data
.expansions
= isl_union_map_list_from_union_map(expansion
);
3582 node
= isl_schedule_node_copy(node
);
3583 node
= traverse(node
, &subtree_expansion_enter
,
3584 &subtree_expansion_leave
, &data
);
3586 data
.res
= isl_union_map_free(data
.res
);
3587 isl_schedule_node_free(node
);
3589 isl_union_map_list_free(data
.expansions
);
3594 /* Internal data structure for isl_schedule_node_get_subtree_contraction.
3595 * "contractions" contains a list of accumulated contractions
3596 * for each outer expansion, set or sequence node. The first element
3597 * in the list is an identity mapping on the reaching domain elements.
3598 * "res" collects the results.
3600 struct isl_subtree_contraction_data
{
3601 isl_union_pw_multi_aff_list
*contractions
;
3602 isl_union_pw_multi_aff
*res
;
3605 /* Callback for "traverse" to enter a node and to move
3606 * to the deepest initial subtree that should be traversed
3607 * by isl_schedule_node_get_subtree_contraction.
3609 * Whenever we come across an expansion node, the last element
3610 * of data->contractions is combined with the contraction
3611 * on the expansion node.
3613 * Whenever we come across a filter node that is the child
3614 * of a set or sequence node, data->contractions is extended
3615 * with a new element that restricts the previous element
3616 * to the elements selected by the filter.
3617 * The previous element can then be reused while backtracking.
3619 static __isl_give isl_schedule_node
*subtree_contraction_enter(
3620 __isl_take isl_schedule_node
*node
, void *user
)
3622 struct isl_subtree_contraction_data
*data
= user
;
3625 enum isl_schedule_node_type type
;
3626 isl_union_set
*filter
;
3627 isl_union_pw_multi_aff
*inner
, *contraction
;
3630 switch (isl_schedule_node_get_type(node
)) {
3631 case isl_schedule_node_error
:
3632 return isl_schedule_node_free(node
);
3633 case isl_schedule_node_filter
:
3634 type
= isl_schedule_node_get_parent_type(node
);
3635 if (type
!= isl_schedule_node_set
&&
3636 type
!= isl_schedule_node_sequence
)
3638 filter
= isl_schedule_node_filter_get_filter(node
);
3639 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3640 data
->contractions
);
3642 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3643 data
->contractions
, n
- 1);
3644 inner
= isl_union_pw_multi_aff_intersect_domain(inner
,
3646 data
->contractions
=
3647 isl_union_pw_multi_aff_list_add(data
->contractions
,
3650 case isl_schedule_node_expansion
:
3651 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3652 data
->contractions
);
3654 isl_schedule_node_expansion_get_contraction(node
);
3656 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3657 data
->contractions
, n
- 1);
3659 isl_union_pw_multi_aff_pullback_union_pw_multi_aff(
3660 inner
, contraction
);
3661 data
->contractions
=
3662 isl_union_pw_multi_aff_list_set_union_pw_multi_aff(
3663 data
->contractions
, n
- 1, inner
);
3665 case isl_schedule_node_band
:
3666 case isl_schedule_node_context
:
3667 case isl_schedule_node_domain
:
3668 case isl_schedule_node_extension
:
3669 case isl_schedule_node_guard
:
3670 case isl_schedule_node_leaf
:
3671 case isl_schedule_node_mark
:
3672 case isl_schedule_node_sequence
:
3673 case isl_schedule_node_set
:
3676 } while (isl_schedule_node_has_children(node
) &&
3677 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3682 /* Callback for "traverse" to leave a node for
3683 * isl_schedule_node_get_subtree_contraction.
3685 * If we come across a filter node that is the child
3686 * of a set or sequence node, then we remove the element
3687 * of data->contractions that was added in subtree_contraction_enter.
3689 * If we reach a leaf node, then the accumulated contraction is
3690 * added to data->res.
3692 static __isl_give isl_schedule_node
*subtree_contraction_leave(
3693 __isl_take isl_schedule_node
*node
, void *user
)
3695 struct isl_subtree_contraction_data
*data
= user
;
3697 isl_union_pw_multi_aff
*inner
;
3698 enum isl_schedule_node_type type
;
3700 switch (isl_schedule_node_get_type(node
)) {
3701 case isl_schedule_node_error
:
3702 return isl_schedule_node_free(node
);
3703 case isl_schedule_node_filter
:
3704 type
= isl_schedule_node_get_parent_type(node
);
3705 if (type
!= isl_schedule_node_set
&&
3706 type
!= isl_schedule_node_sequence
)
3708 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3709 data
->contractions
);
3710 data
->contractions
=
3711 isl_union_pw_multi_aff_list_drop(data
->contractions
,
3714 case isl_schedule_node_leaf
:
3715 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3716 data
->contractions
);
3717 inner
= isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3718 data
->contractions
, n
- 1);
3719 data
->res
= isl_union_pw_multi_aff_union_add(data
->res
, inner
);
3721 case isl_schedule_node_band
:
3722 case isl_schedule_node_context
:
3723 case isl_schedule_node_domain
:
3724 case isl_schedule_node_expansion
:
3725 case isl_schedule_node_extension
:
3726 case isl_schedule_node_guard
:
3727 case isl_schedule_node_mark
:
3728 case isl_schedule_node_sequence
:
3729 case isl_schedule_node_set
:
3736 /* Return a mapping from the domain elements in the leaves of the subtree
3737 * rooted at "node" to the corresponding domain elements that reach "node"
3738 * obtained by composing the intermediate contractions.
3740 * We start out with an identity mapping between the domain elements
3741 * that reach "node" and compose it with all the contractions
3742 * on a path from "node" to a leaf while traversing the subtree.
3743 * Within the children of an a sequence or set node, the
3744 * accumulated contraction is restricted to the elements selected
3745 * by the filter child.
3747 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_get_subtree_contraction(
3748 __isl_keep isl_schedule_node
*node
)
3750 struct isl_subtree_contraction_data data
;
3752 isl_union_set
*domain
;
3753 isl_union_pw_multi_aff
*contraction
;
3758 domain
= isl_schedule_node_get_universe_domain(node
);
3759 space
= isl_union_set_get_space(domain
);
3760 contraction
= isl_union_set_identity_union_pw_multi_aff(domain
);
3761 data
.res
= isl_union_pw_multi_aff_empty(space
);
3763 isl_union_pw_multi_aff_list_from_union_pw_multi_aff(contraction
);
3765 node
= isl_schedule_node_copy(node
);
3766 node
= traverse(node
, &subtree_contraction_enter
,
3767 &subtree_contraction_leave
, &data
);
3769 data
.res
= isl_union_pw_multi_aff_free(data
.res
);
3770 isl_schedule_node_free(node
);
3772 isl_union_pw_multi_aff_list_free(data
.contractions
);
3777 /* Do the nearest "n" ancestors of "node" have the types given in "types"
3778 * (starting at the parent of "node")?
3780 static int has_ancestors(__isl_keep isl_schedule_node
*node
,
3781 int n
, enum isl_schedule_node_type
*types
)
3788 n_ancestor
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
3792 for (i
= 0; i
< n
; ++i
) {
3793 isl_schedule_tree
*tree
;
3796 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
3797 n_ancestor
- 1 - i
);
3800 correct_type
= isl_schedule_tree_get_type(tree
) == types
[i
];
3801 isl_schedule_tree_free(tree
);
3809 /* Given a node "node" that appears in an extension (i.e., it is the child
3810 * of a filter in a sequence inside an extension node), are the spaces
3811 * of the extension specified by "extension" disjoint from those
3812 * of both the original extension and the domain elements that reach
3813 * that original extension?
3815 static int is_disjoint_extension(__isl_keep isl_schedule_node
*node
,
3816 __isl_keep isl_union_map
*extension
)
3819 isl_union_set
*domain
;
3822 node
= isl_schedule_node_copy(node
);
3823 node
= isl_schedule_node_parent(node
);
3824 node
= isl_schedule_node_parent(node
);
3825 node
= isl_schedule_node_parent(node
);
3826 old
= isl_schedule_node_extension_get_extension(node
);
3827 domain
= isl_schedule_node_get_universe_domain(node
);
3828 isl_schedule_node_free(node
);
3829 old
= isl_union_map_universe(old
);
3830 domain
= isl_union_set_union(domain
, isl_union_map_range(old
));
3831 extension
= isl_union_map_copy(extension
);
3832 extension
= isl_union_map_intersect_range(extension
, domain
);
3833 empty
= isl_union_map_is_empty(extension
);
3834 isl_union_map_free(extension
);
3839 /* Given a node "node" that is governed by an extension node, extend
3840 * that extension node with "extension".
3842 * In particular, "node" is the child of a filter in a sequence that
3843 * is in turn a child of an extension node. Extend that extension node
3846 * Return a pointer to the parent of the original node (i.e., a filter).
3848 static __isl_give isl_schedule_node
*extend_extension(
3849 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
3853 isl_union_map
*node_extension
;
3855 node
= isl_schedule_node_parent(node
);
3856 pos
= isl_schedule_node_get_child_position(node
);
3857 node
= isl_schedule_node_parent(node
);
3858 node
= isl_schedule_node_parent(node
);
3859 node_extension
= isl_schedule_node_extension_get_extension(node
);
3860 disjoint
= isl_union_map_is_disjoint(extension
, node_extension
);
3861 extension
= isl_union_map_union(extension
, node_extension
);
3862 node
= isl_schedule_node_extension_set_extension(node
, extension
);
3863 node
= isl_schedule_node_child(node
, 0);
3864 node
= isl_schedule_node_child(node
, pos
);
3867 return isl_schedule_node_free(node
);
3871 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3872 "extension domain should be disjoint from earlier "
3873 "extensions", return isl_schedule_node_free(node
));
3878 /* Return the universe of "uset" if this universe is disjoint from "ref".
3879 * Otherwise, return "uset".
3881 * Also check if "uset" itself is disjoint from "ref", reporting
3882 * an error if it is not.
3884 static __isl_give isl_union_set
*replace_by_universe_if_disjoint(
3885 __isl_take isl_union_set
*uset
, __isl_keep isl_union_set
*ref
)
3888 isl_union_set
*universe
;
3890 disjoint
= isl_union_set_is_disjoint(uset
, ref
);
3892 return isl_union_set_free(uset
);
3894 isl_die(isl_union_set_get_ctx(uset
), isl_error_invalid
,
3895 "extension domain should be disjoint from "
3896 "current domain", return isl_union_set_free(uset
));
3898 universe
= isl_union_set_universe(isl_union_set_copy(uset
));
3899 disjoint
= isl_union_set_is_disjoint(universe
, ref
);
3900 if (disjoint
>= 0 && disjoint
) {
3901 isl_union_set_free(uset
);
3904 isl_union_set_free(universe
);
3907 return isl_union_set_free(uset
);
3911 /* Insert an extension node on top of "node" with extension "extension".
3912 * In addition, insert a filter that separates node from the extension
3913 * between the extension node and "node".
3914 * Return a pointer to the inserted filter node.
3916 * If "node" already appears in an extension (i.e., if it is the child
3917 * of a filter in a sequence inside an extension node), then extend that
3918 * extension with "extension" instead.
3919 * In this case, a pointer to the original filter node is returned.
3920 * Note that if some of the elements in the new extension live in the
3921 * same space as those of the original extension or the domain elements
3922 * reaching the original extension, then we insert a new extension anyway.
3923 * Otherwise, we would have to adjust the filters in the sequence child
3924 * of the extension to ensure that the elements in the new extension
3927 static __isl_give isl_schedule_node
*insert_extension(
3928 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
3930 enum isl_schedule_node_type ancestors
[] =
3931 { isl_schedule_node_filter
, isl_schedule_node_sequence
,
3932 isl_schedule_node_extension
};
3933 isl_union_set
*domain
;
3934 isl_union_set
*filter
;
3937 in_ext
= has_ancestors(node
, 3, ancestors
);
3943 disjoint
= is_disjoint_extension(node
, extension
);
3947 return extend_extension(node
, extension
);
3950 filter
= isl_schedule_node_get_domain(node
);
3951 domain
= isl_union_map_range(isl_union_map_copy(extension
));
3952 filter
= replace_by_universe_if_disjoint(filter
, domain
);
3953 isl_union_set_free(domain
);
3955 node
= isl_schedule_node_insert_filter(node
, filter
);
3956 node
= isl_schedule_node_insert_extension(node
, extension
);
3957 node
= isl_schedule_node_child(node
, 0);
3960 isl_schedule_node_free(node
);
3961 isl_union_map_free(extension
);
3965 /* Replace the subtree that "node" points to by "tree" (which has
3966 * a sequence root with two children), except if the parent of "node"
3967 * is a sequence as well, in which case "tree" is spliced at the position
3968 * of "node" in its parent.
3969 * Return a pointer to the child of the "tree_pos" (filter) child of "tree"
3970 * in the updated schedule tree.
3972 static __isl_give isl_schedule_node
*graft_or_splice(
3973 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_tree
*tree
,
3978 if (isl_schedule_node_get_parent_type(node
) ==
3979 isl_schedule_node_sequence
) {
3980 pos
= isl_schedule_node_get_child_position(node
);
3981 node
= isl_schedule_node_parent(node
);
3982 node
= isl_schedule_node_sequence_splice(node
, pos
, tree
);
3985 node
= isl_schedule_node_graft_tree(node
, tree
);
3987 node
= isl_schedule_node_child(node
, pos
+ tree_pos
);
3988 node
= isl_schedule_node_child(node
, 0);
3993 /* Insert a node "graft" into the schedule tree of "node" such that it
3994 * is executed before (if "before" is set) or after (if "before" is not set)
3995 * the node that "node" points to.
3996 * The root of "graft" is an extension node.
3997 * Return a pointer to the node that "node" pointed to.
3999 * We first insert an extension node on top of "node" (or extend
4000 * the extension node if there already is one), with a filter on "node"
4001 * separating it from the extension.
4002 * We then insert a filter in the graft to separate it from the original
4003 * domain elements and combine the original and new tree in a sequence.
4004 * If we have extended an extension node, then the children of this
4005 * sequence are spliced in the sequence of the extended extension
4006 * at the position where "node" appears in the original extension.
4007 * Otherwise, the sequence pair is attached to the new extension node.
4009 static __isl_give isl_schedule_node
*graft_extension(
4010 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
,
4013 isl_union_map
*extension
;
4014 isl_union_set
*graft_domain
;
4015 isl_union_set
*node_domain
;
4016 isl_schedule_tree
*tree
, *tree_graft
;
4018 extension
= isl_schedule_node_extension_get_extension(graft
);
4019 graft_domain
= isl_union_map_range(isl_union_map_copy(extension
));
4020 node_domain
= isl_schedule_node_get_universe_domain(node
);
4021 node
= insert_extension(node
, extension
);
4023 graft_domain
= replace_by_universe_if_disjoint(graft_domain
,
4025 isl_union_set_free(node_domain
);
4027 tree
= isl_schedule_node_get_tree(node
);
4028 if (!isl_schedule_node_has_children(graft
)) {
4029 tree_graft
= isl_schedule_tree_from_filter(graft_domain
);
4031 graft
= isl_schedule_node_child(graft
, 0);
4032 tree_graft
= isl_schedule_node_get_tree(graft
);
4033 tree_graft
= isl_schedule_tree_insert_filter(tree_graft
,
4037 tree
= isl_schedule_tree_sequence_pair(tree_graft
, tree
);
4039 tree
= isl_schedule_tree_sequence_pair(tree
, tree_graft
);
4040 node
= graft_or_splice(node
, tree
, before
);
4042 isl_schedule_node_free(graft
);
4047 /* Replace the root domain node of "node" by an extension node suitable
4048 * for insertion at "pos".
4049 * That is, create an extension node that maps the outer band nodes
4050 * at "pos" to the domain of the root node of "node" and attach
4051 * the child of this root node to the extension node.
4053 static __isl_give isl_schedule_node
*extension_from_domain(
4054 __isl_take isl_schedule_node
*node
, __isl_keep isl_schedule_node
*pos
)
4056 isl_union_set
*universe
;
4057 isl_union_set
*domain
;
4062 isl_schedule_node
*res
;
4063 isl_schedule_tree
*tree
;
4065 anchored
= isl_schedule_node_is_subtree_anchored(node
);
4067 return isl_schedule_node_free(node
);
4069 isl_die(isl_schedule_node_get_ctx(node
), isl_error_unsupported
,
4070 "cannot graft anchored tree with domain root",
4071 return isl_schedule_node_free(node
));
4073 depth
= isl_schedule_node_get_schedule_depth(pos
);
4074 domain
= isl_schedule_node_domain_get_domain(node
);
4075 space
= isl_union_set_get_space(domain
);
4076 space
= isl_space_set_from_params(space
);
4077 space
= isl_space_add_dims(space
, isl_dim_set
, depth
);
4078 universe
= isl_union_set_from_set(isl_set_universe(space
));
4079 ext
= isl_union_map_from_domain_and_range(universe
, domain
);
4080 res
= isl_schedule_node_from_extension(ext
);
4081 node
= isl_schedule_node_child(node
, 0);
4083 return isl_schedule_node_free(res
);
4084 if (!isl_schedule_tree_is_leaf(node
->tree
)) {
4085 tree
= isl_schedule_node_get_tree(node
);
4086 res
= isl_schedule_node_child(res
, 0);
4087 res
= isl_schedule_node_graft_tree(res
, tree
);
4088 res
= isl_schedule_node_parent(res
);
4090 isl_schedule_node_free(node
);
4095 /* Insert a node "graft" into the schedule tree of "node" such that it
4096 * is executed before (if "before" is set) or after (if "before" is not set)
4097 * the node that "node" points to.
4098 * The root of "graft" may be either a domain or an extension node.
4099 * In the latter case, the domain of the extension needs to correspond
4100 * to the outer band nodes of "node".
4101 * The elements of the domain or the range of the extension may not
4102 * intersect with the domain elements that reach "node".
4103 * The schedule tree of "graft" may not be anchored.
4105 * The schedule tree of "node" is modified to include an extension node
4106 * corresponding to the root node of "graft" as a child of the original
4107 * parent of "node". The original node that "node" points to and the
4108 * child of the root node of "graft" are attached to this extension node
4109 * through a sequence, with appropriate filters and with the child
4110 * of "graft" appearing before or after the original "node".
4112 * If "node" already appears inside a sequence that is the child of
4113 * an extension node and if the spaces of the new domain elements
4114 * do not overlap with those of the original domain elements,
4115 * then that extension node is extended with the new extension
4116 * rather than introducing a new segment of extension and sequence nodes.
4118 * Return a pointer to the same node in the modified tree that
4119 * "node" pointed to in the original tree.
4121 static __isl_give isl_schedule_node
*isl_schedule_node_graft_before_or_after(
4122 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
,
4125 if (!node
|| !graft
)
4127 if (check_insert(node
) < 0)
4130 if (isl_schedule_node_get_type(graft
) == isl_schedule_node_domain
)
4131 graft
= extension_from_domain(graft
, node
);
4133 if (isl_schedule_node_get_type(graft
) != isl_schedule_node_extension
)
4134 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4135 "expecting domain or extension as root of graft",
4138 return graft_extension(node
, graft
, before
);
4140 isl_schedule_node_free(node
);
4141 isl_schedule_node_free(graft
);
4145 /* Insert a node "graft" into the schedule tree of "node" such that it
4146 * is executed before the node that "node" points to.
4147 * The root of "graft" may be either a domain or an extension node.
4148 * In the latter case, the domain of the extension needs to correspond
4149 * to the outer band nodes of "node".
4150 * The elements of the domain or the range of the extension may not
4151 * intersect with the domain elements that reach "node".
4152 * The schedule tree of "graft" may not be anchored.
4154 * Return a pointer to the same node in the modified tree that
4155 * "node" pointed to in the original tree.
4157 __isl_give isl_schedule_node
*isl_schedule_node_graft_before(
4158 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
)
4160 return isl_schedule_node_graft_before_or_after(node
, graft
, 1);
4163 /* Insert a node "graft" into the schedule tree of "node" such that it
4164 * is executed after the node that "node" points to.
4165 * The root of "graft" may be either a domain or an extension node.
4166 * In the latter case, the domain of the extension needs to correspond
4167 * to the outer band nodes of "node".
4168 * The elements of the domain or the range of the extension may not
4169 * intersect with the domain elements that reach "node".
4170 * The schedule tree of "graft" may not be anchored.
4172 * Return a pointer to the same node in the modified tree that
4173 * "node" pointed to in the original tree.
4175 __isl_give isl_schedule_node
*isl_schedule_node_graft_after(
4176 __isl_take isl_schedule_node
*node
,
4177 __isl_take isl_schedule_node
*graft
)
4179 return isl_schedule_node_graft_before_or_after(node
, graft
, 0);
4182 /* Split the domain elements that reach "node" into those that satisfy
4183 * "filter" and those that do not. Arrange for the first subset to be
4184 * executed after the second subset.
4185 * Return a pointer to the tree corresponding to the second subset,
4186 * except when this subset is empty in which case the original pointer
4188 * If both subsets are non-empty, then a sequence node is introduced
4189 * to impose the order. If the grandparent of the original node was
4190 * itself a sequence, then the original child is replaced by two children
4191 * in this sequence instead.
4192 * The children in the sequence are copies of the original subtree,
4193 * simplified with respect to their filters.
4195 __isl_give isl_schedule_node
*isl_schedule_node_order_after(
4196 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
4198 enum isl_schedule_node_type ancestors
[] =
4199 { isl_schedule_node_filter
, isl_schedule_node_sequence
};
4200 isl_union_set
*node_domain
, *node_filter
= NULL
;
4201 isl_schedule_node
*node2
;
4202 isl_schedule_tree
*tree1
, *tree2
;
4206 if (!node
|| !filter
)
4208 if (check_insert(node
) < 0)
4211 in_seq
= has_ancestors(node
, 2, ancestors
);
4215 node
= isl_schedule_node_parent(node
);
4216 node_domain
= isl_schedule_node_get_domain(node
);
4217 filter
= isl_union_set_gist(filter
, isl_union_set_copy(node_domain
));
4218 node_filter
= isl_union_set_copy(node_domain
);
4219 node_filter
= isl_union_set_subtract(node_filter
,
4220 isl_union_set_copy(filter
));
4221 node_filter
= isl_union_set_gist(node_filter
, node_domain
);
4222 empty1
= isl_union_set_is_empty(filter
);
4223 empty2
= isl_union_set_is_empty(node_filter
);
4224 if (empty1
< 0 || empty2
< 0)
4226 if (empty1
|| empty2
) {
4227 isl_union_set_free(filter
);
4228 isl_union_set_free(node_filter
);
4232 node2
= isl_schedule_node_copy(node
);
4233 node
= isl_schedule_node_gist(node
, isl_union_set_copy(node_filter
));
4234 node2
= isl_schedule_node_gist(node2
, isl_union_set_copy(filter
));
4235 tree1
= isl_schedule_node_get_tree(node
);
4236 tree2
= isl_schedule_node_get_tree(node2
);
4237 isl_schedule_node_free(node2
);
4238 tree1
= isl_schedule_tree_insert_filter(tree1
, node_filter
);
4239 tree2
= isl_schedule_tree_insert_filter(tree2
, filter
);
4240 tree1
= isl_schedule_tree_sequence_pair(tree1
, tree2
);
4242 node
= graft_or_splice(node
, tree1
, 0);
4246 isl_schedule_node_free(node
);
4247 isl_union_set_free(filter
);
4248 isl_union_set_free(node_filter
);
4252 /* Reset the user pointer on all identifiers of parameters and tuples
4253 * in the schedule node "node".
4255 __isl_give isl_schedule_node
*isl_schedule_node_reset_user(
4256 __isl_take isl_schedule_node
*node
)
4258 isl_schedule_tree
*tree
;
4260 tree
= isl_schedule_node_get_tree(node
);
4261 tree
= isl_schedule_tree_reset_user(tree
);
4262 node
= isl_schedule_node_graft_tree(node
, tree
);
4267 /* Align the parameters of the schedule node "node" to those of "space".
4269 __isl_give isl_schedule_node
*isl_schedule_node_align_params(
4270 __isl_take isl_schedule_node
*node
, __isl_take isl_space
*space
)
4272 isl_schedule_tree
*tree
;
4274 tree
= isl_schedule_node_get_tree(node
);
4275 tree
= isl_schedule_tree_align_params(tree
, space
);
4276 node
= isl_schedule_node_graft_tree(node
, tree
);
4281 /* Compute the pullback of schedule node "node"
4282 * by the function represented by "upma".
4283 * In other words, plug in "upma" in the iteration domains
4284 * of schedule node "node".
4285 * We currently do not handle expansion nodes.
4287 * Note that this is only a helper function for
4288 * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency,
4289 * this function should not be called on a single node without also
4290 * calling it on all the other nodes.
4292 __isl_give isl_schedule_node
*isl_schedule_node_pullback_union_pw_multi_aff(
4293 __isl_take isl_schedule_node
*node
,
4294 __isl_take isl_union_pw_multi_aff
*upma
)
4296 isl_schedule_tree
*tree
;
4298 tree
= isl_schedule_node_get_tree(node
);
4299 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, upma
);
4300 node
= isl_schedule_node_graft_tree(node
, tree
);
4305 /* Return the position of the subtree containing "node" among the children
4306 * of "ancestor". "node" is assumed to be a descendant of "ancestor".
4307 * In particular, both nodes should point to the same schedule tree.
4309 * Return -1 on error.
4311 int isl_schedule_node_get_ancestor_child_position(
4312 __isl_keep isl_schedule_node
*node
,
4313 __isl_keep isl_schedule_node
*ancestor
)
4316 isl_schedule_tree
*tree
;
4318 if (!node
|| !ancestor
)
4321 if (node
->schedule
!= ancestor
->schedule
)
4322 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4323 "not a descendant", return -1);
4325 n1
= isl_schedule_node_get_tree_depth(ancestor
);
4326 n2
= isl_schedule_node_get_tree_depth(node
);
4329 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4330 "not a descendant", return -1);
4331 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n1
);
4332 isl_schedule_tree_free(tree
);
4333 if (tree
!= ancestor
->tree
)
4334 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4335 "not a descendant", return -1);
4337 return node
->child_pos
[n1
];
4340 /* Given two nodes that point to the same schedule tree, return their
4341 * closest shared ancestor.
4343 * Since the two nodes point to the same schedule, they share at least
4344 * one ancestor, the root of the schedule. We move down from the root
4345 * to the first ancestor where the respective children have a different
4346 * child position. This is the requested ancestor.
4347 * If there is no ancestor where the children have a different position,
4348 * then one node is an ancestor of the other and then this node is
4349 * the requested ancestor.
4351 __isl_give isl_schedule_node
*isl_schedule_node_get_shared_ancestor(
4352 __isl_keep isl_schedule_node
*node1
,
4353 __isl_keep isl_schedule_node
*node2
)
4357 if (!node1
|| !node2
)
4359 if (node1
->schedule
!= node2
->schedule
)
4360 isl_die(isl_schedule_node_get_ctx(node1
), isl_error_invalid
,
4361 "not part of same schedule", return NULL
);
4362 n1
= isl_schedule_node_get_tree_depth(node1
);
4363 n2
= isl_schedule_node_get_tree_depth(node2
);
4365 return isl_schedule_node_get_shared_ancestor(node2
, node1
);
4367 return isl_schedule_node_copy(node1
);
4368 if (isl_schedule_node_is_equal(node1
, node2
))
4369 return isl_schedule_node_copy(node1
);
4371 for (i
= 0; i
< n1
; ++i
)
4372 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
4375 node1
= isl_schedule_node_copy(node1
);
4376 return isl_schedule_node_ancestor(node1
, n1
- i
);
4379 /* Print "node" to "p".
4381 __isl_give isl_printer
*isl_printer_print_schedule_node(
4382 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
4385 return isl_printer_free(p
);
4386 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
,
4387 isl_schedule_tree_list_n_schedule_tree(node
->ancestors
),
4391 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
4394 isl_printer
*printer
;
4399 ctx
= isl_schedule_node_get_ctx(node
);
4400 printer
= isl_printer_to_file(ctx
, stderr
);
4401 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
4402 printer
= isl_printer_print_schedule_node(printer
, node
);
4404 isl_printer_free(printer
);