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