Coverage Report

Created: 2018-07-17 09:43

/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
/* Return the ctx to which "si" belongs.
26
 */
27
isl_ctx *isl_stride_info_get_ctx(__isl_keep isl_stride_info *si)
28
0
{
29
0
  if (!si)
30
0
    return NULL;
31
0
32
0
  return isl_val_get_ctx(si->stride);
33
0
}
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
6.17k
{
40
6.17k
  if (!si)
41
0
    return NULL;
42
6.17k
  isl_val_free(si->stride);
43
6.17k
  isl_aff_free(si->offset);
44
6.17k
  free(si);
45
6.17k
  return NULL;
46
6.17k
}
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
6.17k
{
53
6.17k
  struct isl_stride_info *si;
54
6.17k
55
6.17k
  if (!stride || !offset)
56
0
    goto error;
57
6.17k
  si = isl_alloc_type(isl_val_get_ctx(stride), struct isl_stride_info);
58
6.17k
  if (!si)
59
0
    goto error;
60
6.17k
  si->stride = stride;
61
6.17k
  si->offset = offset;
62
6.17k
  return si;
63
0
error:
64
0
  isl_val_free(stride);
65
0
  isl_aff_free(offset);
66
0
  return NULL;
67
6.17k
}
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
0
{
74
0
  if (!si)
75
0
    return NULL;
76
0
77
0
  return isl_stride_info_alloc(isl_val_copy(si->stride),
78
0
    isl_aff_copy(si->offset));
79
0
}
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
6.17k
{
85
6.17k
  if (!si)
86
0
    return NULL;
87
6.17k
  return isl_val_copy(si->stride);
88
6.17k
}
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
6.17k
{
94
6.17k
  if (!si)
95
0
    return NULL;
96
6.17k
  return isl_aff_copy(si->offset);
97
6.17k
}
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
static isl_stat set_stride(struct isl_detect_stride_data *data,
144
  __isl_take isl_val *stride, __isl_take isl_aff *offset)
145
14
{
146
14
  int pos;
147
14
148
14
  if (!stride || !offset)
149
0
    goto error;
150
14
151
14
  pos = data->pos;
152
14
153
14
  if (data->found) {
154
0
    isl_val *stride2, *a, *b, *g;
155
0
    isl_aff *offset2;
156
0
157
0
    stride2 = data->stride;
158
0
    g = isl_val_gcdext(isl_val_copy(stride), isl_val_copy(stride2),
159
0
          &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
0
166
0
    if (!data->want_offset) {
167
0
      isl_val_free(a);
168
0
      isl_val_free(b);
169
0
    } 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
0
    }
175
0
  }
176
14
177
14
  data->found = 1;
178
14
  data->stride = stride;
179
14
  if (data->want_offset)
180
14
    data->offset = offset;
181
0
  else
182
0
    isl_aff_free(offset);
183
14
  if (!data->stride || (data->want_offset && !data->offset))
184
0
    return isl_stat_error;
185
14
186
14
  return isl_stat_ok;
187
0
error:
188
0
  isl_val_free(stride);
189
0
  isl_aff_free(offset);
190
0
  return isl_stat_error;
191
14
}
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
static isl_stat detect_stride(__isl_take isl_constraint *c, void *user)
228
6.72k
{
229
6.72k
  struct isl_detect_stride_data *data = user;
230
6.72k
  int i, n_div;
231
6.72k
  isl_ctx *ctx;
232
6.72k
  isl_stat r = isl_stat_ok;
233
6.72k
  isl_val *v, *stride, *m;
234
6.72k
  isl_bool is_eq, relevant, has_stride;
235
6.72k
236
6.72k
  is_eq = isl_constraint_is_equality(c);
237
6.72k
  relevant = isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1);
238
6.72k
  if (is_eq < 0 || relevant < 0)
239
0
    goto error;
240
6.72k
  if (!is_eq || 
!relevant6.70k
) {
241
1.39k
    isl_constraint_free(c);
242
1.39k
    return isl_stat_ok;
243
1.39k
  }
244
5.32k
245
5.32k
  ctx = isl_constraint_get_ctx(c);
246
5.32k
  stride = isl_val_zero(ctx);
247
5.32k
  n_div = isl_constraint_dim(c, isl_dim_div);
248
5.40k
  for (i = 0; i < n_div; 
++i75
) {
249
75
    v = isl_constraint_get_coefficient_val(c, isl_dim_div, i);
250
75
    stride = isl_val_gcd(stride, v);
251
75
  }
