LLVM API Documentation
00001 //===- llvm/Analysis/Dominators.h - Dominator Info Calculation --*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines the following classes: 00011 // 1. ImmediateDominators: Calculates and holds a mapping between BasicBlocks 00012 // and their immediate dominator. 00013 // 2. DominatorSet: Calculates the [reverse] dominator set for a function 00014 // 3. DominatorTree: Represent the ImmediateDominator as an explicit tree 00015 // structure. 00016 // 4. DominanceFrontier: Calculate and hold the dominance frontier for a 00017 // function. 00018 // 00019 // These data structures are listed in increasing order of complexity. It 00020 // takes longer to calculate the dominator frontier, for example, than the 00021 // ImmediateDominator mapping. 00022 // 00023 //===----------------------------------------------------------------------===// 00024 00025 #ifndef LLVM_ANALYSIS_DOMINATORS_H 00026 #define LLVM_ANALYSIS_DOMINATORS_H 00027 00028 #include "llvm/Pass.h" 00029 #include <set> 00030 00031 namespace llvm { 00032 00033 class Instruction; 00034 00035 template <typename GraphType> struct GraphTraits; 00036 00037 //===----------------------------------------------------------------------===// 00038 /// DominatorBase - Base class that other, more interesting dominator analyses 00039 /// inherit from. 00040 /// 00041 class DominatorBase : public FunctionPass { 00042 protected: 00043 std::vector<BasicBlock*> Roots; 00044 const bool IsPostDominators; 00045 00046 inline DominatorBase(bool isPostDom) : Roots(), IsPostDominators(isPostDom) {} 00047 public: 00048 /// getRoots - Return the root blocks of the current CFG. This may include 00049 /// multiple blocks if we are computing post dominators. For forward 00050 /// dominators, this will always be a single block (the entry node). 00051 /// 00052 inline const std::vector<BasicBlock*> &getRoots() const { return Roots; } 00053 00054 /// isPostDominator - Returns true if analysis based of postdoms 00055 /// 00056 bool isPostDominator() const { return IsPostDominators; } 00057 }; 00058 00059 00060 //===----------------------------------------------------------------------===// 00061 /// ImmediateDominators - Calculate the immediate dominator for each node in a 00062 /// function. 00063 /// 00064 class ImmediateDominatorsBase : public DominatorBase { 00065 protected: 00066 std::map<BasicBlock*, BasicBlock*> IDoms; 00067 public: 00068 ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {} 00069 00070 virtual void releaseMemory() { IDoms.clear(); } 00071 00072 // Accessor interface: 00073 typedef std::map<BasicBlock*, BasicBlock*> IDomMapType; 00074 typedef IDomMapType::const_iterator const_iterator; 00075 inline const_iterator begin() const { return IDoms.begin(); } 00076 inline const_iterator end() const { return IDoms.end(); } 00077 inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);} 00078 00079 /// operator[] - Return the idom for the specified basic block. The start 00080 /// node returns null, because it does not have an immediate dominator. 00081 /// 00082 inline BasicBlock *operator[](BasicBlock *BB) const { 00083 return get(BB); 00084 } 00085 00086 /// get() - Synonym for operator[]. 00087 /// 00088 inline BasicBlock *get(BasicBlock *BB) const { 00089 std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB); 00090 return I != IDoms.end() ? I->second : 0; 00091 } 00092 00093 //===--------------------------------------------------------------------===// 00094 // API to update Immediate(Post)Dominators information based on modifications 00095 // to the CFG... 00096 00097 /// addNewBlock - Add a new block to the CFG, with the specified immediate 00098 /// dominator. 00099 /// 00100 void addNewBlock(BasicBlock *BB, BasicBlock *IDom) { 00101 assert(get(BB) == 0 && "BasicBlock already in idom info!"); 00102 IDoms[BB] = IDom; 00103 } 00104 00105 /// setImmediateDominator - Update the immediate dominator information to 00106 /// change the current immediate dominator for the specified block to another 00107 /// block. This method requires that BB already have an IDom, otherwise just 00108 /// use addNewBlock. 00109 /// 00110 void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) { 00111 assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!"); 00112 IDoms[BB] = NewIDom; 00113 } 00114 00115 /// print - Convert to human readable form 00116 /// 00117 virtual void print(std::ostream &OS) const; 00118 }; 00119 00120 //===------------------------------------- 00121 /// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase 00122 /// that is used to compute a normal immediate dominator set. 00123 /// 00124 struct ImmediateDominators : public ImmediateDominatorsBase { 00125 ImmediateDominators() : ImmediateDominatorsBase(false) {} 00126 00127 BasicBlock *getRoot() const { 00128 assert(Roots.size() == 1 && "Should always have entry node!"); 00129 return Roots[0]; 00130 } 00131 00132 virtual bool runOnFunction(Function &F); 00133 00134 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00135 AU.setPreservesAll(); 00136 } 00137 00138 private: 00139 struct InfoRec { 00140 unsigned Semi; 00141 unsigned Size; 00142 BasicBlock *Label, *Parent, *Child, *Ancestor; 00143 00144 std::vector<BasicBlock*> Bucket; 00145 00146 InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){} 00147 }; 00148 00149 // Vertex - Map the DFS number to the BasicBlock* 00150 std::vector<BasicBlock*> Vertex; 00151 00152 // Info - Collection of information used during the computation of idoms. 00153 std::map<BasicBlock*, InfoRec> Info; 00154 00155 unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N); 00156 void Compress(BasicBlock *V, InfoRec &VInfo); 00157 BasicBlock *Eval(BasicBlock *v); 00158 void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo); 00159 }; 00160 00161 00162 00163 //===----------------------------------------------------------------------===// 00164 /// DominatorSet - Maintain a set<BasicBlock*> for every basic block in a 00165 /// function, that represents the blocks that dominate the block. If the block 00166 /// is unreachable in this function, the set will be empty. This cannot happen 00167 /// for reachable code, because every block dominates at least itself. 00168 /// 00169 struct DominatorSetBase : public DominatorBase { 00170 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 00171 // Map of dom sets 00172 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; 00173 protected: 00174 DomSetMapType Doms; 00175 public: 00176 DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {} 00177 00178 virtual void releaseMemory() { Doms.clear(); } 00179 00180 // Accessor interface: 00181 typedef DomSetMapType::const_iterator const_iterator; 00182 typedef DomSetMapType::iterator iterator; 00183 inline const_iterator begin() const { return Doms.begin(); } 00184 inline iterator begin() { return Doms.begin(); } 00185 inline const_iterator end() const { return Doms.end(); } 00186 inline iterator end() { return Doms.end(); } 00187 inline const_iterator find(BasicBlock* B) const { return Doms.find(B); } 00188 inline iterator find(BasicBlock* B) { return Doms.find(B); } 00189 00190 00191 /// getDominators - Return the set of basic blocks that dominate the specified 00192 /// block. 00193 /// 00194 inline const DomSetType &getDominators(BasicBlock *BB) const { 00195 const_iterator I = find(BB); 00196 assert(I != end() && "BB not in function!"); 00197 return I->second; 00198 } 00199 00200 /// isReachable - Return true if the specified basicblock is reachable. If 00201 /// the block is reachable, we have dominator set information for it. 00202 /// 00203 bool isReachable(BasicBlock *BB) const { 00204 return !getDominators(BB).empty(); 00205 } 00206 00207 /// dominates - Return true if A dominates B. 00208 /// 00209 inline bool dominates(BasicBlock *A, BasicBlock *B) const { 00210 return getDominators(B).count(A) != 0; 00211 } 00212 00213 /// properlyDominates - Return true if A dominates B and A != B. 00214 /// 00215 bool properlyDominates(BasicBlock *A, BasicBlock *B) const { 00216 return dominates(A, B) && A != B; 00217 } 00218 00219 /// print - Convert to human readable form 00220 /// 00221 virtual void print(std::ostream &OS) const; 00222 00223 /// dominates - Return true if A dominates B. This performs the special 00224 /// checks necessary if A and B are in the same basic block. 00225 /// 00226 bool dominates(Instruction *A, Instruction *B) const; 00227 00228 //===--------------------------------------------------------------------===// 00229 // API to update (Post)DominatorSet information based on modifications to 00230 // the CFG... 00231 00232 /// addBasicBlock - Call to update the dominator set with information about a 00233 /// new block that was inserted into the function. 00234 /// 00235 void addBasicBlock(BasicBlock *BB, const DomSetType &Dominators) { 00236 assert(find(BB) == end() && "Block already in DominatorSet!"); 00237 Doms.insert(std::make_pair(BB, Dominators)); 00238 } 00239 00240 /// addDominator - If a new block is inserted into the CFG, then method may be 00241 /// called to notify the blocks it dominates that it is in their set. 00242 /// 00243 void addDominator(BasicBlock *BB, BasicBlock *NewDominator) { 00244 iterator I = find(BB); 00245 assert(I != end() && "BB is not in DominatorSet!"); 00246 I->second.insert(NewDominator); 00247 } 00248 }; 00249 00250 00251 //===------------------------------------- 00252 /// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to 00253 /// compute a normal dominator set. 00254 /// 00255 struct DominatorSet : public DominatorSetBase { 00256 DominatorSet() : DominatorSetBase(false) {} 00257 00258 virtual bool runOnFunction(Function &F); 00259 00260 BasicBlock *getRoot() const { 00261 assert(Roots.size() == 1 && "Should always have entry node!"); 00262 return Roots[0]; 00263 } 00264 00265 /// getAnalysisUsage - This simply provides a dominator set 00266 /// 00267 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00268 AU.addRequired<ImmediateDominators>(); 00269 AU.setPreservesAll(); 00270 } 00271 00272 // stub - dummy function, just ignore it 00273 static void stub(); 00274 }; 00275 00276 00277 //===----------------------------------------------------------------------===// 00278 /// DominatorTree - Calculate the immediate dominator tree for a function. 00279 /// 00280 struct DominatorTreeBase : public DominatorBase { 00281 class Node; 00282 protected: 00283 std::map<BasicBlock*, Node*> Nodes; 00284 void reset(); 00285 typedef std::map<BasicBlock*, Node*> NodeMapType; 00286 00287 Node *RootNode; 00288 public: 00289 class Node { 00290 friend struct DominatorTree; 00291 friend struct PostDominatorTree; 00292 friend struct DominatorTreeBase; 00293 BasicBlock *TheBB; 00294 Node *IDom; 00295 std::vector<Node*> Children; 00296 public: 00297 typedef std::vector<Node*>::iterator iterator; 00298 typedef std::vector<Node*>::const_iterator const_iterator; 00299 00300 iterator begin() { return Children.begin(); } 00301 iterator end() { return Children.end(); } 00302 const_iterator begin() const { return Children.begin(); } 00303 const_iterator end() const { return Children.end(); } 00304 00305 inline BasicBlock *getBlock() const { return TheBB; } 00306 inline Node *getIDom() const { return IDom; } 00307 inline const std::vector<Node*> &getChildren() const { return Children; } 00308 00309 /// dominates - Returns true iff this dominates N. Note that this is not a 00310 /// constant time operation! 00311 /// 00312 inline bool dominates(const Node *N) const { 00313 const Node *IDom; 00314 while ((IDom = N->getIDom()) != 0 && IDom != this) 00315 N = IDom; // Walk up the tree 00316 return IDom != 0; 00317 } 00318 00319 private: 00320 inline Node(BasicBlock *BB, Node *iDom) : TheBB(BB), IDom(iDom) {} 00321 inline Node *addChild(Node *C) { Children.push_back(C); return C; } 00322 00323 void setIDom(Node *NewIDom); 00324 }; 00325 00326 public: 00327 DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {} 00328 ~DominatorTreeBase() { reset(); } 00329 00330 virtual void releaseMemory() { reset(); } 00331 00332 /// getNode - return the (Post)DominatorTree node for the specified basic 00333 /// block. This is the same as using operator[] on this class. 00334 /// 00335 inline Node *getNode(BasicBlock *BB) const { 00336 NodeMapType::const_iterator i = Nodes.find(BB); 00337 return (i != Nodes.end()) ? i->second : 0; 00338 } 00339 00340 inline Node *operator[](BasicBlock *BB) const { 00341 return getNode(BB); 00342 } 00343 00344 /// getRootNode - This returns the entry node for the CFG of the function. If 00345 /// this tree represents the post-dominance relations for a function, however, 00346 /// this root may be a node with the block == NULL. This is the case when 00347 /// there are multiple exit nodes from a particular function. Consumers of 00348 /// post-dominance information must be capable of dealing with this 00349 /// possibility. 00350 /// 00351 Node *getRootNode() { return RootNode; } 00352 const Node *getRootNode() const { return RootNode; } 00353 00354 //===--------------------------------------------------------------------===// 00355 // API to update (Post)DominatorTree information based on modifications to 00356 // the CFG... 00357 00358 /// createNewNode - Add a new node to the dominator tree information. This 00359 /// creates a new node as a child of IDomNode, linking it into the children 00360 /// list of the immediate dominator. 00361 /// 00362 Node *createNewNode(BasicBlock *BB, Node *IDomNode) { 00363 assert(getNode(BB) == 0 && "Block already in dominator tree!"); 00364 assert(IDomNode && "Not immediate dominator specified for block!"); 00365 return Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode)); 00366 } 00367 00368 /// changeImmediateDominator - This method is used to update the dominator 00369 /// tree information when a node's immediate dominator changes. 00370 /// 00371 void changeImmediateDominator(Node *N, Node *NewIDom) { 00372 assert(N && NewIDom && "Cannot change null node pointers!"); 00373 N->setIDom(NewIDom); 00374 } 00375 00376 /// print - Convert to human readable form 00377 /// 00378 virtual void print(std::ostream &OS) const; 00379 }; 00380 00381 00382 //===------------------------------------- 00383 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 00384 /// compute a normal dominator tree. 00385 /// 00386 struct DominatorTree : public DominatorTreeBase { 00387 DominatorTree() : DominatorTreeBase(false) {} 00388 00389 BasicBlock *getRoot() const { 00390 assert(Roots.size() == 1 && "Should always have entry node!"); 00391 return Roots[0]; 00392 } 00393 00394 virtual bool runOnFunction(Function &F) { 00395 reset(); // Reset from the last time we were run... 00396 ImmediateDominators &ID = getAnalysis<ImmediateDominators>(); 00397 Roots = ID.getRoots(); 00398 calculate(ID); 00399 return false; 00400 } 00401 00402 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00403 AU.setPreservesAll(); 00404 AU.addRequired<ImmediateDominators>(); 00405 } 00406 private: 00407 void calculate(const ImmediateDominators &ID); 00408 Node *getNodeForBlock(BasicBlock *BB); 00409 }; 00410 00411 //===------------------------------------- 00412 /// DominatorTree GraphTraits specialization so the DominatorTree can be 00413 /// iterable by generic graph iterators. 00414 /// 00415 template <> struct GraphTraits<DominatorTree::Node*> { 00416 typedef DominatorTree::Node NodeType; 00417 typedef NodeType::iterator ChildIteratorType; 00418 00419 static NodeType *getEntryNode(NodeType *N) { 00420 return N; 00421 } 00422 static inline ChildIteratorType child_begin(NodeType* N) { 00423 return N->begin(); 00424 } 00425 static inline ChildIteratorType child_end(NodeType* N) { 00426 return N->end(); 00427 } 00428 }; 00429 00430 template <> struct GraphTraits<DominatorTree*> 00431 : public GraphTraits<DominatorTree::Node*> { 00432 static NodeType *getEntryNode(DominatorTree *DT) { 00433 return DT->getRootNode(); 00434 } 00435 }; 00436 00437 //===----------------------------------------------------------------------===// 00438 /// DominanceFrontier - Calculate the dominance frontiers for a function. 00439 /// 00440 struct DominanceFrontierBase : public DominatorBase { 00441 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 00442 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map 00443 protected: 00444 DomSetMapType Frontiers; 00445 public: 00446 DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {} 00447 00448 virtual void releaseMemory() { Frontiers.clear(); } 00449 00450 // Accessor interface: 00451 typedef DomSetMapType::iterator iterator; 00452 typedef DomSetMapType::const_iterator const_iterator; 00453 iterator begin() { return Frontiers.begin(); } 00454 const_iterator begin() const { return Frontiers.begin(); } 00455 iterator end() { return Frontiers.end(); } 00456 const_iterator end() const { return Frontiers.end(); } 00457 iterator find(BasicBlock *B) { return Frontiers.find(B); } 00458 const_iterator find(BasicBlock *B) const { return Frontiers.find(B); } 00459 00460 void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) { 00461 assert(find(BB) == end() && "Block already in DominanceFrontier!"); 00462 Frontiers.insert(std::make_pair(BB, frontier)); 00463 } 00464 00465 void addToFrontier(iterator I, BasicBlock *Node) { 00466 assert(I != end() && "BB is not in DominanceFrontier!"); 00467 I->second.insert(Node); 00468 } 00469 00470 void removeFromFrontier(iterator I, BasicBlock *Node) { 00471 assert(I != end() && "BB is not in DominanceFrontier!"); 00472 assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB"); 00473 I->second.erase(Node); 00474 } 00475 00476 /// print - Convert to human readable form 00477 /// 00478 virtual void print(std::ostream &OS) const; 00479 }; 00480 00481 00482 //===------------------------------------- 00483 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 00484 /// compute a normal dominator tree. 00485 /// 00486 struct DominanceFrontier : public DominanceFrontierBase { 00487 DominanceFrontier() : DominanceFrontierBase(false) {} 00488 00489 BasicBlock *getRoot() const { 00490 assert(Roots.size() == 1 && "Should always have entry node!"); 00491 return Roots[0]; 00492 } 00493 00494 virtual bool runOnFunction(Function &) { 00495 Frontiers.clear(); 00496 DominatorTree &DT = getAnalysis<DominatorTree>(); 00497 Roots = DT.getRoots(); 00498 assert(Roots.size() == 1 && "Only one entry block for forward domfronts!"); 00499 calculate(DT, DT[Roots[0]]); 00500 return false; 00501 } 00502 00503 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00504 AU.setPreservesAll(); 00505 AU.addRequired<DominatorTree>(); 00506 } 00507 private: 00508 const DomSetType &calculate(const DominatorTree &DT, 00509 const DominatorTree::Node *Node); 00510 }; 00511 00512 // Make sure that any clients of this file link in Dominators.cpp 00513 static IncludeFile 00514 DOMINATORS_INCLUDE_FILE((void*)&DominatorSet::stub); 00515 } // End llvm namespace 00516 00517 #endif