isl_basic_map_eliminate: reuse isl_basic_map_check_range
[isl.git] / isl_box.c
blobb90ef869f349a0f5a65f345dc0aa4dfd9d8768c2
1 /*
2 * Copyright 2010-2011 INRIA Saclay
3 * Copyright 2012-2013 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
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
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>
21 /* Representation of a box of fixed size containing the elements
22 * [offset, offset + size).
23 * "size" lives in the target space of "offset".
25 * If any of the "offsets" is NaN, then the object represents
26 * the failure of finding a fixed-size box.
28 struct isl_fixed_box {
29 isl_multi_aff *offset;
30 isl_multi_val *size;
33 /* Free "box" and return NULL.
35 __isl_null isl_fixed_box *isl_fixed_box_free(__isl_take isl_fixed_box *box)
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;
45 /* Construct an isl_fixed_box with the given offset and size.
47 static __isl_give isl_fixed_box *isl_fixed_box_alloc(
48 __isl_take isl_multi_aff *offset, __isl_take isl_multi_val *size)
50 isl_ctx *ctx;
51 isl_fixed_box *box;
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;
62 return box;
63 error:
64 isl_multi_aff_free(offset);
65 isl_multi_val_free(size);
66 return NULL;
69 /* Construct an initial isl_fixed_box with zero offsets
70 * in the given space and zero corresponding sizes.
72 static __isl_give isl_fixed_box *isl_fixed_box_init(
73 __isl_take isl_space *space)
75 isl_multi_aff *offset;
76 isl_multi_val *size;
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);
83 /* Return a copy of "box".
85 __isl_give isl_fixed_box *isl_fixed_box_copy(__isl_keep isl_fixed_box *box)
87 isl_multi_aff *offset;
88 isl_multi_val *size;
90 offset = isl_fixed_box_get_offset(box);
91 size = isl_fixed_box_get_size(box);
92 return isl_fixed_box_alloc(offset, size);
95 /* Replace the offset and size in direction "pos" by "offset" and "size"
96 * (without checking whether "box" is a valid box).
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)
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;
112 /* Replace the offset and size in direction "pos" by "offset" and "size",
113 * if "box" is a valid box.
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)
119 isl_bool valid;
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);
127 /* Replace "box" by an invalid box, by setting all offsets to NaN
128 * (and all sizes to infinity).
130 static __isl_give isl_fixed_box *isl_fixed_box_invalidate(
131 __isl_take isl_fixed_box *box)
133 int i, n;
134 isl_space *space;
135 isl_val *infty;
136 isl_aff *nan;
138 if (!box)
139 return NULL;
140 n = isl_multi_val_dim(box->size, isl_dim_set);
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);
150 if (!box->offset || !box->size)
151 return isl_fixed_box_free(box);
152 return box;
155 /* Return the isl_ctx to which "box" belongs.
157 isl_ctx *isl_fixed_box_get_ctx(__isl_keep isl_fixed_box *box)
159 if (!box)
160 return NULL;
161 return isl_multi_aff_get_ctx(box->offset);
164 /* Return the space in which "box" lives.
166 __isl_give isl_space *isl_fixed_box_get_space(__isl_keep isl_fixed_box *box)
168 if (!box)
169 return NULL;
170 return isl_multi_aff_get_space(box->offset);
173 /* Does "box" contain valid information?
175 isl_bool isl_fixed_box_is_valid(__isl_keep isl_fixed_box *box)
177 if (!box)
178 return isl_bool_error;
179 return isl_bool_not(isl_multi_aff_involves_nan(box->offset));
182 /* Return the offsets of the box "box".
184 __isl_give isl_multi_aff *isl_fixed_box_get_offset(
185 __isl_keep isl_fixed_box *box)
187 if (!box)
188 return NULL;
189 return isl_multi_aff_copy(box->offset);
192 /* Return the sizes of the box "box".
194 __isl_give isl_multi_val *isl_fixed_box_get_size(__isl_keep isl_fixed_box *box)
196 if (!box)
197 return NULL;
198 return isl_multi_val_copy(box->size);
201 /* Data used in set_dim_extent and compute_size_in_direction.
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).
213 struct isl_size_info {
214 isl_basic_set *bset;
215 int pos;
216 isl_val *size;
217 isl_aff *offset;
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.
226 static isl_bool is_suitable_bound(__isl_keep isl_constraint *c, unsigned pos)
228 unsigned n_div;
229 isl_bool is_bound, any_divs;
231 is_bound = isl_constraint_is_lower_bound(c, isl_dim_set, pos);
232 if (is_bound < 0 || !is_bound)
233 return is_bound;
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);
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).
247 static isl_stat compute_size_in_direction(__isl_take isl_constraint *c,
248 void *user)
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;
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;
262 aff = isl_constraint_get_bound(c, isl_dim_set, info->pos);
263 aff = isl_aff_ceil(aff);
265 lb = isl_aff_copy(aff);
267 aff = isl_aff_neg(aff);
268 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, info->pos, 1);
270 v = isl_basic_set_max_val(info->bset, aff);
271 isl_aff_free(aff);
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);
282 isl_val_free(v);
283 isl_aff_free(lb);
285 isl_constraint_free(c);
287 return better < 0 ? isl_stat_error : isl_stat_ok;
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.
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.
301 static __isl_give isl_fixed_box *set_dim_extent(__isl_take isl_fixed_box *box,
302 __isl_keep isl_map *map, int pos)
304 struct isl_size_info info;
305 isl_bool valid;
306 isl_ctx *ctx;
308 if (!box || !map)
309 return isl_fixed_box_free(box);
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);
334 return box;
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.
342 * Iterate over the dimensions in the range
343 * setting the corresponding offset and extent.
345 __isl_give isl_fixed_box *isl_map_get_range_simple_fixed_box_hull(
346 __isl_keep isl_map *map)
348 int i, n;
349 isl_space *space;
350 isl_fixed_box *box;
352 n = isl_map_dim(map, isl_dim_out);
353 space = isl_map_get_space(map);
354 box = isl_fixed_box_init(space);
356 map = isl_map_detect_equalities(isl_map_copy(map));
357 for (i = 0; i < n; ++i) {
358 isl_bool valid;
360 box = set_dim_extent(box, map, i);
361 valid = isl_fixed_box_is_valid(box);
362 if (valid < 0 || !valid)
363 break;
365 isl_map_free(map);
367 return box;