2 * Copyright 2013-2014 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
4 * Copyright 2016 Sven Verdoolaege
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege,
9 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
10 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
11 * B.P. 105 - 78153 Le Chesnay, France
16 #include <isl/space.h>
18 #include <isl_schedule_band.h>
19 #include <isl_schedule_private.h>
20 #include <isl_schedule_node_private.h>
22 /* Create a new schedule node in the given schedule, point at the given
23 * tree with given ancestors and child positions.
24 * "child_pos" may be NULL if there are no ancestors.
26 __isl_give isl_schedule_node
*isl_schedule_node_alloc(
27 __isl_take isl_schedule
*schedule
, __isl_take isl_schedule_tree
*tree
,
28 __isl_take isl_schedule_tree_list
*ancestors
, int *child_pos
)
31 isl_schedule_node
*node
;
35 n
= isl_schedule_tree_list_n_schedule_tree(ancestors
);
36 if (!schedule
|| !tree
|| n
< 0)
38 if (n
> 0 && !child_pos
)
40 ctx
= isl_schedule_get_ctx(schedule
);
41 node
= isl_calloc_type(ctx
, isl_schedule_node
);
45 node
->schedule
= schedule
;
47 node
->ancestors
= ancestors
;
48 node
->child_pos
= isl_alloc_array(ctx
, int, n
);
49 if (n
&& !node
->child_pos
)
50 return isl_schedule_node_free(node
);
51 for (i
= 0; i
< n
; ++i
)
52 node
->child_pos
[i
] = child_pos
[i
];
56 isl_schedule_free(schedule
);
57 isl_schedule_tree_free(tree
);
58 isl_schedule_tree_list_free(ancestors
);
62 /* Return a pointer to the root of a schedule tree with as single
63 * node a domain node with the given domain.
65 __isl_give isl_schedule_node
*isl_schedule_node_from_domain(
66 __isl_take isl_union_set
*domain
)
68 isl_schedule
*schedule
;
69 isl_schedule_node
*node
;
71 schedule
= isl_schedule_from_domain(domain
);
72 node
= isl_schedule_get_root(schedule
);
73 isl_schedule_free(schedule
);
78 /* Return a pointer to the root of a schedule tree with as single
79 * node a extension node with the given extension.
81 __isl_give isl_schedule_node
*isl_schedule_node_from_extension(
82 __isl_take isl_union_map
*extension
)
85 isl_schedule
*schedule
;
86 isl_schedule_tree
*tree
;
87 isl_schedule_node
*node
;
92 ctx
= isl_union_map_get_ctx(extension
);
93 tree
= isl_schedule_tree_from_extension(extension
);
94 schedule
= isl_schedule_from_schedule_tree(ctx
, tree
);
95 node
= isl_schedule_get_root(schedule
);
96 isl_schedule_free(schedule
);
101 /* Return the isl_ctx to which "node" belongs.
103 isl_ctx
*isl_schedule_node_get_ctx(__isl_keep isl_schedule_node
*node
)
105 return node
? isl_schedule_get_ctx(node
->schedule
) : NULL
;
108 /* Return a pointer to the leaf of the schedule into which "node" points.
110 __isl_keep isl_schedule_tree
*isl_schedule_node_peek_leaf(
111 __isl_keep isl_schedule_node
*node
)
113 return node
? isl_schedule_peek_leaf(node
->schedule
) : NULL
;
116 /* Return a copy of the leaf of the schedule into which "node" points.
118 __isl_give isl_schedule_tree
*isl_schedule_node_get_leaf(
119 __isl_keep isl_schedule_node
*node
)
121 return isl_schedule_tree_copy(isl_schedule_node_peek_leaf(node
));
124 /* Return the type of the node or isl_schedule_node_error on error.
126 enum isl_schedule_node_type
isl_schedule_node_get_type(
127 __isl_keep isl_schedule_node
*node
)
129 return node
? isl_schedule_tree_get_type(node
->tree
)
130 : isl_schedule_node_error
;
133 /* Return the type of the parent of "node" or isl_schedule_node_error on error.
135 enum isl_schedule_node_type
isl_schedule_node_get_parent_type(
136 __isl_keep isl_schedule_node
*node
)
141 isl_schedule_tree
*parent
;
142 enum isl_schedule_node_type type
;
145 return isl_schedule_node_error
;
146 has_parent
= isl_schedule_node_has_parent(node
);
148 return isl_schedule_node_error
;
150 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
151 "node has no parent", return isl_schedule_node_error
);
152 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
154 return isl_schedule_node_error
;
157 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, pos
);
158 type
= isl_schedule_tree_get_type(parent
);
159 isl_schedule_tree_free(parent
);
164 /* Return a copy of the subtree that this node points to.
166 __isl_give isl_schedule_tree
*isl_schedule_node_get_tree(
167 __isl_keep isl_schedule_node
*node
)
172 return isl_schedule_tree_copy(node
->tree
);
175 /* Return a copy of the schedule into which "node" points.
177 __isl_give isl_schedule
*isl_schedule_node_get_schedule(
178 __isl_keep isl_schedule_node
*node
)
182 return isl_schedule_copy(node
->schedule
);
185 /* Return a fresh copy of "node".
187 __isl_take isl_schedule_node
*isl_schedule_node_dup(
188 __isl_keep isl_schedule_node
*node
)
193 return isl_schedule_node_alloc(isl_schedule_copy(node
->schedule
),
194 isl_schedule_tree_copy(node
->tree
),
195 isl_schedule_tree_list_copy(node
->ancestors
),
199 /* Return an isl_schedule_node that is equal to "node" and that has only
200 * a single reference.
202 __isl_give isl_schedule_node
*isl_schedule_node_cow(
203 __isl_take isl_schedule_node
*node
)
211 return isl_schedule_node_dup(node
);
214 /* Return a new reference to "node".
216 __isl_give isl_schedule_node
*isl_schedule_node_copy(
217 __isl_keep isl_schedule_node
*node
)
226 /* Free "node" and return NULL.
228 __isl_null isl_schedule_node
*isl_schedule_node_free(
229 __isl_take isl_schedule_node
*node
)
236 isl_schedule_tree_list_free(node
->ancestors
);
237 free(node
->child_pos
);
238 isl_schedule_tree_free(node
->tree
);
239 isl_schedule_free(node
->schedule
);
245 /* Do "node1" and "node2" point to the same position in the same
248 isl_bool
isl_schedule_node_is_equal(__isl_keep isl_schedule_node
*node1
,
249 __isl_keep isl_schedule_node
*node2
)
253 if (!node1
|| !node2
)
254 return isl_bool_error
;
256 return isl_bool_true
;
257 if (node1
->schedule
!= node2
->schedule
)
258 return isl_bool_false
;
260 n1
= isl_schedule_node_get_tree_depth(node1
);
261 n2
= isl_schedule_node_get_tree_depth(node2
);
263 return isl_bool_false
;
264 for (i
= 0; i
< n1
; ++i
)
265 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
266 return isl_bool_false
;
268 return isl_bool_true
;
271 /* Return the number of outer schedule dimensions of "node"
272 * in its schedule tree.
274 * Return -1 on error.
276 int isl_schedule_node_get_schedule_depth(__isl_keep isl_schedule_node
*node
)
285 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
288 for (i
= n
- 1; i
>= 0; --i
) {
289 isl_schedule_tree
*tree
;
291 tree
= isl_schedule_tree_list_get_schedule_tree(
295 if (tree
->type
== isl_schedule_node_band
)
296 depth
+= isl_schedule_tree_band_n_member(tree
);
297 isl_schedule_tree_free(tree
);
303 /* Internal data structure for
304 * isl_schedule_node_get_prefix_schedule_union_pw_multi_aff
306 * "initialized" is set if the filter field has been initialized.
307 * If "universe_domain" is not set, then the collected filter is intersected
308 * with the domain of the root domain node.
309 * "universe_filter" is set if we are only collecting the universes of filters
310 * "collect_prefix" is set if we are collecting prefixes.
311 * "filter" collects all outer filters and is NULL until "initialized" is set.
312 * "prefix" collects all outer band partial schedules (if "collect_prefix"
313 * is set). If it is used, then it is initialized by the caller
314 * of collect_filter_prefix to a zero-dimensional function.
316 struct isl_schedule_node_get_filter_prefix_data
{
321 isl_union_set
*filter
;
322 isl_multi_union_pw_aff
*prefix
;
325 static isl_stat
collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
326 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
);
328 /* Update the filter and prefix information in "data" based on the first "n"
329 * elements in "list" and the expansion tree root "tree".
331 * We first collect the information from the elements in "list",
332 * initializing the filter based on the domain of the expansion.
333 * Then we map the results to the expanded space and combined them
334 * with the results already in "data".
336 static isl_stat
collect_filter_prefix_expansion(
337 __isl_take isl_schedule_tree
*tree
,
338 __isl_keep isl_schedule_tree_list
*list
, int n
,
339 struct isl_schedule_node_get_filter_prefix_data
*data
)
341 struct isl_schedule_node_get_filter_prefix_data contracted
;
342 isl_union_pw_multi_aff
*c
;
343 isl_union_map
*exp
, *universe
;
344 isl_union_set
*filter
;
346 c
= isl_schedule_tree_expansion_get_contraction(tree
);
347 exp
= isl_schedule_tree_expansion_get_expansion(tree
);
349 contracted
.initialized
= 1;
350 contracted
.universe_domain
= data
->universe_domain
;
351 contracted
.universe_filter
= data
->universe_filter
;
352 contracted
.collect_prefix
= data
->collect_prefix
;
353 universe
= isl_union_map_universe(isl_union_map_copy(exp
));
354 filter
= isl_union_map_domain(universe
);
355 if (data
->collect_prefix
) {
356 isl_space
*space
= isl_union_set_get_space(filter
);
357 space
= isl_space_set_from_params(space
);
358 contracted
.prefix
= isl_multi_union_pw_aff_zero(space
);
360 contracted
.filter
= filter
;
362 if (collect_filter_prefix(list
, n
, &contracted
) < 0)
363 contracted
.filter
= isl_union_set_free(contracted
.filter
);
364 if (data
->collect_prefix
) {
365 isl_multi_union_pw_aff
*prefix
;
367 prefix
= contracted
.prefix
;
369 isl_multi_union_pw_aff_pullback_union_pw_multi_aff(prefix
,
370 isl_union_pw_multi_aff_copy(c
));
371 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(
372 prefix
, data
->prefix
);
374 filter
= contracted
.filter
;
375 if (data
->universe_domain
)
376 filter
= isl_union_set_preimage_union_pw_multi_aff(filter
,
377 isl_union_pw_multi_aff_copy(c
));
379 filter
= isl_union_set_apply(filter
, isl_union_map_copy(exp
));
380 if (!data
->initialized
)
381 data
->filter
= filter
;
383 data
->filter
= isl_union_set_intersect(filter
, data
->filter
);
384 data
->initialized
= 1;
386 isl_union_pw_multi_aff_free(c
);
387 isl_union_map_free(exp
);
388 isl_schedule_tree_free(tree
);
393 /* Update the filter information in "data" based on the first "n"
394 * elements in "list" and the extension tree root "tree", in case
395 * data->universe_domain is set and data->collect_prefix is not.
397 * We collect the universe domain of the elements in "list" and
398 * add it to the universe range of the extension (intersected
399 * with the already collected filter, if any).
401 static isl_stat
collect_universe_domain_extension(
402 __isl_take isl_schedule_tree
*tree
,
403 __isl_keep isl_schedule_tree_list
*list
, int n
,
404 struct isl_schedule_node_get_filter_prefix_data
*data
)
406 struct isl_schedule_node_get_filter_prefix_data data_outer
;
407 isl_union_map
*extension
;
408 isl_union_set
*filter
;
410 data_outer
.initialized
= 0;
411 data_outer
.universe_domain
= 1;
412 data_outer
.universe_filter
= data
->universe_filter
;
413 data_outer
.collect_prefix
= 0;
414 data_outer
.filter
= NULL
;
415 data_outer
.prefix
= NULL
;
417 if (collect_filter_prefix(list
, n
, &data_outer
) < 0)
418 data_outer
.filter
= isl_union_set_free(data_outer
.filter
);
420 extension
= isl_schedule_tree_extension_get_extension(tree
);
421 extension
= isl_union_map_universe(extension
);
422 filter
= isl_union_map_range(extension
);
423 if (data_outer
.initialized
)
424 filter
= isl_union_set_union(filter
, data_outer
.filter
);
425 if (data
->initialized
)
426 filter
= isl_union_set_intersect(filter
, data
->filter
);
428 data
->filter
= filter
;
430 isl_schedule_tree_free(tree
);
435 /* Update "data" based on the tree node "tree" in case "data" has
436 * not been initialized yet.
438 * Return 0 on success and -1 on error.
440 * If "tree" is a filter, then we set data->filter to this filter
442 * If "tree" is a domain, then this means we have reached the root
443 * of the schedule tree without being able to extract any information.
444 * We therefore initialize data->filter to the universe of the domain,
445 * or the domain itself if data->universe_domain is not set.
446 * If "tree" is a band with at least one member, then we set data->filter
447 * to the universe of the schedule domain and replace the zero-dimensional
448 * data->prefix by the band schedule (if data->collect_prefix is set).
450 static isl_stat
collect_filter_prefix_init(__isl_keep isl_schedule_tree
*tree
,
451 struct isl_schedule_node_get_filter_prefix_data
*data
)
453 enum isl_schedule_node_type type
;
454 isl_multi_union_pw_aff
*mupa
;
455 isl_union_set
*filter
;
457 type
= isl_schedule_tree_get_type(tree
);
459 case isl_schedule_node_error
:
460 return isl_stat_error
;
461 case isl_schedule_node_expansion
:
462 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
463 "should be handled by caller", return isl_stat_error
);
464 case isl_schedule_node_extension
:
465 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
466 "cannot handle extension nodes", return isl_stat_error
);
467 case isl_schedule_node_context
:
468 case isl_schedule_node_leaf
:
469 case isl_schedule_node_guard
:
470 case isl_schedule_node_mark
:
471 case isl_schedule_node_sequence
:
472 case isl_schedule_node_set
:
474 case isl_schedule_node_domain
:
475 filter
= isl_schedule_tree_domain_get_domain(tree
);
476 if (data
->universe_domain
)
477 filter
= isl_union_set_universe(filter
);
478 data
->filter
= filter
;
480 case isl_schedule_node_band
:
481 if (isl_schedule_tree_band_n_member(tree
) == 0)
483 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
484 if (data
->collect_prefix
) {
485 isl_multi_union_pw_aff_free(data
->prefix
);
486 mupa
= isl_multi_union_pw_aff_reset_tuple_id(mupa
,
488 data
->prefix
= isl_multi_union_pw_aff_copy(mupa
);
490 filter
= isl_multi_union_pw_aff_domain(mupa
);
491 filter
= isl_union_set_universe(filter
);
492 data
->filter
= filter
;
494 case isl_schedule_node_filter
:
495 filter
= isl_schedule_tree_filter_get_filter(tree
);
496 if (data
->universe_filter
)
497 filter
= isl_union_set_universe(filter
);
498 data
->filter
= filter
;
502 if ((data
->collect_prefix
&& !data
->prefix
) || !data
->filter
)
503 return isl_stat_error
;
505 data
->initialized
= 1;
510 /* Update "data" based on the tree node "tree" in case "data" has
511 * already been initialized.
513 * Return 0 on success and -1 on error.
515 * If "tree" is a domain and data->universe_domain is not set, then
516 * intersect data->filter with the domain.
517 * If "tree" is a filter, then we intersect data->filter with this filter
519 * If "tree" is a band with at least one member and data->collect_prefix
520 * is set, then we extend data->prefix with the band schedule.
521 * If "tree" is an extension, then we make sure that we are not collecting
522 * information on any extended domain elements.
524 static isl_stat
collect_filter_prefix_update(__isl_keep isl_schedule_tree
*tree
,
525 struct isl_schedule_node_get_filter_prefix_data
*data
)
527 enum isl_schedule_node_type type
;
528 isl_multi_union_pw_aff
*mupa
;
529 isl_union_set
*filter
;
530 isl_union_map
*extension
;
533 type
= isl_schedule_tree_get_type(tree
);
535 case isl_schedule_node_error
:
536 return isl_stat_error
;
537 case isl_schedule_node_expansion
:
538 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
539 "should be handled by caller", return isl_stat_error
);
540 case isl_schedule_node_extension
:
541 extension
= isl_schedule_tree_extension_get_extension(tree
);
542 extension
= isl_union_map_intersect_range(extension
,
543 isl_union_set_copy(data
->filter
));
544 empty
= isl_union_map_is_empty(extension
);
545 isl_union_map_free(extension
);
547 return isl_stat_error
;
550 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
551 "cannot handle extension nodes", return isl_stat_error
);
552 case isl_schedule_node_context
:
553 case isl_schedule_node_leaf
:
554 case isl_schedule_node_guard
:
555 case isl_schedule_node_mark
:
556 case isl_schedule_node_sequence
:
557 case isl_schedule_node_set
:
559 case isl_schedule_node_domain
:
560 if (data
->universe_domain
)
562 filter
= isl_schedule_tree_domain_get_domain(tree
);
563 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
565 case isl_schedule_node_band
:
566 if (isl_schedule_tree_band_n_member(tree
) == 0)
568 if (!data
->collect_prefix
)
570 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
571 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(mupa
,
574 return isl_stat_error
;
576 case isl_schedule_node_filter
:
577 filter
= isl_schedule_tree_filter_get_filter(tree
);
578 if (data
->universe_filter
)
579 filter
= isl_union_set_universe(filter
);
580 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
582 return isl_stat_error
;
589 /* Collect filter and/or prefix information from the first "n"
590 * elements in "list" (which represent the ancestors of a node).
591 * Store the results in "data".
593 * Extension nodes are only supported if they do not affect the outcome,
594 * i.e., if we are collecting information on non-extended domain elements,
595 * or if we are collecting the universe domain (without prefix).
597 * Return 0 on success and -1 on error.
599 * We traverse the list from innermost ancestor (last element)
600 * to outermost ancestor (first element), calling collect_filter_prefix_init
601 * on each node as long as we have not been able to extract any information
602 * yet and collect_filter_prefix_update afterwards.
603 * If we come across an expansion node, then we interrupt the traversal
604 * and call collect_filter_prefix_expansion to restart the traversal
605 * over the remaining ancestors and to combine the results with those
606 * that have already been collected.
607 * If we come across an extension node and we are only computing
608 * the universe domain, then we interrupt the traversal and call
609 * collect_universe_domain_extension to restart the traversal
610 * over the remaining ancestors and to combine the results with those
611 * that have already been collected.
612 * On successful return, data->initialized will be set since the outermost
613 * ancestor is a domain node, which always results in an initialization.
615 static isl_stat
collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
616 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
)
621 return isl_stat_error
;
623 for (i
= n
- 1; i
>= 0; --i
) {
624 isl_schedule_tree
*tree
;
625 enum isl_schedule_node_type type
;
628 tree
= isl_schedule_tree_list_get_schedule_tree(list
, i
);
630 return isl_stat_error
;
631 type
= isl_schedule_tree_get_type(tree
);
632 if (type
== isl_schedule_node_expansion
)
633 return collect_filter_prefix_expansion(tree
, list
, i
,
635 if (type
== isl_schedule_node_extension
&&
636 data
->universe_domain
&& !data
->collect_prefix
)
637 return collect_universe_domain_extension(tree
, list
, i
,
639 if (!data
->initialized
)
640 r
= collect_filter_prefix_init(tree
, data
);
642 r
= collect_filter_prefix_update(tree
, data
);
643 isl_schedule_tree_free(tree
);
645 return isl_stat_error
;
651 /* Return the concatenation of the partial schedules of all outer band
652 * nodes of "node" interesected with all outer filters
653 * as an isl_multi_union_pw_aff.
654 * None of the ancestors of "node" may be an extension node, unless
655 * there is also a filter ancestor that filters out all the extended
658 * If "node" is pointing at the root of the schedule tree, then
659 * there are no domain elements reaching the current node, so
660 * we return an empty result.
662 * We collect all the filters and partial schedules in collect_filter_prefix
663 * and intersect the domain of the combined schedule with the combined filter.
665 __isl_give isl_multi_union_pw_aff
*
666 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(
667 __isl_keep isl_schedule_node
*node
)
671 struct isl_schedule_node_get_filter_prefix_data data
;
676 space
= isl_schedule_get_space(node
->schedule
);
677 space
= isl_space_set_from_params(space
);
678 if (node
->tree
== node
->schedule
->root
)
679 return isl_multi_union_pw_aff_zero(space
);
681 data
.initialized
= 0;
682 data
.universe_domain
= 1;
683 data
.universe_filter
= 0;
684 data
.collect_prefix
= 1;
686 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
688 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
689 if (n
< 0 || collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
690 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
692 data
.prefix
= isl_multi_union_pw_aff_intersect_domain(data
.prefix
,
698 /* Return the concatenation of the partial schedules of all outer band
699 * nodes of "node" interesected with all outer filters
700 * as an isl_union_pw_multi_aff.
701 * None of the ancestors of "node" may be an extension node, unless
702 * there is also a filter ancestor that filters out all the extended
705 * If "node" is pointing at the root of the schedule tree, then
706 * there are no domain elements reaching the current node, so
707 * we return an empty result.
709 * We collect all the filters and partial schedules in collect_filter_prefix.
710 * The partial schedules are collected as an isl_multi_union_pw_aff.
711 * If this isl_multi_union_pw_aff is zero-dimensional, then it does not
712 * contain any domain information, so we construct the isl_union_pw_multi_aff
713 * result as a zero-dimensional function on the collected filter.
714 * Otherwise, we convert the isl_multi_union_pw_aff to
715 * an isl_multi_union_pw_aff and intersect the domain with the filter.
717 __isl_give isl_union_pw_multi_aff
*
718 isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(
719 __isl_keep isl_schedule_node
*node
)
723 isl_union_pw_multi_aff
*prefix
;
724 struct isl_schedule_node_get_filter_prefix_data data
;
729 space
= isl_schedule_get_space(node
->schedule
);
730 if (node
->tree
== node
->schedule
->root
)
731 return isl_union_pw_multi_aff_empty(space
);
733 space
= isl_space_set_from_params(space
);
734 data
.initialized
= 0;
735 data
.universe_domain
= 1;
736 data
.universe_filter
= 0;
737 data
.collect_prefix
= 1;
739 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
741 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
742 if (n
< 0 || collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
743 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
745 dim
= isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
);
747 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
748 if (data
.prefix
&& dim
== 0) {
749 isl_multi_union_pw_aff_free(data
.prefix
);
750 prefix
= isl_union_pw_multi_aff_from_domain(data
.filter
);
753 isl_union_pw_multi_aff_from_multi_union_pw_aff(data
.prefix
);
754 prefix
= isl_union_pw_multi_aff_intersect_domain(prefix
,
761 /* Return the concatenation of the partial schedules of all outer band
762 * nodes of "node" interesected with all outer filters
763 * as an isl_union_map.
765 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_union_map(
766 __isl_keep isl_schedule_node
*node
)
768 isl_union_pw_multi_aff
*upma
;
770 upma
= isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(node
);
771 return isl_union_map_from_union_pw_multi_aff(upma
);
774 /* Return the concatenation of the partial schedules of all outer band
775 * nodes of "node" intersected with all outer domain constraints.
776 * None of the ancestors of "node" may be an extension node, unless
777 * there is also a filter ancestor that filters out all the extended
780 * Essentially, this function intersects the domain of the output
781 * of isl_schedule_node_get_prefix_schedule_union_map with the output
782 * of isl_schedule_node_get_domain, except that it only traverses
783 * the ancestors of "node" once.
785 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_relation(
786 __isl_keep isl_schedule_node
*node
)
790 isl_union_map
*prefix
;
791 struct isl_schedule_node_get_filter_prefix_data data
;
796 space
= isl_schedule_get_space(node
->schedule
);
797 if (node
->tree
== node
->schedule
->root
)
798 return isl_union_map_empty(space
);
800 space
= isl_space_set_from_params(space
);
801 data
.initialized
= 0;
802 data
.universe_domain
= 0;
803 data
.universe_filter
= 0;
804 data
.collect_prefix
= 1;
806 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
808 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
809 if (n
< 0 || collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
810 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
812 dim
= isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
);
814 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
815 if (data
.prefix
&& dim
== 0) {
816 isl_multi_union_pw_aff_free(data
.prefix
);
817 prefix
= isl_union_map_from_domain(data
.filter
);
819 prefix
= isl_union_map_from_multi_union_pw_aff(data
.prefix
);
820 prefix
= isl_union_map_intersect_domain(prefix
, data
.filter
);
826 /* Return the domain elements that reach "node".
828 * If "node" is pointing at the root of the schedule tree, then
829 * there are no domain elements reaching the current node, so
830 * we return an empty result.
831 * None of the ancestors of "node" may be an extension node, unless
832 * there is also a filter ancestor that filters out all the extended
835 * Otherwise, we collect all filters reaching the node,
836 * intersected with the root domain in collect_filter_prefix.
838 __isl_give isl_union_set
*isl_schedule_node_get_domain(
839 __isl_keep isl_schedule_node
*node
)
842 struct isl_schedule_node_get_filter_prefix_data data
;
847 if (node
->tree
== node
->schedule
->root
) {
850 space
= isl_schedule_get_space(node
->schedule
);
851 return isl_union_set_empty(space
);
854 data
.initialized
= 0;
855 data
.universe_domain
= 0;
856 data
.universe_filter
= 0;
857 data
.collect_prefix
= 0;
861 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
862 if (n
< 0 || collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
863 data
.filter
= isl_union_set_free(data
.filter
);
868 /* Return the union of universe sets of the domain elements that reach "node".
870 * If "node" is pointing at the root of the schedule tree, then
871 * there are no domain elements reaching the current node, so
872 * we return an empty result.
874 * Otherwise, we collect the universes of all filters reaching the node
875 * in collect_filter_prefix.
877 __isl_give isl_union_set
*isl_schedule_node_get_universe_domain(
878 __isl_keep isl_schedule_node
*node
)
881 struct isl_schedule_node_get_filter_prefix_data data
;
886 if (node
->tree
== node
->schedule
->root
) {
889 space
= isl_schedule_get_space(node
->schedule
);
890 return isl_union_set_empty(space
);
893 data
.initialized
= 0;
894 data
.universe_domain
= 1;
895 data
.universe_filter
= 1;
896 data
.collect_prefix
= 0;
900 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
901 if (n
< 0 || collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
902 data
.filter
= isl_union_set_free(data
.filter
);
907 /* Return the subtree schedule of "node".
909 * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle
910 * trees that do not contain any schedule information, we first
911 * move down to the first relevant descendant and handle leaves ourselves.
913 * If the subtree rooted at "node" contains any expansion nodes, then
914 * the returned subtree schedule is formulated in terms of the expanded
916 * The subtree is not allowed to contain any extension nodes.
918 __isl_give isl_union_map
*isl_schedule_node_get_subtree_schedule_union_map(
919 __isl_keep isl_schedule_node
*node
)
921 isl_schedule_tree
*tree
, *leaf
;
924 tree
= isl_schedule_node_get_tree(node
);
925 leaf
= isl_schedule_node_peek_leaf(node
);
926 tree
= isl_schedule_tree_first_schedule_descendant(tree
, leaf
);
930 isl_union_set
*domain
;
931 domain
= isl_schedule_node_get_universe_domain(node
);
932 isl_schedule_tree_free(tree
);
933 return isl_union_map_from_domain(domain
);
936 umap
= isl_schedule_tree_get_subtree_schedule_union_map(tree
);
937 isl_schedule_tree_free(tree
);
941 /* Return the number of ancestors of "node" in its schedule tree.
943 int isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node
*node
)
947 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
950 /* Does "node" have a parent?
952 * That is, does it point to any node of the schedule other than the root?
954 isl_bool
isl_schedule_node_has_parent(__isl_keep isl_schedule_node
*node
)
958 depth
= isl_schedule_node_get_tree_depth(node
);
960 return isl_bool_error
;
964 /* Return the position of "node" among the children of its parent.
966 int isl_schedule_node_get_child_position(__isl_keep isl_schedule_node
*node
)
973 has_parent
= isl_schedule_node_has_parent(node
);
977 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
978 "node has no parent", return -1);
980 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
981 return n
< 0 ? -1 : node
->child_pos
[n
- 1];
984 /* Does the parent (if any) of "node" have any children with a smaller child
985 * position than this one?
987 isl_bool
isl_schedule_node_has_previous_sibling(
988 __isl_keep isl_schedule_node
*node
)
994 return isl_bool_error
;
995 has_parent
= isl_schedule_node_has_parent(node
);
996 if (has_parent
< 0 || !has_parent
)
999 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1001 return isl_bool_error
;
1003 return node
->child_pos
[n
- 1] > 0;
1006 /* Does the parent (if any) of "node" have any children with a greater child
1007 * position than this one?
1009 isl_bool
isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node
*node
)
1011 isl_size n
, n_child
;
1012 isl_bool has_parent
;
1013 isl_schedule_tree
*tree
;
1016 return isl_bool_error
;
1017 has_parent
= isl_schedule_node_has_parent(node
);
1018 if (has_parent
< 0 || !has_parent
)
1021 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1023 return isl_bool_error
;
1024 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
1025 n_child
= isl_schedule_tree_n_children(tree
);
1026 isl_schedule_tree_free(tree
);
1028 return isl_bool_error
;
1030 return node
->child_pos
[n
- 1] + 1 < n_child
;
1033 /* Does "node" have any children?
1035 * Any node other than the leaf nodes is considered to have at least
1036 * one child, even if the corresponding isl_schedule_tree does not
1037 * have any children.
1039 isl_bool
isl_schedule_node_has_children(__isl_keep isl_schedule_node
*node
)
1042 return isl_bool_error
;
1043 return !isl_schedule_tree_is_leaf(node
->tree
);
1046 /* Return the number of children of "node"?
1048 * Any node other than the leaf nodes is considered to have at least
1049 * one child, even if the corresponding isl_schedule_tree does not
1050 * have any children. That is, the number of children of "node" is
1051 * only zero if its tree is the explicit empty tree. Otherwise,
1052 * if the isl_schedule_tree has any children, then it is equal
1053 * to the number of children of "node". If it has zero children,
1054 * then "node" still has a leaf node as child.
1056 isl_size
isl_schedule_node_n_children(__isl_keep isl_schedule_node
*node
)
1061 return isl_size_error
;
1063 if (isl_schedule_tree_is_leaf(node
->tree
))
1066 n
= isl_schedule_tree_n_children(node
->tree
);
1068 return isl_size_error
;
1075 /* Move the "node" pointer to the ancestor of the given generation
1076 * of the node it currently points to, where generation 0 is the node
1077 * itself and generation 1 is its parent.
1079 __isl_give isl_schedule_node
*isl_schedule_node_ancestor(
1080 __isl_take isl_schedule_node
*node
, int generation
)
1083 isl_schedule_tree
*tree
;
1087 if (generation
== 0)
1089 n
= isl_schedule_node_get_tree_depth(node
);
1091 return isl_schedule_node_free(node
);
1092 if (generation
< 0 || generation
> n
)
1093 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1094 "generation out of bounds",
1095 return isl_schedule_node_free(node
));
1096 node
= isl_schedule_node_cow(node
);
1100 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1102 isl_schedule_tree_free(node
->tree
);
1104 node
->ancestors
= isl_schedule_tree_list_drop(node
->ancestors
,
1105 n
- generation
, generation
);
1106 if (!node
->ancestors
|| !node
->tree
)
1107 return isl_schedule_node_free(node
);
1112 /* Move the "node" pointer to the parent of the node it currently points to.
1114 __isl_give isl_schedule_node
*isl_schedule_node_parent(
1115 __isl_take isl_schedule_node
*node
)
1119 if (!isl_schedule_node_has_parent(node
))
1120 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1121 "node has no parent",
1122 return isl_schedule_node_free(node
));
1123 return isl_schedule_node_ancestor(node
, 1);
1126 /* Move the "node" pointer to the root of its schedule tree.
1128 __isl_give isl_schedule_node
*isl_schedule_node_root(
1129 __isl_take isl_schedule_node
*node
)
1135 n
= isl_schedule_node_get_tree_depth(node
);
1137 return isl_schedule_node_free(node
);
1138 return isl_schedule_node_ancestor(node
, n
);
1141 /* Move the "node" pointer to the child at position "pos" of the node
1142 * it currently points to.
1144 __isl_give isl_schedule_node
*isl_schedule_node_child(
1145 __isl_take isl_schedule_node
*node
, int pos
)
1149 isl_schedule_tree
*tree
;
1152 node
= isl_schedule_node_cow(node
);
1155 if (!isl_schedule_node_has_children(node
))
1156 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1157 "node has no children",
1158 return isl_schedule_node_free(node
));
1160 ctx
= isl_schedule_node_get_ctx(node
);
1161 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1163 return isl_schedule_node_free(node
);
1164 child_pos
= isl_realloc_array(ctx
, node
->child_pos
, int, n
+ 1);
1166 return isl_schedule_node_free(node
);
1167 node
->child_pos
= child_pos
;
1168 node
->child_pos
[n
] = pos
;
1170 node
->ancestors
= isl_schedule_tree_list_add(node
->ancestors
,
1171 isl_schedule_tree_copy(node
->tree
));
1173 if (isl_schedule_tree_has_children(tree
))
1174 tree
= isl_schedule_tree_get_child(tree
, pos
);
1176 tree
= isl_schedule_node_get_leaf(node
);
1177 isl_schedule_tree_free(node
->tree
);
1180 if (!node
->tree
|| !node
->ancestors
)
1181 return isl_schedule_node_free(node
);
1186 /* Move the "node" pointer to the first child of the node
1187 * it currently points to.
1189 __isl_give isl_schedule_node
*isl_schedule_node_first_child(
1190 __isl_take isl_schedule_node
*node
)
1192 return isl_schedule_node_child(node
, 0);
1195 /* Move the "node" pointer to the child of this node's parent in
1196 * the previous child position.
1198 __isl_give isl_schedule_node
*isl_schedule_node_previous_sibling(
1199 __isl_take isl_schedule_node
*node
)
1202 isl_schedule_tree
*parent
, *tree
;
1204 node
= isl_schedule_node_cow(node
);
1207 if (!isl_schedule_node_has_previous_sibling(node
))
1208 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1209 "node has no previous sibling",
1210 return isl_schedule_node_free(node
));
1212 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1214 return isl_schedule_node_free(node
);
1215 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1218 return isl_schedule_node_free(node
);
1219 node
->child_pos
[n
- 1]--;
1220 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1221 node
->child_pos
[n
- 1]);
1222 isl_schedule_tree_free(parent
);
1224 return isl_schedule_node_free(node
);
1225 isl_schedule_tree_free(node
->tree
);
1231 /* Move the "node" pointer to the child of this node's parent in
1232 * the next child position.
1234 __isl_give isl_schedule_node
*isl_schedule_node_next_sibling(
1235 __isl_take isl_schedule_node
*node
)
1238 isl_schedule_tree
*parent
, *tree
;
1240 node
= isl_schedule_node_cow(node
);
1243 if (!isl_schedule_node_has_next_sibling(node
))
1244 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1245 "node has no next sibling",
1246 return isl_schedule_node_free(node
));
1248 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1250 return isl_schedule_node_free(node
);
1251 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1254 return isl_schedule_node_free(node
);
1255 node
->child_pos
[n
- 1]++;
1256 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1257 node
->child_pos
[n
- 1]);
1258 isl_schedule_tree_free(parent
);
1260 return isl_schedule_node_free(node
);
1261 isl_schedule_tree_free(node
->tree
);
1267 /* Return a copy to the child at position "pos" of "node".
1269 __isl_give isl_schedule_node
*isl_schedule_node_get_child(
1270 __isl_keep isl_schedule_node
*node
, int pos
)
1272 return isl_schedule_node_child(isl_schedule_node_copy(node
), pos
);
1275 /* Traverse the descendant of "node" in depth-first order, including
1276 * "node" itself. Call "enter" whenever a node is entered and "leave"
1277 * whenever a node is left. The callback "enter" is responsible
1278 * for moving to the deepest initial subtree of its argument that
1279 * should be traversed.
1281 static __isl_give isl_schedule_node
*traverse(
1282 __isl_take isl_schedule_node
*node
,
1283 __isl_give isl_schedule_node
*(*enter
)(
1284 __isl_take isl_schedule_node
*node
, void *user
),
1285 __isl_give isl_schedule_node
*(*leave
)(
1286 __isl_take isl_schedule_node
*node
, void *user
),
1294 depth
= isl_schedule_node_get_tree_depth(node
);
1296 node
= enter(node
, user
);
1297 node
= leave(node
, user
);
1298 while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
&&
1299 !isl_schedule_node_has_next_sibling(node
)) {
1300 node
= isl_schedule_node_parent(node
);
1301 node
= leave(node
, user
);
1303 if (node
&& isl_schedule_node_get_tree_depth(node
) > depth
)
1304 node
= isl_schedule_node_next_sibling(node
);
1305 } while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
);
1310 /* Internal data structure for isl_schedule_node_foreach_descendant_top_down.
1312 * "fn" is the user-specified callback function.
1313 * "user" is the user-specified argument for the callback.
1315 struct isl_schedule_node_preorder_data
{
1316 isl_bool (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
);
1320 /* Callback for "traverse" to enter a node and to move
1321 * to the deepest initial subtree that should be traversed
1322 * for use in a preorder visit.
1324 * If the user callback returns a negative value, then we abort
1325 * the traversal. If this callback returns zero, then we skip
1326 * the subtree rooted at the current node. Otherwise, we move
1327 * down to the first child and repeat the process until a leaf
1330 static __isl_give isl_schedule_node
*preorder_enter(
1331 __isl_take isl_schedule_node
*node
, void *user
)
1333 struct isl_schedule_node_preorder_data
*data
= user
;
1341 r
= data
->fn(node
, data
->user
);
1343 return isl_schedule_node_free(node
);
1344 if (r
== isl_bool_false
)
1346 } while (isl_schedule_node_has_children(node
) &&
1347 (node
= isl_schedule_node_first_child(node
)) != NULL
);
1352 /* Callback for "traverse" to leave a node
1353 * for use in a preorder visit.
1354 * Since we already visited the node when we entered it,
1355 * we do not need to do anything here.
1357 static __isl_give isl_schedule_node
*preorder_leave(
1358 __isl_take isl_schedule_node
*node
, void *user
)
1363 /* Traverse the descendants of "node" (including the node itself)
1364 * in depth first preorder.
1366 * If "fn" returns isl_bool_error on any of the nodes,
1367 * then the traversal is aborted.
1368 * If "fn" returns isl_bool_false on any of the nodes, then the subtree rooted
1369 * at that node is skipped.
1371 * Return isl_stat_ok on success and isl_stat_error on failure.
1373 isl_stat
isl_schedule_node_foreach_descendant_top_down(
1374 __isl_keep isl_schedule_node
*node
,
1375 isl_bool (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
),
1378 struct isl_schedule_node_preorder_data data
= { fn
, user
};
1380 node
= isl_schedule_node_copy(node
);
1381 node
= traverse(node
, &preorder_enter
, &preorder_leave
, &data
);
1382 isl_schedule_node_free(node
);
1384 return node
? isl_stat_ok
: isl_stat_error
;
1387 /* Internal data structure for isl_schedule_node_every_descendant.
1389 * "test" is the user-specified callback function.
1390 * "user" is the user-specified callback function argument.
1392 * "failed" is initialized to 0 and set to 1 if "test" fails
1395 struct isl_union_map_every_data
{
1396 isl_bool (*test
)(__isl_keep isl_schedule_node
*node
, void *user
);
1401 /* isl_schedule_node_foreach_descendant_top_down callback
1402 * that sets data->failed if data->test returns false and
1403 * subsequently aborts the traversal.
1405 static isl_bool
call_every(__isl_keep isl_schedule_node
*node
, void *user
)
1407 struct isl_union_map_every_data
*data
= user
;
1410 r
= data
->test(node
, data
->user
);
1412 return isl_bool_error
;
1414 return isl_bool_true
;
1416 return isl_bool_error
;
1419 /* Does "test" succeed on every descendant of "node" (including "node" itself)?
1421 isl_bool
isl_schedule_node_every_descendant(__isl_keep isl_schedule_node
*node
,
1422 isl_bool (*test
)(__isl_keep isl_schedule_node
*node
, void *user
),
1425 struct isl_union_map_every_data data
= { test
, user
, 0 };
1428 r
= isl_schedule_node_foreach_descendant_top_down(node
, &call_every
,
1431 return isl_bool_true
;
1433 return isl_bool_false
;
1434 return isl_bool_error
;
1437 /* Internal data structure for isl_schedule_node_map_descendant_bottom_up.
1439 * "fn" is the user-specified callback function.
1440 * "user" is the user-specified argument for the callback.
1442 struct isl_schedule_node_postorder_data
{
1443 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1448 /* Callback for "traverse" to enter a node and to move
1449 * to the deepest initial subtree that should be traversed
1450 * for use in a postorder visit.
1452 * Since we are performing a postorder visit, we only need
1453 * to move to the deepest initial leaf here.
1455 static __isl_give isl_schedule_node
*postorder_enter(
1456 __isl_take isl_schedule_node
*node
, void *user
)
1458 while (node
&& isl_schedule_node_has_children(node
))
1459 node
= isl_schedule_node_first_child(node
);
1464 /* Callback for "traverse" to leave a node
1465 * for use in a postorder visit.
1467 * Since we are performing a postorder visit, we need
1468 * to call the user callback here.
1470 static __isl_give isl_schedule_node
*postorder_leave(
1471 __isl_take isl_schedule_node
*node
, void *user
)
1473 struct isl_schedule_node_postorder_data
*data
= user
;
1475 return data
->fn(node
, data
->user
);
1478 /* Traverse the descendants of "node" (including the node itself)
1479 * in depth first postorder, allowing the user to modify the visited node.
1480 * The traversal continues from the node returned by the callback function.
1481 * It is the responsibility of the user to ensure that this does not
1482 * lead to an infinite loop. It is safest to always return a pointer
1483 * to the same position (same ancestors and child positions) as the input node.
1485 __isl_give isl_schedule_node
*isl_schedule_node_map_descendant_bottom_up(
1486 __isl_take isl_schedule_node
*node
,
1487 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1488 void *user
), void *user
)
1490 struct isl_schedule_node_postorder_data data
= { fn
, user
};
1492 return traverse(node
, &postorder_enter
, &postorder_leave
, &data
);
1495 /* Traverse the ancestors of "node" from the root down to and including
1496 * the parent of "node", calling "fn" on each of them.
1498 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1500 * Return 0 on success and -1 on failure.
1502 isl_stat
isl_schedule_node_foreach_ancestor_top_down(
1503 __isl_keep isl_schedule_node
*node
,
1504 isl_stat (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
),
1510 return isl_stat_error
;
1512 n
= isl_schedule_node_get_tree_depth(node
);
1513 for (i
= 0; i
< n
; ++i
) {
1514 isl_schedule_node
*ancestor
;
1517 ancestor
= isl_schedule_node_copy(node
);
1518 ancestor
= isl_schedule_node_ancestor(ancestor
, n
- i
);
1519 r
= fn(ancestor
, user
);
1520 isl_schedule_node_free(ancestor
);
1522 return isl_stat_error
;
1528 /* Is any node in the subtree rooted at "node" anchored?
1529 * That is, do any of these nodes reference the outer band nodes?
1531 isl_bool
isl_schedule_node_is_subtree_anchored(
1532 __isl_keep isl_schedule_node
*node
)
1535 return isl_bool_error
;
1536 return isl_schedule_tree_is_subtree_anchored(node
->tree
);
1539 /* Return the number of members in the given band node.
1541 unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node
*node
)
1543 return node
? isl_schedule_tree_band_n_member(node
->tree
) : 0;
1546 /* Is the band member at position "pos" of the band node "node"
1547 * marked coincident?
1549 isl_bool
isl_schedule_node_band_member_get_coincident(
1550 __isl_keep isl_schedule_node
*node
, int pos
)
1553 return isl_bool_error
;
1554 return isl_schedule_tree_band_member_get_coincident(node
->tree
, pos
);
1557 /* Mark the band member at position "pos" the band node "node"
1558 * as being coincident or not according to "coincident".
1560 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_coincident(
1561 __isl_take isl_schedule_node
*node
, int pos
, int coincident
)
1564 isl_schedule_tree
*tree
;
1568 c
= isl_schedule_node_band_member_get_coincident(node
, pos
);
1569 if (c
== coincident
)
1572 tree
= isl_schedule_tree_copy(node
->tree
);
1573 tree
= isl_schedule_tree_band_member_set_coincident(tree
, pos
,
1575 node
= isl_schedule_node_graft_tree(node
, tree
);
1580 /* Is the band node "node" marked permutable?
1582 isl_bool
isl_schedule_node_band_get_permutable(
1583 __isl_keep isl_schedule_node
*node
)
1586 return isl_bool_error
;
1588 return isl_schedule_tree_band_get_permutable(node
->tree
);
1591 /* Mark the band node "node" permutable or not according to "permutable"?
1593 __isl_give isl_schedule_node
*isl_schedule_node_band_set_permutable(
1594 __isl_take isl_schedule_node
*node
, int permutable
)
1596 isl_schedule_tree
*tree
;
1600 if (isl_schedule_node_band_get_permutable(node
) == permutable
)
1603 tree
= isl_schedule_tree_copy(node
->tree
);
1604 tree
= isl_schedule_tree_band_set_permutable(tree
, permutable
);
1605 node
= isl_schedule_node_graft_tree(node
, tree
);
1610 /* Return the schedule space of the band node.
1612 __isl_give isl_space
*isl_schedule_node_band_get_space(
1613 __isl_keep isl_schedule_node
*node
)
1618 return isl_schedule_tree_band_get_space(node
->tree
);
1621 /* Return the schedule of the band node in isolation.
1623 __isl_give isl_multi_union_pw_aff
*isl_schedule_node_band_get_partial_schedule(
1624 __isl_keep isl_schedule_node
*node
)
1629 return isl_schedule_tree_band_get_partial_schedule(node
->tree
);
1632 /* Return the schedule of the band node in isolation in the form of
1635 * If the band does not have any members, then we construct a universe map
1636 * with the universe of the domain elements reaching the node as domain.
1637 * Otherwise, we extract an isl_multi_union_pw_aff representation and
1638 * convert that to an isl_union_map.
1640 __isl_give isl_union_map
*isl_schedule_node_band_get_partial_schedule_union_map(
1641 __isl_keep isl_schedule_node
*node
)
1643 isl_multi_union_pw_aff
*mupa
;
1648 if (isl_schedule_node_get_type(node
) != isl_schedule_node_band
)
1649 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1650 "not a band node", return NULL
);
1651 if (isl_schedule_node_band_n_member(node
) == 0) {
1652 isl_union_set
*domain
;
1654 domain
= isl_schedule_node_get_universe_domain(node
);
1655 return isl_union_map_from_domain(domain
);
1658 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
1659 return isl_union_map_from_multi_union_pw_aff(mupa
);
1662 /* Return the loop AST generation type for the band member of band node "node"
1663 * at position "pos".
1665 enum isl_ast_loop_type
isl_schedule_node_band_member_get_ast_loop_type(
1666 __isl_keep isl_schedule_node
*node
, int pos
)
1669 return isl_ast_loop_error
;
1671 return isl_schedule_tree_band_member_get_ast_loop_type(node
->tree
, pos
);
1674 /* Set the loop AST generation type for the band member of band node "node"
1675 * at position "pos" to "type".
1677 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_ast_loop_type(
1678 __isl_take isl_schedule_node
*node
, int pos
,
1679 enum isl_ast_loop_type type
)
1681 isl_schedule_tree
*tree
;
1686 tree
= isl_schedule_tree_copy(node
->tree
);
1687 tree
= isl_schedule_tree_band_member_set_ast_loop_type(tree
, pos
, type
);
1688 return isl_schedule_node_graft_tree(node
, tree
);
1691 /* Return the loop AST generation type for the band member of band node "node"
1692 * at position "pos" for the isolated part.
1694 enum isl_ast_loop_type
isl_schedule_node_band_member_get_isolate_ast_loop_type(
1695 __isl_keep isl_schedule_node
*node
, int pos
)
1698 return isl_ast_loop_error
;
1700 return isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1704 /* Set the loop AST generation type for the band member of band node "node"
1705 * at position "pos" for the isolated part to "type".
1707 __isl_give isl_schedule_node
*
1708 isl_schedule_node_band_member_set_isolate_ast_loop_type(
1709 __isl_take isl_schedule_node
*node
, int pos
,
1710 enum isl_ast_loop_type type
)
1712 isl_schedule_tree
*tree
;
1717 tree
= isl_schedule_tree_copy(node
->tree
);
1718 tree
= isl_schedule_tree_band_member_set_isolate_ast_loop_type(tree
,
1720 return isl_schedule_node_graft_tree(node
, tree
);
1723 /* Return the AST build options associated to band node "node".
1725 __isl_give isl_union_set
*isl_schedule_node_band_get_ast_build_options(
1726 __isl_keep isl_schedule_node
*node
)
1731 return isl_schedule_tree_band_get_ast_build_options(node
->tree
);
1734 /* Replace the AST build options associated to band node "node" by "options".
1736 __isl_give isl_schedule_node
*isl_schedule_node_band_set_ast_build_options(
1737 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*options
)
1739 isl_schedule_tree
*tree
;
1741 if (!node
|| !options
)
1744 tree
= isl_schedule_tree_copy(node
->tree
);
1745 tree
= isl_schedule_tree_band_set_ast_build_options(tree
, options
);
1746 return isl_schedule_node_graft_tree(node
, tree
);
1748 isl_schedule_node_free(node
);
1749 isl_union_set_free(options
);
1753 /* Return the "isolate" option associated to band node "node".
1755 __isl_give isl_set
*isl_schedule_node_band_get_ast_isolate_option(
1756 __isl_keep isl_schedule_node
*node
)
1763 depth
= isl_schedule_node_get_schedule_depth(node
);
1764 return isl_schedule_tree_band_get_ast_isolate_option(node
->tree
, depth
);
1767 /* Make sure that that spaces of "node" and "mv" are the same.
1768 * Return -1 on error, reporting the error to the user.
1770 static int check_space_multi_val(__isl_keep isl_schedule_node
*node
,
1771 __isl_keep isl_multi_val
*mv
)
1773 isl_space
*node_space
, *mv_space
;
1776 node_space
= isl_schedule_node_band_get_space(node
);
1777 mv_space
= isl_multi_val_get_space(mv
);
1778 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1779 mv_space
, isl_dim_set
);
1780 isl_space_free(mv_space
);
1781 isl_space_free(node_space
);
1785 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1786 "spaces don't match", return -1);
1791 /* Multiply the partial schedule of the band node "node"
1792 * with the factors in "mv".
1794 __isl_give isl_schedule_node
*isl_schedule_node_band_scale(
1795 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1797 isl_schedule_tree
*tree
;
1802 if (check_space_multi_val(node
, mv
) < 0)
1804 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1808 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1809 "cannot scale band node with anchored subtree",
1812 tree
= isl_schedule_node_get_tree(node
);
1813 tree
= isl_schedule_tree_band_scale(tree
, mv
);
1814 return isl_schedule_node_graft_tree(node
, tree
);
1816 isl_multi_val_free(mv
);
1817 isl_schedule_node_free(node
);
1821 /* Divide the partial schedule of the band node "node"
1822 * by the factors in "mv".
1824 __isl_give isl_schedule_node
*isl_schedule_node_band_scale_down(
1825 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1827 isl_schedule_tree
*tree
;
1832 if (check_space_multi_val(node
, mv
) < 0)
1834 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1838 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1839 "cannot scale down band node with anchored subtree",
1842 tree
= isl_schedule_node_get_tree(node
);
1843 tree
= isl_schedule_tree_band_scale_down(tree
, mv
);
1844 return isl_schedule_node_graft_tree(node
, tree
);
1846 isl_multi_val_free(mv
);
1847 isl_schedule_node_free(node
);
1851 /* Reduce the partial schedule of the band node "node"
1852 * modulo the factors in "mv".
1854 __isl_give isl_schedule_node
*isl_schedule_node_band_mod(
1855 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1857 isl_schedule_tree
*tree
;
1862 if (check_space_multi_val(node
, mv
) < 0)
1864 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1868 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1869 "cannot perform mod on band node with anchored subtree",
1872 tree
= isl_schedule_node_get_tree(node
);
1873 tree
= isl_schedule_tree_band_mod(tree
, mv
);
1874 return isl_schedule_node_graft_tree(node
, tree
);
1876 isl_multi_val_free(mv
);
1877 isl_schedule_node_free(node
);
1881 /* Make sure that that spaces of "node" and "mupa" are the same.
1882 * Return isl_stat_error on error, reporting the error to the user.
1884 static isl_stat
check_space_multi_union_pw_aff(
1885 __isl_keep isl_schedule_node
*node
,
1886 __isl_keep isl_multi_union_pw_aff
*mupa
)
1888 isl_space
*node_space
, *mupa_space
;
1891 node_space
= isl_schedule_node_band_get_space(node
);
1892 mupa_space
= isl_multi_union_pw_aff_get_space(mupa
);
1893 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1894 mupa_space
, isl_dim_set
);
1895 isl_space_free(mupa_space
);
1896 isl_space_free(node_space
);
1898 return isl_stat_error
;
1900 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1901 "spaces don't match", return isl_stat_error
);
1906 /* Shift the partial schedule of the band node "node" by "shift".
1908 __isl_give isl_schedule_node
*isl_schedule_node_band_shift(
1909 __isl_take isl_schedule_node
*node
,
1910 __isl_take isl_multi_union_pw_aff
*shift
)
1912 isl_schedule_tree
*tree
;
1915 if (!node
|| !shift
)
1917 if (check_space_multi_union_pw_aff(node
, shift
) < 0)
1919 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1923 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1924 "cannot shift band node with anchored subtree",
1927 tree
= isl_schedule_node_get_tree(node
);
1928 tree
= isl_schedule_tree_band_shift(tree
, shift
);
1929 return isl_schedule_node_graft_tree(node
, tree
);
1931 isl_multi_union_pw_aff_free(shift
);
1932 isl_schedule_node_free(node
);
1936 /* Tile "node" with tile sizes "sizes".
1938 * The current node is replaced by two nested nodes corresponding
1939 * to the tile dimensions and the point dimensions.
1941 * Return a pointer to the outer (tile) node.
1943 * If any of the descendants of "node" depend on the set of outer band nodes,
1944 * then we refuse to tile the node.
1946 * If the scale tile loops option is set, then the tile loops
1947 * are scaled by the tile sizes. If the shift point loops option is set,
1948 * then the point loops are shifted to start at zero.
1949 * In particular, these options affect the tile and point loop schedules
1952 * scale shift original tile point
1954 * 0 0 i floor(i/s) i
1955 * 1 0 i s * floor(i/s) i
1956 * 0 1 i floor(i/s) i - s * floor(i/s)
1957 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1959 __isl_give isl_schedule_node
*isl_schedule_node_band_tile(
1960 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*sizes
)
1962 isl_schedule_tree
*tree
;
1965 if (!node
|| !sizes
)
1967 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1971 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1972 "cannot tile band node with anchored subtree",
1975 if (check_space_multi_val(node
, sizes
) < 0)
1978 tree
= isl_schedule_node_get_tree(node
);
1979 tree
= isl_schedule_tree_band_tile(tree
, sizes
);
1980 return isl_schedule_node_graft_tree(node
, tree
);
1982 isl_multi_val_free(sizes
);
1983 isl_schedule_node_free(node
);
1987 /* Move the band node "node" down to all the leaves in the subtree
1989 * Return a pointer to the node in the resulting tree that is in the same
1990 * position as the node pointed to by "node" in the original tree.
1992 * If the node only has a leaf child, then nothing needs to be done.
1993 * Otherwise, the child of the node is removed and the result is
1994 * appended to all the leaves in the subtree rooted at the original child.
1995 * Since the node is moved to the leaves, it needs to be expanded
1996 * according to the expansion, if any, defined by that subtree.
1997 * In the end, the original node is replaced by the result of
1998 * attaching copies of the expanded node to the leaves.
2000 * If any of the nodes in the subtree rooted at "node" depend on
2001 * the set of outer band nodes then we refuse to sink the band node.
2003 __isl_give isl_schedule_node
*isl_schedule_node_band_sink(
2004 __isl_take isl_schedule_node
*node
)
2006 enum isl_schedule_node_type type
;
2007 isl_schedule_tree
*tree
, *child
;
2008 isl_union_pw_multi_aff
*contraction
;
2015 type
= isl_schedule_node_get_type(node
);
2016 if (type
!= isl_schedule_node_band
)
2017 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2018 "not a band node", return isl_schedule_node_free(node
));
2019 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2021 return isl_schedule_node_free(node
);
2023 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2024 "cannot sink band node in anchored subtree",
2025 return isl_schedule_node_free(node
));
2026 n
= isl_schedule_tree_n_children(node
->tree
);
2028 return isl_schedule_node_free(node
);
2032 contraction
= isl_schedule_node_get_subtree_contraction(node
);
2034 tree
= isl_schedule_node_get_tree(node
);
2035 child
= isl_schedule_tree_get_child(tree
, 0);
2036 tree
= isl_schedule_tree_reset_children(tree
);
2037 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, contraction
);
2038 tree
= isl_schedule_tree_append_to_leaves(child
, tree
);
2040 return isl_schedule_node_graft_tree(node
, tree
);
2043 /* Split "node" into two nested band nodes, one with the first "pos"
2044 * dimensions and one with the remaining dimensions.
2045 * The schedules of the two band nodes live in anonymous spaces.
2046 * The loop AST generation type options and the isolate option
2047 * are split over the two band nodes.
2049 __isl_give isl_schedule_node
*isl_schedule_node_band_split(
2050 __isl_take isl_schedule_node
*node
, int pos
)
2053 isl_schedule_tree
*tree
;
2055 depth
= isl_schedule_node_get_schedule_depth(node
);
2056 tree
= isl_schedule_node_get_tree(node
);
2057 tree
= isl_schedule_tree_band_split(tree
, pos
, depth
);
2058 return isl_schedule_node_graft_tree(node
, tree
);
2061 /* Return the context of the context node "node".
2063 __isl_give isl_set
*isl_schedule_node_context_get_context(
2064 __isl_keep isl_schedule_node
*node
)
2069 return isl_schedule_tree_context_get_context(node
->tree
);
2072 /* Return the domain of the domain node "node".
2074 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
2075 __isl_keep isl_schedule_node
*node
)
2080 return isl_schedule_tree_domain_get_domain(node
->tree
);
2083 /* Return the expansion map of expansion node "node".
2085 __isl_give isl_union_map
*isl_schedule_node_expansion_get_expansion(
2086 __isl_keep isl_schedule_node
*node
)
2091 return isl_schedule_tree_expansion_get_expansion(node
->tree
);
2094 /* Return the contraction of expansion node "node".
2096 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_expansion_get_contraction(
2097 __isl_keep isl_schedule_node
*node
)
2102 return isl_schedule_tree_expansion_get_contraction(node
->tree
);
2105 /* Replace the contraction and the expansion of the expansion node "node"
2106 * by "contraction" and "expansion".
2108 __isl_give isl_schedule_node
*
2109 isl_schedule_node_expansion_set_contraction_and_expansion(
2110 __isl_take isl_schedule_node
*node
,
2111 __isl_take isl_union_pw_multi_aff
*contraction
,
2112 __isl_take isl_union_map
*expansion
)
2114 isl_schedule_tree
*tree
;
2116 if (!node
|| !contraction
|| !expansion
)
2119 tree
= isl_schedule_tree_copy(node
->tree
);
2120 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
2121 contraction
, expansion
);
2122 return isl_schedule_node_graft_tree(node
, tree
);
2124 isl_schedule_node_free(node
);
2125 isl_union_pw_multi_aff_free(contraction
);
2126 isl_union_map_free(expansion
);
2130 /* Return the extension of the extension node "node".
2132 __isl_give isl_union_map
*isl_schedule_node_extension_get_extension(
2133 __isl_keep isl_schedule_node
*node
)
2138 return isl_schedule_tree_extension_get_extension(node
->tree
);
2141 /* Replace the extension of extension node "node" by "extension".
2143 __isl_give isl_schedule_node
*isl_schedule_node_extension_set_extension(
2144 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
2146 isl_schedule_tree
*tree
;
2148 if (!node
|| !extension
)
2151 tree
= isl_schedule_tree_copy(node
->tree
);
2152 tree
= isl_schedule_tree_extension_set_extension(tree
, extension
);
2153 return isl_schedule_node_graft_tree(node
, tree
);
2155 isl_schedule_node_free(node
);
2156 isl_union_map_free(extension
);
2160 /* Return the filter of the filter node "node".
2162 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
2163 __isl_keep isl_schedule_node
*node
)
2168 return isl_schedule_tree_filter_get_filter(node
->tree
);
2171 /* Replace the filter of filter node "node" by "filter".
2173 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
2174 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2176 isl_schedule_tree
*tree
;
2178 if (!node
|| !filter
)
2181 tree
= isl_schedule_tree_copy(node
->tree
);
2182 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
2183 return isl_schedule_node_graft_tree(node
, tree
);
2185 isl_schedule_node_free(node
);
2186 isl_union_set_free(filter
);
2190 /* Intersect the filter of filter node "node" with "filter".
2192 * If the filter of the node is already a subset of "filter",
2193 * then leave the node unchanged.
2195 __isl_give isl_schedule_node
*isl_schedule_node_filter_intersect_filter(
2196 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2198 isl_union_set
*node_filter
= NULL
;
2201 if (!node
|| !filter
)
2204 node_filter
= isl_schedule_node_filter_get_filter(node
);
2205 subset
= isl_union_set_is_subset(node_filter
, filter
);
2209 isl_union_set_free(node_filter
);
2210 isl_union_set_free(filter
);
2213 node_filter
= isl_union_set_intersect(node_filter
, filter
);
2214 node
= isl_schedule_node_filter_set_filter(node
, node_filter
);
2217 isl_schedule_node_free(node
);
2218 isl_union_set_free(node_filter
);
2219 isl_union_set_free(filter
);
2223 /* Return the guard of the guard node "node".
2225 __isl_give isl_set
*isl_schedule_node_guard_get_guard(
2226 __isl_keep isl_schedule_node
*node
)
2231 return isl_schedule_tree_guard_get_guard(node
->tree
);
2234 /* Return the mark identifier of the mark node "node".
2236 __isl_give isl_id
*isl_schedule_node_mark_get_id(
2237 __isl_keep isl_schedule_node
*node
)
2242 return isl_schedule_tree_mark_get_id(node
->tree
);
2245 /* Replace the child at position "pos" of the sequence node "node"
2246 * by the children of sequence root node of "tree".
2248 __isl_give isl_schedule_node
*isl_schedule_node_sequence_splice(
2249 __isl_take isl_schedule_node
*node
, int pos
,
2250 __isl_take isl_schedule_tree
*tree
)
2252 isl_schedule_tree
*node_tree
;
2256 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2257 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2258 "not a sequence node", goto error
);
2259 if (isl_schedule_tree_get_type(tree
) != isl_schedule_node_sequence
)
2260 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2261 "not a sequence node", goto error
);
2262 node_tree
= isl_schedule_node_get_tree(node
);
2263 node_tree
= isl_schedule_tree_sequence_splice(node_tree
, pos
, tree
);
2264 node
= isl_schedule_node_graft_tree(node
, node_tree
);
2268 isl_schedule_node_free(node
);
2269 isl_schedule_tree_free(tree
);
2273 /* Given a sequence node "node", with a child at position "pos" that
2274 * is also a sequence node, attach the children of that node directly
2275 * as children of "node" at that position, replacing the original child.
2277 * The filters of these children are intersected with the filter
2278 * of the child at position "pos".
2280 __isl_give isl_schedule_node
*isl_schedule_node_sequence_splice_child(
2281 __isl_take isl_schedule_node
*node
, int pos
)
2285 isl_union_set
*filter
;
2286 isl_schedule_node
*child
;
2287 isl_schedule_tree
*tree
;
2291 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2292 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2293 "not a sequence node",
2294 return isl_schedule_node_free(node
));
2295 node
= isl_schedule_node_child(node
, pos
);
2296 node
= isl_schedule_node_child(node
, 0);
2297 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2298 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2299 "not a sequence node",
2300 return isl_schedule_node_free(node
));
2301 n
= isl_schedule_node_n_children(node
);
2303 return isl_schedule_node_free(node
);
2304 child
= isl_schedule_node_copy(node
);
2305 node
= isl_schedule_node_parent(node
);
2306 filter
= isl_schedule_node_filter_get_filter(node
);
2307 for (i
= 0; i
< n
; ++i
) {
2308 child
= isl_schedule_node_child(child
, i
);
2309 child
= isl_schedule_node_filter_intersect_filter(child
,
2310 isl_union_set_copy(filter
));
2311 child
= isl_schedule_node_parent(child
);
2313 isl_union_set_free(filter
);
2314 tree
= isl_schedule_node_get_tree(child
);
2315 isl_schedule_node_free(child
);
2316 node
= isl_schedule_node_parent(node
);
2317 node
= isl_schedule_node_sequence_splice(node
, pos
, tree
);
2322 /* Update the ancestors of "node" to point to the tree that "node"
2324 * That is, replace the child in the original parent that corresponds
2325 * to the current tree position by node->tree and continue updating
2326 * the ancestors in the same way until the root is reached.
2328 * If "fn" is not NULL, then it is called on each ancestor as we move up
2329 * the tree so that it can modify the ancestor before it is added
2330 * to the list of ancestors of the modified node.
2331 * The additional "pos" argument records the position
2332 * of the "tree" argument in the original schedule tree.
2334 * If "node" originally points to a leaf of the schedule tree, then make sure
2335 * that in the end it points to a leaf in the updated schedule tree.
2337 static __isl_give isl_schedule_node
*update_ancestors(
2338 __isl_take isl_schedule_node
*node
,
2339 __isl_give isl_schedule_tree
*(*fn
)(__isl_take isl_schedule_tree
*tree
,
2340 __isl_keep isl_schedule_node
*pos
, void *user
), void *user
)
2345 isl_schedule_tree
*tree
;
2346 isl_schedule_node
*pos
= NULL
;
2349 pos
= isl_schedule_node_copy(node
);
2351 node
= isl_schedule_node_cow(node
);
2353 return isl_schedule_node_free(pos
);
2355 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
2357 return isl_schedule_node_free(pos
);
2358 tree
= isl_schedule_tree_copy(node
->tree
);
2360 for (i
= n
- 1; i
>= 0; --i
) {
2361 isl_schedule_tree
*parent
;
2363 parent
= isl_schedule_tree_list_get_schedule_tree(
2364 node
->ancestors
, i
);
2365 parent
= isl_schedule_tree_replace_child(parent
,
2366 node
->child_pos
[i
], tree
);
2368 pos
= isl_schedule_node_parent(pos
);
2369 parent
= fn(parent
, pos
, user
);
2371 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
2372 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
2378 isl_schedule_node_free(pos
);
2380 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
2381 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
2383 isl_schedule_tree_free(node
->tree
);
2384 node
->tree
= isl_schedule_node_get_leaf(node
);
2387 if (!node
->schedule
|| !node
->ancestors
)
2388 return isl_schedule_node_free(node
);
2393 /* Replace the subtree that "pos" points to by "tree", updating
2394 * the ancestors to maintain a consistent state.
2396 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
2397 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
2401 if (pos
->tree
== tree
) {
2402 isl_schedule_tree_free(tree
);
2406 pos
= isl_schedule_node_cow(pos
);
2410 isl_schedule_tree_free(pos
->tree
);
2413 return update_ancestors(pos
, NULL
, NULL
);
2415 isl_schedule_node_free(pos
);
2416 isl_schedule_tree_free(tree
);
2420 /* Make sure we can insert a node between "node" and its parent.
2421 * Return -1 on error, reporting the reason why we cannot insert a node.
2423 static int check_insert(__isl_keep isl_schedule_node
*node
)
2426 enum isl_schedule_node_type type
;
2428 has_parent
= isl_schedule_node_has_parent(node
);
2432 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2433 "cannot insert node outside of root", return -1);
2435 type
= isl_schedule_node_get_parent_type(node
);
2436 if (type
== isl_schedule_node_error
)
2438 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
2439 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2440 "cannot insert node between set or sequence node "
2441 "and its filter children", return -1);
2446 /* Insert a band node with partial schedule "mupa" between "node" and
2448 * Return a pointer to the new band node.
2450 * If any of the nodes in the subtree rooted at "node" depend on
2451 * the set of outer band nodes then we refuse to insert the band node.
2453 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
2454 __isl_take isl_schedule_node
*node
,
2455 __isl_take isl_multi_union_pw_aff
*mupa
)
2458 isl_schedule_band
*band
;
2459 isl_schedule_tree
*tree
;
2461 if (check_insert(node
) < 0)
2462 node
= isl_schedule_node_free(node
);
2463 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2467 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2468 "cannot insert band node in anchored subtree",
2471 tree
= isl_schedule_node_get_tree(node
);
2472 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
2473 tree
= isl_schedule_tree_insert_band(tree
, band
);
2474 node
= isl_schedule_node_graft_tree(node
, tree
);
2478 isl_schedule_node_free(node
);
2479 isl_multi_union_pw_aff_free(mupa
);
2483 /* Insert a context node with context "context" between "node" and its parent.
2484 * Return a pointer to the new context node.
2486 __isl_give isl_schedule_node
*isl_schedule_node_insert_context(
2487 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
2489 isl_schedule_tree
*tree
;
2491 if (check_insert(node
) < 0)
2492 node
= isl_schedule_node_free(node
);
2494 tree
= isl_schedule_node_get_tree(node
);
2495 tree
= isl_schedule_tree_insert_context(tree
, context
);
2496 node
= isl_schedule_node_graft_tree(node
, tree
);
2501 /* Insert an expansion node with the given "contraction" and "expansion"
2502 * between "node" and its parent.
2503 * Return a pointer to the new expansion node.
2505 * Typically the domain and range spaces of the expansion are different.
2506 * This means that only one of them can refer to the current domain space
2507 * in a consistent tree. It is up to the caller to ensure that the tree
2508 * returns to a consistent state.
2510 __isl_give isl_schedule_node
*isl_schedule_node_insert_expansion(
2511 __isl_take isl_schedule_node
*node
,
2512 __isl_take isl_union_pw_multi_aff
*contraction
,
2513 __isl_take isl_union_map
*expansion
)
2515 isl_schedule_tree
*tree
;
2517 if (check_insert(node
) < 0)
2518 node
= isl_schedule_node_free(node
);
2520 tree
= isl_schedule_node_get_tree(node
);
2521 tree
= isl_schedule_tree_insert_expansion(tree
, contraction
, expansion
);
2522 node
= isl_schedule_node_graft_tree(node
, tree
);
2527 /* Insert an extension node with extension "extension" between "node" and
2529 * Return a pointer to the new extension node.
2531 __isl_give isl_schedule_node
*isl_schedule_node_insert_extension(
2532 __isl_take isl_schedule_node
*node
,
2533 __isl_take isl_union_map
*extension
)
2535 isl_schedule_tree
*tree
;
2537 tree
= isl_schedule_node_get_tree(node
);
2538 tree
= isl_schedule_tree_insert_extension(tree
, extension
);
2539 node
= isl_schedule_node_graft_tree(node
, tree
);
2544 /* Insert a filter node with filter "filter" between "node" and its parent.
2545 * Return a pointer to the new filter node.
2547 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
2548 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2550 isl_schedule_tree
*tree
;
2552 if (check_insert(node
) < 0)
2553 node
= isl_schedule_node_free(node
);
2555 tree
= isl_schedule_node_get_tree(node
);
2556 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2557 node
= isl_schedule_node_graft_tree(node
, tree
);
2562 /* Insert a guard node with guard "guard" between "node" and its parent.
2563 * Return a pointer to the new guard node.
2565 __isl_give isl_schedule_node
*isl_schedule_node_insert_guard(
2566 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*guard
)
2568 isl_schedule_tree
*tree
;
2570 if (check_insert(node
) < 0)
2571 node
= isl_schedule_node_free(node
);
2573 tree
= isl_schedule_node_get_tree(node
);
2574 tree
= isl_schedule_tree_insert_guard(tree
, guard
);
2575 node
= isl_schedule_node_graft_tree(node
, tree
);
2580 /* Insert a mark node with mark identifier "mark" between "node" and
2582 * Return a pointer to the new mark node.
2584 __isl_give isl_schedule_node
*isl_schedule_node_insert_mark(
2585 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*mark
)
2587 isl_schedule_tree
*tree
;
2589 if (check_insert(node
) < 0)
2590 node
= isl_schedule_node_free(node
);
2592 tree
= isl_schedule_node_get_tree(node
);
2593 tree
= isl_schedule_tree_insert_mark(tree
, mark
);
2594 node
= isl_schedule_node_graft_tree(node
, tree
);
2599 /* Attach the current subtree of "node" to a sequence of filter tree nodes
2600 * with filters described by "filters", attach this sequence
2601 * of filter tree nodes as children to a new tree of type "type" and
2602 * replace the original subtree of "node" by this new tree.
2603 * Each copy of the original subtree is simplified with respect
2604 * to the corresponding filter.
2606 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
2607 __isl_take isl_schedule_node
*node
,
2608 enum isl_schedule_node_type type
,
2609 __isl_take isl_union_set_list
*filters
)
2614 isl_schedule_tree
*tree
;
2615 isl_schedule_tree_list
*list
;
2617 if (check_insert(node
) < 0)
2618 node
= isl_schedule_node_free(node
);
2620 n
= isl_union_set_list_n_union_set(filters
);
2624 ctx
= isl_schedule_node_get_ctx(node
);
2625 list
= isl_schedule_tree_list_alloc(ctx
, n
);
2626 for (i
= 0; i
< n
; ++i
) {
2627 isl_schedule_node
*node_i
;
2628 isl_schedule_tree
*tree
;
2629 isl_union_set
*filter
;
2631 filter
= isl_union_set_list_get_union_set(filters
, i
);
2632 node_i
= isl_schedule_node_copy(node
);
2633 node_i
= isl_schedule_node_gist(node_i
,
2634 isl_union_set_copy(filter
));
2635 tree
= isl_schedule_node_get_tree(node_i
);
2636 isl_schedule_node_free(node_i
);
2637 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2638 list
= isl_schedule_tree_list_add(list
, tree
);
2640 tree
= isl_schedule_tree_from_children(type
, list
);
2641 node
= isl_schedule_node_graft_tree(node
, tree
);
2643 isl_union_set_list_free(filters
);
2646 isl_union_set_list_free(filters
);
2647 isl_schedule_node_free(node
);
2651 /* Insert a sequence node with child filters "filters" between "node" and
2652 * its parent. That is, the tree that "node" points to is attached
2653 * to each of the child nodes of the filter nodes.
2654 * Return a pointer to the new sequence node.
2656 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
2657 __isl_take isl_schedule_node
*node
,
2658 __isl_take isl_union_set_list
*filters
)
2660 return isl_schedule_node_insert_children(node
,
2661 isl_schedule_node_sequence
, filters
);
2664 /* Insert a set node with child filters "filters" between "node" and
2665 * its parent. That is, the tree that "node" points to is attached
2666 * to each of the child nodes of the filter nodes.
2667 * Return a pointer to the new set node.
2669 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
2670 __isl_take isl_schedule_node
*node
,
2671 __isl_take isl_union_set_list
*filters
)
2673 return isl_schedule_node_insert_children(node
,
2674 isl_schedule_node_set
, filters
);
2677 /* Remove "node" from its schedule tree and return a pointer
2678 * to the leaf at the same position in the updated schedule tree.
2680 * It is not allowed to remove the root of a schedule tree or
2681 * a child of a set or sequence node.
2683 __isl_give isl_schedule_node
*isl_schedule_node_cut(
2684 __isl_take isl_schedule_node
*node
)
2686 isl_schedule_tree
*leaf
;
2687 enum isl_schedule_node_type parent_type
;
2691 if (!isl_schedule_node_has_parent(node
))
2692 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2693 "cannot cut root", return isl_schedule_node_free(node
));
2695 parent_type
= isl_schedule_node_get_parent_type(node
);
2696 if (parent_type
== isl_schedule_node_set
||
2697 parent_type
== isl_schedule_node_sequence
)
2698 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2699 "cannot cut child of set or sequence",
2700 return isl_schedule_node_free(node
));
2702 leaf
= isl_schedule_node_get_leaf(node
);
2703 return isl_schedule_node_graft_tree(node
, leaf
);
2706 /* Remove a single node from the schedule tree, attaching the child
2707 * of "node" directly to its parent.
2708 * Return a pointer to this former child or to the leaf the position
2709 * of the original node if there was no child.
2710 * It is not allowed to remove the root of a schedule tree,
2711 * a set or sequence node, a child of a set or sequence node or
2712 * a band node with an anchored subtree.
2714 __isl_give isl_schedule_node
*isl_schedule_node_delete(
2715 __isl_take isl_schedule_node
*node
)
2718 isl_schedule_tree
*tree
;
2719 enum isl_schedule_node_type type
;
2721 n
= isl_schedule_node_n_children(node
);
2723 return isl_schedule_node_free(node
);
2725 if (isl_schedule_node_get_tree_depth(node
) == 0)
2726 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2727 "cannot delete root node",
2728 return isl_schedule_node_free(node
));
2730 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2731 "can only delete node with a single child",
2732 return isl_schedule_node_free(node
));
2733 type
= isl_schedule_node_get_parent_type(node
);
2734 if (type
== isl_schedule_node_sequence
|| type
== isl_schedule_node_set
)
2735 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2736 "cannot delete child of set or sequence",
2737 return isl_schedule_node_free(node
));
2738 if (isl_schedule_node_get_type(node
) == isl_schedule_node_band
) {
2741 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2743 return isl_schedule_node_free(node
);
2745 isl_die(isl_schedule_node_get_ctx(node
),
2747 "cannot delete band node with anchored subtree",
2748 return isl_schedule_node_free(node
));
2751 tree
= isl_schedule_node_get_tree(node
);
2752 if (!tree
|| isl_schedule_tree_has_children(tree
)) {
2753 tree
= isl_schedule_tree_child(tree
, 0);
2755 isl_schedule_tree_free(tree
);
2756 tree
= isl_schedule_node_get_leaf(node
);
2758 node
= isl_schedule_node_graft_tree(node
, tree
);
2763 /* Internal data structure for the group_ancestor callback.
2765 * If "finished" is set, then we no longer need to modify
2766 * any further ancestors.
2768 * "contraction" and "expansion" represent the expansion
2769 * that reflects the grouping.
2771 * "domain" contains the domain elements that reach the position
2772 * where the grouping is performed. That is, it is the range
2773 * of the resulting expansion.
2774 * "domain_universe" is the universe of "domain".
2775 * "group" is the set of group elements, i.e., the domain
2776 * of the resulting expansion.
2777 * "group_universe" is the universe of "group".
2779 * "sched" is the schedule for the group elements, in pratice
2780 * an identity mapping on "group_universe".
2781 * "dim" is the dimension of "sched".
2783 struct isl_schedule_group_data
{
2786 isl_union_map
*expansion
;
2787 isl_union_pw_multi_aff
*contraction
;
2789 isl_union_set
*domain
;
2790 isl_union_set
*domain_universe
;
2791 isl_union_set
*group
;
2792 isl_union_set
*group_universe
;
2795 isl_multi_aff
*sched
;
2798 /* Is domain covered by data->domain within data->domain_universe?
2800 static isl_bool
locally_covered_by_domain(__isl_keep isl_union_set
*domain
,
2801 struct isl_schedule_group_data
*data
)
2804 isl_union_set
*test
;
2806 test
= isl_union_set_copy(domain
);
2807 test
= isl_union_set_intersect(test
,
2808 isl_union_set_copy(data
->domain_universe
));
2809 is_subset
= isl_union_set_is_subset(test
, data
->domain
);
2810 isl_union_set_free(test
);
2815 /* Update the band tree root "tree" to refer to the group instances
2816 * in data->group rather than the original domain elements in data->domain.
2817 * "pos" is the position in the original schedule tree where the modified
2818 * "tree" will be attached.
2820 * Add the part of the identity schedule on the group instances data->sched
2821 * that corresponds to this band node to the band schedule.
2822 * If the domain elements that reach the node and that are part
2823 * of data->domain_universe are all elements of data->domain (and therefore
2824 * replaced by the group instances) then this data->domain_universe
2825 * is removed from the domain of the band schedule.
2827 static __isl_give isl_schedule_tree
*group_band(
2828 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2829 struct isl_schedule_group_data
*data
)
2831 isl_union_set
*domain
;
2833 isl_multi_union_pw_aff
*mupa
, *partial
;
2834 isl_bool is_covered
;
2838 domain
= isl_schedule_node_get_domain(pos
);
2839 is_covered
= locally_covered_by_domain(domain
, data
);
2840 if (is_covered
>= 0 && is_covered
) {
2841 domain
= isl_union_set_universe(domain
);
2842 domain
= isl_union_set_subtract(domain
,
2843 isl_union_set_copy(data
->domain_universe
));
2844 tree
= isl_schedule_tree_band_intersect_domain(tree
, domain
);
2846 isl_union_set_free(domain
);
2848 return isl_schedule_tree_free(tree
);
2849 depth
= isl_schedule_node_get_schedule_depth(pos
);
2850 n
= isl_schedule_tree_band_n_member(tree
);
2851 ma
= isl_multi_aff_copy(data
->sched
);
2852 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, depth
);
2853 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, n
, data
->dim
- depth
- n
);
2854 mupa
= isl_multi_union_pw_aff_from_multi_aff(ma
);
2855 partial
= isl_schedule_tree_band_get_partial_schedule(tree
);
2856 has_id
= isl_multi_union_pw_aff_has_tuple_id(partial
, isl_dim_set
);
2858 partial
= isl_multi_union_pw_aff_free(partial
);
2859 } else if (has_id
) {
2861 id
= isl_multi_union_pw_aff_get_tuple_id(partial
, isl_dim_set
);
2862 mupa
= isl_multi_union_pw_aff_set_tuple_id(mupa
,
2865 partial
= isl_multi_union_pw_aff_union_add(partial
, mupa
);
2866 tree
= isl_schedule_tree_band_set_partial_schedule(tree
, partial
);
2871 /* Drop the parameters in "uset" that are not also in "space".
2872 * "n" is the number of parameters in "space".
2874 static __isl_give isl_union_set
*union_set_drop_extra_params(
2875 __isl_take isl_union_set
*uset
, __isl_keep isl_space
*space
, int n
)
2879 uset
= isl_union_set_align_params(uset
, isl_space_copy(space
));
2880 n2
= isl_union_set_dim(uset
, isl_dim_param
);
2882 return isl_union_set_free(uset
);
2883 uset
= isl_union_set_project_out(uset
, isl_dim_param
, n
, n2
- n
);
2888 /* Update the context tree root "tree" to refer to the group instances
2889 * in data->group rather than the original domain elements in data->domain.
2890 * "pos" is the position in the original schedule tree where the modified
2891 * "tree" will be attached.
2893 * We do not actually need to update "tree" since a context node only
2894 * refers to the schedule space. However, we may need to update "data"
2895 * to not refer to any parameters introduced by the context node.
2897 static __isl_give isl_schedule_tree
*group_context(
2898 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2899 struct isl_schedule_group_data
*data
)
2902 isl_union_set
*domain
;
2906 if (isl_schedule_node_get_tree_depth(pos
) == 1)
2909 domain
= isl_schedule_node_get_universe_domain(pos
);
2910 space
= isl_union_set_get_space(domain
);
2911 isl_union_set_free(domain
);
2913 n1
= isl_space_dim(space
, isl_dim_param
);
2914 data
->expansion
= isl_union_map_align_params(data
->expansion
, space
);
2915 n2
= isl_union_map_dim(data
->expansion
, isl_dim_param
);
2917 if (n1
< 0 || n2
< 0)
2918 return isl_schedule_tree_free(tree
);
2922 involves
= isl_union_map_involves_dims(data
->expansion
,
2923 isl_dim_param
, n1
, n2
- n1
);
2925 return isl_schedule_tree_free(tree
);
2927 isl_die(isl_schedule_node_get_ctx(pos
), isl_error_invalid
,
2928 "grouping cannot only refer to global parameters",
2929 return isl_schedule_tree_free(tree
));
2931 data
->expansion
= isl_union_map_project_out(data
->expansion
,
2932 isl_dim_param
, n1
, n2
- n1
);
2933 space
= isl_union_map_get_space(data
->expansion
);
2935 data
->contraction
= isl_union_pw_multi_aff_align_params(
2936 data
->contraction
, isl_space_copy(space
));
2937 n2
= isl_union_pw_multi_aff_dim(data
->contraction
, isl_dim_param
);
2940 isl_union_pw_multi_aff_free(data
->contraction
);
2941 data
->contraction
= isl_union_pw_multi_aff_drop_dims(data
->contraction
,
2942 isl_dim_param
, n1
, n2
- n1
);
2944 data
->domain
= union_set_drop_extra_params(data
->domain
, space
, n1
);
2945 data
->domain_universe
=
2946 union_set_drop_extra_params(data
->domain_universe
, space
, n1
);
2947 data
->group
= union_set_drop_extra_params(data
->group
, space
, n1
);
2948 data
->group_universe
=
2949 union_set_drop_extra_params(data
->group_universe
, space
, n1
);
2951 data
->sched
= isl_multi_aff_align_params(data
->sched
,
2952 isl_space_copy(space
));
2953 n2
= isl_multi_aff_dim(data
->sched
, isl_dim_param
);
2955 data
->sched
= isl_multi_aff_free(data
->sched
);
2956 data
->sched
= isl_multi_aff_drop_dims(data
->sched
,
2957 isl_dim_param
, n1
, n2
- n1
);
2959 isl_space_free(space
);
2964 /* Update the domain tree root "tree" to refer to the group instances
2965 * in data->group rather than the original domain elements in data->domain.
2966 * "pos" is the position in the original schedule tree where the modified
2967 * "tree" will be attached.
2969 * We first double-check that all grouped domain elements are actually
2970 * part of the root domain and then replace those elements by the group
2973 static __isl_give isl_schedule_tree
*group_domain(
2974 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2975 struct isl_schedule_group_data
*data
)
2977 isl_union_set
*domain
;
2980 domain
= isl_schedule_tree_domain_get_domain(tree
);
2981 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2982 isl_union_set_free(domain
);
2984 return isl_schedule_tree_free(tree
);
2986 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2987 "grouped domain should be part of outer domain",
2988 return isl_schedule_tree_free(tree
));
2989 domain
= isl_schedule_tree_domain_get_domain(tree
);
2990 domain
= isl_union_set_subtract(domain
,
2991 isl_union_set_copy(data
->domain
));
2992 domain
= isl_union_set_union(domain
, isl_union_set_copy(data
->group
));
2993 tree
= isl_schedule_tree_domain_set_domain(tree
, domain
);
2998 /* Update the expansion tree root "tree" to refer to the group instances
2999 * in data->group rather than the original domain elements in data->domain.
3000 * "pos" is the position in the original schedule tree where the modified
3001 * "tree" will be attached.
3003 * Let G_1 -> D_1 be the expansion of "tree" and G_2 -> D_2 the newly
3004 * introduced expansion in a descendant of "tree".
3005 * We first double-check that D_2 is a subset of D_1.
3006 * Then we remove D_2 from the range of G_1 -> D_1 and add the mapping
3007 * G_1 -> D_1 . D_2 -> G_2.
3008 * Simmilarly, we restrict the domain of the contraction to the universe
3009 * of the range of the updated expansion and add G_2 -> D_2 . D_1 -> G_1,
3010 * attempting to remove the domain constraints of this additional part.
3012 static __isl_give isl_schedule_tree
*group_expansion(
3013 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
3014 struct isl_schedule_group_data
*data
)
3016 isl_union_set
*domain
;
3017 isl_union_map
*expansion
, *umap
;
3018 isl_union_pw_multi_aff
*contraction
, *upma
;
3021 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
3022 domain
= isl_union_map_range(expansion
);
3023 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
3024 isl_union_set_free(domain
);
3026 return isl_schedule_tree_free(tree
);
3028 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
3029 "grouped domain should be part "
3030 "of outer expansion domain",
3031 return isl_schedule_tree_free(tree
));
3032 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
3033 umap
= isl_union_map_from_union_pw_multi_aff(
3034 isl_union_pw_multi_aff_copy(data
->contraction
));
3035 umap
= isl_union_map_apply_range(expansion
, umap
);
3036 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
3037 expansion
= isl_union_map_subtract_range(expansion
,
3038 isl_union_set_copy(data
->domain
));
3039 expansion
= isl_union_map_union(expansion
, umap
);
3040 umap
= isl_union_map_universe(isl_union_map_copy(expansion
));
3041 domain
= isl_union_map_range(umap
);
3042 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
3043 umap
= isl_union_map_from_union_pw_multi_aff(contraction
);
3044 umap
= isl_union_map_apply_range(isl_union_map_copy(data
->expansion
),
3046 upma
= isl_union_pw_multi_aff_from_union_map(umap
);
3047 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
3048 contraction
= isl_union_pw_multi_aff_intersect_domain(contraction
,
3050 domain
= isl_union_pw_multi_aff_domain(
3051 isl_union_pw_multi_aff_copy(upma
));
3052 upma
= isl_union_pw_multi_aff_gist(upma
, domain
);
3053 contraction
= isl_union_pw_multi_aff_union_add(contraction
, upma
);
3054 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
3055 contraction
, expansion
);
3060 /* Update the tree root "tree" to refer to the group instances
3061 * in data->group rather than the original domain elements in data->domain.
3062 * "pos" is the position in the original schedule tree where the modified
3063 * "tree" will be attached.
3065 * If we have come across a domain or expansion node before (data->finished
3066 * is set), then we no longer need perform any modifications.
3068 * If "tree" is a filter, then we add data->group_universe to the filter.
3069 * We also remove data->domain_universe from the filter if all the domain
3070 * elements in this universe that reach the filter node are part of
3071 * the elements that are being grouped by data->expansion.
3072 * If "tree" is a band, domain or expansion, then it is handled
3073 * in a separate function.
3075 static __isl_give isl_schedule_tree
*group_ancestor(
3076 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
3079 struct isl_schedule_group_data
*data
= user
;
3080 isl_union_set
*domain
;
3081 isl_bool is_covered
;
3084 return isl_schedule_tree_free(tree
);
3089 switch (isl_schedule_tree_get_type(tree
)) {
3090 case isl_schedule_node_error
:
3091 return isl_schedule_tree_free(tree
);
3092 case isl_schedule_node_extension
:
3093 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_unsupported
,
3094 "grouping not allowed in extended tree",
3095 return isl_schedule_tree_free(tree
));
3096 case isl_schedule_node_band
:
3097 tree
= group_band(tree
, pos
, data
);
3099 case isl_schedule_node_context
:
3100 tree
= group_context(tree
, pos
, data
);
3102 case isl_schedule_node_domain
:
3103 tree
= group_domain(tree
, pos
, data
);
3106 case isl_schedule_node_filter
:
3107 domain
= isl_schedule_node_get_domain(pos
);
3108 is_covered
= locally_covered_by_domain(domain
, data
);
3109 isl_union_set_free(domain
);
3111 return isl_schedule_tree_free(tree
);
3112 domain
= isl_schedule_tree_filter_get_filter(tree
);
3114 domain
= isl_union_set_subtract(domain
,
3115 isl_union_set_copy(data
->domain_universe
));
3116 domain
= isl_union_set_union(domain
,
3117 isl_union_set_copy(data
->group_universe
));
3118 tree
= isl_schedule_tree_filter_set_filter(tree
, domain
);
3120 case isl_schedule_node_expansion
:
3121 tree
= group_expansion(tree
, pos
, data
);
3124 case isl_schedule_node_leaf
:
3125 case isl_schedule_node_guard
:
3126 case isl_schedule_node_mark
:
3127 case isl_schedule_node_sequence
:
3128 case isl_schedule_node_set
:
3135 /* Group the domain elements that reach "node" into instances
3136 * of a single statement with identifier "group_id".
3137 * In particular, group the domain elements according to their
3140 * That is, introduce an expansion node with as contraction
3141 * the prefix schedule (with the target space replaced by "group_id")
3142 * and as expansion the inverse of this contraction (with its range
3143 * intersected with the domain elements that reach "node").
3144 * The outer nodes are then modified to refer to the group instances
3145 * instead of the original domain elements.
3147 * No instance of "group_id" is allowed to reach "node" prior
3149 * No ancestor of "node" is allowed to be an extension node.
3151 * Return a pointer to original node in tree, i.e., the child
3152 * of the newly introduced expansion node.
3154 __isl_give isl_schedule_node
*isl_schedule_node_group(
3155 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*group_id
)
3157 struct isl_schedule_group_data data
= { 0 };
3159 isl_union_set
*domain
;
3160 isl_union_pw_multi_aff
*contraction
;
3161 isl_union_map
*expansion
;
3164 if (!node
|| !group_id
)
3166 if (check_insert(node
) < 0)
3169 domain
= isl_schedule_node_get_domain(node
);
3170 data
.domain
= isl_union_set_copy(domain
);
3171 data
.domain_universe
= isl_union_set_copy(domain
);
3172 data
.domain_universe
= isl_union_set_universe(data
.domain_universe
);
3174 data
.dim
= isl_schedule_node_get_schedule_depth(node
);
3175 if (data
.dim
== 0) {
3178 isl_union_set
*group
;
3179 isl_union_map
*univ
;
3181 ctx
= isl_schedule_node_get_ctx(node
);
3182 space
= isl_space_set_alloc(ctx
, 0, 0);
3183 space
= isl_space_set_tuple_id(space
, isl_dim_set
, group_id
);
3184 set
= isl_set_universe(isl_space_copy(space
));
3185 group
= isl_union_set_from_set(set
);
3186 expansion
= isl_union_map_from_domain_and_range(domain
, group
);
3187 univ
= isl_union_map_universe(isl_union_map_copy(expansion
));
3188 contraction
= isl_union_pw_multi_aff_from_union_map(univ
);
3189 expansion
= isl_union_map_reverse(expansion
);
3191 isl_multi_union_pw_aff
*prefix
;
3192 isl_union_set
*univ
;
3195 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node
);
3196 prefix
= isl_multi_union_pw_aff_set_tuple_id(prefix
,
3197 isl_dim_set
, group_id
);
3198 space
= isl_multi_union_pw_aff_get_space(prefix
);
3199 contraction
= isl_union_pw_multi_aff_from_multi_union_pw_aff(
3201 univ
= isl_union_set_universe(isl_union_set_copy(domain
));
3203 isl_union_pw_multi_aff_intersect_domain(contraction
, univ
);
3204 expansion
= isl_union_map_from_union_pw_multi_aff(
3205 isl_union_pw_multi_aff_copy(contraction
));
3206 expansion
= isl_union_map_reverse(expansion
);
3207 expansion
= isl_union_map_intersect_range(expansion
, domain
);
3209 space
= isl_space_map_from_set(space
);
3210 data
.sched
= isl_multi_aff_identity(space
);
3211 data
.group
= isl_union_map_domain(isl_union_map_copy(expansion
));
3212 data
.group
= isl_union_set_coalesce(data
.group
);
3213 data
.group_universe
= isl_union_set_copy(data
.group
);
3214 data
.group_universe
= isl_union_set_universe(data
.group_universe
);
3215 data
.expansion
= isl_union_map_copy(expansion
);
3216 data
.contraction
= isl_union_pw_multi_aff_copy(contraction
);
3217 node
= isl_schedule_node_insert_expansion(node
, contraction
, expansion
);
3219 disjoint
= isl_union_set_is_disjoint(data
.domain_universe
,
3220 data
.group_universe
);
3222 node
= update_ancestors(node
, &group_ancestor
, &data
);
3224 isl_union_set_free(data
.domain
);
3225 isl_union_set_free(data
.domain_universe
);
3226 isl_union_set_free(data
.group
);
3227 isl_union_set_free(data
.group_universe
);
3228 isl_multi_aff_free(data
.sched
);
3229 isl_union_map_free(data
.expansion
);
3230 isl_union_pw_multi_aff_free(data
.contraction
);
3232 node
= isl_schedule_node_child(node
, 0);
3234 if (!node
|| disjoint
< 0)
3235 return isl_schedule_node_free(node
);
3237 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3238 "group instances already reach node",
3239 return isl_schedule_node_free(node
));
3243 isl_schedule_node_free(node
);
3244 isl_id_free(group_id
);
3248 /* Compute the gist of the given band node with respect to "context".
3250 __isl_give isl_schedule_node
*isl_schedule_node_band_gist(
3251 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3253 isl_schedule_tree
*tree
;
3255 tree
= isl_schedule_node_get_tree(node
);
3256 tree
= isl_schedule_tree_band_gist(tree
, context
);
3257 return isl_schedule_node_graft_tree(node
, tree
);
3260 /* Internal data structure for isl_schedule_node_gist.
3261 * "n_expansion" is the number of outer expansion nodes
3262 * with respect to the current position
3263 * "filters" contains an element for each outer filter, expansion or
3264 * extension node with respect to the current position, each representing
3265 * the intersection of the previous element and the filter on the filter node
3266 * or the expansion/extension of the previous element.
3267 * The first element in the original context passed to isl_schedule_node_gist.
3269 struct isl_node_gist_data
{
3271 isl_union_set_list
*filters
;
3274 /* Enter the expansion node "node" during a isl_schedule_node_gist traversal.
3276 * In particular, add an extra element to data->filters containing
3277 * the expansion of the previous element and replace the expansion
3278 * and contraction on "node" by the gist with respect to these filters.
3279 * Also keep track of the fact that we have entered another expansion.
3281 static __isl_give isl_schedule_node
*gist_enter_expansion(
3282 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3285 isl_union_set
*inner
;
3286 isl_union_map
*expansion
;
3287 isl_union_pw_multi_aff
*contraction
;
3289 data
->n_expansion
++;
3291 n
= isl_union_set_list_n_union_set(data
->filters
);
3293 return isl_schedule_node_free(node
);
3294 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3295 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3296 inner
= isl_union_set_apply(inner
, expansion
);
3298 contraction
= isl_schedule_node_expansion_get_contraction(node
);
3299 contraction
= isl_union_pw_multi_aff_gist(contraction
,
3300 isl_union_set_copy(inner
));
3302 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
3304 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3305 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3306 expansion
= isl_union_map_gist_domain(expansion
, inner
);
3307 node
= isl_schedule_node_expansion_set_contraction_and_expansion(node
,
3308 contraction
, expansion
);
3313 /* Leave the expansion node "node" during a isl_schedule_node_gist traversal.
3315 * In particular, remove the element in data->filters that was added by
3316 * gist_enter_expansion and decrement the number of outer expansions.
3318 * The expansion has already been simplified in gist_enter_expansion.
3319 * If this simplification results in an identity expansion, then
3320 * it is removed here.
3322 static __isl_give isl_schedule_node
*gist_leave_expansion(
3323 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3327 isl_union_map
*expansion
;
3329 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3330 identity
= isl_union_map_is_identity(expansion
);
3331 isl_union_map_free(expansion
);
3334 node
= isl_schedule_node_free(node
);
3336 node
= isl_schedule_node_delete(node
);
3338 n
= isl_union_set_list_n_union_set(data
->filters
);
3340 return isl_schedule_node_free(node
);
3341 data
->filters
= isl_union_set_list_drop(data
->filters
, n
- 1, 1);
3343 data
->n_expansion
--;
3348 /* Enter the extension node "node" during a isl_schedule_node_gist traversal.
3350 * In particular, add an extra element to data->filters containing
3351 * the union of the previous element with the additional domain elements
3352 * introduced by the extension.
3354 static __isl_give isl_schedule_node
*gist_enter_extension(
3355 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3358 isl_union_set
*inner
, *extra
;
3359 isl_union_map
*extension
;
3361 n
= isl_union_set_list_n_union_set(data
->filters
);
3363 return isl_schedule_node_free(node
);
3364 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3365 extension
= isl_schedule_node_extension_get_extension(node
);
3366 extra
= isl_union_map_range(extension
);
3367 inner
= isl_union_set_union(inner
, extra
);
3369 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
3374 /* Can we finish gisting at this node?
3375 * That is, is the filter on the current filter node a subset of
3376 * the original context passed to isl_schedule_node_gist?
3377 * If we have gone through any expansions, then we cannot perform
3378 * this test since the current domain elements are incomparable
3379 * to the domain elements in the original context.
3381 static isl_bool
gist_done(__isl_keep isl_schedule_node
*node
,
3382 struct isl_node_gist_data
*data
)
3384 isl_union_set
*filter
, *outer
;
3387 if (data
->n_expansion
!= 0)
3388 return isl_bool_false
;
3390 filter
= isl_schedule_node_filter_get_filter(node
);
3391 outer
= isl_union_set_list_get_union_set(data
->filters
, 0);
3392 subset
= isl_union_set_is_subset(filter
, outer
);
3393 isl_union_set_free(outer
);
3394 isl_union_set_free(filter
);
3399 /* Callback for "traverse" to enter a node and to move
3400 * to the deepest initial subtree that should be traversed
3401 * by isl_schedule_node_gist.
3403 * The "filters" list is extended by one element each time
3404 * we come across a filter node by the result of intersecting
3405 * the last element in the list with the filter on the filter node.
3407 * If the filter on the current filter node is a subset of
3408 * the original context passed to isl_schedule_node_gist,
3409 * then there is no need to go into its subtree since it cannot
3410 * be further simplified by the context. The "filters" list is
3411 * still extended for consistency, but the actual value of the
3412 * added element is immaterial since it will not be used.
3414 * Otherwise, the filter on the current filter node is replaced by
3415 * the gist of the original filter with respect to the intersection
3416 * of the original context with the intermediate filters.
3418 * If the new element in the "filters" list is empty, then no elements
3419 * can reach the descendants of the current filter node. The subtree
3420 * underneath the filter node is therefore removed.
3422 * Each expansion node we come across is handled by
3423 * gist_enter_expansion.
3425 * Each extension node we come across is handled by
3426 * gist_enter_extension.
3428 static __isl_give isl_schedule_node
*gist_enter(
3429 __isl_take isl_schedule_node
*node
, void *user
)
3431 struct isl_node_gist_data
*data
= user
;
3434 isl_union_set
*filter
, *inner
;
3435 isl_bool done
, empty
;
3438 switch (isl_schedule_node_get_type(node
)) {
3439 case isl_schedule_node_error
:
3440 return isl_schedule_node_free(node
);
3441 case isl_schedule_node_expansion
:
3442 node
= gist_enter_expansion(node
, data
);
3444 case isl_schedule_node_extension
:
3445 node
= gist_enter_extension(node
, data
);
3447 case isl_schedule_node_band
:
3448 case isl_schedule_node_context
:
3449 case isl_schedule_node_domain
:
3450 case isl_schedule_node_guard
:
3451 case isl_schedule_node_leaf
:
3452 case isl_schedule_node_mark
:
3453 case isl_schedule_node_sequence
:
3454 case isl_schedule_node_set
:
3456 case isl_schedule_node_filter
:
3459 done
= gist_done(node
, data
);
3460 filter
= isl_schedule_node_filter_get_filter(node
);
3461 n
= isl_union_set_list_n_union_set(data
->filters
);
3462 if (n
< 0 || done
< 0 || done
) {
3463 data
->filters
= isl_union_set_list_add(data
->filters
,
3465 if (n
< 0 || done
< 0)
3466 return isl_schedule_node_free(node
);
3469 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3470 filter
= isl_union_set_gist(filter
, isl_union_set_copy(inner
));
3471 node
= isl_schedule_node_filter_set_filter(node
,
3472 isl_union_set_copy(filter
));
3473 filter
= isl_union_set_intersect(filter
, inner
);
3474 empty
= isl_union_set_is_empty(filter
);
3475 data
->filters
= isl_union_set_list_add(data
->filters
, filter
);
3477 return isl_schedule_node_free(node
);
3480 node
= isl_schedule_node_child(node
, 0);
3481 node
= isl_schedule_node_cut(node
);
3482 node
= isl_schedule_node_parent(node
);
3484 } while (isl_schedule_node_has_children(node
) &&
3485 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3490 /* Callback for "traverse" to leave a node for isl_schedule_node_gist.
3492 * In particular, if the current node is a filter node, then we remove
3493 * the element on the "filters" list that was added when we entered
3494 * the node. There is no need to compute any gist here, since we
3495 * already did that when we entered the node.
3497 * Expansion nodes are handled by gist_leave_expansion.
3499 * If the current node is an extension, then remove the element
3500 * in data->filters that was added by gist_enter_extension.
3502 * If the current node is a band node, then we compute the gist of
3503 * the band node with respect to the intersection of the original context
3504 * and the intermediate filters.
3506 * If the current node is a sequence or set node, then some of
3507 * the filter children may have become empty and so they are removed.
3508 * If only one child is left, then the set or sequence node along with
3509 * the single remaining child filter is removed. The filter can be
3510 * removed because the filters on a sequence or set node are supposed
3511 * to partition the incoming domain instances.
3512 * In principle, it should then be impossible for there to be zero
3513 * remaining children, but should this happen, we replace the entire
3514 * subtree with an empty filter.
3516 static __isl_give isl_schedule_node
*gist_leave(
3517 __isl_take isl_schedule_node
*node
, void *user
)
3519 struct isl_node_gist_data
*data
= user
;
3520 isl_schedule_tree
*tree
;
3523 isl_union_set
*filter
;
3525 switch (isl_schedule_node_get_type(node
)) {
3526 case isl_schedule_node_error
:
3527 return isl_schedule_node_free(node
);
3528 case isl_schedule_node_expansion
:
3529 node
= gist_leave_expansion(node
, data
);
3531 case isl_schedule_node_extension
:
3532 case isl_schedule_node_filter
:
3533 n
= isl_union_set_list_n_union_set(data
->filters
);
3535 return isl_schedule_node_free(node
);
3536 data
->filters
= isl_union_set_list_drop(data
->filters
,
3539 case isl_schedule_node_band
:
3540 n
= isl_union_set_list_n_union_set(data
->filters
);
3542 return isl_schedule_node_free(node
);
3543 filter
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3544 node
= isl_schedule_node_band_gist(node
, filter
);
3546 case isl_schedule_node_set
:
3547 case isl_schedule_node_sequence
:
3548 tree
= isl_schedule_node_get_tree(node
);
3549 n
= isl_schedule_tree_n_children(tree
);
3551 tree
= isl_schedule_tree_free(tree
);
3552 for (i
= n
- 1; i
>= 0; --i
) {
3553 isl_schedule_tree
*child
;
3554 isl_union_set
*filter
;
3557 child
= isl_schedule_tree_get_child(tree
, i
);
3558 filter
= isl_schedule_tree_filter_get_filter(child
);
3559 empty
= isl_union_set_is_empty(filter
);
3560 isl_union_set_free(filter
);
3561 isl_schedule_tree_free(child
);
3563 tree
= isl_schedule_tree_free(tree
);
3565 tree
= isl_schedule_tree_drop_child(tree
, i
);
3567 n
= isl_schedule_tree_n_children(tree
);
3569 tree
= isl_schedule_tree_free(tree
);
3570 node
= isl_schedule_node_graft_tree(node
, tree
);
3572 node
= isl_schedule_node_delete(node
);
3573 node
= isl_schedule_node_delete(node
);
3574 } else if (n
== 0) {
3578 isl_union_set_list_get_union_set(data
->filters
, 0);
3579 space
= isl_union_set_get_space(filter
);
3580 isl_union_set_free(filter
);
3581 filter
= isl_union_set_empty(space
);
3582 node
= isl_schedule_node_cut(node
);
3583 node
= isl_schedule_node_insert_filter(node
, filter
);
3586 case isl_schedule_node_context
:
3587 case isl_schedule_node_domain
:
3588 case isl_schedule_node_guard
:
3589 case isl_schedule_node_leaf
:
3590 case isl_schedule_node_mark
:
3597 /* Compute the gist of the subtree at "node" with respect to
3598 * the reaching domain elements in "context".
3599 * In particular, compute the gist of all band and filter nodes
3600 * in the subtree with respect to "context". Children of set or sequence
3601 * nodes that end up with an empty filter are removed completely.
3603 * We keep track of the intersection of "context" with all outer filters
3604 * of the current node within the subtree in the final element of "filters".
3605 * Initially, this list contains the single element "context" and it is
3606 * extended or shortened each time we enter or leave a filter node.
3608 __isl_give isl_schedule_node
*isl_schedule_node_gist(
3609 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3611 struct isl_node_gist_data data
;
3613 data
.n_expansion
= 0;
3614 data
.filters
= isl_union_set_list_from_union_set(context
);
3615 node
= traverse(node
, &gist_enter
, &gist_leave
, &data
);
3616 isl_union_set_list_free(data
.filters
);
3620 /* Intersect the domain of domain node "node" with "domain".
3622 * If the domain of "node" is already a subset of "domain",
3623 * then nothing needs to be changed.
3625 * Otherwise, we replace the domain of the domain node by the intersection
3626 * and simplify the subtree rooted at "node" with respect to this intersection.
3628 __isl_give isl_schedule_node
*isl_schedule_node_domain_intersect_domain(
3629 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
)
3631 isl_schedule_tree
*tree
;
3632 isl_union_set
*uset
;
3635 if (!node
|| !domain
)
3638 uset
= isl_schedule_tree_domain_get_domain(node
->tree
);
3639 is_subset
= isl_union_set_is_subset(uset
, domain
);
3640 isl_union_set_free(uset
);
3644 isl_union_set_free(domain
);
3648 tree
= isl_schedule_tree_copy(node
->tree
);
3649 uset
= isl_schedule_tree_domain_get_domain(tree
);
3650 uset
= isl_union_set_intersect(uset
, domain
);
3651 tree
= isl_schedule_tree_domain_set_domain(tree
,
3652 isl_union_set_copy(uset
));
3653 node
= isl_schedule_node_graft_tree(node
, tree
);
3655 node
= isl_schedule_node_child(node
, 0);
3656 node
= isl_schedule_node_gist(node
, uset
);
3657 node
= isl_schedule_node_parent(node
);
3661 isl_schedule_node_free(node
);
3662 isl_union_set_free(domain
);
3666 /* Replace the domain of domain node "node" with the gist
3667 * of the original domain with respect to the parameter domain "context".
3669 __isl_give isl_schedule_node
*isl_schedule_node_domain_gist_params(
3670 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
3672 isl_union_set
*domain
;
3673 isl_schedule_tree
*tree
;
3675 if (!node
|| !context
)
3678 tree
= isl_schedule_tree_copy(node
->tree
);
3679 domain
= isl_schedule_tree_domain_get_domain(node
->tree
);
3680 domain
= isl_union_set_gist_params(domain
, context
);
3681 tree
= isl_schedule_tree_domain_set_domain(tree
, domain
);
3682 node
= isl_schedule_node_graft_tree(node
, tree
);
3686 isl_schedule_node_free(node
);
3687 isl_set_free(context
);
3691 /* Internal data structure for isl_schedule_node_get_subtree_expansion.
3692 * "expansions" contains a list of accumulated expansions
3693 * for each outer expansion, set or sequence node. The first element
3694 * in the list is an identity mapping on the reaching domain elements.
3695 * "res" collects the results.
3697 struct isl_subtree_expansion_data
{
3698 isl_union_map_list
*expansions
;
3702 /* Callback for "traverse" to enter a node and to move
3703 * to the deepest initial subtree that should be traversed
3704 * by isl_schedule_node_get_subtree_expansion.
3706 * Whenever we come across an expansion node, the last element
3707 * of data->expansions is combined with the expansion
3708 * on the expansion node.
3710 * Whenever we come across a filter node that is the child
3711 * of a set or sequence node, data->expansions is extended
3712 * with a new element that restricts the previous element
3713 * to the elements selected by the filter.
3714 * The previous element can then be reused while backtracking.
3716 static __isl_give isl_schedule_node
*subtree_expansion_enter(
3717 __isl_take isl_schedule_node
*node
, void *user
)
3719 struct isl_subtree_expansion_data
*data
= user
;
3722 enum isl_schedule_node_type type
;
3723 isl_union_set
*filter
;
3724 isl_union_map
*inner
, *expansion
;
3727 switch (isl_schedule_node_get_type(node
)) {
3728 case isl_schedule_node_error
:
3729 return isl_schedule_node_free(node
);
3730 case isl_schedule_node_filter
:
3731 type
= isl_schedule_node_get_parent_type(node
);
3732 if (type
!= isl_schedule_node_set
&&
3733 type
!= isl_schedule_node_sequence
)
3735 filter
= isl_schedule_node_filter_get_filter(node
);
3736 n
= isl_union_map_list_n_union_map(data
->expansions
);
3739 isl_union_map_list_free(data
->expansions
);
3741 isl_union_map_list_get_union_map(data
->expansions
,
3743 inner
= isl_union_map_intersect_range(inner
, filter
);
3745 isl_union_map_list_add(data
->expansions
, inner
);
3747 case isl_schedule_node_expansion
:
3748 n
= isl_union_map_list_n_union_map(data
->expansions
);
3751 isl_union_map_list_free(data
->expansions
);
3753 isl_schedule_node_expansion_get_expansion(node
);
3755 isl_union_map_list_get_union_map(data
->expansions
,
3757 inner
= isl_union_map_apply_range(inner
, expansion
);
3759 isl_union_map_list_set_union_map(data
->expansions
,
3762 case isl_schedule_node_band
:
3763 case isl_schedule_node_context
:
3764 case isl_schedule_node_domain
:
3765 case isl_schedule_node_extension
:
3766 case isl_schedule_node_guard
:
3767 case isl_schedule_node_leaf
:
3768 case isl_schedule_node_mark
:
3769 case isl_schedule_node_sequence
:
3770 case isl_schedule_node_set
:
3773 } while (isl_schedule_node_has_children(node
) &&
3774 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3779 /* Callback for "traverse" to leave a node for
3780 * isl_schedule_node_get_subtree_expansion.
3782 * If we come across a filter node that is the child
3783 * of a set or sequence node, then we remove the element
3784 * of data->expansions that was added in subtree_expansion_enter.
3786 * If we reach a leaf node, then the accumulated expansion is
3787 * added to data->res.
3789 static __isl_give isl_schedule_node
*subtree_expansion_leave(
3790 __isl_take isl_schedule_node
*node
, void *user
)
3792 struct isl_subtree_expansion_data
*data
= user
;
3794 isl_union_map
*inner
;
3795 enum isl_schedule_node_type type
;
3797 switch (isl_schedule_node_get_type(node
)) {
3798 case isl_schedule_node_error
:
3799 return isl_schedule_node_free(node
);
3800 case isl_schedule_node_filter
:
3801 type
= isl_schedule_node_get_parent_type(node
);
3802 if (type
!= isl_schedule_node_set
&&
3803 type
!= isl_schedule_node_sequence
)
3805 n
= isl_union_map_list_n_union_map(data
->expansions
);
3808 isl_union_map_list_free(data
->expansions
);
3809 data
->expansions
= isl_union_map_list_drop(data
->expansions
,
3812 case isl_schedule_node_leaf
:
3813 n
= isl_union_map_list_n_union_map(data
->expansions
);
3816 isl_union_map_list_free(data
->expansions
);
3817 inner
= isl_union_map_list_get_union_map(data
->expansions
,
3819 data
->res
= isl_union_map_union(data
->res
, inner
);
3821 case isl_schedule_node_band
:
3822 case isl_schedule_node_context
:
3823 case isl_schedule_node_domain
:
3824 case isl_schedule_node_expansion
:
3825 case isl_schedule_node_extension
:
3826 case isl_schedule_node_guard
:
3827 case isl_schedule_node_mark
:
3828 case isl_schedule_node_sequence
:
3829 case isl_schedule_node_set
:
3836 /* Return a mapping from the domain elements that reach "node"
3837 * to the corresponding domain elements in the leaves of the subtree
3838 * rooted at "node" obtained by composing the intermediate expansions.
3840 * We start out with an identity mapping between the domain elements
3841 * that reach "node" and compose it with all the expansions
3842 * on a path from "node" to a leaf while traversing the subtree.
3843 * Within the children of an a sequence or set node, the
3844 * accumulated expansion is restricted to the elements selected
3845 * by the filter child.
3847 __isl_give isl_union_map
*isl_schedule_node_get_subtree_expansion(
3848 __isl_keep isl_schedule_node
*node
)
3850 struct isl_subtree_expansion_data data
;
3852 isl_union_set
*domain
;
3853 isl_union_map
*expansion
;
3858 domain
= isl_schedule_node_get_universe_domain(node
);
3859 space
= isl_union_set_get_space(domain
);
3860 expansion
= isl_union_set_identity(domain
);
3861 data
.res
= isl_union_map_empty(space
);
3862 data
.expansions
= isl_union_map_list_from_union_map(expansion
);
3864 node
= isl_schedule_node_copy(node
);
3865 node
= traverse(node
, &subtree_expansion_enter
,
3866 &subtree_expansion_leave
, &data
);
3868 data
.res
= isl_union_map_free(data
.res
);
3869 isl_schedule_node_free(node
);
3871 isl_union_map_list_free(data
.expansions
);
3876 /* Internal data structure for isl_schedule_node_get_subtree_contraction.
3877 * "contractions" contains a list of accumulated contractions
3878 * for each outer expansion, set or sequence node. The first element
3879 * in the list is an identity mapping on the reaching domain elements.
3880 * "res" collects the results.
3882 struct isl_subtree_contraction_data
{
3883 isl_union_pw_multi_aff_list
*contractions
;
3884 isl_union_pw_multi_aff
*res
;
3887 /* Callback for "traverse" to enter a node and to move
3888 * to the deepest initial subtree that should be traversed
3889 * by isl_schedule_node_get_subtree_contraction.
3891 * Whenever we come across an expansion node, the last element
3892 * of data->contractions is combined with the contraction
3893 * on the expansion node.
3895 * Whenever we come across a filter node that is the child
3896 * of a set or sequence node, data->contractions is extended
3897 * with a new element that restricts the previous element
3898 * to the elements selected by the filter.
3899 * The previous element can then be reused while backtracking.
3901 static __isl_give isl_schedule_node
*subtree_contraction_enter(
3902 __isl_take isl_schedule_node
*node
, void *user
)
3904 struct isl_subtree_contraction_data
*data
= user
;
3907 enum isl_schedule_node_type type
;
3908 isl_union_set
*filter
;
3909 isl_union_pw_multi_aff
*inner
, *contraction
;
3912 switch (isl_schedule_node_get_type(node
)) {
3913 case isl_schedule_node_error
:
3914 return isl_schedule_node_free(node
);
3915 case isl_schedule_node_filter
:
3916 type
= isl_schedule_node_get_parent_type(node
);
3917 if (type
!= isl_schedule_node_set
&&
3918 type
!= isl_schedule_node_sequence
)
3920 filter
= isl_schedule_node_filter_get_filter(node
);
3921 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3922 data
->contractions
);
3924 data
->contractions
=
3925 isl_union_pw_multi_aff_list_free(
3926 data
->contractions
);
3928 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3929 data
->contractions
, n
- 1);
3930 inner
= isl_union_pw_multi_aff_intersect_domain(inner
,
3932 data
->contractions
=
3933 isl_union_pw_multi_aff_list_add(data
->contractions
,
3936 case isl_schedule_node_expansion
:
3937 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3938 data
->contractions
);
3940 data
->contractions
=
3941 isl_union_pw_multi_aff_list_free(
3942 data
->contractions
);
3944 isl_schedule_node_expansion_get_contraction(node
);
3946 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3947 data
->contractions
, n
- 1);
3949 isl_union_pw_multi_aff_pullback_union_pw_multi_aff(
3950 inner
, contraction
);
3951 data
->contractions
=
3952 isl_union_pw_multi_aff_list_set_union_pw_multi_aff(
3953 data
->contractions
, n
- 1, inner
);
3955 case isl_schedule_node_band
:
3956 case isl_schedule_node_context
:
3957 case isl_schedule_node_domain
:
3958 case isl_schedule_node_extension
:
3959 case isl_schedule_node_guard
:
3960 case isl_schedule_node_leaf
:
3961 case isl_schedule_node_mark
:
3962 case isl_schedule_node_sequence
:
3963 case isl_schedule_node_set
:
3966 } while (isl_schedule_node_has_children(node
) &&
3967 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3972 /* Callback for "traverse" to leave a node for
3973 * isl_schedule_node_get_subtree_contraction.
3975 * If we come across a filter node that is the child
3976 * of a set or sequence node, then we remove the element
3977 * of data->contractions that was added in subtree_contraction_enter.
3979 * If we reach a leaf node, then the accumulated contraction is
3980 * added to data->res.
3982 static __isl_give isl_schedule_node
*subtree_contraction_leave(
3983 __isl_take isl_schedule_node
*node
, void *user
)
3985 struct isl_subtree_contraction_data
*data
= user
;
3987 isl_union_pw_multi_aff
*inner
;
3988 enum isl_schedule_node_type type
;
3990 switch (isl_schedule_node_get_type(node
)) {
3991 case isl_schedule_node_error
:
3992 return isl_schedule_node_free(node
);
3993 case isl_schedule_node_filter
:
3994 type
= isl_schedule_node_get_parent_type(node
);
3995 if (type
!= isl_schedule_node_set
&&
3996 type
!= isl_schedule_node_sequence
)
3998 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3999 data
->contractions
);
4001 data
->contractions
= isl_union_pw_multi_aff_list_free(
4002 data
->contractions
);
4003 data
->contractions
=
4004 isl_union_pw_multi_aff_list_drop(data
->contractions
,
4007 case isl_schedule_node_leaf
:
4008 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
4009 data
->contractions
);
4011 data
->contractions
= isl_union_pw_multi_aff_list_free(
4012 data
->contractions
);
4013 inner
= isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
4014 data
->contractions
, n
- 1);
4015 data
->res
= isl_union_pw_multi_aff_union_add(data
->res
, inner
);
4017 case isl_schedule_node_band
:
4018 case isl_schedule_node_context
:
4019 case isl_schedule_node_domain
:
4020 case isl_schedule_node_expansion
:
4021 case isl_schedule_node_extension
:
4022 case isl_schedule_node_guard
:
4023 case isl_schedule_node_mark
:
4024 case isl_schedule_node_sequence
:
4025 case isl_schedule_node_set
:
4032 /* Return a mapping from the domain elements in the leaves of the subtree
4033 * rooted at "node" to the corresponding domain elements that reach "node"
4034 * obtained by composing the intermediate contractions.
4036 * We start out with an identity mapping between the domain elements
4037 * that reach "node" and compose it with all the contractions
4038 * on a path from "node" to a leaf while traversing the subtree.
4039 * Within the children of an a sequence or set node, the
4040 * accumulated contraction is restricted to the elements selected
4041 * by the filter child.
4043 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_get_subtree_contraction(
4044 __isl_keep isl_schedule_node
*node
)
4046 struct isl_subtree_contraction_data data
;
4048 isl_union_set
*domain
;
4049 isl_union_pw_multi_aff
*contraction
;
4054 domain
= isl_schedule_node_get_universe_domain(node
);
4055 space
= isl_union_set_get_space(domain
);
4056 contraction
= isl_union_set_identity_union_pw_multi_aff(domain
);
4057 data
.res
= isl_union_pw_multi_aff_empty(space
);
4059 isl_union_pw_multi_aff_list_from_union_pw_multi_aff(contraction
);
4061 node
= isl_schedule_node_copy(node
);
4062 node
= traverse(node
, &subtree_contraction_enter
,
4063 &subtree_contraction_leave
, &data
);
4065 data
.res
= isl_union_pw_multi_aff_free(data
.res
);
4066 isl_schedule_node_free(node
);
4068 isl_union_pw_multi_aff_list_free(data
.contractions
);
4073 /* Do the nearest "n" ancestors of "node" have the types given in "types"
4074 * (starting at the parent of "node")?
4076 static isl_bool
has_ancestors(__isl_keep isl_schedule_node
*node
,
4077 int n
, enum isl_schedule_node_type
*types
)
4080 isl_size n_ancestor
;
4083 return isl_bool_error
;
4085 n_ancestor
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
4087 return isl_bool_error
;
4089 return isl_bool_false
;
4091 for (i
= 0; i
< n
; ++i
) {
4092 isl_schedule_tree
*tree
;
4095 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
4096 n_ancestor
- 1 - i
);
4098 return isl_bool_error
;
4099 correct_type
= isl_schedule_tree_get_type(tree
) == types
[i
];
4100 isl_schedule_tree_free(tree
);
4102 return isl_bool_false
;
4105 return isl_bool_true
;
4108 /* Given a node "node" that appears in an extension (i.e., it is the child
4109 * of a filter in a sequence inside an extension node), are the spaces
4110 * of the extension specified by "extension" disjoint from those
4111 * of both the original extension and the domain elements that reach
4112 * that original extension?
4114 static int is_disjoint_extension(__isl_keep isl_schedule_node
*node
,
4115 __isl_keep isl_union_map
*extension
)
4118 isl_union_set
*domain
;
4121 node
= isl_schedule_node_copy(node
);
4122 node
= isl_schedule_node_parent(node
);
4123 node
= isl_schedule_node_parent(node
);
4124 node
= isl_schedule_node_parent(node
);
4125 old
= isl_schedule_node_extension_get_extension(node
);
4126 domain
= isl_schedule_node_get_universe_domain(node
);
4127 isl_schedule_node_free(node
);
4128 old
= isl_union_map_universe(old
);
4129 domain
= isl_union_set_union(domain
, isl_union_map_range(old
));
4130 extension
= isl_union_map_copy(extension
);
4131 extension
= isl_union_map_intersect_range(extension
, domain
);
4132 empty
= isl_union_map_is_empty(extension
);
4133 isl_union_map_free(extension
);
4138 /* Given a node "node" that is governed by an extension node, extend
4139 * that extension node with "extension".
4141 * In particular, "node" is the child of a filter in a sequence that
4142 * is in turn a child of an extension node. Extend that extension node
4145 * Return a pointer to the parent of the original node (i.e., a filter).
4147 static __isl_give isl_schedule_node
*extend_extension(
4148 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
4152 isl_union_map
*node_extension
;
4154 node
= isl_schedule_node_parent(node
);
4155 pos
= isl_schedule_node_get_child_position(node
);
4156 node
= isl_schedule_node_parent(node
);
4157 node
= isl_schedule_node_parent(node
);
4158 node_extension
= isl_schedule_node_extension_get_extension(node
);
4159 disjoint
= isl_union_map_is_disjoint(extension
, node_extension
);
4160 extension
= isl_union_map_union(extension
, node_extension
);
4161 node
= isl_schedule_node_extension_set_extension(node
, extension
);
4162 node
= isl_schedule_node_child(node
, 0);
4163 node
= isl_schedule_node_child(node
, pos
);
4166 return isl_schedule_node_free(node
);
4170 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4171 "extension domain should be disjoint from earlier "
4172 "extensions", return isl_schedule_node_free(node
));
4177 /* Return the universe of "uset" if this universe is disjoint from "ref".
4178 * Otherwise, return "uset".
4180 * Also check if "uset" itself is disjoint from "ref", reporting
4181 * an error if it is not.
4183 static __isl_give isl_union_set
*replace_by_universe_if_disjoint(
4184 __isl_take isl_union_set
*uset
, __isl_keep isl_union_set
*ref
)
4187 isl_union_set
*universe
;
4189 disjoint
= isl_union_set_is_disjoint(uset
, ref
);
4191 return isl_union_set_free(uset
);
4193 isl_die(isl_union_set_get_ctx(uset
), isl_error_invalid
,
4194 "extension domain should be disjoint from "
4195 "current domain", return isl_union_set_free(uset
));
4197 universe
= isl_union_set_universe(isl_union_set_copy(uset
));
4198 disjoint
= isl_union_set_is_disjoint(universe
, ref
);
4199 if (disjoint
>= 0 && disjoint
) {
4200 isl_union_set_free(uset
);
4203 isl_union_set_free(universe
);
4206 return isl_union_set_free(uset
);
4210 /* Insert an extension node on top of "node" with extension "extension".
4211 * In addition, insert a filter that separates node from the extension
4212 * between the extension node and "node".
4213 * Return a pointer to the inserted filter node.
4215 * If "node" already appears in an extension (i.e., if it is the child
4216 * of a filter in a sequence inside an extension node), then extend that
4217 * extension with "extension" instead.
4218 * In this case, a pointer to the original filter node is returned.
4219 * Note that if some of the elements in the new extension live in the
4220 * same space as those of the original extension or the domain elements
4221 * reaching the original extension, then we insert a new extension anyway.
4222 * Otherwise, we would have to adjust the filters in the sequence child
4223 * of the extension to ensure that the elements in the new extension
4226 static __isl_give isl_schedule_node
*insert_extension(
4227 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
4229 enum isl_schedule_node_type ancestors
[] =
4230 { isl_schedule_node_filter
, isl_schedule_node_sequence
,
4231 isl_schedule_node_extension
};
4232 isl_union_set
*domain
;
4233 isl_union_set
*filter
;
4236 in_ext
= has_ancestors(node
, 3, ancestors
);
4242 disjoint
= is_disjoint_extension(node
, extension
);
4246 return extend_extension(node
, extension
);
4249 filter
= isl_schedule_node_get_domain(node
);
4250 domain
= isl_union_map_range(isl_union_map_copy(extension
));
4251 filter
= replace_by_universe_if_disjoint(filter
, domain
);
4252 isl_union_set_free(domain
);
4254 node
= isl_schedule_node_insert_filter(node
, filter
);
4255 node
= isl_schedule_node_insert_extension(node
, extension
);
4256 node
= isl_schedule_node_child(node
, 0);
4259 isl_schedule_node_free(node
);
4260 isl_union_map_free(extension
);
4264 /* Replace the subtree that "node" points to by "tree" (which has
4265 * a sequence root with two children), except if the parent of "node"
4266 * is a sequence as well, in which case "tree" is spliced at the position
4267 * of "node" in its parent.
4268 * Return a pointer to the child of the "tree_pos" (filter) child of "tree"
4269 * in the updated schedule tree.
4271 static __isl_give isl_schedule_node
*graft_or_splice(
4272 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_tree
*tree
,
4277 if (isl_schedule_node_get_parent_type(node
) ==
4278 isl_schedule_node_sequence
) {
4279 pos
= isl_schedule_node_get_child_position(node
);
4280 node
= isl_schedule_node_parent(node
);
4281 node
= isl_schedule_node_sequence_splice(node
, pos
, tree
);
4284 node
= isl_schedule_node_graft_tree(node
, tree
);
4286 node
= isl_schedule_node_child(node
, pos
+ tree_pos
);
4287 node
= isl_schedule_node_child(node
, 0);
4292 /* Insert a node "graft" into the schedule tree of "node" such that it
4293 * is executed before (if "before" is set) or after (if "before" is not set)
4294 * the node that "node" points to.
4295 * The root of "graft" is an extension node.
4296 * Return a pointer to the node that "node" pointed to.
4298 * We first insert an extension node on top of "node" (or extend
4299 * the extension node if there already is one), with a filter on "node"
4300 * separating it from the extension.
4301 * We then insert a filter in the graft to separate it from the original
4302 * domain elements and combine the original and new tree in a sequence.
4303 * If we have extended an extension node, then the children of this
4304 * sequence are spliced in the sequence of the extended extension
4305 * at the position where "node" appears in the original extension.
4306 * Otherwise, the sequence pair is attached to the new extension node.
4308 static __isl_give isl_schedule_node
*graft_extension(
4309 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
,
4312 isl_union_map
*extension
;
4313 isl_union_set
*graft_domain
;
4314 isl_union_set
*node_domain
;
4315 isl_schedule_tree
*tree
, *tree_graft
;
4317 extension
= isl_schedule_node_extension_get_extension(graft
);
4318 graft_domain
= isl_union_map_range(isl_union_map_copy(extension
));
4319 node_domain
= isl_schedule_node_get_universe_domain(node
);
4320 node
= insert_extension(node
, extension
);
4322 graft_domain
= replace_by_universe_if_disjoint(graft_domain
,
4324 isl_union_set_free(node_domain
);
4326 tree
= isl_schedule_node_get_tree(node
);
4327 if (!isl_schedule_node_has_children(graft
)) {
4328 tree_graft
= isl_schedule_tree_from_filter(graft_domain
);
4330 graft
= isl_schedule_node_child(graft
, 0);
4331 tree_graft
= isl_schedule_node_get_tree(graft
);
4332 tree_graft
= isl_schedule_tree_insert_filter(tree_graft
,
4336 tree
= isl_schedule_tree_sequence_pair(tree_graft
, tree
);
4338 tree
= isl_schedule_tree_sequence_pair(tree
, tree_graft
);
4339 node
= graft_or_splice(node
, tree
, before
);
4341 isl_schedule_node_free(graft
);
4346 /* Replace the root domain node of "node" by an extension node suitable
4347 * for insertion at "pos".
4348 * That is, create an extension node that maps the outer band nodes
4349 * at "pos" to the domain of the root node of "node" and attach
4350 * the child of this root node to the extension node.
4352 static __isl_give isl_schedule_node
*extension_from_domain(
4353 __isl_take isl_schedule_node
*node
, __isl_keep isl_schedule_node
*pos
)
4355 isl_union_set
*universe
;
4356 isl_union_set
*domain
;
4361 isl_schedule_node
*res
;
4362 isl_schedule_tree
*tree
;
4364 anchored
= isl_schedule_node_is_subtree_anchored(node
);
4366 return isl_schedule_node_free(node
);
4368 isl_die(isl_schedule_node_get_ctx(node
), isl_error_unsupported
,
4369 "cannot graft anchored tree with domain root",
4370 return isl_schedule_node_free(node
));
4372 depth
= isl_schedule_node_get_schedule_depth(pos
);
4373 domain
= isl_schedule_node_domain_get_domain(node
);
4374 space
= isl_union_set_get_space(domain
);
4375 space
= isl_space_set_from_params(space
);
4376 space
= isl_space_add_dims(space
, isl_dim_set
, depth
);
4377 universe
= isl_union_set_from_set(isl_set_universe(space
));
4378 ext
= isl_union_map_from_domain_and_range(universe
, domain
);
4379 res
= isl_schedule_node_from_extension(ext
);
4380 node
= isl_schedule_node_child(node
, 0);
4382 return isl_schedule_node_free(res
);
4383 if (!isl_schedule_tree_is_leaf(node
->tree
)) {
4384 tree
= isl_schedule_node_get_tree(node
);
4385 res
= isl_schedule_node_child(res
, 0);
4386 res
= isl_schedule_node_graft_tree(res
, tree
);
4387 res
= isl_schedule_node_parent(res
);
4389 isl_schedule_node_free(node
);
4394 /* Insert a node "graft" into the schedule tree of "node" such that it
4395 * is executed before (if "before" is set) or after (if "before" is not set)
4396 * the node that "node" points to.
4397 * The root of "graft" may be either a domain or an extension node.
4398 * In the latter case, the domain of the extension needs to correspond
4399 * to the outer band nodes of "node".
4400 * The elements of the domain or the range of the extension may not
4401 * intersect with the domain elements that reach "node".
4402 * The schedule tree of "graft" may not be anchored.
4404 * The schedule tree of "node" is modified to include an extension node
4405 * corresponding to the root node of "graft" as a child of the original
4406 * parent of "node". The original node that "node" points to and the
4407 * child of the root node of "graft" are attached to this extension node
4408 * through a sequence, with appropriate filters and with the child
4409 * of "graft" appearing before or after the original "node".
4411 * If "node" already appears inside a sequence that is the child of
4412 * an extension node and if the spaces of the new domain elements
4413 * do not overlap with those of the original domain elements,
4414 * then that extension node is extended with the new extension
4415 * rather than introducing a new segment of extension and sequence nodes.
4417 * Return a pointer to the same node in the modified tree that
4418 * "node" pointed to in the original tree.
4420 static __isl_give isl_schedule_node
*isl_schedule_node_graft_before_or_after(
4421 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
,
4424 if (!node
|| !graft
)
4426 if (check_insert(node
) < 0)
4429 if (isl_schedule_node_get_type(graft
) == isl_schedule_node_domain
)
4430 graft
= extension_from_domain(graft
, node
);
4434 if (isl_schedule_node_get_type(graft
) != isl_schedule_node_extension
)
4435 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4436 "expecting domain or extension as root of graft",
4439 return graft_extension(node
, graft
, before
);
4441 isl_schedule_node_free(node
);
4442 isl_schedule_node_free(graft
);
4446 /* Insert a node "graft" into the schedule tree of "node" such that it
4447 * is executed before the node that "node" points to.
4448 * The root of "graft" may be either a domain or an extension node.
4449 * In the latter case, the domain of the extension needs to correspond
4450 * to the outer band nodes of "node".
4451 * The elements of the domain or the range of the extension may not
4452 * intersect with the domain elements that reach "node".
4453 * The schedule tree of "graft" may not be anchored.
4455 * Return a pointer to the same node in the modified tree that
4456 * "node" pointed to in the original tree.
4458 __isl_give isl_schedule_node
*isl_schedule_node_graft_before(
4459 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
)
4461 return isl_schedule_node_graft_before_or_after(node
, graft
, 1);
4464 /* Insert a node "graft" into the schedule tree of "node" such that it
4465 * is executed after the node that "node" points to.
4466 * The root of "graft" may be either a domain or an extension node.
4467 * In the latter case, the domain of the extension needs to correspond
4468 * to the outer band nodes of "node".
4469 * The elements of the domain or the range of the extension may not
4470 * intersect with the domain elements that reach "node".
4471 * The schedule tree of "graft" may not be anchored.
4473 * Return a pointer to the same node in the modified tree that
4474 * "node" pointed to in the original tree.
4476 __isl_give isl_schedule_node
*isl_schedule_node_graft_after(
4477 __isl_take isl_schedule_node
*node
,
4478 __isl_take isl_schedule_node
*graft
)
4480 return isl_schedule_node_graft_before_or_after(node
, graft
, 0);
4483 /* Split the domain elements that reach "node" into those that satisfy
4484 * "filter" and those that do not. Arrange for the first subset to be
4485 * executed before or after the second subset, depending on the value
4487 * Return a pointer to the tree corresponding to the second subset,
4488 * except when this subset is empty in which case the original pointer
4490 * If both subsets are non-empty, then a sequence node is introduced
4491 * to impose the order. If the grandparent of the original node was
4492 * itself a sequence, then the original child is replaced by two children
4493 * in this sequence instead.
4494 * The children in the sequence are copies of the original subtree,
4495 * simplified with respect to their filters.
4497 static __isl_give isl_schedule_node
*isl_schedule_node_order_before_or_after(
4498 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
,
4501 enum isl_schedule_node_type ancestors
[] =
4502 { isl_schedule_node_filter
, isl_schedule_node_sequence
};
4503 isl_union_set
*node_domain
, *node_filter
= NULL
, *parent_filter
;
4504 isl_schedule_node
*node2
;
4505 isl_schedule_tree
*tree1
, *tree2
;
4506 isl_bool empty1
, empty2
;
4509 if (!node
|| !filter
)
4511 if (check_insert(node
) < 0)
4514 in_seq
= has_ancestors(node
, 2, ancestors
);
4517 node_domain
= isl_schedule_node_get_domain(node
);
4518 filter
= isl_union_set_gist(filter
, isl_union_set_copy(node_domain
));
4519 node_filter
= isl_union_set_copy(node_domain
);
4520 node_filter
= isl_union_set_subtract(node_filter
,
4521 isl_union_set_copy(filter
));
4522 node_filter
= isl_union_set_gist(node_filter
, node_domain
);
4523 empty1
= isl_union_set_is_empty(filter
);
4524 empty2
= isl_union_set_is_empty(node_filter
);
4525 if (empty1
< 0 || empty2
< 0)
4527 if (empty1
|| empty2
) {
4528 isl_union_set_free(filter
);
4529 isl_union_set_free(node_filter
);
4534 node
= isl_schedule_node_parent(node
);
4535 parent_filter
= isl_schedule_node_filter_get_filter(node
);
4536 node_filter
= isl_union_set_intersect(node_filter
,
4537 isl_union_set_copy(parent_filter
));
4538 filter
= isl_union_set_intersect(filter
, parent_filter
);
4541 node2
= isl_schedule_node_copy(node
);
4542 node
= isl_schedule_node_gist(node
, isl_union_set_copy(node_filter
));
4543 node2
= isl_schedule_node_gist(node2
, isl_union_set_copy(filter
));
4544 tree1
= isl_schedule_node_get_tree(node
);
4545 tree2
= isl_schedule_node_get_tree(node2
);
4546 tree1
= isl_schedule_tree_insert_filter(tree1
, node_filter
);
4547 tree2
= isl_schedule_tree_insert_filter(tree2
, filter
);
4548 isl_schedule_node_free(node2
);
4551 tree1
= isl_schedule_tree_sequence_pair(tree2
, tree1
);
4552 node
= graft_or_splice(node
, tree1
, 1);
4554 tree1
= isl_schedule_tree_sequence_pair(tree1
, tree2
);
4555 node
= graft_or_splice(node
, tree1
, 0);
4560 isl_schedule_node_free(node
);
4561 isl_union_set_free(filter
);
4562 isl_union_set_free(node_filter
);
4566 /* Split the domain elements that reach "node" into those that satisfy
4567 * "filter" and those that do not. Arrange for the first subset to be
4568 * executed before the second subset.
4569 * Return a pointer to the tree corresponding to the second subset,
4570 * except when this subset is empty in which case the original pointer
4573 __isl_give isl_schedule_node
*isl_schedule_node_order_before(
4574 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
4576 return isl_schedule_node_order_before_or_after(node
, filter
, 1);
4579 /* Split the domain elements that reach "node" into those that satisfy
4580 * "filter" and those that do not. Arrange for the first subset to be
4581 * executed after the second subset.
4582 * Return a pointer to the tree corresponding to the second subset,
4583 * except when this subset is empty in which case the original pointer
4586 __isl_give isl_schedule_node
*isl_schedule_node_order_after(
4587 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
4589 return isl_schedule_node_order_before_or_after(node
, filter
, 0);
4592 /* Reset the user pointer on all identifiers of parameters and tuples
4593 * in the schedule node "node".
4595 __isl_give isl_schedule_node
*isl_schedule_node_reset_user(
4596 __isl_take isl_schedule_node
*node
)
4598 isl_schedule_tree
*tree
;
4600 tree
= isl_schedule_node_get_tree(node
);
4601 tree
= isl_schedule_tree_reset_user(tree
);
4602 node
= isl_schedule_node_graft_tree(node
, tree
);
4607 /* Align the parameters of the schedule node "node" to those of "space".
4609 __isl_give isl_schedule_node
*isl_schedule_node_align_params(
4610 __isl_take isl_schedule_node
*node
, __isl_take isl_space
*space
)
4612 isl_schedule_tree
*tree
;
4614 tree
= isl_schedule_node_get_tree(node
);
4615 tree
= isl_schedule_tree_align_params(tree
, space
);
4616 node
= isl_schedule_node_graft_tree(node
, tree
);
4621 /* Compute the pullback of schedule node "node"
4622 * by the function represented by "upma".
4623 * In other words, plug in "upma" in the iteration domains
4624 * of schedule node "node".
4625 * We currently do not handle expansion nodes.
4627 * Note that this is only a helper function for
4628 * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency,
4629 * this function should not be called on a single node without also
4630 * calling it on all the other nodes.
4632 __isl_give isl_schedule_node
*isl_schedule_node_pullback_union_pw_multi_aff(
4633 __isl_take isl_schedule_node
*node
,
4634 __isl_take isl_union_pw_multi_aff
*upma
)
4636 isl_schedule_tree
*tree
;
4638 tree
= isl_schedule_node_get_tree(node
);
4639 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, upma
);
4640 node
= isl_schedule_node_graft_tree(node
, tree
);
4645 /* Internal data structure for isl_schedule_node_expand.
4646 * "tree" is the tree that needs to be plugged in in all the leaves.
4647 * "domain" is the set of domain elements in the original leaves
4648 * to which the tree applies.
4650 struct isl_schedule_expand_data
{
4651 isl_schedule_tree
*tree
;
4652 isl_union_set
*domain
;
4655 /* If "node" is a leaf, then plug in data->tree, simplifying it
4656 * within its new context.
4658 * If there are any domain elements at the leaf where the tree
4659 * should not be plugged in (i.e., there are elements not in data->domain)
4660 * then first extend the tree to only apply to the elements in data->domain
4661 * by constructing a set node that selects data->tree for elements
4662 * in data->domain and a leaf for the other elements.
4664 static __isl_give isl_schedule_node
*expand(__isl_take isl_schedule_node
*node
,
4667 struct isl_schedule_expand_data
*data
= user
;
4668 isl_schedule_tree
*tree
, *leaf
;
4669 isl_union_set
*domain
, *left
;
4672 if (isl_schedule_node_get_type(node
) != isl_schedule_node_leaf
)
4675 domain
= isl_schedule_node_get_domain(node
);
4676 tree
= isl_schedule_tree_copy(data
->tree
);
4678 left
= isl_union_set_copy(domain
);
4679 left
= isl_union_set_subtract(left
, isl_union_set_copy(data
->domain
));
4680 empty
= isl_union_set_is_empty(left
);
4681 if (empty
>= 0 && !empty
) {
4682 leaf
= isl_schedule_node_get_leaf(node
);
4683 leaf
= isl_schedule_tree_insert_filter(leaf
, left
);
4684 left
= isl_union_set_copy(data
->domain
);
4685 tree
= isl_schedule_tree_insert_filter(tree
, left
);
4686 tree
= isl_schedule_tree_set_pair(tree
, leaf
);
4689 node
= isl_schedule_node_free(node
);
4690 isl_union_set_free(left
);
4693 node
= isl_schedule_node_graft_tree(node
, tree
);
4694 node
= isl_schedule_node_gist(node
, domain
);
4699 /* Expand the tree rooted at "node" by extending all leaves
4700 * with an expansion node with as child "tree".
4701 * The expansion is determined by "contraction" and "domain".
4702 * That is, the elements of "domain" are contracted according
4703 * to "contraction". The expansion relation is then the inverse
4704 * of "contraction" with its range intersected with "domain".
4706 * Insert the appropriate expansion node on top of "tree" and
4707 * then plug in the result in all leaves of "node".
4709 __isl_give isl_schedule_node
*isl_schedule_node_expand(
4710 __isl_take isl_schedule_node
*node
,
4711 __isl_take isl_union_pw_multi_aff
*contraction
,
4712 __isl_take isl_union_set
*domain
,
4713 __isl_take isl_schedule_tree
*tree
)
4715 struct isl_schedule_expand_data data
;
4716 isl_union_map
*expansion
;
4717 isl_union_pw_multi_aff
*copy
;
4719 if (!node
|| !contraction
|| !tree
)
4720 node
= isl_schedule_node_free(node
);
4722 copy
= isl_union_pw_multi_aff_copy(contraction
);
4723 expansion
= isl_union_map_from_union_pw_multi_aff(copy
);
4724 expansion
= isl_union_map_reverse(expansion
);
4725 expansion
= isl_union_map_intersect_range(expansion
, domain
);
4726 data
.domain
= isl_union_map_domain(isl_union_map_copy(expansion
));
4728 tree
= isl_schedule_tree_insert_expansion(tree
, contraction
, expansion
);
4731 node
= isl_schedule_node_map_descendant_bottom_up(node
, &expand
, &data
);
4732 isl_union_set_free(data
.domain
);
4733 isl_schedule_tree_free(data
.tree
);
4737 /* Return the position of the subtree containing "node" among the children
4738 * of "ancestor". "node" is assumed to be a descendant of "ancestor".
4739 * In particular, both nodes should point to the same schedule tree.
4741 * Return -1 on error.
4743 int isl_schedule_node_get_ancestor_child_position(
4744 __isl_keep isl_schedule_node
*node
,
4745 __isl_keep isl_schedule_node
*ancestor
)
4748 isl_schedule_tree
*tree
;
4750 if (!node
|| !ancestor
)
4753 if (node
->schedule
!= ancestor
->schedule
)
4754 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4755 "not a descendant", return -1);
4757 n1
= isl_schedule_node_get_tree_depth(ancestor
);
4758 n2
= isl_schedule_node_get_tree_depth(node
);
4761 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4762 "not a descendant", return -1);
4763 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n1
);
4764 isl_schedule_tree_free(tree
);
4765 if (tree
!= ancestor
->tree
)
4766 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4767 "not a descendant", return -1);
4769 return node
->child_pos
[n1
];
4772 /* Given two nodes that point to the same schedule tree, return their
4773 * closest shared ancestor.
4775 * Since the two nodes point to the same schedule, they share at least
4776 * one ancestor, the root of the schedule. We move down from the root
4777 * to the first ancestor where the respective children have a different
4778 * child position. This is the requested ancestor.
4779 * If there is no ancestor where the children have a different position,
4780 * then one node is an ancestor of the other and then this node is
4781 * the requested ancestor.
4783 __isl_give isl_schedule_node
*isl_schedule_node_get_shared_ancestor(
4784 __isl_keep isl_schedule_node
*node1
,
4785 __isl_keep isl_schedule_node
*node2
)
4789 if (!node1
|| !node2
)
4791 if (node1
->schedule
!= node2
->schedule
)
4792 isl_die(isl_schedule_node_get_ctx(node1
), isl_error_invalid
,
4793 "not part of same schedule", return NULL
);
4794 n1
= isl_schedule_node_get_tree_depth(node1
);
4795 n2
= isl_schedule_node_get_tree_depth(node2
);
4797 return isl_schedule_node_get_shared_ancestor(node2
, node1
);
4799 return isl_schedule_node_copy(node1
);
4800 if (isl_schedule_node_is_equal(node1
, node2
))
4801 return isl_schedule_node_copy(node1
);
4803 for (i
= 0; i
< n1
; ++i
)
4804 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
4807 node1
= isl_schedule_node_copy(node1
);
4808 return isl_schedule_node_ancestor(node1
, n1
- i
);
4811 /* Print "node" to "p".
4813 __isl_give isl_printer
*isl_printer_print_schedule_node(
4814 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
4819 return isl_printer_free(p
);
4820 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
4822 return isl_printer_free(p
);
4823 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
, n
,
4827 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
4830 isl_printer
*printer
;
4835 ctx
= isl_schedule_node_get_ctx(node
);
4836 printer
= isl_printer_to_file(ctx
, stderr
);
4837 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
4838 printer
= isl_printer_print_schedule_node(printer
, node
);
4840 isl_printer_free(printer
);
4843 /* Return a string representation of "node".
4844 * Print the schedule node in block format as it would otherwise
4845 * look identical to the entire schedule.
4847 __isl_give
char *isl_schedule_node_to_str(__isl_keep isl_schedule_node
*node
)
4849 isl_printer
*printer
;
4855 printer
= isl_printer_to_str(isl_schedule_node_get_ctx(node
));
4856 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
4857 printer
= isl_printer_print_schedule_node(printer
, node
);
4858 s
= isl_printer_get_str(printer
);
4859 isl_printer_free(printer
);