X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_aff.c;h=e9d728658aaf234cb2d914662ce1f7b0e566bdec;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=88ce47341c99100fa8ce7078964393c26b0ece7d;hpb=80d1f461abbbbef01f56c6e77cc02d876c96cf4e;p=platform%2Fupstream%2Fisl.git diff --git a/isl_aff.c b/isl_aff.c index 88ce473..e9d7286 100644 --- a/isl_aff.c +++ b/isl_aff.c @@ -3,7 +3,7 @@ * Copyright 2011 Sven Verdoolaege * Copyright 2012 Ecole Normale Superieure * - * 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, @@ -88,6 +88,63 @@ __isl_give isl_aff *isl_aff_zero_on_domain(__isl_take isl_local_space *ls) return aff; } +/* Return a piecewise affine expression defined on the specified domain + * that is equal to zero. + */ +__isl_give isl_pw_aff *isl_pw_aff_zero_on_domain(__isl_take isl_local_space *ls) +{ + return isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls)); +} + +/* Return an affine expression that is equal to the specified dimension + * in "ls". + */ +__isl_give isl_aff *isl_aff_var_on_domain(__isl_take isl_local_space *ls, + enum isl_dim_type type, unsigned pos) +{ + isl_space *space; + isl_aff *aff; + + if (!ls) + return NULL; + + space = isl_local_space_get_space(ls); + if (!space) + goto error; + if (isl_space_is_map(space)) + isl_die(isl_space_get_ctx(space), isl_error_invalid, + "expecting (parameter) set space", goto error); + if (pos >= isl_local_space_dim(ls, type)) + isl_die(isl_space_get_ctx(space), isl_error_invalid, + "position out of bounds", goto error); + + isl_space_free(space); + aff = isl_aff_alloc(ls); + if (!aff) + return NULL; + + pos += isl_local_space_offset(aff->ls, type); + + isl_int_set_si(aff->v->el[0], 1); + isl_seq_clr(aff->v->el + 1, aff->v->size - 1); + isl_int_set_si(aff->v->el[1 + pos], 1); + + return aff; +error: + isl_local_space_free(ls); + isl_space_free(space); + return NULL; +} + +/* Return a piecewise affine expression that is equal to + * the specified dimension in "ls". + */ +__isl_give isl_pw_aff *isl_pw_aff_var_on_domain(__isl_take isl_local_space *ls, + enum isl_dim_type type, unsigned pos) +{ + return isl_pw_aff_from_aff(isl_aff_var_on_domain(ls, type, pos)); +} + __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff) { if (!aff) @@ -648,6 +705,226 @@ __isl_give isl_aff *isl_aff_remove_unused_divs( __isl_take isl_aff *aff) return aff; } +/* Given two affine expressions "p" of length p_len (including the + * denominator and the constant term) and "subs" of length subs_len, + * plug in "subs" for the variable at position "pos". + * The variables of "subs" and "p" are assumed to match up to subs_len, + * but "p" may have additional variables. + * "v" is an initialized isl_int that can be used internally. + * + * In particular, if "p" represents the expression + * + * (a i + g)/m + * + * with i the variable at position "pos" and "subs" represents the expression + * + * f/d + * + * then the result represents the expression + * + * (a f + d g)/(m d) + * + */ +void isl_seq_substitute(isl_int *p, int pos, isl_int *subs, + int p_len, int subs_len, isl_int v) +{ + isl_int_set(v, p[1 + pos]); + isl_int_set_si(p[1 + pos], 0); + isl_seq_combine(p + 1, subs[0], p + 1, v, subs + 1, subs_len - 1); + isl_seq_scale(p + subs_len, p + subs_len, subs[0], p_len - subs_len); + isl_int_mul(p[0], p[0], subs[0]); +} + +/* Look for any divs in the aff->ls with a denominator equal to one + * and plug them into the affine expression and any subsequent divs + * that may reference the div. + */ +static __isl_give isl_aff *plug_in_integral_divs(__isl_take isl_aff *aff) +{ + int i, n; + int len; + isl_int v; + isl_vec *vec; + isl_local_space *ls; + unsigned pos; + + if (!aff) + return NULL; + + n = isl_local_space_dim(aff->ls, isl_dim_div); + len = aff->v->size; + for (i = 0; i < n; ++i) { + if (!isl_int_is_one(aff->ls->div->row[i][0])) + continue; + ls = isl_local_space_copy(aff->ls); + ls = isl_local_space_substitute_seq(ls, isl_dim_div, i, + aff->ls->div->row[i], len, i + 1, n - (i + 1)); + vec = isl_vec_copy(aff->v); + vec = isl_vec_cow(vec); + if (!ls || !vec) + goto error; + + isl_int_init(v); + + pos = isl_local_space_offset(aff->ls, isl_dim_div) + i; + isl_seq_substitute(vec->el, pos, aff->ls->div->row[i], + len, len, v); + + isl_int_clear(v); + + isl_vec_free(aff->v); + aff->v = vec; + isl_local_space_free(aff->ls); + aff->ls = ls; + } + + return aff; +error: + isl_vec_free(vec); + isl_local_space_free(ls); + return isl_aff_free(aff); +} + +/* Look for any divs j that appear with a unit coefficient inside + * the definitions of other divs i and plug them into the definitions + * of the divs i. + * + * In particular, an expression of the form + * + * floor((f(..) + floor(g(..)/n))/m) + * + * is simplified to + * + * floor((n * f(..) + g(..))/(n * m)) + * + * This simplification is correct because we can move the expression + * f(..) into the inner floor in the original expression to obtain + * + * floor(floor((n * f(..) + g(..))/n)/m) + * + * from which we can derive the simplified expression. + */ +static __isl_give isl_aff *plug_in_unit_divs(__isl_take isl_aff *aff) +{ + int i, j, n; + int off; + + if (!aff) + return NULL; + + n = isl_local_space_dim(aff->ls, isl_dim_div); + off = isl_local_space_offset(aff->ls, isl_dim_div); + for (i = 1; i < n; ++i) { + for (j = 0; j < i; ++j) { + if (!isl_int_is_one(aff->ls->div->row[i][1 + off + j])) + continue; + aff->ls = isl_local_space_substitute_seq(aff->ls, + isl_dim_div, j, aff->ls->div->row[j], + aff->v->size, i, 1); + if (!aff->ls) + return isl_aff_free(aff); + } + } + + return aff; +} + +/* Swap divs "a" and "b" in "aff", which is assumed to be non-NULL. + * + * Even though this function is only called on isl_affs with a single + * reference, we are careful to only change aff->v and aff->ls together. + */ +static __isl_give isl_aff *swap_div(__isl_take isl_aff *aff, int a, int b) +{ + unsigned off = isl_local_space_offset(aff->ls, isl_dim_div); + isl_local_space *ls; + isl_vec *v; + + ls = isl_local_space_copy(aff->ls); + ls = isl_local_space_swap_div(ls, a, b); + v = isl_vec_copy(aff->v); + v = isl_vec_cow(v); + if (!ls || !v) + goto error; + + isl_int_swap(v->el[1 + off + a], v->el[1 + off + b]); + isl_vec_free(aff->v); + aff->v = v; + isl_local_space_free(aff->ls); + aff->ls = ls; + + return aff; +error: + isl_vec_free(v); + isl_local_space_free(ls); + return isl_aff_free(aff); +} + +/* Merge divs "a" and "b" in "aff", which is assumed to be non-NULL. + * + * We currently do not actually remove div "b", but simply add its + * coefficient to that of "a" and then zero it out. + */ +static __isl_give isl_aff *merge_divs(__isl_take isl_aff *aff, int a, int b) +{ + unsigned off = isl_local_space_offset(aff->ls, isl_dim_div); + + if (isl_int_is_zero(aff->v->el[1 + off + b])) + return aff; + + aff->v = isl_vec_cow(aff->v); + if (!aff->v) + return isl_aff_free(aff); + + isl_int_add(aff->v->el[1 + off + a], + aff->v->el[1 + off + a], aff->v->el[1 + off + b]); + isl_int_set_si(aff->v->el[1 + off + b], 0); + + return aff; +} + +/* Sort the divs in the local space of "aff" according to + * the comparison function "cmp_row" in isl_local_space.c, + * combining the coefficients of identical divs. + * + * Reordering divs does not change the semantics of "aff", + * so there is no need to call isl_aff_cow. + * Moreover, this function is currently only called on isl_affs + * with a single reference. + */ +static __isl_give isl_aff *sort_divs(__isl_take isl_aff *aff) +{ + int i, j, n; + unsigned off; + + if (!aff) + return NULL; + + off = isl_local_space_offset(aff->ls, isl_dim_div); + n = isl_aff_dim(aff, isl_dim_div); + for (i = 1; i < n; ++i) { + for (j = i - 1; j >= 0; --j) { + int cmp = isl_mat_cmp_div(aff->ls->div, j, j + 1); + if (cmp < 0) + break; + if (cmp == 0) + aff = merge_divs(aff, j, j + 1); + else + aff = swap_div(aff, j, j + 1); + if (!aff) + return NULL; + } + } + + return aff; +} + +/* Normalize the representation of "aff". + * + * This function should only be called of "new" isl_affs, i.e., + * with only a single reference. We therefore do not need to + * worry about affecting other instances. + */ __isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff) { if (!aff) @@ -655,6 +932,9 @@ __isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff) aff->v = isl_vec_normalize(aff->v); if (!aff->v) return isl_aff_free(aff); + aff = plug_in_integral_divs(aff); + aff = plug_in_unit_divs(aff); + aff = sort_divs(aff); aff = isl_aff_remove_unused_divs(aff); return aff; } @@ -720,6 +1000,8 @@ __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff) isl_int_set_si(aff->v->el[0], 1); isl_int_set_si(aff->v->el[size], 1); + aff = isl_aff_normalize(aff); + return aff; } @@ -759,7 +1041,13 @@ __isl_give isl_pw_aff *isl_pw_aff_mod(__isl_take isl_pw_aff *pwaff, isl_int m) /* Given f, return ceil(f). * If f is an integer expression, then just return f. - * Otherwise, create a new div d = [-f] and return the expression -d. + * Otherwise, let f be the expression + * + * e/m + * + * then return + * + * floor((e + m - 1)/m) */ __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff) { @@ -769,9 +1057,16 @@ __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff) if (isl_int_is_one(aff->v->el[0])) return aff; - aff = isl_aff_neg(aff); + aff = isl_aff_cow(aff); + if (!aff) + return NULL; + aff->v = isl_vec_cow(aff->v); + if (!aff->v) + return isl_aff_free(aff); + + isl_int_add(aff->v->el[1], aff->v->el[1], aff->v->el[0]); + isl_int_sub_ui(aff->v->el[1], aff->v->el[1], 1); aff = isl_aff_floor(aff); - aff = isl_aff_neg(aff); return aff; } @@ -939,6 +1234,11 @@ __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f) aff = isl_aff_cow(aff); if (!aff) return NULL; + + if (isl_int_is_zero(f)) + isl_die(isl_aff_get_ctx(aff), isl_error_invalid, + "cannot scale down by zero", return isl_aff_free(aff)); + aff->v = isl_vec_cow(aff->v); if (!aff->v) return isl_aff_free(aff); @@ -1036,7 +1336,8 @@ static __isl_give isl_aff *isl_aff_substitute_equalities_lifted( aff->ls = isl_local_space_substitute_equalities(aff->ls, isl_basic_set_copy(eq)); - if (!aff->ls) + aff->v = isl_vec_cow(aff->v); + if (!aff->ls || !aff->v) goto error; total = 1 + isl_space_dim(eq->dim, isl_dim_all); @@ -1071,7 +1372,7 @@ static __isl_give isl_aff *isl_aff_substitute_equalities( goto error; n_div = isl_local_space_dim(aff->ls, isl_dim_div); if (n_div > 0) - eq = isl_basic_set_add(eq, isl_dim_set, n_div); + eq = isl_basic_set_add_dims(eq, isl_dim_set, n_div); return isl_aff_substitute_equalities_lifted(aff, eq); error: isl_basic_set_free(eq); @@ -1123,8 +1424,10 @@ __isl_give isl_aff *isl_aff_gist_params(__isl_take isl_aff *aff, /* Return a basic set containing those elements in the space * of aff where it is non-negative. + * If "rational" is set, then return a rational basic set. */ -__isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff) +static __isl_give isl_basic_set *aff_nonneg_basic_set( + __isl_take isl_aff *aff, int rational) { isl_constraint *ineq; isl_basic_set *bset; @@ -1132,10 +1435,20 @@ __isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff) ineq = isl_inequality_from_aff(aff); bset = isl_basic_set_from_constraint(ineq); + if (rational) + bset = isl_basic_set_set_rational(bset); bset = isl_basic_set_simplify(bset); return bset; } +/* Return a basic set containing those elements in the space + * of aff where it is non-negative. + */ +__isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff) +{ + return aff_nonneg_basic_set(aff, 0); +} + /* Return a basic set containing those elements in the domain space * of aff where it is negative. */ @@ -1148,8 +1461,10 @@ __isl_give isl_basic_set *isl_aff_neg_basic_set(__isl_take isl_aff *aff) /* Return a basic set containing those elements in the space * of aff where it is zero. + * If "rational" is set, then return a rational basic set. */ -__isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff) +static __isl_give isl_basic_set *aff_zero_basic_set(__isl_take isl_aff *aff, + int rational) { isl_constraint *ineq; isl_basic_set *bset; @@ -1157,10 +1472,20 @@ __isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff) ineq = isl_equality_from_aff(aff); bset = isl_basic_set_from_constraint(ineq); + if (rational) + bset = isl_basic_set_set_rational(bset); bset = isl_basic_set_simplify(bset); return bset; } +/* Return a basic set containing those elements in the space + * of aff where it is zero. + */ +__isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff) +{ + return aff_zero_basic_set(aff, 0); +} + /* Return a basic set containing those elements in the shared space * of aff1 and aff2 where aff1 is greater than or equal to aff2. */ @@ -1615,8 +1940,11 @@ __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff) for (i = 0; i < pwaff->n; ++i) { isl_basic_set *bset; isl_set *set_i; + int rational; - bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff)); + rational = isl_set_has_rational(pwaff->p[i].set); + bset = aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff), + rational); set_i = isl_set_from_basic_set(bset); set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set)); set = isl_set_union_disjoint(set, set_i); @@ -1645,8 +1973,11 @@ static __isl_give isl_set *pw_aff_zero_set(__isl_take isl_pw_aff *pwaff, for (i = 0; i < pwaff->n; ++i) { isl_basic_set *bset; isl_set *set_i, *zero; + int rational; - bset = isl_aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff)); + rational = isl_set_has_rational(pwaff->p[i].set); + bset = aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff), + rational); zero = isl_set_from_basic_set(bset); set_i = isl_set_copy(pwaff->p[i].set); if (complement) @@ -2020,6 +2351,46 @@ error: return NULL; } +/* Divide "aff1" by "aff2", assuming "aff2" is a piecewise constant. + */ +__isl_give isl_aff *isl_aff_div(__isl_take isl_aff *aff1, + __isl_take isl_aff *aff2) +{ + int is_cst; + int neg; + + is_cst = isl_aff_is_cst(aff2); + if (is_cst < 0) + goto error; + if (!is_cst) + isl_die(isl_aff_get_ctx(aff2), isl_error_invalid, + "second argument should be a constant", goto error); + + if (!aff2) + goto error; + + neg = isl_int_is_neg(aff2->v->el[1]); + if (neg) { + isl_int_neg(aff2->v->el[0], aff2->v->el[0]); + isl_int_neg(aff2->v->el[1], aff2->v->el[1]); + } + + aff1 = isl_aff_scale(aff1, aff2->v->el[0]); + aff1 = isl_aff_scale_down(aff1, aff2->v->el[1]); + + if (neg) { + isl_int_neg(aff2->v->el[0], aff2->v->el[0]); + isl_int_neg(aff2->v->el[1], aff2->v->el[1]); + } + + isl_aff_free(aff2); + return aff1; +error: + isl_aff_free(aff1); + isl_aff_free(aff2); + return NULL; +} + static __isl_give isl_pw_aff *pw_aff_add(__isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2) { @@ -2050,6 +2421,101 @@ __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1, return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul); } +static __isl_give isl_pw_aff *pw_aff_div(__isl_take isl_pw_aff *pa1, + __isl_take isl_pw_aff *pa2) +{ + return isl_pw_aff_on_shared_domain(pa1, pa2, &isl_aff_div); +} + +/* Divide "pa1" by "pa2", assuming "pa2" is a piecewise constant. + */ +__isl_give isl_pw_aff *isl_pw_aff_div(__isl_take isl_pw_aff *pa1, + __isl_take isl_pw_aff *pa2) +{ + int is_cst; + + is_cst = isl_pw_aff_is_cst(pa2); + if (is_cst < 0) + goto error; + if (!is_cst) + isl_die(isl_pw_aff_get_ctx(pa2), isl_error_invalid, + "second argument should be a piecewise constant", + goto error); + return isl_pw_aff_align_params_pw_pw_and(pa1, pa2, &pw_aff_div); +error: + isl_pw_aff_free(pa1); + isl_pw_aff_free(pa2); + return NULL; +} + +/* Compute the quotient of the integer division of "pa1" by "pa2" + * with rounding towards zero. + * "pa2" is assumed to be a piecewise constant. + * + * In particular, return + * + * pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2) + * + */ +__isl_give isl_pw_aff *isl_pw_aff_tdiv_q(__isl_take isl_pw_aff *pa1, + __isl_take isl_pw_aff *pa2) +{ + int is_cst; + isl_set *cond; + isl_pw_aff *f, *c; + + is_cst = isl_pw_aff_is_cst(pa2); + if (is_cst < 0) + goto error; + if (!is_cst) + isl_die(isl_pw_aff_get_ctx(pa2), isl_error_invalid, + "second argument should be a piecewise constant", + goto error); + + pa1 = isl_pw_aff_div(pa1, pa2); + + cond = isl_pw_aff_nonneg_set(isl_pw_aff_copy(pa1)); + f = isl_pw_aff_floor(isl_pw_aff_copy(pa1)); + c = isl_pw_aff_ceil(pa1); + return isl_pw_aff_cond(isl_set_indicator_function(cond), f, c); +error: + isl_pw_aff_free(pa1); + isl_pw_aff_free(pa2); + return NULL; +} + +/* Compute the remainder of the integer division of "pa1" by "pa2" + * with rounding towards zero. + * "pa2" is assumed to be a piecewise constant. + * + * In particular, return + * + * pa1 - pa2 * (pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2)) + * + */ +__isl_give isl_pw_aff *isl_pw_aff_tdiv_r(__isl_take isl_pw_aff *pa1, + __isl_take isl_pw_aff *pa2) +{ + int is_cst; + isl_pw_aff *res; + + is_cst = isl_pw_aff_is_cst(pa2); + if (is_cst < 0) + goto error; + if (!is_cst) + isl_die(isl_pw_aff_get_ctx(pa2), isl_error_invalid, + "second argument should be a piecewise constant", + goto error); + res = isl_pw_aff_tdiv_q(isl_pw_aff_copy(pa1), isl_pw_aff_copy(pa2)); + res = isl_pw_aff_mul(pa2, res); + res = isl_pw_aff_sub(pa1, res); + return res; +error: + isl_pw_aff_free(pa1); + isl_pw_aff_free(pa2); + return NULL; +} + static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2) { @@ -2134,96 +2600,56 @@ __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list) return pw_aff_list_reduce(list, &isl_pw_aff_max); } -#undef BASE -#define BASE aff - -#include - -/* Construct an isl_multi_aff in the given space with value zero in - * each of the output dimensions. +/* Mark the domains of "pwaff" as rational. */ -__isl_give isl_multi_aff *isl_multi_aff_zero(__isl_take isl_space *space) +__isl_give isl_pw_aff *isl_pw_aff_set_rational(__isl_take isl_pw_aff *pwaff) { - int n; - isl_multi_aff *ma; + int i; - if (!space) + pwaff = isl_pw_aff_cow(pwaff); + if (!pwaff) return NULL; + if (pwaff->n == 0) + return pwaff; - n = isl_space_dim(space , isl_dim_out); - ma = isl_multi_aff_alloc(isl_space_copy(space)); - - if (!n) - isl_space_free(space); - else { - int i; - isl_local_space *ls; - isl_aff *aff; - - space = isl_space_domain(space); - ls = isl_local_space_from_space(space); - aff = isl_aff_zero_on_domain(ls); - - for (i = 0; i < n; ++i) - ma = isl_multi_aff_set_aff(ma, i, isl_aff_copy(aff)); - - isl_aff_free(aff); + for (i = 0; i < pwaff->n; ++i) { + pwaff->p[i].set = isl_set_set_rational(pwaff->p[i].set); + if (!pwaff->p[i].set) + return isl_pw_aff_free(pwaff); } - return ma; + return pwaff; } -/* Create an isl_multi_aff in the given space that maps each - * input dimension to the corresponding output dimension. +/* Mark the domains of the elements of "list" as rational. */ -__isl_give isl_multi_aff *isl_multi_aff_identity(__isl_take isl_space *space) +__isl_give isl_pw_aff_list *isl_pw_aff_list_set_rational( + __isl_take isl_pw_aff_list *list) { - int n; - isl_multi_aff *ma; + int i, n; - if (!space) + if (!list) return NULL; + if (list->n == 0) + return list; - if (isl_space_is_set(space)) - isl_die(isl_space_get_ctx(space), isl_error_invalid, - "expecting map space", goto error); - - n = isl_space_dim(space, isl_dim_out); - if (n != isl_space_dim(space, isl_dim_in)) - isl_die(isl_space_get_ctx(space), isl_error_invalid, - "number of input and output dimensions needs to be " - "the same", goto error); - - ma = isl_multi_aff_alloc(isl_space_copy(space)); + n = list->n; + for (i = 0; i < n; ++i) { + isl_pw_aff *pa; - if (!n) - isl_space_free(space); - else { - int i; - isl_local_space *ls; - isl_aff *aff; - - space = isl_space_domain(space); - ls = isl_local_space_from_space(space); - aff = isl_aff_zero_on_domain(ls); - - for (i = 0; i < n; ++i) { - isl_aff *aff_i; - aff_i = isl_aff_copy(aff); - aff_i = isl_aff_add_coefficient_si(aff_i, - isl_dim_in, i, 1); - ma = isl_multi_aff_set_aff(ma, i, aff_i); - } - - isl_aff_free(aff); + pa = isl_pw_aff_list_get_pw_aff(list, i); + pa = isl_pw_aff_set_rational(pa); + list = isl_pw_aff_list_set_pw_aff(list, i, pa); } - return ma; -error: - isl_space_free(space); - return NULL; + return list; } +#undef BASE +#define BASE aff + +#include + /* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe * domain. */ @@ -2234,6 +2660,15 @@ __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_multi_aff( return isl_pw_multi_aff_alloc(dom, ma); } +/* Create a piecewise multi-affine expression in the given space that maps each + * input dimension to the corresponding output dimension. + */ +__isl_give isl_pw_multi_aff *isl_pw_multi_aff_identity( + __isl_take isl_space *space) +{ + return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_identity(space)); +} + __isl_give isl_multi_aff *isl_multi_aff_add(__isl_take isl_multi_aff *maff1, __isl_take isl_multi_aff *maff2) { @@ -2264,6 +2699,47 @@ error: return NULL; } +/* Given two multi-affine expressions A -> B and C -> D, + * construct a multi-affine expression [A -> C] -> [B -> D]. + */ +__isl_give isl_multi_aff *isl_multi_aff_product( + __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2) +{ + int i; + isl_aff *aff; + isl_space *space; + isl_multi_aff *res; + int in1, in2, out1, out2; + + in1 = isl_multi_aff_dim(ma1, isl_dim_in); + in2 = isl_multi_aff_dim(ma2, isl_dim_in); + out1 = isl_multi_aff_dim(ma1, isl_dim_out); + out2 = isl_multi_aff_dim(ma2, isl_dim_out); + space = isl_space_product(isl_multi_aff_get_space(ma1), + isl_multi_aff_get_space(ma2)); + res = isl_multi_aff_alloc(isl_space_copy(space)); + space = isl_space_domain(space); + + for (i = 0; i < out1; ++i) { + aff = isl_multi_aff_get_aff(ma1, i); + aff = isl_aff_insert_dims(aff, isl_dim_in, in1, in2); + aff = isl_aff_reset_domain_space(aff, isl_space_copy(space)); + res = isl_multi_aff_set_aff(res, i, aff); + } + + for (i = 0; i < out2; ++i) { + aff = isl_multi_aff_get_aff(ma2, i); + aff = isl_aff_insert_dims(aff, isl_dim_in, 0, in1); + aff = isl_aff_reset_domain_space(aff, isl_space_copy(space)); + res = isl_multi_aff_set_aff(res, out1 + i, aff); + } + + isl_space_free(space); + isl_multi_aff_free(ma1); + isl_multi_aff_free(ma2); + return res; +} + /* Exploit the equalities in "eq" to simplify the affine expressions. */ static __isl_give isl_multi_aff *isl_multi_aff_substitute_equalities( @@ -2347,62 +2823,6 @@ int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff *maff1, return 1; } -__isl_give isl_multi_aff *isl_multi_aff_set_dim_name( - __isl_take isl_multi_aff *maff, - enum isl_dim_type type, unsigned pos, const char *s) -{ - int i; - - maff = isl_multi_aff_cow(maff); - if (!maff) - return NULL; - - maff->space = isl_space_set_dim_name(maff->space, type, pos, s); - if (!maff->space) - return isl_multi_aff_free(maff); - - if (type == isl_dim_out) - return maff; - for (i = 0; i < maff->n; ++i) { - maff->p[i] = isl_aff_set_dim_name(maff->p[i], type, pos, s); - if (!maff->p[i]) - return isl_multi_aff_free(maff); - } - - return maff; -} - -__isl_give isl_multi_aff *isl_multi_aff_drop_dims(__isl_take isl_multi_aff *maff, - enum isl_dim_type type, unsigned first, unsigned n) -{ - int i; - - maff = isl_multi_aff_cow(maff); - if (!maff) - return NULL; - - maff->space = isl_space_drop_dims(maff->space, type, first, n); - if (!maff->space) - return isl_multi_aff_free(maff); - - if (type == isl_dim_out) { - for (i = 0; i < n; ++i) - isl_aff_free(maff->p[first + i]); - for (i = first; i + n < maff->n; ++i) - maff->p[i] = maff->p[i + n]; - maff->n -= n; - return maff; - } - - for (i = 0; i < maff->n; ++i) { - maff->p[i] = isl_aff_drop_dims(maff->p[i], type, first, n); - if (!maff->p[i]) - return isl_multi_aff_free(maff); - } - - return maff; -} - /* Return the set of domain elements where "ma1" is lexicographically * smaller than or equal to "ma2". */ @@ -2643,6 +3063,54 @@ __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_add( return isl_pw_multi_aff_union_add_(pma1, pma2); } +/* Given two piecewise multi-affine expressions A -> B and C -> D, + * construct a piecewise multi-affine expression [A -> C] -> [B -> D]. + */ +static __isl_give isl_pw_multi_aff *pw_multi_aff_product( + __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2) +{ + int i, j, n; + isl_space *space; + isl_pw_multi_aff *res; + + if (!pma1 || !pma2) + goto error; + + n = pma1->n * pma2->n; + space = isl_space_product(isl_space_copy(pma1->dim), + isl_space_copy(pma2->dim)); + res = isl_pw_multi_aff_alloc_size(space, n); + + for (i = 0; i < pma1->n; ++i) { + for (j = 0; j < pma2->n; ++j) { + isl_set *domain; + isl_multi_aff *ma; + + domain = isl_set_product(isl_set_copy(pma1->p[i].set), + isl_set_copy(pma2->p[j].set)); + ma = isl_multi_aff_product( + isl_multi_aff_copy(pma1->p[i].maff), + isl_multi_aff_copy(pma2->p[i].maff)); + res = isl_pw_multi_aff_add_piece(res, domain, ma); + } + } + + isl_pw_multi_aff_free(pma1); + isl_pw_multi_aff_free(pma2); + return res; +error: + isl_pw_multi_aff_free(pma1); + isl_pw_multi_aff_free(pma2); + return NULL; +} + +__isl_give isl_pw_multi_aff *isl_pw_multi_aff_product( + __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2) +{ + return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2, + &pw_multi_aff_product); +} + /* Construct a map mapping the domain of the piecewise multi-affine expression * to its range, with each dimension in the range equated to the * corresponding affine expression on its cell. @@ -2676,6 +3144,9 @@ __isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma) __isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma) { + if (!pma) + return NULL; + if (!isl_space_is_set(pma->dim)) isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid, "isl_pw_multi_aff cannot be converted into an isl_set", @@ -2774,43 +3245,457 @@ static __isl_give isl_multi_aff *extract_isl_multi_aff_from_basic_map( ma = isl_multi_aff_set_aff(ma, i, aff); } - isl_basic_map_free(bmap); + isl_basic_map_free(bmap); + + return ma; +} + +/* Create an isl_pw_multi_aff that is equivalent to + * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain). + * The given basic map is such that each output dimension is defined + * in terms of the parameters and input dimensions using an equality. + */ +static __isl_give isl_pw_multi_aff *plain_pw_multi_aff_from_map( + __isl_take isl_set *domain, __isl_take isl_basic_map *bmap) +{ + isl_multi_aff *ma; + + ma = extract_isl_multi_aff_from_basic_map(bmap); + return isl_pw_multi_aff_alloc(domain, ma); +} + +/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map. + * This obviously only works if the input "map" is single-valued. + * If so, we compute the lexicographic minimum of the image in the form + * of an isl_pw_multi_aff. Since the image is unique, it is equal + * to its lexicographic minimum. + * If the input is not single-valued, we produce an error. + */ +static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_base( + __isl_take isl_map *map) +{ + int i; + int sv; + isl_pw_multi_aff *pma; + + sv = isl_map_is_single_valued(map); + if (sv < 0) + goto error; + if (!sv) + isl_die(isl_map_get_ctx(map), isl_error_invalid, + "map is not single-valued", goto error); + map = isl_map_make_disjoint(map); + if (!map) + return NULL; + + pma = isl_pw_multi_aff_empty(isl_map_get_space(map)); + + for (i = 0; i < map->n; ++i) { + isl_pw_multi_aff *pma_i; + isl_basic_map *bmap; + bmap = isl_basic_map_copy(map->p[i]); + pma_i = isl_basic_map_lexmin_pw_multi_aff(bmap); + pma = isl_pw_multi_aff_add_disjoint(pma, pma_i); + } + + isl_map_free(map); + return pma; +error: + isl_map_free(map); + return NULL; +} + +/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map, + * taking into account that the output dimension at position "d" + * can be represented as + * + * x = floor((e(...) + c1) / m) + * + * given that constraint "i" is of the form + * + * e(...) + c1 - m x >= 0 + * + * + * Let "map" be of the form + * + * A -> B + * + * We construct a mapping + * + * A -> [A -> x = floor(...)] + * + * apply that to the map, obtaining + * + * [A -> x = floor(...)] -> B + * + * and equate dimension "d" to x. + * We then compute a isl_pw_multi_aff representation of the resulting map + * and plug in the mapping above. + */ +static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_div( + __isl_take isl_map *map, __isl_take isl_basic_map *hull, int d, int i) +{ + isl_ctx *ctx; + isl_space *space; + isl_local_space *ls; + isl_multi_aff *ma; + isl_aff *aff; + isl_vec *v; + isl_map *insert; + int offset; + int n; + int n_in; + isl_pw_multi_aff *pma; + int is_set; + + is_set = isl_map_is_set(map); + + offset = isl_basic_map_offset(hull, isl_dim_out); + ctx = isl_map_get_ctx(map); + space = isl_space_domain(isl_map_get_space(map)); + n_in = isl_space_dim(space, isl_dim_set); + n = isl_space_dim(space, isl_dim_all); + + v = isl_vec_alloc(ctx, 1 + 1 + n); + if (v) { + isl_int_neg(v->el[0], hull->ineq[i][offset + d]); + isl_seq_cpy(v->el + 1, hull->ineq[i], 1 + n); + } + isl_basic_map_free(hull); + + ls = isl_local_space_from_space(isl_space_copy(space)); + aff = isl_aff_alloc_vec(ls, v); + aff = isl_aff_floor(aff); + if (is_set) { + isl_space_free(space); + ma = isl_multi_aff_from_aff(aff); + } else { + ma = isl_multi_aff_identity(isl_space_map_from_set(space)); + ma = isl_multi_aff_range_product(ma, + isl_multi_aff_from_aff(aff)); + } + + insert = isl_map_from_multi_aff(isl_multi_aff_copy(ma)); + map = isl_map_apply_domain(map, insert); + map = isl_map_equate(map, isl_dim_in, n_in, isl_dim_out, d); + pma = isl_pw_multi_aff_from_map(map); + pma = isl_pw_multi_aff_pullback_multi_aff(pma, ma); + + return pma; +} + +/* Is constraint "c" of the form + * + * e(...) + c1 - m x >= 0 + * + * or + * + * -e(...) + c2 + m x >= 0 + * + * where m > 1 and e only depends on parameters and input dimemnsions? + * + * "offset" is the offset of the output dimensions + * "pos" is the position of output dimension x. + */ +static int is_potential_div_constraint(isl_int *c, int offset, int d, int total) +{ + if (isl_int_is_zero(c[offset + d])) + return 0; + if (isl_int_is_one(c[offset + d])) + return 0; + if (isl_int_is_negone(c[offset + d])) + return 0; + if (isl_seq_first_non_zero(c + offset, d) != -1) + return 0; + if (isl_seq_first_non_zero(c + offset + d + 1, + total - (offset + d + 1)) != -1) + return 0; + return 1; +} + +/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map. + * + * As a special case, we first check if there is any pair of constraints, + * shared by all the basic maps in "map" that force a given dimension + * to be equal to the floor of some affine combination of the input dimensions. + * + * In particular, if we can find two constraints + * + * e(...) + c1 - m x >= 0 i.e., m x <= e(...) + c1 + * + * and + * + * -e(...) + c2 + m x >= 0 i.e., m x >= e(...) - c2 + * + * where m > 1 and e only depends on parameters and input dimemnsions, + * and such that + * + * c1 + c2 < m i.e., -c2 >= c1 - (m - 1) + * + * then we know that we can take + * + * x = floor((e(...) + c1) / m) + * + * without having to perform any computation. + * + * Note that we know that + * + * c1 + c2 >= 1 + * + * If c1 + c2 were 0, then we would have detected an equality during + * simplification. If c1 + c2 were negative, then we would have detected + * a contradiction. + */ +static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_check_div( + __isl_take isl_map *map) +{ + int d, dim; + int i, j, n; + int offset, total; + isl_int sum; + isl_basic_map *hull; + + hull = isl_map_unshifted_simple_hull(isl_map_copy(map)); + if (!hull) + goto error; + + isl_int_init(sum); + dim = isl_map_dim(map, isl_dim_out); + offset = isl_basic_map_offset(hull, isl_dim_out); + total = 1 + isl_basic_map_total_dim(hull); + n = hull->n_ineq; + for (d = 0; d < dim; ++d) { + for (i = 0; i < n; ++i) { + if (!is_potential_div_constraint(hull->ineq[i], + offset, d, total)) + continue; + for (j = i + 1; j < n; ++j) { + if (!isl_seq_is_neg(hull->ineq[i] + 1, + hull->ineq[j] + 1, total - 1)) + continue; + isl_int_add(sum, hull->ineq[i][0], + hull->ineq[j][0]); + if (isl_int_abs_lt(sum, + hull->ineq[i][offset + d])) + break; + + } + if (j >= n) + continue; + isl_int_clear(sum); + if (isl_int_is_pos(hull->ineq[j][offset + d])) + j = i; + return pw_multi_aff_from_map_div(map, hull, d, j); + } + } + isl_int_clear(sum); + isl_basic_map_free(hull); + return pw_multi_aff_from_map_base(map); +error: + isl_map_free(map); + isl_basic_map_free(hull); + return NULL; +} + +/* Given an affine expression + * + * [A -> B] -> f(A,B) + * + * construct an isl_multi_aff + * + * [A -> B] -> B' + * + * such that dimension "d" in B' is set to "aff" and the remaining + * dimensions are set equal to the corresponding dimensions in B. + * "n_in" is the dimension of the space A. + * "n_out" is the dimension of the space B. + * + * If "is_set" is set, then the affine expression is of the form + * + * [B] -> f(B) + * + * and we construct an isl_multi_aff + * + * B -> B' + */ +static __isl_give isl_multi_aff *range_map(__isl_take isl_aff *aff, int d, + unsigned n_in, unsigned n_out, int is_set) +{ + int i; + isl_multi_aff *ma; + isl_space *space, *space2; + isl_local_space *ls; + + space = isl_aff_get_domain_space(aff); + ls = isl_local_space_from_space(isl_space_copy(space)); + space2 = isl_space_copy(space); + if (!is_set) + space2 = isl_space_range(isl_space_unwrap(space2)); + space = isl_space_map_from_domain_and_range(space, space2); + ma = isl_multi_aff_alloc(space); + ma = isl_multi_aff_set_aff(ma, d, aff); + + for (i = 0; i < n_out; ++i) { + if (i == d) + continue; + aff = isl_aff_var_on_domain(isl_local_space_copy(ls), + isl_dim_set, n_in + i); + ma = isl_multi_aff_set_aff(ma, i, aff); + } + + isl_local_space_free(ls); return ma; } -/* Create an isl_pw_multi_aff that is equivalent to - * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain). - * The given basic map is such that each output dimension is defined - * in terms of the parameters and input dimensions using an equality. +/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map, + * taking into account that the dimension at position "d" can be written as + * + * x = m a + f(..) (1) + * + * where m is equal to "gcd". + * "i" is the index of the equality in "hull" that defines f(..). + * In particular, the equality is of the form + * + * f(..) - x + m g(existentials) = 0 + * + * or + * + * -f(..) + x + m g(existentials) = 0 + * + * We basically plug (1) into "map", resulting in a map with "a" + * in the range instead of "x". The corresponding isl_pw_multi_aff + * defining "a" is then plugged back into (1) to obtain a definition fro "x". + * + * Specifically, given the input map + * + * A -> B + * + * We first wrap it into a set + * + * [A -> B] + * + * and define (1) on top of the corresponding space, resulting in "aff". + * We use this to create an isl_multi_aff that maps the output position "d" + * from "a" to "x", leaving all other (intput and output) dimensions unchanged. + * We plug this into the wrapped map, unwrap the result and compute the + * corresponding isl_pw_multi_aff. + * The result is an expression + * + * A -> T(A) + * + * We adjust that to + * + * A -> [A -> T(A)] + * + * so that we can plug that into "aff", after extending the latter to + * a mapping + * + * [A -> B] -> B' + * + * + * If "map" is actually a set, then there is no "A" space, meaning + * that we do not need to perform any wrapping, and that the result + * of the recursive call is of the form + * + * [T] + * + * which is plugged into a mapping of the form + * + * B -> B' */ -static __isl_give isl_pw_multi_aff *plain_pw_multi_aff_from_map( - __isl_take isl_set *domain, __isl_take isl_basic_map *bmap) +static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_stride( + __isl_take isl_map *map, __isl_take isl_basic_map *hull, int d, int i, + isl_int gcd) { + isl_set *set; + isl_space *space; + isl_local_space *ls; + isl_aff *aff; isl_multi_aff *ma; + isl_pw_multi_aff *pma, *id; + unsigned n_in; + unsigned o_out; + unsigned n_out; + int is_set; - ma = extract_isl_multi_aff_from_basic_map(bmap); - return isl_pw_multi_aff_alloc(domain, ma); + is_set = isl_map_is_set(map); + + n_in = isl_basic_map_dim(hull, isl_dim_in); + n_out = isl_basic_map_dim(hull, isl_dim_out); + o_out = isl_basic_map_offset(hull, isl_dim_out); + + if (is_set) + set = map; + else + set = isl_map_wrap(map); + space = isl_space_map_from_set(isl_set_get_space(set)); + ma = isl_multi_aff_identity(space); + ls = isl_local_space_from_space(isl_set_get_space(set)); + aff = isl_aff_alloc(ls); + if (aff) { + isl_int_set_si(aff->v->el[0], 1); + if (isl_int_is_one(hull->eq[i][o_out + d])) + isl_seq_neg(aff->v->el + 1, hull->eq[i], + aff->v->size - 1); + else + isl_seq_cpy(aff->v->el + 1, hull->eq[i], + aff->v->size - 1); + isl_int_set(aff->v->el[1 + o_out + d], gcd); + } + ma = isl_multi_aff_set_aff(ma, n_in + d, isl_aff_copy(aff)); + set = isl_set_preimage_multi_aff(set, ma); + + ma = range_map(aff, d, n_in, n_out, is_set); + + if (is_set) + map = set; + else + map = isl_set_unwrap(set); + pma = isl_pw_multi_aff_from_map(set); + + if (!is_set) { + space = isl_pw_multi_aff_get_domain_space(pma); + space = isl_space_map_from_set(space); + id = isl_pw_multi_aff_identity(space); + pma = isl_pw_multi_aff_range_product(id, pma); + } + id = isl_pw_multi_aff_from_multi_aff(ma); + pma = isl_pw_multi_aff_pullback_pw_multi_aff(id, pma); + + isl_basic_map_free(hull); + return pma; } /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map. - * This obivously only works if the input "map" is single-valued. - * If so, we compute the lexicographic minimum of the image in the form - * of an isl_pw_multi_aff. Since the image is unique, it is equal - * to its lexicographic minimum. - * If the input is not single-valued, we produce an error. * * As a special case, we first check if all output dimensions are uniquely * defined in terms of the parameters and input dimensions over the entire * domain. If so, we extract the desired isl_pw_multi_aff directly * from the affine hull of "map" and its domain. + * + * Otherwise, we check if any of the output dimensions is "strided". + * That is, we check if can be written as + * + * x = m a + f(..) + * + * with m greater than 1, a some combination of existentiall quantified + * variables and f and expression in the parameters and input dimensions. + * If so, we remove the stride in pw_multi_aff_from_map_stride. + * + * Otherwise, we continue with pw_multi_aff_from_map_check_div for a further + * special case. */ __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_map(__isl_take isl_map *map) { - int i; + int i, j; int sv; - isl_pw_multi_aff *pma; isl_basic_map *hull; + unsigned n_out; + unsigned o_out; + unsigned n_div; + unsigned o_div; + isl_int gcd; if (!map) return NULL; @@ -2819,32 +3704,53 @@ __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_map(__isl_take isl_map *map) sv = isl_basic_map_plain_is_single_valued(hull); if (sv >= 0 && sv) return plain_pw_multi_aff_from_map(isl_map_domain(map), hull); - isl_basic_map_free(hull); if (sv < 0) + hull = isl_basic_map_free(hull); + if (!hull) goto error; - sv = isl_map_is_single_valued(map); - if (sv < 0) - goto error; - if (!sv) - isl_die(isl_map_get_ctx(map), isl_error_invalid, - "map is not single-valued", goto error); - map = isl_map_make_disjoint(map); - if (!map) - return NULL; + n_div = isl_basic_map_dim(hull, isl_dim_div); + o_div = isl_basic_map_offset(hull, isl_dim_div); - pma = isl_pw_multi_aff_empty(isl_map_get_space(map)); + if (n_div == 0) { + isl_basic_map_free(hull); + return pw_multi_aff_from_map_check_div(map); + } - for (i = 0; i < map->n; ++i) { - isl_pw_multi_aff *pma_i; - isl_basic_map *bmap; - bmap = isl_basic_map_copy(map->p[i]); - pma_i = isl_basic_map_lexmin_pw_multi_aff(bmap); - pma = isl_pw_multi_aff_add_disjoint(pma, pma_i); + isl_int_init(gcd); + + n_out = isl_basic_map_dim(hull, isl_dim_out); + o_out = isl_basic_map_offset(hull, isl_dim_out); + + for (i = 0; i < n_out; ++i) { + for (j = 0; j < hull->n_eq; ++j) { + isl_int *eq = hull->eq[j]; + isl_pw_multi_aff *res; + + if (!isl_int_is_one(eq[o_out + i]) && + !isl_int_is_negone(eq[o_out + i])) + continue; + if (isl_seq_first_non_zero(eq + o_out, i) != -1) + continue; + if (isl_seq_first_non_zero(eq + o_out + i + 1, + n_out - (i + 1)) != -1) + continue; + isl_seq_gcd(eq + o_div, n_div, &gcd); + if (isl_int_is_zero(gcd)) + continue; + if (isl_int_is_one(gcd)) + continue; + + res = pw_multi_aff_from_map_stride(map, hull, + i, j, gcd); + isl_int_clear(gcd); + return res; + } } - isl_map_free(map); - return pma; + isl_int_clear(gcd); + isl_basic_map_free(hull); + return pw_multi_aff_from_map_check_div(map); error: isl_map_free(map); return NULL; @@ -2885,7 +3791,7 @@ __isl_give isl_pw_aff *isl_set_indicator_function(__isl_take isl_set *set) * * The result is * - * floor((a f + d g')/(m d)) + * (a f + d g')/(m d) * * where g' is the result of plugging in "subs" in each of the integer * divisions in g. @@ -2919,11 +3825,8 @@ __isl_give isl_aff *isl_aff_substitute(__isl_take isl_aff *aff, pos += isl_local_space_offset(aff->ls, type); isl_int_init(v); - isl_int_set(v, aff->v->el[1 + pos]); - isl_int_set_si(aff->v->el[1 + pos], 0); - isl_seq_combine(aff->v->el + 1, subs->v->el[0], aff->v->el + 1, - v, subs->v->el + 1, subs->v->size - 1); - isl_int_mul(aff->v->el[0], aff->v->el[0], subs->v->el[0]); + isl_seq_substitute(aff->v->el, pos, subs->v->el, + aff->v->size, subs->v->size, v); isl_int_clear(v); return aff; @@ -2989,13 +3892,18 @@ __isl_give isl_pw_multi_aff *isl_pw_multi_aff_substitute( for (j = 0; j < subs->n; ++j) { isl_set *common; isl_multi_aff *res_ij; + int empty; + common = isl_set_intersect( isl_set_copy(pma->p[i].set), isl_set_copy(subs->p[j].set)); common = isl_set_substitute(common, type, pos, subs->p[j].aff); - if (isl_set_plain_is_empty(common)) { + empty = isl_set_plain_is_empty(common); + if (empty < 0 || empty) { isl_set_free(common); + if (empty < 0) + goto error; continue; } @@ -3009,6 +3917,179 @@ __isl_give isl_pw_multi_aff *isl_pw_multi_aff_substitute( isl_pw_multi_aff_free(pma); return res; +error: + isl_pw_multi_aff_free(pma); + isl_pw_multi_aff_free(res); + return NULL; +} + +/* Compute the preimage of the affine expression "src" under "ma" + * and put the result in "dst". If "has_denom" is set (to one), + * then "src" and "dst" have an extra initial denominator. + * "n_div_ma" is the number of existentials in "ma" + * "n_div_bset" is the number of existentials in "src" + * The resulting "dst" (which is assumed to have been allocated by + * the caller) contains coefficients for both sets of existentials, + * first those in "ma" and then those in "src". + * f, c1, c2 and g are temporary objects that have been initialized + * by the caller. + * + * Let src represent the expression + * + * (a(p) + b x + c(divs))/d + * + * and let ma represent the expressions + * + * x_i = (r_i(p) + s_i(y) + t_i(divs'))/m_i + * + * We start out with the following expression for dst: + * + * (a(p) + 0 y + 0 divs' + f \sum_i b_i x_i + c(divs))/d + * + * with the multiplication factor f initially equal to 1. + * For each x_i that we substitute, we multiply the numerator + * (and denominator) of dst by c_1 = m_i and add the numerator + * of the x_i expression multiplied by c_2 = f b_i, + * after removing the common factors of c_1 and c_2. + * The multiplication factor f also needs to be multiplied by c_1 + * for the next x_j, j > i. + */ +void isl_seq_preimage(isl_int *dst, isl_int *src, + __isl_keep isl_multi_aff *ma, int n_div_ma, int n_div_bset, + isl_int f, isl_int c1, isl_int c2, isl_int g, int has_denom) +{ + int i; + int n_param, n_in, n_out; + int o_div_bset; + + n_param = isl_multi_aff_dim(ma, isl_dim_param); + n_in = isl_multi_aff_dim(ma, isl_dim_in); + n_out = isl_multi_aff_dim(ma, isl_dim_out); + + o_div_bset = has_denom + 1 + n_param + n_in + n_div_ma; + + isl_seq_cpy(dst, src, has_denom + 1 + n_param); + isl_seq_clr(dst + has_denom + 1 + n_param, n_in + n_div_ma); + isl_seq_cpy(dst + o_div_bset, + src + has_denom + 1 + n_param + n_out, n_div_bset); + + isl_int_set_si(f, 1); + + for (i = 0; i < n_out; ++i) { + if (isl_int_is_zero(src[has_denom + 1 + n_param + i])) + continue; + isl_int_set(c1, ma->p[i]->v->el[0]); + isl_int_mul(c2, f, src[has_denom + 1 + n_param + i]); + isl_int_gcd(g, c1, c2); + isl_int_divexact(c1, c1, g); + isl_int_divexact(c2, c2, g); + + isl_int_mul(f, f, c1); + isl_seq_combine(dst + has_denom, c1, dst + has_denom, + c2, ma->p[i]->v->el + 1, ma->p[i]->v->size - 1); + isl_seq_scale(dst + o_div_bset, + dst + o_div_bset, c1, n_div_bset); + if (has_denom) + isl_int_mul(dst[0], dst[0], c1); + } +} + +/* Compute the pullback of "aff" by the function represented by "ma". + * In other words, plug in "ma" in "aff". The result is an affine expression + * defined over the domain space of "ma". + * + * If "aff" is represented by + * + * (a(p) + b x + c(divs))/d + * + * and ma is represented by + * + * x = D(p) + F(y) + G(divs') + * + * then the result is + * + * (a(p) + b D(p) + b F(y) + b G(divs') + c(divs))/d + * + * The divs in the local space of the input are similarly adjusted + * through a call to isl_local_space_preimage_multi_aff. + */ +__isl_give isl_aff *isl_aff_pullback_multi_aff(__isl_take isl_aff *aff, + __isl_take isl_multi_aff *ma) +{ + isl_aff *res = NULL; + isl_local_space *ls; + int n_div_aff, n_div_ma; + isl_int f, c1, c2, g; + + ma = isl_multi_aff_align_divs(ma); + if (!aff || !ma) + goto error; + + n_div_aff = isl_aff_dim(aff, isl_dim_div); + n_div_ma = ma->n ? isl_aff_dim(ma->p[0], isl_dim_div) : 0; + + ls = isl_aff_get_domain_local_space(aff); + ls = isl_local_space_preimage_multi_aff(ls, isl_multi_aff_copy(ma)); + res = isl_aff_alloc(ls); + if (!res) + goto error; + + isl_int_init(f); + isl_int_init(c1); + isl_int_init(c2); + isl_int_init(g); + + isl_seq_preimage(res->v->el, aff->v->el, ma, n_div_ma, n_div_aff, + f, c1, c2, g, 1); + + isl_int_clear(f); + isl_int_clear(c1); + isl_int_clear(c2); + isl_int_clear(g); + + isl_aff_free(aff); + isl_multi_aff_free(ma); + res = isl_aff_normalize(res); + return res; +error: + isl_aff_free(aff); + isl_multi_aff_free(ma); + isl_aff_free(res); + return NULL; +} + +/* Compute the pullback of "ma1" by the function represented by "ma2". + * In other words, plug in "ma2" in "ma1". + */ +__isl_give isl_multi_aff *isl_multi_aff_pullback_multi_aff( + __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2) +{ + int i; + isl_space *space = NULL; + + ma2 = isl_multi_aff_align_divs(ma2); + ma1 = isl_multi_aff_cow(ma1); + if (!ma1 || !ma2) + goto error; + + space = isl_space_join(isl_multi_aff_get_space(ma2), + isl_multi_aff_get_space(ma1)); + + for (i = 0; i < ma1->n; ++i) { + ma1->p[i] = isl_aff_pullback_multi_aff(ma1->p[i], + isl_multi_aff_copy(ma2)); + if (!ma1->p[i]) + goto error; + } + + ma1 = isl_multi_aff_reset_space(ma1, space); + isl_multi_aff_free(ma2); + return ma1; +error: + isl_space_free(space); + isl_multi_aff_free(ma2); + isl_multi_aff_free(ma1); + return NULL; } /* Extend the local space of "dst" to include the divs @@ -3346,45 +4427,28 @@ error: return NULL; } -/* Given two isl_multi_affs A -> B and C -> D, - * construct an isl_multi_aff (A * C) -> (B, D). +/* Given two aligned isl_pw_multi_affs A -> B and C -> D, + * construct an isl_pw_multi_aff (A * C) -> [B -> D]. */ -__isl_give isl_multi_aff *isl_multi_aff_flat_range_product( - __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2) +static __isl_give isl_pw_multi_aff *pw_multi_aff_range_product( + __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2) { - int i, n1, n2; - isl_aff *aff; isl_space *space; - isl_multi_aff *res; - - if (!ma1 || !ma2) - goto error; - space = isl_space_range_product(isl_multi_aff_get_space(ma1), - isl_multi_aff_get_space(ma2)); - space = isl_space_flatten_range(space); - res = isl_multi_aff_alloc(space); - - n1 = isl_multi_aff_dim(ma1, isl_dim_out); - n2 = isl_multi_aff_dim(ma2, isl_dim_out); - - for (i = 0; i < n1; ++i) { - aff = isl_multi_aff_get_aff(ma1, i); - res = isl_multi_aff_set_aff(res, i, aff); - } - - for (i = 0; i < n2; ++i) { - aff = isl_multi_aff_get_aff(ma2, i); - res = isl_multi_aff_set_aff(res, n1 + i, aff); - } + space = isl_space_range_product(isl_pw_multi_aff_get_space(pma1), + isl_pw_multi_aff_get_space(pma2)); + return isl_pw_multi_aff_on_shared_domain_in(pma1, pma2, space, + &isl_multi_aff_range_product); +} - isl_multi_aff_free(ma1); - isl_multi_aff_free(ma2); - return res; -error: - isl_multi_aff_free(ma1); - isl_multi_aff_free(ma2); - return NULL; +/* Given two isl_pw_multi_affs A -> B and C -> D, + * construct an isl_pw_multi_aff (A * C) -> [B -> D]. + */ +__isl_give isl_pw_multi_aff *isl_pw_multi_aff_range_product( + __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2) +{ + return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2, + &pw_multi_aff_range_product); } /* Given two aligned isl_pw_multi_affs A -> B and C -> D, @@ -3442,3 +4506,92 @@ __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_flat_range_product( { return bin_op(upma1, upma2, &flat_range_product_entry); } + +/* Replace the affine expressions at position "pos" in "pma" by "pa". + * The parameters are assumed to have been aligned. + * + * The implementation essentially performs an isl_pw_*_on_shared_domain, + * except that it works on two different isl_pw_* types. + */ +static __isl_give isl_pw_multi_aff *pw_multi_aff_set_pw_aff( + __isl_take isl_pw_multi_aff *pma, unsigned pos, + __isl_take isl_pw_aff *pa) +{ + int i, j, n; + isl_pw_multi_aff *res = NULL; + + if (!pma || !pa) + goto error; + + if (!isl_space_tuple_match(pma->dim, isl_dim_in, pa->dim, isl_dim_in)) + isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid, + "domains don't match", goto error); + if (pos >= isl_pw_multi_aff_dim(pma, isl_dim_out)) + isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid, + "index out of bounds", goto error); + + n = pma->n * pa->n; + res = isl_pw_multi_aff_alloc_size(isl_pw_multi_aff_get_space(pma), n); + + for (i = 0; i < pma->n; ++i) { + for (j = 0; j < pa->n; ++j) { + isl_set *common; + isl_multi_aff *res_ij; + int empty; + + common = isl_set_intersect(isl_set_copy(pma->p[i].set), + isl_set_copy(pa->p[j].set)); + empty = isl_set_plain_is_empty(common); + if (empty < 0 || empty) { + isl_set_free(common); + if (empty < 0) + goto error; + continue; + } + + res_ij = isl_multi_aff_set_aff( + isl_multi_aff_copy(pma->p[i].maff), pos, + isl_aff_copy(pa->p[j].aff)); + res_ij = isl_multi_aff_gist(res_ij, + isl_set_copy(common)); + + res = isl_pw_multi_aff_add_piece(res, common, res_ij); + } + } + + isl_pw_multi_aff_free(pma); + isl_pw_aff_free(pa); + return res; +error: + isl_pw_multi_aff_free(pma); + isl_pw_aff_free(pa); + return isl_pw_multi_aff_free(res); +} + +/* Replace the affine expressions at position "pos" in "pma" by "pa". + */ +__isl_give isl_pw_multi_aff *isl_pw_multi_aff_set_pw_aff( + __isl_take isl_pw_multi_aff *pma, unsigned pos, + __isl_take isl_pw_aff *pa) +{ + if (!pma || !pa) + goto error; + if (isl_space_match(pma->dim, isl_dim_param, pa->dim, isl_dim_param)) + return pw_multi_aff_set_pw_aff(pma, pos, pa); + if (!isl_space_has_named_params(pma->dim) || + !isl_space_has_named_params(pa->dim)) + isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid, + "unaligned unnamed parameters", goto error); + pma = isl_pw_multi_aff_align_params(pma, isl_pw_aff_get_space(pa)); + pa = isl_pw_aff_align_params(pa, isl_pw_multi_aff_get_space(pma)); + return pw_multi_aff_set_pw_aff(pma, pos, pa); +error: + isl_pw_multi_aff_free(pma); + isl_pw_aff_free(pa); + return NULL; +} + +#undef BASE +#define BASE pw_aff + +#include