Introduce a basic MemorySSA updater, that supports insertDef and insertUse operations.

[• dberlin]

Summary

This creates a basic MemorySSA updater that handles arbitrary insertion of uses and defs into MemorySSA.
I will extend it to handle moves (the current splice API).

It can be made to handle arbitrary control flow changes.
Currently, it uses the same updater algorithm from D28934.

The main difference is because MemorySSA is single variable, we have
the complete def and use list, and don't need anyone to give it to us
as part of the API. We also have to rename stores below us in some
cases.

If we go that direction in that patch, i will merge all the updater
implementations (using an updater_traits or something to provide the
get* functions we use, called read*/write* in that patch).

Sadly, the current SSAUpdater algorithm is way too slow to use for
what we are doing here.

I have updated the tests we have to basically build memoryssa
incrementally using the updater api, and make sure it still comes out
the same.

I have also added a fairly complex testcase, but a few more coming.

[• dberlin]

• Update formatting

[george.burgess.iv]

Mostly just nits; I'm assuming that the algorithm in the paper is correct, and I can't immediately see any issues with the logic here.

Thanks for the patch!

include/llvm/Transforms/Utils/MemorySSA.h

579

"since iplist's own if you don't change the traits" sounds weird to me

759

SmallPtrSet?

763

Can this just take a Def in the first place (same for the function below, except Use)

774

Was this a typo? If not, the AfterUs seems redundant unless it's from the paper you referenced or something.

lib/Transforms/Utils/MemorySSA.cpp

2414

Nit: Since we're doing nothing but returning Result, can this be converted to returning early? (And below)

2415

else if (!VisitedBlocks.insert(BB))? (will be less sketchy if we swap to early returns)

2440

Useless braces

2455

Incomplete comment? (And below * 2)

2493

Naming nit: MemorySSAUpdater::getLastDefIn?

2577

"we generate figure out"?

2634

FixupList.append(InsertedPhis.end() - StartingPHISize, InsertedPhis.end());?

2668

if (auto *Defs = ...)

2673

"access, make"

unittests/Transforms/Utils/MemorySSA.cpp

278

Temporary (and below)?

[davide]

I spent a bit of time reviewing this (with particular attention to the marker algorithm) and I think it's correct. Minor comments inline, happy to see this in when George is happy with it.

include/llvm/Transforms/Utils/MemorySSA.h

755–756

This is just my personal preference, so ignore it if you don't like, but, what about moving the updater to its own separate file?

unittests/Transforms/Utils/MemorySSA.cpp

711

I assume this #if 0 will go away, right?

[• dberlin]

include/llvm/Transforms/Utils/MemorySSA.h

755–756

I'll do this as a followup (otherwise it's going to completely screw up the comments here :P)

lib/Transforms/Utils/MemorySSA.cpp

2493

I went back and forth on what to call this one.
It used to be named getLastDef or something, but it's really not.
It's the same as the previous two functions, except it starts at the end of the block instead of a memory access.

2634

thanks, that's the function i was looking for.

unittests/Transforms/Utils/MemorySSA.cpp

278

Yes, the followup will add the move function

[• dberlin]

• Implement MoveBefore.

[• dberlin]

• Add moveAfter, refactor to use moveTo internally

[george.burgess.iv]

Just a few nits. You can consider this a LGTM-with-nits if the concern I raised isn't actually an issue.

include/llvm/Transforms/Utils/MemorySSA.h

770

nit: "just call moveBefore or moveAfter with"

lib/Transforms/Utils/MemorySSA.cpp

2729

Please remove parens

2733

Please remove parens

2733

I'm not super familiar with how BB Instruction ordering actually works, so this could totally be a misunderstanding on my part, but I think this might cause issues with operand dominance. Consider:

define void @foo() {
entry:
  ; 1 = MemoryDef
  %a = call i8* @bar()
  %b = bitcast i8* %a to i32*
  br i1 undef label %lbb, label %lbc

lbb:
  ; MemoryUse(1)
  %c = load i32, i32* %b
  br label %lbc

lbc:
  ret void
}

updater.moveAfter(Use1, Def1) will make %c dominate %b, since we call TheLoad.moveBefore(EntryBlock, ++TheStore), and ++TheStore == TheBitcast.

Same comment for blocks that only have MemoryPhis, as well.

2736

Coming into this with no updater-related context outside of this patch, it's mildly surprising to me that MemorySSA's updater moves actual Instructions around in BBs. It makes sense, but can we call that we do this out in the comments, please?

2761

Please remove the extra parens

[davide]

include/llvm/Transforms/Utils/MemorySSA.h

755–756

Yeah, feel free to do that in a follow up =)

[• dberlin]

lib/Transforms/Utils/MemorySSA.cpp

2733

Yes, You are correct. It is possible to use moveBefore to generate illegal blocks if you are not careful.
The same is true of basicblock's movebefore.

Essentially, we do what we are told. If you tell us "put this after this def", we put it *right after this def*.

I could change it to also take a basicblock iterator if you are worried we need one.

2736

We could make it not do that rather than take an iterator above?
Then the user is responsible for ordering it relative to the def.

[• dberlin]

lib/Transforms/Utils/MemorySSA.cpp

2736

i'm definitely going to do this because it simplifies life considerably.

include/llvm/Transforms/Utils/MemorySSA.h

 // definitions, which would require multiple phis, and multiple memoryaccesses
 // per instruction.
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_MEMORYSSA_H
 #define LLVM_TRANSFORMS_UTILS_MEMORYSSA_H
 
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/ilist.h"
 #include "llvm/ADT/ilist_node.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/AliasAnalysis.h"

 namespace llvm {
 
 class Function;
 class Instruction;
 class MemoryAccess;
 class LLVMContext;
 class raw_ostream;
 namespace MSSAHelpers {
-
 struct AllAccessTag {};
 struct DefsOnlyTag {};
 }
 
 enum {
   // Used to signify what the default invalid ID is for MemoryAccess's
   // getID()
   INVALID_MEMORYACCESS_ID = 0

 
 protected:
   friend class MemorySSA;
   friend class MemoryUseOrDef;
   friend class MemoryUse;
   friend class MemoryDef;
   friend class MemoryPhi;
 
+  /// \brief Used by MemorySSA to change the block of a MemoryAccess when it is
+  /// moved.
+  void setBlock(BasicBlock *BB) { Block = BB; }
+
   /// \brief Used for debugging and tracking things about MemoryAccesses.
   /// Guaranteed unique among MemoryAccesses, no guarantees otherwise.
   virtual unsigned getID() const = 0;
 
   MemoryAccess(LLVMContext &C, unsigned Vty, BasicBlock *BB,
                unsigned NumOperands)
       : User(Type::getVoidTy(C), Vty, nullptr, NumOperands), Block(BB) {}
 
public:
 
   static inline bool classof(const MemoryUseOrDef *) { return true; }
   static inline bool classof(const Value *MA) {
     return MA->getValueID() == MemoryUseVal || MA->getValueID() == MemoryDefVal;
   }
 
 protected:
   friend class MemorySSA;
-
+  friend class MemorySSAUpdater;
   MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty,
                  Instruction *MI, BasicBlock *BB)
       : MemoryAccess(C, Vty, BB, 1), MemoryInst(MI) {
     setDefiningAccess(DMA);
   }
 
   void setDefiningAccess(MemoryAccess *DMA) { setOperand(0, DMA); }
 
public:
   }
 
   inline MemoryAccess *getLiveOnEntryDef() const {
     return LiveOnEntryDef.get();
   }
 
   // Sadly, iplists, by default, owns and deletes pointers added to the
   // list. It's not currently possible to have two iplists for the same type,
   // where one owns the pointers, and one does not. This is because the traits
   // are per-type, not per-tag.  If this ever changes, we should make the
   // DefList an iplist.
   using AccessList = iplist<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>;
   using DefsList =
       simple_ilist<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>;
 
   /// \brief Return the list of MemoryAccess's for a given basic block.
   ///
MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition,
                                        InsertionPlace Point);
 
   /// \brief Create a MemoryAccess in MemorySSA before or after an existing
   /// MemoryAccess.
   ///
   /// Returns the new MemoryAccess.
   /// This should be called when a memory instruction is created that is being
   /// used to replace an existing memory instruction. It will *not* create PHI
-  /// nodes, or verify the clobbering definition.  The clobbering definition
-  /// must be non-null.
+  /// nodes, or verify the clobbering definition.
+  ///
   /// Note: If a MemoryAccess already exists for I, this function will make it
   /// inaccessible and it *must* have removeMemoryAccess called on it.
   MemoryUseOrDef *createMemoryAccessBefore(Instruction *I,
                                            MemoryAccess *Definition,
                                            MemoryUseOrDef *InsertPt);
   MemoryUseOrDef *createMemoryAccessAfter(Instruction *I,
                                           MemoryAccess *Definition,
                                           MemoryAccess *InsertPt);
 
-  // \brief Splice \p What to just before \p Where.
-  //
-  // In order to be efficient, the following conditions must be met:
-  //   - \p Where  dominates \p What,
-  //   - All memory accesses in [\p Where, \p What) are no-alias with \p What.
-  //
-  // TODO: relax the MemoryDef requirement on Where.
-  void spliceMemoryAccessAbove(MemoryDef *Where, MemoryUseOrDef *What);
-
   /// \brief Remove a MemoryAccess from MemorySSA, including updating all
   /// definitions and uses.
   /// This should be called when a memory instruction that has a MemoryAccess
   /// associated with it is erased from the program.  For example, if a store or
   /// load is simply erased (not replaced), removeMemoryAccess should be called
   /// on the MemoryAccess for that store/load.
   void removeMemoryAccess(MemoryAccess *);
 
public:
   /// \brief Verify that MemorySSA is self consistent (IE definitions dominate
   /// all uses, uses appear in the right places).  This is used by unit tests.
   void verifyMemorySSA() const;
 
 protected:
   // Used by Memory SSA annotater, dumpers, and wrapper pass
   friend class MemorySSAAnnotatedWriter;
   friend class MemorySSAPrinterLegacyPass;
+  friend class MemorySSAUpdater;
 
   void verifyDefUses(Function &F) const;
   void verifyDomination(Function &F) const;
   void verifyOrdering(Function &F) const;
 
   // This is used by the use optimizer and updater.
   AccessList *getWritableBlockAccesses(const BasicBlock *BB) const {
     auto It = PerBlockAccesses.find(BB);
     return It == PerBlockAccesses.end() ? nullptr : It->second.get();
   }
 
   // This is used by the use optimizer and updater.
   DefsList *getWritableBlockDefs(const BasicBlock *BB) const {
     auto It = PerBlockDefs.find(BB);
     return It == PerBlockDefs.end() ? nullptr : It->second.get();
   }
 
+  // This is used by the updater to perform the internal memoryssa machinations
+  // for moves.  It does not always leave the IR in a correct state, and relies
+  // on the updater to fixup what it breaks, so it is not public.
+  void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where);
+
 private:
   class CachingWalker;
   class OptimizeUses;
 
   CachingWalker *getWalkerImpl();
   void buildMemorySSA();
   void optimizeUses();
 
   void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
   using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>;
   using DefsMap = DenseMap<const BasicBlock *, std::unique_ptr<DefsList>>;
 
   void
   determineInsertionPoint(const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks);
   void computeDomLevels(DenseMap<DomTreeNode *, unsigned> &DomLevels);
   void markUnreachableAsLiveOnEntry(BasicBlock *BB);
   bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const;
   MemoryUseOrDef *createNewAccess(Instruction *);
   MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *);
   MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace);
   void removeFromLookups(MemoryAccess *);
+  void removeFromLists(MemoryAccess *, bool ShouldDelete = true);
 
   void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &,
                      const DenseMap<const BasicBlock *, unsigned int> &);
   MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *);
   void renamePass(DomTreeNode *, MemoryAccess *IncomingVal,
                   SmallPtrSet<BasicBlock *, 16> &Visited);
   AccessList *getOrCreateAccessList(const BasicBlock *);
   DefsList *getOrCreateDefsList(const BasicBlock *);
private:
   mutable SmallPtrSet<const BasicBlock *, 16> BlockNumberingValid;
   mutable DenseMap<const MemoryAccess *, unsigned long> BlockNumbering;
 
   // Memory SSA building info
   std::unique_ptr<CachingWalker> Walker;
   unsigned NextID;
 };
 
