[Dominators] Remove the DeferredDominance class

NutshellySima · NutshellySima · commit ce698a55866a · 2018-08-11T08:12:07.000Z
Summary: After converting all existing passes to use the new DomTreeUpdater interface, there isn't any usage of the original DeferredDominance class. Thus, we can safely remove it from the codebase. Reviewers: kuhar, brzycki, dmgreen, davide, grosser Reviewed By: kuhar, brzycki Subscribers: mgorny, llvm-commits Differential Revision: https://reviews.llvm.org/D49747 llvm-svn: 339502
diff --git a/llvm/include/llvm/IR/Dominators.h b/llvm/include/llvm/IR/Dominators.h
@@ -276,94 +276,6 @@ class DominatorTreeWrapperPass : public FunctionPass {
 
   void print(raw_ostream &OS, const Module *M = nullptr) const override;
 };
-
-//===-------------------------------------
-/// Class to defer updates to a DominatorTree.
-///
-/// Definition: Applying updates to every edge insertion and deletion is
-/// expensive and not necessary. When one needs the DominatorTree for analysis
-/// they can request a flush() to perform a larger batch update. This has the
-/// advantage of the DominatorTree inspecting the set of updates to find
-/// duplicates or unnecessary subtree updates.
-///
-/// The scope of DeferredDominance operates at a Function level.
-///
-/// It is not necessary for the user to scrub the updates for duplicates or
-/// updates that point to the same block (Delete, BB_A, BB_A). Performance
-/// can be gained if the caller attempts to batch updates before submitting
-/// to applyUpdates(ArrayRef) in cases where duplicate edge requests will
-/// occur.
-///
-/// It is required for the state of the LLVM IR to be applied *before*
-/// submitting updates. The update routines must analyze the current state
-/// between a pair of (From, To) basic blocks to determine if the update
-/// needs to be queued.
-/// Example (good):
-///     TerminatorInstructionBB->removeFromParent();
-///     DDT->deleteEdge(BB, Successor);
-/// Example (bad):
-///     DDT->deleteEdge(BB, Successor);
-///     TerminatorInstructionBB->removeFromParent();
-class DeferredDominance {
-public:
-  DeferredDominance(DominatorTree &DT_) : DT(DT_) {}
-
-  /// Queues multiple updates and discards duplicates.
-  void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates);
-
-  /// Helper method for a single edge insertion. It's almost always
-  /// better to batch updates and call applyUpdates to quickly remove duplicate
-  /// edges. This is best used when there is only a single insertion needed to
-  /// update Dominators.
-  void insertEdge(BasicBlock *From, BasicBlock *To);
-
-  /// Helper method for a single edge deletion. It's almost always better
-  /// to batch updates and call applyUpdates to quickly remove duplicate edges.
-  /// This is best used when there is only a single deletion needed to update
-  /// Dominators.
-  void deleteEdge(BasicBlock *From, BasicBlock *To);
-
-  /// Delays the deletion of a basic block until a flush() event.
-  void deleteBB(BasicBlock *DelBB);
-
-  /// Returns true if DelBB is awaiting deletion at a flush() event.
-  bool pendingDeletedBB(BasicBlock *DelBB);
-
-  /// Returns true if pending DT updates are queued for a flush() event.
-  bool pending();
-
-  /// Flushes all pending updates and block deletions. Returns a
-  /// correct DominatorTree reference to be used by the caller for analysis.
-  DominatorTree &flush();
-
-  /// Drops all internal state and forces a (slow) recalculation of the
-  /// DominatorTree based on the current state of the LLVM IR in F. This should
-  /// only be used in corner cases such as the Entry block of F being deleted.
-  void recalculate(Function &F);
-
-  /// Debug method to help view the state of pending updates.
-  LLVM_DUMP_METHOD void dump() const;
-
-private:
-  DominatorTree &DT;
-  SmallVector<DominatorTree::UpdateType, 16> PendUpdates;
-  SmallPtrSet<BasicBlock *, 8> DeletedBBs;
-
-  /// Apply an update (Kind, From, To) to the internal queued updates. The
-  /// update is only added when determined to be necessary. Checks for
-  /// self-domination, unnecessary updates, duplicate requests, and balanced
-  /// pairs of requests are all performed. Returns true if the update is
-  /// queued and false if it is discarded.
-  bool applyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From,
-                   BasicBlock *To);
-
-  /// Performs all pending basic block deletions. We have to defer the deletion
-  /// of these blocks until after the DominatorTree updates are applied. The
-  /// internal workings of the DominatorTree code expect every update's From
-  /// and To blocks to exist and to be a member of the same Function.
-  bool flushDelBB();
-};
-
 } // end namespace llvm
 
 #endif // LLVM_IR_DOMINATORS_H
