Optimize double storing by memset; memcpy

[ab]

Summary

A common idiom in some code is to do the following:

memset(dest, 0, dest_size);
memcpy(dest, src, src_size);

This patch implements a rewrite to avoid storing to the same location twice. The above code is rewritten as:

memcpy(dest, src, dest_size);
memset((char *)dest + dest_size, setVal,

src_size > dest_size ? src_size - dest_size : 0);

[joel_k_jones]

Note that the the compile times aren't close, as my change is against a different version than the baseline.

[grosbach]

lib/Transforms/IPO/PassManagerBuilder.cpp

119 ↗

(On Diff #1192)

This seems unrelated to the optimization?

lib/Transforms/Scalar/MemCpyOptimizer.cpp

881

This should copy SrcSize bytes, not DestSize, right?

883

"NewDest" is a bit vague. Better would be referencing that this is the first byte of the trailing bit we'll be zeroing explicitly.

888

What happens if LenDiff is negative?

897

We should check for the (probably fairly common) case of both SrcLen and DstLen being constants, in which case we don't have to emit instructions to do the arithmetic.

Likewise, we should check if DestLen==SrcLen. That'd be a bit silly in the user's code, but this sort of pattern can often come from autogenerated code that's not smart enough to elide the bzero() in that case. We should just do it for them.

902

The DEBUG() line needs a lot more context about what it's logging. For anyone looking at debug output that's not actively working on this exact optimization, the instruction dump() here is going to be baffling.

1131

Seems not related to the optimization? If we want to add good DEBUG() output for these transforms, that's great, but it should be done as a separate patch first.

[joel_k_jones]

These are all valid points. Thanks for the review.

Joel

[ab]

Tweak Joel's patch here and there, mainly:

• correct a size problem
• try to keep as much alignment as possible

[ab]

Ping for review!

Reworded a few of the comments.

[ab]

Ping for an ancient patch? =)

[ab]

Ping! (also, rebase and harden a bit.)

-Ahmed

[alexr]

This only handles overlap at the start of the memset. Does it make sense to handle other overlaps?

[ab]

Ping!

[jmolloy]

Hi Ahmed,

This looks OK to me, I think, unless anyone else has objections?

Cheers,

James

[• dberlin]

Looks reasonable to me as well.

lib/Transforms/Scalar/MemCpyOptimizer.cpp

private:
     bool processStore(StoreInst *SI, BasicBlock::iterator &BBI);
     bool processMemSet(MemSetInst *SI, BasicBlock::iterator &BBI);
     bool processMemCpy(MemCpyInst *M);
     bool processMemMove(MemMoveInst *M);
     bool performCallSlotOptzn(Instruction *cpy, Value *cpyDst, Value *cpySrc,
                               uint64_t cpyLen, unsigned cpyAlign, CallInst *C);
     bool processMemCpyMemCpyDependence(MemCpyInst *M, MemCpyInst *MDep,
                                        uint64_t MSize);
+    bool processMemSetMemCpyDependence(MemCpyInst *M, MemSetInst *MDep);
     bool processByValArgument(CallSite CS, unsigned ArgNo);
     Instruction *tryMergingIntoMemset(Instruction *I, Value *StartPtr,
                                       Value *ByteVal);
 
     bool iterateOnFunction(Function &F);
   };
 
   char MemCpyOpt::ID = 0;
bool MemCpyOpt::processMemCpyMemCpyDependence(MemCpyInst *M, MemCpyInst *MDep,
 
   // Remove the instruction we're replacing.
   MD->removeInstruction(M);
   M->eraseFromParent();
   ++NumMemCpyInstr;
   return true;
 }
 
+/// We've found that the (upward scanning) memory dependence of \p MemCpy is
+/// \p MemSet.  Try to simplify \p MemSet to only set the trailing bytes that
+/// weren't copied over by \p MemCpy.
+///
+/// In other words, transform:
+/// \code
+///   memset(dest, set_val, dest_size);
+///   memcpy(dest, src, src_size);
+/// \endcode
+/// into:
+/// \code
+///   memcpy(dest, src, src_size);
+///   memset((char *)dest + src_size, set_val,
+///           dest_size < src_size ? 0 : dest_size - src_size);
+/// \endcode
+bool MemCpyOpt::processMemSetMemCpyDependence(MemCpyInst *MemCpy,
+                                              MemSetInst *MemSet) {
+  // We can only transforms memset/memcpy with the same destinations.
+  if (MemSet->getDest() != MemCpy->getDest())
+    return false;
+
+  Value *Dest = MemSet->getOperand(0);
+  Value *DestSize = MemSet->getOperand(2);
+  Value *SrcSize = MemCpy->getOperand(2);
+  Value *SetVal = MemSet->getOperand(1);
+
+  // By default, create an unaligned memset.
+  unsigned Align = 1;
+  // If the old memset Dest was aligned, and SrcSize is constant, use the
+  // minimum alignment of the sum.
+  const unsigned DestAlign = MemSet->getAlignment();
+  if (DestAlign > 1)
+    if (ConstantInt *SrcSizeC = dyn_cast<ConstantInt>(SrcSize))
+      Align = MinAlign(SrcSizeC->getZExtValue(), DestAlign);
+
+  IRBuilder<> Builder(MemCpy->getNextNode());
+
+  Value *Zero = ConstantInt::getNullValue(DestSize->getType());
+  Value *MemsetStart = Builder.CreateGEP(Dest, SrcSize);
+  Value *SetValTrunc = Builder.CreateTrunc(SetVal, Builder.getInt8Ty());
+
+  // LenDiff == (dest_size - src_size)
+  Value *LenDiff = Builder.CreateSub(DestSize, SrcSize);
+  // LenDiffNeg == (dest_size - src_size) < 0 == (dest_size < src_size)
+  Value *LenDiffNeg = Builder.CreateICmpSLT(LenDiff, Zero);
+  // MemsetLen == (dest_size < src_size) ? 0 : (dest_size - src_size)
+  Value *MemsetLen = Builder.CreateSelect(LenDiffNeg, Zero, LenDiff);
+
+  CallInst *NewMemSetCall = Builder.CreateMemSet(MemsetStart, SetValTrunc,
+                                                 MemsetLen, Align);
+
+  DEBUG(dbgs() << "MemCpyOpt: Optimizing redundant memset in memset;memcpy: "
+               << *NewMemSetCall << "\n");
+  (void)NewMemSetCall;
+
+  MD->removeInstruction(MemSet);
+  MemSet->eraseFromParent();
+  return true;
+}
 
 /// processMemCpy - perform simplification of memcpy's.  If we have memcpy A
 /// which copies X to Y, and memcpy B which copies Y to Z, then we can rewrite
 /// B to be a memcpy from X to Z (or potentially a memmove, depending on
 /// circumstances). This allows later passes to remove the first memcpy
 /// altogether.
 bool MemCpyOpt::processMemCpy(MemCpyInst *M) {
   // We can only optimize non-volatile memcpy's.
   if (M->isVolatile()) return false;
 
   // If the source and destination of the memcpy are the same, then zap it.
   if (M->getSource() == M->getDest()) {
     MD->removeInstruction(M);
     M->eraseFromParent();
     return false;
   }
 
   // If copying from a constant, try to turn the memcpy into a memset.
   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getSource()))
     if (GV->isConstant() && GV->hasDefinitiveInitializer())
       if (Value *ByteVal = isBytewiseValue(GV->getInitializer())) {
         IRBuilder<> Builder(M);
         Builder.CreateMemSet(M->getRawDest(), ByteVal, M->getLength(),
                              M->getAlignment(), false);
         MD->removeInstruction(M);
         M->eraseFromParent();
         ++NumCpyToSet;
         return true;
       }
 
