LLVM API Documentation

ET-Forest.h

Go to the documentation of this file.
00001 //===- llvm/Analysis/ET-Forest.h - ET-Forest implementation -----*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was written by Daniel Berlin from code written by Pavel Nejedy, and
00006 // is distributed under the University of Illinois Open Source License. See
00007 // LICENSE.TXT for details.
00008 //
00009 //===----------------------------------------------------------------------===//
00010 //
00011 // This file defines the following classes:
00012 //  1. ETNode:  A node in the ET forest.
00013 //  2. ETOccurrence: An occurrence of the node in the splay tree
00014 //  storing the DFS path information.
00015 //
00016 //  The ET-forest structure is described in:
00017 //    D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
00018 //    J.  G'omput. System Sci., 26(3):362 381, 1983.
00019 //
00020 // Basically, the ET-Forest is storing the dominator tree (ETNode),
00021 // and a splay tree containing the depth first path information for
00022 // those nodes (ETOccurrence).  This enables us to answer queries
00023 // about domination (DominatedBySlow), and ancestry (NCA) in
00024 // logarithmic time, and perform updates to the information in
00025 // logarithmic time.
00026 //
00027 //===----------------------------------------------------------------------===//
00028 
00029 #ifndef LLVM_ANALYSIS_ETFOREST_H
00030 #define LLVM_ANALYSIS_ETFOREST_H
00031 
00032 #include <cassert>
00033 #include <cstdlib>
00034 
00035 namespace llvm {
00036 class ETNode;
00037 
00038 /// ETOccurrence - An occurrence for a node in the et tree
00039 ///
00040 /// The et occurrence tree is really storing the sequences you get from
00041 /// doing a DFS over the ETNode's.  It is stored as a modified splay
00042 /// tree.
00043 /// ET occurrences can occur at multiple places in the ordering depending
00044 /// on how many ET nodes have it as their father.  To handle
00045 /// this, they are separate from the nodes.
00046 ///
00047 class ETOccurrence {
00048 public:
00049   ETOccurrence(ETNode *n): OccFor(n), Parent(NULL), Left(NULL), Right(NULL),
00050     Depth(0), Min(0), MinOccurrence(this) {};
00051 
00052   void setParent(ETOccurrence *n) {
00053     assert(n != this && "Trying to set parent to ourselves");
00054     Parent = n;
00055   }
00056 
00057   // Add D to our current depth
00058   void setDepthAdd(int d) {
00059     Min += d;
00060     Depth += d;
00061   }
00062   
00063   // Reset our depth to D
00064   void setDepth(int d) {
00065     Min += d - Depth;
00066     Depth = d;
00067   }
00068 
00069   // Set Left to N
00070   void setLeft(ETOccurrence *n) {
00071     assert(n != this && "Trying to set our left to ourselves");
00072     Left = n;
00073     if (n)
00074       n->setParent(this);
00075   }
00076   
00077   // Set Right to N
00078   void setRight(ETOccurrence *n) {
00079     assert(n != this && "Trying to set our right to ourselves");
00080     Right = n;
00081     if (n)
00082       n->setParent(this);
00083   }
00084   
00085   // Splay us to the root of the tree
00086   void Splay(void);
00087 
00088   // Recompute the minimum occurrence for this occurrence.
00089   void recomputeMin(void) {
00090     ETOccurrence *themin = Left;
00091     
00092     // The min may be our Right, too.
00093     if (!themin || (Right && themin->Min > Right->Min))
00094       themin = Right;
00095     
00096     if (themin && themin->Min < 0) {
00097       Min = themin->Min + Depth;
00098       MinOccurrence = themin->MinOccurrence;
00099     } else {
00100       Min = Depth;
00101       MinOccurrence = this;
00102     }
00103   }
00104  private:
00105   friend class ETNode;
00106 
00107     // Node we represent
00108   ETNode *OccFor;
00109 
00110   // Parent in the splay tree
00111   ETOccurrence *Parent;
00112 
00113   // Left Son in the splay tree
00114   ETOccurrence *Left;
00115 
00116   // Right Son in the splay tree
00117   ETOccurrence *Right;
00118 
00119   // Depth of the node is the sum of the depth on the path to the
00120   // root.
00121   int Depth;
00122 
00123   // Subtree occurrence's minimum depth
00124   int Min;
00125 
00126   // Subtree occurrence with minimum depth
00127   ETOccurrence *MinOccurrence;
00128 };
00129 
00130 
00131 class ETNode {
00132 public:
00133   ETNode(void *d) : data(d), DFSNumIn(-1), DFSNumOut(-1),
00134                     Father(NULL), Left(NULL),
00135                     Right(NULL), Son(NULL), ParentOcc(NULL) {   
00136     RightmostOcc = new ETOccurrence(this);
00137   };
00138 
00139   // This does *not* maintain the tree structure.
00140   // If you want to remove a node from the forest structure, use
00141   // removeFromForest()
00142   ~ETNode() {
00143     delete RightmostOcc;
00144   }
00145 
00146   void removeFromForest() {
00147     // Split us away from all our sons.
00148     while (Son)
00149       Son->Split();
00150     
00151     // And then split us away from our father.
00152     if (Father)
00153       Father->Split();
00154   }
00155 
00156   // Split us away from our parents and children, so that we can be
00157   // reparented. NB: setFather WILL NOT DO WHAT YOU WANT IF YOU DO NOT
00158   // SPLIT US FIRST.
00159   void Split();
00160 
00161   // Set our parent node to the passed in node
00162   void setFather(ETNode *);
00163   
00164   // Nearest Common Ancestor of two et nodes.
00165   ETNode *NCA(ETNode *);
00166   
00167   // Return true if we are below the passed in node in the forest.
00168   bool Below(ETNode *);
00169   /*
00170    Given a dominator tree, we can determine whether one thing
00171    dominates another in constant time by using two DFS numbers:
00172   
00173    1. The number for when we visit a node on the way down the tree
00174    2. The number for when we visit a node on the way back up the tree
00175   
00176    You can view these as bounds for the range of dfs numbers the
00177    nodes in the subtree of the dominator tree rooted at that node
00178    will contain.
00179   
00180    The dominator tree is always a simple acyclic tree, so there are
00181    only three possible relations two nodes in the dominator tree have
00182    to each other:
00183   
00184    1. Node A is above Node B (and thus, Node A dominates node B)
00185   
00186         A
00187         |
00188         C
00189        / \ 
00190       B   D
00191   
00192   
00193    In the above case, DFS_Number_In of A will be <= DFS_Number_In of
00194    B, and DFS_Number_Out of A will be >= DFS_Number_Out of B.  This is
00195    because we must hit A in the dominator tree *before* B on the walk
00196    down, and we will hit A *after* B on the walk back up
00197   
00198    2. Node A is below node B (and thus, node B dominates node B)
00199        
00200         B
00201         |
00202         A
00203        / \ 
00204       C   D
00205   
00206    In the above case, DFS_Number_In of A will be >= DFS_Number_In of
00207    B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
00208   
00209    This is because we must hit A in the dominator tree *after* B on
00210    the walk down, and we will hit A *before* B on the walk back up
00211   
00212    3. Node A and B are siblings (and thus, neither dominates the other)
00213   
00214         C
00215         |
00216         D
00217        / \                        
00218       A   B
00219   
00220    In the above case, DFS_Number_In of A will *always* be <=
00221    DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
00222    DFS_Number_Out of B.  This is because we will always finish the dfs
00223    walk of one of the subtrees before the other, and thus, the dfs
00224    numbers for one subtree can't intersect with the range of dfs
00225    numbers for the other subtree.  If you swap A and B's position in
00226    the dominator tree, the comparison changes direction, but the point
00227    is that both comparisons will always go the same way if there is no
00228    dominance relationship.
00229   
00230    Thus, it is sufficient to write
00231   
00232    A_Dominates_B(node A, node B) {
00233       return DFS_Number_In(A) <= DFS_Number_In(B) &&
00234              DFS_Number_Out(A) >= DFS_Number_Out(B);
00235    }
00236   
00237    A_Dominated_by_B(node A, node B) {
00238      return DFS_Number_In(A) >= DFS_Number_In(A) &&
00239             DFS_Number_Out(A) <= DFS_Number_Out(B);
00240    }
00241   */
00242   bool DominatedBy(ETNode *other) const {
00243     return this->DFSNumIn >= other->DFSNumIn &&
00244            this->DFSNumOut <= other->DFSNumOut;
00245   }
00246   
00247   // This method is slower, but doesn't require the DFS numbers to
00248   // be up to date.
00249   bool DominatedBySlow(ETNode *other) {
00250     return this->Below(other);
00251   }
00252 
00253   void assignDFSNumber(int &num) {
00254     DFSNumIn = num++;
00255     
00256     if (Son) {
00257       Son->assignDFSNumber(num);
00258       for (ETNode *son = Son->Right; son != Son; son = son->Right)
00259         son->assignDFSNumber(num);
00260     }
00261     DFSNumOut = num++;
00262   }
00263   
00264   bool hasFather() const {
00265     return Father != NULL;
00266   }
00267 
00268   // Do not let people play around with fathers.
00269   const ETNode *getFather() const {
00270     return Father;
00271   }
00272 
00273   template <typename T>
00274   T *getData() const {
00275     return static_cast<T*>(data);
00276   }
00277   
00278   unsigned getDFSNumIn() const {
00279     return DFSNumIn;
00280   }
00281   
00282   unsigned getDFSNumOut() const {
00283     return DFSNumOut;
00284   }
00285 
00286  private:
00287   // Data represented by the node
00288   void *data;
00289 
00290   // DFS Numbers
00291   int DFSNumIn, DFSNumOut;
00292 
00293   // Father
00294   ETNode *Father;
00295 
00296   // Brothers.  Node, this ends up being a circularly linked list.
00297   // Thus, if you want to get all the brothers, you need to stop when
00298   // you hit node == this again.
00299   ETNode *Left, *Right;
00300 
00301   // First Son
00302   ETNode *Son;
00303 
00304   // Rightmost occurrence for this node
00305   ETOccurrence *RightmostOcc;
00306 
00307   // Parent occurrence for this node
00308   ETOccurrence *ParentOcc;
00309 };
00310 }  // end llvm namespace
00311 
00312 #endif