Coverage Report

Created: 2018-08-20 19:24

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_seq.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2008-2009 Katholieke Universiteit Leuven
3
 * Copyright 2011      INRIA Saclay
4
 *
5
 * Use of this software is governed by the MIT license
6
 *
7
 * Written by Sven Verdoolaege, K.U.Leuven, Departement
8
 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
9
 */
10
11
#include <isl_ctx_private.h>
12
#include <isl_seq.h>
13
14
void isl_seq_clr(isl_int *p, unsigned len)
15
75.2M
{
16
75.2M
  int i;
17
213M
  for (i = 0; i < len; 
++i138M
)
18
138M
    isl_int_set_si(p[i], 0);
19
75.2M
}
20
21
void isl_seq_set_si(isl_int *p, int v, unsigned len)
22
1.65k
{
23
1.65k
  int i;
24
2.53k
  for (i = 0; i < len; 
++i875
)
25
1.65k
    
isl_int_set_si875
(p[i], v);
26
1.65k
}
27
28
void isl_seq_set(isl_int *p, isl_int v, unsigned len)
29
10
{
30
10
  int i;
31
22
  for (i = 0; i < len; 
++i12
)
32
12
    isl_int_set(p[i], v);
33
10
}
34
35
void isl_seq_neg(isl_int *dst, isl_int *src, unsigned len)
36
17.7M
{
37
17.7M
  int i;
38
194M
  for (i = 0; i < len; 
++i176M
)
39
176M
    isl_int_neg(dst[i], src[i]);
40
17.7M
}
41
42
void isl_seq_cpy(isl_int *dst, isl_int *src, unsigned len)
43
61.2M
{
44
61.2M
  int i;
45
631M
  for (i = 0; i < len; 
++i570M
)
46
570M
    isl_int_set(dst[i], src[i]);
47
61.2M
}
48
49
void isl_seq_submul(isl_int *dst, isl_int f, isl_int *src, unsigned len)
50
9.66k
{
51
9.66k
  int i;
52
96.2k
  for (i = 0; i < len; 
++i86.5k
)
53
86.5k
    isl_int_submul(dst[i], f, src[i]);
54
9.66k
}
55
56
void isl_seq_addmul(isl_int *dst, isl_int f, isl_int *src, unsigned len)
57
65.5k
{
58
65.5k
  int i;
59
347k
  for (i = 0; i < len; 
++i281k
)
60
281k
    isl_int_addmul(dst[i], f, src[i]);
61
65.5k
}
62
63
void isl_seq_swp_or_cpy(isl_int *dst, isl_int *src, unsigned len)
64
2.82M
{
65
2.82M
  int i;
66
26.8M
  for (i = 0; i < len; 
++i24.0M
)
67
24.0M
    isl_int_swap_or_set(dst[i], src[i]);
68
2.82M
}
69
70
void isl_seq_scale(isl_int *dst, isl_int *src, isl_int m, unsigned len)
71
4.52M
{
72
4.52M
  int i;
73
15.2M
  for (i = 0; i < len; 
++i10.6M
)
74
10.6M
    isl_int_mul(dst[i], src[i], m);
75
4.52M
}
76
77
void isl_seq_scale_down(isl_int *dst, isl_int *src, isl_int m, unsigned len)
78
3.44M
{
79
3.44M
  int i;
80
42.7M
  for (i = 0; i < len; 
++i39.2M
)
81
39.2M
    isl_int_divexact(dst[i], src[i], m);
82
3.44M
}
83
84
void isl_seq_cdiv_q(isl_int *dst, isl_int *src, isl_int m, unsigned len)
85
3.42k
{
86
3.42k
  int i;
87
12.5k
  for (i = 0; i < len; 
++i9.17k
)
88
9.17k
    isl_int_cdiv_q(dst[i], src[i], m);
89
3.42k
}
90
91
void isl_seq_fdiv_q(isl_int *dst, isl_int *src, isl_int m, unsigned len)
92
117
{
93
117
  int i;
94
877
  for (i = 0; i < len; 
++i760
)
95
760
    isl_int_fdiv_q(dst[i], src[i], m);
96
117
}
97
98
void isl_seq_fdiv_r(isl_int *dst, isl_int *src, isl_int m, unsigned len)
99
689
{
100
689
  int i;
101
4.35k
  for (i = 0; i < len; 
++i3.66k
)
102
3.66k
    isl_int_fdiv_r(dst[i], src[i], m);
103
689
}
104
105
void isl_seq_combine(isl_int *dst, isl_int m1, isl_int *src1,
106
      isl_int m2, isl_int *src2, unsigned len)
