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 isl_stat
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 /* Return a positive ("sign" > 0) or negative ("sign" < 0) infinite polynomial
141 * with domain space "space".
143 static __isl_give isl_qpolynomial
*signed_infty(__isl_take isl_space
*space
,
147 return isl_qpolynomial_infty_on_domain(space
);
149 return isl_qpolynomial_neginfty_on_domain(space
);
152 static __isl_give isl_qpolynomial
*bound2poly(__isl_take isl_constraint
*bound
,
153 __isl_take isl_space
*space
, unsigned pos
, int sign
)
156 return signed_infty(space
, sign
);
157 isl_space_free(space
);
158 return isl_qpolynomial_from_constraint(bound
, isl_dim_set
, pos
);
161 static int bound_is_integer(__isl_take isl_constraint
*bound
, unsigned pos
)
170 isl_constraint_get_coefficient(bound
, isl_dim_set
, pos
, &c
);
171 is_int
= isl_int_is_one(c
) || isl_int_is_negone(c
);
177 struct isl_fixed_sign_data
{
180 isl_qpolynomial
*poly
;
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.
188 static isl_stat
collect_fixed_sign_terms(__isl_take isl_term
*term
, void *user
)
190 struct isl_fixed_sign_data
*data
= (struct isl_fixed_sign_data
*)user
;
198 return isl_stat_error
;
200 nparam
= isl_term_dim(term
, isl_dim_param
);
201 nvar
= isl_term_dim(term
, isl_dim_set
);
205 isl_term_get_num(term
, &n
);
207 sign
= isl_int_sgn(n
);
208 for (i
= 0; i
< nparam
; ++i
) {
209 if (data
->signs
[i
] > 0)
211 if (isl_term_get_exp(term
, isl_dim_param
, i
) % 2)
214 for (i
= 0; i
< nvar
; ++i
) {
215 if (data
->signs
[nparam
+ i
] > 0)
217 if (isl_term_get_exp(term
, isl_dim_set
, i
) % 2)
221 if (sign
== data
->sign
) {
222 isl_qpolynomial
*t
= isl_qpolynomial_from_term(term
);
224 data
->poly
= isl_qpolynomial_add(data
->poly
, t
);
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.
237 __isl_give isl_qpolynomial
*isl_qpolynomial_terms_of_sign(
238 __isl_keep isl_qpolynomial
*poly
, int *signs
, int sign
)
241 struct isl_fixed_sign_data data
= { signs
, sign
};
243 space
= isl_qpolynomial_get_domain_space(poly
);
244 data
.poly
= isl_qpolynomial_zero_on_domain(space
);
246 if (isl_qpolynomial_foreach_term(poly
, collect_fixed_sign_terms
, &data
) < 0)
251 isl_qpolynomial_free(data
.poly
);
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.
258 static isl_stat
add_guarded_poly(__isl_take isl_basic_set
*bset
,
259 __isl_take isl_qpolynomial
*poly
, struct range_data
*data
)
261 enum isl_fold type
= data
->sign
< 0 ? isl_fold_min
: isl_fold_max
;
263 isl_qpolynomial_fold
*fold
;
264 isl_pw_qpolynomial_fold
*pwf
;
266 bset
= isl_basic_set_params(bset
);
267 poly
= isl_qpolynomial_project_domain_on_params(poly
);
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
);
273 data
->pwf_tight
= isl_pw_qpolynomial_fold_fold(
274 data
->pwf_tight
, pwf
);
276 data
->pwf
= isl_pw_qpolynomial_fold_fold(data
->pwf
, pwf
);
281 /* Plug in "sub" for the variable at position "pos" in "poly".
283 static __isl_give isl_qpolynomial
*plug_in_at_pos(
284 __isl_take isl_qpolynomial
*poly
, int pos
,
285 __isl_take isl_qpolynomial
*sub
)
287 poly
= isl_qpolynomial_substitute(poly
, isl_dim_in
, pos
, 1, &sub
);
288 isl_qpolynomial_free(sub
);
293 /* Given a lower and upper bound on the final variable and constraints
294 * on the remaining variables where these bounds are active,
295 * eliminate the variable from data->poly based on these bounds.
296 * If the polynomial has been determined to be monotonic
297 * in the variable, then simply plug in the appropriate bound.
298 * If the current polynomial is tight and if this bound is integer,
299 * then the result is still tight. In all other cases, the results
301 * Otherwise, plug in the largest bound (in absolute value) in
302 * the positive terms (if an upper bound is wanted) or the negative terms
303 * (if a lower bounded is wanted) and the other bound in the other terms.
305 * If all variables have been eliminated, then record the result.
306 * Ohterwise, recurse on the next variable.
308 static isl_stat
propagate_on_bound_pair(__isl_take isl_constraint
*lower
,
309 __isl_take isl_constraint
*upper
, __isl_take isl_basic_set
*bset
,
312 struct range_data
*data
= (struct range_data
*)user
;
313 int save_tight
= data
->tight
;
314 isl_qpolynomial
*poly
;
318 nvar
= isl_basic_set_dim(bset
, isl_dim_set
);
320 if (data
->monotonicity
) {
321 isl_qpolynomial
*sub
;
322 isl_space
*dim
= isl_qpolynomial_get_domain_space(data
->poly
);
323 if (data
->monotonicity
* data
->sign
> 0) {
325 data
->tight
= bound_is_integer(upper
, nvar
);
326 sub
= bound2poly(upper
, dim
, nvar
, 1);
327 isl_constraint_free(lower
);
330 data
->tight
= bound_is_integer(lower
, nvar
);
331 sub
= bound2poly(lower
, dim
, nvar
, -1);
332 isl_constraint_free(upper
);
334 poly
= isl_qpolynomial_copy(data
->poly
);
335 poly
= plug_in_at_pos(poly
, nvar
, sub
);
336 poly
= isl_qpolynomial_drop_dims(poly
, isl_dim_in
, nvar
, 1);
338 isl_qpolynomial
*l
, *u
;
339 isl_qpolynomial
*pos
, *neg
;
340 isl_space
*dim
= isl_qpolynomial_get_domain_space(data
->poly
);
341 unsigned nparam
= isl_basic_set_dim(bset
, isl_dim_param
);
342 int sign
= data
->sign
* data
->signs
[nparam
+ nvar
];
346 u
= bound2poly(upper
, isl_space_copy(dim
), nvar
, 1);
347 l
= bound2poly(lower
, dim
, nvar
, -1);
349 pos
= isl_qpolynomial_terms_of_sign(data
->poly
, data
->signs
, sign
);
350 neg
= isl_qpolynomial_terms_of_sign(data
->poly
, data
->signs
, -sign
);
352 pos
= plug_in_at_pos(pos
, nvar
, u
);
353 neg
= plug_in_at_pos(neg
, nvar
, l
);
355 poly
= isl_qpolynomial_add(pos
, neg
);
356 poly
= isl_qpolynomial_drop_dims(poly
, isl_dim_in
, nvar
, 1);
359 if (isl_basic_set_dim(bset
, isl_dim_set
) == 0)
360 r
= add_guarded_poly(bset
, poly
, data
);
362 r
= propagate_on_domain(bset
, poly
, data
);
364 data
->tight
= save_tight
;
369 /* Recursively perform range propagation on the polynomial "poly"
370 * defined over the basic set "bset" and collect the results in "data".
372 static isl_stat
propagate_on_domain(__isl_take isl_basic_set
*bset
,
373 __isl_take isl_qpolynomial
*poly
, struct range_data
*data
)
376 isl_qpolynomial
*save_poly
= data
->poly
;
377 int save_monotonicity
= data
->monotonicity
;
383 ctx
= isl_basic_set_get_ctx(bset
);
384 d
= isl_basic_set_dim(bset
, isl_dim_set
);
385 isl_assert(ctx
, d
>= 1, goto error
);
387 if (isl_qpolynomial_is_cst(poly
, NULL
, NULL
)) {
388 bset
= isl_basic_set_project_out(bset
, isl_dim_set
, 0, d
);
389 poly
= isl_qpolynomial_drop_dims(poly
, isl_dim_in
, 0, d
);
390 return add_guarded_poly(bset
, poly
, data
);
393 if (data
->test_monotonicity
)
394 data
->monotonicity
= monotonicity(bset
, poly
, data
);
396 data
->monotonicity
= 0;
397 if (data
->monotonicity
< -1)
401 if (isl_basic_set_foreach_bound_pair(bset
, isl_dim_set
, d
- 1,
402 &propagate_on_bound_pair
, data
) < 0)
405 isl_basic_set_free(bset
);
406 isl_qpolynomial_free(poly
);
407 data
->monotonicity
= save_monotonicity
;
408 data
->poly
= save_poly
;
412 isl_basic_set_free(bset
);
413 isl_qpolynomial_free(poly
);
414 data
->monotonicity
= save_monotonicity
;
415 data
->poly
= save_poly
;
416 return isl_stat_error
;
419 static isl_stat
basic_guarded_poly_bound(__isl_take isl_basic_set
*bset
,
422 struct range_data
*data
= (struct range_data
*)user
;
424 unsigned nparam
= isl_basic_set_dim(bset
, isl_dim_param
);
425 unsigned dim
= isl_basic_set_dim(bset
, isl_dim_set
);
430 ctx
= isl_basic_set_get_ctx(bset
);
431 data
->signs
= isl_alloc_array(ctx
, int,
432 isl_basic_set_dim(bset
, isl_dim_all
));
434 if (isl_basic_set_dims_get_sign(bset
, isl_dim_set
, 0, dim
,
435 data
->signs
+ nparam
) < 0)
437 if (isl_basic_set_dims_get_sign(bset
, isl_dim_param
, 0, nparam
,
441 r
= propagate_on_domain(bset
, isl_qpolynomial_copy(data
->poly
), data
);
448 isl_basic_set_free(bset
);
449 return isl_stat_error
;
452 static int qpolynomial_bound_on_domain_range(__isl_take isl_basic_set
*bset
,
453 __isl_take isl_qpolynomial
*poly
, struct range_data
*data
)
455 unsigned nparam
= isl_basic_set_dim(bset
, isl_dim_param
);
456 unsigned nvar
= isl_basic_set_dim(bset
, isl_dim_set
);
463 return add_guarded_poly(bset
, poly
, data
);
465 set
= isl_set_from_basic_set(bset
);
466 set
= isl_set_split_dims(set
, isl_dim_param
, 0, nparam
);
467 set
= isl_set_split_dims(set
, isl_dim_set
, 0, nvar
);
471 data
->test_monotonicity
= 1;
472 if (isl_set_foreach_basic_set(set
, &basic_guarded_poly_bound
, data
) < 0)
476 isl_qpolynomial_free(poly
);
481 isl_qpolynomial_free(poly
);
485 int isl_qpolynomial_bound_on_domain_range(__isl_take isl_basic_set
*bset
,
486 __isl_take isl_qpolynomial
*poly
, struct isl_bound
*bound
)
488 struct range_data data
;
491 data
.pwf
= bound
->pwf
;
492 data
.pwf_tight
= bound
->pwf_tight
;
493 data
.tight
= bound
->check_tight
;
494 if (bound
->type
== isl_fold_min
)
499 r
= qpolynomial_bound_on_domain_range(bset
, poly
, &data
);
501 bound
->pwf
= data
.pwf
;
502 bound
->pwf_tight
= data
.pwf_tight
;