From 6d403703b5140843ef3e2a49147365e801c8147e Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Sat, 30 Jan 2016 10:13:47 +0100 Subject: [PATCH] isl_schedule_node_band_split: preserve isolate option The isolate option was not preserved by the initial implementation, presumably because for a band there is no way of knowing which position it has in the schedule tree, while the isolate option depends on this position. By passing in the schedule depth to the internal functions, these function are able to split the isolate option over the two bands. Signed-off-by: Sven Verdoolaege --- doc/user.pod | 2 ++ isl_schedule_band.c | 9 +++--- isl_schedule_node.c | 6 +++- isl_schedule_tree.c | 91 ++++++++++++++++++++++++++++++++++++++++++++++++++++- isl_schedule_tree.h | 2 +- 5 files changed, 103 insertions(+), 7 deletions(-) diff --git a/doc/user.pod b/doc/user.pod index b1a11d40..8021a547 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -8504,6 +8504,8 @@ using the following function. The resulting outer band node contains the first C dimensions of the schedule of C while the inner band contains the remaining dimensions. The schedules of the two band nodes live in anonymous spaces. +The loop AST generation type options and the isolate option +are split over the the two band nodes. A band node can be moved down to the leaves of the subtree rooted at the band node using the following function. diff --git a/isl_schedule_band.c b/isl_schedule_band.c index 71a6e15b..f0d91217 100644 --- a/isl_schedule_band.c +++ b/isl_schedule_band.c @@ -1168,8 +1168,7 @@ error: * We apply the transformation even if "n" is zero to ensure consistent * behavior with respect to changes in the schedule space. * - * The loop AST generation types for the isolated part become - * meaningless after dropping dimensions, so we remove them. + * The caller is responsible for updating the isolate option. */ __isl_give isl_schedule_band *isl_schedule_band_drop( __isl_take isl_schedule_band *band, int pos, int n) @@ -1195,8 +1194,10 @@ __isl_give isl_schedule_band *isl_schedule_band_drop( if (band->loop_type) for (i = pos + n; i < band->n; ++i) band->loop_type[i - n] = band->loop_type[i]; - free(band->isolate_loop_type); - band->isolate_loop_type = NULL; + if (band->isolate_loop_type) + for (i = pos + n; i < band->n; ++i) + band->isolate_loop_type[i - n] = + band->isolate_loop_type[i]; band->n -= n; diff --git a/isl_schedule_node.c b/isl_schedule_node.c index 1f894dff..a636d744 100644 --- a/isl_schedule_node.c +++ b/isl_schedule_node.c @@ -1959,14 +1959,18 @@ __isl_give isl_schedule_node *isl_schedule_node_band_sink( /* Split "node" into two nested band nodes, one with the first "pos" * dimensions and one with the remaining dimensions. * The schedules of the two band nodes live in anonymous spaces. + * The loop AST generation type options and the isolate option + * are split over the the two band nodes. */ __isl_give isl_schedule_node *isl_schedule_node_band_split( __isl_take isl_schedule_node *node, int pos) { + int depth; isl_schedule_tree *tree; + depth = isl_schedule_node_get_schedule_depth(node); tree = isl_schedule_node_get_tree(node); - tree = isl_schedule_tree_band_split(tree, pos); + tree = isl_schedule_tree_band_split(tree, pos, depth); return isl_schedule_node_graft_tree(node, tree); } diff --git a/isl_schedule_tree.c b/isl_schedule_tree.c index 612729c7..b764edd8 100644 --- a/isl_schedule_tree.c +++ b/isl_schedule_tree.c @@ -2180,14 +2180,95 @@ error: return NULL; } +/* Given an isolate AST generation option "isolate" for a band of size pos + n, + * return the corresponding option for a band covering the first "pos" + * members. + * + * The input isolate option is of the form + * + * isolate[[flattened outer bands] -> [pos; n]] + * + * The output isolate option is of the form + * + * isolate[[flattened outer bands] -> [pos]] + */ +static __isl_give isl_set *isolate_initial(__isl_keep isl_set *isolate, + int pos, int n) +{ + isl_id *id; + isl_map *map; + + isolate = isl_set_copy(isolate); + id = isl_set_get_tuple_id(isolate); + map = isl_set_unwrap(isolate); + map = isl_map_project_out(map, isl_dim_out, pos, n); + isolate = isl_map_wrap(map); + isolate = isl_set_set_tuple_id(isolate, id); + + return isolate; +} + +/* Given an isolate AST generation option "isolate" for a band of size pos + n, + * return the corresponding option for a band covering the final "n" + * members within a band covering the first "pos" members. + * + * The input isolate option is of the form + * + * isolate[[flattened outer bands] -> [pos; n]] + * + * The output isolate option is of the form + * + * isolate[[flattened outer bands; pos] -> [n]] + * + * + * The range is first split into + * + * isolate[[flattened outer bands] -> [[pos] -> [n]]] + * + * and then the first pos members are moved to the domain + * + * isolate[[[flattened outer bands] -> [pos]] -> [n]] + * + * after which the domain is flattened to obtain the desired output. + */ +static __isl_give isl_set *isolate_final(__isl_keep isl_set *isolate, + int pos, int n) +{ + isl_id *id; + isl_space *space; + isl_multi_aff *ma1, *ma2; + isl_map *map; + + isolate = isl_set_copy(isolate); + id = isl_set_get_tuple_id(isolate); + map = isl_set_unwrap(isolate); + space = isl_space_range(isl_map_get_space(map)); + ma1 = isl_multi_aff_project_out_map(isl_space_copy(space), + isl_dim_set, pos, n); + ma2 = isl_multi_aff_project_out_map(space, isl_dim_set, 0, pos); + ma1 = isl_multi_aff_range_product(ma1, ma2); + map = isl_map_apply_range(map, isl_map_from_multi_aff(ma1)); + map = isl_map_uncurry(map); + map = isl_map_flatten_domain(map); + isolate = isl_map_wrap(map); + isolate = isl_set_set_tuple_id(isolate, id); + + return isolate; +} + /* Split the band root node of "tree" into two nested band nodes, * one with the first "pos" dimensions and * one with the remaining dimensions. + * The tree is itself positioned at schedule depth "depth". + * + * The loop AST generation type options and the isolate option + * are split over the the two band nodes. */ __isl_give isl_schedule_tree *isl_schedule_tree_band_split( - __isl_take isl_schedule_tree *tree, int pos) + __isl_take isl_schedule_tree *tree, int pos, int depth) { int n; + isl_set *isolate, *tree_isolate, *child_isolate; isl_schedule_tree *child; if (!tree) @@ -2208,8 +2289,16 @@ __isl_give isl_schedule_tree *isl_schedule_tree_band_split( if (!tree || !child) goto error; + isolate = isl_schedule_tree_band_get_ast_isolate_option(tree, depth); + tree_isolate = isolate_initial(isolate, pos, n - pos); + child_isolate = isolate_final(isolate, pos, n - pos); child->band = isl_schedule_band_drop(child->band, 0, pos); + child->band = isl_schedule_band_replace_ast_build_option(child->band, + isl_set_copy(isolate), child_isolate); tree->band = isl_schedule_band_drop(tree->band, pos, n - pos); + tree->band = isl_schedule_band_replace_ast_build_option(tree->band, + isl_set_copy(isolate), tree_isolate); + isl_set_free(isolate); if (!child->band || !tree->band) goto error; diff --git a/isl_schedule_tree.h b/isl_schedule_tree.h index 2e1acdbe..9bb32c40 100644 --- a/isl_schedule_tree.h +++ b/isl_schedule_tree.h @@ -232,7 +232,7 @@ __isl_give isl_schedule_tree *isl_schedule_tree_band_shift( __isl_take isl_schedule_tree *tree, __isl_take isl_multi_union_pw_aff *shift); __isl_give isl_schedule_tree *isl_schedule_tree_band_split( - __isl_take isl_schedule_tree *tree, int pos); + __isl_take isl_schedule_tree *tree, int pos, int depth); __isl_give isl_schedule_tree *isl_schedule_tree_band_gist( __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *context); -- 2.11.4.GIT