commit f3204ce1ae6b97f7e79d633844d61d021da8502e
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.
@@ -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;
@@ -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.
@@ -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