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/* 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.
23 */
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)
27{
28	isl_set *dom;
29	isl_qpolynomial_fold *fold;
30	isl_pw_qpolynomial_fold *pwf;
31
32	fold = isl_qpolynomial_fold_alloc(type, poly);
33	dom = isl_set_from_basic_set(bset);
34	if (tight)
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);
38}
39
40/* Add the bound "pwf", which is not known to be tight,
41 * to the output of "bound".
42 */
43isl_stat isl_bound_add(struct isl_bound *bound,
44	__isl_take isl_pw_qpolynomial_fold *pwf)
45{
46	bound->pwf = isl_pw_qpolynomial_fold_fold(bound->pwf, pwf);
47	return isl_stat_non_null(bound->pwf);
48}
49
50/* Add the bound "pwf", which is known to be tight,
51 * to the output of "bound".
52 */
53isl_stat isl_bound_add_tight(struct isl_bound *bound,
54	__isl_take isl_pw_qpolynomial_fold *pwf)
55{
56	bound->pwf_tight = isl_pw_qpolynomial_fold_fold(bound->pwf_tight, pwf);
57	return isl_stat_non_null(bound->pwf);
58}
59
60/* Given a polynomial "poly" that is constant in terms
61 * of the domain variables and the domain "bset",
62 * construct the corresponding polynomial reduction and
63 * add it to the tight bounds of "bound".
64 */
65static isl_stat add_constant_poly(__isl_take isl_basic_set *bset,
66	__isl_take isl_qpolynomial *poly, struct isl_bound *bound)
67{
68	isl_pw_qpolynomial_fold *pwf;
69
70	pwf = isl_qpolynomial_cst_bound(bset, poly, bound->type, NULL);
71	return isl_bound_add_tight(bound, pwf);
72}
73
74/* Compute a bound on the polynomial defined over the parametric polytope
75 * using either range propagation or bernstein expansion and
76 * store the result in bound->pwf and bound->pwf_tight.
77 * Since bernstein expansion requires bounded domains, we apply
78 * range propagation on unbounded domains.  Otherwise, we respect the choice
79 * of the user.
80 *
81 * If the polynomial does not depend on the set variables
82 * then the bound is equal to the polynomial and
83 * it can be added to "bound" directly.
84 */
85static isl_stat compressed_guarded_poly_bound(__isl_take isl_basic_set *bset,
86	__isl_take isl_qpolynomial *poly, void *user)
87{
88	struct isl_bound *bound = (struct isl_bound *)user;
89	isl_ctx *ctx;
90	int bounded;
91	int degree;
92
93	if (!bset || !poly)
94		goto error;
95
96	degree = isl_qpolynomial_degree(poly);
97	if (degree < -1)
98		goto error;
99	if (degree <= 0)
100		return add_constant_poly(bset, poly, bound);
101
102	ctx = isl_basic_set_get_ctx(bset);
103	if (ctx->opt->bound == ISL_BOUND_RANGE)
104		return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
105
106	bounded = isl_basic_set_is_bounded(bset);
107	if (bounded < 0)
108		goto error;
109	if (bounded)
110		return isl_qpolynomial_bound_on_domain_bernstein(bset, poly, bound);
111	else
112		return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
113error:
114	isl_basic_set_free(bset);
115	isl_qpolynomial_free(poly);
116	return isl_stat_error;
117}
118
119static isl_stat unwrapped_guarded_poly_bound(__isl_take isl_basic_set *bset,
120	__isl_take isl_qpolynomial *poly, void *user)
121{
122	struct isl_bound *bound = (struct isl_bound *)user;
123	isl_pw_qpolynomial_fold *top_pwf;
124	isl_pw_qpolynomial_fold *top_pwf_tight;
125	isl_space *space;
126	isl_morph *morph;
127	isl_stat r;
128
129	bset = isl_basic_set_detect_equalities(bset);
130
131	if (!bset)
132		goto error;
133
134	if (bset->n_eq == 0)
135		return compressed_guarded_poly_bound(bset, poly, user);
136
137	morph = isl_basic_set_full_compression(bset);
138
139	bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
140	poly = isl_qpolynomial_morph_domain(poly, isl_morph_copy(morph));
141
142	space = isl_morph_get_ran_space(morph);
143	space = isl_space_params(space);
144
145	top_pwf = bound->pwf;
146	top_pwf_tight = bound->pwf_tight;
147
148	space = isl_space_from_domain(space);
149	space = isl_space_add_dims(space, isl_dim_out, 1);
150	bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(space),
151						  bound->type);
152	bound->pwf_tight = isl_pw_qpolynomial_fold_zero(space, bound->type);
153
154	r = compressed_guarded_poly_bound(bset, poly, user);
155
156	morph = isl_morph_dom_params(morph);
157	morph = isl_morph_ran_params(morph);
158	morph = isl_morph_inverse(morph);
159
160	bound->pwf = isl_pw_qpolynomial_fold_morph_domain(bound->pwf,
161							isl_morph_copy(morph));
162	bound->pwf_tight = isl_pw_qpolynomial_fold_morph_domain(
163						bound->pwf_tight, morph);
164
165	isl_bound_add(bound, top_pwf);
166	isl_bound_add_tight(bound, top_pwf_tight);
167
168	return r;
169error:
170	isl_basic_set_free(bset);
171	isl_qpolynomial_free(poly);
172	return isl_stat_error;
173}
174
175/* Update bound->pwf and bound->pwf_tight with a bound
176 * of type bound->type on the polynomial "poly" over the domain "bset".
177 *
178 * If the original problem had a wrapped relation in the domain,
179 * meaning that the bound should be computed over the range
180 * of this relation, then temporarily treat the domain dimensions
181 * of this wrapped relation as parameters, compute a bound
182 * in terms of these and the original parameters,
183 * turn the parameters back into set dimensions and
184 * add the results to bound->pwf and bound->pwf_tight.
185 *
186 * Note that even though "bset" is known to live in the same space
187 * as the domain of "poly", the names of the set dimensions
188 * may be different (or missing).  Make sure the naming is exactly
189 * the same before turning these dimensions into parameters
190 * to ensure that the spaces are still the same after
191 * this operation.
192 */
193static isl_stat guarded_poly_bound(__isl_take isl_basic_set *bset,
194	__isl_take isl_qpolynomial *poly, void *user)
195{
196	struct isl_bound *bound = (struct isl_bound *)user;
197	isl_space *space;
198	isl_pw_qpolynomial_fold *top_pwf;
199	isl_pw_qpolynomial_fold *top_pwf_tight;
200	isl_size nparam;
201	isl_size n_in;
202	isl_stat r;
203
204	if (!bound->wrapping)
205		return unwrapped_guarded_poly_bound(bset, poly, user);
206
207	nparam = isl_space_dim(bound->dim, isl_dim_param);
208	n_in = isl_space_dim(bound->dim, isl_dim_in);
209	if (nparam < 0 || n_in < 0)
210		goto error;
211
212	space = isl_qpolynomial_get_domain_space(poly);
213	bset = isl_basic_set_reset_space(bset, space);
214
215	bset = isl_basic_set_move_dims(bset, isl_dim_param, nparam,
216					isl_dim_set, 0, n_in);
217	poly = isl_qpolynomial_move_dims(poly, isl_dim_param, nparam,
218					isl_dim_in, 0, n_in);
219
220	space = isl_basic_set_get_space(bset);
221	space = isl_space_params(space);
222
223	top_pwf = bound->pwf;
224	top_pwf_tight = bound->pwf_tight;
225
226	space = isl_space_from_domain(space);
227	space = isl_space_add_dims(space, isl_dim_out, 1);
228	bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(space),
229						  bound->type);
230	bound->pwf_tight = isl_pw_qpolynomial_fold_zero(space, bound->type);
231
232	r = unwrapped_guarded_poly_bound(bset, poly, user);
233
234	bound->pwf = isl_pw_qpolynomial_fold_reset_space(bound->pwf,
235						    isl_space_copy(bound->dim));
236	bound->pwf_tight = isl_pw_qpolynomial_fold_reset_space(bound->pwf_tight,
237						    isl_space_copy(bound->dim));
238
239	isl_bound_add(bound, top_pwf);
240	isl_bound_add_tight(bound, top_pwf_tight);
241
242	return r;
243error:
244	isl_basic_set_free(bset);
245	isl_qpolynomial_free(poly);
246	return isl_stat_error;
247}
248
249static isl_stat guarded_qp(__isl_take isl_qpolynomial *qp, void *user)
250{
251	struct isl_bound *bound = (struct isl_bound *)user;
252	isl_stat r;
253
254	r = isl_qpolynomial_as_polynomial_on_domain(qp, bound->bset,
255						    &guarded_poly_bound, user);
256	isl_qpolynomial_free(qp);
257	return r;
258}
259
260static isl_stat basic_guarded_fold(__isl_take isl_basic_set *bset, void *user)
261{
262	struct isl_bound *bound = (struct isl_bound *)user;
263	isl_stat r;
264
265	bound->bset = bset;
266	r = isl_qpolynomial_fold_foreach_qpolynomial(bound->fold,
267							&guarded_qp, user);
268	isl_basic_set_free(bset);
269	return r;
270}
271
272static isl_stat guarded_fold(__isl_take isl_set *set,
273	__isl_take isl_qpolynomial_fold *fold, void *user)
274{
275	struct isl_bound *bound = (struct isl_bound *)user;
276
277	if (!set || !fold)
278		goto error;
279
280	set = isl_set_make_disjoint(set);
281
282	bound->fold = fold;
283	bound->type = isl_qpolynomial_fold_get_type(fold);
284
285	if (isl_set_foreach_basic_set(set, &basic_guarded_fold, bound) < 0)
286		goto error;
287
288	isl_set_free(set);
289	isl_qpolynomial_fold_free(fold);
290
291	return isl_stat_ok;
292error:
293	isl_set_free(set);
294	isl_qpolynomial_fold_free(fold);
295	return isl_stat_error;
296}
297
298__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
299	__isl_take isl_pw_qpolynomial_fold *pwf, isl_bool *tight)
300{
301	isl_size nvar;
302	struct isl_bound bound;
303	isl_bool covers;
304
305	if (!pwf)
306		return NULL;
307
308	bound.dim = isl_pw_qpolynomial_fold_get_domain_space(pwf);
309
310	bound.wrapping = isl_space_is_wrapping(bound.dim);
311	if (bound.wrapping)
312		bound.dim = isl_space_unwrap(bound.dim);
313	nvar = isl_space_dim(bound.dim, isl_dim_out);
314	if (nvar < 0)
315		bound.dim = isl_space_free(bound.dim);
316	bound.dim = isl_space_domain(bound.dim);
317	bound.dim = isl_space_from_domain(bound.dim);
318	bound.dim = isl_space_add_dims(bound.dim, isl_dim_out, 1);
319
320	if (nvar == 0) {
321		if (tight)
322			*tight = isl_bool_true;
323		return isl_pw_qpolynomial_fold_reset_space(pwf, bound.dim);
324	}
325
326	if (isl_pw_qpolynomial_fold_is_zero(pwf)) {
327		enum isl_fold type = pwf->type;
328		isl_pw_qpolynomial_fold_free(pwf);
329		if (tight)
330			*tight = isl_bool_true;
331		return isl_pw_qpolynomial_fold_zero(bound.dim, type);
332	}
333
334	bound.pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
335							pwf->type);
336	bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
337							pwf->type);
338	bound.check_tight = !!tight;
339
340	if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,
341							guarded_fold, &bound) < 0)
342		goto error;
343
344	covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);
345	if (covers < 0)
346		goto error;
347
348	if (tight)
349		*tight = covers;
350
351	isl_space_free(bound.dim);
352	isl_pw_qpolynomial_fold_free(pwf);
353
354	if (covers) {
355		isl_pw_qpolynomial_fold_free(bound.pwf);
356		return bound.pwf_tight;
357	}
358
359	bound.pwf = isl_pw_qpolynomial_fold_fold(bound.pwf, bound.pwf_tight);
360
361	return bound.pwf;
362error:
363	isl_pw_qpolynomial_fold_free(bound.pwf_tight);
364	isl_pw_qpolynomial_fold_free(bound.pwf);
365	isl_pw_qpolynomial_fold_free(pwf);
366	isl_space_free(bound.dim);
367	return NULL;
368}
369
370__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
371	__isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type,
372	isl_bool *tight)
373{
374	isl_pw_qpolynomial_fold *pwf;
375
376	pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
377	return isl_pw_qpolynomial_fold_bound(pwf, tight);
378}
379
380struct isl_union_bound_data {
381	enum isl_fold type;
382	isl_bool tight;
383	isl_union_pw_qpolynomial_fold *res;
384};
385
386static isl_stat bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)
387{
388	struct isl_union_bound_data *data = user;
389	isl_pw_qpolynomial_fold *pwf;
390
391	pwf = isl_pw_qpolynomial_bound(pwqp, data->type,
392					data->tight ? &data->tight : NULL);
393	data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
394								data->res, pwf);
395
396	return isl_stat_ok;
397}
398
399__isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
400	__isl_take isl_union_pw_qpolynomial *upwqp,
401	enum isl_fold type, isl_bool *tight)
402{
403	isl_space *space;
404	struct isl_union_bound_data data = { type, 1, NULL };
405
406	if (!upwqp)
407		return NULL;
408
409	if (!tight)
410		data.tight = isl_bool_false;
411
412	space = isl_union_pw_qpolynomial_get_space(upwqp);
413	data.res = isl_union_pw_qpolynomial_fold_zero(space, type);
414	if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp,
415						    &bound_pw, &data) < 0)
416		goto error;
417
418	isl_union_pw_qpolynomial_free(upwqp);
419	if (tight)
420		*tight = data.tight;
421
422	return data.res;
423error:
424	isl_union_pw_qpolynomial_free(upwqp);
425	isl_union_pw_qpolynomial_fold_free(data.res);
426	return NULL;
427}
428