[COMMITTED] Add signbit property to frange to better model signed zeros.

[COMMITTED] Add signbit property to frange to better model signed zeros.

[Aldy Hernandez]

As discussed here:

	https://gcc.gnu.org/pipermail/gcc-patches/2022-August/600656.html

This adds an frange property to keep track of the sign bit.  We keep
it updated at all times, but we don't use it make any decisions when
!HONOR_SIGNED_ZEROS.

With this property we can now query the range for the appropriate sign
with frange::get_signbit ().  Possible values are yes, no, and unknown.

We had some old notes in PR24021 that indicated what was important in
the FP world: finite, signed zeros, normalized, in the range [-1,1] for
trig functions, etc.  I think frange now has enough to model everything
we care about.

gcc/ChangeLog:

	* range-op-float.cc (foperator_equal::op1_range): Do not copy sign
	bit.
	(foperator_not_equal::op1_range): Same.
	* value-query.cc (range_query::get_tree_range): Set sign bit.
	* value-range-pretty-print.cc (vrange_printer::visit): Dump sign bit.
	* value-range.cc (frange::set_signbit): New.
	(frange::set): Adjust for sign bit.
	(frange::normalize_kind): Same.
	(frange::union_): Remove useless comment.
	(frange::intersect): Same.
	(frange::contains_p): Adjust for sign bit.
	(frange::singleton_p): Same.
	(frange::verify_range): Same.
	(range_tests_signbit): New tests.
	(range_tests_floats): Call range_tests_signbit.
	* value-range.h (class frange_props): Add signbit
	(class frange): Same.
---
 gcc/range-op-float.cc           |   6 +
 gcc/value-query.cc              |  27 +++--
 gcc/value-range-pretty-print.cc |   1 +
 gcc/value-range.cc              | 200 +++++++++++++++++++++++++++-----
 gcc/value-range.h               |   4 +
 5 files changed, 204 insertions(+), 34 deletions(-)

diff --git a/gcc/range-op-float.cc b/gcc/range-op-float.cc
index c30f2af391c..2f1af4055c3 100644
--- a/gcc/range-op-float.cc
+++ b/gcc/range-op-float.cc
@@ -361,6 +361,9 @@ foperator_equal::op1_range (frange &r, tree type,
     case BRS_TRUE:
       // If it's true, the result is the same as OP2.
       r = op2;
+      // Make sure we don't copy the sign bit if we may have a zero.
+      if (HONOR_SIGNED_ZEROS (type) && r.contains_p (build_zero_cst (type)))
+	r.set_signbit (fp_prop::VARYING);
       // The TRUE side of op1 == op2 implies op1 is !NAN.
       r.set_nan (fp_prop::NO);
       break;
@@ -462,6 +465,9 @@ foperator_not_equal::op1_range (frange &r, tree type,
     case BRS_FALSE:
       // If it's false, the result is the same as OP2.
       r = op2;
+      // Make sure we don't copy the sign bit if we may have a zero.
+      if (HONOR_SIGNED_ZEROS (type) && r.contains_p (build_zero_cst (type)))
+	r.set_signbit (fp_prop::VARYING);
       // The FALSE side of op1 != op2 implies op1 is !NAN.
       r.set_nan (fp_prop::NO);
       break;
diff --git a/gcc/value-query.cc b/gcc/value-query.cc
index 4637fb409e5..201f679a36e 100644
--- a/gcc/value-query.cc
+++ b/gcc/value-query.cc
@@ -217,14 +217,25 @@ range_query::get_tree_range (vrange &r, tree expr, gimple *stmt)
       return true;
 
     case REAL_CST:
-      if (TREE_OVERFLOW_P (expr))
-	expr = drop_tree_overflow (expr);
-      r.set (expr, expr);
-      if (real_isnan (TREE_REAL_CST_PTR (expr)))
-	as_a <frange> (r).set_nan (fp_prop::YES);
-      else
-	as_a <frange> (r).set_nan (fp_prop::NO);
-      return true;
+      {
+	if (TREE_OVERFLOW_P (expr))
+	  expr = drop_tree_overflow (expr);
+
+	frange &f = as_a <frange> (r);
+	f.set (expr, expr);
+
+	// Singletons from the tree world have known properties.
+	REAL_VALUE_TYPE *rv = TREE_REAL_CST_PTR (expr);
+	if (real_isnan (rv))
+	  f.set_nan (fp_prop::YES);
+	else
+	  f.set_nan (fp_prop::NO);
+	if (real_isneg (rv))
+	  f.set_signbit (fp_prop::YES);
+	else
+	  f.set_signbit (fp_prop::NO);
+	return true;
+      }
 
     case SSA_NAME:
       gimple_range_global (r, expr);
diff --git a/gcc/value-range-pretty-print.cc b/gcc/value-range-pretty-print.cc
index e66d56da29d..93e18d3c1b6 100644
--- a/gcc/value-range-pretty-print.cc
+++ b/gcc/value-range-pretty-print.cc
@@ -146,6 +146,7 @@ vrange_printer::visit (const frange &r) const
   pp_string (pp, "] ");
 
   print_frange_prop ("NAN", r.get_nan ());
+  print_frange_prop ("SIGN", r.get_signbit ());
 }
 
 // Print the FP properties in an frange.
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 3c7d4cb84b9..71581b2c54d 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -288,6 +288,58 @@ frange::set_nan (fp_prop::kind k)
 
   m_props.set_nan (k);
   normalize_kind ();
+  if (flag_checking)
+    verify_range ();
+}
+
+// Set the SIGNBIT property.  Adjust the range if appropriate.
+
+void
+frange::set_signbit (fp_prop::kind k)
+{
+  gcc_checking_assert (m_type);
+
+  // No additional adjustments are needed for a NAN.
+  if (get_nan ().yes_p ())
+    {
+      m_props.set_signbit (k);
+      return;
+    }
+  // Ignore sign changes when they're set correctly.
+  if (real_less (&m_max, &dconst0))
+    {
+      gcc_checking_assert (get_signbit ().yes_p ());
+      return;
+    }
+  if (real_less (&dconst0, &m_min))
+    {
+      gcc_checking_assert (get_signbit ().no_p ());
+      return;
+    }
+  // Adjust the range depending on the sign bit.
+  if (k == fp_prop::YES)
+    {
+      // Crop the range to [-INF, 0].
+      REAL_VALUE_TYPE min;
+      real_inf (&min, 1);
+      frange crop (m_type, min, dconst0);
+      intersect (crop);
+      m_props.set_signbit (fp_prop::YES);
+    }
+  else if (k == fp_prop::NO)
+    {
+      // Crop the range to [0, +INF].
+      REAL_VALUE_TYPE max;
+      real_inf (&max, 0);
+      frange crop (m_type, dconst0, max);
+      intersect (crop);
+      m_props.set_signbit (fp_prop::NO);
+    }
+  else
+    m_props.set_signbit (fp_prop::VARYING);
+
+  if (flag_checking)
+    verify_range ();
 }
 
 // Setter for franges.
@@ -329,6 +381,12 @@ frange::set (tree min, tree max, value_range_kind kind)
   else if (!HONOR_NANS (m_type))
     m_props.nan_set_no ();
 
+  // Set SIGNBIT property for positive and negative ranges.
+  if (real_less (&m_max, &dconst0))
+    m_props.signbit_set_yes ();
+  else if (real_less (&dconst0, &m_min))
+    m_props.signbit_set_no ();
+
   // Check for swapped ranges.
   gcc_checking_assert (is_nan || tree_compare (LE_EXPR, min, max));
 
@@ -360,7 +418,7 @@ bool
 frange::normalize_kind ()
 {
   // Undefined is viral.
-  if (m_props.nan_undefined_p ())
+  if (m_props.nan_undefined_p () || m_props.signbit_undefined_p ())
     {
       set_undefined ();
       return true;
@@ -438,13 +496,6 @@ frange::union_ (const vrange &v)
     }
 
   bool changed = m_props.union_ (r.m_props);
-
-  // Note: for the combination of zeros that differ in sign we keep
-  // the endpoints untouched.  This means that for -0.0 U +0.0, the
-  // result will be -0.0.  Ultimately this doesn't matter, because we
-  // keep singleton zeros ambiguous throughout to avoid propagating
-  // them.  See frange::singleton_p().
-
   if (real_less (&r.m_min, &m_min))
     {
       m_min = r.m_min;
@@ -484,12 +535,6 @@ frange::intersect (const vrange &v)
 
   bool changed = m_props.intersect (r.m_props);
 
-  // Note: for the combination of zeros that differ in sign we keep
-  // the endpoints untouched.  This means that for -0.0 ^ +0.0, the
-  // result will be -0.0.  Ultimately this doesn't matter, because we
-  // keep singleton zeros ambiguous throughout to avoid propagating
-  // them.  See frange::singleton_p().
-
   if (real_less (&m_min, &r.m_min))
     {
       m_min = r.m_min;
@@ -563,26 +608,51 @@ frange::contains_p (tree cst) const
 
   gcc_checking_assert (m_kind == VR_RANGE);
 
-  return (real_compare (GE_EXPR, TREE_REAL_CST_PTR (cst), &m_min)
-	  && real_compare (LE_EXPR, TREE_REAL_CST_PTR (cst), &m_max));
+  const REAL_VALUE_TYPE *rv = TREE_REAL_CST_PTR (cst);
+  if (real_compare (GE_EXPR, rv, &m_min)
+      && real_compare (LE_EXPR, rv, &m_max))
+    {
+      if (HONOR_SIGNED_ZEROS (m_type) && real_iszero (rv))
+	{
+	  if (get_signbit ().yes_p ())
+	    return real_isneg (rv);
+	  else if (get_signbit ().no_p ())
+	    return !real_isneg (rv);
+	  else
+	    return true;
+	}
+      return true;
+    }
+  return false;
 }
 
 // If range is a singleton, place it in RESULT and return TRUE.  If
 // RESULT is NULL, just return TRUE.
 //
-// A NAN can never be a singleton, and neither can a 0.0 if we're
-// honoring signed zeros because we have no way of telling which zero
-// it is.
+// A NAN can never be a singleton.
 
 bool
 frange::singleton_p (tree *result) const
 {
   if (m_kind == VR_RANGE && real_identical (&m_min, &m_max))
     {
-      // If we're honoring signed zeros, fail because we don't know
-      // which zero we have.  This avoids propagating the wrong zero.
+      // Return the appropriate zero if known.
       if (HONOR_SIGNED_ZEROS (m_type) && zero_p ())
-	return false;
+	{
+	  if (get_signbit ().no_p ())
+	    {
+	      if (result)
+		*result = build_real (m_type, dconst0);
+	      return true;
+	    }
+	  if (get_signbit ().yes_p ())
+	    {
+	      if (result)
+		*result = build_real (m_type, real_value_negate (&dconst0));
+	      return true;
+	    }
+	  return false;
+	}
 
       // Return false for any singleton that may be a NAN.
       if (HONOR_NANS (m_type) && !get_nan ().no_p ())
@@ -639,6 +709,14 @@ frange::verify_range ()
       gcc_checking_assert (real_isnan (&m_min));
       gcc_checking_assert (real_isnan (&m_max));
     }
+  else
+    {
+      // Make sure the signbit and range agree.
+      if (m_props.get_signbit ().yes_p ())
+	gcc_checking_assert (real_compare (LE_EXPR, &m_max, &dconst0));
+      else if (m_props.get_signbit ().no_p ())
+	gcc_checking_assert (real_compare (GE_EXPR, &m_min, &dconst0));
+    }
 
   // If all the properties are clear, we better not span the entire
   // domain, because that would make us varying.
@@ -3605,16 +3683,85 @@ range_tests_signed_zeros ()
   tree neg_zero = fold_build1 (NEGATE_EXPR, float_type_node, zero);
   frange r0, r1;
 
-  // ?? If -0.0 == +0.0, then a range of [-0.0, -0.0] should
-  // contain +0.0 and vice versa.  We probably need a property to
-  // track signed zeros in the frange like we do for NAN, to
-  // properly model all this.
+  // Since -0.0 == +0.0, a range of [-0.0, -0.0] should contain +0.0
+  // and vice versa.
   r0 = frange (zero, zero);
   r1 = frange (neg_zero, neg_zero);
   ASSERT_TRUE (r0.contains_p (zero));
   ASSERT_TRUE (r0.contains_p (neg_zero));
   ASSERT_TRUE (r1.contains_p (zero));
   ASSERT_TRUE (r1.contains_p (neg_zero));
+
+  // Test contains_p() when we know the sign of the zero.
+  r0 = frange(zero, zero);
+  r0.set_signbit (fp_prop::NO);
+  ASSERT_TRUE (r0.contains_p (zero));
+  ASSERT_FALSE (r0.contains_p (neg_zero));
+  r0.set_signbit (fp_prop::YES);
+  ASSERT_TRUE (r0.contains_p (neg_zero));
+  ASSERT_FALSE (r0.contains_p (zero));
+
+  // The intersection of zeros that differ in sign is the empty set.
+  r0 = frange (zero, zero);
+  r0.set_signbit (fp_prop::YES);
+  r1 = frange (zero, zero);
+  r1.set_signbit (fp_prop::NO);
+  r0.intersect (r1);
+  ASSERT_TRUE (r0.undefined_p ());
+
+  // The union of zeros that differ in sign is a zero with unknown sign.
+  r0 = frange (zero, zero);
+  r0.set_signbit (fp_prop::NO);
+  r1 = frange (zero, zero);
+  r1.set_signbit (fp_prop::YES);
+  r0.union_ (r1);
+  ASSERT_TRUE (r0.zero_p () && r0.get_signbit ().varying_p ());
+}
+
+static void
+range_tests_signbit ()
+{
+  frange r0, r1;
+
+  // Setting the signbit drops the range to [-INF, 0].
+  r0.set_varying (float_type_node);
+  r0.set_signbit (fp_prop::YES);
+  ASSERT_TRUE (real_isinf (&r0.lower_bound (), 1));
+  ASSERT_TRUE (real_iszero (&r0.upper_bound ()));
+
+  // Setting the signbit for [-5, 10] crops the range to [-5, 0] with
+  // the signbit property set.
+  r0 = frange_float ("-5", "10");
+  r0.set_signbit (fp_prop::YES);
+  ASSERT_TRUE (r0.get_signbit ().yes_p ());
+  r1 = frange_float ("-5", "0");
+  ASSERT_TRUE (real_identical (&r0.lower_bound (), &r1.lower_bound ()));
+  ASSERT_TRUE (real_identical (&r0.upper_bound (), &r1.upper_bound ()));
+
+  // Negative numbers should have the SIGNBIT set.
+  r0 = frange_float ("-5", "-1");
+  ASSERT_TRUE (r0.get_signbit ().yes_p ());
+  // Positive numbers should have the SIGNBIT clear.
+  r0 = frange_float ("1", "10");
+  ASSERT_TRUE (r0.get_signbit ().no_p ());
+  // Numbers containing zero should have an unknown SIGNBIT.
+  r0 = frange_float ("0", "10");
+  ASSERT_TRUE (r0.get_signbit ().varying_p ());
+  // Numbers spanning both positive and negative should have an
+  // unknown SIGNBIT.
+  r0 = frange_float ("-10", "10");
+  ASSERT_TRUE (r0.get_signbit ().varying_p ());
+  r0.set_varying (float_type_node);
+  ASSERT_TRUE (r0.get_signbit ().varying_p ());
+
+  // Ignore signbit changes when the sign bit is obviously known from
+  // the range.
+  r0 = frange_float ("5", "10");
+  r0.set_signbit (fp_prop::VARYING);
+  ASSERT_TRUE (r0.get_signbit ().no_p ());
+  r0 = frange_float ("-5", "-1");
+  r0.set_signbit (fp_prop::NO);
+  ASSERT_TRUE (r0.get_signbit ().yes_p ());
 }
 
 static void
@@ -3623,6 +3770,7 @@ range_tests_floats ()
   frange r0, r1;
 
   range_tests_nan ();
+  range_tests_signbit ();
 
   if (HONOR_SIGNED_ZEROS (float_type_node))
     range_tests_signed_zeros ();
diff --git a/gcc/value-range.h b/gcc/value-range.h
index f7f3665be07..3767bd17314 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -314,10 +314,12 @@ public:
   bool intersect (const frange_props &other);
   bool operator== (const frange_props &other) const;
   FP_PROP_ACCESSOR(nan)
+  FP_PROP_ACCESSOR(signbit)
 private:
   union {
     struct {
       unsigned char nan : 2;
+      unsigned char signbit : 2;
     } bits;
     unsigned char bytes;
   } u;
@@ -364,6 +366,8 @@ public:
   // Accessors for FP properties.
   fp_prop get_nan () const { return m_props.get_nan (); }
   void set_nan (fp_prop::kind f);
+  fp_prop get_signbit () const { return m_props.get_signbit (); }
+  void set_signbit (fp_prop::kind);
 private:
   void verify_range ();
   bool normalize_kind ();
-- 
2.37.1

[COMMITTED] Implement ranger folder for __builtin_signbit.

[Aldy Hernandez]

Now that we keep track of the signbit, we can use it to fold __builtin_signbit.

I am assuming I don't have try too hard to get the actual signbit
number and 1 will do.  Especially, since we're inconsistent in trunk whether
we fold the builtin or whether we calculate it at runtime.

abulafia:~$ cat a.c
float nzero = -0.0;

main(){
    printf("0x%x\n", __builtin_signbit(-0.0));
    printf("0x%x\n", __builtin_signbit(nzero));
}
abulafia:~$ gcc a.c -w && ./a.out
0x1
0x80000000

It is amazing that we've been failing to fold something as simple as
this:

	if (x > 5.0)
	  num = __builtin_signbit (x);

It does the right thing now :-P.

gcc/ChangeLog:

	* gimple-range-fold.cc
	(fold_using_range::range_of_builtin_int_call): Add case for
	CFN_BUILT_IN_SIGNBIT.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/vrp-float-signbit-1.c: New test.
---
 gcc/gimple-range-fold.cc                      | 20 +++++++++++++++++++
 .../gcc.dg/tree-ssa/vrp-float-signbit-1.c     | 12 +++++++++++
 2 files changed, 32 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-float-signbit-1.c

diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index b0b22106320..d8497fc9be7 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -1023,6 +1023,26 @@ fold_using_range::range_of_builtin_int_call (irange &r, gcall *call,
 	break;
       }
 
+    case CFN_BUILT_IN_SIGNBIT:
+      {
+	arg = gimple_call_arg (call, 0);
+	frange tmp;
+	if (src.get_operand (tmp, arg))
+	  {
+	    if (tmp.get_signbit ().varying_p ())
+	      return false;
+	    if (tmp.get_signbit ().yes_p ())
+	      {
+		tree one = build_one_cst (type);
+		r.set (one, one);
+	      }
+	    else
+	      r.set_zero (type);
+	    return true;
+	  }
+	break;
+      }
+
     case CFN_BUILT_IN_TOUPPER:
       {
 	arg = gimple_call_arg (call, 0);
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-signbit-1.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-signbit-1.c
new file mode 100644
index 00000000000..3fa783ec460
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-float-signbit-1.c
@@ -0,0 +1,12 @@
+// { dg-do compile }
+// { dg-options "-O2 -fdump-tree-evrp" }
+
+int num;
+
+void func(float x)
+{
+  if (x > 5.0)
+    num = __builtin_signbit (x);
+}
+
+// { dg-final { scan-tree-dump-times "num = 0;" 1 "evrp" } }
-- 
2.37.1

Re: [COMMITTED] Implement ranger folder for __builtin_signbit.

[Joseph Myers]

On Thu, 1 Sep 2022, Aldy Hernandez via Gcc-patches wrote:

> Now that we keep track of the signbit, we can use it to fold __builtin_signbit.
> 
> I am assuming I don't have try too hard to get the actual signbit
> number and 1 will do.  Especially, since we're inconsistent in trunk whether
> we fold the builtin or whether we calculate it at runtime.

The main thing to watch out for is cases where, in the abstract machine, 
there is a single call executed to __builtin_signbit, but after code 
transformations, some uses of the result of that call are optimized to use 
a 0 or 1 value and other uses end up using a runtime value - inconsistency 
between different calls is fine, inconsistency where only a single call is 
executed in the abstract machine isn't.  (Cf. bugs 102930, 85957, 93681, 
93806, 93682, for example; the test in bug 93806 comment 27 is the sort of 
thing to try.)

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: [COMMITTED] Implement ranger folder for __builtin_signbit.

[Aldy Hernandez]

On Thu, Sep 1, 2022 at 6:41 PM Joseph Myers <joseph@codesourcery.com> wrote:
>
> On Thu, 1 Sep 2022, Aldy Hernandez via Gcc-patches wrote:
>
> > Now that we keep track of the signbit, we can use it to fold __builtin_signbit.
> >
> > I am assuming I don't have try too hard to get the actual signbit
> > number and 1 will do.  Especially, since we're inconsistent in trunk whether
> > we fold the builtin or whether we calculate it at runtime.
>
> The main thing to watch out for is cases where, in the abstract machine,
> there is a single call executed to __builtin_signbit, but after code
> transformations, some uses of the result of that call are optimized to use
> a 0 or 1 value and other uses end up using a runtime value - inconsistency
> between different calls is fine, inconsistency where only a single call is
> executed in the abstract machine isn't.  (Cf. bugs 102930, 85957, 93681,
> 93806, 93682, for example; the test in bug 93806 comment 27 is the sort of
> thing to try.)

Can't we just be consistent with the runtime?  I'm happy to return
whatever value is appropriate for the architecture.  It doesn't have
to be 1.  Though ISTM that if we know the sign on one side of a
conditional, we should know the sign on the other side of the
conditional, so we should fold all uses of __builtin_signbit in that
case.  So maybe we're ok.

On the other hand, we could narrow the range to nonzero, which we can
model perfectly for integers (and __builtin_signbit returns one).  If
we take this approach it means we can't fold:

  if (x < -5.0)
    num = __builtin_signbit (x);

but we could fold:

  if (x > 5.0)
    num = __builtin_signbit (x);

since that's always 0.

And it also means we could fold conditional checks against zero/nonzero:

void func(float x)
{
  if (x < -5.0 && !__builtin_signbit (x))
    link_error ();
}

Whatever works for y'all.
Aldy

p.s. My head exploded after reading half of PR93806.  I should just go
back to integers.