[RFA,PR,tree-optimization/79095,3/4] Improve ASSERT_EXPRs and simplification of overflow tests

This is the actual optimization piece of the patchseries and uses the 
overflow test detection function in patch #2.

First, when we detect an overflow test, we register additional 
ASSERT_EXPRs for the given name.  So instead of an ASSERT_EXPR for an 
expression like A < B, we get an assert like A > 0xfffffffe  or A <= 0.

Additionally, during propagation and folding, if we are presented with 
an overflow test which collapses into an equality test, we will simplify 
the test into an equality check (without changing the IL).   So A + 1 < 
A would turn into A == -1  or A + 1 > A turns into A != -1.  There's a 
corresponding equivalent for A - 1 < A and A - 1 > A.

The net result is the new ASSERT_EXPRs and simplified tests allow VRP to 
eliminate more paths through the CFG and improve its constant 
propagation capabilities.  Examples can be found in the next patch which 
has the tests.

Bootstrapped and regression tested with the other patches in this 
series.  OK for the trunk?
* tree-vrp.c (register_edge_assert_for_2): Register additional asserts
	fif NAME is used in an overflow test.
	(vrp_evaluate_conditional_warnv_with_ops): If the ops represent an
	overflow check that can be expressed as an equality test, then adjust
	ops to be that equality test.

On Sat, Feb 4, 2017 at 3:52 PM, Jeff Law <law@redhat.com> wrote:
>
> This is the actual optimization piece of the patchseries and uses the
> overflow test detection function in patch #2.
>
> First, when we detect an overflow test, we register additional ASSERT_EXPRs
> for the given name.  So instead of an ASSERT_EXPR for an expression like A <
> B, we get an assert like A > 0xfffffffe  or A <= 0.
>
> Additionally, during propagation and folding, if we are presented with an
> overflow test which collapses into an equality test, we will simplify the
> test into an equality check (without changing the IL).   So A + 1 < A would
> turn into A == -1  or A + 1 > A turns into A != -1.  There's a corresponding
> equivalent for A - 1 < A and A - 1 > A.
>
> The net result is the new ASSERT_EXPRs and simplified tests allow VRP to
> eliminate more paths through the CFG and improve its constant propagation
> capabilities.  Examples can be found in the next patch which has the tests.
>
> Bootstrapped and regression tested with the other patches in this series.
> OK for the trunk?
>
>         * tree-vrp.c (register_edge_assert_for_2): Register additional
> asserts
>         fif NAME is used in an overflow test.
>         (vrp_evaluate_conditional_warnv_with_ops): If the ops represent an
>         overflow check that can be expressed as an equality test, then
> adjust
>         ops to be that equality test.
>
>
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index 6459c71..8d78646 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -5299,7 +5298,19 @@ register_edge_assert_for_2 (tree name, edge e,
> gimple_stmt_iterator bsi,
>    /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
>       reachable from E.  */
>    if (live_on_edge (e, name))
> -    register_new_assert_for (name, name, comp_code, val, NULL, e, bsi);
> +    {
> +      tree x;
> +      if (overflow_comparison_p (comp_code, name, val, false, false, &x)
> +         || overflow_comparison_p (swap_tree_comparison (comp_code), val,
> name,
> +                                                         false, true, &x))
> +       {
> +         enum tree_code new_code
> +           = ((comp_code == GT_EXPR || comp_code == GE_EXPR)
> +              ? GT_EXPR : LE_EXPR);
> +         register_new_assert_for (name, name, new_code, x, NULL, e, bsi);
> +       }
> +      register_new_assert_for (name, name, comp_code, val, NULL, e, bsi);
> +    }
>
>    /* In the case of NAME <= CST and NAME being defined as
>       NAME = (unsigned) NAME2 + CST2 we can assert NAME2 >= -CST2
> @@ -7658,6 +7669,60 @@ vrp_evaluate_conditional_warnv_with_ops (enum
> tree_code code, tree op0,
>        && !POINTER_TYPE_P (TREE_TYPE (op0)))
>      return NULL_TREE;
>
> +  /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
> +     as a simple equality test, then prefer that over its current form
> +     for evaluation.
> +
> +     An overflow test which collapses to an equality test can always be
> +     expressed as a comparison of one argument against zero.  Overflow
> +     occurs when the chosen argument is zero and does not occur if the
> +     chosen argument is not zero.  */
> +  tree x;
> +  if (overflow_comparison_p (code, op0, op1, use_equiv_p, false, &x))

This somehow feels like a hack so I'd add a comment why we do not change
the IL in the first place.

Feeding overflow_comparison_p the original and the swapped comparison
looks like it makes it more expensive given its stmt walking?  I'd see whether
returning a second output from it (whether we matched op0 or op1) would
simplify callers.

Richard.

> +    {
> +      wide_int max = wi::max_value (TYPE_PRECISION (TREE_TYPE (op0)),
> UNSIGNED);
> +      /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
> +         B = A - 1; if (A > B) -> B = A - 1; if (A != 0) */
> +      if (integer_zerop (x))
> +       {
> +         op1 = x;
> +         code = (code == LT_EXPR || code == LE_EXPR) ? EQ_EXPR : NE_EXPR;
> +       }
> +      /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0)
> +         B = A + 1; if (A < B) -> B = A + 1; if (B != 0) */
> +      else if (wi::eq_p (x, max - 1))
> +       {
> +         op0 = op1;
> +         op1 = wide_int_to_tree (TREE_TYPE (op0), 0);
> +         code = (code == GT_EXPR || code == GE_EXPR) ? EQ_EXPR : NE_EXPR;
> +       }
> +    }
> +  else if (overflow_comparison_p (swap_tree_comparison (code),
> +                                 op1, op0, use_equiv_p, true, &x))
> +    {
> +      /* X holds the value if we wanted to generate an overflow check
> +        for the comparison using OP1.  But we're actually going to
> +        test against OP0 and we're always going to use an equality
> +        test, so the constants for detection below are different
> +        than the constant we pass into vrp_evaluate_... */
> +      wide_int max = wi::max_value (TYPE_PRECISION (TREE_TYPE (op0)),
> UNSIGNED);
> +      /* B = A - 1; if (B > A) -> B = A - 1; if (A == 0)
> +         B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */
> +      if (wi::eq_p (x, max - 1))
> +       {
> +         op0 = op1;
> +         op1 = wide_int_to_tree (TREE_TYPE (op0), 0);
> +         code = (code == GT_EXPR || code == GE_EXPR) ? EQ_EXPR : NE_EXPR;
> +       }
> +      /* B = A + 1; if (B < A) -> B = A + 1; if (B == 0)
> +         B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */
> +      else if (integer_zerop (x))
> +       {
> +         op1 = x;
> +         code = (code == LT_EXPR || code == LE_EXPR) ? EQ_EXPR : NE_EXPR;
> +       }
> +    }
> +
>    if ((ret = vrp_evaluate_conditional_warnv_with_ops_using_ranges
>                (code, op0, op1, strict_overflow_p)))
>      return ret;
>

