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_ANALYSIS_DOMINATORS_H
19 #define LLVM_ANALYSIS_DOMINATORS_H
21 #include "llvm/Pass.h"
26 template <typename GraphType> struct GraphTraits;
28 //===----------------------------------------------------------------------===//
30 // DominatorBase - Base class that other, more interesting dominator analyses
33 class DominatorBase : public FunctionPass {
36 const bool IsPostDominators;
38 inline DominatorBase(bool isPostDom) : Root(0), IsPostDominators(isPostDom) {}
40 inline BasicBlock *getRoot() const { return Root; }
42 // Returns true if analysis based of postdoms
43 bool isPostDominator() const { return IsPostDominators; }
46 //===----------------------------------------------------------------------===//
48 // DominatorSet - Maintain a set<BasicBlock*> for every basic block in a
49 // function, that represents the blocks that dominate the block. If the block
50 // is unreachable in this function, the set will be empty. This cannot happen
51 // for reachable code, because every block dominates at least itself.
53 class DominatorSetBase : public DominatorBase {
55 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
57 typedef std::map<BasicBlock*, DomSetType> DomSetMapType;
61 DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {}
63 virtual void releaseMemory() { Doms.clear(); }
65 // Accessor interface:
66 typedef DomSetMapType::const_iterator const_iterator;
67 typedef DomSetMapType::iterator iterator;
68 inline const_iterator begin() const { return Doms.begin(); }
69 inline iterator begin() { return Doms.begin(); }
70 inline const_iterator end() const { return Doms.end(); }
71 inline iterator end() { return Doms.end(); }
72 inline const_iterator find(BasicBlock* B) const { return Doms.find(B); }
73 inline iterator find(BasicBlock* B) { return Doms.find(B); }
76 /// getDominators - Return the set of basic blocks that dominate the specified
79 inline const DomSetType &getDominators(BasicBlock *BB) const {
80 const_iterator I = find(BB);
81 assert(I != end() && "BB not in function!");
85 /// isReachable - Return true if the specified basicblock is reachable. If
86 /// the block is reachable, we have dominator set information for it.
87 bool isReachable(BasicBlock *BB) const {
88 return !getDominators(BB).empty();
91 /// dominates - Return true if A dominates B.
93 inline bool dominates(BasicBlock *A, BasicBlock *B) const {
94 return getDominators(B).count(A) != 0;
97 /// properlyDominates - Return true if A dominates B and A != B.
99 bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
100 return dominates(A, B) && A != B;
103 /// print - Convert to human readable form
104 virtual void print(std::ostream &OS) const;
106 /// dominates - Return true if A dominates B. This performs the special
107 /// checks necessary if A and B are in the same basic block.
109 bool dominates(Instruction *A, Instruction *B) const;
111 //===--------------------------------------------------------------------===//
112 // API to update (Post)DominatorSet information based on modifications to
115 /// addBasicBlock - Call to update the dominator set with information about a
116 /// new block that was inserted into the function.
117 void addBasicBlock(BasicBlock *BB, const DomSetType &Dominators) {
118 assert(find(BB) == end() && "Block already in DominatorSet!");
119 Doms.insert(std::make_pair(BB, Dominators));
122 // addDominator - If a new block is inserted into the CFG, then method may be
123 // called to notify the blocks it dominates that it is in their set.
125 void addDominator(BasicBlock *BB, BasicBlock *NewDominator) {
126 iterator I = find(BB);
127 assert(I != end() && "BB is not in DominatorSet!");
128 I->second.insert(NewDominator);
133 //===-------------------------------------
134 // DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
135 // compute a normal dominator set.
137 struct DominatorSet : public DominatorSetBase {
138 DominatorSet() : DominatorSetBase(false) {}
140 virtual bool runOnFunction(Function &F);
142 /// recalculate - This method may be called by external passes that modify the
143 /// CFG and then need dominator information recalculated. This method is
144 /// obviously really slow, so it should be avoided if at all possible.
147 // getAnalysisUsage - This simply provides a dominator set
148 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
149 AU.setPreservesAll();
152 void calculateDominatorsFromBlock(BasicBlock *BB);
156 //===----------------------------------------------------------------------===//
158 // ImmediateDominators - Calculate the immediate dominator for each node in a
161 class ImmediateDominatorsBase : public DominatorBase {
163 std::map<BasicBlock*, BasicBlock*> IDoms;
164 void calcIDoms(const DominatorSetBase &DS);
166 ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {}
168 virtual void releaseMemory() { IDoms.clear(); }
170 // Accessor interface:
171 typedef std::map<BasicBlock*, BasicBlock*> IDomMapType;
172 typedef IDomMapType::const_iterator const_iterator;
173 inline const_iterator begin() const { return IDoms.begin(); }
174 inline const_iterator end() const { return IDoms.end(); }
175 inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);}
177 // operator[] - Return the idom for the specified basic block. The start
178 // node returns null, because it does not have an immediate dominator.
180 inline BasicBlock *operator[](BasicBlock *BB) const {
184 // get() - Synonym for operator[].
185 inline BasicBlock *get(BasicBlock *BB) const {
186 std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
187 return I != IDoms.end() ? I->second : 0;
190 //===--------------------------------------------------------------------===//
191 // API to update Immediate(Post)Dominators information based on modifications
194 /// addNewBlock - Add a new block to the CFG, with the specified immediate
197 void addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
198 assert(get(BB) == 0 && "BasicBlock already in idom info!");
202 /// setImmediateDominator - Update the immediate dominator information to
203 /// change the current immediate dominator for the specified block to another
204 /// block. This method requires that BB already have an IDom, otherwise just
206 void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) {
207 assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!");
211 // print - Convert to human readable form
212 virtual void print(std::ostream &OS) const;
215 //===-------------------------------------
216 // ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase that
217 // is used to compute a normal immediate dominator set.
219 struct ImmediateDominators : public ImmediateDominatorsBase {
220 ImmediateDominators() : ImmediateDominatorsBase(false) {}
222 virtual bool runOnFunction(Function &F) {
223 IDoms.clear(); // Reset from the last time we were run...
224 DominatorSet &DS = getAnalysis<DominatorSet>();
230 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
231 AU.setPreservesAll();
232 AU.addRequired<DominatorSet>();
237 //===----------------------------------------------------------------------===//
239 // DominatorTree - Calculate the immediate dominator tree for a function.
241 class DominatorTreeBase : public DominatorBase {
247 std::map<BasicBlock*, Node*> Nodes;
249 typedef std::map<BasicBlock*, Node*> NodeMapType;
252 friend class DominatorTree;
253 friend class PostDominatorTree;
254 friend class DominatorTreeBase;
257 std::vector<Node*> Children;
259 typedef std::vector<Node*>::iterator iterator;
260 typedef std::vector<Node*>::const_iterator const_iterator;
262 iterator begin() { return Children.begin(); }
263 iterator end() { return Children.end(); }
264 const_iterator begin() const { return Children.begin(); }
265 const_iterator end() const { return Children.end(); }
267 inline BasicBlock *getNode() const { return TheNode; }
268 inline Node2 *getIDom() const { return IDom; }
269 inline const std::vector<Node*> &getChildren() const { return Children; }
271 // dominates - Returns true iff this dominates N. Note that this is not a
272 // constant time operation!
273 inline bool dominates(const Node2 *N) const {
275 while ((IDom = N->getIDom()) != 0 && IDom != this)
276 N = IDom; // Walk up the tree
281 inline Node2(BasicBlock *node, Node *iDom)
282 : TheNode(node), IDom(iDom) {}
283 inline Node2 *addChild(Node *C) { Children.push_back(C); return C; }
285 void setIDom(Node2 *NewIDom);
289 DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {}
290 ~DominatorTreeBase() { reset(); }
292 virtual void releaseMemory() { reset(); }
294 /// getNode - return the (Post)DominatorTree node for the specified basic
295 /// block. This is the same as using operator[] on this class.
297 inline Node *getNode(BasicBlock *BB) const {
298 NodeMapType::const_iterator i = Nodes.find(BB);
299 return (i != Nodes.end()) ? i->second : 0;
302 inline Node *operator[](BasicBlock *BB) const {
306 //===--------------------------------------------------------------------===// // API to update (Post)DominatorTree information based on modifications to
309 /// createNewNode - Add a new node to the dominator tree information. This
310 /// creates a new node as a child of IDomNode, linking it into the children
311 /// list of the immediate dominator.
313 Node *createNewNode(BasicBlock *BB, Node *IDomNode) {
314 assert(getNode(BB) == 0 && "Block already in dominator tree!");
315 assert(IDomNode && "Not immediate dominator specified for block!");
316 return Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
319 /// changeImmediateDominator - This method is used to update the dominator
320 /// tree information when a node's immediate dominator changes.
322 void changeImmediateDominator(Node *Node, Node *NewIDom) {
323 assert(Node && NewIDom && "Cannot change null node pointers!");
324 Node->setIDom(NewIDom);
327 /// print - Convert to human readable form
328 virtual void print(std::ostream &OS) const;
332 //===-------------------------------------
333 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
334 // compute a normal dominator tree.
336 struct DominatorTree : public DominatorTreeBase {
337 DominatorTree() : DominatorTreeBase(false) {}
339 virtual bool runOnFunction(Function &F) {
340 reset(); // Reset from the last time we were run...
341 DominatorSet &DS = getAnalysis<DominatorSet>();
347 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
348 AU.setPreservesAll();
349 AU.addRequired<DominatorSet>();
352 void calculate(const DominatorSet &DS);
355 //===-------------------------------------
356 // DominatorTree GraphTraits specialization so the DominatorTree can be
357 // iterable by generic graph iterators.
359 template <> struct GraphTraits<DominatorTree::Node*> {
360 typedef DominatorTree::Node NodeType;
361 typedef NodeType::iterator ChildIteratorType;
363 static NodeType *getEntryNode(NodeType *N) {
366 static inline ChildIteratorType child_begin(NodeType* N) {
369 static inline ChildIteratorType child_end(NodeType* N) {
374 template <> struct GraphTraits<DominatorTree*>
375 : public GraphTraits<DominatorTree::Node*> {
376 static NodeType *getEntryNode(DominatorTree *DT) {
377 return DT->getNode(DT->getRoot());
381 //===----------------------------------------------------------------------===//
383 // DominanceFrontier - Calculate the dominance frontiers for a function.
385 class DominanceFrontierBase : public DominatorBase {
387 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
388 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
390 DomSetMapType Frontiers;
392 DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {}
394 virtual void releaseMemory() { Frontiers.clear(); }
396 // Accessor interface:
397 typedef DomSetMapType::iterator iterator;
398 typedef DomSetMapType::const_iterator const_iterator;
399 iterator begin() { return Frontiers.begin(); }
400 const_iterator begin() const { return Frontiers.begin(); }
401 iterator end() { return Frontiers.end(); }
402 const_iterator end() const { return Frontiers.end(); }
403 iterator find(BasicBlock *B) { return Frontiers.find(B); }
404 const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
406 void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
407 assert(find(BB) == end() && "Block already in DominanceFrontier!");
408 Frontiers.insert(std::make_pair(BB, frontier));
411 void addToFrontier(iterator I, BasicBlock *Node) {
412 assert(I != end() && "BB is not in DominanceFrontier!");
413 I->second.insert(Node);
416 void removeFromFrontier(iterator I, BasicBlock *Node) {
417 assert(I != end() && "BB is not in DominanceFrontier!");
418 assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
419 I->second.erase(Node);
422 // print - Convert to human readable form
423 virtual void print(std::ostream &OS) const;
427 //===-------------------------------------
428 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
429 // compute a normal dominator tree.
431 struct DominanceFrontier : public DominanceFrontierBase {
432 DominanceFrontier() : DominanceFrontierBase(false) {}
434 virtual bool runOnFunction(Function &) {
436 DominatorTree &DT = getAnalysis<DominatorTree>();
438 calculate(DT, DT[Root]);
442 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
443 AU.setPreservesAll();
444 AU.addRequired<DominatorTree>();
447 const DomSetType &calculate(const DominatorTree &DT,
448 const DominatorTree::Node *Node);