252
5.32k
253
5.32k
  v = isl_constraint_get_coefficient_val(c, isl_dim_set, data->pos);
254
5.32k
  m = isl_val_gcd(isl_val_copy(stride), isl_val_copy(v));
255
5.32k
  stride = isl_val_div(stride, isl_val_copy(m));
256
5.32k
  v = isl_val_div(v, isl_val_copy(m));
257
5.32k
258
5.32k
  has_stride = isl_val_gt_si(stride, 1);
259
5.32k
  if (has_stride >= 0 && has_stride) {
260
14
    isl_aff *aff;
261
14
    isl_val *gcd, *a, *b;
262
14
263
14
    gcd = isl_val_gcdext(v, isl_val_copy(stride), &a, &b);
264
14
    isl_val_free(gcd);
265
14
    isl_val_free(b);
266
14
267
14
    aff = isl_constraint_get_aff(c);
268
30
    for (i = 0; i < n_div; 
++i16
)
269
16
      aff = isl_aff_set_coefficient_si(aff,
270
16
               isl_dim_div, i, 0);
271
14
    aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0);
272
14
    aff = isl_aff_remove_unused_divs(aff);
273
14
    a = isl_val_neg(a);
274
14
    aff = isl_aff_scale_val(aff, a);
275
14
    aff = isl_aff_scale_down_val(aff, m);
276
14
    r = set_stride(data, stride, aff);
277
5.31k
  } else {
278
5.31k
    isl_val_free(stride);
279
5.31k
    isl_val_free(m);
280
5.31k
    isl_val_free(v);
281
5.31k
  }
282
5.32k
283
5.32k
  isl_constraint_free(c);
284
5.32k
  if (has_stride < 0)
285
0
    return isl_stat_error;
286
5.32k
  return r;
287
0
error:
288
0
  isl_constraint_free(c);
289
0
  return isl_stat_error;
290
5.32k
}
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
static void set_detect_stride(__isl_keep isl_set *set, int pos,
301
  struct isl_detect_stride_data *data)
302
6.17k
{
303
6.17k
  isl_basic_set *hull;
304
6.17k
305
6.17k
  hull = isl_set_affine_hull(isl_set_copy(set));
306
6.17k
307
6.17k
  data->pos = pos;
308
6.17k
  data->found = 0;
309
6.17k
  data->stride = NULL;
310
6.17k
  data->offset = NULL;
311
6.17k
  if (isl_basic_set_foreach_constraint(hull, &detect_stride, data) < 0)
312
0
    goto error;
313
6.17k
314
6.17k
  if (!data->found) {
315
6.16k
    data->stride = isl_val_one(isl_set_get_ctx(set));
316
6.16k
    if (data->want_offset) {
317
6.16k
      isl_space *space;
318
6.16k
      isl_local_space *ls;
319
6.16k
320
6.16k
      space = isl_set_get_space(set);
321
6.16k
      ls = isl_local_space_from_space(space);
322
6.16k
      data->offset = isl_aff_zero_on_domain(ls);
323
6.16k
    }
324
6.16k
  }
325
6.17k
  isl_basic_set_free(hull);
326
6.17k
  return;
327
0
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
0
}
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
__isl_give isl_stride_info *isl_set_get_stride_info(__isl_keep isl_set *set,
337
  int pos)
338
6.17k
{
339
6.17k
  struct isl_detect_stride_data data;
340
6.17k
341
6.17k
  data.want_offset = 1;
342
6.17k
  set_detect_stride(set, pos, &data);
343
6.17k
344
6.17k
  return isl_stride_info_alloc(data.stride, data.offset);
345
6.17k
}
346
347
/* Check if the constraints in "set" imply any stride on set dimension "pos" and
348
 * return this stride.
349
 */
350
__isl_give isl_val *isl_set_get_stride(__isl_keep isl_set *set, int pos)
351
0
{
352
0
  struct isl_detect_stride_data data;
353
0
354
0
  data.want_offset = 0;
355
0
  set_detect_stride(set, pos, &data);
356
0
357
0
  return data.stride;
358
0
}
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
__isl_give isl_stride_info *isl_map_get_range_stride_info(
370
  __isl_keep isl_map *map, int pos)
371
0
{
372
0
  isl_stride_info *si;
373
0
  isl_set *set;
374
0
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
0
}