isl_stream: maintain private ungetc buffer
[isl.git] / isl_bound.c
blobb25c2f6a129c1ea62cbf86a1cc51970c91c8bd08
1 /*
2 * Copyright 2010 INRIA Saclay
4 * Use of this software is governed by the GNU LGPLv2.1 license
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
8 * 91893 Orsay, France
9 */
11 #include <isl_map_private.h>
12 #include <isl_bound.h>
13 #include <isl_bernstein.h>
14 #include <isl_range.h>
15 #include <isl_polynomial_private.h>
17 /* Compute a bound on the polynomial defined over the parametric polytope
18 * using either range propagation or bernstein expansion and
19 * store the result in bound->pwf and bound->pwf_tight.
20 * Since bernstein expansion requires bounded domains, we apply
21 * range propagation on unbounded domains. Otherwise, we respect the choice
22 * of the user.
24 static int compressed_guarded_poly_bound(__isl_take isl_basic_set *bset,
25 __isl_take isl_qpolynomial *poly, void *user)
27 struct isl_bound *bound = (struct isl_bound *)user;
28 int bounded;
30 if (!bset || !poly)
31 goto error;
33 if (bset->ctx->opt->bound == ISL_BOUND_RANGE)
34 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
36 bounded = isl_basic_set_is_bounded(bset);
37 if (bounded < 0)
38 goto error;
39 if (bounded)
40 return isl_qpolynomial_bound_on_domain_bernstein(bset, poly, bound);
41 else
42 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
43 error:
44 isl_basic_set_free(bset);
45 isl_qpolynomial_free(poly);
46 return -1;
49 static int unwrapped_guarded_poly_bound(__isl_take isl_basic_set *bset,
50 __isl_take isl_qpolynomial *poly, void *user)
52 struct isl_bound *bound = (struct isl_bound *)user;
53 isl_pw_qpolynomial_fold *top_pwf;
54 isl_pw_qpolynomial_fold *top_pwf_tight;
55 isl_dim *dim;
56 isl_morph *morph;
57 unsigned orig_nvar, final_nvar;
58 int r;
60 bset = isl_basic_set_detect_equalities(bset);
62 if (!bset)
63 goto error;
65 if (bset->n_eq == 0)
66 return compressed_guarded_poly_bound(bset, poly, user);
68 orig_nvar = isl_basic_set_dim(bset, isl_dim_set);
70 morph = isl_basic_set_full_compression(bset);
72 bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
73 poly = isl_qpolynomial_morph(poly, isl_morph_copy(morph));
75 final_nvar = isl_basic_set_dim(bset, isl_dim_set);
77 dim = isl_morph_get_ran_dim(morph);
78 dim = isl_dim_drop(dim, isl_dim_set, 0, isl_dim_size(dim, isl_dim_set));
80 top_pwf = bound->pwf;
81 top_pwf_tight = bound->pwf_tight;
83 bound->pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim),
84 bound->type);
85 bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim, bound->type);
87 r = compressed_guarded_poly_bound(bset, poly, user);
89 morph = isl_morph_remove_dom_dims(morph, isl_dim_set, 0, orig_nvar);
90 morph = isl_morph_remove_ran_dims(morph, isl_dim_set, 0, final_nvar);
91 morph = isl_morph_inverse(morph);
93 bound->pwf = isl_pw_qpolynomial_fold_morph(bound->pwf,
94 isl_morph_copy(morph));
95 bound->pwf_tight = isl_pw_qpolynomial_fold_morph(bound->pwf_tight, morph);
97 bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
98 bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
99 bound->pwf_tight);
101 return r;
102 error:
103 isl_basic_set_free(bset);
104 isl_qpolynomial_free(poly);
105 return -1;
108 static int guarded_poly_bound(__isl_take isl_basic_set *bset,
109 __isl_take isl_qpolynomial *poly, void *user)
111 struct isl_bound *bound = (struct isl_bound *)user;
112 isl_dim *dim;
113 isl_pw_qpolynomial_fold *top_pwf;
114 isl_pw_qpolynomial_fold *top_pwf_tight;
115 int nparam;
116 int n_in;
117 int r;
119 if (!bound->wrapping)
120 return unwrapped_guarded_poly_bound(bset, poly, user);
122 nparam = isl_dim_size(bound->dim, isl_dim_param);
123 n_in = isl_dim_size(bound->dim, isl_dim_set);
125 bset = isl_basic_set_move_dims(bset, isl_dim_param, nparam,
126 isl_dim_set, 0, n_in);
127 poly = isl_qpolynomial_move_dims(poly, isl_dim_param, nparam,
128 isl_dim_set, 0, n_in);
130 dim = isl_basic_set_get_dim(bset);
131 dim = isl_dim_drop(dim, isl_dim_set, 0, isl_dim_size(dim, isl_dim_set));
133 top_pwf = bound->pwf;
134 top_pwf_tight = bound->pwf_tight;
136 bound->pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim),
137 bound->type);
138 bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim, bound->type);
140 r = unwrapped_guarded_poly_bound(bset, poly, user);
142 bound->pwf = isl_pw_qpolynomial_fold_reset_dim(bound->pwf,
143 isl_dim_copy(bound->dim));
144 bound->pwf_tight = isl_pw_qpolynomial_fold_reset_dim(bound->pwf_tight,
145 isl_dim_copy(bound->dim));
147 bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
148 bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
149 bound->pwf_tight);
151 return r;
154 static int guarded_qp(__isl_take isl_qpolynomial *qp, void *user)
156 struct isl_bound *bound = (struct isl_bound *)user;
157 int r;
159 r = isl_qpolynomial_as_polynomial_on_domain(qp, bound->bset,
160 &guarded_poly_bound, user);
161 isl_qpolynomial_free(qp);
162 return r;
165 static int basic_guarded_fold(__isl_take isl_basic_set *bset, void *user)
167 struct isl_bound *bound = (struct isl_bound *)user;
168 int r;
170 bound->bset = bset;
171 r = isl_qpolynomial_fold_foreach_qpolynomial(bound->fold,
172 &guarded_qp, user);
173 isl_basic_set_free(bset);
174 return r;
177 static int guarded_fold(__isl_take isl_set *set,
178 __isl_take isl_qpolynomial_fold *fold, void *user)
180 struct isl_bound *bound = (struct isl_bound *)user;
182 if (!set || !fold)
183 goto error;
185 set = isl_set_make_disjoint(set);
187 bound->fold = fold;
188 bound->type = isl_qpolynomial_fold_get_type(fold);
190 if (isl_set_foreach_basic_set(set, &basic_guarded_fold, bound) < 0)
191 goto error;
193 isl_set_free(set);
194 isl_qpolynomial_fold_free(fold);
196 return 0;
197 error:
198 isl_set_free(set);
199 isl_qpolynomial_fold_free(fold);
200 return -1;
203 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
204 __isl_take isl_pw_qpolynomial_fold *pwf, int *tight)
206 unsigned nvar;
207 struct isl_bound bound;
208 int covers;
210 if (!pwf)
211 return NULL;
213 bound.dim = isl_pw_qpolynomial_fold_get_dim(pwf);
214 nvar = isl_dim_size(bound.dim, isl_dim_set);
216 bound.wrapping = isl_dim_is_wrapping(bound.dim);
217 if (bound.wrapping) {
218 bound.dim = isl_dim_unwrap(bound.dim);
219 nvar = isl_dim_size(bound.dim, isl_dim_out);
220 bound.dim = isl_dim_domain(bound.dim);
221 } else
222 bound.dim = isl_dim_drop(bound.dim, isl_dim_set, 0, nvar);
224 if (nvar == 0) {
225 if (tight)
226 *tight = 1;
227 return isl_pw_qpolynomial_fold_reset_dim(pwf, bound.dim);
230 if (isl_pw_qpolynomial_fold_is_zero(pwf)) {
231 enum isl_fold type = pwf->type;
232 isl_pw_qpolynomial_fold_free(pwf);
233 if (tight)
234 *tight = 1;
235 return isl_pw_qpolynomial_fold_zero(bound.dim, type);
238 bound.pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(bound.dim),
239 pwf->type);
240 bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_dim_copy(bound.dim),
241 pwf->type);
242 bound.check_tight = !!tight;
244 if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,
245 guarded_fold, &bound) < 0)
246 goto error;
248 covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);
249 if (covers < 0)
250 goto error;
252 if (tight)
253 *tight = covers;
255 isl_dim_free(bound.dim);
256 isl_pw_qpolynomial_fold_free(pwf);
258 if (covers) {
259 isl_pw_qpolynomial_fold_free(bound.pwf);
260 return bound.pwf_tight;
263 bound.pwf = isl_pw_qpolynomial_fold_fold(bound.pwf, bound.pwf_tight);
265 return bound.pwf;
266 error:
267 isl_pw_qpolynomial_fold_free(bound.pwf_tight);
268 isl_pw_qpolynomial_fold_free(bound.pwf);
269 isl_pw_qpolynomial_fold_free(pwf);
270 isl_dim_free(bound.dim);
271 return NULL;
274 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
275 __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type, int *tight)
277 isl_pw_qpolynomial_fold *pwf;
279 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
280 return isl_pw_qpolynomial_fold_bound(pwf, tight);
283 struct isl_union_bound_data {
284 enum isl_fold type;
285 int tight;
286 isl_union_pw_qpolynomial_fold *res;
289 static int bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)
291 struct isl_union_bound_data *data = user;
292 isl_pw_qpolynomial_fold *pwf;
294 pwf = isl_pw_qpolynomial_bound(pwqp, data->type,
295 data->tight ? &data->tight : NULL);
296 data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
297 data->res, pwf);
299 return 0;
302 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
303 __isl_take isl_union_pw_qpolynomial *upwqp,
304 enum isl_fold type, int *tight)
306 isl_dim *dim;
307 struct isl_union_bound_data data = { type, 1, NULL };
309 if (!upwqp)
310 return NULL;
312 if (!tight)
313 data.tight = 0;
315 dim = isl_union_pw_qpolynomial_get_dim(upwqp);
316 data.res = isl_union_pw_qpolynomial_fold_zero(dim, type);
317 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp,
318 &bound_pw, &data) < 0)
319 goto error;
321 isl_union_pw_qpolynomial_free(upwqp);
322 if (tight)
323 *tight = data.tight;
325 return data.res;
326 error:
327 isl_union_pw_qpolynomial_free(upwqp);
328 isl_union_pw_qpolynomial_fold_free(data.res);
329 return NULL;