Add forgetBlock in PredIteratorCache.

[trentxintong]

Summary

This is preparatory work to make Jump Threading to use PredIterCache.
There are places in which some of the predecessors are split in Jump Threading.

[• dberlin]

I'm all in favor of cache invalidation when weird things happen, but I also assume you could just tell it when you are removing/adding edges as well?

IE i would expect this kind of invalidation when we do something like "clone a loop", or "clone a region" and it's difficult to tell what happened.

But otherwise, i presume we could just update it instead of destroy it.

Anyway, probably not worth it here.
Just sayin.

[• dberlin]

Hmmm, actually, i bet, for jump threading, the way it caches preds is slower than counting them repeatedly.
If it just cached the count, that would likely be fast, but i expect the copying is slower than the counting,.

[trentxintong]

In D30871#698856, @dberlin wrote:

Hmmm, actually, i bet, for jump threading, the way it caches preds is slower than counting them repeatedly.
If it just cached the count, that would likely be fast, but i expect the copying is slower than the counting,.

There are some opportunities for caching the basicblock* list in jump threading (In addtion to the count). But we also need to do the copy ... I will wait for the outcome of your investigation in https://reviews.llvm.org/D30873

include/llvm/IR/PredIteratorCache.h

private:
   }
 
 public:
   size_t size(BasicBlock *BB) { return GetNumPreds(BB); }
   ArrayRef<BasicBlock *> get(BasicBlock *BB) {
     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();
     BlockToPredCountMap.clear();
     Memory.Reset();
   }
 };
 
 } // end namespace llvm
 
 #endif

unittests/IR/CMakeLists.txt

set(IRSources
   InstructionsTest.cpp
   IntrinsicsTest.cpp
   LegacyPassManagerTest.cpp
   MDBuilderTest.cpp
   MetadataTest.cpp
   ModuleTest.cpp
   PassManagerTest.cpp
   PatternMatch.cpp
+  PredIterCacheTest.cpp
   TypeBuilderTest.cpp
   TypesTest.cpp
   UseTest.cpp
   UserTest.cpp
   ValueHandleTest.cpp
   ValueMapTest.cpp
   ValueTest.cpp
   VerifierTest.cpp

unittests/IR/PredIterCacheTest.cpp

+//===- 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