frange class to represent floating point ranges

This implements a basic frange class to represent floating point
ranges.  Although it is meant to be a base for further development, it
is enough to handle relations and propagate NAN and other properties.

For ranger clients to become floating point aware, we still need the
range-op entries, which I will submit later this week.  Since those
entries require specialized FP knowledge, I will ask for a review from
the FP experts before committing.

Once range-op entries come live, all ranger clients that have been
converted to the type agnostic vrange API will become FP aware: evrp,
DOM, the threaders, loop-ch, etc.  (Still missing is loop unswitching,
as a lot of the int_range* temporaries should be Value_Range.  I don't
have enough cycles to convert loop unswitching, but could gladly give
guidance.  It should be straightforward for those familiar with the
code ;-)).

Samples things we handle:

* We can set the FP properties (!NAN, !INF, etc) at assignment from
  constants (and propagate them throughout the CFG):

  float z = 0.0;
  if (__builtin_isnan (z))
    link_error ();

* The relation oracle works in tandem with the FP ranges:

      if (x > y)
       ;
      else if (!__builtin_isnan (x) && !__builtin_isnan (y))
       {
         // If x and y are not NAN, the x <= y relationship holds, and the
         // following conditional can be folded away.
         if (x <= y)
           bar ();
       }

* We know the true side of all ordered conditionals (except !=)
  implies !NAN:

  if (x > y)
    {
      if (__builtin_isnan (x) || __builtin_isnan (y))
        link_error ();
    }

Range-ops also works correctly with -ffinite-math-only, and avoids
checking for NANs, etc.

I believe this is enough to get a fully fleshed out floating point
support for evrp and friends, but doing so is beyond my limited FP
knowledge.  For example, frange could be enhanced to track constant
endpoints, and we could track other FP properties aside from NAN.
Further discussion is gladly welcome.

Tested on x86-64 Linux.

gcc/ChangeLog:

	* value-range-pretty-print.cc (vrange_printer::visit): New.
	(vrange_printer::print_frange_prop): New.
	* value-range-pretty-print.h (class vrange_printer): Add visit and
	print_frange_prop.
	* value-range-storage.h (vrange_allocator::alloc_vrange): Handle frange.
	(vrange_allocator::alloc_frange): New.
	* value-range.cc (vrange::operator=): Handle frange.
	(vrange::operator==): Same.
	(frange::accept): New.
	(frange::set): New.
	(frange::normalize_kind): New.
	(frange::union_): New.
	(frange::intersect): New.
	(frange::operator=): New.
	(frange::operator==): New.
	(frange::supports_type_p): New.
	(frange::verify_range): New.
	* value-range.h (enum value_range_discriminator): Handle frange.
	(class fp_prop): New.
	(FP_PROP_ACCESSOR): New.
	(class frange_props): New.
	(FRANGE_PROP_ACCESSOR): New.
	(class frange): New.
	(Value_Range::init): Handle frange.
	(Value_Range::operator=): Same.
	(Value_Range::supports_type_p): Same.
	(frange_props::operator==): New.
	(frange_props::union_): New.
	(frange_props::intersect): New
	(frange::frange): New.
	(frange::type): New.
	(frange::set_varying): New.
	(frange::set_undefined): New.

1 files changed, 193 insertions, 1 deletions

diff --git a/gcc/value-range.h b/gcc/value-range.h
index 4af92fd..e43fbe3 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -45,6 +45,8 @@ enum value_range_discriminator
 {
   // Range holds an integer or pointer.
   VR_IRANGE,
+  // Floating point range.
+  VR_FRANGE,
   // Range holds an unsupported type.
   VR_UNKNOWN
 };
