[gcc r13-442] Return a bool result for union, and add performance improvements.

[gcc r13-442] Return a bool result for union, and add performance improvements.

[Andrew Macleod]

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

commit r13-442-gf3204ce1ae6b97f7e79d633844d61d021da8502e
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Mon May 9 13:32:31 2022 -0400

    Return a bool result for union, and add performance improvements.
    
    Union_ returns a boolean indicating if the operation changes the range.
    Also optimize the common single-pair UNION single-pair case.
    
            * gimple-range-edge.cc (calc_switch_ranges): Check union return value.
            * value-range.cc (irange::legacy_verbose_union_): Add return value.
            (irange::irange_single_pair_union): New.
            (irange::irange_union): Add return value.
            * value-range.h (class irange): Adjust prototypes.

Diff:
---
 gcc/gimple-range-edge.cc |  4 ++-
 gcc/value-range.cc       | 93 +++++++++++++++++++++++++++++++++++++++++++-----
 gcc/value-range.h        | 12 ++++---
 3 files changed, 94 insertions(+), 15 deletions(-)

diff --git a/gcc/gimple-range-edge.cc b/gcc/gimple-range-edge.cc
index 6caa07c8f02..0bee38ba770 100644
--- a/gcc/gimple-range-edge.cc
+++ b/gcc/gimple-range-edge.cc
@@ -154,7 +154,9 @@ gimple_outgoing_range::calc_switch_ranges (gswitch *sw)
       irange *&slot = m_edge_table->get_or_insert (e, &existed);
       if (existed)
 	{
-	  case_range.union_ (*slot);
+	  // If this doesn't change the value, move on.
+	  if (!case_range.union_ (*slot))
+	   continue;
 	  if (slot->fits_p (case_range))
 	    {
 	      *slot = case_range;
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 190d7fb6f22..2e7385aecc2 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -1439,9 +1439,10 @@ irange::legacy_union (irange *vr0, const irange *vr1)
 
 /* Meet operation for value ranges.  Given two value ranges VR0 and
    VR1, store in VR0 a range that contains both VR0 and VR1.  This
-   may not be the smallest possible such range.  */
+   may not be the smallest possible such range.
+   Return TRUE if the original value changes.  */
 
-void
+bool
 irange::legacy_verbose_union_ (const irange *other)
 {
   if (legacy_mode_p ())
@@ -1450,7 +1451,7 @@ irange::legacy_verbose_union_ (const irange *other)
 	{
 	  int_range<1> tmp = *other;
 	  legacy_union (this, &tmp);
-	  return;
+	  return true;
 	}
       if (dump_file && (dump_flags & TDF_DETAILS))
 	{
@@ -1469,16 +1470,16 @@ irange::legacy_verbose_union_ (const irange *other)
 	  dump_value_range (dump_file, this);
 	  fprintf (dump_file, "\n");
 	}
-      return;
+      return true;
     }
 
   if (other->legacy_mode_p ())
     {
       int_range<2> wider = *other;
-      irange_union (wider);
+      return irange_union (wider);
     }
   else
-    irange_union (*other);
+    return irange_union (*other);
 }
 
 bool
@@ -1522,22 +1523,95 @@ irange::legacy_verbose_intersect (const irange *other)
     return irange_intersect (*other);
 }
 
+// Perform an efficient union with R when both ranges have only a single pair.
+// Excluded are VARYING and UNDEFINED ranges.
+
+bool
+irange::irange_single_pair_union (const irange &r)
+{
+  gcc_checking_assert (!undefined_p () && !varying_p ());
+  gcc_checking_assert (!r.undefined_p () && !varying_p ());
+
+  signop sign = TYPE_SIGN (TREE_TYPE (m_base[0]));
+  // Check if current lower bound is also the new lower bound.
+  if (wi::le_p (wi::to_wide (m_base[0]), wi::to_wide (r.m_base[0]), sign))
+    {
+      // If current upper bound is new upper bound, we're done.
+      if (wi::le_p (wi::to_wide (r.m_base[1]), wi::to_wide (m_base[1]), sign))
+	return false;
+      // Otherwise R has the new upper bound.
+      // Check for overlap/touching ranges, or single target range.
+      if (m_max_ranges == 1
+	  || wi::to_widest (m_base[1]) + 1 >= wi::to_widest (r.m_base[0]))
+	{
+	  m_base[1] = r.m_base[1];
+	  if (varying_compatible_p ())
+	    m_kind = VR_VARYING;
+	}
+      else
+	{
+	  // This is a dual range result.
+	  m_base[2] = r.m_base[0];
+	  m_base[3] = r.m_base[1];
+	  m_num_ranges = 2;
+	}
+      if (flag_checking)
+	verify_range ();
+      return true;
+    }
+
+  // Set the new lower bound to R's lower bound.
+  tree lb = m_base[0];
+  m_base[0] = r.m_base[0];
+
+  // If R fully contains THIS range, just set the upper bound.
+  if (wi::ge_p (wi::to_wide (r.m_base[1]), wi::to_wide (m_base[1]), sign))
+    m_base[1] = r.m_base[1];
+  // Check for overlapping ranges, or target limited to a single range.
+  else if (m_max_ranges == 1
+	   || wi::to_widest (r.m_base[1]) + 1 >= wi::to_widest (lb))
+    {
+      // This has the new upper bound, just check for varying.
+      if (varying_compatible_p ())
+	  m_kind = VR_VARYING;
+    }
+  else
+    {
+      // Left with 2 pairs.
+      m_num_ranges = 2;
+      m_base[2] = lb;
+      m_base[3] = m_base[1];
+      m_base[1] = r.m_base[1];
+    }
+  if (flag_checking)
+    verify_range ();
+  return true;
+}
+
 // union_ for multi-ranges.
 
-void
+bool
 irange::irange_union (const irange &r)
 {
   gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ());
 
   if (r.undefined_p () || varying_p ())
-    return;
+    return false;
 
   if (undefined_p () || r.varying_p ())
     {
       operator= (r);
-      return;
+      return true;
     }
 
+  // Special case one range union one range.
+  if (m_num_ranges == 1 && r.m_num_ranges == 1)
+    return irange_single_pair_union (r);
+
+  // If this ranges fully contains R, then we need do nothing.
+  if (irange_contains_p (r))
+    return false;
+
   // Do not worry about merging and such by reserving twice as many
   // pairs as needed, and then simply sort the 2 ranges into this
   // intermediate form.
@@ -1628,6 +1702,7 @@ irange::irange_union (const irange &r)
 
   if (flag_checking)
     verify_range ();
+  return true;
 }
 
 // Return TRUE if THIS fully contains R.  No undefined or varying cases.
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 419860247fc..ec59d2e4f23 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -71,7 +71,7 @@ public:
   bool contains_p (tree) const;
 
   // In-place operators.
-  void union_ (const irange &);
+  bool union_ (const irange &);
   bool intersect (const irange &);
   void invert ();
 
@@ -96,7 +96,7 @@ public:
   bool may_contain_p (tree) const;		// DEPRECATED
   void set (tree);				// DEPRECATED
   bool equal_p (const irange &) const;		// DEPRECATED
-  void legacy_verbose_union_ (const class irange *);	// DEPRECATED
+  bool legacy_verbose_union_ (const class irange *);	// DEPRECATED
   bool legacy_verbose_intersect (const irange *);	// DEPRECATED
 
 protected:
@@ -107,11 +107,12 @@ protected:
   tree tree_upper_bound () const;
 
    // In-place operators.
-  void irange_union (const irange &);
+  bool irange_union (const irange &);
   bool irange_intersect (const irange &);
   void irange_set (tree, tree);
   void irange_set_anti_range (tree, tree);
   bool irange_contains_p (const irange &) const;
+  bool irange_single_pair_union (const irange &r);
 
   void normalize_kind ();
 
@@ -545,13 +546,14 @@ irange::upper_bound () const
   return upper_bound (pairs - 1);
 }
 
-inline void
+inline bool
 irange::union_ (const irange &r)
 {
   dump_flags_t m_flags = dump_flags;
   dump_flags &= ~TDF_DETAILS;
-  irange::legacy_verbose_union_ (&r);
+  bool ret = irange::legacy_verbose_union_ (&r);
   dump_flags = m_flags;
+  return ret;
 }
 
 inline bool