isl_schedule_tree.c

   1 /*
   2  * Copyright 2013-2014 Ecole Normale Superieure
   3  * Copyright 2014      INRIA Rocquencourt
   4  *
   5  * Use of this software is governed by the MIT license
   6  *
   7  * Written by Sven Verdoolaege,
   8  * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
   9  * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
  10  * B.P. 105 - 78153 Le Chesnay, France
  11  */
  12
  13 #include <isl/map.h>
  14 #include <isl_schedule_band.h>
  15 #include <isl_schedule_private.h>
  16
  17 #undef EL
  18 #define EL isl_schedule_tree
  19
  20 #include <isl_list_templ.h>
  21
  22 #undef BASE
  23 #define BASE schedule_tree
  24
  25 #include <isl_list_templ.c>
  26
  27 /* Is "tree" the leaf of a schedule tree?
  28  */
  29 int isl_schedule_tree_is_leaf(__isl_keep isl_schedule_tree *tree)
  30 {
  31         return isl_schedule_tree_get_type(tree) == isl_schedule_node_leaf;
  32 }
  33
  34 /* Create a new schedule tree of type "type".
  35  * The caller is responsible for filling in the type specific fields and
  36  * the children.
  37  *
  38  * By default, the single node tree does not have any anchored nodes.
  39  * The caller is responsible for updating the anchored field if needed.
  40  */
  41 static __isl_give isl_schedule_tree *isl_schedule_tree_alloc(isl_ctx *ctx,
  42         enum isl_schedule_node_type type)
  43 {
  44         isl_schedule_tree *tree;
  45
  46         if (type == isl_schedule_node_error)
  47                 return NULL;
  48
  49         tree = isl_calloc_type(ctx, isl_schedule_tree);
  50         if (!tree)
  51                 return NULL;
  52
  53         tree->ref = 1;
  54         tree->ctx = ctx;
  55         isl_ctx_ref(ctx);
  56         tree->type = type;
  57         tree->anchored = 0;
  58
  59         return tree;
  60 }
  61
  62 /* Return a fresh copy of "tree".
  63  */
  64 __isl_take isl_schedule_tree *isl_schedule_tree_dup(
  65         __isl_keep isl_schedule_tree *tree)
  66 {
  67         isl_ctx *ctx;
  68         isl_schedule_tree *dup;
  69
  70         if (!tree)
  71                 return NULL;
  72
  73         ctx = isl_schedule_tree_get_ctx(tree);
  74         dup = isl_schedule_tree_alloc(ctx, tree->type);
  75         if (!dup)
  76                 return NULL;
  77
  78         switch (tree->type) {
  79         case isl_schedule_node_error:
  80                 isl_die(ctx, isl_error_internal,
  81                         "allocation should have failed",
  82                         isl_schedule_tree_free(dup));
  83         case isl_schedule_node_band:
  84                 dup->band = isl_schedule_band_copy(tree->band);
  85                 if (!dup->band)
  86                         return isl_schedule_tree_free(dup);
  87                 break;
  88         case isl_schedule_node_context:
  89                 dup->context = isl_set_copy(tree->context);
  90                 if (!dup->context)
  91                         return isl_schedule_tree_free(dup);
  92                 break;
  93         case isl_schedule_node_domain:
  94                 dup->domain = isl_union_set_copy(tree->domain);
  95                 if (!dup->domain)
  96                         return isl_schedule_tree_free(dup);
  97                 break;
  98         case isl_schedule_node_filter:
  99                 dup->filter = isl_union_set_copy(tree->filter);
 100                 if (!dup->filter)
 101                         return isl_schedule_tree_free(dup);
 102                 break;
 103         case isl_schedule_node_leaf:
 104         case isl_schedule_node_sequence:
 105         case isl_schedule_node_set:
 106                 break;
 107         }
 108
 109         if (tree->children) {
 110                 dup->children = isl_schedule_tree_list_copy(tree->children);
 111                 if (!dup->children)
 112                         return isl_schedule_tree_free(dup);
 113         }
 114         dup->anchored = tree->anchored;
 115
 116         return dup;
 117 }
 118
 119 /* Return an isl_schedule_tree that is equal to "tree" and that has only
 120  * a single reference.
 121  *
 122  * This function is called before a tree is modified.
 123  * A static tree (with negative reference count) should never be modified,
 124  * so it is not allowed to call this function on a static tree.
 125  */
 126 __isl_give isl_schedule_tree *isl_schedule_tree_cow(
 127         __isl_take isl_schedule_tree *tree)
 128 {
 129         if (!tree)
 130                 return NULL;
 131
 132         if (tree->ref < 0)
 133                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
 134                         "static trees cannot be modified",
 135                         return isl_schedule_tree_free(tree));
 136
 137         if (tree->ref == 1)
 138                 return tree;
 139         tree->ref--;
 140         return isl_schedule_tree_dup(tree);
 141 }
 142
 143 /* Return a new reference to "tree".
 144  *
 145  * A static tree (with negative reference count) does not keep track
 146  * of the number of references and should not be modified.
 147  */
 148 __isl_give isl_schedule_tree *isl_schedule_tree_copy(
 149         __isl_keep isl_schedule_tree *tree)
 150 {
 151         if (!tree)
 152                 return NULL;
 153
 154         if (tree->ref < 0)
 155                 return tree;
 156
 157         tree->ref++;
 158         return tree;
 159 }
 160
 161 /* Free "tree" and return NULL.
 162  */
 163 __isl_null isl_schedule_tree *isl_schedule_tree_free(
 164         __isl_take isl_schedule_tree *tree)
 165 {
 166         if (!tree)
 167                 return NULL;
 168         if (tree->ref < 0)
 169                 return NULL;
 170         if (--tree->ref > 0)
 171                 return NULL;
 172
 173         switch (tree->type) {
 174         case isl_schedule_node_band:
 175                 isl_schedule_band_free(tree->band);
 176                 break;
 177         case isl_schedule_node_context:
 178                 isl_set_free(tree->context);
 179                 break;
 180         case isl_schedule_node_domain:
 181                 isl_union_set_free(tree->domain);
 182                 break;
 183         case isl_schedule_node_filter:
 184                 isl_union_set_free(tree->filter);
 185                 break;
 186         case isl_schedule_node_sequence:
 187         case isl_schedule_node_set:
 188         case isl_schedule_node_error:
 189         case isl_schedule_node_leaf:
 190                 break;
 191         }
 192         isl_schedule_tree_list_free(tree->children);
 193         isl_ctx_deref(tree->ctx);
 194         free(tree);
 195
 196         return NULL;
 197 }
 198
 199 /* Create and return a new leaf schedule tree.
 200  */
 201 __isl_give isl_schedule_tree *isl_schedule_tree_leaf(isl_ctx *ctx)
 202 {
 203         return isl_schedule_tree_alloc(ctx, isl_schedule_node_leaf);
 204 }
 205
 206 /* Create a new band schedule tree referring to "band"
 207  * with no children.
 208  */
 209 __isl_give isl_schedule_tree *isl_schedule_tree_from_band(
 210         __isl_take isl_schedule_band *band)
 211 {
 212         isl_ctx *ctx;
 213         isl_schedule_tree *tree;
 214
 215         if (!band)
 216                 return NULL;
 217
 218         ctx = isl_schedule_band_get_ctx(band);
 219         tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_band);
 220         if (!tree)
 221                 goto error;
 222
 223         tree->band = band;
 224         tree->anchored = isl_schedule_band_is_anchored(band);
 225
 226         return tree;
 227 error:
 228         isl_schedule_band_free(band);
 229         return NULL;
 230 }
 231
 232 /* Create a new context schedule tree with the given context and no children.
 233  * Since the context references the outer schedule dimension,
 234  * the tree is anchored.
 235  */
 236 __isl_give isl_schedule_tree *isl_schedule_tree_from_context(
 237         __isl_take isl_set *context)
 238 {
 239         isl_ctx *ctx;
 240         isl_schedule_tree *tree;
 241
 242         if (!context)
 243                 return NULL;
 244
 245         ctx = isl_set_get_ctx(context);
 246         tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_context);
 247         if (!tree)
 248                 goto error;
 249
 250         tree->context = context;
 251         tree->anchored = 1;
 252
 253         return tree;
 254 error:
 255         isl_set_free(context);
 256         return NULL;
 257 }
 258
 259 /* Create a new domain schedule tree with the given domain and no children.
 260  */
 261 __isl_give isl_schedule_tree *isl_schedule_tree_from_domain(
 262         __isl_take isl_union_set *domain)
 263 {
 264         isl_ctx *ctx;
 265         isl_schedule_tree *tree;
 266
 267         if (!domain)
 268                 return NULL;
 269
 270         ctx = isl_union_set_get_ctx(domain);
 271         tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_domain);
 272         if (!tree)
 273                 goto error;
 274
 275         tree->domain = domain;
 276
 277         return tree;
 278 error:
 279         isl_union_set_free(domain);
 280         return NULL;
 281 }
 282
 283 /* Create a new filter schedule tree with the given filter and no children.
 284  */
 285 __isl_give isl_schedule_tree *isl_schedule_tree_from_filter(
 286         __isl_take isl_union_set *filter)
 287 {
 288         isl_ctx *ctx;
 289         isl_schedule_tree *tree;
 290
 291         if (!filter)
 292                 return NULL;
 293
 294         ctx = isl_union_set_get_ctx(filter);
 295         tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_filter);
 296         if (!tree)
 297                 goto error;
 298
 299         tree->filter = filter;
 300
 301         return tree;
 302 error:
 303         isl_union_set_free(filter);
 304         return NULL;
 305 }
 306
 307 /* Does "tree" have any node that depends on its position
 308  * in the complete schedule tree?
 309  */
 310 int isl_schedule_tree_is_subtree_anchored(__isl_keep isl_schedule_tree *tree)
 311 {
 312         return tree ? tree->anchored : -1;
 313 }
 314
 315 /* Does the root node of "tree" depend on its position in the complete
 316  * schedule tree?
 317  * Band nodes may be anchored depending on the associated AST build options.
 318  * Context nodes are always anchored.
 319  */
 320 int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree *tree)
 321 {
 322         if (!tree)
 323                 return -1;
 324
 325         switch (isl_schedule_tree_get_type(tree)) {
 326         case isl_schedule_node_error:
 327                 return -1;
 328         case isl_schedule_node_band:
 329                 return isl_schedule_band_is_anchored(tree->band);
 330         case isl_schedule_node_context:
 331                 return 1;
 332         case isl_schedule_node_domain:
 333         case isl_schedule_node_filter:
 334         case isl_schedule_node_leaf:
 335         case isl_schedule_node_sequence:
 336         case isl_schedule_node_set:
 337                 return 0;
 338         }
 339 }
 340
 341 /* Update the anchored field of "tree" based on whether the root node
 342  * itself in anchored and the anchored fields of the children.
 343  *
 344  * This function should be called whenever the children of a tree node
 345  * are changed or the anchoredness of the tree root itself changes.
 346  */
 347 __isl_give isl_schedule_tree *isl_schedule_tree_update_anchored(
 348         __isl_take isl_schedule_tree *tree)
 349 {
 350         int i, n;
 351         int anchored;
 352
 353         if (!tree)
 354                 return NULL;
 355
 356         anchored = isl_schedule_tree_is_anchored(tree);
 357         if (anchored < 0)
 358                 return isl_schedule_tree_free(tree);
 359
 360         n = isl_schedule_tree_list_n_schedule_tree(tree->children);
 361         for (i = 0; !anchored && i < n; ++i) {
 362                 isl_schedule_tree *child;
 363
 364                 child = isl_schedule_tree_get_child(tree, i);
 365                 if (!child)
 366                         return isl_schedule_tree_free(tree);
 367                 anchored = child->anchored;
 368                 isl_schedule_tree_free(child);
 369         }
 370
 371         if (anchored == tree->anchored)
 372                 return tree;
 373         tree = isl_schedule_tree_cow(tree);
 374         if (!tree)
 375                 return NULL;
 376         tree->anchored = anchored;
 377         return tree;
 378 }
 379
 380 /* Create a new tree of the given type (isl_schedule_node_sequence or
 381  * isl_schedule_node_set) with the given children.
 382  */
 383 __isl_give isl_schedule_tree *isl_schedule_tree_from_children(
 384         enum isl_schedule_node_type type,
 385         __isl_take isl_schedule_tree_list *list)
 386 {
 387         isl_ctx *ctx;
 388         isl_schedule_tree *tree;
 389
 390         if (!list)
 391                 return NULL;
 392
 393         ctx = isl_schedule_tree_list_get_ctx(list);
 394         tree = isl_schedule_tree_alloc(ctx, type);
 395         if (!tree)
 396                 goto error;
 397
 398         tree->children = list;
 399         tree = isl_schedule_tree_update_anchored(tree);
 400
 401         return tree;
 402 error:
 403         isl_schedule_tree_list_free(list);
 404         return NULL;
 405 }
 406
 407 /* Construct a tree with a root node of type "type" and as children
 408  * "tree1" and "tree2".
 409  * If the root of one (or both) of the input trees is itself of type "type",
 410  * then the tree is replaced by its children.
 411  */
 412 __isl_give isl_schedule_tree *isl_schedule_tree_from_pair(
 413         enum isl_schedule_node_type type, __isl_take isl_schedule_tree *tree1,
 414         __isl_take isl_schedule_tree *tree2)
 415 {
 416         isl_ctx *ctx;
 417         isl_schedule_tree_list *list;
 418
 419         if (!tree1 || !tree2)
 420                 goto error;
 421
 422         ctx = isl_schedule_tree_get_ctx(tree1);
 423         if (isl_schedule_tree_get_type(tree1) == type) {
 424                 list = isl_schedule_tree_list_copy(tree1->children);
 425                 isl_schedule_tree_free(tree1);
 426         } else {
 427                 list = isl_schedule_tree_list_alloc(ctx, 2);
 428                 list = isl_schedule_tree_list_add(list, tree1);
 429         }
 430         if (isl_schedule_tree_get_type(tree2) == type) {
 431                 isl_schedule_tree_list *children;
 432
 433                 children = isl_schedule_tree_list_copy(tree2->children);
 434                 list = isl_schedule_tree_list_concat(list, children);
 435                 isl_schedule_tree_free(tree2);
 436         } else {
 437                 list = isl_schedule_tree_list_add(list, tree2);
 438         }
 439
 440         return isl_schedule_tree_from_children(type, list);
 441 error:
 442         isl_schedule_tree_free(tree1);
 443         isl_schedule_tree_free(tree2);
 444         return NULL;
 445 }
 446
 447 /* Return the isl_ctx to which "tree" belongs.
 448  */
 449 isl_ctx *isl_schedule_tree_get_ctx(__isl_keep isl_schedule_tree *tree)
 450 {
 451         return tree ? tree->ctx : NULL;
 452 }
 453
 454 /* Return the type of the root of the tree or isl_schedule_node_error
 455  * on error.
 456  */
 457 enum isl_schedule_node_type isl_schedule_tree_get_type(
 458         __isl_keep isl_schedule_tree *tree)
 459 {
 460         return tree ? tree->type : isl_schedule_node_error;
 461 }
 462
 463 /* Are "tree1" and "tree2" obviously equal to each other?
 464  */
 465 int isl_schedule_tree_plain_is_equal(__isl_keep isl_schedule_tree *tree1,
 466         __isl_keep isl_schedule_tree *tree2)
 467 {
 468         int equal;
 469         int i, n;
 470
 471         if (!tree1 || !tree2)
 472                 return -1;
 473         if (tree1 == tree2)
 474                 return 1;
 475         if (tree1->type != tree2->type)
 476                 return 0;
 477
 478         switch (tree1->type) {
 479         case isl_schedule_node_band:
 480                 equal = isl_schedule_band_plain_is_equal(tree1->band,
 481                                                         tree2->band);
 482                 break;
 483         case isl_schedule_node_context:
 484                 equal = isl_set_is_equal(tree1->context, tree2->context);
 485                 break;
 486         case isl_schedule_node_domain:
 487                 equal = isl_union_set_is_equal(tree1->domain, tree2->domain);
 488                 break;
 489         case isl_schedule_node_filter:
 490                 equal = isl_union_set_is_equal(tree1->filter, tree2->filter);
 491                 break;
 492         case isl_schedule_node_leaf:
 493         case isl_schedule_node_sequence:
 494         case isl_schedule_node_set:
 495                 equal = 1;
 496                 break;
 497         case isl_schedule_node_error:
 498                 equal = -1;
 499                 break;
 500         }
 501
 502         if (equal < 0 || !equal)
 503                 return equal;
 504
 505         n = isl_schedule_tree_n_children(tree1);
 506         if (n != isl_schedule_tree_n_children(tree2))
 507                 return 0;
 508         for (i = 0; i < n; ++i) {
 509                 isl_schedule_tree *child1, *child2;
 510
 511                 child1 = isl_schedule_tree_get_child(tree1, i);
 512                 child2 = isl_schedule_tree_get_child(tree2, i);
 513                 equal = isl_schedule_tree_plain_is_equal(child1, child2);
 514                 isl_schedule_tree_free(child1);
 515                 isl_schedule_tree_free(child2);
 516
 517                 if (equal < 0 || !equal)
 518                         return equal;
 519         }
 520
 521         return 1;
 522 }
 523
 524 /* Does "tree" have any children, other than an implicit leaf.
 525  */
 526 int isl_schedule_tree_has_children(__isl_keep isl_schedule_tree *tree)
 527 {
 528         if (!tree)
 529                 return -1;
 530
 531         return tree->children != NULL;
 532 }
 533
 534 /* Return the number of children of "tree", excluding implicit leaves.
 535  */
 536 int isl_schedule_tree_n_children(__isl_keep isl_schedule_tree *tree)
 537 {
 538         if (!tree)
 539                 return -1;
 540
 541         return isl_schedule_tree_list_n_schedule_tree(tree->children);
 542 }
 543
 544 /* Return a copy of the (explicit) child at position "pos" of "tree".
 545  */
 546 __isl_give isl_schedule_tree *isl_schedule_tree_get_child(
 547         __isl_keep isl_schedule_tree *tree, int pos)
 548 {
 549         if (!tree)
 550                 return NULL;
 551         if (!tree->children)
 552                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
 553                         "schedule tree has no explicit children", return NULL);
 554         return isl_schedule_tree_list_get_schedule_tree(tree->children, pos);
 555 }
 556
 557 /* Return a copy of the (explicit) child at position "pos" of "tree" and
 558  * free "tree".
 559  */
 560 __isl_give isl_schedule_tree *isl_schedule_tree_child(
 561         __isl_take isl_schedule_tree *tree, int pos)
 562 {
 563         isl_schedule_tree *child;
 564
 565         child = isl_schedule_tree_get_child(tree, pos);
 566         isl_schedule_tree_free(tree);
 567         return child;
 568 }
 569
 570 /* Remove all (explicit) children from "tree".
 571  */
 572 __isl_give isl_schedule_tree *isl_schedule_tree_reset_children(
 573         __isl_take isl_schedule_tree *tree)
 574 {
 575         tree = isl_schedule_tree_cow(tree);
 576         if (!tree)
 577                 return NULL;
 578         tree->children = isl_schedule_tree_list_free(tree->children);
 579         return tree;
 580 }
 581
 582 /* Remove the child at position "pos" from the children of "tree".
 583  * If there was only one child to begin with, then remove all children.
 584  */
 585 __isl_give isl_schedule_tree *isl_schedule_tree_drop_child(
 586         __isl_take isl_schedule_tree *tree, int pos)
 587 {
 588         int n;
 589
 590         tree = isl_schedule_tree_cow(tree);
 591         if (!tree)
 592                 return NULL;
 593
 594         if (!isl_schedule_tree_has_children(tree))
 595                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
 596                         "tree does not have any explicit children",
 597                         return isl_schedule_tree_free(tree));
 598         n = isl_schedule_tree_list_n_schedule_tree(tree->children);
 599         if (pos < 0 || pos >= n)
 600                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
 601                         "position out of bounds",
 602                         return isl_schedule_tree_free(tree));
 603         if (n == 1)
 604                 return isl_schedule_tree_reset_children(tree);
 605
 606         tree->children = isl_schedule_tree_list_drop(tree->children, pos, 1);
 607         if (!tree->children)
 608                 return isl_schedule_tree_free(tree);
 609
 610         return tree;
 611 }
 612
 613 /* Replace the child at position "pos" of "tree" by "child".
 614  *
 615  * If the new child is a leaf, then it is not explicitly
 616  * recorded in the list of children.  Instead, the list of children
 617  * (which is assumed to have only one element) is removed.
 618  * Note that the children of set and sequence nodes are always
 619  * filters, so they cannot be replaced by empty trees.
 620  */
 621 __isl_give isl_schedule_tree *isl_schedule_tree_replace_child(
 622         __isl_take isl_schedule_tree *tree, int pos,
 623         __isl_take isl_schedule_tree *child)
 624 {
 625         tree = isl_schedule_tree_cow(tree);
 626         if (!tree || !child)
 627                 goto error;
 628
 629         if (isl_schedule_tree_is_leaf(child)) {
 630                 isl_schedule_tree_free(child);
 631                 if (!tree->children && pos == 0)
 632                         return tree;
 633                 if (isl_schedule_tree_n_children(tree) != 1)
 634                         isl_die(isl_schedule_tree_get_ctx(tree),
 635                                 isl_error_internal,
 636                                 "can only replace single child by leaf",
 637                                 goto error);
 638                 return isl_schedule_tree_reset_children(tree);
 639         }
 640
 641         if (!tree->children && pos == 0)
 642                 tree->children =
 643                         isl_schedule_tree_list_from_schedule_tree(child);
 644         else
 645                 tree->children = isl_schedule_tree_list_set_schedule_tree(
 646                                 tree->children, pos, child);
 647
 648         if (!tree->children)
 649                 return isl_schedule_tree_free(tree);
 650         tree = isl_schedule_tree_update_anchored(tree);
 651
 652         return tree;
 653 error:
 654         isl_schedule_tree_free(tree);
 655         isl_schedule_tree_free(child);
 656         return NULL;
 657 }
 658
 659 /* Replace the (explicit) children of "tree" by "children"?
 660  */
 661 __isl_give isl_schedule_tree *isl_schedule_tree_set_children(
 662         __isl_take isl_schedule_tree *tree,
 663         __isl_take isl_schedule_tree_list *children)
 664 {
 665         tree = isl_schedule_tree_cow(tree);
 666         if (!tree || !children)
 667                 goto error;
 668         isl_schedule_tree_list_free(tree->children);
 669         tree->children = children;
 670         return tree;
 671 error:
 672         isl_schedule_tree_free(tree);
 673         isl_schedule_tree_list_free(children);
 674         return NULL;
 675 }
 676
 677 /* Create a new band schedule tree referring to "band"
 678  * with "tree" as single child.
 679  */
 680 __isl_give isl_schedule_tree *isl_schedule_tree_insert_band(
 681         __isl_take isl_schedule_tree *tree, __isl_take isl_schedule_band *band)
 682 {
 683         isl_schedule_tree *res;
 684
 685         res = isl_schedule_tree_from_band(band);
 686         return isl_schedule_tree_replace_child(res, 0, tree);
 687 }
 688
 689 /* Create a new context schedule tree with the given context and
 690  * with "tree" as single child.
 691  */
 692 __isl_give isl_schedule_tree *isl_schedule_tree_insert_context(
 693         __isl_take isl_schedule_tree *tree, __isl_take isl_set *context)
 694 {
 695         isl_schedule_tree *res;
 696
 697         res = isl_schedule_tree_from_context(context);
 698         return isl_schedule_tree_replace_child(res, 0, tree);
 699 }
 700
 701 /* Create a new domain schedule tree with the given domain and
 702  * with "tree" as single child.
 703  */
 704 __isl_give isl_schedule_tree *isl_schedule_tree_insert_domain(
 705         __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
 706 {
 707         isl_schedule_tree *res;
 708
 709         res = isl_schedule_tree_from_domain(domain);
 710         return isl_schedule_tree_replace_child(res, 0, tree);
 711 }
 712
 713 /* Create a new filter schedule tree with the given filter and single child.
 714  *
 715  * If the root of "tree" is itself a filter node, then the two
 716  * filter nodes are merged into one node.
 717  */
 718 __isl_give isl_schedule_tree *isl_schedule_tree_insert_filter(
 719         __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
 720 {
 721         isl_schedule_tree *res;
 722
 723         if (isl_schedule_tree_get_type(tree) == isl_schedule_node_filter) {
 724                 isl_union_set *tree_filter;
 725
 726                 tree_filter = isl_schedule_tree_filter_get_filter(tree);
 727                 tree_filter = isl_union_set_intersect(tree_filter, filter);
 728                 tree = isl_schedule_tree_filter_set_filter(tree, tree_filter);
 729                 return tree;
 730         }
 731
 732         res = isl_schedule_tree_from_filter(filter);
 733         return isl_schedule_tree_replace_child(res, 0, tree);
 734 }
 735
 736 /* Insert a filter node with filter set "filter"
 737  * in each of the children of "tree".
 738  */
 739 __isl_give isl_schedule_tree *isl_schedule_tree_children_insert_filter(
 740         __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
 741 {
 742         int i, n;
 743
 744         if (!tree || !filter)
 745                 goto error;
 746
 747         n = isl_schedule_tree_n_children(tree);
 748         for (i = 0; i < n; ++i) {
 749                 isl_schedule_tree *child;
 750
 751                 child = isl_schedule_tree_get_child(tree, i);
 752                 child = isl_schedule_tree_insert_filter(child,
 753                                                     isl_union_set_copy(filter));
 754                 tree = isl_schedule_tree_replace_child(tree, i, child);
 755         }
 756
 757         isl_union_set_free(filter);
 758         return tree;
 759 error:
 760         isl_union_set_free(filter);
 761         isl_schedule_tree_free(tree);
 762         return NULL;
 763 }
 764
 765 /* Return the number of members in the band tree root.
 766  */
 767 unsigned isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree *tree)
 768 {
 769         if (!tree)
 770                 return 0;
 771
 772         if (tree->type != isl_schedule_node_band)
 773                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
 774                         "not a band node", return 0);
 775
 776         return isl_schedule_band_n_member(tree->band);
 777 }
 778
 779 /* Is the band member at position "pos" of the band tree root
 780  * marked coincident?
 781  */
 782 int isl_schedule_tree_band_member_get_coincident(
 783         __isl_keep isl_schedule_tree *tree, int pos)
 784 {
 785         if (!tree)
 786                 return -1;
 787
 788         if (tree->type != isl_schedule_node_band)
 789                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
 790                         "not a band node", return -1);
 791
 792         return isl_schedule_band_member_get_coincident(tree->band, pos);
 793 }
 794
 795 /* Mark the given band member as being coincident or not
 796  * according to "coincident".
 797  */
 798 __isl_give isl_schedule_tree *isl_schedule_tree_band_member_set_coincident(
 799         __isl_take isl_schedule_tree *tree, int pos, int coincident)
 800 {
 801         if (!tree)
 802                 return NULL;
 803         if (tree->type != isl_schedule_node_band)
 804                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
 805                         "not a band node", return isl_schedule_tree_free(tree));
 806         if (isl_schedule_tree_band_member_get_coincident(tree, pos) ==
 807                                                                     coincident)
 808                 return tree;
 809         tree = isl_schedule_tree_cow(tree);
 810         if (!tree)
 811                 return NULL;
 812
 813         tree->band = isl_schedule_band_member_set_coincident(tree->band, pos,
 814                                                         coincident);
 815         if (!tree->band)
 816                 return isl_schedule_tree_free(tree);
 817         return tree;
 818 }
 819
 820 /* Is the band tree root marked permutable?
 821  */
 822 int isl_schedule_tree_band_get_permutable(__isl_keep isl_schedule_tree *tree)
 823 {
 824         if (!tree)
 825                 return -1;
 826
 827         if (tree->type != isl_schedule_node_band)
 828                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
 829                         "not a band node", return -1);
 830
 831         return isl_schedule_band_get_permutable(tree->band);
 832 }
 833
 834 /* Mark the band tree root permutable or not according to "permutable"?
 835  */
 836 __isl_give isl_schedule_tree *isl_schedule_tree_band_set_permutable(
 837         __isl_take isl_schedule_tree *tree, int permutable)
 838 {
 839         if (!tree)
 840                 return NULL;
 841         if (tree->type != isl_schedule_node_band)
 842                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
 843                         "not a band node", return isl_schedule_tree_free(tree));
 844         if (isl_schedule_tree_band_get_permutable(tree) == permutable)
 845                 return tree;
 846         tree = isl_schedule_tree_cow(tree);
 847         if (!tree)
 848                 return NULL;
 849
 850         tree->band = isl_schedule_band_set_permutable(tree->band, permutable);
 851         if (!tree->band)
 852                 return isl_schedule_tree_free(tree);
 853         return tree;
 854 }
 855
 856 /* Return the schedule space of the band tree root.
 857  */
 858 __isl_give isl_space *isl_schedule_tree_band_get_space(
 859         __isl_keep isl_schedule_tree *tree)
 860 {
 861         if (!tree)
 862                 return NULL;
 863
 864         if (tree->type != isl_schedule_node_band)
 865                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
 866                         "not a band node", return NULL);
 867
 868         return isl_schedule_band_get_space(tree->band);
 869 }
 870
 871 /* Return the schedule of the band tree root in isolation.
 872  */
 873 __isl_give isl_multi_union_pw_aff *isl_schedule_tree_band_get_partial_schedule(
 874         __isl_keep isl_schedule_tree *tree)
 875 {
 876         if (!tree)
 877                 return NULL;
 878
 879         if (tree->type != isl_schedule_node_band)
 880                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
 881                         "not a band node", return NULL);
 882
 883         return isl_schedule_band_get_partial_schedule(tree->band);
 884 }
 885
 886 /* Return the loop AST generation type for the band member
 887  * of the band tree root at position "pos".
 888  */
 889 enum isl_ast_loop_type isl_schedule_tree_band_member_get_ast_loop_type(
 890         __isl_keep isl_schedule_tree *tree, int pos)
 891 {
 892         if (!tree)
 893                 return isl_ast_loop_error;
 894
 895         if (tree->type != isl_schedule_node_band)
 896                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
 897                         "not a band node", return isl_ast_loop_error);
 898
 899         return isl_schedule_band_member_get_ast_loop_type(tree->band, pos);
 900 }
 901
 902 /* Set the loop AST generation type for the band member of the band tree root
 903  * at position "pos" to "type".
 904  */
 905 __isl_give isl_schedule_tree *isl_schedule_tree_band_member_set_ast_loop_type(
 906         __isl_take isl_schedule_tree *tree, int pos,
 907         enum isl_ast_loop_type type)
 908 {
 909         tree = isl_schedule_tree_cow(tree);
 910         if (!tree)
 911                 return NULL;
 912
 913         if (tree->type != isl_schedule_node_band)
 914                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
 915                         "not a band node", return isl_schedule_tree_free(tree));
 916
 917         tree->band = isl_schedule_band_member_set_ast_loop_type(tree->band,
 918                                                                 pos, type);
 919         if (!tree->band)
 920                 return isl_schedule_tree_free(tree);
 921
 922         return tree;
 923 }
 924
 925 /* Return the loop AST generation type for the band member
 926  * of the band tree root at position "pos" for the isolated part.
 927  */
 928 enum isl_ast_loop_type isl_schedule_tree_band_member_get_isolate_ast_loop_type(
 929         __isl_keep isl_schedule_tree *tree, int pos)
 930 {
 931         if (!tree)
 932                 return isl_ast_loop_error;
 933
 934         if (tree->type != isl_schedule_node_band)
 935                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
 936                         "not a band node", return isl_ast_loop_error);
 937
 938         return isl_schedule_band_member_get_isolate_ast_loop_type(tree->band,
 939                                                                         pos);
 940 }
 941
 942 /* Set the loop AST generation type for the band member of the band tree root
 943  * at position "pos" for the isolated part to "type".
 944  */
 945 __isl_give isl_schedule_tree *
 946 isl_schedule_tree_band_member_set_isolate_ast_loop_type(
 947         __isl_take isl_schedule_tree *tree, int pos,
 948         enum isl_ast_loop_type type)
 949 {
 950         tree = isl_schedule_tree_cow(tree);
 951         if (!tree)
 952                 return NULL;
 953
 954         if (tree->type != isl_schedule_node_band)
 955                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
 956                         "not a band node", return isl_schedule_tree_free(tree));
 957
 958         tree->band = isl_schedule_band_member_set_isolate_ast_loop_type(
 959                                                         tree->band, pos, type);
 960         if (!tree->band)
 961                 return isl_schedule_tree_free(tree);
 962
 963         return tree;
 964 }
 965
 966 /* Return the AST build options associated to the band tree root.
 967  */
 968 __isl_give isl_union_set *isl_schedule_tree_band_get_ast_build_options(
 969         __isl_keep isl_schedule_tree *tree)
 970 {
 971         if (!tree)
 972                 return NULL;
 973
 974         if (tree->type != isl_schedule_node_band)
 975                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
 976                         "not a band node", return NULL);
 977
 978         return isl_schedule_band_get_ast_build_options(tree->band);
 979 }
 980
 981 /* Replace the AST build options associated to band tree root by "options".
 982  * Updated the anchored field if the anchoredness of the root node itself
 983  * changes.
 984  */
 985 __isl_give isl_schedule_tree *isl_schedule_tree_band_set_ast_build_options(
 986         __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *options)
 987 {
 988         int was_anchored;
 989
 990         tree = isl_schedule_tree_cow(tree);
 991         if (!tree || !options)
 992                 goto error;
 993
 994         if (tree->type != isl_schedule_node_band)
 995                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
 996                         "not a band node", goto error);
 997
 998         was_anchored = isl_schedule_tree_is_anchored(tree);
 999         tree->band = isl_schedule_band_set_ast_build_options(tree->band,
1000                                                                 options);
1001         if (!tree->band)
1002                 return isl_schedule_tree_free(tree);
1003         if (isl_schedule_tree_is_anchored(tree) != was_anchored)
1004                 tree = isl_schedule_tree_update_anchored(tree);
1005
1006         return tree;
1007 error:
1008         isl_schedule_tree_free(tree);
1009         isl_union_set_free(options);
1010         return NULL;
1011 }
1012
1013 /* Return the context of the context tree root.
1014  */
1015 __isl_give isl_set *isl_schedule_tree_context_get_context(
1016         __isl_keep isl_schedule_tree *tree)
1017 {
1018         if (!tree)
1019                 return NULL;
1020
1021         if (tree->type != isl_schedule_node_context)
1022                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1023                         "not a context node", return NULL);
1024
1025         return isl_set_copy(tree->context);
1026 }
1027
1028 /* Return the domain of the domain tree root.
1029  */
1030 __isl_give isl_union_set *isl_schedule_tree_domain_get_domain(
1031         __isl_keep isl_schedule_tree *tree)
1032 {
1033         if (!tree)
1034                 return NULL;
1035
1036         if (tree->type != isl_schedule_node_domain)
1037                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1038                         "not a domain node", return NULL);
1039
1040         return isl_union_set_copy(tree->domain);
1041 }
1042
1043 /* Replace the domain of domain tree root "tree" by "domain".
1044  */
1045 __isl_give isl_schedule_tree *isl_schedule_tree_domain_set_domain(
1046         __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
1047 {
1048         tree = isl_schedule_tree_cow(tree);
1049         if (!tree || !domain)
1050                 goto error;
1051
1052         if (tree->type != isl_schedule_node_domain)
1053                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1054                         "not a domain node", goto error);
1055
1056         isl_union_set_free(tree->domain);
1057         tree->domain = domain;
1058
1059         return tree;
1060 error:
1061         isl_schedule_tree_free(tree);
1062         isl_union_set_free(domain);
1063         return NULL;
1064 }
1065
1066 /* Return the filter of the filter tree root.
1067  */
1068 __isl_give isl_union_set *isl_schedule_tree_filter_get_filter(
1069         __isl_keep isl_schedule_tree *tree)
1070 {
1071         if (!tree)
1072                 return NULL;
1073
1074         if (tree->type != isl_schedule_node_filter)
1075                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1076                         "not a filter node", return NULL);
1077
1078         return isl_union_set_copy(tree->filter);
1079 }
1080
1081 /* Replace the filter of the filter tree root by "filter".
1082  */
1083 __isl_give isl_schedule_tree *isl_schedule_tree_filter_set_filter(
1084         __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
1085 {
1086         tree = isl_schedule_tree_cow(tree);
1087         if (!tree || !filter)
1088                 goto error;
1089
1090         if (tree->type != isl_schedule_node_filter)
1091                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1092                         "not a filter node", return NULL);
1093
1094         isl_union_set_free(tree->filter);
1095         tree->filter = filter;
1096
1097         return tree;
1098 error:
1099         isl_schedule_tree_free(tree);
1100         isl_union_set_free(filter);
1101         return NULL;
1102 }
1103
1104 /* Set dim to the range dimension of "map" and abort the search.
1105  */
1106 static int set_range_dim(__isl_take isl_map *map, void *user)
1107 {
1108         int *dim = user;
1109
1110         *dim = isl_map_dim(map, isl_dim_out);
1111         isl_map_free(map);
1112
1113         return -1;
1114 }
1115
1116 /* Return the dimension of the range of "umap".
1117  * "umap" is assumed not to be empty and
1118  * all maps inside "umap" are assumed to have the same range.
1119  *
1120  * We extract the range dimension from the first map in "umap".
1121  */
1122 static int range_dim(__isl_keep isl_union_map *umap)
1123 {
1124         int dim = -1;
1125
1126         if (!umap)
1127                 return -1;
1128         if (isl_union_map_n_map(umap) == 0)
1129                 isl_die(isl_union_map_get_ctx(umap), isl_error_internal,
1130                         "unexpected empty input", return -1);
1131
1132         isl_union_map_foreach_map(umap, &set_range_dim, &dim);
1133
1134         return dim;
1135 }
1136
1137 /* Append an "extra" number of zeros to the range of "umap" and
1138  * return the result.
1139  */
1140 static __isl_give isl_union_map *append_range(__isl_take isl_union_map *umap,
1141         int extra)
1142 {
1143         isl_union_set *dom;
1144         isl_space *space;
1145         isl_multi_val *mv;
1146         isl_union_pw_multi_aff *suffix;
1147         isl_union_map *universe;
1148         isl_union_map *suffix_umap;
1149
1150         universe = isl_union_map_universe(isl_union_map_copy(umap));
1151         dom = isl_union_map_domain(universe);
1152         space = isl_union_set_get_space(dom);
1153         space = isl_space_set_from_params(space);
1154         space = isl_space_add_dims(space, isl_dim_set, extra);
1155         mv = isl_multi_val_zero(space);
1156
1157         suffix = isl_union_pw_multi_aff_multi_val_on_domain(dom, mv);
1158         suffix_umap = isl_union_map_from_union_pw_multi_aff(suffix);
1159         umap = isl_union_map_flat_range_product(umap, suffix_umap);
1160
1161         return umap;
1162 }
1163
1164 /* Should we skip the root of "tree" while looking for the first
1165  * descendant with schedule information?
1166  * That is, is it impossible to derive any information about
1167  * the iteration domain from this node?
1168  *
1169  * We do not want to skip leaf or error nodes because there is
1170  * no point in looking any deeper from these nodes.
1171  */
1172 static int domain_less(__isl_keep isl_schedule_tree *tree)
1173 {
1174         enum isl_schedule_node_type type;
1175
1176         type = isl_schedule_tree_get_type(tree);
1177         switch (type) {
1178         case isl_schedule_node_band:
1179                 return isl_schedule_tree_band_n_member(tree) == 0;
1180         case isl_schedule_node_context:
1181                 return 1;
1182         case isl_schedule_node_leaf:
1183         case isl_schedule_node_error:
1184         case isl_schedule_node_domain:
1185         case isl_schedule_node_filter:
1186         case isl_schedule_node_set:
1187         case isl_schedule_node_sequence:
1188                 return 0;
1189         }
1190 }
1191
1192 /* Move down to the first descendant of "tree" that contains any schedule
1193  * information or return "leaf" if there is no such descendant.
1194  */
1195 __isl_give isl_schedule_tree *isl_schedule_tree_first_schedule_descendant(
1196         __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_tree *leaf)
1197 {
1198         while (domain_less(tree)) {
1199                 if (!isl_schedule_tree_has_children(tree)) {
1200                         isl_schedule_tree_free(tree);
1201                         return isl_schedule_tree_copy(leaf);
1202                 }
1203                 tree = isl_schedule_tree_child(tree, 0);
1204         }
1205
1206         return tree;
1207 }
1208
1209 static __isl_give isl_union_map *subtree_schedule_extend(
1210         __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer);
1211
1212 /* Extend the schedule map "outer" with the subtree schedule
1213  * of the (single) child of "tree", if any.
1214  *
1215  * If "tree" does not have any descendants (apart from those that
1216  * do not carry any schedule information), then we simply return "outer".
1217  * Otherwise, we extend the schedule map "outer" with the subtree schedule
1218  * of the single child.
1219  */
1220 static __isl_give isl_union_map *subtree_schedule_extend_child(
1221         __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1222 {
1223         isl_schedule_tree *child;
1224         isl_union_map *res;
1225
1226         if (!tree)
1227                 return isl_union_map_free(outer);
1228         if (!isl_schedule_tree_has_children(tree))
1229                 return outer;
1230         child = isl_schedule_tree_get_child(tree, 0);
1231         if (!child)
1232                 return isl_union_map_free(outer);
1233         res = subtree_schedule_extend(child, outer);
1234         isl_schedule_tree_free(child);
1235         return res;
1236 }
1237
1238 /* Extract the parameter space from one of the children of "tree",
1239  * which are assumed to be filters.
1240  */
1241 static __isl_give isl_space *extract_space_from_filter_child(
1242         __isl_keep isl_schedule_tree *tree)
1243 {
1244         isl_space *space;
1245         isl_union_set *dom;
1246         isl_schedule_tree *child;
1247
1248         child = isl_schedule_tree_list_get_schedule_tree(tree->children, 0);
1249         dom = isl_schedule_tree_filter_get_filter(child);
1250         space = isl_union_set_get_space(dom);
1251         isl_union_set_free(dom);
1252         isl_schedule_tree_free(child);
1253
1254         return space;
1255 }
1256
1257 /* Extend the schedule map "outer" with the subtree schedule
1258  * of a set or sequence node.
1259  *
1260  * The schedule for the set or sequence node itself is composed of
1261  * pieces of the form
1262  *
1263  *      filter -> []
1264  *
1265  * or
1266  *
1267  *      filter -> [index]
1268  *
1269  * The first form is used if there is only a single child or
1270  * if the current node is a set node and the schedule_separate_components
1271  * option is not set.
1272  *
1273  * Each of the pieces above is extended with the subtree schedule of
1274  * the child of the corresponding filter, if any, padded with zeros
1275  * to ensure that all pieces have the same range dimension.
1276  */
1277 static __isl_give isl_union_map *subtree_schedule_extend_from_children(
1278         __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1279 {
1280         int i, n;
1281         int dim;
1282         int separate;
1283         isl_ctx *ctx;
1284         isl_val *v = NULL;
1285         isl_multi_val *mv;
1286         isl_space *space;
1287         isl_union_map *umap;
1288
1289         if (!tree)
1290                 return NULL;
1291
1292         ctx = isl_schedule_tree_get_ctx(tree);
1293         if (!tree->children)
1294                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1295                         "missing children", return NULL);
1296         n = isl_schedule_tree_list_n_schedule_tree(tree->children);
1297         if (n == 0)
1298                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1299                         "missing children", return NULL);
1300
1301         separate = n > 1 && (tree->type == isl_schedule_node_sequence ||
1302                             isl_options_get_schedule_separate_components(ctx));
1303
1304         space = extract_space_from_filter_child(tree);
1305
1306         umap = isl_union_map_empty(isl_space_copy(space));
1307         space = isl_space_set_from_params(space);
1308         if (separate) {
1309                 space = isl_space_add_dims(space, isl_dim_set, 1);
1310                 v = isl_val_zero(ctx);
1311         }
1312         mv = isl_multi_val_zero(space);
1313
1314         dim = isl_multi_val_dim(mv, isl_dim_set);
1315         for (i = 0; i < n; ++i) {
1316                 isl_union_pw_multi_aff *upma;
1317                 isl_union_map *umap_i;
1318                 isl_union_set *dom;
1319                 isl_schedule_tree *child;
1320                 int dim_i;
1321                 int empty;
1322
1323                 child = isl_schedule_tree_list_get_schedule_tree(
1324                                                         tree->children, i);
1325                 dom = isl_schedule_tree_filter_get_filter(child);
1326
1327                 if (separate) {
1328                         mv = isl_multi_val_set_val(mv, 0, isl_val_copy(v));
1329                         v = isl_val_add_ui(v, 1);
1330                 }
1331                 upma = isl_union_pw_multi_aff_multi_val_on_domain(dom,
1332                                                         isl_multi_val_copy(mv));
1333                 umap_i = isl_union_map_from_union_pw_multi_aff(upma);
1334                 umap_i = isl_union_map_flat_range_product(
1335                                             isl_union_map_copy(outer), umap_i);
1336                 umap_i = subtree_schedule_extend_child(child, umap_i);
1337                 isl_schedule_tree_free(child);
1338
1339                 empty = isl_union_map_is_empty(umap_i);
1340                 if (empty < 0)
1341                         umap_i = isl_union_map_free(umap_i);
1342                 else if (empty) {
1343                         isl_union_map_free(umap_i);
1344                         continue;
1345                 }
1346
1347                 dim_i = range_dim(umap_i);
1348                 if (dim_i < 0) {
1349                         umap = isl_union_map_free(umap);
1350                 } else if (dim < dim_i) {
1351                         umap = append_range(umap, dim_i - dim);
1352                         dim = dim_i;
1353                 } else if (dim_i < dim) {
1354                         umap_i = append_range(umap_i, dim - dim_i);
1355                 }
1356                 umap = isl_union_map_union(umap, umap_i);
1357         }
1358
1359         isl_val_free(v);
1360         isl_multi_val_free(mv);
1361         isl_union_map_free(outer);
1362
1363         return umap;
1364 }
1365
1366 /* Extend the schedule map "outer" with the subtree schedule of "tree".
1367  *
1368  * If the root of the tree is a set or a sequence, then we extend
1369  * the schedule map in subtree_schedule_extend_from_children.
1370  * Otherwise, we extend the schedule map with the partial schedule
1371  * corresponding to the root of the tree and then continue with
1372  * the single child of this root.
1373  */
1374 static __isl_give isl_union_map *subtree_schedule_extend(
1375         __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1376 {
1377         isl_multi_union_pw_aff *mupa;
1378         isl_union_map *umap;
1379         isl_union_set *domain;
1380
1381         if (!tree)
1382                 return NULL;
1383
1384         switch (tree->type) {
1385         case isl_schedule_node_error:
1386                 return isl_union_map_free(outer);
1387         case isl_schedule_node_context:
1388                 return subtree_schedule_extend_child(tree, outer);
1389         case isl_schedule_node_band:
1390                 if (isl_schedule_tree_band_n_member(tree) == 0)
1391                         return subtree_schedule_extend_child(tree, outer);
1392                 mupa = isl_schedule_band_get_partial_schedule(tree->band);
1393                 umap = isl_union_map_from_multi_union_pw_aff(mupa);
1394                 outer = isl_union_map_flat_range_product(outer, umap);
1395                 umap = subtree_schedule_extend_child(tree, outer);
1396                 break;
1397         case isl_schedule_node_domain:
1398                 domain = isl_schedule_tree_domain_get_domain(tree);
1399                 umap = isl_union_map_from_domain(domain);
1400                 outer = isl_union_map_flat_range_product(outer, umap);
1401                 umap = subtree_schedule_extend_child(tree, outer);
1402                 break;
1403         case isl_schedule_node_filter:
1404                 domain = isl_schedule_tree_filter_get_filter(tree);
1405                 umap = isl_union_map_from_domain(domain);
1406                 outer = isl_union_map_flat_range_product(outer, umap);
1407                 umap = subtree_schedule_extend_child(tree, outer);
1408                 break;
1409         case isl_schedule_node_leaf:
1410                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1411                         "leaf node should be handled by caller", return NULL);
1412         case isl_schedule_node_set:
1413         case isl_schedule_node_sequence:
1414                 umap = subtree_schedule_extend_from_children(tree, outer);
1415                 break;
1416         }
1417
1418         return umap;
1419 }
1420
1421 static __isl_give isl_union_set *initial_domain(
1422         __isl_keep isl_schedule_tree *tree);
1423
1424 /* Extract a universe domain from the children of the tree root "tree",
1425  * which is a set or sequence, meaning that its children are filters.
1426  * In particular, return the union of the universes of the filters.
1427  */
1428 static __isl_give isl_union_set *initial_domain_from_children(
1429         __isl_keep isl_schedule_tree *tree)
1430 {
1431         int i, n;
1432         isl_space *space;
1433         isl_union_set *domain;
1434
1435         if (!tree->children)
1436                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1437                         "missing children", return NULL);
1438         n = isl_schedule_tree_list_n_schedule_tree(tree->children);
1439         if (n == 0)
1440                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1441                         "missing children", return NULL);
1442
1443         space = extract_space_from_filter_child(tree);
1444         domain = isl_union_set_empty(space);
1445
1446         for (i = 0; i < n; ++i) {
1447                 isl_schedule_tree *child;
1448                 isl_union_set *domain_i;
1449
1450                 child = isl_schedule_tree_get_child(tree, i);
1451                 domain_i = initial_domain(child);
1452                 domain = isl_union_set_union(domain, domain_i);
1453                 isl_schedule_tree_free(child);
1454         }
1455
1456         return domain;
1457 }
1458
1459 /* Extract a universe domain from the tree root "tree".
1460  * The caller is responsible for making sure that this node
1461  * would not be skipped by isl_schedule_tree_first_schedule_descendant
1462  * and that it is not a leaf node.
1463  */
1464 static __isl_give isl_union_set *initial_domain(
1465         __isl_keep isl_schedule_tree *tree)
1466 {
1467         isl_multi_union_pw_aff *mupa;
1468         isl_union_set *domain;
1469
1470         if (!tree)
1471                 return NULL;
1472
1473         switch (tree->type) {
1474         case isl_schedule_node_error:
1475                 return NULL;
1476         case isl_schedule_node_context:
1477                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1478                         "context node should be handled by caller",
1479                         return NULL);
1480         case isl_schedule_node_band:
1481                 if (isl_schedule_tree_band_n_member(tree) == 0)
1482                         isl_die(isl_schedule_tree_get_ctx(tree),
1483                                 isl_error_internal,
1484                                 "0D band should be handled by caller",
1485                                 return NULL);
1486                 mupa = isl_schedule_band_get_partial_schedule(tree->band);
1487                 domain = isl_multi_union_pw_aff_domain(mupa);
1488                 domain = isl_union_set_universe(domain);
1489                 break;
1490         case isl_schedule_node_domain:
1491                 domain = isl_schedule_tree_domain_get_domain(tree);
1492                 domain = isl_union_set_universe(domain);
1493                 break;
1494         case isl_schedule_node_filter:
1495                 domain = isl_schedule_tree_filter_get_filter(tree);
1496                 domain = isl_union_set_universe(domain);
1497                 break;
1498         case isl_schedule_node_leaf:
1499                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1500                         "leaf node should be handled by caller", return NULL);
1501         case isl_schedule_node_set:
1502         case isl_schedule_node_sequence:
1503                 domain = initial_domain_from_children(tree);
1504                 break;
1505         }
1506
1507         return domain;
1508 }
1509
1510 /* Return the subtree schedule of a node that contains some schedule
1511  * information, i.e., a node that would not be skipped by
1512  * isl_schedule_tree_first_schedule_descendant and that is not a leaf.
1513  *
1514  * We start with an initial zero-dimensional subtree schedule based
1515  * on the domain information in the root node and then extend it
1516  * based on the schedule information in the root node and its descendants.
1517  */
1518 __isl_give isl_union_map *isl_schedule_tree_get_subtree_schedule_union_map(
1519         __isl_keep isl_schedule_tree *tree)
1520 {
1521         isl_union_set *domain;
1522         isl_union_map *umap;
1523
1524         domain = initial_domain(tree);
1525         umap = isl_union_map_from_domain(domain);
1526         return subtree_schedule_extend(tree, umap);
1527 }
1528
1529 /* Multiply the partial schedule of the band root node of "tree"
1530  * with the factors in "mv".
1531  */
1532 __isl_give isl_schedule_tree *isl_schedule_tree_band_scale(
1533         __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
1534 {
1535         if (!tree || !mv)
1536                 goto error;
1537         if (tree->type != isl_schedule_node_band)
1538                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1539                         "not a band node", goto error);
1540
1541         tree = isl_schedule_tree_cow(tree);
1542         if (!tree)
1543                 goto error;
1544
1545         tree->band = isl_schedule_band_scale(tree->band, mv);
1546         if (!tree->band)
1547                 return isl_schedule_tree_free(tree);
1548
1549         return tree;
1550 error:
1551         isl_schedule_tree_free(tree);
1552         isl_multi_val_free(mv);
1553         return NULL;
1554 }
1555
1556 /* Divide the partial schedule of the band root node of "tree"
1557  * by the factors in "mv".
1558  */
1559 __isl_give isl_schedule_tree *isl_schedule_tree_band_scale_down(
1560         __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
1561 {
1562         if (!tree || !mv)
1563                 goto error;
1564         if (tree->type != isl_schedule_node_band)
1565                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1566                         "not a band node", goto error);
1567
1568         tree = isl_schedule_tree_cow(tree);
1569         if (!tree)
1570                 goto error;
1571
1572         tree->band = isl_schedule_band_scale_down(tree->band, mv);
1573         if (!tree->band)
1574                 return isl_schedule_tree_free(tree);
1575
1576         return tree;
1577 error:
1578         isl_schedule_tree_free(tree);
1579         isl_multi_val_free(mv);
1580         return NULL;
1581 }
1582
1583 /* Tile the band root node of "tree" with tile sizes "sizes".
1584  *
1585  * We duplicate the band node, change the schedule of one of them
1586  * to the tile schedule and the other to the point schedule and then
1587  * attach the point band as a child to the tile band.
1588  */
1589 __isl_give isl_schedule_tree *isl_schedule_tree_band_tile(
1590         __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *sizes)
1591 {
1592         isl_schedule_tree *child = NULL;
1593
1594         if (!tree || !sizes)
1595                 goto error;
1596         if (tree->type != isl_schedule_node_band)
1597                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1598                         "not a band node", goto error);
1599
1600         child = isl_schedule_tree_copy(tree);
1601         tree = isl_schedule_tree_cow(tree);
1602         child = isl_schedule_tree_cow(child);
1603         if (!tree || !child)
1604                 goto error;
1605
1606         tree->band = isl_schedule_band_tile(tree->band,
1607                                             isl_multi_val_copy(sizes));
1608         if (!tree->band)
1609                 goto error;
1610         child->band = isl_schedule_band_point(child->band, tree->band, sizes);
1611         if (!child->band)
1612                 child = isl_schedule_tree_free(child);
1613
1614         tree = isl_schedule_tree_replace_child(tree, 0, child);
1615
1616         return tree;
1617 error:
1618         isl_schedule_tree_free(child);
1619         isl_schedule_tree_free(tree);
1620         isl_multi_val_free(sizes);
1621         return NULL;
1622 }
1623
1624 /* Split the band root node of "tree" into two nested band nodes,
1625  * one with the first "pos" dimensions and
1626  * one with the remaining dimensions.
1627  */
1628 __isl_give isl_schedule_tree *isl_schedule_tree_band_split(
1629         __isl_take isl_schedule_tree *tree, int pos)
1630 {
1631         int n;
1632         isl_schedule_tree *child;
1633
1634         if (!tree)
1635                 return NULL;
1636         if (tree->type != isl_schedule_node_band)
1637                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1638                         "not a band node", return isl_schedule_tree_free(tree));
1639
1640         n = isl_schedule_tree_band_n_member(tree);
1641         if (pos < 0 || pos > n)
1642                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1643                         "position out of bounds",
1644                         return isl_schedule_tree_free(tree));
1645
1646         child = isl_schedule_tree_copy(tree);
1647         tree = isl_schedule_tree_cow(tree);
1648         child = isl_schedule_tree_cow(child);
1649         if (!tree || !child)
1650                 goto error;
1651
1652         child->band = isl_schedule_band_drop(child->band, 0, pos);
1653         tree->band = isl_schedule_band_drop(tree->band, pos, n - pos);
1654         if (!child->band || !tree->band)
1655                 goto error;
1656
1657         tree = isl_schedule_tree_replace_child(tree, 0, child);
1658
1659         return tree;
1660 error:
1661         isl_schedule_tree_free(child);
1662         isl_schedule_tree_free(tree);
1663         return NULL;
1664 }
1665
1666 /* Attach "tree2" at each of the leaves of "tree1".
1667  *
1668  * If "tree1" does not have any explicit children, then make "tree2"
1669  * its single child.  Otherwise, attach "tree2" to the leaves of
1670  * each of the children of "tree1".
1671  */
1672 __isl_give isl_schedule_tree *isl_schedule_tree_append_to_leaves(
1673         __isl_take isl_schedule_tree *tree1,
1674         __isl_take isl_schedule_tree *tree2)
1675 {
1676         int i, n;
1677
1678         if (!tree1 || !tree2)
1679                 goto error;
1680         n = isl_schedule_tree_n_children(tree1);
1681         if (n == 0) {
1682                 isl_schedule_tree_list *list;
1683                 list = isl_schedule_tree_list_from_schedule_tree(tree2);
1684                 tree1 = isl_schedule_tree_set_children(tree1, list);
1685                 return tree1;
1686         }
1687         for (i = 0; i < n; ++i) {
1688                 isl_schedule_tree *child;
1689
1690                 child = isl_schedule_tree_get_child(tree1, i);
1691                 child = isl_schedule_tree_append_to_leaves(child,
1692                                         isl_schedule_tree_copy(tree2));
1693                 tree1 = isl_schedule_tree_replace_child(tree1, i, child);
1694         }
1695
1696         isl_schedule_tree_free(tree2);
1697         return tree1;
1698 error:
1699         isl_schedule_tree_free(tree1);
1700         isl_schedule_tree_free(tree2);
1701         return NULL;
1702 }
1703
1704 /* Reset the user pointer on all identifiers of parameters and tuples
1705  * in the root of "tree".
1706  */
1707 __isl_give isl_schedule_tree *isl_schedule_tree_reset_user(
1708         __isl_take isl_schedule_tree *tree)
1709 {
1710         if (isl_schedule_tree_is_leaf(tree))
1711                 return tree;
1712
1713         tree = isl_schedule_tree_cow(tree);
1714         if (!tree)
1715                 return NULL;
1716
1717         switch (tree->type) {
1718         case isl_schedule_node_error:
1719                 return isl_schedule_tree_free(tree);
1720         case isl_schedule_node_band:
1721                 tree->band = isl_schedule_band_reset_user(tree->band);
1722                 if (!tree->band)
1723                         return isl_schedule_tree_free(tree);
1724                 break;
1725         case isl_schedule_node_context:
1726                 tree->context = isl_set_reset_user(tree->context);
1727                 if (!tree->context)
1728                         return isl_schedule_tree_free(tree);
1729                 break;
1730         case isl_schedule_node_domain:
1731                 tree->domain = isl_union_set_reset_user(tree->domain);
1732                 if (!tree->domain)
1733                         return isl_schedule_tree_free(tree);
1734                 break;
1735         case isl_schedule_node_filter:
1736                 tree->filter = isl_union_set_reset_user(tree->filter);
1737                 if (!tree->filter)
1738                         return isl_schedule_tree_free(tree);
1739                 break;
1740         case isl_schedule_node_leaf:
1741         case isl_schedule_node_sequence:
1742         case isl_schedule_node_set:
1743                 break;
1744         }
1745
1746         return tree;
1747 }
1748
1749 /* Align the parameters of the root of "tree" to those of "space".
1750  */
1751 __isl_give isl_schedule_tree *isl_schedule_tree_align_params(
1752         __isl_take isl_schedule_tree *tree, __isl_take isl_space *space)
1753 {
1754         if (!space)
1755                 goto error;
1756
1757         if (isl_schedule_tree_is_leaf(tree)) {
1758                 isl_space_free(space);
1759                 return tree;
1760         }
1761
1762         tree = isl_schedule_tree_cow(tree);
1763         if (!tree)
1764                 goto error;
1765
1766         switch (tree->type) {
1767         case isl_schedule_node_error:
1768                 goto error;
1769         case isl_schedule_node_band:
1770                 tree->band = isl_schedule_band_align_params(tree->band, space);
1771                 if (!tree->band)
1772                         return isl_schedule_tree_free(tree);
1773                 break;
1774         case isl_schedule_node_context:
1775                 tree->context = isl_set_align_params(tree->context, space);
1776                 if (!tree->context)
1777                         return isl_schedule_tree_free(tree);
1778                 break;
1779         case isl_schedule_node_domain:
1780                 tree->domain = isl_union_set_align_params(tree->domain, space);
1781                 if (!tree->domain)
1782                         return isl_schedule_tree_free(tree);
1783                 break;
1784         case isl_schedule_node_filter:
1785                 tree->filter = isl_union_set_align_params(tree->filter, space);
1786                 if (!tree->filter)
1787                         return isl_schedule_tree_free(tree);
1788                 break;
1789         case isl_schedule_node_leaf:
1790         case isl_schedule_node_sequence:
1791         case isl_schedule_node_set:
1792                 isl_space_free(space);
1793                 break;
1794         }
1795
1796         return tree;
1797 error:
1798         isl_space_free(space);
1799         isl_schedule_tree_free(tree);
1800         return NULL;
1801 }
1802
1803 /* Does "tree" involve the iteration domain?
1804  * That is, does it need to be modified
1805  * by isl_schedule_tree_pullback_union_pw_multi_aff?
1806  */
1807 static int involves_iteration_domain(__isl_keep isl_schedule_tree *tree)
1808 {
1809         if (!tree)
1810                 return -1;
1811
1812         switch (tree->type) {
1813         case isl_schedule_node_error:
1814                 return -1;
1815         case isl_schedule_node_band:
1816         case isl_schedule_node_domain:
1817         case isl_schedule_node_filter:
1818                 return 1;
1819         case isl_schedule_node_context:
1820         case isl_schedule_node_leaf:
1821         case isl_schedule_node_sequence:
1822         case isl_schedule_node_set:
1823                 return 0;
1824         }
1825 }
1826
1827 /* Compute the pullback of the root node of "tree" by the function
1828  * represented by "upma".
1829  * In other words, plug in "upma" in the iteration domains of
1830  * the root node of "tree".
1831  *
1832  * We first check if the root node involves any iteration domains.
1833  * If so, we handle the specific cases.
1834  */
1835 __isl_give isl_schedule_tree *isl_schedule_tree_pullback_union_pw_multi_aff(
1836         __isl_take isl_schedule_tree *tree,
1837         __isl_take isl_union_pw_multi_aff *upma)
1838 {
1839         int involves;
1840
1841         if (!tree || !upma)
1842                 goto error;
1843
1844         involves = involves_iteration_domain(tree);
1845         if (involves < 0)
1846                 goto error;
1847         if (!involves) {
1848                 isl_union_pw_multi_aff_free(upma);
1849                 return tree;
1850         }
1851
1852         tree = isl_schedule_tree_cow(tree);
1853         if (!tree)
1854                 goto error;
1855
1856         if (tree->type == isl_schedule_node_band) {
1857                 tree->band = isl_schedule_band_pullback_union_pw_multi_aff(
1858                                                             tree->band, upma);
1859                 if (!tree->band)
1860                         return isl_schedule_tree_free(tree);
1861         } else if (tree->type == isl_schedule_node_domain) {
1862                 tree->domain =
1863                         isl_union_set_preimage_union_pw_multi_aff(tree->domain,
1864                                                                         upma);
1865                 if (!tree->domain)
1866                         return isl_schedule_tree_free(tree);
1867         } else if (tree->type == isl_schedule_node_filter) {
1868                 tree->filter =
1869                         isl_union_set_preimage_union_pw_multi_aff(tree->filter,
1870                                                                         upma);
1871                 if (!tree->filter)
1872                         return isl_schedule_tree_free(tree);
1873         }
1874
1875         return tree;
1876 error:
1877         isl_union_pw_multi_aff_free(upma);
1878         isl_schedule_tree_free(tree);
1879         return NULL;
1880 }
1881
1882 /* Compute the gist of the band tree root with respect to "context".
1883  */
1884 __isl_give isl_schedule_tree *isl_schedule_tree_band_gist(
1885         __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *context)
1886 {
1887         if (!tree)
1888                 return NULL;
1889         if (tree->type != isl_schedule_node_band)
1890                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1891                         "not a band node", goto error);
1892         tree = isl_schedule_tree_cow(tree);
1893         if (!tree)
1894                 goto error;
1895
1896         tree->band = isl_schedule_band_gist(tree->band, context);
1897         if (!tree->band)
1898                 return isl_schedule_tree_free(tree);
1899         return tree;
1900 error:
1901         isl_union_set_free(context);
1902         isl_schedule_tree_free(tree);
1903         return NULL;
1904 }
1905
1906 /* Are any members in "band" marked coincident?
1907  */
1908 static int any_coincident(__isl_keep isl_schedule_band *band)
1909 {
1910         int i, n;
1911
1912         n = isl_schedule_band_n_member(band);
1913         for (i = 0; i < n; ++i)
1914                 if (isl_schedule_band_member_get_coincident(band, i))
1915                         return 1;
1916
1917         return 0;
1918 }
1919
1920 /* Print the band node "band" to "p".
1921  *
1922  * The permutable and coincident properties are only printed if they
1923  * are different from the defaults.
1924  * The coincident property is always printed in YAML flow style.
1925  */
1926 static __isl_give isl_printer *print_tree_band(__isl_take isl_printer *p,
1927         __isl_keep isl_schedule_band *band)
1928 {
1929         isl_union_set *options;
1930         int empty;
1931
1932         p = isl_printer_print_str(p, "schedule");
1933         p = isl_printer_yaml_next(p);
1934         p = isl_printer_print_str(p, "\"");
1935         p = isl_printer_print_multi_union_pw_aff(p, band->mupa);
1936         p = isl_printer_print_str(p, "\"");
1937         if (isl_schedule_band_get_permutable(band)) {
1938                 p = isl_printer_yaml_next(p);
1939                 p = isl_printer_print_str(p, "permutable");
1940                 p = isl_printer_yaml_next(p);
1941                 p = isl_printer_print_int(p, 1);
1942         }
1943         if (any_coincident(band)) {
1944                 int i, n;
1945                 int style;
1946
1947                 p = isl_printer_yaml_next(p);
1948                 p = isl_printer_print_str(p, "coincident");
1949                 p = isl_printer_yaml_next(p);
1950                 style = isl_printer_get_yaml_style(p);
1951                 p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_FLOW);
1952                 p = isl_printer_yaml_start_sequence(p);
1953                 n = isl_schedule_band_n_member(band);
1954                 for (i = 0; i < n; ++i) {
1955                         p = isl_printer_print_int(p,
1956                             isl_schedule_band_member_get_coincident(band, i));
1957                         p = isl_printer_yaml_next(p);
1958                 }
1959                 p = isl_printer_yaml_end_sequence(p);
1960                 p = isl_printer_set_yaml_style(p, style);
1961         }
1962         options = isl_schedule_band_get_ast_build_options(band);
1963         empty = isl_union_set_is_empty(options);
1964         if (empty < 0)
1965                 p = isl_printer_free(p);
1966         if (!empty) {
1967                 p = isl_printer_yaml_next(p);
1968                 p = isl_printer_print_str(p, "options");
1969                 p = isl_printer_yaml_next(p);
1970                 p = isl_printer_print_str(p, "\"");
1971                 p = isl_printer_print_union_set(p, options);
1972                 p = isl_printer_print_str(p, "\"");
1973         }
1974         isl_union_set_free(options);
1975
1976         return p;
1977 }
1978
1979 /* Print "tree" to "p".
1980  *
1981  * If "n_ancestor" is non-negative, then "child_pos" contains the child
1982  * positions of a descendant of the current node that should be marked
1983  * (by the comment "YOU ARE HERE").  In particular, if "n_ancestor"
1984  * is zero, then the current node should be marked.
1985  * The marking is only printed in YAML block format.
1986  *
1987  * Implicit leaf nodes are not printed, except if they correspond
1988  * to the node that should be marked.
1989  */
1990 __isl_give isl_printer *isl_printer_print_schedule_tree_mark(
1991         __isl_take isl_printer *p, __isl_keep isl_schedule_tree *tree,
1992         int n_ancestor, int *child_pos)
1993 {
1994         int i, n;
1995         int sequence = 0;
1996         int block;
1997
1998         block = isl_printer_get_yaml_style(p) == ISL_YAML_STYLE_BLOCK;
1999
2000         p = isl_printer_yaml_start_mapping(p);
2001         if (n_ancestor == 0 && block) {
2002                 p = isl_printer_print_str(p, "# YOU ARE HERE");
2003                 p = isl_printer_end_line(p);
2004                 p = isl_printer_start_line(p);
2005         }
2006         switch (tree->type) {
2007         case isl_schedule_node_error:
2008                 p = isl_printer_print_str(p, "ERROR");
2009                 break;
2010         case isl_schedule_node_leaf:
2011                 p = isl_printer_print_str(p, "leaf");
2012                 break;
2013         case isl_schedule_node_sequence:
2014                 p = isl_printer_print_str(p, "sequence");
2015                 sequence = 1;
2016                 break;
2017         case isl_schedule_node_set:
2018                 p = isl_printer_print_str(p, "set");
2019                 sequence = 1;
2020                 break;
2021         case isl_schedule_node_context:
2022                 p = isl_printer_print_str(p, "context");
2023                 p = isl_printer_yaml_next(p);
2024                 p = isl_printer_print_str(p, "\"");
2025                 p = isl_printer_print_set(p, tree->context);
2026                 p = isl_printer_print_str(p, "\"");
2027                 break;
2028         case isl_schedule_node_domain:
2029                 p = isl_printer_print_str(p, "domain");
2030                 p = isl_printer_yaml_next(p);
2031                 p = isl_printer_print_str(p, "\"");
2032                 p = isl_printer_print_union_set(p, tree->domain);
2033                 p = isl_printer_print_str(p, "\"");
2034                 break;
2035         case isl_schedule_node_filter:
2036                 p = isl_printer_print_str(p, "filter");
2037                 p = isl_printer_yaml_next(p);
2038                 p = isl_printer_print_str(p, "\"");
2039                 p = isl_printer_print_union_set(p, tree->filter);
2040                 p = isl_printer_print_str(p, "\"");
2041                 break;
2042         case isl_schedule_node_band:
2043                 p = print_tree_band(p, tree->band);
2044                 break;
2045         }
2046         p = isl_printer_yaml_next(p);
2047
2048         if (!tree->children) {
2049                 if (n_ancestor > 0 && block) {
2050                         isl_schedule_tree *leaf;
2051
2052                         p = isl_printer_print_str(p, "child");
2053                         p = isl_printer_yaml_next(p);
2054                         leaf = isl_schedule_tree_leaf(isl_printer_get_ctx(p));
2055                         p = isl_printer_print_schedule_tree_mark(p,
2056                                         leaf, 0, NULL);
2057                         isl_schedule_tree_free(leaf);
2058                         p = isl_printer_yaml_next(p);
2059                 }
2060                 return isl_printer_yaml_end_mapping(p);
2061         }
2062
2063         if (sequence) {
2064                 p = isl_printer_yaml_start_sequence(p);
2065         } else {
2066                 p = isl_printer_print_str(p, "child");
2067                 p = isl_printer_yaml_next(p);
2068         }
2069
2070         n = isl_schedule_tree_list_n_schedule_tree(tree->children);
2071         for (i = 0; i < n; ++i) {
2072                 isl_schedule_tree *t;
2073
2074                 t = isl_schedule_tree_get_child(tree, i);
2075                 if (n_ancestor > 0 && child_pos[0] == i)
2076                         p = isl_printer_print_schedule_tree_mark(p, t,
2077                                                 n_ancestor - 1, child_pos + 1);
2078                 else
2079                         p = isl_printer_print_schedule_tree_mark(p, t,
2080                                                 -1, NULL);
2081                 isl_schedule_tree_free(t);
2082
2083                 p = isl_printer_yaml_next(p);
2084         }
2085
2086         if (sequence)
2087                 p = isl_printer_yaml_end_sequence(p);
2088         p = isl_printer_yaml_end_mapping(p);
2089
2090         return p;
2091 }
2092
2093 /* Print "tree" to "p".
2094  */
2095 __isl_give isl_printer *isl_printer_print_schedule_tree(
2096         __isl_take isl_printer *p, __isl_keep isl_schedule_tree *tree)
2097 {
2098         return isl_printer_print_schedule_tree_mark(p, tree, -1, NULL);
2099 }
2100
2101 void isl_schedule_tree_dump(__isl_keep isl_schedule_tree *tree)
2102 {
2103         isl_ctx *ctx;
2104         isl_printer *printer;
2105
2106         if (!tree)
2107                 return;
2108
2109         ctx = isl_schedule_tree_get_ctx(tree);
2110         printer = isl_printer_to_file(ctx, stderr);
2111         printer = isl_printer_set_yaml_style(printer, ISL_YAML_STYLE_BLOCK);
2112         printer = isl_printer_print_schedule_tree(printer, tree);
2113
2114         isl_printer_free(printer);
2115 }