X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_aff.c;h=e9d728658aaf234cb2d914662ce1f7b0e566bdec;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=9ad26d6dfd04bf2c9d70b35bcc6f996b9433fdff;hpb=9c833e66e1dffc229594631e4bb07cf410c9f6a9;p=platform%2Fupstream%2Fisl.git diff --git a/isl_aff.c b/isl_aff.c index 9ad26d6..e9d7286 100644 --- a/isl_aff.c +++ b/isl_aff.c @@ -758,7 +758,7 @@ static __isl_give isl_aff *plug_in_integral_divs(__isl_take isl_aff *aff) 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); + 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) @@ -785,6 +785,50 @@ error: 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 @@ -889,6 +933,7 @@ __isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff) 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; @@ -955,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; } @@ -994,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) { @@ -1004,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; } @@ -1276,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); @@ -1311,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); @@ -1363,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; @@ -1372,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. */ @@ -1388,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; @@ -1397,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. */ @@ -1855,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); @@ -1885,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) @@ -2509,6 +2600,51 @@ __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); } +/* Mark the domains of "pwaff" as rational. + */ +__isl_give isl_pw_aff *isl_pw_aff_set_rational(__isl_take isl_pw_aff *pwaff) +{ + int i; + + pwaff = isl_pw_aff_cow(pwaff); + if (!pwaff) + return NULL; + if (pwaff->n == 0) + return pwaff; + + 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 pwaff; +} + +/* Mark the domains of the elements of "list" as rational. + */ +__isl_give isl_pw_aff_list *isl_pw_aff_list_set_rational( + __isl_take isl_pw_aff_list *list) +{ + int i, n; + + if (!list) + return NULL; + if (list->n == 0) + return list; + + n = list->n; + for (i = 0; i < n; ++i) { + isl_pw_aff *pa; + + 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 list; +} + #undef BASE #define BASE aff @@ -3134,29 +3270,13 @@ static __isl_give isl_pw_multi_aff *plain_pw_multi_aff_from_map( * 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. */ -__isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_map(__isl_take isl_map *map) +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; - isl_basic_map *hull; - - if (!map) - return NULL; - - hull = isl_map_affine_hull(isl_map_copy(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) - goto error; sv = isl_map_is_single_valued(map); if (sv < 0) @@ -3185,6 +3305,457 @@ error: 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; +} + +/* 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 *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; + + 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. + * + * 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, j; + int sv; + isl_basic_map *hull; + unsigned n_out; + unsigned o_out; + unsigned n_div; + unsigned o_div; + isl_int gcd; + + if (!map) + return NULL; + + hull = isl_map_affine_hull(isl_map_copy(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); + if (sv < 0) + hull = isl_basic_map_free(hull); + if (!hull) + goto error; + + n_div = isl_basic_map_dim(hull, isl_dim_div); + o_div = isl_basic_map_offset(hull, isl_dim_div); + + if (n_div == 0) { + isl_basic_map_free(hull); + return pw_multi_aff_from_map_check_div(map); + } + + 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_int_clear(gcd); + isl_basic_map_free(hull); + return pw_multi_aff_from_map_check_div(map); +error: + isl_map_free(map); + return NULL; +} + __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_set(__isl_take isl_set *set) { return isl_pw_multi_aff_from_map(set); @@ -3321,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; } @@ -3341,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 @@ -3679,6 +4428,30 @@ error: } /* Given two aligned isl_pw_multi_affs A -> B and C -> D, + * construct an isl_pw_multi_aff (A * C) -> [B -> D]. + */ +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) +{ + isl_space *space; + + 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); +} + +/* 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, * construct an isl_pw_multi_aff (A * C) -> (B, D). */ static __isl_give isl_pw_multi_aff *pw_multi_aff_flat_range_product( @@ -3817,3 +4590,8 @@ error: isl_pw_aff_free(pa); return NULL; } + +#undef BASE +#define BASE pw_aff + +#include