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_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>
18 /* Compute a bound on the polynomial defined over the parametric polytope
19 * using either range propagation or bernstein expansion and
20 * store the result in bound->pwf and bound->pwf_tight.
21 * Since bernstein expansion requires bounded domains, we apply
22 * range propagation on unbounded domains. Otherwise, we respect the choice
25 static int compressed_guarded_poly_bound(__isl_take isl_basic_set *bset,
26 __isl_take isl_qpolynomial *poly, void *user)
28 struct isl_bound *bound = (struct isl_bound *)user;
34 if (bset->ctx->opt->bound == ISL_BOUND_RANGE)
35 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
37 bounded = isl_basic_set_is_bounded(bset);
41 return isl_qpolynomial_bound_on_domain_bernstein(bset, poly, bound);
43 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
45 isl_basic_set_free(bset);
46 isl_qpolynomial_free(poly);
50 static int unwrapped_guarded_poly_bound(__isl_take isl_basic_set *bset,
51 __isl_take isl_qpolynomial *poly, void *user)
53 struct isl_bound *bound = (struct isl_bound *)user;
54 isl_pw_qpolynomial_fold *top_pwf;
55 isl_pw_qpolynomial_fold *top_pwf_tight;
60 bset = isl_basic_set_detect_equalities(bset);
66 return compressed_guarded_poly_bound(bset, poly, user);
68 morph = isl_basic_set_full_compression(bset);
70 bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
71 poly = isl_qpolynomial_morph(poly, isl_morph_copy(morph));
73 dim = isl_morph_get_ran_space(morph);
74 dim = isl_space_params(dim);
77 top_pwf_tight = bound->pwf_tight;
79 bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(dim),
81 bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim, bound->type);
83 r = compressed_guarded_poly_bound(bset, poly, user);
85 morph = isl_morph_dom_params(morph);
86 morph = isl_morph_ran_params(morph);
87 morph = isl_morph_inverse(morph);
89 bound->pwf = isl_pw_qpolynomial_fold_morph(bound->pwf,
90 isl_morph_copy(morph));
91 bound->pwf_tight = isl_pw_qpolynomial_fold_morph(bound->pwf_tight, morph);
93 bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
94 bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
99 isl_basic_set_free(bset);
100 isl_qpolynomial_free(poly);
104 static int guarded_poly_bound(__isl_take isl_basic_set *bset,
105 __isl_take isl_qpolynomial *poly, void *user)
107 struct isl_bound *bound = (struct isl_bound *)user;
109 isl_pw_qpolynomial_fold *top_pwf;
110 isl_pw_qpolynomial_fold *top_pwf_tight;
115 if (!bound->wrapping)
116 return unwrapped_guarded_poly_bound(bset, poly, user);
118 nparam = isl_space_dim(bound->dim, isl_dim_param);
119 n_in = isl_space_dim(bound->dim, isl_dim_set);
121 bset = isl_basic_set_move_dims(bset, isl_dim_param, nparam,
122 isl_dim_set, 0, n_in);
123 poly = isl_qpolynomial_move_dims(poly, isl_dim_param, nparam,
124 isl_dim_set, 0, n_in);
126 dim = isl_basic_set_get_space(bset);
127 dim = isl_space_params(dim);
129 top_pwf = bound->pwf;
130 top_pwf_tight = bound->pwf_tight;
132 bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(dim),
134 bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim, bound->type);
136 r = unwrapped_guarded_poly_bound(bset, poly, user);
138 bound->pwf = isl_pw_qpolynomial_fold_reset_space(bound->pwf,
139 isl_space_copy(bound->dim));
140 bound->pwf_tight = isl_pw_qpolynomial_fold_reset_space(bound->pwf_tight,
141 isl_space_copy(bound->dim));
143 bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
144 bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
150 static int guarded_qp(__isl_take isl_qpolynomial *qp, void *user)
152 struct isl_bound *bound = (struct isl_bound *)user;
155 r = isl_qpolynomial_as_polynomial_on_domain(qp, bound->bset,
156 &guarded_poly_bound, user);
157 isl_qpolynomial_free(qp);
161 static int basic_guarded_fold(__isl_take isl_basic_set *bset, void *user)
163 struct isl_bound *bound = (struct isl_bound *)user;
167 r = isl_qpolynomial_fold_foreach_qpolynomial(bound->fold,
169 isl_basic_set_free(bset);
173 static int guarded_fold(__isl_take isl_set *set,
174 __isl_take isl_qpolynomial_fold *fold, void *user)
176 struct isl_bound *bound = (struct isl_bound *)user;
181 set = isl_set_make_disjoint(set);
184 bound->type = isl_qpolynomial_fold_get_type(fold);
186 if (isl_set_foreach_basic_set(set, &basic_guarded_fold, bound) < 0)
190 isl_qpolynomial_fold_free(fold);
195 isl_qpolynomial_fold_free(fold);
199 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
200 __isl_take isl_pw_qpolynomial_fold *pwf, int *tight)
203 struct isl_bound bound;
209 bound.dim = isl_pw_qpolynomial_fold_get_space(pwf);
211 bound.wrapping = isl_space_is_wrapping(bound.dim);
213 bound.dim = isl_space_unwrap(bound.dim);
214 nvar = isl_space_dim(bound.dim, isl_dim_out);
215 bound.dim = isl_space_domain(bound.dim);
220 return isl_pw_qpolynomial_fold_reset_space(pwf, bound.dim);
223 if (isl_pw_qpolynomial_fold_is_zero(pwf)) {
224 enum isl_fold type = pwf->type;
225 isl_pw_qpolynomial_fold_free(pwf);
228 return isl_pw_qpolynomial_fold_zero(bound.dim, type);
231 bound.pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
233 bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
235 bound.check_tight = !!tight;
237 if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,
238 guarded_fold, &bound) < 0)
241 covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);
248 isl_space_free(bound.dim);
249 isl_pw_qpolynomial_fold_free(pwf);
252 isl_pw_qpolynomial_fold_free(bound.pwf);
253 return bound.pwf_tight;
256 bound.pwf = isl_pw_qpolynomial_fold_fold(bound.pwf, bound.pwf_tight);
260 isl_pw_qpolynomial_fold_free(bound.pwf_tight);
261 isl_pw_qpolynomial_fold_free(bound.pwf);
262 isl_pw_qpolynomial_fold_free(pwf);
263 isl_space_free(bound.dim);
267 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
268 __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type, int *tight)
270 isl_pw_qpolynomial_fold *pwf;
272 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
273 return isl_pw_qpolynomial_fold_bound(pwf, tight);
276 struct isl_union_bound_data {
279 isl_union_pw_qpolynomial_fold *res;
282 static int bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)
284 struct isl_union_bound_data *data = user;
285 isl_pw_qpolynomial_fold *pwf;
287 pwf = isl_pw_qpolynomial_bound(pwqp, data->type,
288 data->tight ? &data->tight : NULL);
289 data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
295 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
296 __isl_take isl_union_pw_qpolynomial *upwqp,
297 enum isl_fold type, int *tight)
300 struct isl_union_bound_data data = { type, 1, NULL };
308 dim = isl_union_pw_qpolynomial_get_space(upwqp);
309 data.res = isl_union_pw_qpolynomial_fold_zero(dim, type);
310 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp,
311 &bound_pw, &data) < 0)
314 isl_union_pw_qpolynomial_free(upwqp);
320 isl_union_pw_qpolynomial_free(upwqp);
321 isl_union_pw_qpolynomial_fold_free(data.res);