add isl_schedule_node_gist
[isl.git] / isl_bound.c
blob04c76a0ffb23e965c78dcc2ebb5927088546fcae
1 /*
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,
8 * 91893 Orsay, France
9 */
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 /* Compute a bound on the polynomial defined over the parametric polytope
20 * using either range propagation or bernstein expansion and
21 * store the result in bound->pwf and bound->pwf_tight.
22 * Since bernstein expansion requires bounded domains, we apply
23 * range propagation on unbounded domains. Otherwise, we respect the choice
24 * of the user.
26 static int compressed_guarded_poly_bound(__isl_take isl_basic_set *bset,
27 __isl_take isl_qpolynomial *poly, void *user)
29 struct isl_bound *bound = (struct isl_bound *)user;
30 int bounded;
32 if (!bset || !poly)
33 goto error;
35 if (bset->ctx->opt->bound == ISL_BOUND_RANGE)
36 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
38 bounded = isl_basic_set_is_bounded(bset);
39 if (bounded < 0)
40 goto error;
41 if (bounded)
42 return isl_qpolynomial_bound_on_domain_bernstein(bset, poly, bound);
43 else
44 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
45 error:
46 isl_basic_set_free(bset);
47 isl_qpolynomial_free(poly);
48 return -1;
51 static int unwrapped_guarded_poly_bound(__isl_take isl_basic_set *bset,
52 __isl_take isl_qpolynomial *poly, void *user)
54 struct isl_bound *bound = (struct isl_bound *)user;
55 isl_pw_qpolynomial_fold *top_pwf;
56 isl_pw_qpolynomial_fold *top_pwf_tight;
57 isl_space *dim;
58 isl_morph *morph;
59 int r;
61 bset = isl_basic_set_detect_equalities(bset);
63 if (!bset)
64 goto error;
66 if (bset->n_eq == 0)
67 return compressed_guarded_poly_bound(bset, poly, user);
69 morph = isl_basic_set_full_compression(bset);
71 bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
72 poly = isl_qpolynomial_morph_domain(poly, isl_morph_copy(morph));
74 dim = isl_morph_get_ran_space(morph);
75 dim = isl_space_params(dim);
77 top_pwf = bound->pwf;
78 top_pwf_tight = bound->pwf_tight;
80 dim = isl_space_from_domain(dim);
81 dim = isl_space_add_dims(dim, isl_dim_out, 1);
82 bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(dim),
83 bound->type);
84 bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim, bound->type);
86 r = compressed_guarded_poly_bound(bset, poly, user);
88 morph = isl_morph_dom_params(morph);
89 morph = isl_morph_ran_params(morph);
90 morph = isl_morph_inverse(morph);
92 bound->pwf = isl_pw_qpolynomial_fold_morph_domain(bound->pwf,
93 isl_morph_copy(morph));
94 bound->pwf_tight = isl_pw_qpolynomial_fold_morph_domain(
95 bound->pwf_tight, morph);
97 bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
98 bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
99 bound->pwf_tight);
101 return r;
102 error:
103 isl_basic_set_free(bset);
104 isl_qpolynomial_free(poly);
105 return -1;
108 static int guarded_poly_bound(__isl_take isl_basic_set *bset,
109 __isl_take isl_qpolynomial *poly, void *user)
111 struct isl_bound *bound = (struct isl_bound *)user;
112 isl_space *dim;
113 isl_pw_qpolynomial_fold *top_pwf;
114 isl_pw_qpolynomial_fold *top_pwf_tight;
115 int nparam;
116 int n_in;
117 int r;
119 if (!bound->wrapping)
120 return unwrapped_guarded_poly_bound(bset, poly, user);
122 nparam = isl_space_dim(bound->dim, isl_dim_param);
123 n_in = isl_space_dim(bound->dim, isl_dim_in);
125 bset = isl_basic_set_move_dims(bset, isl_dim_param, nparam,
126 isl_dim_set, 0, n_in);
127 poly = isl_qpolynomial_move_dims(poly, isl_dim_param, nparam,
128 isl_dim_in, 0, n_in);
130 dim = isl_basic_set_get_space(bset);
131 dim = isl_space_params(dim);
133 top_pwf = bound->pwf;
134 top_pwf_tight = bound->pwf_tight;
136 dim = isl_space_from_domain(dim);
137 dim = isl_space_add_dims(dim, isl_dim_out, 1);
138 bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(dim),
139 bound->type);
140 bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim, bound->type);
142 r = unwrapped_guarded_poly_bound(bset, poly, user);
144 bound->pwf = isl_pw_qpolynomial_fold_reset_space(bound->pwf,
145 isl_space_copy(bound->dim));
146 bound->pwf_tight = isl_pw_qpolynomial_fold_reset_space(bound->pwf_tight,
147 isl_space_copy(bound->dim));
149 bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
150 bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
151 bound->pwf_tight);
153 return r;
156 static int guarded_qp(__isl_take isl_qpolynomial *qp, void *user)
158 struct isl_bound *bound = (struct isl_bound *)user;
159 int r;
161 r = isl_qpolynomial_as_polynomial_on_domain(qp, bound->bset,
162 &guarded_poly_bound, user);
163 isl_qpolynomial_free(qp);
164 return r;
167 static int basic_guarded_fold(__isl_take isl_basic_set *bset, void *user)
169 struct isl_bound *bound = (struct isl_bound *)user;
170 int r;
172 bound->bset = bset;
173 r = isl_qpolynomial_fold_foreach_qpolynomial(bound->fold,
174 &guarded_qp, user);
175 isl_basic_set_free(bset);
176 return r;
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;
184 if (!set || !fold)
185 goto error;
187 set = isl_set_make_disjoint(set);
189 bound->fold = fold;
190 bound->type = isl_qpolynomial_fold_get_type(fold);
192 if (isl_set_foreach_basic_set(set, &basic_guarded_fold, bound) < 0)
193 goto error;
195 isl_set_free(set);
196 isl_qpolynomial_fold_free(fold);
198 return 0;
199 error:
200 isl_set_free(set);
201 isl_qpolynomial_fold_free(fold);
202 return -1;
205 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
206 __isl_take isl_pw_qpolynomial_fold *pwf, int *tight)
208 unsigned nvar;
209 struct isl_bound bound;
210 int covers;
212 if (!pwf)
213 return NULL;
215 bound.dim = isl_pw_qpolynomial_fold_get_domain_space(pwf);
217 bound.wrapping = isl_space_is_wrapping(bound.dim);
218 if (bound.wrapping)
219 bound.dim = isl_space_unwrap(bound.dim);
220 nvar = isl_space_dim(bound.dim, isl_dim_out);
221 bound.dim = isl_space_domain(bound.dim);
222 bound.dim = isl_space_from_domain(bound.dim);
223 bound.dim = isl_space_add_dims(bound.dim, isl_dim_out, 1);
225 if (nvar == 0) {
226 if (tight)
227 *tight = 1;
228 return isl_pw_qpolynomial_fold_reset_space(pwf, bound.dim);
231 if (isl_pw_qpolynomial_fold_is_zero(pwf)) {
232 enum isl_fold type = pwf->type;
233 isl_pw_qpolynomial_fold_free(pwf);
234 if (tight)
235 *tight = 1;
236 return isl_pw_qpolynomial_fold_zero(bound.dim, type);
239 bound.pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
240 pwf->type);
241 bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
242 pwf->type);
243 bound.check_tight = !!tight;
245 if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,
246 guarded_fold, &bound) < 0)
247 goto error;
249 covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);
250 if (covers < 0)
251 goto error;
253 if (tight)
254 *tight = covers;
256 isl_space_free(bound.dim);
257 isl_pw_qpolynomial_fold_free(pwf);
259 if (covers) {
260 isl_pw_qpolynomial_fold_free(bound.pwf);
261 return bound.pwf_tight;
264 bound.pwf = isl_pw_qpolynomial_fold_fold(bound.pwf, bound.pwf_tight);
266 return bound.pwf;
267 error:
268 isl_pw_qpolynomial_fold_free(bound.pwf_tight);
269 isl_pw_qpolynomial_fold_free(bound.pwf);
270 isl_pw_qpolynomial_fold_free(pwf);
271 isl_space_free(bound.dim);
272 return NULL;
275 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
276 __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type, int *tight)
278 isl_pw_qpolynomial_fold *pwf;
280 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
281 return isl_pw_qpolynomial_fold_bound(pwf, tight);
284 struct isl_union_bound_data {
285 enum isl_fold type;
286 int tight;
287 isl_union_pw_qpolynomial_fold *res;
290 static int bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)
292 struct isl_union_bound_data *data = user;
293 isl_pw_qpolynomial_fold *pwf;
295 pwf = isl_pw_qpolynomial_bound(pwqp, data->type,
296 data->tight ? &data->tight : NULL);
297 data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
298 data->res, pwf);
300 return 0;
303 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
304 __isl_take isl_union_pw_qpolynomial *upwqp,
305 enum isl_fold type, int *tight)
307 isl_space *dim;
308 struct isl_union_bound_data data = { type, 1, NULL };
310 if (!upwqp)
311 return NULL;
313 if (!tight)
314 data.tight = 0;
316 dim = isl_union_pw_qpolynomial_get_space(upwqp);
317 data.res = isl_union_pw_qpolynomial_fold_zero(dim, type);
318 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp,
319 &bound_pw, &data) < 0)
320 goto error;
322 isl_union_pw_qpolynomial_free(upwqp);
323 if (tight)
324 *tight = data.tight;
326 return data.res;
327 error:
328 isl_union_pw_qpolynomial_free(upwqp);
329 isl_union_pw_qpolynomial_fold_free(data.res);
330 return NULL;