[Bug tree-optimization/110060] New: Adding optimizer hints to std::vector causes a new -Wstringop-overread false positive

[Bug tree-optimization/110060] New: Adding optimizer hints to std::vector causes a new -Wstringop-overread false positive

[redi at gcc dot gnu.org]

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

            Bug ID: 110060
           Summary: Adding optimizer hints to std::vector causes a new
                    -Wstringop-overread false positive
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Keywords: diagnostic
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: redi at gcc dot gnu.org
            Blocks: 97048
  Target Milestone: ---

Created attachment 55223
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55223&action=edit
Preprocessed source for FAIL 23_containers/vector/types/1.cc

As discussed on IRC recently, I want to add optimization hints to
std::vector::size() and std::vector::capacity() so that gcc knows there will be
no reallocation here:

  vec.assign(vec.size(), 0);

The call to assign will not reallocate because size() <= capacity() is always
true. We can express that invariant in the code.

However, doing so causes a new testsuite FAIL:

FAIL: 23_containers/vector/types/1.cc (test for excess errors)

$ ~/gcc/latest/bin/g++ -O2 -Wall a-1.ii
In file included from /home/jwakely/gcc/14/include/c++/14.0.0/vector:62,
                 from
/home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/23_containers/vector/types/1.cc:23:
In static member function ‘static _Up* std::__copy_move<_IsMove, true,
std::random_access_iterator_tag>::__copy_m(_Tp*, _Tp*, _Up*) [with _Tp =
greedy_ops::X; _Up = greedy_ops::X; bool _IsMove = false]’,
    inlined from ‘_OI std::__copy_move_a2(_II, _II, _OI) [with bool _IsMove =
false; _II = greedy_ops::X*; _OI = greedy_ops::X*]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_algobase.h:506:30,
    inlined from ‘_OI std::__copy_move_a1(_II, _II, _OI) [with bool _IsMove =
false; _II = greedy_ops::X*; _OI = greedy_ops::X*]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_algobase.h:533:42,
    inlined from ‘_OI std::__copy_move_a(_II, _II, _OI) [with bool _IsMove =
false; _II = greedy_ops::X*; _OI = greedy_ops::X*]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_algobase.h:540:31,
    inlined from ‘_OI std::copy(_II, _II, _OI) [with _II = greedy_ops::X*; _OI
= greedy_ops::X*]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_algobase.h:633:7,
    inlined from ‘std::vector<_Tp, _Alloc>& std::vector<_Tp,
_Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = greedy_ops::X;
_Alloc = std::allocator<greedy_ops::X>]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/vector.tcc:255:17,
    inlined from ‘int main()’ at
/home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/23_containers/vector/types/1.cc:35:7:
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_algobase.h:437:30: warning:
‘void* __builtin_memcpy(void*, const void*, long unsigned int)’ forming offset
1 is out of the bounds [0, 1] [-Warray-bounds=]
  437 |             __builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
      |             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In static member function ‘static _Up* std::__copy_move<_IsMove, true,
std::random_access_iterator_tag>::__copy_m(_Tp*, _Tp*, _Up*) [with _Tp =
greedy_ops::X; _Up = greedy_ops::X; bool _IsMove = false]’,
    inlined from ‘_OI std::__copy_move_a2(_II, _II, _OI) [with bool _IsMove =
false; _II = greedy_ops::X*; _OI = greedy_ops::X*]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_algobase.h:506:30,
    inlined from ‘_OI std::__copy_move_a1(_II, _II, _OI) [with bool _IsMove =
false; _II = greedy_ops::X*; _OI = greedy_ops::X*]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_algobase.h:533:42,
    inlined from ‘_OI std::__copy_move_a(_II, _II, _OI) [with bool _IsMove =
false; _II = greedy_ops::X*; _OI = greedy_ops::X*]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_algobase.h:540:31,
    inlined from ‘_OI std::copy(_II, _II, _OI) [with _II = greedy_ops::X*; _OI
= greedy_ops::X*]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_algobase.h:633:7,
    inlined from ‘static _ForwardIterator
std::__uninitialized_copy<true>::__uninit_copy(_InputIterator, _InputIterator,
_ForwardIterator) [with _InputIterator = greedy_ops::X*; _ForwardIterator =
greedy_ops::X*]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_uninitialized.h:147:27,
    inlined from ‘_ForwardIterator std::uninitialized_copy(_InputIterator,
_InputIterator, _ForwardIterator) [with _InputIterator = greedy_ops::X*;
_ForwardIterator = greedy_ops::X*]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_uninitialized.h:185:15,
    inlined from ‘_ForwardIterator std::__uninitialized_copy_a(_InputIterator,
_InputIterator, _ForwardIterator, allocator<_Tp>&) [with _InputIterator =
greedy_ops::X*; _ForwardIterator = greedy_ops::X*; _Tp = greedy_ops::X]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_uninitialized.h:373:37,
    inlined from ‘std::vector<_Tp, _Alloc>& std::vector<_Tp,
_Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = greedy_ops::X;
_Alloc = std::allocator<greedy_ops::X>]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/vector.tcc:257:35,
    inlined from ‘int main()’ at
/home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/23_containers/vector/types/1.cc:35:7:
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_algobase.h:437:30: warning:
‘void* __builtin_memcpy(void*, const void*, long unsigned int)’ reading between
2 and 9223372036854775807 bytes from a region of size 1 [-Wstringop-overread]
  437 |             __builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
      |             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from
/home/jwakely/gcc/14/include/c++/14.0.0/x86_64-pc-linux-gnu/bits/c++allocator.h:33,
                 from
/home/jwakely/gcc/14/include/c++/14.0.0/bits/allocator.h:46,
                 from /home/jwakely/gcc/14/include/c++/14.0.0/vector:63:
In member function ‘_Tp* std::__new_allocator<_Tp>::allocate(size_type, const
void*) [with _Tp = greedy_ops::X]’,
    inlined from ‘static _Tp* std::allocator_traits<std::allocator<_Tp1>
>::allocate(allocator_type&, size_type) [with _Tp = greedy_ops::X]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/alloc_traits.h:482:28,
    inlined from ‘std::_Vector_base<_Tp, _Alloc>::pointer
std::_Vector_base<_Tp, _Alloc>::_M_allocate(std::size_t) [with _Tp =
greedy_ops::X; _Alloc = std::allocator<greedy_ops::X>]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_vector.h:378:33,
    inlined from ‘std::_Vector_base<_Tp, _Alloc>::pointer
std::_Vector_base<_Tp, _Alloc>::_M_allocate(std::size_t) [with _Tp =
greedy_ops::X; _Alloc = std::allocator<greedy_ops::X>]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_vector.h:375:7,
    inlined from ‘void std::_Vector_base<_Tp,
_Alloc>::_M_create_storage(std::size_t) [with _Tp = greedy_ops::X; _Alloc =
std::allocator<greedy_ops::X>]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_vector.h:413:44,
    inlined from ‘std::_Vector_base<_Tp, _Alloc>::_Vector_base(std::size_t,
const allocator_type&) [with _Tp = greedy_ops::X; _Alloc =
std::allocator<greedy_ops::X>]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_vector.h:332:26,
    inlined from ‘std::vector<_Tp, _Alloc>::vector(size_type, const
allocator_type&) [with _Tp = greedy_ops::X; _Alloc =
std::allocator<greedy_ops::X>]’ at
/home/jwakely/gcc/14/include/c++/14.0.0/bits/stl_vector.h:572:47,
    inlined from ‘int main()’ at
/home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/23_containers/vector/types/1.cc:29:39:
/home/jwakely/gcc/14/include/c++/14.0.0/bits/new_allocator.h:147:48: note:
source object of size 1 allocated by ‘operator new’
  147 |         return static_cast<_Tp*>(_GLIBCXX_OPERATOR_NEW(__n *
sizeof(_Tp)));
      |                                  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~



The preprocessed source of the test is attached (with the proposed new hints
added to the std::vector code). There's no warning with -O1 or -O3, only -O2.


Referenced Bugs:

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

[Bug tree-optimization/110060] Adding optimizer hints to std::vector causes a new -Wstringop-overread false positive

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Hmm:
```
  MEM[(struct _Vector_base *)&w]._M_impl.D.25239._M_start = _73;
  _66 = _73 + 1;
  MEM[(struct _Vector_base *)&w]._M_impl.D.25239._M_end_of_storage = _66;
  MEM[(struct vector *)&w].D.25935._M_impl.D.25239._M_finish = _66;
  _486 = _63 + 2;
  v.D.25935._M_impl.D.25239._M_finish = _486;
  _154 = _63 + 3;
  v.D.25935._M_impl.D.25239._M_finish = _154;
  _138 = MEM[(struct X * const &)&v];
  _215 = v.D.25935._M_impl.D.25239._M_end_of_storage;
  _216 = v.D.25935._M_impl.D.25239._M_finish;
  if (_215 != _216)
```

There is huge missed optimizations here.
I noticed that the last fre is not iterative and we have the case where many of
the ifs are removed due to fre and forwprop at the end.

[Bug tree-optimization/110060] Adding optimizer hints to std::vector causes a new -Wstringop-overread false positive

[redi at gcc dot gnu.org]

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

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Anything I can do in std::vector to make it optimize better?

[Bug tree-optimization/110060] Adding optimizer hints to std::vector causes a new -Wstringop-overread false positive

[pinskia at gcc dot gnu.org]

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #2)
> Anything I can do in std::vector to make it optimize better?

I don't think in this case there is but I could be wrong.
it has to do with the v.insert call saving the end value and then loading from
it and doing a comparison and it is iterative on it (with a few v.insert).

[Bug tree-optimization/110060] Adding optimizer hints to std::vector causes a new -Wstringop-overread false positive

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So the other thing that is going wrong is the addition of the optimizer hints
is causing things like std::vector<T>::size no longer to be inlined. because
the TU size has increased and we start hitting the TU size limit.
This is why -O3 does not warn either.