+// An automatic updater for MemorySSA that handles arbitrary insertion,
+// deletion, and moves.  It performs phi insertion where necessary, and
+// automatically updates the MemorySSA IR to be correct.
+// While updating loads or removing instructions is often easy enough to not
+// need this, updating stores should generally not be attemped outside this
+// API.
+//
+// Basic API usage:
+// Create the memory access you want for the instruction (this is mainly so
+// we know where it is, without having to duplicate the entire set of create
+// functions MemorySSA supports).
+// Call insertDef or insertUse depending on whether it's a MemoryUse or a
+// MemoryDef.
+// That's it.
+//
+// For moving, just call moveBefore with the right arguments.
+//
+class MemorySSAUpdater {
+private:
+  MemorySSA *MSSA;
+  SmallVector<MemoryPhi *, 8> InsertedPHIs;
+  SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
+
+public:
+  MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
+  void insertDef(MemoryDef *Def);
+  void insertUse(MemoryUse *Use);
+  void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
+  void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where);
+
+private:
+  void moveTo(MemoryUseOrDef *What, BasicBlock *BB,
+              MemorySSA::AccessList::iterator Where);
+  MemoryAccess *getPreviousDef(MemoryAccess *);
+  MemoryAccess *getPreviousDefInBlock(MemoryAccess *);
+  MemoryAccess *getPreviousDefFromEnd(BasicBlock *);
+  MemoryAccess *getPreviousDefRecursive(BasicBlock *);
+  MemoryAccess *recursePhi(MemoryAccess *Phi);
+  template <class RangeType>
+  MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
+  void fixupDefs(const SmallVectorImpl<MemoryAccess *> &);
+};
+
 // This pass does eager building and then printing of MemorySSA. It is used by
 // the tests to be able to build, dump, and verify Memory SSA.
 class MemorySSAPrinterLegacyPass : public FunctionPass {
 public:
   MemorySSAPrinterLegacyPass();
 
   bool runOnFunction(Function &) override;
   void getAnalysisUsage(AnalysisUsage &AU) const override;

lib/Transforms/Utils/MemorySSA.cpp

if (WasEnd) {
       if (InsertPt == Accesses->end())
         Defs->push_back(*What);
       else
         Defs->insert(InsertPt->getDefsIterator(), *What);
     }
   }
 }
 
+// Move What before Where in the IR.  The end result is taht What will belong to
+// the right lists and have the right Block set, but will not otherwise be
+// correct. It will not have the right defining access, and if it is a def,
+// things below it will not properly be updated.
+void MemorySSA::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
+                       AccessList::iterator Where) {
+  // Keep it in the lookup tables, remove from the lists
+  removeFromLists(What, false);
+  What->setBlock(BB);
+  insertIntoListsBefore(What, BB, Where);
+}
+
 MemoryPhi *MemorySSA::createMemoryPhi(BasicBlock *BB) {
   assert(!getMemoryAccess(BB) && "MemoryPhi already exists for this BB");
   MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++);
   insertIntoListsForBlock(Phi, BB, Beginning);
   ValueToMemoryAccess[BB] = Phi;
   // Phi's always are placed at the front of the block.
   BlockNumberingValid.erase(BB);
   return Phi;
assert(I->getParent() == InsertPt->getBlock() &&
          "New and old access must be in the same block");
   MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition);
   BlockNumberingValid.erase(InsertPt->getBlock());
   insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
                         ++(InsertPt->getIterator()));
   return NewAccess;
 }
 
-void MemorySSA::spliceMemoryAccessAbove(MemoryDef *Where,
-                                        MemoryUseOrDef *What) {
-  assert(What != getLiveOnEntryDef() && Where != getLiveOnEntryDef() &&
-         "Can't splice (above) LOE.");
-  assert(dominates(Where, What) && "Only upwards splices are permitted.");
-
-  if (Where == What)
-    return;
-  if (isa<MemoryDef>(What)) {
-    // TODO: possibly use removeMemoryAccess' more efficient RAUW
-    What->replaceAllUsesWith(What->getDefiningAccess());
-    What->setDefiningAccess(Where->getDefiningAccess());
-    Where->setDefiningAccess(What);
-  }
-  AccessList *Src = getWritableBlockAccesses(What->getBlock());
-  AccessList *Dest = getWritableBlockAccesses(Where->getBlock());
-  Dest->splice(AccessList::iterator(Where), *Src, What);
-
-  BlockNumberingValid.erase(What->getBlock());
-  if (What->getBlock() != Where->getBlock())
-    BlockNumberingValid.erase(Where->getBlock());
-}
-
 /// \brief Helper function to create new memory accesses
 MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I) {
   // The assume intrinsic has a control dependency which we model by claiming
   // that it writes arbitrarily. Ignore that fake memory dependency here.
   // FIXME: Replace this special casing with a more accurate modelling of
   // assume's control dependency.
   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
     if (II->getIntrinsicID() == Intrinsic::assume)
if (!MA)
       MA = cast<MemoryAccess>(Arg);
     else if (MA != Arg)
       return nullptr;
   }
   return MA;
 }
 
 /// \brief Properly remove \p MA from all of MemorySSA's lookup tables.
-///
-/// Because of the way the intrusive list and use lists work, it is important to
-/// do removal in the right order.
 void MemorySSA::removeFromLookups(MemoryAccess *MA) {
   assert(MA->use_empty() &&
          "Trying to remove memory access that still has uses");
   BlockNumbering.erase(MA);
   if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(MA))
     MUD->setDefiningAccess(nullptr);
   // Invalidate our walker's cache if necessary
   if (!isa<MemoryUse>(MA))
     Walker->invalidateInfo(MA);
   // The call below to erase will destroy MA, so we can't change the order we
   // are doing things here
   Value *MemoryInst;
   if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
     MemoryInst = MUD->getMemoryInst();
   } else {
     MemoryInst = MA->getBlock();
   }
   auto VMA = ValueToMemoryAccess.find(MemoryInst);
   if (VMA->second == MA)
     ValueToMemoryAccess.erase(VMA);
+}
 
+/// \brief Properly remove \p MA from all of MemorySSA's lists.
+///
+/// Because of the way the intrusive list and use lists work, it is important to
+/// do removal in the right order.
+/// ShouldDelete defaults to true, and will cause the memory access to also be
+/// deleted, not just removed.
+void MemorySSA::removeFromLists(MemoryAccess *MA, bool ShouldDelete) {
   // The access list owns the reference, so we erase it from the non-owning list
   // first.
   if (!isa<MemoryUse>(MA)) {
     auto DefsIt = PerBlockDefs.find(MA->getBlock());
     std::unique_ptr<DefsList> &Defs = DefsIt->second;
     Defs->remove(*MA);
     if (Defs->empty())
       PerBlockDefs.erase(DefsIt);
   }
 
+  // The erase call here will delete it. If we don't want it deleted, we call
+  // remove instead.
   auto AccessIt = PerBlockAccesses.find(MA->getBlock());
   std::unique_ptr<AccessList> &Accesses = AccessIt->second;
+  if (ShouldDelete)
     Accesses->erase(MA);
+  else
+    Accesses->remove(MA);
+
   if (Accesses->empty())
     PerBlockAccesses.erase(AccessIt);
 }
 
 void MemorySSA::removeMemoryAccess(MemoryAccess *MA) {
   assert(!isLiveOnEntryDef(MA) && "Trying to remove the live on entry def");
   // We can only delete phi nodes if they have no uses, or we can replace all
   // uses with a single definition.
   MemoryAccess *NewDefTarget = nullptr;
   if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
     // Note that it is sufficient to know that all edges of the phi node have
     // the same argument.  If they do, by the definition of dominance frontiers
     // (which we used to place this phi), that argument must dominate this phi,
     // and thus, must dominate the phi's uses, and so we will not hit the assert
     // below.
     NewDefTarget = onlySingleValue(MP);
     assert((NewDefTarget || MP->use_empty()) &&
            "We can't delete this memory phi");
   } else {
     NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
   }
 
   // Re-point the uses at our defining access
