X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FDominators.h;h=956ed1a36f116202a8434602def65d4a0d8c62cc;hb=af9ac8f8212a062291e218ea0dea90a2e81dcf66;hp=87ea6c1651dc7e8807ae9653095888e8e4de0e7e;hpb=9a51157db555395f7a6ad89faec40b3afa121091;p=oota-llvm.git

diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 87ea6c1651d..956ed1a36f1 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -9,9 +9,7 @@
 //
 // This file defines the following classes:
 //  1. DominatorTree: Represent dominators as an explicit tree structure.
-//  2. ETForest: Efficient data structure for dominance comparisons and 
-//     nearest-common-ancestor queries.
-//  3. DominanceFrontier: Calculate and hold the dominance frontier for a
+//  2. DominanceFrontier: Calculate and hold the dominance frontier for a
 //     function.
 //
 //  These data structures are listed in increasing order of complexity.  It
@@ -23,33 +21,41 @@
 #ifndef LLVM_ANALYSIS_DOMINATORS_H
 #define LLVM_ANALYSIS_DOMINATORS_H
 
-#include "llvm/Analysis/ET-Forest.h"
 #include "llvm/Pass.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/Function.h"
+#include "llvm/Instruction.h"
+#include "llvm/Instructions.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Assembly/Writer.h"
+#include "llvm/Support/CFG.h"
+#include "llvm/Support/Compiler.h"
+#include <algorithm>
 #include <set>
 
 namespace llvm {
 
-class Instruction;
-
-template <typename GraphType> struct GraphTraits;
-
 //===----------------------------------------------------------------------===//
 /// DominatorBase - Base class that other, more interesting dominator analyses
 /// inherit from.
 ///
-class DominatorBase : public FunctionPass {
+template <class NodeT>
+class DominatorBase {
 protected:
-  std::vector<BasicBlock*> Roots;
+  std::vector<NodeT*> Roots;
   const bool IsPostDominators;
-  inline DominatorBase(intptr_t ID, bool isPostDom) : 
-    FunctionPass(ID), Roots(), IsPostDominators(isPostDom) {}
+  inline DominatorBase(bool isPostDom) : 
+    Roots(), IsPostDominators(isPostDom) {}
 public:
 
   /// getRoots -  Return the root blocks of the current CFG.  This may include
   /// multiple blocks if we are computing post dominators.  For forward
   /// dominators, this will always be a single block (the entry node).
   ///
-  inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
+  inline const std::vector<NodeT*> &getRoots() const { return Roots; }
 
   /// isPostDominator - Returns true if analysis based of postdoms
   ///
@@ -59,48 +65,113 @@ public:
 
 //===----------------------------------------------------------------------===//
 // DomTreeNode - Dominator Tree Node
-
-class DomTreeNode {
-  BasicBlock *TheBB;
-  DomTreeNode *IDom;
-  ETNode *ETN;
-  std::vector<DomTreeNode*> Children;
+template<class NodeT> class DominatorTreeBase;
+struct PostDominatorTree;
+class MachineBasicBlock;
+
+template <class NodeT>
+class DomTreeNodeBase {
+  NodeT *TheBB;
+  DomTreeNodeBase<NodeT> *IDom;
+  std::vector<DomTreeNodeBase<NodeT> *> Children;
+  int DFSNumIn, DFSNumOut;
+
+  template<class N> friend class DominatorTreeBase;
+  friend struct PostDominatorTree;
 public:
-  typedef std::vector<DomTreeNode*>::iterator iterator;
-  typedef std::vector<DomTreeNode*>::const_iterator const_iterator;
+  typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator;
+  typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator
+                   const_iterator;
   
   iterator begin()             { return Children.begin(); }
   iterator end()               { return Children.end(); }
   const_iterator begin() const { return Children.begin(); }
   const_iterator end()   const { return Children.end(); }
   
-  inline BasicBlock *getBlock() const { return TheBB; }
-  inline DomTreeNode *getIDom() const { return IDom; }
-  inline ETNode *getETNode() const { return ETN; }
-  inline const std::vector<DomTreeNode*> &getChildren() const { return Children; }
+  NodeT *getBlock() const { return TheBB; }
+  DomTreeNodeBase<NodeT> *getIDom() const { return IDom; }
+  const std::vector<DomTreeNodeBase<NodeT>*> &getChildren() const {
+    return Children;
+  }
   
-  inline DomTreeNode(BasicBlock *BB, DomTreeNode *iDom, ETNode *E) 
-    : TheBB(BB), IDom(iDom), ETN(E) {
-    if (IDom)
-      ETN->setFather(IDom->getETNode());
+  DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom)
+    : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { }
+  
+  DomTreeNodeBase<NodeT> *addChild(DomTreeNodeBase<NodeT> *C) {
+    Children.push_back(C);
+    return C;
+  }
+  
+  void setIDom(DomTreeNodeBase<NodeT> *NewIDom) {
+    assert(IDom && "No immediate dominator?");
+    if (IDom != NewIDom) {
+      typename std::vector<DomTreeNodeBase<NodeT>*>::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);
+    }
+  }
+  
+  /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do
+  /// not call them.
+  unsigned getDFSNumIn() const { return DFSNumIn; }
+  unsigned getDFSNumOut() const { return DFSNumOut; }
+private:
+  // Return true if this node is dominated by other. Use this only if DFS info
+  // is valid.
+  bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const {
+    return this->DFSNumIn >= other->DFSNumIn &&
+      this->DFSNumOut <= other->DFSNumOut;
   }
-  inline DomTreeNode *addChild(DomTreeNode *C) { Children.push_back(C); return C; }
-  void setIDom(DomTreeNode *NewIDom);
 };
 
+EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>);
+EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>);
+
+template<class NodeT>
+static std::ostream &operator<<(std::ostream &o,
+                                const DomTreeNodeBase<NodeT> *Node) {
+  if (Node->getBlock())
+    WriteAsOperand(o, Node->getBlock(), false);
+  else
+    o << " <<exit node>>";
+  
+  o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}";
+  
+  return o << "\n";
+}
+
+template<class NodeT>
+static void PrintDomTree(const DomTreeNodeBase<NodeT> *N, std::ostream &o,
+                         unsigned Lev) {
+  o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N;
+  for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
+       E = N->end(); I != E; ++I)
+    PrintDomTree<NodeT>(*I, o, Lev+1);
+}
+
+typedef DomTreeNodeBase<BasicBlock> DomTreeNode;
+
 //===----------------------------------------------------------------------===//
 /// DominatorTree - Calculate the immediate dominator tree for a function.
 ///
