[Bug middle-end/32667] builtin operator= generates memcpy with overlapping memory regions

[Bug middle-end/32667] builtin operator= generates memcpy with overlapping memory regions

[lu_zero at gentoo dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32667

lu_zero at gentoo dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |lu_zero at gentoo dot org

--- Comment #6 from lu_zero at gentoo dot org 2011-12-05 16:59:07 UTC ---
Doesn't seem.

Here a reduced testcase courtesy of Mans Rullgard

struct foo {
    int x[64];
};

void __attribute__((noinline)) foo(struct foo *a, struct foo *b)
{
    *a = *b;
}

int main(void)
{
    struct foo a = { 0 };
    foo(&a, &a);
    return 0;
}

[Bug middle-end/32667] builtin operator= generates memcpy with overlapping memory regions

[mans at mansr dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32667

Mans Rullgard <mans at mansr dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mans at mansr dot com

--- Comment #7 from Mans Rullgard <mans at mansr dot com> 2011-12-05 20:37:18 UTC ---
Note that the test case in comment #6 does not trigger the problem on x86 where
the copying is inlined. It does trigger on ARM and other targets where this
assignment results in a memcpy() call. All current stable releases show the
bug. I did not test with trunk.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32667

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|builtin operator= generates |block copy with exact
                   |memcpy with overlapping     |overlap is expanded as
                   |memory regions              |memcpy
      Known to fail|                            |4.7.0

--- Comment #8 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-12-06 08:44:46 UTC ---
This is a generic middle-end issue (at best).  There is at least one duplicate
of this bug (can't find it with a quick search).

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |msebor at gmail dot com

--- Comment #9 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 65029 has been marked as a duplicate of this bug. ***

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
One way to "fix" this is to emit the memcpy as

  if (p != q)
    memcpy (p, q, ...);

but of course that comes at a cost in code-size and runtime for no obvious good
reason (in practice).

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
And another way to fix this is add a new library entrypoint, that would have
the same semantics as memcpy, but would allow full overlap (dst == src).
When we e.g. expand this without a library call, we could do exactly what we do
for memcpy, because we know we do handle the dst == src case fine.  Similarly,
e.g. in glibc it could very well be just another alias to memcpy, because we
know it handles that too.  On targets which would not have the library function
we'd use the #c10 approach.  Of course, this would require coordination in
between glibc, gcc, valgrind, libsanitizer, memstomp etc.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[hugh at mimosa dot com]

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

D. Hugh Redelmeier <hugh at mimosa dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hugh at mimosa dot com

--- Comment #12 from D. Hugh Redelmeier <hugh at mimosa dot com> ---
JJ in #11 is right.

The compiler should never generate calls to functions with names in the user's
space.  That's because the user is allowed to (re)define anything with those
names and is not constrained to preserve expected semantics.

There should be a function in the reserved-to-system namespace that does what
is needed.  GCC should then call this function.

Let's say that GCC uses __memcpy.  The default standard definition of memcpy
could be a synonym (until redefinition) for __memcpy.

On the other hand, there are compile-time constraints on struct assignments
that could yield even better performance.  For example, GCC might know that the
object is a multiple of 8 bytes, aligned on an 8-byte boundary.  GCC would
certainly know that the struct's length is non-zero, conceptually eliminating
one test.  This suggests implementing specialized variants, perhaps having
names starting with __struct_assign.

(I know GCC has an extension allowing 0 length objects.  The assignment for
such objects could be eliminated.)

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[public at timruffing dot de]

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

Tim Ruffing <public at timruffing dot de> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |public at timruffing dot de

--- Comment #18 from Tim Ruffing <public at timruffing dot de> ---
Is there still interest in fixing this? This still leads to spurious Valgrind
warnings in the real world.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[rguenther at suse dot de]

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

--- Comment #19 from rguenther at suse dot de <rguenther at suse dot de> ---
On Wed, 9 Jun 2021, public at timruffing dot de wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=32667
> 
> Tim Ruffing <public at timruffing dot de> changed:
> 
>            What    |Removed                     |Added
> ----------------------------------------------------------------------------
>                  CC|                            |public at timruffing dot de
> 
> --- Comment #18 from Tim Ruffing <public at timruffing dot de> ---
> Is there still interest in fixing this? This still leads to spurious Valgrind
> warnings in the real world.

I don't think this is ever going to be "fixed" on the GCC side, instead
maybe valgrind should be at least given an option to ignore those cases.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |nyh at math dot technion.ac.il

--- Comment #20 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 108296 has been marked as a duplicate of this bug. ***

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[nyh at math dot technion.ac.il]

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

--- Comment #21 from Nadav Har'El <nyh at math dot technion.ac.il> ---
This old problem has become a real problem in gcc 12 with a real effect on
incorrect code generation, where code that copies an object was incorrectly
"optimized" to use __builtin_memcpy() instead of __builtin_memmove() even
though the source and destination objects may overlap - and it turns out that
__builtin_memcpy() may produce incorrect results for overlapping addresses.

This bug was discovered in the OSv project
https://github.com/cloudius-systems/osv/issues/1212 with code that doesn't
(obviously) call __builtin_memcpy() directly, but rather had a 27-character
type being copied and the compiler implemented this copy with a call to
__builtin_memcpy(). Here is an example of code which generates the wrong
results (note the missing "c" in the result and unexpectedly doubled "g"):

#include <cstdio>
int main(){
    char buf[128] = "0123456789abcdefghijklmnopqrstuvwxyz";
    struct [[gnu::packed]] data {
        char x[27];
    };
    void *p0 = buf;
    void *p1 = &buf[1];
    *static_cast<data*>(p0) = *static_cast<const data*>(p1);
    printf("%s", buf);
}

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[lopresti at gmail dot com]

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

--- Comment #22 from Patrick J. LoPresti <lopresti at gmail dot com> ---
I disagree that bug 108296 is a duplicate. That bug requires code that, at
least arguably, invokes undefined behavior. See e.g.
https://stackoverflow.com/q/7292862/ and https://stackoverflow.com/q/61070828/.

This bug is about clearly valid C++ code (object self-assignment) for which GCC
emits clearly invalid calls to memcpy() (with dest == src).

Now, I suspect what Andrew is thinking is that both of these bugs could be
resolved by invoking memmove() instead of memcpy(). That seems like a
reasonable idea to me, since small assignments get inlined and large
assignments can amortize the overhead.

But this bug could also be resolved in other ways, a few of which have been
suggested in these comments.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[post+gcc at ralfj dot de]

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

post+gcc at ralfj dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |post+gcc at ralfj dot de

--- Comment #23 from post+gcc at ralfj dot de ---
>  Is glibc community ready to provide such guarantee?

This is indeed a key question here I think. Currently GCC makes assumptions
that *even the libc produced by the same project* does not document as stable
guarantees. That's rather dissonant. The GNU project should at least within
itself come to a proper conclusion on the question of whether memcpy should be
UB or not when both pointers are equal. Right now we have everyone pointing at
everyone else, and users are left in the rain with their valgrind errors.

Ideally of course the C standard would be updated to ensure that slowly but
steadily, the memcpy contract is updated to match reality. That will take a
while, but given that this issue was filed 16 years ago (!), there clearly
would have been enough time. (If someone does, please join forces with the
clang people that are interested in getting C updated:
https://reviews.llvm.org/D86993#4585590).

But GNU controls glibc so there's not really any excuse for not updating those
docs, I think? glibc making such a move would be a great step towards
convincing valgrind and the C committee that memcpy should have defined
behavior when both pointers are equal.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[bugdal at aerifal dot cx]

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

Rich Felker <bugdal at aerifal dot cx> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bugdal at aerifal dot cx

--- Comment #24 from Rich Felker <bugdal at aerifal dot cx> ---
If the copy is such that gcc is happy to emit an external call to memcpy for
it, there is no significant size or performance cost to emitting a branch
checking for equality before making the call, and performing this branch would
greatly optimize the (maybe rare in the caller, maybe not) case of
self-assignment!

On the other hand, expecting the libc memcpy to make this check greatly
pessimizes every reasonable small use of memcpy with a gratuitous branch for
what is undefined behavior and should never appear in any valid program.

Fix it on the compiler side please.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[rguenther at suse dot de]

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

--- Comment #25 from rguenther at suse dot de <rguenther at suse dot de> ---
On Tue, 21 Nov 2023, bugdal at aerifal dot cx wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=32667
> 
> Rich Felker <bugdal at aerifal dot cx> changed:
> 
>            What    |Removed                     |Added
> ----------------------------------------------------------------------------
>                  CC|                            |bugdal at aerifal dot cx
> 
> --- Comment #24 from Rich Felker <bugdal at aerifal dot cx> ---
> If the copy is such that gcc is happy to emit an external call to memcpy for
> it, there is no significant size or performance cost to emitting a branch
> checking for equality before making the call, and performing this branch would
> greatly optimize the (maybe rare in the caller, maybe not) case of
> self-assignment!
> 
> On the other hand, expecting the libc memcpy to make this check greatly
> pessimizes every reasonable small use of memcpy with a gratuitous branch for
> what is undefined behavior and should never appear in any valid program.
> 
> Fix it on the compiler side please.

The only reasonable fix on the compiler side is to never emit memcpy
but always use memmove.  The pessimization of that compared to the
non-existing "real" issue with calling memcpy with exact overlap
is the reason for the non-action.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[bugdal at aerifal dot cx]

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

--- Comment #26 from Rich Felker <bugdal at aerifal dot cx> ---
> The only reasonable fix on the compiler side is to never emit memcpy but always use memmove.

No, it can literally just emit (equivalent at whatever intermediate form of):

cmp src,dst
je 1f
call memcpy
1:

in place of memcpy.

It can even optimize out that in the case where it's provable that they're not
equal, e.g. presence of restrict or one of the two objects not having had its
address taken/leaked.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[jakub at gcc dot gnu.org]

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

--- Comment #27 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Rich Felker from comment #26)
> > The only reasonable fix on the compiler side is to never emit memcpy but always use memmove.
> 
> No, it can literally just emit (equivalent at whatever intermediate form of):
> 
> cmp src,dst
> je 1f
> call memcpy
> 1:
> 
> in place of memcpy.

No, that is not a reasonable fix, because it severely pessimizes common code
for a theoretical only problem.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[bugdal at aerifal dot cx]

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

--- Comment #28 from Rich Felker <bugdal at aerifal dot cx> ---
> No, that is not a reasonable fix, because it severely pessimizes common code for a theoretical only problem.

Far less than a call to memmove (which necessarily has something comparable to
that and other unnecessary branches) pessimizes it.

I also disagree that it's severe. On basically any machine with branch
prediction, the branch will be predicted correctly all the time and has
basically zero cost. On the other hand, the branches in memmove could go
different ways depending on the caller, so it's much more
machine-capability-dependent whether they can be predicted.

In some sense the optimal thing to do is "nothing", just assuming it would be
hard to write a memcpy that fails on src==dest. However, at the very least this
precludes hardened memcpy trapping on src==dest, which might be a useful
hardening feature (or rather on a range test for overlapping, which would
happen to also catch exact overlap). So it would be nice if it were fixed.

FWIW, I don't think single branches are relevant to overall performance in
cases where the compiler is doing something reasonable by emitting a call to
memcpy to implement assignment. If the object is small enough that the branch
is relevant, the call overhead is even more of a big deal, and it should be
inlining loads/stores to perform the assignment.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[lopresti at gmail dot com]

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

--- Comment #29 from Patrick J. LoPresti <lopresti at gmail dot com> ---
(In reply to Jakub Jelinek from comment #27)
> 
> No, that is not a reasonable fix, because it severely pessimizes common code
> for a theoretical only problem.

The very existence of (and interest in) this bug report means it is obviously
not "a theoretical only problem".

And of course Rich Felker is correct that the cost of the obvious fix is
trivial and not remotely "severe".

But the bottom line is that GCC is emitting library calls that invoke undefined
behavior. At a minimum, GCC should document this non-standard requirement on
its runtime environment. Has anyone bothered to do that? Why not?

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[post+gcc at ralfj dot de]

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

--- Comment #30 from post+gcc at ralfj dot de ---
There have been several assertions above that a certain way to solve this
either has no performance cost at all or severe performance cost. That sounds
like we are missing data -- ideally, someone would benchmark the actual cost of
emitting that branch. It seems kind of pointless to just make assertions about
the impact of this change without real data.

> On the other hand, expecting the libc memcpy to make this check greatly pessimizes every reasonable small use of memcpy with a gratuitous branch for what is undefined behavior and should never appear in any valid program.

I don't think this is true. As far as I can see, the performance impact of
having memcpy support the src==dest case is zero -- the assembly generated by
the current implementations already supports that case. (At least I have not
seen any evidence to the contrary.) No new check in memcpy is required.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[rguenth at gcc dot gnu.org]

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

--- Comment #31 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Patrick J. LoPresti from comment #29)
> (In reply to Jakub Jelinek from comment #27)
> > 
> > No, that is not a reasonable fix, because it severely pessimizes common code
> > for a theoretical only problem.
> 
> The very existence of (and interest in) this bug report means it is
> obviously not "a theoretical only problem".
> 
> And of course Rich Felker is correct that the cost of the obvious fix is
> trivial and not remotely "severe".

But I didn't see a patch proposed to address this issue, which means it
doesn't seem to be trivial.

> But the bottom line is that GCC is emitting library calls that invoke
> undefined behavior. At a minimum, GCC should document this non-standard
> requirement on its runtime environment. Has anyone bothered to do that? Why
> not?

I think it's written down somewhere but I can't quickly find it (I also
wonder where exactly the best place to document would be - it's related
to porting GCC to a new target architecture I guess, not so much user-facing).

OTOH I see

@cindex @code{cpymem@var{m}} instruction pattern 
@item @samp{cpymem@var{m}}
...
The @code{cpymem@var{m}} patterns need not give special consideration
to the possibility that the source and destination strings might
overlap. These patterns are used to do inline expansion of
@code{__builtin_memcpy}.

which is possibly the closest piece we have and which fails to mention
exact overlap.  I'll propose an adjustment to this.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[fw at gcc dot gnu.org]

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

--- Comment #32 from Florian Weimer <fw at gcc dot gnu.org> ---
There's this in standards.texi:

Most of the compiler support routines used by GCC are present in
@file{libgcc}, but there are a few exceptions.  GCC requires the
freestanding environment provide @code{memcpy}, @code{memmove},
@code{memset} and @code{memcmp}.
Finally, if @code{__builtin_trap} is used, and the target does
not implement the @code{trap} pattern, then GCC emits a call
to @code{abort}.

Maybe that would be a place to mention this issue, too?

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[rguenther at suse dot de]

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

--- Comment #33 from rguenther at suse dot de <rguenther at suse dot de> ---
On Thu, 23 Nov 2023, fw at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=32667
> 
> --- Comment #32 from Florian Weimer <fw at gcc dot gnu.org> ---
> There's this in standards.texi:
> 
> Most of the compiler support routines used by GCC are present in
> @file{libgcc}, but there are a few exceptions.  GCC requires the
> freestanding environment provide @code{memcpy}, @code{memmove},
> @code{memset} and @code{memcmp}.
> Finally, if @code{__builtin_trap} is used, and the target does
> not implement the @code{trap} pattern, then GCC emits a call
> to @code{abort}.
> 
> Maybe that would be a place to mention this issue, too?

Will add.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[cvs-commit at gcc dot gnu.org]

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

--- Comment #34 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:7758cb4b53e8a33642709402ce582f769eb9fd18

commit r14-5772-g7758cb4b53e8a33642709402ce582f769eb9fd18
Author: Richard Biener <rguenther@suse.de>
Date:   Thu Nov 23 08:54:56 2023 +0100

    middle-end/32667 - document cpymem and memcpy exact overlap requirement

    The following amends the cpymem documentation to mention that exact
    overlap needs to be handled gracefully, also noting that the target
    runtime is expected to behave the same way where -ffreestanding
    docs mention the set of routines required.

            PR middle-end/32667
            * doc/md.texi (cpymem): Document that exact overlap of source
            and destination needs to work.
            * doc/standards.texi (ffreestanding): Mention memcpy is required
            to handle the exact overlap case.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[jakub at gcc dot gnu.org]

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

--- Comment #35 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Note, clang makes the same assumption apparently (while MSVC emits rep movs
inline and
ICC either that, or calls _intel_fast_memcpy).  As I mentioned earlier, if
glibc and other libraries provide an alias to memcpy or memmove (whichever
guarantees that exact overlap will be handled right in the implementation), GCC
could start using that instead of memcpy for those cases.  And it would be up
to the libraries to decide which implementation satisfies that.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[bugdal at aerifal dot cx]

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

--- Comment #36 from Rich Felker <bugdal at aerifal dot cx> ---
> the assembly generated by the current implementations already supports that case.

Our memcpy is not written in asm but in C, and it has the restrict qualifier on
src and dest. This entitles a compiler to emit asm equivalent to if (src==dest)
system("rm -rf /") if it likes. I don't know how you can write a valid C
implementation of memcpy that "doesn't care" about 100% overlap without giving
up restrict (and the benefits it entails) entirely.

If you're happy with a branch, you could probably take restrict off the
arguments and do something like:

if (src==dest) return;
const char *restrict src2 = src;
char *restrict dest2 = dest;
...

but that's shoving the branch into memcpy where it's a cost on every caller
making dynamic memcpys with potentially tiny size (like qsort, etc.) and
obeying the contract not to call with overlapping src/dest, rather than just
imposing it on bad callers.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[bugdal at aerifal dot cx]

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

--- Comment #37 from Rich Felker <bugdal at aerifal dot cx> ---
Also: has anyone even looked at what happens if a C memcpy with proper use of
restrict gets LTO-inlined into a caller with GCC-generated memcpy calll where
src==dest? That sounds like a case likely to blow up...

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[public at timruffing dot de]

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

--- Comment #38 from Tim Ruffing <public at timruffing dot de> ---
(In reply to Rich Felker from comment #36)
> If you're happy with a branch, you could probably take restrict off the
> arguments and do something like:
> 
> if (src==dest) return;
> const char *restrict src2 = src;
> char *restrict dest2 = dest;
> ...
> 


I'm not saying that such an implementation will be a good idea, but just a
remark: You could, in fact, keep restrict for the arguments in this case,
because the object pointed to by src and dest is not accessed at all when
src==dest. So this is correct code according to the standard. (The exact
semantics of restrict are a bit involved...)

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[public at timruffing dot de]

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

--- Comment #39 from Tim Ruffing <public at timruffing dot de> ---
(In reply to Rich Felker from comment #36)

> Our memcpy is not written in asm but in C, and it has the restrict qualifier
> on src and dest. 

For my curiosity, can you point me to this implementation? I couldn't find a
memcpy with restrict in the libc source, but I suspect that's just because I'm
not familiar with the code base.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[sjames at gcc dot gnu.org]

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

--- Comment #40 from Sam James <sjames at gcc dot gnu.org> ---
https://git.musl-libc.org/cgit/musl/tree/src/string/memcpy.c#n5

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[post+gcc at ralfj dot de]

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

--- Comment #41 from post+gcc at ralfj dot de ---
> This entitles a compiler to emit asm equivalent to if (src==dest) system("rm -rf /") if it likes.

No it does not. restrict causes UB if the two pointers are used to access the
same memory. It has nothing to do with whether the pointers are equal. So it
would have to be "if (src==dest && n>0)" and the compiler would have to first
prove that "n>0" implies that later accesses through both pointers occur at
offset 0 (and at least one of them is a write).

But it's still UB to call this the way GCC does, that much I agree with.

> Our memcpy is not written in asm but in C, and it has the restrict qualifier on src and dest.

The question is, does that qualifier help? If you remove it, does the generated
assembly change in any way, does the performance change? If not, it clearly
doesn't matter and can just be removed. If yes, then yeah compilers clearly
shouldn't call this with identical ranges.

Basically, compiler devs are claiming that libc can support the src==dest case
"for free", without any noticeable cost to other uses of the function. libc
devs are claiming that compilers can insert a branch that tests for equality,
without any noticeable cost. Both of these are testable hypotheses. I'm not a
compiler dev nor a libc dev, I just want to make sure that my compiler and my
libc use the same contract when talking to each other -- but I hope someone who
is a compiler dev or a libc dev can go and actually test these hypotheses,
rather than just speculating about it as has been happening so far.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[bugdal at aerifal dot cx]

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

--- Comment #42 from Rich Felker <bugdal at aerifal dot cx> ---
> I'm not saying that such an implementation will be a good idea, but just a remark: You could, in fact, keep restrict for the arguments in this case, because the object pointed to by src and dest is not accessed at all when src==dest. So this is correct code according to the standard. (The exact semantics of restrict are a bit involved...)

Nope, UB is invoked as soon as you evaluate src==dest, even with no
dereferencing. The semantics of restrict are such that the behavior of the code
must be unchanged if the pointer were replaced to a pointer to a relocated copy
of the pointed-to object. Since this would alter the result of the == operator,
that constraint is not satisfied and thereby the behavior is undefined.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[post+gcc at ralfj dot de]

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

--- Comment #43 from post+gcc at ralfj dot de ---
That is not my reading of the standard, but absent a proper (formal,
mathematical) spec I guess it is hard to tell.

With your reading, "if ((uintptr_t)src == 0x400400)" is UB, since changing the
"src" argument to a different copy located at that address would change the
execution. I strongly doubt that is the intent of the standard.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[bugdal at aerifal dot cx]

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

--- Comment #44 from Rich Felker <bugdal at aerifal dot cx> ---
My naive expectation is that "if ((uintptr_t)src == 0x400400)" is and should be
UB, but I may be misremembering the details of the formalism by which the spec
for restrict is implemented.

If so, that's kinda a help, but I still think you would want to remove restrict
from the arguments and apply it later, so that the fast-path head/tail copies
can avoid any branch, and the check for equality can be deferred until it's
known that there's a "body remainder" to copy. That's the part where you really
want the benefits of restrict anyway -- without restrict it's not vectorizable
because the compiler has to assume there might be nonexact overlap, in which
case reordering the loads and stores in any way could change the result.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[public at timruffing dot de]

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

--- Comment #45 from Tim Ruffing <public at timruffing dot de> ---
Ha, I didn't want to move to discussion about restrict, but as a final remark:
The formal semantics of restrict are not easy to parse and understand (see
https://www.iso-9899.info/n3047.html#6.7.3.1 ). But just the sentence "If L is
used to access the value of the object X that it designates, and X is also
modified (by any means), then the following requirements apply ..." should make
clear that no requirement is made at all if no object is modified. And this is
clearly the case for `if (src==dest) return;`

Besides that, I agree with what Ralf said:
> I'm not a compiler dev nor a libc dev, I just want to make sure that my compiler and my libc use the same contract when talking to each other -- but I hope someone who is a compiler dev or a libc dev can go and actually test these hypotheses, rather than just speculating about it as has been happening so far.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[rguenth at gcc dot gnu.org]

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

--- Comment #46 from Richard Biener <rguenth at gcc dot gnu.org> ---
I'll note that restrict on the parameters can help optimizing the copying loop
because you can then unroll and hoist loads before stores.  I'll also note that
almost all (important) targets implement memcpy with special assembler in libc.

But yes, a compiler might, seeing

void foo (char * __restrict d, char * s)
{
  *d = *s;
  if (d != s)
    abort ();
}

optimize the compare to always true because of the wording of the C standard
with regard to restrict.  GCC doesn't (yet) do this.  A compiler might also
transform

 foo (p, p);

to trap (as part of eliminating paths with undefined behavior) if it
can analyze foo inter-procedurally seeing that foo will always invoke
undefined behavior if d == s.

For memcpy the same would hold true but the compiler would need to know
that the size of the copy is not zero.

So yes, the most clean solution would be to have __forgiving_memcpy
possibly also allowing NULL pointers when n == 0 besides allowing
the exact overlap.  Its prototype wouldn't have restrict then or
nonnull.

This all doesn't change the fact that GCC up to now always assumed
memcpy with exact overlap is fine to do, so it's practically impossible
to change implementations without recompiling the world with a "fixed"
compiler.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[jakub at gcc dot gnu.org]

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

--- Comment #47 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #46)
> So yes, the most clean solution would be to have __forgiving_memcpy
> possibly also allowing NULL pointers when n == 0 besides allowing
> the exact overlap.  Its prototype wouldn't have restrict then or
> nonnull.

That is basically what I've argued above (however it is called), and completely
agree also on the NULL pointers when n == 0 case for it, I think that one came
up in the Honza vs. Jonathan libstdc++ discussions again recently.
And, ideally it could be implemented in libc as an alias to memcpy if e.g. the
assembly written memcpy satisfies all the requirements in it, but valgrind
could implement it separately and do there if (n == 0 || dst == src) return
dst; return memcpy (dst, src, n);
Of course, it would take some time, because it needs to be in libc first, gcc
needs to key on the versions which have it.  But then possibly in such case
could also fold
if (n != 0)
  memcpy (dst, src, n);
into
  __forgiving_memcpy (dst, src, n);
or __builtin_* variants thereof.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[post+gcc at ralfj dot de]

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

--- Comment #48 from post+gcc at ralfj dot de ---
> Note, clang makes the same assumption apparently (while MSVC emits rep movs inline and ICC either that, or calls _intel_fast_memcpy).

MSVC does the same thing as clang and GCC, if godbolt is to be trusted:
https://rust.godbolt.org/z/o7TevfvcY

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[post+gcc at ralfj dot de]

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

--- Comment #49 from post+gcc at ralfj dot de ---
Even glibc itself seems to use `restrict`:

https://codebrowser.dev/glibc/glibc/string/string.h.html#43

So the compiler building glibc might inadvertently rely on the memory written
through dst and the memory read through src being disjoint, making even the
perfectly-overlapping case UB (unless the implementation has a guard somewhere
that skips the copy when src==dst, but I was not able to find such a guard).

(The implementation at https://codebrowser.dev/glibc/glibc/string/memcpy.c.html
does not have the `restrict`, but it includes the string.h header and I think
the compiler is allowed to apply attributes from the declaration to the
definition. Or, alternatively, it might even be UB to have `restrict` in one
place and not the other: "All declarations that refer to the same object or
function shall have compatible type; otherwise, the behavior is undefined" [C23
§6.2.7.2] and "For two qualified types to be compatible, both shall have the
identically qualified version of a compatible type; the order of type
qualifiers within a list of specifiers or qualifiers does not affect the
specified type" [C23 §6.7.3.11].)

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[joseph at codesourcery dot com]

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

--- Comment #50 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
Qualifiers on function parameter types do not affect type compatibility or 
composite type (see 6.7.6.3#14).  I think they're only actually of 
significance in the definition; in a declaration they effectively serve as 
documentation.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[post+gcc at ralfj dot de]

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

--- Comment #51 from post+gcc at ralfj dot de ---
Oh great, I love it when one part of the C standard just adds exceptions to
statements made elsewhere. It's almost as if the authors want this to be as
hard to understand as possible...

That then raises the question which version of the signature is actually used
for building (and optimizing) the function: the one in the declaration or the
one in the definition. Does the standard have an answer to that?

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[post+gcc at ralfj dot de]

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

--- Comment #52 from post+gcc at ralfj dot de ---
For the point discussed earlier with the `restrict` in the musl memcpy, I had
another look at the definition of `restrict` and it's not entirely clear to me
any more that there is UB here. The restrict rules only apply to objects that
are "also modified (by any means)". Now the question is, does "*X = *X" modify
the object? Is a write always a modification or only if the stores
representation changes or only if the stored value changes?

If it requires a representation change, then "memcpy(x, x, n)" does not modify
anything, and hence there is no UB from "restrict".

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[rguenther at suse dot de]

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

--- Comment #53 from rguenther at suse dot de <rguenther at suse dot de> ---
On Tue, 28 Nov 2023, post+gcc at ralfj dot de wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=32667
> 
> --- Comment #51 from post+gcc at ralfj dot de ---
> Oh great, I love it when one part of the C standard just adds exceptions to
> statements made elsewhere. It's almost as if the authors want this to be as
> hard to understand as possible...
> 
> That then raises the question which version of the signature is actually used
> for building (and optimizing) the function: the one in the declaration or the
> one in the definition. Does the standard have an answer to that?

For avoidance of doubt the frontends should drop non-semantic qualifiers
from declarations then just in case the middle-end tries to apply
semantics there.  Like it does for const qualified reference arguments
(OK, that's not C but C++).  The middle-end also uses the qualifiers
for diagnostic purposes.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[rguenth at gcc dot gnu.org]

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

--- Comment #54 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to post+gcc from comment #52)
> For the point discussed earlier with the `restrict` in the musl memcpy, I
> had another look at the definition of `restrict` and it's not entirely clear
> to me any more that there is UB here. The restrict rules only apply to
> objects that are "also modified (by any means)". Now the question is, does
> "*X = *X" modify the object? Is a write always a modification or only if the
> stores representation changes or only if the stored value changes?
> 
> If it requires a representation change, then "memcpy(x, x, n)" does not
> modify anything, and hence there is no UB from "restrict".

Heh, interesting splitting of hairs ;)  I guess you need to file a DR with the
language to resolve this question ...

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[fw at gcc dot gnu.org]

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

--- Comment #55 from Florian Weimer <fw at gcc dot gnu.org> ---
(In reply to post+gcc from comment #52)
> For the point discussed earlier with the `restrict` in the musl memcpy, I
> had another look at the definition of `restrict` and it's not entirely clear
> to me any more that there is UB here. The restrict rules only apply to
> objects that are "also modified (by any means)". Now the question is, does
> "*X = *X" modify the object?

C11 says this:

| NOTE: “Modify” includes the case where the new value being stored is the same
as the previous value.

So at least this should be quite clear (although I think notes are supposedly
informal).

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[rearnsha at gcc dot gnu.org]

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

--- Comment #56 from Richard Earnshaw <rearnsha at gcc dot gnu.org> ---
I've never heard of a memcpy implementation that corrupts data if called with
memcpy (p, p, n).  (The problems come from partial overlaps where the direction
of the copy may matter).

Has anybody considered asking the standards committee to bless this as a
special exception?

Of course, if n is large, then performing an early test is still worthwhile,
but for small n, the cost of the check possibly exceeds the benefit of eliding
the copy.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[bugdal at aerifal dot cx]

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

--- Comment #57 from Rich Felker <bugdal at aerifal dot cx> ---
I think one could reasonably envision an implementation that does some sort of
vector loads/stores where, due to some performance constraint or avoiding
special casing for possible page boundary past the end of the copy, it only
wants to load N bits at a time, but the efficient store instruction always
stores a full vector of 2N bits. Of course, one could also argue quite
reasonably that this is a weird enough thing to do that the implementation
should then just check for src==dest and early-out.

I'm far less concerned about whether such mechanical breakage exists, and more
concerned about the consequences of LTO/whole-program-analysis where something
in the translation process can see the violated restrict qualifier, infer UB,
and blow everything up.

The change being requested here is really one of removing the restrict
qualification from the arguments and making a custom weaker condition. This may
in turn have consequences on what types of transformations are possible.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[jakub at gcc dot gnu.org]

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

--- Comment #58 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Rich Felker from comment #57)
> and more concerned about the consequences of LTO/whole-program-analysis where
> something in the translation process can see the violated restrict
> qualifier, infer UB, and blow everything up.

That can't happen, in GCC in GIMPLE these are represented as assignments, not
{__builtin_,}memcpy calls and are turned into the calls (or inline expansion of
the copying) only when being expanded into RTL.
All the LTO/whole program optimizations happen on GIMPLE, so at that point
nothing can be inferred from that because it simply isn't present in the IL and
only after all LTO & IPA optimizations are done individual functions go through
the rest of GIMPLE optimizations and then RTL ones.
The only exception to that is IPA-RA, which intra partition (for LTO, otherwise
within the TU) can take into account what hard registers are used/unused by
previously emitted
functions and take that knowledge into their callers emitted later; but for
those this is a library call like any other.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[rearnsha at gcc dot gnu.org]

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

--- Comment #59 from Richard Earnshaw <rearnsha at gcc dot gnu.org> ---
Memcpy must never write beyond the end of the specified buffer, even if reading
it is safe.  That wouldn't be thread safe.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[bugdal at aerifal dot cx]

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

--- Comment #60 from Rich Felker <bugdal at aerifal dot cx> ---
Nobody said anything about writing past end of buffer. Obviously you can't do
that.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[rearnsha at gcc dot gnu.org]

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

--- Comment #61 from Richard Earnshaw <rearnsha at gcc dot gnu.org> ---
Then I don't understand what you're trying to say in c57.

[Bug middle-end/32667] block copy with exact overlap is expanded as memcpy

[bugdal at aerifal dot cx]

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

--- Comment #62 from Rich Felker <bugdal at aerifal dot cx> ---
The process described there would have to end at least N bits before the end of
the destination buffer. The point was that it would destroy information
internal to the buffer at each step along the way, before it got to the end.