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

[pcwalton]

Summary

Make the memory dependence queries in the memcpy optimizer nonlocal.

This eliminates 28% of the llvm.memcpy calls in librustc.

Fixes PR28958.

[majnemer]

Thanks for the patch!

Could you please reduce the testcase? It contains quite a few unnecessary instructions.

Something along the lines of the following would be more appropriate:

define void @wobble(i8* noalias nocapture sret %arg, i8* nocapture readonly dereferenceable(64) %arg1, i1 zeroext %arg3) local_unnamed_addr #0 {
bb:
  %tmp51 = alloca [64 x i8], align 8
  %tmp51.sub = getelementptr inbounds [64 x i8], [64 x i8]* %tmp51, i64 0, i64 0
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %tmp51.sub, i8* nonnull %arg1, i64 64, i32 8, i1 false)
  br i1 %arg3, label %bb11, label %bb12

bb11:                                             ; preds = %bb
  tail call void @ham() #3
  unreachable

bb12:                                             ; preds = %bb
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %arg, i8* %tmp51.sub, i64 64, i32 8, i1 false)
  ret void
}

; Function Attrs: argmemonly nounwind
declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i32, i1) #1

; Function Attrs: noreturn nounwind
declare void @ham() local_unnamed_addr #2

[• dberlin]

include/llvm/Analysis/MemoryDependenceAnalysis.h

384

I figure you are trying to make the two API's look the same, but the honest truth is: the other API sucks :)

There are a bunch of instructions that affect memory that don't have MemoryLocation's (calls are a good example).

I know you just are pushing the first two lines it does up, and that this means the function will crash on things like fences, etc, but we shouldn't make it worse :)

In any case, if you really want to do this, this should be shoved into a different patch, as it's completely unrelated to your change

[pcwalton]

include/llvm/Analysis/MemoryDependenceAnalysis.h

384

OK, I think I'm going to just go the MemorySSA route instead. I wrote some boilerplate code to get MemCpyOpt using MemorySSA, so at this point it'd be awesome if you could summarize how you'd like me to change MemorySSA to conform to MemCpyOpt's requirements :)

[sunfish]

I posted an updated version of this patch for review here: https://reviews.llvm.org/D38374

include/llvm/Analysis/MemoryDependenceAnalysis.h

public:
   /// define or clobber the value.
   ///
   /// Warning: For a volatile query instruction, the dependencies will be
   /// accurate, and thus usable for reordering, but it is never legal to
   /// remove the query instruction.
   ///
   /// This method assumes the pointer has a "NonLocal" dependency within
   /// QueryInst's parent basic block.
-  void getNonLocalPointerDependency(Instruction *QueryInst,
+  void getNonLocalPointerDependency(MemoryLocation &Loc, bool isLoad, Instruction *QueryInst,
                                     SmallVectorImpl<NonLocalDepResult> &Result);
 
   /// Removes an instruction from the dependence analysis, updating the
   /// dependence of instructions that previously depended on it.
   void removeInstruction(Instruction *InstToRemove);
 
   /// Invalidates cached information about the specified pointer, because it
   /// may be too conservative in memdep.

lib/Analysis/MemDepPrinter.cpp

if (!Res.isNonLocal()) {
       for (const NonLocalDepEntry &I : NLDI) {
         const MemDepResult &Res = I.getResult();
         InstDeps.insert(std::make_pair(getInstTypePair(Res), I.getBB()));
       }
     } else {
       SmallVector<NonLocalDepResult, 4> NLDI;
       assert( (isa<LoadInst>(Inst) || isa<StoreInst>(Inst) ||
                isa<VAArgInst>(Inst)) && "Unknown memory instruction!"); 
-      MDA.getNonLocalPointerDependency(Inst, NLDI);
+
+      MemoryLocation Loc = MemoryLocation::get(Inst);
+      MDA.getNonLocalPointerDependency(Loc, isa<LoadInst>(Inst), Inst, NLDI);
 
       DepSet &InstDeps = Deps[Inst];
       for (const NonLocalDepResult &I : NLDI) {
         const MemDepResult &Res = I.getResult();
         InstDeps.insert(std::make_pair(getInstTypePair(Res), I.getBB()));
       }
     }
   }

lib/Analysis/MemoryDependenceAnalysis.cpp

if (!Dep.isNonLocal()) {
         DirtyBlocks.push_back(Pred);
     }
   }
 
   return Cache;
 }
 
 void MemoryDependenceResults::getNonLocalPointerDependency(
-    Instruction *QueryInst, SmallVectorImpl<NonLocalDepResult> &Result) {
-  const MemoryLocation Loc = MemoryLocation::get(QueryInst);
-  bool isLoad = isa<LoadInst>(QueryInst);
+    MemoryLocation &Loc, bool isLoad, Instruction *QueryInst,
+    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();
 
   // This routine does not expect to deal with volatile instructions.

lib/Transforms/Scalar/GVN.cpp

 /// non-local by performing PHI construction.
 bool GVN::processNonLocalLoad(LoadInst *LI) {
   // non-local speculations are not allowed under asan.
   if (LI->getParent()->getParent()->hasFnAttribute(Attribute::SanitizeAddress))
     return false;
 
   // Step 1: Find the non-local dependencies of the load.
   LoadDepVect Deps;
-  MD->getNonLocalPointerDependency(LI, Deps);
+  MemoryLocation Loc = MemoryLocation::get(LI);
+  MD->getNonLocalPointerDependency(Loc, true, LI, Deps);
 
   // If we had to process more than one hundred blocks to find the
   // dependencies, this load isn't worth worrying about.  Optimizing
   // it will be too expensive.
   unsigned NumDeps = Deps.size();
   if (NumDeps > 100)
     return false;
 

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());
+
+  SmallVector<NonLocalDepResult, 2> NonLocalDepResults;
+  if (SourceDep.isNonLocal()) {
+    MD->getNonLocalPointerDependency(SourceLoc, false, M, NonLocalDepResults);
+    if (NonLocalDepResults.size() == 1)
+      SourceDep = NonLocalDepResults[0].getResult();
+  }
+
   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());
 
