Coverage Report

Created: 2017-08-21 19:50

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/External/isl/isl_bound.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2010      INRIA Saclay
3
 *
4
 * Use of this software is governed by the MIT license
5
 *
6
 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7
 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
8
 * 91893 Orsay, France 
9
 */
10
11
#include <isl_ctx_private.h>
12
#include <isl_map_private.h>
13
#include <isl_bound.h>
14
#include <isl_bernstein.h>
15
#include <isl_range.h>
16
#include <isl_polynomial_private.h>
17
#include <isl_options_private.h>
18
19
/* Compute a bound on the polynomial defined over the parametric polytope
20
 * using either range propagation or bernstein expansion and
21
 * store the result in bound->pwf and bound->pwf_tight.
22
 * Since bernstein expansion requires bounded domains, we apply
23
 * range propagation on unbounded domains.  Otherwise, we respect the choice
24
 * of the user.
25
 */
26
static isl_stat compressed_guarded_poly_bound(__isl_take isl_basic_set *bset,
27
  __isl_take isl_qpolynomial *poly, void *user)
28
2
{
29
2
  struct isl_bound *bound = (struct isl_bound *)user;
30
2
  int bounded;
31
2
32
2
  if (
!bset || 2
!poly2
)
33
0
    goto error;
34
2
35
2
  
if (2
bset->ctx->opt->bound == 2
ISL_BOUND_RANGE2
)
36
0
    return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
37
2
38
2
  bounded = isl_basic_set_is_bounded(bset);
39
2
  if (bounded < 0)
40
0
    goto error;
41
2
  
if (2
bounded2
)
42
1
    return isl_qpolynomial_bound_on_domain_bernstein(bset, poly, bound);
43
2
  else
44
1
    return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
45
2
error:
46
0
  isl_basic_set_free(bset);
47
0
  isl_qpolynomial_free(poly);
48
2
  return -1;
49
2
}
50
51
static isl_stat unwrapped_guarded_poly_bound(__isl_take isl_basic_set *bset,
52
  __isl_take isl_qpolynomial *poly, void *user)
53
2
{
54
2
  struct isl_bound *bound = (struct isl_bound *)user;
55
2
  isl_pw_qpolynomial_fold *top_pwf;
56
2
  isl_pw_qpolynomial_fold *top_pwf_tight;
57
2
  isl_space *dim;
58
2
  isl_morph *morph;
59
2
  isl_stat r;
60
2
61
2
  bset = isl_basic_set_detect_equalities(bset);
62
2
63
2
  if (!bset)
64
0
    goto error;
65
2
66
2
  
if (2
bset->n_eq == 02
)
67
1
    return compressed_guarded_poly_bound(bset, poly, user);
68
2
69
2
  morph = isl_basic_set_full_compression(bset);
70
1
71
1
  bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
72
1
  poly = isl_qpolynomial_morph_domain(poly, isl_morph_copy(morph));
73
1
74
1
  dim = isl_morph_get_ran_space(morph);
75
1
  dim = isl_space_params(dim);
76
1
77
1
  top_pwf = bound->pwf;
78
1
  top_pwf_tight = bound->pwf_tight;
79
1
80
1
  dim = isl_space_from_domain(dim);
81
1
  dim = isl_space_add_dims(dim, isl_dim_out, 1);
82
1
  bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(dim),
83
1
              bound->type);
84
1
  bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim, bound->type);
85
1
86
1
  r = compressed_guarded_poly_bound(bset, poly, user);
87
1
88
1
  morph = isl_morph_dom_params(morph);
89
1
  morph = isl_morph_ran_params(morph);
90
1
  morph = isl_morph_inverse(morph);
91
1
92
1
  bound->pwf = isl_pw_qpolynomial_fold_morph_domain(bound->pwf,
93
1
              isl_morph_copy(morph));
94
1
  bound->pwf_tight = isl_pw_qpolynomial_fold_morph_domain(
95
1
            bound->pwf_tight, morph);
96
1
97
1
  bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
98
1
  bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
99
1
              bound->pwf_tight);
100
1
101
2
  return r;
102
2
error:
103
0
  isl_basic_set_free(bset);
104
0
  isl_qpolynomial_free(poly);
105
2
  return isl_stat_error;
106
2
}
107
108
static isl_stat guarded_poly_bound(__isl_take isl_basic_set *bset,
109
  __isl_take isl_qpolynomial *poly, void *user)
