Remove ETForest.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37765 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 1 insertions, 1031 deletions

diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 0b62c513fe..9873759025 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,7 +21,6 @@
 #ifndef LLVM_ANALYSIS_DOMINATORS_H
 #define LLVM_ANALYSIS_DOMINATORS_H
 
-#include "llvm/Analysis/ET-Forest.h"
 #include "llvm/Pass.h"
 #include <set>
 
@@ -347,170 +344,6 @@ template <> struct GraphTraits<DominatorTree*>
 };
 
 
-//===-------------------------------------
-/// 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.
diff --git a/include/llvm/Analysis/ET-Forest.h b/include/llvm/Analysis/ET-Forest.h
deleted file mode 100644
index 8bd5e447bc..0000000000
--- a/include/llvm/Analysis/ET-Forest.h
+++ /dev/null
@@ -1,312 +0,0 @@
-//===- llvm/Analysis/ET-Forest.h - ET-Forest implementation -----*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file was written by Daniel Berlin from code written by Pavel Nejedy, and
-// is distributed under the University of Illinois Open Source License. See
-// LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file defines the following classes:
-//  1. ETNode:  A node in the ET forest.
-//  2. ETOccurrence: An occurrence of the node in the splay tree
-//  storing the DFS path information.
-//
-//  The ET-forest structure is described in:
-//    D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
-//    J.  G'omput. System Sci., 26(3):362 381, 1983.
-//
-// Basically, the ET-Forest is storing the dominator tree (ETNode),
-// and a splay tree containing the depth first path information for
-// those nodes (ETOccurrence).  This enables us to answer queries
-// about domination (DominatedBySlow), and ancestry (NCA) in
-// logarithmic time, and perform updates to the information in
-// logarithmic time.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_ETFOREST_H
-#define LLVM_ANALYSIS_ETFOREST_H
-
-#include <cassert>
-#include <cstdlib>
-
-namespace llvm {
-class ETNode;
-
-/// ETOccurrence - An occurrence for a node in the et tree
-///
-/// The et occurrence tree is really storing the sequences you get from
-/// doing a DFS over the ETNode's.  It is stored as a modified splay
-/// tree.
-/// ET occurrences can occur at multiple places in the ordering depending
-/// on how many ET nodes have it as their father.  To handle
-/// this, they are separate from the nodes.
-///
-class ETOccurrence {
-public:
-  ETOccurrence(ETNode *n): OccFor(n), Parent(NULL), Left(NULL), Right(NULL),
-    Depth(0), Min(0), MinOccurrence(this) {};
-
-  void setParent(ETOccurrence *n) {
-    assert(n != this && "Trying to set parent to ourselves");
-    Parent = n;
-  }
-
-  // Add D to our current depth
-  void setDepthAdd(int d) {
-    Min += d;
-    Depth += d;
-  }
-  
-  // Reset our depth to D
-  void setDepth(int d) {
-    Min += d - Depth;
-    Depth = d;
-  }
-
-  // Set Left to N
-  void setLeft(ETOccurrence *n) {
-    assert(n != this && "Trying to set our left to ourselves");
-    Left = n;
-    if (n)
-      n->setParent(this);
-  }
-  
-  // Set Right to N
-  void setRight(ETOccurrence *n) {
-    assert(n != this && "Trying to set our right to ourselves");
-    Right = n;
-    if (n)
-      n->setParent(this);
-  }
-  
-  // Splay us to the root of the tree
-  void Splay(void);
-
-  // Recompute the minimum occurrence for this occurrence.
-  void recomputeMin(void) {
-    ETOccurrence *themin = Left;
-    
-    // The min may be our Right, too.
-    if (!themin || (Right && themin->Min > Right->Min))
-      themin = Right;
-    
-    if (themin && themin->Min < 0) {
-      Min = themin->Min + Depth;
-      MinOccurrence = themin->MinOccurrence;
-    } else {
-      Min = Depth;
-      MinOccurrence = this;
-    }
-  }
- private:
-  friend class ETNode;
-
-    // Node we represent
-  ETNode *OccFor;
-
-  // Parent in the splay tree
-  ETOccurrence *Parent;
-
-  // Left Son in the splay tree
-  ETOccurrence *Left;
-
-  // Right Son in the splay tree
-  ETOccurrence *Right;
-
-  // Depth of the node is the sum of the depth on the path to the
-  // root.
-  int Depth;
-
-  // Subtree occurrence's minimum depth
-  int Min;
-
-  // Subtree occurrence with minimum depth
-  ETOccurrence *MinOccurrence;
-};
-
-
-class ETNode {
-public:
-  ETNode(void *d) : data(d), DFSNumIn(-1), DFSNumOut(-1),
-                    Father(NULL), Left(NULL),
-                    Right(NULL), Son(NULL), ParentOcc(NULL) {   
-    RightmostOcc = new ETOccurrence(this);
-  };
-
-  // This does *not* maintain the tree structure.
-  // If you want to remove a node from the forest structure, use
-  // removeFromForest()
-  ~ETNode() {
-    delete RightmostOcc;
-    delete ParentOcc;
-  }
-
-  void removeFromForest() {
-    // Split us away from all our sons.
-    while (Son)
-      Son->Split();
-    
-    // And then split us away from our father.
-    if (Father)
-      Father->Split();
-  }
-
-  // Split us away from our parents and children, so that we can be
-  // reparented. NB: setFather WILL NOT DO WHAT YOU WANT IF YOU DO NOT
-  // SPLIT US FIRST.
-  void Split();
-
-  // Set our parent node to the passed in node
-  void setFather(ETNode *);
-  
-  // Nearest Common Ancestor of two et nodes.
-  ETNode *NCA(ETNode *);
-  
-  // Return true if we are below the passed in node in the forest.
-  bool Below(ETNode *);
-  /*
-   Given a dominator tree, we can determine whether one thing
-   dominates another in constant time by using two DFS numbers:
-  
-   1. The number for when we visit a node on the way down the tree
-   2. The number for when we visit a node on the way back up the tree
-  
-   You can view these as bounds for the range of dfs numbers the
-   nodes in the subtree of the dominator tree rooted at that node
-   will contain.
-  
-   The dominator tree is always a simple acyclic tree, so there are
-   only three possible relations two nodes in the dominator tree have
-   to each other:
-  
-   1. Node A is above Node B (and thus, Node A dominates node B)
-  
-        A
-        |
-        C
-       / \ 
-      B   D
-  
-  
-   In the above case, DFS_Number_In of A will be <= DFS_Number_In of
-   B, and DFS_Number_Out of A will be >= DFS_Number_Out of B.  This is
-   because we must hit A in the dominator tree *before* B on the walk
-   down, and we will hit A *after* B on the walk back up
-  
-   2. Node A is below node B (and thus, node B dominates node B)
-       
-        B
-        |
-        A
-       / \ 
-      C   D
-  
-   In the above case, DFS_Number_In of A will be >= DFS_Number_In of
-   B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
-  
-   This is because we must hit A in the dominator tree *after* B on
-   the walk down, and we will hit A *before* B on the walk back up
-  
-   3. Node A and B are siblings (and thus, neither dominates the other)
-  
-        C
-        |
-        D
-       / \                        
-      A   B
-  
-   In the above case, DFS_Number_In of A will *always* be <=
-   DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
-   DFS_Number_Out of B.  This is because we will always finish the dfs
-   walk of one of the subtrees before the other, and thus, the dfs
-   numbers for one subtree can't intersect with the range of dfs
-   numbers for the other subtree.  If you swap A and B's position in
-   the dominator tree, the comparison changes direction, but the point
-   is that both comparisons will always go the same way if there is no
-   dominance relationship.
-  
-   Thus, it is sufficient to write
-  
-   A_Dominates_B(node A, node B) {
-      return DFS_Number_In(A) <= DFS_Number_In(B) &&
-             DFS_Number_Out(A) >= DFS_Number_Out(B);
-   }
-  
-   A_Dominated_by_B(node A, node B) {
-     return DFS_Number_In(A) >= DFS_Number_In(A) &&
-            DFS_Number_Out(A) <= DFS_Number_Out(B);
-   }
-  */
-  bool DominatedBy(ETNode *other) const {
-    return this->DFSNumIn >= other->DFSNumIn &&
-           this->DFSNumOut <= other->DFSNumOut;
-  }
-  
-  // This method is slower, but doesn't require the DFS numbers to
-  // be up to date.
-  bool DominatedBySlow(ETNode *other) {
-    return this->Below(other);
-  }
-
-  void assignDFSNumber (int);
-  
-  bool hasFather() const {
-    return Father != NULL;
-  }
-
-  // Do not let people play around with fathers.
-  const ETNode *getFather() const {
-    return Father;
-  }
-
-  template <typename T>
-  T *getData() const {
-    return static_cast<T*>(data);
-  }
-  
-  unsigned getDFSNumIn() const {
-    return DFSNumIn;
-  }
-  
-  unsigned getDFSNumOut() const {
-    return DFSNumOut;
-  }
-
-  const ETNode *getSon() const {
-    return Son;
-  }
-  
-  const ETNode *getBrother() const {
-    return Left;
-  }
-
- private:
-  // Data represented by the node
-  void *data;
-
-  // DFS Numbers
-  int DFSNumIn, DFSNumOut;
-
-  // Father
-  ETNode *Father;
-
-  // Brothers.  Node, this ends up being a circularly linked list.
-  // Thus, if you want to get all the brothers, you need to stop when
-  // you hit node == this again.
-  ETNode *Left, *Right;
-
-  // First Son
-  ETNode *Son;
-
-  // Rightmost occurrence for this node
-  ETOccurrence *RightmostOcc;
-
-  // Parent occurrence for this node
-  ETOccurrence *ParentOcc;
-};
-}  // end llvm namespace
-
-#endif
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index 256cf1ca44..f8aef5dde2 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -805,554 +805,3 @@ void DominanceFrontierBase::print(std::ostream &o, const Module* ) const {
 void DominanceFrontierBase::dump() {
   print (llvm::cerr);
 }
-
-
-//===----------------------------------------------------------------------===//
-// ETOccurrence Implementation
-//===----------------------------------------------------------------------===//
-
-void ETOccurrence::Splay() {
-  ETOccurrence *father;
-  ETOccurrence *grandfather;
-  int occdepth;
-  int fatherdepth;
-  
-  while (Parent) {
-    occdepth = Depth;
-    
-    father = Parent;
-    fatherdepth = Parent->Depth;
-    grandfather = father->Parent;
-    
-    // If we have no grandparent, a single zig or zag will do.
-    if (!grandfather) {
-      setDepthAdd(fatherdepth);
-      MinOccurrence = father->MinOccurrence;
-      Min = father->Min;
-      
-      // See what we have to rotate
-      if (father->Left == this) {
-        // Zig
-        father->setLeft(Right);
-        setRight(father);
-        if (father->Left)
-          father->Left->setDepthAdd(occdepth);
-      } else {
-        // Zag
-        father->setRight(Left);
-        setLeft(father);
-        if (father->Right)
-          father->Right->setDepthAdd(occdepth);
-      }
-      father->setDepth(-occdepth);
-      Parent = NULL;
-      
-      father->recomputeMin();
-      return;
-    }
-    
-    // If we have a grandfather, we need to do some
-    // combination of zig and zag.
-    int grandfatherdepth = grandfather->Depth;
-    
-    setDepthAdd(fatherdepth + grandfatherdepth);
-    MinOccurrence = grandfather->MinOccurrence;
-    Min = grandfather->Min;
-    
-    ETOccurrence *greatgrandfather = grandfather->Parent;
-    
-    if (grandfather->Left == father) {
-      if (father->Left == this) {
-        // Zig zig
-        grandfather->setLeft(father->Right);
-        father->setLeft(Right);
-        setRight(father);
-        father->setRight(grandfather);
-        
-        father->setDepth(-occdepth);
-        
-        if (father->Left)
-          father->Left->setDepthAdd(occdepth);
-        
-        grandfather->setDepth(-fatherdepth);
-        if (grandfather->Left)
-          grandfather->Left->setDepthAdd(fatherdepth);
-      } else {
-        // Zag zig
-        grandfather->setLeft(Right);
-        father->setRight(Left);
-        setLeft(father);
-        setRight(grandfather);
-        
-        father->setDepth(-occdepth);
-        if (father->Right)
-          father->Right->setDepthAdd(occdepth);
-        grandfather->setDepth(-occdepth - fatherdepth);
-        if (grandfather->Left)
-          grandfather->Left->setDepthAdd(occdepth + fatherdepth);
-      }
-    } else {
-      if (father->Left == this) {
-        // Zig zag
-        grandfather->setRight(Left);
-        father->setLeft(Right);
-        setLeft(grandfather);
-        setRight(father);
-        
-        father->setDepth(-occdepth);
-        if (father->Left)
-          father->Left->setDepthAdd(occdepth);
-        grandfather->setDepth(-occdepth - fatherdepth);
-        if (grandfather->Right)
-          grandfather->Right->setDepthAdd(occdepth + fatherdepth);
-      } else {              // Zag Zag
-        grandfather->setRight(father->Left);
-        father->setRight(Left);
-        setLeft(father);
-        father->setLeft(grandfather);
-        
-        father->setDepth(-occdepth);
-        if (father->Right)
-          father->Right->setDepthAdd(occdepth);
-        grandfather->setDepth(-fatherdepth);
-        if (grandfather->Right)
-          grandfather->Right->setDepthAdd(fatherdepth);
-      }
-    }
-    
-    // Might need one more rotate depending on greatgrandfather.
-    setParent(greatgrandfather);
-    if (greatgrandfather) {
-      if (greatgrandfather->Left == grandfather)
-        greatgrandfather->Left = this;
-      else
-        greatgrandfather->Right = this;
-      
-    }
-    grandfather->recomputeMin();
-    father->recomputeMin();
-  }
-}
-
-//===----------------------------------------------------------------------===//
-// ETNode implementation
-//===----------------------------------------------------------------------===//
-
-void ETNode::Split() {
-  ETOccurrence *right, *left;
-  ETOccurrence *rightmost = RightmostOcc;
-  ETOccurrence *parent;
-
-  // Update the occurrence tree first.
-  RightmostOcc->Splay();
-
-  // Find the leftmost occurrence in the rightmost subtree, then splay
-  // around it.
-  for (right = rightmost->Right; right->Left; right = right->Left);
-
-  right->Splay();
-
-  // Start splitting
-  right->Left->Parent = NULL;
-  parent = ParentOcc;
-  parent->Splay();
-  ParentOcc = NULL;
-
-  left = parent->Left;
-  parent->Right->Parent = NULL;
-
-  right->setLeft(left);
-
-  right->recomputeMin();
-
-  rightmost->Splay();
-  rightmost->Depth = 0;
-  rightmost->Min = 0;
-
-  delete parent;
-
-  // Now update *our* tree
-
-  if (Father->Son == this)
-    Father->Son = Right;
-
-  if (Father->Son == this)
-    Father->Son = NULL;
-  else {
-    Left->Right = Right;
-    Right->Left = Left;
-  }
-  Left = Right = NULL;
-  Father = NULL;
-}
-
-void ETNode::setFather(ETNode *NewFather) {
-  ETOccurrence *rightmost;
-  ETOccurrence *leftpart;
-  ETOccurrence *NewFatherOcc;
-  ETOccurrence *temp;
-
-  // First update the path in the splay tree
-  NewFatherOcc = new ETOccurrence(NewFather);
-
-  rightmost = NewFather->RightmostOcc;
-  rightmost->Splay();
-
-  leftpart = rightmost->Left;
-
-  temp = RightmostOcc;
-  temp->Splay();
-
-  NewFatherOcc->setLeft(leftpart);
-  NewFatherOcc->setRight(temp);
-
-  temp->Depth++;
-  temp->Min++;
-  NewFatherOcc->recomputeMin();
-
-  rightmost->setLeft(NewFatherOcc);
-
-  if (NewFatherOcc->Min + rightmost->Depth < rightmost->Min) {
-    rightmost->Min = NewFatherOcc->Min + rightmost->Depth;
-    rightmost->MinOccurrence = NewFatherOcc->MinOccurrence;
-  }
-
-  delete ParentOcc;
-  ParentOcc = NewFatherOcc;
-
-  // Update *our* tree
-  ETNode *left;
-  ETNode *right;
-
-  Father = NewFather;
-  right = Father->Son;
-
-  if (right)
-    left = right->Left;
-  else
-    left = right = this;
-
-  left->Right = this;
-  right->Left = this;
-  Left = left;
-  Right = right;
-
-  Father->Son = this;
-}
-
-bool ETNode::Below(ETNode *other) {
-  ETOccurrence *up = other->RightmostOcc;
-  ETOccurrence *down = RightmostOcc;
-
-  if (this == other)
-    return true;
-
-  up->Splay();
-
-  ETOccurrence *left, *right;
-  left = up->Left;
-  right = up->Right;
-
-  if (!left)
-    return false;
-
-  left->Parent = NULL;
-
-  if (right)
-    right->Parent = NULL;
-
-  down->Splay();
-
-  if (left == down || left->Parent != NULL) {
-    if (right)
-      right->Parent = up;
-    up->setLeft(down);
-  } else {
-    left->Parent = up;
-
-    // If the two occurrences are in different trees, put things
-    // back the way they were.
-    if (right && right->Parent != NULL)
-      up->setRight(down);
-    else
-      up->setRight(right);
-    return false;
-  }
-
-  if (down->Depth <= 0)
-    return false;
-
-  return !down->Right || down->Right->Min + down->Depth >= 0;
-}
-
-ETNode *ETNode::NCA(ETNode *other) {
-  ETOccurrence *occ1 = RightmostOcc;
-  ETOccurrence *occ2 = other->RightmostOcc;
-  
-  ETOccurrence *left, *right, *ret;
-  ETOccurrence *occmin;
-  int mindepth;
-  
-  if (this == other)
-    return this;
-  
-  occ1->Splay();
-  left = occ1->Left;
-  right = occ1->Right;
-  
-  if (left)
-    left->Parent = NULL;
-  
-  if (right)
-    right->Parent = NULL;
-  occ2->Splay();
-
-  if (left == occ2 || (left && left->Parent != NULL)) {
-    ret = occ2->Right;
-    
-    occ1->setLeft(occ2);
-    if (right)
-      right->Parent = occ1;
-  } else {
-    ret = occ2->Left;
-    
-    occ1->setRight(occ2);
-    if (left)
-      left->Parent = occ1;
-  }
-
-  if (occ2->Depth > 0) {
-    occmin = occ1;
-    mindepth = occ1->Depth;
-  } else {
-    occmin = occ2;
-    mindepth = occ2->Depth + occ1->Depth;
-  }
-  
-  if (ret && ret->Min + occ1->Depth + occ2->Depth < mindepth)
-    return ret->MinOccurrence->OccFor;
-  else
-    return occmin->OccFor;
-}
-
-void ETNode::assignDFSNumber(int num) {
-  std::vector<ETNode *>  workStack;
-  std::set<ETNode *> visitedNodes;
-  
-  workStack.push_back(this);
-  visitedNodes.insert(this);
-  this->DFSNumIn = num++;
-
-  while (!workStack.empty()) {
-    ETNode  *Node = workStack.back();
-    
-    // If this is leaf node then set DFSNumOut and pop the stack
-    if (!Node->Son) {
-      Node->DFSNumOut = num++;
-      workStack.pop_back();
-      continue;
-    }
-    
-    ETNode *son = Node->Son;
-    
-    // Visit Node->Son first
-    if (visitedNodes.count(son) == 0) {
-      son->DFSNumIn = num++;
-      workStack.push_back(son);
-      visitedNodes.insert(son);
-      continue;
-    }
-    
-    bool visitChild = false;
-    // Visit remaining children
-    for (ETNode *s = son->Right;  s != son && !visitChild; s = s->Right) {
-      if (visitedNodes.count(s) == 0) {
-        visitChild = true;
-        s->DFSNumIn = num++;
-        workStack.push_back(s);
-        visitedNodes.insert(s);
-      }
-    }
-    
-    if (!visitChild) {
-      // If we reach here means all children are visited
-      Node->DFSNumOut = num++;
-      workStack.pop_back();
-    }
-  }
-}
-
-//===----------------------------------------------------------------------===//
-// ETForest implementation
-//===----------------------------------------------------------------------===//
-
-char ETForest::ID = 0;
-static RegisterPass<ETForest>
-D("etforest", "ET Forest Construction", true);
-
-void ETForestBase::reset() {
-  for (ETMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
-    delete I->second;
-  Nodes.clear();
-}
-
-void ETForestBase::updateDFSNumbers()
-{
-  int dfsnum = 0;
-  // Iterate over all nodes in depth first order.
-  for (unsigned i = 0, e = Roots.size(); i != e; ++i)
-    for (df_iterator<BasicBlock*> I = df_begin(Roots[i]),
-           E = df_end(Roots[i]); I != E; ++I) {
-      BasicBlock *BB = *I;
-      ETNode *ETN = getNode(BB);
-      if (ETN && !ETN->hasFather())
-        ETN->assignDFSNumber(dfsnum);    
-  }
-  SlowQueries = 0;
-  DFSInfoValid = true;
-}
-
-// dominates - Return true if A dominates B. THis performs the
-// special checks necessary if A and B are in the same basic block.
-bool ETForestBase::dominates(Instruction *A, Instruction *B) {
-  BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
-  if (BBA != BBB) return 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(!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;
-  }
-}
-
-/// isReachableFromEntry - Return true if A is dominated by the entry
-/// block of the function containing it.
-const bool ETForestBase::isReachableFromEntry(BasicBlock* A) {
-  return dominates(&A->getParent()->getEntryBlock(), A);
-}
-
-// FIXME : There is no need to make getNodeForBlock public. Fix
-// predicate simplifier.
-ETNode *ETForest::getNodeForBlock(BasicBlock *BB) {
-  ETNode *&BBNode = Nodes[BB];
-  if (BBNode) return BBNode;
-
-  // Haven't calculated this node yet?  Get or calculate the node for the
-  // immediate dominator.
-  DomTreeNode *node= getAnalysis<DominatorTree>().getNode(BB);
-
-  // If we are unreachable, we may not have an immediate dominator.
-  if (!node || !node->getIDom())
-    return BBNode = new ETNode(BB);
-  else {
-    ETNode *IDomNode = getNodeForBlock(node->getIDom()->getBlock());
-    
-    // Add a new tree node for this BasicBlock, and link it as a child of
-    // IDomNode
-    BBNode = new ETNode(BB);
-    BBNode->setFather(IDomNode);
-    return BBNode;
-  }
-}
-
-void ETForest::calculate(const DominatorTree &DT) {
-  assert(Roots.size() == 1 && "ETForest should have 1 root block!");
-  BasicBlock *Root = Roots[0];
-  Nodes[Root] = new ETNode(Root); // Add a node for the root
-
-  Function *F = Root->getParent();
-  // Loop over all of the reachable blocks in the function...
-  for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
-    DomTreeNode* node = DT.getNode(I);
-    if (node && node->getIDom()) {  // Reachable block.
-      BasicBlock* ImmDom = node->getIDom()->getBlock();
-      ETNode *&BBNode = Nodes[I];
-      if (!BBNode) {  // Haven't calculated this node yet?
-        // Get or calculate the node for the immediate dominator
-        ETNode *IDomNode =  getNodeForBlock(ImmDom);
-
-        // Add a new ETNode for this BasicBlock, and set it's parent
-        // to it's immediate dominator.
-        BBNode = new ETNode(I);
-        BBNode->setFather(IDomNode);
-      }
-    }
-  }
-
-  // Make sure we've got nodes around for every block
-  for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
-    ETNode *&BBNode = Nodes[I];
-    if (!BBNode)
-      BBNode = new ETNode(I);
-  }
-
-  updateDFSNumbers ();
-}
-
-//===----------------------------------------------------------------------===//
-// ETForestBase Implementation
-//===----------------------------------------------------------------------===//
-
-void ETForestBase::addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
-  ETNode *&BBNode = Nodes[BB];
-  assert(!BBNode && "BasicBlock already in ET-Forest");
-
-  BBNode = new ETNode(BB);
-  BBNode->setFather(getNode(IDom));
-  DFSInfoValid = false;
-}
-
-void ETForestBase::setImmediateDominator(BasicBlock *BB, BasicBlock *newIDom) {
-  assert(getNode(BB) && "BasicBlock not in ET-Forest");
-  assert(getNode(newIDom) && "IDom not in ET-Forest");
-  
-  ETNode *Node = getNode(BB);
-  if (Node->hasFather()) {
-    if (Node->getFather()->getData<BasicBlock>() == newIDom)
-      return;
-    Node->Split();
-  }
-  Node->setFather(getNode(newIDom));
-  DFSInfoValid= false;
-}
-
-void ETForestBase::print(std::ostream &o, const Module *) const {
-  o << "=============================--------------------------------\n";
-  o << "ET Forest:\n";
-  o << "DFS Info ";
-  if (DFSInfoValid)
-    o << "is";
-  else
-    o << "is not";
-  o << " up to date\n";
-
-  Function *F = getRoots()[0]->getParent();
-  for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
-    o << "  DFS Numbers For Basic Block:";
-    WriteAsOperand(o, I, false);
-    o << " are:";
-    if (ETNode *EN = getNode(I)) {
-      o << "In: " << EN->getDFSNumIn();
-      o << " Out: " << EN->getDFSNumOut() << "\n";
-    } else {
-      o << "No associated ETNode";
-    }
-    o << "\n";
-  }
-  o << "\n";
-}
-
-void ETForestBase::dump() {
-  print (llvm::cerr);
-}