Index: include/llvm/Analysis/InstructionPrecedenceTracking.h
===================================================================
--- include/llvm/Analysis/InstructionPrecedenceTracking.h
+++ include/llvm/Analysis/InstructionPrecedenceTracking.h
@@ -37,6 +37,18 @@
   // Fills information about the given block's special instructions.
   void fill(const BasicBlock *BB);
 
+#ifndef NDEBUG
+  /// Asserts that the cached info for \p BB is up-to-date. The behavior of a
+  /// query to a block with invalid cache is undefined, so we should avoid this
+  /// situation.
+  void validate(const BasicBlock *BB) const;
+
+  /// Asserts whether or not the contents of this tracking is up-to-date. It can
+  /// be used to detect situations where we failed to invalidate the map
+  /// properly.
+  void validateAll() const;
+#endif
+
 protected:
   InstructionPrecedenceTracking(DominatorTree *DT)
       : OI(OrderedInstructions(DT)) {}
Index: lib/Analysis/InstructionPrecedenceTracking.cpp
===================================================================
--- lib/Analysis/InstructionPrecedenceTracking.cpp
+++ lib/Analysis/InstructionPrecedenceTracking.cpp
@@ -23,8 +23,25 @@
 
 using namespace llvm;
 
+#ifndef NDEBUG
+static cl::opt<bool> ExpensiveAsserts(
+    "ipt-expensive-asserts",
+    cl::desc("Perform expensive assert validation on every query to Instruction"
+             " Precedence Tracking"),
+    cl::init(false), cl::Hidden);
+#endif
+
 const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction(
     const BasicBlock *BB) {
+#ifndef NDEBUG
+  // If there is a bug connected to invalid cache, turn on ExpensiveAsserts to
+  // catch this situation as early as possible.
+  if (ExpensiveAsserts)
+    validateAll();
+  else
+    validate(BB);
+#endif
+
   if (!KnownBlocks.count(BB))
     fill(BB);
   auto *FirstICF = FirstSpecialInsts.lookup(BB);
@@ -56,6 +73,38 @@
   KnownBlocks.insert(BB);
 }
 
+#ifndef NDEBUG
+void InstructionPrecedenceTracking::validate(const BasicBlock *BB) const {
+  auto It = FirstSpecialInsts.find(BB);
+  bool BlockHasSpecialInsns = false;
+  for (const Instruction &Insn : *BB) {
+    if (isSpecialInstruction(&Insn)) {
+      assert(It != FirstSpecialInsts.end() &&
+             "Blocked marked as known but we have no cached value for it!");
+      assert(It->second == &Insn &&
+             "Cached first special instruction is wrong!");
+      BlockHasSpecialInsns = true;
+      break;
+    }
+  }
+  if (!BlockHasSpecialInsns)
+    assert(It == FirstSpecialInsts.end() &&
+           "Block is marked as having special instructions but in fact it "
+           "has none!");
+}
+
+void InstructionPrecedenceTracking::validateAll() const {
+  // Check that for every known block the cached value is correct.
+  for (auto *BB : KnownBlocks)
+    validate(BB);
+
+  // Check that all blocks with cached values are marked as known.
+  for (auto &It : FirstSpecialInsts)
+    assert(KnownBlocks.count(It.first) &&
+           "We have a cached value but the block is not marked as known?");
+}
+#endif
+
 void InstructionPrecedenceTracking::invalidateBlock(const BasicBlock *BB) {
   OI.invalidateBlock(BB);
   FirstSpecialInsts.erase(BB);
@@ -67,6 +116,10 @@
     OI.invalidateBlock(It.first);
   FirstSpecialInsts.clear();
   KnownBlocks.clear();
+#ifndef NDEBUG
+  // The map should be valid after clearing (at least empty).
+  validateAll();
+#endif
 }
 
 bool ImplicitControlFlowTracking::isSpecialInstruction(