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_mark
:
400 case isl_schedule_node_sequence
:
401 case isl_schedule_node_set
:
403 case isl_schedule_node_domain
:
404 filter
= isl_schedule_tree_domain_get_domain(tree
);
405 if (data
->universe_domain
)
406 filter
= isl_union_set_universe(filter
);
407 data
->filter
= filter
;
409 case isl_schedule_node_band
:
410 if (isl_schedule_tree_band_n_member(tree
) == 0)
412 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
413 if (data
->collect_prefix
) {
414 isl_multi_union_pw_aff_free(data
->prefix
);
415 mupa
= isl_multi_union_pw_aff_reset_tuple_id(mupa
,
417 data
->prefix
= isl_multi_union_pw_aff_copy(mupa
);
419 filter
= isl_multi_union_pw_aff_domain(mupa
);
420 filter
= isl_union_set_universe(filter
);
421 data
->filter
= filter
;
423 case isl_schedule_node_filter
:
424 filter
= isl_schedule_tree_filter_get_filter(tree
);
425 if (data
->universe_filter
)
426 filter
= isl_union_set_universe(filter
);
427 data
->filter
= filter
;
431 if ((data
->collect_prefix
&& !data
->prefix
) || !data
->filter
)
434 data
->initialized
= 1;
439 /* Update "data" based on the tree node "tree" in case "data" has
440 * already been initialized.
442 * Return 0 on success and -1 on error.
444 * If "tree" is a domain and data->universe_domain is not set, then
445 * intersect data->filter with the domain.
446 * If "tree" is a filter, then we intersect data->filter with this filter
448 * If "tree" is a band with at least one member and data->collect_prefix
449 * is set, then we extend data->prefix with the band schedule.
451 static int collect_filter_prefix_update(__isl_keep isl_schedule_tree
*tree
,
452 struct isl_schedule_node_get_filter_prefix_data
*data
)
454 enum isl_schedule_node_type type
;
455 isl_multi_union_pw_aff
*mupa
;
456 isl_union_set
*filter
;
458 type
= isl_schedule_tree_get_type(tree
);
460 case isl_schedule_node_error
:
462 case isl_schedule_node_expansion
:
463 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
464 "should be handled by caller", return -1);
465 case isl_schedule_node_context
:
466 case isl_schedule_node_leaf
:
467 case isl_schedule_node_mark
:
468 case isl_schedule_node_sequence
:
469 case isl_schedule_node_set
:
471 case isl_schedule_node_domain
:
472 if (data
->universe_domain
)
474 filter
= isl_schedule_tree_domain_get_domain(tree
);
475 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
477 case isl_schedule_node_band
:
478 if (isl_schedule_tree_band_n_member(tree
) == 0)
480 if (!data
->collect_prefix
)
482 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
483 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(mupa
,
488 case isl_schedule_node_filter
:
489 filter
= isl_schedule_tree_filter_get_filter(tree
);
490 if (data
->universe_filter
)
491 filter
= isl_union_set_universe(filter
);
492 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
501 /* Collect filter and/or prefix information from the first "n"
502 * elements in "list" (which represent the ancestors of a node).
503 * Store the results in "data".
505 * Return 0 on success and -1 on error.
507 * We traverse the list from innermost ancestor (last element)
508 * to outermost ancestor (first element), calling collect_filter_prefix_init
509 * on each node as long as we have not been able to extract any information
510 * yet and collect_filter_prefix_update afterwards.
511 * If we come across an expansion node, then we interrupt the traversal
512 * and call collect_filter_prefix_expansion to restart the traversal
513 * over the remaining ancestors and to combine the results with those
514 * that have already been collected.
515 * On successful return, data->initialized will be set since the outermost
516 * ancestor is a domain node, which always results in an initialization.
518 static int collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
519 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
)
526 for (i
= n
- 1; i
>= 0; --i
) {
527 isl_schedule_tree
*tree
;
528 enum isl_schedule_node_type type
;
531 tree
= isl_schedule_tree_list_get_schedule_tree(list
, i
);
534 type
= isl_schedule_tree_get_type(tree
);
535 if (type
== isl_schedule_node_expansion
)
536 return collect_filter_prefix_expansion(tree
, list
, i
,
538 if (!data
->initialized
)
539 r
= collect_filter_prefix_init(tree
, data
);
541 r
= collect_filter_prefix_update(tree
, data
);
542 isl_schedule_tree_free(tree
);
550 /* Return the concatenation of the partial schedules of all outer band
551 * nodes of "node" interesected with all outer filters
552 * as an isl_multi_union_pw_aff.
554 * If "node" is pointing at the root of the schedule tree, then
555 * there are no domain elements reaching the current node, so
556 * we return an empty result.
558 * We collect all the filters and partial schedules in collect_filter_prefix
559 * and intersect the domain of the combined schedule with the combined filter.
561 __isl_give isl_multi_union_pw_aff
*
562 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(
563 __isl_keep isl_schedule_node
*node
)
567 struct isl_schedule_node_get_filter_prefix_data data
;
572 space
= isl_schedule_get_space(node
->schedule
);
573 space
= isl_space_set_from_params(space
);
574 if (node
->tree
== node
->schedule
->root
)
575 return isl_multi_union_pw_aff_zero(space
);
577 data
.initialized
= 0;
578 data
.universe_domain
= 1;
579 data
.universe_filter
= 0;
580 data
.collect_prefix
= 1;
582 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
584 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
585 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
586 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
588 data
.prefix
= isl_multi_union_pw_aff_intersect_domain(data
.prefix
,
594 /* Return the concatenation of the partial schedules of all outer band
595 * nodes of "node" interesected with all outer filters
596 * as an isl_union_pw_multi_aff.
598 * If "node" is pointing at the root of the schedule tree, then
599 * there are no domain elements reaching the current node, so
600 * we return an empty result.
602 * We collect all the filters and partial schedules in collect_filter_prefix.
603 * The partial schedules are collected as an isl_multi_union_pw_aff.
604 * If this isl_multi_union_pw_aff is zero-dimensional, then it does not
605 * contain any domain information, so we construct the isl_union_pw_multi_aff
606 * result as a zero-dimensional function on the collected filter.
607 * Otherwise, we convert the isl_multi_union_pw_aff to
608 * an isl_multi_union_pw_aff and intersect the domain with the filter.
610 __isl_give isl_union_pw_multi_aff
*
611 isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(
612 __isl_keep isl_schedule_node
*node
)
616 isl_union_pw_multi_aff
*prefix
;
617 struct isl_schedule_node_get_filter_prefix_data data
;
622 space
= isl_schedule_get_space(node
->schedule
);
623 if (node
->tree
== node
->schedule
->root
)
624 return isl_union_pw_multi_aff_empty(space
);
626 space
= isl_space_set_from_params(space
);
627 data
.initialized
= 0;
628 data
.universe_domain
= 1;
629 data
.universe_filter
= 0;
630 data
.collect_prefix
= 1;
632 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
634 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
635 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
636 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
639 isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
) == 0) {
640 isl_multi_union_pw_aff_free(data
.prefix
);
641 prefix
= isl_union_pw_multi_aff_from_domain(data
.filter
);
644 isl_union_pw_multi_aff_from_multi_union_pw_aff(data
.prefix
);
645 prefix
= isl_union_pw_multi_aff_intersect_domain(prefix
,
652 /* Return the concatenation of the partial schedules of all outer band
653 * nodes of "node" interesected with all outer filters
654 * as an isl_union_map.
656 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_union_map(
657 __isl_keep isl_schedule_node
*node
)
659 isl_union_pw_multi_aff
*upma
;
661 upma
= isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(node
);
662 return isl_union_map_from_union_pw_multi_aff(upma
);
665 /* Return the concatenation of the partial schedules of all outer band
666 * nodes of "node" intersected with all outer domain constraints.
668 * Essentially, this functions intersected the domain of the output
669 * of isl_schedule_node_get_prefix_schedule_union_map with the output
670 * of isl_schedule_node_get_domain, except that it only traverses
671 * the ancestors of "node" once.
673 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_relation(
674 __isl_keep isl_schedule_node
*node
)
678 isl_union_map
*prefix
;
679 struct isl_schedule_node_get_filter_prefix_data data
;
684 space
= isl_schedule_get_space(node
->schedule
);
685 if (node
->tree
== node
->schedule
->root
)
686 return isl_union_map_empty(space
);
688 space
= isl_space_set_from_params(space
);
689 data
.initialized
= 0;
690 data
.universe_domain
= 0;
691 data
.universe_filter
= 0;
692 data
.collect_prefix
= 1;
694 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
696 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
697 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
698 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
701 isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
) == 0) {
702 isl_multi_union_pw_aff_free(data
.prefix
);
703 prefix
= isl_union_map_from_domain(data
.filter
);
705 prefix
= isl_union_map_from_multi_union_pw_aff(data
.prefix
);
706 prefix
= isl_union_map_intersect_domain(prefix
, data
.filter
);
712 /* Return the domain elements that reach "node".
714 * If "node" is pointing at the root of the schedule tree, then
715 * there are no domain elements reaching the current node, so
716 * we return an empty result.
718 * Otherwise, we collect all filters reaching the node,
719 * intersected with the root domain in collect_filter_prefix.
721 __isl_give isl_union_set
*isl_schedule_node_get_domain(
722 __isl_keep isl_schedule_node
*node
)
725 struct isl_schedule_node_get_filter_prefix_data data
;
730 if (node
->tree
== node
->schedule
->root
) {
733 space
= isl_schedule_get_space(node
->schedule
);
734 return isl_union_set_empty(space
);
737 data
.initialized
= 0;
738 data
.universe_domain
= 0;
739 data
.universe_filter
= 0;
740 data
.collect_prefix
= 0;
744 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
745 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
746 data
.filter
= isl_union_set_free(data
.filter
);
751 /* Return the union of universe sets of the domain elements that reach "node".
753 * If "node" is pointing at the root of the schedule tree, then
754 * there are no domain elements reaching the current node, so
755 * we return an empty result.
757 * Otherwise, we collect the universes of all filters reaching the node
758 * in collect_filter_prefix.
760 __isl_give isl_union_set
*isl_schedule_node_get_universe_domain(
761 __isl_keep isl_schedule_node
*node
)
764 struct isl_schedule_node_get_filter_prefix_data data
;
769 if (node
->tree
== node
->schedule
->root
) {
772 space
= isl_schedule_get_space(node
->schedule
);
773 return isl_union_set_empty(space
);
776 data
.initialized
= 0;
777 data
.universe_domain
= 1;
778 data
.universe_filter
= 1;
779 data
.collect_prefix
= 0;
783 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
784 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
785 data
.filter
= isl_union_set_free(data
.filter
);
790 /* Return the subtree schedule of "node".
792 * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle
793 * trees that do not contain any schedule information, we first
794 * move down to the first relevant descendant and handle leaves ourselves.
796 * If the subtree rooted at "node" contains any expansion nodes, then
797 * the returned subtree schedule is formulated in terms of the expanded
800 __isl_give isl_union_map
*isl_schedule_node_get_subtree_schedule_union_map(
801 __isl_keep isl_schedule_node
*node
)
803 isl_schedule_tree
*tree
, *leaf
;
806 tree
= isl_schedule_node_get_tree(node
);
807 leaf
= isl_schedule_node_peek_leaf(node
);
808 tree
= isl_schedule_tree_first_schedule_descendant(tree
, leaf
);
812 isl_union_set
*domain
;
813 domain
= isl_schedule_node_get_universe_domain(node
);
814 isl_schedule_tree_free(tree
);
815 return isl_union_map_from_domain(domain
);
818 umap
= isl_schedule_tree_get_subtree_schedule_union_map(tree
);
819 isl_schedule_tree_free(tree
);
823 /* Return the number of ancestors of "node" in its schedule tree.
825 int isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node
*node
)
829 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
832 /* Does "node" have a parent?
834 * That is, does it point to any node of the schedule other than the root?
836 int isl_schedule_node_has_parent(__isl_keep isl_schedule_node
*node
)
840 if (!node
->ancestors
)
843 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) != 0;
846 /* Return the position of "node" among the children of its parent.
848 int isl_schedule_node_get_child_position(__isl_keep isl_schedule_node
*node
)
855 has_parent
= isl_schedule_node_has_parent(node
);
859 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
860 "node has no parent", return -1);
862 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
863 return node
->child_pos
[n
- 1];
866 /* Does the parent (if any) of "node" have any children with a smaller child
867 * position than this one?
869 int isl_schedule_node_has_previous_sibling(__isl_keep isl_schedule_node
*node
)
876 has_parent
= isl_schedule_node_has_parent(node
);
877 if (has_parent
< 0 || !has_parent
)
880 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
882 return node
->child_pos
[n
- 1] > 0;
885 /* Does the parent (if any) of "node" have any children with a greater child
886 * position than this one?
888 int isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node
*node
)
892 isl_schedule_tree
*tree
;
896 has_parent
= isl_schedule_node_has_parent(node
);
897 if (has_parent
< 0 || !has_parent
)
900 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
901 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
904 n_child
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
905 isl_schedule_tree_free(tree
);
907 return node
->child_pos
[n
- 1] + 1 < n_child
;
910 /* Does "node" have any children?
912 * Any node other than the leaf nodes is considered to have at least
913 * one child, even if the corresponding isl_schedule_tree does not
916 int isl_schedule_node_has_children(__isl_keep isl_schedule_node
*node
)
920 return !isl_schedule_tree_is_leaf(node
->tree
);
923 /* Return the number of children of "node"?
925 * Any node other than the leaf nodes is considered to have at least
926 * one child, even if the corresponding isl_schedule_tree does not
927 * have any children. That is, the number of children of "node" is
928 * only zero if its tree is the explicit empty tree. Otherwise,
929 * if the isl_schedule_tree has any children, then it is equal
930 * to the number of children of "node". If it has zero children,
931 * then "node" still has a leaf node as child.
933 int isl_schedule_node_n_children(__isl_keep isl_schedule_node
*node
)
940 if (isl_schedule_tree_is_leaf(node
->tree
))
943 n
= isl_schedule_tree_n_children(node
->tree
);
950 /* Move the "node" pointer to the ancestor of the given generation
951 * of the node it currently points to, where generation 0 is the node
952 * itself and generation 1 is its parent.
954 __isl_give isl_schedule_node
*isl_schedule_node_ancestor(
955 __isl_take isl_schedule_node
*node
, int generation
)
958 isl_schedule_tree
*tree
;
964 n
= isl_schedule_node_get_tree_depth(node
);
966 return isl_schedule_node_free(node
);
967 if (generation
< 0 || generation
> n
)
968 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
969 "generation out of bounds",
970 return isl_schedule_node_free(node
));
971 node
= isl_schedule_node_cow(node
);
975 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
977 isl_schedule_tree_free(node
->tree
);
979 node
->ancestors
= isl_schedule_tree_list_drop(node
->ancestors
,
980 n
- generation
, generation
);
981 if (!node
->ancestors
|| !node
->tree
)
982 return isl_schedule_node_free(node
);
987 /* Move the "node" pointer to the parent of the node it currently points to.
989 __isl_give isl_schedule_node
*isl_schedule_node_parent(
990 __isl_take isl_schedule_node
*node
)
994 if (!isl_schedule_node_has_parent(node
))
995 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
996 "node has no parent",
997 return isl_schedule_node_free(node
));
998 return isl_schedule_node_ancestor(node
, 1);
1001 /* Move the "node" pointer to the root of its schedule tree.
1003 __isl_give isl_schedule_node
*isl_schedule_node_root(
1004 __isl_take isl_schedule_node
*node
)
1010 n
= isl_schedule_node_get_tree_depth(node
);
1012 return isl_schedule_node_free(node
);
1013 return isl_schedule_node_ancestor(node
, n
);
1016 /* Move the "node" pointer to the child at position "pos" of the node
1017 * it currently points to.
1019 __isl_give isl_schedule_node
*isl_schedule_node_child(
1020 __isl_take isl_schedule_node
*node
, int pos
)
1024 isl_schedule_tree
*tree
;
1027 node
= isl_schedule_node_cow(node
);
1030 if (!isl_schedule_node_has_children(node
))
1031 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1032 "node has no children",
1033 return isl_schedule_node_free(node
));
1035 ctx
= isl_schedule_node_get_ctx(node
);
1036 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1037 child_pos
= isl_realloc_array(ctx
, node
->child_pos
, int, n
+ 1);
1039 return isl_schedule_node_free(node
);
1040 node
->child_pos
= child_pos
;
1041 node
->child_pos
[n
] = pos
;
1043 node
->ancestors
= isl_schedule_tree_list_add(node
->ancestors
,
1044 isl_schedule_tree_copy(node
->tree
));
1046 if (isl_schedule_tree_has_children(tree
))
1047 tree
= isl_schedule_tree_get_child(tree
, pos
);
1049 tree
= isl_schedule_node_get_leaf(node
);
1050 isl_schedule_tree_free(node
->tree
);
1053 if (!node
->tree
|| !node
->ancestors
)
1054 return isl_schedule_node_free(node
);
1059 /* Move the "node" pointer to the first child of the node
1060 * it currently points to.
1062 __isl_give isl_schedule_node
*isl_schedule_node_first_child(
1063 __isl_take isl_schedule_node
*node
)
1065 return isl_schedule_node_child(node
, 0);
1068 /* Move the "node" pointer to the child of this node's parent in
1069 * the previous child position.
1071 __isl_give isl_schedule_node
*isl_schedule_node_previous_sibling(
1072 __isl_take isl_schedule_node
*node
)
1075 isl_schedule_tree
*parent
, *tree
;
1077 node
= isl_schedule_node_cow(node
);
1080 if (!isl_schedule_node_has_previous_sibling(node
))
1081 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1082 "node has no previous sibling",
1083 return isl_schedule_node_free(node
));
1085 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1086 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1089 return isl_schedule_node_free(node
);
1090 node
->child_pos
[n
- 1]--;
1091 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1092 node
->child_pos
[n
- 1]);
1093 isl_schedule_tree_free(parent
);
1095 return isl_schedule_node_free(node
);
1096 isl_schedule_tree_free(node
->tree
);
1102 /* Move the "node" pointer to the child of this node's parent in
1103 * the next child position.
1105 __isl_give isl_schedule_node
*isl_schedule_node_next_sibling(
1106 __isl_take isl_schedule_node
*node
)
1109 isl_schedule_tree
*parent
, *tree
;
1111 node
= isl_schedule_node_cow(node
);
1114 if (!isl_schedule_node_has_next_sibling(node
))
1115 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1116 "node has no next sibling",
1117 return isl_schedule_node_free(node
));
1119 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1120 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1123 return isl_schedule_node_free(node
);
1124 node
->child_pos
[n
- 1]++;
1125 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1126 node
->child_pos
[n
- 1]);
1127 isl_schedule_tree_free(parent
);
1129 return isl_schedule_node_free(node
);
1130 isl_schedule_tree_free(node
->tree
);
1136 /* Return a copy to the child at position "pos" of "node".
1138 __isl_give isl_schedule_node
*isl_schedule_node_get_child(
1139 __isl_keep isl_schedule_node
*node
, int pos
)
1141 return isl_schedule_node_child(isl_schedule_node_copy(node
), pos
);
1144 /* Traverse the descendant of "node" in depth-first order, including
1145 * "node" itself. Call "enter" whenever a node is entered and "leave"
1146 * whenever a node is left. The callback "enter" is responsible
1147 * for moving to the deepest initial subtree of its argument that
1148 * should be traversed.
1150 static __isl_give isl_schedule_node
*traverse(
1151 __isl_take isl_schedule_node
*node
,
1152 __isl_give isl_schedule_node
*(*enter
)(
1153 __isl_take isl_schedule_node
*node
, void *user
),
1154 __isl_give isl_schedule_node
*(*leave
)(
1155 __isl_take isl_schedule_node
*node
, void *user
),
1163 depth
= isl_schedule_node_get_tree_depth(node
);
1165 node
= enter(node
, user
);
1166 node
= leave(node
, user
);
1167 while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
&&
1168 !isl_schedule_node_has_next_sibling(node
)) {
1169 node
= isl_schedule_node_parent(node
);
1170 node
= leave(node
, user
);
1172 if (node
&& isl_schedule_node_get_tree_depth(node
) > depth
)
1173 node
= isl_schedule_node_next_sibling(node
);
1174 } while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
);
1179 /* Internal data structure for isl_schedule_node_foreach_descendant.
1181 * "fn" is the user-specified callback function.
1182 * "user" is the user-specified argument for the callback.
1184 struct isl_schedule_node_preorder_data
{
1185 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
);
1189 /* Callback for "traverse" to enter a node and to move
1190 * to the deepest initial subtree that should be traversed
1191 * for use in a preorder visit.
1193 * If the user callback returns a negative value, then we abort
1194 * the traversal. If this callback returns zero, then we skip
1195 * the subtree rooted at the current node. Otherwise, we move
1196 * down to the first child and repeat the process until a leaf
1199 static __isl_give isl_schedule_node
*preorder_enter(
1200 __isl_take isl_schedule_node
*node
, void *user
)
1202 struct isl_schedule_node_preorder_data
*data
= user
;
1210 r
= data
->fn(node
, data
->user
);
1212 return isl_schedule_node_free(node
);
1215 } while (isl_schedule_node_has_children(node
) &&
1216 (node
= isl_schedule_node_first_child(node
)) != NULL
);
1221 /* Callback for "traverse" to leave a node
1222 * for use in a preorder visit.
1223 * Since we already visited the node when we entered it,
1224 * we do not need to do anything here.
1226 static __isl_give isl_schedule_node
*preorder_leave(
1227 __isl_take isl_schedule_node
*node
, void *user
)
1232 /* Traverse the descendants of "node" (including the node itself)
1233 * in depth first preorder.
1235 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1236 * If "fn" returns 0 on any of the nodes, then the subtree rooted
1237 * at that node is skipped.
1239 * Return 0 on success and -1 on failure.
1241 int isl_schedule_node_foreach_descendant(__isl_keep isl_schedule_node
*node
,
1242 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
), void *user
)
1244 struct isl_schedule_node_preorder_data data
= { fn
, user
};
1246 node
= isl_schedule_node_copy(node
);
1247 node
= traverse(node
, &preorder_enter
, &preorder_leave
, &data
);
1248 isl_schedule_node_free(node
);
1250 return node
? 0 : -1;
1253 /* Internal data structure for isl_schedule_node_map_descendant.
1255 * "fn" is the user-specified callback function.
1256 * "user" is the user-specified argument for the callback.
1258 struct isl_schedule_node_postorder_data
{
1259 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1264 /* Callback for "traverse" to enter a node and to move
1265 * to the deepest initial subtree that should be traversed
1266 * for use in a postorder visit.
1268 * Since we are performing a postorder visit, we only need
1269 * to move to the deepest initial leaf here.
1271 static __isl_give isl_schedule_node
*postorder_enter(
1272 __isl_take isl_schedule_node
*node
, void *user
)
1274 while (node
&& isl_schedule_node_has_children(node
))
1275 node
= isl_schedule_node_first_child(node
);
1280 /* Callback for "traverse" to leave a node
1281 * for use in a postorder visit.
1283 * Since we are performing a postorder visit, we need
1284 * to call the user callback here.
1286 static __isl_give isl_schedule_node
*postorder_leave(
1287 __isl_take isl_schedule_node
*node
, void *user
)
1289 struct isl_schedule_node_postorder_data
*data
= user
;
1291 return data
->fn(node
, data
->user
);
1294 /* Traverse the descendants of "node" (including the node itself)
1295 * in depth first postorder, allowing the user to modify the visited node.
1296 * The traversal continues from the node returned by the callback function.
1297 * It is the responsibility of the user to ensure that this does not
1298 * lead to an infinite loop. It is safest to always return a pointer
1299 * to the same position (same ancestors and child positions) as the input node.
1301 __isl_give isl_schedule_node
*isl_schedule_node_map_descendant(
1302 __isl_take isl_schedule_node
*node
,
1303 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1304 void *user
), void *user
)
1306 struct isl_schedule_node_postorder_data data
= { fn
, user
};
1308 return traverse(node
, &postorder_enter
, &postorder_leave
, &data
);
1311 /* Traverse the ancestors of "node" from the root down to and including
1312 * the parent of "node", calling "fn" on each of them.
1314 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1316 * Return 0 on success and -1 on failure.
1318 int isl_schedule_node_foreach_ancestor_top_down(
1319 __isl_keep isl_schedule_node
*node
,
1320 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
), void *user
)
1327 n
= isl_schedule_node_get_tree_depth(node
);
1328 for (i
= 0; i
< n
; ++i
) {
1329 isl_schedule_node
*ancestor
;
1332 ancestor
= isl_schedule_node_copy(node
);
1333 ancestor
= isl_schedule_node_ancestor(ancestor
, n
- i
);
1334 r
= fn(ancestor
, user
);
1335 isl_schedule_node_free(ancestor
);
1343 /* Is any node in the subtree rooted at "node" anchored?
1344 * That is, do any of these nodes reference the outer band nodes?
1346 int isl_schedule_node_is_subtree_anchored(__isl_keep isl_schedule_node
*node
)
1350 return isl_schedule_tree_is_subtree_anchored(node
->tree
);
1353 /* Return the number of members in the given band node.
1355 unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node
*node
)
1357 return node
? isl_schedule_tree_band_n_member(node
->tree
) : 0;
1360 /* Is the band member at position "pos" of the band node "node"
1361 * marked coincident?
1363 int isl_schedule_node_band_member_get_coincident(
1364 __isl_keep isl_schedule_node
*node
, int pos
)
1368 return isl_schedule_tree_band_member_get_coincident(node
->tree
, pos
);
1371 /* Mark the band member at position "pos" the band node "node"
1372 * as being coincident or not according to "coincident".
1374 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_coincident(
1375 __isl_take isl_schedule_node
*node
, int pos
, int coincident
)
1378 isl_schedule_tree
*tree
;
1382 c
= isl_schedule_node_band_member_get_coincident(node
, pos
);
1383 if (c
== coincident
)
1386 tree
= isl_schedule_tree_copy(node
->tree
);
1387 tree
= isl_schedule_tree_band_member_set_coincident(tree
, pos
,
1389 node
= isl_schedule_node_graft_tree(node
, tree
);
1394 /* Is the band node "node" marked permutable?
1396 int isl_schedule_node_band_get_permutable(__isl_keep isl_schedule_node
*node
)
1401 return isl_schedule_tree_band_get_permutable(node
->tree
);
1404 /* Mark the band node "node" permutable or not according to "permutable"?
1406 __isl_give isl_schedule_node
*isl_schedule_node_band_set_permutable(
1407 __isl_take isl_schedule_node
*node
, int permutable
)
1409 isl_schedule_tree
*tree
;
1413 if (isl_schedule_node_band_get_permutable(node
) == permutable
)
1416 tree
= isl_schedule_tree_copy(node
->tree
);
1417 tree
= isl_schedule_tree_band_set_permutable(tree
, permutable
);
1418 node
= isl_schedule_node_graft_tree(node
, tree
);
1423 /* Return the schedule space of the band node.
1425 __isl_give isl_space
*isl_schedule_node_band_get_space(
1426 __isl_keep isl_schedule_node
*node
)
1431 return isl_schedule_tree_band_get_space(node
->tree
);
1434 /* Return the schedule of the band node in isolation.
1436 __isl_give isl_multi_union_pw_aff
*isl_schedule_node_band_get_partial_schedule(
1437 __isl_keep isl_schedule_node
*node
)
1442 return isl_schedule_tree_band_get_partial_schedule(node
->tree
);
1445 /* Return the schedule of the band node in isolation in the form of
1448 * If the band does not have any members, then we construct a universe map
1449 * with the universe of the domain elements reaching the node as domain.
1450 * Otherwise, we extract an isl_multi_union_pw_aff representation and
1451 * convert that to an isl_union_map.
1453 __isl_give isl_union_map
*isl_schedule_node_band_get_partial_schedule_union_map(
1454 __isl_keep isl_schedule_node
*node
)
1456 isl_multi_union_pw_aff
*mupa
;
1461 if (isl_schedule_node_get_type(node
) != isl_schedule_node_band
)
1462 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1463 "not a band node", return NULL
);
1464 if (isl_schedule_node_band_n_member(node
) == 0) {
1465 isl_union_set
*domain
;
1467 domain
= isl_schedule_node_get_universe_domain(node
);
1468 return isl_union_map_from_domain(domain
);
1471 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
1472 return isl_union_map_from_multi_union_pw_aff(mupa
);
1475 /* Return the loop AST generation type for the band member of band node "node"
1476 * at position "pos".
1478 enum isl_ast_loop_type
isl_schedule_node_band_member_get_ast_loop_type(
1479 __isl_keep isl_schedule_node
*node
, int pos
)
1482 return isl_ast_loop_error
;
1484 return isl_schedule_tree_band_member_get_ast_loop_type(node
->tree
, pos
);
1487 /* Set the loop AST generation type for the band member of band node "node"
1488 * at position "pos" to "type".
1490 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_ast_loop_type(
1491 __isl_take isl_schedule_node
*node
, int pos
,
1492 enum isl_ast_loop_type type
)
1494 isl_schedule_tree
*tree
;
1499 tree
= isl_schedule_tree_copy(node
->tree
);
1500 tree
= isl_schedule_tree_band_member_set_ast_loop_type(tree
, pos
, type
);
1501 return isl_schedule_node_graft_tree(node
, tree
);
1504 /* Return the loop AST generation type for the band member of band node "node"
1505 * at position "pos" for the isolated part.
1507 enum isl_ast_loop_type
isl_schedule_node_band_member_get_isolate_ast_loop_type(
1508 __isl_keep isl_schedule_node
*node
, int pos
)
1511 return isl_ast_loop_error
;
1513 return isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1517 /* Set the loop AST generation type for the band member of band node "node"
1518 * at position "pos" for the isolated part to "type".
1520 __isl_give isl_schedule_node
*
1521 isl_schedule_node_band_member_set_isolate_ast_loop_type(
1522 __isl_take isl_schedule_node
*node
, int pos
,
1523 enum isl_ast_loop_type type
)
1525 isl_schedule_tree
*tree
;
1530 tree
= isl_schedule_tree_copy(node
->tree
);
1531 tree
= isl_schedule_tree_band_member_set_isolate_ast_loop_type(tree
,
1533 return isl_schedule_node_graft_tree(node
, tree
);
1536 /* Return the AST build options associated to band node "node".
1538 __isl_give isl_union_set
*isl_schedule_node_band_get_ast_build_options(
1539 __isl_keep isl_schedule_node
*node
)
1544 return isl_schedule_tree_band_get_ast_build_options(node
->tree
);
1547 /* Replace the AST build options associated to band node "node" by "options".
1549 __isl_give isl_schedule_node
*isl_schedule_node_band_set_ast_build_options(
1550 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*options
)
1552 isl_schedule_tree
*tree
;
1554 if (!node
|| !options
)
1557 tree
= isl_schedule_tree_copy(node
->tree
);
1558 tree
= isl_schedule_tree_band_set_ast_build_options(tree
, options
);
1559 return isl_schedule_node_graft_tree(node
, tree
);
1561 isl_schedule_node_free(node
);
1562 isl_union_set_free(options
);
1566 /* Make sure that that spaces of "node" and "mv" are the same.
1567 * Return -1 on error, reporting the error to the user.
1569 static int check_space_multi_val(__isl_keep isl_schedule_node
*node
,
1570 __isl_keep isl_multi_val
*mv
)
1572 isl_space
*node_space
, *mv_space
;
1575 node_space
= isl_schedule_node_band_get_space(node
);
1576 mv_space
= isl_multi_val_get_space(mv
);
1577 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1578 mv_space
, isl_dim_set
);
1579 isl_space_free(mv_space
);
1580 isl_space_free(node_space
);
1584 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1585 "spaces don't match", return -1);
1590 /* Multiply the partial schedule of the band node "node"
1591 * with the factors in "mv".
1593 __isl_give isl_schedule_node
*isl_schedule_node_band_scale(
1594 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1596 isl_schedule_tree
*tree
;
1601 if (check_space_multi_val(node
, mv
) < 0)
1603 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1607 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1608 "cannot scale band node with anchored subtree",
1611 tree
= isl_schedule_node_get_tree(node
);
1612 tree
= isl_schedule_tree_band_scale(tree
, mv
);
1613 return isl_schedule_node_graft_tree(node
, tree
);
1615 isl_multi_val_free(mv
);
1616 isl_schedule_node_free(node
);
1620 /* Divide the partial schedule of the band node "node"
1621 * by the factors in "mv".
1623 __isl_give isl_schedule_node
*isl_schedule_node_band_scale_down(
1624 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1626 isl_schedule_tree
*tree
;
1631 if (check_space_multi_val(node
, mv
) < 0)
1633 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1637 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1638 "cannot scale down band node with anchored subtree",
1641 tree
= isl_schedule_node_get_tree(node
);
1642 tree
= isl_schedule_tree_band_scale_down(tree
, mv
);
1643 return isl_schedule_node_graft_tree(node
, tree
);
1645 isl_multi_val_free(mv
);
1646 isl_schedule_node_free(node
);
1650 /* Tile "node" with tile sizes "sizes".
1652 * The current node is replaced by two nested nodes corresponding
1653 * to the tile dimensions and the point dimensions.
1655 * Return a pointer to the outer (tile) node.
1657 * If any of the descendants of "node" depend on the set of outer band nodes,
1658 * then we refuse to tile the node.
1660 * If the scale tile loops option is set, then the tile loops
1661 * are scaled by the tile sizes. If the shift point loops option is set,
1662 * then the point loops are shifted to start at zero.
1663 * In particular, these options affect the tile and point loop schedules
1666 * scale shift original tile point
1668 * 0 0 i floor(i/s) i
1669 * 1 0 i s * floor(i/s) i
1670 * 0 1 i floor(i/s) i - s * floor(i/s)
1671 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1673 __isl_give isl_schedule_node
*isl_schedule_node_band_tile(
1674 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*sizes
)
1676 isl_schedule_tree
*tree
;
1679 if (!node
|| !sizes
)
1681 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1685 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1686 "cannot tile band node with anchored subtree",
1689 if (check_space_multi_val(node
, sizes
) < 0)
1692 tree
= isl_schedule_node_get_tree(node
);
1693 tree
= isl_schedule_tree_band_tile(tree
, sizes
);
1694 return isl_schedule_node_graft_tree(node
, tree
);
1696 isl_multi_val_free(sizes
);
1697 isl_schedule_node_free(node
);
1701 /* Move the band node "node" down to all the leaves in the subtree
1703 * Return a pointer to the node in the resulting tree that is in the same
1704 * position as the node pointed to by "node" in the original tree.
1706 * If the node only has a leaf child, then nothing needs to be done.
1707 * Otherwise, the child of the node is removed and the result is
1708 * appended to all the leaves in the subtree rooted at the original child.
1709 * The original node is then replaced by the result of this operation.
1711 * If any of the nodes in the subtree rooted at "node" depend on
1712 * the set of outer band nodes then we refuse to sink the band node.
1714 __isl_give isl_schedule_node
*isl_schedule_node_band_sink(
1715 __isl_take isl_schedule_node
*node
)
1717 enum isl_schedule_node_type type
;
1718 isl_schedule_tree
*tree
, *child
;
1724 type
= isl_schedule_node_get_type(node
);
1725 if (type
!= isl_schedule_node_band
)
1726 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1727 "not a band node", isl_schedule_node_free(node
));
1728 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1730 return isl_schedule_node_free(node
);
1732 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1733 "cannot sink band node in anchored subtree",
1734 isl_schedule_node_free(node
));
1735 if (isl_schedule_tree_n_children(node
->tree
) == 0)
1738 tree
= isl_schedule_node_get_tree(node
);
1739 child
= isl_schedule_tree_get_child(tree
, 0);
1740 tree
= isl_schedule_tree_reset_children(tree
);
1741 tree
= isl_schedule_tree_append_to_leaves(child
, tree
);
1743 return isl_schedule_node_graft_tree(node
, tree
);
1746 /* Split "node" into two nested band nodes, one with the first "pos"
1747 * dimensions and one with the remaining dimensions.
1748 * The schedules of the two band nodes live in anonymous spaces.
1750 __isl_give isl_schedule_node
*isl_schedule_node_band_split(
1751 __isl_take isl_schedule_node
*node
, int pos
)
1753 isl_schedule_tree
*tree
;
1755 tree
= isl_schedule_node_get_tree(node
);
1756 tree
= isl_schedule_tree_band_split(tree
, pos
);
1757 return isl_schedule_node_graft_tree(node
, tree
);
1760 /* Return the context of the context node "node".
1762 __isl_give isl_set
*isl_schedule_node_context_get_context(
1763 __isl_keep isl_schedule_node
*node
)
1768 return isl_schedule_tree_context_get_context(node
->tree
);
1771 /* Return the domain of the domain node "node".
1773 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
1774 __isl_keep isl_schedule_node
*node
)
1779 return isl_schedule_tree_domain_get_domain(node
->tree
);
1782 /* Return the expansion map of expansion node "node".
1784 __isl_give isl_union_map
*isl_schedule_node_expansion_get_expansion(
1785 __isl_keep isl_schedule_node
*node
)
1790 return isl_schedule_tree_expansion_get_expansion(node
->tree
);
1793 /* Return the contraction of expansion node "node".
1795 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_expansion_get_contraction(
1796 __isl_keep isl_schedule_node
*node
)
1801 return isl_schedule_tree_expansion_get_contraction(node
->tree
);
1804 /* Replace the contraction and the expansion of the expansion node "node"
1805 * by "contraction" and "expansion".
1807 __isl_give isl_schedule_node
*
1808 isl_schedule_node_expansion_set_contraction_and_expansion(
1809 __isl_take isl_schedule_node
*node
,
1810 __isl_take isl_union_pw_multi_aff
*contraction
,
1811 __isl_take isl_union_map
*expansion
)
1813 isl_schedule_tree
*tree
;
1815 if (!node
|| !contraction
|| !expansion
)
1818 tree
= isl_schedule_tree_copy(node
->tree
);
1819 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
1820 contraction
, expansion
);
1821 return isl_schedule_node_graft_tree(node
, tree
);
1823 isl_schedule_node_free(node
);
1824 isl_union_pw_multi_aff_free(contraction
);
1825 isl_union_map_free(expansion
);
1829 /* Return the filter of the filter node "node".
1831 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
1832 __isl_keep isl_schedule_node
*node
)
1837 return isl_schedule_tree_filter_get_filter(node
->tree
);
1840 /* Replace the filter of filter node "node" by "filter".
1842 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
1843 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
1845 isl_schedule_tree
*tree
;
1847 if (!node
|| !filter
)
1850 tree
= isl_schedule_tree_copy(node
->tree
);
1851 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
1852 return isl_schedule_node_graft_tree(node
, tree
);
1854 isl_schedule_node_free(node
);
1855 isl_union_set_free(filter
);
1859 /* Return the mark identifier of the mark node "node".
1861 __isl_give isl_id
*isl_schedule_node_mark_get_id(
1862 __isl_keep isl_schedule_node
*node
)
1867 return isl_schedule_tree_mark_get_id(node
->tree
);
1870 /* Update the ancestors of "node" to point to the tree that "node"
1872 * That is, replace the child in the original parent that corresponds
1873 * to the current tree position by node->tree and continue updating
1874 * the ancestors in the same way until the root is reached.
1876 * If "fn" is not NULL, then it is called on each ancestor as we move up
1877 * the tree so that it can modify the ancestor before it is added
1878 * to the list of ancestors of the modified node.
1879 * The additional "pos" argument records the position
1880 * of the "tree" argument in the original schedule tree.
1882 * If "node" originally points to a leaf of the schedule tree, then make sure
1883 * that in the end it points to a leaf in the updated schedule tree.
1885 static __isl_give isl_schedule_node
*update_ancestors(
1886 __isl_take isl_schedule_node
*node
,
1887 __isl_give isl_schedule_tree
*(*fn
)(__isl_take isl_schedule_tree
*tree
,
1888 __isl_keep isl_schedule_node
*pos
, void *user
), void *user
)
1893 isl_schedule_tree
*tree
;
1894 isl_schedule_node
*pos
= NULL
;
1897 pos
= isl_schedule_node_copy(node
);
1899 node
= isl_schedule_node_cow(node
);
1901 return isl_schedule_node_free(pos
);
1903 ctx
= isl_schedule_node_get_ctx(node
);
1904 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1905 tree
= isl_schedule_tree_copy(node
->tree
);
1907 for (i
= n
- 1; i
>= 0; --i
) {
1908 isl_schedule_tree
*parent
;
1910 parent
= isl_schedule_tree_list_get_schedule_tree(
1911 node
->ancestors
, i
);
1912 parent
= isl_schedule_tree_replace_child(parent
,
1913 node
->child_pos
[i
], tree
);
1915 pos
= isl_schedule_node_parent(pos
);
1916 parent
= fn(parent
, pos
, user
);
1918 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
1919 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
1925 isl_schedule_node_free(pos
);
1927 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
1928 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
1930 isl_schedule_tree_free(node
->tree
);
1931 node
->tree
= isl_schedule_node_get_leaf(node
);
1934 if (!node
->schedule
|| !node
->ancestors
)
1935 return isl_schedule_node_free(node
);
1940 /* Replace the subtree that "pos" points to by "tree", updating
1941 * the ancestors to maintain a consistent state.
1943 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
1944 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
1948 if (pos
->tree
== tree
) {
1949 isl_schedule_tree_free(tree
);
1953 pos
= isl_schedule_node_cow(pos
);
1957 isl_schedule_tree_free(pos
->tree
);
1960 return update_ancestors(pos
, NULL
, NULL
);
1962 isl_schedule_node_free(pos
);
1963 isl_schedule_tree_free(tree
);
1967 /* Make sure we can insert a node between "node" and its parent.
1968 * Return -1 on error, reporting the reason why we cannot insert a node.
1970 static int check_insert(__isl_keep isl_schedule_node
*node
)
1973 enum isl_schedule_node_type type
;
1975 has_parent
= isl_schedule_node_has_parent(node
);
1979 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1980 "cannot insert node outside of root", return -1);
1982 type
= isl_schedule_node_get_parent_type(node
);
1983 if (type
== isl_schedule_node_error
)
1985 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
1986 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1987 "cannot insert node between set or sequence node "
1988 "and its filter children", return -1);
1993 /* Insert a band node with partial schedule "mupa" between "node" and
1995 * Return a pointer to the new band node.
1997 * If any of the nodes in the subtree rooted at "node" depend on
1998 * the set of outer band nodes then we refuse to insert the band node.
2000 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
2001 __isl_take isl_schedule_node
*node
,
2002 __isl_take isl_multi_union_pw_aff
*mupa
)
2005 isl_schedule_band
*band
;
2006 isl_schedule_tree
*tree
;
2008 if (check_insert(node
) < 0)
2009 node
= isl_schedule_node_free(node
);
2010 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2014 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2015 "cannot insert band node in anchored subtree",
2018 tree
= isl_schedule_node_get_tree(node
);
2019 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
2020 tree
= isl_schedule_tree_insert_band(tree
, band
);
2021 node
= isl_schedule_node_graft_tree(node
, tree
);
2025 isl_schedule_node_free(node
);
2026 isl_multi_union_pw_aff_free(mupa
);
2030 /* Insert a context node with context "context" between "node" and its parent.
2031 * Return a pointer to the new context node.
2033 __isl_give isl_schedule_node
*isl_schedule_node_insert_context(
2034 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
2036 isl_schedule_tree
*tree
;
2038 if (check_insert(node
) < 0)
2039 node
= isl_schedule_node_free(node
);
2041 tree
= isl_schedule_node_get_tree(node
);
2042 tree
= isl_schedule_tree_insert_context(tree
, context
);
2043 node
= isl_schedule_node_graft_tree(node
, tree
);
2048 /* Insert an expansion node with the given "contraction" and "expansion"
2049 * between "node" and its parent.
2050 * Return a pointer to the new expansion node.
2052 * Typically the domain and range spaces of the expansion are different.
2053 * This means that only one of them can refer to the current domain space
2054 * in a consistent tree. It is up to the caller to ensure that the tree
2055 * returns to a consistent state.
2057 __isl_give isl_schedule_node
*isl_schedule_node_insert_expansion(
2058 __isl_take isl_schedule_node
*node
,
2059 __isl_take isl_union_pw_multi_aff
*contraction
,
2060 __isl_take isl_union_map
*expansion
)
2062 isl_schedule_tree
*tree
;
2064 if (check_insert(node
) < 0)
2065 node
= isl_schedule_node_free(node
);
2067 tree
= isl_schedule_node_get_tree(node
);
2068 tree
= isl_schedule_tree_insert_expansion(tree
, contraction
, expansion
);
2069 node
= isl_schedule_node_graft_tree(node
, tree
);
2074 /* Insert a filter node with filter "filter" between "node" and its parent.
2075 * Return a pointer to the new filter node.
2077 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
2078 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2080 isl_schedule_tree
*tree
;
2082 if (check_insert(node
) < 0)
2083 node
= isl_schedule_node_free(node
);
2085 tree
= isl_schedule_node_get_tree(node
);
2086 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2087 node
= isl_schedule_node_graft_tree(node
, tree
);
2092 /* Insert a mark node with mark identifier "mark" between "node" and
2094 * Return a pointer to the new mark node.
2096 __isl_give isl_schedule_node
*isl_schedule_node_insert_mark(
2097 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*mark
)
2099 isl_schedule_tree
*tree
;
2101 if (check_insert(node
) < 0)
2102 node
= isl_schedule_node_free(node
);
2104 tree
= isl_schedule_node_get_tree(node
);
2105 tree
= isl_schedule_tree_insert_mark(tree
, mark
);
2106 node
= isl_schedule_node_graft_tree(node
, tree
);
2111 /* Attach the current subtree of "node" to a sequence of filter tree nodes
2112 * with filters described by "filters", attach this sequence
2113 * of filter tree nodes as children to a new tree of type "type" and
2114 * replace the original subtree of "node" by this new tree.
2116 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
2117 __isl_take isl_schedule_node
*node
,
2118 enum isl_schedule_node_type type
,
2119 __isl_take isl_union_set_list
*filters
)
2123 isl_schedule_tree
*tree
;
2124 isl_schedule_tree_list
*list
;
2126 if (check_insert(node
) < 0)
2127 node
= isl_schedule_node_free(node
);
2129 if (!node
|| !filters
)
2132 ctx
= isl_schedule_node_get_ctx(node
);
2133 n
= isl_union_set_list_n_union_set(filters
);
2134 list
= isl_schedule_tree_list_alloc(ctx
, n
);
2135 for (i
= 0; i
< n
; ++i
) {
2136 isl_schedule_tree
*tree
;
2137 isl_union_set
*filter
;
2139 tree
= isl_schedule_node_get_tree(node
);
2140 filter
= isl_union_set_list_get_union_set(filters
, i
);
2141 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2142 list
= isl_schedule_tree_list_add(list
, tree
);
2144 tree
= isl_schedule_tree_from_children(type
, list
);
2145 node
= isl_schedule_node_graft_tree(node
, tree
);
2147 isl_union_set_list_free(filters
);
2150 isl_union_set_list_free(filters
);
2151 isl_schedule_node_free(node
);
2155 /* Insert a sequence node with child filters "filters" between "node" and
2156 * its parent. That is, the tree that "node" points to is attached
2157 * to each of the child nodes of the filter nodes.
2158 * Return a pointer to the new sequence node.
2160 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
2161 __isl_take isl_schedule_node
*node
,
2162 __isl_take isl_union_set_list
*filters
)
2164 return isl_schedule_node_insert_children(node
,
2165 isl_schedule_node_sequence
, filters
);
2168 /* Insert a set node with child filters "filters" between "node" and
2169 * its parent. That is, the tree that "node" points to is attached
2170 * to each of the child nodes of the filter nodes.
2171 * Return a pointer to the new set node.
2173 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
2174 __isl_take isl_schedule_node
*node
,
2175 __isl_take isl_union_set_list
*filters
)
2177 return isl_schedule_node_insert_children(node
,
2178 isl_schedule_node_set
, filters
);
2181 /* Remove "node" from its schedule tree and return a pointer
2182 * to the leaf at the same position in the updated schedule tree.
2184 * It is not allowed to remove the root of a schedule tree or
2185 * a child of a set or sequence node.
2187 __isl_give isl_schedule_node
*isl_schedule_node_cut(
2188 __isl_take isl_schedule_node
*node
)
2190 isl_schedule_tree
*leaf
;
2191 enum isl_schedule_node_type parent_type
;
2195 if (!isl_schedule_node_has_parent(node
))
2196 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2197 "cannot cut root", return isl_schedule_node_free(node
));
2199 parent_type
= isl_schedule_node_get_parent_type(node
);
2200 if (parent_type
== isl_schedule_node_set
||
2201 parent_type
== isl_schedule_node_sequence
)
2202 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2203 "cannot cut child of set or sequence",
2204 return isl_schedule_node_free(node
));
2206 leaf
= isl_schedule_node_get_leaf(node
);
2207 return isl_schedule_node_graft_tree(node
, leaf
);
2210 /* Remove a single node from the schedule tree, attaching the child
2211 * of "node" directly to its parent.
2212 * Return a pointer to this former child or to the leaf the position
2213 * of the original node if there was no child.
2214 * It is not allowed to remove the root of a schedule tree,
2215 * a set or sequence node, a child of a set or sequence node or
2216 * a band node with an anchored subtree.
2218 __isl_give isl_schedule_node
*isl_schedule_node_delete(
2219 __isl_take isl_schedule_node
*node
)
2222 isl_schedule_tree
*tree
;
2223 enum isl_schedule_node_type type
;
2228 if (isl_schedule_node_get_tree_depth(node
) == 0)
2229 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2230 "cannot delete root node",
2231 return isl_schedule_node_free(node
));
2232 n
= isl_schedule_node_n_children(node
);
2234 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2235 "can only delete node with a single child",
2236 return isl_schedule_node_free(node
));
2237 type
= isl_schedule_node_get_parent_type(node
);
2238 if (type
== isl_schedule_node_sequence
|| type
== isl_schedule_node_set
)
2239 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2240 "cannot delete child of set or sequence",
2241 return isl_schedule_node_free(node
));
2242 if (isl_schedule_node_get_type(node
) == isl_schedule_node_band
) {
2245 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2247 return isl_schedule_node_free(node
);
2249 isl_die(isl_schedule_node_get_ctx(node
),
2251 "cannot delete band node with anchored subtree",
2252 return isl_schedule_node_free(node
));
2255 tree
= isl_schedule_node_get_tree(node
);
2256 if (!tree
|| isl_schedule_tree_has_children(tree
)) {
2257 tree
= isl_schedule_tree_child(tree
, 0);
2259 isl_schedule_tree_free(tree
);
2260 tree
= isl_schedule_node_get_leaf(node
);
2262 node
= isl_schedule_node_graft_tree(node
, tree
);
2267 /* Internal data structure for the group_ancestor callback.
2269 * If "finished" is set, then we no longer need to modify
2270 * any further ancestors.
2272 * "contraction" and "expansion" represent the expansion
2273 * that reflects the grouping.
2275 * "domain" contains the domain elements that reach the position
2276 * where the grouping is performed. That is, it is the range
2277 * of the resulting expansion.
2278 * "domain_universe" is the universe of "domain".
2279 * "group" is the set of group elements, i.e., the domain
2280 * of the resulting expansion.
2281 * "group_universe" is the universe of "group".
2283 * "sched" is the schedule for the group elements, in pratice
2284 * an identity mapping on "group_universe".
2285 * "dim" is the dimension of "sched".
2287 struct isl_schedule_group_data
{
2290 isl_union_map
*expansion
;
2291 isl_union_pw_multi_aff
*contraction
;
2293 isl_union_set
*domain
;
2294 isl_union_set
*domain_universe
;
2295 isl_union_set
*group
;
2296 isl_union_set
*group_universe
;
2299 isl_multi_aff
*sched
;
2302 /* Is domain covered by data->domain within data->domain_universe?
2304 static int locally_covered_by_domain(__isl_keep isl_union_set
*domain
,
2305 struct isl_schedule_group_data
*data
)
2308 isl_union_set
*test
;
2310 test
= isl_union_set_copy(domain
);
2311 test
= isl_union_set_intersect(test
,
2312 isl_union_set_copy(data
->domain_universe
));
2313 is_subset
= isl_union_set_is_subset(test
, data
->domain
);
2314 isl_union_set_free(test
);
2319 /* Update the band tree root "tree" to refer to the group instances
2320 * in data->group rather than the original domain elements in data->domain.
2321 * "pos" is the position in the original schedule tree where the modified
2322 * "tree" will be attached.
2324 * Add the part of the identity schedule on the group instances data->sched
2325 * that corresponds to this band node to the band schedule.
2326 * If the domain elements that reach the node and that are part
2327 * of data->domain_universe are all elements of data->domain (and therefore
2328 * replaced by the group instances) then this data->domain_universe
2329 * is removed from the domain of the band schedule.
2331 static __isl_give isl_schedule_tree
*group_band(
2332 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2333 struct isl_schedule_group_data
*data
)
2335 isl_union_set
*domain
;
2337 isl_multi_union_pw_aff
*mupa
, *partial
;
2339 int depth
, n
, has_id
;
2341 domain
= isl_schedule_node_get_domain(pos
);
2342 is_covered
= locally_covered_by_domain(domain
, data
);
2343 if (is_covered
>= 0 && is_covered
) {
2344 domain
= isl_union_set_universe(domain
);
2345 domain
= isl_union_set_subtract(domain
,
2346 isl_union_set_copy(data
->domain_universe
));
2347 tree
= isl_schedule_tree_band_intersect_domain(tree
, domain
);
2349 isl_union_set_free(domain
);
2351 return isl_schedule_tree_free(tree
);
2352 depth
= isl_schedule_node_get_schedule_depth(pos
);
2353 n
= isl_schedule_tree_band_n_member(tree
);
2354 ma
= isl_multi_aff_copy(data
->sched
);
2355 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, depth
);
2356 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, n
, data
->dim
- depth
- n
);
2357 mupa
= isl_multi_union_pw_aff_from_multi_aff(ma
);
2358 partial
= isl_schedule_tree_band_get_partial_schedule(tree
);
2359 has_id
= isl_multi_union_pw_aff_has_tuple_id(partial
, isl_dim_set
);
2361 partial
= isl_multi_union_pw_aff_free(partial
);
2362 } else if (has_id
) {
2364 id
= isl_multi_union_pw_aff_get_tuple_id(partial
, isl_dim_set
);
2365 mupa
= isl_multi_union_pw_aff_set_tuple_id(mupa
,
2368 partial
= isl_multi_union_pw_aff_union_add(partial
, mupa
);
2369 tree
= isl_schedule_tree_band_set_partial_schedule(tree
, partial
);
2374 /* Drop the parameters in "uset" that are not also in "space".
2375 * "n" is the number of parameters in "space".
2377 static __isl_give isl_union_set
*union_set_drop_extra_params(
2378 __isl_take isl_union_set
*uset
, __isl_keep isl_space
*space
, int n
)
2382 uset
= isl_union_set_align_params(uset
, isl_space_copy(space
));
2383 n2
= isl_union_set_dim(uset
, isl_dim_param
);
2384 uset
= isl_union_set_project_out(uset
, isl_dim_param
, n
, n2
- n
);
2389 /* Update the context tree root "tree" to refer to the group instances
2390 * in data->group rather than the original domain elements in data->domain.
2391 * "pos" is the position in the original schedule tree where the modified
2392 * "tree" will be attached.
2394 * We do not actually need to update "tree" since a context node only
2395 * refers to the schedule space. However, we may need to update "data"
2396 * to not refer to any parameters introduced by the context node.
2398 static __isl_give isl_schedule_tree
*group_context(
2399 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2400 struct isl_schedule_group_data
*data
)
2403 isl_union_set
*domain
;
2407 if (isl_schedule_node_get_tree_depth(pos
) == 1)
2410 domain
= isl_schedule_node_get_universe_domain(pos
);
2411 space
= isl_union_set_get_space(domain
);
2412 isl_union_set_free(domain
);
2414 n1
= isl_space_dim(space
, isl_dim_param
);
2415 data
->expansion
= isl_union_map_align_params(data
->expansion
, space
);
2416 n2
= isl_union_map_dim(data
->expansion
, isl_dim_param
);
2418 if (!data
->expansion
)
2419 return isl_schedule_tree_free(tree
);
2423 involves
= isl_union_map_involves_dims(data
->expansion
,
2424 isl_dim_param
, n1
, n2
- n1
);
2426 return isl_schedule_tree_free(tree
);
2428 isl_die(isl_schedule_node_get_ctx(pos
), isl_error_invalid
,
2429 "grouping cannot only refer to global parameters",
2430 return isl_schedule_tree_free(tree
));
2432 data
->expansion
= isl_union_map_project_out(data
->expansion
,
2433 isl_dim_param
, n1
, n2
- n1
);
2434 space
= isl_union_map_get_space(data
->expansion
);
2436 data
->contraction
= isl_union_pw_multi_aff_align_params(
2437 data
->contraction
, isl_space_copy(space
));
2438 n2
= isl_union_pw_multi_aff_dim(data
->contraction
, isl_dim_param
);
2439 data
->contraction
= isl_union_pw_multi_aff_drop_dims(data
->contraction
,
2440 isl_dim_param
, n1
, n2
- n1
);
2442 data
->domain
= union_set_drop_extra_params(data
->domain
, space
, n1
);
2443 data
->domain_universe
=
2444 union_set_drop_extra_params(data
->domain_universe
, space
, n1
);
2445 data
->group
= union_set_drop_extra_params(data
->group
, space
, n1
);
2446 data
->group_universe
=
2447 union_set_drop_extra_params(data
->group_universe
, space
, n1
);
2449 data
->sched
= isl_multi_aff_align_params(data
->sched
,
2450 isl_space_copy(space
));
2451 n2
= isl_multi_aff_dim(data
->sched
, isl_dim_param
);
2452 data
->sched
= isl_multi_aff_drop_dims(data
->sched
,
2453 isl_dim_param
, n1
, n2
- n1
);
2455 isl_space_free(space
);
2460 /* Update the domain tree root "tree" to refer to the group instances
2461 * in data->group rather than the original domain elements in data->domain.
2462 * "pos" is the position in the original schedule tree where the modified
2463 * "tree" will be attached.
2465 * We first double-check that all grouped domain elements are actually
2466 * part of the root domain and then replace those elements by the group
2469 static __isl_give isl_schedule_tree
*group_domain(
2470 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2471 struct isl_schedule_group_data
*data
)
2473 isl_union_set
*domain
;
2476 domain
= isl_schedule_tree_domain_get_domain(tree
);
2477 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2478 isl_union_set_free(domain
);
2480 return isl_schedule_tree_free(tree
);
2482 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2483 "grouped domain should be part of outer domain",
2484 return isl_schedule_tree_free(tree
));
2485 domain
= isl_schedule_tree_domain_get_domain(tree
);
2486 domain
= isl_union_set_subtract(domain
,
2487 isl_union_set_copy(data
->domain
));
2488 domain
= isl_union_set_union(domain
, isl_union_set_copy(data
->group
));
2489 tree
= isl_schedule_tree_domain_set_domain(tree
, domain
);
2494 /* Update the expansion tree root "tree" to refer to the group instances
2495 * in data->group rather than the original domain elements in data->domain.
2496 * "pos" is the position in the original schedule tree where the modified
2497 * "tree" will be attached.
2499 * Let G_1 -> D_1 be the expansion of "tree" and G_2 -> D_2 the newly
2500 * introduced expansion in a descendant of "tree".
2501 * We first double-check that D_2 is a subset of D_1.
2502 * Then we remove D_2 from the range of G_1 -> D_1 and add the mapping
2503 * G_1 -> D_1 . D_2 -> G_2.
2504 * Simmilarly, we restrict the domain of the contraction to the universe
2505 * of the range of the updated expansion and add G_2 -> D_2 . D_1 -> G_1,
2506 * attempting to remove the domain constraints of this additional part.
2508 static __isl_give isl_schedule_tree
*group_expansion(
2509 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2510 struct isl_schedule_group_data
*data
)
2512 isl_union_set
*domain
;
2513 isl_union_map
*expansion
, *umap
;
2514 isl_union_pw_multi_aff
*contraction
, *upma
;
2517 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2518 domain
= isl_union_map_range(expansion
);
2519 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2520 isl_union_set_free(domain
);
2522 return isl_schedule_tree_free(tree
);
2524 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2525 "grouped domain should be part "
2526 "of outer expansion domain",
2527 return isl_schedule_tree_free(tree
));
2528 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2529 umap
= isl_union_map_from_union_pw_multi_aff(
2530 isl_union_pw_multi_aff_copy(data
->contraction
));
2531 umap
= isl_union_map_apply_range(expansion
, umap
);
2532 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2533 expansion
= isl_union_map_subtract_range(expansion
,
2534 isl_union_set_copy(data
->domain
));
2535 expansion
= isl_union_map_union(expansion
, umap
);
2536 umap
= isl_union_map_universe(isl_union_map_copy(expansion
));
2537 domain
= isl_union_map_range(umap
);
2538 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
2539 umap
= isl_union_map_from_union_pw_multi_aff(contraction
);
2540 umap
= isl_union_map_apply_range(isl_union_map_copy(data
->expansion
),
2542 upma
= isl_union_pw_multi_aff_from_union_map(umap
);
2543 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
2544 contraction
= isl_union_pw_multi_aff_intersect_domain(contraction
,
2546 domain
= isl_union_pw_multi_aff_domain(
2547 isl_union_pw_multi_aff_copy(upma
));
2548 upma
= isl_union_pw_multi_aff_gist(upma
, domain
);
2549 contraction
= isl_union_pw_multi_aff_union_add(contraction
, upma
);
2550 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
2551 contraction
, expansion
);
2556 /* Update the tree root "tree" to refer to the group instances
2557 * in data->group rather than the original domain elements in data->domain.
2558 * "pos" is the position in the original schedule tree where the modified
2559 * "tree" will be attached.
2561 * If we have come across a domain or expansion node before (data->finished
2562 * is set), then we no longer need perform any modifications.
2564 * If "tree" is a filter, then we add data->group_universe to the filter.
2565 * We also remove data->domain_universe from the filter if all the domain
2566 * elements in this universe that reach the filter node are part of
2567 * the elements that are being grouped by data->expansion.
2568 * If "tree" is a band, domain or expansion, then it is handled
2569 * in a separate function.
2571 static __isl_give isl_schedule_tree
*group_ancestor(
2572 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2575 struct isl_schedule_group_data
*data
= user
;
2576 isl_union_set
*domain
;
2580 return isl_schedule_tree_free(tree
);
2585 switch (isl_schedule_tree_get_type(tree
)) {
2586 case isl_schedule_node_error
:
2587 return isl_schedule_tree_free(tree
);
2588 case isl_schedule_node_band
:
2589 tree
= group_band(tree
, pos
, data
);
2591 case isl_schedule_node_context
:
2592 tree
= group_context(tree
, pos
, data
);
2594 case isl_schedule_node_domain
:
2595 tree
= group_domain(tree
, pos
, data
);
2598 case isl_schedule_node_filter
:
2599 domain
= isl_schedule_node_get_domain(pos
);
2600 is_covered
= locally_covered_by_domain(domain
, data
);
2601 isl_union_set_free(domain
);
2603 return isl_schedule_tree_free(tree
);
2604 domain
= isl_schedule_tree_filter_get_filter(tree
);
2606 domain
= isl_union_set_subtract(domain
,
2607 isl_union_set_copy(data
->domain_universe
));
2608 domain
= isl_union_set_union(domain
,
2609 isl_union_set_copy(data
->group_universe
));
2610 tree
= isl_schedule_tree_filter_set_filter(tree
, domain
);
2612 case isl_schedule_node_expansion
:
2613 tree
= group_expansion(tree
, pos
, data
);
2616 case isl_schedule_node_leaf
:
2617 case isl_schedule_node_mark
:
2618 case isl_schedule_node_sequence
:
2619 case isl_schedule_node_set
:
2626 /* Group the domain elements that reach "node" into instances
2627 * of a single statement with identifier "group_id".
2628 * In particular, group the domain elements according to their
2631 * That is, introduce an expansion node with as contraction
2632 * the prefix schedule (with the target space replaced by "group_id")
2633 * and as expansion the inverse of this contraction (with its range
2634 * intersected with the domain elements that reach "node").
2635 * The outer nodes are then modified to refer to the group instances
2636 * instead of the original domain elements.
2638 * No instance of "group_id" is allowed to reach "node" prior
2641 * Return a pointer to original node in tree, i.e., the child
2642 * of the newly introduced expansion node.
2644 __isl_give isl_schedule_node
*isl_schedule_node_group(
2645 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*group_id
)
2647 struct isl_schedule_group_data data
= { 0 };
2649 isl_union_set
*domain
;
2650 isl_union_pw_multi_aff
*contraction
;
2651 isl_union_map
*expansion
;
2654 if (!node
|| !group_id
)
2656 if (check_insert(node
) < 0)
2659 domain
= isl_schedule_node_get_domain(node
);
2660 data
.domain
= isl_union_set_copy(domain
);
2661 data
.domain_universe
= isl_union_set_copy(domain
);
2662 data
.domain_universe
= isl_union_set_universe(data
.domain_universe
);
2664 data
.dim
= isl_schedule_node_get_schedule_depth(node
);
2665 if (data
.dim
== 0) {
2668 isl_union_set
*group
;
2669 isl_union_map
*univ
;
2671 ctx
= isl_schedule_node_get_ctx(node
);
2672 space
= isl_space_set_alloc(ctx
, 0, 0);
2673 space
= isl_space_set_tuple_id(space
, isl_dim_set
, group_id
);
2674 set
= isl_set_universe(isl_space_copy(space
));
2675 group
= isl_union_set_from_set(set
);
2676 expansion
= isl_union_map_from_domain_and_range(domain
, group
);
2677 univ
= isl_union_map_universe(isl_union_map_copy(expansion
));
2678 contraction
= isl_union_pw_multi_aff_from_union_map(univ
);
2679 expansion
= isl_union_map_reverse(expansion
);
2681 isl_multi_union_pw_aff
*prefix
;
2682 isl_union_set
*univ
;
2685 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node
);
2686 prefix
= isl_multi_union_pw_aff_set_tuple_id(prefix
,
2687 isl_dim_set
, group_id
);
2688 space
= isl_multi_union_pw_aff_get_space(prefix
);
2689 contraction
= isl_union_pw_multi_aff_from_multi_union_pw_aff(
2691 univ
= isl_union_set_universe(isl_union_set_copy(domain
));
2693 isl_union_pw_multi_aff_intersect_domain(contraction
, univ
);
2694 expansion
= isl_union_map_from_union_pw_multi_aff(
2695 isl_union_pw_multi_aff_copy(contraction
));
2696 expansion
= isl_union_map_reverse(expansion
);
2697 expansion
= isl_union_map_intersect_range(expansion
, domain
);
2699 space
= isl_space_map_from_set(space
);
2700 data
.sched
= isl_multi_aff_identity(space
);
2701 data
.group
= isl_union_map_domain(isl_union_map_copy(expansion
));
2702 data
.group
= isl_union_set_coalesce(data
.group
);
2703 data
.group_universe
= isl_union_set_copy(data
.group
);
2704 data
.group_universe
= isl_union_set_universe(data
.group_universe
);
2705 data
.expansion
= isl_union_map_copy(expansion
);
2706 data
.contraction
= isl_union_pw_multi_aff_copy(contraction
);
2707 node
= isl_schedule_node_insert_expansion(node
, contraction
, expansion
);
2709 disjoint
= isl_union_set_is_disjoint(data
.domain_universe
,
2710 data
.group_universe
);
2712 node
= update_ancestors(node
, &group_ancestor
, &data
);
2714 isl_union_set_free(data
.domain
);
2715 isl_union_set_free(data
.domain_universe
);
2716 isl_union_set_free(data
.group
);
2717 isl_union_set_free(data
.group_universe
);
2718 isl_multi_aff_free(data
.sched
);
2719 isl_union_map_free(data
.expansion
);
2720 isl_union_pw_multi_aff_free(data
.contraction
);
2722 node
= isl_schedule_node_child(node
, 0);
2724 if (!node
|| disjoint
< 0)
2725 return isl_schedule_node_free(node
);
2727 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2728 "group instances already reach node",
2729 isl_schedule_node_free(node
));
2733 isl_schedule_node_free(node
);
2734 isl_id_free(group_id
);
2738 /* Compute the gist of the given band node with respect to "context".
2740 __isl_give isl_schedule_node
*isl_schedule_node_band_gist(
2741 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
2743 isl_schedule_tree
*tree
;
2745 tree
= isl_schedule_node_get_tree(node
);
2746 tree
= isl_schedule_tree_band_gist(tree
, context
);
2747 return isl_schedule_node_graft_tree(node
, tree
);
2750 /* Internal data structure for isl_schedule_node_gist.
2751 * "n_expansion" is the number of outer expansion nodes
2752 * with respect to the current position
2753 * "filters" contains an element for each outer filter or expansion node
2754 * with respect to the current position, each representing
2755 * the intersection of the previous element and the filter on the filter node
2756 * or the expansion of the previous element.
2757 * The first element in the original context passed to isl_schedule_node_gist.
2759 struct isl_node_gist_data
{
2761 isl_union_set_list
*filters
;
2764 /* Enter the expansion node "node" during a isl_schedule_node_gist traversal.
2766 * In particular, add an extra element to data->filters containing
2767 * the expansion of the previous element and replace the expansion
2768 * and contraction on "node" by the gist with respect to these filters.
2769 * Also keep track of the fact that we have entered another expansion.
2771 static __isl_give isl_schedule_node
*gist_enter_expansion(
2772 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
2775 isl_union_set
*inner
;
2776 isl_union_map
*expansion
;
2777 isl_union_pw_multi_aff
*contraction
;
2779 data
->n_expansion
++;
2781 n
= isl_union_set_list_n_union_set(data
->filters
);
2782 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
2783 expansion
= isl_schedule_node_expansion_get_expansion(node
);
2784 inner
= isl_union_set_apply(inner
, expansion
);
2786 contraction
= isl_schedule_node_expansion_get_contraction(node
);
2787 contraction
= isl_union_pw_multi_aff_gist(contraction
,
2788 isl_union_set_copy(inner
));
2790 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
2792 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
2793 expansion
= isl_schedule_node_expansion_get_expansion(node
);
2794 expansion
= isl_union_map_gist_domain(expansion
, inner
);
2795 node
= isl_schedule_node_expansion_set_contraction_and_expansion(node
,
2796 contraction
, expansion
);
2801 /* Can we finish gisting at this node?
2802 * That is, is the filter on the current filter node a subset of
2803 * the original context passed to isl_schedule_node_gist?
2804 * If we have gone through any expansions, then we cannot perform
2805 * this test since the current domain elements are incomparable
2806 * to the domain elements in the original context.
2808 static int gist_done(__isl_keep isl_schedule_node
*node
,
2809 struct isl_node_gist_data
*data
)
2811 isl_union_set
*filter
, *outer
;
2814 if (data
->n_expansion
!= 0)
2817 filter
= isl_schedule_node_filter_get_filter(node
);
2818 outer
= isl_union_set_list_get_union_set(data
->filters
, 0);
2819 subset
= isl_union_set_is_subset(filter
, outer
);
2820 isl_union_set_free(outer
);
2821 isl_union_set_free(filter
);
2826 /* Callback for "traverse" to enter a node and to move
2827 * to the deepest initial subtree that should be traversed
2828 * by isl_schedule_node_gist.
2830 * The "filters" list is extended by one element each time
2831 * we come across a filter node by the result of intersecting
2832 * the last element in the list with the filter on the filter node.
2834 * If the filter on the current filter node is a subset of
2835 * the original context passed to isl_schedule_node_gist,
2836 * then there is no need to go into its subtree since it cannot
2837 * be further simplified by the context. The "filters" list is
2838 * still extended for consistency, but the actual value of the
2839 * added element is immaterial since it will not be used.
2841 * Otherwise, the filter on the current filter node is replaced by
2842 * the gist of the original filter with respect to the intersection
2843 * of the original context with the intermediate filters.
2845 * If the new element in the "filters" list is empty, then no elements
2846 * can reach the descendants of the current filter node. The subtree
2847 * underneath the filter node is therefore removed.
2849 * Each expansion node we come across is handled by
2850 * gist_enter_expansion.
2852 static __isl_give isl_schedule_node
*gist_enter(
2853 __isl_take isl_schedule_node
*node
, void *user
)
2855 struct isl_node_gist_data
*data
= user
;
2858 isl_union_set
*filter
, *inner
;
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 node
= gist_enter_expansion(node
, data
);
2868 case isl_schedule_node_band
:
2869 case isl_schedule_node_context
:
2870 case isl_schedule_node_domain
:
2871 case isl_schedule_node_leaf
:
2872 case isl_schedule_node_mark
:
2873 case isl_schedule_node_sequence
:
2874 case isl_schedule_node_set
:
2876 case isl_schedule_node_filter
:
2879 done
= gist_done(node
, data
);
2880 filter
= isl_schedule_node_filter_get_filter(node
);
2881 if (done
< 0 || done
) {
2882 data
->filters
= isl_union_set_list_add(data
->filters
,
2885 return isl_schedule_node_free(node
);
2888 n
= isl_union_set_list_n_union_set(data
->filters
);
2889 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
2890 filter
= isl_union_set_gist(filter
, isl_union_set_copy(inner
));
2891 node
= isl_schedule_node_filter_set_filter(node
,
2892 isl_union_set_copy(filter
));
2893 filter
= isl_union_set_intersect(filter
, inner
);
2894 empty
= isl_union_set_is_empty(filter
);
2895 data
->filters
= isl_union_set_list_add(data
->filters
, filter
);
2897 return isl_schedule_node_free(node
);
2900 node
= isl_schedule_node_child(node
, 0);
2901 node
= isl_schedule_node_cut(node
);
2902 node
= isl_schedule_node_parent(node
);
2904 } while (isl_schedule_node_has_children(node
) &&
2905 (node
= isl_schedule_node_first_child(node
)) != NULL
);
2910 /* Callback for "traverse" to leave a node for isl_schedule_node_gist.
2912 * In particular, if the current node is a filter node, then we remove
2913 * the element on the "filters" list that was added when we entered
2914 * the node. There is no need to compute any gist here, since we
2915 * already did that when we entered the node.
2917 * If the current node is an expansion, then we decrement
2918 * the number of outer expansions and remove the element
2919 * in data->filters that was added by gist_enter_expansion.
2921 * If the current node is a band node, then we compute the gist of
2922 * the band node with respect to the intersection of the original context
2923 * and the intermediate filters.
2925 * If the current node is a sequence or set node, then some of
2926 * the filter children may have become empty and so they are removed.
2927 * If only one child is left, then the set or sequence node along with
2928 * the single remaining child filter is removed. The filter can be
2929 * removed because the filters on a sequence or set node are supposed
2930 * to partition the incoming domain instances.
2931 * In principle, it should then be impossible for there to be zero
2932 * remaining children, but should this happen, we replace the entire
2933 * subtree with an empty filter.
2935 static __isl_give isl_schedule_node
*gist_leave(
2936 __isl_take isl_schedule_node
*node
, void *user
)
2938 struct isl_node_gist_data
*data
= user
;
2939 isl_schedule_tree
*tree
;
2941 isl_union_set
*filter
;
2943 switch (isl_schedule_node_get_type(node
)) {
2944 case isl_schedule_node_error
:
2945 return isl_schedule_node_free(node
);
2946 case isl_schedule_node_expansion
:
2947 data
->n_expansion
--;
2948 case isl_schedule_node_filter
:
2949 n
= isl_union_set_list_n_union_set(data
->filters
);
2950 data
->filters
= isl_union_set_list_drop(data
->filters
,
2953 case isl_schedule_node_band
:
2954 n
= isl_union_set_list_n_union_set(data
->filters
);
2955 filter
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
2956 node
= isl_schedule_node_band_gist(node
, filter
);
2958 case isl_schedule_node_set
:
2959 case isl_schedule_node_sequence
:
2960 tree
= isl_schedule_node_get_tree(node
);
2961 n
= isl_schedule_tree_n_children(tree
);
2962 for (i
= n
- 1; i
>= 0; --i
) {
2963 isl_schedule_tree
*child
;
2964 isl_union_set
*filter
;
2967 child
= isl_schedule_tree_get_child(tree
, i
);
2968 filter
= isl_schedule_tree_filter_get_filter(child
);
2969 empty
= isl_union_set_is_empty(filter
);
2970 isl_union_set_free(filter
);
2971 isl_schedule_tree_free(child
);
2973 tree
= isl_schedule_tree_free(tree
);
2975 tree
= isl_schedule_tree_drop_child(tree
, i
);
2977 n
= isl_schedule_tree_n_children(tree
);
2978 node
= isl_schedule_node_graft_tree(node
, tree
);
2980 node
= isl_schedule_node_delete(node
);
2981 node
= isl_schedule_node_delete(node
);
2982 } else if (n
== 0) {
2986 isl_union_set_list_get_union_set(data
->filters
, 0);
2987 space
= isl_union_set_get_space(filter
);
2988 isl_union_set_free(filter
);
2989 filter
= isl_union_set_empty(space
);
2990 node
= isl_schedule_node_cut(node
);
2991 node
= isl_schedule_node_insert_filter(node
, filter
);
2994 case isl_schedule_node_context
:
2995 case isl_schedule_node_domain
:
2996 case isl_schedule_node_leaf
:
2997 case isl_schedule_node_mark
:
3004 /* Compute the gist of the subtree at "node" with respect to
3005 * the reaching domain elements in "context".
3006 * In particular, compute the gist of all band and filter nodes
3007 * in the subtree with respect to "context". Children of set or sequence
3008 * nodes that end up with an empty filter are removed completely.
3010 * We keep track of the intersection of "context" with all outer filters
3011 * of the current node within the subtree in the final element of "filters".
3012 * Initially, this list contains the single element "context" and it is
3013 * extended or shortened each time we enter or leave a filter node.
3015 __isl_give isl_schedule_node
*isl_schedule_node_gist(
3016 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3018 struct isl_node_gist_data data
;
3020 data
.n_expansion
= 0;
3021 data
.filters
= isl_union_set_list_from_union_set(context
);
3022 node
= traverse(node
, &gist_enter
, &gist_leave
, &data
);
3023 isl_union_set_list_free(data
.filters
);
3027 /* Intersect the domain of domain node "node" with "domain".
3029 * If the domain of "node" is already a subset of "domain",
3030 * then nothing needs to be changed.
3032 * Otherwise, we replace the domain of the domain node by the intersection
3033 * and simplify the subtree rooted at "node" with respect to this intersection.
3035 __isl_give isl_schedule_node
*isl_schedule_node_domain_intersect_domain(
3036 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
)
3038 isl_schedule_tree
*tree
;
3039 isl_union_set
*uset
;
3042 if (!node
|| !domain
)
3045 uset
= isl_schedule_tree_domain_get_domain(node
->tree
);
3046 is_subset
= isl_union_set_is_subset(uset
, domain
);
3047 isl_union_set_free(uset
);
3051 isl_union_set_free(domain
);
3055 tree
= isl_schedule_tree_copy(node
->tree
);
3056 uset
= isl_schedule_tree_domain_get_domain(tree
);
3057 uset
= isl_union_set_intersect(uset
, domain
);
3058 tree
= isl_schedule_tree_domain_set_domain(tree
,
3059 isl_union_set_copy(uset
));
3060 node
= isl_schedule_node_graft_tree(node
, tree
);
3062 node
= isl_schedule_node_child(node
, 0);
3063 node
= isl_schedule_node_gist(node
, uset
);
3064 node
= isl_schedule_node_parent(node
);
3068 isl_schedule_node_free(node
);
3069 isl_union_set_free(domain
);
3073 /* Internal data structure for isl_schedule_node_get_subtree_expansion.
3074 * "expansions" contains a list of accumulated expansions
3075 * for each outer expansion, set or sequence node. The first element
3076 * in the list is an identity mapping on the reaching domain elements.
3077 * "res" collects the results.
3079 struct isl_subtree_expansion_data
{
3080 isl_union_map_list
*expansions
;
3084 /* Callback for "traverse" to enter a node and to move
3085 * to the deepest initial subtree that should be traversed
3086 * by isl_schedule_node_get_subtree_expansion.
3088 * Whenever we come across an expansion node, the last element
3089 * of data->expansions is combined with the expansion
3090 * on the expansion node.
3092 * Whenever we come across a filter node that is the child
3093 * of a set or sequence node, data->expansions is extended
3094 * with a new element that restricts the previous element
3095 * to the elements selected by the filter.
3096 * The previous element can then be reused while backtracking.
3098 static __isl_give isl_schedule_node
*subtree_expansion_enter(
3099 __isl_take isl_schedule_node
*node
, void *user
)
3101 struct isl_subtree_expansion_data
*data
= user
;
3104 enum isl_schedule_node_type type
;
3105 isl_union_set
*filter
;
3106 isl_union_map
*inner
, *expansion
;
3109 switch (isl_schedule_node_get_type(node
)) {
3110 case isl_schedule_node_error
:
3111 return isl_schedule_node_free(node
);
3112 case isl_schedule_node_filter
:
3113 type
= isl_schedule_node_get_parent_type(node
);
3114 if (type
!= isl_schedule_node_set
&&
3115 type
!= isl_schedule_node_sequence
)
3117 filter
= isl_schedule_node_filter_get_filter(node
);
3118 n
= isl_union_map_list_n_union_map(data
->expansions
);
3120 isl_union_map_list_get_union_map(data
->expansions
,
3122 inner
= isl_union_map_intersect_range(inner
, filter
);
3124 isl_union_map_list_add(data
->expansions
, inner
);
3126 case isl_schedule_node_expansion
:
3127 n
= isl_union_map_list_n_union_map(data
->expansions
);
3129 isl_schedule_node_expansion_get_expansion(node
);
3131 isl_union_map_list_get_union_map(data
->expansions
,
3133 inner
= isl_union_map_apply_range(inner
, expansion
);
3135 isl_union_map_list_set_union_map(data
->expansions
,
3138 case isl_schedule_node_band
:
3139 case isl_schedule_node_context
:
3140 case isl_schedule_node_domain
:
3141 case isl_schedule_node_leaf
:
3142 case isl_schedule_node_mark
:
3143 case isl_schedule_node_sequence
:
3144 case isl_schedule_node_set
:
3147 } while (isl_schedule_node_has_children(node
) &&
3148 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3153 /* Callback for "traverse" to leave a node for
3154 * isl_schedule_node_get_subtree_expansion.
3156 * If we come across a filter node that is the child
3157 * of a set or sequence node, then we remove the element
3158 * of data->expansions that was added in subtree_expansion_enter.
3160 * If we reach a leaf node, then the accumulated expansion is
3161 * added to data->res.
3163 static __isl_give isl_schedule_node
*subtree_expansion_leave(
3164 __isl_take isl_schedule_node
*node
, void *user
)
3166 struct isl_subtree_expansion_data
*data
= user
;
3168 isl_union_map
*inner
;
3169 enum isl_schedule_node_type type
;
3171 switch (isl_schedule_node_get_type(node
)) {
3172 case isl_schedule_node_error
:
3173 return isl_schedule_node_free(node
);
3174 case isl_schedule_node_filter
:
3175 type
= isl_schedule_node_get_parent_type(node
);
3176 if (type
!= isl_schedule_node_set
&&
3177 type
!= isl_schedule_node_sequence
)
3179 n
= isl_union_map_list_n_union_map(data
->expansions
);
3180 data
->expansions
= isl_union_map_list_drop(data
->expansions
,
3183 case isl_schedule_node_leaf
:
3184 n
= isl_union_map_list_n_union_map(data
->expansions
);
3185 inner
= isl_union_map_list_get_union_map(data
->expansions
,
3187 data
->res
= isl_union_map_union(data
->res
, inner
);
3189 case isl_schedule_node_band
:
3190 case isl_schedule_node_context
:
3191 case isl_schedule_node_domain
:
3192 case isl_schedule_node_expansion
:
3193 case isl_schedule_node_mark
:
3194 case isl_schedule_node_sequence
:
3195 case isl_schedule_node_set
:
3202 /* Return a mapping from the domain elements that reach "node"
3203 * to the corresponding domain elements in the leaves of the subtree
3204 * rooted at "node" obtained by composing the intermediate expansions.
3206 * We start out with an identity mapping between the domain elements
3207 * that reach "node" and compose it with all the expansions
3208 * on a path from "node" to a leaf while traversing the subtree.
3209 * Within the children of an a sequence or set node, the
3210 * accumulated expansion is restricted to the elements selected
3211 * by the filter child.
3213 __isl_give isl_union_map
*isl_schedule_node_get_subtree_expansion(
3214 __isl_keep isl_schedule_node
*node
)
3216 struct isl_subtree_expansion_data data
;
3218 isl_union_set
*domain
;
3219 isl_union_map
*expansion
;
3224 domain
= isl_schedule_node_get_universe_domain(node
);
3225 space
= isl_union_set_get_space(domain
);
3226 expansion
= isl_union_set_identity(domain
);
3227 data
.res
= isl_union_map_empty(space
);
3228 data
.expansions
= isl_union_map_list_from_union_map(expansion
);
3230 node
= isl_schedule_node_copy(node
);
3231 node
= traverse(node
, &subtree_expansion_enter
,
3232 &subtree_expansion_leave
, &data
);
3234 data
.res
= isl_union_map_free(data
.res
);
3235 isl_schedule_node_free(node
);
3237 isl_union_map_list_free(data
.expansions
);
3242 /* Internal data structure for isl_schedule_node_get_subtree_contraction.
3243 * "contractions" contains a list of accumulated contractions
3244 * for each outer expansion, set or sequence node. The first element
3245 * in the list is an identity mapping on the reaching domain elements.
3246 * "res" collects the results.
3248 struct isl_subtree_contraction_data
{
3249 isl_union_pw_multi_aff_list
*contractions
;
3250 isl_union_pw_multi_aff
*res
;
3253 /* Callback for "traverse" to enter a node and to move
3254 * to the deepest initial subtree that should be traversed
3255 * by isl_schedule_node_get_subtree_contraction.
3257 * Whenever we come across an expansion node, the last element
3258 * of data->contractions is combined with the contraction
3259 * on the expansion node.
3261 * Whenever we come across a filter node that is the child
3262 * of a set or sequence node, data->contractions is extended
3263 * with a new element that restricts the previous element
3264 * to the elements selected by the filter.
3265 * The previous element can then be reused while backtracking.
3267 static __isl_give isl_schedule_node
*subtree_contraction_enter(
3268 __isl_take isl_schedule_node
*node
, void *user
)
3270 struct isl_subtree_contraction_data
*data
= user
;
3273 enum isl_schedule_node_type type
;
3274 isl_union_set
*filter
;
3275 isl_union_pw_multi_aff
*inner
, *contraction
;
3278 switch (isl_schedule_node_get_type(node
)) {
3279 case isl_schedule_node_error
:
3280 return isl_schedule_node_free(node
);
3281 case isl_schedule_node_filter
:
3282 type
= isl_schedule_node_get_parent_type(node
);
3283 if (type
!= isl_schedule_node_set
&&
3284 type
!= isl_schedule_node_sequence
)
3286 filter
= isl_schedule_node_filter_get_filter(node
);
3287 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3288 data
->contractions
);
3290 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3291 data
->contractions
, n
- 1);
3292 inner
= isl_union_pw_multi_aff_intersect_domain(inner
,
3294 data
->contractions
=
3295 isl_union_pw_multi_aff_list_add(data
->contractions
,
3298 case isl_schedule_node_expansion
:
3299 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3300 data
->contractions
);
3302 isl_schedule_node_expansion_get_contraction(node
);
3304 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3305 data
->contractions
, n
- 1);
3307 isl_union_pw_multi_aff_pullback_union_pw_multi_aff(
3308 inner
, contraction
);
3309 data
->contractions
=
3310 isl_union_pw_multi_aff_list_set_union_pw_multi_aff(
3311 data
->contractions
, n
- 1, inner
);
3313 case isl_schedule_node_band
:
3314 case isl_schedule_node_context
:
3315 case isl_schedule_node_domain
:
3316 case isl_schedule_node_leaf
:
3317 case isl_schedule_node_mark
:
3318 case isl_schedule_node_sequence
:
3319 case isl_schedule_node_set
:
3322 } while (isl_schedule_node_has_children(node
) &&
3323 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3328 /* Callback for "traverse" to leave a node for
3329 * isl_schedule_node_get_subtree_contraction.
3331 * If we come across a filter node that is the child
3332 * of a set or sequence node, then we remove the element
3333 * of data->contractions that was added in subtree_contraction_enter.
3335 * If we reach a leaf node, then the accumulated contraction is
3336 * added to data->res.
3338 static __isl_give isl_schedule_node
*subtree_contraction_leave(
3339 __isl_take isl_schedule_node
*node
, void *user
)
3341 struct isl_subtree_contraction_data
*data
= user
;
3343 isl_union_pw_multi_aff
*inner
;
3344 enum isl_schedule_node_type type
;
3346 switch (isl_schedule_node_get_type(node
)) {
3347 case isl_schedule_node_error
:
3348 return isl_schedule_node_free(node
);
3349 case isl_schedule_node_filter
:
3350 type
= isl_schedule_node_get_parent_type(node
);
3351 if (type
!= isl_schedule_node_set
&&
3352 type
!= isl_schedule_node_sequence
)
3354 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3355 data
->contractions
);
3356 data
->contractions
=
3357 isl_union_pw_multi_aff_list_drop(data
->contractions
,
3360 case isl_schedule_node_leaf
:
3361 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3362 data
->contractions
);
3363 inner
= isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3364 data
->contractions
, n
- 1);
3365 data
->res
= isl_union_pw_multi_aff_union_add(data
->res
, inner
);
3367 case isl_schedule_node_band
:
3368 case isl_schedule_node_context
:
3369 case isl_schedule_node_domain
:
3370 case isl_schedule_node_expansion
:
3371 case isl_schedule_node_mark
:
3372 case isl_schedule_node_sequence
:
3373 case isl_schedule_node_set
:
3380 /* Return a mapping from the domain elements in the leaves of the subtree
3381 * rooted at "node" to the corresponding domain elements that reach "node"
3382 * obtained by composing the intermediate contractions.
3384 * We start out with an identity mapping between the domain elements
3385 * that reach "node" and compose it with all the contractions
3386 * on a path from "node" to a leaf while traversing the subtree.
3387 * Within the children of an a sequence or set node, the
3388 * accumulated contraction is restricted to the elements selected
3389 * by the filter child.
3391 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_get_subtree_contraction(
3392 __isl_keep isl_schedule_node
*node
)
3394 struct isl_subtree_contraction_data data
;
3396 isl_union_set
*domain
;
3397 isl_union_pw_multi_aff
*contraction
;
3402 domain
= isl_schedule_node_get_universe_domain(node
);
3403 space
= isl_union_set_get_space(domain
);
3404 contraction
= isl_union_set_identity_union_pw_multi_aff(domain
);
3405 data
.res
= isl_union_pw_multi_aff_empty(space
);
3407 isl_union_pw_multi_aff_list_from_union_pw_multi_aff(contraction
);
3409 node
= isl_schedule_node_copy(node
);
3410 node
= traverse(node
, &subtree_contraction_enter
,
3411 &subtree_contraction_leave
, &data
);
3413 data
.res
= isl_union_pw_multi_aff_free(data
.res
);
3414 isl_schedule_node_free(node
);
3416 isl_union_pw_multi_aff_list_free(data
.contractions
);
3421 /* Reset the user pointer on all identifiers of parameters and tuples
3422 * in the schedule node "node".
3424 __isl_give isl_schedule_node
*isl_schedule_node_reset_user(
3425 __isl_take isl_schedule_node
*node
)
3427 isl_schedule_tree
*tree
;
3429 tree
= isl_schedule_node_get_tree(node
);
3430 tree
= isl_schedule_tree_reset_user(tree
);
3431 node
= isl_schedule_node_graft_tree(node
, tree
);
3436 /* Align the parameters of the schedule node "node" to those of "space".
3438 __isl_give isl_schedule_node
*isl_schedule_node_align_params(
3439 __isl_take isl_schedule_node
*node
, __isl_take isl_space
*space
)
3441 isl_schedule_tree
*tree
;
3443 tree
= isl_schedule_node_get_tree(node
);
3444 tree
= isl_schedule_tree_align_params(tree
, space
);
3445 node
= isl_schedule_node_graft_tree(node
, tree
);
3450 /* Compute the pullback of schedule node "node"
3451 * by the function represented by "upma".
3452 * In other words, plug in "upma" in the iteration domains
3453 * of schedule node "node".
3454 * We currently do not handle expansion nodes.
3456 * Note that this is only a helper function for
3457 * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency,
3458 * this function should not be called on a single node without also
3459 * calling it on all the other nodes.
3461 __isl_give isl_schedule_node
*isl_schedule_node_pullback_union_pw_multi_aff(
3462 __isl_take isl_schedule_node
*node
,
3463 __isl_take isl_union_pw_multi_aff
*upma
)
3465 isl_schedule_tree
*tree
;
3467 tree
= isl_schedule_node_get_tree(node
);
3468 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, upma
);
3469 node
= isl_schedule_node_graft_tree(node
, tree
);
3474 /* Return the position of the subtree containing "node" among the children
3475 * of "ancestor". "node" is assumed to be a descendant of "ancestor".
3476 * In particular, both nodes should point to the same schedule tree.
3478 * Return -1 on error.
3480 int isl_schedule_node_get_ancestor_child_position(
3481 __isl_keep isl_schedule_node
*node
,
3482 __isl_keep isl_schedule_node
*ancestor
)
3485 isl_schedule_tree
*tree
;
3487 if (!node
|| !ancestor
)
3490 if (node
->schedule
!= ancestor
->schedule
)
3491 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3492 "not a descendant", return -1);
3494 n1
= isl_schedule_node_get_tree_depth(ancestor
);
3495 n2
= isl_schedule_node_get_tree_depth(node
);
3498 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3499 "not a descendant", return -1);
3500 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n1
);
3501 isl_schedule_tree_free(tree
);
3502 if (tree
!= ancestor
->tree
)
3503 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3504 "not a descendant", return -1);
3506 return node
->child_pos
[n1
];
3509 /* Given two nodes that point to the same schedule tree, return their
3510 * closest shared ancestor.
3512 * Since the two nodes point to the same schedule, they share at least
3513 * one ancestor, the root of the schedule. We move down from the root
3514 * to the first ancestor where the respective children have a different
3515 * child position. This is the requested ancestor.
3516 * If there is no ancestor where the children have a different position,
3517 * then one node is an ancestor of the other and then this node is
3518 * the requested ancestor.
3520 __isl_give isl_schedule_node
*isl_schedule_node_get_shared_ancestor(
3521 __isl_keep isl_schedule_node
*node1
,
3522 __isl_keep isl_schedule_node
*node2
)
3526 if (!node1
|| !node2
)
3528 if (node1
->schedule
!= node2
->schedule
)
3529 isl_die(isl_schedule_node_get_ctx(node1
), isl_error_invalid
,
3530 "not part of same schedule", return NULL
);
3531 n1
= isl_schedule_node_get_tree_depth(node1
);
3532 n2
= isl_schedule_node_get_tree_depth(node2
);
3534 return isl_schedule_node_get_shared_ancestor(node2
, node1
);
3536 return isl_schedule_node_copy(node1
);
3537 if (isl_schedule_node_is_equal(node1
, node2
))
3538 return isl_schedule_node_copy(node1
);
3540 for (i
= 0; i
< n1
; ++i
)
3541 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
3544 node1
= isl_schedule_node_copy(node1
);
3545 return isl_schedule_node_ancestor(node1
, n1
- i
);
3548 /* Print "node" to "p".
3550 __isl_give isl_printer
*isl_printer_print_schedule_node(
3551 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
3554 return isl_printer_free(p
);
3555 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
,
3556 isl_schedule_tree_list_n_schedule_tree(node
->ancestors
),
3560 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
3563 isl_printer
*printer
;
3568 ctx
= isl_schedule_node_get_ctx(node
);
3569 printer
= isl_printer_to_file(ctx
, stderr
);
3570 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
3571 printer
= isl_printer_print_schedule_node(printer
, node
);
3573 isl_printer_free(printer
);