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

[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 has the same intention with D50300. But it targets the Auto[2] UpdateStrategy presented in D50311.

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 this revision along with D50311.

include/llvm/IR/DomTreeUpdater.h

 //===----------------------------------------------------------------------===//
 
 #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/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 SnapshotSortTimer("SnapshotSort", "SnapshotSort", DTUTimerGroup);
+static Timer PendPushTimer("PendPush", "PendPush", DTUTimerGroup);
+static Timer HintPushTimer("HintPush", "HintPush", 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());
 #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;
 }
 
 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.
+  PendPushTimer.startTimer();
   if (SnapshotedCFG.find(BB) != SnapshotedCFG.end()) {
+    PendPushTimer.stopTimer();
     return;
   }
   // It is a new BB.
   if (CFGPoints.find(BB) == CFGPoints.end()) {
+    PendPushTimer.stopTimer();
     return;
   }
+  PendPushTimer.stopTimer();
+  SnapshotTimer.startTimer();
   SnapshotedCFG[BB] = getNewCFG(BB);
+  SnapshotTimer.stopTimer();
 }
 
 std::vector<DominatorTree::UpdateType> DomTreeUpdater::diffCFG() {
+  DiffTimer.startTimer();
 
   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();
+  DiffTimer.stopTimer();
   NeedCalculate = false;
 
   return Updates;
 }
 
 void DomTreeUpdater::snapshotCFG(CFG &Graph) {
   if (!DT && !PDT)
     return;
 
+  PendPushTimer.startTimer();
   Graph.clear();
+  PendPushTimer.stopTimer();
 
+  SnapshotTimer.startTimer();
   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);
+  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()) {
     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()) {
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);
 
+  PendPushTimer.startTimer();
   // Delete this FromBB in case of memory leak.
   if (isAuto())
     SnapshotedCFG.erase(DelBB);
+  PendPushTimer.stopTimer();
 
   CFGPoints.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.
void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
   if (!DT && !PDT)
     return;
 
   if (isAuto()) {
 
     if (Updates.empty())
       return;
 
+    HintPushTimer.startTimer();
     bool Changed = false;
     for (auto &Update : Updates) {
       if (Update.getFrom() != Update.getTo()) {
         PendEdges[Update.getFrom()].insert(Update.getTo());
         Changed = true;
       }
     }
     NeedCalculate |= Changed;
+    HintPushTimer.stopTimer();
     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();
if (!DT && !PDT)
     return;
 
   // Won't affect DomTree and PostDomTree; discard update.
   if (From == To)
     return;
 
   if (isAuto()) {
     NeedCalculate = true;
+    HintPushTimer.startTimer();
     PendEdges[From].insert(To);
+    HintPushTimer.stopTimer();
     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()) {
     NeedCalculate = true;
+    HintPushTimer.startTimer();
     PendEdges[From].insert(To);
+    HintPushTimer.stopTimer();
     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()) {
     NeedCalculate = true;
+    HintPushTimer.startTimer();
     PendEdges[From].insert(To);
+    HintPushTimer.stopTimer();
     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()) {
     NeedCalculate = true;
+    HintPushTimer.startTimer();
     PendEdges[From].insert(To);
+    HintPushTimer.stopTimer();
     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 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();
   const auto E = PendUpdates.begin() + dropIndex;
   assert(B <= E && "Iterator out of range.");
+  DeduplicateTimer.startTimer();
   PendUpdates.erase(B, E);
+  DeduplicateTimer.stopTimer();
   // Calculate current index.
   PendDTUpdateIndex -= dropIndex;
   PendPDTUpdateIndex -= dropIndex;
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void DomTreeUpdater::dump() const {
   raw_ostream &OS = llvm::dbgs();
void DomTreeUpdater::applyAutoUpdates() {
   if (SnapshotedBB != &Func->getEntryBlock()) {
     // recalculate() will snapshot and reset NeedCalculate.
     recalculate(*Func);
     return;
   }
 
   // diffCFG will reset NeedCalculate.
   auto Updates = diffCFG();
+  DTUApplyUpdatesTimer.startTimer();
   if (DT)
     DT->applyUpdates(Updates);
+  DTUApplyUpdatesTimer.stopTimer();
+  PDTUApplyUpdatesTimer.startTimer();
   if (PDT)
     PDT->applyUpdates(Updates);
+  PDTUApplyUpdatesTimer.stopTimer();
 }
 } // namespace llvm