X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FDominators.cpp;h=c55f0e4a5141f4246ef217dcb663e568e0e74156;hb=287d11191f8470add8deaad90e2c40a953a4c4f5;hp=cd0825c128ab41789d26b5089f385236eb960adf;hpb=80b7f8ceb4ea78276f69fe2ae6dfb172f4895165;p=oota-llvm.git

diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index cd0825c128a..c55f0e4a514 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -12,7 +12,6 @@
 #include "llvm/Assembly/Writer.h"
 #include "Support/DepthFirstIterator.h"
 #include "Support/SetOperations.h"
-using std::set;
 
 //===----------------------------------------------------------------------===//
 //  DominatorSet Implementation
@@ -22,7 +21,7 @@ static RegisterAnalysis<DominatorSet>
 A("domset", "Dominator Set Construction", true);
 
 // dominates - Return true if A dominates B.  This performs the special checks
-// neccesary if A and B are in the same basic block.
+// necessary if A and B are in the same basic block.
 //
 bool DominatorSetBase::dominates(Instruction *A, Instruction *B) const {
   BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
@@ -49,23 +48,30 @@ void DominatorSet::calculateDominatorsFromBlock(BasicBlock *RootBB) {
       BasicBlock *BB = *It;
       pred_iterator PI = pred_begin(BB), PEnd = pred_end(BB);
       if (PI != PEnd) {                // Is there SOME predecessor?
-	// Loop until we get to a predecessor that has had it's dom set filled
+	// Loop until we get to a predecessor that has had its dom set filled
 	// in at least once.  We are guaranteed to have this because we are
-	// traversing the graph in DFO and have handled start nodes specially.
+	// traversing the graph in DFO and have handled start nodes specially,
+	// except when there are unreachable blocks.
 	//
-	while (Doms[*PI].empty()) ++PI;
-	WorkingSet = Doms[*PI];
-
-	for (++PI; PI != PEnd; ++PI) { // Intersect all of the predecessor sets
-	  DomSetType &PredSet = Doms[*PI];
-	  if (PredSet.size())
-	    set_intersect(WorkingSet, PredSet);
-	}
+	while (PI != PEnd && Doms[*PI].empty()) ++PI;
+        if (PI != PEnd) {     // Not unreachable code case?
+          WorkingSet = Doms[*PI];
+
+          // Intersect all of the predecessor sets
+          for (++PI; PI != PEnd; ++PI) {
+            DomSetType &PredSet = Doms[*PI];
+            if (PredSet.size())
+              set_intersect(WorkingSet, PredSet);
+          }
+        }
+      } else {
+        assert(BB == Root && "We got into unreachable code somehow!");
       }
 	
       WorkingSet.insert(BB);           // A block always dominates itself
       DomSetType &BBSet = Doms[BB];
       if (BBSet != WorkingSet) {
+        //assert(WorkingSet.size() > BBSet.size() && "Must only grow sets!");
 	BBSet.swap(WorkingSet);        // Constant time operation!
 	Changed = true;                // The sets changed.
       }
@@ -80,31 +86,31 @@ void DominatorSet::calculateDominatorsFromBlock(BasicBlock *RootBB) {
 // specified function.
 //
 bool DominatorSet::runOnFunction(Function &F) {
-  Doms.clear();   // Reset from the last time we were run...
   Root = &F.getEntryNode();
   assert(pred_begin(Root) == pred_end(Root) &&
 	 "Root node has predecessors in function!");
+  recalculate();
+  return false;
+}
+
+void DominatorSet::recalculate() {
+  Doms.clear();   // Reset from the last time we were run...
 
   // Calculate dominator sets for the reachable basic blocks...
   calculateDominatorsFromBlock(Root);
 
-  // Every basic block in the function should at least dominate themselves, and
-  // thus every basic block should have an entry in Doms.  The one case where we
-  // miss this is when a basic block is unreachable.  To get these we now do an
-  // extra pass over the function, calculating dominator information for
-  // unreachable blocks.
-  //
-  for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
-    if (Doms[I].empty()) {
-      calculateDominatorsFromBlock(I);
-    }
 
-  return false;
+  // Loop through the function, ensuring that every basic block has at least an
+  // empty set of nodes.  This is important for the case when there is
+  // unreachable blocks.
+  Function *F = Root->getParent();
+  for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) Doms[I];
 }
 
 
-static std::ostream &operator<<(std::ostream &o, const set<BasicBlock*> &BBs) {
-  for (set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
+static std::ostream &operator<<(std::ostream &o,
+                                const std::set<BasicBlock*> &BBs) {
+  for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
        I != E; ++I) {
     o << "  ";
     WriteAsOperand(o, *I, false);
@@ -114,10 +120,12 @@ static std::ostream &operator<<(std::ostream &o, const set<BasicBlock*> &BBs) {
 }
 
 void DominatorSetBase::print(std::ostream &o) const {
-  for (const_iterator I = begin(), E = end(); I != E; ++I)
+  for (const_iterator I = begin(), E = end(); I != E; ++I) {
     o << "=============================--------------------------------\n"
-      << "\nDominator Set For Basic Block\n" << I->first
-      << "-------------------------------\n" << I->second << "\n";
+      << "\nDominator Set For Basic Block: ";
+    WriteAsOperand(o, I->first, false);
+    o  << "\n-------------------------------\n" << I->second << "\n";
+  }
 }
 
 //===----------------------------------------------------------------------===//
@@ -164,10 +172,14 @@ void ImmediateDominatorsBase::calcIDoms(const DominatorSetBase &DS) {
 }
 
 void ImmediateDominatorsBase::print(std::ostream &o) const {
-  for (const_iterator I = begin(), E = end(); I != E; ++I)
+  for (const_iterator I = begin(), E = end(); I != E; ++I) {
     o << "=============================--------------------------------\n"
-      << "\nImmediate Dominator For Basic Block\n" << *I->first
-      << "is: \n" << *I->second << "\n";
+      << "\nImmediate Dominator For Basic Block:";
+    WriteAsOperand(o, I->first, false);
+    o << " is:";
+    WriteAsOperand(o, I->second, false);
+    o << "\n";
+  }
 }
 
 
@@ -186,6 +198,23 @@ void DominatorTreeBase::reset() {
   Nodes.clear();
 }
 
+void DominatorTreeBase::Node2::setIDom(Node2 *NewIDom) {
+  assert(IDom && "No immediate dominator?");
+  if (IDom != NewIDom) {
+    std::vector<Node*>::iterator I =
+      std::find(IDom->Children.begin(), IDom->Children.end(), this);
+    assert(I != IDom->Children.end() &&
+           "Not in immediate dominator children set!");
+    // I am no longer your child...
+    IDom->Children.erase(I);
+
+    // Switch to new dominator
+    IDom = NewIDom;
+    IDom->Children.push_back(this);
+  }
+}
+
+
 
 void DominatorTree::calculate(const DominatorSet &DS) {
   Nodes[Root] = new Node(Root, 0);   // Add a node for the root...