public inbox for libstdc++@gcc.gnu.org
 help / color / mirror / Atom feed
From: Alexandre Oliva <oliva@adacore.com>
To: gcc-patches@gcc.gnu.org, libstdc++@gcc.gnu.org
Subject: [PATCH] libstdc++: optimize bit iterators assuming normalization [PR110807]
Date: Wed, 08 Nov 2023 13:10:18 -0300	[thread overview]
Message-ID: <orfs1gi5ud.fsf@lxoliva.fsfla.org> (raw)


The representation of bit iterators, using a pointer into an array of
words, and an unsigned bit offset into that word, makes for some
optimization challenges: because the compiler doesn't know that the
offset is always in a certain narrow range, beginning at zero and
ending before the word bitwidth, when a function loads an offset that
it hasn't normalized itself, it may fail to derive certain reasonable
conclusions, even to the point of retaining useless calls that elicit
incorrect warnings.

Case at hand: The 110807.cc testcase for bit vectors assigns a 1-bit
list to a global bit vector variable.  Based on the compile-time
constant length of the list, we decide in _M_insert_range whether to
use the existing storage or to allocate new storage for the vector.
After allocation, we decide in _M_copy_aligned how to copy any
preexisting portions of the vector to the newly-allocated storage.
When copying two or more words, we use __builtin_memmove.

However, because we compute the available room using bit offsets
without range information, even comparing them with constants, we fail
to infer ranges for the preexisting vector depending on word size, and
may thus retain the memmove call despite knowing we've only allocated
one word.

Other parts of the compiler then detect the mismatch between the
constant allocation size and the much larger range that could
theoretically be copied into the newly-allocated storage if we could
reach the call.

Ensuring the compiler is aware of the constraints on the offset range
enables it to do a much better job at optimizing.  The challenge is to
do so without runtime overhead, because this is not about checking
that it's in range, it's only about telling the compiler about it.

This patch introduces a __GLIBCXX_BUILTIN_ASSUME macro that, when
optimizing, expands to code that invokes undefined behavior in case
the expression doesn't hold, so that the compiler optimizes out the
test and the entire branch containing, but retaining enough
information about the paths that shouldn't be taken, so that at
remaining paths it optimizes based on the assumption.

I also introduce a member function in bit iterators that conveys to
the compiler the information that the assumption is supposed to hold,
and various calls throughout member functions of bit iterators that
might not otherwise know that the offsets have to be in range,
making pessimistic decisions and failing to optimize out cases that it
could.

With the explicit assumptions, the compiler can correlate the test for
available storage in the vector with the test for how much storage
might need to be copied, and determine that, if we're not asking for
enough room for two or more words, we can omit entirely the code to
copy two or more words, without any runtime overhead whatsoever: no
traces remain of the undefined behavior or of the tests that inform
the compiler about the assumptions that must hold.

Regstrapped on x86_64-linux-gnu, also tested with gcc-13 on i686- and
x86_64-.  Ok to install?

(It was later found to fix 23_containers/vector/bool/allocator/copy_cc
on x86_64-linux-gnu as well, that fails on gcc-13 with the same warning.)

(The constant_evaluated/static_assert bit is disabled because expr is
not a constant according to some libstdc++ build errors, but there
doesn't seem to be a problem with the other bits.  I haven't really
thought that bit through, it was something I started out as potentially
desirable, but that turned out to be not required.  I suppose I could
just drop it.)

