VRP: undefined shifting calculation should not need sign bit
diff mbox series

Message ID 1ab7411f-d602-5aa6-4b4a-02c066d693a3@redhat.com
State New
Headers show
Series
  • VRP: undefined shifting calculation should not need sign bit
Related show

Commit Message

Aldy Hernandez Sept. 11, 2018, 10:09 a.m. UTC
We can calculate wide_int_range_shift_undefined_p() without having to 
pass down the sign bit of the operand.  Also, vrp_shift_undefined_p is a 
brain dead wrapper so I'm removing it.

OK for trunk?

Comments

Jeff Law Sept. 11, 2018, 10:59 p.m. UTC | #1
On 9/11/18 4:09 AM, Aldy Hernandez wrote:
> We can calculate wide_int_range_shift_undefined_p() without having to
> pass down the sign bit of the operand.  Also, vrp_shift_undefined_p is a
> brain dead wrapper so I'm removing it.
> 
> OK for trunk?
> 
> curr.patch
> 
> commit 9aeb62d4c33b50bc007b07ec5097e8f3edd4b31b
> Author: Aldy Hernandez <aldyh@redhat.com>
> Date:   Mon Sep 10 17:46:10 2018 +0200
> 
>             * tree-vrp.c (vrp_shift_undefined_p): Remove.
>             (extract_range_from_binary_expr_1: Call
>             wide_int_range_shift_undefined_p instead of vrp_shift_undefined_p.
>             * wide-int-range.h (wide_int_range_shift_undefined_p): Do not
>             depend on sign.
OK
jeff
Richard Sandiford Sept. 12, 2018, 4:57 p.m. UTC | #2
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.

Thanks,
Richard
Aldy Hernandez Sept. 12, 2018, 5:39 p.m. UTC | #3
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?

Aldy
Richard Sandiford Sept. 13, 2018, 7:33 a.m. UTC | #4
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
Aldy Hernandez Sept. 13, 2018, 2 p.m. UTC | #5
On 09/13/2018 03: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.
Heh heh.  Academical or not, it seems like finding these UINT256 bugs in 
the future will be harder than me passing the correct inner sign now.

My tree is a mess right now, but I'll submit a fix next week reverting 
the inner sign discrepancy, while keeping the bits that remove the 
vrp_shift_undefined_p wrapper.

Thank you for your explanation.
Aldy
Aldy Hernandez Oct. 17, 2018, 10:17 a.m. UTC | #6
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.

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)
 {
   /* ?? Note: The original comment said this only applied to
@@ -142,7 +142,7 @@ wide_int_range_shift_undefined_p (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::sign_mask (min) || wi::ge_p (max, prec, UNSIGNED);
+  return wi::lt_p (min, 0, sign) || wi::ge_p (max, prec, sign);
 }
 
 /* Calculate MIN/MAX_EXPR of two ranges and store the result in [MIN, MAX].  */
Richard Sandiford Oct. 17, 2018, 10:52 a.m. UTC | #7
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
Aldy Hernandez Oct. 17, 2018, 12:32 p.m. UTC | #8
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

Patch
diff mbox series

commit 9aeb62d4c33b50bc007b07ec5097e8f3edd4b31b
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Mon Sep 10 17:46:10 2018 +0200

            * tree-vrp.c (vrp_shift_undefined_p): Remove.
            (extract_range_from_binary_expr_1: Call
            wide_int_range_shift_undefined_p instead of vrp_shift_undefined_p.
            * wide-int-range.h (wide_int_range_shift_undefined_p): Do not
            depend on sign.

diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 653e45b50a4..1adb919a6df 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -1018,17 +1018,6 @@  extract_range_into_wide_ints (const value_range *vr,
     }
 }
 
-/* Value range wrapper for wide_int_range_shift_undefined_p.  */
-
-static inline bool
-vrp_shift_undefined_p (const value_range &shifter, unsigned prec)
-{
-  tree type = TREE_TYPE (shifter.min);
-  return wide_int_range_shift_undefined_p (TYPE_SIGN (type), prec,
-					   wi::to_wide (shifter.min),
-					   wi::to_wide (shifter.max));
-}
-
 /* Value range wrapper for wide_int_range_multiplicative_op:
 
      *VR = *VR0 .CODE. *VR1.  */
@@ -1565,7 +1554,9 @@  extract_range_from_binary_expr_1 (value_range *vr,
 	   || code == LSHIFT_EXPR)
     {
       if (range_int_cst_p (&vr1)
-	  && !vrp_shift_undefined_p (vr1, prec))
+	  && !wide_int_range_shift_undefined_p (prec,
+						wi::to_wide (vr1.min),
+						wi::to_wide (vr1.max)))
 	{
 	  if (code == RSHIFT_EXPR)
 	    {
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);
 }
 
 /* Calculate MIN/MAX_EXPR of two ranges and store the result in [MIN, MAX].  */