X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FDominators.h;h=c0c133b67f8f4bccd761443d0ce9a10966b3973c;hb=e083a1d6956bee8a2d54616571f3a626a904e089;hp=3a29eec6c887bb1a0770ee0402a28296fbcca3c8;hpb=8fc2f2072de83665ae20e06929e28317f449bcdf;p=oota-llvm.git diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index 3a29eec6c88..c0c133b67f8 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -15,11 +15,12 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_DOMINATORS_H -#define LLVM_DOMINATORS_H +#ifndef LLVM_ANALYSIS_DOMINATORS_H +#define LLVM_ANALYSIS_DOMINATORS_H #include "llvm/Pass.h" #include +class Instruction; //===----------------------------------------------------------------------===// // @@ -44,26 +45,17 @@ public: // DominatorSet - Maintain a set for every basic block in a // function, that represents the blocks that dominate the block. // -class DominatorSet : public DominatorBase { +class DominatorSetBase : public DominatorBase { public: typedef std::set DomSetType; // Dom set for a bb // Map of dom sets typedef std::map DomSetMapType; -private: +protected: DomSetMapType Doms; - - void calcForwardDominatorSet(Function *F); - void calcPostDominatorSet(Function *F); public: - // DominatorSet ctor - Build either the dominator set or the post-dominator - // set for a function... - // - static AnalysisID ID; // Build dominator set - static AnalysisID PostDomID; // Build postdominator set - - DominatorSet(AnalysisID id) : DominatorBase(id == PostDomID) {} + DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {} - virtual bool runOnFunction(Function *F); + virtual void releaseMemory() { Doms.clear(); } // Accessor interface: typedef DomSetMapType::const_iterator const_iterator; @@ -75,25 +67,64 @@ public: 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. - // + + /// 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; } - // dominates - Return true if A dominates B. - // + /// dominates - Return true if A dominates B. + /// inline bool dominates(BasicBlock *A, BasicBlock *B) const { return getDominators(B).count(A) != 0; } - // getAnalysisUsage - This obviously provides a dominator set, but it also - // uses the UnifyFunctionExitNode pass if building post-dominators - // - virtual void getAnalysisUsage(AnalysisUsage &AU) const; + /// properlyDominates - Return true if A dominates B and A != B. + /// + bool properlyDominates(BasicBlock *A, BasicBlock *B) const { + return dominates(A, B) && A != B; + } + + /// print - Convert to human readable form + virtual void print(std::ostream &OS) const; + + /// dominates - Return true if A dominates B. This performs the special + /// checks neccesary if A and B are in the same basic block. + /// + bool dominates(Instruction *A, Instruction *B) const; + + //===--------------------------------------------------------------------===// + // API to update (Post)DominatorSet information based on modifications to + // the CFG... + + /// 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)); + } +}; + + +//===------------------------------------- +// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to +// compute a normal dominator set. +// +struct DominatorSet : public DominatorSetBase { + DominatorSet() : DominatorSetBase(false) {} + + virtual bool runOnFunction(Function &F); + + // getAnalysisUsage - This simply provides a dominator set + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + } +private: + void calculateDominatorsFromBlock(BasicBlock *BB); }; @@ -102,31 +133,14 @@ public: // ImmediateDominators - Calculate the immediate dominator for each node in a // function. // -class ImmediateDominators : public DominatorBase { +class ImmediateDominatorsBase : public DominatorBase { +protected: std::map IDoms; - void calcIDoms(const DominatorSet &DS); + void calcIDoms(const DominatorSetBase &DS); public: + ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {} - // ImmediateDominators ctor - Calculate the idom or post-idom mapping, - // for a function... - // - static AnalysisID ID; // Build immediate dominators - static AnalysisID PostDomID; // Build immediate postdominators - - ImmediateDominators(AnalysisID id) : DominatorBase(id == PostDomID) {} - - virtual bool runOnFunction(Function *F) { - IDoms.clear(); // Reset from the last time we were run... - DominatorSet *DS; - if (isPostDominator()) - DS = &getAnalysis(DominatorSet::PostDomID); - else - DS = &getAnalysis(); - - Root = DS->getRoot(); - calcIDoms(*DS); // Can be used to make rev-idoms - return false; - } + virtual void releaseMemory() { IDoms.clear(); } // Accessor interface: typedef std::map IDomMapType; @@ -139,22 +153,50 @@ public: // node returns null, because it does not have an immediate dominator. // inline BasicBlock *operator[](BasicBlock *BB) const { + return get(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; } - // getAnalysisUsage - This obviously provides a dominator tree, but it - // can only do so with the input of dominator sets - // + //===--------------------------------------------------------------------===// + // 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. + /// + void addNewBlock(BasicBlock *BB, BasicBlock *IDom) { + assert(get(BB) == 0 && "BasicBlock already in idom info!"); + IDoms[BB] = IDom; + } + + + // 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; + } + virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); - if (isPostDominator()) { - AU.addRequired(DominatorSet::PostDomID); - AU.addProvided(PostDomID); - } else { - AU.addRequired(DominatorSet::ID); - AU.addProvided(ID); - } + AU.addRequired(); } }; @@ -163,18 +205,20 @@ public: // // DominatorTree - Calculate the immediate dominator tree for a function. // -class DominatorTree : public DominatorBase { +class DominatorTreeBase : public DominatorBase { +protected: class Node2; public: typedef Node2 Node; -private: +protected: std::map Nodes; - void calculate(const DominatorSet &DS); void reset(); typedef std::map NodeMapType; public: class Node2 : public std::vector { friend class DominatorTree; + friend class PostDominatorTree; + friend class DominatorTreeBase; BasicBlock *TheNode; Node2 *IDom; public: @@ -198,44 +242,63 @@ public: }; public: - // DominatorTree ctor - Compute a dominator tree, given various amounts of - // previous knowledge... - static AnalysisID ID; // Build dominator tree - static AnalysisID PostDomID; // Build postdominator tree - - DominatorTree(AnalysisID id) : DominatorBase(id == PostDomID) {} - ~DominatorTree() { reset(); } - - virtual bool runOnFunction(Function *F) { - reset(); - DominatorSet *DS; - if (isPostDominator()) - DS = &getAnalysis(DominatorSet::PostDomID); - else - DS = &getAnalysis(); - Root = DS->getRoot(); - calculate(*DS); // Can be used to make rev-idoms - return false; - } + DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {} + ~DominatorTreeBase() { reset(); } - inline Node *operator[](BasicBlock *BB) const { + 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; } - // getAnalysisUsage - This obviously provides a dominator tree, but it - // uses dominator sets - // + inline Node *operator[](BasicBlock *BB) const { + return getNode(BB); + } + + // 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) { + assert(getNode(BB) == 0 && "Block already in dominator tree!"); + Node *New = Nodes[BB] = new Node(BB, IDomNode); + if (IDomNode) IDomNode->addChild(New); + return New; + } + + /// print - Convert to human readable form + virtual void print(std::ostream &OS) const; +}; + + +//===------------------------------------- +// 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; + } + virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); - if (isPostDominator()) { - AU.addRequired(DominatorSet::PostDomID); - AU.addProvided(PostDomID); - } else { - AU.addRequired(DominatorSet::ID); - AU.addProvided(ID); - } + AU.addRequired(); } +private: + void calculate(const DominatorSet &DS); }; @@ -243,40 +306,16 @@ public: // // DominanceFrontier - Calculate the dominance frontiers for a function. // -class DominanceFrontier : public DominatorBase { +class DominanceFrontierBase : public DominatorBase { public: typedef std::set DomSetType; // Dom set for a bb typedef std::map DomSetMapType; // Dom set map -private: +protected: DomSetMapType Frontiers; - const DomSetType &calcDomFrontier(const DominatorTree &DT, - const DominatorTree::Node *Node); - const DomSetType &calcPostDomFrontier(const DominatorTree &DT, - const DominatorTree::Node *Node); public: + DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {} - // DominatorFrontier ctor - Compute dominator frontiers for a function - // - static AnalysisID ID; // Build dominator frontier - static AnalysisID PostDomID; // Build postdominator frontier - - DominanceFrontier(AnalysisID id) : DominatorBase(id == PostDomID) {} - - virtual bool runOnFunction(Function *) { - Frontiers.clear(); - DominatorTree *DT; - if (isPostDominator()) - DT = &getAnalysis(DominatorTree::PostDomID); - else - DT = &getAnalysis(); - Root = DT->getRoot(); - - if (isPostDominator()) - calcPostDomFrontier(*DT, (*DT)[Root]); - else - calcDomFrontier(*DT, (*DT)[Root]); - return false; - } + virtual void releaseMemory() { Frontiers.clear(); } // Accessor interface: typedef DomSetMapType::const_iterator const_iterator; @@ -284,19 +323,33 @@ public: inline const_iterator end() const { return Frontiers.end(); } inline const_iterator find(BasicBlock* B) const { return Frontiers.find(B); } - // getAnalysisUsage - This obviously provides the dominance frontier, but it - // uses dominator sets - // + // print - Convert to human readable form + virtual void print(std::ostream &OS) const; +}; + + +//===------------------------------------- +// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to +// compute a normal dominator tree. +// +struct DominanceFrontier : public DominanceFrontierBase { + DominanceFrontier() : DominanceFrontierBase(false) {} + + virtual bool runOnFunction(Function &) { + Frontiers.clear(); + DominatorTree &DT = getAnalysis(); + Root = DT.getRoot(); + calculate(DT, DT[Root]); + return false; + } + virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); - if (isPostDominator()) { - AU.addRequired(DominatorTree::PostDomID); - AU.addProvided(PostDomID); - } else { - AU.addRequired(DominatorTree::ID); - AU.addProvided(ID); - } + AU.addRequired(); } +private: + const DomSetType &calculate(const DominatorTree &DT, + const DominatorTree::Node *Node); }; #endif