[Bug c++/101361] New: Bogus -Wstringop-overread warning with -O3

[Bug c++/101361] New: Bogus -Wstringop-overread warning with -O3

[boris at kolpackov dot net]

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

            Bug ID: 101361
           Summary: Bogus -Wstringop-overread warning with -O3
           Product: gcc
           Version: 11.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: boris at kolpackov dot net
  Target Milestone: ---

Created attachment 51113
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51113&action=edit
reproducer

g++ -Wall -Wextra -O3 -std=c++2a -o driver.o -c -fdirectives-only driver.ii

In file included from
/home/boris/work/build2/tests/modules/gcc2/gcc-install/include/c++/11.0.1/string:40,
                 from
/home/boris/work/build2/libbutl/tests/prefix-map/driver.cxx:7:
In static member function ‘static constexpr int
std::char_traits<char>::compare(const char_type*, const char_type*,
std::size_t)’,
    inlined from ‘int butl::compare_prefix<std::__cxx11::basic_string<_CharT>
>::compare(const C*, butl::compare_prefix<std::__cxx11::basic_string<_CharT>
>::size_type, const C*, butl::compare_prefix<std::__cxx11::basic_string<_CharT>
>::size_type) const [with C = char]’ at
/home/boris/work/build2/libbutl/libbutl/prefix-map.mxx:93:35,
    inlined from ‘bool butl::compare_prefix<std::__cxx11::basic_string<_CharT>
>::prefix(const K&, const K&) const [with C = char]’ at
/home/boris/work/build2/libbutl/libbutl/prefix-map.mxx:70:18,
    inlined from ‘std::pair<typename M::const_iterator, typename
M::const_iterator> butl::prefix_map_common<M>::find_sub(const key_type&) const
[with M = std::map<std::__cxx11::basic_string<char>, int,
butl::compare_prefix<std::__cxx11::basic_string<char> >,
std::allocator<std::pair<const std::__cxx11::basic_string<char>, int> > >]’ at
/home/boris/work/build2/libbutl/libbutl/prefix-map.txx:36:21:
/home/boris/work/build2/tests/modules/gcc2/gcc-install/include/c++/11.0.1/bits/char_traits.h:361:32:
warning: ‘int __builtin_memcmp_eq(const void*, const void*, long unsigned int)’
specified bound 18446744073709551615 exceeds maximum object size
9223372036854775807 [-Wstringop-overread]
  361 |         return __builtin_memcmp(__s1, __s2, __n);
      |                ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
In file included from
/home/boris/work/build2/tests/modules/gcc2/gcc-install/include/c++/11.0.1/string:55,
                 from
/home/boris/work/build2/libbutl/tests/prefix-map/driver.cxx:7:
/home/boris/work/build2/tests/modules/gcc2/gcc-install/include/c++/11.0.1/bits/basic_string.h:
In member function ‘std::pair<typename M::const_iterator, typename
M::const_iterator> butl::prefix_map_common<M>::find_sub(const key_type&) const
[with M = std::map<std::__cxx11::basic_string<char>, int,
butl::compare_prefix<std::__cxx11::basic_string<char> >,
std::allocator<std::pair<const std::__cxx11::basic_string<char>, int> > >]’:
/home/boris/work/build2/tests/modules/gcc2/gcc-install/include/c++/11.0.1/bits/basic_string.h:187:28:
note: source object allocated here
  187 |       { return _M_dataplus._M_p; }
      |                            ^~~~
In file included from
/home/boris/work/build2/tests/modules/gcc2/gcc-install/include/c++/11.0.1/string:40,
                 from
/home/boris/work/build2/libbutl/tests/prefix-map/driver.cxx:7:
In static member function ‘static constexpr int
std::char_traits<char>::compare(const char_type*, const char_type*,
std::size_t)’,
    inlined from ‘int butl::compare_prefix<std::__cxx11::basic_string<_CharT>
>::compare(const C*, butl::compare_prefix<std::__cxx11::basic_string<_CharT>
>::size_type, const C*, butl::compare_prefix<std::__cxx11::basic_string<_CharT>
>::size_type) const [with C = char]’ at
/home/boris/work/build2/libbutl/libbutl/prefix-map.mxx:93:35,
    inlined from ‘bool butl::compare_prefix<std::__cxx11::basic_string<_CharT>
>::prefix(const K&, const K&) const [with C = char]’ at
/home/boris/work/build2/libbutl/libbutl/prefix-map.mxx:70:18,
    inlined from ‘std::pair<typename M::iterator, typename M::iterator>