-  if (!MA->use_empty()) {
+  if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
     // Reset optimized on users of this store, and reset the uses.
     // A few notes:
     // 1. This is a slightly modified version of RAUW to avoid walking the
     // uses twice here.
     // 2. If we wanted to be complete, we would have to reset the optimized
     // flags on users of phi nodes if doing the below makes a phi node have all
     // the same arguments. Instead, we prefer users to removeMemoryAccess those
     // phi nodes, because doing it here would be N^3.
     if (MA->hasValueHandle())
       ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);
     // Note: We assume MemorySSA is not used in metadata since it's not really
     // part of the IR.
 
     while (!MA->use_empty()) {
       Use &U = *MA->use_begin();
       if (MemoryUse *MU = dyn_cast<MemoryUse>(U.getUser()))
         MU->resetOptimized();
       U.set(NewDefTarget);
     }
   }
 
   // The call below to erase will destroy MA, so we can't change the order we
   // are doing things here
   removeFromLookups(MA);
+  removeFromLists(MA);
 }
 
 void MemorySSA::print(raw_ostream &OS) const {
   MemorySSAAnnotatedWriter Writer(this);
   F.print(OS, &Writer);
 }
 
 void MemorySSA::dump() const {

 }
 
 MemoryAccess *DoNothingMemorySSAWalker::getClobberingMemoryAccess(
     MemoryAccess *StartingAccess, const MemoryLocation &) {
   if (auto *Use = dyn_cast<MemoryUseOrDef>(StartingAccess))
     return Use->getDefiningAccess();
   return StartingAccess;
 }
