Page MenuHomePhabricator

[LangRef] Adjust guarantee for llvm.memcpy to also allow equal arguments.
ClosedPublic

Authored by fhahn on Aug 28 2020, 1:43 PM.

Details

Summary

This adjusts the description of llvm.memcpy to also allow operands
to be equal. This is in line with what Clang currently expects.

This change is intended to be temporary and followed by re-introduce
a variant with the non-overlapping guarantee for cases where we can
actually ensure that property in the front-end.

See the links below for more details:
http://lists.llvm.org/pipermail/cfe-dev/2020-August/066614.html
and PR11763.

Diff Detail

Unit TestsFailed

TimeTest
50 mslinux > LLVM.Transforms/DeadStoreElimination/MSSA::simple.ll
Script: -- : 'RUN: at line 2'; /mnt/disks/ssd0/agent/llvm-project/build/bin/opt < /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/DeadStoreElimination/MSSA/simple.ll -basic-aa -dse -enable-dse-memoryssa -S | /mnt/disks/ssd0/agent/llvm-project/build/bin/FileCheck /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/DeadStoreElimination/MSSA/simple.ll
90 mswindows > LLVM.Transforms/DeadStoreElimination/MSSA::simple.ll
Script: -- : 'RUN: at line 2'; c:\ws\w32-1\llvm-project\premerge-checks\build\bin\opt.exe < C:\ws\w32-1\llvm-project\premerge-checks\llvm\test\Transforms\DeadStoreElimination\MSSA\simple.ll -basic-aa -dse -enable-dse-memoryssa -S | c:\ws\w32-1\llvm-project\premerge-checks\build\bin\filecheck.exe C:\ws\w32-1\llvm-project\premerge-checks\llvm\test\Transforms\DeadStoreElimination\MSSA\simple.ll

Event Timeline

fhahn created this revision.Aug 28 2020, 1:43 PM
Herald added a project: Restricted Project. · View Herald Transcript
fhahn requested review of this revision.Aug 28 2020, 1:43 PM

How about making it explicit: The source location and the destination location may overlap.

aqjune added a subscriber: aqjune.Aug 28 2020, 2:06 PM
rsmith added a subscriber: rsmith.Aug 28 2020, 2:23 PM
rsmith added inline comments.
llvm/docs/LangRef.rst
12477–12478

I think we only want to allow the source and destination to be the same, and still want to disallow all other cases of overlap. We still want to be able to lower llvm.memcpy to memcpy not memmove.

llvm/lib/Analysis/BasicAliasAnalysis.cpp
982

This would presumably now be correct for memmove too.

989–994

These two ifs appear to now be equivalent to what would happen anyway in the general-case code below, and can presumably be deleted.

Would we need a change in MemCpyOptimizer too?
I see that the optimization is assuming memcpys don't allow partial overlapping (https://godbolt.org/z/h8jvo5 ).

arsenm added a subscriber: arsenm.Aug 28 2020, 2:41 PM

Why would we change this? What's the point of having separate memcpy and memmove intrinsics?

Why would we change this? What's the point of having separate memcpy and memmove intrinsics?

I'm reading this as clang mis-uses llvm.memcpy when it probably should be using llvm.memmove

Why would we change this? What's the point of having separate memcpy and memmove intrinsics?

I'm reading this as clang mis-uses llvm.memcpy when it probably should be using llvm.memmove

There is a longstanding assumption made by ~every compiler that memcpy(p, p, n) is safe. That's what we should be encoding here. We should not be removing all overlap restrictions.

Why would we change this? What's the point of having separate memcpy and memmove intrinsics?

I'm reading this as clang mis-uses llvm.memcpy when it probably should be using llvm.memmove

Can we detect overlap on frontend? And emit memmove in this case..

uenoku added a subscriber: uenoku.Aug 29 2020, 1:34 AM
fhahn updated this revision to Diff 288970.Aug 31 2020, 9:50 AM

Update to only allow operands to exactly overlap or not at all, as suggested. Simplified AA code.

Why would we change this? What's the point of having separate memcpy and memmove intrinsics?

I'm reading this as clang mis-uses llvm.memcpy when it probably should be using llvm.memmove

There is a longstanding assumption made by ~every compiler that memcpy(p, p, n) is safe. That's what we should be encoding here. We should not be removing all overlap restrictions.

Sounds good to me! I don't think allowing exact overlap is really helpful in terms of AA (because it means the operands either Must or No-Alias), but it might be helpful for a more efficient lowering/implementation of memcpy.

fhahn marked 3 inline comments as done.Aug 31 2020, 10:16 AM

Would we need a change in MemCpyOptimizer too?
I see that the optimization is assuming memcpys don't allow partial overlapping (https://godbolt.org/z/h8jvo5 ).

