[gcc r13-1594] Cleanups to irange::nonzero bit code.

[Aldy Hernandez <aldyh@gcc.gnu.org>]

https://gcc.gnu.org/g:c106825b936446c346d49ef10952e40370753b9d

commit r13-1594-gc106825b936446c346d49ef10952e40370753b9d
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Sat Jul 9 17:43:47 2022 +0200

    Cleanups to irange::nonzero bit code.
    
    In discussions with Andrew we realized varying_p() was returning true
    for a range of the entire domain with a non-empty nonzero mask.  This
    is confusing as varying_p() should only return true when absolutely no
    information is available.  A nonzero mask that has any cleared bits is
    extra information and must return false for varying_p().  This patch
    fixes this oversight.  Now a range of the entire domain with nonzero
    bits, is internally set to VR_RANGE (with the appropriate end points
    set).  VR_VARYING ranges must have a null nonzero mask.
    
    Also, the union and intersect code were not quite right in the presence of
    nonzero masks.  Sometimes we would drop masks to -1 unnecessarily.  I
    was trying to be too smart in avoiding extra work when the mask was
    NULL, but there's also an implicit mask in the range that must be
    taken into account.  For example, [0,0] may have no nonzero bits set
    explicitly, but the mask is really 0x0.  This will all be simpler when
    we drop trees, because the nonzero bits will always be set, even if
    -1.
    
    Finally, I've added unit tests to the nonzero mask code.  This should
    help us maintain sanity going forward.
    
    There should be no visible changes, as the main consumer of this code
    is the SSA_NAME_RANGE_INFO patchset which has yet to be committed.
    
    Tested on x86-64 Linux.
    
    gcc/ChangeLog:
    
            * value-range.cc (irange::operator=): Call verify_range.
            (irange::irange_set): Normalize kind after everything else has
            been set.
            (irange::irange_set_anti_range): Same.
            (irange::set): Same.
            (irange::verify_range): Disallow nonzero masks for VARYING.
            (irange::irange_union): Call verify_range.
            Handle nonzero masks better.
            (irange::irange_intersect): Same.
            (irange::set_nonzero_bits): Calculate mask if either range has an
            explicit mask.
            (irange::intersect_nonzero_bits): Same.
            (irange::union_nonzero_bits): Same.
            (range_tests_nonzero_bits): New.
            (range_tests): Call range_tests_nonzero_bits.
            * value-range.h (class irange): Remove set_nonzero_bits method
            with trees.
            (irange::varying_compatible_p): Set nonzero mask.

Diff:
---
 gcc/value-range.cc | 167 +++++++++++++++++++++++++++++++++++++++++------------
 gcc/value-range.h  |   5 +-
 2 files changed, 133 insertions(+), 39 deletions(-)

diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index fd549b9ca59..a02fab47fc4 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -275,6 +275,8 @@ irange::operator= (const irange &src)
   m_num_ranges = lim;
   m_kind = src.m_kind;
   m_nonzero_mask = src.m_nonzero_mask;
+  if (flag_checking)
+    verify_range ();
   return *this;
 }
 
@@ -393,8 +395,8 @@ irange::irange_set (tree min, tree max)
   m_base[1] = max;
   m_num_ranges = 1;
   m_kind = VR_RANGE;
-  normalize_kind ();
   m_nonzero_mask = NULL;
+  normalize_kind ();
 
   if (flag_checking)
     verify_range ();
@@ -467,8 +469,8 @@ irange::irange_set_anti_range (tree min, tree max)
     }
 
   m_kind = VR_RANGE;
-  normalize_kind ();
   m_nonzero_mask = NULL;
+  normalize_kind ();
 
   if (flag_checking)
     verify_range ();
@@ -577,8 +579,8 @@ irange::set (tree min, tree max, value_range_kind kind)
   m_base[0] = min;
   m_base[1] = max;
   m_num_ranges = 1;
-  normalize_kind ();
   m_nonzero_mask = NULL;
+  normalize_kind ();
   if (flag_checking)
     verify_range ();
 }
