From 1ceda1d63ed128b34c332c81890f314ce2e5373d Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Wed, 27 Jun 2007 20:53:52 +0000 Subject: [PATCH] Remove ETForest. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37765 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/Dominators.h | 169 +-------- include/llvm/Analysis/ET-Forest.h | 312 ---------------- lib/VMCore/Dominators.cpp | 551 ----------------------------- 3 files changed, 1 insertion(+), 1031 deletions(-) delete mode 100644 include/llvm/Analysis/ET-Forest.h diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index 0b62c513fe8..9873759025c 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -9,9 +9,7 @@ // // This file defines the following classes: // 1. DominatorTree: Represent dominators as an explicit tree structure. -// 2. ETForest: Efficient data structure for dominance comparisons and -// nearest-common-ancestor queries. -// 3. DominanceFrontier: Calculate and hold the dominance frontier for a +// 2. DominanceFrontier: Calculate and hold the dominance frontier for a // function. // // These data structures are listed in increasing order of complexity. It @@ -23,7 +21,6 @@ #ifndef LLVM_ANALYSIS_DOMINATORS_H #define LLVM_ANALYSIS_DOMINATORS_H -#include "llvm/Analysis/ET-Forest.h" #include "llvm/Pass.h" #include @@ -347,170 +344,6 @@ template <> struct GraphTraits }; -//===------------------------------------- -/// ET-Forest Class - Class used to construct forwards and backwards -/// ET-Forests -/// -class ETForestBase : public DominatorBase { -public: - ETForestBase(intptr_t ID, bool isPostDom) - : DominatorBase(ID, isPostDom), Nodes(), - DFSInfoValid(false), SlowQueries(0) {} - - virtual void releaseMemory() { reset(); } - - typedef std::map ETMapType; - - // FIXME : There is no need to make this interface public. - // Fix predicate simplifier. - void updateDFSNumbers(); - - /// dominates - Return true if A dominates B. - /// - inline bool dominates(BasicBlock *A, BasicBlock *B) { - if (A == B) - return true; - - ETNode *NodeA = getNode(A); - ETNode *NodeB = getNode(B); - - if (DFSInfoValid) - return NodeB->DominatedBy(NodeA); - else { - // If we end up with too many slow queries, just update the - // DFS numbers on the theory that we are going to keep querying. - SlowQueries++; - if (SlowQueries > 32) { - updateDFSNumbers(); - return NodeB->DominatedBy(NodeA); - } - return NodeB->DominatedBySlow(NodeA); - } - } - - // dominates - Return true if A dominates B. This performs the - // special checks necessary if A and B are in the same basic block. - bool dominates(Instruction *A, Instruction *B); - - /// properlyDominates - Return true if A dominates B and A != B. - /// - bool properlyDominates(BasicBlock *A, BasicBlock *B) { - return dominates(A, B) && A != B; - } - - /// isReachableFromEntry - Return true if A is dominated by the entry - /// block of the function containing it. - const bool isReachableFromEntry(BasicBlock* A); - - /// 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(); - } - - /// Return the immediate dominator of A. - BasicBlock *getIDom(BasicBlock *A) const { - ETNode *NodeA = getNode(A); - if (!NodeA) return 0; - const ETNode *idom = NodeA->getFather(); - return idom ? idom->getData() : 0; - } - - void getETNodeChildren(BasicBlock *A, std::vector& children) const { - ETNode *NodeA = getNode(A); - if (!NodeA) return; - const ETNode* son = NodeA->getSon(); - - if (!son) return; - children.push_back(son->getData()); - - const ETNode* brother = son->getBrother(); - while (brother != son) { - children.push_back(brother->getData()); - brother = brother->getBrother(); - } - } - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired(); - } - //===--------------------------------------------------------------------===// - // 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; - void print(std::ostream *OS, const Module* M = 0) const { - if (OS) print(*OS, M); - } - virtual void dump(); -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; - unsigned int SlowQueries; - -}; - -//==------------------------------------- -/// ETForest Class - Concrete subclass of ETForestBase that is used to -/// compute a forwards ET-Forest. - -class ETForest : public ETForestBase { -public: - static char ID; // Pass identification, replacement for typeid - - ETForest() : ETForestBase((intptr_t)&ID, 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... - DominatorTree &DT = getAnalysis(); - Roots = DT.getRoots(); - calculate(DT); - return false; - } - - void calculate(const DominatorTree &DT); - // FIXME : There is no need to make getNodeForBlock public. Fix - // predicate simplifier. - ETNode *getNodeForBlock(BasicBlock *BB); -}; - //===----------------------------------------------------------------------===// /// DominanceFrontierBase - Common base class for computing forward and inverse /// dominance frontiers for a function. diff --git a/include/llvm/Analysis/ET-Forest.h b/include/llvm/Analysis/ET-Forest.h deleted file mode 100644 index 8bd5e447bca..00000000000 --- a/include/llvm/Analysis/ET-Forest.h +++ /dev/null @@ -1,312 +0,0 @@ -//===- 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 -#include - -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) { - assert(n != this && "Trying to set parent to ourselves"); - 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), DFSNumIn(-1), DFSNumOut(-1), - 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; - delete ParentOcc; - } - - 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); - - bool hasFather() const { - return Father != NULL; - } - - // Do not let people play around with fathers. - const ETNode *getFather() const { - return Father; - } - - template - T *getData() const { - return static_cast(data); - } - - unsigned getDFSNumIn() const { - return DFSNumIn; - } - - unsigned getDFSNumOut() const { - return DFSNumOut; - } - - const ETNode *getSon() const { - return Son; - } - - const ETNode *getBrother() const { - return Left; - } - - private: - // Data represented by the node - void *data; - - // DFS Numbers - int 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/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 256cf1ca44c..f8aef5dde2a 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -805,554 +805,3 @@ void DominanceFrontierBase::print(std::ostream &o, const Module* ) const { void DominanceFrontierBase::dump() { print (llvm::cerr); } - - -//===----------------------------------------------------------------------===// -// 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; right->Left; right = right->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; - } - - delete ParentOcc; - 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; -} - -void ETNode::assignDFSNumber(int num) { - std::vector workStack; - std::set visitedNodes; - - workStack.push_back(this); - visitedNodes.insert(this); - this->DFSNumIn = num++; - - while (!workStack.empty()) { - ETNode *Node = workStack.back(); - - // If this is leaf node then set DFSNumOut and pop the stack - if (!Node->Son) { - Node->DFSNumOut = num++; - workStack.pop_back(); - continue; - } - - ETNode *son = Node->Son; - - // Visit Node->Son first - if (visitedNodes.count(son) == 0) { - son->DFSNumIn = num++; - workStack.push_back(son); - visitedNodes.insert(son); - continue; - } - - bool visitChild = false; - // Visit remaining children - for (ETNode *s = son->Right; s != son && !visitChild; s = s->Right) { - if (visitedNodes.count(s) == 0) { - visitChild = true; - s->DFSNumIn = num++; - workStack.push_back(s); - visitedNodes.insert(s); - } - } - - if (!visitChild) { - // If we reach here means all children are visited - Node->DFSNumOut = num++; - workStack.pop_back(); - } - } -} - -//===----------------------------------------------------------------------===// -// ETForest implementation -//===----------------------------------------------------------------------===// - -char ETForest::ID = 0; -static RegisterPass -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(); -} - -void ETForestBase::updateDFSNumbers() -{ - int dfsnum = 0; - // Iterate over all nodes in depth first order. - for (unsigned i = 0, e = Roots.size(); i != e; ++i) - for (df_iterator I = df_begin(Roots[i]), - E = df_end(Roots[i]); I != E; ++I) { - BasicBlock *BB = *I; - ETNode *ETN = getNode(BB); - if (ETN && !ETN->hasFather()) - ETN->assignDFSNumber(dfsnum); - } - SlowQueries = 0; - DFSInfoValid = true; -} - -// dominates - Return true if A dominates B. THis performs the -// special checks necessary if A and B are in the same basic block. -bool ETForestBase::dominates(Instruction *A, Instruction *B) { - BasicBlock *BBA = A->getParent(), *BBB = B->getParent(); - if (BBA != BBB) return dominates(BBA, BBB); - - // It is not possible to determine dominance between two PHI nodes - // based on their ordering. - if (isa(A) && isa(B)) - return false; - - // Loop through the basic block until we find A or B. - BasicBlock::iterator I = BBA->begin(); - for (; &*I != A && &*I != B; ++I) /*empty*/; - - if(!IsPostDominators) { - // A dominates B if it is found first in the basic block. - return &*I == A; - } else { - // A post-dominates B if B is found first in the basic block. - return &*I == B; - } -} - -/// isReachableFromEntry - Return true if A is dominated by the entry -/// block of the function containing it. -const bool ETForestBase::isReachableFromEntry(BasicBlock* A) { - return dominates(&A->getParent()->getEntryBlock(), A); -} - -// FIXME : There is no need to make getNodeForBlock public. Fix -// predicate simplifier. -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. - DomTreeNode *node= getAnalysis().getNode(BB); - - // If we are unreachable, we may not have an immediate dominator. - if (!node || !node->getIDom()) - return BBNode = new ETNode(BB); - else { - ETNode *IDomNode = getNodeForBlock(node->getIDom()->getBlock()); - - // 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 DominatorTree &DT) { - 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) { - DomTreeNode* node = DT.getNode(I); - if (node && node->getIDom()) { // Reachable block. - BasicBlock* ImmDom = node->getIDom()->getBlock(); - 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); - } - } - } - - // Make sure we've got nodes around for every block - for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { - ETNode *&BBNode = Nodes[I]; - if (!BBNode) - BBNode = new ETNode(I); - } - - updateDFSNumbers (); -} - -//===----------------------------------------------------------------------===// -// 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() == 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"; -} - -void ETForestBase::dump() { - print (llvm::cerr); -} -- 2.34.1