Changes in directory llvm/include/llvm/Analysis:
Dominators.h updated: 1.64 -> 1.65 PostDominators.h updated: 1.14 -> 1.15 --- Log message: Completely purge DomSet. This is the (hopefully) final patch for PR1171: http://llvm.org/PR1171 . --- Diffs of the changes: (+1 -149) Dominators.h | 127 ------------------------------------------------------- PostDominators.h | 23 --------- 2 files changed, 1 insertion(+), 149 deletions(-) Index: llvm/include/llvm/Analysis/Dominators.h diff -u llvm/include/llvm/Analysis/Dominators.h:1.64 llvm/include/llvm/Analysis/Dominators.h:1.65 --- llvm/include/llvm/Analysis/Dominators.h:1.64 Tue Mar 20 15:19:48 2007 +++ llvm/include/llvm/Analysis/Dominators.h Sat Apr 7 02:17:27 2007 @@ -10,8 +10,7 @@ // This file defines the following classes: // 1. ImmediateDominators: Calculates and holds a mapping between BasicBlocks // and their immediate dominator. -// 2. DominatorSet: Calculates the [reverse] dominator set for a function -// 3. DominatorTree: Represent the ImmediateDominator as an explicit tree +// 2. DominatorTree: Represent the ImmediateDominator as an explicit tree // structure. // 4. ETForest: Efficient data structure for dominance comparisons and // nearest-common-ancestor queries. @@ -175,127 +174,6 @@ void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo); }; - - -//===----------------------------------------------------------------------===// -/// DominatorSet - Maintain a set<BasicBlock*> 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<BasicBlock*> DomSetType; // Dom set for a bb - // Map of dom sets - typedef std::map<BasicBlock*, DomSetType> DomSetMapType; -protected: - DomSetMapType Doms; -public: - DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {} - - virtual void releaseMemory() { Doms.clear(); } - - // 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; - } - - /// 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(); - } - - /// dominates - Return true if A dominates B. - /// - inline bool dominates(BasicBlock *A, BasicBlock *B) const { - return getDominators(B).count(A) != 0; - } - - /// 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 Module* = 0) const; - void print(std::ostream *OS, const Module* M = 0) const { - if (OS) print(*OS, M); - } - - /// 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; - - //===--------------------------------------------------------------------===// - // 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)); - } - - /// 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); - } -}; - - -//===------------------------------------- -/// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to -/// compute a normal dominator set. -/// -class DominatorSet : public DominatorSetBase { -public: - DominatorSet() : DominatorSetBase(false) {} - - virtual bool runOnFunction(Function &F); - - BasicBlock *getRoot() const { - assert(Roots.size() == 1 && "Should always have entry node!"); - return Roots[0]; - } - - /// getAnalysisUsage - This simply provides a dominator set - /// - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired<ImmediateDominators>(); - AU.setPreservesAll(); - } - - // stub - dummy function, just ignore it - static int stub; -}; - - //===----------------------------------------------------------------------===// /// DominatorTree - Calculate the immediate dominator tree for a function. /// @@ -691,7 +569,4 @@ } // End llvm namespace -// Make sure that any clients of this file link in Dominators.cpp -FORCE_DEFINING_FILE_TO_BE_LINKED(DominatorSet) - #endif Index: llvm/include/llvm/Analysis/PostDominators.h diff -u llvm/include/llvm/Analysis/PostDominators.h:1.14 llvm/include/llvm/Analysis/PostDominators.h:1.15 --- llvm/include/llvm/Analysis/PostDominators.h:1.14 Wed Jun 7 17:00:25 2006 +++ llvm/include/llvm/Analysis/PostDominators.h Sat Apr 7 02:17:27 2007 @@ -38,29 +38,6 @@ void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo); }; -/// PostDominatorSet Class - Concrete subclass of DominatorSetBase that is used -/// to compute the post-dominator set. Because there can be multiple exit nodes -/// in an LLVM function, we calculate post dominators with a special null block -/// which is the virtual exit node that the real exit nodes all virtually branch -/// to. Clients should be prepared to see an entry in the dominator sets with a -/// null BasicBlock*. -/// -struct PostDominatorSet : public DominatorSetBase { - PostDominatorSet() : DominatorSetBase(true) {} - - virtual bool runOnFunction(Function &F); - - /// getAnalysisUsage - This simply provides a dominator set - /// - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired<ImmediatePostDominators>(); - AU.setPreservesAll(); - } - - // stub - dummy function, just ignore it - static void stub(); -}; - /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to /// compute the a post-dominator tree. /// _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
