isl_tab_pip.c: find_solutions: fix error handling
[isl.git] / isl_range.c
blob140ca501c2f95505a88aa43ae193f427627f3f62
1 #include <isl_constraint.h>
2 #include <isl_set.h>
3 #include <isl_polynomial_private.h>
4 #include <isl_morph.h>
5 #include <isl_range.h>
7 struct range_data {
8 struct isl_bound *bound;
9 int *signs;
10 int sign;
11 int test_monotonicity;
12 int monotonicity;
13 int tight;
14 isl_qpolynomial *poly;
15 isl_pw_qpolynomial_fold *pwf;
16 isl_pw_qpolynomial_fold *pwf_tight;
19 static int propagate_on_domain(__isl_take isl_basic_set *bset,
20 __isl_take isl_qpolynomial *poly, struct range_data *data);
22 /* Check whether the polynomial "poly" has sign "sign" over "bset",
23 * i.e., if sign == 1, check that the lower bound on the polynomial
24 * is non-negative and if sign == -1, check that the upper bound on
25 * the polynomial is non-positive.
27 static int has_sign(__isl_keep isl_basic_set *bset,
28 __isl_keep isl_qpolynomial *poly, int sign, int *signs)
30 struct range_data data_m;
31 unsigned nvar;
32 unsigned nparam;
33 isl_dim *dim;
34 isl_qpolynomial *opt;
35 int r;
37 nparam = isl_basic_set_dim(bset, isl_dim_param);
38 nvar = isl_basic_set_dim(bset, isl_dim_set);
40 bset = isl_basic_set_copy(bset);
41 poly = isl_qpolynomial_copy(poly);
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_set, 0,
46 isl_dim_param, 0, nparam);
48 dim = isl_qpolynomial_get_dim(poly);
49 dim = isl_dim_drop(dim, isl_dim_set, 0, isl_dim_size(dim, isl_dim_set));
51 data_m.test_monotonicity = 0;
52 data_m.signs = signs;
53 data_m.pwf = isl_pw_qpolynomial_fold_zero(dim);
54 data_m.sign = -sign;
55 data_m.tight = 0;
56 data_m.pwf_tight = NULL;
58 if (propagate_on_domain(bset, poly, &data_m) < 0)
59 goto error;
61 if (sign > 0)
62 opt = isl_pw_qpolynomial_fold_min(data_m.pwf);
63 else
64 opt = isl_pw_qpolynomial_fold_max(data_m.pwf);
66 if (!opt)
67 r = -1;
68 else if (isl_qpolynomial_is_nan(opt) ||
69 isl_qpolynomial_is_infty(opt) ||
70 isl_qpolynomial_is_neginfty(opt))
71 r = 0;
72 else
73 r = sign * isl_qpolynomial_sgn(opt) >= 0;
75 isl_qpolynomial_free(opt);
77 return r;
78 error:
79 isl_pw_qpolynomial_fold_free(data_m.pwf);
80 return -1;
83 /* Return 1 if poly is monotonically increasing in the last set variable,
84 * -1 if poly is monotonically decreasing in the last set variable,
85 * 0 if no conclusion,
86 * -2 on error.
88 * We simply check the sign of p(x+1)-p(x)
90 static int monotonicity(__isl_keep isl_basic_set *bset,
91 __isl_keep isl_qpolynomial *poly, struct range_data *data)
93 isl_ctx *ctx;
94 isl_dim *dim;
95 isl_qpolynomial *sub = NULL;
96 isl_qpolynomial *diff = NULL;
97 int result = 0;
98 int s;
99 unsigned nvar;
101 ctx = isl_qpolynomial_get_ctx(poly);
102 dim = isl_qpolynomial_get_dim(poly);
104 nvar = isl_basic_set_dim(bset, isl_dim_set);
106 sub = isl_qpolynomial_var(isl_dim_copy(dim), isl_dim_set, nvar - 1);
107 sub = isl_qpolynomial_add(sub,
108 isl_qpolynomial_rat_cst(dim, ctx->one, ctx->one));
110 diff = isl_qpolynomial_substitute(isl_qpolynomial_copy(poly),
111 isl_dim_set, nvar - 1, 1, &sub);
112 diff = isl_qpolynomial_sub(diff, isl_qpolynomial_copy(poly));
114 s = has_sign(bset, diff, 1, data->signs);
115 if (s < 0)
116 goto error;
117 if (s)
118 result = 1;
119 else {
120 s = has_sign(bset, diff, -1, data->signs);
121 if (s < 0)
122 goto error;
123 if (s)
124 result = -1;
127 isl_qpolynomial_free(diff);
128 isl_qpolynomial_free(sub);
130 return result;
131 error:
132 isl_qpolynomial_free(diff);
133 isl_qpolynomial_free(sub);
134 return -2;
137 static __isl_give isl_qpolynomial *bound2poly(__isl_take isl_constraint *bound,
138 __isl_take isl_dim *dim, unsigned pos, int sign)
140 if (!bound) {
141 if (sign > 0)
142 return isl_qpolynomial_infty(dim);
143 else
144 return isl_qpolynomial_neginfty(dim);
146 isl_dim_free(dim);
147 return isl_qpolynomial_from_constraint(bound, isl_dim_set, pos);
150 static int bound_is_integer(__isl_take isl_constraint *bound, unsigned pos)
152 isl_int c;
153 int is_int;
155 if (!bound)
156 return 1;
158 isl_int_init(c);
159 isl_constraint_get_coefficient(bound, isl_dim_set, pos, &c);
160 is_int = isl_int_is_one(c) || isl_int_is_negone(c);
161 isl_int_clear(c);
163 return is_int;
166 struct isl_fixed_sign_data {
167 int *signs;
168 int sign;
169 isl_qpolynomial *poly;
172 /* Add term "term" to data->poly if it has sign data->sign.
173 * The sign is determined based on the signs of the parameters
174 * and variables in data->signs.
176 static int collect_fixed_sign_terms(__isl_take isl_term *term, void *user)
178 struct isl_fixed_sign_data *data = (struct isl_fixed_sign_data *)user;
179 isl_int n, d;
180 int i;
181 int sign;
182 unsigned nparam;
183 unsigned nvar;
185 if (!term)
186 return -1;
188 nparam = isl_term_dim(term, isl_dim_param);
189 nvar = isl_term_dim(term, isl_dim_set);
191 isl_assert(isl_term_get_ctx(term), isl_term_dim(term, isl_dim_div) == 0,
192 return -1);
194 isl_int_init(n);
195 isl_int_init(d);
197 isl_term_get_num(term, &n);
198 isl_term_get_den(term, &d);
200 sign = isl_int_sgn(n);
201 for (i = 0; i < nparam; ++i) {
202 if (data->signs[i] > 0)
203 continue;
204 if (isl_term_get_exp(term, isl_dim_param, i) % 2)
205 sign = -sign;
207 for (i = 0; i < nvar; ++i) {
208 if (data->signs[nparam + i] > 0)
209 continue;
210 if (isl_term_get_exp(term, isl_dim_set, i) % 2)
211 sign = -sign;
214 if (sign == data->sign) {
215 isl_qpolynomial *t = isl_qpolynomial_from_term(term);
217 data->poly = isl_qpolynomial_add(data->poly, t);
218 } else
219 isl_term_free(term);
221 isl_int_clear(n);
222 isl_int_clear(d);
224 return 0;
227 /* Construct and return a polynomial that consists of the terms
228 * in "poly" that have sign "sign".
230 static __isl_give isl_qpolynomial *fixed_sign_terms(
231 __isl_keep isl_qpolynomial *poly, int *signs, int sign)
233 struct isl_fixed_sign_data data = { signs, sign };
234 data.poly = isl_qpolynomial_zero(isl_qpolynomial_get_dim(poly));
236 if (isl_qpolynomial_foreach_term(poly, collect_fixed_sign_terms, &data) < 0)
237 goto error;
239 return data.poly;
240 error:
241 isl_qpolynomial_free(data.poly);
242 return NULL;
245 /* Helper function to add a guarded polynomial to either pwf_tight or pwf,
246 * depending on whether the result has been determined to be tight.
248 static int add_guarded_poly(__isl_take isl_basic_set *bset,
249 __isl_take isl_qpolynomial *poly, struct range_data *data)
251 enum isl_fold type = data->sign < 0 ? isl_fold_min : isl_fold_max;
252 isl_set *set;
253 isl_qpolynomial_fold *fold;
254 isl_pw_qpolynomial_fold *pwf;
256 fold = isl_qpolynomial_fold_alloc(type, poly);
257 set = isl_set_from_basic_set(bset);
258 pwf = isl_pw_qpolynomial_fold_alloc(set, fold);
259 if (data->tight)
260 data->pwf_tight = isl_pw_qpolynomial_fold_add(
261 data->pwf_tight, pwf);
262 else
263 data->pwf = isl_pw_qpolynomial_fold_add(data->pwf, pwf);
265 return 0;
268 /* Given a lower and upper bound on the final variable and constraints
269 * on the remaining variables where these bounds are active,
270 * eliminate the variable from data->poly based on these bounds.
271 * If the polynomial has been determined to be monotonic
272 * in the variable, then simply plug in the appropriate bound.
273 * If the current polynomial is tight and if this bound is integer,
274 * then the result is still tight. In all other cases, the results
275 * may not be tight.
276 * Otherwise, plug in the largest bound (in absolute value) in
277 * the positive terms (if an upper bound is wanted) or the negative terms
278 * (if a lower bounded is wanted) and the other bound in the other terms.
280 * If all variables have been eliminated, then record the result.
281 * Ohterwise, recurse on the next variable.
283 static int propagate_on_bound_pair(__isl_take isl_constraint *lower,
284 __isl_take isl_constraint *upper, __isl_take isl_basic_set *bset,
285 void *user)
287 struct range_data *data = (struct range_data *)user;
288 int save_tight = data->tight;
289 isl_qpolynomial *poly;
290 int r;
291 unsigned nvar;
293 nvar = isl_basic_set_dim(bset, isl_dim_set);
295 if (data->monotonicity) {
296 isl_qpolynomial *sub;
297 isl_dim *dim = isl_qpolynomial_get_dim(data->poly);
298 if (data->monotonicity * data->sign > 0) {
299 if (data->tight)
300 data->tight = bound_is_integer(upper, nvar);
301 sub = bound2poly(upper, dim, nvar, 1);
302 isl_constraint_free(lower);
303 } else {
304 if (data->tight)
305 data->tight = bound_is_integer(lower, nvar);
306 sub = bound2poly(lower, dim, nvar, -1);
307 isl_constraint_free(upper);
309 poly = isl_qpolynomial_copy(data->poly);
310 poly = isl_qpolynomial_substitute(poly, isl_dim_set, nvar, 1, &sub);
311 poly = isl_qpolynomial_drop_dims(poly, isl_dim_set, nvar, 1);
313 isl_qpolynomial_free(sub);
314 } else {
315 isl_qpolynomial *l, *u;
316 isl_qpolynomial *pos, *neg;
317 isl_dim *dim = isl_qpolynomial_get_dim(data->poly);
318 unsigned nparam = isl_basic_set_dim(bset, isl_dim_param);
319 int sign = data->sign * data->signs[nparam + nvar];
321 data->tight = 0;
323 u = bound2poly(upper, isl_dim_copy(dim), nvar, 1);
324 l = bound2poly(lower, dim, nvar, -1);
326 pos = fixed_sign_terms(data->poly, data->signs, sign);
327 neg = fixed_sign_terms(data->poly, data->signs, -sign);
329 pos = isl_qpolynomial_substitute(pos, isl_dim_set, nvar, 1, &u);
330 neg = isl_qpolynomial_substitute(neg, isl_dim_set, nvar, 1, &l);
332 poly = isl_qpolynomial_add(pos, neg);
333 poly = isl_qpolynomial_drop_dims(poly, isl_dim_set, nvar, 1);
335 isl_qpolynomial_free(u);
336 isl_qpolynomial_free(l);
339 if (isl_basic_set_dim(bset, isl_dim_set) == 0)
340 r = add_guarded_poly(bset, poly, data);
341 else
342 r = propagate_on_domain(bset, poly, data);
344 data->tight = save_tight;
346 return r;
349 /* Recursively perform range propagation on the polynomial "poly"
350 * defined over the basic set "bset" and collect the results in "data".
352 static int propagate_on_domain(__isl_take isl_basic_set *bset,
353 __isl_take isl_qpolynomial *poly, struct range_data *data)
355 isl_qpolynomial *save_poly = data->poly;
356 int save_monotonicity = data->monotonicity;
357 unsigned d;
359 if (!bset || !poly)
360 goto error;
362 d = isl_basic_set_dim(bset, isl_dim_set);
363 isl_assert(bset->ctx, d >= 1, goto error);
365 if (isl_qpolynomial_is_cst(poly, NULL, NULL)) {
366 bset = isl_basic_set_project_out(bset, isl_dim_set, 0, d);
367 poly = isl_qpolynomial_drop_dims(poly, isl_dim_set, 0, d);
368 return add_guarded_poly(bset, poly, data);
371 if (data->test_monotonicity)
372 data->monotonicity = monotonicity(bset, poly, data);
373 else
374 data->monotonicity = 0;
375 if (data->monotonicity < -1)
376 goto error;
378 data->poly = poly;
379 if (isl_basic_set_foreach_bound_pair(bset, isl_dim_set, d - 1,
380 &propagate_on_bound_pair, data) < 0)
381 goto error;
383 isl_basic_set_free(bset);
384 isl_qpolynomial_free(poly);
385 data->monotonicity = save_monotonicity;
386 data->poly = save_poly;
388 return 0;
389 error:
390 isl_basic_set_free(bset);
391 isl_qpolynomial_free(poly);
392 data->monotonicity = save_monotonicity;
393 data->poly = save_poly;
394 return -1;
397 static int basic_guarded_poly_bound(__isl_take isl_basic_set *bset, void *user)
399 struct range_data *data = (struct range_data *)user;
400 unsigned nparam = isl_basic_set_dim(bset, isl_dim_param);
401 unsigned dim = isl_basic_set_dim(bset, isl_dim_set);
402 int r;
404 data->signs = NULL;
406 data->signs = isl_alloc_array(bset->ctx, int,
407 isl_basic_set_dim(bset, isl_dim_all));
409 if (isl_basic_set_dims_get_sign(bset, isl_dim_set, 0, dim,
410 data->signs + nparam) < 0)
411 goto error;
412 if (isl_basic_set_dims_get_sign(bset, isl_dim_param, 0, nparam,
413 data->signs) < 0)
414 goto error;
416 r = propagate_on_domain(bset, isl_qpolynomial_copy(data->poly), data);
418 free(data->signs);
420 return r;
421 error:
422 free(data->signs);
423 isl_basic_set_free(bset);
424 return -1;
427 static int qpolynomial_bound_on_domain_range(__isl_take isl_basic_set *bset,
428 __isl_take isl_qpolynomial *poly, struct range_data *data)
430 unsigned nparam = isl_basic_set_dim(bset, isl_dim_param);
431 unsigned nvar = isl_basic_set_dim(bset, isl_dim_set);
432 isl_set *set;
434 if (!bset)
435 goto error;
437 if (nvar == 0)
438 return add_guarded_poly(bset, poly, data);
440 set = isl_set_from_basic_set(bset);
441 set = isl_set_split_dims(set, isl_dim_param, 0, nparam);
442 set = isl_set_split_dims(set, isl_dim_set, 0, nvar);
444 data->poly = poly;
446 data->test_monotonicity = 1;
447 if (isl_set_foreach_basic_set(set, &basic_guarded_poly_bound, data) < 0)
448 goto error;
450 isl_set_free(set);
451 isl_qpolynomial_free(poly);
453 return 0;
454 error:
455 isl_set_free(set);
456 isl_qpolynomial_free(poly);
457 return -1;
460 int isl_qpolynomial_bound_on_domain_range(__isl_take isl_basic_set *bset,
461 __isl_take isl_qpolynomial *poly, struct isl_bound *bound)
463 struct range_data data;
464 int r;
466 data.pwf = bound->pwf;
467 data.pwf_tight = bound->pwf_tight;
468 data.tight = bound->check_tight;
469 if (bound->type == isl_fold_min)
470 data.sign = -1;
471 else
472 data.sign = 1;
474 r = qpolynomial_bound_on_domain_range(bset, poly, &data);
476 bound->pwf = data.pwf;
477 bound->pwf_tight = data.pwf_tight;
479 return r;