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