From b0a600c3dbb267704fd3799ca50077d6471d2444 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Tue, 20 Mar 2012 17:55:52 +0100 Subject: [PATCH] add isl_band_tile Signed-off-by: Sven Verdoolaege --- doc/user.pod | 17 ++++++ include/isl/band.h | 6 ++ isl_band.c | 159 ++++++++++++++++++++++++++++++++++++++++++++++++++ isl_options.c | 7 +++ isl_options_private.h | 3 + 5 files changed, 192 insertions(+) diff --git a/doc/user.pod b/doc/user.pod index 2f9e387..83d0a4f 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -4464,6 +4464,23 @@ That is, if the dependence distances of the proximity dependences are all zero in that direction (for fixed iterations of outer bands). +A band can be tiled using the following function. + + #include + int isl_band_tile(__isl_keep isl_band *band, + __isl_take isl_vec *sizes); + + int isl_options_set_tile_scale_tile_loops(isl_ctx *ctx, + int val); + int isl_options_get_tile_scale_tile_loops(isl_ctx *ctx); + +The C function tiles the band using the given tile sizes +inside its schedule. +A new child band is created to represent the point loops and it is +inserted between the modified band and its children. +The C option specifies whether the tile +loops iterators should be scaled by the tile sizes. + A representation of the band can be printed using #include diff --git a/include/isl/band.h b/include/isl/band.h index f5c31cf..7dbb62a 100644 --- a/include/isl/band.h +++ b/include/isl/band.h @@ -4,6 +4,7 @@ #include #include #include +#include #if defined(__cplusplus) extern "C" { @@ -28,6 +29,11 @@ __isl_give isl_union_map *isl_band_get_partial_schedule( __isl_give isl_union_map *isl_band_get_suffix_schedule( __isl_keep isl_band *band); +int isl_options_set_tile_scale_tile_loops(isl_ctx *ctx, int val); +int isl_options_get_tile_scale_tile_loops(isl_ctx *ctx); + +int isl_band_tile(__isl_keep isl_band *band, __isl_take isl_vec *sizes); + int isl_band_n_member(__isl_keep isl_band *band); int isl_band_member_is_zero_distance(__isl_keep isl_band *band, int pos); diff --git a/isl_band.c b/isl_band.c index 7d05cd6..e381c60 100644 --- a/isl_band.c +++ b/isl_band.c @@ -284,6 +284,165 @@ __isl_give isl_union_map *isl_band_get_suffix_schedule( return isl_union_map_from_union_pw_multi_aff(suffix); } +/* Internal data used during the construction of the schedule + * for the tile loops. + * + * sizes contains the tile sizes + * scale is set if the tile loops should be scaled + * tiled collects the result for a single statement + * res collects the result for all statements + */ +struct isl_band_tile_data { + isl_vec *sizes; + isl_union_pw_multi_aff *res; + isl_pw_multi_aff *tiled; + int scale; +}; + +/* Given part of the schedule of a band, construct the corresponding + * schedule for the tile loops based on the tile sizes in data->sizes + * and add the result to data->tiled. + * + * If data->scale is set, then dimension i of the schedule will be + * of the form + * + * m_i * floor(s_i(x) / m_i) + * + * where s_i(x) refers to the original schedule and m_i is the tile size. + * If data->scale is not set, then dimension i of the schedule will be + * of the form + * + * floor(s_i(x) / m_i) + * + */ +static int multi_aff_tile(__isl_take isl_set *set, + __isl_take isl_multi_aff *ma, void *user) +{ + struct isl_band_tile_data *data = user; + isl_pw_multi_aff *pma; + int i, n; + isl_int v; + + n = isl_multi_aff_dim(ma, isl_dim_out); + if (isl_vec_size(data->sizes) < n) + n = isl_vec_size(data->sizes); + + isl_int_init(v); + for (i = 0; i < n; ++i) { + isl_aff *aff; + + aff = isl_multi_aff_get_aff(ma, i); + isl_vec_get_element(data->sizes, i, &v); + + aff = isl_aff_scale_down(aff, v); + aff = isl_aff_floor(aff); + if (data->scale) + aff = isl_aff_scale(aff, v); + + ma = isl_multi_aff_set_aff(ma, i, aff); + } + isl_int_clear(v); + + pma = isl_pw_multi_aff_alloc(set, ma); + data->tiled = isl_pw_multi_aff_union_add(data->tiled, pma); + + return 0; +} + +/* Given part of the schedule of a band, construct the corresponding + * schedule for the tile loops based on the tile sizes in data->sizes + * and add the result to data->res. + */ +static int pw_multi_aff_tile(__isl_take isl_pw_multi_aff *pma, void *user) +{ + struct isl_band_tile_data *data = user; + + data->tiled = isl_pw_multi_aff_empty(isl_pw_multi_aff_get_space(pma)); + + if (isl_pw_multi_aff_foreach_piece(pma, &multi_aff_tile, data) < 0) + goto error; + + isl_pw_multi_aff_free(pma); + data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, + data->tiled); + + return 0; +error: + isl_pw_multi_aff_free(pma); + isl_pw_multi_aff_free(data->tiled); + return -1; +} + +/* Given the schedule of a band, construct the corresponding + * schedule for the tile loops based on the given tile sizes + * and return the result. + */ +static isl_union_pw_multi_aff *isl_union_pw_multi_aff_tile( + __isl_take isl_union_pw_multi_aff *sched, __isl_keep isl_vec *sizes) +{ + isl_ctx *ctx; + isl_space *space; + struct isl_band_tile_data data = { sizes }; + + ctx = isl_vec_get_ctx(sizes); + + space = isl_union_pw_multi_aff_get_space(sched); + data.res = isl_union_pw_multi_aff_empty(space); + data.scale = isl_options_get_tile_scale_tile_loops(ctx); + + if (isl_union_pw_multi_aff_foreach_pw_multi_aff(sched, + &pw_multi_aff_tile, &data) < 0) + goto error; + + isl_union_pw_multi_aff_free(sched); + return data.res; +error: + isl_union_pw_multi_aff_free(sched); + isl_union_pw_multi_aff_free(data.res); + return NULL; +} + +/* Tile the given band using the specified tile sizes. + * The given band is modified to refer to the tile loops and + * a child band is created to refer to the point loops. + * The children of this point loop band are the children + * of the original band. + */ +int isl_band_tile(__isl_keep isl_band *band, __isl_take isl_vec *sizes) +{ + isl_ctx *ctx; + isl_band *child; + isl_band_list *list = NULL; + isl_union_pw_multi_aff *sched; + + if (!band || !sizes) + goto error; + + ctx = isl_vec_get_ctx(sizes); + child = isl_band_dup(band); + list = isl_band_list_alloc(ctx, 1); + list = isl_band_list_add(list, child); + if (!list) + goto error; + + sched = isl_union_pw_multi_aff_copy(band->pma); + sched = isl_union_pw_multi_aff_tile(sched, sizes); + if (!sched) + goto error; + + child->children = band->children; + band->children = list; + isl_union_pw_multi_aff_free(band->pma); + band->pma = sched; + + isl_vec_free(sizes); + return 0; +error: + isl_band_list_free(list); + isl_vec_free(sizes); + return -1; +} + __isl_give isl_printer *isl_printer_print_band(__isl_take isl_printer *p, __isl_keep isl_band *band) { diff --git a/isl_options.c b/isl_options.c index 8f7ccd0..f214ce3 100644 --- a/isl_options.c +++ b/isl_options.c @@ -167,6 +167,8 @@ ISL_ARG_CHOICE(struct isl_options, schedule_algorithm, 0, ISL_SCHEDULE_ALGORITHM_ISL, "scheduling algorithm to use") ISL_ARG_CHOICE(struct isl_options, schedule_fuse, 0, "schedule-fuse", fuse, ISL_SCHEDULE_FUSE_MAX, "level of fusion during scheduling") +ISL_ARG_BOOL(struct isl_options, tile_scale_tile_loops, 0, + "tile-scale-tile-loops", 1, "scale tile loops") ISL_ARG_VERSION(print_version) ISL_ARGS_END @@ -231,3 +233,8 @@ ISL_CTX_SET_CHOICE_DEF(isl_options, struct isl_options, isl_options_args, schedule_fuse) ISL_CTX_GET_CHOICE_DEF(isl_options, struct isl_options, isl_options_args, schedule_fuse) + +ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, + tile_scale_tile_loops) +ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, + tile_scale_tile_loops) diff --git a/isl_options_private.h b/isl_options_private.h index 80c9aa5..93563ec 100644 --- a/isl_options_private.h +++ b/isl_options_private.h @@ -56,6 +56,9 @@ struct isl_options { int schedule_separate_components; unsigned schedule_algorithm; int schedule_fuse; + + int tile_scale_tile_loops; + }; #endif -- 2.7.4