[Bug c++/100516] New: Unexpected -Wstringop-overread in deque<char> initialization from empty initializer_list

[Bug c++/100516] New: Unexpected -Wstringop-overread in deque<char> initialization from empty initializer_list

[vopl at bk dot ru]

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

            Bug ID: 100516
           Summary: Unexpected -Wstringop-overread in deque<char>
                    initialization from empty initializer_list
           Product: gcc
           Version: 11.1.0
            Status: UNCONFIRMED
          Keywords: diagnostic
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: vopl at bk dot ru
                CC: msebor at gcc dot gnu.org
  Target Milestone: ---

[Bug c++/100516] Unexpected -Wstringop-overread in deque<char> initialization from empty initializer_list

[vopl at bk dot ru]

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

--- Comment #1 from vopl at bk dot ru ---
Please look at the following code, it throws an unexpected warning
[-Wstringop-overread].

$ cat b11.cpp && echo EOFFFFF
#include <deque>

void f()
{
    std::initializer_list<char> il{};
    std::deque<char>{il};
}
EOFFFFF

$ g++-11.1.0 -v -O2 -c b11.cpp
Using built-in specs.
COLLECT_GCC=g++-11.1.0
Target: x86_64-pc-linux-gnu
Configured with:
/var/tmp/portage/sys-devel/gcc-11.1.0/work/gcc-11.1.0/configure
--host=x86_64-pc-linux-gnu --build=x86_64-pc-linux-gnu --prefix=/usr
--bindir=/usr/x86_64-pc-linux-gnu/gcc-bin/11.1.0
--includedir=/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include
--datadir=/usr/share/gcc-data/x86_64-pc-linux-gnu/11.1.0
--mandir=/usr/share/gcc-data/x86_64-pc-linux-gnu/11.1.0/man
--infodir=/usr/share/gcc-data/x86_64-pc-linux-gnu/11.1.0/info
--with-gxx-include-dir=/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include/g++-v11
--with-python-dir=/share/gcc-data/x86_64-pc-linux-gnu/11.1.0/python
--enable-languages=c,c++,fortran --enable-obsolete --enable-secureplt
--disable-werror --with-system-zlib --disable-nls --enable-checking=release
--with-bugurl=https://bugs.gentoo.org/ --with-pkgversion='Gentoo 11.1.0 p1'
--disable-esp --enable-libstdcxx-time --with-build-config=bootstrap-lto
--enable-shared --enable-threads=posix --enable-__cxa_atexit
--enable-clocale=gnu --enable-multilib --with-multilib-list=m32,m64
--disable-fixed-point --enable-targets=all --enable-libgomp --disable-libssp
--disable-libada --enable-systemtap --disable-valgrind-annotations
--enable-vtable-verify --with-zstd --enable-lto --with-isl
--disable-isl-version-check --enable-default-pie --disable-default-ssp
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 11.1.0 (Gentoo 11.1.0 p1) 
COLLECT_GCC_OPTIONS='-v' '-O2' '-c' '-shared-libgcc' '-mtune=generic'
'-march=x86-64'
 /usr/libexec/gcc/x86_64-pc-linux-gnu/11.1.0/cc1plus -quiet -v -D_GNU_SOURCE
./b11.cpp -quiet -dumpbase b11.cpp -dumpbase-ext .cpp -mtune=generic
-march=x86-64 -O2 -version -o /tmp/ccLiGLAe.s
GNU C++17 (Gentoo 11.1.0 p1) version 11.1.0 (x86_64-pc-linux-gnu)
        compiled by GNU C version 11.1.0, GMP version 6.2.1, MPFR version
4.1.0, MPC version 1.2.1, isl version isl-0.23-GMP

GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
ignoring nonexistent directory "/usr/local/include"
ignoring nonexistent directory
"/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/../../../../x86_64-pc-linux-gnu/include"
#include "..." search starts here:
#include <...> search starts here:
 /usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include/g++-v11
 /usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include/g++-v11/x86_64-pc-linux-gnu
 /usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include/g++-v11/backward
 /usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include
 /usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include-fixed
 /usr/include
End of search list.
GNU C++17 (Gentoo 11.1.0 p1) version 11.1.0 (x86_64-pc-linux-gnu)
        compiled by GNU C version 11.1.0, GMP version 6.2.1, MPFR version
4.1.0, MPC version 1.2.1, isl version isl-0.23-GMP

GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
Compiler executable checksum: bf86c5c567158ff2074c3c886a72c867
In file included from
/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include/g++-v11/deque:60,
                 from ./b11.cpp:1:
In static member function 'static _Tp* std::__copy_move<_IsMove, true,
std::random_access_iterator_tag>::__copy_m(const _Tp*, const _Tp*, _Tp*) [with
_Tp = char; bool _IsMove = false]',
    inlined from '_OI std::__copy_move_a2(_II, _II, _OI) [with bool _IsMove =
false; _II = const char*; _OI = char*]' at
/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include/g++-v11/bits/stl_algobase.h:495:30,
    inlined from '_OI std::__copy_move_a1(_II, _II, _OI) [with bool _IsMove =
false; _II = const char*; _OI = char*]' at
/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include/g++-v11/bits/stl_algobase.h:522:42,
    inlined from '_OI std::__copy_move_a(_II, _II, _OI) [with bool _IsMove =
false; _II = const char*; _OI = char*]' at
/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include/g++-v11/bits/stl_algobase.h:529:31,
    inlined from '_OI std::copy(_II, _II, _OI) [with _II = const char*; _OI =
char*]' at
/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include/g++-v11/bits/stl_algobase.h:620:7,
    inlined from 'static _ForwardIterator
std::__uninitialized_copy<true>::__uninit_copy(_InputIterator, _InputIterator,
_ForwardIterator) [with _InputIterator = const char*; _ForwardIterator =
char*]' at
/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include/g++-v11/bits/stl_uninitialized.h:110:27,
    inlined from '_ForwardIterator std::uninitialized_copy(_InputIterator,
_InputIterator, _ForwardIterator) [with _InputIterator = const char*;
_ForwardIterator = char*]' at
/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include/g++-v11/bits/stl_uninitialized.h:151:15,
    inlined from '_ForwardIterator std::__uninitialized_copy_a(_InputIterator,
_InputIterator, _ForwardIterator, std::allocator<_Tp>&) [with _InputIterator =
const char*; _ForwardIterator = char*; _Tp = char]' at
/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include/g++-v11/bits/stl_uninitialized.h:333:37,
    inlined from 'void std::deque<_Tp,
_Alloc>::_M_range_initialize(_ForwardIterator, _ForwardIterator,
std::forward_iterator_tag) [with _ForwardIterator = const char*; _Tp = char;
_Alloc = std::allocator<char>]' at
/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include/g++-v11/bits/deque.tcc:463:33,
    inlined from 'std::deque<_Tp, _Alloc>::deque(std::initializer_list<_Tp>,
const allocator_type&) [with _Tp = char; _Alloc = std::allocator<char>]' at
/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include/g++-v11/bits/stl_deque.h:958:21,
    inlined from 'void f()' at ./b11.cpp:6:10:
/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/include/g++-v11/bits/stl_algobase.h:431:30:
warning: 'void* __builtin_memcpy(void*, const void*, long unsigned int)'
reading 1 or more bytes from a region of size 0 [-Wstringop-overread]
  431 |             __builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
      |             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
COLLECT_GCC_OPTIONS='-v' '-O2' '-c' '-shared-libgcc' '-mtune=generic'
'-march=x86-64'
 /usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/../../../../x86_64-pc-linux-gnu/bin/as
-v --64 -o b11.o /tmp/ccLiGLAe.s
GNU assembler version 2.35.2 (x86_64-pc-linux-gnu) using BFD version (Gentoo
2.35.2 p1) 2.35.2
COMPILER_PATH=/usr/libexec/gcc/x86_64-pc-linux-gnu/11.1.0/:/usr/libexec/gcc/x86_64-pc-linux-gnu/11.1.0/:/usr/libexec/gcc/x86_64-pc-linux-gnu/:/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/:/usr/lib/gcc/x86_64-pc-linux-gnu/:/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/../../../../x86_64-pc-linux-gnu/bin/
LIBRARY_PATH=/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/:/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/../../../../lib64/:/lib/../lib64/:/usr/lib/../lib64/:/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/../../../../x86_64-pc-linux-gnu/lib/:/usr/lib/gcc/x86_64-pc-linux-gnu/11.1.0/../../../:/lib/:/usr/lib/
COLLECT_GCC_OPTIONS='-v' '-O2' '-c' '-shared-libgcc' '-mtune=generic'
'-march=x86-64'

[Bug c++/100516] Unexpected -Wstringop-overread in deque<char> initialization from empty initializer_list