107
12.8M
{
108
12.8M
  int i;
109
12.8M
  isl_int tmp;
110
12.8M
111
12.8M
  if (dst == src1 && 
isl_int_is_one12.8M
(m1)) {
112
11.4M
    if (isl_int_is_zero(m2))
113
11.4M
      
return6.45M
;
114
40.8M
    
for (i = 0; 5.02M
i < len;
++i35.8M
)
115
35.8M
      isl_int_addmul(src1[i], m2, src2[i]);
116
5.02M
    return;
117
5.02M
  }
118
1.39M
119
1.39M
  isl_int_init(tmp);
120
11.5M
  for (i = 0; i < len; 
++i10.1M
) {
121
10.1M
    isl_int_mul(tmp, m1, src1[i]);
122
10.1M
    isl_int_addmul(tmp, m2, src2[i]);
123
10.1M
    isl_int_set(dst[i], tmp);
124
10.1M
  }
125
1.39M
  isl_int_clear(tmp);
126
1.39M
}
127
128
/*
129
 * Let d = dst[pos] and s = src[pos]
130
 * dst is replaced by |s| dst - sgn(s)d src
131
 */
132
void isl_seq_elim(isl_int *dst, isl_int *src, unsigned pos, unsigned len,
133
      isl_int *m)
134
2.17M
{
135
2.17M
  isl_int a;
136
2.17M
  isl_int b;
137
2.17M
138
2.17M
  if (isl_int_is_zero(dst[pos]))
139
2.17M
    
return4.88k
;
140
2.16M
141
2.16M
  isl_int_init(a);
142
2.16M
  isl_int_init(b);
143
2.16M
144
2.16M
  isl_int_gcd(a, src[pos], dst[pos]);
145
2.16M
  isl_int_divexact(b, dst[pos], a);
146
2.16M
  if (isl_int_is_pos(src[pos]))
147
2.16M
    
isl_int_neg1.99M
(b, b);
148
2.16M
  isl_int_divexact(a, src[pos], a);
149
2.16M
  isl_int_abs(a, a);
150
2.16M
  isl_seq_combine(dst, a, dst, b, src, len);
151
2.16M
152
2.16M
  if (m)
153
2.16M
    
isl_int_mul20.7k
(*m, *m, a);
154
2.16M
155
2.16M
  isl_int_clear(a);
156
2.16M
  isl_int_clear(b);
157
2.16M
}
158
159
int isl_seq_eq(isl_int *p1, isl_int *p2, unsigned len)
160
13.7M
{
161
13.7M
  int i;
162
106M
  for (i = 0; i < len; 
++i92.2M
)
163
99.1M
    if (isl_int_ne(p1[i], p2[i]))
164
99.1M
      
return 06.88M
;
165
13.7M
  
return 16.89M
;
166
13.7M
}
167
168
int isl_seq_cmp(isl_int *p1, isl_int *p2, unsigned len)
169
2.98M
{
170
2.98M
  int i;
171
2.98M
  int cmp;
172
24.2M
  for (i = 0; i < len; 
++i21.2M
)
173
22.8M
    if ((cmp = isl_int_cmp(p1[i], p2[i])) != 0)
174
1.57M
      return cmp;
175
2.98M
  
return 01.41M
;
176
2.98M
}
177
178
int isl_seq_is_neg(isl_int *p1, isl_int *p2, unsigned len)
179
133k
{
180
133k
  int i;
181
133k
182
756k
  for (i = 0; i < len; 
++i622k
) {
183
719k
    if (isl_int_abs_ne(p1[i], p2[i]))
184
719k
      
return 026.6k
;
185
692k
    if (isl_int_is_zero(p1[i]))
186
692k
      
continue554k
;
187
138k
    if (isl_int_eq(p1[i], p2[i]))
188
138k
      
return 070.2k
;
189
138k
  }
190
133k
  
return 136.9k
;
191
133k
}
192
193
int isl_seq_first_non_zero(isl_int *p, unsigned len)
194
47.0M
{
195
47.0M
  int i;
196
47.0M
197
286M
  for (i = 0; i < len; 
++i239M
)
198
275M
    if (!isl_int_is_zero(p[i]))
199
275M
      
return i35.5M
;
200
47.0M
  
return -111.4M
;
201
47.0M
}
202
203
int isl_seq_last_non_zero(isl_int *p, unsigned len)
204
11.6M
{
205
11.6M
  int i;
206
11.6M
207
67.6M
  for (i = len - 1; i >= 0; 
--i55.9M
)
208
63.3M
    if (!isl_int_is_zero(p[i]))
209
63.3M
      
return i7.38M
;
210
11.6M
  
return -14.25M
;
211
11.6M
}
212
213
void isl_seq_abs_max(isl_int *p, unsigned len, isl_int *max)
214
17.0k
{
215
17.0k
  int i;
216
17.0k
217
17.0k
  isl_int_set_si(*max, 0);
218
17.0k
219
114k
  for (i = 0; i < len; 
++i97.9k
)
220
97.9k
    if (isl_int_abs_gt(p[i], *max))
221
97.9k
      
isl_int_abs17.6k
(*max, p[i]);
222
17.0k
}
223
224
int isl_seq_abs_min_non_zero(isl_int *p, unsigned len)
225
29.6M
{
226
29.6M
  int i, min = isl_seq_first_non_zero(p, len);
227
29.6M
  if (min < 0)
228
1.97M
    return -1;
229
211M
  
for (i = min + 1; 27.6M
i < len;
++i183M
) {
230
183M
    if (isl_int_is_zero(p[i]))
231
183M
      
continue146M
;
232
37.2M
    if (isl_int_abs_lt(p[i], p[min]))
233
37.2M
      
min = i7.01M
;
234
37.2M
  }
235
27.6M
  return min;
236
27.6M
}
237
238
void isl_seq_gcd(isl_int *p, unsigned len, isl_int *gcd)
239
27.7M
{
240
27.7M
  int i, min = isl_seq_abs_min_non_zero(p, len);
241
27.7M
242
27.7M
  if (min < 0) {
243
1.51M
    isl_int_set_si(*gcd, 0);
244
1.51M
    return;
245
1.51M
  }
246
26.2M
  isl_int_abs(*gcd, p[min]);
247
68.0M
  for (i = 0; isl_int_cmp_si(*gcd, 1) > 0 && 
i < len45.4M
;
++i41.8M
) {
248
41.8M
    if (i == min)
249
3.99M
      continue;
250
37.8M
    if (isl_int_is_zero(p[i]))
251
37.8M
      
continue24.3M
;
252
13.5M
    isl_int_gcd(*gcd, *gcd, p[i]);
253
13.5M
  }
254
26.2M
}
255
256
void isl_seq_normalize(struct isl_ctx *ctx, isl_int *p, unsigned len)
257
12.3M
{
258
12.3M
  if (len == 0)
259
0
    return;
260
12.3M
  isl_seq_gcd(p, len, &ctx->normalize_gcd);
261
12.3M
  if (!isl_int_is_zero(ctx->normalize_gcd) &&
262
12.3M
      
!11.6M
isl_int_is_one11.6M
(ctx->normalize_gcd))
263
12.3M
    
isl_seq_scale_down(p, p, ctx->normalize_gcd, len)3.28M
;
264
12.3M
}
265
266
void isl_seq_lcm(isl_int *p, unsigned len, isl_int *lcm)
267
3.27k
{
268
3.27k
  int i;
269
3.27k
270
3.27k
  if (len == 0) {
271
0
    isl_int_set_si(*lcm, 1);
272
0
    return;
273
0
  }
274
3.27k
  isl_int_set(*lcm, p[0]);
275
7.06k
  for (i = 1; i < len; 
++i3.79k
)
276
3.79k
    isl_int_lcm(*lcm, *lcm, p[i]);
277
3.27k
}
278
279
void isl_seq_inner_product(isl_int *p1, isl_int *p2, unsigned len,
280
         isl_int *prod)
