[WIP!][DomTreeUpdater/Auto[3]] A new Auto UpdateStrategy candidate

[NutshellySima]

Summary

This patch is a work-in-process and I don't intend to commit it. If you are automatically subscribed to this patch, please ignore it.

This patch is the most promising one of the Auto UpdateStrategy implementations.

This patch is an approach to solve the problems in the current DomTreeUpdater and JumpThreading pass. (We need to figure out the previous state of the CFG when we call applyUpdates()/insertEdge()/deleteEdge() or we need to concern about the internal state of the DomTreeUpdater). It shows a similar performance on bitcode files with the current DomTreeUpdater working under Lazy UpdateStrategy after converting CorrelatedValuePropagation/RewriteStatepointsForGC/JumpThreading and testing under the -O3 pipeline.
This patch implements the Auto UpdateStrategy by getting a snapshot of the single from point if it didn't get one when user calls DTU.isAboutToChange(). Then use the information submitted by users (especially the From points) to narrow down the changes needs to be applied. When a flush() happens, it diffs the narrowed down range of points, thus it shows a rather good performance in line with the current one.

[NutshellySima]

Benchmark results on Auto UpdateStrategy 3:
https://reviews.llvm.org/P8101

[NutshellySima]

Close this revision because D58170 is landed.
D58170 provides a cleaner interface than the Auto[3] strategy here as it does not require users to add extra functions calls before CFG changes. Moreover, it doesn't suffer from potential performance issues presented in Auto* implementations.

include/llvm/IR/DomTreeUpdater.h

 // This file defines the DomTreeUpdater class, which provides a uniform way to
 // update dominator tree related data structures.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DOMTREEUPDATER_H
 #define LLVM_DOMTREEUPDATER_H
 
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/GenericDomTree.h"
 #include <functional>
+#include <utility>
 #include <vector>
 
 namespace llvm {
 class DomTreeUpdater {
 public:
-  enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 };
+  enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1, Auto = 2 };
 
   explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {}
   DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_)
-      : DT(&DT_), Strategy(Strategy_) {}
+      : DT(&DT_), Strategy(Strategy_) {
+    if (isAuto())
+      snapshotCFG(SnapshotedCFG);
+  }
   DomTreeUpdater(DominatorTree *DT_, UpdateStrategy Strategy_)
-      : DT(DT_), Strategy(Strategy_) {}
+      : DT(DT_), Strategy(Strategy_) {
+    if (isAuto())
+      snapshotCFG(SnapshotedCFG);
+  }
   DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_)
-      : PDT(&PDT_), Strategy(Strategy_) {}
+      : PDT(&PDT_), Strategy(Strategy_) {
+    if (isAuto())
+      snapshotCFG(SnapshotedCFG);
+  }
   DomTreeUpdater(PostDominatorTree *PDT_, UpdateStrategy Strategy_)
-      : PDT(PDT_), Strategy(Strategy_) {}
+      : PDT(PDT_), Strategy(Strategy_) {
+    if (isAuto())
+      snapshotCFG(SnapshotedCFG);
+  }
   DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_,
                  UpdateStrategy Strategy_)
-      : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {}
+      : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {
+    if (isAuto())
+      snapshotCFG(SnapshotedCFG);
+  }
   DomTreeUpdater(DominatorTree *DT_, PostDominatorTree *PDT_,
                  UpdateStrategy Strategy_)
-      : DT(DT_), PDT(PDT_), Strategy(Strategy_) {}
+      : DT(DT_), PDT(PDT_), Strategy(Strategy_) {
+    if (isAuto())
+      snapshotCFG(SnapshotedCFG);
+  }
 
-  ~DomTreeUpdater() { flush(); }
+  ~DomTreeUpdater() {
+    if (isAuto())
+      assert(PendUpdates.empty());
+    flush();
+  }
 
   /// Returns true if the current strategy is Lazy.
-  bool isLazy() const { return Strategy == UpdateStrategy::Lazy; };
+  bool isLazy() const { return Strategy != UpdateStrategy::Eager; };
 
   /// Returns true if the current strategy is Eager.
   bool isEager() const { return Strategy == UpdateStrategy::Eager; };
 
   /// Returns true if it holds a DominatorTree.
   bool hasDomTree() const { return DT != nullptr; }
 
   /// Returns true if it holds a PostDominatorTree.
