merge isl_basic_set/isl_basic_map and isl_set/isl_map
[platform/upstream/isl.git] / isl_bound.c
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_map_private.h>
12 #include <isl_bound.h>
13 #include <isl_bernstein.h>
14 #include <isl_range.h>
15 #include <isl_polynomial_private.h>
16
17 /* Compute a bound on the polynomial defined over the parametric polytope
18  * using either range propagation or bernstein expansion and
19  * store the result in bound->pwf and bound->pwf_tight.
20  * Since bernstein expansion requires bounded domains, we apply
21  * range propagation on unbounded domains.  Otherwise, we respect the choice
22  * of the user.
23  */
24 static int compressed_guarded_poly_bound(__isl_take isl_basic_set *bset,
25         __isl_take isl_qpolynomial *poly, void *user)
26 {
27         struct isl_bound *bound = (struct isl_bound *)user;
28         int bounded;
29
30         if (!bset || !poly)
31                 goto error;
32
33         if (bset->ctx->opt->bound == ISL_BOUND_RANGE)
34                 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
35
36         bounded = isl_basic_set_is_bounded(bset);
37         if (bounded < 0)
38                 goto error;
39         if (bounded)
40                 return isl_qpolynomial_bound_on_domain_bernstein(bset, poly, bound);
41         else
42                 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
43 error:
44         isl_basic_set_free(bset);
45         isl_qpolynomial_free(poly);
46         return -1;
47 }
48
49 static int unwrapped_guarded_poly_bound(__isl_take isl_basic_set *bset,
50         __isl_take isl_qpolynomial *poly, void *user)
51 {
52         struct isl_bound *bound = (struct isl_bound *)user;
53         isl_pw_qpolynomial_fold *top_pwf;
54         isl_pw_qpolynomial_fold *top_pwf_tight;
55         isl_dim *dim;
56         isl_morph *morph;
57         unsigned orig_nvar, final_nvar;
58         int r;
59
60         bset = isl_basic_set_detect_equalities(bset);
61
62         if (!bset)
63                 goto error;
64
65         if (bset->n_eq == 0)
66                 return compressed_guarded_poly_bound(bset, poly, user);
67
68         orig_nvar = isl_basic_set_dim(bset, isl_dim_set);
69
70         morph = isl_basic_set_full_compression(bset);
71
72         bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
73         poly = isl_qpolynomial_morph(poly, isl_morph_copy(morph));
74
75         final_nvar = isl_basic_set_dim(bset, isl_dim_set);
76
77         dim = isl_morph_get_ran_dim(morph);
78         dim = isl_dim_drop(dim, isl_dim_set, 0, isl_dim_size(dim, isl_dim_set));
79
80         top_pwf = bound->pwf;
81         top_pwf_tight = bound->pwf_tight;
82
83         bound->pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim),
84                                                   bound->type);
85         bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim, bound->type);
86
87         r = compressed_guarded_poly_bound(bset, poly, user);
88
89         morph = isl_morph_remove_dom_dims(morph, isl_dim_set, 0, orig_nvar);
90         morph = isl_morph_remove_ran_dims(morph, isl_dim_set, 0, final_nvar);
91         morph = isl_morph_inverse(morph);
92
93         bound->pwf = isl_pw_qpolynomial_fold_morph(bound->pwf,
94                                                         isl_morph_copy(morph));
95         bound->pwf_tight = isl_pw_qpolynomial_fold_morph(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_dim *dim;
113         isl_dim *target_dim;
114         isl_pw_qpolynomial_fold *top_pwf;
115         isl_pw_qpolynomial_fold *top_pwf_tight;
116         int nparam;
117         int n_in;
118         int r;
119
120         if (!isl_basic_set_is_wrapping(bset))
121                 return unwrapped_guarded_poly_bound(bset, poly, user);
122
123         target_dim = isl_basic_set_get_dim(bset);
124         target_dim = isl_dim_unwrap(target_dim);
125         target_dim = isl_dim_domain(target_dim);
126
127         nparam = isl_dim_size(target_dim, isl_dim_param);
128         n_in = isl_dim_size(target_dim, isl_dim_set);
129
130         bset = isl_basic_set_move_dims(bset, isl_dim_param, nparam,
131                                         isl_dim_set, 0, n_in);
132         poly = isl_qpolynomial_move_dims(poly, isl_dim_param, nparam,
133                                         isl_dim_set, 0, n_in);
134
135         dim = isl_basic_set_get_dim(bset);
136         dim = isl_dim_drop(dim, isl_dim_set, 0, isl_dim_size(dim, isl_dim_set));
137
138         top_pwf = bound->pwf;
139         top_pwf_tight = bound->pwf_tight;
140
141         bound->pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim),
142                                                   bound->type);
143         bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim, bound->type);
144
145         r = unwrapped_guarded_poly_bound(bset, poly, user);
146
147         bound->pwf = isl_pw_qpolynomial_fold_reset_dim(bound->pwf,
148                                                     isl_dim_copy(target_dim));
149         bound->pwf_tight = isl_pw_qpolynomial_fold_reset_dim(bound->pwf_tight,
150                                                     target_dim);
151
152         bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
153         bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
154                                                         bound->pwf_tight);
155
156         return r;
157 }
158
159 static int guarded_qp(__isl_take isl_qpolynomial *qp, void *user)
160 {
161         struct isl_bound *bound = (struct isl_bound *)user;
162         int r;
163
164         r = isl_qpolynomial_as_polynomial_on_domain(qp, bound->bset,
165                                                     &guarded_poly_bound, user);
166         isl_qpolynomial_free(qp);
167         return r;
168 }
169
170 static int basic_guarded_fold(__isl_take isl_basic_set *bset, void *user)
171 {
172         struct isl_bound *bound = (struct isl_bound *)user;
173         int r;
174
175         bound->bset = bset;
176         r = isl_qpolynomial_fold_foreach_qpolynomial(bound->fold,
177                                                         &guarded_qp, user);
178         isl_basic_set_free(bset);
179         return r;
180 }
181
182 static int guarded_fold(__isl_take isl_set *set,
183         __isl_take isl_qpolynomial_fold *fold, void *user)
184 {
185         struct isl_bound *bound = (struct isl_bound *)user;
186
187         if (!set || !fold)
188                 goto error;
189
190         set = isl_set_make_disjoint(set);
191
192         bound->fold = fold;
193         bound->type = isl_qpolynomial_fold_get_type(fold);
194
195         if (isl_set_foreach_basic_set(set, &basic_guarded_fold, bound) < 0)
196                 goto error;
197
198         isl_set_free(set);
199         isl_qpolynomial_fold_free(fold);
200
201         return 0;
202 error:
203         isl_set_free(set);
204         isl_qpolynomial_fold_free(fold);
205         return -1;
206 }
207
208 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
209         __isl_take isl_pw_qpolynomial_fold *pwf, int *tight)
210 {
211         isl_dim *dim;
212         unsigned nvar;
213         struct isl_bound bound;
214         int covers;
215
216         if (!pwf)
217                 return NULL;
218
219         dim = isl_pw_qpolynomial_fold_get_dim(pwf);
220         nvar = isl_dim_size(dim, isl_dim_set);
221
222         if (isl_dim_is_wrapping(dim)) {
223                 dim = isl_dim_unwrap(dim);
224                 nvar = isl_dim_size(dim, isl_dim_out);
225                 dim = isl_dim_domain(dim);
226         } else
227                 dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
228
229         if (nvar == 0) {
230                 if (tight)
231                         *tight = 1;
232                 return isl_pw_qpolynomial_fold_reset_dim(pwf, dim);
233         }
234
235         if (isl_pw_qpolynomial_fold_is_zero(pwf)) {
236                 enum isl_fold type = pwf->type;
237                 isl_pw_qpolynomial_fold_free(pwf);
238                 if (tight)
239                         *tight = 1;
240                 return isl_pw_qpolynomial_fold_zero(dim, type);
241         }
242
243         bound.pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim), pwf->type);
244         bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim),
245                                                         pwf->type);
246         bound.check_tight = !!tight;
247
248         if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,
249                                                         guarded_fold, &bound) < 0)
250                 goto error;
251
252         covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);
253         if (covers < 0)
254                 goto error;
255
256         if (tight)
257                 *tight = covers;
258
259         isl_dim_free(dim);
260         isl_pw_qpolynomial_fold_free(pwf);
261
262         if (covers) {
263                 isl_pw_qpolynomial_fold_free(bound.pwf);
264                 return bound.pwf_tight;
265         }
266
267         bound.pwf = isl_pw_qpolynomial_fold_fold(bound.pwf, bound.pwf_tight);
268
269         return bound.pwf;
270 error:
271         isl_pw_qpolynomial_fold_free(bound.pwf_tight);
272         isl_pw_qpolynomial_fold_free(bound.pwf);
273         isl_pw_qpolynomial_fold_free(pwf);
274         isl_dim_free(dim);
275         return NULL;
276 }
277
278 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
279         __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type, int *tight)
280 {
281         isl_pw_qpolynomial_fold *pwf;
282
283         pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
284         return isl_pw_qpolynomial_fold_bound(pwf, tight);
285 }
286
287 struct isl_union_bound_data {
288         enum isl_fold type;
289         int tight;
290         isl_union_pw_qpolynomial_fold *res;
291 };
292
293 static int bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)
294 {
295         struct isl_union_bound_data *data = user;
296         isl_pw_qpolynomial_fold *pwf;
297
298         pwf = isl_pw_qpolynomial_bound(pwqp, data->type,
299                                         data->tight ? &data->tight : NULL);
300         data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
301                                                                 data->res, pwf);
302
303         return 0;
304 }
305
306 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
307         __isl_take isl_union_pw_qpolynomial *upwqp,
308         enum isl_fold type, int *tight)
309 {
310         isl_dim *dim;
311         struct isl_union_bound_data data = { type, 1, NULL };
312
313         if (!upwqp)
314                 return NULL;
315
316         if (!tight)
317                 data.tight = 0;
318
319         dim = isl_union_pw_qpolynomial_get_dim(upwqp);
320         data.res = isl_union_pw_qpolynomial_fold_zero(dim, type);
321         if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp,
322                                                     &bound_pw, &data) < 0)
323                 goto error;
324
325         isl_union_pw_qpolynomial_free(upwqp);
326         if (tight)
327                 *tight = data.tight;
328
329         return data.res;
330 error:
331         isl_union_pw_qpolynomial_free(upwqp);
332         isl_union_pw_qpolynomial_fold_free(data.res);
333         return NULL;
334 }