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. ETForest: Efficient data structure for dominance comparisons and
17 // nearest-common-ancestor queries.
18 // 5. DominanceFrontier: Calculate and hold the dominance frontier for a
21 // These data structures are listed in increasing order of complexity. It
22 // takes longer to calculate the dominator frontier, for example, than the
23 // ImmediateDominator mapping.
25 //===----------------------------------------------------------------------===//
27 #ifndef LLVM_ANALYSIS_DOMINATORS_H
28 #define LLVM_ANALYSIS_DOMINATORS_H
30 #include "llvm/Analysis/ET-Forest.h"
31 #include "llvm/Pass.h"
38 template <typename GraphType> struct GraphTraits;
40 //===----------------------------------------------------------------------===//
41 /// DominatorBase - Base class that other, more interesting dominator analyses
44 class DominatorBase : public FunctionPass {
46 std::vector<BasicBlock*> Roots;
47 const bool IsPostDominators;
49 inline DominatorBase(bool isPostDom) : Roots(), IsPostDominators(isPostDom) {}
51 /// getRoots - Return the root blocks of the current CFG. This may include
52 /// multiple blocks if we are computing post dominators. For forward
53 /// dominators, this will always be a single block (the entry node).
55 inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
57 /// isPostDominator - Returns true if analysis based of postdoms
59 bool isPostDominator() const { return IsPostDominators; }
63 //===----------------------------------------------------------------------===//
64 /// ImmediateDominators - Calculate the immediate dominator for each node in a
67 class ImmediateDominatorsBase : public DominatorBase {
72 BasicBlock *Label, *Parent, *Child, *Ancestor;
74 std::vector<BasicBlock*> Bucket;
76 InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){}
79 std::map<BasicBlock*, BasicBlock*> IDoms;
81 // Vertex - Map the DFS number to the BasicBlock*
82 std::vector<BasicBlock*> Vertex;
84 // Info - Collection of information used during the computation of idoms.
85 std::map<BasicBlock*, InfoRec> Info;
87 ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {}
89 virtual void releaseMemory() { IDoms.clear(); }
91 // Accessor interface:
92 typedef std::map<BasicBlock*, BasicBlock*> IDomMapType;
93 typedef IDomMapType::const_iterator const_iterator;
94 inline const_iterator begin() const { return IDoms.begin(); }
95 inline const_iterator end() const { return IDoms.end(); }
96 inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);}
98 /// operator[] - Return the idom for the specified basic block. The start
99 /// node returns null, because it does not have an immediate dominator.
101 inline BasicBlock *operator[](BasicBlock *BB) const {
105 /// get() - Synonym for operator[].
107 inline BasicBlock *get(BasicBlock *BB) const {
108 std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
109 return I != IDoms.end() ? I->second : 0;
112 //===--------------------------------------------------------------------===//
113 // API to update Immediate(Post)Dominators information based on modifications
116 /// addNewBlock - Add a new block to the CFG, with the specified immediate
119 void addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
120 assert(get(BB) == 0 && "BasicBlock already in idom info!");
124 /// setImmediateDominator - Update the immediate dominator information to
125 /// change the current immediate dominator for the specified block to another
126 /// block. This method requires that BB already have an IDom, otherwise just
129 void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) {
130 assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!");
134 /// print - Convert to human readable form
136 virtual void print(std::ostream &OS, const Module* = 0) const;
139 //===-------------------------------------
140 /// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase
141 /// that is used to compute a normal immediate dominator set.
143 class ImmediateDominators : public ImmediateDominatorsBase {
145 ImmediateDominators() : ImmediateDominatorsBase(false) {}
147 BasicBlock *getRoot() const {
148 assert(Roots.size() == 1 && "Should always have entry node!");
152 virtual bool runOnFunction(Function &F);
154 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
155 AU.setPreservesAll();
159 unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N);
160 void Compress(BasicBlock *V, InfoRec &VInfo);
161 BasicBlock *Eval(BasicBlock *v);
162 void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
167 //===----------------------------------------------------------------------===//
168 /// DominatorSet - Maintain a set<BasicBlock*> for every basic block in a
169 /// function, that represents the blocks that dominate the block. If the block
170 /// is unreachable in this function, the set will be empty. This cannot happen
171 /// for reachable code, because every block dominates at least itself.
173 class DominatorSetBase : public DominatorBase {
175 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
177 typedef std::map<BasicBlock*, DomSetType> DomSetMapType;
181 DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {}
183 virtual void releaseMemory() { Doms.clear(); }
185 // Accessor interface:
186 typedef DomSetMapType::const_iterator const_iterator;
187 typedef DomSetMapType::iterator iterator;
188 inline const_iterator begin() const { return Doms.begin(); }
189 inline iterator begin() { return Doms.begin(); }
190 inline const_iterator end() const { return Doms.end(); }
191 inline iterator end() { return Doms.end(); }
192 inline const_iterator find(BasicBlock* B) const { return Doms.find(B); }
193 inline iterator find(BasicBlock* B) { return Doms.find(B); }
196 /// getDominators - Return the set of basic blocks that dominate the specified
199 inline const DomSetType &getDominators(BasicBlock *BB) const {
200 const_iterator I = find(BB);
201 assert(I != end() && "BB not in function!");
205 /// isReachable - Return true if the specified basicblock is reachable. If
206 /// the block is reachable, we have dominator set information for it.
208 bool isReachable(BasicBlock *BB) const {
209 return !getDominators(BB).empty();
212 /// dominates - Return true if A dominates B.
214 inline bool dominates(BasicBlock *A, BasicBlock *B) const {
215 return getDominators(B).count(A) != 0;
218 /// properlyDominates - Return true if A dominates B and A != B.
220 bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
221 return dominates(A, B) && A != B;
224 /// print - Convert to human readable form
226 virtual void print(std::ostream &OS, const Module* = 0) const;
228 /// dominates - Return true if A dominates B. This performs the special
229 /// checks necessary if A and B are in the same basic block.
231 bool dominates(Instruction *A, Instruction *B) const;
233 //===--------------------------------------------------------------------===//
234 // API to update (Post)DominatorSet information based on modifications to
237 /// addBasicBlock - Call to update the dominator set with information about a
238 /// new block that was inserted into the function.
240 void addBasicBlock(BasicBlock *BB, const DomSetType &Dominators) {
241 assert(find(BB) == end() && "Block already in DominatorSet!");
242 Doms.insert(std::make_pair(BB, Dominators));
245 /// addDominator - If a new block is inserted into the CFG, then method may be
246 /// called to notify the blocks it dominates that it is in their set.
248 void addDominator(BasicBlock *BB, BasicBlock *NewDominator) {
249 iterator I = find(BB);
250 assert(I != end() && "BB is not in DominatorSet!");
251 I->second.insert(NewDominator);
256 //===-------------------------------------
257 /// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
258 /// compute a normal dominator set.
260 class DominatorSet : public DominatorSetBase {
262 DominatorSet() : DominatorSetBase(false) {}
264 virtual bool runOnFunction(Function &F);
266 BasicBlock *getRoot() const {
267 assert(Roots.size() == 1 && "Should always have entry node!");
271 /// getAnalysisUsage - This simply provides a dominator set
273 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
274 AU.addRequired<ImmediateDominators>();
275 AU.setPreservesAll();
278 // stub - dummy function, just ignore it
283 //===----------------------------------------------------------------------===//
284 /// DominatorTree - Calculate the immediate dominator tree for a function.
286 class DominatorTreeBase : public DominatorBase {
290 std::map<BasicBlock*, Node*> Nodes;
292 typedef std::map<BasicBlock*, Node*> NodeMapType;
297 friend struct DominatorTree;
298 friend struct PostDominatorTree;
299 friend struct DominatorTreeBase;
302 std::vector<Node*> Children;
304 typedef std::vector<Node*>::iterator iterator;
305 typedef std::vector<Node*>::const_iterator const_iterator;
307 iterator begin() { return Children.begin(); }
308 iterator end() { return Children.end(); }
309 const_iterator begin() const { return Children.begin(); }
310 const_iterator end() const { return Children.end(); }
312 inline BasicBlock *getBlock() const { return TheBB; }
313 inline Node *getIDom() const { return IDom; }
314 inline const std::vector<Node*> &getChildren() const { return Children; }
316 /// properlyDominates - Returns true iff this dominates N and this != N.
317 /// Note that this is not a constant time operation!
319 bool properlyDominates(const Node *N) const {
321 if (this == 0 || N == 0) return false;
322 while ((IDom = N->getIDom()) != 0 && IDom != this)
323 N = IDom; // Walk up the tree
327 /// dominates - Returns true iff this dominates N. Note that this is not a
328 /// constant time operation!
330 inline bool dominates(const Node *N) const {
331 if (N == this) return true; // A node trivially dominates itself.
332 return properlyDominates(N);
336 inline Node(BasicBlock *BB, Node *iDom) : TheBB(BB), IDom(iDom) {}
337 inline Node *addChild(Node *C) { Children.push_back(C); return C; }
339 void setIDom(Node *NewIDom);
343 DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {}
344 ~DominatorTreeBase() { reset(); }
346 virtual void releaseMemory() { reset(); }
348 /// getNode - return the (Post)DominatorTree node for the specified basic
349 /// block. This is the same as using operator[] on this class.
351 inline Node *getNode(BasicBlock *BB) const {
352 NodeMapType::const_iterator i = Nodes.find(BB);
353 return (i != Nodes.end()) ? i->second : 0;
356 inline Node *operator[](BasicBlock *BB) const {
360 /// getRootNode - This returns the entry node for the CFG of the function. If
361 /// this tree represents the post-dominance relations for a function, however,
362 /// this root may be a node with the block == NULL. This is the case when
363 /// there are multiple exit nodes from a particular function. Consumers of
364 /// post-dominance information must be capable of dealing with this
367 Node *getRootNode() { return RootNode; }
368 const Node *getRootNode() const { return RootNode; }
370 //===--------------------------------------------------------------------===//
371 // API to update (Post)DominatorTree information based on modifications to
374 /// createNewNode - Add a new node to the dominator tree information. This
375 /// creates a new node as a child of IDomNode, linking it into the children
376 /// list of the immediate dominator.
378 Node *createNewNode(BasicBlock *BB, Node *IDomNode) {
379 assert(getNode(BB) == 0 && "Block already in dominator tree!");
380 assert(IDomNode && "Not immediate dominator specified for block!");
381 return Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
384 /// changeImmediateDominator - This method is used to update the dominator
385 /// tree information when a node's immediate dominator changes.
387 void changeImmediateDominator(Node *N, Node *NewIDom) {
388 assert(N && NewIDom && "Cannot change null node pointers!");
392 /// print - Convert to human readable form
394 virtual void print(std::ostream &OS, const Module* = 0) const;
398 //===-------------------------------------
399 /// ET-Forest Class - Class used to construct forwards and backwards
402 class ETForestBase : public DominatorBase {
404 ETForestBase(bool isPostDom) : DominatorBase(isPostDom), Nodes(),
405 DFSInfoValid(false), SlowQueries(0) {}
407 virtual void releaseMemory() { reset(); }
409 typedef std::map<BasicBlock*, ETNode*> ETMapType;
411 void updateDFSNumbers();
413 /// dominates - Return true if A dominates B.
415 inline bool dominates(BasicBlock *A, BasicBlock *B) {
419 ETNode *NodeA = getNode(A);
420 ETNode *NodeB = getNode(B);
423 return NodeB->DominatedBy(NodeA);
425 // If we end up with too many slow queries, just update the
426 // DFS numbers on the theory that we are going to keep querying.
428 if (SlowQueries > 32) {
430 return NodeB->DominatedBy(NodeA);
432 return NodeB->DominatedBySlow(NodeA);
436 /// properlyDominates - Return true if A dominates B and A != B.
438 bool properlyDominates(BasicBlock *A, BasicBlock *B) {
439 return dominates(A, B) && A != B;
442 /// Return the nearest common dominator of A and B.
443 BasicBlock *nearestCommonDominator(BasicBlock *A, BasicBlock *B) const {
444 ETNode *NodeA = getNode(A);
445 ETNode *NodeB = getNode(B);
447 ETNode *Common = NodeA->NCA(NodeB);
450 return Common->getData<BasicBlock>();
453 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
454 AU.setPreservesAll();
455 AU.addRequired<ImmediateDominators>();
457 //===--------------------------------------------------------------------===//
458 // API to update Forest information based on modifications
461 /// addNewBlock - Add a new block to the CFG, with the specified immediate
464 void addNewBlock(BasicBlock *BB, BasicBlock *IDom);
466 /// setImmediateDominator - Update the immediate dominator information to
467 /// change the current immediate dominator for the specified block
468 /// to another block. This method requires that BB for NewIDom
469 /// already have an ETNode, otherwise just use addNewBlock.
471 void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom);
472 /// print - Convert to human readable form
474 virtual void print(std::ostream &OS, const Module* = 0) const;
476 /// getNode - return the (Post)DominatorTree node for the specified basic
477 /// block. This is the same as using operator[] on this class.
479 inline ETNode *getNode(BasicBlock *BB) const {
480 ETMapType::const_iterator i = Nodes.find(BB);
481 return (i != Nodes.end()) ? i->second : 0;
484 inline ETNode *operator[](BasicBlock *BB) const {
491 unsigned int SlowQueries;
495 //==-------------------------------------
496 /// ETForest Class - Concrete subclass of ETForestBase that is used to
497 /// compute a forwards ET-Forest.
499 class ETForest : public ETForestBase {
501 ETForest() : ETForestBase(false) {}
503 BasicBlock *getRoot() const {
504 assert(Roots.size() == 1 && "Should always have entry node!");
508 virtual bool runOnFunction(Function &F) {
509 reset(); // Reset from the last time we were run...
510 ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
511 Roots = ID.getRoots();
516 void calculate(const ImmediateDominators &ID);
517 ETNode *getNodeForBlock(BasicBlock *BB);
520 //===-------------------------------------
521 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
522 /// compute a normal dominator tree.
524 class DominatorTree : public DominatorTreeBase {
526 DominatorTree() : DominatorTreeBase(false) {}
528 BasicBlock *getRoot() const {
529 assert(Roots.size() == 1 && "Should always have entry node!");
533 virtual bool runOnFunction(Function &F) {
534 reset(); // Reset from the last time we were run...
535 ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
536 Roots = ID.getRoots();
541 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
542 AU.setPreservesAll();
543 AU.addRequired<ImmediateDominators>();
546 void calculate(const ImmediateDominators &ID);
547 Node *getNodeForBlock(BasicBlock *BB);
550 //===-------------------------------------
551 /// DominatorTree GraphTraits specialization so the DominatorTree can be
552 /// iterable by generic graph iterators.
554 template <> struct GraphTraits<DominatorTree::Node*> {
555 typedef DominatorTree::Node NodeType;
556 typedef NodeType::iterator ChildIteratorType;
558 static NodeType *getEntryNode(NodeType *N) {
561 static inline ChildIteratorType child_begin(NodeType* N) {
564 static inline ChildIteratorType child_end(NodeType* N) {
569 template <> struct GraphTraits<DominatorTree*>
570 : public GraphTraits<DominatorTree::Node*> {
571 static NodeType *getEntryNode(DominatorTree *DT) {
572 return DT->getRootNode();
576 //===----------------------------------------------------------------------===//
577 /// DominanceFrontierBase - Common base class for computing forward and inverse
578 /// dominance frontiers for a function.
580 class DominanceFrontierBase : public DominatorBase {
582 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
583 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
585 DomSetMapType Frontiers;
587 DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {}
589 virtual void releaseMemory() { Frontiers.clear(); }
591 // Accessor interface:
592 typedef DomSetMapType::iterator iterator;
593 typedef DomSetMapType::const_iterator const_iterator;
594 iterator begin() { return Frontiers.begin(); }
595 const_iterator begin() const { return Frontiers.begin(); }
596 iterator end() { return Frontiers.end(); }
597 const_iterator end() const { return Frontiers.end(); }
598 iterator find(BasicBlock *B) { return Frontiers.find(B); }
599 const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
601 void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
602 assert(find(BB) == end() && "Block already in DominanceFrontier!");
603 Frontiers.insert(std::make_pair(BB, frontier));
606 void addToFrontier(iterator I, BasicBlock *Node) {
607 assert(I != end() && "BB is not in DominanceFrontier!");
608 I->second.insert(Node);
611 void removeFromFrontier(iterator I, BasicBlock *Node) {
612 assert(I != end() && "BB is not in DominanceFrontier!");
613 assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
614 I->second.erase(Node);
617 /// print - Convert to human readable form
619 virtual void print(std::ostream &OS, const Module* = 0) const;
623 //===-------------------------------------
624 /// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
625 /// used to compute a forward dominator frontiers.
627 class DominanceFrontier : public DominanceFrontierBase {
629 DominanceFrontier() : DominanceFrontierBase(false) {}
631 BasicBlock *getRoot() const {
632 assert(Roots.size() == 1 && "Should always have entry node!");
636 virtual bool runOnFunction(Function &) {
638 DominatorTree &DT = getAnalysis<DominatorTree>();
639 Roots = DT.getRoots();
640 assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
641 calculate(DT, DT[Roots[0]]);
645 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
646 AU.setPreservesAll();
647 AU.addRequired<DominatorTree>();
650 const DomSetType &calculate(const DominatorTree &DT,
651 const DominatorTree::Node *Node);
655 } // End llvm namespace
657 // Make sure that any clients of this file link in Dominators.cpp
658 FORCE_DEFINING_FILE_TO_BE_LINKED(DominatorSet)