Index: llvm/lib/Transforms/Scalar/GVNHoist.cpp
===================================================================
--- llvm/lib/Transforms/Scalar/GVNHoist.cpp
+++ llvm/lib/Transforms/Scalar/GVNHoist.cpp
@@ -330,49 +330,47 @@
     return I1DFS < I2DFS;
   }
 
-  // Return true when there are users of Def in BB.
-  bool hasMemoryUseOnPath(MemoryAccess *Def, const BasicBlock *BB,
-                          const Instruction *OldPt) {
-    const BasicBlock *DefBB = Def->getBlock();
+  // Return true when there are memory uses of Def in BB.
+  bool hasMemoryUseOnPath(const Instruction *NewPt, MemoryDef *Def, const BasicBlock *BB) {
+    const Instruction *OldPt = Def->getMemoryInst();
     const BasicBlock *OldBB = OldPt->getParent();
+    const BasicBlock *NewBB = NewPt->getParent();
 
-    for (User *U : Def->users())
-      if (auto *MU = dyn_cast<MemoryUse>(U)) {
-        // 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;
+    MemoryLocation DefLoc = MemoryLocation::get(OldPt);
+    const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
+    for (const MemoryAccess &MA : *Acc) {
+      auto *MU = dyn_cast<MemoryUse>(&MA);
+      if (!MU)
+        continue;
 
-        // A use in the same block as the Def is on the path.
-        if (UBB == DefBB) {
-          assert(MSSA->locallyDominates(Def, MU) && "def not dominating use");
-          return true;
-        }
+      // Do not check whether MU aliases Def when MU occurs after OldPt.
+      if (BB == OldBB && firstInBB(OldPt, MU->getMemoryInst()))
+        continue;
 
-        if (UBB != OldBB)
-          return true;
+      // Do not check whether MU aliases Def when MU occurs before NewPt.
+      if (BB == NewBB && firstInBB(MU->getMemoryInst(), NewPt))
+        continue;
 
-        // It is only harmful to hoist when the use is before OldPt.
-        if (firstInBB(MU->getMemoryInst(), OldPt))
-          return true;
-      }
+      if (!AA->isNoAlias(DefLoc, MemoryLocation::get(MU->getMemoryInst())))
+        return true;
+    }
 
     return false;
   }
 
   // Return true when there are exception handling or loads of memory Def
-  // between OldPt and NewPt.
+  // between Def and NewPt.  This function is only called for stores: Def is
+  // the MemoryDef of the store to be hoisted.
 
   // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
   // return true when the counter NBBsOnAllPaths reaces 0, except when it is
   // initialized to -1 which is unlimited.
-  bool hasEHOrLoadsOnPath(const Instruction *NewPt, const Instruction *OldPt,
-                          MemoryAccess *Def, int &NBBsOnAllPaths) {
+  bool hasEHOrLoadsOnPath(const Instruction *NewPt, MemoryDef *Def,
+                          int &NBBsOnAllPaths) {
     const BasicBlock *NewBB = NewPt->getParent();
-    const BasicBlock *OldBB = OldPt->getParent();
+    const BasicBlock *OldBB = Def->getBlock();
     assert(DT->dominates(NewBB, OldBB) && "invalid path");
-    assert(DT->dominates(Def->getBlock(), NewBB) &&
+    assert(DT->dominates(Def->getDefiningAccess()->getBlock(), NewBB) &&
            "def does not dominate new hoisting point");
 
     // Walk all basic blocks reachable in depth-first iteration on the inverse
@@ -391,7 +389,7 @@
         return true;
 
       // Check that we do not move a store past loads.
-      if (hasMemoryUseOnPath(Def, *I, OldPt))
+      if (hasMemoryUseOnPath(NewPt, Def, *I))
         return true;
 
       // Stop walk once the limit is reached.
@@ -474,7 +472,7 @@
 
     // Check for unsafe hoistings due to side effects.
     if (K == InsKind::Store) {
-      if (hasEHOrLoadsOnPath(NewPt, OldPt, D, NBBsOnAllPaths))
+      if (hasEHOrLoadsOnPath(NewPt, dyn_cast<MemoryDef>(U), NBBsOnAllPaths))
         return false;
     } else if (hasEHOnPath(NewBB, OldBB, NBBsOnAllPaths))
       return false;
Index: llvm/test/Transforms/GVN/pr28626.ll
===================================================================
--- llvm/test/Transforms/GVN/pr28626.ll
+++ /dev/null
@@ -1,42 +0,0 @@
-; RUN: opt -S -gvn-hoist < %s | FileCheck %s
-target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
-target triple = "x86_64-unknown-linux-gnu"
-
-define void @test1(i1 %a, i1** %d) {
-entry:
-  %0 = load i1*, i1** %d, align 8
-  br i1 %a, label %if.then, label %if.else
-
-if.then:                                          ; preds = %entry
-  br label %if.end
-
-if.else:                                          ; preds = %entry
-  br label %if.end
-
-if.end:                                           ; preds = %if.else, %if.then
-  %c.0 = phi i1 [ 1, %if.then ], [ 0, %if.else ]
-  br i1 %c.0, label %if.then2, label %if.else3
-
-if.then2:                                         ; preds = %if.end
-  %rc = getelementptr inbounds i1, i1* %0, i64 0
-  store i1 %c.0, i1* %rc, align 4
-  br label %if.end6
-
-if.else3:                                         ; preds = %if.end
-  %rc5 = getelementptr inbounds i1, i1* %0, i64 0
-  store i1 %c.0, i1* %rc5, align 4
-  br label %if.end6
-
-if.end6:                                          ; preds = %if.else3, %if.then2
-  ret void
-}
-
-; CHECK-LABEL: define void @test1(
-; CHECK:  %[[load:.*]] = load i1*, i1** %d, align 8
-; CHECK:  %[[phi:.*]] = phi i1 [ true, {{.*}} ], [ false, {{.*}} ]
-
-; CHECK: %[[gep0:.*]] = getelementptr inbounds i1, i1* %[[load]], i64 0
-; CHECK: store i1 %[[phi]], i1* %[[gep0]], align 4
-
-; Check that store instructions are hoisted.
-; CHECK-NOT: store
\ No newline at end of file
Index: llvm/test/Transforms/GVNHoist/pr28626.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/GVNHoist/pr28626.ll
@@ -0,0 +1,42 @@
+; RUN: opt -S -gvn-hoist < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @test1(i1 %a, i1** %d) {
+entry:
+  %0 = load i1*, i1** %d, align 8
+  br i1 %a, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %c.0 = phi i1 [ 1, %if.then ], [ 0, %if.else ]
+  br i1 %c.0, label %if.then2, label %if.else3
+
+if.then2:                                         ; preds = %if.end
+  %rc = getelementptr inbounds i1, i1* %0, i64 0
+  store i1 %c.0, i1* %rc, align 4
+  br label %if.end6
+
+if.else3:                                         ; preds = %if.end
+  %rc5 = getelementptr inbounds i1, i1* %0, i64 0
+  store i1 %c.0, i1* %rc5, align 4
+  br label %if.end6
+
+if.end6:                                          ; preds = %if.else3, %if.then2
+  ret void
+}
+
+; CHECK-LABEL: define void @test1(
+; CHECK:  %[[load:.*]] = load i1*, i1** %d, align 8
+; CHECK:  %[[phi:.*]] = phi i1 [ true, {{.*}} ], [ false, {{.*}} ]
+
+; CHECK: %[[gep0:.*]] = getelementptr inbounds i1, i1* %[[load]], i64 0
+; CHECK: store i1 %[[phi]], i1* %[[gep0]], align 4
+
+; Check that store instructions are hoisted.
+; CHECK-NOT: store
\ No newline at end of file
Index: llvm/test/Transforms/GVNHoist/pr30216.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/GVNHoist/pr30216.ll
@@ -0,0 +1,52 @@
+; RUN: opt -S -gvn-hoist < %s | FileCheck %s
+
+; Make sure the two stores @B do not get hoisted past the load @B.
+
+; CHECK-LABEL: define i8* @Foo
+; CHECK: store
+; CHECK: store
+; CHECK: load
+; CHECK: store
+
+@A = external global i8
+@B = external global i8*
+
+define i8* @Foo() {
+  store i8 0, i8* @A
+  br i1 undef, label %if.then, label %if.else
+
+if.then:
+  store i8* null, i8** @B
+  ret i8* null
+
+if.else:
+  %1 = load i8*, i8** @B
+  store i8* null, i8** @B
+  ret i8* %1
+}
+
+; Make sure the two stores @B do not get hoisted past the store @GlobalVar.
+
+; CHECK-LABEL: define i8* @Fun
+; CHECK: store
+; CHECK: store
+; CHECK: store
+; CHECK: store
+; CHECK: load
+
+@GlobalVar = internal global i8 0
+
+define i8* @Fun() {
+  store i8 0, i8* @A
+  br i1 undef, label %if.then, label %if.else
+
+if.then:
+  store i8* null, i8** @B
+  ret i8* null
+
+if.else:
+  store i8 0, i8* @GlobalVar
+  store i8* null, i8** @B
+  %1 = load i8*, i8** @B
+  ret i8* %1
+}