Coverage Report

Created: 2018-05-21 22:49

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