Dominators.h revision 31b935357d1396d3be32fdf24dcb0319a6908c6f
1//===- llvm/Analysis/Dominators.h - Dominator Info Calculation --*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 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. 7// 8//===----------------------------------------------------------------------===// 9// 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 15// structure. 16// 4. DominanceFrontier: Calculate and hold the dominance frontier for a 17// function. 18// 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. 22// 23//===----------------------------------------------------------------------===// 24 25#ifndef LLVM_ANALYSIS_DOMINATORS_H 26#define LLVM_ANALYSIS_DOMINATORS_H 27 28#include "llvm/Pass.h" 29#include <set> 30 31namespace llvm { 32 33class Instruction; 34 35template <typename GraphType> struct GraphTraits; 36 37//===----------------------------------------------------------------------===// 38// 39// DominatorBase - Base class that other, more interesting dominator analyses 40// inherit from. 41// 42class DominatorBase : public FunctionPass { 43protected: 44 std::vector<BasicBlock*> Roots; 45 const bool IsPostDominators; 46 47 inline DominatorBase(bool isPostDom) : Roots(), IsPostDominators(isPostDom) {} 48public: 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; } 53 54 // Returns true if analysis based of postdoms 55 bool isPostDominator() const { return IsPostDominators; } 56}; 57 58 59//===----------------------------------------------------------------------===// 60// 61// ImmediateDominators - Calculate the immediate dominator for each node in a 62// function. 63// 64class ImmediateDominatorsBase : public DominatorBase { 65protected: 66 std::map<BasicBlock*, BasicBlock*> IDoms; 67public: 68 ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {} 69 70 virtual void releaseMemory() { IDoms.clear(); } 71 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);} 78 79 // operator[] - Return the idom for the specified basic block. The start 80 // node returns null, because it does not have an immediate dominator. 81 // 82 inline BasicBlock *operator[](BasicBlock *BB) const { 83 return get(BB); 84 } 85 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; 90 } 91 92 //===--------------------------------------------------------------------===// 93 // API to update Immediate(Post)Dominators information based on modifications 94 // to the CFG... 95 96 /// addNewBlock - Add a new block to the CFG, with the specified immediate 97 /// dominator. 98 /// 99 void addNewBlock(BasicBlock *BB, BasicBlock *IDom) { 100 assert(get(BB) == 0 && "BasicBlock already in idom info!"); 101 IDoms[BB] = IDom; 102 } 103 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 107 /// use addNewBlock. 108 void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) { 109 assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!"); 110 IDoms[BB] = NewIDom; 111 } 112 113 // print - Convert to human readable form 114 virtual void print(std::ostream &OS) const; 115}; 116 117//===------------------------------------- 118// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase that 119// is used to compute a normal immediate dominator set. 120// 121struct ImmediateDominators : public ImmediateDominatorsBase { 122 ImmediateDominators() : ImmediateDominatorsBase(false) {} 123 124 BasicBlock *getRoot() const { 125 assert(Roots.size() == 1 && "Should always have entry node!"); 126 return Roots[0]; 127 } 128 129 virtual bool runOnFunction(Function &F); 130 131 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 132 AU.setPreservesAll(); 133 } 134 135private: 136 struct InfoRec { 137 unsigned Semi; 138 unsigned Size; 139 BasicBlock *Label, *Parent, *Child, *Ancestor; 140 141 std::vector<BasicBlock*> Bucket; 142 143 InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){} 144 }; 145 146 // Vertex - Map the DFS number to the BasicBlock* 147 std::vector<BasicBlock*> Vertex; 148 149 // Info - Collection of information used during the computation of idoms. 150 std::map<BasicBlock*, InfoRec> Info; 151 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); 156}; 157 158 159 160//===----------------------------------------------------------------------===// 161// 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. 166// 167struct DominatorSetBase : public DominatorBase { 168 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 169 // Map of dom sets 170 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; 171protected: 172 DomSetMapType Doms; 173public: 174 DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {} 175 176 virtual void releaseMemory() { Doms.clear(); } 177 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); } 187 188 189 /// getDominators - Return the set of basic blocks that dominate the specified 190 /// block. 191 /// 192 inline const DomSetType &getDominators(BasicBlock *BB) const { 193 const_iterator I = find(BB); 194 assert(I != end() && "BB not in function!"); 195 return I->second; 196 } 197 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(); 202 } 203 204 /// dominates - Return true if A dominates B. 205 /// 206 inline bool dominates(BasicBlock *A, BasicBlock *B) const { 207 return getDominators(B).count(A) != 0; 208 } 209 210 /// properlyDominates - Return true if A dominates B and A != B. 211 /// 212 bool properlyDominates(BasicBlock *A, BasicBlock *B) const { 213 return dominates(A, B) && A != B; 214 } 215 216 /// print - Convert to human readable form 217 virtual void print(std::ostream &OS) const; 218 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. 221 /// 222 bool dominates(Instruction *A, Instruction *B) const; 223 224 //===--------------------------------------------------------------------===// 225 // API to update (Post)DominatorSet information based on modifications to 226 // the CFG... 227 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)); 233 } 234 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. 237 // 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); 242 } 243}; 244 245 246//===------------------------------------- 247// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to 248// compute a normal dominator set. 249// 250struct DominatorSet : public DominatorSetBase { 251 DominatorSet() : DominatorSetBase(false) {} 252 253 virtual bool runOnFunction(Function &F); 254 255 /// recalculate - This method may be called by external passes that modify the 256 /// CFG and then need dominator information recalculated. This method is 257 /// obviously really slow, so it should be avoided if at all possible. 258 void recalculate(); 259 260 BasicBlock *getRoot() const { 261 assert(Roots.size() == 1 && "Should always have entry node!"); 262 return Roots[0]; 263 } 264 265 // getAnalysisUsage - This simply provides a dominator set 266 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 267 AU.addRequired<ImmediateDominators>(); 268 AU.setPreservesAll(); 269 } 270}; 271 272 273//===----------------------------------------------------------------------===// 274// 275// DominatorTree - Calculate the immediate dominator tree for a function. 276// 277struct DominatorTreeBase : public DominatorBase { 278 class Node; 279protected: 280 std::map<BasicBlock*, Node*> Nodes; 281 void reset(); 282 typedef std::map<BasicBlock*, Node*> NodeMapType; 283 284 Node *RootNode; 285public: 286 class Node { 287 friend class DominatorTree; 288 friend class PostDominatorTree; 289 friend class DominatorTreeBase; 290 BasicBlock *TheBB; 291 Node *IDom; 292 std::vector<Node*> Children; 293 public: 294 typedef std::vector<Node*>::iterator iterator; 295 typedef std::vector<Node*>::const_iterator const_iterator; 296 297 iterator begin() { return Children.begin(); } 298 iterator end() { return Children.end(); } 299 const_iterator begin() const { return Children.begin(); } 300 const_iterator end() const { return Children.end(); } 301 302 inline BasicBlock *getBlock() const { return TheBB; } 303 inline Node *getIDom() const { return IDom; } 304 inline const std::vector<Node*> &getChildren() const { return Children; } 305 306 // dominates - Returns true iff this dominates N. Note that this is not a 307 // constant time operation! 308 inline bool dominates(const Node *N) const { 309 const Node *IDom; 310 while ((IDom = N->getIDom()) != 0 && IDom != this) 311 N = IDom; // Walk up the tree 312 return IDom != 0; 313 } 314 315 private: 316 inline Node(BasicBlock *BB, Node *iDom) 317 : TheBB(BB), IDom(iDom) {} 318 inline Node *addChild(Node *C) { Children.push_back(C); return C; } 319 320 void setIDom(Node *NewIDom); 321 }; 322 323public: 324 DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {} 325 ~DominatorTreeBase() { reset(); } 326 327 virtual void releaseMemory() { reset(); } 328 329 /// getNode - return the (Post)DominatorTree node for the specified basic 330 /// block. This is the same as using operator[] on this class. 331 /// 332 inline Node *getNode(BasicBlock *BB) const { 333 NodeMapType::const_iterator i = Nodes.find(BB); 334 return (i != Nodes.end()) ? i->second : 0; 335 } 336 337 inline Node *operator[](BasicBlock *BB) const { 338 return getNode(BB); 339 } 340 341 // getRootNode - This returns the entry node for the CFG of the function. If 342 // this tree represents the post-dominance relations for a function, however, 343 // this root may be a node with the block == NULL. This is the case when 344 // there are multiple exit nodes from a particular function. Consumers of 345 // post-dominance information must be capable of dealing with this 346 // possibility. 347 // 348 Node *getRootNode() { return RootNode; } 349 const Node *getRootNode() const { return RootNode; } 350 351 //===--------------------------------------------------------------------===// 352 // API to update (Post)DominatorTree information based on modifications to 353 // the CFG... 354 355 /// createNewNode - Add a new node to the dominator tree information. This 356 /// creates a new node as a child of IDomNode, linking it into the children 357 /// list of the immediate dominator. 358 /// 359 Node *createNewNode(BasicBlock *BB, Node *IDomNode) { 360 assert(getNode(BB) == 0 && "Block already in dominator tree!"); 361 assert(IDomNode && "Not immediate dominator specified for block!"); 362 return Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode)); 363 } 364 365 /// changeImmediateDominator - This method is used to update the dominator 366 /// tree information when a node's immediate dominator changes. 367 /// 368 void changeImmediateDominator(Node *Node, Node *NewIDom) { 369 assert(Node && NewIDom && "Cannot change null node pointers!"); 370 Node->setIDom(NewIDom); 371 } 372 373 /// print - Convert to human readable form 374 virtual void print(std::ostream &OS) const; 375}; 376 377 378//===------------------------------------- 379// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 380// compute a normal dominator tree. 381// 382struct DominatorTree : public DominatorTreeBase { 383 DominatorTree() : DominatorTreeBase(false) {} 384 385 BasicBlock *getRoot() const { 386 assert(Roots.size() == 1 && "Should always have entry node!"); 387 return Roots[0]; 388 } 389 390 virtual bool runOnFunction(Function &F) { 391 reset(); // Reset from the last time we were run... 392 ImmediateDominators &ID = getAnalysis<ImmediateDominators>(); 393 Roots = ID.getRoots(); 394 calculate(ID); 395 return false; 396 } 397 398 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 399 AU.setPreservesAll(); 400 AU.addRequired<ImmediateDominators>(); 401 } 402private: 403 void calculate(const ImmediateDominators &ID); 404 Node *getNodeForBlock(BasicBlock *BB); 405}; 406 407//===------------------------------------- 408// DominatorTree GraphTraits specialization so the DominatorTree can be 409// iterable by generic graph iterators. 410 411template <> struct GraphTraits<DominatorTree::Node*> { 412 typedef DominatorTree::Node NodeType; 413 typedef NodeType::iterator ChildIteratorType; 414 415 static NodeType *getEntryNode(NodeType *N) { 416 return N; 417 } 418 static inline ChildIteratorType child_begin(NodeType* N) { 419 return N->begin(); 420 } 421 static inline ChildIteratorType child_end(NodeType* N) { 422 return N->end(); 423 } 424}; 425 426template <> struct GraphTraits<DominatorTree*> 427 : public GraphTraits<DominatorTree::Node*> { 428 static NodeType *getEntryNode(DominatorTree *DT) { 429 return DT->getRootNode(); 430 } 431}; 432 433//===----------------------------------------------------------------------===// 434// 435// DominanceFrontier - Calculate the dominance frontiers for a function. 436// 437struct DominanceFrontierBase : public DominatorBase { 438 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 439 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map 440protected: 441 DomSetMapType Frontiers; 442public: 443 DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {} 444 445 virtual void releaseMemory() { Frontiers.clear(); } 446 447 // Accessor interface: 448 typedef DomSetMapType::iterator iterator; 449 typedef DomSetMapType::const_iterator const_iterator; 450 iterator begin() { return Frontiers.begin(); } 451 const_iterator begin() const { return Frontiers.begin(); } 452 iterator end() { return Frontiers.end(); } 453 const_iterator end() const { return Frontiers.end(); } 454 iterator find(BasicBlock *B) { return Frontiers.find(B); } 455 const_iterator find(BasicBlock *B) const { return Frontiers.find(B); } 456 457 void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) { 458 assert(find(BB) == end() && "Block already in DominanceFrontier!"); 459 Frontiers.insert(std::make_pair(BB, frontier)); 460 } 461 462 void addToFrontier(iterator I, BasicBlock *Node) { 463 assert(I != end() && "BB is not in DominanceFrontier!"); 464 I->second.insert(Node); 465 } 466 467 void removeFromFrontier(iterator I, BasicBlock *Node) { 468 assert(I != end() && "BB is not in DominanceFrontier!"); 469 assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB"); 470 I->second.erase(Node); 471 } 472 473 // print - Convert to human readable form 474 virtual void print(std::ostream &OS) const; 475}; 476 477 478//===------------------------------------- 479// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 480// compute a normal dominator tree. 481// 482struct DominanceFrontier : public DominanceFrontierBase { 483 DominanceFrontier() : DominanceFrontierBase(false) {} 484 485 BasicBlock *getRoot() const { 486 assert(Roots.size() == 1 && "Should always have entry node!"); 487 return Roots[0]; 488 } 489 490 virtual bool runOnFunction(Function &) { 491 Frontiers.clear(); 492 DominatorTree &DT = getAnalysis<DominatorTree>(); 493 Roots = DT.getRoots(); 494 assert(Roots.size() == 1 && "Only one entry block for forward domfronts!"); 495 calculate(DT, DT[Roots[0]]); 496 return false; 497 } 498 499 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 500 AU.setPreservesAll(); 501 AU.addRequired<DominatorTree>(); 502 } 503private: 504 const DomSetType &calculate(const DominatorTree &DT, 505 const DominatorTree::Node *Node); 506}; 507 508} // End llvm namespace 509 510#endif 511