From 3781a46c3c70a83b2a5312aa358512578e87b9ca Mon Sep 17 00:00:00 2001
From: Arthur Eubanks <aeubanks@google.com>
Date: Thu, 21 Oct 2021 10:48:41 -0700
Subject: [PATCH] Revert "[IPT] Restructure cache to allow lazy update
 following invalidation [NFC]"

This reverts commit baea663a6e9bc52f80995d02bb8149934c825612.

Causes crashes, e.g. https://lab.llvm.org/buildbot/#/builders/77/builds/10715.
---
 .../llvm/Analysis/InstructionPrecedenceTracking.h  | 11 ++--
 .../lib/Analysis/InstructionPrecedenceTracking.cpp | 61 +++++++++-------------
 2 files changed, 32 insertions(+), 40 deletions(-)

diff --git a/llvm/include/llvm/Analysis/InstructionPrecedenceTracking.h b/llvm/include/llvm/Analysis/InstructionPrecedenceTracking.h
index cf997f0..192630e 100644
--- a/llvm/include/llvm/Analysis/InstructionPrecedenceTracking.h
+++ b/llvm/include/llvm/Analysis/InstructionPrecedenceTracking.h
@@ -28,13 +28,14 @@ class BasicBlock;
 class Instruction;
 
 class InstructionPrecedenceTracking {
-  // 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.
+  // 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.
   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
diff --git a/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp b/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp
index 850ccac..9fee57c 100644
--- a/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp
+++ b/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp
@@ -47,29 +47,11 @@ const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction(
     validate(BB);
 #endif
 
-  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;
-    }
-    // Mark this block as having no special instructions.
-    return nullptr;
-  }();
-
-  FirstSpecialInsts[BB] = Res;
-  return Res;
+  if (FirstSpecialInsts.find(BB) == FirstSpecialInsts.end()) {
+    fill(BB);
+    assert(FirstSpecialInsts.find(BB) != FirstSpecialInsts.end() && "Must be!");
+  }
+  return FirstSpecialInsts[BB];
 }
 
 bool InstructionPrecedenceTracking::hasSpecialInstructions(
@@ -84,6 +66,20 @@ bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(
   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);
@@ -91,13 +87,12 @@ void InstructionPrecedenceTracking::validate(const BasicBlock *BB) const {
   if (It == FirstSpecialInsts.end())
     return;
 
-  for (const Instruction &I : *BB) {
-    if (&I == It->second)
-      // No special instruction before cached result
+  for (const Instruction &Insn : *BB)
+    if (isSpecialInstruction(&Insn)) {
+      assert(It->second == &Insn &&
+             "Cached first special instruction is wrong!");
       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 "
@@ -120,12 +115,8 @@ void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst,
 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) {
-    if (Inst->isTerminator())
-      FirstSpecialInsts[BB] = nullptr;
-    else
-      FirstSpecialInsts[BB] = &*std::next(Inst->getIterator());
-  }
+  if (FirstSpecialInsts.count(BB) && FirstSpecialInsts[BB] == Inst)
+    FirstSpecialInsts.erase(BB);
 }
 
 void InstructionPrecedenceTracking::removeUsersOf(const Instruction *Inst) {
-- 
2.7.4