isl_schedule_tree.c

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