isl_schedule_tree.c

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