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,
11 #include <isl_bound.h>
12 #include <isl_bernstein.h>
13 #include <isl_range.h>
14 #include <isl_polynomial_private.h>
16 /* Compute a bound on the polynomial defined over the parametric polytope
17 * using either range propagation or bernstein expansion and
18 * store the result in bound->pwf and bound->pwf_tight.
19 * Since bernstein expansion requires bounded domains, we apply
20 * range propagation on unbounded domains. Otherwise, we respect the choice
23 static int compressed_guarded_poly_bound(__isl_take isl_basic_set *bset,
24 __isl_take isl_qpolynomial *poly, void *user)
26 struct isl_bound *bound = (struct isl_bound *)user;
32 if (bset->ctx->opt->bound == ISL_BOUND_RANGE)
33 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
35 bounded = isl_basic_set_is_bounded(bset);
39 return isl_qpolynomial_bound_on_domain_bernstein(bset, poly, bound);
41 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
43 isl_basic_set_free(bset);
44 isl_qpolynomial_free(poly);
48 static int unwrapped_guarded_poly_bound(__isl_take isl_basic_set *bset,
49 __isl_take isl_qpolynomial *poly, void *user)
51 struct isl_bound *bound = (struct isl_bound *)user;
52 isl_pw_qpolynomial_fold *top_pwf;
53 isl_pw_qpolynomial_fold *top_pwf_tight;
56 unsigned orig_nvar, final_nvar;
59 bset = isl_basic_set_detect_equalities(bset);
65 return compressed_guarded_poly_bound(bset, poly, user);
67 orig_nvar = isl_basic_set_dim(bset, isl_dim_set);
69 morph = isl_basic_set_full_compression(bset);
71 bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
72 poly = isl_qpolynomial_morph(poly, isl_morph_copy(morph));
74 final_nvar = isl_basic_set_dim(bset, isl_dim_set);
76 dim = isl_morph_get_ran_dim(morph);
77 dim = isl_dim_drop(dim, isl_dim_set, 0, isl_dim_size(dim, isl_dim_set));
80 top_pwf_tight = bound->pwf_tight;
82 bound->pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
83 bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim);
85 r = compressed_guarded_poly_bound(bset, poly, user);
87 morph = isl_morph_remove_dom_dims(morph, isl_dim_set, 0, orig_nvar);
88 morph = isl_morph_remove_ran_dims(morph, isl_dim_set, 0, final_nvar);
89 morph = isl_morph_inverse(morph);
91 bound->pwf = isl_pw_qpolynomial_fold_morph(bound->pwf,
92 isl_morph_copy(morph));
93 bound->pwf_tight = isl_pw_qpolynomial_fold_morph(bound->pwf_tight, morph);
95 bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
96 bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
101 isl_basic_set_free(bset);
102 isl_qpolynomial_free(poly);
106 static int guarded_poly_bound(__isl_take isl_basic_set *bset,
107 __isl_take isl_qpolynomial *poly, void *user)
109 struct isl_bound *bound = (struct isl_bound *)user;
112 isl_pw_qpolynomial_fold *top_pwf;
113 isl_pw_qpolynomial_fold *top_pwf_tight;
118 if (!isl_basic_set_is_wrapping(bset))
119 return unwrapped_guarded_poly_bound(bset, poly, user);
121 target_dim = isl_basic_set_get_dim(bset);
122 target_dim = isl_dim_unwrap(target_dim);
123 target_dim = isl_dim_domain(target_dim);
125 nparam = isl_dim_size(target_dim, isl_dim_param);
126 n_in = isl_dim_size(target_dim, isl_dim_set);
128 bset = isl_basic_set_move_dims(bset, isl_dim_param, nparam,
129 isl_dim_set, 0, n_in);
130 poly = isl_qpolynomial_move_dims(poly, isl_dim_param, nparam,
131 isl_dim_set, 0, n_in);
133 dim = isl_basic_set_get_dim(bset);
134 dim = isl_dim_drop(dim, isl_dim_set, 0, isl_dim_size(dim, isl_dim_set));
136 top_pwf = bound->pwf;
137 top_pwf_tight = bound->pwf_tight;
139 bound->pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
140 bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim);
142 r = unwrapped_guarded_poly_bound(bset, poly, user);
144 bound->pwf = isl_pw_qpolynomial_fold_reset_dim(bound->pwf,
145 isl_dim_copy(target_dim));
146 bound->pwf_tight = isl_pw_qpolynomial_fold_reset_dim(bound->pwf_tight,
149 bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
150 bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
156 static int guarded_qp(__isl_take isl_qpolynomial *qp, void *user)
158 struct isl_bound *bound = (struct isl_bound *)user;
161 r = isl_qpolynomial_as_polynomial_on_domain(qp, bound->bset,
162 &guarded_poly_bound, user);
163 isl_qpolynomial_free(qp);
167 static int basic_guarded_fold(__isl_take isl_basic_set *bset, void *user)
169 struct isl_bound *bound = (struct isl_bound *)user;
173 r = isl_qpolynomial_fold_foreach_qpolynomial(bound->fold,
175 isl_basic_set_free(bset);
179 static int guarded_fold(__isl_take isl_set *set,
180 __isl_take isl_qpolynomial_fold *fold, void *user)
182 struct isl_bound *bound = (struct isl_bound *)user;
187 set = isl_set_make_disjoint(set);
190 bound->type = isl_qpolynomial_fold_get_type(fold);
192 if (isl_set_foreach_basic_set(set, &basic_guarded_fold, bound) < 0)
196 isl_qpolynomial_fold_free(fold);
201 isl_qpolynomial_fold_free(fold);
205 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
206 __isl_take isl_pw_qpolynomial_fold *pwf, int *tight)
210 struct isl_bound bound;
216 dim = isl_pw_qpolynomial_fold_get_dim(pwf);
217 nvar = isl_dim_size(dim, isl_dim_set);
219 if (isl_pw_qpolynomial_fold_is_zero(pwf)) {
220 isl_pw_qpolynomial_fold_free(pwf);
221 dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
224 return isl_pw_qpolynomial_fold_zero(dim);
234 if (isl_dim_is_wrapping(dim)) {
235 dim = isl_dim_unwrap(dim);
236 nvar = isl_dim_size(dim, isl_dim_out);
237 dim = isl_dim_domain(dim);
241 return isl_pw_qpolynomial_fold_reset_dim(pwf, dim);
244 dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
246 bound.pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
247 bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
248 bound.check_tight = !!tight;
250 if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,
251 guarded_fold, &bound) < 0)
254 covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);
262 isl_pw_qpolynomial_fold_free(pwf);
265 isl_pw_qpolynomial_fold_free(bound.pwf);
266 return bound.pwf_tight;
269 bound.pwf = isl_pw_qpolynomial_fold_fold(bound.pwf, bound.pwf_tight);
273 isl_pw_qpolynomial_fold_free(bound.pwf_tight);
274 isl_pw_qpolynomial_fold_free(bound.pwf);
275 isl_pw_qpolynomial_fold_free(pwf);
280 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
281 __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type, int *tight)
283 isl_pw_qpolynomial_fold *pwf;
285 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
286 return isl_pw_qpolynomial_fold_bound(pwf, tight);
289 struct isl_union_bound_data {
292 isl_union_pw_qpolynomial_fold *res;
295 static int bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)
297 struct isl_union_bound_data *data = user;
298 isl_pw_qpolynomial_fold *pwf;
300 pwf = isl_pw_qpolynomial_bound(pwqp, data->type,
301 data->tight ? &data->tight : NULL);
302 data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
308 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
309 __isl_take isl_union_pw_qpolynomial *upwqp,
310 enum isl_fold type, int *tight)
313 struct isl_union_bound_data data = { type, 1, NULL };
321 dim = isl_union_pw_qpolynomial_get_dim(upwqp);
322 data.res = isl_union_pw_qpolynomial_fold_zero(dim);
323 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp,
324 &bound_pw, &data) < 0)
327 isl_union_pw_qpolynomial_free(upwqp);
333 isl_union_pw_qpolynomial_free(upwqp);
334 isl_union_pw_qpolynomial_fold_free(data.res);