+// This is the marker algorithm from "Simple and Efficient Construction of
+// Static Single Assignment Form"
+// The simple, non-marker algorithm places phi nodes at any join
+// Here, we place markers, and only place phi nodes if they end up necessary.
+// They are only necessary if they break a cycle (IE we recursively visit
+// ourselves again), or we discover, while getting the value of the operands,
+// that there are two or more definitions needing to be merged.
+// This still will leave non-minimal form in the case of irreducible control
+// flow, where phi nodes may be in cycles with themselves, but unnecessary.
+MemoryAccess *MemorySSAUpdater::getPreviousDefRecursive(BasicBlock *BB) {
+  // Single predecessor case, just recurse, we can only have one definition.
+  if (BasicBlock *Pred = BB->getSinglePredecessor()) {
+    return getPreviousDefFromEnd(Pred);
+  } else if (VisitedBlocks.count(BB)) {
+    // We hit our node again, meaning we had a cycle, we must insert a phi
+    // node to break it so we have an operand. The only case this will
+    // insert useless phis is if we have irreducible control flow.
+    return MSSA->createMemoryPhi(BB);
+  } else {
+    // Mark us visited so we can detect a cycle
+    VisitedBlocks.insert(BB);
+    SmallVector<MemoryAccess *, 8> PhiOps;
+
+    // Recurse to get the values in our predecessors for placement of a
+    // potential phi node. This will insert phi nodes if we cycle in order to
+    // break the cycle and have an operand.
+    for (auto *Pred : predecessors(BB))
+      PhiOps.push_back(getPreviousDefFromEnd(Pred));
+
+    // Now try to simplify the ops to avoid placing a phi.
+    // This may return null if we never created a phi yet, that's okay
+    MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MSSA->getMemoryAccess(BB));
+    bool PHIExistsButNeedsUpdate = false;
+    // See if the existing phi operands match what we need.
+    // Unlike normal SSA, we only allow one phi node per block, so we can't just
+    // create a new one.
+    if (Phi && Phi->getNumOperands() != 0)
+      if (!std::equal(Phi->op_begin(), Phi->op_end(), PhiOps.begin())) {
+        PHIExistsButNeedsUpdate = true;
+      }
+
+    // See if we can avoid the phi by simplifying it.
+    auto *Result = tryRemoveTrivialPhi(Phi, PhiOps);
+    // If we couldn't simplify, we may have to create a phi
+    if (Result == Phi) {
+      if (!Phi)
+        Phi = MSSA->createMemoryPhi(BB);
+
+      // These will have been filled in by the recursive read we did above.
+      if (PHIExistsButNeedsUpdate) {
+        std::copy(PhiOps.begin(), PhiOps.end(), Phi->op_begin());
+        std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin());
+      } else {
+        unsigned i = 0;
+        for (auto *Pred : predecessors(BB))
+          Phi->addIncoming(PhiOps[i++], Pred);
+      }
+
+      Result = Phi;
+    }
+    if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Result))
+      InsertedPHIs.push_back(MP);
+    // Set ourselves up for the next variable by resetting visited state.
+    VisitedBlocks.erase(BB);
+    return Result;
+  }
+  llvm_unreachable("Should have hit one of the three cases above");
+}
+
+// This starts at the memory access, and goes backwards in the block to find the
+// previous definition. If a definition is not found the block of the access,
+// it continues globally, creating phi nodes to ensure we have a single
+// definition.
+MemoryAccess *MemorySSAUpdater::getPreviousDef(MemoryAccess *MA) {
+  auto *LocalResult = getPreviousDefInBlock(MA);
+
+  return LocalResult ? LocalResult : getPreviousDefRecursive(MA->getBlock());
+}
+
+// This starts at the memory access, and goes backwards in the block to the find
+// the previous definition. If the definition is not found in the block of the
+// access, it returns nullptr.
+MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) {
+  auto *Defs = MSSA->getWritableBlockDefs(MA->getBlock());
+
+  // It's possible there are no defs, or we got handed the first def to start.
+  if (Defs) {
+    // If this is a def, we can just use the def iterators.
+    if (!isa<MemoryUse>(MA)) {
+      auto Iter = MA->getReverseDefsIterator();
+      ++Iter;
+      if (Iter != Defs->rend())
+        return &*Iter;
+    } else {
+      // Otherwise, have to walk the all access iterator.
+      auto Iter = MA->getReverseIterator();
+      ++Iter;
+      while (&*Iter != &*Defs->begin()) {
+        if (!isa<MemoryUse>(*Iter))
+          return &*Iter;
+        --Iter;
+      }
+      // At this point it must be pointing at firstdef
+      assert(&*Iter == &*Defs->begin() &&
+             "Should have hit first def walking backwards");
+      return &*Iter;
+    }
+  }
+  return nullptr;
+}
+
+// This starts at the end of block
+MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(BasicBlock *BB) {
+  auto *Defs = MSSA->getWritableBlockDefs(BB);
+
+  if (Defs)
+    return &*Defs->rbegin();
+
+  return getPreviousDefRecursive(BB);
+}
+// Recurse over a set of phi uses to eliminate the trivial ones
+MemoryAccess *MemorySSAUpdater::recursePhi(MemoryAccess *Phi) {
+  if (!Phi)
+    return nullptr;
+  TrackingVH<MemoryAccess> Res(Phi);
+  SmallVector<TrackingVH<Value>, 8> Uses;
+  std::copy(Phi->user_begin(), Phi->user_end(), std::back_inserter(Uses));
+  for (auto &U : Uses) {
+    if (MemoryPhi *UsePhi = dyn_cast<MemoryPhi>(&*U)) {
+      auto OperRange = UsePhi->operands();
+      tryRemoveTrivialPhi(UsePhi, OperRange);
+    }
+  }
+  return Res;
+}
+
+// Eliminate trivial phis
+// Phis are trivial if they are defined either by themselves, or all the same
+// argument.
+// IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c)
+// We recursively try to remove them.
+template <class RangeType>
+MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
+                                                    RangeType &Operands) {
+  // Detect equal or self arguments
+  MemoryAccess *Same = nullptr;
+  for (auto &Op : Operands) {
+    // If the same or self, good so far
+    if (Op == Phi || Op == Same)
+      continue;
+    // not the same, return the phi since it's not eliminatable by us
+    if (Same)
+      return Phi;
+    Same = cast<MemoryAccess>(Op);
+  }
+  // Never found a non-self reference, the phi is undef
+  if (Same == nullptr)
+    return MSSA->getLiveOnEntryDef();
+  if (Phi) {
+    Phi->replaceAllUsesWith(Same);
+    MSSA->removeMemoryAccess(Phi);
+  }
+
+  // We should only end up recursing in case we replaced something, in which
+  // case, we may have made other Phis trivial.
+  return recursePhi(Same);
+}
+
+void MemorySSAUpdater::insertUse(MemoryUse *MU) {
+  InsertedPHIs.clear();
+  MU->setDefiningAccess(getPreviousDef(MU));
+  // Unlike for defs, there is no extra work to do.  Because uses do not create
+  // new may-defs, there are only two cases:
+  //
+  // 1. There was a def already below us, and therefore, we should not have
+  // created a phi node because it was already needed for the def.
+  //
+  // 2. There is no def below us, and therefore, there is no extra renaming work
+  // to do.
+}
+
+void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB,
+                               MemoryAccess *NewDef) {
+  // Replace any operand with us an incoming block with the new defining
+  // access.
+  int i = MP->getBasicBlockIndex(BB);
+  assert(i != -1 && "Should have found the basic block in the phi");
+  while (MP->getIncomingBlock(i) == BB) {
+    // Unlike above, there is already a phi node here, so we only need
+    // to set the right value.
+    MP->setIncomingValue(i, NewDef);
+    ++i;
+  }
+}
+
+// A brief description of the algorithm:
+// First, we compute what should define the new def, using the SSA
+// construction algorithm.
+// Then, we update the defs below us (and any new phi nodes) in the graph to
+// point to the correct new defs, to ensure we only have one variable, and no
+// disconnected stores.
+void MemorySSAUpdater::insertDef(MemoryDef *MD) {
+  InsertedPHIs.clear();
+
+  // See if we had a local def, and if not, go hunting.
+  MemoryAccess *DefBefore = getPreviousDefInBlock(MD);
+  bool DefBeforeSameBlock = DefBefore != nullptr;
+  if (!DefBefore)
+    DefBefore = getPreviousDefRecursive(MD->getBlock());
+
+  // There is a def before us, which means we can replace any store/phi uses
+  // of that thing with us, since we are in the way of whatever was there
+  // before.
+  // We now define that def's memorydefs and memoryphis
+  for (auto UI = DefBefore->use_begin(), UE = DefBefore->use_end(); UI != UE;) {
+    Use &U = *UI++;
+    // Leave the uses alone
+    if (isa<MemoryUse>(U.getUser()))
+      continue;
+    U.set(MD);
+  }
+  // and that def is now our defining access.
+  // We change them in this order otherwise we will appear in the use list
+  // above and reset ourselves.
+  MD->setDefiningAccess(DefBefore);
+
+  SmallVector<MemoryAccess *, 8> FixupList(InsertedPHIs.begin(),
+                                           InsertedPHIs.end());
+  if (!DefBeforeSameBlock) {
+    // If there was a local def before us, we must have the same effect it
+    // did. Because every may-def is the same, any phis/etc we would create, it
+    // would also have created.  If there was no local def before us, we
+    // performed a global update, and have to search all successors and make
+    // sure we update the first def in each of them (following all paths until
+    // we hit the first def along each path). This may also insert phi nodes.
+    // TODO: There are other cases we can skip this work, such as when we have a
+    // single successor, and only used a straight line of single pred blocks
+    // backwards to find the def.  To make that work, we'd have to track whether
+    // getDefRecursive only ever used the single predecessor case.  These types
+    // of paths also only exist in between CFG simplifications.
+    FixupList.push_back(MD);
+  }
+
+  while (!FixupList.empty()) {
+    unsigned StartingPHISize = InsertedPHIs.size();
+    fixupDefs(FixupList);
+    FixupList.clear();
+    // Put any new phis on the fixup list, and process them
+    FixupList.append(InsertedPHIs.end() - StartingPHISize, InsertedPHIs.end());
+  }
+}
+
+void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<MemoryAccess *> &Vars) {
+  SmallPtrSet<const BasicBlock *, 8> Seen;
+  SmallVector<const BasicBlock *, 16> Worklist;
+  for (auto *NewDef : Vars) {
+    // First, see if there is a local def after the operand.
+    auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock());
+    auto DefIter = NewDef->getDefsIterator();
+
+    // If there is a local def after us, we only have to rename that.
+    if (++DefIter != Defs->end()) {
+      cast<MemoryDef>(DefIter)->setDefiningAccess(NewDef);
+      continue;
+    }
+
+    // Otherwise, we need to search down through the CFG.
+    // For each of our successors, handle it directly if their is a phi, or
+    // place on the fixup worklist.
+    for (const auto *S : successors(NewDef->getBlock())) {
+      if (auto *MP = MSSA->getMemoryAccess(S))
+        setMemoryPhiValueForBlock(MP, NewDef->getBlock(), NewDef);
+      else
+        Worklist.push_back(S);
+    }
+
+    while (!Worklist.empty()) {
+      const BasicBlock *FixupBlock = Worklist.back();
+      Worklist.pop_back();
+
+      // Get the first def in the block that isn't a phi node.
+      if (auto *Defs = MSSA->getWritableBlockDefs(FixupBlock)) {
+        auto *FirstDef = &*Defs->begin();
+        // The loop above and below should have taken care of phi nodes
+        assert(!isa<MemoryPhi>(FirstDef) &&
+               "Should have already handled phi nodes!");
+        // We are now this def's defining access, make sure we actually dominate
+        // it
+        assert(MSSA->dominates(NewDef, FirstDef) &&
+               "Should have dominated the new access");
+
+        // This may insert new phi nodes, because we are not guaranteed the
+        // block we are processing has a single pred, and depending where the
+        // store was inserted, it may require phi nodes below it.
+        cast<MemoryDef>(FirstDef)->setDefiningAccess(getPreviousDef(FirstDef));
+        return;
+      }
+      // We didn't find a def, so we must continue.
+      for (const auto *S : successors(FixupBlock)) {
+        // If there is a phi node, handle it.
+        // Otherwise, put the block on the worklist
+        if (auto *MP = MSSA->getMemoryAccess(S))
+          setMemoryPhiValueForBlock(MP, FixupBlock, NewDef);
+        else {
+          // If we cycle, we should have ended up at a phi node that we already
+          // processed.  FIXME: Double check this
+          if (!Seen.insert(S).second)
+            continue;
+          Worklist.push_back(S);
+        }
+      }
+    }
+  }
+}
+
+// Move What before Where in the MemorySSA IR.
+void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
+                              MemorySSA::AccessList::iterator Where) {
+  // Replace all our users with our defining access.
+  What->replaceAllUsesWith(What->getDefiningAccess());
+  // Now literally move the instruction
+  auto *Accesses = MSSA->getBlockAccesses(BB);
+  // It's complicated if Where doesn't point to a real instruction. If it's the
+  // end of the access list, we need to figure out what the end of the access
+  // list in terms of real instructions, and place it there.  If the end of the
+  // access list is a phi node, we place it after the phis in the associated
+  // block.
+  if (Where == Accesses->end()) {
+    // Get the last memory access
+    const MemoryAccess *Last = &*(Accesses->rbegin());
+    BasicBlock::iterator BBPlace;
+    // We are guaranteed there is at least something in the block.
+    if (auto *MUD = dyn_cast<MemoryUseOrDef>(Last))
+      BBPlace = ++(MUD->getMemoryInst()->getIterator());
+    else
+      BBPlace = BB->getFirstNonPHI()->getIterator();
+    What->getMemoryInst()->moveBefore(*BB, BBPlace);
+  } else {
+    What->getMemoryInst()->moveBefore(
+        cast<MemoryUseOrDef>(Where)->getMemoryInst());
+  }
+  // We move the instruction first, otherwise the above has to take into account
+  // that the instruction is already on the access list for the block it's
+  // moving to.
+
+  // Now let MemorySSA take care of moving it around in the lists.
+  MSSA->moveTo(What, BB, Where);
+
+  // Now reinsert it into the IR and do whatever fixups needed.
+  if (auto *MD = dyn_cast<MemoryDef>(What))
+    insertDef(MD);
+  else
+    insertUse(cast<MemoryUse>(What));
+}
+// Move What before Where in the MemorySSA IR.
+void MemorySSAUpdater::moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
+  moveTo(What, Where->getBlock(), Where->getIterator());
+}
+
+// Move What after Where in the MemorySSA IR.
+void MemorySSAUpdater::moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
+  moveTo(What, Where->getBlock(), ++(Where->getIterator()));
+}
+
 } // namespace llvm

