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
;
34 if (!schedule
|| !tree
|| !ancestors
)
36 n
= isl_schedule_tree_list_n_schedule_tree(ancestors
);
37 if (n
> 0 && !child_pos
)
39 ctx
= isl_schedule_get_ctx(schedule
);
40 node
= isl_calloc_type(ctx
, isl_schedule_node
);
44 node
->schedule
= schedule
;
46 node
->ancestors
= ancestors
;
47 node
->child_pos
= isl_alloc_array(ctx
, int, n
);
48 if (n
&& !node
->child_pos
)
49 return isl_schedule_node_free(node
);
50 for (i
= 0; i
< n
; ++i
)
51 node
->child_pos
[i
] = child_pos
[i
];
55 isl_schedule_free(schedule
);
56 isl_schedule_tree_free(tree
);
57 isl_schedule_tree_list_free(ancestors
);
61 /* Return a pointer to the root of a schedule tree with as single
62 * node a domain node with the given domain.
64 __isl_give isl_schedule_node
*isl_schedule_node_from_domain(
65 __isl_take isl_union_set
*domain
)
67 isl_schedule
*schedule
;
68 isl_schedule_node
*node
;
70 schedule
= isl_schedule_from_domain(domain
);
71 node
= isl_schedule_get_root(schedule
);
72 isl_schedule_free(schedule
);
77 /* Return a pointer to the root of a schedule tree with as single
78 * node a extension node with the given extension.
80 __isl_give isl_schedule_node
*isl_schedule_node_from_extension(
81 __isl_take isl_union_map
*extension
)
84 isl_schedule
*schedule
;
85 isl_schedule_tree
*tree
;
86 isl_schedule_node
*node
;
91 ctx
= isl_union_map_get_ctx(extension
);
92 tree
= isl_schedule_tree_from_extension(extension
);
93 schedule
= isl_schedule_from_schedule_tree(ctx
, tree
);
94 node
= isl_schedule_get_root(schedule
);
95 isl_schedule_free(schedule
);
100 /* Return the isl_ctx to which "node" belongs.
102 isl_ctx
*isl_schedule_node_get_ctx(__isl_keep isl_schedule_node
*node
)
104 return node
? isl_schedule_get_ctx(node
->schedule
) : NULL
;
107 /* Return a pointer to the leaf of the schedule into which "node" points.
109 __isl_keep isl_schedule_tree
*isl_schedule_node_peek_leaf(
110 __isl_keep isl_schedule_node
*node
)
112 return node
? isl_schedule_peek_leaf(node
->schedule
) : NULL
;
115 /* Return a copy of the leaf of the schedule into which "node" points.
117 __isl_give isl_schedule_tree
*isl_schedule_node_get_leaf(
118 __isl_keep isl_schedule_node
*node
)
120 return isl_schedule_tree_copy(isl_schedule_node_peek_leaf(node
));
123 /* Return the type of the node or isl_schedule_node_error on error.
125 enum isl_schedule_node_type
isl_schedule_node_get_type(
126 __isl_keep isl_schedule_node
*node
)
128 return node
? isl_schedule_tree_get_type(node
->tree
)
129 : isl_schedule_node_error
;
132 /* Return the type of the parent of "node" or isl_schedule_node_error on error.
134 enum isl_schedule_node_type
isl_schedule_node_get_parent_type(
135 __isl_keep isl_schedule_node
*node
)
139 isl_schedule_tree
*parent
;
140 enum isl_schedule_node_type type
;
143 return isl_schedule_node_error
;
144 has_parent
= isl_schedule_node_has_parent(node
);
146 return isl_schedule_node_error
;
148 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
149 "node has no parent", return isl_schedule_node_error
);
151 pos
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) - 1;
152 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, pos
);
153 type
= isl_schedule_tree_get_type(parent
);
154 isl_schedule_tree_free(parent
);
159 /* Return a copy of the subtree that this node points to.
161 __isl_give isl_schedule_tree
*isl_schedule_node_get_tree(
162 __isl_keep isl_schedule_node
*node
)
167 return isl_schedule_tree_copy(node
->tree
);
170 /* Return a copy of the schedule into which "node" points.
172 __isl_give isl_schedule
*isl_schedule_node_get_schedule(
173 __isl_keep isl_schedule_node
*node
)
177 return isl_schedule_copy(node
->schedule
);
180 /* Return a fresh copy of "node".
182 __isl_take isl_schedule_node
*isl_schedule_node_dup(
183 __isl_keep isl_schedule_node
*node
)
188 return isl_schedule_node_alloc(isl_schedule_copy(node
->schedule
),
189 isl_schedule_tree_copy(node
->tree
),
190 isl_schedule_tree_list_copy(node
->ancestors
),
194 /* Return an isl_schedule_node that is equal to "node" and that has only
195 * a single reference.
197 __isl_give isl_schedule_node
*isl_schedule_node_cow(
198 __isl_take isl_schedule_node
*node
)
206 return isl_schedule_node_dup(node
);
209 /* Return a new reference to "node".
211 __isl_give isl_schedule_node
*isl_schedule_node_copy(
212 __isl_keep isl_schedule_node
*node
)
221 /* Free "node" and return NULL.
223 __isl_null isl_schedule_node
*isl_schedule_node_free(
224 __isl_take isl_schedule_node
*node
)
231 isl_schedule_tree_list_free(node
->ancestors
);
232 free(node
->child_pos
);
233 isl_schedule_tree_free(node
->tree
);
234 isl_schedule_free(node
->schedule
);
240 /* Do "node1" and "node2" point to the same position in the same
243 isl_bool
isl_schedule_node_is_equal(__isl_keep isl_schedule_node
*node1
,
244 __isl_keep isl_schedule_node
*node2
)
248 if (!node1
|| !node2
)
249 return isl_bool_error
;
251 return isl_bool_true
;
252 if (node1
->schedule
!= node2
->schedule
)
253 return isl_bool_false
;
255 n1
= isl_schedule_node_get_tree_depth(node1
);
256 n2
= isl_schedule_node_get_tree_depth(node2
);
258 return isl_bool_false
;
259 for (i
= 0; i
< n1
; ++i
)
260 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
261 return isl_bool_false
;
263 return isl_bool_true
;
266 /* Return the number of outer schedule dimensions of "node"
267 * in its schedule tree.
269 * Return -1 on error.
271 int isl_schedule_node_get_schedule_depth(__isl_keep isl_schedule_node
*node
)
279 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
280 for (i
= n
- 1; i
>= 0; --i
) {
281 isl_schedule_tree
*tree
;
283 tree
= isl_schedule_tree_list_get_schedule_tree(
287 if (tree
->type
== isl_schedule_node_band
)
288 depth
+= isl_schedule_tree_band_n_member(tree
);
289 isl_schedule_tree_free(tree
);
295 /* Internal data structure for
296 * isl_schedule_node_get_prefix_schedule_union_pw_multi_aff
298 * "initialized" is set if the filter field has been initialized.
299 * If "universe_domain" is not set, then the collected filter is intersected
300 * with the domain of the root domain node.
301 * "universe_filter" is set if we are only collecting the universes of filters
302 * "collect_prefix" is set if we are collecting prefixes.
303 * "filter" collects all outer filters and is NULL until "initialized" is set.
304 * "prefix" collects all outer band partial schedules (if "collect_prefix"
305 * is set). If it is used, then it is initialized by the caller
306 * of collect_filter_prefix to a zero-dimensional function.
308 struct isl_schedule_node_get_filter_prefix_data
{
313 isl_union_set
*filter
;
314 isl_multi_union_pw_aff
*prefix
;
317 static isl_stat
collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
318 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
);
320 /* Update the filter and prefix information in "data" based on the first "n"
321 * elements in "list" and the expansion tree root "tree".
323 * We first collect the information from the elements in "list",
324 * initializing the filter based on the domain of the expansion.
325 * Then we map the results to the expanded space and combined them
326 * with the results already in "data".
328 static isl_stat
collect_filter_prefix_expansion(
329 __isl_take isl_schedule_tree
*tree
,
330 __isl_keep isl_schedule_tree_list
*list
, int n
,
331 struct isl_schedule_node_get_filter_prefix_data
*data
)
333 struct isl_schedule_node_get_filter_prefix_data contracted
;
334 isl_union_pw_multi_aff
*c
;
335 isl_union_map
*exp
, *universe
;
336 isl_union_set
*filter
;
338 c
= isl_schedule_tree_expansion_get_contraction(tree
);
339 exp
= isl_schedule_tree_expansion_get_expansion(tree
);
341 contracted
.initialized
= 1;
342 contracted
.universe_domain
= data
->universe_domain
;
343 contracted
.universe_filter
= data
->universe_filter
;
344 contracted
.collect_prefix
= data
->collect_prefix
;
345 universe
= isl_union_map_universe(isl_union_map_copy(exp
));
346 filter
= isl_union_map_domain(universe
);
347 if (data
->collect_prefix
) {
348 isl_space
*space
= isl_union_set_get_space(filter
);
349 space
= isl_space_set_from_params(space
);
350 contracted
.prefix
= isl_multi_union_pw_aff_zero(space
);
352 contracted
.filter
= filter
;
354 if (collect_filter_prefix(list
, n
, &contracted
) < 0)
355 contracted
.filter
= isl_union_set_free(contracted
.filter
);
356 if (data
->collect_prefix
) {
357 isl_multi_union_pw_aff
*prefix
;
359 prefix
= contracted
.prefix
;
361 isl_multi_union_pw_aff_pullback_union_pw_multi_aff(prefix
,
362 isl_union_pw_multi_aff_copy(c
));
363 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(
364 prefix
, data
->prefix
);
366 filter
= contracted
.filter
;
367 if (data
->universe_domain
)
368 filter
= isl_union_set_preimage_union_pw_multi_aff(filter
,
369 isl_union_pw_multi_aff_copy(c
));
371 filter
= isl_union_set_apply(filter
, isl_union_map_copy(exp
));
372 if (!data
->initialized
)
373 data
->filter
= filter
;
375 data
->filter
= isl_union_set_intersect(filter
, data
->filter
);
376 data
->initialized
= 1;
378 isl_union_pw_multi_aff_free(c
);
379 isl_union_map_free(exp
);
380 isl_schedule_tree_free(tree
);
385 /* Update the filter information in "data" based on the first "n"
386 * elements in "list" and the extension tree root "tree", in case
387 * data->universe_domain is set and data->collect_prefix is not.
389 * We collect the universe domain of the elements in "list" and
390 * add it to the universe range of the extension (intersected
391 * with the already collected filter, if any).
393 static isl_stat
collect_universe_domain_extension(
394 __isl_take isl_schedule_tree
*tree
,
395 __isl_keep isl_schedule_tree_list
*list
, int n
,
396 struct isl_schedule_node_get_filter_prefix_data
*data
)
398 struct isl_schedule_node_get_filter_prefix_data data_outer
;
399 isl_union_map
*extension
;
400 isl_union_set
*filter
;
402 data_outer
.initialized
= 0;
403 data_outer
.universe_domain
= 1;
404 data_outer
.universe_filter
= data
->universe_filter
;
405 data_outer
.collect_prefix
= 0;
406 data_outer
.filter
= NULL
;
407 data_outer
.prefix
= NULL
;
409 if (collect_filter_prefix(list
, n
, &data_outer
) < 0)
410 data_outer
.filter
= isl_union_set_free(data_outer
.filter
);
412 extension
= isl_schedule_tree_extension_get_extension(tree
);
413 extension
= isl_union_map_universe(extension
);
414 filter
= isl_union_map_range(extension
);
415 if (data_outer
.initialized
)
416 filter
= isl_union_set_union(filter
, data_outer
.filter
);
417 if (data
->initialized
)
418 filter
= isl_union_set_intersect(filter
, data
->filter
);
420 data
->filter
= filter
;
422 isl_schedule_tree_free(tree
);
427 /* Update "data" based on the tree node "tree" in case "data" has
428 * not been initialized yet.
430 * Return 0 on success and -1 on error.
432 * If "tree" is a filter, then we set data->filter to this filter
434 * If "tree" is a domain, then this means we have reached the root
435 * of the schedule tree without being able to extract any information.
436 * We therefore initialize data->filter to the universe of the domain,
437 * or the domain itself if data->universe_domain is not set.
438 * If "tree" is a band with at least one member, then we set data->filter
439 * to the universe of the schedule domain and replace the zero-dimensional
440 * data->prefix by the band schedule (if data->collect_prefix is set).
442 static isl_stat
collect_filter_prefix_init(__isl_keep isl_schedule_tree
*tree
,
443 struct isl_schedule_node_get_filter_prefix_data
*data
)
445 enum isl_schedule_node_type type
;
446 isl_multi_union_pw_aff
*mupa
;
447 isl_union_set
*filter
;
449 type
= isl_schedule_tree_get_type(tree
);
451 case isl_schedule_node_error
:
452 return isl_stat_error
;
453 case isl_schedule_node_expansion
:
454 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
455 "should be handled by caller", return isl_stat_error
);
456 case isl_schedule_node_extension
:
457 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
458 "cannot handle extension nodes", return isl_stat_error
);
459 case isl_schedule_node_context
:
460 case isl_schedule_node_leaf
:
461 case isl_schedule_node_guard
:
462 case isl_schedule_node_mark
:
463 case isl_schedule_node_sequence
:
464 case isl_schedule_node_set
:
466 case isl_schedule_node_domain
:
467 filter
= isl_schedule_tree_domain_get_domain(tree
);
468 if (data
->universe_domain
)
469 filter
= isl_union_set_universe(filter
);
470 data
->filter
= filter
;
472 case isl_schedule_node_band
:
473 if (isl_schedule_tree_band_n_member(tree
) == 0)
475 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
476 if (data
->collect_prefix
) {
477 isl_multi_union_pw_aff_free(data
->prefix
);
478 mupa
= isl_multi_union_pw_aff_reset_tuple_id(mupa
,
480 data
->prefix
= isl_multi_union_pw_aff_copy(mupa
);
482 filter
= isl_multi_union_pw_aff_domain(mupa
);
483 filter
= isl_union_set_universe(filter
);
484 data
->filter
= filter
;
486 case isl_schedule_node_filter
:
487 filter
= isl_schedule_tree_filter_get_filter(tree
);
488 if (data
->universe_filter
)
489 filter
= isl_union_set_universe(filter
);
490 data
->filter
= filter
;
494 if ((data
->collect_prefix
&& !data
->prefix
) || !data
->filter
)
495 return isl_stat_error
;
497 data
->initialized
= 1;
502 /* Update "data" based on the tree node "tree" in case "data" has
503 * already been initialized.
505 * Return 0 on success and -1 on error.
507 * If "tree" is a domain and data->universe_domain is not set, then
508 * intersect data->filter with the domain.
509 * If "tree" is a filter, then we intersect data->filter with this filter
511 * If "tree" is a band with at least one member and data->collect_prefix
512 * is set, then we extend data->prefix with the band schedule.
513 * If "tree" is an extension, then we make sure that we are not collecting
514 * information on any extended domain elements.
516 static isl_stat
collect_filter_prefix_update(__isl_keep isl_schedule_tree
*tree
,
517 struct isl_schedule_node_get_filter_prefix_data
*data
)
519 enum isl_schedule_node_type type
;
520 isl_multi_union_pw_aff
*mupa
;
521 isl_union_set
*filter
;
522 isl_union_map
*extension
;
525 type
= isl_schedule_tree_get_type(tree
);
527 case isl_schedule_node_error
:
528 return isl_stat_error
;
529 case isl_schedule_node_expansion
:
530 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
531 "should be handled by caller", return isl_stat_error
);
532 case isl_schedule_node_extension
:
533 extension
= isl_schedule_tree_extension_get_extension(tree
);
534 extension
= isl_union_map_intersect_range(extension
,
535 isl_union_set_copy(data
->filter
));
536 empty
= isl_union_map_is_empty(extension
);
537 isl_union_map_free(extension
);
539 return isl_stat_error
;
542 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
543 "cannot handle extension nodes", return isl_stat_error
);
544 case isl_schedule_node_context
:
545 case isl_schedule_node_leaf
:
546 case isl_schedule_node_guard
:
547 case isl_schedule_node_mark
:
548 case isl_schedule_node_sequence
:
549 case isl_schedule_node_set
:
551 case isl_schedule_node_domain
:
552 if (data
->universe_domain
)
554 filter
= isl_schedule_tree_domain_get_domain(tree
);
555 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
557 case isl_schedule_node_band
:
558 if (isl_schedule_tree_band_n_member(tree
) == 0)
560 if (!data
->collect_prefix
)
562 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
563 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(mupa
,
566 return isl_stat_error
;
568 case isl_schedule_node_filter
:
569 filter
= isl_schedule_tree_filter_get_filter(tree
);
570 if (data
->universe_filter
)
571 filter
= isl_union_set_universe(filter
);
572 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
574 return isl_stat_error
;
581 /* Collect filter and/or prefix information from the first "n"
582 * elements in "list" (which represent the ancestors of a node).
583 * Store the results in "data".
585 * Extension nodes are only supported if they do not affect the outcome,
586 * i.e., if we are collecting information on non-extended domain elements,
587 * or if we are collecting the universe domain (without prefix).
589 * Return 0 on success and -1 on error.
591 * We traverse the list from innermost ancestor (last element)
592 * to outermost ancestor (first element), calling collect_filter_prefix_init
593 * on each node as long as we have not been able to extract any information
594 * yet and collect_filter_prefix_update afterwards.
595 * If we come across an expansion node, then we interrupt the traversal
596 * and call collect_filter_prefix_expansion to restart the traversal
597 * over the remaining ancestors and to combine the results with those
598 * that have already been collected.
599 * If we come across an extension node and we are only computing
600 * the universe domain, then we interrupt the traversal and call
601 * collect_universe_domain_extension to restart the traversal
602 * over the remaining ancestors and to combine the results with those
603 * that have already been collected.
604 * On successful return, data->initialized will be set since the outermost
605 * ancestor is a domain node, which always results in an initialization.
607 static isl_stat
collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
608 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
)
613 return isl_stat_error
;
615 for (i
= n
- 1; i
>= 0; --i
) {
616 isl_schedule_tree
*tree
;
617 enum isl_schedule_node_type type
;
620 tree
= isl_schedule_tree_list_get_schedule_tree(list
, i
);
622 return isl_stat_error
;
623 type
= isl_schedule_tree_get_type(tree
);
624 if (type
== isl_schedule_node_expansion
)
625 return collect_filter_prefix_expansion(tree
, list
, i
,
627 if (type
== isl_schedule_node_extension
&&
628 data
->universe_domain
&& !data
->collect_prefix
)
629 return collect_universe_domain_extension(tree
, list
, i
,
631 if (!data
->initialized
)
632 r
= collect_filter_prefix_init(tree
, data
);
634 r
= collect_filter_prefix_update(tree
, data
);
635 isl_schedule_tree_free(tree
);
637 return isl_stat_error
;
643 /* Return the concatenation of the partial schedules of all outer band
644 * nodes of "node" interesected with all outer filters
645 * as an isl_multi_union_pw_aff.
646 * None of the ancestors of "node" may be an extension node, unless
647 * there is also a filter ancestor that filters out all the extended
650 * If "node" is pointing at the root of the schedule tree, then
651 * there are no domain elements reaching the current node, so
652 * we return an empty result.
654 * We collect all the filters and partial schedules in collect_filter_prefix
655 * and intersect the domain of the combined schedule with the combined filter.
657 __isl_give isl_multi_union_pw_aff
*
658 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(
659 __isl_keep isl_schedule_node
*node
)
663 struct isl_schedule_node_get_filter_prefix_data data
;
668 space
= isl_schedule_get_space(node
->schedule
);
669 space
= isl_space_set_from_params(space
);
670 if (node
->tree
== node
->schedule
->root
)
671 return isl_multi_union_pw_aff_zero(space
);
673 data
.initialized
= 0;
674 data
.universe_domain
= 1;
675 data
.universe_filter
= 0;
676 data
.collect_prefix
= 1;
678 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
680 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
681 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
682 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
684 data
.prefix
= isl_multi_union_pw_aff_intersect_domain(data
.prefix
,
690 /* Return the concatenation of the partial schedules of all outer band
691 * nodes of "node" interesected with all outer filters
692 * as an isl_union_pw_multi_aff.
693 * None of the ancestors of "node" may be an extension node, unless
694 * there is also a filter ancestor that filters out all the extended
697 * If "node" is pointing at the root of the schedule tree, then
698 * there are no domain elements reaching the current node, so
699 * we return an empty result.
701 * We collect all the filters and partial schedules in collect_filter_prefix.
702 * The partial schedules are collected as an isl_multi_union_pw_aff.
703 * If this isl_multi_union_pw_aff is zero-dimensional, then it does not
704 * contain any domain information, so we construct the isl_union_pw_multi_aff
705 * result as a zero-dimensional function on the collected filter.
706 * Otherwise, we convert the isl_multi_union_pw_aff to
707 * an isl_multi_union_pw_aff and intersect the domain with the filter.
709 __isl_give isl_union_pw_multi_aff
*
710 isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(
711 __isl_keep isl_schedule_node
*node
)
716 isl_union_pw_multi_aff
*prefix
;
717 struct isl_schedule_node_get_filter_prefix_data data
;
722 space
= isl_schedule_get_space(node
->schedule
);
723 if (node
->tree
== node
->schedule
->root
)
724 return isl_union_pw_multi_aff_empty(space
);
726 space
= isl_space_set_from_params(space
);
727 data
.initialized
= 0;
728 data
.universe_domain
= 1;
729 data
.universe_filter
= 0;
730 data
.collect_prefix
= 1;
732 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
734 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
735 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
736 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
738 dim
= isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
);
740 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
741 if (data
.prefix
&& dim
== 0) {
742 isl_multi_union_pw_aff_free(data
.prefix
);
743 prefix
= isl_union_pw_multi_aff_from_domain(data
.filter
);
746 isl_union_pw_multi_aff_from_multi_union_pw_aff(data
.prefix
);
747 prefix
= isl_union_pw_multi_aff_intersect_domain(prefix
,
754 /* Return the concatenation of the partial schedules of all outer band
755 * nodes of "node" interesected with all outer filters
756 * as an isl_union_map.
758 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_union_map(
759 __isl_keep isl_schedule_node
*node
)
761 isl_union_pw_multi_aff
*upma
;
763 upma
= isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(node
);
764 return isl_union_map_from_union_pw_multi_aff(upma
);
767 /* Return the concatenation of the partial schedules of all outer band
768 * nodes of "node" intersected with all outer domain constraints.
769 * None of the ancestors of "node" may be an extension node, unless
770 * there is also a filter ancestor that filters out all the extended
773 * Essentially, this function intersects the domain of the output
774 * of isl_schedule_node_get_prefix_schedule_union_map with the output
775 * of isl_schedule_node_get_domain, except that it only traverses
776 * the ancestors of "node" once.
778 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_relation(
779 __isl_keep isl_schedule_node
*node
)
784 isl_union_map
*prefix
;
785 struct isl_schedule_node_get_filter_prefix_data data
;
790 space
= isl_schedule_get_space(node
->schedule
);
791 if (node
->tree
== node
->schedule
->root
)
792 return isl_union_map_empty(space
);
794 space
= isl_space_set_from_params(space
);
795 data
.initialized
= 0;
796 data
.universe_domain
= 0;
797 data
.universe_filter
= 0;
798 data
.collect_prefix
= 1;
800 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
802 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
803 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
804 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
806 dim
= isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
);
808 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
809 if (data
.prefix
&& dim
== 0) {
810 isl_multi_union_pw_aff_free(data
.prefix
);
811 prefix
= isl_union_map_from_domain(data
.filter
);
813 prefix
= isl_union_map_from_multi_union_pw_aff(data
.prefix
);
814 prefix
= isl_union_map_intersect_domain(prefix
, data
.filter
);
820 /* Return the domain elements that reach "node".
822 * If "node" is pointing at the root of the schedule tree, then
823 * there are no domain elements reaching the current node, so
824 * we return an empty result.
825 * None of the ancestors of "node" may be an extension node, unless
826 * there is also a filter ancestor that filters out all the extended
829 * Otherwise, we collect all filters reaching the node,
830 * intersected with the root domain in collect_filter_prefix.
832 __isl_give isl_union_set
*isl_schedule_node_get_domain(
833 __isl_keep isl_schedule_node
*node
)
836 struct isl_schedule_node_get_filter_prefix_data data
;
841 if (node
->tree
== node
->schedule
->root
) {
844 space
= isl_schedule_get_space(node
->schedule
);
845 return isl_union_set_empty(space
);
848 data
.initialized
= 0;
849 data
.universe_domain
= 0;
850 data
.universe_filter
= 0;
851 data
.collect_prefix
= 0;
855 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
856 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
857 data
.filter
= isl_union_set_free(data
.filter
);
862 /* Return the union of universe sets of the domain elements that reach "node".
864 * If "node" is pointing at the root of the schedule tree, then
865 * there are no domain elements reaching the current node, so
866 * we return an empty result.
868 * Otherwise, we collect the universes of all filters reaching the node
869 * in collect_filter_prefix.
871 __isl_give isl_union_set
*isl_schedule_node_get_universe_domain(
872 __isl_keep isl_schedule_node
*node
)
875 struct isl_schedule_node_get_filter_prefix_data data
;
880 if (node
->tree
== node
->schedule
->root
) {
883 space
= isl_schedule_get_space(node
->schedule
);
884 return isl_union_set_empty(space
);
887 data
.initialized
= 0;
888 data
.universe_domain
= 1;
889 data
.universe_filter
= 1;
890 data
.collect_prefix
= 0;
894 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
895 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
896 data
.filter
= isl_union_set_free(data
.filter
);
901 /* Return the subtree schedule of "node".
903 * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle
904 * trees that do not contain any schedule information, we first
905 * move down to the first relevant descendant and handle leaves ourselves.
907 * If the subtree rooted at "node" contains any expansion nodes, then
908 * the returned subtree schedule is formulated in terms of the expanded
910 * The subtree is not allowed to contain any extension nodes.
912 __isl_give isl_union_map
*isl_schedule_node_get_subtree_schedule_union_map(
913 __isl_keep isl_schedule_node
*node
)
915 isl_schedule_tree
*tree
, *leaf
;
918 tree
= isl_schedule_node_get_tree(node
);
919 leaf
= isl_schedule_node_peek_leaf(node
);
920 tree
= isl_schedule_tree_first_schedule_descendant(tree
, leaf
);
924 isl_union_set
*domain
;
925 domain
= isl_schedule_node_get_universe_domain(node
);
926 isl_schedule_tree_free(tree
);
927 return isl_union_map_from_domain(domain
);
930 umap
= isl_schedule_tree_get_subtree_schedule_union_map(tree
);
931 isl_schedule_tree_free(tree
);
935 /* Return the number of ancestors of "node" in its schedule tree.
937 int isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node
*node
)
941 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
944 /* Does "node" have a parent?
946 * That is, does it point to any node of the schedule other than the root?
948 isl_bool
isl_schedule_node_has_parent(__isl_keep isl_schedule_node
*node
)
952 depth
= isl_schedule_node_get_tree_depth(node
);
954 return isl_bool_error
;
958 /* Return the position of "node" among the children of its parent.
960 int isl_schedule_node_get_child_position(__isl_keep isl_schedule_node
*node
)
967 has_parent
= isl_schedule_node_has_parent(node
);
971 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
972 "node has no parent", return -1);
974 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
975 return node
->child_pos
[n
- 1];
978 /* Does the parent (if any) of "node" have any children with a smaller child
979 * position than this one?
981 isl_bool
isl_schedule_node_has_previous_sibling(
982 __isl_keep isl_schedule_node
*node
)
988 return isl_bool_error
;
989 has_parent
= isl_schedule_node_has_parent(node
);
990 if (has_parent
< 0 || !has_parent
)
993 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
995 return node
->child_pos
[n
- 1] > 0;
998 /* Does the parent (if any) of "node" have any children with a greater child
999 * position than this one?
1001 isl_bool
isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node
*node
)
1004 isl_bool has_parent
;
1005 isl_schedule_tree
*tree
;
1008 return isl_bool_error
;
1009 has_parent
= isl_schedule_node_has_parent(node
);
1010 if (has_parent
< 0 || !has_parent
)
1013 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1014 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
1015 n_child
= isl_schedule_tree_n_children(tree
);
1016 isl_schedule_tree_free(tree
);
1018 return isl_bool_error
;
1020 return node
->child_pos
[n
- 1] + 1 < n_child
;
1023 /* Does "node" have any children?
1025 * Any node other than the leaf nodes is considered to have at least
1026 * one child, even if the corresponding isl_schedule_tree does not
1027 * have any children.
1029 isl_bool
isl_schedule_node_has_children(__isl_keep isl_schedule_node
*node
)
1032 return isl_bool_error
;
1033 return !isl_schedule_tree_is_leaf(node
->tree
);
1036 /* Return the number of children of "node"?
1038 * Any node other than the leaf nodes is considered to have at least
1039 * one child, even if the corresponding isl_schedule_tree does not
1040 * have any children. That is, the number of children of "node" is
1041 * only zero if its tree is the explicit empty tree. Otherwise,
1042 * if the isl_schedule_tree has any children, then it is equal
1043 * to the number of children of "node". If it has zero children,
1044 * then "node" still has a leaf node as child.
1046 int isl_schedule_node_n_children(__isl_keep isl_schedule_node
*node
)
1053 if (isl_schedule_tree_is_leaf(node
->tree
))
1056 n
= isl_schedule_tree_n_children(node
->tree
);
1063 /* Move the "node" pointer to the ancestor of the given generation
1064 * of the node it currently points to, where generation 0 is the node
1065 * itself and generation 1 is its parent.
1067 __isl_give isl_schedule_node
*isl_schedule_node_ancestor(
1068 __isl_take isl_schedule_node
*node
, int generation
)
1071 isl_schedule_tree
*tree
;
1075 if (generation
== 0)
1077 n
= isl_schedule_node_get_tree_depth(node
);
1079 return isl_schedule_node_free(node
);
1080 if (generation
< 0 || generation
> n
)
1081 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1082 "generation out of bounds",
1083 return isl_schedule_node_free(node
));
1084 node
= isl_schedule_node_cow(node
);
1088 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1090 isl_schedule_tree_free(node
->tree
);
1092 node
->ancestors
= isl_schedule_tree_list_drop(node
->ancestors
,
1093 n
- generation
, generation
);
1094 if (!node
->ancestors
|| !node
->tree
)
1095 return isl_schedule_node_free(node
);
1100 /* Move the "node" pointer to the parent of the node it currently points to.
1102 __isl_give isl_schedule_node
*isl_schedule_node_parent(
1103 __isl_take isl_schedule_node
*node
)
1107 if (!isl_schedule_node_has_parent(node
))
1108 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1109 "node has no parent",
1110 return isl_schedule_node_free(node
));
1111 return isl_schedule_node_ancestor(node
, 1);
1114 /* Move the "node" pointer to the root of its schedule tree.
1116 __isl_give isl_schedule_node
*isl_schedule_node_root(
1117 __isl_take isl_schedule_node
*node
)
1123 n
= isl_schedule_node_get_tree_depth(node
);
1125 return isl_schedule_node_free(node
);
1126 return isl_schedule_node_ancestor(node
, n
);
1129 /* Move the "node" pointer to the child at position "pos" of the node
1130 * it currently points to.
1132 __isl_give isl_schedule_node
*isl_schedule_node_child(
1133 __isl_take isl_schedule_node
*node
, int pos
)
1137 isl_schedule_tree
*tree
;
1140 node
= isl_schedule_node_cow(node
);
1143 if (!isl_schedule_node_has_children(node
))
1144 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1145 "node has no children",
1146 return isl_schedule_node_free(node
));
1148 ctx
= isl_schedule_node_get_ctx(node
);
1149 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1150 child_pos
= isl_realloc_array(ctx
, node
->child_pos
, int, n
+ 1);
1152 return isl_schedule_node_free(node
);
1153 node
->child_pos
= child_pos
;
1154 node
->child_pos
[n
] = pos
;
1156 node
->ancestors
= isl_schedule_tree_list_add(node
->ancestors
,
1157 isl_schedule_tree_copy(node
->tree
));
1159 if (isl_schedule_tree_has_children(tree
))
1160 tree
= isl_schedule_tree_get_child(tree
, pos
);
1162 tree
= isl_schedule_node_get_leaf(node
);
1163 isl_schedule_tree_free(node
->tree
);
1166 if (!node
->tree
|| !node
->ancestors
)
1167 return isl_schedule_node_free(node
);
1172 /* Move the "node" pointer to the first child of the node
1173 * it currently points to.
1175 __isl_give isl_schedule_node
*isl_schedule_node_first_child(
1176 __isl_take isl_schedule_node
*node
)
1178 return isl_schedule_node_child(node
, 0);
1181 /* Move the "node" pointer to the child of this node's parent in
1182 * the previous child position.
1184 __isl_give isl_schedule_node
*isl_schedule_node_previous_sibling(
1185 __isl_take isl_schedule_node
*node
)
1188 isl_schedule_tree
*parent
, *tree
;
1190 node
= isl_schedule_node_cow(node
);
1193 if (!isl_schedule_node_has_previous_sibling(node
))
1194 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1195 "node has no previous sibling",
1196 return isl_schedule_node_free(node
));
1198 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1199 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1202 return isl_schedule_node_free(node
);
1203 node
->child_pos
[n
- 1]--;
1204 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1205 node
->child_pos
[n
- 1]);
1206 isl_schedule_tree_free(parent
);
1208 return isl_schedule_node_free(node
);
1209 isl_schedule_tree_free(node
->tree
);
1215 /* Move the "node" pointer to the child of this node's parent in
1216 * the next child position.
1218 __isl_give isl_schedule_node
*isl_schedule_node_next_sibling(
1219 __isl_take isl_schedule_node
*node
)
1222 isl_schedule_tree
*parent
, *tree
;
1224 node
= isl_schedule_node_cow(node
);
1227 if (!isl_schedule_node_has_next_sibling(node
))
1228 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1229 "node has no next sibling",
1230 return isl_schedule_node_free(node
));
1232 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1233 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1236 return isl_schedule_node_free(node
);
1237 node
->child_pos
[n
- 1]++;
1238 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1239 node
->child_pos
[n
- 1]);
1240 isl_schedule_tree_free(parent
);
1242 return isl_schedule_node_free(node
);
1243 isl_schedule_tree_free(node
->tree
);
1249 /* Return a copy to the child at position "pos" of "node".
1251 __isl_give isl_schedule_node
*isl_schedule_node_get_child(
1252 __isl_keep isl_schedule_node
*node
, int pos
)
1254 return isl_schedule_node_child(isl_schedule_node_copy(node
), pos
);
1257 /* Traverse the descendant of "node" in depth-first order, including
1258 * "node" itself. Call "enter" whenever a node is entered and "leave"
1259 * whenever a node is left. The callback "enter" is responsible
1260 * for moving to the deepest initial subtree of its argument that
1261 * should be traversed.
1263 static __isl_give isl_schedule_node
*traverse(
1264 __isl_take isl_schedule_node
*node
,
1265 __isl_give isl_schedule_node
*(*enter
)(
1266 __isl_take isl_schedule_node
*node
, void *user
),
1267 __isl_give isl_schedule_node
*(*leave
)(
1268 __isl_take isl_schedule_node
*node
, void *user
),
1276 depth
= isl_schedule_node_get_tree_depth(node
);
1278 node
= enter(node
, user
);
1279 node
= leave(node
, user
);
1280 while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
&&
1281 !isl_schedule_node_has_next_sibling(node
)) {
1282 node
= isl_schedule_node_parent(node
);
1283 node
= leave(node
, user
);
1285 if (node
&& isl_schedule_node_get_tree_depth(node
) > depth
)
1286 node
= isl_schedule_node_next_sibling(node
);
1287 } while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
);
1292 /* Internal data structure for isl_schedule_node_foreach_descendant_top_down.
1294 * "fn" is the user-specified callback function.
1295 * "user" is the user-specified argument for the callback.
1297 struct isl_schedule_node_preorder_data
{
1298 isl_bool (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
);
1302 /* Callback for "traverse" to enter a node and to move
1303 * to the deepest initial subtree that should be traversed
1304 * for use in a preorder visit.
1306 * If the user callback returns a negative value, then we abort
1307 * the traversal. If this callback returns zero, then we skip
1308 * the subtree rooted at the current node. Otherwise, we move
1309 * down to the first child and repeat the process until a leaf
1312 static __isl_give isl_schedule_node
*preorder_enter(
1313 __isl_take isl_schedule_node
*node
, void *user
)
1315 struct isl_schedule_node_preorder_data
*data
= user
;
1323 r
= data
->fn(node
, data
->user
);
1325 return isl_schedule_node_free(node
);
1326 if (r
== isl_bool_false
)
1328 } while (isl_schedule_node_has_children(node
) &&
1329 (node
= isl_schedule_node_first_child(node
)) != NULL
);
1334 /* Callback for "traverse" to leave a node
1335 * for use in a preorder visit.
1336 * Since we already visited the node when we entered it,
1337 * we do not need to do anything here.
1339 static __isl_give isl_schedule_node
*preorder_leave(
1340 __isl_take isl_schedule_node
*node
, void *user
)
1345 /* Traverse the descendants of "node" (including the node itself)
1346 * in depth first preorder.
1348 * If "fn" returns isl_bool_error on any of the nodes,
1349 * then the traversal is aborted.
1350 * If "fn" returns isl_bool_false on any of the nodes, then the subtree rooted
1351 * at that node is skipped.
1353 * Return isl_stat_ok on success and isl_stat_error on failure.
1355 isl_stat
isl_schedule_node_foreach_descendant_top_down(
1356 __isl_keep isl_schedule_node
*node
,
1357 isl_bool (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
),
1360 struct isl_schedule_node_preorder_data data
= { fn
, user
};
1362 node
= isl_schedule_node_copy(node
);
1363 node
= traverse(node
, &preorder_enter
, &preorder_leave
, &data
);
1364 isl_schedule_node_free(node
);
1366 return node
? isl_stat_ok
: isl_stat_error
;
1369 /* Internal data structure for isl_schedule_node_every_descendant.
1371 * "test" is the user-specified callback function.
1372 * "user" is the user-specified callback function argument.
1374 * "failed" is initialized to 0 and set to 1 if "test" fails
1377 struct isl_union_map_every_data
{
1378 isl_bool (*test
)(__isl_keep isl_schedule_node
*node
, void *user
);
1383 /* isl_schedule_node_foreach_descendant_top_down callback
1384 * that sets data->failed if data->test returns false and
1385 * subsequently aborts the traversal.
1387 static isl_bool
call_every(__isl_keep isl_schedule_node
*node
, void *user
)
1389 struct isl_union_map_every_data
*data
= user
;
1392 r
= data
->test(node
, data
->user
);
1394 return isl_bool_error
;
1396 return isl_bool_true
;
1398 return isl_bool_error
;
1401 /* Does "test" succeed on every descendant of "node" (including "node" itself)?
1403 isl_bool
isl_schedule_node_every_descendant(__isl_keep isl_schedule_node
*node
,
1404 isl_bool (*test
)(__isl_keep isl_schedule_node
*node
, void *user
),
1407 struct isl_union_map_every_data data
= { test
, user
, 0 };
1410 r
= isl_schedule_node_foreach_descendant_top_down(node
, &call_every
,
1413 return isl_bool_true
;
1415 return isl_bool_false
;
1416 return isl_bool_error
;
1419 /* Internal data structure for isl_schedule_node_map_descendant_bottom_up.
1421 * "fn" is the user-specified callback function.
1422 * "user" is the user-specified argument for the callback.
1424 struct isl_schedule_node_postorder_data
{
1425 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1430 /* Callback for "traverse" to enter a node and to move
1431 * to the deepest initial subtree that should be traversed
1432 * for use in a postorder visit.
1434 * Since we are performing a postorder visit, we only need
1435 * to move to the deepest initial leaf here.
1437 static __isl_give isl_schedule_node
*postorder_enter(
1438 __isl_take isl_schedule_node
*node
, void *user
)
1440 while (node
&& isl_schedule_node_has_children(node
))
1441 node
= isl_schedule_node_first_child(node
);
1446 /* Callback for "traverse" to leave a node
1447 * for use in a postorder visit.
1449 * Since we are performing a postorder visit, we need
1450 * to call the user callback here.
1452 static __isl_give isl_schedule_node
*postorder_leave(
1453 __isl_take isl_schedule_node
*node
, void *user
)
1455 struct isl_schedule_node_postorder_data
*data
= user
;
1457 return data
->fn(node
, data
->user
);
1460 /* Traverse the descendants of "node" (including the node itself)
1461 * in depth first postorder, allowing the user to modify the visited node.
1462 * The traversal continues from the node returned by the callback function.
1463 * It is the responsibility of the user to ensure that this does not
1464 * lead to an infinite loop. It is safest to always return a pointer
1465 * to the same position (same ancestors and child positions) as the input node.
1467 __isl_give isl_schedule_node
*isl_schedule_node_map_descendant_bottom_up(
1468 __isl_take isl_schedule_node
*node
,
1469 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1470 void *user
), void *user
)
1472 struct isl_schedule_node_postorder_data data
= { fn
, user
};
1474 return traverse(node
, &postorder_enter
, &postorder_leave
, &data
);
1477 /* Traverse the ancestors of "node" from the root down to and including
1478 * the parent of "node", calling "fn" on each of them.
1480 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1482 * Return 0 on success and -1 on failure.
1484 isl_stat
isl_schedule_node_foreach_ancestor_top_down(
1485 __isl_keep isl_schedule_node
*node
,
1486 isl_stat (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
),
1492 return isl_stat_error
;
1494 n
= isl_schedule_node_get_tree_depth(node
);
1495 for (i
= 0; i
< n
; ++i
) {
1496 isl_schedule_node
*ancestor
;
1499 ancestor
= isl_schedule_node_copy(node
);
1500 ancestor
= isl_schedule_node_ancestor(ancestor
, n
- i
);
1501 r
= fn(ancestor
, user
);
1502 isl_schedule_node_free(ancestor
);
1504 return isl_stat_error
;
1510 /* Is any node in the subtree rooted at "node" anchored?
1511 * That is, do any of these nodes reference the outer band nodes?
1513 isl_bool
isl_schedule_node_is_subtree_anchored(
1514 __isl_keep isl_schedule_node
*node
)
1517 return isl_bool_error
;
1518 return isl_schedule_tree_is_subtree_anchored(node
->tree
);
1521 /* Return the number of members in the given band node.
1523 unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node
*node
)
1525 return node
? isl_schedule_tree_band_n_member(node
->tree
) : 0;
1528 /* Is the band member at position "pos" of the band node "node"
1529 * marked coincident?
1531 isl_bool
isl_schedule_node_band_member_get_coincident(
1532 __isl_keep isl_schedule_node
*node
, int pos
)
1535 return isl_bool_error
;
1536 return isl_schedule_tree_band_member_get_coincident(node
->tree
, pos
);
1539 /* Mark the band member at position "pos" the band node "node"
1540 * as being coincident or not according to "coincident".
1542 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_coincident(
1543 __isl_take isl_schedule_node
*node
, int pos
, int coincident
)
1546 isl_schedule_tree
*tree
;
1550 c
= isl_schedule_node_band_member_get_coincident(node
, pos
);
1551 if (c
== coincident
)
1554 tree
= isl_schedule_tree_copy(node
->tree
);
1555 tree
= isl_schedule_tree_band_member_set_coincident(tree
, pos
,
1557 node
= isl_schedule_node_graft_tree(node
, tree
);
1562 /* Is the band node "node" marked permutable?
1564 isl_bool
isl_schedule_node_band_get_permutable(
1565 __isl_keep isl_schedule_node
*node
)
1568 return isl_bool_error
;
1570 return isl_schedule_tree_band_get_permutable(node
->tree
);
1573 /* Mark the band node "node" permutable or not according to "permutable"?
1575 __isl_give isl_schedule_node
*isl_schedule_node_band_set_permutable(
1576 __isl_take isl_schedule_node
*node
, int permutable
)
1578 isl_schedule_tree
*tree
;
1582 if (isl_schedule_node_band_get_permutable(node
) == permutable
)
1585 tree
= isl_schedule_tree_copy(node
->tree
);
1586 tree
= isl_schedule_tree_band_set_permutable(tree
, permutable
);
1587 node
= isl_schedule_node_graft_tree(node
, tree
);
1592 /* Return the schedule space of the band node.
1594 __isl_give isl_space
*isl_schedule_node_band_get_space(
1595 __isl_keep isl_schedule_node
*node
)
1600 return isl_schedule_tree_band_get_space(node
->tree
);
1603 /* Return the schedule of the band node in isolation.
1605 __isl_give isl_multi_union_pw_aff
*isl_schedule_node_band_get_partial_schedule(
1606 __isl_keep isl_schedule_node
*node
)
1611 return isl_schedule_tree_band_get_partial_schedule(node
->tree
);
1614 /* Return the schedule of the band node in isolation in the form of
1617 * If the band does not have any members, then we construct a universe map
1618 * with the universe of the domain elements reaching the node as domain.
1619 * Otherwise, we extract an isl_multi_union_pw_aff representation and
1620 * convert that to an isl_union_map.
1622 __isl_give isl_union_map
*isl_schedule_node_band_get_partial_schedule_union_map(
1623 __isl_keep isl_schedule_node
*node
)
1625 isl_multi_union_pw_aff
*mupa
;
1630 if (isl_schedule_node_get_type(node
) != isl_schedule_node_band
)
1631 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1632 "not a band node", return NULL
);
1633 if (isl_schedule_node_band_n_member(node
) == 0) {
1634 isl_union_set
*domain
;
1636 domain
= isl_schedule_node_get_universe_domain(node
);
1637 return isl_union_map_from_domain(domain
);
1640 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
1641 return isl_union_map_from_multi_union_pw_aff(mupa
);
1644 /* Return the loop AST generation type for the band member of band node "node"
1645 * at position "pos".
1647 enum isl_ast_loop_type
isl_schedule_node_band_member_get_ast_loop_type(
1648 __isl_keep isl_schedule_node
*node
, int pos
)
1651 return isl_ast_loop_error
;
1653 return isl_schedule_tree_band_member_get_ast_loop_type(node
->tree
, pos
);
1656 /* Set the loop AST generation type for the band member of band node "node"
1657 * at position "pos" to "type".
1659 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_ast_loop_type(
1660 __isl_take isl_schedule_node
*node
, int pos
,
1661 enum isl_ast_loop_type type
)
1663 isl_schedule_tree
*tree
;
1668 tree
= isl_schedule_tree_copy(node
->tree
);
1669 tree
= isl_schedule_tree_band_member_set_ast_loop_type(tree
, pos
, type
);
1670 return isl_schedule_node_graft_tree(node
, tree
);
1673 /* Return the loop AST generation type for the band member of band node "node"
1674 * at position "pos" for the isolated part.
1676 enum isl_ast_loop_type
isl_schedule_node_band_member_get_isolate_ast_loop_type(
1677 __isl_keep isl_schedule_node
*node
, int pos
)
1680 return isl_ast_loop_error
;
1682 return isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1686 /* Set the loop AST generation type for the band member of band node "node"
1687 * at position "pos" for the isolated part to "type".
1689 __isl_give isl_schedule_node
*
1690 isl_schedule_node_band_member_set_isolate_ast_loop_type(
1691 __isl_take isl_schedule_node
*node
, int pos
,
1692 enum isl_ast_loop_type type
)
1694 isl_schedule_tree
*tree
;
1699 tree
= isl_schedule_tree_copy(node
->tree
);
1700 tree
= isl_schedule_tree_band_member_set_isolate_ast_loop_type(tree
,
1702 return isl_schedule_node_graft_tree(node
, tree
);
1705 /* Return the AST build options associated to band node "node".
1707 __isl_give isl_union_set
*isl_schedule_node_band_get_ast_build_options(
1708 __isl_keep isl_schedule_node
*node
)
1713 return isl_schedule_tree_band_get_ast_build_options(node
->tree
);
1716 /* Replace the AST build options associated to band node "node" by "options".
1718 __isl_give isl_schedule_node
*isl_schedule_node_band_set_ast_build_options(
1719 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*options
)
1721 isl_schedule_tree
*tree
;
1723 if (!node
|| !options
)
1726 tree
= isl_schedule_tree_copy(node
->tree
);
1727 tree
= isl_schedule_tree_band_set_ast_build_options(tree
, options
);
1728 return isl_schedule_node_graft_tree(node
, tree
);
1730 isl_schedule_node_free(node
);
1731 isl_union_set_free(options
);
1735 /* Return the "isolate" option associated to band node "node".
1737 __isl_give isl_set
*isl_schedule_node_band_get_ast_isolate_option(
1738 __isl_keep isl_schedule_node
*node
)
1745 depth
= isl_schedule_node_get_schedule_depth(node
);
1746 return isl_schedule_tree_band_get_ast_isolate_option(node
->tree
, depth
);
1749 /* Make sure that that spaces of "node" and "mv" are the same.
1750 * Return -1 on error, reporting the error to the user.
1752 static int check_space_multi_val(__isl_keep isl_schedule_node
*node
,
1753 __isl_keep isl_multi_val
*mv
)
1755 isl_space
*node_space
, *mv_space
;
1758 node_space
= isl_schedule_node_band_get_space(node
);
1759 mv_space
= isl_multi_val_get_space(mv
);
1760 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1761 mv_space
, isl_dim_set
);
1762 isl_space_free(mv_space
);
1763 isl_space_free(node_space
);
1767 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1768 "spaces don't match", return -1);
1773 /* Multiply the partial schedule of the band node "node"
1774 * with the factors in "mv".
1776 __isl_give isl_schedule_node
*isl_schedule_node_band_scale(
1777 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1779 isl_schedule_tree
*tree
;
1784 if (check_space_multi_val(node
, mv
) < 0)
1786 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1790 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1791 "cannot scale band node with anchored subtree",
1794 tree
= isl_schedule_node_get_tree(node
);
1795 tree
= isl_schedule_tree_band_scale(tree
, mv
);
1796 return isl_schedule_node_graft_tree(node
, tree
);
1798 isl_multi_val_free(mv
);
1799 isl_schedule_node_free(node
);
1803 /* Divide the partial schedule of the band node "node"
1804 * by the factors in "mv".
1806 __isl_give isl_schedule_node
*isl_schedule_node_band_scale_down(
1807 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1809 isl_schedule_tree
*tree
;
1814 if (check_space_multi_val(node
, mv
) < 0)
1816 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1820 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1821 "cannot scale down band node with anchored subtree",
1824 tree
= isl_schedule_node_get_tree(node
);
1825 tree
= isl_schedule_tree_band_scale_down(tree
, mv
);
1826 return isl_schedule_node_graft_tree(node
, tree
);
1828 isl_multi_val_free(mv
);
1829 isl_schedule_node_free(node
);
1833 /* Reduce the partial schedule of the band node "node"
1834 * modulo the factors in "mv".
1836 __isl_give isl_schedule_node
*isl_schedule_node_band_mod(
1837 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1839 isl_schedule_tree
*tree
;
1844 if (check_space_multi_val(node
, mv
) < 0)
1846 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1850 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1851 "cannot perform mod on band node with anchored subtree",
1854 tree
= isl_schedule_node_get_tree(node
);
1855 tree
= isl_schedule_tree_band_mod(tree
, mv
);
1856 return isl_schedule_node_graft_tree(node
, tree
);
1858 isl_multi_val_free(mv
);
1859 isl_schedule_node_free(node
);
1863 /* Make sure that that spaces of "node" and "mupa" are the same.
1864 * Return isl_stat_error on error, reporting the error to the user.
1866 static isl_stat
check_space_multi_union_pw_aff(
1867 __isl_keep isl_schedule_node
*node
,
1868 __isl_keep isl_multi_union_pw_aff
*mupa
)
1870 isl_space
*node_space
, *mupa_space
;
1873 node_space
= isl_schedule_node_band_get_space(node
);
1874 mupa_space
= isl_multi_union_pw_aff_get_space(mupa
);
1875 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1876 mupa_space
, isl_dim_set
);
1877 isl_space_free(mupa_space
);
1878 isl_space_free(node_space
);
1880 return isl_stat_error
;
1882 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1883 "spaces don't match", return isl_stat_error
);
1888 /* Shift the partial schedule of the band node "node" by "shift".
1890 __isl_give isl_schedule_node
*isl_schedule_node_band_shift(
1891 __isl_take isl_schedule_node
*node
,
1892 __isl_take isl_multi_union_pw_aff
*shift
)
1894 isl_schedule_tree
*tree
;
1897 if (!node
|| !shift
)
1899 if (check_space_multi_union_pw_aff(node
, shift
) < 0)
1901 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1905 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1906 "cannot shift band node with anchored subtree",
1909 tree
= isl_schedule_node_get_tree(node
);
1910 tree
= isl_schedule_tree_band_shift(tree
, shift
);
1911 return isl_schedule_node_graft_tree(node
, tree
);
1913 isl_multi_union_pw_aff_free(shift
);
1914 isl_schedule_node_free(node
);
1918 /* Tile "node" with tile sizes "sizes".
1920 * The current node is replaced by two nested nodes corresponding
1921 * to the tile dimensions and the point dimensions.
1923 * Return a pointer to the outer (tile) node.
1925 * If any of the descendants of "node" depend on the set of outer band nodes,
1926 * then we refuse to tile the node.
1928 * If the scale tile loops option is set, then the tile loops
1929 * are scaled by the tile sizes. If the shift point loops option is set,
1930 * then the point loops are shifted to start at zero.
1931 * In particular, these options affect the tile and point loop schedules
1934 * scale shift original tile point
1936 * 0 0 i floor(i/s) i
1937 * 1 0 i s * floor(i/s) i
1938 * 0 1 i floor(i/s) i - s * floor(i/s)
1939 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1941 __isl_give isl_schedule_node
*isl_schedule_node_band_tile(
1942 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*sizes
)
1944 isl_schedule_tree
*tree
;
1947 if (!node
|| !sizes
)
1949 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1953 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1954 "cannot tile band node with anchored subtree",
1957 if (check_space_multi_val(node
, sizes
) < 0)
1960 tree
= isl_schedule_node_get_tree(node
);
1961 tree
= isl_schedule_tree_band_tile(tree
, sizes
);
1962 return isl_schedule_node_graft_tree(node
, tree
);
1964 isl_multi_val_free(sizes
);
1965 isl_schedule_node_free(node
);
1969 /* Move the band node "node" down to all the leaves in the subtree
1971 * Return a pointer to the node in the resulting tree that is in the same
1972 * position as the node pointed to by "node" in the original tree.
1974 * If the node only has a leaf child, then nothing needs to be done.
1975 * Otherwise, the child of the node is removed and the result is
1976 * appended to all the leaves in the subtree rooted at the original child.
1977 * Since the node is moved to the leaves, it needs to be expanded
1978 * according to the expansion, if any, defined by that subtree.
1979 * In the end, the original node is replaced by the result of
1980 * attaching copies of the expanded node to the leaves.
1982 * If any of the nodes in the subtree rooted at "node" depend on
1983 * the set of outer band nodes then we refuse to sink the band node.
1985 __isl_give isl_schedule_node
*isl_schedule_node_band_sink(
1986 __isl_take isl_schedule_node
*node
)
1988 enum isl_schedule_node_type type
;
1989 isl_schedule_tree
*tree
, *child
;
1990 isl_union_pw_multi_aff
*contraction
;
1996 type
= isl_schedule_node_get_type(node
);
1997 if (type
!= isl_schedule_node_band
)
1998 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1999 "not a band node", return isl_schedule_node_free(node
));
2000 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2002 return isl_schedule_node_free(node
);
2004 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2005 "cannot sink band node in anchored subtree",
2006 return isl_schedule_node_free(node
));
2007 if (isl_schedule_tree_n_children(node
->tree
) == 0)
2010 contraction
= isl_schedule_node_get_subtree_contraction(node
);
2012 tree
= isl_schedule_node_get_tree(node
);
2013 child
= isl_schedule_tree_get_child(tree
, 0);
2014 tree
= isl_schedule_tree_reset_children(tree
);
2015 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, contraction
);
2016 tree
= isl_schedule_tree_append_to_leaves(child
, tree
);
2018 return isl_schedule_node_graft_tree(node
, tree
);
2021 /* Split "node" into two nested band nodes, one with the first "pos"
2022 * dimensions and one with the remaining dimensions.
2023 * The schedules of the two band nodes live in anonymous spaces.
2024 * The loop AST generation type options and the isolate option
2025 * are split over the two band nodes.
2027 __isl_give isl_schedule_node
*isl_schedule_node_band_split(
2028 __isl_take isl_schedule_node
*node
, int pos
)
2031 isl_schedule_tree
*tree
;
2033 depth
= isl_schedule_node_get_schedule_depth(node
);
2034 tree
= isl_schedule_node_get_tree(node
);
2035 tree
= isl_schedule_tree_band_split(tree
, pos
, depth
);
2036 return isl_schedule_node_graft_tree(node
, tree
);
2039 /* Return the context of the context node "node".
2041 __isl_give isl_set
*isl_schedule_node_context_get_context(
2042 __isl_keep isl_schedule_node
*node
)
2047 return isl_schedule_tree_context_get_context(node
->tree
);
2050 /* Return the domain of the domain node "node".
2052 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
2053 __isl_keep isl_schedule_node
*node
)
2058 return isl_schedule_tree_domain_get_domain(node
->tree
);
2061 /* Return the expansion map of expansion node "node".
2063 __isl_give isl_union_map
*isl_schedule_node_expansion_get_expansion(
2064 __isl_keep isl_schedule_node
*node
)
2069 return isl_schedule_tree_expansion_get_expansion(node
->tree
);
2072 /* Return the contraction of expansion node "node".
2074 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_expansion_get_contraction(
2075 __isl_keep isl_schedule_node
*node
)
2080 return isl_schedule_tree_expansion_get_contraction(node
->tree
);
2083 /* Replace the contraction and the expansion of the expansion node "node"
2084 * by "contraction" and "expansion".
2086 __isl_give isl_schedule_node
*
2087 isl_schedule_node_expansion_set_contraction_and_expansion(
2088 __isl_take isl_schedule_node
*node
,
2089 __isl_take isl_union_pw_multi_aff
*contraction
,
2090 __isl_take isl_union_map
*expansion
)
2092 isl_schedule_tree
*tree
;
2094 if (!node
|| !contraction
|| !expansion
)
2097 tree
= isl_schedule_tree_copy(node
->tree
);
2098 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
2099 contraction
, expansion
);
2100 return isl_schedule_node_graft_tree(node
, tree
);
2102 isl_schedule_node_free(node
);
2103 isl_union_pw_multi_aff_free(contraction
);
2104 isl_union_map_free(expansion
);
2108 /* Return the extension of the extension node "node".
2110 __isl_give isl_union_map
*isl_schedule_node_extension_get_extension(
2111 __isl_keep isl_schedule_node
*node
)
2116 return isl_schedule_tree_extension_get_extension(node
->tree
);
2119 /* Replace the extension of extension node "node" by "extension".
2121 __isl_give isl_schedule_node
*isl_schedule_node_extension_set_extension(
2122 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
2124 isl_schedule_tree
*tree
;
2126 if (!node
|| !extension
)
2129 tree
= isl_schedule_tree_copy(node
->tree
);
2130 tree
= isl_schedule_tree_extension_set_extension(tree
, extension
);
2131 return isl_schedule_node_graft_tree(node
, tree
);
2133 isl_schedule_node_free(node
);
2134 isl_union_map_free(extension
);
2138 /* Return the filter of the filter node "node".
2140 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
2141 __isl_keep isl_schedule_node
*node
)
2146 return isl_schedule_tree_filter_get_filter(node
->tree
);
2149 /* Replace the filter of filter node "node" by "filter".
2151 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
2152 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2154 isl_schedule_tree
*tree
;
2156 if (!node
|| !filter
)
2159 tree
= isl_schedule_tree_copy(node
->tree
);
2160 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
2161 return isl_schedule_node_graft_tree(node
, tree
);
2163 isl_schedule_node_free(node
);
2164 isl_union_set_free(filter
);
2168 /* Intersect the filter of filter node "node" with "filter".
2170 * If the filter of the node is already a subset of "filter",
2171 * then leave the node unchanged.
2173 __isl_give isl_schedule_node
*isl_schedule_node_filter_intersect_filter(
2174 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2176 isl_union_set
*node_filter
= NULL
;
2179 if (!node
|| !filter
)
2182 node_filter
= isl_schedule_node_filter_get_filter(node
);
2183 subset
= isl_union_set_is_subset(node_filter
, filter
);
2187 isl_union_set_free(node_filter
);
2188 isl_union_set_free(filter
);
2191 node_filter
= isl_union_set_intersect(node_filter
, filter
);
2192 node
= isl_schedule_node_filter_set_filter(node
, node_filter
);
2195 isl_schedule_node_free(node
);
2196 isl_union_set_free(node_filter
);
2197 isl_union_set_free(filter
);
2201 /* Return the guard of the guard node "node".
2203 __isl_give isl_set
*isl_schedule_node_guard_get_guard(
2204 __isl_keep isl_schedule_node
*node
)
2209 return isl_schedule_tree_guard_get_guard(node
->tree
);
2212 /* Return the mark identifier of the mark node "node".
2214 __isl_give isl_id
*isl_schedule_node_mark_get_id(
2215 __isl_keep isl_schedule_node
*node
)
2220 return isl_schedule_tree_mark_get_id(node
->tree
);
2223 /* Replace the child at position "pos" of the sequence node "node"
2224 * by the children of sequence root node of "tree".
2226 __isl_give isl_schedule_node
*isl_schedule_node_sequence_splice(
2227 __isl_take isl_schedule_node
*node
, int pos
,
2228 __isl_take isl_schedule_tree
*tree
)
2230 isl_schedule_tree
*node_tree
;
2234 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2235 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2236 "not a sequence node", goto error
);
2237 if (isl_schedule_tree_get_type(tree
) != isl_schedule_node_sequence
)
2238 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2239 "not a sequence node", goto error
);
2240 node_tree
= isl_schedule_node_get_tree(node
);
2241 node_tree
= isl_schedule_tree_sequence_splice(node_tree
, pos
, tree
);
2242 node
= isl_schedule_node_graft_tree(node
, node_tree
);
2246 isl_schedule_node_free(node
);
2247 isl_schedule_tree_free(tree
);
2251 /* Given a sequence node "node", with a child at position "pos" that
2252 * is also a sequence node, attach the children of that node directly
2253 * as children of "node" at that position, replacing the original child.
2255 * The filters of these children are intersected with the filter
2256 * of the child at position "pos".
2258 __isl_give isl_schedule_node
*isl_schedule_node_sequence_splice_child(
2259 __isl_take isl_schedule_node
*node
, int pos
)
2262 isl_union_set
*filter
;
2263 isl_schedule_node
*child
;
2264 isl_schedule_tree
*tree
;
2268 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2269 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2270 "not a sequence node",
2271 return isl_schedule_node_free(node
));
2272 node
= isl_schedule_node_child(node
, pos
);
2273 node
= isl_schedule_node_child(node
, 0);
2274 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2275 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2276 "not a sequence node",
2277 return isl_schedule_node_free(node
));
2278 child
= isl_schedule_node_copy(node
);
2279 node
= isl_schedule_node_parent(node
);
2280 filter
= isl_schedule_node_filter_get_filter(node
);
2281 n
= isl_schedule_node_n_children(child
);
2282 for (i
= 0; i
< n
; ++i
) {
2283 child
= isl_schedule_node_child(child
, i
);
2284 child
= isl_schedule_node_filter_intersect_filter(child
,
2285 isl_union_set_copy(filter
));
2286 child
= isl_schedule_node_parent(child
);
2288 isl_union_set_free(filter
);
2289 tree
= isl_schedule_node_get_tree(child
);
2290 isl_schedule_node_free(child
);
2291 node
= isl_schedule_node_parent(node
);
2292 node
= isl_schedule_node_sequence_splice(node
, pos
, tree
);
2297 /* Update the ancestors of "node" to point to the tree that "node"
2299 * That is, replace the child in the original parent that corresponds
2300 * to the current tree position by node->tree and continue updating
2301 * the ancestors in the same way until the root is reached.
2303 * If "fn" is not NULL, then it is called on each ancestor as we move up
2304 * the tree so that it can modify the ancestor before it is added
2305 * to the list of ancestors of the modified node.
2306 * The additional "pos" argument records the position
2307 * of the "tree" argument in the original schedule tree.
2309 * If "node" originally points to a leaf of the schedule tree, then make sure
2310 * that in the end it points to a leaf in the updated schedule tree.
2312 static __isl_give isl_schedule_node
*update_ancestors(
2313 __isl_take isl_schedule_node
*node
,
2314 __isl_give isl_schedule_tree
*(*fn
)(__isl_take isl_schedule_tree
*tree
,
2315 __isl_keep isl_schedule_node
*pos
, void *user
), void *user
)
2319 isl_schedule_tree
*tree
;
2320 isl_schedule_node
*pos
= NULL
;
2323 pos
= isl_schedule_node_copy(node
);
2325 node
= isl_schedule_node_cow(node
);
2327 return isl_schedule_node_free(pos
);
2329 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
2330 tree
= isl_schedule_tree_copy(node
->tree
);
2332 for (i
= n
- 1; i
>= 0; --i
) {
2333 isl_schedule_tree
*parent
;
2335 parent
= isl_schedule_tree_list_get_schedule_tree(
2336 node
->ancestors
, i
);
2337 parent
= isl_schedule_tree_replace_child(parent
,
2338 node
->child_pos
[i
], tree
);
2340 pos
= isl_schedule_node_parent(pos
);
2341 parent
= fn(parent
, pos
, user
);
2343 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
2344 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
2350 isl_schedule_node_free(pos
);
2352 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
2353 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
2355 isl_schedule_tree_free(node
->tree
);
2356 node
->tree
= isl_schedule_node_get_leaf(node
);
2359 if (!node
->schedule
|| !node
->ancestors
)
2360 return isl_schedule_node_free(node
);
2365 /* Replace the subtree that "pos" points to by "tree", updating
2366 * the ancestors to maintain a consistent state.
2368 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
2369 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
2373 if (pos
->tree
== tree
) {
2374 isl_schedule_tree_free(tree
);
2378 pos
= isl_schedule_node_cow(pos
);
2382 isl_schedule_tree_free(pos
->tree
);
2385 return update_ancestors(pos
, NULL
, NULL
);
2387 isl_schedule_node_free(pos
);
2388 isl_schedule_tree_free(tree
);
2392 /* Make sure we can insert a node between "node" and its parent.
2393 * Return -1 on error, reporting the reason why we cannot insert a node.
2395 static int check_insert(__isl_keep isl_schedule_node
*node
)
2398 enum isl_schedule_node_type type
;
2400 has_parent
= isl_schedule_node_has_parent(node
);
2404 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2405 "cannot insert node outside of root", return -1);
2407 type
= isl_schedule_node_get_parent_type(node
);
2408 if (type
== isl_schedule_node_error
)
2410 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
2411 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2412 "cannot insert node between set or sequence node "
2413 "and its filter children", return -1);
2418 /* Insert a band node with partial schedule "mupa" between "node" and
2420 * Return a pointer to the new band node.
2422 * If any of the nodes in the subtree rooted at "node" depend on
2423 * the set of outer band nodes then we refuse to insert the band node.
2425 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
2426 __isl_take isl_schedule_node
*node
,
2427 __isl_take isl_multi_union_pw_aff
*mupa
)
2430 isl_schedule_band
*band
;
2431 isl_schedule_tree
*tree
;
2433 if (check_insert(node
) < 0)
2434 node
= isl_schedule_node_free(node
);
2435 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2439 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2440 "cannot insert band node in anchored subtree",
2443 tree
= isl_schedule_node_get_tree(node
);
2444 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
2445 tree
= isl_schedule_tree_insert_band(tree
, band
);
2446 node
= isl_schedule_node_graft_tree(node
, tree
);
2450 isl_schedule_node_free(node
);
2451 isl_multi_union_pw_aff_free(mupa
);
2455 /* Insert a context node with context "context" between "node" and its parent.
2456 * Return a pointer to the new context node.
2458 __isl_give isl_schedule_node
*isl_schedule_node_insert_context(
2459 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
2461 isl_schedule_tree
*tree
;
2463 if (check_insert(node
) < 0)
2464 node
= isl_schedule_node_free(node
);
2466 tree
= isl_schedule_node_get_tree(node
);
2467 tree
= isl_schedule_tree_insert_context(tree
, context
);
2468 node
= isl_schedule_node_graft_tree(node
, tree
);
2473 /* Insert an expansion node with the given "contraction" and "expansion"
2474 * between "node" and its parent.
2475 * Return a pointer to the new expansion node.
2477 * Typically the domain and range spaces of the expansion are different.
2478 * This means that only one of them can refer to the current domain space
2479 * in a consistent tree. It is up to the caller to ensure that the tree
2480 * returns to a consistent state.
2482 __isl_give isl_schedule_node
*isl_schedule_node_insert_expansion(
2483 __isl_take isl_schedule_node
*node
,
2484 __isl_take isl_union_pw_multi_aff
*contraction
,
2485 __isl_take isl_union_map
*expansion
)
2487 isl_schedule_tree
*tree
;
2489 if (check_insert(node
) < 0)
2490 node
= isl_schedule_node_free(node
);
2492 tree
= isl_schedule_node_get_tree(node
);
2493 tree
= isl_schedule_tree_insert_expansion(tree
, contraction
, expansion
);
2494 node
= isl_schedule_node_graft_tree(node
, tree
);
2499 /* Insert an extension node with extension "extension" between "node" and
2501 * Return a pointer to the new extension node.
2503 __isl_give isl_schedule_node
*isl_schedule_node_insert_extension(
2504 __isl_take isl_schedule_node
*node
,
2505 __isl_take isl_union_map
*extension
)
2507 isl_schedule_tree
*tree
;
2509 tree
= isl_schedule_node_get_tree(node
);
2510 tree
= isl_schedule_tree_insert_extension(tree
, extension
);
2511 node
= isl_schedule_node_graft_tree(node
, tree
);
2516 /* Insert a filter node with filter "filter" between "node" and its parent.
2517 * Return a pointer to the new filter node.
2519 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
2520 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2522 isl_schedule_tree
*tree
;
2524 if (check_insert(node
) < 0)
2525 node
= isl_schedule_node_free(node
);
2527 tree
= isl_schedule_node_get_tree(node
);
2528 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2529 node
= isl_schedule_node_graft_tree(node
, tree
);
2534 /* Insert a guard node with guard "guard" between "node" and its parent.
2535 * Return a pointer to the new guard node.
2537 __isl_give isl_schedule_node
*isl_schedule_node_insert_guard(
2538 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*guard
)
2540 isl_schedule_tree
*tree
;
2542 if (check_insert(node
) < 0)
2543 node
= isl_schedule_node_free(node
);
2545 tree
= isl_schedule_node_get_tree(node
);
2546 tree
= isl_schedule_tree_insert_guard(tree
, guard
);
2547 node
= isl_schedule_node_graft_tree(node
, tree
);
2552 /* Insert a mark node with mark identifier "mark" between "node" and
2554 * Return a pointer to the new mark node.
2556 __isl_give isl_schedule_node
*isl_schedule_node_insert_mark(
2557 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*mark
)
2559 isl_schedule_tree
*tree
;
2561 if (check_insert(node
) < 0)
2562 node
= isl_schedule_node_free(node
);
2564 tree
= isl_schedule_node_get_tree(node
);
2565 tree
= isl_schedule_tree_insert_mark(tree
, mark
);
2566 node
= isl_schedule_node_graft_tree(node
, tree
);
2571 /* Attach the current subtree of "node" to a sequence of filter tree nodes
2572 * with filters described by "filters", attach this sequence
2573 * of filter tree nodes as children to a new tree of type "type" and
2574 * replace the original subtree of "node" by this new tree.
2575 * Each copy of the original subtree is simplified with respect
2576 * to the corresponding filter.
2578 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
2579 __isl_take isl_schedule_node
*node
,
2580 enum isl_schedule_node_type type
,
2581 __isl_take isl_union_set_list
*filters
)
2585 isl_schedule_tree
*tree
;
2586 isl_schedule_tree_list
*list
;
2588 if (check_insert(node
) < 0)
2589 node
= isl_schedule_node_free(node
);
2591 if (!node
|| !filters
)
2594 ctx
= isl_schedule_node_get_ctx(node
);
2595 n
= isl_union_set_list_n_union_set(filters
);
2596 list
= isl_schedule_tree_list_alloc(ctx
, n
);
2597 for (i
= 0; i
< n
; ++i
) {
2598 isl_schedule_node
*node_i
;
2599 isl_schedule_tree
*tree
;
2600 isl_union_set
*filter
;
2602 filter
= isl_union_set_list_get_union_set(filters
, i
);
2603 node_i
= isl_schedule_node_copy(node
);
2604 node_i
= isl_schedule_node_gist(node_i
,
2605 isl_union_set_copy(filter
));
2606 tree
= isl_schedule_node_get_tree(node_i
);
2607 isl_schedule_node_free(node_i
);
2608 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2609 list
= isl_schedule_tree_list_add(list
, tree
);
2611 tree
= isl_schedule_tree_from_children(type
, list
);
2612 node
= isl_schedule_node_graft_tree(node
, tree
);
2614 isl_union_set_list_free(filters
);
2617 isl_union_set_list_free(filters
);
2618 isl_schedule_node_free(node
);
2622 /* Insert a sequence node with child filters "filters" between "node" and
2623 * its parent. That is, the tree that "node" points to is attached
2624 * to each of the child nodes of the filter nodes.
2625 * Return a pointer to the new sequence node.
2627 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
2628 __isl_take isl_schedule_node
*node
,
2629 __isl_take isl_union_set_list
*filters
)
2631 return isl_schedule_node_insert_children(node
,
2632 isl_schedule_node_sequence
, filters
);
2635 /* Insert a set node with child filters "filters" between "node" and
2636 * its parent. That is, the tree that "node" points to is attached
2637 * to each of the child nodes of the filter nodes.
2638 * Return a pointer to the new set node.
2640 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
2641 __isl_take isl_schedule_node
*node
,
2642 __isl_take isl_union_set_list
*filters
)
2644 return isl_schedule_node_insert_children(node
,
2645 isl_schedule_node_set
, filters
);
2648 /* Remove "node" from its schedule tree and return a pointer
2649 * to the leaf at the same position in the updated schedule tree.
2651 * It is not allowed to remove the root of a schedule tree or
2652 * a child of a set or sequence node.
2654 __isl_give isl_schedule_node
*isl_schedule_node_cut(
2655 __isl_take isl_schedule_node
*node
)
2657 isl_schedule_tree
*leaf
;
2658 enum isl_schedule_node_type parent_type
;
2662 if (!isl_schedule_node_has_parent(node
))
2663 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2664 "cannot cut root", return isl_schedule_node_free(node
));
2666 parent_type
= isl_schedule_node_get_parent_type(node
);
2667 if (parent_type
== isl_schedule_node_set
||
2668 parent_type
== isl_schedule_node_sequence
)
2669 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2670 "cannot cut child of set or sequence",
2671 return isl_schedule_node_free(node
));
2673 leaf
= isl_schedule_node_get_leaf(node
);
2674 return isl_schedule_node_graft_tree(node
, leaf
);
2677 /* Remove a single node from the schedule tree, attaching the child
2678 * of "node" directly to its parent.
2679 * Return a pointer to this former child or to the leaf the position
2680 * of the original node if there was no child.
2681 * It is not allowed to remove the root of a schedule tree,
2682 * a set or sequence node, a child of a set or sequence node or
2683 * a band node with an anchored subtree.
2685 __isl_give isl_schedule_node
*isl_schedule_node_delete(
2686 __isl_take isl_schedule_node
*node
)
2689 isl_schedule_tree
*tree
;
2690 enum isl_schedule_node_type type
;
2695 if (isl_schedule_node_get_tree_depth(node
) == 0)
2696 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2697 "cannot delete root node",
2698 return isl_schedule_node_free(node
));
2699 n
= isl_schedule_node_n_children(node
);
2701 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2702 "can only delete node with a single child",
2703 return isl_schedule_node_free(node
));
2704 type
= isl_schedule_node_get_parent_type(node
);
2705 if (type
== isl_schedule_node_sequence
|| type
== isl_schedule_node_set
)
2706 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2707 "cannot delete child of set or sequence",
2708 return isl_schedule_node_free(node
));
2709 if (isl_schedule_node_get_type(node
) == isl_schedule_node_band
) {
2712 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2714 return isl_schedule_node_free(node
);
2716 isl_die(isl_schedule_node_get_ctx(node
),
2718 "cannot delete band node with anchored subtree",
2719 return isl_schedule_node_free(node
));
2722 tree
= isl_schedule_node_get_tree(node
);
2723 if (!tree
|| isl_schedule_tree_has_children(tree
)) {
2724 tree
= isl_schedule_tree_child(tree
, 0);
2726 isl_schedule_tree_free(tree
);
2727 tree
= isl_schedule_node_get_leaf(node
);
2729 node
= isl_schedule_node_graft_tree(node
, tree
);
2734 /* Internal data structure for the group_ancestor callback.
2736 * If "finished" is set, then we no longer need to modify
2737 * any further ancestors.
2739 * "contraction" and "expansion" represent the expansion
2740 * that reflects the grouping.
2742 * "domain" contains the domain elements that reach the position
2743 * where the grouping is performed. That is, it is the range
2744 * of the resulting expansion.
2745 * "domain_universe" is the universe of "domain".
2746 * "group" is the set of group elements, i.e., the domain
2747 * of the resulting expansion.
2748 * "group_universe" is the universe of "group".
2750 * "sched" is the schedule for the group elements, in pratice
2751 * an identity mapping on "group_universe".
2752 * "dim" is the dimension of "sched".
2754 struct isl_schedule_group_data
{
2757 isl_union_map
*expansion
;
2758 isl_union_pw_multi_aff
*contraction
;
2760 isl_union_set
*domain
;
2761 isl_union_set
*domain_universe
;
2762 isl_union_set
*group
;
2763 isl_union_set
*group_universe
;
2766 isl_multi_aff
*sched
;
2769 /* Is domain covered by data->domain within data->domain_universe?
2771 static isl_bool
locally_covered_by_domain(__isl_keep isl_union_set
*domain
,
2772 struct isl_schedule_group_data
*data
)
2775 isl_union_set
*test
;
2777 test
= isl_union_set_copy(domain
);
2778 test
= isl_union_set_intersect(test
,
2779 isl_union_set_copy(data
->domain_universe
));
2780 is_subset
= isl_union_set_is_subset(test
, data
->domain
);
2781 isl_union_set_free(test
);
2786 /* Update the band tree root "tree" to refer to the group instances
2787 * in data->group rather than the original domain elements in data->domain.
2788 * "pos" is the position in the original schedule tree where the modified
2789 * "tree" will be attached.
2791 * Add the part of the identity schedule on the group instances data->sched
2792 * that corresponds to this band node to the band schedule.
2793 * If the domain elements that reach the node and that are part
2794 * of data->domain_universe are all elements of data->domain (and therefore
2795 * replaced by the group instances) then this data->domain_universe
2796 * is removed from the domain of the band schedule.
2798 static __isl_give isl_schedule_tree
*group_band(
2799 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2800 struct isl_schedule_group_data
*data
)
2802 isl_union_set
*domain
;
2804 isl_multi_union_pw_aff
*mupa
, *partial
;
2805 isl_bool is_covered
;
2809 domain
= isl_schedule_node_get_domain(pos
);
2810 is_covered
= locally_covered_by_domain(domain
, data
);
2811 if (is_covered
>= 0 && is_covered
) {
2812 domain
= isl_union_set_universe(domain
);
2813 domain
= isl_union_set_subtract(domain
,
2814 isl_union_set_copy(data
->domain_universe
));
2815 tree
= isl_schedule_tree_band_intersect_domain(tree
, domain
);
2817 isl_union_set_free(domain
);
2819 return isl_schedule_tree_free(tree
);
2820 depth
= isl_schedule_node_get_schedule_depth(pos
);
2821 n
= isl_schedule_tree_band_n_member(tree
);
2822 ma
= isl_multi_aff_copy(data
->sched
);
2823 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, depth
);
2824 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, n
, data
->dim
- depth
- n
);
2825 mupa
= isl_multi_union_pw_aff_from_multi_aff(ma
);
2826 partial
= isl_schedule_tree_band_get_partial_schedule(tree
);
2827 has_id
= isl_multi_union_pw_aff_has_tuple_id(partial
, isl_dim_set
);
2829 partial
= isl_multi_union_pw_aff_free(partial
);
2830 } else if (has_id
) {
2832 id
= isl_multi_union_pw_aff_get_tuple_id(partial
, isl_dim_set
);
2833 mupa
= isl_multi_union_pw_aff_set_tuple_id(mupa
,
2836 partial
= isl_multi_union_pw_aff_union_add(partial
, mupa
);
2837 tree
= isl_schedule_tree_band_set_partial_schedule(tree
, partial
);
2842 /* Drop the parameters in "uset" that are not also in "space".
2843 * "n" is the number of parameters in "space".
2845 static __isl_give isl_union_set
*union_set_drop_extra_params(
2846 __isl_take isl_union_set
*uset
, __isl_keep isl_space
*space
, int n
)
2850 uset
= isl_union_set_align_params(uset
, isl_space_copy(space
));
2851 n2
= isl_union_set_dim(uset
, isl_dim_param
);
2853 return isl_union_set_free(uset
);
2854 uset
= isl_union_set_project_out(uset
, isl_dim_param
, n
, n2
- n
);
2859 /* Update the context tree root "tree" to refer to the group instances
2860 * in data->group rather than the original domain elements in data->domain.
2861 * "pos" is the position in the original schedule tree where the modified
2862 * "tree" will be attached.
2864 * We do not actually need to update "tree" since a context node only
2865 * refers to the schedule space. However, we may need to update "data"
2866 * to not refer to any parameters introduced by the context node.
2868 static __isl_give isl_schedule_tree
*group_context(
2869 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2870 struct isl_schedule_group_data
*data
)
2873 isl_union_set
*domain
;
2877 if (isl_schedule_node_get_tree_depth(pos
) == 1)
2880 domain
= isl_schedule_node_get_universe_domain(pos
);
2881 space
= isl_union_set_get_space(domain
);
2882 isl_union_set_free(domain
);
2884 n1
= isl_space_dim(space
, isl_dim_param
);
2885 data
->expansion
= isl_union_map_align_params(data
->expansion
, space
);
2886 n2
= isl_union_map_dim(data
->expansion
, isl_dim_param
);
2888 if (n1
< 0 || n2
< 0)
2889 return isl_schedule_tree_free(tree
);
2893 involves
= isl_union_map_involves_dims(data
->expansion
,
2894 isl_dim_param
, n1
, n2
- n1
);
2896 return isl_schedule_tree_free(tree
);
2898 isl_die(isl_schedule_node_get_ctx(pos
), isl_error_invalid
,
2899 "grouping cannot only refer to global parameters",
2900 return isl_schedule_tree_free(tree
));
2902 data
->expansion
= isl_union_map_project_out(data
->expansion
,
2903 isl_dim_param
, n1
, n2
- n1
);
2904 space
= isl_union_map_get_space(data
->expansion
);
2906 data
->contraction
= isl_union_pw_multi_aff_align_params(
2907 data
->contraction
, isl_space_copy(space
));
2908 n2
= isl_union_pw_multi_aff_dim(data
->contraction
, isl_dim_param
);
2911 isl_union_pw_multi_aff_free(data
->contraction
);
2912 data
->contraction
= isl_union_pw_multi_aff_drop_dims(data
->contraction
,
2913 isl_dim_param
, n1
, n2
- n1
);
2915 data
->domain
= union_set_drop_extra_params(data
->domain
, space
, n1
);
2916 data
->domain_universe
=
2917 union_set_drop_extra_params(data
->domain_universe
, space
, n1
);
2918 data
->group
= union_set_drop_extra_params(data
->group
, space
, n1
);
2919 data
->group_universe
=
2920 union_set_drop_extra_params(data
->group_universe
, space
, n1
);
2922 data
->sched
= isl_multi_aff_align_params(data
->sched
,
2923 isl_space_copy(space
));
2924 n2
= isl_multi_aff_dim(data
->sched
, isl_dim_param
);
2926 data
->sched
= isl_multi_aff_free(data
->sched
);
2927 data
->sched
= isl_multi_aff_drop_dims(data
->sched
,
2928 isl_dim_param
, n1
, n2
- n1
);
2930 isl_space_free(space
);
2935 /* Update the domain tree root "tree" to refer to the group instances
2936 * in data->group rather than the original domain elements in data->domain.
2937 * "pos" is the position in the original schedule tree where the modified
2938 * "tree" will be attached.
2940 * We first double-check that all grouped domain elements are actually
2941 * part of the root domain and then replace those elements by the group
2944 static __isl_give isl_schedule_tree
*group_domain(
2945 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2946 struct isl_schedule_group_data
*data
)
2948 isl_union_set
*domain
;
2951 domain
= isl_schedule_tree_domain_get_domain(tree
);
2952 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2953 isl_union_set_free(domain
);
2955 return isl_schedule_tree_free(tree
);
2957 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2958 "grouped domain should be part of outer domain",
2959 return isl_schedule_tree_free(tree
));
2960 domain
= isl_schedule_tree_domain_get_domain(tree
);
2961 domain
= isl_union_set_subtract(domain
,
2962 isl_union_set_copy(data
->domain
));
2963 domain
= isl_union_set_union(domain
, isl_union_set_copy(data
->group
));
2964 tree
= isl_schedule_tree_domain_set_domain(tree
, domain
);
2969 /* Update the expansion tree root "tree" to refer to the group instances
2970 * in data->group rather than the original domain elements in data->domain.
2971 * "pos" is the position in the original schedule tree where the modified
2972 * "tree" will be attached.
2974 * Let G_1 -> D_1 be the expansion of "tree" and G_2 -> D_2 the newly
2975 * introduced expansion in a descendant of "tree".
2976 * We first double-check that D_2 is a subset of D_1.
2977 * Then we remove D_2 from the range of G_1 -> D_1 and add the mapping
2978 * G_1 -> D_1 . D_2 -> G_2.
2979 * Simmilarly, we restrict the domain of the contraction to the universe
2980 * of the range of the updated expansion and add G_2 -> D_2 . D_1 -> G_1,
2981 * attempting to remove the domain constraints of this additional part.
2983 static __isl_give isl_schedule_tree
*group_expansion(
2984 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2985 struct isl_schedule_group_data
*data
)
2987 isl_union_set
*domain
;
2988 isl_union_map
*expansion
, *umap
;
2989 isl_union_pw_multi_aff
*contraction
, *upma
;
2992 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2993 domain
= isl_union_map_range(expansion
);
2994 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2995 isl_union_set_free(domain
);
2997 return isl_schedule_tree_free(tree
);
2999 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
3000 "grouped domain should be part "
3001 "of outer expansion domain",
3002 return isl_schedule_tree_free(tree
));
3003 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
3004 umap
= isl_union_map_from_union_pw_multi_aff(
3005 isl_union_pw_multi_aff_copy(data
->contraction
));
3006 umap
= isl_union_map_apply_range(expansion
, umap
);
3007 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
3008 expansion
= isl_union_map_subtract_range(expansion
,
3009 isl_union_set_copy(data
->domain
));
3010 expansion
= isl_union_map_union(expansion
, umap
);
3011 umap
= isl_union_map_universe(isl_union_map_copy(expansion
));
3012 domain
= isl_union_map_range(umap
);
3013 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
3014 umap
= isl_union_map_from_union_pw_multi_aff(contraction
);
3015 umap
= isl_union_map_apply_range(isl_union_map_copy(data
->expansion
),
3017 upma
= isl_union_pw_multi_aff_from_union_map(umap
);
3018 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
3019 contraction
= isl_union_pw_multi_aff_intersect_domain(contraction
,
3021 domain
= isl_union_pw_multi_aff_domain(
3022 isl_union_pw_multi_aff_copy(upma
));
3023 upma
= isl_union_pw_multi_aff_gist(upma
, domain
);
3024 contraction
= isl_union_pw_multi_aff_union_add(contraction
, upma
);
3025 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
3026 contraction
, expansion
);
3031 /* Update the tree root "tree" to refer to the group instances
3032 * in data->group rather than the original domain elements in data->domain.
3033 * "pos" is the position in the original schedule tree where the modified
3034 * "tree" will be attached.
3036 * If we have come across a domain or expansion node before (data->finished
3037 * is set), then we no longer need perform any modifications.
3039 * If "tree" is a filter, then we add data->group_universe to the filter.
3040 * We also remove data->domain_universe from the filter if all the domain
3041 * elements in this universe that reach the filter node are part of
3042 * the elements that are being grouped by data->expansion.
3043 * If "tree" is a band, domain or expansion, then it is handled
3044 * in a separate function.
3046 static __isl_give isl_schedule_tree
*group_ancestor(
3047 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
3050 struct isl_schedule_group_data
*data
= user
;
3051 isl_union_set
*domain
;
3052 isl_bool is_covered
;
3055 return isl_schedule_tree_free(tree
);
3060 switch (isl_schedule_tree_get_type(tree
)) {
3061 case isl_schedule_node_error
:
3062 return isl_schedule_tree_free(tree
);
3063 case isl_schedule_node_extension
:
3064 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_unsupported
,
3065 "grouping not allowed in extended tree",
3066 return isl_schedule_tree_free(tree
));
3067 case isl_schedule_node_band
:
3068 tree
= group_band(tree
, pos
, data
);
3070 case isl_schedule_node_context
:
3071 tree
= group_context(tree
, pos
, data
);
3073 case isl_schedule_node_domain
:
3074 tree
= group_domain(tree
, pos
, data
);
3077 case isl_schedule_node_filter
:
3078 domain
= isl_schedule_node_get_domain(pos
);
3079 is_covered
= locally_covered_by_domain(domain
, data
);
3080 isl_union_set_free(domain
);
3082 return isl_schedule_tree_free(tree
);
3083 domain
= isl_schedule_tree_filter_get_filter(tree
);
3085 domain
= isl_union_set_subtract(domain
,
3086 isl_union_set_copy(data
->domain_universe
));
3087 domain
= isl_union_set_union(domain
,
3088 isl_union_set_copy(data
->group_universe
));
3089 tree
= isl_schedule_tree_filter_set_filter(tree
, domain
);
3091 case isl_schedule_node_expansion
:
3092 tree
= group_expansion(tree
, pos
, data
);
3095 case isl_schedule_node_leaf
:
3096 case isl_schedule_node_guard
:
3097 case isl_schedule_node_mark
:
3098 case isl_schedule_node_sequence
:
3099 case isl_schedule_node_set
:
3106 /* Group the domain elements that reach "node" into instances
3107 * of a single statement with identifier "group_id".
3108 * In particular, group the domain elements according to their
3111 * That is, introduce an expansion node with as contraction
3112 * the prefix schedule (with the target space replaced by "group_id")
3113 * and as expansion the inverse of this contraction (with its range
3114 * intersected with the domain elements that reach "node").
3115 * The outer nodes are then modified to refer to the group instances
3116 * instead of the original domain elements.
3118 * No instance of "group_id" is allowed to reach "node" prior
3120 * No ancestor of "node" is allowed to be an extension node.
3122 * Return a pointer to original node in tree, i.e., the child
3123 * of the newly introduced expansion node.
3125 __isl_give isl_schedule_node
*isl_schedule_node_group(
3126 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*group_id
)
3128 struct isl_schedule_group_data data
= { 0 };
3130 isl_union_set
*domain
;
3131 isl_union_pw_multi_aff
*contraction
;
3132 isl_union_map
*expansion
;
3135 if (!node
|| !group_id
)
3137 if (check_insert(node
) < 0)
3140 domain
= isl_schedule_node_get_domain(node
);
3141 data
.domain
= isl_union_set_copy(domain
);
3142 data
.domain_universe
= isl_union_set_copy(domain
);
3143 data
.domain_universe
= isl_union_set_universe(data
.domain_universe
);
3145 data
.dim
= isl_schedule_node_get_schedule_depth(node
);
3146 if (data
.dim
== 0) {
3149 isl_union_set
*group
;
3150 isl_union_map
*univ
;
3152 ctx
= isl_schedule_node_get_ctx(node
);
3153 space
= isl_space_set_alloc(ctx
, 0, 0);
3154 space
= isl_space_set_tuple_id(space
, isl_dim_set
, group_id
);
3155 set
= isl_set_universe(isl_space_copy(space
));
3156 group
= isl_union_set_from_set(set
);
3157 expansion
= isl_union_map_from_domain_and_range(domain
, group
);
3158 univ
= isl_union_map_universe(isl_union_map_copy(expansion
));
3159 contraction
= isl_union_pw_multi_aff_from_union_map(univ
);
3160 expansion
= isl_union_map_reverse(expansion
);
3162 isl_multi_union_pw_aff
*prefix
;
3163 isl_union_set
*univ
;
3166 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node
);
3167 prefix
= isl_multi_union_pw_aff_set_tuple_id(prefix
,
3168 isl_dim_set
, group_id
);
3169 space
= isl_multi_union_pw_aff_get_space(prefix
);
3170 contraction
= isl_union_pw_multi_aff_from_multi_union_pw_aff(
3172 univ
= isl_union_set_universe(isl_union_set_copy(domain
));
3174 isl_union_pw_multi_aff_intersect_domain(contraction
, univ
);
3175 expansion
= isl_union_map_from_union_pw_multi_aff(
3176 isl_union_pw_multi_aff_copy(contraction
));
3177 expansion
= isl_union_map_reverse(expansion
);
3178 expansion
= isl_union_map_intersect_range(expansion
, domain
);
3180 space
= isl_space_map_from_set(space
);
3181 data
.sched
= isl_multi_aff_identity(space
);
3182 data
.group
= isl_union_map_domain(isl_union_map_copy(expansion
));
3183 data
.group
= isl_union_set_coalesce(data
.group
);
3184 data
.group_universe
= isl_union_set_copy(data
.group
);
3185 data
.group_universe
= isl_union_set_universe(data
.group_universe
);
3186 data
.expansion
= isl_union_map_copy(expansion
);
3187 data
.contraction
= isl_union_pw_multi_aff_copy(contraction
);
3188 node
= isl_schedule_node_insert_expansion(node
, contraction
, expansion
);
3190 disjoint
= isl_union_set_is_disjoint(data
.domain_universe
,
3191 data
.group_universe
);
3193 node
= update_ancestors(node
, &group_ancestor
, &data
);
3195 isl_union_set_free(data
.domain
);
3196 isl_union_set_free(data
.domain_universe
);
3197 isl_union_set_free(data
.group
);
3198 isl_union_set_free(data
.group_universe
);
3199 isl_multi_aff_free(data
.sched
);
3200 isl_union_map_free(data
.expansion
);
3201 isl_union_pw_multi_aff_free(data
.contraction
);
3203 node
= isl_schedule_node_child(node
, 0);
3205 if (!node
|| disjoint
< 0)
3206 return isl_schedule_node_free(node
);
3208 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3209 "group instances already reach node",
3210 return isl_schedule_node_free(node
));
3214 isl_schedule_node_free(node
);
3215 isl_id_free(group_id
);
3219 /* Compute the gist of the given band node with respect to "context".
3221 __isl_give isl_schedule_node
*isl_schedule_node_band_gist(
3222 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3224 isl_schedule_tree
*tree
;
3226 tree
= isl_schedule_node_get_tree(node
);
3227 tree
= isl_schedule_tree_band_gist(tree
, context
);
3228 return isl_schedule_node_graft_tree(node
, tree
);
3231 /* Internal data structure for isl_schedule_node_gist.
3232 * "n_expansion" is the number of outer expansion nodes
3233 * with respect to the current position
3234 * "filters" contains an element for each outer filter, expansion or
3235 * extension node with respect to the current position, each representing
3236 * the intersection of the previous element and the filter on the filter node
3237 * or the expansion/extension of the previous element.
3238 * The first element in the original context passed to isl_schedule_node_gist.
3240 struct isl_node_gist_data
{
3242 isl_union_set_list
*filters
;
3245 /* Enter the expansion node "node" during a isl_schedule_node_gist traversal.
3247 * In particular, add an extra element to data->filters containing
3248 * the expansion of the previous element and replace the expansion
3249 * and contraction on "node" by the gist with respect to these filters.
3250 * Also keep track of the fact that we have entered another expansion.
3252 static __isl_give isl_schedule_node
*gist_enter_expansion(
3253 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3256 isl_union_set
*inner
;
3257 isl_union_map
*expansion
;
3258 isl_union_pw_multi_aff
*contraction
;
3260 data
->n_expansion
++;
3262 n
= isl_union_set_list_n_union_set(data
->filters
);
3263 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3264 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3265 inner
= isl_union_set_apply(inner
, expansion
);
3267 contraction
= isl_schedule_node_expansion_get_contraction(node
);
3268 contraction
= isl_union_pw_multi_aff_gist(contraction
,
3269 isl_union_set_copy(inner
));
3271 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
3273 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3274 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3275 expansion
= isl_union_map_gist_domain(expansion
, inner
);
3276 node
= isl_schedule_node_expansion_set_contraction_and_expansion(node
,
3277 contraction
, expansion
);
3282 /* Leave the expansion node "node" during a isl_schedule_node_gist traversal.
3284 * In particular, remove the element in data->filters that was added by
3285 * gist_enter_expansion and decrement the number of outer expansions.
3287 * The expansion has already been simplified in gist_enter_expansion.
3288 * If this simplification results in an identity expansion, then
3289 * it is removed here.
3291 static __isl_give isl_schedule_node
*gist_leave_expansion(
3292 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3296 isl_union_map
*expansion
;
3298 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3299 identity
= isl_union_map_is_identity(expansion
);
3300 isl_union_map_free(expansion
);
3303 node
= isl_schedule_node_free(node
);
3305 node
= isl_schedule_node_delete(node
);
3307 n
= isl_union_set_list_n_union_set(data
->filters
);
3308 data
->filters
= isl_union_set_list_drop(data
->filters
, n
- 1, 1);
3310 data
->n_expansion
--;
3315 /* Enter the extension node "node" during a isl_schedule_node_gist traversal.
3317 * In particular, add an extra element to data->filters containing
3318 * the union of the previous element with the additional domain elements
3319 * introduced by the extension.
3321 static __isl_give isl_schedule_node
*gist_enter_extension(
3322 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3325 isl_union_set
*inner
, *extra
;
3326 isl_union_map
*extension
;
3328 n
= isl_union_set_list_n_union_set(data
->filters
);
3329 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3330 extension
= isl_schedule_node_extension_get_extension(node
);
3331 extra
= isl_union_map_range(extension
);
3332 inner
= isl_union_set_union(inner
, extra
);
3334 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
3339 /* Can we finish gisting at this node?
3340 * That is, is the filter on the current filter node a subset of
3341 * the original context passed to isl_schedule_node_gist?
3342 * If we have gone through any expansions, then we cannot perform
3343 * this test since the current domain elements are incomparable
3344 * to the domain elements in the original context.
3346 static isl_bool
gist_done(__isl_keep isl_schedule_node
*node
,
3347 struct isl_node_gist_data
*data
)
3349 isl_union_set
*filter
, *outer
;
3352 if (data
->n_expansion
!= 0)
3353 return isl_bool_false
;
3355 filter
= isl_schedule_node_filter_get_filter(node
);
3356 outer
= isl_union_set_list_get_union_set(data
->filters
, 0);
3357 subset
= isl_union_set_is_subset(filter
, outer
);
3358 isl_union_set_free(outer
);
3359 isl_union_set_free(filter
);
3364 /* Callback for "traverse" to enter a node and to move
3365 * to the deepest initial subtree that should be traversed
3366 * by isl_schedule_node_gist.
3368 * The "filters" list is extended by one element each time
3369 * we come across a filter node by the result of intersecting
3370 * the last element in the list with the filter on the filter node.
3372 * If the filter on the current filter node is a subset of
3373 * the original context passed to isl_schedule_node_gist,
3374 * then there is no need to go into its subtree since it cannot
3375 * be further simplified by the context. The "filters" list is
3376 * still extended for consistency, but the actual value of the
3377 * added element is immaterial since it will not be used.
3379 * Otherwise, the filter on the current filter node is replaced by
3380 * the gist of the original filter with respect to the intersection
3381 * of the original context with the intermediate filters.
3383 * If the new element in the "filters" list is empty, then no elements
3384 * can reach the descendants of the current filter node. The subtree
3385 * underneath the filter node is therefore removed.
3387 * Each expansion node we come across is handled by
3388 * gist_enter_expansion.
3390 * Each extension node we come across is handled by
3391 * gist_enter_extension.
3393 static __isl_give isl_schedule_node
*gist_enter(
3394 __isl_take isl_schedule_node
*node
, void *user
)
3396 struct isl_node_gist_data
*data
= user
;
3399 isl_union_set
*filter
, *inner
;
3400 isl_bool done
, empty
;
3403 switch (isl_schedule_node_get_type(node
)) {
3404 case isl_schedule_node_error
:
3405 return isl_schedule_node_free(node
);
3406 case isl_schedule_node_expansion
:
3407 node
= gist_enter_expansion(node
, data
);
3409 case isl_schedule_node_extension
:
3410 node
= gist_enter_extension(node
, data
);
3412 case isl_schedule_node_band
:
3413 case isl_schedule_node_context
:
3414 case isl_schedule_node_domain
:
3415 case isl_schedule_node_guard
:
3416 case isl_schedule_node_leaf
:
3417 case isl_schedule_node_mark
:
3418 case isl_schedule_node_sequence
:
3419 case isl_schedule_node_set
:
3421 case isl_schedule_node_filter
:
3424 done
= gist_done(node
, data
);
3425 filter
= isl_schedule_node_filter_get_filter(node
);
3426 if (done
< 0 || done
) {
3427 data
->filters
= isl_union_set_list_add(data
->filters
,
3430 return isl_schedule_node_free(node
);
3433 n
= isl_union_set_list_n_union_set(data
->filters
);
3434 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3435 filter
= isl_union_set_gist(filter
, isl_union_set_copy(inner
));
3436 node
= isl_schedule_node_filter_set_filter(node
,
3437 isl_union_set_copy(filter
));
3438 filter
= isl_union_set_intersect(filter
, inner
);
3439 empty
= isl_union_set_is_empty(filter
);
3440 data
->filters
= isl_union_set_list_add(data
->filters
, filter
);
3442 return isl_schedule_node_free(node
);
3445 node
= isl_schedule_node_child(node
, 0);
3446 node
= isl_schedule_node_cut(node
);
3447 node
= isl_schedule_node_parent(node
);
3449 } while (isl_schedule_node_has_children(node
) &&
3450 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3455 /* Callback for "traverse" to leave a node for isl_schedule_node_gist.
3457 * In particular, if the current node is a filter node, then we remove
3458 * the element on the "filters" list that was added when we entered
3459 * the node. There is no need to compute any gist here, since we
3460 * already did that when we entered the node.
3462 * Expansion nodes are handled by gist_leave_expansion.
3464 * If the current node is an extension, then remove the element
3465 * in data->filters that was added by gist_enter_extension.
3467 * If the current node is a band node, then we compute the gist of
3468 * the band node with respect to the intersection of the original context
3469 * and the intermediate filters.
3471 * If the current node is a sequence or set node, then some of
3472 * the filter children may have become empty and so they are removed.
3473 * If only one child is left, then the set or sequence node along with
3474 * the single remaining child filter is removed. The filter can be
3475 * removed because the filters on a sequence or set node are supposed
3476 * to partition the incoming domain instances.
3477 * In principle, it should then be impossible for there to be zero
3478 * remaining children, but should this happen, we replace the entire
3479 * subtree with an empty filter.
3481 static __isl_give isl_schedule_node
*gist_leave(
3482 __isl_take isl_schedule_node
*node
, void *user
)
3484 struct isl_node_gist_data
*data
= user
;
3485 isl_schedule_tree
*tree
;
3487 isl_union_set
*filter
;
3489 switch (isl_schedule_node_get_type(node
)) {
3490 case isl_schedule_node_error
:
3491 return isl_schedule_node_free(node
);
3492 case isl_schedule_node_expansion
:
3493 node
= gist_leave_expansion(node
, data
);
3495 case isl_schedule_node_extension
:
3496 case isl_schedule_node_filter
:
3497 n
= isl_union_set_list_n_union_set(data
->filters
);
3498 data
->filters
= isl_union_set_list_drop(data
->filters
,
3501 case isl_schedule_node_band
:
3502 n
= isl_union_set_list_n_union_set(data
->filters
);
3503 filter
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3504 node
= isl_schedule_node_band_gist(node
, filter
);
3506 case isl_schedule_node_set
:
3507 case isl_schedule_node_sequence
:
3508 tree
= isl_schedule_node_get_tree(node
);
3509 n
= isl_schedule_tree_n_children(tree
);
3510 for (i
= n
- 1; i
>= 0; --i
) {
3511 isl_schedule_tree
*child
;
3512 isl_union_set
*filter
;
3515 child
= isl_schedule_tree_get_child(tree
, i
);
3516 filter
= isl_schedule_tree_filter_get_filter(child
);
3517 empty
= isl_union_set_is_empty(filter
);
3518 isl_union_set_free(filter
);
3519 isl_schedule_tree_free(child
);
3521 tree
= isl_schedule_tree_free(tree
);
3523 tree
= isl_schedule_tree_drop_child(tree
, i
);
3525 n
= isl_schedule_tree_n_children(tree
);
3526 node
= isl_schedule_node_graft_tree(node
, tree
);
3528 node
= isl_schedule_node_delete(node
);
3529 node
= isl_schedule_node_delete(node
);
3530 } else if (n
== 0) {
3534 isl_union_set_list_get_union_set(data
->filters
, 0);
3535 space
= isl_union_set_get_space(filter
);
3536 isl_union_set_free(filter
);
3537 filter
= isl_union_set_empty(space
);
3538 node
= isl_schedule_node_cut(node
);
3539 node
= isl_schedule_node_insert_filter(node
, filter
);
3542 case isl_schedule_node_context
:
3543 case isl_schedule_node_domain
:
3544 case isl_schedule_node_guard
:
3545 case isl_schedule_node_leaf
:
3546 case isl_schedule_node_mark
:
3553 /* Compute the gist of the subtree at "node" with respect to
3554 * the reaching domain elements in "context".
3555 * In particular, compute the gist of all band and filter nodes
3556 * in the subtree with respect to "context". Children of set or sequence
3557 * nodes that end up with an empty filter are removed completely.
3559 * We keep track of the intersection of "context" with all outer filters
3560 * of the current node within the subtree in the final element of "filters".
3561 * Initially, this list contains the single element "context" and it is
3562 * extended or shortened each time we enter or leave a filter node.
3564 __isl_give isl_schedule_node
*isl_schedule_node_gist(
3565 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3567 struct isl_node_gist_data data
;
3569 data
.n_expansion
= 0;
3570 data
.filters
= isl_union_set_list_from_union_set(context
);
3571 node
= traverse(node
, &gist_enter
, &gist_leave
, &data
);
3572 isl_union_set_list_free(data
.filters
);
3576 /* Intersect the domain of domain node "node" with "domain".
3578 * If the domain of "node" is already a subset of "domain",
3579 * then nothing needs to be changed.
3581 * Otherwise, we replace the domain of the domain node by the intersection
3582 * and simplify the subtree rooted at "node" with respect to this intersection.
3584 __isl_give isl_schedule_node
*isl_schedule_node_domain_intersect_domain(
3585 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
)
3587 isl_schedule_tree
*tree
;
3588 isl_union_set
*uset
;
3591 if (!node
|| !domain
)
3594 uset
= isl_schedule_tree_domain_get_domain(node
->tree
);
3595 is_subset
= isl_union_set_is_subset(uset
, domain
);
3596 isl_union_set_free(uset
);
3600 isl_union_set_free(domain
);
3604 tree
= isl_schedule_tree_copy(node
->tree
);
3605 uset
= isl_schedule_tree_domain_get_domain(tree
);
3606 uset
= isl_union_set_intersect(uset
, domain
);
3607 tree
= isl_schedule_tree_domain_set_domain(tree
,
3608 isl_union_set_copy(uset
));
3609 node
= isl_schedule_node_graft_tree(node
, tree
);
3611 node
= isl_schedule_node_child(node
, 0);
3612 node
= isl_schedule_node_gist(node
, uset
);
3613 node
= isl_schedule_node_parent(node
);
3617 isl_schedule_node_free(node
);
3618 isl_union_set_free(domain
);
3622 /* Replace the domain of domain node "node" with the gist
3623 * of the original domain with respect to the parameter domain "context".
3625 __isl_give isl_schedule_node
*isl_schedule_node_domain_gist_params(
3626 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
3628 isl_union_set
*domain
;
3629 isl_schedule_tree
*tree
;
3631 if (!node
|| !context
)
3634 tree
= isl_schedule_tree_copy(node
->tree
);
3635 domain
= isl_schedule_tree_domain_get_domain(node
->tree
);
3636 domain
= isl_union_set_gist_params(domain
, context
);
3637 tree
= isl_schedule_tree_domain_set_domain(tree
, domain
);
3638 node
= isl_schedule_node_graft_tree(node
, tree
);
3642 isl_schedule_node_free(node
);
3643 isl_set_free(context
);
3647 /* Internal data structure for isl_schedule_node_get_subtree_expansion.
3648 * "expansions" contains a list of accumulated expansions
3649 * for each outer expansion, set or sequence node. The first element
3650 * in the list is an identity mapping on the reaching domain elements.
3651 * "res" collects the results.
3653 struct isl_subtree_expansion_data
{
3654 isl_union_map_list
*expansions
;
3658 /* Callback for "traverse" to enter a node and to move
3659 * to the deepest initial subtree that should be traversed
3660 * by isl_schedule_node_get_subtree_expansion.
3662 * Whenever we come across an expansion node, the last element
3663 * of data->expansions is combined with the expansion
3664 * on the expansion node.
3666 * Whenever we come across a filter node that is the child
3667 * of a set or sequence node, data->expansions is extended
3668 * with a new element that restricts the previous element
3669 * to the elements selected by the filter.
3670 * The previous element can then be reused while backtracking.
3672 static __isl_give isl_schedule_node
*subtree_expansion_enter(
3673 __isl_take isl_schedule_node
*node
, void *user
)
3675 struct isl_subtree_expansion_data
*data
= user
;
3678 enum isl_schedule_node_type type
;
3679 isl_union_set
*filter
;
3680 isl_union_map
*inner
, *expansion
;
3683 switch (isl_schedule_node_get_type(node
)) {
3684 case isl_schedule_node_error
:
3685 return isl_schedule_node_free(node
);
3686 case isl_schedule_node_filter
:
3687 type
= isl_schedule_node_get_parent_type(node
);
3688 if (type
!= isl_schedule_node_set
&&
3689 type
!= isl_schedule_node_sequence
)
3691 filter
= isl_schedule_node_filter_get_filter(node
);
3692 n
= isl_union_map_list_n_union_map(data
->expansions
);
3694 isl_union_map_list_get_union_map(data
->expansions
,
3696 inner
= isl_union_map_intersect_range(inner
, filter
);
3698 isl_union_map_list_add(data
->expansions
, inner
);
3700 case isl_schedule_node_expansion
:
3701 n
= isl_union_map_list_n_union_map(data
->expansions
);
3703 isl_schedule_node_expansion_get_expansion(node
);
3705 isl_union_map_list_get_union_map(data
->expansions
,
3707 inner
= isl_union_map_apply_range(inner
, expansion
);
3709 isl_union_map_list_set_union_map(data
->expansions
,
3712 case isl_schedule_node_band
:
3713 case isl_schedule_node_context
:
3714 case isl_schedule_node_domain
:
3715 case isl_schedule_node_extension
:
3716 case isl_schedule_node_guard
:
3717 case isl_schedule_node_leaf
:
3718 case isl_schedule_node_mark
:
3719 case isl_schedule_node_sequence
:
3720 case isl_schedule_node_set
:
3723 } while (isl_schedule_node_has_children(node
) &&
3724 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3729 /* Callback for "traverse" to leave a node for
3730 * isl_schedule_node_get_subtree_expansion.
3732 * If we come across a filter node that is the child
3733 * of a set or sequence node, then we remove the element
3734 * of data->expansions that was added in subtree_expansion_enter.
3736 * If we reach a leaf node, then the accumulated expansion is
3737 * added to data->res.
3739 static __isl_give isl_schedule_node
*subtree_expansion_leave(
3740 __isl_take isl_schedule_node
*node
, void *user
)
3742 struct isl_subtree_expansion_data
*data
= user
;
3744 isl_union_map
*inner
;
3745 enum isl_schedule_node_type type
;
3747 switch (isl_schedule_node_get_type(node
)) {
3748 case isl_schedule_node_error
:
3749 return isl_schedule_node_free(node
);
3750 case isl_schedule_node_filter
:
3751 type
= isl_schedule_node_get_parent_type(node
);
3752 if (type
!= isl_schedule_node_set
&&
3753 type
!= isl_schedule_node_sequence
)
3755 n
= isl_union_map_list_n_union_map(data
->expansions
);
3756 data
->expansions
= isl_union_map_list_drop(data
->expansions
,
3759 case isl_schedule_node_leaf
:
3760 n
= isl_union_map_list_n_union_map(data
->expansions
);
3761 inner
= isl_union_map_list_get_union_map(data
->expansions
,
3763 data
->res
= isl_union_map_union(data
->res
, inner
);
3765 case isl_schedule_node_band
:
3766 case isl_schedule_node_context
:
3767 case isl_schedule_node_domain
:
3768 case isl_schedule_node_expansion
:
3769 case isl_schedule_node_extension
:
3770 case isl_schedule_node_guard
:
3771 case isl_schedule_node_mark
:
3772 case isl_schedule_node_sequence
:
3773 case isl_schedule_node_set
:
3780 /* Return a mapping from the domain elements that reach "node"
3781 * to the corresponding domain elements in the leaves of the subtree
3782 * rooted at "node" obtained by composing the intermediate expansions.
3784 * We start out with an identity mapping between the domain elements
3785 * that reach "node" and compose it with all the expansions
3786 * on a path from "node" to a leaf while traversing the subtree.
3787 * Within the children of an a sequence or set node, the
3788 * accumulated expansion is restricted to the elements selected
3789 * by the filter child.
3791 __isl_give isl_union_map
*isl_schedule_node_get_subtree_expansion(
3792 __isl_keep isl_schedule_node
*node
)
3794 struct isl_subtree_expansion_data data
;
3796 isl_union_set
*domain
;
3797 isl_union_map
*expansion
;
3802 domain
= isl_schedule_node_get_universe_domain(node
);
3803 space
= isl_union_set_get_space(domain
);
3804 expansion
= isl_union_set_identity(domain
);
3805 data
.res
= isl_union_map_empty(space
);
3806 data
.expansions
= isl_union_map_list_from_union_map(expansion
);
3808 node
= isl_schedule_node_copy(node
);
3809 node
= traverse(node
, &subtree_expansion_enter
,
3810 &subtree_expansion_leave
, &data
);
3812 data
.res
= isl_union_map_free(data
.res
);
3813 isl_schedule_node_free(node
);
3815 isl_union_map_list_free(data
.expansions
);
3820 /* Internal data structure for isl_schedule_node_get_subtree_contraction.
3821 * "contractions" contains a list of accumulated contractions
3822 * for each outer expansion, set or sequence node. The first element
3823 * in the list is an identity mapping on the reaching domain elements.
3824 * "res" collects the results.
3826 struct isl_subtree_contraction_data
{
3827 isl_union_pw_multi_aff_list
*contractions
;
3828 isl_union_pw_multi_aff
*res
;
3831 /* Callback for "traverse" to enter a node and to move
3832 * to the deepest initial subtree that should be traversed
3833 * by isl_schedule_node_get_subtree_contraction.
3835 * Whenever we come across an expansion node, the last element
3836 * of data->contractions is combined with the contraction
3837 * on the expansion node.
3839 * Whenever we come across a filter node that is the child
3840 * of a set or sequence node, data->contractions is extended
3841 * with a new element that restricts the previous element
3842 * to the elements selected by the filter.
3843 * The previous element can then be reused while backtracking.
3845 static __isl_give isl_schedule_node
*subtree_contraction_enter(
3846 __isl_take isl_schedule_node
*node
, void *user
)
3848 struct isl_subtree_contraction_data
*data
= user
;
3851 enum isl_schedule_node_type type
;
3852 isl_union_set
*filter
;
3853 isl_union_pw_multi_aff
*inner
, *contraction
;
3856 switch (isl_schedule_node_get_type(node
)) {
3857 case isl_schedule_node_error
:
3858 return isl_schedule_node_free(node
);
3859 case isl_schedule_node_filter
:
3860 type
= isl_schedule_node_get_parent_type(node
);
3861 if (type
!= isl_schedule_node_set
&&
3862 type
!= isl_schedule_node_sequence
)
3864 filter
= isl_schedule_node_filter_get_filter(node
);
3865 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3866 data
->contractions
);
3868 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3869 data
->contractions
, n
- 1);
3870 inner
= isl_union_pw_multi_aff_intersect_domain(inner
,
3872 data
->contractions
=
3873 isl_union_pw_multi_aff_list_add(data
->contractions
,
3876 case isl_schedule_node_expansion
:
3877 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3878 data
->contractions
);
3880 isl_schedule_node_expansion_get_contraction(node
);
3882 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3883 data
->contractions
, n
- 1);
3885 isl_union_pw_multi_aff_pullback_union_pw_multi_aff(
3886 inner
, contraction
);
3887 data
->contractions
=
3888 isl_union_pw_multi_aff_list_set_union_pw_multi_aff(
3889 data
->contractions
, n
- 1, inner
);
3891 case isl_schedule_node_band
:
3892 case isl_schedule_node_context
:
3893 case isl_schedule_node_domain
:
3894 case isl_schedule_node_extension
:
3895 case isl_schedule_node_guard
:
3896 case isl_schedule_node_leaf
:
3897 case isl_schedule_node_mark
:
3898 case isl_schedule_node_sequence
:
3899 case isl_schedule_node_set
:
3902 } while (isl_schedule_node_has_children(node
) &&
3903 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3908 /* Callback for "traverse" to leave a node for
3909 * isl_schedule_node_get_subtree_contraction.
3911 * If we come across a filter node that is the child
3912 * of a set or sequence node, then we remove the element
3913 * of data->contractions that was added in subtree_contraction_enter.
3915 * If we reach a leaf node, then the accumulated contraction is
3916 * added to data->res.
3918 static __isl_give isl_schedule_node
*subtree_contraction_leave(
3919 __isl_take isl_schedule_node
*node
, void *user
)
3921 struct isl_subtree_contraction_data
*data
= user
;
3923 isl_union_pw_multi_aff
*inner
;
3924 enum isl_schedule_node_type type
;
3926 switch (isl_schedule_node_get_type(node
)) {
3927 case isl_schedule_node_error
:
3928 return isl_schedule_node_free(node
);
3929 case isl_schedule_node_filter
:
3930 type
= isl_schedule_node_get_parent_type(node
);
3931 if (type
!= isl_schedule_node_set
&&
3932 type
!= isl_schedule_node_sequence
)
3934 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3935 data
->contractions
);
3936 data
->contractions
=
3937 isl_union_pw_multi_aff_list_drop(data
->contractions
,
3940 case isl_schedule_node_leaf
:
3941 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3942 data
->contractions
);
3943 inner
= isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3944 data
->contractions
, n
- 1);
3945 data
->res
= isl_union_pw_multi_aff_union_add(data
->res
, inner
);
3947 case isl_schedule_node_band
:
3948 case isl_schedule_node_context
:
3949 case isl_schedule_node_domain
:
3950 case isl_schedule_node_expansion
:
3951 case isl_schedule_node_extension
:
3952 case isl_schedule_node_guard
:
3953 case isl_schedule_node_mark
:
3954 case isl_schedule_node_sequence
:
3955 case isl_schedule_node_set
:
3962 /* Return a mapping from the domain elements in the leaves of the subtree
3963 * rooted at "node" to the corresponding domain elements that reach "node"
3964 * obtained by composing the intermediate contractions.
3966 * We start out with an identity mapping between the domain elements
3967 * that reach "node" and compose it with all the contractions
3968 * on a path from "node" to a leaf while traversing the subtree.
3969 * Within the children of an a sequence or set node, the
3970 * accumulated contraction is restricted to the elements selected
3971 * by the filter child.
3973 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_get_subtree_contraction(
3974 __isl_keep isl_schedule_node
*node
)
3976 struct isl_subtree_contraction_data data
;
3978 isl_union_set
*domain
;
3979 isl_union_pw_multi_aff
*contraction
;
3984 domain
= isl_schedule_node_get_universe_domain(node
);
3985 space
= isl_union_set_get_space(domain
);
3986 contraction
= isl_union_set_identity_union_pw_multi_aff(domain
);
3987 data
.res
= isl_union_pw_multi_aff_empty(space
);
3989 isl_union_pw_multi_aff_list_from_union_pw_multi_aff(contraction
);
3991 node
= isl_schedule_node_copy(node
);
3992 node
= traverse(node
, &subtree_contraction_enter
,
3993 &subtree_contraction_leave
, &data
);
3995 data
.res
= isl_union_pw_multi_aff_free(data
.res
);
3996 isl_schedule_node_free(node
);
3998 isl_union_pw_multi_aff_list_free(data
.contractions
);
4003 /* Do the nearest "n" ancestors of "node" have the types given in "types"
4004 * (starting at the parent of "node")?
4006 static isl_bool
has_ancestors(__isl_keep isl_schedule_node
*node
,
4007 int n
, enum isl_schedule_node_type
*types
)
4012 return isl_bool_error
;
4014 n_ancestor
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
4016 return isl_bool_false
;
4018 for (i
= 0; i
< n
; ++i
) {
4019 isl_schedule_tree
*tree
;
4022 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
4023 n_ancestor
- 1 - i
);
4025 return isl_bool_error
;
4026 correct_type
= isl_schedule_tree_get_type(tree
) == types
[i
];
4027 isl_schedule_tree_free(tree
);
4029 return isl_bool_false
;
4032 return isl_bool_true
;
4035 /* Given a node "node" that appears in an extension (i.e., it is the child
4036 * of a filter in a sequence inside an extension node), are the spaces
4037 * of the extension specified by "extension" disjoint from those
4038 * of both the original extension and the domain elements that reach
4039 * that original extension?
4041 static int is_disjoint_extension(__isl_keep isl_schedule_node
*node
,
4042 __isl_keep isl_union_map
*extension
)
4045 isl_union_set
*domain
;
4048 node
= isl_schedule_node_copy(node
);
4049 node
= isl_schedule_node_parent(node
);
4050 node
= isl_schedule_node_parent(node
);
4051 node
= isl_schedule_node_parent(node
);
4052 old
= isl_schedule_node_extension_get_extension(node
);
4053 domain
= isl_schedule_node_get_universe_domain(node
);
4054 isl_schedule_node_free(node
);
4055 old
= isl_union_map_universe(old
);
4056 domain
= isl_union_set_union(domain
, isl_union_map_range(old
));
4057 extension
= isl_union_map_copy(extension
);
4058 extension
= isl_union_map_intersect_range(extension
, domain
);
4059 empty
= isl_union_map_is_empty(extension
);
4060 isl_union_map_free(extension
);
4065 /* Given a node "node" that is governed by an extension node, extend
4066 * that extension node with "extension".
4068 * In particular, "node" is the child of a filter in a sequence that
4069 * is in turn a child of an extension node. Extend that extension node
4072 * Return a pointer to the parent of the original node (i.e., a filter).
4074 static __isl_give isl_schedule_node
*extend_extension(
4075 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
4079 isl_union_map
*node_extension
;
4081 node
= isl_schedule_node_parent(node
);
4082 pos
= isl_schedule_node_get_child_position(node
);
4083 node
= isl_schedule_node_parent(node
);
4084 node
= isl_schedule_node_parent(node
);
4085 node_extension
= isl_schedule_node_extension_get_extension(node
);
4086 disjoint
= isl_union_map_is_disjoint(extension
, node_extension
);
4087 extension
= isl_union_map_union(extension
, node_extension
);
4088 node
= isl_schedule_node_extension_set_extension(node
, extension
);
4089 node
= isl_schedule_node_child(node
, 0);
4090 node
= isl_schedule_node_child(node
, pos
);
4093 return isl_schedule_node_free(node
);
4097 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4098 "extension domain should be disjoint from earlier "
4099 "extensions", return isl_schedule_node_free(node
));
4104 /* Return the universe of "uset" if this universe is disjoint from "ref".
4105 * Otherwise, return "uset".
4107 * Also check if "uset" itself is disjoint from "ref", reporting
4108 * an error if it is not.
4110 static __isl_give isl_union_set
*replace_by_universe_if_disjoint(
4111 __isl_take isl_union_set
*uset
, __isl_keep isl_union_set
*ref
)
4114 isl_union_set
*universe
;
4116 disjoint
= isl_union_set_is_disjoint(uset
, ref
);
4118 return isl_union_set_free(uset
);
4120 isl_die(isl_union_set_get_ctx(uset
), isl_error_invalid
,
4121 "extension domain should be disjoint from "
4122 "current domain", return isl_union_set_free(uset
));
4124 universe
= isl_union_set_universe(isl_union_set_copy(uset
));
4125 disjoint
= isl_union_set_is_disjoint(universe
, ref
);
4126 if (disjoint
>= 0 && disjoint
) {
4127 isl_union_set_free(uset
);
4130 isl_union_set_free(universe
);
4133 return isl_union_set_free(uset
);
4137 /* Insert an extension node on top of "node" with extension "extension".
4138 * In addition, insert a filter that separates node from the extension
4139 * between the extension node and "node".
4140 * Return a pointer to the inserted filter node.
4142 * If "node" already appears in an extension (i.e., if it is the child
4143 * of a filter in a sequence inside an extension node), then extend that
4144 * extension with "extension" instead.
4145 * In this case, a pointer to the original filter node is returned.
4146 * Note that if some of the elements in the new extension live in the
4147 * same space as those of the original extension or the domain elements
4148 * reaching the original extension, then we insert a new extension anyway.
4149 * Otherwise, we would have to adjust the filters in the sequence child
4150 * of the extension to ensure that the elements in the new extension
4153 static __isl_give isl_schedule_node
*insert_extension(
4154 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
4156 enum isl_schedule_node_type ancestors
[] =
4157 { isl_schedule_node_filter
, isl_schedule_node_sequence
,
4158 isl_schedule_node_extension
};
4159 isl_union_set
*domain
;
4160 isl_union_set
*filter
;
4163 in_ext
= has_ancestors(node
, 3, ancestors
);
4169 disjoint
= is_disjoint_extension(node
, extension
);
4173 return extend_extension(node
, extension
);
4176 filter
= isl_schedule_node_get_domain(node
);
4177 domain
= isl_union_map_range(isl_union_map_copy(extension
));
4178 filter
= replace_by_universe_if_disjoint(filter
, domain
);
4179 isl_union_set_free(domain
);
4181 node
= isl_schedule_node_insert_filter(node
, filter
);
4182 node
= isl_schedule_node_insert_extension(node
, extension
);
4183 node
= isl_schedule_node_child(node
, 0);
4186 isl_schedule_node_free(node
);
4187 isl_union_map_free(extension
);
4191 /* Replace the subtree that "node" points to by "tree" (which has
4192 * a sequence root with two children), except if the parent of "node"
4193 * is a sequence as well, in which case "tree" is spliced at the position
4194 * of "node" in its parent.
4195 * Return a pointer to the child of the "tree_pos" (filter) child of "tree"
4196 * in the updated schedule tree.
4198 static __isl_give isl_schedule_node
*graft_or_splice(
4199 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_tree
*tree
,
4204 if (isl_schedule_node_get_parent_type(node
) ==
4205 isl_schedule_node_sequence
) {
4206 pos
= isl_schedule_node_get_child_position(node
);
4207 node
= isl_schedule_node_parent(node
);
4208 node
= isl_schedule_node_sequence_splice(node
, pos
, tree
);
4211 node
= isl_schedule_node_graft_tree(node
, tree
);
4213 node
= isl_schedule_node_child(node
, pos
+ tree_pos
);
4214 node
= isl_schedule_node_child(node
, 0);
4219 /* Insert a node "graft" into the schedule tree of "node" such that it
4220 * is executed before (if "before" is set) or after (if "before" is not set)
4221 * the node that "node" points to.
4222 * The root of "graft" is an extension node.
4223 * Return a pointer to the node that "node" pointed to.
4225 * We first insert an extension node on top of "node" (or extend
4226 * the extension node if there already is one), with a filter on "node"
4227 * separating it from the extension.
4228 * We then insert a filter in the graft to separate it from the original
4229 * domain elements and combine the original and new tree in a sequence.
4230 * If we have extended an extension node, then the children of this
4231 * sequence are spliced in the sequence of the extended extension
4232 * at the position where "node" appears in the original extension.
4233 * Otherwise, the sequence pair is attached to the new extension node.
4235 static __isl_give isl_schedule_node
*graft_extension(
4236 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
,
4239 isl_union_map
*extension
;
4240 isl_union_set
*graft_domain
;
4241 isl_union_set
*node_domain
;
4242 isl_schedule_tree
*tree
, *tree_graft
;
4244 extension
= isl_schedule_node_extension_get_extension(graft
);
4245 graft_domain
= isl_union_map_range(isl_union_map_copy(extension
));
4246 node_domain
= isl_schedule_node_get_universe_domain(node
);
4247 node
= insert_extension(node
, extension
);
4249 graft_domain
= replace_by_universe_if_disjoint(graft_domain
,
4251 isl_union_set_free(node_domain
);
4253 tree
= isl_schedule_node_get_tree(node
);
4254 if (!isl_schedule_node_has_children(graft
)) {
4255 tree_graft
= isl_schedule_tree_from_filter(graft_domain
);
4257 graft
= isl_schedule_node_child(graft
, 0);
4258 tree_graft
= isl_schedule_node_get_tree(graft
);
4259 tree_graft
= isl_schedule_tree_insert_filter(tree_graft
,
4263 tree
= isl_schedule_tree_sequence_pair(tree_graft
, tree
);
4265 tree
= isl_schedule_tree_sequence_pair(tree
, tree_graft
);
4266 node
= graft_or_splice(node
, tree
, before
);
4268 isl_schedule_node_free(graft
);
4273 /* Replace the root domain node of "node" by an extension node suitable
4274 * for insertion at "pos".
4275 * That is, create an extension node that maps the outer band nodes
4276 * at "pos" to the domain of the root node of "node" and attach
4277 * the child of this root node to the extension node.
4279 static __isl_give isl_schedule_node
*extension_from_domain(
4280 __isl_take isl_schedule_node
*node
, __isl_keep isl_schedule_node
*pos
)
4282 isl_union_set
*universe
;
4283 isl_union_set
*domain
;
4288 isl_schedule_node
*res
;
4289 isl_schedule_tree
*tree
;
4291 anchored
= isl_schedule_node_is_subtree_anchored(node
);
4293 return isl_schedule_node_free(node
);
4295 isl_die(isl_schedule_node_get_ctx(node
), isl_error_unsupported
,
4296 "cannot graft anchored tree with domain root",
4297 return isl_schedule_node_free(node
));
4299 depth
= isl_schedule_node_get_schedule_depth(pos
);
4300 domain
= isl_schedule_node_domain_get_domain(node
);
4301 space
= isl_union_set_get_space(domain
);
4302 space
= isl_space_set_from_params(space
);
4303 space
= isl_space_add_dims(space
, isl_dim_set
, depth
);
4304 universe
= isl_union_set_from_set(isl_set_universe(space
));
4305 ext
= isl_union_map_from_domain_and_range(universe
, domain
);
4306 res
= isl_schedule_node_from_extension(ext
);
4307 node
= isl_schedule_node_child(node
, 0);
4309 return isl_schedule_node_free(res
);
4310 if (!isl_schedule_tree_is_leaf(node
->tree
)) {
4311 tree
= isl_schedule_node_get_tree(node
);
4312 res
= isl_schedule_node_child(res
, 0);
4313 res
= isl_schedule_node_graft_tree(res
, tree
);
4314 res
= isl_schedule_node_parent(res
);
4316 isl_schedule_node_free(node
);
4321 /* Insert a node "graft" into the schedule tree of "node" such that it
4322 * is executed before (if "before" is set) or after (if "before" is not set)
4323 * the node that "node" points to.
4324 * The root of "graft" may be either a domain or an extension node.
4325 * In the latter case, the domain of the extension needs to correspond
4326 * to the outer band nodes of "node".
4327 * The elements of the domain or the range of the extension may not
4328 * intersect with the domain elements that reach "node".
4329 * The schedule tree of "graft" may not be anchored.
4331 * The schedule tree of "node" is modified to include an extension node
4332 * corresponding to the root node of "graft" as a child of the original
4333 * parent of "node". The original node that "node" points to and the
4334 * child of the root node of "graft" are attached to this extension node
4335 * through a sequence, with appropriate filters and with the child
4336 * of "graft" appearing before or after the original "node".
4338 * If "node" already appears inside a sequence that is the child of
4339 * an extension node and if the spaces of the new domain elements
4340 * do not overlap with those of the original domain elements,
4341 * then that extension node is extended with the new extension
4342 * rather than introducing a new segment of extension and sequence nodes.
4344 * Return a pointer to the same node in the modified tree that
4345 * "node" pointed to in the original tree.
4347 static __isl_give isl_schedule_node
*isl_schedule_node_graft_before_or_after(
4348 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
,
4351 if (!node
|| !graft
)
4353 if (check_insert(node
) < 0)
4356 if (isl_schedule_node_get_type(graft
) == isl_schedule_node_domain
)
4357 graft
= extension_from_domain(graft
, node
);
4361 if (isl_schedule_node_get_type(graft
) != isl_schedule_node_extension
)
4362 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4363 "expecting domain or extension as root of graft",
4366 return graft_extension(node
, graft
, before
);
4368 isl_schedule_node_free(node
);
4369 isl_schedule_node_free(graft
);
4373 /* Insert a node "graft" into the schedule tree of "node" such that it
4374 * is executed before the node that "node" points to.
4375 * The root of "graft" may be either a domain or an extension node.
4376 * In the latter case, the domain of the extension needs to correspond
4377 * to the outer band nodes of "node".
4378 * The elements of the domain or the range of the extension may not
4379 * intersect with the domain elements that reach "node".
4380 * The schedule tree of "graft" may not be anchored.
4382 * Return a pointer to the same node in the modified tree that
4383 * "node" pointed to in the original tree.
4385 __isl_give isl_schedule_node
*isl_schedule_node_graft_before(
4386 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
)
4388 return isl_schedule_node_graft_before_or_after(node
, graft
, 1);
4391 /* Insert a node "graft" into the schedule tree of "node" such that it
4392 * is executed after the node that "node" points to.
4393 * The root of "graft" may be either a domain or an extension node.
4394 * In the latter case, the domain of the extension needs to correspond
4395 * to the outer band nodes of "node".
4396 * The elements of the domain or the range of the extension may not
4397 * intersect with the domain elements that reach "node".
4398 * The schedule tree of "graft" may not be anchored.
4400 * Return a pointer to the same node in the modified tree that
4401 * "node" pointed to in the original tree.
4403 __isl_give isl_schedule_node
*isl_schedule_node_graft_after(
4404 __isl_take isl_schedule_node
*node
,
4405 __isl_take isl_schedule_node
*graft
)
4407 return isl_schedule_node_graft_before_or_after(node
, graft
, 0);
4410 /* Split the domain elements that reach "node" into those that satisfy
4411 * "filter" and those that do not. Arrange for the first subset to be
4412 * executed before or after the second subset, depending on the value
4414 * Return a pointer to the tree corresponding to the second subset,
4415 * except when this subset is empty in which case the original pointer
4417 * If both subsets are non-empty, then a sequence node is introduced
4418 * to impose the order. If the grandparent of the original node was
4419 * itself a sequence, then the original child is replaced by two children
4420 * in this sequence instead.
4421 * The children in the sequence are copies of the original subtree,
4422 * simplified with respect to their filters.
4424 static __isl_give isl_schedule_node
*isl_schedule_node_order_before_or_after(
4425 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
,
4428 enum isl_schedule_node_type ancestors
[] =
4429 { isl_schedule_node_filter
, isl_schedule_node_sequence
};
4430 isl_union_set
*node_domain
, *node_filter
= NULL
, *parent_filter
;
4431 isl_schedule_node
*node2
;
4432 isl_schedule_tree
*tree1
, *tree2
;
4433 isl_bool empty1
, empty2
;
4436 if (!node
|| !filter
)
4438 if (check_insert(node
) < 0)
4441 in_seq
= has_ancestors(node
, 2, ancestors
);
4444 node_domain
= isl_schedule_node_get_domain(node
);
4445 filter
= isl_union_set_gist(filter
, isl_union_set_copy(node_domain
));
4446 node_filter
= isl_union_set_copy(node_domain
);
4447 node_filter
= isl_union_set_subtract(node_filter
,
4448 isl_union_set_copy(filter
));
4449 node_filter
= isl_union_set_gist(node_filter
, node_domain
);
4450 empty1
= isl_union_set_is_empty(filter
);
4451 empty2
= isl_union_set_is_empty(node_filter
);
4452 if (empty1
< 0 || empty2
< 0)
4454 if (empty1
|| empty2
) {
4455 isl_union_set_free(filter
);
4456 isl_union_set_free(node_filter
);
4461 node
= isl_schedule_node_parent(node
);
4462 parent_filter
= isl_schedule_node_filter_get_filter(node
);
4463 node_filter
= isl_union_set_intersect(node_filter
,
4464 isl_union_set_copy(parent_filter
));
4465 filter
= isl_union_set_intersect(filter
, parent_filter
);
4468 node2
= isl_schedule_node_copy(node
);
4469 node
= isl_schedule_node_gist(node
, isl_union_set_copy(node_filter
));
4470 node2
= isl_schedule_node_gist(node2
, isl_union_set_copy(filter
));
4471 tree1
= isl_schedule_node_get_tree(node
);
4472 tree2
= isl_schedule_node_get_tree(node2
);
4473 tree1
= isl_schedule_tree_insert_filter(tree1
, node_filter
);
4474 tree2
= isl_schedule_tree_insert_filter(tree2
, filter
);
4475 isl_schedule_node_free(node2
);
4478 tree1
= isl_schedule_tree_sequence_pair(tree2
, tree1
);
4479 node
= graft_or_splice(node
, tree1
, 1);
4481 tree1
= isl_schedule_tree_sequence_pair(tree1
, tree2
);
4482 node
= graft_or_splice(node
, tree1
, 0);
4487 isl_schedule_node_free(node
);
4488 isl_union_set_free(filter
);
4489 isl_union_set_free(node_filter
);
4493 /* Split the domain elements that reach "node" into those that satisfy
4494 * "filter" and those that do not. Arrange for the first subset to be
4495 * executed before the second subset.
4496 * Return a pointer to the tree corresponding to the second subset,
4497 * except when this subset is empty in which case the original pointer
4500 __isl_give isl_schedule_node
*isl_schedule_node_order_before(
4501 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
4503 return isl_schedule_node_order_before_or_after(node
, filter
, 1);
4506 /* Split the domain elements that reach "node" into those that satisfy
4507 * "filter" and those that do not. Arrange for the first subset to be
4508 * executed after the second subset.
4509 * Return a pointer to the tree corresponding to the second subset,
4510 * except when this subset is empty in which case the original pointer
4513 __isl_give isl_schedule_node
*isl_schedule_node_order_after(
4514 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
4516 return isl_schedule_node_order_before_or_after(node
, filter
, 0);
4519 /* Reset the user pointer on all identifiers of parameters and tuples
4520 * in the schedule node "node".
4522 __isl_give isl_schedule_node
*isl_schedule_node_reset_user(
4523 __isl_take isl_schedule_node
*node
)
4525 isl_schedule_tree
*tree
;
4527 tree
= isl_schedule_node_get_tree(node
);
4528 tree
= isl_schedule_tree_reset_user(tree
);
4529 node
= isl_schedule_node_graft_tree(node
, tree
);
4534 /* Align the parameters of the schedule node "node" to those of "space".
4536 __isl_give isl_schedule_node
*isl_schedule_node_align_params(
4537 __isl_take isl_schedule_node
*node
, __isl_take isl_space
*space
)
4539 isl_schedule_tree
*tree
;
4541 tree
= isl_schedule_node_get_tree(node
);
4542 tree
= isl_schedule_tree_align_params(tree
, space
);
4543 node
= isl_schedule_node_graft_tree(node
, tree
);
4548 /* Compute the pullback of schedule node "node"
4549 * by the function represented by "upma".
4550 * In other words, plug in "upma" in the iteration domains
4551 * of schedule node "node".
4552 * We currently do not handle expansion nodes.
4554 * Note that this is only a helper function for
4555 * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency,
4556 * this function should not be called on a single node without also
4557 * calling it on all the other nodes.
4559 __isl_give isl_schedule_node
*isl_schedule_node_pullback_union_pw_multi_aff(
4560 __isl_take isl_schedule_node
*node
,
4561 __isl_take isl_union_pw_multi_aff
*upma
)
4563 isl_schedule_tree
*tree
;
4565 tree
= isl_schedule_node_get_tree(node
);
4566 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, upma
);
4567 node
= isl_schedule_node_graft_tree(node
, tree
);
4572 /* Internal data structure for isl_schedule_node_expand.
4573 * "tree" is the tree that needs to be plugged in in all the leaves.
4574 * "domain" is the set of domain elements in the original leaves
4575 * to which the tree applies.
4577 struct isl_schedule_expand_data
{
4578 isl_schedule_tree
*tree
;
4579 isl_union_set
*domain
;
4582 /* If "node" is a leaf, then plug in data->tree, simplifying it
4583 * within its new context.
4585 * If there are any domain elements at the leaf where the tree
4586 * should not be plugged in (i.e., there are elements not in data->domain)
4587 * then first extend the tree to only apply to the elements in data->domain
4588 * by constructing a set node that selects data->tree for elements
4589 * in data->domain and a leaf for the other elements.
4591 static __isl_give isl_schedule_node
*expand(__isl_take isl_schedule_node
*node
,
4594 struct isl_schedule_expand_data
*data
= user
;
4595 isl_schedule_tree
*tree
, *leaf
;
4596 isl_union_set
*domain
, *left
;
4599 if (isl_schedule_node_get_type(node
) != isl_schedule_node_leaf
)
4602 domain
= isl_schedule_node_get_domain(node
);
4603 tree
= isl_schedule_tree_copy(data
->tree
);
4605 left
= isl_union_set_copy(domain
);
4606 left
= isl_union_set_subtract(left
, isl_union_set_copy(data
->domain
));
4607 empty
= isl_union_set_is_empty(left
);
4608 if (empty
>= 0 && !empty
) {
4609 leaf
= isl_schedule_node_get_leaf(node
);
4610 leaf
= isl_schedule_tree_insert_filter(leaf
, left
);
4611 left
= isl_union_set_copy(data
->domain
);
4612 tree
= isl_schedule_tree_insert_filter(tree
, left
);
4613 tree
= isl_schedule_tree_set_pair(tree
, leaf
);
4616 node
= isl_schedule_node_free(node
);
4617 isl_union_set_free(left
);
4620 node
= isl_schedule_node_graft_tree(node
, tree
);
4621 node
= isl_schedule_node_gist(node
, domain
);
4626 /* Expand the tree rooted at "node" by extending all leaves
4627 * with an expansion node with as child "tree".
4628 * The expansion is determined by "contraction" and "domain".
4629 * That is, the elements of "domain" are contracted according
4630 * to "contraction". The expansion relation is then the inverse
4631 * of "contraction" with its range intersected with "domain".
4633 * Insert the appropriate expansion node on top of "tree" and
4634 * then plug in the result in all leaves of "node".
4636 __isl_give isl_schedule_node
*isl_schedule_node_expand(
4637 __isl_take isl_schedule_node
*node
,
4638 __isl_take isl_union_pw_multi_aff
*contraction
,
4639 __isl_take isl_union_set
*domain
,
4640 __isl_take isl_schedule_tree
*tree
)
4642 struct isl_schedule_expand_data data
;
4643 isl_union_map
*expansion
;
4644 isl_union_pw_multi_aff
*copy
;
4646 if (!node
|| !contraction
|| !tree
)
4647 node
= isl_schedule_node_free(node
);
4649 copy
= isl_union_pw_multi_aff_copy(contraction
);
4650 expansion
= isl_union_map_from_union_pw_multi_aff(copy
);
4651 expansion
= isl_union_map_reverse(expansion
);
4652 expansion
= isl_union_map_intersect_range(expansion
, domain
);
4653 data
.domain
= isl_union_map_domain(isl_union_map_copy(expansion
));
4655 tree
= isl_schedule_tree_insert_expansion(tree
, contraction
, expansion
);
4658 node
= isl_schedule_node_map_descendant_bottom_up(node
, &expand
, &data
);
4659 isl_union_set_free(data
.domain
);
4660 isl_schedule_tree_free(data
.tree
);
4664 /* Return the position of the subtree containing "node" among the children
4665 * of "ancestor". "node" is assumed to be a descendant of "ancestor".
4666 * In particular, both nodes should point to the same schedule tree.
4668 * Return -1 on error.
4670 int isl_schedule_node_get_ancestor_child_position(
4671 __isl_keep isl_schedule_node
*node
,
4672 __isl_keep isl_schedule_node
*ancestor
)
4675 isl_schedule_tree
*tree
;
4677 if (!node
|| !ancestor
)
4680 if (node
->schedule
!= ancestor
->schedule
)
4681 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4682 "not a descendant", return -1);
4684 n1
= isl_schedule_node_get_tree_depth(ancestor
);
4685 n2
= isl_schedule_node_get_tree_depth(node
);
4688 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4689 "not a descendant", return -1);
4690 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n1
);
4691 isl_schedule_tree_free(tree
);
4692 if (tree
!= ancestor
->tree
)
4693 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4694 "not a descendant", return -1);
4696 return node
->child_pos
[n1
];
4699 /* Given two nodes that point to the same schedule tree, return their
4700 * closest shared ancestor.
4702 * Since the two nodes point to the same schedule, they share at least
4703 * one ancestor, the root of the schedule. We move down from the root
4704 * to the first ancestor where the respective children have a different
4705 * child position. This is the requested ancestor.
4706 * If there is no ancestor where the children have a different position,
4707 * then one node is an ancestor of the other and then this node is
4708 * the requested ancestor.
4710 __isl_give isl_schedule_node
*isl_schedule_node_get_shared_ancestor(
4711 __isl_keep isl_schedule_node
*node1
,
4712 __isl_keep isl_schedule_node
*node2
)
4716 if (!node1
|| !node2
)
4718 if (node1
->schedule
!= node2
->schedule
)
4719 isl_die(isl_schedule_node_get_ctx(node1
), isl_error_invalid
,
4720 "not part of same schedule", return NULL
);
4721 n1
= isl_schedule_node_get_tree_depth(node1
);
4722 n2
= isl_schedule_node_get_tree_depth(node2
);
4724 return isl_schedule_node_get_shared_ancestor(node2
, node1
);
4726 return isl_schedule_node_copy(node1
);
4727 if (isl_schedule_node_is_equal(node1
, node2
))
4728 return isl_schedule_node_copy(node1
);
4730 for (i
= 0; i
< n1
; ++i
)
4731 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
4734 node1
= isl_schedule_node_copy(node1
);
4735 return isl_schedule_node_ancestor(node1
, n1
- i
);
4738 /* Print "node" to "p".
4740 __isl_give isl_printer
*isl_printer_print_schedule_node(
4741 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
4744 return isl_printer_free(p
);
4745 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
,
4746 isl_schedule_tree_list_n_schedule_tree(node
->ancestors
),
4750 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
4753 isl_printer
*printer
;
4758 ctx
= isl_schedule_node_get_ctx(node
);
4759 printer
= isl_printer_to_file(ctx
, stderr
);
4760 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
4761 printer
= isl_printer_print_schedule_node(printer
, node
);
4763 isl_printer_free(printer
);
4766 /* Return a string representation of "node".
4767 * Print the schedule node in block format as it would otherwise
4768 * look identical to the entire schedule.
4770 __isl_give
char *isl_schedule_node_to_str(__isl_keep isl_schedule_node
*node
)
4772 isl_printer
*printer
;
4778 printer
= isl_printer_to_str(isl_schedule_node_get_ctx(node
));
4779 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
4780 printer
= isl_printer_print_schedule_node(printer
, node
);
4781 s
= isl_printer_get_str(printer
);
4782 isl_printer_free(printer
);