@@ -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)
{
@@ -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;
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 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.