-class DominatorTreeBase : public DominatorBase {
 
+template<class FuncT, class N>
+void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT,
+               FuncT& F);
+
+template<class NodeT>
+class DominatorTreeBase : public DominatorBase<NodeT> {
 protected:
-  void reset();
-  typedef std::map<BasicBlock*, DomTreeNode*> DomTreeNodeMapType;
+  typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> DomTreeNodeMapType;
   DomTreeNodeMapType DomTreeNodes;
-  DomTreeNode *RootNode;
-
-  typedef std::map<BasicBlock*, ETNode*> ETMapType;
-  ETMapType ETNodes;
+  DomTreeNodeBase<NodeT> *RootNode;
 
   bool DFSInfoValid;
   unsigned int SlowQueries;
@@ -108,38 +179,135 @@ protected:
   struct InfoRec {
     unsigned Semi;
     unsigned Size;
-    BasicBlock *Label, *Parent, *Child, *Ancestor;
+    NodeT *Label, *Parent, *Child, *Ancestor;
 
-    std::vector<BasicBlock*> Bucket;
+    std::vector<NodeT*> Bucket;
 
-    InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){}
+    InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0) {}
   };
 
-  std::map<BasicBlock*, BasicBlock*> IDoms;
+  DenseMap<NodeT*, NodeT*> IDoms;
 
   // Vertex - Map the DFS number to the BasicBlock*
-  std::vector<BasicBlock*> Vertex;
+  std::vector<NodeT*> Vertex;
 
   // Info - Collection of information used during the computation of idoms.
