isl_schedule.c

   1 /*
   2  * Copyright 2011      INRIA Saclay
   3  * Copyright 2012-2014 Ecole Normale Superieure
   4  *
   5  * Use of this software is governed by the MIT license
   6  *
   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
  11  */
  12
  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>
  24
  25 /* Return a schedule encapsulating the given schedule tree.
  26  *
  27  * We currently only allow schedule trees with a domain as root.
  28  *
  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.
  35  */
  36 __isl_give isl_schedule *isl_schedule_from_schedule_tree(isl_ctx *ctx,
  37         __isl_take isl_schedule_tree *tree)
  38 {
  39         isl_schedule *schedule;
  40
  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);
  47
  48         schedule = isl_calloc_type(ctx, isl_schedule);
  49         if (!schedule)
  50                 goto error;
  51
  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;
  58
  59         return schedule;
  60 error:
  61         isl_schedule_tree_free(tree);
  62         return NULL;
  63 }
  64
  65 /* Return a pointer to a schedule with as single node
  66  * a domain node with the given domain.
  67  */
  68 __isl_give isl_schedule *isl_schedule_from_domain(
  69         __isl_take isl_union_set *domain)
  70 {
  71         isl_ctx *ctx;
  72         isl_schedule_tree *tree;
  73
  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);
  77 }
  78
  79 /* Return a pointer to a schedule with as single node
  80  * a domain node with an empty domain.
  81  */
  82 __isl_give isl_schedule *isl_schedule_empty(__isl_take isl_space *space)
  83 {
  84         return isl_schedule_from_domain(isl_union_set_empty(space));
  85 }
  86
  87 /* Return a new reference to "sched".
  88  */
  89 __isl_give isl_schedule *isl_schedule_copy(__isl_keep isl_schedule *sched)
  90 {
  91         if (!sched)
  92                 return NULL;
  93
  94         sched->ref++;
  95         return sched;
  96 }
  97
  98 /* Return an isl_schedule that is equal to "schedule" and that has only
  99  * a single reference.
 100  *
 101  * We only need and support this function when the schedule is represented
 102  * as a schedule tree.
 103  */
 104 __isl_give isl_schedule *isl_schedule_cow(__isl_take isl_schedule *schedule)
 105 {
 106         isl_ctx *ctx;
 107         isl_schedule_tree *tree;
 108
 109         if (!schedule)
 110                 return NULL;
 111         if (schedule->ref == 1)
 112                 return schedule;
 113
 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);
 122 }
 123
 124 __isl_null isl_schedule *isl_schedule_free(__isl_take isl_schedule *sched)
 125 {
 126         if (!sched)
 127                 return NULL;
 128
 129         if (--sched->ref > 0)
 130                 return NULL;
 131
 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;
 137 }
 138
 139 /* Replace the root of "schedule" by "tree".
 140  */
 141 __isl_give isl_schedule *isl_schedule_set_root(
 142         __isl_take isl_schedule *schedule, __isl_take isl_schedule_tree *tree)
 143 {
 144         if (!schedule || !tree)
 145                 goto error;
 146         if (schedule->root == tree) {
 147                 isl_schedule_tree_free(tree);
 148                 return schedule;
 149         }
 150
 151         schedule = isl_schedule_cow(schedule);
 152         if (!schedule)
 153                 goto error;
 154         isl_schedule_tree_free(schedule->root);
 155         schedule->root = tree;
 156
 157         return schedule;
 158 error:
 159         isl_schedule_free(schedule);
 160         isl_schedule_tree_free(tree);
 161         return NULL;
 162 }
 163
 164 isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule)
 165 {
 166         return schedule ? schedule->leaf.ctx : NULL;
 167 }
 168
 169 /* Return a pointer to the leaf of "schedule".
 170  *
 171  * Even though these leaves are not reference counted, we still
 172  * indicate that this function does not return a copy.
 173  */
 174 __isl_keep isl_schedule_tree *isl_schedule_peek_leaf(
 175         __isl_keep isl_schedule *schedule)
 176 {
 177         return schedule ? &schedule->leaf : NULL;
 178 }
 179
 180 /* Return the (parameter) space of the schedule, i.e., the space
 181  * of the root domain.
 182  */
 183 __isl_give isl_space *isl_schedule_get_space(
 184         __isl_keep isl_schedule *schedule)
 185 {
 186         enum isl_schedule_node_type type;
 187         isl_space *space;
 188         isl_union_set *domain;
 189
 190         if (!schedule)
 191                 return NULL;
 192         if (!schedule->root)
 193                 isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
 194                         "schedule tree representation not available",
 195                         return NULL);
 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);
 200
 201         domain = isl_schedule_tree_domain_get_domain(schedule->root);
 202         space = isl_union_set_get_space(domain);
 203         isl_union_set_free(domain);
 204
 205         return space;
 206 }
 207
 208 /* Return a pointer to the root of "schedule".
 209  */
 210 __isl_give isl_schedule_node *isl_schedule_get_root(
 211         __isl_keep isl_schedule *schedule)
 212 {
 213         isl_ctx *ctx;
 214         isl_schedule_tree *tree;
 215         isl_schedule_tree_list *ancestors;
 216
 217         if (!schedule)
 218                 return NULL;
 219
 220         if (!schedule->root)
 221                 isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
 222                         "schedule tree representation not available",
 223                         return NULL);
 224
 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);
 230 }
 231
 232 /* Set max_out to the maximal number of output dimensions over
 233  * all maps.
 234  */
 235 static int update_max_out(__isl_take isl_map *map, void *user)
 236 {
 237         int *max_out = user;
 238         int n_out = isl_map_dim(map, isl_dim_out);
 239
 240         if (n_out > *max_out)
 241                 *max_out = n_out;
 242
 243         isl_map_free(map);
 244         return 0;
 245 }
 246
 247 /* Internal data structure for map_pad_range.
 248  *
 249  * "max_out" is the maximal schedule dimension.
 250  * "res" collects the results.
 251  */
 252 struct isl_pad_schedule_map_data {
 253         int max_out;
 254         isl_union_map *res;
 255 };
 256
 257 /* Pad the range of the given map with zeros to data->max_out and
 258  * then add the result to data->res.
 259  */
 260 static int map_pad_range(__isl_take isl_map *map, void *user)
 261 {
 262         struct isl_pad_schedule_map_data *data = user;
 263         int i;
 264         int n_out = isl_map_dim(map, isl_dim_out);
 265
 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);
 269
 270         data->res = isl_union_map_add_map(data->res, map);
 271         if (!data->res)
 272                 return -1;
 273
 274         return 0;
 275 }
 276
 277 /* Pad the ranges of the maps in the union map with zeros such they all have
 278  * the same dimension.
 279  */
 280 static __isl_give isl_union_map *pad_schedule_map(
 281         __isl_take isl_union_map *umap)
 282 {
 283         struct isl_pad_schedule_map_data data;
 284
 285         if (!umap)
 286                 return NULL;
 287         if (isl_union_map_n_map(umap) <= 1)
 288                 return umap;
 289
 290         data.max_out = 0;
 291         if (isl_union_map_foreach_map(umap, &update_max_out, &data.max_out) < 0)
 292                 return isl_union_map_free(umap);
 293
 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);
 297
 298         isl_union_map_free(umap);
 299         return data.res;
 300 }
 301
 302 /* Return the domain of the root domain node of "schedule".
 303  */
 304 __isl_give isl_union_set *isl_schedule_get_domain(
 305         __isl_keep isl_schedule *schedule)
 306 {
 307         if (!schedule)
 308                 return NULL;
 309         if (!schedule->root)
 310                 isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
 311                         "schedule tree representation not available",
 312                         return NULL);
 313         return isl_schedule_tree_domain_get_domain(schedule->root);
 314 }
 315
 316 /* Traverse all nodes of "sched" in depth first preorder.
 317  *
 318  * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
 319  * If "fn" returns 0 on any of the nodes, then the subtree rooted
 320  * at that node is skipped.
 321  *
 322  * Return 0 on success and -1 on failure.
 323  */
 324 int isl_schedule_foreach_schedule_node(__isl_keep isl_schedule *sched,
 325         int (*fn)(__isl_keep isl_schedule_node *node, void *user), void *user)
 326 {
 327         isl_schedule_node *node;
 328         int r;
 329
 330         if (!sched)
 331                 return -1;
 332
 333         node = isl_schedule_get_root(sched);
 334         r = isl_schedule_node_foreach_descendant(node, fn, user);
 335         isl_schedule_node_free(node);
 336
 337         return r;
 338 }
 339
 340 /* Traverse the node of "sched" in depth first postorder,
 341  * allowing the user to modify the visited node.
 342  * The traversal continues from the node returned by the callback function.
 343  * It is the responsibility of the user to ensure that this does not
 344  * lead to an infinite loop.  It is safest to always return a pointer
 345  * to the same position (same ancestors and child positions) as the input node.
 346  */
 347 __isl_give isl_schedule *isl_schedule_map_schedule_node(
 348         __isl_take isl_schedule *schedule,
 349         __isl_give isl_schedule_node *(*fn)(
 350                 __isl_take isl_schedule_node *node, void *user), void *user)
 351 {
 352         isl_schedule_node *node;
 353
 354         node = isl_schedule_get_root(schedule);
 355         isl_schedule_free(schedule);
 356
 357         node = isl_schedule_node_map_descendant(node, fn, user);
 358         schedule = isl_schedule_node_get_schedule(node);
 359         isl_schedule_node_free(node);
 360
 361         return schedule;
 362 }
 363
 364 /* Return an isl_union_map representation of the schedule.
 365  * If we still have access to the schedule tree, then we return
 366  * an isl_union_map corresponding to the subtree schedule of the child
 367  * of the root domain node.  That is, we do not intersect the domain
 368  * of the returned isl_union_map with the domain constraints.
 369  * Otherwise, we must have removed it because we created a band forest.
 370  * If so, we extract the isl_union_map from the forest.
 371  * This reconstructed schedule map
 372  * then needs to be padded with zeros to unify the schedule space
 373  * since the result of isl_band_list_get_suffix_schedule may not have
 374  * a unified schedule space.
 375  */
 376 __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
 377 {
 378         enum isl_schedule_node_type type;
 379         isl_schedule_node *node;
 380         isl_union_map *umap;
 381
 382         if (!sched)
 383                 return NULL;
 384
 385         if (sched->root) {
 386                 type = isl_schedule_tree_get_type(sched->root);
 387                 if (type != isl_schedule_node_domain)
 388                         isl_die(isl_schedule_get_ctx(sched), isl_error_internal,
 389                                 "root node not a domain node", return NULL);
 390
 391                 node = isl_schedule_get_root(sched);
 392                 node = isl_schedule_node_child(node, 0);
 393                 umap = isl_schedule_node_get_subtree_schedule_union_map(node);
 394                 isl_schedule_node_free(node);
 395
 396                 return umap;
 397         }
 398
 399         umap = isl_band_list_get_suffix_schedule(sched->band_forest);
 400         return pad_schedule_map(umap);
 401 }
 402
 403 static __isl_give isl_band_list *construct_band_list(
 404         __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
 405         __isl_keep isl_band *parent);
 406
 407 /* Construct an isl_band structure from the given schedule tree node,
 408  * which may be either a band node or a leaf node.
 409  * In the latter case, construct a zero-dimensional band.
 410  * "domain" is the universe set of the domain elements that reach "node".
 411  * "parent" is the parent isl_band of the isl_band constructed
 412  * by this function.
 413  *
 414  * In case of a band node, we copy the properties (except tilability,
 415  * which is implicit in an isl_band) to the isl_band.
 416  * We assume that the band node is not zero-dimensional.
 417  * If the child of the band node is not a leaf node,
 418  * then we extract the children of the isl_band from this child.
 419  */
 420 static __isl_give isl_band *construct_band(__isl_take isl_schedule_node *node,
 421         __isl_take isl_union_set *domain, __isl_keep isl_band *parent)
 422 {
 423         int i;
 424         isl_ctx *ctx;
 425         isl_band *band = NULL;
 426         isl_multi_union_pw_aff *mupa;
 427
 428         if (!node || !domain)
 429                 goto error;
 430
 431         ctx = isl_schedule_node_get_ctx(node);
 432         band = isl_band_alloc(ctx);
 433         if (!band)
 434                 goto error;
 435
 436         band->schedule = node->schedule;
 437         band->parent = parent;
 438
 439         if (isl_schedule_node_get_type(node) == isl_schedule_node_leaf) {
 440                 band->n = 0;
 441                 band->pma = isl_union_pw_multi_aff_from_domain(domain);
 442                 isl_schedule_node_free(node);
 443                 return band;
 444         }
 445
 446         band->n = isl_schedule_node_band_n_member(node);
 447         if (band->n == 0)
 448                 isl_die(ctx, isl_error_unsupported,
 449                         "zero-dimensional band nodes not supported",
 450                         goto error);
 451         band->coincident = isl_alloc_array(ctx, int, band->n);
 452         if (band->n && !band->coincident)
 453                 goto error;
 454         for (i = 0; i < band->n; ++i)
 455                 band->coincident[i] =
 456                         isl_schedule_node_band_member_get_coincident(node, i);
 457         mupa = isl_schedule_node_band_get_partial_schedule(node);
 458         band->pma = isl_union_pw_multi_aff_from_multi_union_pw_aff(mupa);
 459         if (!band->pma)
 460                 goto error;
 461
 462         node = isl_schedule_node_child(node, 0);
 463         if (isl_schedule_node_get_type(node) == isl_schedule_node_leaf) {
 464                 isl_schedule_node_free(node);
 465                 isl_union_set_free(domain);
 466                 return band;
 467         }
 468
 469         band->children = construct_band_list(node, domain, band);
 470         if (!band->children)
 471                 return isl_band_free(band);
 472
 473         return band;
 474 error:
 475         isl_union_set_free(domain);
 476         isl_schedule_node_free(node);
 477         isl_band_free(band);
 478         return NULL;
 479 }
 480
 481 /* Construct a list of isl_band structures from the children of "node".
 482  * "node" itself is a sequence or set node, so that each of the child nodes
 483  * is a filter node and the list returned by node_construct_band_list
 484  * consists of a single element.
 485  * "domain" is the universe set of the domain elements that reach "node".
 486  * "parent" is the parent isl_band of the isl_band structures constructed
 487  * by this function.
 488  */
 489 static __isl_give isl_band_list *construct_band_list_from_children(
 490         __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
 491         __isl_keep isl_band *parent)
 492 {
 493         int i, n;
 494         isl_ctx *ctx;
 495         isl_band_list *list;
 496
 497         n = isl_schedule_node_n_children(node);
 498
 499         ctx = isl_schedule_node_get_ctx(node);
 500         list = isl_band_list_alloc(ctx, 0);
 501         for (i = 0; i < n; ++i) {
 502                 isl_schedule_node *child;
 503                 isl_band_list *list_i;
 504
 505                 child = isl_schedule_node_get_child(node, i);
 506                 list_i = construct_band_list(child, isl_union_set_copy(domain),
 507                                                 parent);
 508                 list = isl_band_list_concat(list, list_i);
 509         }
 510
 511         isl_union_set_free(domain);
 512         isl_schedule_node_free(node);
 513
 514         return list;
 515 }
 516
 517 /* Construct an isl_band structure from the given sequence node
 518  * (or set node that is treated as a sequence node).
 519  * A single-dimensional band is created with as schedule for each of
 520  * filters of the children, the corresponding child position.
 521  * "domain" is the universe set of the domain elements that reach "node".
 522  * "parent" is the parent isl_band of the isl_band constructed
 523  * by this function.
 524  */
 525 static __isl_give isl_band_list *construct_band_list_sequence(
 526         __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
 527         __isl_keep isl_band *parent)
 528 {
 529         int i, n;
 530         isl_ctx *ctx;
 531         isl_band *band = NULL;
 532         isl_space *space;
 533         isl_union_pw_multi_aff *upma;
 534
 535         if (!node || !domain)
 536                 goto error;
 537
 538         ctx = isl_schedule_node_get_ctx(node);
 539         band = isl_band_alloc(ctx);
 540         if (!band)
 541                 goto error;
 542
 543         band->schedule = node->schedule;
 544         band->parent = parent;
 545         band->n = 1;
 546         band->coincident = isl_calloc_array(ctx, int, band->n);
 547         if (!band->coincident)
 548                 goto error;
 549
 550         n = isl_schedule_node_n_children(node);
 551         space = isl_union_set_get_space(domain);
 552         upma = isl_union_pw_multi_aff_empty(isl_space_copy(space));
 553
 554         space = isl_space_set_from_params(space);
 555         space = isl_space_add_dims(space, isl_dim_set, 1);
 556
 557         for (i = 0; i < n; ++i) {
 558                 isl_schedule_node *child;
 559                 isl_union_set *filter;
 560                 isl_val *v;
 561                 isl_val_list *vl;
 562                 isl_multi_val *mv;
 563                 isl_union_pw_multi_aff *upma_i;
 564
 565                 child = isl_schedule_node_get_child(node, i);
 566                 filter = isl_schedule_node_filter_get_filter(child);
 567                 isl_schedule_node_free(child);
 568                 filter = isl_union_set_intersect(filter,
 569                                                 isl_union_set_copy(domain));
 570                 v = isl_val_int_from_si(ctx, i);
 571                 vl = isl_val_list_from_val(v);
 572                 mv = isl_multi_val_from_val_list(isl_space_copy(space), vl);
 573                 upma_i = isl_union_pw_multi_aff_multi_val_on_domain(filter, mv);
 574                 upma = isl_union_pw_multi_aff_union_add(upma, upma_i);
 575         }
 576
 577         isl_space_free(space);
 578
 579         band->pma = upma;
 580         if (!band->pma)
 581                 goto error;
 582
 583         band->children = construct_band_list_from_children(node, domain, band);
 584         if (!band->children)
 585                 band = isl_band_free(band);
 586         return isl_band_list_from_band(band);
 587 error:
 588         isl_union_set_free(domain);
 589         isl_schedule_node_free(node);
 590         isl_band_free(band);
 591         return NULL;
 592 }
 593
 594 /* Construct a list of isl_band structures from "node" depending
 595  * on the type of "node".
 596  * "domain" is the universe set of the domain elements that reach "node".
 597  * "parent" is the parent isl_band of the isl_band structures constructed
 598  * by this function.
 599  *
 600  * If schedule_separate_components is set then set nodes are treated
 601  * as sequence nodes.  Otherwise, we directly extract an (implicitly
 602  * parallel) list of isl_band structures.
 603  *
 604  * If "node" is a filter, then "domain" is updated by the filter.
 605  */
 606 static __isl_give isl_band_list *construct_band_list(
 607         __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
 608         __isl_keep isl_band *parent)
 609 {
 610         enum isl_schedule_node_type type;
 611         isl_ctx *ctx;
 612         isl_band *band;
 613         isl_band_list *list;
 614         isl_union_set *filter;
 615
 616         if (!node || !domain)
 617                 goto error;
 618
 619         type = isl_schedule_node_get_type(node);
 620         switch (type) {
 621         case isl_schedule_node_error:
 622                 goto error;
 623         case isl_schedule_node_domain:
 624                 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
 625                         "internal domain nodes not allowed", goto error);
 626         case isl_schedule_node_filter:
 627                 filter = isl_schedule_node_filter_get_filter(node);
 628                 domain = isl_union_set_intersect(domain, filter);
 629                 node = isl_schedule_node_child(node, 0);
 630                 return construct_band_list(node, domain, parent);
 631         case isl_schedule_node_set:
 632                 ctx = isl_schedule_node_get_ctx(node);
 633                 if (isl_options_get_schedule_separate_components(ctx))
 634                         return construct_band_list_sequence(node, domain,
 635                                                             parent);
 636                 else
 637                         return construct_band_list_from_children(node, domain,
 638                                                             parent);
 639         case isl_schedule_node_sequence:
 640                 return construct_band_list_sequence(node, domain, parent);
 641         case isl_schedule_node_leaf:
 642         case isl_schedule_node_band:
 643                 band = construct_band(node, domain, parent);
 644                 list = isl_band_list_from_band(band);
 645                 break;
 646         }
 647
 648         return list;
 649 error:
 650         isl_union_set_free(domain);
 651         isl_schedule_node_free(node);
 652         return NULL;
 653 }
 654
 655 /* Return the roots of a band forest representation of the schedule.
 656  * The band forest is constructed from the schedule tree,
 657  * but once such a band forest is
 658  * constructed, we forget about the original schedule tree since
 659  * the user may modify the schedule through the band forest.
 660  */
 661 __isl_give isl_band_list *isl_schedule_get_band_forest(
 662         __isl_keep isl_schedule *schedule)
 663 {
 664         isl_schedule_node *node;
 665         isl_union_set *domain;
 666
 667         if (!schedule)
 668                 return NULL;
 669         if (schedule->root) {
 670                 node = isl_schedule_get_root(schedule);
 671                 domain = isl_schedule_node_domain_get_domain(node);
 672                 domain = isl_union_set_universe(domain);
 673                 node = isl_schedule_node_child(node, 0);
 674
 675                 schedule->band_forest = construct_band_list(node, domain, NULL);
 676                 schedule->root = isl_schedule_tree_free(schedule->root);
 677         }
 678         return isl_band_list_dup(schedule->band_forest);
 679 }
 680
 681 /* Call "fn" on each band in the schedule in depth-first post-order.
 682  */
 683 int isl_schedule_foreach_band(__isl_keep isl_schedule *sched,
 684         int (*fn)(__isl_keep isl_band *band, void *user), void *user)
 685 {
 686         int r;
 687         isl_band_list *forest;
 688
 689         if (!sched)
 690                 return -1;
 691
 692         forest = isl_schedule_get_band_forest(sched);
 693         r = isl_band_list_foreach_band(forest, fn, user);
 694         isl_band_list_free(forest);
 695
 696         return r;
 697 }
 698
 699 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
 700         __isl_keep isl_band_list *list);
 701
 702 static __isl_give isl_printer *print_band(__isl_take isl_printer *p,
 703         __isl_keep isl_band *band)
 704 {
 705         isl_band_list *children;
 706
 707         p = isl_printer_start_line(p);
 708         p = isl_printer_print_union_pw_multi_aff(p, band->pma);
 709         p = isl_printer_end_line(p);
 710
 711         if (!isl_band_has_children(band))
 712                 return p;
 713
 714         children = isl_band_get_children(band);
 715
 716         p = isl_printer_indent(p, 4);
 717         p = print_band_list(p, children);
 718         p = isl_printer_indent(p, -4);
 719
 720         isl_band_list_free(children);
 721
 722         return p;
 723 }
 724
 725 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
 726         __isl_keep isl_band_list *list)
 727 {
 728         int i, n;
 729
 730         n = isl_band_list_n_band(list);
 731         for (i = 0; i < n; ++i) {
 732                 isl_band *band;
 733                 band = isl_band_list_get_band(list, i);
 734                 p = print_band(p, band);
 735                 isl_band_free(band);
 736         }
 737
 738         return p;
 739 }
 740
 741 /* Print "schedule" to "p".
 742  *
 743  * If "schedule" was created from a schedule tree, then we print
 744  * the schedule tree representation.  Otherwise, we print
 745  * the band forest representation.
 746  */
 747 __isl_give isl_printer *isl_printer_print_schedule(__isl_take isl_printer *p,
 748         __isl_keep isl_schedule *schedule)
 749 {
 750         isl_band_list *forest;
 751
 752         if (!schedule)
 753                 return isl_printer_free(p);
 754
 755         if (schedule->root)
 756                 return isl_printer_print_schedule_tree(p, schedule->root);
 757
 758         forest = isl_schedule_get_band_forest(schedule);
 759
 760         p = print_band_list(p, forest);
 761
 762         isl_band_list_free(forest);
 763
 764         return p;
 765 }
 766
 767 void isl_schedule_dump(__isl_keep isl_schedule *schedule)
 768 {
 769         isl_printer *printer;
 770
 771         if (!schedule)
 772                 return;
 773
 774         printer = isl_printer_to_file(isl_schedule_get_ctx(schedule), stderr);
 775         printer = isl_printer_set_yaml_style(printer, ISL_YAML_STYLE_BLOCK);
 776         printer = isl_printer_print_schedule(printer, schedule);
 777
 778         isl_printer_free(printer);
 779 }