4965 lines · c
1/*2 * Copyright 2013-2014 Ecole Normale Superieure3 * Copyright 2014 INRIA Rocquencourt4 * Copyright 2016 Sven Verdoolaege5 *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 */13 14#include <isl/id.h>15#include <isl/val.h>16#include <isl/space.h>17#include <isl/set.h>18#include <isl_schedule_band.h>19#include <isl_schedule_private.h>20#include <isl_schedule_node_private.h>21 22/* Create a new schedule node in the given schedule, point at the given23 * tree with given ancestors and child positions.24 * "child_pos" may be NULL if there are no ancestors.25 */26__isl_give isl_schedule_node *isl_schedule_node_alloc(27 __isl_take isl_schedule *schedule, __isl_take isl_schedule_tree *tree,28 __isl_take isl_schedule_tree_list *ancestors, int *child_pos)29{30 isl_ctx *ctx;31 isl_schedule_node *node;32 int i;33 isl_size n;34 35 n = isl_schedule_tree_list_n_schedule_tree(ancestors);36 if (!schedule || !tree || n < 0)37 goto error;38 if (n > 0 && !child_pos)39 goto error;40 ctx = isl_schedule_get_ctx(schedule);41 node = isl_calloc_type(ctx, isl_schedule_node);42 if (!node)43 goto error;44 node->ref = 1;45 node->schedule = schedule;46 node->tree = tree;47 node->ancestors = ancestors;48 node->child_pos = isl_alloc_array(ctx, int, n);49 if (n && !node->child_pos)50 return isl_schedule_node_free(node);51 for (i = 0; i < n; ++i)52 node->child_pos[i] = child_pos[i];53 54 return node;55error:56 isl_schedule_free(schedule);57 isl_schedule_tree_free(tree);58 isl_schedule_tree_list_free(ancestors);59 return NULL;60}61 62/* Return a pointer to the root of a schedule tree with as single63 * node a domain node with the given domain.64 */65__isl_give isl_schedule_node *isl_schedule_node_from_domain(66 __isl_take isl_union_set *domain)67{68 isl_schedule *schedule;69 isl_schedule_node *node;70 71 schedule = isl_schedule_from_domain(domain);72 node = isl_schedule_get_root(schedule);73 isl_schedule_free(schedule);74 75 return node;76}77 78/* Return a pointer to the root of a schedule tree with as single79 * node a extension node with the given extension.80 */81__isl_give isl_schedule_node *isl_schedule_node_from_extension(82 __isl_take isl_union_map *extension)83{84 isl_ctx *ctx;85 isl_schedule *schedule;86 isl_schedule_tree *tree;87 isl_schedule_node *node;88 89 if (!extension)90 return NULL;91 92 ctx = isl_union_map_get_ctx(extension);93 tree = isl_schedule_tree_from_extension(extension);94 schedule = isl_schedule_from_schedule_tree(ctx, tree);95 node = isl_schedule_get_root(schedule);96 isl_schedule_free(schedule);97 98 return node;99}100 101/* Return the isl_ctx to which "node" belongs.102 */103isl_ctx *isl_schedule_node_get_ctx(__isl_keep isl_schedule_node *node)104{105 return node ? isl_schedule_get_ctx(node->schedule) : NULL;106}107 108/* Return a pointer to the leaf of the schedule into which "node" points.109 */110__isl_keep isl_schedule_tree *isl_schedule_node_peek_leaf(111 __isl_keep isl_schedule_node *node)112{113 return node ? isl_schedule_peek_leaf(node->schedule) : NULL;114}115 116/* Return a copy of the leaf of the schedule into which "node" points.117 */118__isl_give isl_schedule_tree *isl_schedule_node_get_leaf(119 __isl_keep isl_schedule_node *node)120{121 return isl_schedule_tree_copy(isl_schedule_node_peek_leaf(node));122}123 124/* Return the type of the node or isl_schedule_node_error on error.125 */126enum isl_schedule_node_type isl_schedule_node_get_type(127 __isl_keep isl_schedule_node *node)128{129 return node ? isl_schedule_tree_get_type(node->tree)130 : isl_schedule_node_error;131}132 133/* Return the type of the parent of "node" or isl_schedule_node_error on error.134 */135enum isl_schedule_node_type isl_schedule_node_get_parent_type(136 __isl_keep isl_schedule_node *node)137{138 isl_size n;139 int pos;140 int has_parent;141 isl_schedule_tree *parent;142 enum isl_schedule_node_type type;143 144 if (!node)145 return isl_schedule_node_error;146 has_parent = isl_schedule_node_has_parent(node);147 if (has_parent < 0)148 return isl_schedule_node_error;149 if (!has_parent)150 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,151 "node has no parent", return isl_schedule_node_error);152 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);153 if (n < 0)154 return isl_schedule_node_error;155 156 pos = n - 1;157 parent = isl_schedule_tree_list_get_schedule_tree(node->ancestors, pos);158 type = isl_schedule_tree_get_type(parent);159 isl_schedule_tree_free(parent);160 161 return type;162}163 164/* Return a copy of the subtree that this node points to.165 */166__isl_give isl_schedule_tree *isl_schedule_node_get_tree(167 __isl_keep isl_schedule_node *node)168{169 if (!node)170 return NULL;171 172 return isl_schedule_tree_copy(node->tree);173}174 175/* Return a copy of the schedule into which "node" points.176 */177__isl_give isl_schedule *isl_schedule_node_get_schedule(178 __isl_keep isl_schedule_node *node)179{180 if (!node)181 return NULL;182 return isl_schedule_copy(node->schedule);183}184 185/* Return a fresh copy of "node".186 */187__isl_give isl_schedule_node *isl_schedule_node_dup(188 __isl_keep isl_schedule_node *node)189{190 if (!node)191 return NULL;192 193 return isl_schedule_node_alloc(isl_schedule_copy(node->schedule),194 isl_schedule_tree_copy(node->tree),195 isl_schedule_tree_list_copy(node->ancestors),196 node->child_pos);197}198 199/* Return an isl_schedule_node that is equal to "node" and that has only200 * a single reference.201 */202__isl_give isl_schedule_node *isl_schedule_node_cow(203 __isl_take isl_schedule_node *node)204{205 if (!node)206 return NULL;207 208 if (node->ref == 1)209 return node;210 node->ref--;211 return isl_schedule_node_dup(node);212}213 214/* Return a new reference to "node".215 */216__isl_give isl_schedule_node *isl_schedule_node_copy(217 __isl_keep isl_schedule_node *node)218{219 if (!node)220 return NULL;221 222 node->ref++;223 return node;224}225 226/* Free "node" and return NULL.227 */228__isl_null isl_schedule_node *isl_schedule_node_free(229 __isl_take isl_schedule_node *node)230{231 if (!node)232 return NULL;233 if (--node->ref > 0)234 return NULL;235 236 isl_schedule_tree_list_free(node->ancestors);237 free(node->child_pos);238 isl_schedule_tree_free(node->tree);239 isl_schedule_free(node->schedule);240 free(node);241 242 return NULL;243}244 245/* Do "node1" and "node2" point to the same position in the same246 * schedule?247 */248isl_bool isl_schedule_node_is_equal(__isl_keep isl_schedule_node *node1,249 __isl_keep isl_schedule_node *node2)250{251 int i;252 isl_size n1, n2;253 254 if (!node1 || !node2)255 return isl_bool_error;256 if (node1 == node2)257 return isl_bool_true;258 if (node1->schedule != node2->schedule)259 return isl_bool_false;260 261 n1 = isl_schedule_node_get_tree_depth(node1);262 n2 = isl_schedule_node_get_tree_depth(node2);263 if (n1 < 0 || n2 < 0)264 return isl_bool_error;265 if (n1 != n2)266 return isl_bool_false;267 for (i = 0; i < n1; ++i)268 if (node1->child_pos[i] != node2->child_pos[i])269 return isl_bool_false;270 271 return isl_bool_true;272}273 274/* Return the number of outer schedule dimensions of "node"275 * in its schedule tree.276 *277 * Return isl_size_error on error.278 */279isl_size isl_schedule_node_get_schedule_depth(280 __isl_keep isl_schedule_node *node)281{282 int i;283 isl_size n;284 int depth = 0;285 286 if (!node)287 return isl_size_error;288 289 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);290 if (n < 0)291 return isl_size_error;292 for (i = n - 1; i >= 0; --i) {293 isl_schedule_tree *tree;294 isl_size n;295 296 tree = isl_schedule_tree_list_get_schedule_tree(297 node->ancestors, i);298 if (!tree)299 return isl_size_error;300 n = 0;301 if (tree->type == isl_schedule_node_band)302 n = isl_schedule_tree_band_n_member(tree);303 depth += n;304 isl_schedule_tree_free(tree);305 if (n < 0)306 return isl_size_error;307 }308 309 return depth;310}311 312/* Internal data structure for313 * isl_schedule_node_get_prefix_schedule_union_pw_multi_aff314 *315 * "initialized" is set if the filter field has been initialized.316 * If "universe_domain" is not set, then the collected filter is intersected317 * with the domain of the root domain node.318 * "universe_filter" is set if we are only collecting the universes of filters319 * "collect_prefix" is set if we are collecting prefixes.320 * "filter" collects all outer filters and is NULL until "initialized" is set.321 * "prefix" collects all outer band partial schedules (if "collect_prefix"322 * is set). If it is used, then it is initialized by the caller323 * of collect_filter_prefix to a zero-dimensional function.324 */325struct isl_schedule_node_get_filter_prefix_data {326 int initialized;327 int universe_domain;328 int universe_filter;329 int collect_prefix;330 isl_union_set *filter;331 isl_multi_union_pw_aff *prefix;332};333 334static isl_stat collect_filter_prefix(__isl_keep isl_schedule_tree_list *list,335 int n, struct isl_schedule_node_get_filter_prefix_data *data);336 337/* Update the filter and prefix information in "data" based on the first "n"338 * elements in "list" and the expansion tree root "tree".339 *340 * We first collect the information from the elements in "list",341 * initializing the filter based on the domain of the expansion.342 * Then we map the results to the expanded space and combined them343 * with the results already in "data".344 */345static isl_stat collect_filter_prefix_expansion(346 __isl_take isl_schedule_tree *tree,347 __isl_keep isl_schedule_tree_list *list, int n,348 struct isl_schedule_node_get_filter_prefix_data *data)349{350 struct isl_schedule_node_get_filter_prefix_data contracted;351 isl_union_pw_multi_aff *c;352 isl_union_map *exp, *universe;353 isl_union_set *filter;354 355 c = isl_schedule_tree_expansion_get_contraction(tree);356 exp = isl_schedule_tree_expansion_get_expansion(tree);357 358 contracted.initialized = 1;359 contracted.universe_domain = data->universe_domain;360 contracted.universe_filter = data->universe_filter;361 contracted.collect_prefix = data->collect_prefix;362 universe = isl_union_map_universe(isl_union_map_copy(exp));363 filter = isl_union_map_domain(universe);364 if (data->collect_prefix) {365 isl_space *space = isl_union_set_get_space(filter);366 space = isl_space_set_from_params(space);367 contracted.prefix = isl_multi_union_pw_aff_zero(space);368 }369 contracted.filter = filter;370 371 if (collect_filter_prefix(list, n, &contracted) < 0)372 contracted.filter = isl_union_set_free(contracted.filter);373 if (data->collect_prefix) {374 isl_multi_union_pw_aff *prefix;375 376 prefix = contracted.prefix;377 prefix =378 isl_multi_union_pw_aff_pullback_union_pw_multi_aff(prefix,379 isl_union_pw_multi_aff_copy(c));380 data->prefix = isl_multi_union_pw_aff_flat_range_product(381 prefix, data->prefix);382 }383 filter = contracted.filter;384 if (data->universe_domain)385 filter = isl_union_set_preimage_union_pw_multi_aff(filter,386 isl_union_pw_multi_aff_copy(c));387 else388 filter = isl_union_set_apply(filter, isl_union_map_copy(exp));389 if (!data->initialized)390 data->filter = filter;391 else392 data->filter = isl_union_set_intersect(filter, data->filter);393 data->initialized = 1;394 395 isl_union_pw_multi_aff_free(c);396 isl_union_map_free(exp);397 isl_schedule_tree_free(tree);398 399 return isl_stat_ok;400}401 402/* Update the filter information in "data" based on the first "n"403 * elements in "list" and the extension tree root "tree", in case404 * data->universe_domain is set and data->collect_prefix is not.405 *406 * We collect the universe domain of the elements in "list" and407 * add it to the universe range of the extension (intersected408 * with the already collected filter, if any).409 */410static isl_stat collect_universe_domain_extension(411 __isl_take isl_schedule_tree *tree,412 __isl_keep isl_schedule_tree_list *list, int n,413 struct isl_schedule_node_get_filter_prefix_data *data)414{415 struct isl_schedule_node_get_filter_prefix_data data_outer;416 isl_union_map *extension;417 isl_union_set *filter;418 419 data_outer.initialized = 0;420 data_outer.universe_domain = 1;421 data_outer.universe_filter = data->universe_filter;422 data_outer.collect_prefix = 0;423 data_outer.filter = NULL;424 data_outer.prefix = NULL;425 426 if (collect_filter_prefix(list, n, &data_outer) < 0)427 data_outer.filter = isl_union_set_free(data_outer.filter);428 429 extension = isl_schedule_tree_extension_get_extension(tree);430 extension = isl_union_map_universe(extension);431 filter = isl_union_map_range(extension);432 if (data_outer.initialized)433 filter = isl_union_set_union(filter, data_outer.filter);434 if (data->initialized)435 filter = isl_union_set_intersect(filter, data->filter);436 437 data->filter = filter;438 439 isl_schedule_tree_free(tree);440 441 return isl_stat_ok;442}443 444/* Update "data" based on the tree node "tree" in case "data" has445 * not been initialized yet.446 *447 * Return 0 on success and -1 on error.448 *449 * If "tree" is a filter, then we set data->filter to this filter450 * (or its universe).451 * If "tree" is a domain, then this means we have reached the root452 * of the schedule tree without being able to extract any information.453 * We therefore initialize data->filter to the universe of the domain,454 * or the domain itself if data->universe_domain is not set.455 * If "tree" is a band with at least one member, then we set data->filter456 * to the universe of the schedule domain and replace the zero-dimensional457 * data->prefix by the band schedule (if data->collect_prefix is set).458 */459static isl_stat collect_filter_prefix_init(__isl_keep isl_schedule_tree *tree,460 struct isl_schedule_node_get_filter_prefix_data *data)461{462 enum isl_schedule_node_type type;463 isl_multi_union_pw_aff *mupa;464 isl_union_set *filter;465 isl_size n;466 467 type = isl_schedule_tree_get_type(tree);468 switch (type) {469 case isl_schedule_node_error:470 return isl_stat_error;471 case isl_schedule_node_expansion:472 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,473 "should be handled by caller", return isl_stat_error);474 case isl_schedule_node_extension:475 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,476 "cannot handle extension nodes", return isl_stat_error);477 case isl_schedule_node_context:478 case isl_schedule_node_leaf:479 case isl_schedule_node_guard:480 case isl_schedule_node_mark:481 case isl_schedule_node_sequence:482 case isl_schedule_node_set:483 return isl_stat_ok;484 case isl_schedule_node_domain:485 filter = isl_schedule_tree_domain_get_domain(tree);486 if (data->universe_domain)487 filter = isl_union_set_universe(filter);488 data->filter = filter;489 break;490 case isl_schedule_node_band:491 n = isl_schedule_tree_band_n_member(tree);492 if (n < 0)493 return isl_stat_error;494 if (n == 0)495 return isl_stat_ok;496 mupa = isl_schedule_tree_band_get_partial_schedule(tree);497 if (data->collect_prefix) {498 isl_multi_union_pw_aff_free(data->prefix);499 mupa = isl_multi_union_pw_aff_reset_tuple_id(mupa,500 isl_dim_set);501 data->prefix = isl_multi_union_pw_aff_copy(mupa);502 }503 filter = isl_multi_union_pw_aff_domain(mupa);504 filter = isl_union_set_universe(filter);505 data->filter = filter;506 break;507 case isl_schedule_node_filter:508 filter = isl_schedule_tree_filter_get_filter(tree);509 if (data->universe_filter)510 filter = isl_union_set_universe(filter);511 data->filter = filter;512 break;513 }514 515 if ((data->collect_prefix && !data->prefix) || !data->filter)516 return isl_stat_error;517 518 data->initialized = 1;519 520 return isl_stat_ok;521}522 523/* Update "data" based on the tree node "tree" in case "data" has524 * already been initialized.525 *526 * Return 0 on success and -1 on error.527 *528 * If "tree" is a domain and data->universe_domain is not set, then529 * intersect data->filter with the domain.530 * If "tree" is a filter, then we intersect data->filter with this filter531 * (or its universe).532 * If "tree" is a band with at least one member and data->collect_prefix533 * is set, then we extend data->prefix with the band schedule.534 * If "tree" is an extension, then we make sure that we are not collecting535 * information on any extended domain elements.536 */537static isl_stat collect_filter_prefix_update(__isl_keep isl_schedule_tree *tree,538 struct isl_schedule_node_get_filter_prefix_data *data)539{540 enum isl_schedule_node_type type;541 isl_multi_union_pw_aff *mupa;542 isl_union_set *filter;543 isl_union_map *extension;544 isl_bool empty;545 isl_size n;546 547 type = isl_schedule_tree_get_type(tree);548 switch (type) {549 case isl_schedule_node_error:550 return isl_stat_error;551 case isl_schedule_node_expansion:552 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,553 "should be handled by caller", return isl_stat_error);554 case isl_schedule_node_extension:555 extension = isl_schedule_tree_extension_get_extension(tree);556 extension = isl_union_map_intersect_range(extension,557 isl_union_set_copy(data->filter));558 empty = isl_union_map_is_empty(extension);559 isl_union_map_free(extension);560 if (empty < 0)561 return isl_stat_error;562 if (empty)563 break;564 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,565 "cannot handle extension nodes", return isl_stat_error);566 case isl_schedule_node_context:567 case isl_schedule_node_leaf:568 case isl_schedule_node_guard:569 case isl_schedule_node_mark:570 case isl_schedule_node_sequence:571 case isl_schedule_node_set:572 break;573 case isl_schedule_node_domain:574 if (data->universe_domain)575 break;576 filter = isl_schedule_tree_domain_get_domain(tree);577 data->filter = isl_union_set_intersect(data->filter, filter);578 break;579 case isl_schedule_node_band:580 n = isl_schedule_tree_band_n_member(tree);581 if (n < 0)582 return isl_stat_error;583 if (n == 0)584 break;585 if (!data->collect_prefix)586 break;587 mupa = isl_schedule_tree_band_get_partial_schedule(tree);588 data->prefix = isl_multi_union_pw_aff_flat_range_product(mupa,589 data->prefix);590 if (!data->prefix)591 return isl_stat_error;592 break;593 case isl_schedule_node_filter:594 filter = isl_schedule_tree_filter_get_filter(tree);595 if (data->universe_filter)596 filter = isl_union_set_universe(filter);597 data->filter = isl_union_set_intersect(data->filter, filter);598 if (!data->filter)599 return isl_stat_error;600 break;601 }602 603 return isl_stat_ok;604}605 606/* Collect filter and/or prefix information from the first "n"607 * elements in "list" (which represent the ancestors of a node).608 * Store the results in "data".609 *610 * Extension nodes are only supported if they do not affect the outcome,611 * i.e., if we are collecting information on non-extended domain elements,612 * or if we are collecting the universe domain (without prefix).613 *614 * Return 0 on success and -1 on error.615 *616 * We traverse the list from innermost ancestor (last element)617 * to outermost ancestor (first element), calling collect_filter_prefix_init618 * on each node as long as we have not been able to extract any information619 * yet and collect_filter_prefix_update afterwards.620 * If we come across an expansion node, then we interrupt the traversal621 * and call collect_filter_prefix_expansion to restart the traversal622 * over the remaining ancestors and to combine the results with those623 * that have already been collected.624 * If we come across an extension node and we are only computing625 * the universe domain, then we interrupt the traversal and call626 * collect_universe_domain_extension to restart the traversal627 * over the remaining ancestors and to combine the results with those628 * that have already been collected.629 * On successful return, data->initialized will be set since the outermost630 * ancestor is a domain node, which always results in an initialization.631 */632static isl_stat collect_filter_prefix(__isl_keep isl_schedule_tree_list *list,633 int n, struct isl_schedule_node_get_filter_prefix_data *data)634{635 int i;636 637 if (!list)638 return isl_stat_error;639 640 for (i = n - 1; i >= 0; --i) {641 isl_schedule_tree *tree;642 enum isl_schedule_node_type type;643 isl_stat r;644 645 tree = isl_schedule_tree_list_get_schedule_tree(list, i);646 if (!tree)647 return isl_stat_error;648 type = isl_schedule_tree_get_type(tree);649 if (type == isl_schedule_node_expansion)650 return collect_filter_prefix_expansion(tree, list, i,651 data);652 if (type == isl_schedule_node_extension &&653 data->universe_domain && !data->collect_prefix)654 return collect_universe_domain_extension(tree, list, i,655 data);656 if (!data->initialized)657 r = collect_filter_prefix_init(tree, data);658 else659 r = collect_filter_prefix_update(tree, data);660 isl_schedule_tree_free(tree);661 if (r < 0)662 return isl_stat_error;663 }664 665 return isl_stat_ok;666}667 668/* Return the concatenation of the partial schedules of all outer band669 * nodes of "node" interesected with all outer filters670 * as an isl_multi_union_pw_aff.671 * None of the ancestors of "node" may be an extension node, unless672 * there is also a filter ancestor that filters out all the extended673 * domain elements.674 *675 * If "node" is pointing at the root of the schedule tree, then676 * there are no domain elements reaching the current node, so677 * we return an empty result.678 *679 * We collect all the filters and partial schedules in collect_filter_prefix680 * and intersect the domain of the combined schedule with the combined filter.681 */682__isl_give isl_multi_union_pw_aff *683isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(684 __isl_keep isl_schedule_node *node)685{686 isl_size n;687 isl_space *space;688 struct isl_schedule_node_get_filter_prefix_data data;689 690 if (!node)691 return NULL;692 693 space = isl_schedule_get_space(node->schedule);694 space = isl_space_set_from_params(space);695 if (node->tree == node->schedule->root)696 return isl_multi_union_pw_aff_zero(space);697 698 data.initialized = 0;699 data.universe_domain = 1;700 data.universe_filter = 0;701 data.collect_prefix = 1;702 data.filter = NULL;703 data.prefix = isl_multi_union_pw_aff_zero(space);704 705 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);706 if (n < 0 || collect_filter_prefix(node->ancestors, n, &data) < 0)707 data.prefix = isl_multi_union_pw_aff_free(data.prefix);708 709 data.prefix = isl_multi_union_pw_aff_intersect_domain(data.prefix,710 data.filter);711 712 return data.prefix;713}714 715/* Return the concatenation of the partial schedules of all outer band716 * nodes of "node" interesected with all outer filters717 * as an isl_union_pw_multi_aff.718 * None of the ancestors of "node" may be an extension node, unless719 * there is also a filter ancestor that filters out all the extended720 * domain elements.721 *722 * If "node" is pointing at the root of the schedule tree, then723 * there are no domain elements reaching the current node, so724 * we return an empty result.725 *726 * We collect all the filters and partial schedules in collect_filter_prefix.727 * The partial schedules are collected as an isl_multi_union_pw_aff.728 * If this isl_multi_union_pw_aff is zero-dimensional, then it does not729 * contain any domain information, so we construct the isl_union_pw_multi_aff730 * result as a zero-dimensional function on the collected filter.731 * Otherwise, we convert the isl_multi_union_pw_aff to732 * an isl_multi_union_pw_aff and intersect the domain with the filter.733 */734__isl_give isl_union_pw_multi_aff *735isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(736 __isl_keep isl_schedule_node *node)737{738 isl_size n, dim;739 isl_space *space;740 isl_union_pw_multi_aff *prefix;741 struct isl_schedule_node_get_filter_prefix_data data;742 743 if (!node)744 return NULL;745 746 space = isl_schedule_get_space(node->schedule);747 if (node->tree == node->schedule->root)748 return isl_union_pw_multi_aff_empty(space);749 750 space = isl_space_set_from_params(space);751 data.initialized = 0;752 data.universe_domain = 1;753 data.universe_filter = 0;754 data.collect_prefix = 1;755 data.filter = NULL;756 data.prefix = isl_multi_union_pw_aff_zero(space);757 758 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);759 if (n < 0 || collect_filter_prefix(node->ancestors, n, &data) < 0)760 data.prefix = isl_multi_union_pw_aff_free(data.prefix);761 762 dim = isl_multi_union_pw_aff_dim(data.prefix, isl_dim_set);763 if (dim < 0)764 data.prefix = isl_multi_union_pw_aff_free(data.prefix);765 if (data.prefix && dim == 0) {766 isl_multi_union_pw_aff_free(data.prefix);767 prefix = isl_union_pw_multi_aff_from_domain(data.filter);768 } else {769 prefix =770 isl_union_pw_multi_aff_from_multi_union_pw_aff(data.prefix);771 prefix = isl_union_pw_multi_aff_intersect_domain(prefix,772 data.filter);773 }774 775 return prefix;776}777 778/* Return the concatenation of the partial schedules of all outer band779 * nodes of "node" interesected with all outer filters780 * as an isl_union_map.781 */782__isl_give isl_union_map *isl_schedule_node_get_prefix_schedule_union_map(783 __isl_keep isl_schedule_node *node)784{785 isl_union_pw_multi_aff *upma;786 787 upma = isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(node);788 return isl_union_map_from_union_pw_multi_aff(upma);789}790 791/* Return the concatenation of the partial schedules of all outer band792 * nodes of "node" intersected with all outer domain constraints.793 * None of the ancestors of "node" may be an extension node, unless794 * there is also a filter ancestor that filters out all the extended795 * domain elements.796 *797 * Essentially, this function intersects the domain of the output798 * of isl_schedule_node_get_prefix_schedule_union_map with the output799 * of isl_schedule_node_get_domain, except that it only traverses800 * the ancestors of "node" once.801 */802__isl_give isl_union_map *isl_schedule_node_get_prefix_schedule_relation(803 __isl_keep isl_schedule_node *node)804{805 isl_size n, dim;806 isl_space *space;807 isl_union_map *prefix;808 struct isl_schedule_node_get_filter_prefix_data data;809 810 if (!node)811 return NULL;812 813 space = isl_schedule_get_space(node->schedule);814 if (node->tree == node->schedule->root)815 return isl_union_map_empty(space);816 817 space = isl_space_set_from_params(space);818 data.initialized = 0;819 data.universe_domain = 0;820 data.universe_filter = 0;821 data.collect_prefix = 1;822 data.filter = NULL;823 data.prefix = isl_multi_union_pw_aff_zero(space);824 825 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);826 if (n < 0 || collect_filter_prefix(node->ancestors, n, &data) < 0)827 data.prefix = isl_multi_union_pw_aff_free(data.prefix);828 829 dim = isl_multi_union_pw_aff_dim(data.prefix, isl_dim_set);830 if (dim < 0)831 data.prefix = isl_multi_union_pw_aff_free(data.prefix);832 if (data.prefix && dim == 0) {833 isl_multi_union_pw_aff_free(data.prefix);834 prefix = isl_union_map_from_domain(data.filter);835 } else {836 prefix = isl_union_map_from_multi_union_pw_aff(data.prefix);837 prefix = isl_union_map_intersect_domain(prefix, data.filter);838 }839 840 return prefix;841}842 843/* Return the domain elements that reach "node".844 *845 * If "node" is pointing at the root of the schedule tree, then846 * there are no domain elements reaching the current node, so847 * we return an empty result.848 * None of the ancestors of "node" may be an extension node, unless849 * there is also a filter ancestor that filters out all the extended850 * domain elements.851 *852 * Otherwise, we collect all filters reaching the node,853 * intersected with the root domain in collect_filter_prefix.854 */855__isl_give isl_union_set *isl_schedule_node_get_domain(856 __isl_keep isl_schedule_node *node)857{858 isl_size n;859 struct isl_schedule_node_get_filter_prefix_data data;860 861 if (!node)862 return NULL;863 864 if (node->tree == node->schedule->root) {865 isl_space *space;866 867 space = isl_schedule_get_space(node->schedule);868 return isl_union_set_empty(space);869 }870 871 data.initialized = 0;872 data.universe_domain = 0;873 data.universe_filter = 0;874 data.collect_prefix = 0;875 data.filter = NULL;876 data.prefix = NULL;877 878 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);879 if (n < 0 || collect_filter_prefix(node->ancestors, n, &data) < 0)880 data.filter = isl_union_set_free(data.filter);881 882 return data.filter;883}884 885/* Return the union of universe sets of the domain elements that reach "node".886 *887 * If "node" is pointing at the root of the schedule tree, then888 * there are no domain elements reaching the current node, so889 * we return an empty result.890 *891 * Otherwise, we collect the universes of all filters reaching the node892 * in collect_filter_prefix.893 */894__isl_give isl_union_set *isl_schedule_node_get_universe_domain(895 __isl_keep isl_schedule_node *node)896{897 isl_size n;898 struct isl_schedule_node_get_filter_prefix_data data;899 900 if (!node)901 return NULL;902 903 if (node->tree == node->schedule->root) {904 isl_space *space;905 906 space = isl_schedule_get_space(node->schedule);907 return isl_union_set_empty(space);908 }909 910 data.initialized = 0;911 data.universe_domain = 1;912 data.universe_filter = 1;913 data.collect_prefix = 0;914 data.filter = NULL;915 data.prefix = NULL;916 917 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);918 if (n < 0 || collect_filter_prefix(node->ancestors, n, &data) < 0)919 data.filter = isl_union_set_free(data.filter);920 921 return data.filter;922}923 924/* Return the subtree schedule of "node".925 *926 * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle927 * trees that do not contain any schedule information, we first928 * move down to the first relevant descendant and handle leaves ourselves.929 *930 * If the subtree rooted at "node" contains any expansion nodes, then931 * the returned subtree schedule is formulated in terms of the expanded932 * domains.933 * The subtree is not allowed to contain any extension nodes.934 */935__isl_give isl_union_map *isl_schedule_node_get_subtree_schedule_union_map(936 __isl_keep isl_schedule_node *node)937{938 isl_schedule_tree *tree, *leaf;939 isl_union_map *umap;940 941 tree = isl_schedule_node_get_tree(node);942 leaf = isl_schedule_node_peek_leaf(node);943 tree = isl_schedule_tree_first_schedule_descendant(tree, leaf);944 if (!tree)945 return NULL;946 if (tree == leaf) {947 isl_union_set *domain;948 domain = isl_schedule_node_get_universe_domain(node);949 isl_schedule_tree_free(tree);950 return isl_union_map_from_domain(domain);951 }952 953 umap = isl_schedule_tree_get_subtree_schedule_union_map(tree);954 isl_schedule_tree_free(tree);955 return umap;956}957 958/* Return the number of ancestors of "node" in its schedule tree.959 */960isl_size isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node *node)961{962 if (!node)963 return isl_size_error;964 return isl_schedule_tree_list_n_schedule_tree(node->ancestors);965}966 967/* Does "node" have a parent?968 *969 * That is, does it point to any node of the schedule other than the root?970 */971isl_bool isl_schedule_node_has_parent(__isl_keep isl_schedule_node *node)972{973 isl_size depth;974 975 depth = isl_schedule_node_get_tree_depth(node);976 if (depth < 0)977 return isl_bool_error;978 return isl_bool_ok(depth != 0);979}980 981/* Return the position of "node" among the children of its parent.982 */983isl_size isl_schedule_node_get_child_position(984 __isl_keep isl_schedule_node *node)985{986 isl_size n;987 isl_bool has_parent;988 989 if (!node)990 return isl_size_error;991 has_parent = isl_schedule_node_has_parent(node);992 if (has_parent < 0)993 return isl_size_error;994 if (!has_parent)995 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,996 "node has no parent", return isl_size_error);997 998 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);999 return n < 0 ? isl_size_error : node->child_pos[n - 1];1000}1001 1002/* Does the parent (if any) of "node" have any children with a smaller child1003 * position than this one?1004 */1005isl_bool isl_schedule_node_has_previous_sibling(1006 __isl_keep isl_schedule_node *node)1007{1008 isl_size n;1009 isl_bool has_parent;1010 1011 if (!node)1012 return isl_bool_error;1013 has_parent = isl_schedule_node_has_parent(node);1014 if (has_parent < 0 || !has_parent)1015 return has_parent;1016 1017 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);1018 if (n < 0)1019 return isl_bool_error;1020 1021 return isl_bool_ok(node->child_pos[n - 1] > 0);1022}1023 1024/* Does the parent (if any) of "node" have any children with a greater child1025 * position than this one?1026 */1027isl_bool isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node *node)1028{1029 isl_size n, n_child;1030 isl_bool has_parent;1031 isl_schedule_tree *tree;1032 1033 if (!node)1034 return isl_bool_error;1035 has_parent = isl_schedule_node_has_parent(node);1036 if (has_parent < 0 || !has_parent)1037 return has_parent;1038 1039 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);1040 if (n < 0)1041 return isl_bool_error;1042 tree = isl_schedule_tree_list_get_schedule_tree(node->ancestors, n - 1);1043 n_child = isl_schedule_tree_n_children(tree);1044 isl_schedule_tree_free(tree);1045 if (n_child < 0)1046 return isl_bool_error;1047 1048 return isl_bool_ok(node->child_pos[n - 1] + 1 < n_child);1049}1050 1051/* Does "node" have any children?1052 *1053 * Any node other than the leaf nodes is considered to have at least1054 * one child, even if the corresponding isl_schedule_tree does not1055 * have any children.1056 */1057isl_bool isl_schedule_node_has_children(__isl_keep isl_schedule_node *node)1058{1059 if (!node)1060 return isl_bool_error;1061 return isl_bool_ok(!isl_schedule_tree_is_leaf(node->tree));1062}1063 1064/* Return the number of children of "node"?1065 *1066 * Any node other than the leaf nodes is considered to have at least1067 * one child, even if the corresponding isl_schedule_tree does not1068 * have any children. That is, the number of children of "node" is1069 * only zero if its tree is the explicit empty tree. Otherwise,1070 * if the isl_schedule_tree has any children, then it is equal1071 * to the number of children of "node". If it has zero children,1072 * then "node" still has a leaf node as child.1073 */1074isl_size isl_schedule_node_n_children(__isl_keep isl_schedule_node *node)1075{1076 isl_size n;1077 1078 if (!node)1079 return isl_size_error;1080 1081 if (isl_schedule_tree_is_leaf(node->tree))1082 return 0;1083 1084 n = isl_schedule_tree_n_children(node->tree);1085 if (n < 0)1086 return isl_size_error;1087 if (n == 0)1088 return 1;1089 1090 return n;1091}1092 1093/* Move the "node" pointer to the ancestor of the given generation1094 * of the node it currently points to, where generation 0 is the node1095 * itself and generation 1 is its parent.1096 */1097__isl_give isl_schedule_node *isl_schedule_node_ancestor(1098 __isl_take isl_schedule_node *node, int generation)1099{1100 isl_size n;1101 isl_schedule_tree *tree;1102 1103 if (!node)1104 return NULL;1105 if (generation == 0)1106 return node;1107 n = isl_schedule_node_get_tree_depth(node);1108 if (n < 0)1109 return isl_schedule_node_free(node);1110 if (generation < 0 || generation > n)1111 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,1112 "generation out of bounds",1113 return isl_schedule_node_free(node));1114 node = isl_schedule_node_cow(node);1115 if (!node)1116 return NULL;1117 1118 tree = isl_schedule_tree_list_get_schedule_tree(node->ancestors,1119 n - generation);1120 isl_schedule_tree_free(node->tree);1121 node->tree = tree;1122 node->ancestors = isl_schedule_tree_list_drop(node->ancestors,1123 n - generation, generation);1124 if (!node->ancestors || !node->tree)1125 return isl_schedule_node_free(node);1126 1127 return node;1128}1129 1130/* Move the "node" pointer to the parent of the node it currently points to.1131 */1132__isl_give isl_schedule_node *isl_schedule_node_parent(1133 __isl_take isl_schedule_node *node)1134{1135 if (!node)1136 return NULL;1137 if (!isl_schedule_node_has_parent(node))1138 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,1139 "node has no parent",1140 return isl_schedule_node_free(node));1141 return isl_schedule_node_ancestor(node, 1);1142}1143 1144/* Move the "node" pointer to the parent of its parent.1145 */1146__isl_give isl_schedule_node *isl_schedule_node_grandparent(1147 __isl_take isl_schedule_node *node)1148{1149 return isl_schedule_node_ancestor(node, 2);1150}1151 1152/* Move the "node" pointer to the root of its schedule tree.1153 */1154__isl_give isl_schedule_node *isl_schedule_node_root(1155 __isl_take isl_schedule_node *node)1156{1157 isl_size n;1158 1159 if (!node)1160 return NULL;1161 n = isl_schedule_node_get_tree_depth(node);1162 if (n < 0)1163 return isl_schedule_node_free(node);1164 return isl_schedule_node_ancestor(node, n);1165}1166 1167/* Move the "node" pointer to the child at position "pos" of the node1168 * it currently points to.1169 */1170__isl_give isl_schedule_node *isl_schedule_node_child(1171 __isl_take isl_schedule_node *node, int pos)1172{1173 isl_size n;1174 isl_ctx *ctx;1175 isl_schedule_tree *tree;1176 int *child_pos;1177 1178 node = isl_schedule_node_cow(node);1179 if (!node)1180 return NULL;1181 if (!isl_schedule_node_has_children(node))1182 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,1183 "node has no children",1184 return isl_schedule_node_free(node));1185 1186 ctx = isl_schedule_node_get_ctx(node);1187 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);1188 if (n < 0)1189 return isl_schedule_node_free(node);1190 child_pos = isl_realloc_array(ctx, node->child_pos, int, n + 1);1191 if (!child_pos)1192 return isl_schedule_node_free(node);1193 node->child_pos = child_pos;1194 node->child_pos[n] = pos;1195 1196 node->ancestors = isl_schedule_tree_list_add(node->ancestors,1197 isl_schedule_tree_copy(node->tree));1198 tree = node->tree;1199 if (isl_schedule_tree_has_children(tree))1200 tree = isl_schedule_tree_get_child(tree, pos);1201 else1202 tree = isl_schedule_node_get_leaf(node);1203 isl_schedule_tree_free(node->tree);1204 node->tree = tree;1205 1206 if (!node->tree || !node->ancestors)1207 return isl_schedule_node_free(node);1208 1209 return node;1210}1211 1212/* Move the "node" pointer to the child at position "pos2" of the child1213 * at position "pos1".1214 */1215__isl_give isl_schedule_node *isl_schedule_node_grandchild(1216 __isl_take isl_schedule_node *node, int pos1, int pos2)1217{1218 node = isl_schedule_node_child(node, pos1);1219 node = isl_schedule_node_child(node, pos2);1220 return node;1221}1222 1223/* Move the "node" pointer to the first child of the node1224 * it currently points to.1225 */1226__isl_give isl_schedule_node *isl_schedule_node_first_child(1227 __isl_take isl_schedule_node *node)1228{1229 return isl_schedule_node_child(node, 0);1230}1231 1232/* Move the "node" pointer to the child of this node's parent in1233 * the previous child position.1234 */1235__isl_give isl_schedule_node *isl_schedule_node_previous_sibling(1236 __isl_take isl_schedule_node *node)1237{1238 isl_size n;1239 isl_schedule_tree *parent, *tree;1240 1241 node = isl_schedule_node_cow(node);1242 if (!node)1243 return NULL;1244 if (!isl_schedule_node_has_previous_sibling(node))1245 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,1246 "node has no previous sibling",1247 return isl_schedule_node_free(node));1248 1249 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);1250 if (n < 0)1251 return isl_schedule_node_free(node);1252 parent = isl_schedule_tree_list_get_schedule_tree(node->ancestors,1253 n - 1);1254 if (!parent)1255 return isl_schedule_node_free(node);1256 node->child_pos[n - 1]--;1257 tree = isl_schedule_tree_list_get_schedule_tree(parent->children,1258 node->child_pos[n - 1]);1259 isl_schedule_tree_free(parent);1260 if (!tree)1261 return isl_schedule_node_free(node);1262 isl_schedule_tree_free(node->tree);1263 node->tree = tree;1264 1265 return node;1266}1267 1268/* Move the "node" pointer to the child of this node's parent in1269 * the next child position.1270 */1271__isl_give isl_schedule_node *isl_schedule_node_next_sibling(1272 __isl_take isl_schedule_node *node)1273{1274 isl_size n;1275 isl_schedule_tree *parent, *tree;1276 1277 node = isl_schedule_node_cow(node);1278 if (!node)1279 return NULL;1280 if (!isl_schedule_node_has_next_sibling(node))1281 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,1282 "node has no next sibling",1283 return isl_schedule_node_free(node));1284 1285 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);1286 if (n < 0)1287 return isl_schedule_node_free(node);1288 parent = isl_schedule_tree_list_get_schedule_tree(node->ancestors,1289 n - 1);1290 if (!parent)1291 return isl_schedule_node_free(node);1292 node->child_pos[n - 1]++;1293 tree = isl_schedule_tree_list_get_schedule_tree(parent->children,1294 node->child_pos[n - 1]);1295 isl_schedule_tree_free(parent);1296 if (!tree)1297 return isl_schedule_node_free(node);1298 isl_schedule_tree_free(node->tree);1299 node->tree = tree;1300 1301 return node;1302}1303 1304/* Return a copy to the child at position "pos" of "node".1305 */1306__isl_give isl_schedule_node *isl_schedule_node_get_child(1307 __isl_keep isl_schedule_node *node, int pos)1308{1309 return isl_schedule_node_child(isl_schedule_node_copy(node), pos);1310}1311 1312/* Traverse the descendant of "node" in depth-first order, including1313 * "node" itself. Call "enter" whenever a node is entered and "leave"1314 * whenever a node is left. The callback "enter" is responsible1315 * for moving to the deepest initial subtree of its argument that1316 * should be traversed.1317 */1318static __isl_give isl_schedule_node *traverse(1319 __isl_take isl_schedule_node *node,1320 __isl_give isl_schedule_node *(*enter)(1321 __isl_take isl_schedule_node *node, void *user),1322 __isl_give isl_schedule_node *(*leave)(1323 __isl_take isl_schedule_node *node, void *user),1324 void *user)1325{1326 isl_size depth;1327 isl_size node_depth;1328 1329 depth = isl_schedule_node_get_tree_depth(node);1330 if (depth < 0)1331 return isl_schedule_node_free(node);1332 1333 do {1334 node = enter(node, user);1335 node = leave(node, user);1336 while ((node_depth = isl_schedule_node_get_tree_depth(node)) >1337 depth &&1338 !isl_schedule_node_has_next_sibling(node)) {1339 node = isl_schedule_node_parent(node);1340 node = leave(node, user);1341 }1342 if (node_depth < 0)1343 return isl_schedule_node_free(node);1344 if (node_depth > depth)1345 node = isl_schedule_node_next_sibling(node);1346 } while (node_depth > depth);1347 1348 return node;1349}1350 1351/* Internal data structure for isl_schedule_node_foreach_descendant_top_down.1352 *1353 * "fn" is the user-specified callback function.1354 * "user" is the user-specified argument for the callback.1355 */1356struct isl_schedule_node_preorder_data {1357 isl_bool (*fn)(__isl_keep isl_schedule_node *node, void *user);1358 void *user;1359};1360 1361/* Callback for "traverse" to enter a node and to move1362 * to the deepest initial subtree that should be traversed1363 * for use in a preorder visit.1364 *1365 * If the user callback returns a negative value, then we abort1366 * the traversal. If this callback returns zero, then we skip1367 * the subtree rooted at the current node. Otherwise, we move1368 * down to the first child and repeat the process until a leaf1369 * is reached.1370 */1371static __isl_give isl_schedule_node *preorder_enter(1372 __isl_take isl_schedule_node *node, void *user)1373{1374 struct isl_schedule_node_preorder_data *data = user;1375 1376 if (!node)1377 return NULL;1378 1379 do {1380 isl_bool r;1381 1382 r = data->fn(node, data->user);1383 if (r < 0)1384 return isl_schedule_node_free(node);1385 if (r == isl_bool_false)1386 return node;1387 } while (isl_schedule_node_has_children(node) &&1388 (node = isl_schedule_node_first_child(node)) != NULL);1389 1390 return node;1391}1392 1393/* Callback for "traverse" to leave a node1394 * for use in a preorder visit.1395 * Since we already visited the node when we entered it,1396 * we do not need to do anything here.1397 */1398static __isl_give isl_schedule_node *preorder_leave(1399 __isl_take isl_schedule_node *node, void *user)1400{1401 return node;1402}1403 1404/* Traverse the descendants of "node" (including the node itself)1405 * in depth first preorder.1406 *1407 * If "fn" returns isl_bool_error on any of the nodes,1408 * then the traversal is aborted.1409 * If "fn" returns isl_bool_false on any of the nodes, then the subtree rooted1410 * at that node is skipped.1411 *1412 * Return isl_stat_ok on success and isl_stat_error on failure.1413 */1414isl_stat isl_schedule_node_foreach_descendant_top_down(1415 __isl_keep isl_schedule_node *node,1416 isl_bool (*fn)(__isl_keep isl_schedule_node *node, void *user),1417 void *user)1418{1419 struct isl_schedule_node_preorder_data data = { fn, user };1420 1421 node = isl_schedule_node_copy(node);1422 node = traverse(node, &preorder_enter, &preorder_leave, &data);1423 isl_schedule_node_free(node);1424 1425 return node ? isl_stat_ok : isl_stat_error;1426}1427 1428/* Internal data structure for isl_schedule_node_every_descendant.1429 *1430 * "test" is the user-specified callback function.1431 * "user" is the user-specified callback function argument.1432 *1433 * "failed" is initialized to 0 and set to 1 if "test" fails1434 * on any node.1435 */1436struct isl_union_map_every_data {1437 isl_bool (*test)(__isl_keep isl_schedule_node *node, void *user);1438 void *user;1439 int failed;1440};1441 1442/* isl_schedule_node_foreach_descendant_top_down callback1443 * that sets data->failed if data->test returns false and1444 * subsequently aborts the traversal.1445 */1446static isl_bool call_every(__isl_keep isl_schedule_node *node, void *user)1447{1448 struct isl_union_map_every_data *data = user;1449 isl_bool r;1450 1451 r = data->test(node, data->user);1452 if (r < 0)1453 return isl_bool_error;1454 if (r)1455 return isl_bool_true;1456 data->failed = 1;1457 return isl_bool_error;1458}1459 1460/* Does "test" succeed on every descendant of "node" (including "node" itself)?1461 */1462isl_bool isl_schedule_node_every_descendant(__isl_keep isl_schedule_node *node,1463 isl_bool (*test)(__isl_keep isl_schedule_node *node, void *user),1464 void *user)1465{1466 struct isl_union_map_every_data data = { test, user, 0 };1467 isl_stat r;1468 1469 r = isl_schedule_node_foreach_descendant_top_down(node, &call_every,1470 &data);1471 if (r >= 0)1472 return isl_bool_true;1473 if (data.failed)1474 return isl_bool_false;1475 return isl_bool_error;1476}1477 1478/* Internal data structure for isl_schedule_node_map_descendant_bottom_up.1479 *1480 * "fn" is the user-specified callback function.1481 * "user" is the user-specified argument for the callback.1482 */1483struct isl_schedule_node_postorder_data {1484 __isl_give isl_schedule_node *(*fn)(__isl_take isl_schedule_node *node,1485 void *user);1486 void *user;1487};1488 1489/* Callback for "traverse" to enter a node and to move1490 * to the deepest initial subtree that should be traversed1491 * for use in a postorder visit.1492 *1493 * Since we are performing a postorder visit, we only need1494 * to move to the deepest initial leaf here.1495 */1496static __isl_give isl_schedule_node *postorder_enter(1497 __isl_take isl_schedule_node *node, void *user)1498{1499 while (node && isl_schedule_node_has_children(node))1500 node = isl_schedule_node_first_child(node);1501 1502 return node;1503}1504 1505/* Callback for "traverse" to leave a node1506 * for use in a postorder visit.1507 *1508 * Since we are performing a postorder visit, we need1509 * to call the user callback here.1510 */1511static __isl_give isl_schedule_node *postorder_leave(1512 __isl_take isl_schedule_node *node, void *user)1513{1514 struct isl_schedule_node_postorder_data *data = user;1515 1516 return data->fn(node, data->user);1517}1518 1519/* Traverse the descendants of "node" (including the node itself)1520 * in depth first postorder, allowing the user to modify the visited node.1521 * The traversal continues from the node returned by the callback function.1522 * It is the responsibility of the user to ensure that this does not1523 * lead to an infinite loop. It is safest to always return a pointer1524 * to the same position (same ancestors and child positions) as the input node.1525 */1526__isl_give isl_schedule_node *isl_schedule_node_map_descendant_bottom_up(1527 __isl_take isl_schedule_node *node,1528 __isl_give isl_schedule_node *(*fn)(__isl_take isl_schedule_node *node,1529 void *user), void *user)1530{1531 struct isl_schedule_node_postorder_data data = { fn, user };1532 1533 return traverse(node, &postorder_enter, &postorder_leave, &data);1534}1535 1536/* Traverse the ancestors of "node" from the root down to and including1537 * the parent of "node", calling "fn" on each of them.1538 *1539 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.1540 *1541 * Return 0 on success and -1 on failure.1542 */1543isl_stat isl_schedule_node_foreach_ancestor_top_down(1544 __isl_keep isl_schedule_node *node,1545 isl_stat (*fn)(__isl_keep isl_schedule_node *node, void *user),1546 void *user)1547{1548 int i;1549 isl_size n;1550 1551 n = isl_schedule_node_get_tree_depth(node);1552 if (n < 0)1553 return isl_stat_error;1554 1555 for (i = 0; i < n; ++i) {1556 isl_schedule_node *ancestor;1557 isl_stat r;1558 1559 ancestor = isl_schedule_node_copy(node);1560 ancestor = isl_schedule_node_ancestor(ancestor, n - i);1561 r = fn(ancestor, user);1562 isl_schedule_node_free(ancestor);1563 if (r < 0)1564 return isl_stat_error;1565 }1566 1567 return isl_stat_ok;1568}1569 1570/* Is any node in the subtree rooted at "node" anchored?1571 * That is, do any of these nodes reference the outer band nodes?1572 */1573isl_bool isl_schedule_node_is_subtree_anchored(1574 __isl_keep isl_schedule_node *node)1575{1576 if (!node)1577 return isl_bool_error;1578 return isl_schedule_tree_is_subtree_anchored(node->tree);1579}1580 1581/* Return the number of members in the given band node.1582 */1583isl_size isl_schedule_node_band_n_member(__isl_keep isl_schedule_node *node)1584{1585 if (!node)1586 return isl_size_error;1587 return isl_schedule_tree_band_n_member(node->tree);1588}1589 1590/* Is the band member at position "pos" of the band node "node"1591 * marked coincident?1592 */1593isl_bool isl_schedule_node_band_member_get_coincident(1594 __isl_keep isl_schedule_node *node, int pos)1595{1596 if (!node)1597 return isl_bool_error;1598 return isl_schedule_tree_band_member_get_coincident(node->tree, pos);1599}1600 1601/* Mark the band member at position "pos" the band node "node"1602 * as being coincident or not according to "coincident".1603 */1604__isl_give isl_schedule_node *isl_schedule_node_band_member_set_coincident(1605 __isl_take isl_schedule_node *node, int pos, int coincident)1606{1607 int c;1608 isl_schedule_tree *tree;1609 1610 if (!node)1611 return NULL;1612 c = isl_schedule_node_band_member_get_coincident(node, pos);1613 if (c == coincident)1614 return node;1615 1616 tree = isl_schedule_tree_copy(node->tree);1617 tree = isl_schedule_tree_band_member_set_coincident(tree, pos,1618 coincident);1619 node = isl_schedule_node_graft_tree(node, tree);1620 1621 return node;1622}1623 1624/* Is the band node "node" marked permutable?1625 */1626isl_bool isl_schedule_node_band_get_permutable(1627 __isl_keep isl_schedule_node *node)1628{1629 if (!node)1630 return isl_bool_error;1631 1632 return isl_schedule_tree_band_get_permutable(node->tree);1633}1634 1635/* Mark the band node "node" permutable or not according to "permutable"?1636 */1637__isl_give isl_schedule_node *isl_schedule_node_band_set_permutable(1638 __isl_take isl_schedule_node *node, int permutable)1639{1640 isl_schedule_tree *tree;1641 1642 if (!node)1643 return NULL;1644 if (isl_schedule_node_band_get_permutable(node) == permutable)1645 return node;1646 1647 tree = isl_schedule_tree_copy(node->tree);1648 tree = isl_schedule_tree_band_set_permutable(tree, permutable);1649 node = isl_schedule_node_graft_tree(node, tree);1650 1651 return node;1652}1653 1654/* Return the schedule space of the band node.1655 */1656__isl_give isl_space *isl_schedule_node_band_get_space(1657 __isl_keep isl_schedule_node *node)1658{1659 if (!node)1660 return NULL;1661 1662 return isl_schedule_tree_band_get_space(node->tree);1663}1664 1665/* Return the schedule of the band node in isolation.1666 */1667__isl_give isl_multi_union_pw_aff *isl_schedule_node_band_get_partial_schedule(1668 __isl_keep isl_schedule_node *node)1669{1670 if (!node)1671 return NULL;1672 1673 return isl_schedule_tree_band_get_partial_schedule(node->tree);1674}1675 1676/* Return the schedule of the band node in isolation in the form of1677 * an isl_union_map.1678 *1679 * If the band does not have any members, then we construct a universe map1680 * with the universe of the domain elements reaching the node as domain.1681 * Otherwise, we extract an isl_multi_union_pw_aff representation and1682 * convert that to an isl_union_map.1683 */1684__isl_give isl_union_map *isl_schedule_node_band_get_partial_schedule_union_map(1685 __isl_keep isl_schedule_node *node)1686{1687 isl_size n;1688 isl_multi_union_pw_aff *mupa;1689 1690 if (!node)1691 return NULL;1692 1693 if (isl_schedule_node_get_type(node) != isl_schedule_node_band)1694 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,1695 "not a band node", return NULL);1696 n = isl_schedule_node_band_n_member(node);1697 if (n < 0)1698 return NULL;1699 if (n == 0) {1700 isl_union_set *domain;1701 1702 domain = isl_schedule_node_get_universe_domain(node);1703 return isl_union_map_from_domain(domain);1704 }1705 1706 mupa = isl_schedule_node_band_get_partial_schedule(node);1707 return isl_union_map_from_multi_union_pw_aff(mupa);1708}1709 1710/* Return the loop AST generation type for the band member of band node "node"1711 * at position "pos".1712 */1713enum isl_ast_loop_type isl_schedule_node_band_member_get_ast_loop_type(1714 __isl_keep isl_schedule_node *node, int pos)1715{1716 if (!node)1717 return isl_ast_loop_error;1718 1719 return isl_schedule_tree_band_member_get_ast_loop_type(node->tree, pos);1720}1721 1722/* Set the loop AST generation type for the band member of band node "node"1723 * at position "pos" to "type".1724 */1725__isl_give isl_schedule_node *isl_schedule_node_band_member_set_ast_loop_type(1726 __isl_take isl_schedule_node *node, int pos,1727 enum isl_ast_loop_type type)1728{1729 isl_schedule_tree *tree;1730 1731 if (!node)1732 return NULL;1733 1734 tree = isl_schedule_tree_copy(node->tree);1735 tree = isl_schedule_tree_band_member_set_ast_loop_type(tree, pos, type);1736 return isl_schedule_node_graft_tree(node, tree);1737}1738 1739/* Return the loop AST generation type for the band member of band node "node"1740 * at position "pos" for the isolated part.1741 */1742enum isl_ast_loop_type isl_schedule_node_band_member_get_isolate_ast_loop_type(1743 __isl_keep isl_schedule_node *node, int pos)1744{1745 if (!node)1746 return isl_ast_loop_error;1747 1748 return isl_schedule_tree_band_member_get_isolate_ast_loop_type(1749 node->tree, pos);1750}1751 1752/* Set the loop AST generation type for the band member of band node "node"1753 * at position "pos" for the isolated part to "type".1754 */1755__isl_give isl_schedule_node *1756isl_schedule_node_band_member_set_isolate_ast_loop_type(1757 __isl_take isl_schedule_node *node, int pos,1758 enum isl_ast_loop_type type)1759{1760 isl_schedule_tree *tree;1761 1762 if (!node)1763 return NULL;1764 1765 tree = isl_schedule_tree_copy(node->tree);1766 tree = isl_schedule_tree_band_member_set_isolate_ast_loop_type(tree,1767 pos, type);1768 return isl_schedule_node_graft_tree(node, tree);1769}1770 1771/* Return the AST build options associated to band node "node".1772 */1773__isl_give isl_union_set *isl_schedule_node_band_get_ast_build_options(1774 __isl_keep isl_schedule_node *node)1775{1776 if (!node)1777 return NULL;1778 1779 return isl_schedule_tree_band_get_ast_build_options(node->tree);1780}1781 1782/* Replace the AST build options associated to band node "node" by "options".1783 */1784__isl_give isl_schedule_node *isl_schedule_node_band_set_ast_build_options(1785 __isl_take isl_schedule_node *node, __isl_take isl_union_set *options)1786{1787 isl_schedule_tree *tree;1788 1789 if (!node || !options)1790 goto error;1791 1792 tree = isl_schedule_tree_copy(node->tree);1793 tree = isl_schedule_tree_band_set_ast_build_options(tree, options);1794 return isl_schedule_node_graft_tree(node, tree);1795error:1796 isl_schedule_node_free(node);1797 isl_union_set_free(options);1798 return NULL;1799}1800 1801/* Return the "isolate" option associated to band node "node".1802 */1803__isl_give isl_set *isl_schedule_node_band_get_ast_isolate_option(1804 __isl_keep isl_schedule_node *node)1805{1806 isl_size depth;1807 1808 depth = isl_schedule_node_get_schedule_depth(node);1809 if (depth < 0)1810 return NULL;1811 1812 return isl_schedule_tree_band_get_ast_isolate_option(node->tree, depth);1813}1814 1815/* Make sure that that spaces of "node" and "mv" are the same.1816 * Return -1 on error, reporting the error to the user.1817 */1818static int check_space_multi_val(__isl_keep isl_schedule_node *node,1819 __isl_keep isl_multi_val *mv)1820{1821 isl_space *node_space, *mv_space;1822 int equal;1823 1824 node_space = isl_schedule_node_band_get_space(node);1825 mv_space = isl_multi_val_get_space(mv);1826 equal = isl_space_tuple_is_equal(node_space, isl_dim_set,1827 mv_space, isl_dim_set);1828 isl_space_free(mv_space);1829 isl_space_free(node_space);1830 if (equal < 0)1831 return -1;1832 if (!equal)1833 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,1834 "spaces don't match", return -1);1835 1836 return 0;1837}1838 1839/* Multiply the partial schedule of the band node "node"1840 * with the factors in "mv".1841 */1842__isl_give isl_schedule_node *isl_schedule_node_band_scale(1843 __isl_take isl_schedule_node *node, __isl_take isl_multi_val *mv)1844{1845 isl_schedule_tree *tree;1846 int anchored;1847 1848 if (!node || !mv)1849 goto error;1850 if (check_space_multi_val(node, mv) < 0)1851 goto error;1852 anchored = isl_schedule_node_is_subtree_anchored(node);1853 if (anchored < 0)1854 goto error;1855 if (anchored)1856 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,1857 "cannot scale band node with anchored subtree",1858 goto error);1859 1860 tree = isl_schedule_node_get_tree(node);1861 tree = isl_schedule_tree_band_scale(tree, mv);1862 return isl_schedule_node_graft_tree(node, tree);1863error:1864 isl_multi_val_free(mv);1865 isl_schedule_node_free(node);1866 return NULL;1867}1868 1869/* Divide the partial schedule of the band node "node"1870 * by the factors in "mv".1871 */1872__isl_give isl_schedule_node *isl_schedule_node_band_scale_down(1873 __isl_take isl_schedule_node *node, __isl_take isl_multi_val *mv)1874{1875 isl_schedule_tree *tree;1876 int anchored;1877 1878 if (!node || !mv)1879 goto error;1880 if (check_space_multi_val(node, mv) < 0)1881 goto error;1882 anchored = isl_schedule_node_is_subtree_anchored(node);1883 if (anchored < 0)1884 goto error;1885 if (anchored)1886 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,1887 "cannot scale down band node with anchored subtree",1888 goto error);1889 1890 tree = isl_schedule_node_get_tree(node);1891 tree = isl_schedule_tree_band_scale_down(tree, mv);1892 return isl_schedule_node_graft_tree(node, tree);1893error:1894 isl_multi_val_free(mv);1895 isl_schedule_node_free(node);1896 return NULL;1897}1898 1899/* Reduce the partial schedule of the band node "node"1900 * modulo the factors in "mv".1901 */1902__isl_give isl_schedule_node *isl_schedule_node_band_mod(1903 __isl_take isl_schedule_node *node, __isl_take isl_multi_val *mv)1904{1905 isl_schedule_tree *tree;1906 isl_bool anchored;1907 1908 if (!node || !mv)1909 goto error;1910 if (check_space_multi_val(node, mv) < 0)1911 goto error;1912 anchored = isl_schedule_node_is_subtree_anchored(node);1913 if (anchored < 0)1914 goto error;1915 if (anchored)1916 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,1917 "cannot perform mod on band node with anchored subtree",1918 goto error);1919 1920 tree = isl_schedule_node_get_tree(node);1921 tree = isl_schedule_tree_band_mod(tree, mv);1922 return isl_schedule_node_graft_tree(node, tree);1923error:1924 isl_multi_val_free(mv);1925 isl_schedule_node_free(node);1926 return NULL;1927}1928 1929/* Make sure that that spaces of "node" and "mupa" are the same.1930 * Return isl_stat_error on error, reporting the error to the user.1931 */1932static isl_stat check_space_multi_union_pw_aff(1933 __isl_keep isl_schedule_node *node,1934 __isl_keep isl_multi_union_pw_aff *mupa)1935{1936 isl_space *node_space, *mupa_space;1937 isl_bool equal;1938 1939 node_space = isl_schedule_node_band_get_space(node);1940 mupa_space = isl_multi_union_pw_aff_get_space(mupa);1941 equal = isl_space_tuple_is_equal(node_space, isl_dim_set,1942 mupa_space, isl_dim_set);1943 isl_space_free(mupa_space);1944 isl_space_free(node_space);1945 if (equal < 0)1946 return isl_stat_error;1947 if (!equal)1948 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,1949 "spaces don't match", return isl_stat_error);1950 1951 return isl_stat_ok;1952}1953 1954/* Shift the partial schedule of the band node "node" by "shift".1955 */1956__isl_give isl_schedule_node *isl_schedule_node_band_shift(1957 __isl_take isl_schedule_node *node,1958 __isl_take isl_multi_union_pw_aff *shift)1959{1960 isl_schedule_tree *tree;1961 int anchored;1962 1963 if (!node || !shift)1964 goto error;1965 if (check_space_multi_union_pw_aff(node, shift) < 0)1966 goto error;1967 anchored = isl_schedule_node_is_subtree_anchored(node);1968 if (anchored < 0)1969 goto error;1970 if (anchored)1971 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,1972 "cannot shift band node with anchored subtree",1973 goto error);1974 1975 tree = isl_schedule_node_get_tree(node);1976 tree = isl_schedule_tree_band_shift(tree, shift);1977 return isl_schedule_node_graft_tree(node, tree);1978error:1979 isl_multi_union_pw_aff_free(shift);1980 isl_schedule_node_free(node);1981 return NULL;1982}1983 1984/* Tile "node" with tile sizes "sizes".1985 *1986 * The current node is replaced by two nested nodes corresponding1987 * to the tile dimensions and the point dimensions.1988 *1989 * Return a pointer to the outer (tile) node.1990 *1991 * If any of the descendants of "node" depend on the set of outer band nodes,1992 * then we refuse to tile the node.1993 *1994 * If the scale tile loops option is set, then the tile loops1995 * are scaled by the tile sizes. If the shift point loops option is set,1996 * then the point loops are shifted to start at zero.1997 * In particular, these options affect the tile and point loop schedules1998 * as follows1999 *2000 * scale shift original tile point2001 *2002 * 0 0 i floor(i/s) i2003 * 1 0 i s * floor(i/s) i2004 * 0 1 i floor(i/s) i - s * floor(i/s)2005 * 1 1 i s * floor(i/s) i - s * floor(i/s)2006 */2007__isl_give isl_schedule_node *isl_schedule_node_band_tile(2008 __isl_take isl_schedule_node *node, __isl_take isl_multi_val *sizes)2009{2010 isl_schedule_tree *tree;2011 int anchored;2012 2013 if (!node || !sizes)2014 goto error;2015 anchored = isl_schedule_node_is_subtree_anchored(node);2016 if (anchored < 0)2017 goto error;2018 if (anchored)2019 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,2020 "cannot tile band node with anchored subtree",2021 goto error);2022 2023 if (check_space_multi_val(node, sizes) < 0)2024 goto error;2025 2026 tree = isl_schedule_node_get_tree(node);2027 tree = isl_schedule_tree_band_tile(tree, sizes);2028 return isl_schedule_node_graft_tree(node, tree);2029error:2030 isl_multi_val_free(sizes);2031 isl_schedule_node_free(node);2032 return NULL;2033}2034 2035/* Move the band node "node" down to all the leaves in the subtree2036 * rooted at "node".2037 * Return a pointer to the node in the resulting tree that is in the same2038 * position as the node pointed to by "node" in the original tree.2039 *2040 * If the node only has a leaf child, then nothing needs to be done.2041 * Otherwise, the child of the node is removed and the result is2042 * appended to all the leaves in the subtree rooted at the original child.2043 * Since the node is moved to the leaves, it needs to be expanded2044 * according to the expansion, if any, defined by that subtree.2045 * In the end, the original node is replaced by the result of2046 * attaching copies of the expanded node to the leaves.2047 *2048 * If any of the nodes in the subtree rooted at "node" depend on2049 * the set of outer band nodes then we refuse to sink the band node.2050 */2051__isl_give isl_schedule_node *isl_schedule_node_band_sink(2052 __isl_take isl_schedule_node *node)2053{2054 enum isl_schedule_node_type type;2055 isl_schedule_tree *tree, *child;2056 isl_union_pw_multi_aff *contraction;2057 isl_bool anchored;2058 isl_size n;2059 2060 if (!node)2061 return NULL;2062 2063 type = isl_schedule_node_get_type(node);2064 if (type != isl_schedule_node_band)2065 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,2066 "not a band node", return isl_schedule_node_free(node));2067 anchored = isl_schedule_node_is_subtree_anchored(node);2068 if (anchored < 0)2069 return isl_schedule_node_free(node);2070 if (anchored)2071 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,2072 "cannot sink band node in anchored subtree",2073 return isl_schedule_node_free(node));2074 n = isl_schedule_tree_n_children(node->tree);2075 if (n < 0)2076 return isl_schedule_node_free(node);2077 if (n == 0)2078 return node;2079 2080 contraction = isl_schedule_node_get_subtree_contraction(node);2081 2082 tree = isl_schedule_node_get_tree(node);2083 child = isl_schedule_tree_get_child(tree, 0);2084 tree = isl_schedule_tree_reset_children(tree);2085 tree = isl_schedule_tree_pullback_union_pw_multi_aff(tree, contraction);2086 tree = isl_schedule_tree_append_to_leaves(child, tree);2087 2088 return isl_schedule_node_graft_tree(node, tree);2089}2090 2091/* Split "node" into two nested band nodes, one with the first "pos"2092 * dimensions and one with the remaining dimensions.2093 * The schedules of the two band nodes live in anonymous spaces.2094 * The loop AST generation type options and the isolate option2095 * are split over the two band nodes.2096 */2097__isl_give isl_schedule_node *isl_schedule_node_band_split(2098 __isl_take isl_schedule_node *node, int pos)2099{2100 isl_size depth;2101 isl_schedule_tree *tree;2102 2103 depth = isl_schedule_node_get_schedule_depth(node);2104 if (depth < 0)2105 return isl_schedule_node_free(node);2106 tree = isl_schedule_node_get_tree(node);2107 tree = isl_schedule_tree_band_split(tree, pos, depth);2108 return isl_schedule_node_graft_tree(node, tree);2109}2110 2111/* Return the context of the context node "node".2112 */2113__isl_give isl_set *isl_schedule_node_context_get_context(2114 __isl_keep isl_schedule_node *node)2115{2116 if (!node)2117 return NULL;2118 2119 return isl_schedule_tree_context_get_context(node->tree);2120}2121 2122/* Return the domain of the domain node "node".2123 */2124__isl_give isl_union_set *isl_schedule_node_domain_get_domain(2125 __isl_keep isl_schedule_node *node)2126{2127 if (!node)2128 return NULL;2129 2130 return isl_schedule_tree_domain_get_domain(node->tree);2131}2132 2133/* Return the expansion map of expansion node "node".2134 */2135__isl_give isl_union_map *isl_schedule_node_expansion_get_expansion(2136 __isl_keep isl_schedule_node *node)2137{2138 if (!node)2139 return NULL;2140 2141 return isl_schedule_tree_expansion_get_expansion(node->tree);2142}2143 2144/* Return the contraction of expansion node "node".2145 */2146__isl_give isl_union_pw_multi_aff *isl_schedule_node_expansion_get_contraction(2147 __isl_keep isl_schedule_node *node)2148{2149 if (!node)2150 return NULL;2151 2152 return isl_schedule_tree_expansion_get_contraction(node->tree);2153}2154 2155/* Replace the contraction and the expansion of the expansion node "node"2156 * by "contraction" and "expansion".2157 */2158__isl_give isl_schedule_node *2159isl_schedule_node_expansion_set_contraction_and_expansion(2160 __isl_take isl_schedule_node *node,2161 __isl_take isl_union_pw_multi_aff *contraction,2162 __isl_take isl_union_map *expansion)2163{2164 isl_schedule_tree *tree;2165 2166 if (!node || !contraction || !expansion)2167 goto error;2168 2169 tree = isl_schedule_tree_copy(node->tree);2170 tree = isl_schedule_tree_expansion_set_contraction_and_expansion(tree,2171 contraction, expansion);2172 return isl_schedule_node_graft_tree(node, tree);2173error:2174 isl_schedule_node_free(node);2175 isl_union_pw_multi_aff_free(contraction);2176 isl_union_map_free(expansion);2177 return NULL;2178}2179 2180/* Return the extension of the extension node "node".2181 */2182__isl_give isl_union_map *isl_schedule_node_extension_get_extension(2183 __isl_keep isl_schedule_node *node)2184{2185 if (!node)2186 return NULL;2187 2188 return isl_schedule_tree_extension_get_extension(node->tree);2189}2190 2191/* Replace the extension of extension node "node" by "extension".2192 */2193__isl_give isl_schedule_node *isl_schedule_node_extension_set_extension(2194 __isl_take isl_schedule_node *node, __isl_take isl_union_map *extension)2195{2196 isl_schedule_tree *tree;2197 2198 if (!node || !extension)2199 goto error;2200 2201 tree = isl_schedule_tree_copy(node->tree);2202 tree = isl_schedule_tree_extension_set_extension(tree, extension);2203 return isl_schedule_node_graft_tree(node, tree);2204error:2205 isl_schedule_node_free(node);2206 isl_union_map_free(extension);2207 return NULL;2208}2209 2210/* Return the filter of the filter node "node".2211 */2212__isl_give isl_union_set *isl_schedule_node_filter_get_filter(2213 __isl_keep isl_schedule_node *node)2214{2215 if (!node)2216 return NULL;2217 2218 return isl_schedule_tree_filter_get_filter(node->tree);2219}2220 2221/* Replace the filter of filter node "node" by "filter".2222 */2223__isl_give isl_schedule_node *isl_schedule_node_filter_set_filter(2224 __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter)2225{2226 isl_schedule_tree *tree;2227 2228 if (!node || !filter)2229 goto error;2230 2231 tree = isl_schedule_tree_copy(node->tree);2232 tree = isl_schedule_tree_filter_set_filter(tree, filter);2233 return isl_schedule_node_graft_tree(node, tree);2234error:2235 isl_schedule_node_free(node);2236 isl_union_set_free(filter);2237 return NULL;2238}2239 2240/* Intersect the filter of filter node "node" with "filter".2241 *2242 * If the filter of the node is already a subset of "filter",2243 * then leave the node unchanged.2244 */2245__isl_give isl_schedule_node *isl_schedule_node_filter_intersect_filter(2246 __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter)2247{2248 isl_union_set *node_filter = NULL;2249 isl_bool subset;2250 2251 if (!node || !filter)2252 goto error;2253 2254 node_filter = isl_schedule_node_filter_get_filter(node);2255 subset = isl_union_set_is_subset(node_filter, filter);2256 if (subset < 0)2257 goto error;2258 if (subset) {2259 isl_union_set_free(node_filter);2260 isl_union_set_free(filter);2261 return node;2262 }2263 node_filter = isl_union_set_intersect(node_filter, filter);2264 node = isl_schedule_node_filter_set_filter(node, node_filter);2265 return node;2266error:2267 isl_schedule_node_free(node);2268 isl_union_set_free(node_filter);2269 isl_union_set_free(filter);2270 return NULL;2271}2272 2273/* Return the guard of the guard node "node".2274 */2275__isl_give isl_set *isl_schedule_node_guard_get_guard(2276 __isl_keep isl_schedule_node *node)2277{2278 if (!node)2279 return NULL;2280 2281 return isl_schedule_tree_guard_get_guard(node->tree);2282}2283 2284/* Return the mark identifier of the mark node "node".2285 */2286__isl_give isl_id *isl_schedule_node_mark_get_id(2287 __isl_keep isl_schedule_node *node)2288{2289 if (!node)2290 return NULL;2291 2292 return isl_schedule_tree_mark_get_id(node->tree);2293}2294 2295/* Check that "node" is a sequence node.2296 */2297static isl_stat check_is_sequence(__isl_keep isl_schedule_node *node)2298{2299 if (!node)2300 return isl_stat_error;2301 2302 if (isl_schedule_node_get_type(node) != isl_schedule_node_sequence)2303 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,2304 "not a sequence node", return isl_stat_error);2305 2306 return isl_stat_ok;2307}2308 2309/* Replace the child at position "pos" of the sequence node "node"2310 * by the children of sequence root node of "tree".2311 */2312__isl_give isl_schedule_node *isl_schedule_node_sequence_splice(2313 __isl_take isl_schedule_node *node, int pos,2314 __isl_take isl_schedule_tree *tree)2315{2316 isl_schedule_tree *node_tree;2317 2318 if (check_is_sequence(node) < 0 || !tree)2319 goto error;2320 if (isl_schedule_tree_get_type(tree) != isl_schedule_node_sequence)2321 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,2322 "not a sequence node", goto error);2323 node_tree = isl_schedule_node_get_tree(node);2324 node_tree = isl_schedule_tree_sequence_splice(node_tree, pos, tree);2325 node = isl_schedule_node_graft_tree(node, node_tree);2326 2327 return node;2328error:2329 isl_schedule_node_free(node);2330 isl_schedule_tree_free(tree);2331 return NULL;2332}2333 2334/* Given a sequence node "node", with a child at position "pos" that2335 * is also a sequence node, attach the children of that node directly2336 * as children of "node" at that position, replacing the original child.2337 *2338 * The filters of these children are intersected with the filter2339 * of the child at position "pos".2340 */2341__isl_give isl_schedule_node *isl_schedule_node_sequence_splice_child(2342 __isl_take isl_schedule_node *node, int pos)2343{2344 int i;2345 isl_size n;2346 isl_union_set *filter;2347 isl_schedule_node *child;2348 isl_schedule_tree *tree;2349 2350 if (check_is_sequence(node) < 0)2351 return isl_schedule_node_free(node);2352 node = isl_schedule_node_grandchild(node, pos, 0);2353 if (check_is_sequence(node) < 0)2354 return isl_schedule_node_free(node);2355 n = isl_schedule_node_n_children(node);2356 if (n < 0)2357 return isl_schedule_node_free(node);2358 child = isl_schedule_node_copy(node);2359 node = isl_schedule_node_parent(node);2360 filter = isl_schedule_node_filter_get_filter(node);2361 for (i = 0; i < n; ++i) {2362 child = isl_schedule_node_child(child, i);2363 child = isl_schedule_node_filter_intersect_filter(child,2364 isl_union_set_copy(filter));2365 child = isl_schedule_node_parent(child);2366 }2367 isl_union_set_free(filter);2368 tree = isl_schedule_node_get_tree(child);2369 isl_schedule_node_free(child);2370 node = isl_schedule_node_parent(node);2371 node = isl_schedule_node_sequence_splice(node, pos, tree);2372 2373 return node;2374}2375 2376/* Given a sequence node "node", for each child that is also2377 * (the parent of) a sequence node, attach the children of that node directly2378 * as children of "node" at the position of the child,2379 * replacing this original child.2380 *2381 * Since splicing in a child may change the positions of later children,2382 * iterate through the children from last to first.2383 */2384__isl_give isl_schedule_node *isl_schedule_node_sequence_splice_children(2385 __isl_take isl_schedule_node *node)2386{2387 int i;2388 isl_size n;2389 2390 if (check_is_sequence(node) < 0)2391 return isl_schedule_node_free(node);2392 n = isl_schedule_node_n_children(node);2393 if (n < 0)2394 return isl_schedule_node_free(node);2395 2396 for (i = n - 1; i >= 0; --i) {2397 enum isl_schedule_node_type type;2398 int is_seq;2399 2400 node = isl_schedule_node_grandchild(node, i, 0);2401 type = isl_schedule_node_get_type(node);2402 if (type < 0)2403 return isl_schedule_node_free(node);2404 is_seq = type == isl_schedule_node_sequence;2405 node = isl_schedule_node_grandparent(node);2406 2407 if (!is_seq)2408 continue;2409 2410 node = isl_schedule_node_sequence_splice_child(node, i);2411 }2412 2413 return node;2414}2415 2416/* Update the ancestors of "node" to point to the tree that "node"2417 * now points to.2418 * That is, replace the child in the original parent that corresponds2419 * to the current tree position by node->tree and continue updating2420 * the ancestors in the same way until the root is reached.2421 *2422 * If "fn" is not NULL, then it is called on each ancestor as we move up2423 * the tree so that it can modify the ancestor before it is added2424 * to the list of ancestors of the modified node.2425 * The additional "pos" argument records the position2426 * of the "tree" argument in the original schedule tree.2427 *2428 * If "node" originally points to a leaf of the schedule tree, then make sure2429 * that in the end it points to a leaf in the updated schedule tree.2430 */2431static __isl_give isl_schedule_node *update_ancestors(2432 __isl_take isl_schedule_node *node,2433 __isl_give isl_schedule_tree *(*fn)(__isl_take isl_schedule_tree *tree,2434 __isl_keep isl_schedule_node *pos, void *user), void *user)2435{2436 int i;2437 isl_size n;2438 int is_leaf;2439 isl_schedule_tree *tree;2440 isl_schedule_node *pos = NULL;2441 2442 if (fn)2443 pos = isl_schedule_node_copy(node);2444 2445 node = isl_schedule_node_cow(node);2446 if (!node)2447 return isl_schedule_node_free(pos);2448 2449 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);2450 if (n < 0)2451 return isl_schedule_node_free(pos);2452 tree = isl_schedule_tree_copy(node->tree);2453 2454 for (i = n - 1; i >= 0; --i) {2455 isl_schedule_tree *parent;2456 2457 parent = isl_schedule_tree_list_get_schedule_tree(2458 node->ancestors, i);2459 parent = isl_schedule_tree_replace_child(parent,2460 node->child_pos[i], tree);2461 if (fn) {2462 pos = isl_schedule_node_parent(pos);2463 parent = fn(parent, pos, user);2464 }2465 node->ancestors = isl_schedule_tree_list_set_schedule_tree(2466 node->ancestors, i, isl_schedule_tree_copy(parent));2467 2468 tree = parent;2469 }2470 2471 if (fn)2472 isl_schedule_node_free(pos);2473 2474 is_leaf = isl_schedule_tree_is_leaf(node->tree);2475 node->schedule = isl_schedule_set_root(node->schedule, tree);2476 if (is_leaf) {2477 isl_schedule_tree_free(node->tree);2478 node->tree = isl_schedule_node_get_leaf(node);2479 }2480 2481 if (!node->schedule || !node->ancestors)2482 return isl_schedule_node_free(node);2483 2484 return node;2485}2486 2487/* Replace the subtree that "pos" points to by "tree", updating2488 * the ancestors to maintain a consistent state.2489 */2490__isl_give isl_schedule_node *isl_schedule_node_graft_tree(2491 __isl_take isl_schedule_node *pos, __isl_take isl_schedule_tree *tree)2492{2493 if (!tree || !pos)2494 goto error;2495 if (pos->tree == tree) {2496 isl_schedule_tree_free(tree);2497 return pos;2498 }2499 2500 pos = isl_schedule_node_cow(pos);2501 if (!pos)2502 goto error;2503 2504 isl_schedule_tree_free(pos->tree);2505 pos->tree = tree;2506 2507 return update_ancestors(pos, NULL, NULL);2508error:2509 isl_schedule_node_free(pos);2510 isl_schedule_tree_free(tree);2511 return NULL;2512}2513 2514/* Make sure we can insert a node between "node" and its parent.2515 * Return -1 on error, reporting the reason why we cannot insert a node.2516 */2517static int check_insert(__isl_keep isl_schedule_node *node)2518{2519 int has_parent;2520 enum isl_schedule_node_type type;2521 2522 has_parent = isl_schedule_node_has_parent(node);2523 if (has_parent < 0)2524 return -1;2525 if (!has_parent)2526 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,2527 "cannot insert node outside of root", return -1);2528 2529 type = isl_schedule_node_get_parent_type(node);2530 if (type == isl_schedule_node_error)2531 return -1;2532 if (type == isl_schedule_node_set || type == isl_schedule_node_sequence)2533 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,2534 "cannot insert node between set or sequence node "2535 "and its filter children", return -1);2536 2537 return 0;2538}2539 2540/* Insert a band node with partial schedule "mupa" between "node" and2541 * its parent.2542 * Return a pointer to the new band node.2543 *2544 * If any of the nodes in the subtree rooted at "node" depend on2545 * the set of outer band nodes then we refuse to insert the band node.2546 */2547__isl_give isl_schedule_node *isl_schedule_node_insert_partial_schedule(2548 __isl_take isl_schedule_node *node,2549 __isl_take isl_multi_union_pw_aff *mupa)2550{2551 int anchored;2552 isl_schedule_band *band;2553 isl_schedule_tree *tree;2554 2555 if (check_insert(node) < 0)2556 node = isl_schedule_node_free(node);2557 anchored = isl_schedule_node_is_subtree_anchored(node);2558 if (anchored < 0)2559 goto error;2560 if (anchored)2561 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,2562 "cannot insert band node in anchored subtree",2563 goto error);2564 2565 tree = isl_schedule_node_get_tree(node);2566 band = isl_schedule_band_from_multi_union_pw_aff(mupa);2567 tree = isl_schedule_tree_insert_band(tree, band);2568 node = isl_schedule_node_graft_tree(node, tree);2569 2570 return node;2571error:2572 isl_schedule_node_free(node);2573 isl_multi_union_pw_aff_free(mupa);2574 return NULL;2575}2576 2577/* Insert a context node with context "context" between "node" and its parent.2578 * Return a pointer to the new context node.2579 */2580__isl_give isl_schedule_node *isl_schedule_node_insert_context(2581 __isl_take isl_schedule_node *node, __isl_take isl_set *context)2582{2583 isl_schedule_tree *tree;2584 2585 if (check_insert(node) < 0)2586 node = isl_schedule_node_free(node);2587 2588 tree = isl_schedule_node_get_tree(node);2589 tree = isl_schedule_tree_insert_context(tree, context);2590 node = isl_schedule_node_graft_tree(node, tree);2591 2592 return node;2593}2594 2595/* Insert an expansion node with the given "contraction" and "expansion"2596 * between "node" and its parent.2597 * Return a pointer to the new expansion node.2598 *2599 * Typically the domain and range spaces of the expansion are different.2600 * This means that only one of them can refer to the current domain space2601 * in a consistent tree. It is up to the caller to ensure that the tree2602 * returns to a consistent state.2603 */2604__isl_give isl_schedule_node *isl_schedule_node_insert_expansion(2605 __isl_take isl_schedule_node *node,2606 __isl_take isl_union_pw_multi_aff *contraction,2607 __isl_take isl_union_map *expansion)2608{2609 isl_schedule_tree *tree;2610 2611 if (check_insert(node) < 0)2612 node = isl_schedule_node_free(node);2613 2614 tree = isl_schedule_node_get_tree(node);2615 tree = isl_schedule_tree_insert_expansion(tree, contraction, expansion);2616 node = isl_schedule_node_graft_tree(node, tree);2617 2618 return node;2619}2620 2621/* Insert an extension node with extension "extension" between "node" and2622 * its parent.2623 * Return a pointer to the new extension node.2624 */2625__isl_give isl_schedule_node *isl_schedule_node_insert_extension(2626 __isl_take isl_schedule_node *node,2627 __isl_take isl_union_map *extension)2628{2629 isl_schedule_tree *tree;2630 2631 tree = isl_schedule_node_get_tree(node);2632 tree = isl_schedule_tree_insert_extension(tree, extension);2633 node = isl_schedule_node_graft_tree(node, tree);2634 2635 return node;2636}2637 2638/* Insert a filter node with filter "filter" between "node" and its parent.2639 * Return a pointer to the new filter node.2640 */2641__isl_give isl_schedule_node *isl_schedule_node_insert_filter(2642 __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter)2643{2644 isl_schedule_tree *tree;2645 2646 if (check_insert(node) < 0)2647 node = isl_schedule_node_free(node);2648 2649 tree = isl_schedule_node_get_tree(node);2650 tree = isl_schedule_tree_insert_filter(tree, filter);2651 node = isl_schedule_node_graft_tree(node, tree);2652 2653 return node;2654}2655 2656/* Insert a guard node with guard "guard" between "node" and its parent.2657 * Return a pointer to the new guard node.2658 */2659__isl_give isl_schedule_node *isl_schedule_node_insert_guard(2660 __isl_take isl_schedule_node *node, __isl_take isl_set *guard)2661{2662 isl_schedule_tree *tree;2663 2664 if (check_insert(node) < 0)2665 node = isl_schedule_node_free(node);2666 2667 tree = isl_schedule_node_get_tree(node);2668 tree = isl_schedule_tree_insert_guard(tree, guard);2669 node = isl_schedule_node_graft_tree(node, tree);2670 2671 return node;2672}2673 2674/* Insert a mark node with mark identifier "mark" between "node" and2675 * its parent.2676 * Return a pointer to the new mark node.2677 */2678__isl_give isl_schedule_node *isl_schedule_node_insert_mark(2679 __isl_take isl_schedule_node *node, __isl_take isl_id *mark)2680{2681 isl_schedule_tree *tree;2682 2683 if (check_insert(node) < 0)2684 node = isl_schedule_node_free(node);2685 2686 tree = isl_schedule_node_get_tree(node);2687 tree = isl_schedule_tree_insert_mark(tree, mark);2688 node = isl_schedule_node_graft_tree(node, tree);2689 2690 return node;2691}2692 2693/* Attach the current subtree of "node" to a sequence of filter tree nodes2694 * with filters described by "filters", attach this sequence2695 * of filter tree nodes as children to a new tree of type "type" and2696 * replace the original subtree of "node" by this new tree.2697 * Each copy of the original subtree is simplified with respect2698 * to the corresponding filter.2699 */2700static __isl_give isl_schedule_node *isl_schedule_node_insert_children(2701 __isl_take isl_schedule_node *node,2702 enum isl_schedule_node_type type,2703 __isl_take isl_union_set_list *filters)2704{2705 int i;2706 isl_size n;2707 isl_ctx *ctx;2708 isl_schedule_tree *tree;2709 isl_schedule_tree_list *list;2710 2711 if (check_insert(node) < 0)2712 node = isl_schedule_node_free(node);2713 2714 n = isl_union_set_list_n_union_set(filters);2715 if (!node || n < 0)2716 goto error;2717 2718 ctx = isl_schedule_node_get_ctx(node);2719 list = isl_schedule_tree_list_alloc(ctx, n);2720 for (i = 0; i < n; ++i) {2721 isl_schedule_node *node_i;2722 isl_schedule_tree *tree;2723 isl_union_set *filter;2724 2725 filter = isl_union_set_list_get_union_set(filters, i);2726 node_i = isl_schedule_node_copy(node);2727 node_i = isl_schedule_node_gist(node_i,2728 isl_union_set_copy(filter));2729 tree = isl_schedule_node_get_tree(node_i);2730 isl_schedule_node_free(node_i);2731 tree = isl_schedule_tree_insert_filter(tree, filter);2732 list = isl_schedule_tree_list_add(list, tree);2733 }2734 tree = isl_schedule_tree_from_children(type, list);2735 node = isl_schedule_node_graft_tree(node, tree);2736 2737 isl_union_set_list_free(filters);2738 return node;2739error:2740 isl_union_set_list_free(filters);2741 isl_schedule_node_free(node);2742 return NULL;2743}2744 2745/* Insert a sequence node with child filters "filters" between "node" and2746 * its parent. That is, the tree that "node" points to is attached2747 * to each of the child nodes of the filter nodes.2748 * Return a pointer to the new sequence node.2749 */2750__isl_give isl_schedule_node *isl_schedule_node_insert_sequence(2751 __isl_take isl_schedule_node *node,2752 __isl_take isl_union_set_list *filters)2753{2754 return isl_schedule_node_insert_children(node,2755 isl_schedule_node_sequence, filters);2756}2757 2758/* Insert a set node with child filters "filters" between "node" and2759 * its parent. That is, the tree that "node" points to is attached2760 * to each of the child nodes of the filter nodes.2761 * Return a pointer to the new set node.2762 */2763__isl_give isl_schedule_node *isl_schedule_node_insert_set(2764 __isl_take isl_schedule_node *node,2765 __isl_take isl_union_set_list *filters)2766{2767 return isl_schedule_node_insert_children(node,2768 isl_schedule_node_set, filters);2769}2770 2771/* Remove "node" from its schedule tree and return a pointer2772 * to the leaf at the same position in the updated schedule tree.2773 *2774 * It is not allowed to remove the root of a schedule tree or2775 * a child of a set or sequence node.2776 */2777__isl_give isl_schedule_node *isl_schedule_node_cut(2778 __isl_take isl_schedule_node *node)2779{2780 isl_schedule_tree *leaf;2781 enum isl_schedule_node_type parent_type;2782 2783 if (!node)2784 return NULL;2785 if (!isl_schedule_node_has_parent(node))2786 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,2787 "cannot cut root", return isl_schedule_node_free(node));2788 2789 parent_type = isl_schedule_node_get_parent_type(node);2790 if (parent_type == isl_schedule_node_set ||2791 parent_type == isl_schedule_node_sequence)2792 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,2793 "cannot cut child of set or sequence",2794 return isl_schedule_node_free(node));2795 2796 leaf = isl_schedule_node_get_leaf(node);2797 return isl_schedule_node_graft_tree(node, leaf);2798}2799 2800/* Remove a single node from the schedule tree, attaching the child2801 * of "node" directly to its parent.2802 * Return a pointer to this former child or to the leaf the position2803 * of the original node if there was no child.2804 * It is not allowed to remove the root of a schedule tree,2805 * a set or sequence node, a child of a set or sequence node or2806 * a band node with an anchored subtree.2807 */2808__isl_give isl_schedule_node *isl_schedule_node_delete(2809 __isl_take isl_schedule_node *node)2810{2811 isl_size n, depth;2812 isl_schedule_tree *tree;2813 enum isl_schedule_node_type type;2814 2815 depth = isl_schedule_node_get_tree_depth(node);2816 n = isl_schedule_node_n_children(node);2817 if (depth < 0 || n < 0)2818 return isl_schedule_node_free(node);2819 2820 if (depth == 0)2821 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,2822 "cannot delete root node",2823 return isl_schedule_node_free(node));2824 if (n != 1)2825 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,2826 "can only delete node with a single child",2827 return isl_schedule_node_free(node));2828 type = isl_schedule_node_get_parent_type(node);2829 if (type == isl_schedule_node_sequence || type == isl_schedule_node_set)2830 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,2831 "cannot delete child of set or sequence",2832 return isl_schedule_node_free(node));2833 if (isl_schedule_node_get_type(node) == isl_schedule_node_band) {2834 int anchored;2835 2836 anchored = isl_schedule_node_is_subtree_anchored(node);2837 if (anchored < 0)2838 return isl_schedule_node_free(node);2839 if (anchored)2840 isl_die(isl_schedule_node_get_ctx(node),2841 isl_error_invalid,2842 "cannot delete band node with anchored subtree",2843 return isl_schedule_node_free(node));2844 }2845 2846 tree = isl_schedule_node_get_tree(node);2847 if (!tree || isl_schedule_tree_has_children(tree)) {2848 tree = isl_schedule_tree_child(tree, 0);2849 } else {2850 isl_schedule_tree_free(tree);2851 tree = isl_schedule_node_get_leaf(node);2852 }2853 node = isl_schedule_node_graft_tree(node, tree);2854 2855 return node;2856}2857 2858/* Internal data structure for the group_ancestor callback.2859 *2860 * If "finished" is set, then we no longer need to modify2861 * any further ancestors.2862 *2863 * "contraction" and "expansion" represent the expansion2864 * that reflects the grouping.2865 *2866 * "domain" contains the domain elements that reach the position2867 * where the grouping is performed. That is, it is the range2868 * of the resulting expansion.2869 * "domain_universe" is the universe of "domain".2870 * "group" is the set of group elements, i.e., the domain2871 * of the resulting expansion.2872 * "group_universe" is the universe of "group".2873 *2874 * "sched" is the schedule for the group elements, in pratice2875 * an identity mapping on "group_universe".2876 * "dim" is the dimension of "sched".2877 */2878struct isl_schedule_group_data {2879 int finished;2880 2881 isl_union_map *expansion;2882 isl_union_pw_multi_aff *contraction;2883 2884 isl_union_set *domain;2885 isl_union_set *domain_universe;2886 isl_union_set *group;2887 isl_union_set *group_universe;2888 2889 int dim;2890 isl_multi_aff *sched;2891};2892 2893/* Is domain covered by data->domain within data->domain_universe?2894 */2895static isl_bool locally_covered_by_domain(__isl_keep isl_union_set *domain,2896 struct isl_schedule_group_data *data)2897{2898 isl_bool is_subset;2899 isl_union_set *test;2900 2901 test = isl_union_set_copy(domain);2902 test = isl_union_set_intersect(test,2903 isl_union_set_copy(data->domain_universe));2904 is_subset = isl_union_set_is_subset(test, data->domain);2905 isl_union_set_free(test);2906 2907 return is_subset;2908}2909 2910/* Update the band tree root "tree" to refer to the group instances2911 * in data->group rather than the original domain elements in data->domain.2912 * "pos" is the position in the original schedule tree where the modified2913 * "tree" will be attached.2914 *2915 * Add the part of the identity schedule on the group instances data->sched2916 * that corresponds to this band node to the band schedule.2917 * If the domain elements that reach the node and that are part2918 * of data->domain_universe are all elements of data->domain (and therefore2919 * replaced by the group instances) then this data->domain_universe2920 * is removed from the domain of the band schedule.2921 */2922static __isl_give isl_schedule_tree *group_band(2923 __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_node *pos,2924 struct isl_schedule_group_data *data)2925{2926 isl_union_set *domain;2927 isl_multi_aff *ma;2928 isl_multi_union_pw_aff *mupa, *partial;2929 isl_bool is_covered;2930 isl_size depth, n;2931 isl_bool has_id;2932 2933 domain = isl_schedule_node_get_domain(pos);2934 is_covered = locally_covered_by_domain(domain, data);2935 if (is_covered >= 0 && is_covered) {2936 domain = isl_union_set_universe(domain);2937 domain = isl_union_set_subtract(domain,2938 isl_union_set_copy(data->domain_universe));2939 tree = isl_schedule_tree_band_intersect_domain(tree, domain);2940 } else2941 isl_union_set_free(domain);2942 if (is_covered < 0)2943 return isl_schedule_tree_free(tree);2944 depth = isl_schedule_node_get_schedule_depth(pos);2945 n = isl_schedule_tree_band_n_member(tree);2946 if (depth < 0 || n < 0)2947 return isl_schedule_tree_free(tree);2948 ma = isl_multi_aff_copy(data->sched);2949 ma = isl_multi_aff_drop_dims(ma, isl_dim_out, 0, depth);2950 ma = isl_multi_aff_drop_dims(ma, isl_dim_out, n, data->dim - depth - n);2951 mupa = isl_multi_union_pw_aff_from_multi_aff(ma);2952 partial = isl_schedule_tree_band_get_partial_schedule(tree);2953 has_id = isl_multi_union_pw_aff_has_tuple_id(partial, isl_dim_set);2954 if (has_id < 0) {2955 partial = isl_multi_union_pw_aff_free(partial);2956 } else if (has_id) {2957 isl_id *id;2958 id = isl_multi_union_pw_aff_get_tuple_id(partial, isl_dim_set);2959 mupa = isl_multi_union_pw_aff_set_tuple_id(mupa,2960 isl_dim_set, id);2961 }2962 partial = isl_multi_union_pw_aff_union_add(partial, mupa);2963 tree = isl_schedule_tree_band_set_partial_schedule(tree, partial);2964 2965 return tree;2966}2967 2968/* Drop the parameters in "uset" that are not also in "space".2969 * "n" is the number of parameters in "space".2970 */2971static __isl_give isl_union_set *union_set_drop_extra_params(2972 __isl_take isl_union_set *uset, __isl_keep isl_space *space, int n)2973{2974 isl_size n2;2975 2976 uset = isl_union_set_align_params(uset, isl_space_copy(space));2977 n2 = isl_union_set_dim(uset, isl_dim_param);2978 if (n2 < 0)2979 return isl_union_set_free(uset);2980 uset = isl_union_set_project_out(uset, isl_dim_param, n, n2 - n);2981 2982 return uset;2983}2984 2985/* Update the context tree root "tree" to refer to the group instances2986 * in data->group rather than the original domain elements in data->domain.2987 * "pos" is the position in the original schedule tree where the modified2988 * "tree" will be attached.2989 *2990 * We do not actually need to update "tree" since a context node only2991 * refers to the schedule space. However, we may need to update "data"2992 * to not refer to any parameters introduced by the context node.2993 */2994static __isl_give isl_schedule_tree *group_context(2995 __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_node *pos,2996 struct isl_schedule_group_data *data)2997{2998 isl_space *space;2999 isl_union_set *domain;3000 isl_size n1, n2;3001 isl_bool involves;3002 isl_size depth;3003 3004 depth = isl_schedule_node_get_tree_depth(pos);3005 if (depth < 0)3006 return isl_schedule_tree_free(tree);3007 if (depth == 1)3008 return tree;3009 3010 domain = isl_schedule_node_get_universe_domain(pos);3011 space = isl_union_set_get_space(domain);3012 isl_union_set_free(domain);3013 3014 n1 = isl_space_dim(space, isl_dim_param);3015 data->expansion = isl_union_map_align_params(data->expansion, space);3016 n2 = isl_union_map_dim(data->expansion, isl_dim_param);3017 3018 if (n1 < 0 || n2 < 0)3019 return isl_schedule_tree_free(tree);3020 if (n1 == n2)3021 return tree;3022 3023 involves = isl_union_map_involves_dims(data->expansion,3024 isl_dim_param, n1, n2 - n1);3025 if (involves < 0)3026 return isl_schedule_tree_free(tree);3027 if (involves)3028 isl_die(isl_schedule_node_get_ctx(pos), isl_error_invalid,3029 "grouping cannot only refer to global parameters",3030 return isl_schedule_tree_free(tree));3031 3032 data->expansion = isl_union_map_project_out(data->expansion,3033 isl_dim_param, n1, n2 - n1);3034 space = isl_union_map_get_space(data->expansion);3035 3036 data->contraction = isl_union_pw_multi_aff_align_params(3037 data->contraction, isl_space_copy(space));3038 n2 = isl_union_pw_multi_aff_dim(data->contraction, isl_dim_param);3039 if (n2 < 0)3040 data->contraction =3041 isl_union_pw_multi_aff_free(data->contraction);3042 data->contraction = isl_union_pw_multi_aff_drop_dims(data->contraction,3043 isl_dim_param, n1, n2 - n1);3044 3045 data->domain = union_set_drop_extra_params(data->domain, space, n1);3046 data->domain_universe =3047 union_set_drop_extra_params(data->domain_universe, space, n1);3048 data->group = union_set_drop_extra_params(data->group, space, n1);3049 data->group_universe =3050 union_set_drop_extra_params(data->group_universe, space, n1);3051 3052 data->sched = isl_multi_aff_align_params(data->sched,3053 isl_space_copy(space));3054 n2 = isl_multi_aff_dim(data->sched, isl_dim_param);3055 if (n2 < 0)3056 data->sched = isl_multi_aff_free(data->sched);3057 data->sched = isl_multi_aff_drop_dims(data->sched,3058 isl_dim_param, n1, n2 - n1);3059 3060 isl_space_free(space);3061 3062 return tree;3063}3064 3065/* Update the domain tree root "tree" to refer to the group instances3066 * in data->group rather than the original domain elements in data->domain.3067 * "pos" is the position in the original schedule tree where the modified3068 * "tree" will be attached.3069 *3070 * We first double-check that all grouped domain elements are actually3071 * part of the root domain and then replace those elements by the group3072 * instances.3073 */3074static __isl_give isl_schedule_tree *group_domain(3075 __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_node *pos,3076 struct isl_schedule_group_data *data)3077{3078 isl_union_set *domain;3079 isl_bool is_subset;3080 3081 domain = isl_schedule_tree_domain_get_domain(tree);3082 is_subset = isl_union_set_is_subset(data->domain, domain);3083 isl_union_set_free(domain);3084 if (is_subset < 0)3085 return isl_schedule_tree_free(tree);3086 if (!is_subset)3087 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,3088 "grouped domain should be part of outer domain",3089 return isl_schedule_tree_free(tree));3090 domain = isl_schedule_tree_domain_get_domain(tree);3091 domain = isl_union_set_subtract(domain,3092 isl_union_set_copy(data->domain));3093 domain = isl_union_set_union(domain, isl_union_set_copy(data->group));3094 tree = isl_schedule_tree_domain_set_domain(tree, domain);3095 3096 return tree;3097}3098 3099/* Update the expansion tree root "tree" to refer to the group instances3100 * in data->group rather than the original domain elements in data->domain.3101 * "pos" is the position in the original schedule tree where the modified3102 * "tree" will be attached.3103 *3104 * Let G_1 -> D_1 be the expansion of "tree" and G_2 -> D_2 the newly3105 * introduced expansion in a descendant of "tree".3106 * We first double-check that D_2 is a subset of D_1.3107 * Then we remove D_2 from the range of G_1 -> D_1 and add the mapping3108 * G_1 -> D_1 . D_2 -> G_2.3109 * Simmilarly, we restrict the domain of the contraction to the universe3110 * of the range of the updated expansion and add G_2 -> D_2 . D_1 -> G_1,3111 * attempting to remove the domain constraints of this additional part.3112 */3113static __isl_give isl_schedule_tree *group_expansion(3114 __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_node *pos,3115 struct isl_schedule_group_data *data)3116{3117 isl_union_set *domain;3118 isl_union_map *expansion, *umap;3119 isl_union_pw_multi_aff *contraction, *upma;3120 int is_subset;3121 3122 expansion = isl_schedule_tree_expansion_get_expansion(tree);3123 domain = isl_union_map_range(expansion);3124 is_subset = isl_union_set_is_subset(data->domain, domain);3125 isl_union_set_free(domain);3126 if (is_subset < 0)3127 return isl_schedule_tree_free(tree);3128 if (!is_subset)3129 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,3130 "grouped domain should be part "3131 "of outer expansion domain",3132 return isl_schedule_tree_free(tree));3133 expansion = isl_schedule_tree_expansion_get_expansion(tree);3134 umap = isl_union_map_from_union_pw_multi_aff(3135 isl_union_pw_multi_aff_copy(data->contraction));3136 umap = isl_union_map_apply_range(expansion, umap);3137 expansion = isl_schedule_tree_expansion_get_expansion(tree);3138 expansion = isl_union_map_subtract_range(expansion,3139 isl_union_set_copy(data->domain));3140 expansion = isl_union_map_union(expansion, umap);3141 umap = isl_union_map_universe(isl_union_map_copy(expansion));3142 domain = isl_union_map_range(umap);3143 contraction = isl_schedule_tree_expansion_get_contraction(tree);3144 umap = isl_union_map_from_union_pw_multi_aff(contraction);3145 umap = isl_union_map_apply_range(isl_union_map_copy(data->expansion),3146 umap);3147 upma = isl_union_pw_multi_aff_from_union_map(umap);3148 contraction = isl_schedule_tree_expansion_get_contraction(tree);3149 contraction = isl_union_pw_multi_aff_intersect_domain(contraction,3150 domain);3151 domain = isl_union_pw_multi_aff_domain(3152 isl_union_pw_multi_aff_copy(upma));3153 upma = isl_union_pw_multi_aff_gist(upma, domain);3154 contraction = isl_union_pw_multi_aff_union_add(contraction, upma);3155 tree = isl_schedule_tree_expansion_set_contraction_and_expansion(tree,3156 contraction, expansion);3157 3158 return tree;3159}3160 3161/* Update the tree root "tree" to refer to the group instances3162 * in data->group rather than the original domain elements in data->domain.3163 * "pos" is the position in the original schedule tree where the modified3164 * "tree" will be attached.3165 *3166 * If we have come across a domain or expansion node before (data->finished3167 * is set), then we no longer need perform any modifications.3168 *3169 * If "tree" is a filter, then we add data->group_universe to the filter.3170 * We also remove data->domain_universe from the filter if all the domain3171 * elements in this universe that reach the filter node are part of3172 * the elements that are being grouped by data->expansion.3173 * If "tree" is a band, domain or expansion, then it is handled3174 * in a separate function.3175 */3176static __isl_give isl_schedule_tree *group_ancestor(3177 __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_node *pos,3178 void *user)3179{3180 struct isl_schedule_group_data *data = user;3181 isl_union_set *domain;3182 isl_bool is_covered;3183 3184 if (!tree || !pos)3185 return isl_schedule_tree_free(tree);3186 3187 if (data->finished)3188 return tree;3189 3190 switch (isl_schedule_tree_get_type(tree)) {3191 case isl_schedule_node_error:3192 return isl_schedule_tree_free(tree);3193 case isl_schedule_node_extension:3194 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_unsupported,3195 "grouping not allowed in extended tree",3196 return isl_schedule_tree_free(tree));3197 case isl_schedule_node_band:3198 tree = group_band(tree, pos, data);3199 break;3200 case isl_schedule_node_context:3201 tree = group_context(tree, pos, data);3202 break;3203 case isl_schedule_node_domain:3204 tree = group_domain(tree, pos, data);3205 data->finished = 1;3206 break;3207 case isl_schedule_node_filter:3208 domain = isl_schedule_node_get_domain(pos);3209 is_covered = locally_covered_by_domain(domain, data);3210 isl_union_set_free(domain);3211 if (is_covered < 0)3212 return isl_schedule_tree_free(tree);3213 domain = isl_schedule_tree_filter_get_filter(tree);3214 if (is_covered)3215 domain = isl_union_set_subtract(domain,3216 isl_union_set_copy(data->domain_universe));3217 domain = isl_union_set_union(domain,3218 isl_union_set_copy(data->group_universe));3219 tree = isl_schedule_tree_filter_set_filter(tree, domain);3220 break;3221 case isl_schedule_node_expansion:3222 tree = group_expansion(tree, pos, data);3223 data->finished = 1;3224 break;3225 case isl_schedule_node_leaf:3226 case isl_schedule_node_guard:3227 case isl_schedule_node_mark:3228 case isl_schedule_node_sequence:3229 case isl_schedule_node_set:3230 break;3231 }3232 3233 return tree;3234}3235 3236/* Group the domain elements that reach "node" into instances3237 * of a single statement with identifier "group_id".3238 * In particular, group the domain elements according to their3239 * prefix schedule.3240 *3241 * That is, introduce an expansion node with as contraction3242 * the prefix schedule (with the target space replaced by "group_id")3243 * and as expansion the inverse of this contraction (with its range3244 * intersected with the domain elements that reach "node").3245 * The outer nodes are then modified to refer to the group instances3246 * instead of the original domain elements.3247 *3248 * No instance of "group_id" is allowed to reach "node" prior3249 * to the grouping.3250 * No ancestor of "node" is allowed to be an extension node.3251 *3252 * Return a pointer to original node in tree, i.e., the child3253 * of the newly introduced expansion node.3254 */3255__isl_give isl_schedule_node *isl_schedule_node_group(3256 __isl_take isl_schedule_node *node, __isl_take isl_id *group_id)3257{3258 struct isl_schedule_group_data data = { 0 };3259 isl_space *space;3260 isl_union_set *domain;3261 isl_union_pw_multi_aff *contraction;3262 isl_union_map *expansion;3263 isl_bool disjoint;3264 isl_size depth;3265 3266 depth = isl_schedule_node_get_schedule_depth(node);3267 if (depth < 0 || !group_id)3268 goto error;3269 if (check_insert(node) < 0)3270 goto error;3271 3272 domain = isl_schedule_node_get_domain(node);3273 data.domain = isl_union_set_copy(domain);3274 data.domain_universe = isl_union_set_copy(domain);3275 data.domain_universe = isl_union_set_universe(data.domain_universe);3276 3277 data.dim = depth;3278 if (data.dim == 0) {3279 isl_ctx *ctx;3280 isl_set *set;3281 isl_union_set *group;3282 isl_union_map *univ;3283 3284 ctx = isl_schedule_node_get_ctx(node);3285 space = isl_space_set_alloc(ctx, 0, 0);3286 space = isl_space_set_tuple_id(space, isl_dim_set, group_id);3287 set = isl_set_universe(isl_space_copy(space));3288 group = isl_union_set_from_set(set);3289 expansion = isl_union_map_from_domain_and_range(domain, group);3290 univ = isl_union_map_universe(isl_union_map_copy(expansion));3291 contraction = isl_union_pw_multi_aff_from_union_map(univ);3292 expansion = isl_union_map_reverse(expansion);3293 } else {3294 isl_multi_union_pw_aff *prefix;3295 isl_union_set *univ;3296 3297 prefix =3298 isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node);3299 prefix = isl_multi_union_pw_aff_set_tuple_id(prefix,3300 isl_dim_set, group_id);3301 space = isl_multi_union_pw_aff_get_space(prefix);3302 contraction = isl_union_pw_multi_aff_from_multi_union_pw_aff(3303 prefix);3304 univ = isl_union_set_universe(isl_union_set_copy(domain));3305 contraction =3306 isl_union_pw_multi_aff_intersect_domain(contraction, univ);3307 expansion = isl_union_map_from_union_pw_multi_aff(3308 isl_union_pw_multi_aff_copy(contraction));3309 expansion = isl_union_map_reverse(expansion);3310 expansion = isl_union_map_intersect_range(expansion, domain);3311 }3312 space = isl_space_map_from_set(space);3313 data.sched = isl_multi_aff_identity(space);3314 data.group = isl_union_map_domain(isl_union_map_copy(expansion));3315 data.group = isl_union_set_coalesce(data.group);3316 data.group_universe = isl_union_set_copy(data.group);3317 data.group_universe = isl_union_set_universe(data.group_universe);3318 data.expansion = isl_union_map_copy(expansion);3319 data.contraction = isl_union_pw_multi_aff_copy(contraction);3320 node = isl_schedule_node_insert_expansion(node, contraction, expansion);3321 3322 disjoint = isl_union_set_is_disjoint(data.domain_universe,3323 data.group_universe);3324 3325 node = update_ancestors(node, &group_ancestor, &data);3326 3327 isl_union_set_free(data.domain);3328 isl_union_set_free(data.domain_universe);3329 isl_union_set_free(data.group);3330 isl_union_set_free(data.group_universe);3331 isl_multi_aff_free(data.sched);3332 isl_union_map_free(data.expansion);3333 isl_union_pw_multi_aff_free(data.contraction);3334 3335 node = isl_schedule_node_child(node, 0);3336 3337 if (!node || disjoint < 0)3338 return isl_schedule_node_free(node);3339 if (!disjoint)3340 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,3341 "group instances already reach node",3342 return isl_schedule_node_free(node));3343 3344 return node;3345error:3346 isl_schedule_node_free(node);3347 isl_id_free(group_id);3348 return NULL;3349}3350 3351/* Compute the gist of the given band node with respect to "context".3352 */3353__isl_give isl_schedule_node *isl_schedule_node_band_gist(3354 __isl_take isl_schedule_node *node, __isl_take isl_union_set *context)3355{3356 isl_schedule_tree *tree;3357 3358 tree = isl_schedule_node_get_tree(node);3359 tree = isl_schedule_tree_band_gist(tree, context);3360 return isl_schedule_node_graft_tree(node, tree);3361}3362 3363/* Internal data structure for isl_schedule_node_gist.3364 * "n_expansion" is the number of outer expansion nodes3365 * with respect to the current position3366 * "filters" contains an element for each outer filter, expansion or3367 * extension node with respect to the current position, each representing3368 * the intersection of the previous element and the filter on the filter node3369 * or the expansion/extension of the previous element.3370 * The first element in the original context passed to isl_schedule_node_gist.3371 */3372struct isl_node_gist_data {3373 int n_expansion;3374 isl_union_set_list *filters;3375};3376 3377/* Enter the expansion node "node" during a isl_schedule_node_gist traversal.3378 *3379 * In particular, add an extra element to data->filters containing3380 * the expansion of the previous element and replace the expansion3381 * and contraction on "node" by the gist with respect to these filters.3382 * Also keep track of the fact that we have entered another expansion.3383 */3384static __isl_give isl_schedule_node *gist_enter_expansion(3385 __isl_take isl_schedule_node *node, struct isl_node_gist_data *data)3386{3387 isl_size n;3388 isl_union_set *inner;3389 isl_union_map *expansion;3390 isl_union_pw_multi_aff *contraction;3391 3392 data->n_expansion++;3393 3394 n = isl_union_set_list_n_union_set(data->filters);3395 if (n < 0)3396 return isl_schedule_node_free(node);3397 inner = isl_union_set_list_get_union_set(data->filters, n - 1);3398 expansion = isl_schedule_node_expansion_get_expansion(node);3399 inner = isl_union_set_apply(inner, expansion);3400 3401 contraction = isl_schedule_node_expansion_get_contraction(node);3402 contraction = isl_union_pw_multi_aff_gist(contraction,3403 isl_union_set_copy(inner));3404 3405 data->filters = isl_union_set_list_add(data->filters, inner);3406 3407 inner = isl_union_set_list_get_union_set(data->filters, n - 1);3408 expansion = isl_schedule_node_expansion_get_expansion(node);3409 expansion = isl_union_map_gist_domain(expansion, inner);3410 node = isl_schedule_node_expansion_set_contraction_and_expansion(node,3411 contraction, expansion);3412 3413 return node;3414}3415 3416/* Leave the expansion node "node" during a isl_schedule_node_gist traversal.3417 *3418 * In particular, remove the element in data->filters that was added by3419 * gist_enter_expansion and decrement the number of outer expansions.3420 *3421 * The expansion has already been simplified in gist_enter_expansion.3422 * If this simplification results in an identity expansion, then3423 * it is removed here.3424 */3425static __isl_give isl_schedule_node *gist_leave_expansion(3426 __isl_take isl_schedule_node *node, struct isl_node_gist_data *data)3427{3428 isl_size n;3429 isl_bool identity;3430 isl_union_map *expansion;3431 3432 expansion = isl_schedule_node_expansion_get_expansion(node);3433 identity = isl_union_map_is_identity(expansion);3434 isl_union_map_free(expansion);3435 3436 if (identity < 0)3437 node = isl_schedule_node_free(node);3438 else if (identity)3439 node = isl_schedule_node_delete(node);3440 3441 n = isl_union_set_list_n_union_set(data->filters);3442 if (n < 0)3443 return isl_schedule_node_free(node);3444 data->filters = isl_union_set_list_drop(data->filters, n - 1, 1);3445 3446 data->n_expansion--;3447 3448 return node;3449}3450 3451/* Enter the extension node "node" during a isl_schedule_node_gist traversal.3452 *3453 * In particular, add an extra element to data->filters containing3454 * the union of the previous element with the additional domain elements3455 * introduced by the extension.3456 */3457static __isl_give isl_schedule_node *gist_enter_extension(3458 __isl_take isl_schedule_node *node, struct isl_node_gist_data *data)3459{3460 isl_size n;3461 isl_union_set *inner, *extra;3462 isl_union_map *extension;3463 3464 n = isl_union_set_list_n_union_set(data->filters);3465 if (n < 0)3466 return isl_schedule_node_free(node);3467 inner = isl_union_set_list_get_union_set(data->filters, n - 1);3468 extension = isl_schedule_node_extension_get_extension(node);3469 extra = isl_union_map_range(extension);3470 inner = isl_union_set_union(inner, extra);3471 3472 data->filters = isl_union_set_list_add(data->filters, inner);3473 3474 return node;3475}3476 3477/* Can we finish gisting at this node?3478 * That is, is the filter on the current filter node a subset of3479 * the original context passed to isl_schedule_node_gist?3480 * If we have gone through any expansions, then we cannot perform3481 * this test since the current domain elements are incomparable3482 * to the domain elements in the original context.3483 */3484static isl_bool gist_done(__isl_keep isl_schedule_node *node,3485 struct isl_node_gist_data *data)3486{3487 isl_union_set *filter, *outer;3488 isl_bool subset;3489 3490 if (data->n_expansion != 0)3491 return isl_bool_false;3492 3493 filter = isl_schedule_node_filter_get_filter(node);3494 outer = isl_union_set_list_get_union_set(data->filters, 0);3495 subset = isl_union_set_is_subset(filter, outer);3496 isl_union_set_free(outer);3497 isl_union_set_free(filter);3498 3499 return subset;3500}3501 3502/* Callback for "traverse" to enter a node and to move3503 * to the deepest initial subtree that should be traversed3504 * by isl_schedule_node_gist.3505 *3506 * The "filters" list is extended by one element each time3507 * we come across a filter node by the result of intersecting3508 * the last element in the list with the filter on the filter node.3509 *3510 * If the filter on the current filter node is a subset of3511 * the original context passed to isl_schedule_node_gist,3512 * then there is no need to go into its subtree since it cannot3513 * be further simplified by the context. The "filters" list is3514 * still extended for consistency, but the actual value of the3515 * added element is immaterial since it will not be used.3516 *3517 * Otherwise, the filter on the current filter node is replaced by3518 * the gist of the original filter with respect to the intersection3519 * of the original context with the intermediate filters.3520 *3521 * If the new element in the "filters" list is empty, then no elements3522 * can reach the descendants of the current filter node. The subtree3523 * underneath the filter node is therefore removed.3524 *3525 * Each expansion node we come across is handled by3526 * gist_enter_expansion.3527 *3528 * Each extension node we come across is handled by3529 * gist_enter_extension.3530 */3531static __isl_give isl_schedule_node *gist_enter(3532 __isl_take isl_schedule_node *node, void *user)3533{3534 struct isl_node_gist_data *data = user;3535 3536 do {3537 isl_union_set *filter, *inner;3538 isl_bool done, empty;3539 isl_size n;3540 3541 switch (isl_schedule_node_get_type(node)) {3542 case isl_schedule_node_error:3543 return isl_schedule_node_free(node);3544 case isl_schedule_node_expansion:3545 node = gist_enter_expansion(node, data);3546 continue;3547 case isl_schedule_node_extension:3548 node = gist_enter_extension(node, data);3549 continue;3550 case isl_schedule_node_band:3551 case isl_schedule_node_context:3552 case isl_schedule_node_domain:3553 case isl_schedule_node_guard:3554 case isl_schedule_node_leaf:3555 case isl_schedule_node_mark:3556 case isl_schedule_node_sequence:3557 case isl_schedule_node_set:3558 continue;3559 case isl_schedule_node_filter:3560 break;3561 }3562 done = gist_done(node, data);3563 filter = isl_schedule_node_filter_get_filter(node);3564 n = isl_union_set_list_n_union_set(data->filters);3565 if (n < 0 || done < 0 || done) {3566 data->filters = isl_union_set_list_add(data->filters,3567 filter);3568 if (n < 0 || done < 0)3569 return isl_schedule_node_free(node);3570 return node;3571 }3572 inner = isl_union_set_list_get_union_set(data->filters, n - 1);3573 filter = isl_union_set_gist(filter, isl_union_set_copy(inner));3574 node = isl_schedule_node_filter_set_filter(node,3575 isl_union_set_copy(filter));3576 filter = isl_union_set_intersect(filter, inner);3577 empty = isl_union_set_is_empty(filter);3578 data->filters = isl_union_set_list_add(data->filters, filter);3579 if (empty < 0)3580 return isl_schedule_node_free(node);3581 if (!empty)3582 continue;3583 node = isl_schedule_node_child(node, 0);3584 node = isl_schedule_node_cut(node);3585 node = isl_schedule_node_parent(node);3586 return node;3587 } while (isl_schedule_node_has_children(node) &&3588 (node = isl_schedule_node_first_child(node)) != NULL);3589 3590 return node;3591}3592 3593/* Callback for "traverse" to leave a node for isl_schedule_node_gist.3594 *3595 * In particular, if the current node is a filter node, then we remove3596 * the element on the "filters" list that was added when we entered3597 * the node. There is no need to compute any gist here, since we3598 * already did that when we entered the node.3599 *3600 * Expansion nodes are handled by gist_leave_expansion.3601 *3602 * If the current node is an extension, then remove the element3603 * in data->filters that was added by gist_enter_extension.3604 *3605 * If the current node is a band node, then we compute the gist of3606 * the band node with respect to the intersection of the original context3607 * and the intermediate filters.3608 *3609 * If the current node is a sequence or set node, then some of3610 * the filter children may have become empty and so they are removed.3611 * If only one child is left, then the set or sequence node along with3612 * the single remaining child filter is removed. The filter can be3613 * removed because the filters on a sequence or set node are supposed3614 * to partition the incoming domain instances.3615 * In principle, it should then be impossible for there to be zero3616 * remaining children, but should this happen, we replace the entire3617 * subtree with an empty filter.3618 */3619static __isl_give isl_schedule_node *gist_leave(3620 __isl_take isl_schedule_node *node, void *user)3621{3622 struct isl_node_gist_data *data = user;3623 isl_schedule_tree *tree;3624 int i;3625 isl_size n;3626 isl_union_set *filter;3627 3628 switch (isl_schedule_node_get_type(node)) {3629 case isl_schedule_node_error:3630 return isl_schedule_node_free(node);3631 case isl_schedule_node_expansion:3632 node = gist_leave_expansion(node, data);3633 break;3634 case isl_schedule_node_extension:3635 case isl_schedule_node_filter:3636 n = isl_union_set_list_n_union_set(data->filters);3637 if (n < 0)3638 return isl_schedule_node_free(node);3639 data->filters = isl_union_set_list_drop(data->filters,3640 n - 1, 1);3641 break;3642 case isl_schedule_node_band:3643 n = isl_union_set_list_n_union_set(data->filters);3644 if (n < 0)3645 return isl_schedule_node_free(node);3646 filter = isl_union_set_list_get_union_set(data->filters, n - 1);3647 node = isl_schedule_node_band_gist(node, filter);3648 break;3649 case isl_schedule_node_set:3650 case isl_schedule_node_sequence:3651 tree = isl_schedule_node_get_tree(node);3652 n = isl_schedule_tree_n_children(tree);3653 if (n < 0)3654 tree = isl_schedule_tree_free(tree);3655 for (i = n - 1; i >= 0; --i) {3656 isl_schedule_tree *child;3657 isl_union_set *filter;3658 isl_bool empty;3659 3660 child = isl_schedule_tree_get_child(tree, i);3661 filter = isl_schedule_tree_filter_get_filter(child);3662 empty = isl_union_set_is_empty(filter);3663 isl_union_set_free(filter);3664 isl_schedule_tree_free(child);3665 if (empty < 0)3666 tree = isl_schedule_tree_free(tree);3667 else if (empty)3668 tree = isl_schedule_tree_drop_child(tree, i);3669 }3670 n = isl_schedule_tree_n_children(tree);3671 if (n < 0)3672 tree = isl_schedule_tree_free(tree);3673 node = isl_schedule_node_graft_tree(node, tree);3674 if (n == 1) {3675 node = isl_schedule_node_delete(node);3676 node = isl_schedule_node_delete(node);3677 } else if (n == 0) {3678 isl_space *space;3679 3680 filter =3681 isl_union_set_list_get_union_set(data->filters, 0);3682 space = isl_union_set_get_space(filter);3683 isl_union_set_free(filter);3684 filter = isl_union_set_empty(space);3685 node = isl_schedule_node_cut(node);3686 node = isl_schedule_node_insert_filter(node, filter);3687 }3688 break;3689 case isl_schedule_node_context:3690 case isl_schedule_node_domain:3691 case isl_schedule_node_guard:3692 case isl_schedule_node_leaf:3693 case isl_schedule_node_mark:3694 break;3695 }3696 3697 return node;3698}3699 3700/* Compute the gist of the subtree at "node" with respect to3701 * the reaching domain elements in "context".3702 * In particular, compute the gist of all band and filter nodes3703 * in the subtree with respect to "context". Children of set or sequence3704 * nodes that end up with an empty filter are removed completely.3705 *3706 * We keep track of the intersection of "context" with all outer filters3707 * of the current node within the subtree in the final element of "filters".3708 * Initially, this list contains the single element "context" and it is3709 * extended or shortened each time we enter or leave a filter node.3710 */3711__isl_give isl_schedule_node *isl_schedule_node_gist(3712 __isl_take isl_schedule_node *node, __isl_take isl_union_set *context)3713{3714 struct isl_node_gist_data data;3715 3716 data.n_expansion = 0;3717 data.filters = isl_union_set_list_from_union_set(context);3718 node = traverse(node, &gist_enter, &gist_leave, &data);3719 isl_union_set_list_free(data.filters);3720 return node;3721}3722 3723/* Intersect the domain of domain node "node" with "domain".3724 *3725 * If the domain of "node" is already a subset of "domain",3726 * then nothing needs to be changed.3727 *3728 * Otherwise, we replace the domain of the domain node by the intersection3729 * and simplify the subtree rooted at "node" with respect to this intersection.3730 */3731__isl_give isl_schedule_node *isl_schedule_node_domain_intersect_domain(3732 __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain)3733{3734 isl_schedule_tree *tree;3735 isl_union_set *uset;3736 int is_subset;3737 3738 if (!node || !domain)3739 goto error;3740 3741 uset = isl_schedule_tree_domain_get_domain(node->tree);3742 is_subset = isl_union_set_is_subset(uset, domain);3743 isl_union_set_free(uset);3744 if (is_subset < 0)3745 goto error;3746 if (is_subset) {3747 isl_union_set_free(domain);3748 return node;3749 }3750 3751 tree = isl_schedule_tree_copy(node->tree);3752 uset = isl_schedule_tree_domain_get_domain(tree);3753 uset = isl_union_set_intersect(uset, domain);3754 tree = isl_schedule_tree_domain_set_domain(tree,3755 isl_union_set_copy(uset));3756 node = isl_schedule_node_graft_tree(node, tree);3757 3758 node = isl_schedule_node_child(node, 0);3759 node = isl_schedule_node_gist(node, uset);3760 node = isl_schedule_node_parent(node);3761 3762 return node;3763error:3764 isl_schedule_node_free(node);3765 isl_union_set_free(domain);3766 return NULL;3767}3768 3769/* Replace the domain of domain node "node" with the gist3770 * of the original domain with respect to the parameter domain "context".3771 */3772__isl_give isl_schedule_node *isl_schedule_node_domain_gist_params(3773 __isl_take isl_schedule_node *node, __isl_take isl_set *context)3774{3775 isl_union_set *domain;3776 isl_schedule_tree *tree;3777 3778 if (!node || !context)3779 goto error;3780 3781 tree = isl_schedule_tree_copy(node->tree);3782 domain = isl_schedule_tree_domain_get_domain(node->tree);3783 domain = isl_union_set_gist_params(domain, context);3784 tree = isl_schedule_tree_domain_set_domain(tree, domain);3785 node = isl_schedule_node_graft_tree(node, tree);3786 3787 return node;3788error:3789 isl_schedule_node_free(node);3790 isl_set_free(context);3791 return NULL;3792}3793 3794/* Internal data structure for isl_schedule_node_get_subtree_expansion.3795 * "expansions" contains a list of accumulated expansions3796 * for each outer expansion, set or sequence node. The first element3797 * in the list is an identity mapping on the reaching domain elements.3798 * "res" collects the results.3799 */3800struct isl_subtree_expansion_data {3801 isl_union_map_list *expansions;3802 isl_union_map *res;3803};3804 3805/* Callback for "traverse" to enter a node and to move3806 * to the deepest initial subtree that should be traversed3807 * by isl_schedule_node_get_subtree_expansion.3808 *3809 * Whenever we come across an expansion node, the last element3810 * of data->expansions is combined with the expansion3811 * on the expansion node.3812 *3813 * Whenever we come across a filter node that is the child3814 * of a set or sequence node, data->expansions is extended3815 * with a new element that restricts the previous element3816 * to the elements selected by the filter.3817 * The previous element can then be reused while backtracking.3818 */3819static __isl_give isl_schedule_node *subtree_expansion_enter(3820 __isl_take isl_schedule_node *node, void *user)3821{3822 struct isl_subtree_expansion_data *data = user;3823 3824 do {3825 enum isl_schedule_node_type type;3826 isl_union_set *filter;3827 isl_union_map *inner, *expansion;3828 isl_size n;3829 3830 switch (isl_schedule_node_get_type(node)) {3831 case isl_schedule_node_error:3832 return isl_schedule_node_free(node);3833 case isl_schedule_node_filter:3834 type = isl_schedule_node_get_parent_type(node);3835 if (type != isl_schedule_node_set &&3836 type != isl_schedule_node_sequence)3837 break;3838 filter = isl_schedule_node_filter_get_filter(node);3839 n = isl_union_map_list_n_union_map(data->expansions);3840 if (n < 0)3841 data->expansions =3842 isl_union_map_list_free(data->expansions);3843 inner =3844 isl_union_map_list_get_union_map(data->expansions,3845 n - 1);3846 inner = isl_union_map_intersect_range(inner, filter);3847 data->expansions =3848 isl_union_map_list_add(data->expansions, inner);3849 break;3850 case isl_schedule_node_expansion:3851 n = isl_union_map_list_n_union_map(data->expansions);3852 if (n < 0)3853 data->expansions =3854 isl_union_map_list_free(data->expansions);3855 expansion =3856 isl_schedule_node_expansion_get_expansion(node);3857 inner =3858 isl_union_map_list_get_union_map(data->expansions,3859 n - 1);3860 inner = isl_union_map_apply_range(inner, expansion);3861 data->expansions =3862 isl_union_map_list_set_union_map(data->expansions,3863 n - 1, inner);3864 break;3865 case isl_schedule_node_band:3866 case isl_schedule_node_context:3867 case isl_schedule_node_domain:3868 case isl_schedule_node_extension:3869 case isl_schedule_node_guard:3870 case isl_schedule_node_leaf:3871 case isl_schedule_node_mark:3872 case isl_schedule_node_sequence:3873 case isl_schedule_node_set:3874 break;3875 }3876 } while (isl_schedule_node_has_children(node) &&3877 (node = isl_schedule_node_first_child(node)) != NULL);3878 3879 return node;3880}3881 3882/* Callback for "traverse" to leave a node for3883 * isl_schedule_node_get_subtree_expansion.3884 *3885 * If we come across a filter node that is the child3886 * of a set or sequence node, then we remove the element3887 * of data->expansions that was added in subtree_expansion_enter.3888 *3889 * If we reach a leaf node, then the accumulated expansion is3890 * added to data->res.3891 */3892static __isl_give isl_schedule_node *subtree_expansion_leave(3893 __isl_take isl_schedule_node *node, void *user)3894{3895 struct isl_subtree_expansion_data *data = user;3896 isl_size n;3897 isl_union_map *inner;3898 enum isl_schedule_node_type type;3899 3900 switch (isl_schedule_node_get_type(node)) {3901 case isl_schedule_node_error:3902 return isl_schedule_node_free(node);3903 case isl_schedule_node_filter:3904 type = isl_schedule_node_get_parent_type(node);3905 if (type != isl_schedule_node_set &&3906 type != isl_schedule_node_sequence)3907 break;3908 n = isl_union_map_list_n_union_map(data->expansions);3909 if (n < 0)3910 data->expansions =3911 isl_union_map_list_free(data->expansions);3912 data->expansions = isl_union_map_list_drop(data->expansions,3913 n - 1, 1);3914 break;3915 case isl_schedule_node_leaf:3916 n = isl_union_map_list_n_union_map(data->expansions);3917 if (n < 0)3918 data->expansions =3919 isl_union_map_list_free(data->expansions);3920 inner = isl_union_map_list_get_union_map(data->expansions,3921 n - 1);3922 data->res = isl_union_map_union(data->res, inner);3923 break;3924 case isl_schedule_node_band:3925 case isl_schedule_node_context:3926 case isl_schedule_node_domain:3927 case isl_schedule_node_expansion:3928 case isl_schedule_node_extension:3929 case isl_schedule_node_guard:3930 case isl_schedule_node_mark:3931 case isl_schedule_node_sequence:3932 case isl_schedule_node_set:3933 break;3934 }3935 3936 return node;3937}3938 3939/* Return a mapping from the domain elements that reach "node"3940 * to the corresponding domain elements in the leaves of the subtree3941 * rooted at "node" obtained by composing the intermediate expansions.3942 *3943 * We start out with an identity mapping between the domain elements3944 * that reach "node" and compose it with all the expansions3945 * on a path from "node" to a leaf while traversing the subtree.3946 * Within the children of an a sequence or set node, the3947 * accumulated expansion is restricted to the elements selected3948 * by the filter child.3949 */3950__isl_give isl_union_map *isl_schedule_node_get_subtree_expansion(3951 __isl_keep isl_schedule_node *node)3952{3953 struct isl_subtree_expansion_data data;3954 isl_space *space;3955 isl_union_set *domain;3956 isl_union_map *expansion;3957 3958 if (!node)3959 return NULL;3960 3961 domain = isl_schedule_node_get_universe_domain(node);3962 space = isl_union_set_get_space(domain);3963 expansion = isl_union_set_identity(domain);3964 data.res = isl_union_map_empty(space);3965 data.expansions = isl_union_map_list_from_union_map(expansion);3966 3967 node = isl_schedule_node_copy(node);3968 node = traverse(node, &subtree_expansion_enter,3969 &subtree_expansion_leave, &data);3970 if (!node)3971 data.res = isl_union_map_free(data.res);3972 isl_schedule_node_free(node);3973 3974 isl_union_map_list_free(data.expansions);3975 3976 return data.res;3977}3978 3979/* Internal data structure for isl_schedule_node_get_subtree_contraction.3980 * "contractions" contains a list of accumulated contractions3981 * for each outer expansion, set or sequence node. The first element3982 * in the list is an identity mapping on the reaching domain elements.3983 * "res" collects the results.3984 */3985struct isl_subtree_contraction_data {3986 isl_union_pw_multi_aff_list *contractions;3987 isl_union_pw_multi_aff *res;3988};3989 3990/* Callback for "traverse" to enter a node and to move3991 * to the deepest initial subtree that should be traversed3992 * by isl_schedule_node_get_subtree_contraction.3993 *3994 * Whenever we come across an expansion node, the last element3995 * of data->contractions is combined with the contraction3996 * on the expansion node.3997 *3998 * Whenever we come across a filter node that is the child3999 * of a set or sequence node, data->contractions is extended4000 * with a new element that restricts the previous element4001 * to the elements selected by the filter.4002 * The previous element can then be reused while backtracking.4003 */4004static __isl_give isl_schedule_node *subtree_contraction_enter(4005 __isl_take isl_schedule_node *node, void *user)4006{4007 struct isl_subtree_contraction_data *data = user;4008 4009 do {4010 enum isl_schedule_node_type type;4011 isl_union_set *filter;4012 isl_union_pw_multi_aff *inner, *contraction;4013 isl_size n;4014 4015 switch (isl_schedule_node_get_type(node)) {4016 case isl_schedule_node_error:4017 return isl_schedule_node_free(node);4018 case isl_schedule_node_filter:4019 type = isl_schedule_node_get_parent_type(node);4020 if (type != isl_schedule_node_set &&4021 type != isl_schedule_node_sequence)4022 break;4023 filter = isl_schedule_node_filter_get_filter(node);4024 n = isl_union_pw_multi_aff_list_n_union_pw_multi_aff(4025 data->contractions);4026 if (n < 0)4027 data->contractions =4028 isl_union_pw_multi_aff_list_free(4029 data->contractions);4030 inner =4031 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(4032 data->contractions, n - 1);4033 inner = isl_union_pw_multi_aff_intersect_domain(inner,4034 filter);4035 data->contractions =4036 isl_union_pw_multi_aff_list_add(data->contractions,4037 inner);4038 break;4039 case isl_schedule_node_expansion:4040 n = isl_union_pw_multi_aff_list_n_union_pw_multi_aff(4041 data->contractions);4042 if (n < 0)4043 data->contractions =4044 isl_union_pw_multi_aff_list_free(4045 data->contractions);4046 contraction =4047 isl_schedule_node_expansion_get_contraction(node);4048 inner =4049 isl_union_pw_multi_aff_list_get_union_pw_multi_aff(4050 data->contractions, n - 1);4051 inner =4052 isl_union_pw_multi_aff_pullback_union_pw_multi_aff(4053 inner, contraction);4054 data->contractions =4055 isl_union_pw_multi_aff_list_set_union_pw_multi_aff(4056 data->contractions, n - 1, inner);4057 break;4058 case isl_schedule_node_band:4059 case isl_schedule_node_context:4060 case isl_schedule_node_domain:4061 case isl_schedule_node_extension:4062 case isl_schedule_node_guard:4063 case isl_schedule_node_leaf:4064 case isl_schedule_node_mark:4065 case isl_schedule_node_sequence:4066 case isl_schedule_node_set:4067 break;4068 }4069 } while (isl_schedule_node_has_children(node) &&4070 (node = isl_schedule_node_first_child(node)) != NULL);4071 4072 return node;4073}4074 4075/* Callback for "traverse" to leave a node for4076 * isl_schedule_node_get_subtree_contraction.4077 *4078 * If we come across a filter node that is the child4079 * of a set or sequence node, then we remove the element4080 * of data->contractions that was added in subtree_contraction_enter.4081 *4082 * If we reach a leaf node, then the accumulated contraction is4083 * added to data->res.4084 */4085static __isl_give isl_schedule_node *subtree_contraction_leave(4086 __isl_take isl_schedule_node *node, void *user)4087{4088 struct isl_subtree_contraction_data *data = user;4089 isl_size n;4090 isl_union_pw_multi_aff *inner;4091 enum isl_schedule_node_type type;4092 4093 switch (isl_schedule_node_get_type(node)) {4094 case isl_schedule_node_error:4095 return isl_schedule_node_free(node);4096 case isl_schedule_node_filter:4097 type = isl_schedule_node_get_parent_type(node);4098 if (type != isl_schedule_node_set &&4099 type != isl_schedule_node_sequence)4100 break;4101 n = isl_union_pw_multi_aff_list_n_union_pw_multi_aff(4102 data->contractions);4103 if (n < 0)4104 data->contractions = isl_union_pw_multi_aff_list_free(4105 data->contractions);4106 data->contractions =4107 isl_union_pw_multi_aff_list_drop(data->contractions,4108 n - 1, 1);4109 break;4110 case isl_schedule_node_leaf:4111 n = isl_union_pw_multi_aff_list_n_union_pw_multi_aff(4112 data->contractions);4113 if (n < 0)4114 data->contractions = isl_union_pw_multi_aff_list_free(4115 data->contractions);4116 inner = isl_union_pw_multi_aff_list_get_union_pw_multi_aff(4117 data->contractions, n - 1);4118 data->res = isl_union_pw_multi_aff_union_add(data->res, inner);4119 break;4120 case isl_schedule_node_band:4121 case isl_schedule_node_context:4122 case isl_schedule_node_domain:4123 case isl_schedule_node_expansion:4124 case isl_schedule_node_extension:4125 case isl_schedule_node_guard:4126 case isl_schedule_node_mark:4127 case isl_schedule_node_sequence:4128 case isl_schedule_node_set:4129 break;4130 }4131 4132 return node;4133}4134 4135/* Return a mapping from the domain elements in the leaves of the subtree4136 * rooted at "node" to the corresponding domain elements that reach "node"4137 * obtained by composing the intermediate contractions.4138 *4139 * We start out with an identity mapping between the domain elements4140 * that reach "node" and compose it with all the contractions4141 * on a path from "node" to a leaf while traversing the subtree.4142 * Within the children of an a sequence or set node, the4143 * accumulated contraction is restricted to the elements selected4144 * by the filter child.4145 */4146__isl_give isl_union_pw_multi_aff *isl_schedule_node_get_subtree_contraction(4147 __isl_keep isl_schedule_node *node)4148{4149 struct isl_subtree_contraction_data data;4150 isl_space *space;4151 isl_union_set *domain;4152 isl_union_pw_multi_aff *contraction;4153 4154 if (!node)4155 return NULL;4156 4157 domain = isl_schedule_node_get_universe_domain(node);4158 space = isl_union_set_get_space(domain);4159 contraction = isl_union_set_identity_union_pw_multi_aff(domain);4160 data.res = isl_union_pw_multi_aff_empty(space);4161 data.contractions =4162 isl_union_pw_multi_aff_list_from_union_pw_multi_aff(contraction);4163 4164 node = isl_schedule_node_copy(node);4165 node = traverse(node, &subtree_contraction_enter,4166 &subtree_contraction_leave, &data);4167 if (!node)4168 data.res = isl_union_pw_multi_aff_free(data.res);4169 isl_schedule_node_free(node);4170 4171 isl_union_pw_multi_aff_list_free(data.contractions);4172 4173 return data.res;4174}4175 4176/* Do the nearest "n" ancestors of "node" have the types given in "types"4177 * (starting at the parent of "node")?4178 */4179static isl_bool has_ancestors(__isl_keep isl_schedule_node *node,4180 int n, enum isl_schedule_node_type *types)4181{4182 int i;4183 isl_size n_ancestor;4184 4185 if (!node)4186 return isl_bool_error;4187 4188 n_ancestor = isl_schedule_tree_list_n_schedule_tree(node->ancestors);4189 if (n_ancestor < 0)4190 return isl_bool_error;4191 if (n_ancestor < n)4192 return isl_bool_false;4193 4194 for (i = 0; i < n; ++i) {4195 isl_schedule_tree *tree;4196 int correct_type;4197 4198 tree = isl_schedule_tree_list_get_schedule_tree(node->ancestors,4199 n_ancestor - 1 - i);4200 if (!tree)4201 return isl_bool_error;4202 correct_type = isl_schedule_tree_get_type(tree) == types[i];4203 isl_schedule_tree_free(tree);4204 if (!correct_type)4205 return isl_bool_false;4206 }4207 4208 return isl_bool_true;4209}4210 4211/* Given a node "node" that appears in an extension (i.e., it is the child4212 * of a filter in a sequence inside an extension node), are the spaces4213 * of the extension specified by "extension" disjoint from those4214 * of both the original extension and the domain elements that reach4215 * that original extension?4216 */4217static isl_bool is_disjoint_extension(__isl_keep isl_schedule_node *node,4218 __isl_keep isl_union_map *extension)4219{4220 isl_union_map *old;4221 isl_union_set *domain;4222 isl_bool empty;4223 4224 node = isl_schedule_node_copy(node);4225 node = isl_schedule_node_ancestor(node, 3);4226 old = isl_schedule_node_extension_get_extension(node);4227 domain = isl_schedule_node_get_universe_domain(node);4228 isl_schedule_node_free(node);4229 old = isl_union_map_universe(old);4230 domain = isl_union_set_union(domain, isl_union_map_range(old));4231 extension = isl_union_map_copy(extension);4232 extension = isl_union_map_intersect_range(extension, domain);4233 empty = isl_union_map_is_empty(extension);4234 isl_union_map_free(extension);4235 4236 return empty;4237}4238 4239/* Given a node "node" that is governed by an extension node, extend4240 * that extension node with "extension".4241 *4242 * In particular, "node" is the child of a filter in a sequence that4243 * is in turn a child of an extension node. Extend that extension node4244 * with "extension".4245 *4246 * Return a pointer to the parent of the original node (i.e., a filter).4247 */4248static __isl_give isl_schedule_node *extend_extension(4249 __isl_take isl_schedule_node *node, __isl_take isl_union_map *extension)4250{4251 isl_size pos;4252 isl_bool disjoint;4253 isl_union_map *node_extension;4254 4255 node = isl_schedule_node_parent(node);4256 pos = isl_schedule_node_get_child_position(node);4257 if (pos < 0)4258 node = isl_schedule_node_free(node);4259 node = isl_schedule_node_grandparent(node);4260 node_extension = isl_schedule_node_extension_get_extension(node);4261 disjoint = isl_union_map_is_disjoint(extension, node_extension);4262 extension = isl_union_map_union(extension, node_extension);4263 node = isl_schedule_node_extension_set_extension(node, extension);4264 node = isl_schedule_node_grandchild(node, 0, pos);4265 4266 if (disjoint < 0)4267 return isl_schedule_node_free(node);4268 if (!node)4269 return NULL;4270 if (!disjoint)4271 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,4272 "extension domain should be disjoint from earlier "4273 "extensions", return isl_schedule_node_free(node));4274 4275 return node;4276}4277 4278/* Return the universe of "uset" if this universe is disjoint from "ref".4279 * Otherwise, return "uset".4280 *4281 * Also check if "uset" itself is disjoint from "ref", reporting4282 * an error if it is not.4283 */4284static __isl_give isl_union_set *replace_by_universe_if_disjoint(4285 __isl_take isl_union_set *uset, __isl_keep isl_union_set *ref)4286{4287 int disjoint;4288 isl_union_set *universe;4289 4290 disjoint = isl_union_set_is_disjoint(uset, ref);4291 if (disjoint < 0)4292 return isl_union_set_free(uset);4293 if (!disjoint)4294 isl_die(isl_union_set_get_ctx(uset), isl_error_invalid,4295 "extension domain should be disjoint from "4296 "current domain", return isl_union_set_free(uset));4297 4298 universe = isl_union_set_universe(isl_union_set_copy(uset));4299 disjoint = isl_union_set_is_disjoint(universe, ref);4300 if (disjoint >= 0 && disjoint) {4301 isl_union_set_free(uset);4302 return universe;4303 }4304 isl_union_set_free(universe);4305 4306 if (disjoint < 0)4307 return isl_union_set_free(uset);4308 return uset;4309}4310 4311/* Insert an extension node on top of "node" with extension "extension".4312 * In addition, insert a filter that separates node from the extension4313 * between the extension node and "node".4314 * Return a pointer to the inserted filter node.4315 *4316 * If "node" already appears in an extension (i.e., if it is the child4317 * of a filter in a sequence inside an extension node), then extend that4318 * extension with "extension" instead.4319 * In this case, a pointer to the original filter node is returned.4320 * Note that if some of the elements in the new extension live in the4321 * same space as those of the original extension or the domain elements4322 * reaching the original extension, then we insert a new extension anyway.4323 * Otherwise, we would have to adjust the filters in the sequence child4324 * of the extension to ensure that the elements in the new extension4325 * are filtered out.4326 */4327static __isl_give isl_schedule_node *insert_extension(4328 __isl_take isl_schedule_node *node, __isl_take isl_union_map *extension)4329{4330 enum isl_schedule_node_type ancestors[] =4331 { isl_schedule_node_filter, isl_schedule_node_sequence,4332 isl_schedule_node_extension };4333 isl_union_set *domain;4334 isl_union_set *filter;4335 isl_bool in_ext;4336 4337 in_ext = has_ancestors(node, 3, ancestors);4338 if (in_ext < 0)4339 goto error;4340 if (in_ext) {4341 isl_bool disjoint;4342 4343 disjoint = is_disjoint_extension(node, extension);4344 if (disjoint < 0)4345 goto error;4346 if (disjoint)4347 return extend_extension(node, extension);4348 }4349 4350 filter = isl_schedule_node_get_domain(node);4351 domain = isl_union_map_range(isl_union_map_copy(extension));4352 filter = replace_by_universe_if_disjoint(filter, domain);4353 isl_union_set_free(domain);4354 4355 node = isl_schedule_node_insert_filter(node, filter);4356 node = isl_schedule_node_insert_extension(node, extension);4357 node = isl_schedule_node_child(node, 0);4358 return node;4359error:4360 isl_schedule_node_free(node);4361 isl_union_map_free(extension);4362 return NULL;4363}4364 4365/* Replace the subtree that "node" points to by "tree" (which has4366 * a sequence root with two children), except if the parent of "node"4367 * is a sequence as well, in which case "tree" is spliced at the position4368 * of "node" in its parent.4369 * Return a pointer to the child of the "tree_pos" (filter) child of "tree"4370 * in the updated schedule tree.4371 */4372static __isl_give isl_schedule_node *graft_or_splice(4373 __isl_take isl_schedule_node *node, __isl_take isl_schedule_tree *tree,4374 int tree_pos)4375{4376 isl_size pos;4377 4378 if (isl_schedule_node_get_parent_type(node) ==4379 isl_schedule_node_sequence) {4380 pos = isl_schedule_node_get_child_position(node);4381 if (pos < 0)4382 node = isl_schedule_node_free(node);4383 node = isl_schedule_node_parent(node);4384 node = isl_schedule_node_sequence_splice(node, pos, tree);4385 } else {4386 pos = 0;4387 node = isl_schedule_node_graft_tree(node, tree);4388 }4389 node = isl_schedule_node_grandchild(node, pos + tree_pos, 0);4390 4391 return node;4392}4393 4394/* Insert a node "graft" into the schedule tree of "node" such that it4395 * is executed before (if "before" is set) or after (if "before" is not set)4396 * the node that "node" points to.4397 * The root of "graft" is an extension node.4398 * Return a pointer to the node that "node" pointed to.4399 *4400 * We first insert an extension node on top of "node" (or extend4401 * the extension node if there already is one), with a filter on "node"4402 * separating it from the extension.4403 * We then insert a filter in the graft to separate it from the original4404 * domain elements and combine the original and new tree in a sequence.4405 * If we have extended an extension node, then the children of this4406 * sequence are spliced in the sequence of the extended extension4407 * at the position where "node" appears in the original extension.4408 * Otherwise, the sequence pair is attached to the new extension node.4409 */4410static __isl_give isl_schedule_node *graft_extension(4411 __isl_take isl_schedule_node *node, __isl_take isl_schedule_node *graft,4412 int before)4413{4414 isl_union_map *extension;4415 isl_union_set *graft_domain;4416 isl_union_set *node_domain;4417 isl_schedule_tree *tree, *tree_graft;4418 4419 extension = isl_schedule_node_extension_get_extension(graft);4420 graft_domain = isl_union_map_range(isl_union_map_copy(extension));4421 node_domain = isl_schedule_node_get_universe_domain(node);4422 node = insert_extension(node, extension);4423 4424 graft_domain = replace_by_universe_if_disjoint(graft_domain,4425 node_domain);4426 isl_union_set_free(node_domain);4427 4428 tree = isl_schedule_node_get_tree(node);4429 if (!isl_schedule_node_has_children(graft)) {4430 tree_graft = isl_schedule_tree_from_filter(graft_domain);4431 } else {4432 graft = isl_schedule_node_child(graft, 0);4433 tree_graft = isl_schedule_node_get_tree(graft);4434 tree_graft = isl_schedule_tree_insert_filter(tree_graft,4435 graft_domain);4436 }4437 if (before)4438 tree = isl_schedule_tree_sequence_pair(tree_graft, tree);4439 else4440 tree = isl_schedule_tree_sequence_pair(tree, tree_graft);4441 node = graft_or_splice(node, tree, before);4442 4443 isl_schedule_node_free(graft);4444 4445 return node;4446}4447 4448/* Replace the root domain node of "node" by an extension node suitable4449 * for insertion at "pos".4450 * That is, create an extension node that maps the outer band nodes4451 * at "pos" to the domain of the root node of "node" and attach4452 * the child of this root node to the extension node.4453 */4454static __isl_give isl_schedule_node *extension_from_domain(4455 __isl_take isl_schedule_node *node, __isl_keep isl_schedule_node *pos)4456{4457 isl_union_set *universe;4458 isl_union_set *domain;4459 isl_union_map *ext;4460 isl_size depth;4461 isl_bool anchored;4462 isl_space *space;4463 isl_schedule_node *res;4464 isl_schedule_tree *tree;4465 4466 depth = isl_schedule_node_get_schedule_depth(pos);4467 anchored = isl_schedule_node_is_subtree_anchored(node);4468 if (depth < 0 || anchored < 0)4469 return isl_schedule_node_free(node);4470 if (anchored)4471 isl_die(isl_schedule_node_get_ctx(node), isl_error_unsupported,4472 "cannot graft anchored tree with domain root",4473 return isl_schedule_node_free(node));4474 4475 domain = isl_schedule_node_domain_get_domain(node);4476 space = isl_union_set_get_space(domain);4477 space = isl_space_set_from_params(space);4478 space = isl_space_add_dims(space, isl_dim_set, depth);4479 universe = isl_union_set_from_set(isl_set_universe(space));4480 ext = isl_union_map_from_domain_and_range(universe, domain);4481 res = isl_schedule_node_from_extension(ext);4482 node = isl_schedule_node_child(node, 0);4483 if (!node)4484 return isl_schedule_node_free(res);4485 if (!isl_schedule_tree_is_leaf(node->tree)) {4486 tree = isl_schedule_node_get_tree(node);4487 res = isl_schedule_node_child(res, 0);4488 res = isl_schedule_node_graft_tree(res, tree);4489 res = isl_schedule_node_parent(res);4490 }4491 isl_schedule_node_free(node);4492 4493 return res;4494}4495 4496/* Insert a node "graft" into the schedule tree of "node" such that it4497 * is executed before (if "before" is set) or after (if "before" is not set)4498 * the node that "node" points to.4499 * The root of "graft" may be either a domain or an extension node.4500 * In the latter case, the domain of the extension needs to correspond4501 * to the outer band nodes of "node".4502 * The elements of the domain or the range of the extension may not4503 * intersect with the domain elements that reach "node".4504 * The schedule tree of "graft" may not be anchored.4505 *4506 * The schedule tree of "node" is modified to include an extension node4507 * corresponding to the root node of "graft" as a child of the original4508 * parent of "node". The original node that "node" points to and the4509 * child of the root node of "graft" are attached to this extension node4510 * through a sequence, with appropriate filters and with the child4511 * of "graft" appearing before or after the original "node".4512 *4513 * If "node" already appears inside a sequence that is the child of4514 * an extension node and if the spaces of the new domain elements4515 * do not overlap with those of the original domain elements,4516 * then that extension node is extended with the new extension4517 * rather than introducing a new segment of extension and sequence nodes.4518 *4519 * Return a pointer to the same node in the modified tree that4520 * "node" pointed to in the original tree.4521 */4522static __isl_give isl_schedule_node *isl_schedule_node_graft_before_or_after(4523 __isl_take isl_schedule_node *node, __isl_take isl_schedule_node *graft,4524 int before)4525{4526 if (!node || !graft)4527 goto error;4528 if (check_insert(node) < 0)4529 goto error;4530 4531 if (isl_schedule_node_get_type(graft) == isl_schedule_node_domain)4532 graft = extension_from_domain(graft, node);4533 4534 if (!graft)4535 goto error;4536 if (isl_schedule_node_get_type(graft) != isl_schedule_node_extension)4537 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,4538 "expecting domain or extension as root of graft",4539 goto error);4540 4541 return graft_extension(node, graft, before);4542error:4543 isl_schedule_node_free(node);4544 isl_schedule_node_free(graft);4545 return NULL;4546}4547 4548/* Insert a node "graft" into the schedule tree of "node" such that it4549 * is executed before the node that "node" points to.4550 * The root of "graft" may be either a domain or an extension node.4551 * In the latter case, the domain of the extension needs to correspond4552 * to the outer band nodes of "node".4553 * The elements of the domain or the range of the extension may not4554 * intersect with the domain elements that reach "node".4555 * The schedule tree of "graft" may not be anchored.4556 *4557 * Return a pointer to the same node in the modified tree that4558 * "node" pointed to in the original tree.4559 */4560__isl_give isl_schedule_node *isl_schedule_node_graft_before(4561 __isl_take isl_schedule_node *node, __isl_take isl_schedule_node *graft)4562{4563 return isl_schedule_node_graft_before_or_after(node, graft, 1);4564}4565 4566/* Insert a node "graft" into the schedule tree of "node" such that it4567 * is executed after the node that "node" points to.4568 * The root of "graft" may be either a domain or an extension node.4569 * In the latter case, the domain of the extension needs to correspond4570 * to the outer band nodes of "node".4571 * The elements of the domain or the range of the extension may not4572 * intersect with the domain elements that reach "node".4573 * The schedule tree of "graft" may not be anchored.4574 *4575 * Return a pointer to the same node in the modified tree that4576 * "node" pointed to in the original tree.4577 */4578__isl_give isl_schedule_node *isl_schedule_node_graft_after(4579 __isl_take isl_schedule_node *node,4580 __isl_take isl_schedule_node *graft)4581{4582 return isl_schedule_node_graft_before_or_after(node, graft, 0);4583}4584 4585/* Split the domain elements that reach "node" into those that satisfy4586 * "filter" and those that do not. Arrange for the first subset to be4587 * executed before or after the second subset, depending on the value4588 * of "before".4589 * Return a pointer to the tree corresponding to the second subset,4590 * except when this subset is empty in which case the original pointer4591 * is returned.4592 * If both subsets are non-empty, then a sequence node is introduced4593 * to impose the order. If the grandparent of the original node was4594 * itself a sequence, then the original child is replaced by two children4595 * in this sequence instead.4596 * The children in the sequence are copies of the original subtree,4597 * simplified with respect to their filters.4598 */4599static __isl_give isl_schedule_node *isl_schedule_node_order_before_or_after(4600 __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter,4601 int before)4602{4603 enum isl_schedule_node_type ancestors[] =4604 { isl_schedule_node_filter, isl_schedule_node_sequence };4605 isl_union_set *node_domain, *node_filter = NULL, *parent_filter;4606 isl_schedule_node *node2;4607 isl_schedule_tree *tree1, *tree2;4608 isl_bool empty1, empty2;4609 isl_bool in_seq;4610 4611 if (!node || !filter)4612 goto error;4613 if (check_insert(node) < 0)4614 goto error;4615 4616 in_seq = has_ancestors(node, 2, ancestors);4617 if (in_seq < 0)4618 goto error;4619 node_domain = isl_schedule_node_get_domain(node);4620 filter = isl_union_set_gist(filter, isl_union_set_copy(node_domain));4621 node_filter = isl_union_set_copy(node_domain);4622 node_filter = isl_union_set_subtract(node_filter,4623 isl_union_set_copy(filter));4624 node_filter = isl_union_set_gist(node_filter, node_domain);4625 empty1 = isl_union_set_is_empty(filter);4626 empty2 = isl_union_set_is_empty(node_filter);4627 if (empty1 < 0 || empty2 < 0)4628 goto error;4629 if (empty1 || empty2) {4630 isl_union_set_free(filter);4631 isl_union_set_free(node_filter);4632 return node;4633 }4634 4635 if (in_seq) {4636 node = isl_schedule_node_parent(node);4637 parent_filter = isl_schedule_node_filter_get_filter(node);4638 node_filter = isl_union_set_intersect(node_filter,4639 isl_union_set_copy(parent_filter));4640 filter = isl_union_set_intersect(filter, parent_filter);4641 }4642 4643 node2 = isl_schedule_node_copy(node);4644 node = isl_schedule_node_gist(node, isl_union_set_copy(node_filter));4645 node2 = isl_schedule_node_gist(node2, isl_union_set_copy(filter));4646 tree1 = isl_schedule_node_get_tree(node);4647 tree2 = isl_schedule_node_get_tree(node2);4648 tree1 = isl_schedule_tree_insert_filter(tree1, node_filter);4649 tree2 = isl_schedule_tree_insert_filter(tree2, filter);4650 isl_schedule_node_free(node2);4651 4652 if (before) {4653 tree1 = isl_schedule_tree_sequence_pair(tree2, tree1);4654 node = graft_or_splice(node, tree1, 1);4655 } else {4656 tree1 = isl_schedule_tree_sequence_pair(tree1, tree2);4657 node = graft_or_splice(node, tree1, 0);4658 }4659 4660 return node;4661error:4662 isl_schedule_node_free(node);4663 isl_union_set_free(filter);4664 isl_union_set_free(node_filter);4665 return NULL;4666}4667 4668/* Split the domain elements that reach "node" into those that satisfy4669 * "filter" and those that do not. Arrange for the first subset to be4670 * executed before the second subset.4671 * Return a pointer to the tree corresponding to the second subset,4672 * except when this subset is empty in which case the original pointer4673 * is returned.4674 */4675__isl_give isl_schedule_node *isl_schedule_node_order_before(4676 __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter)4677{4678 return isl_schedule_node_order_before_or_after(node, filter, 1);4679}4680 4681/* Split the domain elements that reach "node" into those that satisfy4682 * "filter" and those that do not. Arrange for the first subset to be4683 * executed after the second subset.4684 * Return a pointer to the tree corresponding to the second subset,4685 * except when this subset is empty in which case the original pointer4686 * is returned.4687 */4688__isl_give isl_schedule_node *isl_schedule_node_order_after(4689 __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter)4690{4691 return isl_schedule_node_order_before_or_after(node, filter, 0);4692}4693 4694/* Reset the user pointer on all identifiers of parameters and tuples4695 * in the schedule node "node".4696 */4697__isl_give isl_schedule_node *isl_schedule_node_reset_user(4698 __isl_take isl_schedule_node *node)4699{4700 isl_schedule_tree *tree;4701 4702 tree = isl_schedule_node_get_tree(node);4703 tree = isl_schedule_tree_reset_user(tree);4704 node = isl_schedule_node_graft_tree(node, tree);4705 4706 return node;4707}4708 4709/* Align the parameters of the schedule node "node" to those of "space".4710 */4711__isl_give isl_schedule_node *isl_schedule_node_align_params(4712 __isl_take isl_schedule_node *node, __isl_take isl_space *space)4713{4714 isl_schedule_tree *tree;4715 4716 tree = isl_schedule_node_get_tree(node);4717 tree = isl_schedule_tree_align_params(tree, space);4718 node = isl_schedule_node_graft_tree(node, tree);4719 4720 return node;4721}4722 4723/* Compute the pullback of schedule node "node"4724 * by the function represented by "upma".4725 * In other words, plug in "upma" in the iteration domains4726 * of schedule node "node".4727 * We currently do not handle expansion nodes.4728 *4729 * Note that this is only a helper function for4730 * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency,4731 * this function should not be called on a single node without also4732 * calling it on all the other nodes.4733 */4734__isl_give isl_schedule_node *isl_schedule_node_pullback_union_pw_multi_aff(4735 __isl_take isl_schedule_node *node,4736 __isl_take isl_union_pw_multi_aff *upma)4737{4738 isl_schedule_tree *tree;4739 4740 tree = isl_schedule_node_get_tree(node);4741 tree = isl_schedule_tree_pullback_union_pw_multi_aff(tree, upma);4742 node = isl_schedule_node_graft_tree(node, tree);4743 4744 return node;4745}4746 4747/* Internal data structure for isl_schedule_node_expand.4748 * "tree" is the tree that needs to be plugged in in all the leaves.4749 * "domain" is the set of domain elements in the original leaves4750 * to which the tree applies.4751 */4752struct isl_schedule_expand_data {4753 isl_schedule_tree *tree;4754 isl_union_set *domain;4755};4756 4757/* If "node" is a leaf, then plug in data->tree, simplifying it4758 * within its new context.4759 *4760 * If there are any domain elements at the leaf where the tree4761 * should not be plugged in (i.e., there are elements not in data->domain)4762 * then first extend the tree to only apply to the elements in data->domain4763 * by constructing a set node that selects data->tree for elements4764 * in data->domain and a leaf for the other elements.4765 */4766static __isl_give isl_schedule_node *expand(__isl_take isl_schedule_node *node,4767 void *user)4768{4769 struct isl_schedule_expand_data *data = user;4770 isl_schedule_tree *tree, *leaf;4771 isl_union_set *domain, *left;4772 isl_bool empty;4773 4774 if (isl_schedule_node_get_type(node) != isl_schedule_node_leaf)4775 return node;4776 4777 domain = isl_schedule_node_get_domain(node);4778 tree = isl_schedule_tree_copy(data->tree);4779 4780 left = isl_union_set_copy(domain);4781 left = isl_union_set_subtract(left, isl_union_set_copy(data->domain));4782 empty = isl_union_set_is_empty(left);4783 if (empty >= 0 && !empty) {4784 leaf = isl_schedule_node_get_leaf(node);4785 leaf = isl_schedule_tree_insert_filter(leaf, left);4786 left = isl_union_set_copy(data->domain);4787 tree = isl_schedule_tree_insert_filter(tree, left);4788 tree = isl_schedule_tree_set_pair(tree, leaf);4789 } else {4790 if (empty < 0)4791 node = isl_schedule_node_free(node);4792 isl_union_set_free(left);4793 }4794 4795 node = isl_schedule_node_graft_tree(node, tree);4796 node = isl_schedule_node_gist(node, domain);4797 4798 return node;4799}4800 4801/* Expand the tree rooted at "node" by extending all leaves4802 * with an expansion node with as child "tree".4803 * The expansion is determined by "contraction" and "domain".4804 * That is, the elements of "domain" are contracted according4805 * to "contraction". The expansion relation is then the inverse4806 * of "contraction" with its range intersected with "domain".4807 *4808 * Insert the appropriate expansion node on top of "tree" and4809 * then plug in the result in all leaves of "node".4810 */4811__isl_give isl_schedule_node *isl_schedule_node_expand(4812 __isl_take isl_schedule_node *node,4813 __isl_take isl_union_pw_multi_aff *contraction,4814 __isl_take isl_union_set *domain,4815 __isl_take isl_schedule_tree *tree)4816{4817 struct isl_schedule_expand_data data;4818 isl_union_map *expansion;4819 isl_union_pw_multi_aff *copy;4820 4821 if (!node || !contraction || !tree)4822 node = isl_schedule_node_free(node);4823 4824 copy = isl_union_pw_multi_aff_copy(contraction);4825 expansion = isl_union_map_from_union_pw_multi_aff(copy);4826 expansion = isl_union_map_reverse(expansion);4827 expansion = isl_union_map_intersect_range(expansion, domain);4828 data.domain = isl_union_map_domain(isl_union_map_copy(expansion));4829 4830 tree = isl_schedule_tree_insert_expansion(tree, contraction, expansion);4831 data.tree = tree;4832 4833 node = isl_schedule_node_map_descendant_bottom_up(node, &expand, &data);4834 isl_union_set_free(data.domain);4835 isl_schedule_tree_free(data.tree);4836 return node;4837}4838 4839/* Return the position of the subtree containing "node" among the children4840 * of "ancestor". "node" is assumed to be a descendant of "ancestor".4841 * In particular, both nodes should point to the same schedule tree.4842 *4843 * Return isl_size_error on error.4844 */4845isl_size isl_schedule_node_get_ancestor_child_position(4846 __isl_keep isl_schedule_node *node,4847 __isl_keep isl_schedule_node *ancestor)4848{4849 isl_size n1, n2;4850 isl_schedule_tree *tree;4851 4852 n1 = isl_schedule_node_get_tree_depth(ancestor);4853 n2 = isl_schedule_node_get_tree_depth(node);4854 if (n1 < 0 || n2 < 0)4855 return isl_size_error;4856 4857 if (node->schedule != ancestor->schedule)4858 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,4859 "not a descendant", return isl_size_error);4860 4861 if (n1 >= n2)4862 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,4863 "not a descendant", return isl_size_error);4864 tree = isl_schedule_tree_list_get_schedule_tree(node->ancestors, n1);4865 isl_schedule_tree_free(tree);4866 if (tree != ancestor->tree)4867 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,4868 "not a descendant", return isl_size_error);4869 4870 return node->child_pos[n1];4871}4872 4873/* Given two nodes that point to the same schedule tree, return their4874 * closest shared ancestor.4875 *4876 * Since the two nodes point to the same schedule, they share at least4877 * one ancestor, the root of the schedule. We move down from the root4878 * to the first ancestor where the respective children have a different4879 * child position. This is the requested ancestor.4880 * If there is no ancestor where the children have a different position,4881 * then one node is an ancestor of the other and then this node is4882 * the requested ancestor.4883 */4884__isl_give isl_schedule_node *isl_schedule_node_get_shared_ancestor(4885 __isl_keep isl_schedule_node *node1,4886 __isl_keep isl_schedule_node *node2)4887{4888 int i;4889 isl_size n1, n2;4890 4891 n1 = isl_schedule_node_get_tree_depth(node1);4892 n2 = isl_schedule_node_get_tree_depth(node2);4893 if (n1 < 0 || n2 < 0)4894 return NULL;4895 if (node1->schedule != node2->schedule)4896 isl_die(isl_schedule_node_get_ctx(node1), isl_error_invalid,4897 "not part of same schedule", return NULL);4898 if (n2 < n1)4899 return isl_schedule_node_get_shared_ancestor(node2, node1);4900 if (n1 == 0)4901 return isl_schedule_node_copy(node1);4902 if (isl_schedule_node_is_equal(node1, node2))4903 return isl_schedule_node_copy(node1);4904 4905 for (i = 0; i < n1; ++i)4906 if (node1->child_pos[i] != node2->child_pos[i])4907 break;4908 4909 node1 = isl_schedule_node_copy(node1);4910 return isl_schedule_node_ancestor(node1, n1 - i);4911}4912 4913/* Print "node" to "p".4914 */4915__isl_give isl_printer *isl_printer_print_schedule_node(4916 __isl_take isl_printer *p, __isl_keep isl_schedule_node *node)4917{4918 isl_size n;4919 4920 if (!node)4921 return isl_printer_free(p);4922 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);4923 if (n < 0)4924 return isl_printer_free(p);4925 return isl_printer_print_schedule_tree_mark(p, node->schedule->root, n,4926 node->child_pos);4927}4928 4929void isl_schedule_node_dump(__isl_keep isl_schedule_node *node)4930{4931 isl_ctx *ctx;4932 isl_printer *printer;4933 4934 if (!node)4935 return;4936 4937 ctx = isl_schedule_node_get_ctx(node);4938 printer = isl_printer_to_file(ctx, stderr);4939 printer = isl_printer_set_yaml_style(printer, ISL_YAML_STYLE_BLOCK);4940 printer = isl_printer_print_schedule_node(printer, node);4941 4942 isl_printer_free(printer);4943}4944 4945/* Return a string representation of "node".4946 * Print the schedule node in block format as it would otherwise4947 * look identical to the entire schedule.4948 */4949__isl_give char *isl_schedule_node_to_str(__isl_keep isl_schedule_node *node)4950{4951 isl_printer *printer;4952 char *s;4953 4954 if (!node)4955 return NULL;4956 4957 printer = isl_printer_to_str(isl_schedule_node_get_ctx(node));4958 printer = isl_printer_set_yaml_style(printer, ISL_YAML_STYLE_BLOCK);4959 printer = isl_printer_print_schedule_node(printer, node);4960 s = isl_printer_get_str(printer);4961 isl_printer_free(printer);4962 4963 return s;4964}4965