private:
 
   /// Returns true if the update appears in the LLVM IR.
   /// It is used to check whether an update is valid in
   /// insertEdge/deleteEdge or is unnecessary in the batch update.
   bool isUpdateValid(DominatorTree::UpdateType Update) const;
 
   /// Returns true if the update is self dominance.
   bool isSelfDominance(DominatorTree::UpdateType Update) const;
+
+  // Auto
+
+  // <From, Set<To>>
+  using CFG = DenseMap<BasicBlock *, DenseSet<BasicBlock *>>;
+
+  void snapshotCFG(CFG &Graph);
+
+  std::vector<DominatorTree::UpdateType> diffCFG();
+
+  bool isAuto() const { return Strategy == UpdateStrategy::Auto; }
+
+  DenseSet<BasicBlock *> getNewCFG(BasicBlock *BB);
+
+  void applyAutoUpdates();
+
+  DenseSet<BasicBlock *> CFGPoints;
+
+  CFG SnapshotedCFG;
+  BasicBlock *SnapshotedBB = nullptr;
+  Function *Func = nullptr;
+  bool NeedCalculate = false;
+
+  // Store <From, Set<To>>
+  DenseMap<BasicBlock *, DenseSet<BasicBlock *>> PendEdges;
+
+public:
+  /// Submit before the CFG change on which From point
+  /// is going to change.
+  void isAboutToChange(BasicBlock *BB);
 };
 } // namespace llvm
 
 #endif // LLVM_DOMTREEUPDATER_H

