diff mbox series

[COMMITTED] Reduce startup costs for Value_Range.

Message ID 20240501074150.304170-2-aldyh@redhat.com
State New
Headers show
Series [COMMITTED] Reduce startup costs for Value_Range. | expand

Commit Message

Aldy Hernandez May 1, 2024, 7:41 a.m. UTC 
Value_Range is our polymorphic temporary that can hold any range.  It
is used for type agnostic code where it isn't known ahead of time,
what the type of the range will be (irange, france, etc).  Currently,
there is a temporary of each type in the object, which means we need
to construct each range for every temporary.  This isn't scaling
well now that prange is about to add yet another range type.

This patch removes each range, opting to use in-place new for a byte
buffer sufficiently large to hold ranges of any type.  It reduces the
memory footprint by 14% for every Value_Range temporary (from 792 to
680 bytes), and we are guaranteed it will never again grow as we add
more range types (strings, complex numbers, etc).

Surprisingly, it improves VRP performance by 6.61% and overall
compilation by 0.44%, which is a lot more than we bargained for
when we started working on prange performance.

There is a slight change in semantics for Value_Range.  The default
constructor does not initialize the object at all.  It must be
manually initialized with either Value_Range::set_type(), or by
assigning a range to it.  This means that IPA's m_known_value_ranges
must be initialized at allocation, instead of depending on the empty
constructor to initialize it to VR_UNDEFINED for unsupported_range.

I have taken the time to properly document both the class, and each
method.  If anything isn't clear, please let me know so I can adjust it
accordingly.

gcc/ChangeLog:

	* ipa-fnsummary.cc (evaluate_properties_for_edge): Initialize Value_Range's.
	* value-range.h (class Value_Range): Add a buffer and remove
	m_irange and m_frange.
	(Value_Range::Value_Range): Call init.
	(Value_Range::set_type): Same.
	(Value_Range::init): Use in place new to initialize buffer.
	(Value_Range::operator=): Tidy.
---
 gcc/ipa-fnsummary.cc |   8 ++-
 gcc/value-range.h    | 127 ++++++++++++++++++++++++-------------------
 2 files changed, 76 insertions(+), 59 deletions(-)

Comments

Ian Lance Taylor May 2, 2024, 2:39 a.m. UTC | #1 
On Wed, May 1, 2024 at 12:43 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> gcc/ChangeLog:
>
>         * ipa-fnsummary.cc (evaluate_properties_for_edge): Initialize Value_Range's.
>         * value-range.h (class Value_Range): Add a buffer and remove
>         m_irange and m_frange.
>         (Value_Range::Value_Range): Call init.
>         (Value_Range::set_type): Same.
>         (Value_Range::init): Use in place new to initialize buffer.
>         (Value_Range::operator=): Tidy.


I'm seeing a crash building on sparc-sun-solaris2.11 that may be due
to this change.  The crash occurs in stage 1, the first time the newly
built compiler is used.

./xgcc -B./ -B/var/gcc/iant/install/sparc-sun-solaris2.11/bin/
-isystem /var/gcc/iant/install/sparc-sun-solaris2.11/include -isystem
/var/gcc/iant/install/sparc-sun-solaris2.11/sys-include
-L/var/gcc/iant/bootstrap/gcc/../ld  -xc -nostdinc /dev/null -S -o
/dev/null -fself-test=../../gcc/gcc/testsuite/selftests
In function ‘test_fn’:
cc1: internal compiler error: Bus Error
0x1c7db03 crash_signal
        ../../gcc/gcc/toplev.cc:319
0x104a82c void wi::copy<wide_int_storage,
generic_wide_int<wide_int_ref_storage<true, false> >
>(wide_int_storage&, generic_wide_int<wide_int_ref_storage<true,
false> > const&)
        ../../gcc/gcc/wide-int.h:2191
0x1049da3 wide_int_storage&
wide_int_storage::operator=<wi::hwi_with_prec>(wi::hwi_with_prec
const&)
        ../../gcc/gcc/wide-int.h:1247
0x104929b generic_wide_int<wide_int_storage>&
generic_wide_int<wide_int_storage>::operator=<wi::hwi_with_prec>(wi::hwi_with_prec
const&)
        ../../gcc/gcc/wide-int.h:1002
0x104757f irange_bitmask::set_unknown(unsigned int)
        ../../gcc/gcc/value-range.h:163
0x1047b6f irange::set_varying(tree_node*)
        ../../gcc/gcc/value-range.h:1067