-  std::map<BasicBlock*, InfoRec> Info;
+  DenseMap<NodeT*, InfoRec> Info;
+
+  void reset() {
+    for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(), 
+           E = DomTreeNodes.end(); I != E; ++I)
+      delete I->second;
+    DomTreeNodes.clear();
+    IDoms.clear();
+    this->Roots.clear();
+    Vertex.clear();
+    RootNode = 0;
+  }
+  
+  // NewBB is split and now it has one successor. Update dominator tree to
+  // reflect this change.
+  template<class N, class GraphT>
+  void Split(DominatorTreeBase<typename GraphT::NodeType>& DT,
+             typename GraphT::NodeType* NewBB) {
+    assert(std::distance(GraphT::child_begin(NewBB), GraphT::child_end(NewBB)) == 1
+           && "NewBB should have a single successor!");
+    typename GraphT::NodeType* NewBBSucc = *GraphT::child_begin(NewBB);
+
+    std::vector<typename GraphT::NodeType*> PredBlocks;
+    for (typename GraphTraits<Inverse<N> >::ChildIteratorType PI =
+         GraphTraits<Inverse<N> >::child_begin(NewBB),
+         PE = GraphTraits<Inverse<N> >::child_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;
+      {
+        typename GraphT::NodeType* OnePred = PredBlocks[0];
+        unsigned i = 1, e = PredBlocks.size();
+        for (i = 1; !DT.isReachableFromEntry(OnePred); ++i) {
+          assert(i != e && "Didn't find reachable pred?");
+          OnePred = PredBlocks[i];
+        }
+
+        for (; i != e; ++i)
+          if (PredBlocks[i] != OnePred && DT.isReachableFromEntry(OnePred)) {
+            NewBBDominatesNewBBSucc = false;
+            break;
+          }
+
+      if (NewBBDominatesNewBBSucc)
+        for (typename GraphTraits<Inverse<N> >::ChildIteratorType PI =
+             GraphTraits<Inverse<N> >::child_begin(NewBBSucc),
+             E = GraphTraits<Inverse<N> >::child_end(NewBBSucc); PI != E; ++PI)
+          if (*PI != NewBB && !DT.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 (typename GraphTraits<Inverse<N> >::ChildIteratorType PI = 
+           GraphTraits<Inverse<N> >::child_begin(NewBBSucc),
+           E = GraphTraits<Inverse<N> >::child_end(NewBBSucc); PI != E; ++PI)
+         if (*PI != NewBB && !DT.dominates(NewBBSucc, *PI)) {
+          NewBBDominatesNewBBSucc = false;
+          break;
+        }
+    }
 
-  public:
-  DominatorTreeBase(intptr_t ID, bool isPostDom) 
-    : DominatorBase(ID, isPostDom), DFSInfoValid(false), SlowQueries(0) {}
-  ~DominatorTreeBase() { reset(); }
+    // Find NewBB's immediate dominator and create new dominator tree node for
+    // NewBB.
+    NodeT *NewBBIDom = 0;
+    unsigned i = 0;
+    for (i = 0; i < PredBlocks.size(); ++i)
+      if (DT.isReachableFromEntry(PredBlocks[i])) {
+        NewBBIDom = PredBlocks[i];
+        break;
+      }
+    assert(i != PredBlocks.size() && "No reachable preds?");
+    for (i = i + 1; i < PredBlocks.size(); ++i) {
+      if (DT.isReachableFromEntry(PredBlocks[i]))
+        NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
+    }
+    assert(NewBBIDom && "No immediate dominator found??");
+
+    // Create the new dominator tree node... and set the idom of NewBB.
+    DomTreeNodeBase<NodeT> *NewBBNode = DT.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) {
+      DomTreeNodeBase<NodeT> *NewBBSuccNode = DT.getNode(NewBBSucc);
+      DT.changeImmediateDominator(NewBBSuccNode, NewBBNode);
+    }
+  }
+
+public:
+  DominatorTreeBase(bool isPostDom) 
+    : DominatorBase<NodeT>(isPostDom), DFSInfoValid(false), SlowQueries(0) {}
+  virtual ~DominatorTreeBase() { reset(); }
+
+  // FIXME: Should remove this
+  virtual bool runOnFunction(Function &F) { return false; }
 
   virtual void releaseMemory() { reset(); }
 
   /// getNode - return the (Post)DominatorTree node for the specified basic
   /// block.  This is the same as using operator[] on this class.
   ///
-  inline DomTreeNode *getNode(BasicBlock *BB) const {
-    DomTreeNodeMapType::const_iterator i = DomTreeNodes.find(BB);
-    return (i != DomTreeNodes.end()) ? i->second : 0;
-  }
-
-  inline DomTreeNode *operator[](BasicBlock *BB) const {
-    return getNode(BB);
+  inline DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
+    typename DomTreeNodeMapType::const_iterator I = DomTreeNodes.find(BB);
+    return I != DomTreeNodes.end() ? I->second : 0;
   }
 
   /// getRootNode - This returns the entry node for the CFG of the function.  If
@@ -149,50 +317,123 @@ protected:
   /// post-dominance information must be capable of dealing with this
   /// possibility.
   ///
-  DomTreeNode *getRootNode() { return RootNode; }
-  const DomTreeNode *getRootNode() const { return RootNode; }
+  DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
+  const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
 
   /// properlyDominates - Returns true iff this dominates N and this != N.
   /// Note that this is not a constant time operation!
   ///
-  bool properlyDominates(const DomTreeNode *A, DomTreeNode *B) const {
+  bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
+                         DomTreeNodeBase<NodeT> *B) const {
     if (A == 0 || B == 0) return false;
     return dominatedBySlowTreeWalk(A, B);
   }
 
-  bool dominatedBySlowTreeWalk(const DomTreeNode *A, 
-                               const DomTreeNode *B) const {
-    const DomTreeNode *IDom;
+  inline bool properlyDominates(NodeT *A, NodeT *B) {
+    return properlyDominates(getNode(A), getNode(B));
+  }
+
+  bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A, 
+                               const DomTreeNodeBase<NodeT> *B) const {
+    const DomTreeNodeBase<NodeT> *IDom;
     if (A == 0 || B == 0) return false;
-    while ((IDom = B->getIDom()) != 0 && IDom != A)
+    while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B)
       B = IDom;   // Walk up the tree
     return IDom != 0;
   }
 
-  void updateDFSNumbers();  
-  /// dominates - Returns true iff this dominates N.  Note that this is not a
+
+  /// isReachableFromEntry - Return true if A is dominated by the entry
+  /// block of the function containing it.
+  bool isReachableFromEntry(NodeT* A) {
+    assert (!this->isPostDominator() 
+            && "This is not implemented for post dominators");
+    return dominates(&A->getParent()->front(), A);
+  }
+  
+  /// dominates - Returns true iff A dominates B.  Note that this is not a
   /// constant time operation!
   ///
