Re: [PATCH 1/2] [frange] Enable sub-ranges.

On Mon, Aug 3, 2026 at 12:16 AM Aldy Hernandez <[email protected]> wrote:
>
> 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.

Thanks for implementing this.
I might take a look at some other related code generation now that we
can represent this.
The main thing I was looking at previously is the adding of 0.0 to a
frange without -0.0 (and NaN) can be optimized away.

Thanks,
Andrea


>
> 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
>