public inbox for libstdc++-cvs@sourceware.org help / color / mirror / Atom feed
From: Torbjorn Svensson <azoff@gcc.gnu.org> To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc r13-8309] libstdc++: optimize bit iterators assuming normalization [PR110807] Date: Fri, 9 Feb 2024 08:46:48 +0000 (GMT) [thread overview] Message-ID: <20240209084648.7378C3858C35@sourceware.org> (raw) https://gcc.gnu.org/g:5d684a5f7f82b1425cac5eaa11dccc3b51a62d44 commit r13-8309-g5d684a5f7f82b1425cac5eaa11dccc3b51a62d44 Author: Alexandre Oliva <oliva@adacore.com> Date: Thu Nov 9 00:01:37 2023 -0300 libstdc++: optimize bit iterators assuming normalization [PR110807] 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. Using attribute assume (_M_offset <= ...) didn't work, because gimple lowered that to something that vrp could only use to ensure 'this' was non-NULL. Exposing _M_offset as an automatic variable/gimple register outside the unevaluated assume operand enabled the optimizer to do its job. Rather than placing such load-then-assume constructs all over, I introduced an always-inline member function in bit iterators that does the job of conveying to the compiler the information that the assumption is supposed to hold, and various calls throughout functions pertaining to bit iterators that might not otherwise know that the offsets have to be in range, so that the compiler no longer needs to make conservative assumptions that prevent optimizations. 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. for libstdc++-v3/ChangeLog PR libstdc++/110807 * include/bits/stl_bvector.h (_Bit_iterator_base): Add _M_assume_normalized member function. Call it in _M_bump_up, _M_bump_down, _M_incr, operator==, operator<=>, operator<, and operator-. (_Bit_iterator): Also call it in operator*. (_Bit_const_iterator): Likewise. (cherry picked from commit e39b3e02c27bd771a07e385f9672ecf1a45ced77) Diff: --- libstdc++-v3/include/bits/stl_bvector.h | 37 ++++++++++++++++++++++++++++++--- 1 file changed, 34 insertions(+), 3 deletions(-) diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h index 8d18bcaffd43..2b91af2005f2 100644 --- a/libstdc++-v3/include/bits/stl_bvector.h +++ b/libstdc++-v3/include/bits/stl_bvector.h @@ -56,6 +56,10 @@ #ifndef _STL_BVECTOR_H #define _STL_BVECTOR_H 1 +#ifndef _GLIBCXX_ALWAYS_INLINE +#define _GLIBCXX_ALWAYS_INLINE inline __attribute__((__always_inline__)) +#endif + #if __cplusplus >= 201103L #include <initializer_list> #include <bits/functional_hash.h> @@ -177,6 +181,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Bit_type * _M_p; unsigned int _M_offset; + _GLIBCXX20_CONSTEXPR _GLIBCXX_ALWAYS_INLINE + void + _M_assume_normalized() const + { + unsigned int __ofst = _M_offset; + __attribute__ ((__assume__ (__ofst < unsigned(_S_word_bit)))); + } + _GLIBCXX20_CONSTEXPR _Bit_iterator_base(_Bit_type * __x, unsigned int __y) : _M_p(__x), _M_offset(__y) { } @@ -185,6 +197,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 +209,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 +221,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 +236,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 +248,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 +259,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 +289,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER friend _GLIBCXX20_CONSTEXPR ptrdiff_t operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) { + __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 +322,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 +436,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&
reply other threads:[~2024-02-09 8:46 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
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=20240209084648.7378C3858C35@sourceware.org \ --to=azoff@gcc.gnu.org \ --cc=gcc-cvs@gcc.gnu.org \ --cc=libstdc++-cvs@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: linkBe 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).