-  inline bool dominates(const DomTreeNode *A, DomTreeNode *B) {
-    if (B == A) return true;  // A node trivially dominates itself.
+  inline bool dominates(const DomTreeNodeBase<NodeT> *A,
+                        DomTreeNodeBase<NodeT> *B) {
+    if (B == A) 
+      return true;  // A node trivially dominates itself.
+
+    if (A == 0 || B == 0)
+      return false;
 
-    ETNode *NodeA = A->getETNode();
-    ETNode *NodeB = B->getETNode();
-    
     if (DFSInfoValid)
-      return NodeB->DominatedBy(NodeA);
+      return B->DominatedBy(A);
 
     // If we end up with too many slow queries, just update the
     // DFS numbers on the theory that we are going to keep querying.
     SlowQueries++;
     if (SlowQueries > 32) {
       updateDFSNumbers();
-      return NodeB->DominatedBy(NodeA);
+      return B->DominatedBy(A);
     }
-    //return NodeB->DominatedBySlow(NodeA);
+
     return dominatedBySlowTreeWalk(A, B);
   }
+
+  inline bool dominates(NodeT *A, NodeT *B) {
+    if (A == B) 
+      return true;
+    
+    return dominates(getNode(A), getNode(B));
+  }
   
+  NodeT *getRoot() const {
+    assert(this->Roots.size() == 1 && "Should always have entry node!");
+    return this->Roots[0];
+  }
+
+  /// findNearestCommonDominator - Find nearest common dominator basic block
+  /// for basic block A and B. If there is no such block then return NULL.
+  NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) {
+
+    assert (!this->isPostDominator() 
+            && "This is not implemented for post dominators");
+    assert (A->getParent() == B->getParent() 
+            && "Two blocks are not in same function");
+
+    // If either A or B is a entry block then it is nearest common dominator.
+    NodeT &Entry  = A->getParent()->front();
+    if (A == &Entry || B == &Entry)
+      return &Entry;
+
+    // If B dominates A then B is nearest common dominator.
+    if (dominates(B, A))
+      return B;
+
+    // If A dominates B then A is nearest common dominator.
+    if (dominates(A, B))
+      return A;
+
+    DomTreeNodeBase<NodeT> *NodeA = getNode(A);
+    DomTreeNodeBase<NodeT> *NodeB = getNode(B);
+
+    // Collect NodeA dominators set.
+    SmallPtrSet<DomTreeNodeBase<NodeT>*, 16> NodeADoms;
+    NodeADoms.insert(NodeA);
+    DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom();
+    while (IDomA) {
+      NodeADoms.insert(IDomA);
+      IDomA = IDomA->getIDom();
+    }
+
+    // Walk NodeB immediate dominators chain and find common dominator node.
+    DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom();
+    while(IDomB) {
+      if (NodeADoms.count(IDomB) != 0)
+        return IDomB->getBlock();
+
+      IDomB = IDomB->getIDom();
+    }
+
+    return NULL;
+  }
+
   //===--------------------------------------------------------------------===//
   // API to update (Post)DominatorTree information based on modifications to
   // the CFG...
@@ -200,59 +441,251 @@ protected:
   /// addNewBlock - Add a new node to the dominator tree information.  This
   /// creates a new node as a child of DomBB dominator node,linking it into 
   /// the children list of the immediate dominator.
-  DomTreeNode *addNewBlock(BasicBlock *BB, BasicBlock *DomBB) {
+  DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
     assert(getNode(BB) == 0 && "Block already in dominator tree!");
-    DomTreeNode *IDomNode = getNode(DomBB);
+    DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
     assert(IDomNode && "Not immediate dominator specified for block!");
     DFSInfoValid = false;
-    ETNode *E = new ETNode(BB);
-    ETNodes[BB] = E;
     return DomTreeNodes[BB] = 
-      IDomNode->addChild(new DomTreeNode(BB, IDomNode, E));
+      IDomNode->addChild(new DomTreeNodeBase<NodeT>(BB, IDomNode));
   }
 
   /// changeImmediateDominator - This method is used to update the dominator
   /// tree information when a node's immediate dominator changes.
   ///
-  void changeImmediateDominator(DomTreeNode *N, DomTreeNode *NewIDom) {
+  void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
+                                DomTreeNodeBase<NodeT> *NewIDom) {
     assert(N && NewIDom && "Cannot change null node pointers!");
     DFSInfoValid = false;
     N->setIDom(NewIDom);
   }
 
-  void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB) {
+  void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
     changeImmediateDominator(getNode(BB), getNode(NewBB));
   }
 
+  /// eraseNode - Removes a node from  the dominator tree. Block must not
+  /// domiante any other blocks. Removes node from its immediate dominator's
+  /// children list. Deletes dominator node associated with basic block BB.
+  void eraseNode(NodeT *BB) {
+    DomTreeNodeBase<NodeT> *Node = getNode(BB);
+    assert (Node && "Removing node that isn't in dominator tree.");
+    assert (Node->getChildren().empty() && "Node is not a leaf node.");
+
+      // Remove node from immediate dominator's children list.
+    DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
+    if (IDom) {
+      typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I =
+        std::find(IDom->Children.begin(), IDom->Children.end(), Node);
+      assert(I != IDom->Children.end() &&
+             "Not in immediate dominator children set!");
+      // I am no longer your child...
+      IDom->Children.erase(I);
+    }
+
+    DomTreeNodes.erase(BB);
+    delete Node;
+  }
+
   /// removeNode - Removes a node from the dominator tree.  Block must not
   /// dominate any other blocks.  Invalidates any node pointing to removed
   /// block.
