Return "[NFC] Add severe validation of InstructionPrecedenceTracking"

[mkazantsev]

Summary

This validation patch has been reverted as rL341147 because of conserns raised by
@reames. This revision returns it as is to raise a discussion and address the concerns.

[reames]

include/llvm/Analysis/InstructionPrecedenceTracking.h

54

I really really think there should be a destructor here which checks to make sure the information is still valid. If the info is no longer used, a client can call clear explicitly.

lib/Analysis/InstructionPrecedenceTracking.cpp

36

As noted, calling this here makes this operation unexpected O(Inst in F) in the worst case.

Please check only the containing block.

79

This comment caused me to misread. Something more along the lines of:
// For each block we have cached, make sure we cached the right answer

[mkazantsev]

include/llvm/Analysis/InstructionPrecedenceTracking.h

54

I don't understand why we want it to be valid on destructor. We definitely are not going to use this after the destructor is executed, it's OK if it contains garbage. We only want the contents to be OK on *queries*.

[mkazantsev]

lib/Analysis/InstructionPrecedenceTracking.cpp

36

This is intentional. If we have modified a block and haven't dropped cached info, we want to detect it as early as possible, specifically when we make *any* query to this tracking. Imagine we've screwed up invalidating a block A, then did 100 correct modifications and queries to other blocks and then requested something for A. The assertion will fail, and it will be very hard to figure out what and when has happened.

On the other hand, in current strategy we will be able to detect that we've screwed up whenever any query is made, which was the entire point of making this patch.

I don't think that win on compile time in debug mode is worth making investigation of functional bugs more complex.

[mkazantsev]

After offline discussion with Philip, we agreed on the following version: by default, we have one-block verification to keep compile time in reasonable bounds. For troubleshooting purposes, there is an option (false by default and with no intention to turn it on) to diagnose it. Assertion on destructor does not happen because we don't have a commitment to keep the information valid after the last point where the last query was made.

[reames]

LGTM w/ changes made before submit.

include/llvm/Analysis/InstructionPrecedenceTracking.h

42

You're better off defining the behaviour as being erroneous. (i.e. illegal). Suggest alternate wording:
This helps to catch the usage error of accessing a block without properly invalidating after a previous transform.

lib/Analysis/InstructionPrecedenceTracking.cpp

77

Optional, can be follow up: You'd be better to reduce the scope of the conditional compilation by using a conditional early return in this function.

101

You can write this as:
assert(KnownBlocks.size() == FirstSpecialInsts.size())

since you've already validated each bloc, if there are no other special instructions, no further validation is needed.

[mkazantsev]

lib/Analysis/InstructionPrecedenceTracking.cpp

101

It is not true. We can have some block in KnownBlocks and nothing in FirstSpecialInsts, and it will mean that there is no special instructions in this block. Maybe it makes sense to put nullptr for such blocks instead and completely eliminate KnownBlocks, I'll do it as a follow-up NFC.

[mkazantsev]

lib/Analysis/InstructionPrecedenceTracking.cpp

101

https://reviews.llvm.org/rL341531

This looks much more clearly now.

include/llvm/Analysis/InstructionPrecedenceTracking.h

class InstructionPrecedenceTracking {
   // Allows to answer queries about precedence of instructions within one block.
   OrderedInstructions OI;
   // Blocks for which we have the up-to-date cached information.
   SmallPtrSet<const BasicBlock *, 8> KnownBlocks;
 
   // 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)) {}
 
   /// Returns the topmost special instruction from the block \p BB. Returns
   /// nullptr if there is no special instructions in the block.
   const Instruction *getFirstSpecialInstruction(const BasicBlock *BB);
 
   /// Returns true iff at least one instruction from the basic block \p BB is
   /// special.
   bool hasSpecialInstructions(const BasicBlock *BB);

lib/Analysis/InstructionPrecedenceTracking.cpp

 // a content of some tracked block is changed.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/InstructionPrecedenceTracking.h"
 #include "llvm/Analysis/ValueTracking.h"
 
 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);
   assert((!FirstICF || FirstICF->getParent() == BB) && "Inconsistent cache!");
   return FirstICF;
 }
 
 bool InstructionPrecedenceTracking::hasSpecialInstructions(
if (isSpecialInstruction(&I)) {
       FirstSpecialInsts[BB] = &I;
       break;
     }
 
   // Mark this block as having a known result.
   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);
   KnownBlocks.erase(BB);
 }
 
 void InstructionPrecedenceTracking::clear() {
   for (auto It : FirstSpecialInsts)
     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(
     const Instruction *Insn) const {
   // If a block's instruction doesn't always pass the control to its successor
   // instruction, mark the block as having implicit control flow. We use them
   // to avoid wrong assumptions of sort "if A is executed and B post-dominates
   // A, then B is also executed". This is not true is there is an implicit