[WIP!][DomTreeUpdater-Auto[1]] Collect DomTree construction/update statistics and timing data

[NutshellySima]

Summary

Note: This is a work-in-progress patch and I don't intend to commit it.

This patch has the same intention with D50300. But it targets the Auto[1] UpdateStrategy presented in D50302.

This patch measures the performance of DomTree updating by counting via Statistics the number of no-ops/invalid updates removed, the number of lazy updates applied, the number of recalculation requested via the DomTreeUpdater interface.

This patch also provide timing data through the Timer and TimerGroup class in the LLVM codebase. I put the Timer of DominatorTree in the DomTreeUpdater.cpp because the Timer needs to be static and can only be initialized once so it cannot be in a header file. The unittests failed by this patch is because of some part of LLVM (e.g. lto2) is multithreaded.

Example data collected:

$ opt -passes="default<O3>" -stats < ./sqlite.bc > /dev/null
Statistics
    3 DTU-stats                    - Number of invalid updates discarded
 7058 DTU-stats                    - Number of lazy updates applied
 2541 DTU-stats                    - Number of no-ops removed
    3 DTU-stats                    - Number of recalculations requested
===-------------------------------------------------------------------------===
                                   DTU timing
===-------------------------------------------------------------------------===
  Total Execution Time: 0.0228 seconds (0.0230 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
   0.0223 ( 98.3%)   0.0001 ( 97.2%)   0.0224 ( 98.3%)   0.0227 ( 98.4%)  apply-updates -- DomTree
   0.0003 (  1.4%)   0.0000 (  2.8%)   0.0003 (  1.5%)   0.0003 (  1.3%)  apply-updates -- PostDomTree
   0.0000 (  0.1%)   0.0000 (  0.0%)   0.0000 (  0.1%)   0.0000 (  0.2%)  delete-edge -- DomTree
   0.0000 (  0.1%)   0.0000 (  0.0%)   0.0000 (  0.1%)   0.0000 (  0.1%)  insert-edge -- DomTree
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  recalculate -- DomTree
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  delete-edge -- PostDomTree
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  insert-edge -- PostDomTree
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  recalculate -- PostDomTree
   0.0227 (100.0%)   0.0001 (100.0%)   0.0228 (100.0%)   0.0230 (100.0%)  Total

===-------------------------------------------------------------------------===
                              DomTree Calculation
===-------------------------------------------------------------------------===
  Total Execution Time: 0.1437 seconds (0.1458 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
   0.0899 ( 63.4%)   0.0017 ( 88.4%)   0.0916 ( 63.8%)   0.0931 ( 63.9%)  recalculate -- DomTree
   0.0406 ( 28.6%)   0.0002 (  8.0%)   0.0408 ( 28.4%)   0.0409 ( 28.0%)  apply-updates -- DomTree
   0.0110 (  7.8%)   0.0001 (  3.4%)   0.0111 (  7.7%)   0.0116 (  8.0%)  recalculate -- PostDomTree
   0.0002 (  0.1%)   0.0000 (  0.2%)   0.0002 (  0.1%)   0.0002 (  0.1%)  delete-edge -- DomTree
   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)  insert-edge -- DomTree
   0.1417 (100.0%)   0.0019 (100.0%)   0.1437 (100.0%)   0.1458 (100.0%)  Total

[NutshellySima]

Close along with D50302.

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/Statistic.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>

include/llvm/Support/GenericDomTree.h

 ///
 /// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_GENERICDOMTREE_H
 #define LLVM_SUPPORT_GENERICDOMTREE_H
 
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Timer.h"
+#include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <iterator>
 #include <memory>
 #include <type_traits>
 #include <utility>
 #include <vector>
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/GraphTraits.h"
-#include "llvm/ADT/PointerIntPair.h"
-#include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/Support/raw_ostream.h"
-
 namespace llvm {
 
+struct Timers;
+
+inline Timers *&GetTimers() {
+  static Timers *TimersPtr = nullptr;
+  return TimersPtr;
+}
+
+struct Timers {
+  Timer &DTApplyUpdatesTimer, &DTInsertEdgeTimer, &DTDeleteEdgeTimer,
+      &DTRecalculateTimer, &PDTApplyUpdatesTimer, &PDTInsertEdgeTimer,
+      &PDTDeleteEdgeTimer, &PDTRecalculateTimer;
+
+  Timers(Timer &DTApplyUpdatesTimer_, Timer &DTInsertEdgeTimer_,
+         Timer &DTDeleteEdgeTimer_, Timer &DTRecalculateTimer_,
+         Timer &PDTApplyUpdatesTimer_, Timer &PDTInsertEdgeTimer_,
+         Timer &PDTDeleteEdgeTimer_, Timer &PDTRecalculateTimer_)
+      : DTApplyUpdatesTimer(DTApplyUpdatesTimer_),
+        DTInsertEdgeTimer(DTInsertEdgeTimer_),
+        DTDeleteEdgeTimer(DTDeleteEdgeTimer_),
+        DTRecalculateTimer(DTRecalculateTimer_),
+        PDTApplyUpdatesTimer(PDTApplyUpdatesTimer_),
+        PDTInsertEdgeTimer(PDTInsertEdgeTimer_),
+        PDTDeleteEdgeTimer(PDTDeleteEdgeTimer_),
+        PDTRecalculateTimer(PDTRecalculateTimer_) {
+
+    llvm::GetTimers() = this;
+  }
+  static Timers *getTimers() { return GetTimers(); }
+};
+
 template <typename NodeT, bool IsPostDom>
 class DominatorTreeBase;
 
 namespace DomTreeBuilder {
 template <typename DomTreeT>
 struct SemiNCAInfo;
 }  // namespace DomTreeBuilder
 
#endif
   /// updates on reverse edges internally (so there's no need to swap the
   /// From and To pointers when constructing DominatorTree::UpdateType).
   /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
   /// with the same template parameter T.
   ///
   /// \param Updates An unordered sequence of updates to perform.
   ///
   void applyUpdates(ArrayRef<UpdateType> Updates) {
+    if (!Timers::getTimers()) {
+      DomTreeBuilder::ApplyUpdates(*this, Updates);
+      return;
+    }
+
+    Timer *T = &Timers::getTimers()->DTApplyUpdatesTimer;
+    if (this->isPostDominator())
+      T = &Timers::getTimers()->PDTApplyUpdatesTimer;
+    T->startTimer();
     DomTreeBuilder::ApplyUpdates(*this, Updates);
+    T->stopTimer();
   }
 
   /// Inform the dominator tree about a CFG edge insertion and update the tree.
   ///
   /// This function has to be called just before or just after making the update
   /// on the actual CFG. There cannot be any other updates that the dominator
   /// tree doesn't know about.
   ///
   /// Note that for postdominators it automatically takes care of inserting
   /// a reverse edge internally (so there's no need to swap the parameters).
   ///
   void insertEdge(NodeT *From, NodeT *To) {
     assert(From);
     assert(To);
     assert(From->getParent() == Parent);
     assert(To->getParent() == Parent);
+    if (!Timers::getTimers()) {
+      DomTreeBuilder::InsertEdge(*this, From, To);
+      return;
+    }
+    Timer *T = &Timers::getTimers()->DTInsertEdgeTimer;
+    if (this->isPostDominator())
+      T = &Timers::getTimers()->PDTInsertEdgeTimer;
+    T->startTimer();
     DomTreeBuilder::InsertEdge(*this, From, To);
+    T->stopTimer();
   }
 
   /// Inform the dominator tree about a CFG edge deletion and update the tree.
   ///
   /// This function has to be called just after making the update on the actual
   /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
   /// DEBUG mode. There cannot be any other updates that the
   /// dominator tree doesn't know about.
   ///
   /// Note that for postdominators it automatically takes care of deleting
   /// a reverse edge internally (so there's no need to swap the parameters).
   ///
   void deleteEdge(NodeT *From, NodeT *To) {
     assert(From);
     assert(To);
     assert(From->getParent() == Parent);
     assert(To->getParent() == Parent);
+    if (!Timers::getTimers()) {
+      DomTreeBuilder::DeleteEdge(*this, From, To);
+      return;
+    }
+    Timer *T = &Timers::getTimers()->DTDeleteEdgeTimer;
+    if (this->isPostDominator())
+      T = &Timers::getTimers()->PDTDeleteEdgeTimer;
+    T->startTimer();
     DomTreeBuilder::DeleteEdge(*this, From, To);
+    T->stopTimer();
   }
 
   /// Add a new node to the dominator tree information.
   ///
   /// This creates a new node as a child of DomBB dominator node, linking it
   /// into the children list of the immediate dominator.
   ///
   /// \param BB New node in CFG.
void updateDFSNumbers() const {
 
     SlowQueries = 0;
     DFSInfoValid = true;
   }
 
   /// recalculate - compute a dominator tree for the given function
   void recalculate(ParentType &Func) {
     Parent = &Func;
+    if (!Timers::getTimers()) {
+      DomTreeBuilder::Calculate(*this);
+      return;
+    }
+    Timer *T = &Timers::getTimers()->DTRecalculateTimer;
+    if (this->isPostDominator())
+      T = &Timers::getTimers()->PDTRecalculateTimer;
+    T->startTimer();
     DomTreeBuilder::Calculate(*this);
+    T->stopTimer();
   }
 
   /// verify - checks if the tree is correct. There are 3 level of verification:
   ///  - Full --  verifies if the tree is correct by making sure all the
   ///             properties (including the parent and the sibling property)
   ///             hold.
   ///             Takes O(N^3) time.
   ///

lib/IR/DomTreeUpdater.cpp

 //===- DomTreeUpdater.cpp - DomTree/Post DomTree Updater --------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the DomTreeUpdater class, which provides a uniform way
 // to update dominator tree related data structures.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/DomTreeUpdater.h"
+#include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/Support/GenericDomTree.h"
+#include "llvm/Support/Timer.h"
 #include <algorithm>
 #include <functional>
-
 namespace llvm {
 
+#define DEBUG_TYPE "DTU-stats"
+
+STATISTIC(NumNoopPruned, "Number of no-ops removed");
+STATISTIC(NumDuplicatePruned, "Number of duplicates removed");
+STATISTIC(NumInvalidPruned, "Number of invalid updates discarded");
+STATISTIC(NumRecalculate, "Number of recalculations requested");
+STATISTIC(NumLazyUpdate, "Number of lazy updates applied");
+
+#undef DEBUG_TYPE
+
+static TimerGroup DTTimerGroup("DomTree Timer", "DomTree Calculation");
+static Timer DTApplyUpdatesTimer("domtree-au", "apply-updates -- DomTree",
+                                 DTTimerGroup);
+static Timer DTInsertEdgeTimer("domtree-ie", "insert-edge -- DomTree",
+                               DTTimerGroup);
+static Timer DTDeleteEdgeTimer("domtree-de", "delete-edge -- DomTree",
+                               DTTimerGroup);
+static Timer DTRecalculateTimer("domtree-re", "recalculate -- DomTree",
+                                DTTimerGroup);
+static Timer PDTApplyUpdatesTimer("pdomtree-au", "apply-updates -- PostDomTree",
+                                  DTTimerGroup);
+static Timer PDTInsertEdgeTimer("pdomtree-ie", "insert-edge -- PostDomTree",
+                                DTTimerGroup);
+static Timer PDTDeleteEdgeTimer("pdomtree-de", "delete-edge -- PostDomTree",
+                                DTTimerGroup);
+static Timer PDTRecalculateTimer("pdomtree-re", "recalculate -- PostDomTree",
+                                 DTTimerGroup);
+static Timers DTTimers(DTApplyUpdatesTimer, DTInsertEdgeTimer,
+                       DTDeleteEdgeTimer, DTRecalculateTimer,
+                       PDTApplyUpdatesTimer, PDTInsertEdgeTimer,
+                       PDTDeleteEdgeTimer, PDTRecalculateTimer);
+static TimerGroup DTUTimerGroup("DTU Timer", "DTU timing");
+static Timer DTUApplyUpdatesTimer("domtree-au", "apply-updates -- DomTree",
+                                  DTUTimerGroup);
+static Timer DTUInsertEdgeTimer("domtree-ie", "insert-edge -- DomTree",
+                                DTUTimerGroup);
+static Timer DTUDeleteEdgeTimer("domtree-de", "delete-edge -- DomTree",
+                                DTUTimerGroup);
+static Timer DTURecalculateTimer("domtree-re", "recalculate -- DomTree",
+                                 DTUTimerGroup);
+static Timer PDTUApplyUpdatesTimer("pdomtree-au",
+                                   "apply-updates -- PostDomTree",
+                                   DTUTimerGroup);
+static Timer PDTUInsertEdgeTimer("pdomtree-ie", "insert-edge -- PostDomTree",
+                                 DTUTimerGroup);
+static Timer PDTUDeleteEdgeTimer("pdomtree-de", "delete-edge -- PostDomTree",
+                                 DTUTimerGroup);
+static Timer PDTURecalculateTimer("pdomtree-re", "recalculate -- PostDomTree",
+                                  DTUTimerGroup);
+static Timer SnapshotTimer("Snapshot", "Snapshot", DTUTimerGroup);
+static Timer DiffTimer("Diff", "Diff", DTUTimerGroup);
+static Timer DeduplicateTimer("Deduplicate", "Deduplicate", DTUTimerGroup);
+
 bool DomTreeUpdater::isUpdateValid(
     const DominatorTree::UpdateType Update) const {
 #ifdef NDEBUG
   assert(!isAuto() && "Auto UpdateStrategy should not go into this function.");
 #endif
+  ++NumInvalidPruned;
   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.
   const bool HasEdge = llvm::any_of(
       successors(From), [To](const BasicBlock *B) { return B == To; });
 
   // If the IR does not match the update,
   // 1. In batch updates, this update is unnecessary.
   // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid.
   // Edge does not exist in IR.
   if (Kind == DominatorTree::Insert && !HasEdge)
     return false;
 
   // Edge exists in IR.
   if (Kind == DominatorTree::Delete && HasEdge)
     return false;
-
+  --NumInvalidPruned;
   return true;
 }
 
 std::vector<DominatorTree::UpdateType> DomTreeUpdater::diffCFG(CFG &PrevCFG,
                                                                CFG &NewCFG) {
+  DiffTimer.startTimer();
   CFG DiffCFG;
   std::vector<DominatorTree::UpdateType> Updates;
   std::set_difference(PrevCFG.begin(), PrevCFG.end(), NewCFG.begin(),
                       NewCFG.end(), std::inserter(DiffCFG, DiffCFG.begin()));
   // Deleted Edges
   for (auto &Edge : DiffCFG)
     if (Edge.first != Edge.second) // Discard self dominance.
       Updates.push_back({DominatorTree::Delete, Edge.first, Edge.second});
   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 (Edge.first != Edge.second) // Discard self dominance.
       Updates.push_back({DominatorTree::Insert, Edge.first, Edge.second});
+  DiffTimer.stopTimer();
   return Updates;
 }
 
 void DomTreeUpdater::snapshotCFG(CFG &Graph) {
   // No DT and PDT.
   if (!DT && !PDT)
     return;
 
   // Get Function to snapshot.
   if (!Func) {
     if (DT)
       Func = DT->getRoot()->getParent();
     else if (PDT)
       Func = PDT->getRoot()->getParent();
   }
 
   // Get Current EntryBB.
   SnapshotedBB = &Func->getEntryBlock();
 
   // Do the full snapshot.
+  SnapshotTimer.startTimer();
   Graph.clear();
   for (BasicBlock &BB : Func->getBasicBlockList())
     for (auto *Addr : successors(&BB))
       Graph.push_back(std::make_pair(&BB, Addr));
   // Deduplicate
   llvm::sort(Graph.begin(), Graph.end());
   Graph.erase(std::unique(Graph.begin(), Graph.end()), Graph.end());
+  SnapshotTimer.stopTimer();
 }
 
 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,
   // Only check duplicates in updates that are not applied by both trees.
   auto I =
       PendUpdates.begin() + std::max(PendDTUpdateIndex, PendPDTUpdateIndex);
   const auto E = PendUpdates.end();
 
   assert(I <= E && "Iterator out of range.");
 
   for (; I != E; ++I) {
-    if (Update == *I)
+    if (Update == *I) {
+      ++NumDuplicatePruned;
       return false; // Discard duplicate updates.
-
+    }
     if (Invert == *I) {
       // Update and Invert are both valid (equivalent to a no-op). Remove
       // Invert from PendUpdates and discard the Update.
+      ++NumNoopPruned;
+      --NumLazyUpdate;
       PendUpdates.erase(I);
       return false;
     }
   }
-
+  ++NumLazyUpdate;
   PendUpdates.push_back(Update); // Save the valid update.
   return true;
 }
 
 void DomTreeUpdater::applyDomTreeUpdates() {
   // No pending DomTreeUpdates.
   if (Strategy != UpdateStrategy::Lazy || !DT)
     return;
 
   // Only apply updates not are applied by DomTree.
   if (hasPendingDomTreeUpdates()) {
     const auto I = PendUpdates.begin() + PendDTUpdateIndex;
     const auto E = PendUpdates.end();
     assert(I < E && "Iterator range invalid; there should be DomTree updates.");
+    DTUApplyUpdatesTimer.startTimer();
     DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
+    DTUApplyUpdatesTimer.stopTimer();
     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;
 
   // Only apply updates not are applied by PostDomTree.
   if (hasPendingPostDomTreeUpdates()) {
     const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
     const auto E = PendUpdates.end();
     assert(I < E &&
            "Iterator range invalid; there should be PostDomTree updates.");
+    PDTUApplyUpdatesTimer.startTimer();
     PDT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
+    PDTUApplyUpdatesTimer.stopTimer();
     PendPDTUpdateIndex = PendUpdates.size();
   }
 }
 
 void DomTreeUpdater::tryFlushDeletedBB() {
   if (!hasPendingUpdates())
     forceFlushDeletedBB();
 }
bool DomTreeUpdater::forceFlushDeletedBB() {
   Callbacks.clear();
   return true;
 }
 
 void DomTreeUpdater::recalculate(Function &F) {
 
   if (Strategy == UpdateStrategy::Eager) {
     if (DT)
+      ++NumRecalculate;
+    if (PDT)
+      ++NumRecalculate;
+    DTURecalculateTimer.startTimer();
+    if (DT)
       DT->recalculate(F);
+    DTURecalculateTimer.stopTimer();
+    PDTURecalculateTimer.startTimer();
     if (PDT)
       PDT->recalculate(F);
+    PDTURecalculateTimer.stopTimer();
     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.
   forceFlushDeletedBB();
   if (isAuto()) {
     // Entry block is not replaced.
     if (SnapshotedBB == &Func->getEntryBlock()) {
       NeedCalculate = true;
       IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
       applyAutoUpdates();
       return;
     }
-  }
 
     if (DT)
+      ++NumRecalculate;
+    if (PDT)
+      ++NumRecalculate;
+    DTURecalculateTimer.startTimer();
+    if (DT)
       DT->recalculate(F);
+    DTURecalculateTimer.stopTimer();
+    PDTURecalculateTimer.startTimer();
     if (PDT)
       PDT->recalculate(F);
+    PDTURecalculateTimer.stopTimer();
 
     // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
     IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
 
     if (!isAuto())
       PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
 
     dropOutOfDateUpdates();
 
     if (isAuto()) {
       // The tree is updated.
       snapshotCFG(SnapshotedCFG);
       NeedCalculate = false;
   }
 }
+}
 
 bool DomTreeUpdater::hasPendingUpdates() const {
   return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
 }
 
 bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
   if (!DT)
     return false;
for (auto &Update : Updates)
         Changed = true;
         break;
       }
     NeedCalculate = Changed;
     return;
   }
 
   if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) {
+    if (isLazy())
+      DeduplicateTimer.startTimer();
     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; }) &&
           isUpdateValid(U) && !isSelfDominance(U)) {
         Seen.push_back(U);
         if (Strategy == UpdateStrategy::Lazy)
           applyLazyUpdate(U.getKind(), U.getFrom(), U.getTo());
       }
