Coverage Report

Created: 2018-04-24 22:41

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_range.c
Line
Count
Source (jump to first uncovered line)
1
#include <isl_ctx_private.h>
2
#include <isl/val.h>
3
#include <isl_constraint_private.h>
4
#include <isl/set.h>
5
#include <isl_polynomial_private.h>
6
#include <isl_morph.h>
7
#include <isl_range.h>
8
9
struct range_data {
10
  struct isl_bound  *bound;
11
  int           *signs;
12
  int     sign;
13
  int     test_monotonicity;
14
  int         monotonicity;
15
  int     tight;
16
  isl_qpolynomial       *poly;
17
  isl_pw_qpolynomial_fold *pwf;
18
  isl_pw_qpolynomial_fold *pwf_tight;
19
};
20
21
static isl_stat propagate_on_domain(__isl_take isl_basic_set *bset,
22
  __isl_take isl_qpolynomial *poly, struct range_data *data);
23
24
/* Check whether the polynomial "poly" has sign "sign" over "bset",
25
 * i.e., if sign == 1, check that the lower bound on the polynomial
26
 * is non-negative and if sign == -1, check that the upper bound on
27
 * the polynomial is non-positive.
28
 */
29
static int has_sign(__isl_keep isl_basic_set *bset,
30
  __isl_keep isl_qpolynomial *poly, int sign, int *signs)
31
7
{
32
7
  struct range_data data_m;
33
7
  unsigned nparam;
34
7
  isl_space *dim;
35
7
  isl_val *opt;
36
7
  int r;
37
7
  enum isl_fold type;
38
7
39
7
  nparam = isl_basic_set_dim(bset, isl_dim_param);
40
7
41
7
  bset = isl_basic_set_copy(bset);
42
7
  poly = isl_qpolynomial_copy(poly);
43
7
44
7
  bset = isl_basic_set_move_dims(bset, isl_dim_set, 0,
45
7
          isl_dim_param, 0, nparam);
46
7
  poly = isl_qpolynomial_move_dims(poly, isl_dim_in, 0,
47
7
          isl_dim_param, 0, nparam);
48
7
49
7
  dim = isl_qpolynomial_get_space(poly);
50
7
  dim = isl_space_params(dim);
51
7
  dim = isl_space_from_domain(dim);
52
7
  dim = isl_space_add_dims(dim, isl_dim_out, 1);
53
7
54
7
  data_m.test_monotonicity = 0;
55
7
  data_m.signs = signs;
56
7
  data_m.sign = -sign;
57
7
  type = data_m.sign < 0 ? 
isl_fold_min5
:
isl_fold_max2
;
58
7
  data_m.pwf = isl_pw_qpolynomial_fold_zero(dim, type);
59
7
  data_m.tight = 0;
60
7
  data_m.pwf_tight = NULL;
61
7
62
7
  if (propagate_on_domain(bset, poly, &data_m) < 0)
63
0
    goto error;
64
7
65
7
  if (sign > 0)
66
5
    opt = isl_pw_qpolynomial_fold_min(data_m.pwf);
67
2
  else
68
2
    opt = isl_pw_qpolynomial_fold_max(data_m.pwf);
69
7
70
7
  if (!opt)
71
0
    r = -1;
72
7
  else if (isl_val_is_nan(opt) ||
73
7
     isl_val_is_infty(opt) ||
74
7
     isl_val_is_neginfty(opt))
75
2
    r = 0;
76
5
  else
77
5
    r = sign * isl_val_sgn(opt) >= 0;
78
7
79
7
  isl_val_free(opt);
80
7
81
7
  return r;
82
0
error:
83
0
  isl_pw_qpolynomial_fold_free(data_m.pwf);
84
0
  return -1;
85
7
}
86
87
/* Return  1 if poly is monotonically increasing in the last set variable,
88
 *        -1 if poly is monotonically decreasing in the last set variable,
89
 *     0 if no conclusion,
90
 *    -2 on error.
91
 *
92
 * We simply check the sign of p(x+1)-p(x)
93
 */
