Index: include/llvm/Analysis/MemorySSAUpdater.h
===================================================================
--- include/llvm/Analysis/MemorySSAUpdater.h
+++ include/llvm/Analysis/MemorySSAUpdater.h
@@ -33,6 +33,7 @@
 #define LLVM_ANALYSIS_MEMORYSSAUPDATER_H
 
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/IR/BasicBlock.h"
@@ -61,6 +62,7 @@
   MemorySSA *MSSA;
   SmallVector<MemoryPhi *, 8> InsertedPHIs;
   SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
+  SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis;
 
 public:
   MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
Index: lib/Analysis/MemorySSAUpdater.cpp
===================================================================
--- lib/Analysis/MemorySSAUpdater.cpp
+++ lib/Analysis/MemorySSAUpdater.cpp
@@ -180,6 +180,10 @@
 template <class RangeType>
 MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
                                                     RangeType &Operands) {
+  // Bail out on non-opt Phis.
+  if (NonOptPhis.count(Phi))
+    return Phi;
+
   // Detect equal or self arguments
   MemoryAccess *Same = nullptr;
   for (auto &Op : Operands) {
@@ -320,6 +324,10 @@
     auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock());
     auto DefIter = NewDef->getDefsIterator();
 
+    // The temporary Phi is being fixed, unmark it for not to optimize.
+    if (MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(NewDef))
+      NonOptPhis.erase(Phi);
+
     // If there is a local def after us, we only have to rename that.
     if (++DefIter != Defs->end()) {
       cast<MemoryDef>(DefIter)->setDefiningAccess(NewDef);
@@ -379,6 +387,11 @@
 template <class WhereType>
 void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
                               WhereType Where) {
+  // Mark MemoryPhi users of What not to be optimized.
+  for (auto *U : What->users())
+    if (MemoryPhi *PhiUser = dyn_cast_or_null<MemoryPhi>(U))
+      NonOptPhis.insert(PhiUser);
+
   // Replace all our users with our defining access.
   What->replaceAllUsesWith(What->getDefiningAccess());
 
@@ -390,6 +403,10 @@
     insertDef(MD);
   else
     insertUse(cast<MemoryUse>(What));
+
+  // Clear dangling pointers. We added all MemoryPhi users, but not all
+  // of them are removed by fixupDefs().
+  NonOptPhis.clear();
 }
 
 // Move What before Where in the MemorySSA IR.
Index: test/Transforms/GVNHoist/non-trivial-phi.ll
===================================================================
--- /dev/null
+++ test/Transforms/GVNHoist/non-trivial-phi.ll
@@ -0,0 +1,34 @@
+; RUN: opt -gvn-hoist %s -S -o - | FileCheck %s
+
+; CHECK: store
+; CHECK-NOT: store
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+
+define void @f(i8* %p) {
+entry:
+  switch i4 undef, label %if.then30 [
+    i4 4, label %if.end
+    i4 0, label %if.end
+  ]
+
+if.end:
+  br label %if.end19
+
+if.end19:
+  br i1 undef, label %e, label %e.thread
+
+e.thread:
+  store i8 0, i8* %p, align 4
+  br label %if.then30
+
+if.then30:
+  call void @g()
+  unreachable
+
+e:
+  store i8 0, i8* %p, align 4
+  unreachable
+}
+
+declare void @g()