Fix VR_ANTI_RANGE handling in intersect_range_with_nonzero_bits (PR 84321)

[Richard Sandiford <richard dot sandiford at linaro dot org>]

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  <richard.sandiford@linaro.org>

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 +0000
--- gcc/tree-vrp.c	2018-02-12 15:26:13.703500747 +0000
*************** intersect_range_with_nonzero_bits (enum
*** 184,220 ****
  				   const wide_int &nonzero_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 &nonzero_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 +0000
--- gcc/testsuite/gcc.dg/pr84321.c	2018-02-12 15:26:13.702500788 +0000
***************
*** 0 ****
--- 1,16 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O3 -fwrapv" } */
+ 
+ int c;
+ 
+ void
+ foo (int *a, int b)
+ {
+   int e;
+   if (b == 1)
+     return;
+   for (e = 0; e < (b & ~7); e += 8)
+     ;
+   for (++e; e < b;)
+     c = a[e];
+ }