0x1774d1b Value_Range::set_varying(tree_node*)
        ../../gcc/gcc/value-range.h:720
0x1aef213 range_cast(vrange&, tree_node*)
        ../../gcc/gcc/range-op.h:248
0x1ada517 operator_lshift::op1_range(irange&, tree_node*, irange
const&, irange const&, relation_trio) const
        ../../gcc/gcc/range-op.cc:2706
0x1aeaa6b range_op_lshift_tests
        ../../gcc/gcc/range-op.cc:4750
0x1aee20f selftest::range_op_tests()
        ../../gcc/gcc/range-op.cc:4887
0x2dfaa37 test_ranges
        ../../gcc/gcc/function-tests.cc:585
0x2dfb337 selftest::function_tests_cc_tests()
        ../../gcc/gcc/function-tests.cc:681
0x308a027 selftest::run_tests()
        ../../gcc/gcc/selftest-run-tests.cc:108
0x1c833ef toplev::run_self_tests()
        ../../gcc/gcc/toplev.cc:2213
Please submit a full bug report, with preprocessed source (by using
-freport-bug).
Please include the complete backtrace with any bug report.
See <https://gcc.gnu.org/bugs/> for instructions.
make: *** [../../gcc/gcc/c/Make-lang.in:153: s-selftest-c] Error 1

Ian
Andrew Pinski May 2, 2024, 2:50 a.m. UTC | #2 
On Wed, May 1, 2024 at 7:40 PM Ian Lance Taylor <iant@google.com> wrote:
>
> On Wed, May 1, 2024 at 12:43 AM Aldy Hernandez <aldyh@redhat.com> wrote:
> >
> > gcc/ChangeLog:
> >
> >         * ipa-fnsummary.cc (evaluate_properties_for_edge): Initialize Value_Range's.
> >         * value-range.h (class Value_Range): Add a buffer and remove
> >         m_irange and m_frange.
> >         (Value_Range::Value_Range): Call init.
> >         (Value_Range::set_type): Same.
> >         (Value_Range::init): Use in place new to initialize buffer.
> >         (Value_Range::operator=): Tidy.
>
>
> I'm seeing a crash building on sparc-sun-solaris2.11 that may be due
> to this change.  The crash occurs in stage 1, the first time the newly
> built compiler is used.
>
> ./xgcc -B./ -B/var/gcc/iant/install/sparc-sun-solaris2.11/bin/
> -isystem /var/gcc/iant/install/sparc-sun-solaris2.11/include -isystem
> /var/gcc/iant/install/sparc-sun-solaris2.11/sys-include
> -L/var/gcc/iant/bootstrap/gcc/../ld  -xc -nostdinc /dev/null -S -o
> /dev/null -fself-test=../../gcc/gcc/testsuite/selftests
> In function ‘test_fn’:
> cc1: internal compiler error: Bus Error
> 0x1c7db03 crash_signal
>         ../../gcc/gcc/toplev.cc:319
> 0x104a82c void wi::copy<wide_int_storage,
> generic_wide_int<wide_int_ref_storage<true, false> >
> >(wide_int_storage&, generic_wide_int<wide_int_ref_storage<true,
> false> > const&)
>         ../../gcc/gcc/wide-int.h:2191
> 0x1049da3 wide_int_storage&
> wide_int_storage::operator=<wi::hwi_with_prec>(wi::hwi_with_prec
> const&)
>         ../../gcc/gcc/wide-int.h:1247
> 0x104929b generic_wide_int<wide_int_storage>&
> generic_wide_int<wide_int_storage>::operator=<wi::hwi_with_prec>(wi::hwi_with_prec
> const&)
>         ../../gcc/gcc/wide-int.h:1002
> 0x104757f irange_bitmask::set_unknown(unsigned int)
>         ../../gcc/gcc/value-range.h:163
> 0x1047b6f irange::set_varying(tree_node*)
>         ../../gcc/gcc/value-range.h:1067
> 0x1774d1b Value_Range::set_varying(tree_node*)
>         ../../gcc/gcc/value-range.h:720
> 0x1aef213 range_cast(vrange&, tree_node*)
>         ../../gcc/gcc/range-op.h:248
> 0x1ada517 operator_lshift::op1_range(irange&, tree_node*, irange
> const&, irange const&, relation_trio) const
>         ../../gcc/gcc/range-op.cc:2706
> 0x1aeaa6b range_op_lshift_tests
>         ../../gcc/gcc/range-op.cc:4750
> 0x1aee20f selftest::range_op_tests()
>         ../../gcc/gcc/range-op.cc:4887
> 0x2dfaa37 test_ranges
>         ../../gcc/gcc/function-tests.cc:585
> 0x2dfb337 selftest::function_tests_cc_tests()
>         ../../gcc/gcc/function-tests.cc:681
> 0x308a027 selftest::run_tests()
>         ../../gcc/gcc/selftest-run-tests.cc:108
> 0x1c833ef toplev::run_self_tests()
>         ../../gcc/gcc/toplev.cc:2213
> Please submit a full bug report, with preprocessed source (by using
> -freport-bug).
> Please include the complete backtrace with any bug report.
> See <https://gcc.gnu.org/bugs/> for instructions.
> make: *** [../../gcc/gcc/c/Make-lang.in:153: s-selftest-c] Error 1

