X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_polynomial.c;h=45676e5e83ac81f9eb0e4fb0162166aad85c3f8d;hb=19596bc4e5cd282b2e75d17077b1aaaeacbfd6f9;hp=173c213f8b883b5b9c19f7160b559b8cdc6950e5;hpb=f53869239275299d045f11ddbf71c9f590e73979;p=platform%2Fupstream%2Fisl.git diff --git a/isl_polynomial.c b/isl_polynomial.c index 173c213..45676e5 100644 --- a/isl_polynomial.c +++ b/isl_polynomial.c @@ -1,7 +1,7 @@ /* * Copyright 2010 INRIA Saclay * - * Use of this software is governed by the GNU LGPLv2.1 license + * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, @@ -24,6 +24,7 @@ #include #include #include +#include #include static unsigned pos(__isl_keep isl_space *dim, enum isl_dim_type type) @@ -801,6 +802,60 @@ error: return NULL; } +/* Multiply the constant polynomial "up" by "v". + */ +static __isl_give struct isl_upoly *isl_upoly_cst_scale_val( + __isl_take struct isl_upoly *up, __isl_keep isl_val *v) +{ + struct isl_upoly_cst *cst; + + if (isl_upoly_is_zero(up)) + return up; + + up = isl_upoly_cow(up); + if (!up) + return NULL; + + cst = isl_upoly_as_cst(up); + + isl_int_mul(cst->n, cst->n, v->n); + isl_int_mul(cst->d, cst->d, v->d); + isl_upoly_cst_reduce(cst); + + return up; +} + +/* Multiply the polynomial "up" by "v". + */ +static __isl_give struct isl_upoly *isl_upoly_scale_val( + __isl_take struct isl_upoly *up, __isl_keep isl_val *v) +{ + int i; + struct isl_upoly_rec *rec; + + if (!up) + return NULL; + + if (isl_upoly_is_cst(up)) + return isl_upoly_cst_scale_val(up, v); + + up = isl_upoly_cow(up); + rec = isl_upoly_as_rec(up); + if (!rec) + goto error; + + for (i = 0; i < rec->n; ++i) { + rec->p[i] = isl_upoly_scale_val(rec->p[i], v); + if (!rec->p[i]) + goto error; + } + + return up; +error: + isl_upoly_free(up); + return NULL; +} + __isl_give struct isl_upoly *isl_upoly_mul_cst(__isl_take struct isl_upoly *up1, __isl_take struct isl_upoly *up2) { @@ -1463,6 +1518,48 @@ __isl_give isl_qpolynomial *isl_qpolynomial_scale( return isl_qpolynomial_mul_isl_int(qp, v); } +/* Multiply "qp" by "v". + */ +__isl_give isl_qpolynomial *isl_qpolynomial_scale_val( + __isl_take isl_qpolynomial *qp, __isl_take isl_val *v) +{ + if (!qp || !v) + goto error; + + if (!isl_val_is_rat(v)) + isl_die(isl_qpolynomial_get_ctx(qp), isl_error_invalid, + "expecting rational factor", goto error); + + if (isl_val_is_one(v)) { + isl_val_free(v); + return qp; + } + + if (isl_val_is_zero(v)) { + isl_space *space; + + space = isl_qpolynomial_get_domain_space(qp); + isl_qpolynomial_free(qp); + isl_val_free(v); + return isl_qpolynomial_zero_on_domain(space); + } + + qp = isl_qpolynomial_cow(qp); + if (!qp) + goto error; + + qp->upoly = isl_upoly_scale_val(qp->upoly, v); + if (!qp->upoly) + qp = isl_qpolynomial_free(qp); + + isl_val_free(v); + return qp; +error: + isl_val_free(v); + isl_qpolynomial_free(qp); + return NULL; +} + __isl_give isl_qpolynomial *isl_qpolynomial_mul(__isl_take isl_qpolynomial *qp1, __isl_take isl_qpolynomial *qp2) { @@ -1613,6 +1710,42 @@ int isl_qpolynomial_is_cst(__isl_keep isl_qpolynomial *qp, return 1; } +/* Return the constant term of "up". + */ +static __isl_give isl_val *isl_upoly_get_constant_val( + __isl_keep struct isl_upoly *up) +{ + struct isl_upoly_cst *cst; + + if (!up) + return NULL; + + while (!isl_upoly_is_cst(up)) { + struct isl_upoly_rec *rec; + + rec = isl_upoly_as_rec(up); + if (!rec) + return NULL; + up = rec->p[0]; + } + + cst = isl_upoly_as_cst(up); + if (!cst) + return NULL; + return isl_val_rat_from_isl_int(cst->up.ctx, cst->n, cst->d); +} + +/* Return the constant term of "qp". + */ +__isl_give isl_val *isl_qpolynomial_get_constant_val( + __isl_keep isl_qpolynomial *qp) +{ + if (!qp) + return NULL; + + return isl_upoly_get_constant_val(qp->upoly); +} + int isl_upoly_is_affine(__isl_keep struct isl_upoly *up) { int is_cst; @@ -2146,6 +2279,33 @@ __isl_give isl_qpolynomial *isl_qpolynomial_rat_cst_on_domain( return qp; } +/* Return an isl_qpolynomial that is equal to "val" on domain space "domain". + */ +__isl_give isl_qpolynomial *isl_qpolynomial_val_on_domain( + __isl_take isl_space *domain, __isl_take isl_val *val) +{ + isl_qpolynomial *qp; + struct isl_upoly_cst *cst; + + if (!domain || !val) + goto error; + + qp = isl_qpolynomial_alloc(domain, 0, isl_upoly_zero(domain->ctx)); + if (!qp) + goto error; + + cst = isl_upoly_as_cst(qp->upoly); + isl_int_set(cst->n, val->n); + isl_int_set(cst->d, val->d); + + isl_val_free(val); + return qp; +error: + isl_space_free(domain); + isl_val_free(val); + return NULL; +} + static int up_set_active(__isl_keep struct isl_upoly *up, int *active, int d) { struct isl_upoly_rec *rec; @@ -2503,7 +2663,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_substitute_equalities( if (!qp || !eq) goto error; if (qp->div->n_row > 0) - eq = isl_basic_set_add(eq, isl_dim_set, qp->div->n_row); + eq = isl_basic_set_add_dims(eq, isl_dim_set, qp->div->n_row); return isl_qpolynomial_substitute_equalities_lifted(qp, eq); error: isl_basic_set_free(eq); @@ -2567,6 +2727,15 @@ error: return NULL; } +__isl_give isl_qpolynomial *isl_qpolynomial_gist_params( + __isl_take isl_qpolynomial *qp, __isl_take isl_set *context) +{ + isl_space *space = isl_qpolynomial_get_domain_space(qp); + isl_set *dom_context = isl_set_universe(space); + dom_context = isl_set_intersect_params(dom_context, context); + return isl_qpolynomial_gist(qp, dom_context); +} + __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_qpolynomial( __isl_take isl_qpolynomial *qp) { @@ -2596,6 +2765,10 @@ __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_qpolynomial( #define IS_ZERO is_zero #undef FIELD #define FIELD qp +#undef DEFAULT_IS_ZERO +#define DEFAULT_IS_ZERO 1 + +#define NO_PULLBACK #include @@ -2623,6 +2796,13 @@ int isl_pw_qpolynomial_is_one(__isl_keep isl_pw_qpolynomial *pwqp) return isl_qpolynomial_is_one(pwqp->p[0].qp); } +__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add( + __isl_take isl_pw_qpolynomial *pwqp1, + __isl_take isl_pw_qpolynomial *pwqp2) +{ + return isl_pw_qpolynomial_union_add_(pwqp1, pwqp2); +} + __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_mul( __isl_take isl_pw_qpolynomial *pwqp1, __isl_take isl_pw_qpolynomial *pwqp2) @@ -3195,7 +3375,7 @@ int isl_qpolynomial_as_polynomial_on_domain(__isl_keep isl_qpolynomial *qp, dim = isl_space_add_dims(dim, isl_dim_set, qp->div->n_row); poly = isl_qpolynomial_alloc(dim, 0, isl_upoly_copy(qp->upoly)); bset = isl_basic_set_copy(bset); - bset = isl_basic_set_add(bset, isl_dim_set, qp->div->n_row); + bset = isl_basic_set_add_dims(bset, isl_dim_set, qp->div->n_row); bset = add_div_constraints(bset, div); return fn(bset, poly, user); @@ -3464,7 +3644,7 @@ __isl_give isl_term *isl_term_dup(__isl_keep isl_term *term) isl_term *dup; unsigned total; - if (term) + if (!term) return NULL; total = isl_space_dim(term->dim, isl_dim_all) + term->div->n_row; @@ -3543,6 +3723,17 @@ void isl_term_get_den(__isl_keep isl_term *term, isl_int *d) isl_int_set(*d, term->d); } +/* Return the coefficient of the term "term". + */ +__isl_give isl_val *isl_term_get_coefficient_val(__isl_keep isl_term *term) +{ + if (!term) + return NULL; + + return isl_val_rat_from_isl_int(isl_term_get_ctx(term), + term->n, term->d); +} + int isl_term_get_exp(__isl_keep isl_term *term, enum isl_dim_type type, unsigned pos) { @@ -3563,7 +3754,6 @@ __isl_give isl_aff *isl_term_get_div(__isl_keep isl_term *term, unsigned pos) { isl_local_space *ls; isl_aff *aff; - unsigned total; if (!term) return NULL; @@ -3571,13 +3761,6 @@ __isl_give isl_aff *isl_term_get_div(__isl_keep isl_term *term, unsigned pos) isl_assert(term->dim->ctx, pos < isl_term_dim(term, isl_dim_div), return NULL); - total = term->div->n_col - term->div->n_row - 2; - /* No nested divs for now */ - isl_assert(term->dim->ctx, - isl_seq_first_non_zero(term->div->row[pos] + 2 + total, - term->div->n_row) == -1, - return NULL); - ls = isl_local_space_alloc_div(isl_space_copy(term->dim), isl_mat_copy(term->div)); aff = isl_aff_alloc(ls); @@ -3586,6 +3769,8 @@ __isl_give isl_aff *isl_term_get_div(__isl_keep isl_term *term, unsigned pos) isl_seq_cpy(aff->v->el, term->div->row[pos], aff->v->size); + aff = isl_aff_normalize(aff); + return aff; } @@ -3942,52 +4127,11 @@ error: return NULL; } -__isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_sub( - __isl_take isl_union_pw_qpolynomial *upwqp1, - __isl_take isl_union_pw_qpolynomial *upwqp2) -{ - return isl_union_pw_qpolynomial_add(upwqp1, - isl_union_pw_qpolynomial_neg(upwqp2)); -} - -static int mul_entry(void **entry, void *user) -{ - struct isl_union_pw_qpolynomial_match_bin_data *data = user; - uint32_t hash; - struct isl_hash_table_entry *entry2; - isl_pw_qpolynomial *pwpq = *entry; - int empty; - - hash = isl_space_get_hash(pwpq->dim); - entry2 = isl_hash_table_find(data->u2->dim->ctx, &data->u2->table, - hash, &has_dim, pwpq->dim, 0); - if (!entry2) - return 0; - - pwpq = isl_pw_qpolynomial_copy(pwpq); - pwpq = isl_pw_qpolynomial_mul(pwpq, - isl_pw_qpolynomial_copy(entry2->data)); - - empty = isl_pw_qpolynomial_is_zero(pwpq); - if (empty < 0) { - isl_pw_qpolynomial_free(pwpq); - return -1; - } - if (empty) { - isl_pw_qpolynomial_free(pwpq); - return 0; - } - - data->res = isl_union_pw_qpolynomial_add_pw_qpolynomial(data->res, pwpq); - - return 0; -} - __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_mul( __isl_take isl_union_pw_qpolynomial *upwqp1, __isl_take isl_union_pw_qpolynomial *upwqp2) { - return match_bin_op(upwqp1, upwqp2, &mul_entry); + return match_bin_op(upwqp1, upwqp2, &isl_pw_qpolynomial_mul); } /* Reorder the columns of the given div definitions according to the @@ -4448,7 +4592,7 @@ error: /* Drop all floors in "qp", turning each integer division [a/m] into * a rational division a/m. If "down" is set, then the integer division - * is replaces by (a-(m-1))/m instead. + * is replaced by (a-(m-1))/m instead. */ static __isl_give isl_qpolynomial *qp_drop_floors( __isl_take isl_qpolynomial *qp, int down)