[DSE] Preserve basic block ordering using OrderedBasicBlock.

By extending OrderedBB to allow removing and replacing cached
instructions, we can preserve OrderedBBs in DSE easily. This eliminates
one source of quadratic compile time in DSE.

Fixes PR38829.

Reviewers: rnk, efriedma, hfinkel

Reviewed By: efriedma

Differential Revision: https://reviews.llvm.org/D59789

llvm-svn: 357208

1 files changed, 23 insertions, 0 deletions

diff --git a/llvm/lib/Analysis/OrderedBasicBlock.cpp b/llvm/lib/Analysis/OrderedBasicBlock.cpp
index 3cc6319..ad80a66 100644
--- a/llvm/lib/Analysis/OrderedBasicBlock.cpp
+++ b/llvm/lib/Analysis/OrderedBasicBlock.cpp
@@ -85,3 +85,26 @@ bool OrderedBasicBlock::dominates(const Instruction *A, const Instruction *B) {
 
   return comesBefore(A, B);
 }
+
+void OrderedBasicBlock::eraseInstruction(const Instruction *I) {
+  if (LastInstFound != BB->end() && I == &*LastInstFound) {
+    if (LastInstFound == BB->begin())
+      LastInstFound = BB->end();
+    else
+      LastInstFound--;
+  }
+
+  NumberedInsts.erase(I);
+}
+
+void OrderedBasicBlock::replaceInstruction(const Instruction *Old,
+                                           const Instruction *New) {
+  auto OI = NumberedInsts.find(Old);
+  if (OI == NumberedInsts.end())
+    return;
+
+  NumberedInsts[New] = OI->second;
+  if (LastInstFound != BB->end() && Old == &*LastInstFound)
+    LastInstFound = New->getIterator();
+  NumberedInsts.erase(Old);
+}