X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FDominators.h;h=c69b1edec7b30667d465efaaf9ab496aae56fe07;hb=b09c146b116359616f6cbd4c8b3328607e00ff42;hp=73c6e6286b5b23bda1ccc15f02a4f7acee60914a;hpb=9ccaf53ada99c63737547c0235baeb8454b04e80;p=oota-llvm.git diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index 73c6e6286b5..c69b1edec7b 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -7,35 +7,25 @@ // //===----------------------------------------------------------------------===// // -// This file defines the following classes: -// 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 -// DominatorTree mapping. +// This file defines the DominatorTree class, which provides fast and efficient +// dominance queries. // //===----------------------------------------------------------------------===// #ifndef LLVM_ANALYSIS_DOMINATORS_H #define LLVM_ANALYSIS_DOMINATORS_H -#include "llvm/Pass.h" -#include "llvm/Function.h" -#include "llvm/Instructions.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/Assembly/Writer.h" +#include "llvm/Function.h" +#include "llvm/Pass.h" #include "llvm/Support/CFG.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/raw_ostream.h" #include -#include -#include namespace llvm { @@ -162,7 +152,7 @@ EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase); EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase); template -static raw_ostream &operator<<(raw_ostream &o, +inline raw_ostream &operator<<(raw_ostream &o, const DomTreeNodeBase *Node) { if (Node->getBlock()) WriteAsOperand(o, Node->getBlock(), false); @@ -175,7 +165,7 @@ static raw_ostream &operator<<(raw_ostream &o, } template -static void PrintDomTree(const DomTreeNodeBase *N, raw_ostream &o, +inline void PrintDomTree(const DomTreeNodeBase *N, raw_ostream &o, unsigned Lev) { o.indent(2*Lev) << "[" << Lev << "] " << N; for (typename DomTreeNodeBase::const_iterator I = N->begin(), @@ -195,6 +185,18 @@ void Calculate(DominatorTreeBase::NodeType>& DT, template class DominatorTreeBase : public DominatorBase { + bool dominatedBySlowTreeWalk(const DomTreeNodeBase *A, + const DomTreeNodeBase *B) const { + assert(A != B); + assert(isReachableFromEntry(B)); + assert(isReachableFromEntry(A)); + + const DomTreeNodeBase *IDom; + while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B) + B = IDom; // Walk up the tree + return IDom != 0; + } + protected: typedef DenseMap*> DomTreeNodeMapType; DomTreeNodeMapType DomTreeNodes; @@ -205,15 +207,11 @@ protected: // Information record used during immediate dominators computation. struct InfoRec { unsigned DFSNum; + unsigned Parent; unsigned Semi; - unsigned Size; - NodeT *Label, *Child; - unsigned Parent, Ancestor; + NodeT *Label; - std::vector Bucket; - - InfoRec() : DFSNum(0), Semi(0), Size(0), Label(0), Child(0), Parent(0), - Ancestor(0) {} + InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(0) {} }; DenseMap IDoms; @@ -303,9 +301,6 @@ public: : DominatorBase(isPostDom), DFSInfoValid(false), SlowQueries(0) {} virtual ~DominatorTreeBase() { reset(); } - // FIXME: Should remove this - virtual bool runOnFunction(Function &F) { return false; } - /// compare - Return false if the other dominator tree base matches this /// dominator tree base. Otherwise return true. bool compare(DominatorTreeBase &Other) const { @@ -338,8 +333,7 @@ public: /// block. This is the same as using operator[] on this class. /// inline DomTreeNodeBase *getNode(NodeT *BB) const { - typename DomTreeNodeMapType::const_iterator I = DomTreeNodes.find(BB); - return I != DomTreeNodes.end() ? I->second : 0; + return DomTreeNodes.lookup(BB); } /// getRootNode - This returns the entry node for the CFG of the function. If @@ -352,35 +346,30 @@ public: DomTreeNodeBase *getRootNode() { return RootNode; } const DomTreeNodeBase *getRootNode() const { return RootNode; } - /// properlyDominates - Returns true iff this dominates N and this != N. + /// properlyDominates - Returns true iff A dominates B and A != B. /// Note that this is not a constant time operation! /// bool properlyDominates(const DomTreeNodeBase *A, - const DomTreeNodeBase *B) const { - if (A == 0 || B == 0) return false; - return dominatedBySlowTreeWalk(A, B); - } - - inline bool properlyDominates(NodeT *A, NodeT *B) { - return properlyDominates(getNode(A), getNode(B)); - } - - bool dominatedBySlowTreeWalk(const DomTreeNodeBase *A, - const DomTreeNodeBase *B) const { - const DomTreeNodeBase *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; + const DomTreeNodeBase *B) { + if (A == 0 || B == 0) + return false; + if (A == B) + return false; + return dominates(A, B); } + bool properlyDominates(const NodeT *A, const NodeT *B); /// isReachableFromEntry - Return true if A is dominated by the entry /// block of the function containing it. - bool isReachableFromEntry(NodeT* A) { + bool isReachableFromEntry(const NodeT* A) const { assert(!this->isPostDominator() && "This is not implemented for post dominators"); - return dominates(&A->getParent()->front(), A); + return isReachableFromEntry(getNode(const_cast(A))); + } + + inline bool isReachableFromEntry(const DomTreeNodeBase *A) const { + return A; } /// dominates - Returns true iff A dominates B. Note that this is not a @@ -388,10 +377,16 @@ public: /// inline bool dominates(const DomTreeNodeBase *A, const DomTreeNodeBase *B) { + // A node trivially dominates itself. if (B == A) - return true; // A node trivially dominates itself. + return true; - if (A == 0 || B == 0) + // An unreachable node is dominated by anything. + if (!isReachableFromEntry(B)) + return true; + + // And dominates nothing. + if (!isReachableFromEntry(A)) return false; // Compare the result of the tree walk and the dfs numbers, if expensive @@ -416,16 +411,7 @@ public: return dominatedBySlowTreeWalk(A, B); } - inline bool dominates(const NodeT *A, const NodeT *B) { - if (A == B) - return true; - - // Cast away the const qualifiers here. This is ok since - // this function doesn't actually return the values returned - // from getNode. - return dominates(getNode(const_cast(A)), - getNode(const_cast(B))); - } + bool dominates(const NodeT *A, const NodeT *B); NodeT *getRoot() const { assert(this->Roots.size() == 1 && "Should always have entry node!"); @@ -478,6 +464,13 @@ public: return NULL; } + const NodeT *findNearestCommonDominator(const NodeT *A, const NodeT *B) { + // Cast away the const qualifiers here. This is ok since + // const is re-introduced on the return type. + return findNearestCommonDominator(const_cast(A), + const_cast(B)); + } + //===--------------------------------------------------------------------===// // API to update (Post)DominatorTree information based on modifications to // the CFG... @@ -509,7 +502,7 @@ public: } /// eraseNode - Removes a node from the dominator tree. Block must not - /// domiante any other blocks. Removes node from its immediate dominator's + /// dominate any other blocks. Removes node from its immediate dominator's /// children list. Deletes dominator node associated with basic block BB. void eraseNode(NodeT *BB) { DomTreeNodeBase *Node = getNode(BB); @@ -556,7 +549,7 @@ public: o << "Inorder PostDominator Tree: "; else o << "Inorder Dominator Tree: "; - if (this->DFSInfoValid) + if (!this->DFSInfoValid) o << "DFSNumbers invalid: " << SlowQueries << " slow queries."; o << "\n"; @@ -566,19 +559,11 @@ public: } protected: - template - friend void Compress(DominatorTreeBase& DT, - typename GraphT::NodeType* VIn); - template friend typename GraphT::NodeType* Eval( DominatorTreeBase& DT, - typename GraphT::NodeType* V); - - template - friend void Link(DominatorTreeBase& DT, - unsigned DFSNumV, typename GraphT::NodeType* W, - typename DominatorTreeBase::InfoRec &WInfo); + typename GraphT::NodeType* V, + unsigned LastLinked); template friend unsigned DFSPass(DominatorTreeBase& DT, @@ -634,9 +619,8 @@ protected: } DomTreeNodeBase *getNodeForBlock(NodeT *BB) { - typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.find(BB); - if (I != this->DomTreeNodes.end() && I->second) - return I->second; + if (DomTreeNodeBase *Node = getNode(BB)) + return Node; // Haven't calculated this node yet? Get or calculate the node for the // immediate dominator. @@ -652,8 +636,7 @@ protected: } inline NodeT *getIDom(NodeT *BB) const { - typename DenseMap::const_iterator I = IDoms.find(BB); - return I != IDoms.end() ? I->second : 0; + return IDoms.lookup(BB); } inline void addRoot(NodeT* BB) { @@ -664,21 +647,24 @@ public: /// recalculate - compute a dominator tree for the given function template void recalculate(FT& F) { + typedef GraphTraits TraitsTy; reset(); this->Vertex.push_back(0); if (!this->IsPostDominators) { // Initialize root - this->Roots.push_back(&F.front()); - this->IDoms[&F.front()] = 0; - this->DomTreeNodes[&F.front()] = 0; + NodeT *entry = TraitsTy::getEntryNode(&F); + this->Roots.push_back(entry); + this->IDoms[entry] = 0; + this->DomTreeNodes[entry] = 0; Calculate(*this, F); } else { // Initialize the roots list - for (typename FT::iterator I = F.begin(), E = F.end(); I != E; ++I) { - if (std::distance(GraphTraits::child_begin(I), - GraphTraits::child_end(I)) == 0) + for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F), + E = TraitsTy::nodes_end(&F); I != E; ++I) { + if (std::distance(TraitsTy::child_begin(I), + TraitsTy::child_end(I)) == 0) addRoot(I); // Prepopulate maps so that we don't get iterator invalidation issues later. @@ -691,8 +677,49 @@ public: } }; +// These two functions are declared out of line as a workaround for building +// with old (< r147295) versions of clang because of pr11642. +template +bool DominatorTreeBase::dominates(const NodeT *A, const NodeT *B) { + if (A == B) + return true; + + // Cast away the const qualifiers here. This is ok since + // this function doesn't actually return the values returned + // from getNode. + return dominates(getNode(const_cast(A)), + getNode(const_cast(B))); +} +template +bool +DominatorTreeBase::properlyDominates(const NodeT *A, const NodeT *B) { + if (A == B) + return false; + + // Cast away the const qualifiers here. This is ok since + // this function doesn't actually return the values returned + // from getNode. + return dominates(getNode(const_cast(A)), + getNode(const_cast(B))); +} + EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase); +class BasicBlockEdge { + const BasicBlock *Start; + const BasicBlock *End; +public: + BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) : + Start(Start_), End(End_) { } + const BasicBlock *getStart() const { + return Start; + } + const BasicBlock *getEnd() const { + return End; + } + bool isSingleEdge() const; +}; + //===------------------------------------- /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to /// compute a normal dominator tree. @@ -703,6 +730,7 @@ public: DominatorTreeBase* DT; DominatorTree() : FunctionPass(ID) { + initializeDominatorTreePass(*PassRegistry::getPassRegistry()); DT = new DominatorTreeBase(false); } @@ -751,7 +779,7 @@ public: AU.setPreservesAll(); } - inline bool dominates(DomTreeNode* A, DomTreeNode* B) const { + inline bool dominates(const DomTreeNode* A, const DomTreeNode* B) const { return DT->dominates(A, B); } @@ -759,15 +787,20 @@ public: return DT->dominates(A, 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(const Instruction *A, const Instruction *B) const; + // dominates - Return true if Def dominates a use in User. This performs + // the special checks necessary if Def and User are in the same basic block. + // Note that Def doesn't dominate a use in Def itself! + bool dominates(const Instruction *Def, const Use &U) const; + bool dominates(const Instruction *Def, const Instruction *User) const; + bool dominates(const Instruction *Def, const BasicBlock *BB) const; + bool dominates(const BasicBlockEdge &BBE, const Use &U) const; + bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const; bool properlyDominates(const DomTreeNode *A, const DomTreeNode *B) const { return DT->properlyDominates(A, B); } - bool properlyDominates(BasicBlock *A, BasicBlock *B) const { + bool properlyDominates(const BasicBlock *A, const BasicBlock *B) const { return DT->properlyDominates(A, B); } @@ -777,6 +810,11 @@ public: return DT->findNearestCommonDominator(A, B); } + inline const BasicBlock *findNearestCommonDominator(const BasicBlock *A, + const BasicBlock *B) { + return DT->findNearestCommonDominator(A, B); + } + inline DomTreeNode *operator[](BasicBlock *BB) const { return DT->getNode(BB); } @@ -807,7 +845,7 @@ public: } /// eraseNode - Removes a node from the dominator tree. Block must not - /// domiante any other blocks. Removes node from its immediate dominator's + /// dominate any other blocks. Removes node from its immediate dominator's /// children list. Deletes dominator node associated with basic block BB. inline void eraseNode(BasicBlock *BB) { DT->eraseNode(BB); @@ -819,10 +857,12 @@ public: DT->splitBlock(NewBB); } - bool isReachableFromEntry(BasicBlock* A) { + bool isReachableFromEntry(const BasicBlock* A) const { return DT->isReachableFromEntry(A); } + bool isReachableFromEntry(const Use &U) const; + virtual void releaseMemory() { DT->releaseMemory(); @@ -876,194 +916,6 @@ template <> struct GraphTraits }; -//===----------------------------------------------------------------------===// -/// DominanceFrontierBase - Common base class for computing forward and inverse -/// dominance frontiers for a function. -/// -class DominanceFrontierBase : public FunctionPass { -public: - typedef std::set DomSetType; // Dom set for a bb - typedef std::map DomSetMapType; // Dom set map -protected: - DomSetMapType Frontiers; - std::vector Roots; - const bool IsPostDominators; - -public: - DominanceFrontierBase(char &ID, bool isPostDom) - : FunctionPass(ID), IsPostDominators(isPostDom) {} - - /// 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; } - - virtual void releaseMemory() { Frontiers.clear(); } - - // Accessor interface: - typedef DomSetMapType::iterator iterator; - typedef DomSetMapType::const_iterator const_iterator; - iterator begin() { return Frontiers.begin(); } - const_iterator begin() const { return Frontiers.begin(); } - iterator end() { return Frontiers.end(); } - const_iterator end() const { return Frontiers.end(); } - iterator find(BasicBlock *B) { return Frontiers.find(B); } - const_iterator find(BasicBlock *B) const { return Frontiers.find(B); } - - iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) { - assert(find(BB) == end() && "Block already in DominanceFrontier!"); - return Frontiers.insert(std::make_pair(BB, frontier)).first; - } - - /// removeBlock - Remove basic block BB's frontier. - void removeBlock(BasicBlock *BB) { - assert(find(BB) != end() && "Block is not in DominanceFrontier!"); - for (iterator I = begin(), E = end(); I != E; ++I) - I->second.erase(BB); - Frontiers.erase(BB); - } - - void addToFrontier(iterator I, BasicBlock *Node) { - assert(I != end() && "BB is not in DominanceFrontier!"); - I->second.insert(Node); - } - - void removeFromFrontier(iterator I, BasicBlock *Node) { - assert(I != end() && "BB is not in DominanceFrontier!"); - assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB"); - I->second.erase(Node); - } - - /// compareDomSet - Return false if two domsets match. Otherwise - /// return true; - bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const { - std::set tmpSet; - for (DomSetType::const_iterator I = DS2.begin(), - E = DS2.end(); I != E; ++I) - tmpSet.insert(*I); - - for (DomSetType::const_iterator I = DS1.begin(), - E = DS1.end(); I != E; ) { - BasicBlock *Node = *I++; - - if (tmpSet.erase(Node) == 0) - // Node is in DS1 but not in DS2. - return true; - } - - if (!tmpSet.empty()) - // There are nodes that are in DS2 but not in DS1. - return true; - - // DS1 and DS2 matches. - return false; - } - - /// compare - Return true if the other dominance frontier base matches - /// this dominance frontier base. Otherwise return false. - bool compare(DominanceFrontierBase &Other) const { - DomSetMapType tmpFrontiers; - for (DomSetMapType::const_iterator I = Other.begin(), - E = Other.end(); I != E; ++I) - tmpFrontiers.insert(std::make_pair(I->first, I->second)); - - for (DomSetMapType::iterator I = tmpFrontiers.begin(), - E = tmpFrontiers.end(); I != E; ) { - BasicBlock *Node = I->first; - const_iterator DFI = find(Node); - if (DFI == end()) - return true; - - if (compareDomSet(I->second, DFI->second)) - return true; - - ++I; - tmpFrontiers.erase(Node); - } - - if (!tmpFrontiers.empty()) - return true; - - return false; - } - - /// print - Convert to human readable form - /// - virtual void print(raw_ostream &OS, const Module* = 0) const; - - /// dump - Dump the dominance frontier to dbgs(). - void dump() const; -}; - - -//===------------------------------------- -/// 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(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(); - Roots = DT.getRoots(); - assert(Roots.size() == 1 && "Only one entry block for forward domfronts!"); - calculate(DT, DT[Roots[0]]); - return false; - } - - virtual void verifyAnalysis() const; - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired(); - } - - /// splitBlock - BB is split and now it has one successor. Update dominance - /// frontier to reflect this change. - void splitBlock(BasicBlock *BB); - - /// BasicBlock BB's new dominator is NewBB. Update BB's dominance frontier - /// to reflect this change. - void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB, - DominatorTree *DT) { - // NewBB is now dominating BB. Which means BB's dominance - // frontier is now part of NewBB's dominance frontier. However, BB - // itself is not member of NewBB's dominance frontier. - DominanceFrontier::iterator NewDFI = find(NewBB); - DominanceFrontier::iterator DFI = find(BB); - // If BB was an entry block then its frontier is empty. - if (DFI == end()) - return; - DominanceFrontier::DomSetType BBSet = DFI->second; - for (DominanceFrontier::DomSetType::iterator BBSetI = BBSet.begin(), - BBSetE = BBSet.end(); BBSetI != BBSetE; ++BBSetI) { - BasicBlock *DFMember = *BBSetI; - // Insert only if NewBB dominates DFMember. - if (!DT->dominates(NewBB, DFMember)) - NewDFI->second.insert(DFMember); - } - NewDFI->second.erase(BB); - } - - const DomSetType &calculate(const DominatorTree &DT, - const DomTreeNode *Node); -}; - - } // End llvm namespace #endif