From 962d4ad04871dbe8b4ac449661269ae05d429da3 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Thu, 10 May 2018 19:02:49 +0200 Subject: [PATCH] isl_map_coalesce: fix stride constraint integer division harmonization Commit isl-0.18-43-g0b4256f662 (isl_map_coalesce: harmonize integer divisions in stride constraints, Tue Oct 4 11:12:34 2016 +0200) introduced a harmonization of integer divisions in stride constraints that ends up getting used by the test case introduced in commit isl-0.18-46-g5334f05998 (isl_basic_map_simplify: reduce coefficients of integer divisions, Thu Jun 23 17:31:31 2016 +0200). The final clearing of the constant term of the integer division is, however, only valid if the integer division has been derived directly from the equality constraint. In the new test case, two disjuncts get combined first that have the equality constraints from which the integer division was derived replaced by a pair of inequality constraints. However, the result still has another equality constraint that could also be used to derive an expression for the integer division. Since this expression is different, the clearing of the constant term is not valid in this case. Only perform the clearing of the constant if the equality constraint is of the expected form. Note that this clearing is not needed for the test case introduced in isl-0.18-46-g5334f05998, even though the equality constraint is of the expected form here. Still, there may very well be other cases where this clearing is required, so the clearing is still performed whenever possible. Reported-by: Michael Kruse Signed-off-by: Sven Verdoolaege --- isl_coalesce.c | 12 ++++++++---- isl_constraint.c | 26 ++++++++++++++++++++++++++ isl_constraint_private.h | 3 +++ isl_local_space.c | 28 ++++++++++++++++++++++++++++ isl_local_space_private.h | 2 ++ isl_test.c | 4 ++++ 6 files changed, 71 insertions(+), 4 deletions(-) diff --git a/isl_coalesce.c b/isl_coalesce.c index 598eac23..7ad8548e 100644 --- a/isl_coalesce.c +++ b/isl_coalesce.c @@ -2393,7 +2393,7 @@ static isl_stat shift_div(struct isl_coalesce_info *info, int div, * * c + f + m a = 0 * - * The integer division expression is then of the form + * The integer division expression is then typically of the form * * a = floor((-f - c')/m) * @@ -2411,11 +2411,12 @@ static isl_stat shift_div(struct isl_coalesce_info *info, int div, * a' = (-f - (c mod m))/m = floor((-f)/m) * * because a' is an integer and 0 <= (c mod m) < m. - * The constant term of a' can therefore be zeroed out. + * The constant term of a' can therefore be zeroed out, + * but only if the integer division expression is of the expected form. */ static isl_stat normalize_stride_div(struct isl_coalesce_info *info, int div) { - isl_bool defined; + isl_bool defined, valid; isl_stat r; isl_constraint *c; isl_int shift, stride; @@ -2428,6 +2429,7 @@ static isl_stat normalize_stride_div(struct isl_coalesce_info *info, int div) return isl_stat_ok; if (!c) return isl_stat_error; + valid = isl_constraint_is_div_equality(c, div); isl_int_init(shift); isl_int_init(stride); isl_constraint_get_constant(c, &shift); @@ -2437,8 +2439,10 @@ static isl_stat normalize_stride_div(struct isl_coalesce_info *info, int div) isl_int_clear(stride); isl_int_clear(shift); isl_constraint_free(c); - if (r < 0) + if (r < 0 || valid < 0) return isl_stat_error; + if (!valid) + return isl_stat_ok; info->bmap = isl_basic_map_set_div_expr_constant_num_si_inplace( info->bmap, div, 0); if (!info->bmap) diff --git a/isl_constraint.c b/isl_constraint.c index f1b0b4ee..7612559a 100644 --- a/isl_constraint.c +++ b/isl_constraint.c @@ -717,6 +717,32 @@ int isl_constraint_is_div_constraint(__isl_keep isl_constraint *constraint) return 0; } +/* Is "constraint" an equality that corresponds to integer division "div"? + * + * That is, given an integer division of the form + * + * a = floor((f + c)/m) + * + * is the equality of the form + * + * -f + m d + c' = 0 + * ? + * Note that the constant term is not checked explicitly, but given + * that this is a valid equality constraint, the constant c' necessarily + * has a value close to -c. + */ +isl_bool isl_constraint_is_div_equality(__isl_keep isl_constraint *constraint, + unsigned div) +{ + isl_bool equality; + + equality = isl_constraint_is_equality(constraint); + if (equality < 0 || !equality) + return equality; + return isl_local_space_is_div_equality(constraint->ls, + constraint->v->el, div); +} + /* We manually set ISL_BASIC_SET_FINAL instead of calling * isl_basic_map_finalize because we want to keep the position * of the divs and we therefore do not want to throw away redundant divs. diff --git a/isl_constraint_private.h b/isl_constraint_private.h index 82f41df1..71939879 100644 --- a/isl_constraint_private.h +++ b/isl_constraint_private.h @@ -26,4 +26,7 @@ void isl_constraint_get_constant(__isl_keep isl_constraint *constraint, void isl_constraint_get_coefficient(__isl_keep isl_constraint *constraint, enum isl_dim_type type, int pos, isl_int *v); +isl_bool isl_constraint_is_div_equality(__isl_keep isl_constraint *constraint, + unsigned div); + #endif diff --git a/isl_local_space.c b/isl_local_space.c index eaf0700d..70edc6ff 100644 --- a/isl_local_space.c +++ b/isl_local_space.c @@ -1266,6 +1266,34 @@ isl_bool isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls, return isl_bool_true; } +/* Is the constraint pointed to by "constraint" one + * of an equality that corresponds to integer division "div" in "ls"? + * + * That is, given an integer division of the form + * + * a = floor((f + c)/m) + * + * is the equality of the form + * + * -f + m d + c' = 0 + * ? + * Note that the constant term is not checked explicitly, but given + * that this is a valid equality constraint, the constant c' necessarily + * has a value close to -c. + */ +isl_bool isl_local_space_is_div_equality(__isl_keep isl_local_space *ls, + isl_int *constraint, unsigned div) +{ + int sign; + isl_bool linear; + + linear = is_linear_div_constraint(ls, constraint, div, &sign); + if (linear < 0 || !linear) + return linear; + + return sign < 0; +} + /* * Set active[i] to 1 if the dimension at position i is involved * in the linear expression l. diff --git a/isl_local_space_private.h b/isl_local_space_private.h index a1bdb1b4..a31831b8 100644 --- a/isl_local_space_private.h +++ b/isl_local_space_private.h @@ -54,6 +54,8 @@ __isl_give isl_local_space *isl_local_space_realign( isl_bool isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls, isl_int *constraint, unsigned div); +isl_bool isl_local_space_is_div_equality(__isl_keep isl_local_space *ls, + isl_int *constraint, unsigned div); int *isl_local_space_get_active(__isl_keep isl_local_space *ls, isl_int *l); diff --git a/isl_test.c b/isl_test.c index f6ad0a0a..470ec536 100644 --- a/isl_test.c +++ b/isl_test.c @@ -1891,6 +1891,10 @@ struct { { 0, "{ [a, b] : a >= 0 and 0 <= b <= 1 - a; [-1, 3] }" }, { 1, "{ [a, b] : a, b >= 0 and a + 2b <= 2; [1, 1] }" }, { 0, "{ [a, b] : a, b >= 0 and a + 2b <= 2; [2, 1] }" }, + { 0, "{ [a, c] : (2 + a) mod 4 = 0 or " + "(c = 4 + a and 4 * floor((a)/4) = a and a >= 0 and a <= 4) or " + "(c = 3 + a and 4 * floor((-1 + a)/4) = -1 + a and " + "a > 0 and a <= 5) }" }, }; /* A specialized coalescing test case that would result -- 2.11.4.GIT