[MemCpyOpt] Preserve MemorySSA.

[fhahn]

Summary

This patch updates MemCpyOpt to preserve MemorySSA. It uses the
MemoryDef at the insertion point of the builder and inserts the new def
after that def.

In some cases, we just modify a memory instruction. In that case, get
the defining access, then remove the memory access and add a new one.
If the defining access is in a different block, insert a new def at the
beginning of the current block, otherwise after the defining access.

[fhahn]

Fix some bugs in the updating, add test cases.

There is one case where we turn a memmove into a memcpy, which currently is a no-op. We should probably remove the access and re-add it, but I am not sure how to best ensure we re-add the access at the correct position.

[asbirlea]

I was working on having MemCpyOpt preserve and use MSSA, in order to replace the use of MemDepAnalysis entirely. But I'm happy with having MSSA preserved first :-).

Some quick comments below.

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

413

assert (LastDef && "Must exist.");

419

Remove braces.

llvm/test/Transforms/MemCpyOpt/perserve-memssa.ll

1 ↗

(On Diff #288764)

Typo in file name, rename file to preserve-memssa.

3 ↗

(On Diff #288764)

;REQUIRES: asserts

[fhahn]

In D86651#2251167, @asbirlea wrote:

I was working on having MemCpyOpt preserve and use MSSA, in order to replace the use of MemDepAnalysis entirely. But I'm happy with having MSSA preserved first :-).

I agree that MemCpyOpt is another good candidate the use MSSA and I think it should be possible to share some of the analysis/approach from DSE + MemorySSA to also remove the BB only limitation.

But preserving it is a relatively small step compared to that so we can take the initial step with DSE + MemorySSA :)

Some quick comments below.

Thanks, should be addressed!

[fhahn]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

413

Done, added an assert for both LastAcc and LastDef.

[fhahn]

Add MemorySSAAnalysis to preserved also for NPM.

[asbirlea]

A small note to test with EXPENSIVE_CHECKS as well, as there's extra verification there.

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

324

I'm not sure I fully understand how these two work.
LastDef is the last definition, last access, or the defining access for the new MemoryAccess created below. It should be always updated in the loop. Should it also be updated when BI is not a store or memset but the access is a MemoryDef?
LastAcc is the insertion point (perhaps rename this one?)

The insertion point for the memset in the BB, seems to be where BI left off, so then LastAcc is either the same as LastDef or one before, so it should be updated more often than just for non-store and non-memset?

If my understanding is incomplete, could you please explain?

Unrelated, below, in Ranges, the StartInst is also added and I think that's a store. So LastAcc could be initialized to MSSAU->getMemorySSA()->getMemoryAccess(StartInstI); outside the loop?

1102

Can you add a comment explaining this?
The new memset is inserted after the memcpy, but it is known that its defining access is the memset about to be removed which immediately precedes the memcpy.

[fhahn]

Add additional comments as suggested, thanks!

[fhahn]

Further simplify LastMemDef, MemInsertPoint management.

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

324

I'm not sure I fully understand how these two work.
LastDef is the last definition, last access, or the defining access for the new MemoryAccess created below. It should be always updated in the loop. Should it also be updated when BI is not a store or memset but the access is a MemoryDef?
LastAcc is the insertion point (perhaps rename this one?)

I renamed LastAcc to MemInsertPoint.

The insertion point for the memset in the BB, seems to be where BI left off, so then LastAcc is either the same as LastDef or one before, so it should be updated more often than just for non-store and non-memset?

Yes, MemInsertPoint (LastAcc) should be updated on each iteration. I updated the code. I also added comments explaining in more detail what both variables track. MemInsertPoint is either LastMemDef or the last memory user of before the insertion point for the new memsets.

Unrelated, below, in Ranges, the StartInst is also added and I think that's a store. So LastAcc could be initialized to MSSAU->getMemorySSA()->getMemoryAccess(StartInstI); outside the loop?

Yes I think it could be initialized with StartInstI, but it is set in each loop iteration now and should be much clearer, so I don't think it is necessary to additionally initialize it outside the loop

[asbirlea]

Diff looks good to me.
Same comment as before about testing with EXPENSIVE_CHECKS to catch potential missed updates.
Thank you for working on this!

llvm/include/llvm/Transforms/Scalar/MemCpyOptimizer.h

 class AssumptionCache;
 class CallInst;
 class DominatorTree;
 class Function;
 class Instruction;
 class MemCpyInst;
 class MemMoveInst;
 class MemoryDependenceResults;
+class MemorySSA;
+class MemorySSAUpdater;
 class MemSetInst;
 class StoreInst;
 class TargetLibraryInfo;
 class Value;
 
 class MemCpyOptPass : public PassInfoMixin<MemCpyOptPass> {
   MemoryDependenceResults *MD = nullptr;
   TargetLibraryInfo *TLI = nullptr;
+  MemorySSAUpdater *MSSAU = nullptr;
   std::function<AliasAnalysis &()> LookupAliasAnalysis;
   std::function<AssumptionCache &()> LookupAssumptionCache;
   std::function<DominatorTree &()> LookupDomTree;
 
 public:
   MemCpyOptPass() = default;
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   // Glue for the old PM.
   bool runImpl(Function &F, MemoryDependenceResults *MD_,
-               TargetLibraryInfo *TLI_,
+               TargetLibraryInfo *TLI_, MemorySSA *MSSA_,
                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);

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/MemoryLocation.h"
+#include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<MemoryDependenceWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
     AU.addPreserved<MemoryDependenceWrapperPass>();
+    AU.addPreserved<MemorySSAWrapperPass>();
   }
 };
 
 } // end anonymous namespace
 
 char MemCpyOptLegacyPass::ID = 0;
 
 /// The public interface to this file...
