Optionally extend alloca lifetimes to allow for callslot optimization to happen

[dotdash]

Summary

Currently, memcpy callslot optimization doesn't happen if the memcpy's
destination starts its lifetime between the call and the memcpy. We can
make the optimization happen by extending the allocas lifetime to start
before the call, but we must only do that if the callslot optimization
succeeds, because otherwise we might lose some opportunities for stack
slot sharing

[reames]

I'm reasonable sure this code is correct, but I'm not sure it's as well structured as it could be. I reserve the right to be wrong here; you may just need to explain a few things. :)

lib/Transforms/Scalar/MemCpyOptimizer.cpp

891

I'm a bit concerned about running these queries unconditionally. MDA is rather expensive.

894

I'm not clear I understand the problem here. Is the issue that MD->getDependency is returning the lifetime_start as the dependency but MD->getPointerDependency(Src) is not?

Also, would it be *correct* to always use the source pointer dependency here? Or do you need to consider both source and dest dependencies when considering the callSlotOpt? Depending on the implementation of the callSlotOpt, I could see that going either way.

[reames]

p.s. You may be interested in the bug I just filed on a related issue. http://llvm.org/bugs/show_bug.cgi?id=22758

[dotdash]

lib/Transforms/Scalar/MemCpyOptimizer.cpp

894

Yes, MD->getDependency returns the lifetime_start as the dependency.

It would be incorrect to always use the source pointer dependency here, because we would then apply the call slot optimization to cases like this:

memset(%src, 0, 1000)
memset(%dst, 1, 1000)
foo(dst)
memcpy(%dst, %src, 1000)
foo(dst)

transforming it to

memset(%dst, 0, 1000)
memset(%dst, 1, 1000)
foo(dst)
foo(dst)

Unfortunately the same is true for this patch when %dst has multiple lifetime ranges like this:

memset(%src, 0, 1000)
lifetime_start(1000, %dst)
memset(%dst, 1, 1000)
foo(dst)
lifetime_end(1000, %dst)
lifetime_start(1000, %dst)
memcpy(%dst, %src, 1000)
foo(dst)
lifetime_end(1000, %dst)

I'll have to rethink this.

lib/Transforms/Scalar/MemCpyOptimizer.cpp

bool MemCpyOpt::processMemCpy(MemCpyInst *M) {
   if (!CopySize) return false;
 
   // The are three possible optimizations we can do for memcpy:
   //   a) memcpy-memcpy xform which exposes redundance for DSE.
   //   b) call-memcpy xform for return slot optimization.
   //   c) memcpy from freshly alloca'd space or space that has just started its
   //      lifetime copies undefined data, and we can therefore eliminate the
   //      memcpy in favor of the data that was already at the destination.
-  MemDepResult DepInfo = MD->getDependency(M);
+  AliasAnalysis::Location SrcLoc = AliasAnalysis::getLocationForSource(M);
+  MemDepResult SrcDepInfo = MD->getPointerDependencyFrom(SrcLoc, true,
+                                                         M, M->getParent());
+  AliasAnalysis::Location DstLoc = AliasAnalysis::getLocationForDest(M);
+  MemDepResult DstDepInfo = MD->getPointerDependencyFrom(DstLoc, true,
+                                                         M, M->getParent());
+
+  // If the destination just started its lifetime, pretend that the lifetime
+  // start isn't present, try the callslot optimization and if it succeeds,
+  // extend the lifetime accordingly
+  IntrinsicInst *LT = dyn_cast_or_null<IntrinsicInst>(DstDepInfo.getInst());
+  if (LT && LT->getIntrinsicID() != Intrinsic::lifetime_start)
+    LT = nullptr;
+
+  MemDepResult DepInfo = LT ? SrcDepInfo : MD->getDependency(M);
   if (DepInfo.isClobber()) {
     if (CallInst *C = dyn_cast<CallInst>(DepInfo.getInst())) {
       if (performCallSlotOptzn(M, M->getDest(), M->getSource(),
                                CopySize->getZExtValue(), M->getAlignment(),
                                C)) {
+        if (LT) {
+          IRBuilder<> Builder(SrcDepInfo.getInst());
+          Builder.CreateLifetimeStart(M->getDest(),
+                                      cast<ConstantInt>(LT->getArgOperand(0)));
+          MD->removeInstruction(LT);
+          LT->eraseFromParent();
+        }
+
         MD->removeInstruction(M);
         M->eraseFromParent();
         return true;
       }
     }
   }
-
-  AliasAnalysis::Location SrcLoc = AliasAnalysis::getLocationForSource(M);
-  MemDepResult SrcDepInfo = MD->getPointerDependencyFrom(SrcLoc, true,
-                                                         M, M->getParent());
   if (SrcDepInfo.isClobber()) {
     if (MemCpyInst *MDep = dyn_cast<MemCpyInst>(SrcDepInfo.getInst()))
       return processMemCpyMemCpyDependence(M, MDep, CopySize->getZExtValue());
   } else if (SrcDepInfo.isDef()) {
     Instruction *I = SrcDepInfo.getInst();
     bool hasUndefContents = false;
 
     if (isa<AllocaInst>(I)) {

test/Transforms/MemCpyOpt/extend-lifetime.ll

+; RUN: opt < %s -basicaa -memcpyopt -S | FileCheck %s
+target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+
+declare void @foo([100000 x i32]*)
+
+declare void @llvm.lifetime.start(i64, i8* nocapture)
+declare void @llvm.lifetime.end(i64, i8* nocapture)
+declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1)
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i32, i1)
+
+; Function Attrs: nounwind uwtable
+define void @testfunc() {
+  %src = alloca [100000 x i32], align 4
+  %dst = alloca [100000 x i32], align 4
+  %1 = bitcast [100000 x i32]* %src to i8*
+  call void @llvm.memset.p0i8.i64(i8* %1, i8 0, i64 400000, i32 4, i1 false)
+  %2 = bitcast [100000 x i32]* %dst to i8*
+  call void @llvm.lifetime.start(i64 400000, i8* %2)
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %2, i8* %1, i64 400000, i32 4, i1 false)
+  call void @foo([100000 x i32]* %dst)
+  call void @llvm.lifetime.end(i64 400000, i8* %2)
+  ret void
+; CHECK-LABEL: @testfunc
+; CHECK-NOT: memcpy
+; CHECK: lifetime.start
+; CHECK: memset
+}