Index: include/llvm/Analysis/OrderedBasicBlock.h
===================================================================
--- include/llvm/Analysis/OrderedBasicBlock.h
+++ include/llvm/Analysis/OrderedBasicBlock.h
@@ -60,6 +60,11 @@
   /// only relevant to compare relative instructions positions inside \p BB.
   /// Returns false for A == B.
   bool dominates(const Instruction *A, const Instruction *B);
+
+#ifndef NDEBUG
+  /// Validates consistency of cached info in this block.
+  void validate() const;
+#endif
 };
 
 } // End llvm namespace
Index: include/llvm/Analysis/OrderedInstructions.h
===================================================================
--- include/llvm/Analysis/OrderedInstructions.h
+++ include/llvm/Analysis/OrderedInstructions.h
@@ -58,6 +58,14 @@
   /// should call this function to invalidate the OrderedBasicBlock cache for
   /// this basic block.
   void invalidateBlock(const BasicBlock *BB) { OBBMap.erase(BB); }
+
+#ifndef NDEBUG
+  /// Validates consistency of cached info for \p BB.
+  void validate(const BasicBlock *BB) const;
+
+  /// Validates consistency of cached info for all blocks.
+  void validateAll() const;
+#endif
 };
 
 } // end namespace llvm
Index: lib/Analysis/InstructionPrecedenceTracking.cpp
===================================================================
--- lib/Analysis/InstructionPrecedenceTracking.cpp
+++ lib/Analysis/InstructionPrecedenceTracking.cpp
@@ -90,12 +90,14 @@
   assert(It->second == nullptr &&
          "Block is marked as having special instructions but in fact it  has "
          "none!");
+  OI.validate(BB);
 }
 
 void InstructionPrecedenceTracking::validateAll() const {
   // Check that for every known block the cached value is correct.
   for (auto &It : FirstSpecialInsts)
     validate(It.first);
+  OI.validateAll();
 }
 #endif
 
Index: lib/Analysis/OrderedBasicBlock.cpp
===================================================================
--- lib/Analysis/OrderedBasicBlock.cpp
+++ lib/Analysis/OrderedBasicBlock.cpp
@@ -83,3 +83,34 @@
 
   return comesBefore(A, B);
 }
+
+#ifndef NDEBUG
+void OrderedBasicBlock::validate() const {
+  // Check that all instructions in map are in the current BB.
+  for (auto &It : NumberedInsts)
+    assert(It.first->getParent() == BB && "Instruction not in the block?");
+
+  // Check that:
+  // 1. We have numbers for all instructions until some point;
+  // 2. They go in ascending order.
+  bool WorkingWithKnownInstructions = true;
+  bool FirstSeen = true;
+  unsigned LastSeenID = 0;
+  for (const Instruction &I : *BB) {
+    auto It = NumberedInsts.find(&I);
+    if (It == NumberedInsts.end()) {
+      // No known instructions any more.
+      WorkingWithKnownInstructions = false;
+      continue;
+    }
+    assert(WorkingWithKnownInstructions && "There was an instruction without "
+                                           "number and then an instruction "
+                                           "with number?");
+    if (!FirstSeen)
+      assert(It->second > LastSeenID &&
+             "Numbers should go in increasing order!");
+    LastSeenID = It->second;
+    FirstSeen = false;
+  }
+}
+#endif
Index: lib/Analysis/OrderedInstructions.cpp
===================================================================
--- lib/Analysis/OrderedInstructions.cpp
+++ lib/Analysis/OrderedInstructions.cpp
@@ -49,3 +49,17 @@
   DomTreeNode *DB = DT->getNode(InstB->getParent());
   return DA->getDFSNumIn() < DB->getDFSNumIn();
 }
+
+#ifndef NDEBUG
+void OrderedInstructions::validate(const BasicBlock *BB) const {
+  auto It = OBBMap.find(BB);
+  if (It == OBBMap.end())
+    return;
+  It->second->validate();
+}
+
+void OrderedInstructions::validateAll() const {
+  for (auto &It : OBBMap)
+    It.second->validate();
+}
+#endif