diff --git a/llvm/lib/IR/Dominators.cpp b/llvm/lib/IR/Dominators.cpp
@@ -372,193 +372,3 @@ void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
   DT.print(OS);
 }
 
-//===----------------------------------------------------------------------===//
-//  DeferredDominance Implementation
-//===----------------------------------------------------------------------===//
-//
-// The implementation details of the DeferredDominance class which allows
-// one to queue updates to a DominatorTree.
-//
-//===----------------------------------------------------------------------===//
-
-/// Queues multiple updates and discards duplicates.
-void DeferredDominance::applyUpdates(
-    ArrayRef<DominatorTree::UpdateType> Updates) {
-  SmallVector<DominatorTree::UpdateType, 8> Seen;
-  for (auto U : Updates)
-    // Avoid duplicates to applyUpdate() to save on analysis.
-    if (std::none_of(Seen.begin(), Seen.end(),
-                     [U](DominatorTree::UpdateType S) { return S == U; })) {
-      Seen.push_back(U);
-      applyUpdate(U.getKind(), U.getFrom(), U.getTo());
-    }
-}
-
-/// Helper method for a single edge insertion. It's almost always better
-/// to batch updates and call applyUpdates to quickly remove duplicate edges.
-/// This is best used when there is only a single insertion needed to update
-/// Dominators.
-void DeferredDominance::insertEdge(BasicBlock *From, BasicBlock *To) {
-  applyUpdate(DominatorTree::Insert, From, To);
-}
-
-/// Helper method for a single edge deletion. It's almost always better
-/// to batch updates and call applyUpdates to quickly remove duplicate edges.
-/// This is best used when there is only a single deletion needed to update
-/// Dominators.
-void DeferredDominance::deleteEdge(BasicBlock *From, BasicBlock *To) {
-  applyUpdate(DominatorTree::Delete, From, To);
-}
-
-/// Delays the deletion of a basic block until a flush() event.
-void DeferredDominance::deleteBB(BasicBlock *DelBB) {
-  assert(DelBB && "Invalid push_back of nullptr DelBB.");
-  assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
-  // DelBB is unreachable and all its instructions are dead.
-  while (!DelBB->empty()) {
-    Instruction &I = DelBB->back();
-    // Replace used instructions with an arbitrary value (undef).
-    if (!I.use_empty())
-      I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
-    DelBB->getInstList().pop_back();
-  }
-  // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
-  // Child of Function F it must contain valid IR.
-  new UnreachableInst(DelBB->getContext(), DelBB);
-  DeletedBBs.insert(DelBB);
-}
-
-/// Returns true if DelBB is awaiting deletion at a flush() event.
-bool DeferredDominance::pendingDeletedBB(BasicBlock *DelBB) {
-  if (DeletedBBs.empty())
-    return false;
-  return DeletedBBs.count(DelBB) != 0;
-}
-
-/// Returns true if pending DT updates are queued for a flush() event.
-bool DeferredDominance::pending() { return !PendUpdates.empty(); }
-
-/// Flushes all pending updates and block deletions. Returns a
-/// correct DominatorTree reference to be used by the caller for analysis.
-DominatorTree &DeferredDominance::flush() {
-  // Updates to DT must happen before blocks are deleted below. Otherwise the
-  // DT traversal will encounter badref blocks and assert.
-  if (!PendUpdates.empty()) {
-    DT.applyUpdates(PendUpdates);
-    PendUpdates.clear();
-  }
-  flushDelBB();
-  return DT;
-}
-
-/// Drops all internal state and forces a (slow) recalculation of the
-/// DominatorTree based on the current state of the LLVM IR in F. This should
-/// only be used in corner cases such as the Entry block of F being deleted.
-void DeferredDominance::recalculate(Function &F) {
-  // flushDelBB must be flushed before the recalculation. The state of the IR
-  // must be consistent before the DT traversal algorithm determines the
-  // actual DT.
-  if (flushDelBB() || !PendUpdates.empty()) {
-    DT.recalculate(F);
-    PendUpdates.clear();
-  }
-}
-
-/// Debug method to help view the state of pending updates.
-#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-LLVM_DUMP_METHOD void DeferredDominance::dump() const {
-  raw_ostream &OS = llvm::dbgs();
-  OS << "PendUpdates:\n";
-  int I = 0;
-  for (auto U : PendUpdates) {
-    OS << "  " << I << " : ";
-    ++I;
-    if (U.getKind() == DominatorTree::Insert)
-      OS << "Insert, ";
-    else
-      OS << "Delete, ";
-    BasicBlock *From = U.getFrom();
-    if (From) {
-      auto S = From->getName();
-      if (!From->hasName())
-        S = "(no name)";
-      OS << S << "(" << From << "), ";
-    } else {
-      OS << "(badref), ";
-    }
-    BasicBlock *To = U.getTo();
-    if (To) {
-      auto S = To->getName();
-      if (!To->hasName())
-        S = "(no_name)";
-      OS << S << "(" << To << ")\n";
-    } else {
-      OS << "(badref)\n";
-    }
-  }
-  OS << "DeletedBBs:\n";
-  I = 0;
-  for (auto BB : DeletedBBs) {
-    OS << "  " << I << " : ";
-    ++I;
-    if (BB->hasName())
-      OS << BB->getName() << "(";
-    else
-      OS << "(no_name)(";
-    OS << BB << ")\n";
-  }
-}
-#endif
-
-/// Apply an update (Kind, From, To) to the internal queued updates. The
-/// update is only added when determined to be necessary. Checks for
-/// self-domination, unnecessary updates, duplicate requests, and balanced
-/// pairs of requests are all performed. Returns true if the update is
-/// queued and false if it is discarded.
-bool DeferredDominance::applyUpdate(DominatorTree::UpdateKind Kind,
-                                    BasicBlock *From, BasicBlock *To) {
-  if (From == To)
-    return false; // Cannot dominate self; discard update.
-
-  // Discard updates by inspecting the current state of successors of From.
-  // Since applyUpdate() must be called *after* the Terminator of From is
-  // altered we can determine if the update is unnecessary.
-  bool HasEdge = std::any_of(succ_begin(From), succ_end(From),
-                             [To](BasicBlock *B) { return B == To; });
-  if (Kind == DominatorTree::Insert && !HasEdge)
-    return false; // Unnecessary Insert: edge does not exist in IR.
-  if (Kind == DominatorTree::Delete && HasEdge)
-    return false; // Unnecessary Delete: edge still exists in IR.
-
-  // Analyze pending updates to determine if the update is unnecessary.
-  DominatorTree::UpdateType Update = {Kind, From, To};
-  DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
-                                          ? DominatorTree::Insert
-                                          : DominatorTree::Delete,
-                                      From, To};
-  for (auto I = PendUpdates.begin(), E = PendUpdates.end(); I != E; ++I) {
-    if (Update == *I)
-      return false; // Discard duplicate updates.
-    if (Invert == *I) {
-      // Update and Invert are both valid (equivalent to a no-op). Remove
-      // Invert from PendUpdates and discard the Update.
-      PendUpdates.erase(I);
-      return false;
-    }
-  }
-  PendUpdates.push_back(Update); // Save the valid update.
-  return true;
-}
-
-/// Performs all pending basic block deletions. We have to defer the deletion
-/// of these blocks until after the DominatorTree updates are applied. The
-/// internal workings of the DominatorTree code expect every update's From
-/// and To blocks to exist and to be a member of the same Function.
-bool DeferredDominance::flushDelBB() {
-  if (DeletedBBs.empty())
-    return false;
-  for (auto *BB : DeletedBBs)
-    BB->eraseFromParent();
-  DeletedBBs.clear();
-  return true;
-}
diff --git a/llvm/unittests/IR/CMakeLists.txt b/llvm/unittests/IR/CMakeLists.txt
@@ -15,7 +15,6 @@ add_llvm_unittest(IRTests
   ConstantsTest.cpp
   DebugInfoTest.cpp
   DebugTypeODRUniquingTest.cpp
-  DeferredDominanceTest.cpp
   DominatorTreeTest.cpp
   DominatorTreeBatchUpdatesTest.cpp
   DomTreeUpdaterTest.cpp
diff --git a/llvm/unittests/IR/DeferredDominanceTest.cpp b/llvm/unittests/IR/DeferredDominanceTest.cpp