-  void removeNode(BasicBlock *BB) {
+  void removeNode(NodeT *BB) {
     assert(getNode(BB) && "Removing node that isn't in dominator tree.");
     DomTreeNodes.erase(BB);
   }
+  
+  /// splitBlock - BB is split and now it has one successor. Update dominator
+  /// tree to reflect this change.
+  void splitBlock(NodeT* NewBB) {
+    if (this->IsPostDominators)
+      this->Split<Inverse<NodeT*>, GraphTraits<Inverse<NodeT*> > >(*this, NewBB);
+    else
+      this->Split<NodeT*, GraphTraits<NodeT*> >(*this, NewBB);
+  }
 
   /// print - Convert to human readable form
   ///
-  virtual void print(std::ostream &OS, const Module* = 0) const;
+  virtual void print(std::ostream &o, const Module* ) const {
+    o << "=============================--------------------------------\n";
+    o << "Inorder Dominator Tree: ";
+    if (this->DFSInfoValid)
+      o << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
+    o << "\n";
+
+    PrintDomTree<NodeT>(getRootNode(), o, 1);
+  }
+  
   void print(std::ostream *OS, const Module* M = 0) const {
     if (OS) print(*OS, M);
   }
-  virtual void dump();
+  
+  virtual void dump() {
+    print(llvm::cerr);
+  }
+  
+protected:
+  template<class GraphT>
+  friend void Compress(DominatorTreeBase<typename GraphT::NodeType>& DT,
+                       typename GraphT::NodeType* VIn);
+
+  template<class GraphT>
+  friend typename GraphT::NodeType* Eval(
+                               DominatorTreeBase<typename GraphT::NodeType>& DT,
+                                         typename GraphT::NodeType* V);
+
+  template<class GraphT>
+  friend void Link(DominatorTreeBase<typename GraphT::NodeType>& DT,
+                   typename GraphT::NodeType* V,
+                   typename GraphT::NodeType* W,
+         typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo);
+  
+  template<class GraphT>
+  friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT,
+                          typename GraphT::NodeType* V,
+                          unsigned N);
+  
+  template<class FuncT, class N>
+  friend void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT,
+                        FuncT& F);
+  
+  /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
+  /// dominator tree in dfs order.
+  void updateDFSNumbers() {
+    unsigned DFSNum = 0;
+
+    SmallVector<std::pair<DomTreeNodeBase<NodeT>*,
+                typename DomTreeNodeBase<NodeT>::iterator>, 32> WorkStack;
+
+    for (unsigned i = 0, e = this->Roots.size(); i != e; ++i) {
+      DomTreeNodeBase<NodeT> *ThisRoot = getNode(this->Roots[i]);
+      WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin()));
+      ThisRoot->DFSNumIn = DFSNum++;
+
+      while (!WorkStack.empty()) {
+        DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
+        typename DomTreeNodeBase<NodeT>::iterator ChildIt =
+                                                        WorkStack.back().second;
+
+        // If we visited all of the children of this node, "recurse" back up the
+        // stack setting the DFOutNum.
+        if (ChildIt == Node->end()) {
+          Node->DFSNumOut = DFSNum++;
+          WorkStack.pop_back();
+        } else {
+          // Otherwise, recursively visit this child.
+          DomTreeNodeBase<NodeT> *Child = *ChildIt;
+          ++WorkStack.back().second;
+          
+          WorkStack.push_back(std::make_pair(Child, Child->begin()));
+          Child->DFSNumIn = DFSNum++;
+        }
+      }
+    }
+    
+    SlowQueries = 0;
+    DFSInfoValid = true;
+  }
+  
+  DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
+    if (DomTreeNodeBase<NodeT> *BBNode = this->DomTreeNodes[BB])
+      return BBNode;
+
+    // Haven't calculated this node yet?  Get or calculate the node for the
+    // immediate dominator.
+    NodeT *IDom = getIDom(BB);
+    DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom);
+
+    // Add a new tree node for this BasicBlock, and link it as a child of
+    // IDomNode
+    DomTreeNodeBase<NodeT> *C = new DomTreeNodeBase<NodeT>(BB, IDomNode);
+    return this->DomTreeNodes[BB] = IDomNode->addChild(C);
+  }
+  
+  inline NodeT *getIDom(NodeT *BB) const {
+    typename DenseMap<NodeT*, NodeT*>::const_iterator I = IDoms.find(BB);
+    return I != IDoms.end() ? I->second : 0;
+  }
+  
+  inline void addRoot(NodeT* BB) {
+    // Unreachable block is not a root node.
+    if (!isa<UnreachableInst>(&BB->back()))
+      this->Roots.push_back(BB);
+  }
+  
+public:
+  /// recalculate - compute a dominator tree for the given function
+  template<class FT>
+  void recalculate(FT& F) {
+    if (!this->IsPostDominators) {
+      reset();
+      
+      // Initialize roots
+      this->Roots.push_back(&F.front());
+      this->IDoms[&F.front()] = 0;
+      this->DomTreeNodes[&F.front()] = 0;
+      this->Vertex.push_back(0);
+      
+      Calculate<FT, NodeT*>(*this, F);
+      
+      updateDFSNumbers();
+    } else {
+      reset();     // Reset from the last time we were run...
+
+      // Initialize the roots list
+      for (typename FT::iterator I = F.begin(), E = F.end(); I != E; ++I) {
+        if (std::distance(GraphTraits<FT*>::child_begin(I),
+                          GraphTraits<FT*>::child_end(I)) == 0)
+          addRoot(I);
+
+        // Prepopulate maps so that we don't get iterator invalidation issues later.
+        this->IDoms[I] = 0;
+        this->DomTreeNodes[I] = 0;
+      }
+
+      this->Vertex.push_back(0);
+      
+      Calculate<FT, Inverse<NodeT*> >(*this, F);
+    }
+  }
 };
 
+EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
+
 //===-------------------------------------
 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 /// compute a normal dominator tree.
 ///
-class DominatorTree : public DominatorTreeBase {
+class DominatorTree : public FunctionPass {
 public:
   static char ID; // Pass ID, replacement for typeid
-  DominatorTree() : DominatorTreeBase((intptr_t)&ID, false) {}
+  DominatorTreeBase<BasicBlock>* DT;
   
-  BasicBlock *getRoot() const {
-    assert(Roots.size() == 1 && "Should always have entry node!");
-    return Roots[0];
+  DominatorTree() : FunctionPass(intptr_t(&ID)) {
+    DT = new DominatorTreeBase<BasicBlock>(false);
+  }
+  
+  ~DominatorTree() {
+    DT->releaseMemory();
+    delete DT;
+  }
+  
+  DominatorTreeBase<BasicBlock>& getBase() { return *DT; }
+  
+  /// getRoots -  Return the root blocks of the current CFG.  This may include
+  /// multiple blocks if we are computing post dominators.  For forward
+  /// dominators, this will always be a single block (the entry node).
+  ///
+  inline const std::vector<BasicBlock*> &getRoots() const {
+    return DT->getRoots();
+  }
+  
+  inline BasicBlock *getRoot() const {
+    return DT->getRoot();
+  }
+  
+  inline DomTreeNode *getRootNode() const {
+    return DT->getRootNode();
   }
   
   virtual bool runOnFunction(Function &F);
@@ -260,24 +693,110 @@ public:
   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
     AU.setPreservesAll();
   }
-private:
-  void calculate(Function& F);
-  DomTreeNode *getNodeForBlock(BasicBlock *BB);
-  unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N);
-  void Compress(BasicBlock *V);
-  BasicBlock *Eval(BasicBlock *v);
-  void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
-  inline BasicBlock *getIDom(BasicBlock *BB) const {
-      std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
-      return I != IDoms.end() ? I->second : 0;
-    }
+  
+  inline bool dominates(DomTreeNode* A, DomTreeNode* B) const {
+    return DT->dominates(A, B);
+  }
+  
+  inline bool dominates(BasicBlock* A, BasicBlock* B) const {
+    return DT->dominates(A, B);
+  }
+  
+  // dominates - Return true if A dominates B. This performs the
+  // special checks necessary if A and B are in the same basic block.
+  bool dominates(Instruction *A, Instruction *B) const {
+    BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
+    if (BBA != BBB) return DT->dominates(BBA, BBB);
+
+    // It is not possible to determine dominance between two PHI nodes 
+    // based on their ordering.
+    if (isa<PHINode>(A) && isa<PHINode>(B)) 
+      return false;
+
+    // Loop through the basic block until we find A or B.
+    BasicBlock::iterator I = BBA->begin();
+    for (; &*I != A && &*I != B; ++I) /*empty*/;
+
+    //if(!DT.IsPostDominators) {
+      // A dominates B if it is found first in the basic block.
+      return &*I == A;
+    //} else {
+    //  // A post-dominates B if B is found first in the basic block.
+    //  return &*I == B;
+    //}
+  }
+  
+  inline bool properlyDominates(const DomTreeNode* A, DomTreeNode* B) const {
+    return DT->properlyDominates(A, B);
+  }
+  
+  inline bool properlyDominates(BasicBlock* A, BasicBlock* B) const {
+    return DT->properlyDominates(A, B);
+  }
+  
+  /// findNearestCommonDominator - Find nearest common dominator basic block
+  /// for basic block A and B. If there is no such block then return NULL.
+  inline BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B) {
+    return DT->findNearestCommonDominator(A, B);
+  }
+  
+  inline DomTreeNode *operator[](BasicBlock *BB) const {
+    return DT->getNode(BB);
+  }
+  
+  /// getNode - return the (Post)DominatorTree node for the specified basic
+  /// block.  This is the same as using operator[] on this class.
+  ///
+  inline DomTreeNode *getNode(BasicBlock *BB) const {
+    return DT->getNode(BB);
+  }
+  
+  /// addNewBlock - Add a new node to the dominator tree information.  This
+  /// creates a new node as a child of DomBB dominator node,linking it into 
+  /// the children list of the immediate dominator.
+  inline DomTreeNode *addNewBlock(BasicBlock *BB, BasicBlock *DomBB) {
+    return DT->addNewBlock(BB, DomBB);
+  }
+  
+  /// changeImmediateDominator - This method is used to update the dominator
+  /// tree information when a node's immediate dominator changes.
+  ///
+  inline void changeImmediateDominator(BasicBlock *N, BasicBlock* NewIDom) {
+    DT->changeImmediateDominator(N, NewIDom);
+  }
+  
+  inline void changeImmediateDominator(DomTreeNode *N, DomTreeNode* NewIDom) {
+    DT->changeImmediateDominator(N, NewIDom);
+  }
+  
+  /// eraseNode - Removes a node from  the dominator tree. Block must not
+  /// domiante any other blocks. Removes node from its immediate dominator's
+  /// children list. Deletes dominator node associated with basic block BB.
+  inline void eraseNode(BasicBlock *BB) {
+    DT->eraseNode(BB);
+  }
+  
+  /// splitBlock - BB is split and now it has one successor. Update dominator
+  /// tree to reflect this change.
+  inline void splitBlock(BasicBlock* NewBB) {
+    DT->splitBlock(NewBB);
+  }
+  
+  
+  virtual void releaseMemory() { 
+    DT->releaseMemory();
+  }
+  
+  virtual void print(std::ostream &OS, const Module* M= 0) const {
+    DT->print(OS, M);
+  }
 };
 
 //===-------------------------------------
 /// DominatorTree GraphTraits specialization so the DominatorTree can be
 /// iterable by generic graph iterators.
 ///