lib/IR/DomTreeUpdater.cpp

 #include "llvm/Support/GenericDomTree.h"
 #include <algorithm>
 #include <functional>
 
 namespace llvm {
 
 bool DomTreeUpdater::isUpdateValid(
     const DominatorTree::UpdateType Update) const {
+#ifdef NDEBUG
+  assert(!isAuto());
+#endif
   const auto *From = Update.getFrom();
   const auto *To = Update.getTo();
   const auto Kind = Update.getKind();
 
   // Discard updates by inspecting the current state of successors of From.
   // Since isUpdateValid() must be called *after* the Terminator of From is
   // altered we can determine if the update is unnecessary for batch updates
   // or invalid for a single update.
#endif
 
   // Edge exists in IR.
   if (Kind == DominatorTree::Delete && HasEdge)
     return false;
 
   return true;
 }
 
+DenseSet<BasicBlock *> DomTreeUpdater::getNewCFG(llvm::BasicBlock *BB) {
+  DenseSet<BasicBlock *> Ret;
+  for (auto *Addr : successors(BB))
+    Ret.insert(Addr);
+  return Ret;
+}
+
+void DomTreeUpdater::isAboutToChange(BasicBlock *BB) {
+  if (!isAuto())
+    return;
+  if (!DT && !PDT)
+    return;
+  // Have snapshoted.
+  if (SnapshotedCFG.find(BB) != SnapshotedCFG.end()) {
+    return;
+  }
+  // It is a new BB.
+  if (CFGPoints.find(BB) == CFGPoints.end()) {
+    return;
+  }
+  SnapshotedCFG[BB] = getNewCFG(BB);
+}
+
+std::vector<DominatorTree::UpdateType> DomTreeUpdater::diffCFG() {
+
+  std::vector<DominatorTree::UpdateType> Updates;
+
+  for (const auto &Edge : PendEdges) {
+    if (SnapshotedCFG.find(Edge.first) == SnapshotedCFG.end())
+      if (CFGPoints.find(Edge.first) != CFGPoints.end())
+        continue;
+    CFGPoints.insert(Edge.first);
+    auto &PrevCFG = SnapshotedCFG[Edge.first];
+    auto NewCFG = getNewCFG(Edge.first);
+    for (auto &Update : Edge.second) {
+      bool ExistinNew = NewCFG.find(Update) != NewCFG.end();
+      bool ExistinOld = PrevCFG.find(Update) != PrevCFG.end();
+      if (ExistinNew == ExistinOld)
+        continue;
+      if (ExistinNew)
+        Updates.push_back({DominatorTree::Insert, Edge.first, Update});
+      else
+        Updates.push_back({DominatorTree::Delete, Edge.first, Update});
+    }
+    SnapshotedCFG[Edge.first] = std::move(NewCFG);
+  }
+
+  PendEdges.clear();
+  NeedCalculate = false;
+
+  return Updates;
+}
+
+void DomTreeUpdater::snapshotCFG(CFG &Graph) {
+  if (!DT && !PDT)
+    return;
+
+  Graph.clear();
+
+  if (!Func) {
+    if (DT)
+      Func = DT->getRoot()->getParent();
+    else if (PDT)
+      Func = PDT->getRoot()->getParent();
+  }
+
+  SnapshotedBB = &Func->getEntryBlock();
+
+  CFGPoints.clear();
+  for (auto &BB : Func->getBasicBlockList())
+    CFGPoints.insert(&BB);
+}
+
 bool DomTreeUpdater::isSelfDominance(
     const DominatorTree::UpdateType Update) const {
   // Won't affect DomTree and PostDomTree.
   return Update.getFrom() == Update.getTo();
 }
 
 bool DomTreeUpdater::applyLazyUpdate(DominatorTree::UpdateKind Kind,
                                      BasicBlock *From, BasicBlock *To) {
if (hasPendingDomTreeUpdates()) {
     const auto E = PendUpdates.end();
     assert(I < E && "Iterator range invalid; there should be DomTree updates.");
     DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
     PendDTUpdateIndex = PendUpdates.size();
   }
 }
 
 void DomTreeUpdater::flush() {
+  if (!isAuto()) {
     applyDomTreeUpdates();
     applyPostDomTreeUpdates();
+  } else
+    applyAutoUpdates();
   dropOutOfDateUpdates();
 }
 
 void DomTreeUpdater::applyPostDomTreeUpdates() {
   // No pending PostDomTreeUpdates.
   if (Strategy != UpdateStrategy::Lazy || !PDT)
     return;
 
void DomTreeUpdater::recalculate(Function &F) {
   // Lazy UpdateStrategy so we recalculate available trees immediately.
 
   // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
   IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
 
   // Because all trees are going to be up-to-date after recalculation,
   // flush awaiting deleted BasicBlocks.
   forceFlushDeletedBB();
+  if (isAuto()) {
+    if (SnapshotedBB == &Func->getEntryBlock()) {
+      NeedCalculate = true;
+      IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
+      applyAutoUpdates();
+      return;
+    }
+  }
+
   if (DT)
     DT->recalculate(F);
   if (PDT)
     PDT->recalculate(F);
 
   // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
   IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
+  if (!isAuto())
     PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
   dropOutOfDateUpdates();
+
+  if (isAuto()) {
+    snapshotCFG(SnapshotedCFG);
+    PendEdges.clear();
+    NeedCalculate = false;
+  }
 }
 
 bool DomTreeUpdater::hasPendingUpdates() const {
   return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
 }
 
 bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
   if (!DT)
     return false;
+
+  if (isAuto()) {
+    if (NeedCalculate)
+      return true;
+
+    return false;
+  }
+
   return PendUpdates.size() != PendDTUpdateIndex;
 }
 
 bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const {
   if (!PDT)
     return false;
+
+  if (isAuto()) {
+    if (NeedCalculate)
+      return true;
+
+    return false;
+  }
+
   return PendUpdates.size() != PendPDTUpdateIndex;
 }
 
 bool DomTreeUpdater::isBBPendingDeletion(llvm::BasicBlock *DelBB) const {
   if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
     return false;
   return DeletedBBs.count(DelBB) != 0;
 }
 
 // The DT and PDT require the nodes related to updates
 // are not deleted when update functions are called.
 // So BasicBlock deletions must be pended when the
 // UpdateStrategy is Lazy. When the UpdateStrategy is
 // Eager, the BasicBlock will be deleted immediately.
 void DomTreeUpdater::deleteBB(BasicBlock *DelBB) {
   validateDeleteBB(DelBB);
-  if (Strategy == UpdateStrategy::Lazy) {
+  if (isLazy()) {
     DeletedBBs.insert(DelBB);
     return;
   }
 
   DelBB->removeFromParent();
   eraseDelBBNode(DelBB);
   delete DelBB;
 }
 
 void DomTreeUpdater::callbackDeleteBB(
     BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
   validateDeleteBB(DelBB);
-  if (Strategy == UpdateStrategy::Lazy) {
+  if (isLazy()) {
     Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
     DeletedBBs.insert(DelBB);
     return;
   }
 
   DelBB->removeFromParent();
   eraseDelBBNode(DelBB);
   Callback(DelBB);
   delete DelBB;
 }
 
 void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) {
   if (DT && !IsRecalculatingDomTree)
     if (DT->getNode(DelBB))
       DT->eraseNode(DelBB);
 
   if (PDT && !IsRecalculatingPostDomTree)
     if (PDT->getNode(DelBB))
       PDT->eraseNode(DelBB);
+
+  // Delete this FromBB in case of memory leak.
+  if (isAuto())
+    SnapshotedCFG.erase(DelBB);
+
+  CFGPoints.erase(DelBB);
 }
 
 void DomTreeUpdater::validateDeleteBB(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);
 }
 
 void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
                                   bool ForceRemoveDuplicates) {
   if (!DT && !PDT)
     return;
 
+  if (isAuto()) {
+
+    if (Updates.empty())
+      return;
+
+    bool Changed = false;
+    for (auto &Update : Updates) {
+      if (Update.getFrom() != Update.getTo()) {
+        PendEdges[Update.getFrom()].insert(Update.getTo());
+        Changed = true;
+      }
+    }
+    NeedCalculate |= Changed;
+    return;
+  }
+
   if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) {
     SmallVector<DominatorTree::UpdateType, 8> Seen;
     for (const auto U : Updates)
       // For Lazy UpdateStrategy, avoid duplicates to applyLazyUpdate() to save
       // on analysis.
       if (llvm::none_of(
               Seen,
               [U](const DominatorTree::UpdateType S) { return S == U; }) &&
void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
   if (DT)
     DT->applyUpdates(Updates);
   if (PDT)
     PDT->applyUpdates(Updates);
 }
 
 DominatorTree &DomTreeUpdater::getDomTree() {
   assert(DT && "Invalid acquisition of a null DomTree");
+  if (!isAuto())
     applyDomTreeUpdates();
+  else
+    applyAutoUpdates();
   dropOutOfDateUpdates();
   return *DT;
 }
 
 PostDominatorTree &DomTreeUpdater::getPostDomTree() {
   assert(PDT && "Invalid acquisition of a null PostDomTree");
+  if (!isAuto())
     applyPostDomTreeUpdates();
+  else
+    applyAutoUpdates();
   dropOutOfDateUpdates();
   return *PDT;
 }
 
 void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) {
 
 #ifndef NDEBUG
   assert(isUpdateValid({DominatorTree::Insert, From, To}) &&
          "Inserted edge does not appear in the CFG");
 #endif
 
   if (!DT && !PDT)
     return;
 
   // Won't affect DomTree and PostDomTree; discard update.
   if (From == To)
     return;
 
+  if (isAuto()) {
+    NeedCalculate = true;
+    PendEdges[From].insert(To);
+    return;
+  }
+
   if (Strategy == UpdateStrategy::Eager) {
     if (DT)
       DT->insertEdge(From, To);
     if (PDT)
       PDT->insertEdge(From, To);
     return;
   }
 
   applyLazyUpdate(DominatorTree::Insert, From, To);
 }
 
 void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
   if (From == To)
     return;
 
   if (!DT && !PDT)
     return;
 
