[Dominators] Use Semi-NCA instead of SLT to calculate dominators

[kuhar]

Summary

This patch makes GenericDomTreeConstruction use the Semi-NCA algorithm instead of Simple Lengauer-Tarjan.

As described in RFC: Dynamic dominators, Semi-NCA offers slightly better performance than SLT. What's more important, it can be extended to perform incremental updates on already constructed dominator trees.

The patch passes check-all, llvm test suite and is able to boostrap clang. I also wasn't able to observe any compilation time regressions.

[kuhar]

include/llvm/Support/GenericDomTreeConstruction.h

143 ↗

(On Diff #102739)

This should be moved to the header.

[kuhar]

Move algorithm attribution to the header.

[• dberlin]

Given we haven't found anything fuzzing wise, i think it's fine to land this, but let's watch out for performance regressions and be ready to revert if we need to.

include/llvm/Support/GenericDomTreeConstruction.h

209 ↗

(On Diff #102920)

Typo: should be WIDomCandidate

llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h

 //===- GenericDomTreeConstruction.h - Dominator Calculation ------*- C++ -*-==//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 /// \file
 ///
 /// Generic dominator tree construction - This file provides routines to
 /// construct immediate dominator information for a flow-graph based on the
-/// algorithm described in this document:
+/// Semi-NCA algorithm described in this dissertation:
 ///
-///   A Fast Algorithm for Finding Dominators in a Flowgraph
-///   T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141.
+///   Linear-Time Algorithms for Dominators and Related Problems
+///   Loukas Georgiadis, Princeton University, November 2005, pp. 21-23:
+///   ftp://ftp.cs.princeton.edu/reports/2005/737.pdf
 ///
 /// This implements the O(n*log(n)) versions of EVAL and LINK, because it turns
 /// out that the theoretically slower O(n*log(n)) implementation is actually
 /// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT,
   if (DT.isPostDominator()){
     for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size());
          i != e; ++i)
       N = ReverseDFSPass<GraphT>(DT, DT.Roots[i], N);
   } else {
     N = DFSPass<GraphT>(DT, DT.Roots[0], N);
   }
 
-  // it might be that some blocks did not get a DFS number (e.g., blocks of
+  // It might be that some blocks did not get a DFS number (e.g., blocks of
   // infinite loops). In these cases an artificial exit node is required.
   MultipleRoots |= (DT.isPostDominator() && N != GraphTraits<FuncT*>::size(&F));
 
-  // When naively implemented, the Lengauer-Tarjan algorithm requires a separate
-  // bucket for each vertex. However, this is unnecessary, because each vertex
-  // is only placed into a single bucket (that of its semidominator), and each
-  // vertex's bucket is processed before it is added to any bucket itself.
-  //
-  // Instead of using a bucket per vertex, we use a single array Buckets that
-  // has two purposes. Before the vertex V with preorder number i is processed,
-  // Buckets[i] stores the index of the first element in V's bucket. After V's
-  // bucket is processed, Buckets[i] stores the index of the next element in the
-  // bucket containing V, if any.
-  SmallVector<unsigned, 32> Buckets;
-  Buckets.resize(N + 1);
-  for (unsigned i = 1; i <= N; ++i)
-    Buckets[i] = i;
+  // Initialize IDoms to spanning tree parents.
+  for (unsigned i = 1; i <= N; ++i) {
+    const NodePtr V = DT.Vertex[i];
+    DT.IDoms[V] = DT.Vertex[DT.Info[V].Parent];
+  }
 
+  // Step #2: Calculate the semidominators of all vertices.
   for (unsigned i = N; i >= 2; --i) {
     NodePtr W = DT.Vertex[i];
     auto &WInfo = DT.Info[W];
 
-    // Step #2: Implicitly define the immediate dominator of vertices
-    for (unsigned j = i; Buckets[j] != i; j = Buckets[j]) {
-      NodePtr V = DT.Vertex[Buckets[j]];
-      NodePtr U = Eval<GraphT>(DT, V, i + 1);
-      DT.IDoms[V] = DT.Info[U].Semi < i ? U : W;
-    }
-
-    // Step #3: Calculate the semidominators of all vertices
-
-    // initialize the semi dominator to point to the parent node
+    // Initialize the semi dominator to point to the parent node.
     WInfo.Semi = WInfo.Parent;
     for (const auto &N : inverse_children<NodeT>(W))
       if (DT.Info.count(N)) { // Only if this predecessor is reachable!
         unsigned SemiU = DT.Info[Eval<GraphT>(DT, N, i + 1)].Semi;
         if (SemiU < WInfo.Semi)
           WInfo.Semi = SemiU;
       }
-
-    // If V is a non-root vertex and sdom(V) = parent(V), then idom(V) is
-    // necessarily parent(V). In this case, set idom(V) here and avoid placing
-    // V into a bucket.
-    if (WInfo.Semi == WInfo.Parent) {
-      DT.IDoms[W] = DT.Vertex[WInfo.Parent];
-    } else {
-      Buckets[i] = Buckets[WInfo.Semi];
-      Buckets[WInfo.Semi] = i;
-    }
   }
 
-  if (N >= 1) {
-    NodePtr Root = DT.Vertex[1];
-    for (unsigned j = 1; Buckets[j] != 1; j = Buckets[j]) {
-      NodePtr V = DT.Vertex[Buckets[j]];
-      DT.IDoms[V] = Root;
-    }
-  }
 
-  // Step #4: Explicitly define the immediate dominator of each vertex
+  // Step #3: Explicitly define the immediate dominator of each vertex.
+  //          IDom[i] = NCA(SDom[i], SpanningTreeParent(i)).
+  // Note that the parents were stored in IDoms and later got invalidated during
+  // path compression in Eval.
   for (unsigned i = 2; i <= N; ++i) {
-    NodePtr W = DT.Vertex[i];
-    NodePtr &WIDom = DT.IDoms[W];
-    if (WIDom != DT.Vertex[DT.Info[W].Semi])
-      WIDom = DT.IDoms[WIDom];
+    const NodePtr W = DT.Vertex[i];
+    const auto &WInfo = DT.Info[W];
+    const unsigned SDomNum = DT.Info[DT.Vertex[WInfo.Semi]].DFSNum;
+    NodePtr WIDomCandidate = DT.IDoms[W];
+    while (DT.Info[WIDomCandidate].DFSNum > SDomNum)
+      WIDomCandidate = DT.IDoms[WIDomCandidate];
+
+    DT.IDoms[W] = WIDomCandidate;
   }
 
   if (DT.Roots.empty()) return;
 
   // Add a node for the root.  This node might be the actual root, if there is
   // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0)
   // which postdominates all real exits if there are multiple exit blocks, or
   // an infinite loop.