2 * Copyright 2010 INRIA Saclay
4 * Use of this software is governed by the MIT 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>
17 #include <isl_options_private.h>
19 /* Given a polynomial "poly" that is constant in terms
20 * of the domain variables, construct a polynomial reduction
21 * of type "type" that is equal to "poly" on "bset",
22 * with the domain projected onto the parameters.
24 __isl_give isl_pw_qpolynomial_fold
*isl_qpolynomial_cst_bound(
25 __isl_take isl_basic_set
*bset
, __isl_take isl_qpolynomial
*poly
,
26 enum isl_fold type
, isl_bool
*tight
)
29 isl_qpolynomial_fold
*fold
;
30 isl_pw_qpolynomial_fold
*pwf
;
32 fold
= isl_qpolynomial_fold_alloc(type
, poly
);
33 dom
= isl_set_from_basic_set(bset
);
35 *tight
= isl_bool_true
;
36 pwf
= isl_pw_qpolynomial_fold_alloc(type
, dom
, fold
);
37 return isl_pw_qpolynomial_fold_project_domain_on_params(pwf
);
40 /* Add the bound "pwf", which is not known to be tight,
41 * to the output of "bound".
43 isl_stat
isl_bound_add(struct isl_bound
*bound
,
44 __isl_take isl_pw_qpolynomial_fold
*pwf
)
46 bound
->pwf
= isl_pw_qpolynomial_fold_fold(bound
->pwf
, pwf
);
47 return isl_stat_non_null(bound
->pwf
);
50 /* Add the bound "pwf", which is known to be tight,
51 * to the output of "bound".
53 isl_stat
isl_bound_add_tight(struct isl_bound
*bound
,
54 __isl_take isl_pw_qpolynomial_fold
*pwf
)
56 bound
->pwf_tight
= isl_pw_qpolynomial_fold_fold(bound
->pwf_tight
, pwf
);
57 return isl_stat_non_null(bound
->pwf
);
60 /* Compute a bound on the polynomial defined over the parametric polytope
61 * using either range propagation or bernstein expansion and
62 * store the result in bound->pwf and bound->pwf_tight.
63 * Since bernstein expansion requires bounded domains, we apply
64 * range propagation on unbounded domains. Otherwise, we respect the choice
67 static isl_stat
compressed_guarded_poly_bound(__isl_take isl_basic_set
*bset
,
68 __isl_take isl_qpolynomial
*poly
, void *user
)
70 struct isl_bound
*bound
= (struct isl_bound
*)user
;
77 ctx
= isl_basic_set_get_ctx(bset
);
78 if (ctx
->opt
->bound
== ISL_BOUND_RANGE
)
79 return isl_qpolynomial_bound_on_domain_range(bset
, poly
, bound
);
81 bounded
= isl_basic_set_is_bounded(bset
);
85 return isl_qpolynomial_bound_on_domain_bernstein(bset
, poly
, bound
);
87 return isl_qpolynomial_bound_on_domain_range(bset
, poly
, bound
);
89 isl_basic_set_free(bset
);
90 isl_qpolynomial_free(poly
);
91 return isl_stat_error
;
94 static isl_stat
unwrapped_guarded_poly_bound(__isl_take isl_basic_set
*bset
,
95 __isl_take isl_qpolynomial
*poly
, void *user
)
97 struct isl_bound
*bound
= (struct isl_bound
*)user
;
98 isl_pw_qpolynomial_fold
*top_pwf
;
99 isl_pw_qpolynomial_fold
*top_pwf_tight
;
104 bset
= isl_basic_set_detect_equalities(bset
);
110 return compressed_guarded_poly_bound(bset
, poly
, user
);
112 morph
= isl_basic_set_full_compression(bset
);
114 bset
= isl_morph_basic_set(isl_morph_copy(morph
), bset
);
115 poly
= isl_qpolynomial_morph_domain(poly
, isl_morph_copy(morph
));
117 space
= isl_morph_get_ran_space(morph
);
118 space
= isl_space_params(space
);
120 top_pwf
= bound
->pwf
;
121 top_pwf_tight
= bound
->pwf_tight
;
123 space
= isl_space_from_domain(space
);
124 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
125 bound
->pwf
= isl_pw_qpolynomial_fold_zero(isl_space_copy(space
),
127 bound
->pwf_tight
= isl_pw_qpolynomial_fold_zero(space
, bound
->type
);
129 r
= compressed_guarded_poly_bound(bset
, poly
, user
);
131 morph
= isl_morph_dom_params(morph
);
132 morph
= isl_morph_ran_params(morph
);
133 morph
= isl_morph_inverse(morph
);
135 bound
->pwf
= isl_pw_qpolynomial_fold_morph_domain(bound
->pwf
,
136 isl_morph_copy(morph
));
137 bound
->pwf_tight
= isl_pw_qpolynomial_fold_morph_domain(
138 bound
->pwf_tight
, morph
);
140 isl_bound_add(bound
, top_pwf
);
141 isl_bound_add_tight(bound
, top_pwf_tight
);
145 isl_basic_set_free(bset
);
146 isl_qpolynomial_free(poly
);
147 return isl_stat_error
;
150 /* Update bound->pwf and bound->pwf_tight with a bound
151 * of type bound->type on the polynomial "poly" over the domain "bset".
153 * If the original problem had a wrapped relation in the domain,
154 * meaning that the bound should be computed over the range
155 * of this relation, then temporarily treat the domain dimensions
156 * of this wrapped relation as parameters, compute a bound
157 * in terms of these and the original parameters,
158 * turn the parameters back into set dimensions and
159 * add the results to bound->pwf and bound->pwf_tight.
161 * Note that even though "bset" is known to live in the same space
162 * as the domain of "poly", the names of the set dimensions
163 * may be different (or missing). Make sure the naming is exactly
164 * the same before turning these dimensions into parameters
165 * to ensure that the spaces are still the same after
168 static isl_stat
guarded_poly_bound(__isl_take isl_basic_set
*bset
,
169 __isl_take isl_qpolynomial
*poly
, void *user
)
171 struct isl_bound
*bound
= (struct isl_bound
*)user
;
173 isl_pw_qpolynomial_fold
*top_pwf
;
174 isl_pw_qpolynomial_fold
*top_pwf_tight
;
179 if (!bound
->wrapping
)
180 return unwrapped_guarded_poly_bound(bset
, poly
, user
);
182 nparam
= isl_space_dim(bound
->dim
, isl_dim_param
);
183 n_in
= isl_space_dim(bound
->dim
, isl_dim_in
);
184 if (nparam
< 0 || n_in
< 0)
187 space
= isl_qpolynomial_get_domain_space(poly
);
188 bset
= isl_basic_set_reset_space(bset
, space
);
190 bset
= isl_basic_set_move_dims(bset
, isl_dim_param
, nparam
,
191 isl_dim_set
, 0, n_in
);
192 poly
= isl_qpolynomial_move_dims(poly
, isl_dim_param
, nparam
,
193 isl_dim_in
, 0, n_in
);
195 space
= isl_basic_set_get_space(bset
);
196 space
= isl_space_params(space
);
198 top_pwf
= bound
->pwf
;
199 top_pwf_tight
= bound
->pwf_tight
;
201 space
= isl_space_from_domain(space
);
202 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
203 bound
->pwf
= isl_pw_qpolynomial_fold_zero(isl_space_copy(space
),
205 bound
->pwf_tight
= isl_pw_qpolynomial_fold_zero(space
, bound
->type
);
207 r
= unwrapped_guarded_poly_bound(bset
, poly
, user
);
209 bound
->pwf
= isl_pw_qpolynomial_fold_reset_space(bound
->pwf
,
210 isl_space_copy(bound
->dim
));
211 bound
->pwf_tight
= isl_pw_qpolynomial_fold_reset_space(bound
->pwf_tight
,
212 isl_space_copy(bound
->dim
));
214 isl_bound_add(bound
, top_pwf
);
215 isl_bound_add_tight(bound
, top_pwf_tight
);
219 isl_basic_set_free(bset
);
220 isl_qpolynomial_free(poly
);
221 return isl_stat_error
;
224 static isl_stat
guarded_qp(__isl_take isl_qpolynomial
*qp
, void *user
)
226 struct isl_bound
*bound
= (struct isl_bound
*)user
;
229 r
= isl_qpolynomial_as_polynomial_on_domain(qp
, bound
->bset
,
230 &guarded_poly_bound
, user
);
231 isl_qpolynomial_free(qp
);
235 static isl_stat
basic_guarded_fold(__isl_take isl_basic_set
*bset
, void *user
)
237 struct isl_bound
*bound
= (struct isl_bound
*)user
;
241 r
= isl_qpolynomial_fold_foreach_qpolynomial(bound
->fold
,
243 isl_basic_set_free(bset
);
247 static isl_stat
guarded_fold(__isl_take isl_set
*set
,
248 __isl_take isl_qpolynomial_fold
*fold
, void *user
)
250 struct isl_bound
*bound
= (struct isl_bound
*)user
;
255 set
= isl_set_make_disjoint(set
);
258 bound
->type
= isl_qpolynomial_fold_get_type(fold
);
260 if (isl_set_foreach_basic_set(set
, &basic_guarded_fold
, bound
) < 0)
264 isl_qpolynomial_fold_free(fold
);
269 isl_qpolynomial_fold_free(fold
);
270 return isl_stat_error
;
273 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_bound(
274 __isl_take isl_pw_qpolynomial_fold
*pwf
, isl_bool
*tight
)
277 struct isl_bound bound
;
283 bound
.dim
= isl_pw_qpolynomial_fold_get_domain_space(pwf
);
285 bound
.wrapping
= isl_space_is_wrapping(bound
.dim
);
287 bound
.dim
= isl_space_unwrap(bound
.dim
);
288 nvar
= isl_space_dim(bound
.dim
, isl_dim_out
);
290 bound
.dim
= isl_space_free(bound
.dim
);
291 bound
.dim
= isl_space_domain(bound
.dim
);
292 bound
.dim
= isl_space_from_domain(bound
.dim
);
293 bound
.dim
= isl_space_add_dims(bound
.dim
, isl_dim_out
, 1);
297 *tight
= isl_bool_true
;
298 return isl_pw_qpolynomial_fold_reset_space(pwf
, bound
.dim
);
301 if (isl_pw_qpolynomial_fold_is_zero(pwf
)) {
302 enum isl_fold type
= pwf
->type
;
303 isl_pw_qpolynomial_fold_free(pwf
);
305 *tight
= isl_bool_true
;
306 return isl_pw_qpolynomial_fold_zero(bound
.dim
, type
);
309 bound
.pwf
= isl_pw_qpolynomial_fold_zero(isl_space_copy(bound
.dim
),
311 bound
.pwf_tight
= isl_pw_qpolynomial_fold_zero(isl_space_copy(bound
.dim
),
313 bound
.check_tight
= !!tight
;
315 if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf
,
316 guarded_fold
, &bound
) < 0)
319 covers
= isl_pw_qpolynomial_fold_covers(bound
.pwf_tight
, bound
.pwf
);
326 isl_space_free(bound
.dim
);
327 isl_pw_qpolynomial_fold_free(pwf
);
330 isl_pw_qpolynomial_fold_free(bound
.pwf
);
331 return bound
.pwf_tight
;
334 bound
.pwf
= isl_pw_qpolynomial_fold_fold(bound
.pwf
, bound
.pwf_tight
);
338 isl_pw_qpolynomial_fold_free(bound
.pwf_tight
);
339 isl_pw_qpolynomial_fold_free(bound
.pwf
);
340 isl_pw_qpolynomial_fold_free(pwf
);
341 isl_space_free(bound
.dim
);
345 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_bound(
346 __isl_take isl_pw_qpolynomial
*pwqp
, enum isl_fold type
,
349 isl_pw_qpolynomial_fold
*pwf
;
351 pwf
= isl_pw_qpolynomial_fold_from_pw_qpolynomial(type
, pwqp
);
352 return isl_pw_qpolynomial_fold_bound(pwf
, tight
);
355 struct isl_union_bound_data
{
358 isl_union_pw_qpolynomial_fold
*res
;
361 static isl_stat
bound_pw(__isl_take isl_pw_qpolynomial
*pwqp
, void *user
)
363 struct isl_union_bound_data
*data
= user
;
364 isl_pw_qpolynomial_fold
*pwf
;
366 pwf
= isl_pw_qpolynomial_bound(pwqp
, data
->type
,
367 data
->tight
? &data
->tight
: NULL
);
368 data
->res
= isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
374 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_bound(
375 __isl_take isl_union_pw_qpolynomial
*upwqp
,
376 enum isl_fold type
, isl_bool
*tight
)
379 struct isl_union_bound_data data
= { type
, 1, NULL
};
385 data
.tight
= isl_bool_false
;
387 space
= isl_union_pw_qpolynomial_get_space(upwqp
);
388 data
.res
= isl_union_pw_qpolynomial_fold_zero(space
, type
);
389 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp
,
390 &bound_pw
, &data
) < 0)
393 isl_union_pw_qpolynomial_free(upwqp
);
399 isl_union_pw_qpolynomial_free(upwqp
);
400 isl_union_pw_qpolynomial_fold_free(data
.res
);