[WIP!][Dominators] 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 can work with D36884 to provide a better view to devs who concern about the performance of DomTree updating and construction.

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]

Some timing benchmarks on Lazy UpdateStrategy:
https://reviews.llvm.org/P8098

[NutshellySima]

1. Add the timer on stateful deduplication (which aims to be deprecated soon).
2. rebase.

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 <vector>
 

include/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/CFGUpdate.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>
 
 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();
   }
 
   void recalculate(ParentType &Func, ArrayRef<UpdateType> Updates) {
     Parent = &Func;
     DomTreeBuilder::CalculateWithUpdates(*this, Updates);
   }
 
   /// verify - checks if the tree is correct. There are 3 level of verification:

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 DTUDeDuplicate("dtu-dedup", "Deduplication", DTUTimerGroup);
+
 bool DomTreeUpdater::isUpdateValid(
     const DominatorTree::UpdateType Update) const {
+  ++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;
 }
 
 bool DomTreeUpdater::isSelfDominance(
     const DominatorTree::UpdateType Update) const {
   // Won't affect DomTree and PostDomTree.
   return Update.getFrom() == Update.getTo();
 }
const DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
                                                 : DominatorTree::Delete,
                                             From, To};
   // 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.");
+  DTUDeDuplicate.startTimer();
 
   for (; I != E; ++I) {
-    if (Update == *I)
+    if (Update == *I) {
+      ++NumDuplicatePruned;
+      DTUDeDuplicate.stopTimer();
       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);
+      DTUDeDuplicate.stopTimer();
       return false;
     }
   }
-
+  DTUDeDuplicate.stopTimer();
+  ++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() {
   applyDomTreeUpdates();
   applyPostDomTreeUpdates();
   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 (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;
   PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
   dropOutOfDateUpdates();
 }
 
 bool DomTreeUpdater::hasPendingUpdates() const {
for (const auto U : Updates)
           isUpdateValid(U) && !isSelfDominance(U)) {
         Seen.push_back(U);
         if (Strategy == UpdateStrategy::Lazy)
           applyLazyUpdate(U.getKind(), U.getFrom(), U.getTo());
       }
     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");
   applyDomTreeUpdates();
   dropOutOfDateUpdates();
   return *DT;
 }
#endif
   if (!DT && !PDT)
     return;
 
   // Won't affect DomTree and PostDomTree; discard update.
   if (From == To)
     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;
   }
 
   applyLazyUpdate(DominatorTree::Insert, From, To);
 }
 
 void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
   if (From == To)
     return;
 
   if (!DT && !PDT)
     return;
 
   if (!isUpdateValid({DominatorTree::Insert, From, To}))
     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;
   }
 
   applyLazyUpdate(DominatorTree::Insert, From, To);
 }
 
 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 (Strategy == UpdateStrategy::Eager) {
+    DTUDeleteEdgeTimer.startTimer();
     if (DT)
       DT->deleteEdge(From, To);
+    DTUDeleteEdgeTimer.stopTimer();
+    PDTUDeleteEdgeTimer.startTimer();
     if (PDT)
       PDT->deleteEdge(From, To);
+    PDTUDeleteEdgeTimer.stopTimer();
     return;
   }
 
   applyLazyUpdate(DominatorTree::Delete, From, To);
 }
 
 void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
   if (From == To)
     return;
 
   if (!DT && !PDT)
     return;
 
   if (!isUpdateValid({DominatorTree::Delete, From, To}))
     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;
   }
 
   applyLazyUpdate(DominatorTree::Delete, From, To);
 }
 
 void DomTreeUpdater::dropOutOfDateUpdates() {
   if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)