[IPT] Restructure cache to allow lazy update following invalidation [NFC]

[reames]

Summary

This change restructures the cache used in IPT to point not to the first special instruction, but to the first instruction which *could* be special. That is, the cached reference is always equal to the first special, or comes before it in the block.

This avoids expensive block scans when we are removing special instructions from the beginning of the block. At the moment, this case is not heavily used, though it does trigger in GVN when doing CSE of calls. The main motivation was a change I'm no longer planning to move forward with, but the cache optimization seemed worthwhile as a minor perf win at low cost.

[mkazantsev]

llvm/lib/Analysis/InstructionPrecedenceTracking.cpp

96

This loosens the validation. What if I is not special? We used to check this and now we don't.

128

This looks correct, but it's not entirely an NFC. We used to completely drop cache, assuming that after the removal we could insert smth in the beginning of this block and this will be fine. Now, if we insert a special instruction before this point, it will not be found. Could you please review the users of removeInstruction and confirm that we never use it as invalidation for insertion (which we shouldn't be doing, but not a fact that we don't).

[mkazantsev]

Please mark [NFC] if you don't expect it to have any other implications than compile time improvement.

[reames]

llvm/lib/Analysis/InstructionPrecedenceTracking.cpp

96

We check to see if I is special just below. And as indicated in the comment, the cached result does not need to be special, just before any special instruction.

128

This was never the documented public interface of this class, but in theory it's a risk. I have glanced at existing usage, and didn't see anything suspicious.

[nikic]

Not seeing any practical impact from this, but the change generally looks reasonable to me.

llvm/lib/Analysis/InstructionPrecedenceTracking.cpp

52

To avoid doing the BB lookup three times, use something like this?

auto It = FirstSpecialInsts.try_emplace(BB, &BB->front()).first;
Instruction *CurI = It->second;
// ...
It->second = Res;

[mkazantsev]

llvm/lib/Analysis/InstructionPrecedenceTracking.cpp

96

If I is not special but it somehow got into the It->second, where do you detect that?

[reames]

llvm/lib/Analysis/InstructionPrecedenceTracking.cpp

52

I'll be honest here and say that I find the try_emplace style code simply unreadable. I tried to write something based on your suggestion, and gave up when I couldn't decipher the error messages.

I doubt this will be performance critical. The hot path is the second if, so at most we have two lookups on the fast path.

I'd strongly prefer to leave this as is.

96

Max, you appear to be missing the point of the change. The cached entry (e.g. It->second) is by design no longer always special. It's simply guaranteed to comeBefore the first special instruction. It is not an error for the cached instruction not to be special. It's only an error for there to be a special instruction before the cached one.

[aeubanks]

lgtm

[benlangmuir]

It looks like this caused an assertion failure on buildbots, would you mind reverting?

https://lab.llvm.org/buildbot/#/builders/77/builds/10715
https://lab.llvm.org/buildbot/#/builders/98/builds/7617/

