2 * Copyright 2013-2014 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
9 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
10 * B.P. 105 - 78153 Le Chesnay, France
14 #include <isl_schedule_band.h>
15 #include <isl_schedule_private.h>
16 #include <isl_schedule_node_private.h>
18 /* Create a new schedule node in the given schedule, point at the given
19 * tree with given ancestors and child positions.
20 * "child_pos" may be NULL if there are no ancestors.
22 __isl_give isl_schedule_node
*isl_schedule_node_alloc(
23 __isl_take isl_schedule
*schedule
, __isl_take isl_schedule_tree
*tree
,
24 __isl_take isl_schedule_tree_list
*ancestors
, int *child_pos
)
27 isl_schedule_node
*node
;
30 if (!schedule
|| !tree
|| !ancestors
)
32 n
= isl_schedule_tree_list_n_schedule_tree(ancestors
);
33 if (n
> 0 && !child_pos
)
35 ctx
= isl_schedule_get_ctx(schedule
);
36 node
= isl_calloc_type(ctx
, isl_schedule_node
);
40 node
->schedule
= schedule
;
42 node
->ancestors
= ancestors
;
43 node
->child_pos
= isl_alloc_array(ctx
, int, n
);
44 if (n
&& !node
->child_pos
)
45 return isl_schedule_node_free(node
);
46 for (i
= 0; i
< n
; ++i
)
47 node
->child_pos
[i
] = child_pos
[i
];
51 isl_schedule_free(schedule
);
52 isl_schedule_tree_free(tree
);
53 isl_schedule_tree_list_free(ancestors
);
57 /* Return a pointer to the root of a schedule tree with as single
58 * node a domain node with the given domain.
60 __isl_give isl_schedule_node
*isl_schedule_node_from_domain(
61 __isl_take isl_union_set
*domain
)
63 isl_schedule
*schedule
;
64 isl_schedule_node
*node
;
66 schedule
= isl_schedule_from_domain(domain
);
67 node
= isl_schedule_get_root(schedule
);
68 isl_schedule_free(schedule
);
73 /* Return a pointer to the root of a schedule tree with as single
74 * node a extension node with the given extension.
76 __isl_give isl_schedule_node
*isl_schedule_node_from_extension(
77 __isl_take isl_union_map
*extension
)
80 isl_schedule
*schedule
;
81 isl_schedule_tree
*tree
;
82 isl_schedule_node
*node
;
87 ctx
= isl_union_map_get_ctx(extension
);
88 tree
= isl_schedule_tree_from_extension(extension
);
89 schedule
= isl_schedule_from_schedule_tree(ctx
, tree
);
90 node
= isl_schedule_get_root(schedule
);
91 isl_schedule_free(schedule
);
96 /* Return the isl_ctx to which "node" belongs.
98 isl_ctx
*isl_schedule_node_get_ctx(__isl_keep isl_schedule_node
*node
)
100 return node
? isl_schedule_get_ctx(node
->schedule
) : NULL
;
103 /* Return a pointer to the leaf of the schedule into which "node" points.
105 __isl_keep isl_schedule_tree
*isl_schedule_node_peek_leaf(
106 __isl_keep isl_schedule_node
*node
)
108 return node
? isl_schedule_peek_leaf(node
->schedule
) : NULL
;
111 /* Return a copy of the leaf of the schedule into which "node" points.
113 __isl_give isl_schedule_tree
*isl_schedule_node_get_leaf(
114 __isl_keep isl_schedule_node
*node
)
116 return isl_schedule_tree_copy(isl_schedule_node_peek_leaf(node
));
119 /* Return the type of the node or isl_schedule_node_error on error.
121 enum isl_schedule_node_type
isl_schedule_node_get_type(
122 __isl_keep isl_schedule_node
*node
)
124 return node
? isl_schedule_tree_get_type(node
->tree
)
125 : isl_schedule_node_error
;
128 /* Return the type of the parent of "node" or isl_schedule_node_error on error.
130 enum isl_schedule_node_type
isl_schedule_node_get_parent_type(
131 __isl_keep isl_schedule_node
*node
)
135 isl_schedule_tree
*parent
;
136 enum isl_schedule_node_type type
;
139 return isl_schedule_node_error
;
140 has_parent
= isl_schedule_node_has_parent(node
);
142 return isl_schedule_node_error
;
144 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
145 "node has no parent", return isl_schedule_node_error
);
147 pos
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) - 1;
148 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, pos
);
149 type
= isl_schedule_tree_get_type(parent
);
150 isl_schedule_tree_free(parent
);
155 /* Return a copy of the subtree that this node points to.
157 __isl_give isl_schedule_tree
*isl_schedule_node_get_tree(
158 __isl_keep isl_schedule_node
*node
)
163 return isl_schedule_tree_copy(node
->tree
);
166 /* Return a copy of the schedule into which "node" points.
168 __isl_give isl_schedule
*isl_schedule_node_get_schedule(
169 __isl_keep isl_schedule_node
*node
)
173 return isl_schedule_copy(node
->schedule
);
176 /* Return a fresh copy of "node".
178 __isl_take isl_schedule_node
*isl_schedule_node_dup(
179 __isl_keep isl_schedule_node
*node
)
184 return isl_schedule_node_alloc(isl_schedule_copy(node
->schedule
),
185 isl_schedule_tree_copy(node
->tree
),
186 isl_schedule_tree_list_copy(node
->ancestors
),
190 /* Return an isl_schedule_node that is equal to "node" and that has only
191 * a single reference.
193 __isl_give isl_schedule_node
*isl_schedule_node_cow(
194 __isl_take isl_schedule_node
*node
)
202 return isl_schedule_node_dup(node
);
205 /* Return a new reference to "node".
207 __isl_give isl_schedule_node
*isl_schedule_node_copy(
208 __isl_keep isl_schedule_node
*node
)
217 /* Free "node" and return NULL.
219 * Since the node may point to a leaf of its schedule, which
220 * point to a field inside the schedule, we need to make sure
221 * we free the tree before freeing the schedule.
223 __isl_null isl_schedule_node
*isl_schedule_node_free(
224 __isl_take isl_schedule_node
*node
)
231 isl_schedule_tree_list_free(node
->ancestors
);
232 free(node
->child_pos
);
233 isl_schedule_tree_free(node
->tree
);
234 isl_schedule_free(node
->schedule
);
240 /* Do "node1" and "node2" point to the same position in the same
243 isl_bool
isl_schedule_node_is_equal(__isl_keep isl_schedule_node
*node1
,
244 __isl_keep isl_schedule_node
*node2
)
248 if (!node1
|| !node2
)
249 return isl_bool_error
;
251 return isl_bool_true
;
252 if (node1
->schedule
!= node2
->schedule
)
253 return isl_bool_false
;
255 n1
= isl_schedule_node_get_tree_depth(node1
);
256 n2
= isl_schedule_node_get_tree_depth(node2
);
258 return isl_bool_false
;
259 for (i
= 0; i
< n1
; ++i
)
260 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
261 return isl_bool_false
;
263 return isl_bool_true
;
266 /* Return the number of outer schedule dimensions of "node"
267 * in its schedule tree.
269 * Return -1 on error.
271 int isl_schedule_node_get_schedule_depth(__isl_keep isl_schedule_node
*node
)
279 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
280 for (i
= n
- 1; i
>= 0; --i
) {
281 isl_schedule_tree
*tree
;
283 tree
= isl_schedule_tree_list_get_schedule_tree(
287 if (tree
->type
== isl_schedule_node_band
)
288 depth
+= isl_schedule_tree_band_n_member(tree
);
289 isl_schedule_tree_free(tree
);
295 /* Internal data structure for
296 * isl_schedule_node_get_prefix_schedule_union_pw_multi_aff
298 * "initialized" is set if the filter field has been initialized.
299 * If "universe_domain" is not set, then the collected filter is intersected
300 * with the the domain of the root domain node.
301 * "universe_filter" is set if we are only collecting the universes of filters
302 * "collect_prefix" is set if we are collecting prefixes.
303 * "filter" collects all outer filters and is NULL until "initialized" is set.
304 * "prefix" collects all outer band partial schedules (if "collect_prefix"
305 * is set). If it is used, then it is initialized by the caller
306 * of collect_filter_prefix to a zero-dimensional function.
308 struct isl_schedule_node_get_filter_prefix_data
{
313 isl_union_set
*filter
;
314 isl_multi_union_pw_aff
*prefix
;
317 static int collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
318 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
);
320 /* Update the filter and prefix information in "data" based on the first "n"
321 * elements in "list" and the expansion tree root "tree".
323 * We first collect the information from the elements in "list",
324 * initializing the filter based on the domain of the expansion.
325 * Then we map the results to the expanded space and combined them
326 * with the results already in "data".
328 static int collect_filter_prefix_expansion(__isl_take isl_schedule_tree
*tree
,
329 __isl_keep isl_schedule_tree_list
*list
, int n
,
330 struct isl_schedule_node_get_filter_prefix_data
*data
)
332 struct isl_schedule_node_get_filter_prefix_data contracted
;
333 isl_union_pw_multi_aff
*c
;
334 isl_union_map
*exp
, *universe
;
335 isl_union_set
*filter
;
337 c
= isl_schedule_tree_expansion_get_contraction(tree
);
338 exp
= isl_schedule_tree_expansion_get_expansion(tree
);
340 contracted
.initialized
= 1;
341 contracted
.universe_domain
= data
->universe_domain
;
342 contracted
.universe_filter
= data
->universe_filter
;
343 contracted
.collect_prefix
= data
->collect_prefix
;
344 universe
= isl_union_map_universe(isl_union_map_copy(exp
));
345 filter
= isl_union_map_domain(universe
);
346 if (data
->collect_prefix
) {
347 isl_space
*space
= isl_union_set_get_space(filter
);
348 space
= isl_space_set_from_params(space
);
349 contracted
.prefix
= isl_multi_union_pw_aff_zero(space
);
351 contracted
.filter
= filter
;
353 if (collect_filter_prefix(list
, n
, &contracted
) < 0)
354 contracted
.filter
= isl_union_set_free(contracted
.filter
);
355 if (data
->collect_prefix
) {
356 isl_multi_union_pw_aff
*prefix
;
358 prefix
= contracted
.prefix
;
360 isl_multi_union_pw_aff_pullback_union_pw_multi_aff(prefix
,
361 isl_union_pw_multi_aff_copy(c
));
362 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(
363 prefix
, data
->prefix
);
365 filter
= contracted
.filter
;
366 if (data
->universe_domain
)
367 filter
= isl_union_set_preimage_union_pw_multi_aff(filter
,
368 isl_union_pw_multi_aff_copy(c
));
370 filter
= isl_union_set_apply(filter
, isl_union_map_copy(exp
));
371 if (!data
->initialized
)
372 data
->filter
= filter
;
374 data
->filter
= isl_union_set_intersect(filter
, data
->filter
);
375 data
->initialized
= 1;
377 isl_union_pw_multi_aff_free(c
);
378 isl_union_map_free(exp
);
379 isl_schedule_tree_free(tree
);
384 /* Update the filter information in "data" based on the first "n"
385 * elements in "list" and the extension tree root "tree", in case
386 * data->universe_domain is set and data->collect_prefix is not.
388 * We collect the universe domain of the elements in "list" and
389 * add it to the universe range of the extension (intersected
390 * with the already collected filter, if any).
392 static int collect_universe_domain_extension(__isl_take isl_schedule_tree
*tree
,
393 __isl_keep isl_schedule_tree_list
*list
, int n
,
394 struct isl_schedule_node_get_filter_prefix_data
*data
)
396 struct isl_schedule_node_get_filter_prefix_data data_outer
;
397 isl_union_map
*extension
;
398 isl_union_set
*filter
;
400 data_outer
.initialized
= 0;
401 data_outer
.universe_domain
= 1;
402 data_outer
.universe_filter
= data
->universe_filter
;
403 data_outer
.collect_prefix
= 0;
404 data_outer
.filter
= NULL
;
405 data_outer
.prefix
= NULL
;
407 if (collect_filter_prefix(list
, n
, &data_outer
) < 0)
408 data_outer
.filter
= isl_union_set_free(data_outer
.filter
);
410 extension
= isl_schedule_tree_extension_get_extension(tree
);
411 extension
= isl_union_map_universe(extension
);
412 filter
= isl_union_map_range(extension
);
413 if (data_outer
.initialized
)
414 filter
= isl_union_set_union(filter
, data_outer
.filter
);
415 if (data
->initialized
)
416 filter
= isl_union_set_intersect(filter
, data
->filter
);
418 data
->filter
= filter
;
420 isl_schedule_tree_free(tree
);
425 /* Update "data" based on the tree node "tree" in case "data" has
426 * not been initialized yet.
428 * Return 0 on success and -1 on error.
430 * If "tree" is a filter, then we set data->filter to this filter
432 * If "tree" is a domain, then this means we have reached the root
433 * of the schedule tree without being able to extract any information.
434 * We therefore initialize data->filter to the universe of the domain,
435 * or the domain itself if data->universe_domain is not set.
436 * If "tree" is a band with at least one member, then we set data->filter
437 * to the universe of the schedule domain and replace the zero-dimensional
438 * data->prefix by the band schedule (if data->collect_prefix is set).
440 static int collect_filter_prefix_init(__isl_keep isl_schedule_tree
*tree
,
441 struct isl_schedule_node_get_filter_prefix_data
*data
)
443 enum isl_schedule_node_type type
;
444 isl_multi_union_pw_aff
*mupa
;
445 isl_union_set
*filter
;
447 type
= isl_schedule_tree_get_type(tree
);
449 case isl_schedule_node_error
:
451 case isl_schedule_node_expansion
:
452 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
453 "should be handled by caller", return -1);
454 case isl_schedule_node_extension
:
455 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
456 "cannot handle extension nodes", return -1);
457 case isl_schedule_node_context
:
458 case isl_schedule_node_leaf
:
459 case isl_schedule_node_guard
:
460 case isl_schedule_node_mark
:
461 case isl_schedule_node_sequence
:
462 case isl_schedule_node_set
:
464 case isl_schedule_node_domain
:
465 filter
= isl_schedule_tree_domain_get_domain(tree
);
466 if (data
->universe_domain
)
467 filter
= isl_union_set_universe(filter
);
468 data
->filter
= filter
;
470 case isl_schedule_node_band
:
471 if (isl_schedule_tree_band_n_member(tree
) == 0)
473 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
474 if (data
->collect_prefix
) {
475 isl_multi_union_pw_aff_free(data
->prefix
);
476 mupa
= isl_multi_union_pw_aff_reset_tuple_id(mupa
,
478 data
->prefix
= isl_multi_union_pw_aff_copy(mupa
);
480 filter
= isl_multi_union_pw_aff_domain(mupa
);
481 filter
= isl_union_set_universe(filter
);
482 data
->filter
= filter
;
484 case isl_schedule_node_filter
:
485 filter
= isl_schedule_tree_filter_get_filter(tree
);
486 if (data
->universe_filter
)
487 filter
= isl_union_set_universe(filter
);
488 data
->filter
= filter
;
492 if ((data
->collect_prefix
&& !data
->prefix
) || !data
->filter
)
495 data
->initialized
= 1;
500 /* Update "data" based on the tree node "tree" in case "data" has
501 * already been initialized.
503 * Return 0 on success and -1 on error.
505 * If "tree" is a domain and data->universe_domain is not set, then
506 * intersect data->filter with the domain.
507 * If "tree" is a filter, then we intersect data->filter with this filter
509 * If "tree" is a band with at least one member and data->collect_prefix
510 * is set, then we extend data->prefix with the band schedule.
511 * If "tree" is an extension, then we make sure that we are not collecting
512 * information on any extended domain elements.
514 static int collect_filter_prefix_update(__isl_keep isl_schedule_tree
*tree
,
515 struct isl_schedule_node_get_filter_prefix_data
*data
)
517 enum isl_schedule_node_type type
;
518 isl_multi_union_pw_aff
*mupa
;
519 isl_union_set
*filter
;
520 isl_union_map
*extension
;
523 type
= isl_schedule_tree_get_type(tree
);
525 case isl_schedule_node_error
:
527 case isl_schedule_node_expansion
:
528 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
529 "should be handled by caller", return -1);
530 case isl_schedule_node_extension
:
531 extension
= isl_schedule_tree_extension_get_extension(tree
);
532 extension
= isl_union_map_intersect_range(extension
,
533 isl_union_set_copy(data
->filter
));
534 empty
= isl_union_map_is_empty(extension
);
535 isl_union_map_free(extension
);
540 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
541 "cannot handle extension nodes", return -1);
542 case isl_schedule_node_context
:
543 case isl_schedule_node_leaf
:
544 case isl_schedule_node_guard
:
545 case isl_schedule_node_mark
:
546 case isl_schedule_node_sequence
:
547 case isl_schedule_node_set
:
549 case isl_schedule_node_domain
:
550 if (data
->universe_domain
)
552 filter
= isl_schedule_tree_domain_get_domain(tree
);
553 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
555 case isl_schedule_node_band
:
556 if (isl_schedule_tree_band_n_member(tree
) == 0)
558 if (!data
->collect_prefix
)
560 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
561 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(mupa
,
566 case isl_schedule_node_filter
:
567 filter
= isl_schedule_tree_filter_get_filter(tree
);
568 if (data
->universe_filter
)
569 filter
= isl_union_set_universe(filter
);
570 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
579 /* Collect filter and/or prefix information from the first "n"
580 * elements in "list" (which represent the ancestors of a node).
581 * Store the results in "data".
583 * Extension nodes are only supported if they do not affect the outcome,
584 * i.e., if we are collecting information on non-extended domain elements,
585 * or if we are collecting the universe domain (without prefix).
587 * Return 0 on success and -1 on error.
589 * We traverse the list from innermost ancestor (last element)
590 * to outermost ancestor (first element), calling collect_filter_prefix_init
591 * on each node as long as we have not been able to extract any information
592 * yet and collect_filter_prefix_update afterwards.
593 * If we come across an expansion node, then we interrupt the traversal
594 * and call collect_filter_prefix_expansion to restart the traversal
595 * over the remaining ancestors and to combine the results with those
596 * that have already been collected.
597 * If we come across an extension node and we are only computing
598 * the universe domain, then we interrupt the traversal and call
599 * collect_universe_domain_extension to restart the traversal
600 * over the remaining ancestors and to combine the results with those
601 * that have already been collected.
602 * On successful return, data->initialized will be set since the outermost
603 * ancestor is a domain node, which always results in an initialization.
605 static int collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
606 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
)
613 for (i
= n
- 1; i
>= 0; --i
) {
614 isl_schedule_tree
*tree
;
615 enum isl_schedule_node_type type
;
618 tree
= isl_schedule_tree_list_get_schedule_tree(list
, i
);
621 type
= isl_schedule_tree_get_type(tree
);
622 if (type
== isl_schedule_node_expansion
)
623 return collect_filter_prefix_expansion(tree
, list
, i
,
625 if (type
== isl_schedule_node_extension
&&
626 data
->universe_domain
&& !data
->collect_prefix
)
627 return collect_universe_domain_extension(tree
, list
, i
,
629 if (!data
->initialized
)
630 r
= collect_filter_prefix_init(tree
, data
);
632 r
= collect_filter_prefix_update(tree
, data
);
633 isl_schedule_tree_free(tree
);
641 /* Return the concatenation of the partial schedules of all outer band
642 * nodes of "node" interesected with all outer filters
643 * as an isl_multi_union_pw_aff.
644 * None of the ancestors of "node" may be an extension node, unless
645 * there is also a filter ancestor that filters out all the extended
648 * If "node" is pointing at the root of the schedule tree, then
649 * there are no domain elements reaching the current node, so
650 * we return an empty result.
652 * We collect all the filters and partial schedules in collect_filter_prefix
653 * and intersect the domain of the combined schedule with the combined filter.
655 __isl_give isl_multi_union_pw_aff
*
656 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(
657 __isl_keep isl_schedule_node
*node
)
661 struct isl_schedule_node_get_filter_prefix_data data
;
666 space
= isl_schedule_get_space(node
->schedule
);
667 space
= isl_space_set_from_params(space
);
668 if (node
->tree
== node
->schedule
->root
)
669 return isl_multi_union_pw_aff_zero(space
);
671 data
.initialized
= 0;
672 data
.universe_domain
= 1;
673 data
.universe_filter
= 0;
674 data
.collect_prefix
= 1;
676 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
678 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
679 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
680 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
682 data
.prefix
= isl_multi_union_pw_aff_intersect_domain(data
.prefix
,
688 /* Return the concatenation of the partial schedules of all outer band
689 * nodes of "node" interesected with all outer filters
690 * as an isl_union_pw_multi_aff.
691 * None of the ancestors of "node" may be an extension node, unless
692 * there is also a filter ancestor that filters out all the extended
695 * If "node" is pointing at the root of the schedule tree, then
696 * there are no domain elements reaching the current node, so
697 * we return an empty result.
699 * We collect all the filters and partial schedules in collect_filter_prefix.
700 * The partial schedules are collected as an isl_multi_union_pw_aff.
701 * If this isl_multi_union_pw_aff is zero-dimensional, then it does not
702 * contain any domain information, so we construct the isl_union_pw_multi_aff
703 * result as a zero-dimensional function on the collected filter.
704 * Otherwise, we convert the isl_multi_union_pw_aff to
705 * an isl_multi_union_pw_aff and intersect the domain with the filter.
707 __isl_give isl_union_pw_multi_aff
*
708 isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(
709 __isl_keep isl_schedule_node
*node
)
713 isl_union_pw_multi_aff
*prefix
;
714 struct isl_schedule_node_get_filter_prefix_data data
;
719 space
= isl_schedule_get_space(node
->schedule
);
720 if (node
->tree
== node
->schedule
->root
)
721 return isl_union_pw_multi_aff_empty(space
);
723 space
= isl_space_set_from_params(space
);
724 data
.initialized
= 0;
725 data
.universe_domain
= 1;
726 data
.universe_filter
= 0;
727 data
.collect_prefix
= 1;
729 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
731 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
732 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
733 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
736 isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
) == 0) {
737 isl_multi_union_pw_aff_free(data
.prefix
);
738 prefix
= isl_union_pw_multi_aff_from_domain(data
.filter
);
741 isl_union_pw_multi_aff_from_multi_union_pw_aff(data
.prefix
);
742 prefix
= isl_union_pw_multi_aff_intersect_domain(prefix
,
749 /* Return the concatenation of the partial schedules of all outer band
750 * nodes of "node" interesected with all outer filters
751 * as an isl_union_map.
753 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_union_map(
754 __isl_keep isl_schedule_node
*node
)
756 isl_union_pw_multi_aff
*upma
;
758 upma
= isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(node
);
759 return isl_union_map_from_union_pw_multi_aff(upma
);
762 /* Return the concatenation of the partial schedules of all outer band
763 * nodes of "node" intersected with all outer domain constraints.
764 * None of the ancestors of "node" may be an extension node, unless
765 * there is also a filter ancestor that filters out all the extended
768 * Essentially, this function intersects the domain of the output
769 * of isl_schedule_node_get_prefix_schedule_union_map with the output
770 * of isl_schedule_node_get_domain, except that it only traverses
771 * the ancestors of "node" once.
773 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_relation(
774 __isl_keep isl_schedule_node
*node
)
778 isl_union_map
*prefix
;
779 struct isl_schedule_node_get_filter_prefix_data data
;
784 space
= isl_schedule_get_space(node
->schedule
);
785 if (node
->tree
== node
->schedule
->root
)
786 return isl_union_map_empty(space
);
788 space
= isl_space_set_from_params(space
);
789 data
.initialized
= 0;
790 data
.universe_domain
= 0;
791 data
.universe_filter
= 0;
792 data
.collect_prefix
= 1;
794 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
796 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
797 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
798 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
801 isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
) == 0) {
802 isl_multi_union_pw_aff_free(data
.prefix
);
803 prefix
= isl_union_map_from_domain(data
.filter
);
805 prefix
= isl_union_map_from_multi_union_pw_aff(data
.prefix
);
806 prefix
= isl_union_map_intersect_domain(prefix
, data
.filter
);
812 /* Return the domain elements that reach "node".
814 * If "node" is pointing at the root of the schedule tree, then
815 * there are no domain elements reaching the current node, so
816 * we return an empty result.
817 * None of the ancestors of "node" may be an extension node, unless
818 * there is also a filter ancestor that filters out all the extended
821 * Otherwise, we collect all filters reaching the node,
822 * intersected with the root domain in collect_filter_prefix.
824 __isl_give isl_union_set
*isl_schedule_node_get_domain(
825 __isl_keep isl_schedule_node
*node
)
828 struct isl_schedule_node_get_filter_prefix_data data
;
833 if (node
->tree
== node
->schedule
->root
) {
836 space
= isl_schedule_get_space(node
->schedule
);
837 return isl_union_set_empty(space
);
840 data
.initialized
= 0;
841 data
.universe_domain
= 0;
842 data
.universe_filter
= 0;
843 data
.collect_prefix
= 0;
847 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
848 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
849 data
.filter
= isl_union_set_free(data
.filter
);
854 /* Return the union of universe sets of the domain elements that reach "node".
856 * If "node" is pointing at the root of the schedule tree, then
857 * there are no domain elements reaching the current node, so
858 * we return an empty result.
860 * Otherwise, we collect the universes of all filters reaching the node
861 * in collect_filter_prefix.
863 __isl_give isl_union_set
*isl_schedule_node_get_universe_domain(
864 __isl_keep isl_schedule_node
*node
)
867 struct isl_schedule_node_get_filter_prefix_data data
;
872 if (node
->tree
== node
->schedule
->root
) {
875 space
= isl_schedule_get_space(node
->schedule
);
876 return isl_union_set_empty(space
);
879 data
.initialized
= 0;
880 data
.universe_domain
= 1;
881 data
.universe_filter
= 1;
882 data
.collect_prefix
= 0;
886 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
887 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
888 data
.filter
= isl_union_set_free(data
.filter
);
893 /* Return the subtree schedule of "node".
895 * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle
896 * trees that do not contain any schedule information, we first
897 * move down to the first relevant descendant and handle leaves ourselves.
899 * If the subtree rooted at "node" contains any expansion nodes, then
900 * the returned subtree schedule is formulated in terms of the expanded
902 * The subtree is not allowed to contain any extension nodes.
904 __isl_give isl_union_map
*isl_schedule_node_get_subtree_schedule_union_map(
905 __isl_keep isl_schedule_node
*node
)
907 isl_schedule_tree
*tree
, *leaf
;
910 tree
= isl_schedule_node_get_tree(node
);
911 leaf
= isl_schedule_node_peek_leaf(node
);
912 tree
= isl_schedule_tree_first_schedule_descendant(tree
, leaf
);
916 isl_union_set
*domain
;
917 domain
= isl_schedule_node_get_universe_domain(node
);
918 isl_schedule_tree_free(tree
);
919 return isl_union_map_from_domain(domain
);
922 umap
= isl_schedule_tree_get_subtree_schedule_union_map(tree
);
923 isl_schedule_tree_free(tree
);
927 /* Return the number of ancestors of "node" in its schedule tree.
929 int isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node
*node
)
933 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
936 /* Does "node" have a parent?
938 * That is, does it point to any node of the schedule other than the root?
940 isl_bool
isl_schedule_node_has_parent(__isl_keep isl_schedule_node
*node
)
943 return isl_bool_error
;
944 if (!node
->ancestors
)
945 return isl_bool_error
;
947 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) != 0;
950 /* Return the position of "node" among the children of its parent.
952 int isl_schedule_node_get_child_position(__isl_keep isl_schedule_node
*node
)
959 has_parent
= isl_schedule_node_has_parent(node
);
963 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
964 "node has no parent", return -1);
966 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
967 return node
->child_pos
[n
- 1];
970 /* Does the parent (if any) of "node" have any children with a smaller child
971 * position than this one?
973 isl_bool
isl_schedule_node_has_previous_sibling(
974 __isl_keep isl_schedule_node
*node
)
980 return isl_bool_error
;
981 has_parent
= isl_schedule_node_has_parent(node
);
982 if (has_parent
< 0 || !has_parent
)
985 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
987 return node
->child_pos
[n
- 1] > 0;
990 /* Does the parent (if any) of "node" have any children with a greater child
991 * position than this one?
993 isl_bool
isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node
*node
)
997 isl_schedule_tree
*tree
;
1000 return isl_bool_error
;
1001 has_parent
= isl_schedule_node_has_parent(node
);
1002 if (has_parent
< 0 || !has_parent
)
1005 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1006 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
1008 return isl_bool_error
;
1009 n_child
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1010 isl_schedule_tree_free(tree
);
1012 return node
->child_pos
[n
- 1] + 1 < n_child
;
1015 /* Does "node" have any children?
1017 * Any node other than the leaf nodes is considered to have at least
1018 * one child, even if the corresponding isl_schedule_tree does not
1019 * have any children.
1021 isl_bool
isl_schedule_node_has_children(__isl_keep isl_schedule_node
*node
)
1024 return isl_bool_error
;
1025 return !isl_schedule_tree_is_leaf(node
->tree
);
1028 /* Return the number of children of "node"?
1030 * Any node other than the leaf nodes is considered to have at least
1031 * one child, even if the corresponding isl_schedule_tree does not
1032 * have any children. That is, the number of children of "node" is
1033 * only zero if its tree is the explicit empty tree. Otherwise,
1034 * if the isl_schedule_tree has any children, then it is equal
1035 * to the number of children of "node". If it has zero children,
1036 * then "node" still has a leaf node as child.
1038 int isl_schedule_node_n_children(__isl_keep isl_schedule_node
*node
)
1045 if (isl_schedule_tree_is_leaf(node
->tree
))
1048 n
= isl_schedule_tree_n_children(node
->tree
);
1055 /* Move the "node" pointer to the ancestor of the given generation
1056 * of the node it currently points to, where generation 0 is the node
1057 * itself and generation 1 is its parent.
1059 __isl_give isl_schedule_node
*isl_schedule_node_ancestor(
1060 __isl_take isl_schedule_node
*node
, int generation
)
1063 isl_schedule_tree
*tree
;
1067 if (generation
== 0)
1069 n
= isl_schedule_node_get_tree_depth(node
);
1071 return isl_schedule_node_free(node
);
1072 if (generation
< 0 || generation
> n
)
1073 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1074 "generation out of bounds",
1075 return isl_schedule_node_free(node
));
1076 node
= isl_schedule_node_cow(node
);
1080 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1082 isl_schedule_tree_free(node
->tree
);
1084 node
->ancestors
= isl_schedule_tree_list_drop(node
->ancestors
,
1085 n
- generation
, generation
);
1086 if (!node
->ancestors
|| !node
->tree
)
1087 return isl_schedule_node_free(node
);
1092 /* Move the "node" pointer to the parent of the node it currently points to.
1094 __isl_give isl_schedule_node
*isl_schedule_node_parent(
1095 __isl_take isl_schedule_node
*node
)
1099 if (!isl_schedule_node_has_parent(node
))
1100 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1101 "node has no parent",
1102 return isl_schedule_node_free(node
));
1103 return isl_schedule_node_ancestor(node
, 1);
1106 /* Move the "node" pointer to the root of its schedule tree.
1108 __isl_give isl_schedule_node
*isl_schedule_node_root(
1109 __isl_take isl_schedule_node
*node
)
1115 n
= isl_schedule_node_get_tree_depth(node
);
1117 return isl_schedule_node_free(node
);
1118 return isl_schedule_node_ancestor(node
, n
);
1121 /* Move the "node" pointer to the child at position "pos" of the node
1122 * it currently points to.
1124 __isl_give isl_schedule_node
*isl_schedule_node_child(
1125 __isl_take isl_schedule_node
*node
, int pos
)
1129 isl_schedule_tree
*tree
;
1132 node
= isl_schedule_node_cow(node
);
1135 if (!isl_schedule_node_has_children(node
))
1136 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1137 "node has no children",
1138 return isl_schedule_node_free(node
));
1140 ctx
= isl_schedule_node_get_ctx(node
);
1141 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1142 child_pos
= isl_realloc_array(ctx
, node
->child_pos
, int, n
+ 1);
1144 return isl_schedule_node_free(node
);
1145 node
->child_pos
= child_pos
;
1146 node
->child_pos
[n
] = pos
;
1148 node
->ancestors
= isl_schedule_tree_list_add(node
->ancestors
,
1149 isl_schedule_tree_copy(node
->tree
));
1151 if (isl_schedule_tree_has_children(tree
))
1152 tree
= isl_schedule_tree_get_child(tree
, pos
);
1154 tree
= isl_schedule_node_get_leaf(node
);
1155 isl_schedule_tree_free(node
->tree
);
1158 if (!node
->tree
|| !node
->ancestors
)
1159 return isl_schedule_node_free(node
);
1164 /* Move the "node" pointer to the first child of the node
1165 * it currently points to.
1167 __isl_give isl_schedule_node
*isl_schedule_node_first_child(
1168 __isl_take isl_schedule_node
*node
)
1170 return isl_schedule_node_child(node
, 0);
1173 /* Move the "node" pointer to the child of this node's parent in
1174 * the previous child position.
1176 __isl_give isl_schedule_node
*isl_schedule_node_previous_sibling(
1177 __isl_take isl_schedule_node
*node
)
1180 isl_schedule_tree
*parent
, *tree
;
1182 node
= isl_schedule_node_cow(node
);
1185 if (!isl_schedule_node_has_previous_sibling(node
))
1186 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1187 "node has no previous sibling",
1188 return isl_schedule_node_free(node
));
1190 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1191 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1194 return isl_schedule_node_free(node
);
1195 node
->child_pos
[n
- 1]--;
1196 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1197 node
->child_pos
[n
- 1]);
1198 isl_schedule_tree_free(parent
);
1200 return isl_schedule_node_free(node
);
1201 isl_schedule_tree_free(node
->tree
);
1207 /* Move the "node" pointer to the child of this node's parent in
1208 * the next child position.
1210 __isl_give isl_schedule_node
*isl_schedule_node_next_sibling(
1211 __isl_take isl_schedule_node
*node
)
1214 isl_schedule_tree
*parent
, *tree
;
1216 node
= isl_schedule_node_cow(node
);
1219 if (!isl_schedule_node_has_next_sibling(node
))
1220 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1221 "node has no next sibling",
1222 return isl_schedule_node_free(node
));
1224 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1225 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1228 return isl_schedule_node_free(node
);
1229 node
->child_pos
[n
- 1]++;
1230 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1231 node
->child_pos
[n
- 1]);
1232 isl_schedule_tree_free(parent
);
1234 return isl_schedule_node_free(node
);
1235 isl_schedule_tree_free(node
->tree
);
1241 /* Return a copy to the child at position "pos" of "node".
1243 __isl_give isl_schedule_node
*isl_schedule_node_get_child(
1244 __isl_keep isl_schedule_node
*node
, int pos
)
1246 return isl_schedule_node_child(isl_schedule_node_copy(node
), pos
);
1249 /* Traverse the descendant of "node" in depth-first order, including
1250 * "node" itself. Call "enter" whenever a node is entered and "leave"
1251 * whenever a node is left. The callback "enter" is responsible
1252 * for moving to the deepest initial subtree of its argument that
1253 * should be traversed.
1255 static __isl_give isl_schedule_node
*traverse(
1256 __isl_take isl_schedule_node
*node
,
1257 __isl_give isl_schedule_node
*(*enter
)(
1258 __isl_take isl_schedule_node
*node
, void *user
),
1259 __isl_give isl_schedule_node
*(*leave
)(
1260 __isl_take isl_schedule_node
*node
, void *user
),
1268 depth
= isl_schedule_node_get_tree_depth(node
);
1270 node
= enter(node
, user
);
1271 node
= leave(node
, user
);
1272 while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
&&
1273 !isl_schedule_node_has_next_sibling(node
)) {
1274 node
= isl_schedule_node_parent(node
);
1275 node
= leave(node
, user
);
1277 if (node
&& isl_schedule_node_get_tree_depth(node
) > depth
)
1278 node
= isl_schedule_node_next_sibling(node
);
1279 } while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
);
1284 /* Internal data structure for isl_schedule_node_foreach_descendant_top_down.
1286 * "fn" is the user-specified callback function.
1287 * "user" is the user-specified argument for the callback.
1289 struct isl_schedule_node_preorder_data
{
1290 isl_bool (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
);
1294 /* Callback for "traverse" to enter a node and to move
1295 * to the deepest initial subtree that should be traversed
1296 * for use in a preorder visit.
1298 * If the user callback returns a negative value, then we abort
1299 * the traversal. If this callback returns zero, then we skip
1300 * the subtree rooted at the current node. Otherwise, we move
1301 * down to the first child and repeat the process until a leaf
1304 static __isl_give isl_schedule_node
*preorder_enter(
1305 __isl_take isl_schedule_node
*node
, void *user
)
1307 struct isl_schedule_node_preorder_data
*data
= user
;
1315 r
= data
->fn(node
, data
->user
);
1317 return isl_schedule_node_free(node
);
1318 if (r
== isl_bool_false
)
1320 } while (isl_schedule_node_has_children(node
) &&
1321 (node
= isl_schedule_node_first_child(node
)) != NULL
);
1326 /* Callback for "traverse" to leave a node
1327 * for use in a preorder visit.
1328 * Since we already visited the node when we entered it,
1329 * we do not need to do anything here.
1331 static __isl_give isl_schedule_node
*preorder_leave(
1332 __isl_take isl_schedule_node
*node
, void *user
)
1337 /* Traverse the descendants of "node" (including the node itself)
1338 * in depth first preorder.
1340 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1341 * If "fn" returns 0 on any of the nodes, then the subtree rooted
1342 * at that node is skipped.
1344 * Return 0 on success and -1 on failure.
1346 isl_stat
isl_schedule_node_foreach_descendant_top_down(
1347 __isl_keep isl_schedule_node
*node
,
1348 isl_bool (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
),
1351 struct isl_schedule_node_preorder_data data
= { fn
, user
};
1353 node
= isl_schedule_node_copy(node
);
1354 node
= traverse(node
, &preorder_enter
, &preorder_leave
, &data
);
1355 isl_schedule_node_free(node
);
1357 return node
? isl_stat_ok
: isl_stat_error
;
1360 /* Internal data structure for isl_schedule_node_map_descendant_bottom_up.
1362 * "fn" is the user-specified callback function.
1363 * "user" is the user-specified argument for the callback.
1365 struct isl_schedule_node_postorder_data
{
1366 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1371 /* Callback for "traverse" to enter a node and to move
1372 * to the deepest initial subtree that should be traversed
1373 * for use in a postorder visit.
1375 * Since we are performing a postorder visit, we only need
1376 * to move to the deepest initial leaf here.
1378 static __isl_give isl_schedule_node
*postorder_enter(
1379 __isl_take isl_schedule_node
*node
, void *user
)
1381 while (node
&& isl_schedule_node_has_children(node
))
1382 node
= isl_schedule_node_first_child(node
);
1387 /* Callback for "traverse" to leave a node
1388 * for use in a postorder visit.
1390 * Since we are performing a postorder visit, we need
1391 * to call the user callback here.
1393 static __isl_give isl_schedule_node
*postorder_leave(
1394 __isl_take isl_schedule_node
*node
, void *user
)
1396 struct isl_schedule_node_postorder_data
*data
= user
;
1398 return data
->fn(node
, data
->user
);
1401 /* Traverse the descendants of "node" (including the node itself)
1402 * in depth first postorder, allowing the user to modify the visited node.
1403 * The traversal continues from the node returned by the callback function.
1404 * It is the responsibility of the user to ensure that this does not
1405 * lead to an infinite loop. It is safest to always return a pointer
1406 * to the same position (same ancestors and child positions) as the input node.
1408 __isl_give isl_schedule_node
*isl_schedule_node_map_descendant_bottom_up(
1409 __isl_take isl_schedule_node
*node
,
1410 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1411 void *user
), void *user
)
1413 struct isl_schedule_node_postorder_data data
= { fn
, user
};
1415 return traverse(node
, &postorder_enter
, &postorder_leave
, &data
);
1418 /* Traverse the ancestors of "node" from the root down to and including
1419 * the parent of "node", calling "fn" on each of them.
1421 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1423 * Return 0 on success and -1 on failure.
1425 isl_stat
isl_schedule_node_foreach_ancestor_top_down(
1426 __isl_keep isl_schedule_node
*node
,
1427 isl_stat (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
),
1433 return isl_stat_error
;
1435 n
= isl_schedule_node_get_tree_depth(node
);
1436 for (i
= 0; i
< n
; ++i
) {
1437 isl_schedule_node
*ancestor
;
1440 ancestor
= isl_schedule_node_copy(node
);
1441 ancestor
= isl_schedule_node_ancestor(ancestor
, n
- i
);
1442 r
= fn(ancestor
, user
);
1443 isl_schedule_node_free(ancestor
);
1445 return isl_stat_error
;
1451 /* Is any node in the subtree rooted at "node" anchored?
1452 * That is, do any of these nodes reference the outer band nodes?
1454 isl_bool
isl_schedule_node_is_subtree_anchored(
1455 __isl_keep isl_schedule_node
*node
)
1458 return isl_bool_error
;
1459 return isl_schedule_tree_is_subtree_anchored(node
->tree
);
1462 /* Return the number of members in the given band node.
1464 unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node
*node
)
1466 return node
? isl_schedule_tree_band_n_member(node
->tree
) : 0;
1469 /* Is the band member at position "pos" of the band node "node"
1470 * marked coincident?
1472 isl_bool
isl_schedule_node_band_member_get_coincident(
1473 __isl_keep isl_schedule_node
*node
, int pos
)
1476 return isl_bool_error
;
1477 return isl_schedule_tree_band_member_get_coincident(node
->tree
, pos
);
1480 /* Mark the band member at position "pos" the band node "node"
1481 * as being coincident or not according to "coincident".
1483 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_coincident(
1484 __isl_take isl_schedule_node
*node
, int pos
, int coincident
)
1487 isl_schedule_tree
*tree
;
1491 c
= isl_schedule_node_band_member_get_coincident(node
, pos
);
1492 if (c
== coincident
)
1495 tree
= isl_schedule_tree_copy(node
->tree
);
1496 tree
= isl_schedule_tree_band_member_set_coincident(tree
, pos
,
1498 node
= isl_schedule_node_graft_tree(node
, tree
);
1503 /* Is the band node "node" marked permutable?
1505 isl_bool
isl_schedule_node_band_get_permutable(
1506 __isl_keep isl_schedule_node
*node
)
1509 return isl_bool_error
;
1511 return isl_schedule_tree_band_get_permutable(node
->tree
);
1514 /* Mark the band node "node" permutable or not according to "permutable"?
1516 __isl_give isl_schedule_node
*isl_schedule_node_band_set_permutable(
1517 __isl_take isl_schedule_node
*node
, int permutable
)
1519 isl_schedule_tree
*tree
;
1523 if (isl_schedule_node_band_get_permutable(node
) == permutable
)
1526 tree
= isl_schedule_tree_copy(node
->tree
);
1527 tree
= isl_schedule_tree_band_set_permutable(tree
, permutable
);
1528 node
= isl_schedule_node_graft_tree(node
, tree
);
1533 /* Return the schedule space of the band node.
1535 __isl_give isl_space
*isl_schedule_node_band_get_space(
1536 __isl_keep isl_schedule_node
*node
)
1541 return isl_schedule_tree_band_get_space(node
->tree
);
1544 /* Return the schedule of the band node in isolation.
1546 __isl_give isl_multi_union_pw_aff
*isl_schedule_node_band_get_partial_schedule(
1547 __isl_keep isl_schedule_node
*node
)
1552 return isl_schedule_tree_band_get_partial_schedule(node
->tree
);
1555 /* Return the schedule of the band node in isolation in the form of
1558 * If the band does not have any members, then we construct a universe map
1559 * with the universe of the domain elements reaching the node as domain.
1560 * Otherwise, we extract an isl_multi_union_pw_aff representation and
1561 * convert that to an isl_union_map.
1563 __isl_give isl_union_map
*isl_schedule_node_band_get_partial_schedule_union_map(
1564 __isl_keep isl_schedule_node
*node
)
1566 isl_multi_union_pw_aff
*mupa
;
1571 if (isl_schedule_node_get_type(node
) != isl_schedule_node_band
)
1572 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1573 "not a band node", return NULL
);
1574 if (isl_schedule_node_band_n_member(node
) == 0) {
1575 isl_union_set
*domain
;
1577 domain
= isl_schedule_node_get_universe_domain(node
);
1578 return isl_union_map_from_domain(domain
);
1581 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
1582 return isl_union_map_from_multi_union_pw_aff(mupa
);
1585 /* Return the loop AST generation type for the band member of band node "node"
1586 * at position "pos".
1588 enum isl_ast_loop_type
isl_schedule_node_band_member_get_ast_loop_type(
1589 __isl_keep isl_schedule_node
*node
, int pos
)
1592 return isl_ast_loop_error
;
1594 return isl_schedule_tree_band_member_get_ast_loop_type(node
->tree
, pos
);
1597 /* Set the loop AST generation type for the band member of band node "node"
1598 * at position "pos" to "type".
1600 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_ast_loop_type(
1601 __isl_take isl_schedule_node
*node
, int pos
,
1602 enum isl_ast_loop_type type
)
1604 isl_schedule_tree
*tree
;
1609 tree
= isl_schedule_tree_copy(node
->tree
);
1610 tree
= isl_schedule_tree_band_member_set_ast_loop_type(tree
, pos
, type
);
1611 return isl_schedule_node_graft_tree(node
, tree
);
1614 /* Return the loop AST generation type for the band member of band node "node"
1615 * at position "pos" for the isolated part.
1617 enum isl_ast_loop_type
isl_schedule_node_band_member_get_isolate_ast_loop_type(
1618 __isl_keep isl_schedule_node
*node
, int pos
)
1621 return isl_ast_loop_error
;
1623 return isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1627 /* Set the loop AST generation type for the band member of band node "node"
1628 * at position "pos" for the isolated part to "type".
1630 __isl_give isl_schedule_node
*
1631 isl_schedule_node_band_member_set_isolate_ast_loop_type(
1632 __isl_take isl_schedule_node
*node
, int pos
,
1633 enum isl_ast_loop_type type
)
1635 isl_schedule_tree
*tree
;
1640 tree
= isl_schedule_tree_copy(node
->tree
);
1641 tree
= isl_schedule_tree_band_member_set_isolate_ast_loop_type(tree
,
1643 return isl_schedule_node_graft_tree(node
, tree
);
1646 /* Return the AST build options associated to band node "node".
1648 __isl_give isl_union_set
*isl_schedule_node_band_get_ast_build_options(
1649 __isl_keep isl_schedule_node
*node
)
1654 return isl_schedule_tree_band_get_ast_build_options(node
->tree
);
1657 /* Replace the AST build options associated to band node "node" by "options".
1659 __isl_give isl_schedule_node
*isl_schedule_node_band_set_ast_build_options(
1660 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*options
)
1662 isl_schedule_tree
*tree
;
1664 if (!node
|| !options
)
1667 tree
= isl_schedule_tree_copy(node
->tree
);
1668 tree
= isl_schedule_tree_band_set_ast_build_options(tree
, options
);
1669 return isl_schedule_node_graft_tree(node
, tree
);
1671 isl_schedule_node_free(node
);
1672 isl_union_set_free(options
);
1676 /* Make sure that that spaces of "node" and "mv" are the same.
1677 * Return -1 on error, reporting the error to the user.
1679 static int check_space_multi_val(__isl_keep isl_schedule_node
*node
,
1680 __isl_keep isl_multi_val
*mv
)
1682 isl_space
*node_space
, *mv_space
;
1685 node_space
= isl_schedule_node_band_get_space(node
);
1686 mv_space
= isl_multi_val_get_space(mv
);
1687 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1688 mv_space
, isl_dim_set
);
1689 isl_space_free(mv_space
);
1690 isl_space_free(node_space
);
1694 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1695 "spaces don't match", return -1);
1700 /* Multiply the partial schedule of the band node "node"
1701 * with the factors in "mv".
1703 __isl_give isl_schedule_node
*isl_schedule_node_band_scale(
1704 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1706 isl_schedule_tree
*tree
;
1711 if (check_space_multi_val(node
, mv
) < 0)
1713 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1717 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1718 "cannot scale band node with anchored subtree",
1721 tree
= isl_schedule_node_get_tree(node
);
1722 tree
= isl_schedule_tree_band_scale(tree
, mv
);
1723 return isl_schedule_node_graft_tree(node
, tree
);
1725 isl_multi_val_free(mv
);
1726 isl_schedule_node_free(node
);
1730 /* Divide the partial schedule of the band node "node"
1731 * by the factors in "mv".
1733 __isl_give isl_schedule_node
*isl_schedule_node_band_scale_down(
1734 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1736 isl_schedule_tree
*tree
;
1741 if (check_space_multi_val(node
, mv
) < 0)
1743 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1747 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1748 "cannot scale down band node with anchored subtree",
1751 tree
= isl_schedule_node_get_tree(node
);
1752 tree
= isl_schedule_tree_band_scale_down(tree
, mv
);
1753 return isl_schedule_node_graft_tree(node
, tree
);
1755 isl_multi_val_free(mv
);
1756 isl_schedule_node_free(node
);
1760 /* Reduce the partial schedule of the band node "node"
1761 * modulo the factors in "mv".
1763 __isl_give isl_schedule_node
*isl_schedule_node_band_mod(
1764 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1766 isl_schedule_tree
*tree
;
1771 if (check_space_multi_val(node
, mv
) < 0)
1773 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1777 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1778 "cannot perform mod on band node with anchored subtree",
1781 tree
= isl_schedule_node_get_tree(node
);
1782 tree
= isl_schedule_tree_band_mod(tree
, mv
);
1783 return isl_schedule_node_graft_tree(node
, tree
);
1785 isl_multi_val_free(mv
);
1786 isl_schedule_node_free(node
);
1790 /* Make sure that that spaces of "node" and "mupa" are the same.
1791 * Return isl_stat_error on error, reporting the error to the user.
1793 static isl_stat
check_space_multi_union_pw_aff(
1794 __isl_keep isl_schedule_node
*node
,
1795 __isl_keep isl_multi_union_pw_aff
*mupa
)
1797 isl_space
*node_space
, *mupa_space
;
1800 node_space
= isl_schedule_node_band_get_space(node
);
1801 mupa_space
= isl_multi_union_pw_aff_get_space(mupa
);
1802 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1803 mupa_space
, isl_dim_set
);
1804 isl_space_free(mupa_space
);
1805 isl_space_free(node_space
);
1807 return isl_stat_error
;
1809 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1810 "spaces don't match", return isl_stat_error
);
1815 /* Shift the partial schedule of the band node "node" by "shift".
1817 __isl_give isl_schedule_node
*isl_schedule_node_band_shift(
1818 __isl_take isl_schedule_node
*node
,
1819 __isl_take isl_multi_union_pw_aff
*shift
)
1821 isl_schedule_tree
*tree
;
1824 if (!node
|| !shift
)
1826 if (check_space_multi_union_pw_aff(node
, shift
) < 0)
1828 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1832 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1833 "cannot shift band node with anchored subtree",
1836 tree
= isl_schedule_node_get_tree(node
);
1837 tree
= isl_schedule_tree_band_shift(tree
, shift
);
1838 return isl_schedule_node_graft_tree(node
, tree
);
1840 isl_multi_union_pw_aff_free(shift
);
1841 isl_schedule_node_free(node
);
1845 /* Tile "node" with tile sizes "sizes".
1847 * The current node is replaced by two nested nodes corresponding
1848 * to the tile dimensions and the point dimensions.
1850 * Return a pointer to the outer (tile) node.
1852 * If any of the descendants of "node" depend on the set of outer band nodes,
1853 * then we refuse to tile the node.
1855 * If the scale tile loops option is set, then the tile loops
1856 * are scaled by the tile sizes. If the shift point loops option is set,
1857 * then the point loops are shifted to start at zero.
1858 * In particular, these options affect the tile and point loop schedules
1861 * scale shift original tile point
1863 * 0 0 i floor(i/s) i
1864 * 1 0 i s * floor(i/s) i
1865 * 0 1 i floor(i/s) i - s * floor(i/s)
1866 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1868 __isl_give isl_schedule_node
*isl_schedule_node_band_tile(
1869 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*sizes
)
1871 isl_schedule_tree
*tree
;
1874 if (!node
|| !sizes
)
1876 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1880 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1881 "cannot tile band node with anchored subtree",
1884 if (check_space_multi_val(node
, sizes
) < 0)
1887 tree
= isl_schedule_node_get_tree(node
);
1888 tree
= isl_schedule_tree_band_tile(tree
, sizes
);
1889 return isl_schedule_node_graft_tree(node
, tree
);
1891 isl_multi_val_free(sizes
);
1892 isl_schedule_node_free(node
);
1896 /* Move the band node "node" down to all the leaves in the subtree
1898 * Return a pointer to the node in the resulting tree that is in the same
1899 * position as the node pointed to by "node" in the original tree.
1901 * If the node only has a leaf child, then nothing needs to be done.
1902 * Otherwise, the child of the node is removed and the result is
1903 * appended to all the leaves in the subtree rooted at the original child.
1904 * Since the node is moved to the leaves, it needs to be expanded
1905 * according to the expansion, if any, defined by that subtree.
1906 * In the end, the original node is replaced by the result of
1907 * attaching copies of the expanded node to the leaves.
1909 * If any of the nodes in the subtree rooted at "node" depend on
1910 * the set of outer band nodes then we refuse to sink the band node.
1912 __isl_give isl_schedule_node
*isl_schedule_node_band_sink(
1913 __isl_take isl_schedule_node
*node
)
1915 enum isl_schedule_node_type type
;
1916 isl_schedule_tree
*tree
, *child
;
1917 isl_union_pw_multi_aff
*contraction
;
1923 type
= isl_schedule_node_get_type(node
);
1924 if (type
!= isl_schedule_node_band
)
1925 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1926 "not a band node", isl_schedule_node_free(node
));
1927 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1929 return isl_schedule_node_free(node
);
1931 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1932 "cannot sink band node in anchored subtree",
1933 isl_schedule_node_free(node
));
1934 if (isl_schedule_tree_n_children(node
->tree
) == 0)
1937 contraction
= isl_schedule_node_get_subtree_contraction(node
);
1939 tree
= isl_schedule_node_get_tree(node
);
1940 child
= isl_schedule_tree_get_child(tree
, 0);
1941 tree
= isl_schedule_tree_reset_children(tree
);
1942 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, contraction
);
1943 tree
= isl_schedule_tree_append_to_leaves(child
, tree
);
1945 return isl_schedule_node_graft_tree(node
, tree
);
1948 /* Split "node" into two nested band nodes, one with the first "pos"
1949 * dimensions and one with the remaining dimensions.
1950 * The schedules of the two band nodes live in anonymous spaces.
1952 __isl_give isl_schedule_node
*isl_schedule_node_band_split(
1953 __isl_take isl_schedule_node
*node
, int pos
)
1955 isl_schedule_tree
*tree
;
1957 tree
= isl_schedule_node_get_tree(node
);
1958 tree
= isl_schedule_tree_band_split(tree
, pos
);
1959 return isl_schedule_node_graft_tree(node
, tree
);
1962 /* Return the context of the context node "node".
1964 __isl_give isl_set
*isl_schedule_node_context_get_context(
1965 __isl_keep isl_schedule_node
*node
)
1970 return isl_schedule_tree_context_get_context(node
->tree
);
1973 /* Return the domain of the domain node "node".
1975 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
1976 __isl_keep isl_schedule_node
*node
)
1981 return isl_schedule_tree_domain_get_domain(node
->tree
);
1984 /* Return the expansion map of expansion node "node".
1986 __isl_give isl_union_map
*isl_schedule_node_expansion_get_expansion(
1987 __isl_keep isl_schedule_node
*node
)
1992 return isl_schedule_tree_expansion_get_expansion(node
->tree
);
1995 /* Return the contraction of expansion node "node".
1997 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_expansion_get_contraction(
1998 __isl_keep isl_schedule_node
*node
)
2003 return isl_schedule_tree_expansion_get_contraction(node
->tree
);
2006 /* Replace the contraction and the expansion of the expansion node "node"
2007 * by "contraction" and "expansion".
2009 __isl_give isl_schedule_node
*
2010 isl_schedule_node_expansion_set_contraction_and_expansion(
2011 __isl_take isl_schedule_node
*node
,
2012 __isl_take isl_union_pw_multi_aff
*contraction
,
2013 __isl_take isl_union_map
*expansion
)
2015 isl_schedule_tree
*tree
;
2017 if (!node
|| !contraction
|| !expansion
)
2020 tree
= isl_schedule_tree_copy(node
->tree
);
2021 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
2022 contraction
, expansion
);
2023 return isl_schedule_node_graft_tree(node
, tree
);
2025 isl_schedule_node_free(node
);
2026 isl_union_pw_multi_aff_free(contraction
);
2027 isl_union_map_free(expansion
);
2031 /* Return the extension of the extension node "node".
2033 __isl_give isl_union_map
*isl_schedule_node_extension_get_extension(
2034 __isl_keep isl_schedule_node
*node
)
2039 return isl_schedule_tree_extension_get_extension(node
->tree
);
2042 /* Replace the extension of extension node "node" by "extension".
2044 __isl_give isl_schedule_node
*isl_schedule_node_extension_set_extension(
2045 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
2047 isl_schedule_tree
*tree
;
2049 if (!node
|| !extension
)
2052 tree
= isl_schedule_tree_copy(node
->tree
);
2053 tree
= isl_schedule_tree_extension_set_extension(tree
, extension
);
2054 return isl_schedule_node_graft_tree(node
, tree
);
2056 isl_schedule_node_free(node
);
2057 isl_union_map_free(extension
);
2061 /* Return the filter of the filter node "node".
2063 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
2064 __isl_keep isl_schedule_node
*node
)
2069 return isl_schedule_tree_filter_get_filter(node
->tree
);
2072 /* Replace the filter of filter node "node" by "filter".
2074 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
2075 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2077 isl_schedule_tree
*tree
;
2079 if (!node
|| !filter
)
2082 tree
= isl_schedule_tree_copy(node
->tree
);
2083 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
2084 return isl_schedule_node_graft_tree(node
, tree
);
2086 isl_schedule_node_free(node
);
2087 isl_union_set_free(filter
);
2091 /* Intersect the filter of filter node "node" with "filter".
2093 * If the filter of the node is already a subset of "filter",
2094 * then leave the node unchanged.
2096 __isl_give isl_schedule_node
*isl_schedule_node_filter_intersect_filter(
2097 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2099 isl_union_set
*node_filter
= NULL
;
2102 if (!node
|| !filter
)
2105 node_filter
= isl_schedule_node_filter_get_filter(node
);
2106 subset
= isl_union_set_is_subset(node_filter
, filter
);
2110 isl_union_set_free(node_filter
);
2111 isl_union_set_free(filter
);
2114 node_filter
= isl_union_set_intersect(node_filter
, filter
);
2115 node
= isl_schedule_node_filter_set_filter(node
, node_filter
);
2118 isl_schedule_node_free(node
);
2119 isl_union_set_free(node_filter
);
2120 isl_union_set_free(filter
);
2124 /* Return the guard of the guard node "node".
2126 __isl_give isl_set
*isl_schedule_node_guard_get_guard(
2127 __isl_keep isl_schedule_node
*node
)
2132 return isl_schedule_tree_guard_get_guard(node
->tree
);
2135 /* Return the mark identifier of the mark node "node".
2137 __isl_give isl_id
*isl_schedule_node_mark_get_id(
2138 __isl_keep isl_schedule_node
*node
)
2143 return isl_schedule_tree_mark_get_id(node
->tree
);
2146 /* Replace the child at position "pos" of the sequence node "node"
2147 * by the children of sequence root node of "tree".
2149 __isl_give isl_schedule_node
*isl_schedule_node_sequence_splice(
2150 __isl_take isl_schedule_node
*node
, int pos
,
2151 __isl_take isl_schedule_tree
*tree
)
2153 isl_schedule_tree
*node_tree
;
2157 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2158 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2159 "not a sequence node", goto error
);
2160 if (isl_schedule_tree_get_type(tree
) != isl_schedule_node_sequence
)
2161 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2162 "not a sequence node", goto error
);
2163 node_tree
= isl_schedule_node_get_tree(node
);
2164 node_tree
= isl_schedule_tree_sequence_splice(node_tree
, pos
, tree
);
2165 node
= isl_schedule_node_graft_tree(node
, node_tree
);
2169 isl_schedule_node_free(node
);
2170 isl_schedule_tree_free(tree
);
2174 /* Given a sequence node "node", with a child at position "pos" that
2175 * is also a sequence node, attach the children of that node directly
2176 * as children of "node" at that position, replacing the original child.
2178 * The filters of these children are intersected with the filter
2179 * of the child at position "pos".
2181 __isl_give isl_schedule_node
*isl_schedule_node_sequence_splice_child(
2182 __isl_take isl_schedule_node
*node
, int pos
)
2185 isl_union_set
*filter
;
2186 isl_schedule_node
*child
;
2187 isl_schedule_tree
*tree
;
2191 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2192 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2193 "not a sequence node", isl_schedule_node_free(node
));
2194 node
= isl_schedule_node_child(node
, pos
);
2195 node
= isl_schedule_node_child(node
, 0);
2196 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2197 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2198 "not a sequence node", isl_schedule_node_free(node
));
2199 child
= isl_schedule_node_copy(node
);
2200 node
= isl_schedule_node_parent(node
);
2201 filter
= isl_schedule_node_filter_get_filter(node
);
2202 n
= isl_schedule_node_n_children(child
);
2203 for (i
= 0; i
< n
; ++i
) {
2204 child
= isl_schedule_node_child(child
, i
);
2205 child
= isl_schedule_node_filter_intersect_filter(child
,
2206 isl_union_set_copy(filter
));
2207 child
= isl_schedule_node_parent(child
);
2209 isl_union_set_free(filter
);
2210 tree
= isl_schedule_node_get_tree(child
);
2211 isl_schedule_node_free(child
);
2212 node
= isl_schedule_node_parent(node
);
2213 node
= isl_schedule_node_sequence_splice(node
, pos
, tree
);
2218 /* Update the ancestors of "node" to point to the tree that "node"
2220 * That is, replace the child in the original parent that corresponds
2221 * to the current tree position by node->tree and continue updating
2222 * the ancestors in the same way until the root is reached.
2224 * If "fn" is not NULL, then it is called on each ancestor as we move up
2225 * the tree so that it can modify the ancestor before it is added
2226 * to the list of ancestors of the modified node.
2227 * The additional "pos" argument records the position
2228 * of the "tree" argument in the original schedule tree.
2230 * If "node" originally points to a leaf of the schedule tree, then make sure
2231 * that in the end it points to a leaf in the updated schedule tree.
2233 static __isl_give isl_schedule_node
*update_ancestors(
2234 __isl_take isl_schedule_node
*node
,
2235 __isl_give isl_schedule_tree
*(*fn
)(__isl_take isl_schedule_tree
*tree
,
2236 __isl_keep isl_schedule_node
*pos
, void *user
), void *user
)
2241 isl_schedule_tree
*tree
;
2242 isl_schedule_node
*pos
= NULL
;
2245 pos
= isl_schedule_node_copy(node
);
2247 node
= isl_schedule_node_cow(node
);
2249 return isl_schedule_node_free(pos
);
2251 ctx
= isl_schedule_node_get_ctx(node
);
2252 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
2253 tree
= isl_schedule_tree_copy(node
->tree
);
2255 for (i
= n
- 1; i
>= 0; --i
) {
2256 isl_schedule_tree
*parent
;
2258 parent
= isl_schedule_tree_list_get_schedule_tree(
2259 node
->ancestors
, i
);
2260 parent
= isl_schedule_tree_replace_child(parent
,
2261 node
->child_pos
[i
], tree
);
2263 pos
= isl_schedule_node_parent(pos
);
2264 parent
= fn(parent
, pos
, user
);
2266 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
2267 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
2273 isl_schedule_node_free(pos
);
2275 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
2276 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
2278 isl_schedule_tree_free(node
->tree
);
2279 node
->tree
= isl_schedule_node_get_leaf(node
);
2282 if (!node
->schedule
|| !node
->ancestors
)
2283 return isl_schedule_node_free(node
);
2288 /* Replace the subtree that "pos" points to by "tree", updating
2289 * the ancestors to maintain a consistent state.
2291 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
2292 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
2296 if (pos
->tree
== tree
) {
2297 isl_schedule_tree_free(tree
);
2301 pos
= isl_schedule_node_cow(pos
);
2305 isl_schedule_tree_free(pos
->tree
);
2308 return update_ancestors(pos
, NULL
, NULL
);
2310 isl_schedule_node_free(pos
);
2311 isl_schedule_tree_free(tree
);
2315 /* Make sure we can insert a node between "node" and its parent.
2316 * Return -1 on error, reporting the reason why we cannot insert a node.
2318 static int check_insert(__isl_keep isl_schedule_node
*node
)
2321 enum isl_schedule_node_type type
;
2323 has_parent
= isl_schedule_node_has_parent(node
);
2327 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2328 "cannot insert node outside of root", return -1);
2330 type
= isl_schedule_node_get_parent_type(node
);
2331 if (type
== isl_schedule_node_error
)
2333 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
2334 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2335 "cannot insert node between set or sequence node "
2336 "and its filter children", return -1);
2341 /* Insert a band node with partial schedule "mupa" between "node" and
2343 * Return a pointer to the new band node.
2345 * If any of the nodes in the subtree rooted at "node" depend on
2346 * the set of outer band nodes then we refuse to insert the band node.
2348 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
2349 __isl_take isl_schedule_node
*node
,
2350 __isl_take isl_multi_union_pw_aff
*mupa
)
2353 isl_schedule_band
*band
;
2354 isl_schedule_tree
*tree
;
2356 if (check_insert(node
) < 0)
2357 node
= isl_schedule_node_free(node
);
2358 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2362 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2363 "cannot insert band node in anchored subtree",
2366 tree
= isl_schedule_node_get_tree(node
);
2367 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
2368 tree
= isl_schedule_tree_insert_band(tree
, band
);
2369 node
= isl_schedule_node_graft_tree(node
, tree
);
2373 isl_schedule_node_free(node
);
2374 isl_multi_union_pw_aff_free(mupa
);
2378 /* Insert a context node with context "context" between "node" and its parent.
2379 * Return a pointer to the new context node.
2381 __isl_give isl_schedule_node
*isl_schedule_node_insert_context(
2382 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
2384 isl_schedule_tree
*tree
;
2386 if (check_insert(node
) < 0)
2387 node
= isl_schedule_node_free(node
);
2389 tree
= isl_schedule_node_get_tree(node
);
2390 tree
= isl_schedule_tree_insert_context(tree
, context
);
2391 node
= isl_schedule_node_graft_tree(node
, tree
);
2396 /* Insert an expansion node with the given "contraction" and "expansion"
2397 * between "node" and its parent.
2398 * Return a pointer to the new expansion node.
2400 * Typically the domain and range spaces of the expansion are different.
2401 * This means that only one of them can refer to the current domain space
2402 * in a consistent tree. It is up to the caller to ensure that the tree
2403 * returns to a consistent state.
2405 __isl_give isl_schedule_node
*isl_schedule_node_insert_expansion(
2406 __isl_take isl_schedule_node
*node
,
2407 __isl_take isl_union_pw_multi_aff
*contraction
,
2408 __isl_take isl_union_map
*expansion
)
2410 isl_schedule_tree
*tree
;
2412 if (check_insert(node
) < 0)
2413 node
= isl_schedule_node_free(node
);
2415 tree
= isl_schedule_node_get_tree(node
);
2416 tree
= isl_schedule_tree_insert_expansion(tree
, contraction
, expansion
);
2417 node
= isl_schedule_node_graft_tree(node
, tree
);
2422 /* Insert an extension node with extension "extension" between "node" and
2424 * Return a pointer to the new extension node.
2426 __isl_give isl_schedule_node
*isl_schedule_node_insert_extension(
2427 __isl_take isl_schedule_node
*node
,
2428 __isl_take isl_union_map
*extension
)
2430 isl_schedule_tree
*tree
;
2432 tree
= isl_schedule_node_get_tree(node
);
2433 tree
= isl_schedule_tree_insert_extension(tree
, extension
);
2434 node
= isl_schedule_node_graft_tree(node
, tree
);
2439 /* Insert a filter node with filter "filter" between "node" and its parent.
2440 * Return a pointer to the new filter node.
2442 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
2443 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2445 isl_schedule_tree
*tree
;
2447 if (check_insert(node
) < 0)
2448 node
= isl_schedule_node_free(node
);
2450 tree
= isl_schedule_node_get_tree(node
);
2451 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2452 node
= isl_schedule_node_graft_tree(node
, tree
);
2457 /* Insert a guard node with guard "guard" between "node" and its parent.
2458 * Return a pointer to the new guard node.
2460 __isl_give isl_schedule_node
*isl_schedule_node_insert_guard(
2461 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*guard
)
2463 isl_schedule_tree
*tree
;
2465 if (check_insert(node
) < 0)
2466 node
= isl_schedule_node_free(node
);
2468 tree
= isl_schedule_node_get_tree(node
);
2469 tree
= isl_schedule_tree_insert_guard(tree
, guard
);
2470 node
= isl_schedule_node_graft_tree(node
, tree
);
2475 /* Insert a mark node with mark identifier "mark" between "node" and
2477 * Return a pointer to the new mark node.
2479 __isl_give isl_schedule_node
*isl_schedule_node_insert_mark(
2480 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*mark
)
2482 isl_schedule_tree
*tree
;
2484 if (check_insert(node
) < 0)
2485 node
= isl_schedule_node_free(node
);
2487 tree
= isl_schedule_node_get_tree(node
);
2488 tree
= isl_schedule_tree_insert_mark(tree
, mark
);
2489 node
= isl_schedule_node_graft_tree(node
, tree
);
2494 /* Attach the current subtree of "node" to a sequence of filter tree nodes
2495 * with filters described by "filters", attach this sequence
2496 * of filter tree nodes as children to a new tree of type "type" and
2497 * replace the original subtree of "node" by this new tree.
2498 * Each copy of the original subtree is simplified with respect
2499 * to the corresponding filter.
2501 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
2502 __isl_take isl_schedule_node
*node
,
2503 enum isl_schedule_node_type type
,
2504 __isl_take isl_union_set_list
*filters
)
2508 isl_schedule_tree
*tree
;
2509 isl_schedule_tree_list
*list
;
2511 if (check_insert(node
) < 0)
2512 node
= isl_schedule_node_free(node
);
2514 if (!node
|| !filters
)
2517 ctx
= isl_schedule_node_get_ctx(node
);
2518 n
= isl_union_set_list_n_union_set(filters
);
2519 list
= isl_schedule_tree_list_alloc(ctx
, n
);
2520 for (i
= 0; i
< n
; ++i
) {
2521 isl_schedule_node
*node_i
;
2522 isl_schedule_tree
*tree
;
2523 isl_union_set
*filter
;
2525 filter
= isl_union_set_list_get_union_set(filters
, i
);
2526 node_i
= isl_schedule_node_copy(node
);
2527 node_i
= isl_schedule_node_gist(node_i
,
2528 isl_union_set_copy(filter
));
2529 tree
= isl_schedule_node_get_tree(node_i
);
2530 isl_schedule_node_free(node_i
);
2531 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2532 list
= isl_schedule_tree_list_add(list
, tree
);
2534 tree
= isl_schedule_tree_from_children(type
, list
);
2535 node
= isl_schedule_node_graft_tree(node
, tree
);
2537 isl_union_set_list_free(filters
);
2540 isl_union_set_list_free(filters
);
2541 isl_schedule_node_free(node
);
2545 /* Insert a sequence node with child filters "filters" between "node" and
2546 * its parent. That is, the tree that "node" points to is attached
2547 * to each of the child nodes of the filter nodes.
2548 * Return a pointer to the new sequence node.
2550 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
2551 __isl_take isl_schedule_node
*node
,
2552 __isl_take isl_union_set_list
*filters
)
2554 return isl_schedule_node_insert_children(node
,
2555 isl_schedule_node_sequence
, filters
);
2558 /* Insert a set node with child filters "filters" between "node" and
2559 * its parent. That is, the tree that "node" points to is attached
2560 * to each of the child nodes of the filter nodes.
2561 * Return a pointer to the new set node.
2563 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
2564 __isl_take isl_schedule_node
*node
,
2565 __isl_take isl_union_set_list
*filters
)
2567 return isl_schedule_node_insert_children(node
,
2568 isl_schedule_node_set
, filters
);
2571 /* Remove "node" from its schedule tree and return a pointer
2572 * to the leaf at the same position in the updated schedule tree.
2574 * It is not allowed to remove the root of a schedule tree or
2575 * a child of a set or sequence node.
2577 __isl_give isl_schedule_node
*isl_schedule_node_cut(
2578 __isl_take isl_schedule_node
*node
)
2580 isl_schedule_tree
*leaf
;
2581 enum isl_schedule_node_type parent_type
;
2585 if (!isl_schedule_node_has_parent(node
))
2586 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2587 "cannot cut root", return isl_schedule_node_free(node
));
2589 parent_type
= isl_schedule_node_get_parent_type(node
);
2590 if (parent_type
== isl_schedule_node_set
||
2591 parent_type
== isl_schedule_node_sequence
)
2592 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2593 "cannot cut child of set or sequence",
2594 return isl_schedule_node_free(node
));
2596 leaf
= isl_schedule_node_get_leaf(node
);
2597 return isl_schedule_node_graft_tree(node
, leaf
);
2600 /* Remove a single node from the schedule tree, attaching the child
2601 * of "node" directly to its parent.
2602 * Return a pointer to this former child or to the leaf the position
2603 * of the original node if there was no child.
2604 * It is not allowed to remove the root of a schedule tree,
2605 * a set or sequence node, a child of a set or sequence node or
2606 * a band node with an anchored subtree.
2608 __isl_give isl_schedule_node
*isl_schedule_node_delete(
2609 __isl_take isl_schedule_node
*node
)
2612 isl_schedule_tree
*tree
;
2613 enum isl_schedule_node_type type
;
2618 if (isl_schedule_node_get_tree_depth(node
) == 0)
2619 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2620 "cannot delete root node",
2621 return isl_schedule_node_free(node
));
2622 n
= isl_schedule_node_n_children(node
);
2624 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2625 "can only delete node with a single child",
2626 return isl_schedule_node_free(node
));
2627 type
= isl_schedule_node_get_parent_type(node
);
2628 if (type
== isl_schedule_node_sequence
|| type
== isl_schedule_node_set
)
2629 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2630 "cannot delete child of set or sequence",
2631 return isl_schedule_node_free(node
));
2632 if (isl_schedule_node_get_type(node
) == isl_schedule_node_band
) {
2635 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2637 return isl_schedule_node_free(node
);
2639 isl_die(isl_schedule_node_get_ctx(node
),
2641 "cannot delete band node with anchored subtree",
2642 return isl_schedule_node_free(node
));
2645 tree
= isl_schedule_node_get_tree(node
);
2646 if (!tree
|| isl_schedule_tree_has_children(tree
)) {
2647 tree
= isl_schedule_tree_child(tree
, 0);
2649 isl_schedule_tree_free(tree
);
2650 tree
= isl_schedule_node_get_leaf(node
);
2652 node
= isl_schedule_node_graft_tree(node
, tree
);
2657 /* Internal data structure for the group_ancestor callback.
2659 * If "finished" is set, then we no longer need to modify
2660 * any further ancestors.
2662 * "contraction" and "expansion" represent the expansion
2663 * that reflects the grouping.
2665 * "domain" contains the domain elements that reach the position
2666 * where the grouping is performed. That is, it is the range
2667 * of the resulting expansion.
2668 * "domain_universe" is the universe of "domain".
2669 * "group" is the set of group elements, i.e., the domain
2670 * of the resulting expansion.
2671 * "group_universe" is the universe of "group".
2673 * "sched" is the schedule for the group elements, in pratice
2674 * an identity mapping on "group_universe".
2675 * "dim" is the dimension of "sched".
2677 struct isl_schedule_group_data
{
2680 isl_union_map
*expansion
;
2681 isl_union_pw_multi_aff
*contraction
;
2683 isl_union_set
*domain
;
2684 isl_union_set
*domain_universe
;
2685 isl_union_set
*group
;
2686 isl_union_set
*group_universe
;
2689 isl_multi_aff
*sched
;
2692 /* Is domain covered by data->domain within data->domain_universe?
2694 static int locally_covered_by_domain(__isl_keep isl_union_set
*domain
,
2695 struct isl_schedule_group_data
*data
)
2698 isl_union_set
*test
;
2700 test
= isl_union_set_copy(domain
);
2701 test
= isl_union_set_intersect(test
,
2702 isl_union_set_copy(data
->domain_universe
));
2703 is_subset
= isl_union_set_is_subset(test
, data
->domain
);
2704 isl_union_set_free(test
);
2709 /* Update the band tree root "tree" to refer to the group instances
2710 * in data->group rather than the original domain elements in data->domain.
2711 * "pos" is the position in the original schedule tree where the modified
2712 * "tree" will be attached.
2714 * Add the part of the identity schedule on the group instances data->sched
2715 * that corresponds to this band node to the band schedule.
2716 * If the domain elements that reach the node and that are part
2717 * of data->domain_universe are all elements of data->domain (and therefore
2718 * replaced by the group instances) then this data->domain_universe
2719 * is removed from the domain of the band schedule.
2721 static __isl_give isl_schedule_tree
*group_band(
2722 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2723 struct isl_schedule_group_data
*data
)
2725 isl_union_set
*domain
;
2727 isl_multi_union_pw_aff
*mupa
, *partial
;
2729 int depth
, n
, has_id
;
2731 domain
= isl_schedule_node_get_domain(pos
);
2732 is_covered
= locally_covered_by_domain(domain
, data
);
2733 if (is_covered
>= 0 && is_covered
) {
2734 domain
= isl_union_set_universe(domain
);
2735 domain
= isl_union_set_subtract(domain
,
2736 isl_union_set_copy(data
->domain_universe
));
2737 tree
= isl_schedule_tree_band_intersect_domain(tree
, domain
);
2739 isl_union_set_free(domain
);
2741 return isl_schedule_tree_free(tree
);
2742 depth
= isl_schedule_node_get_schedule_depth(pos
);
2743 n
= isl_schedule_tree_band_n_member(tree
);
2744 ma
= isl_multi_aff_copy(data
->sched
);
2745 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, depth
);
2746 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, n
, data
->dim
- depth
- n
);
2747 mupa
= isl_multi_union_pw_aff_from_multi_aff(ma
);
2748 partial
= isl_schedule_tree_band_get_partial_schedule(tree
);
2749 has_id
= isl_multi_union_pw_aff_has_tuple_id(partial
, isl_dim_set
);
2751 partial
= isl_multi_union_pw_aff_free(partial
);
2752 } else if (has_id
) {
2754 id
= isl_multi_union_pw_aff_get_tuple_id(partial
, isl_dim_set
);
2755 mupa
= isl_multi_union_pw_aff_set_tuple_id(mupa
,
2758 partial
= isl_multi_union_pw_aff_union_add(partial
, mupa
);
2759 tree
= isl_schedule_tree_band_set_partial_schedule(tree
, partial
);
2764 /* Drop the parameters in "uset" that are not also in "space".
2765 * "n" is the number of parameters in "space".
2767 static __isl_give isl_union_set
*union_set_drop_extra_params(
2768 __isl_take isl_union_set
*uset
, __isl_keep isl_space
*space
, int n
)
2772 uset
= isl_union_set_align_params(uset
, isl_space_copy(space
));
2773 n2
= isl_union_set_dim(uset
, isl_dim_param
);
2774 uset
= isl_union_set_project_out(uset
, isl_dim_param
, n
, n2
- n
);
2779 /* Update the context tree root "tree" to refer to the group instances
2780 * in data->group rather than the original domain elements in data->domain.
2781 * "pos" is the position in the original schedule tree where the modified
2782 * "tree" will be attached.
2784 * We do not actually need to update "tree" since a context node only
2785 * refers to the schedule space. However, we may need to update "data"
2786 * to not refer to any parameters introduced by the context node.
2788 static __isl_give isl_schedule_tree
*group_context(
2789 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2790 struct isl_schedule_group_data
*data
)
2793 isl_union_set
*domain
;
2797 if (isl_schedule_node_get_tree_depth(pos
) == 1)
2800 domain
= isl_schedule_node_get_universe_domain(pos
);
2801 space
= isl_union_set_get_space(domain
);
2802 isl_union_set_free(domain
);
2804 n1
= isl_space_dim(space
, isl_dim_param
);
2805 data
->expansion
= isl_union_map_align_params(data
->expansion
, space
);
2806 n2
= isl_union_map_dim(data
->expansion
, isl_dim_param
);
2808 if (!data
->expansion
)
2809 return isl_schedule_tree_free(tree
);
2813 involves
= isl_union_map_involves_dims(data
->expansion
,
2814 isl_dim_param
, n1
, n2
- n1
);
2816 return isl_schedule_tree_free(tree
);
2818 isl_die(isl_schedule_node_get_ctx(pos
), isl_error_invalid
,
2819 "grouping cannot only refer to global parameters",
2820 return isl_schedule_tree_free(tree
));
2822 data
->expansion
= isl_union_map_project_out(data
->expansion
,
2823 isl_dim_param
, n1
, n2
- n1
);
2824 space
= isl_union_map_get_space(data
->expansion
);
2826 data
->contraction
= isl_union_pw_multi_aff_align_params(
2827 data
->contraction
, isl_space_copy(space
));
2828 n2
= isl_union_pw_multi_aff_dim(data
->contraction
, isl_dim_param
);
2829 data
->contraction
= isl_union_pw_multi_aff_drop_dims(data
->contraction
,
2830 isl_dim_param
, n1
, n2
- n1
);
2832 data
->domain
= union_set_drop_extra_params(data
->domain
, space
, n1
);
2833 data
->domain_universe
=
2834 union_set_drop_extra_params(data
->domain_universe
, space
, n1
);
2835 data
->group
= union_set_drop_extra_params(data
->group
, space
, n1
);
2836 data
->group_universe
=
2837 union_set_drop_extra_params(data
->group_universe
, space
, n1
);
2839 data
->sched
= isl_multi_aff_align_params(data
->sched
,
2840 isl_space_copy(space
));
2841 n2
= isl_multi_aff_dim(data
->sched
, isl_dim_param
);
2842 data
->sched
= isl_multi_aff_drop_dims(data
->sched
,
2843 isl_dim_param
, n1
, n2
- n1
);
2845 isl_space_free(space
);
2850 /* Update the domain tree root "tree" to refer to the group instances
2851 * in data->group rather than the original domain elements in data->domain.
2852 * "pos" is the position in the original schedule tree where the modified
2853 * "tree" will be attached.
2855 * We first double-check that all grouped domain elements are actually
2856 * part of the root domain and then replace those elements by the group
2859 static __isl_give isl_schedule_tree
*group_domain(
2860 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2861 struct isl_schedule_group_data
*data
)
2863 isl_union_set
*domain
;
2866 domain
= isl_schedule_tree_domain_get_domain(tree
);
2867 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2868 isl_union_set_free(domain
);
2870 return isl_schedule_tree_free(tree
);
2872 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2873 "grouped domain should be part of outer domain",
2874 return isl_schedule_tree_free(tree
));
2875 domain
= isl_schedule_tree_domain_get_domain(tree
);
2876 domain
= isl_union_set_subtract(domain
,
2877 isl_union_set_copy(data
->domain
));
2878 domain
= isl_union_set_union(domain
, isl_union_set_copy(data
->group
));
2879 tree
= isl_schedule_tree_domain_set_domain(tree
, domain
);
2884 /* Update the expansion tree root "tree" to refer to the group instances
2885 * in data->group rather than the original domain elements in data->domain.
2886 * "pos" is the position in the original schedule tree where the modified
2887 * "tree" will be attached.
2889 * Let G_1 -> D_1 be the expansion of "tree" and G_2 -> D_2 the newly
2890 * introduced expansion in a descendant of "tree".
2891 * We first double-check that D_2 is a subset of D_1.
2892 * Then we remove D_2 from the range of G_1 -> D_1 and add the mapping
2893 * G_1 -> D_1 . D_2 -> G_2.
2894 * Simmilarly, we restrict the domain of the contraction to the universe
2895 * of the range of the updated expansion and add G_2 -> D_2 . D_1 -> G_1,
2896 * attempting to remove the domain constraints of this additional part.
2898 static __isl_give isl_schedule_tree
*group_expansion(
2899 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2900 struct isl_schedule_group_data
*data
)
2902 isl_union_set
*domain
;
2903 isl_union_map
*expansion
, *umap
;
2904 isl_union_pw_multi_aff
*contraction
, *upma
;
2907 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2908 domain
= isl_union_map_range(expansion
);
2909 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2910 isl_union_set_free(domain
);
2912 return isl_schedule_tree_free(tree
);
2914 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2915 "grouped domain should be part "
2916 "of outer expansion domain",
2917 return isl_schedule_tree_free(tree
));
2918 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2919 umap
= isl_union_map_from_union_pw_multi_aff(
2920 isl_union_pw_multi_aff_copy(data
->contraction
));
2921 umap
= isl_union_map_apply_range(expansion
, umap
);
2922 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2923 expansion
= isl_union_map_subtract_range(expansion
,
2924 isl_union_set_copy(data
->domain
));
2925 expansion
= isl_union_map_union(expansion
, umap
);
2926 umap
= isl_union_map_universe(isl_union_map_copy(expansion
));
2927 domain
= isl_union_map_range(umap
);
2928 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
2929 umap
= isl_union_map_from_union_pw_multi_aff(contraction
);
2930 umap
= isl_union_map_apply_range(isl_union_map_copy(data
->expansion
),
2932 upma
= isl_union_pw_multi_aff_from_union_map(umap
);
2933 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
2934 contraction
= isl_union_pw_multi_aff_intersect_domain(contraction
,
2936 domain
= isl_union_pw_multi_aff_domain(
2937 isl_union_pw_multi_aff_copy(upma
));
2938 upma
= isl_union_pw_multi_aff_gist(upma
, domain
);
2939 contraction
= isl_union_pw_multi_aff_union_add(contraction
, upma
);
2940 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
2941 contraction
, expansion
);
2946 /* Update the tree root "tree" to refer to the group instances
2947 * in data->group rather than the original domain elements in data->domain.
2948 * "pos" is the position in the original schedule tree where the modified
2949 * "tree" will be attached.
2951 * If we have come across a domain or expansion node before (data->finished
2952 * is set), then we no longer need perform any modifications.
2954 * If "tree" is a filter, then we add data->group_universe to the filter.
2955 * We also remove data->domain_universe from the filter if all the domain
2956 * elements in this universe that reach the filter node are part of
2957 * the elements that are being grouped by data->expansion.
2958 * If "tree" is a band, domain or expansion, then it is handled
2959 * in a separate function.
2961 static __isl_give isl_schedule_tree
*group_ancestor(
2962 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2965 struct isl_schedule_group_data
*data
= user
;
2966 isl_union_set
*domain
;
2970 return isl_schedule_tree_free(tree
);
2975 switch (isl_schedule_tree_get_type(tree
)) {
2976 case isl_schedule_node_error
:
2977 return isl_schedule_tree_free(tree
);
2978 case isl_schedule_node_extension
:
2979 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_unsupported
,
2980 "grouping not allowed in extended tree",
2981 return isl_schedule_tree_free(tree
));
2982 case isl_schedule_node_band
:
2983 tree
= group_band(tree
, pos
, data
);
2985 case isl_schedule_node_context
:
2986 tree
= group_context(tree
, pos
, data
);
2988 case isl_schedule_node_domain
:
2989 tree
= group_domain(tree
, pos
, data
);
2992 case isl_schedule_node_filter
:
2993 domain
= isl_schedule_node_get_domain(pos
);
2994 is_covered
= locally_covered_by_domain(domain
, data
);
2995 isl_union_set_free(domain
);
2997 return isl_schedule_tree_free(tree
);
2998 domain
= isl_schedule_tree_filter_get_filter(tree
);
3000 domain
= isl_union_set_subtract(domain
,
3001 isl_union_set_copy(data
->domain_universe
));
3002 domain
= isl_union_set_union(domain
,
3003 isl_union_set_copy(data
->group_universe
));
3004 tree
= isl_schedule_tree_filter_set_filter(tree
, domain
);
3006 case isl_schedule_node_expansion
:
3007 tree
= group_expansion(tree
, pos
, data
);
3010 case isl_schedule_node_leaf
:
3011 case isl_schedule_node_guard
:
3012 case isl_schedule_node_mark
:
3013 case isl_schedule_node_sequence
:
3014 case isl_schedule_node_set
:
3021 /* Group the domain elements that reach "node" into instances
3022 * of a single statement with identifier "group_id".
3023 * In particular, group the domain elements according to their
3026 * That is, introduce an expansion node with as contraction
3027 * the prefix schedule (with the target space replaced by "group_id")
3028 * and as expansion the inverse of this contraction (with its range
3029 * intersected with the domain elements that reach "node").
3030 * The outer nodes are then modified to refer to the group instances
3031 * instead of the original domain elements.
3033 * No instance of "group_id" is allowed to reach "node" prior
3035 * No ancestor of "node" is allowed to be an extension node.
3037 * Return a pointer to original node in tree, i.e., the child
3038 * of the newly introduced expansion node.
3040 __isl_give isl_schedule_node
*isl_schedule_node_group(
3041 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*group_id
)
3043 struct isl_schedule_group_data data
= { 0 };
3045 isl_union_set
*domain
;
3046 isl_union_pw_multi_aff
*contraction
;
3047 isl_union_map
*expansion
;
3050 if (!node
|| !group_id
)
3052 if (check_insert(node
) < 0)
3055 domain
= isl_schedule_node_get_domain(node
);
3056 data
.domain
= isl_union_set_copy(domain
);
3057 data
.domain_universe
= isl_union_set_copy(domain
);
3058 data
.domain_universe
= isl_union_set_universe(data
.domain_universe
);
3060 data
.dim
= isl_schedule_node_get_schedule_depth(node
);
3061 if (data
.dim
== 0) {
3064 isl_union_set
*group
;
3065 isl_union_map
*univ
;
3067 ctx
= isl_schedule_node_get_ctx(node
);
3068 space
= isl_space_set_alloc(ctx
, 0, 0);
3069 space
= isl_space_set_tuple_id(space
, isl_dim_set
, group_id
);
3070 set
= isl_set_universe(isl_space_copy(space
));
3071 group
= isl_union_set_from_set(set
);
3072 expansion
= isl_union_map_from_domain_and_range(domain
, group
);
3073 univ
= isl_union_map_universe(isl_union_map_copy(expansion
));
3074 contraction
= isl_union_pw_multi_aff_from_union_map(univ
);
3075 expansion
= isl_union_map_reverse(expansion
);
3077 isl_multi_union_pw_aff
*prefix
;
3078 isl_union_set
*univ
;
3081 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node
);
3082 prefix
= isl_multi_union_pw_aff_set_tuple_id(prefix
,
3083 isl_dim_set
, group_id
);
3084 space
= isl_multi_union_pw_aff_get_space(prefix
);
3085 contraction
= isl_union_pw_multi_aff_from_multi_union_pw_aff(
3087 univ
= isl_union_set_universe(isl_union_set_copy(domain
));
3089 isl_union_pw_multi_aff_intersect_domain(contraction
, univ
);
3090 expansion
= isl_union_map_from_union_pw_multi_aff(
3091 isl_union_pw_multi_aff_copy(contraction
));
3092 expansion
= isl_union_map_reverse(expansion
);
3093 expansion
= isl_union_map_intersect_range(expansion
, domain
);
3095 space
= isl_space_map_from_set(space
);
3096 data
.sched
= isl_multi_aff_identity(space
);
3097 data
.group
= isl_union_map_domain(isl_union_map_copy(expansion
));
3098 data
.group
= isl_union_set_coalesce(data
.group
);
3099 data
.group_universe
= isl_union_set_copy(data
.group
);
3100 data
.group_universe
= isl_union_set_universe(data
.group_universe
);
3101 data
.expansion
= isl_union_map_copy(expansion
);
3102 data
.contraction
= isl_union_pw_multi_aff_copy(contraction
);
3103 node
= isl_schedule_node_insert_expansion(node
, contraction
, expansion
);
3105 disjoint
= isl_union_set_is_disjoint(data
.domain_universe
,
3106 data
.group_universe
);
3108 node
= update_ancestors(node
, &group_ancestor
, &data
);
3110 isl_union_set_free(data
.domain
);
3111 isl_union_set_free(data
.domain_universe
);
3112 isl_union_set_free(data
.group
);
3113 isl_union_set_free(data
.group_universe
);
3114 isl_multi_aff_free(data
.sched
);
3115 isl_union_map_free(data
.expansion
);
3116 isl_union_pw_multi_aff_free(data
.contraction
);
3118 node
= isl_schedule_node_child(node
, 0);
3120 if (!node
|| disjoint
< 0)
3121 return isl_schedule_node_free(node
);
3123 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3124 "group instances already reach node",
3125 isl_schedule_node_free(node
));
3129 isl_schedule_node_free(node
);
3130 isl_id_free(group_id
);
3134 /* Compute the gist of the given band node with respect to "context".
3136 __isl_give isl_schedule_node
*isl_schedule_node_band_gist(
3137 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3139 isl_schedule_tree
*tree
;
3141 tree
= isl_schedule_node_get_tree(node
);
3142 tree
= isl_schedule_tree_band_gist(tree
, context
);
3143 return isl_schedule_node_graft_tree(node
, tree
);
3146 /* Internal data structure for isl_schedule_node_gist.
3147 * "n_expansion" is the number of outer expansion nodes
3148 * with respect to the current position
3149 * "filters" contains an element for each outer filter, expansion or
3150 * extension node with respect to the current position, each representing
3151 * the intersection of the previous element and the filter on the filter node
3152 * or the expansion/extension of the previous element.
3153 * The first element in the original context passed to isl_schedule_node_gist.
3155 struct isl_node_gist_data
{
3157 isl_union_set_list
*filters
;
3160 /* Enter the expansion node "node" during a isl_schedule_node_gist traversal.
3162 * In particular, add an extra element to data->filters containing
3163 * the expansion of the previous element and replace the expansion
3164 * and contraction on "node" by the gist with respect to these filters.
3165 * Also keep track of the fact that we have entered another expansion.
3167 static __isl_give isl_schedule_node
*gist_enter_expansion(
3168 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3171 isl_union_set
*inner
;
3172 isl_union_map
*expansion
;
3173 isl_union_pw_multi_aff
*contraction
;
3175 data
->n_expansion
++;
3177 n
= isl_union_set_list_n_union_set(data
->filters
);
3178 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3179 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3180 inner
= isl_union_set_apply(inner
, expansion
);
3182 contraction
= isl_schedule_node_expansion_get_contraction(node
);
3183 contraction
= isl_union_pw_multi_aff_gist(contraction
,
3184 isl_union_set_copy(inner
));
3186 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
3188 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3189 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3190 expansion
= isl_union_map_gist_domain(expansion
, inner
);
3191 node
= isl_schedule_node_expansion_set_contraction_and_expansion(node
,
3192 contraction
, expansion
);
3197 /* Leave the expansion node "node" during a isl_schedule_node_gist traversal.
3199 * In particular, remove the element in data->filters that was added by
3200 * gist_enter_expansion and decrement the number of outer expansions.
3202 * The expansion has already been simplified in gist_enter_expansion.
3203 * If this simplification results in an identity expansion, then
3204 * it is removed here.
3206 static __isl_give isl_schedule_node
*gist_leave_expansion(
3207 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3211 isl_union_map
*expansion
;
3213 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3214 identity
= isl_union_map_is_identity(expansion
);
3215 isl_union_map_free(expansion
);
3218 node
= isl_schedule_node_free(node
);
3220 node
= isl_schedule_node_delete(node
);
3222 n
= isl_union_set_list_n_union_set(data
->filters
);
3223 data
->filters
= isl_union_set_list_drop(data
->filters
, n
- 1, 1);
3225 data
->n_expansion
--;
3230 /* Enter the extension node "node" during a isl_schedule_node_gist traversal.
3232 * In particular, add an extra element to data->filters containing
3233 * the union of the previous element with the additional domain elements
3234 * introduced by the extension.
3236 static __isl_give isl_schedule_node
*gist_enter_extension(
3237 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3240 isl_union_set
*inner
, *extra
;
3241 isl_union_map
*extension
;
3243 n
= isl_union_set_list_n_union_set(data
->filters
);
3244 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3245 extension
= isl_schedule_node_extension_get_extension(node
);
3246 extra
= isl_union_map_range(extension
);
3247 inner
= isl_union_set_union(inner
, extra
);
3249 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
3254 /* Can we finish gisting at this node?
3255 * That is, is the filter on the current filter node a subset of
3256 * the original context passed to isl_schedule_node_gist?
3257 * If we have gone through any expansions, then we cannot perform
3258 * this test since the current domain elements are incomparable
3259 * to the domain elements in the original context.
3261 static int gist_done(__isl_keep isl_schedule_node
*node
,
3262 struct isl_node_gist_data
*data
)
3264 isl_union_set
*filter
, *outer
;
3267 if (data
->n_expansion
!= 0)
3270 filter
= isl_schedule_node_filter_get_filter(node
);
3271 outer
= isl_union_set_list_get_union_set(data
->filters
, 0);
3272 subset
= isl_union_set_is_subset(filter
, outer
);
3273 isl_union_set_free(outer
);
3274 isl_union_set_free(filter
);
3279 /* Callback for "traverse" to enter a node and to move
3280 * to the deepest initial subtree that should be traversed
3281 * by isl_schedule_node_gist.
3283 * The "filters" list is extended by one element each time
3284 * we come across a filter node by the result of intersecting
3285 * the last element in the list with the filter on the filter node.
3287 * If the filter on the current filter node is a subset of
3288 * the original context passed to isl_schedule_node_gist,
3289 * then there is no need to go into its subtree since it cannot
3290 * be further simplified by the context. The "filters" list is
3291 * still extended for consistency, but the actual value of the
3292 * added element is immaterial since it will not be used.
3294 * Otherwise, the filter on the current filter node is replaced by
3295 * the gist of the original filter with respect to the intersection
3296 * of the original context with the intermediate filters.
3298 * If the new element in the "filters" list is empty, then no elements
3299 * can reach the descendants of the current filter node. The subtree
3300 * underneath the filter node is therefore removed.
3302 * Each expansion node we come across is handled by
3303 * gist_enter_expansion.
3305 * Each extension node we come across is handled by
3306 * gist_enter_extension.
3308 static __isl_give isl_schedule_node
*gist_enter(
3309 __isl_take isl_schedule_node
*node
, void *user
)
3311 struct isl_node_gist_data
*data
= user
;
3314 isl_union_set
*filter
, *inner
;
3318 switch (isl_schedule_node_get_type(node
)) {
3319 case isl_schedule_node_error
:
3320 return isl_schedule_node_free(node
);
3321 case isl_schedule_node_expansion
:
3322 node
= gist_enter_expansion(node
, data
);
3324 case isl_schedule_node_extension
:
3325 node
= gist_enter_extension(node
, data
);
3327 case isl_schedule_node_band
:
3328 case isl_schedule_node_context
:
3329 case isl_schedule_node_domain
:
3330 case isl_schedule_node_guard
:
3331 case isl_schedule_node_leaf
:
3332 case isl_schedule_node_mark
:
3333 case isl_schedule_node_sequence
:
3334 case isl_schedule_node_set
:
3336 case isl_schedule_node_filter
:
3339 done
= gist_done(node
, data
);
3340 filter
= isl_schedule_node_filter_get_filter(node
);
3341 if (done
< 0 || done
) {
3342 data
->filters
= isl_union_set_list_add(data
->filters
,
3345 return isl_schedule_node_free(node
);
3348 n
= isl_union_set_list_n_union_set(data
->filters
);
3349 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3350 filter
= isl_union_set_gist(filter
, isl_union_set_copy(inner
));
3351 node
= isl_schedule_node_filter_set_filter(node
,
3352 isl_union_set_copy(filter
));
3353 filter
= isl_union_set_intersect(filter
, inner
);
3354 empty
= isl_union_set_is_empty(filter
);
3355 data
->filters
= isl_union_set_list_add(data
->filters
, filter
);
3357 return isl_schedule_node_free(node
);
3360 node
= isl_schedule_node_child(node
, 0);
3361 node
= isl_schedule_node_cut(node
);
3362 node
= isl_schedule_node_parent(node
);
3364 } while (isl_schedule_node_has_children(node
) &&
3365 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3370 /* Callback for "traverse" to leave a node for isl_schedule_node_gist.
3372 * In particular, if the current node is a filter node, then we remove
3373 * the element on the "filters" list that was added when we entered
3374 * the node. There is no need to compute any gist here, since we
3375 * already did that when we entered the node.
3377 * Expansion nodes are handled by gist_leave_expansion.
3379 * If the current node is an extension, then remove the element
3380 * in data->filters that was added by gist_enter_extension.
3382 * If the current node is a band node, then we compute the gist of
3383 * the band node with respect to the intersection of the original context
3384 * and the intermediate filters.
3386 * If the current node is a sequence or set node, then some of
3387 * the filter children may have become empty and so they are removed.
3388 * If only one child is left, then the set or sequence node along with
3389 * the single remaining child filter is removed. The filter can be
3390 * removed because the filters on a sequence or set node are supposed
3391 * to partition the incoming domain instances.
3392 * In principle, it should then be impossible for there to be zero
3393 * remaining children, but should this happen, we replace the entire
3394 * subtree with an empty filter.
3396 static __isl_give isl_schedule_node
*gist_leave(
3397 __isl_take isl_schedule_node
*node
, void *user
)
3399 struct isl_node_gist_data
*data
= user
;
3400 isl_schedule_tree
*tree
;
3402 isl_union_set
*filter
;
3404 switch (isl_schedule_node_get_type(node
)) {
3405 case isl_schedule_node_error
:
3406 return isl_schedule_node_free(node
);
3407 case isl_schedule_node_expansion
:
3408 node
= gist_leave_expansion(node
, data
);
3410 case isl_schedule_node_extension
:
3411 case isl_schedule_node_filter
:
3412 n
= isl_union_set_list_n_union_set(data
->filters
);
3413 data
->filters
= isl_union_set_list_drop(data
->filters
,
3416 case isl_schedule_node_band
:
3417 n
= isl_union_set_list_n_union_set(data
->filters
);
3418 filter
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3419 node
= isl_schedule_node_band_gist(node
, filter
);
3421 case isl_schedule_node_set
:
3422 case isl_schedule_node_sequence
:
3423 tree
= isl_schedule_node_get_tree(node
);
3424 n
= isl_schedule_tree_n_children(tree
);
3425 for (i
= n
- 1; i
>= 0; --i
) {
3426 isl_schedule_tree
*child
;
3427 isl_union_set
*filter
;
3430 child
= isl_schedule_tree_get_child(tree
, i
);
3431 filter
= isl_schedule_tree_filter_get_filter(child
);
3432 empty
= isl_union_set_is_empty(filter
);
3433 isl_union_set_free(filter
);
3434 isl_schedule_tree_free(child
);
3436 tree
= isl_schedule_tree_free(tree
);
3438 tree
= isl_schedule_tree_drop_child(tree
, i
);
3440 n
= isl_schedule_tree_n_children(tree
);
3441 node
= isl_schedule_node_graft_tree(node
, tree
);
3443 node
= isl_schedule_node_delete(node
);
3444 node
= isl_schedule_node_delete(node
);
3445 } else if (n
== 0) {
3449 isl_union_set_list_get_union_set(data
->filters
, 0);
3450 space
= isl_union_set_get_space(filter
);
3451 isl_union_set_free(filter
);
3452 filter
= isl_union_set_empty(space
);
3453 node
= isl_schedule_node_cut(node
);
3454 node
= isl_schedule_node_insert_filter(node
, filter
);
3457 case isl_schedule_node_context
:
3458 case isl_schedule_node_domain
:
3459 case isl_schedule_node_guard
:
3460 case isl_schedule_node_leaf
:
3461 case isl_schedule_node_mark
:
3468 /* Compute the gist of the subtree at "node" with respect to
3469 * the reaching domain elements in "context".
3470 * In particular, compute the gist of all band and filter nodes
3471 * in the subtree with respect to "context". Children of set or sequence
3472 * nodes that end up with an empty filter are removed completely.
3474 * We keep track of the intersection of "context" with all outer filters
3475 * of the current node within the subtree in the final element of "filters".
3476 * Initially, this list contains the single element "context" and it is
3477 * extended or shortened each time we enter or leave a filter node.
3479 __isl_give isl_schedule_node
*isl_schedule_node_gist(
3480 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3482 struct isl_node_gist_data data
;
3484 data
.n_expansion
= 0;
3485 data
.filters
= isl_union_set_list_from_union_set(context
);
3486 node
= traverse(node
, &gist_enter
, &gist_leave
, &data
);
3487 isl_union_set_list_free(data
.filters
);
3491 /* Intersect the domain of domain node "node" with "domain".
3493 * If the domain of "node" is already a subset of "domain",
3494 * then nothing needs to be changed.
3496 * Otherwise, we replace the domain of the domain node by the intersection
3497 * and simplify the subtree rooted at "node" with respect to this intersection.
3499 __isl_give isl_schedule_node
*isl_schedule_node_domain_intersect_domain(
3500 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
)
3502 isl_schedule_tree
*tree
;
3503 isl_union_set
*uset
;
3506 if (!node
|| !domain
)
3509 uset
= isl_schedule_tree_domain_get_domain(node
->tree
);
3510 is_subset
= isl_union_set_is_subset(uset
, domain
);
3511 isl_union_set_free(uset
);
3515 isl_union_set_free(domain
);
3519 tree
= isl_schedule_tree_copy(node
->tree
);
3520 uset
= isl_schedule_tree_domain_get_domain(tree
);
3521 uset
= isl_union_set_intersect(uset
, domain
);
3522 tree
= isl_schedule_tree_domain_set_domain(tree
,
3523 isl_union_set_copy(uset
));
3524 node
= isl_schedule_node_graft_tree(node
, tree
);
3526 node
= isl_schedule_node_child(node
, 0);
3527 node
= isl_schedule_node_gist(node
, uset
);
3528 node
= isl_schedule_node_parent(node
);
3532 isl_schedule_node_free(node
);
3533 isl_union_set_free(domain
);
3537 /* Replace the domain of domain node "node" with the gist
3538 * of the original domain with respect to the parameter domain "context".
3540 __isl_give isl_schedule_node
*isl_schedule_node_domain_gist_params(
3541 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
3543 isl_union_set
*domain
;
3544 isl_schedule_tree
*tree
;
3546 if (!node
|| !context
)
3549 tree
= isl_schedule_tree_copy(node
->tree
);
3550 domain
= isl_schedule_tree_domain_get_domain(node
->tree
);
3551 domain
= isl_union_set_gist_params(domain
, context
);
3552 tree
= isl_schedule_tree_domain_set_domain(tree
, domain
);
3553 node
= isl_schedule_node_graft_tree(node
, tree
);
3557 isl_schedule_node_free(node
);
3558 isl_set_free(context
);
3562 /* Internal data structure for isl_schedule_node_get_subtree_expansion.
3563 * "expansions" contains a list of accumulated expansions
3564 * for each outer expansion, set or sequence node. The first element
3565 * in the list is an identity mapping on the reaching domain elements.
3566 * "res" collects the results.
3568 struct isl_subtree_expansion_data
{
3569 isl_union_map_list
*expansions
;
3573 /* Callback for "traverse" to enter a node and to move
3574 * to the deepest initial subtree that should be traversed
3575 * by isl_schedule_node_get_subtree_expansion.
3577 * Whenever we come across an expansion node, the last element
3578 * of data->expansions is combined with the expansion
3579 * on the expansion node.
3581 * Whenever we come across a filter node that is the child
3582 * of a set or sequence node, data->expansions is extended
3583 * with a new element that restricts the previous element
3584 * to the elements selected by the filter.
3585 * The previous element can then be reused while backtracking.
3587 static __isl_give isl_schedule_node
*subtree_expansion_enter(
3588 __isl_take isl_schedule_node
*node
, void *user
)
3590 struct isl_subtree_expansion_data
*data
= user
;
3593 enum isl_schedule_node_type type
;
3594 isl_union_set
*filter
;
3595 isl_union_map
*inner
, *expansion
;
3598 switch (isl_schedule_node_get_type(node
)) {
3599 case isl_schedule_node_error
:
3600 return isl_schedule_node_free(node
);
3601 case isl_schedule_node_filter
:
3602 type
= isl_schedule_node_get_parent_type(node
);
3603 if (type
!= isl_schedule_node_set
&&
3604 type
!= isl_schedule_node_sequence
)
3606 filter
= isl_schedule_node_filter_get_filter(node
);
3607 n
= isl_union_map_list_n_union_map(data
->expansions
);
3609 isl_union_map_list_get_union_map(data
->expansions
,
3611 inner
= isl_union_map_intersect_range(inner
, filter
);
3613 isl_union_map_list_add(data
->expansions
, inner
);
3615 case isl_schedule_node_expansion
:
3616 n
= isl_union_map_list_n_union_map(data
->expansions
);
3618 isl_schedule_node_expansion_get_expansion(node
);
3620 isl_union_map_list_get_union_map(data
->expansions
,
3622 inner
= isl_union_map_apply_range(inner
, expansion
);
3624 isl_union_map_list_set_union_map(data
->expansions
,
3627 case isl_schedule_node_band
:
3628 case isl_schedule_node_context
:
3629 case isl_schedule_node_domain
:
3630 case isl_schedule_node_extension
:
3631 case isl_schedule_node_guard
:
3632 case isl_schedule_node_leaf
:
3633 case isl_schedule_node_mark
:
3634 case isl_schedule_node_sequence
:
3635 case isl_schedule_node_set
:
3638 } while (isl_schedule_node_has_children(node
) &&
3639 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3644 /* Callback for "traverse" to leave a node for
3645 * isl_schedule_node_get_subtree_expansion.
3647 * If we come across a filter node that is the child
3648 * of a set or sequence node, then we remove the element
3649 * of data->expansions that was added in subtree_expansion_enter.
3651 * If we reach a leaf node, then the accumulated expansion is
3652 * added to data->res.
3654 static __isl_give isl_schedule_node
*subtree_expansion_leave(
3655 __isl_take isl_schedule_node
*node
, void *user
)
3657 struct isl_subtree_expansion_data
*data
= user
;
3659 isl_union_map
*inner
;
3660 enum isl_schedule_node_type type
;
3662 switch (isl_schedule_node_get_type(node
)) {
3663 case isl_schedule_node_error
:
3664 return isl_schedule_node_free(node
);
3665 case isl_schedule_node_filter
:
3666 type
= isl_schedule_node_get_parent_type(node
);
3667 if (type
!= isl_schedule_node_set
&&
3668 type
!= isl_schedule_node_sequence
)
3670 n
= isl_union_map_list_n_union_map(data
->expansions
);
3671 data
->expansions
= isl_union_map_list_drop(data
->expansions
,
3674 case isl_schedule_node_leaf
:
3675 n
= isl_union_map_list_n_union_map(data
->expansions
);
3676 inner
= isl_union_map_list_get_union_map(data
->expansions
,
3678 data
->res
= isl_union_map_union(data
->res
, inner
);
3680 case isl_schedule_node_band
:
3681 case isl_schedule_node_context
:
3682 case isl_schedule_node_domain
:
3683 case isl_schedule_node_expansion
:
3684 case isl_schedule_node_extension
:
3685 case isl_schedule_node_guard
:
3686 case isl_schedule_node_mark
:
3687 case isl_schedule_node_sequence
:
3688 case isl_schedule_node_set
:
3695 /* Return a mapping from the domain elements that reach "node"
3696 * to the corresponding domain elements in the leaves of the subtree
3697 * rooted at "node" obtained by composing the intermediate expansions.
3699 * We start out with an identity mapping between the domain elements
3700 * that reach "node" and compose it with all the expansions
3701 * on a path from "node" to a leaf while traversing the subtree.
3702 * Within the children of an a sequence or set node, the
3703 * accumulated expansion is restricted to the elements selected
3704 * by the filter child.
3706 __isl_give isl_union_map
*isl_schedule_node_get_subtree_expansion(
3707 __isl_keep isl_schedule_node
*node
)
3709 struct isl_subtree_expansion_data data
;
3711 isl_union_set
*domain
;
3712 isl_union_map
*expansion
;
3717 domain
= isl_schedule_node_get_universe_domain(node
);
3718 space
= isl_union_set_get_space(domain
);
3719 expansion
= isl_union_set_identity(domain
);
3720 data
.res
= isl_union_map_empty(space
);
3721 data
.expansions
= isl_union_map_list_from_union_map(expansion
);
3723 node
= isl_schedule_node_copy(node
);
3724 node
= traverse(node
, &subtree_expansion_enter
,
3725 &subtree_expansion_leave
, &data
);
3727 data
.res
= isl_union_map_free(data
.res
);
3728 isl_schedule_node_free(node
);
3730 isl_union_map_list_free(data
.expansions
);
3735 /* Internal data structure for isl_schedule_node_get_subtree_contraction.
3736 * "contractions" contains a list of accumulated contractions
3737 * for each outer expansion, set or sequence node. The first element
3738 * in the list is an identity mapping on the reaching domain elements.
3739 * "res" collects the results.
3741 struct isl_subtree_contraction_data
{
3742 isl_union_pw_multi_aff_list
*contractions
;
3743 isl_union_pw_multi_aff
*res
;
3746 /* Callback for "traverse" to enter a node and to move
3747 * to the deepest initial subtree that should be traversed
3748 * by isl_schedule_node_get_subtree_contraction.
3750 * Whenever we come across an expansion node, the last element
3751 * of data->contractions is combined with the contraction
3752 * on the expansion node.
3754 * Whenever we come across a filter node that is the child
3755 * of a set or sequence node, data->contractions is extended
3756 * with a new element that restricts the previous element
3757 * to the elements selected by the filter.
3758 * The previous element can then be reused while backtracking.
3760 static __isl_give isl_schedule_node
*subtree_contraction_enter(
3761 __isl_take isl_schedule_node
*node
, void *user
)
3763 struct isl_subtree_contraction_data
*data
= user
;
3766 enum isl_schedule_node_type type
;
3767 isl_union_set
*filter
;
3768 isl_union_pw_multi_aff
*inner
, *contraction
;
3771 switch (isl_schedule_node_get_type(node
)) {
3772 case isl_schedule_node_error
:
3773 return isl_schedule_node_free(node
);
3774 case isl_schedule_node_filter
:
3775 type
= isl_schedule_node_get_parent_type(node
);
3776 if (type
!= isl_schedule_node_set
&&
3777 type
!= isl_schedule_node_sequence
)
3779 filter
= isl_schedule_node_filter_get_filter(node
);
3780 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3781 data
->contractions
);
3783 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3784 data
->contractions
, n
- 1);
3785 inner
= isl_union_pw_multi_aff_intersect_domain(inner
,
3787 data
->contractions
=
3788 isl_union_pw_multi_aff_list_add(data
->contractions
,
3791 case isl_schedule_node_expansion
:
3792 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3793 data
->contractions
);
3795 isl_schedule_node_expansion_get_contraction(node
);
3797 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3798 data
->contractions
, n
- 1);
3800 isl_union_pw_multi_aff_pullback_union_pw_multi_aff(
3801 inner
, contraction
);
3802 data
->contractions
=
3803 isl_union_pw_multi_aff_list_set_union_pw_multi_aff(
3804 data
->contractions
, n
- 1, inner
);
3806 case isl_schedule_node_band
:
3807 case isl_schedule_node_context
:
3808 case isl_schedule_node_domain
:
3809 case isl_schedule_node_extension
:
3810 case isl_schedule_node_guard
:
3811 case isl_schedule_node_leaf
:
3812 case isl_schedule_node_mark
:
3813 case isl_schedule_node_sequence
:
3814 case isl_schedule_node_set
:
3817 } while (isl_schedule_node_has_children(node
) &&
3818 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3823 /* Callback for "traverse" to leave a node for
3824 * isl_schedule_node_get_subtree_contraction.
3826 * If we come across a filter node that is the child
3827 * of a set or sequence node, then we remove the element
3828 * of data->contractions that was added in subtree_contraction_enter.
3830 * If we reach a leaf node, then the accumulated contraction is
3831 * added to data->res.
3833 static __isl_give isl_schedule_node
*subtree_contraction_leave(
3834 __isl_take isl_schedule_node
*node
, void *user
)
3836 struct isl_subtree_contraction_data
*data
= user
;
3838 isl_union_pw_multi_aff
*inner
;
3839 enum isl_schedule_node_type type
;
3841 switch (isl_schedule_node_get_type(node
)) {
3842 case isl_schedule_node_error
:
3843 return isl_schedule_node_free(node
);
3844 case isl_schedule_node_filter
:
3845 type
= isl_schedule_node_get_parent_type(node
);
3846 if (type
!= isl_schedule_node_set
&&
3847 type
!= isl_schedule_node_sequence
)
3849 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3850 data
->contractions
);
3851 data
->contractions
=
3852 isl_union_pw_multi_aff_list_drop(data
->contractions
,
3855 case isl_schedule_node_leaf
:
3856 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3857 data
->contractions
);
3858 inner
= isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3859 data
->contractions
, n
- 1);
3860 data
->res
= isl_union_pw_multi_aff_union_add(data
->res
, inner
);
3862 case isl_schedule_node_band
:
3863 case isl_schedule_node_context
:
3864 case isl_schedule_node_domain
:
3865 case isl_schedule_node_expansion
:
3866 case isl_schedule_node_extension
:
3867 case isl_schedule_node_guard
:
3868 case isl_schedule_node_mark
:
3869 case isl_schedule_node_sequence
:
3870 case isl_schedule_node_set
:
3877 /* Return a mapping from the domain elements in the leaves of the subtree
3878 * rooted at "node" to the corresponding domain elements that reach "node"
3879 * obtained by composing the intermediate contractions.
3881 * We start out with an identity mapping between the domain elements
3882 * that reach "node" and compose it with all the contractions
3883 * on a path from "node" to a leaf while traversing the subtree.
3884 * Within the children of an a sequence or set node, the
3885 * accumulated contraction is restricted to the elements selected
3886 * by the filter child.
3888 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_get_subtree_contraction(
3889 __isl_keep isl_schedule_node
*node
)
3891 struct isl_subtree_contraction_data data
;
3893 isl_union_set
*domain
;
3894 isl_union_pw_multi_aff
*contraction
;
3899 domain
= isl_schedule_node_get_universe_domain(node
);
3900 space
= isl_union_set_get_space(domain
);
3901 contraction
= isl_union_set_identity_union_pw_multi_aff(domain
);
3902 data
.res
= isl_union_pw_multi_aff_empty(space
);
3904 isl_union_pw_multi_aff_list_from_union_pw_multi_aff(contraction
);
3906 node
= isl_schedule_node_copy(node
);
3907 node
= traverse(node
, &subtree_contraction_enter
,
3908 &subtree_contraction_leave
, &data
);
3910 data
.res
= isl_union_pw_multi_aff_free(data
.res
);
3911 isl_schedule_node_free(node
);
3913 isl_union_pw_multi_aff_list_free(data
.contractions
);
3918 /* Do the nearest "n" ancestors of "node" have the types given in "types"
3919 * (starting at the parent of "node")?
3921 static int has_ancestors(__isl_keep isl_schedule_node
*node
,
3922 int n
, enum isl_schedule_node_type
*types
)
3929 n_ancestor
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
3933 for (i
= 0; i
< n
; ++i
) {
3934 isl_schedule_tree
*tree
;
3937 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
3938 n_ancestor
- 1 - i
);
3941 correct_type
= isl_schedule_tree_get_type(tree
) == types
[i
];
3942 isl_schedule_tree_free(tree
);
3950 /* Given a node "node" that appears in an extension (i.e., it is the child
3951 * of a filter in a sequence inside an extension node), are the spaces
3952 * of the extension specified by "extension" disjoint from those
3953 * of both the original extension and the domain elements that reach
3954 * that original extension?
3956 static int is_disjoint_extension(__isl_keep isl_schedule_node
*node
,
3957 __isl_keep isl_union_map
*extension
)
3960 isl_union_set
*domain
;
3963 node
= isl_schedule_node_copy(node
);
3964 node
= isl_schedule_node_parent(node
);
3965 node
= isl_schedule_node_parent(node
);
3966 node
= isl_schedule_node_parent(node
);
3967 old
= isl_schedule_node_extension_get_extension(node
);
3968 domain
= isl_schedule_node_get_universe_domain(node
);
3969 isl_schedule_node_free(node
);
3970 old
= isl_union_map_universe(old
);
3971 domain
= isl_union_set_union(domain
, isl_union_map_range(old
));
3972 extension
= isl_union_map_copy(extension
);
3973 extension
= isl_union_map_intersect_range(extension
, domain
);
3974 empty
= isl_union_map_is_empty(extension
);
3975 isl_union_map_free(extension
);
3980 /* Given a node "node" that is governed by an extension node, extend
3981 * that extension node with "extension".
3983 * In particular, "node" is the child of a filter in a sequence that
3984 * is in turn a child of an extension node. Extend that extension node
3987 * Return a pointer to the parent of the original node (i.e., a filter).
3989 static __isl_give isl_schedule_node
*extend_extension(
3990 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
3994 isl_union_map
*node_extension
;
3996 node
= isl_schedule_node_parent(node
);
3997 pos
= isl_schedule_node_get_child_position(node
);
3998 node
= isl_schedule_node_parent(node
);
3999 node
= isl_schedule_node_parent(node
);
4000 node_extension
= isl_schedule_node_extension_get_extension(node
);
4001 disjoint
= isl_union_map_is_disjoint(extension
, node_extension
);
4002 extension
= isl_union_map_union(extension
, node_extension
);
4003 node
= isl_schedule_node_extension_set_extension(node
, extension
);
4004 node
= isl_schedule_node_child(node
, 0);
4005 node
= isl_schedule_node_child(node
, pos
);
4008 return isl_schedule_node_free(node
);
4012 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4013 "extension domain should be disjoint from earlier "
4014 "extensions", return isl_schedule_node_free(node
));
4019 /* Return the universe of "uset" if this universe is disjoint from "ref".
4020 * Otherwise, return "uset".
4022 * Also check if "uset" itself is disjoint from "ref", reporting
4023 * an error if it is not.
4025 static __isl_give isl_union_set
*replace_by_universe_if_disjoint(
4026 __isl_take isl_union_set
*uset
, __isl_keep isl_union_set
*ref
)
4029 isl_union_set
*universe
;
4031 disjoint
= isl_union_set_is_disjoint(uset
, ref
);
4033 return isl_union_set_free(uset
);
4035 isl_die(isl_union_set_get_ctx(uset
), isl_error_invalid
,
4036 "extension domain should be disjoint from "
4037 "current domain", return isl_union_set_free(uset
));
4039 universe
= isl_union_set_universe(isl_union_set_copy(uset
));
4040 disjoint
= isl_union_set_is_disjoint(universe
, ref
);
4041 if (disjoint
>= 0 && disjoint
) {
4042 isl_union_set_free(uset
);
4045 isl_union_set_free(universe
);
4048 return isl_union_set_free(uset
);
4052 /* Insert an extension node on top of "node" with extension "extension".
4053 * In addition, insert a filter that separates node from the extension
4054 * between the extension node and "node".
4055 * Return a pointer to the inserted filter node.
4057 * If "node" already appears in an extension (i.e., if it is the child
4058 * of a filter in a sequence inside an extension node), then extend that
4059 * extension with "extension" instead.
4060 * In this case, a pointer to the original filter node is returned.
4061 * Note that if some of the elements in the new extension live in the
4062 * same space as those of the original extension or the domain elements
4063 * reaching the original extension, then we insert a new extension anyway.
4064 * Otherwise, we would have to adjust the filters in the sequence child
4065 * of the extension to ensure that the elements in the new extension
4068 static __isl_give isl_schedule_node
*insert_extension(
4069 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
4071 enum isl_schedule_node_type ancestors
[] =
4072 { isl_schedule_node_filter
, isl_schedule_node_sequence
,
4073 isl_schedule_node_extension
};
4074 isl_union_set
*domain
;
4075 isl_union_set
*filter
;
4078 in_ext
= has_ancestors(node
, 3, ancestors
);
4084 disjoint
= is_disjoint_extension(node
, extension
);
4088 return extend_extension(node
, extension
);
4091 filter
= isl_schedule_node_get_domain(node
);
4092 domain
= isl_union_map_range(isl_union_map_copy(extension
));
4093 filter
= replace_by_universe_if_disjoint(filter
, domain
);
4094 isl_union_set_free(domain
);
4096 node
= isl_schedule_node_insert_filter(node
, filter
);
4097 node
= isl_schedule_node_insert_extension(node
, extension
);
4098 node
= isl_schedule_node_child(node
, 0);
4101 isl_schedule_node_free(node
);
4102 isl_union_map_free(extension
);
4106 /* Replace the subtree that "node" points to by "tree" (which has
4107 * a sequence root with two children), except if the parent of "node"
4108 * is a sequence as well, in which case "tree" is spliced at the position
4109 * of "node" in its parent.
4110 * Return a pointer to the child of the "tree_pos" (filter) child of "tree"
4111 * in the updated schedule tree.
4113 static __isl_give isl_schedule_node
*graft_or_splice(
4114 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_tree
*tree
,
4119 if (isl_schedule_node_get_parent_type(node
) ==
4120 isl_schedule_node_sequence
) {
4121 pos
= isl_schedule_node_get_child_position(node
);
4122 node
= isl_schedule_node_parent(node
);
4123 node
= isl_schedule_node_sequence_splice(node
, pos
, tree
);
4126 node
= isl_schedule_node_graft_tree(node
, tree
);
4128 node
= isl_schedule_node_child(node
, pos
+ tree_pos
);
4129 node
= isl_schedule_node_child(node
, 0);
4134 /* Insert a node "graft" into the schedule tree of "node" such that it
4135 * is executed before (if "before" is set) or after (if "before" is not set)
4136 * the node that "node" points to.
4137 * The root of "graft" is an extension node.
4138 * Return a pointer to the node that "node" pointed to.
4140 * We first insert an extension node on top of "node" (or extend
4141 * the extension node if there already is one), with a filter on "node"
4142 * separating it from the extension.
4143 * We then insert a filter in the graft to separate it from the original
4144 * domain elements and combine the original and new tree in a sequence.
4145 * If we have extended an extension node, then the children of this
4146 * sequence are spliced in the sequence of the extended extension
4147 * at the position where "node" appears in the original extension.
4148 * Otherwise, the sequence pair is attached to the new extension node.
4150 static __isl_give isl_schedule_node
*graft_extension(
4151 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
,
4154 isl_union_map
*extension
;
4155 isl_union_set
*graft_domain
;
4156 isl_union_set
*node_domain
;
4157 isl_schedule_tree
*tree
, *tree_graft
;
4159 extension
= isl_schedule_node_extension_get_extension(graft
);
4160 graft_domain
= isl_union_map_range(isl_union_map_copy(extension
));
4161 node_domain
= isl_schedule_node_get_universe_domain(node
);
4162 node
= insert_extension(node
, extension
);
4164 graft_domain
= replace_by_universe_if_disjoint(graft_domain
,
4166 isl_union_set_free(node_domain
);
4168 tree
= isl_schedule_node_get_tree(node
);
4169 if (!isl_schedule_node_has_children(graft
)) {
4170 tree_graft
= isl_schedule_tree_from_filter(graft_domain
);
4172 graft
= isl_schedule_node_child(graft
, 0);
4173 tree_graft
= isl_schedule_node_get_tree(graft
);
4174 tree_graft
= isl_schedule_tree_insert_filter(tree_graft
,
4178 tree
= isl_schedule_tree_sequence_pair(tree_graft
, tree
);
4180 tree
= isl_schedule_tree_sequence_pair(tree
, tree_graft
);
4181 node
= graft_or_splice(node
, tree
, before
);
4183 isl_schedule_node_free(graft
);
4188 /* Replace the root domain node of "node" by an extension node suitable
4189 * for insertion at "pos".
4190 * That is, create an extension node that maps the outer band nodes
4191 * at "pos" to the domain of the root node of "node" and attach
4192 * the child of this root node to the extension node.
4194 static __isl_give isl_schedule_node
*extension_from_domain(
4195 __isl_take isl_schedule_node
*node
, __isl_keep isl_schedule_node
*pos
)
4197 isl_union_set
*universe
;
4198 isl_union_set
*domain
;
4203 isl_schedule_node
*res
;
4204 isl_schedule_tree
*tree
;
4206 anchored
= isl_schedule_node_is_subtree_anchored(node
);
4208 return isl_schedule_node_free(node
);
4210 isl_die(isl_schedule_node_get_ctx(node
), isl_error_unsupported
,
4211 "cannot graft anchored tree with domain root",
4212 return isl_schedule_node_free(node
));
4214 depth
= isl_schedule_node_get_schedule_depth(pos
);
4215 domain
= isl_schedule_node_domain_get_domain(node
);
4216 space
= isl_union_set_get_space(domain
);
4217 space
= isl_space_set_from_params(space
);
4218 space
= isl_space_add_dims(space
, isl_dim_set
, depth
);
4219 universe
= isl_union_set_from_set(isl_set_universe(space
));
4220 ext
= isl_union_map_from_domain_and_range(universe
, domain
);
4221 res
= isl_schedule_node_from_extension(ext
);
4222 node
= isl_schedule_node_child(node
, 0);
4224 return isl_schedule_node_free(res
);
4225 if (!isl_schedule_tree_is_leaf(node
->tree
)) {
4226 tree
= isl_schedule_node_get_tree(node
);
4227 res
= isl_schedule_node_child(res
, 0);
4228 res
= isl_schedule_node_graft_tree(res
, tree
);
4229 res
= isl_schedule_node_parent(res
);
4231 isl_schedule_node_free(node
);
4236 /* Insert a node "graft" into the schedule tree of "node" such that it
4237 * is executed before (if "before" is set) or after (if "before" is not set)
4238 * the node that "node" points to.
4239 * The root of "graft" may be either a domain or an extension node.
4240 * In the latter case, the domain of the extension needs to correspond
4241 * to the outer band nodes of "node".
4242 * The elements of the domain or the range of the extension may not
4243 * intersect with the domain elements that reach "node".
4244 * The schedule tree of "graft" may not be anchored.
4246 * The schedule tree of "node" is modified to include an extension node
4247 * corresponding to the root node of "graft" as a child of the original
4248 * parent of "node". The original node that "node" points to and the
4249 * child of the root node of "graft" are attached to this extension node
4250 * through a sequence, with appropriate filters and with the child
4251 * of "graft" appearing before or after the original "node".
4253 * If "node" already appears inside a sequence that is the child of
4254 * an extension node and if the spaces of the new domain elements
4255 * do not overlap with those of the original domain elements,
4256 * then that extension node is extended with the new extension
4257 * rather than introducing a new segment of extension and sequence nodes.
4259 * Return a pointer to the same node in the modified tree that
4260 * "node" pointed to in the original tree.
4262 static __isl_give isl_schedule_node
*isl_schedule_node_graft_before_or_after(
4263 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
,
4266 if (!node
|| !graft
)
4268 if (check_insert(node
) < 0)
4271 if (isl_schedule_node_get_type(graft
) == isl_schedule_node_domain
)
4272 graft
= extension_from_domain(graft
, node
);
4274 if (isl_schedule_node_get_type(graft
) != isl_schedule_node_extension
)
4275 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4276 "expecting domain or extension as root of graft",
4279 return graft_extension(node
, graft
, before
);
4281 isl_schedule_node_free(node
);
4282 isl_schedule_node_free(graft
);
4286 /* Insert a node "graft" into the schedule tree of "node" such that it
4287 * is executed before the node that "node" points to.
4288 * The root of "graft" may be either a domain or an extension node.
4289 * In the latter case, the domain of the extension needs to correspond
4290 * to the outer band nodes of "node".
4291 * The elements of the domain or the range of the extension may not
4292 * intersect with the domain elements that reach "node".
4293 * The schedule tree of "graft" may not be anchored.
4295 * Return a pointer to the same node in the modified tree that
4296 * "node" pointed to in the original tree.
4298 __isl_give isl_schedule_node
*isl_schedule_node_graft_before(
4299 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
)
4301 return isl_schedule_node_graft_before_or_after(node
, graft
, 1);
4304 /* Insert a node "graft" into the schedule tree of "node" such that it
4305 * is executed after the node that "node" points to.
4306 * The root of "graft" may be either a domain or an extension node.
4307 * In the latter case, the domain of the extension needs to correspond
4308 * to the outer band nodes of "node".
4309 * The elements of the domain or the range of the extension may not
4310 * intersect with the domain elements that reach "node".
4311 * The schedule tree of "graft" may not be anchored.
4313 * Return a pointer to the same node in the modified tree that
4314 * "node" pointed to in the original tree.
4316 __isl_give isl_schedule_node
*isl_schedule_node_graft_after(
4317 __isl_take isl_schedule_node
*node
,
4318 __isl_take isl_schedule_node
*graft
)
4320 return isl_schedule_node_graft_before_or_after(node
, graft
, 0);
4323 /* Split the domain elements that reach "node" into those that satisfy
4324 * "filter" and those that do not. Arrange for the first subset to be
4325 * executed before or after the second subset, depending on the value
4327 * Return a pointer to the tree corresponding to the second subset,
4328 * except when this subset is empty in which case the original pointer
4330 * If both subsets are non-empty, then a sequence node is introduced
4331 * to impose the order. If the grandparent of the original node was
4332 * itself a sequence, then the original child is replaced by two children
4333 * in this sequence instead.
4334 * The children in the sequence are copies of the original subtree,
4335 * simplified with respect to their filters.
4337 static __isl_give isl_schedule_node
*isl_schedule_node_order_before_or_after(
4338 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
,
4341 enum isl_schedule_node_type ancestors
[] =
4342 { isl_schedule_node_filter
, isl_schedule_node_sequence
};
4343 isl_union_set
*node_domain
, *node_filter
= NULL
, *parent_filter
;
4344 isl_schedule_node
*node2
;
4345 isl_schedule_tree
*tree1
, *tree2
;
4349 if (!node
|| !filter
)
4351 if (check_insert(node
) < 0)
4354 in_seq
= has_ancestors(node
, 2, ancestors
);
4357 node_domain
= isl_schedule_node_get_domain(node
);
4358 filter
= isl_union_set_gist(filter
, isl_union_set_copy(node_domain
));
4359 node_filter
= isl_union_set_copy(node_domain
);
4360 node_filter
= isl_union_set_subtract(node_filter
,
4361 isl_union_set_copy(filter
));
4362 node_filter
= isl_union_set_gist(node_filter
, node_domain
);
4363 empty1
= isl_union_set_is_empty(filter
);
4364 empty2
= isl_union_set_is_empty(node_filter
);
4365 if (empty1
< 0 || empty2
< 0)
4367 if (empty1
|| empty2
) {
4368 isl_union_set_free(filter
);
4369 isl_union_set_free(node_filter
);
4374 node
= isl_schedule_node_parent(node
);
4375 parent_filter
= isl_schedule_node_filter_get_filter(node
);
4376 node_filter
= isl_union_set_intersect(node_filter
,
4377 isl_union_set_copy(parent_filter
));
4378 filter
= isl_union_set_intersect(filter
, parent_filter
);
4381 node2
= isl_schedule_node_copy(node
);
4382 node
= isl_schedule_node_gist(node
, isl_union_set_copy(node_filter
));
4383 node2
= isl_schedule_node_gist(node2
, isl_union_set_copy(filter
));
4384 tree1
= isl_schedule_node_get_tree(node
);
4385 tree2
= isl_schedule_node_get_tree(node2
);
4386 tree1
= isl_schedule_tree_insert_filter(tree1
, node_filter
);
4387 tree2
= isl_schedule_tree_insert_filter(tree2
, filter
);
4388 isl_schedule_node_free(node2
);
4391 tree1
= isl_schedule_tree_sequence_pair(tree2
, tree1
);
4392 node
= graft_or_splice(node
, tree1
, 1);
4394 tree1
= isl_schedule_tree_sequence_pair(tree1
, tree2
);
4395 node
= graft_or_splice(node
, tree1
, 0);
4400 isl_schedule_node_free(node
);
4401 isl_union_set_free(filter
);
4402 isl_union_set_free(node_filter
);
4406 /* Split the domain elements that reach "node" into those that satisfy
4407 * "filter" and those that do not. Arrange for the first subset to be
4408 * executed before the second subset.
4409 * Return a pointer to the tree corresponding to the second subset,
4410 * except when this subset is empty in which case the original pointer
4413 __isl_give isl_schedule_node
*isl_schedule_node_order_before(
4414 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
4416 return isl_schedule_node_order_before_or_after(node
, filter
, 1);
4419 /* Split the domain elements that reach "node" into those that satisfy
4420 * "filter" and those that do not. Arrange for the first subset to be
4421 * executed after the second subset.
4422 * Return a pointer to the tree corresponding to the second subset,
4423 * except when this subset is empty in which case the original pointer
4426 __isl_give isl_schedule_node
*isl_schedule_node_order_after(
4427 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
4429 return isl_schedule_node_order_before_or_after(node
, filter
, 0);
4432 /* Reset the user pointer on all identifiers of parameters and tuples
4433 * in the schedule node "node".
4435 __isl_give isl_schedule_node
*isl_schedule_node_reset_user(
4436 __isl_take isl_schedule_node
*node
)
4438 isl_schedule_tree
*tree
;
4440 tree
= isl_schedule_node_get_tree(node
);
4441 tree
= isl_schedule_tree_reset_user(tree
);
4442 node
= isl_schedule_node_graft_tree(node
, tree
);
4447 /* Align the parameters of the schedule node "node" to those of "space".
4449 __isl_give isl_schedule_node
*isl_schedule_node_align_params(
4450 __isl_take isl_schedule_node
*node
, __isl_take isl_space
*space
)
4452 isl_schedule_tree
*tree
;
4454 tree
= isl_schedule_node_get_tree(node
);
4455 tree
= isl_schedule_tree_align_params(tree
, space
);
4456 node
= isl_schedule_node_graft_tree(node
, tree
);
4461 /* Compute the pullback of schedule node "node"
4462 * by the function represented by "upma".
4463 * In other words, plug in "upma" in the iteration domains
4464 * of schedule node "node".
4465 * We currently do not handle expansion nodes.
4467 * Note that this is only a helper function for
4468 * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency,
4469 * this function should not be called on a single node without also
4470 * calling it on all the other nodes.
4472 __isl_give isl_schedule_node
*isl_schedule_node_pullback_union_pw_multi_aff(
4473 __isl_take isl_schedule_node
*node
,
4474 __isl_take isl_union_pw_multi_aff
*upma
)
4476 isl_schedule_tree
*tree
;
4478 tree
= isl_schedule_node_get_tree(node
);
4479 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, upma
);
4480 node
= isl_schedule_node_graft_tree(node
, tree
);
4485 /* Return the position of the subtree containing "node" among the children
4486 * of "ancestor". "node" is assumed to be a descendant of "ancestor".
4487 * In particular, both nodes should point to the same schedule tree.
4489 * Return -1 on error.
4491 int isl_schedule_node_get_ancestor_child_position(
4492 __isl_keep isl_schedule_node
*node
,
4493 __isl_keep isl_schedule_node
*ancestor
)
4496 isl_schedule_tree
*tree
;
4498 if (!node
|| !ancestor
)
4501 if (node
->schedule
!= ancestor
->schedule
)
4502 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4503 "not a descendant", return -1);
4505 n1
= isl_schedule_node_get_tree_depth(ancestor
);
4506 n2
= isl_schedule_node_get_tree_depth(node
);
4509 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4510 "not a descendant", return -1);
4511 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n1
);
4512 isl_schedule_tree_free(tree
);
4513 if (tree
!= ancestor
->tree
)
4514 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4515 "not a descendant", return -1);
4517 return node
->child_pos
[n1
];
4520 /* Given two nodes that point to the same schedule tree, return their
4521 * closest shared ancestor.
4523 * Since the two nodes point to the same schedule, they share at least
4524 * one ancestor, the root of the schedule. We move down from the root
4525 * to the first ancestor where the respective children have a different
4526 * child position. This is the requested ancestor.
4527 * If there is no ancestor where the children have a different position,
4528 * then one node is an ancestor of the other and then this node is
4529 * the requested ancestor.
4531 __isl_give isl_schedule_node
*isl_schedule_node_get_shared_ancestor(
4532 __isl_keep isl_schedule_node
*node1
,
4533 __isl_keep isl_schedule_node
*node2
)
4537 if (!node1
|| !node2
)
4539 if (node1
->schedule
!= node2
->schedule
)
4540 isl_die(isl_schedule_node_get_ctx(node1
), isl_error_invalid
,
4541 "not part of same schedule", return NULL
);
4542 n1
= isl_schedule_node_get_tree_depth(node1
);
4543 n2
= isl_schedule_node_get_tree_depth(node2
);
4545 return isl_schedule_node_get_shared_ancestor(node2
, node1
);
4547 return isl_schedule_node_copy(node1
);
4548 if (isl_schedule_node_is_equal(node1
, node2
))
4549 return isl_schedule_node_copy(node1
);
4551 for (i
= 0; i
< n1
; ++i
)
4552 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
4555 node1
= isl_schedule_node_copy(node1
);
4556 return isl_schedule_node_ancestor(node1
, n1
- i
);
4559 /* Print "node" to "p".
4561 __isl_give isl_printer
*isl_printer_print_schedule_node(
4562 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
4565 return isl_printer_free(p
);
4566 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
,
4567 isl_schedule_tree_list_n_schedule_tree(node
->ancestors
),
4571 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
4574 isl_printer
*printer
;
4579 ctx
= isl_schedule_node_get_ctx(node
);
4580 printer
= isl_printer_to_file(ctx
, stderr
);
4581 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
4582 printer
= isl_printer_print_schedule_node(printer
, node
);
4584 isl_printer_free(printer
);
4587 /* Return a string representation of "node".
4588 * Print the schedule node in block format as it would otherwise
4589 * look identical to the entire schedule.
4591 __isl_give
char *isl_schedule_node_to_str(__isl_keep isl_schedule_node
*node
)
4593 isl_printer
*printer
;
4599 printer
= isl_printer_to_str(isl_schedule_node_get_ctx(node
));
4600 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
4601 printer
= isl_printer_print_schedule_node(printer
, node
);
4602 s
= isl_printer_get_str(printer
);
4603 isl_printer_free(printer
);