Rewrite NAN and sign handling in frange

The attatched patch rewrites the NAN and sign handling, dropping both
tristates in favor of a pair of boolean flags for NANs, and nothing at
all for signs.  The signs are tracked in the range itself, so now it's
possible to describe things like [-0.0, +0.0] +NAN, [+0, +0], [-5, +0],
[+0, 3] -NAN, etc.

Here is an example of the various ranges and how they are displayed:

    [frange] float VARYING NAN ;; Varying includes NAN
    [frange] UNDEFINED                      ;; Empty set as always
    [frange] float [] +-NAN                 ;; Unknown sign NAN
    [frange] float [] -NAN                  ;; -NAN
    [frange] float [] +NAN                  ;; +NAN
    [frange] float [-0.0, 0.0]              ;; All zeros.
    [frange] float [-0.0, -0.0] +-NAN       ;; -0 or NAN.
    [frange] float [-5.0e+0, -1.0e+0] +NAN  ;; [-5, -1] or +NAN
    [frange] float [-5.0e+0, -0.0] +-NAN    ;; [-5, -0] or NAN
    [frange] float [-5.0e+0, -0.0]          ;; [-5, -0]
    [frange] float [5.0e+0, 1.0e+1]         ;; [5, 10]

Notice the NAN signs are decoupled from the range, so we can represent
a negative range with a positive NAN.  For this range,
frange::signbit_p() would return false, as only when the signs of the
NANs and range agree can we be certain.

There is no longer any pessimization of ranges for intersects
involving NANs.  Also, union and intersect work with signed zeros:

//   [-0,  x] U [+0,  x] => [-0,  x]
//   [ x, -0] U [ x, +0] => [ x, +0]
//   [-0,  x] ^ [+0,  x] => [+0,  x]
//   [ x, -0] ^ [ x, +0] => [ x, -0]

The special casing for signed zeros in the singleton code is gone in
favor of just making sure the signs in the range agree, that is
[-0, -0] for example.

I have removed the idea that a known NAN is a "range", so a NAN is no
longer in the endpoints itself.  Requesting the bound of a known NAN
is a hard fail.  For that matter, we don't store the actual NAN in the
range.  The only information we have are the set of boolean flags.
This way we make sure nothing seeps into the frange.  This also means
it's explicit that we don't track anything but the sign in NANs.  We
can revisit this if we desire to track signalling or whatever
concoction y'all can imagine.

Regstrapped with mpfr tests on x86-64 and ppc64le Linux.  Selftests
were also run with -ffinite-math-only on x86-64.

At Jakub's suggestion, I built lapack with associated tests.  They
pass on x86-64 and ppc64le Linux with no regressions from mainline.
As a sanity check, I also ran them for -ffinite-math-only on x86 which
(as expected) returned:

	NaN arithmetic did not perform per the ieee spec

Otherwise, all tests pass for -ffinite-math-only.

gcc/ChangeLog:

	* range-op-float.cc (frange_add_zeros): Replace set_signbit with
	union of zero.
	* value-query.cc (range_query::get_tree_range): Remove set_signbit
	use.
	* value-range-pretty-print.cc (vrange_printer::print_frange_prop):
	Remove.
	(vrange_printer::print_frange_nan): New.
	* value-range-pretty-print.h (print_frange_prop): Remove.
	(print_frange_nan): New.
	* value-range-storage.cc (frange_storage_slot::set_frange): Set
	kind and NAN fields.
	(frange_storage_slot::get_frange): Restore kind and NAN fields.
	* value-range-storage.h (class frange_storage_slot): Add kind and
	NAN fields.
	* value-range.cc (frange::update_nan): Remove.
	(frange::set_signbit): Remove.
	(frange::set): Adjust for NAN fields.
	(frange::normalize_kind): Remove m_props.
	(frange::combine_zeros): New.
	(frange::union_nans): New.
	(frange::union_): Handle new NAN fields.
	(frange::intersect_nans): New.
	(frange::intersect): Handle new NAN fields.
	(frange::operator=): Same.
	(frange::operator==): Same.
	(frange::contains_p): Same.
	(frange::singleton_p): Remove special case for signed zeros.
	(frange::verify_range): Adjust for new NAN fields.
	(frange::set_zero): Handle signed zeros.
	(frange::set_nonnegative): Same.
	(range_tests_nan): Adjust tests.
	(range_tests_signed_zeros): Same.
	(range_tests_signbit): Same.
	(range_tests_floats): Same.
	* value-range.h (class fp_prop): Remove.
	(FP_PROP_ACCESSOR): Remove.
	(class frange_props): Remove
	(frange::lower_bound): NANs don't have endpoints.
	(frange::upper_bound): Same.
	(frange_props::operator==): Remove.
	(frange_props::union_): Remove.
	(frange_props::intersect): Remove.
	(frange::update_nan): New.
	(frange::clear_nan): New.
	(frange::undefined_p): New.
	(frange::set_nan): New.
	(frange::known_finite): Adjust for new NAN representation.
	(frange::maybe_isnan): Same.
	(frange::known_isnan): Same.
	(frange::signbit_p): Same.
	* gimple-range-fold.cc (range_of_builtin_int_call): Rename
	known_signbit_p into signbit_p.

