nexmon – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /*
2 * Copyright 2010 INRIA Saclay
3 *
4 * Use of this software is governed by the GNU LGPLv2.1 license
5 *
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 */
10  
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>
18  
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.
25 */
26 static int compressed_guarded_poly_bound(__isl_take isl_basic_set *bset,
27 __isl_take isl_qpolynomial *poly, void *user)
28 {
29 struct isl_bound *bound = (struct isl_bound *)user;
30 int bounded;
31  
32 if (!bset || !poly)
33 goto error;
34  
35 if (bset->ctx->opt->bound == ISL_BOUND_RANGE)
36 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
37  
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;
49 }
50  
51 static int unwrapped_guarded_poly_bound(__isl_take isl_basic_set *bset,
52 __isl_take isl_qpolynomial *poly, void *user)
53 {
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;
60  
61 bset = isl_basic_set_detect_equalities(bset);
62  
63 if (!bset)
64 goto error;
65  
66 if (bset->n_eq == 0)
67 return compressed_guarded_poly_bound(bset, poly, user);
68  
69 morph = isl_basic_set_full_compression(bset);
70  
71 bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
72 poly = isl_qpolynomial_morph_domain(poly, isl_morph_copy(morph));
73  
74 dim = isl_morph_get_ran_space(morph);
75 dim = isl_space_params(dim);
76  
77 top_pwf = bound->pwf;
78 top_pwf_tight = bound->pwf_tight;
79  
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);
85  
86 r = compressed_guarded_poly_bound(bset, poly, user);
87  
88 morph = isl_morph_dom_params(morph);
89 morph = isl_morph_ran_params(morph);
90 morph = isl_morph_inverse(morph);
91  
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);
96  
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);
100  
101 return r;
102 error:
103 isl_basic_set_free(bset);
104 isl_qpolynomial_free(poly);
105 return -1;
106 }
107  
108 static int guarded_poly_bound(__isl_take isl_basic_set *bset,
109 __isl_take isl_qpolynomial *poly, void *user)
110 {
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;
118  
119 if (!bound->wrapping)
120 return unwrapped_guarded_poly_bound(bset, poly, user);
121  
122 nparam = isl_space_dim(bound->dim, isl_dim_param);
123 n_in = isl_space_dim(bound->dim, isl_dim_in);
124  
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);
129  
130 dim = isl_basic_set_get_space(bset);
131 dim = isl_space_params(dim);
132  
133 top_pwf = bound->pwf;
134 top_pwf_tight = bound->pwf_tight;
135  
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);
141  
142 r = unwrapped_guarded_poly_bound(bset, poly, user);
143  
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));
148  
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);
152  
153 return r;
154 }
155  
156 static int guarded_qp(__isl_take isl_qpolynomial *qp, void *user)
157 {
158 struct isl_bound *bound = (struct isl_bound *)user;
159 int r;
160  
161 r = isl_qpolynomial_as_polynomial_on_domain(qp, bound->bset,
162 &guarded_poly_bound, user);
163 isl_qpolynomial_free(qp);
164 return r;
165 }
166  
167 static int basic_guarded_fold(__isl_take isl_basic_set *bset, void *user)
168 {
169 struct isl_bound *bound = (struct isl_bound *)user;
170 int r;
171  
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;
177 }
178  
179 static int guarded_fold(__isl_take isl_set *set,
180 __isl_take isl_qpolynomial_fold *fold, void *user)
181 {
182 struct isl_bound *bound = (struct isl_bound *)user;
183  
184 if (!set || !fold)
185 goto error;
186  
187 set = isl_set_make_disjoint(set);
188  
189 bound->fold = fold;
190 bound->type = isl_qpolynomial_fold_get_type(fold);
191  
192 if (isl_set_foreach_basic_set(set, &basic_guarded_fold, bound) < 0)
193 goto error;
194  
195 isl_set_free(set);
196 isl_qpolynomial_fold_free(fold);
197  
198 return 0;
199 error:
200 isl_set_free(set);
201 isl_qpolynomial_fold_free(fold);
202 return -1;
203 }
204  
205 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
206 __isl_take isl_pw_qpolynomial_fold *pwf, int *tight)
207 {
208 unsigned nvar;
209 struct isl_bound bound;
210 int covers;
211  
212 if (!pwf)
213 return NULL;
214  
215 bound.dim = isl_pw_qpolynomial_fold_get_domain_space(pwf);
216  
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);
224  
225 if (nvar == 0) {
226 if (tight)
227 *tight = 1;
228 return isl_pw_qpolynomial_fold_reset_space(pwf, bound.dim);
229 }
230  
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);
237 }
238  
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;
244  
245 if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,
246 guarded_fold, &bound) < 0)
247 goto error;
248  
249 covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);
250 if (covers < 0)
251 goto error;
252  
253 if (tight)
254 *tight = covers;
255  
256 isl_space_free(bound.dim);
257 isl_pw_qpolynomial_fold_free(pwf);
258  
259 if (covers) {
260 isl_pw_qpolynomial_fold_free(bound.pwf);
261 return bound.pwf_tight;
262 }
263  
264 bound.pwf = isl_pw_qpolynomial_fold_fold(bound.pwf, bound.pwf_tight);
265  
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;
273 }
274  
275 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
276 __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type, int *tight)
277 {
278 isl_pw_qpolynomial_fold *pwf;
279  
280 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
281 return isl_pw_qpolynomial_fold_bound(pwf, tight);
282 }
283  
284 struct isl_union_bound_data {
285 enum isl_fold type;
286 int tight;
287 isl_union_pw_qpolynomial_fold *res;
288 };
289  
290 static int bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)
291 {
292 struct isl_union_bound_data *data = user;
293 isl_pw_qpolynomial_fold *pwf;
294  
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);
299  
300 return 0;
301 }
302  
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)
306 {
307 isl_space *dim;
308 struct isl_union_bound_data data = { type, 1, NULL };
309  
310 if (!upwqp)
311 return NULL;
312  
313 if (!tight)
314 data.tight = 0;
315  
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;
321  
322 isl_union_pw_qpolynomial_free(upwqp);
323 if (tight)
324 *tight = data.tight;
325  
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;
331 }