[PATCH 1/2] [frange] Enable sub-ranges.
Aldy Hernandez <[email protected]> Mon, 3 Aug 2026 09:14:44 +0200
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
Raise MAX_PAIRS from 1 to 2, enabling sub-ranges. This will allow us
to represent non-zero and other inequalities in a follow-up patch.
I tested how many sub-ranges would give us the most bang for the buck,
by allowing 10 sub-ranges, and seeing how many we created and used.
Even though 1 sub-range caught 91.29% of what we encountered in real
life (well, in a corpus of Fortran files from the LAPACK package), we
couldn't represent non-zero, which caused DOM to get a bunch of cases
we missed. With 2 subranges, we caught 99.63% of ranges generated,
and anything past this was useless, cause we either didn't generate
them in real life, or there was no change in generated code by having
more sub-ranges. For instance, from 3631 files, going from 2 to 3
sub-ranges caused code generation changes in 4 files (all rotmg*).
Going past 3, produced zero effect.
I also benchmarked LAPACK and the GSL package for jump threading
changes as well as VRP constant propagation. For LAPACK, we got 0.31%
more jump threading opportunities, and for GSL 1.10%. For VRP it was
the opposite, LAPACK got 0.48% more constants propagated, whereas GSL
got a mere 0.26% boost.
This may not seem like much, but just being able to represent the
inverse of a constant (e.g. nonzero) closes the gap with the DOM
internal tables. With this work, we get 100% of what DOM threading
was getting with its internal tables for the LAPACK corpus. We nuked
58 of the regressions, and I believe this will fix a few PRs we had
open for nonzero folding, as well as some signed zero missed
optimizations.
Oh, and with this patch we cause code generation differences in 2.2%
of LAPACK, and 5.48% of GSL files. I didn't dig into any of these,
but it seems other passes benefit as well. Either way, we needed a
way to represent != 0.0, which seemed like a big limitation in the
initial frange implementation, and was causing me to lose sleep in my
self-imposed break from hacking.
Tested on ppc64le: regstrap, LAPACK, GSL.
Pushed.
gcc/ChangeLog:
* value-range.h (class frange): Raise MAX_PAIRS to 2.
* value-range.cc: Include value-range-storage.h.
(real_from_str, range_tests_sub_ranges, range_tests_sub_ranges_nan)
(range_tests_sub_ranges_zero, range_tests_sub_ranges_storage): New.
(range_tests_floats): Call them, and adjust the disjoint-union test.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/vrp-float-15.c: New test.
* gcc.dg/tree-ssa/vrp-float-16.c: New test.
* gcc.dg/tree-ssa/vrp-float-17.c: New test.
---
gcc/testsuite/gcc.dg/tree-ssa/vrp-float-15.c | 24 +++
gcc/testsuite/gcc.dg/tree-ssa/vrp-float-16.c | 30 ++++
gcc/testsuite/gcc.dg/tree-ssa/vrp-float-17.c | 26 +++
gcc/value-range.cc | 160 ++++++++++++++++++-
gcc/value-range.h | 6 +-
5 files changed, 239 insertions(+), 7 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-float-15.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-float-16.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-float-17.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-15.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-15.c
new file mode 100644
index 00000000000..131fed09ea6
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-15.c
@@ -0,0 +1,24 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-thread-jumps -fdump-tree-evrp" } */
+
+extern void link_error (void);
+
+/* x is [-Inf, 2.0] U [4.0, +Inf]; 3.0 falls in the gap. */
+void
+ineq_gap (double x)
+{
+ if (x <= 2.0 || x >= 4.0)
+ if (x == 3.0)
+ link_error ();
+}
+
+/* x is [2.0, 2.0] U [4.0, 4.0]; 3.0 falls in the gap. */
+void
+two_points (double x)
+{
+ if (x == 2.0 || x == 4.0)
+ if (x == 3.0)
+ link_error ();
+}
+
+/* { dg-final { scan-tree-dump-not "link_error" "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-16.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-16.c
new file mode 100644
index 00000000000..841c6569a66
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-16.c
@@ -0,0 +1,30 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-thread-jumps -fdump-tree-evrp-details" } */
+
+/* Verify the pretty-printer shows two-piece ranges correctly. */
+
+/* Two disjoint points: {2.0} U {4.0}. */
+double
+pp_two_points (int c)
+{
+ double x;
+ if (c)
+ x = 2.0;
+ else
+ x = 4.0;
+ return x;
+}
+
+/* Two intervals from inequalities: [-Inf, 2.0] U [4.0, +Inf]. */
+double
+pp_ineq_gap (double x)
+{
+ if (x <= 2.0 || x >= 4.0)
+ return x;
+ return 0.0;
+}
+
+/* {2.0, 2.0}{4.0, 4.0} -- two disjoint pieces on one line. */
+/* { dg-final { scan-tree-dump "2\\.0e\\+0\[^\r\n\]*2\\.0e\\+0\[^\r\n\]*4\\.0e\\+0\[^\r\n\]*4\\.0e\\+0" "evrp" } } */
+/* [-Inf, 2.0][4.0, +Inf] -- inequality gap on one line. */
+/* { dg-final { scan-tree-dump "-Inf, 2\\.0e\\+0\[^\r\n\]*4\\.0e\\+0\[^\r\n\]*\\+Inf" "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-17.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-17.c
new file mode 100644
index 00000000000..4ae8ee1477c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-17.c
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-thread-jumps -fdump-tree-evrp" } */
+
+extern void link_error (void);
+
+/* [-Inf, 2.0] U [4.0, +Inf], meet [1.0, 5.0] -> [1.0, 2.0] U [4.0, 5.0]. */
+void
+meet_ineq (double x)
+{
+ if (x <= 2.0 || x >= 4.0)
+ if (x >= 1.0 && x <= 5.0)
+ if (x == 3.0)
+ link_error ();
+}
+
+/* [0.0, 5.0] U [10.0, 15.0], meet [4.0, 11.0] -> [4.0, 5.0] U [10.0, 11.0]. */
+void
+meet_intervals (double x)
+{
+ if ((x >= 0.0 && x <= 5.0) || (x >= 10.0 && x <= 15.0))
+ if (x >= 4.0 && x <= 11.0)
+ if (x == 7.0)
+ link_error ();
+}
+
+/* { dg-final { scan-tree-dump-not "link_error" "evrp" } } */
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 18aa82733a4..2ce257f6ce6 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -28,6 +28,7 @@ along with GCC; see the file COPYING3. If not see
#include "ssa.h"
#include "tree-pretty-print.h"
#include "value-range-pretty-print.h"
+#include "value-range-storage.h"
#include "fold-const.h"
#include "gimple-range.h"
#include "tree-dfa.h"
@@ -3601,6 +3602,148 @@ frange_float (const char *lb, const char *ub, tree type = float_type_node)
return frange (type, min, max);
}
+// Build the REAL_VALUE_TYPE for the string S.
+
+static REAL_VALUE_TYPE
+real_from_str (const char *s)
+{
+ REAL_VALUE_TYPE r;
+ gcc_assert (real_from_string (&r, s) == 0);
+ return r;
+}
+
+static void
+range_tests_sub_ranges ()
+{
+ frange r0, r1;
+
+ // A union of two disjoint intervals keeps both.
+ r0 = frange_float ("3", "5");
+ r1 = frange_float ("10", "12");
+ r0.union_ (r1);
+ ASSERT_EQ (r0.num_pairs (), 2);
+ ASSERT_TRUE (r0.contains_p (real_from_str ("4")));
+ ASSERT_TRUE (r0.contains_p (real_from_str ("11")));
+ ASSERT_FALSE (r0.contains_p (real_from_str ("7")));
+
+ REAL_VALUE_TYPE three = real_from_str ("3");
+ REAL_VALUE_TYPE twelve = real_from_str ("12");
+ ASSERT_TRUE (real_identical (&r0.lower_bound (), &three));
+ ASSERT_TRUE (real_identical (&r0.upper_bound (), &twelve));
+
+ // Intersecting away one side leaves a single interval again.
+ r1 = frange_float ("0", "6");
+ r0.intersect (r1);
+ ASSERT_EQ (r0.num_pairs (), 1);
+ ASSERT_TRUE (r0.contains_p (real_from_str ("4")));
+ ASSERT_FALSE (r0.contains_p (real_from_str ("11")));
+
+ // Overlapping intervals fuse rather than leave a gap.
+ r0 = frange_float ("3", "8");
+ r1 = frange_float ("5", "12");
+ r0.union_ (r1);
+ ASSERT_EQ (r0.num_pairs (), 1);
+ ASSERT_TRUE (r0.contains_p (real_from_str ("7")));
+
+ if (frange::MAX_PAIRS == 2)
+ {
+ // When more pieces arrive than fit, the last slot swallows the tail:
+ // [0,1] stays and [3,4], [100,101] merge into [3,101].
+ r0 = frange_float ("0", "1");
+ r1 = frange_float ("100", "101");
+ r0.union_ (r1);
+ r1 = frange_float ("3", "4");
+ r0.union_ (r1);
+ ASSERT_EQ (r0.num_pairs (), 2);
+ ASSERT_TRUE (r0.contains_p (real_from_str ("50")));
+ ASSERT_TRUE (r0.contains_p (real_from_str ("3.5")));
+ ASSERT_TRUE (r0.contains_p (real_from_str ("100.5")));
+ }
+
+ // Equality accounts for the sub-ranges.
+ r0 = frange_float ("3", "5");
+ r1 = frange_float ("10", "12");
+ r0.union_ (r1);
+ r1 = frange_float ("3", "12");
+ ASSERT_NE (r0, r1);
+
+ // Intersecting every piece away, with the NAN cleared, leaves UNDEFINED.
+ r0 = frange_float ("3", "5");
+ r1 = frange_float ("10", "12");
+ r0.union_ (r1);
+ r0.clear_nan ();
+ r1 = frange_float ("20", "25");
+ r1.clear_nan ();
+ r0.intersect (r1);
+ ASSERT_TRUE (r0.undefined_p ());
+}
+
+static void
+range_tests_sub_ranges_zero ()
+{
+ frange r0, r1;
+
+ // -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");
+ r0.clear_nan ();
+ r1 = frange_float ("0.0", "5");
+ r1.clear_nan ();
+ r0.union_ (r1);
+ ASSERT_EQ (r0.num_pairs (), 1);
+ ASSERT_TRUE (r0.contains_p (dconst0));
+ ASSERT_TRUE (r0.contains_p (dconstm0));
+}
+
+// A cached frange must come back with every sub-range intact.
+
+static void
+range_tests_sub_ranges_storage ()
+{
+ vrange_allocator alloc (false);
+
+ // A two-piece range comes back as two pieces, unchanged.
+ frange r0 = frange_float ("3", "5");
+ frange r1 = frange_float ("10", "12");
+ r0.union_ (r1);
+ ASSERT_EQ (r0.num_pairs (), 2);
+
+ vrange_storage *slot = alloc.clone (r0);
+ frange r2;
+ slot->get_vrange (r2, float_type_node);
+ ASSERT_EQ (r2.num_pairs (), 2);
+ ASSERT_EQ (r2, r0);
+}
+
+// NANs and sub-ranges: unioning in a NAN keeps the intervals, while
+// intersecting the intervals away collapses to a plain NAN with a single
+// pair.
+
+static void
+range_tests_sub_ranges_nan ()
+{
+ frange r0, r1;
+
+ // Union with a NAN keeps both intervals and gains the NAN.
+ r0 = frange_float ("3", "5");
+ r1 = frange_float ("10", "12");
+ r0.union_ (r1);
+ r0.clear_nan ();
+ r1.set_nan (float_type_node);
+ r0.union_ (r1);
+ ASSERT_EQ (r0.num_pairs (), 2);
+ ASSERT_TRUE (r0.maybe_isnan ());
+
+ // Intersecting the intervals away leaves just the NAN.
+ r0 = frange_float ("3", "5");
+ r1 = frange_float ("10", "12");
+ r0.union_ (r1);
+ r1 = frange_float ("20", "25");
+ r0.intersect (r1);
+ ASSERT_TRUE (r0.known_isnan ());
+ ASSERT_EQ (r0.num_pairs (), 1);
+}
+
static void
range_tests_nan ()
{
@@ -3901,12 +4044,20 @@ range_tests_floats ()
frange r0, r1;
if (HONOR_NANS (float_type_node))
- range_tests_nan ();
+ {
+ range_tests_nan ();
+ range_tests_sub_ranges_nan ();
+ }
range_tests_signbit ();
range_tests_flush_denormals ();
+ range_tests_sub_ranges ();
+ range_tests_sub_ranges_storage ();
if (HONOR_SIGNED_ZEROS (float_type_node))
- range_tests_signed_zeros ();
+ {
+ range_tests_signed_zeros ();
+ range_tests_sub_ranges_zero ();
+ }
// A range of [-INF,+INF] is actually VARYING if no other properties
// are set.
@@ -3929,11 +4080,12 @@ range_tests_floats ()
ASSERT_NE (r0, r1);
}
- // [3,5] U [10,12] = [3,12].
+ // [3,5] U [10,12] = [3,5][10,12]
r0 = frange_float ("3", "5");
r1 = frange_float ("10", "12");
r0.union_ (r1);
- ASSERT_EQ (r0, frange_float ("3", "12"));
+ ASSERT_EQ (r0.num_pairs (), 2);
+ ASSERT_NE (r0, frange_float ("3", "12"));
// [5,10] U [4,8] = [4,10]
r0 = frange_float ("5", "10");
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 5e6ee37277f..dc80b2b4bf1 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -594,8 +594,8 @@ struct frange_pair
// A subset of possible values for a floating point type.
//
-// The representation is a single interval, unioned with a subset of
-// { -NaN, +NaN }.
+// The representation is a handful of disjoint intervals, unioned with a
+// subset of { -NaN, +NaN }.
class frange final : public vrange
{
@@ -666,7 +666,7 @@ public:
bool known_isdenormal_or_zero () const;
virtual void verify_range () const override;
- static const unsigned int MAX_PAIRS = 1;
+ static const unsigned int MAX_PAIRS = 2;
unsigned num_pairs () const { return m_num_ranges; }
const REAL_VALUE_TYPE &lower_bound (unsigned pair) const;
const REAL_VALUE_TYPE &upper_bound (unsigned pair) const;
--
2.47.3