[PATCH] Look through widening type conversions for possible edge assertions

[Patrick Palka]

On Mon, Nov 17, 2014 at 5:32 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Sun, Nov 16, 2014 at 3:40 PM, Patrick Palka <patrick@parcs.ath.cx> wrote:
>> On Sun, Nov 16, 2014 at 8:52 AM, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>> On November 16, 2014 5:22:26 AM CET, Patrick Palka <patrick@parcs.ath.cx> wrote:
>>>>On Wed, Nov 12, 2014 at 3:38 AM, Richard Biener
>>>><richard.guenther@gmail.com> wrote:
>>>>> On Wed, Nov 12, 2014 at 5:17 AM, Patrick Palka <patrick@parcs.ath.cx>
>>>>wrote:
>>>>>> On Tue, Nov 11, 2014 at 8:48 AM, Richard Biener
>>>>>> <richard.guenther@gmail.com> wrote:
>>>>>>> On Tue, Nov 11, 2014 at 1:10 PM, Patrick Palka
>>>><patrick@parcs.ath.cx> wrote:
>>>>>>>> This patch is a replacement for the 2nd VRP refactoring patch.  It
>>>>>>>> simply teaches VRP to look through widening type conversions when
>>>>>>>> finding suitable edge assertions, e.g.
>>>>>>>>
>>>>>>>> bool p = x != y;
>>>>>>>> int q = (int) p;
>>>>>>>> if (q == 0) // new edge assert: p == 0 and therefore x == y
>>>>>>>
>>>>>>> I think the proper fix is to forward x != y to q == 0 instead of
>>>>this one.
>>>>>>> That said - the tree-ssa-forwprop.c restriction on only forwarding
>>>>>>> single-uses into conditions is clearly bogus here.  I suggest to
>>>>>>> relax it for conversions and compares.  Like with
>>>>>>>
>>>>>>> Index: tree-ssa-forwprop.c
>>>>>>> ===================================================================
>>>>>>> --- tree-ssa-forwprop.c (revision 217349)
>>>>>>> +++ tree-ssa-forwprop.c (working copy)
>>>>>>> @@ -476,7 +476,7 @@ forward_propagate_into_comparison_1 (gim
>>>>>>>         {
>>>>>>>           rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
>>>>>>>           tmp = combine_cond_expr_cond (stmt, code, type,
>>>>>>> -                                       rhs0, op1, !single_use0_p);
>>>>>>> +                                       rhs0, op1, false);
>>>>>>>           if (tmp)
>>>>>>>             return tmp;
>>>>>>>         }
>>>>>>>
>>>>>>>
>>>>>>> Thanks,
>>>>>>> Richard.
>>>>>>
>>>>>> That makes sense.  Attached is what I have so far.  I relaxed the
>>>>>> forwprop restriction in the case of comparing an integer constant
>>>>with
>>>>>> a comparison or with a conversion from a boolean value.  (If I allow
>>>>>> all conversions, not just those from a boolean value, then a couple
>>>>of
>>>>>> -Wstrict-overflow faillures trigger..)  Does the change look
>>>>sensible?
>>>>>>  Should the logic be duplicated for the case when TREE_CODE (op1) ==
>>>>>> SSA_NAME? Thanks for your help so far!
>>>>>
>>>>> It looks good though I'd have allowed all kinds of conversions, not
>>>>only
>>>>> those from booleans.
>>>>>
>>>>> If the patch tests ok with that change it is ok.
>>>>
>>>>Sadly changing the patch to propagate all kinds of conversions, not
>>>>only just those from booleans, introduces regressions that I don't
>>>>know how to adequately fix.
>>>
>>> OK.  The original patch propagating only bool conversions is ok then.  Can you list the failures you have seen when propagating more?
>>>
>>> Thanks,
>>> Richard.
>>>
>>
>> gcc.dg/Wstrict-overflow-26.c: the patch introduces a bogus overflow
>> warning here.  I was able to fix this one by not warning on equality
>> comparisons, but fixing it caused ...
>> gcc.dg/Wstrict-overflow-18.c: ... this to regress.  I was able to this
>> one too, by teaching VRP to emit an overflow warning when simplifying
>> non-equality comparisons to equality comparisons (in this case i > 0
>> --> i != 0) when the operand has the range [0, +INF(OVF)].
>
> Can you push these changes?  ISTR I hit those at some point in
> match-and-simplify development as well..

Okay.

>
>> g++.dg/calloc.C: this regression I wasn't able to fix.  One problem is
>> that VRP is no longer able to simplify the "m * 4 > 0" comparison in
>> the following testcase:
>>
>> void
>> f (int n)
>> {
>>   size_t m = n;
>>   if (m > (size_t)-1 / 4)
>>     abort ();
>>   if (n != 0) // used to be m != 0 before the patch
>>     {
>>       ...
>>       if (m * 4 > 0)
>>         ..
>>     }
>> }
>>
>> This happens because VRP has no way of knowing that if n != 0 then m
>> != 0.  I hacked up a fix for this deficiency in VRP by looking at an
>> operand's def stmts when adding edge assertions, so that for the
>> conditional "n != 0" we will also insert the edge assertion "m != 0".
>> But still calloc.C regressed, most notably in the slsr pass where the
>> pass was unable to combine two ssa names which had equivalent
>> definitions. At that point I gave up.
>
> Aww, yeah.  g++.dg/calloc.C is very fragile.
>
>> I also played around with folding "m > (size_t)-1 / 4" to "n < 0" in
>> the hopes that a subsequent pass would move the definition for m
>> closer to its use (assuming such a pass exists) so that m will see n's
>> ASSERT_EXPRs in m's def chain.  But that didn't work too well because
>> apparently such a pass doesn't exist.
>
> That pass would be tree-ssa-sink.c, but it only runs once after PRE.
> I'll try to remember your analysis above ;)

So such a pass does exist! Good to know.

>
> Thanks,
> Richard.