unittests/Transforms/Utils/MemorySSA.cpp

TEST_F(MemorySSATest, CreateALoad) {
 
   // Create the load memory acccess
   MemoryUse *LoadAccess = cast<MemoryUse>(
       MSSA.createMemoryAccessInBB(LoadInst, MP, Merge, MemorySSA::Beginning));
   MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
   EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
   MSSA.verifyMemorySSA();
 }
+TEST_F(MemorySSATest, CreateLoadsAndStoreUpdater) {
+  // We create a diamond, then build memoryssa with no memory accesses, and
+  // incrementally update it by inserting a store in the, entry, a load in the
+  // merge point, then a store in the branch, another load in the merge point,
+  // and then a store in the entry.
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+  BasicBlock *Entry(BasicBlock::Create(C, "", F));
+  BasicBlock *Left(BasicBlock::Create(C, "", F));
+  BasicBlock *Right(BasicBlock::Create(C, "", F));
+  BasicBlock *Merge(BasicBlock::Create(C, "", F));
+  B.SetInsertPoint(Entry);
+  B.CreateCondBr(B.getTrue(), Left, Right);
+  B.SetInsertPoint(Left, Left->begin());
+  Argument *PointerArg = &*F->arg_begin();
+  B.SetInsertPoint(Left);
+  B.CreateBr(Merge);
+  B.SetInsertPoint(Right);
+  B.CreateBr(Merge);
+
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAUpdater Updater(&MSSA);
+  // Add the store
+  B.SetInsertPoint(Entry, Entry->begin());
+  StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
+  MemoryAccess *EntryStoreAccess = MSSA.createMemoryAccessInBB(
+      EntryStore, nullptr, Entry, MemorySSA::Beginning);
+  Updater.insertDef(cast<MemoryDef>(EntryStoreAccess));
+
+  // Add the load
+  B.SetInsertPoint(Merge, Merge->begin());
+  LoadInst *FirstLoad = B.CreateLoad(PointerArg);
+
+  // MemoryPHI should not already exist.
+  MemoryPhi *MP = MSSA.getMemoryAccess(Merge);
+  EXPECT_EQ(MP, nullptr);
+
+  // Create the load memory access
+  MemoryUse *FirstLoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
+      FirstLoad, nullptr, Merge, MemorySSA::Beginning));
+  Updater.insertUse(FirstLoadAccess);
+  // Should just have a load using the entry access, because it should discover
+  // the phi is trivial
+  EXPECT_EQ(FirstLoadAccess->getDefiningAccess(), EntryStoreAccess);
+
+  // Create a store on the left
+  // Add the store
+  B.SetInsertPoint(Left, Left->begin());
+  StoreInst *LeftStore = B.CreateStore(B.getInt8(16), PointerArg);
+  MemoryAccess *LeftStoreAccess = MSSA.createMemoryAccessInBB(
+      LeftStore, nullptr, Left, MemorySSA::Beginning);
+  Updater.insertDef(cast<MemoryDef>(LeftStoreAccess));
+  // We don't touch existing loads, so we need to create a new one to get a phi
+  // Add the second load
+  B.SetInsertPoint(Merge, Merge->begin());
+  LoadInst *SecondLoad = B.CreateLoad(PointerArg);
+
+  // MemoryPHI should not already exist.
+  MP = MSSA.getMemoryAccess(Merge);
+  EXPECT_EQ(MP, nullptr);
+
+  // Create the load memory access
+  MemoryUse *SecondLoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
+      SecondLoad, nullptr, Merge, MemorySSA::Beginning));
+  Updater.insertUse(SecondLoadAccess);
+  // Now the load should be a phi of the entry store and the left store
+  MemoryPhi *MergePhi =
+      dyn_cast<MemoryPhi>(SecondLoadAccess->getDefiningAccess());
+  EXPECT_NE(MergePhi, nullptr);
+  EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess);
+  EXPECT_EQ(MergePhi->getIncomingValue(1), LeftStoreAccess);
+  // Now create a store below the existing one in the entry
+  B.SetInsertPoint(Entry, --Entry->end());
+  StoreInst *SecondEntryStore = B.CreateStore(B.getInt8(16), PointerArg);
+  MemoryAccess *SecondEntryStoreAccess = MSSA.createMemoryAccessInBB(
+      SecondEntryStore, nullptr, Entry, MemorySSA::End);
+  Updater.insertDef(cast<MemoryDef>(SecondEntryStoreAccess));
+  // and make sure the phi below it got updated, despite being blocks away
+  MergePhi = dyn_cast<MemoryPhi>(SecondLoadAccess->getDefiningAccess());
+  EXPECT_NE(MergePhi, nullptr);
+  EXPECT_EQ(MergePhi->getIncomingValue(0), SecondEntryStoreAccess);
+  EXPECT_EQ(MergePhi->getIncomingValue(1), LeftStoreAccess);
+  MSSA.verifyMemorySSA();
+}
+
+TEST_F(MemorySSATest, CreateALoadUpdater) {
+  // We create a diamond, then build memoryssa with no memory accesses, and
+  // incrementally update it by inserting a store in one of the branches, and a
+  // load in the merge point
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+  BasicBlock *Entry(BasicBlock::Create(C, "", F));
+  BasicBlock *Left(BasicBlock::Create(C, "", F));
+  BasicBlock *Right(BasicBlock::Create(C, "", F));
+  BasicBlock *Merge(BasicBlock::Create(C, "", F));
+  B.SetInsertPoint(Entry);
+  B.CreateCondBr(B.getTrue(), Left, Right);
+  B.SetInsertPoint(Left, Left->begin());
+  Argument *PointerArg = &*F->arg_begin();
+  B.SetInsertPoint(Left);
+  B.CreateBr(Merge);
+  B.SetInsertPoint(Right);
+  B.CreateBr(Merge);
+
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAUpdater Updater(&MSSA);
+  B.SetInsertPoint(Left, Left->begin());
+  // Add the store
+  StoreInst *SI = B.CreateStore(B.getInt8(16), PointerArg);
+  MemoryAccess *StoreAccess =
+      MSSA.createMemoryAccessInBB(SI, nullptr, Left, MemorySSA::Beginning);
+  Updater.insertDef(cast<MemoryDef>(StoreAccess));
+
+  // Add the load
+  B.SetInsertPoint(Merge, Merge->begin());
+  LoadInst *LoadInst = B.CreateLoad(PointerArg);
+
+  // MemoryPHI should not already exist.
+  MemoryPhi *MP = MSSA.getMemoryAccess(Merge);
+  EXPECT_EQ(MP, nullptr);
+
+  // Create the load memory acccess
+  MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
+      LoadInst, nullptr, Merge, MemorySSA::Beginning));
+  Updater.insertUse(LoadAccess);
+  MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
+  EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
+  MSSA.verifyMemorySSA();
+}
 
 TEST_F(MemorySSATest, MoveAStore) {
   // We create a diamond where there is a in the entry, a store on one side, and
   // a load at the end.  After building MemorySSA, we test updating by moving
-  // the store from the side block to the entry block.
+  // the store from the side block to the entry block. This destroys the old
+  // access.
   F = Function::Create(
       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
       GlobalValue::ExternalLinkage, "F", &M);
   BasicBlock *Entry(BasicBlock::Create(C, "", F));
   BasicBlock *Left(BasicBlock::Create(C, "", F));
   BasicBlock *Right(BasicBlock::Create(C, "", F));
   BasicBlock *Merge(BasicBlock::Create(C, "", F));
   B.SetInsertPoint(Entry);
TEST_F(MemorySSATest, MoveAStore) {
   MemoryAccess *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
   MemoryAccess *NewStoreAccess = MSSA.createMemoryAccessAfter(
       SideStore, EntryStoreAccess, EntryStoreAccess);
   EntryStoreAccess->replaceAllUsesWith(NewStoreAccess);
   MSSA.removeMemoryAccess(SideStoreAccess);
   MSSA.verifyMemorySSA();
 }
 
+TEST_F(MemorySSATest, MoveAStoreUpdater) {
+  // We create a diamond where there is a in the entry, a store on one side, and
+  // a load at the end.  After building MemorySSA, we test updating by moving
+  // the store from the side block to the entry block.  This destroys the old
+  // access.
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+  BasicBlock *Entry(BasicBlock::Create(C, "", F));
+  BasicBlock *Left(BasicBlock::Create(C, "", F));
+  BasicBlock *Right(BasicBlock::Create(C, "", F));
+  BasicBlock *Merge(BasicBlock::Create(C, "", F));
+  B.SetInsertPoint(Entry);
+  Argument *PointerArg = &*F->arg_begin();
+  StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
+  B.CreateCondBr(B.getTrue(), Left, Right);
+  B.SetInsertPoint(Left);
+  auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg);
+  BranchInst::Create(Merge, Left);
+  BranchInst::Create(Merge, Right);
+  B.SetInsertPoint(Merge);
+  auto *MergeLoad = B.CreateLoad(PointerArg);
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAUpdater Updater(&MSSA);
+
+  // Move the store
+  SideStore->moveBefore(Entry->getTerminator());
+  auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);
+  auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
+  auto *NewStoreAccess = MSSA.createMemoryAccessAfter(
+      SideStore, EntryStoreAccess, EntryStoreAccess);
+  // Before, the load will point to a phi of the EntryStore and SideStore.
+  auto *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(MergeLoad));
+  EXPECT_TRUE(isa<MemoryPhi>(LoadAccess->getDefiningAccess()));
+  MemoryPhi *MergePhi = cast<MemoryPhi>(LoadAccess->getDefiningAccess());
+  EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);
+  EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
+  MSSA.removeMemoryAccess(SideStoreAccess);
+  Updater.insertDef(cast<MemoryDef>(NewStoreAccess));
+  // After it's a phi of the new side store access.
+  EXPECT_EQ(MergePhi->getIncomingValue(0), NewStoreAccess);
+  EXPECT_EQ(MergePhi->getIncomingValue(1), NewStoreAccess);
+  MSSA.verifyMemorySSA();
+}
+
+TEST_F(MemorySSATest, MoveAStoreUpdaterMove) {
+  // We create a diamond where there is a in the entry, a store on one side, and
+  // a load at the end.  After building MemorySSA, we test updating by moving
+  // the store from the side block to the entry block.  This does not destroy
+  // the old access.
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+  BasicBlock *Entry(BasicBlock::Create(C, "", F));
+  BasicBlock *Left(BasicBlock::Create(C, "", F));
+  BasicBlock *Right(BasicBlock::Create(C, "", F));
+  BasicBlock *Merge(BasicBlock::Create(C, "", F));
+  B.SetInsertPoint(Entry);
+  Argument *PointerArg = &*F->arg_begin();
+  StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
+  B.CreateCondBr(B.getTrue(), Left, Right);
+  B.SetInsertPoint(Left);
+  auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg);
+  BranchInst::Create(Merge, Left);
+  BranchInst::Create(Merge, Right);
+  B.SetInsertPoint(Merge);
+  auto *MergeLoad = B.CreateLoad(PointerArg);
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAUpdater Updater(&MSSA);
+
+  // Move the store
+  auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);
+  auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
+  // Before, the load will point to a phi of the EntryStore and SideStore.
+  auto *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(MergeLoad));
+  EXPECT_TRUE(isa<MemoryPhi>(LoadAccess->getDefiningAccess()));
+  MemoryPhi *MergePhi = cast<MemoryPhi>(LoadAccess->getDefiningAccess());
+  EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);
+  EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
+  Updater.moveAfter(SideStoreAccess, EntryStoreAccess);
+  // After, it's a phi of the side store.
+  EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
+  EXPECT_EQ(MergePhi->getIncomingValue(1), SideStoreAccess);
+
+  MSSA.verifyMemorySSA();
+}
+
 TEST_F(MemorySSATest, RemoveAPhi) {
   // We create a diamond where there is a store on one side, and then a load
   // after the merge point.  This enables us to test a bunch of different
   // removal cases.
   F = Function::Create(
       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
       GlobalValue::ExternalLinkage, "F", &M);
   BasicBlock *Entry(BasicBlock::Create(C, "", F));
TEST_F(MemorySSATest, WalkerReopt) {
   // Create the load memory access pointing to an unoptimized place.
   MemoryUse *NewLoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
       LIA, MSSA.getMemoryAccess(SIB), LIA->getParent(), MemorySSA::End));
   // This should it cause it to be optimized
   EXPECT_EQ(Walker->getClobberingMemoryAccess(NewLoadAccess), LoadClobber);
   EXPECT_EQ(NewLoadAccess->getDefiningAccess(), LoadClobber);
 }
 
