Initial implementation of the ET-Forest data structure for dominators and

post-dominators.  This code was written/adapted by Daniel Berlin!


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@25144 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 447 insertions, 1 deletions

diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index f0d9a8e..947b223 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -13,7 +13,9 @@
 //  2. DominatorSet: Calculates the [reverse] dominator set for a function
 //  3. DominatorTree: Represent the ImmediateDominator as an explicit tree
 //     structure.
-//  4. DominanceFrontier: Calculate and hold the dominance frontier for a
+//  4. ETForest: Efficient data structure for dominance comparisons and 
+//     nearest-common-ancestor queries.
+//  5. DominanceFrontier: Calculate and hold the dominance frontier for a
 //     function.
 //
 //  These data structures are listed in increasing order of complexity.  It
@@ -25,6 +27,7 @@
 #ifndef LLVM_ANALYSIS_DOMINATORS_H
 #define LLVM_ANALYSIS_DOMINATORS_H
 
+#include "llvm/Analysis/ET-Forest.h"
 #include "llvm/Pass.h"
 #include <set>
 
@@ -389,6 +392,116 @@ public:
 
 
 //===-------------------------------------
+/// ET-Forest Class - Class used to construct forwards and backwards 
+/// ET-Forests
+///
+struct ETForestBase : public DominatorBase {
+  ETForestBase(bool isPostDom) : DominatorBase(isPostDom), Nodes(), 
+                                 DFSInfoValid(false) {}
+  
+  virtual void releaseMemory() { reset(); }
+
+  typedef std::map<BasicBlock*, ETNode*> ETMapType;
+
+
+  /// dominates - Return true if A dominates B.
+  ///
+  inline bool dominates(BasicBlock *A, BasicBlock *B) const {
+    if (A == B)
+      return true;
+    
+    ETNode *NodeA = getNode(A);
+    ETNode *NodeB = getNode(B);
+    
+    if (DFSInfoValid)
+      return NodeB->DominatedBy(NodeA);
+    else
+      return NodeB->DominatedBySlow(NodeA);
+  }
+
+  /// properlyDominates - Return true if A dominates B and A != B.
+  ///
+  bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
+    return dominates(A, B) && A != B;
+  }
+
+  /// Return the nearest common dominator of A and B.
+  BasicBlock *nearestCommonDominator(BasicBlock *A, BasicBlock *B) const  {
+    ETNode *NodeA = getNode(A);
+    ETNode *NodeB = getNode(B);
+    
+    ETNode *Common = NodeA->NCA(NodeB);
+    if (!Common)
+      return NULL;
+    return Common->getData<BasicBlock>();
+  }
+
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesAll();
+    AU.addRequired<ImmediateDominators>();
+  }
+  //===--------------------------------------------------------------------===//
+  // API to update Forest information based on modifications
+  // to the CFG...
+
+  /// addNewBlock - Add a new block to the CFG, with the specified immediate
+  /// dominator.
+  ///
+  void addNewBlock(BasicBlock *BB, BasicBlock *IDom);
+
+  /// setImmediateDominator - Update the immediate dominator information to
+  /// change the current immediate dominator for the specified block
+  /// to another block.  This method requires that BB for NewIDom
+  /// already have an ETNode, otherwise just use addNewBlock.
+  ///
+  void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom);
+  /// print - Convert to human readable form
+  ///
+  virtual void print(std::ostream &OS, const Module* = 0) const;
+protected:
+  /// getNode - return the (Post)DominatorTree node for the specified basic
+  /// block.  This is the same as using operator[] on this class.
+  ///
+  inline ETNode *getNode(BasicBlock *BB) const {
+    ETMapType::const_iterator i = Nodes.find(BB);
+    return (i != Nodes.end()) ? i->second : 0;
+  }
+
+  inline ETNode *operator[](BasicBlock *BB) const {
+    return getNode(BB);
+  }
+
+  void reset();
+  ETMapType Nodes;
+  bool DFSInfoValid;
+
+};
+
+//==-------------------------------------
+/// ETForest Class - Concrete subclass of ETForestBase that is used to
+/// compute a forwards ET-Forest.
+
+struct ETForest : public ETForestBase {
+  ETForest() : ETForestBase(false) {}
+
+  BasicBlock *getRoot() const {
+    assert(Roots.size() == 1 && "Should always have entry node!");
+    return Roots[0];
+  }
+
+  virtual bool runOnFunction(Function &F) {
+    reset();     // Reset from the last time we were run...
+    ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
+    Roots = ID.getRoots();
+    calculate(ID);
+    return false;
+  }
+
+  void calculate(const ImmediateDominators &ID);
+  ETNode *getNodeForBlock(BasicBlock *BB);
+};
+
+//===-------------------------------------
 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 /// compute a normal dominator tree.
 ///
@@ -518,6 +631,7 @@ private:
                               const DominatorTree::Node *Node);
 };
 
+
 // Make sure that any clients of this file link in Dominators.cpp
 static IncludeFile
 DOMINATORS_INCLUDE_FILE((void*)&DominatorSet::stub);
