[RFA,PR,tree-optimization/79095,2/4] Add infrastructure to detect overflow checks

This is the second in the 4 part series to address 79095.  This patch 
introduces a new function into tree-vrp.c to allow for the detection of 
overflow checks of the form A OP A + CST (for unsigned/wrapping A).

This is implemented by first checking for A OP B, we then conditionally 
walk the ASSERT_EXPR chain for B to produce B'.  We then look at the 
defining statement for B or B' to see if it has the form B = X + CST or 
B' = X + CST respectively.

Then we conditionally walk the ASSERT_EXPR chain for A to see if it 
resolves to X at any point.  There have been cases where no walking was 
necessary to show that X resolves to A.  Other cases have required 
walking part or the entire ASSERT_EXPR chain.

We do not walk during propagation, but do walk during 
folding/simplification.

At this point we have an overflow check of the appropriate form.  We 
compute an updated constant so that we can check for overflow with 
expressions like

A > 0xfffffffe

or

A <= 0

Those are particularly interesting forms as they collapse into equality 
tests (next patch).  The code supports other forms, but they're not as 
useful because they don't end up generating equality tests or allow for 
constant propagation.

Bootstrapped and regression tested with the other patches in this 
series.  OK for the trunk?
* tree-vrp.c (overflow_comparison_p): New function.

