1 #include <isl_ctx_private.h>
2 #include <isl_constraint_private.h>
4 #include <isl_polynomial_private.h>
9 struct isl_bound
*bound
;
12 int test_monotonicity
;
15 isl_qpolynomial
*poly
;
16 isl_pw_qpolynomial_fold
*pwf
;
17 isl_pw_qpolynomial_fold
*pwf_tight
;
20 static int propagate_on_domain(__isl_take isl_basic_set
*bset
,
21 __isl_take isl_qpolynomial
*poly
, struct range_data
*data
);
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.
28 static int has_sign(__isl_keep isl_basic_set
*bset
,
29 __isl_keep isl_qpolynomial
*poly
, int sign
, int *signs
)
31 struct range_data data_m
;
38 nparam
= isl_basic_set_dim(bset
, isl_dim_param
);
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_in
, 0,
46 isl_dim_param
, 0, nparam
);
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);
53 data_m
.test_monotonicity
= 0;
56 type
= data_m
.sign
< 0 ? isl_fold_min
: isl_fold_max
;
57 data_m
.pwf
= isl_pw_qpolynomial_fold_zero(dim
, type
);
59 data_m
.pwf_tight
= NULL
;
61 if (propagate_on_domain(bset
, poly
, &data_m
) < 0)
65 opt
= isl_pw_qpolynomial_fold_min(data_m
.pwf
);
67 opt
= isl_pw_qpolynomial_fold_max(data_m
.pwf
);
71 else if (isl_val_is_nan(opt
) ||
72 isl_val_is_infty(opt
) ||
73 isl_val_is_neginfty(opt
))
76 r
= sign
* isl_val_sgn(opt
) >= 0;
82 isl_pw_qpolynomial_fold_free(data_m
.pwf
);
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,
91 * We simply check the sign of p(x+1)-p(x)
93 static int monotonicity(__isl_keep isl_basic_set
*bset
,
94 __isl_keep isl_qpolynomial
*poly
, struct range_data
*data
)
98 isl_qpolynomial
*sub
= NULL
;
99 isl_qpolynomial
*diff
= NULL
;
104 ctx
= isl_qpolynomial_get_ctx(poly
);
105 dim
= isl_qpolynomial_get_domain_space(poly
);
107 nvar
= isl_basic_set_dim(bset
, isl_dim_set
);
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
));
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
));
117 s
= has_sign(bset
, diff
, 1, data
->signs
);
123 s
= has_sign(bset
, diff
, -1, data
->signs
);
130 isl_qpolynomial_free(diff
);
131 isl_qpolynomial_free(sub
);
135 isl_qpolynomial_free(diff
);
136 isl_qpolynomial_free(sub
);
140 static __isl_give isl_qpolynomial
*bound2poly(__isl_take isl_constraint
*bound
,
141 __isl_take isl_space
*dim
, unsigned pos
, int sign
)
145 return isl_qpolynomial_infty_on_domain(dim
);
147 return isl_qpolynomial_neginfty_on_domain(dim
);
150 return isl_qpolynomial_from_constraint(bound
, isl_dim_set
, pos
);
153 static int bound_is_integer(__isl_take isl_constraint
*bound
, unsigned pos
)
162 isl_constraint_get_coefficient(bound
, isl_dim_set
, pos
, &c
);
163 is_int
= isl_int_is_one(c
) || isl_int_is_negone(c
);
169 struct isl_fixed_sign_data
{
172 isl_qpolynomial
*poly
;
175 /* Add term "term" to data->poly if it has sign data->sign.
176 * The sign is determined based on the signs of the parameters
177 * and variables in data->signs. The integer divisions, if
178 * any, are assumed to be non-negative.
180 static int collect_fixed_sign_terms(__isl_take isl_term
*term
, void *user
)
182 struct isl_fixed_sign_data
*data
= (struct isl_fixed_sign_data
*)user
;
192 nparam
= isl_term_dim(term
, isl_dim_param
);
193 nvar
= isl_term_dim(term
, isl_dim_set
);
197 isl_term_get_num(term
, &n
);
199 sign
= isl_int_sgn(n
);
200 for (i
= 0; i
< nparam
; ++i
) {
201 if (data
->signs
[i
] > 0)
203 if (isl_term_get_exp(term
, isl_dim_param
, i
) % 2)
206 for (i
= 0; i
< nvar
; ++i
) {
207 if (data
->signs
[nparam
+ i
] > 0)
209 if (isl_term_get_exp(term
, isl_dim_set
, i
) % 2)
213 if (sign
== data
->sign
) {
214 isl_qpolynomial
*t
= isl_qpolynomial_from_term(term
);
216 data
->poly
= isl_qpolynomial_add(data
->poly
, t
);
225 /* Construct and return a polynomial that consists of the terms
226 * in "poly" that have sign "sign". The integer divisions, if
227 * any, are assumed to be non-negative.
229 __isl_give isl_qpolynomial
*isl_qpolynomial_terms_of_sign(
230 __isl_keep isl_qpolynomial
*poly
, int *signs
, int sign
)
233 struct isl_fixed_sign_data data
= { signs
, sign
};
235 space
= isl_qpolynomial_get_domain_space(poly
);
236 data
.poly
= isl_qpolynomial_zero_on_domain(space
);
238 if (isl_qpolynomial_foreach_term(poly
, collect_fixed_sign_terms
, &data
) < 0)
243 isl_qpolynomial_free(data
.poly
);
247 /* Helper function to add a guarded polynomial to either pwf_tight or pwf,
248 * depending on whether the result has been determined to be tight.
250 static int add_guarded_poly(__isl_take isl_basic_set
*bset
,
251 __isl_take isl_qpolynomial
*poly
, struct range_data
*data
)
253 enum isl_fold type
= data
->sign
< 0 ? isl_fold_min
: isl_fold_max
;
255 isl_qpolynomial_fold
*fold
;
256 isl_pw_qpolynomial_fold
*pwf
;
258 bset
= isl_basic_set_params(bset
);
259 poly
= isl_qpolynomial_project_domain_on_params(poly
);
261 fold
= isl_qpolynomial_fold_alloc(type
, poly
);
262 set
= isl_set_from_basic_set(bset
);
263 pwf
= isl_pw_qpolynomial_fold_alloc(type
, set
, fold
);
265 data
->pwf_tight
= isl_pw_qpolynomial_fold_fold(
266 data
->pwf_tight
, pwf
);
268 data
->pwf
= isl_pw_qpolynomial_fold_fold(data
->pwf
, pwf
);
273 /* Given a lower and upper bound on the final variable and constraints
274 * on the remaining variables where these bounds are active,
275 * eliminate the variable from data->poly based on these bounds.
276 * If the polynomial has been determined to be monotonic
277 * in the variable, then simply plug in the appropriate bound.
278 * If the current polynomial is tight and if this bound is integer,
279 * then the result is still tight. In all other cases, the results
281 * Otherwise, plug in the largest bound (in absolute value) in
282 * the positive terms (if an upper bound is wanted) or the negative terms
283 * (if a lower bounded is wanted) and the other bound in the other terms.
285 * If all variables have been eliminated, then record the result.
286 * Ohterwise, recurse on the next variable.
288 static int propagate_on_bound_pair(__isl_take isl_constraint
*lower
,
289 __isl_take isl_constraint
*upper
, __isl_take isl_basic_set
*bset
,
292 struct range_data
*data
= (struct range_data
*)user
;
293 int save_tight
= data
->tight
;
294 isl_qpolynomial
*poly
;
298 nvar
= isl_basic_set_dim(bset
, isl_dim_set
);
300 if (data
->monotonicity
) {
301 isl_qpolynomial
*sub
;
302 isl_space
*dim
= isl_qpolynomial_get_domain_space(data
->poly
);
303 if (data
->monotonicity
* data
->sign
> 0) {
305 data
->tight
= bound_is_integer(upper
, nvar
);
306 sub
= bound2poly(upper
, dim
, nvar
, 1);
307 isl_constraint_free(lower
);
310 data
->tight
= bound_is_integer(lower
, nvar
);
311 sub
= bound2poly(lower
, dim
, nvar
, -1);
312 isl_constraint_free(upper
);
314 poly
= isl_qpolynomial_copy(data
->poly
);
315 poly
= isl_qpolynomial_substitute(poly
, isl_dim_in
, nvar
, 1, &sub
);
316 poly
= isl_qpolynomial_drop_dims(poly
, isl_dim_in
, nvar
, 1);
318 isl_qpolynomial_free(sub
);
320 isl_qpolynomial
*l
, *u
;
321 isl_qpolynomial
*pos
, *neg
;
322 isl_space
*dim
= isl_qpolynomial_get_domain_space(data
->poly
);
323 unsigned nparam
= isl_basic_set_dim(bset
, isl_dim_param
);
324 int sign
= data
->sign
* data
->signs
[nparam
+ nvar
];
328 u
= bound2poly(upper
, isl_space_copy(dim
), nvar
, 1);
329 l
= bound2poly(lower
, dim
, nvar
, -1);
331 pos
= isl_qpolynomial_terms_of_sign(data
->poly
, data
->signs
, sign
);
332 neg
= isl_qpolynomial_terms_of_sign(data
->poly
, data
->signs
, -sign
);
334 pos
= isl_qpolynomial_substitute(pos
, isl_dim_in
, nvar
, 1, &u
);
335 neg
= isl_qpolynomial_substitute(neg
, isl_dim_in
, nvar
, 1, &l
);
337 poly
= isl_qpolynomial_add(pos
, neg
);
338 poly
= isl_qpolynomial_drop_dims(poly
, isl_dim_in
, nvar
, 1);
340 isl_qpolynomial_free(u
);
341 isl_qpolynomial_free(l
);
344 if (isl_basic_set_dim(bset
, isl_dim_set
) == 0)
345 r
= add_guarded_poly(bset
, poly
, data
);
347 r
= propagate_on_domain(bset
, poly
, data
);
349 data
->tight
= save_tight
;
354 /* Recursively perform range propagation on the polynomial "poly"
355 * defined over the basic set "bset" and collect the results in "data".
357 static int propagate_on_domain(__isl_take isl_basic_set
*bset
,
358 __isl_take isl_qpolynomial
*poly
, struct range_data
*data
)
361 isl_qpolynomial
*save_poly
= data
->poly
;
362 int save_monotonicity
= data
->monotonicity
;
368 ctx
= isl_basic_set_get_ctx(bset
);
369 d
= isl_basic_set_dim(bset
, isl_dim_set
);
370 isl_assert(ctx
, d
>= 1, goto error
);
372 if (isl_qpolynomial_is_cst(poly
, NULL
, NULL
)) {
373 bset
= isl_basic_set_project_out(bset
, isl_dim_set
, 0, d
);
374 poly
= isl_qpolynomial_drop_dims(poly
, isl_dim_in
, 0, d
);
375 return add_guarded_poly(bset
, poly
, data
);
378 if (data
->test_monotonicity
)
379 data
->monotonicity
= monotonicity(bset
, poly
, data
);
381 data
->monotonicity
= 0;
382 if (data
->monotonicity
< -1)
386 if (isl_basic_set_foreach_bound_pair(bset
, isl_dim_set
, d
- 1,
387 &propagate_on_bound_pair
, data
) < 0)
390 isl_basic_set_free(bset
);
391 isl_qpolynomial_free(poly
);
392 data
->monotonicity
= save_monotonicity
;
393 data
->poly
= save_poly
;
397 isl_basic_set_free(bset
);
398 isl_qpolynomial_free(poly
);
399 data
->monotonicity
= save_monotonicity
;
400 data
->poly
= save_poly
;
404 static int basic_guarded_poly_bound(__isl_take isl_basic_set
*bset
, void *user
)
406 struct range_data
*data
= (struct range_data
*)user
;
408 unsigned nparam
= isl_basic_set_dim(bset
, isl_dim_param
);
409 unsigned dim
= isl_basic_set_dim(bset
, isl_dim_set
);
414 ctx
= isl_basic_set_get_ctx(bset
);
415 data
->signs
= isl_alloc_array(ctx
, int,
416 isl_basic_set_dim(bset
, isl_dim_all
));
418 if (isl_basic_set_dims_get_sign(bset
, isl_dim_set
, 0, dim
,
419 data
->signs
+ nparam
) < 0)
421 if (isl_basic_set_dims_get_sign(bset
, isl_dim_param
, 0, nparam
,
425 r
= propagate_on_domain(bset
, isl_qpolynomial_copy(data
->poly
), data
);
432 isl_basic_set_free(bset
);
436 static int qpolynomial_bound_on_domain_range(__isl_take isl_basic_set
*bset
,
437 __isl_take isl_qpolynomial
*poly
, struct range_data
*data
)
439 unsigned nparam
= isl_basic_set_dim(bset
, isl_dim_param
);
440 unsigned nvar
= isl_basic_set_dim(bset
, isl_dim_set
);
447 return add_guarded_poly(bset
, poly
, data
);
449 set
= isl_set_from_basic_set(bset
);
450 set
= isl_set_split_dims(set
, isl_dim_param
, 0, nparam
);
451 set
= isl_set_split_dims(set
, isl_dim_set
, 0, nvar
);
455 data
->test_monotonicity
= 1;
456 if (isl_set_foreach_basic_set(set
, &basic_guarded_poly_bound
, data
) < 0)
460 isl_qpolynomial_free(poly
);
465 isl_qpolynomial_free(poly
);
469 int isl_qpolynomial_bound_on_domain_range(__isl_take isl_basic_set
*bset
,
470 __isl_take isl_qpolynomial
*poly
, struct isl_bound
*bound
)
472 struct range_data data
;
475 data
.pwf
= bound
->pwf
;
476 data
.pwf_tight
= bound
->pwf_tight
;
477 data
.tight
= bound
->check_tight
;
478 if (bound
->type
== isl_fold_min
)
483 r
= qpolynomial_bound_on_domain_range(bset
, poly
, &data
);
485 bound
->pwf
= data
.pwf
;
486 bound
->pwf_tight
= data
.pwf_tight
;