94
static int monotonicity(__isl_keep isl_basic_set *bset,
95
  __isl_keep isl_qpolynomial *poly, struct range_data *data)
96
5
{
97
5
  isl_ctx *ctx;
98
5
  isl_space *dim;
99
5
  isl_qpolynomial *sub = NULL;
100
5
  isl_qpolynomial *diff = NULL;
101
5
  int result = 0;
102
5
  int s;
103
5
  unsigned nvar;
104
5
105
5
  ctx = isl_qpolynomial_get_ctx(poly);
106
5
  dim = isl_qpolynomial_get_domain_space(poly);
107
5
108
5
  nvar = isl_basic_set_dim(bset, isl_dim_set);
109
5
110
5
  sub = isl_qpolynomial_var_on_domain(isl_space_copy(dim), isl_dim_set, nvar - 1);
111
5
  sub = isl_qpolynomial_add(sub,
112
5
    isl_qpolynomial_rat_cst_on_domain(dim, ctx->one, ctx->one));
113
5
114
5
  diff = isl_qpolynomial_substitute(isl_qpolynomial_copy(poly),
115
5
      isl_dim_in, nvar - 1, 1, &sub);
116
5
  diff = isl_qpolynomial_sub(diff, isl_qpolynomial_copy(poly));
117
5
118
5
  s = has_sign(bset, diff, 1, data->signs);
119
5
  if (s < 0)
120
0
    goto error;
121
5
  if (s)
122
3
    result = 1;
123
2
  else {
124
2
    s = has_sign(bset, diff, -1, data->signs);
125
2
    if (s < 0)
126
0
      goto error;
127
2
    if (s)
128
2
      result = -1;
129
2
  }
130
5
131
5
  isl_qpolynomial_free(diff);
132
5
  isl_qpolynomial_free(sub);
133
5
134
5
  return result;
135
0
error:
136
0
  isl_qpolynomial_free(diff);
137
0
  isl_qpolynomial_free(sub);
138
0
  return -2;
139
5
}
140
141
/* Return a positive ("sign" > 0) or negative ("sign" < 0) infinite polynomial
142
 * with domain space "space".
143
 */
144
static __isl_give isl_qpolynomial *signed_infty(__isl_take isl_space *space,
145
  int sign)
146
18
{
147
18
  if (sign > 0)
148
10
    return isl_qpolynomial_infty_on_domain(space);
149
8
  else
150
8
    return isl_qpolynomial_neginfty_on_domain(space);
151
18
}
152
153
static __isl_give isl_qpolynomial *bound2poly(__isl_take isl_constraint *bound,
154
  __isl_take isl_space *space, unsigned pos, int sign)
155
29
{
156
29
  if (!bound)
157
14
    return signed_infty(space, sign);
158
15
  isl_space_free(space);
159
15
  return isl_qpolynomial_from_constraint(bound, isl_dim_set, pos);
160
15
}
161
162
static int bound_is_integer(__isl_take isl_constraint *bound, unsigned pos)
163
0
{
164
0
  isl_int c;
165
0
  int is_int;
166
0
167
0
  if (!bound)
168
0
    return 1;
169
0
170
0
  isl_int_init(c);
171
0
  isl_constraint_get_coefficient(bound, isl_dim_set, pos, &c);
172
0
  is_int = isl_int_is_one(c) || isl_int_is_negone(c);
173
0
  isl_int_clear(c);
174
0
175
0
  return is_int;
176
0
}
177
178
struct isl_fixed_sign_data {
179
  int   *signs;
180
  int   sign;
181
  isl_qpolynomial *poly;
182
};
183
184
/* Add term "term" to data->poly if it has sign data->sign.
185
 * The sign is determined based on the signs of the parameters
186
 * and variables in data->signs.  The integer divisions, if
187
 * any, are assumed to be non-negative.
188
 */
