Dominators.h revision 4f1bd9e9963239c119db70070db1d68286b3de7e
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/// 143class ImmediateDominators : public ImmediateDominatorsBase { 144public: 145 ImmediateDominators() : ImmediateDominatorsBase(false) {} 146 147 BasicBlock *getRoot() const { 148 assert(Roots.size() == 1 && "Should always have entry node!"); 149 return Roots[0]; 150 } 151 152 virtual bool runOnFunction(Function &F); 153 154 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 155 AU.setPreservesAll(); 156 } 157 158private: 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); 163}; 164 165 166 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. 172/// 173class DominatorSetBase : public DominatorBase { 174public: 175 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 176 // Map of dom sets 177 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; 178protected: 179 DomSetMapType Doms; 180public: 181 DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {} 182 183 virtual void releaseMemory() { Doms.clear(); } 184 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); } 194 195 196 /// getDominators - Return the set of basic blocks that dominate the specified 197 /// block. 198 /// 199 inline const DomSetType &getDominators(BasicBlock *BB) const { 200 const_iterator I = find(BB); 201 assert(I != end() && "BB not in function!"); 202 return I->second; 203 } 204 205 /// isReachable - Return true if the specified basicblock is reachable. If 206 /// the block is reachable, we have dominator set information for it. 207 /// 208 bool isReachable(BasicBlock *BB) const { 209 return !getDominators(BB).empty(); 210 } 211 212 /// dominates - Return true if A dominates B. 213 /// 214 inline bool dominates(BasicBlock *A, BasicBlock *B) const { 215 return getDominators(B).count(A) != 0; 216 } 217 218 /// properlyDominates - Return true if A dominates B and A != B. 219 /// 220 bool properlyDominates(BasicBlock *A, BasicBlock *B) const { 221 return dominates(A, B) && A != B; 222 } 223 224 /// print - Convert to human readable form 225 /// 226 virtual void print(std::ostream &OS, const Module* = 0) const; 227 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. 230 /// 231 bool dominates(Instruction *A, Instruction *B) const; 232 233 //===--------------------------------------------------------------------===// 234 // API to update (Post)DominatorSet information based on modifications to 235 // the CFG... 236 237 /// addBasicBlock - Call to update the dominator set with information about a 238 /// new block that was inserted into the function. 239 /// 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)); 243 } 244 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. 247 /// 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); 252 } 253}; 254 255 256//===------------------------------------- 257/// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to 258/// compute a normal dominator set. 259/// 260class DominatorSet : public DominatorSetBase { 261public: 262 DominatorSet() : DominatorSetBase(false) {} 263 264 virtual bool runOnFunction(Function &F); 265 266 BasicBlock *getRoot() const { 267 assert(Roots.size() == 1 && "Should always have entry node!"); 268 return Roots[0]; 269 } 270 271 /// getAnalysisUsage - This simply provides a dominator set 272 /// 273 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 274 AU.addRequired<ImmediateDominators>(); 275 AU.setPreservesAll(); 276 } 277 278 // stub - dummy function, just ignore it 279 static int stub; 280}; 281 282 283//===----------------------------------------------------------------------===// 284/// DominatorTree - Calculate the immediate dominator tree for a function. 285/// 286class DominatorTreeBase : public DominatorBase { 287public: 288 class Node; 289protected: 290 std::map<BasicBlock*, Node*> Nodes; 291 void reset(); 292 typedef std::map<BasicBlock*, Node*> NodeMapType; 293 294 Node *RootNode; 295public: 296 class Node { 297 friend struct DominatorTree; 298 friend struct PostDominatorTree; 299 friend struct DominatorTreeBase; 300 BasicBlock *TheBB; 301 Node *IDom; 302 std::vector<Node*> Children; 303 public: 304 typedef std::vector<Node*>::iterator iterator; 305 typedef std::vector<Node*>::const_iterator const_iterator; 306 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(); } 311 312 inline BasicBlock *getBlock() const { return TheBB; } 313 inline Node *getIDom() const { return IDom; } 314 inline const std::vector<Node*> &getChildren() const { return Children; } 315 316 /// properlyDominates - Returns true iff this dominates N and this != N. 317 /// Note that this is not a constant time operation! 318 /// 319 bool properlyDominates(const Node *N) const { 320 const Node *IDom; 321 if (this == 0 || N == 0) return false; 322 while ((IDom = N->getIDom()) != 0 && IDom != this) 323 N = IDom; // Walk up the tree 324 return IDom != 0; 325 } 326 327 /// dominates - Returns true iff this dominates N. Note that this is not a 328 /// constant time operation! 329 /// 330 inline bool dominates(const Node *N) const { 331 if (N == this) return true; // A node trivially dominates itself. 332 return properlyDominates(N); 333 } 334 335 private: 336 inline Node(BasicBlock *BB, Node *iDom) : TheBB(BB), IDom(iDom) {} 337 inline Node *addChild(Node *C) { Children.push_back(C); return C; } 338 339 void setIDom(Node *NewIDom); 340 }; 341 342public: 343 DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {} 344 ~DominatorTreeBase() { reset(); } 345 346 virtual void releaseMemory() { reset(); } 347 348 /// getNode - return the (Post)DominatorTree node for the specified basic 349 /// block. This is the same as using operator[] on this class. 350 /// 351 inline Node *getNode(BasicBlock *BB) const { 352 NodeMapType::const_iterator i = Nodes.find(BB); 353 return (i != Nodes.end()) ? i->second : 0; 354 } 355 356 inline Node *operator[](BasicBlock *BB) const { 357 return getNode(BB); 358 } 359 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 365 /// possibility. 366 /// 367 Node *getRootNode() { return RootNode; } 368 const Node *getRootNode() const { return RootNode; } 369 370 //===--------------------------------------------------------------------===// 371 // API to update (Post)DominatorTree information based on modifications to 372 // the CFG... 373 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. 377 /// 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)); 382 } 383 384 /// changeImmediateDominator - This method is used to update the dominator 385 /// tree information when a node's immediate dominator changes. 386 /// 387 void changeImmediateDominator(Node *N, Node *NewIDom) { 388 assert(N && NewIDom && "Cannot change null node pointers!"); 389 N->setIDom(NewIDom); 390 } 391 392 /// print - Convert to human readable form 393 /// 394 virtual void print(std::ostream &OS, const Module* = 0) const; 395}; 396 397 398//===------------------------------------- 399/// ET-Forest Class - Class used to construct forwards and backwards 400/// ET-Forests 401/// 402class ETForestBase : public DominatorBase { 403public: 404 ETForestBase(bool isPostDom) : DominatorBase(isPostDom), Nodes(), 405 DFSInfoValid(false), SlowQueries(0) {} 406 407 virtual void releaseMemory() { reset(); } 408 409 typedef std::map<BasicBlock*, ETNode*> ETMapType; 410 411 void updateDFSNumbers(); 412 413 /// dominates - Return true if A dominates B. 414 /// 415 inline bool dominates(BasicBlock *A, BasicBlock *B) { 416 if (A == B) 417 return true; 418 419 ETNode *NodeA = getNode(A); 420 ETNode *NodeB = getNode(B); 421 422 if (DFSInfoValid) 423 return NodeB->DominatedBy(NodeA); 424 else { 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. 427 SlowQueries++; 428 if (SlowQueries > 32) { 429 updateDFSNumbers(); 430 return NodeB->DominatedBy(NodeA); 431 } 432 return NodeB->DominatedBySlow(NodeA); 433 } 434 } 435 436 /// properlyDominates - Return true if A dominates B and A != B. 437 /// 438 bool properlyDominates(BasicBlock *A, BasicBlock *B) { 439 return dominates(A, B) && A != B; 440 } 441 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); 446 447 ETNode *Common = NodeA->NCA(NodeB); 448 if (!Common) 449 return NULL; 450 return Common->getData<BasicBlock>(); 451 } 452 453 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 454 AU.setPreservesAll(); 455 AU.addRequired<ImmediateDominators>(); 456 } 457 //===--------------------------------------------------------------------===// 458 // API to update Forest information based on modifications 459 // to the CFG... 460 461 /// addNewBlock - Add a new block to the CFG, with the specified immediate 462 /// dominator. 463 /// 464 void addNewBlock(BasicBlock *BB, BasicBlock *IDom); 465 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. 470 /// 471 void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom); 472 /// print - Convert to human readable form 473 /// 474 virtual void print(std::ostream &OS, const Module* = 0) const; 475protected: 476 /// getNode - return the (Post)DominatorTree node for the specified basic 477 /// block. This is the same as using operator[] on this class. 478 /// 479 inline ETNode *getNode(BasicBlock *BB) const { 480 ETMapType::const_iterator i = Nodes.find(BB); 481 return (i != Nodes.end()) ? i->second : 0; 482 } 483 484 inline ETNode *operator[](BasicBlock *BB) const { 485 return getNode(BB); 486 } 487 488 void reset(); 489 ETMapType Nodes; 490 bool DFSInfoValid; 491 unsigned int SlowQueries; 492 493}; 494 495//==------------------------------------- 496/// ETForest Class - Concrete subclass of ETForestBase that is used to 497/// compute a forwards ET-Forest. 498 499class ETForest : public ETForestBase { 500public: 501 ETForest() : ETForestBase(false) {} 502 503 BasicBlock *getRoot() const { 504 assert(Roots.size() == 1 && "Should always have entry node!"); 505 return Roots[0]; 506 } 507 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(); 512 calculate(ID); 513 return false; 514 } 515 516 void calculate(const ImmediateDominators &ID); 517 ETNode *getNodeForBlock(BasicBlock *BB); 518}; 519 520//===------------------------------------- 521/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 522/// compute a normal dominator tree. 523/// 524class DominatorTree : public DominatorTreeBase { 525public: 526 DominatorTree() : DominatorTreeBase(false) {} 527 528 BasicBlock *getRoot() const { 529 assert(Roots.size() == 1 && "Should always have entry node!"); 530 return Roots[0]; 531 } 532 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(); 537 calculate(ID); 538 return false; 539 } 540 541 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 542 AU.setPreservesAll(); 543 AU.addRequired<ImmediateDominators>(); 544 } 545private: 546 void calculate(const ImmediateDominators &ID); 547 Node *getNodeForBlock(BasicBlock *BB); 548}; 549 550//===------------------------------------- 551/// DominatorTree GraphTraits specialization so the DominatorTree can be 552/// iterable by generic graph iterators. 553/// 554template <> struct GraphTraits<DominatorTree::Node*> { 555 typedef DominatorTree::Node NodeType; 556 typedef NodeType::iterator ChildIteratorType; 557 558 static NodeType *getEntryNode(NodeType *N) { 559 return N; 560 } 561 static inline ChildIteratorType child_begin(NodeType* N) { 562 return N->begin(); 563 } 564 static inline ChildIteratorType child_end(NodeType* N) { 565 return N->end(); 566 } 567}; 568 569template <> struct GraphTraits<DominatorTree*> 570 : public GraphTraits<DominatorTree::Node*> { 571 static NodeType *getEntryNode(DominatorTree *DT) { 572 return DT->getRootNode(); 573 } 574}; 575 576//===----------------------------------------------------------------------===// 577/// DominanceFrontierBase - Common base class for computing forward and inverse 578/// dominance frontiers for a function. 579/// 580class DominanceFrontierBase : public DominatorBase { 581public: 582 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 583 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map 584protected: 585 DomSetMapType Frontiers; 586public: 587 DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {} 588 589 virtual void releaseMemory() { Frontiers.clear(); } 590 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); } 600 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)); 604 } 605 606 void addToFrontier(iterator I, BasicBlock *Node) { 607 assert(I != end() && "BB is not in DominanceFrontier!"); 608 I->second.insert(Node); 609 } 610 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); 615 } 616 617 /// print - Convert to human readable form 618 /// 619 virtual void print(std::ostream &OS, const Module* = 0) const; 620}; 621 622 623//===------------------------------------- 624/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is 625/// used to compute a forward dominator frontiers. 626/// 627class DominanceFrontier : public DominanceFrontierBase { 628public: 629 DominanceFrontier() : DominanceFrontierBase(false) {} 630 631 BasicBlock *getRoot() const { 632 assert(Roots.size() == 1 && "Should always have entry node!"); 633 return Roots[0]; 634 } 635 636 virtual bool runOnFunction(Function &) { 637 Frontiers.clear(); 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]]); 642 return false; 643 } 644 645 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 646 AU.setPreservesAll(); 647 AU.addRequired<DominatorTree>(); 648 } 649private: 650 const DomSetType &calculate(const DominatorTree &DT, 651 const DominatorTree::Node *Node); 652}; 653 654 655} // End llvm namespace 656 657// Make sure that any clients of this file link in Dominators.cpp 658FORCE_DEFINING_FILE_TO_BE_LINKED(DominatorSet) 659 660#endif 661