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;
 134         isl_size n;
 135         isl_space *space;
 136         isl_val *infty;
 137         isl_aff *nan;
 138
 139         if (!box)
 140                 return NULL;
 141         n = isl_multi_val_dim(box->size, isl_dim_set);
 142         if (n < 0)
 143                 return isl_fixed_box_free(box);
 144
 145         infty = isl_val_infty(isl_fixed_box_get_ctx(box));
 146         space = isl_space_domain(isl_fixed_box_get_space(box));
 147         nan = isl_aff_nan_on_domain(isl_local_space_from_space(space));
 148         for (i = 0; i < n; ++i)
 149                 box = isl_fixed_box_set_extent(box, i, nan, infty);
 150         isl_aff_free(nan);
 151         isl_val_free(infty);
 152
 153         if (!box->offset || !box->size)
 154                 return isl_fixed_box_free(box);
 155         return box;
 156 }
 157
 158 /* Return the isl_ctx to which "box" belongs.
 159  */
 160 isl_ctx *isl_fixed_box_get_ctx(__isl_keep isl_fixed_box *box)
 161 {
 162         if (!box)
 163                 return NULL;
 164         return isl_multi_aff_get_ctx(box->offset);
 165 }
 166
 167 /* Return the space in which "box" lives.
 168  */
 169 __isl_give isl_space *isl_fixed_box_get_space(__isl_keep isl_fixed_box *box)
 170 {
 171         if (!box)
 172                 return NULL;
 173         return isl_multi_aff_get_space(box->offset);
 174 }
 175
 176 /* Does "box" contain valid information?
 177  */
 178 isl_bool isl_fixed_box_is_valid(__isl_keep isl_fixed_box *box)
 179 {
 180         if (!box)
 181                 return isl_bool_error;
 182         return isl_bool_not(isl_multi_aff_involves_nan(box->offset));
 183 }
 184
 185 /* Return the offsets of the box "box".
 186  */
 187 __isl_give isl_multi_aff *isl_fixed_box_get_offset(
 188         __isl_keep isl_fixed_box *box)
 189 {
 190         if (!box)
 191                 return NULL;
 192         return isl_multi_aff_copy(box->offset);
 193 }
 194
 195 /* Return the sizes of the box "box".
 196  */
 197 __isl_give isl_multi_val *isl_fixed_box_get_size(__isl_keep isl_fixed_box *box)
 198 {
 199         if (!box)
 200                 return NULL;
 201         return isl_multi_val_copy(box->size);
 202 }
 203
 204 /* Data used in set_dim_extent and compute_size_in_direction.
 205  *
 206  * "bset" is a wrapped copy of the basic map that has the selected
 207  * output dimension as range.
 208  * "pos" is the position of the variable representing the output dimension,
 209  * i.e., the variable for which the size should be computed.  This variable
 210  * is also the last variable in "bset".
 211  * "size" is the best size found so far
 212  * (infinity if no offset was found so far).
 213  * "offset" is the offset corresponding to the best size
 214  * (NULL if no offset was found so far).
 215  */
 216 struct isl_size_info {
 217         isl_basic_set *bset;
 218         isl_size pos;
 219         isl_val *size;
 220         isl_aff *offset;
 221 };
 222
 223 /* Is "c" a suitable bound on dimension "pos" for use as a lower bound
 224  * of a fixed-size range.
 225  * In particular, it needs to be a lower bound on "pos".
 226  * In order for the final offset not to be too complicated,
 227  * the constraint itself should also not involve any integer divisions.
 228  */
 229 static isl_bool is_suitable_bound(__isl_keep isl_constraint *c, unsigned pos)
 230 {
 231         isl_size n_div;
 232         isl_bool is_bound, any_divs;
 233
 234         is_bound = isl_constraint_is_lower_bound(c, isl_dim_set, pos);
 235         if (is_bound < 0 || !is_bound)
 236                 return is_bound;
 237
 238         n_div = isl_constraint_dim(c, isl_dim_div);
 239         if (n_div < 0)
 240                 return isl_bool_error;
 241         any_divs = isl_constraint_involves_dims(c, isl_dim_div, 0, n_div);
 242         return isl_bool_not(any_divs);
 243 }
 244
 245 /* Given a constraint from the basic set describing the bounds on
 246  * an array index, check if it is a lower bound, say m i >= b(x), and,
 247  * if so, check whether the expression "i - ceil(b(x)/m) + 1" has a constant
 248  * upper bound.  If so, and if this bound is smaller than any bound
 249  * derived from earlier constraints, set the size to this bound on
 250  * the expression and the lower bound to ceil(b(x)/m).
 251  */
 252 static isl_stat compute_size_in_direction(__isl_take isl_constraint *c,
 253         void *user)
 254 {
 255         struct isl_size_info *info = user;
 256         isl_val *v;
 257         isl_aff *aff;
 258         isl_aff *lb;
 259         isl_bool is_bound, better;
 260
 261         is_bound = is_suitable_bound(c, info->pos);
 262         if (is_bound < 0 || !is_bound) {
 263                 isl_constraint_free(c);
 264                 return is_bound < 0 ? isl_stat_error : isl_stat_ok;
 265         }
 266
 267         aff = isl_constraint_get_bound(c, isl_dim_set, info->pos);
 268         aff = isl_aff_ceil(aff);
 269
 270         lb = isl_aff_copy(aff);
 271
 272         aff = isl_aff_neg(aff);
 273         aff = isl_aff_add_coefficient_si(aff, isl_dim_in, info->pos, 1);
 274
 275         v = isl_basic_set_max_val(info->bset, aff);
 276         isl_aff_free(aff);
 277
 278         v = isl_val_add_ui(v, 1);
 279         better = isl_val_lt(v, info->size);
 280         if (better >= 0 && better) {
 281                 isl_val_free(info->size);
 282                 info->size = isl_val_copy(v);
 283                 lb = isl_aff_domain_factor_domain(lb);
 284                 isl_aff_free(info->offset);
 285                 info->offset = isl_aff_copy(lb);
 286         }
 287         isl_val_free(v);
 288         isl_aff_free(lb);
 289
 290         isl_constraint_free(c);
 291
 292         return better < 0 ? isl_stat_error : isl_stat_ok;
 293 }
 294
 295 /* Look for a fixed-size range of values for the output dimension "pos"
 296  * of "map", by looking for a lower-bound expression in the parameters
 297  * and input dimensions such that the range of the output dimension
 298  * is a constant shifted by this expression.
 299  *
 300  * In particular, look through the explicit lower bounds on the output dimension
 301  * for candidate expressions and pick the one that results in the smallest size.
 302  * Initialize the size with infinity and if no better size is found
 303  * then invalidate the box.  Otherwise, set the offset and size
 304  * in the given direction by those that correspond to the smallest size.
 305  */
 306 static __isl_give isl_fixed_box *set_dim_extent(__isl_take isl_fixed_box *box,
 307         __isl_keep isl_map *map, int pos)
 308 {
 309         struct isl_size_info info;
 310         isl_bool valid;
 311         isl_ctx *ctx;
 312
 313         if (!box || !map)
 314                 return isl_fixed_box_free(box);
 315
 316         ctx = isl_map_get_ctx(map);
 317         map = isl_map_copy(map);
 318         map = isl_map_project_onto(map, isl_dim_out, pos, 1);
 319         map = isl_map_compute_divs(map);
 320         info.size = isl_val_infty(ctx);
 321         info.offset = NULL;
 322         info.pos = isl_map_dim(map, isl_dim_in);
 323         info.bset = isl_basic_map_wrap(isl_map_simple_hull(map));
 324         if (info.pos < 0)
 325                 info.bset = isl_basic_set_free(info.bset);
 326         if (isl_basic_set_foreach_constraint(info.bset,
 327                                         &compute_size_in_direction, &info) < 0)
 328                 box = isl_fixed_box_free(box);
 329         valid = isl_val_is_int(info.size);
 330         if (valid < 0)
 331                 box = isl_fixed_box_free(box);
 332         else if (valid)
 333                 box = isl_fixed_box_set_valid_extent(box, pos,
 334                                                      info.offset, info.size);
 335         else
 336                 box = isl_fixed_box_invalidate(box);
 337         isl_val_free(info.size);
 338         isl_aff_free(info.offset);
 339         isl_basic_set_free(info.bset);
 340
 341         return box;
 342 }
 343
 344 /* Try and construct a fixed-size rectangular box with an offset
 345  * in terms of the domain of "map" that contains the range of "map".
 346  * If no such box can be constructed, then return an invalidated box,
 347  * i.e., one where isl_fixed_box_is_valid returns false.
 348  *
 349  * Iterate over the dimensions in the range
 350  * setting the corresponding offset and extent.
 351  */
 352 __isl_give isl_fixed_box *isl_map_get_range_simple_fixed_box_hull(
 353         __isl_keep isl_map *map)
 354 {
 355         int i;
 356         isl_size n;
 357         isl_space *space;
 358         isl_fixed_box *box;
 359
 360         n = isl_map_dim(map, isl_dim_out);
 361         if (n < 0)
 362                 return NULL;
 363         space = isl_map_get_space(map);
 364         box = isl_fixed_box_init(space);
 365
 366         map = isl_map_detect_equalities(isl_map_copy(map));
 367         for (i = 0; i < n; ++i) {
 368                 isl_bool valid;
 369
 370                 box = set_dim_extent(box, map, i);
 371                 valid = isl_fixed_box_is_valid(box);
 372                 if (valid < 0 || !valid)
 373                         break;
 374         }
 375         isl_map_free(map);
 376
 377         return box;
 378 }
 379
 380 #undef BASE
 381 #define BASE multi_val
 382 #include "print_yaml_field_templ.c"
 383
 384 #undef BASE
 385 #define BASE multi_aff
 386 #include "print_yaml_field_templ.c"
 387
 388 /* Print the information contained in "box" to "p".
 389  * The information is printed as a YAML document.
 390  */
 391 __isl_give isl_printer *isl_printer_print_fixed_box(
 392         __isl_take isl_printer *p, __isl_keep isl_fixed_box *box)
 393 {
 394         if (!box)
 395                 return isl_printer_free(p);
 396
 397         p = isl_printer_yaml_start_mapping(p);
 398         p = print_yaml_field_multi_aff(p, "offset", box->offset);
 399         p = print_yaml_field_multi_val(p, "size", box->size);
 400         p = isl_printer_yaml_end_mapping(p);
 401
 402         return p;
 403 }
 404
 405 #undef BASE
 406 #define BASE fixed_box
 407 #include <print_templ_yaml.c>