aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Analysis/Dominators.h130
-rw-r--r--lib/VMCore/Dominators.cpp96
-rw-r--r--test/Analysis/Dominators/2003-05-12-UnreachableCode.ll15
-rw-r--r--test/Analysis/Dominators/2007-01-14-BreakCritEdges.ll2
-rw-r--r--test/BugPoint/crash-basictest.ll4
-rw-r--r--test/Other/2002-08-02-DomSetProblem.ll11
6 files changed, 6 insertions, 252 deletions
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 1a6320f..f6ac58a 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<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 +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 b3e18e8..3206ba2 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<DominatorSet>
-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<PHINode>(A) && isa<PHINode>(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<ImmediateDominators>();
- 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<BasicBlock*> &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 << " <<exit node>>";
- 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 256cb54..0000000
--- 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 e6eb000..a00433a 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 647a53f..f631d70 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 f62135d..0000000
--- 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
-}
generated by cgit v1.1 at 2024-05-29 09:47:36 +0000