On Sun, 27 Mar 2016, Patrick Palka wrote:
> In unrolling of the inner loop in the test case below we introduce
> unreachable code that otherwise contains out-of-bounds array accesses.
> This is because the estimation of the maximum number of iterations of
> the inner loop is too conservative: we assume 6 iterations instead of
> the actual 4.
>
> Nonetheless, VRP should be able to tell that the code is unreachable so
> that it doesn't warn about it. The only thing holding VRP back is that
> it doesn't look through conditionals of the form
>
> if (j_10 != CST1) where j_10 = j_9 + CST2
>
> so that it could add the assertion
>
> j_9 != (CST1 - CST2)
>
> This patch teaches VRP to detect such conditionals and to add such
> assertions, so that it could remove instead of warn about the
> unreachable code created during loop unrolling.
>
> What this addition does with the test case below is something like this:
>
> ASSERT_EXPR (i <= 5);
> for (i = 1; i < 6; i++)
> {
> j = i - 1;
> if (j == 0)
> break;
> // ASSERT_EXPR (i != 1)
> bar[j] = baz[j];
>
> j = i - 2
> if (j == 0)
> break;
> // ASSERT_EXPR (i != 2)
> bar[j] = baz[j];
>
> j = i - 3
> if (j == 0)
> break;
> // ASSERT_EXPR (i != 3)
> bar[j] = baz[j];
>
> j = i - 4
> if (j == 0)
> break;
> // ASSERT_EXPR (i != 4)
> bar[j] = baz[j];
>
> j = i - 5
> if (j == 0)
> break;
> // ASSERT_EXPR (i != 5)
> bar[j] = baz[j];
>
> j = i - 6
> if (j == 0)
> break;
> // ASSERT_EXPR (i != 6)
> bar[j] = baz[j]; // unreachable because (i != 6 && i <= 5) is always false
> }
>
> (I think the patch I sent a year ago that improved the
> register_edge_assert stuff would have fixed this too. I'll try to
> post it again during next stage 1.
> https://gcc.gnu.org/ml/gcc-patches/2014-11/msg00908.html)
>
> Bootstrap + regtest in progress on x86_64-pc-linux-gnu, does this look
> OK to commit after testing?
>
> gcc/ChangeLog:
>
> PR tree-optimization/59124
> * tree-vrp.c (register_edge_assert_for): For NAME != CST1
> where NAME = A + CST2 add the assertion A != (CST1 - CST2).
>
> gcc/testsuite/ChangeLog:
>
> PR tree-optimization/59124
> * gcc.dg/Warray-bounds-19.c: New test.
> ---
> gcc/testsuite/gcc.dg/Warray-bounds-19.c | 17 +++++++++++++++++
> gcc/tree-vrp.c | 22 ++++++++++++++++++++++
> 2 files changed, 39 insertions(+)
> create mode 100644 gcc/testsuite/gcc.dg/Warray-bounds-19.c
>
> diff --git a/gcc/testsuite/gcc.dg/Warray-bounds-19.c
> b/gcc/testsuite/gcc.dg/Warray-bounds-19.c
> new file mode 100644
> index 0000000..e2f9661
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/Warray-bounds-19.c
> @@ -0,0 +1,17 @@
> +/* PR tree-optimization/59124 */
> +/* { dg-options "-O3 -Warray-bounds" } */
> +
> +unsigned baz[6];
> +
> +void foo(unsigned *bar, unsigned n)
> +{
> + unsigned i, j;
> +
> + if (n > 6)
> + n = 6;
> +
> + for (i = 1; i < n; i++)
> + for (j = i - 1; j > 0; j--)
> + bar[j - 1] = baz[j - 1];
> +}
> +
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index b5654c5..31bd575 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -5820,6 +5820,28 @@ register_edge_assert_for (tree name, edge e,
> gimple_stmt_iterator si,
> }
> }
>
> + /* In the case of NAME != CST1 where NAME = A + CST2 we can
> + assert that NAME != (CST1 - CST2). */
This should say A != (...) not NAME != (...)
> + if ((comp_code == EQ_EXPR || comp_code == NE_EXPR)
> + && TREE_CODE (val) == INTEGER_CST)
> + {
> + gimple *def_stmt = SSA_NAME_DEF_STMT (name);
> +
> + if (is_gimple_assign (def_stmt)
> + && gimple_assign_rhs_code (def_stmt) == PLUS_EXPR)
> + {
> + tree op0 = gimple_assign_rhs1 (def_stmt);
> + tree op1 = gimple_assign_rhs2 (def_stmt);
> + if (TREE_CODE (op0) == SSA_NAME
> + && TREE_CODE (op1) == INTEGER_CST)
> + {
> + op1 = int_const_binop (MINUS_EXPR, val, op1);
> + register_edge_assert_for_2 (op0, e, si, comp_code,
> + op0, op1, is_else_edge);
The last argument to register_edge_assert_for_2() should be false not
is_else_edge since comp_code is already inverted.
Consider these two things fixed. Also I moved down the new code so that
it's at the very bottom of register_edge_assert_for. Here's an updated
patch that passes bootstrap + regtest.
-- 8< --
gcc/ChangeLog:
PR tree-optimization/59124
* tree-vrp.c (register_edge_assert_for): For NAME != CST1
where NAME = A + CST2 add the assertion A != (CST1 - CST2).
gcc/testsuite/ChangeLog:
PR tree-optimization/59124
* gcc.dg/Warray-bounds-19.c: New test.
---
gcc/testsuite/gcc.dg/Warray-bounds-19.c | 17 +++++++++++++++++
gcc/tree-vrp.c | 22 ++++++++++++++++++++++
2 files changed, 39 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/Warray-bounds-19.c
diff --git a/gcc/testsuite/gcc.dg/Warray-bounds-19.c
b/gcc/testsuite/gcc.dg/Warray-bounds-19.c
new file mode 100644
index 0000000..e2f9661
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/Warray-bounds-19.c
@@ -0,0 +1,17 @@
+/* PR tree-optimization/59124 */
+/* { dg-options "-O3 -Warray-bounds" } */
+
+unsigned baz[6];
+
+void foo(unsigned *bar, unsigned n)
+{
+ unsigned i, j;
+
+ if (n > 6)
+ n = 6;
+
+ for (i = 1; i < n; i++)
+ for (j = i - 1; j > 0; j--)
+ bar[j - 1] = baz[j - 1];
+}
+
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index b5654c5..a009f7a 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -5841,6 +5841,28 @@ register_edge_assert_for (tree name, edge e,
gimple_stmt_iterator si,
register_edge_assert_for_1 (op1, EQ_EXPR, e, si);
}
}
+
+ /* In the case of NAME != CST1 where NAME = A + CST2 we can
+ assert that A != (CST1 - CST2). */
+ if ((comp_code == EQ_EXPR || comp_code == NE_EXPR)
+ && TREE_CODE (val) == INTEGER_CST)
+ {
+ gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+
+ if (is_gimple_assign (def_stmt)
+ && gimple_assign_rhs_code (def_stmt) == PLUS_EXPR)
+ {
+ tree op0 = gimple_assign_rhs1 (def_stmt);
+ tree op1 = gimple_assign_rhs2 (def_stmt);
+ if (TREE_CODE (op0) == SSA_NAME
+ && TREE_CODE (op1) == INTEGER_CST)
+ {
+ op1 = int_const_binop (MINUS_EXPR, val, op1);
+ register_edge_assert_for_2 (op0, e, si, comp_code,
+ op0, op1, false);
+ }
+ }
+ }
}
--
2.8.0.rc3.27.gade0865
