1 //===- llvm/Analysis/Dominators.h - Dominator Info Calculation --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the following classes:
11 // 1. DominatorSet: Calculates the [reverse] dominator set for a function
12 // 2. ImmediateDominators: Calculates and holds a mapping between BasicBlocks
13 // and their immediate dominator.
14 // 3. DominatorTree: Represent the ImmediateDominator as an explicit tree
16 // 4. DominanceFrontier: Calculate and hold the dominance frontier for a
19 // These data structures are listed in increasing order of complexity. It
20 // takes longer to calculate the dominator frontier, for example, than the
21 // ImmediateDominator mapping.
23 //===----------------------------------------------------------------------===//
25 #ifndef LLVM_ANALYSIS_DOMINATORS_H
26 #define LLVM_ANALYSIS_DOMINATORS_H
28 #include "llvm/Pass.h"
33 template <typename GraphType> struct GraphTraits;
35 //===----------------------------------------------------------------------===//
37 // DominatorBase - Base class that other, more interesting dominator analyses
40 class DominatorBase : public FunctionPass {
42 std::vector<BasicBlock*> Roots;
43 const bool IsPostDominators;
45 inline DominatorBase(bool isPostDom) : Roots(), IsPostDominators(isPostDom) {}
47 // Return the root blocks of the current CFG. This may include multiple
48 // blocks if we are computing post dominators. For forward dominators, this
49 // will always be a single block (the entry node).
50 inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
52 // Returns true if analysis based of postdoms
53 bool isPostDominator() const { return IsPostDominators; }
56 //===----------------------------------------------------------------------===//
58 // DominatorSet - Maintain a set<BasicBlock*> for every basic block in a
59 // function, that represents the blocks that dominate the block. If the block
60 // is unreachable in this function, the set will be empty. This cannot happen
61 // for reachable code, because every block dominates at least itself.
63 struct DominatorSetBase : public DominatorBase {
64 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
66 typedef std::map<BasicBlock*, DomSetType> DomSetMapType;
70 DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {}
72 virtual void releaseMemory() { Doms.clear(); }
74 // Accessor interface:
75 typedef DomSetMapType::const_iterator const_iterator;
76 typedef DomSetMapType::iterator iterator;
77 inline const_iterator begin() const { return Doms.begin(); }
78 inline iterator begin() { return Doms.begin(); }
79 inline const_iterator end() const { return Doms.end(); }
80 inline iterator end() { return Doms.end(); }
81 inline const_iterator find(BasicBlock* B) const { return Doms.find(B); }
82 inline iterator find(BasicBlock* B) { return Doms.find(B); }
85 /// getDominators - Return the set of basic blocks that dominate the specified
88 inline const DomSetType &getDominators(BasicBlock *BB) const {
89 const_iterator I = find(BB);
90 assert(I != end() && "BB not in function!");
94 /// isReachable - Return true if the specified basicblock is reachable. If
95 /// the block is reachable, we have dominator set information for it.
96 bool isReachable(BasicBlock *BB) const {
97 return !getDominators(BB).empty();
100 /// dominates - Return true if A dominates B.
102 inline bool dominates(BasicBlock *A, BasicBlock *B) const {
103 return getDominators(B).count(A) != 0;
106 /// properlyDominates - Return true if A dominates B and A != B.
108 bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
109 return dominates(A, B) && A != B;
112 /// print - Convert to human readable form
113 virtual void print(std::ostream &OS) const;
115 /// dominates - Return true if A dominates B. This performs the special
116 /// checks necessary if A and B are in the same basic block.
118 bool dominates(Instruction *A, Instruction *B) const;
120 //===--------------------------------------------------------------------===//
121 // API to update (Post)DominatorSet information based on modifications to
124 /// addBasicBlock - Call to update the dominator set with information about a
125 /// new block that was inserted into the function.
126 void addBasicBlock(BasicBlock *BB, const DomSetType &Dominators) {
127 assert(find(BB) == end() && "Block already in DominatorSet!");
128 Doms.insert(std::make_pair(BB, Dominators));
131 // addDominator - If a new block is inserted into the CFG, then method may be
132 // called to notify the blocks it dominates that it is in their set.
134 void addDominator(BasicBlock *BB, BasicBlock *NewDominator) {
135 iterator I = find(BB);
136 assert(I != end() && "BB is not in DominatorSet!");
137 I->second.insert(NewDominator);
142 //===-------------------------------------
143 // DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
144 // compute a normal dominator set.
146 struct DominatorSet : public DominatorSetBase {
147 DominatorSet() : DominatorSetBase(false) {}
149 virtual bool runOnFunction(Function &F);
151 /// recalculate - This method may be called by external passes that modify the
152 /// CFG and then need dominator information recalculated. This method is
153 /// obviously really slow, so it should be avoided if at all possible.
156 BasicBlock *getRoot() const {
157 assert(Roots.size() == 1 && "Should always have entry node!");
161 // getAnalysisUsage - This simply provides a dominator set
162 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
163 AU.setPreservesAll();
166 void calculateDominatorsFromBlock(BasicBlock *BB);
170 //===----------------------------------------------------------------------===//
172 // ImmediateDominators - Calculate the immediate dominator for each node in a
175 class ImmediateDominatorsBase : public DominatorBase {
177 std::map<BasicBlock*, BasicBlock*> IDoms;
178 void calcIDoms(const DominatorSetBase &DS);
180 ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {}
182 virtual void releaseMemory() { IDoms.clear(); }
184 // Accessor interface:
185 typedef std::map<BasicBlock*, BasicBlock*> IDomMapType;
186 typedef IDomMapType::const_iterator const_iterator;
187 inline const_iterator begin() const { return IDoms.begin(); }
188 inline const_iterator end() const { return IDoms.end(); }
189 inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);}
191 // operator[] - Return the idom for the specified basic block. The start
192 // node returns null, because it does not have an immediate dominator.
194 inline BasicBlock *operator[](BasicBlock *BB) const {
198 // get() - Synonym for operator[].
199 inline BasicBlock *get(BasicBlock *BB) const {
200 std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
201 return I != IDoms.end() ? I->second : 0;
204 //===--------------------------------------------------------------------===//
205 // API to update Immediate(Post)Dominators information based on modifications
208 /// addNewBlock - Add a new block to the CFG, with the specified immediate
211 void addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
212 assert(get(BB) == 0 && "BasicBlock already in idom info!");
216 /// setImmediateDominator - Update the immediate dominator information to
217 /// change the current immediate dominator for the specified block to another
218 /// block. This method requires that BB already have an IDom, otherwise just
220 void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) {
221 assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!");
225 // print - Convert to human readable form
226 virtual void print(std::ostream &OS) const;
229 //===-------------------------------------
230 // ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase that
231 // is used to compute a normal immediate dominator set.
233 struct ImmediateDominators : public ImmediateDominatorsBase {
234 ImmediateDominators() : ImmediateDominatorsBase(false) {}
236 BasicBlock *getRoot() const {
237 assert(Roots.size() == 1 && "Should always have entry node!");
241 virtual bool runOnFunction(Function &F) {
242 IDoms.clear(); // Reset from the last time we were run...
243 DominatorSet &DS = getAnalysis<DominatorSet>();
244 Roots = DS.getRoots();
249 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
250 AU.setPreservesAll();
251 AU.addRequired<DominatorSet>();
256 //===----------------------------------------------------------------------===//
258 // DominatorTree - Calculate the immediate dominator tree for a function.
260 struct DominatorTreeBase : public DominatorBase {
263 std::map<BasicBlock*, Node*> Nodes;
265 typedef std::map<BasicBlock*, Node*> NodeMapType;
270 friend class DominatorTree;
271 friend class PostDominatorTree;
272 friend class DominatorTreeBase;
275 std::vector<Node*> Children;
277 typedef std::vector<Node*>::iterator iterator;
278 typedef std::vector<Node*>::const_iterator const_iterator;
280 iterator begin() { return Children.begin(); }
281 iterator end() { return Children.end(); }
282 const_iterator begin() const { return Children.begin(); }
283 const_iterator end() const { return Children.end(); }
285 inline BasicBlock *getBlock() const { return TheBB; }
286 inline Node *getIDom() const { return IDom; }
287 inline const std::vector<Node*> &getChildren() const { return Children; }
289 // dominates - Returns true iff this dominates N. Note that this is not a
290 // constant time operation!
291 inline bool dominates(const Node *N) const {
293 while ((IDom = N->getIDom()) != 0 && IDom != this)
294 N = IDom; // Walk up the tree
299 inline Node(BasicBlock *BB, Node *iDom)
300 : TheBB(BB), IDom(iDom) {}
301 inline Node *addChild(Node *C) { Children.push_back(C); return C; }
303 void setIDom(Node *NewIDom);
307 DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {}
308 ~DominatorTreeBase() { reset(); }
310 virtual void releaseMemory() { reset(); }
312 /// getNode - return the (Post)DominatorTree node for the specified basic
313 /// block. This is the same as using operator[] on this class.
315 inline Node *getNode(BasicBlock *BB) const {
316 NodeMapType::const_iterator i = Nodes.find(BB);
317 return (i != Nodes.end()) ? i->second : 0;
320 inline Node *operator[](BasicBlock *BB) const {
324 // getRootNode - This returns the entry node for the CFG of the function. If
325 // this tree represents the post-dominance relations for a function, however,
326 // this root may be a node with the block == NULL. This is the case when
327 // there are multiple exit nodes from a particular function. Consumers of
328 // post-dominance information must be capable of dealing with this
331 Node *getRootNode() { return RootNode; }
332 const Node *getRootNode() const { return RootNode; }
334 //===--------------------------------------------------------------------===//
335 // API to update (Post)DominatorTree information based on modifications to
338 /// createNewNode - Add a new node to the dominator tree information. This
339 /// creates a new node as a child of IDomNode, linking it into the children
340 /// list of the immediate dominator.
342 Node *createNewNode(BasicBlock *BB, Node *IDomNode) {
343 assert(getNode(BB) == 0 && "Block already in dominator tree!");
344 assert(IDomNode && "Not immediate dominator specified for block!");
345 return Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
348 /// changeImmediateDominator - This method is used to update the dominator
349 /// tree information when a node's immediate dominator changes.
351 void changeImmediateDominator(Node *Node, Node *NewIDom) {
352 assert(Node && NewIDom && "Cannot change null node pointers!");
353 Node->setIDom(NewIDom);
356 /// print - Convert to human readable form
357 virtual void print(std::ostream &OS) const;
361 //===-------------------------------------
362 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
363 // compute a normal dominator tree.
365 struct DominatorTree : public DominatorTreeBase {
366 DominatorTree() : DominatorTreeBase(false) {}
368 BasicBlock *getRoot() const {
369 assert(Roots.size() == 1 && "Should always have entry node!");
373 virtual bool runOnFunction(Function &F) {
374 reset(); // Reset from the last time we were run...
375 DominatorSet &DS = getAnalysis<DominatorSet>();
376 Roots = DS.getRoots();
381 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
382 AU.setPreservesAll();
383 AU.addRequired<DominatorSet>();
386 void calculate(const DominatorSet &DS);
389 //===-------------------------------------
390 // DominatorTree GraphTraits specialization so the DominatorTree can be
391 // iterable by generic graph iterators.
393 template <> struct GraphTraits<DominatorTree::Node*> {
394 typedef DominatorTree::Node NodeType;
395 typedef NodeType::iterator ChildIteratorType;
397 static NodeType *getEntryNode(NodeType *N) {
400 static inline ChildIteratorType child_begin(NodeType* N) {
403 static inline ChildIteratorType child_end(NodeType* N) {
408 template <> struct GraphTraits<DominatorTree*>
409 : public GraphTraits<DominatorTree::Node*> {
410 static NodeType *getEntryNode(DominatorTree *DT) {
411 return DT->getRootNode();
415 //===----------------------------------------------------------------------===//
417 // DominanceFrontier - Calculate the dominance frontiers for a function.
419 struct DominanceFrontierBase : public DominatorBase {
420 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
421 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
423 DomSetMapType Frontiers;
425 DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {}
427 virtual void releaseMemory() { Frontiers.clear(); }
429 // Accessor interface:
430 typedef DomSetMapType::iterator iterator;
431 typedef DomSetMapType::const_iterator const_iterator;
432 iterator begin() { return Frontiers.begin(); }
433 const_iterator begin() const { return Frontiers.begin(); }
434 iterator end() { return Frontiers.end(); }
435 const_iterator end() const { return Frontiers.end(); }
436 iterator find(BasicBlock *B) { return Frontiers.find(B); }
437 const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
439 void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
440 assert(find(BB) == end() && "Block already in DominanceFrontier!");
441 Frontiers.insert(std::make_pair(BB, frontier));
444 void addToFrontier(iterator I, BasicBlock *Node) {
445 assert(I != end() && "BB is not in DominanceFrontier!");
446 I->second.insert(Node);
449 void removeFromFrontier(iterator I, BasicBlock *Node) {
450 assert(I != end() && "BB is not in DominanceFrontier!");
451 assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
452 I->second.erase(Node);
455 // print - Convert to human readable form
456 virtual void print(std::ostream &OS) const;
460 //===-------------------------------------
461 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
462 // compute a normal dominator tree.
464 struct DominanceFrontier : public DominanceFrontierBase {
465 DominanceFrontier() : DominanceFrontierBase(false) {}
467 BasicBlock *getRoot() const {
468 assert(Roots.size() == 1 && "Should always have entry node!");
472 virtual bool runOnFunction(Function &) {
474 DominatorTree &DT = getAnalysis<DominatorTree>();
475 Roots = DT.getRoots();
476 assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
477 calculate(DT, DT[Roots[0]]);
481 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
482 AU.setPreservesAll();
483 AU.addRequired<DominatorTree>();
486 const DomSetType &calculate(const DominatorTree &DT,
487 const DominatorTree::Node *Node);