+    if (isLazy())
+      DeduplicateTimer.stopTimer();
     if (Strategy == UpdateStrategy::Lazy)
       return;
 
+    DTUApplyUpdatesTimer.startTimer();
     if (DT)
       DT->applyUpdates(Seen);
+    DTUApplyUpdatesTimer.stopTimer();
+    PDTUApplyUpdatesTimer.startTimer();
     if (PDT)
       PDT->applyUpdates(Seen);
+    PDTUApplyUpdatesTimer.stopTimer();
     return;
   }
 
+  DTUApplyUpdatesTimer.startTimer();
   if (DT)
     DT->applyUpdates(Updates);
+  DTUApplyUpdatesTimer.stopTimer();
+  PDTUApplyUpdatesTimer.startTimer();
   if (PDT)
     PDT->applyUpdates(Updates);
+  PDTUApplyUpdatesTimer.stopTimer();
 }
 
 DominatorTree &DomTreeUpdater::getDomTree() {
   assert(DT && "Invalid acquisition of a null DomTree");
   if (!isAuto())
     applyDomTreeUpdates();
   else
     applyAutoUpdates();
#endif
 
   if (isAuto()) {
     // There is a change in the CFG.
     NeedCalculate = true;
     return;
   }
 
   if (Strategy == UpdateStrategy::Eager) {
+    DTUInsertEdgeTimer.startTimer();
     if (DT)
       DT->insertEdge(From, To);
+    DTUInsertEdgeTimer.stopTimer();
+    PDTUInsertEdgeTimer.startTimer();
     if (PDT)
       PDT->insertEdge(From, To);
+    PDTUInsertEdgeTimer.stopTimer();
     return;
   }
 
+  DeduplicateTimer.startTimer();
   applyLazyUpdate(DominatorTree::Insert, From, To);
+  DeduplicateTimer.stopTimer();
 }
 
 void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
   if (From == To)
     return;
 
   if (!DT && !PDT)
     return;
 
   if (isAuto()) {
     // Assume there is a change in the CFG.
     NeedCalculate = true;
     return;
   }
 