1 files changed, 101 insertions, 130 deletions

diff --git a/gcc/value-range.h b/gcc/value-range.h
index 4392de8..3a401f3 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -35,6 +35,8 @@ enum value_range_kind
   VR_RANGE,
   /* Range is ~[MIN, MAX].  */
   VR_ANTI_RANGE,
+  /* Range is a NAN.  */
+  VR_NAN,
   /* Range is a nice guy.  */
   VR_LAST
 };
@@ -263,69 +265,10 @@ public:
   virtual void accept (const vrange_visitor &v) const override;
 };
 
-// Floating point property to represent possible values of a NAN, INF, etc.
-
-class fp_prop
-{
-public:
-  enum kind {
-    UNDEFINED	= 0x0,		// Prop is impossible.
-    YES		= 0x1,		// Prop is definitely set.
-    NO		= 0x2,		// Prop is definitely not set.
-    VARYING	= (YES | NO)	// Prop may hold.
-  };
-  fp_prop (kind f) : m_kind (f) { }
-  bool varying_p () const { return m_kind == VARYING; }
-  bool undefined_p () const { return m_kind == UNDEFINED; }
-  bool yes_p () const { return m_kind == YES; }
-  bool no_p () const { return m_kind == NO; }
-private:
-  unsigned char m_kind : 2;
-};
-
-// Accessors for individual FP properties.
-
-#define FP_PROP_ACCESSOR(NAME) \
-  void NAME##_set_varying () { u.bits.NAME = fp_prop::VARYING; }	\
-  void NAME##_set_yes () { u.bits.NAME = fp_prop::YES; }	\
-  void NAME##_set_no () { u.bits.NAME = fp_prop::NO; }	\
-  bool NAME##_varying_p () const { return u.bits.NAME == fp_prop::VARYING; } \
-  bool NAME##_undefined_p () const { return u.bits.NAME == fp_prop::UNDEFINED; } \
-  bool NAME##_yes_p () const { return u.bits.NAME == fp_prop::YES; }	\
-  bool NAME##_no_p () const { return u.bits.NAME == fp_prop::NO; } \
-  fp_prop get_##NAME () const				   \
-  { return fp_prop ((fp_prop::kind) u.bits.NAME); } \
-  void set_##NAME (fp_prop::kind f) { u.bits.NAME = f; }
-
-// Aggregate of all the FP properties in an frange packed into one
-// structure to save space.  Using explicit fp_prop's in the frange,
-// would take one byte per property because of padding.  Instead, we
-// can save all properties into one byte.
-
-class frange_props
-{
-public:
-  frange_props () { set_varying (); }
-  void set_varying () { u.bytes = 0xff; }
-  void set_undefined () { u.bytes = 0; }
-  bool varying_p () { return u.bytes == 0xff; }
-  bool undefined_p () { return u.bytes == 0; }
-  bool union_ (const frange_props &other);
-  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;
-};
-
 // A floating point range.
