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 /* Check whether the output elements lie on a rectangular lattice, 436 * possibly depending on the parameters and the input dimensions. 437 * Return a tile in this lattice. 438 * If no stride information can be found, then return a tile of size 1 439 * (and offset 0). 440 * 441 * Obtain stride information in each output dimension separately and 442 * combine the results. 443 */ 444 __isl_give isl_fixed_box *isl_map_get_range_lattice_tile( 445 __isl_keep isl_map *map) 446 { 447 int i; 448 isl_size n; 449 isl_space *space; 450 isl_fixed_box *box; 451 452 n = isl_map_dim(map, isl_dim_out); 453 if (n < 0) 454 return NULL; 455 space = isl_map_get_space(map); 456 box = isl_fixed_box_init(space); 457 458 for (i = 0; i < n; ++i) { 459 isl_val *stride; 460 isl_aff *offset; 461 isl_stride_info *si; 462 463 si = isl_map_get_range_stride_info(map, i); 464 stride = isl_stride_info_get_stride(si); 465 offset = isl_stride_info_get_offset(si); 466 isl_stride_info_free(si); 467 468 box = isl_fixed_box_set_valid_extent(box, i, offset, stride); 469 470 isl_aff_free(offset); 471 isl_val_free(stride); 472 } 473 474 return box; 475 } 476 477 #undef BASE 478 #define BASE multi_val 479 #include "print_yaml_field_templ.c" 480 481 #undef BASE 482 #define BASE multi_aff 483 #include "print_yaml_field_templ.c" 484 485 /* Print the information contained in "box" to "p". 486 * The information is printed as a YAML document. 487 */ 488 __isl_give isl_printer *isl_printer_print_fixed_box( 489 __isl_take isl_printer *p, __isl_keep isl_fixed_box *box) 490 { 491 if (!box) 492 return isl_printer_free(p); 493 494 p = isl_printer_yaml_start_mapping(p); 495 p = print_yaml_field_multi_aff(p, "offset", box->offset); 496 p = print_yaml_field_multi_val(p, "size", box->size); 497 p = isl_printer_yaml_end_mapping(p); 498 499 return p; 500 } 501 502 #undef BASE 503 #define BASE fixed_box 504 #include <print_templ_yaml.c> 505