From d18103e58a9a7781067f6141eab3227a2d75cc6c Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Wed, 22 Jul 2020 16:44:18 +0200 Subject: [PATCH] isl_aff.c: pw_multi_aff_from_map_div: allow nested integer divisions That is, allow the constraint from which an integer division is constructed to itself involve integer divisions. This prepares for an upcoming commit that will extend the detection of the constraint in isl_basic_map_find_output_lower_div_constraint in a similar way. Note that pw_multi_aff_from_map_div now uses the local space of the basic map, which may involve local variables without a known integer division expression, even though the coefficients of those variables are known to be zero in the constraint from which the affine expression is constructed. This still causes problems since such local variables are not expected to appear in the local space at all. Remove these local variables before the construction of the affine expression. Reviewed-by: Tianjiao Sun Signed-off-by: Sven Verdoolaege --- isl_aff.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++-- isl_map.c | 19 ++++++++++++------- 2 files changed, 67 insertions(+), 9 deletions(-) diff --git a/isl_aff.c b/isl_aff.c index b4e8a35a..2635c2cc 100644 --- a/isl_aff.c +++ b/isl_aff.c @@ -5203,6 +5203,48 @@ error: return NULL; } +/* Construct an isl_aff from the given domain local space "ls" and + * coefficients "v", where the local space may involve + * local variables without a known expression, as long as these + * do not have a non-zero coefficient in "v". + * These need to be pruned away first since an isl_aff cannot + * reference any local variables without a known expression. + * For simplicity, remove all local variables that have a zero coefficient and + * that are not used in other local variables with a non-zero coefficient. + */ +static __isl_give isl_aff *isl_aff_alloc_vec_prune( + __isl_take isl_local_space *ls, __isl_take isl_vec *v) +{ + int i; + isl_size n_div, v_div; + + n_div = isl_local_space_dim(ls, isl_dim_div); + v_div = isl_local_space_var_offset(ls, isl_dim_div); + if (n_div < 0 || v_div < 0 || !v) + goto error; + for (i = n_div - 1; i >= 0; --i) { + isl_bool involves; + + if (!isl_int_is_zero(v->el[1 + 1 + v_div + i])) + continue; + involves = isl_local_space_involves_dims(ls, isl_dim_div, i, 1); + if (involves < 0) + goto error; + if (involves) + continue; + ls = isl_local_space_drop_dims(ls, isl_dim_div, i, 1); + v = isl_vec_drop_els(v, 1 + 1 + v_div + i, 1); + if (!v) + goto error; + } + + return isl_aff_alloc_vec(ls, v); +error: + isl_local_space_free(ls); + isl_vec_free(v); + 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 @@ -5213,6 +5255,8 @@ error: * * e(...) + c1 - m x >= 0 * + * with e(...) an expression that does not involve any other output dimensions. + * * * Let "map" be of the form * @@ -5229,6 +5273,11 @@ error: * 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. + * + * The constraint "i" is guaranteed by the caller not to involve + * any local variables without a known expression, but such local variables + * may appear in other constraints. They therefore need to be removed + * during the construction of the affine expression. */ 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) @@ -5252,16 +5301,20 @@ static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_div( if (n_in < 0) goto error; + ls = isl_basic_map_get_local_space(hull); + if (!is_set) + ls = isl_local_space_wrap(ls); v = isl_basic_map_inequality_extract_output_upper_bound(hull, i, d); isl_basic_map_free(hull); - ls = isl_local_space_from_space(isl_space_copy(space)); - aff = isl_aff_alloc_vec_validated(ls, v); + aff = isl_aff_alloc_vec_prune(ls, v); aff = isl_aff_floor(aff); if (is_set) { + aff = isl_aff_project_domain_on_params(aff); isl_space_free(space); ma = isl_multi_aff_from_aff(aff); } else { + aff = isl_aff_domain_factor_domain(aff); ma = isl_multi_aff_identity(isl_space_map_from_set(space)); ma = isl_multi_aff_range_product(ma, isl_multi_aff_from_aff(aff)); diff --git a/isl_map.c b/isl_map.c index 6b75f534..eaebe45b 100644 --- a/isl_map.c +++ b/isl_map.c @@ -14309,14 +14309,17 @@ __isl_give isl_set *isl_set_preimage_multi_pw_aff(__isl_take isl_set *set, } /* Given that inequality "ineq" of "bmap" expresses an upper bound - * on the output dimension "pos" in terms of the parameters and - * the input dimensions, extract this upper bound. + * on the output dimension "pos" in terms of the parameters, + * the input dimensions and possibly some integer divisions, + * but not any other output dimensions, extract this upper bound + * as a function of all dimensions (with zero coefficients + * for the output dimensions). * * That is, the inequality is of the form * * e(...) + c - m x >= 0 * - * where e only depends on parameters and input dimensions. + * where e does not depend on any other output dimensions. * Return (e(...) + c) / m, with the denominator m in the first position. */ __isl_give isl_vec *isl_basic_map_inequality_extract_output_upper_bound( @@ -14324,17 +14327,19 @@ __isl_give isl_vec *isl_basic_map_inequality_extract_output_upper_bound( { isl_ctx *ctx; isl_vec *v; - isl_size v_out; + isl_size v_out, total; v_out = isl_basic_map_var_offset(bmap, isl_dim_out); - if (v_out < 0) + total = isl_basic_map_dim(bmap, isl_dim_all); + if (v_out < 0 || total < 0) return NULL; ctx = isl_basic_map_get_ctx(bmap); - v = isl_vec_alloc(ctx, 1 + 1 + v_out); + v = isl_vec_alloc(ctx, 1 + 1 + total); if (!v) return NULL; isl_int_neg(v->el[0], bmap->ineq[ineq][1 + v_out + pos]); - isl_seq_cpy(v->el + 1, bmap->ineq[ineq], 1 + v_out); + isl_seq_cpy(v->el + 1, bmap->ineq[ineq], 1 + total); + isl_int_set_si(v->el[1 + 1 + v_out + pos], 0); return v; } -- 2.11.4.GIT