X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FDominators.h;h=57cad9987138e104c37b650ddc39478c250dd3b3;hb=ef6ba18a4c6ecddb12ec50668021776a6b73a71c;hp=a6df5560515ecf9eb8643cdf8b91cb049d52ea61;hpb=fd4d8975cf0e7c288b4985b1751113154c7defcc;p=oota-llvm.git diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index a6df5560515..57cad998713 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -1,18 +1,21 @@ //===- llvm/Analysis/Dominators.h - Dominator Info Calculation --*- C++ -*-===// // +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// // This file defines the following classes: -// 1. DominatorSet: Calculates the [reverse] dominator set for a function -// 2. ImmediateDominators: Calculates and holds a mapping between BasicBlocks -// and their immediate dominator. -// 3. DominatorTree: Represent the ImmediateDominator as an explicit tree -// structure. -// 4. DominanceFrontier: Calculate and hold the dominance frontier for a +// 1. DominatorTree: Represent dominators as an explicit tree structure. +// 2. DominanceFrontier: Calculate and hold the dominance frontier for a // function. // // These data structures are listed in increasing order of complexity. It -// takes longer to calculate the dominator frontier, for example, than the -// ImmediateDominator mapping. -// +// takes longer to calculate the dominator frontier, for example, than the +// DominatorTree mapping. +// //===----------------------------------------------------------------------===// #ifndef LLVM_ANALYSIS_DOMINATORS_H @@ -21,345 +24,307 @@ #include "llvm/Pass.h" #include +namespace llvm { + class Instruction; template struct GraphTraits; //===----------------------------------------------------------------------===// -// -// DominatorBase - Base class that other, more interesting dominator analyses -// inherit from. -// +/// DominatorBase - Base class that other, more interesting dominator analyses +/// inherit from. +/// class DominatorBase : public FunctionPass { protected: - BasicBlock *Root; + std::vector Roots; const bool IsPostDominators; - - inline DominatorBase(bool isPostDom) : Root(0), IsPostDominators(isPostDom) {} + inline DominatorBase(intptr_t ID, bool isPostDom) : + FunctionPass(ID), Roots(), IsPostDominators(isPostDom) {} public: - inline BasicBlock *getRoot() const { return Root; } - // Returns true if analysis based of postdoms + /// getRoots - Return the root blocks of the current CFG. This may include + /// multiple blocks if we are computing post dominators. For forward + /// dominators, this will always be a single block (the entry node). + /// + inline const std::vector &getRoots() const { return Roots; } + + /// isPostDominator - Returns true if analysis based of postdoms + /// bool isPostDominator() const { return IsPostDominators; } }; + //===----------------------------------------------------------------------===// -// -// DominatorSet - Maintain a set for every basic block in a -// function, that represents the blocks that dominate the block. If the block -// is unreachable in this function, the set will be empty. This cannot happen -// for reachable code, because every block dominates at least itself. -// -class DominatorSetBase : public DominatorBase { -public: - typedef std::set DomSetType; // Dom set for a bb - // Map of dom sets - typedef std::map DomSetMapType; -protected: - DomSetMapType Doms; +// 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: - DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {} - - virtual void releaseMemory() { Doms.clear(); } + 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); - // Accessor interface: - typedef DomSetMapType::const_iterator const_iterator; - typedef DomSetMapType::iterator iterator; - inline const_iterator begin() const { return Doms.begin(); } - inline iterator begin() { return Doms.begin(); } - inline const_iterator end() const { return Doms.end(); } - inline iterator end() { return Doms.end(); } - inline const_iterator find(BasicBlock* B) const { return Doms.find(B); } - inline iterator find(BasicBlock* B) { return Doms.find(B); } - - - /// getDominators - Return the set of basic blocks that dominate the specified - /// block. - /// - inline const DomSetType &getDominators(BasicBlock *BB) const { - const_iterator I = find(BB); - assert(I != end() && "BB not in function!"); - return I->second; +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; } - /// isReachable - Return true if the specified basicblock is reachable. If - /// the block is reachable, we have dominator set information for it. - bool isReachable(BasicBlock *BB) const { - return !getDominators(BB).empty(); - } + /// assignDFSNumber - Assign In and Out numbers while walking dominator tree + /// in dfs order. + void assignDFSNumber(int num); +}; - /// dominates - Return true if A dominates B. - /// - inline bool dominates(BasicBlock *A, BasicBlock *B) const { - return getDominators(B).count(A) != 0; - } +//===----------------------------------------------------------------------===// +/// DominatorTree - Calculate the immediate dominator tree for a function. +/// +class DominatorTreeBase : public DominatorBase { - /// properlyDominates - Return true if A dominates B and A != B. - /// - bool properlyDominates(BasicBlock *A, BasicBlock *B) const { - return dominates(A, B) && A != B; - } +protected: + void reset(); + typedef std::map DomTreeNodeMapType; + DomTreeNodeMapType DomTreeNodes; + DomTreeNode *RootNode; - /// print - Convert to human readable form - virtual void print(std::ostream &OS) const; + bool DFSInfoValid; + unsigned int SlowQueries; + // Information record used during immediate dominators computation. + struct InfoRec { + unsigned Semi; + unsigned Size; + BasicBlock *Label, *Parent, *Child, *Ancestor; - /// 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) const; + std::vector Bucket; - //===--------------------------------------------------------------------===// - // API to update (Post)DominatorSet information based on modifications to - // the CFG... + InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){} + }; - /// addBasicBlock - Call to update the dominator set with information about a - /// new block that was inserted into the function. - void addBasicBlock(BasicBlock *BB, const DomSetType &Dominators) { - assert(find(BB) == end() && "Block already in DominatorSet!"); - Doms.insert(std::make_pair(BB, Dominators)); - } + std::map IDoms; - // addDominator - If a new block is inserted into the CFG, then method may be - // called to notify the blocks it dominates that it is in their set. - // - void addDominator(BasicBlock *BB, BasicBlock *NewDominator) { - iterator I = find(BB); - assert(I != end() && "BB is not in DominatorSet!"); - I->second.insert(NewDominator); - } -}; + // Vertex - Map the DFS number to the BasicBlock* + std::vector Vertex; + // Info - Collection of information used during the computation of idoms. + std::map Info; -//===------------------------------------- -// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to -// compute a normal dominator set. -// -struct DominatorSet : public DominatorSetBase { - DominatorSet() : DominatorSetBase(false) {} + void updateDFSNumbers(); - virtual bool runOnFunction(Function &F); + public: + DominatorTreeBase(intptr_t ID, bool isPostDom) + : DominatorBase(ID, isPostDom), DFSInfoValid(false), SlowQueries(0) {} + ~DominatorTreeBase() { reset(); } - /// recalculate - This method may be called by external passes that modify the - /// CFG and then need dominator information recalculated. This method is - /// obviously really slow, so it should be avoided if at all possible. - void recalculate(); + virtual void releaseMemory() { reset(); } - // getAnalysisUsage - This simply provides a dominator set - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); + /// getNode - return the (Post)DominatorTree node for the specified basic + /// block. This is the same as using operator[] on this class. + /// + inline DomTreeNode *getNode(BasicBlock *BB) const { + DomTreeNodeMapType::const_iterator i = DomTreeNodes.find(BB); + return (i != DomTreeNodes.end()) ? i->second : 0; } -private: - void calculateDominatorsFromBlock(BasicBlock *BB); -}; - -//===----------------------------------------------------------------------===// -// -// ImmediateDominators - Calculate the immediate dominator for each node in a -// function. -// -class ImmediateDominatorsBase : public DominatorBase { -protected: - std::map IDoms; - void calcIDoms(const DominatorSetBase &DS); -public: - ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {} - - virtual void releaseMemory() { IDoms.clear(); } - - // Accessor interface: - typedef std::map IDomMapType; - typedef IDomMapType::const_iterator const_iterator; - inline const_iterator begin() const { return IDoms.begin(); } - inline const_iterator end() const { return IDoms.end(); } - inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);} - - // operator[] - Return the idom for the specified basic block. The start - // node returns null, because it does not have an immediate dominator. - // - inline BasicBlock *operator[](BasicBlock *BB) const { - return get(BB); + inline DomTreeNode *operator[](BasicBlock *BB) const { + return getNode(BB); } - // get() - Synonym for operator[]. - inline BasicBlock *get(BasicBlock *BB) const { - std::map::const_iterator I = IDoms.find(BB); - return I != IDoms.end() ? I->second : 0; + /// 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(); } - //===--------------------------------------------------------------------===// - // API to update Immediate(Post)Dominators information based on modifications - // to the CFG... - - /// addNewBlock - Add a new block to the CFG, with the specified immediate - /// dominator. + /// 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 + /// there are multiple exit nodes from a particular function. Consumers of + /// post-dominance information must be capable of dealing with this + /// possibility. /// - void addNewBlock(BasicBlock *BB, BasicBlock *IDom) { - assert(get(BB) == 0 && "BasicBlock already in idom info!"); - IDoms[BB] = IDom; - } + DomTreeNode *getRootNode() { return RootNode; } + const DomTreeNode *getRootNode() const { return RootNode; } - /// setImmediateDominator - Update the immediate dominator information to - /// change the current immediate dominator for the specified block to another - /// block. This method requires that BB already have an IDom, otherwise just - /// use addNewBlock. - void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) { - assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!"); - IDoms[BB] = NewIDom; + /// 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); } - // print - Convert to human readable form - virtual void print(std::ostream &OS) const; -}; - -//===------------------------------------- -// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase that -// is used to compute a normal immediate dominator set. -// -struct ImmediateDominators : public ImmediateDominatorsBase { - ImmediateDominators() : ImmediateDominatorsBase(false) {} - - virtual bool runOnFunction(Function &F) { - IDoms.clear(); // Reset from the last time we were run... - DominatorSet &DS = getAnalysis(); - Root = DS.getRoot(); - calcIDoms(DS); - return false; + inline bool properlyDominates(BasicBlock *A, BasicBlock *B) { + return properlyDominates(getNode(A), getNode(B)); } - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired(); + 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; } -}; -//===----------------------------------------------------------------------===// -// -// DominatorTree - Calculate the immediate dominator tree for a function. -// -class DominatorTreeBase : public DominatorBase { -protected: - class Node2; -public: - typedef Node2 Node; -protected: - std::map Nodes; - void reset(); - typedef std::map NodeMapType; -public: - class Node2 { - friend class DominatorTree; - friend class PostDominatorTree; - friend class DominatorTreeBase; - BasicBlock *TheNode; - Node2 *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 *getNode() const { return TheNode; } - inline Node2 *getIDom() const { return IDom; } - inline const std::vector &getChildren() const { return Children; } - - // dominates - Returns true iff this dominates N. Note that this is not a - // constant time operation! - inline bool dominates(const Node2 *N) const { - const Node2 *IDom; - while ((IDom = N->getIDom()) != 0 && IDom != this) - N = 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); } - private: - inline Node2(BasicBlock *node, Node *iDom) - : TheNode(node), IDom(iDom) {} - inline Node2 *addChild(Node *C) { Children.push_back(C); return C; } - - void setIDom(Node2 *NewIDom); - }; - -public: - DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {} - ~DominatorTreeBase() { reset(); } - - virtual void releaseMemory() { reset(); } - - /// 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; + return dominatedBySlowTreeWalk(A, B); } - inline Node *operator[](BasicBlock *BB) const { - return getNode(BB); + inline bool dominates(BasicBlock *A, BasicBlock *B) { + if (A == B) + return true; + + return dominates(getNode(A), getNode(B)); } - //===--------------------------------------------------------------------===// // API to update (Post)DominatorTree information based on modifications to + /// 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 *Node, Node *NewIDom) { - assert(Node && NewIDom && "Cannot change null node pointers!"); - Node->setIDom(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."); + DomTreeNodes.erase(BB); } /// print - Convert to human readable form - virtual void print(std::ostream &OS) const; + /// + 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(); }; - //===------------------------------------- -// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to -// compute a normal dominator tree. -// -struct DominatorTree : public DominatorTreeBase { - DominatorTree() : DominatorTreeBase(false) {} - - virtual bool runOnFunction(Function &F) { - reset(); // Reset from the last time we were run... - DominatorSet &DS = getAnalysis(); - Root = DS.getRoot(); - calculate(DS); - return false; +/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to +/// compute a normal dominator tree. +/// +class DominatorTree : public DominatorTreeBase { +public: + static char ID; // Pass ID, replacement for typeid + DominatorTree() : DominatorTreeBase((intptr_t)&ID, false) {} + + BasicBlock *getRoot() const { + assert(Roots.size() == 1 && "Should always have entry node!"); + return Roots[0]; } - + + virtual bool runOnFunction(Function &F); + virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); - AU.addRequired(); } + + /// splitBlock + /// BB is split and now it has one successor. Update dominator tree to + /// reflect this change. + void splitBlock(BasicBlock *BB); private: - void calculate(const DominatorSet &DS); + void calculate(Function& F); + DomTreeNode *getNodeForBlock(BasicBlock *BB); + unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N); + void Compress(BasicBlock *V); + BasicBlock *Eval(BasicBlock *v); + void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo); + inline BasicBlock *getIDom(BasicBlock *BB) const { + std::map::const_iterator I = IDoms.find(BB); + return I != IDoms.end() ? I->second : 0; + } }; //===------------------------------------- -// DominatorTree GraphTraits specialization so the DominatorTree can be -// iterable by generic graph iterators. - -template <> struct GraphTraits { - typedef DominatorTree::Node NodeType; +/// DominatorTree GraphTraits specialization so the DominatorTree can be +/// iterable by generic graph iterators. +/// +template <> struct GraphTraits { + typedef DomTreeNode NodeType; typedef NodeType::iterator ChildIteratorType; - + static NodeType *getEntryNode(NodeType *N) { return N; } @@ -372,16 +337,17 @@ template <> struct GraphTraits { }; template <> struct GraphTraits - : public GraphTraits { + : public GraphTraits { static NodeType *getEntryNode(DominatorTree *DT) { - return DT->getNode(DT->getRoot()); + return DT->getRootNode(); } }; + //===----------------------------------------------------------------------===// -// -// DominanceFrontier - Calculate the dominance frontiers for a function. -// +/// DominanceFrontierBase - Common base class for computing forward and inverse +/// dominance frontiers for a function. +/// class DominanceFrontierBase : public DominatorBase { public: typedef std::set DomSetType; // Dom set for a bb @@ -389,7 +355,8 @@ public: protected: DomSetMapType Frontiers; public: - DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {} + DominanceFrontierBase(intptr_t ID, bool isPostDom) + : DominatorBase(ID, isPostDom) {} virtual void releaseMemory() { Frontiers.clear(); } @@ -419,23 +386,37 @@ public: I->second.erase(Node); } - // print - Convert to human readable form - virtual void print(std::ostream &OS) const; + /// 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(); }; //===------------------------------------- -// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to -// compute a normal dominator tree. -// -struct DominanceFrontier : public DominanceFrontierBase { - DominanceFrontier() : DominanceFrontierBase(false) {} +/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is +/// used to compute a forward dominator frontiers. +/// +class DominanceFrontier : public DominanceFrontierBase { +public: + static char ID; // Pass ID, replacement for typeid + DominanceFrontier() : + DominanceFrontierBase((intptr_t)& ID, false) {} + + BasicBlock *getRoot() const { + assert(Roots.size() == 1 && "Should always have entry node!"); + return Roots[0]; + } virtual bool runOnFunction(Function &) { Frontiers.clear(); DominatorTree &DT = getAnalysis(); - Root = DT.getRoot(); - calculate(DT, DT[Root]); + Roots = DT.getRoots(); + assert(Roots.size() == 1 && "Only one entry block for forward domfronts!"); + calculate(DT, DT[Roots[0]]); return false; } @@ -443,9 +424,18 @@ struct DominanceFrontier : public DominanceFrontierBase { 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); }; + +} // End llvm namespace + #endif