Coverage Report

Created: 2017-06-23 12:40

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/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
45.9M
{
16
45.9M
  int i;
17
120M
  for (i = 0; 
i < len120M
;
++i74.4M
)
18
74.4M
    isl_int_set_si(p[i], 0);
19
45.9M
}
20
21
void isl_seq_set_si(isl_int *p, int v, unsigned len)
22
1.63k
{
23
1.63k
  int i;
24
2.46k
  for (i = 0; 
i < len2.46k
;
++i826
)
25
826
    isl_int_set_si(p[i], v);
26
1.63k
}
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 < len22
;
++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
10.8M
{
37
10.8M
  int i;
38
97.3M
  for (i = 0; 
i < len97.3M
;
++i86.4M
)
39
86.4M
    isl_int_neg(dst[i], src[i]);
40
10.8M
}
41
42
void isl_seq_cpy(isl_int *dst, isl_int *src, unsigned len)
43
37.3M
{
44
37.3M
  int i;
45
248M
  for (i = 0; 
i < len248M
;
++i211M
)
46
211M
    isl_int_set(dst[i], src[i]);
47
37.3M
}
48
49
void isl_seq_submul(isl_int *dst, isl_int f, isl_int *src, unsigned len)
50
4.08k
{
51
4.08k
  int i;
52
29.1k
  for (i = 0; 
i < len29.1k
;
++i25.0k
)
53
25.0k
    isl_int_submul(dst[i], f, src[i]);
54
4.08k
}
55
56
void isl_seq_addmul(isl_int *dst, isl_int f, isl_int *src, unsigned len)
57
58.2k
{
58
58.2k
  int i;
59
312k
  for (i = 0; 
i < len312k
;
++i254k
)
60
254k
    isl_int_addmul(dst[i], f, src[i]);
61
58.2k
}
62
63
void isl_seq_swp_or_cpy(isl_int *dst, isl_int *src, unsigned len)
64
1.77M
{
65
1.77M
  int i;
66
14.3M
  for (i = 0; 
i < len14.3M
;
++i12.5M
)
67
12.5M
    isl_int_swap_or_set(dst[i], src[i]);
68
1.77M
}
69
70
void isl_seq_scale(isl_int *dst, isl_int *src, isl_int m, unsigned len)
71
2.48M
{
72
2.48M
  int i;
73
8.66M
  for (i = 0; 
i < len8.66M
;
++i6.18M
)
74
6.18M
    isl_int_mul(dst[i], src[i], m);
75
2.48M
}
76
77
void isl_seq_scale_down(isl_int *dst, isl_int *src, isl_int m, unsigned len)
78
4.32M
{
79
4.32M
  int i;
80
58.8M
  for (i = 0; 
i < len58.8M
;
++i54.5M
)
81
54.5M
    isl_int_divexact(dst[i], src[i], m);
82
4.32M
}
83
84
void isl_seq_cdiv_q(isl_int *dst, isl_int *src, isl_int m, unsigned len)
85
3.78k
{
86
3.78k
  int i;
87
15.4k
  for (i = 0; 
i < len15.4k
;
++i11.7k
)
88
11.7k
    isl_int_cdiv_q(dst[i], src[i], m);
89
3.78k
}
90
91
void isl_seq_fdiv_q(isl_int *dst, isl_int *src, isl_int m, unsigned len)
92
86
{
93
86
  int i;
94
593
  for (i = 0; 
i < len593
;
++i507
)
95
507
    isl_int_fdiv_q(dst[i], src[i], m);
96
86
}
97
98
void isl_seq_fdiv_r(isl_int *dst, isl_int *src, isl_int m, unsigned len)
99
631
{
100
631
  int i;
101
4.33k
  for (i = 0; 
i < len4.33k
;
++i3.69k
)
102
3.69k
    isl_int_fdiv_r(dst[i], src[i], m);
103
631
}
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
8.44M
{
108
8.44M
  int i;
109
8.44M
  isl_int tmp;
110
8.44M
111
8.44M
  if (
dst == src1 && 8.44M
isl_int_is_one8.40M
(m1))
{7.20M
112
7.20M
    if (isl_int_is_zero(m2))
113
3.86M
      return;
114
26.5M
    
for (i = 0; 3.34M
i < len26.5M
;
++i23.2M
)
115
23.2M
      isl_int_addmul(src1[i], m2, src2[i]);
116
3.34M
    return;
117
7.20M
  }
118
8.44M
119
1.24M
  
isl_int_init1.24M
(tmp);1.24M
120
9.67M
  for (i = 0; 
i < len9.67M
;
++i8.43M
)
{8.43M
121
8.43M
    isl_int_mul(tmp, m1, src1[i]);
122
8.43M
    isl_int_addmul(tmp, m2, src2[i]);
123
8.43M
    isl_int_set(dst[i], tmp);
124
8.43M
  }
125
1.24M
  isl_int_clear(tmp);
126
1.24M
}
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
1.56M
{
135
1.56M
  isl_int a;
136
1.56M
  isl_int b;
137
1.56M
138
1.56M
  if (isl_int_is_zero(dst[pos]))
139
849
    return;
140
1.56M
141
1.56M
  
isl_int_init1.56M
(a);1.56M
142
1.56M
  isl_int_init(b);
143
1.56M
144
1.56M
  isl_int_gcd(a, src[pos], dst[pos]);
145
1.56M
  isl_int_divexact(b, dst[pos], a);
146
1.56M
  if (isl_int_is_pos(src[pos]))
147
1.46M
    isl_int_neg(b, b);
148
1.56M
  isl_int_divexact(a, src[pos], a);
149
1.56M
  isl_int_abs(a, a);
150
1.56M
  isl_seq_combine(dst, a, dst, b, src, len);
151
1.56M
152
1.56M
  if (m)
153
10.8k
    isl_int_mul(*m, *m, a);
154
1.56M
155
1.56M
  isl_int_clear(a);
156
1.56M
  isl_int_clear(b);
157
1.56M
}
158
159
int isl_seq_eq(isl_int *p1, isl_int *p2, unsigned len)
160
7.71M
{
161
7.71M
  int i;
162
50.4M
  for (i = 0; 
i < len50.4M
;
++i42.7M
)
163
46.3M
    
if (46.3M
isl_int_ne46.3M
(p1[i], p2[i]))
164
3.54M
      return 0;
165
4.16M
  return 1;
166
7.71M
}
167
168
int isl_seq_cmp(isl_int *p1, isl_int *p2, unsigned len)
169
2.52M
{
170
2.52M
  int i;
171
2.52M
  int cmp;
172
20.4M
  for (i = 0; 
i < len20.4M
;
++i17.9M
)
173
19.3M
    
if (19.3M
(cmp = 19.3M
isl_int_cmp19.3M
(p1[i], p2[i])) != 0)
174
1.36M
      return cmp;
175
1.15M
  return 0;
176
2.52M
}
177
178
int isl_seq_is_neg(isl_int *p1, isl_int *p2, unsigned len)
179
83.9k
{
180
83.9k
  int i;
181
83.9k
182
478k
  for (i = 0; 
i < len478k
;
++i394k
)
{454k
183
454k
    if (isl_int_abs_ne(p1[i], p2[i]))
184
18.3k
      return 0;
185
435k
    
if (435k
isl_int_is_zero435k
(p1[i]))
186
339k
      continue;
187
95.8k
    
if (95.8k
isl_int_eq95.8k
(p1[i], p2[i]))
188
40.7k
      return 0;
189
95.8k
  }
190
24.7k
  return 1;
191
83.9k
}
192
193
int isl_seq_first_non_zero(isl_int *p, unsigned len)
194
30.5M
{
195
30.5M
  int i;
196
30.5M
197
114M
  for (i = 0; 
i < len114M
;
++i84.2M
)
198
109M
    
if (109M
!109M
isl_int_is_zero109M
(p[i]))
199
24.7M
      return i;
200
5.84M
  return -1;
201
30.5M
}
202
203
int isl_seq_last_non_zero(isl_int *p, unsigned len)
204
6.39M
{
205
6.39M
  int i;
206
6.39M
207
25.2M
  for (i = len - 1; 
i >= 025.2M
;
--i18.8M
)
208
22.3M
    
if (22.3M
!22.3M
isl_int_is_zero22.3M
(p[i]))
209
3.57M
      return i;
210
2.82M
  return -1;
211
6.39M
}
212
213
void isl_seq_abs_max(isl_int *p, unsigned len, isl_int *max)
214
6.57k
{
215
6.57k
  int i;
216
6.57k
217
6.57k
  isl_int_set_si(*max, 0);
218
6.57k
219
40.1k
  for (i = 0; 
i < len40.1k
;
++i33.6k
)
220
33.6k
    
if (33.6k
isl_int_abs_gt33.6k
(p[i], *max))
221
6.77k
      isl_int_abs(*max, p[i]);
222
6.57k
}
223
224
int isl_seq_abs_min_non_zero(isl_int *p, unsigned len)
225
22.3M
{
226
22.3M
  int i, min = isl_seq_first_non_zero(p, len);
227
22.3M
  if (min < 0)
228
1.22M
    return -1;
229
166M
  
for (i = min + 1; 21.1M
i < len166M
;
++i145M
)
{145M
230
145M
    if (isl_int_is_zero(p[i]))
231
95.0M
      continue;
232
50.1M
    
if (50.1M
isl_int_abs_lt50.1M
(p[i], p[min]))
233
10.0M
      min = i;
234
50.1M
  }
235
21.1M
  return min;
236
22.3M
}
237
238
void isl_seq_gcd(isl_int *p, unsigned len, isl_int *gcd)
239
21.2M
{
240
21.2M
  int i, min = isl_seq_abs_min_non_zero(p, len);
241
21.2M
242
21.2M
  if (
min < 021.2M
)
{956k
243
956k
    isl_int_set_si(*gcd, 0);
244
956k
    return;
245
956k
  }
246
20.2M
  
isl_int_abs20.2M
(*gcd, p[min]);20.2M
247
79.9M
  for (i = 0; 
isl_int_cmp_si79.9M
(*gcd, 1) > 0 && 79.9M
i < len64.2M
;
++i59.6M
)
{59.6M
248
59.6M
    if (i == min)
249
5.04M
      continue;
250
54.6M
    
if (54.6M
isl_int_is_zero54.6M
(p[i]))
251
27.1M
      continue;
252
27.4M
    
isl_int_gcd27.4M
(*gcd, *gcd, p[i]);27.4M
253
27.4M
  }
254
20.2M
}
255
256
void isl_seq_normalize(struct isl_ctx *ctx, isl_int *p, unsigned len)
257
11.2M
{
258
11.2M
  if (len == 0)
259
0
    return;
260
11.2M
  isl_seq_gcd(p, len, &ctx->normalize_gcd);
261
11.2M
  if (
!11.2M
isl_int_is_zero11.2M
(ctx->normalize_gcd) &&
262
10.7M
      
!10.7M
isl_int_is_one10.7M
(ctx->normalize_gcd))
263
4.17M
    isl_seq_scale_down(p, p, ctx->normalize_gcd, len);
264
11.2M
}
265
266
void isl_seq_lcm(isl_int *p, unsigned len, isl_int *lcm)
267
1.81k
{
268
1.81k
  int i;
269
1.81k
270
1.81k
  if (
len == 01.81k
)
{0
271
0
    isl_int_set_si(*lcm, 1);
272
0
    return;
273
0
  }
274
1.81k
  
isl_int_set1.81k
(*lcm, p[0]);1.81k
275
4.08k
  for (i = 1; 
i < len4.08k
;
++i2.26k
)
276
2.26k
    isl_int_lcm(*lcm, *lcm, p[i]);
277
1.81k
}
278
279
void isl_seq_inner_product(isl_int *p1, isl_int *p2, unsigned len,
280
         isl_int *prod)
