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     delete ParentOcc;
 145   }
 146
 147   void removeFromForest() {
 148     // Split us away from all our sons.
 149     while (Son)
 150       Son->Split();
 151
 152     // And then split us away from our father.
 153     if (Father)
 154       Father->Split();
 155   }
 156
 157   // Split us away from our parents and children, so that we can be
 158   // reparented. NB: setFather WILL NOT DO WHAT YOU WANT IF YOU DO NOT
 159   // SPLIT US FIRST.
 160   void Split();
 161
 162   // Set our parent node to the passed in node
 163   void setFather(ETNode *);
 164
 165   // Nearest Common Ancestor of two et nodes.
 166   ETNode *NCA(ETNode *);
 167
 168   // Return true if we are below the passed in node in the forest.
 169   bool Below(ETNode *);
 170   /*
 171    Given a dominator tree, we can determine whether one thing
 172    dominates another in constant time by using two DFS numbers:
 173
 174    1. The number for when we visit a node on the way down the tree
 175    2. The number for when we visit a node on the way back up the tree
 176
 177    You can view these as bounds for the range of dfs numbers the
 178    nodes in the subtree of the dominator tree rooted at that node
 179    will contain.
 180
 181    The dominator tree is always a simple acyclic tree, so there are
 182    only three possible relations two nodes in the dominator tree have
 183    to each other:
 184
 185    1. Node A is above Node B (and thus, Node A dominates node B)
 186
 187         A
 188         |
 189         C
 190        / \
 191       B   D
 192
 193
 194    In the above case, DFS_Number_In of A will be <= DFS_Number_In of
 195    B, and DFS_Number_Out of A will be >= DFS_Number_Out of B.  This is
 196    because we must hit A in the dominator tree *before* B on the walk
 197    down, and we will hit A *after* B on the walk back up
 198
 199    2. Node A is below node B (and thus, node B dominates node B)
 200
 201         B
 202         |
 203         A
 204        / \
 205       C   D
 206
 207    In the above case, DFS_Number_In of A will be >= DFS_Number_In of
 208    B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
 209
 210    This is because we must hit A in the dominator tree *after* B on
 211    the walk down, and we will hit A *before* B on the walk back up
 212
 213    3. Node A and B are siblings (and thus, neither dominates the other)
 214
 215         C
 216         |
 217         D
 218        / \
 219       A   B
 220
 221    In the above case, DFS_Number_In of A will *always* be <=
 222    DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
 223    DFS_Number_Out of B.  This is because we will always finish the dfs
 224    walk of one of the subtrees before the other, and thus, the dfs
 225    numbers for one subtree can't intersect with the range of dfs
 226    numbers for the other subtree.  If you swap A and B's position in
 227    the dominator tree, the comparison changes direction, but the point
 228    is that both comparisons will always go the same way if there is no
 229    dominance relationship.
 230
 231    Thus, it is sufficient to write
 232
 233    A_Dominates_B(node A, node B) {
 234       return DFS_Number_In(A) <= DFS_Number_In(B) &&
 235              DFS_Number_Out(A) >= DFS_Number_Out(B);
 236    }
 237
 238    A_Dominated_by_B(node A, node B) {
 239      return DFS_Number_In(A) >= DFS_Number_In(A) &&
 240             DFS_Number_Out(A) <= DFS_Number_Out(B);
 241    }
 242   */
 243   bool DominatedBy(ETNode *other) const {
 244     return this->DFSNumIn >= other->DFSNumIn &&
 245            this->DFSNumOut <= other->DFSNumOut;
 246   }
 247
 248   // This method is slower, but doesn't require the DFS numbers to
 249   // be up to date.
 250   bool DominatedBySlow(ETNode *other) {
 251     return this->Below(other);
 252   }
 253
 254   void assignDFSNumber (int);
 255
 256   bool hasFather() const {
 257     return Father != NULL;
 258   }
 259
 260   // Do not let people play around with fathers.
 261   const ETNode *getFather() const {
 262     return Father;
 263   }
 264
 265   template <typename T>
 266   T *getData() const {
 267     return static_cast<T*>(data);
 268   }
 269
 270   unsigned getDFSNumIn() const {
 271     return DFSNumIn;
 272   }
 273
 274   unsigned getDFSNumOut() const {
 275     return DFSNumOut;
 276   }
 277
 278  private:
 279   // Data represented by the node
 280   void *data;
 281
 282   // DFS Numbers
 283   int DFSNumIn, DFSNumOut;
 284
 285   // Father
 286   ETNode *Father;
 287
 288   // Brothers.  Node, this ends up being a circularly linked list.
 289   // Thus, if you want to get all the brothers, you need to stop when
 290   // you hit node == this again.
 291   ETNode *Left, *Right;
 292
 293   // First Son
 294   ETNode *Son;
 295
 296   // Rightmost occurrence for this node
 297   ETOccurrence *RightmostOcc;
 298
 299   // Parent occurrence for this node
 300   ETOccurrence *ParentOcc;
 301 };
 302 }  // end llvm namespace
 303
 304 #endif