On Sat, Feb 4, 2017 at 3:52 PM, Jeff Law <law@redhat.com> wrote:
>
> This is the second in the 4 part series to address 79095.  This patch
> introduces a new function into tree-vrp.c to allow for the detection of
> overflow checks of the form A OP A + CST (for unsigned/wrapping A).
>
> This is implemented by first checking for A OP B, we then conditionally walk
> the ASSERT_EXPR chain for B to produce B'.  We then look at the defining
> statement for B or B' to see if it has the form B = X + CST or B' = X + CST
> respectively.
>
> Then we conditionally walk the ASSERT_EXPR chain for A to see if it resolves
> to X at any point.  There have been cases where no walking was necessary to
> show that X resolves to A.  Other cases have required walking part or the
> entire ASSERT_EXPR chain.
>
> We do not walk during propagation, but do walk during
> folding/simplification.
>
> At this point we have an overflow check of the appropriate form.  We compute
> an updated constant so that we can check for overflow with expressions like
>
> A > 0xfffffffe
>
> or
>
> A <= 0
>
> Those are particularly interesting forms as they collapse into equality
> tests (next patch).  The code supports other forms, but they're not as
> useful because they don't end up generating equality tests or allow for
> constant propagation.
>
> Bootstrapped and regression tested with the other patches in this series.
> OK for the trunk?
>
>
>
>
>         * tree-vrp.c (overflow_comparison_p): New function.
>
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index 3338d8b..6459c71 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -5189,6 +5189,94 @@ masked_increment (const wide_int &val_in, const
> wide_int &mask,
>    return val ^ sgnbit;
>  }
>
> +/* OP0 CODE OP1 is a comparison.  Examine the comparison and potentially
> +   OP1's defining statement to see if it ultimately has the form
> +   OP0 CODE (OP0 PLUS INTEGER_CST)
> +
> +   If so, return TRUE indicating this is an overflow test and store into
> +   *NEW_CST an updated constant that can be used in a narrowed range test.
> +
> +   REVERSED indicates if the comparison was originally:
> +
> +   OP1 CODE' OP0.
> +
> +   This affects how we build the updated constant.  */
> +
> +static bool
> +overflow_comparison_p (enum tree_code code, tree op0, tree op1,
> +                      bool follow_assert_exprs, bool reversed, tree
> *new_cst)
> +{
> +  /* See if this is a relational operation between two SSA_NAMES with
> +     unsigned, overflow wrapping values.  If so, check it more deeply.  */
> +  if ((code == LT_EXPR || code == LE_EXPR
> +       || code == GE_EXPR || code == GT_EXPR)
> +      && TREE_CODE (op0) == SSA_NAME
> +      && TREE_CODE (op1) == SSA_NAME
> +      && INTEGRAL_TYPE_P (TREE_TYPE (op0))
> +      && TYPE_UNSIGNED (TREE_TYPE (op0))
> +      && TYPE_OVERFLOW_WRAPS (TREE_TYPE (op0)))
> +    {
> +      gimple *op1_def = SSA_NAME_DEF_STMT (op1);
> +
> +      /* If requested, follow any ASSERT_EXPRs backwards for OP1.  */
> +      if (follow_assert_exprs)
> +       {
> +         while (gimple_assign_single_p (op1_def)
> +                && TREE_CODE (gimple_assign_rhs1 (op1_def)) == ASSERT_EXPR)
> +           {
> +             op1 = TREE_OPERAND (gimple_assign_rhs1 (op1_def), 0);
> +             if (TREE_CODE (op1) != SSA_NAME)
> +               break;
> +             op1_def = SSA_NAME_DEF_STMT (op1);
> +           }
> +       }
> +
> +      /* Now look at the defining statement of OP1 to see if it adds
> +        or subtracts a nonzero constant from another operand.  */
> +      if (op1_def
> +         && is_gimple_assign (op1_def)
> +         && gimple_assign_rhs_code (op1_def) == PLUS_EXPR
> +         && TREE_CODE (gimple_assign_rhs2 (op1_def)) == INTEGER_CST
> +         && wi::ne_p (gimple_assign_rhs2 (op1_def), 0))

! integer_zerop ()

> +       {
> +         tree target = gimple_assign_rhs1 (op1_def);
> +
> +         /* If requested, follow ASSERT_EXPRs backwards for op0 looking
> +            for one where TARGET appears on the RHS.  */
> +         if (follow_assert_exprs)
> +           {
> +             /* Now see if that "other operand" is op0, following the chain
> +                of ASSERT_EXPRs if necessary.  */
> +             gimple *op0_def = SSA_NAME_DEF_STMT (op0);
> +             while (op0 != target
> +                    && gimple_assign_single_p (op0_def)
> +                    && TREE_CODE (gimple_assign_rhs1 (op0_def)) ==
> ASSERT_EXPR)
> +               {
> +                 op0 = TREE_OPERAND (gimple_assign_rhs1 (op0_def), 0);
> +                 if (TREE_CODE (op0) != SSA_NAME)
> +                   break;
> +                 op0_def = SSA_NAME_DEF_STMT (op0);
> +               }
> +           }
> +
> +         /* If we did not find our target SSA_NAME, then this is not
> +            an overflow test.  */
> +         if (op0 != target)
> +           return false;
> +
> +         tree type = TREE_TYPE (op0);
> +         wide_int max = wi::max_value (TYPE_PRECISION (type), UNSIGNED);
> +         HOST_WIDE_INT inc = TREE_INT_CST_LOW (gimple_assign_rhs2
> (op1_def));

You nowhere tested that rhs2 fits a HOST_WIDE_INT.  You can simply make inc
a tree and use that in the max + inc expression below.

I'll have to see where the function is used to make sense of it.

> +         if (reversed)
> +           *new_cst = wide_int_to_tree (type, max + inc);
> +         else
> +           *new_cst = wide_int_to_tree (type, max - inc);
> +         return true;
> +       }
> +    }
> +  return false;
> +}
> +
>  /* Try to register an edge assertion for SSA name NAME on edge E for
>     the condition COND contributing to the conditional jump pointed to by
> BSI.
>     Invert the condition COND if INVERT is true.  */
>

On 02/06/2017 05:52 AM, Richard Biener wrote:
>> +      /* Now look at the defining statement of OP1 to see if it adds
>> +        or subtracts a nonzero constant from another operand.  */
>> +      if (op1_def
>> +         && is_gimple_assign (op1_def)
>> +         && gimple_assign_rhs_code (op1_def) == PLUS_EXPR
>> +         && TREE_CODE (gimple_assign_rhs2 (op1_def)) == INTEGER_CST
>> +         && wi::ne_p (gimple_assign_rhs2 (op1_def), 0))
>
> ! integer_zerop ()
Fixed.

>> +
>> +         tree type = TREE_TYPE (op0);
>> +         wide_int max = wi::max_value (TYPE_PRECISION (type), UNSIGNED);
>> +         HOST_WIDE_INT inc = TREE_INT_CST_LOW (gimple_assign_rhs2
>> (op1_def));
>
> You nowhere tested that rhs2 fits a HOST_WIDE_INT.  You can simply make inc
> a tree and use that in the max + inc expression below.
Also fixed.

>
> I'll have to see where the function is used to make sense of it.
Understood.

jeff