This was also reported here: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114912

The same question applies really, what compiler are you using to
compile GCC with? I suspect this is making a difference. It might also
be the sparc compiler that both of you two are using is causing wrong
code with some more complex C++ code even though it is at -O0.
The adding of the deconstructor to Value_Range might be causing the
structure to become a "non-POD" and different argument passing and it
was broken even at -O0 (this is just a guess).

Thanks,
Andrew Pinski

>
> Ian
Ian Lance Taylor May 2, 2024, 11:18 a.m. UTC | #3 
On Wed, May 1, 2024 at 7:50 PM Andrew Pinski <pinskia@gmail.com> wrote:
>
> On Wed, May 1, 2024 at 7:40 PM Ian Lance Taylor <iant@google.com> wrote:
> >
> > On Wed, May 1, 2024 at 12:43 AM Aldy Hernandez <aldyh@redhat.com> wrote:
> > >
> > > gcc/ChangeLog:
> > >
> > >         * ipa-fnsummary.cc (evaluate_properties_for_edge): Initialize Value_Range's.
> > >         * value-range.h (class Value_Range): Add a buffer and remove
> > >         m_irange and m_frange.
> > >         (Value_Range::Value_Range): Call init.
> > >         (Value_Range::set_type): Same.
> > >         (Value_Range::init): Use in place new to initialize buffer.
> > >         (Value_Range::operator=): Tidy.
> >
> >
> > I'm seeing a crash building on sparc-sun-solaris2.11 that may be due
> > to this change.  The crash occurs in stage 1, the first time the newly
> > built compiler is used.
> >
> > ./xgcc -B./ -B/var/gcc/iant/install/sparc-sun-solaris2.11/bin/
> > -isystem /var/gcc/iant/install/sparc-sun-solaris2.11/include -isystem
> > /var/gcc/iant/install/sparc-sun-solaris2.11/sys-include
> > -L/var/gcc/iant/bootstrap/gcc/../ld  -xc -nostdinc /dev/null -S -o
> > /dev/null -fself-test=../../gcc/gcc/testsuite/selftests
> > In function ‘test_fn’:
> > cc1: internal compiler error: Bus Error
> > 0x1c7db03 crash_signal
> >         ../../gcc/gcc/toplev.cc:319
> > 0x104a82c void wi::copy<wide_int_storage,
> > generic_wide_int<wide_int_ref_storage<true, false> >
> > >(wide_int_storage&, generic_wide_int<wide_int_ref_storage<true,
> > false> > const&)
> >         ../../gcc/gcc/wide-int.h:2191
> > 0x1049da3 wide_int_storage&
> > wide_int_storage::operator=<wi::hwi_with_prec>(wi::hwi_with_prec
> > const&)
> >         ../../gcc/gcc/wide-int.h:1247
> > 0x104929b generic_wide_int<wide_int_storage>&
> > generic_wide_int<wide_int_storage>::operator=<wi::hwi_with_prec>(wi::hwi_with_prec
> > const&)
> >         ../../gcc/gcc/wide-int.h:1002
> > 0x104757f irange_bitmask::set_unknown(unsigned int)
> >         ../../gcc/gcc/value-range.h:163
> > 0x1047b6f irange::set_varying(tree_node*)
> >         ../../gcc/gcc/value-range.h:1067
> > 0x1774d1b Value_Range::set_varying(tree_node*)
> >         ../../gcc/gcc/value-range.h:720
> > 0x1aef213 range_cast(vrange&, tree_node*)
> >         ../../gcc/gcc/range-op.h:248
> > 0x1ada517 operator_lshift::op1_range(irange&, tree_node*, irange
> > const&, irange const&, relation_trio) const
> >         ../../gcc/gcc/range-op.cc:2706
> > 0x1aeaa6b range_op_lshift_tests
> >         ../../gcc/gcc/range-op.cc:4750
> > 0x1aee20f selftest::range_op_tests()
> >         ../../gcc/gcc/range-op.cc:4887
> > 0x2dfaa37 test_ranges
> >         ../../gcc/gcc/function-tests.cc:585
> > 0x2dfb337 selftest::function_tests_cc_tests()
> >         ../../gcc/gcc/function-tests.cc:681
> > 0x308a027 selftest::run_tests()
> >         ../../gcc/gcc/selftest-run-tests.cc:108
> > 0x1c833ef toplev::run_self_tests()
> >         ../../gcc/gcc/toplev.cc:2213
> > Please submit a full bug report, with preprocessed source (by using
> > -freport-bug).
> > Please include the complete backtrace with any bug report.
> > See <https://gcc.gnu.org/bugs/> for instructions.
> > make: *** [../../gcc/gcc/c/Make-lang.in:153: s-selftest-c] Error 1
>
> This was also reported here: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114912

