2 * Copyright 2013-2014 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
9 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
10 * B.P. 105 - 78153 Le Chesnay, France
14 #include <isl_schedule_band.h>
15 #include <isl_schedule_private.h>
16 #include <isl_schedule_node_private.h>
18 /* Create a new schedule node in the given schedule, point at the given
19 * tree with given ancestors and child positions.
20 * "child_pos" may be NULL if there are no ancestors.
22 __isl_give isl_schedule_node
*isl_schedule_node_alloc(
23 __isl_take isl_schedule
*schedule
, __isl_take isl_schedule_tree
*tree
,
24 __isl_take isl_schedule_tree_list
*ancestors
, int *child_pos
)
27 isl_schedule_node
*node
;
30 if (!schedule
|| !tree
|| !ancestors
)
32 n
= isl_schedule_tree_list_n_schedule_tree(ancestors
);
33 if (n
> 0 && !child_pos
)
35 ctx
= isl_schedule_get_ctx(schedule
);
36 node
= isl_calloc_type(ctx
, isl_schedule_node
);
40 node
->schedule
= schedule
;
42 node
->ancestors
= ancestors
;
43 node
->child_pos
= isl_alloc_array(ctx
, int, n
);
44 if (n
&& !node
->child_pos
)
45 return isl_schedule_node_free(node
);
46 for (i
= 0; i
< n
; ++i
)
47 node
->child_pos
[i
] = child_pos
[i
];
51 isl_schedule_free(schedule
);
52 isl_schedule_tree_free(tree
);
53 isl_schedule_tree_list_free(ancestors
);
57 /* Return a pointer to the root of a schedule tree with as single
58 * node a domain node with the given domain.
60 __isl_give isl_schedule_node
*isl_schedule_node_from_domain(
61 __isl_take isl_union_set
*domain
)
63 isl_schedule
*schedule
;
64 isl_schedule_node
*node
;
66 schedule
= isl_schedule_from_domain(domain
);
67 node
= isl_schedule_get_root(schedule
);
68 isl_schedule_free(schedule
);
73 /* Return the isl_ctx to which "node" belongs.
75 isl_ctx
*isl_schedule_node_get_ctx(__isl_keep isl_schedule_node
*node
)
77 return node
? isl_schedule_get_ctx(node
->schedule
) : NULL
;
80 /* Return a pointer to the leaf of the schedule into which "node" points.
82 * Even though these leaves are not reference counted, we still
83 * indicate that this function does not return a copy.
85 __isl_keep isl_schedule_tree
*isl_schedule_node_peek_leaf(
86 __isl_keep isl_schedule_node
*node
)
88 return node
? isl_schedule_peek_leaf(node
->schedule
) : NULL
;
91 /* Return a pointer to the leaf of the schedule into which "node" points.
93 * Even though these leaves are not reference counted, we still
94 * return a "copy" of the leaf here such that it can still be "freed"
97 __isl_give isl_schedule_tree
*isl_schedule_node_get_leaf(
98 __isl_keep isl_schedule_node
*node
)
100 return isl_schedule_tree_copy(isl_schedule_node_peek_leaf(node
));
103 /* Return the type of the node or isl_schedule_node_error on error.
105 enum isl_schedule_node_type
isl_schedule_node_get_type(
106 __isl_keep isl_schedule_node
*node
)
108 return node
? isl_schedule_tree_get_type(node
->tree
)
109 : isl_schedule_node_error
;
112 /* Return the type of the parent of "node" or isl_schedule_node_error on error.
114 enum isl_schedule_node_type
isl_schedule_node_get_parent_type(
115 __isl_keep isl_schedule_node
*node
)
119 isl_schedule_tree
*parent
;
120 enum isl_schedule_node_type type
;
123 return isl_schedule_node_error
;
124 has_parent
= isl_schedule_node_has_parent(node
);
126 return isl_schedule_node_error
;
128 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
129 "node has no parent", return isl_schedule_node_error
);
131 pos
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) - 1;
132 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, pos
);
133 type
= isl_schedule_tree_get_type(parent
);
134 isl_schedule_tree_free(parent
);
139 /* Return a copy of the subtree that this node points to.
141 __isl_give isl_schedule_tree
*isl_schedule_node_get_tree(
142 __isl_keep isl_schedule_node
*node
)
147 return isl_schedule_tree_copy(node
->tree
);
150 /* Return a copy of the schedule into which "node" points.
152 __isl_give isl_schedule
*isl_schedule_node_get_schedule(
153 __isl_keep isl_schedule_node
*node
)
157 return isl_schedule_copy(node
->schedule
);
160 /* Return a fresh copy of "node".
162 __isl_take isl_schedule_node
*isl_schedule_node_dup(
163 __isl_keep isl_schedule_node
*node
)
168 return isl_schedule_node_alloc(isl_schedule_copy(node
->schedule
),
169 isl_schedule_tree_copy(node
->tree
),
170 isl_schedule_tree_list_copy(node
->ancestors
),
174 /* Return an isl_schedule_node that is equal to "node" and that has only
175 * a single reference.
177 __isl_give isl_schedule_node
*isl_schedule_node_cow(
178 __isl_take isl_schedule_node
*node
)
186 return isl_schedule_node_dup(node
);
189 /* Return a new reference to "node".
191 __isl_give isl_schedule_node
*isl_schedule_node_copy(
192 __isl_keep isl_schedule_node
*node
)
201 /* Free "node" and return NULL.
203 * Since the node may point to a leaf of its schedule, which
204 * point to a field inside the schedule, we need to make sure
205 * we free the tree before freeing the schedule.
207 __isl_null isl_schedule_node
*isl_schedule_node_free(
208 __isl_take isl_schedule_node
*node
)
215 isl_schedule_tree_list_free(node
->ancestors
);
216 free(node
->child_pos
);
217 isl_schedule_tree_free(node
->tree
);
218 isl_schedule_free(node
->schedule
);
224 /* Do "node1" and "node2" point to the same position in the same
227 int isl_schedule_node_is_equal(__isl_keep isl_schedule_node
*node1
,
228 __isl_keep isl_schedule_node
*node2
)
232 if (!node1
|| !node2
)
236 if (node1
->schedule
!= node2
->schedule
)
239 n1
= isl_schedule_node_get_tree_depth(node1
);
240 n2
= isl_schedule_node_get_tree_depth(node2
);
243 for (i
= 0; i
< n1
; ++i
)
244 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
250 /* Return the number of outer schedule dimensions of "node"
251 * in its schedule tree.
253 * Return -1 on error.
255 int isl_schedule_node_get_schedule_depth(__isl_keep isl_schedule_node
*node
)
263 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
264 for (i
= n
- 1; i
>= 0; --i
) {
265 isl_schedule_tree
*tree
;
267 tree
= isl_schedule_tree_list_get_schedule_tree(
271 if (tree
->type
== isl_schedule_node_band
)
272 depth
+= isl_schedule_tree_band_n_member(tree
);
273 isl_schedule_tree_free(tree
);
279 /* Internal data structure for
280 * isl_schedule_node_get_prefix_schedule_union_pw_multi_aff
282 * "initialized" is set if the filter field has been initialized.
283 * If "universe_domain" is not set, then the collected filter is intersected
284 * with the the domain of the root domain node.
285 * "universe_filter" is set if we are only collecting the universes of filters
286 * "collect_prefix" is set if we are collecting prefixes.
287 * "filter" collects all outer filters and is NULL until "initialized" is set.
288 * "prefix" collects all outer band partial schedules (if "collect_prefix"
289 * is set). If it is used, then it is initialized by the caller
290 * of collect_filter_prefix to a zero-dimensional function.
292 struct isl_schedule_node_get_filter_prefix_data
{
297 isl_union_set
*filter
;
298 isl_multi_union_pw_aff
*prefix
;
301 static int collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
302 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
);
304 /* Update the filter and prefix information in "data" based on the first "n"
305 * elements in "list" and the expansion tree root "tree".
307 * We first collect the information from the elements in "list",
308 * initializing the filter based on the domain of the expansion.
309 * Then we map the results to the expanded space and combined them
310 * with the results already in "data".
312 static int collect_filter_prefix_expansion(__isl_take isl_schedule_tree
*tree
,
313 __isl_keep isl_schedule_tree_list
*list
, int n
,
314 struct isl_schedule_node_get_filter_prefix_data
*data
)
316 struct isl_schedule_node_get_filter_prefix_data contracted
;
317 isl_union_pw_multi_aff
*c
;
318 isl_union_map
*exp
, *universe
;
319 isl_union_set
*filter
;
321 c
= isl_schedule_tree_expansion_get_contraction(tree
);
322 exp
= isl_schedule_tree_expansion_get_expansion(tree
);
324 contracted
.initialized
= 1;
325 contracted
.universe_domain
= data
->universe_domain
;
326 contracted
.universe_filter
= data
->universe_filter
;
327 contracted
.collect_prefix
= data
->collect_prefix
;
328 universe
= isl_union_map_universe(isl_union_map_copy(exp
));
329 filter
= isl_union_map_domain(universe
);
330 if (data
->collect_prefix
) {
331 isl_space
*space
= isl_union_set_get_space(filter
);
332 space
= isl_space_set_from_params(space
);
333 contracted
.prefix
= isl_multi_union_pw_aff_zero(space
);
335 contracted
.filter
= filter
;
337 if (collect_filter_prefix(list
, n
, &contracted
) < 0)
338 contracted
.filter
= isl_union_set_free(contracted
.filter
);
339 if (data
->collect_prefix
) {
340 isl_multi_union_pw_aff
*prefix
;
342 prefix
= contracted
.prefix
;
344 isl_multi_union_pw_aff_pullback_union_pw_multi_aff(prefix
,
345 isl_union_pw_multi_aff_copy(c
));
346 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(
347 prefix
, data
->prefix
);
349 filter
= contracted
.filter
;
350 if (data
->universe_domain
)
351 filter
= isl_union_set_preimage_union_pw_multi_aff(filter
,
352 isl_union_pw_multi_aff_copy(c
));
354 filter
= isl_union_set_apply(filter
, isl_union_map_copy(exp
));
355 if (!data
->initialized
)
356 data
->filter
= filter
;
358 data
->filter
= isl_union_set_intersect(filter
, data
->filter
);
359 data
->initialized
= 1;
361 isl_union_pw_multi_aff_free(c
);
362 isl_union_map_free(exp
);
363 isl_schedule_tree_free(tree
);
368 /* Update "data" based on the tree node "tree" in case "data" has
369 * not been initialized yet.
371 * Return 0 on success and -1 on error.
373 * If "tree" is a filter, then we set data->filter to this filter
375 * If "tree" is a domain, then this means we have reached the root
376 * of the schedule tree without being able to extract any information.
377 * We therefore initialize data->filter to the universe of the domain,
378 * or the domain itself if data->universe_domain is not set.
379 * If "tree" is a band with at least one member, then we set data->filter
380 * to the universe of the schedule domain and replace the zero-dimensional
381 * data->prefix by the band schedule (if data->collect_prefix is set).
383 static int collect_filter_prefix_init(__isl_keep isl_schedule_tree
*tree
,
384 struct isl_schedule_node_get_filter_prefix_data
*data
)
386 enum isl_schedule_node_type type
;
387 isl_multi_union_pw_aff
*mupa
;
388 isl_union_set
*filter
;
390 type
= isl_schedule_tree_get_type(tree
);
392 case isl_schedule_node_error
:
394 case isl_schedule_node_expansion
:
395 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
396 "should be handled by caller", return -1);
397 case isl_schedule_node_context
:
398 case isl_schedule_node_leaf
:
399 case isl_schedule_node_sequence
:
400 case isl_schedule_node_set
:
402 case isl_schedule_node_domain
:
403 filter
= isl_schedule_tree_domain_get_domain(tree
);
404 if (data
->universe_domain
)
405 filter
= isl_union_set_universe(filter
);
406 data
->filter
= filter
;
408 case isl_schedule_node_band
:
409 if (isl_schedule_tree_band_n_member(tree
) == 0)
411 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
412 if (data
->collect_prefix
) {
413 isl_multi_union_pw_aff_free(data
->prefix
);
414 mupa
= isl_multi_union_pw_aff_reset_tuple_id(mupa
,
416 data
->prefix
= isl_multi_union_pw_aff_copy(mupa
);
418 filter
= isl_multi_union_pw_aff_domain(mupa
);
419 filter
= isl_union_set_universe(filter
);
420 data
->filter
= filter
;
422 case isl_schedule_node_filter
:
423 filter
= isl_schedule_tree_filter_get_filter(tree
);
424 if (data
->universe_filter
)
425 filter
= isl_union_set_universe(filter
);
426 data
->filter
= filter
;
430 if ((data
->collect_prefix
&& !data
->prefix
) || !data
->filter
)
433 data
->initialized
= 1;
438 /* Update "data" based on the tree node "tree" in case "data" has
439 * already been initialized.
441 * Return 0 on success and -1 on error.
443 * If "tree" is a domain and data->universe_domain is not set, then
444 * intersect data->filter with the domain.
445 * If "tree" is a filter, then we intersect data->filter with this filter
447 * If "tree" is a band with at least one member and data->collect_prefix
448 * is set, then we extend data->prefix with the band schedule.
450 static int collect_filter_prefix_update(__isl_keep isl_schedule_tree
*tree
,
451 struct isl_schedule_node_get_filter_prefix_data
*data
)
453 enum isl_schedule_node_type type
;
454 isl_multi_union_pw_aff
*mupa
;
455 isl_union_set
*filter
;
457 type
= isl_schedule_tree_get_type(tree
);
459 case isl_schedule_node_error
:
461 case isl_schedule_node_expansion
:
462 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
463 "should be handled by caller", return -1);
464 case isl_schedule_node_context
:
465 case isl_schedule_node_leaf
:
466 case isl_schedule_node_sequence
:
467 case isl_schedule_node_set
:
469 case isl_schedule_node_domain
:
470 if (data
->universe_domain
)
472 filter
= isl_schedule_tree_domain_get_domain(tree
);
473 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
475 case isl_schedule_node_band
:
476 if (isl_schedule_tree_band_n_member(tree
) == 0)
478 if (!data
->collect_prefix
)
480 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
481 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(mupa
,
486 case isl_schedule_node_filter
:
487 filter
= isl_schedule_tree_filter_get_filter(tree
);
488 if (data
->universe_filter
)
489 filter
= isl_union_set_universe(filter
);
490 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
499 /* Collect filter and/or prefix information from the first "n"
500 * elements in "list" (which represent the ancestors of a node).
501 * Store the results in "data".
503 * Return 0 on success and -1 on error.
505 * We traverse the list from innermost ancestor (last element)
506 * to outermost ancestor (first element), calling collect_filter_prefix_init
507 * on each node as long as we have not been able to extract any information
508 * yet and collect_filter_prefix_update afterwards.
509 * If we come across an expansion node, then we interrupt the traversal
510 * and call collect_filter_prefix_expansion to restart the traversal
511 * over the remaining ancestors and to combine the results with those
512 * that have already been collected.
513 * On successful return, data->initialized will be set since the outermost
514 * ancestor is a domain node, which always results in an initialization.
516 static int collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
517 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
)
524 for (i
= n
- 1; i
>= 0; --i
) {
525 isl_schedule_tree
*tree
;
526 enum isl_schedule_node_type type
;
529 tree
= isl_schedule_tree_list_get_schedule_tree(list
, i
);
532 type
= isl_schedule_tree_get_type(tree
);
533 if (type
== isl_schedule_node_expansion
)
534 return collect_filter_prefix_expansion(tree
, list
, i
,
536 if (!data
->initialized
)
537 r
= collect_filter_prefix_init(tree
, data
);
539 r
= collect_filter_prefix_update(tree
, data
);
540 isl_schedule_tree_free(tree
);
548 /* Return the concatenation of the partial schedules of all outer band
549 * nodes of "node" interesected with all outer filters
550 * as an isl_multi_union_pw_aff.
552 * If "node" is pointing at the root of the schedule tree, then
553 * there are no domain elements reaching the current node, so
554 * we return an empty result.
556 * We collect all the filters and partial schedules in collect_filter_prefix
557 * and intersect the domain of the combined schedule with the combined filter.
559 __isl_give isl_multi_union_pw_aff
*
560 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(
561 __isl_keep isl_schedule_node
*node
)
565 struct isl_schedule_node_get_filter_prefix_data data
;
570 space
= isl_schedule_get_space(node
->schedule
);
571 space
= isl_space_set_from_params(space
);
572 if (node
->tree
== node
->schedule
->root
)
573 return isl_multi_union_pw_aff_zero(space
);
575 data
.initialized
= 0;
576 data
.universe_domain
= 1;
577 data
.universe_filter
= 0;
578 data
.collect_prefix
= 1;
580 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
582 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
583 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
584 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
586 data
.prefix
= isl_multi_union_pw_aff_intersect_domain(data
.prefix
,
592 /* Return the concatenation of the partial schedules of all outer band
593 * nodes of "node" interesected with all outer filters
594 * as an isl_union_pw_multi_aff.
596 * If "node" is pointing at the root of the schedule tree, then
597 * there are no domain elements reaching the current node, so
598 * we return an empty result.
600 * We collect all the filters and partial schedules in collect_filter_prefix.
601 * The partial schedules are collected as an isl_multi_union_pw_aff.
602 * If this isl_multi_union_pw_aff is zero-dimensional, then it does not
603 * contain any domain information, so we construct the isl_union_pw_multi_aff
604 * result as a zero-dimensional function on the collected filter.
605 * Otherwise, we convert the isl_multi_union_pw_aff to
606 * an isl_multi_union_pw_aff and intersect the domain with the filter.
608 __isl_give isl_union_pw_multi_aff
*
609 isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(
610 __isl_keep isl_schedule_node
*node
)
614 isl_union_pw_multi_aff
*prefix
;
615 struct isl_schedule_node_get_filter_prefix_data data
;
620 space
= isl_schedule_get_space(node
->schedule
);
621 if (node
->tree
== node
->schedule
->root
)
622 return isl_union_pw_multi_aff_empty(space
);
624 space
= isl_space_set_from_params(space
);
625 data
.initialized
= 0;
626 data
.universe_domain
= 1;
627 data
.universe_filter
= 0;
628 data
.collect_prefix
= 1;
630 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
632 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
633 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
634 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
637 isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
) == 0) {
638 isl_multi_union_pw_aff_free(data
.prefix
);
639 prefix
= isl_union_pw_multi_aff_from_domain(data
.filter
);
642 isl_union_pw_multi_aff_from_multi_union_pw_aff(data
.prefix
);
643 prefix
= isl_union_pw_multi_aff_intersect_domain(prefix
,
650 /* Return the concatenation of the partial schedules of all outer band
651 * nodes of "node" interesected with all outer filters
652 * as an isl_union_map.
654 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_union_map(
655 __isl_keep isl_schedule_node
*node
)
657 isl_union_pw_multi_aff
*upma
;
659 upma
= isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(node
);
660 return isl_union_map_from_union_pw_multi_aff(upma
);
663 /* Return the domain elements that reach "node".
665 * If "node" is pointing at the root of the schedule tree, then
666 * there are no domain elements reaching the current node, so
667 * we return an empty result.
669 * Otherwise, we collect all filters reaching the node,
670 * intersected with the root domain in collect_filter_prefix.
672 __isl_give isl_union_set
*isl_schedule_node_get_domain(
673 __isl_keep isl_schedule_node
*node
)
676 struct isl_schedule_node_get_filter_prefix_data data
;
681 if (node
->tree
== node
->schedule
->root
) {
684 space
= isl_schedule_get_space(node
->schedule
);
685 return isl_union_set_empty(space
);
688 data
.initialized
= 0;
689 data
.universe_domain
= 0;
690 data
.universe_filter
= 0;
691 data
.collect_prefix
= 0;
695 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
696 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
697 data
.filter
= isl_union_set_free(data
.filter
);
702 /* Return the union of universe sets of the domain elements that reach "node".
704 * If "node" is pointing at the root of the schedule tree, then
705 * there are no domain elements reaching the current node, so
706 * we return an empty result.
708 * Otherwise, we collect the universes of all filters reaching the node
709 * in collect_filter_prefix.
711 __isl_give isl_union_set
*isl_schedule_node_get_universe_domain(
712 __isl_keep isl_schedule_node
*node
)
715 struct isl_schedule_node_get_filter_prefix_data data
;
720 if (node
->tree
== node
->schedule
->root
) {
723 space
= isl_schedule_get_space(node
->schedule
);
724 return isl_union_set_empty(space
);
727 data
.initialized
= 0;
728 data
.universe_domain
= 1;
729 data
.universe_filter
= 1;
730 data
.collect_prefix
= 0;
734 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
735 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
736 data
.filter
= isl_union_set_free(data
.filter
);
741 /* Return the subtree schedule of "node".
743 * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle
744 * trees that do not contain any schedule information, we first
745 * move down to the first relevant descendant and handle leaves ourselves.
747 * If the subtree rooted at "node" contains any expansion nodes, then
748 * the returned subtree schedule is formulated in terms of the expanded
751 __isl_give isl_union_map
*isl_schedule_node_get_subtree_schedule_union_map(
752 __isl_keep isl_schedule_node
*node
)
754 isl_schedule_tree
*tree
, *leaf
;
757 tree
= isl_schedule_node_get_tree(node
);
758 leaf
= isl_schedule_node_peek_leaf(node
);
759 tree
= isl_schedule_tree_first_schedule_descendant(tree
, leaf
);
763 isl_union_set
*domain
;
764 domain
= isl_schedule_node_get_universe_domain(node
);
765 isl_schedule_tree_free(tree
);
766 return isl_union_map_from_domain(domain
);
769 umap
= isl_schedule_tree_get_subtree_schedule_union_map(tree
);
770 isl_schedule_tree_free(tree
);
774 /* Return the number of ancestors of "node" in its schedule tree.
776 int isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node
*node
)
780 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
783 /* Does "node" have a parent?
785 * That is, does it point to any node of the schedule other than the root?
787 int isl_schedule_node_has_parent(__isl_keep isl_schedule_node
*node
)
791 if (!node
->ancestors
)
794 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) != 0;
797 /* Return the position of "node" among the children of its parent.
799 int isl_schedule_node_get_child_position(__isl_keep isl_schedule_node
*node
)
806 has_parent
= isl_schedule_node_has_parent(node
);
810 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
811 "node has no parent", return -1);
813 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
814 return node
->child_pos
[n
- 1];
817 /* Does the parent (if any) of "node" have any children with a smaller child
818 * position than this one?
820 int isl_schedule_node_has_previous_sibling(__isl_keep isl_schedule_node
*node
)
827 has_parent
= isl_schedule_node_has_parent(node
);
828 if (has_parent
< 0 || !has_parent
)
831 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
833 return node
->child_pos
[n
- 1] > 0;
836 /* Does the parent (if any) of "node" have any children with a greater child
837 * position than this one?
839 int isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node
*node
)
843 isl_schedule_tree
*tree
;
847 has_parent
= isl_schedule_node_has_parent(node
);
848 if (has_parent
< 0 || !has_parent
)
851 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
852 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
855 n_child
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
856 isl_schedule_tree_free(tree
);
858 return node
->child_pos
[n
- 1] + 1 < n_child
;
861 /* Does "node" have any children?
863 * Any node other than the leaf nodes is considered to have at least
864 * one child, even if the corresponding isl_schedule_tree does not
867 int isl_schedule_node_has_children(__isl_keep isl_schedule_node
*node
)
871 return !isl_schedule_tree_is_leaf(node
->tree
);
874 /* Return the number of children of "node"?
876 * Any node other than the leaf nodes is considered to have at least
877 * one child, even if the corresponding isl_schedule_tree does not
878 * have any children. That is, the number of children of "node" is
879 * only zero if its tree is the explicit empty tree. Otherwise,
880 * if the isl_schedule_tree has any children, then it is equal
881 * to the number of children of "node". If it has zero children,
882 * then "node" still has a leaf node as child.
884 int isl_schedule_node_n_children(__isl_keep isl_schedule_node
*node
)
891 if (isl_schedule_tree_is_leaf(node
->tree
))
894 n
= isl_schedule_tree_n_children(node
->tree
);
901 /* Move the "node" pointer to the ancestor of the given generation
902 * of the node it currently points to, where generation 0 is the node
903 * itself and generation 1 is its parent.
905 __isl_give isl_schedule_node
*isl_schedule_node_ancestor(
906 __isl_take isl_schedule_node
*node
, int generation
)
909 isl_schedule_tree
*tree
;
915 n
= isl_schedule_node_get_tree_depth(node
);
917 return isl_schedule_node_free(node
);
918 if (generation
< 0 || generation
> n
)
919 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
920 "generation out of bounds",
921 return isl_schedule_node_free(node
));
922 node
= isl_schedule_node_cow(node
);
926 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
928 isl_schedule_tree_free(node
->tree
);
930 node
->ancestors
= isl_schedule_tree_list_drop(node
->ancestors
,
931 n
- generation
, generation
);
932 if (!node
->ancestors
|| !node
->tree
)
933 return isl_schedule_node_free(node
);
938 /* Move the "node" pointer to the parent of the node it currently points to.
940 __isl_give isl_schedule_node
*isl_schedule_node_parent(
941 __isl_take isl_schedule_node
*node
)
945 if (!isl_schedule_node_has_parent(node
))
946 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
947 "node has no parent",
948 return isl_schedule_node_free(node
));
949 return isl_schedule_node_ancestor(node
, 1);
952 /* Move the "node" pointer to the root of its schedule tree.
954 __isl_give isl_schedule_node
*isl_schedule_node_root(
955 __isl_take isl_schedule_node
*node
)
961 n
= isl_schedule_node_get_tree_depth(node
);
963 return isl_schedule_node_free(node
);
964 return isl_schedule_node_ancestor(node
, n
);
967 /* Move the "node" pointer to the child at position "pos" of the node
968 * it currently points to.
970 __isl_give isl_schedule_node
*isl_schedule_node_child(
971 __isl_take isl_schedule_node
*node
, int pos
)
975 isl_schedule_tree
*tree
;
978 node
= isl_schedule_node_cow(node
);
981 if (!isl_schedule_node_has_children(node
))
982 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
983 "node has no children",
984 return isl_schedule_node_free(node
));
986 ctx
= isl_schedule_node_get_ctx(node
);
987 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
988 child_pos
= isl_realloc_array(ctx
, node
->child_pos
, int, n
+ 1);
990 return isl_schedule_node_free(node
);
991 node
->child_pos
= child_pos
;
992 node
->child_pos
[n
] = pos
;
994 node
->ancestors
= isl_schedule_tree_list_add(node
->ancestors
,
995 isl_schedule_tree_copy(node
->tree
));
997 if (isl_schedule_tree_has_children(tree
))
998 tree
= isl_schedule_tree_get_child(tree
, pos
);
1000 tree
= isl_schedule_node_get_leaf(node
);
1001 isl_schedule_tree_free(node
->tree
);
1004 if (!node
->tree
|| !node
->ancestors
)
1005 return isl_schedule_node_free(node
);
1010 /* Move the "node" pointer to the first child of the node
1011 * it currently points to.
1013 __isl_give isl_schedule_node
*isl_schedule_node_first_child(
1014 __isl_take isl_schedule_node
*node
)
1016 return isl_schedule_node_child(node
, 0);
1019 /* Move the "node" pointer to the child of this node's parent in
1020 * the previous child position.
1022 __isl_give isl_schedule_node
*isl_schedule_node_previous_sibling(
1023 __isl_take isl_schedule_node
*node
)
1026 isl_schedule_tree
*parent
, *tree
;
1028 node
= isl_schedule_node_cow(node
);
1031 if (!isl_schedule_node_has_previous_sibling(node
))
1032 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1033 "node has no previous sibling",
1034 return isl_schedule_node_free(node
));
1036 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1037 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1040 return isl_schedule_node_free(node
);
1041 node
->child_pos
[n
- 1]--;
1042 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1043 node
->child_pos
[n
- 1]);
1044 isl_schedule_tree_free(parent
);
1046 return isl_schedule_node_free(node
);
1047 isl_schedule_tree_free(node
->tree
);
1053 /* Move the "node" pointer to the child of this node's parent in
1054 * the next child position.
1056 __isl_give isl_schedule_node
*isl_schedule_node_next_sibling(
1057 __isl_take isl_schedule_node
*node
)
1060 isl_schedule_tree
*parent
, *tree
;
1062 node
= isl_schedule_node_cow(node
);
1065 if (!isl_schedule_node_has_next_sibling(node
))
1066 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1067 "node has no next sibling",
1068 return isl_schedule_node_free(node
));
1070 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1071 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1074 return isl_schedule_node_free(node
);
1075 node
->child_pos
[n
- 1]++;
1076 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1077 node
->child_pos
[n
- 1]);
1078 isl_schedule_tree_free(parent
);
1080 return isl_schedule_node_free(node
);
1081 isl_schedule_tree_free(node
->tree
);
1087 /* Return a copy to the child at position "pos" of "node".
1089 __isl_give isl_schedule_node
*isl_schedule_node_get_child(
1090 __isl_keep isl_schedule_node
*node
, int pos
)
1092 return isl_schedule_node_child(isl_schedule_node_copy(node
), pos
);
1095 /* Traverse the descendant of "node" in depth-first order, including
1096 * "node" itself. Call "enter" whenever a node is entered and "leave"
1097 * whenever a node is left. The callback "enter" is responsible
1098 * for moving to the deepest initial subtree of its argument that
1099 * should be traversed.
1101 static __isl_give isl_schedule_node
*traverse(
1102 __isl_take isl_schedule_node
*node
,
1103 __isl_give isl_schedule_node
*(*enter
)(
1104 __isl_take isl_schedule_node
*node
, void *user
),
1105 __isl_give isl_schedule_node
*(*leave
)(
1106 __isl_take isl_schedule_node
*node
, void *user
),
1114 depth
= isl_schedule_node_get_tree_depth(node
);
1116 node
= enter(node
, user
);
1117 node
= leave(node
, user
);
1118 while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
&&
1119 !isl_schedule_node_has_next_sibling(node
)) {
1120 node
= isl_schedule_node_parent(node
);
1121 node
= leave(node
, user
);
1123 if (node
&& isl_schedule_node_get_tree_depth(node
) > depth
)
1124 node
= isl_schedule_node_next_sibling(node
);
1125 } while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
);
1130 /* Internal data structure for isl_schedule_node_foreach_descendant.
1132 * "fn" is the user-specified callback function.
1133 * "user" is the user-specified argument for the callback.
1135 struct isl_schedule_node_preorder_data
{
1136 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
);
1140 /* Callback for "traverse" to enter a node and to move
1141 * to the deepest initial subtree that should be traversed
1142 * for use in a preorder visit.
1144 * If the user callback returns a negative value, then we abort
1145 * the traversal. If this callback returns zero, then we skip
1146 * the subtree rooted at the current node. Otherwise, we move
1147 * down to the first child and repeat the process until a leaf
1150 static __isl_give isl_schedule_node
*preorder_enter(
1151 __isl_take isl_schedule_node
*node
, void *user
)
1153 struct isl_schedule_node_preorder_data
*data
= user
;
1161 r
= data
->fn(node
, data
->user
);
1163 return isl_schedule_node_free(node
);
1166 } while (isl_schedule_node_has_children(node
) &&
1167 (node
= isl_schedule_node_first_child(node
)) != NULL
);
1172 /* Callback for "traverse" to leave a node
1173 * for use in a preorder visit.
1174 * Since we already visited the node when we entered it,
1175 * we do not need to do anything here.
1177 static __isl_give isl_schedule_node
*preorder_leave(
1178 __isl_take isl_schedule_node
*node
, void *user
)
1183 /* Traverse the descendants of "node" (including the node itself)
1184 * in depth first preorder.
1186 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1187 * If "fn" returns 0 on any of the nodes, then the subtree rooted
1188 * at that node is skipped.
1190 * Return 0 on success and -1 on failure.
1192 int isl_schedule_node_foreach_descendant(__isl_keep isl_schedule_node
*node
,
1193 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
), void *user
)
1195 struct isl_schedule_node_preorder_data data
= { fn
, user
};
1197 node
= isl_schedule_node_copy(node
);
1198 node
= traverse(node
, &preorder_enter
, &preorder_leave
, &data
);
1199 isl_schedule_node_free(node
);
1201 return node
? 0 : -1;
1204 /* Internal data structure for isl_schedule_node_map_descendant.
1206 * "fn" is the user-specified callback function.
1207 * "user" is the user-specified argument for the callback.
1209 struct isl_schedule_node_postorder_data
{
1210 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1215 /* Callback for "traverse" to enter a node and to move
1216 * to the deepest initial subtree that should be traversed
1217 * for use in a postorder visit.
1219 * Since we are performing a postorder visit, we only need
1220 * to move to the deepest initial leaf here.
1222 static __isl_give isl_schedule_node
*postorder_enter(
1223 __isl_take isl_schedule_node
*node
, void *user
)
1225 while (node
&& isl_schedule_node_has_children(node
))
1226 node
= isl_schedule_node_first_child(node
);
1231 /* Callback for "traverse" to leave a node
1232 * for use in a postorder visit.
1234 * Since we are performing a postorder visit, we need
1235 * to call the user callback here.
1237 static __isl_give isl_schedule_node
*postorder_leave(
1238 __isl_take isl_schedule_node
*node
, void *user
)
1240 struct isl_schedule_node_postorder_data
*data
= user
;
1242 return data
->fn(node
, data
->user
);
1245 /* Traverse the descendants of "node" (including the node itself)
1246 * in depth first postorder, allowing the user to modify the visited node.
1247 * The traversal continues from the node returned by the callback function.
1248 * It is the responsibility of the user to ensure that this does not
1249 * lead to an infinite loop. It is safest to always return a pointer
1250 * to the same position (same ancestors and child positions) as the input node.
1252 __isl_give isl_schedule_node
*isl_schedule_node_map_descendant(
1253 __isl_take isl_schedule_node
*node
,
1254 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1255 void *user
), void *user
)
1257 struct isl_schedule_node_postorder_data data
= { fn
, user
};
1259 return traverse(node
, &postorder_enter
, &postorder_leave
, &data
);
1262 /* Traverse the ancestors of "node" from the root down to and including
1263 * the parent of "node", calling "fn" on each of them.
1265 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1267 * Return 0 on success and -1 on failure.
1269 int isl_schedule_node_foreach_ancestor_top_down(
1270 __isl_keep isl_schedule_node
*node
,
1271 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
), void *user
)
1278 n
= isl_schedule_node_get_tree_depth(node
);
1279 for (i
= 0; i
< n
; ++i
) {
1280 isl_schedule_node
*ancestor
;
1283 ancestor
= isl_schedule_node_copy(node
);
1284 ancestor
= isl_schedule_node_ancestor(ancestor
, n
- i
);
1285 r
= fn(ancestor
, user
);
1286 isl_schedule_node_free(ancestor
);
1294 /* Is any node in the subtree rooted at "node" anchored?
1295 * That is, do any of these nodes reference the outer band nodes?
1297 int isl_schedule_node_is_subtree_anchored(__isl_keep isl_schedule_node
*node
)
1301 return isl_schedule_tree_is_subtree_anchored(node
->tree
);
1304 /* Return the number of members in the given band node.
1306 unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node
*node
)
1308 return node
? isl_schedule_tree_band_n_member(node
->tree
) : 0;
1311 /* Is the band member at position "pos" of the band node "node"
1312 * marked coincident?
1314 int isl_schedule_node_band_member_get_coincident(
1315 __isl_keep isl_schedule_node
*node
, int pos
)
1319 return isl_schedule_tree_band_member_get_coincident(node
->tree
, pos
);
1322 /* Mark the band member at position "pos" the band node "node"
1323 * as being coincident or not according to "coincident".
1325 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_coincident(
1326 __isl_take isl_schedule_node
*node
, int pos
, int coincident
)
1329 isl_schedule_tree
*tree
;
1333 c
= isl_schedule_node_band_member_get_coincident(node
, pos
);
1334 if (c
== coincident
)
1337 tree
= isl_schedule_tree_copy(node
->tree
);
1338 tree
= isl_schedule_tree_band_member_set_coincident(tree
, pos
,
1340 node
= isl_schedule_node_graft_tree(node
, tree
);
1345 /* Is the band node "node" marked permutable?
1347 int isl_schedule_node_band_get_permutable(__isl_keep isl_schedule_node
*node
)
1352 return isl_schedule_tree_band_get_permutable(node
->tree
);
1355 /* Mark the band node "node" permutable or not according to "permutable"?
1357 __isl_give isl_schedule_node
*isl_schedule_node_band_set_permutable(
1358 __isl_take isl_schedule_node
*node
, int permutable
)
1360 isl_schedule_tree
*tree
;
1364 if (isl_schedule_node_band_get_permutable(node
) == permutable
)
1367 tree
= isl_schedule_tree_copy(node
->tree
);
1368 tree
= isl_schedule_tree_band_set_permutable(tree
, permutable
);
1369 node
= isl_schedule_node_graft_tree(node
, tree
);
1374 /* Return the schedule space of the band node.
1376 __isl_give isl_space
*isl_schedule_node_band_get_space(
1377 __isl_keep isl_schedule_node
*node
)
1382 return isl_schedule_tree_band_get_space(node
->tree
);
1385 /* Return the schedule of the band node in isolation.
1387 __isl_give isl_multi_union_pw_aff
*isl_schedule_node_band_get_partial_schedule(
1388 __isl_keep isl_schedule_node
*node
)
1393 return isl_schedule_tree_band_get_partial_schedule(node
->tree
);
1396 /* Return the schedule of the band node in isolation in the form of
1399 * If the band does not have any members, then we construct a universe map
1400 * with the universe of the domain elements reaching the node as domain.
1401 * Otherwise, we extract an isl_multi_union_pw_aff representation and
1402 * convert that to an isl_union_map.
1404 __isl_give isl_union_map
*isl_schedule_node_band_get_partial_schedule_union_map(
1405 __isl_keep isl_schedule_node
*node
)
1407 isl_multi_union_pw_aff
*mupa
;
1412 if (isl_schedule_node_get_type(node
) != isl_schedule_node_band
)
1413 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1414 "not a band node", return NULL
);
1415 if (isl_schedule_node_band_n_member(node
) == 0) {
1416 isl_union_set
*domain
;
1418 domain
= isl_schedule_node_get_universe_domain(node
);
1419 return isl_union_map_from_domain(domain
);
1422 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
1423 return isl_union_map_from_multi_union_pw_aff(mupa
);
1426 /* Return the loop AST generation type for the band member of band node "node"
1427 * at position "pos".
1429 enum isl_ast_loop_type
isl_schedule_node_band_member_get_ast_loop_type(
1430 __isl_keep isl_schedule_node
*node
, int pos
)
1433 return isl_ast_loop_error
;
1435 return isl_schedule_tree_band_member_get_ast_loop_type(node
->tree
, pos
);
1438 /* Set the loop AST generation type for the band member of band node "node"
1439 * at position "pos" to "type".
1441 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_ast_loop_type(
1442 __isl_take isl_schedule_node
*node
, int pos
,
1443 enum isl_ast_loop_type type
)
1445 isl_schedule_tree
*tree
;
1450 tree
= isl_schedule_tree_copy(node
->tree
);
1451 tree
= isl_schedule_tree_band_member_set_ast_loop_type(tree
, pos
, type
);
1452 return isl_schedule_node_graft_tree(node
, tree
);
1455 /* Return the loop AST generation type for the band member of band node "node"
1456 * at position "pos" for the isolated part.
1458 enum isl_ast_loop_type
isl_schedule_node_band_member_get_isolate_ast_loop_type(
1459 __isl_keep isl_schedule_node
*node
, int pos
)
1462 return isl_ast_loop_error
;
1464 return isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1468 /* Set the loop AST generation type for the band member of band node "node"
1469 * at position "pos" for the isolated part to "type".
1471 __isl_give isl_schedule_node
*
1472 isl_schedule_node_band_member_set_isolate_ast_loop_type(
1473 __isl_take isl_schedule_node
*node
, int pos
,
1474 enum isl_ast_loop_type type
)
1476 isl_schedule_tree
*tree
;
1481 tree
= isl_schedule_tree_copy(node
->tree
);
1482 tree
= isl_schedule_tree_band_member_set_isolate_ast_loop_type(tree
,
1484 return isl_schedule_node_graft_tree(node
, tree
);
1487 /* Return the AST build options associated to band node "node".
1489 __isl_give isl_union_set
*isl_schedule_node_band_get_ast_build_options(
1490 __isl_keep isl_schedule_node
*node
)
1495 return isl_schedule_tree_band_get_ast_build_options(node
->tree
);
1498 /* Replace the AST build options associated to band node "node" by "options".
1500 __isl_give isl_schedule_node
*isl_schedule_node_band_set_ast_build_options(
1501 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*options
)
1503 isl_schedule_tree
*tree
;
1505 if (!node
|| !options
)
1508 tree
= isl_schedule_tree_copy(node
->tree
);
1509 tree
= isl_schedule_tree_band_set_ast_build_options(tree
, options
);
1510 return isl_schedule_node_graft_tree(node
, tree
);
1512 isl_schedule_node_free(node
);
1513 isl_union_set_free(options
);
1517 /* Make sure that that spaces of "node" and "mv" are the same.
1518 * Return -1 on error, reporting the error to the user.
1520 static int check_space_multi_val(__isl_keep isl_schedule_node
*node
,
1521 __isl_keep isl_multi_val
*mv
)
1523 isl_space
*node_space
, *mv_space
;
1526 node_space
= isl_schedule_node_band_get_space(node
);
1527 mv_space
= isl_multi_val_get_space(mv
);
1528 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1529 mv_space
, isl_dim_set
);
1530 isl_space_free(mv_space
);
1531 isl_space_free(node_space
);
1535 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1536 "spaces don't match", return -1);
1541 /* Multiply the partial schedule of the band node "node"
1542 * with the factors in "mv".
1544 __isl_give isl_schedule_node
*isl_schedule_node_band_scale(
1545 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1547 isl_schedule_tree
*tree
;
1552 if (check_space_multi_val(node
, mv
) < 0)
1554 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1558 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1559 "cannot scale band node with anchored subtree",
1562 tree
= isl_schedule_node_get_tree(node
);
1563 tree
= isl_schedule_tree_band_scale(tree
, mv
);
1564 return isl_schedule_node_graft_tree(node
, tree
);
1566 isl_multi_val_free(mv
);
1567 isl_schedule_node_free(node
);
1571 /* Divide the partial schedule of the band node "node"
1572 * by the factors in "mv".
1574 __isl_give isl_schedule_node
*isl_schedule_node_band_scale_down(
1575 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1577 isl_schedule_tree
*tree
;
1582 if (check_space_multi_val(node
, mv
) < 0)
1584 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1588 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1589 "cannot scale down band node with anchored subtree",
1592 tree
= isl_schedule_node_get_tree(node
);
1593 tree
= isl_schedule_tree_band_scale_down(tree
, mv
);
1594 return isl_schedule_node_graft_tree(node
, tree
);
1596 isl_multi_val_free(mv
);
1597 isl_schedule_node_free(node
);
1601 /* Tile "node" with tile sizes "sizes".
1603 * The current node is replaced by two nested nodes corresponding
1604 * to the tile dimensions and the point dimensions.
1606 * Return a pointer to the outer (tile) node.
1608 * If any of the descendants of "node" depend on the set of outer band nodes,
1609 * then we refuse to tile the node.
1611 * If the scale tile loops option is set, then the tile loops
1612 * are scaled by the tile sizes. If the shift point loops option is set,
1613 * then the point loops are shifted to start at zero.
1614 * In particular, these options affect the tile and point loop schedules
1617 * scale shift original tile point
1619 * 0 0 i floor(i/s) i
1620 * 1 0 i s * floor(i/s) i
1621 * 0 1 i floor(i/s) i - s * floor(i/s)
1622 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1624 __isl_give isl_schedule_node
*isl_schedule_node_band_tile(
1625 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*sizes
)
1627 isl_schedule_tree
*tree
;
1630 if (!node
|| !sizes
)
1632 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1636 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1637 "cannot tile band node with anchored subtree",
1640 if (check_space_multi_val(node
, sizes
) < 0)
1643 tree
= isl_schedule_node_get_tree(node
);
1644 tree
= isl_schedule_tree_band_tile(tree
, sizes
);
1645 return isl_schedule_node_graft_tree(node
, tree
);
1647 isl_multi_val_free(sizes
);
1648 isl_schedule_node_free(node
);
1652 /* Move the band node "node" down to all the leaves in the subtree
1654 * Return a pointer to the node in the resulting tree that is in the same
1655 * position as the node pointed to by "node" in the original tree.
1657 * If the node only has a leaf child, then nothing needs to be done.
1658 * Otherwise, the child of the node is removed and the result is
1659 * appended to all the leaves in the subtree rooted at the original child.
1660 * The original node is then replaced by the result of this operation.
1662 * If any of the nodes in the subtree rooted at "node" depend on
1663 * the set of outer band nodes then we refuse to sink the band node.
1665 __isl_give isl_schedule_node
*isl_schedule_node_band_sink(
1666 __isl_take isl_schedule_node
*node
)
1668 enum isl_schedule_node_type type
;
1669 isl_schedule_tree
*tree
, *child
;
1675 type
= isl_schedule_node_get_type(node
);
1676 if (type
!= isl_schedule_node_band
)
1677 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1678 "not a band node", isl_schedule_node_free(node
));
1679 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1681 return isl_schedule_node_free(node
);
1683 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1684 "cannot sink band node in anchored subtree",
1685 isl_schedule_node_free(node
));
1686 if (isl_schedule_tree_n_children(node
->tree
) == 0)
1689 tree
= isl_schedule_node_get_tree(node
);
1690 child
= isl_schedule_tree_get_child(tree
, 0);
1691 tree
= isl_schedule_tree_reset_children(tree
);
1692 tree
= isl_schedule_tree_append_to_leaves(child
, tree
);
1694 return isl_schedule_node_graft_tree(node
, tree
);
1697 /* Split "node" into two nested band nodes, one with the first "pos"
1698 * dimensions and one with the remaining dimensions.
1699 * The schedules of the two band nodes live in anonymous spaces.
1701 __isl_give isl_schedule_node
*isl_schedule_node_band_split(
1702 __isl_take isl_schedule_node
*node
, int pos
)
1704 isl_schedule_tree
*tree
;
1706 tree
= isl_schedule_node_get_tree(node
);
1707 tree
= isl_schedule_tree_band_split(tree
, pos
);
1708 return isl_schedule_node_graft_tree(node
, tree
);
1711 /* Return the context of the context node "node".
1713 __isl_give isl_set
*isl_schedule_node_context_get_context(
1714 __isl_keep isl_schedule_node
*node
)
1719 return isl_schedule_tree_context_get_context(node
->tree
);
1722 /* Return the domain of the domain node "node".
1724 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
1725 __isl_keep isl_schedule_node
*node
)
1730 return isl_schedule_tree_domain_get_domain(node
->tree
);
1733 /* Return the expansion map of expansion node "node".
1735 __isl_give isl_union_map
*isl_schedule_node_expansion_get_expansion(
1736 __isl_keep isl_schedule_node
*node
)
1741 return isl_schedule_tree_expansion_get_expansion(node
->tree
);
1744 /* Return the contraction of expansion node "node".
1746 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_expansion_get_contraction(
1747 __isl_keep isl_schedule_node
*node
)
1752 return isl_schedule_tree_expansion_get_contraction(node
->tree
);
1755 /* Replace the contraction and the expansion of the expansion node "node"
1756 * by "contraction" and "expansion".
1758 __isl_give isl_schedule_node
*
1759 isl_schedule_node_expansion_set_contraction_and_expansion(
1760 __isl_take isl_schedule_node
*node
,
1761 __isl_take isl_union_pw_multi_aff
*contraction
,
1762 __isl_take isl_union_map
*expansion
)
1764 isl_schedule_tree
*tree
;
1766 if (!node
|| !contraction
|| !expansion
)
1769 tree
= isl_schedule_tree_copy(node
->tree
);
1770 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
1771 contraction
, expansion
);
1772 return isl_schedule_node_graft_tree(node
, tree
);
1774 isl_schedule_node_free(node
);
1775 isl_union_pw_multi_aff_free(contraction
);
1776 isl_union_map_free(expansion
);
1780 /* Return the filter of the filter node "node".
1782 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
1783 __isl_keep isl_schedule_node
*node
)
1788 return isl_schedule_tree_filter_get_filter(node
->tree
);
1791 /* Replace the filter of filter node "node" by "filter".
1793 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
1794 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
1796 isl_schedule_tree
*tree
;
1798 if (!node
|| !filter
)
1801 tree
= isl_schedule_tree_copy(node
->tree
);
1802 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
1803 return isl_schedule_node_graft_tree(node
, tree
);
1805 isl_schedule_node_free(node
);
1806 isl_union_set_free(filter
);
1810 /* Update the ancestors of "node" to point to the tree that "node"
1812 * That is, replace the child in the original parent that corresponds
1813 * to the current tree position by node->tree and continue updating
1814 * the ancestors in the same way until the root is reached.
1816 * If "fn" is not NULL, then it is called on each ancestor as we move up
1817 * the tree so that it can modify the ancestor before it is added
1818 * to the list of ancestors of the modified node.
1819 * The additional "pos" argument records the position
1820 * of the "tree" argument in the original schedule tree.
1822 * If "node" originally points to a leaf of the schedule tree, then make sure
1823 * that in the end it points to a leaf in the updated schedule tree.
1825 static __isl_give isl_schedule_node
*update_ancestors(
1826 __isl_take isl_schedule_node
*node
,
1827 __isl_give isl_schedule_tree
*(*fn
)(__isl_take isl_schedule_tree
*tree
,
1828 __isl_keep isl_schedule_node
*pos
, void *user
), void *user
)
1833 isl_schedule_tree
*tree
;
1834 isl_schedule_node
*pos
= NULL
;
1837 pos
= isl_schedule_node_copy(node
);
1839 node
= isl_schedule_node_cow(node
);
1841 return isl_schedule_node_free(pos
);
1843 ctx
= isl_schedule_node_get_ctx(node
);
1844 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1845 tree
= isl_schedule_tree_copy(node
->tree
);
1847 for (i
= n
- 1; i
>= 0; --i
) {
1848 isl_schedule_tree
*parent
;
1850 parent
= isl_schedule_tree_list_get_schedule_tree(
1851 node
->ancestors
, i
);
1852 parent
= isl_schedule_tree_replace_child(parent
,
1853 node
->child_pos
[i
], tree
);
1855 pos
= isl_schedule_node_parent(pos
);
1856 parent
= fn(parent
, pos
, user
);
1858 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
1859 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
1865 isl_schedule_node_free(pos
);
1867 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
1868 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
1870 isl_schedule_tree_free(node
->tree
);
1871 node
->tree
= isl_schedule_node_get_leaf(node
);
1874 if (!node
->schedule
|| !node
->ancestors
)
1875 return isl_schedule_node_free(node
);
1880 /* Replace the subtree that "pos" points to by "tree", updating
1881 * the ancestors to maintain a consistent state.
1883 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
1884 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
1888 if (pos
->tree
== tree
) {
1889 isl_schedule_tree_free(tree
);
1893 pos
= isl_schedule_node_cow(pos
);
1897 isl_schedule_tree_free(pos
->tree
);
1900 return update_ancestors(pos
, NULL
, NULL
);
1902 isl_schedule_node_free(pos
);
1903 isl_schedule_tree_free(tree
);
1907 /* Make sure we can insert a node between "node" and its parent.
1908 * Return -1 on error, reporting the reason why we cannot insert a node.
1910 static int check_insert(__isl_keep isl_schedule_node
*node
)
1913 enum isl_schedule_node_type type
;
1915 has_parent
= isl_schedule_node_has_parent(node
);
1919 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1920 "cannot insert node outside of root", return -1);
1922 type
= isl_schedule_node_get_parent_type(node
);
1923 if (type
== isl_schedule_node_error
)
1925 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
1926 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1927 "cannot insert node between set or sequence node "
1928 "and its filter children", return -1);
1933 /* Insert a band node with partial schedule "mupa" between "node" and
1935 * Return a pointer to the new band node.
1937 * If any of the nodes in the subtree rooted at "node" depend on
1938 * the set of outer band nodes then we refuse to insert the band node.
1940 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
1941 __isl_take isl_schedule_node
*node
,
1942 __isl_take isl_multi_union_pw_aff
*mupa
)
1945 isl_schedule_band
*band
;
1946 isl_schedule_tree
*tree
;
1948 if (check_insert(node
) < 0)
1949 node
= isl_schedule_node_free(node
);
1950 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1954 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1955 "cannot insert band node in anchored subtree",
1958 tree
= isl_schedule_node_get_tree(node
);
1959 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
1960 tree
= isl_schedule_tree_insert_band(tree
, band
);
1961 node
= isl_schedule_node_graft_tree(node
, tree
);
1965 isl_schedule_node_free(node
);
1966 isl_multi_union_pw_aff_free(mupa
);
1970 /* Insert a context node with context "context" between "node" and its parent.
1971 * Return a pointer to the new context node.
1973 __isl_give isl_schedule_node
*isl_schedule_node_insert_context(
1974 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
1976 isl_schedule_tree
*tree
;
1978 if (check_insert(node
) < 0)
1979 node
= isl_schedule_node_free(node
);
1981 tree
= isl_schedule_node_get_tree(node
);
1982 tree
= isl_schedule_tree_insert_context(tree
, context
);
1983 node
= isl_schedule_node_graft_tree(node
, tree
);
1988 /* Insert an expansion node with the given "contraction" and "expansion"
1989 * between "node" and its parent.
1990 * Return a pointer to the new expansion node.
1992 * Typically the domain and range spaces of the expansion are different.
1993 * This means that only one of them can refer to the current domain space
1994 * in a consistent tree. It is up to the caller to ensure that the tree
1995 * returns to a consistent state.
1997 __isl_give isl_schedule_node
*isl_schedule_node_insert_expansion(
1998 __isl_take isl_schedule_node
*node
,
1999 __isl_take isl_union_pw_multi_aff
*contraction
,
2000 __isl_take isl_union_map
*expansion
)
2002 isl_schedule_tree
*tree
;
2004 if (check_insert(node
) < 0)
2005 node
= isl_schedule_node_free(node
);
2007 tree
= isl_schedule_node_get_tree(node
);
2008 tree
= isl_schedule_tree_insert_expansion(tree
, contraction
, expansion
);
2009 node
= isl_schedule_node_graft_tree(node
, tree
);
2014 /* Insert a filter node with filter "filter" between "node" and its parent.
2015 * Return a pointer to the new filter node.
2017 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
2018 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2020 isl_schedule_tree
*tree
;
2022 if (check_insert(node
) < 0)
2023 node
= isl_schedule_node_free(node
);
2025 tree
= isl_schedule_node_get_tree(node
);
2026 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2027 node
= isl_schedule_node_graft_tree(node
, tree
);
2032 /* Attach the current subtree of "node" to a sequence of filter tree nodes
2033 * with filters described by "filters", attach this sequence
2034 * of filter tree nodes as children to a new tree of type "type" and
2035 * replace the original subtree of "node" by this new tree.
2037 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
2038 __isl_take isl_schedule_node
*node
,
2039 enum isl_schedule_node_type type
,
2040 __isl_take isl_union_set_list
*filters
)
2044 isl_schedule_tree
*tree
;
2045 isl_schedule_tree_list
*list
;
2047 if (check_insert(node
) < 0)
2048 node
= isl_schedule_node_free(node
);
2050 if (!node
|| !filters
)
2053 ctx
= isl_schedule_node_get_ctx(node
);
2054 n
= isl_union_set_list_n_union_set(filters
);
2055 list
= isl_schedule_tree_list_alloc(ctx
, n
);
2056 for (i
= 0; i
< n
; ++i
) {
2057 isl_schedule_tree
*tree
;
2058 isl_union_set
*filter
;
2060 tree
= isl_schedule_node_get_tree(node
);
2061 filter
= isl_union_set_list_get_union_set(filters
, i
);
2062 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2063 list
= isl_schedule_tree_list_add(list
, tree
);
2065 tree
= isl_schedule_tree_from_children(type
, list
);
2066 node
= isl_schedule_node_graft_tree(node
, tree
);
2068 isl_union_set_list_free(filters
);
2071 isl_union_set_list_free(filters
);
2072 isl_schedule_node_free(node
);
2076 /* Insert a sequence node with child filters "filters" between "node" and
2077 * its parent. That is, the tree that "node" points to is attached
2078 * to each of the child nodes of the filter nodes.
2079 * Return a pointer to the new sequence node.
2081 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
2082 __isl_take isl_schedule_node
*node
,
2083 __isl_take isl_union_set_list
*filters
)
2085 return isl_schedule_node_insert_children(node
,
2086 isl_schedule_node_sequence
, filters
);
2089 /* Insert a set node with child filters "filters" between "node" and
2090 * its parent. That is, the tree that "node" points to is attached
2091 * to each of the child nodes of the filter nodes.
2092 * Return a pointer to the new set node.
2094 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
2095 __isl_take isl_schedule_node
*node
,
2096 __isl_take isl_union_set_list
*filters
)
2098 return isl_schedule_node_insert_children(node
,
2099 isl_schedule_node_set
, filters
);
2102 /* Remove "node" from its schedule tree and return a pointer
2103 * to the leaf at the same position in the updated schedule tree.
2105 * It is not allowed to remove the root of a schedule tree or
2106 * a child of a set or sequence node.
2108 __isl_give isl_schedule_node
*isl_schedule_node_cut(
2109 __isl_take isl_schedule_node
*node
)
2111 isl_schedule_tree
*leaf
;
2112 enum isl_schedule_node_type parent_type
;
2116 if (!isl_schedule_node_has_parent(node
))
2117 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2118 "cannot cut root", return isl_schedule_node_free(node
));
2120 parent_type
= isl_schedule_node_get_parent_type(node
);
2121 if (parent_type
== isl_schedule_node_set
||
2122 parent_type
== isl_schedule_node_sequence
)
2123 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2124 "cannot cut child of set or sequence",
2125 return isl_schedule_node_free(node
));
2127 leaf
= isl_schedule_node_get_leaf(node
);
2128 return isl_schedule_node_graft_tree(node
, leaf
);
2131 /* Remove a single node from the schedule tree, attaching the child
2132 * of "node" directly to its parent.
2133 * Return a pointer to this former child or to the leaf the position
2134 * of the original node if there was no child.
2135 * It is not allowed to remove the root of a schedule tree,
2136 * a set or sequence node, a child of a set or sequence node or
2137 * a band node with an anchored subtree.
2139 __isl_give isl_schedule_node
*isl_schedule_node_delete(
2140 __isl_take isl_schedule_node
*node
)
2143 isl_schedule_tree
*tree
;
2144 enum isl_schedule_node_type type
;
2149 if (isl_schedule_node_get_tree_depth(node
) == 0)
2150 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2151 "cannot delete root node",
2152 return isl_schedule_node_free(node
));
2153 n
= isl_schedule_node_n_children(node
);
2155 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2156 "can only delete node with a single child",
2157 return isl_schedule_node_free(node
));
2158 type
= isl_schedule_node_get_parent_type(node
);
2159 if (type
== isl_schedule_node_sequence
|| type
== isl_schedule_node_set
)
2160 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2161 "cannot delete child of set or sequence",
2162 return isl_schedule_node_free(node
));
2163 if (isl_schedule_node_get_type(node
) == isl_schedule_node_band
) {
2166 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2168 return isl_schedule_node_free(node
);
2170 isl_die(isl_schedule_node_get_ctx(node
),
2172 "cannot delete band node with anchored subtree",
2173 return isl_schedule_node_free(node
));
2176 tree
= isl_schedule_node_get_tree(node
);
2177 if (!tree
|| isl_schedule_tree_has_children(tree
)) {
2178 tree
= isl_schedule_tree_child(tree
, 0);
2180 isl_schedule_tree_free(tree
);
2181 tree
= isl_schedule_node_get_leaf(node
);
2183 node
= isl_schedule_node_graft_tree(node
, tree
);
2188 /* Internal data structure for the group_ancestor callback.
2190 * If "finished" is set, then we no longer need to modify
2191 * any further ancestors.
2193 * "contraction" and "expansion" represent the expansion
2194 * that reflects the grouping.
2196 * "domain" contains the domain elements that reach the position
2197 * where the grouping is performed. That is, it is the range
2198 * of the resulting expansion.
2199 * "domain_universe" is the universe of "domain".
2200 * "group" is the set of group elements, i.e., the domain
2201 * of the resulting expansion.
2202 * "group_universe" is the universe of "group".
2204 * "sched" is the schedule for the group elements, in pratice
2205 * an identity mapping on "group_universe".
2206 * "dim" is the dimension of "sched".
2208 struct isl_schedule_group_data
{
2211 isl_union_map
*expansion
;
2212 isl_union_pw_multi_aff
*contraction
;
2214 isl_union_set
*domain
;
2215 isl_union_set
*domain_universe
;
2216 isl_union_set
*group
;
2217 isl_union_set
*group_universe
;
2220 isl_multi_aff
*sched
;
2223 /* Is domain covered by data->domain within data->domain_universe?
2225 static int locally_covered_by_domain(__isl_keep isl_union_set
*domain
,
2226 struct isl_schedule_group_data
*data
)
2229 isl_union_set
*test
;
2231 test
= isl_union_set_copy(domain
);
2232 test
= isl_union_set_intersect(test
,
2233 isl_union_set_copy(data
->domain_universe
));
2234 is_subset
= isl_union_set_is_subset(test
, data
->domain
);
2235 isl_union_set_free(test
);
2240 /* Update the band tree root "tree" to refer to the group instances
2241 * in data->group rather than the original domain elements in data->domain.
2242 * "pos" is the position in the original schedule tree where the modified
2243 * "tree" will be attached.
2245 * Add the part of the identity schedule on the group instances data->sched
2246 * that corresponds to this band node to the band schedule.
2247 * If the domain elements that reach the node and that are part
2248 * of data->domain_universe are all elements of data->domain (and therefore
2249 * replaced by the group instances) then this data->domain_universe
2250 * is removed from the domain of the band schedule.
2252 static __isl_give isl_schedule_tree
*group_band(
2253 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2254 struct isl_schedule_group_data
*data
)
2256 isl_union_set
*domain
;
2258 isl_multi_union_pw_aff
*mupa
, *partial
;
2260 int depth
, n
, has_id
;
2262 domain
= isl_schedule_node_get_domain(pos
);
2263 is_covered
= locally_covered_by_domain(domain
, data
);
2264 if (is_covered
>= 0 && is_covered
) {
2265 domain
= isl_union_set_universe(domain
);
2266 domain
= isl_union_set_subtract(domain
,
2267 isl_union_set_copy(data
->domain_universe
));
2268 tree
= isl_schedule_tree_band_intersect_domain(tree
, domain
);
2270 isl_union_set_free(domain
);
2272 return isl_schedule_tree_free(tree
);
2273 depth
= isl_schedule_node_get_schedule_depth(pos
);
2274 n
= isl_schedule_tree_band_n_member(tree
);
2275 ma
= isl_multi_aff_copy(data
->sched
);
2276 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, depth
);
2277 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, n
, data
->dim
- depth
- n
);
2278 mupa
= isl_multi_union_pw_aff_from_multi_aff(ma
);
2279 partial
= isl_schedule_tree_band_get_partial_schedule(tree
);
2280 has_id
= isl_multi_union_pw_aff_has_tuple_id(partial
, isl_dim_set
);
2282 partial
= isl_multi_union_pw_aff_free(partial
);
2283 } else if (has_id
) {
2285 id
= isl_multi_union_pw_aff_get_tuple_id(partial
, isl_dim_set
);
2286 mupa
= isl_multi_union_pw_aff_set_tuple_id(mupa
,
2289 partial
= isl_multi_union_pw_aff_union_add(partial
, mupa
);
2290 tree
= isl_schedule_tree_band_set_partial_schedule(tree
, partial
);
2295 /* Drop the parameters in "uset" that are not also in "space".
2296 * "n" is the number of parameters in "space".
2298 static __isl_give isl_union_set
*union_set_drop_extra_params(
2299 __isl_take isl_union_set
*uset
, __isl_keep isl_space
*space
, int n
)
2303 uset
= isl_union_set_align_params(uset
, isl_space_copy(space
));
2304 n2
= isl_union_set_dim(uset
, isl_dim_param
);
2305 uset
= isl_union_set_project_out(uset
, isl_dim_param
, n
, n2
- n
);
2310 /* Update the context tree root "tree" to refer to the group instances
2311 * in data->group rather than the original domain elements in data->domain.
2312 * "pos" is the position in the original schedule tree where the modified
2313 * "tree" will be attached.
2315 * We do not actually need to update "tree" since a context node only
2316 * refers to the schedule space. However, we may need to update "data"
2317 * to not refer to any parameters introduced by the context node.
2319 static __isl_give isl_schedule_tree
*group_context(
2320 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2321 struct isl_schedule_group_data
*data
)
2324 isl_union_set
*domain
;
2328 if (isl_schedule_node_get_tree_depth(pos
) == 1)
2331 domain
= isl_schedule_node_get_universe_domain(pos
);
2332 space
= isl_union_set_get_space(domain
);
2333 isl_union_set_free(domain
);
2335 n1
= isl_space_dim(space
, isl_dim_param
);
2336 data
->expansion
= isl_union_map_align_params(data
->expansion
, space
);
2337 n2
= isl_union_map_dim(data
->expansion
, isl_dim_param
);
2339 if (!data
->expansion
)
2340 return isl_schedule_tree_free(tree
);
2344 involves
= isl_union_map_involves_dims(data
->expansion
,
2345 isl_dim_param
, n1
, n2
- n1
);
2347 return isl_schedule_tree_free(tree
);
2349 isl_die(isl_schedule_node_get_ctx(pos
), isl_error_invalid
,
2350 "grouping cannot only refer to global parameters",
2351 return isl_schedule_tree_free(tree
));
2353 data
->expansion
= isl_union_map_project_out(data
->expansion
,
2354 isl_dim_param
, n1
, n2
- n1
);
2355 space
= isl_union_map_get_space(data
->expansion
);
2357 data
->contraction
= isl_union_pw_multi_aff_align_params(
2358 data
->contraction
, isl_space_copy(space
));
2359 n2
= isl_union_pw_multi_aff_dim(data
->contraction
, isl_dim_param
);
2360 data
->contraction
= isl_union_pw_multi_aff_drop_dims(data
->contraction
,
2361 isl_dim_param
, n1
, n2
- n1
);
2363 data
->domain
= union_set_drop_extra_params(data
->domain
, space
, n1
);
2364 data
->domain_universe
=
2365 union_set_drop_extra_params(data
->domain_universe
, space
, n1
);
2366 data
->group
= union_set_drop_extra_params(data
->group
, space
, n1
);
2367 data
->group_universe
=
2368 union_set_drop_extra_params(data
->group_universe
, space
, n1
);
2370 data
->sched
= isl_multi_aff_align_params(data
->sched
,
2371 isl_space_copy(space
));
2372 n2
= isl_multi_aff_dim(data
->sched
, isl_dim_param
);
2373 data
->sched
= isl_multi_aff_drop_dims(data
->sched
,
2374 isl_dim_param
, n1
, n2
- n1
);
2376 isl_space_free(space
);
2381 /* Update the domain tree root "tree" to refer to the group instances
2382 * in data->group rather than the original domain elements in data->domain.
2383 * "pos" is the position in the original schedule tree where the modified
2384 * "tree" will be attached.
2386 * We first double-check that all grouped domain elements are actually
2387 * part of the root domain and then replace those elements by the group
2390 static __isl_give isl_schedule_tree
*group_domain(
2391 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2392 struct isl_schedule_group_data
*data
)
2394 isl_union_set
*domain
;
2397 domain
= isl_schedule_tree_domain_get_domain(tree
);
2398 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2399 isl_union_set_free(domain
);
2401 return isl_schedule_tree_free(tree
);
2403 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2404 "grouped domain should be part of outer domain",
2405 return isl_schedule_tree_free(tree
));
2406 domain
= isl_schedule_tree_domain_get_domain(tree
);
2407 domain
= isl_union_set_subtract(domain
,
2408 isl_union_set_copy(data
->domain
));
2409 domain
= isl_union_set_union(domain
, isl_union_set_copy(data
->group
));
2410 tree
= isl_schedule_tree_domain_set_domain(tree
, domain
);
2415 /* Update the expansion tree root "tree" to refer to the group instances
2416 * in data->group rather than the original domain elements in data->domain.
2417 * "pos" is the position in the original schedule tree where the modified
2418 * "tree" will be attached.
2420 * Let G_1 -> D_1 be the expansion of "tree" and G_2 -> D_2 the newly
2421 * introduced expansion in a descendant of "tree".
2422 * We first double-check that D_2 is a subset of D_1.
2423 * Then we remove D_2 from the range of G_1 -> D_1 and add the mapping
2424 * G_1 -> D_1 . D_2 -> G_2.
2425 * Simmilarly, we restrict the domain of the contraction to the universe
2426 * of the range of the updated expansion and add G_2 -> D_2 . D_1 -> G_1,
2427 * attempting to remove the domain constraints of this additional part.
2429 static __isl_give isl_schedule_tree
*group_expansion(
2430 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2431 struct isl_schedule_group_data
*data
)
2433 isl_union_set
*domain
;
2434 isl_union_map
*expansion
, *umap
;
2435 isl_union_pw_multi_aff
*contraction
, *upma
;
2438 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2439 domain
= isl_union_map_range(expansion
);
2440 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2441 isl_union_set_free(domain
);
2443 return isl_schedule_tree_free(tree
);
2445 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2446 "grouped domain should be part "
2447 "of outer expansion domain",
2448 return isl_schedule_tree_free(tree
));
2449 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2450 umap
= isl_union_map_from_union_pw_multi_aff(
2451 isl_union_pw_multi_aff_copy(data
->contraction
));
2452 umap
= isl_union_map_apply_range(expansion
, umap
);
2453 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2454 expansion
= isl_union_map_subtract_range(expansion
,
2455 isl_union_set_copy(data
->domain
));
2456 expansion
= isl_union_map_union(expansion
, umap
);
2457 umap
= isl_union_map_universe(isl_union_map_copy(expansion
));
2458 domain
= isl_union_map_range(umap
);
2459 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
2460 umap
= isl_union_map_from_union_pw_multi_aff(contraction
);
2461 umap
= isl_union_map_apply_range(isl_union_map_copy(data
->expansion
),
2463 upma
= isl_union_pw_multi_aff_from_union_map(umap
);
2464 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
2465 contraction
= isl_union_pw_multi_aff_intersect_domain(contraction
,
2467 domain
= isl_union_pw_multi_aff_domain(
2468 isl_union_pw_multi_aff_copy(upma
));
2469 upma
= isl_union_pw_multi_aff_gist(upma
, domain
);
2470 contraction
= isl_union_pw_multi_aff_union_add(contraction
, upma
);
2471 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
2472 contraction
, expansion
);
2477 /* Update the tree root "tree" to refer to the group instances
2478 * in data->group rather than the original domain elements in data->domain.
2479 * "pos" is the position in the original schedule tree where the modified
2480 * "tree" will be attached.
2482 * If we have come across a domain or expansion node before (data->finished
2483 * is set), then we no longer need perform any modifications.
2485 * If "tree" is a filter, then we add data->group_universe to the filter.
2486 * We also remove data->domain_universe from the filter if all the domain
2487 * elements in this universe that reach the filter node are part of
2488 * the elements that are being grouped by data->expansion.
2489 * If "tree" is a band, domain or expansion, then it is handled
2490 * in a separate function.
2492 static __isl_give isl_schedule_tree
*group_ancestor(
2493 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2496 struct isl_schedule_group_data
*data
= user
;
2497 isl_union_set
*domain
;
2501 return isl_schedule_tree_free(tree
);
2506 switch (isl_schedule_tree_get_type(tree
)) {
2507 case isl_schedule_node_error
:
2508 return isl_schedule_tree_free(tree
);
2509 case isl_schedule_node_band
:
2510 tree
= group_band(tree
, pos
, data
);
2512 case isl_schedule_node_context
:
2513 tree
= group_context(tree
, pos
, data
);
2515 case isl_schedule_node_domain
:
2516 tree
= group_domain(tree
, pos
, data
);
2519 case isl_schedule_node_filter
:
2520 domain
= isl_schedule_node_get_domain(pos
);
2521 is_covered
= locally_covered_by_domain(domain
, data
);
2522 isl_union_set_free(domain
);
2524 return isl_schedule_tree_free(tree
);
2525 domain
= isl_schedule_tree_filter_get_filter(tree
);
2527 domain
= isl_union_set_subtract(domain
,
2528 isl_union_set_copy(data
->domain_universe
));
2529 domain
= isl_union_set_union(domain
,
2530 isl_union_set_copy(data
->group_universe
));
2531 tree
= isl_schedule_tree_filter_set_filter(tree
, domain
);
2533 case isl_schedule_node_expansion
:
2534 tree
= group_expansion(tree
, pos
, data
);
2537 case isl_schedule_node_leaf
:
2538 case isl_schedule_node_sequence
:
2539 case isl_schedule_node_set
:
2546 /* Group the domain elements that reach "node" into instances
2547 * of a single statement with identifier "group_id".
2548 * In particular, group the domain elements according to their
2551 * That is, introduce an expansion node with as contraction
2552 * the prefix schedule (with the target space replaced by "group_id")
2553 * and as expansion the inverse of this contraction (with its range
2554 * intersected with the domain elements that reach "node").
2555 * The outer nodes are then modified to refer to the group instances
2556 * instead of the original domain elements.
2558 * No instance of "group_id" is allowed to reach "node" prior
2561 * Return a pointer to original node in tree, i.e., the child
2562 * of the newly introduced expansion node.
2564 __isl_give isl_schedule_node
*isl_schedule_node_group(
2565 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*group_id
)
2567 struct isl_schedule_group_data data
= { 0 };
2569 isl_union_set
*domain
;
2570 isl_union_pw_multi_aff
*contraction
;
2571 isl_union_map
*expansion
;
2574 if (!node
|| !group_id
)
2576 if (check_insert(node
) < 0)
2579 domain
= isl_schedule_node_get_domain(node
);
2580 data
.domain
= isl_union_set_copy(domain
);
2581 data
.domain_universe
= isl_union_set_copy(domain
);
2582 data
.domain_universe
= isl_union_set_universe(data
.domain_universe
);
2584 data
.dim
= isl_schedule_node_get_schedule_depth(node
);
2585 if (data
.dim
== 0) {
2588 isl_union_set
*group
;
2589 isl_union_map
*univ
;
2591 ctx
= isl_schedule_node_get_ctx(node
);
2592 space
= isl_space_set_alloc(ctx
, 0, 0);
2593 space
= isl_space_set_tuple_id(space
, isl_dim_set
, group_id
);
2594 set
= isl_set_universe(isl_space_copy(space
));
2595 group
= isl_union_set_from_set(set
);
2596 expansion
= isl_union_map_from_domain_and_range(domain
, group
);
2597 univ
= isl_union_map_universe(isl_union_map_copy(expansion
));
2598 contraction
= isl_union_pw_multi_aff_from_union_map(univ
);
2599 expansion
= isl_union_map_reverse(expansion
);
2601 isl_multi_union_pw_aff
*prefix
;
2602 isl_union_set
*univ
;
2605 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node
);
2606 prefix
= isl_multi_union_pw_aff_set_tuple_id(prefix
,
2607 isl_dim_set
, group_id
);
2608 space
= isl_multi_union_pw_aff_get_space(prefix
);
2609 contraction
= isl_union_pw_multi_aff_from_multi_union_pw_aff(
2611 univ
= isl_union_set_universe(isl_union_set_copy(domain
));
2613 isl_union_pw_multi_aff_intersect_domain(contraction
, univ
);
2614 expansion
= isl_union_map_from_union_pw_multi_aff(
2615 isl_union_pw_multi_aff_copy(contraction
));
2616 expansion
= isl_union_map_reverse(expansion
);
2617 expansion
= isl_union_map_intersect_range(expansion
, domain
);
2619 space
= isl_space_map_from_set(space
);
2620 data
.sched
= isl_multi_aff_identity(space
);
2621 data
.group
= isl_union_map_domain(isl_union_map_copy(expansion
));
2622 data
.group
= isl_union_set_coalesce(data
.group
);
2623 data
.group_universe
= isl_union_set_copy(data
.group
);
2624 data
.group_universe
= isl_union_set_universe(data
.group_universe
);
2625 data
.expansion
= isl_union_map_copy(expansion
);
2626 data
.contraction
= isl_union_pw_multi_aff_copy(contraction
);
2627 node
= isl_schedule_node_insert_expansion(node
, contraction
, expansion
);
2629 disjoint
= isl_union_set_is_disjoint(data
.domain_universe
,
2630 data
.group_universe
);
2632 node
= update_ancestors(node
, &group_ancestor
, &data
);
2634 isl_union_set_free(data
.domain
);
2635 isl_union_set_free(data
.domain_universe
);
2636 isl_union_set_free(data
.group
);
2637 isl_union_set_free(data
.group_universe
);
2638 isl_multi_aff_free(data
.sched
);
2639 isl_union_map_free(data
.expansion
);
2640 isl_union_pw_multi_aff_free(data
.contraction
);
2642 node
= isl_schedule_node_child(node
, 0);
2644 if (!node
|| disjoint
< 0)
2645 return isl_schedule_node_free(node
);
2647 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2648 "group instances already reach node",
2649 isl_schedule_node_free(node
));
2653 isl_schedule_node_free(node
);
2654 isl_id_free(group_id
);
2658 /* Compute the gist of the given band node with respect to "context".
2660 __isl_give isl_schedule_node
*isl_schedule_node_band_gist(
2661 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
2663 isl_schedule_tree
*tree
;
2665 tree
= isl_schedule_node_get_tree(node
);
2666 tree
= isl_schedule_tree_band_gist(tree
, context
);
2667 return isl_schedule_node_graft_tree(node
, tree
);
2670 /* Internal data structure for isl_schedule_node_gist.
2671 * "n_expansion" is the number of outer expansion nodes
2672 * with respect to the current position
2673 * "filters" contains an element for each outer filter or expansion node
2674 * with respect to the current position, each representing
2675 * the intersection of the previous element and the filter on the filter node
2676 * or the expansion of the previous element.
2677 * The first element in the original context passed to isl_schedule_node_gist.
2679 struct isl_node_gist_data
{
2681 isl_union_set_list
*filters
;
2684 /* Enter the expansion node "node" during a isl_schedule_node_gist traversal.
2686 * In particular, add an extra element to data->filters containing
2687 * the expansion of the previous element and replace the expansion
2688 * and contraction on "node" by the gist with respect to these filters.
2689 * Also keep track of the fact that we have entered another expansion.
2691 static __isl_give isl_schedule_node
*gist_enter_expansion(
2692 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
2695 isl_union_set
*inner
;
2696 isl_union_map
*expansion
;
2697 isl_union_pw_multi_aff
*contraction
;
2699 data
->n_expansion
++;
2701 n
= isl_union_set_list_n_union_set(data
->filters
);
2702 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
2703 expansion
= isl_schedule_node_expansion_get_expansion(node
);
2704 inner
= isl_union_set_apply(inner
, expansion
);
2706 contraction
= isl_schedule_node_expansion_get_contraction(node
);
2707 contraction
= isl_union_pw_multi_aff_gist(contraction
,
2708 isl_union_set_copy(inner
));
2710 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
2712 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
2713 expansion
= isl_schedule_node_expansion_get_expansion(node
);
2714 expansion
= isl_union_map_gist_domain(expansion
, inner
);
2715 node
= isl_schedule_node_expansion_set_contraction_and_expansion(node
,
2716 contraction
, expansion
);
2721 /* Can we finish gisting at this node?
2722 * That is, is the filter on the current filter node a subset of
2723 * the original context passed to isl_schedule_node_gist?
2724 * If we have gone through any expansions, then we cannot perform
2725 * this test since the current domain elements are incomparable
2726 * to the domain elements in the original context.
2728 static int gist_done(__isl_keep isl_schedule_node
*node
,
2729 struct isl_node_gist_data
*data
)
2731 isl_union_set
*filter
, *outer
;
2734 if (data
->n_expansion
!= 0)
2737 filter
= isl_schedule_node_filter_get_filter(node
);
2738 outer
= isl_union_set_list_get_union_set(data
->filters
, 0);
2739 subset
= isl_union_set_is_subset(filter
, outer
);
2740 isl_union_set_free(outer
);
2741 isl_union_set_free(filter
);
2746 /* Callback for "traverse" to enter a node and to move
2747 * to the deepest initial subtree that should be traversed
2748 * by isl_schedule_node_gist.
2750 * The "filters" list is extended by one element each time
2751 * we come across a filter node by the result of intersecting
2752 * the last element in the list with the filter on the filter node.
2754 * If the filter on the current filter node is a subset of
2755 * the original context passed to isl_schedule_node_gist,
2756 * then there is no need to go into its subtree since it cannot
2757 * be further simplified by the context. The "filters" list is
2758 * still extended for consistency, but the actual value of the
2759 * added element is immaterial since it will not be used.
2761 * Otherwise, the filter on the current filter node is replaced by
2762 * the gist of the original filter with respect to the intersection
2763 * of the original context with the intermediate filters.
2765 * If the new element in the "filters" list is empty, then no elements
2766 * can reach the descendants of the current filter node. The subtree
2767 * underneath the filter node is therefore removed.
2769 * Each expansion node we come across is handled by
2770 * gist_enter_expansion.
2772 static __isl_give isl_schedule_node
*gist_enter(
2773 __isl_take isl_schedule_node
*node
, void *user
)
2775 struct isl_node_gist_data
*data
= user
;
2778 isl_union_set
*filter
, *inner
;
2782 switch (isl_schedule_node_get_type(node
)) {
2783 case isl_schedule_node_error
:
2784 return isl_schedule_node_free(node
);
2785 case isl_schedule_node_expansion
:
2786 node
= gist_enter_expansion(node
, data
);
2788 case isl_schedule_node_band
:
2789 case isl_schedule_node_context
:
2790 case isl_schedule_node_domain
:
2791 case isl_schedule_node_leaf
:
2792 case isl_schedule_node_sequence
:
2793 case isl_schedule_node_set
:
2795 case isl_schedule_node_filter
:
2798 done
= gist_done(node
, data
);
2799 filter
= isl_schedule_node_filter_get_filter(node
);
2800 if (done
< 0 || done
) {
2801 data
->filters
= isl_union_set_list_add(data
->filters
,
2804 return isl_schedule_node_free(node
);
2807 n
= isl_union_set_list_n_union_set(data
->filters
);
2808 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
2809 filter
= isl_union_set_gist(filter
, isl_union_set_copy(inner
));
2810 node
= isl_schedule_node_filter_set_filter(node
,
2811 isl_union_set_copy(filter
));
2812 filter
= isl_union_set_intersect(filter
, inner
);
2813 empty
= isl_union_set_is_empty(filter
);
2814 data
->filters
= isl_union_set_list_add(data
->filters
, filter
);
2816 return isl_schedule_node_free(node
);
2819 node
= isl_schedule_node_child(node
, 0);
2820 node
= isl_schedule_node_cut(node
);
2821 node
= isl_schedule_node_parent(node
);
2823 } while (isl_schedule_node_has_children(node
) &&
2824 (node
= isl_schedule_node_first_child(node
)) != NULL
);
2829 /* Callback for "traverse" to leave a node for isl_schedule_node_gist.
2831 * In particular, if the current node is a filter node, then we remove
2832 * the element on the "filters" list that was added when we entered
2833 * the node. There is no need to compute any gist here, since we
2834 * already did that when we entered the node.
2836 * If the current node is an expansion, then we decrement
2837 * the number of outer expansions and remove the element
2838 * in data->filters that was added by gist_enter_expansion.
2840 * If the current node is a band node, then we compute the gist of
2841 * the band node with respect to the intersection of the original context
2842 * and the intermediate filters.
2844 * If the current node is a sequence or set node, then some of
2845 * the filter children may have become empty and so they are removed.
2846 * If only one child is left, then the set or sequence node along with
2847 * the single remaining child filter is removed. The filter can be
2848 * removed because the filters on a sequence or set node are supposed
2849 * to partition the incoming domain instances.
2850 * In principle, it should then be impossible for there to be zero
2851 * remaining children, but should this happen, we replace the entire
2852 * subtree with an empty filter.
2854 static __isl_give isl_schedule_node
*gist_leave(
2855 __isl_take isl_schedule_node
*node
, void *user
)
2857 struct isl_node_gist_data
*data
= user
;
2858 isl_schedule_tree
*tree
;
2860 isl_union_set
*filter
;
2862 switch (isl_schedule_node_get_type(node
)) {
2863 case isl_schedule_node_error
:
2864 return isl_schedule_node_free(node
);
2865 case isl_schedule_node_expansion
:
2866 data
->n_expansion
--;
2867 case isl_schedule_node_filter
:
2868 n
= isl_union_set_list_n_union_set(data
->filters
);
2869 data
->filters
= isl_union_set_list_drop(data
->filters
,
2872 case isl_schedule_node_band
:
2873 n
= isl_union_set_list_n_union_set(data
->filters
);
2874 filter
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
2875 node
= isl_schedule_node_band_gist(node
, filter
);
2877 case isl_schedule_node_set
:
2878 case isl_schedule_node_sequence
:
2879 tree
= isl_schedule_node_get_tree(node
);
2880 n
= isl_schedule_tree_n_children(tree
);
2881 for (i
= n
- 1; i
>= 0; --i
) {
2882 isl_schedule_tree
*child
;
2883 isl_union_set
*filter
;
2886 child
= isl_schedule_tree_get_child(tree
, i
);
2887 filter
= isl_schedule_tree_filter_get_filter(child
);
2888 empty
= isl_union_set_is_empty(filter
);
2889 isl_union_set_free(filter
);
2890 isl_schedule_tree_free(child
);
2892 tree
= isl_schedule_tree_free(tree
);
2894 tree
= isl_schedule_tree_drop_child(tree
, i
);
2896 n
= isl_schedule_tree_n_children(tree
);
2897 node
= isl_schedule_node_graft_tree(node
, tree
);
2899 node
= isl_schedule_node_delete(node
);
2900 node
= isl_schedule_node_delete(node
);
2901 } else if (n
== 0) {
2905 isl_union_set_list_get_union_set(data
->filters
, 0);
2906 space
= isl_union_set_get_space(filter
);
2907 isl_union_set_free(filter
);
2908 filter
= isl_union_set_empty(space
);
2909 node
= isl_schedule_node_cut(node
);
2910 node
= isl_schedule_node_insert_filter(node
, filter
);
2913 case isl_schedule_node_context
:
2914 case isl_schedule_node_domain
:
2915 case isl_schedule_node_leaf
:
2922 /* Compute the gist of the subtree at "node" with respect to
2923 * the reaching domain elements in "context".
2924 * In particular, compute the gist of all band and filter nodes
2925 * in the subtree with respect to "context". Children of set or sequence
2926 * nodes that end up with an empty filter are removed completely.
2928 * We keep track of the intersection of "context" with all outer filters
2929 * of the current node within the subtree in the final element of "filters".
2930 * Initially, this list contains the single element "context" and it is
2931 * extended or shortened each time we enter or leave a filter node.
2933 __isl_give isl_schedule_node
*isl_schedule_node_gist(
2934 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
2936 struct isl_node_gist_data data
;
2938 data
.n_expansion
= 0;
2939 data
.filters
= isl_union_set_list_from_union_set(context
);
2940 node
= traverse(node
, &gist_enter
, &gist_leave
, &data
);
2941 isl_union_set_list_free(data
.filters
);
2945 /* Intersect the domain of domain node "node" with "domain".
2947 * If the domain of "node" is already a subset of "domain",
2948 * then nothing needs to be changed.
2950 * Otherwise, we replace the domain of the domain node by the intersection
2951 * and simplify the subtree rooted at "node" with respect to this intersection.
2953 __isl_give isl_schedule_node
*isl_schedule_node_domain_intersect_domain(
2954 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
)
2956 isl_schedule_tree
*tree
;
2957 isl_union_set
*uset
;
2960 if (!node
|| !domain
)
2963 uset
= isl_schedule_tree_domain_get_domain(node
->tree
);
2964 is_subset
= isl_union_set_is_subset(uset
, domain
);
2965 isl_union_set_free(uset
);
2969 isl_union_set_free(domain
);
2973 tree
= isl_schedule_tree_copy(node
->tree
);
2974 uset
= isl_schedule_tree_domain_get_domain(tree
);
2975 uset
= isl_union_set_intersect(uset
, domain
);
2976 tree
= isl_schedule_tree_domain_set_domain(tree
,
2977 isl_union_set_copy(uset
));
2978 node
= isl_schedule_node_graft_tree(node
, tree
);
2980 node
= isl_schedule_node_child(node
, 0);
2981 node
= isl_schedule_node_gist(node
, uset
);
2982 node
= isl_schedule_node_parent(node
);
2986 isl_schedule_node_free(node
);
2987 isl_union_set_free(domain
);
2991 /* Internal data structure for isl_schedule_node_get_subtree_expansion.
2992 * "expansions" contains a list of accumulated expansions
2993 * for each outer expansion, set or sequence node. The first element
2994 * in the list is an identity mapping on the reaching domain elements.
2995 * "res" collects the results.
2997 struct isl_subtree_expansion_data
{
2998 isl_union_map_list
*expansions
;
3002 /* Callback for "traverse" to enter a node and to move
3003 * to the deepest initial subtree that should be traversed
3004 * by isl_schedule_node_get_subtree_expansion.
3006 * Whenever we come across an expansion node, the last element
3007 * of data->expansions is combined with the expansion
3008 * on the expansion node.
3010 * Whenever we come across a filter node that is the child
3011 * of a set or sequence node, data->expansions is extended
3012 * with a new element that restricts the previous element
3013 * to the elements selected by the filter.
3014 * The previous element can then be reused while backtracking.
3016 static __isl_give isl_schedule_node
*subtree_expansion_enter(
3017 __isl_take isl_schedule_node
*node
, void *user
)
3019 struct isl_subtree_expansion_data
*data
= user
;
3022 enum isl_schedule_node_type type
;
3023 isl_union_set
*filter
;
3024 isl_union_map
*inner
, *expansion
;
3027 switch (isl_schedule_node_get_type(node
)) {
3028 case isl_schedule_node_error
:
3029 return isl_schedule_node_free(node
);
3030 case isl_schedule_node_filter
:
3031 type
= isl_schedule_node_get_parent_type(node
);
3032 if (type
!= isl_schedule_node_set
&&
3033 type
!= isl_schedule_node_sequence
)
3035 filter
= isl_schedule_node_filter_get_filter(node
);
3036 n
= isl_union_map_list_n_union_map(data
->expansions
);
3038 isl_union_map_list_get_union_map(data
->expansions
,
3040 inner
= isl_union_map_intersect_range(inner
, filter
);
3042 isl_union_map_list_add(data
->expansions
, inner
);
3044 case isl_schedule_node_expansion
:
3045 n
= isl_union_map_list_n_union_map(data
->expansions
);
3047 isl_schedule_node_expansion_get_expansion(node
);
3049 isl_union_map_list_get_union_map(data
->expansions
,
3051 inner
= isl_union_map_apply_range(inner
, expansion
);
3053 isl_union_map_list_set_union_map(data
->expansions
,
3056 case isl_schedule_node_band
:
3057 case isl_schedule_node_context
:
3058 case isl_schedule_node_domain
:
3059 case isl_schedule_node_leaf
:
3060 case isl_schedule_node_sequence
:
3061 case isl_schedule_node_set
:
3064 } while (isl_schedule_node_has_children(node
) &&
3065 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3070 /* Callback for "traverse" to leave a node for
3071 * isl_schedule_node_get_subtree_expansion.
3073 * If we come across a filter node that is the child
3074 * of a set or sequence node, then we remove the element
3075 * of data->expansions that was added in subtree_expansion_enter.
3077 * If we reach a leaf node, then the accumulated expansion is
3078 * added to data->res.
3080 static __isl_give isl_schedule_node
*subtree_expansion_leave(
3081 __isl_take isl_schedule_node
*node
, void *user
)
3083 struct isl_subtree_expansion_data
*data
= user
;
3085 isl_union_map
*inner
;
3086 enum isl_schedule_node_type type
;
3088 switch (isl_schedule_node_get_type(node
)) {
3089 case isl_schedule_node_error
:
3090 return isl_schedule_node_free(node
);
3091 case isl_schedule_node_filter
:
3092 type
= isl_schedule_node_get_parent_type(node
);
3093 if (type
!= isl_schedule_node_set
&&
3094 type
!= isl_schedule_node_sequence
)
3096 n
= isl_union_map_list_n_union_map(data
->expansions
);
3097 data
->expansions
= isl_union_map_list_drop(data
->expansions
,
3100 case isl_schedule_node_leaf
:
3101 n
= isl_union_map_list_n_union_map(data
->expansions
);
3102 inner
= isl_union_map_list_get_union_map(data
->expansions
,
3104 data
->res
= isl_union_map_union(data
->res
, inner
);
3106 case isl_schedule_node_band
:
3107 case isl_schedule_node_context
:
3108 case isl_schedule_node_domain
:
3109 case isl_schedule_node_expansion
:
3110 case isl_schedule_node_sequence
:
3111 case isl_schedule_node_set
:
3118 /* Return a mapping from the domain elements that reach "node"
3119 * to the corresponding domain elements in the leaves of the subtree
3120 * rooted at "node" obtained by composing the intermediate expansions.
3122 * We start out with an identity mapping between the domain elements
3123 * that reach "node" and compose it with all the expansions
3124 * on a path from "node" to a leaf while traversing the subtree.
3125 * Within the children of an a sequence or set node, the
3126 * accumulated expansion is restricted to the elements selected
3127 * by the filter child.
3129 __isl_give isl_union_map
*isl_schedule_node_get_subtree_expansion(
3130 __isl_keep isl_schedule_node
*node
)
3132 struct isl_subtree_expansion_data data
;
3134 isl_union_set
*domain
;
3135 isl_union_map
*expansion
;
3140 domain
= isl_schedule_node_get_universe_domain(node
);
3141 space
= isl_union_set_get_space(domain
);
3142 expansion
= isl_union_set_identity(domain
);
3143 data
.res
= isl_union_map_empty(space
);
3144 data
.expansions
= isl_union_map_list_from_union_map(expansion
);
3146 node
= isl_schedule_node_copy(node
);
3147 node
= traverse(node
, &subtree_expansion_enter
,
3148 &subtree_expansion_leave
, &data
);
3150 data
.res
= isl_union_map_free(data
.res
);
3151 isl_schedule_node_free(node
);
3153 isl_union_map_list_free(data
.expansions
);
3158 /* Internal data structure for isl_schedule_node_get_subtree_contraction.
3159 * "contractions" contains a list of accumulated contractions
3160 * for each outer expansion, set or sequence node. The first element
3161 * in the list is an identity mapping on the reaching domain elements.
3162 * "res" collects the results.
3164 struct isl_subtree_contraction_data
{
3165 isl_union_pw_multi_aff_list
*contractions
;
3166 isl_union_pw_multi_aff
*res
;
3169 /* Callback for "traverse" to enter a node and to move
3170 * to the deepest initial subtree that should be traversed
3171 * by isl_schedule_node_get_subtree_contraction.
3173 * Whenever we come across an expansion node, the last element
3174 * of data->contractions is combined with the contraction
3175 * on the expansion node.
3177 * Whenever we come across a filter node that is the child
3178 * of a set or sequence node, data->contractions is extended
3179 * with a new element that restricts the previous element
3180 * to the elements selected by the filter.
3181 * The previous element can then be reused while backtracking.
3183 static __isl_give isl_schedule_node
*subtree_contraction_enter(
3184 __isl_take isl_schedule_node
*node
, void *user
)
3186 struct isl_subtree_contraction_data
*data
= user
;
3189 enum isl_schedule_node_type type
;
3190 isl_union_set
*filter
;
3191 isl_union_pw_multi_aff
*inner
, *contraction
;
3194 switch (isl_schedule_node_get_type(node
)) {
3195 case isl_schedule_node_error
:
3196 return isl_schedule_node_free(node
);
3197 case isl_schedule_node_filter
:
3198 type
= isl_schedule_node_get_parent_type(node
);
3199 if (type
!= isl_schedule_node_set
&&
3200 type
!= isl_schedule_node_sequence
)
3202 filter
= isl_schedule_node_filter_get_filter(node
);
3203 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3204 data
->contractions
);
3206 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3207 data
->contractions
, n
- 1);
3208 inner
= isl_union_pw_multi_aff_intersect_domain(inner
,
3210 data
->contractions
=
3211 isl_union_pw_multi_aff_list_add(data
->contractions
,
3214 case isl_schedule_node_expansion
:
3215 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3216 data
->contractions
);
3218 isl_schedule_node_expansion_get_contraction(node
);
3220 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3221 data
->contractions
, n
- 1);
3223 isl_union_pw_multi_aff_pullback_union_pw_multi_aff(
3224 inner
, contraction
);
3225 data
->contractions
=
3226 isl_union_pw_multi_aff_list_set_union_pw_multi_aff(
3227 data
->contractions
, n
- 1, inner
);
3229 case isl_schedule_node_band
:
3230 case isl_schedule_node_context
:
3231 case isl_schedule_node_domain
:
3232 case isl_schedule_node_leaf
:
3233 case isl_schedule_node_sequence
:
3234 case isl_schedule_node_set
:
3237 } while (isl_schedule_node_has_children(node
) &&
3238 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3243 /* Callback for "traverse" to leave a node for
3244 * isl_schedule_node_get_subtree_contraction.
3246 * If we come across a filter node that is the child
3247 * of a set or sequence node, then we remove the element
3248 * of data->contractions that was added in subtree_contraction_enter.
3250 * If we reach a leaf node, then the accumulated contraction is
3251 * added to data->res.
3253 static __isl_give isl_schedule_node
*subtree_contraction_leave(
3254 __isl_take isl_schedule_node
*node
, void *user
)
3256 struct isl_subtree_contraction_data
*data
= user
;
3258 isl_union_pw_multi_aff
*inner
;
3259 enum isl_schedule_node_type type
;
3261 switch (isl_schedule_node_get_type(node
)) {
3262 case isl_schedule_node_error
:
3263 return isl_schedule_node_free(node
);
3264 case isl_schedule_node_filter
:
3265 type
= isl_schedule_node_get_parent_type(node
);
3266 if (type
!= isl_schedule_node_set
&&
3267 type
!= isl_schedule_node_sequence
)
3269 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3270 data
->contractions
);
3271 data
->contractions
=
3272 isl_union_pw_multi_aff_list_drop(data
->contractions
,
3275 case isl_schedule_node_leaf
:
3276 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3277 data
->contractions
);
3278 inner
= isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3279 data
->contractions
, n
- 1);
3280 data
->res
= isl_union_pw_multi_aff_union_add(data
->res
, inner
);
3282 case isl_schedule_node_band
:
3283 case isl_schedule_node_context
:
3284 case isl_schedule_node_domain
:
3285 case isl_schedule_node_expansion
:
3286 case isl_schedule_node_sequence
:
3287 case isl_schedule_node_set
:
3294 /* Return a mapping from the domain elements in the leaves of the subtree
3295 * rooted at "node" to the corresponding domain elements that reach "node"
3296 * obtained by composing the intermediate contractions.
3298 * We start out with an identity mapping between the domain elements
3299 * that reach "node" and compose it with all the contractions
3300 * on a path from "node" to a leaf while traversing the subtree.
3301 * Within the children of an a sequence or set node, the
3302 * accumulated contraction is restricted to the elements selected
3303 * by the filter child.
3305 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_get_subtree_contraction(
3306 __isl_keep isl_schedule_node
*node
)
3308 struct isl_subtree_contraction_data data
;
3310 isl_union_set
*domain
;
3311 isl_union_pw_multi_aff
*contraction
;
3316 domain
= isl_schedule_node_get_universe_domain(node
);
3317 space
= isl_union_set_get_space(domain
);
3318 contraction
= isl_union_set_identity_union_pw_multi_aff(domain
);
3319 data
.res
= isl_union_pw_multi_aff_empty(space
);
3321 isl_union_pw_multi_aff_list_from_union_pw_multi_aff(contraction
);
3323 node
= isl_schedule_node_copy(node
);
3324 node
= traverse(node
, &subtree_contraction_enter
,
3325 &subtree_contraction_leave
, &data
);
3327 data
.res
= isl_union_pw_multi_aff_free(data
.res
);
3328 isl_schedule_node_free(node
);
3330 isl_union_pw_multi_aff_list_free(data
.contractions
);
3335 /* Reset the user pointer on all identifiers of parameters and tuples
3336 * in the schedule node "node".
3338 __isl_give isl_schedule_node
*isl_schedule_node_reset_user(
3339 __isl_take isl_schedule_node
*node
)
3341 isl_schedule_tree
*tree
;
3343 tree
= isl_schedule_node_get_tree(node
);
3344 tree
= isl_schedule_tree_reset_user(tree
);
3345 node
= isl_schedule_node_graft_tree(node
, tree
);
3350 /* Align the parameters of the schedule node "node" to those of "space".
3352 __isl_give isl_schedule_node
*isl_schedule_node_align_params(
3353 __isl_take isl_schedule_node
*node
, __isl_take isl_space
*space
)
3355 isl_schedule_tree
*tree
;
3357 tree
= isl_schedule_node_get_tree(node
);
3358 tree
= isl_schedule_tree_align_params(tree
, space
);
3359 node
= isl_schedule_node_graft_tree(node
, tree
);
3364 /* Compute the pullback of schedule node "node"
3365 * by the function represented by "upma".
3366 * In other words, plug in "upma" in the iteration domains
3367 * of schedule node "node".
3368 * We currently do not handle expansion nodes.
3370 * Note that this is only a helper function for
3371 * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency,
3372 * this function should not be called on a single node without also
3373 * calling it on all the other nodes.
3375 __isl_give isl_schedule_node
*isl_schedule_node_pullback_union_pw_multi_aff(
3376 __isl_take isl_schedule_node
*node
,
3377 __isl_take isl_union_pw_multi_aff
*upma
)
3379 isl_schedule_tree
*tree
;
3381 tree
= isl_schedule_node_get_tree(node
);
3382 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, upma
);
3383 node
= isl_schedule_node_graft_tree(node
, tree
);
3388 /* Return the position of the subtree containing "node" among the children
3389 * of "ancestor". "node" is assumed to be a descendant of "ancestor".
3390 * In particular, both nodes should point to the same schedule tree.
3392 * Return -1 on error.
3394 int isl_schedule_node_get_ancestor_child_position(
3395 __isl_keep isl_schedule_node
*node
,
3396 __isl_keep isl_schedule_node
*ancestor
)
3399 isl_schedule_tree
*tree
;
3401 if (!node
|| !ancestor
)
3404 if (node
->schedule
!= ancestor
->schedule
)
3405 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3406 "not a descendant", return -1);
3408 n1
= isl_schedule_node_get_tree_depth(ancestor
);
3409 n2
= isl_schedule_node_get_tree_depth(node
);
3412 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3413 "not a descendant", return -1);
3414 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n1
);
3415 isl_schedule_tree_free(tree
);
3416 if (tree
!= ancestor
->tree
)
3417 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3418 "not a descendant", return -1);
3420 return node
->child_pos
[n1
];
3423 /* Given two nodes that point to the same schedule tree, return their
3424 * closest shared ancestor.
3426 * Since the two nodes point to the same schedule, they share at least
3427 * one ancestor, the root of the schedule. We move down from the root
3428 * to the first ancestor where the respective children have a different
3429 * child position. This is the requested ancestor.
3430 * If there is no ancestor where the children have a different position,
3431 * then one node is an ancestor of the other and then this node is
3432 * the requested ancestor.
3434 __isl_give isl_schedule_node
*isl_schedule_node_get_shared_ancestor(
3435 __isl_keep isl_schedule_node
*node1
,
3436 __isl_keep isl_schedule_node
*node2
)
3440 if (!node1
|| !node2
)
3442 if (node1
->schedule
!= node2
->schedule
)
3443 isl_die(isl_schedule_node_get_ctx(node1
), isl_error_invalid
,
3444 "not part of same schedule", return NULL
);
3445 n1
= isl_schedule_node_get_tree_depth(node1
);
3446 n2
= isl_schedule_node_get_tree_depth(node2
);
3448 return isl_schedule_node_get_shared_ancestor(node2
, node1
);
3450 return isl_schedule_node_copy(node1
);
3451 if (isl_schedule_node_is_equal(node1
, node2
))
3452 return isl_schedule_node_copy(node1
);
3454 for (i
= 0; i
< n1
; ++i
)
3455 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
3458 node1
= isl_schedule_node_copy(node1
);
3459 return isl_schedule_node_ancestor(node1
, n1
- i
);
3462 /* Print "node" to "p".
3464 __isl_give isl_printer
*isl_printer_print_schedule_node(
3465 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
3468 return isl_printer_free(p
);
3469 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
,
3470 isl_schedule_tree_list_n_schedule_tree(node
->ancestors
),
3474 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
3477 isl_printer
*printer
;
3482 ctx
= isl_schedule_node_get_ctx(node
);
3483 printer
= isl_printer_to_file(ctx
, stderr
);
3484 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
3485 printer
= isl_printer_print_schedule_node(printer
, node
);
3487 isl_printer_free(printer
);