isl_box.c

   1 /*
   2  * Copyright 2010-2011 INRIA Saclay
   3  * Copyright 2012-2013 Ecole Normale Superieure
   4  *
   5  * Use of this software is governed by the MIT license
   6  *
   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, France
  10  * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
  11  */
  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 elements
  22  * [offset, offset + size).
  23  * "size" lives in the target space of "offset".
  24  *
  25  * If any of the "offsets" is NaN, then the object represents
  26  * the failure of finding a fixed-size box.
  27  */
  28 struct 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  */
  47 static __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;
  63 error:
  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 offsets
  70  * in the given space and zero corresponding sizes.
  71  */
  72 static __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         size = isl_multi_val_zero(isl_space_range(space));
  80         return isl_fixed_box_alloc(offset, size);
  81 }
  82
  83 /* Return a copy of "box".
  84  */
  85 __isl_give isl_fixed_box *isl_fixed_box_copy(__isl_keep isl_fixed_box *box)
  86 {
  87         isl_multi_aff *offset;
  88         isl_multi_val *size;
  89
  90         offset = isl_fixed_box_get_offset(box);
  91         size = isl_fixed_box_get_size(box);
  92         return isl_fixed_box_alloc(offset, size);
  93 }
  94
  95 /* Replace the offset and size in direction "pos" by "offset" and "size"
  96  * (without checking whether "box" is a valid box).
  97  */
  98 static __isl_give isl_fixed_box *isl_fixed_box_set_extent(
  99         __isl_take isl_fixed_box *box, int pos, __isl_keep isl_aff *offset,
 100         __isl_keep isl_val *size)
 101 {
 102         if (!box)
 103                 return NULL;
 104         box->offset = isl_multi_aff_set_aff(box->offset, pos,
 105                                                         isl_aff_copy(offset));
 106         box->size = isl_multi_val_set_val(box->size, pos, isl_val_copy(size));
 107         if (!box->offset || !box->size)
 108                 return isl_fixed_box_free(box);
 109         return box;
 110 }
 111
 112 /* Replace the offset and size in direction "pos" by "offset" and "size",
 113  * if "box" is a valid box.
 114  */
 115 static __isl_give isl_fixed_box *isl_fixed_box_set_valid_extent(
 116         __isl_take isl_fixed_box *box, int pos, __isl_keep isl_aff *offset,
 117         __isl_keep isl_val *size)
 118 {
 119         isl_bool valid;
 120
 121         valid = isl_fixed_box_is_valid(box);
 122         if (valid < 0 || !valid)
 123                 return box;
 124         return isl_fixed_box_set_extent(box, pos, offset, size);
 125 }
 126
 127 /* Replace "box" by an invalid box, by setting all offsets to NaN
 128  * (and all sizes to infinity).
 129  */
 130 static __isl_give isl_fixed_box *isl_fixed_box_invalidate(
 131         __isl_take isl_fixed_box *box)
 132 {
 133         int i, n;
 134         isl_space *space;
 135         isl_val *infty;
 136         isl_aff *nan;
 137
 138         if (!box)
 139                 return NULL;
 140         n = isl_multi_val_dim(box->size, isl_dim_set);
 141
 142         infty = isl_val_infty(isl_fixed_box_get_ctx(box));
 143         space = isl_space_domain(isl_fixed_box_get_space(box));
 144         nan = isl_aff_nan_on_domain(isl_local_space_from_space(space));
 145         for (i = 0; i < n; ++i)
 146                 box = isl_fixed_box_set_extent(box, i, nan, infty);
 147         isl_aff_free(nan);
 148         isl_val_free(infty);
 149
 150         if (!box->offset || !box->size)
 151                 return isl_fixed_box_free(box);
 152         return box;
 153 }
 154
 155 /* Return the isl_ctx to which "box" belongs.
 156  */
 157 isl_ctx *isl_fixed_box_get_ctx(__isl_keep isl_fixed_box *box)
 158 {
 159         if (!box)
 160                 return NULL;
 161         return isl_multi_aff_get_ctx(box->offset);
 162 }
 163
 164 /* Return the space in which "box" lives.
 165  */
 166 __isl_give isl_space *isl_fixed_box_get_space(__isl_keep isl_fixed_box *box)
 167 {
 168         if (!box)
 169                 return NULL;
 170         return isl_multi_aff_get_space(box->offset);
 171 }
 172
 173 /* Does "box" contain valid information?
 174  */
 175 isl_bool isl_fixed_box_is_valid(__isl_keep isl_fixed_box *box)
 176 {
 177         if (!box)
 178                 return isl_bool_error;
 179         return isl_bool_not(isl_multi_aff_involves_nan(box->offset));
 180 }
 181
 182 /* Return the offsets of the box "box".
 183  */
 184 __isl_give isl_multi_aff *isl_fixed_box_get_offset(
 185         __isl_keep isl_fixed_box *box)
 186 {
 187         if (!box)
 188                 return NULL;
 189         return isl_multi_aff_copy(box->offset);
 190 }
 191
 192 /* Return the sizes of the box "box".
 193  */
 194 __isl_give isl_multi_val *isl_fixed_box_get_size(__isl_keep isl_fixed_box *box)
 195 {
 196         if (!box)
 197                 return NULL;
 198         return isl_multi_val_copy(box->size);
 199 }
 200
 201 /* Data used in set_dim_extent and compute_size_in_direction.
 202  *
 203  * "bset" is a wrapped copy of the basic map that has the selected
 204  * output dimension as range.
 205  * "pos" is the position of the variable representing the output dimension,
 206  * i.e., the variable for which the size should be computed.  This variable
 207  * is also the last variable in "bset".
 208  * "size" is the best size found so far
 209  * (infinity if no offset was found so far).
 210  * "offset" is the offset corresponding to the best size
 211  * (NULL if no offset was found so far).
 212  */
 213 struct isl_size_info {
 214         isl_basic_set *bset;
 215         int pos;
 216         isl_val *size;
 217         isl_aff *offset;
 218 };
 219
 220 /* Is "c" a suitable bound on dimension "pos" for use as a lower bound
 221  * of a fixed-size range.
 222  * In particular, it needs to be a lower bound on "pos".
 223  * In order for the final offset not to be too complicated,
 224  * the constraint itself should also not involve any integer divisions.
 225  */
 226 static isl_bool is_suitable_bound(__isl_keep isl_constraint *c, unsigned pos)
 227 {
 228         unsigned n_div;
 229         isl_bool is_bound, any_divs;
 230
 231         is_bound = isl_constraint_is_lower_bound(c, isl_dim_set, pos);
 232         if (is_bound < 0 || !is_bound)
 233                 return is_bound;
 234
 235         n_div = isl_constraint_dim(c, isl_dim_div);
 236         any_divs = isl_constraint_involves_dims(c, isl_dim_div, 0, n_div);
 237         return isl_bool_not(any_divs);
 238 }
 239
 240 /* Given a constraint from the basic set describing the bounds on
 241  * an array index, check if it is a lower bound, say m i >= b(x), and,
 242  * if so, check whether the expression "i - ceil(b(x)/m) + 1" has a constant
 243  * upper bound.  If so, and if this bound is smaller than any bound
 244  * derived from earlier constraints, set the size to this bound on
 245  * the expression and the lower bound to ceil(b(x)/m).
 246  */
 247 static isl_stat compute_size_in_direction(__isl_take isl_constraint *c,
 248         void *user)
 249 {
 250         struct isl_size_info *info = user;
 251         isl_val *v;
 252         isl_aff *aff;
 253         isl_aff *lb;
 254         isl_bool is_bound, better;
 255
 256         is_bound = is_suitable_bound(c, info->pos);
 257         if (is_bound < 0 || !is_bound) {
 258                 isl_constraint_free(c);
 259                 return is_bound < 0 ? isl_stat_error : isl_stat_ok;
 260         }
 261
 262         aff = isl_constraint_get_bound(c, isl_dim_set, info->pos);
 263         aff = isl_aff_ceil(aff);
 264
 265         lb = isl_aff_copy(aff);
 266
 267         aff = isl_aff_neg(aff);
 268         aff = isl_aff_add_coefficient_si(aff, isl_dim_in, info->pos, 1);
 269
 270         v = isl_basic_set_max_val(info->bset, aff);
 271         isl_aff_free(aff);
 272
 273         v = isl_val_add_ui(v, 1);
 274         better = isl_val_lt(v, info->size);
 275         if (better >= 0 && better) {
 276                 isl_val_free(info->size);
 277                 info->size = isl_val_copy(v);
 278                 lb = isl_aff_domain_factor_domain(lb);
 279                 isl_aff_free(info->offset);
 280                 info->offset = isl_aff_copy(lb);
 281         }
 282         isl_val_free(v);
 283         isl_aff_free(lb);
 284
 285         isl_constraint_free(c);
 286
 287         return better < 0 ? isl_stat_error : isl_stat_ok;
 288 }
 289
 290 /* Look for a fixed-size range of values for the output dimension "pos"
 291  * of "map", by looking for a lower-bound expression in the parameters
 292  * and input dimensions such that the range of the output dimension
 293  * is a constant shifted by this expression.
 294  *
 295  * In particular, look through the explicit lower bounds on the output dimension
 296  * for candidate expressions and pick the one that results in the smallest size.
 297  * Initialize the size with infinity and if no better size is found
 298  * then invalidate the box.  Otherwise, set the offset and size
 299  * in the given direction by those that correspond to the smallest size.
 300  */
 301 static __isl_give isl_fixed_box *set_dim_extent(__isl_take isl_fixed_box *box,
 302         __isl_keep isl_map *map, int pos)
 303 {
 304         struct isl_size_info info;
 305         isl_bool valid;
 306         isl_ctx *ctx;
 307
 308         if (!box || !map)
 309                 return isl_fixed_box_free(box);
 310
 311         ctx = isl_map_get_ctx(map);
 312         map = isl_map_copy(map);
 313         map = isl_map_project_onto(map, isl_dim_out, pos, 1);
 314         map = isl_map_compute_divs(map);
 315         info.size = isl_val_infty(ctx);
 316         info.offset = NULL;
 317         info.pos = isl_map_dim(map, isl_dim_in);
 318         info.bset = isl_basic_map_wrap(isl_map_simple_hull(map));
 319         if (isl_basic_set_foreach_constraint(info.bset,
 320                                         &compute_size_in_direction, &info) < 0)
 321                 box = isl_fixed_box_free(box);
 322         valid = isl_val_is_int(info.size);
 323         if (valid < 0)
 324                 box = isl_fixed_box_free(box);
 325         else if (valid)
 326                 box = isl_fixed_box_set_valid_extent(box, pos,
 327                                                      info.offset, info.size);
 328         else
 329                 box = isl_fixed_box_invalidate(box);
 330         isl_val_free(info.size);
 331         isl_aff_free(info.offset);
 332         isl_basic_set_free(info.bset);
 333
 334         return box;
 335 }
 336
 337 /* Try and construct a fixed-size rectangular box with an offset
 338  * in terms of the domain of "map" that contains the range of "map".
 339  * If no such box can be constructed, then return an invalidated box,
 340  * i.e., one where isl_fixed_box_is_valid returns false.
 341  *
 342  * Iterate over the dimensions in the range
 343  * setting the corresponding offset and extent.
 344  */
 345 __isl_give isl_fixed_box *isl_map_get_range_simple_fixed_box_hull(
 346         __isl_keep isl_map *map)
 347 {
 348         int i, n;
 349         isl_space *space;
 350         isl_fixed_box *box;
 351
 352         n = isl_map_dim(map, isl_dim_out);
 353         space = isl_map_get_space(map);
 354         box = isl_fixed_box_init(space);
 355
 356         map = isl_map_detect_equalities(isl_map_copy(map));
 357         for (i = 0; i < n; ++i) {
 358                 isl_bool valid;
 359
 360                 box = set_dim_extent(box, map, i);
 361                 valid = isl_fixed_box_is_valid(box);
 362                 if (valid < 0 || !valid)
 363                         break;
 364         }
 365         isl_map_free(map);
 366
 367         return box;
 368 }