Index: include/llvm/IR/DomTreeUpdater.h
===================================================================
--- include/llvm/IR/DomTreeUpdater.h
+++ include/llvm/IR/DomTreeUpdater.h
@@ -15,39 +15,65 @@
 #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; };
@@ -251,6 +277,36 @@
 
   /// 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
 
Index: lib/IR/DomTreeUpdater.cpp
===================================================================
--- lib/IR/DomTreeUpdater.cpp
+++ lib/IR/DomTreeUpdater.cpp
@@ -23,6 +23,9 @@
 
 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();
@@ -48,6 +51,79 @@
   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.
@@ -105,8 +181,11 @@
 }
 
 void DomTreeUpdater::flush() {
-  applyDomTreeUpdates();
-  applyPostDomTreeUpdates();
+  if (!isAuto()) {
+    applyDomTreeUpdates();
+    applyPostDomTreeUpdates();
+  } else
+    applyAutoUpdates();
   dropOutOfDateUpdates();
 }
 
@@ -171,6 +250,15 @@
   // 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)
@@ -178,8 +266,15 @@
 
   // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
   IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
-  PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
+  if (!isAuto())
+    PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
   dropOutOfDateUpdates();
+
+  if (isAuto()) {
+    snapshotCFG(SnapshotedCFG);
+    PendEdges.clear();
+    NeedCalculate = false;
+  }
 }
 
 bool DomTreeUpdater::hasPendingUpdates() const {
@@ -189,12 +284,28 @@
 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;
 }
 
@@ -211,7 +322,7 @@
 // Eager, the BasicBlock will be deleted immediately.
 void DomTreeUpdater::deleteBB(BasicBlock *DelBB) {
   validateDeleteBB(DelBB);
-  if (Strategy == UpdateStrategy::Lazy) {
+  if (isLazy()) {
     DeletedBBs.insert(DelBB);
     return;
   }
@@ -224,7 +335,7 @@
 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;
@@ -244,6 +355,12 @@
   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) {
@@ -267,6 +384,22 @@
   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)
@@ -298,14 +431,20 @@
 
 DominatorTree &DomTreeUpdater::getDomTree() {
   assert(DT && "Invalid acquisition of a null DomTree");
-  applyDomTreeUpdates();
+  if (!isAuto())
+    applyDomTreeUpdates();
+  else
+    applyAutoUpdates();
   dropOutOfDateUpdates();
   return *DT;
 }
 
 PostDominatorTree &DomTreeUpdater::getPostDomTree() {
   assert(PDT && "Invalid acquisition of a null PostDomTree");
-  applyPostDomTreeUpdates();
+  if (!isAuto())
+    applyPostDomTreeUpdates();
+  else
+    applyAutoUpdates();
   dropOutOfDateUpdates();
   return *PDT;
 }
@@ -324,6 +463,12 @@
   if (From == To)
     return;
 
+  if (isAuto()) {
+    NeedCalculate = true;
+    PendEdges[From].insert(To);
+    return;
+  }
+
   if (Strategy == UpdateStrategy::Eager) {
     if (DT)
       DT->insertEdge(From, To);
@@ -342,8 +487,15 @@
   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)
@@ -370,6 +522,12 @@
   if (From == To)
     return;
 
+  if (isAuto()) {
+    NeedCalculate = true;
+    PendEdges[From].insert(To);
+    return;
+  }
+
   if (Strategy == UpdateStrategy::Eager) {
     if (DT)
       DT->deleteEdge(From, To);
@@ -388,8 +546,15 @@
   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)
@@ -408,6 +573,10 @@
 
   tryFlushDeletedBB();
 
+  // Early return in Auto mode.
+  if (isAuto())
+    return;
+
   // Drop all updates applied by both trees.
   if (!DT)
     PendDTUpdateIndex = PendUpdates.size();
@@ -526,4 +695,25 @@
   }
 }
 #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
Index: unittests/IR/DomTreeUpdaterTest.cpp
===================================================================
--- unittests/IR/DomTreeUpdaterTest.cpp
+++ unittests/IR/DomTreeUpdaterTest.cpp
@@ -253,7 +253,7 @@
 
   // 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.
@@ -509,13 +509,13 @@
   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);
 }