From d1f04b14ba623e32fb592ea5412398df4985628d Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Fri, 8 May 2015 08:50:14 +0200 Subject: [PATCH] isl_ast_expr_from_aff: avoid extracting modulos with very large coefficients When looking for opportunities for writing an fdiv_q in terms of a modulo, we check the explicitly available constraints first. These constraints may include bounds on integer variables to the maximal value of some integer type. We do not want to use such constraints since the corresponding modulo expression will include this large constant value. With any luck, there is still another bound hidden in the constraints that does not have such a large constant term. For example, on the new test case, we would produce code like this for (int c2 = 0; c2 < -((-n + 2147483648) % 32) + 32; c2 += 1) for (int c3 = 0; c3 <= 31; c3 += 1) S_1(((-n + 2147483648) % 32) + n + c2 - 32, c1 + c3); because the upper bound on n is explicitly available in the constraints, while the lower bound on n has been eliminated because it is implied by other constraints. By rejecting the upper bound, the AST generator is forced to look for a lower bound on n and in the end produces for (int c2 = 0; c2 < n % 32; c2 += 1) for (int c3 = 0; c3 <= 31; c3 += 1) S_1(-((n - 1) % 32) + n + c2 - 1, c1 + c3); Signed-off-by: Sven Verdoolaege --- isl_ast_build_expr.c | 15 +++++++++++++++ test_inputs/codegen/isolate7.c | 34 ++++++++++++++++++++++++++++++++++ test_inputs/codegen/isolate7.st | 16 ++++++++++++++++ 3 files changed, 65 insertions(+) create mode 100644 test_inputs/codegen/isolate7.c create mode 100644 test_inputs/codegen/isolate7.st diff --git a/isl_ast_build_expr.c b/isl_ast_build_expr.c index bdd70e79..fcd59c2f 100644 --- a/isl_ast_build_expr.c +++ b/isl_ast_build_expr.c @@ -661,6 +661,12 @@ static int mod_constraint_is_simpler(struct isl_extract_mod_data *data, * not to involve any coefficients that are multiples of d, "c" may * very well involve such coefficients. This means that we may actually * miss some cases. + * + * If the constant term is "too large", then the constraint is rejected, + * where "too large" is fairly arbitrarily set to 1 << 15. + * We do this to avoid picking up constraints that bound a variable + * by a very large number, say the largest or smallest possible + * variable in the representation of some integer type. */ static isl_stat check_parallel_or_opposite(__isl_take isl_constraint *c, void *user) @@ -684,6 +690,15 @@ static isl_stat check_parallel_or_opposite(__isl_take isl_constraint *c, } } + if (parallel || opposite) { + isl_val *v; + + v = isl_val_abs(isl_constraint_get_constant_val(c)); + if (isl_val_cmp_si(v, 1 << 15) > 0) + parallel = opposite = 0; + isl_val_free(v); + } + for (t = 0; t < 2; ++t) { for (i = 0; i < n[t]; ++i) { isl_val *v1, *v2; diff --git a/test_inputs/codegen/isolate7.c b/test_inputs/codegen/isolate7.c new file mode 100644 index 00000000..bc304cdc --- /dev/null +++ b/test_inputs/codegen/isolate7.c @@ -0,0 +1,34 @@ +{ + for (int c0 = 0; c0 < n - 31; c0 += 32) + for (int c1 = 0; c1 <= n; c1 += 32) { + if (n >= c1 + 32) { + for (int c2 = 0; c2 <= 31; c2 += 1) + for (int c3 = 0; c3 <= 31; c3 += 1) + S_1(c0 + c2, c1 + c3); + } else + for (int c2 = 0; c2 <= 31; c2 += 1) { + for (int c3 = 0; c3 < n - c1; c3 += 1) + S_1(c0 + c2, c1 + c3); + S_2(c0 + c2); + } + } + if (n >= 32) { + for (int c1 = 0; c1 < n; c1 += 32) { + if (n >= c1 + 32) { + for (int c2 = 0; c2 < n % 32; c2 += 1) + for (int c3 = 0; c3 <= 31; c3 += 1) + S_1(-((n - 1) % 32) + n + c2 - 1, c1 + c3); + } else + for (int c2 = 0; c2 < n - c1; c2 += 1) { + for (int c3 = 0; c3 < n - c1; c3 += 1) + S_1(c1 + c2, c1 + c3); + S_2(c1 + c2); + } + } + } else + for (int c2 = 0; c2 < n; c2 += 1) { + for (int c3 = 0; c3 < n; c3 += 1) + S_1(c2, c3); + S_2(c2); + } +} diff --git a/test_inputs/codegen/isolate7.st b/test_inputs/codegen/isolate7.st new file mode 100644 index 00000000..673eb08b --- /dev/null +++ b/test_inputs/codegen/isolate7.st @@ -0,0 +1,16 @@ +# Check that no expressions of the form ((-n + 2147483648) % 32) are produced. +domain: "[n] -> { S_2[i] : i >= 0 and i <= -1 + n; S_1[i, j] : j >= 0 and j <= -1 + n and i >= 0 and i <= -1 + n }" +child: + context: "[n] -> { [] : n <= 2147483647 and n >= 0 }" + child: + schedule: "[n] -> [{ S_1[i, j] -> [(32*floor((i)/32))]; S_2[i] -> [(32*floor((i)/32))] }, { S_1[i, j] -> [(32*floor((j)/32))]; S_2[i] -> [(32*floor((n)/32))] }]" + permutable: 1 + options: "[n] -> { atomic[i0] : i0 >= 0 and i0 <= 1; isolate[[] -> [i0, i1]] : (exists (e0 = floor((i0)/32), e1 = floor((i1)/32): 32e0 = i0 and 32e1 = i1 and i0 >= 0 and i0 <= -32 + n and i1 >= 0 and i1 <= n)) or (exists (e0 = floor((i0)/32), e1 = floor((i1)/32): 32e0 = i0 and 32e1 = i1 and i0 >= 0 and i0 <= -32 + n and i1 >= -31 + n and i1 <= -31 + 2n)) }" + child: + schedule: "[n] -> [{ S_1[i, j] -> [(i - 32*floor((i)/32))]; S_2[i] -> [(i - 32*floor((i)/32))] }, { S_1[i, j] -> [(j - 32*floor((j)/32))]; S_2[i] -> [(n - 32*floor((n)/32))] }]" + permutable: 1 + options: "{ separate[i0] : i0 >= 0 and i0 <= 1 }" + child: + sequence: + - filter: "[n] -> { S_1[i, j] }" + - filter: "[n] -> { S_2[i] }" -- 2.11.4.GIT