Bug 110807

Slightly reduced:
#include <vector>

std::vector<bool> byCallSpread;
void f()
{
  byCallSpread = {true};
}

Confirmed.  We're diagnosing the sequence

<bb 2> [local count: 1073741824]:
D.26106[0] = 1;
_7 = byCallSpread.D.26008._M_impl.D.25481._M_start.D.16802._M_p;
_8 = MEM[(const struct _Bit_iterator &)&byCallSpread + 16].D.16802._M_offset;
_9 = MEM[(const struct _Bit_iterator &)&byCallSpread + 16].D.16802._M_p;
_10 = _9 - _7;
_11 = _10 * 8;
_12 = (long int) _8;
_13 = _11 + _12;
_14 = (long unsigned int) _13;
if (_14 > 1)
  goto <bb 3>; [50.00%]
else
  goto <bb 4>; [50.00%]

<bb 4> [local count: 536870913]:
if (_13 == 1)
  goto <bb 5>; [89.00%]
else
  goto <bb 9>; [11.00%]

<bb 9> [local count: 375809640]:
__result ={v} {CLOBBER(eol)};
_118 = MEM[(const struct _Bvector_impl *)&byCallSpread].D.25481._M_end_of_storage;
if (_7 != _118)
  goto <bb 10>; [50.00%]
else
  goto <bb 14>; [50.00%]

<bb 14> [local count: 187904820]:
_316 = operator new (8);
_138 = byCallSpread.D.26008._M_impl.D.25481._M_start.D.16802._M_p;
_339 = _9 - _138;
_775 = (long unsigned int) _339;
if (_339 > 8)
  goto <bb 15>; [90.00%]
else
  goto <bb 16>; [10.00%]

<bb 15> [local count: 169114338]:
__builtin_memmove (_316, _138, _775);

the memmove call in BB 15 is diagnosed, it goes to storage of size 8
and obviously the guarding test just checked we will write more than 8 bytes
here.

I'm just guessing this is a missed optimization (this code must be
unreachable), but possibly again the standard library implementation
might make it impossible for the compiler to prove that given it isn't
able to second-guess constraints in the standard library.
Disclaimer: I didn't try to decipher the shitload of code we generate for
this simple function ;)

I think this is the same warning that causes libstdc++ testsuite failures when testing with --target_board=unix/-D_GLIBCXX_DEBUG

FAIL: 23_containers/vector/bool/swap.cc (test for excess errors)

I thought I'd already reported that, but I can't find it.

The library allocates space for N elements then copies n elements:

      vector(const vector& __x)
      : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator()))
      {
	_M_initialize(__x.size());
	_M_copy_aligned(__x.begin(), __x.end(), begin());
      }

We probably have the usual problem that GCC thinks allocating memory might alter __x because it's a global, and so in theory (but never in practice) the program could replace operator new with something insane that modifies the global.

I tried changing the constructor to:

	const_iterator __xbegin = __x.begin(), __xend = __x.end();
	_M_initialize(__x.size());
	_M_copy_aligned(__xbegin, __xend, begin());

That fixes the library test FAILs, but not the case in this bug report.

A similar change in vector<bool>::_M_insert_range fixes this one though.

The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:7931a1de9ec87b996d51d3d60786f5c81f63919f

commit r14-2797-g7931a1de9ec87b996d51d3d60786f5c81f63919f
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Wed Jul 26 14:09:24 2023 +0100

    libstdc++: Avoid bogus overflow warnings in std::vector<bool> [PR110807]
    
    GCC thinks the allocation can alter the object being copied if it's
    globally reachable, so doesn't realize that [x.begin(), x.end()) after
    the allocation is the same as x.size() before it.
    
    This causes a testsuite failure when testing with -D_GLIBCXX_DEBUG:
    FAIL: 23_containers/vector/bool/swap.cc (test for excess errors)
    A fix is to move the calls to x.begin() and x.end() to before the
    allocation.
    
    A similar problem exists in vector<bool>::_M_insert_range where *this is
    globally reachable, as reported in PR libstdc++/110807. That can also be
    fixed by moving calls to begin() and end() before the allocation.
    
    libstdc++-v3/ChangeLog:
    
            PR libstdc++/110807
            * include/bits/stl_bvector.h (vector(const vector&)): Access
            iterators before allocating.
            * include/bits/vector.tcc (vector<bool>::_M_insert_range):
            Likewise.
            * testsuite/23_containers/vector/bool/110807.cc: New test.

