From ad05b8d23ba51ad9c4135548368382c4cc4eb5f8 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Tue, 15 May 2018 15:06:05 +0200 Subject: [PATCH] add isl_map_get_range_simple_fixed_box_hull This code is essentially copied from PPCG. It computes an overapproximation of the range of a map in the form of a fixed-size rectangular box. It may be a bit PPCG specific, but there is at least one other potential user (which is arguably closely related to PPCG). The exact position and size of the box may depend on the internal representation of the map and is therefore not defined exactly. This is similar to some of the other hull operations. Reviewed-by: Oleksandr Zinenko Signed-off-by: Sven Verdoolaege --- Makefile.am | 2 + doc/user.pod | 44 ++++++ include/isl/fixed_box.h | 34 +++++ include/isl/map.h | 3 + isl_box.c | 368 ++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 451 insertions(+) create mode 100644 include/isl/fixed_box.h create mode 100644 isl_box.c diff --git a/Makefile.am b/Makefile.am index 9b73a167..7c337662 100644 --- a/Makefile.am +++ b/Makefile.am @@ -84,6 +84,7 @@ libisl_la_SOURCES = \ isl_blk.h \ isl_bound.c \ isl_bound.h \ + isl_box.c \ isl_coalesce.c \ isl_constraint.c \ isl_constraint_private.h \ @@ -274,6 +275,7 @@ pkginclude_HEADERS = \ include/isl/ast_build.h \ include/isl/constraint.h \ include/isl/ctx.h \ + include/isl/fixed_box.h \ include/isl/flow.h \ include/isl/id.h \ include/isl/id_type.h \ diff --git a/doc/user.pod b/doc/user.pod index 04e8cede..ddd0e2b6 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -611,6 +611,10 @@ in which the object was created. isl_ctx *isl_stride_info_get_ctx( __isl_keep isl_stride_info *si); + #include + isl_ctx *isl_fixed_box_get_ctx( + __isl_keep isl_fixed_box *box); + =head2 Return Types C uses two special return types for functions that either return @@ -1116,6 +1120,10 @@ of the original object. __isl_give isl_space *isl_point_get_space( __isl_keep isl_point *pnt); + #include + __isl_give isl_space *isl_fixed_box_get_space( + __isl_keep isl_fixed_box *box); + The number of dimensions of a given type of space may be read off from a space or an object that lives in a space using the following functions. @@ -5227,6 +5235,42 @@ that contains the whole input set or relation. In case of union sets and relations, the polyhedral hull is computed per space. +=item * Box hull + + #include + __isl_give isl_fixed_box * + isl_map_get_range_simple_fixed_box_hull( + __isl_keep isl_map *map); + +This function tries to approximate the range of the map by a box of fixed size. +The box is described in terms of an offset living in the same space as +the input map and a size living in the range space. For any element +in the input map, the range value is greater than or equal to +the offset applied to the domain value and the difference with +this offset is strictly smaller than the size. +If no fixed-size approximation of the range can be found, +an I box is returned, i.e., one for which +C below returns false. + +The validity, the offset and the size of the box can be obtained using +the following functions. + + #include + isl_bool isl_fixed_box_is_valid( + __isl_keep isl_fixed_box *box); + __isl_give isl_multi_aff *isl_fixed_box_get_offset( + __isl_keep isl_fixed_box *box); + __isl_give isl_multi_val *isl_fixed_box_get_size( + __isl_keep isl_fixed_box *box); + +The box can be copied and freed using the following functions. + + #include + __isl_give isl_fixed_box *isl_fixed_box_copy( + __isl_keep isl_fixed_box *box); + __isl_null isl_fixed_box *isl_fixed_box_free( + __isl_take isl_fixed_box *box); + =item * Other approximations #include diff --git a/include/isl/fixed_box.h b/include/isl/fixed_box.h new file mode 100644 index 00000000..5a40a6f0 --- /dev/null +++ b/include/isl/fixed_box.h @@ -0,0 +1,34 @@ +/* + * Use of this software is governed by the MIT license + */ + +#ifndef ISL_FIXED_BOX_H +#define ISL_FIXED_BOX_H + +#include +#include +#include +#include + +#if defined(__cplusplus) +extern "C" { +#endif + +struct isl_fixed_box; +typedef struct isl_fixed_box isl_fixed_box; + +isl_ctx *isl_fixed_box_get_ctx(__isl_keep isl_fixed_box *box); +__isl_give isl_space *isl_fixed_box_get_space(__isl_keep isl_fixed_box *box); +isl_bool isl_fixed_box_is_valid(__isl_keep isl_fixed_box *box); +__isl_give isl_multi_aff *isl_fixed_box_get_offset( + __isl_keep isl_fixed_box *box); +__isl_give isl_multi_val *isl_fixed_box_get_size(__isl_keep isl_fixed_box *box); + +__isl_give isl_fixed_box *isl_fixed_box_copy(__isl_keep isl_fixed_box *box); +__isl_null isl_fixed_box *isl_fixed_box_free(__isl_take isl_fixed_box *box); + +#if defined(__cplusplus) +} +#endif + +#endif diff --git a/include/isl/map.h b/include/isl/map.h index 6728e3f5..8b05ba9d 100644 --- a/include/isl/map.h +++ b/include/isl/map.h @@ -24,6 +24,7 @@ #include #include #include +#include #if defined(__cplusplus) extern "C" { @@ -607,6 +608,8 @@ __isl_give isl_map *isl_map_gist_basic_map(__isl_take isl_map *map, __isl_give isl_stride_info *isl_map_get_range_stride_info( __isl_keep isl_map *map, int pos); +__isl_give isl_fixed_box *isl_map_get_range_simple_fixed_box_hull( + __isl_keep isl_map *map); __isl_export __isl_give isl_map *isl_map_coalesce(__isl_take isl_map *map); diff --git a/isl_box.c b/isl_box.c new file mode 100644 index 00000000..b90ef869 --- /dev/null +++ b/isl_box.c @@ -0,0 +1,368 @@ +/* + * Copyright 2010-2011 INRIA Saclay + * Copyright 2012-2013 Ecole Normale Superieure + * + * Use of this software is governed by the MIT license + * + * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, + * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, + * 91893 Orsay, France + * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France + */ + +#include +#include +#include +#include +#include +#include +#include + +/* Representation of a box of fixed size containing the elements + * [offset, offset + size). + * "size" lives in the target space of "offset". + * + * If any of the "offsets" is NaN, then the object represents + * the failure of finding a fixed-size box. + */ +struct isl_fixed_box { + isl_multi_aff *offset; + isl_multi_val *size; +}; + +/* Free "box" and return NULL. + */ +__isl_null isl_fixed_box *isl_fixed_box_free(__isl_take isl_fixed_box *box) +{ + if (!box) + return NULL; + isl_multi_aff_free(box->offset); + isl_multi_val_free(box->size); + free(box); + return NULL; +} + +/* Construct an isl_fixed_box with the given offset and size. + */ +static __isl_give isl_fixed_box *isl_fixed_box_alloc( + __isl_take isl_multi_aff *offset, __isl_take isl_multi_val *size) +{ + isl_ctx *ctx; + isl_fixed_box *box; + + if (!offset || !size) + goto error; + ctx = isl_multi_aff_get_ctx(offset); + box = isl_alloc_type(ctx, struct isl_fixed_box); + if (!box) + goto error; + box->offset = offset; + box->size = size; + + return box; +error: + isl_multi_aff_free(offset); + isl_multi_val_free(size); + return NULL; +} + +/* Construct an initial isl_fixed_box with zero offsets + * in the given space and zero corresponding sizes. + */ +static __isl_give isl_fixed_box *isl_fixed_box_init( + __isl_take isl_space *space) +{ + isl_multi_aff *offset; + isl_multi_val *size; + + offset = isl_multi_aff_zero(isl_space_copy(space)); + size = isl_multi_val_zero(isl_space_range(space)); + return isl_fixed_box_alloc(offset, size); +} + +/* Return a copy of "box". + */ +__isl_give isl_fixed_box *isl_fixed_box_copy(__isl_keep isl_fixed_box *box) +{ + isl_multi_aff *offset; + isl_multi_val *size; + + offset = isl_fixed_box_get_offset(box); + size = isl_fixed_box_get_size(box); + return isl_fixed_box_alloc(offset, size); +} + +/* Replace the offset and size in direction "pos" by "offset" and "size" + * (without checking whether "box" is a valid box). + */ +static __isl_give isl_fixed_box *isl_fixed_box_set_extent( + __isl_take isl_fixed_box *box, int pos, __isl_keep isl_aff *offset, + __isl_keep isl_val *size) +{ + if (!box) + return NULL; + box->offset = isl_multi_aff_set_aff(box->offset, pos, + isl_aff_copy(offset)); + box->size = isl_multi_val_set_val(box->size, pos, isl_val_copy(size)); + if (!box->offset || !box->size) + return isl_fixed_box_free(box); + return box; +} + +/* Replace the offset and size in direction "pos" by "offset" and "size", + * if "box" is a valid box. + */ +static __isl_give isl_fixed_box *isl_fixed_box_set_valid_extent( + __isl_take isl_fixed_box *box, int pos, __isl_keep isl_aff *offset, + __isl_keep isl_val *size) +{ + isl_bool valid; + + valid = isl_fixed_box_is_valid(box); + if (valid < 0 || !valid) + return box; + return isl_fixed_box_set_extent(box, pos, offset, size); +} + +/* Replace "box" by an invalid box, by setting all offsets to NaN + * (and all sizes to infinity). + */ +static __isl_give isl_fixed_box *isl_fixed_box_invalidate( + __isl_take isl_fixed_box *box) +{ + int i, n; + isl_space *space; + isl_val *infty; + isl_aff *nan; + + if (!box) + return NULL; + n = isl_multi_val_dim(box->size, isl_dim_set); + + infty = isl_val_infty(isl_fixed_box_get_ctx(box)); + space = isl_space_domain(isl_fixed_box_get_space(box)); + nan = isl_aff_nan_on_domain(isl_local_space_from_space(space)); + for (i = 0; i < n; ++i) + box = isl_fixed_box_set_extent(box, i, nan, infty); + isl_aff_free(nan); + isl_val_free(infty); + + if (!box->offset || !box->size) + return isl_fixed_box_free(box); + return box; +} + +/* Return the isl_ctx to which "box" belongs. + */ +isl_ctx *isl_fixed_box_get_ctx(__isl_keep isl_fixed_box *box) +{ + if (!box) + return NULL; + return isl_multi_aff_get_ctx(box->offset); +} + +/* Return the space in which "box" lives. + */ +__isl_give isl_space *isl_fixed_box_get_space(__isl_keep isl_fixed_box *box) +{ + if (!box) + return NULL; + return isl_multi_aff_get_space(box->offset); +} + +/* Does "box" contain valid information? + */ +isl_bool isl_fixed_box_is_valid(__isl_keep isl_fixed_box *box) +{ + if (!box) + return isl_bool_error; + return isl_bool_not(isl_multi_aff_involves_nan(box->offset)); +} + +/* Return the offsets of the box "box". + */ +__isl_give isl_multi_aff *isl_fixed_box_get_offset( + __isl_keep isl_fixed_box *box) +{ + if (!box) + return NULL; + return isl_multi_aff_copy(box->offset); +} + +/* Return the sizes of the box "box". + */ +__isl_give isl_multi_val *isl_fixed_box_get_size(__isl_keep isl_fixed_box *box) +{ + if (!box) + return NULL; + return isl_multi_val_copy(box->size); +} + +/* Data used in set_dim_extent and compute_size_in_direction. + * + * "bset" is a wrapped copy of the basic map that has the selected + * output dimension as range. + * "pos" is the position of the variable representing the output dimension, + * i.e., the variable for which the size should be computed. This variable + * is also the last variable in "bset". + * "size" is the best size found so far + * (infinity if no offset was found so far). + * "offset" is the offset corresponding to the best size + * (NULL if no offset was found so far). + */ +struct isl_size_info { + isl_basic_set *bset; + int pos; + isl_val *size; + isl_aff *offset; +}; + +/* Is "c" a suitable bound on dimension "pos" for use as a lower bound + * of a fixed-size range. + * In particular, it needs to be a lower bound on "pos". + * In order for the final offset not to be too complicated, + * the constraint itself should also not involve any integer divisions. + */ +static isl_bool is_suitable_bound(__isl_keep isl_constraint *c, unsigned pos) +{ + unsigned n_div; + isl_bool is_bound, any_divs; + + is_bound = isl_constraint_is_lower_bound(c, isl_dim_set, pos); + if (is_bound < 0 || !is_bound) + return is_bound; + + n_div = isl_constraint_dim(c, isl_dim_div); + any_divs = isl_constraint_involves_dims(c, isl_dim_div, 0, n_div); + return isl_bool_not(any_divs); +} + +/* Given a constraint from the basic set describing the bounds on + * an array index, check if it is a lower bound, say m i >= b(x), and, + * if so, check whether the expression "i - ceil(b(x)/m) + 1" has a constant + * upper bound. If so, and if this bound is smaller than any bound + * derived from earlier constraints, set the size to this bound on + * the expression and the lower bound to ceil(b(x)/m). + */ +static isl_stat compute_size_in_direction(__isl_take isl_constraint *c, + void *user) +{ + struct isl_size_info *info = user; + isl_val *v; + isl_aff *aff; + isl_aff *lb; + isl_bool is_bound, better; + + is_bound = is_suitable_bound(c, info->pos); + if (is_bound < 0 || !is_bound) { + isl_constraint_free(c); + return is_bound < 0 ? isl_stat_error : isl_stat_ok; + } + + aff = isl_constraint_get_bound(c, isl_dim_set, info->pos); + aff = isl_aff_ceil(aff); + + lb = isl_aff_copy(aff); + + aff = isl_aff_neg(aff); + aff = isl_aff_add_coefficient_si(aff, isl_dim_in, info->pos, 1); + + v = isl_basic_set_max_val(info->bset, aff); + isl_aff_free(aff); + + v = isl_val_add_ui(v, 1); + better = isl_val_lt(v, info->size); + if (better >= 0 && better) { + isl_val_free(info->size); + info->size = isl_val_copy(v); + lb = isl_aff_domain_factor_domain(lb); + isl_aff_free(info->offset); + info->offset = isl_aff_copy(lb); + } + isl_val_free(v); + isl_aff_free(lb); + + isl_constraint_free(c); + + return better < 0 ? isl_stat_error : isl_stat_ok; +} + +/* Look for a fixed-size range of values for the output dimension "pos" + * of "map", by looking for a lower-bound expression in the parameters + * and input dimensions such that the range of the output dimension + * is a constant shifted by this expression. + * + * In particular, look through the explicit lower bounds on the output dimension + * for candidate expressions and pick the one that results in the smallest size. + * Initialize the size with infinity and if no better size is found + * then invalidate the box. Otherwise, set the offset and size + * in the given direction by those that correspond to the smallest size. + */ +static __isl_give isl_fixed_box *set_dim_extent(__isl_take isl_fixed_box *box, + __isl_keep isl_map *map, int pos) +{ + struct isl_size_info info; + isl_bool valid; + isl_ctx *ctx; + + if (!box || !map) + return isl_fixed_box_free(box); + + ctx = isl_map_get_ctx(map); + map = isl_map_copy(map); + map = isl_map_project_onto(map, isl_dim_out, pos, 1); + map = isl_map_compute_divs(map); + info.size = isl_val_infty(ctx); + info.offset = NULL; + info.pos = isl_map_dim(map, isl_dim_in); + info.bset = isl_basic_map_wrap(isl_map_simple_hull(map)); + if (isl_basic_set_foreach_constraint(info.bset, + &compute_size_in_direction, &info) < 0) + box = isl_fixed_box_free(box); + valid = isl_val_is_int(info.size); + if (valid < 0) + box = isl_fixed_box_free(box); + else if (valid) + box = isl_fixed_box_set_valid_extent(box, pos, + info.offset, info.size); + else + box = isl_fixed_box_invalidate(box); + isl_val_free(info.size); + isl_aff_free(info.offset); + isl_basic_set_free(info.bset); + + return box; +} + +/* Try and construct a fixed-size rectangular box with an offset + * in terms of the domain of "map" that contains the range of "map". + * If no such box can be constructed, then return an invalidated box, + * i.e., one where isl_fixed_box_is_valid returns false. + * + * Iterate over the dimensions in the range + * setting the corresponding offset and extent. + */ +__isl_give isl_fixed_box *isl_map_get_range_simple_fixed_box_hull( + __isl_keep isl_map *map) +{ + int i, n; + isl_space *space; + isl_fixed_box *box; + + n = isl_map_dim(map, isl_dim_out); + space = isl_map_get_space(map); + box = isl_fixed_box_init(space); + + map = isl_map_detect_equalities(isl_map_copy(map)); + for (i = 0; i < n; ++i) { + isl_bool valid; + + box = set_dim_extent(box, map, i); + valid = isl_fixed_box_is_valid(box); + if (valid < 0 || !valid) + break; + } + isl_map_free(map); + + return box; +} -- 2.11.4.GIT