281
9.45M
{
282
9.45M
  int i;
283
9.45M
  if (len == 0) {
284
0
    isl_int_set_si(*prod, 0);
285
0
    return;
286
0
  }
287
9.45M
  isl_int_mul(*prod, p1[0], p2[0]);
288
83.0M
  for (i = 1; i < len; 
++i73.6M
)
289
73.6M
    isl_int_addmul(*prod, p1[i], p2[i]);
290
9.45M
}
291
292
uint32_t isl_seq_hash(isl_int *p, unsigned len, uint32_t hash)
293
19.4M
{
294
19.4M
  int i;
295
207M
  for (i = 0; i < len; 
++i187M
) {
296
187M
    if (isl_int_is_zero(p[i]))
297
187M
      
continue162M
;
298
24.9M
    hash *= 16777619;
299
24.9M
    hash ^= (i & 0xFF);
300
24.9M
    hash = isl_int_hash(p[i], hash);
301
24.9M
  }
302
19.4M
  return hash;
303
19.4M
}
304
305
/* Given two affine expressions "p" of length p_len (including the
306
 * denominator and the constant term) and "subs" of length subs_len,
307
 * plug in "subs" for the variable at position "pos".
308
 * The variables of "subs" and "p" are assumed to match up to subs_len,
309
 * but "p" may have additional variables.
310
 * "v" is an initialized isl_int that can be used internally.
311
 *
312
 * In particular, if "p" represents the expression
313
 *
314
 *  (a i + g)/m
315
 *
316
 * with i the variable at position "pos" and "subs" represents the expression
317
 *
318
 *  f/d
319
 *
320
 * then the result represents the expression
321
 *
322
 *  (a f + d g)/(m d)
323
 *
324
 */