[Bug tree-optimization/110060] Adding optimizer hints to std::vector causes a new -Wstringop-overread false positive

[redi at gcc dot gnu.org]

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

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Ugh, that's not good - maybe I should revert it then. Or make _M_invariant much
smaller.

[Bug tree-optimization/110060] Adding optimizer hints to std::vector causes a new -Wstringop-overread false positive

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note you can reduce main to just:
```
int main()
{
  std::vector<int> v(5);
  const std::vector<int> w(1);

  v.resize(1);
//  v.insert(v.begin(), 0);
  //v.insert(v.begin(), 1, 0);
//  v.insert(v.begin(), w.begin(), w.end());
  v = w;

  return 0;
}
```
And get the warning still at -O2.

With the above main in .optimized we get:
```
  MEM[(struct _Vector_base *)&w]._M_impl.D.25239._M_start = _53;
  _46 = _53 + 4;
  MEM[(struct _Vector_base *)&w]._M_impl.D.25239._M_end_of_storage = _46;
  *_53 = 0;
  w.D.25935._M_impl.D.25239._M_finish = _46;
  v.D.25935._M_impl.D.25239._M_finish = __first_33;
  __xlen_82 = std::vector<int>::size (&w);
  if (__xlen_82 > 5)
    goto <bb 4>; [33.00%]
  else
    goto <bb 10>; [67.00%]
```

std::vector<int>::size is literally just:
```
        movq    8(%rdi), %rax
        subq    (%rdi), %rax
        sarq    $2, %rax
        ret
```

So that is definitely an issue there.

[Bug tree-optimization/110060] Adding optimizer hints to std::vector causes a new -Wstringop-overread false positive

[redi at gcc dot gnu.org]

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

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
The library change also caused:

FAIL: g++.dg/pr104547.C -std=gnu++17 scan-tree-dump-not vrp2
"_M_default_append"

So I'm definitely changing std::vector again. I don't know if this is worth
keeping open as a tree-optimization bug, or just blame the increased function
sizes in the library code.

[Bug libstdc++/110060] [14 Regression] Adding optimizer hints to std::vector causes a new -Wstringop-overread false positive

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |13.1.1
          Component|tree-optimization           |libstdc++
     Ever confirmed|0                           |1
            Summary|Adding optimizer hints to   |[14 Regression] Adding
                   |std::vector causes a new    |optimizer hints to
                   |-Wstringop-overread false   |std::vector causes a new
                   |positive                    |-Wstringop-overread false
                   |                            |positive
   Last reconfirmed|                            |2023-06-01
      Known to fail|                            |14.0
           Assignee|unassigned at gcc dot gnu.org      |redi at gcc dot gnu.org
   Target Milestone|---                         |14.0
             Status|UNCONFIRMED                 |ASSIGNED

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Reassigning to libstdc++ and taking it myself.

[Bug libstdc++/110060] [14 Regression] Adding optimizer hints to std::vector causes a new -Wstringop-overread false positive

[cvs-commit at gcc dot gnu.org]

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

--- Comment #9 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:b7b255e77a271974479c34d1db3daafc04b920bc

commit r14-1470-gb7b255e77a271974479c34d1db3daafc04b920bc
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Jun 1 10:26:10 2023 +0100

    libstdc++: Fix code size regressions in std::vector [PR110060]

    My r14-1452-gfb409a15d9babc change to add optimization hints to
    std::vector causes regressions because it makes std::vector::size() and
    std::vector::capacity() too big to inline. That's the opposite of what
    I wanted, so revert the changes to those functions.

    To achieve the original aim of optimizing vec.assign(vec.size(), x) we
    can add a local optimization hint to _M_fill_assign, so that it doesn't
    affect all other uses of size() and capacity().

    Additionally, add the same hint to the _M_assign_aux overload for
    forward iterators and add that to the testcase.

    It would be nice to similarly optimize:
      if (vec1.size() == vec2.size()) vec1 = vec2;
    but adding hints to operator=(const vector&) doesn't help. Presumably
    the relationships between the two sizes and two capacities are too
    complex to track effectively.

    libstdc++-v3/ChangeLog:

            PR libstdc++/110060
            * include/bits/stl_vector.h (_Vector_base::_M_invariant):
            Remove.
            (vector::size, vector::capacity): Remove calls to _M_invariant.
            * include/bits/vector.tcc (vector::_M_fill_assign): Add
            optimization hint to reallocating path.
            (vector::_M_assign_aux(FwdIter, FwdIter, forward_iterator_tag)):
            Likewise.
            * testsuite/23_containers/vector/capacity/invariant.cc: Moved
            to...
            * testsuite/23_containers/vector/modifiers/assign/no_realloc.cc:
            ...here. Check assign(FwdIter, FwdIter) too.
            * testsuite/23_containers/vector/types/1.cc: Revert addition
            of -Wno-stringop-overread option.

[Bug libstdc++/110060] [14 Regression] Adding optimizer hints to std::vector causes a new -Wstringop-overread false positive

[redi at gcc dot gnu.org]

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

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

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

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