[memcpyopt] Memcpy-memcpy dependence isn't detected across basic blocks

[sunfish]

Summary

This picks up the patch from https://reviews.llvm.org/D23470 and updates it to address the review feedback provided there.

This is a very simple patch that just hooks up memcpyopt's existing logic for optimizing memcpys, which already uses memdep, to memdep's existing logic for doing non-local queries. This notably allows it to eliminate many more llvm.memcpy calls in common Rust code, often by 20-30%.

[• dberlin]

1. non-local calls in GVN are the cause of pretty much all of it's massive slowdown.

Have you measured the effect this has on larger memory-using testcases?

2. If you are interested, someone already ported it to memoryssa:

https://reviews.llvm.org/D26739

(Bryant appears to have disappeared, sadly :( )

[sunfish]

In D38374#883738, @dberlin wrote:

1. non-local calls in GVN are the cause of pretty much all of it's massive slowdown.

Have you measured the effect this has on larger memory-using testcases?

I've measured compile times on some C++ and Rust testcases, and it doesn't appear to significantly slow down -O2. memcpyopt remains under 1% of the time, according to -time-passes.

2. If you are interested, someone already ported it to memoryssa:

https://reviews.llvm.org/D26739

That's interesting, though I'm still interested in the focused and incremental patch here.

[• dberlin]

In D38374#883874, @sunfish wrote:

In D38374#883738, @dberlin wrote:

1. non-local calls in GVN are the cause of pretty much all of it's massive slowdown.

Have you measured the effect this has on larger memory-using testcases?

I've measured compile times on some C++ and Rust testcases, and it doesn't appear to significantly slow down -O2. memcpyopt remains under 1% of the time, according to -time-passes.

I'm not opposed if we are willing to revert it.

2. If you are interested, someone already ported it to memoryssa:

https://reviews.llvm.org/D26739

That's interesting, though I'm still interested in the focused and incremental patch here.

Okay. You said"It might be desirable to use MemorySSA, however MemCpyOpt is currently using MemoryDependenceAnalysis for everything, and it seems desirable to avoid using a mix of both within the same pass, and updating the whole pass to use MemorySSA is a bigger project than I'm hoping to take on here."

1. There's now a way to do that, with pretty much no work.
2. Chandler specifically requested that passes be mixed with an option to turn it on off.

So ....

[sunfish]

In D38374#883899, @dberlin wrote:

In D38374#883874, @sunfish wrote:

In D38374#883738, @dberlin wrote:

1. non-local calls in GVN are the cause of pretty much all of it's massive slowdown.

Have you measured the effect this has on larger memory-using testcases?

I've measured compile times on some C++ and Rust testcases, and it doesn't appear to significantly slow down -O2. memcpyopt remains under 1% of the time, according to -time-passes.

I'm not opposed if we are willing to revert it.

Is that approval? :-)

2. If you are interested, someone already ported it to memoryssa:

https://reviews.llvm.org/D26739

That's interesting, though I'm still interested in the focused and incremental patch here.

Okay. You said"It might be desirable to use MemorySSA, however MemCpyOpt is currently using MemoryDependenceAnalysis for everything, and it seems desirable to avoid using a mix of both within the same pass, and updating the whole pass to use MemorySSA is a bigger project than I'm hoping to take on here."

1. There's now a way to do that, with pretty much no work.
2. Chandler specifically requested that passes be mixed with an option to turn it on off.

So ....

Indeed maybe it wouldn't be as much work as I assumed. That said, I'm still interested in pursuing the current incremental, focused, and simple patch first.

[• dberlin]

So, if the work is done (I think you would have to change some getDefiningAccess calls to getClobberingAccess), and it works, i'd prefer for us to just do that and declare victory.
If it's *not* done, okay, fine, that sucks but not gonna hold up the world here.

Everyone always wants to just do the small change they want, You know this.
Part of doing the review is to say "well, that's nice, but we should make sure that's really a good thing for llvm as a whole".
Otherwise, tragedy of the commons and all that.
So i'd like to understand if the other patch solves your problem before i approve this one.

