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