+  AliasAnalysis::Location SrcLoc = AliasAnalysis::getLocationForSource(M);
+  MemDepResult SrcDepInfo = MD->getPointerDependencyFrom(SrcLoc, true,
+                                                         M, M->getParent());
+
+  // Try to turn a partially redundant memset + memcpy into
+  // memcpy + smaller memset
+  if (SrcDepInfo.isClobber())
+    if (MemSetInst *MDep = dyn_cast<MemSetInst>(SrcDepInfo.getInst()))
+      if (processMemSetMemCpyDependence(M, MDep))
+        return true;
+
   // The optimizations after this point require the memcpy size.
   ConstantInt *CopySize = dyn_cast<ConstantInt>(M->getLength());
   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);
   if (DepInfo.isClobber()) {
     if (CallInst *C = dyn_cast<CallInst>(DepInfo.getInst())) {
       if (performCallSlotOptzn(M, M->getDest(), M->getSource(),
                                CopySize->getZExtValue(), M->getAlignment(),
                                C)) {
         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)) {
bool MemCpyOpt::iterateOnFunction(Function &F) {
 
   return MadeChange;
 }
 
 // MemCpyOpt::runOnFunction - This is the main transformation entry point for a
 // function.
 //
 bool MemCpyOpt::runOnFunction(Function &F) {
   if (skipOptnoneFunction(F))
     return false;
 
   bool MadeChange = false;
   MD = &getAnalysis<MemoryDependenceAnalysis>();
   DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
   DL = DLP ? &DLP->getDataLayout() : nullptr;
   TLI = &getAnalysis<TargetLibraryInfo>();
 

test/Transforms/MemCpyOpt/memset-memcpy-redundant-memset.ll

+; RUN: opt -memcpyopt -S %s | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.10.0"
+
+; CHECK-LABEL: test
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dest, i8* %src, i64 %src_size, i32 1, i1 false)
+; CHECK: %1 = getelementptr i8* %dest, i64 %src_size
+; CHECK: %2 = sub i64 %dest_size, %src_size
+; CHECK: %3 = icmp slt i64 %2, 0
+; CHECK: %4 = select i1 %3, i64 0, i64 %2
+; CHECK: call void @llvm.memset.p0i8.i64(i8* %1, i8 0, i64 %4, i32 1, i1 false)
+; CHECK: ret void
+define void @test(i8* %src, i64 %src_size, i8* %dest, i64 %dest_size) {
+  call void @llvm.memset.p0i8.i64(i8* %dest, i8 0, i64 %dest_size, i32 1, i1 false)
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dest, i8* %src, i64 %src_size, i32 1, i1 false)
+  ret void
+}
+
+; CHECK-LABEL: test_align_same
+; CHECK: call void @llvm.memset.p0i8.i64(i8* %1, i8 0, i64 %4, i32 8, i1 false)
+define void @test_align_same(i8* %src, i8* %dest, i64 %dest_size) {
+  call void @llvm.memset.p0i8.i64(i8* %dest, i8 0, i64 %dest_size, i32 8, i1 false)
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dest, i8* %src, i64 80, i32 1, i1 false)
+  ret void
+}
+
+; CHECK-LABEL: test_align_min
+; CHECK: call void @llvm.memset.p0i8.i64(i8* %1, i8 0, i64 %4, i32 4, i1 false)
+define void @test_align_min(i8* %src, i8* %dest, i64 %dest_size) {
+  call void @llvm.memset.p0i8.i64(i8* %dest, i8 0, i64 %dest_size, i32 8, i1 false)
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dest, i8* %src, i64 36, i32 1, i1 false)
+  ret void
+}
+
+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)