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 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 isl_schedule
*schedule
;
43 if (isl_schedule_tree_get_type(tree
) != isl_schedule_node_domain
)
44 isl_die(isl_schedule_tree_get_ctx(tree
), isl_error_unsupported
,
45 "root of schedule tree should be a domain",
48 schedule
= isl_calloc_type(ctx
, isl_schedule
);
52 schedule
->leaf
.ctx
= ctx
;
55 schedule
->root
= tree
;
56 schedule
->leaf
.ref
= -1;
57 schedule
->leaf
.type
= isl_schedule_node_leaf
;
61 isl_schedule_tree_free(tree
);
65 /* Return a pointer to a schedule with as single node
66 * a domain node with the given domain.
68 __isl_give isl_schedule
*isl_schedule_from_domain(
69 __isl_take isl_union_set
*domain
)
72 isl_schedule_tree
*tree
;
74 ctx
= isl_union_set_get_ctx(domain
);
75 tree
= isl_schedule_tree_from_domain(domain
);
76 return isl_schedule_from_schedule_tree(ctx
, tree
);
79 /* Return a pointer to a schedule with as single node
80 * a domain node with an empty domain.
82 __isl_give isl_schedule
*isl_schedule_empty(__isl_take isl_space
*space
)
84 return isl_schedule_from_domain(isl_union_set_empty(space
));
87 /* Return a new reference to "sched".
89 __isl_give isl_schedule
*isl_schedule_copy(__isl_keep isl_schedule
*sched
)
98 /* Return an isl_schedule that is equal to "schedule" and that has only
101 * We only need and support this function when the schedule is represented
102 * as a schedule tree.
104 __isl_give isl_schedule
*isl_schedule_cow(__isl_take isl_schedule
*schedule
)
107 isl_schedule_tree
*tree
;
111 if (schedule
->ref
== 1)
114 ctx
= isl_schedule_get_ctx(schedule
);
116 isl_die(ctx
, isl_error_internal
,
117 "only for schedule tree based schedules",
118 return isl_schedule_free(schedule
));
120 tree
= isl_schedule_tree_copy(schedule
->root
);
121 return isl_schedule_from_schedule_tree(ctx
, tree
);
124 __isl_null isl_schedule
*isl_schedule_free(__isl_take isl_schedule
*sched
)
129 if (--sched
->ref
> 0)
132 isl_band_list_free(sched
->band_forest
);
133 isl_schedule_tree_free(sched
->root
);
134 isl_ctx_deref(sched
->leaf
.ctx
);
139 /* Replace the root of "schedule" by "tree".
141 __isl_give isl_schedule
*isl_schedule_set_root(
142 __isl_take isl_schedule
*schedule
, __isl_take isl_schedule_tree
*tree
)
144 if (!schedule
|| !tree
)
146 if (schedule
->root
== tree
) {
147 isl_schedule_tree_free(tree
);
151 schedule
= isl_schedule_cow(schedule
);
154 isl_schedule_tree_free(schedule
->root
);
155 schedule
->root
= tree
;
159 isl_schedule_free(schedule
);
160 isl_schedule_tree_free(tree
);
164 isl_ctx
*isl_schedule_get_ctx(__isl_keep isl_schedule
*schedule
)
166 return schedule
? schedule
->leaf
.ctx
: NULL
;
169 /* Return a pointer to the leaf of "schedule".
171 * Even though these leaves are not reference counted, we still
172 * indicate that this function does not return a copy.
174 __isl_keep isl_schedule_tree
*isl_schedule_peek_leaf(
175 __isl_keep isl_schedule
*schedule
)
177 return schedule
? &schedule
->leaf
: NULL
;
180 /* Are "schedule1" and "schedule2" obviously equal to each other?
182 int isl_schedule_plain_is_equal(__isl_keep isl_schedule
*schedule1
,
183 __isl_keep isl_schedule
*schedule2
)
185 if (!schedule1
|| !schedule2
)
187 if (schedule1
== schedule2
)
189 return isl_schedule_tree_plain_is_equal(schedule1
->root
,
193 /* Return the (parameter) space of the schedule, i.e., the space
194 * of the root domain.
196 __isl_give isl_space
*isl_schedule_get_space(
197 __isl_keep isl_schedule
*schedule
)
199 enum isl_schedule_node_type type
;
201 isl_union_set
*domain
;
206 isl_die(isl_schedule_get_ctx(schedule
), isl_error_invalid
,
207 "schedule tree representation not available",
209 type
= isl_schedule_tree_get_type(schedule
->root
);
210 if (type
!= isl_schedule_node_domain
)
211 isl_die(isl_schedule_get_ctx(schedule
), isl_error_internal
,
212 "root node not a domain node", return NULL
);
214 domain
= isl_schedule_tree_domain_get_domain(schedule
->root
);
215 space
= isl_union_set_get_space(domain
);
216 isl_union_set_free(domain
);
221 /* Return a pointer to the root of "schedule".
223 __isl_give isl_schedule_node
*isl_schedule_get_root(
224 __isl_keep isl_schedule
*schedule
)
227 isl_schedule_tree
*tree
;
228 isl_schedule_tree_list
*ancestors
;
234 isl_die(isl_schedule_get_ctx(schedule
), isl_error_invalid
,
235 "schedule tree representation not available",
238 ctx
= isl_schedule_get_ctx(schedule
);
239 tree
= isl_schedule_tree_copy(schedule
->root
);
240 schedule
= isl_schedule_copy(schedule
);
241 ancestors
= isl_schedule_tree_list_alloc(ctx
, 0);
242 return isl_schedule_node_alloc(schedule
, tree
, ancestors
, NULL
);
245 /* Set max_out to the maximal number of output dimensions over
248 static int update_max_out(__isl_take isl_map
*map
, void *user
)
251 int n_out
= isl_map_dim(map
, isl_dim_out
);
253 if (n_out
> *max_out
)
260 /* Internal data structure for map_pad_range.
262 * "max_out" is the maximal schedule dimension.
263 * "res" collects the results.
265 struct isl_pad_schedule_map_data
{
270 /* Pad the range of the given map with zeros to data->max_out and
271 * then add the result to data->res.
273 static int map_pad_range(__isl_take isl_map
*map
, void *user
)
275 struct isl_pad_schedule_map_data
*data
= user
;
277 int n_out
= isl_map_dim(map
, isl_dim_out
);
279 map
= isl_map_add_dims(map
, isl_dim_out
, data
->max_out
- n_out
);
280 for (i
= n_out
; i
< data
->max_out
; ++i
)
281 map
= isl_map_fix_si(map
, isl_dim_out
, i
, 0);
283 data
->res
= isl_union_map_add_map(data
->res
, map
);
290 /* Pad the ranges of the maps in the union map with zeros such they all have
291 * the same dimension.
293 static __isl_give isl_union_map
*pad_schedule_map(
294 __isl_take isl_union_map
*umap
)
296 struct isl_pad_schedule_map_data data
;
300 if (isl_union_map_n_map(umap
) <= 1)
304 if (isl_union_map_foreach_map(umap
, &update_max_out
, &data
.max_out
) < 0)
305 return isl_union_map_free(umap
);
307 data
.res
= isl_union_map_empty(isl_union_map_get_space(umap
));
308 if (isl_union_map_foreach_map(umap
, &map_pad_range
, &data
) < 0)
309 data
.res
= isl_union_map_free(data
.res
);
311 isl_union_map_free(umap
);
315 /* Return the domain of the root domain node of "schedule".
317 __isl_give isl_union_set
*isl_schedule_get_domain(
318 __isl_keep isl_schedule
*schedule
)
323 isl_die(isl_schedule_get_ctx(schedule
), isl_error_invalid
,
324 "schedule tree representation not available",
326 return isl_schedule_tree_domain_get_domain(schedule
->root
);
329 /* Traverse all nodes of "sched" in depth first preorder.
331 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
332 * If "fn" returns 0 on any of the nodes, then the subtree rooted
333 * at that node is skipped.
335 * Return 0 on success and -1 on failure.
337 int isl_schedule_foreach_schedule_node(__isl_keep isl_schedule
*sched
,
338 int (*fn
)(__isl_keep isl_schedule_node
*node
, void *user
), void *user
)
340 isl_schedule_node
*node
;
346 node
= isl_schedule_get_root(sched
);
347 r
= isl_schedule_node_foreach_descendant(node
, fn
, user
);
348 isl_schedule_node_free(node
);
353 /* Traverse the node of "sched" in depth first postorder,
354 * allowing the user to modify the visited node.
355 * The traversal continues from the node returned by the callback function.
356 * It is the responsibility of the user to ensure that this does not
357 * lead to an infinite loop. It is safest to always return a pointer
358 * to the same position (same ancestors and child positions) as the input node.
360 __isl_give isl_schedule
*isl_schedule_map_schedule_node(
361 __isl_take isl_schedule
*schedule
,
362 __isl_give isl_schedule_node
*(*fn
)(
363 __isl_take isl_schedule_node
*node
, void *user
), void *user
)
365 isl_schedule_node
*node
;
367 node
= isl_schedule_get_root(schedule
);
368 isl_schedule_free(schedule
);
370 node
= isl_schedule_node_map_descendant(node
, fn
, user
);
371 schedule
= isl_schedule_node_get_schedule(node
);
372 isl_schedule_node_free(node
);
377 /* Wrapper around isl_schedule_node_reset_user for use as
378 * an isl_schedule_map_schedule_node callback.
380 static __isl_give isl_schedule_node
*reset_user(
381 __isl_take isl_schedule_node
*node
, void *user
)
383 return isl_schedule_node_reset_user(node
);
386 /* Reset the user pointer on all identifiers of parameters and tuples
387 * in the schedule "schedule".
389 __isl_give isl_schedule
*isl_schedule_reset_user(
390 __isl_take isl_schedule
*schedule
)
392 return isl_schedule_map_schedule_node(schedule
, &reset_user
, NULL
);
395 /* Wrapper around isl_schedule_node_align_params for use as
396 * an isl_schedule_map_schedule_node callback.
398 static __isl_give isl_schedule_node
*align_params(
399 __isl_take isl_schedule_node
*node
, void *user
)
401 isl_space
*space
= user
;
403 return isl_schedule_node_align_params(node
, isl_space_copy(space
));
406 /* Align the parameters of all nodes in schedule "schedule"
407 * to those of "space".
409 __isl_give isl_schedule
*isl_schedule_align_params(
410 __isl_take isl_schedule
*schedule
, __isl_take isl_space
*space
)
412 schedule
= isl_schedule_map_schedule_node(schedule
,
413 &align_params
, space
);
414 isl_space_free(space
);
418 /* Wrapper around isl_schedule_node_pullback_union_pw_multi_aff for use as
419 * an isl_schedule_map_schedule_node callback.
421 static __isl_give isl_schedule_node
*pullback_upma(
422 __isl_take isl_schedule_node
*node
, void *user
)
424 isl_union_pw_multi_aff
*upma
= user
;
426 return isl_schedule_node_pullback_union_pw_multi_aff(node
,
427 isl_union_pw_multi_aff_copy(upma
));
430 /* Compute the pullback of "schedule" by the function represented by "upma".
431 * In other words, plug in "upma" in the iteration domains of "schedule".
433 * The schedule tree is not allowed to contain any expansion nodes.
435 __isl_give isl_schedule
*isl_schedule_pullback_union_pw_multi_aff(
436 __isl_take isl_schedule
*schedule
,
437 __isl_take isl_union_pw_multi_aff
*upma
)
439 schedule
= isl_schedule_map_schedule_node(schedule
,
440 &pullback_upma
, upma
);
441 isl_union_pw_multi_aff_free(upma
);
445 /* Intersect the domain of the schedule "schedule" with "domain".
447 __isl_give isl_schedule
*isl_schedule_intersect_domain(
448 __isl_take isl_schedule
*schedule
, __isl_take isl_union_set
*domain
)
450 enum isl_schedule_node_type root_type
;
451 isl_schedule_node
*node
;
453 if (!schedule
|| !domain
)
456 root_type
= isl_schedule_tree_get_type(schedule
->root
);
457 if (root_type
!= isl_schedule_node_domain
)
458 isl_die(isl_schedule_get_ctx(schedule
), isl_error_internal
,
459 "root node not a domain node", goto error
);
461 node
= isl_schedule_get_root(schedule
);
462 isl_schedule_free(schedule
);
463 node
= isl_schedule_node_domain_intersect_domain(node
, domain
);
464 schedule
= isl_schedule_node_get_schedule(node
);
465 isl_schedule_node_free(node
);
469 isl_schedule_free(schedule
);
470 isl_union_set_free(domain
);
474 /* Return an isl_union_map representation of the schedule.
475 * If we still have access to the schedule tree, then we return
476 * an isl_union_map corresponding to the subtree schedule of the child
477 * of the root domain node. That is, we do not intersect the domain
478 * of the returned isl_union_map with the domain constraints.
479 * Otherwise, we must have removed it because we created a band forest.
480 * If so, we extract the isl_union_map from the forest.
481 * This reconstructed schedule map
482 * then needs to be padded with zeros to unify the schedule space
483 * since the result of isl_band_list_get_suffix_schedule may not have
484 * a unified schedule space.
486 __isl_give isl_union_map
*isl_schedule_get_map(__isl_keep isl_schedule
*sched
)
488 enum isl_schedule_node_type type
;
489 isl_schedule_node
*node
;
496 type
= isl_schedule_tree_get_type(sched
->root
);
497 if (type
!= isl_schedule_node_domain
)
498 isl_die(isl_schedule_get_ctx(sched
), isl_error_internal
,
499 "root node not a domain node", return NULL
);
501 node
= isl_schedule_get_root(sched
);
502 node
= isl_schedule_node_child(node
, 0);
503 umap
= isl_schedule_node_get_subtree_schedule_union_map(node
);
504 isl_schedule_node_free(node
);
509 umap
= isl_band_list_get_suffix_schedule(sched
->band_forest
);
510 return pad_schedule_map(umap
);
513 static __isl_give isl_band_list
*construct_band_list(
514 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
,
515 __isl_keep isl_band
*parent
);
517 /* Construct an isl_band structure from the given schedule tree node,
518 * which may be either a band node or a leaf node.
519 * In the latter case, construct a zero-dimensional band.
520 * "domain" is the universe set of the domain elements that reach "node".
521 * "parent" is the parent isl_band of the isl_band constructed
524 * In case of a band node, we copy the properties (except tilability,
525 * which is implicit in an isl_band) to the isl_band.
526 * We assume that the band node is not zero-dimensional.
527 * If the child of the band node is not a leaf node,
528 * then we extract the children of the isl_band from this child.
530 static __isl_give isl_band
*construct_band(__isl_take isl_schedule_node
*node
,
531 __isl_take isl_union_set
*domain
, __isl_keep isl_band
*parent
)
535 isl_band
*band
= NULL
;
536 isl_multi_union_pw_aff
*mupa
;
538 if (!node
|| !domain
)
541 ctx
= isl_schedule_node_get_ctx(node
);
542 band
= isl_band_alloc(ctx
);
546 band
->schedule
= node
->schedule
;
547 band
->parent
= parent
;
549 if (isl_schedule_node_get_type(node
) == isl_schedule_node_leaf
) {
551 band
->pma
= isl_union_pw_multi_aff_from_domain(domain
);
552 isl_schedule_node_free(node
);
556 band
->n
= isl_schedule_node_band_n_member(node
);
558 isl_die(ctx
, isl_error_unsupported
,
559 "zero-dimensional band nodes not supported",
561 band
->coincident
= isl_alloc_array(ctx
, int, band
->n
);
562 if (band
->n
&& !band
->coincident
)
564 for (i
= 0; i
< band
->n
; ++i
)
565 band
->coincident
[i
] =
566 isl_schedule_node_band_member_get_coincident(node
, i
);
567 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
568 band
->pma
= isl_union_pw_multi_aff_from_multi_union_pw_aff(mupa
);
572 node
= isl_schedule_node_child(node
, 0);
573 if (isl_schedule_node_get_type(node
) == isl_schedule_node_leaf
) {
574 isl_schedule_node_free(node
);
575 isl_union_set_free(domain
);
579 band
->children
= construct_band_list(node
, domain
, band
);
581 return isl_band_free(band
);
585 isl_union_set_free(domain
);
586 isl_schedule_node_free(node
);
591 /* Construct a list of isl_band structures from the children of "node".
592 * "node" itself is a sequence or set node, so that each of the child nodes
593 * is a filter node and the list returned by node_construct_band_list
594 * consists of a single element.
595 * "domain" is the universe set of the domain elements that reach "node".
596 * "parent" is the parent isl_band of the isl_band structures constructed
599 static __isl_give isl_band_list
*construct_band_list_from_children(
600 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
,
601 __isl_keep isl_band
*parent
)
607 n
= isl_schedule_node_n_children(node
);
609 ctx
= isl_schedule_node_get_ctx(node
);
610 list
= isl_band_list_alloc(ctx
, 0);
611 for (i
= 0; i
< n
; ++i
) {
612 isl_schedule_node
*child
;
613 isl_band_list
*list_i
;
615 child
= isl_schedule_node_get_child(node
, i
);
616 list_i
= construct_band_list(child
, isl_union_set_copy(domain
),
618 list
= isl_band_list_concat(list
, list_i
);
621 isl_union_set_free(domain
);
622 isl_schedule_node_free(node
);
627 /* Construct an isl_band structure from the given sequence node
628 * (or set node that is treated as a sequence node).
629 * A single-dimensional band is created with as schedule for each of
630 * filters of the children, the corresponding child position.
631 * "domain" is the universe set of the domain elements that reach "node".
632 * "parent" is the parent isl_band of the isl_band constructed
635 static __isl_give isl_band_list
*construct_band_list_sequence(
636 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
,
637 __isl_keep isl_band
*parent
)
641 isl_band
*band
= NULL
;
643 isl_union_pw_multi_aff
*upma
;
645 if (!node
|| !domain
)
648 ctx
= isl_schedule_node_get_ctx(node
);
649 band
= isl_band_alloc(ctx
);
653 band
->schedule
= node
->schedule
;
654 band
->parent
= parent
;
656 band
->coincident
= isl_calloc_array(ctx
, int, band
->n
);
657 if (!band
->coincident
)
660 n
= isl_schedule_node_n_children(node
);
661 space
= isl_union_set_get_space(domain
);
662 upma
= isl_union_pw_multi_aff_empty(isl_space_copy(space
));
664 space
= isl_space_set_from_params(space
);
665 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
667 for (i
= 0; i
< n
; ++i
) {
668 isl_schedule_node
*child
;
669 isl_union_set
*filter
;
673 isl_union_pw_multi_aff
*upma_i
;
675 child
= isl_schedule_node_get_child(node
, i
);
676 filter
= isl_schedule_node_filter_get_filter(child
);
677 isl_schedule_node_free(child
);
678 filter
= isl_union_set_intersect(filter
,
679 isl_union_set_copy(domain
));
680 v
= isl_val_int_from_si(ctx
, i
);
681 vl
= isl_val_list_from_val(v
);
682 mv
= isl_multi_val_from_val_list(isl_space_copy(space
), vl
);
683 upma_i
= isl_union_pw_multi_aff_multi_val_on_domain(filter
, mv
);
684 upma
= isl_union_pw_multi_aff_union_add(upma
, upma_i
);
687 isl_space_free(space
);
693 band
->children
= construct_band_list_from_children(node
, domain
, band
);
695 band
= isl_band_free(band
);
696 return isl_band_list_from_band(band
);
698 isl_union_set_free(domain
);
699 isl_schedule_node_free(node
);
704 /* Construct a list of isl_band structures from "node" depending
705 * on the type of "node".
706 * "domain" is the universe set of the domain elements that reach "node".
707 * "parent" is the parent isl_band of the isl_band structures constructed
710 * If schedule_separate_components is set then set nodes are treated
711 * as sequence nodes. Otherwise, we directly extract an (implicitly
712 * parallel) list of isl_band structures.
714 * If "node" is a filter, then "domain" is updated by the filter.
716 static __isl_give isl_band_list
*construct_band_list(
717 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
,
718 __isl_keep isl_band
*parent
)
720 enum isl_schedule_node_type type
;
724 isl_union_set
*filter
;
726 if (!node
|| !domain
)
729 type
= isl_schedule_node_get_type(node
);
731 case isl_schedule_node_error
:
733 case isl_schedule_node_context
:
734 isl_die(isl_schedule_node_get_ctx(node
), isl_error_unsupported
,
735 "context nodes not supported", goto error
);
736 case isl_schedule_node_domain
:
737 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
738 "internal domain nodes not allowed", goto error
);
739 case isl_schedule_node_expansion
:
740 isl_die(isl_schedule_node_get_ctx(node
), isl_error_unsupported
,
741 "expansion nodes not supported", goto error
);
742 case isl_schedule_node_filter
:
743 filter
= isl_schedule_node_filter_get_filter(node
);
744 domain
= isl_union_set_intersect(domain
, filter
);
745 node
= isl_schedule_node_child(node
, 0);
746 return construct_band_list(node
, domain
, parent
);
747 case isl_schedule_node_set
:
748 ctx
= isl_schedule_node_get_ctx(node
);
749 if (isl_options_get_schedule_separate_components(ctx
))
750 return construct_band_list_sequence(node
, domain
,
753 return construct_band_list_from_children(node
, domain
,
755 case isl_schedule_node_sequence
:
756 return construct_band_list_sequence(node
, domain
, parent
);
757 case isl_schedule_node_leaf
:
758 case isl_schedule_node_band
:
759 band
= construct_band(node
, domain
, parent
);
760 list
= isl_band_list_from_band(band
);
766 isl_union_set_free(domain
);
767 isl_schedule_node_free(node
);
771 /* Return the roots of a band forest representation of the schedule.
772 * The band forest is constructed from the schedule tree,
773 * but once such a band forest is
774 * constructed, we forget about the original schedule tree since
775 * the user may modify the schedule through the band forest.
777 __isl_give isl_band_list
*isl_schedule_get_band_forest(
778 __isl_keep isl_schedule
*schedule
)
780 isl_schedule_node
*node
;
781 isl_union_set
*domain
;
785 if (schedule
->root
) {
786 node
= isl_schedule_get_root(schedule
);
787 domain
= isl_schedule_node_domain_get_domain(node
);
788 domain
= isl_union_set_universe(domain
);
789 node
= isl_schedule_node_child(node
, 0);
791 schedule
->band_forest
= construct_band_list(node
, domain
, NULL
);
792 schedule
->root
= isl_schedule_tree_free(schedule
->root
);
794 return isl_band_list_dup(schedule
->band_forest
);
797 /* Call "fn" on each band in the schedule in depth-first post-order.
799 int isl_schedule_foreach_band(__isl_keep isl_schedule
*sched
,
800 int (*fn
)(__isl_keep isl_band
*band
, void *user
), void *user
)
803 isl_band_list
*forest
;
808 forest
= isl_schedule_get_band_forest(sched
);
809 r
= isl_band_list_foreach_band(forest
, fn
, user
);
810 isl_band_list_free(forest
);
815 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
816 __isl_keep isl_band_list
*list
);
818 static __isl_give isl_printer
*print_band(__isl_take isl_printer
*p
,
819 __isl_keep isl_band
*band
)
821 isl_band_list
*children
;
823 p
= isl_printer_start_line(p
);
824 p
= isl_printer_print_union_pw_multi_aff(p
, band
->pma
);
825 p
= isl_printer_end_line(p
);
827 if (!isl_band_has_children(band
))
830 children
= isl_band_get_children(band
);
832 p
= isl_printer_indent(p
, 4);
833 p
= print_band_list(p
, children
);
834 p
= isl_printer_indent(p
, -4);
836 isl_band_list_free(children
);
841 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
842 __isl_keep isl_band_list
*list
)
846 n
= isl_band_list_n_band(list
);
847 for (i
= 0; i
< n
; ++i
) {
849 band
= isl_band_list_get_band(list
, i
);
850 p
= print_band(p
, band
);
857 /* Insert a band node with partial schedule "partial" between the domain
858 * root node of "schedule" and its single child.
859 * Return a pointer to the updated schedule.
861 * If any of the nodes in the tree depend on the set of outer band nodes
862 * then we refuse to insert the band node.
864 __isl_give isl_schedule
*isl_schedule_insert_partial_schedule(
865 __isl_take isl_schedule
*schedule
,
866 __isl_take isl_multi_union_pw_aff
*partial
)
868 isl_schedule_node
*node
;
871 node
= isl_schedule_get_root(schedule
);
872 isl_schedule_free(schedule
);
875 if (isl_schedule_node_get_type(node
) != isl_schedule_node_domain
)
876 isl_die(isl_schedule_node_get_ctx(node
), isl_error_internal
,
877 "root node not a domain node", goto error
);
879 node
= isl_schedule_node_child(node
, 0);
880 anchored
= isl_schedule_node_is_subtree_anchored(node
);
884 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
885 "cannot insert band node in anchored subtree",
887 node
= isl_schedule_node_insert_partial_schedule(node
, partial
);
889 schedule
= isl_schedule_node_get_schedule(node
);
890 isl_schedule_node_free(node
);
894 isl_schedule_node_free(node
);
895 isl_multi_union_pw_aff_free(partial
);
899 /* Insert a context node with constraints "context" between the domain
900 * root node of "schedule" and its single child.
901 * Return a pointer to the updated schedule.
903 __isl_give isl_schedule
*isl_schedule_insert_context(
904 __isl_take isl_schedule
*schedule
, __isl_take isl_set
*context
)
906 isl_schedule_node
*node
;
908 node
= isl_schedule_get_root(schedule
);
909 isl_schedule_free(schedule
);
910 node
= isl_schedule_node_child(node
, 0);
911 node
= isl_schedule_node_insert_context(node
, context
);
912 schedule
= isl_schedule_node_get_schedule(node
);
913 isl_schedule_node_free(node
);
918 /* Return a tree with as top-level node a filter corresponding to "filter" and
919 * as child, the (single) child of "tree".
920 * However, if this single child is of type "type", then the filter is inserted
921 * in the children of this single child instead.
923 static __isl_give isl_schedule_tree
*insert_filter_in_child_of_type(
924 __isl_take isl_schedule_tree
*tree
, __isl_take isl_union_set
*filter
,
925 enum isl_schedule_node_type type
)
927 if (!isl_schedule_tree_has_children(tree
)) {
928 isl_schedule_tree_free(tree
);
929 return isl_schedule_tree_from_filter(filter
);
931 tree
= isl_schedule_tree_child(tree
, 0);
934 if (isl_schedule_tree_get_type(tree
) == type
)
935 tree
= isl_schedule_tree_children_insert_filter(tree
, filter
);
937 tree
= isl_schedule_tree_insert_filter(tree
, filter
);
942 /* Construct a schedule that combines the schedules "schedule1" and "schedule2"
943 * with a top-level node (underneath the domain node) of type "type",
944 * either isl_schedule_node_sequence or isl_schedule_node_set.
945 * The domains of the two schedules are assumed to be disjoint.
947 * The new schedule has as domain the union of the domains of the two
948 * schedules. The child of the domain node is a node of type "type"
949 * with two filters corresponding to the domains of the input schedules.
950 * If one (or both) of the top-level nodes of the two schedules is itself
951 * of type "type", then the filter is pushed into the children of that
952 * node and the sequence of set is flattened.
954 __isl_give isl_schedule
*isl_schedule_pair(enum isl_schedule_node_type type
,
955 __isl_take isl_schedule
*schedule1
, __isl_take isl_schedule
*schedule2
)
959 enum isl_schedule_node_type root_type
;
960 isl_schedule_tree
*tree1
, *tree2
;
961 isl_union_set
*filter1
, *filter2
, *domain
;
963 if (!schedule1
|| !schedule2
)
966 root_type
= isl_schedule_tree_get_type(schedule1
->root
);
967 if (root_type
!= isl_schedule_node_domain
)
968 isl_die(isl_schedule_get_ctx(schedule1
), isl_error_internal
,
969 "root node not a domain node", goto error
);
970 root_type
= isl_schedule_tree_get_type(schedule2
->root
);
971 if (root_type
!= isl_schedule_node_domain
)
972 isl_die(isl_schedule_get_ctx(schedule1
), isl_error_internal
,
973 "root node not a domain node", goto error
);
975 ctx
= isl_schedule_get_ctx(schedule1
);
976 tree1
= isl_schedule_tree_copy(schedule1
->root
);
977 filter1
= isl_schedule_tree_domain_get_domain(tree1
);
978 tree2
= isl_schedule_tree_copy(schedule2
->root
);
979 filter2
= isl_schedule_tree_domain_get_domain(tree2
);
981 isl_schedule_free(schedule1
);
982 isl_schedule_free(schedule2
);
984 disjoint
= isl_union_set_is_disjoint(filter1
, filter2
);
986 filter1
= isl_union_set_free(filter1
);
988 isl_die(ctx
, isl_error_invalid
,
989 "schedule domains not disjoint",
990 filter1
= isl_union_set_free(filter1
));
992 domain
= isl_union_set_union(isl_union_set_copy(filter1
),
993 isl_union_set_copy(filter2
));
994 filter1
= isl_union_set_gist(filter1
, isl_union_set_copy(domain
));
995 filter2
= isl_union_set_gist(filter2
, isl_union_set_copy(domain
));
997 tree1
= insert_filter_in_child_of_type(tree1
, filter1
, type
);
998 tree2
= insert_filter_in_child_of_type(tree2
, filter2
, type
);
1000 tree1
= isl_schedule_tree_from_pair(type
, tree1
, tree2
);
1001 tree1
= isl_schedule_tree_insert_domain(tree1
, domain
);
1003 return isl_schedule_from_schedule_tree(ctx
, tree1
);
1005 isl_schedule_free(schedule1
);
1006 isl_schedule_free(schedule2
);
1010 /* Construct a schedule that combines the schedules "schedule1" and "schedule2"
1011 * through a sequence node.
1012 * The domains of the input schedules are assumed to be disjoint.
1014 __isl_give isl_schedule
*isl_schedule_sequence(
1015 __isl_take isl_schedule
*schedule1
, __isl_take isl_schedule
*schedule2
)
1017 return isl_schedule_pair(isl_schedule_node_sequence
,
1018 schedule1
, schedule2
);
1021 /* Construct a schedule that combines the schedules "schedule1" and "schedule2"
1022 * through a set node.
1023 * The domains of the input schedules are assumed to be disjoint.
1025 __isl_give isl_schedule
*isl_schedule_set(
1026 __isl_take isl_schedule
*schedule1
, __isl_take isl_schedule
*schedule2
)
1028 return isl_schedule_pair(isl_schedule_node_set
, schedule1
, schedule2
);
1031 /* Print "schedule" to "p".
1033 * If "schedule" was created from a schedule tree, then we print
1034 * the schedule tree representation. Otherwise, we print
1035 * the band forest representation.
1037 __isl_give isl_printer
*isl_printer_print_schedule(__isl_take isl_printer
*p
,
1038 __isl_keep isl_schedule
*schedule
)
1040 isl_band_list
*forest
;
1043 return isl_printer_free(p
);
1046 return isl_printer_print_schedule_tree(p
, schedule
->root
);
1048 forest
= isl_schedule_get_band_forest(schedule
);
1050 p
= print_band_list(p
, forest
);
1052 isl_band_list_free(forest
);
1057 void isl_schedule_dump(__isl_keep isl_schedule
*schedule
)
1059 isl_printer
*printer
;
1064 printer
= isl_printer_to_file(isl_schedule_get_ctx(schedule
), stderr
);
1065 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
1066 printer
= isl_printer_print_schedule(printer
, schedule
);
1068 isl_printer_free(printer
);