[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.

[dotdash]

Hi,

could someone take a look at this or maybe suggest a different reviewer if I chose poorly, please?

Thanks a lot!

[rnk]

I think you could split this up and write more targetted tests. The sret change needs a test and is probably separable.

[hfinkel]

lib/IR/Value.cpp

661

arraySize -> ArraySize

663

Because of this especially, please make DerefBytes a uint64_t (instead of just unsigned).

lib/Transforms/Scalar/MemCpyOptimizer.cpp

843

destSize -> DestSize (and similar for other variables below as per our coding conventions)

[dotdash]

In D40723#955555, @rnk wrote:

I think you could split this up and write more targetted tests. The sret change needs a test and is probably separable.

I didn't realize that phabricator only displays the list of commits, but provides no access to the individual diffs.

So I should submit the fixes incrementally in multiple, sequential review requests, right?

[hfinkel]

In D40723#956485, @dotdash wrote:

In D40723#955555, @rnk wrote:

I think you could split this up and write more targetted tests. The sret change needs a test and is probably separable.

I didn't realize that phabricator only displays the list of commits, but provides no access to the individual diffs.

So I should submit the fixes incrementally in multiple, sequential review requests, right?

Yes. Please post multiple phabricator review requests.

[dotdash]

Will replace with a series of individual review requests.

lib/IR/Value.cpp

 unsigned Value::getPointerDereferenceableBytes(const DataLayout &DL,
                                                bool &CanBeNull) const {
   assert(getType()->isPointerTy() && "must be pointer");
 
   unsigned DerefBytes = 0;
   CanBeNull = false;
   if (const Argument *A = dyn_cast<Argument>(this)) {
     DerefBytes = A->getDereferenceableBytes();
-    if (DerefBytes == 0 && A->hasByValAttr() && A->getType()->isSized()) {
-      DerefBytes = DL.getTypeStoreSize(A->getType());
+    if (DerefBytes == 0 && (A->hasByValAttr() || A->hasStructRetAttr())) {
+      Type *PT = cast<PointerType>(A->getType())->getElementType();
+      if (PT->isSized()) {
+        DerefBytes = DL.getTypeStoreSize(PT);
         CanBeNull = false;
       }
+    }
     if (DerefBytes == 0) {
       DerefBytes = A->getDereferenceableOrNullBytes();
       CanBeNull = true;
     }
   } else if (auto CS = ImmutableCallSite(this)) {
     DerefBytes = CS.getDereferenceableBytes(AttributeList::ReturnIndex);
     if (DerefBytes == 0) {
       DerefBytes = CS.getDereferenceableOrNullBytes(AttributeList::ReturnIndex);
       CanBeNull = true;
     }
   } else if (const LoadInst *LI = dyn_cast<LoadInst>(this)) {
     if (MDNode *MD = LI->getMetadata(LLVMContext::MD_dereferenceable)) {
       ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
       DerefBytes = CI->getLimitedValue();
     }
     if (DerefBytes == 0) {
       if (MDNode *MD =
               LI->getMetadata(LLVMContext::MD_dereferenceable_or_null)) {
         ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
         DerefBytes = CI->getLimitedValue();
       }
       CanBeNull = true;
     }
   } else if (auto *AI = dyn_cast<AllocaInst>(this)) {
-    if (AI->getAllocatedType()->isSized()) {
-      DerefBytes = DL.getTypeStoreSize(AI->getAllocatedType());
+    const ConstantInt *arraySize = dyn_cast<ConstantInt>(AI->getArraySize());
+    if (arraySize && AI->getAllocatedType()->isSized()) {
+      DerefBytes = DL.getTypeStoreSize(AI->getAllocatedType()) *
+        arraySize->getZExtValue();
       CanBeNull = false;
     }
   } else if (auto *GV = dyn_cast<GlobalVariable>(this)) {
     if (GV->getValueType()->isSized() && !GV->hasExternalWeakLinkage()) {
       // TODO: Don't outright reject hasExternalWeakLinkage but set the
       // CanBeNull flag.
       DerefBytes = DL.getTypeStoreSize(GV->getValueType());
       CanBeNull = false;

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.
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 }