Bug Summary

File:tools/polly/lib/External/isl/isl_range.c
Warning:line 410, column 2
Assigned value is garbage or undefined

Annotated Source Code

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