Fixed on trunk so far.

The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:f30e62b0ee05befd20863466d1fb55a34d15c228

commit r14-2802-gf30e62b0ee05befd20863466d1fb55a34d15c228
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Wed Jul 26 19:08:39 2023 +0100

    libstdc++: Require C++11 for 23_containers/vector/bool/110807.cc [PR110807]
    
    This new test uses uniform initialization syntax, so requires C++11 or
    later.
    
    libstdc++-v3/ChangeLog:
    
            PR libstdc++/110807
            * testsuite/23_containers/vector/bool/110807.cc: Require c++11.

The new test fails with -m32 -D_GLIBCXX_USE_CXX11_ABI=0

I give up.

The releases/gcc-13 branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:962cd3e2c475e8197fd0cfa7330a8f352b4ff5b2

commit r13-7625-g962cd3e2c475e8197fd0cfa7330a8f352b4ff5b2
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Wed Jul 26 14:09:24 2023 +0100

    libstdc++: Avoid bogus overflow warnings in std::vector<bool> [PR110807]
    
    GCC thinks the allocation can alter the object being copied if it's
    globally reachable, so doesn't realize that [x.begin(), x.end()) after
    the allocation is the same as x.size() before it.
    
    This causes a testsuite failure when testing with -D_GLIBCXX_DEBUG:
    FAIL: 23_containers/vector/bool/swap.cc (test for excess errors)
    A fix is to move the calls to x.begin() and x.end() to before the
    allocation.
    
    A similar problem exists in vector<bool>::_M_insert_range where *this is
    globally reachable, as reported in PR libstdc++/110807. That can also be
    fixed by moving calls to begin() and end() before the allocation.
    
    libstdc++-v3/ChangeLog:
    
            PR libstdc++/110807
            * include/bits/stl_bvector.h (vector(const vector&)): Access
            iterators before allocating.
            * include/bits/vector.tcc (vector<bool>::_M_insert_range):
            Likewise.
            * testsuite/23_containers/vector/bool/110807.cc: New test.
    
    (cherry picked from commit 7931a1de9ec87b996d51d3d60786f5c81f63919f)

Fixed for 13.3

> The new test fails with -m32

I've looked a bit into why.  The memmove is optimized out by vrp (or, if that's disabled, by dom) on lp64, because it's guarded by two conditions: _10 > sizeof(long), and !(_14 > 1), where _10 is a signed long (ptrdiff_t) computed as the difference between the _M_p of _M_finish and _M_start in the preexisting vector, and _14 = (unsigned long)(_10*8 + _8), where _8 is the vector's finish offset.  in order for the _14 condition to hold, _14 must be 0ul..1ul.

Since _10 is long, _8 promotes to long in lp64, the addition is performed as a signed long, and then converted to unsigned long.  _8 is loaded from memory as an unsigned int, and nothing is known about it, so its promoted operand is 0l..0xffffffffl.  In order for _14 to be <= 1ul, _10 * 8 must be in the range -0xffffffffl..1l, and therefore _10 must be <= 0x1fffffffl..0l, which enables folding of the _10 condition as the entire range is <= sizeof(long).

In the lp32 case, _10 is int, so _10*8 promotes to unsigned int for the addition, whose result is then NOPped to unsigned long.  _8 is also loaded from memory as unsigned int, but because unsigned addition wraps around and _8 covers the full range, nothing can be inferred about the range of _10*8, and thus _10's range is only limited by overflow-avoidance in the signed multiplication: -0x1fffffffl..0x1ffffffl.  Therefore, the _10 compare cannot be folded, and the memmove call remains.

I think the missed optimization and the overall problem stems from the fact that optimizers don't know the actual range of _M_offset.  Ensuring it's visibly normalized at uses in which out-of-range _M_offsets might sneak in might be enough to avoid the warning and enable further optimizations.

I don't think _M_offset can ever be out of range, it's always set by the library code.

Doesn't the warning come from this line, which doesn't use _M_offset anyway?

	_Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);

So I'm not sure what we can do in the library to state the invariants in a way the optimizer can understand them.

The master branch has been updated by Alexandre Oliva <aoliva@gcc.gnu.org>:

https://gcc.gnu.org/g:e39b3e02c27bd771a07e385f9672ecf1a45ced77

commit r14-5260-ge39b3e02c27bd771a07e385f9672ecf1a45ced77
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.

The releases/gcc-13 branch has been updated by Torbjorn Svensson <azoff@gcc.gnu.org>:

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)