Re: Fix VR_ANTI_RANGE handling in intersect_range_with_nonzero_bits (PR 84321)

2018-02-13 Thread Jeff Law 
On 02/13/2018 08:26 AM, Richard Biener wrote:
> On Mon, Feb 12, 2018 at 4:29 PM, Richard Sandiford
>  wrote:
>> VR_ANTI_RANGE is basically a union of two ranges, and although
>> intersect_range_with_nonzero_bits had code to deal with the upper
>> one being empty, it didn't handle the lower one being empty.
>> There were also some off-by-one errors.
>>
>> This patch rewrites the code in a hopefully clearer way.
>>
>> Tested on aarch64-linux-gnu and x86_64-linux-gnu.  OK to install?
> 
> Ok.
And committed.

jeff

Re: Fix VR_ANTI_RANGE handling in intersect_range_with_nonzero_bits (PR 84321)

2018-02-13 Thread Richard Biener 
On Mon, Feb 12, 2018 at 4:29 PM, Richard Sandiford
 wrote:
> VR_ANTI_RANGE is basically a union of two ranges, and although
> intersect_range_with_nonzero_bits had code to deal with the upper
> one being empty, it didn't handle the lower one being empty.
> There were also some off-by-one errors.
>
> This patch rewrites the code in a hopefully clearer way.
>
> Tested on aarch64-linux-gnu and x86_64-linux-gnu.  OK to install?

Ok.

Richard.

> Richard
>
>
> 2018-02-12  Richard Sandiford  
>
> gcc/
> PR tree-optimization/84321
> * tree-vrp.c (intersect_range_with_nonzero_bits): Fix VR_ANTI_RANGE
> handling.  Also check whether the anti-range contains any values
> that satisfy the mask; switch to a VR_RANGE if not.
>
> gcc/testsuite/
> PR tree-optimization/84321
> * gcc.dg/pr84321.c: New test.
>
> Index: gcc/tree-vrp.c
> ===
> *** gcc/tree-vrp.c  2018-02-08 15:16:21.784407397 +
> --- gcc/tree-vrp.c  2018-02-12 15:26:13.703500747 +
> *** intersect_range_with_nonzero_bits (enum
> *** 184,220 
>const wide_int _bits,
>signop sgn)
>   {
> !   if (vr_type == VR_RANGE)
>   {
> !   *max = wi::round_down_for_mask (*max, nonzero_bits);
>
> !   /* Check that the range contains at least one valid value.  */
> !   if (wi::gt_p (*min, *max, sgn))
> !   return VR_UNDEFINED;
>
> !   *min = wi::round_up_for_mask (*min, nonzero_bits);
> !   gcc_checking_assert (wi::le_p (*min, *max, sgn));
> ! }
> !   if (vr_type == VR_ANTI_RANGE)
> ! {
> !   *max = wi::round_up_for_mask (*max, nonzero_bits);
>
> !   /* If the calculation wrapped, we now have a VR_RANGE whose
> !lower bound is *MAX and whose upper bound is *MIN.  */
> !   if (wi::gt_p (*min, *max, sgn))
> {
> ! std::swap (*min, *max);
> ! *max = wi::round_down_for_mask (*max, nonzero_bits);
>   gcc_checking_assert (wi::le_p (*min, *max, sgn));
>   return VR_RANGE;
> }
>
> !   *min = wi::round_down_for_mask (*min, nonzero_bits);
> gcc_checking_assert (wi::le_p (*min, *max, sgn));
>
> !   /* Check whether we now have an empty set of values.  */
> !   if (*min - 1 == *max)
> return VR_UNDEFINED;
>   }
> return vr_type;
>   }
> --- 184,244 
>const wide_int _bits,
>signop sgn)
>   {
> !   if (vr_type == VR_ANTI_RANGE)
>   {
> !   /* The VR_ANTI_RANGE is equivalent to the union of the ranges
> !A: [-INF, *MIN) and B: (*MAX, +INF].  First use NONZERO_BITS
> !to create an inclusive upper bound for A and an inclusive lower
> !bound for B.  */
> !   wide_int a_max = wi::round_down_for_mask (*min - 1, nonzero_bits);
> !   wide_int b_min = wi::round_up_for_mask (*max + 1, nonzero_bits);
>
> !   /* If the calculation of A_MAX wrapped, A is effectively empty
> !and A_MAX is the highest value that satisfies NONZERO_BITS.
> !Likewise if the calculation of B_MIN wrapped, B is effectively
> !empty and B_MIN is the lowest value that satisfies NONZERO_BITS.  */
> !   bool a_empty = wi::ge_p (a_max, *min, sgn);
> !   bool b_empty = wi::le_p (b_min, *max, sgn);
>
> !   /* If both A and B are empty, there are no valid values.  */
> !   if (a_empty && b_empty)
> !   return VR_UNDEFINED;
>
> !   /* If exactly one of A or B is empty, return a VR_RANGE for the
> !other one.  */
> !   if (a_empty || b_empty)
> {
> ! *min = b_min;
> ! *max = a_max;
>   gcc_checking_assert (wi::le_p (*min, *max, sgn));
>   return VR_RANGE;
> }
>
> !   /* Update the VR_ANTI_RANGE bounds.  */
> !   *min = a_max + 1;
> !   *max = b_min - 1;
> gcc_checking_assert (wi::le_p (*min, *max, sgn));
>
> !   /* Now check whether the excluded range includes any values that
> !satisfy NONZERO_BITS.  If not, switch to a full VR_RANGE.  */
> !   if (wi::round_up_for_mask (*min, nonzero_bits) == b_min)
> !   {
> ! unsigned int precision = min->get_precision ();
> ! *min = wi::min_value (precision, sgn);
> ! *max = wi::max_value (precision, sgn);
> ! vr_type = VR_RANGE;
> !   }
> ! }
> !   if (vr_type == VR_RANGE)
> ! {
> !   *max = wi::round_down_for_mask (*max, nonzero_bits);
> !
> !   /* Check that the range contains at least one valid value.  */
> !   if (wi::gt_p (*min, *max, sgn))
> return VR_UNDEFINED;
> +
> +   *min = wi::round_up_for_mask (*min, nonzero_bits);
> +   gcc_checking_assert (wi::le_p (*min, *max, sgn));
>   }
> return vr_type;
>   }
> Index:

Fix VR_ANTI_RANGE handling in intersect_range_with_nonzero_bits (PR 84321)

2018-02-12 Thread Richard Sandiford 
VR_ANTI_RANGE is basically a union of two ranges, and although
intersect_range_with_nonzero_bits had code to deal with the upper
one being empty, it didn't handle the lower one being empty.
There were also some off-by-one errors.

This patch rewrites the code in a hopefully clearer way.

Tested on aarch64-linux-gnu and x86_64-linux-gnu.  OK to install?

Richard


2018-02-12  Richard Sandiford  

gcc/
PR tree-optimization/84321
* tree-vrp.c (intersect_range_with_nonzero_bits): Fix VR_ANTI_RANGE
handling.  Also check whether the anti-range contains any values
that satisfy the mask; switch to a VR_RANGE if not.

gcc/testsuite/
PR tree-optimization/84321
* gcc.dg/pr84321.c: New test.

Index: gcc/tree-vrp.c
===
*** gcc/tree-vrp.c  2018-02-08 15:16:21.784407397 +
--- gcc/tree-vrp.c  2018-02-12 15:26:13.703500747 +
*** intersect_range_with_nonzero_bits (enum
*** 184,220 
   const wide_int _bits,
   signop sgn)
  {
!   if (vr_type == VR_RANGE)
  {
!   *max = wi::round_down_for_mask (*max, nonzero_bits);
  
!   /* Check that the range contains at least one valid value.  */
!   if (wi::gt_p (*min, *max, sgn))
!   return VR_UNDEFINED;
  
!   *min = wi::round_up_for_mask (*min, nonzero_bits);
!   gcc_checking_assert (wi::le_p (*min, *max, sgn));
! }
!   if (vr_type == VR_ANTI_RANGE)
! {
!   *max = wi::round_up_for_mask (*max, nonzero_bits);
  
!   /* If the calculation wrapped, we now have a VR_RANGE whose
!lower bound is *MAX and whose upper bound is *MIN.  */
!   if (wi::gt_p (*min, *max, sgn))
{
! std::swap (*min, *max);
! *max = wi::round_down_for_mask (*max, nonzero_bits);
  gcc_checking_assert (wi::le_p (*min, *max, sgn));
  return VR_RANGE;
}
  
!   *min = wi::round_down_for_mask (*min, nonzero_bits);
gcc_checking_assert (wi::le_p (*min, *max, sgn));
  
!   /* Check whether we now have an empty set of values.  */
!   if (*min - 1 == *max)
return VR_UNDEFINED;
  }
return vr_type;
  }
