[Dominators] Use a custom DFS implementation

[kuhar]

Summary

Custom DFS implementation allows us to skip over certain nodes without adding them to the visited map, which is not easily doable with llvm's dfs iterators. What's more, caching predecessors becomes easy.

This patch implements a single DFS function (template) for both forward and reverse DFS, which should be easier to maintain then separate two ones.

Skipping over nodes based on a predicate will be necessary later to implement incremental updates.

There also seems to be a very slight performance improved when bootstrapping clang with this patch on my machine (3:28s -> 3:26s) .

[kuhar]

Format patch

[kuhar]

Remove unused alias declaration

[• dberlin]

So, just to note: It's generally nonsense to try to calculate the root list prior to DFS (and a source of bugs in the current postdominator tree). By nonsense i mean "impossible".
You need to see what's reachable to know what ends up needing to be connected to a virtual root.

[kuhar]

Update the diff so that it applies cleanly.

[• dberlin]

At some point we should make the DFS iterators more flexible, but i don't think we need to design that for this

[kuhar]

Update the diff to apply cleanly.

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

 
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/GenericDomTree.h"
 
 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));
+  }
+};
+
+template <typename NodePtr>
+struct ChildrenGetter<NodePtr, true> {
+  static auto Get(NodePtr N) -> decltype(inverse_children<NodePtr>(N)) {
+    return inverse_children<NodePtr>(N);
+  }
+};
+
 // Information record used by Semi-NCA during tree construction.
 template <typename NodeT>
 struct SemiNCAInfo {
   using NodePtr = NodeT *;
   using DomTreeT = DominatorTreeBase<NodeT>;
   using TreeNodePtr = DomTreeNodeBase<NodeT> *;
 
   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;
   DenseMap<NodePtr, InfoRec> NodeToInfo;
 
   void clear() {
     NumToNode.clear();
     NodeToInfo.clear();
TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT) {
 
     // Add a new tree node for this NodeT, and link it as a child of
     // IDomNode
     return (DT.DomTreeNodes[BB] = IDomNode->addChild(
                 llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode)))
         .get();
   }
 
-  // External storage for depth first iterator that reuses the info lookup map
-  // SemiNCAInfo already has. We don't have a set, but a map instead, so we are
-  // converting the one argument insert calls.
-  struct df_iterator_dom_storage {
-   public:
-    using BaseSet = decltype(NodeToInfo);
-    df_iterator_dom_storage(BaseSet &Storage) : Storage(Storage) {}
-
-    using iterator = typename BaseSet::iterator;
-    std::pair<iterator, bool> insert(NodePtr N) {
-      return Storage.insert({N, InfoRec()});
-    }
-    void completed(NodePtr) {}
-
-   private:
-    BaseSet &Storage;
-  };
+  static bool AlwaysDescend(NodePtr, NodePtr) { return true; }
 
-  df_iterator_dom_storage getStorage() { return {NodeToInfo}; }
+  // Custom DFS implementation which can skip nodes based on a provided
+  // predicate. It also collects ReverseChildren so that we don't have to spend
+  // time getting predecessors in SemiNCA.
+  template <bool Inverse, 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;
 
-  unsigned runReverseDFS(NodePtr V, unsigned N) {
-    auto DFStorage = getStorage();
-
-    bool IsChildOfArtificialExit = (N != 0);
-    for (auto I = idf_ext_begin(V, DFStorage), E = idf_ext_end(V, DFStorage);
-         I != E; ++I) {
-      NodePtr BB = *I;
+    while (!WorkList.empty()) {
+      const NodePtr BB = WorkList.pop_back_val();
       auto &BBInfo = NodeToInfo[BB];
-      BBInfo.DFSNum = BBInfo.Semi = ++N;
-      BBInfo.Label = BB;
-      // Set the parent to the top of the visited stack.  The stack includes us,
-      // and is 1 based, so we subtract to account for both of these.
-      if (I.getPathLength() > 1)
-        BBInfo.Parent = NodeToInfo[I.getPath(I.getPathLength() - 2)].DFSNum;
-      NumToNode.push_back(BB);  // NumToNode[n] = V;
 
-      if (IsChildOfArtificialExit)
-        BBInfo.Parent = 1;
+      // Visited nodes always have positive DFS numbers.
+      if (BBInfo.DFSNum != 0) continue;
+      BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
+      BBInfo.Label = BB;
+      NumToNode.push_back(BB);
 
-      IsChildOfArtificialExit = false;
-    }
-    return N;
+      for (const NodePtr Succ : ChildrenGetter<NodePtr, Inverse>::Get(BB)) {
+        const auto SIT = NodeToInfo.find(Succ);
+        // Don't visit nodes more than once but remember to collect
+        // RerverseChildren.
+        if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
+          if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
+          continue;
         }
 
-  unsigned runForwardDFS(NodePtr V, unsigned N) {
-    auto DFStorage = getStorage();
+        if (!Condition(BB, Succ)) continue;
 
-    for (auto I = df_ext_begin(V, DFStorage), E = df_ext_end(V, DFStorage);
-         I != E; ++I) {
-      NodePtr BB = *I;
-      auto &BBInfo = NodeToInfo[BB];
-      BBInfo.DFSNum = BBInfo.Semi = ++N;
-      BBInfo.Label = BB;
-      // Set the parent to the top of the visited stack.  The stack includes us,
-      // and is 1 based, so we subtract to account for both of these.
-      if (I.getPathLength() > 1)
-        BBInfo.Parent = NodeToInfo[I.getPath(I.getPathLength() - 2)].DFSNum;
-      NumToNode.push_back(BB);  // NumToNode[n] = V;
+        // 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);
       }
-    return N;
     }
 
+    return LastNum;
+  };
+
   NodePtr eval(NodePtr VIn, unsigned LastLinked) {
     auto &VInInfo = NodeToInfo[VIn];
     if (VInInfo.DFSNum < LastLinked)
       return VIn;
 
     SmallVector<NodePtr, 32> Work;
     SmallPtrSet<NodePtr, 32> Visited;
 
while (!Work.empty()) {
       VInfo.Parent = VAInfo.Parent;
     }
 
     return VInInfo.Label;
   }
 
   template <typename NodeType>
   void runSemiNCA(DomTreeT &DT, unsigned NumBlocks) {
-    unsigned N = 0;
-    NumToNode.push_back(nullptr);
-
-    bool MultipleRoots = (DT.Roots.size() > 1);
-    if (MultipleRoots) {
-      auto &BBInfo = NodeToInfo[nullptr];
-      BBInfo.DFSNum = BBInfo.Semi = ++N;
-      BBInfo.Label = nullptr;
-
-      NumToNode.push_back(nullptr); // NumToNode[n] = V;
-    }
-
     // Step #1: Number blocks in depth-first order and initialize variables used
     // in later stages of the algorithm.
-    if (DT.isPostDominator()){
-      for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size());
-           i != e; ++i)
-        N = runReverseDFS(DT.Roots[i], N);
-    } else {
-      N = runForwardDFS(DT.Roots[0], N);
-    }
+    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.
-    MultipleRoots |= (DT.isPostDominator() && N != NumBlocks);
+    const bool MultipleRoots =
+        DT.Roots.size() > 1 || (DT.isPostDominator() && N != NumBlocks);
 
     // Initialize IDoms to spanning tree parents.
     for (unsigned i = 1; i <= N; ++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) {
       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 : inverse_children<NodeType>(W))
