Make updateDFSNumbers API public

[• dberlin]

Summary

There are a number of passes that could be sped up by using dominator tree DFS numbers to order or compare things across multiple bbs
(MemorySSA, MergedLoadStoreMotion, EarlyCSE, Sinking, GVN, NewGVN, for starters :P).

For example, GVN/CSE elimination can be done with a simple stack/etc (instead of full-on scoped hash table or repeated leader set walks)

if the DFS pair is stored next to leaders.

The dominator tree keeps them, and the DOM tree nodes expose them as public, but you have no guarantee they are up to date (and in fact,
if you split blocks or whatever during your pass, they definitely won't be)

This means passes either have to compute their own versions[1], or make 32 queries, or ....
Rather than try to hide this, i just made the API public, and make it do nothing if the numbers are already valid.

[1] Which we want as a non-recursive walk, which is not pretty, sadly,
because it cannot use the depth first iterators since you don't get called on the way back up. So you either have to do one walk with po_iterator
and one with df_iterator, or write your own non-recursive walk that looks identical to the one in updateDFSNumbers.

[• dberlin]

It looks like it generated the stupidest diff possible for this change.

In reality, what happened is i moved the updateDFSNumbers below the
public: line.

Instead, it generated a diff that makes it look like i moved everything up.
:)

[chandlerc]

LGTM. We should consider documenting this and teaching people to use it like they would use vector::reserve when they *know* they're going to make mor ethan 32 queries and it doesn't make sense to have the first 32 be slow.

[• dberlin]

Not recalculating if valid exposes a bug in maintenance of the DFSInfoValid
flag (which is very hard to trigger, but expensive debugging has a check
that catches it on two out of the 13000 testcases we have because it
requires passes to recalculate the dom tree and then do something with it)

I am submitting the change without that part (IE just moving
updateDFSNumbers), then submitting a bug fix (coming) to maintain the flag
properly and add the check back along with a unit test.

The bug is that GenericDomTree::recalculate never sets DFSInfoValid =
false, but calls DT.updateDFSNumbers at the end, expecting it will always
recalculate the DFS numbers.

llvm/trunk/include/llvm/Support/GenericDomTree.h

protected:
   template <class GraphT>
   friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType> &DT,
                           typename GraphT::NodeType *V, unsigned N);
 
   template <class FuncT, class N>
   friend void
   Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType> &DT, FuncT &F);
 
+
+  DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
+    if (DomTreeNodeBase<NodeT> *Node = getNode(BB))
+      return Node;
+
+    // Haven't calculated this node yet?  Get or calculate the node for the
+    // immediate dominator.
+    NodeT *IDom = getIDom(BB);
+
+    assert(IDom || this->DomTreeNodes[nullptr]);
+    DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom);
+
+    // Add a new tree node for this NodeT, and link it as a child of
+    // IDomNode
+    return (this->DomTreeNodes[BB] = IDomNode->addChild(
+                llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
+  }
+
+  NodeT *getIDom(NodeT *BB) const { return IDoms.lookup(BB); }
+
+  void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
+
+public:
   /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
   /// dominator tree in dfs order.
   void updateDFSNumbers() const {
     unsigned DFSNum = 0;
 
     SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
                           typename DomTreeNodeBase<NodeT>::const_iterator>,
                 32> WorkStack;
while (!WorkStack.empty()) {
         Child->DFSNumIn = DFSNum++;
       }
     }
 
     SlowQueries = 0;
     DFSInfoValid = true;
   }
 
-  DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
-    if (DomTreeNodeBase<NodeT> *Node = getNode(BB))
-      return Node;
-
-    // Haven't calculated this node yet?  Get or calculate the node for the
-    // immediate dominator.
-    NodeT *IDom = getIDom(BB);
-
-    assert(IDom || this->DomTreeNodes[nullptr]);
-    DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom);
-
-    // Add a new tree node for this NodeT, and link it as a child of
-    // IDomNode
-    return (this->DomTreeNodes[BB] = IDomNode->addChild(
-                llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
-  }
-
-  NodeT *getIDom(NodeT *BB) const { return IDoms.lookup(BB); }
-
-  void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
-
-public:
   /// recalculate - compute a dominator tree for the given function
   template <class FT> void recalculate(FT &F) {
     typedef GraphTraits<FT *> TraitsTy;
     reset();
     this->Vertex.push_back(nullptr);
 
     if (!this->IsPostDominators) {
       // Initialize root