Dominators.h revision 26d5d16a2c8ef6c0763afbfe06c940c40c461d6e
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. ETForest: Efficient data structure for dominance comparisons and 17// nearest-common-ancestor queries. 18// 5. DominanceFrontier: Calculate and hold the dominance frontier for a 19// function. 20// 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. 24// 25//===----------------------------------------------------------------------===// 26 27#ifndef LLVM_ANALYSIS_DOMINATORS_H 28#define LLVM_ANALYSIS_DOMINATORS_H 29 30#include "llvm/Analysis/ET-Forest.h" 31#include "llvm/Pass.h" 32#include <set> 33 34namespace llvm { 35 36class Instruction; 37 38template <typename GraphType> struct GraphTraits; 39 40//===----------------------------------------------------------------------===// 41/// DominatorBase - Base class that other, more interesting dominator analyses 42/// inherit from. 43/// 44class DominatorBase : public FunctionPass { 45protected: 46 std::vector<BasicBlock*> Roots; 47 const bool IsPostDominators; 48 49 inline DominatorBase(bool isPostDom) : Roots(), IsPostDominators(isPostDom) {} 50public: 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). 54 /// 55 inline const std::vector<BasicBlock*> &getRoots() const { return Roots; } 56 57 /// isPostDominator - Returns true if analysis based of postdoms 58 /// 59 bool isPostDominator() const { return IsPostDominators; } 60}; 61 62 63//===----------------------------------------------------------------------===// 64/// ImmediateDominators - Calculate the immediate dominator for each node in a 65/// function. 66/// 67class ImmediateDominatorsBase : public DominatorBase { 68protected: 69 struct InfoRec { 70 unsigned Semi; 71 unsigned Size; 72 BasicBlock *Label, *Parent, *Child, *Ancestor; 73 74 std::vector<BasicBlock*> Bucket; 75 76 InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){} 77 }; 78 79 std::map<BasicBlock*, BasicBlock*> IDoms; 80 81 // Vertex - Map the DFS number to the BasicBlock* 82 std::vector<BasicBlock*> Vertex; 83 84 // Info - Collection of information used during the computation of idoms. 85 std::map<BasicBlock*, InfoRec> Info; 86public: 87 ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {} 88 89 virtual void releaseMemory() { IDoms.clear(); } 90 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);} 97 98 /// operator[] - Return the idom for the specified basic block. The start 99 /// node returns null, because it does not have an immediate dominator. 100 /// 101 inline BasicBlock *operator[](BasicBlock *BB) const { 102 return get(BB); 103 } 104 105 /// get() - Synonym for operator[]. 106 /// 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; 110 } 111 112 //===--------------------------------------------------------------------===// 113 // API to update Immediate(Post)Dominators information based on modifications 114 // to the CFG... 115 116 /// addNewBlock - Add a new block to the CFG, with the specified immediate 117 /// dominator. 118 /// 119 void addNewBlock(BasicBlock *BB, BasicBlock *IDom) { 120 assert(get(BB) == 0 && "BasicBlock already in idom info!"); 121 IDoms[BB] = IDom; 122 } 123 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 127 /// use addNewBlock. 128 /// 129 void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) { 130 assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!"); 131 IDoms[BB] = NewIDom; 132 } 133 134 /// print - Convert to human readable form 135 /// 136 virtual void print(std::ostream &OS, const Module* = 0) const; 137}; 138 139//===------------------------------------- 140/// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase 141/// that is used to compute a normal immediate dominator set. 142/// 143struct ImmediateDominators : public ImmediateDominatorsBase { 144 ImmediateDominators() : ImmediateDominatorsBase(false) {} 145 146 BasicBlock *getRoot() const { 147 assert(Roots.size() == 1 && "Should always have entry node!"); 148 return Roots[0]; 149 } 150 151 virtual bool runOnFunction(Function &F); 152 153 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 154 AU.setPreservesAll(); 155 } 156 157private: 158 unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N); 159 void Compress(BasicBlock *V, InfoRec &VInfo); 160 BasicBlock *Eval(BasicBlock *v); 161 void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo); 162}; 163 164 165 166//===----------------------------------------------------------------------===// 167/// DominatorSet - Maintain a set<BasicBlock*> for every basic block in a 168/// function, that represents the blocks that dominate the block. If the block 169/// is unreachable in this function, the set will be empty. This cannot happen 170/// for reachable code, because every block dominates at least itself. 171/// 172struct DominatorSetBase : public DominatorBase { 173 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 174 // Map of dom sets 175 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; 176protected: 177 DomSetMapType Doms; 178public: 179 DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {} 180 181 virtual void releaseMemory() { Doms.clear(); } 182 183 // Accessor interface: 184 typedef DomSetMapType::const_iterator const_iterator; 185 typedef DomSetMapType::iterator iterator; 186 inline const_iterator begin() const { return Doms.begin(); } 187 inline iterator begin() { return Doms.begin(); } 188 inline const_iterator end() const { return Doms.end(); } 189 inline iterator end() { return Doms.end(); } 190 inline const_iterator find(BasicBlock* B) const { return Doms.find(B); } 191 inline iterator find(BasicBlock* B) { return Doms.find(B); } 192 193 194 /// getDominators - Return the set of basic blocks that dominate the specified 195 /// block. 196 /// 197 inline const DomSetType &getDominators(BasicBlock *BB) const { 198 const_iterator I = find(BB); 199 assert(I != end() && "BB not in function!"); 200 return I->second; 201 } 202 203 /// isReachable - Return true if the specified basicblock is reachable. If 204 /// the block is reachable, we have dominator set information for it. 205 /// 206 bool isReachable(BasicBlock *BB) const { 207 return !getDominators(BB).empty(); 208 } 209 210 /// dominates - Return true if A dominates B. 211 /// 212 inline bool dominates(BasicBlock *A, BasicBlock *B) const { 213 return getDominators(B).count(A) != 0; 214 } 215 216 /// properlyDominates - Return true if A dominates B and A != B. 217 /// 218 bool properlyDominates(BasicBlock *A, BasicBlock *B) const { 219 return dominates(A, B) && A != B; 220 } 221 222 /// print - Convert to human readable form 223 /// 224 virtual void print(std::ostream &OS, const Module* = 0) const; 225 226 /// dominates - Return true if A dominates B. This performs the special 227 /// checks necessary if A and B are in the same basic block. 228 /// 229 bool dominates(Instruction *A, Instruction *B) const; 230 231 //===--------------------------------------------------------------------===// 232 // API to update (Post)DominatorSet information based on modifications to 233 // the CFG... 234 235 /// addBasicBlock - Call to update the dominator set with information about a 236 /// new block that was inserted into the function. 237 /// 238 void addBasicBlock(BasicBlock *BB, const DomSetType &Dominators) { 239 assert(find(BB) == end() && "Block already in DominatorSet!"); 240 Doms.insert(std::make_pair(BB, Dominators)); 241 } 242 243 /// addDominator - If a new block is inserted into the CFG, then method may be 244 /// called to notify the blocks it dominates that it is in their set. 245 /// 246 void addDominator(BasicBlock *BB, BasicBlock *NewDominator) { 247 iterator I = find(BB); 248 assert(I != end() && "BB is not in DominatorSet!"); 249 I->second.insert(NewDominator); 250 } 251}; 252 253 254//===------------------------------------- 255/// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to 256/// compute a normal dominator set. 257/// 258struct DominatorSet : public DominatorSetBase { 259 DominatorSet() : DominatorSetBase(false) {} 260 261 virtual bool runOnFunction(Function &F); 262 263 BasicBlock *getRoot() const { 264 assert(Roots.size() == 1 && "Should always have entry node!"); 265 return Roots[0]; 266 } 267 268 /// getAnalysisUsage - This simply provides a dominator set 269 /// 270 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 271 AU.addRequired<ImmediateDominators>(); 272 AU.setPreservesAll(); 273 } 274 275 // stub - dummy function, just ignore it 276 static void stub(); 277}; 278 279 280//===----------------------------------------------------------------------===// 281/// DominatorTree - Calculate the immediate dominator tree for a function. 282/// 283struct DominatorTreeBase : public DominatorBase { 284 class Node; 285protected: 286 std::map<BasicBlock*, Node*> Nodes; 287 void reset(); 288 typedef std::map<BasicBlock*, Node*> NodeMapType; 289 290 Node *RootNode; 291public: 292 class Node { 293 friend struct DominatorTree; 294 friend struct PostDominatorTree; 295 friend struct DominatorTreeBase; 296 BasicBlock *TheBB; 297 Node *IDom; 298 std::vector<Node*> Children; 299 public: 300 typedef std::vector<Node*>::iterator iterator; 301 typedef std::vector<Node*>::const_iterator const_iterator; 302 303 iterator begin() { return Children.begin(); } 304 iterator end() { return Children.end(); } 305 const_iterator begin() const { return Children.begin(); } 306 const_iterator end() const { return Children.end(); } 307 308 inline BasicBlock *getBlock() const { return TheBB; } 309 inline Node *getIDom() const { return IDom; } 310 inline const std::vector<Node*> &getChildren() const { return Children; } 311 312 /// properlyDominates - Returns true iff this dominates N and this != N. 313 /// Note that this is not a constant time operation! 314 /// 315 bool properlyDominates(const Node *N) const { 316 const Node *IDom; 317 if (this == 0 || N == 0) return false; 318 while ((IDom = N->getIDom()) != 0 && IDom != this) 319 N = IDom; // Walk up the tree 320 return IDom != 0; 321 } 322 323 /// dominates - Returns true iff this dominates N. Note that this is not a 324 /// constant time operation! 325 /// 326 inline bool dominates(const Node *N) const { 327 if (N == this) return true; // A node trivially dominates itself. 328 return properlyDominates(N); 329 } 330 331 private: 332 inline Node(BasicBlock *BB, Node *iDom) : TheBB(BB), IDom(iDom) {} 333 inline Node *addChild(Node *C) { Children.push_back(C); return C; } 334 335 void setIDom(Node *NewIDom); 336 }; 337 338public: 339 DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {} 340 ~DominatorTreeBase() { reset(); } 341 342 virtual void releaseMemory() { reset(); } 343 344 /// getNode - return the (Post)DominatorTree node for the specified basic 345 /// block. This is the same as using operator[] on this class. 346 /// 347 inline Node *getNode(BasicBlock *BB) const { 348 NodeMapType::const_iterator i = Nodes.find(BB); 349 return (i != Nodes.end()) ? i->second : 0; 350 } 351 352 inline Node *operator[](BasicBlock *BB) const { 353 return getNode(BB); 354 } 355 356 /// getRootNode - This returns the entry node for the CFG of the function. If 357 /// this tree represents the post-dominance relations for a function, however, 358 /// this root may be a node with the block == NULL. This is the case when 359 /// there are multiple exit nodes from a particular function. Consumers of 360 /// post-dominance information must be capable of dealing with this 361 /// possibility. 362 /// 363 Node *getRootNode() { return RootNode; } 364 const Node *getRootNode() const { return RootNode; } 365 366 //===--------------------------------------------------------------------===// 367 // API to update (Post)DominatorTree information based on modifications to 368 // the CFG... 369 370 /// createNewNode - Add a new node to the dominator tree information. This 371 /// creates a new node as a child of IDomNode, linking it into the children 372 /// list of the immediate dominator. 373 /// 374 Node *createNewNode(BasicBlock *BB, Node *IDomNode) { 375 assert(getNode(BB) == 0 && "Block already in dominator tree!"); 376 assert(IDomNode && "Not immediate dominator specified for block!"); 377 return Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode)); 378 } 379 380 /// changeImmediateDominator - This method is used to update the dominator 381 /// tree information when a node's immediate dominator changes. 382 /// 383 void changeImmediateDominator(Node *N, Node *NewIDom) { 384 assert(N && NewIDom && "Cannot change null node pointers!"); 385 N->setIDom(NewIDom); 386 } 387 388 /// print - Convert to human readable form 389 /// 390 virtual void print(std::ostream &OS, const Module* = 0) const; 391}; 392 393 394//===------------------------------------- 395/// ET-Forest Class - Class used to construct forwards and backwards 396/// ET-Forests 397/// 398struct ETForestBase : public DominatorBase { 399 ETForestBase(bool isPostDom) : DominatorBase(isPostDom), Nodes(), 400 DFSInfoValid(false), SlowQueries(0) {} 401 402 virtual void releaseMemory() { reset(); } 403 404 typedef std::map<BasicBlock*, ETNode*> ETMapType; 405 406 void updateDFSNumbers(); 407 408 /// dominates - Return true if A dominates B. 409 /// 410 inline bool dominates(BasicBlock *A, BasicBlock *B) { 411 if (A == B) 412 return true; 413 414 ETNode *NodeA = getNode(A); 415 ETNode *NodeB = getNode(B); 416 417 if (DFSInfoValid) 418 return NodeB->DominatedBy(NodeA); 419 else { 420 // If we end up with too many slow queries, just update the 421 // DFS numbers on the theory that we are going to keep querying. 422 SlowQueries++; 423 if (SlowQueries > 32) { 424 updateDFSNumbers(); 425 return NodeB->DominatedBy(NodeA); 426 } 427 return NodeB->DominatedBySlow(NodeA); 428 } 429 } 430 431 /// properlyDominates - Return true if A dominates B and A != B. 432 /// 433 bool properlyDominates(BasicBlock *A, BasicBlock *B) { 434 return dominates(A, B) && A != B; 435 } 436 437 /// Return the nearest common dominator of A and B. 438 BasicBlock *nearestCommonDominator(BasicBlock *A, BasicBlock *B) const { 439 ETNode *NodeA = getNode(A); 440 ETNode *NodeB = getNode(B); 441 442 ETNode *Common = NodeA->NCA(NodeB); 443 if (!Common) 444 return NULL; 445 return Common->getData<BasicBlock>(); 446 } 447 448 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 449 AU.setPreservesAll(); 450 AU.addRequired<ImmediateDominators>(); 451 } 452 //===--------------------------------------------------------------------===// 453 // API to update Forest information based on modifications 454 // to the CFG... 455 456 /// addNewBlock - Add a new block to the CFG, with the specified immediate 457 /// dominator. 458 /// 459 void addNewBlock(BasicBlock *BB, BasicBlock *IDom); 460 461 /// setImmediateDominator - Update the immediate dominator information to 462 /// change the current immediate dominator for the specified block 463 /// to another block. This method requires that BB for NewIDom 464 /// already have an ETNode, otherwise just use addNewBlock. 465 /// 466 void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom); 467 /// print - Convert to human readable form 468 /// 469 virtual void print(std::ostream &OS, const Module* = 0) const; 470protected: 471 /// getNode - return the (Post)DominatorTree node for the specified basic 472 /// block. This is the same as using operator[] on this class. 473 /// 474 inline ETNode *getNode(BasicBlock *BB) const { 475 ETMapType::const_iterator i = Nodes.find(BB); 476 return (i != Nodes.end()) ? i->second : 0; 477 } 478 479 inline ETNode *operator[](BasicBlock *BB) const { 480 return getNode(BB); 481 } 482 483 void reset(); 484 ETMapType Nodes; 485 bool DFSInfoValid; 486 unsigned int SlowQueries; 487 488}; 489 490//==------------------------------------- 491/// ETForest Class - Concrete subclass of ETForestBase that is used to 492/// compute a forwards ET-Forest. 493 494struct ETForest : public ETForestBase { 495 ETForest() : ETForestBase(false) {} 496 497 BasicBlock *getRoot() const { 498 assert(Roots.size() == 1 && "Should always have entry node!"); 499 return Roots[0]; 500 } 501 502 virtual bool runOnFunction(Function &F) { 503 reset(); // Reset from the last time we were run... 504 ImmediateDominators &ID = getAnalysis<ImmediateDominators>(); 505 Roots = ID.getRoots(); 506 calculate(ID); 507 return false; 508 } 509 510 void calculate(const ImmediateDominators &ID); 511 ETNode *getNodeForBlock(BasicBlock *BB); 512}; 513 514//===------------------------------------- 515/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 516/// compute a normal dominator tree. 517/// 518struct DominatorTree : public DominatorTreeBase { 519 DominatorTree() : DominatorTreeBase(false) {} 520 521 BasicBlock *getRoot() const { 522 assert(Roots.size() == 1 && "Should always have entry node!"); 523 return Roots[0]; 524 } 525 526 virtual bool runOnFunction(Function &F) { 527 reset(); // Reset from the last time we were run... 528 ImmediateDominators &ID = getAnalysis<ImmediateDominators>(); 529 Roots = ID.getRoots(); 530 calculate(ID); 531 return false; 532 } 533 534 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 535 AU.setPreservesAll(); 536 AU.addRequired<ImmediateDominators>(); 537 } 538private: 539 void calculate(const ImmediateDominators &ID); 540 Node *getNodeForBlock(BasicBlock *BB); 541}; 542 543//===------------------------------------- 544/// DominatorTree GraphTraits specialization so the DominatorTree can be 545/// iterable by generic graph iterators. 546/// 547template <> struct GraphTraits<DominatorTree::Node*> { 548 typedef DominatorTree::Node NodeType; 549 typedef NodeType::iterator ChildIteratorType; 550 551 static NodeType *getEntryNode(NodeType *N) { 552 return N; 553 } 554 static inline ChildIteratorType child_begin(NodeType* N) { 555 return N->begin(); 556 } 557 static inline ChildIteratorType child_end(NodeType* N) { 558 return N->end(); 559 } 560}; 561 562template <> struct GraphTraits<DominatorTree*> 563 : public GraphTraits<DominatorTree::Node*> { 564 static NodeType *getEntryNode(DominatorTree *DT) { 565 return DT->getRootNode(); 566 } 567}; 568 569//===----------------------------------------------------------------------===// 570/// DominanceFrontier - Calculate the dominance frontiers for a function. 571/// 572struct DominanceFrontierBase : public DominatorBase { 573 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 574 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map 575protected: 576 DomSetMapType Frontiers; 577public: 578 DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {} 579 580 virtual void releaseMemory() { Frontiers.clear(); } 581 582 // Accessor interface: 583 typedef DomSetMapType::iterator iterator; 584 typedef DomSetMapType::const_iterator const_iterator; 585 iterator begin() { return Frontiers.begin(); } 586 const_iterator begin() const { return Frontiers.begin(); } 587 iterator end() { return Frontiers.end(); } 588 const_iterator end() const { return Frontiers.end(); } 589 iterator find(BasicBlock *B) { return Frontiers.find(B); } 590 const_iterator find(BasicBlock *B) const { return Frontiers.find(B); } 591 592 void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) { 593 assert(find(BB) == end() && "Block already in DominanceFrontier!"); 594 Frontiers.insert(std::make_pair(BB, frontier)); 595 } 596 597 void addToFrontier(iterator I, BasicBlock *Node) { 598 assert(I != end() && "BB is not in DominanceFrontier!"); 599 I->second.insert(Node); 600 } 601 602 void removeFromFrontier(iterator I, BasicBlock *Node) { 603 assert(I != end() && "BB is not in DominanceFrontier!"); 604 assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB"); 605 I->second.erase(Node); 606 } 607 608 /// print - Convert to human readable form 609 /// 610 virtual void print(std::ostream &OS, const Module* = 0) const; 611}; 612 613 614//===------------------------------------- 615/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 616/// compute a normal dominator tree. 617/// 618struct DominanceFrontier : public DominanceFrontierBase { 619 DominanceFrontier() : DominanceFrontierBase(false) {} 620 621 BasicBlock *getRoot() const { 622 assert(Roots.size() == 1 && "Should always have entry node!"); 623 return Roots[0]; 624 } 625 626 virtual bool runOnFunction(Function &) { 627 Frontiers.clear(); 628 DominatorTree &DT = getAnalysis<DominatorTree>(); 629 Roots = DT.getRoots(); 630 assert(Roots.size() == 1 && "Only one entry block for forward domfronts!"); 631 calculate(DT, DT[Roots[0]]); 632 return false; 633 } 634 635 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 636 AU.setPreservesAll(); 637 AU.addRequired<DominatorTree>(); 638 } 639private: 640 const DomSetType &calculate(const DominatorTree &DT, 641 const DominatorTree::Node *Node); 642}; 643 644 645// Make sure that any clients of this file link in Dominators.cpp 646static IncludeFile 647DOMINATORS_INCLUDE_FILE((void*)&DominatorSet::stub); 648} // End llvm namespace 649 650#endif 651