add more test cases from CLooG
[isl.git] / isl_schedule.c
bloba0f6cb5d9b97fb7094089e2addc25679343dceca
1 /*
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,
9 * 91893 Orsay, France
10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
13 #include <isl/ctx.h>
14 #include <isl_aff_private.h>
15 #include <isl/map.h>
16 #include <isl/set.h>
17 #include <isl/schedule.h>
18 #include <isl/schedule_node.h>
19 #include <isl_sort.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
34 * is still alive.
36 __isl_give isl_schedule *isl_schedule_from_schedule_tree(isl_ctx *ctx,
37 __isl_take isl_schedule_tree *tree)
39 isl_schedule *schedule;
41 if (!tree)
42 return NULL;
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",
46 goto error);
48 schedule = isl_calloc_type(ctx, isl_schedule);
49 if (!schedule)
50 goto error;
52 schedule->leaf.ctx = ctx;
53 isl_ctx_ref(ctx);
54 schedule->ref = 1;
55 schedule->root = tree;
56 schedule->leaf.ref = -1;
57 schedule->leaf.type = isl_schedule_node_leaf;
59 return schedule;
60 error:
61 isl_schedule_tree_free(tree);
62 return NULL;
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)
71 isl_ctx *ctx;
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)
91 if (!sched)
92 return NULL;
94 sched->ref++;
95 return sched;
98 /* Return an isl_schedule that is equal to "schedule" and that has only
99 * a single reference.
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)
106 isl_ctx *ctx;
107 isl_schedule_tree *tree;
109 if (!schedule)
110 return NULL;
111 if (schedule->ref == 1)
112 return schedule;
114 ctx = isl_schedule_get_ctx(schedule);
115 if (!schedule->root)
116 isl_die(ctx, isl_error_internal,
117 "only for schedule tree based schedules",
118 return isl_schedule_free(schedule));
119 schedule->ref--;
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)
126 if (!sched)
127 return NULL;
129 if (--sched->ref > 0)
130 return NULL;
132 isl_band_list_free(sched->band_forest);
133 isl_schedule_tree_free(sched->root);
134 isl_ctx_deref(sched->leaf.ctx);
135 free(sched);
136 return NULL;
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)
145 goto error;
146 if (schedule->root == tree) {
147 isl_schedule_tree_free(tree);
148 return schedule;
151 schedule = isl_schedule_cow(schedule);
152 if (!schedule)
153 goto error;
154 isl_schedule_tree_free(schedule->root);
155 schedule->root = tree;
157 return schedule;
158 error:
159 isl_schedule_free(schedule);
160 isl_schedule_tree_free(tree);
161 return NULL;
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)
186 return -1;
187 if (schedule1 == schedule2)
188 return 1;
189 return isl_schedule_tree_plain_is_equal(schedule1->root,
190 schedule2->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;
200 isl_space *space;
201 isl_union_set *domain;
203 if (!schedule)
204 return NULL;
205 if (!schedule->root)
206 isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
207 "schedule tree representation not available",
208 return NULL);
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);
218 return space;
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)
226 isl_ctx *ctx;
227 isl_schedule_tree *tree;
228 isl_schedule_tree_list *ancestors;
230 if (!schedule)
231 return NULL;
233 if (!schedule->root)
234 isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
235 "schedule tree representation not available",
236 return NULL);
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
246 * all maps.
248 static int update_max_out(__isl_take isl_map *map, void *user)
250 int *max_out = user;
251 int n_out = isl_map_dim(map, isl_dim_out);
253 if (n_out > *max_out)
254 *max_out = n_out;
256 isl_map_free(map);
257 return 0;
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 {
266 int max_out;
267 isl_union_map *res;
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;
276 int i;
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);
284 if (!data->res)
285 return -1;
287 return 0;
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;
298 if (!umap)
299 return NULL;
300 if (isl_union_map_n_map(umap) <= 1)
301 return umap;
303 data.max_out = 0;
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);
312 return data.res;
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)
320 if (!schedule)
321 return NULL;
322 if (!schedule->root)
323 isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
324 "schedule tree representation not available",
325 return NULL);
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;
341 int r;
343 if (!sched)
344 return -1;
346 node = isl_schedule_get_root(sched);
347 r = isl_schedule_node_foreach_descendant(node, fn, user);
348 isl_schedule_node_free(node);
350 return r;
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);
374 return schedule;
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);
415 return schedule;
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 __isl_give isl_schedule *isl_schedule_pullback_union_pw_multi_aff(
434 __isl_take isl_schedule *schedule,
435 __isl_take isl_union_pw_multi_aff *upma)
437 schedule = isl_schedule_map_schedule_node(schedule,
438 &pullback_upma, upma);
439 isl_union_pw_multi_aff_free(upma);
440 return schedule;
443 /* Intersect the domain of the schedule "schedule" with "domain".
445 __isl_give isl_schedule *isl_schedule_intersect_domain(
446 __isl_take isl_schedule *schedule, __isl_take isl_union_set *domain)
448 enum isl_schedule_node_type root_type;
449 isl_schedule_node *node;
451 if (!schedule || !domain)
452 goto error;
454 root_type = isl_schedule_tree_get_type(schedule->root);
455 if (root_type != isl_schedule_node_domain)
456 isl_die(isl_schedule_get_ctx(schedule), isl_error_internal,
457 "root node not a domain node", goto error);
459 node = isl_schedule_get_root(schedule);
460 isl_schedule_free(schedule);
461 node = isl_schedule_node_domain_intersect_domain(node, domain);
462 schedule = isl_schedule_node_get_schedule(node);
463 isl_schedule_node_free(node);
465 return schedule;
466 error:
467 isl_schedule_free(schedule);
468 isl_union_set_free(domain);
469 return NULL;
472 /* Return an isl_union_map representation of the schedule.
473 * If we still have access to the schedule tree, then we return
474 * an isl_union_map corresponding to the subtree schedule of the child
475 * of the root domain node. That is, we do not intersect the domain
476 * of the returned isl_union_map with the domain constraints.
477 * Otherwise, we must have removed it because we created a band forest.
478 * If so, we extract the isl_union_map from the forest.
479 * This reconstructed schedule map
480 * then needs to be padded with zeros to unify the schedule space
481 * since the result of isl_band_list_get_suffix_schedule may not have
482 * a unified schedule space.
484 __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
486 enum isl_schedule_node_type type;
487 isl_schedule_node *node;
488 isl_union_map *umap;
490 if (!sched)
491 return NULL;
493 if (sched->root) {
494 type = isl_schedule_tree_get_type(sched->root);
495 if (type != isl_schedule_node_domain)
496 isl_die(isl_schedule_get_ctx(sched), isl_error_internal,
497 "root node not a domain node", return NULL);
499 node = isl_schedule_get_root(sched);
500 node = isl_schedule_node_child(node, 0);
501 umap = isl_schedule_node_get_subtree_schedule_union_map(node);
502 isl_schedule_node_free(node);
504 return umap;
507 umap = isl_band_list_get_suffix_schedule(sched->band_forest);
508 return pad_schedule_map(umap);
511 static __isl_give isl_band_list *construct_band_list(
512 __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
513 __isl_keep isl_band *parent);
515 /* Construct an isl_band structure from the given schedule tree node,
516 * which may be either a band node or a leaf node.
517 * In the latter case, construct a zero-dimensional band.
518 * "domain" is the universe set of the domain elements that reach "node".
519 * "parent" is the parent isl_band of the isl_band constructed
520 * by this function.
522 * In case of a band node, we copy the properties (except tilability,
523 * which is implicit in an isl_band) to the isl_band.
524 * We assume that the band node is not zero-dimensional.
525 * If the child of the band node is not a leaf node,
526 * then we extract the children of the isl_band from this child.
528 static __isl_give isl_band *construct_band(__isl_take isl_schedule_node *node,
529 __isl_take isl_union_set *domain, __isl_keep isl_band *parent)
531 int i;
532 isl_ctx *ctx;
533 isl_band *band = NULL;
534 isl_multi_union_pw_aff *mupa;
536 if (!node || !domain)
537 goto error;
539 ctx = isl_schedule_node_get_ctx(node);
540 band = isl_band_alloc(ctx);
541 if (!band)
542 goto error;
544 band->schedule = node->schedule;
545 band->parent = parent;
547 if (isl_schedule_node_get_type(node) == isl_schedule_node_leaf) {
548 band->n = 0;
549 band->pma = isl_union_pw_multi_aff_from_domain(domain);
550 isl_schedule_node_free(node);
551 return band;
554 band->n = isl_schedule_node_band_n_member(node);
555 if (band->n == 0)
556 isl_die(ctx, isl_error_unsupported,
557 "zero-dimensional band nodes not supported",
558 goto error);
559 band->coincident = isl_alloc_array(ctx, int, band->n);
560 if (band->n && !band->coincident)
561 goto error;
562 for (i = 0; i < band->n; ++i)
563 band->coincident[i] =
564 isl_schedule_node_band_member_get_coincident(node, i);
565 mupa = isl_schedule_node_band_get_partial_schedule(node);
566 band->pma = isl_union_pw_multi_aff_from_multi_union_pw_aff(mupa);
567 if (!band->pma)
568 goto error;
570 node = isl_schedule_node_child(node, 0);
571 if (isl_schedule_node_get_type(node) == isl_schedule_node_leaf) {
572 isl_schedule_node_free(node);
573 isl_union_set_free(domain);
574 return band;
577 band->children = construct_band_list(node, domain, band);
578 if (!band->children)
579 return isl_band_free(band);
581 return band;
582 error:
583 isl_union_set_free(domain);
584 isl_schedule_node_free(node);
585 isl_band_free(band);
586 return NULL;
589 /* Construct a list of isl_band structures from the children of "node".
590 * "node" itself is a sequence or set node, so that each of the child nodes
591 * is a filter node and the list returned by node_construct_band_list
592 * consists of a single element.
593 * "domain" is the universe set of the domain elements that reach "node".
594 * "parent" is the parent isl_band of the isl_band structures constructed
595 * by this function.
597 static __isl_give isl_band_list *construct_band_list_from_children(
598 __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
599 __isl_keep isl_band *parent)
601 int i, n;
602 isl_ctx *ctx;
603 isl_band_list *list;
605 n = isl_schedule_node_n_children(node);
607 ctx = isl_schedule_node_get_ctx(node);
608 list = isl_band_list_alloc(ctx, 0);
609 for (i = 0; i < n; ++i) {
610 isl_schedule_node *child;
611 isl_band_list *list_i;
613 child = isl_schedule_node_get_child(node, i);
614 list_i = construct_band_list(child, isl_union_set_copy(domain),
615 parent);
616 list = isl_band_list_concat(list, list_i);
619 isl_union_set_free(domain);
620 isl_schedule_node_free(node);
622 return list;
625 /* Construct an isl_band structure from the given sequence node
626 * (or set node that is treated as a sequence node).
627 * A single-dimensional band is created with as schedule for each of
628 * filters of the children, the corresponding child position.
629 * "domain" is the universe set of the domain elements that reach "node".
630 * "parent" is the parent isl_band of the isl_band constructed
631 * by this function.
633 static __isl_give isl_band_list *construct_band_list_sequence(
634 __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
635 __isl_keep isl_band *parent)
637 int i, n;
638 isl_ctx *ctx;
639 isl_band *band = NULL;
640 isl_space *space;
641 isl_union_pw_multi_aff *upma;
643 if (!node || !domain)
644 goto error;
646 ctx = isl_schedule_node_get_ctx(node);
647 band = isl_band_alloc(ctx);
648 if (!band)
649 goto error;
651 band->schedule = node->schedule;
652 band->parent = parent;
653 band->n = 1;
654 band->coincident = isl_calloc_array(ctx, int, band->n);
655 if (!band->coincident)
656 goto error;
658 n = isl_schedule_node_n_children(node);
659 space = isl_union_set_get_space(domain);
660 upma = isl_union_pw_multi_aff_empty(isl_space_copy(space));
662 space = isl_space_set_from_params(space);
663 space = isl_space_add_dims(space, isl_dim_set, 1);
665 for (i = 0; i < n; ++i) {
666 isl_schedule_node *child;
667 isl_union_set *filter;
668 isl_val *v;
669 isl_val_list *vl;
670 isl_multi_val *mv;
671 isl_union_pw_multi_aff *upma_i;
673 child = isl_schedule_node_get_child(node, i);
674 filter = isl_schedule_node_filter_get_filter(child);
675 isl_schedule_node_free(child);
676 filter = isl_union_set_intersect(filter,
677 isl_union_set_copy(domain));
678 v = isl_val_int_from_si(ctx, i);
679 vl = isl_val_list_from_val(v);
680 mv = isl_multi_val_from_val_list(isl_space_copy(space), vl);
681 upma_i = isl_union_pw_multi_aff_multi_val_on_domain(filter, mv);
682 upma = isl_union_pw_multi_aff_union_add(upma, upma_i);
685 isl_space_free(space);
687 band->pma = upma;
688 if (!band->pma)
689 goto error;
691 band->children = construct_band_list_from_children(node, domain, band);
692 if (!band->children)
693 band = isl_band_free(band);
694 return isl_band_list_from_band(band);
695 error:
696 isl_union_set_free(domain);
697 isl_schedule_node_free(node);
698 isl_band_free(band);
699 return NULL;
702 /* Construct a list of isl_band structures from "node" depending
703 * on the type of "node".
704 * "domain" is the universe set of the domain elements that reach "node".
705 * "parent" is the parent isl_band of the isl_band structures constructed
706 * by this function.
708 * If schedule_separate_components is set then set nodes are treated
709 * as sequence nodes. Otherwise, we directly extract an (implicitly
710 * parallel) list of isl_band structures.
712 * If "node" is a filter, then "domain" is updated by the filter.
714 static __isl_give isl_band_list *construct_band_list(
715 __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
716 __isl_keep isl_band *parent)
718 enum isl_schedule_node_type type;
719 isl_ctx *ctx;
720 isl_band *band;
721 isl_band_list *list;
722 isl_union_set *filter;
724 if (!node || !domain)
725 goto error;
727 type = isl_schedule_node_get_type(node);
728 switch (type) {
729 case isl_schedule_node_error:
730 goto error;
731 case isl_schedule_node_context:
732 isl_die(isl_schedule_node_get_ctx(node), isl_error_unsupported,
733 "context nodes not supported", goto error);
734 case isl_schedule_node_domain:
735 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
736 "internal domain nodes not allowed", goto error);
737 case isl_schedule_node_filter:
738 filter = isl_schedule_node_filter_get_filter(node);
739 domain = isl_union_set_intersect(domain, filter);
740 node = isl_schedule_node_child(node, 0);
741 return construct_band_list(node, domain, parent);
742 case isl_schedule_node_set:
743 ctx = isl_schedule_node_get_ctx(node);
744 if (isl_options_get_schedule_separate_components(ctx))
745 return construct_band_list_sequence(node, domain,
746 parent);
747 else
748 return construct_band_list_from_children(node, domain,
749 parent);
750 case isl_schedule_node_sequence:
751 return construct_band_list_sequence(node, domain, parent);
752 case isl_schedule_node_leaf:
753 case isl_schedule_node_band:
754 band = construct_band(node, domain, parent);
755 list = isl_band_list_from_band(band);
756 break;
759 return list;
760 error:
761 isl_union_set_free(domain);
762 isl_schedule_node_free(node);
763 return NULL;
766 /* Return the roots of a band forest representation of the schedule.
767 * The band forest is constructed from the schedule tree,
768 * but once such a band forest is
769 * constructed, we forget about the original schedule tree since
770 * the user may modify the schedule through the band forest.
772 __isl_give isl_band_list *isl_schedule_get_band_forest(
773 __isl_keep isl_schedule *schedule)
775 isl_schedule_node *node;
776 isl_union_set *domain;
778 if (!schedule)
779 return NULL;
780 if (schedule->root) {
781 node = isl_schedule_get_root(schedule);
782 domain = isl_schedule_node_domain_get_domain(node);
783 domain = isl_union_set_universe(domain);
784 node = isl_schedule_node_child(node, 0);
786 schedule->band_forest = construct_band_list(node, domain, NULL);
787 schedule->root = isl_schedule_tree_free(schedule->root);
789 return isl_band_list_dup(schedule->band_forest);
792 /* Call "fn" on each band in the schedule in depth-first post-order.
794 int isl_schedule_foreach_band(__isl_keep isl_schedule *sched,
795 int (*fn)(__isl_keep isl_band *band, void *user), void *user)
797 int r;
798 isl_band_list *forest;
800 if (!sched)
801 return -1;
803 forest = isl_schedule_get_band_forest(sched);
804 r = isl_band_list_foreach_band(forest, fn, user);
805 isl_band_list_free(forest);
807 return r;
810 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
811 __isl_keep isl_band_list *list);
813 static __isl_give isl_printer *print_band(__isl_take isl_printer *p,
814 __isl_keep isl_band *band)
816 isl_band_list *children;
818 p = isl_printer_start_line(p);
819 p = isl_printer_print_union_pw_multi_aff(p, band->pma);
820 p = isl_printer_end_line(p);
822 if (!isl_band_has_children(band))
823 return p;
825 children = isl_band_get_children(band);
827 p = isl_printer_indent(p, 4);
828 p = print_band_list(p, children);
829 p = isl_printer_indent(p, -4);
831 isl_band_list_free(children);
833 return p;
836 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
837 __isl_keep isl_band_list *list)
839 int i, n;
841 n = isl_band_list_n_band(list);
842 for (i = 0; i < n; ++i) {
843 isl_band *band;
844 band = isl_band_list_get_band(list, i);
845 p = print_band(p, band);
846 isl_band_free(band);
849 return p;
852 /* Insert a band node with partial schedule "partial" between the domain
853 * root node of "schedule" and its single child.
854 * Return a pointer to the updated schedule.
856 * If any of the nodes in the tree depend on the set of outer band nodes
857 * then we refuse to insert the band node.
859 __isl_give isl_schedule *isl_schedule_insert_partial_schedule(
860 __isl_take isl_schedule *schedule,
861 __isl_take isl_multi_union_pw_aff *partial)
863 isl_schedule_node *node;
864 int anchored;
866 node = isl_schedule_get_root(schedule);
867 isl_schedule_free(schedule);
868 if (!node)
869 goto error;
870 if (isl_schedule_node_get_type(node) != isl_schedule_node_domain)
871 isl_die(isl_schedule_node_get_ctx(node), isl_error_internal,
872 "root node not a domain node", goto error);
874 node = isl_schedule_node_child(node, 0);
875 anchored = isl_schedule_node_is_subtree_anchored(node);
876 if (anchored < 0)
877 goto error;
878 if (anchored)
879 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
880 "cannot insert band node in anchored subtree",
881 goto error);
882 node = isl_schedule_node_insert_partial_schedule(node, partial);
884 schedule = isl_schedule_node_get_schedule(node);
885 isl_schedule_node_free(node);
887 return schedule;
888 error:
889 isl_schedule_node_free(node);
890 isl_multi_union_pw_aff_free(partial);
891 return NULL;
894 /* Return a tree with as top-level node a filter corresponding to "filter" and
895 * as child, the (single) child of "tree".
896 * However, if this single child is of type "type", then the filter is inserted
897 * in the children of this single child instead.
899 static __isl_give isl_schedule_tree *insert_filter_in_child_of_type(
900 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter,
901 enum isl_schedule_node_type type)
903 if (!isl_schedule_tree_has_children(tree)) {
904 isl_schedule_tree_free(tree);
905 return isl_schedule_tree_from_filter(filter);
906 } else {
907 tree = isl_schedule_tree_child(tree, 0);
910 if (isl_schedule_tree_get_type(tree) == type)
911 tree = isl_schedule_tree_children_insert_filter(tree, filter);
912 else
913 tree = isl_schedule_tree_insert_filter(tree, filter);
915 return tree;
918 /* Construct a schedule that combines the schedules "schedule1" and "schedule2"
919 * with a top-level node (underneath the domain node) of type "type",
920 * either isl_schedule_node_sequence or isl_schedule_node_set.
921 * The domains of the two schedules are assumed to be disjoint.
923 * The new schedule has as domain the union of the domains of the two
924 * schedules. The child of the domain node is a node of type "type"
925 * with two filters corresponding to the domains of the input schedules.
926 * If one (or both) of the top-level nodes of the two schedules is itself
927 * of type "type", then the filter is pushed into the children of that
928 * node and the sequence of set is flattened.
930 __isl_give isl_schedule *isl_schedule_pair(enum isl_schedule_node_type type,
931 __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)
933 int disjoint;
934 isl_ctx *ctx;
935 enum isl_schedule_node_type root_type;
936 isl_schedule_tree *tree1, *tree2;
937 isl_union_set *filter1, *filter2, *domain;
939 if (!schedule1 || !schedule2)
940 goto error;
942 root_type = isl_schedule_tree_get_type(schedule1->root);
943 if (root_type != isl_schedule_node_domain)
944 isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal,
945 "root node not a domain node", goto error);
946 root_type = isl_schedule_tree_get_type(schedule2->root);
947 if (root_type != isl_schedule_node_domain)
948 isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal,
949 "root node not a domain node", goto error);
951 ctx = isl_schedule_get_ctx(schedule1);
952 tree1 = isl_schedule_tree_copy(schedule1->root);
953 filter1 = isl_schedule_tree_domain_get_domain(tree1);
954 tree2 = isl_schedule_tree_copy(schedule2->root);
955 filter2 = isl_schedule_tree_domain_get_domain(tree2);
957 isl_schedule_free(schedule1);
958 isl_schedule_free(schedule2);
960 disjoint = isl_union_set_is_disjoint(filter1, filter2);
961 if (disjoint < 0)
962 filter1 = isl_union_set_free(filter1);
963 if (!disjoint)
964 isl_die(ctx, isl_error_invalid,
965 "schedule domains not disjoint",
966 filter1 = isl_union_set_free(filter1));
968 domain = isl_union_set_union(isl_union_set_copy(filter1),
969 isl_union_set_copy(filter2));
970 filter1 = isl_union_set_gist(filter1, isl_union_set_copy(domain));
971 filter2 = isl_union_set_gist(filter2, isl_union_set_copy(domain));
973 tree1 = insert_filter_in_child_of_type(tree1, filter1, type);
974 tree2 = insert_filter_in_child_of_type(tree2, filter2, type);
976 tree1 = isl_schedule_tree_from_pair(type, tree1, tree2);
977 tree1 = isl_schedule_tree_insert_domain(tree1, domain);
979 return isl_schedule_from_schedule_tree(ctx, tree1);
980 error:
981 isl_schedule_free(schedule1);
982 isl_schedule_free(schedule2);
983 return NULL;
986 /* Construct a schedule that combines the schedules "schedule1" and "schedule2"
987 * through a sequence node.
988 * The domains of the input schedules are assumed to be disjoint.
990 __isl_give isl_schedule *isl_schedule_sequence(
991 __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)
993 return isl_schedule_pair(isl_schedule_node_sequence,
994 schedule1, schedule2);
997 /* Construct a schedule that combines the schedules "schedule1" and "schedule2"
998 * through a set node.
999 * The domains of the input schedules are assumed to be disjoint.
1001 __isl_give isl_schedule *isl_schedule_set(
1002 __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)
1004 return isl_schedule_pair(isl_schedule_node_set, schedule1, schedule2);
1007 /* Print "schedule" to "p".
1009 * If "schedule" was created from a schedule tree, then we print
1010 * the schedule tree representation. Otherwise, we print
1011 * the band forest representation.
1013 __isl_give isl_printer *isl_printer_print_schedule(__isl_take isl_printer *p,
1014 __isl_keep isl_schedule *schedule)
1016 isl_band_list *forest;
1018 if (!schedule)
1019 return isl_printer_free(p);
1021 if (schedule->root)
1022 return isl_printer_print_schedule_tree(p, schedule->root);
1024 forest = isl_schedule_get_band_forest(schedule);
1026 p = print_band_list(p, forest);
1028 isl_band_list_free(forest);
1030 return p;
1033 void isl_schedule_dump(__isl_keep isl_schedule *schedule)
1035 isl_printer *printer;
1037 if (!schedule)
1038 return;
1040 printer = isl_printer_to_file(isl_schedule_get_ctx(schedule), stderr);
1041 printer = isl_printer_set_yaml_style(printer, ISL_YAML_STYLE_BLOCK);
1042 printer = isl_printer_print_schedule(printer, schedule);
1044 isl_printer_free(printer);