X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_range.c;h=865cb797c5ce4b4135f88de212a79c3703a4da13;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=d0e342ecc189ccfb7d84224438b639fd8bb74f56;hpb=99b3ab76db8081dcc843a46e7e443b5ff4084dd1;p=platform%2Fupstream%2Fisl.git diff --git a/isl_range.c b/isl_range.c index d0e342e..865cb79 100644 --- a/isl_range.c +++ b/isl_range.c @@ -1,18 +1,20 @@ -#include -#include +#include +#include +#include #include #include +#include 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, @@ -29,9 +31,10 @@ static int has_sign(__isl_keep 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); @@ -41,18 +44,21 @@ static int has_sign(__isl_keep isl_basic_set *bset, 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; @@ -90,7 +96,7 @@ static int monotonicity(__isl_keep isl_basic_set *bset, __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; @@ -98,16 +104,16 @@ static int monotonicity(__isl_keep isl_basic_set *bset, 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); @@ -134,15 +140,15 @@ error: } 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); } @@ -170,12 +176,13 @@ struct isl_fixed_sign_data { /* 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; @@ -187,14 +194,9 @@ static int collect_fixed_sign_terms(__isl_take isl_term *term, void *user) 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) { @@ -218,19 +220,22 @@ static int collect_fixed_sign_terms(__isl_take isl_term *term, void *user) 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; @@ -241,8 +246,8 @@ 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) @@ -252,14 +257,17 @@ static int add_guarded_poly(__isl_take isl_basic_set *bset, 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; } @@ -269,9 +277,9 @@ static int add_guarded_poly(__isl_take isl_basic_set *bset, * 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. @@ -284,7 +292,7 @@ static int propagate_on_bound_pair(__isl_take isl_constraint *lower, 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; @@ -293,43 +301,43 @@ static int propagate_on_bound_pair(__isl_take isl_constraint *lower, 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); @@ -340,7 +348,7 @@ static int propagate_on_bound_pair(__isl_take isl_constraint *lower, else r = propagate_on_domain(bset, poly, data); - data->exact = save_exact; + data->tight = save_tight; return r; } @@ -351,6 +359,7 @@ static int propagate_on_bound_pair(__isl_take isl_constraint *lower, 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; @@ -358,12 +367,13 @@ static int propagate_on_domain(__isl_take isl_basic_set *bset, 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); } @@ -396,13 +406,15 @@ error: 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, @@ -423,13 +435,12 @@ error: 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; @@ -443,6 +454,7 @@ static int compressed_guarded_poly_bound(__isl_take isl_basic_set *bset, data->poly = poly; + data->test_monotonicity = 1; if (isl_set_foreach_basic_set(set, &basic_guarded_poly_bound, data) < 0) goto error; @@ -456,172 +468,24 @@ 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; }