[PATCH][RFA][PR tree-optimization/79095] Improve overflow test optimization and avoid invalid warnings

[Richard Biener]

On January 30, 2017 7:02:38 PM GMT+01:00, Jeff Law <law@redhat.com> wrote:
>On 01/30/2017 02:51 AM, Richard Biener wrote:
>> On Fri, Jan 27, 2017 at 11:21 PM, Jeff Law <law@redhat.com> wrote:
>>> On 01/27/2017 02:35 PM, Richard Biener wrote:
>>>>
>>>> On January 27, 2017 7:30:07 PM GMT+01:00, Jeff Law <law@redhat.com>
>wrote:
>>>>>
>>>>> On 01/27/2017 05:08 AM, Richard Biener wrote:
>>>>>>
>>>>>> On Fri, Jan 27, 2017 at 10:02 AM, Marc Glisse
><marc.glisse@inria.fr>
>>>>>
>>>>> wrote:
>>>>>>>
>>>>>>> On Thu, 26 Jan 2017, Jeff Law wrote:
>>>>>>>
>>>>>>>>> I assume this causes a regression for code like
>>>>>>>>>
>>>>>>>>> unsigned f(unsigned a){
>>>>>>>>>   unsigned b=a+1;
>>>>>>>>>   if(b<a)return 42;
>>>>>>>>>   return b;
>>>>>>>>> }
>>>>>>>>
>>>>>>>>
>>>>>>>> Yes.  The transformation ruins the conversion into ADD_OVERFLOW
>for
>>>>>
>>>>> the +-
>>>>>>>>
>>>>>>>> 1 case.  However, ISTM that we could potentially recover the
>>>>>
>>>>> ADD_OVERFLOW in
>>>>>>>>
>>>>>>>> phi-opt.  It's a very simple pattern that would be presented to
>>>>>
>>>>> phi-opt, so
>>>>>>>>
>>>>>>>> it might not be terrible to recover -- which has the advantage
>that
>>>>>
>>>>> if a
>>>>>>>>
>>>>>>>> user wrote an optimized overflow test we'd be able to recover
>>>>>
>>>>> ADD_OVERFLOW
>>>>>>>>
>>>>>>>> for it.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> phi-opt is a bit surprising at first glance because there can be
>>>>>
>>>>> overflow
>>>>>>>
>>>>>>> checking without condition/PHI, but if it is convenient to catch
>>>>>
>>>>> many
>>>>>>>
>>>>>>> cases...
>>>>>>
>>>>>>
>>>>>> Yeah, and it's still on my TODO to add some helpers exercising
>>>>>> match.pd COND_EXPR
>>>>>> patterns from PHI nodes and their controlling condition.
>>>>>
>>>>> It turns out to be better to fix the existing machinery to detect
>>>>> ADD_OVERFLOW in the transformed case than to add new detection to
>>>>> phi-opt.
>>>>>
>>>>> The problem with improving the detection of ADD_OVERFLOW is that
>the
>>>>> transformed test may allow the ADD/SUB to be sunk.  So by the time
>we
>>>>> run the pass to detect ADD_OVERFLOW, the test and arithmetic may
>be in
>>>>> different blocks -- ugh.
>>>>>
>>>>> The more I keep thinking about this the more I wonder if
>transforming
>>>>> the conditional is just more of a headache than its worth -- the
>main
>>>>> need here is to drive propagation of known constants into the
>THEN/ELSE
>>>>>
>>>>> clauses.  Transforming the conditional makes that easy for VRP &
>DOM to
>>>>>
>>>>> discover those constant and the transform is easy to write in
>match.pd.
>>>>>
>>>>> But we could just go back to discovering the case in VRP or DOM
>via
>>>>> open-coding detection, then propagating the known constants
>without
>>>>> transforming the conditional.
>>>>
>>>>
>>>> Indeed we can do that.  And in fact with named patterns in match.pd
>you
>>>> could even avoid the open-coding.
>>>
>>> negate_expr_p being the example?  That does look mighty
>interesting... After
>>> recognition we'd still have to extract the operands, but it does
>look like
>>> it might handle the detection part.
>>
>> Yes, the (match ..) stuff is actually exported in gimple-match.c
>(just
>> no declarations
>> are emitted to headers yet).  logical_inverted_value might be a
>better example
>> given it has an "output":
>>
>> (match (logical_inverted_value @0)
>>  (truth_not @0))
>>
>> bool
>> gimple_logical_inverted_value (tree t, tree *res_ops, tree
>> (*valueize)(tree) ATTRIBUTE_UNUSED)
>> {
>Thanks.  If I look at the generated code for this match:
>
>(for cmp (lt le ge gt)
>  (match (overflow_test @0 @1 @2)
>   (cmp:c (plus@2 @0 INTEGER_CST@1) @0)
>   (if (TYPE_UNSIGNED (TREE_TYPE (@0))
>        && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0))
>        && wi::ne_p (@1, 0)))))
>
>
>The generated code starts with...
>
>  switch (TREE_CODE (t))
>     {
>     case SSA_NAME:
>       if (do_valueize (valueize, t) != NULL_TREE)
>         {
>           gimple *def_stmt = SSA_NAME_DEF_STMT (t);
>           if (gassign *def = dyn_cast <gassign *> (def_stmt))
>             switch (gimple_assign_rhs_code (def))
>               {
>               case LT_EXPR:
>                 {
>
>So, it appears to want to match an SSA_NAME which is assigned from the 
>conditional.  So it's not all that helpful because the expression we 
>want to match shows up inside a GIMPLE_COND.  It also appears we'd have

Yeah...

>to build a tree to pass down to matching code.

A tree?  Not sure what you mean.

As this isn't used outside of match.PD yet it surely needs some work in genmatch like for the case where the expression to match has no SSA value.

Richard.

>
>Jeff