[sunfish]

Your suggestions above both involve adding functionality under a flag/option. That alone makes them different situations from just landing the current patch, in terms of seeing the work all the way through into production.

I have a simple, small, focused, incremental patch. It makes a significant improvement for some use cases. I have addressed all the concerns raised here about the patch itself, and am happy to address any others that are raised. The patch doesn't make anything about the MemorySSA-based patches harder to work on.

[• dberlin]

"Your suggestions above both involve adding functionality under a flag/option. That alone makes them different situations from just landing the current patch, in terms of seeing the work all the way through into production.
"

(Rust could easily enable that option, of course)
Past that, yes, it is.
But like I said, that's sometimes how you prevent a tragedy of the commons.

"The patch doesn't make anything about the MemorySSA-based patches harder to work on"
First, of course it does.
It's yet another thing to keep working or replace. Both in in time spend keeping this working and fixing issues it exposes over time vs spending improving the infrastructure, and in cost to build a replacement.

You are not signing up to maintain memcpyopt and improve it. That's literally what you are saying above. You are making an improvement you want and then going to the next thing. You see that as an argument in favor of this patch: You can just commit it and move on, and leave the maintenance/support to others.
I'm not saying that as a value judgement, but as an explanation of why it's not anywhere near as simple as you make it out to be.

What you've said is just another way of saying "I don't want to have to sign up for that". Which again, i get. Really!
But if you want the people who basically *have signed up* to fix bugs and keep this stuff working, to be willing to accept it, it also means helping them out time to time.

So if you want me to approve it, i'd like to know it's the right path. Small or large. my line has to be drawn somewhere, otherwise, everything just incrementally gets bigger without any stopping point or design reconsideration.
This is where i am drawing the line for me to approve it - knowing that a thing we believe is a better path doesn't already solve your problem.
I haven't actually asked you to go productionize that (despite your concern that i haven). I've asked you simply to test whether it works and whether that path is feasible. If it works, in fact, i'm happy to commit to productionizing and getting it in in the next week or so.

If someone else who maintains this stuff wants to draw a different line and be more pragmatic, that's fine by me too.
I'm only telling you what i would want to see in this case.

[sunfish]

I've asked you simply to test whether it works and whether that path is feasible. If it works, in fact, i'm happy to commit to productionizing and getting it in in the next week or so.

Ok. I've now tested the patch in https://reviews.llvm.org/D26739 for the use cases that motivated the original patch here, and it does indeed address them.

[sunfish]

Friendly ping :-). I confirmed that the MemorySSA-based patch does implement the optimization. In fact, it tries not to, however it doesn't try hard enough, and the optimization happens anyway. It passes all the tests here as-is.

[sunfish]

Friendly ping! Anyone interested in taking a look?

[sunfish]

Friendly ping! Anyone interested in taking a look?

[sanjoy]

lib/Analysis/MemoryDependenceAnalysis.cpp

925 ↗

