Index: include/llvm/IR/PredIteratorCache.h
===================================================================
--- include/llvm/IR/PredIteratorCache.h
+++ include/llvm/IR/PredIteratorCache.h
@@ -66,6 +66,12 @@
     return makeArrayRef(GetPreds(BB), GetNumPreds(BB));
   }
 
+  /// forgetBlock - Forget about predecessors for this basic block.
+  void forgetBlock(BasicBlock *BB) {
+    BlockToPredsMap.erase(BB);
+    BlockToPredCountMap.erase(BB);
+  }
+
   /// clear - Remove all information.
   void clear() {
     BlockToPredsMap.clear();
Index: unittests/IR/CMakeLists.txt
===================================================================
--- unittests/IR/CMakeLists.txt
+++ unittests/IR/CMakeLists.txt
@@ -23,6 +23,7 @@
   ModuleTest.cpp
   PassManagerTest.cpp
   PatternMatch.cpp
+  PredIterCacheTest.cpp
   TypeBuilderTest.cpp
   TypesTest.cpp
   UseTest.cpp
Index: unittests/IR/PredIterCacheTest.cpp
===================================================================
--- /dev/null
+++ unittests/IR/PredIterCacheTest.cpp
@@ -0,0 +1,92 @@
+//===- llvm/unittest/IR/PredIterCacheTest.cpp - Type unit tests -----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/StringRef.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PredIteratorCache.h"
+#include "llvm/Support/SourceMgr.h"
+#include "gtest/gtest.h"
+using namespace llvm;
+
+namespace {
+
+// Simple predecessor count test.
+// Make sure we can invalidate the cache properly and get the correct
+// predecessor count.
+TEST(PredIterCacheTest, PredCount) {
+  // The ret-block will have 4 predecessors here.
+  const char *ModuleStr = "define void @foo() {\n"
+                          "entry:\n"
+                          "  br i1 undef, label %xl, label %xr\n"
+                          "xl:\n"
+                          "  br i1 undef, label %xll, label %xlr\n"
+                          "xll:\n"
+                          "  br label %ret\n"
+                          "xlr:\n"
+                          "  br label %ret\n"
+                          "xr:\n"
+                          "  br i1 undef, label %xrl, label %xrr\n"
+                          "xrl:\n"
+                          "  br label %ret\n"
+                          "xrr:\n"
+                          "  br label %ret\n"
+                          "ret:\n"
+                          "  ret void\n"
+                          "}\n";
+
+  // Parse the module.
+  LLVMContext Context;
+  SMDiagnostic Err;
+  std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context);
+
+  // The function is called foo.
+  PredIteratorCache PredCache;
+  Function *F = &*(M->begin());
+  ASSERT_EQ("foo", F->getName());
+
+  // Find the return block.
+  BasicBlock *RetBB = nullptr;
+  for (auto &BB : *F) {
+    // This is the ret block.
+    if (BB.getName().equals("ret")) {
+      RetBB = &BB;
+      break;
+    }
+  }
+
+  ASSERT_NE(nullptr, RetBB);
+
+  // Return block has 4 predecessors now.
+  ASSERT_EQ("ret", RetBB->getName());
+  ASSERT_EQ(4u, PredCache.size(RetBB));
+
+  // Remove the first 2 predecessor.
+  int Count = 0;
+  for (auto *PB : PredCache.get(RetBB)) {
+    if (++Count > 2)
+      break;
+    // Remove this predecessor and make its terminator an unreachable.
+    // We do not have phi-nodes in return block, so no need to call
+    // removePredecessor().
+    PB->getTerminator()->eraseFromParent();
+    new UnreachableInst(Context, PB);
+  }
+
+  // Forget the predecessor list for this block.
+  PredCache.forgetBlock(RetBB);
+
+  // RetBB predecessor list has been changed and now it only has 2 predecessors.
+  ASSERT_EQ("ret", RetBB->getName());
+  ASSERT_EQ(2u, PredCache.size(RetBB));
+}
+
+} // end anonymous namespace