VRP: undefined shifting calculation should not need sign bit

[Aldy Hernandez]

On 10/17/18 6:52 AM, Richard Sandiford wrote:
> Aldy Hernandez <aldyh@redhat.com> writes:
>> On 9/13/18 3:33 AM, Richard Sandiford wrote:
>>> Aldy Hernandez <aldyh@redhat.com> writes:
>>>> On 09/12/2018 12:57 PM, Richard Sandiford wrote:
>>>>> Aldy Hernandez <aldyh@redhat.com> writes:
>>>>>> diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h
>>>>>> index 589fdea4df6..e9ee418e5b2 100644
>>>>>> --- a/gcc/wide-int-range.h
>>>>>> +++ b/gcc/wide-int-range.h
>>>>>> @@ -131,7 +131,7 @@ extern bool wide_int_range_div (wide_int &wmin, wide_int &wmax,
>>>>>>     /* Return TRUE if shifting by range [MIN, MAX] is undefined behavior.  */
>>>>>>     
>>>>>>     inline bool
>>>>>> -wide_int_range_shift_undefined_p (signop sign, unsigned prec,
>>>>>> +wide_int_range_shift_undefined_p (unsigned prec,
>>>>>>     				  const wide_int &min, const wide_int &max)
>>>>>>     {
>>>>>>       /* ?? Note: The original comment said this only applied to
>>>>>> @@ -142,7 +142,7 @@ wide_int_range_shift_undefined_p (signop sign, unsigned prec,
>>>>>>          behavior from the shift operation.  We cannot even trust
>>>>>>          SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
>>>>>>          shifts, and the operation at the tree level may be widened.  */
>>>>>> -  return wi::lt_p (min, 0, sign) || wi::ge_p (max, prec, sign);
>>>>>> +  return wi::sign_mask (min) || wi::ge_p (max, prec, UNSIGNED);
>>>>>
>>>>> I don't think this is a good idea.  Logically the comparison should
>>>>> be done relative to the TYPE_SIGN of the type, so I think the original
>>>>> code was correct.
>>>>
>>>> The operation to calculate undefinedness must be done with the type of
>>>> the RHS, as opposed to the type of the entire operation.  This can be
>>>> confusing, as most operations use the same type for all operands as well
>>>> as for the type of the entire operation.  For example, AFAICT, the
>>>> following is valid gimple:
>>>>
>>>> 	UINT64 = UINT64 << INT32
>>>>
>>>> The original code was doing this (correctly), but since it was confusing
>>>> to remember which type to pass, I rewrote the above function to not need
>>>> the sign of the RHS.  This came about because in my ranger work, I
>>>> passed the wrong type which took forever to find ;-).  My patch avoids
>>>> further confusion.
>>>>
>>>> Am I missing a subtle incorrectness in my approach?
>>>
>>> The problem is with things like UINT256 << UINT8 vs. UINT256 << INT8.
>>> A range of [128, 131] on the UINT8 would be represented using the same
>>> wide_ints as a range of [-128, -125] on the INT8, but the former is
>>> well-defined while the latter isn't.  Only the TYPE_SIGN tells you
>>> which applies.
>>>
>>> The original code got this right, but the new code effectively assumes
>>> all shift amounts are signed, and so would treat UINT8 like INT8.
>>>
>>> OK, so no current target actually supports UINT256 AFAIK, so it might
>>> be academic.  But the original point of wide-int.h was to support such
>>> wide types, so they could become a thing in future.
>>>
>>> Thanks,
>>> Richard
>>>
>>
>> As promised.  Here is the reversal of the bits you suggested.
> 
> Thanks!
> 
>> I think this is an obvious patch, but would appreciate a sanity peek.
>>
>> Aldy
>>
>> commit 38a335af9aa5d72778fbacba247ab2219672da7b
>> Author: Aldy Hernandez <aldyh@redhat.com>
>> Date:   Wed Oct 17 11:25:21 2018 +0200
>>
>>              * wide-int-range.h (wide_int_range_shift_undefined_p): Adjust to
>>              use sign as argument.
>>              * tree-vrp.c (extract_range_from_binary_expr_1): Pass sign to
>>              wide_int_range_shift_undefined_p.
>>
>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>> index cbc2ea2f26b..c519613bb28 100644
>> --- a/gcc/tree-vrp.c
>> +++ b/gcc/tree-vrp.c
>> @@ -1521,7 +1521,8 @@ extract_range_from_binary_expr_1 (value_range *vr,
>>   	   || code == LSHIFT_EXPR)
>>       {
>>         if (range_int_cst_p (&vr1)
>> -	  && !wide_int_range_shift_undefined_p (prec,
>> +	  && !wide_int_range_shift_undefined_p (TYPE_SIGN (TREE_TYPE (vr1.min)),
>> +						prec,
>>   						wi::to_wide (vr1.min),
>>   						wi::to_wide (vr1.max)))
>>   	{
>> diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h
>> index e9ee418e5b2..589fdea4df6 100644
>> --- a/gcc/wide-int-range.h
>> +++ b/gcc/wide-int-range.h
>> @@ -131,7 +131,7 @@ extern bool wide_int_range_div (wide_int &wmin, wide_int &wmax,
>>   /* Return TRUE if shifting by range [MIN, MAX] is undefined behavior.  */
>>   
>>   inline bool
>> -wide_int_range_shift_undefined_p (unsigned prec,
>> +wide_int_range_shift_undefined_p (signop sign, unsigned prec,
>>   				  const wide_int &min, const wide_int &max)
> 
> Need to add SIGN back to the comment, maybe something like:
> 
>    /* Return TRUE if shifting by range [MIN, MAX] is undefined behavior,
>       interpreting MIN and MAX according to SIGN.  */
> 
> (or whatever you think's best).

Done.

Committed.

Thanks.
Aldy