281
5.63M
{
282
5.63M
  int i;
283
5.63M
  if (
len == 05.63M
)
{0
284
0
    isl_int_set_si(*prod, 0);
285
0
    return;
286
0
  }
287
5.63M
  
isl_int_mul5.63M
(*prod, p1[0], p2[0]);5.63M
288
44.2M
  for (i = 1; 
i < len44.2M
;
++i38.6M
)
289
38.6M
    isl_int_addmul(*prod, p1[i], p2[i]);
290
5.63M
}
291
292
uint32_t isl_seq_hash(isl_int *p, unsigned len, uint32_t hash)
293
12.2M
{
294
12.2M
  int i;
295
106M
  for (i = 0; 
i < len106M
;
++i94.3M
)
{94.3M
296
94.3M
    if (isl_int_is_zero(p[i]))
297
77.8M
      continue;
298
16.5M
    hash *= 16777619;
299
16.5M
    hash ^= (i & 0xFF);
300
16.5M
    hash = isl_int_hash(p[i], hash);
301
16.5M
  }
302
12.2M
  return hash;
303
12.2M
}
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
622
{
328
622
  isl_int_set(v, p[1 + pos]);
329
622
  isl_int_set_si(p[1 + pos], 0);
330
622
  isl_seq_combine(p + 1, subs[0], p + 1, v, subs + 1, subs_len - 1);
331
622
  isl_seq_scale(p + subs_len, p + subs_len, subs[0], p_len - subs_len);
332
622
  isl_int_mul(p[0], p[0], subs[0]);
333
622
}
334
335
uint32_t isl_seq_get_hash(isl_int *p, unsigned len)
336
12.2M
{
337
12.2M
  uint32_t hash = isl_hash_init();
338
12.2M
339
12.2M
  return isl_seq_hash(p, len, hash);
340
12.2M
}
341
342
uint32_t isl_seq_get_hash_bits(isl_int *p, unsigned len, unsigned bits)
343
12.0M
{
344
12.0M
  uint32_t hash;
345
12.0M
346
12.0M
  hash = isl_seq_get_hash(p, len);
347
12.0M
  return isl_hash_bits(hash, bits);
348
12.0M
}
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 < len0
;
++i0
)
{0
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
}