more updates and random notes, including changes up through Week-of-Mon-20080324.

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

diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index a9900fe1a73d7023b29f302a9cdc3b2b2f83b66d..e9eca4eee4a212fea914099840399273590414ad 100644 (file)
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -2,8 +2,8 @@
 //
 //                     The LLVM Compiler Infrastructure
 //
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
@@ -54,103 +54,10 @@ TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
 
 char DominatorTree::ID = 0;
 static RegisterPass<DominatorTree>
-E("domtree", "Dominator Tree Construction", true);
-
-// NewBB is split and now it has one successor. Update dominator tree to
-// reflect this change.
-void DominatorTree::splitBlock(BasicBlock *NewBB) {
-  assert(NewBB->getTerminator()->getNumSuccessors() == 1
-         && "NewBB should have a single successor!");
-  BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0);
-
-  std::vector<BasicBlock*> PredBlocks;
-  for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB);
-       PI != PE; ++PI)
-      PredBlocks.push_back(*PI);  
-
-  assert(!PredBlocks.empty() && "No predblocks??");
-
-  // The newly inserted basic block will dominate existing basic blocks iff the
-  // PredBlocks dominate all of the non-pred blocks.  If all predblocks dominate
-  // the non-pred blocks, then they all must be the same block!
-  //
-  bool NewBBDominatesNewBBSucc = true;
-  {
-    BasicBlock *OnePred = PredBlocks[0];
-    unsigned i = 1, e = PredBlocks.size();
-    for (i = 1; !isReachableFromEntry(OnePred); ++i) {
-      assert(i != e && "Didn't find reachable pred?");
-      OnePred = PredBlocks[i];
-    }
-    
-    for (; i != e; ++i)
-      if (PredBlocks[i] != OnePred && isReachableFromEntry(OnePred)) {
-        NewBBDominatesNewBBSucc = false;
-        break;
-      }
-
-    if (NewBBDominatesNewBBSucc)
-      for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc);
-           PI != E; ++PI)
-        if (*PI != NewBB && !dominates(NewBBSucc, *PI)) {
-          NewBBDominatesNewBBSucc = false;
-          break;
-        }
-  }
-
-  // The other scenario where the new block can dominate its successors are when
-  // all predecessors of NewBBSucc that are not NewBB are dominated by NewBBSucc
-  // already.
-  if (!NewBBDominatesNewBBSucc) {
-    NewBBDominatesNewBBSucc = true;
-    for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc);
-         PI != E; ++PI)
-      if (*PI != NewBB && !dominates(NewBBSucc, *PI)) {
-        NewBBDominatesNewBBSucc = false;
-        break;
-      }
-  }
-
-  // Find NewBB's immediate dominator and create new dominator tree node for
-  // NewBB.
-  BasicBlock *NewBBIDom = 0;
-  unsigned i = 0;
-  for (i = 0; i < PredBlocks.size(); ++i)
-    if (isReachableFromEntry(PredBlocks[i])) {
-      NewBBIDom = PredBlocks[i];
-      break;
-    }
-  assert(i != PredBlocks.size() && "No reachable preds?");
-  for (i = i + 1; i < PredBlocks.size(); ++i) {
-    if (isReachableFromEntry(PredBlocks[i]))
-      NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
-  }
-  assert(NewBBIDom && "No immediate dominator found??");
-  
-  // Create the new dominator tree node... and set the idom of NewBB.
-  DomTreeNode *NewBBNode = addNewBlock(NewBB, NewBBIDom);
-  
-  // If NewBB strictly dominates other blocks, then it is now the immediate
-  // dominator of NewBBSucc.  Update the dominator tree as appropriate.
-  if (NewBBDominatesNewBBSucc) {
-    DomTreeNode *NewBBSuccNode = getNode(NewBBSucc);
-    changeImmediateDominator(NewBBSuccNode, NewBBNode);
-  }
-}
+E("domtree", "Dominator Tree Construction", true, true);
 
 bool DominatorTree::runOnFunction(Function &F) {
-  reset();     // Reset from the last time we were run...
-  
-  // Initialize roots
-  Roots.push_back(&F.getEntryBlock());
-  IDoms[&F.getEntryBlock()] = 0;
-  DomTreeNodes[&F.getEntryBlock()] = 0;
-  Vertex.push_back(0);
-  
-  Calculate<BasicBlock*, GraphTraits<BasicBlock*> >(*this, F);
-  
-  updateDFSNumbers();
-  
+  DT->recalculate(F);
   return false;
 }
 
@@ -160,7 +67,7 @@ bool DominatorTree::runOnFunction(Function &F) {
 
 char DominanceFrontier::ID = 0;
 static RegisterPass<DominanceFrontier>
-G("domfrontier", "Dominance Frontier Construction", true);
+G("domfrontier", "Dominance Frontier Construction", true, true);
 
 // NewBB is split and now it has one successor. Update dominace frontier to
 // reflect this change.