On Sun, Mar 27, 2016 at 11:37 PM, Patrick Palka <[email protected]> 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
>