@@ -252,6 +254,117 @@ 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(inf)
+  FP_PROP_ACCESSOR(ninf)
+private:
+  union {
+    struct {
+      unsigned char nan : 2;
+      unsigned char inf : 2;
+      unsigned char ninf : 2;
+    } bits;
+    unsigned char bytes;
+  } u;
+};
+
+// Accessors for getting/setting all FP properties at once.
+
+#define FRANGE_PROP_ACCESSOR(NAME)				\
+  fp_prop get_##NAME () const { return m_props.get_##NAME (); }	\
+  void set_##NAME (fp_prop::kind f)				\
+  {								\
+    m_props.set_##NAME (f);					\
+    normalize_kind ();						\
+  }
+
+// A floating point range.
+
+class frange : public vrange
+{
+  friend class frange_storage_slot;
+public:
+  frange ();
+  frange (const frange &);
+  static bool supports_p (tree type)
+  {
+    // Disabled until floating point range-ops come live.
+    return 0 && SCALAR_FLOAT_TYPE_P (type);
+  }
+  virtual tree type () const override;
+  virtual void set (tree, tree, value_range_kind = VR_RANGE) override;
+  virtual void set_varying (tree type) override;
+  virtual void set_undefined () override;
+  virtual bool union_ (const vrange &) override;
+  virtual bool intersect (const vrange &) override;
+  virtual bool supports_type_p (tree type) const override;
+  virtual void accept (const vrange_visitor &v) const override;
+  frange& operator= (const frange &);
+  bool operator== (const frange &) const;
+  bool operator!= (const frange &r) const { return !(*this == r); }
+
+  // Each fp_prop can be accessed with get_PROP() and set_PROP().
+  FRANGE_PROP_ACCESSOR(nan)
+  FRANGE_PROP_ACCESSOR(inf)
+  FRANGE_PROP_ACCESSOR(ninf)
+private:
+  void verify_range ();
+  void normalize_kind ();
+
+  frange_props m_props;
+  tree m_type;
+};
+
 // is_a<> and as_a<> implementation for vrange.
 
 // Anything we haven't specialized is a hard fail.
@@ -297,10 +410,18 @@ is_a <irange> (vrange &v)
   return v.m_discriminator == VR_IRANGE;
 }
 
+template <>
+inline bool
+is_a <frange> (vrange &v)
+{
+  return v.m_discriminator == VR_FRANGE;
+}
+
 class vrange_visitor
 {
 public:
   virtual void visit (const irange &) const { }
+  virtual void visit (const frange &) const { }
   virtual void visit (const unsupported_range &) const { }
 };
 
@@ -360,6 +481,7 @@ private:
   unsupported_range m_unsupported;
   vrange *m_vrange;
   int_range_max m_irange;
+  frange m_frange;
 };
 
 inline
@@ -401,6 +523,8 @@ Value_Range::init (tree type)
 
   if (irange::supports_p (type))
     m_vrange = &m_irange;
+  else if (frange::supports_p (type))
+    m_vrange = &m_frange;
   else
     m_vrange = &m_unsupported;
 }
@@ -426,6 +550,11 @@ Value_Range::operator= (const vrange &r)
       m_irange = as_a <irange> (r);
       m_vrange = &m_irange;
     }
+  else if (is_a <frange> (r))
+    {
+      m_frange = as_a <frange> (r);
+      m_vrange = &m_frange;
+    }
   else
     gcc_unreachable ();
 
@@ -461,7 +590,7 @@ Value_Range::operator const vrange &() const
 inline bool
 Value_Range::supports_type_p (tree type)
 {
-  return irange::supports_p (type);
+  return irange::supports_p (type) || frange::supports_p (type);
 }
 
 // Returns true for an old-school value_range as described above.
@@ -881,6 +1010,69 @@ irange::normalize_kind ()
     }
 }
 
+
+// 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 ()
+{
+  m_discriminator = VR_FRANGE;
+  m_type = nullptr;
+  set_undefined ();
+}
+
+inline
+frange::frange (const frange &src)
+{
+  m_discriminator = VR_FRANGE;
+  *this = src;
+}
+
+inline tree
+frange::type () const
+{
+  return m_type;
+}
+
+inline void
+frange::set_varying (tree type)
+{
+  m_kind = VR_VARYING;
+  m_type = type;
+  m_props.set_varying ();
+}
+
+inline void
+frange::set_undefined ()
+{
+  m_kind = VR_UNDEFINED;
+  m_type = NULL;
+  m_props.set_undefined ();
+}
+
+
 // Return the maximum value for TYPE.
 
 inline tree