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 int isl_schedule_node_is_equal(__isl_keep isl_schedule_node
*node1
,
251 __isl_keep isl_schedule_node
*node2
)
255 if (!node1
|| !node2
)
259 if (node1
->schedule
!= node2
->schedule
)
262 n1
= isl_schedule_node_get_tree_depth(node1
);
263 n2
= isl_schedule_node_get_tree_depth(node2
);
266 for (i
= 0; i
< n1
; ++i
)
267 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
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 int isl_schedule_node_has_parent(__isl_keep isl_schedule_node
*node
)
951 if (!node
->ancestors
)
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 int isl_schedule_node_has_previous_sibling(__isl_keep isl_schedule_node
*node
)
987 has_parent
= isl_schedule_node_has_parent(node
);
988 if (has_parent
< 0 || !has_parent
)
991 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
993 return node
->child_pos
[n
- 1] > 0;
996 /* Does the parent (if any) of "node" have any children with a greater child
997 * position than this one?
999 int isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node
*node
)
1003 isl_schedule_tree
*tree
;
1007 has_parent
= isl_schedule_node_has_parent(node
);
1008 if (has_parent
< 0 || !has_parent
)
1011 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1012 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
1015 n_child
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1016 isl_schedule_tree_free(tree
);
1018 return node
->child_pos
[n
- 1] + 1 < n_child
;
1021 /* Does "node" have any children?
1023 * Any node other than the leaf nodes is considered to have at least
1024 * one child, even if the corresponding isl_schedule_tree does not
1025 * have any children.
1027 int isl_schedule_node_has_children(__isl_keep isl_schedule_node
*node
)
1031 return !isl_schedule_tree_is_leaf(node
->tree
);
1034 /* Return the number of children of "node"?
1036 * Any node other than the leaf nodes is considered to have at least
1037 * one child, even if the corresponding isl_schedule_tree does not
1038 * have any children. That is, the number of children of "node" is
1039 * only zero if its tree is the explicit empty tree. Otherwise,
1040 * if the isl_schedule_tree has any children, then it is equal
1041 * to the number of children of "node". If it has zero children,
1042 * then "node" still has a leaf node as child.
1044 int isl_schedule_node_n_children(__isl_keep isl_schedule_node
*node
)
1051 if (isl_schedule_tree_is_leaf(node
->tree
))
1054 n
= isl_schedule_tree_n_children(node
->tree
);
1061 /* Move the "node" pointer to the ancestor of the given generation
1062 * of the node it currently points to, where generation 0 is the node
1063 * itself and generation 1 is its parent.
1065 __isl_give isl_schedule_node
*isl_schedule_node_ancestor(
1066 __isl_take isl_schedule_node
*node
, int generation
)
1069 isl_schedule_tree
*tree
;
1073 if (generation
== 0)
1075 n
= isl_schedule_node_get_tree_depth(node
);
1077 return isl_schedule_node_free(node
);
1078 if (generation
< 0 || generation
> n
)
1079 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1080 "generation out of bounds",
1081 return isl_schedule_node_free(node
));
1082 node
= isl_schedule_node_cow(node
);
1086 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1088 isl_schedule_tree_free(node
->tree
);
1090 node
->ancestors
= isl_schedule_tree_list_drop(node
->ancestors
,
1091 n
- generation
, generation
);
1092 if (!node
->ancestors
|| !node
->tree
)
1093 return isl_schedule_node_free(node
);
1098 /* Move the "node" pointer to the parent of the node it currently points to.
1100 __isl_give isl_schedule_node
*isl_schedule_node_parent(
1101 __isl_take isl_schedule_node
*node
)
1105 if (!isl_schedule_node_has_parent(node
))
1106 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1107 "node has no parent",
1108 return isl_schedule_node_free(node
));
1109 return isl_schedule_node_ancestor(node
, 1);
1112 /* Move the "node" pointer to the root of its schedule tree.
1114 __isl_give isl_schedule_node
*isl_schedule_node_root(
1115 __isl_take isl_schedule_node
*node
)
1121 n
= isl_schedule_node_get_tree_depth(node
);
1123 return isl_schedule_node_free(node
);
1124 return isl_schedule_node_ancestor(node
, n
);
1127 /* Move the "node" pointer to the child at position "pos" of the node
1128 * it currently points to.
1130 __isl_give isl_schedule_node
*isl_schedule_node_child(
1131 __isl_take isl_schedule_node
*node
, int pos
)
1135 isl_schedule_tree
*tree
;
1138 node
= isl_schedule_node_cow(node
);
1141 if (!isl_schedule_node_has_children(node
))
1142 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1143 "node has no children",
1144 return isl_schedule_node_free(node
));
1146 ctx
= isl_schedule_node_get_ctx(node
);
1147 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1148 child_pos
= isl_realloc_array(ctx
, node
->child_pos
, int, n
+ 1);
1150 return isl_schedule_node_free(node
);
1151 node
->child_pos
= child_pos
;
1152 node
->child_pos
[n
] = pos
;
1154 node
->ancestors
= isl_schedule_tree_list_add(node
->ancestors
,
1155 isl_schedule_tree_copy(node
->tree
));
1157 if (isl_schedule_tree_has_children(tree
))
1158 tree
= isl_schedule_tree_get_child(tree
, pos
);
1160 tree
= isl_schedule_node_get_leaf(node
);
1161 isl_schedule_tree_free(node
->tree
);
1164 if (!node
->tree
|| !node
->ancestors
)
1165 return isl_schedule_node_free(node
);
1170 /* Move the "node" pointer to the first child of the node
1171 * it currently points to.
1173 __isl_give isl_schedule_node
*isl_schedule_node_first_child(
1174 __isl_take isl_schedule_node
*node
)
1176 return isl_schedule_node_child(node
, 0);
1179 /* Move the "node" pointer to the child of this node's parent in
1180 * the previous child position.
1182 __isl_give isl_schedule_node
*isl_schedule_node_previous_sibling(
1183 __isl_take isl_schedule_node
*node
)
1186 isl_schedule_tree
*parent
, *tree
;
1188 node
= isl_schedule_node_cow(node
);
1191 if (!isl_schedule_node_has_previous_sibling(node
))
1192 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1193 "node has no previous sibling",
1194 return isl_schedule_node_free(node
));
1196 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1197 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1200 return isl_schedule_node_free(node
);
1201 node
->child_pos
[n
- 1]--;
1202 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1203 node
->child_pos
[n
- 1]);
1204 isl_schedule_tree_free(parent
);
1206 return isl_schedule_node_free(node
);
1207 isl_schedule_tree_free(node
->tree
);
1213 /* Move the "node" pointer to the child of this node's parent in
1214 * the next child position.
1216 __isl_give isl_schedule_node
*isl_schedule_node_next_sibling(
1217 __isl_take isl_schedule_node
*node
)
1220 isl_schedule_tree
*parent
, *tree
;
1222 node
= isl_schedule_node_cow(node
);
1225 if (!isl_schedule_node_has_next_sibling(node
))
1226 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1227 "node has no next sibling",
1228 return isl_schedule_node_free(node
));
1230 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1231 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1234 return isl_schedule_node_free(node
);
1235 node
->child_pos
[n
- 1]++;
1236 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1237 node
->child_pos
[n
- 1]);
1238 isl_schedule_tree_free(parent
);
1240 return isl_schedule_node_free(node
);
1241 isl_schedule_tree_free(node
->tree
);
1247 /* Return a copy to the child at position "pos" of "node".
1249 __isl_give isl_schedule_node
*isl_schedule_node_get_child(
1250 __isl_keep isl_schedule_node
*node
, int pos
)
1252 return isl_schedule_node_child(isl_schedule_node_copy(node
), pos
);
1255 /* Traverse the descendant of "node" in depth-first order, including
1256 * "node" itself. Call "enter" whenever a node is entered and "leave"
1257 * whenever a node is left. The callback "enter" is responsible
1258 * for moving to the deepest initial subtree of its argument that
1259 * should be traversed.
1261 static __isl_give isl_schedule_node
*traverse(
1262 __isl_take isl_schedule_node
*node
,
1263 __isl_give isl_schedule_node
*(*enter
)(
1264 __isl_take isl_schedule_node
*node
, void *user
),
1265 __isl_give isl_schedule_node
*(*leave
)(
1266 __isl_take isl_schedule_node
*node
, void *user
),
1274 depth
= isl_schedule_node_get_tree_depth(node
);
1276 node
= enter(node
, user
);
1277 node
= leave(node
, user
);
1278 while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
&&
1279 !isl_schedule_node_has_next_sibling(node
)) {
1280 node
= isl_schedule_node_parent(node
);
1281 node
= leave(node
, user
);
1283 if (node
&& isl_schedule_node_get_tree_depth(node
) > depth
)
1284 node
= isl_schedule_node_next_sibling(node
);
1285 } while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
);
1290 /* Internal data structure for isl_schedule_node_foreach_descendant.
1292 * "fn" is the user-specified callback function.
1293 * "user" is the user-specified argument for the callback.
1295 struct isl_schedule_node_preorder_data
{
1296 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
);
1300 /* Callback for "traverse" to enter a node and to move
1301 * to the deepest initial subtree that should be traversed
1302 * for use in a preorder visit.
1304 * If the user callback returns a negative value, then we abort
1305 * the traversal. If this callback returns zero, then we skip
1306 * the subtree rooted at the current node. Otherwise, we move
1307 * down to the first child and repeat the process until a leaf
1310 static __isl_give isl_schedule_node
*preorder_enter(
1311 __isl_take isl_schedule_node
*node
, void *user
)
1313 struct isl_schedule_node_preorder_data
*data
= user
;
1321 r
= data
->fn(node
, data
->user
);
1323 return isl_schedule_node_free(node
);
1326 } while (isl_schedule_node_has_children(node
) &&
1327 (node
= isl_schedule_node_first_child(node
)) != NULL
);
1332 /* Callback for "traverse" to leave a node
1333 * for use in a preorder visit.
1334 * Since we already visited the node when we entered it,
1335 * we do not need to do anything here.
1337 static __isl_give isl_schedule_node
*preorder_leave(
1338 __isl_take isl_schedule_node
*node
, void *user
)
1343 /* Traverse the descendants of "node" (including the node itself)
1344 * in depth first preorder.
1346 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1347 * If "fn" returns 0 on any of the nodes, then the subtree rooted
1348 * at that node is skipped.
1350 * Return 0 on success and -1 on failure.
1352 int isl_schedule_node_foreach_descendant(__isl_keep isl_schedule_node
*node
,
1353 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
), void *user
)
1355 struct isl_schedule_node_preorder_data data
= { fn
, user
};
1357 node
= isl_schedule_node_copy(node
);
1358 node
= traverse(node
, &preorder_enter
, &preorder_leave
, &data
);
1359 isl_schedule_node_free(node
);
1361 return node
? 0 : -1;
1364 /* Internal data structure for isl_schedule_node_map_descendant.
1366 * "fn" is the user-specified callback function.
1367 * "user" is the user-specified argument for the callback.
1369 struct isl_schedule_node_postorder_data
{
1370 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1375 /* Callback for "traverse" to enter a node and to move
1376 * to the deepest initial subtree that should be traversed
1377 * for use in a postorder visit.
1379 * Since we are performing a postorder visit, we only need
1380 * to move to the deepest initial leaf here.
1382 static __isl_give isl_schedule_node
*postorder_enter(
1383 __isl_take isl_schedule_node
*node
, void *user
)
1385 while (node
&& isl_schedule_node_has_children(node
))
1386 node
= isl_schedule_node_first_child(node
);
1391 /* Callback for "traverse" to leave a node
1392 * for use in a postorder visit.
1394 * Since we are performing a postorder visit, we need
1395 * to call the user callback here.
1397 static __isl_give isl_schedule_node
*postorder_leave(
1398 __isl_take isl_schedule_node
*node
, void *user
)
1400 struct isl_schedule_node_postorder_data
*data
= user
;
1402 return data
->fn(node
, data
->user
);
1405 /* Traverse the descendants of "node" (including the node itself)
1406 * in depth first postorder, allowing the user to modify the visited node.
1407 * The traversal continues from the node returned by the callback function.
1408 * It is the responsibility of the user to ensure that this does not
1409 * lead to an infinite loop. It is safest to always return a pointer
1410 * to the same position (same ancestors and child positions) as the input node.
1412 __isl_give isl_schedule_node
*isl_schedule_node_map_descendant(
1413 __isl_take isl_schedule_node
*node
,
1414 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1415 void *user
), void *user
)
1417 struct isl_schedule_node_postorder_data data
= { fn
, user
};
1419 return traverse(node
, &postorder_enter
, &postorder_leave
, &data
);
1422 /* Traverse the ancestors of "node" from the root down to and including
1423 * the parent of "node", calling "fn" on each of them.
1425 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1427 * Return 0 on success and -1 on failure.
1429 int isl_schedule_node_foreach_ancestor_top_down(
1430 __isl_keep isl_schedule_node
*node
,
1431 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
), void *user
)
1438 n
= isl_schedule_node_get_tree_depth(node
);
1439 for (i
= 0; i
< n
; ++i
) {
1440 isl_schedule_node
*ancestor
;
1443 ancestor
= isl_schedule_node_copy(node
);
1444 ancestor
= isl_schedule_node_ancestor(ancestor
, n
- i
);
1445 r
= fn(ancestor
, user
);
1446 isl_schedule_node_free(ancestor
);
1454 /* Is any node in the subtree rooted at "node" anchored?
1455 * That is, do any of these nodes reference the outer band nodes?
1457 int isl_schedule_node_is_subtree_anchored(__isl_keep isl_schedule_node
*node
)
1461 return isl_schedule_tree_is_subtree_anchored(node
->tree
);
1464 /* Return the number of members in the given band node.
1466 unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node
*node
)
1468 return node
? isl_schedule_tree_band_n_member(node
->tree
) : 0;
1471 /* Is the band member at position "pos" of the band node "node"
1472 * marked coincident?
1474 int isl_schedule_node_band_member_get_coincident(
1475 __isl_keep isl_schedule_node
*node
, int pos
)
1479 return isl_schedule_tree_band_member_get_coincident(node
->tree
, pos
);
1482 /* Mark the band member at position "pos" the band node "node"
1483 * as being coincident or not according to "coincident".
1485 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_coincident(
1486 __isl_take isl_schedule_node
*node
, int pos
, int coincident
)
1489 isl_schedule_tree
*tree
;
1493 c
= isl_schedule_node_band_member_get_coincident(node
, pos
);
1494 if (c
== coincident
)
1497 tree
= isl_schedule_tree_copy(node
->tree
);
1498 tree
= isl_schedule_tree_band_member_set_coincident(tree
, pos
,
1500 node
= isl_schedule_node_graft_tree(node
, tree
);
1505 /* Is the band node "node" marked permutable?
1507 int isl_schedule_node_band_get_permutable(__isl_keep isl_schedule_node
*node
)
1512 return isl_schedule_tree_band_get_permutable(node
->tree
);
1515 /* Mark the band node "node" permutable or not according to "permutable"?
1517 __isl_give isl_schedule_node
*isl_schedule_node_band_set_permutable(
1518 __isl_take isl_schedule_node
*node
, int permutable
)
1520 isl_schedule_tree
*tree
;
1524 if (isl_schedule_node_band_get_permutable(node
) == permutable
)
1527 tree
= isl_schedule_tree_copy(node
->tree
);
1528 tree
= isl_schedule_tree_band_set_permutable(tree
, permutable
);
1529 node
= isl_schedule_node_graft_tree(node
, tree
);
1534 /* Return the schedule space of the band node.
1536 __isl_give isl_space
*isl_schedule_node_band_get_space(
1537 __isl_keep isl_schedule_node
*node
)
1542 return isl_schedule_tree_band_get_space(node
->tree
);
1545 /* Return the schedule of the band node in isolation.
1547 __isl_give isl_multi_union_pw_aff
*isl_schedule_node_band_get_partial_schedule(
1548 __isl_keep isl_schedule_node
*node
)
1553 return isl_schedule_tree_band_get_partial_schedule(node
->tree
);
1556 /* Return the schedule of the band node in isolation in the form of
1559 * If the band does not have any members, then we construct a universe map
1560 * with the universe of the domain elements reaching the node as domain.
1561 * Otherwise, we extract an isl_multi_union_pw_aff representation and
1562 * convert that to an isl_union_map.
1564 __isl_give isl_union_map
*isl_schedule_node_band_get_partial_schedule_union_map(
1565 __isl_keep isl_schedule_node
*node
)
1567 isl_multi_union_pw_aff
*mupa
;
1572 if (isl_schedule_node_get_type(node
) != isl_schedule_node_band
)
1573 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1574 "not a band node", return NULL
);
1575 if (isl_schedule_node_band_n_member(node
) == 0) {
1576 isl_union_set
*domain
;
1578 domain
= isl_schedule_node_get_universe_domain(node
);
1579 return isl_union_map_from_domain(domain
);
1582 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
1583 return isl_union_map_from_multi_union_pw_aff(mupa
);
1586 /* Return the loop AST generation type for the band member of band node "node"
1587 * at position "pos".
1589 enum isl_ast_loop_type
isl_schedule_node_band_member_get_ast_loop_type(
1590 __isl_keep isl_schedule_node
*node
, int pos
)
1593 return isl_ast_loop_error
;
1595 return isl_schedule_tree_band_member_get_ast_loop_type(node
->tree
, pos
);
1598 /* Set the loop AST generation type for the band member of band node "node"
1599 * at position "pos" to "type".
1601 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_ast_loop_type(
1602 __isl_take isl_schedule_node
*node
, int pos
,
1603 enum isl_ast_loop_type type
)
1605 isl_schedule_tree
*tree
;
1610 tree
= isl_schedule_tree_copy(node
->tree
);
1611 tree
= isl_schedule_tree_band_member_set_ast_loop_type(tree
, pos
, type
);
1612 return isl_schedule_node_graft_tree(node
, tree
);
1615 /* Return the loop AST generation type for the band member of band node "node"
1616 * at position "pos" for the isolated part.
1618 enum isl_ast_loop_type
isl_schedule_node_band_member_get_isolate_ast_loop_type(
1619 __isl_keep isl_schedule_node
*node
, int pos
)
1622 return isl_ast_loop_error
;
1624 return isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1628 /* Set the loop AST generation type for the band member of band node "node"
1629 * at position "pos" for the isolated part to "type".
1631 __isl_give isl_schedule_node
*
1632 isl_schedule_node_band_member_set_isolate_ast_loop_type(
1633 __isl_take isl_schedule_node
*node
, int pos
,
1634 enum isl_ast_loop_type type
)
1636 isl_schedule_tree
*tree
;
1641 tree
= isl_schedule_tree_copy(node
->tree
);
1642 tree
= isl_schedule_tree_band_member_set_isolate_ast_loop_type(tree
,
1644 return isl_schedule_node_graft_tree(node
, tree
);
1647 /* Return the AST build options associated to band node "node".
1649 __isl_give isl_union_set
*isl_schedule_node_band_get_ast_build_options(
1650 __isl_keep isl_schedule_node
*node
)
1655 return isl_schedule_tree_band_get_ast_build_options(node
->tree
);
1658 /* Replace the AST build options associated to band node "node" by "options".
1660 __isl_give isl_schedule_node
*isl_schedule_node_band_set_ast_build_options(
1661 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*options
)
1663 isl_schedule_tree
*tree
;
1665 if (!node
|| !options
)
1668 tree
= isl_schedule_tree_copy(node
->tree
);
1669 tree
= isl_schedule_tree_band_set_ast_build_options(tree
, options
);
1670 return isl_schedule_node_graft_tree(node
, tree
);
1672 isl_schedule_node_free(node
);
1673 isl_union_set_free(options
);
1677 /* Make sure that that spaces of "node" and "mv" are the same.
1678 * Return -1 on error, reporting the error to the user.
1680 static int check_space_multi_val(__isl_keep isl_schedule_node
*node
,
1681 __isl_keep isl_multi_val
*mv
)
1683 isl_space
*node_space
, *mv_space
;
1686 node_space
= isl_schedule_node_band_get_space(node
);
1687 mv_space
= isl_multi_val_get_space(mv
);
1688 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1689 mv_space
, isl_dim_set
);
1690 isl_space_free(mv_space
);
1691 isl_space_free(node_space
);
1695 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1696 "spaces don't match", return -1);
1701 /* Multiply the partial schedule of the band node "node"
1702 * with the factors in "mv".
1704 __isl_give isl_schedule_node
*isl_schedule_node_band_scale(
1705 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1707 isl_schedule_tree
*tree
;
1712 if (check_space_multi_val(node
, mv
) < 0)
1714 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1718 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1719 "cannot scale band node with anchored subtree",
1722 tree
= isl_schedule_node_get_tree(node
);
1723 tree
= isl_schedule_tree_band_scale(tree
, mv
);
1724 return isl_schedule_node_graft_tree(node
, tree
);
1726 isl_multi_val_free(mv
);
1727 isl_schedule_node_free(node
);
1731 /* Divide the partial schedule of the band node "node"
1732 * by the factors in "mv".
1734 __isl_give isl_schedule_node
*isl_schedule_node_band_scale_down(
1735 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1737 isl_schedule_tree
*tree
;
1742 if (check_space_multi_val(node
, mv
) < 0)
1744 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1748 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1749 "cannot scale down band node with anchored subtree",
1752 tree
= isl_schedule_node_get_tree(node
);
1753 tree
= isl_schedule_tree_band_scale_down(tree
, mv
);
1754 return isl_schedule_node_graft_tree(node
, tree
);
1756 isl_multi_val_free(mv
);
1757 isl_schedule_node_free(node
);
1761 /* Tile "node" with tile sizes "sizes".
1763 * The current node is replaced by two nested nodes corresponding
1764 * to the tile dimensions and the point dimensions.
1766 * Return a pointer to the outer (tile) node.
1768 * If any of the descendants of "node" depend on the set of outer band nodes,
1769 * then we refuse to tile the node.
1771 * If the scale tile loops option is set, then the tile loops
1772 * are scaled by the tile sizes. If the shift point loops option is set,
1773 * then the point loops are shifted to start at zero.
1774 * In particular, these options affect the tile and point loop schedules
1777 * scale shift original tile point
1779 * 0 0 i floor(i/s) i
1780 * 1 0 i s * floor(i/s) i
1781 * 0 1 i floor(i/s) i - s * floor(i/s)
1782 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1784 __isl_give isl_schedule_node
*isl_schedule_node_band_tile(
1785 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*sizes
)
1787 isl_schedule_tree
*tree
;
1790 if (!node
|| !sizes
)
1792 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1796 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1797 "cannot tile band node with anchored subtree",
1800 if (check_space_multi_val(node
, sizes
) < 0)
1803 tree
= isl_schedule_node_get_tree(node
);
1804 tree
= isl_schedule_tree_band_tile(tree
, sizes
);
1805 return isl_schedule_node_graft_tree(node
, tree
);
1807 isl_multi_val_free(sizes
);
1808 isl_schedule_node_free(node
);
1812 /* Move the band node "node" down to all the leaves in the subtree
1814 * Return a pointer to the node in the resulting tree that is in the same
1815 * position as the node pointed to by "node" in the original tree.
1817 * If the node only has a leaf child, then nothing needs to be done.
1818 * Otherwise, the child of the node is removed and the result is
1819 * appended to all the leaves in the subtree rooted at the original child.
1820 * The original node is then replaced by the result of this operation.
1822 * If any of the nodes in the subtree rooted at "node" depend on
1823 * the set of outer band nodes then we refuse to sink the band node.
1825 __isl_give isl_schedule_node
*isl_schedule_node_band_sink(
1826 __isl_take isl_schedule_node
*node
)
1828 enum isl_schedule_node_type type
;
1829 isl_schedule_tree
*tree
, *child
;
1835 type
= isl_schedule_node_get_type(node
);
1836 if (type
!= isl_schedule_node_band
)
1837 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1838 "not a band node", isl_schedule_node_free(node
));
1839 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1841 return isl_schedule_node_free(node
);
1843 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1844 "cannot sink band node in anchored subtree",
1845 isl_schedule_node_free(node
));
1846 if (isl_schedule_tree_n_children(node
->tree
) == 0)
1849 tree
= isl_schedule_node_get_tree(node
);
1850 child
= isl_schedule_tree_get_child(tree
, 0);
1851 tree
= isl_schedule_tree_reset_children(tree
);
1852 tree
= isl_schedule_tree_append_to_leaves(child
, tree
);
1854 return isl_schedule_node_graft_tree(node
, tree
);
1857 /* Split "node" into two nested band nodes, one with the first "pos"
1858 * dimensions and one with the remaining dimensions.
1859 * The schedules of the two band nodes live in anonymous spaces.
1861 __isl_give isl_schedule_node
*isl_schedule_node_band_split(
1862 __isl_take isl_schedule_node
*node
, int pos
)
1864 isl_schedule_tree
*tree
;
1866 tree
= isl_schedule_node_get_tree(node
);
1867 tree
= isl_schedule_tree_band_split(tree
, pos
);
1868 return isl_schedule_node_graft_tree(node
, tree
);
1871 /* Return the context of the context node "node".
1873 __isl_give isl_set
*isl_schedule_node_context_get_context(
1874 __isl_keep isl_schedule_node
*node
)
1879 return isl_schedule_tree_context_get_context(node
->tree
);
1882 /* Return the domain of the domain node "node".
1884 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
1885 __isl_keep isl_schedule_node
*node
)
1890 return isl_schedule_tree_domain_get_domain(node
->tree
);
1893 /* Return the expansion map of expansion node "node".
1895 __isl_give isl_union_map
*isl_schedule_node_expansion_get_expansion(
1896 __isl_keep isl_schedule_node
*node
)
1901 return isl_schedule_tree_expansion_get_expansion(node
->tree
);
1904 /* Return the contraction of expansion node "node".
1906 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_expansion_get_contraction(
1907 __isl_keep isl_schedule_node
*node
)
1912 return isl_schedule_tree_expansion_get_contraction(node
->tree
);
1915 /* Replace the contraction and the expansion of the expansion node "node"
1916 * by "contraction" and "expansion".
1918 __isl_give isl_schedule_node
*
1919 isl_schedule_node_expansion_set_contraction_and_expansion(
1920 __isl_take isl_schedule_node
*node
,
1921 __isl_take isl_union_pw_multi_aff
*contraction
,
1922 __isl_take isl_union_map
*expansion
)
1924 isl_schedule_tree
*tree
;
1926 if (!node
|| !contraction
|| !expansion
)
1929 tree
= isl_schedule_tree_copy(node
->tree
);
1930 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
1931 contraction
, expansion
);
1932 return isl_schedule_node_graft_tree(node
, tree
);
1934 isl_schedule_node_free(node
);
1935 isl_union_pw_multi_aff_free(contraction
);
1936 isl_union_map_free(expansion
);
1940 /* Return the extension of the extension node "node".
1942 __isl_give isl_union_map
*isl_schedule_node_extension_get_extension(
1943 __isl_keep isl_schedule_node
*node
)
1948 return isl_schedule_tree_extension_get_extension(node
->tree
);
1951 /* Replace the extension of extension node "node" by "extension".
1953 __isl_give isl_schedule_node
*isl_schedule_node_extension_set_extension(
1954 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
1956 isl_schedule_tree
*tree
;
1958 if (!node
|| !extension
)
1961 tree
= isl_schedule_tree_copy(node
->tree
);
1962 tree
= isl_schedule_tree_extension_set_extension(tree
, extension
);
1963 return isl_schedule_node_graft_tree(node
, tree
);
1965 isl_schedule_node_free(node
);
1966 isl_union_map_free(extension
);
1970 /* Return the filter of the filter node "node".
1972 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
1973 __isl_keep isl_schedule_node
*node
)
1978 return isl_schedule_tree_filter_get_filter(node
->tree
);
1981 /* Replace the filter of filter node "node" by "filter".
1983 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
1984 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
1986 isl_schedule_tree
*tree
;
1988 if (!node
|| !filter
)
1991 tree
= isl_schedule_tree_copy(node
->tree
);
1992 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
1993 return isl_schedule_node_graft_tree(node
, tree
);
1995 isl_schedule_node_free(node
);
1996 isl_union_set_free(filter
);
2000 /* Return the guard of the guard node "node".
2002 __isl_give isl_set
*isl_schedule_node_guard_get_guard(
2003 __isl_keep isl_schedule_node
*node
)
2008 return isl_schedule_tree_guard_get_guard(node
->tree
);
2011 /* Return the mark identifier of the mark node "node".
2013 __isl_give isl_id
*isl_schedule_node_mark_get_id(
2014 __isl_keep isl_schedule_node
*node
)
2019 return isl_schedule_tree_mark_get_id(node
->tree
);
2022 /* Update the ancestors of "node" to point to the tree that "node"
2024 * That is, replace the child in the original parent that corresponds
2025 * to the current tree position by node->tree and continue updating
2026 * the ancestors in the same way until the root is reached.
2028 * If "fn" is not NULL, then it is called on each ancestor as we move up
2029 * the tree so that it can modify the ancestor before it is added
2030 * to the list of ancestors of the modified node.
2031 * The additional "pos" argument records the position
2032 * of the "tree" argument in the original schedule tree.
2034 * If "node" originally points to a leaf of the schedule tree, then make sure
2035 * that in the end it points to a leaf in the updated schedule tree.
2037 static __isl_give isl_schedule_node
*update_ancestors(
2038 __isl_take isl_schedule_node
*node
,
2039 __isl_give isl_schedule_tree
*(*fn
)(__isl_take isl_schedule_tree
*tree
,
2040 __isl_keep isl_schedule_node
*pos
, void *user
), void *user
)
2045 isl_schedule_tree
*tree
;
2046 isl_schedule_node
*pos
= NULL
;
2049 pos
= isl_schedule_node_copy(node
);
2051 node
= isl_schedule_node_cow(node
);
2053 return isl_schedule_node_free(pos
);
2055 ctx
= isl_schedule_node_get_ctx(node
);
2056 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
2057 tree
= isl_schedule_tree_copy(node
->tree
);
2059 for (i
= n
- 1; i
>= 0; --i
) {
2060 isl_schedule_tree
*parent
;
2062 parent
= isl_schedule_tree_list_get_schedule_tree(
2063 node
->ancestors
, i
);
2064 parent
= isl_schedule_tree_replace_child(parent
,
2065 node
->child_pos
[i
], tree
);
2067 pos
= isl_schedule_node_parent(pos
);
2068 parent
= fn(parent
, pos
, user
);
2070 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
2071 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
2077 isl_schedule_node_free(pos
);
2079 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
2080 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
2082 isl_schedule_tree_free(node
->tree
);
2083 node
->tree
= isl_schedule_node_get_leaf(node
);
2086 if (!node
->schedule
|| !node
->ancestors
)
2087 return isl_schedule_node_free(node
);
2092 /* Replace the subtree that "pos" points to by "tree", updating
2093 * the ancestors to maintain a consistent state.
2095 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
2096 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
2100 if (pos
->tree
== tree
) {
2101 isl_schedule_tree_free(tree
);
2105 pos
= isl_schedule_node_cow(pos
);
2109 isl_schedule_tree_free(pos
->tree
);
2112 return update_ancestors(pos
, NULL
, NULL
);
2114 isl_schedule_node_free(pos
);
2115 isl_schedule_tree_free(tree
);
2119 /* Make sure we can insert a node between "node" and its parent.
2120 * Return -1 on error, reporting the reason why we cannot insert a node.
2122 static int check_insert(__isl_keep isl_schedule_node
*node
)
2125 enum isl_schedule_node_type type
;
2127 has_parent
= isl_schedule_node_has_parent(node
);
2131 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2132 "cannot insert node outside of root", return -1);
2134 type
= isl_schedule_node_get_parent_type(node
);
2135 if (type
== isl_schedule_node_error
)
2137 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
2138 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2139 "cannot insert node between set or sequence node "
2140 "and its filter children", return -1);
2145 /* Insert a band node with partial schedule "mupa" between "node" and
2147 * Return a pointer to the new band node.
2149 * If any of the nodes in the subtree rooted at "node" depend on
2150 * the set of outer band nodes then we refuse to insert the band node.
2152 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
2153 __isl_take isl_schedule_node
*node
,
2154 __isl_take isl_multi_union_pw_aff
*mupa
)
2157 isl_schedule_band
*band
;
2158 isl_schedule_tree
*tree
;
2160 if (check_insert(node
) < 0)
2161 node
= isl_schedule_node_free(node
);
2162 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2166 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2167 "cannot insert band node in anchored subtree",
2170 tree
= isl_schedule_node_get_tree(node
);
2171 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
2172 tree
= isl_schedule_tree_insert_band(tree
, band
);
2173 node
= isl_schedule_node_graft_tree(node
, tree
);
2177 isl_schedule_node_free(node
);
2178 isl_multi_union_pw_aff_free(mupa
);
2182 /* Insert a context node with context "context" between "node" and its parent.
2183 * Return a pointer to the new context node.
2185 __isl_give isl_schedule_node
*isl_schedule_node_insert_context(
2186 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
2188 isl_schedule_tree
*tree
;
2190 if (check_insert(node
) < 0)
2191 node
= isl_schedule_node_free(node
);
2193 tree
= isl_schedule_node_get_tree(node
);
2194 tree
= isl_schedule_tree_insert_context(tree
, context
);
2195 node
= isl_schedule_node_graft_tree(node
, tree
);
2200 /* Insert an expansion node with the given "contraction" and "expansion"
2201 * between "node" and its parent.
2202 * Return a pointer to the new expansion node.
2204 * Typically the domain and range spaces of the expansion are different.
2205 * This means that only one of them can refer to the current domain space
2206 * in a consistent tree. It is up to the caller to ensure that the tree
2207 * returns to a consistent state.
2209 __isl_give isl_schedule_node
*isl_schedule_node_insert_expansion(
2210 __isl_take isl_schedule_node
*node
,
2211 __isl_take isl_union_pw_multi_aff
*contraction
,
2212 __isl_take isl_union_map
*expansion
)
2214 isl_schedule_tree
*tree
;
2216 if (check_insert(node
) < 0)
2217 node
= isl_schedule_node_free(node
);
2219 tree
= isl_schedule_node_get_tree(node
);
2220 tree
= isl_schedule_tree_insert_expansion(tree
, contraction
, expansion
);
2221 node
= isl_schedule_node_graft_tree(node
, tree
);
2226 /* Insert an extension node with extension "extension" between "node" and
2228 * Return a pointer to the new extension node.
2230 __isl_give isl_schedule_node
*isl_schedule_node_insert_extension(
2231 __isl_take isl_schedule_node
*node
,
2232 __isl_take isl_union_map
*extension
)
2234 isl_schedule_tree
*tree
;
2236 tree
= isl_schedule_node_get_tree(node
);
2237 tree
= isl_schedule_tree_insert_extension(tree
, extension
);
2238 node
= isl_schedule_node_graft_tree(node
, tree
);
2243 /* Insert a filter node with filter "filter" between "node" and its parent.
2244 * Return a pointer to the new filter node.
2246 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
2247 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2249 isl_schedule_tree
*tree
;
2251 if (check_insert(node
) < 0)
2252 node
= isl_schedule_node_free(node
);
2254 tree
= isl_schedule_node_get_tree(node
);
2255 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2256 node
= isl_schedule_node_graft_tree(node
, tree
);
2261 /* Insert a guard node with guard "guard" between "node" and its parent.
2262 * Return a pointer to the new guard node.
2264 __isl_give isl_schedule_node
*isl_schedule_node_insert_guard(
2265 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*guard
)
2267 isl_schedule_tree
*tree
;
2269 if (check_insert(node
) < 0)
2270 node
= isl_schedule_node_free(node
);
2272 tree
= isl_schedule_node_get_tree(node
);
2273 tree
= isl_schedule_tree_insert_guard(tree
, guard
);
2274 node
= isl_schedule_node_graft_tree(node
, tree
);
2279 /* Insert a mark node with mark identifier "mark" between "node" and
2281 * Return a pointer to the new mark node.
2283 __isl_give isl_schedule_node
*isl_schedule_node_insert_mark(
2284 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*mark
)
2286 isl_schedule_tree
*tree
;
2288 if (check_insert(node
) < 0)
2289 node
= isl_schedule_node_free(node
);
2291 tree
= isl_schedule_node_get_tree(node
);
2292 tree
= isl_schedule_tree_insert_mark(tree
, mark
);
2293 node
= isl_schedule_node_graft_tree(node
, tree
);
2298 /* Attach the current subtree of "node" to a sequence of filter tree nodes
2299 * with filters described by "filters", attach this sequence
2300 * of filter tree nodes as children to a new tree of type "type" and
2301 * replace the original subtree of "node" by this new tree.
2303 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
2304 __isl_take isl_schedule_node
*node
,
2305 enum isl_schedule_node_type type
,
2306 __isl_take isl_union_set_list
*filters
)
2310 isl_schedule_tree
*tree
;
2311 isl_schedule_tree_list
*list
;
2313 if (check_insert(node
) < 0)
2314 node
= isl_schedule_node_free(node
);
2316 if (!node
|| !filters
)
2319 ctx
= isl_schedule_node_get_ctx(node
);
2320 n
= isl_union_set_list_n_union_set(filters
);
2321 list
= isl_schedule_tree_list_alloc(ctx
, n
);
2322 for (i
= 0; i
< n
; ++i
) {
2323 isl_schedule_tree
*tree
;
2324 isl_union_set
*filter
;
2326 tree
= isl_schedule_node_get_tree(node
);
2327 filter
= isl_union_set_list_get_union_set(filters
, i
);
2328 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2329 list
= isl_schedule_tree_list_add(list
, tree
);
2331 tree
= isl_schedule_tree_from_children(type
, list
);
2332 node
= isl_schedule_node_graft_tree(node
, tree
);
2334 isl_union_set_list_free(filters
);
2337 isl_union_set_list_free(filters
);
2338 isl_schedule_node_free(node
);
2342 /* Insert a sequence node with child filters "filters" between "node" and
2343 * its parent. That is, the tree that "node" points to is attached
2344 * to each of the child nodes of the filter nodes.
2345 * Return a pointer to the new sequence node.
2347 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
2348 __isl_take isl_schedule_node
*node
,
2349 __isl_take isl_union_set_list
*filters
)
2351 return isl_schedule_node_insert_children(node
,
2352 isl_schedule_node_sequence
, filters
);
2355 /* Insert a set node with child filters "filters" between "node" and
2356 * its parent. That is, the tree that "node" points to is attached
2357 * to each of the child nodes of the filter nodes.
2358 * Return a pointer to the new set node.
2360 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
2361 __isl_take isl_schedule_node
*node
,
2362 __isl_take isl_union_set_list
*filters
)
2364 return isl_schedule_node_insert_children(node
,
2365 isl_schedule_node_set
, filters
);
2368 /* Remove "node" from its schedule tree and return a pointer
2369 * to the leaf at the same position in the updated schedule tree.
2371 * It is not allowed to remove the root of a schedule tree or
2372 * a child of a set or sequence node.
2374 __isl_give isl_schedule_node
*isl_schedule_node_cut(
2375 __isl_take isl_schedule_node
*node
)
2377 isl_schedule_tree
*leaf
;
2378 enum isl_schedule_node_type parent_type
;
2382 if (!isl_schedule_node_has_parent(node
))
2383 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2384 "cannot cut root", return isl_schedule_node_free(node
));
2386 parent_type
= isl_schedule_node_get_parent_type(node
);
2387 if (parent_type
== isl_schedule_node_set
||
2388 parent_type
== isl_schedule_node_sequence
)
2389 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2390 "cannot cut child of set or sequence",
2391 return isl_schedule_node_free(node
));
2393 leaf
= isl_schedule_node_get_leaf(node
);
2394 return isl_schedule_node_graft_tree(node
, leaf
);
2397 /* Remove a single node from the schedule tree, attaching the child
2398 * of "node" directly to its parent.
2399 * Return a pointer to this former child or to the leaf the position
2400 * of the original node if there was no child.
2401 * It is not allowed to remove the root of a schedule tree,
2402 * a set or sequence node, a child of a set or sequence node or
2403 * a band node with an anchored subtree.
2405 __isl_give isl_schedule_node
*isl_schedule_node_delete(
2406 __isl_take isl_schedule_node
*node
)
2409 isl_schedule_tree
*tree
;
2410 enum isl_schedule_node_type type
;
2415 if (isl_schedule_node_get_tree_depth(node
) == 0)
2416 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2417 "cannot delete root node",
2418 return isl_schedule_node_free(node
));
2419 n
= isl_schedule_node_n_children(node
);
2421 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2422 "can only delete node with a single child",
2423 return isl_schedule_node_free(node
));
2424 type
= isl_schedule_node_get_parent_type(node
);
2425 if (type
== isl_schedule_node_sequence
|| type
== isl_schedule_node_set
)
2426 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2427 "cannot delete child of set or sequence",
2428 return isl_schedule_node_free(node
));
2429 if (isl_schedule_node_get_type(node
) == isl_schedule_node_band
) {
2432 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2434 return isl_schedule_node_free(node
);
2436 isl_die(isl_schedule_node_get_ctx(node
),
2438 "cannot delete band node with anchored subtree",
2439 return isl_schedule_node_free(node
));
2442 tree
= isl_schedule_node_get_tree(node
);
2443 if (!tree
|| isl_schedule_tree_has_children(tree
)) {
2444 tree
= isl_schedule_tree_child(tree
, 0);
2446 isl_schedule_tree_free(tree
);
2447 tree
= isl_schedule_node_get_leaf(node
);
2449 node
= isl_schedule_node_graft_tree(node
, tree
);
2454 /* Internal data structure for the group_ancestor callback.
2456 * If "finished" is set, then we no longer need to modify
2457 * any further ancestors.
2459 * "contraction" and "expansion" represent the expansion
2460 * that reflects the grouping.
2462 * "domain" contains the domain elements that reach the position
2463 * where the grouping is performed. That is, it is the range
2464 * of the resulting expansion.
2465 * "domain_universe" is the universe of "domain".
2466 * "group" is the set of group elements, i.e., the domain
2467 * of the resulting expansion.
2468 * "group_universe" is the universe of "group".
2470 * "sched" is the schedule for the group elements, in pratice
2471 * an identity mapping on "group_universe".
2472 * "dim" is the dimension of "sched".
2474 struct isl_schedule_group_data
{
2477 isl_union_map
*expansion
;
2478 isl_union_pw_multi_aff
*contraction
;
2480 isl_union_set
*domain
;
2481 isl_union_set
*domain_universe
;
2482 isl_union_set
*group
;
2483 isl_union_set
*group_universe
;
2486 isl_multi_aff
*sched
;
2489 /* Is domain covered by data->domain within data->domain_universe?
2491 static int locally_covered_by_domain(__isl_keep isl_union_set
*domain
,
2492 struct isl_schedule_group_data
*data
)
2495 isl_union_set
*test
;
2497 test
= isl_union_set_copy(domain
);
2498 test
= isl_union_set_intersect(test
,
2499 isl_union_set_copy(data
->domain_universe
));
2500 is_subset
= isl_union_set_is_subset(test
, data
->domain
);
2501 isl_union_set_free(test
);
2506 /* Update the band tree root "tree" to refer to the group instances
2507 * in data->group rather than the original domain elements in data->domain.
2508 * "pos" is the position in the original schedule tree where the modified
2509 * "tree" will be attached.
2511 * Add the part of the identity schedule on the group instances data->sched
2512 * that corresponds to this band node to the band schedule.
2513 * If the domain elements that reach the node and that are part
2514 * of data->domain_universe are all elements of data->domain (and therefore
2515 * replaced by the group instances) then this data->domain_universe
2516 * is removed from the domain of the band schedule.
2518 static __isl_give isl_schedule_tree
*group_band(
2519 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2520 struct isl_schedule_group_data
*data
)
2522 isl_union_set
*domain
;
2524 isl_multi_union_pw_aff
*mupa
, *partial
;
2526 int depth
, n
, has_id
;
2528 domain
= isl_schedule_node_get_domain(pos
);
2529 is_covered
= locally_covered_by_domain(domain
, data
);
2530 if (is_covered
>= 0 && is_covered
) {
2531 domain
= isl_union_set_universe(domain
);
2532 domain
= isl_union_set_subtract(domain
,
2533 isl_union_set_copy(data
->domain_universe
));
2534 tree
= isl_schedule_tree_band_intersect_domain(tree
, domain
);
2536 isl_union_set_free(domain
);
2538 return isl_schedule_tree_free(tree
);
2539 depth
= isl_schedule_node_get_schedule_depth(pos
);
2540 n
= isl_schedule_tree_band_n_member(tree
);
2541 ma
= isl_multi_aff_copy(data
->sched
);
2542 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, depth
);
2543 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, n
, data
->dim
- depth
- n
);
2544 mupa
= isl_multi_union_pw_aff_from_multi_aff(ma
);
2545 partial
= isl_schedule_tree_band_get_partial_schedule(tree
);
2546 has_id
= isl_multi_union_pw_aff_has_tuple_id(partial
, isl_dim_set
);
2548 partial
= isl_multi_union_pw_aff_free(partial
);
2549 } else if (has_id
) {
2551 id
= isl_multi_union_pw_aff_get_tuple_id(partial
, isl_dim_set
);
2552 mupa
= isl_multi_union_pw_aff_set_tuple_id(mupa
,
2555 partial
= isl_multi_union_pw_aff_union_add(partial
, mupa
);
2556 tree
= isl_schedule_tree_band_set_partial_schedule(tree
, partial
);
2561 /* Drop the parameters in "uset" that are not also in "space".
2562 * "n" is the number of parameters in "space".
2564 static __isl_give isl_union_set
*union_set_drop_extra_params(
2565 __isl_take isl_union_set
*uset
, __isl_keep isl_space
*space
, int n
)
2569 uset
= isl_union_set_align_params(uset
, isl_space_copy(space
));
2570 n2
= isl_union_set_dim(uset
, isl_dim_param
);
2571 uset
= isl_union_set_project_out(uset
, isl_dim_param
, n
, n2
- n
);
2576 /* Update the context tree root "tree" to refer to the group instances
2577 * in data->group rather than the original domain elements in data->domain.
2578 * "pos" is the position in the original schedule tree where the modified
2579 * "tree" will be attached.
2581 * We do not actually need to update "tree" since a context node only
2582 * refers to the schedule space. However, we may need to update "data"
2583 * to not refer to any parameters introduced by the context node.
2585 static __isl_give isl_schedule_tree
*group_context(
2586 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2587 struct isl_schedule_group_data
*data
)
2590 isl_union_set
*domain
;
2594 if (isl_schedule_node_get_tree_depth(pos
) == 1)
2597 domain
= isl_schedule_node_get_universe_domain(pos
);
2598 space
= isl_union_set_get_space(domain
);
2599 isl_union_set_free(domain
);
2601 n1
= isl_space_dim(space
, isl_dim_param
);
2602 data
->expansion
= isl_union_map_align_params(data
->expansion
, space
);
2603 n2
= isl_union_map_dim(data
->expansion
, isl_dim_param
);
2605 if (!data
->expansion
)
2606 return isl_schedule_tree_free(tree
);
2610 involves
= isl_union_map_involves_dims(data
->expansion
,
2611 isl_dim_param
, n1
, n2
- n1
);
2613 return isl_schedule_tree_free(tree
);
2615 isl_die(isl_schedule_node_get_ctx(pos
), isl_error_invalid
,
2616 "grouping cannot only refer to global parameters",
2617 return isl_schedule_tree_free(tree
));
2619 data
->expansion
= isl_union_map_project_out(data
->expansion
,
2620 isl_dim_param
, n1
, n2
- n1
);
2621 space
= isl_union_map_get_space(data
->expansion
);
2623 data
->contraction
= isl_union_pw_multi_aff_align_params(
2624 data
->contraction
, isl_space_copy(space
));
2625 n2
= isl_union_pw_multi_aff_dim(data
->contraction
, isl_dim_param
);
2626 data
->contraction
= isl_union_pw_multi_aff_drop_dims(data
->contraction
,
2627 isl_dim_param
, n1
, n2
- n1
);
2629 data
->domain
= union_set_drop_extra_params(data
->domain
, space
, n1
);
2630 data
->domain_universe
=
2631 union_set_drop_extra_params(data
->domain_universe
, space
, n1
);
2632 data
->group
= union_set_drop_extra_params(data
->group
, space
, n1
);
2633 data
->group_universe
=
2634 union_set_drop_extra_params(data
->group_universe
, space
, n1
);
2636 data
->sched
= isl_multi_aff_align_params(data
->sched
,
2637 isl_space_copy(space
));
2638 n2
= isl_multi_aff_dim(data
->sched
, isl_dim_param
);
2639 data
->sched
= isl_multi_aff_drop_dims(data
->sched
,
2640 isl_dim_param
, n1
, n2
- n1
);
2642 isl_space_free(space
);
2647 /* Update the domain tree root "tree" to refer to the group instances
2648 * in data->group rather than the original domain elements in data->domain.
2649 * "pos" is the position in the original schedule tree where the modified
2650 * "tree" will be attached.
2652 * We first double-check that all grouped domain elements are actually
2653 * part of the root domain and then replace those elements by the group
2656 static __isl_give isl_schedule_tree
*group_domain(
2657 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2658 struct isl_schedule_group_data
*data
)
2660 isl_union_set
*domain
;
2663 domain
= isl_schedule_tree_domain_get_domain(tree
);
2664 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2665 isl_union_set_free(domain
);
2667 return isl_schedule_tree_free(tree
);
2669 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2670 "grouped domain should be part of outer domain",
2671 return isl_schedule_tree_free(tree
));
2672 domain
= isl_schedule_tree_domain_get_domain(tree
);
2673 domain
= isl_union_set_subtract(domain
,
2674 isl_union_set_copy(data
->domain
));
2675 domain
= isl_union_set_union(domain
, isl_union_set_copy(data
->group
));
2676 tree
= isl_schedule_tree_domain_set_domain(tree
, domain
);
2681 /* Update the expansion tree root "tree" to refer to the group instances
2682 * in data->group rather than the original domain elements in data->domain.
2683 * "pos" is the position in the original schedule tree where the modified
2684 * "tree" will be attached.
2686 * Let G_1 -> D_1 be the expansion of "tree" and G_2 -> D_2 the newly
2687 * introduced expansion in a descendant of "tree".
2688 * We first double-check that D_2 is a subset of D_1.
2689 * Then we remove D_2 from the range of G_1 -> D_1 and add the mapping
2690 * G_1 -> D_1 . D_2 -> G_2.
2691 * Simmilarly, we restrict the domain of the contraction to the universe
2692 * of the range of the updated expansion and add G_2 -> D_2 . D_1 -> G_1,
2693 * attempting to remove the domain constraints of this additional part.
2695 static __isl_give isl_schedule_tree
*group_expansion(
2696 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2697 struct isl_schedule_group_data
*data
)
2699 isl_union_set
*domain
;
2700 isl_union_map
*expansion
, *umap
;
2701 isl_union_pw_multi_aff
*contraction
, *upma
;
2704 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2705 domain
= isl_union_map_range(expansion
);
2706 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2707 isl_union_set_free(domain
);
2709 return isl_schedule_tree_free(tree
);
2711 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2712 "grouped domain should be part "
2713 "of outer expansion domain",
2714 return isl_schedule_tree_free(tree
));
2715 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2716 umap
= isl_union_map_from_union_pw_multi_aff(
2717 isl_union_pw_multi_aff_copy(data
->contraction
));
2718 umap
= isl_union_map_apply_range(expansion
, umap
);
2719 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2720 expansion
= isl_union_map_subtract_range(expansion
,
2721 isl_union_set_copy(data
->domain
));
2722 expansion
= isl_union_map_union(expansion
, umap
);
2723 umap
= isl_union_map_universe(isl_union_map_copy(expansion
));
2724 domain
= isl_union_map_range(umap
);
2725 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
2726 umap
= isl_union_map_from_union_pw_multi_aff(contraction
);
2727 umap
= isl_union_map_apply_range(isl_union_map_copy(data
->expansion
),
2729 upma
= isl_union_pw_multi_aff_from_union_map(umap
);
2730 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
2731 contraction
= isl_union_pw_multi_aff_intersect_domain(contraction
,
2733 domain
= isl_union_pw_multi_aff_domain(
2734 isl_union_pw_multi_aff_copy(upma
));
2735 upma
= isl_union_pw_multi_aff_gist(upma
, domain
);
2736 contraction
= isl_union_pw_multi_aff_union_add(contraction
, upma
);
2737 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
2738 contraction
, expansion
);
2743 /* Update the tree root "tree" to refer to the group instances
2744 * in data->group rather than the original domain elements in data->domain.
2745 * "pos" is the position in the original schedule tree where the modified
2746 * "tree" will be attached.
2748 * If we have come across a domain or expansion node before (data->finished
2749 * is set), then we no longer need perform any modifications.
2751 * If "tree" is a filter, then we add data->group_universe to the filter.
2752 * We also remove data->domain_universe from the filter if all the domain
2753 * elements in this universe that reach the filter node are part of
2754 * the elements that are being grouped by data->expansion.
2755 * If "tree" is a band, domain or expansion, then it is handled
2756 * in a separate function.
2758 static __isl_give isl_schedule_tree
*group_ancestor(
2759 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2762 struct isl_schedule_group_data
*data
= user
;
2763 isl_union_set
*domain
;
2767 return isl_schedule_tree_free(tree
);
2772 switch (isl_schedule_tree_get_type(tree
)) {
2773 case isl_schedule_node_error
:
2774 return isl_schedule_tree_free(tree
);
2775 case isl_schedule_node_extension
:
2776 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_unsupported
,
2777 "grouping not allowed in extended tree",
2778 return isl_schedule_tree_free(tree
));
2779 case isl_schedule_node_band
:
2780 tree
= group_band(tree
, pos
, data
);
2782 case isl_schedule_node_context
:
2783 tree
= group_context(tree
, pos
, data
);
2785 case isl_schedule_node_domain
:
2786 tree
= group_domain(tree
, pos
, data
);
2789 case isl_schedule_node_filter
:
2790 domain
= isl_schedule_node_get_domain(pos
);
2791 is_covered
= locally_covered_by_domain(domain
, data
);
2792 isl_union_set_free(domain
);
2794 return isl_schedule_tree_free(tree
);
2795 domain
= isl_schedule_tree_filter_get_filter(tree
);
2797 domain
= isl_union_set_subtract(domain
,
2798 isl_union_set_copy(data
->domain_universe
));
2799 domain
= isl_union_set_union(domain
,
2800 isl_union_set_copy(data
->group_universe
));
2801 tree
= isl_schedule_tree_filter_set_filter(tree
, domain
);
2803 case isl_schedule_node_expansion
:
2804 tree
= group_expansion(tree
, pos
, data
);
2807 case isl_schedule_node_leaf
:
2808 case isl_schedule_node_guard
:
2809 case isl_schedule_node_mark
:
2810 case isl_schedule_node_sequence
:
2811 case isl_schedule_node_set
:
2818 /* Group the domain elements that reach "node" into instances
2819 * of a single statement with identifier "group_id".
2820 * In particular, group the domain elements according to their
2823 * That is, introduce an expansion node with as contraction
2824 * the prefix schedule (with the target space replaced by "group_id")
2825 * and as expansion the inverse of this contraction (with its range
2826 * intersected with the domain elements that reach "node").
2827 * The outer nodes are then modified to refer to the group instances
2828 * instead of the original domain elements.
2830 * No instance of "group_id" is allowed to reach "node" prior
2832 * No ancestor of "node" is allowed to be an extension node.
2834 * Return a pointer to original node in tree, i.e., the child
2835 * of the newly introduced expansion node.
2837 __isl_give isl_schedule_node
*isl_schedule_node_group(
2838 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*group_id
)
2840 struct isl_schedule_group_data data
= { 0 };
2842 isl_union_set
*domain
;
2843 isl_union_pw_multi_aff
*contraction
;
2844 isl_union_map
*expansion
;
2847 if (!node
|| !group_id
)
2849 if (check_insert(node
) < 0)
2852 domain
= isl_schedule_node_get_domain(node
);
2853 data
.domain
= isl_union_set_copy(domain
);
2854 data
.domain_universe
= isl_union_set_copy(domain
);
2855 data
.domain_universe
= isl_union_set_universe(data
.domain_universe
);
2857 data
.dim
= isl_schedule_node_get_schedule_depth(node
);
2858 if (data
.dim
== 0) {
2861 isl_union_set
*group
;
2862 isl_union_map
*univ
;
2864 ctx
= isl_schedule_node_get_ctx(node
);
2865 space
= isl_space_set_alloc(ctx
, 0, 0);
2866 space
= isl_space_set_tuple_id(space
, isl_dim_set
, group_id
);
2867 set
= isl_set_universe(isl_space_copy(space
));
2868 group
= isl_union_set_from_set(set
);
2869 expansion
= isl_union_map_from_domain_and_range(domain
, group
);
2870 univ
= isl_union_map_universe(isl_union_map_copy(expansion
));
2871 contraction
= isl_union_pw_multi_aff_from_union_map(univ
);
2872 expansion
= isl_union_map_reverse(expansion
);
2874 isl_multi_union_pw_aff
*prefix
;
2875 isl_union_set
*univ
;
2878 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node
);
2879 prefix
= isl_multi_union_pw_aff_set_tuple_id(prefix
,
2880 isl_dim_set
, group_id
);
2881 space
= isl_multi_union_pw_aff_get_space(prefix
);
2882 contraction
= isl_union_pw_multi_aff_from_multi_union_pw_aff(
2884 univ
= isl_union_set_universe(isl_union_set_copy(domain
));
2886 isl_union_pw_multi_aff_intersect_domain(contraction
, univ
);
2887 expansion
= isl_union_map_from_union_pw_multi_aff(
2888 isl_union_pw_multi_aff_copy(contraction
));
2889 expansion
= isl_union_map_reverse(expansion
);
2890 expansion
= isl_union_map_intersect_range(expansion
, domain
);
2892 space
= isl_space_map_from_set(space
);
2893 data
.sched
= isl_multi_aff_identity(space
);
2894 data
.group
= isl_union_map_domain(isl_union_map_copy(expansion
));
2895 data
.group
= isl_union_set_coalesce(data
.group
);
2896 data
.group_universe
= isl_union_set_copy(data
.group
);
2897 data
.group_universe
= isl_union_set_universe(data
.group_universe
);
2898 data
.expansion
= isl_union_map_copy(expansion
);
2899 data
.contraction
= isl_union_pw_multi_aff_copy(contraction
);
2900 node
= isl_schedule_node_insert_expansion(node
, contraction
, expansion
);
2902 disjoint
= isl_union_set_is_disjoint(data
.domain_universe
,
2903 data
.group_universe
);
2905 node
= update_ancestors(node
, &group_ancestor
, &data
);
2907 isl_union_set_free(data
.domain
);
2908 isl_union_set_free(data
.domain_universe
);
2909 isl_union_set_free(data
.group
);
2910 isl_union_set_free(data
.group_universe
);
2911 isl_multi_aff_free(data
.sched
);
2912 isl_union_map_free(data
.expansion
);
2913 isl_union_pw_multi_aff_free(data
.contraction
);
2915 node
= isl_schedule_node_child(node
, 0);
2917 if (!node
|| disjoint
< 0)
2918 return isl_schedule_node_free(node
);
2920 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2921 "group instances already reach node",
2922 isl_schedule_node_free(node
));
2926 isl_schedule_node_free(node
);
2927 isl_id_free(group_id
);
2931 /* Compute the gist of the given band node with respect to "context".
2933 __isl_give isl_schedule_node
*isl_schedule_node_band_gist(
2934 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
2936 isl_schedule_tree
*tree
;
2938 tree
= isl_schedule_node_get_tree(node
);
2939 tree
= isl_schedule_tree_band_gist(tree
, context
);
2940 return isl_schedule_node_graft_tree(node
, tree
);
2943 /* Internal data structure for isl_schedule_node_gist.
2944 * "n_expansion" is the number of outer expansion nodes
2945 * with respect to the current position
2946 * "filters" contains an element for each outer filter, expansion or
2947 * extension node with respect to the current position, each representing
2948 * the intersection of the previous element and the filter on the filter node
2949 * or the expansion/extension of the previous element.
2950 * The first element in the original context passed to isl_schedule_node_gist.
2952 struct isl_node_gist_data
{
2954 isl_union_set_list
*filters
;
2957 /* Enter the expansion node "node" during a isl_schedule_node_gist traversal.
2959 * In particular, add an extra element to data->filters containing
2960 * the expansion of the previous element and replace the expansion
2961 * and contraction on "node" by the gist with respect to these filters.
2962 * Also keep track of the fact that we have entered another expansion.
2964 static __isl_give isl_schedule_node
*gist_enter_expansion(
2965 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
2968 isl_union_set
*inner
;
2969 isl_union_map
*expansion
;
2970 isl_union_pw_multi_aff
*contraction
;
2972 data
->n_expansion
++;
2974 n
= isl_union_set_list_n_union_set(data
->filters
);
2975 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
2976 expansion
= isl_schedule_node_expansion_get_expansion(node
);
2977 inner
= isl_union_set_apply(inner
, expansion
);
2979 contraction
= isl_schedule_node_expansion_get_contraction(node
);
2980 contraction
= isl_union_pw_multi_aff_gist(contraction
,
2981 isl_union_set_copy(inner
));
2983 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
2985 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
2986 expansion
= isl_schedule_node_expansion_get_expansion(node
);
2987 expansion
= isl_union_map_gist_domain(expansion
, inner
);
2988 node
= isl_schedule_node_expansion_set_contraction_and_expansion(node
,
2989 contraction
, expansion
);
2994 /* Enter the extension node "node" during a isl_schedule_node_gist traversal.
2996 * In particular, add an extra element to data->filters containing
2997 * the union of the previous element with the additional domain elements
2998 * introduced by the extension.
3000 static __isl_give isl_schedule_node
*gist_enter_extension(
3001 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3004 isl_union_set
*inner
, *extra
;
3005 isl_union_map
*extension
;
3007 n
= isl_union_set_list_n_union_set(data
->filters
);
3008 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3009 extension
= isl_schedule_node_extension_get_extension(node
);
3010 extra
= isl_union_map_range(extension
);
3011 inner
= isl_union_set_union(inner
, extra
);
3013 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
3018 /* Can we finish gisting at this node?
3019 * That is, is the filter on the current filter node a subset of
3020 * the original context passed to isl_schedule_node_gist?
3021 * If we have gone through any expansions, then we cannot perform
3022 * this test since the current domain elements are incomparable
3023 * to the domain elements in the original context.
3025 static int gist_done(__isl_keep isl_schedule_node
*node
,
3026 struct isl_node_gist_data
*data
)
3028 isl_union_set
*filter
, *outer
;
3031 if (data
->n_expansion
!= 0)
3034 filter
= isl_schedule_node_filter_get_filter(node
);
3035 outer
= isl_union_set_list_get_union_set(data
->filters
, 0);
3036 subset
= isl_union_set_is_subset(filter
, outer
);
3037 isl_union_set_free(outer
);
3038 isl_union_set_free(filter
);
3043 /* Callback for "traverse" to enter a node and to move
3044 * to the deepest initial subtree that should be traversed
3045 * by isl_schedule_node_gist.
3047 * The "filters" list is extended by one element each time
3048 * we come across a filter node by the result of intersecting
3049 * the last element in the list with the filter on the filter node.
3051 * If the filter on the current filter node is a subset of
3052 * the original context passed to isl_schedule_node_gist,
3053 * then there is no need to go into its subtree since it cannot
3054 * be further simplified by the context. The "filters" list is
3055 * still extended for consistency, but the actual value of the
3056 * added element is immaterial since it will not be used.
3058 * Otherwise, the filter on the current filter node is replaced by
3059 * the gist of the original filter with respect to the intersection
3060 * of the original context with the intermediate filters.
3062 * If the new element in the "filters" list is empty, then no elements
3063 * can reach the descendants of the current filter node. The subtree
3064 * underneath the filter node is therefore removed.
3066 * Each expansion node we come across is handled by
3067 * gist_enter_expansion.
3069 * Each extension node we come across is handled by
3070 * gist_enter_extension.
3072 static __isl_give isl_schedule_node
*gist_enter(
3073 __isl_take isl_schedule_node
*node
, void *user
)
3075 struct isl_node_gist_data
*data
= user
;
3078 isl_union_set
*filter
, *inner
;
3082 switch (isl_schedule_node_get_type(node
)) {
3083 case isl_schedule_node_error
:
3084 return isl_schedule_node_free(node
);
3085 case isl_schedule_node_expansion
:
3086 node
= gist_enter_expansion(node
, data
);
3088 case isl_schedule_node_extension
:
3089 node
= gist_enter_extension(node
, data
);
3091 case isl_schedule_node_band
:
3092 case isl_schedule_node_context
:
3093 case isl_schedule_node_domain
:
3094 case isl_schedule_node_guard
:
3095 case isl_schedule_node_leaf
:
3096 case isl_schedule_node_mark
:
3097 case isl_schedule_node_sequence
:
3098 case isl_schedule_node_set
:
3100 case isl_schedule_node_filter
:
3103 done
= gist_done(node
, data
);
3104 filter
= isl_schedule_node_filter_get_filter(node
);
3105 if (done
< 0 || done
) {
3106 data
->filters
= isl_union_set_list_add(data
->filters
,
3109 return isl_schedule_node_free(node
);
3112 n
= isl_union_set_list_n_union_set(data
->filters
);
3113 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3114 filter
= isl_union_set_gist(filter
, isl_union_set_copy(inner
));
3115 node
= isl_schedule_node_filter_set_filter(node
,
3116 isl_union_set_copy(filter
));
3117 filter
= isl_union_set_intersect(filter
, inner
);
3118 empty
= isl_union_set_is_empty(filter
);
3119 data
->filters
= isl_union_set_list_add(data
->filters
, filter
);
3121 return isl_schedule_node_free(node
);
3124 node
= isl_schedule_node_child(node
, 0);
3125 node
= isl_schedule_node_cut(node
);
3126 node
= isl_schedule_node_parent(node
);
3128 } while (isl_schedule_node_has_children(node
) &&
3129 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3134 /* Callback for "traverse" to leave a node for isl_schedule_node_gist.
3136 * In particular, if the current node is a filter node, then we remove
3137 * the element on the "filters" list that was added when we entered
3138 * the node. There is no need to compute any gist here, since we
3139 * already did that when we entered the node.
3141 * If the current node is an expansion, then we decrement
3142 * the number of outer expansions and remove the element
3143 * in data->filters that was added by gist_enter_expansion.
3145 * If the current node is an extension, then remove the element
3146 * in data->filters that was added by gist_enter_extension.
3148 * If the current node is a band node, then we compute the gist of
3149 * the band node with respect to the intersection of the original context
3150 * and the intermediate filters.
3152 * If the current node is a sequence or set node, then some of
3153 * the filter children may have become empty and so they are removed.
3154 * If only one child is left, then the set or sequence node along with
3155 * the single remaining child filter is removed. The filter can be
3156 * removed because the filters on a sequence or set node are supposed
3157 * to partition the incoming domain instances.
3158 * In principle, it should then be impossible for there to be zero
3159 * remaining children, but should this happen, we replace the entire
3160 * subtree with an empty filter.
3162 static __isl_give isl_schedule_node
*gist_leave(
3163 __isl_take isl_schedule_node
*node
, void *user
)
3165 struct isl_node_gist_data
*data
= user
;
3166 isl_schedule_tree
*tree
;
3168 isl_union_set
*filter
;
3170 switch (isl_schedule_node_get_type(node
)) {
3171 case isl_schedule_node_error
:
3172 return isl_schedule_node_free(node
);
3173 case isl_schedule_node_expansion
:
3174 data
->n_expansion
--;
3175 case isl_schedule_node_extension
:
3176 case isl_schedule_node_filter
:
3177 n
= isl_union_set_list_n_union_set(data
->filters
);
3178 data
->filters
= isl_union_set_list_drop(data
->filters
,
3181 case isl_schedule_node_band
:
3182 n
= isl_union_set_list_n_union_set(data
->filters
);
3183 filter
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3184 node
= isl_schedule_node_band_gist(node
, filter
);
3186 case isl_schedule_node_set
:
3187 case isl_schedule_node_sequence
:
3188 tree
= isl_schedule_node_get_tree(node
);
3189 n
= isl_schedule_tree_n_children(tree
);
3190 for (i
= n
- 1; i
>= 0; --i
) {
3191 isl_schedule_tree
*child
;
3192 isl_union_set
*filter
;
3195 child
= isl_schedule_tree_get_child(tree
, i
);
3196 filter
= isl_schedule_tree_filter_get_filter(child
);
3197 empty
= isl_union_set_is_empty(filter
);
3198 isl_union_set_free(filter
);
3199 isl_schedule_tree_free(child
);
3201 tree
= isl_schedule_tree_free(tree
);
3203 tree
= isl_schedule_tree_drop_child(tree
, i
);
3205 n
= isl_schedule_tree_n_children(tree
);
3206 node
= isl_schedule_node_graft_tree(node
, tree
);
3208 node
= isl_schedule_node_delete(node
);
3209 node
= isl_schedule_node_delete(node
);
3210 } else if (n
== 0) {
3214 isl_union_set_list_get_union_set(data
->filters
, 0);
3215 space
= isl_union_set_get_space(filter
);
3216 isl_union_set_free(filter
);
3217 filter
= isl_union_set_empty(space
);
3218 node
= isl_schedule_node_cut(node
);
3219 node
= isl_schedule_node_insert_filter(node
, filter
);
3222 case isl_schedule_node_context
:
3223 case isl_schedule_node_domain
:
3224 case isl_schedule_node_guard
:
3225 case isl_schedule_node_leaf
:
3226 case isl_schedule_node_mark
:
3233 /* Compute the gist of the subtree at "node" with respect to
3234 * the reaching domain elements in "context".
3235 * In particular, compute the gist of all band and filter nodes
3236 * in the subtree with respect to "context". Children of set or sequence
3237 * nodes that end up with an empty filter are removed completely.
3239 * We keep track of the intersection of "context" with all outer filters
3240 * of the current node within the subtree in the final element of "filters".
3241 * Initially, this list contains the single element "context" and it is
3242 * extended or shortened each time we enter or leave a filter node.
3244 __isl_give isl_schedule_node
*isl_schedule_node_gist(
3245 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3247 struct isl_node_gist_data data
;
3249 data
.n_expansion
= 0;
3250 data
.filters
= isl_union_set_list_from_union_set(context
);
3251 node
= traverse(node
, &gist_enter
, &gist_leave
, &data
);
3252 isl_union_set_list_free(data
.filters
);
3256 /* Intersect the domain of domain node "node" with "domain".
3258 * If the domain of "node" is already a subset of "domain",
3259 * then nothing needs to be changed.
3261 * Otherwise, we replace the domain of the domain node by the intersection
3262 * and simplify the subtree rooted at "node" with respect to this intersection.
3264 __isl_give isl_schedule_node
*isl_schedule_node_domain_intersect_domain(
3265 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
)
3267 isl_schedule_tree
*tree
;
3268 isl_union_set
*uset
;
3271 if (!node
|| !domain
)
3274 uset
= isl_schedule_tree_domain_get_domain(node
->tree
);
3275 is_subset
= isl_union_set_is_subset(uset
, domain
);
3276 isl_union_set_free(uset
);
3280 isl_union_set_free(domain
);
3284 tree
= isl_schedule_tree_copy(node
->tree
);
3285 uset
= isl_schedule_tree_domain_get_domain(tree
);
3286 uset
= isl_union_set_intersect(uset
, domain
);
3287 tree
= isl_schedule_tree_domain_set_domain(tree
,
3288 isl_union_set_copy(uset
));
3289 node
= isl_schedule_node_graft_tree(node
, tree
);
3291 node
= isl_schedule_node_child(node
, 0);
3292 node
= isl_schedule_node_gist(node
, uset
);
3293 node
= isl_schedule_node_parent(node
);
3297 isl_schedule_node_free(node
);
3298 isl_union_set_free(domain
);
3302 /* Internal data structure for isl_schedule_node_get_subtree_expansion.
3303 * "expansions" contains a list of accumulated expansions
3304 * for each outer expansion, set or sequence node. The first element
3305 * in the list is an identity mapping on the reaching domain elements.
3306 * "res" collects the results.
3308 struct isl_subtree_expansion_data
{
3309 isl_union_map_list
*expansions
;
3313 /* Callback for "traverse" to enter a node and to move
3314 * to the deepest initial subtree that should be traversed
3315 * by isl_schedule_node_get_subtree_expansion.
3317 * Whenever we come across an expansion node, the last element
3318 * of data->expansions is combined with the expansion
3319 * on the expansion node.
3321 * Whenever we come across a filter node that is the child
3322 * of a set or sequence node, data->expansions is extended
3323 * with a new element that restricts the previous element
3324 * to the elements selected by the filter.
3325 * The previous element can then be reused while backtracking.
3327 static __isl_give isl_schedule_node
*subtree_expansion_enter(
3328 __isl_take isl_schedule_node
*node
, void *user
)
3330 struct isl_subtree_expansion_data
*data
= user
;
3333 enum isl_schedule_node_type type
;
3334 isl_union_set
*filter
;
3335 isl_union_map
*inner
, *expansion
;
3338 switch (isl_schedule_node_get_type(node
)) {
3339 case isl_schedule_node_error
:
3340 return isl_schedule_node_free(node
);
3341 case isl_schedule_node_filter
:
3342 type
= isl_schedule_node_get_parent_type(node
);
3343 if (type
!= isl_schedule_node_set
&&
3344 type
!= isl_schedule_node_sequence
)
3346 filter
= isl_schedule_node_filter_get_filter(node
);
3347 n
= isl_union_map_list_n_union_map(data
->expansions
);
3349 isl_union_map_list_get_union_map(data
->expansions
,
3351 inner
= isl_union_map_intersect_range(inner
, filter
);
3353 isl_union_map_list_add(data
->expansions
, inner
);
3355 case isl_schedule_node_expansion
:
3356 n
= isl_union_map_list_n_union_map(data
->expansions
);
3358 isl_schedule_node_expansion_get_expansion(node
);
3360 isl_union_map_list_get_union_map(data
->expansions
,
3362 inner
= isl_union_map_apply_range(inner
, expansion
);
3364 isl_union_map_list_set_union_map(data
->expansions
,
3367 case isl_schedule_node_band
:
3368 case isl_schedule_node_context
:
3369 case isl_schedule_node_domain
:
3370 case isl_schedule_node_extension
:
3371 case isl_schedule_node_guard
:
3372 case isl_schedule_node_leaf
:
3373 case isl_schedule_node_mark
:
3374 case isl_schedule_node_sequence
:
3375 case isl_schedule_node_set
:
3378 } while (isl_schedule_node_has_children(node
) &&
3379 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3384 /* Callback for "traverse" to leave a node for
3385 * isl_schedule_node_get_subtree_expansion.
3387 * If we come across a filter node that is the child
3388 * of a set or sequence node, then we remove the element
3389 * of data->expansions that was added in subtree_expansion_enter.
3391 * If we reach a leaf node, then the accumulated expansion is
3392 * added to data->res.
3394 static __isl_give isl_schedule_node
*subtree_expansion_leave(
3395 __isl_take isl_schedule_node
*node
, void *user
)
3397 struct isl_subtree_expansion_data
*data
= user
;
3399 isl_union_map
*inner
;
3400 enum isl_schedule_node_type type
;
3402 switch (isl_schedule_node_get_type(node
)) {
3403 case isl_schedule_node_error
:
3404 return isl_schedule_node_free(node
);
3405 case isl_schedule_node_filter
:
3406 type
= isl_schedule_node_get_parent_type(node
);
3407 if (type
!= isl_schedule_node_set
&&
3408 type
!= isl_schedule_node_sequence
)
3410 n
= isl_union_map_list_n_union_map(data
->expansions
);
3411 data
->expansions
= isl_union_map_list_drop(data
->expansions
,
3414 case isl_schedule_node_leaf
:
3415 n
= isl_union_map_list_n_union_map(data
->expansions
);
3416 inner
= isl_union_map_list_get_union_map(data
->expansions
,
3418 data
->res
= isl_union_map_union(data
->res
, inner
);
3420 case isl_schedule_node_band
:
3421 case isl_schedule_node_context
:
3422 case isl_schedule_node_domain
:
3423 case isl_schedule_node_expansion
:
3424 case isl_schedule_node_extension
:
3425 case isl_schedule_node_guard
:
3426 case isl_schedule_node_mark
:
3427 case isl_schedule_node_sequence
:
3428 case isl_schedule_node_set
:
3435 /* Return a mapping from the domain elements that reach "node"
3436 * to the corresponding domain elements in the leaves of the subtree
3437 * rooted at "node" obtained by composing the intermediate expansions.
3439 * We start out with an identity mapping between the domain elements
3440 * that reach "node" and compose it with all the expansions
3441 * on a path from "node" to a leaf while traversing the subtree.
3442 * Within the children of an a sequence or set node, the
3443 * accumulated expansion is restricted to the elements selected
3444 * by the filter child.
3446 __isl_give isl_union_map
*isl_schedule_node_get_subtree_expansion(
3447 __isl_keep isl_schedule_node
*node
)
3449 struct isl_subtree_expansion_data data
;
3451 isl_union_set
*domain
;
3452 isl_union_map
*expansion
;
3457 domain
= isl_schedule_node_get_universe_domain(node
);
3458 space
= isl_union_set_get_space(domain
);
3459 expansion
= isl_union_set_identity(domain
);
3460 data
.res
= isl_union_map_empty(space
);
3461 data
.expansions
= isl_union_map_list_from_union_map(expansion
);
3463 node
= isl_schedule_node_copy(node
);
3464 node
= traverse(node
, &subtree_expansion_enter
,
3465 &subtree_expansion_leave
, &data
);
3467 data
.res
= isl_union_map_free(data
.res
);
3468 isl_schedule_node_free(node
);
3470 isl_union_map_list_free(data
.expansions
);
3475 /* Internal data structure for isl_schedule_node_get_subtree_contraction.
3476 * "contractions" contains a list of accumulated contractions
3477 * for each outer expansion, set or sequence node. The first element
3478 * in the list is an identity mapping on the reaching domain elements.
3479 * "res" collects the results.
3481 struct isl_subtree_contraction_data
{
3482 isl_union_pw_multi_aff_list
*contractions
;
3483 isl_union_pw_multi_aff
*res
;
3486 /* Callback for "traverse" to enter a node and to move
3487 * to the deepest initial subtree that should be traversed
3488 * by isl_schedule_node_get_subtree_contraction.
3490 * Whenever we come across an expansion node, the last element
3491 * of data->contractions is combined with the contraction
3492 * on the expansion node.
3494 * Whenever we come across a filter node that is the child
3495 * of a set or sequence node, data->contractions is extended
3496 * with a new element that restricts the previous element
3497 * to the elements selected by the filter.
3498 * The previous element can then be reused while backtracking.
3500 static __isl_give isl_schedule_node
*subtree_contraction_enter(
3501 __isl_take isl_schedule_node
*node
, void *user
)
3503 struct isl_subtree_contraction_data
*data
= user
;
3506 enum isl_schedule_node_type type
;
3507 isl_union_set
*filter
;
3508 isl_union_pw_multi_aff
*inner
, *contraction
;
3511 switch (isl_schedule_node_get_type(node
)) {
3512 case isl_schedule_node_error
:
3513 return isl_schedule_node_free(node
);
3514 case isl_schedule_node_filter
:
3515 type
= isl_schedule_node_get_parent_type(node
);
3516 if (type
!= isl_schedule_node_set
&&
3517 type
!= isl_schedule_node_sequence
)
3519 filter
= isl_schedule_node_filter_get_filter(node
);
3520 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3521 data
->contractions
);
3523 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3524 data
->contractions
, n
- 1);
3525 inner
= isl_union_pw_multi_aff_intersect_domain(inner
,
3527 data
->contractions
=
3528 isl_union_pw_multi_aff_list_add(data
->contractions
,
3531 case isl_schedule_node_expansion
:
3532 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3533 data
->contractions
);
3535 isl_schedule_node_expansion_get_contraction(node
);
3537 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3538 data
->contractions
, n
- 1);
3540 isl_union_pw_multi_aff_pullback_union_pw_multi_aff(
3541 inner
, contraction
);
3542 data
->contractions
=
3543 isl_union_pw_multi_aff_list_set_union_pw_multi_aff(
3544 data
->contractions
, n
- 1, inner
);
3546 case isl_schedule_node_band
:
3547 case isl_schedule_node_context
:
3548 case isl_schedule_node_domain
:
3549 case isl_schedule_node_extension
:
3550 case isl_schedule_node_guard
:
3551 case isl_schedule_node_leaf
:
3552 case isl_schedule_node_mark
:
3553 case isl_schedule_node_sequence
:
3554 case isl_schedule_node_set
:
3557 } while (isl_schedule_node_has_children(node
) &&
3558 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3563 /* Callback for "traverse" to leave a node for
3564 * isl_schedule_node_get_subtree_contraction.
3566 * If we come across a filter node that is the child
3567 * of a set or sequence node, then we remove the element
3568 * of data->contractions that was added in subtree_contraction_enter.
3570 * If we reach a leaf node, then the accumulated contraction is
3571 * added to data->res.
3573 static __isl_give isl_schedule_node
*subtree_contraction_leave(
3574 __isl_take isl_schedule_node
*node
, void *user
)
3576 struct isl_subtree_contraction_data
*data
= user
;
3578 isl_union_pw_multi_aff
*inner
;
3579 enum isl_schedule_node_type type
;
3581 switch (isl_schedule_node_get_type(node
)) {
3582 case isl_schedule_node_error
:
3583 return isl_schedule_node_free(node
);
3584 case isl_schedule_node_filter
:
3585 type
= isl_schedule_node_get_parent_type(node
);
3586 if (type
!= isl_schedule_node_set
&&
3587 type
!= isl_schedule_node_sequence
)
3589 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3590 data
->contractions
);
3591 data
->contractions
=
3592 isl_union_pw_multi_aff_list_drop(data
->contractions
,
3595 case isl_schedule_node_leaf
:
3596 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3597 data
->contractions
);
3598 inner
= isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3599 data
->contractions
, n
- 1);
3600 data
->res
= isl_union_pw_multi_aff_union_add(data
->res
, inner
);
3602 case isl_schedule_node_band
:
3603 case isl_schedule_node_context
:
3604 case isl_schedule_node_domain
:
3605 case isl_schedule_node_expansion
:
3606 case isl_schedule_node_extension
:
3607 case isl_schedule_node_guard
:
3608 case isl_schedule_node_mark
:
3609 case isl_schedule_node_sequence
:
3610 case isl_schedule_node_set
:
3617 /* Return a mapping from the domain elements in the leaves of the subtree
3618 * rooted at "node" to the corresponding domain elements that reach "node"
3619 * obtained by composing the intermediate contractions.
3621 * We start out with an identity mapping between the domain elements
3622 * that reach "node" and compose it with all the contractions
3623 * on a path from "node" to a leaf while traversing the subtree.
3624 * Within the children of an a sequence or set node, the
3625 * accumulated contraction is restricted to the elements selected
3626 * by the filter child.
3628 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_get_subtree_contraction(
3629 __isl_keep isl_schedule_node
*node
)
3631 struct isl_subtree_contraction_data data
;
3633 isl_union_set
*domain
;
3634 isl_union_pw_multi_aff
*contraction
;
3639 domain
= isl_schedule_node_get_universe_domain(node
);
3640 space
= isl_union_set_get_space(domain
);
3641 contraction
= isl_union_set_identity_union_pw_multi_aff(domain
);
3642 data
.res
= isl_union_pw_multi_aff_empty(space
);
3644 isl_union_pw_multi_aff_list_from_union_pw_multi_aff(contraction
);
3646 node
= isl_schedule_node_copy(node
);
3647 node
= traverse(node
, &subtree_contraction_enter
,
3648 &subtree_contraction_leave
, &data
);
3650 data
.res
= isl_union_pw_multi_aff_free(data
.res
);
3651 isl_schedule_node_free(node
);
3653 isl_union_pw_multi_aff_list_free(data
.contractions
);
3658 /* Reset the user pointer on all identifiers of parameters and tuples
3659 * in the schedule node "node".
3661 __isl_give isl_schedule_node
*isl_schedule_node_reset_user(
3662 __isl_take isl_schedule_node
*node
)
3664 isl_schedule_tree
*tree
;
3666 tree
= isl_schedule_node_get_tree(node
);
3667 tree
= isl_schedule_tree_reset_user(tree
);
3668 node
= isl_schedule_node_graft_tree(node
, tree
);
3673 /* Align the parameters of the schedule node "node" to those of "space".
3675 __isl_give isl_schedule_node
*isl_schedule_node_align_params(
3676 __isl_take isl_schedule_node
*node
, __isl_take isl_space
*space
)
3678 isl_schedule_tree
*tree
;
3680 tree
= isl_schedule_node_get_tree(node
);
3681 tree
= isl_schedule_tree_align_params(tree
, space
);
3682 node
= isl_schedule_node_graft_tree(node
, tree
);
3687 /* Compute the pullback of schedule node "node"
3688 * by the function represented by "upma".
3689 * In other words, plug in "upma" in the iteration domains
3690 * of schedule node "node".
3691 * We currently do not handle expansion nodes.
3693 * Note that this is only a helper function for
3694 * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency,
3695 * this function should not be called on a single node without also
3696 * calling it on all the other nodes.
3698 __isl_give isl_schedule_node
*isl_schedule_node_pullback_union_pw_multi_aff(
3699 __isl_take isl_schedule_node
*node
,
3700 __isl_take isl_union_pw_multi_aff
*upma
)
3702 isl_schedule_tree
*tree
;
3704 tree
= isl_schedule_node_get_tree(node
);
3705 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, upma
);
3706 node
= isl_schedule_node_graft_tree(node
, tree
);
3711 /* Return the position of the subtree containing "node" among the children
3712 * of "ancestor". "node" is assumed to be a descendant of "ancestor".
3713 * In particular, both nodes should point to the same schedule tree.
3715 * Return -1 on error.
3717 int isl_schedule_node_get_ancestor_child_position(
3718 __isl_keep isl_schedule_node
*node
,
3719 __isl_keep isl_schedule_node
*ancestor
)
3722 isl_schedule_tree
*tree
;
3724 if (!node
|| !ancestor
)
3727 if (node
->schedule
!= ancestor
->schedule
)
3728 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3729 "not a descendant", return -1);
3731 n1
= isl_schedule_node_get_tree_depth(ancestor
);
3732 n2
= isl_schedule_node_get_tree_depth(node
);
3735 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3736 "not a descendant", return -1);
3737 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n1
);
3738 isl_schedule_tree_free(tree
);
3739 if (tree
!= ancestor
->tree
)
3740 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3741 "not a descendant", return -1);
3743 return node
->child_pos
[n1
];
3746 /* Given two nodes that point to the same schedule tree, return their
3747 * closest shared ancestor.
3749 * Since the two nodes point to the same schedule, they share at least
3750 * one ancestor, the root of the schedule. We move down from the root
3751 * to the first ancestor where the respective children have a different
3752 * child position. This is the requested ancestor.
3753 * If there is no ancestor where the children have a different position,
3754 * then one node is an ancestor of the other and then this node is
3755 * the requested ancestor.
3757 __isl_give isl_schedule_node
*isl_schedule_node_get_shared_ancestor(
3758 __isl_keep isl_schedule_node
*node1
,
3759 __isl_keep isl_schedule_node
*node2
)
3763 if (!node1
|| !node2
)
3765 if (node1
->schedule
!= node2
->schedule
)
3766 isl_die(isl_schedule_node_get_ctx(node1
), isl_error_invalid
,
3767 "not part of same schedule", return NULL
);
3768 n1
= isl_schedule_node_get_tree_depth(node1
);
3769 n2
= isl_schedule_node_get_tree_depth(node2
);
3771 return isl_schedule_node_get_shared_ancestor(node2
, node1
);
3773 return isl_schedule_node_copy(node1
);
3774 if (isl_schedule_node_is_equal(node1
, node2
))
3775 return isl_schedule_node_copy(node1
);
3777 for (i
= 0; i
< n1
; ++i
)
3778 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
3781 node1
= isl_schedule_node_copy(node1
);
3782 return isl_schedule_node_ancestor(node1
, n1
- i
);
3785 /* Print "node" to "p".
3787 __isl_give isl_printer
*isl_printer_print_schedule_node(
3788 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
3791 return isl_printer_free(p
);
3792 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
,
3793 isl_schedule_tree_list_n_schedule_tree(node
->ancestors
),
3797 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
3800 isl_printer
*printer
;
3805 ctx
= isl_schedule_node_get_ctx(node
);
3806 printer
= isl_printer_to_file(ctx
, stderr
);
3807 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
3808 printer
= isl_printer_print_schedule_node(printer
, node
);
3810 isl_printer_free(printer
);