189
static isl_stat collect_fixed_sign_terms(__isl_take isl_term *term, void *user)
190
24
{
191
24
  struct isl_fixed_sign_data *data = (struct isl_fixed_sign_data *)user;
192
24
  isl_int n;
193
24
  int i;
194
24
  int sign;
195
24
  unsigned nparam;
196
24
  unsigned nvar;
197
24
198
24
  if (!term)
199
0
    return isl_stat_error;
200
24
201
24
  nparam = isl_term_dim(term, isl_dim_param);
202
24
  nvar = isl_term_dim(term, isl_dim_set);
203
24
204
24
  isl_int_init(n);
205
24
206
24
  isl_term_get_num(term, &n);
207
24
208
24
  sign = isl_int_sgn(n);
209
24
  for (i = 0; i < nparam; 
++i0
) {
210
0
    if (data->signs[i] > 0)
211
0
      continue;
212
0
    if (isl_term_get_exp(term, isl_dim_param, i) % 2)
213
0
      sign = -sign;
214
0
  }
215
60
  for (i = 0; i < nvar; 
++i36
) {
216
36
    if (data->signs[nparam + i] > 0)
217
22
      continue;
218
14
    if (isl_term_get_exp(term, isl_dim_set, i) % 2)
219
8
      sign = -sign;
220
14
  }
221
24
222
24
  if (sign == data->sign) {
223
12
    isl_qpolynomial *t = isl_qpolynomial_from_term(term);
224
12
225
12
    data->poly = isl_qpolynomial_add(data->poly, t);
226
12
  } else
227
12
    isl_term_free(term);
228
24
229
24
  isl_int_clear(n);
230
24
231
24
  return isl_stat_ok;
232
24
}
233
234
/* Construct and return a polynomial that consists of the terms
235
 * in "poly" that have sign "sign".  The integer divisions, if
236
 * any, are assumed to be non-negative.
237
 */
238
__isl_give isl_qpolynomial *isl_qpolynomial_terms_of_sign(
239
  __isl_keep isl_qpolynomial *poly, int *signs, int sign)
240
24
{
241
24
  isl_space *space;
242
24
  struct isl_fixed_sign_data data = { signs, sign };
243
24
244
24
  space = isl_qpolynomial_get_domain_space(poly);
245
24
  data.poly = isl_qpolynomial_zero_on_domain(space);
246
24
247
24
  if (isl_qpolynomial_foreach_term(poly, collect_fixed_sign_terms, &data) < 0)
248
0
    goto error;
249
24
250
24
  return data.poly;
251
0
error:
252
0
  isl_qpolynomial_free(data.poly);
253
0
  return NULL;
254
24
}
255
256
/* Helper function to add a guarded polynomial to either pwf_tight or pwf,
257
 * depending on whether the result has been determined to be tight.
258
 */
259
static isl_stat add_guarded_poly(__isl_take isl_basic_set *bset,
260
  __isl_take isl_qpolynomial *poly, struct range_data *data)
261
11
{
262
11
  enum isl_fold type = data->sign < 0 ? 
isl_fold_min5
:
isl_fold_max6
;
263
11
  isl_set *set;
264
11
  isl_qpolynomial_fold *fold;
265
11
  isl_pw_qpolynomial_fold *pwf;
266
11
267
11
  bset = isl_basic_set_params(bset);
268
11
  poly = isl_qpolynomial_project_domain_on_params(poly);
269
11
270
11
  fold = isl_qpolynomial_fold_alloc(type, poly);
271
11
  set = isl_set_from_basic_set(bset);
272
11
  pwf = isl_pw_qpolynomial_fold_alloc(type, set, fold);
273
11
  if (data->tight)
274
0
    data->pwf_tight = isl_pw_qpolynomial_fold_fold(
275
0
            data->pwf_tight, pwf);
276
11
  else
277
11
    data->pwf = isl_pw_qpolynomial_fold_fold(data->pwf, pwf);
278
11
279
11
  return isl_stat_ok;
280
11
}
281
282
/* Plug in "sub" for the variable at position "pos" in "poly".
283
 *
284
 * If "sub" is an infinite polynomial and if the variable actually
285
 * appears in "poly", then calling isl_qpolynomial_substitute
286
 * to perform the substitution may result in a NaN result.
287
 * In such cases, return positive or negative infinity instead,
288
 * depending on whether an upper bound or a lower bound is being computed,
289
 * and mark the result as not being tight.
290
 */