Instruction *MemCpyOptPass::tryMergingIntoMemset(Instruction *StartInst,
   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);
 
+  Instruction *LastWrite = nullptr;
   BasicBlock::iterator BI(StartInst);
   for (++BI; !BI->isTerminator(); ++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())
         break;
       continue;
     }
 
     if (StoreInst *NextStore = dyn_cast<StoreInst>(BI)) {
       // If this is a store, see if we can merge it in.
       if (!NextStore->isSimple()) break;
 
       // Check to see if this stored value is of the same byte-splattable value.
       Value *StoredByte = isBytewiseValue(NextStore->getOperand(0), DL);
       if (isa<UndefValue>(ByteVal) && StoredByte)
         ByteVal = StoredByte;
       if (ByteVal != StoredByte)
         break;
 
       // Check to see if this store is to a constant offset from the start ptr.
       Optional<int64_t> Offset =
           isPointerOffset(StartPtr, NextStore->getPointerOperand(), DL);
       if (!Offset)
         break;
 
       Ranges.addStore(*Offset, NextStore);
+      LastWrite = NextStore;
     } else {
       MemSetInst *MSI = cast<MemSetInst>(BI);
 
       if (MSI->isVolatile() || ByteVal != MSI->getValue() ||
           !isa<ConstantInt>(MSI->getLength()))
         break;
 
       // Check to see if this store is to a constant offset from the start ptr.
       Optional<int64_t> Offset = isPointerOffset(StartPtr, MSI->getDest(), DL);
       if (!Offset)
         break;
 
       Ranges.addMemSet(*Offset, MSI);
+      LastWrite = MSI;
     }
   }
 
   // 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 had at least one store that could be merged in, add the starting
   // store as well.  We try to avoid this unless there is at least something
   // interesting as a small compile-time optimization.
   Ranges.addInst(0, 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;
+
+  MemoryAccess *LastAcc = nullptr;
+  if (MSSAU) {
+    LastAcc = MSSAU->getMemorySSA()->getMemoryAccess(LastWrite);
+  }
   for (const MemsetRange &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))
       continue;
 
     // Otherwise, we do want to transform this!  Create a new memset.
     // Get the starting pointer of the block.
     StartPtr = Range.StartPtr;
 
     AMemSet = Builder.CreateMemSet(StartPtr, ByteVal, Range.End - Range.Start,
                                    MaybeAlign(Range.Alignment));
     LLVM_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());
 
