Line data Source code
1 : /*
2 : * Copyright 2010 INRIA Saclay
3 : *
4 : * Use of this software is governed by the MIT license
5 : *
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 : */
10 :
11 : #include <isl_ctx_private.h>
12 : #include <isl_map_private.h>
13 : #include <isl_bound.h>
14 : #include <isl_bernstein.h>
15 : #include <isl_range.h>
16 : #include <isl_polynomial_private.h>
17 : #include <isl_options_private.h>
18 :
19 : /* Compute a bound on the polynomial defined over the parametric polytope
20 : * using either range propagation or bernstein expansion and
21 : * store the result in bound->pwf and bound->pwf_tight.
22 : * Since bernstein expansion requires bounded domains, we apply
23 : * range propagation on unbounded domains. Otherwise, we respect the choice
24 : * of the user.
25 : */
26 0 : static isl_stat compressed_guarded_poly_bound(__isl_take isl_basic_set *bset,
27 : __isl_take isl_qpolynomial *poly, void *user)
28 : {
29 0 : struct isl_bound *bound = (struct isl_bound *)user;
30 : int bounded;
31 :
32 0 : if (!bset || !poly)
33 : goto error;
34 :
35 0 : if (bset->ctx->opt->bound == ISL_BOUND_RANGE)
36 0 : return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
37 :
38 0 : bounded = isl_basic_set_is_bounded(bset);
39 0 : if (bounded < 0)
40 0 : goto error;
41 0 : if (bounded)
42 0 : return isl_qpolynomial_bound_on_domain_bernstein(bset, poly, bound);
43 : else
44 0 : return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
45 : error:
46 0 : isl_basic_set_free(bset);
47 0 : isl_qpolynomial_free(poly);
48 0 : return isl_stat_error;
49 : }
50 :
51 0 : static isl_stat unwrapped_guarded_poly_bound(__isl_take isl_basic_set *bset,
52 : __isl_take isl_qpolynomial *poly, void *user)
53 : {
54 0 : struct isl_bound *bound = (struct isl_bound *)user;
55 : isl_pw_qpolynomial_fold *top_pwf;
56 : isl_pw_qpolynomial_fold *top_pwf_tight;
57 : isl_space *dim;
58 : isl_morph *morph;
59 : isl_stat r;
60 :
61 0 : bset = isl_basic_set_detect_equalities(bset);
62 :
63 0 : if (!bset)
64 0 : goto error;
65 :
66 0 : if (bset->n_eq == 0)
67 0 : return compressed_guarded_poly_bound(bset, poly, user);
68 :
69 0 : morph = isl_basic_set_full_compression(bset);
70 :
71 0 : bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
72 0 : poly = isl_qpolynomial_morph_domain(poly, isl_morph_copy(morph));
73 :
74 0 : dim = isl_morph_get_ran_space(morph);
75 0 : dim = isl_space_params(dim);
76 :
77 0 : top_pwf = bound->pwf;
78 0 : top_pwf_tight = bound->pwf_tight;
79 :
80 0 : dim = isl_space_from_domain(dim);
81 0 : dim = isl_space_add_dims(dim, isl_dim_out, 1);
82 0 : bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(dim),
83 : bound->type);
84 0 : bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim, bound->type);
85 :
86 0 : r = compressed_guarded_poly_bound(bset, poly, user);
87 :
88 0 : morph = isl_morph_dom_params(morph);
89 0 : morph = isl_morph_ran_params(morph);
90 0 : morph = isl_morph_inverse(morph);
91 :
92 0 : bound->pwf = isl_pw_qpolynomial_fold_morph_domain(bound->pwf,
93 : isl_morph_copy(morph));
94 0 : bound->pwf_tight = isl_pw_qpolynomial_fold_morph_domain(
95 : bound->pwf_tight, morph);
96 :
97 0 : bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
98 0 : bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
99 : bound->pwf_tight);
100 :
101 0 : return r;
102 : error:
103 0 : isl_basic_set_free(bset);
104 0 : isl_qpolynomial_free(poly);
105 0 : return isl_stat_error;
106 : }
107 :
108 0 : static isl_stat guarded_poly_bound(__isl_take isl_basic_set *bset,
109 : __isl_take isl_qpolynomial *poly, void *user)
110 : {
111 0 : struct isl_bound *bound = (struct isl_bound *)user;
112 : isl_space *dim;
113 : isl_pw_qpolynomial_fold *top_pwf;
114 : isl_pw_qpolynomial_fold *top_pwf_tight;
115 : int nparam;
116 : int n_in;
117 : isl_stat r;
118 :
119 0 : if (!bound->wrapping)
120 0 : return unwrapped_guarded_poly_bound(bset, poly, user);
121 :
122 0 : nparam = isl_space_dim(bound->dim, isl_dim_param);
123 0 : n_in = isl_space_dim(bound->dim, isl_dim_in);
124 :
125 0 : bset = isl_basic_set_move_dims(bset, isl_dim_param, nparam,
126 : isl_dim_set, 0, n_in);
127 0 : poly = isl_qpolynomial_move_dims(poly, isl_dim_param, nparam,
128 : isl_dim_in, 0, n_in);
129 :
130 0 : dim = isl_basic_set_get_space(bset);
131 0 : dim = isl_space_params(dim);
132 :
133 0 : top_pwf = bound->pwf;
134 0 : top_pwf_tight = bound->pwf_tight;
135 :
136 0 : dim = isl_space_from_domain(dim);
137 0 : dim = isl_space_add_dims(dim, isl_dim_out, 1);
138 0 : bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(dim),
139 : bound->type);
140 0 : bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim, bound->type);
141 :
142 0 : r = unwrapped_guarded_poly_bound(bset, poly, user);
143 :
144 0 : bound->pwf = isl_pw_qpolynomial_fold_reset_space(bound->pwf,
145 : isl_space_copy(bound->dim));
146 0 : bound->pwf_tight = isl_pw_qpolynomial_fold_reset_space(bound->pwf_tight,
147 : isl_space_copy(bound->dim));
148 :
149 0 : bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
150 0 : bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
151 : bound->pwf_tight);
152 :
153 0 : return r;
154 : }
155 :
156 0 : static isl_stat guarded_qp(__isl_take isl_qpolynomial *qp, void *user)
157 : {
158 0 : struct isl_bound *bound = (struct isl_bound *)user;
159 : isl_stat r;
160 :
161 0 : r = isl_qpolynomial_as_polynomial_on_domain(qp, bound->bset,
162 : &guarded_poly_bound, user);
163 0 : isl_qpolynomial_free(qp);
164 0 : return r;
165 : }
166 :
167 0 : static isl_stat basic_guarded_fold(__isl_take isl_basic_set *bset, void *user)
168 : {
169 0 : struct isl_bound *bound = (struct isl_bound *)user;
170 : isl_stat r;
171 :
172 0 : bound->bset = bset;
173 0 : r = isl_qpolynomial_fold_foreach_qpolynomial(bound->fold,
174 : &guarded_qp, user);
175 0 : isl_basic_set_free(bset);
176 0 : return r;
177 : }
178 :
179 0 : static isl_stat guarded_fold(__isl_take isl_set *set,
180 : __isl_take isl_qpolynomial_fold *fold, void *user)
181 : {
182 0 : struct isl_bound *bound = (struct isl_bound *)user;
183 :
184 0 : if (!set || !fold)
185 : goto error;
186 :
187 0 : set = isl_set_make_disjoint(set);
188 :
189 0 : bound->fold = fold;
190 0 : bound->type = isl_qpolynomial_fold_get_type(fold);
191 :
192 0 : if (isl_set_foreach_basic_set(set, &basic_guarded_fold, bound) < 0)
193 0 : goto error;
194 :
195 0 : isl_set_free(set);
196 0 : isl_qpolynomial_fold_free(fold);
197 :
198 0 : return isl_stat_ok;
199 : error:
200 0 : isl_set_free(set);
201 0 : isl_qpolynomial_fold_free(fold);
202 0 : return isl_stat_error;
203 : }
204 :
205 0 : __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
206 : __isl_take isl_pw_qpolynomial_fold *pwf, int *tight)
207 : {
208 : unsigned nvar;
209 : struct isl_bound bound;
210 : int covers;
211 :
212 0 : if (!pwf)
213 0 : return NULL;
214 :
215 0 : bound.dim = isl_pw_qpolynomial_fold_get_domain_space(pwf);
216 :
217 0 : bound.wrapping = isl_space_is_wrapping(bound.dim);
218 0 : if (bound.wrapping)
219 0 : bound.dim = isl_space_unwrap(bound.dim);
220 0 : nvar = isl_space_dim(bound.dim, isl_dim_out);
221 0 : bound.dim = isl_space_domain(bound.dim);
222 0 : bound.dim = isl_space_from_domain(bound.dim);
223 0 : bound.dim = isl_space_add_dims(bound.dim, isl_dim_out, 1);
224 :
225 0 : if (nvar == 0) {
226 0 : if (tight)
227 0 : *tight = 1;
228 0 : return isl_pw_qpolynomial_fold_reset_space(pwf, bound.dim);
229 : }
230 :
231 0 : if (isl_pw_qpolynomial_fold_is_zero(pwf)) {
232 0 : enum isl_fold type = pwf->type;
233 0 : isl_pw_qpolynomial_fold_free(pwf);
234 0 : if (tight)
235 0 : *tight = 1;
236 0 : return isl_pw_qpolynomial_fold_zero(bound.dim, type);
237 : }
238 :
239 0 : bound.pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
240 : pwf->type);
241 0 : bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
242 : pwf->type);
243 0 : bound.check_tight = !!tight;
244 :
245 0 : if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,
246 : guarded_fold, &bound) < 0)
247 0 : goto error;
248 :
249 0 : covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);
250 0 : if (covers < 0)
251 0 : goto error;
252 :
253 0 : if (tight)
254 0 : *tight = covers;
255 :
256 0 : isl_space_free(bound.dim);
257 0 : isl_pw_qpolynomial_fold_free(pwf);
258 :
259 0 : if (covers) {
260 0 : isl_pw_qpolynomial_fold_free(bound.pwf);
261 0 : return bound.pwf_tight;
262 : }
263 :
264 0 : bound.pwf = isl_pw_qpolynomial_fold_fold(bound.pwf, bound.pwf_tight);
265 :
266 0 : return bound.pwf;
267 : error:
268 0 : isl_pw_qpolynomial_fold_free(bound.pwf_tight);
269 0 : isl_pw_qpolynomial_fold_free(bound.pwf);
270 0 : isl_pw_qpolynomial_fold_free(pwf);
271 0 : isl_space_free(bound.dim);
272 0 : return NULL;
273 : }
274 :
275 0 : __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
276 : __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type, int *tight)
277 : {
278 : isl_pw_qpolynomial_fold *pwf;
279 :
280 0 : pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
281 0 : return isl_pw_qpolynomial_fold_bound(pwf, tight);
282 : }
283 :
284 : struct isl_union_bound_data {
285 : enum isl_fold type;
286 : int tight;
287 : isl_union_pw_qpolynomial_fold *res;
288 : };
289 :
290 0 : static isl_stat bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)
291 : {
292 0 : struct isl_union_bound_data *data = user;
293 : isl_pw_qpolynomial_fold *pwf;
294 :
295 0 : pwf = isl_pw_qpolynomial_bound(pwqp, data->type,
296 0 : data->tight ? &data->tight : NULL);
297 0 : data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
298 : data->res, pwf);
299 :
300 0 : return isl_stat_ok;
301 : }
302 :
303 0 : __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
304 : __isl_take isl_union_pw_qpolynomial *upwqp,
305 : enum isl_fold type, int *tight)
306 : {
307 : isl_space *dim;
308 0 : struct isl_union_bound_data data = { type, 1, NULL };
309 :
310 0 : if (!upwqp)
311 0 : return NULL;
312 :
313 0 : if (!tight)
314 0 : data.tight = 0;
315 :
316 0 : dim = isl_union_pw_qpolynomial_get_space(upwqp);
317 0 : data.res = isl_union_pw_qpolynomial_fold_zero(dim, type);
318 0 : if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp,
319 : &bound_pw, &data) < 0)
320 0 : goto error;
321 :
322 0 : isl_union_pw_qpolynomial_free(upwqp);
323 0 : if (tight)
324 0 : *tight = data.tight;
325 :
326 0 : return data.res;
327 : error:
328 0 : isl_union_pw_qpolynomial_free(upwqp);
329 0 : isl_union_pw_qpolynomial_fold_free(data.res);
330 0 : return NULL;
331 : }
|
