Index: llvm/trunk/include/llvm/IR/DomTreeUpdater.h
===================================================================
--- llvm/trunk/include/llvm/IR/DomTreeUpdater.h
+++ llvm/trunk/include/llvm/IR/DomTreeUpdater.h
@@ -159,11 +159,9 @@
   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
Index: llvm/trunk/lib/IR/DomTreeUpdater.cpp
===================================================================
--- llvm/trunk/lib/IR/DomTreeUpdater.cpp
+++ llvm/trunk/lib/IR/DomTreeUpdater.cpp
@@ -152,39 +152,34 @@
   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);
-
-    // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
-    IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
-    PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
-    dropOutOfDateUpdates();
-    return true;
-  }
+  forceFlushDeletedBB();
+  if (DT)
+    DT->recalculate(F);
+  if (PDT)
+    PDT->recalculate(F);
 
   // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
   IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
-  return false;
+  PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
+  dropOutOfDateUpdates();
 }
 
 bool DomTreeUpdater::hasPendingUpdates() const {
Index: llvm/trunk/unittests/IR/DomTreeUpdaterTest.cpp
===================================================================
--- llvm/trunk/unittests/IR/DomTreeUpdaterTest.cpp
+++ llvm/trunk/unittests/IR/DomTreeUpdaterTest.cpp
@@ -699,3 +699,29 @@
   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());
+}