Index: include/llvm/Support/GenericDomTreeConstruction.h
===================================================================
--- include/llvm/Support/GenericDomTreeConstruction.h
+++ include/llvm/Support/GenericDomTreeConstruction.h
@@ -39,6 +39,7 @@
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/Statistic.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/GenericDomTree.h"
 
@@ -47,6 +48,73 @@
 namespace llvm {
 namespace DomTreeBuilder {
 
+struct StatsHolder;
+
+inline StatsHolder *&GetDomTreeBuilderStats() {
+  static StatsHolder *StatsPtr = nullptr;
+  return StatsPtr;
+}
+
+struct StatsHolder {
+  Statistic &NumDomRecalculated;
+  Statistic &NumPostDomRecalculated;
+  Statistic &NumDomInserted;
+  Statistic &NumPostDomInserted;
+  Statistic &NumDomDeleted;
+  Statistic &NumPostDomDeleted;
+  Statistic &NumDomVisited;
+  Statistic &NumPostDomVisited;
+
+  StatsHolder(Statistic &DomRecalculated,
+              Statistic &PostDomRecalculated,
+              Statistic &DomInserted,
+              Statistic &PostDomInserted,
+              Statistic &DomDeleted,
+              Statistic &PostDomDeleted,
+              Statistic &DomVisited,
+              Statistic &PostDomVisited)
+      : NumDomRecalculated(DomRecalculated),
+        NumPostDomRecalculated(PostDomRecalculated),
+        NumDomInserted(DomInserted),
+        NumPostDomInserted(PostDomInserted),
+        NumDomDeleted(DomDeleted),
+        NumPostDomDeleted(PostDomDeleted),
+        NumDomVisited(DomVisited),
+        NumPostDomVisited(PostDomVisited) {
+
+    DomTreeBuilder::GetDomTreeBuilderStats() = this;
+  }
+
+  static void IncNumRecalculated(bool IsPostDom) {
+    StatsHolder *SH = GetDomTreeBuilderStats();
+    if (!SH) return;
+    if (!IsPostDom) ++(SH->NumDomRecalculated);
+    else ++SH->NumPostDomRecalculated;
+  }
+
+  static void IncNumInsertions(bool IsPostDom) {
+    StatsHolder *SH = GetDomTreeBuilderStats();
+    if (!SH) return;
+    if (!IsPostDom) ++SH->NumDomInserted;
+    else ++SH->NumPostDomInserted;
+  }
+
+  static void IncNumDeletions(bool IsPostDom) {
+    StatsHolder *SH = GetDomTreeBuilderStats();
+    if (!SH) return;
+    if (!IsPostDom) ++SH->NumDomDeleted;
+    else ++SH->NumPostDomDeleted;
+  }
+
+  static void IncNumNodesVisited(bool IsPostDom, unsigned K) {
+    StatsHolder *SH = GetDomTreeBuilderStats();
+    if (!SH) return;
+    if (!IsPostDom) SH->NumDomVisited += K;
+    else SH->NumPostDomVisited += K;
+  }
+};
+
+
 template <typename DomTreeT>
 struct SemiNCAInfo {
   using NodePtr = typename DomTreeT::NodePtr;
@@ -219,6 +287,8 @@
     SmallVector<NodePtr, 64> WorkList = {V};
     if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum;
 
+    const unsigned StartNum = LastNum;
+
     while (!WorkList.empty()) {
       const NodePtr BB = WorkList.pop_back_val();
       auto &BBInfo = NodeToInfo[BB];
@@ -239,7 +309,8 @@
           if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
           continue;
         }
-
+        DEBUG(dbgs() << "[DFS]\t" << BlockNamePrinter(BB) << " -> "
+                     << BlockNamePrinter(Succ) << "\n");
         if (!Condition(BB, Succ)) continue;
 
         // It's fine to add Succ to the map, because we know that it will be
@@ -251,6 +322,7 @@
       }
     }
 
+    StatsHolder::IncNumNodesVisited(IsPostDom, LastNum - StartNum);
     return LastNum;
   }
 
@@ -549,6 +621,7 @@
   }
 
   static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) {
+    StatsHolder::IncNumRecalculated(IsPostDom);
     auto *Parent = DT.Parent;
     DT.reset();
     DT.Parent = Parent;
@@ -635,6 +708,7 @@
 
   static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
                          const NodePtr From, const NodePtr To) {
+    StatsHolder::IncNumInsertions(IsPostDom);
     assert((From || IsPostDom) &&
            "From has to be a valid CFG node or a virtual root");
     assert(To && "Cannot be a nullptr");
@@ -893,6 +967,7 @@
 
   static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
                          const NodePtr From, const NodePtr To) {
+    StatsHolder::IncNumDeletions(IsPostDom);
     assert(From && To && "Cannot disconnect nullptrs");
     DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> "
                  << BlockNamePrinter(To) << "\n");
@@ -1212,8 +1287,12 @@
 
     std::sort(Result.begin(), Result.end(),
               [&Operations](const UpdateT &A, const UpdateT &B) {
-                return Operations[{A.getFrom(), A.getTo()}] >
-                       Operations[{B.getFrom(), B.getTo()}];
+                const int AVal = Operations[{A.getFrom(), A.getTo()}];
+                const int BVal = Operations[{B.getFrom(), B.getTo()}];
+                const auto AKind = 1 - static_cast<unsigned char>(A.getKind());
+                const auto BKind = 1 - static_cast<unsigned char>(B.getKind());
+
+                return std::tie(AKind, AVal) > std::tie(BKind, BVal);
               });
   }
 
Index: lib/IR/Dominators.cpp
===================================================================
--- lib/IR/Dominators.cpp
+++ lib/IR/Dominators.cpp
@@ -91,6 +91,28 @@
 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
     const DomTreeBuilder::BBPostDomTree &DT);
 
+#define DEBUG_TYPE "dom-tree-stats"
+
+STATISTIC(NumDomRecalculated, "Number of DomTree recalculations");
+STATISTIC(NumPostDomRecalculated, "Number of PostDomTree recalculations");
+STATISTIC(NumDomInserted, "Number of edges inserted -- DomTree");
+STATISTIC(NumPostDomInserted, "Number of edges inserted -- PostDomTree");
+STATISTIC(NumDomDeleted, "Number of edges deleted -- DomTree");
+STATISTIC(NumPostDomDeleted, "Number of edges deleted -- PostDomTree");
+STATISTIC(NumDomVisited, "Number of nodes visited by DFS -- DomTree");
+STATISTIC(NumPostDomVisited, "Number of nodes visited by DFS -- PostDomTree");
+
+#undef DEBUG_TYPE
+
+static DomTreeBuilder::StatsHolder DomTreeBuilderStats(NumDomRecalculated,
+                                                       NumPostDomRecalculated,
+                                                       NumDomInserted,
+                                                       NumPostDomInserted,
+                                                       NumDomDeleted,
+                                                       NumPostDomDeleted,
+                                                       NumDomVisited,
+                                                       NumPostDomVisited);
+
 bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
                                FunctionAnalysisManager::Invalidator &) {
   // Check whether the analysis, all analyses on functions, or the function's