For PR1205:

[oota-llvm.git] / lib / Analysis / PostDominators.cpp

diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
index e195d7a4c77addd41b32ccfc20830332652c34af..d1fe9dd7f6614ef8e8e4be6eca4db92437922d73 100644 (file)
--- a/lib/Analysis/PostDominators.cpp
+++ b/lib/Analysis/PostDominators.cpp
@@ -16,35 +16,60 @@
 #include "llvm/Support/CFG.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SetOperations.h"
-#include <iostream>
 using namespace llvm;
 
 //===----------------------------------------------------------------------===//
 //  ImmediatePostDominators Implementation
 //===----------------------------------------------------------------------===//
 
-static RegisterAnalysis<ImmediatePostDominators>
+static RegisterPass<ImmediatePostDominators>
 D("postidom", "Immediate Post-Dominators Construction", true);
 
 unsigned ImmediatePostDominators::DFSPass(BasicBlock *V, InfoRec &VInfo,
                                           unsigned N) {
-  VInfo.Semi = ++N;
-  VInfo.Label = V;
-  
-  Vertex.push_back(V);        // Vertex[n] = V;
-                              //Info[V].Ancestor = 0;     // Ancestor[n] = 0
-                              //Child[V] = 0;             // Child[v] = 0
-  VInfo.Size = 1;             // Size[v] = 1
-  
-  // For PostDominators, we want to walk predecessors rather than successors
-  // as we do in forward Dominators.
-  for (pred_iterator PI = pred_begin(V), PE = pred_end(V); PI != PE; ++PI) {
-    InfoRec &SuccVInfo = Info[*PI];
-    if (SuccVInfo.Semi == 0) {
-      SuccVInfo.Parent = V;
-      N = DFSPass(*PI, SuccVInfo, N);
+  std::vector<std::pair<BasicBlock *, InfoRec *> > workStack;
+  std::set<BasicBlock *> visited;
+  workStack.push_back(std::make_pair(V, &VInfo));
+
+  do {
+    BasicBlock *currentBB = workStack.back().first; 
+    InfoRec *currentVInfo = workStack.back().second;
+
+    // Visit each block only once.
+    if (visited.count(currentBB) == 0) {
+
+      visited.insert(currentBB);
+      currentVInfo->Semi = ++N;
+      currentVInfo->Label = currentBB;
+      
+      Vertex.push_back(currentBB);  // Vertex[n] = current;
+      // Info[currentBB].Ancestor = 0;     
+      // Ancestor[n] = 0
+      // Child[currentBB] = 0;
+      currentVInfo->Size = 1;       // Size[currentBB] = 1
     }
-  }
+
+    // Visit children
+    bool visitChild = false;
+    for (pred_iterator PI = pred_begin(currentBB), PE = pred_end(currentBB); 
+         PI != PE && !visitChild; ++PI) {
+      InfoRec &SuccVInfo = Info[*PI];
+      if (SuccVInfo.Semi == 0) {
+        SuccVInfo.Parent = currentBB;
+        if (visited.count (*PI) == 0) {
+          workStack.push_back(std::make_pair(*PI, &SuccVInfo));   
+          visitChild = true;
+        }
+      }
+    }
+
+    // If all children are visited or if this block has no child then pop this
+    // block out of workStack.
+    if (!visitChild)
+      workStack.pop_back();
+
+  } while (!workStack.empty());
+
   return N;
 }
 
@@ -145,7 +170,7 @@ bool ImmediatePostDominators::runOnFunction(Function &F) {
 //  PostDominatorSet Implementation
 //===----------------------------------------------------------------------===//
 
-static RegisterAnalysis<PostDominatorSet>
+static RegisterPass<PostDominatorSet>
 B("postdomset", "Post-Dominator Set Construction", true);
 
 // Postdominator set construction.  This converts the specified function to only
@@ -212,7 +237,7 @@ bool PostDominatorSet::runOnFunction(Function &F) {
 //  PostDominatorTree Implementation
 //===----------------------------------------------------------------------===//
 
-static RegisterAnalysis<PostDominatorTree>
+static RegisterPass<PostDominatorTree>
 F("postdomtree", "Post-Dominator Tree Construction", true);
 
 DominatorTreeBase::Node *PostDominatorTree::getNodeForBlock(BasicBlock *BB) {
@@ -258,7 +283,7 @@ void PostDominatorTree::calculate(const ImmediatePostDominators &IPD) {
 // PostETForest Implementation
 //===----------------------------------------------------------------------===//
 
-static RegisterAnalysis<PostETForest>
+static RegisterPass<PostETForest>
 G("postetforest", "Post-ET-Forest Construction", true);
 
 ETNode *PostETForest::getNodeForBlock(BasicBlock *BB) {
@@ -322,7 +347,7 @@ void PostETForest::calculate(const ImmediatePostDominators &ID) {
 //  PostDominanceFrontier Implementation
 //===----------------------------------------------------------------------===//
 
-static RegisterAnalysis<PostDominanceFrontier>
+static RegisterPass<PostDominanceFrontier>
 H("postdomfrontier", "Post-Dominance Frontier Construction", true);
 
 const DominanceFrontier::DomSetType &