Re: [COMMITTED] Convert nonzero mask in irange to wide_int.

[Aldy Hernandez <aldyh@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 1035 bytes --]

On Wed, Oct 5, 2022 at 12:14 PM Aldy Hernandez <aldyh@redhat.com> wrote:

> However... I don't think I have the stomach to overhaul the allocators
> this late in the release.  For this release I may opt to put the
> nonzero mask back in a tree, but have it always be set.  The NULL ==
> -1 shortcut was very error prone.  The rest of my fixes in this patch
> still apply, as they keep better track of the masks, which we need.

Here is the patch reverting the nonzero mask to trees.

Unfortunately, having the mask always set caused a 10% regression in
VRP, so that's a no go.  I've gone back to keeping a NULL mask by
default that semantically means -1.  It's not as bad as I thought,
since the code is much cleaner now.  This is unfortunate, but a 10%
regression in VRP plus a 1.5% regression in overall compilation is
unacceptable.  On the plus side, this is temporary as we're moving
entirely to wide ints next release (with appropriate cache/allocator
changes).

I will commit after a final round of tests finishes.

Thanks.
Aldy

[-- Attachment #2: 0001-Convert-nonzero-mask-back-to-tree.patch --]
[-- Type: text/x-patch, Size: 9368 bytes --]

From 6b6e929b238ff91fee1f133e3ff7adceb3f75660 Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <aldyh@redhat.com>
Date: Fri, 7 Oct 2022 09:57:32 +0200
Subject: [PATCH] Convert nonzero mask back to tree.

Having nonzero masks always set had a performance penalty of 10% in
VRP, so mask==NULL is a shortcut to all bits set.

gcc/ChangeLog:

	* value-range.cc (irange::irange_set): Convert nonzero mask to
	tree.
	(irange::irange_set_anti_range): Same.
	(irange::set): Same.
	(irange::verify_range): Same.
	(irange::contains_p): Same.
	(irange::invert): Same.
	(irange::set_range_from_nonzero_bits): Same.
	(irange::set_nonzero_bits): Same.
	(mask_to_wi): Same.
	(irange::intersect_nonzero_bits): Same.
	(irange::union_nonzero_bits): Same.
	* value-range.h (irange::varying_compatible_p): Same.
	(gt_ggc_mx): Same.
	(gt_pch_nx): Same.
	(irange::set_undefined): Same.
	(irange::set_varying): Same.
---
 gcc/value-range.cc | 85 +++++++++++++++++++++++++++++++++++-----------
 gcc/value-range.h  | 19 ++++++-----
 2 files changed, 77 insertions(+), 27 deletions(-)

diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 87239fafa77..b4496ea9eea 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -935,7 +935,7 @@ irange::irange_set (tree min, tree max)
   m_base[1] = max;
   m_num_ranges = 1;
   m_kind = VR_RANGE;
-  m_nonzero_mask = wi::shwi (-1, TYPE_PRECISION (TREE_TYPE (min)));
+  m_nonzero_mask = NULL;
   normalize_kind ();
 
   if (flag_checking)
@@ -1009,7 +1009,7 @@ irange::irange_set_anti_range (tree min, tree max)
     }
 
   m_kind = VR_RANGE;
-  m_nonzero_mask = wi::shwi (-1, TYPE_PRECISION (TREE_TYPE (min)));
+  m_nonzero_mask = NULL;
   normalize_kind ();
 
   if (flag_checking)
@@ -1066,7 +1066,7 @@ irange::set (tree min, tree max, value_range_kind kind)
       m_base[0] = min;
       m_base[1] = max;
       m_num_ranges = 1;
-      m_nonzero_mask = wi::shwi (-1, TYPE_PRECISION (TREE_TYPE (min)));
+      m_nonzero_mask = NULL;
       return;
     }
 
@@ -1116,7 +1116,7 @@ irange::set (tree min, tree max, value_range_kind kind)
   m_base[0] = min;
   m_base[1] = max;
   m_num_ranges = 1;
-  m_nonzero_mask = wi::shwi (-1, TYPE_PRECISION (TREE_TYPE (min)));
+  m_nonzero_mask = NULL;
   normalize_kind ();
   if (flag_checking)
     verify_range ();