291
static __isl_give isl_qpolynomial *plug_in_at_pos(
292
  __isl_take isl_qpolynomial *poly, int pos,
293
  __isl_take isl_qpolynomial *sub, struct range_data *data)
294
29
{
295
29
  isl_bool involves, infty;
296
29
297
29
  involves = isl_qpolynomial_involves_dims(poly, isl_dim_in, pos, 1);
298
29
  if (involves < 0)
299
0
    goto error;
300
29
  if (!involves) {
301
18
    isl_qpolynomial_free(sub);
302
18
    return poly;
303
18
  }
304
11
305
11
  infty = isl_qpolynomial_is_infty(sub);
306
11
  if (infty >= 0 && !infty)
307
8
    infty = isl_qpolynomial_is_neginfty(sub);
308
11
  if (infty < 0)
309
0
    goto error;
310
11
  if (infty) {
311
4
    isl_space *space = isl_qpolynomial_get_domain_space(poly);
312
4
    data->tight = 0;
313
4
    isl_qpolynomial_free(poly);
314
4
    isl_qpolynomial_free(sub);
315
4
    return signed_infty(space, data->sign);
316
4
  }
317
7
318
7
  poly = isl_qpolynomial_substitute(poly, isl_dim_in, pos, 1, &sub);
319
7
  isl_qpolynomial_free(sub);
320
7
321
7
  return poly;
322
0
error:
323
0
  isl_qpolynomial_free(poly);
324
0
  isl_qpolynomial_free(sub);
325
0
  return NULL;
326
7
}
327
328
/* Given a lower and upper bound on the final variable and constraints
329
 * on the remaining variables where these bounds are active,
330
 * eliminate the variable from data->poly based on these bounds.
331
 * If the polynomial has been determined to be monotonic
332
 * in the variable, then simply plug in the appropriate bound.
333
 * If the current polynomial is tight and if this bound is integer,
334
 * then the result is still tight.  In all other cases, the results
335
 * may not be tight.
336
 * Otherwise, plug in the largest bound (in absolute value) in
337
 * the positive terms (if an upper bound is wanted) or the negative terms
338
 * (if a lower bounded is wanted) and the other bound in the other terms.
339
 *
340
 * If all variables have been eliminated, then record the result.
341
 * Ohterwise, recurse on the next variable.
342
 */
343
static isl_stat propagate_on_bound_pair(__isl_take isl_constraint *lower,
344
  __isl_take isl_constraint *upper, __isl_take isl_basic_set *bset,
345
  void *user)
