1/*
2 * Copyright 2010      INRIA Saclay
3 *
4 * Use of this software is governed by the MIT 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 */
26static 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);
45error:
46	isl_basic_set_free(bset);
47	isl_qpolynomial_free(poly);
48	return -1;
49}
50
51static 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;
102error:
103	isl_basic_set_free(bset);
104	isl_qpolynomial_free(poly);
105	return -1;
106}
107
108static 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
156static 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
167static 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
179static 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;
199error:
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;
267error:
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
284struct isl_union_bound_data {
285	enum isl_fold type;
286	int tight;
287	isl_union_pw_qpolynomial_fold *res;
288};
289
290static 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;
327error:
328	isl_union_pw_qpolynomial_free(upwqp);
329	isl_union_pw_qpolynomial_fold_free(data.res);
330	return NULL;
331}
332