1 //===- llvm/Analysis/ET-Forest.h - ET-Forest implementation -----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was written by Daniel Berlin from code written by Pavel Nejedy, and
6 // is distributed under the University of Illinois Open Source License. See
7 // LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 // This file defines the following classes:
12 // 1. ETNode: A node in the ET forest.
13 // 2. ETOccurrence: An occurrence of the node in the splay tree
14 // storing the DFS path information.
16 // The ET-forest structure is described in:
17 // D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
18 // J. G'omput. System Sci., 26(3):362 381, 1983.
20 // Basically, the ET-Forest is storing the dominator tree (ETNode),
21 // and a splay tree containing the depth first path information for
22 // those nodes (ETOccurrence). This enables us to answer queries
23 // about domination (DominatedBySlow), and ancestry (NCA) in
24 // logarithmic time, and perform updates to the information in
27 //===----------------------------------------------------------------------===//
29 #ifndef LLVM_ANALYSIS_ETFOREST_H
30 #define LLVM_ANALYSIS_ETFOREST_H
38 /// ETOccurrence - An occurrence for a node in the et tree
40 /// The et occurrence tree is really storing the sequences you get from
41 /// doing a DFS over the ETNode's. It is stored as a modified splay
43 /// ET occurrences can occur at multiple places in the ordering depending
44 /// on how many ET nodes have it as their father. To handle
45 /// this, they are separate from the nodes.
49 ETOccurrence(ETNode *n): OccFor(n), Parent(NULL), Left(NULL), Right(NULL),
50 Depth(0), Min(0), MinOccurrence(this) {};
52 void setParent(ETOccurrence *n) {
53 assert(n != this && "Trying to set parent to ourselves");
57 // Add D to our current depth
58 void setDepthAdd(int d) {
63 // Reset our depth to D
64 void setDepth(int d) {
70 void setLeft(ETOccurrence *n) {
71 assert(n != this && "Trying to set our left to ourselves");
78 void setRight(ETOccurrence *n) {
79 assert(n != this && "Trying to set our right to ourselves");
85 // Splay us to the root of the tree
88 // Recompute the minimum occurrence for this occurrence.
89 void recomputeMin(void) {
90 ETOccurrence *themin = Left;
92 // The min may be our Right, too.
93 if (!themin || (Right && themin->Min > Right->Min))
96 if (themin && themin->Min < 0) {
97 Min = themin->Min + Depth;
98 MinOccurrence = themin->MinOccurrence;
101 MinOccurrence = this;
110 // Parent in the splay tree
111 ETOccurrence *Parent;
113 // Left Son in the splay tree
116 // Right Son in the splay tree
119 // Depth of the node is the sum of the depth on the path to the
123 // Subtree occurrence's minimum depth
126 // Subtree occurrence with minimum depth
127 ETOccurrence *MinOccurrence;
133 ETNode(void *d) : data(d), DFSNumIn(-1), DFSNumOut(-1),
134 Father(NULL), Left(NULL),
135 Right(NULL), Son(NULL), ParentOcc(NULL) {
136 RightmostOcc = new ETOccurrence(this);
139 // This does *not* maintain the tree structure.
140 // If you want to remove a node from the forest structure, use
141 // removeFromForest()
146 void removeFromForest() {
147 // Split us away from all our sons.
151 // And then split us away from our father.
156 // Split us away from our parents and children, so that we can be
157 // reparented. NB: setFather WILL NOT DO WHAT YOU WANT IF YOU DO NOT
161 // Set our parent node to the passed in node
162 void setFather(ETNode *);
164 // Nearest Common Ancestor of two et nodes.
165 ETNode *NCA(ETNode *);
167 // Return true if we are below the passed in node in the forest.
168 bool Below(ETNode *);
170 Given a dominator tree, we can determine whether one thing
171 dominates another in constant time by using two DFS numbers:
173 1. The number for when we visit a node on the way down the tree
174 2. The number for when we visit a node on the way back up the tree
176 You can view these as bounds for the range of dfs numbers the
177 nodes in the subtree of the dominator tree rooted at that node
180 The dominator tree is always a simple acyclic tree, so there are
181 only three possible relations two nodes in the dominator tree have
184 1. Node A is above Node B (and thus, Node A dominates node B)
193 In the above case, DFS_Number_In of A will be <= DFS_Number_In of
194 B, and DFS_Number_Out of A will be >= DFS_Number_Out of B. This is
195 because we must hit A in the dominator tree *before* B on the walk
196 down, and we will hit A *after* B on the walk back up
198 2. Node A is below node B (and thus, node B dominates node B)
206 In the above case, DFS_Number_In of A will be >= DFS_Number_In of
207 B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
209 This is because we must hit A in the dominator tree *after* B on
210 the walk down, and we will hit A *before* B on the walk back up
212 3. Node A and B are siblings (and thus, neither dominates the other)
220 In the above case, DFS_Number_In of A will *always* be <=
221 DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
222 DFS_Number_Out of B. This is because we will always finish the dfs
223 walk of one of the subtrees before the other, and thus, the dfs
224 numbers for one subtree can't intersect with the range of dfs
225 numbers for the other subtree. If you swap A and B's position in
226 the dominator tree, the comparison changes direction, but the point
227 is that both comparisons will always go the same way if there is no
228 dominance relationship.
230 Thus, it is sufficient to write
232 A_Dominates_B(node A, node B) {
233 return DFS_Number_In(A) <= DFS_Number_In(B) &&
234 DFS_Number_Out(A) >= DFS_Number_Out(B);
237 A_Dominated_by_B(node A, node B) {
238 return DFS_Number_In(A) >= DFS_Number_In(A) &&
239 DFS_Number_Out(A) <= DFS_Number_Out(B);
242 bool DominatedBy(ETNode *other) const {
243 return this->DFSNumIn >= other->DFSNumIn &&
244 this->DFSNumOut <= other->DFSNumOut;
247 // This method is slower, but doesn't require the DFS numbers to
249 bool DominatedBySlow(ETNode *other) {
250 return this->Below(other);
253 void assignDFSNumber(int &num) {
257 Son->assignDFSNumber(num);
258 for (ETNode *son = Son->Right; son != Son; son = son->Right)
259 son->assignDFSNumber(num);
264 bool hasFather() const {
265 return Father != NULL;
268 // Do not let people play around with fathers.
269 const ETNode *getFather() const {
273 template <typename T>
275 return static_cast<T*>(data);
278 unsigned getDFSNumIn() const {
282 unsigned getDFSNumOut() const {
287 // Data represented by the node
291 int DFSNumIn, DFSNumOut;
296 // Brothers. Node, this ends up being a circularly linked list.
297 // Thus, if you want to get all the brothers, you need to stop when
298 // you hit node == this again.
299 ETNode *Left, *Right;
304 // Rightmost occurrence for this node
305 ETOccurrence *RightmostOcc;
307 // Parent occurrence for this node
308 ETOccurrence *ParentOcc;
310 } // end llvm namespace