Index: include/llvm/Analysis/MemorySSAUpdater.h
===================================================================
--- include/llvm/Analysis/MemorySSAUpdater.h
+++ include/llvm/Analysis/MemorySSAUpdater.h
@@ -32,6 +32,7 @@
 #ifndef LLVM_ANALYSIS_MEMORYSSAUPDATER_H
 #define LLVM_ANALYSIS_MEMORYSSAUPDATER_H
 
+#include "llvm/ADT/OrderedSet.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
@@ -60,7 +61,7 @@
 class MemorySSAUpdater {
 private:
   MemorySSA *MSSA;
-  SmallVector<MemoryPhi *, 8> InsertedPHIs;
+  OrderedSet<AssertingVH<MemoryPhi>> InsertedPHIs;
   SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
   SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis;
 
Index: lib/Analysis/MemorySSAUpdater.cpp
===================================================================
--- lib/Analysis/MemorySSAUpdater.cpp
+++ lib/Analysis/MemorySSAUpdater.cpp
@@ -100,7 +100,7 @@
         unsigned i = 0;
         for (auto *Pred : predecessors(BB))
           Phi->addIncoming(PhiOps[i++], Pred);
-        InsertedPHIs.push_back(Phi);
+        InsertedPHIs.insert(Phi);
       }
       Result = Phi;
     }
@@ -205,6 +205,7 @@
   if (Same == nullptr)
     return MSSA->getLiveOnEntryDef();
   if (Phi) {
+    InsertedPHIs.erase(Phi);
     Phi->replaceAllUsesWith(Same);
     removeMemoryAccess(Phi);
   }
@@ -317,7 +318,7 @@
     MSSA->renamePass(MD->getBlock(), FirstDef, Visited);
     // We just inserted a phi into this block, so the incoming value will become
     // the phi anyway, so it does not matter what we pass.
-    for (auto *MP : InsertedPHIs)
+    for (auto &MP : InsertedPHIs)
       MSSA->renamePass(MP->getBlock(), nullptr, Visited);
   }
 }
Index: test/Transforms/GVNHoist/pr37808.ll
===================================================================
--- /dev/null
+++ test/Transforms/GVNHoist/pr37808.ll
@@ -0,0 +1,40 @@
+; RUN: opt < %s -gvn-hoist -S | FileCheck %s
+
+define void @func() {
+; CHECK-LABEL: @func()
+; CHECK:       bb6:
+; CHECK:         store i64 0, i64* undef, align 8
+; CHECK:       bb7:
+; CHECK-NOT:     store i64 0, i64* undef, align 8
+; CHECK:       bb8:
+; CHECK-NOT:     store i64 0, i64* undef, align 8
+
+entry:
+  br label %bb1
+
+bb1:
+  br label %bb2
+
+bb2:
+  br label %bb3
+
+bb3:
+  br i1 undef, label %bb4, label %bb2
+
+bb4:
+  br i1 undef, label %bb5, label %bb3
+
+bb5:
+  br label %bb6
+
+bb6:
+  br i1 undef, label %bb7, label %bb8
+
+bb7:
+  store i64 0, i64* undef, align 8
+  unreachable
+
+bb8:
+  store i64 0, i64* undef, align 8
+  ret void
+}