Index: include/llvm/Transforms/Utils/PredicateInfo.h
===================================================================
--- include/llvm/Transforms/Utils/PredicateInfo.h
+++ include/llvm/Transforms/Utils/PredicateInfo.h
@@ -221,6 +221,13 @@
     return PredicateMap.lookup(V);
   }
 
+  // Inform the PredicateInfo analysis when an instruction is deleted
+  // in the function.
+  void updateErasedInst(const Instruction *Inst) {
+    // Need to invalidate the ordered basicblock for the instruction.
+    OI.invalidateBlock(Inst->getParent());
+  }
+
 protected:
   // Used by PredicateInfo annotater, dumpers, and wrapper pass.
   friend class PredicateInfoAnnotatedWriter;
Index: lib/Transforms/Scalar/NewGVN.cpp
===================================================================
--- lib/Transforms/Scalar/NewGVN.cpp
+++ lib/Transforms/Scalar/NewGVN.cpp
@@ -3174,8 +3174,10 @@
     if (!ToErase->use_empty())
       ToErase->replaceAllUsesWith(UndefValue::get(ToErase->getType()));
 
-    if (ToErase->getParent())
+    if (ToErase->getParent()) {
+      PredInfo->updateErasedInst(ToErase);
       ToErase->eraseFromParent();
+    }
   }
 
   // Delete all unreachable blocks.