Hi folks! In implementing prange (pointer ranges), I have found a 1.74% slowdown in VRP, even without any code path actually using the code. I have tracked this down to irange::get_bitmask() being compiled differently with and without the bare bones patch. With the patch, irange::get_bitmask() has a lot of code inlined into it, particularly get_bitmask_from_range() and consequently the wide_int_storage code.
I don't know whether this is expected behavior, and if it is, how to mitigate it. I have tried declaring get_bitmask_from_range() inline, but that didn't help. OTOH, using __attribute__((always_inline)) helps a bit, but not entirely. What does help is inlining irange::get_bitmask() entirely, but that seems like a big hammer. The overall slowdown in compilation is 0.26%, because VRP is a relatively fast pass, but a measurable pass slowdown is something we'd like to avoid. What's the recommended approach here? For the curious, I am attaching before and after copies of value-range.s. I am also attaching the two patches needed to reproduce the problem on mainline. The first patch is merely setup. It is the second patch that exhibits the problem. Notice there are no uses of prange yet. Thanks. Aldy
From ee63833c5f56064ef47c2bb9debd485f77d00171 Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <al...@redhat.com>
Date: Tue, 19 Mar 2024 18:04:55 +0100
Subject: [PATCH] Move get_bitmask_from_range out of irange class.
---
gcc/value-range.cc | 52 +++++++++++++++++++++++-----------------------
gcc/value-range.h | 1 -
2 files changed, 26 insertions(+), 27 deletions(-)
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 70375f7abf9..0f81ce32615 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -31,6 +31,30 @@ along with GCC; see the file COPYING3. If not see
#include "fold-const.h"
#include "gimple-range.h"
+// Return the bitmask inherent in a range.
+
+static irange_bitmask
+get_bitmask_from_range (tree type,
+ const wide_int &min, const wide_int &max)
+{
+ unsigned prec = TYPE_PRECISION (type);
+
+ // All the bits of a singleton are known.
+ if (min == max)
+ {
+ wide_int mask = wi::zero (prec);
+ wide_int value = min;
+ return irange_bitmask (value, mask);
+ }
+
+ wide_int xorv = min ^ max;
+
+ if (xorv != 0)
+ xorv = wi::mask (prec - wi::clz (xorv), false, prec);
+
+ return irange_bitmask (wi::zero (prec), min | xorv);
+}
+
void
irange::accept (const vrange_visitor &v) const
{
@@ -1832,31 +1856,6 @@ irange::invert ()
verify_range ();
}
-// Return the bitmask inherent in the range.
-
-irange_bitmask
-irange::get_bitmask_from_range () const
-{
- unsigned prec = TYPE_PRECISION (type ());
- wide_int min = lower_bound ();
- wide_int max = upper_bound ();
-
- // All the bits of a singleton are known.
- if (min == max)
- {
- wide_int mask = wi::zero (prec);
- wide_int value = lower_bound ();
- return irange_bitmask (value, mask);
- }
-
- wide_int xorv = min ^ max;
-
- if (xorv != 0)
- xorv = wi::mask (prec - wi::clz (xorv), false, prec);
-
- return irange_bitmask (wi::zero (prec), min | xorv);
-}
-
// Remove trailing ranges that this bitmask indicates can't exist.
void
@@ -1978,7 +1977,8 @@ irange::get_bitmask () const
// in the mask.
//
// See also the note in irange_bitmask::intersect.
- irange_bitmask bm = get_bitmask_from_range ();
+ irange_bitmask bm
+ = get_bitmask_from_range (type (), lower_bound (), upper_bound ());
if (!m_bitmask.unknown_p ())
bm.intersect (m_bitmask);
return bm;
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 9531df56988..dc5b153a83e 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -351,7 +351,6 @@ private:
bool varying_compatible_p () const;
bool intersect_bitmask (const irange &r);
bool union_bitmask (const irange &r);
- irange_bitmask get_bitmask_from_range () const;
bool set_range_from_bitmask ();
bool intersect (const wide_int& lb, const wide_int& ub);
--
2.44.0
From 03c70de43177a97ec5e9c243aafc798c1f37e6d8 Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <al...@redhat.com>
Date: Wed, 20 Mar 2024 06:25:52 +0100
Subject: [PATCH] Implement minimum prange class exhibiting VRP slowdown.
---
gcc/value-range-pretty-print.cc | 25 +++
gcc/value-range-pretty-print.h | 1 +
gcc/value-range.cc | 274 ++++++++++++++++++++++++++++++++
gcc/value-range.h | 196 +++++++++++++++++++++++
4 files changed, 496 insertions(+)
diff --git a/gcc/value-range-pretty-print.cc b/gcc/value-range-pretty-print.cc
index c75cbea3955..154253e047f 100644
--- a/gcc/value-range-pretty-print.cc
+++ b/gcc/value-range-pretty-print.cc
@@ -113,6 +113,31 @@ vrange_printer::print_irange_bitmasks (const irange &r) const
pp_string (pp, p);
}
+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
{
diff --git a/gcc/value-range-pretty-print.h b/gcc/value-range-pretty-print.h
index ca85fd6157c..54ee0cf8c26 100644
--- a/gcc/value-range-pretty-print.h
+++ b/gcc/value-range-pretty-print.h
@@ -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_irange_bound (const wide_int &w, tree type) const;
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 0f81ce32615..06ab1a616bf 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -377,6 +377,280 @@ 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;
+}
+
+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 ();
+}
+
+
void
frange::accept (const vrange_visitor &v) const
{
diff --git a/gcc/value-range.h b/gcc/value-range.h
index dc5b153a83e..9fac89a2f98 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -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.
@@ -389,6 +391,54 @@ private:
wide_int m_ranges[N*2];
};
+class prange : public vrange
+{
+ friend class prange_storage;
+ friend class vrange_printer;
+public:
+ 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;
+
+ 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;
+ void update_bitmask (const irange_bitmask &);
+protected:
+ bool varying_compatible_p () const;
+
+ tree m_type;
+ wide_int m_min;
+ wide_int m_max;
+ irange_bitmask m_bitmask;
+};
+
// Unsupported temporaries may be created by ranger before it's known
// they're unsupported, or by vr_values::get_value_range.
@@ -667,6 +717,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 { }
};
@@ -1196,6 +1247,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)
--
2.44.0
irange_get_bitmask_with_patch.s
Description: Binary data
irange_get_bitmask_without_patch.s
Description: Binary data
