1 files changed, 81 insertions, 66 deletions
diff --git a/contrib/llvm/lib/VMCore/Dominators.cpp b/contrib/llvm/lib/VMCore/Dominators.cpp
index 10a866f..f3dad82 100644
--- a/contrib/llvm/lib/VMCore/Dominators.cpp
+++ b/contrib/llvm/lib/VMCore/Dominators.cpp
@@ -17,6 +17,7 @@
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Support/CFG.h"
 #include "llvm/Support/Compiler.h"
+#include "llvm/Support/Debug.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/SmallPtrSet.h"
@@ -51,8 +52,8 @@ TEMPLATE_INSTANTIATION(class llvm::DomTreeNodeBase<BasicBlock>);
 TEMPLATE_INSTANTIATION(class llvm::DominatorTreeBase<BasicBlock>);
 
 char DominatorTree::ID = 0;
-static RegisterPass<DominatorTree>
-E("domtree", "Dominator Tree Construction", true, true);
+INITIALIZE_PASS(DominatorTree, "domtree",
+                "Dominator Tree Construction", true, true);
 
 bool DominatorTree::runOnFunction(Function &F) {
   DT->recalculate(F);
@@ -105,8 +106,8 @@ bool DominatorTree::dominates(const Instruction *A, const Instruction *B) const{
 //===----------------------------------------------------------------------===//
 
 char DominanceFrontier::ID = 0;
-static RegisterPass<DominanceFrontier>
-G("domfrontier", "Dominance Frontier Construction", true, true);
+INITIALIZE_PASS(DominanceFrontier, "domfrontier",
+                "Dominance Frontier Construction", true, true);
 
 void DominanceFrontier::verifyAnalysis() const {
   if (!VerifyDomInfo) return;
@@ -122,36 +123,23 @@ void DominanceFrontier::verifyAnalysis() const {
 // NewBB is split and now it has one successor. Update dominance frontier to
 // reflect this change.
 void DominanceFrontier::splitBlock(BasicBlock *NewBB) {
-  assert(NewBB->getTerminator()->getNumSuccessors() == 1
-         && "NewBB should have a single successor!");
+  assert(NewBB->getTerminator()->getNumSuccessors() == 1 &&
+         "NewBB should have a single successor!");
   BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0);
 
-  SmallVector<BasicBlock*, 8> PredBlocks;
-  for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB);
-       PI != PE; ++PI)
-    PredBlocks.push_back(*PI);  
-
-  if (PredBlocks.empty())
-    // If NewBB does not have any predecessors then it is a entry block.
-    // In this case, NewBB and its successor NewBBSucc dominates all
-    // other blocks.
-    return;
-
   // NewBBSucc inherits original NewBB frontier.
   DominanceFrontier::iterator NewBBI = find(NewBB);
-  if (NewBBI != end()) {
-    DominanceFrontier::DomSetType NewBBSet = NewBBI->second;
-    DominanceFrontier::DomSetType NewBBSuccSet;
-    NewBBSuccSet.insert(NewBBSet.begin(), NewBBSet.end());
-    addBasicBlock(NewBBSucc, NewBBSuccSet);
-  }
+  if (NewBBI != end())
+    addBasicBlock(NewBBSucc, NewBBI->second);
 
   // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the
-  // DF(PredBlocks[0]) without the stuff that the new block does not dominate
+  // DF(NewBBSucc) without the stuff that the new block does not dominate
   // a predecessor of.
   DominatorTree &DT = getAnalysis<DominatorTree>();
-  if (DT.dominates(NewBB, NewBBSucc)) {
-    DominanceFrontier::iterator DFI = find(PredBlocks[0]);
+  DomTreeNode *NewBBNode = DT.getNode(NewBB);
+  DomTreeNode *NewBBSuccNode = DT.getNode(NewBBSucc);
+  if (DT.dominates(NewBBNode, NewBBSuccNode)) {
+    DominanceFrontier::iterator DFI = find(NewBBSucc);
     if (DFI != end()) {
       DominanceFrontier::DomSetType Set = DFI->second;
       // Filter out stuff in Set that we do not dominate a predecessor of.
@@ -160,8 +148,10 @@ void DominanceFrontier::splitBlock(BasicBlock *NewBB) {
         bool DominatesPred = false;
         for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI);
              PI != E; ++PI)
-          if (DT.dominates(NewBB, *PI))
+          if (DT.dominates(NewBBNode, DT.getNode(*PI))) {
             DominatesPred = true;
+            break;
+          }
         if (!DominatesPred)
           Set.erase(SetI++);
         else
@@ -186,50 +176,71 @@ void DominanceFrontier::splitBlock(BasicBlock *NewBB) {
     NewDFSet.insert(NewBBSucc);
     addBasicBlock(NewBB, NewDFSet);
   }
-  
-  // Now we must loop over all of the dominance frontiers in the function,
-  // replacing occurrences of NewBBSucc with NewBB in some cases.  All
-  // blocks that dominate a block in PredBlocks and contained NewBBSucc in
-  // their dominance frontier must be updated to contain NewBB instead.
-  //
-  for (Function::iterator FI = NewBB->getParent()->begin(),
-         FE = NewBB->getParent()->end(); FI != FE; ++FI) {
-    DominanceFrontier::iterator DFI = find(FI);
-    if (DFI == end()) continue;  // unreachable block.
-    
-    // Only consider nodes that have NewBBSucc in their dominator frontier.
-    if (!DFI->second.count(NewBBSucc)) continue;
-
-    // Verify whether this block dominates a block in predblocks.  If not, do
-    // not update it.
-    bool BlockDominatesAny = false;
-    for (SmallVectorImpl<BasicBlock*>::const_iterator BI = PredBlocks.begin(), 
-           BE = PredBlocks.end(); BI != BE; ++BI) {
-      if (DT.dominates(FI, *BI)) {
-        BlockDominatesAny = true;
+
+  // Now update dominance frontiers which either used to contain NewBBSucc
+  // or which now need to include NewBB.
+
+  // Collect the set of blocks which dominate a predecessor of NewBB or
+  // NewSuccBB and which don't dominate both. This is an initial
+  // approximation of the blocks whose dominance frontiers will need updates.
+  SmallVector<DomTreeNode *, 16> AllPredDoms;
+
+  // Compute the block which dominates both NewBBSucc and NewBB. This is
+  // the immediate dominator of NewBBSucc unless NewBB dominates NewBBSucc.
+  // The code below which climbs dominator trees will stop at this point,
+  // because from this point up, dominance frontiers are unaffected.
+  DomTreeNode *DominatesBoth = 0;
+  if (NewBBSuccNode) {
+    DominatesBoth = NewBBSuccNode->getIDom();
+    if (DominatesBoth == NewBBNode)
+      DominatesBoth = NewBBNode->getIDom();
+  }
+
+  // Collect the set of all blocks which dominate a predecessor of NewBB.
+  SmallPtrSet<DomTreeNode *, 8> NewBBPredDoms;
+  for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB); PI != E; ++PI)
+    for (DomTreeNode *DTN = DT.getNode(*PI); DTN; DTN = DTN->getIDom()) {
+      if (DTN == DominatesBoth)
         break;
-      }
+      if (!NewBBPredDoms.insert(DTN))
+        break;
+      AllPredDoms.push_back(DTN);
     }
 
-    // If NewBBSucc should not stay in our dominator frontier, remove it.
-    // We remove it unless there is a predecessor of NewBBSucc that we
-    // dominate, but we don't strictly dominate NewBBSucc.
-    bool ShouldRemove = true;
-    if ((BasicBlock*)FI == NewBBSucc || !DT.dominates(FI, NewBBSucc)) {
-      // Okay, we know that PredDom does not strictly dominate NewBBSucc.
-      // Check to see if it dominates any predecessors of NewBBSucc.
-      for (pred_iterator PI = pred_begin(NewBBSucc),
-           E = pred_end(NewBBSucc); PI != E; ++PI)
-        if (DT.dominates(FI, *PI)) {
-          ShouldRemove = false;
-          break;
-        }
+  // Collect the set of all blocks which dominate a predecessor of NewSuccBB.
+  SmallPtrSet<DomTreeNode *, 8> NewBBSuccPredDoms;
+  for (pred_iterator PI = pred_begin(NewBBSucc),
+       E = pred_end(NewBBSucc); PI != E; ++PI)
+    for (DomTreeNode *DTN = DT.getNode(*PI); DTN; DTN = DTN->getIDom()) {
+      if (DTN == DominatesBoth)
+        break;
+      if (!NewBBSuccPredDoms.insert(DTN))
+        break;
+      if (!NewBBPredDoms.count(DTN))
+        AllPredDoms.push_back(DTN);
     }
-    
-    if (ShouldRemove)
-      removeFromFrontier(DFI, NewBBSucc);
-    if (BlockDominatesAny && (&*FI == NewBB || !DT.dominates(FI, NewBB)))
+
+  // Visit all relevant dominance frontiers and make any needed updates.
+  for (SmallVectorImpl<DomTreeNode *>::const_iterator I = AllPredDoms.begin(),
+       E = AllPredDoms.end(); I != E; ++I) {
+    DomTreeNode *DTN = *I;
+    iterator DFI = find((*I)->getBlock());
+
+    // Only consider nodes that have NewBBSucc in their dominator frontier.
+    if (DFI == end() || !DFI->second.count(NewBBSucc)) continue;
+
+    // If the block dominates a predecessor of NewBB but does not properly
+    // dominate NewBB itself, add NewBB to its dominance frontier.
+    if (NewBBPredDoms.count(DTN) &&
+        !DT.properlyDominates(DTN, NewBBNode))
       addToFrontier(DFI, NewBB);
+
+    // If the block does not dominate a predecessor of NewBBSucc or
+    // properly dominates NewBBSucc itself, remove NewBBSucc from its
+    // dominance frontier.
+    if (!NewBBSuccPredDoms.count(DTN) ||
+        DT.properlyDominates(DTN, NewBBSuccNode))
+      removeFromFrontier(DFI, NewBBSucc);
   }
 }
 
@@ -343,3 +354,7 @@ void DominanceFrontierBase::print(raw_ostream &OS, const Module* ) const {
   }
 }
 
+void DominanceFrontierBase::dump() const {
+  print(dbgs());
+}
+