(I suppose __GLIBCXX_BUILTIN_ASSUME could be moved to a more general
place and put to more general uses, but I didn't feel that bold ;-)


for  libstdc++-v3/ChangeLog

	PR libstdc++/110807
	* include/bits/stl_bvector.h (__GLIBCXX_BUILTIN_ASSUME): New.
	(_Bit_iterator_base): Add _M_normalized_p and
	_M_assume_normalized.  Use them in _M_bump_up, _M_bump_down,
	_M_incr, operator==, operator<=>, operator<, and operator-.
	(_Bit_iterator): Also use them in operator*.
	(_Bit_const_iterator): Likewise.
---
 libstdc++-v3/include/bits/stl_bvector.h |   75 ++++++++++++++++++++++++++++++-
 1 file changed, 72 insertions(+), 3 deletions(-)

diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h
index 8d18bcaffd434..81b316846454b 100644
--- a/libstdc++-v3/include/bits/stl_bvector.h
+++ b/libstdc++-v3/include/bits/stl_bvector.h
@@ -177,6 +177,55 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     _Bit_type * _M_p;
     unsigned int _M_offset;
 
+#if __OPTIMIZE__ && !__GLIBCXX_DISABLE_ASSUMPTIONS
+// If the assumption (EXPR) fails, invoke undefined behavior, so that
+// the test and the failure block gets optimized out, but the compiler
+// still recalls that (expr) can be taken for granted.  Use this only
+// for expressions that are simple and explicit enough that the
+// compiler can optimize based on them.  When not optimizing, the
+// expression is still compiled, but it's never executed.
+#if 0 /* ??? */ && __cpp_lib_is_constant_evaluated
+#define __GLIBCXX_BUILTIN_ASSUME(expr)		\
+    do						\
+      if (std::is_constant_evaluated ())	\
+	static_assert(expr);			\
+      else if (!(expr))				\
+	{					\
+	  void **__assert_failed = 0;		\
+	  *__assert_failed = 0;			\
+	  __builtin_unreachable ();		\
+	}					\
+    while (0)
+#else
+#define __GLIBCXX_BUILTIN_ASSUME(expr)		\
+    do						\
+      if (!(expr))				\
+	{					\
+	  void **__assert_failed = 0;		\
+	  *__assert_failed = 0;			\
+	  __builtin_unreachable ();		\
+	}					\
+    while (0)
+#endif
+#else
+#define __GLIBCXX_BUILTIN_ASSUME(expr)		\
+    (void)(false && (expr))
+#endif
+
+    _GLIBCXX20_CONSTEXPR
+    bool
+    _M_normalized_p() const
+    {
+      return (_M_offset < unsigned(_S_word_bit));
+    }
+
+    _GLIBCXX20_CONSTEXPR
+    void
+    _M_assume_normalized() const
+    {
+      __GLIBCXX_BUILTIN_ASSUME (_M_normalized_p ());
+    }
+
     _GLIBCXX20_CONSTEXPR
     _Bit_iterator_base(_Bit_type * __x, unsigned int __y)
     : _M_p(__x), _M_offset(__y) { }
@@ -185,6 +234,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     void
     _M_bump_up()
     {
+      _M_assume_normalized();
       if (_M_offset++ == int(_S_word_bit) - 1)
 	{
 	  _M_offset = 0;
@@ -196,6 +246,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     void
     _M_bump_down()
     {
+      _M_assume_normalized();
       if (_M_offset-- == 0)
 	{
 	  _M_offset = int(_S_word_bit) - 1;
@@ -207,6 +258,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     void
     _M_incr(ptrdiff_t __i)
     {
+      _M_assume_normalized();
       difference_type __n = __i + _M_offset;
       _M_p += __n / int(_S_word_bit);
       __n = __n % int(_S_word_bit);
@@ -221,7 +273,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     _GLIBCXX_NODISCARD
     friend _GLIBCXX20_CONSTEXPR bool
     operator==(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
-    { return __x._M_p == __y._M_p && __x._M_offset == __y._M_offset; }
+    {
+      __x._M_assume_normalized();
+      __y._M_assume_normalized();
+      return __x._M_p == __y._M_p && __x._M_offset == __y._M_offset;
+    }
 
 #if __cpp_lib_three_way_comparison
     [[nodiscard]]
@@ -229,6 +285,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     operator<=>(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
     noexcept
     {
+      __x._M_assume_normalized();
+      __y._M_assume_normalized();
       if (const auto __cmp = __x._M_p <=> __y._M_p; __cmp != 0)
 	return __cmp;
       return __x._M_offset <=> __y._M_offset;
@@ -238,6 +296,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     friend bool
     operator<(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
     {
+      __x._M_assume_normalized();
+      __y._M_assume_normalized();
       return __x._M_p < __y._M_p
 	    || (__x._M_p == __y._M_p && __x._M_offset < __y._M_offset);
     }
@@ -266,6 +326,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     friend _GLIBCXX20_CONSTEXPR ptrdiff_t
     operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
     {
+      // Make _M_offset's range visible to optimizers.
+      __x._M_assume_normalized();
+      __y._M_assume_normalized();
       return (int(_S_word_bit) * (__x._M_p - __y._M_p)
 	      + __x._M_offset - __y._M_offset);
     }
@@ -297,7 +360,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
     reference
     operator*() const
-    { return reference(_M_p, 1UL << _M_offset); }
+    {
+      _M_assume_normalized();
+      return reference(_M_p, 1UL << _M_offset);
+    }
 
     _GLIBCXX20_CONSTEXPR
     iterator&
@@ -408,7 +474,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
     const_reference
     operator*() const
-    { return _Bit_reference(_M_p, 1UL << _M_offset); }
+    {
+      _M_assume_normalized();
+      return _Bit_reference(_M_p, 1UL << _M_offset);
+    }
 
     _GLIBCXX20_CONSTEXPR
     const_iterator&

-- 
Alexandre Oliva, happy hacker            https://FSFLA.org/blogs/lxo/
   Free Software Activist                   GNU Toolchain Engineer
More tolerance and less prejudice are key for inclusion and diversity
Excluding neuro-others for not behaving ""normal"" is *not* inclusive

             reply	other threads:[~2023-11-08 16:10 UTC|newest]

Thread overview: 18+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-11-08 16:10 Alexandre Oliva [this message]
2023-11-08 19:32 ` Jonathan Wakely
2023-11-09  1:17   ` [PATCH v2] " Alexandre Oliva
2023-11-09  1:22     ` Jonathan Wakely
2023-11-09  3:36       ` [PATCH v3] " Alexandre Oliva
2023-11-09  5:57         ` François Dumont
2023-11-09  8:16           ` Jonathan Wakely
2023-11-09 19:49             ` [PATCH] libstdc++: bvector: undef always_inline macro Alexandre Oliva
2023-11-09 20:18               ` Jonathan Wakely
2023-11-15  2:20                 ` Patrick Palka
2023-11-15  5:53                   ` Alexandre Oliva
2023-11-15  2:44                 ` Alexandre Oliva
2023-11-15  5:08                   ` Alexandre Oliva
2023-11-15  8:22                   ` Jonathan Wakely
2023-11-16  4:40                     ` Alexandre Oliva
2024-02-07 16:25       ` [PATCH v2] libstdc++: optimize bit iterators assuming normalization [PR110807] Torbjorn SVENSSON
2024-02-07 16:36         ` Jonathan Wakely
2024-02-09  8:49           ` Torbjorn SVENSSON

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=orfs1gi5ud.fsf@lxoliva.fsfla.org \
    --to=oliva@adacore.com \
    --cc=gcc-patches@gcc.gnu.org \
    --cc=libstdc++@gcc.gnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).