Update PassManagerImpl_New::analysisCurrentlyAvailable to check all

[oota-llvm.git] / lib / VMCore / Dominators.cpp

diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index fd193b8d7aa402b39dced6aa7212a4f00c01a8ed..c3e0099ee02ca28429616a78c3eedfac9748fdef 100644 (file)
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -809,6 +809,53 @@ ETNode *ETNode::NCA(ETNode *other) {
     return occmin->OccFor;
 }
 
+void ETNode::assignDFSNumber(int num) {
+  std::vector<ETNode *>  workStack;
+  std::set<ETNode *> visitedNodes;
+  
+  workStack.push_back(this);
+  visitedNodes.insert(this);
+  this->DFSNumIn = num++;
+
+  while (!workStack.empty()) {
+    ETNode  *Node = workStack.back();
+    
+    // If this is leaf node then set DFSNumOut and pop the stack
+    if (!Node->Son) {
+      Node->DFSNumOut = num++;
+      workStack.pop_back();
+      continue;
+    }
+    
+    ETNode *son = Node->Son;
+    
+    // Visit Node->Son first
+    if (visitedNodes.count(son) == 0) {
+      son->DFSNumIn = num++;
+      workStack.push_back(son);
+      visitedNodes.insert(son);
+      continue;
+    }
+    
+    bool visitChild = false;
+    // Visit remaining children
+    for (ETNode *s = son->Right;  s != son && !visitChild; s = s->Right) {
+      if (visitedNodes.count(s) == 0) {
+        visitChild = true;
+        s->DFSNumIn = num++;
+        workStack.push_back(s);
+        visitedNodes.insert(s);
+      }
+    }
+    
+    if (!visitChild) {
+      // If we reach here means all children are visited
+      Node->DFSNumOut = num++;
+      workStack.pop_back();
+    }
+  }
+}
+
 //===----------------------------------------------------------------------===//
 // ETForest implementation
 //===----------------------------------------------------------------------===//
@@ -890,39 +937,6 @@ void ETForest::calculate(const ImmediateDominators &ID) {
   updateDFSNumbers ();
 }
 
-// Walk ETNode and its children using DFS algorithm and assign
-// DFSNumIn and DFSNumOut numbers for each node. 
-void ETNode::assignDFSNumber(int &num) {
-
-    std::vector<ETNode *> DFSInStack;
-    std::set<ETNode *> visited;
-
-    DFSInStack.push_back(this);
-
-    visited.insert(this);
-
-    while(!DFSInStack.empty()) {
-      ETNode *Parent = DFSInStack.back();
-      DFSInStack.pop_back();
-      Parent->DFSNumIn = num++;
-      Parent->DFSNumOut = Parent->DFSNumIn + 1;
-
-      ETNode *son = Parent->Son;
-      if (son && visited.count(son) == 0) {
-
-        DFSInStack.push_back(son);
-        son->DFSNumIn = Parent->DFSNumIn + 1;
-        visited.insert(son);
-        
-        for (ETNode *s = son->Right; s != son; s = s->Right) {
-          DFSInStack.push_back(s);
-          s->DFSNumIn = Parent->DFSNumIn + 1;
-          visited.insert(s);
-        }
-      }
-    }
-}
-
 //===----------------------------------------------------------------------===//
 // ETForestBase Implementation
 //===----------------------------------------------------------------------===//