@@ -599,6 +601,7 @@ irange::verify_range ()
     gcc_checking_assert (wi::to_wide (m_nonzero_mask) != -1);
   if (m_kind == VR_VARYING)
     {
+      gcc_checking_assert (!m_nonzero_mask);
       gcc_checking_assert (m_num_ranges == 1);
       gcc_checking_assert (varying_compatible_p ());
       return;
@@ -1759,6 +1762,8 @@ irange::legacy_verbose_intersect (const irange *other)
 
 // Perform an efficient union with R when both ranges have only a single pair.
 // Excluded are VARYING and UNDEFINED ranges.
+//
+// NOTE: It is the caller's responsibility to set the nonzero mask.
 
 bool
 irange::irange_single_pair_union (const irange &r)
@@ -1831,23 +1836,28 @@ irange::irange_union (const irange &r)
   if (undefined_p ())
     {
       operator= (r);
+      if (flag_checking)
+	verify_range ();
       return true;
     }
 
-  // Save the nonzero mask in case the set operations below clobber it.
-  bool ret_nz = union_nonzero_bits (r);
-  tree saved_nz = m_nonzero_mask;
-
   if (varying_p ())
-    return ret_nz;
+    return false;
 
   if (r.varying_p ())
     {
-      set_varying (r.type ());
-      set_nonzero_bits (saved_nz);
+      set_varying (type ());
       return true;
     }
 
+  // Save the nonzero mask in case the set operations below clobber it.
+  bool ret_nz = union_nonzero_bits (r);
+  tree saved_nz = m_nonzero_mask;
+
+  // The union_nonzero_bits may have turned things into a varying.
+  if (varying_p ())
+    return true;
+
   // Special case one range union one range.
   if (m_num_ranges == 1 && r.m_num_ranges == 1)
     {
@@ -1948,8 +1958,8 @@ irange::irange_union (const irange &r)
   m_num_ranges = i / 2;
 
   m_kind = VR_RANGE;
+  m_nonzero_mask = saved_nz;
   normalize_kind ();
-  set_nonzero_bits (saved_nz);
 
   if (flag_checking)
     verify_range ();
@@ -2029,13 +2039,19 @@ irange::irange_intersect (const irange &r)
   if (varying_p ())
     {
       operator= (r);
-      set_nonzero_bits (saved_nz);
+      if (saved_nz)
+	set_nonzero_bits (saved_nz);
+      if (flag_checking)
+	verify_range ();
       return true;
     }
 
   if (r.num_pairs () == 1)
     {
       bool res = intersect (r.lower_bound (), r.upper_bound ());
+      if (undefined_p ())
+	return true;
+
       set_nonzero_bits (saved_nz);
       return res || saved_nz;
     }
@@ -2113,9 +2129,9 @@ irange::irange_intersect (const irange &r)
   m_num_ranges = bld_pair;
 
   m_kind = VR_RANGE;
-  normalize_kind ();
   if (!undefined_p ())
-    set_nonzero_bits (saved_nz);
+    m_nonzero_mask = saved_nz;
+  normalize_kind ();
 
   if (flag_checking)
     verify_range ();
@@ -2331,6 +2347,30 @@ irange::invert ()
     verify_range ();
 }
 
+void
+irange::set_nonzero_bits (tree mask)
+{
+  gcc_checking_assert (!undefined_p ());
+
+  if (!mask)
+    {
+      if (m_nonzero_mask)
+	{
+	  m_nonzero_mask = NULL;
+	  // Clearing the mask may have turned a range into VARYING.
+	  normalize_kind ();
+	}
+      return;
+    }
+  m_nonzero_mask = mask;
+  // Setting the mask may have turned a VARYING into a range.
+  if (m_kind == VR_VARYING)
+    m_kind = VR_RANGE;
+
+  if (flag_checking)
+    verify_range ();
+}
+
 void
 irange::set_nonzero_bits (const wide_int_ref &bits)
 {
@@ -2338,10 +2378,10 @@ irange::set_nonzero_bits (const wide_int_ref &bits)
 
   if (bits == -1)
     {
-      m_nonzero_mask = NULL;
+      set_nonzero_bits (NULL);
       return;
     }
-  m_nonzero_mask = wide_int_to_tree (type (), bits);
+  set_nonzero_bits (wide_int_to_tree (type (), bits));
 }
 
 wide_int
@@ -2378,17 +2418,14 @@ irange::intersect_nonzero_bits (const irange &r)
 {
   gcc_checking_assert (!undefined_p () && !r.undefined_p ());
 
-  if (!r.m_nonzero_mask)
-    return false;
-  if (!m_nonzero_mask)
+  if (m_nonzero_mask || r.m_nonzero_mask)
     {
-      m_nonzero_mask = r.m_nonzero_mask;
+      wide_int nz = wi::bit_and (get_nonzero_bits (),
+				 r.get_nonzero_bits ());
+      set_nonzero_bits (nz);
       return true;
     }
-  wide_int i = wi::bit_and (wi::to_wide (m_nonzero_mask),
-			    wi::to_wide (r.m_nonzero_mask));
-  set_nonzero_bits (i);
-  return true;
+  return false;
 }
 
 // Union the nonzero bits in R into THIS.
@@ -2398,21 +2435,14 @@ irange::union_nonzero_bits (const irange &r)
 {
   gcc_checking_assert (!undefined_p () && !r.undefined_p ());
 
-  if (!m_nonzero_mask)
-    return false;
-  if (!r.m_nonzero_mask)
+  if (m_nonzero_mask || r.m_nonzero_mask)
     {
-      if (m_nonzero_mask)
-	{
-	  m_nonzero_mask = NULL;
-	  return true;
-	}
-      return false;
+      wide_int nz = wi::bit_or (get_nonzero_bits (),
+				r.get_nonzero_bits ());
+      set_nonzero_bits (nz);
+      return true;
     }
-  wide_int i = wi::bit_or (wi::to_wide (m_nonzero_mask),
-			   wi::to_wide (r.m_nonzero_mask));
-  set_nonzero_bits (i);
-  return true;
+  return false;
 }
 
 static void
@@ -3054,6 +3084,68 @@ range_tests_misc ()
   ASSERT_TRUE (r0.contains_p (UINT (2)));
 }
 
