Re: VRP: undefined shifting calculation should not need sign bit

[Richard Sandiford <richard dot sandiford at arm dot com>]

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).

OK otherwise, thanks.

Richard