MemCpyOpt: combine local load/store sequences into memcpy.

[t.p.northover]

Summary

We've got a loop idiom recognizer that can spot a memcpy, but as far as I can tell nothing for the case where the user has "helpfully" unrolled their loops for us, leaving a linear load/store sequence.

This pass seemed to have most of the machinery in place already to form memsets, so I adapted it to also create memcpy calls when it could. I've run the test-suite with no issues, but I'm still not really in familiar code so I'd appreciate someone else looking over the code.

Cheers.

Tim.

[majnemer]

lib/Transforms/Scalar/MemCpyOptimizer.cpp

567

Atomic?

[t.p.northover]

lib/Transforms/Scalar/MemCpyOptimizer.cpp

567

I don't think MemTransferInsts (i.e. @llvm.mem* calls) can be atomic, can they? For normal loads & stores both volatile and atomic are covered by the isSimple check.

[junbuml]

lib/Transforms/Scalar/MemCpyOptimizer.cpp

151–152

comment should be updated.

199

Looks like it should be :

unsigned MaxIntSize = DL.getLargestLegalIntTypeSize() / 8;

I will submit a separate patch just for this.

603

memset-> memcpy

607–608

Comment should be updated.

[t.p.northover]

Thanks Jun, thought I'd gone through the comments but obviously not all. Updating diff.

[junbuml]

lib/Transforms/Scalar/MemCpyOptimizer.cpp

199

I fix this in D20176.

[t.p.northover]

Just going through my list of open issues and spotted this. Ping?

Tim.

[t.p.northover]

Updating patch to ToT.

[courbet]

Hi Tim,

I've started implementing something similar to this revision and stumbled upon this while searching for related things. Analysis suggesta that our codebase would really benefit from this. Are you still willing to submit this (I don't want to duplicate efforts) ?

Note that the patch still applies quite cleanly (only two s/typedef/using/ to reconcile).

include/llvm/Transforms/Scalar/MemCpyOptimizer.h

bool runImpl(Function &F, MemoryDependenceResults *MD_,
                std::function<AliasAnalysis &()> LookupAliasAnalysis_,
                std::function<AssumptionCache &()> LookupAssumptionCache_,
                std::function<DominatorTree &()> LookupDomTree_);
 
 private:
   // Helper functions
   bool processStore(StoreInst *SI, BasicBlock::iterator &BBI);
   bool processMemSet(MemSetInst *SI, BasicBlock::iterator &BBI);
-  bool processMemCpy(MemCpyInst *M);
+  bool processMemCpy(MemCpyInst *M, BasicBlock::iterator &BBI);
   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);
   bool processMemSetMemCpyDependence(MemCpyInst *M, MemSetInst *MDep);
   bool performMemCpyToMemSetOptzn(MemCpyInst *M, MemSetInst *MDep);
   bool processByValArgument(CallSite CS, unsigned ArgNo);
   Instruction *tryMergingIntoMemset(Instruction *I, Value *StartPtr,
                                     Value *ByteVal);
+  Instruction *tryMergingIntoMemcpy(Instruction *StartInst, Value *StartDstPtr,
+                                    Value *StartSrcPtr);
 
   bool iterateOnFunction(Function &F);
 };
 }
 
 #endif // LLVM_TRANSFORMS_SCALAR_MEMCPYOPTIMIZER_H

lib/Transforms/Scalar/MemCpyOptimizer.cpp

 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include <algorithm>
 using namespace llvm;
 
 #define DEBUG_TYPE "memcpyopt"
 
 STATISTIC(NumMemCpyInstr, "Number of memcpy instructions deleted");