-  if (!isUpdateValid({DominatorTree::Insert, From, To}))
+  if (isAuto()) {
+    NeedCalculate = true;
+    PendEdges[From].insert(To);
     return;
+  }
+
+  if (!isUpdateValid({DominatorTree::Insert, From, To})) {
+    return;
+  }
 
   if (Strategy == UpdateStrategy::Eager) {
     if (DT)
       DT->insertEdge(From, To);
     if (PDT)
       PDT->insertEdge(From, To);
     return;
   }
#endif
 
   if (!DT && !PDT)
     return;
 
   // Won't affect DomTree and PostDomTree; discard update.
   if (From == To)
     return;
 
+  if (isAuto()) {
+    NeedCalculate = true;
+    PendEdges[From].insert(To);
+    return;
+  }
+
   if (Strategy == UpdateStrategy::Eager) {
     if (DT)
       DT->deleteEdge(From, To);
     if (PDT)
       PDT->deleteEdge(From, To);
     return;
   }
 
   applyLazyUpdate(DominatorTree::Delete, From, To);
 }
 
 void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
   if (From == To)
     return;
 
   if (!DT && !PDT)
     return;
 
-  if (!isUpdateValid({DominatorTree::Delete, From, To}))
+  if (isAuto()) {
+    NeedCalculate = true;
+    PendEdges[From].insert(To);
+    return;
+  }
+
+  if (!isUpdateValid({DominatorTree::Delete, From, To})) {
     return;
+  }
 
   if (Strategy == UpdateStrategy::Eager) {
     if (DT)
       DT->deleteEdge(From, To);
     if (PDT)
       PDT->deleteEdge(From, To);
     return;
   }
 
   applyLazyUpdate(DominatorTree::Delete, From, To);
 }
 
 void DomTreeUpdater::dropOutOfDateUpdates() {
   if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
     return;
 
   tryFlushDeletedBB();
 
+  // Early return in Auto mode.
+  if (isAuto())
+    return;
+
   // Drop all updates applied by both trees.
   if (!DT)
     PendDTUpdateIndex = PendUpdates.size();
   if (!PDT)
     PendPDTUpdateIndex = PendUpdates.size();
 
   const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
   const auto B = PendUpdates.begin();
for (auto BB : Callbacks) {
     if (BB->hasName())
       OS << BB->getName() << "(";
     else
       OS << "(no_name)(";
     OS << BB << ")\n";
   }
 }
 #endif