+      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;
         }
     }
 
     // Step #3: Explicitly define the immediate dominator of each vertex.
for (unsigned i = 2; i <= N; ++i) {
 
       // 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));
     }
   }
 
-  void doFullDFSWalk(const DomTreeT &DT) {
-    NumToNode.push_back(nullptr);
+  template <typename DescendCondition>
+  unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
     unsigned Num = 0;
-    for (auto *Root : DT.Roots)
-      if (!DT.isPostDominator())
-        Num = runForwardDFS(Root, Num);
-      else
-        Num = runReverseDFS(Root, Num);
+    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.
   bool verifyReachability(const DomTreeT &DT) {
     clear();
-    doFullDFSWalk(DT);
+    doFullDFSWalk(DT, AlwaysDescend);
 
     for (auto &NodeToTN : DT.DomTreeNodes) {
       const TreeNodePtr TN = NodeToTN.second.get();
       const NodePtr BB = TN->getBlock();
       if (!BB) continue;
 
       if (NodeToInfo.count(BB) == 0) {
         errs() << "DomTree node ";
static bool VerifyLevels(const DomTreeT &DT) {
 
     return true;
   }
 
   // Checks if for every edge From -> To in the graph
   //     NCD(From, To) == IDom(To) or To.
   bool verifyNCD(const DomTreeT &DT) {
     clear();
-    doFullDFSWalk(DT);
+    doFullDFSWalk(DT, AlwaysDescend);
 
     for (auto &BlockToInfo : NodeToInfo) {
       auto &Info = BlockToInfo.second;
 
       const NodePtr From = NumToNode[Info.Parent];
       if (!From) continue;
 
       const NodePtr To = BlockToInfo.first;
struct SemiNCAInfo {
   // the nodes it dominated previously will now become unreachable.
   bool verifyParentProperty(const DomTreeT &DT) {
     for (auto &NodeToTN : DT.DomTreeNodes) {
       const TreeNodePtr TN = NodeToTN.second.get();
       const NodePtr BB = TN->getBlock();
       if (!BB || TN->getChildren().empty()) continue;
 
       clear();
-      NodeToInfo.insert({BB, {}});
-      doFullDFSWalk(DT);
+      doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) {
+        return From != BB && To != BB;
+      });
 
       for (TreeNodePtr Child : TN->getChildren())
         if (NodeToInfo.count(Child->getBlock()) != 0) {
           errs() << "Child ";
           PrintBlockOrNullptr(errs(), Child->getBlock());
           errs() << " reachable after its parent ";
           PrintBlockOrNullptr(errs(), BB);
           errs() << " is removed!\n";
bool verifySiblingProperty(const DomTreeT &DT) {
     for (auto &NodeToTN : DT.DomTreeNodes) {
       const TreeNodePtr TN = NodeToTN.second.get();
       const NodePtr BB = TN->getBlock();
       if (!BB || TN->getChildren().empty()) continue;
 
       const auto &Siblings = TN->getChildren();
       for (const TreeNodePtr N : Siblings) {
         clear();
-        NodeToInfo.insert({N->getBlock(), {}});
-        doFullDFSWalk(DT);
+        NodePtr BBN = N->getBlock();
+        doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) {
+          return From != BBN && To != BBN;
+        });
 
         for (const TreeNodePtr S : Siblings) {
           if (S == N) continue;
 
           if (NodeToInfo.count(S->getBlock()) == 0) {
             errs() << "Node ";
             PrintBlockOrNullptr(errs(), S->getBlock());
             errs() << " not reachable when its sibling ";