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 function
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 FunctionPass {
34 const bool IsPostDominators;
36 inline DominatorBase(bool isPostDom) : Root(0), IsPostDominators(isPostDom) {}
38 inline BasicBlock *getRoot() const { return Root; }
40 // Returns true if analysis based of postdoms
41 bool isPostDominator() const { return IsPostDominators; }
44 //===----------------------------------------------------------------------===//
46 // DominatorSet - Maintain a set<BasicBlock*> for every basic block in a
47 // function, that represents the blocks that dominate the block.
49 class DominatorSet : public DominatorBase {
51 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
53 typedef std::map<BasicBlock*, DomSetType> DomSetMapType;
57 void calcForwardDominatorSet(Function *F);
58 void calcPostDominatorSet(Function *F);
60 // DominatorSet ctor - Build either the dominator set or the post-dominator
61 // set for a function...
63 static AnalysisID ID; // Build dominator set
64 static AnalysisID PostDomID; // Build postdominator set
66 DominatorSet(AnalysisID id) : DominatorBase(id == PostDomID) {}
68 virtual bool runOnFunction(Function *F);
70 // Accessor interface:
71 typedef DomSetMapType::const_iterator const_iterator;
72 typedef DomSetMapType::iterator iterator;
73 inline const_iterator begin() const { return Doms.begin(); }
74 inline iterator begin() { return Doms.begin(); }
75 inline const_iterator end() const { return Doms.end(); }
76 inline iterator end() { return Doms.end(); }
77 inline const_iterator find(BasicBlock* B) const { return Doms.find(B); }
78 inline iterator find(BasicBlock* B) { return Doms.find(B); }
80 // getDominators - Return the set of basic blocks that dominate the specified
83 inline const DomSetType &getDominators(BasicBlock *BB) const {
84 const_iterator I = find(BB);
85 assert(I != end() && "BB not in function!");
89 // dominates - Return true if A dominates B.
91 inline bool dominates(BasicBlock *A, BasicBlock *B) const {
92 return getDominators(B).count(A) != 0;
95 // getAnalysisUsage - This obviously provides a dominator set, but it also
96 // uses the UnifyFunctionExitNode pass if building post-dominators
98 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
102 //===----------------------------------------------------------------------===//
104 // ImmediateDominators - Calculate the immediate dominator for each node in a
107 class ImmediateDominators : public DominatorBase {
108 std::map<BasicBlock*, BasicBlock*> IDoms;
109 void calcIDoms(const DominatorSet &DS);
112 // ImmediateDominators ctor - Calculate the idom or post-idom mapping,
115 static AnalysisID ID; // Build immediate dominators
116 static AnalysisID PostDomID; // Build immediate postdominators
118 ImmediateDominators(AnalysisID id) : DominatorBase(id == PostDomID) {}
120 virtual bool runOnFunction(Function *F) {
121 IDoms.clear(); // Reset from the last time we were run...
123 if (isPostDominator())
124 DS = &getAnalysis<DominatorSet>(DominatorSet::PostDomID);
126 DS = &getAnalysis<DominatorSet>();
128 Root = DS->getRoot();
129 calcIDoms(*DS); // Can be used to make rev-idoms
133 // Accessor interface:
134 typedef std::map<BasicBlock*, BasicBlock*> IDomMapType;
135 typedef IDomMapType::const_iterator const_iterator;
136 inline const_iterator begin() const { return IDoms.begin(); }
137 inline const_iterator end() const { return IDoms.end(); }
138 inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);}
140 // operator[] - Return the idom for the specified basic block. The start
141 // node returns null, because it does not have an immediate dominator.
143 inline BasicBlock *operator[](BasicBlock *BB) const {
144 std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
145 return I != IDoms.end() ? I->second : 0;
148 // getAnalysisUsage - This obviously provides a dominator tree, but it
149 // can only do so with the input of dominator sets
151 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
152 AU.setPreservesAll();
153 if (isPostDominator()) {
154 AU.addRequired(DominatorSet::PostDomID);
155 AU.addProvided(PostDomID);
157 AU.addRequired(DominatorSet::ID);
164 //===----------------------------------------------------------------------===//
166 // DominatorTree - Calculate the immediate dominator tree for a function.
168 class DominatorTree : public DominatorBase {
173 std::map<BasicBlock*, Node*> Nodes;
174 void calculate(const DominatorSet &DS);
176 typedef std::map<BasicBlock*, Node*> NodeMapType;
178 class Node2 : public std::vector<Node*> {
179 friend class DominatorTree;
183 inline BasicBlock *getNode() const { return TheNode; }
184 inline Node2 *getIDom() const { return IDom; }
185 inline const std::vector<Node*> &getChildren() const { return *this; }
187 // dominates - Returns true iff this dominates N. Note that this is not a
188 // constant time operation!
189 inline bool dominates(const Node2 *N) const {
191 while ((IDom = N->getIDom()) != 0 && IDom != this)
192 N = IDom; // Walk up the tree
197 inline Node2(BasicBlock *node, Node *iDom)
198 : TheNode(node), IDom(iDom) {}
199 inline Node2 *addChild(Node *C) { push_back(C); return C; }
203 // DominatorTree ctor - Compute a dominator tree, given various amounts of
204 // previous knowledge...
205 static AnalysisID ID; // Build dominator tree
206 static AnalysisID PostDomID; // Build postdominator tree
208 DominatorTree(AnalysisID id) : DominatorBase(id == PostDomID) {}
209 ~DominatorTree() { reset(); }
211 virtual bool runOnFunction(Function *F) {
214 if (isPostDominator())
215 DS = &getAnalysis<DominatorSet>(DominatorSet::PostDomID);
217 DS = &getAnalysis<DominatorSet>();
218 Root = DS->getRoot();
219 calculate(*DS); // Can be used to make rev-idoms
223 inline Node *operator[](BasicBlock *BB) const {
224 NodeMapType::const_iterator i = Nodes.find(BB);
225 return (i != Nodes.end()) ? i->second : 0;
228 // getAnalysisUsage - This obviously provides a dominator tree, but it
229 // uses dominator sets
231 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
232 AU.setPreservesAll();
233 if (isPostDominator()) {
234 AU.addRequired(DominatorSet::PostDomID);
235 AU.addProvided(PostDomID);
237 AU.addRequired(DominatorSet::ID);
244 //===----------------------------------------------------------------------===//
246 // DominanceFrontier - Calculate the dominance frontiers for a function.
248 class DominanceFrontier : public DominatorBase {
250 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
251 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
253 DomSetMapType Frontiers;
254 const DomSetType &calcDomFrontier(const DominatorTree &DT,
255 const DominatorTree::Node *Node);
256 const DomSetType &calcPostDomFrontier(const DominatorTree &DT,
257 const DominatorTree::Node *Node);
260 // DominatorFrontier ctor - Compute dominator frontiers for a function
262 static AnalysisID ID; // Build dominator frontier
263 static AnalysisID PostDomID; // Build postdominator frontier
265 DominanceFrontier(AnalysisID id) : DominatorBase(id == PostDomID) {}
267 virtual bool runOnFunction(Function *) {
270 if (isPostDominator())
271 DT = &getAnalysis<DominatorTree>(DominatorTree::PostDomID);
273 DT = &getAnalysis<DominatorTree>();
274 Root = DT->getRoot();
276 if (isPostDominator())
277 calcPostDomFrontier(*DT, (*DT)[Root]);
279 calcDomFrontier(*DT, (*DT)[Root]);
283 // Accessor interface:
284 typedef DomSetMapType::const_iterator const_iterator;
285 inline const_iterator begin() const { return Frontiers.begin(); }
286 inline const_iterator end() const { return Frontiers.end(); }
287 inline const_iterator find(BasicBlock* B) const { return Frontiers.find(B); }
289 // getAnalysisUsage - This obviously provides the dominance frontier, but it
290 // uses dominator sets
292 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
293 AU.setPreservesAll();
294 if (isPostDominator()) {
295 AU.addRequired(DominatorTree::PostDomID);
296 AU.addProvided(PostDomID);
298 AU.addRequired(DominatorTree::ID);
304 } // End namespace cfg