Implement frange::set_pairs(), a function that takes an array of
sub-ranges, sorts them, fuses those that overlap, while capping the
result to MAX_PAIRS, and then installs these as the frange's
sub-ranges.
Preliminary stats show that 2 subranges cover 99.6% of all ranges
needed, so we don't bend over backwards to this super efficiently like
we do for irange. We're unlikely to ever need more than 2 subranges.
MAX_PAIRS is still 1, so set_pairs only ever installs a single
interval for now.
No changes to functionality until we flip the switch.
Tested on ppc64le: regstrap, LAPACK, no assembly accross a corpus of
Fortran files, etc.
Pushed.
gcc/ChangeLog:
* value-range.h (class frange): Declare set_pairs. Document the
sub-range representation and that the no-argument bounds are the
convex hull.
* value-range.cc (frange_fusible_p): New.
(frange::set_pairs): New.
(frange::flush_denormals_to_zero): Reinstall the endpoints through
set_pairs.
(frange::normalize_kind): Note a range with a gap is never varying.
(frange::verify_range): Check the sub-range invariants.
---
gcc/value-range.cc | 101 ++++++++++++++++++++++++++++++++++++++++-----
gcc/value-range.h | 1 +
2 files changed, 92 insertions(+), 10 deletions(-)
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 09381e62602..ac8096746e3 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -1013,6 +1013,22 @@ frange_cmp (const REAL_VALUE_TYPE &a, const
REAL_VALUE_TYPE &b)
return 0;
}
+// Return TRUE if [..., A_MAX] and [B_MIN, ...] can be fused into one interval,
+// either because they overlap or because no representable value exists between
+// them. The latter is how -0.0 and +0.0 abut: there is nothing in between, so
+// [x, -0.0] U [+0.0, y] is really [x, y].
+
+static bool
+frange_fusible_p (machine_mode mode, const REAL_VALUE_TYPE &a_max,
+ const REAL_VALUE_TYPE &b_min)
+{
+ if (frange_cmp (b_min, a_max) <= 0)
+ return true;
+ REAL_VALUE_TYPE next = a_max;
+ frange_nextafter (mode, next, dconstinf);
+ return frange_cmp (b_min, next) <= 0;
+}
+
// Flush denormal endpoints to the appropriate 0.0.
void
@@ -1022,23 +1038,29 @@ frange::flush_denormals_to_zero ()
return;
machine_mode mode = TYPE_MODE (type ());
+ frange_pair pairs[MAX_PAIRS];
+ unsigned n = m_num_ranges;
- // FIXME: Rewrite for sub-ranges.
// Flush a denormal endpoint to a zero of the same sign: a +denormal lower
- // bound to +0.0, and a -denormal upper bound to -0.0. Then call
- // canonicalize_zeros to rewrite the sign to whatever the flags make
+ // bound to +0.0, and a -denormal upper bound to -0.0. Then set_pairs, via
+ // canonicalize_zeros, rewrites the sign to whatever the flags make
// canonical. For example, under !HONOR_SIGNED_ZEROS (-fno-signed-zeros) a
// range reaching zero must hold both signs of it, so:
//
// [ +DENORMAL, 5.0 ] flushes to [ -0.0, 5.0 ]
//
- // keeping contains_p (-0.0) true; under HONOR_SIGNED_ZEROS the sign stands
and
- // it stays [ +0.0, 5.0 ].
- if (real_isdenormal (&m_pairs[0].max, mode) && real_isneg (&m_pairs[0].max))
- m_pairs[0].max = dconstm0;
- if (real_isdenormal (&m_pairs[0].min, mode) && !real_isneg (&m_pairs[0].min))
- m_pairs[0].min = dconst0;
- canonicalize_zeros (m_pairs[0]);
+ // keeping contains_p (-0.0) true; under HONOR_SIGNED_ZEROS the sign stands
+ // and it stays [ +0.0, 5.0 ].
+ for (unsigned i = 0; i < n; ++i)
+ {
+ pairs[i] = m_pairs[i];
+ if (real_isdenormal (&pairs[i].max, mode) && real_isneg (&pairs[i].max))
+ pairs[i].max = dconstm0;
+ if (real_isdenormal (&pairs[i].min, mode) && !real_isneg (&pairs[i].min))
+ pairs[i].min = dconst0;
+ }
+
+ set_pairs (pairs, n);
}
// Canonicalize the signed zeros of a sub-range according with what the target
@@ -1070,6 +1092,58 @@ frange::canonicalize_zeros (frange_pair &p)
}
}
+// Sort, fuse and install the N intervals in PAIRS as this range's sub-ranges.
+//
+// Fusing merges intervals that overlap or abut. If more than MAX_PAIRS still
+// survive, the last slot swallows the surplus.
+
+void
+frange::set_pairs (frange_pair *pairs, unsigned n)
+{
+ gcc_checking_assert (n > 0);
+ machine_mode mode = TYPE_MODE (m_type);
+
+ // Sort by lower bound. N is tiny (at most 2 * MAX_PAIRS).
+ for (unsigned i = 0; i + 1 < n; ++i)
+ for (unsigned j = i + 1; j < n; ++j)
+ if (frange_cmp (pairs[j].min, pairs[i].min) < 0)
+ std::swap (pairs[i], pairs[j]);
+
+ // Fuse overlapping and abutting intervals.
+ unsigned k = 0;
+ for (unsigned i = 1; i < n; ++i)
+ {
+ if (frange_fusible_p (mode, pairs[k].max, pairs[i].min))
+ {
+ if (frange_cmp (pairs[i].max, pairs[k].max) > 0)
+ pairs[k].max = pairs[i].max;
+ }
+ else
+ pairs[++k] = pairs[i];
+ }
+ n = k + 1;
+
+ // Only MAX_PAIRS fit. Like irange, keep the first pieces and let the last
+ // slot swallow the rest.
+ if (n > MAX_PAIRS)
+ {
+ pairs[MAX_PAIRS - 1].max = pairs[n - 1].max;
+ n = MAX_PAIRS;
+ }
+
+ m_kind = VR_RANGE;
+ m_num_ranges = n;
+ for (unsigned i = 0; i < n; ++i)
+ {
+ m_pairs[i] = pairs[i];
+ canonicalize_zeros (m_pairs[i]);
+ }
+
+ normalize_kind ();
+ if (flag_checking)
+ verify_range ();
+}
+
// Setter for franges.
void
@@ -1510,6 +1584,7 @@ frange::verify_range () const
return;
case VR_RANGE:
gcc_checking_assert (m_type);
+ gcc_checking_assert (m_num_ranges >= 1 && m_num_ranges <= MAX_PAIRS);
break;
case VR_NAN:
gcc_checking_assert (m_type);
@@ -1540,6 +1615,12 @@ frange::verify_range () const
&& !real_iszero (&m_pairs[i].max, 1));
}
+ // Sub-ranges are sorted and separated by at least one representable value.
+ for (unsigned i = 1; i < m_num_ranges; ++i)
+ gcc_checking_assert (!frange_fusible_p (TYPE_MODE (m_type),
+ m_pairs[i - 1].max,
+ m_pairs[i].min));
+
// If all the properties are clear, we better not span the entire
// domain, because that would make us varying.
if (m_num_ranges == 1 && m_pos_nan && m_neg_nan)
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 2ea0006ba9f..5e6ee37277f 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -679,6 +679,7 @@ private:
bool normalize_kind ();
bool union_nans (const frange &);
bool intersect_nans (const frange &);
+ void set_pairs (frange_pair *, unsigned);
void canonicalize_zeros (frange_pair &);
tree m_type;
--
2.47.3
