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. ImmediateDominators: Calculates and holds a mapping between BasicBlocks
12 // and their immediate dominator.
13 // 2. DominatorSet: Calculates the [reverse] dominator set for a function
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"
35 template <typename GraphType> struct GraphTraits;
37 //===----------------------------------------------------------------------===//
38 /// DominatorBase - Base class that other, more interesting dominator analyses
41 class DominatorBase : public FunctionPass {
43 std::vector<BasicBlock*> Roots;
44 const bool IsPostDominators;
46 inline DominatorBase(bool isPostDom) : Roots(), IsPostDominators(isPostDom) {}
48 /// getRoots - Return the root blocks of the current CFG. This may include
49 /// multiple blocks if we are computing post dominators. For forward
50 /// dominators, this will always be a single block (the entry node).
52 inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
54 /// isPostDominator - Returns true if analysis based of postdoms
56 bool isPostDominator() const { return IsPostDominators; }
60 //===----------------------------------------------------------------------===//
61 /// ImmediateDominators - Calculate the immediate dominator for each node in a
64 class ImmediateDominatorsBase : public DominatorBase {
66 std::map<BasicBlock*, BasicBlock*> IDoms;
68 ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {}
70 virtual void releaseMemory() { IDoms.clear(); }
72 // Accessor interface:
73 typedef std::map<BasicBlock*, BasicBlock*> IDomMapType;
74 typedef IDomMapType::const_iterator const_iterator;
75 inline const_iterator begin() const { return IDoms.begin(); }
76 inline const_iterator end() const { return IDoms.end(); }
77 inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);}
79 /// operator[] - Return the idom for the specified basic block. The start
80 /// node returns null, because it does not have an immediate dominator.
82 inline BasicBlock *operator[](BasicBlock *BB) const {
86 /// get() - Synonym for operator[].
88 inline BasicBlock *get(BasicBlock *BB) const {
89 std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
90 return I != IDoms.end() ? I->second : 0;
93 //===--------------------------------------------------------------------===//
94 // API to update Immediate(Post)Dominators information based on modifications
97 /// addNewBlock - Add a new block to the CFG, with the specified immediate
100 void addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
101 assert(get(BB) == 0 && "BasicBlock already in idom info!");
105 /// setImmediateDominator - Update the immediate dominator information to
106 /// change the current immediate dominator for the specified block to another
107 /// block. This method requires that BB already have an IDom, otherwise just
110 void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) {
111 assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!");
115 /// print - Convert to human readable form
117 virtual void print(std::ostream &OS, const Module* = 0) const;
120 //===-------------------------------------
121 /// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase
122 /// that is used to compute a normal immediate dominator set.
124 struct ImmediateDominators : public ImmediateDominatorsBase {
125 ImmediateDominators() : ImmediateDominatorsBase(false) {}
127 BasicBlock *getRoot() const {
128 assert(Roots.size() == 1 && "Should always have entry node!");
132 virtual bool runOnFunction(Function &F);
134 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
135 AU.setPreservesAll();
142 BasicBlock *Label, *Parent, *Child, *Ancestor;
144 std::vector<BasicBlock*> Bucket;
146 InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){}
149 // Vertex - Map the DFS number to the BasicBlock*
150 std::vector<BasicBlock*> Vertex;
152 // Info - Collection of information used during the computation of idoms.
153 std::map<BasicBlock*, InfoRec> Info;
155 unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N);
156 void Compress(BasicBlock *V, InfoRec &VInfo);
157 BasicBlock *Eval(BasicBlock *v);
158 void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
163 //===----------------------------------------------------------------------===//
164 /// DominatorSet - Maintain a set<BasicBlock*> for every basic block in a
165 /// function, that represents the blocks that dominate the block. If the block
166 /// is unreachable in this function, the set will be empty. This cannot happen
167 /// for reachable code, because every block dominates at least itself.
169 struct DominatorSetBase : public DominatorBase {
170 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
172 typedef std::map<BasicBlock*, DomSetType> DomSetMapType;
176 DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {}
178 virtual void releaseMemory() { Doms.clear(); }
180 // Accessor interface:
181 typedef DomSetMapType::const_iterator const_iterator;
182 typedef DomSetMapType::iterator iterator;
183 inline const_iterator begin() const { return Doms.begin(); }
184 inline iterator begin() { return Doms.begin(); }
185 inline const_iterator end() const { return Doms.end(); }
186 inline iterator end() { return Doms.end(); }
187 inline const_iterator find(BasicBlock* B) const { return Doms.find(B); }
188 inline iterator find(BasicBlock* B) { return Doms.find(B); }
191 /// getDominators - Return the set of basic blocks that dominate the specified
194 inline const DomSetType &getDominators(BasicBlock *BB) const {
195 const_iterator I = find(BB);
196 assert(I != end() && "BB not in function!");
200 /// isReachable - Return true if the specified basicblock is reachable. If
201 /// the block is reachable, we have dominator set information for it.
203 bool isReachable(BasicBlock *BB) const {
204 return !getDominators(BB).empty();
207 /// dominates - Return true if A dominates B.
209 inline bool dominates(BasicBlock *A, BasicBlock *B) const {
210 return getDominators(B).count(A) != 0;
213 /// properlyDominates - Return true if A dominates B and A != B.
215 bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
216 return dominates(A, B) && A != B;
219 /// print - Convert to human readable form
221 virtual void print(std::ostream &OS, const Module* = 0) const;
223 /// dominates - Return true if A dominates B. This performs the special
224 /// checks necessary if A and B are in the same basic block.
226 bool dominates(Instruction *A, Instruction *B) const;
228 //===--------------------------------------------------------------------===//
229 // API to update (Post)DominatorSet information based on modifications to
232 /// addBasicBlock - Call to update the dominator set with information about a
233 /// new block that was inserted into the function.
235 void addBasicBlock(BasicBlock *BB, const DomSetType &Dominators) {
236 assert(find(BB) == end() && "Block already in DominatorSet!");
237 Doms.insert(std::make_pair(BB, Dominators));
240 /// addDominator - If a new block is inserted into the CFG, then method may be
241 /// called to notify the blocks it dominates that it is in their set.
243 void addDominator(BasicBlock *BB, BasicBlock *NewDominator) {
244 iterator I = find(BB);
245 assert(I != end() && "BB is not in DominatorSet!");
246 I->second.insert(NewDominator);
251 //===-------------------------------------
252 /// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
253 /// compute a normal dominator set.
255 struct DominatorSet : public DominatorSetBase {
256 DominatorSet() : DominatorSetBase(false) {}
258 virtual bool runOnFunction(Function &F);
260 BasicBlock *getRoot() const {
261 assert(Roots.size() == 1 && "Should always have entry node!");
265 /// getAnalysisUsage - This simply provides a dominator set
267 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
268 AU.addRequired<ImmediateDominators>();
269 AU.setPreservesAll();
272 // stub - dummy function, just ignore it
277 //===----------------------------------------------------------------------===//
278 /// DominatorTree - Calculate the immediate dominator tree for a function.
280 struct DominatorTreeBase : public DominatorBase {
283 std::map<BasicBlock*, Node*> Nodes;
285 typedef std::map<BasicBlock*, Node*> NodeMapType;
290 friend struct DominatorTree;
291 friend struct PostDominatorTree;
292 friend struct DominatorTreeBase;
295 std::vector<Node*> Children;
297 typedef std::vector<Node*>::iterator iterator;
298 typedef std::vector<Node*>::const_iterator const_iterator;
300 iterator begin() { return Children.begin(); }
301 iterator end() { return Children.end(); }
302 const_iterator begin() const { return Children.begin(); }
303 const_iterator end() const { return Children.end(); }
305 inline BasicBlock *getBlock() const { return TheBB; }
306 inline Node *getIDom() const { return IDom; }
307 inline const std::vector<Node*> &getChildren() const { return Children; }
309 /// dominates - Returns true iff this dominates N. Note that this is not a
310 /// constant time operation!
312 inline bool dominates(const Node *N) const {
314 while ((IDom = N->getIDom()) != 0 && IDom != this)
315 N = IDom; // Walk up the tree
320 inline Node(BasicBlock *BB, Node *iDom) : TheBB(BB), IDom(iDom) {}
321 inline Node *addChild(Node *C) { Children.push_back(C); return C; }
323 void setIDom(Node *NewIDom);
327 DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {}
328 ~DominatorTreeBase() { reset(); }
330 virtual void releaseMemory() { reset(); }
332 /// getNode - return the (Post)DominatorTree node for the specified basic
333 /// block. This is the same as using operator[] on this class.
335 inline Node *getNode(BasicBlock *BB) const {
336 NodeMapType::const_iterator i = Nodes.find(BB);
337 return (i != Nodes.end()) ? i->second : 0;
340 inline Node *operator[](BasicBlock *BB) const {
344 /// getRootNode - This returns the entry node for the CFG of the function. If
345 /// this tree represents the post-dominance relations for a function, however,
346 /// this root may be a node with the block == NULL. This is the case when
347 /// there are multiple exit nodes from a particular function. Consumers of
348 /// post-dominance information must be capable of dealing with this
351 Node *getRootNode() { return RootNode; }
352 const Node *getRootNode() const { return RootNode; }
354 //===--------------------------------------------------------------------===//
355 // API to update (Post)DominatorTree information based on modifications to
358 /// createNewNode - Add a new node to the dominator tree information. This
359 /// creates a new node as a child of IDomNode, linking it into the children
360 /// list of the immediate dominator.
362 Node *createNewNode(BasicBlock *BB, Node *IDomNode) {
363 assert(getNode(BB) == 0 && "Block already in dominator tree!");
364 assert(IDomNode && "Not immediate dominator specified for block!");
365 return Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
368 /// changeImmediateDominator - This method is used to update the dominator
369 /// tree information when a node's immediate dominator changes.
371 void changeImmediateDominator(Node *N, Node *NewIDom) {
372 assert(N && NewIDom && "Cannot change null node pointers!");
376 /// print - Convert to human readable form
378 virtual void print(std::ostream &OS, const Module* = 0) const;
382 //===-------------------------------------
383 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
384 /// compute a normal dominator tree.
386 struct DominatorTree : public DominatorTreeBase {
387 DominatorTree() : DominatorTreeBase(false) {}
389 BasicBlock *getRoot() const {
390 assert(Roots.size() == 1 && "Should always have entry node!");
394 virtual bool runOnFunction(Function &F) {
395 reset(); // Reset from the last time we were run...
396 ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
397 Roots = ID.getRoots();
402 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
403 AU.setPreservesAll();
404 AU.addRequired<ImmediateDominators>();
407 void calculate(const ImmediateDominators &ID);
408 Node *getNodeForBlock(BasicBlock *BB);
411 //===-------------------------------------
412 /// DominatorTree GraphTraits specialization so the DominatorTree can be
413 /// iterable by generic graph iterators.
415 template <> struct GraphTraits<DominatorTree::Node*> {
416 typedef DominatorTree::Node NodeType;
417 typedef NodeType::iterator ChildIteratorType;
419 static NodeType *getEntryNode(NodeType *N) {
422 static inline ChildIteratorType child_begin(NodeType* N) {
425 static inline ChildIteratorType child_end(NodeType* N) {
430 template <> struct GraphTraits<DominatorTree*>
431 : public GraphTraits<DominatorTree::Node*> {
432 static NodeType *getEntryNode(DominatorTree *DT) {
433 return DT->getRootNode();
437 //===----------------------------------------------------------------------===//
438 /// DominanceFrontier - Calculate the dominance frontiers for a function.
440 struct DominanceFrontierBase : public DominatorBase {
441 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
442 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
444 DomSetMapType Frontiers;
446 DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {}
448 virtual void releaseMemory() { Frontiers.clear(); }
450 // Accessor interface:
451 typedef DomSetMapType::iterator iterator;
452 typedef DomSetMapType::const_iterator const_iterator;
453 iterator begin() { return Frontiers.begin(); }
454 const_iterator begin() const { return Frontiers.begin(); }
455 iterator end() { return Frontiers.end(); }
456 const_iterator end() const { return Frontiers.end(); }
457 iterator find(BasicBlock *B) { return Frontiers.find(B); }
458 const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
460 void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
461 assert(find(BB) == end() && "Block already in DominanceFrontier!");
462 Frontiers.insert(std::make_pair(BB, frontier));
465 void addToFrontier(iterator I, BasicBlock *Node) {
466 assert(I != end() && "BB is not in DominanceFrontier!");
467 I->second.insert(Node);
470 void removeFromFrontier(iterator I, BasicBlock *Node) {
471 assert(I != end() && "BB is not in DominanceFrontier!");
472 assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
473 I->second.erase(Node);
476 /// print - Convert to human readable form
478 virtual void print(std::ostream &OS, const Module* = 0) const;
482 //===-------------------------------------
483 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
484 /// compute a normal dominator tree.
486 struct DominanceFrontier : public DominanceFrontierBase {
487 DominanceFrontier() : DominanceFrontierBase(false) {}
489 BasicBlock *getRoot() const {
490 assert(Roots.size() == 1 && "Should always have entry node!");
494 virtual bool runOnFunction(Function &) {
496 DominatorTree &DT = getAnalysis<DominatorTree>();
497 Roots = DT.getRoots();
498 assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
499 calculate(DT, DT[Roots[0]]);
503 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
504 AU.setPreservesAll();
505 AU.addRequired<DominatorTree>();
508 const DomSetType &calculate(const DominatorTree &DT,
509 const DominatorTree::Node *Node);
512 // Make sure that any clients of this file link in Dominators.cpp
514 DOMINATORS_INCLUDE_FILE((void*)&DominatorSet::stub);
515 } // End llvm namespace