110
2
{
111
2
  struct isl_bound *bound = (struct isl_bound *)user;
112
2
  isl_space *dim;
113
2
  isl_pw_qpolynomial_fold *top_pwf;
114
2
  isl_pw_qpolynomial_fold *top_pwf_tight;
115
2
  int nparam;
116
2
  int n_in;
117
2
  isl_stat r;
118
2
119
2
  if (!bound->wrapping)
120
1
    return unwrapped_guarded_poly_bound(bset, poly, user);
121
2
122
2
  nparam = isl_space_dim(bound->dim, isl_dim_param);
123
1
  n_in = isl_space_dim(bound->dim, isl_dim_in);
124
1
125
1
  bset = isl_basic_set_move_dims(bset, isl_dim_param, nparam,
126
1
          isl_dim_set, 0, n_in);
127
1
  poly = isl_qpolynomial_move_dims(poly, isl_dim_param, nparam,
128
1
          isl_dim_in, 0, n_in);
129
1
130
1
  dim = isl_basic_set_get_space(bset);
131
1
  dim = isl_space_params(dim);
132
1
133
1
  top_pwf = bound->pwf;
134
1
  top_pwf_tight = bound->pwf_tight;
135
1
136
1
  dim = isl_space_from_domain(dim);
137
1
  dim = isl_space_add_dims(dim, isl_dim_out, 1);
138
1
  bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(dim),
139
1
              bound->type);
140
1
  bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim, bound->type);
141
1
142
1
  r = unwrapped_guarded_poly_bound(bset, poly, user);
143
1
144
1
  bound->pwf = isl_pw_qpolynomial_fold_reset_space(bound->pwf,
145
1
                isl_space_copy(bound->dim));
146
1
  bound->pwf_tight = isl_pw_qpolynomial_fold_reset_space(bound->pwf_tight,
147
1
                isl_space_copy(bound->dim));
148
1
149
1
  bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
150
1
  bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
151
1
              bound->pwf_tight);
152
1
153
2
  return r;
154
2
}
155
156
static isl_stat guarded_qp(__isl_take isl_qpolynomial *qp, void *user)
157
2
{
158
2
  struct isl_bound *bound = (struct isl_bound *)user;
159
2
  isl_stat r;
160
2
161
2
  r = isl_qpolynomial_as_polynomial_on_domain(qp, bound->bset,
162
2
                &guarded_poly_bound, user);
163
2
  isl_qpolynomial_free(qp);
164
2
  return r;
165
2
}
166
167
static isl_stat basic_guarded_fold(__isl_take isl_basic_set *bset, void *user)
168
2
{
169
2
  struct isl_bound *bound = (struct isl_bound *)user;
170
2
  isl_stat r;
171
2
172
2
  bound->bset = bset;
173
2
  r = isl_qpolynomial_fold_foreach_qpolynomial(bound->fold,
174
2
              &guarded_qp, user);
175
2
  isl_basic_set_free(bset);
176
2
  return r;
177
2
}
178
179
static isl_stat guarded_fold(__isl_take isl_set *set,
180
  __isl_take isl_qpolynomial_fold *fold, void *user)
181
2
{
182
2
  struct isl_bound *bound = (struct isl_bound *)user;
183
2
184
2
  if (
!set || 2
!fold2
)
185
0
    goto error;
186
2
187
2
  set = isl_set_make_disjoint(set);
188
2
189
2
  bound->fold = fold;
190
2
  bound->type = isl_qpolynomial_fold_get_type(fold);
191
2
192
2
  if (isl_set_foreach_basic_set(set, &basic_guarded_fold, bound) < 0)
193
0
    goto error;
194
2
195
2
  isl_set_free(set);
196
2
  isl_qpolynomial_fold_free(fold);
197
2
198
2
  return isl_stat_ok;
199
2
error:
200
0
  isl_set_free(set);
201
0
  isl_qpolynomial_fold_free(fold);
202
2
  return isl_stat_error;
203
2
}
204
205
__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
206
  __isl_take isl_pw_qpolynomial_fold *pwf, int *tight)
