Line data Source code
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 0 : __isl_null isl_fixed_box *isl_fixed_box_free(__isl_take isl_fixed_box *box)
36 : {
37 0 : if (!box)
38 0 : return NULL;
39 0 : isl_multi_aff_free(box->offset);
40 0 : isl_multi_val_free(box->size);
41 0 : free(box);
42 0 : return NULL;
43 : }
44 :
45 : /* Construct an isl_fixed_box with the given offset and size.
46 : */
47 0 : 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 0 : if (!offset || !size)
54 : goto error;
55 0 : ctx = isl_multi_aff_get_ctx(offset);
56 0 : box = isl_alloc_type(ctx, struct isl_fixed_box);
57 0 : if (!box)
58 0 : goto error;
59 0 : box->offset = offset;
60 0 : box->size = size;
61 :
62 0 : return box;
63 : error:
64 0 : isl_multi_aff_free(offset);
65 0 : isl_multi_val_free(size);
66 0 : 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 0 : 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 0 : offset = isl_multi_aff_zero(isl_space_copy(space));
79 0 : size = isl_multi_val_zero(isl_space_range(space));
80 0 : return isl_fixed_box_alloc(offset, size);
81 : }
82 :
83 : /* Return a copy of "box".
84 : */
85 0 : __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 0 : offset = isl_fixed_box_get_offset(box);
91 0 : size = isl_fixed_box_get_size(box);
92 0 : 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 0 : 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 0 : if (!box)
103 0 : return NULL;
104 0 : box->offset = isl_multi_aff_set_aff(box->offset, pos,
105 : isl_aff_copy(offset));
106 0 : box->size = isl_multi_val_set_val(box->size, pos, isl_val_copy(size));
107 0 : if (!box->offset || !box->size)
108 0 : return isl_fixed_box_free(box);
109 0 : 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 0 : 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 0 : valid = isl_fixed_box_is_valid(box);
122 0 : if (valid < 0 || !valid)
123 0 : return box;
124 0 : 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 0 : static __isl_give isl_fixed_box *isl_fixed_box_invalidate(
131 : __isl_take isl_fixed_box *box)
132 : {
133 : int i, n;
134 : isl_space *space;
135 : isl_val *infty;
136 : isl_aff *nan;
137 :
138 0 : if (!box)
139 0 : return NULL;
140 0 : n = isl_multi_val_dim(box->size, isl_dim_set);
141 :
142 0 : infty = isl_val_infty(isl_fixed_box_get_ctx(box));
143 0 : space = isl_space_domain(isl_fixed_box_get_space(box));
144 0 : nan = isl_aff_nan_on_domain(isl_local_space_from_space(space));
145 0 : for (i = 0; i < n; ++i)
146 0 : box = isl_fixed_box_set_extent(box, i, nan, infty);
147 0 : isl_aff_free(nan);
148 0 : isl_val_free(infty);
149 :
150 0 : if (!box->offset || !box->size)
151 0 : return isl_fixed_box_free(box);
152 0 : return box;
153 : }
154 :
155 : /* Return the isl_ctx to which "box" belongs.
156 : */
157 0 : isl_ctx *isl_fixed_box_get_ctx(__isl_keep isl_fixed_box *box)
158 : {
159 0 : if (!box)
160 0 : return NULL;
161 0 : return isl_multi_aff_get_ctx(box->offset);
162 : }
163 :
164 : /* Return the space in which "box" lives.
165 : */
166 0 : __isl_give isl_space *isl_fixed_box_get_space(__isl_keep isl_fixed_box *box)
167 : {
168 0 : if (!box)
169 0 : return NULL;
170 0 : return isl_multi_aff_get_space(box->offset);
171 : }
172 :
173 : /* Does "box" contain valid information?
174 : */
175 0 : isl_bool isl_fixed_box_is_valid(__isl_keep isl_fixed_box *box)
176 : {
177 0 : if (!box)
178 0 : return isl_bool_error;
179 0 : return isl_bool_not(isl_multi_aff_involves_nan(box->offset));
180 : }
181 :
182 : /* Return the offsets of the box "box".
183 : */
184 0 : __isl_give isl_multi_aff *isl_fixed_box_get_offset(
185 : __isl_keep isl_fixed_box *box)
186 : {
187 0 : if (!box)
188 0 : return NULL;
189 0 : return isl_multi_aff_copy(box->offset);
190 : }
191 :
192 : /* Return the sizes of the box "box".
193 : */
194 0 : __isl_give isl_multi_val *isl_fixed_box_get_size(__isl_keep isl_fixed_box *box)
195 : {
196 0 : if (!box)
197 0 : return NULL;
198 0 : return isl_multi_val_copy(box->size);
199 : }
200 :
201 : /* Data used in set_dim_extent and compute_size_in_direction.
202 : *
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).
212 : */
213 : struct isl_size_info {
214 : isl_basic_set *bset;
215 : int pos;
216 : isl_val *size;
217 : isl_aff *offset;
218 : };
219 :
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.
225 : */
226 0 : static isl_bool is_suitable_bound(__isl_keep isl_constraint *c, unsigned pos)
227 : {
228 : unsigned n_div;
229 : isl_bool is_bound, any_divs;
230 :
231 0 : is_bound = isl_constraint_is_lower_bound(c, isl_dim_set, pos);
232 0 : if (is_bound < 0 || !is_bound)
233 0 : return is_bound;
234 :
235 0 : n_div = isl_constraint_dim(c, isl_dim_div);
236 0 : any_divs = isl_constraint_involves_dims(c, isl_dim_div, 0, n_div);
237 0 : return isl_bool_not(any_divs);
238 : }
239 :
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).
246 : */
247 0 : static isl_stat compute_size_in_direction(__isl_take isl_constraint *c,
248 : void *user)
249 : {
250 0 : struct isl_size_info *info = user;
251 : isl_val *v;
252 : isl_aff *aff;
253 : isl_aff *lb;
254 : isl_bool is_bound, better;
255 :
256 0 : is_bound = is_suitable_bound(c, info->pos);
257 0 : if (is_bound < 0 || !is_bound) {
258 0 : isl_constraint_free(c);
259 0 : return is_bound < 0 ? isl_stat_error : isl_stat_ok;
260 : }
261 :
262 0 : aff = isl_constraint_get_bound(c, isl_dim_set, info->pos);
263 0 : aff = isl_aff_ceil(aff);
264 :
265 0 : lb = isl_aff_copy(aff);
266 :
267 0 : aff = isl_aff_neg(aff);
268 0 : aff = isl_aff_add_coefficient_si(aff, isl_dim_in, info->pos, 1);
269 :
270 0 : v = isl_basic_set_max_val(info->bset, aff);
271 0 : isl_aff_free(aff);
272 :
273 0 : v = isl_val_add_ui(v, 1);
274 0 : better = isl_val_lt(v, info->size);
275 0 : if (better >= 0 && better) {
276 0 : isl_val_free(info->size);
277 0 : info->size = isl_val_copy(v);
278 0 : lb = isl_aff_domain_factor_domain(lb);
279 0 : isl_aff_free(info->offset);
280 0 : info->offset = isl_aff_copy(lb);
281 : }
282 0 : isl_val_free(v);
283 0 : isl_aff_free(lb);
284 :
285 0 : isl_constraint_free(c);
286 :
287 0 : return better < 0 ? isl_stat_error : isl_stat_ok;
288 : }
289 :
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.
294 : *
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.
300 : */
301 0 : static __isl_give isl_fixed_box *set_dim_extent(__isl_take isl_fixed_box *box,
302 : __isl_keep isl_map *map, int pos)
303 : {
304 : struct isl_size_info info;
305 : isl_bool valid;
306 : isl_ctx *ctx;
307 :
308 0 : if (!box || !map)
309 0 : return isl_fixed_box_free(box);
310 :
311 0 : ctx = isl_map_get_ctx(map);
312 0 : map = isl_map_copy(map);
313 0 : map = isl_map_project_onto(map, isl_dim_out, pos, 1);
314 0 : map = isl_map_compute_divs(map);
315 0 : info.size = isl_val_infty(ctx);
316 0 : info.offset = NULL;
317 0 : info.pos = isl_map_dim(map, isl_dim_in);
318 0 : info.bset = isl_basic_map_wrap(isl_map_simple_hull(map));
319 0 : if (isl_basic_set_foreach_constraint(info.bset,
320 : &compute_size_in_direction, &info) < 0)
321 0 : box = isl_fixed_box_free(box);
322 0 : valid = isl_val_is_int(info.size);
323 0 : if (valid < 0)
324 0 : box = isl_fixed_box_free(box);
325 0 : else if (valid)
326 0 : box = isl_fixed_box_set_valid_extent(box, pos,
327 : info.offset, info.size);
328 : else
329 0 : box = isl_fixed_box_invalidate(box);
330 0 : isl_val_free(info.size);
331 0 : isl_aff_free(info.offset);
332 0 : isl_basic_set_free(info.bset);
333 :
334 0 : return box;
335 : }
336 :
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.
341 : *
342 : * Iterate over the dimensions in the range
343 : * setting the corresponding offset and extent.
344 : */
345 0 : __isl_give isl_fixed_box *isl_map_get_range_simple_fixed_box_hull(
346 : __isl_keep isl_map *map)
347 : {
348 : int i, n;
349 : isl_space *space;
350 : isl_fixed_box *box;
351 :
352 0 : n = isl_map_dim(map, isl_dim_out);
353 0 : space = isl_map_get_space(map);
354 0 : box = isl_fixed_box_init(space);
355 :
356 0 : map = isl_map_detect_equalities(isl_map_copy(map));
357 0 : for (i = 0; i < n; ++i) {
358 : isl_bool valid;
359 :
360 0 : box = set_dim_extent(box, map, i);
361 0 : valid = isl_fixed_box_is_valid(box);
362 0 : if (valid < 0 || !valid)
363 : break;
364 : }
365 0 : isl_map_free(map);
366 :
367 0 : return box;
368 : }
|
