From fe6f19f1118598bd5e7a129cc125633fbba9883d Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Mon, 11 Nov 2013 21:57:22 +0100 Subject: [PATCH] isl_ast_expr_from_constraint: detect stride constraints In particular, if an equality is of the form e - d floor(e/d) = 0 then directly convert it into e % d == 0 with '%' the isl_ast_op_zdiv_r operator. Do this rather than the default procedure of checking if (some variation of) e is non-negative and replacing d floor(e/d) by e - (e mod d). This saves some needless processing, but more importantly, it allows us to detect stride conditions even when e cannot be proven to be non-negative. For example, we can now write if (n % 2 == 0) instead of if (2 * floord(n, 2) == n) even when nothing is known about n. Signed-off-by: Sven Verdoolaege --- isl_ast_build_expr.c | 157 ++++++++++++++++++++++- test_inputs/codegen/cloog/jacobi-shared.c | 2 +- test_inputs/codegen/cloog/levenshtein-1-2-3.c | 4 +- test_inputs/codegen/cloog/reservoir-liu-zhuge1.c | 4 +- test_inputs/codegen/omega/guard1-0.c | 2 +- test_inputs/codegen/omega/guard1-1.c | 2 +- test_inputs/codegen/omega/iter9-0.c | 2 +- test_inputs/codegen/separate2.c | 2 +- test_inputs/codegen/shift2.c | 2 +- test_inputs/codegen/stride5.c | 2 +- 10 files changed, 163 insertions(+), 16 deletions(-) diff --git a/isl_ast_build_expr.c b/isl_ast_build_expr.c index db12a74c..2c3bfa3a 100644 --- a/isl_ast_build_expr.c +++ b/isl_ast_build_expr.c @@ -1038,10 +1038,143 @@ static int constant_is_considered_positive(__isl_keep isl_val *v, return isl_val_is_pos(v); } +/* Check if the equality + * + * aff = 0 + * + * represents a stride constraint on the integer division "pos". + * + * In particular, if the integer division "pos" is equal to + * + * floor(e/d) + * + * then check if aff is equal to + * + * e - d floor(e/d) + * + * or its opposite. + * + * If so, the equality is exactly + * + * e mod d = 0 + * + * Note that in principle we could also accept + * + * e - d floor(e'/d) + * + * where e and e' differ by a constant. + */ +static int is_stride_constraint(__isl_keep isl_aff *aff, int pos) +{ + isl_aff *div; + isl_val *c, *d; + int eq; + + div = isl_aff_get_div(aff, pos); + c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos); + d = isl_aff_get_denominator_val(div); + eq = isl_val_abs_eq(c, d); + if (eq >= 0 && eq) { + aff = isl_aff_copy(aff); + aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0); + div = isl_aff_scale_val(div, d); + if (isl_val_is_pos(c)) + div = isl_aff_neg(div); + eq = isl_aff_plain_is_equal(div, aff); + isl_aff_free(aff); + } else + isl_val_free(d); + isl_val_free(c); + isl_aff_free(div); + + return eq; +} + +/* Are all coefficients of "aff" (zero or) negative? + */ +static int all_negative_coefficients(__isl_keep isl_aff *aff) +{ + int i, n; + + if (!aff) + return 0; + + n = isl_aff_dim(aff, isl_dim_param); + for (i = 0; i < n; ++i) + if (isl_aff_coefficient_sgn(aff, isl_dim_param, i) > 0) + return 0; + + n = isl_aff_dim(aff, isl_dim_in); + for (i = 0; i < n; ++i) + if (isl_aff_coefficient_sgn(aff, isl_dim_in, i) > 0) + return 0; + + return 1; +} + +/* Give an equality of the form + * + * aff = e - d floor(e/d) = 0 + * + * or + * + * aff = -e + d floor(e/d) = 0 + * + * with the integer division "pos" equal to floor(e/d), + * construct the AST expression + * + * (isl_ast_op_eq, (isl_ast_op_zdiv_r, expr(e), expr(d)), expr(0)) + * + * If e only has negative coefficients, then construct + * + * (isl_ast_op_eq, (isl_ast_op_zdiv_r, expr(-e), expr(d)), expr(0)) + * + * instead. + */ +static __isl_give isl_ast_expr *extract_stride_constraint( + __isl_take isl_aff *aff, int pos, __isl_keep isl_ast_build *build) +{ + isl_ctx *ctx; + isl_val *c; + isl_ast_expr *expr, *cst; + + if (!aff) + return NULL; + + ctx = isl_aff_get_ctx(aff); + + c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos); + aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0); + + if (all_negative_coefficients(aff)) + aff = isl_aff_neg(aff); + + cst = isl_ast_expr_from_val(isl_val_abs(c)); + expr = isl_ast_expr_from_aff(aff, build); + + expr = isl_ast_expr_alloc_binary(isl_ast_op_zdiv_r, expr, cst); + cst = isl_ast_expr_alloc_int_si(ctx, 0); + expr = isl_ast_expr_alloc_binary(isl_ast_op_eq, expr, cst); + + return expr; +} + /* Construct an isl_ast_expr that evaluates the condition "constraint", * The result is simplified in terms of build->domain. * - * Let the constraint by either "a >= 0" or "a == 0". + * We first check if the constraint is an equality of the form + * + * e - d floor(e/d) = 0 + * + * i.e., + * + * e mod d = 0 + * + * If so, we convert it to + * + * (isl_ast_op_eq, (isl_ast_op_zdiv_r, expr(e), expr(d)), expr(0)) + * + * Otherwise, let the constraint by either "a >= 0" or "a == 0". * We first extract hidden modulo computations from "a" * and then collect all the terms with a positive coefficient in cons_pos * and the terms with a negative coefficient in cons_neg. @@ -1065,6 +1198,7 @@ static int constant_is_considered_positive(__isl_keep isl_val *v, static __isl_give isl_ast_expr *isl_ast_expr_from_constraint( __isl_take isl_constraint *constraint, __isl_keep isl_ast_build *build) { + int i, n; isl_ctx *ctx; isl_ast_expr *expr_pos; isl_ast_expr *expr_neg; @@ -1078,8 +1212,21 @@ static __isl_give isl_ast_expr *isl_ast_expr_from_constraint( return NULL; aff = isl_constraint_get_aff(constraint); + eq = isl_constraint_is_equality(constraint); + isl_constraint_free(constraint); - ctx = isl_constraint_get_ctx(constraint); + n = isl_aff_dim(aff, isl_dim_div); + if (eq && n > 0) + for (i = 0; i < n; ++i) { + int is_stride; + is_stride = is_stride_constraint(aff, i); + if (is_stride < 0) + goto error; + if (is_stride) + return extract_stride_constraint(aff, i, build); + } + + ctx = isl_aff_get_ctx(aff); expr_pos = isl_ast_expr_alloc_int_si(ctx, 0); expr_neg = isl_ast_expr_alloc_int_si(ctx, 0); @@ -1096,8 +1243,6 @@ static __isl_give isl_ast_expr *isl_ast_expr_from_constraint( expr_neg = isl_ast_expr_add_int(expr_neg, v); } - eq = isl_constraint_is_equality(constraint); - if (isl_ast_expr_get_type(expr_pos) == isl_ast_expr_int && isl_ast_expr_get_type(expr_neg) != isl_ast_expr_int) { type = eq ? isl_ast_op_eq : isl_ast_op_le; @@ -1107,9 +1252,11 @@ static __isl_give isl_ast_expr *isl_ast_expr_from_constraint( expr = isl_ast_expr_alloc_binary(type, expr_pos, expr_neg); } - isl_constraint_free(constraint); isl_aff_free(aff); return expr; +error: + isl_aff_free(aff); + return NULL; } /* Wrapper around isl_constraint_cmp_last_non_zero for use diff --git a/test_inputs/codegen/cloog/jacobi-shared.c b/test_inputs/codegen/cloog/jacobi-shared.c index ea5a97f3..50840a86 100644 --- a/test_inputs/codegen/cloog/jacobi-shared.c +++ b/test_inputs/codegen/cloog/jacobi-shared.c @@ -1,3 +1,3 @@ -if (((t1 + 31) % 32) + g2 >= 2 && N >= ((t1 + 31) % 32) + g2 + 2 && (h0 + 1) % 2 == 0) +if (((t1 + 31) % 32) + g2 >= 2 && N >= ((t1 + 31) % 32) + g2 + 2 && (h0 - 1) % 2 == 0) for (int c0 = max(((t0 + 15) % 16) + 1, ((g1 + t0 + 13) % 16) - g1 + 3); c0 <= min(32, N - g1 - 1); c0 += 16) S1(g1 + c0 - 1, ((t1 + 31) % 32) + g2); diff --git a/test_inputs/codegen/cloog/levenshtein-1-2-3.c b/test_inputs/codegen/cloog/levenshtein-1-2-3.c index 10fa2a39..0e470b4d 100644 --- a/test_inputs/codegen/cloog/levenshtein-1-2-3.c +++ b/test_inputs/codegen/cloog/levenshtein-1-2-3.c @@ -13,7 +13,7 @@ } for (int c0 = N + 2; c0 < 2 * M - N - 1; c0 += 1) { S7(c0, -N + (N + c0 + 1) / 2 - 1); - if ((-N + c0) % 2 == 0) { + if ((N - c0) % 2 == 0) { S5(c0, (-N + c0) / 2); S8(c0, (-N + c0) / 2); } @@ -21,7 +21,7 @@ S6(c0, c1); S8(c0, c1); } - if ((-N + c0) % 2 == 0) { + if ((N - c0) % 2 == 0) { S4(c0, (N + c0) / 2); S8(c0, (N + c0) / 2); } diff --git a/test_inputs/codegen/cloog/reservoir-liu-zhuge1.c b/test_inputs/codegen/cloog/reservoir-liu-zhuge1.c index 9a056967..dfc7d37d 100644 --- a/test_inputs/codegen/cloog/reservoir-liu-zhuge1.c +++ b/test_inputs/codegen/cloog/reservoir-liu-zhuge1.c @@ -2,13 +2,13 @@ if (M >= 0 && N >= 0) for (int c1 = -4; c1 <= 3 * M + N; c1 += 1) { if (3 * M + N >= c1 + 1 && c1 >= 3 * M) { S2(M, -3 * M + c1); - } else if (3 * M >= c1 + 4 && (c1 + 4) % 3 == 0) + } else if (3 * M >= c1 + 4 && (c1 - 2) % 3 == 0) S1((c1 + 4) / 3, 0); for (int c3 = max(-3 * M + c1 + 3, (c1 + 6) % 3); c3 <= min(N - 1, c1); c3 += 3) { S2((c1 - c3) / 3, c3); S1(((c1 - c3) / 3) + 1, c3 + 1); } - if (c1 >= N && (-N + c1) % 3 == 0) { + if (c1 >= N && (N - c1) % 3 == 0) { S2((-N + c1) / 3, N); } else if (N >= c1 + 4 && c1 >= -3) S1(0, c1 + 4); diff --git a/test_inputs/codegen/omega/guard1-0.c b/test_inputs/codegen/omega/guard1-0.c index 484715e3..555d644f 100644 --- a/test_inputs/codegen/omega/guard1-0.c +++ b/test_inputs/codegen/omega/guard1-0.c @@ -1,2 +1,2 @@ -if (n + 3 * floord(-n + m - 2, 3) + 2 == m) +if ((n - m + 2) % 3 == 0) s0(n, m); diff --git a/test_inputs/codegen/omega/guard1-1.c b/test_inputs/codegen/omega/guard1-1.c index 1d84fe28..335c1b83 100644 --- a/test_inputs/codegen/omega/guard1-1.c +++ b/test_inputs/codegen/omega/guard1-1.c @@ -1,2 +1,2 @@ -if (n + 2 * floord(-n + m - 1, 2) + 1 == m) +if ((n - m + 1) % 2 == 0) s0(n, m); diff --git a/test_inputs/codegen/omega/iter9-0.c b/test_inputs/codegen/omega/iter9-0.c index f1dd3194..9b8522ba 100644 --- a/test_inputs/codegen/omega/iter9-0.c +++ b/test_inputs/codegen/omega/iter9-0.c @@ -6,6 +6,6 @@ for (int c0 = 1; c0 <= 15; c0 += 1) { s2(c0); s1(c0); } - if (((-exprVar1 + 15) % 8) + c0 <= 15 || (c0 >= exprVar1 + 1 && (-exprVar1 + c0 - 1) % 8 == 0)) + if (((-exprVar1 + 15) % 8) + c0 <= 15 || (c0 >= exprVar1 + 1 && (exprVar1 - c0 + 1) % 8 == 0)) s5(c0); } diff --git a/test_inputs/codegen/separate2.c b/test_inputs/codegen/separate2.c index 03811d0e..81668215 100644 --- a/test_inputs/codegen/separate2.c +++ b/test_inputs/codegen/separate2.c @@ -2,7 +2,7 @@ if ((length - 1) % 16 <= 14) for (int c0 = 0; c0 <= 1; c0 += 1) for (int c5 = 0; c5 <= 31; c5 += 1) for (int c6 = max(0, 2 * ((length - 1) % 16) + 2 * c5 - 60); c6 <= 30; c6 += 1) { - if (length + c5 >= ((length - 1) % 32) + 2 && (length - 1) % 32 >= c5 && 2 * ((length - 1) % 32) + c6 >= 2 * c5 && 2 * c5 + 30 >= 2 * ((length - 1) % 32) + c6 && 2 * ((length - 1) % 32) + c6 == 2 * ((length - 1) % 16) + 2 * c5 && (2 * c5 - c6 + 31) % 32 == 31) + if (length + c5 >= ((length - 1) % 32) + 2 && (length - 1) % 32 >= c5 && 2 * ((length - 1) % 32) + c6 >= 2 * c5 && 2 * c5 + 30 >= 2 * ((length - 1) % 32) + c6 && 2 * ((length - 1) % 32) + c6 == 2 * ((length - 1) % 16) + 2 * c5 && (2 * c5 - c6) % 32 == 0) S_3(c0, 0, (c6 / 2) - ((length - 1) % 16) + length - 1); if (length <= 16 && length >= c5 + 1 && c6 >= 1 && length >= c6) S_0(c0, c5, c6 - 1); diff --git a/test_inputs/codegen/shift2.c b/test_inputs/codegen/shift2.c index 59397b86..30ea633b 100644 --- a/test_inputs/codegen/shift2.c +++ b/test_inputs/codegen/shift2.c @@ -27,7 +27,7 @@ for (int c0 = 0; c0 <= 1; c0 += 1) { if (c3 + 30 >= 2 * length && c4 == 0) S_4(c0); } - if (c2 + 16 == length && (length + 16) % 32 == 0) + if (c2 + 16 == length && (length - 16) % 32 == 0) S_4(c0); } else if (length == 0) { S_4(c0); diff --git a/test_inputs/codegen/stride5.c b/test_inputs/codegen/stride5.c index 37b9052a..ee89e367 100644 --- a/test_inputs/codegen/stride5.c +++ b/test_inputs/codegen/stride5.c @@ -1,3 +1,3 @@ -if (2 * floord(n, 2) == n) +if (n % 2 == 0) for (int c0 = (n / 2) + 2 * floord(-n - 1, 4) + 2; c0 <= 100; c0 += 2) S(c0); -- 2.11.4.GIT