On Tue, 29 Mar 2016, Richard Biener wrote: > On Tue, Mar 29, 2016 at 1:23 PM, Patrick Palka <patr...@parcs.ath.cx> wrote: > > On Tue, 29 Mar 2016, Richard Biener wrote: > > > >> On Sun, Mar 27, 2016 at 11:37 PM, Patrick Palka <patr...@parcs.ath.cx> > >> wrote: > >> > 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); > >> > >> Please add > >> > >> if (TREE_OVERFLOW_P (op1)) > >> op1 = drop_tree_overflow (op1); > >> > >> here. > > > > Done. > > > >> > >> > + register_edge_assert_for_2 (op0, e, si, comp_code, > >> > + op0, op1, false); > >> > >> I wonder why you recurse to register_edge_assert_for_2 here rather than > >> calling register_new_assert_for which is what the cases in > >> register_edge_assert_for_2 > >> do. And incidentially a more generic case of this pattern is handled > >> there, so why > >> not add this code in register_edge_assert_for_2 in the first place? There > >> is > >> > >> > >> if (TREE_CODE_CLASS (comp_code) == tcc_comparison > >> && TREE_CODE (val) == INTEGER_CST) > >> { > >> gimple *def_stmt = SSA_NAME_DEF_STMT (name); > >> ... > >> > >> the case itself is simple enough to be worth adding to fix the regression. > > > > Done. I figured recursing would help to identify other useful > > assertions to add but it's not necessary to fix the test case. > > > >> > >> I also wonder why we don't have a match.pd / fold-const case for this, > >> the forwprop pass between cunrolli and vrp1 should have simplified > >> this then. fold_comparison has it (so it didn't get moved to match.pd): > >> > >> /* Transform comparisons of the form X +- C1 CMP C2 to X CMP C2 -+ C1. > >> */ > >> if ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR) > >> && (equality_code > >> ... > >> > >> it's also more general in that it handles non-equality compares when > >> overflow > >> is undefined. Note that at this stage I'm more comfortable with doing the > >> VRP trick than adding a new match.pd pattern (even if only handling the > >> equality compare case) - we'd need to think about what to exactly do > >> for a non-single-use case (probably depends on C2, if that's zero then > >> X +- C1 might set CC codes properly already). > > > > The operands in question are not single-use and C2 is zero so we'd > > already be hitting the edge case :( > > Bah ... :/ > > > Here's an updated patch that calls drop_tree_overflow and moves it all > > to register_edge_assert_for_2. Does this look OK to commit after > > bootstrap and regtest? > > Ok - bonus points if you handle MINUS_EXPR for symmetry reasons > even if not strictly necessary at this point. > > Thanks, > Richard.
Thanks, here's what I committed which handles MINUS_EXPR too: gcc/ChangeLog: PR tree-optimization/59124 * tree-vrp.c (register_edge_assert_for_2): 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 | 21 +++++++++++++++++++++ 2 files changed, 38 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..bbdf9ce 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -5310,6 +5310,27 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi, if (is_gimple_assign (def_stmt)) rhs_code = gimple_assign_rhs_code (def_stmt); + /* 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) + && (rhs_code == PLUS_EXPR || rhs_code == MINUS_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 + && live_on_edge (e, op0) + && !has_single_use (op0)) + { + enum tree_code reverse_op = (rhs_code == PLUS_EXPR + ? MINUS_EXPR : PLUS_EXPR); + op1 = int_const_binop (reverse_op, val, op1); + if (TREE_OVERFLOW (op1)) + op1 = drop_tree_overflow (op1); + register_new_assert_for (op0, op0, comp_code, op1, NULL, e, bsi); + } + } + /* Add asserts for NAME cmp CST and NAME being defined as NAME = (int) NAME2. */ if (!TYPE_UNSIGNED (TREE_TYPE (val)) -- 2.8.0.rc3.27.gade0865