[Bug c++/109205] New: vector.resize( v.size() + 100 ) does unnecessary comparison

[Bug c++/109205] New: vector.resize( v.size() + 100 ) does unnecessary comparison

[joerg.richter@pdv-fs.de]

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

            Bug ID: 109205
           Summary: vector.resize( v.size() + 100 ) does unnecessary
                    comparison
           Product: gcc
           Version: 12.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: joerg.richter@pdv-fs.de
  Target Milestone: ---

This function:

#include <vector>

void testResize( std::vector<char> & v )
{
  v.resize( v.size() + 100 );
}


Will compile (-O2) to something like this:

        mov     rcx, QWORD PTR [rdi+8]
        mov     rax, QWORD PTR [rdi]
        mov     rdx, rcx
        sub     rdx, rax
        lea     rsi, [rdx+100]
        cmp     rdx, rsi
        jb      .L39
        add     rax, rsi
        cmp     rcx, rax
        je      .L36
        mov     QWORD PTR [rdi+8], rax
.L36:
        ret
.L39:
        mov     esi, 100
        jmp     std::vector<char, std::allocator<char>
>::_M_default_append(unsigned long)

The call to _M_default_append is guarded by a cmp.  This seems unnecessary, as
the argument passed to resize is always bigger than size.  

Doing the addition with a signed type does not change the result.

See: https://godbolt.org/z/xY77fsz4z

[Bug libstdc++/109205] vector.resize( v.size() + 100 ) does unnecessary comparison

[pinskia at gcc dot gnu.org]

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

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So the IR looks like:
  _4 = MEM[(const struct vector *)v_3(D)].D.25711._M_impl.D.25018._M_finish;
  _6 = MEM[(const struct vector *)v_3(D)].D.25711._M_impl.D.25018._M_start;
  _7 = _4 - _6;
  _8 = (long unsigned int) _7;
  _1 = _8 + 100;

GCC does not know this statement holds true:
  if (v.end() < v.begin()) __builtin_unreachable();

If you add that, then it will optimize away the comparison.

[Bug libstdc++/109205] vector.resize( v.size() + 100 ) does unnecessary comparison

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

[Bug libstdc++/109205] vector.resize( v.size() + 100 ) does unnecessary comparison

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-03-20
             Status|UNCONFIRMED                 |NEW

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I guess we might as well do it for capacity too:

--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -985,7 +985,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
       size_type
       size() const _GLIBCXX_NOEXCEPT
-      { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
+      {
+       if (this->_M_impl._M_finish < this->_M_impl._M_start)
+         __builtin_unreachable();
+       return size_type(this->_M_impl._M_finish - this->_M_impl._M_start);
+      }

       /**  Returns the size() of the largest possible %vector.  */
       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
@@ -1071,8 +1075,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
       size_type
       capacity() const _GLIBCXX_NOEXCEPT
-      { return size_type(this->_M_impl._M_end_of_storage
-                        - this->_M_impl._M_start); }
+      {
+       if (this->_M_impl._M_end_of_storage < this->_M_impl._M_start)
+         __builtin_unreachable();
+       return size_type(this->_M_impl._M_end_of_storage
+                        - this->_M_impl._M_start);
+      }

       /**
        *  Returns true if the %vector is empty.  (Thus begin() would

[Bug libstdc++/109205] vector.resize( v.size() + 100 ) does unnecessary comparison

[redi at gcc dot gnu.org]

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

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Huh, but that causes a test to FAIL with -D_GLIBCXX_DEBUG

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


/home/jwakely/src/gcc/build/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/stl_vector.h:989:
error: no match for 'operator<' in '((const std::__cxx1998::vector<int,
Alloc<int> >*)this)->std::__cxx1998::vector<int, Alloc<int>
>::<anonymous>.std::__cxx1998::_Vector_base<int, Alloc<int>
>::_M_impl.std::__cxx1998::_Vector_base<int, Alloc<int>
>::_Vector_impl::<anonymous>.std::__cxx1998::_Vector_base<int, Alloc<int>
>::_Vector_impl_data::_M_finish < ((const std::__cxx1998::vector<int,
Alloc<int> >*)this)->std::__cxx1998::vector<int, Alloc<int>
>::<anonymous>.std::__cxx1998::_Vector_base<int, Alloc<int>
>::_M_impl.std::__cxx1998::_Vector_base<int, Alloc<int>
>::_Vector_impl::<anonymous>.std::__cxx1998::_Vector_base<int, Alloc<int>
>::_Vector_impl_data::_M_start' (operand types are 'const
std::__cxx1998::_Vector_base<int, Alloc<int> >::pointer' {aka 'const
std::allocator_traits<Alloc<int> >::pointer'} and 'const
std::__cxx1998::_Vector_base<int, Alloc<int> >::pointer' {aka 'const
std::allocator_traits<Alloc<int> >::pointer'})

[Bug libstdc++/109205] vector.resize( v.size() + 100 ) does unnecessary comparison

[redi at gcc dot gnu.org]

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

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

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

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I added hints to size() and capacity() and it caused regressions, see PR 110060

It makes it less likely for size() to be inlined, and causes:

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

[Bug libstdc++/109205] vector.resize( v.size() + 100 ) does unnecessary comparison

[redi at gcc dot gnu.org]

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

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #3)
> Huh, but that causes a test to FAIL with -D_GLIBCXX_DEBUG
> 
> FAIL: 23_containers/vector/59829.cc (test for excess errors)
> 
> 
> /home/jwakely/src/gcc/build/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/
> stl_vector.h:989: error: no match for 'operator<' in '((const
> std::__cxx1998::vector<int, Alloc<int> >*)this)->std::__cxx1998::vector<int,
> Alloc<int> >::<anonymous>.std::__cxx1998::_Vector_base<int, Alloc<int>
> >::_M_impl.std::__cxx1998::_Vector_base<int, Alloc<int>
> >::_Vector_impl::<anonymous>.std::__cxx1998::_Vector_base<int, Alloc<int>
> >::_Vector_impl_data::_M_finish < ((const std::__cxx1998::vector<int,
> Alloc<int> >*)this)->std::__cxx1998::vector<int, Alloc<int>
> >::<anonymous>.std::__cxx1998::_Vector_base<int, Alloc<int>
> >::_M_impl.std::__cxx1998::_Vector_base<int, Alloc<int>
> >::_Vector_impl::<anonymous>.std::__cxx1998::_Vector_base<int, Alloc<int>
> >::_Vector_impl_data::_M_start' (operand types are 'const
> std::__cxx1998::_Vector_base<int, Alloc<int> >::pointer' {aka 'const
> std::allocator_traits<Alloc<int> >::pointer'} and 'const
> std::__cxx1998::_Vector_base<int, Alloc<int> >::pointer' {aka 'const
> std::allocator_traits<Alloc<int> >::pointer'})

This was fixed by r14-1249-g8d2fa90a415676