1 files changed, 188 insertions, 0 deletions
diff --git a/llvm/lib/IR/Dominators.cpp b/llvm/lib/IR/Dominators.cpp
index ad448a3f240..e44e845b324 100644
--- a/llvm/lib/IR/Dominators.cpp
+++ b/llvm/lib/IR/Dominators.cpp
@@ -18,6 +18,7 @@
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/IR/CFG.h"
+#include "llvm/IR/Constants.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/CommandLine.h"
@@ -389,3 +390,190 @@ 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.
+//
+//===----------------------------------------------------------------------===//
+
+/// \brief 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());
+    }
+}
+
+/// \brief 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);
+}
+
+/// \brief 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);
+}
+
+/// \brief 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);
+}
+
+/// \brief 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;
+}
+
+/// \brief 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;
+}
+
+/// \brief 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();
+  }
+}
+
+/// \brief 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;
+}