Thanks.

> The same question applies really, what compiler are you using to
> compile GCC with? I suspect this is making a difference. It might also
> be the sparc compiler that both of you two are using is causing wrong
> code with some more complex C++ code even though it is at -O0.
> The adding of the deconstructor to Value_Range might be causing the
> structure to become a "non-POD" and different argument passing and it
> was broken even at -O0 (this is just a guess).

I am building stage1 with GCC 9.1.0.

Ian
diff mbox series

Patch

diff --git a/gcc/ipa-fnsummary.cc b/gcc/ipa-fnsummary.cc
index dff40cd8aa5..668a01ef175 100644
--- a/gcc/ipa-fnsummary.cc
+++ b/gcc/ipa-fnsummary.cc
@@ -681,8 +681,12 @@  evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p,
 		    if (!vr.undefined_p () && !vr.varying_p ())
 		      {
 			if (!avals->m_known_value_ranges.length ())
-			  avals->m_known_value_ranges.safe_grow_cleared (count,
-									 true);
+			  {
+			    avals->m_known_value_ranges.safe_grow_cleared (count,
+									   true);
+			    for (int i = 0; i < count; ++i)
+			      avals->m_known_value_ranges[i].set_type (void_type_node);
+			  }
 			avals->m_known_value_ranges[i] = vr;
 		      }
 		  }
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 471f362f388..f1c638f8cd0 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -684,6 +684,16 @@  typedef int_range<2> value_range;
 // This is an "infinite" precision range object for use in temporary
 // calculations for any of the handled types.  The object can be
 // transparently used as a vrange.
+//
+// Using any of the various constructors initializes the object
+// appropriately, but the default constructor is uninitialized and
+// must be initialized either with set_type() or by assigning into it.
+//
+// Assigning between incompatible types is allowed.  For example if a
+// temporary holds an irange, you can assign an frange into it, and
+// all the right things will happen.  However, before passing this
+// object to a function accepting a vrange, the correct type must be
+// set.  If it isn't, you can do so with set_type().
 
 class Value_Range
 {
@@ -693,6 +703,7 @@  public:
   Value_Range (tree type);
   Value_Range (tree, tree, value_range_kind kind = VR_RANGE);
   Value_Range (const Value_Range &);
+  ~Value_Range ();
   void set_type (tree type);
   vrange& operator= (const vrange &);
   Value_Range& operator= (const Value_Range &);
@@ -726,16 +737,29 @@  public:
   void accept (const vrange_visitor &v) const { m_vrange->accept (v); }
 private:
   void init (tree type);
-  unsupported_range m_unsupported;
+  void init (const vrange &);
+
   vrange *m_vrange;
-  int_range_max m_irange;
-  frange m_frange;
+  // The buffer must be at least the size of the largest range.
+  static_assert (sizeof (int_range_max) > sizeof (frange));
+  char m_buffer[sizeof (int_range_max)];
 };
 
+// The default constructor is uninitialized and must be initialized
+// with either set_type() or with an assignment into it.
+
 inline
 Value_Range::Value_Range ()
 {
-  m_vrange = &m_unsupported;
+  m_vrange = NULL;
+}
+
+// Copy constructor.
+
+inline
+Value_Range::Value_Range (const Value_Range &r)
+{
+  init (*r.m_vrange);
 }
 
 // Copy constructor from a vrange.
