685 lines · c
1/*2 * Copyright 2011 INRIA Saclay3 * Copyright 2012-2014 Ecole Normale Superieure4 * Copyright 2016 Sven Verdoolaege5 *6 * Use of this software is governed by the MIT license7 *8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,10 * 91893 Orsay, France11 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France12 */13 14#include <isl/ctx.h>15#include <isl/val.h>16#include <isl_aff_private.h>17#include <isl/map.h>18#include <isl/set.h>19#include <isl/schedule.h>20#include <isl/schedule_node.h>21#include <isl_sort.h>22#include <isl/printer.h>23#include <isl_schedule_private.h>24#include <isl_schedule_tree.h>25#include <isl_schedule_node_private.h>26 27/* Return a schedule encapsulating the given schedule tree.28 *29 * We currently only allow schedule trees with a domain or extension as root.30 *31 * The leaf field is initialized as a leaf node so that it can be32 * used to represent leaves in the constructed schedule.33 * The reference count is set to -1 since the isl_schedule_tree34 * should never be freed. It is up to the (internal) users of35 * these leaves to ensure that they are only used while the schedule36 * is still alive.37 */38__isl_give isl_schedule *isl_schedule_from_schedule_tree(isl_ctx *ctx,39 __isl_take isl_schedule_tree *tree)40{41 enum isl_schedule_node_type type;42 isl_schedule *schedule;43 44 if (!tree)45 return NULL;46 type = isl_schedule_tree_get_type(tree);47 if (type != isl_schedule_node_domain &&48 type != isl_schedule_node_extension)49 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_unsupported,50 "root of schedule tree should be a domain or extension",51 goto error);52 53 schedule = isl_calloc_type(ctx, isl_schedule);54 if (!schedule)55 goto error;56 57 schedule->ref = 1;58 schedule->root = tree;59 schedule->leaf = isl_schedule_tree_leaf(ctx);60 61 if (!schedule->leaf)62 return isl_schedule_free(schedule);63 return schedule;64error:65 isl_schedule_tree_free(tree);66 return NULL;67}68 69/* Return a pointer to a schedule with as single node70 * a domain node with the given domain.71 */72__isl_give isl_schedule *isl_schedule_from_domain(73 __isl_take isl_union_set *domain)74{75 isl_ctx *ctx;76 isl_schedule_tree *tree;77 78 ctx = isl_union_set_get_ctx(domain);79 tree = isl_schedule_tree_from_domain(domain);80 return isl_schedule_from_schedule_tree(ctx, tree);81}82 83/* Return a pointer to a schedule with as single node84 * a domain node with an empty domain.85 */86__isl_give isl_schedule *isl_schedule_empty(__isl_take isl_space *space)87{88 return isl_schedule_from_domain(isl_union_set_empty(space));89}90 91/* Return a new reference to "sched".92 */93__isl_give isl_schedule *isl_schedule_copy(__isl_keep isl_schedule *sched)94{95 if (!sched)96 return NULL;97 98 sched->ref++;99 return sched;100}101 102/* Return an isl_schedule that is equal to "schedule" and that has only103 * a single reference.104 */105__isl_give isl_schedule *isl_schedule_cow(__isl_take isl_schedule *schedule)106{107 isl_ctx *ctx;108 isl_schedule_tree *tree;109 110 if (!schedule)111 return NULL;112 if (schedule->ref == 1)113 return schedule;114 115 ctx = isl_schedule_get_ctx(schedule);116 schedule->ref--;117 tree = isl_schedule_tree_copy(schedule->root);118 return isl_schedule_from_schedule_tree(ctx, tree);119}120 121__isl_null isl_schedule *isl_schedule_free(__isl_take isl_schedule *sched)122{123 if (!sched)124 return NULL;125 126 if (--sched->ref > 0)127 return NULL;128 129 isl_schedule_tree_free(sched->root);130 isl_schedule_tree_free(sched->leaf);131 free(sched);132 return NULL;133}134 135/* Replace the root of "schedule" by "tree".136 */137__isl_give isl_schedule *isl_schedule_set_root(138 __isl_take isl_schedule *schedule, __isl_take isl_schedule_tree *tree)139{140 if (!schedule || !tree)141 goto error;142 if (schedule->root == tree) {143 isl_schedule_tree_free(tree);144 return schedule;145 }146 147 schedule = isl_schedule_cow(schedule);148 if (!schedule)149 goto error;150 isl_schedule_tree_free(schedule->root);151 schedule->root = tree;152 153 return schedule;154error:155 isl_schedule_free(schedule);156 isl_schedule_tree_free(tree);157 return NULL;158}159 160isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule)161{162 return schedule ? isl_schedule_tree_get_ctx(schedule->leaf) : NULL;163}164 165/* Return a pointer to the leaf of "schedule".166 */167__isl_keep isl_schedule_tree *isl_schedule_peek_leaf(168 __isl_keep isl_schedule *schedule)169{170 return schedule ? schedule->leaf : NULL;171}172 173/* Are "schedule1" and "schedule2" obviously equal to each other?174 */175isl_bool isl_schedule_plain_is_equal(__isl_keep isl_schedule *schedule1,176 __isl_keep isl_schedule *schedule2)177{178 if (!schedule1 || !schedule2)179 return isl_bool_error;180 if (schedule1 == schedule2)181 return isl_bool_true;182 return isl_schedule_tree_plain_is_equal(schedule1->root,183 schedule2->root);184}185 186/* Return the (parameter) space of the schedule, i.e., the space187 * of the root domain.188 */189__isl_give isl_space *isl_schedule_get_space(190 __isl_keep isl_schedule *schedule)191{192 enum isl_schedule_node_type type;193 isl_space *space;194 isl_union_set *domain;195 196 if (!schedule)197 return NULL;198 type = isl_schedule_tree_get_type(schedule->root);199 if (type != isl_schedule_node_domain)200 isl_die(isl_schedule_get_ctx(schedule), isl_error_internal,201 "root node not a domain node", return NULL);202 203 domain = isl_schedule_tree_domain_get_domain(schedule->root);204 space = isl_union_set_get_space(domain);205 isl_union_set_free(domain);206 207 return space;208}209 210/* Return a pointer to the root of "schedule".211 */212__isl_give isl_schedule_node *isl_schedule_get_root(213 __isl_keep isl_schedule *schedule)214{215 isl_ctx *ctx;216 isl_schedule_tree *tree;217 isl_schedule_tree_list *ancestors;218 219 if (!schedule)220 return NULL;221 222 ctx = isl_schedule_get_ctx(schedule);223 tree = isl_schedule_tree_copy(schedule->root);224 schedule = isl_schedule_copy(schedule);225 ancestors = isl_schedule_tree_list_alloc(ctx, 0);226 return isl_schedule_node_alloc(schedule, tree, ancestors, NULL);227}228 229/* Return the domain of the root domain node of "schedule".230 */231__isl_give isl_union_set *isl_schedule_get_domain(232 __isl_keep isl_schedule *schedule)233{234 if (!schedule)235 return NULL;236 return isl_schedule_tree_domain_get_domain(schedule->root);237}238 239/* Traverse all nodes of "sched" in depth first preorder.240 *241 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.242 * If "fn" returns 0 on any of the nodes, then the subtree rooted243 * at that node is skipped.244 *245 * Return 0 on success and -1 on failure.246 */247isl_stat isl_schedule_foreach_schedule_node_top_down(248 __isl_keep isl_schedule *sched,249 isl_bool (*fn)(__isl_keep isl_schedule_node *node, void *user),250 void *user)251{252 isl_schedule_node *node;253 isl_stat r;254 255 if (!sched)256 return isl_stat_error;257 258 node = isl_schedule_get_root(sched);259 r = isl_schedule_node_foreach_descendant_top_down(node, fn, user);260 isl_schedule_node_free(node);261 262 return r;263}264 265/* Traverse the node of "sched" in depth first postorder,266 * allowing the user to modify the visited node.267 * The traversal continues from the node returned by the callback function.268 * It is the responsibility of the user to ensure that this does not269 * lead to an infinite loop. It is safest to always return a pointer270 * to the same position (same ancestors and child positions) as the input node.271 */272__isl_give isl_schedule *isl_schedule_map_schedule_node_bottom_up(273 __isl_take isl_schedule *schedule,274 __isl_give isl_schedule_node *(*fn)(275 __isl_take isl_schedule_node *node, void *user), void *user)276{277 isl_schedule_node *node;278 279 node = isl_schedule_get_root(schedule);280 isl_schedule_free(schedule);281 282 node = isl_schedule_node_map_descendant_bottom_up(node, fn, user);283 schedule = isl_schedule_node_get_schedule(node);284 isl_schedule_node_free(node);285 286 return schedule;287}288 289/* Wrapper around isl_schedule_node_reset_user for use as290 * an isl_schedule_map_schedule_node_bottom_up callback.291 */292static __isl_give isl_schedule_node *reset_user(293 __isl_take isl_schedule_node *node, void *user)294{295 return isl_schedule_node_reset_user(node);296}297 298/* Reset the user pointer on all identifiers of parameters and tuples299 * in the schedule "schedule".300 */301__isl_give isl_schedule *isl_schedule_reset_user(302 __isl_take isl_schedule *schedule)303{304 return isl_schedule_map_schedule_node_bottom_up(schedule, &reset_user,305 NULL);306}307 308/* Wrapper around isl_schedule_node_align_params for use as309 * an isl_schedule_map_schedule_node_bottom_up callback.310 */311static __isl_give isl_schedule_node *align_params(312 __isl_take isl_schedule_node *node, void *user)313{314 isl_space *space = user;315 316 return isl_schedule_node_align_params(node, isl_space_copy(space));317}318 319/* Align the parameters of all nodes in schedule "schedule"320 * to those of "space".321 */322__isl_give isl_schedule *isl_schedule_align_params(323 __isl_take isl_schedule *schedule, __isl_take isl_space *space)324{325 schedule = isl_schedule_map_schedule_node_bottom_up(schedule,326 &align_params, space);327 isl_space_free(space);328 return schedule;329}330 331/* Wrapper around isl_schedule_node_pullback_union_pw_multi_aff for use as332 * an isl_schedule_map_schedule_node_bottom_up callback.333 */334static __isl_give isl_schedule_node *pullback_upma(335 __isl_take isl_schedule_node *node, void *user)336{337 isl_union_pw_multi_aff *upma = user;338 339 return isl_schedule_node_pullback_union_pw_multi_aff(node,340 isl_union_pw_multi_aff_copy(upma));341}342 343/* Compute the pullback of "schedule" by the function represented by "upma".344 * In other words, plug in "upma" in the iteration domains of "schedule".345 *346 * The schedule tree is not allowed to contain any expansion nodes.347 */348__isl_give isl_schedule *isl_schedule_pullback_union_pw_multi_aff(349 __isl_take isl_schedule *schedule,350 __isl_take isl_union_pw_multi_aff *upma)351{352 schedule = isl_schedule_map_schedule_node_bottom_up(schedule,353 &pullback_upma, upma);354 isl_union_pw_multi_aff_free(upma);355 return schedule;356}357 358/* Expand the schedule "schedule" by extending all leaves359 * with an expansion node with as subtree the tree of "expansion".360 * The expansion of the expansion node is determined by "contraction"361 * and the domain of "expansion". That is, the domain of "expansion"362 * is contracted according to "contraction".363 *364 * Call isl_schedule_node_expand after extracting the required365 * information from "expansion".366 */367__isl_give isl_schedule *isl_schedule_expand(__isl_take isl_schedule *schedule,368 __isl_take isl_union_pw_multi_aff *contraction,369 __isl_take isl_schedule *expansion)370{371 isl_union_set *domain;372 isl_schedule_node *node;373 isl_schedule_tree *tree;374 375 domain = isl_schedule_get_domain(expansion);376 377 node = isl_schedule_get_root(expansion);378 node = isl_schedule_node_child(node, 0);379 tree = isl_schedule_node_get_tree(node);380 isl_schedule_node_free(node);381 isl_schedule_free(expansion);382 383 node = isl_schedule_get_root(schedule);384 isl_schedule_free(schedule);385 node = isl_schedule_node_expand(node, contraction, domain, tree);386 schedule = isl_schedule_node_get_schedule(node);387 isl_schedule_node_free(node);388 389 return schedule;390}391 392/* Intersect the domain of the schedule "schedule" with "domain".393 * The root of "schedule" is required to be a domain node.394 */395__isl_give isl_schedule *isl_schedule_intersect_domain(396 __isl_take isl_schedule *schedule, __isl_take isl_union_set *domain)397{398 enum isl_schedule_node_type root_type;399 isl_schedule_node *node;400 401 if (!schedule || !domain)402 goto error;403 404 root_type = isl_schedule_tree_get_type(schedule->root);405 if (root_type != isl_schedule_node_domain)406 isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,407 "root node must be a domain node", goto error);408 409 node = isl_schedule_get_root(schedule);410 isl_schedule_free(schedule);411 node = isl_schedule_node_domain_intersect_domain(node, domain);412 schedule = isl_schedule_node_get_schedule(node);413 isl_schedule_node_free(node);414 415 return schedule;416error:417 isl_schedule_free(schedule);418 isl_union_set_free(domain);419 return NULL;420}421 422/* Replace the domain of the schedule "schedule" with the gist423 * of the original domain with respect to the parameter domain "context".424 */425__isl_give isl_schedule *isl_schedule_gist_domain_params(426 __isl_take isl_schedule *schedule, __isl_take isl_set *context)427{428 enum isl_schedule_node_type root_type;429 isl_schedule_node *node;430 431 if (!schedule || !context)432 goto error;433 434 root_type = isl_schedule_tree_get_type(schedule->root);435 if (root_type != isl_schedule_node_domain)436 isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,437 "root node must be a domain node", goto error);438 439 node = isl_schedule_get_root(schedule);440 isl_schedule_free(schedule);441 node = isl_schedule_node_domain_gist_params(node, context);442 schedule = isl_schedule_node_get_schedule(node);443 isl_schedule_node_free(node);444 445 return schedule;446error:447 isl_schedule_free(schedule);448 isl_set_free(context);449 return NULL;450}451 452/* Return an isl_union_map representation of the schedule. In particular,453 * return an isl_union_map corresponding to the subtree schedule of the child454 * of the root domain node. That is, we do not intersect the domain455 * of the returned isl_union_map with the domain constraints.456 */457__isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)458{459 enum isl_schedule_node_type type;460 isl_schedule_node *node;461 isl_union_map *umap;462 463 if (!sched)464 return NULL;465 type = isl_schedule_tree_get_type(sched->root);466 if (type != isl_schedule_node_domain)467 isl_die(isl_schedule_get_ctx(sched), isl_error_internal,468 "root node not a domain node", return NULL);469 470 node = isl_schedule_get_root(sched);471 node = isl_schedule_node_child(node, 0);472 umap = isl_schedule_node_get_subtree_schedule_union_map(node);473 isl_schedule_node_free(node);474 475 return umap;476}477 478/* Insert a band node with partial schedule "partial" between the domain479 * root node of "schedule" and its single child.480 * Return a pointer to the updated schedule.481 *482 * If any of the nodes in the tree depend on the set of outer band nodes483 * then we refuse to insert the band node.484 */485__isl_give isl_schedule *isl_schedule_insert_partial_schedule(486 __isl_take isl_schedule *schedule,487 __isl_take isl_multi_union_pw_aff *partial)488{489 isl_schedule_node *node;490 int anchored;491 492 node = isl_schedule_get_root(schedule);493 isl_schedule_free(schedule);494 if (!node)495 goto error;496 if (isl_schedule_node_get_type(node) != isl_schedule_node_domain)497 isl_die(isl_schedule_node_get_ctx(node), isl_error_internal,498 "root node not a domain node", goto error);499 500 node = isl_schedule_node_child(node, 0);501 anchored = isl_schedule_node_is_subtree_anchored(node);502 if (anchored < 0)503 goto error;504 if (anchored)505 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,506 "cannot insert band node in anchored subtree",507 goto error);508 node = isl_schedule_node_insert_partial_schedule(node, partial);509 510 schedule = isl_schedule_node_get_schedule(node);511 isl_schedule_node_free(node);512 513 return schedule;514error:515 isl_schedule_node_free(node);516 isl_multi_union_pw_aff_free(partial);517 return NULL;518}519 520/* Insert a context node with constraints "context" between the domain521 * root node of "schedule" and its single child.522 * Return a pointer to the updated schedule.523 */524__isl_give isl_schedule *isl_schedule_insert_context(525 __isl_take isl_schedule *schedule, __isl_take isl_set *context)526{527 isl_schedule_node *node;528 529 node = isl_schedule_get_root(schedule);530 isl_schedule_free(schedule);531 node = isl_schedule_node_child(node, 0);532 node = isl_schedule_node_insert_context(node, context);533 schedule = isl_schedule_node_get_schedule(node);534 isl_schedule_node_free(node);535 536 return schedule;537}538 539/* Insert a guard node with constraints "guard" between the domain540 * root node of "schedule" and its single child.541 * Return a pointer to the updated schedule.542 */543__isl_give isl_schedule *isl_schedule_insert_guard(544 __isl_take isl_schedule *schedule, __isl_take isl_set *guard)545{546 isl_schedule_node *node;547 548 node = isl_schedule_get_root(schedule);549 isl_schedule_free(schedule);550 node = isl_schedule_node_child(node, 0);551 node = isl_schedule_node_insert_guard(node, guard);552 schedule = isl_schedule_node_get_schedule(node);553 isl_schedule_node_free(node);554 555 return schedule;556}557 558/* Return a tree with as top-level node a filter corresponding to "filter" and559 * as child, the (single) child of "tree".560 * However, if this single child is of type "type", then the filter is inserted561 * in the children of this single child instead.562 */563static __isl_give isl_schedule_tree *insert_filter_in_child_of_type(564 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter,565 enum isl_schedule_node_type type)566{567 if (!isl_schedule_tree_has_children(tree)) {568 isl_schedule_tree_free(tree);569 return isl_schedule_tree_from_filter(filter);570 } else {571 tree = isl_schedule_tree_child(tree, 0);572 }573 574 if (isl_schedule_tree_get_type(tree) == type)575 tree = isl_schedule_tree_children_insert_filter(tree, filter);576 else577 tree = isl_schedule_tree_insert_filter(tree, filter);578 579 return tree;580}581 582/* Construct a schedule that combines the schedules "schedule1" and "schedule2"583 * with a top-level node (underneath the domain node) of type "type",584 * either isl_schedule_node_sequence or isl_schedule_node_set.585 * The domains of the two schedules are assumed to be disjoint.586 *587 * The new schedule has as domain the union of the domains of the two588 * schedules. The child of the domain node is a node of type "type"589 * with two filters corresponding to the domains of the input schedules.590 * If one (or both) of the top-level nodes of the two schedules is itself591 * of type "type", then the filter is pushed into the children of that592 * node and the sequence or set is flattened.593 */594__isl_give isl_schedule *isl_schedule_pair(enum isl_schedule_node_type type,595 __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)596{597 int disjoint;598 isl_ctx *ctx;599 enum isl_schedule_node_type root_type;600 isl_schedule_tree *tree1, *tree2;601 isl_union_set *filter1, *filter2, *domain;602 603 if (!schedule1 || !schedule2)604 goto error;605 606 root_type = isl_schedule_tree_get_type(schedule1->root);607 if (root_type != isl_schedule_node_domain)608 isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal,609 "root node not a domain node", goto error);610 root_type = isl_schedule_tree_get_type(schedule2->root);611 if (root_type != isl_schedule_node_domain)612 isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal,613 "root node not a domain node", goto error);614 615 ctx = isl_schedule_get_ctx(schedule1);616 tree1 = isl_schedule_tree_copy(schedule1->root);617 filter1 = isl_schedule_tree_domain_get_domain(tree1);618 tree2 = isl_schedule_tree_copy(schedule2->root);619 filter2 = isl_schedule_tree_domain_get_domain(tree2);620 621 isl_schedule_free(schedule1);622 isl_schedule_free(schedule2);623 624 disjoint = isl_union_set_is_disjoint(filter1, filter2);625 if (disjoint < 0)626 filter1 = isl_union_set_free(filter1);627 if (!disjoint)628 isl_die(ctx, isl_error_invalid,629 "schedule domains not disjoint",630 filter1 = isl_union_set_free(filter1));631 632 domain = isl_union_set_union(isl_union_set_copy(filter1),633 isl_union_set_copy(filter2));634 filter1 = isl_union_set_gist(filter1, isl_union_set_copy(domain));635 filter2 = isl_union_set_gist(filter2, isl_union_set_copy(domain));636 637 tree1 = insert_filter_in_child_of_type(tree1, filter1, type);638 tree2 = insert_filter_in_child_of_type(tree2, filter2, type);639 640 tree1 = isl_schedule_tree_from_pair(type, tree1, tree2);641 tree1 = isl_schedule_tree_insert_domain(tree1, domain);642 643 return isl_schedule_from_schedule_tree(ctx, tree1);644error:645 isl_schedule_free(schedule1);646 isl_schedule_free(schedule2);647 return NULL;648}649 650/* Construct a schedule that combines the schedules "schedule1" and "schedule2"651 * through a sequence node.652 * The domains of the input schedules are assumed to be disjoint.653 */654__isl_give isl_schedule *isl_schedule_sequence(655 __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)656{657 return isl_schedule_pair(isl_schedule_node_sequence,658 schedule1, schedule2);659}660 661/* Construct a schedule that combines the schedules "schedule1" and "schedule2"662 * through a set node.663 * The domains of the input schedules are assumed to be disjoint.664 */665__isl_give isl_schedule *isl_schedule_set(666 __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)667{668 return isl_schedule_pair(isl_schedule_node_set, schedule1, schedule2);669}670 671/* Print "schedule" to "p".672 */673__isl_give isl_printer *isl_printer_print_schedule(__isl_take isl_printer *p,674 __isl_keep isl_schedule *schedule)675{676 if (!schedule)677 return isl_printer_free(p);678 679 return isl_printer_print_schedule_tree(p, schedule->root);680}681 682#undef BASE683#define BASE schedule684#include <print_templ_yaml.c>685