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 /* Return the (parameter) space of the schedule, i.e., the space
181 * of the root domain.
183 __isl_give isl_space
*isl_schedule_get_space(
184 __isl_keep isl_schedule
*schedule
)
186 enum isl_schedule_node_type type
;
188 isl_union_set
*domain
;
193 isl_die(isl_schedule_get_ctx(schedule
), isl_error_invalid
,
194 "schedule tree representation not available",
196 type
= isl_schedule_tree_get_type(schedule
->root
);
197 if (type
!= isl_schedule_node_domain
)
198 isl_die(isl_schedule_get_ctx(schedule
), isl_error_internal
,
199 "root node not a domain node", return NULL
);
201 domain
= isl_schedule_tree_domain_get_domain(schedule
->root
);
202 space
= isl_union_set_get_space(domain
);
203 isl_union_set_free(domain
);
208 /* Return a pointer to the root of "schedule".
210 __isl_give isl_schedule_node
*isl_schedule_get_root(
211 __isl_keep isl_schedule
*schedule
)
214 isl_schedule_tree
*tree
;
215 isl_schedule_tree_list
*ancestors
;
221 isl_die(isl_schedule_get_ctx(schedule
), isl_error_invalid
,
222 "schedule tree representation not available",
225 ctx
= isl_schedule_get_ctx(schedule
);
226 tree
= isl_schedule_tree_copy(schedule
->root
);
227 schedule
= isl_schedule_copy(schedule
);
228 ancestors
= isl_schedule_tree_list_alloc(ctx
, 0);
229 return isl_schedule_node_alloc(schedule
, tree
, ancestors
, NULL
);
232 /* Set max_out to the maximal number of output dimensions over
235 static int update_max_out(__isl_take isl_map
*map
, void *user
)
238 int n_out
= isl_map_dim(map
, isl_dim_out
);
240 if (n_out
> *max_out
)
247 /* Internal data structure for map_pad_range.
249 * "max_out" is the maximal schedule dimension.
250 * "res" collects the results.
252 struct isl_pad_schedule_map_data
{
257 /* Pad the range of the given map with zeros to data->max_out and
258 * then add the result to data->res.
260 static int map_pad_range(__isl_take isl_map
*map
, void *user
)
262 struct isl_pad_schedule_map_data
*data
= user
;
264 int n_out
= isl_map_dim(map
, isl_dim_out
);
266 map
= isl_map_add_dims(map
, isl_dim_out
, data
->max_out
- n_out
);
267 for (i
= n_out
; i
< data
->max_out
; ++i
)
268 map
= isl_map_fix_si(map
, isl_dim_out
, i
, 0);
270 data
->res
= isl_union_map_add_map(data
->res
, map
);
277 /* Pad the ranges of the maps in the union map with zeros such they all have
278 * the same dimension.
280 static __isl_give isl_union_map
*pad_schedule_map(
281 __isl_take isl_union_map
*umap
)
283 struct isl_pad_schedule_map_data data
;
287 if (isl_union_map_n_map(umap
) <= 1)
291 if (isl_union_map_foreach_map(umap
, &update_max_out
, &data
.max_out
) < 0)
292 return isl_union_map_free(umap
);
294 data
.res
= isl_union_map_empty(isl_union_map_get_space(umap
));
295 if (isl_union_map_foreach_map(umap
, &map_pad_range
, &data
) < 0)
296 data
.res
= isl_union_map_free(data
.res
);
298 isl_union_map_free(umap
);
302 /* Return the domain of the root domain node of "schedule".
304 __isl_give isl_union_set
*isl_schedule_get_domain(
305 __isl_keep isl_schedule
*schedule
)
310 isl_die(isl_schedule_get_ctx(schedule
), isl_error_invalid
,
311 "schedule tree representation not available",
313 return isl_schedule_tree_domain_get_domain(schedule
->root
);
316 /* Return an isl_union_map representation of the schedule.
317 * If we still have access to the schedule tree, then we return
318 * an isl_union_map corresponding to the subtree schedule of the child
319 * of the root domain node. That is, we do not intersect the domain
320 * of the returned isl_union_map with the domain constraints.
321 * Otherwise, we must have removed it because we created a band forest.
322 * If so, we extract the isl_union_map from the forest.
323 * This reconstructed schedule map
324 * then needs to be padded with zeros to unify the schedule space
325 * since the result of isl_band_list_get_suffix_schedule may not have
326 * a unified schedule space.
328 __isl_give isl_union_map
*isl_schedule_get_map(__isl_keep isl_schedule
*sched
)
330 enum isl_schedule_node_type type
;
331 isl_schedule_node
*node
;
338 type
= isl_schedule_tree_get_type(sched
->root
);
339 if (type
!= isl_schedule_node_domain
)
340 isl_die(isl_schedule_get_ctx(sched
), isl_error_internal
,
341 "root node not a domain node", return NULL
);
343 node
= isl_schedule_get_root(sched
);
344 node
= isl_schedule_node_child(node
, 0);
345 umap
= isl_schedule_node_get_subtree_schedule_union_map(node
);
346 isl_schedule_node_free(node
);
351 umap
= isl_band_list_get_suffix_schedule(sched
->band_forest
);
352 return pad_schedule_map(umap
);
355 static __isl_give isl_band_list
*construct_band_list(
356 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
,
357 __isl_keep isl_band
*parent
);
359 /* Construct an isl_band structure from the given schedule tree node,
360 * which may be either a band node or a leaf node.
361 * In the latter case, construct a zero-dimensional band.
362 * "domain" is the universe set of the domain elements that reach "node".
363 * "parent" is the parent isl_band of the isl_band constructed
366 * In case of a band node, we copy the properties (except tilability,
367 * which is implicit in an isl_band) to the isl_band.
368 * We assume that the band node is not zero-dimensional.
369 * If the child of the band node is not a leaf node,
370 * then we extract the children of the isl_band from this child.
372 static __isl_give isl_band
*construct_band(__isl_take isl_schedule_node
*node
,
373 __isl_take isl_union_set
*domain
, __isl_keep isl_band
*parent
)
377 isl_band
*band
= NULL
;
378 isl_multi_union_pw_aff
*mupa
;
380 if (!node
|| !domain
)
383 ctx
= isl_schedule_node_get_ctx(node
);
384 band
= isl_band_alloc(ctx
);
388 band
->schedule
= node
->schedule
;
389 band
->parent
= parent
;
391 if (isl_schedule_node_get_type(node
) == isl_schedule_node_leaf
) {
393 band
->pma
= isl_union_pw_multi_aff_from_domain(domain
);
394 isl_schedule_node_free(node
);
398 band
->n
= isl_schedule_node_band_n_member(node
);
400 isl_die(ctx
, isl_error_unsupported
,
401 "zero-dimensional band nodes not supported",
403 band
->coincident
= isl_alloc_array(ctx
, int, band
->n
);
404 if (band
->n
&& !band
->coincident
)
406 for (i
= 0; i
< band
->n
; ++i
)
407 band
->coincident
[i
] =
408 isl_schedule_node_band_member_get_coincident(node
, i
);
409 mupa
= isl_schedule_node_band_get_partial_schedule(node
);
410 band
->pma
= isl_union_pw_multi_aff_from_multi_union_pw_aff(mupa
);
414 node
= isl_schedule_node_child(node
, 0);
415 if (isl_schedule_node_get_type(node
) == isl_schedule_node_leaf
) {
416 isl_schedule_node_free(node
);
417 isl_union_set_free(domain
);
421 band
->children
= construct_band_list(node
, domain
, band
);
423 return isl_band_free(band
);
427 isl_union_set_free(domain
);
428 isl_schedule_node_free(node
);
433 /* Construct a list of isl_band structures from the children of "node".
434 * "node" itself is a sequence or set node, so that each of the child nodes
435 * is a filter node and the list returned by node_construct_band_list
436 * consists of a single element.
437 * "domain" is the universe set of the domain elements that reach "node".
438 * "parent" is the parent isl_band of the isl_band structures constructed
441 static __isl_give isl_band_list
*construct_band_list_from_children(
442 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
,
443 __isl_keep isl_band
*parent
)
449 n
= isl_schedule_node_n_children(node
);
451 ctx
= isl_schedule_node_get_ctx(node
);
452 list
= isl_band_list_alloc(ctx
, 0);
453 for (i
= 0; i
< n
; ++i
) {
454 isl_schedule_node
*child
;
455 isl_band_list
*list_i
;
457 child
= isl_schedule_node_get_child(node
, i
);
458 list_i
= construct_band_list(child
, isl_union_set_copy(domain
),
460 list
= isl_band_list_concat(list
, list_i
);
463 isl_union_set_free(domain
);
464 isl_schedule_node_free(node
);
469 /* Construct an isl_band structure from the given sequence node
470 * (or set node that is treated as a sequence node).
471 * A single-dimensional band is created with as schedule for each of
472 * filters of the children, the corresponding child position.
473 * "domain" is the universe set of the domain elements that reach "node".
474 * "parent" is the parent isl_band of the isl_band constructed
477 static __isl_give isl_band_list
*construct_band_list_sequence(
478 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
,
479 __isl_keep isl_band
*parent
)
483 isl_band
*band
= NULL
;
485 isl_union_pw_multi_aff
*upma
;
487 if (!node
|| !domain
)
490 ctx
= isl_schedule_node_get_ctx(node
);
491 band
= isl_band_alloc(ctx
);
495 band
->schedule
= node
->schedule
;
496 band
->parent
= parent
;
498 band
->coincident
= isl_calloc_array(ctx
, int, band
->n
);
499 if (!band
->coincident
)
502 n
= isl_schedule_node_n_children(node
);
503 space
= isl_union_set_get_space(domain
);
504 upma
= isl_union_pw_multi_aff_empty(isl_space_copy(space
));
506 space
= isl_space_set_from_params(space
);
507 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
509 for (i
= 0; i
< n
; ++i
) {
510 isl_schedule_node
*child
;
511 isl_union_set
*filter
;
515 isl_union_pw_multi_aff
*upma_i
;
517 child
= isl_schedule_node_get_child(node
, i
);
518 filter
= isl_schedule_node_filter_get_filter(child
);
519 isl_schedule_node_free(child
);
520 filter
= isl_union_set_intersect(filter
,
521 isl_union_set_copy(domain
));
522 v
= isl_val_int_from_si(ctx
, i
);
523 vl
= isl_val_list_from_val(v
);
524 mv
= isl_multi_val_from_val_list(isl_space_copy(space
), vl
);
525 upma_i
= isl_union_pw_multi_aff_multi_val_on_domain(filter
, mv
);
526 upma
= isl_union_pw_multi_aff_union_add(upma
, upma_i
);
529 isl_space_free(space
);
535 band
->children
= construct_band_list_from_children(node
, domain
, band
);
537 band
= isl_band_free(band
);
538 return isl_band_list_from_band(band
);
540 isl_union_set_free(domain
);
541 isl_schedule_node_free(node
);
546 /* Construct a list of isl_band structures from "node" depending
547 * on the type of "node".
548 * "domain" is the universe set of the domain elements that reach "node".
549 * "parent" is the parent isl_band of the isl_band structures constructed
552 * If schedule_separate_components is set then set nodes are treated
553 * as sequence nodes. Otherwise, we directly extract an (implicitly
554 * parallel) list of isl_band structures.
556 * If "node" is a filter, then "domain" is updated by the filter.
558 static __isl_give isl_band_list
*construct_band_list(
559 __isl_take isl_schedule_node
*node
, __isl_take isl_union_set
*domain
,
560 __isl_keep isl_band
*parent
)
562 enum isl_schedule_node_type type
;
566 isl_union_set
*filter
;
568 if (!node
|| !domain
)
571 type
= isl_schedule_node_get_type(node
);
573 case isl_schedule_node_error
:
575 case isl_schedule_node_domain
:
576 isl_die(isl_schedule_node_get_ctx(node
), isl_error_invalid
,
577 "internal domain nodes not allowed", goto error
);
578 case isl_schedule_node_filter
:
579 filter
= isl_schedule_node_filter_get_filter(node
);
580 domain
= isl_union_set_intersect(domain
, filter
);
581 node
= isl_schedule_node_child(node
, 0);
582 return construct_band_list(node
, domain
, parent
);
583 case isl_schedule_node_set
:
584 ctx
= isl_schedule_node_get_ctx(node
);
585 if (isl_options_get_schedule_separate_components(ctx
))
586 return construct_band_list_sequence(node
, domain
,
589 return construct_band_list_from_children(node
, domain
,
591 case isl_schedule_node_sequence
:
592 return construct_band_list_sequence(node
, domain
, parent
);
593 case isl_schedule_node_leaf
:
594 case isl_schedule_node_band
:
595 band
= construct_band(node
, domain
, parent
);
596 list
= isl_band_list_from_band(band
);
602 isl_union_set_free(domain
);
603 isl_schedule_node_free(node
);
607 /* Return the roots of a band forest representation of the schedule.
608 * The band forest is constructed from the schedule tree,
609 * but once such a band forest is
610 * constructed, we forget about the original schedule tree since
611 * the user may modify the schedule through the band forest.
613 __isl_give isl_band_list
*isl_schedule_get_band_forest(
614 __isl_keep isl_schedule
*schedule
)
616 isl_schedule_node
*node
;
617 isl_union_set
*domain
;
621 if (schedule
->root
) {
622 node
= isl_schedule_get_root(schedule
);
623 domain
= isl_schedule_node_domain_get_domain(node
);
624 domain
= isl_union_set_universe(domain
);
625 node
= isl_schedule_node_child(node
, 0);
627 schedule
->band_forest
= construct_band_list(node
, domain
, NULL
);
628 schedule
->root
= isl_schedule_tree_free(schedule
->root
);
630 return isl_band_list_dup(schedule
->band_forest
);
633 /* Call "fn" on each band in the schedule in depth-first post-order.
635 int isl_schedule_foreach_band(__isl_keep isl_schedule
*sched
,
636 int (*fn
)(__isl_keep isl_band
*band
, void *user
), void *user
)
639 isl_band_list
*forest
;
644 forest
= isl_schedule_get_band_forest(sched
);
645 r
= isl_band_list_foreach_band(forest
, fn
, user
);
646 isl_band_list_free(forest
);
651 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
652 __isl_keep isl_band_list
*list
);
654 static __isl_give isl_printer
*print_band(__isl_take isl_printer
*p
,
655 __isl_keep isl_band
*band
)
657 isl_band_list
*children
;
659 p
= isl_printer_start_line(p
);
660 p
= isl_printer_print_union_pw_multi_aff(p
, band
->pma
);
661 p
= isl_printer_end_line(p
);
663 if (!isl_band_has_children(band
))
666 children
= isl_band_get_children(band
);
668 p
= isl_printer_indent(p
, 4);
669 p
= print_band_list(p
, children
);
670 p
= isl_printer_indent(p
, -4);
672 isl_band_list_free(children
);
677 static __isl_give isl_printer
*print_band_list(__isl_take isl_printer
*p
,
678 __isl_keep isl_band_list
*list
)
682 n
= isl_band_list_n_band(list
);
683 for (i
= 0; i
< n
; ++i
) {
685 band
= isl_band_list_get_band(list
, i
);
686 p
= print_band(p
, band
);
693 /* Print "schedule" to "p".
695 * If "schedule" was created from a schedule tree, then we print
696 * the schedule tree representation. Otherwise, we print
697 * the band forest representation.
699 __isl_give isl_printer
*isl_printer_print_schedule(__isl_take isl_printer
*p
,
700 __isl_keep isl_schedule
*schedule
)
702 isl_band_list
*forest
;
705 return isl_printer_free(p
);
708 return isl_printer_print_schedule_tree(p
, schedule
->root
);
710 forest
= isl_schedule_get_band_forest(schedule
);
712 p
= print_band_list(p
, forest
);
714 isl_band_list_free(forest
);
719 void isl_schedule_dump(__isl_keep isl_schedule
*schedule
)
721 isl_printer
*printer
;
726 printer
= isl_printer_to_file(isl_schedule_get_ctx(schedule
), stderr
);
727 printer
= isl_printer_set_yaml_style(printer
, ISL_YAML_STYLE_BLOCK
);
728 printer
= isl_printer_print_schedule(printer
, schedule
);
730 isl_printer_free(printer
);