+    if (MSSAU) {
+      auto *NewAccess =
+          MSSAU->createMemoryAccessAfter(AMemSet, LastAcc, LastAcc);
+      MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
+    }
+
     // Zap all the stores.
     for (Instruction *SI : Range.TheStores) {
+      if (MSSAU) {
+        if (isa<MemoryUseOrDef>(LastAcc) &&
+            SI == cast<MemoryUseOrDef>(LastAcc)->getMemoryInst())
+          LastAcc = cast<MemoryUseOrDef>(LastAcc)->getDefiningAccess();
+        MSSAU->removeMemoryAccess(SI);
+      }
       MD->removeInstruction(SI);
       SI->eraseFromParent();
     }
+
     ++NumMemSetInfer;
   }
 
   return AMemSet;
 }
 
 // This method try to lift a store instruction before position P.
 // It will lift the store and its argument + that anything that
if (LI->isSimple() && LI->hasOneUse() &&
           else
             M = Builder.CreateMemCpy(
                 SI->getPointerOperand(), SI->getAlign(),
                 LI->getPointerOperand(), LI->getAlign(), Size);
 
           LLVM_DEBUG(dbgs() << "Promoting " << *LI << " to " << *SI << " => "
                             << *M << "\n");
 
+          if (MSSAU) {
+            assert(isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(P)));
+            auto *LastDef =
+                cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(P));
+            auto *NewAccess =
+                MSSAU->createMemoryAccessAfter(M, LastDef, LastDef);
+            MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
+            MSSAU->removeMemoryAccess(SI);
+            MSSAU->removeMemoryAccess(LI);
+          }
+
           MD->removeInstruction(SI);
           SI->eraseFromParent();
           MD->removeInstruction(LI);
           LI->eraseFromParent();
           ++NumMemCpyInstr;
 
           // Make sure we do not invalidate the iterator.
           BBI = M->getIterator();
if (LI->isSimple() && LI->hasOneUse() &&
 
       if (C) {
         bool changed = performCallSlotOptzn(
             LI, SI->getPointerOperand()->stripPointerCasts(),
             LI->getPointerOperand()->stripPointerCasts(),
             DL.getTypeStoreSize(SI->getOperand(0)->getType()),
             commonAlignment(SI->getAlign(), LI->getAlign()), C);
         if (changed) {
+          if (MSSAU) {
+            MSSAU->removeMemoryAccess(SI);
+            MSSAU->removeMemoryAccess(LI);
+          }
+
           MD->removeInstruction(SI);
           SI->eraseFromParent();
           MD->removeInstruction(LI);
           LI->eraseFromParent();
           ++NumMemCpyInstr;
           return true;
         }
       }
if (Value *ByteVal = isBytewiseValue(V, DL)) {
     if (T->isAggregateType()) {
       uint64_t Size = DL.getTypeStoreSize(T);
       IRBuilder<> Builder(SI);
       auto *M = Builder.CreateMemSet(SI->getPointerOperand(), ByteVal, Size,
                                      SI->getAlign());
 
       LLVM_DEBUG(dbgs() << "Promoting " << *SI << " to " << *M << "\n");
 
+      if (MSSAU) {
+        assert(isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(SI)));
+        auto *LastDef =
+            cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(SI));
+        auto *NewAccess = MSSAU->createMemoryAccessAfter(M, LastDef, LastDef);
+        MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
+        MSSAU->removeMemoryAccess(SI);
+      }
+
       MD->removeInstruction(SI);
       SI->eraseFromParent();
       NumMemSetInfer++;
 
       // Make sure we do not invalidate the iterator.
       BBI = M->getIterator();
       return true;
     }
