From: Owen Anderson Date: Sun, 8 Apr 2007 21:30:05 +0000 (+0000) Subject: Remove DomSet completely. This concludes work on PR1171. X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=cd4abb7e6da68510be8a843013fe15176f91ec49 Remove DomSet completely. This concludes work on PR1171. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35775 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index 1a6320fde34..f6ac58a69f1 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -10,12 +10,11 @@ // 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 +// 3. ETForest: Efficient data structure for dominance comparisons and // nearest-common-ancestor queries. -// 5. DominanceFrontier: Calculate and hold the dominance frontier for a +// 4. DominanceFrontier: Calculate and hold the dominance frontier for a // function. // // These data structures are listed in increasing order of complexity. It @@ -176,126 +175,6 @@ private: }; - -//===----------------------------------------------------------------------===// -/// 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; -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(); - AU.setPreservesAll(); - } - - // stub - dummy function, just ignore it - static int stub; -}; - - //===----------------------------------------------------------------------===// /// DominatorTree - Calculate the immediate dominator tree for a function. /// @@ -691,7 +570,4 @@ private: } // End llvm namespace -// Make sure that any clients of this file link in Dominators.cpp -FORCE_DEFINING_FILE_TO_BE_LINKED(DominatorSet) - #endif diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index b3e18e8e3ef..3206ba2e51a 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -251,89 +251,6 @@ void ImmediateDominatorsBase::print(std::ostream &o, const Module* ) const { o << "\n"; } - - -//===----------------------------------------------------------------------===// -// DominatorSet Implementation -//===----------------------------------------------------------------------===// - -static RegisterPass -B("domset", "Dominator Set Construction", true); - -// dominates - Return true if A dominates B. This performs the special checks -// necessary if A and B are in the same basic block. -// -bool DominatorSetBase::dominates(Instruction *A, Instruction *B) const { - BasicBlock *BBA = A->getParent(), *BBB = B->getParent(); - if (BBA != BBB) return dominates(BBA, BBB); - - // It is not possible to determine dominance between two PHI nodes - // based on their ordering. - if (isa(A) && isa(B)) - return false; - - // Loop through the basic block until we find A or B. - BasicBlock::iterator I = BBA->begin(); - for (; &*I != A && &*I != B; ++I) /*empty*/; - - if(!IsPostDominators) { - // A dominates B if it is found first in the basic block. - return &*I == A; - } else { - // A post-dominates B if B is found first in the basic block. - return &*I == B; - } -} - - -// runOnFunction - This method calculates the forward dominator sets for the -// specified function. -// -bool DominatorSet::runOnFunction(Function &F) { - BasicBlock *Root = &F.getEntryBlock(); - Roots.clear(); - Roots.push_back(Root); - assert(pred_begin(Root) == pred_end(Root) && - "Root node has predecessors in function!"); - - ImmediateDominators &ID = getAnalysis(); - Doms.clear(); - if (Roots.empty()) return false; - - // Root nodes only dominate themselves. - for (unsigned i = 0, e = Roots.size(); i != e; ++i) - Doms[Roots[i]].insert(Roots[i]); - - // Loop over all of the blocks in the function, calculating dominator sets for - // each function. - for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) - if (BasicBlock *IDom = ID[I]) { // Get idom if block is reachable - DomSetType &DS = Doms[I]; - assert(DS.empty() && "Domset already filled in for this block?"); - DS.insert(I); // Blocks always dominate themselves - - // Insert all dominators into the set... - while (IDom) { - // If we have already computed the dominator sets for our immediate - // dominator, just use it instead of walking all the way up to the root. - DomSetType &IDS = Doms[IDom]; - if (!IDS.empty()) { - DS.insert(IDS.begin(), IDS.end()); - break; - } else { - DS.insert(IDom); - IDom = ID[IDom]; - } - } - } else { - // Ensure that every basic block has at least an empty set of nodes. This - // is important for the case when there is unreachable blocks. - Doms[I]; - } - - return false; -} - namespace llvm { static std::ostream &operator<<(std::ostream &o, const std::set &BBs) { @@ -347,17 +264,6 @@ static std::ostream &operator<<(std::ostream &o, } } -void DominatorSetBase::print(std::ostream &o, const Module* ) const { - for (const_iterator I = begin(), E = end(); I != E; ++I) { - o << " DomSet For BB: "; - if (I->first) - WriteAsOperand(o, I->first, false); - else - o << " <>"; - o << " is:\t" << I->second << "\n"; - } -} - //===----------------------------------------------------------------------===// // DominatorTree Implementation //===----------------------------------------------------------------------===// @@ -1072,5 +978,3 @@ void ETForestBase::print(std::ostream &o, const Module *) const { } o << "\n"; } - -DEFINING_FILE_FOR(DominatorSet) diff --git a/test/Analysis/Dominators/2003-05-12-UnreachableCode.ll b/test/Analysis/Dominators/2003-05-12-UnreachableCode.ll deleted file mode 100644 index 256cb54e56d..00000000000 --- a/test/Analysis/Dominators/2003-05-12-UnreachableCode.ll +++ /dev/null @@ -1,15 +0,0 @@ -; RUN: llvm-upgrade < %s | llvm-as | opt -analyze -domset -disable-verify -; -int %re_match_2() { -ENTRY: - br label %loopexit.20 -loopentry.20: - br label %loopexit.20 - -loopexit.20: - ret int 0 - -endif.46: ; UNREACHABLE - br label %loopentry.20 - -} diff --git a/test/Analysis/Dominators/2007-01-14-BreakCritEdges.ll b/test/Analysis/Dominators/2007-01-14-BreakCritEdges.ll index e6eb0008d64..a00433adbbf 100644 --- a/test/Analysis/Dominators/2007-01-14-BreakCritEdges.ll +++ b/test/Analysis/Dominators/2007-01-14-BreakCritEdges.ll @@ -1,4 +1,4 @@ -; RUN: llvm-as < %s | opt -domset -break-crit-edges -domtree -disable-output +; RUN: llvm-as < %s | opt -break-crit-edges -domtree -disable-output ; PR1110 %struct.OggVorbis_File = type { i8*, i32, i64, i64, %struct.ogg_sync_state, i32, i64*, i64*, i32*, i64*, %struct.vorbis_info*, %struct.vorbis_comment*, i64, i32, i32, i32, double, double, %struct.ogg_stream_state, %struct.vorbis_dsp_state, %struct.vorbis_block, %struct.ov_callbacks } diff --git a/test/BugPoint/crash-basictest.ll b/test/BugPoint/crash-basictest.ll index 647a53f46e3..f631d701193 100644 --- a/test/BugPoint/crash-basictest.ll +++ b/test/BugPoint/crash-basictest.ll @@ -1,6 +1,6 @@ ; Basic test for bugpoint. -; RUN: bugpoint %s -domset -idom -domset -bugpoint-crashcalls \ -; RUN: -domset -idom -domset +; RUN: bugpoint %s -idom -bugpoint-crashcalls \ +; RUN: -idom define i32 @test() { call i32 @test() diff --git a/test/Other/2002-08-02-DomSetProblem.ll b/test/Other/2002-08-02-DomSetProblem.ll deleted file mode 100644 index f62135d3f11..00000000000 --- a/test/Other/2002-08-02-DomSetProblem.ll +++ /dev/null @@ -1,11 +0,0 @@ -; Dominator set calculation is not calculating dominators for unreachable -; blocks. These blocks should at least dominate themselves. This is -; fouling up the verify pass. -; -; RUN: llvm-upgrade < %s | llvm-as | opt -analyze -domset | grep BB - -void %test() { - ret void -BB: - ret void -}