| Message ID | alpine.DEB.2.20.11.1603271735380.1308@idea |
|---|---|
| State | New |
| Headers | show |
On Sun, Mar 27, 2016 at 11:37 PM, Patrick Palka <patrick@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. > + 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. 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). Thanks, Richard. > + } > + } > + } > } > > -- > 2.8.0.rc3.27.gade0865 >
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); + } + } + } }