@@ -1135,7 +1135,8 @@ irange::verify_range ()
     }
   if (m_kind == VR_VARYING)
     {
-      gcc_checking_assert (m_nonzero_mask == -1);
+      gcc_checking_assert (!m_nonzero_mask
+			   || wi::to_wide (m_nonzero_mask) == -1);
       gcc_checking_assert (m_num_ranges == 1);
       gcc_checking_assert (varying_compatible_p ());
       return;
@@ -1409,10 +1410,10 @@ irange::contains_p (tree cst) const
   gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST);
 
   // See if we can exclude CST based on the nonzero bits.
-  if (m_nonzero_mask != -1)
+  if (m_nonzero_mask)
     {
       wide_int cstw = wi::to_wide (cst);
-      if (cstw != 0 && wi::bit_and (m_nonzero_mask, cstw) == 0)
+      if (cstw != 0 && wi::bit_and (wi::to_wide (m_nonzero_mask), cstw) == 0)
 	return false;
     }
 
@@ -2776,7 +2777,7 @@ irange::invert ()
   signop sign = TYPE_SIGN (ttype);
   wide_int type_min = wi::min_value (prec, sign);
   wide_int type_max = wi::max_value (prec, sign);
-  m_nonzero_mask = wi::shwi (-1, prec);
+  m_nonzero_mask = NULL;
   if (m_num_ranges == m_max_ranges
       && lower_bound () != type_min
       && upper_bound () != type_max)
@@ -2878,20 +2879,22 @@ bool
 irange::set_range_from_nonzero_bits ()
 {
   gcc_checking_assert (!undefined_p ());
-  unsigned popcount = wi::popcount (m_nonzero_mask);
+  if (!m_nonzero_mask)
+    return false;
+  unsigned popcount = wi::popcount (wi::to_wide (m_nonzero_mask));
 
   // If we have only one bit set in the mask, we can figure out the
   // range immediately.
   if (popcount == 1)
     {
       // Make sure we don't pessimize the range.
-      if (!contains_p (wide_int_to_tree (type (), m_nonzero_mask)))
+      if (!contains_p (m_nonzero_mask))
 	return false;
 
       bool has_zero = contains_p (build_zero_cst (type ()));
-      wide_int bits = m_nonzero_mask;
-      set (type (), bits, bits);
-      m_nonzero_mask = bits;
+      tree nz = m_nonzero_mask;
+      set (nz, nz);
+      m_nonzero_mask = nz;
       if (has_zero)
 	{
 	  int_range<2> zero;
@@ -2909,11 +2912,21 @@ irange::set_nonzero_bits (const wide_int_ref &bits)
   gcc_checking_assert (!undefined_p ());
   unsigned prec = TYPE_PRECISION (type ());
 
+  if (bits == -1)
+    {
+      m_nonzero_mask = NULL;
+      normalize_kind ();
+      if (flag_checking)
+	verify_range ();
+      return;
+    }
+
   // Drop VARYINGs with a nonzero mask to a plain range.
   if (m_kind == VR_VARYING && bits != -1)
     m_kind = VR_RANGE;
 
-  m_nonzero_mask = wide_int::from (bits, prec, TYPE_SIGN (type ()));
+  wide_int nz = wide_int::from (bits, prec, TYPE_SIGN (type ()));
+  m_nonzero_mask = wide_int_to_tree (type (), nz);
   if (set_range_from_nonzero_bits ())
     return;
 
@@ -2937,7 +2950,21 @@ irange::get_nonzero_bits () const
   // the mask precisely up to date at all times.  Instead, we default
   // to -1 and set it when explicitly requested.  However, this
   // function will always return the correct mask.
-  return m_nonzero_mask & get_nonzero_bits_from_range ();
+  if (m_nonzero_mask)
+    return wi::to_wide (m_nonzero_mask) & get_nonzero_bits_from_range ();
+  else
+    return get_nonzero_bits_from_range ();
+}
+
+// Convert tree mask to wide_int.  Returns -1 for NULL masks.
+
+inline wide_int
+mask_to_wi (tree mask, tree type)
+{
+  if (mask)
+    return wi::to_wide (mask);
+  else
+    return wi::shwi (-1, TYPE_PRECISION (type));
 }
 
 // Intersect the nonzero bits in R into THIS and normalize the range.
@@ -2948,10 +2975,20 @@ irange::intersect_nonzero_bits (const irange &r)
 {
   gcc_checking_assert (!undefined_p () && !r.undefined_p ());
 
+  if (!m_nonzero_mask && !r.m_nonzero_mask)
+    {
+      normalize_kind ();
+      if (flag_checking)
+	verify_range ();
+      return false;
+    }
+
   bool changed = false;
-  if (m_nonzero_mask != r.m_nonzero_mask)
+  tree t = type ();
+  if (mask_to_wi (m_nonzero_mask, t) != mask_to_wi (r.m_nonzero_mask, t))
     {
-      m_nonzero_mask = get_nonzero_bits () & r.get_nonzero_bits ();
+      wide_int nz = get_nonzero_bits () & r.get_nonzero_bits ();
+      m_nonzero_mask = wide_int_to_tree (t, nz);
       if (set_range_from_nonzero_bits ())
 	return true;
       changed = true;
@@ -2970,10 +3007,20 @@ irange::union_nonzero_bits (const irange &r)
 {
   gcc_checking_assert (!undefined_p () && !r.undefined_p ());
 
+  if (!m_nonzero_mask && !r.m_nonzero_mask)
+    {
+      normalize_kind ();
+      if (flag_checking)
+	verify_range ();
+      return false;
+    }
+
   bool changed = false;
-  if (m_nonzero_mask != r.m_nonzero_mask)
+  tree t = type ();
+  if (mask_to_wi (m_nonzero_mask, t) != mask_to_wi (r.m_nonzero_mask, t))
     {
-      m_nonzero_mask = get_nonzero_bits () | r.get_nonzero_bits ();
+      wide_int nz = get_nonzero_bits () | r.get_nonzero_bits ();
+      m_nonzero_mask = wide_int_to_tree (t, nz);
       // No need to call set_range_from_nonzero_bits, because we'll
       // never narrow the range.  Besides, it would cause endless
       // recursion because of the union_ in
diff --git a/gcc/value-range.h b/gcc/value-range.h
index b06ca7477cd..484f911bd90 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -215,7 +215,7 @@ private:
   bool intersect (const wide_int& lb, const wide_int& ub);
   unsigned char m_num_ranges;
   unsigned char m_max_ranges;
-  wide_int m_nonzero_mask;
+  tree m_nonzero_mask;
   tree *m_base;
 };
 
@@ -683,11 +683,11 @@ irange::varying_compatible_p () const
   if (INTEGRAL_TYPE_P (t))
     return (wi::to_wide (l) == wi::min_value (prec, sign)
 	    && wi::to_wide (u) == wi::max_value (prec, sign)
-	    && m_nonzero_mask == -1);
+	    && (!m_nonzero_mask || wi::to_wide (m_nonzero_mask) == -1));
   if (POINTER_TYPE_P (t))
     return (wi::to_wide (l) == 0
 	    && wi::to_wide (u) == wi::max_value (prec, sign)
-	    && m_nonzero_mask == -1);
+	    && (!m_nonzero_mask || wi::to_wide (m_nonzero_mask) == -1));
   return true;
 }
 
@@ -754,6 +754,8 @@ gt_ggc_mx (irange *x)
       gt_ggc_mx (x->m_base[i * 2]);
       gt_ggc_mx (x->m_base[i * 2 + 1]);
     }
+  if (x->m_nonzero_mask)
+    gt_ggc_mx (x->m_nonzero_mask);
 }
 
 inline void
@@ -764,6 +766,8 @@ gt_pch_nx (irange *x)
       gt_pch_nx (x->m_base[i * 2]);
       gt_pch_nx (x->m_base[i * 2 + 1]);
     }
+  if (x->m_nonzero_mask)
+    gt_pch_nx (x->m_nonzero_mask);
 }
 
 inline void
@@ -774,6 +778,8 @@ gt_pch_nx (irange *x, gt_pointer_operator op, void *cookie)
       op (&x->m_base[i * 2], NULL, cookie);
       op (&x->m_base[i * 2 + 1], NULL, cookie);
     }
+  if (x->m_nonzero_mask)
+    op (&x->m_nonzero_mask, NULL, cookie);
 }
 
 template<unsigned N>
@@ -868,6 +874,7 @@ irange::set_undefined ()
 {
   m_kind = VR_UNDEFINED;
   m_num_ranges = 0;
+  m_nonzero_mask = NULL;
 }
 
 inline void
@@ -875,11 +882,7 @@ irange::set_varying (tree type)
 {
   m_kind = VR_VARYING;
   m_num_ranges = 1;
-
-  if (type == error_mark_node)
-    m_nonzero_mask = wi::shwi (-1, 1);
-  else
-    m_nonzero_mask = wi::shwi (-1, TYPE_PRECISION (type));
+  m_nonzero_mask = NULL;
 
   if (INTEGRAL_TYPE_P (type))
     {
-- 
2.37.1