Index: llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp
+++ llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp
@@ -2549,6 +2549,19 @@
           return false;
         if (auto *MemDef = dyn_cast<MemoryDef>(Pair.first))
           return !isInstructionTriviallyDead(MemDef->getMemoryInst());
+
+        // We could have phi nodes which operands are all trivially dead,
+        // so we don't process them.
+        if (auto *MemPHI = dyn_cast<MemoryPhi>(Pair.first)) {
+          for (auto &U : MemPHI->incoming_values()) {
+            if (Instruction *I = dyn_cast<Instruction>(U.get())) {
+              if (!isInstructionTriviallyDead(I))
+                return true;
+            }
+          }
+          return false;
+        }
+
         return true;
       };
 
Index: llvm/trunk/test/Transforms/NewGVN/verify-memoryphi.ll
===================================================================
--- llvm/trunk/test/Transforms/NewGVN/verify-memoryphi.ll
+++ llvm/trunk/test/Transforms/NewGVN/verify-memoryphi.ll
@@ -0,0 +1,29 @@
+; Skip dead MemoryPhis when performing memory congruency verification
+; in NewGVN.
+; RUN: opt -S -newgvn %s | FileCheck %s
+; REQUIRES: asserts
+
+; CHECK: define void @tinkywinky() {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   br i1 false, label %body, label %end
+; CHECK:      body:
+; CHECK-NEXT:   store i8 undef, i8* null
+; CHECK-NEXT:   br label %end
+; CHECK:      end:
+; CHECK-NEXT:   ret void
+; CHECK-NEXT: }
+
+declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture)
+
+define void @tinkywinky() {
+entry:
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* undef)
+  br i1 false, label %body, label %end
+
+body:
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* undef)
+  br label %end
+
+end:
+  ret void
+}