| Message ID | 1459105083-24035-1-git-send-email-patrick@parcs.ath.cx |
|---|---|
| State | New |
| Headers | show |
On Sun, Mar 27, 2016 at 2:58 PM, Patrick Palka <patrick@parcs.ath.cx> 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 > } Er, sorry, this illustration is wrong. First off, break; should say continue;. Second, we actually find that the second-to-last bar[j] = baz[j]; assignment is unreachable, since VRP can use the ASSERT_EXPRs to determine that i == 5 when evaluating the conditional immediately preceding the second-to-last array access. And because the second-to-last assignment is unreachable then so is the last assignment. So we remove two unreachable array accesses (and their enclosing basic blocks) and thus suppress the two -Warray-bounds warnings.
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). */ + 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); + } + } + } + /* In the case of NAME == 0 or NAME != 1, for BIT_IOR_EXPR defining statement of NAME we can assert both operands of the BIT_IOR_EXPR have zero value. */
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