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