diff mbox

Fix PR tree-optimization/59124 (bogus -Warray-bounds warning)

Message ID alpine.DEB.2.20.11.1603292104510.1308@idea
State New
Headers show

Commit Message

Patrick Palka March 30, 2016, 1:06 a.m. UTC 
On Tue, 29 Mar 2016, Richard Biener wrote:

> On Tue, Mar 29, 2016 at 1:23 PM, Patrick Palka <patrick@parcs.ath.cx> wrote:
> > 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 :(
> 
> 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 mbox

Patch

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))