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 /* Are "schedule1" and "schedule2" obviously equal to each other?
 181  */
 182 int isl_schedule_plain_is_equal(__isl_keep isl_schedule *schedule1,
 183         __isl_keep isl_schedule *schedule2)
 184 {
 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);
 191 }
 192
 193 /* Return the (parameter) space of the schedule, i.e., the space
 194  * of the root domain.
 195  */
 196 __isl_give isl_space *isl_schedule_get_space(
 197         __isl_keep isl_schedule *schedule)
 198 {
 199         enum isl_schedule_node_type type;
 200         isl_space *space;
 201         isl_union_set *domain;
 202
 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);
 213
 214         domain = isl_schedule_tree_domain_get_domain(schedule->root);
 215         space = isl_union_set_get_space(domain);
 216         isl_union_set_free(domain);
 217
 218         return space;
 219 }
 220
 221 /* Return a pointer to the root of "schedule".
 222  */
 223 __isl_give isl_schedule_node *isl_schedule_get_root(
 224         __isl_keep isl_schedule *schedule)
 225 {
 226         isl_ctx *ctx;
 227         isl_schedule_tree *tree;
 228         isl_schedule_tree_list *ancestors;
 229
 230         if (!schedule)
 231                 return NULL;
 232
 233         if (!schedule->root)
 234                 isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
 235                         "schedule tree representation not available",
 236                         return NULL);
 237
 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);
 243 }
 244
 245 /* Set max_out to the maximal number of output dimensions over
 246  * all maps.
 247  */
 248 static int update_max_out(__isl_take isl_map *map, void *user)
 249 {
 250         int *max_out = user;
 251         int n_out = isl_map_dim(map, isl_dim_out);
 252
 253         if (n_out > *max_out)
 254                 *max_out = n_out;
 255
 256         isl_map_free(map);
 257         return 0;
 258 }
 259
 260 /* Internal data structure for map_pad_range.
 261  *
 262  * "max_out" is the maximal schedule dimension.
 263  * "res" collects the results.
 264  */
 265 struct isl_pad_schedule_map_data {
 266         int max_out;
 267         isl_union_map *res;
 268 };
 269
 270 /* Pad the range of the given map with zeros to data->max_out and
 271  * then add the result to data->res.
 272  */
 273 static int map_pad_range(__isl_take isl_map *map, void *user)
 274 {
 275         struct isl_pad_schedule_map_data *data = user;
 276         int i;
 277         int n_out = isl_map_dim(map, isl_dim_out);
 278
 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);
 282
 283         data->res = isl_union_map_add_map(data->res, map);
 284         if (!data->res)
 285                 return -1;
 286
 287         return 0;
 288 }
 289
 290 /* Pad the ranges of the maps in the union map with zeros such they all have
 291  * the same dimension.
 292  */
 293 static __isl_give isl_union_map *pad_schedule_map(
 294         __isl_take isl_union_map *umap)
 295 {
 296         struct isl_pad_schedule_map_data data;
 297
 298         if (!umap)
 299                 return NULL;
 300         if (isl_union_map_n_map(umap) <= 1)
 301                 return umap;
 302
 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);
 306
 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);
 310
 311         isl_union_map_free(umap);
 312         return data.res;
 313 }
 314
 315 /* Return the domain of the root domain node of "schedule".
 316  */
 317 __isl_give isl_union_set *isl_schedule_get_domain(
 318         __isl_keep isl_schedule *schedule)
 319 {
 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);
 327 }
 328
 329 /* Traverse all nodes of "sched" in depth first preorder.
 330  *
 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.
 334  *
 335  * Return 0 on success and -1 on failure.
 336  */
 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)
 339 {
 340         isl_schedule_node *node;
 341         int r;
 342
 343         if (!sched)
 344                 return -1;
 345
 346         node = isl_schedule_get_root(sched);
 347         r = isl_schedule_node_foreach_descendant(node, fn, user);
 348         isl_schedule_node_free(node);
 349
 350         return r;
 351 }
 352
 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.
 359  */
 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)
 364 {
 365         isl_schedule_node *node;
 366
 367         node = isl_schedule_get_root(schedule);
 368         isl_schedule_free(schedule);
 369
 370         node = isl_schedule_node_map_descendant(node, fn, user);
 371         schedule = isl_schedule_node_get_schedule(node);
 372         isl_schedule_node_free(node);
 373
 374         return schedule;
 375 }
 376
 377 /* Wrapper around isl_schedule_node_reset_user for use as
 378  * an isl_schedule_map_schedule_node callback.
 379  */
 380 static __isl_give isl_schedule_node *reset_user(
 381         __isl_take isl_schedule_node *node, void *user)
 382 {
 383         return isl_schedule_node_reset_user(node);
 384 }
 385
 386 /* Reset the user pointer on all identifiers of parameters and tuples
 387  * in the schedule "schedule".
 388  */
 389 __isl_give isl_schedule *isl_schedule_reset_user(
 390         __isl_take isl_schedule *schedule)
 391 {
 392         return isl_schedule_map_schedule_node(schedule, &reset_user, NULL);
 393 }
 394
 395 /* Wrapper around isl_schedule_node_align_params for use as
 396  * an isl_schedule_map_schedule_node callback.
 397  */
 398 static __isl_give isl_schedule_node *align_params(
 399         __isl_take isl_schedule_node *node, void *user)
 400 {
 401         isl_space *space = user;
 402
 403         return isl_schedule_node_align_params(node, isl_space_copy(space));
 404 }
 405
 406 /* Align the parameters of all nodes in schedule "schedule"
 407  * to those of "space".
 408  */
 409 __isl_give isl_schedule *isl_schedule_align_params(
 410         __isl_take isl_schedule *schedule, __isl_take isl_space *space)
 411 {
 412         schedule = isl_schedule_map_schedule_node(schedule,
 413                                                     &align_params, space);
 414         isl_space_free(space);
 415         return schedule;
 416 }
 417
 418 /* Return an isl_union_map representation of the schedule.
 419  * If we still have access to the schedule tree, then we return
 420  * an isl_union_map corresponding to the subtree schedule of the child
 421  * of the root domain node.  That is, we do not intersect the domain
 422  * of the returned isl_union_map with the domain constraints.
 423  * Otherwise, we must have removed it because we created a band forest.
 424  * If so, we extract the isl_union_map from the forest.
 425  * This reconstructed schedule map
 426  * then needs to be padded with zeros to unify the schedule space
 427  * since the result of isl_band_list_get_suffix_schedule may not have
 428  * a unified schedule space.
 429  */
 430 __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
 431 {
 432         enum isl_schedule_node_type type;
 433         isl_schedule_node *node;
 434         isl_union_map *umap;
 435
 436         if (!sched)
 437                 return NULL;
 438
 439         if (sched->root) {
 440                 type = isl_schedule_tree_get_type(sched->root);
 441                 if (type != isl_schedule_node_domain)
 442                         isl_die(isl_schedule_get_ctx(sched), isl_error_internal,
 443                                 "root node not a domain node", return NULL);
 444
 445                 node = isl_schedule_get_root(sched);
 446                 node = isl_schedule_node_child(node, 0);
 447                 umap = isl_schedule_node_get_subtree_schedule_union_map(node);
 448                 isl_schedule_node_free(node);
 449
 450                 return umap;
 451         }
 452
 453         umap = isl_band_list_get_suffix_schedule(sched->band_forest);
 454         return pad_schedule_map(umap);
 455 }
 456
 457 static __isl_give isl_band_list *construct_band_list(
 458         __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
 459         __isl_keep isl_band *parent);
 460
 461 /* Construct an isl_band structure from the given schedule tree node,
 462  * which may be either a band node or a leaf node.
 463  * In the latter case, construct a zero-dimensional band.
 464  * "domain" is the universe set of the domain elements that reach "node".
 465  * "parent" is the parent isl_band of the isl_band constructed
 466  * by this function.
 467  *
 468  * In case of a band node, we copy the properties (except tilability,
 469  * which is implicit in an isl_band) to the isl_band.
 470  * We assume that the band node is not zero-dimensional.
 471  * If the child of the band node is not a leaf node,
 472  * then we extract the children of the isl_band from this child.
 473  */
 474 static __isl_give isl_band *construct_band(__isl_take isl_schedule_node *node,
 475         __isl_take isl_union_set *domain, __isl_keep isl_band *parent)
 476 {
 477         int i;
 478         isl_ctx *ctx;
 479         isl_band *band = NULL;
 480         isl_multi_union_pw_aff *mupa;
 481
 482         if (!node || !domain)
 483                 goto error;
 484
 485         ctx = isl_schedule_node_get_ctx(node);
 486         band = isl_band_alloc(ctx);
 487         if (!band)
 488                 goto error;
 489
 490         band->schedule = node->schedule;
 491         band->parent = parent;
 492
 493         if (isl_schedule_node_get_type(node) == isl_schedule_node_leaf) {
 494                 band->n = 0;
 495                 band->pma = isl_union_pw_multi_aff_from_domain(domain);
 496                 isl_schedule_node_free(node);
 497                 return band;
 498         }
 499
 500         band->n = isl_schedule_node_band_n_member(node);
 501         if (band->n == 0)
 502                 isl_die(ctx, isl_error_unsupported,
 503                         "zero-dimensional band nodes not supported",
 504                         goto error);
 505         band->coincident = isl_alloc_array(ctx, int, band->n);
 506         if (band->n && !band->coincident)
 507                 goto error;
 508         for (i = 0; i < band->n; ++i)
 509                 band->coincident[i] =
 510                         isl_schedule_node_band_member_get_coincident(node, i);
 511         mupa = isl_schedule_node_band_get_partial_schedule(node);
 512         band->pma = isl_union_pw_multi_aff_from_multi_union_pw_aff(mupa);
 513         if (!band->pma)
 514                 goto error;
 515
 516         node = isl_schedule_node_child(node, 0);
 517         if (isl_schedule_node_get_type(node) == isl_schedule_node_leaf) {
 518                 isl_schedule_node_free(node);
 519                 isl_union_set_free(domain);
 520                 return band;
 521         }
 522
 523         band->children = construct_band_list(node, domain, band);
 524         if (!band->children)
 525                 return isl_band_free(band);
 526
 527         return band;
 528 error:
 529         isl_union_set_free(domain);
 530         isl_schedule_node_free(node);
 531         isl_band_free(band);
 532         return NULL;
 533 }
 534
 535 /* Construct a list of isl_band structures from the children of "node".
 536  * "node" itself is a sequence or set node, so that each of the child nodes
 537  * is a filter node and the list returned by node_construct_band_list
 538  * consists of a single element.
 539  * "domain" is the universe set of the domain elements that reach "node".
 540  * "parent" is the parent isl_band of the isl_band structures constructed
 541  * by this function.
 542  */
 543 static __isl_give isl_band_list *construct_band_list_from_children(
 544         __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
 545         __isl_keep isl_band *parent)
 546 {
 547         int i, n;
 548         isl_ctx *ctx;
 549         isl_band_list *list;
 550
 551         n = isl_schedule_node_n_children(node);
 552
 553         ctx = isl_schedule_node_get_ctx(node);
 554         list = isl_band_list_alloc(ctx, 0);
 555         for (i = 0; i < n; ++i) {
 556                 isl_schedule_node *child;
 557                 isl_band_list *list_i;
 558
 559                 child = isl_schedule_node_get_child(node, i);
 560                 list_i = construct_band_list(child, isl_union_set_copy(domain),
 561                                                 parent);
 562                 list = isl_band_list_concat(list, list_i);
 563         }
 564
 565         isl_union_set_free(domain);
 566         isl_schedule_node_free(node);
 567
 568         return list;
 569 }
 570
 571 /* Construct an isl_band structure from the given sequence node
 572  * (or set node that is treated as a sequence node).
 573  * A single-dimensional band is created with as schedule for each of
 574  * filters of the children, the corresponding child position.
 575  * "domain" is the universe set of the domain elements that reach "node".
 576  * "parent" is the parent isl_band of the isl_band constructed
 577  * by this function.
 578  */
 579 static __isl_give isl_band_list *construct_band_list_sequence(
 580         __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
 581         __isl_keep isl_band *parent)
 582 {
 583         int i, n;
 584         isl_ctx *ctx;
 585         isl_band *band = NULL;
 586         isl_space *space;
 587         isl_union_pw_multi_aff *upma;
 588
 589         if (!node || !domain)
 590                 goto error;
 591
 592         ctx = isl_schedule_node_get_ctx(node);
 593         band = isl_band_alloc(ctx);
 594         if (!band)
 595                 goto error;
 596
 597         band->schedule = node->schedule;
 598         band->parent = parent;
 599         band->n = 1;
 600         band->coincident = isl_calloc_array(ctx, int, band->n);
 601         if (!band->coincident)
 602                 goto error;
 603
 604         n = isl_schedule_node_n_children(node);
 605         space = isl_union_set_get_space(domain);
 606         upma = isl_union_pw_multi_aff_empty(isl_space_copy(space));
 607
 608         space = isl_space_set_from_params(space);
 609         space = isl_space_add_dims(space, isl_dim_set, 1);
 610
 611         for (i = 0; i < n; ++i) {
 612                 isl_schedule_node *child;
 613                 isl_union_set *filter;
 614                 isl_val *v;
 615                 isl_val_list *vl;
 616                 isl_multi_val *mv;
 617                 isl_union_pw_multi_aff *upma_i;
 618
 619                 child = isl_schedule_node_get_child(node, i);
 620                 filter = isl_schedule_node_filter_get_filter(child);
 621                 isl_schedule_node_free(child);
 622                 filter = isl_union_set_intersect(filter,
 623                                                 isl_union_set_copy(domain));
 624                 v = isl_val_int_from_si(ctx, i);
 625                 vl = isl_val_list_from_val(v);
 626                 mv = isl_multi_val_from_val_list(isl_space_copy(space), vl);
 627                 upma_i = isl_union_pw_multi_aff_multi_val_on_domain(filter, mv);
 628                 upma = isl_union_pw_multi_aff_union_add(upma, upma_i);
 629         }
 630
 631         isl_space_free(space);
 632
 633         band->pma = upma;
 634         if (!band->pma)
 635                 goto error;
 636
 637         band->children = construct_band_list_from_children(node, domain, band);
 638         if (!band->children)
 639                 band = isl_band_free(band);
 640         return isl_band_list_from_band(band);
 641 error:
 642         isl_union_set_free(domain);
 643         isl_schedule_node_free(node);
 644         isl_band_free(band);
 645         return NULL;
 646 }
 647
 648 /* Construct a list of isl_band structures from "node" depending
 649  * on the type of "node".
 650  * "domain" is the universe set of the domain elements that reach "node".
 651  * "parent" is the parent isl_band of the isl_band structures constructed
 652  * by this function.
 653  *
 654  * If schedule_separate_components is set then set nodes are treated
 655  * as sequence nodes.  Otherwise, we directly extract an (implicitly
 656  * parallel) list of isl_band structures.
 657  *
 658  * If "node" is a filter, then "domain" is updated by the filter.
 659  */
 660 static __isl_give isl_band_list *construct_band_list(
 661         __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
 662         __isl_keep isl_band *parent)
 663 {
 664         enum isl_schedule_node_type type;
 665         isl_ctx *ctx;
 666         isl_band *band;
 667         isl_band_list *list;
 668         isl_union_set *filter;
 669
 670         if (!node || !domain)
 671                 goto error;
 672
 673         type = isl_schedule_node_get_type(node);
 674         switch (type) {
 675         case isl_schedule_node_error:
 676                 goto error;
 677         case isl_schedule_node_domain:
 678                 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
 679                         "internal domain nodes not allowed", goto error);
 680         case isl_schedule_node_filter:
 681                 filter = isl_schedule_node_filter_get_filter(node);
 682                 domain = isl_union_set_intersect(domain, filter);
 683                 node = isl_schedule_node_child(node, 0);
 684                 return construct_band_list(node, domain, parent);
 685         case isl_schedule_node_set:
 686                 ctx = isl_schedule_node_get_ctx(node);
 687                 if (isl_options_get_schedule_separate_components(ctx))
 688                         return construct_band_list_sequence(node, domain,
 689                                                             parent);
 690                 else
 691                         return construct_band_list_from_children(node, domain,
 692                                                             parent);
 693         case isl_schedule_node_sequence:
 694                 return construct_band_list_sequence(node, domain, parent);
 695         case isl_schedule_node_leaf:
 696         case isl_schedule_node_band:
 697                 band = construct_band(node, domain, parent);
 698                 list = isl_band_list_from_band(band);
 699                 break;
 700         }
 701
 702         return list;
 703 error:
 704         isl_union_set_free(domain);
 705         isl_schedule_node_free(node);
 706         return NULL;
 707 }
 708
 709 /* Return the roots of a band forest representation of the schedule.
 710  * The band forest is constructed from the schedule tree,
 711  * but once such a band forest is
 712  * constructed, we forget about the original schedule tree since
 713  * the user may modify the schedule through the band forest.
 714  */
 715 __isl_give isl_band_list *isl_schedule_get_band_forest(
 716         __isl_keep isl_schedule *schedule)
 717 {
 718         isl_schedule_node *node;
 719         isl_union_set *domain;
 720
 721         if (!schedule)
 722                 return NULL;
 723         if (schedule->root) {
 724                 node = isl_schedule_get_root(schedule);
 725                 domain = isl_schedule_node_domain_get_domain(node);
 726                 domain = isl_union_set_universe(domain);
 727                 node = isl_schedule_node_child(node, 0);
 728
 729                 schedule->band_forest = construct_band_list(node, domain, NULL);
 730                 schedule->root = isl_schedule_tree_free(schedule->root);
 731         }
 732         return isl_band_list_dup(schedule->band_forest);
 733 }
 734
 735 /* Call "fn" on each band in the schedule in depth-first post-order.
 736  */
 737 int isl_schedule_foreach_band(__isl_keep isl_schedule *sched,
 738         int (*fn)(__isl_keep isl_band *band, void *user), void *user)
 739 {
 740         int r;
 741         isl_band_list *forest;
 742
 743         if (!sched)
 744                 return -1;
 745
 746         forest = isl_schedule_get_band_forest(sched);
 747         r = isl_band_list_foreach_band(forest, fn, user);
 748         isl_band_list_free(forest);
 749
 750         return r;
 751 }
 752
 753 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
 754         __isl_keep isl_band_list *list);
 755
 756 static __isl_give isl_printer *print_band(__isl_take isl_printer *p,
 757         __isl_keep isl_band *band)
 758 {
 759         isl_band_list *children;
 760
 761         p = isl_printer_start_line(p);
 762         p = isl_printer_print_union_pw_multi_aff(p, band->pma);
 763         p = isl_printer_end_line(p);
 764
 765         if (!isl_band_has_children(band))
 766                 return p;
 767
 768         children = isl_band_get_children(band);
 769
 770         p = isl_printer_indent(p, 4);
 771         p = print_band_list(p, children);
 772         p = isl_printer_indent(p, -4);
 773
 774         isl_band_list_free(children);
 775
 776         return p;
 777 }
 778
 779 static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
 780         __isl_keep isl_band_list *list)
 781 {
 782         int i, n;
 783
 784         n = isl_band_list_n_band(list);
 785         for (i = 0; i < n; ++i) {
 786                 isl_band *band;
 787                 band = isl_band_list_get_band(list, i);
 788                 p = print_band(p, band);
 789                 isl_band_free(band);
 790         }
 791
 792         return p;
 793 }
 794
 795 /* Insert a band node with partial schedule "partial" between the domain
 796  * root node of "schedule" and its single child.
 797  * Return a pointer to the updated schedule.
 798  */
 799 __isl_give isl_schedule *isl_schedule_insert_partial_schedule(
 800         __isl_take isl_schedule *schedule,
 801         __isl_take isl_multi_union_pw_aff *partial)
 802 {
 803         isl_schedule_node *node;
 804
 805         node = isl_schedule_get_root(schedule);
 806         isl_schedule_free(schedule);
 807         if (!node)
 808                 goto error;
 809         if (isl_schedule_node_get_type(node) != isl_schedule_node_domain)
 810                 isl_die(isl_schedule_node_get_ctx(node), isl_error_internal,
 811                         "root node not a domain node", goto error);
 812
 813         node = isl_schedule_node_child(node, 0);
 814         node = isl_schedule_node_insert_partial_schedule(node, partial);
 815
 816         schedule = isl_schedule_node_get_schedule(node);
 817         isl_schedule_node_free(node);
 818
 819         return schedule;
 820 error:
 821         isl_schedule_node_free(node);
 822         isl_multi_union_pw_aff_free(partial);
 823         return NULL;
 824 }
 825
 826 /* Return a tree with as top-level node a filter corresponding to "filter" and
 827  * as child, the (single) child of "tree".
 828  * However, if this single child is of type "type", then the filter is inserted
 829  * in the children of this single child instead.
 830  */
 831 static __isl_give isl_schedule_tree *insert_filter_in_child_of_type(
 832         __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter,
 833         enum isl_schedule_node_type type)
 834 {
 835         if (!isl_schedule_tree_has_children(tree)) {
 836                 isl_schedule_tree_free(tree);
 837                 return isl_schedule_tree_from_filter(filter);
 838         } else {
 839                 tree = isl_schedule_tree_child(tree, 0);
 840         }
 841
 842         if (isl_schedule_tree_get_type(tree) == type)
 843                 tree = isl_schedule_tree_children_insert_filter(tree, filter);
 844         else
 845                 tree = isl_schedule_tree_insert_filter(tree, filter);
 846
 847         return tree;
 848 }
 849
 850 /* Construct a schedule that combines the schedules "schedule1" and "schedule2"
 851  * with a top-level node (underneath the domain node) of type "type",
 852  * either isl_schedule_node_sequence or isl_schedule_node_set.
 853  * The domains of the two schedules are assumed to be disjoint.
 854  *
 855  * The new schedule has as domain the union of the domains of the two
 856  * schedules.  The child of the domain node is a node of type "type"
 857  * with two filters corresponding to the domains of the input schedules.
 858  * If one (or both) of the top-level nodes of the two schedules is itself
 859  * of type "type", then the filter is pushed into the children of that
 860  * node and the sequence of set is flattened.
 861  */
 862 __isl_give isl_schedule *isl_schedule_pair(enum isl_schedule_node_type type,
 863         __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)
 864 {
 865         int disjoint;
 866         isl_ctx *ctx;
 867         enum isl_schedule_node_type root_type;
 868         isl_schedule_tree *tree1, *tree2;
 869         isl_union_set *filter1, *filter2, *domain;
 870
 871         if (!schedule1 || !schedule2)
 872                 goto error;
 873
 874         root_type = isl_schedule_tree_get_type(schedule1->root);
 875         if (root_type != isl_schedule_node_domain)
 876                 isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal,
 877                         "root node not a domain node", goto error);
 878         root_type = isl_schedule_tree_get_type(schedule2->root);
 879         if (root_type != isl_schedule_node_domain)
 880                 isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal,
 881                         "root node not a domain node", goto error);
 882
 883         ctx = isl_schedule_get_ctx(schedule1);
 884         tree1 = isl_schedule_tree_copy(schedule1->root);
 885         filter1 = isl_schedule_tree_domain_get_domain(tree1);
 886         tree2 = isl_schedule_tree_copy(schedule2->root);
 887         filter2 = isl_schedule_tree_domain_get_domain(tree2);
 888
 889         isl_schedule_free(schedule1);
 890         isl_schedule_free(schedule2);
 891
 892         disjoint = isl_union_set_is_disjoint(filter1, filter2);
 893         if (disjoint < 0)
 894                 filter1 = isl_union_set_free(filter1);
 895         if (!disjoint)
 896                 isl_die(ctx, isl_error_invalid,
 897                         "schedule domains not disjoint",
 898                         filter1 = isl_union_set_free(filter1));
 899
 900         domain = isl_union_set_union(isl_union_set_copy(filter1),
 901                                     isl_union_set_copy(filter2));
 902         filter1 = isl_union_set_gist(filter1, isl_union_set_copy(domain));
 903         filter2 = isl_union_set_gist(filter2, isl_union_set_copy(domain));
 904
 905         tree1 = insert_filter_in_child_of_type(tree1, filter1, type);
 906         tree2 = insert_filter_in_child_of_type(tree2, filter2, type);
 907
 908         tree1 = isl_schedule_tree_from_pair(type, tree1, tree2);
 909         tree1 = isl_schedule_tree_insert_domain(tree1, domain);
 910
 911         return isl_schedule_from_schedule_tree(ctx, tree1);
 912 error:
 913         isl_schedule_free(schedule1);
 914         isl_schedule_free(schedule2);
 915         return NULL;
 916 }
 917
 918 /* Construct a schedule that combines the schedules "schedule1" and "schedule2"
 919  * through a sequence node.
 920  * The domains of the input schedules are assumed to be disjoint.
 921  */
 922 __isl_give isl_schedule *isl_schedule_sequence(
 923         __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)
 924 {
 925         return isl_schedule_pair(isl_schedule_node_sequence,
 926                                 schedule1, schedule2);
 927 }
 928
 929 /* Construct a schedule that combines the schedules "schedule1" and "schedule2"
 930  * through a set node.
 931  * The domains of the input schedules are assumed to be disjoint.
 932  */
 933 __isl_give isl_schedule *isl_schedule_set(
 934         __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)
 935 {
 936         return isl_schedule_pair(isl_schedule_node_set, schedule1, schedule2);
 937 }
 938
 939 /* Print "schedule" to "p".
 940  *
 941  * If "schedule" was created from a schedule tree, then we print
 942  * the schedule tree representation.  Otherwise, we print
 943  * the band forest representation.
 944  */
 945 __isl_give isl_printer *isl_printer_print_schedule(__isl_take isl_printer *p,
 946         __isl_keep isl_schedule *schedule)
 947 {
 948         isl_band_list *forest;
 949
 950         if (!schedule)
 951                 return isl_printer_free(p);
 952
 953         if (schedule->root)
 954                 return isl_printer_print_schedule_tree(p, schedule->root);
 955
 956         forest = isl_schedule_get_band_forest(schedule);
 957
 958         p = print_band_list(p, forest);
 959
 960         isl_band_list_free(forest);
 961
 962         return p;
 963 }
 964
 965 void isl_schedule_dump(__isl_keep isl_schedule *schedule)
 966 {
 967         isl_printer *printer;
 968
 969         if (!schedule)
 970                 return;
 971
 972         printer = isl_printer_to_file(isl_schedule_get_ctx(schedule), stderr);
 973         printer = isl_printer_set_yaml_style(printer, ISL_YAML_STYLE_BLOCK);
 974         printer = isl_printer_print_schedule(printer, schedule);
 975
 976         isl_printer_free(printer);
 977 }