-#include <isl_constraint.h>
-#include <isl_set.h>
+#include <isl_ctx_private.h>
+#include <isl/constraint.h>
+#include <isl/set.h>
#include <isl_polynomial_private.h>
#include <isl_morph.h>
+#include <isl_range.h>
struct range_data {
+ struct isl_bound *bound;
int *signs;
int sign;
int test_monotonicity;
int monotonicity;
- int exact;
- isl_qpolynomial *qp;
+ int tight;
isl_qpolynomial *poly;
isl_pw_qpolynomial_fold *pwf;
- isl_pw_qpolynomial_fold *pwf_exact;
+ isl_pw_qpolynomial_fold *pwf_tight;
};
static int propagate_on_domain(__isl_take isl_basic_set *bset,
struct range_data data_m;
unsigned nvar;
unsigned nparam;
- isl_dim *dim;
+ isl_space *dim;
isl_qpolynomial *opt;
int r;
+ enum isl_fold type;
nparam = isl_basic_set_dim(bset, isl_dim_param);
nvar = isl_basic_set_dim(bset, isl_dim_set);
bset = isl_basic_set_move_dims(bset, isl_dim_set, 0,
isl_dim_param, 0, nparam);
- poly = isl_qpolynomial_move_dims(poly, isl_dim_set, 0,
+ poly = isl_qpolynomial_move_dims(poly, isl_dim_in, 0,
isl_dim_param, 0, nparam);
- dim = isl_qpolynomial_get_dim(poly);
- dim = isl_dim_drop(dim, isl_dim_set, 0, isl_dim_size(dim, isl_dim_set));
+ dim = isl_qpolynomial_get_space(poly);
+ dim = isl_space_params(dim);
+ dim = isl_space_from_domain(dim);
+ dim = isl_space_add_dims(dim, isl_dim_out, 1);
data_m.test_monotonicity = 0;
data_m.signs = signs;
- data_m.pwf = isl_pw_qpolynomial_fold_zero(dim);
data_m.sign = -sign;
- data_m.exact = 0;
- data_m.pwf_exact = NULL;
+ type = data_m.sign < 0 ? isl_fold_min : isl_fold_max;
+ data_m.pwf = isl_pw_qpolynomial_fold_zero(dim, type);
+ data_m.tight = 0;
+ data_m.pwf_tight = NULL;
if (propagate_on_domain(bset, poly, &data_m) < 0)
goto error;
__isl_keep isl_qpolynomial *poly, struct range_data *data)
{
isl_ctx *ctx;
- isl_dim *dim;
+ isl_space *dim;
isl_qpolynomial *sub = NULL;
isl_qpolynomial *diff = NULL;
int result = 0;
unsigned nvar;
ctx = isl_qpolynomial_get_ctx(poly);
- dim = isl_qpolynomial_get_dim(poly);
+ dim = isl_qpolynomial_get_domain_space(poly);
nvar = isl_basic_set_dim(bset, isl_dim_set);
- sub = isl_qpolynomial_var(isl_dim_copy(dim), isl_dim_set, nvar - 1);
+ sub = isl_qpolynomial_var_on_domain(isl_space_copy(dim), isl_dim_set, nvar - 1);
sub = isl_qpolynomial_add(sub,
- isl_qpolynomial_rat_cst(dim, ctx->one, ctx->one));
+ isl_qpolynomial_rat_cst_on_domain(dim, ctx->one, ctx->one));
diff = isl_qpolynomial_substitute(isl_qpolynomial_copy(poly),
- isl_dim_set, nvar - 1, 1, &sub);
+ isl_dim_in, nvar - 1, 1, &sub);
diff = isl_qpolynomial_sub(diff, isl_qpolynomial_copy(poly));
s = has_sign(bset, diff, 1, data->signs);
}
static __isl_give isl_qpolynomial *bound2poly(__isl_take isl_constraint *bound,
- __isl_take isl_dim *dim, unsigned pos, int sign)
+ __isl_take isl_space *dim, unsigned pos, int sign)
{
if (!bound) {
if (sign > 0)
- return isl_qpolynomial_infty(dim);
+ return isl_qpolynomial_infty_on_domain(dim);
else
- return isl_qpolynomial_neginfty(dim);
+ return isl_qpolynomial_neginfty_on_domain(dim);
}
- isl_dim_free(dim);
+ isl_space_free(dim);
return isl_qpolynomial_from_constraint(bound, isl_dim_set, pos);
}
/* Add term "term" to data->poly if it has sign data->sign.
* The sign is determined based on the signs of the parameters
- * and variables in data->signs.
+ * and variables in data->signs. The integer divisions, if
+ * any, are assumed to be non-negative.
*/
static int collect_fixed_sign_terms(__isl_take isl_term *term, void *user)
{
struct isl_fixed_sign_data *data = (struct isl_fixed_sign_data *)user;
- isl_int n, d;
+ isl_int n;
int i;
int sign;
unsigned nparam;
nparam = isl_term_dim(term, isl_dim_param);
nvar = isl_term_dim(term, isl_dim_set);
- isl_assert(isl_term_get_ctx(term), isl_term_dim(term, isl_dim_div) == 0,
- return -1);
-
isl_int_init(n);
- isl_int_init(d);
isl_term_get_num(term, &n);
- isl_term_get_den(term, &d);
sign = isl_int_sgn(n);
for (i = 0; i < nparam; ++i) {
isl_term_free(term);
isl_int_clear(n);
- isl_int_clear(d);
return 0;
}
/* Construct and return a polynomial that consists of the terms
- * in "poly" that have sign "sign".
+ * in "poly" that have sign "sign". The integer divisions, if
+ * any, are assumed to be non-negative.
*/
-static __isl_give isl_qpolynomial *fixed_sign_terms(
+__isl_give isl_qpolynomial *isl_qpolynomial_terms_of_sign(
__isl_keep isl_qpolynomial *poly, int *signs, int sign)
{
+ isl_space *space;
struct isl_fixed_sign_data data = { signs, sign };
- data.poly = isl_qpolynomial_zero(isl_qpolynomial_get_dim(poly));
+
+ space = isl_qpolynomial_get_domain_space(poly);
+ data.poly = isl_qpolynomial_zero_on_domain(space);
if (isl_qpolynomial_foreach_term(poly, collect_fixed_sign_terms, &data) < 0)
goto error;
return NULL;
}
-/* Helper function to add a guarder polynomial to either pwf_exact or pwf,
- * depending on whether the result has been determined to be exact.
+/* Helper function to add a guarded polynomial to either pwf_tight or pwf,
+ * depending on whether the result has been determined to be tight.
*/
static int add_guarded_poly(__isl_take isl_basic_set *bset,
__isl_take isl_qpolynomial *poly, struct range_data *data)
isl_qpolynomial_fold *fold;
isl_pw_qpolynomial_fold *pwf;
+ bset = isl_basic_set_params(bset);
+ poly = isl_qpolynomial_project_domain_on_params(poly);
+
fold = isl_qpolynomial_fold_alloc(type, poly);
set = isl_set_from_basic_set(bset);
- pwf = isl_pw_qpolynomial_fold_alloc(set, fold);
- if (data->exact)
- data->pwf_exact = isl_pw_qpolynomial_fold_add(
- data->pwf_exact, pwf);
+ pwf = isl_pw_qpolynomial_fold_alloc(type, set, fold);
+ if (data->tight)
+ data->pwf_tight = isl_pw_qpolynomial_fold_fold(
+ data->pwf_tight, pwf);
else
- data->pwf = isl_pw_qpolynomial_fold_add(data->pwf, pwf);
+ data->pwf = isl_pw_qpolynomial_fold_fold(data->pwf, pwf);
return 0;
}
* eliminate the variable from data->poly based on these bounds.
* If the polynomial has been determined to be monotonic
* in the variable, then simply plug in the appropriate bound.
- * If the current polynomial is exact and if this bound is integer,
- * then the result is still exact. In all other cases, the results
- * may be inexact.
+ * If the current polynomial is tight and if this bound is integer,
+ * then the result is still tight. In all other cases, the results
+ * may not be tight.
* Otherwise, plug in the largest bound (in absolute value) in
* the positive terms (if an upper bound is wanted) or the negative terms
* (if a lower bounded is wanted) and the other bound in the other terms.
void *user)
{
struct range_data *data = (struct range_data *)user;
- int save_exact = data->exact;
+ int save_tight = data->tight;
isl_qpolynomial *poly;
int r;
unsigned nvar;
if (data->monotonicity) {
isl_qpolynomial *sub;
- isl_dim *dim = isl_qpolynomial_get_dim(data->poly);
+ isl_space *dim = isl_qpolynomial_get_domain_space(data->poly);
if (data->monotonicity * data->sign > 0) {
- if (data->exact)
- data->exact = bound_is_integer(upper, nvar);
+ if (data->tight)
+ data->tight = bound_is_integer(upper, nvar);
sub = bound2poly(upper, dim, nvar, 1);
isl_constraint_free(lower);
} else {
- if (data->exact)
- data->exact = bound_is_integer(lower, nvar);
+ if (data->tight)
+ data->tight = bound_is_integer(lower, nvar);
sub = bound2poly(lower, dim, nvar, -1);
isl_constraint_free(upper);
}
poly = isl_qpolynomial_copy(data->poly);
- poly = isl_qpolynomial_substitute(poly, isl_dim_set, nvar, 1, &sub);
- poly = isl_qpolynomial_drop_dims(poly, isl_dim_set, nvar, 1);
+ poly = isl_qpolynomial_substitute(poly, isl_dim_in, nvar, 1, &sub);
+ poly = isl_qpolynomial_drop_dims(poly, isl_dim_in, nvar, 1);
isl_qpolynomial_free(sub);
} else {
isl_qpolynomial *l, *u;
isl_qpolynomial *pos, *neg;
- isl_dim *dim = isl_qpolynomial_get_dim(data->poly);
+ isl_space *dim = isl_qpolynomial_get_domain_space(data->poly);
unsigned nparam = isl_basic_set_dim(bset, isl_dim_param);
int sign = data->sign * data->signs[nparam + nvar];
- data->exact = 0;
+ data->tight = 0;
- u = bound2poly(upper, isl_dim_copy(dim), nvar, 1);
+ u = bound2poly(upper, isl_space_copy(dim), nvar, 1);
l = bound2poly(lower, dim, nvar, -1);
- pos = fixed_sign_terms(data->poly, data->signs, sign);
- neg = fixed_sign_terms(data->poly, data->signs, -sign);
+ pos = isl_qpolynomial_terms_of_sign(data->poly, data->signs, sign);
+ neg = isl_qpolynomial_terms_of_sign(data->poly, data->signs, -sign);
- pos = isl_qpolynomial_substitute(pos, isl_dim_set, nvar, 1, &u);
- neg = isl_qpolynomial_substitute(neg, isl_dim_set, nvar, 1, &l);
+ pos = isl_qpolynomial_substitute(pos, isl_dim_in, nvar, 1, &u);
+ neg = isl_qpolynomial_substitute(neg, isl_dim_in, nvar, 1, &l);
poly = isl_qpolynomial_add(pos, neg);
- poly = isl_qpolynomial_drop_dims(poly, isl_dim_set, nvar, 1);
+ poly = isl_qpolynomial_drop_dims(poly, isl_dim_in, nvar, 1);
isl_qpolynomial_free(u);
isl_qpolynomial_free(l);
else
r = propagate_on_domain(bset, poly, data);
- data->exact = save_exact;
+ data->tight = save_tight;
return r;
}
static int propagate_on_domain(__isl_take isl_basic_set *bset,
__isl_take isl_qpolynomial *poly, struct range_data *data)
{
+ isl_ctx *ctx;
isl_qpolynomial *save_poly = data->poly;
int save_monotonicity = data->monotonicity;
unsigned d;
if (!bset || !poly)
goto error;
+ ctx = isl_basic_set_get_ctx(bset);
d = isl_basic_set_dim(bset, isl_dim_set);
- isl_assert(bset->ctx, d >= 1, goto error);
+ isl_assert(ctx, d >= 1, goto error);
if (isl_qpolynomial_is_cst(poly, NULL, NULL)) {
bset = isl_basic_set_project_out(bset, isl_dim_set, 0, d);
- poly = isl_qpolynomial_drop_dims(poly, isl_dim_set, 0, d);
+ poly = isl_qpolynomial_drop_dims(poly, isl_dim_in, 0, d);
return add_guarded_poly(bset, poly, data);
}
static int basic_guarded_poly_bound(__isl_take isl_basic_set *bset, void *user)
{
struct range_data *data = (struct range_data *)user;
+ isl_ctx *ctx;
unsigned nparam = isl_basic_set_dim(bset, isl_dim_param);
unsigned dim = isl_basic_set_dim(bset, isl_dim_set);
int r;
data->signs = NULL;
- data->signs = isl_alloc_array(bset->ctx, int,
+ ctx = isl_basic_set_get_ctx(bset);
+ data->signs = isl_alloc_array(ctx, int,
isl_basic_set_dim(bset, isl_dim_all));
if (isl_basic_set_dims_get_sign(bset, isl_dim_set, 0, dim,
return -1;
}
-static int compressed_guarded_poly_bound(__isl_take isl_basic_set *bset,
- __isl_take isl_qpolynomial *poly, void *user)
+static int qpolynomial_bound_on_domain_range(__isl_take isl_basic_set *bset,
+ __isl_take isl_qpolynomial *poly, struct range_data *data)
{
- struct range_data *data = (struct range_data *)user;
unsigned nparam = isl_basic_set_dim(bset, isl_dim_param);
unsigned nvar = isl_basic_set_dim(bset, isl_dim_set);
- isl_set *set;
+ isl_set *set = NULL;
if (!bset)
goto error;
data->poly = poly;
+ data->test_monotonicity = 1;
if (isl_set_foreach_basic_set(set, &basic_guarded_poly_bound, data) < 0)
goto error;
return -1;
}
-static int guarded_poly_bound(__isl_take isl_basic_set *bset,
- __isl_take isl_qpolynomial *poly, void *user)
-{
- struct range_data *data = (struct range_data *)user;
- isl_pw_qpolynomial_fold *top_pwf;
- isl_pw_qpolynomial_fold *top_pwf_exact;
- isl_dim *dim;
- isl_morph *morph, *morph2;
- unsigned orig_nvar;
- int r;
-
- bset = isl_basic_set_detect_equalities(bset);
-
- if (!bset)
- goto error;
-
- if (bset->n_eq == 0)
- return compressed_guarded_poly_bound(bset, poly, user);
-
- orig_nvar = isl_basic_set_dim(bset, isl_dim_set);
-
- morph = isl_basic_set_variable_compression(bset, isl_dim_param);
- bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
-
- morph2 = isl_basic_set_parameter_compression(bset);
- bset = isl_morph_basic_set(isl_morph_copy(morph2), bset);
-
- morph = isl_morph_compose(morph2, morph);
-
- morph2 = isl_basic_set_variable_compression(bset, isl_dim_set);
- bset = isl_morph_basic_set(isl_morph_copy(morph2), bset);
-
- morph2 = isl_morph_compose(morph2, isl_morph_copy(morph));
- poly = isl_qpolynomial_morph(poly, morph2);
-
- dim = isl_morph_get_ran_dim(morph);
- dim = isl_dim_drop(dim, isl_dim_set, 0, isl_dim_size(dim, isl_dim_set));
-
- top_pwf = data->pwf;
- top_pwf_exact = data->pwf_exact;
-
- data->pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
- data->pwf_exact = isl_pw_qpolynomial_fold_zero(dim);
-
- r = compressed_guarded_poly_bound(bset, poly, user);
-
- morph = isl_morph_drop_dims(morph, isl_dim_set, 0, orig_nvar);
- morph = isl_morph_inverse(morph);
-
- data->pwf = isl_pw_qpolynomial_fold_morph(data->pwf,
- isl_morph_copy(morph));
- data->pwf_exact = isl_pw_qpolynomial_fold_morph(data->pwf_exact, morph);
-
- data->pwf = isl_pw_qpolynomial_fold_add(top_pwf, data->pwf);
- data->pwf_exact = isl_pw_qpolynomial_fold_add(top_pwf_exact,
- data->pwf_exact);
-
- return r;
-error:
- isl_basic_set_free(bset);
- isl_qpolynomial_free(poly);
- return -1;
-}
-
-static int basic_guarded_bound(__isl_take isl_basic_set *bset, void *user)
-{
- struct range_data *data = (struct range_data *)user;
- int r;
-
- r = isl_qpolynomial_as_polynomial_on_domain(data->qp, bset,
- &guarded_poly_bound, user);
- isl_basic_set_free(bset);
- return r;
-}
-
-static int guarded_bound(__isl_take isl_set *set,
- __isl_take isl_qpolynomial *qp, void *user)
-{
- struct range_data *data = (struct range_data *)user;
-
- if (!set || !qp)
- goto error;
-
- set = isl_set_make_disjoint(set);
-
- data->qp = qp;
-
- if (isl_set_foreach_basic_set(set, &basic_guarded_bound, data) < 0)
- goto error;
-
- isl_set_free(set);
- isl_qpolynomial_free(qp);
-
- return 0;
-error:
- isl_set_free(set);
- isl_qpolynomial_free(qp);
- return -1;
-}
-
-/* Compute a lower or upper bound (depending on "type") on the given
- * piecewise step-polynomial using range propagation.
- */
-__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound_range(
- __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type, int *exact)
+int isl_qpolynomial_bound_on_domain_range(__isl_take isl_basic_set *bset,
+ __isl_take isl_qpolynomial *poly, struct isl_bound *bound)
{
- isl_dim *dim;
- isl_pw_qpolynomial_fold *pwf;
- unsigned nvar;
- unsigned nparam;
struct range_data data;
- int covers;
-
- if (!pwqp)
- return NULL;
-
- dim = isl_pw_qpolynomial_get_dim(pwqp);
- nvar = isl_dim_size(dim, isl_dim_set);
-
- if (isl_pw_qpolynomial_is_zero(pwqp)) {
- isl_pw_qpolynomial_free(pwqp);
- dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
- return isl_pw_qpolynomial_fold_zero(dim);
- }
-
- if (nvar == 0) {
- isl_dim_free(dim);
- return isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
- }
-
- dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
+ int r;
- nparam = isl_dim_size(dim, isl_dim_param);
- data.pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
- data.pwf_exact = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
- if (type == isl_fold_min)
+ data.pwf = bound->pwf;
+ data.pwf_tight = bound->pwf_tight;
+ data.tight = bound->check_tight;
+ if (bound->type == isl_fold_min)
data.sign = -1;
else
data.sign = 1;
- data.test_monotonicity = 1;
- data.exact = !!exact;
- if (isl_pw_qpolynomial_foreach_lifted_piece(pwqp, guarded_bound, &data))
- goto error;
-
- covers = isl_pw_qpolynomial_fold_covers(data.pwf_exact, data.pwf);
- if (covers < 0)
- goto error;
-
- if (exact)
- *exact = covers;
-
- isl_dim_free(dim);
- isl_pw_qpolynomial_free(pwqp);
+ r = qpolynomial_bound_on_domain_range(bset, poly, &data);
- if (covers) {
- isl_pw_qpolynomial_fold_free(data.pwf);
- return data.pwf_exact;
- }
-
- data.pwf = isl_pw_qpolynomial_fold_add(data.pwf, data.pwf_exact);
+ bound->pwf = data.pwf;
+ bound->pwf_tight = data.pwf_tight;
- return data.pwf;
-error:
- isl_pw_qpolynomial_fold_free(data.pwf);
- isl_dim_free(dim);
- isl_pw_qpolynomial_free(pwqp);
- return NULL;
+ return r;
}
projects / platform / upstream / isl.git / blobdiff