[WIP!][DomTreeUpdater/Auto[2]] 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 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 most of the times on bitcode files with the current DomTreeUpdater working under Lazy UpdateStrategy after converting CorrelatedValuePropagation/RewriteStatepointsForGC/JumpThreading and testing under the -O3 pipeline. But it also suffers a performance degradation sometimes which is caused by 1. the LazyValueInfo relies on whether the DominatorTree is up to date to perform queries and the new Auto UpdateStrategy reports up-to-date less than the Lazy UpdateStrategy (this issue needs to inspect further); 2. some Function contains a lot of BasicBlock which causes snapshotting really slow. (we can use some other compilers like rustc which emits a lot of BasicBlocks to test it).

This patch implements the Auto UpdateStrategy by getting a full snapshot the first time DomTreeUpdater is initialized. Then use the information submitted by users (especially the From points) to avoid full snapshot later. Because the JumpThreading pass always calls DTU.recalculate(F) deep in the MergeBasicBlockIntoOnlyPred in Local.cpp, so though this implementation is theoretically faster than D50302, the result of benchmark don't show great difference.

[NutshellySima]

Some benchmarks on Auto UpdateStrategy 2:
https://reviews.llvm.org/P8100

[NutshellySima]

Close this revision because D58170 is landed. D58170 solves the problem this patch trying to resolve.
It also improves the implementation of deduplication, which only takes 0.31s when it deduplicates and validates updates when optimizing clang-5.0.0.bc, while this patch takes 14 seconds to snapshot the CFG.

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/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, <isSorted, To>>
+  using CFG =
+      DenseMap<BasicBlock *, std::pair<bool, std::vector<BasicBlock *>>>;
+  /// Fully snapshot the current CFG; it should only
+  /// be used after recalculation or in the construction
+  /// of the DomTreeUpdater.
+  void snapshotCFG(CFG &Graph);
+
+  /// Return a vector of updates based on the previous CFG in
+  /// SnapshotedCFG. It can automatically gets the diffed CFG
+  /// based on users input of the From points.
+  std::vector<DominatorTree::UpdateType> diffCFG();
+
+  bool isAuto() const { return Strategy == UpdateStrategy::Auto; }
+
+  void applyAutoUpdates();
+
+  CFG SnapshotedCFG;
+  BasicBlock *SnapshotedBB = nullptr;
+  Function *Func = nullptr;
+  bool NeedCalculate = false;
+  // Here we save all the From points users provide.
+  SmallPtrSet<BasicBlock *, 32> PendPoints;
 };
 } // 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;
 }
 
+std::vector<DominatorTree::UpdateType> DomTreeUpdater::diffCFG() {
+
+  auto getNewCFG = [&](BasicBlock *BB) {
+    std::vector<BasicBlock *> Ret;
+    Ret.reserve(succ_size(BB));
+    for (auto *Addr : successors(BB))
+      Ret.push_back(Addr);
+    llvm::sort(Ret.begin(), Ret.end());
+    Ret.erase(std::unique(Ret.begin(), Ret.end()), Ret.end());
+    return Ret;
+  };
+
+  std::vector<DominatorTree::UpdateType> Updates;
+  std::vector<BasicBlock *> DiffCFG;
+
+  for (const auto &Point : PendPoints) {
+    auto &Val = SnapshotedCFG[Point];
+    if (!Val.first) {
+      llvm::sort(Val.second.begin(), Val.second.end());
+      Val.second.erase(std::unique(Val.second.begin(), Val.second.end()),
+                       Val.second.end());
+    }
+    auto &PrevCFG = Val.second;
+    auto NewCFG = getNewCFG(Point);
+    std::set_difference(PrevCFG.begin(), PrevCFG.end(), NewCFG.begin(),
+                        NewCFG.end(), std::inserter(DiffCFG, DiffCFG.begin()));
+    // Deleted Edges
+    for (auto &Edge : DiffCFG)
+      if (Point != Edge)
+        Updates.push_back({DominatorTree::Delete, Point, Edge});
+    DiffCFG.clear();
+    std::set_difference(NewCFG.begin(), NewCFG.end(), PrevCFG.begin(),
+                        PrevCFG.end(), std::inserter(DiffCFG, DiffCFG.begin()));
+    // Inserted Edges
+    for (auto &Edge : DiffCFG)
+      if (Point != Edge)
+        Updates.push_back({DominatorTree::Insert, Point, Edge});
+    Val.first = true; // Sorted.
+    Val.second = std::move(NewCFG);
+    DiffCFG.clear();
+  }
+
+  PendPoints.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();
+
+  for (BasicBlock &BB : Func->getBasicBlockList()) {
+    Graph[&BB].first = false; // Not sorted.
+    auto &I = Graph[&BB].second;
+    I.reserve(succ_size(&BB));
+    for (auto *Addr : successors(&BB))
+      I.push_back(Addr);
+  }
+}
+
 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);
+    PendPoints.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);
 }
 
 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;
+
+    for (auto &Update : Updates)
+      if (Update.getFrom() != Update.getTo())
+        PendPoints.insert(Update.getFrom());
+
+    if (!PendPoints.empty())
+      NeedCalculate = true;
+    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;
+    PendPoints.insert(From);
+    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;
+    PendPoints.insert(From);
+    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;
+    PendPoints.insert(From);
+    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;
+    PendPoints.insert(From);
     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: