[MemCpyOpt] Perform call slot optimizations through GEPs

[dotdash]

Summary

Call slot optimization needs to know that writing to the destination of the
memcpy won't trap, so it has to know the number of dereferenceable bytes of the
destination. Currently it can only handle this for allocas and function
arguments that are directly written to. We can improve upon this by handling
simple GEPs with constant offsets.

This allows call slot optimizations to happen in code like this:

struct Foo {
  int o[200];
};

struct Bar {
  char p;
  Foo f;
};

  __attribute__((noinline))
Foo moo()
{
  return {0};
}

Bar goo()
{
  Bar f;
  f.f = moo();
  return f;
}

Which is a slightly modified version of the code in PR35134 that works around
the missing alias information in the original C++ code.

It also makes the optimization happen in the Rust code that originally lead to
the above PR.

[efriedma]

lib/Transforms/Scalar/MemCpyOptimizer.cpp

836

You probably want to clarify why an alloca is special here.

Does it matter if cpyDest could be accessed from another thread?

Do you need to check whether any calls between "C" and "cpy" could throw?

848

Maybe this code belongs in getPointerDereferenceableBytes, rather than here?

915

This check is kind of fragile, in that it assumes the other operands to the GEP are all ConstantInts.

[dotdash]

lib/Transforms/Scalar/MemCpyOptimizer.cpp

836

You probably want to clarify why an alloca is special here.

I basically just kept the logic as it was here, but looks like that comment is a bit outdated, and I already made call slot opt a bit too aggressive back when I introduced handling of arguments other than sret ones.

Do you need to check whether any calls between "C" and "cpy" could throw?

I guess so, already to properly handle arguments that are merely dereferenceable and not sret, to avoid stores from showing up that should not be visible after a throw. Would a check for postdominance be sufficient here?

Does it matter if cpyDest could be accessed from another thread?

I'm not completely sure, but I'd say that for multithreaded code to behave correctly here, one would need a memory barrier or something similar here anyway, which should break the dependency between the call and the memcpy, so we should not end up here in the first place. Am I missing something here?

848

I had some problems where moving that code broke the original user of getPointerDereferenceableBytes. I can try to see if I can fix that.

915

That's a prerequisite to get here, but I see what you mean. I guess I add an explicit hasAllConstantIndices() check here?

[efriedma]

lib/Transforms/Scalar/MemCpyOptimizer.cpp

836

Would a check for postdominance be sufficient here?

LLVM's PostDominatorTree isn't usable for this, if that's what you're asking.

for multithreaded code to behave correctly here, one would need a memory barrier or something similar here anyway, which should break the dependency between the call and the memcpy

Oh, okay, that's right. (There's a similar transform in LICM I was comparing this to, but LICM is more complicated because we promote conditional stores in some cases.)

874

Sort of orthogonal to the patch, but the check here ("Check that src is not accessed except via the call and the memcpy") doesn't provide the intended guarantee. If the call is in a loop, src doesn't hold undefined values after the first iteration of the loop.

915

Sure. (You could make it an assert if you're confident this code isn't reachable otherwise.)

lib/Transforms/Scalar/MemCpyOptimizer.cpp