-template <> struct GraphTraits<DomTreeNode*> {
+template <> struct GraphTraits<DomTreeNode *> {
   typedef DomTreeNode NodeType;
   typedef NodeType::iterator  ChildIteratorType;
   
@@ -293,190 +812,39 @@ template <> struct GraphTraits<DomTreeNode*> {
 };
 
 template <> struct GraphTraits<DominatorTree*>
-  : public GraphTraits<DomTreeNode*> {
+  : public GraphTraits<DomTreeNode *> {
   static NodeType *getEntryNode(DominatorTree *DT) {
     return DT->getRootNode();
   }
 };
 
 
-//===-------------------------------------
-/// ET-Forest Class - Class used to construct forwards and backwards 
-/// ET-Forests
-///
-class ETForestBase : public DominatorBase {
-public:
-  ETForestBase(intptr_t ID, bool isPostDom) 
-    : DominatorBase(ID, isPostDom), Nodes(), 
-      DFSInfoValid(false), SlowQueries(0) {}
-  
-  virtual void releaseMemory() { reset(); }
-
-  typedef std::map<BasicBlock*, ETNode*> ETMapType;
-
-  // FIXME : There is no need to make this interface public. 
-  // Fix predicate simplifier.
-  void updateDFSNumbers();
-    
-  /// dominates - Return true if A dominates B.
-  ///
-  inline bool dominates(BasicBlock *A, BasicBlock *B) {
-    if (A == B)
-      return true;
-    
-    ETNode *NodeA = getNode(A);
-    ETNode *NodeB = getNode(B);
-    
-    if (DFSInfoValid)
-      return NodeB->DominatedBy(NodeA);
-    else {
-      // If we end up with too many slow queries, just update the
-      // DFS numbers on the theory that we are going to keep querying.
-      SlowQueries++;
-      if (SlowQueries > 32) {
-        updateDFSNumbers();
-        return NodeB->DominatedBy(NodeA);
-      }
-      return NodeB->DominatedBySlow(NodeA);
-    }
-  }
-
-  // dominates - Return true if A dominates B. This performs the
-  // special checks necessary if A and B are in the same basic block.
-  bool dominates(Instruction *A, Instruction *B);
-
-  /// properlyDominates - Return true if A dominates B and A != B.
-  ///
-  bool properlyDominates(BasicBlock *A, BasicBlock *B) {
-    return dominates(A, B) && A != B;
-  }
-
-  /// isReachableFromEntry - Return true if A is dominated by the entry
-  /// block of the function containing it.
-  const bool isReachableFromEntry(BasicBlock* A);
-  
-  /// Return the nearest common dominator of A and B.
-  BasicBlock *nearestCommonDominator(BasicBlock *A, BasicBlock *B) const  {
-    ETNode *NodeA = getNode(A);
-    ETNode *NodeB = getNode(B);
-    
-    ETNode *Common = NodeA->NCA(NodeB);
-    if (!Common)
-      return NULL;
-    return Common->getData<BasicBlock>();
-  }
-  
-  /// Return the immediate dominator of A.
-  BasicBlock *getIDom(BasicBlock *A) const {
-    ETNode *NodeA = getNode(A);
-    if (!NodeA) return 0;
-    const ETNode *idom = NodeA->getFather();
-    return idom ? idom->getData<BasicBlock>() : 0;
-  }
-  
-  void getETNodeChildren(BasicBlock *A, std::vector<BasicBlock*>& children) const {
-    ETNode *NodeA = getNode(A);
-    if (!NodeA) return;
-    const ETNode* son = NodeA->getSon();
-    
-    if (!son) return;
-    children.push_back(son->getData<BasicBlock>());
-        
-    const ETNode* brother = son->getBrother();
-    while (brother != son) {
-      children.push_back(brother->getData<BasicBlock>());
-      brother = brother->getBrother();
-    }
-  }
-
-  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-    AU.setPreservesAll();
-    AU.addRequired<DominatorTree>();
-  }
-  //===--------------------------------------------------------------------===//
-  // API to update Forest information based on modifications
-  // to the CFG...
-
-  /// addNewBlock - Add a new block to the CFG, with the specified immediate
-  /// dominator.
-  ///
-  void addNewBlock(BasicBlock *BB, BasicBlock *IDom);
-
-  /// setImmediateDominator - Update the immediate dominator information to
-  /// change the current immediate dominator for the specified block
-  /// to another block.  This method requires that BB for NewIDom
-  /// already have an ETNode, otherwise just use addNewBlock.
-  ///
-  void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom);
-  /// print - Convert to human readable form
-  ///
-  virtual void print(std::ostream &OS, const Module* = 0) const;
-  void print(std::ostream *OS, const Module* M = 0) const {
-    if (OS) print(*OS, M);
-  }
-  virtual void dump();
-protected:
-  /// getNode - return the (Post)DominatorTree node for the specified basic
-  /// block.  This is the same as using operator[] on this class.
-  ///
-  inline ETNode *getNode(BasicBlock *BB) const {
-    ETMapType::const_iterator i = Nodes.find(BB);
-    return (i != Nodes.end()) ? i->second : 0;
-  }
-
-  inline ETNode *operator[](BasicBlock *BB) const {
-    return getNode(BB);
-  }
-
-  void reset();
-  ETMapType Nodes;
-  bool DFSInfoValid;
-  unsigned int SlowQueries;
-
-};
-
-//==-------------------------------------
-/// ETForest Class - Concrete subclass of ETForestBase that is used to
-/// compute a forwards ET-Forest.
-
-class ETForest : public ETForestBase {
-public:
-  static char ID; // Pass identification, replacement for typeid
-
-  ETForest() : ETForestBase((intptr_t)&ID, false) {}
-
-  BasicBlock *getRoot() const {
-    assert(Roots.size() == 1 && "Should always have entry node!");
-    return Roots[0];
-  }
-
-  virtual bool runOnFunction(Function &F) {
-    reset();     // Reset from the last time we were run...
-    DominatorTree &DT = getAnalysis<DominatorTree>();
-    Roots = DT.getRoots();
-    calculate(DT);
-    return false;
-  }
-
-  void calculate(const DominatorTree &DT);
-  // FIXME : There is no need to make getNodeForBlock public. Fix
-  // predicate simplifier.
-  ETNode *getNodeForBlock(BasicBlock *BB);
-};
-
 //===----------------------------------------------------------------------===//
 /// DominanceFrontierBase - Common base class for computing forward and inverse
 /// dominance frontiers for a function.
 ///
-class DominanceFrontierBase : public DominatorBase {
+class DominanceFrontierBase : public FunctionPass {
 public:
   typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
   typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
 protected:
   DomSetMapType Frontiers;
+    std::vector<BasicBlock*> Roots;
+    const bool IsPostDominators;
+  
 public:
   DominanceFrontierBase(intptr_t ID, bool isPostDom) 
-    : DominatorBase(ID, isPostDom) {}
+    : FunctionPass(ID), IsPostDominators(isPostDom) {}
+
+  /// getRoots -  Return the root blocks of the current CFG.  This may include
+  /// multiple blocks if we are computing post dominators.  For forward
+  /// dominators, this will always be a single block (the entry node).
+  ///
+  inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
+  
+  /// isPostDominator - Returns true if analysis based of postdoms
+  ///
+  bool isPostDominator() const { return IsPostDominators; }
 
   virtual void releaseMemory() { Frontiers.clear(); }
 
@@ -495,6 +863,14 @@ public:
     Frontiers.insert(std::make_pair(BB, frontier));
   }
 
+  /// removeBlock - Remove basic block BB's frontier.
+  void removeBlock(BasicBlock *BB) {
+    assert(find(BB) != end() && "Block is not in DominanceFrontier!");
+    for (iterator I = begin(), E = end(); I != E; ++I)
+      I->second.erase(BB);
+    Frontiers.erase(BB);
+  }
+
   void addToFrontier(iterator I, BasicBlock *Node) {
     assert(I != end() && "BB is not in DominanceFrontier!");
     I->second.insert(Node);
@@ -524,7 +900,7 @@ class DominanceFrontier : public DominanceFrontierBase {
 public:
   static char ID; // Pass ID, replacement for typeid
   DominanceFrontier() : 
-    DominanceFrontierBase((intptr_t)& ID, false) {}
+    DominanceFrontierBase(intptr_t(&ID), false) {}
 
   BasicBlock *getRoot() const {
     assert(Roots.size() == 1 && "Should always have entry node!");
@@ -545,6 +921,30 @@ public:
     AU.addRequired<DominatorTree>();
   }
 
+  /// splitBlock - BB is split and now it has one successor. Update dominance
+  /// frontier to reflect this change.
+  void splitBlock(BasicBlock *BB);
+
+  /// BasicBlock BB's new dominator is NewBB. Update BB's dominance frontier
+  /// to reflect this change.
+  void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB,
+                                DominatorTree *DT) {
+    // NewBB is now  dominating BB. Which means BB's dominance
+    // frontier is now part of NewBB's dominance frontier. However, BB
+    // itself is not member of NewBB's dominance frontier.
+    DominanceFrontier::iterator NewDFI = find(NewBB);
+    DominanceFrontier::iterator DFI = find(BB);
+    DominanceFrontier::DomSetType BBSet = DFI->second;
+    for (DominanceFrontier::DomSetType::iterator BBSetI = BBSet.begin(),
+           BBSetE = BBSet.end(); BBSetI != BBSetE; ++BBSetI) {
+      BasicBlock *DFMember = *BBSetI;
+      // Insert only if NewBB dominates DFMember.
+      if (!DT->dominates(NewBB, DFMember))
+        NewDFI->second.insert(DFMember);
+    }
+    NewDFI->second.erase(BB);
+  }
+
 private:
   const DomSetType &calculate(const DominatorTree &DT,
                               const DomTreeNode *Node);