--- 184,244 
   const wide_int _bits,
   signop sgn)
  {
!   if (vr_type == VR_ANTI_RANGE)
  {
!   /* The VR_ANTI_RANGE is equivalent to the union of the ranges
!A: [-INF, *MIN) and B: (*MAX, +INF].  First use NONZERO_BITS
!to create an inclusive upper bound for A and an inclusive lower
!bound for B.  */
!   wide_int a_max = wi::round_down_for_mask (*min - 1, nonzero_bits);
!   wide_int b_min = wi::round_up_for_mask (*max + 1, nonzero_bits);
  
!   /* If the calculation of A_MAX wrapped, A is effectively empty
!and A_MAX is the highest value that satisfies NONZERO_BITS.
!Likewise if the calculation of B_MIN wrapped, B is effectively
!empty and B_MIN is the lowest value that satisfies NONZERO_BITS.  */
!   bool a_empty = wi::ge_p (a_max, *min, sgn);
!   bool b_empty = wi::le_p (b_min, *max, sgn);
  
!   /* If both A and B are empty, there are no valid values.  */
!   if (a_empty && b_empty)
!   return VR_UNDEFINED;
  
!   /* If exactly one of A or B is empty, return a VR_RANGE for the
!other one.  */
!   if (a_empty || b_empty)
{
! *min = b_min;
! *max = a_max;
  gcc_checking_assert (wi::le_p (*min, *max, sgn));
  return VR_RANGE;
}
  
!   /* Update the VR_ANTI_RANGE bounds.  */
!   *min = a_max + 1;
!   *max = b_min - 1;
gcc_checking_assert (wi::le_p (*min, *max, sgn));
  
!   /* Now check whether the excluded range includes any values that
!satisfy NONZERO_BITS.  If not, switch to a full VR_RANGE.  */
!   if (wi::round_up_for_mask (*min, nonzero_bits) == b_min)
!   {
! unsigned int precision = min->get_precision ();
! *min = wi::min_value (precision, sgn);
! *max = wi::max_value (precision, sgn);
! vr_type = VR_RANGE;
!   }
! }
!   if (vr_type == VR_RANGE)
! {
!   *max = wi::round_down_for_mask (*max, nonzero_bits);
! 
!   /* Check that the range contains at least one valid value.  */
!   if (wi::gt_p (*min, *max, sgn))
return VR_UNDEFINED;
+ 
+   *min = wi::round_up_for_mask (*min, nonzero_bits);
+   gcc_checking_assert (wi::le_p (*min, *max, sgn));
  }
return vr_type;
  }
Index: gcc/testsuite/gcc.dg/pr84321.c
===
*** /dev/null   2018-02-10 09:05:46.714416790 +
--- gcc/testsuite/gcc.dg/pr84321.c  2018-02-12 15:26:13.702500788 +
***
*** 0 
--- 1,16 
+ /* { dg-do compile } */
+ /* { dg-options "-O3 -fwrapv" } */
+ 
+ int c;
+ 
+ void