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