346
17
{
347
17
  struct range_data *data = (struct range_data *)user;
348
17
  int save_tight = data->tight;
349
17
  isl_qpolynomial *poly;
350
17
  isl_stat r;
351
17
  unsigned nvar;
352
17
353
17
  nvar = isl_basic_set_dim(bset, isl_dim_set);
354
17
355
17
  if (data->monotonicity) {
356
5
    isl_qpolynomial *sub;
357
5
    isl_space *dim = isl_qpolynomial_get_domain_space(data->poly);
358
5
    if (data->monotonicity * data->sign > 0) {
359
3
      if (data->tight)
360
0
        data->tight = bound_is_integer(upper, nvar);
361
3
      sub = bound2poly(upper, dim, nvar, 1);
362
3
      isl_constraint_free(lower);
363
3
    } else {
364
2
      if (data->tight)
365
0
        data->tight = bound_is_integer(lower, nvar);
366
2
      sub = bound2poly(lower, dim, nvar, -1);
367
2
      isl_constraint_free(upper);
368
2
    }
369
5
    poly = isl_qpolynomial_copy(data->poly);
370
5
    poly = plug_in_at_pos(poly, nvar, sub, data);
371
5
    poly = isl_qpolynomial_drop_dims(poly, isl_dim_in, nvar, 1);
372
12
  } else {
373
12
    isl_qpolynomial *l, *u;
374
12
    isl_qpolynomial *pos, *neg;
375
12
    isl_space *dim = isl_qpolynomial_get_domain_space(data->poly);
376
12
    unsigned nparam = isl_basic_set_dim(bset, isl_dim_param);
377
12
    int sign = data->sign * data->signs[nparam + nvar];
378
12
379
12
    data->tight = 0;
380
12
381
12
    u = bound2poly(upper, isl_space_copy(dim), nvar, 1);
382
12
    l = bound2poly(lower, dim, nvar, -1);
383
12
384
12
    pos = isl_qpolynomial_terms_of_sign(data->poly, data->signs, sign);
385
12
    neg = isl_qpolynomial_terms_of_sign(data->poly, data->signs, -sign);
386
12
387
12
    pos = plug_in_at_pos(pos, nvar, u, data);
388
12
    neg = plug_in_at_pos(neg, nvar, l, data);
389
12
390
12
    poly = isl_qpolynomial_add(pos, neg);
391
12
    poly = isl_qpolynomial_drop_dims(poly, isl_dim_in, nvar, 1);
392
12
  }
393
17
394
17
  if (isl_basic_set_dim(bset, isl_dim_set) == 0)
395
7
    r = add_guarded_poly(bset, poly, data);
396
10
  else
397
10
    r = propagate_on_domain(bset, poly, data);
398
17
399
17
  data->tight = save_tight;
400
17
401
17
  return r;
402
17
}
403
404
/* Recursively perform range propagation on the polynomial "poly"
405
 * defined over the basic set "bset" and collect the results in "data".
406
 */
407
static isl_stat propagate_on_domain(__isl_take isl_basic_set *bset,
408
  __isl_take isl_qpolynomial *poly, struct range_data *data)
409
21
{
410
21
  isl_ctx *ctx;
411
21
  isl_qpolynomial *save_poly = data->poly;
412
21
  int save_monotonicity = data->monotonicity;
413
21
  unsigned d;
414
21
415
21
  if (!bset || !poly)
416
0
    goto error;
417
21
418
21
  ctx = isl_basic_set_get_ctx(bset);
419
21
  d = isl_basic_set_dim(bset, isl_dim_set);
420
21
  isl_assert(ctx, d >= 1, goto error);
421
21
422
21
  if (isl_qpolynomial_is_cst(poly, NULL, NULL)) {
423
4
    bset = isl_basic_set_project_out(bset, isl_dim_set, 0, d);
424
4
    poly = isl_qpolynomial_drop_dims(poly, isl_dim_in, 0, d);
425
4
    return add_guarded_poly(bset, poly, data);
426
4
  }
427
17
428
17
  if (data->test_monotonicity)
429
5
    data->monotonicity = monotonicity(bset, poly, data);
430
12
  else
431
12
    data->monotonicity = 0;
432
17
  if (data->monotonicity < -1)
433
0
    goto error;
434
17
435
17
  data->poly = poly;
436
17
  if (isl_basic_set_foreach_bound_pair(bset, isl_dim_set, d - 1,
437
17
              &propagate_on_bound_pair, data) < 0)
438
0
    goto error;
439
17
440
17
  isl_basic_set_free(bset);
441
17
  isl_qpolynomial_free(poly);
442
17
  data->monotonicity = save_monotonicity;
443
17
  data->poly = save_poly;
444
17
445
17
  return isl_stat_ok;
446
0
error:
447
0
  isl_basic_set_free(bset);
448
0
  isl_qpolynomial_free(poly);
449
0
  data->monotonicity = save_monotonicity;
450
0
  data->poly = save_poly;
451
0
  return isl_stat_error;
452
17
}
453
454
static isl_stat basic_guarded_poly_bound(__isl_take isl_basic_set *bset,
455
  void *user)