butl::prefix_map_common<M>::find_sub(const key_type&) [with M =
std::map<std::__cxx11::basic_string<char>, int,
butl::compare_prefix<std::__cxx11::basic_string<char> >,
std::allocator<std::pair<const std::__cxx11::basic_string<char>, int> > >]’ at
/home/boris/work/build2/libbutl/libbutl/prefix-map.txx:17:21:
/home/boris/work/build2/tests/modules/gcc2/gcc-install/include/c++/11.0.1/bits/char_traits.h:361:32:
warning: ‘int __builtin_memcmp_eq(const void*, const void*, long unsigned int)’
specified bound 18446744073709551615 exceeds maximum object size
9223372036854775807 [-Wstringop-overread]
  361 |         return __builtin_memcmp(__s1, __s2, __n);
      |                ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
In file included from
/home/boris/work/build2/tests/modules/gcc2/gcc-install/include/c++/11.0.1/string:55,
                 from
/home/boris/work/build2/libbutl/tests/prefix-map/driver.cxx:7:
/home/boris/work/build2/tests/modules/gcc2/gcc-install/include/c++/11.0.1/bits/basic_string.h:
In member function ‘std::pair<typename M::iterator, typename M::iterator>
butl::prefix_map_common<M>::find_sub(const key_type&) [with M =
std::map<std::__cxx11::basic_string<char>, int,
butl::compare_prefix<std::__cxx11::basic_string<char> >,
std::allocator<std::pair<const std::__cxx11::basic_string<char>, int> > >]’:
/home/boris/work/build2/tests/modules/gcc2/gcc-install/include/c++/11.0.1/bits/basic_string.h:187:28:
note: source object allocated here
  187 |       { return _M_dataplus._M_p; }
      |                            ^~~~

[Bug c++/101361] Bogus -Wstringop-overread warning with -O3

[Theodore.Papadopoulo at inria dot fr]

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

Theodore.Papadopoulo at inria dot fr changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |Theodore.Papadopoulo@inria.
                   |                            |fr

--- Comment #1 from Theodore.Papadopoulo at inria dot fr ---
Created attachment 51130
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51130&action=edit
Test case

[Bug c++/101361] Bogus -Wstringop-overread warning with -O3

[Theodore.Papadopoulo at inria dot fr]

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

--- Comment #2 from Theodore.Papadopoulo at inria dot fr ---
Same problem here with the attached test case and gcc version 11.1.1 20210531
(Red Hat 11.1.1-3).

[Bug libstdc++/101361] Bogus -Wstringop-overread warning with -O3

[msebor at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2021-07-12
                 CC|                            |jwakely.gcc at gmail dot com,
                   |                            |msebor at gcc dot gnu.org
     Ever confirmed|0                           |1
             Blocks|                            |97048
             Status|UNCONFIRMED                 |NEW
          Component|c++                         |libstdc++

--- Comment #3 from Martin Sebor <msebor at gcc dot gnu.org> ---
The warning triggers for the memcmp_eq() call in the IL below, so it's working
as designed, and the problem is that optimization exposes invalid but likely
unreachable code:

  _77 = __builtin_memcmp_eq (_27, _86, 18446744073709551615);

The test case in attachment 51130 has the same issue:

  <bb 3> [local count: 1013569139]:
  # i_141 = PHI <i_16(12), _23(2)>
  # prephitmp_26 = PHI <pretmp_32(12), _11(2)>
  D.47043 ={v} {CLOBBER};
  MEM[(struct _Alloc_hider *)&D.47043] ={v} {CLOBBER};
  MEM[(struct _Alloc_hider *)&D.47043]._M_p = &MEM <char[16]> [(void *)&D.47043
+ 16B];
  _46 = MEM[(const struct basic_string *)s2_10(D)]._M_dataplus._M_p;
  _50 = MIN_EXPR <prephitmp_26, i_141>;
  _51 = _46 + _50;
  std::__cxx11::basic_string<char>::_M_construct.isra (&D.47043, _46, _51);
  _21 = D.47043._M_string_length;
  _22 = D.47043._M_dataplus._M_p;
  _18 = MEM[(const struct basic_string *)s1_7(D)]._M_string_length;
  _19 = MEM[(const struct basic_string *)s1_7(D)]._M_dataplus._M_p;
  if (_18 >= _21)
    goto <bb 4>; [33.00%]
  ...

   <bb 4> [local count: 334477814]:
  _130 = .SUB_OVERFLOW (_18, _21);
  _40 = REALPART_EXPR <_130>;
  _2 = IMAGPART_EXPR <_130>;
  if (_2 != 0)
    goto <bb 5>; [0.04%]
  else
    goto <bb 6>; [99.96%]

  ...
  <bb 6> [local count: 334344023]:
  if (_21 != 18446744073709551615)
    goto <bb 17>; [34.00%]
  else
    goto <bb 20>; [66.00%]
  ...
  <bb 20> [local count: 220667054]:
  _125 = _19 + _40;
  _107 = __builtin_memcmp_eq (_125, _22, 18446744073709551615);

The IL is the result of the string ends_with function passing npos to compare
as a shorthand for "the rest of the string:"

      bool
      ends_with(basic_string_view __x) const noexcept
      {
        return this->size() >= __x.size()
          && this->compare(this->size() - __x.size(), npos, __x) == 0;          
      }

Getting rid of npos also avoid the warning.  I think the following should be
equivalent:

      bool
      ends_with(basic_string_view __x) const noexcept
      {
        return this->size() >= __x.size()
          && this->compare(this->size() - __x.size(), __x.size(), __x) == 0;    
      }

Jonathan, would this (or something like it) work?


Referenced Bugs:

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

[Bug libstdc++/101361] Bogus -Wstringop-overread warning with -O3

[redi at gcc dot gnu.org]

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

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
It seems acceptable, but isn't the diagnostic bug still there if users write
exactly the same code? The use of npos there is valid.

[Bug libstdc++/101361] Bogus -Wstringop-overread warning with -O3

[redi at gcc dot gnu.org]

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

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This would be better, because it avoids the redundant range checking done when
this->compare calls this->substr:

      {
        const auto __len = this->size();
        const auto __xlen = __x.size();
        return __len >= __xlen
          && traits_type::compare(end() - __xlen, __x.data(), __xlen) == 0;
      }

But there's still a bug if the compiler warns about unreachable code. The npos
is passed to substr as __n which does:

const size_type __rlen = std::min(__n, _M_len - __pos);

So there is no way we ever pass that value to memcmp. From my uninformed point
of view this seems like a problem with jump threading vs VRP and changing
libstdc++ just sweeps it under the rug.

[Bug libstdc++/101361] Bogus -Wstringop-overread warning with -O3

[redi at gcc dot gnu.org]

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

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
And that change only helps the testcase in comment 1, not the original one in
comment 0.

[Bug libstdc++/101361] Bogus -Wstringop-overread warning with -O3

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 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:4d3eaeb4f505b0838c673ee28e7dba8687fc8272

commit r12-2285-g4d3eaeb4f505b0838c673ee28e7dba8687fc8272
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Jul 13 12:21:27 2021 +0100

    libstdc++: Simplify basic_string_view::ends_with [PR 101361]

    The use of npos triggers a diagnostic as described in PR c++/101361.
    This change replaces the use of npos with the exact length, which is
    already known. We can further simplify it by inlining the effects of
    compare and substr, avoiding the redundant range checks in the latter.

    Signed-off-by: Jonathan Wakely <jwakely@redhat.com>

    libstdc++-v3/ChangeLog:

            PR c++/101361
            * include/std/string_view (ends_with): Use traits_type::compare
            directly.

[Bug libstdc++/101361] Bogus -Wstringop-overread warning with -O3

[msebor at gcc dot gnu.org]

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

--- Comment #8 from Martin Sebor <msebor at gcc dot gnu.org> ---
The warning depends on the optimizer for eliminating unreachable code but not
all of it can be.  For example, the abort below isn't.  In theory it could be
but with longer strings that require memory allocation it gets harder.  As
discussed in pr98465, some sort of an attribute telling GCC that a and b's data
are disjoint might help.

void g (void)
{
  std::string a ("abcd");
  std::string b (a);
  if (a != b)
    __builtin_abort ();
}

In general, code that depends on pointer relationships is not handled optimally
in GCC.  Some unreachable code is introduced by GCC itself as a result of
passes like jump threading and that probably could be avoided.

[Bug libstdc++/101361] Bogus -Wstringop-overread warning with -O3

[cvs-commit at gcc dot gnu.org]

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

--- 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:96205c97294d5db94bd89cd731830058d9c49abd

commit r11-8741-g96205c97294d5db94bd89cd731830058d9c49abd
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Jul 13 12:21:27 2021 +0100

    libstdc++: Simplify basic_string_view::ends_with [PR 101361]

    The use of npos triggers a diagnostic as described in PR c++/101361.
    This change replaces the use of npos with the exact length, which is
    already known. We can further simplify it by inlining the effects of
    compare and substr, avoiding the redundant range checks in the latter.

    Signed-off-by: Jonathan Wakely <jwakely@redhat.com>

    libstdc++-v3/ChangeLog:

            PR c++/101361
            * include/std/string_view (ends_with): Use traits_type::compare
            directly.

    (cherry picked from commit 4d3eaeb4f505b0838c673ee28e7dba8687fc8272)

[Bug libstdc++/101361] Bogus -Wstringop-overread warning with -O3

[cvs-commit at gcc dot gnu.org]

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

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

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

commit r10-9982-ga8ae5dbc60eedade3514e51e3cb35fd28ec1d4c8
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Jul 13 12:21:27 2021 +0100

    libstdc++: Simplify basic_string_view::ends_with [PR 101361]

    The use of npos triggers a diagnostic as described in PR c++/101361.
    This change replaces the use of npos with the exact length, which is
    already known. We can further simplify it by inlining the effects of
    compare and substr, avoiding the redundant range checks in the latter.

    Signed-off-by: Jonathan Wakely <jwakely@redhat.com>

    libstdc++-v3/ChangeLog:

            PR c++/101361
            * include/std/string_view (ends_with): Use traits_type::compare
            directly.

    (cherry picked from commit 4d3eaeb4f505b0838c673ee28e7dba8687fc8272)

[Bug c++/101361] Bogus -Wstringop-overread warning with -O3

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|libstdc++                   |c++

--- Comment #11 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Changing component back to c++ for the remaining issue with the original
testcase in comment 0.

[Bug c++/101361] Bogus -Wstringop-overread warning with -O3

[mail+gnu at tzik dot jp]

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

Taiju Tsuiki <mail+gnu at tzik dot jp> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mail+gnu at tzik dot jp

--- Comment #12 from Taiju Tsuiki <mail+gnu at tzik dot jp> ---
Created attachment 54711
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54711&action=edit
A reproducer of an inaccurate -Wstringop-overread

[Bug c++/101361] Bogus -Wstringop-overread warning with -O3

[mail+gnu at tzik dot jp]

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

--- Comment #13 from Taiju Tsuiki <mail+gnu at tzik dot jp> ---
I saw a similar inaccurate -Wstringop-overread warning with a smaller
reproducer (attached).
https://wandbox.org/permlink/EPjH0ZPoA4EWky0e

Reproducing gcc was tip of trunk (
https://github.com/gcc-mirror/gcc/commits/33fb1625992ba8180b42988e714460bcab08ca0f
),
and compile options and the error were:
$ g++ -Werror -O3 -std=c++20 -c foo.cc
In function ‘auto operator<=>(const V&, const V&)’,
    inlined from ‘Node* foo(Node*, const V&)’ at minify2/foo.cc:33:17:
minify2/foo.cc:20:36: error: ‘int __builtin_memcmp(const void*, const void*,
long unsigned int)’ specified bound [9223372036854775808, 18446744073709551615]
exceeds maximum object size 9223372036854775807 (9) 
[-Werror=stringop-overread]
   20 |     const auto c = __builtin_memcmp(x.beg, y.beg, len) <=> 0;
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
minify2/foo.cc:17:15: note: source object allocated here
   17 |   }(x.end - x.beg, y.end - y.beg);
      |             ~~^~~

$ cat foo.cc
#include <compare>

struct Res {
  long min;
  std::strong_ordering cmp;
};

struct V {
  const unsigned char* beg = nullptr;
  const unsigned char* end = nullptr;
};

auto operator<=>(const V& x, const V& y) {
  const auto [len, lencmp] = [&](long len_x, long len_y) {
    auto c = len_x <=> len_y;
    return Res{c > 0 ? len_y : len_x, c};
  }(x.end - x.beg, y.end - y.beg);

  if (len) {
    const auto c = __builtin_memcmp(x.beg, y.beg, len) <=> 0;
    if (c != 0)
      return c;
  }
  return lencmp;
}

struct Node {
  Node* next = nullptr;
  V v;
};

Node* foo(Node* x, const V& k) {
  while (x && k < x->v)
    x = x->next;
  return x;
}