| /* |
| * 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 <isl/val.h> |
| #include <isl/space.h> |
| #include <isl_map_private.h> |
| #include <isl_aff_private.h> |
| #include <isl/constraint.h> |
| #include <isl/ilp.h> |
| #include <isl/fixed_box.h> |
| |
| /* 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; |
| } |