isl_schedule_tree.c

   1 /*
   2  * Copyright 2013-2014 Ecole Normale Superieure
   3  * Copyright 2014      INRIA Rocquencourt
   4  * Copyright 2016      INRIA Paris
   5  *
   6  * Use of this software is governed by the MIT license
   7  *
   8  * Written by Sven Verdoolaege,
   9  * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
  10  * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
  11  * B.P. 105 - 78153 Le Chesnay, France
  12  * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12,
  13  * CS 42112, 75589 Paris Cedex 12, France
  14  */
  15
  16 #include <isl/map.h>
  17 #include <isl_schedule_band.h>
  18 #include <isl_schedule_private.h>
  19
  20 #undef EL
  21 #define EL isl_schedule_tree
  22
  23 #include <isl_list_templ.h>
  24
  25 #undef BASE
  26 #define BASE schedule_tree
  27
  28 #include <isl_list_templ.c>
  29
  30 /* Is "tree" the leaf of a schedule tree?
  31  */
  32 int isl_schedule_tree_is_leaf(__isl_keep isl_schedule_tree *tree)
  33 {
  34         return isl_schedule_tree_get_type(tree) == isl_schedule_node_leaf;
  35 }
  36
  37 /* Create a new schedule tree of type "type".
  38  * The caller is responsible for filling in the type specific fields and
  39  * the children.
  40  *
  41  * By default, the single node tree does not have any anchored nodes.
  42  * The caller is responsible for updating the anchored field if needed.
  43  */
  44 static __isl_give isl_schedule_tree *isl_schedule_tree_alloc(isl_ctx *ctx,
  45         enum isl_schedule_node_type type)
  46 {
  47         isl_schedule_tree *tree;
  48
  49         if (type == isl_schedule_node_error)
  50                 return NULL;
  51
  52         tree = isl_calloc_type(ctx, isl_schedule_tree);
  53         if (!tree)
  54                 return NULL;
  55
  56         tree->ref = 1;
  57         tree->ctx = ctx;
  58         isl_ctx_ref(ctx);
  59         tree->type = type;
  60         tree->anchored = 0;
  61
  62         return tree;
  63 }
  64
  65 /* Return a fresh copy of "tree".
  66  */
  67 __isl_take isl_schedule_tree *isl_schedule_tree_dup(
  68         __isl_keep isl_schedule_tree *tree)
  69 {
  70         isl_ctx *ctx;
  71         isl_schedule_tree *dup;
  72
  73         if (!tree)
  74                 return NULL;
  75
  76         ctx = isl_schedule_tree_get_ctx(tree);
  77         dup = isl_schedule_tree_alloc(ctx, tree->type);
  78         if (!dup)
  79                 return NULL;
  80
  81         switch (tree->type) {
  82         case isl_schedule_node_error:
  83                 isl_die(ctx, isl_error_internal,
  84                         "allocation should have failed",
  85                         return isl_schedule_tree_free(dup));
  86         case isl_schedule_node_band:
  87                 dup->band = isl_schedule_band_copy(tree->band);
  88                 if (!dup->band)
  89                         return isl_schedule_tree_free(dup);
  90                 break;
  91         case isl_schedule_node_context:
  92                 dup->context = isl_set_copy(tree->context);
  93                 if (!dup->context)
  94                         return isl_schedule_tree_free(dup);
  95                 break;
  96         case isl_schedule_node_domain:
  97                 dup->domain = isl_union_set_copy(tree->domain);
  98                 if (!dup->domain)
  99                         return isl_schedule_tree_free(dup);
 100                 break;
 101         case isl_schedule_node_expansion:
 102                 dup->contraction =
 103                         isl_union_pw_multi_aff_copy(tree->contraction);
 104                 dup->expansion = isl_union_map_copy(tree->expansion);
 105                 if (!dup->contraction || !dup->expansion)
 106                         return isl_schedule_tree_free(dup);
 107                 break;
 108         case isl_schedule_node_extension:
 109                 dup->extension = isl_union_map_copy(tree->extension);
 110                 if (!dup->extension)
 111                         return isl_schedule_tree_free(dup);
 112                 break;
 113         case isl_schedule_node_filter:
 114                 dup->filter = isl_union_set_copy(tree->filter);
 115                 if (!dup->filter)
 116                         return isl_schedule_tree_free(dup);
 117                 break;
 118         case isl_schedule_node_guard:
 119                 dup->guard = isl_set_copy(tree->guard);
 120                 if (!dup->guard)
 121                         return isl_schedule_tree_free(dup);
 122                 break;
 123         case isl_schedule_node_mark:
 124                 dup->mark = isl_id_copy(tree->mark);
 125                 if (!dup->mark)
 126                         return isl_schedule_tree_free(dup);
 127                 break;
 128         case isl_schedule_node_leaf:
 129         case isl_schedule_node_sequence:
 130         case isl_schedule_node_set:
 131                 break;
 132         }
 133
 134         if (tree->children) {
 135                 dup->children = isl_schedule_tree_list_copy(tree->children);
 136                 if (!dup->children)
 137                         return isl_schedule_tree_free(dup);
 138         }
 139         dup->anchored = tree->anchored;
 140
 141         return dup;
 142 }
 143
 144 /* Return an isl_schedule_tree that is equal to "tree" and that has only
 145  * a single reference.
 146  */
 147 __isl_give isl_schedule_tree *isl_schedule_tree_cow(
 148         __isl_take isl_schedule_tree *tree)
 149 {
 150         if (!tree)
 151                 return NULL;
 152
 153         if (tree->ref == 1)
 154                 return tree;
 155         tree->ref--;
 156         return isl_schedule_tree_dup(tree);
 157 }
 158
 159 /* Return a new reference to "tree".
 160  */
 161 __isl_give isl_schedule_tree *isl_schedule_tree_copy(
 162         __isl_keep isl_schedule_tree *tree)
 163 {
 164         if (!tree)
 165                 return NULL;
 166
 167         tree->ref++;
 168         return tree;
 169 }
 170
 171 /* Free "tree" and return NULL.
 172  */
 173 __isl_null isl_schedule_tree *isl_schedule_tree_free(
 174         __isl_take isl_schedule_tree *tree)
 175 {
 176         if (!tree)
 177                 return NULL;
 178         if (--tree->ref > 0)
 179                 return NULL;
 180
 181         switch (tree->type) {
 182         case isl_schedule_node_band:
 183                 isl_schedule_band_free(tree->band);
 184                 break;
 185         case isl_schedule_node_context:
 186                 isl_set_free(tree->context);
 187                 break;
 188         case isl_schedule_node_domain:
 189                 isl_union_set_free(tree->domain);
 190                 break;
 191         case isl_schedule_node_expansion:
 192                 isl_union_pw_multi_aff_free(tree->contraction);
 193                 isl_union_map_free(tree->expansion);
 194                 break;
 195         case isl_schedule_node_extension:
 196                 isl_union_map_free(tree->extension);
 197                 break;
 198         case isl_schedule_node_filter:
 199                 isl_union_set_free(tree->filter);
 200                 break;
 201         case isl_schedule_node_guard:
 202                 isl_set_free(tree->guard);
 203                 break;
 204         case isl_schedule_node_mark:
 205                 isl_id_free(tree->mark);
 206                 break;
 207         case isl_schedule_node_sequence:
 208         case isl_schedule_node_set:
 209         case isl_schedule_node_error:
 210         case isl_schedule_node_leaf:
 211                 break;
 212         }
 213         isl_schedule_tree_list_free(tree->children);
 214         isl_ctx_deref(tree->ctx);
 215         free(tree);
 216
 217         return NULL;
 218 }
 219
 220 /* Create and return a new leaf schedule tree.
 221  */
 222 __isl_give isl_schedule_tree *isl_schedule_tree_leaf(isl_ctx *ctx)
 223 {
 224         return isl_schedule_tree_alloc(ctx, isl_schedule_node_leaf);
 225 }
 226
 227 /* Create a new band schedule tree referring to "band"
 228  * with no children.
 229  */
 230 __isl_give isl_schedule_tree *isl_schedule_tree_from_band(
 231         __isl_take isl_schedule_band *band)
 232 {
 233         isl_ctx *ctx;
 234         isl_schedule_tree *tree;
 235
 236         if (!band)
 237                 return NULL;
 238
 239         ctx = isl_schedule_band_get_ctx(band);
 240         tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_band);
 241         if (!tree)
 242                 goto error;
 243
 244         tree->band = band;
 245         tree->anchored = isl_schedule_band_is_anchored(band);
 246
 247         return tree;
 248 error:
 249         isl_schedule_band_free(band);
 250         return NULL;
 251 }
 252
 253 /* Create a new context schedule tree with the given context and no children.
 254  * Since the context references the outer schedule dimension,
 255  * the tree is anchored.
 256  */
 257 __isl_give isl_schedule_tree *isl_schedule_tree_from_context(
 258         __isl_take isl_set *context)
 259 {
 260         isl_ctx *ctx;
 261         isl_schedule_tree *tree;
 262
 263         if (!context)
 264                 return NULL;
 265
 266         ctx = isl_set_get_ctx(context);
 267         tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_context);
 268         if (!tree)
 269                 goto error;
 270
 271         tree->context = context;
 272         tree->anchored = 1;
 273
 274         return tree;
 275 error:
 276         isl_set_free(context);
 277         return NULL;
 278 }
 279
 280 /* Create a new domain schedule tree with the given domain and no children.
 281  */
 282 __isl_give isl_schedule_tree *isl_schedule_tree_from_domain(
 283         __isl_take isl_union_set *domain)
 284 {
 285         isl_ctx *ctx;
 286         isl_schedule_tree *tree;
 287
 288         if (!domain)
 289                 return NULL;
 290
 291         ctx = isl_union_set_get_ctx(domain);
 292         tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_domain);
 293         if (!tree)
 294                 goto error;
 295
 296         tree->domain = domain;
 297
 298         return tree;
 299 error:
 300         isl_union_set_free(domain);
 301         return NULL;
 302 }
 303
 304 /* Create a new expansion schedule tree with the given contraction and
 305  * expansion and no children.
 306  */
 307 __isl_give isl_schedule_tree *isl_schedule_tree_from_expansion(
 308         __isl_take isl_union_pw_multi_aff *contraction,
 309         __isl_take isl_union_map *expansion)
 310 {
 311         isl_ctx *ctx;
 312         isl_schedule_tree *tree;
 313
 314         if (!contraction || !expansion)
 315                 goto error;
 316
 317         ctx = isl_union_map_get_ctx(expansion);
 318         tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_expansion);
 319         if (!tree)
 320                 goto error;
 321
 322         tree->contraction = contraction;
 323         tree->expansion = expansion;
 324
 325         return tree;
 326 error:
 327         isl_union_pw_multi_aff_free(contraction);
 328         isl_union_map_free(expansion);
 329         return NULL;
 330 }
 331
 332 /* Create a new extension schedule tree with the given extension and
 333  * no children.
 334  * Since the domain of the extension refers to the outer schedule dimension,
 335  * the tree is anchored.
 336  */
 337 __isl_give isl_schedule_tree *isl_schedule_tree_from_extension(
 338         __isl_take isl_union_map *extension)
 339 {
 340         isl_ctx *ctx;
 341         isl_schedule_tree *tree;
 342
 343         if (!extension)
 344                 return NULL;
 345
 346         ctx = isl_union_map_get_ctx(extension);
 347         tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_extension);
 348         if (!tree)
 349                 goto error;
 350
 351         tree->extension = extension;
 352         tree->anchored = 1;
 353
 354         return tree;
 355 error:
 356         isl_union_map_free(extension);
 357         return NULL;
 358 }
 359
 360 /* Create a new filter schedule tree with the given filter and no children.
 361  */
 362 __isl_give isl_schedule_tree *isl_schedule_tree_from_filter(
 363         __isl_take isl_union_set *filter)
 364 {
 365         isl_ctx *ctx;
 366         isl_schedule_tree *tree;
 367
 368         if (!filter)
 369                 return NULL;
 370
 371         ctx = isl_union_set_get_ctx(filter);
 372         tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_filter);
 373         if (!tree)
 374                 goto error;
 375
 376         tree->filter = filter;
 377
 378         return tree;
 379 error:
 380         isl_union_set_free(filter);
 381         return NULL;
 382 }
 383
 384 /* Create a new guard schedule tree with the given guard and no children.
 385  * Since the guard references the outer schedule dimension,
 386  * the tree is anchored.
 387  */
 388 __isl_give isl_schedule_tree *isl_schedule_tree_from_guard(
 389         __isl_take isl_set *guard)
 390 {
 391         isl_ctx *ctx;
 392         isl_schedule_tree *tree;
 393
 394         if (!guard)
 395                 return NULL;
 396
 397         ctx = isl_set_get_ctx(guard);
 398         tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_guard);
 399         if (!tree)
 400                 goto error;
 401
 402         tree->guard = guard;
 403         tree->anchored = 1;
 404
 405         return tree;
 406 error:
 407         isl_set_free(guard);
 408         return NULL;
 409 }
 410
 411 /* Create a new mark schedule tree with the given mark identifier and
 412  * no children.
 413  */
 414 __isl_give isl_schedule_tree *isl_schedule_tree_from_mark(
 415         __isl_take isl_id *mark)
 416 {
 417         isl_ctx *ctx;
 418         isl_schedule_tree *tree;
 419
 420         if (!mark)
 421                 return NULL;
 422
 423         ctx = isl_id_get_ctx(mark);
 424         tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_mark);
 425         if (!tree)
 426                 goto error;
 427
 428         tree->mark = mark;
 429
 430         return tree;
 431 error:
 432         isl_id_free(mark);
 433         return NULL;
 434 }
 435
 436 /* Does "tree" have any node that depends on its position
 437  * in the complete schedule tree?
 438  */
 439 isl_bool isl_schedule_tree_is_subtree_anchored(
 440         __isl_keep isl_schedule_tree *tree)
 441 {
 442         return tree ? tree->anchored : isl_bool_error;
 443 }
 444
 445 /* Does the root node of "tree" depend on its position in the complete
 446  * schedule tree?
 447  * Band nodes may be anchored depending on the associated AST build options.
 448  * Context, extension and guard nodes are always anchored.
 449  */
 450 int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree *tree)
 451 {
 452         if (!tree)
 453                 return -1;
 454
 455         switch (isl_schedule_tree_get_type(tree)) {
 456         case isl_schedule_node_error:
 457                 return -1;
 458         case isl_schedule_node_band:
 459                 return isl_schedule_band_is_anchored(tree->band);
 460         case isl_schedule_node_context:
 461         case isl_schedule_node_extension:
 462         case isl_schedule_node_guard:
 463                 return 1;
 464         case isl_schedule_node_domain:
 465         case isl_schedule_node_expansion:
 466         case isl_schedule_node_filter:
 467         case isl_schedule_node_leaf:
 468         case isl_schedule_node_mark:
 469         case isl_schedule_node_sequence:
 470         case isl_schedule_node_set:
 471                 return 0;
 472         }
 473
 474         isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
 475                 "unhandled case", return -1);
 476 }
 477
 478 /* Update the anchored field of "tree" based on whether the root node
 479  * itself in anchored and the anchored fields of the children.
 480  *
 481  * This function should be called whenever the children of a tree node
 482  * are changed or the anchoredness of the tree root itself changes.
 483  */
 484 __isl_give isl_schedule_tree *isl_schedule_tree_update_anchored(
 485         __isl_take isl_schedule_tree *tree)
 486 {
 487         int i, n;
 488         int anchored;
 489
 490         if (!tree)
 491                 return NULL;
 492
 493         anchored = isl_schedule_tree_is_anchored(tree);
 494         if (anchored < 0)
 495                 return isl_schedule_tree_free(tree);
 496
 497         n = isl_schedule_tree_list_n_schedule_tree(tree->children);
 498         for (i = 0; !anchored && i < n; ++i) {
 499                 isl_schedule_tree *child;
 500
 501                 child = isl_schedule_tree_get_child(tree, i);
 502                 if (!child)
 503                         return isl_schedule_tree_free(tree);
 504                 anchored = child->anchored;
 505                 isl_schedule_tree_free(child);
 506         }
 507
 508         if (anchored == tree->anchored)
 509                 return tree;
 510         tree = isl_schedule_tree_cow(tree);
 511         if (!tree)
 512                 return NULL;
 513         tree->anchored = anchored;
 514         return tree;
 515 }
 516
 517 /* Create a new tree of the given type (isl_schedule_node_sequence or
 518  * isl_schedule_node_set) with the given children.
 519  */
 520 __isl_give isl_schedule_tree *isl_schedule_tree_from_children(
 521         enum isl_schedule_node_type type,
 522         __isl_take isl_schedule_tree_list *list)
 523 {
 524         isl_ctx *ctx;
 525         isl_schedule_tree *tree;
 526
 527         if (!list)
 528                 return NULL;
 529
 530         ctx = isl_schedule_tree_list_get_ctx(list);
 531         tree = isl_schedule_tree_alloc(ctx, type);
 532         if (!tree)
 533                 goto error;
 534
 535         tree->children = list;
 536         tree = isl_schedule_tree_update_anchored(tree);
 537
 538         return tree;
 539 error:
 540         isl_schedule_tree_list_free(list);
 541         return NULL;
 542 }
 543
 544 /* Construct a tree with a root node of type "type" and as children
 545  * "tree1" and "tree2".
 546  * If the root of one (or both) of the input trees is itself of type "type",
 547  * then the tree is replaced by its children.
 548  */
 549 __isl_give isl_schedule_tree *isl_schedule_tree_from_pair(
 550         enum isl_schedule_node_type type, __isl_take isl_schedule_tree *tree1,
 551         __isl_take isl_schedule_tree *tree2)
 552 {
 553         isl_ctx *ctx;
 554         isl_schedule_tree_list *list;
 555
 556         if (!tree1 || !tree2)
 557                 goto error;
 558
 559         ctx = isl_schedule_tree_get_ctx(tree1);
 560         if (isl_schedule_tree_get_type(tree1) == type) {
 561                 list = isl_schedule_tree_list_copy(tree1->children);
 562                 isl_schedule_tree_free(tree1);
 563         } else {
 564                 list = isl_schedule_tree_list_alloc(ctx, 2);
 565                 list = isl_schedule_tree_list_add(list, tree1);
 566         }
 567         if (isl_schedule_tree_get_type(tree2) == type) {
 568                 isl_schedule_tree_list *children;
 569
 570                 children = isl_schedule_tree_list_copy(tree2->children);
 571                 list = isl_schedule_tree_list_concat(list, children);
 572                 isl_schedule_tree_free(tree2);
 573         } else {
 574                 list = isl_schedule_tree_list_add(list, tree2);
 575         }
 576
 577         return isl_schedule_tree_from_children(type, list);
 578 error:
 579         isl_schedule_tree_free(tree1);
 580         isl_schedule_tree_free(tree2);
 581         return NULL;
 582 }
 583
 584 /* Construct a tree with a sequence root node and as children
 585  * "tree1" and "tree2".
 586  * If the root of one (or both) of the input trees is itself a sequence,
 587  * then the tree is replaced by its children.
 588  */
 589 __isl_give isl_schedule_tree *isl_schedule_tree_sequence_pair(
 590         __isl_take isl_schedule_tree *tree1,
 591         __isl_take isl_schedule_tree *tree2)
 592 {
 593         return isl_schedule_tree_from_pair(isl_schedule_node_sequence,
 594                                                 tree1, tree2);
 595 }
 596
 597 /* Construct a tree with a set root node and as children
 598  * "tree1" and "tree2".
 599  * If the root of one (or both) of the input trees is itself a set,
 600  * then the tree is replaced by its children.
 601  */
 602 __isl_give isl_schedule_tree *isl_schedule_tree_set_pair(
 603         __isl_take isl_schedule_tree *tree1,
 604         __isl_take isl_schedule_tree *tree2)
 605 {
 606         return isl_schedule_tree_from_pair(isl_schedule_node_set, tree1, tree2);
 607 }
 608
 609 /* Return the isl_ctx to which "tree" belongs.
 610  */
 611 isl_ctx *isl_schedule_tree_get_ctx(__isl_keep isl_schedule_tree *tree)
 612 {
 613         return tree ? tree->ctx : NULL;
 614 }
 615
 616 /* Return the type of the root of the tree or isl_schedule_node_error
 617  * on error.
 618  */
 619 enum isl_schedule_node_type isl_schedule_tree_get_type(
 620         __isl_keep isl_schedule_tree *tree)
 621 {
 622         return tree ? tree->type : isl_schedule_node_error;
 623 }
 624
 625 /* Are "tree1" and "tree2" obviously equal to each other?
 626  */
 627 isl_bool isl_schedule_tree_plain_is_equal(__isl_keep isl_schedule_tree *tree1,
 628         __isl_keep isl_schedule_tree *tree2)
 629 {
 630         isl_bool equal;
 631         int i, n;
 632
 633         if (!tree1 || !tree2)
 634                 return isl_bool_error;
 635         if (tree1 == tree2)
 636                 return isl_bool_true;
 637         if (tree1->type != tree2->type)
 638                 return isl_bool_false;
 639
 640         switch (tree1->type) {
 641         case isl_schedule_node_band:
 642                 equal = isl_schedule_band_plain_is_equal(tree1->band,
 643                                                         tree2->band);
 644                 break;
 645         case isl_schedule_node_context:
 646                 equal = isl_set_is_equal(tree1->context, tree2->context);
 647                 break;
 648         case isl_schedule_node_domain:
 649                 equal = isl_union_set_is_equal(tree1->domain, tree2->domain);
 650                 break;
 651         case isl_schedule_node_expansion:
 652                 equal = isl_union_map_is_equal(tree1->expansion,
 653                                                 tree2->expansion);
 654                 if (equal >= 0 && equal)
 655                         equal = isl_union_pw_multi_aff_plain_is_equal(
 656                                     tree1->contraction, tree2->contraction);
 657                 break;
 658         case isl_schedule_node_extension:
 659                 equal = isl_union_map_is_equal(tree1->extension,
 660                                                 tree2->extension);
 661                 break;
 662         case isl_schedule_node_filter:
 663                 equal = isl_union_set_is_equal(tree1->filter, tree2->filter);
 664                 break;
 665         case isl_schedule_node_guard:
 666                 equal = isl_set_is_equal(tree1->guard, tree2->guard);
 667                 break;
 668         case isl_schedule_node_mark:
 669                 equal = tree1->mark == tree2->mark;
 670                 break;
 671         case isl_schedule_node_leaf:
 672         case isl_schedule_node_sequence:
 673         case isl_schedule_node_set:
 674                 equal = isl_bool_true;
 675                 break;
 676         case isl_schedule_node_error:
 677                 equal = isl_bool_error;
 678                 break;
 679         }
 680
 681         if (equal < 0 || !equal)
 682                 return equal;
 683
 684         n = isl_schedule_tree_n_children(tree1);
 685         if (n != isl_schedule_tree_n_children(tree2))
 686                 return isl_bool_false;
 687         for (i = 0; i < n; ++i) {
 688                 isl_schedule_tree *child1, *child2;
 689
 690                 child1 = isl_schedule_tree_get_child(tree1, i);
 691                 child2 = isl_schedule_tree_get_child(tree2, i);
 692                 equal = isl_schedule_tree_plain_is_equal(child1, child2);
 693                 isl_schedule_tree_free(child1);
 694                 isl_schedule_tree_free(child2);
 695
 696                 if (equal < 0 || !equal)
 697                         return equal;
 698         }
 699
 700         return isl_bool_true;
 701 }
 702
 703 /* Does "tree" have any children, other than an implicit leaf.
 704  */
 705 int isl_schedule_tree_has_children(__isl_keep isl_schedule_tree *tree)
 706 {
 707         if (!tree)
 708                 return -1;
 709
 710         return tree->children != NULL;
 711 }
 712
 713 /* Return the number of children of "tree", excluding implicit leaves.
 714  */
 715 int isl_schedule_tree_n_children(__isl_keep isl_schedule_tree *tree)
 716 {
 717         if (!tree)
 718                 return -1;
 719
 720         return isl_schedule_tree_list_n_schedule_tree(tree->children);
 721 }
 722
 723 /* Return a copy of the (explicit) child at position "pos" of "tree".
 724  */
 725 __isl_give isl_schedule_tree *isl_schedule_tree_get_child(
 726         __isl_keep isl_schedule_tree *tree, int pos)
 727 {
 728         if (!tree)
 729                 return NULL;
 730         if (!tree->children)
 731                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
 732                         "schedule tree has no explicit children", return NULL);
 733         return isl_schedule_tree_list_get_schedule_tree(tree->children, pos);
 734 }
 735
 736 /* Return a copy of the (explicit) child at position "pos" of "tree" and
 737  * free "tree".
 738  */
 739 __isl_give isl_schedule_tree *isl_schedule_tree_child(
 740         __isl_take isl_schedule_tree *tree, int pos)
 741 {
 742         isl_schedule_tree *child;
 743
 744         child = isl_schedule_tree_get_child(tree, pos);
 745         isl_schedule_tree_free(tree);
 746         return child;
 747 }
 748
 749 /* Remove all (explicit) children from "tree".
 750  */
 751 __isl_give isl_schedule_tree *isl_schedule_tree_reset_children(
 752         __isl_take isl_schedule_tree *tree)
 753 {
 754         tree = isl_schedule_tree_cow(tree);
 755         if (!tree)
 756                 return NULL;
 757         tree->children = isl_schedule_tree_list_free(tree->children);
 758         return tree;
 759 }
 760
 761 /* Remove the child at position "pos" from the children of "tree".
 762  * If there was only one child to begin with, then remove all children.
 763  */
 764 __isl_give isl_schedule_tree *isl_schedule_tree_drop_child(
 765         __isl_take isl_schedule_tree *tree, int pos)
 766 {
 767         int n;
 768
 769         tree = isl_schedule_tree_cow(tree);
 770         if (!tree)
 771                 return NULL;
 772
 773         if (!isl_schedule_tree_has_children(tree))
 774                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
 775                         "tree does not have any explicit children",
 776                         return isl_schedule_tree_free(tree));
 777         n = isl_schedule_tree_list_n_schedule_tree(tree->children);
 778         if (pos < 0 || pos >= n)
 779                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
 780                         "position out of bounds",
 781                         return isl_schedule_tree_free(tree));
 782         if (n == 1)
 783                 return isl_schedule_tree_reset_children(tree);
 784
 785         tree->children = isl_schedule_tree_list_drop(tree->children, pos, 1);
 786         if (!tree->children)
 787                 return isl_schedule_tree_free(tree);
 788
 789         return tree;
 790 }
 791
 792 /* Replace the child at position "pos" of "tree" by "child".
 793  *
 794  * If the new child is a leaf, then it is not explicitly
 795  * recorded in the list of children.  Instead, the list of children
 796  * (which is assumed to have only one element) is removed.
 797  * Note that the children of set and sequence nodes are always
 798  * filters, so they cannot be replaced by empty trees.
 799  */
 800 __isl_give isl_schedule_tree *isl_schedule_tree_replace_child(
 801         __isl_take isl_schedule_tree *tree, int pos,
 802         __isl_take isl_schedule_tree *child)
 803 {
 804         tree = isl_schedule_tree_cow(tree);
 805         if (!tree || !child)
 806                 goto error;
 807
 808         if (isl_schedule_tree_is_leaf(child)) {
 809                 isl_schedule_tree_free(child);
 810                 if (!tree->children && pos == 0)
 811                         return tree;
 812                 if (isl_schedule_tree_n_children(tree) != 1)
 813                         isl_die(isl_schedule_tree_get_ctx(tree),
 814                                 isl_error_internal,
 815                                 "can only replace single child by leaf",
 816                                 goto error);
 817                 return isl_schedule_tree_reset_children(tree);
 818         }
 819
 820         if (!tree->children && pos == 0)
 821                 tree->children =
 822                         isl_schedule_tree_list_from_schedule_tree(child);
 823         else
 824                 tree->children = isl_schedule_tree_list_set_schedule_tree(
 825                                 tree->children, pos, child);
 826
 827         if (!tree->children)
 828                 return isl_schedule_tree_free(tree);
 829         tree = isl_schedule_tree_update_anchored(tree);
 830
 831         return tree;
 832 error:
 833         isl_schedule_tree_free(tree);
 834         isl_schedule_tree_free(child);
 835         return NULL;
 836 }
 837
 838 /* Replace the (explicit) children of "tree" by "children"?
 839  */
 840 __isl_give isl_schedule_tree *isl_schedule_tree_set_children(
 841         __isl_take isl_schedule_tree *tree,
 842         __isl_take isl_schedule_tree_list *children)
 843 {
 844         tree = isl_schedule_tree_cow(tree);
 845         if (!tree || !children)
 846                 goto error;
 847         isl_schedule_tree_list_free(tree->children);
 848         tree->children = children;
 849         return tree;
 850 error:
 851         isl_schedule_tree_free(tree);
 852         isl_schedule_tree_list_free(children);
 853         return NULL;
 854 }
 855
 856 /* Create a new band schedule tree referring to "band"
 857  * with "tree" as single child.
 858  */
 859 __isl_give isl_schedule_tree *isl_schedule_tree_insert_band(
 860         __isl_take isl_schedule_tree *tree, __isl_take isl_schedule_band *band)
 861 {
 862         isl_schedule_tree *res;
 863
 864         res = isl_schedule_tree_from_band(band);
 865         return isl_schedule_tree_replace_child(res, 0, tree);
 866 }
 867
 868 /* Create a new context schedule tree with the given context and
 869  * with "tree" as single child.
 870  */
 871 __isl_give isl_schedule_tree *isl_schedule_tree_insert_context(
 872         __isl_take isl_schedule_tree *tree, __isl_take isl_set *context)
 873 {
 874         isl_schedule_tree *res;
 875
 876         res = isl_schedule_tree_from_context(context);
 877         return isl_schedule_tree_replace_child(res, 0, tree);
 878 }
 879
 880 /* Create a new domain schedule tree with the given domain and
 881  * with "tree" as single child.
 882  */
 883 __isl_give isl_schedule_tree *isl_schedule_tree_insert_domain(
 884         __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
 885 {
 886         isl_schedule_tree *res;
 887
 888         res = isl_schedule_tree_from_domain(domain);
 889         return isl_schedule_tree_replace_child(res, 0, tree);
 890 }
 891
 892 /* Create a new expansion schedule tree with the given contraction and
 893  * expansion and with "tree" as single child.
 894  */
 895 __isl_give isl_schedule_tree *isl_schedule_tree_insert_expansion(
 896         __isl_take isl_schedule_tree *tree,
 897         __isl_take isl_union_pw_multi_aff *contraction,
 898         __isl_take isl_union_map *expansion)
 899 {
 900         isl_schedule_tree *res;
 901
 902         res = isl_schedule_tree_from_expansion(contraction, expansion);
 903         return isl_schedule_tree_replace_child(res, 0, tree);
 904 }
 905
 906 /* Create a new extension schedule tree with the given extension and
 907  * with "tree" as single child.
 908  */
 909 __isl_give isl_schedule_tree *isl_schedule_tree_insert_extension(
 910         __isl_take isl_schedule_tree *tree, __isl_take isl_union_map *extension)
 911 {
 912         isl_schedule_tree *res;
 913
 914         res = isl_schedule_tree_from_extension(extension);
 915         return isl_schedule_tree_replace_child(res, 0, tree);
 916 }
 917
 918 /* Create a new filter schedule tree with the given filter and single child.
 919  *
 920  * If the root of "tree" is itself a filter node, then the two
 921  * filter nodes are merged into one node.
 922  */
 923 __isl_give isl_schedule_tree *isl_schedule_tree_insert_filter(
 924         __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
 925 {
 926         isl_schedule_tree *res;
 927
 928         if (isl_schedule_tree_get_type(tree) == isl_schedule_node_filter) {
 929                 isl_union_set *tree_filter;
 930
 931                 tree_filter = isl_schedule_tree_filter_get_filter(tree);
 932                 tree_filter = isl_union_set_intersect(tree_filter, filter);
 933                 tree = isl_schedule_tree_filter_set_filter(tree, tree_filter);
 934                 return tree;
 935         }
 936
 937         res = isl_schedule_tree_from_filter(filter);
 938         return isl_schedule_tree_replace_child(res, 0, tree);
 939 }
 940
 941 /* Insert a filter node with filter set "filter"
 942  * in each of the children of "tree".
 943  */
 944 __isl_give isl_schedule_tree *isl_schedule_tree_children_insert_filter(
 945         __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
 946 {
 947         int i, n;
 948
 949         if (!tree || !filter)
 950                 goto error;
 951
 952         n = isl_schedule_tree_n_children(tree);
 953         for (i = 0; i < n; ++i) {
 954                 isl_schedule_tree *child;
 955
 956                 child = isl_schedule_tree_get_child(tree, i);
 957                 child = isl_schedule_tree_insert_filter(child,
 958                                                     isl_union_set_copy(filter));
 959                 tree = isl_schedule_tree_replace_child(tree, i, child);
 960         }
 961
 962         isl_union_set_free(filter);
 963         return tree;
 964 error:
 965         isl_union_set_free(filter);
 966         isl_schedule_tree_free(tree);
 967         return NULL;
 968 }
 969
 970 /* Create a new guard schedule tree with the given guard and
 971  * with "tree" as single child.
 972  */
 973 __isl_give isl_schedule_tree *isl_schedule_tree_insert_guard(
 974         __isl_take isl_schedule_tree *tree, __isl_take isl_set *guard)
 975 {
 976         isl_schedule_tree *res;
 977
 978         res = isl_schedule_tree_from_guard(guard);
 979         return isl_schedule_tree_replace_child(res, 0, tree);
 980 }
 981
 982 /* Create a new mark schedule tree with the given mark identifier and
 983  * single child.
 984  */
 985 __isl_give isl_schedule_tree *isl_schedule_tree_insert_mark(
 986         __isl_take isl_schedule_tree *tree, __isl_take isl_id *mark)
 987 {
 988         isl_schedule_tree *res;
 989
 990         res = isl_schedule_tree_from_mark(mark);
 991         return isl_schedule_tree_replace_child(res, 0, tree);
 992 }
 993
 994 /* Return the number of members in the band tree root.
 995  */
 996 unsigned isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree *tree)
 997 {
 998         if (!tree)
 999                 return 0;
1000
1001         if (tree->type != isl_schedule_node_band)
1002                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1003                         "not a band node", return 0);
1004
1005         return isl_schedule_band_n_member(tree->band);
1006 }
1007
1008 /* Is the band member at position "pos" of the band tree root
1009  * marked coincident?
1010  */
1011 isl_bool isl_schedule_tree_band_member_get_coincident(
1012         __isl_keep isl_schedule_tree *tree, int pos)
1013 {
1014         if (!tree)
1015                 return isl_bool_error;
1016
1017         if (tree->type != isl_schedule_node_band)
1018                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1019                         "not a band node", return isl_bool_error);
1020
1021         return isl_schedule_band_member_get_coincident(tree->band, pos);
1022 }
1023
1024 /* Mark the given band member as being coincident or not
1025  * according to "coincident".
1026  */
1027 __isl_give isl_schedule_tree *isl_schedule_tree_band_member_set_coincident(
1028         __isl_take isl_schedule_tree *tree, int pos, int coincident)
1029 {
1030         if (!tree)
1031                 return NULL;
1032         if (tree->type != isl_schedule_node_band)
1033                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1034                         "not a band node", return isl_schedule_tree_free(tree));
1035         if (isl_schedule_tree_band_member_get_coincident(tree, pos) ==
1036                                                                     coincident)
1037                 return tree;
1038         tree = isl_schedule_tree_cow(tree);
1039         if (!tree)
1040                 return NULL;
1041
1042         tree->band = isl_schedule_band_member_set_coincident(tree->band, pos,
1043                                                         coincident);
1044         if (!tree->band)
1045                 return isl_schedule_tree_free(tree);
1046         return tree;
1047 }
1048
1049 /* Is the band tree root marked permutable?
1050  */
1051 isl_bool isl_schedule_tree_band_get_permutable(
1052         __isl_keep isl_schedule_tree *tree)
1053 {
1054         if (!tree)
1055                 return isl_bool_error;
1056
1057         if (tree->type != isl_schedule_node_band)
1058                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1059                         "not a band node", return isl_bool_error);
1060
1061         return isl_schedule_band_get_permutable(tree->band);
1062 }
1063
1064 /* Mark the band tree root permutable or not according to "permutable"?
1065  */
1066 __isl_give isl_schedule_tree *isl_schedule_tree_band_set_permutable(
1067         __isl_take isl_schedule_tree *tree, int permutable)
1068 {
1069         if (!tree)
1070                 return NULL;
1071         if (tree->type != isl_schedule_node_band)
1072                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1073                         "not a band node", return isl_schedule_tree_free(tree));
1074         if (isl_schedule_tree_band_get_permutable(tree) == permutable)
1075                 return tree;
1076         tree = isl_schedule_tree_cow(tree);
1077         if (!tree)
1078                 return NULL;
1079
1080         tree->band = isl_schedule_band_set_permutable(tree->band, permutable);
1081         if (!tree->band)
1082                 return isl_schedule_tree_free(tree);
1083         return tree;
1084 }
1085
1086 /* Return the schedule space of the band tree root.
1087  */
1088 __isl_give isl_space *isl_schedule_tree_band_get_space(
1089         __isl_keep isl_schedule_tree *tree)
1090 {
1091         if (!tree)
1092                 return NULL;
1093
1094         if (tree->type != isl_schedule_node_band)
1095                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1096                         "not a band node", return NULL);
1097
1098         return isl_schedule_band_get_space(tree->band);
1099 }
1100
1101 /* Intersect the domain of the band schedule of the band tree root
1102  * with "domain".
1103  */
1104 __isl_give isl_schedule_tree *isl_schedule_tree_band_intersect_domain(
1105         __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
1106 {
1107         if (!tree || !domain)
1108                 goto error;
1109
1110         if (tree->type != isl_schedule_node_band)
1111                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1112                         "not a band node", goto error);
1113
1114         tree->band = isl_schedule_band_intersect_domain(tree->band, domain);
1115         if (!tree->band)
1116                 return isl_schedule_tree_free(tree);
1117
1118         return tree;
1119 error:
1120         isl_schedule_tree_free(tree);
1121         isl_union_set_free(domain);
1122         return NULL;
1123 }
1124
1125 /* Return the schedule of the band tree root in isolation.
1126  */
1127 __isl_give isl_multi_union_pw_aff *isl_schedule_tree_band_get_partial_schedule(
1128         __isl_keep isl_schedule_tree *tree)
1129 {
1130         if (!tree)
1131                 return NULL;
1132
1133         if (tree->type != isl_schedule_node_band)
1134                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1135                         "not a band node", return NULL);
1136
1137         return isl_schedule_band_get_partial_schedule(tree->band);
1138 }
1139
1140 /* Replace the schedule of the band tree root by "schedule".
1141  */
1142 __isl_give isl_schedule_tree *isl_schedule_tree_band_set_partial_schedule(
1143         __isl_take isl_schedule_tree *tree,
1144         __isl_take isl_multi_union_pw_aff *schedule)
1145 {
1146         tree = isl_schedule_tree_cow(tree);
1147         if (!tree || !schedule)
1148                 goto error;
1149
1150         if (tree->type != isl_schedule_node_band)
1151                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1152                         "not a band node", return NULL);
1153         tree->band = isl_schedule_band_set_partial_schedule(tree->band,
1154                                                                 schedule);
1155
1156         return tree;
1157 error:
1158         isl_schedule_tree_free(tree);
1159         isl_multi_union_pw_aff_free(schedule);
1160         return NULL;
1161 }
1162
1163 /* Return the loop AST generation type for the band member
1164  * of the band tree root at position "pos".
1165  */
1166 enum isl_ast_loop_type isl_schedule_tree_band_member_get_ast_loop_type(
1167         __isl_keep isl_schedule_tree *tree, int pos)
1168 {
1169         if (!tree)
1170                 return isl_ast_loop_error;
1171
1172         if (tree->type != isl_schedule_node_band)
1173                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1174                         "not a band node", return isl_ast_loop_error);
1175
1176         return isl_schedule_band_member_get_ast_loop_type(tree->band, pos);
1177 }
1178
1179 /* Set the loop AST generation type for the band member of the band tree root
1180  * at position "pos" to "type".
1181  */
1182 __isl_give isl_schedule_tree *isl_schedule_tree_band_member_set_ast_loop_type(
1183         __isl_take isl_schedule_tree *tree, int pos,
1184         enum isl_ast_loop_type type)
1185 {
1186         tree = isl_schedule_tree_cow(tree);
1187         if (!tree)
1188                 return NULL;
1189
1190         if (tree->type != isl_schedule_node_band)
1191                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1192                         "not a band node", return isl_schedule_tree_free(tree));
1193
1194         tree->band = isl_schedule_band_member_set_ast_loop_type(tree->band,
1195                                                                 pos, type);
1196         if (!tree->band)
1197                 return isl_schedule_tree_free(tree);
1198
1199         return tree;
1200 }
1201
1202 /* Return the loop AST generation type for the band member
1203  * of the band tree root at position "pos" for the isolated part.
1204  */
1205 enum isl_ast_loop_type isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1206         __isl_keep isl_schedule_tree *tree, int pos)
1207 {
1208         if (!tree)
1209                 return isl_ast_loop_error;
1210
1211         if (tree->type != isl_schedule_node_band)
1212                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1213                         "not a band node", return isl_ast_loop_error);
1214
1215         return isl_schedule_band_member_get_isolate_ast_loop_type(tree->band,
1216                                                                         pos);
1217 }
1218
1219 /* Set the loop AST generation type for the band member of the band tree root
1220  * at position "pos" for the isolated part to "type".
1221  */
1222 __isl_give isl_schedule_tree *
1223 isl_schedule_tree_band_member_set_isolate_ast_loop_type(
1224         __isl_take isl_schedule_tree *tree, int pos,
1225         enum isl_ast_loop_type type)
1226 {
1227         tree = isl_schedule_tree_cow(tree);
1228         if (!tree)
1229                 return NULL;
1230
1231         if (tree->type != isl_schedule_node_band)
1232                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1233                         "not a band node", return isl_schedule_tree_free(tree));
1234
1235         tree->band = isl_schedule_band_member_set_isolate_ast_loop_type(
1236                                                         tree->band, pos, type);
1237         if (!tree->band)
1238                 return isl_schedule_tree_free(tree);
1239
1240         return tree;
1241 }
1242
1243 /* Return the AST build options associated to the band tree root.
1244  */
1245 __isl_give isl_union_set *isl_schedule_tree_band_get_ast_build_options(
1246         __isl_keep isl_schedule_tree *tree)
1247 {
1248         if (!tree)
1249                 return NULL;
1250
1251         if (tree->type != isl_schedule_node_band)
1252                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1253                         "not a band node", return NULL);
1254
1255         return isl_schedule_band_get_ast_build_options(tree->band);
1256 }
1257
1258 /* Replace the AST build options associated to band tree root by "options".
1259  * Updated the anchored field if the anchoredness of the root node itself
1260  * changes.
1261  */
1262 __isl_give isl_schedule_tree *isl_schedule_tree_band_set_ast_build_options(
1263         __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *options)
1264 {
1265         int was_anchored;
1266
1267         tree = isl_schedule_tree_cow(tree);
1268         if (!tree || !options)
1269                 goto error;
1270
1271         if (tree->type != isl_schedule_node_band)
1272                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1273                         "not a band node", goto error);
1274
1275         was_anchored = isl_schedule_tree_is_anchored(tree);
1276         tree->band = isl_schedule_band_set_ast_build_options(tree->band,
1277                                                                 options);
1278         if (!tree->band)
1279                 return isl_schedule_tree_free(tree);
1280         if (isl_schedule_tree_is_anchored(tree) != was_anchored)
1281                 tree = isl_schedule_tree_update_anchored(tree);
1282
1283         return tree;
1284 error:
1285         isl_schedule_tree_free(tree);
1286         isl_union_set_free(options);
1287         return NULL;
1288 }
1289
1290 /* Return the "isolate" option associated to the band tree root of "tree",
1291  * which is assumed to appear at schedule depth "depth".
1292  */
1293 __isl_give isl_set *isl_schedule_tree_band_get_ast_isolate_option(
1294         __isl_keep isl_schedule_tree *tree, int depth)
1295 {
1296         if (!tree)
1297                 return NULL;
1298
1299         if (tree->type != isl_schedule_node_band)
1300                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1301                         "not a band node", return NULL);
1302
1303         return isl_schedule_band_get_ast_isolate_option(tree->band, depth);
1304 }
1305
1306 /* Return the context of the context tree root.
1307  */
1308 __isl_give isl_set *isl_schedule_tree_context_get_context(
1309         __isl_keep isl_schedule_tree *tree)
1310 {
1311         if (!tree)
1312                 return NULL;
1313
1314         if (tree->type != isl_schedule_node_context)
1315                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1316                         "not a context node", return NULL);
1317
1318         return isl_set_copy(tree->context);
1319 }
1320
1321 /* Return the domain of the domain tree root.
1322  */
1323 __isl_give isl_union_set *isl_schedule_tree_domain_get_domain(
1324         __isl_keep isl_schedule_tree *tree)
1325 {
1326         if (!tree)
1327                 return NULL;
1328
1329         if (tree->type != isl_schedule_node_domain)
1330                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1331                         "not a domain node", return NULL);
1332
1333         return isl_union_set_copy(tree->domain);
1334 }
1335
1336 /* Replace the domain of domain tree root "tree" by "domain".
1337  */
1338 __isl_give isl_schedule_tree *isl_schedule_tree_domain_set_domain(
1339         __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
1340 {
1341         tree = isl_schedule_tree_cow(tree);
1342         if (!tree || !domain)
1343                 goto error;
1344
1345         if (tree->type != isl_schedule_node_domain)
1346                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1347                         "not a domain node", goto error);
1348
1349         isl_union_set_free(tree->domain);
1350         tree->domain = domain;
1351
1352         return tree;
1353 error:
1354         isl_schedule_tree_free(tree);
1355         isl_union_set_free(domain);
1356         return NULL;
1357 }
1358
1359 /* Return the contraction of the expansion tree root.
1360  */
1361 __isl_give isl_union_pw_multi_aff *isl_schedule_tree_expansion_get_contraction(
1362         __isl_keep isl_schedule_tree *tree)
1363 {
1364         if (!tree)
1365                 return NULL;
1366
1367         if (tree->type != isl_schedule_node_expansion)
1368                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1369                         "not an expansion node", return NULL);
1370
1371         return isl_union_pw_multi_aff_copy(tree->contraction);
1372 }
1373
1374 /* Return the expansion of the expansion tree root.
1375  */
1376 __isl_give isl_union_map *isl_schedule_tree_expansion_get_expansion(
1377         __isl_keep isl_schedule_tree *tree)
1378 {
1379         if (!tree)
1380                 return NULL;
1381
1382         if (tree->type != isl_schedule_node_expansion)
1383                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1384                         "not an expansion node", return NULL);
1385
1386         return isl_union_map_copy(tree->expansion);
1387 }
1388
1389 /* Replace the contraction and the expansion of the expansion tree root "tree"
1390  * by "contraction" and "expansion".
1391  */
1392 __isl_give isl_schedule_tree *
1393 isl_schedule_tree_expansion_set_contraction_and_expansion(
1394         __isl_take isl_schedule_tree *tree,
1395         __isl_take isl_union_pw_multi_aff *contraction,
1396         __isl_take isl_union_map *expansion)
1397 {
1398         tree = isl_schedule_tree_cow(tree);
1399         if (!tree || !contraction || !expansion)
1400                 goto error;
1401
1402         if (tree->type != isl_schedule_node_expansion)
1403                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1404                         "not an expansion node", return NULL);
1405
1406         isl_union_pw_multi_aff_free(tree->contraction);
1407         tree->contraction = contraction;
1408         isl_union_map_free(tree->expansion);
1409         tree->expansion = expansion;
1410
1411         return tree;
1412 error:
1413         isl_schedule_tree_free(tree);
1414         isl_union_pw_multi_aff_free(contraction);
1415         isl_union_map_free(expansion);
1416         return NULL;
1417 }
1418
1419 /* Return the extension of the extension tree root.
1420  */
1421 __isl_give isl_union_map *isl_schedule_tree_extension_get_extension(
1422         __isl_take isl_schedule_tree *tree)
1423 {
1424         if (!tree)
1425                 return NULL;
1426
1427         if (tree->type != isl_schedule_node_extension)
1428                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1429                         "not an extension node", return NULL);
1430
1431         return isl_union_map_copy(tree->extension);
1432 }
1433
1434 /* Replace the extension of extension tree root "tree" by "extension".
1435  */
1436 __isl_give isl_schedule_tree *isl_schedule_tree_extension_set_extension(
1437         __isl_take isl_schedule_tree *tree, __isl_take isl_union_map *extension)
1438 {
1439         tree = isl_schedule_tree_cow(tree);
1440         if (!tree || !extension)
1441                 goto error;
1442
1443         if (tree->type != isl_schedule_node_extension)
1444                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1445                         "not an extension node", return NULL);
1446         isl_union_map_free(tree->extension);
1447         tree->extension = extension;
1448
1449         return tree;
1450 error:
1451         isl_schedule_tree_free(tree);
1452         isl_union_map_free(extension);
1453         return NULL;
1454 }
1455
1456 /* Return the filter of the filter tree root.
1457  */
1458 __isl_give isl_union_set *isl_schedule_tree_filter_get_filter(
1459         __isl_keep isl_schedule_tree *tree)
1460 {
1461         if (!tree)
1462                 return NULL;
1463
1464         if (tree->type != isl_schedule_node_filter)
1465                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1466                         "not a filter node", return NULL);
1467
1468         return isl_union_set_copy(tree->filter);
1469 }
1470
1471 /* Replace the filter of the filter tree root by "filter".
1472  */
1473 __isl_give isl_schedule_tree *isl_schedule_tree_filter_set_filter(
1474         __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
1475 {
1476         tree = isl_schedule_tree_cow(tree);
1477         if (!tree || !filter)
1478                 goto error;
1479
1480         if (tree->type != isl_schedule_node_filter)
1481                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1482                         "not a filter node", return NULL);
1483
1484         isl_union_set_free(tree->filter);
1485         tree->filter = filter;
1486
1487         return tree;
1488 error:
1489         isl_schedule_tree_free(tree);
1490         isl_union_set_free(filter);
1491         return NULL;
1492 }
1493
1494 /* Return the guard of the guard tree root.
1495  */
1496 __isl_give isl_set *isl_schedule_tree_guard_get_guard(
1497         __isl_take isl_schedule_tree *tree)
1498 {
1499         if (!tree)
1500                 return NULL;
1501
1502         if (tree->type != isl_schedule_node_guard)
1503                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1504                         "not a guard node", return NULL);
1505
1506         return isl_set_copy(tree->guard);
1507 }
1508
1509 /* Return the mark identifier of the mark tree root "tree".
1510  */
1511 __isl_give isl_id *isl_schedule_tree_mark_get_id(
1512         __isl_keep isl_schedule_tree *tree)
1513 {
1514         if (!tree)
1515                 return NULL;
1516
1517         if (tree->type != isl_schedule_node_mark)
1518                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1519                         "not a mark node", return NULL);
1520
1521         return isl_id_copy(tree->mark);
1522 }
1523
1524 /* Set dim to the range dimension of "map" and abort the search.
1525  */
1526 static isl_stat set_range_dim(__isl_take isl_map *map, void *user)
1527 {
1528         int *dim = user;
1529
1530         *dim = isl_map_dim(map, isl_dim_out);
1531         isl_map_free(map);
1532
1533         return isl_stat_error;
1534 }
1535
1536 /* Return the dimension of the range of "umap".
1537  * "umap" is assumed not to be empty and
1538  * all maps inside "umap" are assumed to have the same range.
1539  *
1540  * We extract the range dimension from the first map in "umap".
1541  */
1542 static int range_dim(__isl_keep isl_union_map *umap)
1543 {
1544         int dim = -1;
1545
1546         if (!umap)
1547                 return -1;
1548         if (isl_union_map_n_map(umap) == 0)
1549                 isl_die(isl_union_map_get_ctx(umap), isl_error_internal,
1550                         "unexpected empty input", return -1);
1551
1552         isl_union_map_foreach_map(umap, &set_range_dim, &dim);
1553
1554         return dim;
1555 }
1556
1557 /* Append an "extra" number of zeros to the range of "umap" and
1558  * return the result.
1559  */
1560 static __isl_give isl_union_map *append_range(__isl_take isl_union_map *umap,
1561         int extra)
1562 {
1563         isl_union_set *dom;
1564         isl_space *space;
1565         isl_multi_val *mv;
1566         isl_union_pw_multi_aff *suffix;
1567         isl_union_map *universe;
1568         isl_union_map *suffix_umap;
1569
1570         universe = isl_union_map_universe(isl_union_map_copy(umap));
1571         dom = isl_union_map_domain(universe);
1572         space = isl_union_set_get_space(dom);
1573         space = isl_space_set_from_params(space);
1574         space = isl_space_add_dims(space, isl_dim_set, extra);
1575         mv = isl_multi_val_zero(space);
1576
1577         suffix = isl_union_pw_multi_aff_multi_val_on_domain(dom, mv);
1578         suffix_umap = isl_union_map_from_union_pw_multi_aff(suffix);
1579         umap = isl_union_map_flat_range_product(umap, suffix_umap);
1580
1581         return umap;
1582 }
1583
1584 /* Should we skip the root of "tree" while looking for the first
1585  * descendant with schedule information?
1586  * That is, is it impossible to derive any information about
1587  * the iteration domain from this node?
1588  *
1589  * We do not want to skip leaf or error nodes because there is
1590  * no point in looking any deeper from these nodes.
1591  * We can only extract partial iteration domain information
1592  * from an extension node, but extension nodes are not supported
1593  * by the caller and it will error out on them.
1594  */
1595 static int domain_less(__isl_keep isl_schedule_tree *tree)
1596 {
1597         enum isl_schedule_node_type type;
1598
1599         type = isl_schedule_tree_get_type(tree);
1600         switch (type) {
1601         case isl_schedule_node_band:
1602                 return isl_schedule_tree_band_n_member(tree) == 0;
1603         case isl_schedule_node_context:
1604         case isl_schedule_node_guard:
1605         case isl_schedule_node_mark:
1606                 return 1;
1607         case isl_schedule_node_leaf:
1608         case isl_schedule_node_error:
1609         case isl_schedule_node_domain:
1610         case isl_schedule_node_expansion:
1611         case isl_schedule_node_extension:
1612         case isl_schedule_node_filter:
1613         case isl_schedule_node_set:
1614         case isl_schedule_node_sequence:
1615                 return 0;
1616         }
1617
1618         isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1619                 "unhandled case", return 0);
1620 }
1621
1622 /* Move down to the first descendant of "tree" that contains any schedule
1623  * information or return "leaf" if there is no such descendant.
1624  */
1625 __isl_give isl_schedule_tree *isl_schedule_tree_first_schedule_descendant(
1626         __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_tree *leaf)
1627 {
1628         while (domain_less(tree)) {
1629                 if (!isl_schedule_tree_has_children(tree)) {
1630                         isl_schedule_tree_free(tree);
1631                         return isl_schedule_tree_copy(leaf);
1632                 }
1633                 tree = isl_schedule_tree_child(tree, 0);
1634         }
1635
1636         return tree;
1637 }
1638
1639 static __isl_give isl_union_map *subtree_schedule_extend(
1640         __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer);
1641
1642 /* Extend the schedule map "outer" with the subtree schedule
1643  * of the (single) child of "tree", if any.
1644  *
1645  * If "tree" does not have any descendants (apart from those that
1646  * do not carry any schedule information), then we simply return "outer".
1647  * Otherwise, we extend the schedule map "outer" with the subtree schedule
1648  * of the single child.
1649  */
1650 static __isl_give isl_union_map *subtree_schedule_extend_child(
1651         __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1652 {
1653         isl_schedule_tree *child;
1654         isl_union_map *res;
1655
1656         if (!tree)
1657                 return isl_union_map_free(outer);
1658         if (!isl_schedule_tree_has_children(tree))
1659                 return outer;
1660         child = isl_schedule_tree_get_child(tree, 0);
1661         if (!child)
1662                 return isl_union_map_free(outer);
1663         res = subtree_schedule_extend(child, outer);
1664         isl_schedule_tree_free(child);
1665         return res;
1666 }
1667
1668 /* Extract the parameter space from one of the children of "tree",
1669  * which are assumed to be filters.
1670  */
1671 static __isl_give isl_space *extract_space_from_filter_child(
1672         __isl_keep isl_schedule_tree *tree)
1673 {
1674         isl_space *space;
1675         isl_union_set *dom;
1676         isl_schedule_tree *child;
1677
1678         child = isl_schedule_tree_list_get_schedule_tree(tree->children, 0);
1679         dom = isl_schedule_tree_filter_get_filter(child);
1680         space = isl_union_set_get_space(dom);
1681         isl_union_set_free(dom);
1682         isl_schedule_tree_free(child);
1683
1684         return space;
1685 }
1686
1687 /* Extend the schedule map "outer" with the subtree schedule
1688  * of a set or sequence node.
1689  *
1690  * The schedule for the set or sequence node itself is composed of
1691  * pieces of the form
1692  *
1693  *      filter -> []
1694  *
1695  * or
1696  *
1697  *      filter -> [index]
1698  *
1699  * The first form is used if there is only a single child or
1700  * if the current node is a set node and the schedule_separate_components
1701  * option is not set.
1702  *
1703  * Each of the pieces above is extended with the subtree schedule of
1704  * the child of the corresponding filter, if any, padded with zeros
1705  * to ensure that all pieces have the same range dimension.
1706  */
1707 static __isl_give isl_union_map *subtree_schedule_extend_from_children(
1708         __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1709 {
1710         int i, n;
1711         int dim;
1712         int separate;
1713         isl_ctx *ctx;
1714         isl_val *v = NULL;
1715         isl_multi_val *mv;
1716         isl_space *space;
1717         isl_union_map *umap;
1718
1719         if (!tree)
1720                 return NULL;
1721
1722         ctx = isl_schedule_tree_get_ctx(tree);
1723         if (!tree->children)
1724                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1725                         "missing children", return NULL);
1726         n = isl_schedule_tree_list_n_schedule_tree(tree->children);
1727         if (n == 0)
1728                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1729                         "missing children", return NULL);
1730
1731         separate = n > 1 && (tree->type == isl_schedule_node_sequence ||
1732                             isl_options_get_schedule_separate_components(ctx));
1733
1734         space = extract_space_from_filter_child(tree);
1735
1736         umap = isl_union_map_empty(isl_space_copy(space));
1737         space = isl_space_set_from_params(space);
1738         if (separate) {
1739                 space = isl_space_add_dims(space, isl_dim_set, 1);
1740                 v = isl_val_zero(ctx);
1741         }
1742         mv = isl_multi_val_zero(space);
1743
1744         dim = isl_multi_val_dim(mv, isl_dim_set);
1745         for (i = 0; i < n; ++i) {
1746                 isl_union_pw_multi_aff *upma;
1747                 isl_union_map *umap_i;
1748                 isl_union_set *dom;
1749                 isl_schedule_tree *child;
1750                 int dim_i;
1751                 int empty;
1752
1753                 child = isl_schedule_tree_list_get_schedule_tree(
1754                                                         tree->children, i);
1755                 dom = isl_schedule_tree_filter_get_filter(child);
1756
1757                 if (separate) {
1758                         mv = isl_multi_val_set_val(mv, 0, isl_val_copy(v));
1759                         v = isl_val_add_ui(v, 1);
1760                 }
1761                 upma = isl_union_pw_multi_aff_multi_val_on_domain(dom,
1762                                                         isl_multi_val_copy(mv));
1763                 umap_i = isl_union_map_from_union_pw_multi_aff(upma);
1764                 umap_i = isl_union_map_flat_range_product(
1765                                             isl_union_map_copy(outer), umap_i);
1766                 umap_i = subtree_schedule_extend_child(child, umap_i);
1767                 isl_schedule_tree_free(child);
1768
1769                 empty = isl_union_map_is_empty(umap_i);
1770                 if (empty < 0)
1771                         umap_i = isl_union_map_free(umap_i);
1772                 else if (empty) {
1773                         isl_union_map_free(umap_i);
1774                         continue;
1775                 }
1776
1777                 dim_i = range_dim(umap_i);
1778                 if (dim_i < 0) {
1779                         umap = isl_union_map_free(umap);
1780                 } else if (dim < dim_i) {
1781                         umap = append_range(umap, dim_i - dim);
1782                         dim = dim_i;
1783                 } else if (dim_i < dim) {
1784                         umap_i = append_range(umap_i, dim - dim_i);
1785                 }
1786                 umap = isl_union_map_union(umap, umap_i);
1787         }
1788
1789         isl_val_free(v);
1790         isl_multi_val_free(mv);
1791         isl_union_map_free(outer);
1792
1793         return umap;
1794 }
1795
1796 /* Extend the schedule map "outer" with the subtree schedule of "tree".
1797  *
1798  * If the root of the tree is a set or a sequence, then we extend
1799  * the schedule map in subtree_schedule_extend_from_children.
1800  * Otherwise, we extend the schedule map with the partial schedule
1801  * corresponding to the root of the tree and then continue with
1802  * the single child of this root.
1803  * In the special case of an expansion, the schedule map is "extended"
1804  * by applying the expansion to the domain of the schedule map.
1805  */
1806 static __isl_give isl_union_map *subtree_schedule_extend(
1807         __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1808 {
1809         isl_multi_union_pw_aff *mupa;
1810         isl_union_map *umap;
1811         isl_union_set *domain;
1812
1813         if (!tree)
1814                 return NULL;
1815
1816         switch (tree->type) {
1817         case isl_schedule_node_error:
1818                 return isl_union_map_free(outer);
1819         case isl_schedule_node_extension:
1820                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1821                         "cannot construct subtree schedule of tree "
1822                         "with extension nodes",
1823                         return isl_union_map_free(outer));
1824         case isl_schedule_node_context:
1825         case isl_schedule_node_guard:
1826         case isl_schedule_node_mark:
1827                 return subtree_schedule_extend_child(tree, outer);
1828         case isl_schedule_node_band:
1829                 if (isl_schedule_tree_band_n_member(tree) == 0)
1830                         return subtree_schedule_extend_child(tree, outer);
1831                 mupa = isl_schedule_band_get_partial_schedule(tree->band);
1832                 umap = isl_union_map_from_multi_union_pw_aff(mupa);
1833                 outer = isl_union_map_flat_range_product(outer, umap);
1834                 umap = subtree_schedule_extend_child(tree, outer);
1835                 break;
1836         case isl_schedule_node_domain:
1837                 domain = isl_schedule_tree_domain_get_domain(tree);
1838                 umap = isl_union_map_from_domain(domain);
1839                 outer = isl_union_map_flat_range_product(outer, umap);
1840                 umap = subtree_schedule_extend_child(tree, outer);
1841                 break;
1842         case isl_schedule_node_expansion:
1843                 umap = isl_schedule_tree_expansion_get_expansion(tree);
1844                 outer = isl_union_map_apply_domain(outer, umap);
1845                 umap = subtree_schedule_extend_child(tree, outer);
1846                 break;
1847         case isl_schedule_node_filter:
1848                 domain = isl_schedule_tree_filter_get_filter(tree);
1849                 umap = isl_union_map_from_domain(domain);
1850                 outer = isl_union_map_flat_range_product(outer, umap);
1851                 umap = subtree_schedule_extend_child(tree, outer);
1852                 break;
1853         case isl_schedule_node_leaf:
1854                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1855                         "leaf node should be handled by caller", return NULL);
1856         case isl_schedule_node_set:
1857         case isl_schedule_node_sequence:
1858                 umap = subtree_schedule_extend_from_children(tree, outer);
1859                 break;
1860         }
1861
1862         return umap;
1863 }
1864
1865 static __isl_give isl_union_set *initial_domain(
1866         __isl_keep isl_schedule_tree *tree);
1867
1868 /* Extract a universe domain from the children of the tree root "tree",
1869  * which is a set or sequence, meaning that its children are filters.
1870  * In particular, return the union of the universes of the filters.
1871  */
1872 static __isl_give isl_union_set *initial_domain_from_children(
1873         __isl_keep isl_schedule_tree *tree)
1874 {
1875         int i, n;
1876         isl_space *space;
1877         isl_union_set *domain;
1878
1879         if (!tree->children)
1880                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1881                         "missing children", return NULL);
1882         n = isl_schedule_tree_list_n_schedule_tree(tree->children);
1883         if (n == 0)
1884                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1885                         "missing children", return NULL);
1886
1887         space = extract_space_from_filter_child(tree);
1888         domain = isl_union_set_empty(space);
1889
1890         for (i = 0; i < n; ++i) {
1891                 isl_schedule_tree *child;
1892                 isl_union_set *domain_i;
1893
1894                 child = isl_schedule_tree_get_child(tree, i);
1895                 domain_i = initial_domain(child);
1896                 domain = isl_union_set_union(domain, domain_i);
1897                 isl_schedule_tree_free(child);
1898         }
1899
1900         return domain;
1901 }
1902
1903 /* Extract a universe domain from the tree root "tree".
1904  * The caller is responsible for making sure that this node
1905  * would not be skipped by isl_schedule_tree_first_schedule_descendant
1906  * and that it is not a leaf node.
1907  */
1908 static __isl_give isl_union_set *initial_domain(
1909         __isl_keep isl_schedule_tree *tree)
1910 {
1911         isl_multi_union_pw_aff *mupa;
1912         isl_union_set *domain;
1913         isl_union_map *exp;
1914
1915         if (!tree)
1916                 return NULL;
1917
1918         switch (tree->type) {
1919         case isl_schedule_node_error:
1920                 return NULL;
1921         case isl_schedule_node_context:
1922                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1923                         "context node should be handled by caller",
1924                         return NULL);
1925         case isl_schedule_node_guard:
1926                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1927                         "guard node should be handled by caller",
1928                         return NULL);
1929         case isl_schedule_node_mark:
1930                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1931                         "mark node should be handled by caller",
1932                         return NULL);
1933         case isl_schedule_node_extension:
1934                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1935                         "cannot construct subtree schedule of tree "
1936                         "with extension nodes", return NULL);
1937         case isl_schedule_node_band:
1938                 if (isl_schedule_tree_band_n_member(tree) == 0)
1939                         isl_die(isl_schedule_tree_get_ctx(tree),
1940                                 isl_error_internal,
1941                                 "0D band should be handled by caller",
1942                                 return NULL);
1943                 mupa = isl_schedule_band_get_partial_schedule(tree->band);
1944                 domain = isl_multi_union_pw_aff_domain(mupa);
1945                 domain = isl_union_set_universe(domain);
1946                 break;
1947         case isl_schedule_node_domain:
1948                 domain = isl_schedule_tree_domain_get_domain(tree);
1949                 domain = isl_union_set_universe(domain);
1950                 break;
1951         case isl_schedule_node_expansion:
1952                 exp = isl_schedule_tree_expansion_get_expansion(tree);
1953                 exp = isl_union_map_universe(exp);
1954                 domain = isl_union_map_domain(exp);
1955                 break;
1956         case isl_schedule_node_filter:
1957                 domain = isl_schedule_tree_filter_get_filter(tree);
1958                 domain = isl_union_set_universe(domain);
1959                 break;
1960         case isl_schedule_node_leaf:
1961                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1962                         "leaf node should be handled by caller", return NULL);
1963         case isl_schedule_node_set:
1964         case isl_schedule_node_sequence:
1965                 domain = initial_domain_from_children(tree);
1966                 break;
1967         }
1968
1969         return domain;
1970 }
1971
1972 /* Return the subtree schedule of a node that contains some schedule
1973  * information, i.e., a node that would not be skipped by
1974  * isl_schedule_tree_first_schedule_descendant and that is not a leaf.
1975  *
1976  * If the tree contains any expansions, then the returned subtree
1977  * schedule is formulated in terms of the expanded domains.
1978  * The tree is not allowed to contain any extension nodes.
1979  *
1980  * We start with an initial zero-dimensional subtree schedule based
1981  * on the domain information in the root node and then extend it
1982  * based on the schedule information in the root node and its descendants.
1983  */
1984 __isl_give isl_union_map *isl_schedule_tree_get_subtree_schedule_union_map(
1985         __isl_keep isl_schedule_tree *tree)
1986 {
1987         isl_union_set *domain;
1988         isl_union_map *umap;
1989
1990         domain = initial_domain(tree);
1991         umap = isl_union_map_from_domain(domain);
1992         return subtree_schedule_extend(tree, umap);
1993 }
1994
1995 /* Multiply the partial schedule of the band root node of "tree"
1996  * with the factors in "mv".
1997  */
1998 __isl_give isl_schedule_tree *isl_schedule_tree_band_scale(
1999         __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
2000 {
2001         if (!tree || !mv)
2002                 goto error;
2003         if (tree->type != isl_schedule_node_band)
2004                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2005                         "not a band node", goto error);
2006
2007         tree = isl_schedule_tree_cow(tree);
2008         if (!tree)
2009                 goto error;
2010
2011         tree->band = isl_schedule_band_scale(tree->band, mv);
2012         if (!tree->band)
2013                 return isl_schedule_tree_free(tree);
2014
2015         return tree;
2016 error:
2017         isl_schedule_tree_free(tree);
2018         isl_multi_val_free(mv);
2019         return NULL;
2020 }
2021
2022 /* Divide the partial schedule of the band root node of "tree"
2023  * by the factors in "mv".
2024  */
2025 __isl_give isl_schedule_tree *isl_schedule_tree_band_scale_down(
2026         __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
2027 {
2028         if (!tree || !mv)
2029                 goto error;
2030         if (tree->type != isl_schedule_node_band)
2031                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2032                         "not a band node", goto error);
2033
2034         tree = isl_schedule_tree_cow(tree);
2035         if (!tree)
2036                 goto error;
2037
2038         tree->band = isl_schedule_band_scale_down(tree->band, mv);
2039         if (!tree->band)
2040                 return isl_schedule_tree_free(tree);
2041
2042         return tree;
2043 error:
2044         isl_schedule_tree_free(tree);
2045         isl_multi_val_free(mv);
2046         return NULL;
2047 }
2048
2049 /* Reduce the partial schedule of the band root node of "tree"
2050  * modulo the factors in "mv".
2051  */
2052 __isl_give isl_schedule_tree *isl_schedule_tree_band_mod(
2053         __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
2054 {
2055         if (!tree || !mv)
2056                 goto error;
2057         if (tree->type != isl_schedule_node_band)
2058                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2059                         "not a band node", goto error);
2060
2061         tree = isl_schedule_tree_cow(tree);
2062         if (!tree)
2063                 goto error;
2064
2065         tree->band = isl_schedule_band_mod(tree->band, mv);
2066         if (!tree->band)
2067                 return isl_schedule_tree_free(tree);
2068
2069         return tree;
2070 error:
2071         isl_schedule_tree_free(tree);
2072         isl_multi_val_free(mv);
2073         return NULL;
2074 }
2075
2076 /* Shift the partial schedule of the band root node of "tree" by "shift".
2077  */
2078 __isl_give isl_schedule_tree *isl_schedule_tree_band_shift(
2079         __isl_take isl_schedule_tree *tree,
2080         __isl_take isl_multi_union_pw_aff *shift)
2081 {
2082         if (!tree || !shift)
2083                 goto error;
2084         if (tree->type != isl_schedule_node_band)
2085                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2086                         "not a band node", goto error);
2087
2088         tree = isl_schedule_tree_cow(tree);
2089         if (!tree)
2090                 goto error;
2091
2092         tree->band = isl_schedule_band_shift(tree->band, shift);
2093         if (!tree->band)
2094                 return isl_schedule_tree_free(tree);
2095
2096         return tree;
2097 error:
2098         isl_schedule_tree_free(tree);
2099         isl_multi_union_pw_aff_free(shift);
2100         return NULL;
2101 }
2102
2103 /* Given two trees with sequence roots, replace the child at position
2104  * "pos" of "tree" with the children of "child".
2105  */
2106 __isl_give isl_schedule_tree *isl_schedule_tree_sequence_splice(
2107         __isl_take isl_schedule_tree *tree, int pos,
2108         __isl_take isl_schedule_tree *child)
2109 {
2110         int n;
2111         isl_schedule_tree_list *list1, *list2;
2112
2113         tree = isl_schedule_tree_cow(tree);
2114         if (!tree || !child)
2115                 goto error;
2116         if (isl_schedule_tree_get_type(tree) != isl_schedule_node_sequence)
2117                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2118                         "not a sequence node", goto error);
2119         n = isl_schedule_tree_n_children(tree);
2120         if (pos < 0 || pos >= n)
2121                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2122                         "position out of bounds", goto error);
2123         if (isl_schedule_tree_get_type(child) != isl_schedule_node_sequence)
2124                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2125                         "not a sequence node", goto error);
2126
2127         list1 = isl_schedule_tree_list_copy(tree->children);
2128         list1 = isl_schedule_tree_list_drop(list1, pos, n - pos);
2129         list2 = isl_schedule_tree_list_copy(tree->children);
2130         list2 = isl_schedule_tree_list_drop(list2, 0, pos + 1);
2131         list1 = isl_schedule_tree_list_concat(list1,
2132                                 isl_schedule_tree_list_copy(child->children));
2133         list1 = isl_schedule_tree_list_concat(list1, list2);
2134
2135         isl_schedule_tree_free(tree);
2136         isl_schedule_tree_free(child);
2137         return isl_schedule_tree_from_children(isl_schedule_node_sequence,
2138                                                 list1);
2139 error:
2140         isl_schedule_tree_free(tree);
2141         isl_schedule_tree_free(child);
2142         return NULL;
2143 }
2144
2145 /* Tile the band root node of "tree" with tile sizes "sizes".
2146  *
2147  * We duplicate the band node, change the schedule of one of them
2148  * to the tile schedule and the other to the point schedule and then
2149  * attach the point band as a child to the tile band.
2150  */
2151 __isl_give isl_schedule_tree *isl_schedule_tree_band_tile(
2152         __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *sizes)
2153 {
2154         isl_schedule_tree *child = NULL;
2155
2156         if (!tree || !sizes)
2157                 goto error;
2158         if (tree->type != isl_schedule_node_band)
2159                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2160                         "not a band node", goto error);
2161
2162         child = isl_schedule_tree_copy(tree);
2163         tree = isl_schedule_tree_cow(tree);
2164         child = isl_schedule_tree_cow(child);
2165         if (!tree || !child)
2166                 goto error;
2167
2168         tree->band = isl_schedule_band_tile(tree->band,
2169                                             isl_multi_val_copy(sizes));
2170         if (!tree->band)
2171                 goto error;
2172         child->band = isl_schedule_band_point(child->band, tree->band, sizes);
2173         if (!child->band)
2174                 child = isl_schedule_tree_free(child);
2175
2176         tree = isl_schedule_tree_replace_child(tree, 0, child);
2177
2178         return tree;
2179 error:
2180         isl_schedule_tree_free(child);
2181         isl_schedule_tree_free(tree);
2182         isl_multi_val_free(sizes);
2183         return NULL;
2184 }
2185
2186 /* Given an isolate AST generation option "isolate" for a band of size pos + n,
2187  * return the corresponding option for a band covering the first "pos"
2188  * members.
2189  *
2190  * The input isolate option is of the form
2191  *
2192  *      isolate[[flattened outer bands] -> [pos; n]]
2193  *
2194  * The output isolate option is of the form
2195  *
2196  *      isolate[[flattened outer bands] -> [pos]]
2197  */
2198 static __isl_give isl_set *isolate_initial(__isl_keep isl_set *isolate,
2199         int pos, int n)
2200 {
2201         isl_id *id;
2202         isl_map *map;
2203
2204         isolate = isl_set_copy(isolate);
2205         id = isl_set_get_tuple_id(isolate);
2206         map = isl_set_unwrap(isolate);
2207         map = isl_map_project_out(map, isl_dim_out, pos, n);
2208         isolate = isl_map_wrap(map);
2209         isolate = isl_set_set_tuple_id(isolate, id);
2210
2211         return isolate;
2212 }
2213
2214 /* Given an isolate AST generation option "isolate" for a band of size pos + n,
2215  * return the corresponding option for a band covering the final "n"
2216  * members within a band covering the first "pos" members.
2217  *
2218  * The input isolate option is of the form
2219  *
2220  *      isolate[[flattened outer bands] -> [pos; n]]
2221  *
2222  * The output isolate option is of the form
2223  *
2224  *      isolate[[flattened outer bands; pos] -> [n]]
2225  *
2226  *
2227  * The range is first split into
2228  *
2229  *      isolate[[flattened outer bands] -> [[pos] -> [n]]]
2230  *
2231  * and then the first pos members are moved to the domain
2232  *
2233  *      isolate[[[flattened outer bands] -> [pos]] -> [n]]
2234  *
2235  * after which the domain is flattened to obtain the desired output.
2236  */
2237 static __isl_give isl_set *isolate_final(__isl_keep isl_set *isolate,
2238         int pos, int n)
2239 {
2240         isl_id *id;
2241         isl_space *space;
2242         isl_multi_aff *ma1, *ma2;
2243         isl_map *map;
2244
2245         isolate = isl_set_copy(isolate);
2246         id = isl_set_get_tuple_id(isolate);
2247         map = isl_set_unwrap(isolate);
2248         space = isl_space_range(isl_map_get_space(map));
2249         ma1 = isl_multi_aff_project_out_map(isl_space_copy(space),
2250                                                    isl_dim_set, pos, n);
2251         ma2 = isl_multi_aff_project_out_map(space, isl_dim_set, 0, pos);
2252         ma1 = isl_multi_aff_range_product(ma1, ma2);
2253         map = isl_map_apply_range(map, isl_map_from_multi_aff(ma1));
2254         map = isl_map_uncurry(map);
2255         map = isl_map_flatten_domain(map);
2256         isolate = isl_map_wrap(map);
2257         isolate = isl_set_set_tuple_id(isolate, id);
2258
2259         return isolate;
2260 }
2261
2262 /* Split the band root node of "tree" into two nested band nodes,
2263  * one with the first "pos" dimensions and
2264  * one with the remaining dimensions.
2265  * The tree is itself positioned at schedule depth "depth".
2266  *
2267  * The loop AST generation type options and the isolate option
2268  * are split over the the two band nodes.
2269  */
2270 __isl_give isl_schedule_tree *isl_schedule_tree_band_split(
2271         __isl_take isl_schedule_tree *tree, int pos, int depth)
2272 {
2273         int n;
2274         isl_set *isolate, *tree_isolate, *child_isolate;
2275         isl_schedule_tree *child;
2276
2277         if (!tree)
2278                 return NULL;
2279         if (tree->type != isl_schedule_node_band)
2280                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2281                         "not a band node", return isl_schedule_tree_free(tree));
2282
2283         n = isl_schedule_tree_band_n_member(tree);
2284         if (pos < 0 || pos > n)
2285                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2286                         "position out of bounds",
2287                         return isl_schedule_tree_free(tree));
2288
2289         child = isl_schedule_tree_copy(tree);
2290         tree = isl_schedule_tree_cow(tree);
2291         child = isl_schedule_tree_cow(child);
2292         if (!tree || !child)
2293                 goto error;
2294
2295         isolate = isl_schedule_tree_band_get_ast_isolate_option(tree, depth);
2296         tree_isolate = isolate_initial(isolate, pos, n - pos);
2297         child_isolate = isolate_final(isolate, pos, n - pos);
2298         child->band = isl_schedule_band_drop(child->band, 0, pos);
2299         child->band = isl_schedule_band_replace_ast_build_option(child->band,
2300                                         isl_set_copy(isolate), child_isolate);
2301         tree->band = isl_schedule_band_drop(tree->band, pos, n - pos);
2302         tree->band = isl_schedule_band_replace_ast_build_option(tree->band,
2303                                         isl_set_copy(isolate), tree_isolate);
2304         isl_set_free(isolate);
2305         if (!child->band || !tree->band)
2306                 goto error;
2307
2308         tree = isl_schedule_tree_replace_child(tree, 0, child);
2309
2310         return tree;
2311 error:
2312         isl_schedule_tree_free(child);
2313         isl_schedule_tree_free(tree);
2314         return NULL;
2315 }
2316
2317 /* Attach "tree2" at each of the leaves of "tree1".
2318  *
2319  * If "tree1" does not have any explicit children, then make "tree2"
2320  * its single child.  Otherwise, attach "tree2" to the leaves of
2321  * each of the children of "tree1".
2322  */
2323 __isl_give isl_schedule_tree *isl_schedule_tree_append_to_leaves(
2324         __isl_take isl_schedule_tree *tree1,
2325         __isl_take isl_schedule_tree *tree2)
2326 {
2327         int i, n;
2328
2329         if (!tree1 || !tree2)
2330                 goto error;
2331         n = isl_schedule_tree_n_children(tree1);
2332         if (n == 0) {
2333                 isl_schedule_tree_list *list;
2334                 list = isl_schedule_tree_list_from_schedule_tree(tree2);
2335                 tree1 = isl_schedule_tree_set_children(tree1, list);
2336                 return tree1;
2337         }
2338         for (i = 0; i < n; ++i) {
2339                 isl_schedule_tree *child;
2340
2341                 child = isl_schedule_tree_get_child(tree1, i);
2342                 child = isl_schedule_tree_append_to_leaves(child,
2343                                         isl_schedule_tree_copy(tree2));
2344                 tree1 = isl_schedule_tree_replace_child(tree1, i, child);
2345         }
2346
2347         isl_schedule_tree_free(tree2);
2348         return tree1;
2349 error:
2350         isl_schedule_tree_free(tree1);
2351         isl_schedule_tree_free(tree2);
2352         return NULL;
2353 }
2354
2355 /* Reset the user pointer on all identifiers of parameters and tuples
2356  * in the root of "tree".
2357  */
2358 __isl_give isl_schedule_tree *isl_schedule_tree_reset_user(
2359         __isl_take isl_schedule_tree *tree)
2360 {
2361         if (isl_schedule_tree_is_leaf(tree))
2362                 return tree;
2363
2364         tree = isl_schedule_tree_cow(tree);
2365         if (!tree)
2366                 return NULL;
2367
2368         switch (tree->type) {
2369         case isl_schedule_node_error:
2370                 return isl_schedule_tree_free(tree);
2371         case isl_schedule_node_band:
2372                 tree->band = isl_schedule_band_reset_user(tree->band);
2373                 if (!tree->band)
2374                         return isl_schedule_tree_free(tree);
2375                 break;
2376         case isl_schedule_node_context:
2377                 tree->context = isl_set_reset_user(tree->context);
2378                 if (!tree->context)
2379                         return isl_schedule_tree_free(tree);
2380                 break;
2381         case isl_schedule_node_domain:
2382                 tree->domain = isl_union_set_reset_user(tree->domain);
2383                 if (!tree->domain)
2384                         return isl_schedule_tree_free(tree);
2385                 break;
2386         case isl_schedule_node_expansion:
2387                 tree->contraction =
2388                         isl_union_pw_multi_aff_reset_user(tree->contraction);
2389                 tree->expansion = isl_union_map_reset_user(tree->expansion);
2390                 if (!tree->contraction || !tree->expansion)
2391                         return isl_schedule_tree_free(tree);
2392                 break;
2393         case isl_schedule_node_extension:
2394                 tree->extension = isl_union_map_reset_user(tree->extension);
2395                 if (!tree->extension)
2396                         return isl_schedule_tree_free(tree);
2397                 break;
2398         case isl_schedule_node_filter:
2399                 tree->filter = isl_union_set_reset_user(tree->filter);
2400                 if (!tree->filter)
2401                         return isl_schedule_tree_free(tree);
2402                 break;
2403         case isl_schedule_node_guard:
2404                 tree->guard = isl_set_reset_user(tree->guard);
2405                 if (!tree->guard)
2406                         return isl_schedule_tree_free(tree);
2407                 break;
2408         case isl_schedule_node_leaf:
2409         case isl_schedule_node_mark:
2410         case isl_schedule_node_sequence:
2411         case isl_schedule_node_set:
2412                 break;
2413         }
2414
2415         return tree;
2416 }
2417
2418 /* Align the parameters of the root of "tree" to those of "space".
2419  */
2420 __isl_give isl_schedule_tree *isl_schedule_tree_align_params(
2421         __isl_take isl_schedule_tree *tree, __isl_take isl_space *space)
2422 {
2423         if (!space)
2424                 goto error;
2425
2426         if (isl_schedule_tree_is_leaf(tree)) {
2427                 isl_space_free(space);
2428                 return tree;
2429         }
2430
2431         tree = isl_schedule_tree_cow(tree);
2432         if (!tree)
2433                 goto error;
2434
2435         switch (tree->type) {
2436         case isl_schedule_node_error:
2437                 goto error;
2438         case isl_schedule_node_band:
2439                 tree->band = isl_schedule_band_align_params(tree->band, space);
2440                 if (!tree->band)
2441                         return isl_schedule_tree_free(tree);
2442                 break;
2443         case isl_schedule_node_context:
2444                 tree->context = isl_set_align_params(tree->context, space);
2445                 if (!tree->context)
2446                         return isl_schedule_tree_free(tree);
2447                 break;
2448         case isl_schedule_node_domain:
2449                 tree->domain = isl_union_set_align_params(tree->domain, space);
2450                 if (!tree->domain)
2451                         return isl_schedule_tree_free(tree);
2452                 break;
2453         case isl_schedule_node_expansion:
2454                 tree->contraction =
2455                         isl_union_pw_multi_aff_align_params(tree->contraction,
2456                                                         isl_space_copy(space));
2457                 tree->expansion = isl_union_map_align_params(tree->expansion,
2458                                                                 space);
2459                 if (!tree->contraction || !tree->expansion)
2460                         return isl_schedule_tree_free(tree);
2461                 break;
2462         case isl_schedule_node_extension:
2463                 tree->extension = isl_union_map_align_params(tree->extension,
2464                                                                 space);
2465                 if (!tree->extension)
2466                         return isl_schedule_tree_free(tree);
2467                 break;
2468         case isl_schedule_node_filter:
2469                 tree->filter = isl_union_set_align_params(tree->filter, space);
2470                 if (!tree->filter)
2471                         return isl_schedule_tree_free(tree);
2472                 break;
2473         case isl_schedule_node_guard:
2474                 tree->guard = isl_set_align_params(tree->guard, space);
2475                 if (!tree->guard)
2476                         return isl_schedule_tree_free(tree);
2477                 break;
2478         case isl_schedule_node_leaf:
2479         case isl_schedule_node_mark:
2480         case isl_schedule_node_sequence:
2481         case isl_schedule_node_set:
2482                 isl_space_free(space);
2483                 break;
2484         }
2485
2486         return tree;
2487 error:
2488         isl_space_free(space);
2489         isl_schedule_tree_free(tree);
2490         return NULL;
2491 }
2492
2493 /* Does "tree" involve the iteration domain?
2494  * That is, does it need to be modified
2495  * by isl_schedule_tree_pullback_union_pw_multi_aff?
2496  */
2497 static int involves_iteration_domain(__isl_keep isl_schedule_tree *tree)
2498 {
2499         if (!tree)
2500                 return -1;
2501
2502         switch (tree->type) {
2503         case isl_schedule_node_error:
2504                 return -1;
2505         case isl_schedule_node_band:
2506         case isl_schedule_node_domain:
2507         case isl_schedule_node_expansion:
2508         case isl_schedule_node_extension:
2509         case isl_schedule_node_filter:
2510                 return 1;
2511         case isl_schedule_node_context:
2512         case isl_schedule_node_leaf:
2513         case isl_schedule_node_guard:
2514         case isl_schedule_node_mark:
2515         case isl_schedule_node_sequence:
2516         case isl_schedule_node_set:
2517                 return 0;
2518         }
2519
2520         isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
2521                 "unhandled case", return -1);
2522 }
2523
2524 /* Compute the pullback of the root node of "tree" by the function
2525  * represented by "upma".
2526  * In other words, plug in "upma" in the iteration domains of
2527  * the root node of "tree".
2528  * We currently do not handle expansion nodes.
2529  *
2530  * We first check if the root node involves any iteration domains.
2531  * If so, we handle the specific cases.
2532  */
2533 __isl_give isl_schedule_tree *isl_schedule_tree_pullback_union_pw_multi_aff(
2534         __isl_take isl_schedule_tree *tree,
2535         __isl_take isl_union_pw_multi_aff *upma)
2536 {
2537         int involves;
2538
2539         if (!tree || !upma)
2540                 goto error;
2541
2542         involves = involves_iteration_domain(tree);
2543         if (involves < 0)
2544                 goto error;
2545         if (!involves) {
2546                 isl_union_pw_multi_aff_free(upma);
2547                 return tree;
2548         }
2549
2550         tree = isl_schedule_tree_cow(tree);
2551         if (!tree)
2552                 goto error;
2553
2554         if (tree->type == isl_schedule_node_band) {
2555                 tree->band = isl_schedule_band_pullback_union_pw_multi_aff(
2556                                                             tree->band, upma);
2557                 if (!tree->band)
2558                         return isl_schedule_tree_free(tree);
2559         } else if (tree->type == isl_schedule_node_domain) {
2560                 tree->domain =
2561                         isl_union_set_preimage_union_pw_multi_aff(tree->domain,
2562                                                                         upma);
2563                 if (!tree->domain)
2564                         return isl_schedule_tree_free(tree);
2565         } else if (tree->type == isl_schedule_node_expansion) {
2566                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_unsupported,
2567                         "cannot pullback expansion node", goto error);
2568         } else if (tree->type == isl_schedule_node_extension) {
2569                 tree->extension =
2570                         isl_union_map_preimage_range_union_pw_multi_aff(
2571                             tree->extension, upma);
2572                 if (!tree->extension)
2573                         return isl_schedule_tree_free(tree);
2574         } else if (tree->type == isl_schedule_node_filter) {
2575                 tree->filter =
2576                         isl_union_set_preimage_union_pw_multi_aff(tree->filter,
2577                                                                         upma);
2578                 if (!tree->filter)
2579                         return isl_schedule_tree_free(tree);
2580         }
2581
2582         return tree;
2583 error:
2584         isl_union_pw_multi_aff_free(upma);
2585         isl_schedule_tree_free(tree);
2586         return NULL;
2587 }
2588
2589 /* Compute the gist of the band tree root with respect to "context".
2590  */
2591 __isl_give isl_schedule_tree *isl_schedule_tree_band_gist(
2592         __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *context)
2593 {
2594         if (!tree)
2595                 return NULL;
2596         if (tree->type != isl_schedule_node_band)
2597                 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2598                         "not a band node", goto error);
2599         tree = isl_schedule_tree_cow(tree);
2600         if (!tree)
2601                 goto error;
2602
2603         tree->band = isl_schedule_band_gist(tree->band, context);
2604         if (!tree->band)
2605                 return isl_schedule_tree_free(tree);
2606         return tree;
2607 error:
2608         isl_union_set_free(context);
2609         isl_schedule_tree_free(tree);
2610         return NULL;
2611 }
2612
2613 /* Are any members in "band" marked coincident?
2614  */
2615 static int any_coincident(__isl_keep isl_schedule_band *band)
2616 {
2617         int i, n;
2618
2619         n = isl_schedule_band_n_member(band);
2620         for (i = 0; i < n; ++i)
2621                 if (isl_schedule_band_member_get_coincident(band, i))
2622                         return 1;
2623
2624         return 0;
2625 }
2626
2627 /* Print the band node "band" to "p".
2628  *
2629  * The permutable and coincident properties are only printed if they
2630  * are different from the defaults.
2631  * The coincident property is always printed in YAML flow style.
2632  */
2633 static __isl_give isl_printer *print_tree_band(__isl_take isl_printer *p,
2634         __isl_keep isl_schedule_band *band)
2635 {
2636         isl_union_set *options;
2637         int empty;
2638
2639         p = isl_printer_print_str(p, "schedule");
2640         p = isl_printer_yaml_next(p);
2641         p = isl_printer_print_str(p, "\"");
2642         p = isl_printer_print_multi_union_pw_aff(p, band->mupa);
2643         p = isl_printer_print_str(p, "\"");
2644         if (isl_schedule_band_get_permutable(band)) {
2645                 p = isl_printer_yaml_next(p);
2646                 p = isl_printer_print_str(p, "permutable");
2647                 p = isl_printer_yaml_next(p);
2648                 p = isl_printer_print_int(p, 1);
2649         }
2650         if (any_coincident(band)) {
2651                 int i, n;
2652                 int style;
2653
2654                 p = isl_printer_yaml_next(p);
2655                 p = isl_printer_print_str(p, "coincident");
2656                 p = isl_printer_yaml_next(p);
2657                 style = isl_printer_get_yaml_style(p);
2658                 p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_FLOW);
2659                 p = isl_printer_yaml_start_sequence(p);
2660                 n = isl_schedule_band_n_member(band);
2661                 for (i = 0; i < n; ++i) {
2662                         p = isl_printer_print_int(p,
2663                             isl_schedule_band_member_get_coincident(band, i));
2664                         p = isl_printer_yaml_next(p);
2665                 }
2666                 p = isl_printer_yaml_end_sequence(p);
2667                 p = isl_printer_set_yaml_style(p, style);
2668         }
2669         options = isl_schedule_band_get_ast_build_options(band);
2670         empty = isl_union_set_is_empty(options);
2671         if (empty < 0)
2672                 p = isl_printer_free(p);
2673         if (!empty) {
2674                 p = isl_printer_yaml_next(p);
2675                 p = isl_printer_print_str(p, "options");
2676                 p = isl_printer_yaml_next(p);
2677                 p = isl_printer_print_str(p, "\"");
2678                 p = isl_printer_print_union_set(p, options);
2679                 p = isl_printer_print_str(p, "\"");
2680         }
2681         isl_union_set_free(options);
2682
2683         return p;
2684 }
2685
2686 /* Print "tree" to "p".
2687  *
2688  * If "n_ancestor" is non-negative, then "child_pos" contains the child
2689  * positions of a descendant of the current node that should be marked
2690  * (by the comment "YOU ARE HERE").  In particular, if "n_ancestor"
2691  * is zero, then the current node should be marked.
2692  * The marking is only printed in YAML block format.
2693  *
2694  * Implicit leaf nodes are not printed, except if they correspond
2695  * to the node that should be marked.
2696  */
2697 __isl_give isl_printer *isl_printer_print_schedule_tree_mark(
2698         __isl_take isl_printer *p, __isl_keep isl_schedule_tree *tree,
2699         int n_ancestor, int *child_pos)
2700 {
2701         int i, n;
2702         int sequence = 0;
2703         int block;
2704
2705         block = isl_printer_get_yaml_style(p) == ISL_YAML_STYLE_BLOCK;
2706
2707         p = isl_printer_yaml_start_mapping(p);
2708         if (n_ancestor == 0 && block) {
2709                 p = isl_printer_print_str(p, "# YOU ARE HERE");
2710                 p = isl_printer_end_line(p);
2711                 p = isl_printer_start_line(p);
2712         }
2713         switch (tree->type) {
2714         case isl_schedule_node_error:
2715                 p = isl_printer_print_str(p, "ERROR");
2716                 break;
2717         case isl_schedule_node_leaf:
2718                 p = isl_printer_print_str(p, "leaf");
2719                 break;
2720         case isl_schedule_node_sequence:
2721                 p = isl_printer_print_str(p, "sequence");
2722                 sequence = 1;
2723                 break;
2724         case isl_schedule_node_set:
2725                 p = isl_printer_print_str(p, "set");
2726                 sequence = 1;
2727                 break;
2728         case isl_schedule_node_context:
2729                 p = isl_printer_print_str(p, "context");
2730                 p = isl_printer_yaml_next(p);
2731                 p = isl_printer_print_str(p, "\"");
2732                 p = isl_printer_print_set(p, tree->context);
2733                 p = isl_printer_print_str(p, "\"");
2734                 break;
2735         case isl_schedule_node_domain:
2736                 p = isl_printer_print_str(p, "domain");
2737                 p = isl_printer_yaml_next(p);
2738                 p = isl_printer_print_str(p, "\"");
2739                 p = isl_printer_print_union_set(p, tree->domain);
2740                 p = isl_printer_print_str(p, "\"");
2741                 break;
2742         case isl_schedule_node_expansion:
2743                 p = isl_printer_print_str(p, "contraction");
2744                 p = isl_printer_yaml_next(p);
2745                 p = isl_printer_print_str(p, "\"");
2746                 p = isl_printer_print_union_pw_multi_aff(p, tree->contraction);
2747                 p = isl_printer_print_str(p, "\"");
2748                 p = isl_printer_yaml_next(p);
2749                 p = isl_printer_print_str(p, "expansion");
2750                 p = isl_printer_yaml_next(p);
2751                 p = isl_printer_print_str(p, "\"");
2752                 p = isl_printer_print_union_map(p, tree->expansion);
2753                 p = isl_printer_print_str(p, "\"");
2754                 break;
2755         case isl_schedule_node_extension:
2756                 p = isl_printer_print_str(p, "extension");
2757                 p = isl_printer_yaml_next(p);
2758                 p = isl_printer_print_str(p, "\"");
2759                 p = isl_printer_print_union_map(p, tree->extension);
2760                 p = isl_printer_print_str(p, "\"");
2761                 break;
2762         case isl_schedule_node_filter:
2763                 p = isl_printer_print_str(p, "filter");
2764                 p = isl_printer_yaml_next(p);
2765                 p = isl_printer_print_str(p, "\"");
2766                 p = isl_printer_print_union_set(p, tree->filter);
2767                 p = isl_printer_print_str(p, "\"");
2768                 break;
2769         case isl_schedule_node_guard:
2770                 p = isl_printer_print_str(p, "guard");
2771                 p = isl_printer_yaml_next(p);
2772                 p = isl_printer_print_str(p, "\"");
2773                 p = isl_printer_print_set(p, tree->guard);
2774                 p = isl_printer_print_str(p, "\"");
2775                 break;
2776         case isl_schedule_node_mark:
2777                 p = isl_printer_print_str(p, "mark");
2778                 p = isl_printer_yaml_next(p);
2779                 p = isl_printer_print_str(p, "\"");
2780                 p = isl_printer_print_str(p, isl_id_get_name(tree->mark));
2781                 p = isl_printer_print_str(p, "\"");
2782                 break;
2783         case isl_schedule_node_band:
2784                 p = print_tree_band(p, tree->band);
2785                 break;
2786         }
2787         p = isl_printer_yaml_next(p);
2788
2789         if (!tree->children) {
2790                 if (n_ancestor > 0 && block) {
2791                         isl_schedule_tree *leaf;
2792
2793                         p = isl_printer_print_str(p, "child");
2794                         p = isl_printer_yaml_next(p);
2795                         leaf = isl_schedule_tree_leaf(isl_printer_get_ctx(p));
2796                         p = isl_printer_print_schedule_tree_mark(p,
2797                                         leaf, 0, NULL);
2798                         isl_schedule_tree_free(leaf);
2799                         p = isl_printer_yaml_next(p);
2800                 }
2801                 return isl_printer_yaml_end_mapping(p);
2802         }
2803
2804         if (sequence) {
2805                 p = isl_printer_yaml_start_sequence(p);
2806         } else {
2807                 p = isl_printer_print_str(p, "child");
2808                 p = isl_printer_yaml_next(p);
2809         }
2810
2811         n = isl_schedule_tree_list_n_schedule_tree(tree->children);
2812         for (i = 0; i < n; ++i) {
2813                 isl_schedule_tree *t;
2814
2815                 t = isl_schedule_tree_get_child(tree, i);
2816                 if (n_ancestor > 0 && child_pos[0] == i)
2817                         p = isl_printer_print_schedule_tree_mark(p, t,
2818                                                 n_ancestor - 1, child_pos + 1);
2819                 else
2820                         p = isl_printer_print_schedule_tree_mark(p, t,
2821                                                 -1, NULL);
2822                 isl_schedule_tree_free(t);
2823
2824                 p = isl_printer_yaml_next(p);
2825         }
2826
2827         if (sequence)
2828                 p = isl_printer_yaml_end_sequence(p);
2829         p = isl_printer_yaml_end_mapping(p);
2830
2831         return p;
2832 }
2833
2834 /* Print "tree" to "p".
2835  */
2836 __isl_give isl_printer *isl_printer_print_schedule_tree(
2837         __isl_take isl_printer *p, __isl_keep isl_schedule_tree *tree)
2838 {
2839         return isl_printer_print_schedule_tree_mark(p, tree, -1, NULL);
2840 }
2841
2842 void isl_schedule_tree_dump(__isl_keep isl_schedule_tree *tree)
2843 {
2844         isl_ctx *ctx;
2845         isl_printer *printer;
2846
2847         if (!tree)
2848                 return;
2849
2850         ctx = isl_schedule_tree_get_ctx(tree);
2851         printer = isl_printer_to_file(ctx, stderr);
2852         printer = isl_printer_set_yaml_style(printer, ISL_YAML_STYLE_BLOCK);
2853         printer = isl_printer_print_schedule_tree(printer, tree);
2854
2855         isl_printer_free(printer);
2856 }