1 //===- llvm/Analysis/Dominators.h - Dominator Info Calculation ---*- C++ -*--=//
3 // This file defines the following classes:
4 // 1. DominatorSet: Calculates the [reverse] dominator set for a method
5 // 2. ImmediateDominators: Calculates and holds a mapping between BasicBlocks
6 // and their immediate dominator.
7 // 3. DominatorTree: Represent the ImmediateDominator as an explicit tree
9 // 4. DominanceFrontier: Calculate and hold the dominance frontier for a
12 // These data structures are listed in increasing order of complexity. It
13 // takes longer to calculate the dominator frontier, for example, than the
14 // ImmediateDominator mapping.
16 //===----------------------------------------------------------------------===//
18 #ifndef LLVM_DOMINATORS_H
19 #define LLVM_DOMINATORS_H
21 #include "llvm/Pass.h"
26 //===----------------------------------------------------------------------===//
28 // DominatorBase - Base class that other, more interesting dominator analyses
31 class DominatorBase : public MethodPass {
34 const bool IsPostDominators;
36 inline DominatorBase(bool isPostDom) : Root(0), IsPostDominators(isPostDom) {}
38 inline const BasicBlock *getRoot() const { return Root; }
39 inline BasicBlock *getRoot() { return Root; }
41 // Returns true if analysis based of postdoms
42 bool isPostDominator() const { return IsPostDominators; }
45 //===----------------------------------------------------------------------===//
47 // DominatorSet - Maintain a set<const BasicBlock*> for every basic block in a
48 // method, that represents the blocks that dominate the block.
50 class DominatorSet : public DominatorBase {
52 typedef std::set<const BasicBlock*> DomSetType; // Dom set for a bb
54 typedef std::map<const BasicBlock*, DomSetType> DomSetMapType;
58 void calcForwardDominatorSet(Function *F);
59 void calcPostDominatorSet(Function *F);
61 // DominatorSet ctor - Build either the dominator set or the post-dominator
62 // set for a method...
64 static AnalysisID ID; // Build dominator set
65 static AnalysisID PostDomID; // Build postdominator set
67 DominatorSet(AnalysisID id) : DominatorBase(id == PostDomID) {}
69 virtual bool runOnMethod(Function *F);
71 // Accessor interface:
72 typedef DomSetMapType::const_iterator const_iterator;
73 typedef DomSetMapType::iterator iterator;
74 inline const_iterator begin() const { return Doms.begin(); }
75 inline iterator begin() { return Doms.begin(); }
76 inline const_iterator end() const { return Doms.end(); }
77 inline iterator end() { return Doms.end(); }
78 inline const_iterator find(const BasicBlock* B) const { return Doms.find(B); }
79 inline iterator find( BasicBlock* B) { return Doms.find(B); }
81 // getDominators - Return the set of basic blocks that dominate the specified
84 inline const DomSetType &getDominators(const BasicBlock *BB) const {
85 const_iterator I = find(BB);
86 assert(I != end() && "BB not in method!");
90 // dominates - Return true if A dominates B.
92 inline bool dominates(const BasicBlock *A, const BasicBlock *B) const {
93 return getDominators(B).count(A) != 0;
96 // getAnalysisUsageInfo - This obviously provides a dominator set, but it also
97 // uses the UnifyMethodExitNode pass if building post-dominators
99 virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
100 Pass::AnalysisSet &Destroyed,
101 Pass::AnalysisSet &Provided);
105 //===----------------------------------------------------------------------===//
107 // ImmediateDominators - Calculate the immediate dominator for each node in a
110 class ImmediateDominators : public DominatorBase {
111 std::map<const BasicBlock*, const BasicBlock*> IDoms;
112 void calcIDoms(const DominatorSet &DS);
115 // ImmediateDominators ctor - Calculate the idom or post-idom mapping,
118 static AnalysisID ID; // Build immediate dominators
119 static AnalysisID PostDomID; // Build immediate postdominators
121 ImmediateDominators(AnalysisID id) : DominatorBase(id == PostDomID) {}
123 virtual bool runOnMethod(Function *F) {
124 IDoms.clear(); // Reset from the last time we were run...
126 if (isPostDominator())
127 DS = &getAnalysis<DominatorSet>(DominatorSet::PostDomID);
129 DS = &getAnalysis<DominatorSet>();
131 Root = DS->getRoot();
132 calcIDoms(*DS); // Can be used to make rev-idoms
136 // Accessor interface:
137 typedef std::map<const BasicBlock*, const BasicBlock*> IDomMapType;
138 typedef IDomMapType::const_iterator const_iterator;
139 inline const_iterator begin() const { return IDoms.begin(); }
140 inline const_iterator end() const { return IDoms.end(); }
141 inline const_iterator find(const BasicBlock* B) const { return IDoms.find(B);}
143 // operator[] - Return the idom for the specified basic block. The start
144 // node returns null, because it does not have an immediate dominator.
146 inline const BasicBlock *operator[](const BasicBlock *BB) const {
147 std::map<const BasicBlock*, const BasicBlock*>::const_iterator I =
149 return I != IDoms.end() ? I->second : 0;
152 // getAnalysisUsageInfo - This obviously provides a dominator tree, but it
153 // can only do so with the input of dominator sets
155 virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
156 Pass::AnalysisSet &Destroyed,
157 Pass::AnalysisSet &Provided) {
158 if (isPostDominator()) {
159 Requires.push_back(DominatorSet::PostDomID);
160 Provided.push_back(PostDomID);
162 Requires.push_back(DominatorSet::ID);
163 Provided.push_back(ID);
169 //===----------------------------------------------------------------------===//
171 // DominatorTree - Calculate the immediate dominator tree for a method.
173 class DominatorTree : public DominatorBase {
178 std::map<const BasicBlock*, Node*> Nodes;
179 void calculate(const DominatorSet &DS);
181 typedef std::map<const BasicBlock*, Node*> NodeMapType;
183 class Node2 : public std::vector<Node*> {
184 friend class DominatorTree;
185 const BasicBlock *TheNode;
188 inline const BasicBlock *getNode() const { return TheNode; }
189 inline Node2 *getIDom() const { return IDom; }
190 inline const std::vector<Node*> &getChildren() const { return *this; }
192 // dominates - Returns true iff this dominates N. Note that this is not a
193 // constant time operation!
194 inline bool dominates(const Node2 *N) const {
196 while ((IDom = N->getIDom()) != 0 && IDom != this)
197 N = IDom; // Walk up the tree
202 inline Node2(const BasicBlock *node, Node *iDom)
203 : TheNode(node), IDom(iDom) {}
204 inline Node2 *addChild(Node *C) { push_back(C); return C; }
208 // DominatorTree ctor - Compute a dominator tree, given various amounts of
209 // previous knowledge...
210 static AnalysisID ID; // Build dominator tree
211 static AnalysisID PostDomID; // Build postdominator tree
213 DominatorTree(AnalysisID id) : DominatorBase(id == PostDomID) {}
214 ~DominatorTree() { reset(); }
216 virtual bool runOnMethod(Function *F) {
219 if (isPostDominator())
220 DS = &getAnalysis<DominatorSet>(DominatorSet::PostDomID);
222 DS = &getAnalysis<DominatorSet>();
223 Root = DS->getRoot();
224 calculate(*DS); // Can be used to make rev-idoms
228 inline const Node *operator[](const BasicBlock *BB) const {
229 NodeMapType::const_iterator i = Nodes.find(BB);
230 return (i != Nodes.end()) ? i->second : 0;
233 // getAnalysisUsageInfo - This obviously provides a dominator tree, but it
234 // uses dominator sets
236 virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
237 Pass::AnalysisSet &Destroyed,
238 Pass::AnalysisSet &Provided) {
239 if (isPostDominator()) {
240 Requires.push_back(DominatorSet::PostDomID);
241 Provided.push_back(PostDomID);
243 Requires.push_back(DominatorSet::ID);
244 Provided.push_back(ID);
250 //===----------------------------------------------------------------------===//
252 // DominanceFrontier - Calculate the dominance frontiers for a method.
254 class DominanceFrontier : public DominatorBase {
256 typedef std::set<const BasicBlock*> DomSetType; // Dom set for a bb
257 typedef std::map<const BasicBlock*, DomSetType> DomSetMapType; // Dom set map
259 DomSetMapType Frontiers;
260 const DomSetType &calcDomFrontier(const DominatorTree &DT,
261 const DominatorTree::Node *Node);
262 const DomSetType &calcPostDomFrontier(const DominatorTree &DT,
263 const DominatorTree::Node *Node);
266 // DominatorFrontier ctor - Compute dominator frontiers for a method
268 static AnalysisID ID; // Build dominator frontier
269 static AnalysisID PostDomID; // Build postdominator frontier
271 DominanceFrontier(AnalysisID id) : DominatorBase(id == PostDomID) {}
273 virtual bool runOnMethod(Function *) {
276 if (isPostDominator())
277 DT = &getAnalysis<DominatorTree>(DominatorTree::PostDomID);
279 DT = &getAnalysis<DominatorTree>();
280 Root = DT->getRoot();
282 if (isPostDominator())
283 calcPostDomFrontier(*DT, (*DT)[Root]);
285 calcDomFrontier(*DT, (*DT)[Root]);
289 // Accessor interface:
290 typedef DomSetMapType::const_iterator const_iterator;
291 inline const_iterator begin() const { return Frontiers.begin(); }
292 inline const_iterator end() const { return Frontiers.end(); }
293 inline const_iterator find(const BasicBlock* B) const { return Frontiers.find(B); }
295 // getAnalysisUsageInfo - This obviously provides a dominator tree, but it
296 // uses dominator sets
298 virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
299 Pass::AnalysisSet &Destroyed,
300 Pass::AnalysisSet &Provided) {
301 if (isPostDominator()) {
302 Requires.push_back(DominatorTree::PostDomID);
303 Provided.push_back(PostDomID);
305 Requires.push_back(DominatorTree::ID);
306 Provided.push_back(ID);
311 } // End namespace cfg