+//
+// The representation is a type with a couple of endpoints, unioned
+// with the set of { -NAN, +Nan }.
 
 class frange : public vrange
 {
@@ -349,6 +292,7 @@ public:
   void set (tree type, const REAL_VALUE_TYPE &, const REAL_VALUE_TYPE &,
 	    value_range_kind = VR_RANGE);
   void set_nan (tree type);
+  void set_nan (tree type, bool sign);
   virtual void set_varying (tree type) override;
   virtual void set_undefined () override;
   virtual bool union_ (const vrange &) override;
@@ -367,42 +311,41 @@ public:
   bool operator!= (const frange &r) const { return !(*this == r); }
   const REAL_VALUE_TYPE &lower_bound () const;
   const REAL_VALUE_TYPE &upper_bound () const;
+  void update_nan ();
+  void clear_nan ();
 
   // fpclassify like API
-  bool known_finite () const;
-  bool maybe_inf () const;
-  bool known_inf () const;
-  bool maybe_nan () const;
-  bool known_nan () const;
-  bool known_signbit (bool &signbit) const;
-
-  // Accessors for FP properties.
-  void update_nan (fp_prop::kind f);
-  void clear_nan () { update_nan (fp_prop::NO); }
-  void set_signbit (fp_prop::kind);
+  bool known_isfinite () const;
+  bool known_isnan () const;
+  bool known_isinf () const;
+  bool maybe_isnan () const;
+  bool maybe_isinf () const;
+  bool signbit_p (bool &signbit) const;
 private:
-  fp_prop get_nan () const { return m_props.get_nan (); }
-  fp_prop get_signbit () const { return m_props.get_signbit (); }
   void verify_range ();
   bool normalize_kind ();
+  bool union_nans (const frange &);
+  bool intersect_nans (const frange &);
+  bool combine_zeros (const frange &, bool union_p);
 
-  frange_props m_props;
   tree m_type;
   REAL_VALUE_TYPE m_min;
   REAL_VALUE_TYPE m_max;
+  bool m_pos_nan;
+  bool m_neg_nan;
 };
 
 inline const REAL_VALUE_TYPE &
 frange::lower_bound () const
 {
-  gcc_checking_assert (!undefined_p ());
+  gcc_checking_assert (!undefined_p () && !known_isnan ());
   return m_min;
 }
 
 inline const REAL_VALUE_TYPE &
 frange::upper_bound () const
 {
-  gcc_checking_assert (!undefined_p ());
+  gcc_checking_assert (!undefined_p () && !known_isnan ());
   return m_max;
 }
 
@@ -1082,30 +1025,6 @@ vrp_val_min (const_tree type)
   return NULL_TREE;
 }
 
-// Supporting methods for frange.
-
-inline bool
-frange_props::operator== (const frange_props &other) const
-{
-  return u.bytes == other.u.bytes;
-}
-
-inline bool
-frange_props::union_ (const frange_props &other)
-{
-  unsigned char saved = u.bytes;
-  u.bytes |= other.u.bytes;
-  return u.bytes != saved;
-}
-
-inline bool
-frange_props::intersect (const frange_props &other)
-{
-  unsigned char saved = u.bytes;
-  u.bytes &= other.u.bytes;
-  return u.bytes != saved;
-}
-
 inline
 frange::frange ()
 {
@@ -1154,15 +1073,42 @@ frange::set_varying (tree type)
   m_type = type;
   m_min = dconstninf;
   m_max = dconstinf;
-  m_props.set_varying ();
+  m_pos_nan = true;
+  m_neg_nan = true;
 }
 
 inline void
 frange::set_undefined ()
 {
   m_kind = VR_UNDEFINED;
-  m_type = NULL;
-  m_props.set_undefined ();
+  if (flag_checking)
+    verify_range ();
+}
+
+// Set the NAN bit and adjust the range.
+
+inline void
+frange::update_nan ()
+{
+  gcc_checking_assert (!undefined_p ());
+  m_pos_nan = true;
+  m_neg_nan = true;
+  normalize_kind ();
+  if (flag_checking)
+    verify_range ();
+}
+
+// Clear the NAN bit and adjust the range.
+
+inline void
+frange::clear_nan ()
+{
+  gcc_checking_assert (!undefined_p ());
+  m_pos_nan = false;
+  m_neg_nan = false;
+  normalize_kind ();
+  if (flag_checking)
+    verify_range ();
 }
 
 // Set R to maximum representable value for TYPE.
