Dominators.h revision 05d2318fbde7b603bd6de690f18d48e0ef44d81d
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. DominatorTree: Represent dominators as an explicit tree structure. 12// 2. DominanceFrontier: Calculate and hold the dominance frontier for a 13// function. 14// 15// These data structures are listed in increasing order of complexity. It 16// takes longer to calculate the dominator frontier, for example, than the 17// DominatorTree mapping. 18// 19//===----------------------------------------------------------------------===// 20 21#ifndef LLVM_ANALYSIS_DOMINATORS_H 22#define LLVM_ANALYSIS_DOMINATORS_H 23 24#include "llvm/Pass.h" 25#include "llvm/Instruction.h" 26#include "llvm/Instructions.h" 27#include "llvm/ADT/DenseMap.h" 28#include "llvm/ADT/SmallPtrSet.h" 29#include "llvm/ADT/SmallVector.h" 30#include "llvm/Assembly/Writer.h" 31#include "llvm/Support/Compiler.h" 32#include <algorithm> 33#include <set> 34 35namespace llvm { 36 37template <typename GraphType> struct GraphTraits; 38 39//===----------------------------------------------------------------------===// 40/// DominatorBase - Base class that other, more interesting dominator analyses 41/// inherit from. 42/// 43template <class NodeT> 44class DominatorBase : public FunctionPass { 45protected: 46 std::vector<NodeT*> Roots; 47 const bool IsPostDominators; 48 inline DominatorBase(intptr_t ID, bool isPostDom) : 49 FunctionPass(ID), Roots(), IsPostDominators(isPostDom) {} 50public: 51 52 /// getRoots - Return the root blocks of the current CFG. This may include 53 /// multiple blocks if we are computing post dominators. For forward 54 /// dominators, this will always be a single block (the entry node). 55 /// 56 inline const std::vector<NodeT*> &getRoots() const { return Roots; } 57 58 /// isPostDominator - Returns true if analysis based of postdoms 59 /// 60 bool isPostDominator() const { return IsPostDominators; } 61}; 62 63 64//===----------------------------------------------------------------------===// 65// DomTreeNode - Dominator Tree Node 66template<class NodeT> class DominatorTreeBase; 67class PostDominatorTree; 68class MachineBasicBlock; 69 70template <class NodeT> 71class DomTreeNodeBase { 72 NodeT *TheBB; 73 DomTreeNodeBase<NodeT> *IDom; 74 std::vector<DomTreeNodeBase<NodeT> *> Children; 75 int DFSNumIn, DFSNumOut; 76 77 template<class N> friend class DominatorTreeBase; 78 friend class PostDominatorTree; 79public: 80 typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator; 81 typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator 82 const_iterator; 83 84 iterator begin() { return Children.begin(); } 85 iterator end() { return Children.end(); } 86 const_iterator begin() const { return Children.begin(); } 87 const_iterator end() const { return Children.end(); } 88 89 NodeT *getBlock() const { return TheBB; } 90 DomTreeNodeBase<NodeT> *getIDom() const { return IDom; } 91 const std::vector<DomTreeNodeBase<NodeT>*> &getChildren() const { 92 return Children; 93 } 94 95 DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom) 96 : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { } 97 98 DomTreeNodeBase<NodeT> *addChild(DomTreeNodeBase<NodeT> *C) { 99 Children.push_back(C); 100 return C; 101 } 102 103 void setIDom(DomTreeNodeBase<NodeT> *NewIDom) { 104 assert(IDom && "No immediate dominator?"); 105 if (IDom != NewIDom) { 106 std::vector<DomTreeNodeBase<BasicBlock>*>::iterator I = 107 std::find(IDom->Children.begin(), IDom->Children.end(), this); 108 assert(I != IDom->Children.end() && 109 "Not in immediate dominator children set!"); 110 // I am no longer your child... 111 IDom->Children.erase(I); 112 113 // Switch to new dominator 114 IDom = NewIDom; 115 IDom->Children.push_back(this); 116 } 117 } 118 119 /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do 120 /// not call them. 121 unsigned getDFSNumIn() const { return DFSNumIn; } 122 unsigned getDFSNumOut() const { return DFSNumOut; } 123private: 124 // Return true if this node is dominated by other. Use this only if DFS info 125 // is valid. 126 bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const { 127 return this->DFSNumIn >= other->DFSNumIn && 128 this->DFSNumOut <= other->DFSNumOut; 129 } 130}; 131 132EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>); 133 134template<class NodeT> 135static std::ostream &operator<<(std::ostream &o, 136 const DomTreeNodeBase<NodeT> *Node) { 137 if (Node->getBlock()) 138 WriteAsOperand(o, Node->getBlock(), false); 139 else 140 o << " <<exit node>>"; 141 142 o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}"; 143 144 return o << "\n"; 145} 146 147template<class NodeT> 148static void PrintDomTree(const DomTreeNodeBase<NodeT> *N, std::ostream &o, 149 unsigned Lev) { 150 o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N; 151 for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(), 152 E = N->end(); I != E; ++I) 153 PrintDomTree<NodeT>(*I, o, Lev+1); 154} 155 156typedef DomTreeNodeBase<BasicBlock> DomTreeNode; 157typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode; 158 159//===----------------------------------------------------------------------===// 160/// DominatorTree - Calculate the immediate dominator tree for a function. 161/// 162 163template<class N, class GraphT> 164void Split(DominatorTreeBase<typename GraphT::NodeType>& DT, 165 typename GraphT::NodeType* NewBB); 166 167template<class NodeT> 168class DominatorTreeBase : public DominatorBase<NodeT> { 169protected: 170 typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> DomTreeNodeMapType; 171 DomTreeNodeMapType DomTreeNodes; 172 DomTreeNodeBase<NodeT> *RootNode; 173 174 bool DFSInfoValid; 175 unsigned int SlowQueries; 176 // Information record used during immediate dominators computation. 177 struct InfoRec { 178 unsigned Semi; 179 unsigned Size; 180 NodeT *Label, *Parent, *Child, *Ancestor; 181 182 std::vector<NodeT*> Bucket; 183 184 InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0) {} 185 }; 186 187 DenseMap<NodeT*, NodeT*> IDoms; 188 189 // Vertex - Map the DFS number to the BasicBlock* 190 std::vector<NodeT*> Vertex; 191 192 // Info - Collection of information used during the computation of idoms. 193 DenseMap<NodeT*, InfoRec> Info; 194 195 void reset() { 196 for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(), 197 E = DomTreeNodes.end(); I != E; ++I) 198 delete I->second; 199 DomTreeNodes.clear(); 200 IDoms.clear(); 201 this->Roots.clear(); 202 Vertex.clear(); 203 RootNode = 0; 204 } 205 206public: 207 DominatorTreeBase(intptr_t ID, bool isPostDom) 208 : DominatorBase<NodeT>(ID, isPostDom), DFSInfoValid(false), SlowQueries(0) {} 209 ~DominatorTreeBase() { reset(); } 210 211 virtual void releaseMemory() { reset(); } 212 213 /// getNode - return the (Post)DominatorTree node for the specified basic 214 /// block. This is the same as using operator[] on this class. 215 /// 216 inline DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const { 217 typename DomTreeNodeMapType::const_iterator I = DomTreeNodes.find(BB); 218 return I != DomTreeNodes.end() ? I->second : 0; 219 } 220 221 inline DomTreeNodeBase<NodeT> *operator[](NodeT *BB) const { 222 return getNode(BB); 223 } 224 225 /// getRootNode - This returns the entry node for the CFG of the function. If 226 /// this tree represents the post-dominance relations for a function, however, 227 /// this root may be a node with the block == NULL. This is the case when 228 /// there are multiple exit nodes from a particular function. Consumers of 229 /// post-dominance information must be capable of dealing with this 230 /// possibility. 231 /// 232 DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; } 233 const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; } 234 235 /// properlyDominates - Returns true iff this dominates N and this != N. 236 /// Note that this is not a constant time operation! 237 /// 238 bool properlyDominates(const DomTreeNodeBase<NodeT> *A, 239 DomTreeNodeBase<NodeT> *B) const { 240 if (A == 0 || B == 0) return false; 241 return dominatedBySlowTreeWalk(A, B); 242 } 243 244 inline bool properlyDominates(NodeT *A, NodeT *B) { 245 return properlyDominates(getNode(A), getNode(B)); 246 } 247 248 bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A, 249 const DomTreeNodeBase<NodeT> *B) const { 250 const DomTreeNodeBase<NodeT> *IDom; 251 if (A == 0 || B == 0) return false; 252 while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B) 253 B = IDom; // Walk up the tree 254 return IDom != 0; 255 } 256 257 258 /// isReachableFromEntry - Return true if A is dominated by the entry 259 /// block of the function containing it. 260 const bool isReachableFromEntry(NodeT* A) { 261 assert (!this->isPostDominator() 262 && "This is not implemented for post dominators"); 263 return dominates(&A->getParent()->getEntryBlock(), A); 264 } 265 266 /// dominates - Returns true iff A dominates B. Note that this is not a 267 /// constant time operation! 268 /// 269 inline bool dominates(const DomTreeNodeBase<NodeT> *A, 270 DomTreeNodeBase<NodeT> *B) { 271 if (B == A) 272 return true; // A node trivially dominates itself. 273 274 if (A == 0 || B == 0) 275 return false; 276 277 if (DFSInfoValid) 278 return B->DominatedBy(A); 279 280 // If we end up with too many slow queries, just update the 281 // DFS numbers on the theory that we are going to keep querying. 282 SlowQueries++; 283 if (SlowQueries > 32) { 284 updateDFSNumbers(); 285 return B->DominatedBy(A); 286 } 287 288 return dominatedBySlowTreeWalk(A, B); 289 } 290 291 inline bool dominates(NodeT *A, NodeT *B) { 292 if (A == B) 293 return true; 294 295 return dominates(getNode(A), getNode(B)); 296 } 297 298 /// findNearestCommonDominator - Find nearest common dominator basic block 299 /// for basic block A and B. If there is no such block then return NULL. 300 NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) { 301 302 assert (!this->isPostDominator() 303 && "This is not implemented for post dominators"); 304 assert (A->getParent() == B->getParent() 305 && "Two blocks are not in same function"); 306 307 // If either A or B is a entry block then it is nearest common dominator. 308 NodeT &Entry = A->getParent()->getEntryBlock(); 309 if (A == &Entry || B == &Entry) 310 return &Entry; 311 312 // If B dominates A then B is nearest common dominator. 313 if (dominates(B, A)) 314 return B; 315 316 // If A dominates B then A is nearest common dominator. 317 if (dominates(A, B)) 318 return A; 319 320 DomTreeNodeBase<NodeT> *NodeA = getNode(A); 321 DomTreeNodeBase<NodeT> *NodeB = getNode(B); 322 323 // Collect NodeA dominators set. 324 SmallPtrSet<DomTreeNodeBase<NodeT>*, 16> NodeADoms; 325 NodeADoms.insert(NodeA); 326 DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom(); 327 while (IDomA) { 328 NodeADoms.insert(IDomA); 329 IDomA = IDomA->getIDom(); 330 } 331 332 // Walk NodeB immediate dominators chain and find common dominator node. 333 DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom(); 334 while(IDomB) { 335 if (NodeADoms.count(IDomB) != 0) 336 return IDomB->getBlock(); 337 338 IDomB = IDomB->getIDom(); 339 } 340 341 return NULL; 342 } 343 344 // dominates - Return true if A dominates B. This performs the 345 // special checks necessary if A and B are in the same basic block. 346 bool dominates(Instruction *A, Instruction *B) { 347 NodeT *BBA = A->getParent(), *BBB = B->getParent(); 348 if (BBA != BBB) return this->dominates(BBA, BBB); 349 350 // It is not possible to determine dominance between two PHI nodes 351 // based on their ordering. 352 if (isa<PHINode>(A) && isa<PHINode>(B)) 353 return false; 354 355 // Loop through the basic block until we find A or B. 356 typename NodeT::iterator I = BBA->begin(); 357 for (; &*I != A && &*I != B; ++I) /*empty*/; 358 359 if(!this->IsPostDominators) { 360 // A dominates B if it is found first in the basic block. 361 return &*I == A; 362 } else { 363 // A post-dominates B if B is found first in the basic block. 364 return &*I == B; 365 } 366 } 367 368 //===--------------------------------------------------------------------===// 369 // API to update (Post)DominatorTree information based on modifications to 370 // the CFG... 371 372 /// addNewBlock - Add a new node to the dominator tree information. This 373 /// creates a new node as a child of DomBB dominator node,linking it into 374 /// the children list of the immediate dominator. 375 DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) { 376 assert(getNode(BB) == 0 && "Block already in dominator tree!"); 377 DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB); 378 assert(IDomNode && "Not immediate dominator specified for block!"); 379 DFSInfoValid = false; 380 return DomTreeNodes[BB] = 381 IDomNode->addChild(new DomTreeNode(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(DomTreeNodeBase<NodeT> *N, 388 DomTreeNodeBase<NodeT> *NewIDom) { 389 assert(N && NewIDom && "Cannot change null node pointers!"); 390 DFSInfoValid = false; 391 N->setIDom(NewIDom); 392 } 393 394 void changeImmediateDominator(NodeT *BB, NodeT *NewBB) { 395 changeImmediateDominator(getNode(BB), getNode(NewBB)); 396 } 397 398 /// eraseNode - Removes a node from the dominator tree. Block must not 399 /// domiante any other blocks. Removes node from its immediate dominator's 400 /// children list. Deletes dominator node associated with basic block BB. 401 void eraseNode(NodeT *BB) { 402 DomTreeNodeBase<NodeT> *Node = getNode(BB); 403 assert (Node && "Removing node that isn't in dominator tree."); 404 assert (Node->getChildren().empty() && "Node is not a leaf node."); 405 406 // Remove node from immediate dominator's children list. 407 DomTreeNodeBase<NodeT> *IDom = Node->getIDom(); 408 if (IDom) { 409 typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I = 410 std::find(IDom->Children.begin(), IDom->Children.end(), Node); 411 assert(I != IDom->Children.end() && 412 "Not in immediate dominator children set!"); 413 // I am no longer your child... 414 IDom->Children.erase(I); 415 } 416 417 DomTreeNodes.erase(BB); 418 delete Node; 419 } 420 421 /// removeNode - Removes a node from the dominator tree. Block must not 422 /// dominate any other blocks. Invalidates any node pointing to removed 423 /// block. 424 void removeNode(NodeT *BB) { 425 assert(getNode(BB) && "Removing node that isn't in dominator tree."); 426 DomTreeNodes.erase(BB); 427 } 428 429 /// print - Convert to human readable form 430 /// 431 virtual void print(std::ostream &o, const Module* ) const { 432 o << "=============================--------------------------------\n"; 433 o << "Inorder Dominator Tree: "; 434 if (this->DFSInfoValid) 435 o << "DFSNumbers invalid: " << SlowQueries << " slow queries."; 436 o << "\n"; 437 438 PrintDomTree<NodeT>(getRootNode(), o, 1); 439 } 440 441 void print(std::ostream *OS, const Module* M = 0) const { 442 if (OS) print(*OS, M); 443 } 444 445 virtual void dump() { 446 print(llvm::cerr); 447 } 448 449protected: 450 template<class GraphT> 451 friend void Compress(DominatorTreeBase<typename GraphT::NodeType>& DT, 452 typename GraphT::NodeType* VIn); 453 454 template<class GraphT> 455 friend typename GraphT::NodeType* Eval( 456 DominatorTreeBase<typename GraphT::NodeType>& DT, 457 typename GraphT::NodeType* V); 458 459 template<class GraphT> 460 friend void Link(DominatorTreeBase<typename GraphT::NodeType>& DT, 461 typename GraphT::NodeType* V, 462 typename GraphT::NodeType* W, 463 typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo); 464 465 template<class GraphT> 466 friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT, 467 typename GraphT::NodeType* V, 468 unsigned N); 469 470 template<class N, class GraphT> 471 friend void Calculate(DominatorTreeBase<typename GraphT::NodeType>& DT, 472 Function& F); 473 474 template<class N, class GraphT> 475 friend void Split(DominatorTreeBase<typename GraphT::NodeType>& DT, 476 typename GraphT::NodeType* NewBB); 477 478public: 479 /// splitBlock - BB is split and now it has one successor. Update dominator 480 /// tree to reflect this change. 481 void splitBlock(NodeT* NewBB) { 482 if (this->IsPostDominators) 483 Split<Inverse<NodeT*>, GraphTraits<Inverse<NodeT*> > >(*this, NewBB); 484 else 485 Split<NodeT*, GraphTraits<NodeT*> >(*this, NewBB); 486 } 487 488protected: 489 /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking 490 /// dominator tree in dfs order. 491 void updateDFSNumbers() { 492 unsigned DFSNum = 0; 493 494 SmallVector<std::pair<DomTreeNodeBase<NodeT>*, 495 typename DomTreeNodeBase<NodeT>::iterator>, 32> WorkStack; 496 497 for (unsigned i = 0, e = this->Roots.size(); i != e; ++i) { 498 DomTreeNodeBase<NodeT> *ThisRoot = getNode(this->Roots[i]); 499 WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin())); 500 ThisRoot->DFSNumIn = DFSNum++; 501 502 while (!WorkStack.empty()) { 503 DomTreeNodeBase<NodeT> *Node = WorkStack.back().first; 504 typename DomTreeNodeBase<NodeT>::iterator ChildIt = 505 WorkStack.back().second; 506 507 // If we visited all of the children of this node, "recurse" back up the 508 // stack setting the DFOutNum. 509 if (ChildIt == Node->end()) { 510 Node->DFSNumOut = DFSNum++; 511 WorkStack.pop_back(); 512 } else { 513 // Otherwise, recursively visit this child. 514 DomTreeNodeBase<NodeT> *Child = *ChildIt; 515 ++WorkStack.back().second; 516 517 WorkStack.push_back(std::make_pair(Child, Child->begin())); 518 Child->DFSNumIn = DFSNum++; 519 } 520 } 521 } 522 523 SlowQueries = 0; 524 DFSInfoValid = true; 525 } 526 527 DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) { 528 if (DomTreeNodeBase<NodeT> *BBNode = this->DomTreeNodes[BB]) 529 return BBNode; 530 531 // Haven't calculated this node yet? Get or calculate the node for the 532 // immediate dominator. 533 NodeT *IDom = getIDom(BB); 534 DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom); 535 536 // Add a new tree node for this BasicBlock, and link it as a child of 537 // IDomNode 538 DomTreeNodeBase<NodeT> *C = new DomTreeNodeBase<NodeT>(BB, IDomNode); 539 return this->DomTreeNodes[BB] = IDomNode->addChild(C); 540 } 541 542 inline NodeT *getIDom(NodeT *BB) const { 543 typename DenseMap<NodeT*, NodeT*>::const_iterator I = IDoms.find(BB); 544 return I != IDoms.end() ? I->second : 0; 545 } 546}; 547 548EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>); 549 550//===------------------------------------- 551/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 552/// compute a normal dominator tree. 553/// 554class DominatorTree : public DominatorTreeBase<BasicBlock> { 555public: 556 static char ID; // Pass ID, replacement for typeid 557 DominatorTree() : DominatorTreeBase<BasicBlock>(intptr_t(&ID), false) {} 558 559 BasicBlock *getRoot() const { 560 assert(Roots.size() == 1 && "Should always have entry node!"); 561 return Roots[0]; 562 } 563 564 virtual bool runOnFunction(Function &F); 565 566 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 567 AU.setPreservesAll(); 568 } 569}; 570 571//===------------------------------------- 572/// DominatorTree GraphTraits specialization so the DominatorTree can be 573/// iterable by generic graph iterators. 574/// 575template <> struct GraphTraits<DomTreeNode *> { 576 typedef DomTreeNode NodeType; 577 typedef NodeType::iterator ChildIteratorType; 578 579 static NodeType *getEntryNode(NodeType *N) { 580 return N; 581 } 582 static inline ChildIteratorType child_begin(NodeType* N) { 583 return N->begin(); 584 } 585 static inline ChildIteratorType child_end(NodeType* N) { 586 return N->end(); 587 } 588}; 589 590template <> struct GraphTraits<DominatorTree*> 591 : public GraphTraits<DomTreeNode *> { 592 static NodeType *getEntryNode(DominatorTree *DT) { 593 return DT->getRootNode(); 594 } 595}; 596 597 598//===----------------------------------------------------------------------===// 599/// DominanceFrontierBase - Common base class for computing forward and inverse 600/// dominance frontiers for a function. 601/// 602class DominanceFrontierBase : public DominatorBase<BasicBlock> { 603public: 604 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 605 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map 606protected: 607 DomSetMapType Frontiers; 608public: 609 DominanceFrontierBase(intptr_t ID, bool isPostDom) 610 : DominatorBase<BasicBlock>(ID, isPostDom) {} 611 612 virtual void releaseMemory() { Frontiers.clear(); } 613 614 // Accessor interface: 615 typedef DomSetMapType::iterator iterator; 616 typedef DomSetMapType::const_iterator const_iterator; 617 iterator begin() { return Frontiers.begin(); } 618 const_iterator begin() const { return Frontiers.begin(); } 619 iterator end() { return Frontiers.end(); } 620 const_iterator end() const { return Frontiers.end(); } 621 iterator find(BasicBlock *B) { return Frontiers.find(B); } 622 const_iterator find(BasicBlock *B) const { return Frontiers.find(B); } 623 624 void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) { 625 assert(find(BB) == end() && "Block already in DominanceFrontier!"); 626 Frontiers.insert(std::make_pair(BB, frontier)); 627 } 628 629 /// removeBlock - Remove basic block BB's frontier. 630 void removeBlock(BasicBlock *BB) { 631 assert(find(BB) != end() && "Block is not in DominanceFrontier!"); 632 for (iterator I = begin(), E = end(); I != E; ++I) 633 I->second.erase(BB); 634 Frontiers.erase(BB); 635 } 636 637 void addToFrontier(iterator I, BasicBlock *Node) { 638 assert(I != end() && "BB is not in DominanceFrontier!"); 639 I->second.insert(Node); 640 } 641 642 void removeFromFrontier(iterator I, BasicBlock *Node) { 643 assert(I != end() && "BB is not in DominanceFrontier!"); 644 assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB"); 645 I->second.erase(Node); 646 } 647 648 /// print - Convert to human readable form 649 /// 650 virtual void print(std::ostream &OS, const Module* = 0) const; 651 void print(std::ostream *OS, const Module* M = 0) const { 652 if (OS) print(*OS, M); 653 } 654 virtual void dump(); 655}; 656 657 658//===------------------------------------- 659/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is 660/// used to compute a forward dominator frontiers. 661/// 662class DominanceFrontier : public DominanceFrontierBase { 663public: 664 static char ID; // Pass ID, replacement for typeid 665 DominanceFrontier() : 666 DominanceFrontierBase(intptr_t(&ID), false) {} 667 668 BasicBlock *getRoot() const { 669 assert(Roots.size() == 1 && "Should always have entry node!"); 670 return Roots[0]; 671 } 672 673 virtual bool runOnFunction(Function &) { 674 Frontiers.clear(); 675 DominatorTree &DT = getAnalysis<DominatorTree>(); 676 Roots = DT.getRoots(); 677 assert(Roots.size() == 1 && "Only one entry block for forward domfronts!"); 678 calculate(DT, DT[Roots[0]]); 679 return false; 680 } 681 682 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 683 AU.setPreservesAll(); 684 AU.addRequired<DominatorTree>(); 685 } 686 687 /// splitBlock - BB is split and now it has one successor. Update dominance 688 /// frontier to reflect this change. 689 void splitBlock(BasicBlock *BB); 690 691 /// BasicBlock BB's new dominator is NewBB. Update BB's dominance frontier 692 /// to reflect this change. 693 void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB, 694 DominatorTree *DT) { 695 // NewBB is now dominating BB. Which means BB's dominance 696 // frontier is now part of NewBB's dominance frontier. However, BB 697 // itself is not member of NewBB's dominance frontier. 698 DominanceFrontier::iterator NewDFI = find(NewBB); 699 DominanceFrontier::iterator DFI = find(BB); 700 DominanceFrontier::DomSetType BBSet = DFI->second; 701 for (DominanceFrontier::DomSetType::iterator BBSetI = BBSet.begin(), 702 BBSetE = BBSet.end(); BBSetI != BBSetE; ++BBSetI) { 703 BasicBlock *DFMember = *BBSetI; 704 // Insert only if NewBB dominates DFMember. 705 if (!DT->dominates(NewBB, DFMember)) 706 NewDFI->second.insert(DFMember); 707 } 708 NewDFI->second.erase(BB); 709 } 710 711private: 712 const DomSetType &calculate(const DominatorTree &DT, 713 const DomTreeNode *Node); 714}; 715 716 717} // End llvm namespace 718 719#endif 720