Bug 105651 - [12 Regression] bogus "may overlap" memcpy warning with std::string and operator+ at -O3
Summary: [12 Regression] bogus "may overlap" memcpy warning with std::string and opera...
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 13.0
: P2 normal
Target Milestone: 12.5
Assignee: Not yet assigned to anyone
URL:
Keywords: diagnostic
: 105545 106044 106350 106512 109563 (view as bug list)
Depends on:
Blocks: Wrestrict Wstringop-overflow
  Show dependency treegraph
 
Reported: 2022-05-18 23:38 UTC by James McKelvey
Modified: 2024-08-04 09:29 UTC (History)
23 users (show)

See Also:
Host:
Target:
Build:
Known to work: 11.1.0, 13.0
Known to fail: 12.1.0
Last reconfirmed: 2022-06-21 00:00:00


Attachments
Build.log showing error (1.35 KB, text/plain)
2022-05-18 23:38 UTC, James McKelvey
Details
save-temps (222.75 KB, application/x-xz)
2022-05-18 23:41 UTC, James McKelvey
Details
patch to work around the issue in the library (618 bytes, patch)
2022-08-19 04:13 UTC, Jason Merrill
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description James McKelvey 2022-05-18 23:38:47 UTC
Created attachment 52990 [details]
Build.log showing error

$ /usr/local/bin/g++ -v
Using built-in specs.
COLLECT_GCC=/usr/local/bin/g++
COLLECT_LTO_WRAPPER=/usr/local/libexec/gcc/x86_64-pc-cygwin/13.0.0/lto-wrapper.exe
Target: x86_64-pc-cygwin
Configured with: ./configure --enable-languages=c,c++ --enable-threads=posix
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 13.0.0 20220515 (experimental) (GCC)

$ uname
CYGWIN_NT-10.0

Windows 10.

Builds on gcc-11,12,13 with -std=c++17, but all three fail with c++20.

In file included from /usr/local/include/c++/13.0.0/string:40,
                 from /usr/local/include/c++/13.0.0/bits/locale_classes.h:40,
                 from /usr/local/include/c++/13.0.0/locale:39,
                 from Types.h:36,
                 from PatternDriverTop.h:42,
                 from PatternDriverTop.cc:28:
In static member function ‘static constexpr std::char_traits<char>::char_type* std::char_traits<char>::copy(char_type*, const char_type*, std::size_t)’,
    inlined from ‘static void std::basic_string<_CharT, _Traits, _Alloc>::_M_copy(_CharT*, const _CharT*, size_type) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]’ at /usr/local/include/c++/13.0.0/bits/cow_string.h:402:21,
    inlined from ‘std::basic_string<_CharT, _Traits, _Alloc>& std::basic_string<_CharT, _Traits, _Alloc>::insert(size_type, const _CharT*, size_type) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]’ at /usr/local/include/c++/13.0.0/bits/cow_string.h:3297:16,
    inlined from ‘std::basic_string<_CharT, _Traits, _Alloc>& std::basic_string<_CharT, _Traits, _Alloc>::insert(size_type, const _CharT*) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]’ at /usr/local/include/c++/13.0.0/bits/cow_string.h:1609:21,
    inlined from ‘PatternDriver::pdstring PatternDriver::_printable_by_ctype(const pdstring&, const std::locale&, const pdctype&, bool, bool)’ at PatternDriverTop.cc:589:22:
/usr/local/include/c++/13.0.0/bits/char_traits.h:431:56: error: ‘void* __builtin_memcpy(void*, const void*, long unsigned int)’ accessing 9223372036854775810 or more bytes at offsets [2, 9223372036854775807] and 1 may overlap up to 9223372036854775813 bytes at offset -3 [-Werror=restrict]
  431 |         return static_cast<char_type*>(__builtin_memcpy(__s1, __s2, __n));
      |                                        ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
cc1plus: all warnings being treated as errors
Comment 1 James McKelvey 2022-05-18 23:41:49 UTC
Created attachment 52991 [details]
save-temps
Comment 2 Andrew Pinski 2022-05-19 00:10:15 UTC
> Builds on gcc-11,12,13 with -std=c++17, but all three fail with c++20.

