Line data Source code
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 0 : static int has_sign(__isl_keep isl_basic_set *bset,
30 : __isl_keep isl_qpolynomial *poly, int sign, int *signs)
31 : {
32 : struct range_data data_m;
33 : unsigned nparam;
34 : isl_space *dim;
35 : isl_val *opt;
36 : int r;
37 : enum isl_fold type;
38 :
39 0 : nparam = isl_basic_set_dim(bset, isl_dim_param);
40 :
41 0 : bset = isl_basic_set_copy(bset);
42 0 : poly = isl_qpolynomial_copy(poly);
43 :
44 0 : bset = isl_basic_set_move_dims(bset, isl_dim_set, 0,
45 : isl_dim_param, 0, nparam);
46 0 : poly = isl_qpolynomial_move_dims(poly, isl_dim_in, 0,
47 : isl_dim_param, 0, nparam);
48 :
49 0 : dim = isl_qpolynomial_get_space(poly);
50 0 : dim = isl_space_params(dim);
51 0 : dim = isl_space_from_domain(dim);
52 0 : dim = isl_space_add_dims(dim, isl_dim_out, 1);
53 :
54 0 : data_m.test_monotonicity = 0;
55 0 : data_m.signs = signs;
56 0 : data_m.sign = -sign;
57 0 : type = data_m.sign < 0 ? isl_fold_min : isl_fold_max;
58 0 : data_m.pwf = isl_pw_qpolynomial_fold_zero(dim, type);
59 0 : data_m.tight = 0;
60 0 : data_m.pwf_tight = NULL;
61 :
62 0 : if (propagate_on_domain(bset, poly, &data_m) < 0)
63 0 : goto error;
64 :
65 0 : if (sign > 0)
66 0 : opt = isl_pw_qpolynomial_fold_min(data_m.pwf);
67 : else
68 0 : opt = isl_pw_qpolynomial_fold_max(data_m.pwf);
69 :
70 0 : if (!opt)
71 0 : r = -1;
72 0 : else if (isl_val_is_nan(opt) ||
73 0 : isl_val_is_infty(opt) ||
74 0 : isl_val_is_neginfty(opt))
75 0 : r = 0;
76 : else
77 0 : r = sign * isl_val_sgn(opt) >= 0;
78 :
79 0 : isl_val_free(opt);
80 :
81 0 : return r;
82 : error:
83 0 : isl_pw_qpolynomial_fold_free(data_m.pwf);
84 0 : return -1;
85 : }
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 0 : static int monotonicity(__isl_keep isl_basic_set *bset,
95 : __isl_keep isl_qpolynomial *poly, struct range_data *data)
96 : {
97 : isl_ctx *ctx;
98 : isl_space *dim;
99 0 : isl_qpolynomial *sub = NULL;
100 0 : isl_qpolynomial *diff = NULL;
101 0 : int result = 0;
102 : int s;
103 : unsigned nvar;
104 :
105 0 : ctx = isl_qpolynomial_get_ctx(poly);
106 0 : dim = isl_qpolynomial_get_domain_space(poly);
107 :
108 0 : nvar = isl_basic_set_dim(bset, isl_dim_set);
109 :
110 0 : sub = isl_qpolynomial_var_on_domain(isl_space_copy(dim), isl_dim_set, nvar - 1);
111 0 : sub = isl_qpolynomial_add(sub,
112 0 : isl_qpolynomial_rat_cst_on_domain(dim, ctx->one, ctx->one));
113 :
114 0 : diff = isl_qpolynomial_substitute(isl_qpolynomial_copy(poly),
115 : isl_dim_in, nvar - 1, 1, &sub);
116 0 : diff = isl_qpolynomial_sub(diff, isl_qpolynomial_copy(poly));
117 :
118 0 : s = has_sign(bset, diff, 1, data->signs);
119 0 : if (s < 0)
120 0 : goto error;
121 0 : if (s)
122 0 : result = 1;
123 : else {
124 0 : s = has_sign(bset, diff, -1, data->signs);
125 0 : if (s < 0)
126 0 : goto error;
127 0 : if (s)
128 0 : result = -1;
129 : }
130 :
131 0 : isl_qpolynomial_free(diff);
132 0 : isl_qpolynomial_free(sub);
133 :
134 0 : return result;
135 : error:
136 0 : isl_qpolynomial_free(diff);
137 0 : isl_qpolynomial_free(sub);
138 0 : return -2;
139 : }
140 :
141 : /* Return a positive ("sign" > 0) or negative ("sign" < 0) infinite polynomial
142 : * with domain space "space".
143 : */
144 0 : static __isl_give isl_qpolynomial *signed_infty(__isl_take isl_space *space,
145 : int sign)
146 : {
147 0 : if (sign > 0)
148 0 : return isl_qpolynomial_infty_on_domain(space);
149 : else
150 0 : return isl_qpolynomial_neginfty_on_domain(space);
151 : }
152 :
153 0 : static __isl_give isl_qpolynomial *bound2poly(__isl_take isl_constraint *bound,
154 : __isl_take isl_space *space, unsigned pos, int sign)
155 : {
156 0 : if (!bound)
157 0 : return signed_infty(space, sign);
158 0 : isl_space_free(space);
159 0 : return isl_qpolynomial_from_constraint(bound, isl_dim_set, pos);
160 : }
161 :
162 0 : static int bound_is_integer(__isl_keep isl_constraint *bound, unsigned pos)
163 : {
164 : isl_int c;
165 : int is_int;
166 :
167 0 : if (!bound)
168 0 : return 1;
169 :
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 :
175 0 : return is_int;
176 : }
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 0 : static isl_stat collect_fixed_sign_terms(__isl_take isl_term *term, void *user)
190 : {
191 0 : struct isl_fixed_sign_data *data = (struct isl_fixed_sign_data *)user;
192 : isl_int n;
193 : int i;
194 : int sign;
195 : unsigned nparam;
196 : unsigned nvar;
197 :
198 0 : if (!term)
199 0 : return isl_stat_error;
200 :
201 0 : nparam = isl_term_dim(term, isl_dim_param);
202 0 : nvar = isl_term_dim(term, isl_dim_set);
203 :
204 0 : isl_int_init(n);
205 :
206 0 : isl_term_get_num(term, &n);
207 :
208 0 : sign = isl_int_sgn(n);
209 0 : for (i = 0; i < nparam; ++i) {
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 : }
215 0 : for (i = 0; i < nvar; ++i) {
216 0 : if (data->signs[nparam + i] > 0)
217 0 : continue;
218 0 : if (isl_term_get_exp(term, isl_dim_set, i) % 2)
219 0 : sign = -sign;
220 : }
221 :
222 0 : if (sign == data->sign) {
223 0 : isl_qpolynomial *t = isl_qpolynomial_from_term(term);
224 :
225 0 : data->poly = isl_qpolynomial_add(data->poly, t);
226 : } else
227 0 : isl_term_free(term);
228 :
229 0 : isl_int_clear(n);
230 :
231 0 : return isl_stat_ok;
232 : }
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 0 : __isl_give isl_qpolynomial *isl_qpolynomial_terms_of_sign(
239 : __isl_keep isl_qpolynomial *poly, int *signs, int sign)
240 : {
241 : isl_space *space;
242 0 : struct isl_fixed_sign_data data = { signs, sign };
243 :
244 0 : space = isl_qpolynomial_get_domain_space(poly);
245 0 : data.poly = isl_qpolynomial_zero_on_domain(space);
246 :
247 0 : if (isl_qpolynomial_foreach_term(poly, collect_fixed_sign_terms, &data) < 0)
248 0 : goto error;
249 :
250 0 : return data.poly;
251 : error:
252 0 : isl_qpolynomial_free(data.poly);
253 0 : return NULL;
254 : }
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 0 : static isl_stat add_guarded_poly(__isl_take isl_basic_set *bset,
260 : __isl_take isl_qpolynomial *poly, struct range_data *data)
261 : {
262 0 : enum isl_fold type = data->sign < 0 ? isl_fold_min : isl_fold_max;
263 : isl_set *set;
264 : isl_qpolynomial_fold *fold;
265 : isl_pw_qpolynomial_fold *pwf;
266 :
267 0 : bset = isl_basic_set_params(bset);
268 0 : poly = isl_qpolynomial_project_domain_on_params(poly);
269 :
270 0 : fold = isl_qpolynomial_fold_alloc(type, poly);
271 0 : set = isl_set_from_basic_set(bset);
272 0 : pwf = isl_pw_qpolynomial_fold_alloc(type, set, fold);
273 0 : if (data->tight)
274 0 : data->pwf_tight = isl_pw_qpolynomial_fold_fold(
275 : data->pwf_tight, pwf);
276 : else
277 0 : data->pwf = isl_pw_qpolynomial_fold_fold(data->pwf, pwf);
278 :
279 0 : return isl_stat_ok;
280 : }
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 0 : 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 : {
295 : isl_bool involves, infty;
296 :
297 0 : involves = isl_qpolynomial_involves_dims(poly, isl_dim_in, pos, 1);
298 0 : if (involves < 0)
299 0 : goto error;
300 0 : if (!involves) {
301 0 : isl_qpolynomial_free(sub);
302 0 : return poly;
303 : }
304 :
305 0 : infty = isl_qpolynomial_is_infty(sub);
306 0 : if (infty >= 0 && !infty)
307 0 : infty = isl_qpolynomial_is_neginfty(sub);
308 0 : if (infty < 0)
309 0 : goto error;
310 0 : if (infty) {
311 0 : isl_space *space = isl_qpolynomial_get_domain_space(poly);
312 0 : data->tight = 0;
313 0 : isl_qpolynomial_free(poly);
314 0 : isl_qpolynomial_free(sub);
315 0 : return signed_infty(space, data->sign);
316 : }
317 :
318 0 : poly = isl_qpolynomial_substitute(poly, isl_dim_in, pos, 1, &sub);
319 0 : isl_qpolynomial_free(sub);
320 :
321 0 : return poly;
322 : error:
323 0 : isl_qpolynomial_free(poly);
324 0 : isl_qpolynomial_free(sub);
325 0 : return NULL;
326 : }
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 0 : 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 : {
347 0 : struct range_data *data = (struct range_data *)user;
348 0 : int save_tight = data->tight;
349 : isl_qpolynomial *poly;
350 : isl_stat r;
351 : unsigned nvar;
352 :
353 0 : nvar = isl_basic_set_dim(bset, isl_dim_set);
354 :
355 0 : if (data->monotonicity) {
356 : isl_qpolynomial *sub;
357 0 : isl_space *dim = isl_qpolynomial_get_domain_space(data->poly);
358 0 : if (data->monotonicity * data->sign > 0) {
359 0 : if (data->tight)
360 0 : data->tight = bound_is_integer(upper, nvar);
361 0 : sub = bound2poly(upper, dim, nvar, 1);
362 0 : isl_constraint_free(lower);
363 : } else {
364 0 : if (data->tight)
365 0 : data->tight = bound_is_integer(lower, nvar);
366 0 : sub = bound2poly(lower, dim, nvar, -1);
367 0 : isl_constraint_free(upper);
368 : }
369 0 : poly = isl_qpolynomial_copy(data->poly);
370 0 : poly = plug_in_at_pos(poly, nvar, sub, data);
371 0 : poly = isl_qpolynomial_drop_dims(poly, isl_dim_in, nvar, 1);
372 : } else {
373 : isl_qpolynomial *l, *u;
374 : isl_qpolynomial *pos, *neg;
375 0 : isl_space *dim = isl_qpolynomial_get_domain_space(data->poly);
376 0 : unsigned nparam = isl_basic_set_dim(bset, isl_dim_param);
377 0 : int sign = data->sign * data->signs[nparam + nvar];
378 :
379 0 : data->tight = 0;
380 :
381 0 : u = bound2poly(upper, isl_space_copy(dim), nvar, 1);
382 0 : l = bound2poly(lower, dim, nvar, -1);
383 :
384 0 : pos = isl_qpolynomial_terms_of_sign(data->poly, data->signs, sign);
385 0 : neg = isl_qpolynomial_terms_of_sign(data->poly, data->signs, -sign);
386 :
387 0 : pos = plug_in_at_pos(pos, nvar, u, data);
388 0 : neg = plug_in_at_pos(neg, nvar, l, data);
389 :
390 0 : poly = isl_qpolynomial_add(pos, neg);
391 0 : poly = isl_qpolynomial_drop_dims(poly, isl_dim_in, nvar, 1);
392 : }
393 :
394 0 : if (isl_basic_set_dim(bset, isl_dim_set) == 0)
395 0 : r = add_guarded_poly(bset, poly, data);
396 : else
397 0 : r = propagate_on_domain(bset, poly, data);
398 :
399 0 : data->tight = save_tight;
400 :
401 0 : return r;
402 : }
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 0 : static isl_stat propagate_on_domain(__isl_take isl_basic_set *bset,
408 : __isl_take isl_qpolynomial *poly, struct range_data *data)
409 : {
410 : isl_ctx *ctx;
411 0 : isl_qpolynomial *save_poly = data->poly;
412 0 : int save_monotonicity = data->monotonicity;
413 : unsigned d;
414 :
415 0 : if (!bset || !poly)
416 : goto error;
417 :
418 0 : ctx = isl_basic_set_get_ctx(bset);
419 0 : d = isl_basic_set_dim(bset, isl_dim_set);
420 0 : isl_assert(ctx, d >= 1, goto error);
421 :
422 0 : if (isl_qpolynomial_is_cst(poly, NULL, NULL)) {
423 0 : bset = isl_basic_set_project_out(bset, isl_dim_set, 0, d);
424 0 : poly = isl_qpolynomial_drop_dims(poly, isl_dim_in, 0, d);
425 0 : return add_guarded_poly(bset, poly, data);
426 : }
427 :
428 0 : if (data->test_monotonicity)
429 0 : data->monotonicity = monotonicity(bset, poly, data);
430 : else
431 0 : data->monotonicity = 0;
432 0 : if (data->monotonicity < -1)
433 0 : goto error;
434 :
435 0 : data->poly = poly;
436 0 : if (isl_basic_set_foreach_bound_pair(bset, isl_dim_set, d - 1,
437 : &propagate_on_bound_pair, data) < 0)
438 0 : goto error;
439 :
440 0 : isl_basic_set_free(bset);
441 0 : isl_qpolynomial_free(poly);
442 0 : data->monotonicity = save_monotonicity;
443 0 : data->poly = save_poly;
444 :
445 0 : return isl_stat_ok;
446 : 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 : }
453 :
454 0 : static isl_stat basic_guarded_poly_bound(__isl_take isl_basic_set *bset,
455 : void *user)
456 : {
457 0 : struct range_data *data = (struct range_data *)user;
458 : isl_ctx *ctx;
459 0 : unsigned nparam = isl_basic_set_dim(bset, isl_dim_param);
460 0 : unsigned dim = isl_basic_set_dim(bset, isl_dim_set);
461 : isl_stat r;
462 :
463 0 : data->signs = NULL;
464 :
465 0 : ctx = isl_basic_set_get_ctx(bset);
466 0 : data->signs = isl_alloc_array(ctx, int,
467 : isl_basic_set_dim(bset, isl_dim_all));
468 :
469 0 : if (isl_basic_set_dims_get_sign(bset, isl_dim_set, 0, dim,
470 0 : data->signs + nparam) < 0)
471 0 : goto error;
472 0 : if (isl_basic_set_dims_get_sign(bset, isl_dim_param, 0, nparam,
473 : data->signs) < 0)
474 0 : goto error;
475 :
476 0 : r = propagate_on_domain(bset, isl_qpolynomial_copy(data->poly), data);
477 :
478 0 : free(data->signs);
479 :
480 0 : return r;
481 : error:
482 0 : free(data->signs);
483 0 : isl_basic_set_free(bset);
484 0 : return isl_stat_error;
485 : }
486 :
487 0 : 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 : {
491 0 : unsigned nparam = isl_basic_set_dim(bset, isl_dim_param);
492 0 : unsigned nvar = isl_basic_set_dim(bset, isl_dim_set);
493 0 : isl_set *set = NULL;
494 :
495 0 : if (!bset)
496 0 : goto error;
497 :
498 0 : if (nvar == 0)
499 0 : return add_guarded_poly(bset, poly, data);
500 :
501 0 : set = isl_set_from_basic_set(bset);
502 0 : set = isl_set_split_dims(set, isl_dim_param, 0, nparam);
503 0 : set = isl_set_split_dims(set, isl_dim_set, 0, nvar);
504 :
505 0 : data->poly = poly;
506 :
507 0 : data->test_monotonicity = 1;
508 0 : if (isl_set_foreach_basic_set(set, &basic_guarded_poly_bound, data) < 0)
509 0 : goto error;
510 :
511 0 : isl_set_free(set);
512 0 : isl_qpolynomial_free(poly);
513 :
514 0 : return isl_stat_ok;
515 : error:
516 0 : isl_set_free(set);
517 0 : isl_qpolynomial_free(poly);
518 0 : return isl_stat_error;
519 : }
520 :
521 0 : 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 : {
524 : struct range_data data;
525 : isl_stat r;
526 :
527 0 : data.pwf = bound->pwf;
528 0 : data.pwf_tight = bound->pwf_tight;
529 0 : data.tight = bound->check_tight;
530 0 : if (bound->type == isl_fold_min)
531 0 : data.sign = -1;
532 : else
533 0 : data.sign = 1;
534 :
535 0 : r = qpolynomial_bound_on_domain_range(bset, poly, &data);
536 :
537 0 : bound->pwf = data.pwf;
538 0 : bound->pwf_tight = data.pwf_tight;
539 :
540 0 : return r;
541 : }
|
