529 lines · c
1/*2 * Copyright 2010-2011 INRIA Saclay3 * Copyright 2012-2013 Ecole Normale Superieure4 *5 * Use of this software is governed by the MIT license6 *7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,9 * 91893 Orsay, France10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France11 */12 13#include <isl/val.h>14#include <isl/space.h>15#include <isl_map_private.h>16#include <isl_aff_private.h>17#include <isl/constraint.h>18#include <isl/ilp.h>19#include <isl/fixed_box.h>20 21/* Representation of a box of fixed size containing the elements22 * [offset, offset + size).23 * "size" lives in the target space of "offset".24 *25 * If any of the "offsets" is NaN, then the object represents26 * the failure of finding a fixed-size box.27 */28struct isl_fixed_box {29 isl_multi_aff *offset;30 isl_multi_val *size;31};32 33/* Free "box" and return NULL.34 */35__isl_null isl_fixed_box *isl_fixed_box_free(__isl_take isl_fixed_box *box)36{37 if (!box)38 return NULL;39 isl_multi_aff_free(box->offset);40 isl_multi_val_free(box->size);41 free(box);42 return NULL;43}44 45/* Construct an isl_fixed_box with the given offset and size.46 */47static __isl_give isl_fixed_box *isl_fixed_box_alloc(48 __isl_take isl_multi_aff *offset, __isl_take isl_multi_val *size)49{50 isl_ctx *ctx;51 isl_fixed_box *box;52 53 if (!offset || !size)54 goto error;55 ctx = isl_multi_aff_get_ctx(offset);56 box = isl_alloc_type(ctx, struct isl_fixed_box);57 if (!box)58 goto error;59 box->offset = offset;60 box->size = size;61 62 return box;63error:64 isl_multi_aff_free(offset);65 isl_multi_val_free(size);66 return NULL;67}68 69/* Construct an initial isl_fixed_box with zero offsets70 * in the given space and zero corresponding sizes.71 */72static __isl_give isl_fixed_box *isl_fixed_box_init(73 __isl_take isl_space *space)74{75 isl_multi_aff *offset;76 isl_multi_val *size;77 78 offset = isl_multi_aff_zero(isl_space_copy(space));79 space = isl_space_drop_all_params(isl_space_range(space));80 size = isl_multi_val_zero(space);81 return isl_fixed_box_alloc(offset, size);82}83 84/* Return a copy of "box".85 */86__isl_give isl_fixed_box *isl_fixed_box_copy(__isl_keep isl_fixed_box *box)87{88 isl_multi_aff *offset;89 isl_multi_val *size;90 91 offset = isl_fixed_box_get_offset(box);92 size = isl_fixed_box_get_size(box);93 return isl_fixed_box_alloc(offset, size);94}95 96/* Replace the offset and size in direction "pos" by "offset" and "size"97 * (without checking whether "box" is a valid box).98 */99static __isl_give isl_fixed_box *isl_fixed_box_set_extent(100 __isl_take isl_fixed_box *box, int pos, __isl_keep isl_aff *offset,101 __isl_keep isl_val *size)102{103 if (!box)104 return NULL;105 box->offset = isl_multi_aff_set_aff(box->offset, pos,106 isl_aff_copy(offset));107 box->size = isl_multi_val_set_val(box->size, pos, isl_val_copy(size));108 if (!box->offset || !box->size)109 return isl_fixed_box_free(box);110 return box;111}112 113/* Replace the offset and size in direction "pos" by "offset" and "size",114 * if "box" is a valid box.115 */116static __isl_give isl_fixed_box *isl_fixed_box_set_valid_extent(117 __isl_take isl_fixed_box *box, int pos, __isl_keep isl_aff *offset,118 __isl_keep isl_val *size)119{120 isl_bool valid;121 122 valid = isl_fixed_box_is_valid(box);123 if (valid < 0 || !valid)124 return box;125 return isl_fixed_box_set_extent(box, pos, offset, size);126}127 128/* Replace "box" by an invalid box, by setting all offsets to NaN129 * (and all sizes to infinity).130 */131static __isl_give isl_fixed_box *isl_fixed_box_invalidate(132 __isl_take isl_fixed_box *box)133{134 int i;135 isl_size n;136 isl_space *space;137 isl_val *infty;138 isl_aff *nan;139 140 if (!box)141 return NULL;142 n = isl_multi_val_dim(box->size, isl_dim_set);143 if (n < 0)144 return isl_fixed_box_free(box);145 146 infty = isl_val_infty(isl_fixed_box_get_ctx(box));147 space = isl_space_domain(isl_fixed_box_get_space(box));148 nan = isl_aff_nan_on_domain(isl_local_space_from_space(space));149 for (i = 0; i < n; ++i)150 box = isl_fixed_box_set_extent(box, i, nan, infty);151 isl_aff_free(nan);152 isl_val_free(infty);153 154 if (!box->offset || !box->size)155 return isl_fixed_box_free(box);156 return box;157}158 159/* Project the domain of the fixed box onto its parameter space.160 * In particular, project out the domain of the offset.161 */162static __isl_give isl_fixed_box *isl_fixed_box_project_domain_on_params(163 __isl_take isl_fixed_box *box)164{165 isl_bool valid;166 167 valid = isl_fixed_box_is_valid(box);168 if (valid < 0)169 return isl_fixed_box_free(box);170 if (!valid)171 return box;172 173 box->offset = isl_multi_aff_project_domain_on_params(box->offset);174 if (!box->offset)175 return isl_fixed_box_free(box);176 177 return box;178}179 180/* Return the isl_ctx to which "box" belongs.181 */182isl_ctx *isl_fixed_box_get_ctx(__isl_keep isl_fixed_box *box)183{184 if (!box)185 return NULL;186 return isl_multi_aff_get_ctx(box->offset);187}188 189/* Return the space in which "box" lives.190 */191__isl_give isl_space *isl_fixed_box_get_space(__isl_keep isl_fixed_box *box)192{193 if (!box)194 return NULL;195 return isl_multi_aff_get_space(box->offset);196}197 198/* Does "box" contain valid information?199 */200isl_bool isl_fixed_box_is_valid(__isl_keep isl_fixed_box *box)201{202 if (!box)203 return isl_bool_error;204 return isl_bool_not(isl_multi_aff_involves_nan(box->offset));205}206 207/* Return the offsets of the box "box".208 */209__isl_give isl_multi_aff *isl_fixed_box_get_offset(210 __isl_keep isl_fixed_box *box)211{212 if (!box)213 return NULL;214 return isl_multi_aff_copy(box->offset);215}216 217/* Return the sizes of the box "box".218 */219__isl_give isl_multi_val *isl_fixed_box_get_size(__isl_keep isl_fixed_box *box)220{221 if (!box)222 return NULL;223 return isl_multi_val_copy(box->size);224}225 226/* Data used in set_dim_extent and compute_size_in_direction.227 *228 * "bset" is a wrapped copy of the basic map that has the selected229 * output dimension as range.230 * "pos" is the position of the variable representing the output dimension,231 * i.e., the variable for which the size should be computed. This variable232 * is also the last variable in "bset".233 * "size" is the best size found so far234 * (infinity if no offset was found so far).235 * "offset" is the offset corresponding to the best size236 * (NULL if no offset was found so far).237 */238struct isl_size_info {239 isl_basic_set *bset;240 isl_size pos;241 isl_val *size;242 isl_aff *offset;243};244 245/* Is "c" a suitable bound on dimension "pos" for use as a lower bound246 * of a fixed-size range.247 * In particular, it needs to be a lower bound on "pos".248 * In order for the final offset not to be too complicated,249 * the constraint itself should also not involve any integer divisions.250 */251static isl_bool is_suitable_bound(__isl_keep isl_constraint *c, unsigned pos)252{253 isl_size n_div;254 isl_bool is_bound, any_divs;255 256 is_bound = isl_constraint_is_lower_bound(c, isl_dim_set, pos);257 if (is_bound < 0 || !is_bound)258 return is_bound;259 260 n_div = isl_constraint_dim(c, isl_dim_div);261 if (n_div < 0)262 return isl_bool_error;263 any_divs = isl_constraint_involves_dims(c, isl_dim_div, 0, n_div);264 return isl_bool_not(any_divs);265}266 267/* Given a constraint from the basic set describing the bounds on268 * an array index, check if it is a lower bound, say m i >= b(x), and,269 * if so, check whether the expression "i - ceil(b(x)/m) + 1" has a constant270 * upper bound. If so, and if this bound is smaller than any bound271 * derived from earlier constraints, set the size to this bound on272 * the expression and the lower bound to ceil(b(x)/m).273 */274static isl_stat compute_size_in_direction(__isl_take isl_constraint *c,275 void *user)276{277 struct isl_size_info *info = user;278 isl_val *v;279 isl_aff *aff;280 isl_aff *lb;281 isl_bool is_bound, better;282 283 is_bound = is_suitable_bound(c, info->pos);284 if (is_bound < 0 || !is_bound) {285 isl_constraint_free(c);286 return is_bound < 0 ? isl_stat_error : isl_stat_ok;287 }288 289 aff = isl_constraint_get_bound(c, isl_dim_set, info->pos);290 aff = isl_aff_ceil(aff);291 292 lb = isl_aff_copy(aff);293 294 aff = isl_aff_neg(aff);295 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, info->pos, 1);296 297 v = isl_basic_set_max_val(info->bset, aff);298 isl_aff_free(aff);299 300 v = isl_val_add_ui(v, 1);301 better = isl_val_lt(v, info->size);302 if (better >= 0 && better) {303 isl_val_free(info->size);304 info->size = isl_val_copy(v);305 lb = isl_aff_domain_factor_domain(lb);306 isl_aff_free(info->offset);307 info->offset = isl_aff_copy(lb);308 }309 isl_val_free(v);310 isl_aff_free(lb);311 312 isl_constraint_free(c);313 314 return better < 0 ? isl_stat_error : isl_stat_ok;315}316 317/* Look for a fixed-size range of values for the output dimension "pos"318 * of "map", by looking for a lower-bound expression in the parameters319 * and input dimensions such that the range of the output dimension320 * is a constant shifted by this expression.321 *322 * In particular, look through the explicit lower bounds on the output dimension323 * for candidate expressions and pick the one that results in the smallest size.324 * Initialize the size with infinity and if no better size is found325 * then invalidate the box. Otherwise, set the offset and size326 * in the given direction by those that correspond to the smallest size.327 *328 * Note that while evaluating the size corresponding to a lower bound,329 * an affine expression is constructed from the lower bound.330 * This lower bound may therefore not have any unknown local variables.331 * Eliminate any unknown local variables up front.332 * No such restriction needs to be imposed on the set over which333 * the size is computed.334 */335static __isl_give isl_fixed_box *set_dim_extent(__isl_take isl_fixed_box *box,336 __isl_keep isl_map *map, int pos)337{338 struct isl_size_info info;339 isl_bool valid;340 isl_ctx *ctx;341 isl_basic_set *bset;342 343 if (!box || !map)344 return isl_fixed_box_free(box);345 346 ctx = isl_map_get_ctx(map);347 map = isl_map_copy(map);348 map = isl_map_project_onto(map, isl_dim_out, pos, 1);349 info.size = isl_val_infty(ctx);350 info.offset = NULL;351 info.pos = isl_map_dim(map, isl_dim_in);352 info.bset = isl_basic_map_wrap(isl_map_simple_hull(map));353 bset = isl_basic_set_copy(info.bset);354 bset = isl_basic_set_remove_unknown_divs(bset);355 if (info.pos < 0)356 bset = isl_basic_set_free(bset);357 if (isl_basic_set_foreach_constraint(bset,358 &compute_size_in_direction, &info) < 0)359 box = isl_fixed_box_free(box);360 isl_basic_set_free(bset);361 valid = isl_val_is_int(info.size);362 if (valid < 0)363 box = isl_fixed_box_free(box);364 else if (valid)365 box = isl_fixed_box_set_valid_extent(box, pos,366 info.offset, info.size);367 else368 box = isl_fixed_box_invalidate(box);369 isl_val_free(info.size);370 isl_aff_free(info.offset);371 isl_basic_set_free(info.bset);372 373 return box;374}375 376/* Try and construct a fixed-size rectangular box with an offset377 * in terms of the domain of "map" that contains the range of "map".378 * If no such box can be constructed, then return an invalidated box,379 * i.e., one where isl_fixed_box_is_valid returns false.380 *381 * Iterate over the dimensions in the range382 * setting the corresponding offset and extent.383 */384__isl_give isl_fixed_box *isl_map_get_range_simple_fixed_box_hull(385 __isl_keep isl_map *map)386{387 int i;388 isl_size n;389 isl_space *space;390 isl_fixed_box *box;391 392 n = isl_map_dim(map, isl_dim_out);393 if (n < 0)394 return NULL;395 space = isl_map_get_space(map);396 box = isl_fixed_box_init(space);397 398 map = isl_map_detect_equalities(isl_map_copy(map));399 for (i = 0; i < n; ++i) {400 isl_bool valid;401 402 box = set_dim_extent(box, map, i);403 valid = isl_fixed_box_is_valid(box);404 if (valid < 0 || !valid)405 break;406 }407 isl_map_free(map);408 409 return box;410}411 412/* Compute a fixed box from "set" using "map_box" by treating it as a map413 * with a zero-dimensional domain and414 * project out the domain again from the result.415 */416static __isl_give isl_fixed_box *fixed_box_as_map(__isl_keep isl_set *set,417 __isl_give isl_fixed_box *(*map_box)(__isl_keep isl_map *map))418{419 isl_map *map;420 isl_fixed_box *box;421 422 map = isl_map_from_range(isl_set_copy(set));423 box = map_box(map);424 isl_map_free(map);425 box = isl_fixed_box_project_domain_on_params(box);426 427 return box;428}429 430/* Try and construct a fixed-size rectangular box with an offset431 * in terms of the parameters of "set" that contains "set".432 * If no such box can be constructed, then return an invalidated box,433 * i.e., one where isl_fixed_box_is_valid returns false.434 *435 * Compute the box using isl_map_get_range_simple_fixed_box_hull436 * by constructing a map from the set and437 * project out the domain again from the result.438 */439__isl_give isl_fixed_box *isl_set_get_simple_fixed_box_hull(440 __isl_keep isl_set *set)441{442 return fixed_box_as_map(set, &isl_map_get_range_simple_fixed_box_hull);443}444 445/* Check whether the output elements lie on a rectangular lattice,446 * possibly depending on the parameters and the input dimensions.447 * Return a tile in this lattice.448 * If no stride information can be found, then return a tile of size 1449 * (and offset 0).450 *451 * Obtain stride information in each output dimension separately and452 * combine the results.453 */454__isl_give isl_fixed_box *isl_map_get_range_lattice_tile(455 __isl_keep isl_map *map)456{457 int i;458 isl_size n;459 isl_space *space;460 isl_fixed_box *box;461 462 n = isl_map_dim(map, isl_dim_out);463 if (n < 0)464 return NULL;465 space = isl_map_get_space(map);466 box = isl_fixed_box_init(space);467 468 for (i = 0; i < n; ++i) {469 isl_val *stride;470 isl_aff *offset;471 isl_stride_info *si;472 473 si = isl_map_get_range_stride_info(map, i);474 stride = isl_stride_info_get_stride(si);475 offset = isl_stride_info_get_offset(si);476 isl_stride_info_free(si);477 478 box = isl_fixed_box_set_valid_extent(box, i, offset, stride);479 480 isl_aff_free(offset);481 isl_val_free(stride);482 }483 484 return box;485}486 487/* Check whether the elements lie on a rectangular lattice,488 * possibly depending on the parameters.489 * Return a tile in this lattice.490 * If no stride information can be found, then return a tile of size 1491 * (and offset 0).492 *493 * Consider the set as a map with a zero-dimensional domain and494 * obtain a lattice tile of that map.495 */496__isl_give isl_fixed_box *isl_set_get_lattice_tile(__isl_keep isl_set *set)497{498 return fixed_box_as_map(set, &isl_map_get_range_lattice_tile);499}500 501#undef BASE502#define BASE multi_val503#include "print_yaml_field_templ.c"504 505#undef BASE506#define BASE multi_aff507#include "print_yaml_field_templ.c"508 509/* Print the information contained in "box" to "p".510 * The information is printed as a YAML document.511 */512__isl_give isl_printer *isl_printer_print_fixed_box(513 __isl_take isl_printer *p, __isl_keep isl_fixed_box *box)514{515 if (!box)516 return isl_printer_free(p);517 518 p = isl_printer_yaml_start_mapping(p);519 p = print_yaml_field_multi_aff(p, "offset", box->offset);520 p = print_yaml_field_multi_val(p, "size", box->size);521 p = isl_printer_yaml_end_mapping(p);522 523 return p;524}525 526#undef BASE527#define BASE fixed_box528#include <print_templ_yaml.c>529