456
4
{
457
4
  struct range_data *data = (struct range_data *)user;
458
4
  isl_ctx *ctx;
459
4
  unsigned nparam = isl_basic_set_dim(bset, isl_dim_param);
460
4
  unsigned dim = isl_basic_set_dim(bset, isl_dim_set);
461
4
  isl_stat r;
462
4
463
4
  data->signs = NULL;
464
4
465
4
  ctx = isl_basic_set_get_ctx(bset);
466
4
  data->signs = isl_alloc_array(ctx, int,
467
4
          isl_basic_set_dim(bset, isl_dim_all));
468
4
469
4
  if (isl_basic_set_dims_get_sign(bset, isl_dim_set, 0, dim,
470
4
          data->signs + nparam) < 0)
471
0
    goto error;
472
4
  if (isl_basic_set_dims_get_sign(bset, isl_dim_param, 0, nparam,
473
4
          data->signs) < 0)
474
0
    goto error;
475
4
476
4
  r = propagate_on_domain(bset, isl_qpolynomial_copy(data->poly), data);
477
4
478
4
  free(data->signs);
479
4
480
4
  return r;
481
0
error:
482
0
  free(data->signs);
483
0
  isl_basic_set_free(bset);
484
0
  return isl_stat_error;
485
4
}
486
487
static isl_stat qpolynomial_bound_on_domain_range(
488
  __isl_take isl_basic_set *bset, __isl_take isl_qpolynomial *poly,
489
  struct range_data *data)
490
1
{
491
1
  unsigned nparam = isl_basic_set_dim(bset, isl_dim_param);
492
1
  unsigned nvar = isl_basic_set_dim(bset, isl_dim_set);
493
1
  isl_set *set = NULL;
494
1
495
1
  if (!bset)
496
0
    goto error;
497
1
498
1
  if (nvar == 0)
499
0
    return add_guarded_poly(bset, poly, data);
500
1
501
1
  set = isl_set_from_basic_set(bset);
502
1
  set = isl_set_split_dims(set, isl_dim_param, 0, nparam);
503
1
  set = isl_set_split_dims(set, isl_dim_set, 0, nvar);
504
1
505
1
  data->poly = poly;
506
1
507
1
  data->test_monotonicity = 1;
508
1
  if (isl_set_foreach_basic_set(set, &basic_guarded_poly_bound, data) < 0)
509
0
    goto error;
510
1
511
1
  isl_set_free(set);
512
1
  isl_qpolynomial_free(poly);
513
1
514
1
  return isl_stat_ok;
515
0
error:
516
0
  isl_set_free(set);
517
0
  isl_qpolynomial_free(poly);
518
0
  return isl_stat_error;
519
1
}
520
521
isl_stat isl_qpolynomial_bound_on_domain_range(__isl_take isl_basic_set *bset,
522
  __isl_take isl_qpolynomial *poly, struct isl_bound *bound)
523
1
{
524
1
  struct range_data data;
525
1
  isl_stat r;
526
1
527
1
  data.pwf = bound->pwf;
528
1
  data.pwf_tight = bound->pwf_tight;
529
1
  data.tight = bound->check_tight;
530
1
  if (bound->type == isl_fold_min)
531
0
    data.sign = -1;
532
1
  else
533
1
    data.sign = 1;
534
1
535
1
  r = qpolynomial_bound_on_domain_range(bset, poly, &data);
536
1
537
1
  bound->pwf = data.pwf;
538
1
  bound->pwf_tight = data.pwf_tight;
539
1
540
1
  return r;
541
1
}