X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FDominators.h;h=57cad9987138e104c37b650ddc39478c250dd3b3;hb=ef6ba18a4c6ecddb12ec50668021776a6b73a71c;hp=b03c020704dbcb378596329e06b88b550ce12985;hpb=79b48b8bc07170656e7e2d7500f7fcbf69ccc923;p=oota-llvm.git diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index b03c020704d..57cad998713 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 @@ -56,19 +53,63 @@ public: bool isPostDominator() const { return IsPostDominators; } }; + +//===----------------------------------------------------------------------===// +// DomTreeNode - Dominator Tree Node +class DominatorTreeBase; +class PostDominatorTree; +class DomTreeNode { + BasicBlock *TheBB; + DomTreeNode *IDom; + std::vector Children; + int DFSNumIn, DFSNumOut; + + friend class DominatorTreeBase; + friend class PostDominatorTree; +public: + typedef std::vector::iterator iterator; + typedef std::vector::const_iterator const_iterator; + + iterator begin() { return Children.begin(); } + iterator end() { return Children.end(); } + const_iterator begin() const { return Children.begin(); } + const_iterator end() const { return Children.end(); } + + inline BasicBlock *getBlock() const { return TheBB; } + inline DomTreeNode *getIDom() const { return IDom; } + inline const std::vector &getChildren() const { return Children; } + + inline DomTreeNode(BasicBlock *BB, DomTreeNode *iDom) + : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { } + inline DomTreeNode *addChild(DomTreeNode *C) { Children.push_back(C); return C; } + void setIDom(DomTreeNode *NewIDom); + +private: + // Return true if this node is dominated by other. Use this only if DFS info is valid. + bool DominatedBy(const DomTreeNode *other) const { + return this->DFSNumIn >= other->DFSNumIn && + this->DFSNumOut <= other->DFSNumOut; + } + + /// assignDFSNumber - Assign In and Out numbers while walking dominator tree + /// in dfs order. + void assignDFSNumber(int num); +}; + //===----------------------------------------------------------------------===// /// DominatorTree - Calculate the immediate dominator tree for a function. /// class DominatorTreeBase : public DominatorBase { -public: - class Node; + protected: - std::map Nodes; void reset(); - typedef std::map NodeMapType; - - Node *RootNode; + typedef std::map DomTreeNodeMapType; + DomTreeNodeMapType DomTreeNodes; + DomTreeNode *RootNode; + bool DFSInfoValid; + unsigned int SlowQueries; + // Information record used during immediate dominators computation. struct InfoRec { unsigned Semi; unsigned Size; @@ -87,56 +128,11 @@ protected: // Info - Collection of information used during the computation of idoms. std::map Info; -public: - class Node { - friend class DominatorTree; - friend struct PostDominatorTree; - friend class DominatorTreeBase; - BasicBlock *TheBB; - Node *IDom; - std::vector Children; - public: - typedef std::vector::iterator iterator; - typedef std::vector::const_iterator const_iterator; - - iterator begin() { return Children.begin(); } - iterator end() { return Children.end(); } - const_iterator begin() const { return Children.begin(); } - const_iterator end() const { return Children.end(); } - - inline BasicBlock *getBlock() const { return TheBB; } - inline Node *getIDom() const { return IDom; } - inline const std::vector &getChildren() const { return Children; } - - /// properlyDominates - Returns true iff this dominates N and this != N. - /// Note that this is not a constant time operation! - /// - bool properlyDominates(const Node *N) const { - const Node *IDom; - if (this == 0 || N == 0) return false; - while ((IDom = N->getIDom()) != 0 && IDom != this) - N = IDom; // Walk up the tree - return IDom != 0; - } - - /// dominates - Returns true iff this dominates N. Note that this is not a - /// constant time operation! - /// - inline bool dominates(const Node *N) const { - if (N == this) return true; // A node trivially dominates itself. - return properlyDominates(N); - } - - private: - inline Node(BasicBlock *BB, Node *iDom) : TheBB(BB), IDom(iDom) {} - inline Node *addChild(Node *C) { Children.push_back(C); return C; } - - void setIDom(Node *NewIDom); - }; + void updateDFSNumbers(); -public: + public: DominatorTreeBase(intptr_t ID, bool isPostDom) - : DominatorBase(ID, isPostDom) {} + : DominatorBase(ID, isPostDom), DFSInfoValid(false), SlowQueries(0) {} ~DominatorTreeBase() { reset(); } virtual void releaseMemory() { reset(); } @@ -144,15 +140,25 @@ public: /// getNode - return the (Post)DominatorTree node for the specified basic /// block. This is the same as using operator[] on this class. /// - inline Node *getNode(BasicBlock *BB) const { - NodeMapType::const_iterator i = Nodes.find(BB); - return (i != Nodes.end()) ? i->second : 0; + inline DomTreeNode *getNode(BasicBlock *BB) const { + DomTreeNodeMapType::const_iterator i = DomTreeNodes.find(BB); + return (i != DomTreeNodes.end()) ? i->second : 0; } - inline Node *operator[](BasicBlock *BB) const { + inline DomTreeNode *operator[](BasicBlock *BB) const { return getNode(BB); } + /// getIDomBlock - return basic block BB's immediate dominator basic block. + /// + BasicBlock *getIDomBlock(BasicBlock *BB) { + DomTreeNode *N = getNode(BB); + assert (N && "Missing dominator tree node"); + DomTreeNode *I = N->getIDom(); + assert (N && "Missing immediate dominator"); + return I->getBlock(); + } + /// getRootNode - This returns the entry node for the CFG of the function. If /// this tree represents the post-dominance relations for a function, however, /// this root may be a node with the block == NULL. This is the case when @@ -160,37 +166,109 @@ public: /// post-dominance information must be capable of dealing with this /// possibility. /// - Node *getRootNode() { return RootNode; } - const Node *getRootNode() const { return RootNode; } + DomTreeNode *getRootNode() { return RootNode; } + const DomTreeNode *getRootNode() const { return RootNode; } + + /// properlyDominates - Returns true iff this dominates N and this != N. + /// Note that this is not a constant time operation! + /// + bool properlyDominates(const DomTreeNode *A, DomTreeNode *B) const { + if (A == 0 || B == 0) return false; + return dominatedBySlowTreeWalk(A, B); + } + + inline bool properlyDominates(BasicBlock *A, BasicBlock *B) { + return properlyDominates(getNode(A), getNode(B)); + } + + bool dominatedBySlowTreeWalk(const DomTreeNode *A, + const DomTreeNode *B) const { + const DomTreeNode *IDom; + if (A == 0 || B == 0) return false; + while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B) + B = IDom; // Walk up the tree + return IDom != 0; + } + + + /// isReachableFromEntry - Return true if A is dominated by the entry + /// block of the function containing it. + const bool isReachableFromEntry(BasicBlock* A); + + /// dominates - Returns true iff A dominates B. Note that this is not a + /// constant time operation! + /// + inline bool dominates(const DomTreeNode *A, DomTreeNode *B) { + if (B == A) + return true; // A node trivially dominates itself. + + if (A == 0 || B == 0) + return false; + + if (DFSInfoValid) + return B->DominatedBy(A); + + // 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 B->DominatedBy(A); + } + + return dominatedBySlowTreeWalk(A, B); + } + + inline bool dominates(BasicBlock *A, BasicBlock *B) { + if (A == B) + return true; + + return dominates(getNode(A), getNode(B)); + } + + /// findNearestCommonDominator - Find nearest common dominator basic block + /// for basic block A and B. If there is no such block then return NULL. + BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B); + + // 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); //===--------------------------------------------------------------------===// // API to update (Post)DominatorTree information based on modifications to // the CFG... - /// createNewNode - Add a new node to the dominator tree information. This - /// creates a new node as a child of IDomNode, linking it into the children - /// list of the immediate dominator. - /// - Node *createNewNode(BasicBlock *BB, Node *IDomNode) { + /// addNewBlock - Add a new node to the dominator tree information. This + /// creates a new node as a child of DomBB dominator node,linking it into + /// the children list of the immediate dominator. + DomTreeNode *addNewBlock(BasicBlock *BB, BasicBlock *DomBB) { assert(getNode(BB) == 0 && "Block already in dominator tree!"); + DomTreeNode *IDomNode = getNode(DomBB); assert(IDomNode && "Not immediate dominator specified for block!"); - return Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode)); + DFSInfoValid = false; + return DomTreeNodes[BB] = + IDomNode->addChild(new DomTreeNode(BB, IDomNode)); } /// changeImmediateDominator - This method is used to update the dominator /// tree information when a node's immediate dominator changes. /// - void changeImmediateDominator(Node *N, Node *NewIDom) { + void changeImmediateDominator(DomTreeNode *N, DomTreeNode *NewIDom) { assert(N && NewIDom && "Cannot change null node pointers!"); + DFSInfoValid = false; N->setIDom(NewIDom); } + void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB) { + changeImmediateDominator(getNode(BB), getNode(NewBB)); + } + /// removeNode - Removes a node from the dominator tree. Block must not /// dominate any other blocks. Invalidates any node pointing to removed /// block. void removeNode(BasicBlock *BB) { assert(getNode(BB) && "Removing node that isn't in dominator tree."); - Nodes.erase(BB); + DomTreeNodes.erase(BB); } /// print - Convert to human readable form @@ -221,9 +299,14 @@ public: virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); } + + /// splitBlock + /// BB is split and now it has one successor. Update dominator tree to + /// reflect this change. + void splitBlock(BasicBlock *BB); private: void calculate(Function& F); - Node *getNodeForBlock(BasicBlock *BB); + DomTreeNode *getNodeForBlock(BasicBlock *BB); unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N); void Compress(BasicBlock *V); BasicBlock *Eval(BasicBlock *v); @@ -238,8 +321,8 @@ private: /// DominatorTree GraphTraits specialization so the DominatorTree can be /// iterable by generic graph iterators. /// -template <> struct GraphTraits { - typedef DominatorTree::Node NodeType; +template <> struct GraphTraits { + typedef DomTreeNode NodeType; typedef NodeType::iterator ChildIteratorType; static NodeType *getEntryNode(NodeType *N) { @@ -254,173 +337,13 @@ template <> struct GraphTraits { }; template <> struct GraphTraits - : public GraphTraits { + : public GraphTraits { static NodeType *getEntryNode(DominatorTree *DT) { return DT->getRootNode(); } }; -//===------------------------------------- -/// 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; - - 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 getChildren(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); - ETNode *getNodeForBlock(BasicBlock *BB); -}; - //===----------------------------------------------------------------------===// /// DominanceFrontierBase - Common base class for computing forward and inverse /// dominance frontiers for a function. @@ -501,9 +424,15 @@ public: AU.setPreservesAll(); AU.addRequired(); } + + /// splitBlock + /// BB is split and now it has one successor. Update dominace frontier to + /// reflect this change. + void splitBlock(BasicBlock *BB); + private: const DomSetType &calculate(const DominatorTree &DT, - const DominatorTree::Node *Node); + const DomTreeNode *Node); };