LLVM API Documentation
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