Index: lib/Transforms/Scalar/GVNHoist.cpp
===================================================================
--- lib/Transforms/Scalar/GVNHoist.cpp
+++ lib/Transforms/Scalar/GVNHoist.cpp
@@ -193,14 +193,11 @@
     VN.setAliasAnalysis(AA);
     VN.setMemDep(MD);
     bool Res = false;
+    MemorySSA M(F, AA, DT);
+    MSSA = &M;
 
     // FIXME: use lazy evaluation of VN to avoid the fix-point computation.
     while (1) {
-      // FIXME: only compute MemorySSA once. We need to update the analysis in
-      // the same time as transforming the code.
-      MemorySSA M(F, AA, DT);
-      MSSA = &M;
-
       // Perform DFS Numbering of instructions.
       unsigned I = 0;
       for (const BasicBlock *BB : depth_first(&F.getEntryBlock()))
@@ -208,15 +205,15 @@
           DFSNumber.insert({&Inst, ++I});
 
       auto HoistStat = hoistExpressions(F);
-      if (HoistStat.first + HoistStat.second == 0) {
+      if (HoistStat.first + HoistStat.second == 0)
         return Res;
-      }
-      if (HoistStat.second > 0) {
+
+      if (HoistStat.second > 0)
         // To address a limitation of the current GVN, we need to rerun the
-        // hoisting after we hoisted loads in order to be able to hoist all
-        // scalars dependent on the hoisted loads. Same for stores.
+        // hoisting after we hoisted loads or stores in order to be able to
+        // hoist all scalars dependent on the hoisted ld/st.
         VN.clear();
-      }
+
       Res = true;
 
       // DFS numbers change when instructions are hoisted: clear and recompute.
@@ -310,7 +307,8 @@
 
     for (User *U : Def->users())
       if (auto *MU = dyn_cast<MemoryUse>(U)) {
-        BasicBlock *UBB = MU->getBlock();
+        // FIXME: MU->getBlock() does not get updated when we move the instruction.
+        BasicBlock *UBB = MU->getMemoryInst()->getParent();
         // Only analyze uses in BB.
         if (BB != UBB)
           continue;
@@ -725,6 +723,8 @@
           if (!Repl || firstInBB(I, Repl))
             Repl = I;
 
+      MemoryAccess *NewMemAcc = nullptr;
+
       if (Repl) {
         // Repl is already in HoistPt: it remains in place.
         assert(allOperandsAvailable(Repl, HoistPt) &&
@@ -742,7 +742,23 @@
             !makeGepOperandsAvailable(Repl, HoistPt, InstructionsToHoist))
           continue;
 
+        // Before moving the instruction, get its MSSA access.
+        MemoryUseOrDef *OldMemAcc = nullptr;
+        if (MemoryAccess *MA = MSSA->getMemoryAccess(Repl))
+          OldMemAcc = dyn_cast<MemoryUseOrDef>(MA);
+
+        // Move the instruction at the end of HoistPt.
         Repl->moveBefore(HoistPt->getTerminator());
+
+        if (OldMemAcc) {
+          // The definition of this ld/st will not change: ld/st hoisting is
+          // legal when the ld/st is not moved past its current definition.
+          MemoryAccess *Def = OldMemAcc->getDefiningAccess();
+          NewMemAcc = MSSA->createMemoryAccessInBB(Repl, Def, HoistPt,
+                                                   MemorySSA::End);
+          OldMemAcc->replaceAllUsesWith(NewMemAcc);
+          MSSA->removeMemoryAccess(OldMemAcc);
+        }
       }
 
       if (isa<LoadInst>(Repl))
@@ -775,6 +791,14 @@
           } else if (isa<CallInst>(Repl)) {
             ++NumCallsRemoved;
           }
+
+          if (NewMemAcc) {
+            // Update the uses of the old MSSA access with NewMemAcc.
+            MemoryAccess *OldMA = MSSA->getMemoryAccess(I);
+            OldMA->replaceAllUsesWith(NewMemAcc);
+            MSSA->removeMemoryAccess(OldMA);
+          }
+
           Repl->intersectOptionalDataWith(I);
           combineKnownMetadata(Repl, I);
           I->replaceAllUsesWith(Repl);
Index: lib/Transforms/Utils/MemorySSA.cpp
===================================================================
--- lib/Transforms/Utils/MemorySSA.cpp
+++ lib/Transforms/Utils/MemorySSA.cpp
@@ -1147,7 +1147,7 @@
     // Insert phi node
     AccessList *Accesses = getOrCreateAccessList(BB);
     MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++);
-    ValueToMemoryAccess.insert(std::make_pair(BB, Phi));
+    ValueToMemoryAccess[BB] = Phi;
     // Phi's always are placed at the front of the block.
     Accesses->push_front(Phi);
   }
@@ -1204,7 +1204,7 @@
   assert(!getMemoryAccess(BB) && "MemoryPhi already exists for this BB");
   AccessList *Accesses = getOrCreateAccessList(BB);
   MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++);
-  ValueToMemoryAccess.insert(std::make_pair(BB, Phi));
+  ValueToMemoryAccess[BB] = Phi;
   // Phi's always are placed at the front of the block.
   Accesses->push_front(Phi);
   BlockNumberingValid.erase(BB);
@@ -1293,7 +1293,7 @@
     MUD = new MemoryDef(I->getContext(), nullptr, I, I->getParent(), NextID++);
   else
     MUD = new MemoryUse(I->getContext(), nullptr, I, I->getParent());
-  ValueToMemoryAccess.insert(std::make_pair(I, MUD));
+  ValueToMemoryAccess[I] = MUD;
   return MUD;
 }
 
@@ -1376,7 +1376,9 @@
   } else {
     MemoryInst = MA->getBlock();
   }
-  ValueToMemoryAccess.erase(MemoryInst);
+  auto VMA = ValueToMemoryAccess.find(MemoryInst);
+  if (VMA->second == MemoryInst)
+    ValueToMemoryAccess.erase(VMA);
 
   auto AccessIt = PerBlockAccesses.find(MA->getBlock());
   std::unique_ptr<AccessList> &Accesses = AccessIt->second;