[PATCH] Fix PR tree-optimization/59124 (bogus -Warray-bounds warning)
Patrick Palka
patrick@parcs.ath.cx
Tue Mar 29 11:41:00 GMT 2016
On Tue, 29 Mar 2016, Richard Biener wrote:
> 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.
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 :(
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?
-- >8 --
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 | 19 +++++++++++++++++++
2 files changed, 36 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..87db548 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -5310,6 +5310,25 @@ 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)
+ {
+ 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))
+ {
+ op1 = int_const_binop (MINUS_EXPR, 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
More information about the Gcc-patches
mailing list