diff --git a/include/llvm/Analysis/ET-Forest.h b/include/llvm/Analysis/ET-Forest.h
new file mode 100644
index 0000000..892a0b5
--- /dev/null
+++ b/include/llvm/Analysis/ET-Forest.h
@@ -0,0 +1,309 @@
+//===- llvm/Analysis/ET-Forest.h - ET-Forest implementation -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was written by Daniel Berlin from code written by Pavel Nejedy, and
+// is distributed under the University of Illinois Open Source License. See
+// LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the following classes:
+//  1. ETNode:  A node in the ET forest.
+//  2. ETOccurrence: An occurrence of the node in the splay tree
+//  storing the DFS path information.
+//
+//  The ET-forest structure is described in:
+//    D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
+//    J.  G'omput. System Sci., 26(3):362 381, 1983.
+//
+// Basically, the ET-Forest is storing the dominator tree (ETNode),
+// and a splay tree containing the depth first path information for
+// those nodes (ETOccurrence).  This enables us to answer queries
+// about domination (DominatedBySlow), and ancestry (NCA) in
+// logarithmic time, and perform updates to the information in
+// logarithmic time.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ETFOREST_H
+#define LLVM_ANALYSIS_ETFOREST_H
+
+#include <cassert>
+
+namespace llvm {
+class ETNode;
+
+/// ETOccurrence - An occurrence for a node in the et tree
+///
+/// The et occurrence tree is really storing the sequences you get from
+/// doing a DFS over the ETNode's.  It is stored as a modified splay
+/// tree.
+/// ET occurrences can occur at multiple places in the ordering depending
+/// on how many ET nodes have it as their father.  To handle
+/// this, they are separate from the nodes.
+///
+class ETOccurrence {
+public:
+  ETOccurrence(ETNode *n): OccFor(n), Parent(NULL), Left(NULL), Right(NULL),
+    Depth(0), Min(0), MinOccurrence(this) {};
+
+  void setParent(ETOccurrence *n) {
+    Parent = n;
+  }
+
+  // Add D to our current depth
+  void setDepthAdd(int d) {
+    Min += d;
+    Depth += d;
+  }
+  
+  // Reset our depth to D
+  void setDepth(int d) {
+    Min += d - Depth;
+    Depth = d;
+  }
+
+  // Set Left to N
+  void setLeft(ETOccurrence *n) {
+    assert(n != this && "Trying to set our left to ourselves");
+    Left = n;
+    if (n)
+      n->setParent(this);
+  }
+  
+  // Set Right to N
+  void setRight(ETOccurrence *n) {
+    assert(n != this && "Trying to set our right to ourselves");
+    Right = n;
+    if (n)
+      n->setParent(this);
+  }
+  
+  // Splay us to the root of the tree
+  void Splay(void);
+
+  // Recompute the minimum occurrence for this occurrence.
+  void recomputeMin(void) {
+    ETOccurrence *themin = Left;
+    
+    // The min may be our Right, too.
+    if (!themin || (Right && themin->Min > Right->Min))
+      themin = Right;
+    
+    if (themin && themin->Min < 0) {
+      Min = themin->Min + Depth;
+      MinOccurrence = themin->MinOccurrence;
+    } else {
+      Min = Depth;
+      MinOccurrence = this;
+    }
+  }
+ private:
+  friend class ETNode;
+
+    // Node we represent
+  ETNode *OccFor;
+
+  // Parent in the splay tree
+  ETOccurrence *Parent;
+
+  // Left Son in the splay tree
+  ETOccurrence *Left;
+
+  // Right Son in the splay tree
+  ETOccurrence *Right;
+
+  // Depth of the node is the sum of the depth on the path to the
+  // root.
+  int Depth;
+
+  // Subtree occurrence's minimum depth
+  int Min;
+
+  // Subtree occurrence with minimum depth
+  ETOccurrence *MinOccurrence;
+};
+
+
+class ETNode {
+public:
+  ETNode(void *d) : data(d), Father(NULL), Left(NULL),
+                    Right(NULL), Son(NULL), ParentOcc(NULL) {   
+    RightmostOcc = new ETOccurrence(this);
+  };
+
+  // This does *not* maintain the tree structure.
+  // If you want to remove a node from the forest structure, use
+  // removeFromForest()
+  ~ETNode() {
+    delete RightmostOcc;
+  }
+
+  void removeFromForest() {
+    // Split us away from all our sons.
+    while (Son)
+      Son->Split();
+    
+    // And then split us away from our father.
+    if (Father)
+      Father->Split();
+  }
+
+  // Split us away from our parents and children, so that we can be
+  // reparented. NB: setFather WILL NOT DO WHAT YOU WANT IF YOU DO NOT
+  // SPLIT US FIRST.
+  void Split();
+
+  // Set our parent node to the passed in node
+  void setFather(ETNode *);
+  
+  // Nearest Common Ancestor of two et nodes.
+  ETNode *NCA(ETNode *);
+  
+  // Return true if we are below the passed in node in the forest.
+  bool Below(ETNode *);
+  /*
+   Given a dominator tree, we can determine whether one thing
+   dominates another in constant time by using two DFS numbers:
+  
+   1. The number for when we visit a node on the way down the tree
+   2. The number for when we visit a node on the way back up the tree
+  
+   You can view these as bounds for the range of dfs numbers the
+   nodes in the subtree of the dominator tree rooted at that node
+   will contain.
+  
+   The dominator tree is always a simple acyclic tree, so there are
+   only three possible relations two nodes in the dominator tree have
+   to each other:
+  
+   1. Node A is above Node B (and thus, Node A dominates node B)
+  
+        A
+        |
+        C
+       / \ 
+      B   D
+  
+  
+   In the above case, DFS_Number_In of A will be <= DFS_Number_In of
+   B, and DFS_Number_Out of A will be >= DFS_Number_Out of B.  This is
+   because we must hit A in the dominator tree *before* B on the walk
+   down, and we will hit A *after* B on the walk back up
+  
+   2. Node A is below node B (and thus, node B dominates node B)
+       
+        B
+        |
+        A
+       / \ 
+      C   D
+  
+   In the above case, DFS_Number_In of A will be >= DFS_Number_In of
+   B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
+  
+   This is because we must hit A in the dominator tree *after* B on
+   the walk down, and we will hit A *before* B on the walk back up
+  
+   3. Node A and B are siblings (and thus, neither dominates the other)
+  
+        C
+        |
+        D
+       / \                        
+      A   B
+  
+   In the above case, DFS_Number_In of A will *always* be <=
+   DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
+   DFS_Number_Out of B.  This is because we will always finish the dfs
+   walk of one of the subtrees before the other, and thus, the dfs
+   numbers for one subtree can't intersect with the range of dfs
+   numbers for the other subtree.  If you swap A and B's position in
+   the dominator tree, the comparison changes direction, but the point
+   is that both comparisons will always go the same way if there is no
+   dominance relationship.
+  
+   Thus, it is sufficient to write
+  
+   A_Dominates_B(node A, node B) {
+      return DFS_Number_In(A) <= DFS_Number_In(B) &&
+             DFS_Number_Out(A) >= DFS_Number_Out(B);
+   }
+  
+   A_Dominated_by_B(node A, node B) {
+     return DFS_Number_In(A) >= DFS_Number_In(A) &&
+            DFS_Number_Out(A) <= DFS_Number_Out(B);
+   }
+  */
+  bool DominatedBy(ETNode *other) const {
+    return this->DFSNumIn >= other->DFSNumIn &&
+           this->DFSNumOut <= other->DFSNumOut;
+  }
+  
+  // This method is slower, but doesn't require the DFS numbers to
+  // be up to date.
+  bool DominatedBySlow(ETNode *other) {
+    return this->Below(other);
+  }
+
+  void assignDFSNumber(int &num) {
+    DFSNumIn = num++;
+    
+    if (Son) {
+      Son->assignDFSNumber(num);
+      for (ETNode *son = Son->Right; son != Son; son = son->Right)
+        son->assignDFSNumber(num);
+    }
+    DFSNumOut = num++;
+  }
+  
+  bool hasFather() const {
+    return Father != NULL;
+  }
+
+  // Do not let people play around with fathers.
+  const ETNode *getFather() const {
+    return Father;
+  }
+
+  template <typename T>
+  T *getData() const {
+    return static_cast<T*>(data);
+  }
+  
+  unsigned getDFSNumIn() const {
+    return DFSNumIn;
+  }
+  
+  unsigned getDFSNumOut() const {
+    return DFSNumOut;
+  }
+
+ private:
+  // Data represented by the node
+  void *data;
+
+  // DFS Numbers
+  unsigned DFSNumIn, DFSNumOut;
+
+  // Father
+  ETNode *Father;
+
+  // Brothers.  Node, this ends up being a circularly linked list.
+  // Thus, if you want to get all the brothers, you need to stop when
+  // you hit node == this again.
+  ETNode *Left, *Right;
+
+  // First Son
+  ETNode *Son;
+
+  // Rightmost occurrence for this node
+  ETOccurrence *RightmostOcc;
+
+  // Parent occurrence for this node
+  ETOccurrence *ParentOcc;
+};
+}  // end llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h
index 992a0ce..754d436 100644
--- a/include/llvm/Analysis/PostDominators.h
+++ b/include/llvm/Analysis/PostDominators.h
@@ -84,6 +84,29 @@ private:
 };
 
 
+/// PostETForest Class - Concrete subclass of ETForestBase that is used to
+/// compute a forwards post-dominator ET-Forest.
+struct PostETForest : public ETForestBase {
+  PostETForest() : ETForestBase(true) {}
+
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesAll();
+    AU.addRequired<ImmediatePostDominators>();
+  }
+
+  virtual bool runOnFunction(Function &F) {
+    reset();     // Reset from the last time we were run...
+    ImmediatePostDominators &ID = getAnalysis<ImmediatePostDominators>();
+    Roots = ID.getRoots();
+    calculate(ID);
+    return false;
+  }
+
+  void calculate(const ImmediatePostDominators &ID);
+  ETNode *getNodeForBlock(BasicBlock *BB);
+};
+
+
 /// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is
 /// used to compute the a post-dominance frontier.
 ///