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         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  */
  99 static __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  */
 116 static __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 NaN
 129  * (and all sizes to infinity).
 130  */
 131 static __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  */
 162 static __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  */
 182 isl_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  */
 200 isl_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 selected
 229  * 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 variable
 232  * is also the last variable in "bset".
 233  * "size" is the best size found so far
 234  * (infinity if no offset was found so far).
 235  * "offset" is the offset corresponding to the best size
 236  * (NULL if no offset was found so far).
 237  */
 238 struct 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 bound
 246  * 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  */
 251 static 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 on
 268  * 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 constant
 270  * upper bound.  If so, and if this bound is smaller than any bound
 271  * derived from earlier constraints, set the size to this bound on
 272  * the expression and the lower bound to ceil(b(x)/m).
 273  */
 274 static 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 parameters
 319  * and input dimensions such that the range of the output dimension
 320  * is a constant shifted by this expression.
 321  *
 322  * In particular, look through the explicit lower bounds on the output dimension
 323  * 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 found
 325  * then invalidate the box.  Otherwise, set the offset and size
 326  * 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 which
 333  * the size is computed.
 334  */
 335 static __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         else
 368                 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 offset
 377  * 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 range
 382  * 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 /* Try and construct a fixed-size rectangular box with an offset
 413  * in terms of the parameters of "set" that contains "set".
 414  * If no such box can be constructed, then return an invalidated box,
 415  * i.e., one where isl_fixed_box_is_valid returns false.
 416  *
 417  * Compute the box using isl_map_get_range_simple_fixed_box_hull
 418  * by constructing a map from the set and
 419  * project out the domain again from the result.
 420  */
 421 __isl_give isl_fixed_box *isl_set_get_simple_fixed_box_hull(
 422         __isl_keep isl_set *set)
 423 {
 424         isl_map *map;
 425         isl_fixed_box *box;
 426
 427         map = isl_map_from_range(isl_set_copy(set));
 428         box = isl_map_get_range_simple_fixed_box_hull(map);
 429         isl_map_free(map);
 430         box = isl_fixed_box_project_domain_on_params(box);
 431
 432         return box;
 433 }
 434
 435 #undef BASE
 436 #define BASE multi_val
 437 #include "print_yaml_field_templ.c"
 438
 439 #undef BASE
 440 #define BASE multi_aff
 441 #include "print_yaml_field_templ.c"
 442
 443 /* Print the information contained in "box" to "p".
 444  * The information is printed as a YAML document.
 445  */
 446 __isl_give isl_printer *isl_printer_print_fixed_box(
 447         __isl_take isl_printer *p, __isl_keep isl_fixed_box *box)
 448 {
 449         if (!box)
 450                 return isl_printer_free(p);
 451
 452         p = isl_printer_yaml_start_mapping(p);
 453         p = print_yaml_field_multi_aff(p, "offset", box->offset);
 454         p = print_yaml_field_multi_val(p, "size", box->size);
 455         p = isl_printer_yaml_end_mapping(p);
 456
 457         return p;
 458 }
 459
 460 #undef BASE
 461 #define BASE fixed_box
 462 #include <print_templ_yaml.c>