-#if 0
-// Test out MemorySSA::spliceMemoryAccessAbove.
-TEST_F(MemorySSATest, SpliceAboveMemoryDef) {
+// Test out MemorySSAUpdater::moveBefore
+TEST_F(MemorySSATest, MoveAboveMemoryDef) {
   F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
                        GlobalValue::ExternalLinkage, "F", &M);
   B.SetInsertPoint(BasicBlock::Create(C, "", F));
 
   Type *Int8 = Type::getInt8Ty(C);
   Value *A = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
   Value *B_ = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B");
   Value *C = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "C");
 
   StoreInst *StoreA0 = B.CreateStore(ConstantInt::get(Int8, 0), A);
   StoreInst *StoreB = B.CreateStore(ConstantInt::get(Int8, 0), B_);
   LoadInst *LoadB = B.CreateLoad(B_);
   StoreInst *StoreA1 = B.CreateStore(ConstantInt::get(Int8, 4), A);
-  // splice this above StoreB
   StoreInst *StoreC = B.CreateStore(ConstantInt::get(Int8, 4), C);
   StoreInst *StoreA2 = B.CreateStore(ConstantInt::get(Int8, 4), A);
   LoadInst *LoadC = B.CreateLoad(C);
 
   setupAnalyses();
   MemorySSA &MSSA = *Analyses->MSSA;
   MemorySSAWalker &Walker = *Analyses->Walker;
 
