// 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.
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.
///
} // End llvm namespace
-// Make sure that any clients of this file link in Dominators.cpp
-FORCE_DEFINING_FILE_TO_BE_LINKED(DominatorSet)
-
#endif
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.
///
(void)new llvm::IntervalPartition();
(void)new llvm::ImmediateDominators();
- (void)new llvm::PostDominatorSet();
(void)new llvm::FindUsedTypes();
(void)new llvm::ScalarEvolution();
((llvm::Function*)0)->viewCFGOnly();
bool AllowIdenticalEdges = false);
/// SplitCriticalEdge - If this edge is a critical edge, insert a new node to
-/// split the critical edge. This will update DominatorSet, ImmediateDominator,
+/// split the critical edge. This will update ETForest, ImmediateDominator,
/// DominatorTree, and DominatorFrontier information if it is available, thus
/// calling this pass will not invalidate either of them. This returns true if
/// the edge was split, false otherwise. If MergeIdenticalEdges is true (the
namespace llvm {
class BasicBlock;
- class DominatorSet;
class Function;
class Loop;
return false;
}
-//===----------------------------------------------------------------------===//
-// PostDominatorSet Implementation
-//===----------------------------------------------------------------------===//
-
-static RegisterPass<PostDominatorSet>
-B("postdomset", "Post-Dominator Set Construction", true);
-
-// Postdominator set construction. This converts the specified function to only
-// have a single exit node (return stmt), then calculates the post dominance
-// sets for the function.
-//
-bool PostDominatorSet::runOnFunction(Function &F) {
- // Scan the function looking for the root nodes of the post-dominance
- // relationships. These blocks end with return and unwind instructions.
- // While we are iterating over the function, we also initialize all of the
- // domsets to empty.
- Roots.clear();
- for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
- if (succ_begin(I) == succ_end(I))
- Roots.push_back(I);
-
- // If there are no exit nodes for the function, postdomsets are all empty.
- // This can happen if the function just contains an infinite loop, for
- // example.
- ImmediatePostDominators &IPD = getAnalysis<ImmediatePostDominators>();
- Doms.clear(); // Reset from the last time we were run...
- if (Roots.empty()) return false;
-
- // If we have more than one root, we insert an artificial "null" exit, which
- // has "virtual edges" to each of the real exit nodes.
- //if (Roots.size() > 1)
- // Doms[0].insert(0);
-
- // 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 *IPDom = IPD[I]) { // Get idom if block is reachable
- DomSetType &DS = Doms[I];
- assert(DS.empty() && "PostDomset already filled in for this block?");
- DS.insert(I); // Blocks always dominate themselves
-
- // Insert all dominators into the set...
- while (IPDom) {
- // If we have already computed the dominator sets for our immediate post
- // dominator, just use it instead of walking all the way up to the root.
- DomSetType &IPDS = Doms[IPDom];
- if (!IPDS.empty()) {
- DS.insert(IPDS.begin(), IPDS.end());
- break;
- } else {
- DS.insert(IPDom);
- IPDom = IPD[IPDom];
- }
- }
- } 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;
-}
-
//===----------------------------------------------------------------------===//
// PostDominatorTree Implementation
//===----------------------------------------------------------------------===//
// many analyses if they are around.
AU.addPreservedID(LoopSimplifyID);
AU.addPreserved<LoopInfo>();
- AU.addPreserved<DominatorSet>();
AU.addPreserved<ETForest>();
AU.addPreserved<ImmediateDominators>();
AU.addPreserved<DominanceFrontier>();
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) {
- for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
- I != E; ++I)
- if (*I)
- WriteAsOperand(o, *I, false);
- else
- o << " <<exit node>>";
- return 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
//===----------------------------------------------------------------------===//
return *Result;
}
+namespace llvm {
+static std::ostream &operator<<(std::ostream &o,
+ const std::set<BasicBlock*> &BBs) {
+ for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
+ I != E; ++I)
+ if (*I)
+ WriteAsOperand(o, *I, false);
+ else
+ o << " <<exit node>>";
+ return o;
+}
+}
+
+
void DominanceFrontierBase::print(std::ostream &o, const Module* ) const {
for (const_iterator I = begin(), E = end(); I != E; ++I) {
o << " DomFrontier for BB";
}
o << "\n";
}
-
-DEFINING_FILE_FOR(DominatorSet)
projects / oota-llvm.git / commitdiff