bool MemCpyOptPass::performCallSlotOptzn(Instruction *cpy, Value *cpyDest,
   unsigned KnownIDs[] = {LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
                          LLVMContext::MD_noalias,
                          LLVMContext::MD_invariant_group,
                          LLVMContext::MD_access_group};
   combineMetadata(C, cpy, KnownIDs, true);
 
   // Remove the memcpy.
   MD->removeInstruction(cpy);
+
+  if (MSSAU) {
+    MSSAU->removeMemoryAccess(C);
+    auto *Def = MSSAU->getMemorySSA()->getMemoryAccess(C)->getDefiningAccess();
+    if (Def->getBlock() == C->getParent()) {
+      auto *NewAccess = MSSAU->createMemoryAccessAfter(C, Def, Def);
+      MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
+    } else {
+      auto *NewAccess = MSSAU->createMemoryAccessInBB(
+          C, nullptr, C->getParent(), MemorySSA::Beginning);
+      MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
+    }
+
+    MSSAU->removeMemoryAccess(cpy);
+  }
+
   ++NumMemCpyInstr;
 
   return true;
 }
 
 /// We've found that the (upward scanning) memory dependence of memcpy 'M' is
 /// the memcpy 'MDep'. Try to simplify M to copy from MDep's input if we can.
 bool MemCpyOptPass::processMemCpyMemCpyDependence(MemCpyInst *M,
bool MemCpyOptPass::processMemCpyMemCpyDependence(MemCpyInst *M,
 
   // If all checks passed, then we can transform M.
   LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy->memcpy src:\n"
                     << *MDep << '\n' << *M << '\n');
 
   // TODO: Is this worth it if we're creating a less aligned memcpy? For
   // example we could be moving from movaps -> movq on x86.
   IRBuilder<> Builder(M);
+  Instruction *NewM;
   if (UseMemMove)
-    Builder.CreateMemMove(M->getRawDest(), M->getDestAlign(),
+    NewM = Builder.CreateMemMove(M->getRawDest(), M->getDestAlign(),
                                  MDep->getRawSource(), MDep->getSourceAlign(),
                                  M->getLength(), M->isVolatile());
   else
-    Builder.CreateMemCpy(M->getRawDest(), M->getDestAlign(),
+    NewM = Builder.CreateMemCpy(M->getRawDest(), M->getDestAlign(),
                                 MDep->getRawSource(), MDep->getSourceAlign(),
                                 M->getLength(), M->isVolatile());
 
+  if (MSSAU) {
+    assert(isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(M)));
+    auto *LastDef = cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(M));
+    auto *NewAccess = MSSAU->createMemoryAccessAfter(NewM, LastDef, LastDef);
+    MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
+    MSSAU->removeMemoryAccess(M);
+  }
+
   // 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
if (DestSize->getType() != SrcSize->getType()) {
     else
       DestSize = Builder.CreateZExt(DestSize, SrcSize->getType());
   }
 
   Value *Ule = Builder.CreateICmpULE(DestSize, SrcSize);
   Value *SizeDiff = Builder.CreateSub(DestSize, SrcSize);
   Value *MemsetLen = Builder.CreateSelect(
       Ule, ConstantInt::getNullValue(DestSize->getType()), SizeDiff);
-  Builder.CreateMemSet(
+  Instruction *NewM = Builder.CreateMemSet(
       Builder.CreateGEP(Dest->getType()->getPointerElementType(), Dest,
                         SrcSize),
       MemSet->getOperand(1), MemsetLen, MaybeAlign(Align));
 
+  if (MSSAU) {
+    assert(isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy)));
+    auto *LastDef =
+        cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy));
+    auto *NewAccess = MSSAU->createMemoryAccessAfter(NewM, LastDef, LastDef);
+    MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
+    MSSAU->removeMemoryAccess(MemSet);
+  }
+
   MD->removeInstruction(MemSet);
   MemSet->eraseFromParent();
   return true;
 }
 
 /// Determine whether the instruction has undefined content for the given Size,
 /// either because it was freshly alloca'd or started its lifetime.
 static bool hasUndefContents(Instruction *I, ConstantInt *Size) {
MemDepResult DepInfo = MD->getPointerDependencyFrom(
         MemCpyLoc, true, MemSet->getIterator(), MemSet->getParent());
     if (DepInfo.isDef() && hasUndefContents(DepInfo.getInst(), CopySize))
       CopySize = MemSetSize;
     else
       return false;
   }
 
   IRBuilder<> Builder(MemCpy);