+  SmallVector<NonLocalDepResult, 2> NonLocalDepResults;
+  if (SrcDepInfo.isNonLocal()) {
+    MD->getNonLocalPointerDependency(SrcLoc, true, M, NonLocalDepResults);
+    if (NonLocalDepResults.size() == 1)
+      SrcDepInfo = NonLocalDepResults[0].getResult();
+  }
+
   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)) {

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).
+
+; ModuleID = 'nonlocal-memcpy-memcpy.cpp'
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.11.0"
+
+%struct.s = type { i32, i32 }
+
+@foo_s = private unnamed_addr constant %struct.s { i32 1, i32 2 }, align 4
+@baz_s = private unnamed_addr constant %struct.s { i32 1, i32 2 }, align 4
+@i = external constant i8*
+
+; Function Attrs: ssp uwtable
+define i32 @foo() #0 {
+  %x = alloca i32, align 4
+  %s = alloca %struct.s, align 4
+  %t = alloca %struct.s, align 4
+  %1 = call i32 @bar()
+  store i32 %1, i32* %x, align 4
+  %2 = bitcast %struct.s* %s to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %2, i8* bitcast (%struct.s* @foo_s to i8*), i64 8, i32 4, i1 false)
+  %3 = load i32, i32* %x, align 4
+  %4 = icmp ne i32 %3, 0
+  br i1 %4, label %5, label %8
+
+; <label>:5                                       ; preds = %0
+  %6 = bitcast %struct.s* %t to i8*
+  %7 = bitcast %struct.s* %s to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %6, i8* %7, i64 8, i32 4, i1 false)
+
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %6, i8* bitcast (%struct.s* @foo_s to i8*), i64 8, i32 4, i1 false)
+
+  br label %8
+
+; <label>:8                                       ; preds = %5, %0
+  %9 = getelementptr inbounds %struct.s, %struct.s* %t, i32 0, i32 0
+  %10 = load i32, i32* %9, align 4
+  %11 = getelementptr inbounds %struct.s, %struct.s* %t, i32 0, i32 1
+  %12 = load i32, i32* %11, align 4
+  %13 = add nsw i32 %10, %12
+  ret i32 %13
+}
+
+declare i32 @bar() #1
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i32, i1) #2
+
+; Function Attrs: ssp uwtable
+define i32 @baz() #0 personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+  %x = alloca i32, align 4
+  %s = alloca %struct.s, align 4
+  %t = alloca %struct.s, align 4
+  %1 = alloca i8*
+  %2 = alloca i32
+  %3 = call i32 @bar()
+  store i32 %3, i32* %x, align 4
+  %4 = bitcast %struct.s* %s to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %4, i8* bitcast (%struct.s* @baz_s to i8*), i64 8, i32 4, i1 false)
+  %5 = load i32, i32* %x, align 4
+  %6 = icmp ne i32 %5, 0
+  br i1 %6, label %7, label %23
+
+; <label>:7                                       ; preds = %0
+  %8 = call i8* @__cxa_allocate_exception(i64 4) #3
+  %9 = bitcast i8* %8 to i32*
+  store i32 0, i32* %9, align 8
+  invoke void @__cxa_throw(i8* %8, i8* bitcast (i8** @i to i8*), i8* null) #4
+          to label %26 unwind label %10
+
+; <label>:10                                      ; preds = %7
+  %11 = landingpad { i8*, i32 }
+          catch i8* null
+  %12 = extractvalue { i8*, i32 } %11, 0
+  store i8* %12, i8** %1, align 8
+  %13 = extractvalue { i8*, i32 } %11, 1
+  store i32 %13, i32* %2, align 4
+  br label %14
+
+; <label>:14                                      ; preds = %10
+  %15 = load i8*, i8** %1, align 8
+  %16 = call i8* @__cxa_begin_catch(i8* %15) #3
+  call void @__cxa_end_catch()
+  br label %17
+
+; <label>:17                                      ; preds = %14, %23
+  %18 = getelementptr inbounds %struct.s, %struct.s* %t, i32 0, i32 0
+  %19 = load i32, i32* %18, align 4
+  %20 = getelementptr inbounds %struct.s, %struct.s* %t, i32 0, i32 1
+  %21 = load i32, i32* %20, align 4
+  %22 = add nsw i32 %19, %21
+  ret i32 %22
+
+; <label>:23                                      ; preds = %0
+  %24 = bitcast %struct.s* %t to i8*
+  %25 = bitcast %struct.s* %s to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %24, i8* %25, i64 8, i32 4, i1 false)
+
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %24, i8* bitcast (%struct.s* @baz_s to i8*), i64 8, i32 4, i1 false)
+
+  br label %17
+
+; <label>:26                                      ; preds = %7
+  unreachable
+}
+
+declare i8* @__cxa_allocate_exception(i64)
+
+declare void @__cxa_throw(i8*, i8*, i8*)
+
+declare i32 @__gxx_personality_v0(...)
+
+declare i8* @__cxa_begin_catch(i8*)
+
+declare void @__cxa_end_catch()
+