[NFC] Add validation to Ordered Instructions

[mkazantsev]

Summary

One more measure to prevent potential problems with dangling pointers.
This patch adds validation methods in debug mode to OrderedInstructions
and OrderedBasicBlock to make sure that we are not dealing with dangling
pointers and other data inconsistencies while working with them.

The validation is called from InstructionPrecedenceTracking whenever it
makes its own validation.

[fhahn]

D51664 gets rid of building OrderedBasicBlocks and comes with its own validation of the ordering.

[mkazantsev]

Thanks @fhahn , I haven't seen it before. Actually after studying the code I came to the same conclusions as they did (that we only need to invalidate when we insert instructions or remove blocks). The mental problem I have is the comment for this class stating that: "A OrderedBasicBlock instance should be discarded whenever the source BasicBlock changes". This, in particular, means that I can check that we don't have dangling pointers whenever we make a request to this class...

I'll go read this patch.

[mkazantsev]

Abandoning in favor of https://reviews.llvm.org/D51664

include/llvm/Analysis/OrderedBasicBlock.h

public:
   OrderedBasicBlock(const BasicBlock *BasicB);
 
   /// Find out whether \p A dominates \p B, meaning whether \p A
   /// comes before \p B in \p BB. This is a simplification that considers
   /// cached instruction positions and ignores other basic blocks, being
   /// 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
 
 #endif

include/llvm/Analysis/OrderedInstructions.h

public:
   /// block.
   bool dfsBefore(const Instruction *, const Instruction *) const;
 
   /// Invalidate the OrderedBasicBlock cache when its basic block changes.
   /// i.e. If an instruction is deleted or added to the basic block, the user
   /// 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
 
 #endif // LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H

lib/Analysis/InstructionPrecedenceTracking.cpp

if (isSpecialInstruction(&Insn)) {
       assert(It->second == &Insn &&
              "Cached first special instruction is wrong!");
       return;
     }
 
   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
 
 void InstructionPrecedenceTracking::invalidateBlock(const BasicBlock *BB) {
   OI.invalidateBlock(BB);
   FirstSpecialInsts.erase(BB);
 }
 

lib/Analysis/OrderedBasicBlock.cpp

if (NAI != NumberedInsts.end() && NBI != NumberedInsts.end())
     return NAI->second < NBI->second;
   if (NAI != NumberedInsts.end())
     return true;
   if (NBI != NumberedInsts.end())
     return false;
 
   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

lib/Analysis/OrderedInstructions.cpp

bool OrderedInstructions::dfsBefore(const Instruction *InstA,
   // block.
   if (InstA->getParent() == InstB->getParent())
     return localDominates(InstA, InstB);
 
   DomTreeNode *DA = DT->getNode(InstA->getParent());
   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