Assertion `!isSpecialInstruction(&I) && "Cached first special instruction is wrong!"' failed.
...
#10 0x0000000004e1519d LookupBucketFor<const llvm::BasicBlock *> /var/lib/buildbot/sanitizer-buildbot6/sanitizer-x86_64-linux-android/build/llvm-project/llvm/include/llvm/ADT/DenseMap.h:622:5
#11 0x0000000004e1519d find /var/lib/buildbot/sanitizer-buildbot6/sanitizer-x86_64-linux-android/build/llvm-project/llvm/include/llvm/ADT/DenseMap.h:161:9
#12 0x0000000004e1519d llvm::InstructionPrecedenceTracking::validate(llvm::BasicBlock const*) const /var/lib/buildbot/sanitizer-buildbot6/sanitizer-x86_64-linux-android/build/llvm-project/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp:89:31
#13 0x0000000004e14b0c llvm::InstructionPrecedenceTracking::getFirstSpecialInstruction(llvm::BasicBlock const*) /var/lib/buildbot/sanitizer-buildbot6/sanitizer-x86_64-linux-android/build/llvm-project/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp:50:8
#14 0x0000000004e1523d llvm::InstructionPrecedenceTracking::isPreceededBySpecialInstruction(llvm::Instruction const*) /var/lib/buildbot/sanitizer-buildbot6/sanitizer-x86_64-linux-android/build/llvm-project/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp:84:10
#15 0x0000000005a8a0de isDominatedByICFIFromSameBlock /var/lib/buildbot/sanitizer-buildbot6/sanitizer-x86_64-linux-android/build/llvm-project/llvm/include/llvm/Analysis/InstructionPrecedenceTracking.h:114:12

[aeubanks]

I've gone ahead and reverted this

[reames]

In D111768#3078602, @aeubanks wrote:

I've gone ahead and reverted this

Thanks.

[reames]

I spent time looking into the assertion failure reported, and haven't made much progress. Given this patch was of minor importance, I'm simply going to abandon it until further need comes up.

The assert looks like a missing update in GVN, but I can't find any such thing. Unfortunately, all of the builders which failed are fairly complicated, and none of them captured detail IR or anything which is easily reproducible locally.

llvm/include/llvm/Analysis/InstructionPrecedenceTracking.h

 #include "llvm/ADT/DenseMap.h"
 
 namespace llvm {
 
 class BasicBlock;
 class Instruction;
 
 class InstructionPrecedenceTracking {
-  // Maps a block to the topmost special instruction in it. If the value is
-  // nullptr, it means that it is known that this block does not contain any
-  // special instructions.
+  // Maps a block to the topmost instruction which *might* be a special
+  // instruction in it. This value is lazily updated on query to point to the
+  // topmost special instruction, but we allow it to point before that for
+  // efficient invalidation.  If the value is nullptr, it means that it is
+  // known that this block does not contain any special instructions.
   DenseMap<const BasicBlock *, const Instruction *> FirstSpecialInsts;
 
-  // 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. This helps to catch
   /// the usage error of accessing a block without properly invalidating after a
   /// previous transform.
   void validate(const BasicBlock *BB) const;
 
   /// Asserts whether or not the contents of this tracking is up-to-date. This
   /// helps to catch the usage error of accessing a block without properly

llvm/lib/Analysis/InstructionPrecedenceTracking.cpp

#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 (FirstSpecialInsts.find(BB) == FirstSpecialInsts.end()) {
-    fill(BB);
-    assert(FirstSpecialInsts.find(BB) != FirstSpecialInsts.end() && "Must be!");
+  if (!FirstSpecialInsts.count(BB))
+    // Seed the lazy scan
+    FirstSpecialInsts[BB] = &*BB->begin();
+
+  auto *CurI = FirstSpecialInsts[BB];
+  if (!CurI || isSpecialInstruction(CurI))
+    // We found a cached definite result
+    return CurI;
+
+  // Otherwise, scan forward until we find a definite result, then cache that.
+  auto *Res = [&]() -> const Instruction * {
+    for (auto &I : make_range(CurI->getIterator(), BB->end())) {
+      NumInstScanned++;
+      if (isSpecialInstruction(&I))
+        // Found next special instruction
+        return &I;
     }
-  return FirstSpecialInsts[BB];
+    // Mark this block as having no special instructions.
+    return nullptr;
+  }();
+
+  FirstSpecialInsts[BB] = Res;
+  return Res;
 }
 
 bool InstructionPrecedenceTracking::hasSpecialInstructions(
     const BasicBlock *BB) {
   return getFirstSpecialInstruction(BB) != nullptr;
 }
 
 bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(
     const Instruction *Insn) {
   const Instruction *MaybeFirstSpecial =
       getFirstSpecialInstruction(Insn->getParent());
   return MaybeFirstSpecial && MaybeFirstSpecial->comesBefore(Insn);
 }
 
-void InstructionPrecedenceTracking::fill(const BasicBlock *BB) {
-  FirstSpecialInsts.erase(BB);
-  for (auto &I : *BB) {
-    NumInstScanned++;
-    if (isSpecialInstruction(&I)) {
-      FirstSpecialInsts[BB] = &I;
-      return;
-    }
-  }
-
-  // Mark this block as having no special instructions.
-  FirstSpecialInsts[BB] = nullptr;
-}
-
 #ifndef NDEBUG
 void InstructionPrecedenceTracking::validate(const BasicBlock *BB) const {
   auto It = FirstSpecialInsts.find(BB);
   // Bail if we don't have anything cached for this block.
   if (It == FirstSpecialInsts.end())
     return;
 
-  for (const Instruction &Insn : *BB)
-    if (isSpecialInstruction(&Insn)) {
-      assert(It->second == &Insn &&
-             "Cached first special instruction is wrong!");
+  for (const Instruction &I : *BB) {
+    if (&I == It->second)
+      // No special instruction before cached result
       return;
-    }
+    assert(!isSpecialInstruction(&I) &&
+           "Cached first special instruction is wrong!");
 
   assert(It->second == nullptr &&
          "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 &It : FirstSpecialInsts)
     validate(It.first);
 }
 #endif
 
 void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst,
                                                         const BasicBlock *BB) {
   if (isSpecialInstruction(Inst))
     FirstSpecialInsts.erase(BB);
 }
 
 void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {
   auto *BB = Inst->getParent();
   assert(BB && "must be called before instruction is actually removed");
-  if (FirstSpecialInsts.count(BB) && FirstSpecialInsts[BB] == Inst)
-    FirstSpecialInsts.erase(BB);
+  if (FirstSpecialInsts.count(BB) && FirstSpecialInsts[BB] == Inst) {
+    if (Inst->isTerminator())
+      FirstSpecialInsts[BB] = nullptr;
+    else
+      FirstSpecialInsts[BB] = &*std::next(Inst->getIterator());
+  }
 }
 
 void InstructionPrecedenceTracking::removeUsersOf(const Instruction *Inst) {
   for (const auto *U : Inst->users()) {
     if (const auto *UI = dyn_cast<Instruction>(U))
       removeInstruction(UI);
   }
 }