Line data Source code
1 : /*
2 : * Copyright 2012-2013 Ecole Normale Superieure
3 : *
4 : * Use of this software is governed by the MIT license
5 : *
6 : * Written by Sven Verdoolaege,
7 : * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
8 : */
9 :
10 : #include <isl/val.h>
11 : #include <isl_map_private.h>
12 : #include <isl_aff_private.h>
13 : #include <isl/constraint.h>
14 : #include <isl/set.h>
15 :
16 : /* Stride information about a specific set dimension.
17 : * The values of the set dimension are equal to
18 : * "offset" plus a multiple of "stride".
19 : */
20 : struct isl_stride_info {
21 : isl_val *stride;
22 : isl_aff *offset;
23 : };
24 :
25 : /* Return the ctx to which "si" belongs.
26 : */
27 0 : isl_ctx *isl_stride_info_get_ctx(__isl_keep isl_stride_info *si)
28 : {
29 0 : if (!si)
30 0 : return NULL;
31 :
32 0 : return isl_val_get_ctx(si->stride);
33 : }
34 :
35 : /* Free "si" and return NULL.
36 : */
37 0 : __isl_null isl_stride_info *isl_stride_info_free(
38 : __isl_take isl_stride_info *si)
39 : {
40 0 : if (!si)
41 0 : return NULL;
42 0 : isl_val_free(si->stride);
43 0 : isl_aff_free(si->offset);
44 0 : free(si);
45 0 : return NULL;
46 : }
47 :
48 : /* Construct an isl_stride_info object with given offset and stride.
49 : */
50 0 : __isl_give isl_stride_info *isl_stride_info_alloc(
51 : __isl_take isl_val *stride, __isl_take isl_aff *offset)
52 : {
53 : struct isl_stride_info *si;
54 :
55 0 : if (!stride || !offset)
56 : goto error;
57 0 : si = isl_alloc_type(isl_val_get_ctx(stride), struct isl_stride_info);
58 0 : if (!si)
59 0 : goto error;
60 0 : si->stride = stride;
61 0 : si->offset = offset;
62 0 : return si;
63 : error:
64 0 : isl_val_free(stride);
65 0 : isl_aff_free(offset);
66 0 : return NULL;
67 : }
68 :
69 : /* Make a copy of "si" and return it.
70 : */
71 0 : __isl_give isl_stride_info *isl_stride_info_copy(
72 : __isl_keep isl_stride_info *si)
73 : {
74 0 : if (!si)
75 0 : return NULL;
76 :
77 0 : return isl_stride_info_alloc(isl_val_copy(si->stride),
78 : isl_aff_copy(si->offset));
79 : }
80 :
81 : /* Return the stride of "si".
82 : */
83 0 : __isl_give isl_val *isl_stride_info_get_stride(__isl_keep isl_stride_info *si)
84 : {
85 0 : if (!si)
86 0 : return NULL;
87 0 : return isl_val_copy(si->stride);
88 : }
89 :
90 : /* Return the offset of "si".
91 : */
92 0 : __isl_give isl_aff *isl_stride_info_get_offset(__isl_keep isl_stride_info *si)
93 : {
94 0 : if (!si)
95 0 : return NULL;
96 0 : return isl_aff_copy(si->offset);
97 : }
98 :
99 : /* Information used inside detect_stride.
100 : *
101 : * "pos" is the set dimension at which the stride is being determined.
102 : * "want_offset" is set if the offset should be computed.
103 : * "found" is set if some stride was found already.
104 : * "stride" and "offset" contain the (combined) stride and offset
105 : * found so far and are NULL when "found" is not set.
106 : * If "want_offset" is not set, then "offset" remains NULL.
107 : */
108 : struct isl_detect_stride_data {
109 : int pos;
110 : int want_offset;
111 : int found;
112 : isl_val *stride;
113 : isl_aff *offset;
114 : };
115 :
116 : /* Set the stride and offset of data->pos to the given
117 : * value and expression.
118 : *
119 : * If we had already found a stride before, then the two strides
120 : * are combined into a single stride.
121 : *
122 : * In particular, if the new stride information is of the form
123 : *
124 : * i = f + s (...)
125 : *
126 : * and the old stride information is of the form
127 : *
128 : * i = f2 + s2 (...)
129 : *
130 : * then we compute the extended gcd of s and s2
131 : *
132 : * a s + b s2 = g,
133 : *
134 : * with g = gcd(s,s2), multiply the first equation with t1 = b s2/g
135 : * and the second with t2 = a s1/g.
136 : * This results in
137 : *
138 : * i = (b s2 + a s1)/g i = t1 f + t2 f2 + (s s2)/g (...)
139 : *
140 : * so that t1 f + t2 f2 is the combined offset and (s s2)/g = lcm(s,s2)
141 : * is the combined stride.
142 : */
143 0 : static isl_stat set_stride(struct isl_detect_stride_data *data,
144 : __isl_take isl_val *stride, __isl_take isl_aff *offset)
145 : {
146 : int pos;
147 :
148 0 : if (!stride || !offset)
149 : goto error;
150 :
151 0 : pos = data->pos;
152 :
153 0 : if (data->found) {
154 : isl_val *stride2, *a, *b, *g;
155 : isl_aff *offset2;
156 :
157 0 : stride2 = data->stride;
158 0 : g = isl_val_gcdext(isl_val_copy(stride), isl_val_copy(stride2),
159 : &a, &b);
160 0 : a = isl_val_mul(a, isl_val_copy(stride));
161 0 : a = isl_val_div(a, isl_val_copy(g));
162 0 : stride2 = isl_val_div(stride2, g);
163 0 : b = isl_val_mul(b, isl_val_copy(stride2));
164 0 : stride = isl_val_mul(stride, stride2);
165 :
166 0 : if (!data->want_offset) {
167 0 : isl_val_free(a);
168 0 : isl_val_free(b);
169 : } else {
170 0 : offset2 = data->offset;
171 0 : offset2 = isl_aff_scale_val(offset2, a);
172 0 : offset = isl_aff_scale_val(offset, b);
173 0 : offset = isl_aff_add(offset, offset2);
174 : }
175 : }
176 :
177 0 : data->found = 1;
178 0 : data->stride = stride;
179 0 : if (data->want_offset)
180 0 : data->offset = offset;
181 : else
182 0 : isl_aff_free(offset);
183 0 : if (!data->stride || (data->want_offset && !data->offset))
184 0 : return isl_stat_error;
185 :
186 0 : return isl_stat_ok;
187 : error:
188 0 : isl_val_free(stride);
189 0 : isl_aff_free(offset);
190 0 : return isl_stat_error;
191 : }
192 :
193 : /* Check if constraint "c" imposes any stride on dimension data->pos
194 : * and, if so, update the stride information in "data".
195 : *
196 : * In order to impose a stride on the dimension, "c" needs to be an equality
197 : * and it needs to involve the dimension. Note that "c" may also be
198 : * a div constraint and thus an inequality that we cannot use.
199 : *
200 : * Let c be of the form
201 : *
202 : * h(p) + g * v * i + g * stride * f(alpha) = 0
203 : *
204 : * with h(p) an expression in terms of the parameters and other dimensions
205 : * and f(alpha) an expression in terms of the existentially quantified
206 : * variables.
207 : *
208 : * If "stride" is not zero and not one, then it represents a non-trivial stride
209 : * on "i". We compute a and b such that
210 : *
211 : * a v + b stride = 1
212 : *
213 : * We have
214 : *
215 : * g v i = -h(p) + g stride f(alpha)
216 : *
217 : * a g v i = -a h(p) + g stride f(alpha)
218 : *
219 : * a g v i + b g stride i = -a h(p) + g stride * (...)
220 : *
221 : * g i = -a h(p) + g stride * (...)
222 : *
223 : * i = -a h(p)/g + stride * (...)
224 : *
225 : * The expression "-a h(p)/g" can therefore be used as offset.
226 : */
227 0 : static isl_stat detect_stride(__isl_take isl_constraint *c, void *user)
228 : {
229 0 : struct isl_detect_stride_data *data = user;
230 : int i, n_div;
231 : isl_ctx *ctx;
232 0 : isl_stat r = isl_stat_ok;
233 : isl_val *v, *stride, *m;
234 : isl_bool is_eq, relevant, has_stride;
235 :
236 0 : is_eq = isl_constraint_is_equality(c);
237 0 : relevant = isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1);
238 0 : if (is_eq < 0 || relevant < 0)
239 : goto error;
240 0 : if (!is_eq || !relevant) {
241 0 : isl_constraint_free(c);
242 0 : return isl_stat_ok;
243 : }
244 :
245 0 : ctx = isl_constraint_get_ctx(c);
246 0 : stride = isl_val_zero(ctx);
247 0 : n_div = isl_constraint_dim(c, isl_dim_div);
248 0 : for (i = 0; i < n_div; ++i) {
249 0 : v = isl_constraint_get_coefficient_val(c, isl_dim_div, i);
250 0 : stride = isl_val_gcd(stride, v);
251 : }
252 :
253 0 : v = isl_constraint_get_coefficient_val(c, isl_dim_set, data->pos);
254 0 : m = isl_val_gcd(isl_val_copy(stride), isl_val_copy(v));
255 0 : stride = isl_val_div(stride, isl_val_copy(m));
256 0 : v = isl_val_div(v, isl_val_copy(m));
257 :
258 0 : has_stride = isl_val_gt_si(stride, 1);
259 0 : if (has_stride >= 0 && has_stride) {
260 : isl_aff *aff;
261 : isl_val *gcd, *a, *b;
262 :
263 0 : gcd = isl_val_gcdext(v, isl_val_copy(stride), &a, &b);
264 0 : isl_val_free(gcd);
265 0 : isl_val_free(b);
266 :
267 0 : aff = isl_constraint_get_aff(c);
268 0 : for (i = 0; i < n_div; ++i)
269 0 : aff = isl_aff_set_coefficient_si(aff,
270 : isl_dim_div, i, 0);
271 0 : aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0);
272 0 : aff = isl_aff_remove_unused_divs(aff);
273 0 : a = isl_val_neg(a);
274 0 : aff = isl_aff_scale_val(aff, a);
275 0 : aff = isl_aff_scale_down_val(aff, m);
276 0 : r = set_stride(data, stride, aff);
277 : } else {
278 0 : isl_val_free(stride);
279 0 : isl_val_free(m);
280 0 : isl_val_free(v);
281 : }
282 :
283 0 : isl_constraint_free(c);
284 0 : if (has_stride < 0)
285 0 : return isl_stat_error;
286 0 : return r;
287 : error:
288 0 : isl_constraint_free(c);
289 0 : return isl_stat_error;
290 : }
291 :
292 : /* Check if the constraints in "set" imply any stride on set dimension "pos" and
293 : * store the results in data->stride and data->offset.
294 : *
295 : * In particular, compute the affine hull and then check if
296 : * any of the constraints in the hull impose any stride on the dimension.
297 : * If no such constraint can be found, then the offset is taken
298 : * to be the zero expression and the stride is taken to be one.
299 : */
300 0 : static void set_detect_stride(__isl_keep isl_set *set, int pos,
301 : struct isl_detect_stride_data *data)
302 : {
303 : isl_basic_set *hull;
304 :
305 0 : hull = isl_set_affine_hull(isl_set_copy(set));
306 :
307 0 : data->pos = pos;
308 0 : data->found = 0;
309 0 : data->stride = NULL;
310 0 : data->offset = NULL;
311 0 : if (isl_basic_set_foreach_constraint(hull, &detect_stride, data) < 0)
312 0 : goto error;
313 :
314 0 : if (!data->found) {
315 0 : data->stride = isl_val_one(isl_set_get_ctx(set));
316 0 : if (data->want_offset) {
317 : isl_space *space;
318 : isl_local_space *ls;
319 :
320 0 : space = isl_set_get_space(set);
321 0 : ls = isl_local_space_from_space(space);
322 0 : data->offset = isl_aff_zero_on_domain(ls);
323 : }
324 : }
325 0 : isl_basic_set_free(hull);
326 0 : return;
327 : error:
328 0 : isl_basic_set_free(hull);
329 0 : data->stride = isl_val_free(data->stride);
330 0 : data->offset = isl_aff_free(data->offset);
331 : }
332 :
333 : /* Check if the constraints in "set" imply any stride on set dimension "pos" and
334 : * return the results in the form of an offset and a stride.
335 : */
336 0 : __isl_give isl_stride_info *isl_set_get_stride_info(__isl_keep isl_set *set,
337 : int pos)
338 : {
339 : struct isl_detect_stride_data data;
340 :
341 0 : data.want_offset = 1;
342 0 : set_detect_stride(set, pos, &data);
343 :
344 0 : return isl_stride_info_alloc(data.stride, data.offset);
345 : }
346 :
347 : /* Check if the constraints in "set" imply any stride on set dimension "pos" and
348 : * return this stride.
349 : */
350 0 : __isl_give isl_val *isl_set_get_stride(__isl_keep isl_set *set, int pos)
351 : {
352 : struct isl_detect_stride_data data;
353 :
354 0 : data.want_offset = 0;
355 0 : set_detect_stride(set, pos, &data);
356 :
357 0 : return data.stride;
358 : }
359 :
360 : /* Check if the constraints in "map" imply any stride on output dimension "pos",
361 : * independently of any other output dimensions, and
362 : * return the results in the form of an offset and a stride.
363 : *
364 : * Convert the input to a set with only the input dimensions and
365 : * the single output dimension such that it be passed to
366 : * isl_set_get_stride_info and convert the result back to
367 : * an expression defined over the domain of "map".
368 : */
369 0 : __isl_give isl_stride_info *isl_map_get_range_stride_info(
370 : __isl_keep isl_map *map, int pos)
371 : {
372 : isl_stride_info *si;
373 : isl_set *set;
374 :
375 0 : map = isl_map_copy(map);
376 0 : map = isl_map_project_onto(map, isl_dim_out, pos, 1);
377 0 : pos = isl_map_dim(map, isl_dim_in);
378 0 : set = isl_map_wrap(map);
379 0 : si = isl_set_get_stride_info(set, pos);
380 0 : isl_set_free(set);
381 0 : if (!si)
382 0 : return NULL;
383 0 : si->offset = isl_aff_domain_factor_domain(si->offset);
384 0 : if (!si->offset)
385 0 : return isl_stride_info_free(si);
386 0 : return si;
387 : }
|