-  StoreC->moveBefore(StoreB);
-  MSSA.spliceMemoryAccessAbove(cast<MemoryDef>(MSSA.getMemoryAccess(StoreB)),
-                               MSSA.getMemoryAccess(StoreC));
+  MemorySSAUpdater Updater(&MSSA);
+  Updater.moveBefore(cast<MemoryDef>(MSSA.getMemoryAccess(StoreC)),
+                     cast<MemoryDef>(MSSA.getMemoryAccess(StoreB)));
 
   MSSA.verifyMemorySSA();
 
   EXPECT_EQ(MSSA.getMemoryAccess(StoreB)->getDefiningAccess(),
             MSSA.getMemoryAccess(StoreC));
   EXPECT_EQ(MSSA.getMemoryAccess(StoreC)->getDefiningAccess(),
             MSSA.getMemoryAccess(StoreA0));
   EXPECT_EQ(MSSA.getMemoryAccess(StoreA2)->getDefiningAccess(),
             MSSA.getMemoryAccess(StoreA1));
   EXPECT_EQ(Walker.getClobberingMemoryAccess(LoadB),
             MSSA.getMemoryAccess(StoreB));
   EXPECT_EQ(Walker.getClobberingMemoryAccess(LoadC),
             MSSA.getMemoryAccess(StoreC));
 
   // exercise block numbering
   EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreC),
                                     MSSA.getMemoryAccess(StoreB)));
   EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreA1),
                                     MSSA.getMemoryAccess(StoreA2)));
 }
-#endif
+
+TEST_F(MemorySSATest, Irreducible) {
+  // Create the equivalent of
+  // x = something
+  // if (...)
+  //    goto second_loop_entry
+  // while (...) {
+  // second_loop_entry:
+  // }
+  // use(x)
+
+  SmallVector<PHINode *, 8> Inserted;
+  IRBuilder<> B(C);
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+
+  // Make blocks
+  BasicBlock *IfBB = BasicBlock::Create(C, "if", F);
+  BasicBlock *LoopStartBB = BasicBlock::Create(C, "loopstart", F);
+  BasicBlock *LoopMainBB = BasicBlock::Create(C, "loopmain", F);
+  BasicBlock *AfterLoopBB = BasicBlock::Create(C, "afterloop", F);
+  B.SetInsertPoint(IfBB);
+  B.CreateCondBr(B.getTrue(), LoopMainBB, LoopStartBB);
+  B.SetInsertPoint(LoopStartBB);
+  B.CreateBr(LoopMainBB);
+  B.SetInsertPoint(LoopMainBB);
+  B.CreateCondBr(B.getTrue(), LoopStartBB, AfterLoopBB);
+  B.SetInsertPoint(AfterLoopBB);
+  Argument *FirstArg = &*F->arg_begin();
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAUpdater Updater(&MSSA);
+  // Create the load memory acccess
+  LoadInst *LoadInst = B.CreateLoad(FirstArg);
+  MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
+      LoadInst, nullptr, AfterLoopBB, MemorySSA::Beginning));
+  Updater.insertUse(LoadAccess);
+  MSSA.verifyMemorySSA();
+}