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 */
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(multi: box->offset);
40 isl_multi_val_free(multi: box->size);
41 free(ptr: 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(multi: 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(multi: offset);
65 isl_multi_val_free(multi: 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 */
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(space: isl_space_copy(space));
79 space = isl_space_drop_all_params(space: 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(multi: box->offset, pos,
106 el: isl_aff_copy(aff: offset));
107 box->size = isl_multi_val_set_val(multi: box->size, pos, el: isl_val_copy(v: 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 NaN
129 * (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(multi: box->size, type: isl_dim_set);
143 if (n < 0)
144 return isl_fixed_box_free(box);
145
146 infty = isl_val_infty(ctx: isl_fixed_box_get_ctx(box));
147 space = isl_space_domain(space: isl_fixed_box_get_space(box));
148 nan = isl_aff_nan_on_domain(ls: isl_local_space_from_space(space));
149 for (i = 0; i < n; ++i)
150 box = isl_fixed_box_set_extent(box, pos: i, offset: nan, size: infty);
151 isl_aff_free(aff: nan);
152 isl_val_free(v: 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(multi: 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(multi: 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(multi: 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(b: isl_multi_aff_involves_nan(multi: 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(multi: 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(multi: 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 */
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 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 */
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(constraint: c, type: isl_dim_set, pos);
257 if (is_bound < 0 || !is_bound)
258 return is_bound;
259
260 n_div = isl_constraint_dim(constraint: c, type: isl_dim_div);
261 if (n_div < 0)
262 return isl_bool_error;
263 any_divs = isl_constraint_involves_dims(constraint: c, type: isl_dim_div, first: 0, n: n_div);
264 return isl_bool_not(b: 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 */
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, pos: 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(constraint: c, type: isl_dim_set, pos: 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, type: isl_dim_in, pos: info->pos, v: 1);
296
297 v = isl_basic_set_max_val(bset: info->bset, obj: aff);
298 isl_aff_free(aff);
299
300 v = isl_val_add_ui(v1: v, v2: 1);
301 better = isl_val_lt(v1: v, v2: info->size);
302 if (better >= 0 && better) {
303 isl_val_free(v: info->size);
304 info->size = isl_val_copy(v);
305 lb = isl_aff_domain_factor_domain(aff: lb);
306 isl_aff_free(aff: info->offset);
307 info->offset = isl_aff_copy(aff: lb);
308 }
309 isl_val_free(v);
310 isl_aff_free(aff: 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 */
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, type: isl_dim_out, first: pos, n: 1);
349 info.size = isl_val_infty(ctx);
350 info.offset = NULL;
351 info.pos = isl_map_dim(map, type: isl_dim_in);
352 info.bset = isl_basic_map_wrap(bmap: isl_map_simple_hull(map));
353 bset = isl_basic_set_copy(bset: 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 fn: &compute_size_in_direction, user: &info) < 0)
359 box = isl_fixed_box_free(box);
360 isl_basic_set_free(bset);
361 valid = isl_val_is_int(v: 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 offset: info.offset, size: info.size);
367 else
368 box = isl_fixed_box_invalidate(box);
369 isl_val_free(v: info.size);
370 isl_aff_free(aff: info.offset);
371 isl_basic_set_free(bset: 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, type: 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(map: isl_map_copy(map));
399 for (i = 0; i < n; ++i) {
400 isl_bool valid;
401
402 box = set_dim_extent(box, map, pos: 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 map
413 * with a zero-dimensional domain and
414 * 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(set: 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 offset
431 * 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_hull
436 * by constructing a map from the set and
437 * 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, map_box: &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 1
449 * (and offset 0).
450 *
451 * Obtain stride information in each output dimension separately and
452 * 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, type: 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, pos: 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, pos: i, offset, size: stride);
479
480 isl_aff_free(aff: offset);
481 isl_val_free(v: 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 1
491 * (and offset 0).
492 *
493 * Consider the set as a map with a zero-dimensional domain and
494 * 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, map_box: &isl_map_get_range_lattice_tile);
499}
500
501#undef BASE
502#define BASE multi_val
503#include "print_yaml_field_templ.c"
504
505#undef BASE
506#define BASE multi_aff
507#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(printer: p);
517
518 p = isl_printer_yaml_start_mapping(p);
519 p = print_yaml_field_multi_aff(p, name: "offset", val: box->offset);
520 p = print_yaml_field_multi_val(p, name: "size", val: box->size);
521 p = isl_printer_yaml_end_mapping(p);
522
523 return p;
524}
525
526#undef BASE
527#define BASE fixed_box
528#include <print_templ_yaml.c>
529

source code of polly/lib/External/isl/isl_box.c