[Dominators] Don't compute DFS InOut numbers eagerly.

[kuhar]

Summary

DFS InOut numbers currently get eagerly computer upon DomTree construction. They are only needed to answer dome dominance queries and they get invalidated by updates and recalculations. Because of that, it is faster in practice to compute them lazily when they are actually needed.

Clang built without this patch takes 6m 45s to boostrap on my machine, and with the patch applied 6m 38s.

[kuhar]

Update tests.

[kuhar]

Update the diff to apply cleanly.

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

for (unsigned i = 2; i <= N; ++i) {
       // 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));
     }
-
-    DT.updateDFSNumbers();
   }
 
   void doFullDFSWalk(const DomTreeT &DT) {
     unsigned Num = 0;
     for (auto *Root : DT.Roots)
       if (!DT.isPostDominator())
         Num = runForwardDFS(Root, Num);
       else

llvm/trunk/test/Analysis/Dominators/2006-10-02-BreakCritEdges.ll

 ; RUN: opt < %s -domtree -break-crit-edges -analyze -domtree | FileCheck %s
 ; RUN: opt < %s -passes='require<domtree>,break-crit-edges,print<domtree>' -disable-output 2>&1| FileCheck %s
 ; PR932
 
-; CHECK: [3] %brtrue {1,2}
+; CHECK: [3] %brtrue {{{[0-9]+}},{{[0-9]+}}}
 
 declare void @use1(i32)
 
 define void @f(i32 %i, i1 %c) {
 entry:
   %A = icmp eq i32 %i, 0    ; <i1> [#uses=1]
   br i1 %A, label %brtrue, label %brfalse
 

llvm/trunk/unittests/IR/DominatorTreeTest.cpp

runWithDomTree(
         DominatedBBs.clear();
         PostDominatedBBs.clear();
         DT->getDescendants(BB3, DominatedBBs);
         DT->getDescendants(BB3, PostDominatedBBs);
         EXPECT_EQ(DominatedBBs.size(), 0UL);
         EXPECT_EQ(PostDominatedBBs.size(), 0UL);
 
         // Check DFS Numbers before
+        DT->updateDFSNumbers();
         EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL);
         EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 7UL);
         EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL);
         EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 2UL);
         EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 5UL);
         EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 6UL);
         EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 3UL);
         EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 4UL);
 
         // Reattach block 3 to block 1 and recalculate
         BB1->getTerminator()->eraseFromParent();
         BranchInst::Create(BB4, BB3, ConstantInt::getTrue(F.getContext()), BB1);
         DT->recalculate(F);
 
         // Check DFS Numbers after
+        DT->updateDFSNumbers();
         EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL);
         EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 9UL);
         EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL);
         EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 4UL);
         EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 7UL);
         EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 8UL);
         EXPECT_EQ(DT->getNode(BB3)->getDFSNumIn(), 2UL);
         EXPECT_EQ(DT->getNode(BB3)->getDFSNumOut(), 3UL);