Index: lib/Analysis/MemorySSAUpdater.cpp
===================================================================
--- lib/Analysis/MemorySSAUpdater.cpp
+++ lib/Analysis/MemorySSAUpdater.cpp
@@ -65,7 +65,7 @@
 
   if (VisitedBlocks.insert(BB).second) {
     // Mark us visited so we can detect a cycle
-    SmallVector<MemoryAccess *, 8> PhiOps;
+    SmallVector<WeakVH, 8> PhiOps;
 
     // Recurse to get the values in our predecessors for placement of a
     // potential phi node. This will insert phi nodes if we cycle in order to
@@ -76,14 +76,6 @@
     // Now try to simplify the ops to avoid placing a phi.
     // This may return null if we never created a phi yet, that's okay
     MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MSSA->getMemoryAccess(BB));
-    bool PHIExistsButNeedsUpdate = false;
-    // See if the existing phi operands match what we need.
-    // Unlike normal SSA, we only allow one phi node per block, so we can't just
-    // create a new one.
-    if (Phi && Phi->getNumOperands() != 0)
-      if (!std::equal(Phi->op_begin(), Phi->op_end(), PhiOps.begin())) {
-        PHIExistsButNeedsUpdate = true;
-      }
 
     // See if we can avoid the phi by simplifying it.
     auto *Result = tryRemoveTrivialPhi(Phi, PhiOps);
@@ -92,14 +84,28 @@
       if (!Phi)
         Phi = MSSA->createMemoryPhi(BB);
 
-      // These will have been filled in by the recursive read we did above.
-      if (PHIExistsButNeedsUpdate) {
-        std::copy(PhiOps.begin(), PhiOps.end(), Phi->op_begin());
-        std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin());
+      // PhiOps might be out of date.
+      unsigned i = 0;
+      for (auto *Pred : predecessors(BB)) {
+        auto *MA = dyn_cast_or_null<MemoryAccess>(PhiOps[i]);
+        if (!MA)
+          PhiOps[i] = getPreviousDefFromEnd(Pred, CachedPreviousDef);
+        ++i;
+      }
+
+      // See if the existing phi operands match what we need.
+      // Unlike normal SSA, we only allow one phi node per block, so we can't just
+      // create a new one.
+      if (Phi && Phi->getNumOperands() != 0) {
+        if (!std::equal(Phi->op_begin(), Phi->op_end(), PhiOps.begin())) {
+          // These will have been filled in by the recursive read we did above.
+          std::copy(PhiOps.begin(), PhiOps.end(), Phi->op_begin());
+          std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin());
+        }
       } else {
         unsigned i = 0;
         for (auto *Pred : predecessors(BB))
-          Phi->addIncoming(PhiOps[i++], Pred);
+          Phi->addIncoming(cast<MemoryAccess>(PhiOps[i++]), Pred);
         InsertedPHIs.push_back(Phi);
       }
       Result = Phi;
Index: test/Bitcode/pr37445.ll
===================================================================
--- /dev/null
+++ test/Bitcode/pr37445.ll
@@ -0,0 +1,19 @@
+; RUN: opt < %s.bc -early-cse-memssa -gvn-hoist -S | FileCheck %s
+
+; Make sure opt won't crash and that this pair
+; of instructions is hoisted successfully from
+; bb45 and bb58 to bb41.
+
+;CHECK-LABEL: @func_22
+
+;CHECK:       bb41:
+;CHECK:         %tmp47 = load i32, i32* %arg1, align 4
+;CHECK:         %tmp48 = icmp eq i32 %tmp47, 0
+
+;CHECK:       bb45:
+;CHECK-NOT:     %tmp47 = load i32, i32* %arg1, align 4
+;CHECK-NOT:     %tmp48 = icmp eq i32 %tmp47, 0
+
+;CHECK:       bb58:
+;CHECK-NOT:     %tmp60 = load i32, i32* %arg1, align 4
+;CHECK-NOT:     %tmp61 = icmp eq i32 %tmp60, 0