+static void
+range_tests_nonzero_bits ()
+{
+  int_range<2> r0, r1;
+
+  // Adding nonzero bits to a varying drops the varying.
+  r0.set_varying (integer_type_node);
+  r0.set_nonzero_bits (255);
+  ASSERT_TRUE (!r0.varying_p ());
+  // Dropping the nonzero bits brings us back to varying.
+  r0.set_nonzero_bits (-1);
+  ASSERT_TRUE (r0.varying_p ());
+
+  // Test contains_p with nonzero bits.
+  r0.set_zero (integer_type_node);
+  ASSERT_TRUE (r0.contains_p (INT (0)));
+  ASSERT_FALSE (r0.contains_p (INT (1)));
+  r0.set_nonzero_bits (0xfe);
+  ASSERT_FALSE (r0.contains_p (INT (0x100)));
+  ASSERT_FALSE (r0.contains_p (INT (0x3)));
+
+  // Union of nonzero bits.
+  r0.set_varying (integer_type_node);
+  r0.set_nonzero_bits (0xf0);
+  r1.set_varying (integer_type_node);
+  r1.set_nonzero_bits (0xf);
+  r0.union_ (r1);
+  ASSERT_TRUE (r0.get_nonzero_bits () == 0xff);
+
+  // Union where the mask of nonzero bits is implicit from the range.
+  r0.set_varying (integer_type_node);
+  r0.set_nonzero_bits (0xf00);
+  r1.set_zero (integer_type_node); // nonzero mask is implicitly 0
+  r0.union_ (r1);
+  ASSERT_TRUE (r0.get_nonzero_bits () == 0xf00);
+
+  // Intersect of nonzero bits.
+  r0.set (INT (0), INT (255));
+  r0.set_nonzero_bits (0xfe);
+  r1.set_varying (integer_type_node);
+  r1.set_nonzero_bits (0xf0);
+  r0.intersect (r1);
+  ASSERT_TRUE (r0.get_nonzero_bits () == 0xf0);
+
+  // Intersect where the mask of nonzero bits is implicit from the range.
+  r0.set_varying (integer_type_node);
+  r1.set (INT (0), INT (255));
+  r0.intersect (r1);
+  ASSERT_TRUE (r0.get_nonzero_bits () == 0xff);
+
+  // The union of a mask of 0xff..ffff00 with a mask of 0xff spans the
+  // entire domain, and makes the range a varying.
+  r0.set_varying (integer_type_node);
+  wide_int x = wi::shwi (0xff, TYPE_PRECISION (integer_type_node));
+  x = wi::bit_not (x);
+  r0.set_nonzero_bits (x); 	// 0xff..ff00
+  r1.set_varying (integer_type_node);
+  r1.set_nonzero_bits (0xff);
+  r0.union_ (r1);
+  ASSERT_TRUE (r0.varying_p ());
+}
+
 void
 range_tests ()
 {
@@ -3061,6 +3153,7 @@ range_tests ()
   range_tests_irange3 ();
   range_tests_int_range_max ();
   range_tests_strict_enum ();
+  range_tests_nonzero_bits ();
   range_tests_misc ();
 }
 
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 2e48d92d189..0e341185f69 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -201,7 +201,7 @@ private:
 
   void irange_set_1bit_anti_range (tree, tree);
   bool varying_compatible_p () const;
-  void set_nonzero_bits (tree bits) { m_nonzero_mask = bits; }
+  void set_nonzero_bits (tree mask);
   bool intersect_nonzero_bits (const irange &r);
   bool union_nonzero_bits (const irange &r);
   void dump_bitmasks (FILE *) const;
@@ -555,7 +555,8 @@ irange::varying_compatible_p () const
   signop sign = TYPE_SIGN (t);
   if (INTEGRAL_TYPE_P (t))
     return (wi::to_wide (l) == wi::min_value (prec, sign)
-	    && wi::to_wide (u) == wi::max_value (prec, sign));
+	    && wi::to_wide (u) == wi::max_value (prec, sign)
+	    && !m_nonzero_mask);
   if (POINTER_TYPE_P (t))
     return (wi::to_wide (l) == 0
 	    && wi::to_wide (u) == wi::max_value (prec, sign));