2 * Copyright 2013-2014 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
4 * Copyright 2016 Sven Verdoolaege
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege,
9 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
10 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
11 * B.P. 105 - 78153 Le Chesnay, France
16 #include <isl/space.h>
18 #include <isl_schedule_band.h>
19 #include <isl_schedule_private.h>
20 #include <isl_schedule_node_private.h>
22 /* Create a new schedule node in the given schedule, point at the given
23 * tree with given ancestors and child positions.
24 * "child_pos" may be NULL if there are no ancestors.
26 __isl_give isl_schedule_node
*isl_schedule_node_alloc(
27 __isl_take isl_schedule
*schedule
, __isl_take isl_schedule_tree
*tree
,
28 __isl_take isl_schedule_tree_list
*ancestors
, int *child_pos
)
31 isl_schedule_node
*node
;
35 n
= isl_schedule_tree_list_n_schedule_tree(ancestors
);
36 if (!schedule
|| !tree
|| n
< 0)
38 if (n
> 0 && !child_pos
)
40 ctx
= isl_schedule_get_ctx(schedule
);
41 node
= isl_calloc_type(ctx
, isl_schedule_node
);
45 node
->schedule
= schedule
;
47 node
->ancestors
= ancestors
;
48 node
->child_pos
= isl_alloc_array(ctx
, int, n
);
49 if (n
&& !node
->child_pos
)
50 return isl_schedule_node_free(node
);
51 for (i
= 0; i
< n
; ++i
)
52 node
->child_pos
[i
] = child_pos
[i
];
56 isl_schedule_free(schedule
);
57 isl_schedule_tree_free(tree
);
58 isl_schedule_tree_list_free(ancestors
);
62 /* Return a pointer to the root of a schedule tree with as single
63 * node a domain node with the given domain.
65 __isl_give isl_schedule_node
*isl_schedule_node_from_domain(
66 __isl_take isl_union_set
*domain
)
68 isl_schedule
*schedule
;
69 isl_schedule_node
*node
;
71 schedule
= isl_schedule_from_domain(domain
);
72 node
= isl_schedule_get_root(schedule
);
73 isl_schedule_free(schedule
);
78 /* Return a pointer to the root of a schedule tree with as single
79 * node a extension node with the given extension.
81 __isl_give isl_schedule_node
*isl_schedule_node_from_extension(
82 __isl_take isl_union_map
*extension
)
85 isl_schedule
*schedule
;
86 isl_schedule_tree
*tree
;
87 isl_schedule_node
*node
;
92 ctx
= isl_union_map_get_ctx(extension
);
93 tree
= isl_schedule_tree_from_extension(extension
);
94 schedule
= isl_schedule_from_schedule_tree(ctx
, tree
);
95 node
= isl_schedule_get_root(schedule
);
96 isl_schedule_free(schedule
);
101 /* Return the isl_ctx to which "node" belongs.
103 isl_ctx
*isl_schedule_node_get_ctx(__isl_keep isl_schedule_node
*node
)
105 return node
? isl_schedule_get_ctx(node
->schedule
) : NULL
;
108 /* Return a pointer to the leaf of the schedule into which "node" points.
110 __isl_keep isl_schedule_tree
*isl_schedule_node_peek_leaf(
111 __isl_keep isl_schedule_node
*node
)
113 return node
? isl_schedule_peek_leaf(node
->schedule
) : NULL
;
116 /* Return a copy of the leaf of the schedule into which "node" points.
118 __isl_give isl_schedule_tree
*isl_schedule_node_get_leaf(
119 __isl_keep isl_schedule_node
*node
)
121 return isl_schedule_tree_copy(isl_schedule_node_peek_leaf(node
));
124 /* Return the type of the node or isl_schedule_node_error on error.
126 enum isl_schedule_node_type
isl_schedule_node_get_type(
127 __isl_keep isl_schedule_node
*node
)
129 return node
? isl_schedule_tree_get_type(node
->tree
)
130 : isl_schedule_node_error
;
133 /* Return the type of the parent of "node" or isl_schedule_node_error on error.
135 enum isl_schedule_node_type
isl_schedule_node_get_parent_type(
136 __isl_keep isl_schedule_node
*node
)
141 isl_schedule_tree
*parent
;
142 enum isl_schedule_node_type type
;
145 return isl_schedule_node_error
;
146 has_parent
= isl_schedule_node_has_parent(node
);
148 return isl_schedule_node_error
;
150 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
151 "node has no parent", return isl_schedule_node_error
);
152 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
154 return isl_schedule_node_error
;
157 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, pos
);
158 type
= isl_schedule_tree_get_type(parent
);
159 isl_schedule_tree_free(parent
);
164 /* Return a copy of the subtree that this node points to.
166 __isl_give isl_schedule_tree
*isl_schedule_node_get_tree(
167 __isl_keep isl_schedule_node
*node
)
172 return isl_schedule_tree_copy(node
->tree
);
175 /* Return a copy of the schedule into which "node" points.
177 __isl_give isl_schedule
*isl_schedule_node_get_schedule(
178 __isl_keep isl_schedule_node
*node
)
182 return isl_schedule_copy(node
->schedule
);
185 /* Return a fresh copy of "node".
187 __isl_take isl_schedule_node
*isl_schedule_node_dup(
188 __isl_keep isl_schedule_node
*node
)
193 return isl_schedule_node_alloc(isl_schedule_copy(node
->schedule
),
194 isl_schedule_tree_copy(node
->tree
),
195 isl_schedule_tree_list_copy(node
->ancestors
),
199 /* Return an isl_schedule_node that is equal to "node" and that has only
200 * a single reference.
202 __isl_give isl_schedule_node
*isl_schedule_node_cow(
203 __isl_take isl_schedule_node
*node
)
211 return isl_schedule_node_dup(node
);
214 /* Return a new reference to "node".
216 __isl_give isl_schedule_node
*isl_schedule_node_copy(
217 __isl_keep isl_schedule_node
*node
)
226 /* Free "node" and return NULL.
228 __isl_null isl_schedule_node
*isl_schedule_node_free(
229 __isl_take isl_schedule_node
*node
)
236 isl_schedule_tree_list_free(node
->ancestors
);
237 free(node
->child_pos
);
238 isl_schedule_tree_free(node
->tree
);
239 isl_schedule_free(node
->schedule
);
245 /* Do "node1" and "node2" point to the same position in the same
248 isl_bool
isl_schedule_node_is_equal(__isl_keep isl_schedule_node
*node1
,
249 __isl_keep isl_schedule_node
*node2
)
254 if (!node1
|| !node2
)
255 return isl_bool_error
;
257 return isl_bool_true
;
258 if (node1
->schedule
!= node2
->schedule
)
259 return isl_bool_false
;
261 n1
= isl_schedule_node_get_tree_depth(node1
);
262 n2
= isl_schedule_node_get_tree_depth(node2
);
263 if (n1
< 0 || n2
< 0)
264 return isl_bool_error
;
266 return isl_bool_false
;
267 for (i
= 0; i
< n1
; ++i
)
268 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
269 return isl_bool_false
;
271 return isl_bool_true
;
274 /* Return the number of outer schedule dimensions of "node"
275 * in its schedule tree.
277 * Return -1 on error.
279 int isl_schedule_node_get_schedule_depth(__isl_keep isl_schedule_node
*node
)
288 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
291 for (i
= n
- 1; i
>= 0; --i
) {
292 isl_schedule_tree
*tree
;
294 tree
= isl_schedule_tree_list_get_schedule_tree(
298 if (tree
->type
== isl_schedule_node_band
)
299 depth
+= isl_schedule_tree_band_n_member(tree
);
300 isl_schedule_tree_free(tree
);
306 /* Internal data structure for
307 * isl_schedule_node_get_prefix_schedule_union_pw_multi_aff
309 * "initialized" is set if the filter field has been initialized.
310 * If "universe_domain" is not set, then the collected filter is intersected
311 * with the domain of the root domain node.
312 * "universe_filter" is set if we are only collecting the universes of filters
313 * "collect_prefix" is set if we are collecting prefixes.
314 * "filter" collects all outer filters and is NULL until "initialized" is set.
315 * "prefix" collects all outer band partial schedules (if "collect_prefix"
316 * is set). If it is used, then it is initialized by the caller
317 * of collect_filter_prefix to a zero-dimensional function.
319 struct isl_schedule_node_get_filter_prefix_data
{
324 isl_union_set
*filter
;
325 isl_multi_union_pw_aff
*prefix
;
328 static isl_stat
collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
329 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
);
331 /* Update the filter and prefix information in "data" based on the first "n"
332 * elements in "list" and the expansion tree root "tree".
334 * We first collect the information from the elements in "list",
335 * initializing the filter based on the domain of the expansion.
336 * Then we map the results to the expanded space and combined them
337 * with the results already in "data".
339 static isl_stat
collect_filter_prefix_expansion(
340 __isl_take isl_schedule_tree
*tree
,
341 __isl_keep isl_schedule_tree_list
*list
, int n
,
342 struct isl_schedule_node_get_filter_prefix_data
*data
)
344 struct isl_schedule_node_get_filter_prefix_data contracted
;
345 isl_union_pw_multi_aff
*c
;
346 isl_union_map
*exp
, *universe
;
347 isl_union_set
*filter
;
349 c
= isl_schedule_tree_expansion_get_contraction(tree
);
350 exp
= isl_schedule_tree_expansion_get_expansion(tree
);
352 contracted
.initialized
= 1;
353 contracted
.universe_domain
= data
->universe_domain
;
354 contracted
.universe_filter
= data
->universe_filter
;
355 contracted
.collect_prefix
= data
->collect_prefix
;
356 universe
= isl_union_map_universe(isl_union_map_copy(exp
));
357 filter
= isl_union_map_domain(universe
);
358 if (data
->collect_prefix
) {
359 isl_space
*space
= isl_union_set_get_space(filter
);
360 space
= isl_space_set_from_params(space
);
361 contracted
.prefix
= isl_multi_union_pw_aff_zero(space
);
363 contracted
.filter
= filter
;
365 if (collect_filter_prefix(list
, n
, &contracted
) < 0)
366 contracted
.filter
= isl_union_set_free(contracted
.filter
);
367 if (data
->collect_prefix
) {
368 isl_multi_union_pw_aff
*prefix
;
370 prefix
= contracted
.prefix
;
372 isl_multi_union_pw_aff_pullback_union_pw_multi_aff(prefix
,
373 isl_union_pw_multi_aff_copy(c
));
374 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(
375 prefix
, data
->prefix
);
377 filter
= contracted
.filter
;
378 if (data
->universe_domain
)
379 filter
= isl_union_set_preimage_union_pw_multi_aff(filter
,
380 isl_union_pw_multi_aff_copy(c
));
382 filter
= isl_union_set_apply(filter
, isl_union_map_copy(exp
));
383 if (!data
->initialized
)
384 data
->filter
= filter
;
386 data
->filter
= isl_union_set_intersect(filter
, data
->filter
);
387 data
->initialized
= 1;
389 isl_union_pw_multi_aff_free(c
);
390 isl_union_map_free(exp
);
391 isl_schedule_tree_free(tree
);
396 /* Update the filter information in "data" based on the first "n"
397 * elements in "list" and the extension tree root "tree", in case
398 * data->universe_domain is set and data->collect_prefix is not.
400 * We collect the universe domain of the elements in "list" and
401 * add it to the universe range of the extension (intersected
402 * with the already collected filter, if any).
404 static isl_stat
collect_universe_domain_extension(
405 __isl_take isl_schedule_tree
*tree
,
406 __isl_keep isl_schedule_tree_list
*list
, int n
,
407 struct isl_schedule_node_get_filter_prefix_data
*data
)
409 struct isl_schedule_node_get_filter_prefix_data data_outer
;
410 isl_union_map
*extension
;
411 isl_union_set
*filter
;
413 data_outer
.initialized
= 0;
414 data_outer
.universe_domain
= 1;
415 data_outer
.universe_filter
= data
->universe_filter
;
416 data_outer
.collect_prefix
= 0;
417 data_outer
.filter
= NULL
;
418 data_outer
.prefix
= NULL
;
420 if (collect_filter_prefix(list
, n
, &data_outer
) < 0)
421 data_outer
.filter
= isl_union_set_free(data_outer
.filter
);
423 extension
= isl_schedule_tree_extension_get_extension(tree
);
424 extension
= isl_union_map_universe(extension
);
425 filter
= isl_union_map_range(extension
);
426 if (data_outer
.initialized
)
427 filter
= isl_union_set_union(filter
, data_outer
.filter
);
428 if (data
->initialized
)
429 filter
= isl_union_set_intersect(filter
, data
->filter
);
431 data
->filter
= filter
;
433 isl_schedule_tree_free(tree
);
438 /* Update "data" based on the tree node "tree" in case "data" has
439 * not been initialized yet.
441 * Return 0 on success and -1 on error.
443 * If "tree" is a filter, then we set data->filter to this filter
445 * If "tree" is a domain, then this means we have reached the root
446 * of the schedule tree without being able to extract any information.
447 * We therefore initialize data->filter to the universe of the domain,
448 * or the domain itself if data->universe_domain is not set.
449 * If "tree" is a band with at least one member, then we set data->filter
450 * to the universe of the schedule domain and replace the zero-dimensional
451 * data->prefix by the band schedule (if data->collect_prefix is set).
453 static isl_stat
collect_filter_prefix_init(__isl_keep isl_schedule_tree
*tree
,
454 struct isl_schedule_node_get_filter_prefix_data
*data
)
456 enum isl_schedule_node_type type
;
457 isl_multi_union_pw_aff
*mupa
;
458 isl_union_set
*filter
;
460 type
= isl_schedule_tree_get_type(tree
);
462 case isl_schedule_node_error
:
463 return isl_stat_error
;
464 case isl_schedule_node_expansion
:
465 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
466 "should be handled by caller", return isl_stat_error
);
467 case isl_schedule_node_extension
:
468 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
469 "cannot handle extension nodes", return isl_stat_error
);
470 case isl_schedule_node_context
:
471 case isl_schedule_node_leaf
:
472 case isl_schedule_node_guard
:
473 case isl_schedule_node_mark
:
474 case isl_schedule_node_sequence
:
475 case isl_schedule_node_set
:
477 case isl_schedule_node_domain
:
478 filter
= isl_schedule_tree_domain_get_domain(tree
);
479 if (data
->universe_domain
)
480 filter
= isl_union_set_universe(filter
);
481 data
->filter
= filter
;
483 case isl_schedule_node_band
:
484 if (isl_schedule_tree_band_n_member(tree
) == 0)
486 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
487 if (data
->collect_prefix
) {
488 isl_multi_union_pw_aff_free(data
->prefix
);
489 mupa
= isl_multi_union_pw_aff_reset_tuple_id(mupa
,
491 data
->prefix
= isl_multi_union_pw_aff_copy(mupa
);
493 filter
= isl_multi_union_pw_aff_domain(mupa
);
494 filter
= isl_union_set_universe(filter
);
495 data
->filter
= filter
;
497 case isl_schedule_node_filter
:
498 filter
= isl_schedule_tree_filter_get_filter(tree
);
499 if (data
->universe_filter
)
500 filter
= isl_union_set_universe(filter
);
501 data
->filter
= filter
;
505 if ((data
->collect_prefix
&& !data
->prefix
) || !data
->filter
)
506 return isl_stat_error
;
508 data
->initialized
= 1;
513 /* Update "data" based on the tree node "tree" in case "data" has
514 * already been initialized.
516 * Return 0 on success and -1 on error.
518 * If "tree" is a domain and data->universe_domain is not set, then
519 * intersect data->filter with the domain.
520 * If "tree" is a filter, then we intersect data->filter with this filter
522 * If "tree" is a band with at least one member and data->collect_prefix
523 * is set, then we extend data->prefix with the band schedule.
524 * If "tree" is an extension, then we make sure that we are not collecting
525 * information on any extended domain elements.
527 static isl_stat
collect_filter_prefix_update(__isl_keep isl_schedule_tree
*tree
,
528 struct isl_schedule_node_get_filter_prefix_data
*data
)
530 enum isl_schedule_node_type type
;
531 isl_multi_union_pw_aff
*mupa
;
532 isl_union_set
*filter
;
533 isl_union_map
*extension
;
536 type
= isl_schedule_tree_get_type(tree
);
538 case isl_schedule_node_error
:
539 return isl_stat_error
;
540 case isl_schedule_node_expansion
:
541 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
542 "should be handled by caller", return isl_stat_error
);
543 case isl_schedule_node_extension
:
544 extension
= isl_schedule_tree_extension_get_extension(tree
);
545 extension
= isl_union_map_intersect_range(extension
,
546 isl_union_set_copy(data
->filter
));
547 empty
= isl_union_map_is_empty(extension
);
548 isl_union_map_free(extension
);
550 return isl_stat_error
;
553 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_invalid
,
554 "cannot handle extension nodes", return isl_stat_error
);
555 case isl_schedule_node_context
:
556 case isl_schedule_node_leaf
:
557 case isl_schedule_node_guard
:
558 case isl_schedule_node_mark
:
559 case isl_schedule_node_sequence
:
560 case isl_schedule_node_set
:
562 case isl_schedule_node_domain
:
563 if (data
->universe_domain
)
565 filter
= isl_schedule_tree_domain_get_domain(tree
);
566 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
568 case isl_schedule_node_band
:
569 if (isl_schedule_tree_band_n_member(tree
) == 0)
571 if (!data
->collect_prefix
)
573 mupa
= isl_schedule_tree_band_get_partial_schedule(tree
);
574 data
->prefix
= isl_multi_union_pw_aff_flat_range_product(mupa
,
577 return isl_stat_error
;
579 case isl_schedule_node_filter
:
580 filter
= isl_schedule_tree_filter_get_filter(tree
);
581 if (data
->universe_filter
)
582 filter
= isl_union_set_universe(filter
);
583 data
->filter
= isl_union_set_intersect(data
->filter
, filter
);
585 return isl_stat_error
;
592 /* Collect filter and/or prefix information from the first "n"
593 * elements in "list" (which represent the ancestors of a node).
594 * Store the results in "data".
596 * Extension nodes are only supported if they do not affect the outcome,
597 * i.e., if we are collecting information on non-extended domain elements,
598 * or if we are collecting the universe domain (without prefix).
600 * Return 0 on success and -1 on error.
602 * We traverse the list from innermost ancestor (last element)
603 * to outermost ancestor (first element), calling collect_filter_prefix_init
604 * on each node as long as we have not been able to extract any information
605 * yet and collect_filter_prefix_update afterwards.
606 * If we come across an expansion node, then we interrupt the traversal
607 * and call collect_filter_prefix_expansion to restart the traversal
608 * over the remaining ancestors and to combine the results with those
609 * that have already been collected.
610 * If we come across an extension node and we are only computing
611 * the universe domain, then we interrupt the traversal and call
612 * collect_universe_domain_extension to restart the traversal
613 * over the remaining ancestors and to combine the results with those
614 * that have already been collected.
615 * On successful return, data->initialized will be set since the outermost
616 * ancestor is a domain node, which always results in an initialization.
618 static isl_stat
collect_filter_prefix(__isl_keep isl_schedule_tree_list
*list
,
619 int n
, struct isl_schedule_node_get_filter_prefix_data
*data
)
624 return isl_stat_error
;
626 for (i
= n
- 1; i
>= 0; --i
) {
627 isl_schedule_tree
*tree
;
628 enum isl_schedule_node_type type
;
631 tree
= isl_schedule_tree_list_get_schedule_tree(list
, i
);
633 return isl_stat_error
;
634 type
= isl_schedule_tree_get_type(tree
);
635 if (type
== isl_schedule_node_expansion
)
636 return collect_filter_prefix_expansion(tree
, list
, i
,
638 if (type
== isl_schedule_node_extension
&&
639 data
->universe_domain
&& !data
->collect_prefix
)
640 return collect_universe_domain_extension(tree
, list
, i
,
642 if (!data
->initialized
)
643 r
= collect_filter_prefix_init(tree
, data
);
645 r
= collect_filter_prefix_update(tree
, data
);
646 isl_schedule_tree_free(tree
);
648 return isl_stat_error
;
654 /* Return the concatenation of the partial schedules of all outer band
655 * nodes of "node" interesected with all outer filters
656 * as an isl_multi_union_pw_aff.
657 * None of the ancestors of "node" may be an extension node, unless
658 * there is also a filter ancestor that filters out all the extended
661 * If "node" is pointing at the root of the schedule tree, then
662 * there are no domain elements reaching the current node, so
663 * we return an empty result.
665 * We collect all the filters and partial schedules in collect_filter_prefix
666 * and intersect the domain of the combined schedule with the combined filter.
668 __isl_give isl_multi_union_pw_aff
*
669 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(
670 __isl_keep isl_schedule_node
*node
)
674 struct isl_schedule_node_get_filter_prefix_data data
;
679 space
= isl_schedule_get_space(node
->schedule
);
680 space
= isl_space_set_from_params(space
);
681 if (node
->tree
== node
->schedule
->root
)
682 return isl_multi_union_pw_aff_zero(space
);
684 data
.initialized
= 0;
685 data
.universe_domain
= 1;
686 data
.universe_filter
= 0;
687 data
.collect_prefix
= 1;
689 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
691 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
692 if (n
< 0 || collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
693 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
695 data
.prefix
= isl_multi_union_pw_aff_intersect_domain(data
.prefix
,
701 /* Return the concatenation of the partial schedules of all outer band
702 * nodes of "node" interesected with all outer filters
703 * as an isl_union_pw_multi_aff.
704 * None of the ancestors of "node" may be an extension node, unless
705 * there is also a filter ancestor that filters out all the extended
708 * If "node" is pointing at the root of the schedule tree, then
709 * there are no domain elements reaching the current node, so
710 * we return an empty result.
712 * We collect all the filters and partial schedules in collect_filter_prefix.
713 * The partial schedules are collected as an isl_multi_union_pw_aff.
714 * If this isl_multi_union_pw_aff is zero-dimensional, then it does not
715 * contain any domain information, so we construct the isl_union_pw_multi_aff
716 * result as a zero-dimensional function on the collected filter.
717 * Otherwise, we convert the isl_multi_union_pw_aff to
718 * an isl_multi_union_pw_aff and intersect the domain with the filter.
720 __isl_give isl_union_pw_multi_aff
*
721 isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(
722 __isl_keep isl_schedule_node
*node
)
726 isl_union_pw_multi_aff
*prefix
;
727 struct isl_schedule_node_get_filter_prefix_data data
;
732 space
= isl_schedule_get_space(node
->schedule
);
733 if (node
->tree
== node
->schedule
->root
)
734 return isl_union_pw_multi_aff_empty(space
);
736 space
= isl_space_set_from_params(space
);
737 data
.initialized
= 0;
738 data
.universe_domain
= 1;
739 data
.universe_filter
= 0;
740 data
.collect_prefix
= 1;
742 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
744 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
745 if (n
< 0 || collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
746 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
748 dim
= isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
);
750 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
751 if (data
.prefix
&& dim
== 0) {
752 isl_multi_union_pw_aff_free(data
.prefix
);
753 prefix
= isl_union_pw_multi_aff_from_domain(data
.filter
);
756 isl_union_pw_multi_aff_from_multi_union_pw_aff(data
.prefix
);
757 prefix
= isl_union_pw_multi_aff_intersect_domain(prefix
,
764 /* Return the concatenation of the partial schedules of all outer band
765 * nodes of "node" interesected with all outer filters
766 * as an isl_union_map.
768 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_union_map(
769 __isl_keep isl_schedule_node
*node
)
771 isl_union_pw_multi_aff
*upma
;
773 upma
= isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(node
);
774 return isl_union_map_from_union_pw_multi_aff(upma
);
777 /* Return the concatenation of the partial schedules of all outer band
778 * nodes of "node" intersected with all outer domain constraints.
779 * None of the ancestors of "node" may be an extension node, unless
780 * there is also a filter ancestor that filters out all the extended
783 * Essentially, this function intersects the domain of the output
784 * of isl_schedule_node_get_prefix_schedule_union_map with the output
785 * of isl_schedule_node_get_domain, except that it only traverses
786 * the ancestors of "node" once.
788 __isl_give isl_union_map
*isl_schedule_node_get_prefix_schedule_relation(
789 __isl_keep isl_schedule_node
*node
)
793 isl_union_map
*prefix
;
794 struct isl_schedule_node_get_filter_prefix_data data
;
799 space
= isl_schedule_get_space(node
->schedule
);
800 if (node
->tree
== node
->schedule
->root
)
801 return isl_union_map_empty(space
);
803 space
= isl_space_set_from_params(space
);
804 data
.initialized
= 0;
805 data
.universe_domain
= 0;
806 data
.universe_filter
= 0;
807 data
.collect_prefix
= 1;
809 data
.prefix
= isl_multi_union_pw_aff_zero(space
);
811 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
812 if (n
< 0 || collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
813 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
815 dim
= isl_multi_union_pw_aff_dim(data
.prefix
, isl_dim_set
);
817 data
.prefix
= isl_multi_union_pw_aff_free(data
.prefix
);
818 if (data
.prefix
&& dim
== 0) {
819 isl_multi_union_pw_aff_free(data
.prefix
);
820 prefix
= isl_union_map_from_domain(data
.filter
);
822 prefix
= isl_union_map_from_multi_union_pw_aff(data
.prefix
);
823 prefix
= isl_union_map_intersect_domain(prefix
, data
.filter
);
829 /* Return the domain elements that reach "node".
831 * If "node" is pointing at the root of the schedule tree, then
832 * there are no domain elements reaching the current node, so
833 * we return an empty result.
834 * None of the ancestors of "node" may be an extension node, unless
835 * there is also a filter ancestor that filters out all the extended
838 * Otherwise, we collect all filters reaching the node,
839 * intersected with the root domain in collect_filter_prefix.
841 __isl_give isl_union_set
*isl_schedule_node_get_domain(
842 __isl_keep isl_schedule_node
*node
)
845 struct isl_schedule_node_get_filter_prefix_data data
;
850 if (node
->tree
== node
->schedule
->root
) {
853 space
= isl_schedule_get_space(node
->schedule
);
854 return isl_union_set_empty(space
);
857 data
.initialized
= 0;
858 data
.universe_domain
= 0;
859 data
.universe_filter
= 0;
860 data
.collect_prefix
= 0;
864 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
865 if (n
< 0 || collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
866 data
.filter
= isl_union_set_free(data
.filter
);
871 /* Return the union of universe sets of the domain elements that reach "node".
873 * If "node" is pointing at the root of the schedule tree, then
874 * there are no domain elements reaching the current node, so
875 * we return an empty result.
877 * Otherwise, we collect the universes of all filters reaching the node
878 * in collect_filter_prefix.
880 __isl_give isl_union_set
*isl_schedule_node_get_universe_domain(
881 __isl_keep isl_schedule_node
*node
)
884 struct isl_schedule_node_get_filter_prefix_data data
;
889 if (node
->tree
== node
->schedule
->root
) {
892 space
= isl_schedule_get_space(node
->schedule
);
893 return isl_union_set_empty(space
);
896 data
.initialized
= 0;
897 data
.universe_domain
= 1;
898 data
.universe_filter
= 1;
899 data
.collect_prefix
= 0;
903 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
904 if (n
< 0 || collect_filter_prefix(node
->ancestors
, n
, &data
) < 0)
905 data
.filter
= isl_union_set_free(data
.filter
);
910 /* Return the subtree schedule of "node".
912 * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle
913 * trees that do not contain any schedule information, we first
914 * move down to the first relevant descendant and handle leaves ourselves.
916 * If the subtree rooted at "node" contains any expansion nodes, then
917 * the returned subtree schedule is formulated in terms of the expanded
919 * The subtree is not allowed to contain any extension nodes.
921 __isl_give isl_union_map
*isl_schedule_node_get_subtree_schedule_union_map(
922 __isl_keep isl_schedule_node
*node
)
924 isl_schedule_tree
*tree
, *leaf
;
927 tree
= isl_schedule_node_get_tree(node
);
928 leaf
= isl_schedule_node_peek_leaf(node
);
929 tree
= isl_schedule_tree_first_schedule_descendant(tree
, leaf
);
933 isl_union_set
*domain
;
934 domain
= isl_schedule_node_get_universe_domain(node
);
935 isl_schedule_tree_free(tree
);
936 return isl_union_map_from_domain(domain
);
939 umap
= isl_schedule_tree_get_subtree_schedule_union_map(tree
);
940 isl_schedule_tree_free(tree
);
944 /* Return the number of ancestors of "node" in its schedule tree.
946 isl_size
isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node
*node
)
949 return isl_size_error
;
950 return isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
953 /* Does "node" have a parent?
955 * That is, does it point to any node of the schedule other than the root?
957 isl_bool
isl_schedule_node_has_parent(__isl_keep isl_schedule_node
*node
)
961 depth
= isl_schedule_node_get_tree_depth(node
);
963 return isl_bool_error
;
967 /* Return the position of "node" among the children of its parent.
969 isl_size
isl_schedule_node_get_child_position(
970 __isl_keep isl_schedule_node
*node
)
976 return isl_size_error
;
977 has_parent
= isl_schedule_node_has_parent(node
);
979 return isl_size_error
;
981 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
982 "node has no parent", return isl_size_error
);
984 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
985 return n
< 0 ? isl_size_error
: node
->child_pos
[n
- 1];
988 /* Does the parent (if any) of "node" have any children with a smaller child
989 * position than this one?
991 isl_bool
isl_schedule_node_has_previous_sibling(
992 __isl_keep isl_schedule_node
*node
)
998 return isl_bool_error
;
999 has_parent
= isl_schedule_node_has_parent(node
);
1000 if (has_parent
< 0 || !has_parent
)
1003 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1005 return isl_bool_error
;
1007 return node
->child_pos
[n
- 1] > 0;
1010 /* Does the parent (if any) of "node" have any children with a greater child
1011 * position than this one?
1013 isl_bool
isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node
*node
)
1015 isl_size n
, n_child
;
1016 isl_bool has_parent
;
1017 isl_schedule_tree
*tree
;
1020 return isl_bool_error
;
1021 has_parent
= isl_schedule_node_has_parent(node
);
1022 if (has_parent
< 0 || !has_parent
)
1025 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1027 return isl_bool_error
;
1028 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n
- 1);
1029 n_child
= isl_schedule_tree_n_children(tree
);
1030 isl_schedule_tree_free(tree
);
1032 return isl_bool_error
;
1034 return node
->child_pos
[n
- 1] + 1 < n_child
;
1037 /* Does "node" have any children?
1039 * Any node other than the leaf nodes is considered to have at least
1040 * one child, even if the corresponding isl_schedule_tree does not
1041 * have any children.
1043 isl_bool
isl_schedule_node_has_children(__isl_keep isl_schedule_node
*node
)
1046 return isl_bool_error
;
1047 return !isl_schedule_tree_is_leaf(node
->tree
);
1050 /* Return the number of children of "node"?
1052 * Any node other than the leaf nodes is considered to have at least
1053 * one child, even if the corresponding isl_schedule_tree does not
1054 * have any children. That is, the number of children of "node" is
1055 * only zero if its tree is the explicit empty tree. Otherwise,
1056 * if the isl_schedule_tree has any children, then it is equal
1057 * to the number of children of "node". If it has zero children,
1058 * then "node" still has a leaf node as child.
1060 isl_size
isl_schedule_node_n_children(__isl_keep isl_schedule_node
*node
)
1065 return isl_size_error
;
1067 if (isl_schedule_tree_is_leaf(node
->tree
))
1070 n
= isl_schedule_tree_n_children(node
->tree
);
1072 return isl_size_error
;
1079 /* Move the "node" pointer to the ancestor of the given generation
1080 * of the node it currently points to, where generation 0 is the node
1081 * itself and generation 1 is its parent.
1083 __isl_give isl_schedule_node
*isl_schedule_node_ancestor(
1084 __isl_take isl_schedule_node
*node
, int generation
)
1087 isl_schedule_tree
*tree
;
1091 if (generation
== 0)
1093 n
= isl_schedule_node_get_tree_depth(node
);
1095 return isl_schedule_node_free(node
);
1096 if (generation
< 0 || generation
> n
)
1097 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1098 "generation out of bounds",
1099 return isl_schedule_node_free(node
));
1100 node
= isl_schedule_node_cow(node
);
1104 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1106 isl_schedule_tree_free(node
->tree
);
1108 node
->ancestors
= isl_schedule_tree_list_drop(node
->ancestors
,
1109 n
- generation
, generation
);
1110 if (!node
->ancestors
|| !node
->tree
)
1111 return isl_schedule_node_free(node
);
1116 /* Move the "node" pointer to the parent of the node it currently points to.
1118 __isl_give isl_schedule_node
*isl_schedule_node_parent(
1119 __isl_take isl_schedule_node
*node
)
1123 if (!isl_schedule_node_has_parent(node
))
1124 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1125 "node has no parent",
1126 return isl_schedule_node_free(node
));
1127 return isl_schedule_node_ancestor(node
, 1);
1130 /* Move the "node" pointer to the root of its schedule tree.
1132 __isl_give isl_schedule_node
*isl_schedule_node_root(
1133 __isl_take isl_schedule_node
*node
)
1139 n
= isl_schedule_node_get_tree_depth(node
);
1141 return isl_schedule_node_free(node
);
1142 return isl_schedule_node_ancestor(node
, n
);
1145 /* Move the "node" pointer to the child at position "pos" of the node
1146 * it currently points to.
1148 __isl_give isl_schedule_node
*isl_schedule_node_child(
1149 __isl_take isl_schedule_node
*node
, int pos
)
1153 isl_schedule_tree
*tree
;
1156 node
= isl_schedule_node_cow(node
);
1159 if (!isl_schedule_node_has_children(node
))
1160 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1161 "node has no children",
1162 return isl_schedule_node_free(node
));
1164 ctx
= isl_schedule_node_get_ctx(node
);
1165 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1167 return isl_schedule_node_free(node
);
1168 child_pos
= isl_realloc_array(ctx
, node
->child_pos
, int, n
+ 1);
1170 return isl_schedule_node_free(node
);
1171 node
->child_pos
= child_pos
;
1172 node
->child_pos
[n
] = pos
;
1174 node
->ancestors
= isl_schedule_tree_list_add(node
->ancestors
,
1175 isl_schedule_tree_copy(node
->tree
));
1177 if (isl_schedule_tree_has_children(tree
))
1178 tree
= isl_schedule_tree_get_child(tree
, pos
);
1180 tree
= isl_schedule_node_get_leaf(node
);
1181 isl_schedule_tree_free(node
->tree
);
1184 if (!node
->tree
|| !node
->ancestors
)
1185 return isl_schedule_node_free(node
);
1190 /* Move the "node" pointer to the first child of the node
1191 * it currently points to.
1193 __isl_give isl_schedule_node
*isl_schedule_node_first_child(
1194 __isl_take isl_schedule_node
*node
)
1196 return isl_schedule_node_child(node
, 0);
1199 /* Move the "node" pointer to the child of this node's parent in
1200 * the previous child position.
1202 __isl_give isl_schedule_node
*isl_schedule_node_previous_sibling(
1203 __isl_take isl_schedule_node
*node
)
1206 isl_schedule_tree
*parent
, *tree
;
1208 node
= isl_schedule_node_cow(node
);
1211 if (!isl_schedule_node_has_previous_sibling(node
))
1212 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1213 "node has no previous sibling",
1214 return isl_schedule_node_free(node
));
1216 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1218 return isl_schedule_node_free(node
);
1219 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1222 return isl_schedule_node_free(node
);
1223 node
->child_pos
[n
- 1]--;
1224 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1225 node
->child_pos
[n
- 1]);
1226 isl_schedule_tree_free(parent
);
1228 return isl_schedule_node_free(node
);
1229 isl_schedule_tree_free(node
->tree
);
1235 /* Move the "node" pointer to the child of this node's parent in
1236 * the next child position.
1238 __isl_give isl_schedule_node
*isl_schedule_node_next_sibling(
1239 __isl_take isl_schedule_node
*node
)
1242 isl_schedule_tree
*parent
, *tree
;
1244 node
= isl_schedule_node_cow(node
);
1247 if (!isl_schedule_node_has_next_sibling(node
))
1248 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1249 "node has no next sibling",
1250 return isl_schedule_node_free(node
));
1252 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
1254 return isl_schedule_node_free(node
);
1255 parent
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
1258 return isl_schedule_node_free(node
);
1259 node
->child_pos
[n
- 1]++;
1260 tree
= isl_schedule_tree_list_get_schedule_tree(parent
->children
,
1261 node
->child_pos
[n
- 1]);
1262 isl_schedule_tree_free(parent
);
1264 return isl_schedule_node_free(node
);
1265 isl_schedule_tree_free(node
->tree
);
1271 /* Return a copy to the child at position "pos" of "node".
1273 __isl_give isl_schedule_node
*isl_schedule_node_get_child(
1274 __isl_keep isl_schedule_node
*node
, int pos
)
1276 return isl_schedule_node_child(isl_schedule_node_copy(node
), pos
);
1279 /* Traverse the descendant of "node" in depth-first order, including
1280 * "node" itself. Call "enter" whenever a node is entered and "leave"
1281 * whenever a node is left. The callback "enter" is responsible
1282 * for moving to the deepest initial subtree of its argument that
1283 * should be traversed.
1285 static __isl_give isl_schedule_node
*traverse(
1286 __isl_take isl_schedule_node
*node
,
1287 __isl_give isl_schedule_node
*(*enter
)(
1288 __isl_take isl_schedule_node
*node
, void *user
),
1289 __isl_give isl_schedule_node
*(*leave
)(
1290 __isl_take isl_schedule_node
*node
, void *user
),
1294 isl_size node_depth
;
1296 depth
= isl_schedule_node_get_tree_depth(node
);
1298 return isl_schedule_node_free(node
);
1301 node
= enter(node
, user
);
1302 node
= leave(node
, user
);
1303 while ((node_depth
= isl_schedule_node_get_tree_depth(node
)) >
1305 !isl_schedule_node_has_next_sibling(node
)) {
1306 node
= isl_schedule_node_parent(node
);
1307 node
= leave(node
, user
);
1310 return isl_schedule_node_free(node
);
1311 if (node_depth
> depth
)
1312 node
= isl_schedule_node_next_sibling(node
);
1313 } while (node_depth
> depth
);
1318 /* Internal data structure for isl_schedule_node_foreach_descendant_top_down.
1320 * "fn" is the user-specified callback function.
1321 * "user" is the user-specified argument for the callback.
1323 struct isl_schedule_node_preorder_data
{
1324 isl_bool (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
);
1328 /* Callback for "traverse" to enter a node and to move
1329 * to the deepest initial subtree that should be traversed
1330 * for use in a preorder visit.
1332 * If the user callback returns a negative value, then we abort
1333 * the traversal. If this callback returns zero, then we skip
1334 * the subtree rooted at the current node. Otherwise, we move
1335 * down to the first child and repeat the process until a leaf
1338 static __isl_give isl_schedule_node
*preorder_enter(
1339 __isl_take isl_schedule_node
*node
, void *user
)
1341 struct isl_schedule_node_preorder_data
*data
= user
;
1349 r
= data
->fn(node
, data
->user
);
1351 return isl_schedule_node_free(node
);
1352 if (r
== isl_bool_false
)
1354 } while (isl_schedule_node_has_children(node
) &&
1355 (node
= isl_schedule_node_first_child(node
)) != NULL
);
1360 /* Callback for "traverse" to leave a node
1361 * for use in a preorder visit.
1362 * Since we already visited the node when we entered it,
1363 * we do not need to do anything here.
1365 static __isl_give isl_schedule_node
*preorder_leave(
1366 __isl_take isl_schedule_node
*node
, void *user
)
1371 /* Traverse the descendants of "node" (including the node itself)
1372 * in depth first preorder.
1374 * If "fn" returns isl_bool_error on any of the nodes,
1375 * then the traversal is aborted.
1376 * If "fn" returns isl_bool_false on any of the nodes, then the subtree rooted
1377 * at that node is skipped.
1379 * Return isl_stat_ok on success and isl_stat_error on failure.
1381 isl_stat
isl_schedule_node_foreach_descendant_top_down(
1382 __isl_keep isl_schedule_node
*node
,
1383 isl_bool (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
),
1386 struct isl_schedule_node_preorder_data data
= { fn
, user
};
1388 node
= isl_schedule_node_copy(node
);
1389 node
= traverse(node
, &preorder_enter
, &preorder_leave
, &data
);
1390 isl_schedule_node_free(node
);
1392 return node
? isl_stat_ok
: isl_stat_error
;
1395 /* Internal data structure for isl_schedule_node_every_descendant.
1397 * "test" is the user-specified callback function.
1398 * "user" is the user-specified callback function argument.
1400 * "failed" is initialized to 0 and set to 1 if "test" fails
1403 struct isl_union_map_every_data
{
1404 isl_bool (*test
)(__isl_keep isl_schedule_node
*node
, void *user
);
1409 /* isl_schedule_node_foreach_descendant_top_down callback
1410 * that sets data->failed if data->test returns false and
1411 * subsequently aborts the traversal.
1413 static isl_bool
call_every(__isl_keep isl_schedule_node
*node
, void *user
)
1415 struct isl_union_map_every_data
*data
= user
;
1418 r
= data
->test(node
, data
->user
);
1420 return isl_bool_error
;
1422 return isl_bool_true
;
1424 return isl_bool_error
;
1427 /* Does "test" succeed on every descendant of "node" (including "node" itself)?
1429 isl_bool
isl_schedule_node_every_descendant(__isl_keep isl_schedule_node
*node
,
1430 isl_bool (*test
)(__isl_keep isl_schedule_node
*node
, void *user
),
1433 struct isl_union_map_every_data data
= { test
, user
, 0 };
1436 r
= isl_schedule_node_foreach_descendant_top_down(node
, &call_every
,
1439 return isl_bool_true
;
1441 return isl_bool_false
;
1442 return isl_bool_error
;
1445 /* Internal data structure for isl_schedule_node_map_descendant_bottom_up.
1447 * "fn" is the user-specified callback function.
1448 * "user" is the user-specified argument for the callback.
1450 struct isl_schedule_node_postorder_data
{
1451 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1456 /* Callback for "traverse" to enter a node and to move
1457 * to the deepest initial subtree that should be traversed
1458 * for use in a postorder visit.
1460 * Since we are performing a postorder visit, we only need
1461 * to move to the deepest initial leaf here.
1463 static __isl_give isl_schedule_node
*postorder_enter(
1464 __isl_take isl_schedule_node
*node
, void *user
)
1466 while (node
&& isl_schedule_node_has_children(node
))
1467 node
= isl_schedule_node_first_child(node
);
1472 /* Callback for "traverse" to leave a node
1473 * for use in a postorder visit.
1475 * Since we are performing a postorder visit, we need
1476 * to call the user callback here.
1478 static __isl_give isl_schedule_node
*postorder_leave(
1479 __isl_take isl_schedule_node
*node
, void *user
)
1481 struct isl_schedule_node_postorder_data
*data
= user
;
1483 return data
->fn(node
, data
->user
);
1486 /* Traverse the descendants of "node" (including the node itself)
1487 * in depth first postorder, allowing the user to modify the visited node.
1488 * The traversal continues from the node returned by the callback function.
1489 * It is the responsibility of the user to ensure that this does not
1490 * lead to an infinite loop. It is safest to always return a pointer
1491 * to the same position (same ancestors and child positions) as the input node.
1493 __isl_give isl_schedule_node
*isl_schedule_node_map_descendant_bottom_up(
1494 __isl_take isl_schedule_node
*node
,
1495 __isl_give isl_schedule_node
*(*fn
)(__isl_take isl_schedule_node
*node
,
1496 void *user
), void *user
)
1498 struct isl_schedule_node_postorder_data data
= { fn
, user
};
1500 return traverse(node
, &postorder_enter
, &postorder_leave
, &data
);
1503 /* Traverse the ancestors of "node" from the root down to and including
1504 * the parent of "node", calling "fn" on each of them.
1506 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1508 * Return 0 on success and -1 on failure.
1510 isl_stat
isl_schedule_node_foreach_ancestor_top_down(
1511 __isl_keep isl_schedule_node
*node
,
1512 isl_stat (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
),
1518 n
= isl_schedule_node_get_tree_depth(node
);
1520 return isl_stat_error
;
1522 for (i
= 0; i
< n
; ++i
) {
1523 isl_schedule_node
*ancestor
;
1526 ancestor
= isl_schedule_node_copy(node
);
1527 ancestor
= isl_schedule_node_ancestor(ancestor
, n
- i
);
1528 r
= fn(ancestor
, user
);
1529 isl_schedule_node_free(ancestor
);
1531 return isl_stat_error
;
1537 /* Is any node in the subtree rooted at "node" anchored?
1538 * That is, do any of these nodes reference the outer band nodes?
1540 isl_bool
isl_schedule_node_is_subtree_anchored(
1541 __isl_keep isl_schedule_node
*node
)
1544 return isl_bool_error
;
1545 return isl_schedule_tree_is_subtree_anchored(node
->tree
);
1548 /* Return the number of members in the given band node.
1550 unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node
*node
)
1552 return node
? isl_schedule_tree_band_n_member(node
->tree
) : 0;
1555 /* Is the band member at position "pos" of the band node "node"
1556 * marked coincident?
1558 isl_bool
isl_schedule_node_band_member_get_coincident(
1559 __isl_keep isl_schedule_node
*node
, int pos
)
1562 return isl_bool_error
;
1563 return isl_schedule_tree_band_member_get_coincident(node
->tree
, pos
);
1566 /* Mark the band member at position "pos" the band node "node"
1567 * as being coincident or not according to "coincident".
1569 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_coincident(
1570 __isl_take isl_schedule_node
*node
, int pos
, int coincident
)
1573 isl_schedule_tree
*tree
;
1577 c
= isl_schedule_node_band_member_get_coincident(node
, pos
);
1578 if (c
== coincident
)
1581 tree
= isl_schedule_tree_copy(node
->tree
);
1582 tree
= isl_schedule_tree_band_member_set_coincident(tree
, pos
,
1584 node
= isl_schedule_node_graft_tree(node
, tree
);
1589 /* Is the band node "node" marked permutable?
1591 isl_bool
isl_schedule_node_band_get_permutable(
1592 __isl_keep isl_schedule_node
*node
)
1595 return isl_bool_error
;
1597 return isl_schedule_tree_band_get_permutable(node
->tree
);
1600 /* Mark the band node "node" permutable or not according to "permutable"?
1602 __isl_give isl_schedule_node
*isl_schedule_node_band_set_permutable(
1603 __isl_take isl_schedule_node
*node
, int permutable
)
1605 isl_schedule_tree
*tree
;
1609 if (isl_schedule_node_band_get_permutable(node
) == permutable
)
1612 tree
= isl_schedule_tree_copy(node
->tree
);
1613 tree
= isl_schedule_tree_band_set_permutable(tree
, permutable
);
1614 node
= isl_schedule_node_graft_tree(node
, tree
);
1619 /* Return the schedule space of the band node.
1621 __isl_give isl_space
*isl_schedule_node_band_get_space(
1622 __isl_keep isl_schedule_node
*node
)
1627 return isl_schedule_tree_band_get_space(node
->tree
);
1630 /* Return the schedule of the band node in isolation.
1632 __isl_give isl_multi_union_pw_aff
*isl_schedule_node_band_get_partial_schedule(
1633 __isl_keep isl_schedule_node
*node
)
1638 return isl_schedule_tree_band_get_partial_schedule(node
->tree
);
1641 /* Return the schedule of the band node in isolation in the form of
1644 * If the band does not have any members, then we construct a universe map
1645 * with the universe of the domain elements reaching the node as domain.
1646 * Otherwise, we extract an isl_multi_union_pw_aff representation and
1647 * convert that to an isl_union_map.
1649 __isl_give isl_union_map
*isl_schedule_node_band_get_partial_schedule_union_map(
1650 __isl_keep isl_schedule_node
*node
)
1652 isl_multi_union_pw_aff
*mupa
;
1657 if (isl_schedule_node_get_type(node
) != isl_schedule_node_band
)
1658 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1659 "not a band node", return NULL
);
1660 if (isl_schedule_node_band_n_member(node
) == 0) {
1661 isl_union_set
*domain
;
1663 domain
= isl_schedule_node_get_universe_domain(node
);
1664 return isl_union_map_from_domain(domain
);
1667 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
1668 return isl_union_map_from_multi_union_pw_aff(mupa
);
1671 /* Return the loop AST generation type for the band member of band node "node"
1672 * at position "pos".
1674 enum isl_ast_loop_type
isl_schedule_node_band_member_get_ast_loop_type(
1675 __isl_keep isl_schedule_node
*node
, int pos
)
1678 return isl_ast_loop_error
;
1680 return isl_schedule_tree_band_member_get_ast_loop_type(node
->tree
, pos
);
1683 /* Set the loop AST generation type for the band member of band node "node"
1684 * at position "pos" to "type".
1686 __isl_give isl_schedule_node
*isl_schedule_node_band_member_set_ast_loop_type(
1687 __isl_take isl_schedule_node
*node
, int pos
,
1688 enum isl_ast_loop_type type
)
1690 isl_schedule_tree
*tree
;
1695 tree
= isl_schedule_tree_copy(node
->tree
);
1696 tree
= isl_schedule_tree_band_member_set_ast_loop_type(tree
, pos
, type
);
1697 return isl_schedule_node_graft_tree(node
, tree
);
1700 /* Return the loop AST generation type for the band member of band node "node"
1701 * at position "pos" for the isolated part.
1703 enum isl_ast_loop_type
isl_schedule_node_band_member_get_isolate_ast_loop_type(
1704 __isl_keep isl_schedule_node
*node
, int pos
)
1707 return isl_ast_loop_error
;
1709 return isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1713 /* Set the loop AST generation type for the band member of band node "node"
1714 * at position "pos" for the isolated part to "type".
1716 __isl_give isl_schedule_node
*
1717 isl_schedule_node_band_member_set_isolate_ast_loop_type(
1718 __isl_take isl_schedule_node
*node
, int pos
,
1719 enum isl_ast_loop_type type
)
1721 isl_schedule_tree
*tree
;
1726 tree
= isl_schedule_tree_copy(node
->tree
);
1727 tree
= isl_schedule_tree_band_member_set_isolate_ast_loop_type(tree
,
1729 return isl_schedule_node_graft_tree(node
, tree
);
1732 /* Return the AST build options associated to band node "node".
1734 __isl_give isl_union_set
*isl_schedule_node_band_get_ast_build_options(
1735 __isl_keep isl_schedule_node
*node
)
1740 return isl_schedule_tree_band_get_ast_build_options(node
->tree
);
1743 /* Replace the AST build options associated to band node "node" by "options".
1745 __isl_give isl_schedule_node
*isl_schedule_node_band_set_ast_build_options(
1746 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*options
)
1748 isl_schedule_tree
*tree
;
1750 if (!node
|| !options
)
1753 tree
= isl_schedule_tree_copy(node
->tree
);
1754 tree
= isl_schedule_tree_band_set_ast_build_options(tree
, options
);
1755 return isl_schedule_node_graft_tree(node
, tree
);
1757 isl_schedule_node_free(node
);
1758 isl_union_set_free(options
);
1762 /* Return the "isolate" option associated to band node "node".
1764 __isl_give isl_set
*isl_schedule_node_band_get_ast_isolate_option(
1765 __isl_keep isl_schedule_node
*node
)
1772 depth
= isl_schedule_node_get_schedule_depth(node
);
1773 return isl_schedule_tree_band_get_ast_isolate_option(node
->tree
, depth
);
1776 /* Make sure that that spaces of "node" and "mv" are the same.
1777 * Return -1 on error, reporting the error to the user.
1779 static int check_space_multi_val(__isl_keep isl_schedule_node
*node
,
1780 __isl_keep isl_multi_val
*mv
)
1782 isl_space
*node_space
, *mv_space
;
1785 node_space
= isl_schedule_node_band_get_space(node
);
1786 mv_space
= isl_multi_val_get_space(mv
);
1787 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1788 mv_space
, isl_dim_set
);
1789 isl_space_free(mv_space
);
1790 isl_space_free(node_space
);
1794 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1795 "spaces don't match", return -1);
1800 /* Multiply the partial schedule of the band node "node"
1801 * with the factors in "mv".
1803 __isl_give isl_schedule_node
*isl_schedule_node_band_scale(
1804 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1806 isl_schedule_tree
*tree
;
1811 if (check_space_multi_val(node
, mv
) < 0)
1813 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1817 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1818 "cannot scale band node with anchored subtree",
1821 tree
= isl_schedule_node_get_tree(node
);
1822 tree
= isl_schedule_tree_band_scale(tree
, mv
);
1823 return isl_schedule_node_graft_tree(node
, tree
);
1825 isl_multi_val_free(mv
);
1826 isl_schedule_node_free(node
);
1830 /* Divide the partial schedule of the band node "node"
1831 * by the factors in "mv".
1833 __isl_give isl_schedule_node
*isl_schedule_node_band_scale_down(
1834 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1836 isl_schedule_tree
*tree
;
1841 if (check_space_multi_val(node
, mv
) < 0)
1843 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1847 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1848 "cannot scale down band node with anchored subtree",
1851 tree
= isl_schedule_node_get_tree(node
);
1852 tree
= isl_schedule_tree_band_scale_down(tree
, mv
);
1853 return isl_schedule_node_graft_tree(node
, tree
);
1855 isl_multi_val_free(mv
);
1856 isl_schedule_node_free(node
);
1860 /* Reduce the partial schedule of the band node "node"
1861 * modulo the factors in "mv".
1863 __isl_give isl_schedule_node
*isl_schedule_node_band_mod(
1864 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*mv
)
1866 isl_schedule_tree
*tree
;
1871 if (check_space_multi_val(node
, mv
) < 0)
1873 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1877 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1878 "cannot perform mod on band node with anchored subtree",
1881 tree
= isl_schedule_node_get_tree(node
);
1882 tree
= isl_schedule_tree_band_mod(tree
, mv
);
1883 return isl_schedule_node_graft_tree(node
, tree
);
1885 isl_multi_val_free(mv
);
1886 isl_schedule_node_free(node
);
1890 /* Make sure that that spaces of "node" and "mupa" are the same.
1891 * Return isl_stat_error on error, reporting the error to the user.
1893 static isl_stat
check_space_multi_union_pw_aff(
1894 __isl_keep isl_schedule_node
*node
,
1895 __isl_keep isl_multi_union_pw_aff
*mupa
)
1897 isl_space
*node_space
, *mupa_space
;
1900 node_space
= isl_schedule_node_band_get_space(node
);
1901 mupa_space
= isl_multi_union_pw_aff_get_space(mupa
);
1902 equal
= isl_space_tuple_is_equal(node_space
, isl_dim_set
,
1903 mupa_space
, isl_dim_set
);
1904 isl_space_free(mupa_space
);
1905 isl_space_free(node_space
);
1907 return isl_stat_error
;
1909 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1910 "spaces don't match", return isl_stat_error
);
1915 /* Shift the partial schedule of the band node "node" by "shift".
1917 __isl_give isl_schedule_node
*isl_schedule_node_band_shift(
1918 __isl_take isl_schedule_node
*node
,
1919 __isl_take isl_multi_union_pw_aff
*shift
)
1921 isl_schedule_tree
*tree
;
1924 if (!node
|| !shift
)
1926 if (check_space_multi_union_pw_aff(node
, shift
) < 0)
1928 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1932 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1933 "cannot shift band node with anchored subtree",
1936 tree
= isl_schedule_node_get_tree(node
);
1937 tree
= isl_schedule_tree_band_shift(tree
, shift
);
1938 return isl_schedule_node_graft_tree(node
, tree
);
1940 isl_multi_union_pw_aff_free(shift
);
1941 isl_schedule_node_free(node
);
1945 /* Tile "node" with tile sizes "sizes".
1947 * The current node is replaced by two nested nodes corresponding
1948 * to the tile dimensions and the point dimensions.
1950 * Return a pointer to the outer (tile) node.
1952 * If any of the descendants of "node" depend on the set of outer band nodes,
1953 * then we refuse to tile the node.
1955 * If the scale tile loops option is set, then the tile loops
1956 * are scaled by the tile sizes. If the shift point loops option is set,
1957 * then the point loops are shifted to start at zero.
1958 * In particular, these options affect the tile and point loop schedules
1961 * scale shift original tile point
1963 * 0 0 i floor(i/s) i
1964 * 1 0 i s * floor(i/s) i
1965 * 0 1 i floor(i/s) i - s * floor(i/s)
1966 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1968 __isl_give isl_schedule_node
*isl_schedule_node_band_tile(
1969 __isl_take isl_schedule_node
*node
, __isl_take isl_multi_val
*sizes
)
1971 isl_schedule_tree
*tree
;
1974 if (!node
|| !sizes
)
1976 anchored
= isl_schedule_node_is_subtree_anchored(node
);
1980 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
1981 "cannot tile band node with anchored subtree",
1984 if (check_space_multi_val(node
, sizes
) < 0)
1987 tree
= isl_schedule_node_get_tree(node
);
1988 tree
= isl_schedule_tree_band_tile(tree
, sizes
);
1989 return isl_schedule_node_graft_tree(node
, tree
);
1991 isl_multi_val_free(sizes
);
1992 isl_schedule_node_free(node
);
1996 /* Move the band node "node" down to all the leaves in the subtree
1998 * Return a pointer to the node in the resulting tree that is in the same
1999 * position as the node pointed to by "node" in the original tree.
2001 * If the node only has a leaf child, then nothing needs to be done.
2002 * Otherwise, the child of the node is removed and the result is
2003 * appended to all the leaves in the subtree rooted at the original child.
2004 * Since the node is moved to the leaves, it needs to be expanded
2005 * according to the expansion, if any, defined by that subtree.
2006 * In the end, the original node is replaced by the result of
2007 * attaching copies of the expanded node to the leaves.
2009 * If any of the nodes in the subtree rooted at "node" depend on
2010 * the set of outer band nodes then we refuse to sink the band node.
2012 __isl_give isl_schedule_node
*isl_schedule_node_band_sink(
2013 __isl_take isl_schedule_node
*node
)
2015 enum isl_schedule_node_type type
;
2016 isl_schedule_tree
*tree
, *child
;
2017 isl_union_pw_multi_aff
*contraction
;
2024 type
= isl_schedule_node_get_type(node
);
2025 if (type
!= isl_schedule_node_band
)
2026 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2027 "not a band node", return isl_schedule_node_free(node
));
2028 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2030 return isl_schedule_node_free(node
);
2032 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2033 "cannot sink band node in anchored subtree",
2034 return isl_schedule_node_free(node
));
2035 n
= isl_schedule_tree_n_children(node
->tree
);
2037 return isl_schedule_node_free(node
);
2041 contraction
= isl_schedule_node_get_subtree_contraction(node
);
2043 tree
= isl_schedule_node_get_tree(node
);
2044 child
= isl_schedule_tree_get_child(tree
, 0);
2045 tree
= isl_schedule_tree_reset_children(tree
);
2046 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, contraction
);
2047 tree
= isl_schedule_tree_append_to_leaves(child
, tree
);
2049 return isl_schedule_node_graft_tree(node
, tree
);
2052 /* Split "node" into two nested band nodes, one with the first "pos"
2053 * dimensions and one with the remaining dimensions.
2054 * The schedules of the two band nodes live in anonymous spaces.
2055 * The loop AST generation type options and the isolate option
2056 * are split over the two band nodes.
2058 __isl_give isl_schedule_node
*isl_schedule_node_band_split(
2059 __isl_take isl_schedule_node
*node
, int pos
)
2062 isl_schedule_tree
*tree
;
2064 depth
= isl_schedule_node_get_schedule_depth(node
);
2065 tree
= isl_schedule_node_get_tree(node
);
2066 tree
= isl_schedule_tree_band_split(tree
, pos
, depth
);
2067 return isl_schedule_node_graft_tree(node
, tree
);
2070 /* Return the context of the context node "node".
2072 __isl_give isl_set
*isl_schedule_node_context_get_context(
2073 __isl_keep isl_schedule_node
*node
)
2078 return isl_schedule_tree_context_get_context(node
->tree
);
2081 /* Return the domain of the domain node "node".
2083 __isl_give isl_union_set
*isl_schedule_node_domain_get_domain(
2084 __isl_keep isl_schedule_node
*node
)
2089 return isl_schedule_tree_domain_get_domain(node
->tree
);
2092 /* Return the expansion map of expansion node "node".
2094 __isl_give isl_union_map
*isl_schedule_node_expansion_get_expansion(
2095 __isl_keep isl_schedule_node
*node
)
2100 return isl_schedule_tree_expansion_get_expansion(node
->tree
);
2103 /* Return the contraction of expansion node "node".
2105 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_expansion_get_contraction(
2106 __isl_keep isl_schedule_node
*node
)
2111 return isl_schedule_tree_expansion_get_contraction(node
->tree
);
2114 /* Replace the contraction and the expansion of the expansion node "node"
2115 * by "contraction" and "expansion".
2117 __isl_give isl_schedule_node
*
2118 isl_schedule_node_expansion_set_contraction_and_expansion(
2119 __isl_take isl_schedule_node
*node
,
2120 __isl_take isl_union_pw_multi_aff
*contraction
,
2121 __isl_take isl_union_map
*expansion
)
2123 isl_schedule_tree
*tree
;
2125 if (!node
|| !contraction
|| !expansion
)
2128 tree
= isl_schedule_tree_copy(node
->tree
);
2129 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
2130 contraction
, expansion
);
2131 return isl_schedule_node_graft_tree(node
, tree
);
2133 isl_schedule_node_free(node
);
2134 isl_union_pw_multi_aff_free(contraction
);
2135 isl_union_map_free(expansion
);
2139 /* Return the extension of the extension node "node".
2141 __isl_give isl_union_map
*isl_schedule_node_extension_get_extension(
2142 __isl_keep isl_schedule_node
*node
)
2147 return isl_schedule_tree_extension_get_extension(node
->tree
);
2150 /* Replace the extension of extension node "node" by "extension".
2152 __isl_give isl_schedule_node
*isl_schedule_node_extension_set_extension(
2153 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
2155 isl_schedule_tree
*tree
;
2157 if (!node
|| !extension
)
2160 tree
= isl_schedule_tree_copy(node
->tree
);
2161 tree
= isl_schedule_tree_extension_set_extension(tree
, extension
);
2162 return isl_schedule_node_graft_tree(node
, tree
);
2164 isl_schedule_node_free(node
);
2165 isl_union_map_free(extension
);
2169 /* Return the filter of the filter node "node".
2171 __isl_give isl_union_set
*isl_schedule_node_filter_get_filter(
2172 __isl_keep isl_schedule_node
*node
)
2177 return isl_schedule_tree_filter_get_filter(node
->tree
);
2180 /* Replace the filter of filter node "node" by "filter".
2182 __isl_give isl_schedule_node
*isl_schedule_node_filter_set_filter(
2183 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2185 isl_schedule_tree
*tree
;
2187 if (!node
|| !filter
)
2190 tree
= isl_schedule_tree_copy(node
->tree
);
2191 tree
= isl_schedule_tree_filter_set_filter(tree
, filter
);
2192 return isl_schedule_node_graft_tree(node
, tree
);
2194 isl_schedule_node_free(node
);
2195 isl_union_set_free(filter
);
2199 /* Intersect the filter of filter node "node" with "filter".
2201 * If the filter of the node is already a subset of "filter",
2202 * then leave the node unchanged.
2204 __isl_give isl_schedule_node
*isl_schedule_node_filter_intersect_filter(
2205 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2207 isl_union_set
*node_filter
= NULL
;
2210 if (!node
|| !filter
)
2213 node_filter
= isl_schedule_node_filter_get_filter(node
);
2214 subset
= isl_union_set_is_subset(node_filter
, filter
);
2218 isl_union_set_free(node_filter
);
2219 isl_union_set_free(filter
);
2222 node_filter
= isl_union_set_intersect(node_filter
, filter
);
2223 node
= isl_schedule_node_filter_set_filter(node
, node_filter
);
2226 isl_schedule_node_free(node
);
2227 isl_union_set_free(node_filter
);
2228 isl_union_set_free(filter
);
2232 /* Return the guard of the guard node "node".
2234 __isl_give isl_set
*isl_schedule_node_guard_get_guard(
2235 __isl_keep isl_schedule_node
*node
)
2240 return isl_schedule_tree_guard_get_guard(node
->tree
);
2243 /* Return the mark identifier of the mark node "node".
2245 __isl_give isl_id
*isl_schedule_node_mark_get_id(
2246 __isl_keep isl_schedule_node
*node
)
2251 return isl_schedule_tree_mark_get_id(node
->tree
);
2254 /* Replace the child at position "pos" of the sequence node "node"
2255 * by the children of sequence root node of "tree".
2257 __isl_give isl_schedule_node
*isl_schedule_node_sequence_splice(
2258 __isl_take isl_schedule_node
*node
, int pos
,
2259 __isl_take isl_schedule_tree
*tree
)
2261 isl_schedule_tree
*node_tree
;
2265 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2266 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2267 "not a sequence node", goto error
);
2268 if (isl_schedule_tree_get_type(tree
) != isl_schedule_node_sequence
)
2269 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2270 "not a sequence node", goto error
);
2271 node_tree
= isl_schedule_node_get_tree(node
);
2272 node_tree
= isl_schedule_tree_sequence_splice(node_tree
, pos
, tree
);
2273 node
= isl_schedule_node_graft_tree(node
, node_tree
);
2277 isl_schedule_node_free(node
);
2278 isl_schedule_tree_free(tree
);
2282 /* Given a sequence node "node", with a child at position "pos" that
2283 * is also a sequence node, attach the children of that node directly
2284 * as children of "node" at that position, replacing the original child.
2286 * The filters of these children are intersected with the filter
2287 * of the child at position "pos".
2289 __isl_give isl_schedule_node
*isl_schedule_node_sequence_splice_child(
2290 __isl_take isl_schedule_node
*node
, int pos
)
2294 isl_union_set
*filter
;
2295 isl_schedule_node
*child
;
2296 isl_schedule_tree
*tree
;
2300 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2301 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2302 "not a sequence node",
2303 return isl_schedule_node_free(node
));
2304 node
= isl_schedule_node_child(node
, pos
);
2305 node
= isl_schedule_node_child(node
, 0);
2306 if (isl_schedule_node_get_type(node
) != isl_schedule_node_sequence
)
2307 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2308 "not a sequence node",
2309 return isl_schedule_node_free(node
));
2310 n
= isl_schedule_node_n_children(node
);
2312 return isl_schedule_node_free(node
);
2313 child
= isl_schedule_node_copy(node
);
2314 node
= isl_schedule_node_parent(node
);
2315 filter
= isl_schedule_node_filter_get_filter(node
);
2316 for (i
= 0; i
< n
; ++i
) {
2317 child
= isl_schedule_node_child(child
, i
);
2318 child
= isl_schedule_node_filter_intersect_filter(child
,
2319 isl_union_set_copy(filter
));
2320 child
= isl_schedule_node_parent(child
);
2322 isl_union_set_free(filter
);
2323 tree
= isl_schedule_node_get_tree(child
);
2324 isl_schedule_node_free(child
);
2325 node
= isl_schedule_node_parent(node
);
2326 node
= isl_schedule_node_sequence_splice(node
, pos
, tree
);
2331 /* Update the ancestors of "node" to point to the tree that "node"
2333 * That is, replace the child in the original parent that corresponds
2334 * to the current tree position by node->tree and continue updating
2335 * the ancestors in the same way until the root is reached.
2337 * If "fn" is not NULL, then it is called on each ancestor as we move up
2338 * the tree so that it can modify the ancestor before it is added
2339 * to the list of ancestors of the modified node.
2340 * The additional "pos" argument records the position
2341 * of the "tree" argument in the original schedule tree.
2343 * If "node" originally points to a leaf of the schedule tree, then make sure
2344 * that in the end it points to a leaf in the updated schedule tree.
2346 static __isl_give isl_schedule_node
*update_ancestors(
2347 __isl_take isl_schedule_node
*node
,
2348 __isl_give isl_schedule_tree
*(*fn
)(__isl_take isl_schedule_tree
*tree
,
2349 __isl_keep isl_schedule_node
*pos
, void *user
), void *user
)
2354 isl_schedule_tree
*tree
;
2355 isl_schedule_node
*pos
= NULL
;
2358 pos
= isl_schedule_node_copy(node
);
2360 node
= isl_schedule_node_cow(node
);
2362 return isl_schedule_node_free(pos
);
2364 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
2366 return isl_schedule_node_free(pos
);
2367 tree
= isl_schedule_tree_copy(node
->tree
);
2369 for (i
= n
- 1; i
>= 0; --i
) {
2370 isl_schedule_tree
*parent
;
2372 parent
= isl_schedule_tree_list_get_schedule_tree(
2373 node
->ancestors
, i
);
2374 parent
= isl_schedule_tree_replace_child(parent
,
2375 node
->child_pos
[i
], tree
);
2377 pos
= isl_schedule_node_parent(pos
);
2378 parent
= fn(parent
, pos
, user
);
2380 node
->ancestors
= isl_schedule_tree_list_set_schedule_tree(
2381 node
->ancestors
, i
, isl_schedule_tree_copy(parent
));
2387 isl_schedule_node_free(pos
);
2389 is_leaf
= isl_schedule_tree_is_leaf(node
->tree
);
2390 node
->schedule
= isl_schedule_set_root(node
->schedule
, tree
);
2392 isl_schedule_tree_free(node
->tree
);
2393 node
->tree
= isl_schedule_node_get_leaf(node
);
2396 if (!node
->schedule
|| !node
->ancestors
)
2397 return isl_schedule_node_free(node
);
2402 /* Replace the subtree that "pos" points to by "tree", updating
2403 * the ancestors to maintain a consistent state.
2405 __isl_give isl_schedule_node
*isl_schedule_node_graft_tree(
2406 __isl_take isl_schedule_node
*pos
, __isl_take isl_schedule_tree
*tree
)
2410 if (pos
->tree
== tree
) {
2411 isl_schedule_tree_free(tree
);
2415 pos
= isl_schedule_node_cow(pos
);
2419 isl_schedule_tree_free(pos
->tree
);
2422 return update_ancestors(pos
, NULL
, NULL
);
2424 isl_schedule_node_free(pos
);
2425 isl_schedule_tree_free(tree
);
2429 /* Make sure we can insert a node between "node" and its parent.
2430 * Return -1 on error, reporting the reason why we cannot insert a node.
2432 static int check_insert(__isl_keep isl_schedule_node
*node
)
2435 enum isl_schedule_node_type type
;
2437 has_parent
= isl_schedule_node_has_parent(node
);
2441 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2442 "cannot insert node outside of root", return -1);
2444 type
= isl_schedule_node_get_parent_type(node
);
2445 if (type
== isl_schedule_node_error
)
2447 if (type
== isl_schedule_node_set
|| type
== isl_schedule_node_sequence
)
2448 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2449 "cannot insert node between set or sequence node "
2450 "and its filter children", return -1);
2455 /* Insert a band node with partial schedule "mupa" between "node" and
2457 * Return a pointer to the new band node.
2459 * If any of the nodes in the subtree rooted at "node" depend on
2460 * the set of outer band nodes then we refuse to insert the band node.
2462 __isl_give isl_schedule_node
*isl_schedule_node_insert_partial_schedule(
2463 __isl_take isl_schedule_node
*node
,
2464 __isl_take isl_multi_union_pw_aff
*mupa
)
2467 isl_schedule_band
*band
;
2468 isl_schedule_tree
*tree
;
2470 if (check_insert(node
) < 0)
2471 node
= isl_schedule_node_free(node
);
2472 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2476 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2477 "cannot insert band node in anchored subtree",
2480 tree
= isl_schedule_node_get_tree(node
);
2481 band
= isl_schedule_band_from_multi_union_pw_aff(mupa
);
2482 tree
= isl_schedule_tree_insert_band(tree
, band
);
2483 node
= isl_schedule_node_graft_tree(node
, tree
);
2487 isl_schedule_node_free(node
);
2488 isl_multi_union_pw_aff_free(mupa
);
2492 /* Insert a context node with context "context" between "node" and its parent.
2493 * Return a pointer to the new context node.
2495 __isl_give isl_schedule_node
*isl_schedule_node_insert_context(
2496 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
2498 isl_schedule_tree
*tree
;
2500 if (check_insert(node
) < 0)
2501 node
= isl_schedule_node_free(node
);
2503 tree
= isl_schedule_node_get_tree(node
);
2504 tree
= isl_schedule_tree_insert_context(tree
, context
);
2505 node
= isl_schedule_node_graft_tree(node
, tree
);
2510 /* Insert an expansion node with the given "contraction" and "expansion"
2511 * between "node" and its parent.
2512 * Return a pointer to the new expansion node.
2514 * Typically the domain and range spaces of the expansion are different.
2515 * This means that only one of them can refer to the current domain space
2516 * in a consistent tree. It is up to the caller to ensure that the tree
2517 * returns to a consistent state.
2519 __isl_give isl_schedule_node
*isl_schedule_node_insert_expansion(
2520 __isl_take isl_schedule_node
*node
,
2521 __isl_take isl_union_pw_multi_aff
*contraction
,
2522 __isl_take isl_union_map
*expansion
)
2524 isl_schedule_tree
*tree
;
2526 if (check_insert(node
) < 0)
2527 node
= isl_schedule_node_free(node
);
2529 tree
= isl_schedule_node_get_tree(node
);
2530 tree
= isl_schedule_tree_insert_expansion(tree
, contraction
, expansion
);
2531 node
= isl_schedule_node_graft_tree(node
, tree
);
2536 /* Insert an extension node with extension "extension" between "node" and
2538 * Return a pointer to the new extension node.
2540 __isl_give isl_schedule_node
*isl_schedule_node_insert_extension(
2541 __isl_take isl_schedule_node
*node
,
2542 __isl_take isl_union_map
*extension
)
2544 isl_schedule_tree
*tree
;
2546 tree
= isl_schedule_node_get_tree(node
);
2547 tree
= isl_schedule_tree_insert_extension(tree
, extension
);
2548 node
= isl_schedule_node_graft_tree(node
, tree
);
2553 /* Insert a filter node with filter "filter" between "node" and its parent.
2554 * Return a pointer to the new filter node.
2556 __isl_give isl_schedule_node
*isl_schedule_node_insert_filter(
2557 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
2559 isl_schedule_tree
*tree
;
2561 if (check_insert(node
) < 0)
2562 node
= isl_schedule_node_free(node
);
2564 tree
= isl_schedule_node_get_tree(node
);
2565 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2566 node
= isl_schedule_node_graft_tree(node
, tree
);
2571 /* Insert a guard node with guard "guard" between "node" and its parent.
2572 * Return a pointer to the new guard node.
2574 __isl_give isl_schedule_node
*isl_schedule_node_insert_guard(
2575 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*guard
)
2577 isl_schedule_tree
*tree
;
2579 if (check_insert(node
) < 0)
2580 node
= isl_schedule_node_free(node
);
2582 tree
= isl_schedule_node_get_tree(node
);
2583 tree
= isl_schedule_tree_insert_guard(tree
, guard
);
2584 node
= isl_schedule_node_graft_tree(node
, tree
);
2589 /* Insert a mark node with mark identifier "mark" between "node" and
2591 * Return a pointer to the new mark node.
2593 __isl_give isl_schedule_node
*isl_schedule_node_insert_mark(
2594 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*mark
)
2596 isl_schedule_tree
*tree
;
2598 if (check_insert(node
) < 0)
2599 node
= isl_schedule_node_free(node
);
2601 tree
= isl_schedule_node_get_tree(node
);
2602 tree
= isl_schedule_tree_insert_mark(tree
, mark
);
2603 node
= isl_schedule_node_graft_tree(node
, tree
);
2608 /* Attach the current subtree of "node" to a sequence of filter tree nodes
2609 * with filters described by "filters", attach this sequence
2610 * of filter tree nodes as children to a new tree of type "type" and
2611 * replace the original subtree of "node" by this new tree.
2612 * Each copy of the original subtree is simplified with respect
2613 * to the corresponding filter.
2615 static __isl_give isl_schedule_node
*isl_schedule_node_insert_children(
2616 __isl_take isl_schedule_node
*node
,
2617 enum isl_schedule_node_type type
,
2618 __isl_take isl_union_set_list
*filters
)
2623 isl_schedule_tree
*tree
;
2624 isl_schedule_tree_list
*list
;
2626 if (check_insert(node
) < 0)
2627 node
= isl_schedule_node_free(node
);
2629 n
= isl_union_set_list_n_union_set(filters
);
2633 ctx
= isl_schedule_node_get_ctx(node
);
2634 list
= isl_schedule_tree_list_alloc(ctx
, n
);
2635 for (i
= 0; i
< n
; ++i
) {
2636 isl_schedule_node
*node_i
;
2637 isl_schedule_tree
*tree
;
2638 isl_union_set
*filter
;
2640 filter
= isl_union_set_list_get_union_set(filters
, i
);
2641 node_i
= isl_schedule_node_copy(node
);
2642 node_i
= isl_schedule_node_gist(node_i
,
2643 isl_union_set_copy(filter
));
2644 tree
= isl_schedule_node_get_tree(node_i
);
2645 isl_schedule_node_free(node_i
);
2646 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
2647 list
= isl_schedule_tree_list_add(list
, tree
);
2649 tree
= isl_schedule_tree_from_children(type
, list
);
2650 node
= isl_schedule_node_graft_tree(node
, tree
);
2652 isl_union_set_list_free(filters
);
2655 isl_union_set_list_free(filters
);
2656 isl_schedule_node_free(node
);
2660 /* Insert a sequence node with child filters "filters" between "node" and
2661 * its parent. That is, the tree that "node" points to is attached
2662 * to each of the child nodes of the filter nodes.
2663 * Return a pointer to the new sequence node.
2665 __isl_give isl_schedule_node
*isl_schedule_node_insert_sequence(
2666 __isl_take isl_schedule_node
*node
,
2667 __isl_take isl_union_set_list
*filters
)
2669 return isl_schedule_node_insert_children(node
,
2670 isl_schedule_node_sequence
, filters
);
2673 /* Insert a set node with child filters "filters" between "node" and
2674 * its parent. That is, the tree that "node" points to is attached
2675 * to each of the child nodes of the filter nodes.
2676 * Return a pointer to the new set node.
2678 __isl_give isl_schedule_node
*isl_schedule_node_insert_set(
2679 __isl_take isl_schedule_node
*node
,
2680 __isl_take isl_union_set_list
*filters
)
2682 return isl_schedule_node_insert_children(node
,
2683 isl_schedule_node_set
, filters
);
2686 /* Remove "node" from its schedule tree and return a pointer
2687 * to the leaf at the same position in the updated schedule tree.
2689 * It is not allowed to remove the root of a schedule tree or
2690 * a child of a set or sequence node.
2692 __isl_give isl_schedule_node
*isl_schedule_node_cut(
2693 __isl_take isl_schedule_node
*node
)
2695 isl_schedule_tree
*leaf
;
2696 enum isl_schedule_node_type parent_type
;
2700 if (!isl_schedule_node_has_parent(node
))
2701 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2702 "cannot cut root", return isl_schedule_node_free(node
));
2704 parent_type
= isl_schedule_node_get_parent_type(node
);
2705 if (parent_type
== isl_schedule_node_set
||
2706 parent_type
== isl_schedule_node_sequence
)
2707 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2708 "cannot cut child of set or sequence",
2709 return isl_schedule_node_free(node
));
2711 leaf
= isl_schedule_node_get_leaf(node
);
2712 return isl_schedule_node_graft_tree(node
, leaf
);
2715 /* Remove a single node from the schedule tree, attaching the child
2716 * of "node" directly to its parent.
2717 * Return a pointer to this former child or to the leaf the position
2718 * of the original node if there was no child.
2719 * It is not allowed to remove the root of a schedule tree,
2720 * a set or sequence node, a child of a set or sequence node or
2721 * a band node with an anchored subtree.
2723 __isl_give isl_schedule_node
*isl_schedule_node_delete(
2724 __isl_take isl_schedule_node
*node
)
2727 isl_schedule_tree
*tree
;
2728 enum isl_schedule_node_type type
;
2730 depth
= isl_schedule_node_get_tree_depth(node
);
2731 n
= isl_schedule_node_n_children(node
);
2732 if (depth
< 0 || n
< 0)
2733 return isl_schedule_node_free(node
);
2736 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2737 "cannot delete root node",
2738 return isl_schedule_node_free(node
));
2740 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2741 "can only delete node with a single child",
2742 return isl_schedule_node_free(node
));
2743 type
= isl_schedule_node_get_parent_type(node
);
2744 if (type
== isl_schedule_node_sequence
|| type
== isl_schedule_node_set
)
2745 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
2746 "cannot delete child of set or sequence",
2747 return isl_schedule_node_free(node
));
2748 if (isl_schedule_node_get_type(node
) == isl_schedule_node_band
) {
2751 anchored
= isl_schedule_node_is_subtree_anchored(node
);
2753 return isl_schedule_node_free(node
);
2755 isl_die(isl_schedule_node_get_ctx(node
),
2757 "cannot delete band node with anchored subtree",
2758 return isl_schedule_node_free(node
));
2761 tree
= isl_schedule_node_get_tree(node
);
2762 if (!tree
|| isl_schedule_tree_has_children(tree
)) {
2763 tree
= isl_schedule_tree_child(tree
, 0);
2765 isl_schedule_tree_free(tree
);
2766 tree
= isl_schedule_node_get_leaf(node
);
2768 node
= isl_schedule_node_graft_tree(node
, tree
);
2773 /* Internal data structure for the group_ancestor callback.
2775 * If "finished" is set, then we no longer need to modify
2776 * any further ancestors.
2778 * "contraction" and "expansion" represent the expansion
2779 * that reflects the grouping.
2781 * "domain" contains the domain elements that reach the position
2782 * where the grouping is performed. That is, it is the range
2783 * of the resulting expansion.
2784 * "domain_universe" is the universe of "domain".
2785 * "group" is the set of group elements, i.e., the domain
2786 * of the resulting expansion.
2787 * "group_universe" is the universe of "group".
2789 * "sched" is the schedule for the group elements, in pratice
2790 * an identity mapping on "group_universe".
2791 * "dim" is the dimension of "sched".
2793 struct isl_schedule_group_data
{
2796 isl_union_map
*expansion
;
2797 isl_union_pw_multi_aff
*contraction
;
2799 isl_union_set
*domain
;
2800 isl_union_set
*domain_universe
;
2801 isl_union_set
*group
;
2802 isl_union_set
*group_universe
;
2805 isl_multi_aff
*sched
;
2808 /* Is domain covered by data->domain within data->domain_universe?
2810 static isl_bool
locally_covered_by_domain(__isl_keep isl_union_set
*domain
,
2811 struct isl_schedule_group_data
*data
)
2814 isl_union_set
*test
;
2816 test
= isl_union_set_copy(domain
);
2817 test
= isl_union_set_intersect(test
,
2818 isl_union_set_copy(data
->domain_universe
));
2819 is_subset
= isl_union_set_is_subset(test
, data
->domain
);
2820 isl_union_set_free(test
);
2825 /* Update the band tree root "tree" to refer to the group instances
2826 * in data->group rather than the original domain elements in data->domain.
2827 * "pos" is the position in the original schedule tree where the modified
2828 * "tree" will be attached.
2830 * Add the part of the identity schedule on the group instances data->sched
2831 * that corresponds to this band node to the band schedule.
2832 * If the domain elements that reach the node and that are part
2833 * of data->domain_universe are all elements of data->domain (and therefore
2834 * replaced by the group instances) then this data->domain_universe
2835 * is removed from the domain of the band schedule.
2837 static __isl_give isl_schedule_tree
*group_band(
2838 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2839 struct isl_schedule_group_data
*data
)
2841 isl_union_set
*domain
;
2843 isl_multi_union_pw_aff
*mupa
, *partial
;
2844 isl_bool is_covered
;
2849 domain
= isl_schedule_node_get_domain(pos
);
2850 is_covered
= locally_covered_by_domain(domain
, data
);
2851 if (is_covered
>= 0 && is_covered
) {
2852 domain
= isl_union_set_universe(domain
);
2853 domain
= isl_union_set_subtract(domain
,
2854 isl_union_set_copy(data
->domain_universe
));
2855 tree
= isl_schedule_tree_band_intersect_domain(tree
, domain
);
2857 isl_union_set_free(domain
);
2859 return isl_schedule_tree_free(tree
);
2860 depth
= isl_schedule_node_get_schedule_depth(pos
);
2861 n
= isl_schedule_tree_band_n_member(tree
);
2863 return isl_schedule_tree_free(tree
);
2864 ma
= isl_multi_aff_copy(data
->sched
);
2865 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, 0, depth
);
2866 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
, n
, data
->dim
- depth
- n
);
2867 mupa
= isl_multi_union_pw_aff_from_multi_aff(ma
);
2868 partial
= isl_schedule_tree_band_get_partial_schedule(tree
);
2869 has_id
= isl_multi_union_pw_aff_has_tuple_id(partial
, isl_dim_set
);
2871 partial
= isl_multi_union_pw_aff_free(partial
);
2872 } else if (has_id
) {
2874 id
= isl_multi_union_pw_aff_get_tuple_id(partial
, isl_dim_set
);
2875 mupa
= isl_multi_union_pw_aff_set_tuple_id(mupa
,
2878 partial
= isl_multi_union_pw_aff_union_add(partial
, mupa
);
2879 tree
= isl_schedule_tree_band_set_partial_schedule(tree
, partial
);
2884 /* Drop the parameters in "uset" that are not also in "space".
2885 * "n" is the number of parameters in "space".
2887 static __isl_give isl_union_set
*union_set_drop_extra_params(
2888 __isl_take isl_union_set
*uset
, __isl_keep isl_space
*space
, int n
)
2892 uset
= isl_union_set_align_params(uset
, isl_space_copy(space
));
2893 n2
= isl_union_set_dim(uset
, isl_dim_param
);
2895 return isl_union_set_free(uset
);
2896 uset
= isl_union_set_project_out(uset
, isl_dim_param
, n
, n2
- n
);
2901 /* Update the context tree root "tree" to refer to the group instances
2902 * in data->group rather than the original domain elements in data->domain.
2903 * "pos" is the position in the original schedule tree where the modified
2904 * "tree" will be attached.
2906 * We do not actually need to update "tree" since a context node only
2907 * refers to the schedule space. However, we may need to update "data"
2908 * to not refer to any parameters introduced by the context node.
2910 static __isl_give isl_schedule_tree
*group_context(
2911 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2912 struct isl_schedule_group_data
*data
)
2915 isl_union_set
*domain
;
2920 depth
= isl_schedule_node_get_tree_depth(pos
);
2922 return isl_schedule_tree_free(tree
);
2926 domain
= isl_schedule_node_get_universe_domain(pos
);
2927 space
= isl_union_set_get_space(domain
);
2928 isl_union_set_free(domain
);
2930 n1
= isl_space_dim(space
, isl_dim_param
);
2931 data
->expansion
= isl_union_map_align_params(data
->expansion
, space
);
2932 n2
= isl_union_map_dim(data
->expansion
, isl_dim_param
);
2934 if (n1
< 0 || n2
< 0)
2935 return isl_schedule_tree_free(tree
);
2939 involves
= isl_union_map_involves_dims(data
->expansion
,
2940 isl_dim_param
, n1
, n2
- n1
);
2942 return isl_schedule_tree_free(tree
);
2944 isl_die(isl_schedule_node_get_ctx(pos
), isl_error_invalid
,
2945 "grouping cannot only refer to global parameters",
2946 return isl_schedule_tree_free(tree
));
2948 data
->expansion
= isl_union_map_project_out(data
->expansion
,
2949 isl_dim_param
, n1
, n2
- n1
);
2950 space
= isl_union_map_get_space(data
->expansion
);
2952 data
->contraction
= isl_union_pw_multi_aff_align_params(
2953 data
->contraction
, isl_space_copy(space
));
2954 n2
= isl_union_pw_multi_aff_dim(data
->contraction
, isl_dim_param
);
2957 isl_union_pw_multi_aff_free(data
->contraction
);
2958 data
->contraction
= isl_union_pw_multi_aff_drop_dims(data
->contraction
,
2959 isl_dim_param
, n1
, n2
- n1
);
2961 data
->domain
= union_set_drop_extra_params(data
->domain
, space
, n1
);
2962 data
->domain_universe
=
2963 union_set_drop_extra_params(data
->domain_universe
, space
, n1
);
2964 data
->group
= union_set_drop_extra_params(data
->group
, space
, n1
);
2965 data
->group_universe
=
2966 union_set_drop_extra_params(data
->group_universe
, space
, n1
);
2968 data
->sched
= isl_multi_aff_align_params(data
->sched
,
2969 isl_space_copy(space
));
2970 n2
= isl_multi_aff_dim(data
->sched
, isl_dim_param
);
2972 data
->sched
= isl_multi_aff_free(data
->sched
);
2973 data
->sched
= isl_multi_aff_drop_dims(data
->sched
,
2974 isl_dim_param
, n1
, n2
- n1
);
2976 isl_space_free(space
);
2981 /* Update the domain tree root "tree" to refer to the group instances
2982 * in data->group rather than the original domain elements in data->domain.
2983 * "pos" is the position in the original schedule tree where the modified
2984 * "tree" will be attached.
2986 * We first double-check that all grouped domain elements are actually
2987 * part of the root domain and then replace those elements by the group
2990 static __isl_give isl_schedule_tree
*group_domain(
2991 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
2992 struct isl_schedule_group_data
*data
)
2994 isl_union_set
*domain
;
2997 domain
= isl_schedule_tree_domain_get_domain(tree
);
2998 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
2999 isl_union_set_free(domain
);
3001 return isl_schedule_tree_free(tree
);
3003 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
3004 "grouped domain should be part of outer domain",
3005 return isl_schedule_tree_free(tree
));
3006 domain
= isl_schedule_tree_domain_get_domain(tree
);
3007 domain
= isl_union_set_subtract(domain
,
3008 isl_union_set_copy(data
->domain
));
3009 domain
= isl_union_set_union(domain
, isl_union_set_copy(data
->group
));
3010 tree
= isl_schedule_tree_domain_set_domain(tree
, domain
);
3015 /* Update the expansion tree root "tree" to refer to the group instances
3016 * in data->group rather than the original domain elements in data->domain.
3017 * "pos" is the position in the original schedule tree where the modified
3018 * "tree" will be attached.
3020 * Let G_1 -> D_1 be the expansion of "tree" and G_2 -> D_2 the newly
3021 * introduced expansion in a descendant of "tree".
3022 * We first double-check that D_2 is a subset of D_1.
3023 * Then we remove D_2 from the range of G_1 -> D_1 and add the mapping
3024 * G_1 -> D_1 . D_2 -> G_2.
3025 * Simmilarly, we restrict the domain of the contraction to the universe
3026 * of the range of the updated expansion and add G_2 -> D_2 . D_1 -> G_1,
3027 * attempting to remove the domain constraints of this additional part.
3029 static __isl_give isl_schedule_tree
*group_expansion(
3030 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
3031 struct isl_schedule_group_data
*data
)
3033 isl_union_set
*domain
;
3034 isl_union_map
*expansion
, *umap
;
3035 isl_union_pw_multi_aff
*contraction
, *upma
;
3038 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
3039 domain
= isl_union_map_range(expansion
);
3040 is_subset
= isl_union_set_is_subset(data
->domain
, domain
);
3041 isl_union_set_free(domain
);
3043 return isl_schedule_tree_free(tree
);
3045 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_internal
,
3046 "grouped domain should be part "
3047 "of outer expansion domain",
3048 return isl_schedule_tree_free(tree
));
3049 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
3050 umap
= isl_union_map_from_union_pw_multi_aff(
3051 isl_union_pw_multi_aff_copy(data
->contraction
));
3052 umap
= isl_union_map_apply_range(expansion
, umap
);
3053 expansion
= isl_schedule_tree_expansion_get_expansion(tree
);
3054 expansion
= isl_union_map_subtract_range(expansion
,
3055 isl_union_set_copy(data
->domain
));
3056 expansion
= isl_union_map_union(expansion
, umap
);
3057 umap
= isl_union_map_universe(isl_union_map_copy(expansion
));
3058 domain
= isl_union_map_range(umap
);
3059 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
3060 umap
= isl_union_map_from_union_pw_multi_aff(contraction
);
3061 umap
= isl_union_map_apply_range(isl_union_map_copy(data
->expansion
),
3063 upma
= isl_union_pw_multi_aff_from_union_map(umap
);
3064 contraction
= isl_schedule_tree_expansion_get_contraction(tree
);
3065 contraction
= isl_union_pw_multi_aff_intersect_domain(contraction
,
3067 domain
= isl_union_pw_multi_aff_domain(
3068 isl_union_pw_multi_aff_copy(upma
));
3069 upma
= isl_union_pw_multi_aff_gist(upma
, domain
);
3070 contraction
= isl_union_pw_multi_aff_union_add(contraction
, upma
);
3071 tree
= isl_schedule_tree_expansion_set_contraction_and_expansion(tree
,
3072 contraction
, expansion
);
3077 /* Update the tree root "tree" to refer to the group instances
3078 * in data->group rather than the original domain elements in data->domain.
3079 * "pos" is the position in the original schedule tree where the modified
3080 * "tree" will be attached.
3082 * If we have come across a domain or expansion node before (data->finished
3083 * is set), then we no longer need perform any modifications.
3085 * If "tree" is a filter, then we add data->group_universe to the filter.
3086 * We also remove data->domain_universe from the filter if all the domain
3087 * elements in this universe that reach the filter node are part of
3088 * the elements that are being grouped by data->expansion.
3089 * If "tree" is a band, domain or expansion, then it is handled
3090 * in a separate function.
3092 static __isl_give isl_schedule_tree
*group_ancestor(
3093 __isl_take isl_schedule_tree
*tree
, __isl_keep isl_schedule_node
*pos
,
3096 struct isl_schedule_group_data
*data
= user
;
3097 isl_union_set
*domain
;
3098 isl_bool is_covered
;
3101 return isl_schedule_tree_free(tree
);
3106 switch (isl_schedule_tree_get_type(tree
)) {
3107 case isl_schedule_node_error
:
3108 return isl_schedule_tree_free(tree
);
3109 case isl_schedule_node_extension
:
3110 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_unsupported
,
3111 "grouping not allowed in extended tree",
3112 return isl_schedule_tree_free(tree
));
3113 case isl_schedule_node_band
:
3114 tree
= group_band(tree
, pos
, data
);
3116 case isl_schedule_node_context
:
3117 tree
= group_context(tree
, pos
, data
);
3119 case isl_schedule_node_domain
:
3120 tree
= group_domain(tree
, pos
, data
);
3123 case isl_schedule_node_filter
:
3124 domain
= isl_schedule_node_get_domain(pos
);
3125 is_covered
= locally_covered_by_domain(domain
, data
);
3126 isl_union_set_free(domain
);
3128 return isl_schedule_tree_free(tree
);
3129 domain
= isl_schedule_tree_filter_get_filter(tree
);
3131 domain
= isl_union_set_subtract(domain
,
3132 isl_union_set_copy(data
->domain_universe
));
3133 domain
= isl_union_set_union(domain
,
3134 isl_union_set_copy(data
->group_universe
));
3135 tree
= isl_schedule_tree_filter_set_filter(tree
, domain
);
3137 case isl_schedule_node_expansion
:
3138 tree
= group_expansion(tree
, pos
, data
);
3141 case isl_schedule_node_leaf
:
3142 case isl_schedule_node_guard
:
3143 case isl_schedule_node_mark
:
3144 case isl_schedule_node_sequence
:
3145 case isl_schedule_node_set
:
3152 /* Group the domain elements that reach "node" into instances
3153 * of a single statement with identifier "group_id".
3154 * In particular, group the domain elements according to their
3157 * That is, introduce an expansion node with as contraction
3158 * the prefix schedule (with the target space replaced by "group_id")
3159 * and as expansion the inverse of this contraction (with its range
3160 * intersected with the domain elements that reach "node").
3161 * The outer nodes are then modified to refer to the group instances
3162 * instead of the original domain elements.
3164 * No instance of "group_id" is allowed to reach "node" prior
3166 * No ancestor of "node" is allowed to be an extension node.
3168 * Return a pointer to original node in tree, i.e., the child
3169 * of the newly introduced expansion node.
3171 __isl_give isl_schedule_node
*isl_schedule_node_group(
3172 __isl_take isl_schedule_node
*node
, __isl_take isl_id
*group_id
)
3174 struct isl_schedule_group_data data
= { 0 };
3176 isl_union_set
*domain
;
3177 isl_union_pw_multi_aff
*contraction
;
3178 isl_union_map
*expansion
;
3182 depth
= isl_schedule_node_get_schedule_depth(node
);
3183 if (depth
< 0 || !group_id
)
3185 if (check_insert(node
) < 0)
3188 domain
= isl_schedule_node_get_domain(node
);
3189 data
.domain
= isl_union_set_copy(domain
);
3190 data
.domain_universe
= isl_union_set_copy(domain
);
3191 data
.domain_universe
= isl_union_set_universe(data
.domain_universe
);
3194 if (data
.dim
== 0) {
3197 isl_union_set
*group
;
3198 isl_union_map
*univ
;
3200 ctx
= isl_schedule_node_get_ctx(node
);
3201 space
= isl_space_set_alloc(ctx
, 0, 0);
3202 space
= isl_space_set_tuple_id(space
, isl_dim_set
, group_id
);
3203 set
= isl_set_universe(isl_space_copy(space
));
3204 group
= isl_union_set_from_set(set
);
3205 expansion
= isl_union_map_from_domain_and_range(domain
, group
);
3206 univ
= isl_union_map_universe(isl_union_map_copy(expansion
));
3207 contraction
= isl_union_pw_multi_aff_from_union_map(univ
);
3208 expansion
= isl_union_map_reverse(expansion
);
3210 isl_multi_union_pw_aff
*prefix
;
3211 isl_union_set
*univ
;
3214 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node
);
3215 prefix
= isl_multi_union_pw_aff_set_tuple_id(prefix
,
3216 isl_dim_set
, group_id
);
3217 space
= isl_multi_union_pw_aff_get_space(prefix
);
3218 contraction
= isl_union_pw_multi_aff_from_multi_union_pw_aff(
3220 univ
= isl_union_set_universe(isl_union_set_copy(domain
));
3222 isl_union_pw_multi_aff_intersect_domain(contraction
, univ
);
3223 expansion
= isl_union_map_from_union_pw_multi_aff(
3224 isl_union_pw_multi_aff_copy(contraction
));
3225 expansion
= isl_union_map_reverse(expansion
);
3226 expansion
= isl_union_map_intersect_range(expansion
, domain
);
3228 space
= isl_space_map_from_set(space
);
3229 data
.sched
= isl_multi_aff_identity(space
);
3230 data
.group
= isl_union_map_domain(isl_union_map_copy(expansion
));
3231 data
.group
= isl_union_set_coalesce(data
.group
);
3232 data
.group_universe
= isl_union_set_copy(data
.group
);
3233 data
.group_universe
= isl_union_set_universe(data
.group_universe
);
3234 data
.expansion
= isl_union_map_copy(expansion
);
3235 data
.contraction
= isl_union_pw_multi_aff_copy(contraction
);
3236 node
= isl_schedule_node_insert_expansion(node
, contraction
, expansion
);
3238 disjoint
= isl_union_set_is_disjoint(data
.domain_universe
,
3239 data
.group_universe
);
3241 node
= update_ancestors(node
, &group_ancestor
, &data
);
3243 isl_union_set_free(data
.domain
);
3244 isl_union_set_free(data
.domain_universe
);
3245 isl_union_set_free(data
.group
);
3246 isl_union_set_free(data
.group_universe
);
3247 isl_multi_aff_free(data
.sched
);
3248 isl_union_map_free(data
.expansion
);
3249 isl_union_pw_multi_aff_free(data
.contraction
);
3251 node
= isl_schedule_node_child(node
, 0);
3253 if (!node
|| disjoint
< 0)
3254 return isl_schedule_node_free(node
);
3256 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
3257 "group instances already reach node",
3258 return isl_schedule_node_free(node
));
3262 isl_schedule_node_free(node
);
3263 isl_id_free(group_id
);
3267 /* Compute the gist of the given band node with respect to "context".
3269 __isl_give isl_schedule_node
*isl_schedule_node_band_gist(
3270 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3272 isl_schedule_tree
*tree
;
3274 tree
= isl_schedule_node_get_tree(node
);
3275 tree
= isl_schedule_tree_band_gist(tree
, context
);
3276 return isl_schedule_node_graft_tree(node
, tree
);
3279 /* Internal data structure for isl_schedule_node_gist.
3280 * "n_expansion" is the number of outer expansion nodes
3281 * with respect to the current position
3282 * "filters" contains an element for each outer filter, expansion or
3283 * extension node with respect to the current position, each representing
3284 * the intersection of the previous element and the filter on the filter node
3285 * or the expansion/extension of the previous element.
3286 * The first element in the original context passed to isl_schedule_node_gist.
3288 struct isl_node_gist_data
{
3290 isl_union_set_list
*filters
;
3293 /* Enter the expansion node "node" during a isl_schedule_node_gist traversal.
3295 * In particular, add an extra element to data->filters containing
3296 * the expansion of the previous element and replace the expansion
3297 * and contraction on "node" by the gist with respect to these filters.
3298 * Also keep track of the fact that we have entered another expansion.
3300 static __isl_give isl_schedule_node
*gist_enter_expansion(
3301 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3304 isl_union_set
*inner
;
3305 isl_union_map
*expansion
;
3306 isl_union_pw_multi_aff
*contraction
;
3308 data
->n_expansion
++;
3310 n
= isl_union_set_list_n_union_set(data
->filters
);
3312 return isl_schedule_node_free(node
);
3313 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3314 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3315 inner
= isl_union_set_apply(inner
, expansion
);
3317 contraction
= isl_schedule_node_expansion_get_contraction(node
);
3318 contraction
= isl_union_pw_multi_aff_gist(contraction
,
3319 isl_union_set_copy(inner
));
3321 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
3323 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3324 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3325 expansion
= isl_union_map_gist_domain(expansion
, inner
);
3326 node
= isl_schedule_node_expansion_set_contraction_and_expansion(node
,
3327 contraction
, expansion
);
3332 /* Leave the expansion node "node" during a isl_schedule_node_gist traversal.
3334 * In particular, remove the element in data->filters that was added by
3335 * gist_enter_expansion and decrement the number of outer expansions.
3337 * The expansion has already been simplified in gist_enter_expansion.
3338 * If this simplification results in an identity expansion, then
3339 * it is removed here.
3341 static __isl_give isl_schedule_node
*gist_leave_expansion(
3342 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3346 isl_union_map
*expansion
;
3348 expansion
= isl_schedule_node_expansion_get_expansion(node
);
3349 identity
= isl_union_map_is_identity(expansion
);
3350 isl_union_map_free(expansion
);
3353 node
= isl_schedule_node_free(node
);
3355 node
= isl_schedule_node_delete(node
);
3357 n
= isl_union_set_list_n_union_set(data
->filters
);
3359 return isl_schedule_node_free(node
);
3360 data
->filters
= isl_union_set_list_drop(data
->filters
, n
- 1, 1);
3362 data
->n_expansion
--;
3367 /* Enter the extension node "node" during a isl_schedule_node_gist traversal.
3369 * In particular, add an extra element to data->filters containing
3370 * the union of the previous element with the additional domain elements
3371 * introduced by the extension.
3373 static __isl_give isl_schedule_node
*gist_enter_extension(
3374 __isl_take isl_schedule_node
*node
, struct isl_node_gist_data
*data
)
3377 isl_union_set
*inner
, *extra
;
3378 isl_union_map
*extension
;
3380 n
= isl_union_set_list_n_union_set(data
->filters
);
3382 return isl_schedule_node_free(node
);
3383 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3384 extension
= isl_schedule_node_extension_get_extension(node
);
3385 extra
= isl_union_map_range(extension
);
3386 inner
= isl_union_set_union(inner
, extra
);
3388 data
->filters
= isl_union_set_list_add(data
->filters
, inner
);
3393 /* Can we finish gisting at this node?
3394 * That is, is the filter on the current filter node a subset of
3395 * the original context passed to isl_schedule_node_gist?
3396 * If we have gone through any expansions, then we cannot perform
3397 * this test since the current domain elements are incomparable
3398 * to the domain elements in the original context.
3400 static isl_bool
gist_done(__isl_keep isl_schedule_node
*node
,
3401 struct isl_node_gist_data
*data
)
3403 isl_union_set
*filter
, *outer
;
3406 if (data
->n_expansion
!= 0)
3407 return isl_bool_false
;
3409 filter
= isl_schedule_node_filter_get_filter(node
);
3410 outer
= isl_union_set_list_get_union_set(data
->filters
, 0);
3411 subset
= isl_union_set_is_subset(filter
, outer
);
3412 isl_union_set_free(outer
);
3413 isl_union_set_free(filter
);
3418 /* Callback for "traverse" to enter a node and to move
3419 * to the deepest initial subtree that should be traversed
3420 * by isl_schedule_node_gist.
3422 * The "filters" list is extended by one element each time
3423 * we come across a filter node by the result of intersecting
3424 * the last element in the list with the filter on the filter node.
3426 * If the filter on the current filter node is a subset of
3427 * the original context passed to isl_schedule_node_gist,
3428 * then there is no need to go into its subtree since it cannot
3429 * be further simplified by the context. The "filters" list is
3430 * still extended for consistency, but the actual value of the
3431 * added element is immaterial since it will not be used.
3433 * Otherwise, the filter on the current filter node is replaced by
3434 * the gist of the original filter with respect to the intersection
3435 * of the original context with the intermediate filters.
3437 * If the new element in the "filters" list is empty, then no elements
3438 * can reach the descendants of the current filter node. The subtree
3439 * underneath the filter node is therefore removed.
3441 * Each expansion node we come across is handled by
3442 * gist_enter_expansion.
3444 * Each extension node we come across is handled by
3445 * gist_enter_extension.
3447 static __isl_give isl_schedule_node
*gist_enter(
3448 __isl_take isl_schedule_node
*node
, void *user
)
3450 struct isl_node_gist_data
*data
= user
;
3453 isl_union_set
*filter
, *inner
;
3454 isl_bool done
, empty
;
3457 switch (isl_schedule_node_get_type(node
)) {
3458 case isl_schedule_node_error
:
3459 return isl_schedule_node_free(node
);
3460 case isl_schedule_node_expansion
:
3461 node
= gist_enter_expansion(node
, data
);
3463 case isl_schedule_node_extension
:
3464 node
= gist_enter_extension(node
, data
);
3466 case isl_schedule_node_band
:
3467 case isl_schedule_node_context
:
3468 case isl_schedule_node_domain
:
3469 case isl_schedule_node_guard
:
3470 case isl_schedule_node_leaf
:
3471 case isl_schedule_node_mark
:
3472 case isl_schedule_node_sequence
:
3473 case isl_schedule_node_set
:
3475 case isl_schedule_node_filter
:
3478 done
= gist_done(node
, data
);
3479 filter
= isl_schedule_node_filter_get_filter(node
);
3480 n
= isl_union_set_list_n_union_set(data
->filters
);
3481 if (n
< 0 || done
< 0 || done
) {
3482 data
->filters
= isl_union_set_list_add(data
->filters
,
3484 if (n
< 0 || done
< 0)
3485 return isl_schedule_node_free(node
);
3488 inner
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3489 filter
= isl_union_set_gist(filter
, isl_union_set_copy(inner
));
3490 node
= isl_schedule_node_filter_set_filter(node
,
3491 isl_union_set_copy(filter
));
3492 filter
= isl_union_set_intersect(filter
, inner
);
3493 empty
= isl_union_set_is_empty(filter
);
3494 data
->filters
= isl_union_set_list_add(data
->filters
, filter
);
3496 return isl_schedule_node_free(node
);
3499 node
= isl_schedule_node_child(node
, 0);
3500 node
= isl_schedule_node_cut(node
);
3501 node
= isl_schedule_node_parent(node
);
3503 } while (isl_schedule_node_has_children(node
) &&
3504 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3509 /* Callback for "traverse" to leave a node for isl_schedule_node_gist.
3511 * In particular, if the current node is a filter node, then we remove
3512 * the element on the "filters" list that was added when we entered
3513 * the node. There is no need to compute any gist here, since we
3514 * already did that when we entered the node.
3516 * Expansion nodes are handled by gist_leave_expansion.
3518 * If the current node is an extension, then remove the element
3519 * in data->filters that was added by gist_enter_extension.
3521 * If the current node is a band node, then we compute the gist of
3522 * the band node with respect to the intersection of the original context
3523 * and the intermediate filters.
3525 * If the current node is a sequence or set node, then some of
3526 * the filter children may have become empty and so they are removed.
3527 * If only one child is left, then the set or sequence node along with
3528 * the single remaining child filter is removed. The filter can be
3529 * removed because the filters on a sequence or set node are supposed
3530 * to partition the incoming domain instances.
3531 * In principle, it should then be impossible for there to be zero
3532 * remaining children, but should this happen, we replace the entire
3533 * subtree with an empty filter.
3535 static __isl_give isl_schedule_node
*gist_leave(
3536 __isl_take isl_schedule_node
*node
, void *user
)
3538 struct isl_node_gist_data
*data
= user
;
3539 isl_schedule_tree
*tree
;
3542 isl_union_set
*filter
;
3544 switch (isl_schedule_node_get_type(node
)) {
3545 case isl_schedule_node_error
:
3546 return isl_schedule_node_free(node
);
3547 case isl_schedule_node_expansion
:
3548 node
= gist_leave_expansion(node
, data
);
3550 case isl_schedule_node_extension
:
3551 case isl_schedule_node_filter
:
3552 n
= isl_union_set_list_n_union_set(data
->filters
);
3554 return isl_schedule_node_free(node
);
3555 data
->filters
= isl_union_set_list_drop(data
->filters
,
3558 case isl_schedule_node_band
:
3559 n
= isl_union_set_list_n_union_set(data
->filters
);
3561 return isl_schedule_node_free(node
);
3562 filter
= isl_union_set_list_get_union_set(data
->filters
, n
- 1);
3563 node
= isl_schedule_node_band_gist(node
, filter
);
3565 case isl_schedule_node_set
:
3566 case isl_schedule_node_sequence
:
3567 tree
= isl_schedule_node_get_tree(node
);
3568 n
= isl_schedule_tree_n_children(tree
);
3570 tree
= isl_schedule_tree_free(tree
);
3571 for (i
= n
- 1; i
>= 0; --i
) {
3572 isl_schedule_tree
*child
;
3573 isl_union_set
*filter
;
3576 child
= isl_schedule_tree_get_child(tree
, i
);
3577 filter
= isl_schedule_tree_filter_get_filter(child
);
3578 empty
= isl_union_set_is_empty(filter
);
3579 isl_union_set_free(filter
);
3580 isl_schedule_tree_free(child
);
3582 tree
= isl_schedule_tree_free(tree
);
3584 tree
= isl_schedule_tree_drop_child(tree
, i
);
3586 n
= isl_schedule_tree_n_children(tree
);
3588 tree
= isl_schedule_tree_free(tree
);
3589 node
= isl_schedule_node_graft_tree(node
, tree
);
3591 node
= isl_schedule_node_delete(node
);
3592 node
= isl_schedule_node_delete(node
);
3593 } else if (n
== 0) {
3597 isl_union_set_list_get_union_set(data
->filters
, 0);
3598 space
= isl_union_set_get_space(filter
);
3599 isl_union_set_free(filter
);
3600 filter
= isl_union_set_empty(space
);
3601 node
= isl_schedule_node_cut(node
);
3602 node
= isl_schedule_node_insert_filter(node
, filter
);
3605 case isl_schedule_node_context
:
3606 case isl_schedule_node_domain
:
3607 case isl_schedule_node_guard
:
3608 case isl_schedule_node_leaf
:
3609 case isl_schedule_node_mark
:
3616 /* Compute the gist of the subtree at "node" with respect to
3617 * the reaching domain elements in "context".
3618 * In particular, compute the gist of all band and filter nodes
3619 * in the subtree with respect to "context". Children of set or sequence
3620 * nodes that end up with an empty filter are removed completely.
3622 * We keep track of the intersection of "context" with all outer filters
3623 * of the current node within the subtree in the final element of "filters".
3624 * Initially, this list contains the single element "context" and it is
3625 * extended or shortened each time we enter or leave a filter node.
3627 __isl_give isl_schedule_node
*isl_schedule_node_gist(
3628 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*context
)
3630 struct isl_node_gist_data data
;
3632 data
.n_expansion
= 0;
3633 data
.filters
= isl_union_set_list_from_union_set(context
);
3634 node
= traverse(node
, &gist_enter
, &gist_leave
, &data
);
3635 isl_union_set_list_free(data
.filters
);
3639 /* Intersect the domain of domain node "node" with "domain".
3641 * If the domain of "node" is already a subset of "domain",
3642 * then nothing needs to be changed.
3644 * Otherwise, we replace the domain of the domain node by the intersection
3645 * and simplify the subtree rooted at "node" with respect to this intersection.
3647 __isl_give isl_schedule_node
*isl_schedule_node_domain_intersect_domain(
3648 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
)
3650 isl_schedule_tree
*tree
;
3651 isl_union_set
*uset
;
3654 if (!node
|| !domain
)
3657 uset
= isl_schedule_tree_domain_get_domain(node
->tree
);
3658 is_subset
= isl_union_set_is_subset(uset
, domain
);
3659 isl_union_set_free(uset
);
3663 isl_union_set_free(domain
);
3667 tree
= isl_schedule_tree_copy(node
->tree
);
3668 uset
= isl_schedule_tree_domain_get_domain(tree
);
3669 uset
= isl_union_set_intersect(uset
, domain
);
3670 tree
= isl_schedule_tree_domain_set_domain(tree
,
3671 isl_union_set_copy(uset
));
3672 node
= isl_schedule_node_graft_tree(node
, tree
);
3674 node
= isl_schedule_node_child(node
, 0);
3675 node
= isl_schedule_node_gist(node
, uset
);
3676 node
= isl_schedule_node_parent(node
);
3680 isl_schedule_node_free(node
);
3681 isl_union_set_free(domain
);
3685 /* Replace the domain of domain node "node" with the gist
3686 * of the original domain with respect to the parameter domain "context".
3688 __isl_give isl_schedule_node
*isl_schedule_node_domain_gist_params(
3689 __isl_take isl_schedule_node
*node
, __isl_take isl_set
*context
)
3691 isl_union_set
*domain
;
3692 isl_schedule_tree
*tree
;
3694 if (!node
|| !context
)
3697 tree
= isl_schedule_tree_copy(node
->tree
);
3698 domain
= isl_schedule_tree_domain_get_domain(node
->tree
);
3699 domain
= isl_union_set_gist_params(domain
, context
);
3700 tree
= isl_schedule_tree_domain_set_domain(tree
, domain
);
3701 node
= isl_schedule_node_graft_tree(node
, tree
);
3705 isl_schedule_node_free(node
);
3706 isl_set_free(context
);
3710 /* Internal data structure for isl_schedule_node_get_subtree_expansion.
3711 * "expansions" contains a list of accumulated expansions
3712 * for each outer expansion, set or sequence node. The first element
3713 * in the list is an identity mapping on the reaching domain elements.
3714 * "res" collects the results.
3716 struct isl_subtree_expansion_data
{
3717 isl_union_map_list
*expansions
;
3721 /* Callback for "traverse" to enter a node and to move
3722 * to the deepest initial subtree that should be traversed
3723 * by isl_schedule_node_get_subtree_expansion.
3725 * Whenever we come across an expansion node, the last element
3726 * of data->expansions is combined with the expansion
3727 * on the expansion node.
3729 * Whenever we come across a filter node that is the child
3730 * of a set or sequence node, data->expansions is extended
3731 * with a new element that restricts the previous element
3732 * to the elements selected by the filter.
3733 * The previous element can then be reused while backtracking.
3735 static __isl_give isl_schedule_node
*subtree_expansion_enter(
3736 __isl_take isl_schedule_node
*node
, void *user
)
3738 struct isl_subtree_expansion_data
*data
= user
;
3741 enum isl_schedule_node_type type
;
3742 isl_union_set
*filter
;
3743 isl_union_map
*inner
, *expansion
;
3746 switch (isl_schedule_node_get_type(node
)) {
3747 case isl_schedule_node_error
:
3748 return isl_schedule_node_free(node
);
3749 case isl_schedule_node_filter
:
3750 type
= isl_schedule_node_get_parent_type(node
);
3751 if (type
!= isl_schedule_node_set
&&
3752 type
!= isl_schedule_node_sequence
)
3754 filter
= isl_schedule_node_filter_get_filter(node
);
3755 n
= isl_union_map_list_n_union_map(data
->expansions
);
3758 isl_union_map_list_free(data
->expansions
);
3760 isl_union_map_list_get_union_map(data
->expansions
,
3762 inner
= isl_union_map_intersect_range(inner
, filter
);
3764 isl_union_map_list_add(data
->expansions
, inner
);
3766 case isl_schedule_node_expansion
:
3767 n
= isl_union_map_list_n_union_map(data
->expansions
);
3770 isl_union_map_list_free(data
->expansions
);
3772 isl_schedule_node_expansion_get_expansion(node
);
3774 isl_union_map_list_get_union_map(data
->expansions
,
3776 inner
= isl_union_map_apply_range(inner
, expansion
);
3778 isl_union_map_list_set_union_map(data
->expansions
,
3781 case isl_schedule_node_band
:
3782 case isl_schedule_node_context
:
3783 case isl_schedule_node_domain
:
3784 case isl_schedule_node_extension
:
3785 case isl_schedule_node_guard
:
3786 case isl_schedule_node_leaf
:
3787 case isl_schedule_node_mark
:
3788 case isl_schedule_node_sequence
:
3789 case isl_schedule_node_set
:
3792 } while (isl_schedule_node_has_children(node
) &&
3793 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3798 /* Callback for "traverse" to leave a node for
3799 * isl_schedule_node_get_subtree_expansion.
3801 * If we come across a filter node that is the child
3802 * of a set or sequence node, then we remove the element
3803 * of data->expansions that was added in subtree_expansion_enter.
3805 * If we reach a leaf node, then the accumulated expansion is
3806 * added to data->res.
3808 static __isl_give isl_schedule_node
*subtree_expansion_leave(
3809 __isl_take isl_schedule_node
*node
, void *user
)
3811 struct isl_subtree_expansion_data
*data
= user
;
3813 isl_union_map
*inner
;
3814 enum isl_schedule_node_type type
;
3816 switch (isl_schedule_node_get_type(node
)) {
3817 case isl_schedule_node_error
:
3818 return isl_schedule_node_free(node
);
3819 case isl_schedule_node_filter
:
3820 type
= isl_schedule_node_get_parent_type(node
);
3821 if (type
!= isl_schedule_node_set
&&
3822 type
!= isl_schedule_node_sequence
)
3824 n
= isl_union_map_list_n_union_map(data
->expansions
);
3827 isl_union_map_list_free(data
->expansions
);
3828 data
->expansions
= isl_union_map_list_drop(data
->expansions
,
3831 case isl_schedule_node_leaf
:
3832 n
= isl_union_map_list_n_union_map(data
->expansions
);
3835 isl_union_map_list_free(data
->expansions
);
3836 inner
= isl_union_map_list_get_union_map(data
->expansions
,
3838 data
->res
= isl_union_map_union(data
->res
, inner
);
3840 case isl_schedule_node_band
:
3841 case isl_schedule_node_context
:
3842 case isl_schedule_node_domain
:
3843 case isl_schedule_node_expansion
:
3844 case isl_schedule_node_extension
:
3845 case isl_schedule_node_guard
:
3846 case isl_schedule_node_mark
:
3847 case isl_schedule_node_sequence
:
3848 case isl_schedule_node_set
:
3855 /* Return a mapping from the domain elements that reach "node"
3856 * to the corresponding domain elements in the leaves of the subtree
3857 * rooted at "node" obtained by composing the intermediate expansions.
3859 * We start out with an identity mapping between the domain elements
3860 * that reach "node" and compose it with all the expansions
3861 * on a path from "node" to a leaf while traversing the subtree.
3862 * Within the children of an a sequence or set node, the
3863 * accumulated expansion is restricted to the elements selected
3864 * by the filter child.
3866 __isl_give isl_union_map
*isl_schedule_node_get_subtree_expansion(
3867 __isl_keep isl_schedule_node
*node
)
3869 struct isl_subtree_expansion_data data
;
3871 isl_union_set
*domain
;
3872 isl_union_map
*expansion
;
3877 domain
= isl_schedule_node_get_universe_domain(node
);
3878 space
= isl_union_set_get_space(domain
);
3879 expansion
= isl_union_set_identity(domain
);
3880 data
.res
= isl_union_map_empty(space
);
3881 data
.expansions
= isl_union_map_list_from_union_map(expansion
);
3883 node
= isl_schedule_node_copy(node
);
3884 node
= traverse(node
, &subtree_expansion_enter
,
3885 &subtree_expansion_leave
, &data
);
3887 data
.res
= isl_union_map_free(data
.res
);
3888 isl_schedule_node_free(node
);
3890 isl_union_map_list_free(data
.expansions
);
3895 /* Internal data structure for isl_schedule_node_get_subtree_contraction.
3896 * "contractions" contains a list of accumulated contractions
3897 * for each outer expansion, set or sequence node. The first element
3898 * in the list is an identity mapping on the reaching domain elements.
3899 * "res" collects the results.
3901 struct isl_subtree_contraction_data
{
3902 isl_union_pw_multi_aff_list
*contractions
;
3903 isl_union_pw_multi_aff
*res
;
3906 /* Callback for "traverse" to enter a node and to move
3907 * to the deepest initial subtree that should be traversed
3908 * by isl_schedule_node_get_subtree_contraction.
3910 * Whenever we come across an expansion node, the last element
3911 * of data->contractions is combined with the contraction
3912 * on the expansion node.
3914 * Whenever we come across a filter node that is the child
3915 * of a set or sequence node, data->contractions is extended
3916 * with a new element that restricts the previous element
3917 * to the elements selected by the filter.
3918 * The previous element can then be reused while backtracking.
3920 static __isl_give isl_schedule_node
*subtree_contraction_enter(
3921 __isl_take isl_schedule_node
*node
, void *user
)
3923 struct isl_subtree_contraction_data
*data
= user
;
3926 enum isl_schedule_node_type type
;
3927 isl_union_set
*filter
;
3928 isl_union_pw_multi_aff
*inner
, *contraction
;
3931 switch (isl_schedule_node_get_type(node
)) {
3932 case isl_schedule_node_error
:
3933 return isl_schedule_node_free(node
);
3934 case isl_schedule_node_filter
:
3935 type
= isl_schedule_node_get_parent_type(node
);
3936 if (type
!= isl_schedule_node_set
&&
3937 type
!= isl_schedule_node_sequence
)
3939 filter
= isl_schedule_node_filter_get_filter(node
);
3940 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3941 data
->contractions
);
3943 data
->contractions
=
3944 isl_union_pw_multi_aff_list_free(
3945 data
->contractions
);
3947 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3948 data
->contractions
, n
- 1);
3949 inner
= isl_union_pw_multi_aff_intersect_domain(inner
,
3951 data
->contractions
=
3952 isl_union_pw_multi_aff_list_add(data
->contractions
,
3955 case isl_schedule_node_expansion
:
3956 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3957 data
->contractions
);
3959 data
->contractions
=
3960 isl_union_pw_multi_aff_list_free(
3961 data
->contractions
);
3963 isl_schedule_node_expansion_get_contraction(node
);
3965 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3966 data
->contractions
, n
- 1);
3968 isl_union_pw_multi_aff_pullback_union_pw_multi_aff(
3969 inner
, contraction
);
3970 data
->contractions
=
3971 isl_union_pw_multi_aff_list_set_union_pw_multi_aff(
3972 data
->contractions
, n
- 1, inner
);
3974 case isl_schedule_node_band
:
3975 case isl_schedule_node_context
:
3976 case isl_schedule_node_domain
:
3977 case isl_schedule_node_extension
:
3978 case isl_schedule_node_guard
:
3979 case isl_schedule_node_leaf
:
3980 case isl_schedule_node_mark
:
3981 case isl_schedule_node_sequence
:
3982 case isl_schedule_node_set
:
3985 } while (isl_schedule_node_has_children(node
) &&
3986 (node
= isl_schedule_node_first_child(node
)) != NULL
);
3991 /* Callback for "traverse" to leave a node for
3992 * isl_schedule_node_get_subtree_contraction.
3994 * If we come across a filter node that is the child
3995 * of a set or sequence node, then we remove the element
3996 * of data->contractions that was added in subtree_contraction_enter.
3998 * If we reach a leaf node, then the accumulated contraction is
3999 * added to data->res.
4001 static __isl_give isl_schedule_node
*subtree_contraction_leave(
4002 __isl_take isl_schedule_node
*node
, void *user
)
4004 struct isl_subtree_contraction_data
*data
= user
;
4006 isl_union_pw_multi_aff
*inner
;
4007 enum isl_schedule_node_type type
;
4009 switch (isl_schedule_node_get_type(node
)) {
4010 case isl_schedule_node_error
:
4011 return isl_schedule_node_free(node
);
4012 case isl_schedule_node_filter
:
4013 type
= isl_schedule_node_get_parent_type(node
);
4014 if (type
!= isl_schedule_node_set
&&
4015 type
!= isl_schedule_node_sequence
)
4017 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
4018 data
->contractions
);
4020 data
->contractions
= isl_union_pw_multi_aff_list_free(
4021 data
->contractions
);
4022 data
->contractions
=
4023 isl_union_pw_multi_aff_list_drop(data
->contractions
,
4026 case isl_schedule_node_leaf
:
4027 n
= isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
4028 data
->contractions
);
4030 data
->contractions
= isl_union_pw_multi_aff_list_free(
4031 data
->contractions
);
4032 inner
= isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
4033 data
->contractions
, n
- 1);
4034 data
->res
= isl_union_pw_multi_aff_union_add(data
->res
, inner
);
4036 case isl_schedule_node_band
:
4037 case isl_schedule_node_context
:
4038 case isl_schedule_node_domain
:
4039 case isl_schedule_node_expansion
:
4040 case isl_schedule_node_extension
:
4041 case isl_schedule_node_guard
:
4042 case isl_schedule_node_mark
:
4043 case isl_schedule_node_sequence
:
4044 case isl_schedule_node_set
:
4051 /* Return a mapping from the domain elements in the leaves of the subtree
4052 * rooted at "node" to the corresponding domain elements that reach "node"
4053 * obtained by composing the intermediate contractions.
4055 * We start out with an identity mapping between the domain elements
4056 * that reach "node" and compose it with all the contractions
4057 * on a path from "node" to a leaf while traversing the subtree.
4058 * Within the children of an a sequence or set node, the
4059 * accumulated contraction is restricted to the elements selected
4060 * by the filter child.
4062 __isl_give isl_union_pw_multi_aff
*isl_schedule_node_get_subtree_contraction(
4063 __isl_keep isl_schedule_node
*node
)
4065 struct isl_subtree_contraction_data data
;
4067 isl_union_set
*domain
;
4068 isl_union_pw_multi_aff
*contraction
;
4073 domain
= isl_schedule_node_get_universe_domain(node
);
4074 space
= isl_union_set_get_space(domain
);
4075 contraction
= isl_union_set_identity_union_pw_multi_aff(domain
);
4076 data
.res
= isl_union_pw_multi_aff_empty(space
);
4078 isl_union_pw_multi_aff_list_from_union_pw_multi_aff(contraction
);
4080 node
= isl_schedule_node_copy(node
);
4081 node
= traverse(node
, &subtree_contraction_enter
,
4082 &subtree_contraction_leave
, &data
);
4084 data
.res
= isl_union_pw_multi_aff_free(data
.res
);
4085 isl_schedule_node_free(node
);
4087 isl_union_pw_multi_aff_list_free(data
.contractions
);
4092 /* Do the nearest "n" ancestors of "node" have the types given in "types"
4093 * (starting at the parent of "node")?
4095 static isl_bool
has_ancestors(__isl_keep isl_schedule_node
*node
,
4096 int n
, enum isl_schedule_node_type
*types
)
4099 isl_size n_ancestor
;
4102 return isl_bool_error
;
4104 n_ancestor
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
4106 return isl_bool_error
;
4108 return isl_bool_false
;
4110 for (i
= 0; i
< n
; ++i
) {
4111 isl_schedule_tree
*tree
;
4114 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
,
4115 n_ancestor
- 1 - i
);
4117 return isl_bool_error
;
4118 correct_type
= isl_schedule_tree_get_type(tree
) == types
[i
];
4119 isl_schedule_tree_free(tree
);
4121 return isl_bool_false
;
4124 return isl_bool_true
;
4127 /* Given a node "node" that appears in an extension (i.e., it is the child
4128 * of a filter in a sequence inside an extension node), are the spaces
4129 * of the extension specified by "extension" disjoint from those
4130 * of both the original extension and the domain elements that reach
4131 * that original extension?
4133 static int is_disjoint_extension(__isl_keep isl_schedule_node
*node
,
4134 __isl_keep isl_union_map
*extension
)
4137 isl_union_set
*domain
;
4140 node
= isl_schedule_node_copy(node
);
4141 node
= isl_schedule_node_parent(node
);
4142 node
= isl_schedule_node_parent(node
);
4143 node
= isl_schedule_node_parent(node
);
4144 old
= isl_schedule_node_extension_get_extension(node
);
4145 domain
= isl_schedule_node_get_universe_domain(node
);
4146 isl_schedule_node_free(node
);
4147 old
= isl_union_map_universe(old
);
4148 domain
= isl_union_set_union(domain
, isl_union_map_range(old
));
4149 extension
= isl_union_map_copy(extension
);
4150 extension
= isl_union_map_intersect_range(extension
, domain
);
4151 empty
= isl_union_map_is_empty(extension
);
4152 isl_union_map_free(extension
);
4157 /* Given a node "node" that is governed by an extension node, extend
4158 * that extension node with "extension".
4160 * In particular, "node" is the child of a filter in a sequence that
4161 * is in turn a child of an extension node. Extend that extension node
4164 * Return a pointer to the parent of the original node (i.e., a filter).
4166 static __isl_give isl_schedule_node
*extend_extension(
4167 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
4171 isl_union_map
*node_extension
;
4173 node
= isl_schedule_node_parent(node
);
4174 pos
= isl_schedule_node_get_child_position(node
);
4176 node
= isl_schedule_node_free(node
);
4177 node
= isl_schedule_node_parent(node
);
4178 node
= isl_schedule_node_parent(node
);
4179 node_extension
= isl_schedule_node_extension_get_extension(node
);
4180 disjoint
= isl_union_map_is_disjoint(extension
, node_extension
);
4181 extension
= isl_union_map_union(extension
, node_extension
);
4182 node
= isl_schedule_node_extension_set_extension(node
, extension
);
4183 node
= isl_schedule_node_child(node
, 0);
4184 node
= isl_schedule_node_child(node
, pos
);
4187 return isl_schedule_node_free(node
);
4191 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4192 "extension domain should be disjoint from earlier "
4193 "extensions", return isl_schedule_node_free(node
));
4198 /* Return the universe of "uset" if this universe is disjoint from "ref".
4199 * Otherwise, return "uset".
4201 * Also check if "uset" itself is disjoint from "ref", reporting
4202 * an error if it is not.
4204 static __isl_give isl_union_set
*replace_by_universe_if_disjoint(
4205 __isl_take isl_union_set
*uset
, __isl_keep isl_union_set
*ref
)
4208 isl_union_set
*universe
;
4210 disjoint
= isl_union_set_is_disjoint(uset
, ref
);
4212 return isl_union_set_free(uset
);
4214 isl_die(isl_union_set_get_ctx(uset
), isl_error_invalid
,
4215 "extension domain should be disjoint from "
4216 "current domain", return isl_union_set_free(uset
));
4218 universe
= isl_union_set_universe(isl_union_set_copy(uset
));
4219 disjoint
= isl_union_set_is_disjoint(universe
, ref
);
4220 if (disjoint
>= 0 && disjoint
) {
4221 isl_union_set_free(uset
);
4224 isl_union_set_free(universe
);
4227 return isl_union_set_free(uset
);
4231 /* Insert an extension node on top of "node" with extension "extension".
4232 * In addition, insert a filter that separates node from the extension
4233 * between the extension node and "node".
4234 * Return a pointer to the inserted filter node.
4236 * If "node" already appears in an extension (i.e., if it is the child
4237 * of a filter in a sequence inside an extension node), then extend that
4238 * extension with "extension" instead.
4239 * In this case, a pointer to the original filter node is returned.
4240 * Note that if some of the elements in the new extension live in the
4241 * same space as those of the original extension or the domain elements
4242 * reaching the original extension, then we insert a new extension anyway.
4243 * Otherwise, we would have to adjust the filters in the sequence child
4244 * of the extension to ensure that the elements in the new extension
4247 static __isl_give isl_schedule_node
*insert_extension(
4248 __isl_take isl_schedule_node
*node
, __isl_take isl_union_map
*extension
)
4250 enum isl_schedule_node_type ancestors
[] =
4251 { isl_schedule_node_filter
, isl_schedule_node_sequence
,
4252 isl_schedule_node_extension
};
4253 isl_union_set
*domain
;
4254 isl_union_set
*filter
;
4257 in_ext
= has_ancestors(node
, 3, ancestors
);
4263 disjoint
= is_disjoint_extension(node
, extension
);
4267 return extend_extension(node
, extension
);
4270 filter
= isl_schedule_node_get_domain(node
);
4271 domain
= isl_union_map_range(isl_union_map_copy(extension
));
4272 filter
= replace_by_universe_if_disjoint(filter
, domain
);
4273 isl_union_set_free(domain
);
4275 node
= isl_schedule_node_insert_filter(node
, filter
);
4276 node
= isl_schedule_node_insert_extension(node
, extension
);
4277 node
= isl_schedule_node_child(node
, 0);
4280 isl_schedule_node_free(node
);
4281 isl_union_map_free(extension
);
4285 /* Replace the subtree that "node" points to by "tree" (which has
4286 * a sequence root with two children), except if the parent of "node"
4287 * is a sequence as well, in which case "tree" is spliced at the position
4288 * of "node" in its parent.
4289 * Return a pointer to the child of the "tree_pos" (filter) child of "tree"
4290 * in the updated schedule tree.
4292 static __isl_give isl_schedule_node
*graft_or_splice(
4293 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_tree
*tree
,
4298 if (isl_schedule_node_get_parent_type(node
) ==
4299 isl_schedule_node_sequence
) {
4300 pos
= isl_schedule_node_get_child_position(node
);
4302 node
= isl_schedule_node_free(node
);
4303 node
= isl_schedule_node_parent(node
);
4304 node
= isl_schedule_node_sequence_splice(node
, pos
, tree
);
4307 node
= isl_schedule_node_graft_tree(node
, tree
);
4309 node
= isl_schedule_node_child(node
, pos
+ tree_pos
);
4310 node
= isl_schedule_node_child(node
, 0);
4315 /* Insert a node "graft" into the schedule tree of "node" such that it
4316 * is executed before (if "before" is set) or after (if "before" is not set)
4317 * the node that "node" points to.
4318 * The root of "graft" is an extension node.
4319 * Return a pointer to the node that "node" pointed to.
4321 * We first insert an extension node on top of "node" (or extend
4322 * the extension node if there already is one), with a filter on "node"
4323 * separating it from the extension.
4324 * We then insert a filter in the graft to separate it from the original
4325 * domain elements and combine the original and new tree in a sequence.
4326 * If we have extended an extension node, then the children of this
4327 * sequence are spliced in the sequence of the extended extension
4328 * at the position where "node" appears in the original extension.
4329 * Otherwise, the sequence pair is attached to the new extension node.
4331 static __isl_give isl_schedule_node
*graft_extension(
4332 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
,
4335 isl_union_map
*extension
;
4336 isl_union_set
*graft_domain
;
4337 isl_union_set
*node_domain
;
4338 isl_schedule_tree
*tree
, *tree_graft
;
4340 extension
= isl_schedule_node_extension_get_extension(graft
);
4341 graft_domain
= isl_union_map_range(isl_union_map_copy(extension
));
4342 node_domain
= isl_schedule_node_get_universe_domain(node
);
4343 node
= insert_extension(node
, extension
);
4345 graft_domain
= replace_by_universe_if_disjoint(graft_domain
,
4347 isl_union_set_free(node_domain
);
4349 tree
= isl_schedule_node_get_tree(node
);
4350 if (!isl_schedule_node_has_children(graft
)) {
4351 tree_graft
= isl_schedule_tree_from_filter(graft_domain
);
4353 graft
= isl_schedule_node_child(graft
, 0);
4354 tree_graft
= isl_schedule_node_get_tree(graft
);
4355 tree_graft
= isl_schedule_tree_insert_filter(tree_graft
,
4359 tree
= isl_schedule_tree_sequence_pair(tree_graft
, tree
);
4361 tree
= isl_schedule_tree_sequence_pair(tree
, tree_graft
);
4362 node
= graft_or_splice(node
, tree
, before
);
4364 isl_schedule_node_free(graft
);
4369 /* Replace the root domain node of "node" by an extension node suitable
4370 * for insertion at "pos".
4371 * That is, create an extension node that maps the outer band nodes
4372 * at "pos" to the domain of the root node of "node" and attach
4373 * the child of this root node to the extension node.
4375 static __isl_give isl_schedule_node
*extension_from_domain(
4376 __isl_take isl_schedule_node
*node
, __isl_keep isl_schedule_node
*pos
)
4378 isl_union_set
*universe
;
4379 isl_union_set
*domain
;
4384 isl_schedule_node
*res
;
4385 isl_schedule_tree
*tree
;
4387 anchored
= isl_schedule_node_is_subtree_anchored(node
);
4389 return isl_schedule_node_free(node
);
4391 isl_die(isl_schedule_node_get_ctx(node
), isl_error_unsupported
,
4392 "cannot graft anchored tree with domain root",
4393 return isl_schedule_node_free(node
));
4395 depth
= isl_schedule_node_get_schedule_depth(pos
);
4396 domain
= isl_schedule_node_domain_get_domain(node
);
4397 space
= isl_union_set_get_space(domain
);
4398 space
= isl_space_set_from_params(space
);
4399 space
= isl_space_add_dims(space
, isl_dim_set
, depth
);
4400 universe
= isl_union_set_from_set(isl_set_universe(space
));
4401 ext
= isl_union_map_from_domain_and_range(universe
, domain
);
4402 res
= isl_schedule_node_from_extension(ext
);
4403 node
= isl_schedule_node_child(node
, 0);
4405 return isl_schedule_node_free(res
);
4406 if (!isl_schedule_tree_is_leaf(node
->tree
)) {
4407 tree
= isl_schedule_node_get_tree(node
);
4408 res
= isl_schedule_node_child(res
, 0);
4409 res
= isl_schedule_node_graft_tree(res
, tree
);
4410 res
= isl_schedule_node_parent(res
);
4412 isl_schedule_node_free(node
);
4417 /* Insert a node "graft" into the schedule tree of "node" such that it
4418 * is executed before (if "before" is set) or after (if "before" is not set)
4419 * the node that "node" points to.
4420 * The root of "graft" may be either a domain or an extension node.
4421 * In the latter case, the domain of the extension needs to correspond
4422 * to the outer band nodes of "node".
4423 * The elements of the domain or the range of the extension may not
4424 * intersect with the domain elements that reach "node".
4425 * The schedule tree of "graft" may not be anchored.
4427 * The schedule tree of "node" is modified to include an extension node
4428 * corresponding to the root node of "graft" as a child of the original
4429 * parent of "node". The original node that "node" points to and the
4430 * child of the root node of "graft" are attached to this extension node
4431 * through a sequence, with appropriate filters and with the child
4432 * of "graft" appearing before or after the original "node".
4434 * If "node" already appears inside a sequence that is the child of
4435 * an extension node and if the spaces of the new domain elements
4436 * do not overlap with those of the original domain elements,
4437 * then that extension node is extended with the new extension
4438 * rather than introducing a new segment of extension and sequence nodes.
4440 * Return a pointer to the same node in the modified tree that
4441 * "node" pointed to in the original tree.
4443 static __isl_give isl_schedule_node
*isl_schedule_node_graft_before_or_after(
4444 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
,
4447 if (!node
|| !graft
)
4449 if (check_insert(node
) < 0)
4452 if (isl_schedule_node_get_type(graft
) == isl_schedule_node_domain
)
4453 graft
= extension_from_domain(graft
, node
);
4457 if (isl_schedule_node_get_type(graft
) != isl_schedule_node_extension
)
4458 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4459 "expecting domain or extension as root of graft",
4462 return graft_extension(node
, graft
, before
);
4464 isl_schedule_node_free(node
);
4465 isl_schedule_node_free(graft
);
4469 /* Insert a node "graft" into the schedule tree of "node" such that it
4470 * is executed before the node that "node" points to.
4471 * The root of "graft" may be either a domain or an extension node.
4472 * In the latter case, the domain of the extension needs to correspond
4473 * to the outer band nodes of "node".
4474 * The elements of the domain or the range of the extension may not
4475 * intersect with the domain elements that reach "node".
4476 * The schedule tree of "graft" may not be anchored.
4478 * Return a pointer to the same node in the modified tree that
4479 * "node" pointed to in the original tree.
4481 __isl_give isl_schedule_node
*isl_schedule_node_graft_before(
4482 __isl_take isl_schedule_node
*node
, __isl_take isl_schedule_node
*graft
)
4484 return isl_schedule_node_graft_before_or_after(node
, graft
, 1);
4487 /* Insert a node "graft" into the schedule tree of "node" such that it
4488 * is executed after the node that "node" points to.
4489 * The root of "graft" may be either a domain or an extension node.
4490 * In the latter case, the domain of the extension needs to correspond
4491 * to the outer band nodes of "node".
4492 * The elements of the domain or the range of the extension may not
4493 * intersect with the domain elements that reach "node".
4494 * The schedule tree of "graft" may not be anchored.
4496 * Return a pointer to the same node in the modified tree that
4497 * "node" pointed to in the original tree.
4499 __isl_give isl_schedule_node
*isl_schedule_node_graft_after(
4500 __isl_take isl_schedule_node
*node
,
4501 __isl_take isl_schedule_node
*graft
)
4503 return isl_schedule_node_graft_before_or_after(node
, graft
, 0);
4506 /* Split the domain elements that reach "node" into those that satisfy
4507 * "filter" and those that do not. Arrange for the first subset to be
4508 * executed before or after the second subset, depending on the value
4510 * Return a pointer to the tree corresponding to the second subset,
4511 * except when this subset is empty in which case the original pointer
4513 * If both subsets are non-empty, then a sequence node is introduced
4514 * to impose the order. If the grandparent of the original node was
4515 * itself a sequence, then the original child is replaced by two children
4516 * in this sequence instead.
4517 * The children in the sequence are copies of the original subtree,
4518 * simplified with respect to their filters.
4520 static __isl_give isl_schedule_node
*isl_schedule_node_order_before_or_after(
4521 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
,
4524 enum isl_schedule_node_type ancestors
[] =
4525 { isl_schedule_node_filter
, isl_schedule_node_sequence
};
4526 isl_union_set
*node_domain
, *node_filter
= NULL
, *parent_filter
;
4527 isl_schedule_node
*node2
;
4528 isl_schedule_tree
*tree1
, *tree2
;
4529 isl_bool empty1
, empty2
;
4532 if (!node
|| !filter
)
4534 if (check_insert(node
) < 0)
4537 in_seq
= has_ancestors(node
, 2, ancestors
);
4540 node_domain
= isl_schedule_node_get_domain(node
);
4541 filter
= isl_union_set_gist(filter
, isl_union_set_copy(node_domain
));
4542 node_filter
= isl_union_set_copy(node_domain
);
4543 node_filter
= isl_union_set_subtract(node_filter
,
4544 isl_union_set_copy(filter
));
4545 node_filter
= isl_union_set_gist(node_filter
, node_domain
);
4546 empty1
= isl_union_set_is_empty(filter
);
4547 empty2
= isl_union_set_is_empty(node_filter
);
4548 if (empty1
< 0 || empty2
< 0)
4550 if (empty1
|| empty2
) {
4551 isl_union_set_free(filter
);
4552 isl_union_set_free(node_filter
);
4557 node
= isl_schedule_node_parent(node
);
4558 parent_filter
= isl_schedule_node_filter_get_filter(node
);
4559 node_filter
= isl_union_set_intersect(node_filter
,
4560 isl_union_set_copy(parent_filter
));
4561 filter
= isl_union_set_intersect(filter
, parent_filter
);
4564 node2
= isl_schedule_node_copy(node
);
4565 node
= isl_schedule_node_gist(node
, isl_union_set_copy(node_filter
));
4566 node2
= isl_schedule_node_gist(node2
, isl_union_set_copy(filter
));
4567 tree1
= isl_schedule_node_get_tree(node
);
4568 tree2
= isl_schedule_node_get_tree(node2
);
4569 tree1
= isl_schedule_tree_insert_filter(tree1
, node_filter
);
4570 tree2
= isl_schedule_tree_insert_filter(tree2
, filter
);
4571 isl_schedule_node_free(node2
);
4574 tree1
= isl_schedule_tree_sequence_pair(tree2
, tree1
);
4575 node
= graft_or_splice(node
, tree1
, 1);
4577 tree1
= isl_schedule_tree_sequence_pair(tree1
, tree2
);
4578 node
= graft_or_splice(node
, tree1
, 0);
4583 isl_schedule_node_free(node
);
4584 isl_union_set_free(filter
);
4585 isl_union_set_free(node_filter
);
4589 /* Split the domain elements that reach "node" into those that satisfy
4590 * "filter" and those that do not. Arrange for the first subset to be
4591 * executed before the second subset.
4592 * Return a pointer to the tree corresponding to the second subset,
4593 * except when this subset is empty in which case the original pointer
4596 __isl_give isl_schedule_node
*isl_schedule_node_order_before(
4597 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
4599 return isl_schedule_node_order_before_or_after(node
, filter
, 1);
4602 /* Split the domain elements that reach "node" into those that satisfy
4603 * "filter" and those that do not. Arrange for the first subset to be
4604 * executed after the second subset.
4605 * Return a pointer to the tree corresponding to the second subset,
4606 * except when this subset is empty in which case the original pointer
4609 __isl_give isl_schedule_node
*isl_schedule_node_order_after(
4610 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*filter
)
4612 return isl_schedule_node_order_before_or_after(node
, filter
, 0);
4615 /* Reset the user pointer on all identifiers of parameters and tuples
4616 * in the schedule node "node".
4618 __isl_give isl_schedule_node
*isl_schedule_node_reset_user(
4619 __isl_take isl_schedule_node
*node
)
4621 isl_schedule_tree
*tree
;
4623 tree
= isl_schedule_node_get_tree(node
);
4624 tree
= isl_schedule_tree_reset_user(tree
);
4625 node
= isl_schedule_node_graft_tree(node
, tree
);
4630 /* Align the parameters of the schedule node "node" to those of "space".
4632 __isl_give isl_schedule_node
*isl_schedule_node_align_params(
4633 __isl_take isl_schedule_node
*node
, __isl_take isl_space
*space
)
4635 isl_schedule_tree
*tree
;
4637 tree
= isl_schedule_node_get_tree(node
);
4638 tree
= isl_schedule_tree_align_params(tree
, space
);
4639 node
= isl_schedule_node_graft_tree(node
, tree
);
4644 /* Compute the pullback of schedule node "node"
4645 * by the function represented by "upma".
4646 * In other words, plug in "upma" in the iteration domains
4647 * of schedule node "node".
4648 * We currently do not handle expansion nodes.
4650 * Note that this is only a helper function for
4651 * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency,
4652 * this function should not be called on a single node without also
4653 * calling it on all the other nodes.
4655 __isl_give isl_schedule_node
*isl_schedule_node_pullback_union_pw_multi_aff(
4656 __isl_take isl_schedule_node
*node
,
4657 __isl_take isl_union_pw_multi_aff
*upma
)
4659 isl_schedule_tree
*tree
;
4661 tree
= isl_schedule_node_get_tree(node
);
4662 tree
= isl_schedule_tree_pullback_union_pw_multi_aff(tree
, upma
);
4663 node
= isl_schedule_node_graft_tree(node
, tree
);
4668 /* Internal data structure for isl_schedule_node_expand.
4669 * "tree" is the tree that needs to be plugged in in all the leaves.
4670 * "domain" is the set of domain elements in the original leaves
4671 * to which the tree applies.
4673 struct isl_schedule_expand_data
{
4674 isl_schedule_tree
*tree
;
4675 isl_union_set
*domain
;
4678 /* If "node" is a leaf, then plug in data->tree, simplifying it
4679 * within its new context.
4681 * If there are any domain elements at the leaf where the tree
4682 * should not be plugged in (i.e., there are elements not in data->domain)
4683 * then first extend the tree to only apply to the elements in data->domain
4684 * by constructing a set node that selects data->tree for elements
4685 * in data->domain and a leaf for the other elements.
4687 static __isl_give isl_schedule_node
*expand(__isl_take isl_schedule_node
*node
,
4690 struct isl_schedule_expand_data
*data
= user
;
4691 isl_schedule_tree
*tree
, *leaf
;
4692 isl_union_set
*domain
, *left
;
4695 if (isl_schedule_node_get_type(node
) != isl_schedule_node_leaf
)
4698 domain
= isl_schedule_node_get_domain(node
);
4699 tree
= isl_schedule_tree_copy(data
->tree
);
4701 left
= isl_union_set_copy(domain
);
4702 left
= isl_union_set_subtract(left
, isl_union_set_copy(data
->domain
));
4703 empty
= isl_union_set_is_empty(left
);
4704 if (empty
>= 0 && !empty
) {
4705 leaf
= isl_schedule_node_get_leaf(node
);
4706 leaf
= isl_schedule_tree_insert_filter(leaf
, left
);
4707 left
= isl_union_set_copy(data
->domain
);
4708 tree
= isl_schedule_tree_insert_filter(tree
, left
);
4709 tree
= isl_schedule_tree_set_pair(tree
, leaf
);
4712 node
= isl_schedule_node_free(node
);
4713 isl_union_set_free(left
);
4716 node
= isl_schedule_node_graft_tree(node
, tree
);
4717 node
= isl_schedule_node_gist(node
, domain
);
4722 /* Expand the tree rooted at "node" by extending all leaves
4723 * with an expansion node with as child "tree".
4724 * The expansion is determined by "contraction" and "domain".
4725 * That is, the elements of "domain" are contracted according
4726 * to "contraction". The expansion relation is then the inverse
4727 * of "contraction" with its range intersected with "domain".
4729 * Insert the appropriate expansion node on top of "tree" and
4730 * then plug in the result in all leaves of "node".
4732 __isl_give isl_schedule_node
*isl_schedule_node_expand(
4733 __isl_take isl_schedule_node
*node
,
4734 __isl_take isl_union_pw_multi_aff
*contraction
,
4735 __isl_take isl_union_set
*domain
,
4736 __isl_take isl_schedule_tree
*tree
)
4738 struct isl_schedule_expand_data data
;
4739 isl_union_map
*expansion
;
4740 isl_union_pw_multi_aff
*copy
;
4742 if (!node
|| !contraction
|| !tree
)
4743 node
= isl_schedule_node_free(node
);
4745 copy
= isl_union_pw_multi_aff_copy(contraction
);
4746 expansion
= isl_union_map_from_union_pw_multi_aff(copy
);
4747 expansion
= isl_union_map_reverse(expansion
);
4748 expansion
= isl_union_map_intersect_range(expansion
, domain
);
4749 data
.domain
= isl_union_map_domain(isl_union_map_copy(expansion
));
4751 tree
= isl_schedule_tree_insert_expansion(tree
, contraction
, expansion
);
4754 node
= isl_schedule_node_map_descendant_bottom_up(node
, &expand
, &data
);
4755 isl_union_set_free(data
.domain
);
4756 isl_schedule_tree_free(data
.tree
);
4760 /* Return the position of the subtree containing "node" among the children
4761 * of "ancestor". "node" is assumed to be a descendant of "ancestor".
4762 * In particular, both nodes should point to the same schedule tree.
4764 * Return -1 on error.
4766 int isl_schedule_node_get_ancestor_child_position(
4767 __isl_keep isl_schedule_node
*node
,
4768 __isl_keep isl_schedule_node
*ancestor
)
4771 isl_schedule_tree
*tree
;
4773 n1
= isl_schedule_node_get_tree_depth(ancestor
);
4774 n2
= isl_schedule_node_get_tree_depth(node
);
4775 if (n1
< 0 || n2
< 0)
4776 return isl_size_error
;
4778 if (node
->schedule
!= ancestor
->schedule
)
4779 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4780 "not a descendant", return -1);
4783 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4784 "not a descendant", return -1);
4785 tree
= isl_schedule_tree_list_get_schedule_tree(node
->ancestors
, n1
);
4786 isl_schedule_tree_free(tree
);
4787 if (tree
!= ancestor
->tree
)
4788 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
4789 "not a descendant", return -1);
4791 return node
->child_pos
[n1
];
4794 /* Given two nodes that point to the same schedule tree, return their
4795 * closest shared ancestor.
4797 * Since the two nodes point to the same schedule, they share at least
4798 * one ancestor, the root of the schedule. We move down from the root
4799 * to the first ancestor where the respective children have a different
4800 * child position. This is the requested ancestor.
4801 * If there is no ancestor where the children have a different position,
4802 * then one node is an ancestor of the other and then this node is
4803 * the requested ancestor.
4805 __isl_give isl_schedule_node
*isl_schedule_node_get_shared_ancestor(
4806 __isl_keep isl_schedule_node
*node1
,
4807 __isl_keep isl_schedule_node
*node2
)
4812 n1
= isl_schedule_node_get_tree_depth(node1
);
4813 n2
= isl_schedule_node_get_tree_depth(node2
);
4814 if (n1
< 0 || n2
< 0)
4816 if (node1
->schedule
!= node2
->schedule
)
4817 isl_die(isl_schedule_node_get_ctx(node1
), isl_error_invalid
,
4818 "not part of same schedule", return NULL
);
4820 return isl_schedule_node_get_shared_ancestor(node2
, node1
);
4822 return isl_schedule_node_copy(node1
);
4823 if (isl_schedule_node_is_equal(node1
, node2
))
4824 return isl_schedule_node_copy(node1
);
4826 for (i
= 0; i
< n1
; ++i
)
4827 if (node1
->child_pos
[i
] != node2
->child_pos
[i
])
4830 node1
= isl_schedule_node_copy(node1
);
4831 return isl_schedule_node_ancestor(node1
, n1
- i
);
4834 /* Print "node" to "p".
4836 __isl_give isl_printer
*isl_printer_print_schedule_node(
4837 __isl_take isl_printer
*p
, __isl_keep isl_schedule_node
*node
)
4842 return isl_printer_free(p
);
4843 n
= isl_schedule_tree_list_n_schedule_tree(node
->ancestors
);
4845 return isl_printer_free(p
);
4846 return isl_printer_print_schedule_tree_mark(p
, node
->schedule
->root
, n
,
4850 void isl_schedule_node_dump(__isl_keep isl_schedule_node
*node
)
4853 isl_printer
*printer
;
4858 ctx
= isl_schedule_node_get_ctx(node
);
4859 printer
= isl_printer_to_file(ctx
, stderr
);
4860 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
4861 printer
= isl_printer_print_schedule_node(printer
, node
);
4863 isl_printer_free(printer
);
4866 /* Return a string representation of "node".
4867 * Print the schedule node in block format as it would otherwise
4868 * look identical to the entire schedule.
4870 __isl_give
char *isl_schedule_node_to_str(__isl_keep isl_schedule_node
*node
)
4872 isl_printer
*printer
;
4878 printer
= isl_printer_to_str(isl_schedule_node_get_ctx(node
));
4879 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
4880 printer
= isl_printer_print_schedule_node(printer
, node
);
4881 s
= isl_printer_get_str(printer
);
4882 isl_printer_free(printer
);