bool MemCpyOptPass::performCallSlotOptzn(Instruction *cpy, Value *cpyDest,
 
   const DataLayout &DL = cpy->getModule()->getDataLayout();
   uint64_t srcSize = DL.getTypeAllocSize(srcAlloca->getAllocatedType()) *
                      srcArraySize->getZExtValue();
 
   if (cpyLen < srcSize)
     return false;
 
-  // Check that accessing the first srcSize bytes of dest will not cause a
-  // trap.  Otherwise the transform is invalid since it might cause a trap
-  // to occur earlier than it otherwise would.
-  if (AllocaInst *A = dyn_cast<AllocaInst>(cpyDest)) {
-    // The destination is an alloca.  Check it is larger than srcSize.
-    ConstantInt *destArraySize = dyn_cast<ConstantInt>(A->getArraySize());
-    if (!destArraySize)
-      return false;
-
-    uint64_t destSize = DL.getTypeAllocSize(A->getAllocatedType()) *
-                        destArraySize->getZExtValue();
-
-    if (destSize < srcSize)
-      return false;
-  } else if (Argument *A = dyn_cast<Argument>(cpyDest)) {
-    // The store to dest may never happen if the call can throw.
-    if (C->mayThrow())
-      return false;
+  if (C->mayThrow() && !isa<AllocaInst>(cpyDest))
 
-    if (A->getDereferenceableBytes() < srcSize) {
-      // If the destination is an sret parameter then only accesses that are
-      // outside of the returned struct type can trap.
-      if (!A->hasStructRetAttr())
-        return false;
+  // Check that accessing the first srcSize bytes of dest will not cause a
+  // trap.  Otherwise the transform is invalid since it might cause a trap
+  // to occur earlier than it otherwise would.
+  bool CanBeNull;
+  uint64_t DestSize = 0;
 
-      Type *StructTy = cast<PointerType>(A->getType())->getElementType();
-      if (!StructTy->isSized()) {
-        // The call may never return and hence the copy-instruction may never
-        // be executed, and therefore it's not safe to say "the destination
-        // has at least <cpyLen> bytes, as implied by the copy-instruction",
-        return false;
-      }
+  if (const auto GEP = dyn_cast<GEPOperator>(cpyDest)) {
+    APInt Offset(DL.getPointerTypeSizeInBits(GEP->getType()), 0);
+    APInt APOffset(DL.getPointerSizeInBits(GEP->getPointerAddressSpace()), 0);
+    if (GEP->accumulateConstantOffset(DL, APOffset) && !Offset.isNegative()) {
+      auto Offset = APOffset.getSExtValue();
+      auto InnerSize = GEP->getPointerOperand()->getPointerDereferenceableBytes(
+          DL, CanBeNull);
+      if (Offset <= InnerSize)
+        DestSize = InnerSize - Offset;
+  } else
+    DestSize = cpyDest->getPointerDereferenceableBytes(DL, CanBeNull);
 
-      uint64_t destSize = DL.getTypeAllocSize(StructTy);
-      if (destSize < srcSize)
-        return false;
-    }
-  } else {
+  if (CanBeNull || DestSize < srcSize)
     return false;
-  }
 
   // Check that dest points to memory that is at least as aligned as src.
   unsigned srcAlign = srcAlloca->getAlignment();
   if (!srcAlign)
     srcAlign = DL.getABITypeAlignment(srcAlloca->getAllocatedType());
   bool isDestSufficientlyAligned = srcAlign <= cpyAlign;
   // If dest is not aligned enough and we can't increase its alignment then
   // bail out.
   if (!isDestSufficientlyAligned && !isa<AllocaInst>(cpyDest))
     return false;
 
   // Check that src is not accessed except via the call and the memcpy.  This
   // guarantees that it holds only undefined values when passed in (so the final
   // memcpy can be dropped), that it is not read or written between the call and
   // the memcpy, and that writing beyond the end of it is undefined.
   SmallVector<User*, 8> srcUseList(srcAlloca->user_begin(),
                                    srcAlloca->user_end());
   while (!srcUseList.empty()) {
     User *U = srcUseList.pop_back_val();
 
     if (isa<BitCastInst>(U) || isa<AddrSpaceCastInst>(U)) {
       for (User *UU : U->users())
         srcUseList.push_back(UU);
bool MemCpyOptPass::performCallSlotOptzn(Instruction *cpy, Value *cpyDest,
   // transformation can cause aliasing issues in that case.
   for (unsigned i = 0, e = CS.arg_size(); i != e; ++i)
     if (CS.getArgument(i) == cpySrc && !CS.doesNotCapture(i))
       return false;
 
   // Since we're changing the parameter to the callsite, we need to make sure
   // that what would be the new parameter dominates the callsite.
   DominatorTree &DT = LookupDomTree();
-  if (Instruction *cpyDestInst = dyn_cast<Instruction>(cpyDest))
-    if (!DT.dominates(cpyDestInst, C))
+  if (Instruction *cpyDestInst = dyn_cast<Instruction>(cpyDest)) {
+    if (!DT.dominates(cpyDestInst, C)) {
+      // Try to move a GEP up to allow the optimization to happen
+      if (auto G = dyn_cast<GetElementPtrInst>(cpyDest)) {
+        auto P = G->getPointerOperand();
+        auto PI = dyn_cast<Instruction>(P);
+        if (isa<Argument>(P) || (PI && DT.dominates(PI, C)))
+          G->moveBefore(C);
+        else
           return false;
+      }
+      else
+        return false;
+    }
+  }
 
   // In addition to knowing that the call does not access src in some
   // unexpected manner, for example via a global, which we deduce from
   // the use analysis, we also need to know that it does not sneakily
   // access dest.  We rely on AA to figure this out for us.
   AliasAnalysis &AA = LookupAliasAnalysis();
   ModRefInfo MR = AA.getModRefInfo(C, cpyDest, srcSize);
   // If necessary, perform additional analysis.

test/Transforms/MemCpyOpt/callslot_gep.ll

+; RUN: opt -S -memcpyopt < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-linux-gnu"
+
+define void @foo(i8* noalias dereferenceable(201) %d) #0 {
+; CHECK-LABEL: @foo(
+; CHECK-NOT: call void @llvm.memcpy.p0i8.p0i8.i64
+start:
+  %s = alloca i8, i64 200
+  call void @writer(i8* nocapture %s)
+  %0 = getelementptr inbounds i8, i8* %d, i32 1
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %s, i64 200, i32 1, i1 false)
+  ret void
+}
+
+declare void @writer(i8* nocapture) #0
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i32, i1) #1
+
+attributes #0 = { nounwind }
+attributes #1 = { argmemonly nounwind }