2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
14 #include <isl_aff_private.h>
17 #include <isl/schedule.h>
18 #include <isl/schedule_node.h>
20 #include <isl_schedule_private.h>
21 #include <isl_schedule_tree.h>
22 #include <isl_schedule_node_private.h>
23 #include <isl_band_private.h>
25 /* Return a schedule encapsulating the given schedule tree.
27 * We currently only allow schedule trees with a domain or extension as root.
29 * The leaf field is initialized as a leaf node so that it can be
30 * used to represent leaves in the constructed schedule.
31 * The reference count is set to -1 since the isl_schedule_tree
32 * should never be freed. It is up to the (internal) users of
33 * these leaves to ensure that they are only used while the schedule
36 __isl_give isl_schedule
*isl_schedule_from_schedule_tree(isl_ctx
*ctx
,
37 __isl_take isl_schedule_tree
*tree
)
39 enum isl_schedule_node_type type
;
40 isl_schedule
*schedule
;
44 type
= isl_schedule_tree_get_type(tree
);
45 if (type
!= isl_schedule_node_domain
&&
46 type
!= isl_schedule_node_extension
)
47 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_unsupported
,
48 "root of schedule tree should be a domain or extension",
51 schedule
= isl_calloc_type(ctx
, isl_schedule
);
56 schedule
->root
= tree
;
57 schedule
->leaf
= isl_schedule_tree_leaf(ctx
);
60 return isl_schedule_free(schedule
);
63 isl_schedule_tree_free(tree
);
67 /* Return a pointer to a schedule with as single node
68 * a domain node with the given domain.
70 __isl_give isl_schedule
*isl_schedule_from_domain(
71 __isl_take isl_union_set
*domain
)
74 isl_schedule_tree
*tree
;
76 ctx
= isl_union_set_get_ctx(domain
);
77 tree
= isl_schedule_tree_from_domain(domain
);
78 return isl_schedule_from_schedule_tree(ctx
, tree
);
81 /* Return a pointer to a schedule with as single node
82 * a domain node with an empty domain.
84 __isl_give isl_schedule
*isl_schedule_empty(__isl_take isl_space
*space
)
86 return isl_schedule_from_domain(isl_union_set_empty(space
));
89 /* Return a new reference to "sched".
91 __isl_give isl_schedule
*isl_schedule_copy(__isl_keep isl_schedule
*sched
)
100 /* Return an isl_schedule that is equal to "schedule" and that has only
101 * a single reference.
103 * We only need and support this function when the schedule is represented
104 * as a schedule tree.
106 __isl_give isl_schedule
*isl_schedule_cow(__isl_take isl_schedule
*schedule
)
109 isl_schedule_tree
*tree
;
113 if (schedule
->ref
== 1)
116 ctx
= isl_schedule_get_ctx(schedule
);
118 isl_die(ctx
, isl_error_internal
,
119 "only for schedule tree based schedules",
120 return isl_schedule_free(schedule
));
122 tree
= isl_schedule_tree_copy(schedule
->root
);
123 return isl_schedule_from_schedule_tree(ctx
, tree
);
126 __isl_null isl_schedule
*isl_schedule_free(__isl_take isl_schedule
*sched
)
131 if (--sched
->ref
> 0)
134 isl_band_list_free(sched
->band_forest
);
135 isl_schedule_tree_free(sched
->root
);
136 isl_schedule_tree_free(sched
->leaf
);
141 /* Replace the root of "schedule" by "tree".
143 __isl_give isl_schedule
*isl_schedule_set_root(
144 __isl_take isl_schedule
*schedule
, __isl_take isl_schedule_tree
*tree
)
146 if (!schedule
|| !tree
)
148 if (schedule
->root
== tree
) {
149 isl_schedule_tree_free(tree
);
153 schedule
= isl_schedule_cow(schedule
);
156 isl_schedule_tree_free(schedule
->root
);
157 schedule
->root
= tree
;
161 isl_schedule_free(schedule
);
162 isl_schedule_tree_free(tree
);
166 isl_ctx
*isl_schedule_get_ctx(__isl_keep isl_schedule
*schedule
)
168 return schedule
? isl_schedule_tree_get_ctx(schedule
->leaf
) : NULL
;
171 /* Return a pointer to the leaf of "schedule".
173 * Even though these leaves are not reference counted, we still
174 * indicate that this function does not return a copy.
176 __isl_keep isl_schedule_tree
*isl_schedule_peek_leaf(
177 __isl_keep isl_schedule
*schedule
)
179 return schedule
? schedule
->leaf
: NULL
;
182 /* Are "schedule1" and "schedule2" obviously equal to each other?
184 isl_bool
isl_schedule_plain_is_equal(__isl_keep isl_schedule
*schedule1
,
185 __isl_keep isl_schedule
*schedule2
)
187 if (!schedule1
|| !schedule2
)
188 return isl_bool_error
;
189 if (schedule1
== schedule2
)
190 return isl_bool_true
;
191 return isl_schedule_tree_plain_is_equal(schedule1
->root
,
195 /* Return the (parameter) space of the schedule, i.e., the space
196 * of the root domain.
198 __isl_give isl_space
*isl_schedule_get_space(
199 __isl_keep isl_schedule
*schedule
)
201 enum isl_schedule_node_type type
;
203 isl_union_set
*domain
;
208 isl_die(isl_schedule_get_ctx(schedule
), isl_error_invalid
,
209 "schedule tree representation not available",
211 type
= isl_schedule_tree_get_type(schedule
->root
);
212 if (type
!= isl_schedule_node_domain
)
213 isl_die(isl_schedule_get_ctx(schedule
), isl_error_internal
,
214 "root node not a domain node", return NULL
);
216 domain
= isl_schedule_tree_domain_get_domain(schedule
->root
);
217 space
= isl_union_set_get_space(domain
);
218 isl_union_set_free(domain
);
223 /* Return a pointer to the root of "schedule".
225 __isl_give isl_schedule_node
*isl_schedule_get_root(
226 __isl_keep isl_schedule
*schedule
)
229 isl_schedule_tree
*tree
;
230 isl_schedule_tree_list
*ancestors
;
236 isl_die(isl_schedule_get_ctx(schedule
), isl_error_invalid
,
237 "schedule tree representation not available",
240 ctx
= isl_schedule_get_ctx(schedule
);
241 tree
= isl_schedule_tree_copy(schedule
->root
);
242 schedule
= isl_schedule_copy(schedule
);
243 ancestors
= isl_schedule_tree_list_alloc(ctx
, 0);
244 return isl_schedule_node_alloc(schedule
, tree
, ancestors
, NULL
);
247 /* Set max_out to the maximal number of output dimensions over
250 static isl_stat
update_max_out(__isl_take isl_map
*map
, void *user
)
253 int n_out
= isl_map_dim(map
, isl_dim_out
);
255 if (n_out
> *max_out
)
262 /* Internal data structure for map_pad_range.
264 * "max_out" is the maximal schedule dimension.
265 * "res" collects the results.
267 struct isl_pad_schedule_map_data
{
272 /* Pad the range of the given map with zeros to data->max_out and
273 * then add the result to data->res.
275 static isl_stat
map_pad_range(__isl_take isl_map
*map
, void *user
)
277 struct isl_pad_schedule_map_data
*data
= user
;
279 int n_out
= isl_map_dim(map
, isl_dim_out
);
281 map
= isl_map_add_dims(map
, isl_dim_out
, data
->max_out
- n_out
);
282 for (i
= n_out
; i
< data
->max_out
; ++i
)
283 map
= isl_map_fix_si(map
, isl_dim_out
, i
, 0);
285 data
->res
= isl_union_map_add_map(data
->res
, map
);
287 return isl_stat_error
;
292 /* Pad the ranges of the maps in the union map with zeros such they all have
293 * the same dimension.
295 static __isl_give isl_union_map
*pad_schedule_map(
296 __isl_take isl_union_map
*umap
)
298 struct isl_pad_schedule_map_data data
;
302 if (isl_union_map_n_map(umap
) <= 1)
306 if (isl_union_map_foreach_map(umap
, &update_max_out
, &data
.max_out
) < 0)
307 return isl_union_map_free(umap
);
309 data
.res
= isl_union_map_empty(isl_union_map_get_space(umap
));
310 if (isl_union_map_foreach_map(umap
, &map_pad_range
, &data
) < 0)
311 data
.res
= isl_union_map_free(data
.res
);
313 isl_union_map_free(umap
);
317 /* Return the domain of the root domain node of "schedule".
319 __isl_give isl_union_set
*isl_schedule_get_domain(
320 __isl_keep isl_schedule
*schedule
)
325 isl_die(isl_schedule_get_ctx(schedule
), isl_error_invalid
,
326 "schedule tree representation not available",
328 return isl_schedule_tree_domain_get_domain(schedule
->root
);
331 /* Traverse all nodes of "sched" in depth first preorder.
333 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
334 * If "fn" returns 0 on any of the nodes, then the subtree rooted
335 * at that node is skipped.
337 * Return 0 on success and -1 on failure.
339 isl_stat
isl_schedule_foreach_schedule_node_top_down(
340 __isl_keep isl_schedule
*sched
,
341 isl_bool (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
),
344 isl_schedule_node
*node
;
348 return isl_stat_error
;
350 node
= isl_schedule_get_root(sched
);
351 r
= isl_schedule_node_foreach_descendant_top_down(node
, fn
, user
);
352 isl_schedule_node_free(node
);
357 /* Traverse the node of "sched" in depth first postorder,
358 * allowing the user to modify the visited node.
359 * The traversal continues from the node returned by the callback function.
360 * It is the responsibility of the user to ensure that this does not
361 * lead to an infinite loop. It is safest to always return a pointer
362 * to the same position (same ancestors and child positions) as the input node.
364 __isl_give isl_schedule
*isl_schedule_map_schedule_node_bottom_up(
365 __isl_take isl_schedule
*schedule
,
366 __isl_give isl_schedule_node
*(*fn
)(
367 __isl_take isl_schedule_node
*node
, void *user
), void *user
)
369 isl_schedule_node
*node
;
371 node
= isl_schedule_get_root(schedule
);
372 isl_schedule_free(schedule
);
374 node
= isl_schedule_node_map_descendant_bottom_up(node
, fn
, user
);
375 schedule
= isl_schedule_node_get_schedule(node
);
376 isl_schedule_node_free(node
);
381 /* Wrapper around isl_schedule_node_reset_user for use as
382 * an isl_schedule_map_schedule_node_bottom_up callback.
384 static __isl_give isl_schedule_node
*reset_user(
385 __isl_take isl_schedule_node
*node
, void *user
)
387 return isl_schedule_node_reset_user(node
);
390 /* Reset the user pointer on all identifiers of parameters and tuples
391 * in the schedule "schedule".
393 __isl_give isl_schedule
*isl_schedule_reset_user(
394 __isl_take isl_schedule
*schedule
)
396 return isl_schedule_map_schedule_node_bottom_up(schedule
, &reset_user
,
400 /* Wrapper around isl_schedule_node_align_params for use as
401 * an isl_schedule_map_schedule_node_bottom_up callback.
403 static __isl_give isl_schedule_node
*align_params(
404 __isl_take isl_schedule_node
*node
, void *user
)
406 isl_space
*space
= user
;
408 return isl_schedule_node_align_params(node
, isl_space_copy(space
));
411 /* Align the parameters of all nodes in schedule "schedule"
412 * to those of "space".
414 __isl_give isl_schedule
*isl_schedule_align_params(
415 __isl_take isl_schedule
*schedule
, __isl_take isl_space
*space
)
417 schedule
= isl_schedule_map_schedule_node_bottom_up(schedule
,
418 &align_params
, space
);
419 isl_space_free(space
);
423 /* Wrapper around isl_schedule_node_pullback_union_pw_multi_aff for use as
424 * an isl_schedule_map_schedule_node_bottom_up callback.
426 static __isl_give isl_schedule_node
*pullback_upma(
427 __isl_take isl_schedule_node
*node
, void *user
)
429 isl_union_pw_multi_aff
*upma
= user
;
431 return isl_schedule_node_pullback_union_pw_multi_aff(node
,
432 isl_union_pw_multi_aff_copy(upma
));
435 /* Compute the pullback of "schedule" by the function represented by "upma".
436 * In other words, plug in "upma" in the iteration domains of "schedule".
438 * The schedule tree is not allowed to contain any expansion nodes.
440 __isl_give isl_schedule
*isl_schedule_pullback_union_pw_multi_aff(
441 __isl_take isl_schedule
*schedule
,
442 __isl_take isl_union_pw_multi_aff
*upma
)
444 schedule
= isl_schedule_map_schedule_node_bottom_up(schedule
,
445 &pullback_upma
, upma
);
446 isl_union_pw_multi_aff_free(upma
);
450 /* Intersect the domain of the schedule "schedule" with "domain".
451 * The root of "schedule" is required to be a domain node.
453 __isl_give isl_schedule
*isl_schedule_intersect_domain(
454 __isl_take isl_schedule
*schedule
, __isl_take isl_union_set
*domain
)
456 enum isl_schedule_node_type root_type
;
457 isl_schedule_node
*node
;
459 if (!schedule
|| !domain
)
462 root_type
= isl_schedule_tree_get_type(schedule
->root
);
463 if (root_type
!= isl_schedule_node_domain
)
464 isl_die(isl_schedule_get_ctx(schedule
), isl_error_invalid
,
465 "root node must be a domain node", goto error
);
467 node
= isl_schedule_get_root(schedule
);
468 isl_schedule_free(schedule
);
469 node
= isl_schedule_node_domain_intersect_domain(node
, domain
);
470 schedule
= isl_schedule_node_get_schedule(node
);
471 isl_schedule_node_free(node
);
475 isl_schedule_free(schedule
);
476 isl_union_set_free(domain
);
480 /* Replace the domain of the schedule "schedule" with the gist
481 * of the original domain with respect to the parameter domain "context".
483 __isl_give isl_schedule
*isl_schedule_gist_domain_params(
484 __isl_take isl_schedule
*schedule
, __isl_take isl_set
*context
)
486 enum isl_schedule_node_type root_type
;
487 isl_schedule_node
*node
;
489 if (!schedule
|| !context
)
492 root_type
= isl_schedule_tree_get_type(schedule
->root
);
493 if (root_type
!= isl_schedule_node_domain
)
494 isl_die(isl_schedule_get_ctx(schedule
), isl_error_invalid
,
495 "root node must be a domain node", goto error
);
497 node
= isl_schedule_get_root(schedule
);
498 isl_schedule_free(schedule
);
499 node
= isl_schedule_node_domain_gist_params(node
, context
);
500 schedule
= isl_schedule_node_get_schedule(node
);
501 isl_schedule_node_free(node
);
505 isl_schedule_free(schedule
);
506 isl_set_free(context
);
510 /* Return an isl_union_map representation of the schedule.
511 * If we still have access to the schedule tree, then we return
512 * an isl_union_map corresponding to the subtree schedule of the child
513 * of the root domain node. That is, we do not intersect the domain
514 * of the returned isl_union_map with the domain constraints.
515 * Otherwise, we must have removed it because we created a band forest.
516 * If so, we extract the isl_union_map from the forest.
517 * This reconstructed schedule map
518 * then needs to be padded with zeros to unify the schedule space
519 * since the result of isl_band_list_get_suffix_schedule may not have
520 * a unified schedule space.
522 __isl_give isl_union_map
*isl_schedule_get_map(__isl_keep isl_schedule
*sched
)
524 enum isl_schedule_node_type type
;
525 isl_schedule_node
*node
;
532 type
= isl_schedule_tree_get_type(sched
->root
);
533 if (type
!= isl_schedule_node_domain
)
534 isl_die(isl_schedule_get_ctx(sched
), isl_error_internal
,
535 "root node not a domain node", return NULL
);
537 node
= isl_schedule_get_root(sched
);
538 node
= isl_schedule_node_child(node
, 0);
539 umap
= isl_schedule_node_get_subtree_schedule_union_map(node
);
540 isl_schedule_node_free(node
);
545 umap
= isl_band_list_get_suffix_schedule(sched
->band_forest
);
546 return pad_schedule_map(umap
);
549 static __isl_give isl_band_list
*construct_band_list(
550 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
,
551 __isl_keep isl_band
*parent
);
553 /* Construct an isl_band structure from the given schedule tree node,
554 * which may be either a band node or a leaf node.
555 * In the latter case, construct a zero-dimensional band.
556 * "domain" is the universe set of the domain elements that reach "node".
557 * "parent" is the parent isl_band of the isl_band constructed
560 * In case of a band node, we copy the properties (except tilability,
561 * which is implicit in an isl_band) to the isl_band.
562 * We assume that the band node is not zero-dimensional.
563 * If the child of the band node is not a leaf node,
564 * then we extract the children of the isl_band from this child.
566 static __isl_give isl_band
*construct_band(__isl_take isl_schedule_node
*node
,
567 __isl_take isl_union_set
*domain
, __isl_keep isl_band
*parent
)
571 isl_band
*band
= NULL
;
572 isl_multi_union_pw_aff
*mupa
;
574 if (!node
|| !domain
)
577 ctx
= isl_schedule_node_get_ctx(node
);
578 band
= isl_band_alloc(ctx
);
582 band
->schedule
= node
->schedule
;
583 band
->parent
= parent
;
585 if (isl_schedule_node_get_type(node
) == isl_schedule_node_leaf
) {
587 band
->pma
= isl_union_pw_multi_aff_from_domain(domain
);
588 isl_schedule_node_free(node
);
592 band
->n
= isl_schedule_node_band_n_member(node
);
594 isl_die(ctx
, isl_error_unsupported
,
595 "zero-dimensional band nodes not supported",
597 band
->coincident
= isl_alloc_array(ctx
, int, band
->n
);
598 if (band
->n
&& !band
->coincident
)
600 for (i
= 0; i
< band
->n
; ++i
)
601 band
->coincident
[i
] =
602 isl_schedule_node_band_member_get_coincident(node
, i
);
603 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
604 band
->pma
= isl_union_pw_multi_aff_from_multi_union_pw_aff(mupa
);
608 node
= isl_schedule_node_child(node
, 0);
609 if (isl_schedule_node_get_type(node
) == isl_schedule_node_leaf
) {
610 isl_schedule_node_free(node
);
611 isl_union_set_free(domain
);
615 band
->children
= construct_band_list(node
, domain
, band
);
617 return isl_band_free(band
);
621 isl_union_set_free(domain
);
622 isl_schedule_node_free(node
);
627 /* Construct a list of isl_band structures from the children of "node".
628 * "node" itself is a sequence or set node, so that each of the child nodes
629 * is a filter node and the list returned by node_construct_band_list
630 * consists of a single element.
631 * "domain" is the universe set of the domain elements that reach "node".
632 * "parent" is the parent isl_band of the isl_band structures constructed
635 static __isl_give isl_band_list
*construct_band_list_from_children(
636 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
,
637 __isl_keep isl_band
*parent
)
643 n
= isl_schedule_node_n_children(node
);
645 ctx
= isl_schedule_node_get_ctx(node
);
646 list
= isl_band_list_alloc(ctx
, 0);
647 for (i
= 0; i
< n
; ++i
) {
648 isl_schedule_node
*child
;
649 isl_band_list
*list_i
;
651 child
= isl_schedule_node_get_child(node
, i
);
652 list_i
= construct_band_list(child
, isl_union_set_copy(domain
),
654 list
= isl_band_list_concat(list
, list_i
);
657 isl_union_set_free(domain
);
658 isl_schedule_node_free(node
);
663 /* Construct an isl_band structure from the given sequence node
664 * (or set node that is treated as a sequence node).
665 * A single-dimensional band is created with as schedule for each of
666 * filters of the children, the corresponding child position.
667 * "domain" is the universe set of the domain elements that reach "node".
668 * "parent" is the parent isl_band of the isl_band constructed
671 static __isl_give isl_band_list
*construct_band_list_sequence(
672 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
,
673 __isl_keep isl_band
*parent
)
677 isl_band
*band
= NULL
;
679 isl_union_pw_multi_aff
*upma
;
681 if (!node
|| !domain
)
684 ctx
= isl_schedule_node_get_ctx(node
);
685 band
= isl_band_alloc(ctx
);
689 band
->schedule
= node
->schedule
;
690 band
->parent
= parent
;
692 band
->coincident
= isl_calloc_array(ctx
, int, band
->n
);
693 if (!band
->coincident
)
696 n
= isl_schedule_node_n_children(node
);
697 space
= isl_union_set_get_space(domain
);
698 upma
= isl_union_pw_multi_aff_empty(isl_space_copy(space
));
700 space
= isl_space_set_from_params(space
);
701 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
703 for (i
= 0; i
< n
; ++i
) {
704 isl_schedule_node
*child
;
705 isl_union_set
*filter
;
709 isl_union_pw_multi_aff
*upma_i
;
711 child
= isl_schedule_node_get_child(node
, i
);
712 filter
= isl_schedule_node_filter_get_filter(child
);
713 isl_schedule_node_free(child
);
714 filter
= isl_union_set_intersect(filter
,
715 isl_union_set_copy(domain
));
716 v
= isl_val_int_from_si(ctx
, i
);
717 vl
= isl_val_list_from_val(v
);
718 mv
= isl_multi_val_from_val_list(isl_space_copy(space
), vl
);
719 upma_i
= isl_union_pw_multi_aff_multi_val_on_domain(filter
, mv
);
720 upma
= isl_union_pw_multi_aff_union_add(upma
, upma_i
);
723 isl_space_free(space
);
729 band
->children
= construct_band_list_from_children(node
, domain
, band
);
731 band
= isl_band_free(band
);
732 return isl_band_list_from_band(band
);
734 isl_union_set_free(domain
);
735 isl_schedule_node_free(node
);
740 /* Construct a list of isl_band structures from "node" depending
741 * on the type of "node".
742 * "domain" is the universe set of the domain elements that reach "node".
743 * "parent" is the parent isl_band of the isl_band structures constructed
746 * If schedule_separate_components is set then set nodes are treated
747 * as sequence nodes. Otherwise, we directly extract an (implicitly
748 * parallel) list of isl_band structures.
750 * If "node" is a filter, then "domain" is updated by the filter.
752 static __isl_give isl_band_list
*construct_band_list(
753 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
,
754 __isl_keep isl_band
*parent
)
756 enum isl_schedule_node_type type
;
760 isl_union_set
*filter
;
762 if (!node
|| !domain
)
765 type
= isl_schedule_node_get_type(node
);
767 case isl_schedule_node_error
:
769 case isl_schedule_node_context
:
770 isl_die(isl_schedule_node_get_ctx(node
), isl_error_unsupported
,
771 "context nodes not supported", goto error
);
772 case isl_schedule_node_domain
:
773 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
774 "internal domain nodes not allowed", goto error
);
775 case isl_schedule_node_expansion
:
776 isl_die(isl_schedule_node_get_ctx(node
), isl_error_unsupported
,
777 "expansion nodes not supported", goto error
);
778 case isl_schedule_node_extension
:
779 isl_die(isl_schedule_node_get_ctx(node
), isl_error_unsupported
,
780 "extension nodes not supported", goto error
);
781 case isl_schedule_node_filter
:
782 filter
= isl_schedule_node_filter_get_filter(node
);
783 domain
= isl_union_set_intersect(domain
, filter
);
784 node
= isl_schedule_node_child(node
, 0);
785 return construct_band_list(node
, domain
, parent
);
786 case isl_schedule_node_guard
:
787 isl_die(isl_schedule_node_get_ctx(node
), isl_error_unsupported
,
788 "guard nodes not supported", goto error
);
789 case isl_schedule_node_mark
:
790 isl_die(isl_schedule_node_get_ctx(node
), isl_error_unsupported
,
791 "mark nodes not supported", goto error
);
792 case isl_schedule_node_set
:
793 ctx
= isl_schedule_node_get_ctx(node
);
794 if (isl_options_get_schedule_separate_components(ctx
))
795 return construct_band_list_sequence(node
, domain
,
798 return construct_band_list_from_children(node
, domain
,
800 case isl_schedule_node_sequence
:
801 return construct_band_list_sequence(node
, domain
, parent
);
802 case isl_schedule_node_leaf
:
803 case isl_schedule_node_band
:
804 band
= construct_band(node
, domain
, parent
);
805 list
= isl_band_list_from_band(band
);
811 isl_union_set_free(domain
);
812 isl_schedule_node_free(node
);
816 /* Return the roots of a band forest representation of the schedule.
817 * The band forest is constructed from the schedule tree,
818 * but once such a band forest is
819 * constructed, we forget about the original schedule tree since
820 * the user may modify the schedule through the band forest.
822 __isl_give isl_band_list
*isl_schedule_get_band_forest(
823 __isl_keep isl_schedule
*schedule
)
825 isl_schedule_node
*node
;
826 isl_union_set
*domain
;
830 if (schedule
->root
) {
831 node
= isl_schedule_get_root(schedule
);
832 domain
= isl_schedule_node_domain_get_domain(node
);
833 domain
= isl_union_set_universe(domain
);
834 node
= isl_schedule_node_child(node
, 0);
836 schedule
->band_forest
= construct_band_list(node
, domain
, NULL
);
837 schedule
->root
= isl_schedule_tree_free(schedule
->root
);
839 return isl_band_list_dup(schedule
->band_forest
);
842 /* Call "fn" on each band in the schedule in depth-first post-order.
844 int isl_schedule_foreach_band(__isl_keep isl_schedule
*sched
,
845 int (*fn
)(__isl_keep isl_band
*band
, void *user
), void *user
)
848 isl_band_list
*forest
;
853 forest
= isl_schedule_get_band_forest(sched
);
854 r
= isl_band_list_foreach_band(forest
, fn
, user
);
855 isl_band_list_free(forest
);
860 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
861 __isl_keep isl_band_list
*list
);
863 static __isl_give isl_printer
*print_band(__isl_take isl_printer
*p
,
864 __isl_keep isl_band
*band
)
866 isl_band_list
*children
;
868 p
= isl_printer_start_line(p
);
869 p
= isl_printer_print_union_pw_multi_aff(p
, band
->pma
);
870 p
= isl_printer_end_line(p
);
872 if (!isl_band_has_children(band
))
875 children
= isl_band_get_children(band
);
877 p
= isl_printer_indent(p
, 4);
878 p
= print_band_list(p
, children
);
879 p
= isl_printer_indent(p
, -4);
881 isl_band_list_free(children
);
886 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
887 __isl_keep isl_band_list
*list
)
891 n
= isl_band_list_n_band(list
);
892 for (i
= 0; i
< n
; ++i
) {
894 band
= isl_band_list_get_band(list
, i
);
895 p
= print_band(p
, band
);
902 /* Insert a band node with partial schedule "partial" between the domain
903 * root node of "schedule" and its single child.
904 * Return a pointer to the updated schedule.
906 * If any of the nodes in the tree depend on the set of outer band nodes
907 * then we refuse to insert the band node.
909 __isl_give isl_schedule
*isl_schedule_insert_partial_schedule(
910 __isl_take isl_schedule
*schedule
,
911 __isl_take isl_multi_union_pw_aff
*partial
)
913 isl_schedule_node
*node
;
916 node
= isl_schedule_get_root(schedule
);
917 isl_schedule_free(schedule
);
920 if (isl_schedule_node_get_type(node
) != isl_schedule_node_domain
)
921 isl_die(isl_schedule_node_get_ctx(node
), isl_error_internal
,
922 "root node not a domain node", goto error
);
924 node
= isl_schedule_node_child(node
, 0);
925 anchored
= isl_schedule_node_is_subtree_anchored(node
);
929 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
930 "cannot insert band node in anchored subtree",
932 node
= isl_schedule_node_insert_partial_schedule(node
, partial
);
934 schedule
= isl_schedule_node_get_schedule(node
);
935 isl_schedule_node_free(node
);
939 isl_schedule_node_free(node
);
940 isl_multi_union_pw_aff_free(partial
);
944 /* Insert a context node with constraints "context" between the domain
945 * root node of "schedule" and its single child.
946 * Return a pointer to the updated schedule.
948 __isl_give isl_schedule
*isl_schedule_insert_context(
949 __isl_take isl_schedule
*schedule
, __isl_take isl_set
*context
)
951 isl_schedule_node
*node
;
953 node
= isl_schedule_get_root(schedule
);
954 isl_schedule_free(schedule
);
955 node
= isl_schedule_node_child(node
, 0);
956 node
= isl_schedule_node_insert_context(node
, context
);
957 schedule
= isl_schedule_node_get_schedule(node
);
958 isl_schedule_node_free(node
);
963 /* Insert a guard node with constraints "guard" between the domain
964 * root node of "schedule" and its single child.
965 * Return a pointer to the updated schedule.
967 __isl_give isl_schedule
*isl_schedule_insert_guard(
968 __isl_take isl_schedule
*schedule
, __isl_take isl_set
*guard
)
970 isl_schedule_node
*node
;
972 node
= isl_schedule_get_root(schedule
);
973 isl_schedule_free(schedule
);
974 node
= isl_schedule_node_child(node
, 0);
975 node
= isl_schedule_node_insert_guard(node
, guard
);
976 schedule
= isl_schedule_node_get_schedule(node
);
977 isl_schedule_node_free(node
);
982 /* Return a tree with as top-level node a filter corresponding to "filter" and
983 * as child, the (single) child of "tree".
984 * However, if this single child is of type "type", then the filter is inserted
985 * in the children of this single child instead.
987 static __isl_give isl_schedule_tree
*insert_filter_in_child_of_type(
988 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
,
989 enum isl_schedule_node_type type
)
991 if (!isl_schedule_tree_has_children(tree
)) {
992 isl_schedule_tree_free(tree
);
993 return isl_schedule_tree_from_filter(filter
);
995 tree
= isl_schedule_tree_child(tree
, 0);
998 if (isl_schedule_tree_get_type(tree
) == type
)
999 tree
= isl_schedule_tree_children_insert_filter(tree
, filter
);
1001 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
1006 /* Construct a schedule that combines the schedules "schedule1" and "schedule2"
1007 * with a top-level node (underneath the domain node) of type "type",
1008 * either isl_schedule_node_sequence or isl_schedule_node_set.
1009 * The domains of the two schedules are assumed to be disjoint.
1011 * The new schedule has as domain the union of the domains of the two
1012 * schedules. The child of the domain node is a node of type "type"
1013 * with two filters corresponding to the domains of the input schedules.
1014 * If one (or both) of the top-level nodes of the two schedules is itself
1015 * of type "type", then the filter is pushed into the children of that
1016 * node and the sequence of set is flattened.
1018 __isl_give isl_schedule
*isl_schedule_pair(enum isl_schedule_node_type type
,
1019 __isl_take isl_schedule
*schedule1
, __isl_take isl_schedule
*schedule2
)
1023 enum isl_schedule_node_type root_type
;
1024 isl_schedule_tree
*tree1
, *tree2
;
1025 isl_union_set
*filter1
, *filter2
, *domain
;
1027 if (!schedule1
|| !schedule2
)
1030 root_type
= isl_schedule_tree_get_type(schedule1
->root
);
1031 if (root_type
!= isl_schedule_node_domain
)
1032 isl_die(isl_schedule_get_ctx(schedule1
), isl_error_internal
,
1033 "root node not a domain node", goto error
);
1034 root_type
= isl_schedule_tree_get_type(schedule2
->root
);
1035 if (root_type
!= isl_schedule_node_domain
)
1036 isl_die(isl_schedule_get_ctx(schedule1
), isl_error_internal
,
1037 "root node not a domain node", goto error
);
1039 ctx
= isl_schedule_get_ctx(schedule1
);
1040 tree1
= isl_schedule_tree_copy(schedule1
->root
);
1041 filter1
= isl_schedule_tree_domain_get_domain(tree1
);
1042 tree2
= isl_schedule_tree_copy(schedule2
->root
);
1043 filter2
= isl_schedule_tree_domain_get_domain(tree2
);
1045 isl_schedule_free(schedule1
);
1046 isl_schedule_free(schedule2
);
1048 disjoint
= isl_union_set_is_disjoint(filter1
, filter2
);
1050 filter1
= isl_union_set_free(filter1
);
1052 isl_die(ctx
, isl_error_invalid
,
1053 "schedule domains not disjoint",
1054 filter1
= isl_union_set_free(filter1
));
1056 domain
= isl_union_set_union(isl_union_set_copy(filter1
),
1057 isl_union_set_copy(filter2
));
1058 filter1
= isl_union_set_gist(filter1
, isl_union_set_copy(domain
));
1059 filter2
= isl_union_set_gist(filter2
, isl_union_set_copy(domain
));
1061 tree1
= insert_filter_in_child_of_type(tree1
, filter1
, type
);
1062 tree2
= insert_filter_in_child_of_type(tree2
, filter2
, type
);
1064 tree1
= isl_schedule_tree_from_pair(type
, tree1
, tree2
);
1065 tree1
= isl_schedule_tree_insert_domain(tree1
, domain
);
1067 return isl_schedule_from_schedule_tree(ctx
, tree1
);
1069 isl_schedule_free(schedule1
);
1070 isl_schedule_free(schedule2
);
1074 /* Construct a schedule that combines the schedules "schedule1" and "schedule2"
1075 * through a sequence node.
1076 * The domains of the input schedules are assumed to be disjoint.
1078 __isl_give isl_schedule
*isl_schedule_sequence(
1079 __isl_take isl_schedule
*schedule1
, __isl_take isl_schedule
*schedule2
)
1081 return isl_schedule_pair(isl_schedule_node_sequence
,
1082 schedule1
, schedule2
);
1085 /* Construct a schedule that combines the schedules "schedule1" and "schedule2"
1086 * through a set node.
1087 * The domains of the input schedules are assumed to be disjoint.
1089 __isl_give isl_schedule
*isl_schedule_set(
1090 __isl_take isl_schedule
*schedule1
, __isl_take isl_schedule
*schedule2
)
1092 return isl_schedule_pair(isl_schedule_node_set
, schedule1
, schedule2
);
1095 /* Print "schedule" to "p".
1097 * If "schedule" was created from a schedule tree, then we print
1098 * the schedule tree representation. Otherwise, we print
1099 * the band forest representation.
1101 __isl_give isl_printer
*isl_printer_print_schedule(__isl_take isl_printer
*p
,
1102 __isl_keep isl_schedule
*schedule
)
1104 isl_band_list
*forest
;
1107 return isl_printer_free(p
);
1110 return isl_printer_print_schedule_tree(p
, schedule
->root
);
1112 forest
= isl_schedule_get_band_forest(schedule
);
1114 p
= print_band_list(p
, forest
);
1116 isl_band_list_free(forest
);
1121 void isl_schedule_dump(__isl_keep isl_schedule
*schedule
)
1123 isl_printer
*printer
;
1128 printer
= isl_printer_to_file(isl_schedule_get_ctx(schedule
), stderr
);
1129 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
1130 printer
= isl_printer_print_schedule(printer
, schedule
);
1132 isl_printer_free(printer
);
1135 /* Return a string representation of "schedule".
1136 * Print the schedule in flow format.
1138 __isl_give
char *isl_schedule_to_str(__isl_keep isl_schedule
*schedule
)
1140 isl_printer
*printer
;
1146 printer
= isl_printer_to_str(isl_schedule_get_ctx(schedule
));
1147 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_FLOW
);
1148 printer
= isl_printer_print_schedule(printer
, schedule
);
1149 s
= isl_printer_get_str(printer
);
1150 isl_printer_free(printer
);