+
+void DomTreeUpdater::applyAutoUpdates() {
+  if (!DT && !PDT)
+    return;
+
+  if (!NeedCalculate)
+    return;
+
+  if (SnapshotedBB != &Func->getEntryBlock()) {
+    // recalculate() will snapshot and reset NeedCalculate.
+    recalculate(*Func);
+    return;
+  }
+
+  // diffCFG will reset NeedCalculate.
+  auto Updates = diffCFG();
+  if (DT)
+    DT->applyUpdates(Updates);
+  if (PDT)
+    PDT->applyUpdates(Updates);
+}
 } // namespace llvm

unittests/IR/DomTreeUpdaterTest.cpp

TEST(DomTreeUpdater, LazyUpdateDTBasicOperations) {
   Function::iterator FI = F->begin();
   BasicBlock *BB0 = &*FI++;
   BasicBlock *BB1 = &*FI++;
   BasicBlock *BB2 = &*FI++;
   BasicBlock *BB3 = &*FI++;
 
   // Test discards of self-domination update.
   DTU.deleteEdge(BB0, BB0);
-  ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
+  // ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
 
   // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
   // entries are discarded.
   std::vector<DominatorTree::UpdateType> Updates;
   Updates.reserve(4);
   Updates.push_back({DominatorTree::Delete, BB0, BB3});
   Updates.push_back({DominatorTree::Delete, BB0, BB3});
 
TEST(DomTreeUpdater, LazyUpdateBasicOperations) {
   EXPECT_EQ(BB3->getParent(), F);
 
   // Verify. Updates to DTU must be applied *after* all changes to the CFG
   // (including block deletion).
   DTU.applyUpdates(Updates);
   ASSERT_TRUE(DTU.getDomTree().verify());
   ASSERT_TRUE(DTU.hasPendingUpdates());
   ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates());
-  ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
-  ASSERT_TRUE(DTU.hasPendingDeletedBB());
+  // ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
+  // ASSERT_TRUE(DTU.hasPendingDeletedBB());
   ASSERT_TRUE(DTU.getPostDomTree().verify());
-  ASSERT_FALSE(DTU.hasPendingUpdates());
-  ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());
-  ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
-  ASSERT_FALSE(DTU.hasPendingDeletedBB());
+  // ASSERT_FALSE(DTU.hasPendingUpdates());
+  // ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());
+  // ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
+  // ASSERT_FALSE(DTU.hasPendingDeletedBB());
   ASSERT_EQ(CallbackFlag, true);
 }
 
 TEST(DomTreeUpdater, LazyUpdateReplaceEntryBB) {
   StringRef FuncName = "f";
   StringRef ModuleString = R"(
                            define i32 @f() {
                            bb0: