isl_schedule_node.c: collect_filter_prefix: allow traversal of subset of list
[isl.git] / isl_range.c
blob517db032b0227e52dc7bd7e2e775a2658520dd25
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>
8 struct 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;
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;
32 unsigned nparam;
33 isl_space *dim;
34 isl_val *opt;
35 int r;
36 enum isl_fold type;
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;
54 data_m.signs = signs;
55 data_m.sign = -sign;
56 type = data_m.sign < 0 ? isl_fold_min : isl_fold_max;
57 data_m.pwf = isl_pw_qpolynomial_fold_zero(dim, type);
58 data_m.tight = 0;
59 data_m.pwf_tight = NULL;
61 if (propagate_on_domain(bset, poly, &data_m) < 0)
62 goto error;
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);
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;
78 isl_val_free(opt);
80 return r;
81 error:
82 isl_pw_qpolynomial_fold_free(data_m.pwf);
83 return -1;
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.
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)
96 isl_ctx *ctx;
97 isl_space *dim;
98 isl_qpolynomial *sub = NULL;
99 isl_qpolynomial *diff = NULL;
100 int result = 0;
101 int s;
102 unsigned nvar;
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);
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;
130 isl_qpolynomial_free(diff);
131 isl_qpolynomial_free(sub);
133 return result;
134 error:
135 isl_qpolynomial_free(diff);
136 isl_qpolynomial_free(sub);
137 return -2;
140 static __isl_give isl_qpolynomial *bound2poly(__isl_take isl_constraint *bound,
141 __isl_take isl_space *dim, unsigned pos, int sign)
143 if (!bound) {
144 if (sign > 0)
145 return isl_qpolynomial_infty_on_domain(dim);
146 else
147 return isl_qpolynomial_neginfty_on_domain(dim);
149 isl_space_free(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)
155 isl_int c;
156 int is_int;
158 if (!bound)
159 return 1;
161 isl_int_init(c);
162 isl_constraint_get_coefficient(bound, isl_dim_set, pos, &c);
163 is_int = isl_int_is_one(c) || isl_int_is_negone(c);
164 isl_int_clear(c);
166 return is_int;
169 struct isl_fixed_sign_data {
170 int *signs;
171 int sign;
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;
183 isl_int n;
184 int i;
185 int sign;
186 unsigned nparam;
187 unsigned nvar;
189 if (!term)
190 return -1;
192 nparam = isl_term_dim(term, isl_dim_param);
193 nvar = isl_term_dim(term, isl_dim_set);
195 isl_int_init(n);
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)
202 continue;
203 if (isl_term_get_exp(term, isl_dim_param, i) % 2)
204 sign = -sign;
206 for (i = 0; i < nvar; ++i) {
207 if (data->signs[nparam + i] > 0)
208 continue;
209 if (isl_term_get_exp(term, isl_dim_set, i) % 2)
210 sign = -sign;
213 if (sign == data->sign) {
214 isl_qpolynomial *t = isl_qpolynomial_from_term(term);
216 data->poly = isl_qpolynomial_add(data->poly, t);
217 } else
218 isl_term_free(term);
220 isl_int_clear(n);
222 return 0;
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)
232 isl_space *space;
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)
239 goto error;
241 return data.poly;
242 error:
243 isl_qpolynomial_free(data.poly);
244 return NULL;
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;
254 isl_set *set;
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);
264 if (data->tight)
265 data->pwf_tight = isl_pw_qpolynomial_fold_fold(
266 data->pwf_tight, pwf);
267 else
268 data->pwf = isl_pw_qpolynomial_fold_fold(data->pwf, pwf);
270 return 0;
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
280 * may not be tight.
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,
290 void *user)
292 struct range_data *data = (struct range_data *)user;
293 int save_tight = data->tight;
294 isl_qpolynomial *poly;
295 int r;
296 unsigned nvar;
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) {
304 if (data->tight)
305 data->tight = bound_is_integer(upper, nvar);
306 sub = bound2poly(upper, dim, nvar, 1);
307 isl_constraint_free(lower);
308 } else {
309 if (data->tight)
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);
319 } else {
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];
326 data->tight = 0;
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);
346 else
347 r = propagate_on_domain(bset, poly, data);
349 data->tight = save_tight;
351 return r;
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)
360 isl_ctx *ctx;
361 isl_qpolynomial *save_poly = data->poly;
362 int save_monotonicity = data->monotonicity;
363 unsigned d;
365 if (!bset || !poly)
366 goto error;
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);
380 else
381 data->monotonicity = 0;
382 if (data->monotonicity < -1)
383 goto error;
385 data->poly = poly;
386 if (isl_basic_set_foreach_bound_pair(bset, isl_dim_set, d - 1,
387 &propagate_on_bound_pair, data) < 0)
388 goto error;
390 isl_basic_set_free(bset);
391 isl_qpolynomial_free(poly);
392 data->monotonicity = save_monotonicity;
393 data->poly = save_poly;
395 return 0;
396 error:
397 isl_basic_set_free(bset);
398 isl_qpolynomial_free(poly);
399 data->monotonicity = save_monotonicity;
400 data->poly = save_poly;
401 return -1;
404 static int basic_guarded_poly_bound(__isl_take isl_basic_set *bset, void *user)
406 struct range_data *data = (struct range_data *)user;
407 isl_ctx *ctx;
408 unsigned nparam = isl_basic_set_dim(bset, isl_dim_param);
409 unsigned dim = isl_basic_set_dim(bset, isl_dim_set);
410 int r;
412 data->signs = NULL;
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)
420 goto error;
421 if (isl_basic_set_dims_get_sign(bset, isl_dim_param, 0, nparam,
422 data->signs) < 0)
423 goto error;
425 r = propagate_on_domain(bset, isl_qpolynomial_copy(data->poly), data);
427 free(data->signs);
429 return r;
430 error:
431 free(data->signs);
432 isl_basic_set_free(bset);
433 return -1;
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);
441 isl_set *set = NULL;
443 if (!bset)
444 goto error;
446 if (nvar == 0)
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);
453 data->poly = poly;
455 data->test_monotonicity = 1;
456 if (isl_set_foreach_basic_set(set, &basic_guarded_poly_bound, data) < 0)
457 goto error;
459 isl_set_free(set);
460 isl_qpolynomial_free(poly);
462 return 0;
463 error:
464 isl_set_free(set);
465 isl_qpolynomial_free(poly);
466 return -1;
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;
473 int r;
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)
479 data.sign = -1;
480 else
481 data.sign = 1;
483 r = qpolynomial_bound_on_domain_range(bset, poly, &data);
485 bound->pwf = data.pwf;
486 bound->pwf_tight = data.pwf_tight;
488 return r;