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 */
20struct isl_stride_info {
21 isl_val *stride;
22 isl_aff *offset;
23};
24
25/* Return the ctx to which "si" belongs.
26 */
27isl_ctx *isl_stride_info_get_ctx(__isl_keep isl_stride_info *si)
28{
29 if (!si)
30 return NULL;
31
32 return isl_val_get_ctx(val: si->stride);
33}
34
35/* Free "si" and return NULL.
36 */
37__isl_null isl_stride_info *isl_stride_info_free(
38 __isl_take isl_stride_info *si)
39{
40 if (!si)
41 return NULL;
42 isl_val_free(v: si->stride);
43 isl_aff_free(aff: si->offset);
44 free(ptr: si);
45 return NULL;
46}
47
48/* Construct an isl_stride_info object with given offset and stride.
49 */
50__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 if (!stride || !offset)
56 goto error;
57 si = isl_alloc_type(isl_val_get_ctx(stride), struct isl_stride_info);
58 if (!si)
59 goto error;
60 si->stride = stride;
61 si->offset = offset;
62 return si;
63error:
64 isl_val_free(v: stride);
65 isl_aff_free(aff: offset);
66 return NULL;
67}
68
69/* Make a copy of "si" and return it.
70 */
71__isl_give isl_stride_info *isl_stride_info_copy(
72 __isl_keep isl_stride_info *si)
73{
74 if (!si)
75 return NULL;
76
77 return isl_stride_info_alloc(stride: isl_val_copy(v: si->stride),
78 offset: isl_aff_copy(aff: si->offset));
79}
80
81/* Return the stride of "si".
82 */
83__isl_give isl_val *isl_stride_info_get_stride(__isl_keep isl_stride_info *si)
84{
85 if (!si)
86 return NULL;
87 return isl_val_copy(v: si->stride);
88}
89
90/* Return the offset of "si".
91 */
92__isl_give isl_aff *isl_stride_info_get_offset(__isl_keep isl_stride_info *si)
93{
94 if (!si)
95 return NULL;
96 return isl_aff_copy(aff: 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 */
108struct 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 */
143static isl_stat set_stride(struct isl_detect_stride_data *data,
144 __isl_take isl_val *stride, __isl_take isl_aff *offset)
145{
146 if (!stride || !offset)
147 goto error;
148
149 if (data->found) {
150 isl_val *stride2, *a, *b, *g;
151 isl_aff *offset2;
152
153 stride2 = data->stride;
154 g = isl_val_gcdext(v1: isl_val_copy(v: stride), v2: isl_val_copy(v: stride2),
155 x: &a, y: &b);
156 a = isl_val_mul(v1: a, v2: isl_val_copy(v: stride));
157 a = isl_val_div(v1: a, v2: isl_val_copy(v: g));
158 stride2 = isl_val_div(v1: stride2, v2: g);
159 b = isl_val_mul(v1: b, v2: isl_val_copy(v: stride2));
160 stride = isl_val_mul(v1: stride, v2: stride2);
161
162 if (!data->want_offset) {
163 isl_val_free(v: a);
164 isl_val_free(v: b);
165 } else {
166 offset2 = data->offset;
167 offset2 = isl_aff_scale_val(aff: offset2, v: a);
168 offset = isl_aff_scale_val(aff: offset, v: b);
169 offset = isl_aff_add(aff1: offset, aff2: offset2);
170 }
171 }
172
173 data->found = 1;
174 data->stride = stride;
175 if (data->want_offset)
176 data->offset = offset;
177 else
178 isl_aff_free(aff: offset);
179 if (!data->stride || (data->want_offset && !data->offset))
180 return isl_stat_error;
181
182 return isl_stat_ok;
183error:
184 isl_val_free(v: stride);
185 isl_aff_free(aff: offset);
186 return isl_stat_error;
187}
188
189/* Check if constraint "c" imposes any stride on dimension data->pos
190 * and, if so, update the stride information in "data".
191 *
192 * In order to impose a stride on the dimension, "c" needs to be an equality
193 * and it needs to involve the dimension. Note that "c" may also be
194 * a div constraint and thus an inequality that we cannot use.
195 *
196 * Let c be of the form
197 *
198 * h(p) + g * v * i + g * stride * f(alpha) = 0
199 *
200 * with h(p) an expression in terms of the parameters and other dimensions
201 * and f(alpha) an expression in terms of the existentially quantified
202 * variables.
203 *
204 * If "stride" is not zero and not one, then it represents a non-trivial stride
205 * on "i". We compute a and b such that
206 *
207 * a v + b stride = 1
208 *
209 * We have
210 *
211 * g v i = -h(p) + g stride f(alpha)
212 *
213 * a g v i = -a h(p) + g stride f(alpha)
214 *
215 * a g v i + b g stride i = -a h(p) + g stride * (...)
216 *
217 * g i = -a h(p) + g stride * (...)
218 *
219 * i = -a h(p)/g + stride * (...)
220 *
221 * The expression "-a h(p)/g" can therefore be used as offset.
222 */
223static isl_stat detect_stride(__isl_take isl_constraint *c, void *user)
224{
225 struct isl_detect_stride_data *data = user;
226 int i;
227 isl_size n_div;
228 isl_ctx *ctx;
229 isl_stat r = isl_stat_ok;
230 isl_val *v, *stride, *m;
231 isl_bool is_eq, relevant, has_stride;
232
233 is_eq = isl_constraint_is_equality(constraint: c);
234 relevant = isl_constraint_involves_dims(constraint: c, type: isl_dim_set, first: data->pos, n: 1);
235 if (is_eq < 0 || relevant < 0)
236 goto error;
237 if (!is_eq || !relevant) {
238 isl_constraint_free(c);
239 return isl_stat_ok;
240 }
241
242 n_div = isl_constraint_dim(constraint: c, type: isl_dim_div);
243 if (n_div < 0)
244 goto error;
245 ctx = isl_constraint_get_ctx(c);
246 stride = isl_val_zero(ctx);
247 for (i = 0; i < n_div; ++i) {
248 v = isl_constraint_get_coefficient_val(constraint: c, type: isl_dim_div, pos: i);
249 stride = isl_val_gcd(v1: stride, v2: v);
250 }
251
252 v = isl_constraint_get_coefficient_val(constraint: c, type: isl_dim_set, pos: data->pos);
253 m = isl_val_gcd(v1: isl_val_copy(v: stride), v2: isl_val_copy(v));
254 stride = isl_val_div(v1: stride, v2: isl_val_copy(v: m));
255 v = isl_val_div(v1: v, v2: isl_val_copy(v: m));
256
257 has_stride = isl_val_gt_si(v: stride, i: 1);
258 if (has_stride >= 0 && has_stride) {
259 isl_aff *aff;
260 isl_val *gcd, *a, *b;
261
262 gcd = isl_val_gcdext(v1: v, v2: isl_val_copy(v: stride), x: &a, y: &b);
263 isl_val_free(v: gcd);
264 isl_val_free(v: b);
265
266 aff = isl_constraint_get_aff(constraint: c);
267 for (i = 0; i < n_div; ++i)
268 aff = isl_aff_set_coefficient_si(aff,
269 type: isl_dim_div, pos: i, v: 0);
270 aff = isl_aff_set_coefficient_si(aff, type: isl_dim_in, pos: data->pos, v: 0);
271 aff = isl_aff_remove_unused_divs(aff);
272 a = isl_val_neg(v: a);
273 aff = isl_aff_scale_val(aff, v: a);
274 aff = isl_aff_scale_down_val(aff, v: m);
275 r = set_stride(data, stride, offset: aff);
276 } else {
277 isl_val_free(v: stride);
278 isl_val_free(v: m);
279 isl_val_free(v);
280 }
281
282 isl_constraint_free(c);
283 if (has_stride < 0)
284 return isl_stat_error;
285 return r;
286error:
287 isl_constraint_free(c);
288 return isl_stat_error;
289}
290
291/* Check if the constraints in "set" imply any stride on set dimension "pos" and
292 * store the results in data->stride and data->offset.
293 *
294 * In particular, compute the affine hull and then check if
295 * any of the constraints in the hull impose any stride on the dimension.
296 * If no such constraint can be found, then the offset is taken
297 * to be the zero expression and the stride is taken to be one.
298 */
299static void set_detect_stride(__isl_keep isl_set *set, int pos,
300 struct isl_detect_stride_data *data)
301{
302 isl_basic_set *hull;
303
304 hull = isl_set_affine_hull(set: isl_set_copy(set));
305
306 data->pos = pos;
307 data->found = 0;
308 data->stride = NULL;
309 data->offset = NULL;
310 if (isl_basic_set_foreach_constraint(bset: hull, fn: &detect_stride, user: data) < 0)
311 goto error;
312
313 if (!data->found) {
314 data->stride = isl_val_one(ctx: isl_set_get_ctx(set));
315 if (data->want_offset) {
316 isl_space *space;
317 isl_local_space *ls;
318
319 space = isl_set_get_space(set);
320 ls = isl_local_space_from_space(space);
321 data->offset = isl_aff_zero_on_domain(ls);
322 }
323 }
324 isl_basic_set_free(bset: hull);
325 return;
326error:
327 isl_basic_set_free(bset: hull);
328 data->stride = isl_val_free(v: data->stride);
329 data->offset = isl_aff_free(aff: data->offset);
330}
331
332/* Check if the constraints in "set" imply any stride on set dimension "pos" and
333 * return the results in the form of an offset and a stride.
334 */
335__isl_give isl_stride_info *isl_set_get_stride_info(__isl_keep isl_set *set,
336 int pos)
337{
338 struct isl_detect_stride_data data;
339
340 data.want_offset = 1;
341 set_detect_stride(set, pos, data: &data);
342
343 return isl_stride_info_alloc(stride: data.stride, offset: data.offset);
344}
345
346/* Check if the constraints in "set" imply any stride on set dimension "pos" and
347 * return this stride.
348 */
349__isl_give isl_val *isl_set_get_stride(__isl_keep isl_set *set, int pos)
350{
351 struct isl_detect_stride_data data;
352
353 data.want_offset = 0;
354 set_detect_stride(set, pos, data: &data);
355
356 return data.stride;
357}
358
359/* Check if the constraints in "map" imply any stride on output dimension "pos",
360 * independently of any other output dimensions, and
361 * return the results in the form of an offset and a stride.
362 *
363 * Convert the input to a set with only the input dimensions and
364 * the single output dimension such that it be passed to
365 * isl_set_get_stride_info and convert the result back to
366 * an expression defined over the domain of "map".
367 */
368__isl_give isl_stride_info *isl_map_get_range_stride_info(
369 __isl_keep isl_map *map, int pos)
370{
371 isl_stride_info *si;
372 isl_set *set;
373 isl_size n_in;
374
375 n_in = isl_map_dim(map, type: isl_dim_in);
376 if (n_in < 0)
377 return NULL;
378 map = isl_map_copy(map);
379 map = isl_map_project_onto(map, type: isl_dim_out, first: pos, n: 1);
380 set = isl_map_wrap(map);
381 si = isl_set_get_stride_info(set, pos: n_in);
382 isl_set_free(set);
383 if (!si)
384 return NULL;
385 si->offset = isl_aff_domain_factor_domain(aff: si->offset);
386 if (!si->offset)
387 return isl_stride_info_free(si);
388 return si;
389}
390

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