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