[COMMITTED] Faster irange union for appending ranges.

[COMMITTED] Faster irange union for appending ranges.

[Andrew MacLeod]

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

Its a common idiom to build a range by unioning other ranges into 
another one.  If this is done sequentially, those new ranges can be 
simply appended to the end of the existing range, avoiding some 
expensive processing fro the general case.

This patch identifies and optimizes this situation.  The result is a 
2.1% speedup in VRP and a 0.8% speedup in threading, with a overall 
compile time improvement of 0.14% across the GCC build.

Bootstrapped on  x86_64-pc-linux-gnu with no regressions. Pushed.

Andrew

[-- Attachment #2: 0001 --]
[-- Type: text/plain, Size: 3096 bytes --]

commit f7dbf6230453c76a19921607601eff968bb70169
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 --git a/gcc/value-range.cc b/gcc/value-range.cc
index f507ec57536..fcf53efa1dd 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 c00b15194c4..e9d81d22cd0 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;