From de0e42d3c07466677dab4b3bbc379302e383083b Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Wed, 8 Aug 2007 06:24:20 +0000
Subject: [PATCH] Speed up updateDFSNumbers with two observations: 1. domtree
 is a tree, not a graph.  There is no need to avoid revisiting nodes with a
 set. 2. the worklist can contain the child iterator pointers so we don't get
 N^2 rescanning of children.

This speeds up updateDFSNumbers significantly, making it basically free.  On the testcase in PR1432,
this speeds up loopsimplify by another 3x, dropping it from the 12th most expensive pass to the to
the 30th. :)  It used to be #1.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40923 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/VMCore/Dominators.cpp | 39 +++++++++++++++++----------------------
 1 file changed, 17 insertions(+), 22 deletions(-)

diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index 3dc87965873..d08048cc3b8 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -386,38 +386,33 @@ void DominatorTree::calculate(Function &F) {
 void DominatorTreeBase::updateDFSNumbers() {
   unsigned DFSNum = 0;
 
-  SmallVector<DomTreeNode *, 32> WorkStack;
-  SmallPtrSet<DomTreeNode *, 32> Visited;
-
+  SmallVector<std::pair<DomTreeNode*, DomTreeNode::iterator>, 32> WorkStack;
+  
   for (unsigned i = 0, e = Roots.size(); i != e; ++i) {
     DomTreeNode *ThisRoot = getNode(Roots[i]);
-    WorkStack.push_back(ThisRoot);
-    Visited.insert(ThisRoot);
+    WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin()));
     ThisRoot->DFSNumIn = DFSNum++;
     
     while (!WorkStack.empty()) {
-      DomTreeNode *Node = WorkStack.back();
-      
-      bool MustVisitAChild = false;
-      for (DomTreeNode::iterator DI = Node->begin(), E = Node->end();
-           DI != E; ++DI) {
-        DomTreeNode *Child = *DI;
-        if (!Visited.insert(Child))
-          continue;
-        
-        MustVisitAChild = true;
-        Child->DFSNumIn = DFSNum++;
-        WorkStack.push_back(Child);
-        break;
-      }
-      
-      if (!MustVisitAChild) {
-        // If we reach here means all children are visited
+      DomTreeNode *Node = WorkStack.back().first;
+      DomTreeNode::iterator ChildIt = WorkStack.back().second;
+
+      // If we visited all of the children of this node, "recurse" back up the
+      // stack setting the DFOutNum.
+      if (ChildIt == Node->end()) {
         Node->DFSNumOut = DFSNum++;
         WorkStack.pop_back();
+      } else {
+        // Otherwise, recursively visit this child.
+        DomTreeNode *Child = *ChildIt;
+        ++WorkStack.back().second;
+        
+        WorkStack.push_back(std::make_pair(Child, Child->begin()));
+        Child->DFSNumIn = DFSNum++;
       }
     }
   }
+  
   SlowQueries = 0;
   DFSInfoValid = true;
 }
-- 
2.34.1