+  DeduplicateTimer.startTimer();
   if (!isUpdateValid({DominatorTree::Insert, From, To})) {
+    DeduplicateTimer.stopTimer();
     return;
   }
+  DeduplicateTimer.stopTimer();
 
   if (Strategy == UpdateStrategy::Eager) {
+    DTUInsertEdgeTimer.startTimer();
     if (DT)
       DT->insertEdge(From, To);
+    DTUInsertEdgeTimer.stopTimer();
+    PDTUInsertEdgeTimer.startTimer();
     if (PDT)
       PDT->insertEdge(From, To);
+    PDTUInsertEdgeTimer.stopTimer();
     return;
   }
 
+  DeduplicateTimer.startTimer();
   applyLazyUpdate(DominatorTree::Insert, From, To);
+  DeduplicateTimer.stopTimer();
 }
 
 void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
 
 #ifndef NDEBUG
   assert(isUpdateValid({DominatorTree::Delete, From, To}) &&
          "Deleted edge still exists in the CFG!");
 #endif
 
   if (!DT && !PDT)
     return;
 
   // Won't affect DomTree and PostDomTree; discard update.
   if (From == To)
     return;
 
   if (isAuto()) {
     // There is a change in the CFG.
     NeedCalculate = true;
     return;
   }
 
   if (Strategy == UpdateStrategy::Eager) {
+    DTUDeleteEdgeTimer.startTimer();
     if (DT)
       DT->deleteEdge(From, To);
+    DTUDeleteEdgeTimer.stopTimer();
+    PDTUDeleteEdgeTimer.startTimer();
     if (PDT)
       PDT->deleteEdge(From, To);
+    PDTUDeleteEdgeTimer.stopTimer();
     return;
   }
 
