Index: llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp
+++ llvm/trunk/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;
@@ -742,9 +740,23 @@
             !makeGepOperandsAvailable(Repl, HoistPt, InstructionsToHoist))
           continue;
 
+        // Move the instruction at the end of HoistPt.
         Repl->moveBefore(HoistPt->getTerminator());
       }
 
+      MemoryAccess *NewMemAcc = nullptr;
+      if (MemoryAccess *MA = MSSA->getMemoryAccess(Repl)) {
+        if (MemoryUseOrDef *OldMemAcc = dyn_cast<MemoryUseOrDef>(MA)) {
+          // 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))
         ++NL;
       else if (isa<StoreInst>(Repl))
@@ -775,11 +787,36 @@
           } 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);
           I->eraseFromParent();
         }
+
+      // Remove MemorySSA phi nodes with the same arguments.
+      if (NewMemAcc) {
+        SmallPtrSet<MemoryPhi *, 4> UsePhis;
+        for (User *U : NewMemAcc->users())
+          if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(U))
+            UsePhis.insert(Phi);
+
+        for (auto *Phi : UsePhis) {
+          auto In = Phi->incoming_values();
+          if (std::all_of(In.begin(), In.end(),
+                          [&](Use &U){return U == NewMemAcc;})) {
+            Phi->replaceAllUsesWith(NewMemAcc);
+            MSSA->removeMemoryAccess(Phi);
+          }
+        }
+      }
     }
 
     NumHoisted += NL + NS + NC + NI;
Index: llvm/trunk/test/Transforms/GVN/hoist-mssa.ll
===================================================================
--- llvm/trunk/test/Transforms/GVN/hoist-mssa.ll
+++ llvm/trunk/test/Transforms/GVN/hoist-mssa.ll
@@ -0,0 +1,69 @@
+; RUN: opt -S -gvn-hoist < %s | FileCheck %s
+
+; Check that store hoisting works: there should be only one store left.
+; CHECK-LABEL: @getopt
+; CHECK: store i32
+; CHECK-NOT: store i32
+
+@optind = external global i32, align 4
+
+define void @getopt() {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb
+  br i1 undef, label %bb2, label %bb3
+
+bb2:                                              ; preds = %bb1
+  br label %bb13
+
+bb3:                                              ; preds = %bb1
+  br i1 undef, label %bb4, label %bb9
+
+bb4:                                              ; preds = %bb3
+  %tmp = load i32, i32* @optind, align 4
+  br i1 undef, label %bb5, label %bb7
+
+bb5:                                              ; preds = %bb4
+  %tmp6 = add nsw i32 %tmp, 1
+  store i32 %tmp6, i32* @optind, align 4
+  br label %bb12
+
+bb7:                                              ; preds = %bb4
+  %tmp8 = add nsw i32 %tmp, 1
+  store i32 %tmp8, i32* @optind, align 4
+  br label %bb13
+
+bb9:                                              ; preds = %bb3
+  %tmp10 = load i32, i32* @optind, align 4
+  %tmp11 = add nsw i32 %tmp10, 1
+  store i32 %tmp11, i32* @optind, align 4
+  br label %bb12
+
+bb12:                                             ; preds = %bb9, %bb5
+  br label %bb13
+
+bb13:                                             ; preds = %bb12, %bb7, %bb2
+  ret void
+}
+
+@GlobalVar = internal global float 1.000000e+00
+
+; Check that we hoist stores and remove the MSSA phi node.
+; CHECK-LABEL: @hoistStoresUpdateMSSA
+; CHECK: store float
+; CHECK-NOT: store float
+define float @hoistStoresUpdateMSSA(float %d) {
+entry:
+  store float 0.000000e+00, float* @GlobalVar
+  %cmp = fcmp oge float %d, 0.000000e+00
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store float 0.000000e+00, float* @GlobalVar
+  br label %if.end
+
+if.end:
+  %tmp = load float, float* @GlobalVar, align 4
+  ret float %tmp
+}