@@ -743,11 +767,11 @@  Value_Range::Value_Range ()
 inline
 Value_Range::Value_Range (const vrange &r)
 {
-  *this = r;
+  init (r);
 }
 
-// Copy constructor from a TYPE.  The range of the temporary is set to
-// UNDEFINED.
+// Construct an UNDEFINED range that can hold ranges of TYPE.  If TYPE
+// is not supported, default to unsupported_range.
 
 inline
 Value_Range::Value_Range (tree type)
@@ -755,6 +779,9 @@  Value_Range::Value_Range (tree type)
   init (type);
 }
 
+// Construct a range that can hold a range of [MIN, MAX], where MIN
+// and MAX are trees.
+
 inline
 Value_Range::Value_Range (tree min, tree max, value_range_kind kind)
 {
@@ -763,13 +790,25 @@  Value_Range::Value_Range (tree min, tree max, value_range_kind kind)
 }
 
 inline
-Value_Range::Value_Range (const Value_Range &r)
+Value_Range::~Value_Range ()
 {
-  *this = *r.m_vrange;
+  if (m_vrange)
+    m_vrange->~vrange ();
 }
 
-// Initialize object so it is possible to store temporaries of TYPE
-// into it.
+// Initialize object to an UNDEFINED range that can hold ranges of
+// TYPE.  Clean-up memory if there was a previous object.
+
+inline void
+Value_Range::set_type (tree type)
+{
+  if (m_vrange)
+    m_vrange->~vrange ();
+  init (type);
+}
+
+// Initialize object to an UNDEFINED range that can hold ranges of
+// TYPE.
 
 inline void
 Value_Range::init (tree type)
@@ -777,71 +816,45 @@  Value_Range::init (tree type)
   gcc_checking_assert (TYPE_P (type));
 
   if (irange::supports_p (type))
-    m_vrange = &m_irange;
+    m_vrange = new (&m_buffer) int_range_max ();
   else if (frange::supports_p (type))
-    m_vrange = &m_frange;
+    m_vrange = new (&m_buffer) frange ();
   else
-    m_vrange = &m_unsupported;
+    m_vrange = new (&m_buffer) unsupported_range ();
 }
 
-// Set the temporary to allow storing temporaries of TYPE.  The range
-// of the temporary is set to UNDEFINED.
+// Initialize object with a copy of R.
 
 inline void
-Value_Range::set_type (tree type)
+Value_Range::init (const vrange &r)
 {
-  init (type);
-  m_vrange->set_undefined ();
+  if (is_a <irange> (r))
+    m_vrange = new (&m_buffer) int_range_max (as_a <irange> (r));
+  else if (is_a <frange> (r))
+    m_vrange = new (&m_buffer) frange (as_a <frange> (r));
+  else
+    m_vrange = new (&m_buffer) unsupported_range (as_a <unsupported_range> (r));
 }
 
-// Assignment operator for temporaries.  Copying incompatible types is
-// allowed.
+// Assignment operator.  Copying incompatible types is allowed.  That
+// is, assigning an frange to an object holding an irange does the
+// right thing.
 
 inline vrange &
 Value_Range::operator= (const vrange &r)
 {
-  if (is_a <irange> (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 if (is_a <unsupported_range> (r))
-    {
-      m_unsupported = as_a <unsupported_range> (r);
-      m_vrange = &m_unsupported;
-    }
-  else
-    gcc_unreachable ();
-
+  if (m_vrange)
+    m_vrange->~vrange ();
+  init (r);
   return *m_vrange;
 }
 
 inline Value_Range &
 Value_Range::operator= (const Value_Range &r)
 {
-  if (r.m_vrange == &r.m_irange)
-    {
-      m_irange = r.m_irange;
-      m_vrange = &m_irange;
-    }
-  else if (r.m_vrange == &r.m_frange)
-    {
-      m_frange = r.m_frange;
-      m_vrange = &m_frange;
-    }
-  else if (r.m_vrange == &r.m_unsupported)
-    {
-      m_unsupported = r.m_unsupported;
-      m_vrange = &m_unsupported;
-    }
-  else
-    gcc_unreachable ();
-
+  // No need to call the m_vrange destructor here, as we will do so in
+  // the assignment below.
+  *this = *r.m_vrange;
   return *this;
 }