+  DeduplicateTimer.startTimer();
   applyLazyUpdate(DominatorTree::Delete, From, To);
+  DeduplicateTimer.stopTimer();
 }
 
 void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
   if (From == To)
     return;
 
   if (!DT && !PDT)
     return;
 
   if (isAuto()) {
     // Assume there is a change in the CFG.
     NeedCalculate = true;
     return;
   }
 
+  DeduplicateTimer.startTimer();
   if (!isUpdateValid({DominatorTree::Delete, From, To})) {
+    DeduplicateTimer.stopTimer();
     return;
   }
+  DeduplicateTimer.stopTimer();
 
   if (Strategy == UpdateStrategy::Eager) {
+    DTUDeleteEdgeTimer.startTimer();
     if (DT)
       DT->deleteEdge(From, To);
+    DTUDeleteEdgeTimer.stopTimer();
+    PDTUDeleteEdgeTimer.startTimer();
     if (PDT)
       PDT->deleteEdge(From, To);
+    PDTUDeleteEdgeTimer.stopTimer();
     return;
   }
 
+  DeduplicateTimer.startTimer();
   applyLazyUpdate(DominatorTree::Delete, From, To);
+  DeduplicateTimer.stopTimer();
 }
 
 void DomTreeUpdater::dropOutOfDateUpdates() {
   if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
     return;
 
   tryFlushDeletedBB();
 
   // Early return if DTU works with snapshot.
   if (isAuto())
     return;
 
+  DeduplicateTimer.startTimer();
   // 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();
   const auto E = PendUpdates.begin() + dropIndex;
   assert(B <= E && "Iterator out of range.");
 
   PendUpdates.erase(B, E);
 
   // Calculate current index.
   PendDTUpdateIndex -= dropIndex;
   PendPDTUpdateIndex -= dropIndex;
+  DeduplicateTimer.stopTimer();
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void DomTreeUpdater::dump() const {
   raw_ostream &OS = llvm::dbgs();
 
   OS << "Available Trees: ";
   if (DT || PDT) {
if (SnapshotedBB != &Func->getEntryBlock()) {
     return;
   }
 
   NeedCalculate = false;
   CFG CurrentCFG;
   snapshotCFG(CurrentCFG);
   auto Updates = diffCFG(SnapshotedCFG, CurrentCFG);
   SnapshotedCFG = std::move(CurrentCFG);
+  DTUApplyUpdatesTimer.startTimer();
   if (DT)
     DT->applyUpdates(Updates);
+  DTUApplyUpdatesTimer.stopTimer();
+  PDTUApplyUpdatesTimer.startTimer();
   if (PDT)
     PDT->applyUpdates(Updates);
+  PDTUApplyUpdatesTimer.stopTimer();
 }
 } // namespace llvm