I think with the update (either completely overlap or not overlap at all), the example in the link should be still allowed (either %a and %b don't overlap or the first memcpy is a no-op)

llvm/docs/LangRef.rst
12477–12478

Thanks for the clarification!

llvm/lib/Analysis/BasicAliasAnalysis.cpp
982

yes probably. I can add that in a separate patch.

989–994

Looks like that indeed! Simplified,

jdoerfert added inline comments.Aug 31 2020, 10:55 AM
llvm/docs/LangRef.rst
12476–12479

"completely overlap or not overlap at all" is a weird way of saying: "be equal or not overlap at all". IMHO

fhahn updated this revision to Diff 289023.Aug 31 2020, 1:55 PM
fhahn marked 3 inline comments as done.

change 'exactly overlap or non-overlapping' -> 'equal or non-overlapping'

fhahn marked an inline comment as done.Aug 31 2020, 1:59 PM
fhahn added inline comments.
llvm/docs/LangRef.rst
12476–12479

I'm not really attached to the wording. Updated, thanks.

fhahn marked an inline comment as done.

wording looks good to me.

Thanks, I'm happy with this.

jyknight added inline comments.Aug 31 2020, 5:49 PM
llvm/test/Transforms/DeadStoreElimination/MSSA/memset-and-memcpy.ll
74

This comment needs updating too.

aqjune added a subscriber: nlopes.Aug 31 2020, 5:55 PM
fhahn updated this revision to Diff 289109.Sep 1 2020, 2:45 AM

Adjust comment, thanks!

nlopes added a comment.Sep 1 2020, 3:26 AM

Why would we change this? What's the point of having separate memcpy and memmove intrinsics?

I'm reading this as clang mis-uses llvm.memcpy when it probably should be using llvm.memmove

There is a longstanding assumption made by ~every compiler that memcpy(p, p, n) is safe. That's what we should be encoding here. We should not be removing all overlap restrictions.

If clang doesn't have a document stating the assumptions made about the run-time libraries (couldn't quickly find it), it might be useful to have one and mention this.

fhahn retitled this revision from [LangRef] Remove non-overlapping guarantee from memcpy. to [LangRef] Adjust guarantee for llvm.memcyp to also allow equal arguments..Sep 1 2020, 11:50 AM
fhahn edited the summary of this revision. (Show Details)

There is a longstanding assumption made by ~every compiler that memcpy(p, p, n) is safe. That's what we should be encoding here. We should not be removing all overlap restrictions.

If clang doesn't have a document stating the assumptions made about the run-time libraries (couldn't quickly find it), it might be useful to have one and mention this.

That sounds good, but I am not sure where this should be documented on the Clang side. I think this can also be done separately.

You could just a a file to clang docs with:
Clang assumes that memcpy(p, p, n) is safe.

xbolva00 retitled this revision from [LangRef] Adjust guarantee for llvm.memcyp to also allow equal arguments. to [LangRef] Adjust guarantee for llvm.memcpy to also allow equal arguments..Sep 1 2020, 12:02 PM

There is a longstanding assumption made by ~every compiler that memcpy(p, p, n) is safe. That's what we should be encoding here. We should not be removing all overlap restrictions.

If clang doesn't have a document stating the assumptions made about the run-time libraries (couldn't quickly find it), it might be useful to have one and mention this.

That sounds good, but I am not sure where this should be documented on the Clang side. I think this can also be done separately.

I agree that Clang should document this. Isn't there another technically-undefined assumption that LLVM makes about memcpy, like that it accepts bad pointers if the size is zero? Seems like that should be documented in the same place.

That place is probably the same general section of the manual that documents our implementation-defined behavior and implementation limits, which, er, doesn't currently exist.

Clang/LLVM accepts memcpy(NULL, NULL, 0) while GCC assumes dst/src pointers are not null. LLVM is conservative here.

Clang/LLVM accepts memcpy(NULL, NULL, 0) while GCC assumes dst/src pointers are not null. LLVM is conservative here.

We basically "only" assume the pointers are dereferenceable by as many bytes as you copy. That is, if you copy 0 we don't assume anything.

fhahn added a comment.Sep 1 2020, 1:45 PM

If clang doesn't have a document stating the assumptions made about the run-time libraries (couldn't quickly find it), it might be useful to have one and mention this.

That sounds good, but I am not sure where this should be documented on the Clang side. I think this can also be done separately.

I agree that Clang should document this. Isn't there another technically-undefined assumption that LLVM makes about memcpy, like that it accepts bad pointers if the size is zero? Seems like that should be documented in the same place.

That place is probably the same general section of the manual that documents our implementation-defined behavior and implementation limits, which, er, doesn't currently exist.

Should this happen together with this patch? We should add such a document, but that's probably better as a separate change, as it only concerns clang.

It should be separate, yeah.

rsmith added a comment.Sep 1 2020, 5:11 PM

Documentation patch for your consideration: https://reviews.llvm.org/D86993

fhahn added a comment.Sep 2 2020, 11:56 AM

Documentation patch for your consideration: https://reviews.llvm.org/D86993

Thank you very much for putting up the patch.

fhahn added a comment.Sep 4 2020, 7:11 AM

From the discussion so far it seems like we converged on the wording and changes in LLVM. Is there anything left to discuss or does this look good to go in?

nikic accepted this revision.Sep 4 2020, 12:05 PM
nikic added a subscriber: nikic.

LGTM

This revision is now accepted and ready to land.Sep 4 2020, 12:05 PM
fhahn added a comment.Sep 6 2020, 7:26 AM

Thanks everyone!

FYI: I've just run Alive2 (already patched for this new semantics) on the test suite and no regressions reported.