include/llvm/Analysis/ET-Forest.h

   1 //===- llvm/Analysis/ET-Forest.h - ET-Forest implementation -----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   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.
   8 //
   9 //===----------------------------------------------------------------------===//
  10 //
  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.
  15 //
  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.
  19 //
  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
  25 // logarithmic time.
  26 //
  27 //===----------------------------------------------------------------------===//
  28
  29 #ifndef LLVM_ANALYSIS_ETFOREST_H
  30 #define LLVM_ANALYSIS_ETFOREST_H
  31
  32 #include <cassert>
  33 #include <cstdlib>
  34
  35 namespace llvm {
  36 class ETNode;
  37
  38 /// ETOccurrence - An occurrence for a node in the et tree
  39 ///
  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
  42 /// tree.
  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.
  46 ///
  47 class ETOccurrence {
  48 public:
  49   ETOccurrence(ETNode *n): OccFor(n), Parent(NULL), Left(NULL), Right(NULL),
  50     Depth(0), Min(0), MinOccurrence(this) {};
  51
  52   void setParent(ETOccurrence *n) {
  53     assert(n != this && "Trying to set parent to ourselves");
  54     Parent = n;
  55   }
  56
  57   // Add D to our current depth
  58   void setDepthAdd(int d) {
  59     Min += d;
  60     Depth += d;
  61   }
  62
  63   // Reset our depth to D
  64   void setDepth(int d) {
  65     Min += d - Depth;
  66     Depth = d;
  67   }
  68
  69   // Set Left to N
  70   void setLeft(ETOccurrence *n) {
  71     assert(n != this && "Trying to set our left to ourselves");
  72     Left = n;
  73     if (n)
  74       n->setParent(this);
  75   }
  76
  77   // Set Right to N
  78   void setRight(ETOccurrence *n) {
  79     assert(n != this && "Trying to set our right to ourselves");
  80     Right = n;
  81     if (n)
  82       n->setParent(this);
  83   }
  84
  85   // Splay us to the root of the tree
  86   void Splay(void);
  87
  88   // Recompute the minimum occurrence for this occurrence.
  89   void recomputeMin(void) {
  90     ETOccurrence *themin = Left;
  91
  92     // The min may be our Right, too.
  93     if (!themin || (Right && themin->Min > Right->Min))
  94       themin = Right;
  95
  96     if (themin && themin->Min < 0) {
  97       Min = themin->Min + Depth;
  98       MinOccurrence = themin->MinOccurrence;
  99     } else {
 100       Min = Depth;
 101       MinOccurrence = this;
 102     }
 103   }
 104  private:
 105   friend class ETNode;
 106
 107     // Node we represent
 108   ETNode *OccFor;
 109
 110   // Parent in the splay tree
 111   ETOccurrence *Parent;
 112
 113   // Left Son in the splay tree
 114   ETOccurrence *Left;
 115
 116   // Right Son in the splay tree
 117   ETOccurrence *Right;
 118
 119   // Depth of the node is the sum of the depth on the path to the
 120   // root.
 121   int Depth;
 122
 123   // Subtree occurrence's minimum depth
 124   int Min;
 125
 126   // Subtree occurrence with minimum depth
 127   ETOccurrence *MinOccurrence;
 128 };
 129
 130
 131 class ETNode {
 132 public:
 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);
 137   };
 138
 139   // This does *not* maintain the tree structure.
 140   // If you want to remove a node from the forest structure, use
 141   // removeFromForest()
 142   ~ETNode() {
 143     delete RightmostOcc;
 144     if (ParentOcc)
 145       delete ParentOcc;
 146   }
 147
 148   void removeFromForest() {
 149     // Split us away from all our sons.
 150     while (Son)
 151       Son->Split();
 152
 153     // And then split us away from our father.
 154     if (Father)
 155       Father->Split();
 156   }
 157
 158   // Split us away from our parents and children, so that we can be
 159   // reparented. NB: setFather WILL NOT DO WHAT YOU WANT IF YOU DO NOT
 160   // SPLIT US FIRST.
 161   void Split();
 162
 163   // Set our parent node to the passed in node
 164   void setFather(ETNode *);
 165
 166   // Nearest Common Ancestor of two et nodes.
 167   ETNode *NCA(ETNode *);
 168
 169   // Return true if we are below the passed in node in the forest.
 170   bool Below(ETNode *);
 171   /*
 172    Given a dominator tree, we can determine whether one thing
 173    dominates another in constant time by using two DFS numbers:
 174
 175    1. The number for when we visit a node on the way down the tree
 176    2. The number for when we visit a node on the way back up the tree
 177
 178    You can view these as bounds for the range of dfs numbers the
 179    nodes in the subtree of the dominator tree rooted at that node
 180    will contain.
 181
 182    The dominator tree is always a simple acyclic tree, so there are
 183    only three possible relations two nodes in the dominator tree have
 184    to each other:
 185
 186    1. Node A is above Node B (and thus, Node A dominates node B)
 187
 188         A
 189         |
 190         C
 191        / \
 192       B   D
 193
 194
 195    In the above case, DFS_Number_In of A will be <= DFS_Number_In of
 196    B, and DFS_Number_Out of A will be >= DFS_Number_Out of B.  This is
 197    because we must hit A in the dominator tree *before* B on the walk
 198    down, and we will hit A *after* B on the walk back up
 199
 200    2. Node A is below node B (and thus, node B dominates node B)
 201
 202         B
 203         |
 204         A
 205        / \
 206       C   D
 207
 208    In the above case, DFS_Number_In of A will be >= DFS_Number_In of
 209    B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
 210
 211    This is because we must hit A in the dominator tree *after* B on
 212    the walk down, and we will hit A *before* B on the walk back up
 213
 214    3. Node A and B are siblings (and thus, neither dominates the other)
 215
 216         C
 217         |
 218         D
 219        / \
 220       A   B
 221
 222    In the above case, DFS_Number_In of A will *always* be <=
 223    DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
 224    DFS_Number_Out of B.  This is because we will always finish the dfs
 225    walk of one of the subtrees before the other, and thus, the dfs
 226    numbers for one subtree can't intersect with the range of dfs
 227    numbers for the other subtree.  If you swap A and B's position in
 228    the dominator tree, the comparison changes direction, but the point
 229    is that both comparisons will always go the same way if there is no
 230    dominance relationship.
 231
 232    Thus, it is sufficient to write
 233
 234    A_Dominates_B(node A, node B) {
 235       return DFS_Number_In(A) <= DFS_Number_In(B) &&
 236              DFS_Number_Out(A) >= DFS_Number_Out(B);
 237    }
 238
 239    A_Dominated_by_B(node A, node B) {
 240      return DFS_Number_In(A) >= DFS_Number_In(A) &&
 241             DFS_Number_Out(A) <= DFS_Number_Out(B);
 242    }
 243   */
 244   bool DominatedBy(ETNode *other) const {
 245     return this->DFSNumIn >= other->DFSNumIn &&
 246            this->DFSNumOut <= other->DFSNumOut;
 247   }
 248
 249   // This method is slower, but doesn't require the DFS numbers to
 250   // be up to date.
 251   bool DominatedBySlow(ETNode *other) {
 252     return this->Below(other);
 253   }
 254
 255   void assignDFSNumber (int);
 256
 257   bool hasFather() const {
 258     return Father != NULL;
 259   }
 260
 261   // Do not let people play around with fathers.
 262   const ETNode *getFather() const {
 263     return Father;
 264   }
 265
 266   template <typename T>
 267   T *getData() const {
 268     return static_cast<T*>(data);
 269   }
 270
 271   unsigned getDFSNumIn() const {
 272     return DFSNumIn;
 273   }
 274
 275   unsigned getDFSNumOut() const {
 276     return DFSNumOut;
 277   }
 278
 279  private:
 280   // Data represented by the node
 281   void *data;
 282
 283   // DFS Numbers
 284   int DFSNumIn, DFSNumOut;
 285
 286   // Father
 287   ETNode *Father;
 288
 289   // Brothers.  Node, this ends up being a circularly linked list.
 290   // Thus, if you want to get all the brothers, you need to stop when
 291   // you hit node == this again.
 292   ETNode *Left, *Right;
 293
 294   // First Son
 295   ETNode *Son;
 296
 297   // Rightmost occurrence for this node
 298   ETOccurrence *RightmostOcc;
 299
 300   // Parent occurrence for this node
 301   ETOccurrence *ParentOcc;
 302 };
 303 }  // end llvm namespace
 304
 305 #endif