[Dominators] Split SemiNCA into smaller functions

[kuhar]

Summary

This patch splits the SemiNCA algorithm into smaller functions. It also adds a new debug macro.

In order to perform incremental updates, we need to be able to refire SemiNCA on a subset of CFG nodes (determined by a DFS walk results). We also need to skip nodes that are not deep enough in a DomTree.

[• dberlin]

include/llvm/Support/GenericDomTreeConstruction.h

34

Why doesn't #define DEBUG_TYPE work?

69

Why?

73

Why?

205

I'd rewrite this comment to "Skip predecessors whose level is above the subtree we are processing"

[kuhar]

include/llvm/Support/GenericDomTreeConstruction.h

34

The macro can clash with DEBUG_TYPE in a file including it. Is it better change it to DEBUG_TYPE and undef it at the bottom of this header?

[davide]

include/llvm/Support/GenericDomTreeConstruction.h

34

This seems to be symptom of a more general problem, there shouldn't be clashes. Which file is actually defining another dom-tree-builder ?

[kuhar]

Added comments explaining that NumToNode is 1-based. Fixed the DEBUG macros.

[kuhar]

include/llvm/Support/GenericDomTreeConstruction.h

34

You were absolutely right. MachineCombiner defined the DEBUG_TYPE *before* including headers, and that was the root cause.

[• dberlin]

You should submit the machinecombiner change separately, but otherwise okay.

[davide]

Looks good to me as well (agree that the machinecombiner bit should be separated, you can do that without pre-commit review, it's a no-brainer [assuming it doesn't break anything :)]

[kuhar]

I fixed MachineCombiner in r307940 and a few places within Target/Hexagon in r307947.

[kuhar]

Remove MachineCombiner changes.

include/llvm/Support/GenericDomTreeConstruction.h

 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Support/Debug.h"
 #include "llvm/Support/GenericDomTree.h"
 
