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
);