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 /* Make sure that that spaces of "node" and "mupa" are the same.
1768 * Return isl_stat_error on error, reporting the error to the user.
1770 static isl_stat
check_space_multi_union_pw_aff(
1771 __isl_keep isl_schedule_node
*node
,
1772 __isl_keep isl_multi_union_pw_aff
*mupa
)
1774 isl_space
*node_space
, *mupa_space
;
1777 node_space
= isl_schedule_node_band_get_space(node
);
1778 mupa_space
= isl_multi_union_pw_aff_get_space(mupa
);
1779 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1780 mupa_space
, isl_dim_set
);
1781 isl_space_free(mupa_space
);
1782 isl_space_free(node_space
);
1784 return isl_stat_error
;
1786 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1787 "spaces don't match", return isl_stat_error
);
1792 /* Shift the partial schedule of the band node "node" by "shift".
1794 __isl_give isl_schedule_node
*isl_schedule_node_band_shift(
1795 __isl_take isl_schedule_node
*node
,
1796 __isl_take isl_multi_union_pw_aff
*shift
)
1798 isl_schedule_tree
*tree
;
1801 if (!node
|| !shift
)
1803 if (check_space_multi_union_pw_aff(node
, shift
) < 0)
1805 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1809 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1810 "cannot shift band node with anchored subtree",
1813 tree
= isl_schedule_node_get_tree(node
);
1814 tree
= isl_schedule_tree_band_shift(tree
, shift
);
1815 return isl_schedule_node_graft_tree(node
, tree
);
1817 isl_multi_union_pw_aff_free(shift
);
1818 isl_schedule_node_free(node
);
1822 /* Tile "node" with tile sizes "sizes".
1824 * The current node is replaced by two nested nodes corresponding
1825 * to the tile dimensions and the point dimensions.
1827 * Return a pointer to the outer (tile) node.
1829 * If any of the descendants of "node" depend on the set of outer band nodes,
1830 * then we refuse to tile the node.
1832 * If the scale tile loops option is set, then the tile loops
1833 * are scaled by the tile sizes. If the shift point loops option is set,
1834 * then the point loops are shifted to start at zero.
1835 * In particular, these options affect the tile and point loop schedules
1838 * scale shift original tile point
1840 * 0 0 i floor(i/s) i
1841 * 1 0 i s * floor(i/s) i
1842 * 0 1 i floor(i/s) i - s * floor(i/s)
1843 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1845 __isl_give isl_schedule_node
*isl_schedule_node_band_tile(
1846 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*sizes
)
1848 isl_schedule_tree
*tree
;
1851 if (!node
|| !sizes
)
1853 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1857 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1858 "cannot tile band node with anchored subtree",
1861 if (check_space_multi_val(node
, sizes
) < 0)
1864 tree
= isl_schedule_node_get_tree(node
);
1865 tree
= isl_schedule_tree_band_tile(tree
, sizes
);
1866 return isl_schedule_node_graft_tree(node
, tree
);
1868 isl_multi_val_free(sizes
);
1869 isl_schedule_node_free(node
);
1873 /* Move the band node "node" down to all the leaves in the subtree
1875 * Return a pointer to the node in the resulting tree that is in the same
1876 * position as the node pointed to by "node" in the original tree.
1878 * If the node only has a leaf child, then nothing needs to be done.
1879 * Otherwise, the child of the node is removed and the result is
1880 * appended to all the leaves in the subtree rooted at the original child.
1881 * The original node is then replaced by the result of this operation.
1883 * If any of the nodes in the subtree rooted at "node" depend on
1884 * the set of outer band nodes then we refuse to sink the band node.
1886 __isl_give isl_schedule_node
*isl_schedule_node_band_sink(
1887 __isl_take isl_schedule_node
*node
)
1889 enum isl_schedule_node_type type
;
1890 isl_schedule_tree
*tree
, *child
;
1896 type
= isl_schedule_node_get_type(node
);
1897 if (type
!= isl_schedule_node_band
)
1898 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1899 "not a band node", isl_schedule_node_free(node
));
1900 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1902 return isl_schedule_node_free(node
);
1904 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1905 "cannot sink band node in anchored subtree",
1906 isl_schedule_node_free(node
));
1907 if (isl_schedule_tree_n_children(node
->tree
) == 0)
1910 tree
= isl_schedule_node_get_tree(node
);
1911 child
= isl_schedule_tree_get_child(tree
, 0);
1912 tree
= isl_schedule_tree_reset_children(tree
);
1913 tree
= isl_schedule_tree_append_to_leaves(child
, tree
);
1915 return isl_schedule_node_graft_tree(node
, tree
);
1918 /* Split "node" into two nested band nodes, one with the first "pos"
1919 * dimensions and one with the remaining dimensions.
1920 * The schedules of the two band nodes live in anonymous spaces.
1922 __isl_give isl_schedule_node
*isl_schedule_node_band_split(
1923 __isl_take isl_schedule_node
*node
, int pos
)
1925 isl_schedule_tree
*tree
;
1927 tree
= isl_schedule_node_get_tree(node
);
1928 tree
= isl_schedule_tree_band_split(tree
, pos
);
1929 return isl_schedule_node_graft_tree(node
, tree
);
1932 /* Return the context of the context node "node".
1934 __isl_give isl_set
*isl_schedule_node_context_get_context(
1935 __isl_keep isl_schedule_node
*node
)
1940 return isl_schedule_tree_context_get_context(node
->tree
);
1943 /* Return the domain of the domain node "node".
1945 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
1946 __isl_keep isl_schedule_node
*node
)
1951 return isl_schedule_tree_domain_get_domain(node
->tree
);
1954 /* Return the expansion map of expansion node "node".
1956 __isl_give isl_union_map
*isl_schedule_node_expansion_get_expansion(
1957 __isl_keep isl_schedule_node
*node
)
1962 return isl_schedule_tree_expansion_get_expansion(node
->tree
);
1965 /* Return the contraction of expansion node "node".
1967 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_expansion_get_contraction(
1968 __isl_keep isl_schedule_node
*node
)
1973 return isl_schedule_tree_expansion_get_contraction(node
->tree
);
1976 /* Replace the contraction and the expansion of the expansion node "node"
1977 * by "contraction" and "expansion".
1979 __isl_give isl_schedule_node
*
1980 isl_schedule_node_expansion_set_contraction_and_expansion(
1981 __isl_take isl_schedule_node
*node
,
1982 __isl_take isl_union_pw_multi_aff
*contraction
,
1983 __isl_take isl_union_map
*expansion
)
1985 isl_schedule_tree
*tree
;
1987 if (!node
|| !contraction
|| !expansion
)
1990 tree
= isl_schedule_tree_copy(node
->tree
);
1991 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
1992 contraction
, expansion
);
1993 return isl_schedule_node_graft_tree(node
, tree
);
1995 isl_schedule_node_free(node
);
1996 isl_union_pw_multi_aff_free(contraction
);
1997 isl_union_map_free(expansion
);
2001 /* Return the extension of the extension node "node".
2003 __isl_give isl_union_map
*isl_schedule_node_extension_get_extension(
2004 __isl_keep isl_schedule_node
*node
)
2009 return isl_schedule_tree_extension_get_extension(node
->tree
);
2012 /* Replace the extension of extension node "node" by "extension".
2014 __isl_give isl_schedule_node
*isl_schedule_node_extension_set_extension(
2015 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
2017 isl_schedule_tree
*tree
;
2019 if (!node
|| !extension
)
2022 tree
= isl_schedule_tree_copy(node
->tree
);
2023 tree
= isl_schedule_tree_extension_set_extension(tree
, extension
);
2024 return isl_schedule_node_graft_tree(node
, tree
);
2026 isl_schedule_node_free(node
);
2027 isl_union_map_free(extension
);
2031 /* Return the filter of the filter node "node".
2033 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
2034 __isl_keep isl_schedule_node
*node
)
2039 return isl_schedule_tree_filter_get_filter(node
->tree
);
2042 /* Replace the filter of filter node "node" by "filter".
2044 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
2045 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2047 isl_schedule_tree
*tree
;
2049 if (!node
|| !filter
)
2052 tree
= isl_schedule_tree_copy(node
->tree
);
2053 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
2054 return isl_schedule_node_graft_tree(node
, tree
);
2056 isl_schedule_node_free(node
);
2057 isl_union_set_free(filter
);
2061 /* Return the guard of the guard node "node".
2063 __isl_give isl_set
*isl_schedule_node_guard_get_guard(
2064 __isl_keep isl_schedule_node
*node
)
2069 return isl_schedule_tree_guard_get_guard(node
->tree
);
2072 /* Return the mark identifier of the mark node "node".
2074 __isl_give isl_id
*isl_schedule_node_mark_get_id(
2075 __isl_keep isl_schedule_node
*node
)
2080 return isl_schedule_tree_mark_get_id(node
->tree
);
2083 /* Replace the child at position "pos" of the sequence node "node"
2084 * by the children of sequence root node of "tree".
2086 __isl_give isl_schedule_node
*isl_schedule_node_sequence_splice(
2087 __isl_take isl_schedule_node
*node
, int pos
,
2088 __isl_take isl_schedule_tree
*tree
)
2090 isl_schedule_tree
*node_tree
;
2094 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2095 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2096 "not a sequence node", goto error
);
2097 if (isl_schedule_tree_get_type(tree
) != isl_schedule_node_sequence
)
2098 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2099 "not a sequence node", goto error
);
2100 node_tree
= isl_schedule_node_get_tree(node
);
2101 node_tree
= isl_schedule_tree_sequence_splice(node_tree
, pos
, tree
);
2102 node
= isl_schedule_node_graft_tree(node
, node_tree
);
2106 isl_schedule_node_free(node
);
2107 isl_schedule_tree_free(tree
);
2111 /* Update the ancestors of "node" to point to the tree that "node"
2113 * That is, replace the child in the original parent that corresponds
2114 * to the current tree position by node->tree and continue updating
2115 * the ancestors in the same way until the root is reached.
2117 * If "fn" is not NULL, then it is called on each ancestor as we move up
2118 * the tree so that it can modify the ancestor before it is added
2119 * to the list of ancestors of the modified node.
2120 * The additional "pos" argument records the position
2121 * of the "tree" argument in the original schedule tree.
2123 * If "node" originally points to a leaf of the schedule tree, then make sure
2124 * that in the end it points to a leaf in the updated schedule tree.
2126 static __isl_give isl_schedule_node
*update_ancestors(
2127 __isl_take isl_schedule_node
*node
,
2128 __isl_give isl_schedule_tree
*(*fn
)(__isl_take isl_schedule_tree
*tree
,
2129 __isl_keep isl_schedule_node
*pos
, void *user
), void *user
)
2134 isl_schedule_tree
*tree
;
2135 isl_schedule_node
*pos
= NULL
;
2138 pos
= isl_schedule_node_copy(node
);
2140 node
= isl_schedule_node_cow(node
);
2142 return isl_schedule_node_free(pos
);
2144 ctx
= isl_schedule_node_get_ctx(node
);
2145 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
2146 tree
= isl_schedule_tree_copy(node
->tree
);
2148 for (i
= n
- 1; i
>= 0; --i
) {
2149 isl_schedule_tree
*parent
;
2151 parent
= isl_schedule_tree_list_get_schedule_tree(
2152 node
->ancestors
, i
);
2153 parent
= isl_schedule_tree_replace_child(parent
,
2154 node
->child_pos
[i
], tree
);
2156 pos
= isl_schedule_node_parent(pos
);
2157 parent
= fn(parent
, pos
, user
);
2159 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
2160 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
2166 isl_schedule_node_free(pos
);
2168 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
2169 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
2171 isl_schedule_tree_free(node
->tree
);
2172 node
->tree
= isl_schedule_node_get_leaf(node
);
2175 if (!node
->schedule
|| !node
->ancestors
)
2176 return isl_schedule_node_free(node
);
2181 /* Replace the subtree that "pos" points to by "tree", updating
2182 * the ancestors to maintain a consistent state.
2184 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
2185 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
2189 if (pos
->tree
== tree
) {
2190 isl_schedule_tree_free(tree
);
2194 pos
= isl_schedule_node_cow(pos
);
2198 isl_schedule_tree_free(pos
->tree
);
2201 return update_ancestors(pos
, NULL
, NULL
);
2203 isl_schedule_node_free(pos
);
2204 isl_schedule_tree_free(tree
);
2208 /* Make sure we can insert a node between "node" and its parent.
2209 * Return -1 on error, reporting the reason why we cannot insert a node.
2211 static int check_insert(__isl_keep isl_schedule_node
*node
)
2214 enum isl_schedule_node_type type
;
2216 has_parent
= isl_schedule_node_has_parent(node
);
2220 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2221 "cannot insert node outside of root", return -1);
2223 type
= isl_schedule_node_get_parent_type(node
);
2224 if (type
== isl_schedule_node_error
)
2226 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
2227 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2228 "cannot insert node between set or sequence node "
2229 "and its filter children", return -1);
2234 /* Insert a band node with partial schedule "mupa" between "node" and
2236 * Return a pointer to the new band node.
2238 * If any of the nodes in the subtree rooted at "node" depend on
2239 * the set of outer band nodes then we refuse to insert the band node.
2241 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
2242 __isl_take isl_schedule_node
*node
,
2243 __isl_take isl_multi_union_pw_aff
*mupa
)
2246 isl_schedule_band
*band
;
2247 isl_schedule_tree
*tree
;
2249 if (check_insert(node
) < 0)
2250 node
= isl_schedule_node_free(node
);
2251 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2255 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2256 "cannot insert band node in anchored subtree",
2259 tree
= isl_schedule_node_get_tree(node
);
2260 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
2261 tree
= isl_schedule_tree_insert_band(tree
, band
);
2262 node
= isl_schedule_node_graft_tree(node
, tree
);
2266 isl_schedule_node_free(node
);
2267 isl_multi_union_pw_aff_free(mupa
);
2271 /* Insert a context node with context "context" between "node" and its parent.
2272 * Return a pointer to the new context node.
2274 __isl_give isl_schedule_node
*isl_schedule_node_insert_context(
2275 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
2277 isl_schedule_tree
*tree
;
2279 if (check_insert(node
) < 0)
2280 node
= isl_schedule_node_free(node
);
2282 tree
= isl_schedule_node_get_tree(node
);
2283 tree
= isl_schedule_tree_insert_context(tree
, context
);
2284 node
= isl_schedule_node_graft_tree(node
, tree
);
2289 /* Insert an expansion node with the given "contraction" and "expansion"
2290 * between "node" and its parent.
2291 * Return a pointer to the new expansion node.
2293 * Typically the domain and range spaces of the expansion are different.
2294 * This means that only one of them can refer to the current domain space
2295 * in a consistent tree. It is up to the caller to ensure that the tree
2296 * returns to a consistent state.
2298 __isl_give isl_schedule_node
*isl_schedule_node_insert_expansion(
2299 __isl_take isl_schedule_node
*node
,
2300 __isl_take isl_union_pw_multi_aff
*contraction
,
2301 __isl_take isl_union_map
*expansion
)
2303 isl_schedule_tree
*tree
;
2305 if (check_insert(node
) < 0)
2306 node
= isl_schedule_node_free(node
);
2308 tree
= isl_schedule_node_get_tree(node
);
2309 tree
= isl_schedule_tree_insert_expansion(tree
, contraction
, expansion
);
2310 node
= isl_schedule_node_graft_tree(node
, tree
);
2315 /* Insert an extension node with extension "extension" between "node" and
2317 * Return a pointer to the new extension node.
2319 __isl_give isl_schedule_node
*isl_schedule_node_insert_extension(
2320 __isl_take isl_schedule_node
*node
,
2321 __isl_take isl_union_map
*extension
)
2323 isl_schedule_tree
*tree
;
2325 tree
= isl_schedule_node_get_tree(node
);
2326 tree
= isl_schedule_tree_insert_extension(tree
, extension
);
2327 node
= isl_schedule_node_graft_tree(node
, tree
);
2332 /* Insert a filter node with filter "filter" between "node" and its parent.
2333 * Return a pointer to the new filter node.
2335 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
2336 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2338 isl_schedule_tree
*tree
;
2340 if (check_insert(node
) < 0)
2341 node
= isl_schedule_node_free(node
);
2343 tree
= isl_schedule_node_get_tree(node
);
2344 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2345 node
= isl_schedule_node_graft_tree(node
, tree
);
2350 /* Insert a guard node with guard "guard" between "node" and its parent.
2351 * Return a pointer to the new guard node.
2353 __isl_give isl_schedule_node
*isl_schedule_node_insert_guard(
2354 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*guard
)
2356 isl_schedule_tree
*tree
;
2358 if (check_insert(node
) < 0)
2359 node
= isl_schedule_node_free(node
);
2361 tree
= isl_schedule_node_get_tree(node
);
2362 tree
= isl_schedule_tree_insert_guard(tree
, guard
);
2363 node
= isl_schedule_node_graft_tree(node
, tree
);
2368 /* Insert a mark node with mark identifier "mark" between "node" and
2370 * Return a pointer to the new mark node.
2372 __isl_give isl_schedule_node
*isl_schedule_node_insert_mark(
2373 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*mark
)
2375 isl_schedule_tree
*tree
;
2377 if (check_insert(node
) < 0)
2378 node
= isl_schedule_node_free(node
);
2380 tree
= isl_schedule_node_get_tree(node
);
2381 tree
= isl_schedule_tree_insert_mark(tree
, mark
);
2382 node
= isl_schedule_node_graft_tree(node
, tree
);
2387 /* Attach the current subtree of "node" to a sequence of filter tree nodes
2388 * with filters described by "filters", attach this sequence
2389 * of filter tree nodes as children to a new tree of type "type" and
2390 * replace the original subtree of "node" by this new tree.
2392 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
2393 __isl_take isl_schedule_node
*node
,
2394 enum isl_schedule_node_type type
,
2395 __isl_take isl_union_set_list
*filters
)
2399 isl_schedule_tree
*tree
;
2400 isl_schedule_tree_list
*list
;
2402 if (check_insert(node
) < 0)
2403 node
= isl_schedule_node_free(node
);
2405 if (!node
|| !filters
)
2408 ctx
= isl_schedule_node_get_ctx(node
);
2409 n
= isl_union_set_list_n_union_set(filters
);
2410 list
= isl_schedule_tree_list_alloc(ctx
, n
);
2411 for (i
= 0; i
< n
; ++i
) {
2412 isl_schedule_tree
*tree
;
2413 isl_union_set
*filter
;
2415 tree
= isl_schedule_node_get_tree(node
);
2416 filter
= isl_union_set_list_get_union_set(filters
, i
);
2417 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2418 list
= isl_schedule_tree_list_add(list
, tree
);
2420 tree
= isl_schedule_tree_from_children(type
, list
);
2421 node
= isl_schedule_node_graft_tree(node
, tree
);
2423 isl_union_set_list_free(filters
);
2426 isl_union_set_list_free(filters
);
2427 isl_schedule_node_free(node
);
2431 /* Insert a sequence node with child filters "filters" between "node" and
2432 * its parent. That is, the tree that "node" points to is attached
2433 * to each of the child nodes of the filter nodes.
2434 * Return a pointer to the new sequence node.
2436 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
2437 __isl_take isl_schedule_node
*node
,
2438 __isl_take isl_union_set_list
*filters
)
2440 return isl_schedule_node_insert_children(node
,
2441 isl_schedule_node_sequence
, filters
);
2444 /* Insert a set node with child filters "filters" between "node" and
2445 * its parent. That is, the tree that "node" points to is attached
2446 * to each of the child nodes of the filter nodes.
2447 * Return a pointer to the new set node.
2449 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
2450 __isl_take isl_schedule_node
*node
,
2451 __isl_take isl_union_set_list
*filters
)
2453 return isl_schedule_node_insert_children(node
,
2454 isl_schedule_node_set
, filters
);
2457 /* Remove "node" from its schedule tree and return a pointer
2458 * to the leaf at the same position in the updated schedule tree.
2460 * It is not allowed to remove the root of a schedule tree or
2461 * a child of a set or sequence node.
2463 __isl_give isl_schedule_node
*isl_schedule_node_cut(
2464 __isl_take isl_schedule_node
*node
)
2466 isl_schedule_tree
*leaf
;
2467 enum isl_schedule_node_type parent_type
;
2471 if (!isl_schedule_node_has_parent(node
))
2472 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2473 "cannot cut root", return isl_schedule_node_free(node
));
2475 parent_type
= isl_schedule_node_get_parent_type(node
);
2476 if (parent_type
== isl_schedule_node_set
||
2477 parent_type
== isl_schedule_node_sequence
)
2478 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2479 "cannot cut child of set or sequence",
2480 return isl_schedule_node_free(node
));
2482 leaf
= isl_schedule_node_get_leaf(node
);
2483 return isl_schedule_node_graft_tree(node
, leaf
);
2486 /* Remove a single node from the schedule tree, attaching the child
2487 * of "node" directly to its parent.
2488 * Return a pointer to this former child or to the leaf the position
2489 * of the original node if there was no child.
2490 * It is not allowed to remove the root of a schedule tree,
2491 * a set or sequence node, a child of a set or sequence node or
2492 * a band node with an anchored subtree.
2494 __isl_give isl_schedule_node
*isl_schedule_node_delete(
2495 __isl_take isl_schedule_node
*node
)
2498 isl_schedule_tree
*tree
;
2499 enum isl_schedule_node_type type
;
2504 if (isl_schedule_node_get_tree_depth(node
) == 0)
2505 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2506 "cannot delete root node",
2507 return isl_schedule_node_free(node
));
2508 n
= isl_schedule_node_n_children(node
);
2510 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2511 "can only delete node with a single child",
2512 return isl_schedule_node_free(node
));
2513 type
= isl_schedule_node_get_parent_type(node
);
2514 if (type
== isl_schedule_node_sequence
|| type
== isl_schedule_node_set
)
2515 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2516 "cannot delete child of set or sequence",
2517 return isl_schedule_node_free(node
));
2518 if (isl_schedule_node_get_type(node
) == isl_schedule_node_band
) {
2521 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2523 return isl_schedule_node_free(node
);
2525 isl_die(isl_schedule_node_get_ctx(node
),
2527 "cannot delete band node with anchored subtree",
2528 return isl_schedule_node_free(node
));
2531 tree
= isl_schedule_node_get_tree(node
);
2532 if (!tree
|| isl_schedule_tree_has_children(tree
)) {
2533 tree
= isl_schedule_tree_child(tree
, 0);
2535 isl_schedule_tree_free(tree
);
2536 tree
= isl_schedule_node_get_leaf(node
);
2538 node
= isl_schedule_node_graft_tree(node
, tree
);
2543 /* Internal data structure for the group_ancestor callback.
2545 * If "finished" is set, then we no longer need to modify
2546 * any further ancestors.
2548 * "contraction" and "expansion" represent the expansion
2549 * that reflects the grouping.
2551 * "domain" contains the domain elements that reach the position
2552 * where the grouping is performed. That is, it is the range
2553 * of the resulting expansion.
2554 * "domain_universe" is the universe of "domain".
2555 * "group" is the set of group elements, i.e., the domain
2556 * of the resulting expansion.
2557 * "group_universe" is the universe of "group".
2559 * "sched" is the schedule for the group elements, in pratice
2560 * an identity mapping on "group_universe".
2561 * "dim" is the dimension of "sched".
2563 struct isl_schedule_group_data
{
2566 isl_union_map
*expansion
;
2567 isl_union_pw_multi_aff
*contraction
;
2569 isl_union_set
*domain
;
2570 isl_union_set
*domain_universe
;
2571 isl_union_set
*group
;
2572 isl_union_set
*group_universe
;
2575 isl_multi_aff
*sched
;
2578 /* Is domain covered by data->domain within data->domain_universe?
2580 static int locally_covered_by_domain(__isl_keep isl_union_set
*domain
,
2581 struct isl_schedule_group_data
*data
)
2584 isl_union_set
*test
;
2586 test
= isl_union_set_copy(domain
);
2587 test
= isl_union_set_intersect(test
,
2588 isl_union_set_copy(data
->domain_universe
));
2589 is_subset
= isl_union_set_is_subset(test
, data
->domain
);
2590 isl_union_set_free(test
);
2595 /* Update the band tree root "tree" to refer to the group instances
2596 * in data->group rather than the original domain elements in data->domain.
2597 * "pos" is the position in the original schedule tree where the modified
2598 * "tree" will be attached.
2600 * Add the part of the identity schedule on the group instances data->sched
2601 * that corresponds to this band node to the band schedule.
2602 * If the domain elements that reach the node and that are part
2603 * of data->domain_universe are all elements of data->domain (and therefore
2604 * replaced by the group instances) then this data->domain_universe
2605 * is removed from the domain of the band schedule.
2607 static __isl_give isl_schedule_tree
*group_band(
2608 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2609 struct isl_schedule_group_data
*data
)
2611 isl_union_set
*domain
;
2613 isl_multi_union_pw_aff
*mupa
, *partial
;
2615 int depth
, n
, has_id
;
2617 domain
= isl_schedule_node_get_domain(pos
);
2618 is_covered
= locally_covered_by_domain(domain
, data
);
2619 if (is_covered
>= 0 && is_covered
) {
2620 domain
= isl_union_set_universe(domain
);
2621 domain
= isl_union_set_subtract(domain
,
2622 isl_union_set_copy(data
->domain_universe
));
2623 tree
= isl_schedule_tree_band_intersect_domain(tree
, domain
);
2625 isl_union_set_free(domain
);
2627 return isl_schedule_tree_free(tree
);
2628 depth
= isl_schedule_node_get_schedule_depth(pos
);
2629 n
= isl_schedule_tree_band_n_member(tree
);
2630 ma
= isl_multi_aff_copy(data
->sched
);
2631 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, depth
);
2632 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, n
, data
->dim
- depth
- n
);
2633 mupa
= isl_multi_union_pw_aff_from_multi_aff(ma
);
2634 partial
= isl_schedule_tree_band_get_partial_schedule(tree
);
2635 has_id
= isl_multi_union_pw_aff_has_tuple_id(partial
, isl_dim_set
);
2637 partial
= isl_multi_union_pw_aff_free(partial
);
2638 } else if (has_id
) {
2640 id
= isl_multi_union_pw_aff_get_tuple_id(partial
, isl_dim_set
);
2641 mupa
= isl_multi_union_pw_aff_set_tuple_id(mupa
,
2644 partial
= isl_multi_union_pw_aff_union_add(partial
, mupa
);
2645 tree
= isl_schedule_tree_band_set_partial_schedule(tree
, partial
);
2650 /* Drop the parameters in "uset" that are not also in "space".
2651 * "n" is the number of parameters in "space".
2653 static __isl_give isl_union_set
*union_set_drop_extra_params(
2654 __isl_take isl_union_set
*uset
, __isl_keep isl_space
*space
, int n
)
2658 uset
= isl_union_set_align_params(uset
, isl_space_copy(space
));
2659 n2
= isl_union_set_dim(uset
, isl_dim_param
);
2660 uset
= isl_union_set_project_out(uset
, isl_dim_param
, n
, n2
- n
);
2665 /* Update the context tree root "tree" to refer to the group instances
2666 * in data->group rather than the original domain elements in data->domain.
2667 * "pos" is the position in the original schedule tree where the modified
2668 * "tree" will be attached.
2670 * We do not actually need to update "tree" since a context node only
2671 * refers to the schedule space. However, we may need to update "data"
2672 * to not refer to any parameters introduced by the context node.
2674 static __isl_give isl_schedule_tree
*group_context(
2675 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2676 struct isl_schedule_group_data
*data
)
2679 isl_union_set
*domain
;
2683 if (isl_schedule_node_get_tree_depth(pos
) == 1)
2686 domain
= isl_schedule_node_get_universe_domain(pos
);
2687 space
= isl_union_set_get_space(domain
);
2688 isl_union_set_free(domain
);
2690 n1
= isl_space_dim(space
, isl_dim_param
);
2691 data
->expansion
= isl_union_map_align_params(data
->expansion
, space
);
2692 n2
= isl_union_map_dim(data
->expansion
, isl_dim_param
);
2694 if (!data
->expansion
)
2695 return isl_schedule_tree_free(tree
);
2699 involves
= isl_union_map_involves_dims(data
->expansion
,
2700 isl_dim_param
, n1
, n2
- n1
);
2702 return isl_schedule_tree_free(tree
);
2704 isl_die(isl_schedule_node_get_ctx(pos
), isl_error_invalid
,
2705 "grouping cannot only refer to global parameters",
2706 return isl_schedule_tree_free(tree
));
2708 data
->expansion
= isl_union_map_project_out(data
->expansion
,
2709 isl_dim_param
, n1
, n2
- n1
);
2710 space
= isl_union_map_get_space(data
->expansion
);
2712 data
->contraction
= isl_union_pw_multi_aff_align_params(
2713 data
->contraction
, isl_space_copy(space
));
2714 n2
= isl_union_pw_multi_aff_dim(data
->contraction
, isl_dim_param
);
2715 data
->contraction
= isl_union_pw_multi_aff_drop_dims(data
->contraction
,
2716 isl_dim_param
, n1
, n2
- n1
);
2718 data
->domain
= union_set_drop_extra_params(data
->domain
, space
, n1
);
2719 data
->domain_universe
=
2720 union_set_drop_extra_params(data
->domain_universe
, space
, n1
);
2721 data
->group
= union_set_drop_extra_params(data
->group
, space
, n1
);
2722 data
->group_universe
=
2723 union_set_drop_extra_params(data
->group_universe
, space
, n1
);
2725 data
->sched
= isl_multi_aff_align_params(data
->sched
,
2726 isl_space_copy(space
));
2727 n2
= isl_multi_aff_dim(data
->sched
, isl_dim_param
);
2728 data
->sched
= isl_multi_aff_drop_dims(data
->sched
,
2729 isl_dim_param
, n1
, n2
- n1
);
2731 isl_space_free(space
);
2736 /* Update the domain tree root "tree" to refer to the group instances
2737 * in data->group rather than the original domain elements in data->domain.
2738 * "pos" is the position in the original schedule tree where the modified
2739 * "tree" will be attached.
2741 * We first double-check that all grouped domain elements are actually
2742 * part of the root domain and then replace those elements by the group
2745 static __isl_give isl_schedule_tree
*group_domain(
2746 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2747 struct isl_schedule_group_data
*data
)
2749 isl_union_set
*domain
;
2752 domain
= isl_schedule_tree_domain_get_domain(tree
);
2753 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2754 isl_union_set_free(domain
);
2756 return isl_schedule_tree_free(tree
);
2758 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2759 "grouped domain should be part of outer domain",
2760 return isl_schedule_tree_free(tree
));
2761 domain
= isl_schedule_tree_domain_get_domain(tree
);
2762 domain
= isl_union_set_subtract(domain
,
2763 isl_union_set_copy(data
->domain
));
2764 domain
= isl_union_set_union(domain
, isl_union_set_copy(data
->group
));
2765 tree
= isl_schedule_tree_domain_set_domain(tree
, domain
);
2770 /* Update the expansion tree root "tree" to refer to the group instances
2771 * in data->group rather than the original domain elements in data->domain.
2772 * "pos" is the position in the original schedule tree where the modified
2773 * "tree" will be attached.
2775 * Let G_1 -> D_1 be the expansion of "tree" and G_2 -> D_2 the newly
2776 * introduced expansion in a descendant of "tree".
2777 * We first double-check that D_2 is a subset of D_1.
2778 * Then we remove D_2 from the range of G_1 -> D_1 and add the mapping
2779 * G_1 -> D_1 . D_2 -> G_2.
2780 * Simmilarly, we restrict the domain of the contraction to the universe
2781 * of the range of the updated expansion and add G_2 -> D_2 . D_1 -> G_1,
2782 * attempting to remove the domain constraints of this additional part.
2784 static __isl_give isl_schedule_tree
*group_expansion(
2785 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2786 struct isl_schedule_group_data
*data
)
2788 isl_union_set
*domain
;
2789 isl_union_map
*expansion
, *umap
;
2790 isl_union_pw_multi_aff
*contraction
, *upma
;
2793 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2794 domain
= isl_union_map_range(expansion
);
2795 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2796 isl_union_set_free(domain
);
2798 return isl_schedule_tree_free(tree
);
2800 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2801 "grouped domain should be part "
2802 "of outer expansion domain",
2803 return isl_schedule_tree_free(tree
));
2804 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2805 umap
= isl_union_map_from_union_pw_multi_aff(
2806 isl_union_pw_multi_aff_copy(data
->contraction
));
2807 umap
= isl_union_map_apply_range(expansion
, umap
);
2808 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2809 expansion
= isl_union_map_subtract_range(expansion
,
2810 isl_union_set_copy(data
->domain
));
2811 expansion
= isl_union_map_union(expansion
, umap
);
2812 umap
= isl_union_map_universe(isl_union_map_copy(expansion
));
2813 domain
= isl_union_map_range(umap
);
2814 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
2815 umap
= isl_union_map_from_union_pw_multi_aff(contraction
);
2816 umap
= isl_union_map_apply_range(isl_union_map_copy(data
->expansion
),
2818 upma
= isl_union_pw_multi_aff_from_union_map(umap
);
2819 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
2820 contraction
= isl_union_pw_multi_aff_intersect_domain(contraction
,
2822 domain
= isl_union_pw_multi_aff_domain(
2823 isl_union_pw_multi_aff_copy(upma
));
2824 upma
= isl_union_pw_multi_aff_gist(upma
, domain
);
2825 contraction
= isl_union_pw_multi_aff_union_add(contraction
, upma
);
2826 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
2827 contraction
, expansion
);
2832 /* Update the tree root "tree" to refer to the group instances
2833 * in data->group rather than the original domain elements in data->domain.
2834 * "pos" is the position in the original schedule tree where the modified
2835 * "tree" will be attached.
2837 * If we have come across a domain or expansion node before (data->finished
2838 * is set), then we no longer need perform any modifications.
2840 * If "tree" is a filter, then we add data->group_universe to the filter.
2841 * We also remove data->domain_universe from the filter if all the domain
2842 * elements in this universe that reach the filter node are part of
2843 * the elements that are being grouped by data->expansion.
2844 * If "tree" is a band, domain or expansion, then it is handled
2845 * in a separate function.
2847 static __isl_give isl_schedule_tree
*group_ancestor(
2848 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2851 struct isl_schedule_group_data
*data
= user
;
2852 isl_union_set
*domain
;
2856 return isl_schedule_tree_free(tree
);
2861 switch (isl_schedule_tree_get_type(tree
)) {
2862 case isl_schedule_node_error
:
2863 return isl_schedule_tree_free(tree
);
2864 case isl_schedule_node_extension
:
2865 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_unsupported
,
2866 "grouping not allowed in extended tree",
2867 return isl_schedule_tree_free(tree
));
2868 case isl_schedule_node_band
:
2869 tree
= group_band(tree
, pos
, data
);
2871 case isl_schedule_node_context
:
2872 tree
= group_context(tree
, pos
, data
);
2874 case isl_schedule_node_domain
:
2875 tree
= group_domain(tree
, pos
, data
);
2878 case isl_schedule_node_filter
:
2879 domain
= isl_schedule_node_get_domain(pos
);
2880 is_covered
= locally_covered_by_domain(domain
, data
);
2881 isl_union_set_free(domain
);
2883 return isl_schedule_tree_free(tree
);
2884 domain
= isl_schedule_tree_filter_get_filter(tree
);
2886 domain
= isl_union_set_subtract(domain
,
2887 isl_union_set_copy(data
->domain_universe
));
2888 domain
= isl_union_set_union(domain
,
2889 isl_union_set_copy(data
->group_universe
));
2890 tree
= isl_schedule_tree_filter_set_filter(tree
, domain
);
2892 case isl_schedule_node_expansion
:
2893 tree
= group_expansion(tree
, pos
, data
);
2896 case isl_schedule_node_leaf
:
2897 case isl_schedule_node_guard
:
2898 case isl_schedule_node_mark
:
2899 case isl_schedule_node_sequence
:
2900 case isl_schedule_node_set
:
2907 /* Group the domain elements that reach "node" into instances
2908 * of a single statement with identifier "group_id".
2909 * In particular, group the domain elements according to their
2912 * That is, introduce an expansion node with as contraction
2913 * the prefix schedule (with the target space replaced by "group_id")
2914 * and as expansion the inverse of this contraction (with its range
2915 * intersected with the domain elements that reach "node").
2916 * The outer nodes are then modified to refer to the group instances
2917 * instead of the original domain elements.
2919 * No instance of "group_id" is allowed to reach "node" prior
2921 * No ancestor of "node" is allowed to be an extension node.
2923 * Return a pointer to original node in tree, i.e., the child
2924 * of the newly introduced expansion node.
2926 __isl_give isl_schedule_node
*isl_schedule_node_group(
2927 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*group_id
)
2929 struct isl_schedule_group_data data
= { 0 };
2931 isl_union_set
*domain
;
2932 isl_union_pw_multi_aff
*contraction
;
2933 isl_union_map
*expansion
;
2936 if (!node
|| !group_id
)
2938 if (check_insert(node
) < 0)
2941 domain
= isl_schedule_node_get_domain(node
);
2942 data
.domain
= isl_union_set_copy(domain
);
2943 data
.domain_universe
= isl_union_set_copy(domain
);
2944 data
.domain_universe
= isl_union_set_universe(data
.domain_universe
);
2946 data
.dim
= isl_schedule_node_get_schedule_depth(node
);
2947 if (data
.dim
== 0) {
2950 isl_union_set
*group
;
2951 isl_union_map
*univ
;
2953 ctx
= isl_schedule_node_get_ctx(node
);
2954 space
= isl_space_set_alloc(ctx
, 0, 0);
2955 space
= isl_space_set_tuple_id(space
, isl_dim_set
, group_id
);
2956 set
= isl_set_universe(isl_space_copy(space
));
2957 group
= isl_union_set_from_set(set
);
2958 expansion
= isl_union_map_from_domain_and_range(domain
, group
);
2959 univ
= isl_union_map_universe(isl_union_map_copy(expansion
));
2960 contraction
= isl_union_pw_multi_aff_from_union_map(univ
);
2961 expansion
= isl_union_map_reverse(expansion
);
2963 isl_multi_union_pw_aff
*prefix
;
2964 isl_union_set
*univ
;
2967 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node
);
2968 prefix
= isl_multi_union_pw_aff_set_tuple_id(prefix
,
2969 isl_dim_set
, group_id
);
2970 space
= isl_multi_union_pw_aff_get_space(prefix
);
2971 contraction
= isl_union_pw_multi_aff_from_multi_union_pw_aff(
2973 univ
= isl_union_set_universe(isl_union_set_copy(domain
));
2975 isl_union_pw_multi_aff_intersect_domain(contraction
, univ
);
2976 expansion
= isl_union_map_from_union_pw_multi_aff(
2977 isl_union_pw_multi_aff_copy(contraction
));
2978 expansion
= isl_union_map_reverse(expansion
);
2979 expansion
= isl_union_map_intersect_range(expansion
, domain
);
2981 space
= isl_space_map_from_set(space
);
2982 data
.sched
= isl_multi_aff_identity(space
);
2983 data
.group
= isl_union_map_domain(isl_union_map_copy(expansion
));
2984 data
.group
= isl_union_set_coalesce(data
.group
);
2985 data
.group_universe
= isl_union_set_copy(data
.group
);
2986 data
.group_universe
= isl_union_set_universe(data
.group_universe
);
2987 data
.expansion
= isl_union_map_copy(expansion
);
2988 data
.contraction
= isl_union_pw_multi_aff_copy(contraction
);
2989 node
= isl_schedule_node_insert_expansion(node
, contraction
, expansion
);
2991 disjoint
= isl_union_set_is_disjoint(data
.domain_universe
,
2992 data
.group_universe
);
2994 node
= update_ancestors(node
, &group_ancestor
, &data
);
2996 isl_union_set_free(data
.domain
);
2997 isl_union_set_free(data
.domain_universe
);
2998 isl_union_set_free(data
.group
);
2999 isl_union_set_free(data
.group_universe
);
3000 isl_multi_aff_free(data
.sched
);
3001 isl_union_map_free(data
.expansion
);
3002 isl_union_pw_multi_aff_free(data
.contraction
);
3004 node
= isl_schedule_node_child(node
, 0);
3006 if (!node
|| disjoint
< 0)
3007 return isl_schedule_node_free(node
);
3009 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3010 "group instances already reach node",
3011 isl_schedule_node_free(node
));
3015 isl_schedule_node_free(node
);
3016 isl_id_free(group_id
);
3020 /* Compute the gist of the given band node with respect to "context".
3022 __isl_give isl_schedule_node
*isl_schedule_node_band_gist(
3023 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3025 isl_schedule_tree
*tree
;
3027 tree
= isl_schedule_node_get_tree(node
);
3028 tree
= isl_schedule_tree_band_gist(tree
, context
);
3029 return isl_schedule_node_graft_tree(node
, tree
);
3032 /* Internal data structure for isl_schedule_node_gist.
3033 * "n_expansion" is the number of outer expansion nodes
3034 * with respect to the current position
3035 * "filters" contains an element for each outer filter, expansion or
3036 * extension node with respect to the current position, each representing
3037 * the intersection of the previous element and the filter on the filter node
3038 * or the expansion/extension of the previous element.
3039 * The first element in the original context passed to isl_schedule_node_gist.
3041 struct isl_node_gist_data
{
3043 isl_union_set_list
*filters
;
3046 /* Enter the expansion node "node" during a isl_schedule_node_gist traversal.
3048 * In particular, add an extra element to data->filters containing
3049 * the expansion of the previous element and replace the expansion
3050 * and contraction on "node" by the gist with respect to these filters.
3051 * Also keep track of the fact that we have entered another expansion.
3053 static __isl_give isl_schedule_node
*gist_enter_expansion(
3054 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3057 isl_union_set
*inner
;
3058 isl_union_map
*expansion
;
3059 isl_union_pw_multi_aff
*contraction
;
3061 data
->n_expansion
++;
3063 n
= isl_union_set_list_n_union_set(data
->filters
);
3064 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3065 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3066 inner
= isl_union_set_apply(inner
, expansion
);
3068 contraction
= isl_schedule_node_expansion_get_contraction(node
);
3069 contraction
= isl_union_pw_multi_aff_gist(contraction
,
3070 isl_union_set_copy(inner
));
3072 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
3074 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3075 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3076 expansion
= isl_union_map_gist_domain(expansion
, inner
);
3077 node
= isl_schedule_node_expansion_set_contraction_and_expansion(node
,
3078 contraction
, expansion
);
3083 /* Enter the extension node "node" during a isl_schedule_node_gist traversal.
3085 * In particular, add an extra element to data->filters containing
3086 * the union of the previous element with the additional domain elements
3087 * introduced by the extension.
3089 static __isl_give isl_schedule_node
*gist_enter_extension(
3090 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3093 isl_union_set
*inner
, *extra
;
3094 isl_union_map
*extension
;
3096 n
= isl_union_set_list_n_union_set(data
->filters
);
3097 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3098 extension
= isl_schedule_node_extension_get_extension(node
);
3099 extra
= isl_union_map_range(extension
);
3100 inner
= isl_union_set_union(inner
, extra
);
3102 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
3107 /* Can we finish gisting at this node?
3108 * That is, is the filter on the current filter node a subset of
3109 * the original context passed to isl_schedule_node_gist?
3110 * If we have gone through any expansions, then we cannot perform
3111 * this test since the current domain elements are incomparable
3112 * to the domain elements in the original context.
3114 static int gist_done(__isl_keep isl_schedule_node
*node
,
3115 struct isl_node_gist_data
*data
)
3117 isl_union_set
*filter
, *outer
;
3120 if (data
->n_expansion
!= 0)
3123 filter
= isl_schedule_node_filter_get_filter(node
);
3124 outer
= isl_union_set_list_get_union_set(data
->filters
, 0);
3125 subset
= isl_union_set_is_subset(filter
, outer
);
3126 isl_union_set_free(outer
);
3127 isl_union_set_free(filter
);
3132 /* Callback for "traverse" to enter a node and to move
3133 * to the deepest initial subtree that should be traversed
3134 * by isl_schedule_node_gist.
3136 * The "filters" list is extended by one element each time
3137 * we come across a filter node by the result of intersecting
3138 * the last element in the list with the filter on the filter node.
3140 * If the filter on the current filter node is a subset of
3141 * the original context passed to isl_schedule_node_gist,
3142 * then there is no need to go into its subtree since it cannot
3143 * be further simplified by the context. The "filters" list is
3144 * still extended for consistency, but the actual value of the
3145 * added element is immaterial since it will not be used.
3147 * Otherwise, the filter on the current filter node is replaced by
3148 * the gist of the original filter with respect to the intersection
3149 * of the original context with the intermediate filters.
3151 * If the new element in the "filters" list is empty, then no elements
3152 * can reach the descendants of the current filter node. The subtree
3153 * underneath the filter node is therefore removed.
3155 * Each expansion node we come across is handled by
3156 * gist_enter_expansion.
3158 * Each extension node we come across is handled by
3159 * gist_enter_extension.
3161 static __isl_give isl_schedule_node
*gist_enter(
3162 __isl_take isl_schedule_node
*node
, void *user
)
3164 struct isl_node_gist_data
*data
= user
;
3167 isl_union_set
*filter
, *inner
;
3171 switch (isl_schedule_node_get_type(node
)) {
3172 case isl_schedule_node_error
:
3173 return isl_schedule_node_free(node
);
3174 case isl_schedule_node_expansion
:
3175 node
= gist_enter_expansion(node
, data
);
3177 case isl_schedule_node_extension
:
3178 node
= gist_enter_extension(node
, data
);
3180 case isl_schedule_node_band
:
3181 case isl_schedule_node_context
:
3182 case isl_schedule_node_domain
:
3183 case isl_schedule_node_guard
:
3184 case isl_schedule_node_leaf
:
3185 case isl_schedule_node_mark
:
3186 case isl_schedule_node_sequence
:
3187 case isl_schedule_node_set
:
3189 case isl_schedule_node_filter
:
3192 done
= gist_done(node
, data
);
3193 filter
= isl_schedule_node_filter_get_filter(node
);
3194 if (done
< 0 || done
) {
3195 data
->filters
= isl_union_set_list_add(data
->filters
,
3198 return isl_schedule_node_free(node
);
3201 n
= isl_union_set_list_n_union_set(data
->filters
);
3202 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3203 filter
= isl_union_set_gist(filter
, isl_union_set_copy(inner
));
3204 node
= isl_schedule_node_filter_set_filter(node
,
3205 isl_union_set_copy(filter
));
3206 filter
= isl_union_set_intersect(filter
, inner
);
3207 empty
= isl_union_set_is_empty(filter
);
3208 data
->filters
= isl_union_set_list_add(data
->filters
, filter
);
3210 return isl_schedule_node_free(node
);
3213 node
= isl_schedule_node_child(node
, 0);
3214 node
= isl_schedule_node_cut(node
);
3215 node
= isl_schedule_node_parent(node
);
3217 } while (isl_schedule_node_has_children(node
) &&
3218 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3223 /* Callback for "traverse" to leave a node for isl_schedule_node_gist.
3225 * In particular, if the current node is a filter node, then we remove
3226 * the element on the "filters" list that was added when we entered
3227 * the node. There is no need to compute any gist here, since we
3228 * already did that when we entered the node.
3230 * If the current node is an expansion, then we decrement
3231 * the number of outer expansions and remove the element
3232 * in data->filters that was added by gist_enter_expansion.
3234 * If the current node is an extension, then remove the element
3235 * in data->filters that was added by gist_enter_extension.
3237 * If the current node is a band node, then we compute the gist of
3238 * the band node with respect to the intersection of the original context
3239 * and the intermediate filters.
3241 * If the current node is a sequence or set node, then some of
3242 * the filter children may have become empty and so they are removed.
3243 * If only one child is left, then the set or sequence node along with
3244 * the single remaining child filter is removed. The filter can be
3245 * removed because the filters on a sequence or set node are supposed
3246 * to partition the incoming domain instances.
3247 * In principle, it should then be impossible for there to be zero
3248 * remaining children, but should this happen, we replace the entire
3249 * subtree with an empty filter.
3251 static __isl_give isl_schedule_node
*gist_leave(
3252 __isl_take isl_schedule_node
*node
, void *user
)
3254 struct isl_node_gist_data
*data
= user
;
3255 isl_schedule_tree
*tree
;
3257 isl_union_set
*filter
;
3259 switch (isl_schedule_node_get_type(node
)) {
3260 case isl_schedule_node_error
:
3261 return isl_schedule_node_free(node
);
3262 case isl_schedule_node_expansion
:
3263 data
->n_expansion
--;
3264 case isl_schedule_node_extension
:
3265 case isl_schedule_node_filter
:
3266 n
= isl_union_set_list_n_union_set(data
->filters
);
3267 data
->filters
= isl_union_set_list_drop(data
->filters
,
3270 case isl_schedule_node_band
:
3271 n
= isl_union_set_list_n_union_set(data
->filters
);
3272 filter
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3273 node
= isl_schedule_node_band_gist(node
, filter
);
3275 case isl_schedule_node_set
:
3276 case isl_schedule_node_sequence
:
3277 tree
= isl_schedule_node_get_tree(node
);
3278 n
= isl_schedule_tree_n_children(tree
);
3279 for (i
= n
- 1; i
>= 0; --i
) {
3280 isl_schedule_tree
*child
;
3281 isl_union_set
*filter
;
3284 child
= isl_schedule_tree_get_child(tree
, i
);
3285 filter
= isl_schedule_tree_filter_get_filter(child
);
3286 empty
= isl_union_set_is_empty(filter
);
3287 isl_union_set_free(filter
);
3288 isl_schedule_tree_free(child
);
3290 tree
= isl_schedule_tree_free(tree
);
3292 tree
= isl_schedule_tree_drop_child(tree
, i
);
3294 n
= isl_schedule_tree_n_children(tree
);
3295 node
= isl_schedule_node_graft_tree(node
, tree
);
3297 node
= isl_schedule_node_delete(node
);
3298 node
= isl_schedule_node_delete(node
);
3299 } else if (n
== 0) {
3303 isl_union_set_list_get_union_set(data
->filters
, 0);
3304 space
= isl_union_set_get_space(filter
);
3305 isl_union_set_free(filter
);
3306 filter
= isl_union_set_empty(space
);
3307 node
= isl_schedule_node_cut(node
);
3308 node
= isl_schedule_node_insert_filter(node
, filter
);
3311 case isl_schedule_node_context
:
3312 case isl_schedule_node_domain
:
3313 case isl_schedule_node_guard
:
3314 case isl_schedule_node_leaf
:
3315 case isl_schedule_node_mark
:
3322 /* Compute the gist of the subtree at "node" with respect to
3323 * the reaching domain elements in "context".
3324 * In particular, compute the gist of all band and filter nodes
3325 * in the subtree with respect to "context". Children of set or sequence
3326 * nodes that end up with an empty filter are removed completely.
3328 * We keep track of the intersection of "context" with all outer filters
3329 * of the current node within the subtree in the final element of "filters".
3330 * Initially, this list contains the single element "context" and it is
3331 * extended or shortened each time we enter or leave a filter node.
3333 __isl_give isl_schedule_node
*isl_schedule_node_gist(
3334 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3336 struct isl_node_gist_data data
;
3338 data
.n_expansion
= 0;
3339 data
.filters
= isl_union_set_list_from_union_set(context
);
3340 node
= traverse(node
, &gist_enter
, &gist_leave
, &data
);
3341 isl_union_set_list_free(data
.filters
);
3345 /* Intersect the domain of domain node "node" with "domain".
3347 * If the domain of "node" is already a subset of "domain",
3348 * then nothing needs to be changed.
3350 * Otherwise, we replace the domain of the domain node by the intersection
3351 * and simplify the subtree rooted at "node" with respect to this intersection.
3353 __isl_give isl_schedule_node
*isl_schedule_node_domain_intersect_domain(
3354 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
)
3356 isl_schedule_tree
*tree
;
3357 isl_union_set
*uset
;
3360 if (!node
|| !domain
)
3363 uset
= isl_schedule_tree_domain_get_domain(node
->tree
);
3364 is_subset
= isl_union_set_is_subset(uset
, domain
);
3365 isl_union_set_free(uset
);
3369 isl_union_set_free(domain
);
3373 tree
= isl_schedule_tree_copy(node
->tree
);
3374 uset
= isl_schedule_tree_domain_get_domain(tree
);
3375 uset
= isl_union_set_intersect(uset
, domain
);
3376 tree
= isl_schedule_tree_domain_set_domain(tree
,
3377 isl_union_set_copy(uset
));
3378 node
= isl_schedule_node_graft_tree(node
, tree
);
3380 node
= isl_schedule_node_child(node
, 0);
3381 node
= isl_schedule_node_gist(node
, uset
);
3382 node
= isl_schedule_node_parent(node
);
3386 isl_schedule_node_free(node
);
3387 isl_union_set_free(domain
);
3391 /* Internal data structure for isl_schedule_node_get_subtree_expansion.
3392 * "expansions" contains a list of accumulated expansions
3393 * for each outer expansion, set or sequence node. The first element
3394 * in the list is an identity mapping on the reaching domain elements.
3395 * "res" collects the results.
3397 struct isl_subtree_expansion_data
{
3398 isl_union_map_list
*expansions
;
3402 /* Callback for "traverse" to enter a node and to move
3403 * to the deepest initial subtree that should be traversed
3404 * by isl_schedule_node_get_subtree_expansion.
3406 * Whenever we come across an expansion node, the last element
3407 * of data->expansions is combined with the expansion
3408 * on the expansion node.
3410 * Whenever we come across a filter node that is the child
3411 * of a set or sequence node, data->expansions is extended
3412 * with a new element that restricts the previous element
3413 * to the elements selected by the filter.
3414 * The previous element can then be reused while backtracking.
3416 static __isl_give isl_schedule_node
*subtree_expansion_enter(
3417 __isl_take isl_schedule_node
*node
, void *user
)
3419 struct isl_subtree_expansion_data
*data
= user
;
3422 enum isl_schedule_node_type type
;
3423 isl_union_set
*filter
;
3424 isl_union_map
*inner
, *expansion
;
3427 switch (isl_schedule_node_get_type(node
)) {
3428 case isl_schedule_node_error
:
3429 return isl_schedule_node_free(node
);
3430 case isl_schedule_node_filter
:
3431 type
= isl_schedule_node_get_parent_type(node
);
3432 if (type
!= isl_schedule_node_set
&&
3433 type
!= isl_schedule_node_sequence
)
3435 filter
= isl_schedule_node_filter_get_filter(node
);
3436 n
= isl_union_map_list_n_union_map(data
->expansions
);
3438 isl_union_map_list_get_union_map(data
->expansions
,
3440 inner
= isl_union_map_intersect_range(inner
, filter
);
3442 isl_union_map_list_add(data
->expansions
, inner
);
3444 case isl_schedule_node_expansion
:
3445 n
= isl_union_map_list_n_union_map(data
->expansions
);
3447 isl_schedule_node_expansion_get_expansion(node
);
3449 isl_union_map_list_get_union_map(data
->expansions
,
3451 inner
= isl_union_map_apply_range(inner
, expansion
);
3453 isl_union_map_list_set_union_map(data
->expansions
,
3456 case isl_schedule_node_band
:
3457 case isl_schedule_node_context
:
3458 case isl_schedule_node_domain
:
3459 case isl_schedule_node_extension
:
3460 case isl_schedule_node_guard
:
3461 case isl_schedule_node_leaf
:
3462 case isl_schedule_node_mark
:
3463 case isl_schedule_node_sequence
:
3464 case isl_schedule_node_set
:
3467 } while (isl_schedule_node_has_children(node
) &&
3468 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3473 /* Callback for "traverse" to leave a node for
3474 * isl_schedule_node_get_subtree_expansion.
3476 * If we come across a filter node that is the child
3477 * of a set or sequence node, then we remove the element
3478 * of data->expansions that was added in subtree_expansion_enter.
3480 * If we reach a leaf node, then the accumulated expansion is
3481 * added to data->res.
3483 static __isl_give isl_schedule_node
*subtree_expansion_leave(
3484 __isl_take isl_schedule_node
*node
, void *user
)
3486 struct isl_subtree_expansion_data
*data
= user
;
3488 isl_union_map
*inner
;
3489 enum isl_schedule_node_type type
;
3491 switch (isl_schedule_node_get_type(node
)) {
3492 case isl_schedule_node_error
:
3493 return isl_schedule_node_free(node
);
3494 case isl_schedule_node_filter
:
3495 type
= isl_schedule_node_get_parent_type(node
);
3496 if (type
!= isl_schedule_node_set
&&
3497 type
!= isl_schedule_node_sequence
)
3499 n
= isl_union_map_list_n_union_map(data
->expansions
);
3500 data
->expansions
= isl_union_map_list_drop(data
->expansions
,
3503 case isl_schedule_node_leaf
:
3504 n
= isl_union_map_list_n_union_map(data
->expansions
);
3505 inner
= isl_union_map_list_get_union_map(data
->expansions
,
3507 data
->res
= isl_union_map_union(data
->res
, inner
);
3509 case isl_schedule_node_band
:
3510 case isl_schedule_node_context
:
3511 case isl_schedule_node_domain
:
3512 case isl_schedule_node_expansion
:
3513 case isl_schedule_node_extension
:
3514 case isl_schedule_node_guard
:
3515 case isl_schedule_node_mark
:
3516 case isl_schedule_node_sequence
:
3517 case isl_schedule_node_set
:
3524 /* Return a mapping from the domain elements that reach "node"
3525 * to the corresponding domain elements in the leaves of the subtree
3526 * rooted at "node" obtained by composing the intermediate expansions.
3528 * We start out with an identity mapping between the domain elements
3529 * that reach "node" and compose it with all the expansions
3530 * on a path from "node" to a leaf while traversing the subtree.
3531 * Within the children of an a sequence or set node, the
3532 * accumulated expansion is restricted to the elements selected
3533 * by the filter child.
3535 __isl_give isl_union_map
*isl_schedule_node_get_subtree_expansion(
3536 __isl_keep isl_schedule_node
*node
)
3538 struct isl_subtree_expansion_data data
;
3540 isl_union_set
*domain
;
3541 isl_union_map
*expansion
;
3546 domain
= isl_schedule_node_get_universe_domain(node
);
3547 space
= isl_union_set_get_space(domain
);
3548 expansion
= isl_union_set_identity(domain
);
3549 data
.res
= isl_union_map_empty(space
);
3550 data
.expansions
= isl_union_map_list_from_union_map(expansion
);
3552 node
= isl_schedule_node_copy(node
);
3553 node
= traverse(node
, &subtree_expansion_enter
,
3554 &subtree_expansion_leave
, &data
);
3556 data
.res
= isl_union_map_free(data
.res
);
3557 isl_schedule_node_free(node
);
3559 isl_union_map_list_free(data
.expansions
);
3564 /* Internal data structure for isl_schedule_node_get_subtree_contraction.
3565 * "contractions" contains a list of accumulated contractions
3566 * for each outer expansion, set or sequence node. The first element
3567 * in the list is an identity mapping on the reaching domain elements.
3568 * "res" collects the results.
3570 struct isl_subtree_contraction_data
{
3571 isl_union_pw_multi_aff_list
*contractions
;
3572 isl_union_pw_multi_aff
*res
;
3575 /* Callback for "traverse" to enter a node and to move
3576 * to the deepest initial subtree that should be traversed
3577 * by isl_schedule_node_get_subtree_contraction.
3579 * Whenever we come across an expansion node, the last element
3580 * of data->contractions is combined with the contraction
3581 * on the expansion node.
3583 * Whenever we come across a filter node that is the child
3584 * of a set or sequence node, data->contractions is extended
3585 * with a new element that restricts the previous element
3586 * to the elements selected by the filter.
3587 * The previous element can then be reused while backtracking.
3589 static __isl_give isl_schedule_node
*subtree_contraction_enter(
3590 __isl_take isl_schedule_node
*node
, void *user
)
3592 struct isl_subtree_contraction_data
*data
= user
;
3595 enum isl_schedule_node_type type
;
3596 isl_union_set
*filter
;
3597 isl_union_pw_multi_aff
*inner
, *contraction
;
3600 switch (isl_schedule_node_get_type(node
)) {
3601 case isl_schedule_node_error
:
3602 return isl_schedule_node_free(node
);
3603 case isl_schedule_node_filter
:
3604 type
= isl_schedule_node_get_parent_type(node
);
3605 if (type
!= isl_schedule_node_set
&&
3606 type
!= isl_schedule_node_sequence
)
3608 filter
= isl_schedule_node_filter_get_filter(node
);
3609 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3610 data
->contractions
);
3612 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3613 data
->contractions
, n
- 1);
3614 inner
= isl_union_pw_multi_aff_intersect_domain(inner
,
3616 data
->contractions
=
3617 isl_union_pw_multi_aff_list_add(data
->contractions
,
3620 case isl_schedule_node_expansion
:
3621 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3622 data
->contractions
);
3624 isl_schedule_node_expansion_get_contraction(node
);
3626 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3627 data
->contractions
, n
- 1);
3629 isl_union_pw_multi_aff_pullback_union_pw_multi_aff(
3630 inner
, contraction
);
3631 data
->contractions
=
3632 isl_union_pw_multi_aff_list_set_union_pw_multi_aff(
3633 data
->contractions
, n
- 1, inner
);
3635 case isl_schedule_node_band
:
3636 case isl_schedule_node_context
:
3637 case isl_schedule_node_domain
:
3638 case isl_schedule_node_extension
:
3639 case isl_schedule_node_guard
:
3640 case isl_schedule_node_leaf
:
3641 case isl_schedule_node_mark
:
3642 case isl_schedule_node_sequence
:
3643 case isl_schedule_node_set
:
3646 } while (isl_schedule_node_has_children(node
) &&
3647 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3652 /* Callback for "traverse" to leave a node for
3653 * isl_schedule_node_get_subtree_contraction.
3655 * If we come across a filter node that is the child
3656 * of a set or sequence node, then we remove the element
3657 * of data->contractions that was added in subtree_contraction_enter.
3659 * If we reach a leaf node, then the accumulated contraction is
3660 * added to data->res.
3662 static __isl_give isl_schedule_node
*subtree_contraction_leave(
3663 __isl_take isl_schedule_node
*node
, void *user
)
3665 struct isl_subtree_contraction_data
*data
= user
;
3667 isl_union_pw_multi_aff
*inner
;
3668 enum isl_schedule_node_type type
;
3670 switch (isl_schedule_node_get_type(node
)) {
3671 case isl_schedule_node_error
:
3672 return isl_schedule_node_free(node
);
3673 case isl_schedule_node_filter
:
3674 type
= isl_schedule_node_get_parent_type(node
);
3675 if (type
!= isl_schedule_node_set
&&
3676 type
!= isl_schedule_node_sequence
)
3678 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3679 data
->contractions
);
3680 data
->contractions
=
3681 isl_union_pw_multi_aff_list_drop(data
->contractions
,
3684 case isl_schedule_node_leaf
:
3685 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3686 data
->contractions
);
3687 inner
= isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3688 data
->contractions
, n
- 1);
3689 data
->res
= isl_union_pw_multi_aff_union_add(data
->res
, inner
);
3691 case isl_schedule_node_band
:
3692 case isl_schedule_node_context
:
3693 case isl_schedule_node_domain
:
3694 case isl_schedule_node_expansion
:
3695 case isl_schedule_node_extension
:
3696 case isl_schedule_node_guard
:
3697 case isl_schedule_node_mark
:
3698 case isl_schedule_node_sequence
:
3699 case isl_schedule_node_set
:
3706 /* Return a mapping from the domain elements in the leaves of the subtree
3707 * rooted at "node" to the corresponding domain elements that reach "node"
3708 * obtained by composing the intermediate contractions.
3710 * We start out with an identity mapping between the domain elements
3711 * that reach "node" and compose it with all the contractions
3712 * on a path from "node" to a leaf while traversing the subtree.
3713 * Within the children of an a sequence or set node, the
3714 * accumulated contraction is restricted to the elements selected
3715 * by the filter child.
3717 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_get_subtree_contraction(
3718 __isl_keep isl_schedule_node
*node
)
3720 struct isl_subtree_contraction_data data
;
3722 isl_union_set
*domain
;
3723 isl_union_pw_multi_aff
*contraction
;
3728 domain
= isl_schedule_node_get_universe_domain(node
);
3729 space
= isl_union_set_get_space(domain
);
3730 contraction
= isl_union_set_identity_union_pw_multi_aff(domain
);
3731 data
.res
= isl_union_pw_multi_aff_empty(space
);
3733 isl_union_pw_multi_aff_list_from_union_pw_multi_aff(contraction
);
3735 node
= isl_schedule_node_copy(node
);
3736 node
= traverse(node
, &subtree_contraction_enter
,
3737 &subtree_contraction_leave
, &data
);
3739 data
.res
= isl_union_pw_multi_aff_free(data
.res
);
3740 isl_schedule_node_free(node
);
3742 isl_union_pw_multi_aff_list_free(data
.contractions
);
3747 /* Do the nearest "n" ancestors of "node" have the types given in "types"
3748 * (starting at the parent of "node")?
3750 static int has_ancestors(__isl_keep isl_schedule_node
*node
,
3751 int n
, enum isl_schedule_node_type
*types
)
3758 n_ancestor
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
3762 for (i
= 0; i
< n
; ++i
) {
3763 isl_schedule_tree
*tree
;
3766 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
3767 n_ancestor
- 1 - i
);
3770 correct_type
= isl_schedule_tree_get_type(tree
) == types
[i
];
3771 isl_schedule_tree_free(tree
);
3779 /* Given a node "node" that appears in an extension (i.e., it is the child
3780 * of a filter in a sequence inside an extension node), are the spaces
3781 * of the extension specified by "extension" disjoint from those
3782 * of both the original extension and the domain elements that reach
3783 * that original extension?
3785 static int is_disjoint_extension(__isl_keep isl_schedule_node
*node
,
3786 __isl_keep isl_union_map
*extension
)
3789 isl_union_set
*domain
;
3792 node
= isl_schedule_node_copy(node
);
3793 node
= isl_schedule_node_parent(node
);
3794 node
= isl_schedule_node_parent(node
);
3795 node
= isl_schedule_node_parent(node
);
3796 old
= isl_schedule_node_extension_get_extension(node
);
3797 domain
= isl_schedule_node_get_universe_domain(node
);
3798 isl_schedule_node_free(node
);
3799 old
= isl_union_map_universe(old
);
3800 domain
= isl_union_set_union(domain
, isl_union_map_range(old
));
3801 extension
= isl_union_map_copy(extension
);
3802 extension
= isl_union_map_intersect_range(extension
, domain
);
3803 empty
= isl_union_map_is_empty(extension
);
3804 isl_union_map_free(extension
);
3809 /* Given a node "node" that is governed by an extension node, extend
3810 * that extension node with "extension".
3812 * In particular, "node" is the child of a filter in a sequence that
3813 * is in turn a child of an extension node. Extend that extension node
3816 * Return a pointer to the parent of the original node (i.e., a filter).
3818 static __isl_give isl_schedule_node
*extend_extension(
3819 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
3823 isl_union_map
*node_extension
;
3825 node
= isl_schedule_node_parent(node
);
3826 pos
= isl_schedule_node_get_child_position(node
);
3827 node
= isl_schedule_node_parent(node
);
3828 node
= isl_schedule_node_parent(node
);
3829 node_extension
= isl_schedule_node_extension_get_extension(node
);
3830 disjoint
= isl_union_map_is_disjoint(extension
, node_extension
);
3831 extension
= isl_union_map_union(extension
, node_extension
);
3832 node
= isl_schedule_node_extension_set_extension(node
, extension
);
3833 node
= isl_schedule_node_child(node
, 0);
3834 node
= isl_schedule_node_child(node
, pos
);
3837 return isl_schedule_node_free(node
);
3841 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3842 "extension domain should be disjoint from earlier "
3843 "extensions", return isl_schedule_node_free(node
));
3848 /* Return the universe of "uset" if this universe is disjoint from "ref".
3849 * Otherwise, return "uset".
3851 * Also check if "uset" itself is disjoint from "ref", reporting
3852 * an error if it is not.
3854 static __isl_give isl_union_set
*replace_by_universe_if_disjoint(
3855 __isl_take isl_union_set
*uset
, __isl_keep isl_union_set
*ref
)
3858 isl_union_set
*universe
;
3860 disjoint
= isl_union_set_is_disjoint(uset
, ref
);
3862 return isl_union_set_free(uset
);
3864 isl_die(isl_union_set_get_ctx(uset
), isl_error_invalid
,
3865 "extension domain should be disjoint from "
3866 "current domain", return isl_union_set_free(uset
));
3868 universe
= isl_union_set_universe(isl_union_set_copy(uset
));
3869 disjoint
= isl_union_set_is_disjoint(universe
, ref
);
3870 if (disjoint
>= 0 && disjoint
) {
3871 isl_union_set_free(uset
);
3874 isl_union_set_free(universe
);
3877 return isl_union_set_free(uset
);
3881 /* Insert an extension node on top of "node" with extension "extension".
3882 * In addition, insert a filter that separates node from the extension
3883 * between the extension node and "node".
3884 * Return a pointer to the inserted filter node.
3886 * If "node" already appears in an extension (i.e., if it is the child
3887 * of a filter in a sequence inside an extension node), then extend that
3888 * extension with "extension" instead.
3889 * In this case, a pointer to the original filter node is returned.
3890 * Note that if some of the elements in the new extension live in the
3891 * same space as those of the original extension or the domain elements
3892 * reaching the original extension, then we insert a new extension anyway.
3893 * Otherwise, we would have to adjust the filters in the sequence child
3894 * of the extension to ensure that the elements in the new extension
3897 static __isl_give isl_schedule_node
*insert_extension(
3898 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
3900 enum isl_schedule_node_type ancestors
[] =
3901 { isl_schedule_node_filter
, isl_schedule_node_sequence
,
3902 isl_schedule_node_extension
};
3903 isl_union_set
*domain
;
3904 isl_union_set
*filter
;
3907 in_ext
= has_ancestors(node
, 3, ancestors
);
3913 disjoint
= is_disjoint_extension(node
, extension
);
3917 return extend_extension(node
, extension
);
3920 filter
= isl_schedule_node_get_domain(node
);
3921 domain
= isl_union_map_range(isl_union_map_copy(extension
));
3922 filter
= replace_by_universe_if_disjoint(filter
, domain
);
3923 isl_union_set_free(domain
);
3925 node
= isl_schedule_node_insert_filter(node
, filter
);
3926 node
= isl_schedule_node_insert_extension(node
, extension
);
3927 node
= isl_schedule_node_child(node
, 0);
3930 isl_schedule_node_free(node
);
3931 isl_union_map_free(extension
);
3935 /* Replace the subtree that "node" points to by "tree" (which has
3936 * a sequence root with two children), except if the parent of "node"
3937 * is a sequence as well, in which case "tree" is spliced at the position
3938 * of "node" in its parent.
3939 * Return a pointer to the child of the "tree_pos" (filter) child of "tree"
3940 * in the updated schedule tree.
3942 static __isl_give isl_schedule_node
*graft_or_splice(
3943 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_tree
*tree
,
3948 if (isl_schedule_node_get_parent_type(node
) ==
3949 isl_schedule_node_sequence
) {
3950 pos
= isl_schedule_node_get_child_position(node
);
3951 node
= isl_schedule_node_parent(node
);
3952 node
= isl_schedule_node_sequence_splice(node
, pos
, tree
);
3955 node
= isl_schedule_node_graft_tree(node
, tree
);
3957 node
= isl_schedule_node_child(node
, pos
+ tree_pos
);
3958 node
= isl_schedule_node_child(node
, 0);
3963 /* Insert a node "graft" into the schedule tree of "node" such that it
3964 * is executed before (if "before" is set) or after (if "before" is not set)
3965 * the node that "node" points to.
3966 * The root of "graft" is an extension node.
3967 * Return a pointer to the node that "node" pointed to.
3969 * We first insert an extension node on top of "node" (or extend
3970 * the extension node if there already is one), with a filter on "node"
3971 * separating it from the extension.
3972 * We then insert a filter in the graft to separate it from the original
3973 * domain elements and combine the original and new tree in a sequence.
3974 * If we have extended an extension node, then the children of this
3975 * sequence are spliced in the sequence of the extended extension
3976 * at the position where "node" appears in the original extension.
3977 * Otherwise, the sequence pair is attached to the new extension node.
3979 static __isl_give isl_schedule_node
*graft_extension(
3980 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
,
3983 isl_union_map
*extension
;
3984 isl_union_set
*graft_domain
;
3985 isl_union_set
*node_domain
;
3986 isl_schedule_tree
*tree
, *tree_graft
;
3988 extension
= isl_schedule_node_extension_get_extension(graft
);
3989 graft_domain
= isl_union_map_range(isl_union_map_copy(extension
));
3990 node_domain
= isl_schedule_node_get_universe_domain(node
);
3991 node
= insert_extension(node
, extension
);
3993 graft_domain
= replace_by_universe_if_disjoint(graft_domain
,
3995 isl_union_set_free(node_domain
);
3997 tree
= isl_schedule_node_get_tree(node
);
3998 if (!isl_schedule_node_has_children(graft
)) {
3999 tree_graft
= isl_schedule_tree_from_filter(graft_domain
);
4001 graft
= isl_schedule_node_child(graft
, 0);
4002 tree_graft
= isl_schedule_node_get_tree(graft
);
4003 tree_graft
= isl_schedule_tree_insert_filter(tree_graft
,
4007 tree
= isl_schedule_tree_sequence_pair(tree_graft
, tree
);
4009 tree
= isl_schedule_tree_sequence_pair(tree
, tree_graft
);
4010 node
= graft_or_splice(node
, tree
, before
);
4012 isl_schedule_node_free(graft
);
4017 /* Replace the root domain node of "node" by an extension node suitable
4018 * for insertion at "pos".
4019 * That is, create an extension node that maps the outer band nodes
4020 * at "pos" to the domain of the root node of "node" and attach
4021 * the child of this root node to the extension node.
4023 static __isl_give isl_schedule_node
*extension_from_domain(
4024 __isl_take isl_schedule_node
*node
, __isl_keep isl_schedule_node
*pos
)
4026 isl_union_set
*universe
;
4027 isl_union_set
*domain
;
4032 isl_schedule_node
*res
;
4033 isl_schedule_tree
*tree
;
4035 anchored
= isl_schedule_node_is_subtree_anchored(node
);
4037 return isl_schedule_node_free(node
);
4039 isl_die(isl_schedule_node_get_ctx(node
), isl_error_unsupported
,
4040 "cannot graft anchored tree with domain root",
4041 return isl_schedule_node_free(node
));
4043 depth
= isl_schedule_node_get_schedule_depth(pos
);
4044 domain
= isl_schedule_node_domain_get_domain(node
);
4045 space
= isl_union_set_get_space(domain
);
4046 space
= isl_space_set_from_params(space
);
4047 space
= isl_space_add_dims(space
, isl_dim_set
, depth
);
4048 universe
= isl_union_set_from_set(isl_set_universe(space
));
4049 ext
= isl_union_map_from_domain_and_range(universe
, domain
);
4050 res
= isl_schedule_node_from_extension(ext
);
4051 node
= isl_schedule_node_child(node
, 0);
4053 return isl_schedule_node_free(res
);
4054 if (!isl_schedule_tree_is_leaf(node
->tree
)) {
4055 tree
= isl_schedule_node_get_tree(node
);
4056 res
= isl_schedule_node_child(res
, 0);
4057 res
= isl_schedule_node_graft_tree(res
, tree
);
4058 res
= isl_schedule_node_parent(res
);
4060 isl_schedule_node_free(node
);
4065 /* Insert a node "graft" into the schedule tree of "node" such that it
4066 * is executed before (if "before" is set) or after (if "before" is not set)
4067 * the node that "node" points to.
4068 * The root of "graft" may be either a domain or an extension node.
4069 * In the latter case, the domain of the extension needs to correspond
4070 * to the outer band nodes of "node".
4071 * The elements of the domain or the range of the extension may not
4072 * intersect with the domain elements that reach "node".
4073 * The schedule tree of "graft" may not be anchored.
4075 * The schedule tree of "node" is modified to include an extension node
4076 * corresponding to the root node of "graft" as a child of the original
4077 * parent of "node". The original node that "node" points to and the
4078 * child of the root node of "graft" are attached to this extension node
4079 * through a sequence, with appropriate filters and with the child
4080 * of "graft" appearing before or after the original "node".
4082 * If "node" already appears inside a sequence that is the child of
4083 * an extension node and if the spaces of the new domain elements
4084 * do not overlap with those of the original domain elements,
4085 * then that extension node is extended with the new extension
4086 * rather than introducing a new segment of extension and sequence nodes.
4088 * Return a pointer to the same node in the modified tree that
4089 * "node" pointed to in the original tree.
4091 static __isl_give isl_schedule_node
*isl_schedule_node_graft_before_or_after(
4092 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
,
4095 if (!node
|| !graft
)
4097 if (check_insert(node
) < 0)
4100 if (isl_schedule_node_get_type(graft
) == isl_schedule_node_domain
)
4101 graft
= extension_from_domain(graft
, node
);
4103 if (isl_schedule_node_get_type(graft
) != isl_schedule_node_extension
)
4104 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4105 "expecting domain or extension as root of graft",
4108 return graft_extension(node
, graft
, before
);
4110 isl_schedule_node_free(node
);
4111 isl_schedule_node_free(graft
);
4115 /* Insert a node "graft" into the schedule tree of "node" such that it
4116 * is executed before the node that "node" points to.
4117 * The root of "graft" may be either a domain or an extension node.
4118 * In the latter case, the domain of the extension needs to correspond
4119 * to the outer band nodes of "node".
4120 * The elements of the domain or the range of the extension may not
4121 * intersect with the domain elements that reach "node".
4122 * The schedule tree of "graft" may not be anchored.
4124 * Return a pointer to the same node in the modified tree that
4125 * "node" pointed to in the original tree.
4127 __isl_give isl_schedule_node
*isl_schedule_node_graft_before(
4128 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
)
4130 return isl_schedule_node_graft_before_or_after(node
, graft
, 1);
4133 /* Insert a node "graft" into the schedule tree of "node" such that it
4134 * is executed after the node that "node" points to.
4135 * The root of "graft" may be either a domain or an extension node.
4136 * In the latter case, the domain of the extension needs to correspond
4137 * to the outer band nodes of "node".
4138 * The elements of the domain or the range of the extension may not
4139 * intersect with the domain elements that reach "node".
4140 * The schedule tree of "graft" may not be anchored.
4142 * Return a pointer to the same node in the modified tree that
4143 * "node" pointed to in the original tree.
4145 __isl_give isl_schedule_node
*isl_schedule_node_graft_after(
4146 __isl_take isl_schedule_node
*node
,
4147 __isl_take isl_schedule_node
*graft
)
4149 return isl_schedule_node_graft_before_or_after(node
, graft
, 0);
4152 /* Split the domain elements that reach "node" into those that satisfy
4153 * "filter" and those that do not. Arrange for the first subset to be
4154 * executed after the second subset.
4155 * Return a pointer to the tree corresponding to the second subset,
4156 * except when this subset is empty in which case the original pointer
4158 * If both subsets are non-empty, then a sequence node is introduced
4159 * to impose the order. If the grandparent of the original node was
4160 * itself a sequence, then the original child is replaced by two children
4161 * in this sequence instead.
4162 * The children in the sequence are copies of the original subtree,
4163 * simplified with respect to their filters.
4165 __isl_give isl_schedule_node
*isl_schedule_node_order_after(
4166 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
4168 enum isl_schedule_node_type ancestors
[] =
4169 { isl_schedule_node_filter
, isl_schedule_node_sequence
};
4170 isl_union_set
*node_domain
, *node_filter
= NULL
;
4171 isl_schedule_node
*node2
;
4172 isl_schedule_tree
*tree1
, *tree2
;
4176 if (!node
|| !filter
)
4178 if (check_insert(node
) < 0)
4181 in_seq
= has_ancestors(node
, 2, ancestors
);
4185 node
= isl_schedule_node_parent(node
);
4186 node_domain
= isl_schedule_node_get_domain(node
);
4187 filter
= isl_union_set_gist(filter
, isl_union_set_copy(node_domain
));
4188 node_filter
= isl_union_set_copy(node_domain
);
4189 node_filter
= isl_union_set_subtract(node_filter
,
4190 isl_union_set_copy(filter
));
4191 node_filter
= isl_union_set_gist(node_filter
, node_domain
);
4192 empty1
= isl_union_set_is_empty(filter
);
4193 empty2
= isl_union_set_is_empty(node_filter
);
4194 if (empty1
< 0 || empty2
< 0)
4196 if (empty1
|| empty2
) {
4197 isl_union_set_free(filter
);
4198 isl_union_set_free(node_filter
);
4202 node2
= isl_schedule_node_copy(node
);
4203 node
= isl_schedule_node_gist(node
, isl_union_set_copy(node_filter
));
4204 node2
= isl_schedule_node_gist(node2
, isl_union_set_copy(filter
));
4205 tree1
= isl_schedule_node_get_tree(node
);
4206 tree2
= isl_schedule_node_get_tree(node2
);
4207 isl_schedule_node_free(node2
);
4208 tree1
= isl_schedule_tree_insert_filter(tree1
, node_filter
);
4209 tree2
= isl_schedule_tree_insert_filter(tree2
, filter
);
4210 tree1
= isl_schedule_tree_sequence_pair(tree1
, tree2
);
4212 node
= graft_or_splice(node
, tree1
, 0);
4216 isl_schedule_node_free(node
);
4217 isl_union_set_free(filter
);
4218 isl_union_set_free(node_filter
);
4222 /* Reset the user pointer on all identifiers of parameters and tuples
4223 * in the schedule node "node".
4225 __isl_give isl_schedule_node
*isl_schedule_node_reset_user(
4226 __isl_take isl_schedule_node
*node
)
4228 isl_schedule_tree
*tree
;
4230 tree
= isl_schedule_node_get_tree(node
);
4231 tree
= isl_schedule_tree_reset_user(tree
);
4232 node
= isl_schedule_node_graft_tree(node
, tree
);
4237 /* Align the parameters of the schedule node "node" to those of "space".
4239 __isl_give isl_schedule_node
*isl_schedule_node_align_params(
4240 __isl_take isl_schedule_node
*node
, __isl_take isl_space
*space
)
4242 isl_schedule_tree
*tree
;
4244 tree
= isl_schedule_node_get_tree(node
);
4245 tree
= isl_schedule_tree_align_params(tree
, space
);
4246 node
= isl_schedule_node_graft_tree(node
, tree
);
4251 /* Compute the pullback of schedule node "node"
4252 * by the function represented by "upma".
4253 * In other words, plug in "upma" in the iteration domains
4254 * of schedule node "node".
4255 * We currently do not handle expansion nodes.
4257 * Note that this is only a helper function for
4258 * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency,
4259 * this function should not be called on a single node without also
4260 * calling it on all the other nodes.
4262 __isl_give isl_schedule_node
*isl_schedule_node_pullback_union_pw_multi_aff(
4263 __isl_take isl_schedule_node
*node
,
4264 __isl_take isl_union_pw_multi_aff
*upma
)
4266 isl_schedule_tree
*tree
;
4268 tree
= isl_schedule_node_get_tree(node
);
4269 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, upma
);
4270 node
= isl_schedule_node_graft_tree(node
, tree
);
4275 /* Return the position of the subtree containing "node" among the children
4276 * of "ancestor". "node" is assumed to be a descendant of "ancestor".
4277 * In particular, both nodes should point to the same schedule tree.
4279 * Return -1 on error.
4281 int isl_schedule_node_get_ancestor_child_position(
4282 __isl_keep isl_schedule_node
*node
,
4283 __isl_keep isl_schedule_node
*ancestor
)
4286 isl_schedule_tree
*tree
;
4288 if (!node
|| !ancestor
)
4291 if (node
->schedule
!= ancestor
->schedule
)
4292 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4293 "not a descendant", return -1);
4295 n1
= isl_schedule_node_get_tree_depth(ancestor
);
4296 n2
= isl_schedule_node_get_tree_depth(node
);
4299 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4300 "not a descendant", return -1);
4301 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n1
);
4302 isl_schedule_tree_free(tree
);
4303 if (tree
!= ancestor
->tree
)
4304 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4305 "not a descendant", return -1);
4307 return node
->child_pos
[n1
];
4310 /* Given two nodes that point to the same schedule tree, return their
4311 * closest shared ancestor.
4313 * Since the two nodes point to the same schedule, they share at least
4314 * one ancestor, the root of the schedule. We move down from the root
4315 * to the first ancestor where the respective children have a different
4316 * child position. This is the requested ancestor.
4317 * If there is no ancestor where the children have a different position,
4318 * then one node is an ancestor of the other and then this node is
4319 * the requested ancestor.
4321 __isl_give isl_schedule_node
*isl_schedule_node_get_shared_ancestor(
4322 __isl_keep isl_schedule_node
*node1
,
4323 __isl_keep isl_schedule_node
*node2
)
4327 if (!node1
|| !node2
)
4329 if (node1
->schedule
!= node2
->schedule
)
4330 isl_die(isl_schedule_node_get_ctx(node1
), isl_error_invalid
,
4331 "not part of same schedule", return NULL
);
4332 n1
= isl_schedule_node_get_tree_depth(node1
);
4333 n2
= isl_schedule_node_get_tree_depth(node2
);
4335 return isl_schedule_node_get_shared_ancestor(node2
, node1
);
4337 return isl_schedule_node_copy(node1
);
4338 if (isl_schedule_node_is_equal(node1
, node2
))
4339 return isl_schedule_node_copy(node1
);
4341 for (i
= 0; i
< n1
; ++i
)
4342 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
4345 node1
= isl_schedule_node_copy(node1
);
4346 return isl_schedule_node_ancestor(node1
, n1
- i
);
4349 /* Print "node" to "p".
4351 __isl_give isl_printer
*isl_printer_print_schedule_node(
4352 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
4355 return isl_printer_free(p
);
4356 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
,
4357 isl_schedule_tree_list_n_schedule_tree(node
->ancestors
),
4361 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
4364 isl_printer
*printer
;
4369 ctx
= isl_schedule_node_get_ctx(node
);
4370 printer
= isl_printer_to_file(ctx
, stderr
);
4371 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
4372 printer
= isl_printer_print_schedule_node(printer
, node
);
4374 isl_printer_free(printer
);