2 * Copyright 2013-2014 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
4 * Copyright 2016 Sven Verdoolaege
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege,
9 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
10 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
11 * B.P. 105 - 78153 Le Chesnay, France
15 #include <isl_schedule_band.h>
16 #include <isl_schedule_private.h>
17 #include <isl_schedule_node_private.h>
19 /* Create a new schedule node in the given schedule, point at the given
20 * tree with given ancestors and child positions.
21 * "child_pos" may be NULL if there are no ancestors.
23 __isl_give isl_schedule_node
*isl_schedule_node_alloc(
24 __isl_take isl_schedule
*schedule
, __isl_take isl_schedule_tree
*tree
,
25 __isl_take isl_schedule_tree_list
*ancestors
, int *child_pos
)
28 isl_schedule_node
*node
;
31 if (!schedule
|| !tree
|| !ancestors
)
33 n
= isl_schedule_tree_list_n_schedule_tree(ancestors
);
34 if (n
> 0 && !child_pos
)
36 ctx
= isl_schedule_get_ctx(schedule
);
37 node
= isl_calloc_type(ctx
, isl_schedule_node
);
41 node
->schedule
= schedule
;
43 node
->ancestors
= ancestors
;
44 node
->child_pos
= isl_alloc_array(ctx
, int, n
);
45 if (n
&& !node
->child_pos
)
46 return isl_schedule_node_free(node
);
47 for (i
= 0; i
< n
; ++i
)
48 node
->child_pos
[i
] = child_pos
[i
];
52 isl_schedule_free(schedule
);
53 isl_schedule_tree_free(tree
);
54 isl_schedule_tree_list_free(ancestors
);
58 /* Return a pointer to the root of a schedule tree with as single
59 * node a domain node with the given domain.
61 __isl_give isl_schedule_node
*isl_schedule_node_from_domain(
62 __isl_take isl_union_set
*domain
)
64 isl_schedule
*schedule
;
65 isl_schedule_node
*node
;
67 schedule
= isl_schedule_from_domain(domain
);
68 node
= isl_schedule_get_root(schedule
);
69 isl_schedule_free(schedule
);
74 /* Return a pointer to the root of a schedule tree with as single
75 * node a extension node with the given extension.
77 __isl_give isl_schedule_node
*isl_schedule_node_from_extension(
78 __isl_take isl_union_map
*extension
)
81 isl_schedule
*schedule
;
82 isl_schedule_tree
*tree
;
83 isl_schedule_node
*node
;
88 ctx
= isl_union_map_get_ctx(extension
);
89 tree
= isl_schedule_tree_from_extension(extension
);
90 schedule
= isl_schedule_from_schedule_tree(ctx
, tree
);
91 node
= isl_schedule_get_root(schedule
);
92 isl_schedule_free(schedule
);
97 /* Return the isl_ctx to which "node" belongs.
99 isl_ctx
*isl_schedule_node_get_ctx(__isl_keep isl_schedule_node
*node
)
101 return node
? isl_schedule_get_ctx(node
->schedule
) : NULL
;
104 /* Return a pointer to the leaf of the schedule into which "node" points.
106 __isl_keep isl_schedule_tree
*isl_schedule_node_peek_leaf(
107 __isl_keep isl_schedule_node
*node
)
109 return node
? isl_schedule_peek_leaf(node
->schedule
) : NULL
;
112 /* Return a copy of the leaf of the schedule into which "node" points.
114 __isl_give isl_schedule_tree
*isl_schedule_node_get_leaf(
115 __isl_keep isl_schedule_node
*node
)
117 return isl_schedule_tree_copy(isl_schedule_node_peek_leaf(node
));
120 /* Return the type of the node or isl_schedule_node_error on error.
122 enum isl_schedule_node_type
isl_schedule_node_get_type(
123 __isl_keep isl_schedule_node
*node
)
125 return node
? isl_schedule_tree_get_type(node
->tree
)
126 : isl_schedule_node_error
;
129 /* Return the type of the parent of "node" or isl_schedule_node_error on error.
131 enum isl_schedule_node_type
isl_schedule_node_get_parent_type(
132 __isl_keep isl_schedule_node
*node
)
136 isl_schedule_tree
*parent
;
137 enum isl_schedule_node_type type
;
140 return isl_schedule_node_error
;
141 has_parent
= isl_schedule_node_has_parent(node
);
143 return isl_schedule_node_error
;
145 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
146 "node has no parent", return isl_schedule_node_error
);
148 pos
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) - 1;
149 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, pos
);
150 type
= isl_schedule_tree_get_type(parent
);
151 isl_schedule_tree_free(parent
);
156 /* Return a copy of the subtree that this node points to.
158 __isl_give isl_schedule_tree
*isl_schedule_node_get_tree(
159 __isl_keep isl_schedule_node
*node
)
164 return isl_schedule_tree_copy(node
->tree
);
167 /* Return a copy of the schedule into which "node" points.
169 __isl_give isl_schedule
*isl_schedule_node_get_schedule(
170 __isl_keep isl_schedule_node
*node
)
174 return isl_schedule_copy(node
->schedule
);
177 /* Return a fresh copy of "node".
179 __isl_take isl_schedule_node
*isl_schedule_node_dup(
180 __isl_keep isl_schedule_node
*node
)
185 return isl_schedule_node_alloc(isl_schedule_copy(node
->schedule
),
186 isl_schedule_tree_copy(node
->tree
),
187 isl_schedule_tree_list_copy(node
->ancestors
),
191 /* Return an isl_schedule_node that is equal to "node" and that has only
192 * a single reference.
194 __isl_give isl_schedule_node
*isl_schedule_node_cow(
195 __isl_take isl_schedule_node
*node
)
203 return isl_schedule_node_dup(node
);
206 /* Return a new reference to "node".
208 __isl_give isl_schedule_node
*isl_schedule_node_copy(
209 __isl_keep isl_schedule_node
*node
)
218 /* Free "node" and return NULL.
220 __isl_null isl_schedule_node
*isl_schedule_node_free(
221 __isl_take isl_schedule_node
*node
)
228 isl_schedule_tree_list_free(node
->ancestors
);
229 free(node
->child_pos
);
230 isl_schedule_tree_free(node
->tree
);
231 isl_schedule_free(node
->schedule
);
237 /* Do "node1" and "node2" point to the same position in the same
240 isl_bool
isl_schedule_node_is_equal(__isl_keep isl_schedule_node
*node1
,
241 __isl_keep isl_schedule_node
*node2
)
245 if (!node1
|| !node2
)
246 return isl_bool_error
;
248 return isl_bool_true
;
249 if (node1
->schedule
!= node2
->schedule
)
250 return isl_bool_false
;
252 n1
= isl_schedule_node_get_tree_depth(node1
);
253 n2
= isl_schedule_node_get_tree_depth(node2
);
255 return isl_bool_false
;
256 for (i
= 0; i
< n1
; ++i
)
257 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
258 return isl_bool_false
;
260 return isl_bool_true
;
263 /* Return the number of outer schedule dimensions of "node"
264 * in its schedule tree.
266 * Return -1 on error.
268 int isl_schedule_node_get_schedule_depth(__isl_keep isl_schedule_node
*node
)
276 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
277 for (i
= n
- 1; i
>= 0; --i
) {
278 isl_schedule_tree
*tree
;
280 tree
= isl_schedule_tree_list_get_schedule_tree(
284 if (tree
->type
== isl_schedule_node_band
)
285 depth
+= isl_schedule_tree_band_n_member(tree
);
286 isl_schedule_tree_free(tree
);
292 /* Internal data structure for
293 * isl_schedule_node_get_prefix_schedule_union_pw_multi_aff
295 * "initialized" is set if the filter field has been initialized.
296 * If "universe_domain" is not set, then the collected filter is intersected
297 * with the the domain of the root domain node.
298 * "universe_filter" is set if we are only collecting the universes of filters
299 * "collect_prefix" is set if we are collecting prefixes.
300 * "filter" collects all outer filters and is NULL until "initialized" is set.
301 * "prefix" collects all outer band partial schedules (if "collect_prefix"
302 * is set). If it is used, then it is initialized by the caller
303 * of collect_filter_prefix to a zero-dimensional function.
305 struct isl_schedule_node_get_filter_prefix_data
{
310 isl_union_set
*filter
;
311 isl_multi_union_pw_aff
*prefix
;
314 static int collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
315 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
);
317 /* Update the filter and prefix information in "data" based on the first "n"
318 * elements in "list" and the expansion tree root "tree".
320 * We first collect the information from the elements in "list",
321 * initializing the filter based on the domain of the expansion.
322 * Then we map the results to the expanded space and combined them
323 * with the results already in "data".
325 static int collect_filter_prefix_expansion(__isl_take isl_schedule_tree
*tree
,
326 __isl_keep isl_schedule_tree_list
*list
, int n
,
327 struct isl_schedule_node_get_filter_prefix_data
*data
)
329 struct isl_schedule_node_get_filter_prefix_data contracted
;
330 isl_union_pw_multi_aff
*c
;
331 isl_union_map
*exp
, *universe
;
332 isl_union_set
*filter
;
334 c
= isl_schedule_tree_expansion_get_contraction(tree
);
335 exp
= isl_schedule_tree_expansion_get_expansion(tree
);
337 contracted
.initialized
= 1;
338 contracted
.universe_domain
= data
->universe_domain
;
339 contracted
.universe_filter
= data
->universe_filter
;
340 contracted
.collect_prefix
= data
->collect_prefix
;
341 universe
= isl_union_map_universe(isl_union_map_copy(exp
));
342 filter
= isl_union_map_domain(universe
);
343 if (data
->collect_prefix
) {
344 isl_space
*space
= isl_union_set_get_space(filter
);
345 space
= isl_space_set_from_params(space
);
346 contracted
.prefix
= isl_multi_union_pw_aff_zero(space
);
348 contracted
.filter
= filter
;
350 if (collect_filter_prefix(list
, n
, &contracted
) < 0)
351 contracted
.filter
= isl_union_set_free(contracted
.filter
);
352 if (data
->collect_prefix
) {
353 isl_multi_union_pw_aff
*prefix
;
355 prefix
= contracted
.prefix
;
357 isl_multi_union_pw_aff_pullback_union_pw_multi_aff(prefix
,
358 isl_union_pw_multi_aff_copy(c
));
359 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(
360 prefix
, data
->prefix
);
362 filter
= contracted
.filter
;
363 if (data
->universe_domain
)
364 filter
= isl_union_set_preimage_union_pw_multi_aff(filter
,
365 isl_union_pw_multi_aff_copy(c
));
367 filter
= isl_union_set_apply(filter
, isl_union_map_copy(exp
));
368 if (!data
->initialized
)
369 data
->filter
= filter
;
371 data
->filter
= isl_union_set_intersect(filter
, data
->filter
);
372 data
->initialized
= 1;
374 isl_union_pw_multi_aff_free(c
);
375 isl_union_map_free(exp
);
376 isl_schedule_tree_free(tree
);
381 /* Update the filter information in "data" based on the first "n"
382 * elements in "list" and the extension tree root "tree", in case
383 * data->universe_domain is set and data->collect_prefix is not.
385 * We collect the universe domain of the elements in "list" and
386 * add it to the universe range of the extension (intersected
387 * with the already collected filter, if any).
389 static int collect_universe_domain_extension(__isl_take isl_schedule_tree
*tree
,
390 __isl_keep isl_schedule_tree_list
*list
, int n
,
391 struct isl_schedule_node_get_filter_prefix_data
*data
)
393 struct isl_schedule_node_get_filter_prefix_data data_outer
;
394 isl_union_map
*extension
;
395 isl_union_set
*filter
;
397 data_outer
.initialized
= 0;
398 data_outer
.universe_domain
= 1;
399 data_outer
.universe_filter
= data
->universe_filter
;
400 data_outer
.collect_prefix
= 0;
401 data_outer
.filter
= NULL
;
402 data_outer
.prefix
= NULL
;
404 if (collect_filter_prefix(list
, n
, &data_outer
) < 0)
405 data_outer
.filter
= isl_union_set_free(data_outer
.filter
);
407 extension
= isl_schedule_tree_extension_get_extension(tree
);
408 extension
= isl_union_map_universe(extension
);
409 filter
= isl_union_map_range(extension
);
410 if (data_outer
.initialized
)
411 filter
= isl_union_set_union(filter
, data_outer
.filter
);
412 if (data
->initialized
)
413 filter
= isl_union_set_intersect(filter
, data
->filter
);
415 data
->filter
= filter
;
417 isl_schedule_tree_free(tree
);
422 /* Update "data" based on the tree node "tree" in case "data" has
423 * not been initialized yet.
425 * Return 0 on success and -1 on error.
427 * If "tree" is a filter, then we set data->filter to this filter
429 * If "tree" is a domain, then this means we have reached the root
430 * of the schedule tree without being able to extract any information.
431 * We therefore initialize data->filter to the universe of the domain,
432 * or the domain itself if data->universe_domain is not set.
433 * If "tree" is a band with at least one member, then we set data->filter
434 * to the universe of the schedule domain and replace the zero-dimensional
435 * data->prefix by the band schedule (if data->collect_prefix is set).
437 static int collect_filter_prefix_init(__isl_keep isl_schedule_tree
*tree
,
438 struct isl_schedule_node_get_filter_prefix_data
*data
)
440 enum isl_schedule_node_type type
;
441 isl_multi_union_pw_aff
*mupa
;
442 isl_union_set
*filter
;
444 type
= isl_schedule_tree_get_type(tree
);
446 case isl_schedule_node_error
:
448 case isl_schedule_node_expansion
:
449 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
450 "should be handled by caller", return -1);
451 case isl_schedule_node_extension
:
452 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
453 "cannot handle extension nodes", return -1);
454 case isl_schedule_node_context
:
455 case isl_schedule_node_leaf
:
456 case isl_schedule_node_guard
:
457 case isl_schedule_node_mark
:
458 case isl_schedule_node_sequence
:
459 case isl_schedule_node_set
:
461 case isl_schedule_node_domain
:
462 filter
= isl_schedule_tree_domain_get_domain(tree
);
463 if (data
->universe_domain
)
464 filter
= isl_union_set_universe(filter
);
465 data
->filter
= filter
;
467 case isl_schedule_node_band
:
468 if (isl_schedule_tree_band_n_member(tree
) == 0)
470 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
471 if (data
->collect_prefix
) {
472 isl_multi_union_pw_aff_free(data
->prefix
);
473 mupa
= isl_multi_union_pw_aff_reset_tuple_id(mupa
,
475 data
->prefix
= isl_multi_union_pw_aff_copy(mupa
);
477 filter
= isl_multi_union_pw_aff_domain(mupa
);
478 filter
= isl_union_set_universe(filter
);
479 data
->filter
= filter
;
481 case isl_schedule_node_filter
:
482 filter
= isl_schedule_tree_filter_get_filter(tree
);
483 if (data
->universe_filter
)
484 filter
= isl_union_set_universe(filter
);
485 data
->filter
= filter
;
489 if ((data
->collect_prefix
&& !data
->prefix
) || !data
->filter
)
492 data
->initialized
= 1;
497 /* Update "data" based on the tree node "tree" in case "data" has
498 * already been initialized.
500 * Return 0 on success and -1 on error.
502 * If "tree" is a domain and data->universe_domain is not set, then
503 * intersect data->filter with the domain.
504 * If "tree" is a filter, then we intersect data->filter with this filter
506 * If "tree" is a band with at least one member and data->collect_prefix
507 * is set, then we extend data->prefix with the band schedule.
508 * If "tree" is an extension, then we make sure that we are not collecting
509 * information on any extended domain elements.
511 static int collect_filter_prefix_update(__isl_keep isl_schedule_tree
*tree
,
512 struct isl_schedule_node_get_filter_prefix_data
*data
)
514 enum isl_schedule_node_type type
;
515 isl_multi_union_pw_aff
*mupa
;
516 isl_union_set
*filter
;
517 isl_union_map
*extension
;
520 type
= isl_schedule_tree_get_type(tree
);
522 case isl_schedule_node_error
:
524 case isl_schedule_node_expansion
:
525 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
526 "should be handled by caller", return -1);
527 case isl_schedule_node_extension
:
528 extension
= isl_schedule_tree_extension_get_extension(tree
);
529 extension
= isl_union_map_intersect_range(extension
,
530 isl_union_set_copy(data
->filter
));
531 empty
= isl_union_map_is_empty(extension
);
532 isl_union_map_free(extension
);
537 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
538 "cannot handle extension nodes", return -1);
539 case isl_schedule_node_context
:
540 case isl_schedule_node_leaf
:
541 case isl_schedule_node_guard
:
542 case isl_schedule_node_mark
:
543 case isl_schedule_node_sequence
:
544 case isl_schedule_node_set
:
546 case isl_schedule_node_domain
:
547 if (data
->universe_domain
)
549 filter
= isl_schedule_tree_domain_get_domain(tree
);
550 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
552 case isl_schedule_node_band
:
553 if (isl_schedule_tree_band_n_member(tree
) == 0)
555 if (!data
->collect_prefix
)
557 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
558 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(mupa
,
563 case isl_schedule_node_filter
:
564 filter
= isl_schedule_tree_filter_get_filter(tree
);
565 if (data
->universe_filter
)
566 filter
= isl_union_set_universe(filter
);
567 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
576 /* Collect filter and/or prefix information from the first "n"
577 * elements in "list" (which represent the ancestors of a node).
578 * Store the results in "data".
580 * Extension nodes are only supported if they do not affect the outcome,
581 * i.e., if we are collecting information on non-extended domain elements,
582 * or if we are collecting the universe domain (without prefix).
584 * Return 0 on success and -1 on error.
586 * We traverse the list from innermost ancestor (last element)
587 * to outermost ancestor (first element), calling collect_filter_prefix_init
588 * on each node as long as we have not been able to extract any information
589 * yet and collect_filter_prefix_update afterwards.
590 * If we come across an expansion node, then we interrupt the traversal
591 * and call collect_filter_prefix_expansion to restart the traversal
592 * over the remaining ancestors and to combine the results with those
593 * that have already been collected.
594 * If we come across an extension node and we are only computing
595 * the universe domain, then we interrupt the traversal and call
596 * collect_universe_domain_extension to restart the traversal
597 * over the remaining ancestors and to combine the results with those
598 * that have already been collected.
599 * On successful return, data->initialized will be set since the outermost
600 * ancestor is a domain node, which always results in an initialization.
602 static int collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
603 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
)
610 for (i
= n
- 1; i
>= 0; --i
) {
611 isl_schedule_tree
*tree
;
612 enum isl_schedule_node_type type
;
615 tree
= isl_schedule_tree_list_get_schedule_tree(list
, i
);
618 type
= isl_schedule_tree_get_type(tree
);
619 if (type
== isl_schedule_node_expansion
)
620 return collect_filter_prefix_expansion(tree
, list
, i
,
622 if (type
== isl_schedule_node_extension
&&
623 data
->universe_domain
&& !data
->collect_prefix
)
624 return collect_universe_domain_extension(tree
, list
, i
,
626 if (!data
->initialized
)
627 r
= collect_filter_prefix_init(tree
, data
);
629 r
= collect_filter_prefix_update(tree
, data
);
630 isl_schedule_tree_free(tree
);
638 /* Return the concatenation of the partial schedules of all outer band
639 * nodes of "node" interesected with all outer filters
640 * as an isl_multi_union_pw_aff.
641 * None of the ancestors of "node" may be an extension node, unless
642 * there is also a filter ancestor that filters out all the extended
645 * If "node" is pointing at the root of the schedule tree, then
646 * there are no domain elements reaching the current node, so
647 * we return an empty result.
649 * We collect all the filters and partial schedules in collect_filter_prefix
650 * and intersect the domain of the combined schedule with the combined filter.
652 __isl_give isl_multi_union_pw_aff
*
653 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(
654 __isl_keep isl_schedule_node
*node
)
658 struct isl_schedule_node_get_filter_prefix_data data
;
663 space
= isl_schedule_get_space(node
->schedule
);
664 space
= isl_space_set_from_params(space
);
665 if (node
->tree
== node
->schedule
->root
)
666 return isl_multi_union_pw_aff_zero(space
);
668 data
.initialized
= 0;
669 data
.universe_domain
= 1;
670 data
.universe_filter
= 0;
671 data
.collect_prefix
= 1;
673 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
675 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
676 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
677 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
679 data
.prefix
= isl_multi_union_pw_aff_intersect_domain(data
.prefix
,
685 /* Return the concatenation of the partial schedules of all outer band
686 * nodes of "node" interesected with all outer filters
687 * as an isl_union_pw_multi_aff.
688 * None of the ancestors of "node" may be an extension node, unless
689 * there is also a filter ancestor that filters out all the extended
692 * If "node" is pointing at the root of the schedule tree, then
693 * there are no domain elements reaching the current node, so
694 * we return an empty result.
696 * We collect all the filters and partial schedules in collect_filter_prefix.
697 * The partial schedules are collected as an isl_multi_union_pw_aff.
698 * If this isl_multi_union_pw_aff is zero-dimensional, then it does not
699 * contain any domain information, so we construct the isl_union_pw_multi_aff
700 * result as a zero-dimensional function on the collected filter.
701 * Otherwise, we convert the isl_multi_union_pw_aff to
702 * an isl_multi_union_pw_aff and intersect the domain with the filter.
704 __isl_give isl_union_pw_multi_aff
*
705 isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(
706 __isl_keep isl_schedule_node
*node
)
710 isl_union_pw_multi_aff
*prefix
;
711 struct isl_schedule_node_get_filter_prefix_data data
;
716 space
= isl_schedule_get_space(node
->schedule
);
717 if (node
->tree
== node
->schedule
->root
)
718 return isl_union_pw_multi_aff_empty(space
);
720 space
= isl_space_set_from_params(space
);
721 data
.initialized
= 0;
722 data
.universe_domain
= 1;
723 data
.universe_filter
= 0;
724 data
.collect_prefix
= 1;
726 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
728 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
729 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
730 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
733 isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
) == 0) {
734 isl_multi_union_pw_aff_free(data
.prefix
);
735 prefix
= isl_union_pw_multi_aff_from_domain(data
.filter
);
738 isl_union_pw_multi_aff_from_multi_union_pw_aff(data
.prefix
);
739 prefix
= isl_union_pw_multi_aff_intersect_domain(prefix
,
746 /* Return the concatenation of the partial schedules of all outer band
747 * nodes of "node" interesected with all outer filters
748 * as an isl_union_map.
750 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_union_map(
751 __isl_keep isl_schedule_node
*node
)
753 isl_union_pw_multi_aff
*upma
;
755 upma
= isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(node
);
756 return isl_union_map_from_union_pw_multi_aff(upma
);
759 /* Return the concatenation of the partial schedules of all outer band
760 * nodes of "node" intersected with all outer domain constraints.
761 * None of the ancestors of "node" may be an extension node, unless
762 * there is also a filter ancestor that filters out all the extended
765 * Essentially, this function intersects the domain of the output
766 * of isl_schedule_node_get_prefix_schedule_union_map with the output
767 * of isl_schedule_node_get_domain, except that it only traverses
768 * the ancestors of "node" once.
770 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_relation(
771 __isl_keep isl_schedule_node
*node
)
775 isl_union_map
*prefix
;
776 struct isl_schedule_node_get_filter_prefix_data data
;
781 space
= isl_schedule_get_space(node
->schedule
);
782 if (node
->tree
== node
->schedule
->root
)
783 return isl_union_map_empty(space
);
785 space
= isl_space_set_from_params(space
);
786 data
.initialized
= 0;
787 data
.universe_domain
= 0;
788 data
.universe_filter
= 0;
789 data
.collect_prefix
= 1;
791 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
793 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
794 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
795 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
798 isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
) == 0) {
799 isl_multi_union_pw_aff_free(data
.prefix
);
800 prefix
= isl_union_map_from_domain(data
.filter
);
802 prefix
= isl_union_map_from_multi_union_pw_aff(data
.prefix
);
803 prefix
= isl_union_map_intersect_domain(prefix
, data
.filter
);
809 /* Return the domain elements that reach "node".
811 * If "node" is pointing at the root of the schedule tree, then
812 * there are no domain elements reaching the current node, so
813 * we return an empty result.
814 * None of the ancestors of "node" may be an extension node, unless
815 * there is also a filter ancestor that filters out all the extended
818 * Otherwise, we collect all filters reaching the node,
819 * intersected with the root domain in collect_filter_prefix.
821 __isl_give isl_union_set
*isl_schedule_node_get_domain(
822 __isl_keep isl_schedule_node
*node
)
825 struct isl_schedule_node_get_filter_prefix_data data
;
830 if (node
->tree
== node
->schedule
->root
) {
833 space
= isl_schedule_get_space(node
->schedule
);
834 return isl_union_set_empty(space
);
837 data
.initialized
= 0;
838 data
.universe_domain
= 0;
839 data
.universe_filter
= 0;
840 data
.collect_prefix
= 0;
844 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
845 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
846 data
.filter
= isl_union_set_free(data
.filter
);
851 /* Return the union of universe sets of the domain elements that reach "node".
853 * If "node" is pointing at the root of the schedule tree, then
854 * there are no domain elements reaching the current node, so
855 * we return an empty result.
857 * Otherwise, we collect the universes of all filters reaching the node
858 * in collect_filter_prefix.
860 __isl_give isl_union_set
*isl_schedule_node_get_universe_domain(
861 __isl_keep isl_schedule_node
*node
)
864 struct isl_schedule_node_get_filter_prefix_data data
;
869 if (node
->tree
== node
->schedule
->root
) {
872 space
= isl_schedule_get_space(node
->schedule
);
873 return isl_union_set_empty(space
);
876 data
.initialized
= 0;
877 data
.universe_domain
= 1;
878 data
.universe_filter
= 1;
879 data
.collect_prefix
= 0;
883 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
884 if (collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
885 data
.filter
= isl_union_set_free(data
.filter
);
890 /* Return the subtree schedule of "node".
892 * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle
893 * trees that do not contain any schedule information, we first
894 * move down to the first relevant descendant and handle leaves ourselves.
896 * If the subtree rooted at "node" contains any expansion nodes, then
897 * the returned subtree schedule is formulated in terms of the expanded
899 * The subtree is not allowed to contain any extension nodes.
901 __isl_give isl_union_map
*isl_schedule_node_get_subtree_schedule_union_map(
902 __isl_keep isl_schedule_node
*node
)
904 isl_schedule_tree
*tree
, *leaf
;
907 tree
= isl_schedule_node_get_tree(node
);
908 leaf
= isl_schedule_node_peek_leaf(node
);
909 tree
= isl_schedule_tree_first_schedule_descendant(tree
, leaf
);
913 isl_union_set
*domain
;
914 domain
= isl_schedule_node_get_universe_domain(node
);
915 isl_schedule_tree_free(tree
);
916 return isl_union_map_from_domain(domain
);
919 umap
= isl_schedule_tree_get_subtree_schedule_union_map(tree
);
920 isl_schedule_tree_free(tree
);
924 /* Return the number of ancestors of "node" in its schedule tree.
926 int isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node
*node
)
930 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
933 /* Does "node" have a parent?
935 * That is, does it point to any node of the schedule other than the root?
937 isl_bool
isl_schedule_node_has_parent(__isl_keep isl_schedule_node
*node
)
940 return isl_bool_error
;
941 if (!node
->ancestors
)
942 return isl_bool_error
;
944 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
) != 0;
947 /* Return the position of "node" among the children of its parent.
949 int isl_schedule_node_get_child_position(__isl_keep isl_schedule_node
*node
)
956 has_parent
= isl_schedule_node_has_parent(node
);
960 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
961 "node has no parent", return -1);
963 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
964 return node
->child_pos
[n
- 1];
967 /* Does the parent (if any) of "node" have any children with a smaller child
968 * position than this one?
970 isl_bool
isl_schedule_node_has_previous_sibling(
971 __isl_keep isl_schedule_node
*node
)
977 return isl_bool_error
;
978 has_parent
= isl_schedule_node_has_parent(node
);
979 if (has_parent
< 0 || !has_parent
)
982 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
984 return node
->child_pos
[n
- 1] > 0;
987 /* Does the parent (if any) of "node" have any children with a greater child
988 * position than this one?
990 isl_bool
isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node
*node
)
994 isl_schedule_tree
*tree
;
997 return isl_bool_error
;
998 has_parent
= isl_schedule_node_has_parent(node
);
999 if (has_parent
< 0 || !has_parent
)
1002 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1003 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
1005 return isl_bool_error
;
1006 n_child
= isl_schedule_tree_list_n_schedule_tree(tree
->children
);
1007 isl_schedule_tree_free(tree
);
1009 return node
->child_pos
[n
- 1] + 1 < n_child
;
1012 /* Does "node" have any children?
1014 * Any node other than the leaf nodes is considered to have at least
1015 * one child, even if the corresponding isl_schedule_tree does not
1016 * have any children.
1018 isl_bool
isl_schedule_node_has_children(__isl_keep isl_schedule_node
*node
)
1021 return isl_bool_error
;
1022 return !isl_schedule_tree_is_leaf(node
->tree
);
1025 /* Return the number of children of "node"?
1027 * Any node other than the leaf nodes is considered to have at least
1028 * one child, even if the corresponding isl_schedule_tree does not
1029 * have any children. That is, the number of children of "node" is
1030 * only zero if its tree is the explicit empty tree. Otherwise,
1031 * if the isl_schedule_tree has any children, then it is equal
1032 * to the number of children of "node". If it has zero children,
1033 * then "node" still has a leaf node as child.
1035 int isl_schedule_node_n_children(__isl_keep isl_schedule_node
*node
)
1042 if (isl_schedule_tree_is_leaf(node
->tree
))
1045 n
= isl_schedule_tree_n_children(node
->tree
);
1052 /* Move the "node" pointer to the ancestor of the given generation
1053 * of the node it currently points to, where generation 0 is the node
1054 * itself and generation 1 is its parent.
1056 __isl_give isl_schedule_node
*isl_schedule_node_ancestor(
1057 __isl_take isl_schedule_node
*node
, int generation
)
1060 isl_schedule_tree
*tree
;
1064 if (generation
== 0)
1066 n
= isl_schedule_node_get_tree_depth(node
);
1068 return isl_schedule_node_free(node
);
1069 if (generation
< 0 || generation
> n
)
1070 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1071 "generation out of bounds",
1072 return isl_schedule_node_free(node
));
1073 node
= isl_schedule_node_cow(node
);
1077 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1079 isl_schedule_tree_free(node
->tree
);
1081 node
->ancestors
= isl_schedule_tree_list_drop(node
->ancestors
,
1082 n
- generation
, generation
);
1083 if (!node
->ancestors
|| !node
->tree
)
1084 return isl_schedule_node_free(node
);
1089 /* Move the "node" pointer to the parent of the node it currently points to.
1091 __isl_give isl_schedule_node
*isl_schedule_node_parent(
1092 __isl_take isl_schedule_node
*node
)
1096 if (!isl_schedule_node_has_parent(node
))
1097 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1098 "node has no parent",
1099 return isl_schedule_node_free(node
));
1100 return isl_schedule_node_ancestor(node
, 1);
1103 /* Move the "node" pointer to the root of its schedule tree.
1105 __isl_give isl_schedule_node
*isl_schedule_node_root(
1106 __isl_take isl_schedule_node
*node
)
1112 n
= isl_schedule_node_get_tree_depth(node
);
1114 return isl_schedule_node_free(node
);
1115 return isl_schedule_node_ancestor(node
, n
);
1118 /* Move the "node" pointer to the child at position "pos" of the node
1119 * it currently points to.
1121 __isl_give isl_schedule_node
*isl_schedule_node_child(
1122 __isl_take isl_schedule_node
*node
, int pos
)
1126 isl_schedule_tree
*tree
;
1129 node
= isl_schedule_node_cow(node
);
1132 if (!isl_schedule_node_has_children(node
))
1133 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1134 "node has no children",
1135 return isl_schedule_node_free(node
));
1137 ctx
= isl_schedule_node_get_ctx(node
);
1138 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1139 child_pos
= isl_realloc_array(ctx
, node
->child_pos
, int, n
+ 1);
1141 return isl_schedule_node_free(node
);
1142 node
->child_pos
= child_pos
;
1143 node
->child_pos
[n
] = pos
;
1145 node
->ancestors
= isl_schedule_tree_list_add(node
->ancestors
,
1146 isl_schedule_tree_copy(node
->tree
));
1148 if (isl_schedule_tree_has_children(tree
))
1149 tree
= isl_schedule_tree_get_child(tree
, pos
);
1151 tree
= isl_schedule_node_get_leaf(node
);
1152 isl_schedule_tree_free(node
->tree
);
1155 if (!node
->tree
|| !node
->ancestors
)
1156 return isl_schedule_node_free(node
);
1161 /* Move the "node" pointer to the first child of the node
1162 * it currently points to.
1164 __isl_give isl_schedule_node
*isl_schedule_node_first_child(
1165 __isl_take isl_schedule_node
*node
)
1167 return isl_schedule_node_child(node
, 0);
1170 /* Move the "node" pointer to the child of this node's parent in
1171 * the previous child position.
1173 __isl_give isl_schedule_node
*isl_schedule_node_previous_sibling(
1174 __isl_take isl_schedule_node
*node
)
1177 isl_schedule_tree
*parent
, *tree
;
1179 node
= isl_schedule_node_cow(node
);
1182 if (!isl_schedule_node_has_previous_sibling(node
))
1183 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1184 "node has no previous sibling",
1185 return isl_schedule_node_free(node
));
1187 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1188 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1191 return isl_schedule_node_free(node
);
1192 node
->child_pos
[n
- 1]--;
1193 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1194 node
->child_pos
[n
- 1]);
1195 isl_schedule_tree_free(parent
);
1197 return isl_schedule_node_free(node
);
1198 isl_schedule_tree_free(node
->tree
);
1204 /* Move the "node" pointer to the child of this node's parent in
1205 * the next child position.
1207 __isl_give isl_schedule_node
*isl_schedule_node_next_sibling(
1208 __isl_take isl_schedule_node
*node
)
1211 isl_schedule_tree
*parent
, *tree
;
1213 node
= isl_schedule_node_cow(node
);
1216 if (!isl_schedule_node_has_next_sibling(node
))
1217 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1218 "node has no next sibling",
1219 return isl_schedule_node_free(node
));
1221 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1222 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1225 return isl_schedule_node_free(node
);
1226 node
->child_pos
[n
- 1]++;
1227 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1228 node
->child_pos
[n
- 1]);
1229 isl_schedule_tree_free(parent
);
1231 return isl_schedule_node_free(node
);
1232 isl_schedule_tree_free(node
->tree
);
1238 /* Return a copy to the child at position "pos" of "node".
1240 __isl_give isl_schedule_node
*isl_schedule_node_get_child(
1241 __isl_keep isl_schedule_node
*node
, int pos
)
1243 return isl_schedule_node_child(isl_schedule_node_copy(node
), pos
);
1246 /* Traverse the descendant of "node" in depth-first order, including
1247 * "node" itself. Call "enter" whenever a node is entered and "leave"
1248 * whenever a node is left. The callback "enter" is responsible
1249 * for moving to the deepest initial subtree of its argument that
1250 * should be traversed.
1252 static __isl_give isl_schedule_node
*traverse(
1253 __isl_take isl_schedule_node
*node
,
1254 __isl_give isl_schedule_node
*(*enter
)(
1255 __isl_take isl_schedule_node
*node
, void *user
),
1256 __isl_give isl_schedule_node
*(*leave
)(
1257 __isl_take isl_schedule_node
*node
, void *user
),
1265 depth
= isl_schedule_node_get_tree_depth(node
);
1267 node
= enter(node
, user
);
1268 node
= leave(node
, user
);
1269 while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
&&
1270 !isl_schedule_node_has_next_sibling(node
)) {
1271 node
= isl_schedule_node_parent(node
);
1272 node
= leave(node
, user
);
1274 if (node
&& isl_schedule_node_get_tree_depth(node
) > depth
)
1275 node
= isl_schedule_node_next_sibling(node
);
1276 } while (node
&& isl_schedule_node_get_tree_depth(node
) > depth
);
1281 /* Internal data structure for isl_schedule_node_foreach_descendant_top_down.
1283 * "fn" is the user-specified callback function.
1284 * "user" is the user-specified argument for the callback.
1286 struct isl_schedule_node_preorder_data
{
1287 isl_bool (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
);
1291 /* Callback for "traverse" to enter a node and to move
1292 * to the deepest initial subtree that should be traversed
1293 * for use in a preorder visit.
1295 * If the user callback returns a negative value, then we abort
1296 * the traversal. If this callback returns zero, then we skip
1297 * the subtree rooted at the current node. Otherwise, we move
1298 * down to the first child and repeat the process until a leaf
1301 static __isl_give isl_schedule_node
*preorder_enter(
1302 __isl_take isl_schedule_node
*node
, void *user
)
1304 struct isl_schedule_node_preorder_data
*data
= user
;
1312 r
= data
->fn(node
, data
->user
);
1314 return isl_schedule_node_free(node
);
1315 if (r
== isl_bool_false
)
1317 } while (isl_schedule_node_has_children(node
) &&
1318 (node
= isl_schedule_node_first_child(node
)) != NULL
);
1323 /* Callback for "traverse" to leave a node
1324 * for use in a preorder visit.
1325 * Since we already visited the node when we entered it,
1326 * we do not need to do anything here.
1328 static __isl_give isl_schedule_node
*preorder_leave(
1329 __isl_take isl_schedule_node
*node
, void *user
)
1334 /* Traverse the descendants of "node" (including the node itself)
1335 * in depth first preorder.
1337 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1338 * If "fn" returns 0 on any of the nodes, then the subtree rooted
1339 * at that node is skipped.
1341 * Return 0 on success and -1 on failure.
1343 isl_stat
isl_schedule_node_foreach_descendant_top_down(
1344 __isl_keep isl_schedule_node
*node
,
1345 isl_bool (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
),
1348 struct isl_schedule_node_preorder_data data
= { fn
, user
};
1350 node
= isl_schedule_node_copy(node
);
1351 node
= traverse(node
, &preorder_enter
, &preorder_leave
, &data
);
1352 isl_schedule_node_free(node
);
1354 return node
? isl_stat_ok
: isl_stat_error
;
1357 /* Internal data structure for isl_schedule_node_map_descendant_bottom_up.
1359 * "fn" is the user-specified callback function.
1360 * "user" is the user-specified argument for the callback.
1362 struct isl_schedule_node_postorder_data
{
1363 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1368 /* Callback for "traverse" to enter a node and to move
1369 * to the deepest initial subtree that should be traversed
1370 * for use in a postorder visit.
1372 * Since we are performing a postorder visit, we only need
1373 * to move to the deepest initial leaf here.
1375 static __isl_give isl_schedule_node
*postorder_enter(
1376 __isl_take isl_schedule_node
*node
, void *user
)
1378 while (node
&& isl_schedule_node_has_children(node
))
1379 node
= isl_schedule_node_first_child(node
);
1384 /* Callback for "traverse" to leave a node
1385 * for use in a postorder visit.
1387 * Since we are performing a postorder visit, we need
1388 * to call the user callback here.
1390 static __isl_give isl_schedule_node
*postorder_leave(
1391 __isl_take isl_schedule_node
*node
, void *user
)
1393 struct isl_schedule_node_postorder_data
*data
= user
;
1395 return data
->fn(node
, data
->user
);
1398 /* Traverse the descendants of "node" (including the node itself)
1399 * in depth first postorder, allowing the user to modify the visited node.
1400 * The traversal continues from the node returned by the callback function.
1401 * It is the responsibility of the user to ensure that this does not
1402 * lead to an infinite loop. It is safest to always return a pointer
1403 * to the same position (same ancestors and child positions) as the input node.
1405 __isl_give isl_schedule_node
*isl_schedule_node_map_descendant_bottom_up(
1406 __isl_take isl_schedule_node
*node
,
1407 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1408 void *user
), void *user
)
1410 struct isl_schedule_node_postorder_data data
= { fn
, user
};
1412 return traverse(node
, &postorder_enter
, &postorder_leave
, &data
);
1415 /* Traverse the ancestors of "node" from the root down to and including
1416 * the parent of "node", calling "fn" on each of them.
1418 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1420 * Return 0 on success and -1 on failure.
1422 isl_stat
isl_schedule_node_foreach_ancestor_top_down(
1423 __isl_keep isl_schedule_node
*node
,
1424 isl_stat (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
),
1430 return isl_stat_error
;
1432 n
= isl_schedule_node_get_tree_depth(node
);
1433 for (i
= 0; i
< n
; ++i
) {
1434 isl_schedule_node
*ancestor
;
1437 ancestor
= isl_schedule_node_copy(node
);
1438 ancestor
= isl_schedule_node_ancestor(ancestor
, n
- i
);
1439 r
= fn(ancestor
, user
);
1440 isl_schedule_node_free(ancestor
);
1442 return isl_stat_error
;
1448 /* Is any node in the subtree rooted at "node" anchored?
1449 * That is, do any of these nodes reference the outer band nodes?
1451 isl_bool
isl_schedule_node_is_subtree_anchored(
1452 __isl_keep isl_schedule_node
*node
)
1455 return isl_bool_error
;
1456 return isl_schedule_tree_is_subtree_anchored(node
->tree
);
1459 /* Return the number of members in the given band node.
1461 unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node
*node
)
1463 return node
? isl_schedule_tree_band_n_member(node
->tree
) : 0;
1466 /* Is the band member at position "pos" of the band node "node"
1467 * marked coincident?
1469 isl_bool
isl_schedule_node_band_member_get_coincident(
1470 __isl_keep isl_schedule_node
*node
, int pos
)
1473 return isl_bool_error
;
1474 return isl_schedule_tree_band_member_get_coincident(node
->tree
, pos
);
1477 /* Mark the band member at position "pos" the band node "node"
1478 * as being coincident or not according to "coincident".
1480 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_coincident(
1481 __isl_take isl_schedule_node
*node
, int pos
, int coincident
)
1484 isl_schedule_tree
*tree
;
1488 c
= isl_schedule_node_band_member_get_coincident(node
, pos
);
1489 if (c
== coincident
)
1492 tree
= isl_schedule_tree_copy(node
->tree
);
1493 tree
= isl_schedule_tree_band_member_set_coincident(tree
, pos
,
1495 node
= isl_schedule_node_graft_tree(node
, tree
);
1500 /* Is the band node "node" marked permutable?
1502 isl_bool
isl_schedule_node_band_get_permutable(
1503 __isl_keep isl_schedule_node
*node
)
1506 return isl_bool_error
;
1508 return isl_schedule_tree_band_get_permutable(node
->tree
);
1511 /* Mark the band node "node" permutable or not according to "permutable"?
1513 __isl_give isl_schedule_node
*isl_schedule_node_band_set_permutable(
1514 __isl_take isl_schedule_node
*node
, int permutable
)
1516 isl_schedule_tree
*tree
;
1520 if (isl_schedule_node_band_get_permutable(node
) == permutable
)
1523 tree
= isl_schedule_tree_copy(node
->tree
);
1524 tree
= isl_schedule_tree_band_set_permutable(tree
, permutable
);
1525 node
= isl_schedule_node_graft_tree(node
, tree
);
1530 /* Return the schedule space of the band node.
1532 __isl_give isl_space
*isl_schedule_node_band_get_space(
1533 __isl_keep isl_schedule_node
*node
)
1538 return isl_schedule_tree_band_get_space(node
->tree
);
1541 /* Return the schedule of the band node in isolation.
1543 __isl_give isl_multi_union_pw_aff
*isl_schedule_node_band_get_partial_schedule(
1544 __isl_keep isl_schedule_node
*node
)
1549 return isl_schedule_tree_band_get_partial_schedule(node
->tree
);
1552 /* Return the schedule of the band node in isolation in the form of
1555 * If the band does not have any members, then we construct a universe map
1556 * with the universe of the domain elements reaching the node as domain.
1557 * Otherwise, we extract an isl_multi_union_pw_aff representation and
1558 * convert that to an isl_union_map.
1560 __isl_give isl_union_map
*isl_schedule_node_band_get_partial_schedule_union_map(
1561 __isl_keep isl_schedule_node
*node
)
1563 isl_multi_union_pw_aff
*mupa
;
1568 if (isl_schedule_node_get_type(node
) != isl_schedule_node_band
)
1569 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1570 "not a band node", return NULL
);
1571 if (isl_schedule_node_band_n_member(node
) == 0) {
1572 isl_union_set
*domain
;
1574 domain
= isl_schedule_node_get_universe_domain(node
);
1575 return isl_union_map_from_domain(domain
);
1578 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
1579 return isl_union_map_from_multi_union_pw_aff(mupa
);
1582 /* Return the loop AST generation type for the band member of band node "node"
1583 * at position "pos".
1585 enum isl_ast_loop_type
isl_schedule_node_band_member_get_ast_loop_type(
1586 __isl_keep isl_schedule_node
*node
, int pos
)
1589 return isl_ast_loop_error
;
1591 return isl_schedule_tree_band_member_get_ast_loop_type(node
->tree
, pos
);
1594 /* Set the loop AST generation type for the band member of band node "node"
1595 * at position "pos" to "type".
1597 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_ast_loop_type(
1598 __isl_take isl_schedule_node
*node
, int pos
,
1599 enum isl_ast_loop_type type
)
1601 isl_schedule_tree
*tree
;
1606 tree
= isl_schedule_tree_copy(node
->tree
);
1607 tree
= isl_schedule_tree_band_member_set_ast_loop_type(tree
, pos
, type
);
1608 return isl_schedule_node_graft_tree(node
, tree
);
1611 /* Return the loop AST generation type for the band member of band node "node"
1612 * at position "pos" for the isolated part.
1614 enum isl_ast_loop_type
isl_schedule_node_band_member_get_isolate_ast_loop_type(
1615 __isl_keep isl_schedule_node
*node
, int pos
)
1618 return isl_ast_loop_error
;
1620 return isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1624 /* Set the loop AST generation type for the band member of band node "node"
1625 * at position "pos" for the isolated part to "type".
1627 __isl_give isl_schedule_node
*
1628 isl_schedule_node_band_member_set_isolate_ast_loop_type(
1629 __isl_take isl_schedule_node
*node
, int pos
,
1630 enum isl_ast_loop_type type
)
1632 isl_schedule_tree
*tree
;
1637 tree
= isl_schedule_tree_copy(node
->tree
);
1638 tree
= isl_schedule_tree_band_member_set_isolate_ast_loop_type(tree
,
1640 return isl_schedule_node_graft_tree(node
, tree
);
1643 /* Return the AST build options associated to band node "node".
1645 __isl_give isl_union_set
*isl_schedule_node_band_get_ast_build_options(
1646 __isl_keep isl_schedule_node
*node
)
1651 return isl_schedule_tree_band_get_ast_build_options(node
->tree
);
1654 /* Replace the AST build options associated to band node "node" by "options".
1656 __isl_give isl_schedule_node
*isl_schedule_node_band_set_ast_build_options(
1657 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*options
)
1659 isl_schedule_tree
*tree
;
1661 if (!node
|| !options
)
1664 tree
= isl_schedule_tree_copy(node
->tree
);
1665 tree
= isl_schedule_tree_band_set_ast_build_options(tree
, options
);
1666 return isl_schedule_node_graft_tree(node
, tree
);
1668 isl_schedule_node_free(node
);
1669 isl_union_set_free(options
);
1673 /* Return the "isolate" option associated to band node "node".
1675 __isl_give isl_set
*isl_schedule_node_band_get_ast_isolate_option(
1676 __isl_keep isl_schedule_node
*node
)
1683 depth
= isl_schedule_node_get_schedule_depth(node
);
1684 return isl_schedule_tree_band_get_ast_isolate_option(node
->tree
, depth
);
1687 /* Make sure that that spaces of "node" and "mv" are the same.
1688 * Return -1 on error, reporting the error to the user.
1690 static int check_space_multi_val(__isl_keep isl_schedule_node
*node
,
1691 __isl_keep isl_multi_val
*mv
)
1693 isl_space
*node_space
, *mv_space
;
1696 node_space
= isl_schedule_node_band_get_space(node
);
1697 mv_space
= isl_multi_val_get_space(mv
);
1698 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1699 mv_space
, isl_dim_set
);
1700 isl_space_free(mv_space
);
1701 isl_space_free(node_space
);
1705 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1706 "spaces don't match", return -1);
1711 /* Multiply the partial schedule of the band node "node"
1712 * with the factors in "mv".
1714 __isl_give isl_schedule_node
*isl_schedule_node_band_scale(
1715 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1717 isl_schedule_tree
*tree
;
1722 if (check_space_multi_val(node
, mv
) < 0)
1724 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1728 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1729 "cannot scale band node with anchored subtree",
1732 tree
= isl_schedule_node_get_tree(node
);
1733 tree
= isl_schedule_tree_band_scale(tree
, mv
);
1734 return isl_schedule_node_graft_tree(node
, tree
);
1736 isl_multi_val_free(mv
);
1737 isl_schedule_node_free(node
);
1741 /* Divide the partial schedule of the band node "node"
1742 * by the factors in "mv".
1744 __isl_give isl_schedule_node
*isl_schedule_node_band_scale_down(
1745 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1747 isl_schedule_tree
*tree
;
1752 if (check_space_multi_val(node
, mv
) < 0)
1754 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1758 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1759 "cannot scale down band node with anchored subtree",
1762 tree
= isl_schedule_node_get_tree(node
);
1763 tree
= isl_schedule_tree_band_scale_down(tree
, mv
);
1764 return isl_schedule_node_graft_tree(node
, tree
);
1766 isl_multi_val_free(mv
);
1767 isl_schedule_node_free(node
);
1771 /* Reduce the partial schedule of the band node "node"
1772 * modulo the factors in "mv".
1774 __isl_give isl_schedule_node
*isl_schedule_node_band_mod(
1775 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1777 isl_schedule_tree
*tree
;
1782 if (check_space_multi_val(node
, mv
) < 0)
1784 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1788 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1789 "cannot perform mod on band node with anchored subtree",
1792 tree
= isl_schedule_node_get_tree(node
);
1793 tree
= isl_schedule_tree_band_mod(tree
, mv
);
1794 return isl_schedule_node_graft_tree(node
, tree
);
1796 isl_multi_val_free(mv
);
1797 isl_schedule_node_free(node
);
1801 /* Make sure that that spaces of "node" and "mupa" are the same.
1802 * Return isl_stat_error on error, reporting the error to the user.
1804 static isl_stat
check_space_multi_union_pw_aff(
1805 __isl_keep isl_schedule_node
*node
,
1806 __isl_keep isl_multi_union_pw_aff
*mupa
)
1808 isl_space
*node_space
, *mupa_space
;
1811 node_space
= isl_schedule_node_band_get_space(node
);
1812 mupa_space
= isl_multi_union_pw_aff_get_space(mupa
);
1813 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1814 mupa_space
, isl_dim_set
);
1815 isl_space_free(mupa_space
);
1816 isl_space_free(node_space
);
1818 return isl_stat_error
;
1820 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1821 "spaces don't match", return isl_stat_error
);
1826 /* Shift the partial schedule of the band node "node" by "shift".
1828 __isl_give isl_schedule_node
*isl_schedule_node_band_shift(
1829 __isl_take isl_schedule_node
*node
,
1830 __isl_take isl_multi_union_pw_aff
*shift
)
1832 isl_schedule_tree
*tree
;
1835 if (!node
|| !shift
)
1837 if (check_space_multi_union_pw_aff(node
, shift
) < 0)
1839 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1843 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1844 "cannot shift band node with anchored subtree",
1847 tree
= isl_schedule_node_get_tree(node
);
1848 tree
= isl_schedule_tree_band_shift(tree
, shift
);
1849 return isl_schedule_node_graft_tree(node
, tree
);
1851 isl_multi_union_pw_aff_free(shift
);
1852 isl_schedule_node_free(node
);
1856 /* Tile "node" with tile sizes "sizes".
1858 * The current node is replaced by two nested nodes corresponding
1859 * to the tile dimensions and the point dimensions.
1861 * Return a pointer to the outer (tile) node.
1863 * If any of the descendants of "node" depend on the set of outer band nodes,
1864 * then we refuse to tile the node.
1866 * If the scale tile loops option is set, then the tile loops
1867 * are scaled by the tile sizes. If the shift point loops option is set,
1868 * then the point loops are shifted to start at zero.
1869 * In particular, these options affect the tile and point loop schedules
1872 * scale shift original tile point
1874 * 0 0 i floor(i/s) i
1875 * 1 0 i s * floor(i/s) i
1876 * 0 1 i floor(i/s) i - s * floor(i/s)
1877 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1879 __isl_give isl_schedule_node
*isl_schedule_node_band_tile(
1880 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*sizes
)
1882 isl_schedule_tree
*tree
;
1885 if (!node
|| !sizes
)
1887 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1891 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1892 "cannot tile band node with anchored subtree",
1895 if (check_space_multi_val(node
, sizes
) < 0)
1898 tree
= isl_schedule_node_get_tree(node
);
1899 tree
= isl_schedule_tree_band_tile(tree
, sizes
);
1900 return isl_schedule_node_graft_tree(node
, tree
);
1902 isl_multi_val_free(sizes
);
1903 isl_schedule_node_free(node
);
1907 /* Move the band node "node" down to all the leaves in the subtree
1909 * Return a pointer to the node in the resulting tree that is in the same
1910 * position as the node pointed to by "node" in the original tree.
1912 * If the node only has a leaf child, then nothing needs to be done.
1913 * Otherwise, the child of the node is removed and the result is
1914 * appended to all the leaves in the subtree rooted at the original child.
1915 * Since the node is moved to the leaves, it needs to be expanded
1916 * according to the expansion, if any, defined by that subtree.
1917 * In the end, the original node is replaced by the result of
1918 * attaching copies of the expanded node to the leaves.
1920 * If any of the nodes in the subtree rooted at "node" depend on
1921 * the set of outer band nodes then we refuse to sink the band node.
1923 __isl_give isl_schedule_node
*isl_schedule_node_band_sink(
1924 __isl_take isl_schedule_node
*node
)
1926 enum isl_schedule_node_type type
;
1927 isl_schedule_tree
*tree
, *child
;
1928 isl_union_pw_multi_aff
*contraction
;
1934 type
= isl_schedule_node_get_type(node
);
1935 if (type
!= isl_schedule_node_band
)
1936 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1937 "not a band node", isl_schedule_node_free(node
));
1938 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1940 return isl_schedule_node_free(node
);
1942 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1943 "cannot sink band node in anchored subtree",
1944 isl_schedule_node_free(node
));
1945 if (isl_schedule_tree_n_children(node
->tree
) == 0)
1948 contraction
= isl_schedule_node_get_subtree_contraction(node
);
1950 tree
= isl_schedule_node_get_tree(node
);
1951 child
= isl_schedule_tree_get_child(tree
, 0);
1952 tree
= isl_schedule_tree_reset_children(tree
);
1953 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, contraction
);
1954 tree
= isl_schedule_tree_append_to_leaves(child
, tree
);
1956 return isl_schedule_node_graft_tree(node
, tree
);
1959 /* Split "node" into two nested band nodes, one with the first "pos"
1960 * dimensions and one with the remaining dimensions.
1961 * The schedules of the two band nodes live in anonymous spaces.
1963 __isl_give isl_schedule_node
*isl_schedule_node_band_split(
1964 __isl_take isl_schedule_node
*node
, int pos
)
1966 isl_schedule_tree
*tree
;
1968 tree
= isl_schedule_node_get_tree(node
);
1969 tree
= isl_schedule_tree_band_split(tree
, pos
);
1970 return isl_schedule_node_graft_tree(node
, tree
);
1973 /* Return the context of the context node "node".
1975 __isl_give isl_set
*isl_schedule_node_context_get_context(
1976 __isl_keep isl_schedule_node
*node
)
1981 return isl_schedule_tree_context_get_context(node
->tree
);
1984 /* Return the domain of the domain node "node".
1986 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
1987 __isl_keep isl_schedule_node
*node
)
1992 return isl_schedule_tree_domain_get_domain(node
->tree
);
1995 /* Return the expansion map of expansion node "node".
1997 __isl_give isl_union_map
*isl_schedule_node_expansion_get_expansion(
1998 __isl_keep isl_schedule_node
*node
)
2003 return isl_schedule_tree_expansion_get_expansion(node
->tree
);
2006 /* Return the contraction of expansion node "node".
2008 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_expansion_get_contraction(
2009 __isl_keep isl_schedule_node
*node
)
2014 return isl_schedule_tree_expansion_get_contraction(node
->tree
);
2017 /* Replace the contraction and the expansion of the expansion node "node"
2018 * by "contraction" and "expansion".
2020 __isl_give isl_schedule_node
*
2021 isl_schedule_node_expansion_set_contraction_and_expansion(
2022 __isl_take isl_schedule_node
*node
,
2023 __isl_take isl_union_pw_multi_aff
*contraction
,
2024 __isl_take isl_union_map
*expansion
)
2026 isl_schedule_tree
*tree
;
2028 if (!node
|| !contraction
|| !expansion
)
2031 tree
= isl_schedule_tree_copy(node
->tree
);
2032 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
2033 contraction
, expansion
);
2034 return isl_schedule_node_graft_tree(node
, tree
);
2036 isl_schedule_node_free(node
);
2037 isl_union_pw_multi_aff_free(contraction
);
2038 isl_union_map_free(expansion
);
2042 /* Return the extension of the extension node "node".
2044 __isl_give isl_union_map
*isl_schedule_node_extension_get_extension(
2045 __isl_keep isl_schedule_node
*node
)
2050 return isl_schedule_tree_extension_get_extension(node
->tree
);
2053 /* Replace the extension of extension node "node" by "extension".
2055 __isl_give isl_schedule_node
*isl_schedule_node_extension_set_extension(
2056 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
2058 isl_schedule_tree
*tree
;
2060 if (!node
|| !extension
)
2063 tree
= isl_schedule_tree_copy(node
->tree
);
2064 tree
= isl_schedule_tree_extension_set_extension(tree
, extension
);
2065 return isl_schedule_node_graft_tree(node
, tree
);
2067 isl_schedule_node_free(node
);
2068 isl_union_map_free(extension
);
2072 /* Return the filter of the filter node "node".
2074 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
2075 __isl_keep isl_schedule_node
*node
)
2080 return isl_schedule_tree_filter_get_filter(node
->tree
);
2083 /* Replace the filter of filter node "node" by "filter".
2085 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
2086 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2088 isl_schedule_tree
*tree
;
2090 if (!node
|| !filter
)
2093 tree
= isl_schedule_tree_copy(node
->tree
);
2094 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
2095 return isl_schedule_node_graft_tree(node
, tree
);
2097 isl_schedule_node_free(node
);
2098 isl_union_set_free(filter
);
2102 /* Intersect the filter of filter node "node" with "filter".
2104 * If the filter of the node is already a subset of "filter",
2105 * then leave the node unchanged.
2107 __isl_give isl_schedule_node
*isl_schedule_node_filter_intersect_filter(
2108 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2110 isl_union_set
*node_filter
= NULL
;
2113 if (!node
|| !filter
)
2116 node_filter
= isl_schedule_node_filter_get_filter(node
);
2117 subset
= isl_union_set_is_subset(node_filter
, filter
);
2121 isl_union_set_free(node_filter
);
2122 isl_union_set_free(filter
);
2125 node_filter
= isl_union_set_intersect(node_filter
, filter
);
2126 node
= isl_schedule_node_filter_set_filter(node
, node_filter
);
2129 isl_schedule_node_free(node
);
2130 isl_union_set_free(node_filter
);
2131 isl_union_set_free(filter
);
2135 /* Return the guard of the guard node "node".
2137 __isl_give isl_set
*isl_schedule_node_guard_get_guard(
2138 __isl_keep isl_schedule_node
*node
)
2143 return isl_schedule_tree_guard_get_guard(node
->tree
);
2146 /* Return the mark identifier of the mark node "node".
2148 __isl_give isl_id
*isl_schedule_node_mark_get_id(
2149 __isl_keep isl_schedule_node
*node
)
2154 return isl_schedule_tree_mark_get_id(node
->tree
);
2157 /* Replace the child at position "pos" of the sequence node "node"
2158 * by the children of sequence root node of "tree".
2160 __isl_give isl_schedule_node
*isl_schedule_node_sequence_splice(
2161 __isl_take isl_schedule_node
*node
, int pos
,
2162 __isl_take isl_schedule_tree
*tree
)
2164 isl_schedule_tree
*node_tree
;
2168 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2169 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2170 "not a sequence node", goto error
);
2171 if (isl_schedule_tree_get_type(tree
) != isl_schedule_node_sequence
)
2172 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2173 "not a sequence node", goto error
);
2174 node_tree
= isl_schedule_node_get_tree(node
);
2175 node_tree
= isl_schedule_tree_sequence_splice(node_tree
, pos
, tree
);
2176 node
= isl_schedule_node_graft_tree(node
, node_tree
);
2180 isl_schedule_node_free(node
);
2181 isl_schedule_tree_free(tree
);
2185 /* Given a sequence node "node", with a child at position "pos" that
2186 * is also a sequence node, attach the children of that node directly
2187 * as children of "node" at that position, replacing the original child.
2189 * The filters of these children are intersected with the filter
2190 * of the child at position "pos".
2192 __isl_give isl_schedule_node
*isl_schedule_node_sequence_splice_child(
2193 __isl_take isl_schedule_node
*node
, int pos
)
2196 isl_union_set
*filter
;
2197 isl_schedule_node
*child
;
2198 isl_schedule_tree
*tree
;
2202 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2203 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2204 "not a sequence node", isl_schedule_node_free(node
));
2205 node
= isl_schedule_node_child(node
, pos
);
2206 node
= isl_schedule_node_child(node
, 0);
2207 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2208 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2209 "not a sequence node", isl_schedule_node_free(node
));
2210 child
= isl_schedule_node_copy(node
);
2211 node
= isl_schedule_node_parent(node
);
2212 filter
= isl_schedule_node_filter_get_filter(node
);
2213 n
= isl_schedule_node_n_children(child
);
2214 for (i
= 0; i
< n
; ++i
) {
2215 child
= isl_schedule_node_child(child
, i
);
2216 child
= isl_schedule_node_filter_intersect_filter(child
,
2217 isl_union_set_copy(filter
));
2218 child
= isl_schedule_node_parent(child
);
2220 isl_union_set_free(filter
);
2221 tree
= isl_schedule_node_get_tree(child
);
2222 isl_schedule_node_free(child
);
2223 node
= isl_schedule_node_parent(node
);
2224 node
= isl_schedule_node_sequence_splice(node
, pos
, tree
);
2229 /* Update the ancestors of "node" to point to the tree that "node"
2231 * That is, replace the child in the original parent that corresponds
2232 * to the current tree position by node->tree and continue updating
2233 * the ancestors in the same way until the root is reached.
2235 * If "fn" is not NULL, then it is called on each ancestor as we move up
2236 * the tree so that it can modify the ancestor before it is added
2237 * to the list of ancestors of the modified node.
2238 * The additional "pos" argument records the position
2239 * of the "tree" argument in the original schedule tree.
2241 * If "node" originally points to a leaf of the schedule tree, then make sure
2242 * that in the end it points to a leaf in the updated schedule tree.
2244 static __isl_give isl_schedule_node
*update_ancestors(
2245 __isl_take isl_schedule_node
*node
,
2246 __isl_give isl_schedule_tree
*(*fn
)(__isl_take isl_schedule_tree
*tree
,
2247 __isl_keep isl_schedule_node
*pos
, void *user
), void *user
)
2252 isl_schedule_tree
*tree
;
2253 isl_schedule_node
*pos
= NULL
;
2256 pos
= isl_schedule_node_copy(node
);
2258 node
= isl_schedule_node_cow(node
);
2260 return isl_schedule_node_free(pos
);
2262 ctx
= isl_schedule_node_get_ctx(node
);
2263 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
2264 tree
= isl_schedule_tree_copy(node
->tree
);
2266 for (i
= n
- 1; i
>= 0; --i
) {
2267 isl_schedule_tree
*parent
;
2269 parent
= isl_schedule_tree_list_get_schedule_tree(
2270 node
->ancestors
, i
);
2271 parent
= isl_schedule_tree_replace_child(parent
,
2272 node
->child_pos
[i
], tree
);
2274 pos
= isl_schedule_node_parent(pos
);
2275 parent
= fn(parent
, pos
, user
);
2277 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
2278 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
2284 isl_schedule_node_free(pos
);
2286 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
2287 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
2289 isl_schedule_tree_free(node
->tree
);
2290 node
->tree
= isl_schedule_node_get_leaf(node
);
2293 if (!node
->schedule
|| !node
->ancestors
)
2294 return isl_schedule_node_free(node
);
2299 /* Replace the subtree that "pos" points to by "tree", updating
2300 * the ancestors to maintain a consistent state.
2302 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
2303 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
2307 if (pos
->tree
== tree
) {
2308 isl_schedule_tree_free(tree
);
2312 pos
= isl_schedule_node_cow(pos
);
2316 isl_schedule_tree_free(pos
->tree
);
2319 return update_ancestors(pos
, NULL
, NULL
);
2321 isl_schedule_node_free(pos
);
2322 isl_schedule_tree_free(tree
);
2326 /* Make sure we can insert a node between "node" and its parent.
2327 * Return -1 on error, reporting the reason why we cannot insert a node.
2329 static int check_insert(__isl_keep isl_schedule_node
*node
)
2332 enum isl_schedule_node_type type
;
2334 has_parent
= isl_schedule_node_has_parent(node
);
2338 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2339 "cannot insert node outside of root", return -1);
2341 type
= isl_schedule_node_get_parent_type(node
);
2342 if (type
== isl_schedule_node_error
)
2344 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
2345 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2346 "cannot insert node between set or sequence node "
2347 "and its filter children", return -1);
2352 /* Insert a band node with partial schedule "mupa" between "node" and
2354 * Return a pointer to the new band node.
2356 * If any of the nodes in the subtree rooted at "node" depend on
2357 * the set of outer band nodes then we refuse to insert the band node.
2359 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
2360 __isl_take isl_schedule_node
*node
,
2361 __isl_take isl_multi_union_pw_aff
*mupa
)
2364 isl_schedule_band
*band
;
2365 isl_schedule_tree
*tree
;
2367 if (check_insert(node
) < 0)
2368 node
= isl_schedule_node_free(node
);
2369 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2373 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2374 "cannot insert band node in anchored subtree",
2377 tree
= isl_schedule_node_get_tree(node
);
2378 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
2379 tree
= isl_schedule_tree_insert_band(tree
, band
);
2380 node
= isl_schedule_node_graft_tree(node
, tree
);
2384 isl_schedule_node_free(node
);
2385 isl_multi_union_pw_aff_free(mupa
);
2389 /* Insert a context node with context "context" between "node" and its parent.
2390 * Return a pointer to the new context node.
2392 __isl_give isl_schedule_node
*isl_schedule_node_insert_context(
2393 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
2395 isl_schedule_tree
*tree
;
2397 if (check_insert(node
) < 0)
2398 node
= isl_schedule_node_free(node
);
2400 tree
= isl_schedule_node_get_tree(node
);
2401 tree
= isl_schedule_tree_insert_context(tree
, context
);
2402 node
= isl_schedule_node_graft_tree(node
, tree
);
2407 /* Insert an expansion node with the given "contraction" and "expansion"
2408 * between "node" and its parent.
2409 * Return a pointer to the new expansion node.
2411 * Typically the domain and range spaces of the expansion are different.
2412 * This means that only one of them can refer to the current domain space
2413 * in a consistent tree. It is up to the caller to ensure that the tree
2414 * returns to a consistent state.
2416 __isl_give isl_schedule_node
*isl_schedule_node_insert_expansion(
2417 __isl_take isl_schedule_node
*node
,
2418 __isl_take isl_union_pw_multi_aff
*contraction
,
2419 __isl_take isl_union_map
*expansion
)
2421 isl_schedule_tree
*tree
;
2423 if (check_insert(node
) < 0)
2424 node
= isl_schedule_node_free(node
);
2426 tree
= isl_schedule_node_get_tree(node
);
2427 tree
= isl_schedule_tree_insert_expansion(tree
, contraction
, expansion
);
2428 node
= isl_schedule_node_graft_tree(node
, tree
);
2433 /* Insert an extension node with extension "extension" between "node" and
2435 * Return a pointer to the new extension node.
2437 __isl_give isl_schedule_node
*isl_schedule_node_insert_extension(
2438 __isl_take isl_schedule_node
*node
,
2439 __isl_take isl_union_map
*extension
)
2441 isl_schedule_tree
*tree
;
2443 tree
= isl_schedule_node_get_tree(node
);
2444 tree
= isl_schedule_tree_insert_extension(tree
, extension
);
2445 node
= isl_schedule_node_graft_tree(node
, tree
);
2450 /* Insert a filter node with filter "filter" between "node" and its parent.
2451 * Return a pointer to the new filter node.
2453 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
2454 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2456 isl_schedule_tree
*tree
;
2458 if (check_insert(node
) < 0)
2459 node
= isl_schedule_node_free(node
);
2461 tree
= isl_schedule_node_get_tree(node
);
2462 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2463 node
= isl_schedule_node_graft_tree(node
, tree
);
2468 /* Insert a guard node with guard "guard" between "node" and its parent.
2469 * Return a pointer to the new guard node.
2471 __isl_give isl_schedule_node
*isl_schedule_node_insert_guard(
2472 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*guard
)
2474 isl_schedule_tree
*tree
;
2476 if (check_insert(node
) < 0)
2477 node
= isl_schedule_node_free(node
);
2479 tree
= isl_schedule_node_get_tree(node
);
2480 tree
= isl_schedule_tree_insert_guard(tree
, guard
);
2481 node
= isl_schedule_node_graft_tree(node
, tree
);
2486 /* Insert a mark node with mark identifier "mark" between "node" and
2488 * Return a pointer to the new mark node.
2490 __isl_give isl_schedule_node
*isl_schedule_node_insert_mark(
2491 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*mark
)
2493 isl_schedule_tree
*tree
;
2495 if (check_insert(node
) < 0)
2496 node
= isl_schedule_node_free(node
);
2498 tree
= isl_schedule_node_get_tree(node
);
2499 tree
= isl_schedule_tree_insert_mark(tree
, mark
);
2500 node
= isl_schedule_node_graft_tree(node
, tree
);
2505 /* Attach the current subtree of "node" to a sequence of filter tree nodes
2506 * with filters described by "filters", attach this sequence
2507 * of filter tree nodes as children to a new tree of type "type" and
2508 * replace the original subtree of "node" by this new tree.
2509 * Each copy of the original subtree is simplified with respect
2510 * to the corresponding filter.
2512 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
2513 __isl_take isl_schedule_node
*node
,
2514 enum isl_schedule_node_type type
,
2515 __isl_take isl_union_set_list
*filters
)
2519 isl_schedule_tree
*tree
;
2520 isl_schedule_tree_list
*list
;
2522 if (check_insert(node
) < 0)
2523 node
= isl_schedule_node_free(node
);
2525 if (!node
|| !filters
)
2528 ctx
= isl_schedule_node_get_ctx(node
);
2529 n
= isl_union_set_list_n_union_set(filters
);
2530 list
= isl_schedule_tree_list_alloc(ctx
, n
);
2531 for (i
= 0; i
< n
; ++i
) {
2532 isl_schedule_node
*node_i
;
2533 isl_schedule_tree
*tree
;
2534 isl_union_set
*filter
;
2536 filter
= isl_union_set_list_get_union_set(filters
, i
);
2537 node_i
= isl_schedule_node_copy(node
);
2538 node_i
= isl_schedule_node_gist(node_i
,
2539 isl_union_set_copy(filter
));
2540 tree
= isl_schedule_node_get_tree(node_i
);
2541 isl_schedule_node_free(node_i
);
2542 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2543 list
= isl_schedule_tree_list_add(list
, tree
);
2545 tree
= isl_schedule_tree_from_children(type
, list
);
2546 node
= isl_schedule_node_graft_tree(node
, tree
);
2548 isl_union_set_list_free(filters
);
2551 isl_union_set_list_free(filters
);
2552 isl_schedule_node_free(node
);
2556 /* Insert a sequence node with child filters "filters" between "node" and
2557 * its parent. That is, the tree that "node" points to is attached
2558 * to each of the child nodes of the filter nodes.
2559 * Return a pointer to the new sequence node.
2561 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
2562 __isl_take isl_schedule_node
*node
,
2563 __isl_take isl_union_set_list
*filters
)
2565 return isl_schedule_node_insert_children(node
,
2566 isl_schedule_node_sequence
, filters
);
2569 /* Insert a set node with child filters "filters" between "node" and
2570 * its parent. That is, the tree that "node" points to is attached
2571 * to each of the child nodes of the filter nodes.
2572 * Return a pointer to the new set node.
2574 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
2575 __isl_take isl_schedule_node
*node
,
2576 __isl_take isl_union_set_list
*filters
)
2578 return isl_schedule_node_insert_children(node
,
2579 isl_schedule_node_set
, filters
);
2582 /* Remove "node" from its schedule tree and return a pointer
2583 * to the leaf at the same position in the updated schedule tree.
2585 * It is not allowed to remove the root of a schedule tree or
2586 * a child of a set or sequence node.
2588 __isl_give isl_schedule_node
*isl_schedule_node_cut(
2589 __isl_take isl_schedule_node
*node
)
2591 isl_schedule_tree
*leaf
;
2592 enum isl_schedule_node_type parent_type
;
2596 if (!isl_schedule_node_has_parent(node
))
2597 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2598 "cannot cut root", return isl_schedule_node_free(node
));
2600 parent_type
= isl_schedule_node_get_parent_type(node
);
2601 if (parent_type
== isl_schedule_node_set
||
2602 parent_type
== isl_schedule_node_sequence
)
2603 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2604 "cannot cut child of set or sequence",
2605 return isl_schedule_node_free(node
));
2607 leaf
= isl_schedule_node_get_leaf(node
);
2608 return isl_schedule_node_graft_tree(node
, leaf
);
2611 /* Remove a single node from the schedule tree, attaching the child
2612 * of "node" directly to its parent.
2613 * Return a pointer to this former child or to the leaf the position
2614 * of the original node if there was no child.
2615 * It is not allowed to remove the root of a schedule tree,
2616 * a set or sequence node, a child of a set or sequence node or
2617 * a band node with an anchored subtree.
2619 __isl_give isl_schedule_node
*isl_schedule_node_delete(
2620 __isl_take isl_schedule_node
*node
)
2623 isl_schedule_tree
*tree
;
2624 enum isl_schedule_node_type type
;
2629 if (isl_schedule_node_get_tree_depth(node
) == 0)
2630 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2631 "cannot delete root node",
2632 return isl_schedule_node_free(node
));
2633 n
= isl_schedule_node_n_children(node
);
2635 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2636 "can only delete node with a single child",
2637 return isl_schedule_node_free(node
));
2638 type
= isl_schedule_node_get_parent_type(node
);
2639 if (type
== isl_schedule_node_sequence
|| type
== isl_schedule_node_set
)
2640 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2641 "cannot delete child of set or sequence",
2642 return isl_schedule_node_free(node
));
2643 if (isl_schedule_node_get_type(node
) == isl_schedule_node_band
) {
2646 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2648 return isl_schedule_node_free(node
);
2650 isl_die(isl_schedule_node_get_ctx(node
),
2652 "cannot delete band node with anchored subtree",
2653 return isl_schedule_node_free(node
));
2656 tree
= isl_schedule_node_get_tree(node
);
2657 if (!tree
|| isl_schedule_tree_has_children(tree
)) {
2658 tree
= isl_schedule_tree_child(tree
, 0);
2660 isl_schedule_tree_free(tree
);
2661 tree
= isl_schedule_node_get_leaf(node
);
2663 node
= isl_schedule_node_graft_tree(node
, tree
);
2668 /* Internal data structure for the group_ancestor callback.
2670 * If "finished" is set, then we no longer need to modify
2671 * any further ancestors.
2673 * "contraction" and "expansion" represent the expansion
2674 * that reflects the grouping.
2676 * "domain" contains the domain elements that reach the position
2677 * where the grouping is performed. That is, it is the range
2678 * of the resulting expansion.
2679 * "domain_universe" is the universe of "domain".
2680 * "group" is the set of group elements, i.e., the domain
2681 * of the resulting expansion.
2682 * "group_universe" is the universe of "group".
2684 * "sched" is the schedule for the group elements, in pratice
2685 * an identity mapping on "group_universe".
2686 * "dim" is the dimension of "sched".
2688 struct isl_schedule_group_data
{
2691 isl_union_map
*expansion
;
2692 isl_union_pw_multi_aff
*contraction
;
2694 isl_union_set
*domain
;
2695 isl_union_set
*domain_universe
;
2696 isl_union_set
*group
;
2697 isl_union_set
*group_universe
;
2700 isl_multi_aff
*sched
;
2703 /* Is domain covered by data->domain within data->domain_universe?
2705 static int locally_covered_by_domain(__isl_keep isl_union_set
*domain
,
2706 struct isl_schedule_group_data
*data
)
2709 isl_union_set
*test
;
2711 test
= isl_union_set_copy(domain
);
2712 test
= isl_union_set_intersect(test
,
2713 isl_union_set_copy(data
->domain_universe
));
2714 is_subset
= isl_union_set_is_subset(test
, data
->domain
);
2715 isl_union_set_free(test
);
2720 /* Update the band tree root "tree" to refer to the group instances
2721 * in data->group rather than the original domain elements in data->domain.
2722 * "pos" is the position in the original schedule tree where the modified
2723 * "tree" will be attached.
2725 * Add the part of the identity schedule on the group instances data->sched
2726 * that corresponds to this band node to the band schedule.
2727 * If the domain elements that reach the node and that are part
2728 * of data->domain_universe are all elements of data->domain (and therefore
2729 * replaced by the group instances) then this data->domain_universe
2730 * is removed from the domain of the band schedule.
2732 static __isl_give isl_schedule_tree
*group_band(
2733 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2734 struct isl_schedule_group_data
*data
)
2736 isl_union_set
*domain
;
2738 isl_multi_union_pw_aff
*mupa
, *partial
;
2740 int depth
, n
, has_id
;
2742 domain
= isl_schedule_node_get_domain(pos
);
2743 is_covered
= locally_covered_by_domain(domain
, data
);
2744 if (is_covered
>= 0 && is_covered
) {
2745 domain
= isl_union_set_universe(domain
);
2746 domain
= isl_union_set_subtract(domain
,
2747 isl_union_set_copy(data
->domain_universe
));
2748 tree
= isl_schedule_tree_band_intersect_domain(tree
, domain
);
2750 isl_union_set_free(domain
);
2752 return isl_schedule_tree_free(tree
);
2753 depth
= isl_schedule_node_get_schedule_depth(pos
);
2754 n
= isl_schedule_tree_band_n_member(tree
);
2755 ma
= isl_multi_aff_copy(data
->sched
);
2756 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, depth
);
2757 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, n
, data
->dim
- depth
- n
);
2758 mupa
= isl_multi_union_pw_aff_from_multi_aff(ma
);
2759 partial
= isl_schedule_tree_band_get_partial_schedule(tree
);
2760 has_id
= isl_multi_union_pw_aff_has_tuple_id(partial
, isl_dim_set
);
2762 partial
= isl_multi_union_pw_aff_free(partial
);
2763 } else if (has_id
) {
2765 id
= isl_multi_union_pw_aff_get_tuple_id(partial
, isl_dim_set
);
2766 mupa
= isl_multi_union_pw_aff_set_tuple_id(mupa
,
2769 partial
= isl_multi_union_pw_aff_union_add(partial
, mupa
);
2770 tree
= isl_schedule_tree_band_set_partial_schedule(tree
, partial
);
2775 /* Drop the parameters in "uset" that are not also in "space".
2776 * "n" is the number of parameters in "space".
2778 static __isl_give isl_union_set
*union_set_drop_extra_params(
2779 __isl_take isl_union_set
*uset
, __isl_keep isl_space
*space
, int n
)
2783 uset
= isl_union_set_align_params(uset
, isl_space_copy(space
));
2784 n2
= isl_union_set_dim(uset
, isl_dim_param
);
2785 uset
= isl_union_set_project_out(uset
, isl_dim_param
, n
, n2
- n
);
2790 /* Update the context tree root "tree" to refer to the group instances
2791 * in data->group rather than the original domain elements in data->domain.
2792 * "pos" is the position in the original schedule tree where the modified
2793 * "tree" will be attached.
2795 * We do not actually need to update "tree" since a context node only
2796 * refers to the schedule space. However, we may need to update "data"
2797 * to not refer to any parameters introduced by the context node.
2799 static __isl_give isl_schedule_tree
*group_context(
2800 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2801 struct isl_schedule_group_data
*data
)
2804 isl_union_set
*domain
;
2808 if (isl_schedule_node_get_tree_depth(pos
) == 1)
2811 domain
= isl_schedule_node_get_universe_domain(pos
);
2812 space
= isl_union_set_get_space(domain
);
2813 isl_union_set_free(domain
);
2815 n1
= isl_space_dim(space
, isl_dim_param
);
2816 data
->expansion
= isl_union_map_align_params(data
->expansion
, space
);
2817 n2
= isl_union_map_dim(data
->expansion
, isl_dim_param
);
2819 if (!data
->expansion
)
2820 return isl_schedule_tree_free(tree
);
2824 involves
= isl_union_map_involves_dims(data
->expansion
,
2825 isl_dim_param
, n1
, n2
- n1
);
2827 return isl_schedule_tree_free(tree
);
2829 isl_die(isl_schedule_node_get_ctx(pos
), isl_error_invalid
,
2830 "grouping cannot only refer to global parameters",
2831 return isl_schedule_tree_free(tree
));
2833 data
->expansion
= isl_union_map_project_out(data
->expansion
,
2834 isl_dim_param
, n1
, n2
- n1
);
2835 space
= isl_union_map_get_space(data
->expansion
);
2837 data
->contraction
= isl_union_pw_multi_aff_align_params(
2838 data
->contraction
, isl_space_copy(space
));
2839 n2
= isl_union_pw_multi_aff_dim(data
->contraction
, isl_dim_param
);
2840 data
->contraction
= isl_union_pw_multi_aff_drop_dims(data
->contraction
,
2841 isl_dim_param
, n1
, n2
- n1
);
2843 data
->domain
= union_set_drop_extra_params(data
->domain
, space
, n1
);
2844 data
->domain_universe
=
2845 union_set_drop_extra_params(data
->domain_universe
, space
, n1
);
2846 data
->group
= union_set_drop_extra_params(data
->group
, space
, n1
);
2847 data
->group_universe
=
2848 union_set_drop_extra_params(data
->group_universe
, space
, n1
);
2850 data
->sched
= isl_multi_aff_align_params(data
->sched
,
2851 isl_space_copy(space
));
2852 n2
= isl_multi_aff_dim(data
->sched
, isl_dim_param
);
2853 data
->sched
= isl_multi_aff_drop_dims(data
->sched
,
2854 isl_dim_param
, n1
, n2
- n1
);
2856 isl_space_free(space
);
2861 /* Update the domain tree root "tree" to refer to the group instances
2862 * in data->group rather than the original domain elements in data->domain.
2863 * "pos" is the position in the original schedule tree where the modified
2864 * "tree" will be attached.
2866 * We first double-check that all grouped domain elements are actually
2867 * part of the root domain and then replace those elements by the group
2870 static __isl_give isl_schedule_tree
*group_domain(
2871 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2872 struct isl_schedule_group_data
*data
)
2874 isl_union_set
*domain
;
2877 domain
= isl_schedule_tree_domain_get_domain(tree
);
2878 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2879 isl_union_set_free(domain
);
2881 return isl_schedule_tree_free(tree
);
2883 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2884 "grouped domain should be part of outer domain",
2885 return isl_schedule_tree_free(tree
));
2886 domain
= isl_schedule_tree_domain_get_domain(tree
);
2887 domain
= isl_union_set_subtract(domain
,
2888 isl_union_set_copy(data
->domain
));
2889 domain
= isl_union_set_union(domain
, isl_union_set_copy(data
->group
));
2890 tree
= isl_schedule_tree_domain_set_domain(tree
, domain
);
2895 /* Update the expansion tree root "tree" to refer to the group instances
2896 * in data->group rather than the original domain elements in data->domain.
2897 * "pos" is the position in the original schedule tree where the modified
2898 * "tree" will be attached.
2900 * Let G_1 -> D_1 be the expansion of "tree" and G_2 -> D_2 the newly
2901 * introduced expansion in a descendant of "tree".
2902 * We first double-check that D_2 is a subset of D_1.
2903 * Then we remove D_2 from the range of G_1 -> D_1 and add the mapping
2904 * G_1 -> D_1 . D_2 -> G_2.
2905 * Simmilarly, we restrict the domain of the contraction to the universe
2906 * of the range of the updated expansion and add G_2 -> D_2 . D_1 -> G_1,
2907 * attempting to remove the domain constraints of this additional part.
2909 static __isl_give isl_schedule_tree
*group_expansion(
2910 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2911 struct isl_schedule_group_data
*data
)
2913 isl_union_set
*domain
;
2914 isl_union_map
*expansion
, *umap
;
2915 isl_union_pw_multi_aff
*contraction
, *upma
;
2918 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2919 domain
= isl_union_map_range(expansion
);
2920 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2921 isl_union_set_free(domain
);
2923 return isl_schedule_tree_free(tree
);
2925 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
2926 "grouped domain should be part "
2927 "of outer expansion domain",
2928 return isl_schedule_tree_free(tree
));
2929 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2930 umap
= isl_union_map_from_union_pw_multi_aff(
2931 isl_union_pw_multi_aff_copy(data
->contraction
));
2932 umap
= isl_union_map_apply_range(expansion
, umap
);
2933 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
2934 expansion
= isl_union_map_subtract_range(expansion
,
2935 isl_union_set_copy(data
->domain
));
2936 expansion
= isl_union_map_union(expansion
, umap
);
2937 umap
= isl_union_map_universe(isl_union_map_copy(expansion
));
2938 domain
= isl_union_map_range(umap
);
2939 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
2940 umap
= isl_union_map_from_union_pw_multi_aff(contraction
);
2941 umap
= isl_union_map_apply_range(isl_union_map_copy(data
->expansion
),
2943 upma
= isl_union_pw_multi_aff_from_union_map(umap
);
2944 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
2945 contraction
= isl_union_pw_multi_aff_intersect_domain(contraction
,
2947 domain
= isl_union_pw_multi_aff_domain(
2948 isl_union_pw_multi_aff_copy(upma
));
2949 upma
= isl_union_pw_multi_aff_gist(upma
, domain
);
2950 contraction
= isl_union_pw_multi_aff_union_add(contraction
, upma
);
2951 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
2952 contraction
, expansion
);
2957 /* Update the tree root "tree" to refer to the group instances
2958 * in data->group rather than the original domain elements in data->domain.
2959 * "pos" is the position in the original schedule tree where the modified
2960 * "tree" will be attached.
2962 * If we have come across a domain or expansion node before (data->finished
2963 * is set), then we no longer need perform any modifications.
2965 * If "tree" is a filter, then we add data->group_universe to the filter.
2966 * We also remove data->domain_universe from the filter if all the domain
2967 * elements in this universe that reach the filter node are part of
2968 * the elements that are being grouped by data->expansion.
2969 * If "tree" is a band, domain or expansion, then it is handled
2970 * in a separate function.
2972 static __isl_give isl_schedule_tree
*group_ancestor(
2973 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2976 struct isl_schedule_group_data
*data
= user
;
2977 isl_union_set
*domain
;
2981 return isl_schedule_tree_free(tree
);
2986 switch (isl_schedule_tree_get_type(tree
)) {
2987 case isl_schedule_node_error
:
2988 return isl_schedule_tree_free(tree
);
2989 case isl_schedule_node_extension
:
2990 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_unsupported
,
2991 "grouping not allowed in extended tree",
2992 return isl_schedule_tree_free(tree
));
2993 case isl_schedule_node_band
:
2994 tree
= group_band(tree
, pos
, data
);
2996 case isl_schedule_node_context
:
2997 tree
= group_context(tree
, pos
, data
);
2999 case isl_schedule_node_domain
:
3000 tree
= group_domain(tree
, pos
, data
);
3003 case isl_schedule_node_filter
:
3004 domain
= isl_schedule_node_get_domain(pos
);
3005 is_covered
= locally_covered_by_domain(domain
, data
);
3006 isl_union_set_free(domain
);
3008 return isl_schedule_tree_free(tree
);
3009 domain
= isl_schedule_tree_filter_get_filter(tree
);
3011 domain
= isl_union_set_subtract(domain
,
3012 isl_union_set_copy(data
->domain_universe
));
3013 domain
= isl_union_set_union(domain
,
3014 isl_union_set_copy(data
->group_universe
));
3015 tree
= isl_schedule_tree_filter_set_filter(tree
, domain
);
3017 case isl_schedule_node_expansion
:
3018 tree
= group_expansion(tree
, pos
, data
);
3021 case isl_schedule_node_leaf
:
3022 case isl_schedule_node_guard
:
3023 case isl_schedule_node_mark
:
3024 case isl_schedule_node_sequence
:
3025 case isl_schedule_node_set
:
3032 /* Group the domain elements that reach "node" into instances
3033 * of a single statement with identifier "group_id".
3034 * In particular, group the domain elements according to their
3037 * That is, introduce an expansion node with as contraction
3038 * the prefix schedule (with the target space replaced by "group_id")
3039 * and as expansion the inverse of this contraction (with its range
3040 * intersected with the domain elements that reach "node").
3041 * The outer nodes are then modified to refer to the group instances
3042 * instead of the original domain elements.
3044 * No instance of "group_id" is allowed to reach "node" prior
3046 * No ancestor of "node" is allowed to be an extension node.
3048 * Return a pointer to original node in tree, i.e., the child
3049 * of the newly introduced expansion node.
3051 __isl_give isl_schedule_node
*isl_schedule_node_group(
3052 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*group_id
)
3054 struct isl_schedule_group_data data
= { 0 };
3056 isl_union_set
*domain
;
3057 isl_union_pw_multi_aff
*contraction
;
3058 isl_union_map
*expansion
;
3061 if (!node
|| !group_id
)
3063 if (check_insert(node
) < 0)
3066 domain
= isl_schedule_node_get_domain(node
);
3067 data
.domain
= isl_union_set_copy(domain
);
3068 data
.domain_universe
= isl_union_set_copy(domain
);
3069 data
.domain_universe
= isl_union_set_universe(data
.domain_universe
);
3071 data
.dim
= isl_schedule_node_get_schedule_depth(node
);
3072 if (data
.dim
== 0) {
3075 isl_union_set
*group
;
3076 isl_union_map
*univ
;
3078 ctx
= isl_schedule_node_get_ctx(node
);
3079 space
= isl_space_set_alloc(ctx
, 0, 0);
3080 space
= isl_space_set_tuple_id(space
, isl_dim_set
, group_id
);
3081 set
= isl_set_universe(isl_space_copy(space
));
3082 group
= isl_union_set_from_set(set
);
3083 expansion
= isl_union_map_from_domain_and_range(domain
, group
);
3084 univ
= isl_union_map_universe(isl_union_map_copy(expansion
));
3085 contraction
= isl_union_pw_multi_aff_from_union_map(univ
);
3086 expansion
= isl_union_map_reverse(expansion
);
3088 isl_multi_union_pw_aff
*prefix
;
3089 isl_union_set
*univ
;
3092 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node
);
3093 prefix
= isl_multi_union_pw_aff_set_tuple_id(prefix
,
3094 isl_dim_set
, group_id
);
3095 space
= isl_multi_union_pw_aff_get_space(prefix
);
3096 contraction
= isl_union_pw_multi_aff_from_multi_union_pw_aff(
3098 univ
= isl_union_set_universe(isl_union_set_copy(domain
));
3100 isl_union_pw_multi_aff_intersect_domain(contraction
, univ
);
3101 expansion
= isl_union_map_from_union_pw_multi_aff(
3102 isl_union_pw_multi_aff_copy(contraction
));
3103 expansion
= isl_union_map_reverse(expansion
);
3104 expansion
= isl_union_map_intersect_range(expansion
, domain
);
3106 space
= isl_space_map_from_set(space
);
3107 data
.sched
= isl_multi_aff_identity(space
);
3108 data
.group
= isl_union_map_domain(isl_union_map_copy(expansion
));
3109 data
.group
= isl_union_set_coalesce(data
.group
);
3110 data
.group_universe
= isl_union_set_copy(data
.group
);
3111 data
.group_universe
= isl_union_set_universe(data
.group_universe
);
3112 data
.expansion
= isl_union_map_copy(expansion
);
3113 data
.contraction
= isl_union_pw_multi_aff_copy(contraction
);
3114 node
= isl_schedule_node_insert_expansion(node
, contraction
, expansion
);
3116 disjoint
= isl_union_set_is_disjoint(data
.domain_universe
,
3117 data
.group_universe
);
3119 node
= update_ancestors(node
, &group_ancestor
, &data
);
3121 isl_union_set_free(data
.domain
);
3122 isl_union_set_free(data
.domain_universe
);
3123 isl_union_set_free(data
.group
);
3124 isl_union_set_free(data
.group_universe
);
3125 isl_multi_aff_free(data
.sched
);
3126 isl_union_map_free(data
.expansion
);
3127 isl_union_pw_multi_aff_free(data
.contraction
);
3129 node
= isl_schedule_node_child(node
, 0);
3131 if (!node
|| disjoint
< 0)
3132 return isl_schedule_node_free(node
);
3134 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3135 "group instances already reach node",
3136 isl_schedule_node_free(node
));
3140 isl_schedule_node_free(node
);
3141 isl_id_free(group_id
);
3145 /* Compute the gist of the given band node with respect to "context".
3147 __isl_give isl_schedule_node
*isl_schedule_node_band_gist(
3148 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3150 isl_schedule_tree
*tree
;
3152 tree
= isl_schedule_node_get_tree(node
);
3153 tree
= isl_schedule_tree_band_gist(tree
, context
);
3154 return isl_schedule_node_graft_tree(node
, tree
);
3157 /* Internal data structure for isl_schedule_node_gist.
3158 * "n_expansion" is the number of outer expansion nodes
3159 * with respect to the current position
3160 * "filters" contains an element for each outer filter, expansion or
3161 * extension node with respect to the current position, each representing
3162 * the intersection of the previous element and the filter on the filter node
3163 * or the expansion/extension of the previous element.
3164 * The first element in the original context passed to isl_schedule_node_gist.
3166 struct isl_node_gist_data
{
3168 isl_union_set_list
*filters
;
3171 /* Enter the expansion node "node" during a isl_schedule_node_gist traversal.
3173 * In particular, add an extra element to data->filters containing
3174 * the expansion of the previous element and replace the expansion
3175 * and contraction on "node" by the gist with respect to these filters.
3176 * Also keep track of the fact that we have entered another expansion.
3178 static __isl_give isl_schedule_node
*gist_enter_expansion(
3179 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3182 isl_union_set
*inner
;
3183 isl_union_map
*expansion
;
3184 isl_union_pw_multi_aff
*contraction
;
3186 data
->n_expansion
++;
3188 n
= isl_union_set_list_n_union_set(data
->filters
);
3189 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3190 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3191 inner
= isl_union_set_apply(inner
, expansion
);
3193 contraction
= isl_schedule_node_expansion_get_contraction(node
);
3194 contraction
= isl_union_pw_multi_aff_gist(contraction
,
3195 isl_union_set_copy(inner
));
3197 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
3199 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3200 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3201 expansion
= isl_union_map_gist_domain(expansion
, inner
);
3202 node
= isl_schedule_node_expansion_set_contraction_and_expansion(node
,
3203 contraction
, expansion
);
3208 /* Leave the expansion node "node" during a isl_schedule_node_gist traversal.
3210 * In particular, remove the element in data->filters that was added by
3211 * gist_enter_expansion and decrement the number of outer expansions.
3213 * The expansion has already been simplified in gist_enter_expansion.
3214 * If this simplification results in an identity expansion, then
3215 * it is removed here.
3217 static __isl_give isl_schedule_node
*gist_leave_expansion(
3218 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3222 isl_union_map
*expansion
;
3224 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3225 identity
= isl_union_map_is_identity(expansion
);
3226 isl_union_map_free(expansion
);
3229 node
= isl_schedule_node_free(node
);
3231 node
= isl_schedule_node_delete(node
);
3233 n
= isl_union_set_list_n_union_set(data
->filters
);
3234 data
->filters
= isl_union_set_list_drop(data
->filters
, n
- 1, 1);
3236 data
->n_expansion
--;
3241 /* Enter the extension node "node" during a isl_schedule_node_gist traversal.
3243 * In particular, add an extra element to data->filters containing
3244 * the union of the previous element with the additional domain elements
3245 * introduced by the extension.
3247 static __isl_give isl_schedule_node
*gist_enter_extension(
3248 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3251 isl_union_set
*inner
, *extra
;
3252 isl_union_map
*extension
;
3254 n
= isl_union_set_list_n_union_set(data
->filters
);
3255 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3256 extension
= isl_schedule_node_extension_get_extension(node
);
3257 extra
= isl_union_map_range(extension
);
3258 inner
= isl_union_set_union(inner
, extra
);
3260 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
3265 /* Can we finish gisting at this node?
3266 * That is, is the filter on the current filter node a subset of
3267 * the original context passed to isl_schedule_node_gist?
3268 * If we have gone through any expansions, then we cannot perform
3269 * this test since the current domain elements are incomparable
3270 * to the domain elements in the original context.
3272 static int gist_done(__isl_keep isl_schedule_node
*node
,
3273 struct isl_node_gist_data
*data
)
3275 isl_union_set
*filter
, *outer
;
3278 if (data
->n_expansion
!= 0)
3281 filter
= isl_schedule_node_filter_get_filter(node
);
3282 outer
= isl_union_set_list_get_union_set(data
->filters
, 0);
3283 subset
= isl_union_set_is_subset(filter
, outer
);
3284 isl_union_set_free(outer
);
3285 isl_union_set_free(filter
);
3290 /* Callback for "traverse" to enter a node and to move
3291 * to the deepest initial subtree that should be traversed
3292 * by isl_schedule_node_gist.
3294 * The "filters" list is extended by one element each time
3295 * we come across a filter node by the result of intersecting
3296 * the last element in the list with the filter on the filter node.
3298 * If the filter on the current filter node is a subset of
3299 * the original context passed to isl_schedule_node_gist,
3300 * then there is no need to go into its subtree since it cannot
3301 * be further simplified by the context. The "filters" list is
3302 * still extended for consistency, but the actual value of the
3303 * added element is immaterial since it will not be used.
3305 * Otherwise, the filter on the current filter node is replaced by
3306 * the gist of the original filter with respect to the intersection
3307 * of the original context with the intermediate filters.
3309 * If the new element in the "filters" list is empty, then no elements
3310 * can reach the descendants of the current filter node. The subtree
3311 * underneath the filter node is therefore removed.
3313 * Each expansion node we come across is handled by
3314 * gist_enter_expansion.
3316 * Each extension node we come across is handled by
3317 * gist_enter_extension.
3319 static __isl_give isl_schedule_node
*gist_enter(
3320 __isl_take isl_schedule_node
*node
, void *user
)
3322 struct isl_node_gist_data
*data
= user
;
3325 isl_union_set
*filter
, *inner
;
3329 switch (isl_schedule_node_get_type(node
)) {
3330 case isl_schedule_node_error
:
3331 return isl_schedule_node_free(node
);
3332 case isl_schedule_node_expansion
:
3333 node
= gist_enter_expansion(node
, data
);
3335 case isl_schedule_node_extension
:
3336 node
= gist_enter_extension(node
, data
);
3338 case isl_schedule_node_band
:
3339 case isl_schedule_node_context
:
3340 case isl_schedule_node_domain
:
3341 case isl_schedule_node_guard
:
3342 case isl_schedule_node_leaf
:
3343 case isl_schedule_node_mark
:
3344 case isl_schedule_node_sequence
:
3345 case isl_schedule_node_set
:
3347 case isl_schedule_node_filter
:
3350 done
= gist_done(node
, data
);
3351 filter
= isl_schedule_node_filter_get_filter(node
);
3352 if (done
< 0 || done
) {
3353 data
->filters
= isl_union_set_list_add(data
->filters
,
3356 return isl_schedule_node_free(node
);
3359 n
= isl_union_set_list_n_union_set(data
->filters
);
3360 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3361 filter
= isl_union_set_gist(filter
, isl_union_set_copy(inner
));
3362 node
= isl_schedule_node_filter_set_filter(node
,
3363 isl_union_set_copy(filter
));
3364 filter
= isl_union_set_intersect(filter
, inner
);
3365 empty
= isl_union_set_is_empty(filter
);
3366 data
->filters
= isl_union_set_list_add(data
->filters
, filter
);
3368 return isl_schedule_node_free(node
);
3371 node
= isl_schedule_node_child(node
, 0);
3372 node
= isl_schedule_node_cut(node
);
3373 node
= isl_schedule_node_parent(node
);
3375 } while (isl_schedule_node_has_children(node
) &&
3376 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3381 /* Callback for "traverse" to leave a node for isl_schedule_node_gist.
3383 * In particular, if the current node is a filter node, then we remove
3384 * the element on the "filters" list that was added when we entered
3385 * the node. There is no need to compute any gist here, since we
3386 * already did that when we entered the node.
3388 * Expansion nodes are handled by gist_leave_expansion.
3390 * If the current node is an extension, then remove the element
3391 * in data->filters that was added by gist_enter_extension.
3393 * If the current node is a band node, then we compute the gist of
3394 * the band node with respect to the intersection of the original context
3395 * and the intermediate filters.
3397 * If the current node is a sequence or set node, then some of
3398 * the filter children may have become empty and so they are removed.
3399 * If only one child is left, then the set or sequence node along with
3400 * the single remaining child filter is removed. The filter can be
3401 * removed because the filters on a sequence or set node are supposed
3402 * to partition the incoming domain instances.
3403 * In principle, it should then be impossible for there to be zero
3404 * remaining children, but should this happen, we replace the entire
3405 * subtree with an empty filter.
3407 static __isl_give isl_schedule_node
*gist_leave(
3408 __isl_take isl_schedule_node
*node
, void *user
)
3410 struct isl_node_gist_data
*data
= user
;
3411 isl_schedule_tree
*tree
;
3413 isl_union_set
*filter
;
3415 switch (isl_schedule_node_get_type(node
)) {
3416 case isl_schedule_node_error
:
3417 return isl_schedule_node_free(node
);
3418 case isl_schedule_node_expansion
:
3419 node
= gist_leave_expansion(node
, data
);
3421 case isl_schedule_node_extension
:
3422 case isl_schedule_node_filter
:
3423 n
= isl_union_set_list_n_union_set(data
->filters
);
3424 data
->filters
= isl_union_set_list_drop(data
->filters
,
3427 case isl_schedule_node_band
:
3428 n
= isl_union_set_list_n_union_set(data
->filters
);
3429 filter
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3430 node
= isl_schedule_node_band_gist(node
, filter
);
3432 case isl_schedule_node_set
:
3433 case isl_schedule_node_sequence
:
3434 tree
= isl_schedule_node_get_tree(node
);
3435 n
= isl_schedule_tree_n_children(tree
);
3436 for (i
= n
- 1; i
>= 0; --i
) {
3437 isl_schedule_tree
*child
;
3438 isl_union_set
*filter
;
3441 child
= isl_schedule_tree_get_child(tree
, i
);
3442 filter
= isl_schedule_tree_filter_get_filter(child
);
3443 empty
= isl_union_set_is_empty(filter
);
3444 isl_union_set_free(filter
);
3445 isl_schedule_tree_free(child
);
3447 tree
= isl_schedule_tree_free(tree
);
3449 tree
= isl_schedule_tree_drop_child(tree
, i
);
3451 n
= isl_schedule_tree_n_children(tree
);
3452 node
= isl_schedule_node_graft_tree(node
, tree
);
3454 node
= isl_schedule_node_delete(node
);
3455 node
= isl_schedule_node_delete(node
);
3456 } else if (n
== 0) {
3460 isl_union_set_list_get_union_set(data
->filters
, 0);
3461 space
= isl_union_set_get_space(filter
);
3462 isl_union_set_free(filter
);
3463 filter
= isl_union_set_empty(space
);
3464 node
= isl_schedule_node_cut(node
);
3465 node
= isl_schedule_node_insert_filter(node
, filter
);
3468 case isl_schedule_node_context
:
3469 case isl_schedule_node_domain
:
3470 case isl_schedule_node_guard
:
3471 case isl_schedule_node_leaf
:
3472 case isl_schedule_node_mark
:
3479 /* Compute the gist of the subtree at "node" with respect to
3480 * the reaching domain elements in "context".
3481 * In particular, compute the gist of all band and filter nodes
3482 * in the subtree with respect to "context". Children of set or sequence
3483 * nodes that end up with an empty filter are removed completely.
3485 * We keep track of the intersection of "context" with all outer filters
3486 * of the current node within the subtree in the final element of "filters".
3487 * Initially, this list contains the single element "context" and it is
3488 * extended or shortened each time we enter or leave a filter node.
3490 __isl_give isl_schedule_node
*isl_schedule_node_gist(
3491 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3493 struct isl_node_gist_data data
;
3495 data
.n_expansion
= 0;
3496 data
.filters
= isl_union_set_list_from_union_set(context
);
3497 node
= traverse(node
, &gist_enter
, &gist_leave
, &data
);
3498 isl_union_set_list_free(data
.filters
);
3502 /* Intersect the domain of domain node "node" with "domain".
3504 * If the domain of "node" is already a subset of "domain",
3505 * then nothing needs to be changed.
3507 * Otherwise, we replace the domain of the domain node by the intersection
3508 * and simplify the subtree rooted at "node" with respect to this intersection.
3510 __isl_give isl_schedule_node
*isl_schedule_node_domain_intersect_domain(
3511 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
)
3513 isl_schedule_tree
*tree
;
3514 isl_union_set
*uset
;
3517 if (!node
|| !domain
)
3520 uset
= isl_schedule_tree_domain_get_domain(node
->tree
);
3521 is_subset
= isl_union_set_is_subset(uset
, domain
);
3522 isl_union_set_free(uset
);
3526 isl_union_set_free(domain
);
3530 tree
= isl_schedule_tree_copy(node
->tree
);
3531 uset
= isl_schedule_tree_domain_get_domain(tree
);
3532 uset
= isl_union_set_intersect(uset
, domain
);
3533 tree
= isl_schedule_tree_domain_set_domain(tree
,
3534 isl_union_set_copy(uset
));
3535 node
= isl_schedule_node_graft_tree(node
, tree
);
3537 node
= isl_schedule_node_child(node
, 0);
3538 node
= isl_schedule_node_gist(node
, uset
);
3539 node
= isl_schedule_node_parent(node
);
3543 isl_schedule_node_free(node
);
3544 isl_union_set_free(domain
);
3548 /* Replace the domain of domain node "node" with the gist
3549 * of the original domain with respect to the parameter domain "context".
3551 __isl_give isl_schedule_node
*isl_schedule_node_domain_gist_params(
3552 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
3554 isl_union_set
*domain
;
3555 isl_schedule_tree
*tree
;
3557 if (!node
|| !context
)
3560 tree
= isl_schedule_tree_copy(node
->tree
);
3561 domain
= isl_schedule_tree_domain_get_domain(node
->tree
);
3562 domain
= isl_union_set_gist_params(domain
, context
);
3563 tree
= isl_schedule_tree_domain_set_domain(tree
, domain
);
3564 node
= isl_schedule_node_graft_tree(node
, tree
);
3568 isl_schedule_node_free(node
);
3569 isl_set_free(context
);
3573 /* Internal data structure for isl_schedule_node_get_subtree_expansion.
3574 * "expansions" contains a list of accumulated expansions
3575 * for each outer expansion, set or sequence node. The first element
3576 * in the list is an identity mapping on the reaching domain elements.
3577 * "res" collects the results.
3579 struct isl_subtree_expansion_data
{
3580 isl_union_map_list
*expansions
;
3584 /* Callback for "traverse" to enter a node and to move
3585 * to the deepest initial subtree that should be traversed
3586 * by isl_schedule_node_get_subtree_expansion.
3588 * Whenever we come across an expansion node, the last element
3589 * of data->expansions is combined with the expansion
3590 * on the expansion node.
3592 * Whenever we come across a filter node that is the child
3593 * of a set or sequence node, data->expansions is extended
3594 * with a new element that restricts the previous element
3595 * to the elements selected by the filter.
3596 * The previous element can then be reused while backtracking.
3598 static __isl_give isl_schedule_node
*subtree_expansion_enter(
3599 __isl_take isl_schedule_node
*node
, void *user
)
3601 struct isl_subtree_expansion_data
*data
= user
;
3604 enum isl_schedule_node_type type
;
3605 isl_union_set
*filter
;
3606 isl_union_map
*inner
, *expansion
;
3609 switch (isl_schedule_node_get_type(node
)) {
3610 case isl_schedule_node_error
:
3611 return isl_schedule_node_free(node
);
3612 case isl_schedule_node_filter
:
3613 type
= isl_schedule_node_get_parent_type(node
);
3614 if (type
!= isl_schedule_node_set
&&
3615 type
!= isl_schedule_node_sequence
)
3617 filter
= isl_schedule_node_filter_get_filter(node
);
3618 n
= isl_union_map_list_n_union_map(data
->expansions
);
3620 isl_union_map_list_get_union_map(data
->expansions
,
3622 inner
= isl_union_map_intersect_range(inner
, filter
);
3624 isl_union_map_list_add(data
->expansions
, inner
);
3626 case isl_schedule_node_expansion
:
3627 n
= isl_union_map_list_n_union_map(data
->expansions
);
3629 isl_schedule_node_expansion_get_expansion(node
);
3631 isl_union_map_list_get_union_map(data
->expansions
,
3633 inner
= isl_union_map_apply_range(inner
, expansion
);
3635 isl_union_map_list_set_union_map(data
->expansions
,
3638 case isl_schedule_node_band
:
3639 case isl_schedule_node_context
:
3640 case isl_schedule_node_domain
:
3641 case isl_schedule_node_extension
:
3642 case isl_schedule_node_guard
:
3643 case isl_schedule_node_leaf
:
3644 case isl_schedule_node_mark
:
3645 case isl_schedule_node_sequence
:
3646 case isl_schedule_node_set
:
3649 } while (isl_schedule_node_has_children(node
) &&
3650 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3655 /* Callback for "traverse" to leave a node for
3656 * isl_schedule_node_get_subtree_expansion.
3658 * If we come across a filter node that is the child
3659 * of a set or sequence node, then we remove the element
3660 * of data->expansions that was added in subtree_expansion_enter.
3662 * If we reach a leaf node, then the accumulated expansion is
3663 * added to data->res.
3665 static __isl_give isl_schedule_node
*subtree_expansion_leave(
3666 __isl_take isl_schedule_node
*node
, void *user
)
3668 struct isl_subtree_expansion_data
*data
= user
;
3670 isl_union_map
*inner
;
3671 enum isl_schedule_node_type type
;
3673 switch (isl_schedule_node_get_type(node
)) {
3674 case isl_schedule_node_error
:
3675 return isl_schedule_node_free(node
);
3676 case isl_schedule_node_filter
:
3677 type
= isl_schedule_node_get_parent_type(node
);
3678 if (type
!= isl_schedule_node_set
&&
3679 type
!= isl_schedule_node_sequence
)
3681 n
= isl_union_map_list_n_union_map(data
->expansions
);
3682 data
->expansions
= isl_union_map_list_drop(data
->expansions
,
3685 case isl_schedule_node_leaf
:
3686 n
= isl_union_map_list_n_union_map(data
->expansions
);
3687 inner
= isl_union_map_list_get_union_map(data
->expansions
,
3689 data
->res
= isl_union_map_union(data
->res
, inner
);
3691 case isl_schedule_node_band
:
3692 case isl_schedule_node_context
:
3693 case isl_schedule_node_domain
:
3694 case isl_schedule_node_expansion
:
3695 case isl_schedule_node_extension
:
3696 case isl_schedule_node_guard
:
3697 case isl_schedule_node_mark
:
3698 case isl_schedule_node_sequence
:
3699 case isl_schedule_node_set
:
3706 /* Return a mapping from the domain elements that reach "node"
3707 * to the corresponding domain elements in the leaves of the subtree
3708 * rooted at "node" obtained by composing the intermediate expansions.
3710 * We start out with an identity mapping between the domain elements
3711 * that reach "node" and compose it with all the expansions
3712 * on a path from "node" to a leaf while traversing the subtree.
3713 * Within the children of an a sequence or set node, the
3714 * accumulated expansion is restricted to the elements selected
3715 * by the filter child.
3717 __isl_give isl_union_map
*isl_schedule_node_get_subtree_expansion(
3718 __isl_keep isl_schedule_node
*node
)
3720 struct isl_subtree_expansion_data data
;
3722 isl_union_set
*domain
;
3723 isl_union_map
*expansion
;
3728 domain
= isl_schedule_node_get_universe_domain(node
);
3729 space
= isl_union_set_get_space(domain
);
3730 expansion
= isl_union_set_identity(domain
);
3731 data
.res
= isl_union_map_empty(space
);
3732 data
.expansions
= isl_union_map_list_from_union_map(expansion
);
3734 node
= isl_schedule_node_copy(node
);
3735 node
= traverse(node
, &subtree_expansion_enter
,
3736 &subtree_expansion_leave
, &data
);
3738 data
.res
= isl_union_map_free(data
.res
);
3739 isl_schedule_node_free(node
);
3741 isl_union_map_list_free(data
.expansions
);
3746 /* Internal data structure for isl_schedule_node_get_subtree_contraction.
3747 * "contractions" contains a list of accumulated contractions
3748 * for each outer expansion, set or sequence node. The first element
3749 * in the list is an identity mapping on the reaching domain elements.
3750 * "res" collects the results.
3752 struct isl_subtree_contraction_data
{
3753 isl_union_pw_multi_aff_list
*contractions
;
3754 isl_union_pw_multi_aff
*res
;
3757 /* Callback for "traverse" to enter a node and to move
3758 * to the deepest initial subtree that should be traversed
3759 * by isl_schedule_node_get_subtree_contraction.
3761 * Whenever we come across an expansion node, the last element
3762 * of data->contractions is combined with the contraction
3763 * on the expansion node.
3765 * Whenever we come across a filter node that is the child
3766 * of a set or sequence node, data->contractions is extended
3767 * with a new element that restricts the previous element
3768 * to the elements selected by the filter.
3769 * The previous element can then be reused while backtracking.
3771 static __isl_give isl_schedule_node
*subtree_contraction_enter(
3772 __isl_take isl_schedule_node
*node
, void *user
)
3774 struct isl_subtree_contraction_data
*data
= user
;
3777 enum isl_schedule_node_type type
;
3778 isl_union_set
*filter
;
3779 isl_union_pw_multi_aff
*inner
, *contraction
;
3782 switch (isl_schedule_node_get_type(node
)) {
3783 case isl_schedule_node_error
:
3784 return isl_schedule_node_free(node
);
3785 case isl_schedule_node_filter
:
3786 type
= isl_schedule_node_get_parent_type(node
);
3787 if (type
!= isl_schedule_node_set
&&
3788 type
!= isl_schedule_node_sequence
)
3790 filter
= isl_schedule_node_filter_get_filter(node
);
3791 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3792 data
->contractions
);
3794 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3795 data
->contractions
, n
- 1);
3796 inner
= isl_union_pw_multi_aff_intersect_domain(inner
,
3798 data
->contractions
=
3799 isl_union_pw_multi_aff_list_add(data
->contractions
,
3802 case isl_schedule_node_expansion
:
3803 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3804 data
->contractions
);
3806 isl_schedule_node_expansion_get_contraction(node
);
3808 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3809 data
->contractions
, n
- 1);
3811 isl_union_pw_multi_aff_pullback_union_pw_multi_aff(
3812 inner
, contraction
);
3813 data
->contractions
=
3814 isl_union_pw_multi_aff_list_set_union_pw_multi_aff(
3815 data
->contractions
, n
- 1, inner
);
3817 case isl_schedule_node_band
:
3818 case isl_schedule_node_context
:
3819 case isl_schedule_node_domain
:
3820 case isl_schedule_node_extension
:
3821 case isl_schedule_node_guard
:
3822 case isl_schedule_node_leaf
:
3823 case isl_schedule_node_mark
:
3824 case isl_schedule_node_sequence
:
3825 case isl_schedule_node_set
:
3828 } while (isl_schedule_node_has_children(node
) &&
3829 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3834 /* Callback for "traverse" to leave a node for
3835 * isl_schedule_node_get_subtree_contraction.
3837 * If we come across a filter node that is the child
3838 * of a set or sequence node, then we remove the element
3839 * of data->contractions that was added in subtree_contraction_enter.
3841 * If we reach a leaf node, then the accumulated contraction is
3842 * added to data->res.
3844 static __isl_give isl_schedule_node
*subtree_contraction_leave(
3845 __isl_take isl_schedule_node
*node
, void *user
)
3847 struct isl_subtree_contraction_data
*data
= user
;
3849 isl_union_pw_multi_aff
*inner
;
3850 enum isl_schedule_node_type type
;
3852 switch (isl_schedule_node_get_type(node
)) {
3853 case isl_schedule_node_error
:
3854 return isl_schedule_node_free(node
);
3855 case isl_schedule_node_filter
:
3856 type
= isl_schedule_node_get_parent_type(node
);
3857 if (type
!= isl_schedule_node_set
&&
3858 type
!= isl_schedule_node_sequence
)
3860 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3861 data
->contractions
);
3862 data
->contractions
=
3863 isl_union_pw_multi_aff_list_drop(data
->contractions
,
3866 case isl_schedule_node_leaf
:
3867 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3868 data
->contractions
);
3869 inner
= isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3870 data
->contractions
, n
- 1);
3871 data
->res
= isl_union_pw_multi_aff_union_add(data
->res
, inner
);
3873 case isl_schedule_node_band
:
3874 case isl_schedule_node_context
:
3875 case isl_schedule_node_domain
:
3876 case isl_schedule_node_expansion
:
3877 case isl_schedule_node_extension
:
3878 case isl_schedule_node_guard
:
3879 case isl_schedule_node_mark
:
3880 case isl_schedule_node_sequence
:
3881 case isl_schedule_node_set
:
3888 /* Return a mapping from the domain elements in the leaves of the subtree
3889 * rooted at "node" to the corresponding domain elements that reach "node"
3890 * obtained by composing the intermediate contractions.
3892 * We start out with an identity mapping between the domain elements
3893 * that reach "node" and compose it with all the contractions
3894 * on a path from "node" to a leaf while traversing the subtree.
3895 * Within the children of an a sequence or set node, the
3896 * accumulated contraction is restricted to the elements selected
3897 * by the filter child.
3899 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_get_subtree_contraction(
3900 __isl_keep isl_schedule_node
*node
)
3902 struct isl_subtree_contraction_data data
;
3904 isl_union_set
*domain
;
3905 isl_union_pw_multi_aff
*contraction
;
3910 domain
= isl_schedule_node_get_universe_domain(node
);
3911 space
= isl_union_set_get_space(domain
);
3912 contraction
= isl_union_set_identity_union_pw_multi_aff(domain
);
3913 data
.res
= isl_union_pw_multi_aff_empty(space
);
3915 isl_union_pw_multi_aff_list_from_union_pw_multi_aff(contraction
);
3917 node
= isl_schedule_node_copy(node
);
3918 node
= traverse(node
, &subtree_contraction_enter
,
3919 &subtree_contraction_leave
, &data
);
3921 data
.res
= isl_union_pw_multi_aff_free(data
.res
);
3922 isl_schedule_node_free(node
);
3924 isl_union_pw_multi_aff_list_free(data
.contractions
);
3929 /* Do the nearest "n" ancestors of "node" have the types given in "types"
3930 * (starting at the parent of "node")?
3932 static int has_ancestors(__isl_keep isl_schedule_node
*node
,
3933 int n
, enum isl_schedule_node_type
*types
)
3940 n_ancestor
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
3944 for (i
= 0; i
< n
; ++i
) {
3945 isl_schedule_tree
*tree
;
3948 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
3949 n_ancestor
- 1 - i
);
3952 correct_type
= isl_schedule_tree_get_type(tree
) == types
[i
];
3953 isl_schedule_tree_free(tree
);
3961 /* Given a node "node" that appears in an extension (i.e., it is the child
3962 * of a filter in a sequence inside an extension node), are the spaces
3963 * of the extension specified by "extension" disjoint from those
3964 * of both the original extension and the domain elements that reach
3965 * that original extension?
3967 static int is_disjoint_extension(__isl_keep isl_schedule_node
*node
,
3968 __isl_keep isl_union_map
*extension
)
3971 isl_union_set
*domain
;
3974 node
= isl_schedule_node_copy(node
);
3975 node
= isl_schedule_node_parent(node
);
3976 node
= isl_schedule_node_parent(node
);
3977 node
= isl_schedule_node_parent(node
);
3978 old
= isl_schedule_node_extension_get_extension(node
);
3979 domain
= isl_schedule_node_get_universe_domain(node
);
3980 isl_schedule_node_free(node
);
3981 old
= isl_union_map_universe(old
);
3982 domain
= isl_union_set_union(domain
, isl_union_map_range(old
));
3983 extension
= isl_union_map_copy(extension
);
3984 extension
= isl_union_map_intersect_range(extension
, domain
);
3985 empty
= isl_union_map_is_empty(extension
);
3986 isl_union_map_free(extension
);
3991 /* Given a node "node" that is governed by an extension node, extend
3992 * that extension node with "extension".
3994 * In particular, "node" is the child of a filter in a sequence that
3995 * is in turn a child of an extension node. Extend that extension node
3998 * Return a pointer to the parent of the original node (i.e., a filter).
4000 static __isl_give isl_schedule_node
*extend_extension(
4001 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
4005 isl_union_map
*node_extension
;
4007 node
= isl_schedule_node_parent(node
);
4008 pos
= isl_schedule_node_get_child_position(node
);
4009 node
= isl_schedule_node_parent(node
);
4010 node
= isl_schedule_node_parent(node
);
4011 node_extension
= isl_schedule_node_extension_get_extension(node
);
4012 disjoint
= isl_union_map_is_disjoint(extension
, node_extension
);
4013 extension
= isl_union_map_union(extension
, node_extension
);
4014 node
= isl_schedule_node_extension_set_extension(node
, extension
);
4015 node
= isl_schedule_node_child(node
, 0);
4016 node
= isl_schedule_node_child(node
, pos
);
4019 return isl_schedule_node_free(node
);
4023 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4024 "extension domain should be disjoint from earlier "
4025 "extensions", return isl_schedule_node_free(node
));
4030 /* Return the universe of "uset" if this universe is disjoint from "ref".
4031 * Otherwise, return "uset".
4033 * Also check if "uset" itself is disjoint from "ref", reporting
4034 * an error if it is not.
4036 static __isl_give isl_union_set
*replace_by_universe_if_disjoint(
4037 __isl_take isl_union_set
*uset
, __isl_keep isl_union_set
*ref
)
4040 isl_union_set
*universe
;
4042 disjoint
= isl_union_set_is_disjoint(uset
, ref
);
4044 return isl_union_set_free(uset
);
4046 isl_die(isl_union_set_get_ctx(uset
), isl_error_invalid
,
4047 "extension domain should be disjoint from "
4048 "current domain", return isl_union_set_free(uset
));
4050 universe
= isl_union_set_universe(isl_union_set_copy(uset
));
4051 disjoint
= isl_union_set_is_disjoint(universe
, ref
);
4052 if (disjoint
>= 0 && disjoint
) {
4053 isl_union_set_free(uset
);
4056 isl_union_set_free(universe
);
4059 return isl_union_set_free(uset
);
4063 /* Insert an extension node on top of "node" with extension "extension".
4064 * In addition, insert a filter that separates node from the extension
4065 * between the extension node and "node".
4066 * Return a pointer to the inserted filter node.
4068 * If "node" already appears in an extension (i.e., if it is the child
4069 * of a filter in a sequence inside an extension node), then extend that
4070 * extension with "extension" instead.
4071 * In this case, a pointer to the original filter node is returned.
4072 * Note that if some of the elements in the new extension live in the
4073 * same space as those of the original extension or the domain elements
4074 * reaching the original extension, then we insert a new extension anyway.
4075 * Otherwise, we would have to adjust the filters in the sequence child
4076 * of the extension to ensure that the elements in the new extension
4079 static __isl_give isl_schedule_node
*insert_extension(
4080 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
4082 enum isl_schedule_node_type ancestors
[] =
4083 { isl_schedule_node_filter
, isl_schedule_node_sequence
,
4084 isl_schedule_node_extension
};
4085 isl_union_set
*domain
;
4086 isl_union_set
*filter
;
4089 in_ext
= has_ancestors(node
, 3, ancestors
);
4095 disjoint
= is_disjoint_extension(node
, extension
);
4099 return extend_extension(node
, extension
);
4102 filter
= isl_schedule_node_get_domain(node
);
4103 domain
= isl_union_map_range(isl_union_map_copy(extension
));
4104 filter
= replace_by_universe_if_disjoint(filter
, domain
);
4105 isl_union_set_free(domain
);
4107 node
= isl_schedule_node_insert_filter(node
, filter
);
4108 node
= isl_schedule_node_insert_extension(node
, extension
);
4109 node
= isl_schedule_node_child(node
, 0);
4112 isl_schedule_node_free(node
);
4113 isl_union_map_free(extension
);
4117 /* Replace the subtree that "node" points to by "tree" (which has
4118 * a sequence root with two children), except if the parent of "node"
4119 * is a sequence as well, in which case "tree" is spliced at the position
4120 * of "node" in its parent.
4121 * Return a pointer to the child of the "tree_pos" (filter) child of "tree"
4122 * in the updated schedule tree.
4124 static __isl_give isl_schedule_node
*graft_or_splice(
4125 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_tree
*tree
,
4130 if (isl_schedule_node_get_parent_type(node
) ==
4131 isl_schedule_node_sequence
) {
4132 pos
= isl_schedule_node_get_child_position(node
);
4133 node
= isl_schedule_node_parent(node
);
4134 node
= isl_schedule_node_sequence_splice(node
, pos
, tree
);
4137 node
= isl_schedule_node_graft_tree(node
, tree
);
4139 node
= isl_schedule_node_child(node
, pos
+ tree_pos
);
4140 node
= isl_schedule_node_child(node
, 0);
4145 /* Insert a node "graft" into the schedule tree of "node" such that it
4146 * is executed before (if "before" is set) or after (if "before" is not set)
4147 * the node that "node" points to.
4148 * The root of "graft" is an extension node.
4149 * Return a pointer to the node that "node" pointed to.
4151 * We first insert an extension node on top of "node" (or extend
4152 * the extension node if there already is one), with a filter on "node"
4153 * separating it from the extension.
4154 * We then insert a filter in the graft to separate it from the original
4155 * domain elements and combine the original and new tree in a sequence.
4156 * If we have extended an extension node, then the children of this
4157 * sequence are spliced in the sequence of the extended extension
4158 * at the position where "node" appears in the original extension.
4159 * Otherwise, the sequence pair is attached to the new extension node.
4161 static __isl_give isl_schedule_node
*graft_extension(
4162 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
,
4165 isl_union_map
*extension
;
4166 isl_union_set
*graft_domain
;
4167 isl_union_set
*node_domain
;
4168 isl_schedule_tree
*tree
, *tree_graft
;
4170 extension
= isl_schedule_node_extension_get_extension(graft
);
4171 graft_domain
= isl_union_map_range(isl_union_map_copy(extension
));
4172 node_domain
= isl_schedule_node_get_universe_domain(node
);
4173 node
= insert_extension(node
, extension
);
4175 graft_domain
= replace_by_universe_if_disjoint(graft_domain
,
4177 isl_union_set_free(node_domain
);
4179 tree
= isl_schedule_node_get_tree(node
);
4180 if (!isl_schedule_node_has_children(graft
)) {
4181 tree_graft
= isl_schedule_tree_from_filter(graft_domain
);
4183 graft
= isl_schedule_node_child(graft
, 0);
4184 tree_graft
= isl_schedule_node_get_tree(graft
);
4185 tree_graft
= isl_schedule_tree_insert_filter(tree_graft
,
4189 tree
= isl_schedule_tree_sequence_pair(tree_graft
, tree
);
4191 tree
= isl_schedule_tree_sequence_pair(tree
, tree_graft
);
4192 node
= graft_or_splice(node
, tree
, before
);
4194 isl_schedule_node_free(graft
);
4199 /* Replace the root domain node of "node" by an extension node suitable
4200 * for insertion at "pos".
4201 * That is, create an extension node that maps the outer band nodes
4202 * at "pos" to the domain of the root node of "node" and attach
4203 * the child of this root node to the extension node.
4205 static __isl_give isl_schedule_node
*extension_from_domain(
4206 __isl_take isl_schedule_node
*node
, __isl_keep isl_schedule_node
*pos
)
4208 isl_union_set
*universe
;
4209 isl_union_set
*domain
;
4214 isl_schedule_node
*res
;
4215 isl_schedule_tree
*tree
;
4217 anchored
= isl_schedule_node_is_subtree_anchored(node
);
4219 return isl_schedule_node_free(node
);
4221 isl_die(isl_schedule_node_get_ctx(node
), isl_error_unsupported
,
4222 "cannot graft anchored tree with domain root",
4223 return isl_schedule_node_free(node
));
4225 depth
= isl_schedule_node_get_schedule_depth(pos
);
4226 domain
= isl_schedule_node_domain_get_domain(node
);
4227 space
= isl_union_set_get_space(domain
);
4228 space
= isl_space_set_from_params(space
);
4229 space
= isl_space_add_dims(space
, isl_dim_set
, depth
);
4230 universe
= isl_union_set_from_set(isl_set_universe(space
));
4231 ext
= isl_union_map_from_domain_and_range(universe
, domain
);
4232 res
= isl_schedule_node_from_extension(ext
);
4233 node
= isl_schedule_node_child(node
, 0);
4235 return isl_schedule_node_free(res
);
4236 if (!isl_schedule_tree_is_leaf(node
->tree
)) {
4237 tree
= isl_schedule_node_get_tree(node
);
4238 res
= isl_schedule_node_child(res
, 0);
4239 res
= isl_schedule_node_graft_tree(res
, tree
);
4240 res
= isl_schedule_node_parent(res
);
4242 isl_schedule_node_free(node
);
4247 /* Insert a node "graft" into the schedule tree of "node" such that it
4248 * is executed before (if "before" is set) or after (if "before" is not set)
4249 * the node that "node" points to.
4250 * The root of "graft" may be either a domain or an extension node.
4251 * In the latter case, the domain of the extension needs to correspond
4252 * to the outer band nodes of "node".
4253 * The elements of the domain or the range of the extension may not
4254 * intersect with the domain elements that reach "node".
4255 * The schedule tree of "graft" may not be anchored.
4257 * The schedule tree of "node" is modified to include an extension node
4258 * corresponding to the root node of "graft" as a child of the original
4259 * parent of "node". The original node that "node" points to and the
4260 * child of the root node of "graft" are attached to this extension node
4261 * through a sequence, with appropriate filters and with the child
4262 * of "graft" appearing before or after the original "node".
4264 * If "node" already appears inside a sequence that is the child of
4265 * an extension node and if the spaces of the new domain elements
4266 * do not overlap with those of the original domain elements,
4267 * then that extension node is extended with the new extension
4268 * rather than introducing a new segment of extension and sequence nodes.
4270 * Return a pointer to the same node in the modified tree that
4271 * "node" pointed to in the original tree.
4273 static __isl_give isl_schedule_node
*isl_schedule_node_graft_before_or_after(
4274 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
,
4277 if (!node
|| !graft
)
4279 if (check_insert(node
) < 0)
4282 if (isl_schedule_node_get_type(graft
) == isl_schedule_node_domain
)
4283 graft
= extension_from_domain(graft
, node
);
4285 if (isl_schedule_node_get_type(graft
) != isl_schedule_node_extension
)
4286 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4287 "expecting domain or extension as root of graft",
4290 return graft_extension(node
, graft
, before
);
4292 isl_schedule_node_free(node
);
4293 isl_schedule_node_free(graft
);
4297 /* Insert a node "graft" into the schedule tree of "node" such that it
4298 * is executed before the node that "node" points to.
4299 * The root of "graft" may be either a domain or an extension node.
4300 * In the latter case, the domain of the extension needs to correspond
4301 * to the outer band nodes of "node".
4302 * The elements of the domain or the range of the extension may not
4303 * intersect with the domain elements that reach "node".
4304 * The schedule tree of "graft" may not be anchored.
4306 * Return a pointer to the same node in the modified tree that
4307 * "node" pointed to in the original tree.
4309 __isl_give isl_schedule_node
*isl_schedule_node_graft_before(
4310 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
)
4312 return isl_schedule_node_graft_before_or_after(node
, graft
, 1);
4315 /* Insert a node "graft" into the schedule tree of "node" such that it
4316 * is executed after the node that "node" points to.
4317 * The root of "graft" may be either a domain or an extension node.
4318 * In the latter case, the domain of the extension needs to correspond
4319 * to the outer band nodes of "node".
4320 * The elements of the domain or the range of the extension may not
4321 * intersect with the domain elements that reach "node".
4322 * The schedule tree of "graft" may not be anchored.
4324 * Return a pointer to the same node in the modified tree that
4325 * "node" pointed to in the original tree.
4327 __isl_give isl_schedule_node
*isl_schedule_node_graft_after(
4328 __isl_take isl_schedule_node
*node
,
4329 __isl_take isl_schedule_node
*graft
)
4331 return isl_schedule_node_graft_before_or_after(node
, graft
, 0);
4334 /* Split the domain elements that reach "node" into those that satisfy
4335 * "filter" and those that do not. Arrange for the first subset to be
4336 * executed before or after the second subset, depending on the value
4338 * Return a pointer to the tree corresponding to the second subset,
4339 * except when this subset is empty in which case the original pointer
4341 * If both subsets are non-empty, then a sequence node is introduced
4342 * to impose the order. If the grandparent of the original node was
4343 * itself a sequence, then the original child is replaced by two children
4344 * in this sequence instead.
4345 * The children in the sequence are copies of the original subtree,
4346 * simplified with respect to their filters.
4348 static __isl_give isl_schedule_node
*isl_schedule_node_order_before_or_after(
4349 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
,
4352 enum isl_schedule_node_type ancestors
[] =
4353 { isl_schedule_node_filter
, isl_schedule_node_sequence
};
4354 isl_union_set
*node_domain
, *node_filter
= NULL
, *parent_filter
;
4355 isl_schedule_node
*node2
;
4356 isl_schedule_tree
*tree1
, *tree2
;
4360 if (!node
|| !filter
)
4362 if (check_insert(node
) < 0)
4365 in_seq
= has_ancestors(node
, 2, ancestors
);
4368 node_domain
= isl_schedule_node_get_domain(node
);
4369 filter
= isl_union_set_gist(filter
, isl_union_set_copy(node_domain
));
4370 node_filter
= isl_union_set_copy(node_domain
);
4371 node_filter
= isl_union_set_subtract(node_filter
,
4372 isl_union_set_copy(filter
));
4373 node_filter
= isl_union_set_gist(node_filter
, node_domain
);
4374 empty1
= isl_union_set_is_empty(filter
);
4375 empty2
= isl_union_set_is_empty(node_filter
);
4376 if (empty1
< 0 || empty2
< 0)
4378 if (empty1
|| empty2
) {
4379 isl_union_set_free(filter
);
4380 isl_union_set_free(node_filter
);
4385 node
= isl_schedule_node_parent(node
);
4386 parent_filter
= isl_schedule_node_filter_get_filter(node
);
4387 node_filter
= isl_union_set_intersect(node_filter
,
4388 isl_union_set_copy(parent_filter
));
4389 filter
= isl_union_set_intersect(filter
, parent_filter
);
4392 node2
= isl_schedule_node_copy(node
);
4393 node
= isl_schedule_node_gist(node
, isl_union_set_copy(node_filter
));
4394 node2
= isl_schedule_node_gist(node2
, isl_union_set_copy(filter
));
4395 tree1
= isl_schedule_node_get_tree(node
);
4396 tree2
= isl_schedule_node_get_tree(node2
);
4397 tree1
= isl_schedule_tree_insert_filter(tree1
, node_filter
);
4398 tree2
= isl_schedule_tree_insert_filter(tree2
, filter
);
4399 isl_schedule_node_free(node2
);
4402 tree1
= isl_schedule_tree_sequence_pair(tree2
, tree1
);
4403 node
= graft_or_splice(node
, tree1
, 1);
4405 tree1
= isl_schedule_tree_sequence_pair(tree1
, tree2
);
4406 node
= graft_or_splice(node
, tree1
, 0);
4411 isl_schedule_node_free(node
);
4412 isl_union_set_free(filter
);
4413 isl_union_set_free(node_filter
);
4417 /* Split the domain elements that reach "node" into those that satisfy
4418 * "filter" and those that do not. Arrange for the first subset to be
4419 * executed before the second subset.
4420 * Return a pointer to the tree corresponding to the second subset,
4421 * except when this subset is empty in which case the original pointer
4424 __isl_give isl_schedule_node
*isl_schedule_node_order_before(
4425 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
4427 return isl_schedule_node_order_before_or_after(node
, filter
, 1);
4430 /* Split the domain elements that reach "node" into those that satisfy
4431 * "filter" and those that do not. Arrange for the first subset to be
4432 * executed after the second subset.
4433 * Return a pointer to the tree corresponding to the second subset,
4434 * except when this subset is empty in which case the original pointer
4437 __isl_give isl_schedule_node
*isl_schedule_node_order_after(
4438 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
4440 return isl_schedule_node_order_before_or_after(node
, filter
, 0);
4443 /* Reset the user pointer on all identifiers of parameters and tuples
4444 * in the schedule node "node".
4446 __isl_give isl_schedule_node
*isl_schedule_node_reset_user(
4447 __isl_take isl_schedule_node
*node
)
4449 isl_schedule_tree
*tree
;
4451 tree
= isl_schedule_node_get_tree(node
);
4452 tree
= isl_schedule_tree_reset_user(tree
);
4453 node
= isl_schedule_node_graft_tree(node
, tree
);
4458 /* Align the parameters of the schedule node "node" to those of "space".
4460 __isl_give isl_schedule_node
*isl_schedule_node_align_params(
4461 __isl_take isl_schedule_node
*node
, __isl_take isl_space
*space
)
4463 isl_schedule_tree
*tree
;
4465 tree
= isl_schedule_node_get_tree(node
);
4466 tree
= isl_schedule_tree_align_params(tree
, space
);
4467 node
= isl_schedule_node_graft_tree(node
, tree
);
4472 /* Compute the pullback of schedule node "node"
4473 * by the function represented by "upma".
4474 * In other words, plug in "upma" in the iteration domains
4475 * of schedule node "node".
4476 * We currently do not handle expansion nodes.
4478 * Note that this is only a helper function for
4479 * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency,
4480 * this function should not be called on a single node without also
4481 * calling it on all the other nodes.
4483 __isl_give isl_schedule_node
*isl_schedule_node_pullback_union_pw_multi_aff(
4484 __isl_take isl_schedule_node
*node
,
4485 __isl_take isl_union_pw_multi_aff
*upma
)
4487 isl_schedule_tree
*tree
;
4489 tree
= isl_schedule_node_get_tree(node
);
4490 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, upma
);
4491 node
= isl_schedule_node_graft_tree(node
, tree
);
4496 /* Internal data structure for isl_schedule_node_expand.
4497 * "tree" is the tree that needs to be plugged in in all the leaves.
4498 * "domain" is the set of domain elements in the original leaves
4499 * to which the tree applies.
4501 struct isl_schedule_expand_data
{
4502 isl_schedule_tree
*tree
;
4503 isl_union_set
*domain
;
4506 /* If "node" is a leaf, then plug in data->tree, simplifying it
4507 * within its new context.
4509 * If there are any domain elements at the leaf where the tree
4510 * should not be plugged in (i.e., there are elements not in data->domain)
4511 * then first extend the tree to only apply to the elements in data->domain
4512 * by constructing a set node that selects data->tree for elements
4513 * in data->domain and a leaf for the other elements.
4515 static __isl_give isl_schedule_node
*expand(__isl_take isl_schedule_node
*node
,
4518 struct isl_schedule_expand_data
*data
= user
;
4519 isl_schedule_tree
*tree
, *leaf
;
4520 isl_union_set
*domain
, *left
;
4523 if (isl_schedule_node_get_type(node
) != isl_schedule_node_leaf
)
4526 domain
= isl_schedule_node_get_domain(node
);
4527 tree
= isl_schedule_tree_copy(data
->tree
);
4529 left
= isl_union_set_copy(domain
);
4530 left
= isl_union_set_subtract(left
, isl_union_set_copy(data
->domain
));
4531 empty
= isl_union_set_is_empty(left
);
4532 if (empty
>= 0 && !empty
) {
4533 leaf
= isl_schedule_node_get_leaf(node
);
4534 leaf
= isl_schedule_tree_insert_filter(leaf
, left
);
4535 left
= isl_union_set_copy(data
->domain
);
4536 tree
= isl_schedule_tree_insert_filter(tree
, left
);
4537 tree
= isl_schedule_tree_set_pair(tree
, leaf
);
4540 node
= isl_schedule_node_free(node
);
4541 isl_union_set_free(left
);
4544 node
= isl_schedule_node_graft_tree(node
, tree
);
4545 node
= isl_schedule_node_gist(node
, domain
);
4550 /* Expand the tree rooted at "node" by extending all leaves
4551 * with an expansion node with as child "tree".
4552 * The expansion is determined by "contraction" and "domain".
4553 * That is, the elements of "domain" are contracted according
4554 * to "contraction". The expansion relation is then the inverse
4555 * of "contraction" with its range intersected with "domain".
4557 * Insert the appropriate expansion node on top of "tree" and
4558 * then plug in the result in all leaves of "node".
4560 __isl_give isl_schedule_node
*isl_schedule_node_expand(
4561 __isl_take isl_schedule_node
*node
,
4562 __isl_take isl_union_pw_multi_aff
*contraction
,
4563 __isl_take isl_union_set
*domain
,
4564 __isl_take isl_schedule_tree
*tree
)
4566 struct isl_schedule_expand_data data
;
4567 isl_union_map
*expansion
;
4568 isl_union_pw_multi_aff
*copy
;
4570 if (!node
|| !contraction
|| !tree
)
4571 node
= isl_schedule_node_free(node
);
4573 copy
= isl_union_pw_multi_aff_copy(contraction
);
4574 expansion
= isl_union_map_from_union_pw_multi_aff(copy
);
4575 expansion
= isl_union_map_reverse(expansion
);
4576 expansion
= isl_union_map_intersect_range(expansion
, domain
);
4577 data
.domain
= isl_union_map_domain(isl_union_map_copy(expansion
));
4579 tree
= isl_schedule_tree_insert_expansion(tree
, contraction
, expansion
);
4582 node
= isl_schedule_node_map_descendant_bottom_up(node
, &expand
, &data
);
4583 isl_union_set_free(data
.domain
);
4584 isl_schedule_tree_free(data
.tree
);
4588 /* Return the position of the subtree containing "node" among the children
4589 * of "ancestor". "node" is assumed to be a descendant of "ancestor".
4590 * In particular, both nodes should point to the same schedule tree.
4592 * Return -1 on error.
4594 int isl_schedule_node_get_ancestor_child_position(
4595 __isl_keep isl_schedule_node
*node
,
4596 __isl_keep isl_schedule_node
*ancestor
)
4599 isl_schedule_tree
*tree
;
4601 if (!node
|| !ancestor
)
4604 if (node
->schedule
!= ancestor
->schedule
)
4605 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4606 "not a descendant", return -1);
4608 n1
= isl_schedule_node_get_tree_depth(ancestor
);
4609 n2
= isl_schedule_node_get_tree_depth(node
);
4612 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4613 "not a descendant", return -1);
4614 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n1
);
4615 isl_schedule_tree_free(tree
);
4616 if (tree
!= ancestor
->tree
)
4617 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4618 "not a descendant", return -1);
4620 return node
->child_pos
[n1
];
4623 /* Given two nodes that point to the same schedule tree, return their
4624 * closest shared ancestor.
4626 * Since the two nodes point to the same schedule, they share at least
4627 * one ancestor, the root of the schedule. We move down from the root
4628 * to the first ancestor where the respective children have a different
4629 * child position. This is the requested ancestor.
4630 * If there is no ancestor where the children have a different position,
4631 * then one node is an ancestor of the other and then this node is
4632 * the requested ancestor.
4634 __isl_give isl_schedule_node
*isl_schedule_node_get_shared_ancestor(
4635 __isl_keep isl_schedule_node
*node1
,
4636 __isl_keep isl_schedule_node
*node2
)
4640 if (!node1
|| !node2
)
4642 if (node1
->schedule
!= node2
->schedule
)
4643 isl_die(isl_schedule_node_get_ctx(node1
), isl_error_invalid
,
4644 "not part of same schedule", return NULL
);
4645 n1
= isl_schedule_node_get_tree_depth(node1
);
4646 n2
= isl_schedule_node_get_tree_depth(node2
);
4648 return isl_schedule_node_get_shared_ancestor(node2
, node1
);
4650 return isl_schedule_node_copy(node1
);
4651 if (isl_schedule_node_is_equal(node1
, node2
))
4652 return isl_schedule_node_copy(node1
);
4654 for (i
= 0; i
< n1
; ++i
)
4655 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
4658 node1
= isl_schedule_node_copy(node1
);
4659 return isl_schedule_node_ancestor(node1
, n1
- i
);
4662 /* Print "node" to "p".
4664 __isl_give isl_printer
*isl_printer_print_schedule_node(
4665 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
4668 return isl_printer_free(p
);
4669 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
,
4670 isl_schedule_tree_list_n_schedule_tree(node
->ancestors
),
4674 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
4677 isl_printer
*printer
;
4682 ctx
= isl_schedule_node_get_ctx(node
);
4683 printer
= isl_printer_to_file(ctx
, stderr
);
4684 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
4685 printer
= isl_printer_print_schedule_node(printer
, node
);
4687 isl_printer_free(printer
);
4690 /* Return a string representation of "node".
4691 * Print the schedule node in block format as it would otherwise
4692 * look identical to the entire schedule.
4694 __isl_give
char *isl_schedule_node_to_str(__isl_keep isl_schedule_node
*node
)
4696 isl_printer
*printer
;
4702 printer
= isl_printer_to_str(isl_schedule_node_get_ctx(node
));
4703 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
4704 printer
= isl_printer_print_schedule_node(printer
, node
);
4705 s
= isl_printer_get_str(printer
);
4706 isl_printer_free(printer
);