2 * Copyright 2013-2014 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
4 * Copyright 2016 Sven Verdoolaege
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege,
9 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
10 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
11 * B.P. 105 - 78153 Le Chesnay, France
15 #include <isl/space.h>
17 #include <isl_schedule_band.h>
18 #include <isl_schedule_private.h>
19 #include <isl_schedule_node_private.h>
21 /* Create a new schedule node in the given schedule, point at the given
22 * tree with given ancestors and child positions.
23 * "child_pos" may be NULL if there are no ancestors.
25 __isl_give isl_schedule_node
*isl_schedule_node_alloc(
26 __isl_take isl_schedule
*schedule
, __isl_take isl_schedule_tree
*tree
,
27 __isl_take isl_schedule_tree_list
*ancestors
, int *child_pos
)
30 isl_schedule_node
*node
;
33 if (!schedule
|| !tree
|| !ancestors
)
35 n
= isl_schedule_tree_list_n_schedule_tree(ancestors
);
36 if (n
> 0 && !child_pos
)
38 ctx
= isl_schedule_get_ctx(schedule
);
39 node
= isl_calloc_type(ctx
, isl_schedule_node
);
43 node
->schedule
= schedule
;
45 node
->ancestors
= ancestors
;
46 node
->child_pos
= isl_alloc_array(ctx
, int, n
);
47 if (n
&& !node
->child_pos
)
48 return isl_schedule_node_free(node
);
49 for (i
= 0; i
< n
; ++i
)
50 node
->child_pos
[i
] = child_pos
[i
];
54 isl_schedule_free(schedule
);
55 isl_schedule_tree_free(tree
);
56 isl_schedule_tree_list_free(ancestors
);
60 /* Return a pointer to the root of a schedule tree with as single
61 * node a domain node with the given domain.
63 __isl_give isl_schedule_node
*isl_schedule_node_from_domain(
64 __isl_take isl_union_set
*domain
)
66 isl_schedule
*schedule
;
67 isl_schedule_node
*node
;
69 schedule
= isl_schedule_from_domain(domain
);
70 node
= isl_schedule_get_root(schedule
);
71 isl_schedule_free(schedule
);
76 /* Return a pointer to the root of a schedule tree with as single
77 * node a extension node with the given extension.
79 __isl_give isl_schedule_node
*isl_schedule_node_from_extension(
80 __isl_take isl_union_map
*extension
)
83 isl_schedule
*schedule
;
84 isl_schedule_tree
*tree
;
85 isl_schedule_node
*node
;
90 ctx
= isl_union_map_get_ctx(extension
);
91 tree
= isl_schedule_tree_from_extension(extension
);
92 schedule
= isl_schedule_from_schedule_tree(ctx
, tree
);
93 node
= isl_schedule_get_root(schedule
);
94 isl_schedule_free(schedule
);
99 /* Return the isl_ctx to which "node" belongs.
101 isl_ctx
*isl_schedule_node_get_ctx(__isl_keep isl_schedule_node
*node
)
103 return node
? isl_schedule_get_ctx(node
->schedule
) : NULL
;
106 /* Return a pointer to the leaf of the schedule into which "node" points.
108 __isl_keep isl_schedule_tree
*isl_schedule_node_peek_leaf(
109 __isl_keep isl_schedule_node
*node
)
111 return node
? isl_schedule_peek_leaf(node
->schedule
) : NULL
;
114 /* Return a copy of the leaf of the schedule into which "node" points.
116 __isl_give isl_schedule_tree
*isl_schedule_node_get_leaf(
117 __isl_keep isl_schedule_node
*node
)
119 return isl_schedule_tree_copy(isl_schedule_node_peek_leaf(node
));
122 /* Return the type of the node or isl_schedule_node_error on error.
124 enum isl_schedule_node_type
isl_schedule_node_get_type(
125 __isl_keep isl_schedule_node
*node
)
127 return node
? isl_schedule_tree_get_type(node
->tree
)
128 : isl_schedule_node_error
;
131 /* Return the type of the parent of "node" or isl_schedule_node_error on error.
133 enum isl_schedule_node_type
isl_schedule_node_get_parent_type(
134 __isl_keep isl_schedule_node
*node
)
138 isl_schedule_tree
*parent
;
139 enum isl_schedule_node_type type
;
142 return isl_schedule_node_error
;
143 has_parent
= isl_schedule_node_has_parent(node
);
145 return isl_schedule_node_error
;
147 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
148 "node has no parent", return isl_schedule_node_error
);
150 pos
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) - 1;
151 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, pos
);
152 type
= isl_schedule_tree_get_type(parent
);
153 isl_schedule_tree_free(parent
);
158 /* Return a copy of the subtree that this node points to.
160 __isl_give isl_schedule_tree
*isl_schedule_node_get_tree(
161 __isl_keep isl_schedule_node
*node
)
166 return isl_schedule_tree_copy(node
->tree
);
169 /* Return a copy of the schedule into which "node" points.
171 __isl_give isl_schedule
*isl_schedule_node_get_schedule(
172 __isl_keep isl_schedule_node
*node
)
176 return isl_schedule_copy(node
->schedule
);
179 /* Return a fresh copy of "node".
181 __isl_take isl_schedule_node
*isl_schedule_node_dup(
182 __isl_keep isl_schedule_node
*node
)
187 return isl_schedule_node_alloc(isl_schedule_copy(node
->schedule
),
188 isl_schedule_tree_copy(node
->tree
),
189 isl_schedule_tree_list_copy(node
->ancestors
),
193 /* Return an isl_schedule_node that is equal to "node" and that has only
194 * a single reference.
196 __isl_give isl_schedule_node
*isl_schedule_node_cow(
197 __isl_take isl_schedule_node
*node
)
205 return isl_schedule_node_dup(node
);
208 /* Return a new reference to "node".
210 __isl_give isl_schedule_node
*isl_schedule_node_copy(
211 __isl_keep isl_schedule_node
*node
)
220 /* Free "node" and return NULL.
222 __isl_null isl_schedule_node
*isl_schedule_node_free(
223 __isl_take isl_schedule_node
*node
)
230 isl_schedule_tree_list_free(node
->ancestors
);
231 free(node
->child_pos
);
232 isl_schedule_tree_free(node
->tree
);
233 isl_schedule_free(node
->schedule
);
239 /* Do "node1" and "node2" point to the same position in the same
242 isl_bool
isl_schedule_node_is_equal(__isl_keep isl_schedule_node
*node1
,
243 __isl_keep isl_schedule_node
*node2
)
247 if (!node1
|| !node2
)
248 return isl_bool_error
;
250 return isl_bool_true
;
251 if (node1
->schedule
!= node2
->schedule
)
252 return isl_bool_false
;
254 n1
= isl_schedule_node_get_tree_depth(node1
);
255 n2
= isl_schedule_node_get_tree_depth(node2
);
257 return isl_bool_false
;
258 for (i
= 0; i
< n1
; ++i
)
259 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
260 return isl_bool_false
;
262 return isl_bool_true
;
265 /* Return the number of outer schedule dimensions of "node"
266 * in its schedule tree.
268 * Return -1 on error.
270 int isl_schedule_node_get_schedule_depth(__isl_keep isl_schedule_node
*node
)
278 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
279 for (i
= n
- 1; i
>= 0; --i
) {
280 isl_schedule_tree
*tree
;
282 tree
= isl_schedule_tree_list_get_schedule_tree(
286 if (tree
->type
== isl_schedule_node_band
)
287 depth
+= isl_schedule_tree_band_n_member(tree
);
288 isl_schedule_tree_free(tree
);
294 /* Internal data structure for
295 * isl_schedule_node_get_prefix_schedule_union_pw_multi_aff
297 * "initialized" is set if the filter field has been initialized.
298 * If "universe_domain" is not set, then the collected filter is intersected
299 * with the the domain of the root domain node.
300 * "universe_filter" is set if we are only collecting the universes of filters
301 * "collect_prefix" is set if we are collecting prefixes.
302 * "filter" collects all outer filters and is NULL until "initialized" is set.
303 * "prefix" collects all outer band partial schedules (if "collect_prefix"
304 * is set). If it is used, then it is initialized by the caller
305 * of collect_filter_prefix to a zero-dimensional function.
307 struct isl_schedule_node_get_filter_prefix_data
{
312 isl_union_set
*filter
;
313 isl_multi_union_pw_aff
*prefix
;
316 static int collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
317 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
);
319 /* Update the filter and prefix information in "data" based on the first "n"
320 * elements in "list" and the expansion tree root "tree".
322 * We first collect the information from the elements in "list",
323 * initializing the filter based on the domain of the expansion.
324 * Then we map the results to the expanded space and combined them
325 * with the results already in "data".
327 static int collect_filter_prefix_expansion(__isl_take isl_schedule_tree
*tree
,
328 __isl_keep isl_schedule_tree_list
*list
, int n
,
329 struct isl_schedule_node_get_filter_prefix_data
*data
)
331 struct isl_schedule_node_get_filter_prefix_data contracted
;
332 isl_union_pw_multi_aff
*c
;
333 isl_union_map
*exp
, *universe
;
334 isl_union_set
*filter
;
336 c
= isl_schedule_tree_expansion_get_contraction(tree
);
337 exp
= isl_schedule_tree_expansion_get_expansion(tree
);
339 contracted
.initialized
= 1;
340 contracted
.universe_domain
= data
->universe_domain
;
341 contracted
.universe_filter
= data
->universe_filter
;
342 contracted
.collect_prefix
= data
->collect_prefix
;
343 universe
= isl_union_map_universe(isl_union_map_copy(exp
));
344 filter
= isl_union_map_domain(universe
);
345 if (data
->collect_prefix
) {
346 isl_space
*space
= isl_union_set_get_space(filter
);
347 space
= isl_space_set_from_params(space
);
348 contracted
.prefix
= isl_multi_union_pw_aff_zero(space
);
350 contracted
.filter
= filter
;
352 if (collect_filter_prefix(list
, n
, &contracted
) < 0)
353 contracted
.filter
= isl_union_set_free(contracted
.filter
);
354 if (data
->collect_prefix
) {
355 isl_multi_union_pw_aff
*prefix
;
357 prefix
= contracted
.prefix
;
359 isl_multi_union_pw_aff_pullback_union_pw_multi_aff(prefix
,
360 isl_union_pw_multi_aff_copy(c
));
361 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(
362 prefix
, data
->prefix
);
364 filter
= contracted
.filter
;
365 if (data
->universe_domain
)
366 filter
= isl_union_set_preimage_union_pw_multi_aff(filter
,
367 isl_union_pw_multi_aff_copy(c
));
369 filter
= isl_union_set_apply(filter
, isl_union_map_copy(exp
));
370 if (!data
->initialized
)
371 data
->filter
= filter
;
373 data
->filter
= isl_union_set_intersect(filter
, data
->filter
);
374 data
->initialized
= 1;
376 isl_union_pw_multi_aff_free(c
);
377 isl_union_map_free(exp
);
378 isl_schedule_tree_free(tree
);
383 /* Update the filter information in "data" based on the first "n"
384 * elements in "list" and the extension tree root "tree", in case
385 * data->universe_domain is set and data->collect_prefix is not.
387 * We collect the universe domain of the elements in "list" and
388 * add it to the universe range of the extension (intersected
389 * with the already collected filter, if any).
391 static int collect_universe_domain_extension(__isl_take isl_schedule_tree
*tree
,
392 __isl_keep isl_schedule_tree_list
*list
, int n
,
393 struct isl_schedule_node_get_filter_prefix_data
*data
)
395 struct isl_schedule_node_get_filter_prefix_data data_outer
;
396 isl_union_map
*extension
;
397 isl_union_set
*filter
;
399 data_outer
.initialized
= 0;
400 data_outer
.universe_domain
= 1;
401 data_outer
.universe_filter
= data
->universe_filter
;
402 data_outer
.collect_prefix
= 0;
403 data_outer
.filter
= NULL
;
404 data_outer
.prefix
= NULL
;
406 if (collect_filter_prefix(list
, n
, &data_outer
) < 0)
407 data_outer
.filter
= isl_union_set_free(data_outer
.filter
);
409 extension
= isl_schedule_tree_extension_get_extension(tree
);
410 extension
= isl_union_map_universe(extension
);
411 filter
= isl_union_map_range(extension
);
412 if (data_outer
.initialized
)
413 filter
= isl_union_set_union(filter
, data_outer
.filter
);
414 if (data
->initialized
)
415 filter
= isl_union_set_intersect(filter
, data
->filter
);
417 data
->filter
= filter
;
419 isl_schedule_tree_free(tree
);
424 /* Update "data" based on the tree node "tree" in case "data" has
425 * not been initialized yet.
427 * Return 0 on success and -1 on error.
429 * If "tree" is a filter, then we set data->filter to this filter
431 * If "tree" is a domain, then this means we have reached the root
432 * of the schedule tree without being able to extract any information.
433 * We therefore initialize data->filter to the universe of the domain,
434 * or the domain itself if data->universe_domain is not set.
435 * If "tree" is a band with at least one member, then we set data->filter
436 * to the universe of the schedule domain and replace the zero-dimensional
437 * data->prefix by the band schedule (if data->collect_prefix is set).
439 static int collect_filter_prefix_init(__isl_keep isl_schedule_tree
*tree
,
440 struct isl_schedule_node_get_filter_prefix_data
*data
)
442 enum isl_schedule_node_type type
;
443 isl_multi_union_pw_aff
*mupa
;
444 isl_union_set
*filter
;
446 type
= isl_schedule_tree_get_type(tree
);
448 case isl_schedule_node_error
:
450 case isl_schedule_node_expansion
:
451 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
452 "should be handled by caller", return -1);
453 case isl_schedule_node_extension
:
454 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
455 "cannot handle extension nodes", return -1);
456 case isl_schedule_node_context
:
457 case isl_schedule_node_leaf
:
458 case isl_schedule_node_guard
:
459 case isl_schedule_node_mark
:
460 case isl_schedule_node_sequence
:
461 case isl_schedule_node_set
:
463 case isl_schedule_node_domain
:
464 filter
= isl_schedule_tree_domain_get_domain(tree
);
465 if (data
->universe_domain
)
466 filter
= isl_union_set_universe(filter
);
467 data
->filter
= filter
;
469 case isl_schedule_node_band
:
470 if (isl_schedule_tree_band_n_member(tree
) == 0)
472 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
473 if (data
->collect_prefix
) {
474 isl_multi_union_pw_aff_free(data
->prefix
);
475 mupa
= isl_multi_union_pw_aff_reset_tuple_id(mupa
,
477 data
->prefix
= isl_multi_union_pw_aff_copy(mupa
);
479 filter
= isl_multi_union_pw_aff_domain(mupa
);
480 filter
= isl_union_set_universe(filter
);
481 data
->filter
= filter
;
483 case isl_schedule_node_filter
:
484 filter
= isl_schedule_tree_filter_get_filter(tree
);
485 if (data
->universe_filter
)
486 filter
= isl_union_set_universe(filter
);
487 data
->filter
= filter
;
491 if ((data
->collect_prefix
&& !data
->prefix
) || !data
->filter
)
494 data
->initialized
= 1;
499 /* Update "data" based on the tree node "tree" in case "data" has
500 * already been initialized.
502 * Return 0 on success and -1 on error.
504 * If "tree" is a domain and data->universe_domain is not set, then
505 * intersect data->filter with the domain.
506 * If "tree" is a filter, then we intersect data->filter with this filter
508 * If "tree" is a band with at least one member and data->collect_prefix
509 * is set, then we extend data->prefix with the band schedule.
510 * If "tree" is an extension, then we make sure that we are not collecting
511 * information on any extended domain elements.
513 static int collect_filter_prefix_update(__isl_keep isl_schedule_tree
*tree
,
514 struct isl_schedule_node_get_filter_prefix_data
*data
)
516 enum isl_schedule_node_type type
;
517 isl_multi_union_pw_aff
*mupa
;
518 isl_union_set
*filter
;
519 isl_union_map
*extension
;
522 type
= isl_schedule_tree_get_type(tree
);
524 case isl_schedule_node_error
:
526 case isl_schedule_node_expansion
:
527 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
528 "should be handled by caller", return -1);
529 case isl_schedule_node_extension
:
530 extension
= isl_schedule_tree_extension_get_extension(tree
);
531 extension
= isl_union_map_intersect_range(extension
,
532 isl_union_set_copy(data
->filter
));
533 empty
= isl_union_map_is_empty(extension
);
534 isl_union_map_free(extension
);
539 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
540 "cannot handle extension nodes", return -1);
541 case isl_schedule_node_context
:
542 case isl_schedule_node_leaf
:
543 case isl_schedule_node_guard
:
544 case isl_schedule_node_mark
:
545 case isl_schedule_node_sequence
:
546 case isl_schedule_node_set
:
548 case isl_schedule_node_domain
:
549 if (data
->universe_domain
)
551 filter
= isl_schedule_tree_domain_get_domain(tree
);
552 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
554 case isl_schedule_node_band
:
555 if (isl_schedule_tree_band_n_member(tree
) == 0)
557 if (!data
->collect_prefix
)
559 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
560 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(mupa
,
565 case isl_schedule_node_filter
:
566 filter
= isl_schedule_tree_filter_get_filter(tree
);
567 if (data
->universe_filter
)
568 filter
= isl_union_set_universe(filter
);
569 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
578 /* Collect filter and/or prefix information from the first "n"
579 * elements in "list" (which represent the ancestors of a node).
580 * Store the results in "data".
582 * Extension nodes are only supported if they do not affect the outcome,
583 * i.e., if we are collecting information on non-extended domain elements,
584 * or if we are collecting the universe domain (without prefix).
586 * Return 0 on success and -1 on error.
588 * We traverse the list from innermost ancestor (last element)
589 * to outermost ancestor (first element), calling collect_filter_prefix_init
590 * on each node as long as we have not been able to extract any information
591 * yet and collect_filter_prefix_update afterwards.
592 * If we come across an expansion node, then we interrupt the traversal
593 * and call collect_filter_prefix_expansion to restart the traversal
594 * over the remaining ancestors and to combine the results with those
595 * that have already been collected.
596 * If we come across an extension node and we are only computing
597 * the universe domain, then we interrupt the traversal and call
598 * collect_universe_domain_extension to restart the traversal
599 * over the remaining ancestors and to combine the results with those
600 * that have already been collected.
601 * On successful return, data->initialized will be set since the outermost
602 * ancestor is a domain node, which always results in an initialization.
604 static int collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
605 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
)
612 for (i
= n
- 1; i
>= 0; --i
) {
613 isl_schedule_tree
*tree
;
614 enum isl_schedule_node_type type
;
617 tree
= isl_schedule_tree_list_get_schedule_tree(list
, i
);
620 type
= isl_schedule_tree_get_type(tree
);
621 if (type
== isl_schedule_node_expansion
)
622 return collect_filter_prefix_expansion(tree
, list
, i
,
624 if (type
== isl_schedule_node_extension
&&
625 data
->universe_domain
&& !data
->collect_prefix
)
626 return collect_universe_domain_extension(tree
, list
, i
,
628 if (!data
->initialized
)
629 r
= collect_filter_prefix_init(tree
, data
);
631 r
= collect_filter_prefix_update(tree
, data
);
632 isl_schedule_tree_free(tree
);
640 /* Return the concatenation of the partial schedules of all outer band
641 * nodes of "node" interesected with all outer filters
642 * as an isl_multi_union_pw_aff.
643 * None of the ancestors of "node" may be an extension node, unless
644 * there is also a filter ancestor that filters out all the extended
647 * If "node" is pointing at the root of the schedule tree, then
648 * there are no domain elements reaching the current node, so
649 * we return an empty result.
651 * We collect all the filters and partial schedules in collect_filter_prefix
652 * and intersect the domain of the combined schedule with the combined filter.
654 __isl_give isl_multi_union_pw_aff
*
655 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(
656 __isl_keep isl_schedule_node
*node
)
660 struct isl_schedule_node_get_filter_prefix_data data
;
665 space
= isl_schedule_get_space(node
->schedule
);
666 space
= isl_space_set_from_params(space
);
667 if (node
->tree
== node
->schedule
->root
)
668 return isl_multi_union_pw_aff_zero(space
);
670 data
.initialized
= 0;
671 data
.universe_domain
= 1;
672 data
.universe_filter
= 0;
673 data
.collect_prefix
= 1;
675 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
677 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
678 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
679 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
681 data
.prefix
= isl_multi_union_pw_aff_intersect_domain(data
.prefix
,
687 /* Return the concatenation of the partial schedules of all outer band
688 * nodes of "node" interesected with all outer filters
689 * as an isl_union_pw_multi_aff.
690 * None of the ancestors of "node" may be an extension node, unless
691 * there is also a filter ancestor that filters out all the extended
694 * If "node" is pointing at the root of the schedule tree, then
695 * there are no domain elements reaching the current node, so
696 * we return an empty result.
698 * We collect all the filters and partial schedules in collect_filter_prefix.
699 * The partial schedules are collected as an isl_multi_union_pw_aff.
700 * If this isl_multi_union_pw_aff is zero-dimensional, then it does not
701 * contain any domain information, so we construct the isl_union_pw_multi_aff
702 * result as a zero-dimensional function on the collected filter.
703 * Otherwise, we convert the isl_multi_union_pw_aff to
704 * an isl_multi_union_pw_aff and intersect the domain with the filter.
706 __isl_give isl_union_pw_multi_aff
*
707 isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(
708 __isl_keep isl_schedule_node
*node
)
712 isl_union_pw_multi_aff
*prefix
;
713 struct isl_schedule_node_get_filter_prefix_data data
;
718 space
= isl_schedule_get_space(node
->schedule
);
719 if (node
->tree
== node
->schedule
->root
)
720 return isl_union_pw_multi_aff_empty(space
);
722 space
= isl_space_set_from_params(space
);
723 data
.initialized
= 0;
724 data
.universe_domain
= 1;
725 data
.universe_filter
= 0;
726 data
.collect_prefix
= 1;
728 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
730 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
731 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
732 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
735 isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
) == 0) {
736 isl_multi_union_pw_aff_free(data
.prefix
);
737 prefix
= isl_union_pw_multi_aff_from_domain(data
.filter
);
740 isl_union_pw_multi_aff_from_multi_union_pw_aff(data
.prefix
);
741 prefix
= isl_union_pw_multi_aff_intersect_domain(prefix
,
748 /* Return the concatenation of the partial schedules of all outer band
749 * nodes of "node" interesected with all outer filters
750 * as an isl_union_map.
752 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_union_map(
753 __isl_keep isl_schedule_node
*node
)
755 isl_union_pw_multi_aff
*upma
;
757 upma
= isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(node
);
758 return isl_union_map_from_union_pw_multi_aff(upma
);
761 /* Return the concatenation of the partial schedules of all outer band
762 * nodes of "node" intersected with all outer domain constraints.
763 * None of the ancestors of "node" may be an extension node, unless
764 * there is also a filter ancestor that filters out all the extended
767 * Essentially, this function intersects the domain of the output
768 * of isl_schedule_node_get_prefix_schedule_union_map with the output
769 * of isl_schedule_node_get_domain, except that it only traverses
770 * the ancestors of "node" once.
772 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_relation(
773 __isl_keep isl_schedule_node
*node
)
777 isl_union_map
*prefix
;
778 struct isl_schedule_node_get_filter_prefix_data data
;
783 space
= isl_schedule_get_space(node
->schedule
);
784 if (node
->tree
== node
->schedule
->root
)
785 return isl_union_map_empty(space
);
787 space
= isl_space_set_from_params(space
);
788 data
.initialized
= 0;
789 data
.universe_domain
= 0;
790 data
.universe_filter
= 0;
791 data
.collect_prefix
= 1;
793 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
795 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
796 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
797 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
800 isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
) == 0) {
801 isl_multi_union_pw_aff_free(data
.prefix
);
802 prefix
= isl_union_map_from_domain(data
.filter
);
804 prefix
= isl_union_map_from_multi_union_pw_aff(data
.prefix
);
805 prefix
= isl_union_map_intersect_domain(prefix
, data
.filter
);
811 /* Return the domain elements that reach "node".
813 * If "node" is pointing at the root of the schedule tree, then
814 * there are no domain elements reaching the current node, so
815 * we return an empty result.
816 * None of the ancestors of "node" may be an extension node, unless
817 * there is also a filter ancestor that filters out all the extended
820 * Otherwise, we collect all filters reaching the node,
821 * intersected with the root domain in collect_filter_prefix.
823 __isl_give isl_union_set
*isl_schedule_node_get_domain(
824 __isl_keep isl_schedule_node
*node
)
827 struct isl_schedule_node_get_filter_prefix_data data
;
832 if (node
->tree
== node
->schedule
->root
) {
835 space
= isl_schedule_get_space(node
->schedule
);
836 return isl_union_set_empty(space
);
839 data
.initialized
= 0;
840 data
.universe_domain
= 0;
841 data
.universe_filter
= 0;
842 data
.collect_prefix
= 0;
846 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
847 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
848 data
.filter
= isl_union_set_free(data
.filter
);
853 /* Return the union of universe sets of the domain elements that reach "node".
855 * If "node" is pointing at the root of the schedule tree, then
856 * there are no domain elements reaching the current node, so
857 * we return an empty result.
859 * Otherwise, we collect the universes of all filters reaching the node
860 * in collect_filter_prefix.
862 __isl_give isl_union_set
*isl_schedule_node_get_universe_domain(
863 __isl_keep isl_schedule_node
*node
)
866 struct isl_schedule_node_get_filter_prefix_data data
;
871 if (node
->tree
== node
->schedule
->root
) {
874 space
= isl_schedule_get_space(node
->schedule
);
875 return isl_union_set_empty(space
);
878 data
.initialized
= 0;
879 data
.universe_domain
= 1;
880 data
.universe_filter
= 1;
881 data
.collect_prefix
= 0;
885 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
886 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
887 data
.filter
= isl_union_set_free(data
.filter
);
892 /* Return the subtree schedule of "node".
894 * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle
895 * trees that do not contain any schedule information, we first
896 * move down to the first relevant descendant and handle leaves ourselves.
898 * If the subtree rooted at "node" contains any expansion nodes, then
899 * the returned subtree schedule is formulated in terms of the expanded
901 * The subtree is not allowed to contain any extension nodes.
903 __isl_give isl_union_map
*isl_schedule_node_get_subtree_schedule_union_map(
904 __isl_keep isl_schedule_node
*node
)
906 isl_schedule_tree
*tree
, *leaf
;
909 tree
= isl_schedule_node_get_tree(node
);
910 leaf
= isl_schedule_node_peek_leaf(node
);
911 tree
= isl_schedule_tree_first_schedule_descendant(tree
, leaf
);
915 isl_union_set
*domain
;
916 domain
= isl_schedule_node_get_universe_domain(node
);
917 isl_schedule_tree_free(tree
);
918 return isl_union_map_from_domain(domain
);
921 umap
= isl_schedule_tree_get_subtree_schedule_union_map(tree
);
922 isl_schedule_tree_free(tree
);
926 /* Return the number of ancestors of "node" in its schedule tree.
928 int isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node
*node
)
932 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
935 /* Does "node" have a parent?
937 * That is, does it point to any node of the schedule other than the root?
939 isl_bool
isl_schedule_node_has_parent(__isl_keep isl_schedule_node
*node
)
942 return isl_bool_error
;
943 if (!node
->ancestors
)
944 return isl_bool_error
;
946 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) != 0;
949 /* Return the position of "node" among the children of its parent.
951 int isl_schedule_node_get_child_position(__isl_keep isl_schedule_node
*node
)
958 has_parent
= isl_schedule_node_has_parent(node
);
962 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
963 "node has no parent", return -1);
965 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
966 return node
->child_pos
[n
- 1];
969 /* Does the parent (if any) of "node" have any children with a smaller child
970 * position than this one?
972 isl_bool
isl_schedule_node_has_previous_sibling(
973 __isl_keep isl_schedule_node
*node
)
979 return isl_bool_error
;
980 has_parent
= isl_schedule_node_has_parent(node
);
981 if (has_parent
< 0 || !has_parent
)
984 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
986 return node
->child_pos
[n
- 1] > 0;
989 /* Does the parent (if any) of "node" have any children with a greater child
990 * position than this one?
992 isl_bool
isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node
*node
)
996 isl_schedule_tree
*tree
;
999 return isl_bool_error
;
1000 has_parent
= isl_schedule_node_has_parent(node
);
1001 if (has_parent
< 0 || !has_parent
)
1004 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1005 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
1007 return isl_bool_error
;
1008 n_child
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1009 isl_schedule_tree_free(tree
);
1011 return node
->child_pos
[n
- 1] + 1 < n_child
;
1014 /* Does "node" have any children?
1016 * Any node other than the leaf nodes is considered to have at least
1017 * one child, even if the corresponding isl_schedule_tree does not
1018 * have any children.
1020 isl_bool
isl_schedule_node_has_children(__isl_keep isl_schedule_node
*node
)
1023 return isl_bool_error
;
1024 return !isl_schedule_tree_is_leaf(node
->tree
);
1027 /* Return the number of children of "node"?
1029 * Any node other than the leaf nodes is considered to have at least
1030 * one child, even if the corresponding isl_schedule_tree does not
1031 * have any children. That is, the number of children of "node" is
1032 * only zero if its tree is the explicit empty tree. Otherwise,
1033 * if the isl_schedule_tree has any children, then it is equal
1034 * to the number of children of "node". If it has zero children,
1035 * then "node" still has a leaf node as child.
1037 int isl_schedule_node_n_children(__isl_keep isl_schedule_node
*node
)
1044 if (isl_schedule_tree_is_leaf(node
->tree
))
1047 n
= isl_schedule_tree_n_children(node
->tree
);
1054 /* Move the "node" pointer to the ancestor of the given generation
1055 * of the node it currently points to, where generation 0 is the node
1056 * itself and generation 1 is its parent.
1058 __isl_give isl_schedule_node
*isl_schedule_node_ancestor(
1059 __isl_take isl_schedule_node
*node
, int generation
)
1062 isl_schedule_tree
*tree
;
1066 if (generation
== 0)
1068 n
= isl_schedule_node_get_tree_depth(node
);
1070 return isl_schedule_node_free(node
);
1071 if (generation
< 0 || generation
> n
)
1072 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1073 "generation out of bounds",
1074 return isl_schedule_node_free(node
));
1075 node
= isl_schedule_node_cow(node
);
1079 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1081 isl_schedule_tree_free(node
->tree
);
1083 node
->ancestors
= isl_schedule_tree_list_drop(node
->ancestors
,
1084 n
- generation
, generation
);
1085 if (!node
->ancestors
|| !node
->tree
)
1086 return isl_schedule_node_free(node
);
1091 /* Move the "node" pointer to the parent of the node it currently points to.
1093 __isl_give isl_schedule_node
*isl_schedule_node_parent(
1094 __isl_take isl_schedule_node
*node
)
1098 if (!isl_schedule_node_has_parent(node
))
1099 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1100 "node has no parent",
1101 return isl_schedule_node_free(node
));
1102 return isl_schedule_node_ancestor(node
, 1);
1105 /* Move the "node" pointer to the root of its schedule tree.
1107 __isl_give isl_schedule_node
*isl_schedule_node_root(
1108 __isl_take isl_schedule_node
*node
)
1114 n
= isl_schedule_node_get_tree_depth(node
);
1116 return isl_schedule_node_free(node
);
1117 return isl_schedule_node_ancestor(node
, n
);
1120 /* Move the "node" pointer to the child at position "pos" of the node
1121 * it currently points to.
1123 __isl_give isl_schedule_node
*isl_schedule_node_child(
1124 __isl_take isl_schedule_node
*node
, int pos
)
1128 isl_schedule_tree
*tree
;
1131 node
= isl_schedule_node_cow(node
);
1134 if (!isl_schedule_node_has_children(node
))
1135 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1136 "node has no children",
1137 return isl_schedule_node_free(node
));
1139 ctx
= isl_schedule_node_get_ctx(node
);
1140 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1141 child_pos
= isl_realloc_array(ctx
, node
->child_pos
, int, n
+ 1);
1143 return isl_schedule_node_free(node
);
1144 node
->child_pos
= child_pos
;
1145 node
->child_pos
[n
] = pos
;
1147 node
->ancestors
= isl_schedule_tree_list_add(node
->ancestors
,
1148 isl_schedule_tree_copy(node
->tree
));
1150 if (isl_schedule_tree_has_children(tree
))
1151 tree
= isl_schedule_tree_get_child(tree
, pos
);
1153 tree
= isl_schedule_node_get_leaf(node
);
1154 isl_schedule_tree_free(node
->tree
);
1157 if (!node
->tree
|| !node
->ancestors
)
1158 return isl_schedule_node_free(node
);
1163 /* Move the "node" pointer to the first child of the node
1164 * it currently points to.
1166 __isl_give isl_schedule_node
*isl_schedule_node_first_child(
1167 __isl_take isl_schedule_node
*node
)
1169 return isl_schedule_node_child(node
, 0);
1172 /* Move the "node" pointer to the child of this node's parent in
1173 * the previous child position.
1175 __isl_give isl_schedule_node
*isl_schedule_node_previous_sibling(
1176 __isl_take isl_schedule_node
*node
)
1179 isl_schedule_tree
*parent
, *tree
;
1181 node
= isl_schedule_node_cow(node
);
1184 if (!isl_schedule_node_has_previous_sibling(node
))
1185 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1186 "node has no previous sibling",
1187 return isl_schedule_node_free(node
));
1189 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1190 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1193 return isl_schedule_node_free(node
);
1194 node
->child_pos
[n
- 1]--;
1195 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1196 node
->child_pos
[n
- 1]);
1197 isl_schedule_tree_free(parent
);
1199 return isl_schedule_node_free(node
);
1200 isl_schedule_tree_free(node
->tree
);
1206 /* Move the "node" pointer to the child of this node's parent in
1207 * the next child position.
1209 __isl_give isl_schedule_node
*isl_schedule_node_next_sibling(
1210 __isl_take isl_schedule_node
*node
)
1213 isl_schedule_tree
*parent
, *tree
;
1215 node
= isl_schedule_node_cow(node
);
1218 if (!isl_schedule_node_has_next_sibling(node
))
1219 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1220 "node has no next sibling",
1221 return isl_schedule_node_free(node
));
1223 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1224 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1227 return isl_schedule_node_free(node
);
1228 node
->child_pos
[n
- 1]++;
1229 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1230 node
->child_pos
[n
- 1]);
1231 isl_schedule_tree_free(parent
);
1233 return isl_schedule_node_free(node
);
1234 isl_schedule_tree_free(node
->tree
);
1240 /* Return a copy to the child at position "pos" of "node".
1242 __isl_give isl_schedule_node
*isl_schedule_node_get_child(
1243 __isl_keep isl_schedule_node
*node
, int pos
)
1245 return isl_schedule_node_child(isl_schedule_node_copy(node
), pos
);
1248 /* Traverse the descendant of "node" in depth-first order, including
1249 * "node" itself. Call "enter" whenever a node is entered and "leave"
1250 * whenever a node is left. The callback "enter" is responsible
1251 * for moving to the deepest initial subtree of its argument that
1252 * should be traversed.
1254 static __isl_give isl_schedule_node
*traverse(
1255 __isl_take isl_schedule_node
*node
,
1256 __isl_give isl_schedule_node
*(*enter
)(
1257 __isl_take isl_schedule_node
*node
, void *user
),
1258 __isl_give isl_schedule_node
*(*leave
)(
1259 __isl_take isl_schedule_node
*node
, void *user
),
1267 depth
= isl_schedule_node_get_tree_depth(node
);
1269 node
= enter(node
, user
);
1270 node
= leave(node
, user
);
1271 while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
&&
1272 !isl_schedule_node_has_next_sibling(node
)) {
1273 node
= isl_schedule_node_parent(node
);
1274 node
= leave(node
, user
);
1276 if (node
&& isl_schedule_node_get_tree_depth(node
) > depth
)
1277 node
= isl_schedule_node_next_sibling(node
);
1278 } while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
);
1283 /* Internal data structure for isl_schedule_node_foreach_descendant_top_down.
1285 * "fn" is the user-specified callback function.
1286 * "user" is the user-specified argument for the callback.
1288 struct isl_schedule_node_preorder_data
{
1289 isl_bool (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
);
1293 /* Callback for "traverse" to enter a node and to move
1294 * to the deepest initial subtree that should be traversed
1295 * for use in a preorder visit.
1297 * If the user callback returns a negative value, then we abort
1298 * the traversal. If this callback returns zero, then we skip
1299 * the subtree rooted at the current node. Otherwise, we move
1300 * down to the first child and repeat the process until a leaf
1303 static __isl_give isl_schedule_node
*preorder_enter(
1304 __isl_take isl_schedule_node
*node
, void *user
)
1306 struct isl_schedule_node_preorder_data
*data
= user
;
1314 r
= data
->fn(node
, data
->user
);
1316 return isl_schedule_node_free(node
);
1317 if (r
== isl_bool_false
)
1319 } while (isl_schedule_node_has_children(node
) &&
1320 (node
= isl_schedule_node_first_child(node
)) != NULL
);
1325 /* Callback for "traverse" to leave a node
1326 * for use in a preorder visit.
1327 * Since we already visited the node when we entered it,
1328 * we do not need to do anything here.
1330 static __isl_give isl_schedule_node
*preorder_leave(
1331 __isl_take isl_schedule_node
*node
, void *user
)
1336 /* Traverse the descendants of "node" (including the node itself)
1337 * in depth first preorder.
1339 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1340 * If "fn" returns 0 on any of the nodes, then the subtree rooted
1341 * at that node is skipped.
1343 * Return 0 on success and -1 on failure.
1345 isl_stat
isl_schedule_node_foreach_descendant_top_down(
1346 __isl_keep isl_schedule_node
*node
,
1347 isl_bool (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
),
1350 struct isl_schedule_node_preorder_data data
= { fn
, user
};
1352 node
= isl_schedule_node_copy(node
);
1353 node
= traverse(node
, &preorder_enter
, &preorder_leave
, &data
);
1354 isl_schedule_node_free(node
);
1356 return node
? isl_stat_ok
: isl_stat_error
;
1359 /* Internal data structure for isl_schedule_node_map_descendant_bottom_up.
1361 * "fn" is the user-specified callback function.
1362 * "user" is the user-specified argument for the callback.
1364 struct isl_schedule_node_postorder_data
{
1365 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1370 /* Callback for "traverse" to enter a node and to move
1371 * to the deepest initial subtree that should be traversed
1372 * for use in a postorder visit.
1374 * Since we are performing a postorder visit, we only need
1375 * to move to the deepest initial leaf here.
1377 static __isl_give isl_schedule_node
*postorder_enter(
1378 __isl_take isl_schedule_node
*node
, void *user
)
1380 while (node
&& isl_schedule_node_has_children(node
))
1381 node
= isl_schedule_node_first_child(node
);
1386 /* Callback for "traverse" to leave a node
1387 * for use in a postorder visit.
1389 * Since we are performing a postorder visit, we need
1390 * to call the user callback here.
1392 static __isl_give isl_schedule_node
*postorder_leave(
1393 __isl_take isl_schedule_node
*node
, void *user
)
1395 struct isl_schedule_node_postorder_data
*data
= user
;
1397 return data
->fn(node
, data
->user
);
1400 /* Traverse the descendants of "node" (including the node itself)
1401 * in depth first postorder, allowing the user to modify the visited node.
1402 * The traversal continues from the node returned by the callback function.
1403 * It is the responsibility of the user to ensure that this does not
1404 * lead to an infinite loop. It is safest to always return a pointer
1405 * to the same position (same ancestors and child positions) as the input node.
1407 __isl_give isl_schedule_node
*isl_schedule_node_map_descendant_bottom_up(
1408 __isl_take isl_schedule_node
*node
,
1409 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1410 void *user
), void *user
)
1412 struct isl_schedule_node_postorder_data data
= { fn
, user
};
1414 return traverse(node
, &postorder_enter
, &postorder_leave
, &data
);
1417 /* Traverse the ancestors of "node" from the root down to and including
1418 * the parent of "node", calling "fn" on each of them.
1420 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1422 * Return 0 on success and -1 on failure.
1424 isl_stat
isl_schedule_node_foreach_ancestor_top_down(
1425 __isl_keep isl_schedule_node
*node
,
1426 isl_stat (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
),
1432 return isl_stat_error
;
1434 n
= isl_schedule_node_get_tree_depth(node
);
1435 for (i
= 0; i
< n
; ++i
) {
1436 isl_schedule_node
*ancestor
;
1439 ancestor
= isl_schedule_node_copy(node
);
1440 ancestor
= isl_schedule_node_ancestor(ancestor
, n
- i
);
1441 r
= fn(ancestor
, user
);
1442 isl_schedule_node_free(ancestor
);
1444 return isl_stat_error
;
1450 /* Is any node in the subtree rooted at "node" anchored?
1451 * That is, do any of these nodes reference the outer band nodes?
1453 isl_bool
isl_schedule_node_is_subtree_anchored(
1454 __isl_keep isl_schedule_node
*node
)
1457 return isl_bool_error
;
1458 return isl_schedule_tree_is_subtree_anchored(node
->tree
);
1461 /* Return the number of members in the given band node.
1463 unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node
*node
)
1465 return node
? isl_schedule_tree_band_n_member(node
->tree
) : 0;
1468 /* Is the band member at position "pos" of the band node "node"
1469 * marked coincident?
1471 isl_bool
isl_schedule_node_band_member_get_coincident(
1472 __isl_keep isl_schedule_node
*node
, int pos
)
1475 return isl_bool_error
;
1476 return isl_schedule_tree_band_member_get_coincident(node
->tree
, pos
);
1479 /* Mark the band member at position "pos" the band node "node"
1480 * as being coincident or not according to "coincident".
1482 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_coincident(
1483 __isl_take isl_schedule_node
*node
, int pos
, int coincident
)
1486 isl_schedule_tree
*tree
;
1490 c
= isl_schedule_node_band_member_get_coincident(node
, pos
);
1491 if (c
== coincident
)
1494 tree
= isl_schedule_tree_copy(node
->tree
);
1495 tree
= isl_schedule_tree_band_member_set_coincident(tree
, pos
,
1497 node
= isl_schedule_node_graft_tree(node
, tree
);
1502 /* Is the band node "node" marked permutable?
1504 isl_bool
isl_schedule_node_band_get_permutable(
1505 __isl_keep isl_schedule_node
*node
)
1508 return isl_bool_error
;
1510 return isl_schedule_tree_band_get_permutable(node
->tree
);
1513 /* Mark the band node "node" permutable or not according to "permutable"?
1515 __isl_give isl_schedule_node
*isl_schedule_node_band_set_permutable(
1516 __isl_take isl_schedule_node
*node
, int permutable
)
1518 isl_schedule_tree
*tree
;
1522 if (isl_schedule_node_band_get_permutable(node
) == permutable
)
1525 tree
= isl_schedule_tree_copy(node
->tree
);
1526 tree
= isl_schedule_tree_band_set_permutable(tree
, permutable
);
1527 node
= isl_schedule_node_graft_tree(node
, tree
);
1532 /* Return the schedule space of the band node.
1534 __isl_give isl_space
*isl_schedule_node_band_get_space(
1535 __isl_keep isl_schedule_node
*node
)
1540 return isl_schedule_tree_band_get_space(node
->tree
);
1543 /* Return the schedule of the band node in isolation.
1545 __isl_give isl_multi_union_pw_aff
*isl_schedule_node_band_get_partial_schedule(
1546 __isl_keep isl_schedule_node
*node
)
1551 return isl_schedule_tree_band_get_partial_schedule(node
->tree
);
1554 /* Return the schedule of the band node in isolation in the form of
1557 * If the band does not have any members, then we construct a universe map
1558 * with the universe of the domain elements reaching the node as domain.
1559 * Otherwise, we extract an isl_multi_union_pw_aff representation and
1560 * convert that to an isl_union_map.
1562 __isl_give isl_union_map
*isl_schedule_node_band_get_partial_schedule_union_map(
1563 __isl_keep isl_schedule_node
*node
)
1565 isl_multi_union_pw_aff
*mupa
;
1570 if (isl_schedule_node_get_type(node
) != isl_schedule_node_band
)
1571 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1572 "not a band node", return NULL
);
1573 if (isl_schedule_node_band_n_member(node
) == 0) {
1574 isl_union_set
*domain
;
1576 domain
= isl_schedule_node_get_universe_domain(node
);
1577 return isl_union_map_from_domain(domain
);
1580 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
1581 return isl_union_map_from_multi_union_pw_aff(mupa
);
1584 /* Return the loop AST generation type for the band member of band node "node"
1585 * at position "pos".
1587 enum isl_ast_loop_type
isl_schedule_node_band_member_get_ast_loop_type(
1588 __isl_keep isl_schedule_node
*node
, int pos
)
1591 return isl_ast_loop_error
;
1593 return isl_schedule_tree_band_member_get_ast_loop_type(node
->tree
, pos
);
1596 /* Set the loop AST generation type for the band member of band node "node"
1597 * at position "pos" to "type".
1599 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_ast_loop_type(
1600 __isl_take isl_schedule_node
*node
, int pos
,
1601 enum isl_ast_loop_type type
)
1603 isl_schedule_tree
*tree
;
1608 tree
= isl_schedule_tree_copy(node
->tree
);
1609 tree
= isl_schedule_tree_band_member_set_ast_loop_type(tree
, pos
, type
);
1610 return isl_schedule_node_graft_tree(node
, tree
);
1613 /* Return the loop AST generation type for the band member of band node "node"
1614 * at position "pos" for the isolated part.
1616 enum isl_ast_loop_type
isl_schedule_node_band_member_get_isolate_ast_loop_type(
1617 __isl_keep isl_schedule_node
*node
, int pos
)
1620 return isl_ast_loop_error
;
1622 return isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1626 /* Set the loop AST generation type for the band member of band node "node"
1627 * at position "pos" for the isolated part to "type".
1629 __isl_give isl_schedule_node
*
1630 isl_schedule_node_band_member_set_isolate_ast_loop_type(
1631 __isl_take isl_schedule_node
*node
, int pos
,
1632 enum isl_ast_loop_type type
)
1634 isl_schedule_tree
*tree
;
1639 tree
= isl_schedule_tree_copy(node
->tree
);
1640 tree
= isl_schedule_tree_band_member_set_isolate_ast_loop_type(tree
,
1642 return isl_schedule_node_graft_tree(node
, tree
);
1645 /* Return the AST build options associated to band node "node".
1647 __isl_give isl_union_set
*isl_schedule_node_band_get_ast_build_options(
1648 __isl_keep isl_schedule_node
*node
)
1653 return isl_schedule_tree_band_get_ast_build_options(node
->tree
);
1656 /* Replace the AST build options associated to band node "node" by "options".
1658 __isl_give isl_schedule_node
*isl_schedule_node_band_set_ast_build_options(
1659 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*options
)
1661 isl_schedule_tree
*tree
;
1663 if (!node
|| !options
)
1666 tree
= isl_schedule_tree_copy(node
->tree
);
1667 tree
= isl_schedule_tree_band_set_ast_build_options(tree
, options
);
1668 return isl_schedule_node_graft_tree(node
, tree
);
1670 isl_schedule_node_free(node
);
1671 isl_union_set_free(options
);
1675 /* Return the "isolate" option associated to band node "node".
1677 __isl_give isl_set
*isl_schedule_node_band_get_ast_isolate_option(
1678 __isl_keep isl_schedule_node
*node
)
1685 depth
= isl_schedule_node_get_schedule_depth(node
);
1686 return isl_schedule_tree_band_get_ast_isolate_option(node
->tree
, depth
);
1689 /* Make sure that that spaces of "node" and "mv" are the same.
1690 * Return -1 on error, reporting the error to the user.
1692 static int check_space_multi_val(__isl_keep isl_schedule_node
*node
,
1693 __isl_keep isl_multi_val
*mv
)
1695 isl_space
*node_space
, *mv_space
;
1698 node_space
= isl_schedule_node_band_get_space(node
);
1699 mv_space
= isl_multi_val_get_space(mv
);
1700 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1701 mv_space
, isl_dim_set
);
1702 isl_space_free(mv_space
);
1703 isl_space_free(node_space
);
1707 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1708 "spaces don't match", return -1);
1713 /* Multiply the partial schedule of the band node "node"
1714 * with the factors in "mv".
1716 __isl_give isl_schedule_node
*isl_schedule_node_band_scale(
1717 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1719 isl_schedule_tree
*tree
;
1724 if (check_space_multi_val(node
, mv
) < 0)
1726 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1730 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1731 "cannot scale band node with anchored subtree",
1734 tree
= isl_schedule_node_get_tree(node
);
1735 tree
= isl_schedule_tree_band_scale(tree
, mv
);
1736 return isl_schedule_node_graft_tree(node
, tree
);
1738 isl_multi_val_free(mv
);
1739 isl_schedule_node_free(node
);
1743 /* Divide the partial schedule of the band node "node"
1744 * by the factors in "mv".
1746 __isl_give isl_schedule_node
*isl_schedule_node_band_scale_down(
1747 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1749 isl_schedule_tree
*tree
;
1754 if (check_space_multi_val(node
, mv
) < 0)
1756 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1760 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1761 "cannot scale down band node with anchored subtree",
1764 tree
= isl_schedule_node_get_tree(node
);
1765 tree
= isl_schedule_tree_band_scale_down(tree
, mv
);
1766 return isl_schedule_node_graft_tree(node
, tree
);
1768 isl_multi_val_free(mv
);
1769 isl_schedule_node_free(node
);
1773 /* Reduce the partial schedule of the band node "node"
1774 * modulo the factors in "mv".
1776 __isl_give isl_schedule_node
*isl_schedule_node_band_mod(
1777 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1779 isl_schedule_tree
*tree
;
1784 if (check_space_multi_val(node
, mv
) < 0)
1786 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1790 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1791 "cannot perform mod on band node with anchored subtree",
1794 tree
= isl_schedule_node_get_tree(node
);
1795 tree
= isl_schedule_tree_band_mod(tree
, mv
);
1796 return isl_schedule_node_graft_tree(node
, tree
);
1798 isl_multi_val_free(mv
);
1799 isl_schedule_node_free(node
);
1803 /* Make sure that that spaces of "node" and "mupa" are the same.
1804 * Return isl_stat_error on error, reporting the error to the user.
1806 static isl_stat
check_space_multi_union_pw_aff(
1807 __isl_keep isl_schedule_node
*node
,
1808 __isl_keep isl_multi_union_pw_aff
*mupa
)
1810 isl_space
*node_space
, *mupa_space
;
1813 node_space
= isl_schedule_node_band_get_space(node
);
1814 mupa_space
= isl_multi_union_pw_aff_get_space(mupa
);
1815 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1816 mupa_space
, isl_dim_set
);
1817 isl_space_free(mupa_space
);
1818 isl_space_free(node_space
);
1820 return isl_stat_error
;
1822 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1823 "spaces don't match", return isl_stat_error
);
1828 /* Shift the partial schedule of the band node "node" by "shift".
1830 __isl_give isl_schedule_node
*isl_schedule_node_band_shift(
1831 __isl_take isl_schedule_node
*node
,
1832 __isl_take isl_multi_union_pw_aff
*shift
)
1834 isl_schedule_tree
*tree
;
1837 if (!node
|| !shift
)
1839 if (check_space_multi_union_pw_aff(node
, shift
) < 0)
1841 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1845 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1846 "cannot shift band node with anchored subtree",
1849 tree
= isl_schedule_node_get_tree(node
);
1850 tree
= isl_schedule_tree_band_shift(tree
, shift
);
1851 return isl_schedule_node_graft_tree(node
, tree
);
1853 isl_multi_union_pw_aff_free(shift
);
1854 isl_schedule_node_free(node
);
1858 /* Tile "node" with tile sizes "sizes".
1860 * The current node is replaced by two nested nodes corresponding
1861 * to the tile dimensions and the point dimensions.
1863 * Return a pointer to the outer (tile) node.
1865 * If any of the descendants of "node" depend on the set of outer band nodes,
1866 * then we refuse to tile the node.
1868 * If the scale tile loops option is set, then the tile loops
1869 * are scaled by the tile sizes. If the shift point loops option is set,
1870 * then the point loops are shifted to start at zero.
1871 * In particular, these options affect the tile and point loop schedules
1874 * scale shift original tile point
1876 * 0 0 i floor(i/s) i
1877 * 1 0 i s * floor(i/s) i
1878 * 0 1 i floor(i/s) i - s * floor(i/s)
1879 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1881 __isl_give isl_schedule_node
*isl_schedule_node_band_tile(
1882 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*sizes
)
1884 isl_schedule_tree
*tree
;
1887 if (!node
|| !sizes
)
1889 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1893 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1894 "cannot tile band node with anchored subtree",
1897 if (check_space_multi_val(node
, sizes
) < 0)
1900 tree
= isl_schedule_node_get_tree(node
);
1901 tree
= isl_schedule_tree_band_tile(tree
, sizes
);
1902 return isl_schedule_node_graft_tree(node
, tree
);
1904 isl_multi_val_free(sizes
);
1905 isl_schedule_node_free(node
);
1909 /* Move the band node "node" down to all the leaves in the subtree
1911 * Return a pointer to the node in the resulting tree that is in the same
1912 * position as the node pointed to by "node" in the original tree.
1914 * If the node only has a leaf child, then nothing needs to be done.
1915 * Otherwise, the child of the node is removed and the result is
1916 * appended to all the leaves in the subtree rooted at the original child.
1917 * Since the node is moved to the leaves, it needs to be expanded
1918 * according to the expansion, if any, defined by that subtree.
1919 * In the end, the original node is replaced by the result of
1920 * attaching copies of the expanded node to the leaves.
1922 * If any of the nodes in the subtree rooted at "node" depend on
1923 * the set of outer band nodes then we refuse to sink the band node.
1925 __isl_give isl_schedule_node
*isl_schedule_node_band_sink(
1926 __isl_take isl_schedule_node
*node
)
1928 enum isl_schedule_node_type type
;
1929 isl_schedule_tree
*tree
, *child
;
1930 isl_union_pw_multi_aff
*contraction
;
1936 type
= isl_schedule_node_get_type(node
);
1937 if (type
!= isl_schedule_node_band
)
1938 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1939 "not a band node", return isl_schedule_node_free(node
));
1940 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1942 return isl_schedule_node_free(node
);
1944 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1945 "cannot sink band node in anchored subtree",
1946 return isl_schedule_node_free(node
));
1947 if (isl_schedule_tree_n_children(node
->tree
) == 0)
1950 contraction
= isl_schedule_node_get_subtree_contraction(node
);
1952 tree
= isl_schedule_node_get_tree(node
);
1953 child
= isl_schedule_tree_get_child(tree
, 0);
1954 tree
= isl_schedule_tree_reset_children(tree
);
1955 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, contraction
);
1956 tree
= isl_schedule_tree_append_to_leaves(child
, tree
);
1958 return isl_schedule_node_graft_tree(node
, tree
);
1961 /* Split "node" into two nested band nodes, one with the first "pos"
1962 * dimensions and one with the remaining dimensions.
1963 * The schedules of the two band nodes live in anonymous spaces.
1964 * The loop AST generation type options and the isolate option
1965 * are split over the the two band nodes.
1967 __isl_give isl_schedule_node
*isl_schedule_node_band_split(
1968 __isl_take isl_schedule_node
*node
, int pos
)
1971 isl_schedule_tree
*tree
;
1973 depth
= isl_schedule_node_get_schedule_depth(node
);
1974 tree
= isl_schedule_node_get_tree(node
);
1975 tree
= isl_schedule_tree_band_split(tree
, pos
, depth
);
1976 return isl_schedule_node_graft_tree(node
, tree
);
1979 /* Return the context of the context node "node".
1981 __isl_give isl_set
*isl_schedule_node_context_get_context(
1982 __isl_keep isl_schedule_node
*node
)
1987 return isl_schedule_tree_context_get_context(node
->tree
);
1990 /* Return the domain of the domain node "node".
1992 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
1993 __isl_keep isl_schedule_node
*node
)
1998 return isl_schedule_tree_domain_get_domain(node
->tree
);
2001 /* Return the expansion map of expansion node "node".
2003 __isl_give isl_union_map
*isl_schedule_node_expansion_get_expansion(
2004 __isl_keep isl_schedule_node
*node
)
2009 return isl_schedule_tree_expansion_get_expansion(node
->tree
);
2012 /* Return the contraction of expansion node "node".
2014 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_expansion_get_contraction(
2015 __isl_keep isl_schedule_node
*node
)
2020 return isl_schedule_tree_expansion_get_contraction(node
->tree
);
2023 /* Replace the contraction and the expansion of the expansion node "node"
2024 * by "contraction" and "expansion".
2026 __isl_give isl_schedule_node
*
2027 isl_schedule_node_expansion_set_contraction_and_expansion(
2028 __isl_take isl_schedule_node
*node
,
2029 __isl_take isl_union_pw_multi_aff
*contraction
,
2030 __isl_take isl_union_map
*expansion
)
2032 isl_schedule_tree
*tree
;
2034 if (!node
|| !contraction
|| !expansion
)
2037 tree
= isl_schedule_tree_copy(node
->tree
);
2038 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
2039 contraction
, expansion
);
2040 return isl_schedule_node_graft_tree(node
, tree
);
2042 isl_schedule_node_free(node
);
2043 isl_union_pw_multi_aff_free(contraction
);
2044 isl_union_map_free(expansion
);
2048 /* Return the extension of the extension node "node".
2050 __isl_give isl_union_map
*isl_schedule_node_extension_get_extension(
2051 __isl_keep isl_schedule_node
*node
)
2056 return isl_schedule_tree_extension_get_extension(node
->tree
);
2059 /* Replace the extension of extension node "node" by "extension".
2061 __isl_give isl_schedule_node
*isl_schedule_node_extension_set_extension(
2062 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
2064 isl_schedule_tree
*tree
;
2066 if (!node
|| !extension
)
2069 tree
= isl_schedule_tree_copy(node
->tree
);
2070 tree
= isl_schedule_tree_extension_set_extension(tree
, extension
);
2071 return isl_schedule_node_graft_tree(node
, tree
);
2073 isl_schedule_node_free(node
);
2074 isl_union_map_free(extension
);
2078 /* Return the filter of the filter node "node".
2080 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
2081 __isl_keep isl_schedule_node
*node
)
2086 return isl_schedule_tree_filter_get_filter(node
->tree
);
2089 /* Replace the filter of filter node "node" by "filter".
2091 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
2092 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2094 isl_schedule_tree
*tree
;
2096 if (!node
|| !filter
)
2099 tree
= isl_schedule_tree_copy(node
->tree
);
2100 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
2101 return isl_schedule_node_graft_tree(node
, tree
);
2103 isl_schedule_node_free(node
);
2104 isl_union_set_free(filter
);
2108 /* Intersect the filter of filter node "node" with "filter".
2110 * If the filter of the node is already a subset of "filter",
2111 * then leave the node unchanged.
2113 __isl_give isl_schedule_node
*isl_schedule_node_filter_intersect_filter(
2114 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2116 isl_union_set
*node_filter
= NULL
;
2119 if (!node
|| !filter
)
2122 node_filter
= isl_schedule_node_filter_get_filter(node
);
2123 subset
= isl_union_set_is_subset(node_filter
, filter
);
2127 isl_union_set_free(node_filter
);
2128 isl_union_set_free(filter
);
2131 node_filter
= isl_union_set_intersect(node_filter
, filter
);
2132 node
= isl_schedule_node_filter_set_filter(node
, node_filter
);
2135 isl_schedule_node_free(node
);
2136 isl_union_set_free(node_filter
);
2137 isl_union_set_free(filter
);
2141 /* Return the guard of the guard node "node".
2143 __isl_give isl_set
*isl_schedule_node_guard_get_guard(
2144 __isl_keep isl_schedule_node
*node
)
2149 return isl_schedule_tree_guard_get_guard(node
->tree
);
2152 /* Return the mark identifier of the mark node "node".
2154 __isl_give isl_id
*isl_schedule_node_mark_get_id(
2155 __isl_keep isl_schedule_node
*node
)
2160 return isl_schedule_tree_mark_get_id(node
->tree
);
2163 /* Replace the child at position "pos" of the sequence node "node"
2164 * by the children of sequence root node of "tree".
2166 __isl_give isl_schedule_node
*isl_schedule_node_sequence_splice(
2167 __isl_take isl_schedule_node
*node
, int pos
,
2168 __isl_take isl_schedule_tree
*tree
)
2170 isl_schedule_tree
*node_tree
;
2174 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2175 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2176 "not a sequence node", goto error
);
2177 if (isl_schedule_tree_get_type(tree
) != isl_schedule_node_sequence
)
2178 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2179 "not a sequence node", goto error
);
2180 node_tree
= isl_schedule_node_get_tree(node
);
2181 node_tree
= isl_schedule_tree_sequence_splice(node_tree
, pos
, tree
);
2182 node
= isl_schedule_node_graft_tree(node
, node_tree
);
2186 isl_schedule_node_free(node
);
2187 isl_schedule_tree_free(tree
);
2191 /* Given a sequence node "node", with a child at position "pos" that
2192 * is also a sequence node, attach the children of that node directly
2193 * as children of "node" at that position, replacing the original child.
2195 * The filters of these children are intersected with the filter
2196 * of the child at position "pos".
2198 __isl_give isl_schedule_node
*isl_schedule_node_sequence_splice_child(
2199 __isl_take isl_schedule_node
*node
, int pos
)
2202 isl_union_set
*filter
;
2203 isl_schedule_node
*child
;
2204 isl_schedule_tree
*tree
;
2208 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2209 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2210 "not a sequence node",
2211 return isl_schedule_node_free(node
));
2212 node
= isl_schedule_node_child(node
, pos
);
2213 node
= isl_schedule_node_child(node
, 0);
2214 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2215 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2216 "not a sequence node",
2217 return isl_schedule_node_free(node
));
2218 child
= isl_schedule_node_copy(node
);
2219 node
= isl_schedule_node_parent(node
);
2220 filter
= isl_schedule_node_filter_get_filter(node
);
2221 n
= isl_schedule_node_n_children(child
);
2222 for (i
= 0; i
< n
; ++i
) {
2223 child
= isl_schedule_node_child(child
, i
);
2224 child
= isl_schedule_node_filter_intersect_filter(child
,
2225 isl_union_set_copy(filter
));
2226 child
= isl_schedule_node_parent(child
);
2228 isl_union_set_free(filter
);
2229 tree
= isl_schedule_node_get_tree(child
);
2230 isl_schedule_node_free(child
);
2231 node
= isl_schedule_node_parent(node
);
2232 node
= isl_schedule_node_sequence_splice(node
, pos
, tree
);
2237 /* Update the ancestors of "node" to point to the tree that "node"
2239 * That is, replace the child in the original parent that corresponds
2240 * to the current tree position by node->tree and continue updating
2241 * the ancestors in the same way until the root is reached.
2243 * If "fn" is not NULL, then it is called on each ancestor as we move up
2244 * the tree so that it can modify the ancestor before it is added
2245 * to the list of ancestors of the modified node.
2246 * The additional "pos" argument records the position
2247 * of the "tree" argument in the original schedule tree.
2249 * If "node" originally points to a leaf of the schedule tree, then make sure
2250 * that in the end it points to a leaf in the updated schedule tree.
2252 static __isl_give isl_schedule_node
*update_ancestors(
2253 __isl_take isl_schedule_node
*node
,
2254 __isl_give isl_schedule_tree
*(*fn
)(__isl_take isl_schedule_tree
*tree
,
2255 __isl_keep isl_schedule_node
*pos
, void *user
), void *user
)
2259 isl_schedule_tree
*tree
;
2260 isl_schedule_node
*pos
= NULL
;
2263 pos
= isl_schedule_node_copy(node
);
2265 node
= isl_schedule_node_cow(node
);
2267 return isl_schedule_node_free(pos
);
2269 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
2270 tree
= isl_schedule_tree_copy(node
->tree
);
2272 for (i
= n
- 1; i
>= 0; --i
) {
2273 isl_schedule_tree
*parent
;
2275 parent
= isl_schedule_tree_list_get_schedule_tree(
2276 node
->ancestors
, i
);
2277 parent
= isl_schedule_tree_replace_child(parent
,
2278 node
->child_pos
[i
], tree
);
2280 pos
= isl_schedule_node_parent(pos
);
2281 parent
= fn(parent
, pos
, user
);
2283 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
2284 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
2290 isl_schedule_node_free(pos
);
2292 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
2293 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
2295 isl_schedule_tree_free(node
->tree
);
2296 node
->tree
= isl_schedule_node_get_leaf(node
);
2299 if (!node
->schedule
|| !node
->ancestors
)
2300 return isl_schedule_node_free(node
);
2305 /* Replace the subtree that "pos" points to by "tree", updating
2306 * the ancestors to maintain a consistent state.
2308 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
2309 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
2313 if (pos
->tree
== tree
) {
2314 isl_schedule_tree_free(tree
);
2318 pos
= isl_schedule_node_cow(pos
);
2322 isl_schedule_tree_free(pos
->tree
);
2325 return update_ancestors(pos
, NULL
, NULL
);
2327 isl_schedule_node_free(pos
);
2328 isl_schedule_tree_free(tree
);
2332 /* Make sure we can insert a node between "node" and its parent.
2333 * Return -1 on error, reporting the reason why we cannot insert a node.
2335 static int check_insert(__isl_keep isl_schedule_node
*node
)
2338 enum isl_schedule_node_type type
;
2340 has_parent
= isl_schedule_node_has_parent(node
);
2344 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2345 "cannot insert node outside of root", return -1);
2347 type
= isl_schedule_node_get_parent_type(node
);
2348 if (type
== isl_schedule_node_error
)
2350 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
2351 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2352 "cannot insert node between set or sequence node "
2353 "and its filter children", return -1);
2358 /* Insert a band node with partial schedule "mupa" between "node" and
2360 * Return a pointer to the new band node.
2362 * If any of the nodes in the subtree rooted at "node" depend on
2363 * the set of outer band nodes then we refuse to insert the band node.
2365 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
2366 __isl_take isl_schedule_node
*node
,
2367 __isl_take isl_multi_union_pw_aff
*mupa
)
2370 isl_schedule_band
*band
;
2371 isl_schedule_tree
*tree
;
2373 if (check_insert(node
) < 0)
2374 node
= isl_schedule_node_free(node
);
2375 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2379 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2380 "cannot insert band node in anchored subtree",
2383 tree
= isl_schedule_node_get_tree(node
);
2384 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
2385 tree
= isl_schedule_tree_insert_band(tree
, band
);
2386 node
= isl_schedule_node_graft_tree(node
, tree
);
2390 isl_schedule_node_free(node
);
2391 isl_multi_union_pw_aff_free(mupa
);
2395 /* Insert a context node with context "context" between "node" and its parent.
2396 * Return a pointer to the new context node.
2398 __isl_give isl_schedule_node
*isl_schedule_node_insert_context(
2399 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
2401 isl_schedule_tree
*tree
;
2403 if (check_insert(node
) < 0)
2404 node
= isl_schedule_node_free(node
);
2406 tree
= isl_schedule_node_get_tree(node
);
2407 tree
= isl_schedule_tree_insert_context(tree
, context
);
2408 node
= isl_schedule_node_graft_tree(node
, tree
);
2413 /* Insert an expansion node with the given "contraction" and "expansion"
2414 * between "node" and its parent.
2415 * Return a pointer to the new expansion node.
2417 * Typically the domain and range spaces of the expansion are different.
2418 * This means that only one of them can refer to the current domain space
2419 * in a consistent tree. It is up to the caller to ensure that the tree
2420 * returns to a consistent state.
2422 __isl_give isl_schedule_node
*isl_schedule_node_insert_expansion(
2423 __isl_take isl_schedule_node
*node
,
2424 __isl_take isl_union_pw_multi_aff
*contraction
,
2425 __isl_take isl_union_map
*expansion
)
2427 isl_schedule_tree
*tree
;
2429 if (check_insert(node
) < 0)
2430 node
= isl_schedule_node_free(node
);
2432 tree
= isl_schedule_node_get_tree(node
);
2433 tree
= isl_schedule_tree_insert_expansion(tree
, contraction
, expansion
);
2434 node
= isl_schedule_node_graft_tree(node
, tree
);
2439 /* Insert an extension node with extension "extension" between "node" and
2441 * Return a pointer to the new extension node.
2443 __isl_give isl_schedule_node
*isl_schedule_node_insert_extension(
2444 __isl_take isl_schedule_node
*node
,
2445 __isl_take isl_union_map
*extension
)
2447 isl_schedule_tree
*tree
;
2449 tree
= isl_schedule_node_get_tree(node
);
2450 tree
= isl_schedule_tree_insert_extension(tree
, extension
);
2451 node
= isl_schedule_node_graft_tree(node
, tree
);
2456 /* Insert a filter node with filter "filter" between "node" and its parent.
2457 * Return a pointer to the new filter node.
2459 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
2460 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2462 isl_schedule_tree
*tree
;
2464 if (check_insert(node
) < 0)
2465 node
= isl_schedule_node_free(node
);
2467 tree
= isl_schedule_node_get_tree(node
);
2468 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2469 node
= isl_schedule_node_graft_tree(node
, tree
);
2474 /* Insert a guard node with guard "guard" between "node" and its parent.
2475 * Return a pointer to the new guard node.
2477 __isl_give isl_schedule_node
*isl_schedule_node_insert_guard(
2478 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*guard
)
2480 isl_schedule_tree
*tree
;
2482 if (check_insert(node
) < 0)
2483 node
= isl_schedule_node_free(node
);
2485 tree
= isl_schedule_node_get_tree(node
);
2486 tree
= isl_schedule_tree_insert_guard(tree
, guard
);
2487 node
= isl_schedule_node_graft_tree(node
, tree
);
2492 /* Insert a mark node with mark identifier "mark" between "node" and
2494 * Return a pointer to the new mark node.
2496 __isl_give isl_schedule_node
*isl_schedule_node_insert_mark(
2497 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*mark
)
2499 isl_schedule_tree
*tree
;
2501 if (check_insert(node
) < 0)
2502 node
= isl_schedule_node_free(node
);
2504 tree
= isl_schedule_node_get_tree(node
);
2505 tree
= isl_schedule_tree_insert_mark(tree
, mark
);
2506 node
= isl_schedule_node_graft_tree(node
, tree
);
2511 /* Attach the current subtree of "node" to a sequence of filter tree nodes
2512 * with filters described by "filters", attach this sequence
2513 * of filter tree nodes as children to a new tree of type "type" and
2514 * replace the original subtree of "node" by this new tree.
2515 * Each copy of the original subtree is simplified with respect
2516 * to the corresponding filter.
2518 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
2519 __isl_take isl_schedule_node
*node
,
2520 enum isl_schedule_node_type type
,
2521 __isl_take isl_union_set_list
*filters
)
2525 isl_schedule_tree
*tree
;
2526 isl_schedule_tree_list
*list
;
2528 if (check_insert(node
) < 0)
2529 node
= isl_schedule_node_free(node
);
2531 if (!node
|| !filters
)
2534 ctx
= isl_schedule_node_get_ctx(node
);
2535 n
= isl_union_set_list_n_union_set(filters
);
2536 list
= isl_schedule_tree_list_alloc(ctx
, n
);
2537 for (i
= 0; i
< n
; ++i
) {
2538 isl_schedule_node
*node_i
;
2539 isl_schedule_tree
*tree
;
2540 isl_union_set
*filter
;
2542 filter
= isl_union_set_list_get_union_set(filters
, i
);
2543 node_i
= isl_schedule_node_copy(node
);
2544 node_i
= isl_schedule_node_gist(node_i
,
2545 isl_union_set_copy(filter
));
2546 tree
= isl_schedule_node_get_tree(node_i
);
2547 isl_schedule_node_free(node_i
);
2548 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2549 list
= isl_schedule_tree_list_add(list
, tree
);
2551 tree
= isl_schedule_tree_from_children(type
, list
);
2552 node
= isl_schedule_node_graft_tree(node
, tree
);
2554 isl_union_set_list_free(filters
);
2557 isl_union_set_list_free(filters
);
2558 isl_schedule_node_free(node
);
2562 /* Insert a sequence node with child filters "filters" between "node" and
2563 * its parent. That is, the tree that "node" points to is attached
2564 * to each of the child nodes of the filter nodes.
2565 * Return a pointer to the new sequence node.
2567 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
2568 __isl_take isl_schedule_node
*node
,
2569 __isl_take isl_union_set_list
*filters
)
2571 return isl_schedule_node_insert_children(node
,
2572 isl_schedule_node_sequence
, filters
);
2575 /* Insert a set node with child filters "filters" between "node" and
2576 * its parent. That is, the tree that "node" points to is attached
2577 * to each of the child nodes of the filter nodes.
2578 * Return a pointer to the new set node.
2580 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
2581 __isl_take isl_schedule_node
*node
,
2582 __isl_take isl_union_set_list
*filters
)
2584 return isl_schedule_node_insert_children(node
,
2585 isl_schedule_node_set
, filters
);
2588 /* Remove "node" from its schedule tree and return a pointer
2589 * to the leaf at the same position in the updated schedule tree.
2591 * It is not allowed to remove the root of a schedule tree or
2592 * a child of a set or sequence node.
2594 __isl_give isl_schedule_node
*isl_schedule_node_cut(
2595 __isl_take isl_schedule_node
*node
)
2597 isl_schedule_tree
*leaf
;
2598 enum isl_schedule_node_type parent_type
;
2602 if (!isl_schedule_node_has_parent(node
))
2603 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2604 "cannot cut root", return isl_schedule_node_free(node
));
2606 parent_type
= isl_schedule_node_get_parent_type(node
);
2607 if (parent_type
== isl_schedule_node_set
||
2608 parent_type
== isl_schedule_node_sequence
)
2609 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2610 "cannot cut child of set or sequence",
2611 return isl_schedule_node_free(node
));
2613 leaf
= isl_schedule_node_get_leaf(node
);
2614 return isl_schedule_node_graft_tree(node
, leaf
);
2617 /* Remove a single node from the schedule tree, attaching the child
2618 * of "node" directly to its parent.
2619 * Return a pointer to this former child or to the leaf the position
2620 * of the original node if there was no child.
2621 * It is not allowed to remove the root of a schedule tree,
2622 * a set or sequence node, a child of a set or sequence node or
2623 * a band node with an anchored subtree.
2625 __isl_give isl_schedule_node
*isl_schedule_node_delete(
2626 __isl_take isl_schedule_node
*node
)
2629 isl_schedule_tree
*tree
;
2630 enum isl_schedule_node_type type
;
2635 if (isl_schedule_node_get_tree_depth(node
) == 0)
2636 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2637 "cannot delete root node",
2638 return isl_schedule_node_free(node
));
2639 n
= isl_schedule_node_n_children(node
);
2641 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2642 "can only delete node with a single child",
2643 return isl_schedule_node_free(node
));
2644 type
= isl_schedule_node_get_parent_type(node
);
2645 if (type
== isl_schedule_node_sequence
|| type
== isl_schedule_node_set
)
2646 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2647 "cannot delete child of set or sequence",
2648 return isl_schedule_node_free(node
));
2649 if (isl_schedule_node_get_type(node
) == isl_schedule_node_band
) {
2652 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2654 return isl_schedule_node_free(node
);
2656 isl_die(isl_schedule_node_get_ctx(node
),
2658 "cannot delete band node with anchored subtree",
2659 return isl_schedule_node_free(node
));
2662 tree
= isl_schedule_node_get_tree(node
);
2663 if (!tree
|| isl_schedule_tree_has_children(tree
)) {
2664 tree
= isl_schedule_tree_child(tree
, 0);
2666 isl_schedule_tree_free(tree
);
2667 tree
= isl_schedule_node_get_leaf(node
);
2669 node
= isl_schedule_node_graft_tree(node
, tree
);
2674 /* Internal data structure for the group_ancestor callback.
2676 * If "finished" is set, then we no longer need to modify
2677 * any further ancestors.
2679 * "contraction" and "expansion" represent the expansion
2680 * that reflects the grouping.
2682 * "domain" contains the domain elements that reach the position
2683 * where the grouping is performed. That is, it is the range
2684 * of the resulting expansion.
2685 * "domain_universe" is the universe of "domain".
2686 * "group" is the set of group elements, i.e., the domain
2687 * of the resulting expansion.
2688 * "group_universe" is the universe of "group".
2690 * "sched" is the schedule for the group elements, in pratice
2691 * an identity mapping on "group_universe".
2692 * "dim" is the dimension of "sched".
2694 struct isl_schedule_group_data
{
2697 isl_union_map
*expansion
;
2698 isl_union_pw_multi_aff
*contraction
;
2700 isl_union_set
*domain
;
2701 isl_union_set
*domain_universe
;
2702 isl_union_set
*group
;
2703 isl_union_set
*group_universe
;
2706 isl_multi_aff
*sched
;
2709 /* Is domain covered by data->domain within data->domain_universe?
2711 static int locally_covered_by_domain(__isl_keep isl_union_set
*domain
,
2712 struct isl_schedule_group_data
*data
)
2715 isl_union_set
*test
;
2717 test
= isl_union_set_copy(domain
);
2718 test
= isl_union_set_intersect(test
,
2719 isl_union_set_copy(data
->domain_universe
));
2720 is_subset
= isl_union_set_is_subset(test
, data
->domain
);
2721 isl_union_set_free(test
);
2726 /* Update the band tree root "tree" to refer to the group instances
2727 * in data->group rather than the original domain elements in data->domain.
2728 * "pos" is the position in the original schedule tree where the modified
2729 * "tree" will be attached.
2731 * Add the part of the identity schedule on the group instances data->sched
2732 * that corresponds to this band node to the band schedule.
2733 * If the domain elements that reach the node and that are part
2734 * of data->domain_universe are all elements of data->domain (and therefore
2735 * replaced by the group instances) then this data->domain_universe
2736 * is removed from the domain of the band schedule.
2738 static __isl_give isl_schedule_tree
*group_band(
2739 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2740 struct isl_schedule_group_data
*data
)
2742 isl_union_set
*domain
;
2744 isl_multi_union_pw_aff
*mupa
, *partial
;
2746 int depth
, n
, has_id
;
2748 domain
= isl_schedule_node_get_domain(pos
);
2749 is_covered
= locally_covered_by_domain(domain
, data
);
2750 if (is_covered
>= 0 && is_covered
) {
2751 domain
= isl_union_set_universe(domain
);
2752 domain
= isl_union_set_subtract(domain
,
2753 isl_union_set_copy(data
->domain_universe
));
2754 tree
= isl_schedule_tree_band_intersect_domain(tree
, domain
);
2756 isl_union_set_free(domain
);
2758 return isl_schedule_tree_free(tree
);
2759 depth
= isl_schedule_node_get_schedule_depth(pos
);
2760 n
= isl_schedule_tree_band_n_member(tree
);
2761 ma
= isl_multi_aff_copy(data
->sched
);
2762 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, depth
);
2763 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, n
, data
->dim
- depth
- n
);
2764 mupa
= isl_multi_union_pw_aff_from_multi_aff(ma
);
2765 partial
= isl_schedule_tree_band_get_partial_schedule(tree
);
2766 has_id
= isl_multi_union_pw_aff_has_tuple_id(partial
, isl_dim_set
);
2768 partial
= isl_multi_union_pw_aff_free(partial
);
2769 } else if (has_id
) {
2771 id
= isl_multi_union_pw_aff_get_tuple_id(partial
, isl_dim_set
);
2772 mupa
= isl_multi_union_pw_aff_set_tuple_id(mupa
,
2775 partial
= isl_multi_union_pw_aff_union_add(partial
, mupa
);
2776 tree
= isl_schedule_tree_band_set_partial_schedule(tree
, partial
);
2781 /* Drop the parameters in "uset" that are not also in "space".
2782 * "n" is the number of parameters in "space".
2784 static __isl_give isl_union_set
*union_set_drop_extra_params(
2785 __isl_take isl_union_set
*uset
, __isl_keep isl_space
*space
, int n
)
2789 uset
= isl_union_set_align_params(uset
, isl_space_copy(space
));
2790 n2
= isl_union_set_dim(uset
, isl_dim_param
);
2791 uset
= isl_union_set_project_out(uset
, isl_dim_param
, n
, n2
- n
);
2796 /* Update the context tree root "tree" to refer to the group instances
2797 * in data->group rather than the original domain elements in data->domain.
2798 * "pos" is the position in the original schedule tree where the modified
2799 * "tree" will be attached.
2801 * We do not actually need to update "tree" since a context node only
2802 * refers to the schedule space. However, we may need to update "data"
2803 * to not refer to any parameters introduced by the context node.
2805 static __isl_give isl_schedule_tree
*group_context(
2806 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2807 struct isl_schedule_group_data
*data
)
2810 isl_union_set
*domain
;
2814 if (isl_schedule_node_get_tree_depth(pos
) == 1)
2817 domain
= isl_schedule_node_get_universe_domain(pos
);
2818 space
= isl_union_set_get_space(domain
);
2819 isl_union_set_free(domain
);
2821 n1
= isl_space_dim(space
, isl_dim_param
);
2822 data
->expansion
= isl_union_map_align_params(data
->expansion
, space
);
2823 n2
= isl_union_map_dim(data
->expansion
, isl_dim_param
);
2825 if (!data
->expansion
)
2826 return isl_schedule_tree_free(tree
);
2830 involves
= isl_union_map_involves_dims(data
->expansion
,
2831 isl_dim_param
, n1
, n2
- n1
);
2833 return isl_schedule_tree_free(tree
);
2835 isl_die(isl_schedule_node_get_ctx(pos
), isl_error_invalid
,
2836 "grouping cannot only refer to global parameters",
2837 return isl_schedule_tree_free(tree
));
2839 data
->expansion
= isl_union_map_project_out(data
->expansion
,
2840 isl_dim_param
, n1
, n2
- n1
);
2841 space
= isl_union_map_get_space(data
->expansion
);
2843 data
->contraction
= isl_union_pw_multi_aff_align_params(
2844 data
->contraction
, isl_space_copy(space
));
2845 n2
= isl_union_pw_multi_aff_dim(data
->contraction
, isl_dim_param
);
2846 data
->contraction
= isl_union_pw_multi_aff_drop_dims(data
->contraction
,
2847 isl_dim_param
, n1
, n2
- n1
);
2849 data
->domain
= union_set_drop_extra_params(data
->domain
, space
, n1
);
2850 data
->domain_universe
=
2851 union_set_drop_extra_params(data
->domain_universe
, space
, n1
);
2852 data
->group
= union_set_drop_extra_params(data
->group
, space
, n1
);
2853 data
->group_universe
=
2854 union_set_drop_extra_params(data
->group_universe
, space
, n1
);
2856 data
->sched
= isl_multi_aff_align_params(data
->sched
,
2857 isl_space_copy(space
));
2858 n2
= isl_multi_aff_dim(data
->sched
, isl_dim_param
);
2859 data
->sched
= isl_multi_aff_drop_dims(data
->sched
,
2860 isl_dim_param
, n1
, n2
- n1
);
2862 isl_space_free(space
);
2867 /* Update the domain tree root "tree" to refer to the group instances
2868 * in data->group rather than the original domain elements in data->domain.
2869 * "pos" is the position in the original schedule tree where the modified
2870 * "tree" will be attached.
2872 * We first double-check that all grouped domain elements are actually
2873 * part of the root domain and then replace those elements by the group
2876 static __isl_give isl_schedule_tree
*group_domain(
2877 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2878 struct isl_schedule_group_data
*data
)
2880 isl_union_set
*domain
;
2883 domain
= isl_schedule_tree_domain_get_domain(tree
);
2884 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2885 isl_union_set_free(domain
);
2887 return isl_schedule_tree_free(tree
);
2889 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2890 "grouped domain should be part of outer domain",
2891 return isl_schedule_tree_free(tree
));
2892 domain
= isl_schedule_tree_domain_get_domain(tree
);
2893 domain
= isl_union_set_subtract(domain
,
2894 isl_union_set_copy(data
->domain
));
2895 domain
= isl_union_set_union(domain
, isl_union_set_copy(data
->group
));
2896 tree
= isl_schedule_tree_domain_set_domain(tree
, domain
);
2901 /* Update the expansion tree root "tree" to refer to the group instances
2902 * in data->group rather than the original domain elements in data->domain.
2903 * "pos" is the position in the original schedule tree where the modified
2904 * "tree" will be attached.
2906 * Let G_1 -> D_1 be the expansion of "tree" and G_2 -> D_2 the newly
2907 * introduced expansion in a descendant of "tree".
2908 * We first double-check that D_2 is a subset of D_1.
2909 * Then we remove D_2 from the range of G_1 -> D_1 and add the mapping
2910 * G_1 -> D_1 . D_2 -> G_2.
2911 * Simmilarly, we restrict the domain of the contraction to the universe
2912 * of the range of the updated expansion and add G_2 -> D_2 . D_1 -> G_1,
2913 * attempting to remove the domain constraints of this additional part.
2915 static __isl_give isl_schedule_tree
*group_expansion(
2916 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2917 struct isl_schedule_group_data
*data
)
2919 isl_union_set
*domain
;
2920 isl_union_map
*expansion
, *umap
;
2921 isl_union_pw_multi_aff
*contraction
, *upma
;
2924 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2925 domain
= isl_union_map_range(expansion
);
2926 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2927 isl_union_set_free(domain
);
2929 return isl_schedule_tree_free(tree
);
2931 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2932 "grouped domain should be part "
2933 "of outer expansion domain",
2934 return isl_schedule_tree_free(tree
));
2935 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2936 umap
= isl_union_map_from_union_pw_multi_aff(
2937 isl_union_pw_multi_aff_copy(data
->contraction
));
2938 umap
= isl_union_map_apply_range(expansion
, umap
);
2939 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2940 expansion
= isl_union_map_subtract_range(expansion
,
2941 isl_union_set_copy(data
->domain
));
2942 expansion
= isl_union_map_union(expansion
, umap
);
2943 umap
= isl_union_map_universe(isl_union_map_copy(expansion
));
2944 domain
= isl_union_map_range(umap
);
2945 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
2946 umap
= isl_union_map_from_union_pw_multi_aff(contraction
);
2947 umap
= isl_union_map_apply_range(isl_union_map_copy(data
->expansion
),
2949 upma
= isl_union_pw_multi_aff_from_union_map(umap
);
2950 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
2951 contraction
= isl_union_pw_multi_aff_intersect_domain(contraction
,
2953 domain
= isl_union_pw_multi_aff_domain(
2954 isl_union_pw_multi_aff_copy(upma
));
2955 upma
= isl_union_pw_multi_aff_gist(upma
, domain
);
2956 contraction
= isl_union_pw_multi_aff_union_add(contraction
, upma
);
2957 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
2958 contraction
, expansion
);
2963 /* Update the tree root "tree" to refer to the group instances
2964 * in data->group rather than the original domain elements in data->domain.
2965 * "pos" is the position in the original schedule tree where the modified
2966 * "tree" will be attached.
2968 * If we have come across a domain or expansion node before (data->finished
2969 * is set), then we no longer need perform any modifications.
2971 * If "tree" is a filter, then we add data->group_universe to the filter.
2972 * We also remove data->domain_universe from the filter if all the domain
2973 * elements in this universe that reach the filter node are part of
2974 * the elements that are being grouped by data->expansion.
2975 * If "tree" is a band, domain or expansion, then it is handled
2976 * in a separate function.
2978 static __isl_give isl_schedule_tree
*group_ancestor(
2979 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2982 struct isl_schedule_group_data
*data
= user
;
2983 isl_union_set
*domain
;
2987 return isl_schedule_tree_free(tree
);
2992 switch (isl_schedule_tree_get_type(tree
)) {
2993 case isl_schedule_node_error
:
2994 return isl_schedule_tree_free(tree
);
2995 case isl_schedule_node_extension
:
2996 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_unsupported
,
2997 "grouping not allowed in extended tree",
2998 return isl_schedule_tree_free(tree
));
2999 case isl_schedule_node_band
:
3000 tree
= group_band(tree
, pos
, data
);
3002 case isl_schedule_node_context
:
3003 tree
= group_context(tree
, pos
, data
);
3005 case isl_schedule_node_domain
:
3006 tree
= group_domain(tree
, pos
, data
);
3009 case isl_schedule_node_filter
:
3010 domain
= isl_schedule_node_get_domain(pos
);
3011 is_covered
= locally_covered_by_domain(domain
, data
);
3012 isl_union_set_free(domain
);
3014 return isl_schedule_tree_free(tree
);
3015 domain
= isl_schedule_tree_filter_get_filter(tree
);
3017 domain
= isl_union_set_subtract(domain
,
3018 isl_union_set_copy(data
->domain_universe
));
3019 domain
= isl_union_set_union(domain
,
3020 isl_union_set_copy(data
->group_universe
));
3021 tree
= isl_schedule_tree_filter_set_filter(tree
, domain
);
3023 case isl_schedule_node_expansion
:
3024 tree
= group_expansion(tree
, pos
, data
);
3027 case isl_schedule_node_leaf
:
3028 case isl_schedule_node_guard
:
3029 case isl_schedule_node_mark
:
3030 case isl_schedule_node_sequence
:
3031 case isl_schedule_node_set
:
3038 /* Group the domain elements that reach "node" into instances
3039 * of a single statement with identifier "group_id".
3040 * In particular, group the domain elements according to their
3043 * That is, introduce an expansion node with as contraction
3044 * the prefix schedule (with the target space replaced by "group_id")
3045 * and as expansion the inverse of this contraction (with its range
3046 * intersected with the domain elements that reach "node").
3047 * The outer nodes are then modified to refer to the group instances
3048 * instead of the original domain elements.
3050 * No instance of "group_id" is allowed to reach "node" prior
3052 * No ancestor of "node" is allowed to be an extension node.
3054 * Return a pointer to original node in tree, i.e., the child
3055 * of the newly introduced expansion node.
3057 __isl_give isl_schedule_node
*isl_schedule_node_group(
3058 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*group_id
)
3060 struct isl_schedule_group_data data
= { 0 };
3062 isl_union_set
*domain
;
3063 isl_union_pw_multi_aff
*contraction
;
3064 isl_union_map
*expansion
;
3067 if (!node
|| !group_id
)
3069 if (check_insert(node
) < 0)
3072 domain
= isl_schedule_node_get_domain(node
);
3073 data
.domain
= isl_union_set_copy(domain
);
3074 data
.domain_universe
= isl_union_set_copy(domain
);
3075 data
.domain_universe
= isl_union_set_universe(data
.domain_universe
);
3077 data
.dim
= isl_schedule_node_get_schedule_depth(node
);
3078 if (data
.dim
== 0) {
3081 isl_union_set
*group
;
3082 isl_union_map
*univ
;
3084 ctx
= isl_schedule_node_get_ctx(node
);
3085 space
= isl_space_set_alloc(ctx
, 0, 0);
3086 space
= isl_space_set_tuple_id(space
, isl_dim_set
, group_id
);
3087 set
= isl_set_universe(isl_space_copy(space
));
3088 group
= isl_union_set_from_set(set
);
3089 expansion
= isl_union_map_from_domain_and_range(domain
, group
);
3090 univ
= isl_union_map_universe(isl_union_map_copy(expansion
));
3091 contraction
= isl_union_pw_multi_aff_from_union_map(univ
);
3092 expansion
= isl_union_map_reverse(expansion
);
3094 isl_multi_union_pw_aff
*prefix
;
3095 isl_union_set
*univ
;
3098 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node
);
3099 prefix
= isl_multi_union_pw_aff_set_tuple_id(prefix
,
3100 isl_dim_set
, group_id
);
3101 space
= isl_multi_union_pw_aff_get_space(prefix
);
3102 contraction
= isl_union_pw_multi_aff_from_multi_union_pw_aff(
3104 univ
= isl_union_set_universe(isl_union_set_copy(domain
));
3106 isl_union_pw_multi_aff_intersect_domain(contraction
, univ
);
3107 expansion
= isl_union_map_from_union_pw_multi_aff(
3108 isl_union_pw_multi_aff_copy(contraction
));
3109 expansion
= isl_union_map_reverse(expansion
);
3110 expansion
= isl_union_map_intersect_range(expansion
, domain
);
3112 space
= isl_space_map_from_set(space
);
3113 data
.sched
= isl_multi_aff_identity(space
);
3114 data
.group
= isl_union_map_domain(isl_union_map_copy(expansion
));
3115 data
.group
= isl_union_set_coalesce(data
.group
);
3116 data
.group_universe
= isl_union_set_copy(data
.group
);
3117 data
.group_universe
= isl_union_set_universe(data
.group_universe
);
3118 data
.expansion
= isl_union_map_copy(expansion
);
3119 data
.contraction
= isl_union_pw_multi_aff_copy(contraction
);
3120 node
= isl_schedule_node_insert_expansion(node
, contraction
, expansion
);
3122 disjoint
= isl_union_set_is_disjoint(data
.domain_universe
,
3123 data
.group_universe
);
3125 node
= update_ancestors(node
, &group_ancestor
, &data
);
3127 isl_union_set_free(data
.domain
);
3128 isl_union_set_free(data
.domain_universe
);
3129 isl_union_set_free(data
.group
);
3130 isl_union_set_free(data
.group_universe
);
3131 isl_multi_aff_free(data
.sched
);
3132 isl_union_map_free(data
.expansion
);
3133 isl_union_pw_multi_aff_free(data
.contraction
);
3135 node
= isl_schedule_node_child(node
, 0);
3137 if (!node
|| disjoint
< 0)
3138 return isl_schedule_node_free(node
);
3140 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3141 "group instances already reach node",
3142 return isl_schedule_node_free(node
));
3146 isl_schedule_node_free(node
);
3147 isl_id_free(group_id
);
3151 /* Compute the gist of the given band node with respect to "context".
3153 __isl_give isl_schedule_node
*isl_schedule_node_band_gist(
3154 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3156 isl_schedule_tree
*tree
;
3158 tree
= isl_schedule_node_get_tree(node
);
3159 tree
= isl_schedule_tree_band_gist(tree
, context
);
3160 return isl_schedule_node_graft_tree(node
, tree
);
3163 /* Internal data structure for isl_schedule_node_gist.
3164 * "n_expansion" is the number of outer expansion nodes
3165 * with respect to the current position
3166 * "filters" contains an element for each outer filter, expansion or
3167 * extension node with respect to the current position, each representing
3168 * the intersection of the previous element and the filter on the filter node
3169 * or the expansion/extension of the previous element.
3170 * The first element in the original context passed to isl_schedule_node_gist.
3172 struct isl_node_gist_data
{
3174 isl_union_set_list
*filters
;
3177 /* Enter the expansion node "node" during a isl_schedule_node_gist traversal.
3179 * In particular, add an extra element to data->filters containing
3180 * the expansion of the previous element and replace the expansion
3181 * and contraction on "node" by the gist with respect to these filters.
3182 * Also keep track of the fact that we have entered another expansion.
3184 static __isl_give isl_schedule_node
*gist_enter_expansion(
3185 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3188 isl_union_set
*inner
;
3189 isl_union_map
*expansion
;
3190 isl_union_pw_multi_aff
*contraction
;
3192 data
->n_expansion
++;
3194 n
= isl_union_set_list_n_union_set(data
->filters
);
3195 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3196 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3197 inner
= isl_union_set_apply(inner
, expansion
);
3199 contraction
= isl_schedule_node_expansion_get_contraction(node
);
3200 contraction
= isl_union_pw_multi_aff_gist(contraction
,
3201 isl_union_set_copy(inner
));
3203 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
3205 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3206 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3207 expansion
= isl_union_map_gist_domain(expansion
, inner
);
3208 node
= isl_schedule_node_expansion_set_contraction_and_expansion(node
,
3209 contraction
, expansion
);
3214 /* Leave the expansion node "node" during a isl_schedule_node_gist traversal.
3216 * In particular, remove the element in data->filters that was added by
3217 * gist_enter_expansion and decrement the number of outer expansions.
3219 * The expansion has already been simplified in gist_enter_expansion.
3220 * If this simplification results in an identity expansion, then
3221 * it is removed here.
3223 static __isl_give isl_schedule_node
*gist_leave_expansion(
3224 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3228 isl_union_map
*expansion
;
3230 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3231 identity
= isl_union_map_is_identity(expansion
);
3232 isl_union_map_free(expansion
);
3235 node
= isl_schedule_node_free(node
);
3237 node
= isl_schedule_node_delete(node
);
3239 n
= isl_union_set_list_n_union_set(data
->filters
);
3240 data
->filters
= isl_union_set_list_drop(data
->filters
, n
- 1, 1);
3242 data
->n_expansion
--;
3247 /* Enter the extension node "node" during a isl_schedule_node_gist traversal.
3249 * In particular, add an extra element to data->filters containing
3250 * the union of the previous element with the additional domain elements
3251 * introduced by the extension.
3253 static __isl_give isl_schedule_node
*gist_enter_extension(
3254 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3257 isl_union_set
*inner
, *extra
;
3258 isl_union_map
*extension
;
3260 n
= isl_union_set_list_n_union_set(data
->filters
);
3261 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3262 extension
= isl_schedule_node_extension_get_extension(node
);
3263 extra
= isl_union_map_range(extension
);
3264 inner
= isl_union_set_union(inner
, extra
);
3266 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
3271 /* Can we finish gisting at this node?
3272 * That is, is the filter on the current filter node a subset of
3273 * the original context passed to isl_schedule_node_gist?
3274 * If we have gone through any expansions, then we cannot perform
3275 * this test since the current domain elements are incomparable
3276 * to the domain elements in the original context.
3278 static int gist_done(__isl_keep isl_schedule_node
*node
,
3279 struct isl_node_gist_data
*data
)
3281 isl_union_set
*filter
, *outer
;
3284 if (data
->n_expansion
!= 0)
3287 filter
= isl_schedule_node_filter_get_filter(node
);
3288 outer
= isl_union_set_list_get_union_set(data
->filters
, 0);
3289 subset
= isl_union_set_is_subset(filter
, outer
);
3290 isl_union_set_free(outer
);
3291 isl_union_set_free(filter
);
3296 /* Callback for "traverse" to enter a node and to move
3297 * to the deepest initial subtree that should be traversed
3298 * by isl_schedule_node_gist.
3300 * The "filters" list is extended by one element each time
3301 * we come across a filter node by the result of intersecting
3302 * the last element in the list with the filter on the filter node.
3304 * If the filter on the current filter node is a subset of
3305 * the original context passed to isl_schedule_node_gist,
3306 * then there is no need to go into its subtree since it cannot
3307 * be further simplified by the context. The "filters" list is
3308 * still extended for consistency, but the actual value of the
3309 * added element is immaterial since it will not be used.
3311 * Otherwise, the filter on the current filter node is replaced by
3312 * the gist of the original filter with respect to the intersection
3313 * of the original context with the intermediate filters.
3315 * If the new element in the "filters" list is empty, then no elements
3316 * can reach the descendants of the current filter node. The subtree
3317 * underneath the filter node is therefore removed.
3319 * Each expansion node we come across is handled by
3320 * gist_enter_expansion.
3322 * Each extension node we come across is handled by
3323 * gist_enter_extension.
3325 static __isl_give isl_schedule_node
*gist_enter(
3326 __isl_take isl_schedule_node
*node
, void *user
)
3328 struct isl_node_gist_data
*data
= user
;
3331 isl_union_set
*filter
, *inner
;
3335 switch (isl_schedule_node_get_type(node
)) {
3336 case isl_schedule_node_error
:
3337 return isl_schedule_node_free(node
);
3338 case isl_schedule_node_expansion
:
3339 node
= gist_enter_expansion(node
, data
);
3341 case isl_schedule_node_extension
:
3342 node
= gist_enter_extension(node
, data
);
3344 case isl_schedule_node_band
:
3345 case isl_schedule_node_context
:
3346 case isl_schedule_node_domain
:
3347 case isl_schedule_node_guard
:
3348 case isl_schedule_node_leaf
:
3349 case isl_schedule_node_mark
:
3350 case isl_schedule_node_sequence
:
3351 case isl_schedule_node_set
:
3353 case isl_schedule_node_filter
:
3356 done
= gist_done(node
, data
);
3357 filter
= isl_schedule_node_filter_get_filter(node
);
3358 if (done
< 0 || done
) {
3359 data
->filters
= isl_union_set_list_add(data
->filters
,
3362 return isl_schedule_node_free(node
);
3365 n
= isl_union_set_list_n_union_set(data
->filters
);
3366 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3367 filter
= isl_union_set_gist(filter
, isl_union_set_copy(inner
));
3368 node
= isl_schedule_node_filter_set_filter(node
,
3369 isl_union_set_copy(filter
));
3370 filter
= isl_union_set_intersect(filter
, inner
);
3371 empty
= isl_union_set_is_empty(filter
);
3372 data
->filters
= isl_union_set_list_add(data
->filters
, filter
);
3374 return isl_schedule_node_free(node
);
3377 node
= isl_schedule_node_child(node
, 0);
3378 node
= isl_schedule_node_cut(node
);
3379 node
= isl_schedule_node_parent(node
);
3381 } while (isl_schedule_node_has_children(node
) &&
3382 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3387 /* Callback for "traverse" to leave a node for isl_schedule_node_gist.
3389 * In particular, if the current node is a filter node, then we remove
3390 * the element on the "filters" list that was added when we entered
3391 * the node. There is no need to compute any gist here, since we
3392 * already did that when we entered the node.
3394 * Expansion nodes are handled by gist_leave_expansion.
3396 * If the current node is an extension, then remove the element
3397 * in data->filters that was added by gist_enter_extension.
3399 * If the current node is a band node, then we compute the gist of
3400 * the band node with respect to the intersection of the original context
3401 * and the intermediate filters.
3403 * If the current node is a sequence or set node, then some of
3404 * the filter children may have become empty and so they are removed.
3405 * If only one child is left, then the set or sequence node along with
3406 * the single remaining child filter is removed. The filter can be
3407 * removed because the filters on a sequence or set node are supposed
3408 * to partition the incoming domain instances.
3409 * In principle, it should then be impossible for there to be zero
3410 * remaining children, but should this happen, we replace the entire
3411 * subtree with an empty filter.
3413 static __isl_give isl_schedule_node
*gist_leave(
3414 __isl_take isl_schedule_node
*node
, void *user
)
3416 struct isl_node_gist_data
*data
= user
;
3417 isl_schedule_tree
*tree
;
3419 isl_union_set
*filter
;
3421 switch (isl_schedule_node_get_type(node
)) {
3422 case isl_schedule_node_error
:
3423 return isl_schedule_node_free(node
);
3424 case isl_schedule_node_expansion
:
3425 node
= gist_leave_expansion(node
, data
);
3427 case isl_schedule_node_extension
:
3428 case isl_schedule_node_filter
:
3429 n
= isl_union_set_list_n_union_set(data
->filters
);
3430 data
->filters
= isl_union_set_list_drop(data
->filters
,
3433 case isl_schedule_node_band
:
3434 n
= isl_union_set_list_n_union_set(data
->filters
);
3435 filter
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3436 node
= isl_schedule_node_band_gist(node
, filter
);
3438 case isl_schedule_node_set
:
3439 case isl_schedule_node_sequence
:
3440 tree
= isl_schedule_node_get_tree(node
);
3441 n
= isl_schedule_tree_n_children(tree
);
3442 for (i
= n
- 1; i
>= 0; --i
) {
3443 isl_schedule_tree
*child
;
3444 isl_union_set
*filter
;
3447 child
= isl_schedule_tree_get_child(tree
, i
);
3448 filter
= isl_schedule_tree_filter_get_filter(child
);
3449 empty
= isl_union_set_is_empty(filter
);
3450 isl_union_set_free(filter
);
3451 isl_schedule_tree_free(child
);
3453 tree
= isl_schedule_tree_free(tree
);
3455 tree
= isl_schedule_tree_drop_child(tree
, i
);
3457 n
= isl_schedule_tree_n_children(tree
);
3458 node
= isl_schedule_node_graft_tree(node
, tree
);
3460 node
= isl_schedule_node_delete(node
);
3461 node
= isl_schedule_node_delete(node
);
3462 } else if (n
== 0) {
3466 isl_union_set_list_get_union_set(data
->filters
, 0);
3467 space
= isl_union_set_get_space(filter
);
3468 isl_union_set_free(filter
);
3469 filter
= isl_union_set_empty(space
);
3470 node
= isl_schedule_node_cut(node
);
3471 node
= isl_schedule_node_insert_filter(node
, filter
);
3474 case isl_schedule_node_context
:
3475 case isl_schedule_node_domain
:
3476 case isl_schedule_node_guard
:
3477 case isl_schedule_node_leaf
:
3478 case isl_schedule_node_mark
:
3485 /* Compute the gist of the subtree at "node" with respect to
3486 * the reaching domain elements in "context".
3487 * In particular, compute the gist of all band and filter nodes
3488 * in the subtree with respect to "context". Children of set or sequence
3489 * nodes that end up with an empty filter are removed completely.
3491 * We keep track of the intersection of "context" with all outer filters
3492 * of the current node within the subtree in the final element of "filters".
3493 * Initially, this list contains the single element "context" and it is
3494 * extended or shortened each time we enter or leave a filter node.
3496 __isl_give isl_schedule_node
*isl_schedule_node_gist(
3497 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3499 struct isl_node_gist_data data
;
3501 data
.n_expansion
= 0;
3502 data
.filters
= isl_union_set_list_from_union_set(context
);
3503 node
= traverse(node
, &gist_enter
, &gist_leave
, &data
);
3504 isl_union_set_list_free(data
.filters
);
3508 /* Intersect the domain of domain node "node" with "domain".
3510 * If the domain of "node" is already a subset of "domain",
3511 * then nothing needs to be changed.
3513 * Otherwise, we replace the domain of the domain node by the intersection
3514 * and simplify the subtree rooted at "node" with respect to this intersection.
3516 __isl_give isl_schedule_node
*isl_schedule_node_domain_intersect_domain(
3517 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
)
3519 isl_schedule_tree
*tree
;
3520 isl_union_set
*uset
;
3523 if (!node
|| !domain
)
3526 uset
= isl_schedule_tree_domain_get_domain(node
->tree
);
3527 is_subset
= isl_union_set_is_subset(uset
, domain
);
3528 isl_union_set_free(uset
);
3532 isl_union_set_free(domain
);
3536 tree
= isl_schedule_tree_copy(node
->tree
);
3537 uset
= isl_schedule_tree_domain_get_domain(tree
);
3538 uset
= isl_union_set_intersect(uset
, domain
);
3539 tree
= isl_schedule_tree_domain_set_domain(tree
,
3540 isl_union_set_copy(uset
));
3541 node
= isl_schedule_node_graft_tree(node
, tree
);
3543 node
= isl_schedule_node_child(node
, 0);
3544 node
= isl_schedule_node_gist(node
, uset
);
3545 node
= isl_schedule_node_parent(node
);
3549 isl_schedule_node_free(node
);
3550 isl_union_set_free(domain
);
3554 /* Replace the domain of domain node "node" with the gist
3555 * of the original domain with respect to the parameter domain "context".
3557 __isl_give isl_schedule_node
*isl_schedule_node_domain_gist_params(
3558 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
3560 isl_union_set
*domain
;
3561 isl_schedule_tree
*tree
;
3563 if (!node
|| !context
)
3566 tree
= isl_schedule_tree_copy(node
->tree
);
3567 domain
= isl_schedule_tree_domain_get_domain(node
->tree
);
3568 domain
= isl_union_set_gist_params(domain
, context
);
3569 tree
= isl_schedule_tree_domain_set_domain(tree
, domain
);
3570 node
= isl_schedule_node_graft_tree(node
, tree
);
3574 isl_schedule_node_free(node
);
3575 isl_set_free(context
);
3579 /* Internal data structure for isl_schedule_node_get_subtree_expansion.
3580 * "expansions" contains a list of accumulated expansions
3581 * for each outer expansion, set or sequence node. The first element
3582 * in the list is an identity mapping on the reaching domain elements.
3583 * "res" collects the results.
3585 struct isl_subtree_expansion_data
{
3586 isl_union_map_list
*expansions
;
3590 /* Callback for "traverse" to enter a node and to move
3591 * to the deepest initial subtree that should be traversed
3592 * by isl_schedule_node_get_subtree_expansion.
3594 * Whenever we come across an expansion node, the last element
3595 * of data->expansions is combined with the expansion
3596 * on the expansion node.
3598 * Whenever we come across a filter node that is the child
3599 * of a set or sequence node, data->expansions is extended
3600 * with a new element that restricts the previous element
3601 * to the elements selected by the filter.
3602 * The previous element can then be reused while backtracking.
3604 static __isl_give isl_schedule_node
*subtree_expansion_enter(
3605 __isl_take isl_schedule_node
*node
, void *user
)
3607 struct isl_subtree_expansion_data
*data
= user
;
3610 enum isl_schedule_node_type type
;
3611 isl_union_set
*filter
;
3612 isl_union_map
*inner
, *expansion
;
3615 switch (isl_schedule_node_get_type(node
)) {
3616 case isl_schedule_node_error
:
3617 return isl_schedule_node_free(node
);
3618 case isl_schedule_node_filter
:
3619 type
= isl_schedule_node_get_parent_type(node
);
3620 if (type
!= isl_schedule_node_set
&&
3621 type
!= isl_schedule_node_sequence
)
3623 filter
= isl_schedule_node_filter_get_filter(node
);
3624 n
= isl_union_map_list_n_union_map(data
->expansions
);
3626 isl_union_map_list_get_union_map(data
->expansions
,
3628 inner
= isl_union_map_intersect_range(inner
, filter
);
3630 isl_union_map_list_add(data
->expansions
, inner
);
3632 case isl_schedule_node_expansion
:
3633 n
= isl_union_map_list_n_union_map(data
->expansions
);
3635 isl_schedule_node_expansion_get_expansion(node
);
3637 isl_union_map_list_get_union_map(data
->expansions
,
3639 inner
= isl_union_map_apply_range(inner
, expansion
);
3641 isl_union_map_list_set_union_map(data
->expansions
,
3644 case isl_schedule_node_band
:
3645 case isl_schedule_node_context
:
3646 case isl_schedule_node_domain
:
3647 case isl_schedule_node_extension
:
3648 case isl_schedule_node_guard
:
3649 case isl_schedule_node_leaf
:
3650 case isl_schedule_node_mark
:
3651 case isl_schedule_node_sequence
:
3652 case isl_schedule_node_set
:
3655 } while (isl_schedule_node_has_children(node
) &&
3656 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3661 /* Callback for "traverse" to leave a node for
3662 * isl_schedule_node_get_subtree_expansion.
3664 * If we come across a filter node that is the child
3665 * of a set or sequence node, then we remove the element
3666 * of data->expansions that was added in subtree_expansion_enter.
3668 * If we reach a leaf node, then the accumulated expansion is
3669 * added to data->res.
3671 static __isl_give isl_schedule_node
*subtree_expansion_leave(
3672 __isl_take isl_schedule_node
*node
, void *user
)
3674 struct isl_subtree_expansion_data
*data
= user
;
3676 isl_union_map
*inner
;
3677 enum isl_schedule_node_type type
;
3679 switch (isl_schedule_node_get_type(node
)) {
3680 case isl_schedule_node_error
:
3681 return isl_schedule_node_free(node
);
3682 case isl_schedule_node_filter
:
3683 type
= isl_schedule_node_get_parent_type(node
);
3684 if (type
!= isl_schedule_node_set
&&
3685 type
!= isl_schedule_node_sequence
)
3687 n
= isl_union_map_list_n_union_map(data
->expansions
);
3688 data
->expansions
= isl_union_map_list_drop(data
->expansions
,
3691 case isl_schedule_node_leaf
:
3692 n
= isl_union_map_list_n_union_map(data
->expansions
);
3693 inner
= isl_union_map_list_get_union_map(data
->expansions
,
3695 data
->res
= isl_union_map_union(data
->res
, inner
);
3697 case isl_schedule_node_band
:
3698 case isl_schedule_node_context
:
3699 case isl_schedule_node_domain
:
3700 case isl_schedule_node_expansion
:
3701 case isl_schedule_node_extension
:
3702 case isl_schedule_node_guard
:
3703 case isl_schedule_node_mark
:
3704 case isl_schedule_node_sequence
:
3705 case isl_schedule_node_set
:
3712 /* Return a mapping from the domain elements that reach "node"
3713 * to the corresponding domain elements in the leaves of the subtree
3714 * rooted at "node" obtained by composing the intermediate expansions.
3716 * We start out with an identity mapping between the domain elements
3717 * that reach "node" and compose it with all the expansions
3718 * on a path from "node" to a leaf while traversing the subtree.
3719 * Within the children of an a sequence or set node, the
3720 * accumulated expansion is restricted to the elements selected
3721 * by the filter child.
3723 __isl_give isl_union_map
*isl_schedule_node_get_subtree_expansion(
3724 __isl_keep isl_schedule_node
*node
)
3726 struct isl_subtree_expansion_data data
;
3728 isl_union_set
*domain
;
3729 isl_union_map
*expansion
;
3734 domain
= isl_schedule_node_get_universe_domain(node
);
3735 space
= isl_union_set_get_space(domain
);
3736 expansion
= isl_union_set_identity(domain
);
3737 data
.res
= isl_union_map_empty(space
);
3738 data
.expansions
= isl_union_map_list_from_union_map(expansion
);
3740 node
= isl_schedule_node_copy(node
);
3741 node
= traverse(node
, &subtree_expansion_enter
,
3742 &subtree_expansion_leave
, &data
);
3744 data
.res
= isl_union_map_free(data
.res
);
3745 isl_schedule_node_free(node
);
3747 isl_union_map_list_free(data
.expansions
);
3752 /* Internal data structure for isl_schedule_node_get_subtree_contraction.
3753 * "contractions" contains a list of accumulated contractions
3754 * for each outer expansion, set or sequence node. The first element
3755 * in the list is an identity mapping on the reaching domain elements.
3756 * "res" collects the results.
3758 struct isl_subtree_contraction_data
{
3759 isl_union_pw_multi_aff_list
*contractions
;
3760 isl_union_pw_multi_aff
*res
;
3763 /* Callback for "traverse" to enter a node and to move
3764 * to the deepest initial subtree that should be traversed
3765 * by isl_schedule_node_get_subtree_contraction.
3767 * Whenever we come across an expansion node, the last element
3768 * of data->contractions is combined with the contraction
3769 * on the expansion node.
3771 * Whenever we come across a filter node that is the child
3772 * of a set or sequence node, data->contractions is extended
3773 * with a new element that restricts the previous element
3774 * to the elements selected by the filter.
3775 * The previous element can then be reused while backtracking.
3777 static __isl_give isl_schedule_node
*subtree_contraction_enter(
3778 __isl_take isl_schedule_node
*node
, void *user
)
3780 struct isl_subtree_contraction_data
*data
= user
;
3783 enum isl_schedule_node_type type
;
3784 isl_union_set
*filter
;
3785 isl_union_pw_multi_aff
*inner
, *contraction
;
3788 switch (isl_schedule_node_get_type(node
)) {
3789 case isl_schedule_node_error
:
3790 return isl_schedule_node_free(node
);
3791 case isl_schedule_node_filter
:
3792 type
= isl_schedule_node_get_parent_type(node
);
3793 if (type
!= isl_schedule_node_set
&&
3794 type
!= isl_schedule_node_sequence
)
3796 filter
= isl_schedule_node_filter_get_filter(node
);
3797 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3798 data
->contractions
);
3800 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3801 data
->contractions
, n
- 1);
3802 inner
= isl_union_pw_multi_aff_intersect_domain(inner
,
3804 data
->contractions
=
3805 isl_union_pw_multi_aff_list_add(data
->contractions
,
3808 case isl_schedule_node_expansion
:
3809 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3810 data
->contractions
);
3812 isl_schedule_node_expansion_get_contraction(node
);
3814 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3815 data
->contractions
, n
- 1);
3817 isl_union_pw_multi_aff_pullback_union_pw_multi_aff(
3818 inner
, contraction
);
3819 data
->contractions
=
3820 isl_union_pw_multi_aff_list_set_union_pw_multi_aff(
3821 data
->contractions
, n
- 1, inner
);
3823 case isl_schedule_node_band
:
3824 case isl_schedule_node_context
:
3825 case isl_schedule_node_domain
:
3826 case isl_schedule_node_extension
:
3827 case isl_schedule_node_guard
:
3828 case isl_schedule_node_leaf
:
3829 case isl_schedule_node_mark
:
3830 case isl_schedule_node_sequence
:
3831 case isl_schedule_node_set
:
3834 } while (isl_schedule_node_has_children(node
) &&
3835 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3840 /* Callback for "traverse" to leave a node for
3841 * isl_schedule_node_get_subtree_contraction.
3843 * If we come across a filter node that is the child
3844 * of a set or sequence node, then we remove the element
3845 * of data->contractions that was added in subtree_contraction_enter.
3847 * If we reach a leaf node, then the accumulated contraction is
3848 * added to data->res.
3850 static __isl_give isl_schedule_node
*subtree_contraction_leave(
3851 __isl_take isl_schedule_node
*node
, void *user
)
3853 struct isl_subtree_contraction_data
*data
= user
;
3855 isl_union_pw_multi_aff
*inner
;
3856 enum isl_schedule_node_type type
;
3858 switch (isl_schedule_node_get_type(node
)) {
3859 case isl_schedule_node_error
:
3860 return isl_schedule_node_free(node
);
3861 case isl_schedule_node_filter
:
3862 type
= isl_schedule_node_get_parent_type(node
);
3863 if (type
!= isl_schedule_node_set
&&
3864 type
!= isl_schedule_node_sequence
)
3866 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3867 data
->contractions
);
3868 data
->contractions
=
3869 isl_union_pw_multi_aff_list_drop(data
->contractions
,
3872 case isl_schedule_node_leaf
:
3873 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3874 data
->contractions
);
3875 inner
= isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3876 data
->contractions
, n
- 1);
3877 data
->res
= isl_union_pw_multi_aff_union_add(data
->res
, inner
);
3879 case isl_schedule_node_band
:
3880 case isl_schedule_node_context
:
3881 case isl_schedule_node_domain
:
3882 case isl_schedule_node_expansion
:
3883 case isl_schedule_node_extension
:
3884 case isl_schedule_node_guard
:
3885 case isl_schedule_node_mark
:
3886 case isl_schedule_node_sequence
:
3887 case isl_schedule_node_set
:
3894 /* Return a mapping from the domain elements in the leaves of the subtree
3895 * rooted at "node" to the corresponding domain elements that reach "node"
3896 * obtained by composing the intermediate contractions.
3898 * We start out with an identity mapping between the domain elements
3899 * that reach "node" and compose it with all the contractions
3900 * on a path from "node" to a leaf while traversing the subtree.
3901 * Within the children of an a sequence or set node, the
3902 * accumulated contraction is restricted to the elements selected
3903 * by the filter child.
3905 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_get_subtree_contraction(
3906 __isl_keep isl_schedule_node
*node
)
3908 struct isl_subtree_contraction_data data
;
3910 isl_union_set
*domain
;
3911 isl_union_pw_multi_aff
*contraction
;
3916 domain
= isl_schedule_node_get_universe_domain(node
);
3917 space
= isl_union_set_get_space(domain
);
3918 contraction
= isl_union_set_identity_union_pw_multi_aff(domain
);
3919 data
.res
= isl_union_pw_multi_aff_empty(space
);
3921 isl_union_pw_multi_aff_list_from_union_pw_multi_aff(contraction
);
3923 node
= isl_schedule_node_copy(node
);
3924 node
= traverse(node
, &subtree_contraction_enter
,
3925 &subtree_contraction_leave
, &data
);
3927 data
.res
= isl_union_pw_multi_aff_free(data
.res
);
3928 isl_schedule_node_free(node
);
3930 isl_union_pw_multi_aff_list_free(data
.contractions
);
3935 /* Do the nearest "n" ancestors of "node" have the types given in "types"
3936 * (starting at the parent of "node")?
3938 static int has_ancestors(__isl_keep isl_schedule_node
*node
,
3939 int n
, enum isl_schedule_node_type
*types
)
3946 n_ancestor
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
3950 for (i
= 0; i
< n
; ++i
) {
3951 isl_schedule_tree
*tree
;
3954 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
3955 n_ancestor
- 1 - i
);
3958 correct_type
= isl_schedule_tree_get_type(tree
) == types
[i
];
3959 isl_schedule_tree_free(tree
);
3967 /* Given a node "node" that appears in an extension (i.e., it is the child
3968 * of a filter in a sequence inside an extension node), are the spaces
3969 * of the extension specified by "extension" disjoint from those
3970 * of both the original extension and the domain elements that reach
3971 * that original extension?
3973 static int is_disjoint_extension(__isl_keep isl_schedule_node
*node
,
3974 __isl_keep isl_union_map
*extension
)
3977 isl_union_set
*domain
;
3980 node
= isl_schedule_node_copy(node
);
3981 node
= isl_schedule_node_parent(node
);
3982 node
= isl_schedule_node_parent(node
);
3983 node
= isl_schedule_node_parent(node
);
3984 old
= isl_schedule_node_extension_get_extension(node
);
3985 domain
= isl_schedule_node_get_universe_domain(node
);
3986 isl_schedule_node_free(node
);
3987 old
= isl_union_map_universe(old
);
3988 domain
= isl_union_set_union(domain
, isl_union_map_range(old
));
3989 extension
= isl_union_map_copy(extension
);
3990 extension
= isl_union_map_intersect_range(extension
, domain
);
3991 empty
= isl_union_map_is_empty(extension
);
3992 isl_union_map_free(extension
);
3997 /* Given a node "node" that is governed by an extension node, extend
3998 * that extension node with "extension".
4000 * In particular, "node" is the child of a filter in a sequence that
4001 * is in turn a child of an extension node. Extend that extension node
4004 * Return a pointer to the parent of the original node (i.e., a filter).
4006 static __isl_give isl_schedule_node
*extend_extension(
4007 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
4011 isl_union_map
*node_extension
;
4013 node
= isl_schedule_node_parent(node
);
4014 pos
= isl_schedule_node_get_child_position(node
);
4015 node
= isl_schedule_node_parent(node
);
4016 node
= isl_schedule_node_parent(node
);
4017 node_extension
= isl_schedule_node_extension_get_extension(node
);
4018 disjoint
= isl_union_map_is_disjoint(extension
, node_extension
);
4019 extension
= isl_union_map_union(extension
, node_extension
);
4020 node
= isl_schedule_node_extension_set_extension(node
, extension
);
4021 node
= isl_schedule_node_child(node
, 0);
4022 node
= isl_schedule_node_child(node
, pos
);
4025 return isl_schedule_node_free(node
);
4029 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4030 "extension domain should be disjoint from earlier "
4031 "extensions", return isl_schedule_node_free(node
));
4036 /* Return the universe of "uset" if this universe is disjoint from "ref".
4037 * Otherwise, return "uset".
4039 * Also check if "uset" itself is disjoint from "ref", reporting
4040 * an error if it is not.
4042 static __isl_give isl_union_set
*replace_by_universe_if_disjoint(
4043 __isl_take isl_union_set
*uset
, __isl_keep isl_union_set
*ref
)
4046 isl_union_set
*universe
;
4048 disjoint
= isl_union_set_is_disjoint(uset
, ref
);
4050 return isl_union_set_free(uset
);
4052 isl_die(isl_union_set_get_ctx(uset
), isl_error_invalid
,
4053 "extension domain should be disjoint from "
4054 "current domain", return isl_union_set_free(uset
));
4056 universe
= isl_union_set_universe(isl_union_set_copy(uset
));
4057 disjoint
= isl_union_set_is_disjoint(universe
, ref
);
4058 if (disjoint
>= 0 && disjoint
) {
4059 isl_union_set_free(uset
);
4062 isl_union_set_free(universe
);
4065 return isl_union_set_free(uset
);
4069 /* Insert an extension node on top of "node" with extension "extension".
4070 * In addition, insert a filter that separates node from the extension
4071 * between the extension node and "node".
4072 * Return a pointer to the inserted filter node.
4074 * If "node" already appears in an extension (i.e., if it is the child
4075 * of a filter in a sequence inside an extension node), then extend that
4076 * extension with "extension" instead.
4077 * In this case, a pointer to the original filter node is returned.
4078 * Note that if some of the elements in the new extension live in the
4079 * same space as those of the original extension or the domain elements
4080 * reaching the original extension, then we insert a new extension anyway.
4081 * Otherwise, we would have to adjust the filters in the sequence child
4082 * of the extension to ensure that the elements in the new extension
4085 static __isl_give isl_schedule_node
*insert_extension(
4086 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
4088 enum isl_schedule_node_type ancestors
[] =
4089 { isl_schedule_node_filter
, isl_schedule_node_sequence
,
4090 isl_schedule_node_extension
};
4091 isl_union_set
*domain
;
4092 isl_union_set
*filter
;
4095 in_ext
= has_ancestors(node
, 3, ancestors
);
4101 disjoint
= is_disjoint_extension(node
, extension
);
4105 return extend_extension(node
, extension
);
4108 filter
= isl_schedule_node_get_domain(node
);
4109 domain
= isl_union_map_range(isl_union_map_copy(extension
));
4110 filter
= replace_by_universe_if_disjoint(filter
, domain
);
4111 isl_union_set_free(domain
);
4113 node
= isl_schedule_node_insert_filter(node
, filter
);
4114 node
= isl_schedule_node_insert_extension(node
, extension
);
4115 node
= isl_schedule_node_child(node
, 0);
4118 isl_schedule_node_free(node
);
4119 isl_union_map_free(extension
);
4123 /* Replace the subtree that "node" points to by "tree" (which has
4124 * a sequence root with two children), except if the parent of "node"
4125 * is a sequence as well, in which case "tree" is spliced at the position
4126 * of "node" in its parent.
4127 * Return a pointer to the child of the "tree_pos" (filter) child of "tree"
4128 * in the updated schedule tree.
4130 static __isl_give isl_schedule_node
*graft_or_splice(
4131 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_tree
*tree
,
4136 if (isl_schedule_node_get_parent_type(node
) ==
4137 isl_schedule_node_sequence
) {
4138 pos
= isl_schedule_node_get_child_position(node
);
4139 node
= isl_schedule_node_parent(node
);
4140 node
= isl_schedule_node_sequence_splice(node
, pos
, tree
);
4143 node
= isl_schedule_node_graft_tree(node
, tree
);
4145 node
= isl_schedule_node_child(node
, pos
+ tree_pos
);
4146 node
= isl_schedule_node_child(node
, 0);
4151 /* Insert a node "graft" into the schedule tree of "node" such that it
4152 * is executed before (if "before" is set) or after (if "before" is not set)
4153 * the node that "node" points to.
4154 * The root of "graft" is an extension node.
4155 * Return a pointer to the node that "node" pointed to.
4157 * We first insert an extension node on top of "node" (or extend
4158 * the extension node if there already is one), with a filter on "node"
4159 * separating it from the extension.
4160 * We then insert a filter in the graft to separate it from the original
4161 * domain elements and combine the original and new tree in a sequence.
4162 * If we have extended an extension node, then the children of this
4163 * sequence are spliced in the sequence of the extended extension
4164 * at the position where "node" appears in the original extension.
4165 * Otherwise, the sequence pair is attached to the new extension node.
4167 static __isl_give isl_schedule_node
*graft_extension(
4168 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
,
4171 isl_union_map
*extension
;
4172 isl_union_set
*graft_domain
;
4173 isl_union_set
*node_domain
;
4174 isl_schedule_tree
*tree
, *tree_graft
;
4176 extension
= isl_schedule_node_extension_get_extension(graft
);
4177 graft_domain
= isl_union_map_range(isl_union_map_copy(extension
));
4178 node_domain
= isl_schedule_node_get_universe_domain(node
);
4179 node
= insert_extension(node
, extension
);
4181 graft_domain
= replace_by_universe_if_disjoint(graft_domain
,
4183 isl_union_set_free(node_domain
);
4185 tree
= isl_schedule_node_get_tree(node
);
4186 if (!isl_schedule_node_has_children(graft
)) {
4187 tree_graft
= isl_schedule_tree_from_filter(graft_domain
);
4189 graft
= isl_schedule_node_child(graft
, 0);
4190 tree_graft
= isl_schedule_node_get_tree(graft
);
4191 tree_graft
= isl_schedule_tree_insert_filter(tree_graft
,
4195 tree
= isl_schedule_tree_sequence_pair(tree_graft
, tree
);
4197 tree
= isl_schedule_tree_sequence_pair(tree
, tree_graft
);
4198 node
= graft_or_splice(node
, tree
, before
);
4200 isl_schedule_node_free(graft
);
4205 /* Replace the root domain node of "node" by an extension node suitable
4206 * for insertion at "pos".
4207 * That is, create an extension node that maps the outer band nodes
4208 * at "pos" to the domain of the root node of "node" and attach
4209 * the child of this root node to the extension node.
4211 static __isl_give isl_schedule_node
*extension_from_domain(
4212 __isl_take isl_schedule_node
*node
, __isl_keep isl_schedule_node
*pos
)
4214 isl_union_set
*universe
;
4215 isl_union_set
*domain
;
4220 isl_schedule_node
*res
;
4221 isl_schedule_tree
*tree
;
4223 anchored
= isl_schedule_node_is_subtree_anchored(node
);
4225 return isl_schedule_node_free(node
);
4227 isl_die(isl_schedule_node_get_ctx(node
), isl_error_unsupported
,
4228 "cannot graft anchored tree with domain root",
4229 return isl_schedule_node_free(node
));
4231 depth
= isl_schedule_node_get_schedule_depth(pos
);
4232 domain
= isl_schedule_node_domain_get_domain(node
);
4233 space
= isl_union_set_get_space(domain
);
4234 space
= isl_space_set_from_params(space
);
4235 space
= isl_space_add_dims(space
, isl_dim_set
, depth
);
4236 universe
= isl_union_set_from_set(isl_set_universe(space
));
4237 ext
= isl_union_map_from_domain_and_range(universe
, domain
);
4238 res
= isl_schedule_node_from_extension(ext
);
4239 node
= isl_schedule_node_child(node
, 0);
4241 return isl_schedule_node_free(res
);
4242 if (!isl_schedule_tree_is_leaf(node
->tree
)) {
4243 tree
= isl_schedule_node_get_tree(node
);
4244 res
= isl_schedule_node_child(res
, 0);
4245 res
= isl_schedule_node_graft_tree(res
, tree
);
4246 res
= isl_schedule_node_parent(res
);
4248 isl_schedule_node_free(node
);
4253 /* Insert a node "graft" into the schedule tree of "node" such that it
4254 * is executed before (if "before" is set) or after (if "before" is not set)
4255 * the node that "node" points to.
4256 * The root of "graft" may be either a domain or an extension node.
4257 * In the latter case, the domain of the extension needs to correspond
4258 * to the outer band nodes of "node".
4259 * The elements of the domain or the range of the extension may not
4260 * intersect with the domain elements that reach "node".
4261 * The schedule tree of "graft" may not be anchored.
4263 * The schedule tree of "node" is modified to include an extension node
4264 * corresponding to the root node of "graft" as a child of the original
4265 * parent of "node". The original node that "node" points to and the
4266 * child of the root node of "graft" are attached to this extension node
4267 * through a sequence, with appropriate filters and with the child
4268 * of "graft" appearing before or after the original "node".
4270 * If "node" already appears inside a sequence that is the child of
4271 * an extension node and if the spaces of the new domain elements
4272 * do not overlap with those of the original domain elements,
4273 * then that extension node is extended with the new extension
4274 * rather than introducing a new segment of extension and sequence nodes.
4276 * Return a pointer to the same node in the modified tree that
4277 * "node" pointed to in the original tree.
4279 static __isl_give isl_schedule_node
*isl_schedule_node_graft_before_or_after(
4280 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
,
4283 if (!node
|| !graft
)
4285 if (check_insert(node
) < 0)
4288 if (isl_schedule_node_get_type(graft
) == isl_schedule_node_domain
)
4289 graft
= extension_from_domain(graft
, node
);
4291 if (isl_schedule_node_get_type(graft
) != isl_schedule_node_extension
)
4292 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4293 "expecting domain or extension as root of graft",
4296 return graft_extension(node
, graft
, before
);
4298 isl_schedule_node_free(node
);
4299 isl_schedule_node_free(graft
);
4303 /* Insert a node "graft" into the schedule tree of "node" such that it
4304 * is executed before the node that "node" points to.
4305 * The root of "graft" may be either a domain or an extension node.
4306 * In the latter case, the domain of the extension needs to correspond
4307 * to the outer band nodes of "node".
4308 * The elements of the domain or the range of the extension may not
4309 * intersect with the domain elements that reach "node".
4310 * The schedule tree of "graft" may not be anchored.
4312 * Return a pointer to the same node in the modified tree that
4313 * "node" pointed to in the original tree.
4315 __isl_give isl_schedule_node
*isl_schedule_node_graft_before(
4316 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
)
4318 return isl_schedule_node_graft_before_or_after(node
, graft
, 1);
4321 /* Insert a node "graft" into the schedule tree of "node" such that it
4322 * is executed after the node that "node" points to.
4323 * The root of "graft" may be either a domain or an extension node.
4324 * In the latter case, the domain of the extension needs to correspond
4325 * to the outer band nodes of "node".
4326 * The elements of the domain or the range of the extension may not
4327 * intersect with the domain elements that reach "node".
4328 * The schedule tree of "graft" may not be anchored.
4330 * Return a pointer to the same node in the modified tree that
4331 * "node" pointed to in the original tree.
4333 __isl_give isl_schedule_node
*isl_schedule_node_graft_after(
4334 __isl_take isl_schedule_node
*node
,
4335 __isl_take isl_schedule_node
*graft
)
4337 return isl_schedule_node_graft_before_or_after(node
, graft
, 0);
4340 /* Split the domain elements that reach "node" into those that satisfy
4341 * "filter" and those that do not. Arrange for the first subset to be
4342 * executed before or after the second subset, depending on the value
4344 * Return a pointer to the tree corresponding to the second subset,
4345 * except when this subset is empty in which case the original pointer
4347 * If both subsets are non-empty, then a sequence node is introduced
4348 * to impose the order. If the grandparent of the original node was
4349 * itself a sequence, then the original child is replaced by two children
4350 * in this sequence instead.
4351 * The children in the sequence are copies of the original subtree,
4352 * simplified with respect to their filters.
4354 static __isl_give isl_schedule_node
*isl_schedule_node_order_before_or_after(
4355 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
,
4358 enum isl_schedule_node_type ancestors
[] =
4359 { isl_schedule_node_filter
, isl_schedule_node_sequence
};
4360 isl_union_set
*node_domain
, *node_filter
= NULL
, *parent_filter
;
4361 isl_schedule_node
*node2
;
4362 isl_schedule_tree
*tree1
, *tree2
;
4366 if (!node
|| !filter
)
4368 if (check_insert(node
) < 0)
4371 in_seq
= has_ancestors(node
, 2, ancestors
);
4374 node_domain
= isl_schedule_node_get_domain(node
);
4375 filter
= isl_union_set_gist(filter
, isl_union_set_copy(node_domain
));
4376 node_filter
= isl_union_set_copy(node_domain
);
4377 node_filter
= isl_union_set_subtract(node_filter
,
4378 isl_union_set_copy(filter
));
4379 node_filter
= isl_union_set_gist(node_filter
, node_domain
);
4380 empty1
= isl_union_set_is_empty(filter
);
4381 empty2
= isl_union_set_is_empty(node_filter
);
4382 if (empty1
< 0 || empty2
< 0)
4384 if (empty1
|| empty2
) {
4385 isl_union_set_free(filter
);
4386 isl_union_set_free(node_filter
);
4391 node
= isl_schedule_node_parent(node
);
4392 parent_filter
= isl_schedule_node_filter_get_filter(node
);
4393 node_filter
= isl_union_set_intersect(node_filter
,
4394 isl_union_set_copy(parent_filter
));
4395 filter
= isl_union_set_intersect(filter
, parent_filter
);
4398 node2
= isl_schedule_node_copy(node
);
4399 node
= isl_schedule_node_gist(node
, isl_union_set_copy(node_filter
));
4400 node2
= isl_schedule_node_gist(node2
, isl_union_set_copy(filter
));
4401 tree1
= isl_schedule_node_get_tree(node
);
4402 tree2
= isl_schedule_node_get_tree(node2
);
4403 tree1
= isl_schedule_tree_insert_filter(tree1
, node_filter
);
4404 tree2
= isl_schedule_tree_insert_filter(tree2
, filter
);
4405 isl_schedule_node_free(node2
);
4408 tree1
= isl_schedule_tree_sequence_pair(tree2
, tree1
);
4409 node
= graft_or_splice(node
, tree1
, 1);
4411 tree1
= isl_schedule_tree_sequence_pair(tree1
, tree2
);
4412 node
= graft_or_splice(node
, tree1
, 0);
4417 isl_schedule_node_free(node
);
4418 isl_union_set_free(filter
);
4419 isl_union_set_free(node_filter
);
4423 /* Split the domain elements that reach "node" into those that satisfy
4424 * "filter" and those that do not. Arrange for the first subset to be
4425 * executed before the second subset.
4426 * Return a pointer to the tree corresponding to the second subset,
4427 * except when this subset is empty in which case the original pointer
4430 __isl_give isl_schedule_node
*isl_schedule_node_order_before(
4431 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
4433 return isl_schedule_node_order_before_or_after(node
, filter
, 1);
4436 /* Split the domain elements that reach "node" into those that satisfy
4437 * "filter" and those that do not. Arrange for the first subset to be
4438 * executed after the second subset.
4439 * Return a pointer to the tree corresponding to the second subset,
4440 * except when this subset is empty in which case the original pointer
4443 __isl_give isl_schedule_node
*isl_schedule_node_order_after(
4444 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
4446 return isl_schedule_node_order_before_or_after(node
, filter
, 0);
4449 /* Reset the user pointer on all identifiers of parameters and tuples
4450 * in the schedule node "node".
4452 __isl_give isl_schedule_node
*isl_schedule_node_reset_user(
4453 __isl_take isl_schedule_node
*node
)
4455 isl_schedule_tree
*tree
;
4457 tree
= isl_schedule_node_get_tree(node
);
4458 tree
= isl_schedule_tree_reset_user(tree
);
4459 node
= isl_schedule_node_graft_tree(node
, tree
);
4464 /* Align the parameters of the schedule node "node" to those of "space".
4466 __isl_give isl_schedule_node
*isl_schedule_node_align_params(
4467 __isl_take isl_schedule_node
*node
, __isl_take isl_space
*space
)
4469 isl_schedule_tree
*tree
;
4471 tree
= isl_schedule_node_get_tree(node
);
4472 tree
= isl_schedule_tree_align_params(tree
, space
);
4473 node
= isl_schedule_node_graft_tree(node
, tree
);
4478 /* Compute the pullback of schedule node "node"
4479 * by the function represented by "upma".
4480 * In other words, plug in "upma" in the iteration domains
4481 * of schedule node "node".
4482 * We currently do not handle expansion nodes.
4484 * Note that this is only a helper function for
4485 * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency,
4486 * this function should not be called on a single node without also
4487 * calling it on all the other nodes.
4489 __isl_give isl_schedule_node
*isl_schedule_node_pullback_union_pw_multi_aff(
4490 __isl_take isl_schedule_node
*node
,
4491 __isl_take isl_union_pw_multi_aff
*upma
)
4493 isl_schedule_tree
*tree
;
4495 tree
= isl_schedule_node_get_tree(node
);
4496 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, upma
);
4497 node
= isl_schedule_node_graft_tree(node
, tree
);
4502 /* Internal data structure for isl_schedule_node_expand.
4503 * "tree" is the tree that needs to be plugged in in all the leaves.
4504 * "domain" is the set of domain elements in the original leaves
4505 * to which the tree applies.
4507 struct isl_schedule_expand_data
{
4508 isl_schedule_tree
*tree
;
4509 isl_union_set
*domain
;
4512 /* If "node" is a leaf, then plug in data->tree, simplifying it
4513 * within its new context.
4515 * If there are any domain elements at the leaf where the tree
4516 * should not be plugged in (i.e., there are elements not in data->domain)
4517 * then first extend the tree to only apply to the elements in data->domain
4518 * by constructing a set node that selects data->tree for elements
4519 * in data->domain and a leaf for the other elements.
4521 static __isl_give isl_schedule_node
*expand(__isl_take isl_schedule_node
*node
,
4524 struct isl_schedule_expand_data
*data
= user
;
4525 isl_schedule_tree
*tree
, *leaf
;
4526 isl_union_set
*domain
, *left
;
4529 if (isl_schedule_node_get_type(node
) != isl_schedule_node_leaf
)
4532 domain
= isl_schedule_node_get_domain(node
);
4533 tree
= isl_schedule_tree_copy(data
->tree
);
4535 left
= isl_union_set_copy(domain
);
4536 left
= isl_union_set_subtract(left
, isl_union_set_copy(data
->domain
));
4537 empty
= isl_union_set_is_empty(left
);
4538 if (empty
>= 0 && !empty
) {
4539 leaf
= isl_schedule_node_get_leaf(node
);
4540 leaf
= isl_schedule_tree_insert_filter(leaf
, left
);
4541 left
= isl_union_set_copy(data
->domain
);
4542 tree
= isl_schedule_tree_insert_filter(tree
, left
);
4543 tree
= isl_schedule_tree_set_pair(tree
, leaf
);
4546 node
= isl_schedule_node_free(node
);
4547 isl_union_set_free(left
);
4550 node
= isl_schedule_node_graft_tree(node
, tree
);
4551 node
= isl_schedule_node_gist(node
, domain
);
4556 /* Expand the tree rooted at "node" by extending all leaves
4557 * with an expansion node with as child "tree".
4558 * The expansion is determined by "contraction" and "domain".
4559 * That is, the elements of "domain" are contracted according
4560 * to "contraction". The expansion relation is then the inverse
4561 * of "contraction" with its range intersected with "domain".
4563 * Insert the appropriate expansion node on top of "tree" and
4564 * then plug in the result in all leaves of "node".
4566 __isl_give isl_schedule_node
*isl_schedule_node_expand(
4567 __isl_take isl_schedule_node
*node
,
4568 __isl_take isl_union_pw_multi_aff
*contraction
,
4569 __isl_take isl_union_set
*domain
,
4570 __isl_take isl_schedule_tree
*tree
)
4572 struct isl_schedule_expand_data data
;
4573 isl_union_map
*expansion
;
4574 isl_union_pw_multi_aff
*copy
;
4576 if (!node
|| !contraction
|| !tree
)
4577 node
= isl_schedule_node_free(node
);
4579 copy
= isl_union_pw_multi_aff_copy(contraction
);
4580 expansion
= isl_union_map_from_union_pw_multi_aff(copy
);
4581 expansion
= isl_union_map_reverse(expansion
);
4582 expansion
= isl_union_map_intersect_range(expansion
, domain
);
4583 data
.domain
= isl_union_map_domain(isl_union_map_copy(expansion
));
4585 tree
= isl_schedule_tree_insert_expansion(tree
, contraction
, expansion
);
4588 node
= isl_schedule_node_map_descendant_bottom_up(node
, &expand
, &data
);
4589 isl_union_set_free(data
.domain
);
4590 isl_schedule_tree_free(data
.tree
);
4594 /* Return the position of the subtree containing "node" among the children
4595 * of "ancestor". "node" is assumed to be a descendant of "ancestor".
4596 * In particular, both nodes should point to the same schedule tree.
4598 * Return -1 on error.
4600 int isl_schedule_node_get_ancestor_child_position(
4601 __isl_keep isl_schedule_node
*node
,
4602 __isl_keep isl_schedule_node
*ancestor
)
4605 isl_schedule_tree
*tree
;
4607 if (!node
|| !ancestor
)
4610 if (node
->schedule
!= ancestor
->schedule
)
4611 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4612 "not a descendant", return -1);
4614 n1
= isl_schedule_node_get_tree_depth(ancestor
);
4615 n2
= isl_schedule_node_get_tree_depth(node
);
4618 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4619 "not a descendant", return -1);
4620 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n1
);
4621 isl_schedule_tree_free(tree
);
4622 if (tree
!= ancestor
->tree
)
4623 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4624 "not a descendant", return -1);
4626 return node
->child_pos
[n1
];
4629 /* Given two nodes that point to the same schedule tree, return their
4630 * closest shared ancestor.
4632 * Since the two nodes point to the same schedule, they share at least
4633 * one ancestor, the root of the schedule. We move down from the root
4634 * to the first ancestor where the respective children have a different
4635 * child position. This is the requested ancestor.
4636 * If there is no ancestor where the children have a different position,
4637 * then one node is an ancestor of the other and then this node is
4638 * the requested ancestor.
4640 __isl_give isl_schedule_node
*isl_schedule_node_get_shared_ancestor(
4641 __isl_keep isl_schedule_node
*node1
,
4642 __isl_keep isl_schedule_node
*node2
)
4646 if (!node1
|| !node2
)
4648 if (node1
->schedule
!= node2
->schedule
)
4649 isl_die(isl_schedule_node_get_ctx(node1
), isl_error_invalid
,
4650 "not part of same schedule", return NULL
);
4651 n1
= isl_schedule_node_get_tree_depth(node1
);
4652 n2
= isl_schedule_node_get_tree_depth(node2
);
4654 return isl_schedule_node_get_shared_ancestor(node2
, node1
);
4656 return isl_schedule_node_copy(node1
);
4657 if (isl_schedule_node_is_equal(node1
, node2
))
4658 return isl_schedule_node_copy(node1
);
4660 for (i
= 0; i
< n1
; ++i
)
4661 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
4664 node1
= isl_schedule_node_copy(node1
);
4665 return isl_schedule_node_ancestor(node1
, n1
- i
);
4668 /* Print "node" to "p".
4670 __isl_give isl_printer
*isl_printer_print_schedule_node(
4671 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
4674 return isl_printer_free(p
);
4675 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
,
4676 isl_schedule_tree_list_n_schedule_tree(node
->ancestors
),
4680 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
4683 isl_printer
*printer
;
4688 ctx
= isl_schedule_node_get_ctx(node
);
4689 printer
= isl_printer_to_file(ctx
, stderr
);
4690 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
4691 printer
= isl_printer_print_schedule_node(printer
, node
);
4693 isl_printer_free(printer
);
4696 /* Return a string representation of "node".
4697 * Print the schedule node in block format as it would otherwise
4698 * look identical to the entire schedule.
4700 __isl_give
char *isl_schedule_node_to_str(__isl_keep isl_schedule_node
*node
)
4702 isl_printer
*printer
;
4708 printer
= isl_printer_to_str(isl_schedule_node_get_ctx(node
));
4709 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
4710 printer
= isl_printer_print_schedule_node(printer
, node
);
4711 s
= isl_printer_get_str(printer
);
4712 isl_printer_free(printer
);