On 02/06/2017 06:06 AM, Richard Biener wrote:
>>
>> +  /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
>> +     as a simple equality test, then prefer that over its current form
>> +     for evaluation.
>> +
>> +     An overflow test which collapses to an equality test can always be
>> +     expressed as a comparison of one argument against zero.  Overflow
>> +     occurs when the chosen argument is zero and does not occur if the
>> +     chosen argument is not zero.  */
>> +  tree x;
>> +  if (overflow_comparison_p (code, op0, op1, use_equiv_p, false, &x))
>
> This somehow feels like a hack so I'd add a comment why we do not change
> the IL in the first place.
It doesn't feel like a hack to me.  It's just discovering alternate 
ranges/forms for a class of comparisons that are sometimes more useful 
than the cananoical form we have in the IL (which promotes 
{ADD,SUB}_OVERFLOW detection).

Regardless, a comment WRT why we don't transform the IL sounds quite 
reasonable.;

>
> Feeding overflow_comparison_p the original and the swapped comparison
> looks like it makes it more expensive given its stmt walking?
No.  In both cases we have to walk one or both chains to see if we have 
a statement like X +- CST.  Then and only then we walk the other chain 
to see if it is X.

Identification of X in the other chain can happen at the start of the 
chain, end of the chain or somewhere in the middle (and I've seen all 
three happen in practice).


If we knew we were going to fully walk both chains, then the answer 
would be that we should walk them once to the end, then do detection 
both ways on the result of fully walking both chains.

  I'd see whether
> returning a second output from it (whether we matched op0 or op1) would
> simplify callers.
I think it could slightly.  Let me play with that.

jeff