std::string changes slightly with C++20 and IIRC more inlining happens which is why the warning happens only with -std=c++20.
Comment 3 Richard Biener 2022-05-19 06:19:06 UTC
Both 9223372036854775807 and 9223372036854775810 are suspiciously large (don't fit 64bits).
Comment 4 James McKelvey 2022-05-24 17:48:34 UTC
Still fails with gcc-12-20220521 and gcc-13-20220522, but not gcc-11-20220520.
Comment 5 Jens Maurer 2022-06-07 14:58:40 UTC
Here's a more compact reproducer (gcc 12.1):

#include <string>

void f(const long long v)
{
   std::string line;
   line += " " + std::to_string(v);
}


$ g++ -Wall -O3 -std=c++20 -o test_warning.o -c test_warning.cxx
[...]
     inlined from 'void f(long long int)' at test_warning.cxx:9:15:
/opt/crosstool/x86_64-gcc-12.1.0-glibc-2.12.2/x86_64-unknown-linux-gnu/include/c++/12.1.0/bits/char_traits.h:431:56: 
warning: 'void* __builtin_memcpy(void*, const void*, long unsigned int)' 
accessing 9223372036854775810 or more bytes at offsets [2, 
9223372036854775807] and 1 may overlap up to 9223372036854775813 bytes 
at offset -3 [-Wrestrict]
   431 |         return static_cast<char_type*>(__builtin_memcpy(__s1, 
__s2, __n));
Comment 6 Andrew Pinski 2022-06-21 17:33:01 UTC
*** Bug 106044 has been marked as a duplicate of this bug. ***
Comment 7 Andrew Pinski 2022-06-21 17:38:41 UTC
Slightly more reduced testcase (still has system headers):
#include <string>

std::string f()
{
   return "_" + std::string(" ");
}
Comment 8 Martin Liška 2022-07-08 11:56:08 UTC
Started with r12-3347-g8af8abfbbace49e6 where new warning appeared:

    inlined from ‘std::string f()’ at pr105651.C:5:32:
/dev/shm/gcc-bisect-bin/usr/local/include/c++/12.0.0/bits/char_traits.h:355:56: error: ‘void* __builtin_memcpy(void*, const void*, long unsigned int)’ specified bound between 9223372036854775810 and 18446744073709551615 exceeds maximum object size 9223372036854775807 [-Werror=stringop-overflow=]
  355 |         return static_cast<char_type*>(__builtin_memcpy(__s1, __s2, __n));
      |                                        ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
Comment 9 Andrew Pinski 2022-07-19 23:10:42 UTC
*** Bug 106350 has been marked as a duplicate of this bug. ***
Comment 10 Richard Biener 2022-07-26 09:57:23 UTC
ISTR seeing this before.  We are quite confused by the standard library code
comparing the address of a string literal with the local buffer:

MEM[(char_type &)&D.42061 + 17] = 32;
if (&D.42061.D.33506._M_local_buf >= &MEM <const char[2]> [(void *)"_" + 1B])
  goto <bb 6>; [50.00%]
else
  goto <bb 7>; [50.00%]

if (&D.42061.D.33506._M_local_buf <= "_")
  goto <bb 8>; [50.00%]
else
  goto <bb 9>; [50.00%]

<bb 9> [local count: 21728216]:
_97 = &D.42061.D.33506._M_local_buf - "_";
if (_97 == 1)
  goto <bb 6>; [34.00%]
else
  goto <bb 10>; [66.00%]

and we are afraid of optimizing relational compares of distinct objects
(well, that's simply undefined and good QOI is to DWIM, simply leave the
broken code around if there's no good way to choose true or false).

This is all preceeded by an "overlap condition" working on integers
(so not undefined), so what might work is to aggressively simplify
relational compares of known distinct objects to __builtin_unreachable ()
(aka isolate the errorneous path).

<bb 2> [local count: 1073741824]:
MEM[(struct basic_string *)&D.42061] ={v} {CLOBBER};
MEM[(struct _Alloc_hider *)&D.42061] ={v} {CLOBBER};
MEM[(struct _Alloc_hider *)&D.42061]._M_p = &D.42061.D.33506._M_local_buf;
MEM[(char_type &)&D.42061 + 16] = 32;
D.42061._M_string_length = 1;
__x.25_69 = (long unsigned int) "_";
__y.26_70 = (long unsigned int) &D.42061.D.33506._M_local_buf;
if (__x.25_69 < __y.26_70)
  goto <bb 4>; [50.00%]
else
  goto <bb 3>; [50.00%]

<bb 3> [local count: 347651448]:
__x.25_72 = (long unsigned int) &MEM <char[16]> [(void *)&D.42061 + 17B];
if (__x.25_69 > __x.25_72)
  goto <bb 4>; [50.00%]
else
  goto <bb 5>; [50.00%]

Alternatively somehow re-combine the above overlap test and simplify
it statically.  We are getting into

Breakpoint 5, maybe_fold_and_comparisons (type=<boolean_type 0x7ffff68e2b28 bool>, code1=GE_EXPR, op1a=<ssa_name 0x7ffff4a88cf0 72>, op1b=<ssa_name 0x7ffff4a88c18 69>, code2=GE_EXPR, op2a=<ssa_name 0x7ffff4a88c18 69>, op2b=<ssa_name 0x7ffff4a88c60 70>, outer_cond_bb=<basic_block 0x7ffff4d69548 (2)>)

we do have a patterns optimizing an overlap test (but not statically folding)
with

/* For pointers @0 and @2 and nonnegative constant offset @1, look for
   expressions like:

   A: (@0 + @1 < @2) | (@2 + @1 < @0)
   B: (@0 + @1 <= @2) | (@2 + @1 <= @0)
...

unfortunately simple matching in match.pd falls foul of the PR105142 fix
given _72 is computed in the inner block and thus
maybe_fold_comparisons_from_match_pd is not going to pick that up.
Without that fix

(for cmp1 (lt le le lt)
     cmp2 (lt le lt le)
(simplify
 (bit_and (cmp1:c (convert@4 @0) (convert @1)) (cmp2:c (convert@5 @2) (convert @3)))
 (if (TREE_CODE (@0) == ADDR_EXPR
      && TREE_CODE (@1) == ADDR_EXPR
      && TREE_CODE (@2) == ADDR_EXPR
      && TREE_CODE (@3) == ADDR_EXPR
      && INTEGRAL_TYPE_P (TREE_TYPE (@4))
      && types_match (TREE_TYPE (@4), TREE_TYPE (@5)))
  (with { poly_int64 diff0, diff1; }
   (if (ptr_difference_const (@0, @3, &diff0)
        && ptr_difference_const (@1, @2, &diff1)
        && !ptr_derefs_may_alias_p (@0, @1))
    { constant_boolean_node (false, type); })))))

works to detect this for the case of invariant addresses which have the
offset included.  It would need to be extended for cases where the
increments are variable or the base address is not invariant (but common).

I'm going to improve the PR105142 fix.
Comment 11 Jonathan Wakely 2022-07-26 10:16:10 UTC
(In reply to Richard Biener from comment #10)
> ISTR seeing this before.

PR 105329 maybe?
Comment 12 Jakub Jelinek 2022-07-26 10:20:05 UTC
My preference would be still to make the overlap case out-of-line as mentioned in PR105329, but I don't have statistics on whether the overlap case is really cold in real-world.  If yes, it would make non-overlap case smaller and the overlap case tiny bit slower.
Comment 13 Jonathan Wakely 2022-07-26 10:36:29 UTC
I think the vast majority of string mutations involve inserting/appending/substituting an unrelated string, so non-overlapping. We can make your change on trunk.
Comment 14 rguenther@suse.de 2022-07-26 10:46:22 UTC
On Tue, 26 Jul 2022, jakub at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105651
> 
> --- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
> My preference would be still to make the overlap case out-of-line as mentioned
> in PR105329, but I don't have statistics on whether the overlap case is really
> cold in real-world.  If yes, it would make non-overlap case smaller and the
> overlap case tiny bit slower.

I would say so.  It's of course still beneficial to optimize the
overlap test if possible.  I'm now testing a series of changes required.
Comment 15 Richard Biener 2022-07-26 12:19:21 UTC
Note on trunk we get things way less optimized and end up with

  <bb 32> [local count: 695302893]:
  __x.38_144 = (long unsigned int) " ";
  __y.39_145 = (long unsigned int) _137;
  if (__x.38_144 < __y.39_145)
    goto <bb 34>; [50.00%]
  else
    goto <bb 33>; [50.00%]

  <bb 33> [local count: 347651447]:
  _146 = _137 + _128;
  __x.38_147 = (long unsigned int) _146;
  if (__x.38_147 < __x.38_144)
    goto <bb 34>; [50.00%]
  else
    goto <bb 39>; [50.00%]

and ptr_derefs_may_alias_p doesn't work there because to relate _137 and " "
points-to info would need to track STRING_CSTs but it
doesn't do that (we simply drop knowledge here, see find_what_var_points_to
string_id handling).
Comment 16 Jonathan Wakely 2022-08-03 09:57:05 UTC
*** Bug 106512 has been marked as a duplicate of this bug. ***
Comment 17 Jason Merrill 2022-08-19 04:13:06 UTC
Created attachment 53474 [details]
patch to work around the issue in the library

This patch tells the optimizer that the copy can't overlap, since it is having trouble figuring that out on its own.  This fixes the false positive.

It theoretically could deduce this from the previous two conditions: the first establishes that the end of the source is after the end of the destination; the second establishes that the beginning of the source is before the end of the destination.  So the source crosses the end of the destination, and so the length of the overlap is less than the length of the source.

There's probably a way to help the optimizer out without the __builtin_unreachable hammer, as for 98465; suggestions are welcome.

Turning off -Wrestrict just around the call to _M_copy also works, but this patch should also improve optimization.
Comment 18 Jason Merrill 2022-08-19 04:18:08 UTC
(In reply to Jason Merrill from comment #17)
> There's probably a way to help the optimizer out without the
> __builtin_unreachable hammer, as for 98465; suggestions are welcome.

..like https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104336#c1
Comment 19 Jakub Jelinek 2022-08-19 07:00:07 UTC
(In reply to Jason Merrill from comment #17)
> Created attachment 53474 [details]
> patch to work around the issue in the library

I've posted
https://gcc.gnu.org/pipermail/gcc-patches/2022-July/598896.html
patch for this, waiting for Jon's review.
Comment 20 Richard Biener 2022-08-19 07:19:04 UTC
See also https://gcc.gnu.org/pipermail/gcc-patches/2022-July/598839.html
and https://gcc.gnu.org/pipermail/gcc-patches/2022-July/598840.html
which I didn't pursue further since they didn't seem to catch the case reliably.
Comment 21 Richard Biener 2022-08-19 08:26:25 UTC
GCC 12.2 is being released, retargeting bugs to GCC 12.3.
Comment 22 Jonathan Wakely 2022-10-19 10:48:42 UTC
(In reply to Jakub Jelinek from comment #19)
> I've posted
> https://gcc.gnu.org/pipermail/gcc-patches/2022-July/598896.html
> patch for this, waiting for Jon's review.

N.B. that was committed as r13-2618-g723ef5a937dbab
Comment 23 Richard Biener 2022-10-19 11:08:47 UTC
The testcase from comment#5 is fixed on trunk, the preprocessed source of course not as the workaround was in the library.  Still, fixed in GCC 13.
Comment 24 Jonny Grant 2023-02-13 11:32:52 UTC
Hi, Glad it is fixed in trunk. I saw this fail in 12.2 - test case below.

#include <string>

typedef struct a_bc
{
    std::string a;
    std::string b;
} a_t;


void f()
{
    a_t c;

    c.a = " sdfsdf fsdfsdf fdfsfdsdf ";   // seems to need this long string to reproduce, down to 8 bytes it didn't
    c.b = "E";
}
Comment 25 Andrew Pinski 2023-04-20 04:44:41 UTC
*** Bug 109563 has been marked as a duplicate of this bug. ***
Comment 26 Jonathan Wakely 2023-04-20 12:00:25 UTC
*** Bug 105545 has been marked as a duplicate of this bug. ***
Comment 27 Richard Biener 2023-05-08 12:24:32 UTC
GCC 12.3 is being released, retargeting bugs to GCC 12.4.
Comment 28 GCC Commits 2023-06-21 12:18:55 UTC
The releases/gcc-12 branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:636795a6dfc17ead7b22b9f76b0fc47bdb9d357d

commit r12-9716-g636795a6dfc17ead7b22b9f76b0fc47bdb9d357d
Author: Jason Merrill <jason@redhat.com>
Date:   Thu Aug 18 23:53:16 2022 -0400

    libstdc++: avoid bogus -Wrestrict [PR105651]
    
            PR tree-optimization/105651
    
    libstdc++-v3/ChangeLog:
    
            * include/bits/basic_string.tcc (_M_replace): Add an assert
            to avoid -Wrestrict false positive.
Comment 29 Jonathan Wakely 2023-06-21 12:22:52 UTC
I've pushed the workaround from comment 17 to the gcc-12 branch.
Comment 30 Richard Biener 2024-06-20 09:05:12 UTC
GCC 12.4 is being released, retargeting bugs to GCC 12.5.