-  Builder.CreateMemSet(MemCpy->getRawDest(), MemSet->getOperand(1), CopySize,
-                       MaybeAlign(MemCpy->getDestAlignment()));
+  Instruction *NewM =
+      Builder.CreateMemSet(MemCpy->getRawDest(), MemSet->getOperand(1),
+                           CopySize, MaybeAlign(MemCpy->getDestAlignment()));
+  if (MSSAU) {
+    auto *LastDef =
+        cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy));
+    auto *NewAccess = MSSAU->createMemoryAccessAfter(NewM, LastDef, LastDef);
+    MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
+  }
+
   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, 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()) {
     ++BBI;
+    if (MSSAU)
+      MSSAU->removeMemoryAccess(M);
+
     MD->removeInstruction(M);
     M->eraseFromParent();
     return true;
   }
 
   // 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(),
                                            M->getModule()->getDataLayout())) {
         IRBuilder<> Builder(M);
+        Instruction *NewM =
             Builder.CreateMemSet(M->getRawDest(), ByteVal, M->getLength(),
                                  MaybeAlign(M->getDestAlignment()), false);
+        if (MSSAU) {
+          auto *LastDef =
+              cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(M));
+          auto *NewAccess =
+              MSSAU->createMemoryAccessAfter(NewM, LastDef, LastDef);
+          MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
+          MSSAU->removeMemoryAccess(M);
+        }
+
         MD->removeInstruction(M);
         M->eraseFromParent();
         ++NumCpyToSet;
         return true;
       }
 
   MemDepResult DepInfo = MD->getDependency(M);
 
bool MemCpyOptPass::processMemCpy(MemCpyInst *M, BasicBlock::iterator &BBI) {
   if (DepInfo.isClobber()) {
     if (CallInst *C = dyn_cast<CallInst>(DepInfo.getInst())) {
       // FIXME: Can we pass in either of dest/src alignment here instead
       // of conservatively taking the minimum?
       Align Alignment = std::min(M->getDestAlign().valueOrOne(),
                                  M->getSourceAlign().valueOrOne());
       if (performCallSlotOptzn(M, M->getDest(), M->getSource(),
                                CopySize->getZExtValue(), Alignment, C)) {
+        if (MSSAU)
+          MSSAU->removeMemoryAccess(M);
+
         MD->removeInstruction(M);
         M->eraseFromParent();
         return true;
       }
     }
   }
 
   MemoryLocation SrcLoc = MemoryLocation::getForSource(M);
   MemDepResult SrcDepInfo = MD->getPointerDependencyFrom(
       SrcLoc, true, M->getIterator(), M->getParent());
 
   if (SrcDepInfo.isClobber()) {
     if (MemCpyInst *MDep = dyn_cast<MemCpyInst>(SrcDepInfo.getInst()))
       return processMemCpyMemCpyDependence(M, MDep);
   } else if (SrcDepInfo.isDef()) {
     if (hasUndefContents(SrcDepInfo.getInst(), CopySize)) {
+      if (MSSAU)
+        MSSAU->removeMemoryAccess(M);
+
       MD->removeInstruction(M);
       M->eraseFromParent();
       ++NumMemCpyInstr;
       return true;
     }
   }
 
   if (SrcDepInfo.isClobber())
     if (MemSetInst *MDep = dyn_cast<MemSetInst>(SrcDepInfo.getInst()))
       if (performMemCpyToMemSetOptzn(M, MDep)) {
+        if (MSSAU)
+          MSSAU->removeMemoryAccess(M);
         MD->removeInstruction(M);
         M->eraseFromParent();
         ++NumCpyToSet;
         return true;
       }
 
   return false;
 }
