Replace custom written DFS walk with depth first iterator

[• dberlin]

Summary

GenericDomTreeConstruction had its own written DFS walk.
It is basically identical to the DFS walk df_* is doing in the iterators.
the one difference is that df_iterator uses an internal visited set.
The GenericDomTreeConstruction one reused a field in an existing densemap lookup.

Time-wise, this way is actually more cache-friendly (the previous way has a random store
into a successor's info, the new way does that store at the same time and in the same place
as other stores to the same info)

It costs some very small amount of memory to do this, and one we pay in some other part of
dom tree construction *anyway*, so we aren't really increasing dom tree constructions's
peak memory usage.

It could still be changed to use the old field with a little work on df_ext_* if we care
(and if someone find performance regressions)

[chandlerc]

LGTM. Yay deleting code.

[Eugene.Zelenko]

Looks like patch was not committed.

[• dberlin]

Update to fix parent bug

[• dberlin]

Sigh

[• dberlin]

I'm going to reopen this. The postdom bug in 24415 is much easier to fix if we go with this.
As that bug says, i'm going to make the visited set external, to remove the small slowdown this patch has, and then properly add roots during DFS finding.

[• dberlin]

• Update to use external storage, removing performance difference vs current code.

[• dberlin]

As a followup, i will fix 24415 and i believe that will re-merge these two DFS functions.

include/llvm/Support/GenericDomTreeConstruction.h

 /// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs.
 ///
 //===----------------------------------------------------------------------===//
 
 
 #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 
+#include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/GenericDomTree.h"
 
 namespace llvm {
 
-template<class GraphT>
-unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT,
-                 typename GraphT::NodeType* V, unsigned N) {
-  // This is more understandable as a recursive algorithm, but we can't use the
-  // recursive algorithm due to stack depth issues.  Keep it here for
-  // documentation purposes.
-#if 0
-  InfoRec &VInfo = DT.Info[DT.Roots[i]];
-  VInfo.DFSNum = VInfo.Semi = ++N;
-  VInfo.Label = V;
-
-  Vertex.push_back(V);        // Vertex[n] = V;
-
-  for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) {
-    InfoRec &SuccVInfo = DT.Info[*SI];
-    if (SuccVInfo.Semi == 0) {
-      SuccVInfo.Parent = V;
-      N = DTDFSPass(DT, *SI, N);
-    }
-  }
-#else
+template <class GraphT>
+unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType> &DT,
+                 typename GraphT::NodeType *V, unsigned N) {
   bool IsChildOfArtificialExit = (N != 0);
-
-  SmallVector<std::pair<typename GraphT::NodeType*,
-                        typename GraphT::ChildIteratorType>, 32> Worklist;
-  Worklist.push_back(std::make_pair(V, GraphT::child_begin(V)));
-  while (!Worklist.empty()) {
-    typename GraphT::NodeType* BB = Worklist.back().first;
-    typename GraphT::ChildIteratorType NextSucc = Worklist.back().second;
-
+  for (auto I = df_begin(V), E = df_end(V); I != E; ++I) {
+    typename GraphT::NodeType *BB = *I;
     typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &BBInfo =
-                                                                    DT.Info[BB];
-
-    // First time we visited this BB?
-    if (NextSucc == GraphT::child_begin(BB)) {
-      BBInfo.DFSNum = BBInfo.Semi = ++N;
-      BBInfo.Label = BB;
-
-      DT.Vertex.push_back(BB);       // Vertex[n] = V;
+    // Set the parent to the top of the visited stack
+    BBInfo.Parent = DT.Info[I.getPath(I.getPathLength() - 1)].DFSNum;
+    DT.Vertex.push_back(BB); // Vertex[n] = V;
 
-      if (IsChildOfArtificialExit)
-        BBInfo.Parent = 1;
 
-      IsChildOfArtificialExit = false;
-    }
-
-    // store the DFS number of the current BB - the reference to BBInfo might
-    // get invalidated when processing the successors.
-    unsigned BBDFSNum = BBInfo.DFSNum;
-
-    // If we are done with this block, remove it from the worklist.
-    if (NextSucc == GraphT::child_end(BB)) {
-      Worklist.pop_back();
-      continue;
-    }
-
-    // Increment the successor number for the next time we get to it.
-    ++Worklist.back().second;
-    
-    // Visit the successor next, if it isn't already visited.
-    typename GraphT::NodeType* Succ = *NextSucc;
-
-    typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &SuccVInfo =
-                                                                  DT.Info[Succ];
-    if (SuccVInfo.Semi == 0) {
-      SuccVInfo.Parent = BBDFSNum;
-      Worklist.push_back(std::make_pair(Succ, GraphT::child_begin(Succ)));
-    }
-  }
-#endif
-    return N;
 }
 
 template<class GraphT>
 typename GraphT::NodeType* 
 Eval(DominatorTreeBase<typename GraphT::NodeType>& DT,
      typename GraphT::NodeType *VIn, unsigned LastLinked) {
   typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInInfo =
                                                                   DT.Info[VIn];