(On Diff #117025)

Would it be better to call this getNonLocalPointerDependencyFrom, in line with getPointerDependencyFrom?

lib/Transforms/Scalar/MemCpyOptimizer.cpp

1240 ↗

(On Diff #117025)

Why not push this SmallVector into the if block?

1274 ↗

(On Diff #117025)

IIUC, this may try to create illegal IR (def not dominating use) if it finds the non-local memset via a backedge since it tries to create a memset before the memcpy using the memset's value operand, which may not dominate the memcpy with your change.

[sunfish]

• Sink NonLocalDepResults smallvectors into their if blocks.
• Rename getSpecificNonLocalPointerDependency to getNonLocalPointerDependencyFrom

[sunfish]

Thanks for taking a look!

lib/Analysis/MemoryDependenceAnalysis.cpp

925 ↗

(On Diff #117025)

Sure.

lib/Transforms/Scalar/MemCpyOptimizer.cpp

1240 ↗

(On Diff #117025)

Done.

1274 ↗

(On Diff #117025)

If the memset doesn't dominate the memcpy, the non-local dependence results reflect this. For example, in

for (...) {
    memcpy(out, buffer, size);
    memset(buffer, 0, size);
}

the memcpy depends on the memset around the backend, but memdep reports two dependencies: the memcpy on the backedge, but also whatever there is on the loop entry edge, so the code in this patch requiring a single dependency doesn't accept it.

[sanjoy]

lib/Transforms/Scalar/MemCpyOptimizer.cpp

1274 ↗

(On Diff #117025)

Ok, can you then add an assert that SrcDepInfo.getInst() dominates M (specifically in the cases where you computed it from a singular non-local dependency)?

[sunfish]

lib/Transforms/Scalar/MemCpyOptimizer.cpp

1274 ↗

(On Diff #117025)

Makes sense. I've now added the asserts.

[sunfish]

Thanks for your help!

llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp

MemoryDependenceResults::getNonLocalCallDependency(CallSite QueryCS) {
 
   return Cache;
 }
 
 void MemoryDependenceResults::getNonLocalPointerDependency(
     Instruction *QueryInst, SmallVectorImpl<NonLocalDepResult> &Result) {
   const MemoryLocation Loc = MemoryLocation::get(QueryInst);
   bool isLoad = isa<LoadInst>(QueryInst);
+  return getNonLocalPointerDependencyFrom(QueryInst, Loc, isLoad, Result);
+}
+
+void MemoryDependenceResults::getNonLocalPointerDependencyFrom(
+    Instruction *QueryInst,
+    const MemoryLocation &Loc,
+    bool isLoad,
+    SmallVectorImpl<NonLocalDepResult> &Result) {
   BasicBlock *FromBB = QueryInst->getParent();
   assert(FromBB);
 
   assert(Loc.Ptr->getType()->isPointerTy() &&
          "Can't get pointer deps of a non-pointer!");
   Result.clear();
   {
     // Check if there is cached Def with invariant.group. FIXME: cache might be

llvm/trunk/lib/Transforms/Scalar/MemCpyOptimizer.cpp

bool MemCpyOptPass::processMemCpyMemCpyDependence(MemCpyInst *M,
   //    memcpy(c <- a)
   // It would be invalid to transform the second memcpy into memcpy(c <- b).
   //
   // TODO: If the code between M and MDep is transparent to the destination "c",
   // then we could still perform the xform by moving M up to the first memcpy.
   //
   // NOTE: This is conservative, it will stop on any read from the source loc,
   // not just the defining memcpy.
-  MemDepResult SourceDep =
-      MD->getPointerDependencyFrom(MemoryLocation::getForSource(MDep), false,
+  MemoryLocation SourceLoc = MemoryLocation::getForSource(MDep);
+  MemDepResult SourceDep = MD->getPointerDependencyFrom(SourceLoc, false,
                                                         M->getIterator(), M->getParent());
+
+  if (SourceDep.isNonLocal()) {
+    SmallVector<NonLocalDepResult, 2> NonLocalDepResults;
+    MD->getNonLocalPointerDependencyFrom(M, SourceLoc, /*isLoad=*/false,
+                                         NonLocalDepResults);
+    if (NonLocalDepResults.size() == 1) {
+      SourceDep = NonLocalDepResults[0].getResult();
+      assert((!SourceDep.getInst() ||
+              LookupDomTree().dominates(SourceDep.getInst(), M)) &&
+             "when memdep returns exactly one result, it should dominate");
+    }
+  }
+
   if (!SourceDep.isClobber() || SourceDep.getInst() != MDep)
     return false;
 
   // If the dest of the second might alias the source of the first, then the
   // source and dest might overlap.  We still want to eliminate the intermediate
   // value, but we have to generate a memmove instead of memcpy.
   bool UseMemMove = false;
   if (!AA.isNoAlias(MemoryLocation::getForDest(M),
if (CallInst *C = dyn_cast<CallInst>(DepInfo.getInst())) {
       }
     }
   }
 
   MemoryLocation SrcLoc = MemoryLocation::getForSource(M);
   MemDepResult SrcDepInfo = MD->getPointerDependencyFrom(
       SrcLoc, true, M->getIterator(), M->getParent());
 
+  if (SrcDepInfo.isNonLocal()) {
+    SmallVector<NonLocalDepResult, 2> NonLocalDepResults;
+    MD->getNonLocalPointerDependencyFrom(M, SrcLoc, /*isLoad=*/true,
+                                         NonLocalDepResults);
+    if (NonLocalDepResults.size() == 1) {
+      SrcDepInfo = NonLocalDepResults[0].getResult();
+      assert((!SrcDepInfo.getInst() ||
+              LookupDomTree().dominates(SrcDepInfo.getInst(), M)) &&
+             "when memdep returns exactly one result, it should dominate");
+    }
+  }
+
   if (SrcDepInfo.isClobber()) {
     if (MemCpyInst *MDep = dyn_cast<MemCpyInst>(SrcDepInfo.getInst()))
       return processMemCpyMemCpyDependence(M, MDep);
   } else if (SrcDepInfo.isDef()) {
     Instruction *I = SrcDepInfo.getInst();
     bool hasUndefContents = false;
 
     if (isa<AllocaInst>(I)) {

llvm/trunk/test/Transforms/MemCpyOpt/memcpy-invoke-memcpy.ll

+; RUN: opt < %s -memcpyopt -S | FileCheck %s
+; Test memcpy-memcpy dependencies across invoke edges.
+
+; Test that memcpyopt works across the non-unwind edge of an invoke.
+
+define hidden void @test_normal(i8* noalias %dst, i8* %src) personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+entry:
+  %temp = alloca i8, i32 64
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %temp, i8* nonnull %src, i64 64, i32 8, i1 false)
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %temp, i8* nonnull %src, i64 64, i32 8, i1 false)
+  invoke void @invoke_me()
+          to label %try.cont unwind label %lpad
+
+lpad:
+  landingpad { i8*, i32 }
+          catch i8* null
+  ret void
+
+try.cont:
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %temp, i64 64, i32 8, i1 false)
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %src, i64 64, i32 8, i1 false)
+  ret void
+}
+
+; Test that memcpyopt works across the unwind edge of an invoke.
+
+define hidden void @test_unwind(i8* noalias %dst, i8* %src) personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+entry:
+  %temp = alloca i8, i32 64
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %temp, i8* nonnull %src, i64 64, i32 8, i1 false)
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %temp, i8* nonnull %src, i64 64, i32 8, i1 false)
+  invoke void @invoke_me()
+          to label %try.cont unwind label %lpad
+
+lpad:
+  landingpad { i8*, i32 }
+          catch i8* null
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %temp, i64 64, i32 8, i1 false)
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %src, i64 64, i32 8, i1 false)
+  ret void
+
+try.cont:
+  ret void
+}
+
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i32, i1)
+declare i32 @__gxx_personality_v0(...)
+declare void @invoke_me() readnone

llvm/trunk/test/Transforms/MemCpyOpt/nonlocal-memcpy-memcpy.ll

+; RUN: opt < %s -memcpyopt -S | FileCheck %s
+; Make sure memcpy-memcpy dependence is optimized across
+; basic blocks (conditional branches and invokes).
+
+%struct.s = type { i32, i32 }
+
+@s_foo = private unnamed_addr constant %struct.s { i32 1, i32 2 }, align 4
+@s_baz = private unnamed_addr constant %struct.s { i32 1, i32 2 }, align 4
+@i = external constant i8*
+
+declare void @qux()
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i32, i1)
+declare void @__cxa_throw(i8*, i8*, i8*)
+declare i32 @__gxx_personality_v0(...)
+declare i8* @__cxa_begin_catch(i8*)
+
+; A simple partial redundancy. Test that the second memcpy is optimized
+; to copy directly from the original source rather than from the temporary.
+
+; CHECK-LABEL: @wobble
+define void @wobble(i8* noalias %dst, i8* %src, i1 %some_condition) {
+bb:
+  %temp = alloca i8, i32 64
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %temp, i8* nonnull %src, i64 64, i32 8, i1 false)
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %temp, i8* nonnull %src, i64 64, i32 8, i1 false)
+  br i1 %some_condition, label %more, label %out
+
+out:
+  call void @qux()
+  unreachable
+
+more:
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %temp, i64 64, i32 8, i1 false)
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %src, i64 64, i32 8, i1 false)
+  ret void
+}
+
+; A CFG triangle with a partial redundancy targeting an alloca. Test that the
+; memcpy inside the triangle is optimized to copy directly from the original
+; source rather than from the temporary.
+
+; CHECK-LABEL: @foo
+define i32 @foo(i1 %t3) {
+bb:
+  %s = alloca %struct.s, align 4
+  %t = alloca %struct.s, align 4
+  %s1 = bitcast %struct.s* %s to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %s1, i8* bitcast (%struct.s* @s_foo to i8*), i64 8, i32 4, i1 false)
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %s1, i8* bitcast (%struct.s* @s_foo to i8*), i64 8, i32 4, i1 false)
+  br i1 %t3, label %bb4, label %bb7
+
+bb4:                                              ; preds = %bb
+  %t5 = bitcast %struct.s* %t to i8*
+  %s6 = bitcast %struct.s* %s to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %t5, i8* %s6, i64 8, i32 4, i1 false)
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %t5, i8* bitcast (%struct.s* @s_foo to i8*), i64 8, i32 4, i1 false)
+  br label %bb7
+
+bb7:                                              ; preds = %bb4, %bb
+  %t8 = getelementptr %struct.s, %struct.s* %t, i32 0, i32 0
+  %t9 = load i32, i32* %t8, align 4
+  %t10 = getelementptr %struct.s, %struct.s* %t, i32 0, i32 1
+  %t11 = load i32, i32* %t10, align 4
+  %t12 = add i32 %t9, %t11
+  ret i32 %t12
+}
+
+; A CFG diamond with an invoke on one side, and a partially redundant memcpy
+; into an alloca on the other. Test that the memcpy inside the diamond is
+; optimized to copy ; directly from the original source rather than from the
+; temporary. This more complex test represents a relatively common usage
+; pattern.
+
+; CHECK-LABEL: @baz
+define i32 @baz(i1 %t5) personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+bb:
+  %s = alloca %struct.s, align 4
+  %t = alloca %struct.s, align 4
+  %s3 = bitcast %struct.s* %s to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %s3, i8* bitcast (%struct.s* @s_baz to i8*), i64 8, i32 4, i1 false)
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %s3, i8* bitcast (%struct.s* @s_baz to i8*), i64 8, i32 4, i1 false)
+  br i1 %t5, label %bb6, label %bb22
+
+bb6:                                              ; preds = %bb
+  invoke void @__cxa_throw(i8* null, i8* bitcast (i8** @i to i8*), i8* null)
+          to label %bb25 unwind label %bb9
+
+bb9:                                              ; preds = %bb6
+  %t10 = landingpad { i8*, i32 }
+          catch i8* null
+  br label %bb13
+
+bb13:                                             ; preds = %bb9
+  %t15 = call i8* @__cxa_begin_catch(i8* null)
+  br label %bb23
+
+bb22:                                             ; preds = %bb
+  %t23 = bitcast %struct.s* %t to i8*
+  %s24 = bitcast %struct.s* %s to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %t23, i8* %s24, i64 8, i32 4, i1 false)
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %t23, i8* bitcast (%struct.s* @s_baz to i8*), i64 8, i32 4, i1 false)
+  br label %bb23
+
+bb23:                                             ; preds = %bb22, %bb13
+  %t17 = getelementptr inbounds %struct.s, %struct.s* %t, i32 0, i32 0
+  %t18 = load i32, i32* %t17, align 4
+  %t19 = getelementptr inbounds %struct.s, %struct.s* %t, i32 0, i32 1
+  %t20 = load i32, i32* %t19, align 4
+  %t21 = add nsw i32 %t18, %t20
+  ret i32 %t21
+
+bb25:                                             ; preds = %bb6
+  unreachable
+}