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 //===----------------------------------------------------------------------===//
39 // DominatorBase - Base class that other, more interesting dominator analyses
42 class DominatorBase : public FunctionPass {
44 std::vector<BasicBlock*> Roots;
45 const bool IsPostDominators;
47 inline DominatorBase(bool isPostDom) : Roots(), IsPostDominators(isPostDom) {}
49 // Return the root blocks of the current CFG. This may include multiple
50 // blocks if we are computing post dominators. For forward dominators, this
51 // will always be a single block (the entry node).
52 inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
54 // Returns true if analysis based of postdoms
55 bool isPostDominator() const { return IsPostDominators; }
59 //===----------------------------------------------------------------------===//
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[].
87 inline BasicBlock *get(BasicBlock *BB) const {
88 std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
89 return I != IDoms.end() ? I->second : 0;
92 //===--------------------------------------------------------------------===//
93 // API to update Immediate(Post)Dominators information based on modifications
96 /// addNewBlock - Add a new block to the CFG, with the specified immediate
99 void addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
100 assert(get(BB) == 0 && "BasicBlock already in idom info!");
104 /// setImmediateDominator - Update the immediate dominator information to
105 /// change the current immediate dominator for the specified block to another
106 /// block. This method requires that BB already have an IDom, otherwise just
108 void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) {
109 assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!");
113 // print - Convert to human readable form
114 virtual void print(std::ostream &OS) const;
117 //===-------------------------------------
118 // ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase that
119 // is used to compute a normal immediate dominator set.
121 struct ImmediateDominators : public ImmediateDominatorsBase {
122 ImmediateDominators() : ImmediateDominatorsBase(false) {}
124 BasicBlock *getRoot() const {
125 assert(Roots.size() == 1 && "Should always have entry node!");
129 virtual bool runOnFunction(Function &F);
131 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
132 AU.setPreservesAll();
139 BasicBlock *Label, *Parent, *Child, *Ancestor;
141 std::vector<BasicBlock*> Bucket;
143 InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){}
146 // Vertex - Map the DFS number to the BasicBlock*
147 std::vector<BasicBlock*> Vertex;
149 // Info - Collection of information used during the computation of idoms.
150 std::map<BasicBlock*, InfoRec> Info;
152 unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N);
153 void Compress(BasicBlock *V, InfoRec &VInfo);
154 BasicBlock *Eval(BasicBlock *v);
155 void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
160 //===----------------------------------------------------------------------===//
162 // DominatorSet - Maintain a set<BasicBlock*> for every basic block in a
163 // function, that represents the blocks that dominate the block. If the block
164 // is unreachable in this function, the set will be empty. This cannot happen
165 // for reachable code, because every block dominates at least itself.
167 struct DominatorSetBase : public DominatorBase {
168 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
170 typedef std::map<BasicBlock*, DomSetType> DomSetMapType;
174 DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {}
176 virtual void releaseMemory() { Doms.clear(); }
178 // Accessor interface:
179 typedef DomSetMapType::const_iterator const_iterator;
180 typedef DomSetMapType::iterator iterator;
181 inline const_iterator begin() const { return Doms.begin(); }
182 inline iterator begin() { return Doms.begin(); }
183 inline const_iterator end() const { return Doms.end(); }
184 inline iterator end() { return Doms.end(); }
185 inline const_iterator find(BasicBlock* B) const { return Doms.find(B); }
186 inline iterator find(BasicBlock* B) { return Doms.find(B); }
189 /// getDominators - Return the set of basic blocks that dominate the specified
192 inline const DomSetType &getDominators(BasicBlock *BB) const {
193 const_iterator I = find(BB);
194 assert(I != end() && "BB not in function!");
198 /// isReachable - Return true if the specified basicblock is reachable. If
199 /// the block is reachable, we have dominator set information for it.
200 bool isReachable(BasicBlock *BB) const {
201 return !getDominators(BB).empty();
204 /// dominates - Return true if A dominates B.
206 inline bool dominates(BasicBlock *A, BasicBlock *B) const {
207 return getDominators(B).count(A) != 0;
210 /// properlyDominates - Return true if A dominates B and A != B.
212 bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
213 return dominates(A, B) && A != B;
216 /// print - Convert to human readable form
217 virtual void print(std::ostream &OS) const;
219 /// dominates - Return true if A dominates B. This performs the special
220 /// checks necessary if A and B are in the same basic block.
222 bool dominates(Instruction *A, Instruction *B) const;
224 //===--------------------------------------------------------------------===//
225 // API to update (Post)DominatorSet information based on modifications to
228 /// addBasicBlock - Call to update the dominator set with information about a
229 /// new block that was inserted into the function.
230 void addBasicBlock(BasicBlock *BB, const DomSetType &Dominators) {
231 assert(find(BB) == end() && "Block already in DominatorSet!");
232 Doms.insert(std::make_pair(BB, Dominators));
235 // addDominator - If a new block is inserted into the CFG, then method may be
236 // called to notify the blocks it dominates that it is in their set.
238 void addDominator(BasicBlock *BB, BasicBlock *NewDominator) {
239 iterator I = find(BB);
240 assert(I != end() && "BB is not in DominatorSet!");
241 I->second.insert(NewDominator);
246 //===-------------------------------------
247 // DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
248 // compute a normal dominator set.
250 struct DominatorSet : public DominatorSetBase {
251 DominatorSet() : DominatorSetBase(false) {}
253 virtual bool runOnFunction(Function &F);
255 BasicBlock *getRoot() const {
256 assert(Roots.size() == 1 && "Should always have entry node!");
260 // getAnalysisUsage - This simply provides a dominator set
261 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
262 AU.addRequired<ImmediateDominators>();
263 AU.setPreservesAll();
268 //===----------------------------------------------------------------------===//
270 // DominatorTree - Calculate the immediate dominator tree for a function.
272 struct DominatorTreeBase : public DominatorBase {
275 std::map<BasicBlock*, Node*> Nodes;
277 typedef std::map<BasicBlock*, Node*> NodeMapType;
282 friend class DominatorTree;
283 friend class PostDominatorTree;
284 friend class DominatorTreeBase;
287 std::vector<Node*> Children;
289 typedef std::vector<Node*>::iterator iterator;
290 typedef std::vector<Node*>::const_iterator const_iterator;
292 iterator begin() { return Children.begin(); }
293 iterator end() { return Children.end(); }
294 const_iterator begin() const { return Children.begin(); }
295 const_iterator end() const { return Children.end(); }
297 inline BasicBlock *getBlock() const { return TheBB; }
298 inline Node *getIDom() const { return IDom; }
299 inline const std::vector<Node*> &getChildren() const { return Children; }
301 // dominates - Returns true iff this dominates N. Note that this is not a
302 // constant time operation!
303 inline bool dominates(const Node *N) const {
305 while ((IDom = N->getIDom()) != 0 && IDom != this)
306 N = IDom; // Walk up the tree
311 inline Node(BasicBlock *BB, Node *iDom)
312 : TheBB(BB), IDom(iDom) {}
313 inline Node *addChild(Node *C) { Children.push_back(C); return C; }
315 void setIDom(Node *NewIDom);
319 DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {}
320 ~DominatorTreeBase() { reset(); }
322 virtual void releaseMemory() { reset(); }
324 /// getNode - return the (Post)DominatorTree node for the specified basic
325 /// block. This is the same as using operator[] on this class.
327 inline Node *getNode(BasicBlock *BB) const {
328 NodeMapType::const_iterator i = Nodes.find(BB);
329 return (i != Nodes.end()) ? i->second : 0;
332 inline Node *operator[](BasicBlock *BB) const {
336 // getRootNode - This returns the entry node for the CFG of the function. If
337 // this tree represents the post-dominance relations for a function, however,
338 // this root may be a node with the block == NULL. This is the case when
339 // there are multiple exit nodes from a particular function. Consumers of
340 // post-dominance information must be capable of dealing with this
343 Node *getRootNode() { return RootNode; }
344 const Node *getRootNode() const { return RootNode; }
346 //===--------------------------------------------------------------------===//
347 // API to update (Post)DominatorTree information based on modifications to
350 /// createNewNode - Add a new node to the dominator tree information. This
351 /// creates a new node as a child of IDomNode, linking it into the children
352 /// list of the immediate dominator.
354 Node *createNewNode(BasicBlock *BB, Node *IDomNode) {
355 assert(getNode(BB) == 0 && "Block already in dominator tree!");
356 assert(IDomNode && "Not immediate dominator specified for block!");
357 return Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
360 /// changeImmediateDominator - This method is used to update the dominator
361 /// tree information when a node's immediate dominator changes.
363 void changeImmediateDominator(Node *Node, Node *NewIDom) {
364 assert(Node && NewIDom && "Cannot change null node pointers!");
365 Node->setIDom(NewIDom);
368 /// print - Convert to human readable form
369 virtual void print(std::ostream &OS) const;
373 //===-------------------------------------
374 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
375 // compute a normal dominator tree.
377 struct DominatorTree : public DominatorTreeBase {
378 DominatorTree() : DominatorTreeBase(false) {}
380 BasicBlock *getRoot() const {
381 assert(Roots.size() == 1 && "Should always have entry node!");
385 virtual bool runOnFunction(Function &F) {
386 reset(); // Reset from the last time we were run...
387 ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
388 Roots = ID.getRoots();
393 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
394 AU.setPreservesAll();
395 AU.addRequired<ImmediateDominators>();
398 void calculate(const ImmediateDominators &ID);
399 Node *getNodeForBlock(BasicBlock *BB);
402 //===-------------------------------------
403 // DominatorTree GraphTraits specialization so the DominatorTree can be
404 // iterable by generic graph iterators.
406 template <> struct GraphTraits<DominatorTree::Node*> {
407 typedef DominatorTree::Node NodeType;
408 typedef NodeType::iterator ChildIteratorType;
410 static NodeType *getEntryNode(NodeType *N) {
413 static inline ChildIteratorType child_begin(NodeType* N) {
416 static inline ChildIteratorType child_end(NodeType* N) {
421 template <> struct GraphTraits<DominatorTree*>
422 : public GraphTraits<DominatorTree::Node*> {
423 static NodeType *getEntryNode(DominatorTree *DT) {
424 return DT->getRootNode();
428 //===----------------------------------------------------------------------===//
430 // DominanceFrontier - Calculate the dominance frontiers for a function.
432 struct DominanceFrontierBase : public DominatorBase {
433 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
434 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
436 DomSetMapType Frontiers;
438 DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {}
440 virtual void releaseMemory() { Frontiers.clear(); }
442 // Accessor interface:
443 typedef DomSetMapType::iterator iterator;
444 typedef DomSetMapType::const_iterator const_iterator;
445 iterator begin() { return Frontiers.begin(); }
446 const_iterator begin() const { return Frontiers.begin(); }
447 iterator end() { return Frontiers.end(); }
448 const_iterator end() const { return Frontiers.end(); }
449 iterator find(BasicBlock *B) { return Frontiers.find(B); }
450 const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
452 void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
453 assert(find(BB) == end() && "Block already in DominanceFrontier!");
454 Frontiers.insert(std::make_pair(BB, frontier));
457 void addToFrontier(iterator I, BasicBlock *Node) {
458 assert(I != end() && "BB is not in DominanceFrontier!");
459 I->second.insert(Node);
462 void removeFromFrontier(iterator I, BasicBlock *Node) {
463 assert(I != end() && "BB is not in DominanceFrontier!");
464 assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
465 I->second.erase(Node);
468 // print - Convert to human readable form
469 virtual void print(std::ostream &OS) const;
473 //===-------------------------------------
474 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
475 // compute a normal dominator tree.
477 struct DominanceFrontier : public DominanceFrontierBase {
478 DominanceFrontier() : DominanceFrontierBase(false) {}
480 BasicBlock *getRoot() const {
481 assert(Roots.size() == 1 && "Should always have entry node!");
485 virtual bool runOnFunction(Function &) {
487 DominatorTree &DT = getAnalysis<DominatorTree>();
488 Roots = DT.getRoots();
489 assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
490 calculate(DT, DT[Roots[0]]);
494 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
495 AU.setPreservesAll();
496 AU.addRequired<DominatorTree>();
499 const DomSetType &calculate(const DominatorTree &DT,
500 const DominatorTree::Node *Node);
503 } // End llvm namespace