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