2907 lines · c
1/*2 * Copyright 2013-2014 Ecole Normale Superieure3 * Copyright 2014 INRIA Rocquencourt4 * Copyright 2016 INRIA Paris5 *6 * Use of this software is governed by the MIT license7 *8 * Written by Sven Verdoolaege,9 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France10 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,11 * B.P. 105 - 78153 Le Chesnay, France12 * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12,13 * CS 42112, 75589 Paris Cedex 12, France14 */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 EL24#define EL isl_schedule_tree25 26#include <isl_list_templ.h>27 28#undef EL_BASE29#define EL_BASE schedule_tree30 31#include <isl_list_templ.c>32 33/* Is "tree" the leaf of a schedule tree?34 */35int 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 and42 * 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 */47static __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 only148 * 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;251error: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;278error: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;302error:303 isl_union_set_free(domain);304 return NULL;305}306 307/* Create a new expansion schedule tree with the given contraction and308 * 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;329error: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 and336 * 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;358error: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;382error: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;409error:410 isl_set_free(guard);411 return NULL;412}413 414/* Create a new mark schedule tree with the given mark identifier and415 * 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;434error:435 isl_id_free(mark);436 return NULL;437}438 439/* Does "tree" have any node that depends on its position440 * in the complete schedule tree?441 */442isl_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 complete449 * 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 */453int 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 node482 * itself in anchored and the anchored fields of the children.483 *484 * This function should be called whenever the children of a tree node485 * 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 or519 * 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;540error: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 children546 * "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);579error: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 children586 * "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 children599 * "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 */612isl_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_error618 * on error.619 */620enum 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 */628isl_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 */710int 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 are720 * no children (except for the implicit leaves).721 */722isl_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" and746 * 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 explicitly804 * recorded in the list of children. Instead, the list of children805 * (which is assumed to have only one element) is removed.806 * Note that the children of set and sequence nodes are always807 * 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 else838 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;846error: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;864error: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 and883 * 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 and895 * 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 and907 * 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 and921 * 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 two935 * 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;979error: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 and986 * 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 and998 * 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 */1011isl_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 root1024 * marked coincident?1025 */1026isl_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 not1040 * 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 */1066isl_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 root1117 * 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;1134error: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;1172error: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 member1179 * of the band tree root at position "pos".1180 */1181enum 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 root1195 * 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 member1218 * of the band tree root at position "pos" for the isolated part.1219 */1220enum 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 root1235 * at position "pos" for the isolated part to "type".1236 */1237__isl_give isl_schedule_tree *1238isl_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 itself1275 * 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;1299error: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;1368error: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 *1408isl_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;1427error: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;1465error: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;1503error: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 */1541static 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 and1553 * 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 */1557static 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" and1575 * return the result.1576 */1577static __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 first1602 * descendant with schedule information?1603 * That is, is it impossible to derive any information about1604 * the iteration domain from this node?1605 *1606 * We do not want to skip leaf or error nodes because there is1607 * no point in looking any deeper from these nodes.1608 * We can only extract partial iteration domain information1609 * from an extension node, but extension nodes are not supported1610 * by the caller and it will error out on them.1611 */1612static 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 schedule1642 * 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 1663static __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 schedule1667 * of the (single) child of "tree", if any.1668 *1669 * If "tree" does not have any descendants (apart from those that1670 * do not carry any schedule information), then we simply return "outer".1671 * Otherwise, we extend the schedule map "outer" with the subtree schedule1672 * of the single child.1673 */1674static __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 */1695static __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 schedule1712 * of a set or sequence node.1713 *1714 * The schedule for the set or sequence node itself is composed of1715 * pieces of the form1716 *1717 * filter -> []1718 *1719 * or1720 *1721 * filter -> [index]1722 *1723 * The first form is used if there is only a single child or1724 * if the current node is a set node and the schedule_separate_components1725 * option is not set.1726 *1727 * Each of the pieces above is extended with the subtree schedule of1728 * the child of the corresponding filter, if any, padded with zeros1729 * to ensure that all pieces have the same range dimension.1730 */1731static __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 extend1825 * the schedule map in subtree_schedule_extend_from_children.1826 * Otherwise, we extend the schedule map with the partial schedule1827 * corresponding to the root of the tree and then continue with1828 * 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 */1832static __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 1895static __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 */1902static __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 node1935 * would not be skipped by isl_schedule_tree_first_schedule_descendant1936 * and that it is not a leaf node.1937 */1938static __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 schedule2007 * information, i.e., a node that would not be skipped by2008 * isl_schedule_tree_first_schedule_descendant and that is not a leaf.2009 *2010 * If the tree contains any expansions, then the returned subtree2011 * 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 based2015 * on the domain information in the root node and then extend it2016 * 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;2050error: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;2077error: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;2104error: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;2131error: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 position2138 * "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);2175error: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 them2184 * to the tile schedule and the other to the point schedule and then2185 * 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;2215error: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 form2227 *2228 * isolate[[flattened outer bands] -> [pos; n]]2229 *2230 * The output isolate option is of the form2231 *2232 * isolate[[flattened outer bands] -> [pos]]2233 */2234static __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 form2255 *2256 * isolate[[flattened outer bands] -> [pos; n]]2257 *2258 * The output isolate option is of the form2259 *2260 * isolate[[flattened outer bands; pos] -> [n]]2261 *2262 *2263 * The range is first split into2264 *2265 * isolate[[flattened outer bands] -> [[pos] -> [n]]]2266 *2267 * and then the first pos members are moved to the domain2268 *2269 * isolate[[[flattened outer bands] -> [pos]] -> [n]]2270 *2271 * after which the domain is flattened to obtain the desired output.2272 */2273static __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 and2300 * 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 option2304 * 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;2349error: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 of2359 * 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;2388error: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 tuples2395 * 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;2526error: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 modified2534 * by isl_schedule_tree_pullback_union_pw_multi_aff?2535 */2536static 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 function2564 * represented by "upma".2565 * In other words, plug in "upma" in the iteration domains of2566 * 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;2622error: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;2646error: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 */2654static 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 they2676 * are different from the defaults.2677 * The coincident property is always printed in YAML flow style.2678 */2679static __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 BASE2740#define BASE str2741#define isl_str const char2742#include "print_yaml_field_templ.c"2743 2744#undef BASE2745#define BASE set2746#include "print_yaml_field_templ.c"2747 2748#undef BASE2749#define BASE union_set2750#include "print_yaml_field_templ.c"2751 2752#undef BASE2753#define BASE union_map2754#include "print_yaml_field_templ.c"2755 2756#undef BASE2757#define BASE union_pw_multi_aff2758#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 child2763 * positions of a descendant of the current node that should be marked2764 * (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 correspond2769 * 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 else2870 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 2892void 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