+STATISTIC(NumMemCpyInfer, "Number of memcpys inferred");
 STATISTIC(NumMemSetInfer, "Number of memsets inferred");
 STATISTIC(NumMoveToCpy,   "Number of memmoves converted to memcpy");
 STATISTIC(NumCpyToSet,    "Number of memcpys converted to memset");
 
 static int64_t GetOffsetFromIndex(const GEPOperator *GEP, unsigned Idx,
                                   bool &VariableIdxFound,
                                   const DataLayout &DL) {
   // Skip over the first indices.
static bool IsPointerOffset(Value *Ptr1, Value *Ptr2, int64_t &Offset,
   int64_t Offset1 = GetOffsetFromIndex(GEP1, Idx, VariableIdxFound, DL);
   int64_t Offset2 = GetOffsetFromIndex(GEP2, Idx, VariableIdxFound, DL);
   if (VariableIdxFound) return false;
 
   Offset = Offset2-Offset1;
   return true;
 }
 
+static unsigned findCommonAlignment(const DataLayout &DL, const StoreInst *SI,
+                                     const LoadInst *LI) {
+  unsigned StoreAlign = SI->getAlignment();
+  if (!StoreAlign)
+    StoreAlign = DL.getABITypeAlignment(SI->getOperand(0)->getType());
+  unsigned LoadAlign = LI->getAlignment();
+  if (!LoadAlign)
+    LoadAlign = DL.getABITypeAlignment(LI->getType());
+
+  return std::min(StoreAlign, LoadAlign);
+}
+
 
 /// Represents a range of memset'd bytes with the ByteVal value.
 /// This allows us to analyze stores like:
 ///   store 0 -> P+1
 ///   store 0 -> P+0
 ///   store 0 -> P+3
 ///   store 0 -> P+2
 /// which sometimes happens with stores to arrays of structs etc.  When we see
 /// the first store, we make a range [1, 2).  The second store extends the range
 /// to [0, 2).  The third makes a new range [2, 3).  The fourth store joins the
 /// two ranges into [0, 3) which is memset'able.
 namespace {
-struct MemsetRange {
+struct MemIntrinsicRange {
   // Start/End - A semi range that describes the span that this range covers.
   // The range is closed at the start and open at the end: [Start, End).
   int64_t Start, End;
 
-  /// StartPtr - The getelementptr instruction that points to the start of the
-  /// range.
-  Value *StartPtr;
+  /// DestStartPtr - The getelementptr instruction that points to the start of
+  /// the range being stored to.
+  Value *DestStartPtr;
+
+  /// SrcStartPtr - The getelementptr instruction that points to the start of
+  /// the range being read from.
+  Value *SrcStartPtr;
 
   /// Alignment - The known alignment of the first store.
   unsigned Alignment;
 
   /// TheStores - The actual stores that make up this range.
   SmallVector<Instruction*, 16> TheStores;
 
-  bool isProfitableToUseMemset(const DataLayout &DL) const;
+  bool isProfitableToUseMemIntrinsic(const DataLayout &DL) const;
 };
 } // end anon namespace
 
-bool MemsetRange::isProfitableToUseMemset(const DataLayout &DL) const {
-  // If we found more than 4 stores to merge or 16 bytes, use memset.
+bool MemIntrinsicRange::isProfitableToUseMemIntrinsic(
+    const DataLayout &DL) const {
+  // If we found more than 4 stores to merge or 16 bytes, use mem intrinsic.
   if (TheStores.size() >= 4 || End-Start >= 16) return true;
 
   // If there is nothing to merge, don't do anything.
   if (TheStores.size() < 2) return false;
 
-  // If any of the stores are a memset, then it is always good to extend the
-  // memset.
+  // If any of the stores are already a mem intrinsic, then it is always good to
+  // extend it.
   for (Instruction *SI : TheStores)
-    if (!isa<StoreInst>(SI))
+    if (isa<MemIntrinsic>(SI))
       return true;
 
   // Assume that the code generator is capable of merging pairs of stores
   // together if it wants to.
   if (TheStores.size() == 2) return false;
 
   // If we have fewer than 8 stores, it can still be worthwhile to do this.
   // For example, merging 4 i8 stores into an i32 store is useful almost always.
   // However, merging 2 32-bit stores isn't useful on a 32-bit architecture (the
   // memset will be split into 2 32-bit stores anyway) and doing so can
   // pessimize the llvm optimizer.
   //
   // Since we don't have perfect knowledge here, make some assumptions: assume
   // the maximum GPR width is the same size as the largest legal integer
   // size. If so, check to see whether we will end up actually reducing the
   // number of stores used.
   unsigned Bytes = unsigned(End-Start);
   unsigned MaxIntSize = DL.getLargestLegalIntTypeSizeInBits() / 8;
   if (MaxIntSize == 0)
     MaxIntSize = 1;
   unsigned NumPointerStores = Bytes / MaxIntSize;
 
   // Assume the remaining bytes if any are done a byte at a time.
   unsigned NumByteStores = Bytes % MaxIntSize;
 
   // If we will reduce the # stores (according to this heuristic), do the
   // transformation.  This encourages merging 4 x i8 -> i32 and 2 x i16 -> i32
   // etc.
   return TheStores.size() > NumPointerStores+NumByteStores;
 }
 
 
 namespace {
-class MemsetRanges {
+class MemIntrinsicRanges {
   /// A sorted list of the memset ranges.
-  SmallVector<MemsetRange, 8> Ranges;
-  typedef SmallVectorImpl<MemsetRange>::iterator range_iterator;
+  SmallVector<MemIntrinsicRange, 8> Ranges;
+  typedef SmallVectorImpl<MemIntrinsicRange>::iterator range_iterator;
   const DataLayout &DL;
 public:
-  MemsetRanges(const DataLayout &DL) : DL(DL) {}
+  MemIntrinsicRanges(const DataLayout &DL) : DL(DL) {}
 
-  typedef SmallVectorImpl<MemsetRange>::const_iterator const_iterator;
+  typedef SmallVectorImpl<MemIntrinsicRange>::const_iterator const_iterator;
   const_iterator begin() const { return Ranges.begin(); }
   const_iterator end() const { return Ranges.end(); }
   bool empty() const { return Ranges.empty(); }
 
   void addInst(int64_t OffsetFromFirst, Instruction *Inst) {
     if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
       addStore(OffsetFromFirst, SI);
     else
       addMemSet(OffsetFromFirst, cast<MemSetInst>(Inst));
   }
 
   void addStore(int64_t OffsetFromFirst, StoreInst *SI) {
     int64_t StoreSize = DL.getTypeStoreSize(SI->getOperand(0)->getType());
+    unsigned Alignment =
+        SI->getAlignment()
+            ? SI->getAlignment()
+            : DL.getABITypeAlignment(SI->getValueOperand()->getType());
 
     addRange(OffsetFromFirst, StoreSize,
-             SI->getPointerOperand(), SI->getAlignment(), SI);
+             SI->getPointerOperand(), nullptr, Alignment, SI);
+  }
+
+  void addLoadStore(int64_t OffsetFromFirst, LoadInst *LI, StoreInst *SI) {
+    int64_t StoreSize = DL.getTypeStoreSize(SI->getOperand(0)->getType());
+
+    addRange(OffsetFromFirst, StoreSize, SI->getPointerOperand(),
+             LI->getPointerOperand(), findCommonAlignment(DL, SI, LI), SI);
   }
 
   void addMemSet(int64_t OffsetFromFirst, MemSetInst *MSI) {
     int64_t Size = cast<ConstantInt>(MSI->getLength())->getZExtValue();
-    addRange(OffsetFromFirst, Size, MSI->getDest(), MSI->getAlignment(), MSI);
+    addRange(OffsetFromFirst, Size, MSI->getDest(), nullptr,
+             MSI->getAlignment(), MSI);
+  }
+
+  void addMemTransfer(int64_t OffsetFromFirst, MemTransferInst *MTI) {
+    int64_t Size = cast<ConstantInt>(MTI->getLength())->getZExtValue();
+    addRange(OffsetFromFirst, Size, MTI->getDest(), MTI->getSource(),
+             MTI->getAlignment(), MTI);
   }
 
-  void addRange(int64_t Start, int64_t Size, Value *Ptr,
+  void addRange(int64_t Start, int64_t Size, Value *DestPtr, Value *SrcPtr,
                 unsigned Alignment, Instruction *Inst);
 
 };
 
 } // end anon namespace
 
 
-/// Add a new store to the MemsetRanges data structure.  This adds a
+/// Add a new store to the MemIntrinsicRanges data structure.  This adds a
 /// new range for the specified store at the specified offset, merging into
 /// existing ranges as appropriate.
-void MemsetRanges::addRange(int64_t Start, int64_t Size, Value *Ptr,
-                            unsigned Alignment, Instruction *Inst) {
+void MemIntrinsicRanges::addRange(int64_t Start, int64_t Size, Value *DestPtr,
+                                  Value *SrcPtr, unsigned Alignment,
+                                  Instruction *Inst) {
   int64_t End = Start+Size;
 
   range_iterator I = std::lower_bound(Ranges.begin(), Ranges.end(), Start,
-    [](const MemsetRange &LHS, int64_t RHS) { return LHS.End < RHS; });
+    [](const MemIntrinsicRange &LHS, int64_t RHS) { return LHS.End < RHS; });
 
   // We now know that I == E, in which case we didn't find anything to merge
   // with, or that Start <= I->End.  If End < I->Start or I == E, then we need
   // to insert a new range.  Handle this now.
   if (I == Ranges.end() || End < I->Start) {
-    MemsetRange &R = *Ranges.insert(I, MemsetRange());
+    MemIntrinsicRange &R = *Ranges.insert(I, MemIntrinsicRange());
     R.Start        = Start;
     R.End          = End;
-    R.StartPtr     = Ptr;
+    R.DestStartPtr = DestPtr;
+    R.SrcStartPtr  = SrcPtr;
     R.Alignment    = Alignment;
     R.TheStores.push_back(Inst);
     return;
   }
 
   // This store overlaps with I, add it.
   I->TheStores.push_back(Inst);
 
   // At this point, we may have an interval that completely contains our store.
   // If so, just add it to the interval and return.
   if (I->Start <= Start && I->End >= End)
     return;
 
   // Now we know that Start <= I->End and End >= I->Start so the range overlaps
   // but is not entirely contained within the range.
 
   // See if the range extends the start of the range.  In this case, it couldn't
   // possibly cause it to join the prior range, because otherwise we would have
   // stopped on *it*.
   if (Start < I->Start) {
     I->Start = Start;
-    I->StartPtr = Ptr;
+    I->DestStartPtr = DestPtr;
+    I->SrcStartPtr = SrcPtr;
     I->Alignment = Alignment;
   }
 
   // Now we know that Start <= I->End and Start >= I->Start (so the startpoint
   // is in or right at the end of I), and that End >= I->Start.  Extend I out to
   // End.
   if (End > I->End) {
     I->End = End;
Instruction *MemCpyOptPass::tryMergingIntoMemset(Instruction *StartInst,
                                                  Value *StartPtr,
                                                  Value *ByteVal) {
   const DataLayout &DL = StartInst->getModule()->getDataLayout();
 
   // Okay, so we now have a single store that can be splatable.  Scan to find
   // all subsequent stores of the same value to offset from the same pointer.
   // Join these together into ranges, so we can decide whether contiguous blocks
   // are stored.
-  MemsetRanges Ranges(DL);
+  MemIntrinsicRanges Ranges(DL);
 
   BasicBlock::iterator BI(StartInst);
   for (++BI; !isa<TerminatorInst>(BI); ++BI) {
     if (!isa<StoreInst>(BI) && !isa<MemSetInst>(BI)) {
       // If the instruction is readnone, ignore it, otherwise bail out.  We
       // don't even allow readonly here because we don't want something like:
       // A[1] = 2; strlen(A); A[2] = 2; -> memcpy(A, ...); strlen(A).
       if (BI->mayWriteToMemory() || BI->mayReadFromMemory())
Instruction *MemCpyOptPass::tryMergingIntoMemset(Instruction *StartInst,
   // If we create any memsets, we put it right before the first instruction that
   // isn't part of the memset block.  This ensure that the memset is dominated
   // by any addressing instruction needed by the start of the block.
   IRBuilder<> Builder(&*BI);
 
   // Now that we have full information about ranges, loop over the ranges and
   // emit memset's for anything big enough to be worthwhile.
   Instruction *AMemSet = nullptr;
-  for (const MemsetRange &Range : Ranges) {
+  for (const MemIntrinsicRange &Range : Ranges) {
 
     if (Range.TheStores.size() == 1) continue;
 
     // If it is profitable to lower this range to memset, do so now.
-    if (!Range.isProfitableToUseMemset(DL))
+    if (!Range.isProfitableToUseMemIntrinsic(DL))
       continue;
 
     // Otherwise, we do want to transform this!  Create a new memset.
     // Get the starting pointer of the block.
-    StartPtr = Range.StartPtr;
-
-    // Determine alignment
+    StartPtr = Range.DestStartPtr;
     unsigned Alignment = Range.Alignment;
-    if (Alignment == 0) {
-      Type *EltType =
-        cast<PointerType>(StartPtr->getType())->getElementType();
-      Alignment = DL.getABITypeAlignment(EltType);
-    }
+    assert(!Range.SrcStartPtr && "memset containing transfer instruction?");
 
-    AMemSet =
-      Builder.CreateMemSet(StartPtr, ByteVal, Range.End-Range.Start, Alignment);
+    AMemSet = Builder.CreateMemSet(StartPtr, ByteVal, Range.End - Range.Start,
+                                   Alignment);
 
     DEBUG(dbgs() << "Replace stores:\n";
           for (Instruction *SI : Range.TheStores)
             dbgs() << *SI << '\n';
           dbgs() << "With: " << *AMemSet << '\n');
 
     if (!Range.TheStores.empty())
       AMemSet->setDebugLoc(Range.TheStores[0]->getDebugLoc());
 
     // Zap all the stores.
     for (Instruction *SI : Range.TheStores) {
       MD->removeInstruction(SI);
       SI->eraseFromParent();
     }
     ++NumMemSetInfer;
   }
 
   return AMemSet;
 }
 
-static unsigned findCommonAlignment(const DataLayout &DL, const StoreInst *SI,
-                                     const LoadInst *LI) {
-  unsigned StoreAlign = SI->getAlignment();
-  if (!StoreAlign)
-    StoreAlign = DL.getABITypeAlignment(SI->getOperand(0)->getType());
-  unsigned LoadAlign = LI->getAlignment();
-  if (!LoadAlign)
-    LoadAlign = DL.getABITypeAlignment(LI->getType());
+/// When scanning forward over instructions, we look for some other patterns to
+/// fold away. In particular, this looks for stores to neighboring locations of
+/// memory. If it sees enough consecutive ones, it attempts to merge them
+/// together into a memcpy/memset.
+Instruction *MemCpyOptPass::tryMergingIntoMemcpy(Instruction *StartInst,
+                                                       Value *StartDestPtr,
+                                                       Value *StartSrcPtr) {
+  const DataLayout &DL = StartInst->getModule()->getDataLayout();
+  AliasAnalysis &AA = LookupAliasAnalysis();
 
-  return std::min(StoreAlign, LoadAlign);
+  // Okay, so we now have a single store that can be splatable.  Scan to find
+  // all subsequent stores of the same value to offset from the same pointer.
+  // Join these together into ranges, so we can decide whether contiguous blocks
+  // are stored.
+  MemIntrinsicRanges Ranges(DL);
+
+  BasicBlock::iterator BI(StartInst);
+  LoadInst *NextLoad = nullptr;
+  for (;!isa<TerminatorInst>(BI); ++BI) {
+    if (!isa<StoreInst>(BI) && !isa<LoadInst>(BI) &&
+        !isa<MemTransferInst>(BI)) {
+      // If the instruction is readnone, ignore it, otherwise bail out.  We
+      // don't even allow readonly here because we don't want something like:
+      // A[1] = 2; strlen(A); A[2] = 2; -> memcpy(A, ...); strlen(A).
+      if (BI->mayWriteToMemory() || BI->mayReadFromMemory())
+        break;
+      continue;
+    }
+
+    if (LoadInst *LI = dyn_cast<LoadInst>(BI)) {
+      if (NextLoad || !LI->isSimple() || !LI->hasOneUse())
+        break;
+      NextLoad = LI;
+    } else if (StoreInst *NextStore = dyn_cast<StoreInst>(BI)) {
+      // If this is a store, see if we can merge it in.
+      if (!NextLoad || NextLoad != NextStore->getValueOperand() ||
+          !NextStore->isSimple())
+        break;
+
+      // Check to see if this store is to a constant offset from the start ptr.
+      int64_t DestOffset;
+      if (!IsPointerOffset(StartDestPtr, NextStore->getPointerOperand(),
+                           DestOffset, DL))
+        break;
+
+      int64_t SrcOffset;
+      if (!IsPointerOffset(StartSrcPtr, NextLoad->getPointerOperand(),
+                           SrcOffset, DL))
+        break;
+
+      if (DestOffset != SrcOffset)
+        break;
+
+      Ranges.addLoadStore(DestOffset, NextLoad, NextStore);
+      NextLoad = nullptr;
+    } else {
+      MemTransferInst *MTI = cast<MemTransferInst>(BI);
+
+      if (NextLoad || MTI->isVolatile() || !isa<ConstantInt>(MTI->getLength()))
+        break;
+
+      // Check to see if this store is to a constant offset from the start ptr.
+      int64_t DestOffset;
+      if (!IsPointerOffset(StartDestPtr, MTI->getDest(), DestOffset, DL))
+        break;
+
+      int64_t SrcOffset;
+      if (!IsPointerOffset(StartSrcPtr, MTI->getSource(), SrcOffset, DL))
+        break;
+
+      if (SrcOffset != DestOffset)
+        break;
+
+      Ranges.addMemTransfer(SrcOffset, MTI);
+    }
+  }
+
+  // If we have no ranges, then we just had a single store with nothing that
+  // could be merged in.  This is a very common case of course.
+  if (Ranges.empty())
+    return nullptr;
+
+  // If we create any memsets, we put it right before the first instruction that
+  // isn't part of the memset block.  This ensure that the memset is dominated
+  // by any addressing instruction needed by the start of the block.
+  IRBuilder<> Builder(&*BI);
+
+  // Now that we have full information about ranges, loop over the ranges and
+  // emit memset's for anything big enough to be worthwhile.
+  Instruction *AMemCpy = nullptr;
+  for (const MemIntrinsicRange &Range : Ranges) {
+
+    if (Range.TheStores.size() == 1) continue;
+
+    // If it is profitable to lower this range to memcpy, do so now.
+    if (!Range.isProfitableToUseMemIntrinsic(DL))
+      continue;
+
+    // Otherwise, we do want to transform this!  Create a new memcpy.
+    // Get the starting pointers of the block.
+    Value *DestStartPtr = Range.DestStartPtr;
+    Value *SrcStartPtr = Range.SrcStartPtr;
+    unsigned Alignment = Range.Alignment;
+
+    // We don't keep track of load/store pairs well enough to determine whether
+    // a memmove is permitted for possibly-aliasing addresses (both order and
+    // duplicates matter in that case, possibly in ways only determined
+    // dynamically).
+    uint64_t Size = Range.End - Range.Start;
+    if (!AA.isNoAlias(MemoryLocation(DestStartPtr, Size),
+                      MemoryLocation(SrcStartPtr, Size)))
+      continue;
+
+    AMemCpy = Builder.CreateMemCpy(DestStartPtr, SrcStartPtr, Size, Alignment);
+
+    DEBUG(dbgs() << "Replace load/stores:\n";
+          for (Instruction *I : Range.TheStores) {
+            if (StoreInst *SI = dyn_cast<StoreInst>(I))
+              dbgs() << *SI->getValueOperand() << '\n';
+            dbgs() << *I << '\n';
+          }
+          dbgs() << "With: " << *AMemCpy << '\n');
+
+    if (!Range.TheStores.empty())
+      AMemCpy->setDebugLoc(Range.TheStores[0]->getDebugLoc());
+
+    // Zap all the excess operations.
+    for (Instruction *I : Range.TheStores) {
+      if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
+        auto LI = cast<LoadInst>(SI->getValueOperand());
+        MD->removeInstruction(LI);
+        MD->removeInstruction(SI);
+        SI->eraseFromParent();
+        LI->eraseFromParent();
+      } else {
+        MD->removeInstruction(I);
+        I->eraseFromParent();
+      }
+    }
+    ++NumMemCpyInfer;
+  }
+
+  return AMemCpy;
 }
 
 // This method try to lift a store instruction before position P.
 // It will lift the store and its argument + that anything that
 // may alias with these.
 // The method returns true if it was successful.
 static bool moveUp(AliasAnalysis &AA, StoreInst *SI, Instruction *P) {
   // If the store alias this position, early bail out.
if (LI->isSimple() && LI->hasOneUse() &&
           MD->removeInstruction(LI);
           LI->eraseFromParent();
           ++NumMemCpyInstr;
 
           // Make sure we do not invalidate the iterator.
           BBI = M->getIterator();
           return true;
         }
+      } else if (Instruction *I = tryMergingIntoMemcpy(
+                     LI, SI->getPointerOperand(), LI->getPointerOperand())) {
+        BBI = I->getIterator();
+        return true;
       }
 
       // Detect cases where we're performing call slot forwarding, but
       // happen to be using a load-store pair to implement it, rather than
       // a memcpy.
       MemDepResult ldep = MD->getDependency(LI);
       CallInst *C = nullptr;
       if (ldep.isClobber() && !isa<MemCpyInst>(ldep.getInst()))
bool MemCpyOptPass::performMemCpyToMemSetOptzn(MemCpyInst *MemCpy,
   return true;
 }
 
 /// 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 MemCpyOptPass::processMemCpy(MemCpyInst *M) {
+bool MemCpyOptPass::processMemCpy(MemCpyInst *M, BasicBlock::iterator &BBI) {
   // 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 (SrcDepInfo.isClobber())
     if (MemSetInst *MDep = dyn_cast<MemSetInst>(SrcDepInfo.getInst()))
       if (performMemCpyToMemSetOptzn(M, MDep)) {
         MD->removeInstruction(M);
         M->eraseFromParent();
         ++NumCpyToSet;
         return true;
       }
 
+  if (auto I = tryMergingIntoMemcpy(M, M->getDest(), M->getSource()))
+    BBI = I->getIterator();
+
   return false;
 }
 
 /// Transforms memmove calls to memcpy calls when the src/dst are guaranteed
 /// not to alias.
 bool MemCpyOptPass::processMemMove(MemMoveInst *M) {
   AliasAnalysis &AA = LookupAliasAnalysis();
 
for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) {
 
       bool RepeatInstruction = false;
 
       if (StoreInst *SI = dyn_cast<StoreInst>(I))
         MadeChange |= processStore(SI, BI);
       else if (MemSetInst *M = dyn_cast<MemSetInst>(I))
         RepeatInstruction = processMemSet(M, BI);
       else if (MemCpyInst *M = dyn_cast<MemCpyInst>(I))
-        RepeatInstruction = processMemCpy(M);
+        RepeatInstruction = processMemCpy(M, BI);
       else if (MemMoveInst *M = dyn_cast<MemMoveInst>(I))
         RepeatInstruction = processMemMove(M);
       else if (auto CS = CallSite(I)) {
         for (unsigned i = 0, e = CS.arg_size(); i != e; ++i)
           if (CS.isByValArgument(i))
             MadeChange |= processByValArgument(CS, i);
       }
 

test/Transforms/MemCpyOpt/form-memcpy.ll

+; RUN: opt < %s -memcpyopt -S | FileCheck %s
+
+define void @test_simple_memcpy(i32* noalias %dst, i32* noalias %src) {
+; CHECK-LABEL: @test_simple_memcpy
+; CHECK-DAG: [[DST:%.*]] = bitcast i32* %dst to i8*
+; CHECK-DAG: [[SRC:%.*]] = bitcast i32* %src to i8*
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* [[DST]], i8* [[SRC]], i64 16, i32 4, i1 false)
+
+  %val.0 = load i32, i32* %src
+  store i32 %val.0, i32* %dst
+
+  %src.2 = getelementptr i32, i32* %src, i32 2
+  %dst.2 = getelementptr i32, i32* %dst, i32 2
+  %val.2 = load i32, i32* %src.2
+  store i32 %val.2, i32* %dst.2
+
+  %src.1 = getelementptr i32, i32* %src, i32 1
+  %dst.1 = getelementptr i32, i32* %dst, i32 1
+  %val.1 = load i32, i32* %src.1
+  store i32 %val.1, i32* %dst.1
+
+  %src.3 = getelementptr i32, i32* %src, i32 3
+  %dst.3 = getelementptr i32, i32* %dst, i32 3
+  %val.3 = load i32, i32* %src.3
+  store i32 %val.3, i32* %dst.3
+
+  ret void
+}
+
+define void @test_simple_memmove(i32* %dst, i32* %src) {
+; CHECK-LABEL: @test_simple_memmove
+; CHECK-NOT: call void @llvm.memcpy
+; CHECK-NOT: call void @llvm.memmove
+
+  %val.0 = load i32, i32* %src
+  store i32 %val.0, i32* %dst
+
+  %src.2 = getelementptr i32, i32* %src, i32 2
+  %dst.2 = getelementptr i32, i32* %dst, i32 2
+  %val.2 = load i32, i32* %src.2
+  store i32 %val.2, i32* %dst.2
+
+  %src.1 = getelementptr i32, i32* %src, i32 1
+  %dst.1 = getelementptr i32, i32* %dst, i32 1
+  %val.1 = load i32, i32* %src.1
+  store i32 %val.1, i32* %dst.1
+
+  %src.3 = getelementptr i32, i32* %src, i32 3
+  %dst.3 = getelementptr i32, i32* %dst, i32 3
+  %val.3 = load i32, i32* %src.3
+  store i32 %val.3, i32* %dst.3
+
+  ret void
+}
+
+; Make sure we can handle calculating bases & offsets from a real memcpy.
+define void @test_initial_memcpy(i32* noalias %dst, i32* noalias%src) {
+; CHECK-LABEL: @test_initial_memcpy
+; CHECK: {{%.*}} = bitcast i32* %dst to i8*
+; CHECK: {{%.*}} = bitcast i32* %src to i8*
+; CHECK: [[DST:%.*]] = bitcast i32* %dst to i8*
+; CHECK: [[SRC:%.*]] = bitcast i32* %src to i8*
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* [[DST]], i8* [[SRC]], i64 16, i32 4, i1 false)
+
+  %dst.0 = bitcast i32* %dst to i8*
+  %src.0 = bitcast i32* %src to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst.0, i8* %src.0, i64 4, i32 4, i1 false)
+
+  %src.2 = getelementptr i32, i32* %src, i32 2
+  %dst.2 = getelementptr i32, i32* %dst, i32 2
+  %val.2 = load i32, i32* %src.2
+  store i32 %val.2, i32* %dst.2
+
+  %src.1 = getelementptr i32, i32* %src, i32 1
+  %dst.1 = getelementptr i32, i32* %dst, i32 1
+  %val.1 = load i32, i32* %src.1
+  store i32 %val.1, i32* %dst.1
+
+  %src.3 = getelementptr i32, i32* %src, i32 3
+  %dst.3 = getelementptr i32, i32* %dst, i32 3
+  %val.3 = load i32, i32* %src.3
+  store i32 %val.3, i32* %dst.3
+
+  ret void
+}
+
+define void @test_volatile_skipped(i32* noalias %dst, i32* noalias %src) {
+; CHECK-LABEL: @test_volatile_skipped
+; CHECK-NOT: call void @llvm.memcpy
+; CHECK-NOT: call void @llvm.memmove
+
+  %val.0 = load i32, i32* %src
+  store i32 %val.0, i32* %dst
+
+  %src.2 = getelementptr i32, i32* %src, i32 2
+  %dst.2 = getelementptr i32, i32* %dst, i32 2
+  %val.2 = load volatile i32, i32* %src.2
+  store i32 %val.2, i32* %dst.2
+
+  %src.1 = getelementptr i32, i32* %src, i32 1
+  %dst.1 = getelementptr i32, i32* %dst, i32 1
+  %val.1 = load i32, i32* %src.1
+  store i32 %val.1, i32* %dst.1
+
+  %src.3 = getelementptr i32, i32* %src, i32 3
+  %dst.3 = getelementptr i32, i32* %dst, i32 3
+  %val.3 = load i32, i32* %src.3
+  store i32 %val.3, i32* %dst.3
+
+  ret void
+}
+
+define void @test_atomic_skipped(i32* noalias %dst, i32* noalias %src) {
+; CHECK-LABEL: @test_atomic_skipped
+; CHECK-NOT: call void @llvm.memcpy
+; CHECK-NOT: call void @llvm.memmove
+
+  %val.0 = load i32, i32* %src
+  store i32 %val.0, i32* %dst
+
+  %src.2 = getelementptr i32, i32* %src, i32 2
+  %dst.2 = getelementptr i32, i32* %dst, i32 2
+  %val.2 = load i32, i32* %src.2
+  store i32 %val.2, i32* %dst.2
+
+  %src.1 = getelementptr i32, i32* %src, i32 1
+  %dst.1 = getelementptr i32, i32* %dst, i32 1
+  %val.1 = load i32, i32* %src.1
+  store atomic i32 %val.1, i32* %dst.1 unordered, align 4
+
+  %src.3 = getelementptr i32, i32* %src, i32 3
+  %dst.3 = getelementptr i32, i32* %dst, i32 3
+  %val.3 = load i32, i32* %src.3
+  store i32 %val.3, i32* %dst.3
+
+  ret void
+}
+
+define i32 @test_multi_use_skipped(i32* noalias %dst, i32* noalias %src) {
+; CHECK-LABEL: @test_multi_use_skipped
+; CHECK-NOT: call void @llvm.memcpy
+; CHECK-NOT: call void @llvm.memmove
+
+  %val.0 = load i32, i32* %src
+  store i32 %val.0, i32* %dst
+
+  %src.2 = getelementptr i32, i32* %src, i32 2
+  %dst.2 = getelementptr i32, i32* %dst, i32 2
+  %val.2 = load i32, i32* %src.2
+  store i32 %val.2, i32* %dst.2
+
+  %src.1 = getelementptr i32, i32* %src, i32 1
+  %dst.1 = getelementptr i32, i32* %dst, i32 1
+  %val.1 = load i32, i32* %src.1
+  store i32 %val.1, i32* %dst.1
+
+  %src.3 = getelementptr i32, i32* %src, i32 3
+  %dst.3 = getelementptr i32, i32* %dst, i32 3
+  %val.3 = load i32, i32* %src.3
+  store i32 %val.3, i32* %dst.3
+
+  ret i32 %val.1
+}
+
+define void @test_side_effect_skipped(i32* noalias %dst, i32* noalias %src) {
+; CHECK-LABEL: @test_side_effect_skipped
+; CHECK-NOT: call void @llvm.memcpy
+; CHECK-NOT: call void @llvm.memmove
+
+  %val.0 = load i32, i32* %src
+  store i32 %val.0, i32* %dst
+
+  %src.2 = getelementptr i32, i32* %src, i32 2
+  %dst.2 = getelementptr i32, i32* %dst, i32 2
+  %val.2 = load i32, i32* %src.2
+  store i32 %val.2, i32* %dst.2
+
+  call void asm sideeffect "", ""()
+
+  %src.1 = getelementptr i32, i32* %src, i32 1
+  %dst.1 = getelementptr i32, i32* %dst, i32 1
+  %val.1 = load i32, i32* %src.1
+  store i32 %val.1, i32* %dst.1
+
+  %src.3 = getelementptr i32, i32* %src, i32 3
+  %dst.3 = getelementptr i32, i32* %dst, i32 3
+  %val.3 = load i32, i32* %src.3
+  store i32 %val.3, i32* %dst.3
+
+  ret void
+}
+
+define void @test_holes_handled(i32* noalias %dst, i32* noalias %src) {
+; CHECK-LABEL: @test_holes_handled
+; CHECK-DAG: [[DST:%.*]] = bitcast i32* %dst to i8*
+; CHECK-DAG: [[SRC:%.*]] = bitcast i32* %src to i8*
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* [[DST]], i8* [[SRC]], i64 16, i32 4, i1 false)
+; CHECK-DAG: [[DST:%.*]] = bitcast i32* %dst.7 to i8*
+; CHECK-DAG: [[SRC:%.*]] = bitcast i32* %src.7 to i8*
+; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* [[DST]], i8* [[SRC]], i64 16, i32 4, i1 false)
+
+  %val.0 = load i32, i32* %src
+  store i32 %val.0, i32* %dst
+
+  %src.2 = getelementptr i32, i32* %src, i32 2
+  %dst.2 = getelementptr i32, i32* %dst, i32 2
+  %val.2 = load i32, i32* %src.2
+  store i32 %val.2, i32* %dst.2
+
+  %src.1 = getelementptr i32, i32* %src, i32 1
+  %dst.1 = getelementptr i32, i32* %dst, i32 1
+  %val.1 = load i32, i32* %src.1
+  store i32 %val.1, i32* %dst.1
+
+  %src.3 = getelementptr i32, i32* %src, i32 3
+  %dst.3 = getelementptr i32, i32* %dst, i32 3
+  %val.3 = load i32, i32* %src.3
+  store i32 %val.3, i32* %dst.3
+
+
+  %src.7 = getelementptr i32, i32* %src, i32 7
+  %dst.7 = getelementptr i32, i32* %dst, i32 7
+  %val.7 = load i32, i32* %src.7
+  store i32 %val.7, i32* %dst.7
+
+  %src.9 = getelementptr i32, i32* %src, i32 9
+  %dst.9 = getelementptr i32, i32* %dst, i32 9
+  %val.9 = load i32, i32* %src.9
+  store i32 %val.9, i32* %dst.9
+
+  %src.10 = getelementptr i32, i32* %src, i32 10
+  %dst.10 = getelementptr i32, i32* %dst, i32 10
+  %val.10 = load i32, i32* %src.10
+  store i32 %val.10, i32* %dst.10
+
+  %src.8 = getelementptr i32, i32* %src, i32 8
+  %dst.8 = getelementptr i32, i32* %dst, i32 8
+  %val.8 = load i32, i32* %src.8
+  store i32 %val.8, i32* %dst.8
+
+  ret void
+}
+
+define void @test_offset_mismatch(i32* noalias %dst, i32* noalias %src) {
+; CHECK-LABEL: @test_offset_mismatch
+; CHECK-NOT: call void @llvm.memcpy
+; CHECK-NOT: call void @llvm.memmove
+
+  %val.0 = load i32, i32* %src
+  store i32 %val.0, i32* %dst
+
+  %src.2 = getelementptr i32, i32* %src, i32 2
+  %dst.2 = getelementptr i32, i32* %dst, i32 1
+  %val.2 = load i32, i32* %src.2
+  store i32 %val.2, i32* %dst.2
+
+  %src.1 = getelementptr i32, i32* %src, i32 1
+  %dst.1 = getelementptr i32, i32* %dst, i32 2
+  %val.1 = load i32, i32* %src.1
+  store i32 %val.1, i32* %dst.1
+
+  %src.3 = getelementptr i32, i32* %src, i32 3
+  %dst.3 = getelementptr i32, i32* %dst, i32 3
+  %val.3 = load i32, i32* %src.3
+  store i32 %val.3, i32* %dst.3
+
+  ret void
+}
+
+define void @test_non_idempotent_ops(i8* %dst, i8* %src) {
+; CHECK-LABEL: @test_non_idempotent_ops
+; CHECK-NOT: call void @llvm.memcpy
+; CHECK-NOT: call void @llvm.memmove
+
+  %val.0 = load i8, i8* %src
+  store i8 %val.0, i8* %dst
+
+  %src.2 = getelementptr i8, i8* %src, i8 2
+  %dst.2 = getelementptr i8, i8* %dst, i8 2
+  %val.2 = load i8, i8* %src.2
+  store i8 %val.2, i8* %dst.2
+
+  %val.0.dup = load i8, i8* %src
+  store i8 %val.0.dup, i8* %dst
+
+  %src.1 = getelementptr i8, i8* %src, i8 1
+  %dst.1 = getelementptr i8, i8* %dst, i8 1
+  %val.1 = load i8, i8* %src.1
+  store i8 %val.1, i8* %dst.1
+
+  %src.3 = getelementptr i8, i8* %src, i8 3
+  %dst.3 = getelementptr i8, i8* %dst, i8 3
+  %val.3 = load i8, i8* %src.3
+  store i8 %val.3, i8* %dst.3
+
+  ret void
+}
+
+define void @test_intervening_op(i32* noalias %dst, i32* noalias %src) {
+; CHECK-LABEL: @test_intervening_op
+; CHECK-NOT: call void @llvm.memcpy
+
+  %val.0 = load i32, i32* %src
+  store i32 %val.0, i32* %dst
+
+  %src.2 = getelementptr i32, i32* %src, i32 2
+  %src16.2 = bitcast i32* %src.2 to i16*
+  %dst.2 = getelementptr i32, i32* %dst, i32 2
+  %val16.2 = load i16, i16* %src16.2
+  %val.2 = sext i16 %val16.2 to i32
+  store i32 %val.2, i32* %dst.2
+
+  %src.1 = getelementptr i32, i32* %src, i32 1
+  %dst.1 = getelementptr i32, i32* %dst, i32 1
+  %val.1 = load i32, i32* %src.1
+  store i32 %val.1, i32* %dst.1
+
+  %src.3 = getelementptr i32, i32* %src, i32 3
+  %dst.3 = getelementptr i32, i32* %dst, i32 3
+  %val.3 = load i32, i32* %src.3
+  store i32 %val.3, i32* %dst.3
+
+  ret void
+}
+
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8*, i8*, i64, i32, i1)