[gcc r17-2891] [frange] Enable sub-ranges.

https://gcc.gnu.org/g:9e391103a9fcc140584193ca7f75e5e64181d632

commit r17-2891-g9e391103a9fcc140584193ca7f75e5e64181d632
Author: Aldy Hernandez <[email protected]>
Date:   Thu Jul 30 08:55:15 2026 +0000

    [frange] Enable sub-ranges.
    
    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.
    
    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.

Diff:
---
 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(-)

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 000000000000..131fed09ea69
--- /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 000000000000..841c6569a66e
--- /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 000000000000..4ae8ee1477c1
--- /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 18aa82733a4b..2ce257f6ce60 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 5e6ee37277ff..dc80b2b4bf10 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;