207
4
{
208
4
  unsigned nvar;
209
4
  struct isl_bound bound;
210
4
  int covers;
211
4
212
4
  if (!pwf)
213
0
    return NULL;
214
4
215
4
  bound.dim = isl_pw_qpolynomial_fold_get_domain_space(pwf);
216
4
217
4
  bound.wrapping = isl_space_is_wrapping(bound.dim);
218
4
  if (bound.wrapping)
219
2
    bound.dim = isl_space_unwrap(bound.dim);
220
4
  nvar = isl_space_dim(bound.dim, isl_dim_out);
221
4
  bound.dim = isl_space_domain(bound.dim);
222
4
  bound.dim = isl_space_from_domain(bound.dim);
223
4
  bound.dim = isl_space_add_dims(bound.dim, isl_dim_out, 1);
224
4
225
4
  if (
nvar == 04
)
{1
226
1
    if (tight)
227
0
      *tight = 1;
228
1
    return isl_pw_qpolynomial_fold_reset_space(pwf, bound.dim);
229
4
  }
230
4
231
3
  
if (3
isl_pw_qpolynomial_fold_is_zero(pwf)3
)
{1
232
1
    enum isl_fold type = pwf->type;
233
1
    isl_pw_qpolynomial_fold_free(pwf);
234
1
    if (tight)
235
0
      *tight = 1;
236
1
    return isl_pw_qpolynomial_fold_zero(bound.dim, type);
237
3
  }
238
3
239
3
  bound.pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
240
2
              pwf->type);
241
2
  bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
242
2
              pwf->type);
243
2
  bound.check_tight = !!tight;
244
2
245
2
  if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,
246
2
              guarded_fold, &bound) < 0)
247
0
    goto error;
248
2
249
2
  covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);
250
2
  if (covers < 0)
251
0
    goto error;
252
2
253
2
  
if (2
tight2
)
254
0
    *tight = covers;
255
2
256
2
  isl_space_free(bound.dim);
257
2
  isl_pw_qpolynomial_fold_free(pwf);
258
2
259
2
  if (
covers2
)
{0
260
0
    isl_pw_qpolynomial_fold_free(bound.pwf);
261
0
    return bound.pwf_tight;
262
2
  }
263
2
264
2
  bound.pwf = isl_pw_qpolynomial_fold_fold(bound.pwf, bound.pwf_tight);
265
2
266
2
  return bound.pwf;
267
2
error:
268
0
  isl_pw_qpolynomial_fold_free(bound.pwf_tight);
269
0
  isl_pw_qpolynomial_fold_free(bound.pwf);
270
0
  isl_pw_qpolynomial_fold_free(pwf);
271
0
  isl_space_free(bound.dim);
272
2
  return NULL;
273
4
}
274
275
__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
276
  __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type, int *tight)
277
4
{
278
4
  isl_pw_qpolynomial_fold *pwf;
279
4
280
4
  pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
281
4
  return isl_pw_qpolynomial_fold_bound(pwf, tight);
282
4
}
283
284
struct isl_union_bound_data {
285
  enum isl_fold type;
286
  int tight;
287
  isl_union_pw_qpolynomial_fold *res;
288
};
289
290
static isl_stat bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)
291
0
{
292
0
  struct isl_union_bound_data *data = user;
293
0
  isl_pw_qpolynomial_fold *pwf;
294
0
295
0
  pwf = isl_pw_qpolynomial_bound(pwqp, data->type,
296
0
          data->tight ? &data->tight : NULL);
297
0
  data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
298
0
                data->res, pwf);
299
0
300
0
  return isl_stat_ok;
301
0
}
302
303
__isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
304
  __isl_take isl_union_pw_qpolynomial *upwqp,
305
  enum isl_fold type, int *tight)
306
0
{
307
0
  isl_space *dim;
308
0
  struct isl_union_bound_data data = { type, 1, NULL };
309
0
310
0
  if (!upwqp)
311
0
    return NULL;
312
0
313
0
  
if (0
!tight0
)
314
0
    data.tight = 0;
315
0
316
0
  dim = isl_union_pw_qpolynomial_get_space(upwqp);
317
0
  data.res = isl_union_pw_qpolynomial_fold_zero(dim, type);
318
0
  if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp,
319
0
                &bound_pw, &data) < 0)
320
0
    goto error;
321
0
322
0
  isl_union_pw_qpolynomial_free(upwqp);
323
0
  if (tight)
324
0
    *tight = data.tight;
325
0
326
0
  return data.res;
327
0
error:
328
0
  isl_union_pw_qpolynomial_free(upwqp);
329
0
  isl_union_pw_qpolynomial_fold_free(data.res);
330
0
  return NULL;
331
0
}