[WIP!][Dominators] Collect tree construction and update statistics

[kuhar]

Summary

NOTE: This is a work-in-progress patch and I don't intent to commit it. Please ignore it.

Short braindump:
The main problem with measuring performance of the incremental algorithm is that it is implemented entirely in a header file, inside a class template. A solution to that would be to just insert some timer calls and collect total elapsed times during update function calls, but that's a rather hacky solution.
A better measure of the cost of dominator tree construction and updates is the number of nodes visited during DFS walks, which has a nice property of being free of noise, which is not case with measuring just the execution time. In my local tests, counting visited nodes showed to correlate quite well with execution time.

To collect those statistics, I wanted to use the Statictic class, but the problem is that is requires to be declared as a global, so I decided to put it in lib/IR/DominatorTree.cpp. Now, it turns out, that there is also problem with static initialization order of Statistics and Timers when both try to produce json output. If Statistics get initialized first, they print timers as json upon destruction, but when opposite happens, Timers only print themselves in a tabular format, and then Statistics print themselves as json. The permanent fix for that would be to emit Statistics and Timers as separate Json objects and to make them not know about each other (too remove the dependency cycle).

[grosser]

I mark this as requesting changes such that it does not appear in my "to-review" queue. Looking forward to see this evolve.

include/llvm/Support/GenericDomTreeConstruction.h

 #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 
 #include <queue>
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
 #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"
 
 #define DEBUG_TYPE "dom-tree-builder"
 
 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;
   using NodeT = typename DomTreeT::NodeType;
   using TreeNodePtr = DomTreeNodeBase<NodeT> *;
   using RootsT = decltype(DomTreeT::Roots);
   static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
 
struct SemiNCAInfo {
   // edges for postdominators.
   template <bool IsReverse = false, typename DescendCondition>
   unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,
                   unsigned AttachToNum) {
     assert(V);
     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];
 
       // Visited nodes always have positive DFS numbers.
       if (BBInfo.DFSNum != 0) continue;
       BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
       BBInfo.Label = BB;
       NumToNode.push_back(BB);
 
       constexpr bool Direction = IsReverse != IsPostDom;  // XOR.
       for (const NodePtr Succ :
            ChildrenGetter<Direction>::Get(BB, BatchUpdates)) {
         const auto SIT = NodeToInfo.find(Succ);
         // Don't visit nodes more than once but remember to collect
         // ReverseChildren.
         if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
           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
         // visited later.
         auto &SuccInfo = NodeToInfo[Succ];
         WorkList.push_back(Succ);
         SuccInfo.Parent = LastNum;
         SuccInfo.ReverseChildren.push_back(BB);
       }
     }
 
+    StatsHolder::IncNumNodesVisited(IsPostDom, LastNum - StartNum);
     return LastNum;
   }
 
   NodePtr eval(NodePtr VIn, unsigned LastLinked) {
     auto &VInInfo = NodeToInfo[VIn];
     if (VInInfo.DFSNum < LastLinked)
       return VIn;
 
void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
     }
 
     addVirtualRoot();
     unsigned Num = 1;
     for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0);
   }
 
   static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) {
+    StatsHolder::IncNumRecalculated(IsPostDom);
     auto *Parent = DT.Parent;
     DT.reset();
     DT.Parent = Parent;
     SemiNCAInfo SNCA(nullptr);  // Since we are rebuilding the whole tree,
                                 // there's no point doing it incrementally.
 
     // Step #0: Number blocks in depth-first order and initialize variables used
     // in later stages of the algorithm.
struct InsertionInfo {
     SmallDenseSet<TreeNodePtr, 8> Affected;
     SmallDenseSet<TreeNodePtr, 8> Visited;
     SmallVector<TreeNodePtr, 8> AffectedQueue;
     SmallVector<TreeNodePtr, 8> VisitedNotAffectedQueue;
   };
 
   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");
     DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> "
                  << BlockNamePrinter(To) << "\n");
     TreeNodePtr FromTN = DT.getNode(From);
 
     if (!FromTN) {
static void ComputeUnreachableDominators(
     SNCA.attachNewSubtree(DT, Incoming);
 
     DEBUG(dbgs() << "After adding unreachable nodes\n");
     DEBUG(DT.print(dbgs()));
   }
 
   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");
 
 #ifndef NDEBUG
     // Ensure that the edge was in fact deleted from the CFG before informing
     // the DomTree about it.
     // The check is O(N), so run it only in debug configuration.
for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) {
       if (!IsPostDom)
         Operations[{U.getFrom(), U.getTo()}] = int(i);
       else
         Operations[{U.getTo(), U.getFrom()}] = int(i);
     }
 
     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);
               });
   }
 
   static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) {
     assert(!BUI.Updates.empty() && "No updates to apply!");
     UpdateT CurrentUpdate = BUI.Updates.pop_back_val();
     DEBUG(dbgs() << "Applying update: " << CurrentUpdate << "\n");
 

lib/IR/Dominators.cpp

 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
     DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBUpdates);
 
 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
     const DomTreeBuilder::BBDomTree &DT);
 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
   // CFG have been preserved.
   auto PAC = PA.getChecker<DominatorTreeAnalysis>();
   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
            PAC.preservedSet<CFGAnalyses>());
 }