[Dominators] Refine the logic of recalculate() in the DomTreeUpdater

[NutshellySima]

Summary

This patch refines the logic of recalculate() in the DomTreeUpdater in the following two aspects:

1. Previously, recalculate() tests whether there are pending updates/BBs awaiting deletion and then do recalculation under Lazy UpdateStrategy; and do recalculation immediately under Eager UpdateStrategy. (The former behavior is inherited from the DeferredDominance class). This is an inconsistency between two strategies and there is no obvious reason to do this. So the behavior is changed to always recalculate available trees when calling recalculate().
2. Fix the issue of when DTU under Lazy UpdateStrategy holds nothing but with BBs awaiting deletion, after calling recalculate(), BBs awaiting deletion aren't flushed. An additional unittest is added to cover this case.

[kuhar]

Looks good, thanks for the patch!

include/llvm/IR/DomTreeUpdater.h

164 ↗

(On Diff #158705)

I like this comment, it's brief but straight to the point!

llvm/trunk/include/llvm/IR/DomTreeUpdater.h

public:
   /// Under Eager UpdateStrategy, DelBB will be processed immediately.
   /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
   /// all available trees are up-to-date. Assert if any instruction of DelBB is
   /// modified while awaiting deletion. Multiple callbacks can be queued for one
   /// DelBB under Lazy UpdateStrategy.
   void callbackDeleteBB(BasicBlock *DelBB,
                         std::function<void(BasicBlock *)> Callback);
 
-  /// Recalculate all available trees.
-  /// Under Lazy Strategy, available trees will only be recalculated if there
-  /// are pending updates or there is BasicBlock awaiting deletion. Returns true
-  /// if at least one tree is recalculated.
-  bool recalculate(Function &F);
+  /// Recalculate all available trees and flush all BasicBlocks
+  /// awaiting deletion immediately.
+  void recalculate(Function &F);
 
   /// Flush DomTree updates and return DomTree.
   /// It also flush out of date updates applied by all available trees
   /// and flush Deleted BBs if both trees are up-to-date.
   /// It must only be called when it has a DomTree.
   DominatorTree &getDomTree();
 
   /// Flush PostDomTree updates and return PostDomTree.

llvm/trunk/lib/IR/DomTreeUpdater.cpp

for (auto *BB : DeletedBBs) {
     eraseDelBBNode(BB);
     delete BB;
   }
   DeletedBBs.clear();
   Callbacks.clear();
   return true;
 }
 
-bool DomTreeUpdater::recalculate(Function &F) {
-  if (!DT && !PDT)
-    return false;
+void DomTreeUpdater::recalculate(Function &F) {
 
   if (Strategy == UpdateStrategy::Eager) {
     if (DT)
       DT->recalculate(F);
     if (PDT)
       PDT->recalculate(F);
-    return true;
+    return;
   }
 
+  // There is little performance gain if we pend the recalculation under
+  // 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.
-  if (forceFlushDeletedBB() || hasPendingUpdates()) {
-    if (DT)
-      DT->recalculate(F);
-    if (PDT)
-      PDT->recalculate(F);
+  forceFlushDeletedBB();
 
-    // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
-    IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
-    PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
-    dropOutOfDateUpdates();
-    return true;
-  }
-
-  // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
-  IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
-  return false;
 }
 
 bool DomTreeUpdater::hasPendingUpdates() const {
   return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
 }
 
 bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
   if (!DT)

llvm/trunk/unittests/IR/DomTreeUpdaterTest.cpp

TEST(DomTreeUpdater, LazyUpdateStepTest) {
   // flush PostDomTree
   ASSERT_TRUE(DTU.getPostDomTree().verify());
   ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());
   ASSERT_TRUE(DTU.hasPendingDomTreeUpdates());
   // flush both trees
   DTU.flush();
   ASSERT_TRUE(DT.verify());
 }
+
+TEST(DomTreeUpdater, NoTreeTest) {
+  StringRef FuncName = "f";
+  StringRef ModuleString = R"(
+                           define i32 @f() {
+                           bb0:
+                              ret i32 0
+                           }
+                           )";
+  // Make the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+  Function *F = M->getFunction(FuncName);
+
+  // Make the DTU.
+  DomTreeUpdater DTU(nullptr, nullptr, DomTreeUpdater::UpdateStrategy::Lazy);
+  ASSERT_FALSE(DTU.hasDomTree());
+  ASSERT_FALSE(DTU.hasPostDomTree());
+  Function::iterator FI = F->begin();
+  BasicBlock *BB0 = &*FI++;
+  // Test whether PendingDeletedBB is flushed after the recalculation.
+  DTU.deleteBB(BB0);
+  ASSERT_TRUE(DTU.hasPendingDeletedBB());
+  DTU.recalculate(*F);
+  ASSERT_FALSE(DTU.hasPendingDeletedBB());
+}