[gcc r14-4927] Faster irange union for appending ranges.

[gcc r14-4927] Faster irange union for appending ranges.

[Andrew Macleod]

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

commit r14-4927-gf7dbf6230453c76a19921607601eff968bb70169
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Mon Oct 23 14:52:45 2023 -0400

    Faster irange union for appending ranges.
    
    A common pattern to to append a range to an existing range via union.
    This optimizes that process.
    
            * value-range.cc (irange::union_append): New.
            (irange::union_): Call union_append when appropriate.
            * value-range.h (irange::union_append): New prototype.

Diff:
---
 gcc/value-range.cc | 45 ++++++++++++++++++++++++++++++++++++++++++++-
 gcc/value-range.h  |  1 +
 2 files changed, 45 insertions(+), 1 deletion(-)

diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index f507ec57536b..fcf53efa1dd6 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -1291,6 +1291,45 @@ irange::irange_single_pair_union (const irange &r)
   return true;
 }
 
+// Append R to this range, knowing that R occurs after all of these subranges.
+// Return TRUE as something must have changed.
+
+bool
+irange::union_append (const irange &r)
+{
+  // Check if the first range in R is an immmediate successor to the last
+  // range, ths requiring a merge.
+  signop sign = TYPE_SIGN (m_type);
+  wide_int lb = r.lower_bound ();
+  wide_int ub = upper_bound ();
+  unsigned start = 0;
+  if (widest_int::from (ub, sign) + 1
+      == widest_int::from (lb, sign))
+    {
+      m_base[m_num_ranges * 2 - 1] = r.m_base[1];
+      start = 1;
+    }
+  maybe_resize (m_num_ranges + r.m_num_ranges - start);
+  for ( ; start < r.m_num_ranges; start++)
+    {
+      // Merge the last ranges if it exceeds the maximum size.
+      if (m_num_ranges + 1 > m_max_ranges)
+	{
+	  m_base[m_max_ranges * 2 - 1] = r.m_base[r.m_num_ranges * 2 - 1];
+	  break;
+	}
+      m_base[m_num_ranges * 2] = r.m_base[start * 2];
+      m_base[m_num_ranges * 2 + 1] = r.m_base[start * 2 + 1];
+      m_num_ranges++;
+    }
+
+  if (!union_bitmask (r))
+    normalize_kind ();
+  if (flag_checking)
+    verify_range ();
+  return true;
+}
+
 // Return TRUE if anything changes.
 
 bool
@@ -1322,6 +1361,11 @@ irange::union_ (const vrange &v)
   if (m_num_ranges == 1 && r.m_num_ranges == 1)
     return irange_single_pair_union (r);
 
+  signop sign = TYPE_SIGN (m_type);
+  // Check for an append to the end.
+  if (m_kind == VR_RANGE && wi::gt_p (r.lower_bound (), upper_bound (), sign))
+    return union_append (r);
+
   // If this ranges fully contains R, then we need do nothing.
   if (irange_contains_p (r))
     return union_bitmask (r);
@@ -1340,7 +1384,6 @@ irange::union_ (const vrange &v)
   // [Xi,Yi]..[Xn,Yn]  U  [Xj,Yj]..[Xm,Ym]   -->  [Xk,Yk]..[Xp,Yp]
   auto_vec<wide_int, 20> res (m_num_ranges * 2 + r.m_num_ranges * 2);
   unsigned i = 0, j = 0, k = 0;
-  signop sign = TYPE_SIGN (m_type);
 
   while (i < m_num_ranges * 2 && j < r.m_num_ranges * 2)
     {
diff --git a/gcc/value-range.h b/gcc/value-range.h
index c00b15194c41..e9d81d22cd08 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -339,6 +339,7 @@ private:
   bool set_range_from_bitmask ();
 
   bool intersect (const wide_int& lb, const wide_int& ub);
+  bool union_append (const irange &r);
   unsigned char m_num_ranges;
   bool m_resizable;
   unsigned char m_max_ranges;