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   }
 145
 146   void removeFromForest() {
 147     // Split us away from all our sons.
 148     while (Son)
 149       Son->Split();
 150
 151     // And then split us away from our father.
 152     if (Father)
 153       Father->Split();
 154   }
 155
 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
 158   // SPLIT US FIRST.
 159   void Split();
 160
 161   // Set our parent node to the passed in node
 162   void setFather(ETNode *);
 163
 164   // Nearest Common Ancestor of two et nodes.
 165   ETNode *NCA(ETNode *);
 166
 167   // Return true if we are below the passed in node in the forest.
 168   bool Below(ETNode *);
 169   /*
 170    Given a dominator tree, we can determine whether one thing
 171    dominates another in constant time by using two DFS numbers:
 172
 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
 175
 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
 178    will contain.
 179
 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
 182    to each other:
 183
 184    1. Node A is above Node B (and thus, Node A dominates node B)
 185
 186         A
 187         |
 188         C
 189        / \
 190       B   D
 191
 192
 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
 197
 198    2. Node A is below node B (and thus, node B dominates node B)
 199
 200         B
 201         |
 202         A
 203        / \
 204       C   D
 205
 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.
 208
 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
 211
 212    3. Node A and B are siblings (and thus, neither dominates the other)
 213
 214         C
 215         |
 216         D
 217        / \
 218       A   B
 219
 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.
 229
 230    Thus, it is sufficient to write
 231
 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);
 235    }
 236
 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);
 240    }
 241   */
 242   bool DominatedBy(ETNode *other) const {
 243     return this->DFSNumIn >= other->DFSNumIn &&
 244            this->DFSNumOut <= other->DFSNumOut;
 245   }
 246
 247   // This method is slower, but doesn't require the DFS numbers to
 248   // be up to date.
 249   bool DominatedBySlow(ETNode *other) {
 250     return this->Below(other);
 251   }
 252
 253   void assignDFSNumber (int);
 254
 255   bool hasFather() const {
 256     return Father != NULL;
 257   }
 258
 259   // Do not let people play around with fathers.
 260   const ETNode *getFather() const {
 261     return Father;
 262   }
 263
 264   template <typename T>
 265   T *getData() const {
 266     return static_cast<T*>(data);
 267   }
 268
 269   unsigned getDFSNumIn() const {
 270     return DFSNumIn;
 271   }
 272
 273   unsigned getDFSNumOut() const {
 274     return DFSNumOut;
 275   }
 276
 277  private:
 278   // Data represented by the node
 279   void *data;
 280
 281   // DFS Numbers
 282   int DFSNumIn, DFSNumOut;
 283
 284   // Father
 285   ETNode *Father;
 286
 287   // Brothers.  Node, this ends up being a circularly linked list.
 288   // Thus, if you want to get all the brothers, you need to stop when
 289   // you hit node == this again.
 290   ETNode *Left, *Right;
 291
 292   // First Son
 293   ETNode *Son;
 294
 295   // Rightmost occurrence for this node
 296   ETOccurrence *RightmostOcc;
 297
 298   // Parent occurrence for this node
 299   ETOccurrence *ParentOcc;
 300 };
 301 }  // end llvm namespace
 302
 303 #endif