@@ -112,6 +112,31 @@ vrange_printer::visit (const irange &r) const
print_irange_bitmasks (pp, r.m_bitmask);
}
+void
+vrange_printer::visit (const prange &r) const
+{
+ pp_string (pp, "[prange] ");
+ if (r.undefined_p ())
+ {
+ pp_string (pp, "UNDEFINED");
+ return;
+ }
+ dump_generic_node (pp, r.type (), 0, TDF_NONE | TDF_NOUID, false);
+ pp_character (pp, ' ');
+ if (r.varying_p ())
+ {
+ pp_string (pp, "VARYING");
+ return;
+ }
+
+ pp_character (pp, '[');
+ print_int_bound (pp, r.lower_bound (), r.type ());
+ pp_string (pp, ", ");
+ print_int_bound (pp, r.upper_bound (), r.type ());
+ pp_character (pp, ']');
+ print_irange_bitmasks (pp, r.m_bitmask);
+}
+
void
vrange_printer::print_real_value (tree type, const REAL_VALUE_TYPE &r) const
{
@@ -27,6 +27,7 @@ public:
vrange_printer (pretty_printer *pp_) : pp (pp_) { }
void visit (const unsupported_range &) const override;
void visit (const irange &) const override;
+ void visit (const prange &) const override;
void visit (const frange &) const override;
private:
void print_frange_nan (const frange &) const;
@@ -251,6 +251,8 @@ vrange::operator= (const vrange &src)
{
if (is_a <irange> (src))
as_a <irange> (*this) = as_a <irange> (src);
+ else if (is_a <prange> (src))
+ as_a <prange> (*this) = as_a <prange> (src);
else if (is_a <frange> (src))
as_a <frange> (*this) = as_a <frange> (src);
else
@@ -268,6 +270,8 @@ vrange::operator== (const vrange &src) const
{
if (is_a <irange> (src))
return as_a <irange> (*this) == as_a <irange> (src);
+ if (is_a <prange> (src))
+ return as_a <prange> (*this) == as_a <prange> (src);
if (is_a <frange> (src))
return as_a <frange> (*this) == as_a <frange> (src);
gcc_unreachable ();
@@ -397,6 +401,294 @@ irange::set_nonnegative (tree type)
wi::to_wide (TYPE_MAX_VALUE (type)));
}
+// Prange implementation.
+
+void
+prange::accept (const vrange_visitor &v) const
+{
+ v.visit (*this);
+}
+
+void
+prange::set_nonnegative (tree type)
+{
+ set (type,
+ wi::zero (TYPE_PRECISION (type)),
+ wi::max_value (TYPE_PRECISION (type), UNSIGNED));
+}
+
+void
+prange::set (tree min, tree max, value_range_kind kind)
+{
+ return set (TREE_TYPE (min), wi::to_wide (min), wi::to_wide (max), kind);
+}
+
+void
+prange::set (tree type, const wide_int &min, const wide_int &max,
+ value_range_kind kind)
+{
+ if (kind == VR_UNDEFINED)
+ {
+ set_undefined ();
+ return;
+ }
+ if (kind == VR_VARYING)
+ {
+ set_varying (type);
+ return;
+ }
+ if (kind == VR_ANTI_RANGE)
+ {
+ gcc_checking_assert (min == 0 && max == 0);
+ set_nonzero (type);
+ return;
+ }
+ m_type = type;
+ m_min = min;
+ m_max = max;
+ if (m_min == 0 && m_max == -1)
+ {
+ m_kind = VR_VARYING;
+ m_bitmask.set_unknown (TYPE_PRECISION (type));
+ if (flag_checking)
+ verify_range ();
+ return;
+ }
+
+ m_kind = VR_RANGE;
+ m_bitmask = get_bitmask_from_range (type, min, max);
+ if (flag_checking)
+ verify_range ();
+}
+
+bool
+prange::contains_p (const wide_int &w) const
+{
+ if (undefined_p ())
+ return false;
+
+ if (varying_p ())
+ return true;
+
+ return (wi::le_p (lower_bound (), w, UNSIGNED)
+ && wi::ge_p (upper_bound (), w, UNSIGNED));
+}
+
+bool
+prange::singleton_p (tree *result) const
+{
+ if (m_kind == VR_RANGE && lower_bound () == upper_bound ())
+ {
+ if (result)
+ *result = wide_int_to_tree (type (), m_min);
+ return true;
+ }
+ return false;
+}
+
+tree
+prange::lbound () const
+{
+ return wide_int_to_tree (type (), m_min);
+}
+
+tree
+prange::ubound () const
+{
+ return wide_int_to_tree (type (), m_max);
+}
+
+bool
+prange::union_ (const vrange &v)
+{
+ const prange &r = as_a <prange> (v);
+
+ if (r.undefined_p ())
+ return false;
+ if (undefined_p ())
+ {
+ *this = r;
+ if (flag_checking)
+ verify_range ();
+ return true;
+ }
+ if (varying_p ())
+ return false;
+ if (r.varying_p ())
+ {
+ set_varying (type ());
+ return true;
+ }
+
+ wide_int new_lb = wi::min (r.lower_bound (), lower_bound (), UNSIGNED);
+ wide_int new_ub = wi::max (r.upper_bound (), upper_bound (), UNSIGNED);
+ prange new_range (type (), new_lb, new_ub);
+ new_range.m_bitmask.union_ (m_bitmask);
+ new_range.m_bitmask.union_ (r.m_bitmask);
+ if (new_range.varying_compatible_p ())
+ {
+ set_varying (type ());
+ return true;
+ }
+ if (flag_checking)
+ new_range.verify_range ();
+ if (new_range == *this)
+ return false;
+ *this = new_range;
+ return true;
+}
+
+bool
+prange::intersect (const vrange &v)
+{
+ const prange &r = as_a <prange> (v);
+ gcc_checking_assert (undefined_p () || r.undefined_p ()
+ || range_compatible_p (type (), r.type ()));
+
+ if (undefined_p ())
+ return false;
+ if (r.undefined_p ())
+ {
+ set_undefined ();
+ return true;
+ }
+ if (r.varying_p ())
+ return false;
+ if (varying_p ())
+ {
+ *this = r;
+ return true;
+ }
+
+ prange save = *this;
+ m_min = wi::max (r.lower_bound (), lower_bound (), UNSIGNED);
+ m_max = wi::min (r.upper_bound (), upper_bound (), UNSIGNED);
+ if (wi::gt_p (m_min, m_max, UNSIGNED))
+ {
+ set_undefined ();
+ return true;
+ }
+
+ // Intersect all bitmasks: the old one, the new one, and the other operand's.
+ irange_bitmask new_bitmask = get_bitmask_from_range (m_type, m_min, m_max);
+ m_bitmask.intersect (new_bitmask);
+ m_bitmask.intersect (r.m_bitmask);
+
+ if (flag_checking)
+ verify_range ();
+ if (*this == save)
+ return false;
+ return true;
+}
+
+prange &
+prange::operator= (const prange &src)
+{
+ m_type = src.m_type;
+ m_kind = src.m_kind;
+ m_min = src.m_min;
+ m_max = src.m_max;
+ m_bitmask = src.m_bitmask;
+ if (flag_checking)
+ verify_range ();
+ return *this;
+}
+
+bool
+prange::operator== (const prange &src) const
+{
+ if (m_kind == src.m_kind)
+ {
+ if (undefined_p ())
+ return true;
+
+ if (varying_p ())
+ return types_compatible_p (type (), src.type ());
+
+ return (m_min == src.m_min && m_max == src.m_max
+ && m_bitmask == src.m_bitmask);
+ }
+ return false;
+}
+
+void
+prange::invert ()
+{
+ gcc_checking_assert (!undefined_p () && !varying_p ());
+
+ wide_int new_lb, new_ub;
+ unsigned prec = TYPE_PRECISION (type ());
+ wide_int type_min = wi::zero (prec);
+ wide_int type_max = wi::max_value (prec, UNSIGNED);
+ wi::overflow_type ovf;
+
+ if (lower_bound () == type_min)
+ {
+ new_lb = wi::add (upper_bound (), 1, UNSIGNED, &ovf);
+ if (ovf)
+ new_lb = type_min;
+ new_ub = type_max;
+ set (type (), new_lb, new_ub);
+ }
+ else if (upper_bound () == type_max)
+ {
+ wi::overflow_type ovf;
+ new_lb = type_min;
+ new_ub = wi::sub (lower_bound (), 1, UNSIGNED, &ovf);
+ if (ovf)
+ new_ub = type_max;
+ set (type (), new_lb, new_ub);
+ }
+ else
+ set_varying (type ());
+}
+
+void
+prange::verify_range () const
+{
+ gcc_checking_assert (m_discriminator == VR_PRANGE);
+
+ if (m_kind == VR_UNDEFINED)
+ return;
+
+ gcc_checking_assert (supports_p (type ()));
+
+ if (m_kind == VR_VARYING)
+ {
+ gcc_checking_assert (varying_compatible_p ());
+ return;
+ }
+ gcc_checking_assert (!varying_compatible_p ());
+ gcc_checking_assert (m_kind == VR_RANGE);
+}
+
+void
+prange::update_bitmask (const irange_bitmask &bm)
+{
+ gcc_checking_assert (!undefined_p ());
+
+ // If all the bits are known, this is a singleton.
+ if (bm.mask () == 0)
+ {
+ set (type (), m_bitmask.value (), m_bitmask.value ());
+ return;
+ }
+
+ // Drop VARYINGs with known bits to a plain range.
+ if (m_kind == VR_VARYING && !bm.unknown_p ())
+ m_kind = VR_RANGE;
+
+ m_bitmask = bm;
+ if (varying_compatible_p ())
+ m_kind = VR_VARYING;
+
+ if (flag_checking)
+ verify_range ();
+}
+
+
+// Frange implementation.
+
void
frange::accept (const vrange_visitor &v) const
{
@@ -2542,11 +2834,12 @@ range_tests_misc ()
// Make sure NULL and non-NULL of pointer types work, and that
// inverses of them are consistent.
tree voidp = build_pointer_type (void_type_node);
- r0.set_zero (voidp);
- r1 = r0;
- r0.invert ();
- r0.invert ();
- ASSERT_TRUE (r0 == r1);
+ prange p0;
+ p0.set_zero (voidp);
+ prange p1 = p0;
+ p0.invert ();
+ p0.invert ();
+ ASSERT_TRUE (p0 == p1);
// [10,20] U [15, 30] => [10, 30].
r0 = range_int (10, 20);
@@ -47,6 +47,8 @@ enum value_range_discriminator
{
// Range holds an integer or pointer.
VR_IRANGE,
+ // Pointer range.
+ VR_PRANGE,
// Floating point range.
VR_FRANGE,
// Range holds an unsupported type.
@@ -380,32 +382,49 @@ private:
class prange : public vrange
{
+ friend class prange_storage;
+ friend class vrange_printer;
public:
- static bool supports_p (const_tree) { return false; }
- virtual bool supports_type_p (const_tree) const final override { return false; }
- virtual void accept (const vrange_visitor &) const final override {}
- virtual void set_undefined () final override {}
- virtual void set_varying (tree) final override {}
- virtual void set_nonzero (tree) final override {}
- virtual void set_zero (tree) final override;
- virtual void set_nonnegative (tree) final override {}
- virtual bool contains_p (tree) const final override { return false; }
- virtual bool fits_p (const vrange &) const final override { return false; }
- virtual bool singleton_p (tree * = NULL) const final override { return false; }
- virtual bool zero_p () const final override { return false; }
- virtual bool nonzero_p () const final override { return false; }
- virtual void set (tree, tree, value_range_kind = VR_RANGE) final override {}
- virtual tree type () const final override { return NULL; }
- virtual bool union_ (const vrange &) final override { return false; }
- virtual bool intersect (const vrange &) final override { return false; }
- virtual tree lbound () const final override { return NULL; }
- virtual tree ubound () const final override { return NULL; }
-
+ prange ();
+ prange (const prange &);
+ prange (tree type);
+ prange (tree type, const wide_int &, const wide_int &,
+ value_range_kind = VR_RANGE);
+ static bool supports_p (const_tree type);
+ virtual bool supports_type_p (const_tree type) const final override;
+ virtual void accept (const vrange_visitor &v) const final override;
+ virtual void set_undefined () final override;
+ virtual void set_varying (tree type) final override;
+ virtual void set_nonzero (tree type) final override;
+ virtual void set_zero (tree type) final override;
+ virtual void set_nonnegative (tree type) final override;
+ virtual bool contains_p (tree cst) const final override;
+ virtual bool fits_p (const vrange &v) const final override;
+ virtual bool singleton_p (tree *result = NULL) const final override;
+ virtual bool zero_p () const final override;
+ virtual bool nonzero_p () const final override;
+ virtual void set (tree, tree, value_range_kind = VR_RANGE) final override;
+ virtual tree type () const final override;
+ virtual bool union_ (const vrange &v) final override;
+ virtual bool intersect (const vrange &v) final override;
+ virtual tree lbound () const final override;
+ virtual tree ubound () const final override;
+
+ prange& operator= (const prange &);
+ bool operator== (const prange &) const;
+ void set (tree type, const wide_int &, const wide_int &,
+ value_range_kind = VR_RANGE);
+ void invert ();
+ bool contains_p (const wide_int &) const;
wide_int lower_bound () const;
wide_int upper_bound () const;
+ void verify_range () const;
irange_bitmask get_bitmask () const final override;
- void update_bitmask (const irange_bitmask &) final override {}
-private:
+ void update_bitmask (const irange_bitmask &) final override;
+protected:
+ bool varying_compatible_p () const;
+
+ tree m_type;
wide_int m_min;
wide_int m_max;
irange_bitmask m_bitmask;
@@ -656,6 +675,13 @@ is_a <irange> (vrange &v)
return v.m_discriminator == VR_IRANGE;
}
+template <>
+inline bool
+is_a <prange> (vrange &v)
+{
+ return v.m_discriminator == VR_PRANGE;
+}
+
template <>
inline bool
is_a <frange> (vrange &v)
@@ -708,6 +734,7 @@ class vrange_visitor
{
public:
virtual void visit (const irange &) const { }
+ virtual void visit (const prange &) const { }
virtual void visit (const frange &) const { }
virtual void visit (const unsupported_range &) const { }
};
@@ -775,6 +802,7 @@ private:
vrange *m_vrange;
// The buffer must be at least the size of the largest range.
static_assert (sizeof (int_range_max) > sizeof (frange), "");
+ static_assert (sizeof (int_range_max) > sizeof (prange), "");
char m_buffer[sizeof (int_range_max)];
};
@@ -850,6 +878,8 @@ Value_Range::init (tree type)
if (irange::supports_p (type))
m_vrange = new (&m_buffer) int_range_max ();
+ else if (prange::supports_p (type))
+ m_vrange = new (&m_buffer) prange ();
else if (frange::supports_p (type))
m_vrange = new (&m_buffer) frange ();
else
@@ -863,6 +893,8 @@ Value_Range::init (const vrange &r)
{
if (is_a <irange> (r))
m_vrange = new (&m_buffer) int_range_max (as_a <irange> (r));
+ else if (is_a <prange> (r))
+ m_vrange = new (&m_buffer) prange (as_a <prange> (r));
else if (is_a <frange> (r))
m_vrange = new (&m_buffer) frange (as_a <frange> (r));
else
@@ -920,7 +952,9 @@ Value_Range::operator const vrange &() const
inline bool
Value_Range::supports_type_p (const_tree type)
{
- return irange::supports_p (type) || frange::supports_p (type);
+ return irange::supports_p (type)
+ || prange::supports_p (type)
+ || frange::supports_p (type);
}
extern value_range_kind get_legacy_range (const vrange &, tree &min, tree &max);
@@ -1220,32 +1254,151 @@ irange_val_max (const_tree type)
return wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
}
+inline
+prange::prange ()
+ : vrange (VR_PRANGE)
+{
+ set_undefined ();
+}
+
+inline
+prange::prange (const prange &r)
+ : vrange (VR_PRANGE)
+{
+ *this = r;
+}
+
+inline
+prange::prange (tree type)
+ : vrange (VR_PRANGE)
+{
+ set_varying (type);
+}
+
+inline
+prange::prange (tree type, const wide_int &lb, const wide_int &ub,
+ value_range_kind kind)
+ : vrange (VR_PRANGE)
+{
+ set (type, lb, ub, kind);
+}
+
+inline bool
+prange::supports_p (const_tree type)
+{
+ return POINTER_TYPE_P (type);
+}
+
+inline bool
+prange::supports_type_p (const_tree type) const
+{
+ return POINTER_TYPE_P (type);
+}
+
+inline void
+prange::set_undefined ()
+{
+ m_kind = VR_UNDEFINED;
+}
+
+inline void
+prange::set_varying (tree type)
+{
+ m_kind = VR_VARYING;
+ m_type = type;
+ m_min = wi::zero (TYPE_PRECISION (type));
+ m_max = wi::max_value (TYPE_PRECISION (type), UNSIGNED);
+ m_bitmask.set_unknown (TYPE_PRECISION (type));
+
+ if (flag_checking)
+ verify_range ();
+}
+
+inline void
+prange::set_nonzero (tree type)
+{
+ m_kind = VR_RANGE;
+ m_type = type;
+ m_min = wi::one (TYPE_PRECISION (type));
+ m_max = wi::max_value (TYPE_PRECISION (type), UNSIGNED);
+ m_bitmask.set_unknown (TYPE_PRECISION (type));
+
+ if (flag_checking)
+ verify_range ();
+}
+
inline void
prange::set_zero (tree type)
{
+ m_kind = VR_RANGE;
+ m_type = type;
wide_int zero = wi::zero (TYPE_PRECISION (type));
m_min = m_max = zero;
m_bitmask = irange_bitmask (zero, zero);
+
+ if (flag_checking)
+ verify_range ();
+}
+
+inline bool
+prange::contains_p (tree cst) const
+{
+ return contains_p (wi::to_wide (cst));
+}
+
+inline bool
+prange::zero_p () const
+{
+ return m_kind == VR_RANGE && m_min == 0 && m_max == 0;
+}
+
+inline bool
+prange::nonzero_p () const
+{
+ return m_kind == VR_RANGE && m_min == 1 && m_max == -1;
+}
+
+inline tree
+prange::type () const
+{
+ gcc_checking_assert (!undefined_p ());
+ return m_type;
}
inline wide_int
prange::lower_bound () const
{
+ gcc_checking_assert (!undefined_p ());
return m_min;
}
inline wide_int
prange::upper_bound () const
{
+ gcc_checking_assert (!undefined_p ());
return m_max;
}
+inline bool
+prange::varying_compatible_p () const
+{
+ return (!undefined_p ()
+ && m_min == 0 && m_max == -1 && get_bitmask ().unknown_p ());
+}
+
inline irange_bitmask
prange::get_bitmask () const
{
return m_bitmask;
}
+inline bool
+prange::fits_p (const vrange &) const
+{
+ return true;
+}
+
+
inline
frange::frange ()
: vrange (VR_FRANGE)
This provides a bare prange class with bounds and bitmasks. It will be a drop-in replacement for pointer ranges, so we can pull their support from irange. The range-op code will be contributed as a follow-up. The code is disabled by default, as irange::supports_p still accepts pointers: inline bool irange::supports_p (const_tree type) { return INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type); } Once the prange operators are implemented in range-ops, pointer support will be removed from irange to activate pranges. gcc/ChangeLog: * value-range-pretty-print.cc (vrange_printer::visit): New. * value-range-pretty-print.h: Declare prange visit() method. * value-range.cc (vrange::operator=): Add prange support. (vrange::operator==): Same. (prange::accept): New. (prange::set_nonnegative): New. (prange::set): New. (prange::contains_p): New. (prange::singleton_p): New. (prange::lbound): New. (prange::ubound): New. (prange::union_): New. (prange::intersect): New. (prange::operator=): New. (prange::operator==): New. (prange::invert): New. (prange::verify_range): New. (prange::update_bitmask): New. (range_tests_misc): Use prange. * value-range.h (enum value_range_discriminator): Add VR_PRANGE. (class prange): New. (Value_Range::init): Add prange support. (Value_Range::operator=): Same. (Value_Range::supports_type_p): Same. (prange::prange): New. (prange::supports_p): New. (prange::supports_type_p): New. (prange::set_undefined): New. (prange::set_varying): New. (prange::set_nonzero): New. (prange::set_zero): New. (prange::contains_p): New. (prange::zero_p): New. (prange::nonzero_p): New. (prange::type): New. (prange::lower_bound): New. (prange::upper_bound): New. (prange::varying_compatible_p): New. (prange::get_bitmask): New. (prange::fits_p): New. --- gcc/value-range-pretty-print.cc | 25 +++ gcc/value-range-pretty-print.h | 1 + gcc/value-range.cc | 303 +++++++++++++++++++++++++++++++- gcc/value-range.h | 199 ++++++++++++++++++--- 4 files changed, 500 insertions(+), 28 deletions(-)