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
;
58 unsigned orig_nvar
, final_nvar
;
61 bset
= isl_basic_set_detect_equalities(bset
);
67 return compressed_guarded_poly_bound(bset
, poly
, user
);
69 orig_nvar
= isl_basic_set_dim(bset
, isl_dim_set
);
71 morph
= isl_basic_set_full_compression(bset
);
73 bset
= isl_morph_basic_set(isl_morph_copy(morph
), bset
);
74 poly
= isl_qpolynomial_morph(poly
, isl_morph_copy(morph
));
76 final_nvar
= isl_basic_set_dim(bset
, isl_dim_set
);
78 dim
= isl_morph_get_ran_space(morph
);
79 dim
= isl_space_drop_dims(dim
, isl_dim_set
, 0, isl_space_dim(dim
, isl_dim_set
));
82 top_pwf_tight
= bound
->pwf_tight
;
84 bound
->pwf
= isl_pw_qpolynomial_fold_zero(isl_space_copy(dim
),
86 bound
->pwf_tight
= isl_pw_qpolynomial_fold_zero(dim
, bound
->type
);
88 r
= compressed_guarded_poly_bound(bset
, poly
, user
);
90 morph
= isl_morph_remove_dom_dims(morph
, isl_dim_set
, 0, orig_nvar
);
91 morph
= isl_morph_remove_ran_dims(morph
, isl_dim_set
, 0, final_nvar
);
92 morph
= isl_morph_inverse(morph
);
94 bound
->pwf
= isl_pw_qpolynomial_fold_morph(bound
->pwf
,
95 isl_morph_copy(morph
));
96 bound
->pwf_tight
= isl_pw_qpolynomial_fold_morph(bound
->pwf_tight
, morph
);
98 bound
->pwf
= isl_pw_qpolynomial_fold_fold(top_pwf
, bound
->pwf
);
99 bound
->pwf_tight
= isl_pw_qpolynomial_fold_fold(top_pwf_tight
,
104 isl_basic_set_free(bset
);
105 isl_qpolynomial_free(poly
);
109 static int guarded_poly_bound(__isl_take isl_basic_set
*bset
,
110 __isl_take isl_qpolynomial
*poly
, void *user
)
112 struct isl_bound
*bound
= (struct isl_bound
*)user
;
114 isl_pw_qpolynomial_fold
*top_pwf
;
115 isl_pw_qpolynomial_fold
*top_pwf_tight
;
120 if (!bound
->wrapping
)
121 return unwrapped_guarded_poly_bound(bset
, poly
, user
);
123 nparam
= isl_space_dim(bound
->dim
, isl_dim_param
);
124 n_in
= isl_space_dim(bound
->dim
, isl_dim_set
);
126 bset
= isl_basic_set_move_dims(bset
, isl_dim_param
, nparam
,
127 isl_dim_set
, 0, n_in
);
128 poly
= isl_qpolynomial_move_dims(poly
, isl_dim_param
, nparam
,
129 isl_dim_set
, 0, n_in
);
131 dim
= isl_basic_set_get_space(bset
);
132 dim
= isl_space_drop_dims(dim
, isl_dim_set
, 0, isl_space_dim(dim
, isl_dim_set
));
134 top_pwf
= bound
->pwf
;
135 top_pwf_tight
= bound
->pwf_tight
;
137 bound
->pwf
= isl_pw_qpolynomial_fold_zero(isl_space_copy(dim
),
139 bound
->pwf_tight
= isl_pw_qpolynomial_fold_zero(dim
, bound
->type
);
141 r
= unwrapped_guarded_poly_bound(bset
, poly
, user
);
143 bound
->pwf
= isl_pw_qpolynomial_fold_reset_space(bound
->pwf
,
144 isl_space_copy(bound
->dim
));
145 bound
->pwf_tight
= isl_pw_qpolynomial_fold_reset_space(bound
->pwf_tight
,
146 isl_space_copy(bound
->dim
));
148 bound
->pwf
= isl_pw_qpolynomial_fold_fold(top_pwf
, bound
->pwf
);
149 bound
->pwf_tight
= isl_pw_qpolynomial_fold_fold(top_pwf_tight
,
155 static int guarded_qp(__isl_take isl_qpolynomial
*qp
, void *user
)
157 struct isl_bound
*bound
= (struct isl_bound
*)user
;
160 r
= isl_qpolynomial_as_polynomial_on_domain(qp
, bound
->bset
,
161 &guarded_poly_bound
, user
);
162 isl_qpolynomial_free(qp
);
166 static int basic_guarded_fold(__isl_take isl_basic_set
*bset
, void *user
)
168 struct isl_bound
*bound
= (struct isl_bound
*)user
;
172 r
= isl_qpolynomial_fold_foreach_qpolynomial(bound
->fold
,
174 isl_basic_set_free(bset
);
178 static int guarded_fold(__isl_take isl_set
*set
,
179 __isl_take isl_qpolynomial_fold
*fold
, void *user
)
181 struct isl_bound
*bound
= (struct isl_bound
*)user
;
186 set
= isl_set_make_disjoint(set
);
189 bound
->type
= isl_qpolynomial_fold_get_type(fold
);
191 if (isl_set_foreach_basic_set(set
, &basic_guarded_fold
, bound
) < 0)
195 isl_qpolynomial_fold_free(fold
);
200 isl_qpolynomial_fold_free(fold
);
204 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_bound(
205 __isl_take isl_pw_qpolynomial_fold
*pwf
, int *tight
)
208 struct isl_bound bound
;
214 bound
.dim
= isl_pw_qpolynomial_fold_get_space(pwf
);
216 bound
.wrapping
= isl_space_is_wrapping(bound
.dim
);
218 bound
.dim
= isl_space_unwrap(bound
.dim
);
219 nvar
= isl_space_dim(bound
.dim
, isl_dim_out
);
220 bound
.dim
= isl_space_domain(bound
.dim
);
225 return isl_pw_qpolynomial_fold_reset_space(pwf
, bound
.dim
);
228 if (isl_pw_qpolynomial_fold_is_zero(pwf
)) {
229 enum isl_fold type
= pwf
->type
;
230 isl_pw_qpolynomial_fold_free(pwf
);
233 return isl_pw_qpolynomial_fold_zero(bound
.dim
, type
);
236 bound
.pwf
= isl_pw_qpolynomial_fold_zero(isl_space_copy(bound
.dim
),
238 bound
.pwf_tight
= isl_pw_qpolynomial_fold_zero(isl_space_copy(bound
.dim
),
240 bound
.check_tight
= !!tight
;
242 if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf
,
243 guarded_fold
, &bound
) < 0)
246 covers
= isl_pw_qpolynomial_fold_covers(bound
.pwf_tight
, bound
.pwf
);
253 isl_space_free(bound
.dim
);
254 isl_pw_qpolynomial_fold_free(pwf
);
257 isl_pw_qpolynomial_fold_free(bound
.pwf
);
258 return bound
.pwf_tight
;
261 bound
.pwf
= isl_pw_qpolynomial_fold_fold(bound
.pwf
, bound
.pwf_tight
);
265 isl_pw_qpolynomial_fold_free(bound
.pwf_tight
);
266 isl_pw_qpolynomial_fold_free(bound
.pwf
);
267 isl_pw_qpolynomial_fold_free(pwf
);
268 isl_space_free(bound
.dim
);
272 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_bound(
273 __isl_take isl_pw_qpolynomial
*pwqp
, enum isl_fold type
, int *tight
)
275 isl_pw_qpolynomial_fold
*pwf
;
277 pwf
= isl_pw_qpolynomial_fold_from_pw_qpolynomial(type
, pwqp
);
278 return isl_pw_qpolynomial_fold_bound(pwf
, tight
);
281 struct isl_union_bound_data
{
284 isl_union_pw_qpolynomial_fold
*res
;
287 static int bound_pw(__isl_take isl_pw_qpolynomial
*pwqp
, void *user
)
289 struct isl_union_bound_data
*data
= user
;
290 isl_pw_qpolynomial_fold
*pwf
;
292 pwf
= isl_pw_qpolynomial_bound(pwqp
, data
->type
,
293 data
->tight
? &data
->tight
: NULL
);
294 data
->res
= isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
300 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_bound(
301 __isl_take isl_union_pw_qpolynomial
*upwqp
,
302 enum isl_fold type
, int *tight
)
305 struct isl_union_bound_data data
= { type
, 1, NULL
};
313 dim
= isl_union_pw_qpolynomial_get_space(upwqp
);
314 data
.res
= isl_union_pw_qpolynomial_fold_zero(dim
, type
);
315 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp
,
316 &bound_pw
, &data
) < 0)
319 isl_union_pw_qpolynomial_free(upwqp
);
325 isl_union_pw_qpolynomial_free(upwqp
);
326 isl_union_pw_qpolynomial_fold_free(data
.res
);