[vopl at bk dot ru]

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

--- Comment #2 from vopl at bk dot ru ---
minimal reproduce code I have:

using size_t = decltype(sizeof(char));

class initializer
{
    const char* _array;
    size_t      _len;

public:
    constexpr initializer() : _array{}, _len{} { }
    constexpr const char* begin() const noexcept { return _array; }
    constexpr const char* end() const noexcept { return _array + _len; }
};

/////////0/////////1/////////2/////////3/////////4/////////5/////////6/////////7
struct deque
{
    char** _M_map;
    char** _M_start;
    char** _M_finish;

    template <class=void> void _M_initialize_map(size_t);

    deque(initializer nil)
    {
        const char* first = nil.begin();
        const char* last = nil.end();

        _M_initialize_map(static_cast<size_t>(last - first));

        for (char** cur_node = _M_start; cur_node != _M_finish; ++cur_node)
            ++first;

        if (last != first)
            __builtin_memmove(*_M_finish, first, static_cast<size_t>(last -
first));
    }
};

template <class> void deque::_M_initialize_map(size_t num_elements)
{
    size_t num_nodes = (num_elements / size_t{2} + 1);

    _M_map = new char*[8];

    char** nstart = _M_map + (size_t{8} - num_nodes) / 2;

    try
    {
        for (char** cur = nstart; cur == nstart; ++cur)
            *nstart = new char;
    }
    catch(...)
    {
        throw;
    }

    _M_start = _M_finish = nstart;
}

/////////0/////////1/////////2/////////3/////////4/////////5/////////6/////////7
int main()
{
    deque{initializer{}};
    return 0;
}

[Bug c++/100516] [11 Regression] Unexpected -Wstringop-overread in deque<char> initialization from empty initializer_list

[msebor at gcc dot gnu.org]

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

Martin Sebor <msebor at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Blocks|                            |97048
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2021-05-11
      Known to work|                            |10.3.0
            Summary|Unexpected                  |[11 Regression] Unexpected
                   |-Wstringop-overread in      |-Wstringop-overread in
                   |deque<char> initialization  |deque<char> initialization
                   |from empty initializer_list |from empty initializer_list
      Known to fail|                            |11.1.0, 12.0

--- Comment #3 from Martin Sebor <msebor at gcc dot gnu.org> ---
Confirmed.  Strictly speaking it's a GCC 11 regression introduced by a) the
warning becoming stricter and considering constant addresses to be invalid (as
they usually result from invalid arithmetic involving null pointers), and b)
GCC 11 exposing the null pointer arithmetic.  The warning in the original test
case in comment #0 triggers for the IL below where _19 is set to the address
512 plus some offset:

  <bb 5> [local count: 955247968]:
  _18 = (unsigned long) _58;
  _67 = (unsigned long) __cur_node_17;
  _13 = _18 + 18446744073709551615;
  _40 = _13 - _67;
  _25 = _40 >> 3;
  _3 = _25 * 512;
  _19 = 512B + _3;                          <<< 512 (invalid address)
  _26 = D.17216.D.17192._M_impl.D.16554._M_finish._M_first;
  _39 = (long int) _19;
  _Num_28 = -_39;
  _Num.7_29 = (long unsigned int) _Num_28;  <<< nonzero
  __builtin_memcpy (_26, _19, _Num.7_29);   <<< -Wstringop-overread

Since there can be no object at address 512 its size is determined to be zero. 
The warning triggers because the third argument to memcpy is determined to be
nonzero (also 512 plus some offset).  The bad address results from SCCP:

final value replacement:
  _19 = PHI <_37(4)>
 with expr: 512B + ((((unsigned long) _58 - (unsigned long) __cur_node_17) +
18446744073709551615) / 8) * 512
 final stmt:
  _19 = 512B + _3;

based on:

  <bb 4> [local count: 8684072504]:
  # __first_2 = PHI <_37(10), 0B(9)>
  # __cur_node_42 = PHI <__cur_node_24(10), __cur_node_17(9)>
  _37 = __first_2 + 512;

The underlying problem is that the loop in deque::_M_range_initialize()
iterates over both the deque's nodes and the initializer list's elements, and
the number of iterations has no apparent relationship to the latter.  As far as
GCC sees, the loop increments the null pointer to the empty initializer list by
the deque's buffer size of 512.  The warning could be avoided by
_M_range_initialize() returning early, before entering the loop, when the range
is empty.  Alternatively, it could be suppressed by #pragma GCC diagnostic
(that might need a patch like the one mentioned in pr98465 comment 32).


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97048
[Bug 97048] [meta-bug] bogus/missing -Wstringop-overread warnings

