1 //===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 /// \file 10 /// 11 /// This file defines a set of templates that efficiently compute a dominator 12 /// tree over a generic graph. This is used typically in LLVM for fast 13 /// dominance queries on the CFG, but is fully generic w.r.t. the underlying 14 /// graph types. 15 /// 16 //===----------------------------------------------------------------------===// 17 18 #ifndef LLVM_SUPPORT_GENERIC_DOM_TREE_H 19 #define LLVM_SUPPORT_GENERIC_DOM_TREE_H 20 21 #include "llvm/ADT/DenseMap.h" 22 #include "llvm/ADT/DepthFirstIterator.h" 23 #include "llvm/ADT/GraphTraits.h" 24 #include "llvm/ADT/SmallPtrSet.h" 25 #include "llvm/ADT/SmallVector.h" 26 #include "llvm/Support/Compiler.h" 27 #include "llvm/Support/raw_ostream.h" 28 #include <algorithm> 29 30 namespace llvm { 31 32 //===----------------------------------------------------------------------===// 33 /// DominatorBase - Base class that other, more interesting dominator analyses 34 /// inherit from. 35 /// 36 template <class NodeT> 37 class DominatorBase { 38 protected: 39 std::vector<NodeT*> Roots; 40 const bool IsPostDominators; 41 inline explicit DominatorBase(bool isPostDom) : 42 Roots(), IsPostDominators(isPostDom) {} 43 public: 44 45 /// getRoots - Return the root blocks of the current CFG. This may include 46 /// multiple blocks if we are computing post dominators. For forward 47 /// dominators, this will always be a single block (the entry node). 48 /// 49 inline const std::vector<NodeT*> &getRoots() const { return Roots; } 50 51 /// isPostDominator - Returns true if analysis based of postdoms 52 /// 53 bool isPostDominator() const { return IsPostDominators; } 54 }; 55 56 57 //===----------------------------------------------------------------------===// 58 // DomTreeNodeBase - Dominator Tree Node 59 template<class NodeT> class DominatorTreeBase; 60 struct PostDominatorTree; 61 62 template <class NodeT> 63 class DomTreeNodeBase { 64 NodeT *TheBB; 65 DomTreeNodeBase<NodeT> *IDom; 66 std::vector<DomTreeNodeBase<NodeT> *> Children; 67 mutable int DFSNumIn, DFSNumOut; 68 69 template<class N> friend class DominatorTreeBase; 70 friend struct PostDominatorTree; 71 public: 72 typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator; 73 typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator 74 const_iterator; 75 76 iterator begin() { return Children.begin(); } 77 iterator end() { return Children.end(); } 78 const_iterator begin() const { return Children.begin(); } 79 const_iterator end() const { return Children.end(); } 80 81 NodeT *getBlock() const { return TheBB; } 82 DomTreeNodeBase<NodeT> *getIDom() const { return IDom; } 83 const std::vector<DomTreeNodeBase<NodeT>*> &getChildren() const { 84 return Children; 85 } 86 87 DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom) 88 : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { } 89 90 DomTreeNodeBase<NodeT> *addChild(DomTreeNodeBase<NodeT> *C) { 91 Children.push_back(C); 92 return C; 93 } 94 95 size_t getNumChildren() const { 96 return Children.size(); 97 } 98 99 void clearAllChildren() { 100 Children.clear(); 101 } 102 103 bool compare(const DomTreeNodeBase<NodeT> *Other) const { 104 if (getNumChildren() != Other->getNumChildren()) 105 return true; 106 107 SmallPtrSet<const NodeT *, 4> OtherChildren; 108 for (const_iterator I = Other->begin(), E = Other->end(); I != E; ++I) { 109 const NodeT *Nd = (*I)->getBlock(); 110 OtherChildren.insert(Nd); 111 } 112 113 for (const_iterator I = begin(), E = end(); I != E; ++I) { 114 const NodeT *N = (*I)->getBlock(); 115 if (OtherChildren.count(N) == 0) 116 return true; 117 } 118 return false; 119 } 120 121 void setIDom(DomTreeNodeBase<NodeT> *NewIDom) { 122 assert(IDom && "No immediate dominator?"); 123 if (IDom != NewIDom) { 124 typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I = 125 std::find(IDom->Children.begin(), IDom->Children.end(), this); 126 assert(I != IDom->Children.end() && 127 "Not in immediate dominator children set!"); 128 // I am no longer your child... 129 IDom->Children.erase(I); 130 131 // Switch to new dominator 132 IDom = NewIDom; 133 IDom->Children.push_back(this); 134 } 135 } 136 137 /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do 138 /// not call them. 139 unsigned getDFSNumIn() const { return DFSNumIn; } 140 unsigned getDFSNumOut() const { return DFSNumOut; } 141 private: 142 // Return true if this node is dominated by other. Use this only if DFS info 143 // is valid. 144 bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const { 145 return this->DFSNumIn >= other->DFSNumIn && 146 this->DFSNumOut <= other->DFSNumOut; 147 } 148 }; 149 150 template<class NodeT> 151 inline raw_ostream &operator<<(raw_ostream &o, 152 const DomTreeNodeBase<NodeT> *Node) { 153 if (Node->getBlock()) 154 Node->getBlock()->printAsOperand(o, false); 155 else 156 o << " <<exit node>>"; 157 158 o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}"; 159 160 return o << "\n"; 161 } 162 163 template<class NodeT> 164 inline void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o, 165 unsigned Lev) { 166 o.indent(2*Lev) << "[" << Lev << "] " << N; 167 for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(), 168 E = N->end(); I != E; ++I) 169 PrintDomTree<NodeT>(*I, o, Lev+1); 170 } 171 172 //===----------------------------------------------------------------------===// 173 /// DominatorTree - Calculate the immediate dominator tree for a function. 174 /// 175 176 template<class FuncT, class N> 177 void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT, 178 FuncT& F); 179 180 template<class NodeT> 181 class DominatorTreeBase : public DominatorBase<NodeT> { 182 bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A, 183 const DomTreeNodeBase<NodeT> *B) const { 184 assert(A != B); 185 assert(isReachableFromEntry(B)); 186 assert(isReachableFromEntry(A)); 187 188 const DomTreeNodeBase<NodeT> *IDom; 189 while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B) 190 B = IDom; // Walk up the tree 191 return IDom != nullptr; 192 } 193 194 protected: 195 typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> DomTreeNodeMapType; 196 DomTreeNodeMapType DomTreeNodes; 197 DomTreeNodeBase<NodeT> *RootNode; 198 199 mutable bool DFSInfoValid; 200 mutable unsigned int SlowQueries; 201 // Information record used during immediate dominators computation. 202 struct InfoRec { 203 unsigned DFSNum; 204 unsigned Parent; 205 unsigned Semi; 206 NodeT *Label; 207 208 InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(nullptr) {} 209 }; 210 211 DenseMap<NodeT*, NodeT*> IDoms; 212 213 // Vertex - Map the DFS number to the NodeT* 214 std::vector<NodeT*> Vertex; 215 216 // Info - Collection of information used during the computation of idoms. 217 DenseMap<NodeT*, InfoRec> Info; 218 219 void reset() { 220 for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(), 221 E = DomTreeNodes.end(); I != E; ++I) 222 delete I->second; 223 DomTreeNodes.clear(); 224 IDoms.clear(); 225 this->Roots.clear(); 226 Vertex.clear(); 227 RootNode = nullptr; 228 } 229 230 // NewBB is split and now it has one successor. Update dominator tree to 231 // reflect this change. 232 template<class N, class GraphT> 233 void Split(DominatorTreeBase<typename GraphT::NodeType>& DT, 234 typename GraphT::NodeType* NewBB) { 235 assert(std::distance(GraphT::child_begin(NewBB), 236 GraphT::child_end(NewBB)) == 1 && 237 "NewBB should have a single successor!"); 238 typename GraphT::NodeType* NewBBSucc = *GraphT::child_begin(NewBB); 239 240 std::vector<typename GraphT::NodeType*> PredBlocks; 241 typedef GraphTraits<Inverse<N> > InvTraits; 242 for (typename InvTraits::ChildIteratorType PI = 243 InvTraits::child_begin(NewBB), 244 PE = InvTraits::child_end(NewBB); PI != PE; ++PI) 245 PredBlocks.push_back(*PI); 246 247 assert(!PredBlocks.empty() && "No predblocks?"); 248 249 bool NewBBDominatesNewBBSucc = true; 250 for (typename InvTraits::ChildIteratorType PI = 251 InvTraits::child_begin(NewBBSucc), 252 E = InvTraits::child_end(NewBBSucc); PI != E; ++PI) { 253 typename InvTraits::NodeType *ND = *PI; 254 if (ND != NewBB && !DT.dominates(NewBBSucc, ND) && 255 DT.isReachableFromEntry(ND)) { 256 NewBBDominatesNewBBSucc = false; 257 break; 258 } 259 } 260 261 // Find NewBB's immediate dominator and create new dominator tree node for 262 // NewBB. 263 NodeT *NewBBIDom = nullptr; 264 unsigned i = 0; 265 for (i = 0; i < PredBlocks.size(); ++i) 266 if (DT.isReachableFromEntry(PredBlocks[i])) { 267 NewBBIDom = PredBlocks[i]; 268 break; 269 } 270 271 // It's possible that none of the predecessors of NewBB are reachable; 272 // in that case, NewBB itself is unreachable, so nothing needs to be 273 // changed. 274 if (!NewBBIDom) 275 return; 276 277 for (i = i + 1; i < PredBlocks.size(); ++i) { 278 if (DT.isReachableFromEntry(PredBlocks[i])) 279 NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]); 280 } 281 282 // Create the new dominator tree node... and set the idom of NewBB. 283 DomTreeNodeBase<NodeT> *NewBBNode = DT.addNewBlock(NewBB, NewBBIDom); 284 285 // If NewBB strictly dominates other blocks, then it is now the immediate 286 // dominator of NewBBSucc. Update the dominator tree as appropriate. 287 if (NewBBDominatesNewBBSucc) { 288 DomTreeNodeBase<NodeT> *NewBBSuccNode = DT.getNode(NewBBSucc); 289 DT.changeImmediateDominator(NewBBSuccNode, NewBBNode); 290 } 291 } 292 293 public: 294 explicit DominatorTreeBase(bool isPostDom) 295 : DominatorBase<NodeT>(isPostDom), DFSInfoValid(false), SlowQueries(0) {} 296 virtual ~DominatorTreeBase() { reset(); } 297 298 /// compare - Return false if the other dominator tree base matches this 299 /// dominator tree base. Otherwise return true. 300 bool compare(const DominatorTreeBase &Other) const { 301 302 const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes; 303 if (DomTreeNodes.size() != OtherDomTreeNodes.size()) 304 return true; 305 306 for (typename DomTreeNodeMapType::const_iterator 307 I = this->DomTreeNodes.begin(), 308 E = this->DomTreeNodes.end(); I != E; ++I) { 309 NodeT *BB = I->first; 310 typename DomTreeNodeMapType::const_iterator OI = OtherDomTreeNodes.find(BB); 311 if (OI == OtherDomTreeNodes.end()) 312 return true; 313 314 DomTreeNodeBase<NodeT>* MyNd = I->second; 315 DomTreeNodeBase<NodeT>* OtherNd = OI->second; 316 317 if (MyNd->compare(OtherNd)) 318 return true; 319 } 320 321 return false; 322 } 323 324 virtual void releaseMemory() { reset(); } 325 326 /// getNode - return the (Post)DominatorTree node for the specified basic 327 /// block. This is the same as using operator[] on this class. 328 /// 329 inline DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const { 330 return DomTreeNodes.lookup(BB); 331 } 332 333 inline DomTreeNodeBase<NodeT> *operator[](NodeT *BB) const { 334 return getNode(BB); 335 } 336 337 /// getRootNode - This returns the entry node for the CFG of the function. If 338 /// this tree represents the post-dominance relations for a function, however, 339 /// this root may be a node with the block == NULL. This is the case when 340 /// there are multiple exit nodes from a particular function. Consumers of 341 /// post-dominance information must be capable of dealing with this 342 /// possibility. 343 /// 344 DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; } 345 const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; } 346 347 /// Get all nodes dominated by R, including R itself. 348 void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const { 349 Result.clear(); 350 const DomTreeNodeBase<NodeT> *RN = getNode(R); 351 if (!RN) 352 return; // If R is unreachable, it will not be present in the DOM tree. 353 SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL; 354 WL.push_back(RN); 355 356 while (!WL.empty()) { 357 const DomTreeNodeBase<NodeT> *N = WL.pop_back_val(); 358 Result.push_back(N->getBlock()); 359 WL.append(N->begin(), N->end()); 360 } 361 } 362 363 /// properlyDominates - Returns true iff A dominates B and A != B. 364 /// Note that this is not a constant time operation! 365 /// 366 bool properlyDominates(const DomTreeNodeBase<NodeT> *A, 367 const DomTreeNodeBase<NodeT> *B) const { 368 if (!A || !B) 369 return false; 370 if (A == B) 371 return false; 372 return dominates(A, B); 373 } 374 375 bool properlyDominates(const NodeT *A, const NodeT *B) const; 376 377 /// isReachableFromEntry - Return true if A is dominated by the entry 378 /// block of the function containing it. 379 bool isReachableFromEntry(const NodeT* A) const { 380 assert(!this->isPostDominator() && 381 "This is not implemented for post dominators"); 382 return isReachableFromEntry(getNode(const_cast<NodeT *>(A))); 383 } 384 385 inline bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { 386 return A; 387 } 388 389 /// dominates - Returns true iff A dominates B. Note that this is not a 390 /// constant time operation! 391 /// 392 inline bool dominates(const DomTreeNodeBase<NodeT> *A, 393 const DomTreeNodeBase<NodeT> *B) const { 394 // A node trivially dominates itself. 395 if (B == A) 396 return true; 397 398 // An unreachable node is dominated by anything. 399 if (!isReachableFromEntry(B)) 400 return true; 401 402 // And dominates nothing. 403 if (!isReachableFromEntry(A)) 404 return false; 405 406 // Compare the result of the tree walk and the dfs numbers, if expensive 407 // checks are enabled. 408 #ifdef XDEBUG 409 assert((!DFSInfoValid || 410 (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && 411 "Tree walk disagrees with dfs numbers!"); 412 #endif 413 414 if (DFSInfoValid) 415 return B->DominatedBy(A); 416 417 // If we end up with too many slow queries, just update the 418 // DFS numbers on the theory that we are going to keep querying. 419 SlowQueries++; 420 if (SlowQueries > 32) { 421 updateDFSNumbers(); 422 return B->DominatedBy(A); 423 } 424 425 return dominatedBySlowTreeWalk(A, B); 426 } 427 428 bool dominates(const NodeT *A, const NodeT *B) const; 429 430 NodeT *getRoot() const { 431 assert(this->Roots.size() == 1 && "Should always have entry node!"); 432 return this->Roots[0]; 433 } 434 435 /// findNearestCommonDominator - Find nearest common dominator basic block 436 /// for basic block A and B. If there is no such block then return NULL. 437 NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) { 438 assert(A->getParent() == B->getParent() && 439 "Two blocks are not in same function"); 440 441 // If either A or B is a entry block then it is nearest common dominator 442 // (for forward-dominators). 443 if (!this->isPostDominator()) { 444 NodeT &Entry = A->getParent()->front(); 445 if (A == &Entry || B == &Entry) 446 return &Entry; 447 } 448 449 // If B dominates A then B is nearest common dominator. 450 if (dominates(B, A)) 451 return B; 452 453 // If A dominates B then A is nearest common dominator. 454 if (dominates(A, B)) 455 return A; 456 457 DomTreeNodeBase<NodeT> *NodeA = getNode(A); 458 DomTreeNodeBase<NodeT> *NodeB = getNode(B); 459 460 // If we have DFS info, then we can avoid all allocations by just querying 461 // it from each IDom. Note that because we call 'dominates' twice above, we 462 // expect to call through this code at most 16 times in a row without 463 // building valid DFS information. This is important as below is a *very* 464 // slow tree walk. 465 if (DFSInfoValid) { 466 DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom(); 467 while (IDomA) { 468 if (NodeB->DominatedBy(IDomA)) 469 return IDomA->getBlock(); 470 IDomA = IDomA->getIDom(); 471 } 472 return nullptr; 473 } 474 475 // Collect NodeA dominators set. 476 SmallPtrSet<DomTreeNodeBase<NodeT>*, 16> NodeADoms; 477 NodeADoms.insert(NodeA); 478 DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom(); 479 while (IDomA) { 480 NodeADoms.insert(IDomA); 481 IDomA = IDomA->getIDom(); 482 } 483 484 // Walk NodeB immediate dominators chain and find common dominator node. 485 DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom(); 486 while (IDomB) { 487 if (NodeADoms.count(IDomB) != 0) 488 return IDomB->getBlock(); 489 490 IDomB = IDomB->getIDom(); 491 } 492 493 return nullptr; 494 } 495 496 const NodeT *findNearestCommonDominator(const NodeT *A, const NodeT *B) { 497 // Cast away the const qualifiers here. This is ok since 498 // const is re-introduced on the return type. 499 return findNearestCommonDominator(const_cast<NodeT *>(A), 500 const_cast<NodeT *>(B)); 501 } 502 503 //===--------------------------------------------------------------------===// 504 // API to update (Post)DominatorTree information based on modifications to 505 // the CFG... 506 507 /// addNewBlock - Add a new node to the dominator tree information. This 508 /// creates a new node as a child of DomBB dominator node,linking it into 509 /// the children list of the immediate dominator. 510 DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) { 511 assert(getNode(BB) == nullptr && "Block already in dominator tree!"); 512 DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB); 513 assert(IDomNode && "Not immediate dominator specified for block!"); 514 DFSInfoValid = false; 515 return DomTreeNodes[BB] = 516 IDomNode->addChild(new DomTreeNodeBase<NodeT>(BB, IDomNode)); 517 } 518 519 /// changeImmediateDominator - This method is used to update the dominator 520 /// tree information when a node's immediate dominator changes. 521 /// 522 void changeImmediateDominator(DomTreeNodeBase<NodeT> *N, 523 DomTreeNodeBase<NodeT> *NewIDom) { 524 assert(N && NewIDom && "Cannot change null node pointers!"); 525 DFSInfoValid = false; 526 N->setIDom(NewIDom); 527 } 528 529 void changeImmediateDominator(NodeT *BB, NodeT *NewBB) { 530 changeImmediateDominator(getNode(BB), getNode(NewBB)); 531 } 532 533 /// eraseNode - Removes a node from the dominator tree. Block must not 534 /// dominate any other blocks. Removes node from its immediate dominator's 535 /// children list. Deletes dominator node associated with basic block BB. 536 void eraseNode(NodeT *BB) { 537 DomTreeNodeBase<NodeT> *Node = getNode(BB); 538 assert(Node && "Removing node that isn't in dominator tree."); 539 assert(Node->getChildren().empty() && "Node is not a leaf node."); 540 541 // Remove node from immediate dominator's children list. 542 DomTreeNodeBase<NodeT> *IDom = Node->getIDom(); 543 if (IDom) { 544 typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I = 545 std::find(IDom->Children.begin(), IDom->Children.end(), Node); 546 assert(I != IDom->Children.end() && 547 "Not in immediate dominator children set!"); 548 // I am no longer your child... 549 IDom->Children.erase(I); 550 } 551 552 DomTreeNodes.erase(BB); 553 delete Node; 554 } 555 556 /// removeNode - Removes a node from the dominator tree. Block must not 557 /// dominate any other blocks. Invalidates any node pointing to removed 558 /// block. 559 void removeNode(NodeT *BB) { 560 assert(getNode(BB) && "Removing node that isn't in dominator tree."); 561 DomTreeNodes.erase(BB); 562 } 563 564 /// splitBlock - BB is split and now it has one successor. Update dominator 565 /// tree to reflect this change. 566 void splitBlock(NodeT* NewBB) { 567 if (this->IsPostDominators) 568 this->Split<Inverse<NodeT*>, GraphTraits<Inverse<NodeT*> > >(*this, NewBB); 569 else 570 this->Split<NodeT*, GraphTraits<NodeT*> >(*this, NewBB); 571 } 572 573 /// print - Convert to human readable form 574 /// 575 void print(raw_ostream &o) const { 576 o << "=============================--------------------------------\n"; 577 if (this->isPostDominator()) 578 o << "Inorder PostDominator Tree: "; 579 else 580 o << "Inorder Dominator Tree: "; 581 if (!this->DFSInfoValid) 582 o << "DFSNumbers invalid: " << SlowQueries << " slow queries."; 583 o << "\n"; 584 585 // The postdom tree can have a null root if there are no returns. 586 if (getRootNode()) 587 PrintDomTree<NodeT>(getRootNode(), o, 1); 588 } 589 590 protected: 591 template<class GraphT> 592 friend typename GraphT::NodeType* Eval( 593 DominatorTreeBase<typename GraphT::NodeType>& DT, 594 typename GraphT::NodeType* V, 595 unsigned LastLinked); 596 597 template<class GraphT> 598 friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT, 599 typename GraphT::NodeType* V, 600 unsigned N); 601 602 template<class FuncT, class N> 603 friend void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT, 604 FuncT& F); 605 606 /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking 607 /// dominator tree in dfs order. 608 void updateDFSNumbers() const { 609 unsigned DFSNum = 0; 610 611 SmallVector<std::pair<const DomTreeNodeBase<NodeT>*, 612 typename DomTreeNodeBase<NodeT>::const_iterator>, 32> WorkStack; 613 614 const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode(); 615 616 if (!ThisRoot) 617 return; 618 619 // Even in the case of multiple exits that form the post dominator root 620 // nodes, do not iterate over all exits, but start from the virtual root 621 // node. Otherwise bbs, that are not post dominated by any exit but by the 622 // virtual root node, will never be assigned a DFS number. 623 WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin())); 624 ThisRoot->DFSNumIn = DFSNum++; 625 626 while (!WorkStack.empty()) { 627 const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first; 628 typename DomTreeNodeBase<NodeT>::const_iterator ChildIt = 629 WorkStack.back().second; 630 631 // If we visited all of the children of this node, "recurse" back up the 632 // stack setting the DFOutNum. 633 if (ChildIt == Node->end()) { 634 Node->DFSNumOut = DFSNum++; 635 WorkStack.pop_back(); 636 } else { 637 // Otherwise, recursively visit this child. 638 const DomTreeNodeBase<NodeT> *Child = *ChildIt; 639 ++WorkStack.back().second; 640 641 WorkStack.push_back(std::make_pair(Child, Child->begin())); 642 Child->DFSNumIn = DFSNum++; 643 } 644 } 645 646 SlowQueries = 0; 647 DFSInfoValid = true; 648 } 649 650 DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) { 651 if (DomTreeNodeBase<NodeT> *Node = getNode(BB)) 652 return Node; 653 654 // Haven't calculated this node yet? Get or calculate the node for the 655 // immediate dominator. 656 NodeT *IDom = getIDom(BB); 657 658 assert(IDom || this->DomTreeNodes[nullptr]); 659 DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom); 660 661 // Add a new tree node for this NodeT, and link it as a child of 662 // IDomNode 663 DomTreeNodeBase<NodeT> *C = new DomTreeNodeBase<NodeT>(BB, IDomNode); 664 return this->DomTreeNodes[BB] = IDomNode->addChild(C); 665 } 666 667 inline NodeT *getIDom(NodeT *BB) const { 668 return IDoms.lookup(BB); 669 } 670 671 inline void addRoot(NodeT* BB) { 672 this->Roots.push_back(BB); 673 } 674 675 public: 676 /// recalculate - compute a dominator tree for the given function 677 template<class FT> 678 void recalculate(FT& F) { 679 typedef GraphTraits<FT*> TraitsTy; 680 reset(); 681 this->Vertex.push_back(nullptr); 682 683 if (!this->IsPostDominators) { 684 // Initialize root 685 NodeT *entry = TraitsTy::getEntryNode(&F); 686 this->Roots.push_back(entry); 687 this->IDoms[entry] = nullptr; 688 this->DomTreeNodes[entry] = nullptr; 689 690 Calculate<FT, NodeT*>(*this, F); 691 } else { 692 // Initialize the roots list 693 for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F), 694 E = TraitsTy::nodes_end(&F); I != E; ++I) { 695 if (TraitsTy::child_begin(I) == TraitsTy::child_end(I)) 696 addRoot(I); 697 698 // Prepopulate maps so that we don't get iterator invalidation issues later. 699 this->IDoms[I] = nullptr; 700 this->DomTreeNodes[I] = nullptr; 701 } 702 703 Calculate<FT, Inverse<NodeT*> >(*this, F); 704 } 705 } 706 }; 707 708 // These two functions are declared out of line as a workaround for building 709 // with old (< r147295) versions of clang because of pr11642. 710 template<class NodeT> 711 bool DominatorTreeBase<NodeT>::dominates(const NodeT *A, const NodeT *B) const { 712 if (A == B) 713 return true; 714 715 // Cast away the const qualifiers here. This is ok since 716 // this function doesn't actually return the values returned 717 // from getNode. 718 return dominates(getNode(const_cast<NodeT *>(A)), 719 getNode(const_cast<NodeT *>(B))); 720 } 721 template<class NodeT> 722 bool 723 DominatorTreeBase<NodeT>::properlyDominates(const NodeT *A, const NodeT *B) const { 724 if (A == B) 725 return false; 726 727 // Cast away the const qualifiers here. This is ok since 728 // this function doesn't actually return the values returned 729 // from getNode. 730 return dominates(getNode(const_cast<NodeT *>(A)), 731 getNode(const_cast<NodeT *>(B))); 732 } 733 734 } 735 736 #endif 737