@@ -1186,19 +1132,28 @@ real_min_representable (REAL_VALUE_TYPE *r, tree type)
   *r = real_value_negate (r);
 }
 
-// Build a NAN of type TYPE.
+// Build a signless NAN of type TYPE.
 
 inline void
 frange::set_nan (tree type)
 {
-  REAL_VALUE_TYPE r;
-  gcc_assert (real_nan (&r, "", 1, TYPE_MODE (type)));
-  m_kind = VR_RANGE;
+  m_kind = VR_NAN;
   m_type = type;
-  m_min = r;
-  m_max = r;
-  m_props.set_varying ();
-  m_props.nan_set_yes ();
+  m_pos_nan = true;
+  m_neg_nan = true;
+  if (flag_checking)
+    verify_range ();
+}
+
+// Build a NAN of type TYPE with SIGN.
+
+inline void
+frange::set_nan (tree type, bool sign)
+{
+  m_kind = VR_NAN;
+  m_type = type;
+  m_neg_nan = sign;
+  m_pos_nan = !sign;
   if (flag_checking)
     verify_range ();
 }
@@ -1206,21 +1161,19 @@ frange::set_nan (tree type)
 // Return TRUE if range is known to be finite.
 
 inline bool
-frange::known_finite () const
+frange::known_isfinite () const
 {
   if (undefined_p () || varying_p () || m_kind == VR_ANTI_RANGE)
     return false;
-  return (!real_isnan (&m_min)
-	  && !real_isinf (&m_min)
-	  && !real_isinf (&m_max));
+  return (!maybe_isnan () && !real_isinf (&m_min) && !real_isinf (&m_max));
 }
 
 // Return TRUE if range may be infinite.
 
 inline bool
-frange::maybe_inf () const
+frange::maybe_isinf () const
 {
-  if (undefined_p () || m_kind == VR_ANTI_RANGE)
+  if (undefined_p () || m_kind == VR_ANTI_RANGE || m_kind == VR_NAN)
     return false;
   if (varying_p ())
     return true;
@@ -1230,7 +1183,7 @@ frange::maybe_inf () const
 // Return TRUE if range is known to be the [-INF,-INF] or [+INF,+INF].
 
 inline bool
-frange::known_inf () const
+frange::known_isinf () const
 {
   return (m_kind == VR_RANGE
 	  && real_identical (&m_min, &m_max)
@@ -1240,32 +1193,50 @@ frange::known_inf () const
 // Return TRUE if range is possibly a NAN.
 
 inline bool
-frange::maybe_nan () const
+frange::maybe_isnan () const
 {
-  return !get_nan ().no_p ();
+  return m_pos_nan || m_neg_nan;
 }
 
 // Return TRUE if range is a +NAN or -NAN.
 
 inline bool
-frange::known_nan () const
+frange::known_isnan () const
 {
-  return get_nan ().yes_p ();
+  return m_kind == VR_NAN;
 }
 
 // If the signbit for the range is known, set it in SIGNBIT and return
 // TRUE.
 
 inline bool
-frange::known_signbit (bool &signbit) const
+frange::signbit_p (bool &signbit) const
 {
-  // FIXME: Signed NANs are not supported yet.
-  if (maybe_nan ())
+  if (undefined_p ())
     return false;
-  if (get_signbit ().varying_p ())
+
+  // NAN with unknown sign.
+  if (m_pos_nan && m_neg_nan)
     return false;
-  signbit = get_signbit ().yes_p ();
-  return true;
+  // No NAN.
+  if (!m_pos_nan && !m_neg_nan)
+    {
+      if (m_min.sign == m_max.sign)
+	{
+	  signbit = m_min.sign;
+	  return true;
+	}
+      return false;
+    }
+  // NAN with known sign.
+  bool nan_sign = m_neg_nan;
+  if (known_isnan ()
+      || (nan_sign == m_min.sign && nan_sign == m_max.sign))
+    {
+      signbit = nan_sign;
+      return true;
+    }
+  return false;
 }
 
 #endif // GCC_VALUE_RANGE_H