bool MemCpyOptPass::processMemMove(MemMoveInst *M) {
 
   // If not, then we know we can transform this.
   Type *ArgTys[3] = { M->getRawDest()->getType(),
                       M->getRawSource()->getType(),
                       M->getLength()->getType() };
   M->setCalledFunction(Intrinsic::getDeclaration(M->getModule(),
                                                  Intrinsic::memcpy, ArgTys));
 
+  if (MSSAU) {
+    auto *Def = MSSAU->getMemorySSA()->getMemoryAccess(M)->getDefiningAccess();
+    if (Def->getBlock() == M->getParent()) {
+      auto *NewAccess = MSSAU->createMemoryAccessAfter(M, Def, Def);
+      MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
+    } else {
+      auto *NewAccess = MSSAU->createMemoryAccessInBB(
+          M, nullptr, M->getParent(), MemorySSA::Beginning);
+      MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
+    }
+
+    MSSAU->removeMemoryAccess(M);
+  }
+
   // MemDep may have over conservative information about this instruction, just
   // conservatively flush it from the cache.
   MD->removeInstruction(M);
 
   ++NumMoveToCpy;
   return true;
 }
 
PreservedAnalyses MemCpyOptPass::run(Function &F, FunctionAnalysisManager &AM) {
   };
   auto LookupAssumptionCache = [&]() -> AssumptionCache & {
     return AM.getResult<AssumptionAnalysis>(F);
   };
   auto LookupDomTree = [&]() -> DominatorTree & {
     return AM.getResult<DominatorTreeAnalysis>(F);
   };
 
-  bool MadeChange = runImpl(F, &MD, &TLI, LookupAliasAnalysis,
-                            LookupAssumptionCache, LookupDomTree);
+  auto *MSSA = AM.getCachedResult<MemorySSAAnalysis>(F);
+
+  bool MadeChange =
+      runImpl(F, &MD, &TLI, MSSA ? &MSSA->getMSSA() : nullptr,
+              LookupAliasAnalysis, LookupAssumptionCache, LookupDomTree);
   if (!MadeChange)
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
   PA.preserve<GlobalsAA>();
   PA.preserve<MemoryDependenceAnalysis>();
   return PA;
 }
 
 bool MemCpyOptPass::runImpl(
     Function &F, MemoryDependenceResults *MD_, TargetLibraryInfo *TLI_,
-    std::function<AliasAnalysis &()> LookupAliasAnalysis_,
+    MemorySSA *MSSA_, std::function<AliasAnalysis &()> LookupAliasAnalysis_,
     std::function<AssumptionCache &()> LookupAssumptionCache_,
     std::function<DominatorTree &()> LookupDomTree_) {
+  MemorySSAUpdater MSSAU_(MSSA_);
   bool MadeChange = false;
   MD = MD_;
   TLI = TLI_;
+  MSSAU = MSSA_ ? &MSSAU_ : nullptr;
   LookupAliasAnalysis = std::move(LookupAliasAnalysis_);
   LookupAssumptionCache = std::move(LookupAssumptionCache_);
   LookupDomTree = std::move(LookupDomTree_);
 
   // If we don't have at least memset and memcpy, there is little point of doing
   // anything here.  These are required by a freestanding implementation, so if
   // even they are disabled, there is no point in trying hard.
   if (!TLI->has(LibFunc_memset) || !TLI->has(LibFunc_memcpy))
bool MemCpyOptLegacyPass::runOnFunction(Function &F) {
   };
   auto LookupAssumptionCache = [this, &F]() -> AssumptionCache & {
     return getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
   };
   auto LookupDomTree = [this]() -> DominatorTree & {
     return getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   };
 
-  return Impl.runImpl(F, MD, TLI, LookupAliasAnalysis, LookupAssumptionCache,
+  auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
+
+  return Impl.runImpl(F, MD, TLI, MSSAWP ? &MSSAWP->getMSSA() : nullptr,
+                      LookupAliasAnalysis, LookupAssumptionCache,
                       LookupDomTree);
 }