325
void isl_seq_substitute(isl_int *p, int pos, isl_int *subs,
326
  int p_len, int subs_len, isl_int v)
327
2.07k
{
328
2.07k
  isl_int_set(v, p[1 + pos]);
329
2.07k
  isl_int_set_si(p[1 + pos], 0);
330
2.07k
  isl_seq_combine(p + 1, subs[0], p + 1, v, subs + 1, subs_len - 1);
331
2.07k
  isl_seq_scale(p + subs_len, p + subs_len, subs[0], p_len - subs_len);
332
2.07k
  isl_int_mul(p[0], p[0], subs[0]);
333
2.07k
}
334
335
uint32_t isl_seq_get_hash(isl_int *p, unsigned len)
336
19.4M
{
337
19.4M
  uint32_t hash = isl_hash_init();
338
19.4M
339
19.4M
  return isl_seq_hash(p, len, hash);
340
19.4M
}
341
342
uint32_t isl_seq_get_hash_bits(isl_int *p, unsigned len, unsigned bits)
343
19.1M
{
344
19.1M
  uint32_t hash;
345
19.1M
346
19.1M
  hash = isl_seq_get_hash(p, len);
347
19.1M
  return isl_hash_bits(hash, bits);
348
19.1M
}
349
350
void isl_seq_dump(isl_int *p, unsigned len)
351
0
{
352
0
  int i;
353
0
354
0
  for (i = 0; i < len; ++i) {
355
0
    if (i)
356
0
      fprintf(stderr, " ");
357
0
    isl_int_print(stderr, p[i], 0);
358
0
  }
359
0
  fprintf(stderr, "\n");
360
0
}