[Bug target/80813] [12/13/14/15 Regression] x86: std::vector::operator[] could be somewhat faster using BT instead of SHL

[hubicka at gcc dot gnu.org via Gcc-bugs]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80813

--- Comment #3 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
OK, so the horrid codegen is because bvector's [] operator is imlemented using
iterator:
  return begin()[__n];
iterator's [] operator is implemented using:

    _GLIBCXX20_CONSTEXPR
    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);
      if (__n < 0)
        {
          __n += int(_S_word_bit);
          --_M_p;
        }
      _M_offset = static_cast<unsigned int>(__n);
    }


So the conditional is a check for negative __n which makes sense for iterator's
[], but not for vector's [].  We could add __builtin_unreachable hint that __n
is at most max_size, but since [] is such a common operation on vectors, I
think it makes sense to make life of compiler easier and micro-optimize it in
the array.

diff --git a/libstdc++-v3/include/bits/stl_bvector.h
b/libstdc++-v3/include/bits/stl_bvector.h
index 341eee33b21..43a07bc3e55 100644
--- a/libstdc++-v3/include/bits/stl_bvector.h
+++ b/libstdc++-v3/include/bits/stl_bvector.h
@@ -1132,7 +1141,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       operator[](size_type __n)
       {
        __glibcxx_requires_subscript(__n);
-       return begin()[__n];
+       return _Bit_reference (this->_M_impl._M_start._M_p
+                              + __n / int(_S_word_bit),
+                              __n % int(_S_word_bit));
       }

       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
@@ -1140,7 +1151,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       operator[](size_type __n) const
       {
        __glibcxx_requires_subscript(__n);
-       return begin()[__n];
+       return _Bit_reference (this->_M_impl._M_start._M_p
+                              + __n / int(_S_word_bit),
+                              __n % int(_S_word_bit));
       }

     protected:

With this I now get:
.LFB1248:
        .cfi_startproc
        movq    (%rdi), %rax
        movq    %rsi, %rdx
        shrq    $6, %rdx
        andq    (%rax,%rdx,8), %rsi
        andl    $63, %esi
        setne   %al
        ret
that is certainly better. Still does not use BT.
Not sure if _M_incr can be tweaked for less horrid codegen.