+#define DTB_DEBUG_TYPE "dom-tree-builder"
+#define DTB_DEBUG(Arg) DEBUG_WITH_TYPE(DTB_DEBUG_TYPE, Arg)
+
 namespace llvm {
 namespace DomTreeBuilder {
 
 template <typename NodePtr, bool Inverse>
 struct ChildrenGetter {
   static auto Get(NodePtr N) -> decltype(reverse(children<NodePtr>(N))) {
     return reverse(children<NodePtr>(N));
   }
struct InfoRec {
     unsigned DFSNum = 0;
     unsigned Parent = 0;
     unsigned Semi = 0;
     NodePtr Label = nullptr;
     NodePtr IDom = nullptr;
     SmallVector<NodePtr, 2> ReverseChildren;
   };
 
-  std::vector<NodePtr> NumToNode;
+  std::vector<NodePtr> NumToNode = {nullptr};
   DenseMap<NodePtr, InfoRec> NodeToInfo;
 
   void clear() {
-    NumToNode.clear();
+    NumToNode = {nullptr};
     NodeToInfo.clear();
   }
 
   NodePtr getIDom(NodePtr BB) const {
     auto InfoIt = NodeToInfo.find(BB);
     if (InfoIt == NodeToInfo.end()) return nullptr;
 
     return InfoIt->second.IDom;
while (!Work.empty()) {
       if (NodeToInfo[VAncestorLabel].Semi < NodeToInfo[VLabel].Semi)
         VInfo.Label = VAncestorLabel;
       VInfo.Parent = VAInfo.Parent;
     }
 
     return VInInfo.Label;
   }
 
-  template <typename NodeType>
-  void runSemiNCA(DomTreeT &DT, unsigned NumBlocks) {
-    // Step #1: Number blocks in depth-first order and initialize variables used
-    // in later stages of the algorithm.
-    const unsigned N = doFullDFSWalk(DT, AlwaysDescend);
-
-    // 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.
-    const bool MultipleRoots =
-        DT.Roots.size() > 1 || (DT.isPostDominator() && N != NumBlocks);
-
+  void runSemiNCA(DomTreeT &DT, const unsigned MinLevel = 0) {
+    const unsigned NextDFSNum(NumToNode.size());
     // Initialize IDoms to spanning tree parents.
-    for (unsigned i = 1; i <= N; ++i) {
+    for (unsigned i = 1; i < NextDFSNum; ++i) {
       const NodePtr V = NumToNode[i];
       auto &VInfo = NodeToInfo[V];
       VInfo.IDom = NumToNode[VInfo.Parent];
     }
 
-    // Step #2: Calculate the semidominators of all vertices.
-    for (unsigned i = N; i >= 2; --i) {
+    // Step #1: Calculate the semidominators of all vertices.
+    for (unsigned i = NextDFSNum - 1; i >= 2; --i) {
       NodePtr W = NumToNode[i];
       auto &WInfo = NodeToInfo[W];
 
       // Initialize the semi dominator to point to the parent node.
       WInfo.Semi = WInfo.Parent;
-      for (const auto &N : WInfo.ReverseChildren)
-        if (NodeToInfo.count(N)) {  // Only if this predecessor is reachable!
-          unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi;
-          if (SemiU < WInfo.Semi)
-            WInfo.Semi = SemiU;
-        }
+      for (const auto &N : WInfo.ReverseChildren) {
+        if (NodeToInfo.count(N) == 0)  // Skip unreachable predecessors.
+          continue;
+
+        const TreeNodePtr TN = DT.getNode(N);
+        if (TN && TN->getLevel() < MinLevel)  // Skip too shallow predecessors.
+          continue;
+
+        if (SemiU < WInfo.Semi) WInfo.Semi = SemiU;
     }
 
-    // Step #3: Explicitly define the immediate dominator of each vertex.
+    // Step #2: 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) {
+    for (unsigned i = 2; i < NextDFSNum; ++i) {
       const NodePtr W = NumToNode[i];
       auto &WInfo = NodeToInfo[W];
       const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;
       NodePtr WIDomCandidate = WInfo.IDom;
       while (NodeToInfo[WIDomCandidate].DFSNum > SDomNum)
         WIDomCandidate = NodeToInfo[WIDomCandidate].IDom;
 
       WInfo.IDom = WIDomCandidate;
     }
+  }
+
+  template <typename DescendCondition>
+  unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
+    unsigned Num = 0;
+
+    if (DT.Roots.size() > 1) {
+      auto &BBInfo = NodeToInfo[nullptr];
+      BBInfo.DFSNum = BBInfo.Semi = ++Num;
+      BBInfo.Label = nullptr;
+
+      NumToNode.push_back(nullptr);  // NumToNode[n] = V;
+    }
+
+    if (DT.isPostDominator()) {
+      for (auto *Root : DT.Roots) Num = runDFS<true>(Root, Num, DC, 1);
+    } else {
+      assert(DT.Roots.size() == 1);
+      Num = runDFS<false>(DT.Roots[0], Num, DC, Num);
+    }
+
+    return Num;
+  }
+
+  void calculateFromScratch(DomTreeT &DT, const unsigned NumBlocks) {
+    // Step #0: Number blocks in depth-first order and initialize variables used
+    // in later stages of the algorithm.
+    const unsigned LastDFSNum = doFullDFSWalk(DT, AlwaysDescend);
+
+    runSemiNCA(DT);
 
     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.
+    // 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.
+    const bool MultipleRoots = DT.Roots.size() > 1 || (DT.isPostDominator() &&
+                                                       LastDFSNum != NumBlocks);
     NodePtr Root = !MultipleRoots ? DT.Roots[0] : nullptr;
 
-    DT.RootNode =
-        (DT.DomTreeNodes[Root] =
+    DT.RootNode = (DT.DomTreeNodes[Root] =
                        llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
-            .get();
+    attachNewSubtree(DT, DT.RootNode);
+  }
 
-    // Loop over all of the reachable blocks in the function...
-    for (unsigned i = 2; i <= N; ++i) {
+  void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {
+    // Attach the first unreachable block to AttachTo.
+    NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
+    // Loop over all of the discovered blocks in the function...
+    for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
       NodePtr W = NumToNode[i];
+      DTB_DEBUG(dbgs() << "\tdiscovereed a new reachable node ");
+      DTB_DEBUG(PrintBlockOrNullptr(dbgs(), W));
+      DTB_DEBUG(dbgs() << "\n");
 
       // Don't replace this with 'count', the insertion side effect is important
-      if (DT.DomTreeNodes[W])
-        continue; // Haven't calculated this node yet?
+      if (DT.DomTreeNodes[W]) continue;  // Haven't calculated this node yet?
 
       NodePtr ImmDom = getIDom(W);
 
-      assert(ImmDom || DT.DomTreeNodes[nullptr]);
-
       // Get or calculate the node for the immediate dominator
       TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
 
       // Add a new tree node for this BasicBlock, and link it as a child of
       // IDomNode
       DT.DomTreeNodes[W] = IDomNode->addChild(
           llvm::make_unique<DomTreeNodeBase<NodeT>>(W, IDomNode));
     }
   }
 
-  template <typename DescendCondition>
-  unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
-    unsigned Num = 0;
-    NumToNode.push_back(nullptr);
-
-    if (DT.Roots.size() > 1) {
-      auto &BBInfo = NodeToInfo[nullptr];
-      BBInfo.DFSNum = BBInfo.Semi = ++Num;
-      BBInfo.Label = nullptr;
-
-      NumToNode.push_back(nullptr);  // NumToNode[n] = V;
-    }
-
-    if (DT.isPostDominator()) {
-      for (auto *Root : DT.Roots) Num = runDFS<true>(Root, Num, DC, 1);
-    } else {
-      assert(DT.Roots.size() == 1);
-      Num = runDFS<false>(DT.Roots[0], Num, DC, Num);
-    }
-
-    return Num;
-  }
-
   static void PrintBlockOrNullptr(raw_ostream &O, NodePtr Obj) {
     if (!Obj)
       O << "nullptr";
     else
       Obj->printAsOperand(O, false);
   }
 
   // Checks if the tree contains all reachable nodes in the input graph.

 
 template <class FuncT, class NodeT>
 void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT,
                FuncT &F) {
   using NodePtr = typename GraphTraits<NodeT>::NodeRef;
   static_assert(std::is_pointer<NodePtr>::value,
                 "NodePtr should be a pointer type");
   SemiNCAInfo<typename std::remove_pointer<NodePtr>::type> SNCA;
-  SNCA.template runSemiNCA<NodeT>(DT, GraphTraits<FuncT *>::size(&F));
+  SNCA.calculateFromScratch(DT, GraphTraits<FuncT *>::size(&F));
 }
 
 template <class NodeT>
 bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT) {
   using NodePtr = typename GraphTraits<NodeT>::NodeRef;
   static_assert(std::is_pointer<NodePtr>::value,
                 "NodePtr should be a pointer type");
   SemiNCAInfo<typename std::remove_pointer<NodePtr>::type> SNCA;