[PATCH 2/2] [frange] Represent the inverse of a constant range
Aldy Hernandez <[email protected]> Mon, 3 Aug 2026 09:14:46 +0200
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
We've been throwing away the VR_ANTI_RANGE flag when setting a range,
and quietly turning it into VARYING. This patch allows setting the
inverse of a range:
frange::set (TYPE, MIN, MAX, VR_ANTI_RANGE)
This allows us to represent x != C, which is very useful for
representing non-zero.
Excluding a point is two sub-ranges:
[-INF, prev (C)] U [next (C), +INF]
range-op-float has in fact been asking for this all along.
operator_not_equal::op1_range hands us r.set (type, tmp, tmp,
VR_ANTI_RANGE) on the true edge, and operator_equal::op1_range does
the same on the false edge. They needed no changes; frange simply had
nowhere to put the answer.
Nothing here is special-cased. C == 0.0 excludes both zeros for free,
because prev (0.0) is the largest negative denormal and next (0.0) the
smallest positive one.
With this patch we finally come to parity with DOM floating point
threading, at least when it comes to the LAPACK package, which I've
taken as representative of floating point intensive code.
Tested on ppc64le Linux: regstrap, LAPACK, GSL, etc. I also
benchmarked threading counts and VRP folds, as per the last commit in
this series.
pushed.
gcc/ChangeLog:
* value-range.h (class frange): Declare set_excluding.
* value-range.cc (frange::set_excluding): New.
(frange::set): Assert KIND is VR_RANGE or VR_ANTI_RANGE and that the
endpoints are not NAN. Turn a VR_ANTI_RANGE into the two sub-ranges
that exclude the point.
(frange_float_excluding, range_tests_excluding): New.
(range_tests_floats): Call range_tests_excluding.
* value-range-storage.cc (frange_storage::get_frange): Return early
for VR_VARYING, like irange_storage::get_irange.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/vrp-float-14.c: New test.
---
gcc/testsuite/gcc.dg/tree-ssa/vrp-float-14.c | 32 ++++
gcc/value-range-storage.cc | 5 +
gcc/value-range.cc | 179 +++++++++++++++++--
gcc/value-range.h | 2 +
4 files changed, 205 insertions(+), 13 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-float-14.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-14.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-14.c
new file mode 100644
index 00000000000..95609501a3e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-14.c
@@ -0,0 +1,32 @@
+// { dg-do compile }
+// { dg-options "-O2 -fgimple -fdump-tree-evrp" }
+
+int g;
+
+int __GIMPLE (ssa, startwith ("evrp"))
+some_constant (double x)
+{
+ __BB(2):
+ if (x_1(D) != 1.0e+0)
+ goto __BB3;
+ else
+ goto __BB5;
+
+ __BB(3):
+ g = 1;
+ goto __BB4;
+
+ __BB(4):
+ if (x_1(D) == 1.0e+0) // should fold to false
+ goto __BB5;
+ else
+ goto __BB6;
+
+ __BB(5):
+ return 0;
+
+ __BB(6):
+ return 1;
+}
+
+// { dg-final { scan-tree-dump-not "if \\(x_1\\(D\\) == 1\\.0e\\+0\\)" "evrp" } }
diff --git a/gcc/value-range-storage.cc b/gcc/value-range-storage.cc
index c64bf09e9fe..c1b9d8ec2f6 100644
--- a/gcc/value-range-storage.cc
+++ b/gcc/value-range-storage.cc
@@ -569,6 +569,11 @@ frange_storage::get_frange (frange &r, tree type) const
r.set_undefined ();
return;
}
+ if (m_kind == VR_VARYING)
+ {
+ r.set_varying (type);
+ return;
+ }
// Rebuild piecewise, like irange_storage::get_irange().
r.set_undefined ();
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 2ce257f6ce6..b4c097343d9 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -1157,6 +1157,60 @@ frange::set_pairs (frange_pair *pairs, unsigned n)
verify_range ();
}
+// Set the range to everything except the closed interval [MIN, MAX], which
+// takes two sub-ranges:
+//
+// [-INF, prev (MIN)] U [next (MAX), +INF]
+//
+// Either half falls away when the excluded interval reaches the edge of the
+// domain, and if it covers the entire domain.
+
+void
+frange::set_excluding (tree type, const REAL_VALUE_TYPE &min,
+ const REAL_VALUE_TYPE &max, const nan_state &nan)
+{
+ gcc_checking_assert (frange_cmp (min, max) <= 0);
+
+ machine_mode mode = TYPE_MODE (type);
+ REAL_VALUE_TYPE dom_min = frange_val_min (type);
+ REAL_VALUE_TYPE dom_max = frange_val_max (type);
+ frange_pair pairs[MAX_PAIRS];
+ unsigned n = 0;
+
+ // PREV is the largest value below MIN, so DOM_MIN <= PREV whenever there is
+ // anything below MIN at all. Likewise for NEXT above MAX.
+ if (frange_cmp (dom_min, min) < 0)
+ {
+ REAL_VALUE_TYPE prev = min;
+ frange_nextafter (mode, prev, dconstninf);
+ pairs[n++] = { dom_min, prev };
+ }
+ if (frange_cmp (max, dom_max) < 0)
+ {
+ REAL_VALUE_TYPE next = max;
+ frange_nextafter (mode, next, dconstinf);
+ pairs[n++] = { next, dom_max };
+ }
+
+ // The excluded interval covered the entire domain.
+ if (n == 0)
+ {
+ if (HONOR_NANS (type) && (nan.pos_p () || nan.neg_p ()))
+ set_nan (type, nan);
+ else
+ set_undefined ();
+ return;
+ }
+
+ set (type, pairs[0].min, pairs[0].max, nan);
+ if (n == 2)
+ {
+ frange tmp;
+ tmp.set (type, pairs[1].min, pairs[1].max, nan);
+ union_ (tmp);
+ }
+}
+
// Setter for franges.
void
@@ -1164,23 +1218,17 @@ frange::set (tree type,
const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
const nan_state &nan, value_range_kind kind)
{
- switch (kind)
+ // VARYING and UNDEFINED go through set_varying() and set_undefined()
+ // respectively, like we do for irange.
+ gcc_checking_assert (kind == VR_RANGE || kind == VR_ANTI_RANGE);
+ gcc_checking_assert (!real_isnan (&min) && !real_isnan (&max));
+
+ if (kind == VR_ANTI_RANGE)
{
- case VR_UNDEFINED:
- set_undefined ();
+ set_excluding (type, min, max, nan);
return;
- case VR_VARYING:
- case VR_ANTI_RANGE:
- set_varying (type);
- return;
- case VR_RANGE:
- break;
- default:
- gcc_unreachable ();
}
- gcc_checking_assert (!real_isnan (&min) && !real_isnan (&max));
-
m_kind = kind;
m_type = type;
m_num_ranges = 1;
@@ -3678,11 +3726,115 @@ range_tests_sub_ranges ()
ASSERT_TRUE (r0.undefined_p ());
}
+// Build a range that excludes the single point C.
+
+static frange
+frange_float_excluding (const char *c)
+{
+ REAL_VALUE_TYPE r = real_from_str (c);
+ frange f;
+ f.set (float_type_node, r, r, VR_ANTI_RANGE);
+ return f;
+}
+
+static void
+range_tests_excluding ()
+{
+ frange r0, r1;
+
+ // "x != 1.0" is two sub-ranges with 1.0 missing.
+ r0 = frange_float_excluding ("1.0");
+ ASSERT_FALSE (r0.varying_p ());
+ ASSERT_FALSE (r0.undefined_p ());
+ ASSERT_EQ (r0.num_pairs (), 2);
+ ASSERT_FALSE (r0.contains_p (real_from_str ("1.0")));
+ ASSERT_TRUE (r0.contains_p (real_from_str ("2.0")));
+ ASSERT_TRUE (r0.contains_p (real_from_str ("0.0")));
+ ASSERT_TRUE (r0.contains_p (real_from_str ("-1.0")));
+ ASSERT_FALSE (r0.singleton_p ());
+ // A NAN compares unequal to everything, so this says nothing about NANs.
+ if (HONOR_NANS (float_type_node))
+ ASSERT_TRUE (r0.maybe_isnan ());
+ // The extremes still span the domain.
+ REAL_VALUE_TYPE dom_min = frange_val_min (float_type_node);
+ REAL_VALUE_TYPE dom_max = frange_val_max (float_type_node);
+ ASSERT_TRUE (real_identical (&r0.lower_bound (), &dom_min));
+ ASSERT_TRUE (real_identical (&r0.upper_bound (), &dom_max));
+
+ // Any constant, not just 0.0 or 1.0.
+ r0 = frange_float_excluding ("5.5");
+ ASSERT_EQ (r0.num_pairs (), 2);
+ ASSERT_FALSE (r0.contains_p (real_from_str ("5.5")));
+ ASSERT_TRUE (r0.contains_p (real_from_str ("5.4")));
+
+ // "x != 1.0" met with [1.0, 1.0] is empty.
+ r0 = frange_float_excluding ("1.0");
+ r1 = frange_float ("1.0", "1.0");
+ r1.clear_nan ();
+ r0.intersect (r1);
+ ASSERT_TRUE (r0.undefined_p ());
+
+ // Excluding a point outside a range changes nothing.
+ r0 = frange_float ("3.0", "5.0");
+ r0.clear_nan ();
+ r1 = frange_float_excluding ("1.0");
+ r0.intersect (r1);
+ ASSERT_EQ (r0.num_pairs (), 1);
+ ASSERT_TRUE (r0.contains_p (real_from_str ("3.0")));
+ ASSERT_TRUE (r0.contains_p (real_from_str ("5.0")));
+
+ // Union puts the point back.
+ r0 = frange_float_excluding ("1.0");
+ r1 = frange_float ("1.0", "1.0");
+ r0.union_ (r1);
+ ASSERT_TRUE (r0.varying_p ());
+
+ // Two different exclusions cannot both be held.
+ r0 = frange_float_excluding ("1.0");
+ r1 = frange_float_excluding ("2.0");
+ r0.union_ (r1);
+ ASSERT_TRUE (r0.varying_p ());
+
+ // Nor can an intersection hold both.
+ r0 = frange_float_excluding ("1.0");
+ r1 = frange_float_excluding ("2.0");
+ r0.intersect (r1);
+ ASSERT_TRUE (r0.contains_p (real_from_str ("0.0")));
+ ASSERT_TRUE (r0.contains_p (real_from_str ("3.0")));
+
+ // Equality accounts for the gap.
+ r0 = frange_float_excluding ("1.0");
+ r1 = frange_float_excluding ("2.0");
+ ASSERT_NE (r0, r1);
+ r1 = frange_float_excluding ("1.0");
+ ASSERT_EQ (r0, r1);
+}
+
static void
range_tests_sub_ranges_zero ()
{
frange r0, r1;
+ // "x != 0.0" must exclude BOTH zeros, since -0.0 == 0.0 and so "x != 0.0" is
+ // false for either. The seam lands on the denormals either side of zero,
+ // which falls out of nextafter with no special case.
+ r0 = frange_float_excluding ("0.0");
+ ASSERT_EQ (r0.num_pairs (), 2);
+ ASSERT_FALSE (r0.contains_p (dconst0));
+ ASSERT_FALSE (r0.contains_p (dconstm0));
+ ASSERT_TRUE (r0.contains_p (real_from_str ("1.0")));
+ ASSERT_TRUE (r0.contains_p (real_from_str ("-1.0")));
+
+ // Excluding zero from [-0.0, 5.0] eats the lower end entirely.
+ r0 = frange_float ("-0.0", "5.0");
+ r0.clear_nan ();
+ r1 = frange_float_excluding ("0.0");
+ r0.intersect (r1);
+ ASSERT_EQ (r0.num_pairs (), 1);
+ ASSERT_FALSE (r0.contains_p (dconst0));
+ ASSERT_FALSE (r0.contains_p (dconstm0));
+ ASSERT_TRUE (r0.contains_p (real_from_str ("5.0")));
+
// -0.0 and +0.0 abut: nothing is representable between them, so the two
// halves fuse into one interval rather than leaving a gap.
r0 = frange_float ("-5", "-0.0");
@@ -4052,6 +4204,7 @@ range_tests_floats ()
range_tests_flush_denormals ();
range_tests_sub_ranges ();
range_tests_sub_ranges_storage ();
+ range_tests_excluding ();
if (HONOR_SIGNED_ZEROS (float_type_node))
{
diff --git a/gcc/value-range.h b/gcc/value-range.h
index dc80b2b4bf1..585120dda44 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -681,6 +681,8 @@ private:
bool intersect_nans (const frange &);
void set_pairs (frange_pair *, unsigned);
void canonicalize_zeros (frange_pair &);
+ void set_excluding (tree type, const REAL_VALUE_TYPE &,
+ const REAL_VALUE_TYPE &, const nan_state &);
tree m_type;
frange_pair m_pairs[MAX_PAIRS];
--
2.47.3