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
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 @@
//===-------------------------------------
+/// 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 @@
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 @@
};
+/// 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.
///
diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
index 56af6f6..f9f9a42 100644
--- a/lib/Analysis/PostDominators.cpp
+++ b/lib/Analysis/PostDominators.cpp
@@ -205,6 +205,69 @@
}
}
}
+//===----------------------------------------------------------------------===//
+// PostETForest Implementation
+//===----------------------------------------------------------------------===//
+
+static RegisterAnalysis<PostETForest>
+G("postetforest", "Post-ET-Forest Construction", true);
+
+ETNode *PostETForest::getNodeForBlock(BasicBlock *BB) {
+ ETNode *&BBNode = Nodes[BB];
+ if (BBNode) return BBNode;
+
+ // Haven't calculated this node yet? Get or calculate the node for the
+ // immediate dominator.
+ BasicBlock *IDom = getAnalysis<ImmediatePostDominators>()[BB];
+
+ // If we are unreachable, we may not have an immediate dominator.
+ if (!IDom)
+ return BBNode = new ETNode(BB);
+ else {
+ ETNode *IDomNode = getNodeForBlock(IDom);
+
+ // Add a new tree node for this BasicBlock, and link it as a child of
+ // IDomNode
+ BBNode = new ETNode(BB);
+ BBNode->setFather(IDomNode);
+ return BBNode;
+ }
+}
+
+void PostETForest::calculate(const ImmediatePostDominators &ID) {
+ for (unsigned i = 0, e = Roots.size(); i != e; ++i)
+ Nodes[Roots[i]] = new ETNode(Roots[i]); // Add a node for the root
+
+ // Iterate over all nodes in inverse depth first order.
+ for (unsigned i = 0, e = Roots.size(); i != e; ++i)
+ for (idf_iterator<BasicBlock*> I = idf_begin(Roots[i]),
+ E = idf_end(Roots[i]); I != E; ++I) {
+ BasicBlock *BB = *I;
+ ETNode *&BBNode = Nodes[BB];
+ if (!BBNode) {
+ ETNode *IDomNode = NULL;
+
+ if (ID.get(BB))
+ IDomNode = getNodeForBlock(ID.get(BB));
+
+ // Add a new ETNode for this BasicBlock, and set it's parent
+ // to it's immediate dominator.
+ BBNode = new ETNode(BB);
+ if (IDomNode)
+ BBNode->setFather(IDomNode);
+ }
+ }
+
+ int dfsnum = 0;
+ // Iterate over all nodes in depth first order...
+ for (unsigned i = 0, e = Roots.size(); i != e; ++i)
+ for (idf_iterator<BasicBlock*> I = idf_begin(Roots[i]),
+ E = idf_end(Roots[i]); I != E; ++I) {
+ if (!getNodeForBlock(*I)->hasFather())
+ getNodeForBlock(*I)->assignDFSNumber(dfsnum);
+ }
+ DFSInfoValid = true;
+}
//===----------------------------------------------------------------------===//
// PostDominanceFrontier Implementation
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index 0ddc370..d328c30 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -472,3 +472,446 @@
}
}
+//===----------------------------------------------------------------------===//
+// ETOccurrence Implementation
+//===----------------------------------------------------------------------===//
+
+void ETOccurrence::Splay() {
+ ETOccurrence *father;
+ ETOccurrence *grandfather;
+ int occdepth;
+ int fatherdepth;
+
+ while (Parent) {
+ occdepth = Depth;
+
+ father = Parent;
+ fatherdepth = Parent->Depth;
+ grandfather = father->Parent;
+
+ // If we have no grandparent, a single zig or zag will do.
+ if (!grandfather) {
+ setDepthAdd(fatherdepth);
+ MinOccurrence = father->MinOccurrence;
+ Min = father->Min;
+
+ // See what we have to rotate
+ if (father->Left == this) {
+ // Zig
+ father->setLeft(Right);
+ setRight(father);
+ if (father->Left)
+ father->Left->setDepthAdd(occdepth);
+ } else {
+ // Zag
+ father->setRight(Left);
+ setLeft(father);
+ if (father->Right)
+ father->Right->setDepthAdd(occdepth);
+ }
+ father->setDepth(-occdepth);
+ Parent = NULL;
+
+ father->recomputeMin();
+ return;
+ }
+
+ // If we have a grandfather, we need to do some
+ // combination of zig and zag.
+ int grandfatherdepth = grandfather->Depth;
+
+ setDepthAdd(fatherdepth + grandfatherdepth);
+ MinOccurrence = grandfather->MinOccurrence;
+ Min = grandfather->Min;
+
+ ETOccurrence *greatgrandfather = grandfather->Parent;
+
+ if (grandfather->Left == father) {
+ if (father->Left == this) {
+ // Zig zig
+ grandfather->setLeft(father->Right);
+ father->setLeft(Right);
+ setRight(father);
+ father->setRight(grandfather);
+
+ father->setDepth(-occdepth);
+
+ if (father->Left)
+ father->Left->setDepthAdd(occdepth);
+
+ grandfather->setDepth(-fatherdepth);
+ if (grandfather->Left)
+ grandfather->Left->setDepthAdd(fatherdepth);
+ } else {
+ // Zag zig
+ grandfather->setLeft(Right);
+ father->setRight(Left);
+ setLeft(father);
+ setRight(grandfather);
+
+ father->setDepth(-occdepth);
+ if (father->Right)
+ father->Right->setDepthAdd(occdepth);
+ grandfather->setDepth(-occdepth - fatherdepth);
+ if (grandfather->Left)
+ grandfather->Left->setDepthAdd(occdepth + fatherdepth);
+ }
+ } else {
+ if (father->Left == this) {
+ // Zig zag
+ grandfather->setRight(Left);
+ father->setLeft(Right);
+ setLeft(grandfather);
+ setRight(father);
+
+ father->setDepth(-occdepth);
+ if (father->Left)
+ father->Left->setDepthAdd(occdepth);
+ grandfather->setDepth(-occdepth - fatherdepth);
+ if (grandfather->Right)
+ grandfather->Right->setDepthAdd(occdepth + fatherdepth);
+ } else { // Zag Zag
+ grandfather->setRight(father->Left);
+ father->setRight(Left);
+ setLeft(father);
+ father->setLeft(grandfather);
+
+ father->setDepth(-occdepth);
+ if (father->Right)
+ father->Right->setDepthAdd(occdepth);
+ grandfather->setDepth(-fatherdepth);
+ if (grandfather->Right)
+ grandfather->Right->setDepthAdd(fatherdepth);
+ }
+ }
+
+ // Might need one more rotate depending on greatgrandfather.
+ setParent(greatgrandfather);
+ if (greatgrandfather) {
+ if (greatgrandfather->Left == grandfather)
+ greatgrandfather->Left = this;
+ else
+ greatgrandfather->Right = this;
+
+ }
+ grandfather->recomputeMin();
+ father->recomputeMin();
+ }
+}
+
+//===----------------------------------------------------------------------===//
+// ETNode implementation
+//===----------------------------------------------------------------------===//
+
+void ETNode::Split() {
+ ETOccurrence *right, *left;
+ ETOccurrence *rightmost = RightmostOcc;
+ ETOccurrence *parent;
+
+ // Update the occurrence tree first.
+ RightmostOcc->Splay();
+
+ // Find the leftmost occurrence in the rightmost subtree, then splay
+ // around it.
+ for (right = rightmost->Right; rightmost->Left; rightmost = rightmost->Left);
+
+ right->Splay();
+
+ // Start splitting
+ right->Left->Parent = NULL;
+ parent = ParentOcc;
+ parent->Splay();
+ ParentOcc = NULL;
+
+ left = parent->Left;
+ parent->Right->Parent = NULL;
+
+ right->setLeft(left);
+
+ right->recomputeMin();
+
+ rightmost->Splay();
+ rightmost->Depth = 0;
+ rightmost->Min = 0;
+
+ delete parent;
+
+ // Now update *our* tree
+
+ if (Father->Son == this)
+ Father->Son = Right;
+
+ if (Father->Son == this)
+ Father->Son = NULL;
+ else {
+ Left->Right = Right;
+ Right->Left = Left;
+ }
+ Left = Right = NULL;
+ Father = NULL;
+}
+
+void ETNode::setFather(ETNode *NewFather) {
+ ETOccurrence *rightmost;
+ ETOccurrence *leftpart;
+ ETOccurrence *NewFatherOcc;
+ ETOccurrence *temp;
+
+ // First update the path in the splay tree
+ NewFatherOcc = new ETOccurrence(NewFather);
+
+ rightmost = NewFather->RightmostOcc;
+ rightmost->Splay();
+
+ leftpart = rightmost->Left;
+
+ temp = RightmostOcc;
+ temp->Splay();
+
+ NewFatherOcc->setLeft(leftpart);
+ NewFatherOcc->setRight(temp);
+
+ temp->Depth++;
+ temp->Min++;
+ NewFatherOcc->recomputeMin();
+
+ rightmost->setLeft(NewFatherOcc);
+
+ if (NewFatherOcc->Min + rightmost->Depth < rightmost->Min) {
+ rightmost->Min = NewFatherOcc->Min + rightmost->Depth;
+ rightmost->MinOccurrence = NewFatherOcc->MinOccurrence;
+ }
+
+ ParentOcc = NewFatherOcc;
+
+ // Update *our* tree
+ ETNode *left;
+ ETNode *right;
+
+ Father = NewFather;
+ right = Father->Son;
+
+ if (right)
+ left = right->Left;
+ else
+ left = right = this;
+
+ left->Right = this;
+ right->Left = this;
+ Left = left;
+ Right = right;
+
+ Father->Son = this;
+}
+
+bool ETNode::Below(ETNode *other) {
+ ETOccurrence *up = other->RightmostOcc;
+ ETOccurrence *down = RightmostOcc;
+
+ if (this == other)
+ return true;
+
+ up->Splay();
+
+ ETOccurrence *left, *right;
+ left = up->Left;
+ right = up->Right;
+
+ if (!left)
+ return false;
+
+ left->Parent = NULL;
+
+ if (right)
+ right->Parent = NULL;
+
+ down->Splay();
+
+ if (left == down || left->Parent != NULL) {
+ if (right)
+ right->Parent = up;
+ up->setLeft(down);
+ } else {
+ left->Parent = up;
+
+ // If the two occurrences are in different trees, put things
+ // back the way they were.
+ if (right && right->Parent != NULL)
+ up->setRight(down);
+ else
+ up->setRight(right);
+ return false;
+ }
+
+ if (down->Depth <= 0)
+ return false;
+
+ return !down->Right || down->Right->Min + down->Depth >= 0;
+}
+
+ETNode *ETNode::NCA(ETNode *other) {
+ ETOccurrence *occ1 = RightmostOcc;
+ ETOccurrence *occ2 = other->RightmostOcc;
+
+ ETOccurrence *left, *right, *ret;
+ ETOccurrence *occmin;
+ int mindepth;
+
+ if (this == other)
+ return this;
+
+ occ1->Splay();
+ left = occ1->Left;
+ right = occ1->Right;
+
+ if (left)
+ left->Parent = NULL;
+
+ if (right)
+ right->Parent = NULL;
+ occ2->Splay();
+
+ if (left == occ2 || (left && left->Parent != NULL)) {
+ ret = occ2->Right;
+
+ occ1->setLeft(occ2);
+ if (right)
+ right->Parent = occ1;
+ } else {
+ ret = occ2->Left;
+
+ occ1->setRight(occ2);
+ if (left)
+ left->Parent = occ1;
+ }
+
+ if (occ2->Depth > 0) {
+ occmin = occ1;
+ mindepth = occ1->Depth;
+ } else {
+ occmin = occ2;
+ mindepth = occ2->Depth + occ1->Depth;
+ }
+
+ if (ret && ret->Min + occ1->Depth + occ2->Depth < mindepth)
+ return ret->MinOccurrence->OccFor;
+ else
+ return occmin->OccFor;
+}
+
+//===----------------------------------------------------------------------===//
+// ETForest implementation
+//===----------------------------------------------------------------------===//
+
+static RegisterAnalysis<ETForest>
+D("etforest", "ET Forest Construction", true);
+
+void ETForestBase::reset() {
+ for (ETMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
+ delete I->second;
+ Nodes.clear();
+}
+
+ETNode *ETForest::getNodeForBlock(BasicBlock *BB) {
+ ETNode *&BBNode = Nodes[BB];
+ if (BBNode) return BBNode;
+
+ // Haven't calculated this node yet? Get or calculate the node for the
+ // immediate dominator.
+ BasicBlock *IDom = getAnalysis<ImmediateDominators>()[BB];
+
+ // If we are unreachable, we may not have an immediate dominator.
+ if (!IDom)
+ return BBNode = new ETNode(BB);
+ else {
+ ETNode *IDomNode = getNodeForBlock(IDom);
+
+ // Add a new tree node for this BasicBlock, and link it as a child of
+ // IDomNode
+ BBNode = new ETNode(BB);
+ BBNode->setFather(IDomNode);
+ return BBNode;
+ }
+}
+
+void ETForest::calculate(const ImmediateDominators &ID) {
+ assert(Roots.size() == 1 && "ETForest should have 1 root block!");
+ BasicBlock *Root = Roots[0];
+ Nodes[Root] = new ETNode(Root); // Add a node for the root
+
+ Function *F = Root->getParent();
+ // Loop over all of the reachable blocks in the function...
+ for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
+ if (BasicBlock *ImmDom = ID.get(I)) { // Reachable block.
+ ETNode *&BBNode = Nodes[I];
+ if (!BBNode) { // Haven't calculated this node yet?
+ // Get or calculate the node for the immediate dominator
+ ETNode *IDomNode = getNodeForBlock(ImmDom);
+
+ // Add a new ETNode for this BasicBlock, and set it's parent
+ // to it's immediate dominator.
+ BBNode = new ETNode(I);
+ BBNode->setFather(IDomNode);
+ }
+ }
+
+ int dfsnum = 0;
+ for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
+ if (!getNodeForBlock(I)->hasFather())
+ getNodeForBlock(I)->assignDFSNumber(dfsnum);
+ }
+ DFSInfoValid = true;
+}
+
+//===----------------------------------------------------------------------===//
+// ETForestBase Implementation
+//===----------------------------------------------------------------------===//
+
+void ETForestBase::addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
+ ETNode *&BBNode = Nodes[BB];
+ assert(!BBNode && "BasicBlock already in ET-Forest");
+
+ BBNode = new ETNode(BB);
+ BBNode->setFather(getNode(IDom));
+ DFSInfoValid = false;
+}
+
+void ETForestBase::setImmediateDominator(BasicBlock *BB, BasicBlock *newIDom) {
+ assert(getNode(BB) && "BasicBlock not in ET-Forest");
+ assert(getNode(newIDom) && "IDom not in ET-Forest");
+
+ ETNode *Node = getNode(BB);
+ if (Node->hasFather()) {
+ if (Node->getFather()->getData<BasicBlock>() == newIDom)
+ return;
+ Node->Split();
+ }
+ Node->setFather(getNode(newIDom));
+ DFSInfoValid= false;
+}
+
+void ETForestBase::print(std::ostream &o, const Module *) const {
+ o << "=============================--------------------------------\n";
+ o << "ET Forest:\n";
+ o << "DFS Info ";
+ if (DFSInfoValid)
+ o << "is";
+ else
+ o << "is not";
+ o << " up to date\n";
+
+ Function *F = getRoots()[0]->getParent();
+ for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
+ o << " DFS Numbers For Basic Block:";
+ WriteAsOperand(o, I, false);
+ o << " are:";
+ if (ETNode *EN = getNode(I)) {
+ o << "In: " << EN->getDFSNumIn();
+ o << " Out: " << EN->getDFSNumOut() << "\n";
+ } else {
+ o << "No associated ETNode";
+ }
+ o << "\n";
+ }
+ o << "\n";
+}