[Bug c++/100516] [11/12 Regression] Unexpected -Wstringop-overread in deque<char> initialization from empty initializer_list

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.2
            Summary|[11 Regression] Unexpected  |[11/12 Regression]
                   |-Wstringop-overread in      |Unexpected
                   |deque<char> initialization  |-Wstringop-overread in
                   |from empty initializer_list |deque<char> initialization
                   |                            |from empty initializer_list

[Bug c++/100516] [11/12 Regression] Unexpected -Wstringop-overread in deque<char> initialization from empty initializer_list

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.2                        |11.3

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 11.2 is being released, retargeting bugs to GCC 11.3

[Bug libstdc++/100516] [11/12 Regression] Unexpected -Wstringop-overread in deque<char> initialization from empty initializer_list

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c++                         |libstdc++
           Priority|P3                          |P2
   Last reconfirmed|2021-05-11 00:00:00         |2022-1-20
           Keywords|                            |missed-optimization

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Re-confirmed.  I think it's sth that might need to be worked around in
libstdc++?

[Bug libstdc++/100516] [11/12 Regression] Unexpected -Wstringop-overread in deque<char> initialization from empty initializer_list

[redi at gcc dot gnu.org]

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

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Once again the problem is that GCC warns about code which is unreachable by
construction. The loop bounds are determined by the deque's "map", which is
sized correctly for the incoming range.


I don't see this with trunk, but for GCC 11 adding this to the loop body works:

                if (__n < _S_buffer_size())
                  __builtin_unreachable();

[Bug libstdc++/100516] [11/12 Regression] Unexpected -Wstringop-overread in deque<char> initialization from empty initializer_list

[msebor at gcc dot gnu.org]

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

Martin Sebor <msebor at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=104017

--- Comment #7 from Martin Sebor <msebor at gcc dot gnu.org> ---
See also pr104017 for a related warning in std::deque.

[Bug libstdc++/100516] [11/12 Regression] Unexpected -Wstringop-overread in deque<char> initialization from empty initializer_list

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |redi at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

[Bug libstdc++/100516] [11/12 Regression] Unexpected -Wstringop-overread in deque<char> initialization from empty initializer_list

[cvs-commit at gcc dot gnu.org]

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

--- Comment #8 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

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

commit r12-6907-geae41b4d2cc30327f9f15c7390438c46aa09ed3f
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Jan 27 22:31:26 2022 +0000

    libstdc++: Prevent -Wstringop-overread warning in std::deque [PR100516]

    The compiler warns about the loop in deque::_M_range_initialize because
    it doesn't know that the number of nodes has already been correctly
    sized to match the size of the input. Use __builtin_unreachable to tell
    it that the loop will never be entered if the number of elements is
    smaller than a single node.

    libstdc++-v3/ChangeLog:

            PR libstdc++/100516
            * include/bits/deque.tcc (_M_range_initialize<ForwardIterator>):
            Add __builtin_unreachable to loop.
            * testsuite/23_containers/deque/100516.cc: New test.

[Bug libstdc++/100516] [11 Regression] Unexpected -Wstringop-overread in deque<char> initialization from empty initializer_list

[cvs-commit at gcc dot gnu.org]

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

--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:573bb865df967b420aba5382a5987b8865f83dc0

commit r11-9837-g573bb865df967b420aba5382a5987b8865f83dc0
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Jan 27 22:31:26 2022 +0000

    libstdc++: Prevent -Wstringop-overread warning in std::deque [PR100516]

    The compiler warns about the loop in deque::_M_range_initialize because
    it doesn't know that the number of nodes has already been correctly
    sized to match the size of the input. Use __builtin_unreachable to tell
    it that the loop will never be entered if the number of elements is
    smaller than a single node.

    libstdc++-v3/ChangeLog:

            PR libstdc++/100516
            * include/bits/deque.tcc (_M_range_initialize<ForwardIterator>):
            Add __builtin_unreachable to loop.
            * testsuite/23_containers/deque/100516.cc: New test.

    (cherry picked from commit eae41b4d2cc30327f9f15c7390438c46aa09ed3f)

[Bug libstdc++/100516] [11 Regression] Unexpected -Wstringop-overread in deque<char> initialization from empty initializer_list

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #10 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed for 11.3