1 //===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// \file 9 /// 10 /// This file defines a set of templates that efficiently compute a dominator 11 /// tree over a generic graph. This is used typically in LLVM for fast 12 /// dominance queries on the CFG, but is fully generic w.r.t. the underlying 13 /// graph types. 14 /// 15 /// Unlike ADT/* graph algorithms, generic dominator tree has more requirements 16 /// on the graph's NodeRef. The NodeRef should be a pointer and, 17 /// NodeRef->getParent() must return the parent node that is also a pointer. 18 /// 19 /// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits. 20 /// 21 //===----------------------------------------------------------------------===// 22 23 #ifndef LLVM_SUPPORT_GENERICDOMTREE_H 24 #define LLVM_SUPPORT_GENERICDOMTREE_H 25 26 #include "llvm/ADT/DenseMap.h" 27 #include "llvm/ADT/GraphTraits.h" 28 #include "llvm/ADT/STLExtras.h" 29 #include "llvm/ADT/SmallPtrSet.h" 30 #include "llvm/ADT/SmallVector.h" 31 #include "llvm/Support/CFGUpdate.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 <typename NodeT, bool IsPostDom> 45 class DominatorTreeBase; 46 47 namespace DomTreeBuilder { 48 template <typename DomTreeT> 49 struct SemiNCAInfo; 50 } // namespace DomTreeBuilder 51 52 /// Base class for the actual dominator tree node. 53 template <class NodeT> class DomTreeNodeBase { 54 friend class PostDominatorTree; 55 friend class DominatorTreeBase<NodeT, false>; 56 friend class DominatorTreeBase<NodeT, true>; 57 friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, false>>; 58 friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, true>>; 59 60 NodeT *TheBB; 61 DomTreeNodeBase *IDom; 62 unsigned Level; 63 std::vector<DomTreeNodeBase *> Children; 64 mutable unsigned DFSNumIn = ~0; 65 mutable unsigned DFSNumOut = ~0; 66 67 public: 68 DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom) 69 : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {} 70 71 using iterator = typename std::vector<DomTreeNodeBase *>::iterator; 72 using const_iterator = 73 typename std::vector<DomTreeNodeBase *>::const_iterator; 74 75 iterator begin() { return Children.begin(); } 76 iterator end() { return Children.end(); } 77 const_iterator begin() const { return Children.begin(); } 78 const_iterator end() const { return Children.end(); } 79 80 DomTreeNodeBase *const &back() const { return Children.back(); } 81 DomTreeNodeBase *&back() { return Children.back(); } 82 83 iterator_range<iterator> children() { return make_range(begin(), end()); } 84 iterator_range<const_iterator> children() const { 85 return make_range(begin(), end()); 86 } 87 88 NodeT *getBlock() const { return TheBB; } 89 DomTreeNodeBase *getIDom() const { return IDom; } 90 unsigned getLevel() const { return Level; } 91 92 std::unique_ptr<DomTreeNodeBase> addChild( 93 std::unique_ptr<DomTreeNodeBase> C) { 94 Children.push_back(C.get()); 95 return C; 96 } 97 98 bool isLeaf() const { return Children.empty(); } 99 size_t getNumChildren() const { return Children.size(); } 100 101 void clearAllChildren() { Children.clear(); } 102 103 bool compare(const DomTreeNodeBase *Other) const { 104 if (getNumChildren() != Other->getNumChildren()) 105 return true; 106 107 if (Level != Other->Level) return true; 108 109 SmallPtrSet<const NodeT *, 4> OtherChildren; 110 for (const DomTreeNodeBase *I : *Other) { 111 const NodeT *Nd = I->getBlock(); 112 OtherChildren.insert(Nd); 113 } 114 115 for (const DomTreeNodeBase *I : *this) { 116 const NodeT *N = I->getBlock(); 117 if (OtherChildren.count(N) == 0) 118 return true; 119 } 120 return false; 121 } 122 123 void setIDom(DomTreeNodeBase *NewIDom) { 124 assert(IDom && "No immediate dominator?"); 125 if (IDom == NewIDom) return; 126 127 auto I = find(IDom->Children, this); 128 assert(I != IDom->Children.end() && 129 "Not in immediate dominator children set!"); 130 // I am no longer your child... 131 IDom->Children.erase(I); 132 133 // Switch to new dominator 134 IDom = NewIDom; 135 IDom->Children.push_back(this); 136 137 UpdateLevel(); 138 } 139 140 /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes 141 /// in the dominator tree. They are only guaranteed valid if 142 /// updateDFSNumbers() has been called. 143 unsigned getDFSNumIn() const { return DFSNumIn; } 144 unsigned getDFSNumOut() const { return DFSNumOut; } 145 146 private: 147 // Return true if this node is dominated by other. Use this only if DFS info 148 // is valid. 149 bool DominatedBy(const DomTreeNodeBase *other) const { 150 return this->DFSNumIn >= other->DFSNumIn && 151 this->DFSNumOut <= other->DFSNumOut; 152 } 153 154 void UpdateLevel() { 155 assert(IDom); 156 if (Level == IDom->Level + 1) return; 157 158 SmallVector<DomTreeNodeBase *, 64> WorkStack = {this}; 159 160 while (!WorkStack.empty()) { 161 DomTreeNodeBase *Current = WorkStack.pop_back_val(); 162 Current->Level = Current->IDom->Level + 1; 163 164 for (DomTreeNodeBase *C : *Current) { 165 assert(C->IDom); 166 if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C); 167 } 168 } 169 } 170 }; 171 172 template <class NodeT> 173 raw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) { 174 if (Node->getBlock()) 175 Node->getBlock()->printAsOperand(O, false); 176 else 177 O << " <<exit node>>"; 178 179 O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} [" 180 << Node->getLevel() << "]\n"; 181 182 return O; 183 } 184 185 template <class NodeT> 186 void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O, 187 unsigned Lev) { 188 O.indent(2 * Lev) << "[" << Lev << "] " << N; 189 for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(), 190 E = N->end(); 191 I != E; ++I) 192 PrintDomTree<NodeT>(*I, O, Lev + 1); 193 } 194 195 namespace DomTreeBuilder { 196 // The routines below are provided in a separate header but referenced here. 197 template <typename DomTreeT> 198 void Calculate(DomTreeT &DT); 199 200 template <typename DomTreeT> 201 void CalculateWithUpdates(DomTreeT &DT, 202 ArrayRef<typename DomTreeT::UpdateType> Updates); 203 204 template <typename DomTreeT> 205 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, 206 typename DomTreeT::NodePtr To); 207 208 template <typename DomTreeT> 209 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, 210 typename DomTreeT::NodePtr To); 211 212 template <typename DomTreeT> 213 void ApplyUpdates(DomTreeT &DT, 214 ArrayRef<typename DomTreeT::UpdateType> Updates); 215 216 template <typename DomTreeT> 217 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL); 218 } // namespace DomTreeBuilder 219 220 /// Core dominator tree base class. 221 /// 222 /// This class is a generic template over graph nodes. It is instantiated for 223 /// various graphs in the LLVM IR or in the code generator. 224 template <typename NodeT, bool IsPostDom> 225 class DominatorTreeBase { 226 public: 227 static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value, 228 "Currently DominatorTreeBase supports only pointer nodes"); 229 using NodeType = NodeT; 230 using NodePtr = NodeT *; 231 using ParentPtr = decltype(std::declval<NodeT *>()->getParent()); 232 static_assert(std::is_pointer<ParentPtr>::value, 233 "Currently NodeT's parent must be a pointer type"); 234 using ParentType = std::remove_pointer_t<ParentPtr>; 235 static constexpr bool IsPostDominator = IsPostDom; 236 237 using UpdateType = cfg::Update<NodePtr>; 238 using UpdateKind = cfg::UpdateKind; 239 static constexpr UpdateKind Insert = UpdateKind::Insert; 240 static constexpr UpdateKind Delete = UpdateKind::Delete; 241 242 enum class VerificationLevel { Fast, Basic, Full }; 243 244 protected: 245 // Dominators always have a single root, postdominators can have more. 246 SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots; 247 248 using DomTreeNodeMapType = 249 DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>; 250 DomTreeNodeMapType DomTreeNodes; 251 DomTreeNodeBase<NodeT> *RootNode = nullptr; 252 ParentPtr Parent = nullptr; 253 254 mutable bool DFSInfoValid = false; 255 mutable unsigned int SlowQueries = 0; 256 257 friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>; 258 259 public: 260 DominatorTreeBase() {} 261 262 DominatorTreeBase(DominatorTreeBase &&Arg) 263 : Roots(std::move(Arg.Roots)), 264 DomTreeNodes(std::move(Arg.DomTreeNodes)), 265 RootNode(Arg.RootNode), 266 Parent(Arg.Parent), 267 DFSInfoValid(Arg.DFSInfoValid), 268 SlowQueries(Arg.SlowQueries) { 269 Arg.wipe(); 270 } 271 272 DominatorTreeBase &operator=(DominatorTreeBase &&RHS) { 273 Roots = std::move(RHS.Roots); 274 DomTreeNodes = std::move(RHS.DomTreeNodes); 275 RootNode = RHS.RootNode; 276 Parent = RHS.Parent; 277 DFSInfoValid = RHS.DFSInfoValid; 278 SlowQueries = RHS.SlowQueries; 279 RHS.wipe(); 280 return *this; 281 } 282 283 DominatorTreeBase(const DominatorTreeBase &) = delete; 284 DominatorTreeBase &operator=(const DominatorTreeBase &) = delete; 285 286 /// Iteration over roots. 287 /// 288 /// This may include multiple blocks if we are computing post dominators. 289 /// For forward dominators, this will always be a single block (the entry 290 /// block). 291 using root_iterator = typename SmallVectorImpl<NodeT *>::iterator; 292 using const_root_iterator = typename SmallVectorImpl<NodeT *>::const_iterator; 293 294 root_iterator root_begin() { return Roots.begin(); } 295 const_root_iterator root_begin() const { return Roots.begin(); } 296 root_iterator root_end() { return Roots.end(); } 297 const_root_iterator root_end() const { return Roots.end(); } 298 299 size_t root_size() const { return Roots.size(); } 300 301 iterator_range<root_iterator> roots() { 302 return make_range(root_begin(), root_end()); 303 } 304 iterator_range<const_root_iterator> roots() const { 305 return make_range(root_begin(), root_end()); 306 } 307 308 /// isPostDominator - Returns true if analysis based of postdoms 309 /// 310 bool isPostDominator() const { return IsPostDominator; } 311 312 /// compare - Return false if the other dominator tree base matches this 313 /// dominator tree base. Otherwise return true. 314 bool compare(const DominatorTreeBase &Other) const { 315 if (Parent != Other.Parent) return true; 316 317 if (Roots.size() != Other.Roots.size()) 318 return true; 319 320 if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin())) 321 return true; 322 323 const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes; 324 if (DomTreeNodes.size() != OtherDomTreeNodes.size()) 325 return true; 326 327 for (const auto &DomTreeNode : DomTreeNodes) { 328 NodeT *BB = DomTreeNode.first; 329 typename DomTreeNodeMapType::const_iterator OI = 330 OtherDomTreeNodes.find(BB); 331 if (OI == OtherDomTreeNodes.end()) 332 return true; 333 334 DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second; 335 DomTreeNodeBase<NodeT> &OtherNd = *OI->second; 336 337 if (MyNd.compare(&OtherNd)) 338 return true; 339 } 340 341 return false; 342 } 343 344 /// getNode - return the (Post)DominatorTree node for the specified basic 345 /// block. This is the same as using operator[] on this class. The result 346 /// may (but is not required to) be null for a forward (backwards) 347 /// statically unreachable block. 348 DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const { 349 auto I = DomTreeNodes.find(BB); 350 if (I != DomTreeNodes.end()) 351 return I->second.get(); 352 return nullptr; 353 } 354 355 /// See getNode. 356 DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const { 357 return getNode(BB); 358 } 359 360 /// getRootNode - This returns the entry node for the CFG of the function. If 361 /// this tree represents the post-dominance relations for a function, however, 362 /// this root may be a node with the block == NULL. This is the case when 363 /// there are multiple exit nodes from a particular function. Consumers of 364 /// post-dominance information must be capable of dealing with this 365 /// possibility. 366 /// 367 DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; } 368 const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; } 369 370 /// Get all nodes dominated by R, including R itself. 371 void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const { 372 Result.clear(); 373 const DomTreeNodeBase<NodeT> *RN = getNode(R); 374 if (!RN) 375 return; // If R is unreachable, it will not be present in the DOM tree. 376 SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL; 377 WL.push_back(RN); 378 379 while (!WL.empty()) { 380 const DomTreeNodeBase<NodeT> *N = WL.pop_back_val(); 381 Result.push_back(N->getBlock()); 382 WL.append(N->begin(), N->end()); 383 } 384 } 385 386 /// properlyDominates - Returns true iff A dominates B and A != B. 387 /// Note that this is not a constant time operation! 388 /// 389 bool properlyDominates(const DomTreeNodeBase<NodeT> *A, 390 const DomTreeNodeBase<NodeT> *B) const { 391 if (!A || !B) 392 return false; 393 if (A == B) 394 return false; 395 return dominates(A, B); 396 } 397 398 bool properlyDominates(const NodeT *A, const NodeT *B) const; 399 400 /// isReachableFromEntry - Return true if A is dominated by the entry 401 /// block of the function containing it. 402 bool isReachableFromEntry(const NodeT *A) const { 403 assert(!this->isPostDominator() && 404 "This is not implemented for post dominators"); 405 return isReachableFromEntry(getNode(const_cast<NodeT *>(A))); 406 } 407 408 bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; } 409 410 /// dominates - Returns true iff A dominates B. Note that this is not a 411 /// constant time operation! 412 /// 413 bool dominates(const DomTreeNodeBase<NodeT> *A, 414 const DomTreeNodeBase<NodeT> *B) const { 415 // A node trivially dominates itself. 416 if (B == A) 417 return true; 418 419 // An unreachable node is dominated by anything. 420 if (!isReachableFromEntry(B)) 421 return true; 422 423 // And dominates nothing. 424 if (!isReachableFromEntry(A)) 425 return false; 426 427 if (B->getIDom() == A) return true; 428 429 if (A->getIDom() == B) return false; 430 431 // A can only dominate B if it is higher in the tree. 432 if (A->getLevel() >= B->getLevel()) return false; 433 434 // Compare the result of the tree walk and the dfs numbers, if expensive 435 // checks are enabled. 436 #ifdef EXPENSIVE_CHECKS 437 assert((!DFSInfoValid || 438 (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && 439 "Tree walk disagrees with dfs numbers!"); 440 #endif 441 442 if (DFSInfoValid) 443 return B->DominatedBy(A); 444 445 // If we end up with too many slow queries, just update the 446 // DFS numbers on the theory that we are going to keep querying. 447 SlowQueries++; 448 if (SlowQueries > 32) { 449 updateDFSNumbers(); 450 return B->DominatedBy(A); 451 } 452 453 return dominatedBySlowTreeWalk(A, B); 454 } 455 456 bool dominates(const NodeT *A, const NodeT *B) const; 457 458 NodeT *getRoot() const { 459 assert(this->Roots.size() == 1 && "Should always have entry node!"); 460 return this->Roots[0]; 461 } 462 463 /// findNearestCommonDominator - Find nearest common dominator basic block 464 /// for basic block A and B. If there is no such block then return nullptr. 465 NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const { 466 assert(A && B && "Pointers are not valid"); 467 assert(A->getParent() == B->getParent() && 468 "Two blocks are not in same function"); 469 470 // If either A or B is a entry block then it is nearest common dominator 471 // (for forward-dominators). 472 if (!isPostDominator()) { 473 NodeT &Entry = A->getParent()->front(); 474 if (A == &Entry || B == &Entry) 475 return &Entry; 476 } 477 478 DomTreeNodeBase<NodeT> *NodeA = getNode(A); 479 DomTreeNodeBase<NodeT> *NodeB = getNode(B); 480 481 if (!NodeA || !NodeB) return nullptr; 482 483 // Use level information to go up the tree until the levels match. Then 484 // continue going up til we arrive at the same node. 485 while (NodeA && NodeA != NodeB) { 486 if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB); 487 488 NodeA = NodeA->IDom; 489 } 490 491 return NodeA ? NodeA->getBlock() : nullptr; 492 } 493 494 const NodeT *findNearestCommonDominator(const NodeT *A, 495 const NodeT *B) const { 496 // Cast away the const qualifiers here. This is ok since 497 // const is re-introduced on the return type. 498 return findNearestCommonDominator(const_cast<NodeT *>(A), 499 const_cast<NodeT *>(B)); 500 } 501 502 bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const { 503 return isPostDominator() && !A->getBlock(); 504 } 505 506 //===--------------------------------------------------------------------===// 507 // API to update (Post)DominatorTree information based on modifications to 508 // the CFG... 509 510 /// Inform the dominator tree about a sequence of CFG edge insertions and 511 /// deletions and perform a batch update on the tree. 512 /// 513 /// This function should be used when there were multiple CFG updates after 514 /// the last dominator tree update. It takes care of performing the updates 515 /// in sync with the CFG and optimizes away the redundant operations that 516 /// cancel each other. 517 /// The functions expects the sequence of updates to be balanced. Eg.: 518 /// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because 519 /// logically it results in a single insertions. 520 /// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make 521 /// sense to insert the same edge twice. 522 /// 523 /// What's more, the functions assumes that it's safe to ask every node in the 524 /// CFG about its children and inverse children. This implies that deletions 525 /// of CFG edges must not delete the CFG nodes before calling this function. 526 /// 527 /// The applyUpdates function can reorder the updates and remove redundant 528 /// ones internally. The batch updater is also able to detect sequences of 529 /// zero and exactly one update -- it's optimized to do less work in these 530 /// cases. 531 /// 532 /// Note that for postdominators it automatically takes care of applying 533 /// updates on reverse edges internally (so there's no need to swap the 534 /// From and To pointers when constructing DominatorTree::UpdateType). 535 /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T> 536 /// with the same template parameter T. 537 /// 538 /// \param Updates An unordered sequence of updates to perform. 539 /// 540 void applyUpdates(ArrayRef<UpdateType> Updates) { 541 DomTreeBuilder::ApplyUpdates(*this, Updates); 542 } 543 544 /// Inform the dominator tree about a CFG edge insertion and update the tree. 545 /// 546 /// This function has to be called just before or just after making the update 547 /// on the actual CFG. There cannot be any other updates that the dominator 548 /// tree doesn't know about. 549 /// 550 /// Note that for postdominators it automatically takes care of inserting 551 /// a reverse edge internally (so there's no need to swap the parameters). 552 /// 553 void insertEdge(NodeT *From, NodeT *To) { 554 assert(From); 555 assert(To); 556 assert(From->getParent() == Parent); 557 assert(To->getParent() == Parent); 558 DomTreeBuilder::InsertEdge(*this, From, To); 559 } 560 561 /// Inform the dominator tree about a CFG edge deletion and update the tree. 562 /// 563 /// This function has to be called just after making the update on the actual 564 /// CFG. An internal functions checks if the edge doesn't exist in the CFG in 565 /// DEBUG mode. There cannot be any other updates that the 566 /// dominator tree doesn't know about. 567 /// 568 /// Note that for postdominators it automatically takes care of deleting 569 /// a reverse edge internally (so there's no need to swap the parameters). 570 /// 571 void deleteEdge(NodeT *From, NodeT *To) { 572 assert(From); 573 assert(To); 574 assert(From->getParent() == Parent); 575 assert(To->getParent() == Parent); 576 DomTreeBuilder::DeleteEdge(*this, From, To); 577 } 578 579 /// Add a new node to the dominator tree information. 580 /// 581 /// This creates a new node as a child of DomBB dominator node, linking it 582 /// into the children list of the immediate dominator. 583 /// 584 /// \param BB New node in CFG. 585 /// \param DomBB CFG node that is dominator for BB. 586 /// \returns New dominator tree node that represents new CFG node. 587 /// 588 DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) { 589 assert(getNode(BB) == nullptr && "Block already in dominator tree!"); 590 DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB); 591 assert(IDomNode && "Not immediate dominator specified for block!"); 592 DFSInfoValid = false; 593 return createChild(BB, IDomNode); 594 } 595 596 /// Add a new node to the forward dominator tree and make it a new root. 597 /// 598 /// \param BB New node in CFG. 599 /// \returns New dominator tree node that represents new CFG node. 600 /// 601 DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) { 602 assert(getNode(BB) == nullptr && "Block already in dominator tree!"); 603 assert(!this->isPostDominator() && 604 "Cannot change root of post-dominator tree"); 605 DFSInfoValid = false; 606 DomTreeNodeBase<NodeT> *NewNode = createNode(BB); 607 if (Roots.empty()) { 608 addRoot(BB); 609 } else { 610 assert(Roots.size() == 1); 611 NodeT *OldRoot = Roots.front(); 612 auto &OldNode = DomTreeNodes[OldRoot]; 613 OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot])); 614 OldNode->IDom = NewNode; 615 OldNode->UpdateLevel(); 616 Roots[0] = BB; 617 } 618 return RootNode = NewNode; 619 } 620 621 /// changeImmediateDominator - This method is used to update the dominator 622 /// tree information when a node's immediate dominator changes. 623 /// 624 void changeImmediateDominator(DomTreeNodeBase<NodeT> *N, 625 DomTreeNodeBase<NodeT> *NewIDom) { 626 assert(N && NewIDom && "Cannot change null node pointers!"); 627 DFSInfoValid = false; 628 N->setIDom(NewIDom); 629 } 630 631 void changeImmediateDominator(NodeT *BB, NodeT *NewBB) { 632 changeImmediateDominator(getNode(BB), getNode(NewBB)); 633 } 634 635 /// eraseNode - Removes a node from the dominator tree. Block must not 636 /// dominate any other blocks. Removes node from its immediate dominator's 637 /// children list. Deletes dominator node associated with basic block BB. 638 void eraseNode(NodeT *BB) { 639 DomTreeNodeBase<NodeT> *Node = getNode(BB); 640 assert(Node && "Removing node that isn't in dominator tree."); 641 assert(Node->isLeaf() && "Node is not a leaf node."); 642 643 DFSInfoValid = false; 644 645 // Remove node from immediate dominator's children list. 646 DomTreeNodeBase<NodeT> *IDom = Node->getIDom(); 647 if (IDom) { 648 const auto I = find(IDom->Children, Node); 649 assert(I != IDom->Children.end() && 650 "Not in immediate dominator children set!"); 651 // I am no longer your child... 652 IDom->Children.erase(I); 653 } 654 655 DomTreeNodes.erase(BB); 656 657 if (!IsPostDom) return; 658 659 // Remember to update PostDominatorTree roots. 660 auto RIt = llvm::find(Roots, BB); 661 if (RIt != Roots.end()) { 662 std::swap(*RIt, Roots.back()); 663 Roots.pop_back(); 664 } 665 } 666 667 /// splitBlock - BB is split and now it has one successor. Update dominator 668 /// tree to reflect this change. 669 void splitBlock(NodeT *NewBB) { 670 if (IsPostDominator) 671 Split<Inverse<NodeT *>>(NewBB); 672 else 673 Split<NodeT *>(NewBB); 674 } 675 676 /// print - Convert to human readable form 677 /// 678 void print(raw_ostream &O) const { 679 O << "=============================--------------------------------\n"; 680 if (IsPostDominator) 681 O << "Inorder PostDominator Tree: "; 682 else 683 O << "Inorder Dominator Tree: "; 684 if (!DFSInfoValid) 685 O << "DFSNumbers invalid: " << SlowQueries << " slow queries."; 686 O << "\n"; 687 688 // The postdom tree can have a null root if there are no returns. 689 if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1); 690 O << "Roots: "; 691 for (const NodePtr Block : Roots) { 692 Block->printAsOperand(O, false); 693 O << " "; 694 } 695 O << "\n"; 696 } 697 698 public: 699 /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking 700 /// dominator tree in dfs order. 701 void updateDFSNumbers() const { 702 if (DFSInfoValid) { 703 SlowQueries = 0; 704 return; 705 } 706 707 SmallVector<std::pair<const DomTreeNodeBase<NodeT> *, 708 typename DomTreeNodeBase<NodeT>::const_iterator>, 709 32> WorkStack; 710 711 const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode(); 712 assert((!Parent || ThisRoot) && "Empty constructed DomTree"); 713 if (!ThisRoot) 714 return; 715 716 // Both dominators and postdominators have a single root node. In the case 717 // case of PostDominatorTree, this node is a virtual root. 718 WorkStack.push_back({ThisRoot, ThisRoot->begin()}); 719 720 unsigned DFSNum = 0; 721 ThisRoot->DFSNumIn = DFSNum++; 722 723 while (!WorkStack.empty()) { 724 const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first; 725 const auto ChildIt = WorkStack.back().second; 726 727 // If we visited all of the children of this node, "recurse" back up the 728 // stack setting the DFOutNum. 729 if (ChildIt == Node->end()) { 730 Node->DFSNumOut = DFSNum++; 731 WorkStack.pop_back(); 732 } else { 733 // Otherwise, recursively visit this child. 734 const DomTreeNodeBase<NodeT> *Child = *ChildIt; 735 ++WorkStack.back().second; 736 737 WorkStack.push_back({Child, Child->begin()}); 738 Child->DFSNumIn = DFSNum++; 739 } 740 } 741 742 SlowQueries = 0; 743 DFSInfoValid = true; 744 } 745 746 /// recalculate - compute a dominator tree for the given function 747 void recalculate(ParentType &Func) { 748 Parent = &Func; 749 DomTreeBuilder::Calculate(*this); 750 } 751 752 void recalculate(ParentType &Func, ArrayRef<UpdateType> Updates) { 753 Parent = &Func; 754 DomTreeBuilder::CalculateWithUpdates(*this, Updates); 755 } 756 757 /// verify - checks if the tree is correct. There are 3 level of verification: 758 /// - Full -- verifies if the tree is correct by making sure all the 759 /// properties (including the parent and the sibling property) 760 /// hold. 761 /// Takes O(N^3) time. 762 /// 763 /// - Basic -- checks if the tree is correct, but compares it to a freshly 764 /// constructed tree instead of checking the sibling property. 765 /// Takes O(N^2) time. 766 /// 767 /// - Fast -- checks basic tree structure and compares it with a freshly 768 /// constructed tree. 769 /// Takes O(N^2) time worst case, but is faster in practise (same 770 /// as tree construction). 771 bool verify(VerificationLevel VL = VerificationLevel::Full) const { 772 return DomTreeBuilder::Verify(*this, VL); 773 } 774 775 void reset() { 776 DomTreeNodes.clear(); 777 Roots.clear(); 778 RootNode = nullptr; 779 Parent = nullptr; 780 DFSInfoValid = false; 781 SlowQueries = 0; 782 } 783 784 protected: 785 void addRoot(NodeT *BB) { this->Roots.push_back(BB); } 786 787 DomTreeNodeBase<NodeT> *createChild(NodeT *BB, DomTreeNodeBase<NodeT> *IDom) { 788 return (DomTreeNodes[BB] = IDom->addChild( 789 std::make_unique<DomTreeNodeBase<NodeT>>(BB, IDom))) 790 .get(); 791 } 792 793 DomTreeNodeBase<NodeT> *createNode(NodeT *BB) { 794 return (DomTreeNodes[BB] = 795 std::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)) 796 .get(); 797 } 798 799 // NewBB is split and now it has one successor. Update dominator tree to 800 // reflect this change. 801 template <class N> 802 void Split(typename GraphTraits<N>::NodeRef NewBB) { 803 using GraphT = GraphTraits<N>; 804 using NodeRef = typename GraphT::NodeRef; 805 assert(std::distance(GraphT::child_begin(NewBB), 806 GraphT::child_end(NewBB)) == 1 && 807 "NewBB should have a single successor!"); 808 NodeRef NewBBSucc = *GraphT::child_begin(NewBB); 809 810 std::vector<NodeRef> PredBlocks; 811 for (auto Pred : children<Inverse<N>>(NewBB)) 812 PredBlocks.push_back(Pred); 813 814 assert(!PredBlocks.empty() && "No predblocks?"); 815 816 bool NewBBDominatesNewBBSucc = true; 817 for (auto Pred : children<Inverse<N>>(NewBBSucc)) { 818 if (Pred != NewBB && !dominates(NewBBSucc, Pred) && 819 isReachableFromEntry(Pred)) { 820 NewBBDominatesNewBBSucc = false; 821 break; 822 } 823 } 824 825 // Find NewBB's immediate dominator and create new dominator tree node for 826 // NewBB. 827 NodeT *NewBBIDom = nullptr; 828 unsigned i = 0; 829 for (i = 0; i < PredBlocks.size(); ++i) 830 if (isReachableFromEntry(PredBlocks[i])) { 831 NewBBIDom = PredBlocks[i]; 832 break; 833 } 834 835 // It's possible that none of the predecessors of NewBB are reachable; 836 // in that case, NewBB itself is unreachable, so nothing needs to be 837 // changed. 838 if (!NewBBIDom) return; 839 840 for (i = i + 1; i < PredBlocks.size(); ++i) { 841 if (isReachableFromEntry(PredBlocks[i])) 842 NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]); 843 } 844 845 // Create the new dominator tree node... and set the idom of NewBB. 846 DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom); 847 848 // If NewBB strictly dominates other blocks, then it is now the immediate 849 // dominator of NewBBSucc. Update the dominator tree as appropriate. 850 if (NewBBDominatesNewBBSucc) { 851 DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc); 852 changeImmediateDominator(NewBBSuccNode, NewBBNode); 853 } 854 } 855 856 private: 857 bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A, 858 const DomTreeNodeBase<NodeT> *B) const { 859 assert(A != B); 860 assert(isReachableFromEntry(B)); 861 assert(isReachableFromEntry(A)); 862 863 const unsigned ALevel = A->getLevel(); 864 const DomTreeNodeBase<NodeT> *IDom; 865 866 // Don't walk nodes above A's subtree. When we reach A's level, we must 867 // either find A or be in some other subtree not dominated by A. 868 while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel) 869 B = IDom; // Walk up the tree 870 871 return B == A; 872 } 873 874 /// Wipe this tree's state without releasing any resources. 875 /// 876 /// This is essentially a post-move helper only. It leaves the object in an 877 /// assignable and destroyable state, but otherwise invalid. 878 void wipe() { 879 DomTreeNodes.clear(); 880 RootNode = nullptr; 881 Parent = nullptr; 882 } 883 }; 884 885 template <typename T> 886 using DomTreeBase = DominatorTreeBase<T, false>; 887 888 template <typename T> 889 using PostDomTreeBase = DominatorTreeBase<T, true>; 890 891 // These two functions are declared out of line as a workaround for building 892 // with old (< r147295) versions of clang because of pr11642. 893 template <typename NodeT, bool IsPostDom> 894 bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A, 895 const NodeT *B) const { 896 if (A == B) 897 return true; 898 899 // Cast away the const qualifiers here. This is ok since 900 // this function doesn't actually return the values returned 901 // from getNode. 902 return dominates(getNode(const_cast<NodeT *>(A)), 903 getNode(const_cast<NodeT *>(B))); 904 } 905 template <typename NodeT, bool IsPostDom> 906 bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates( 907 const NodeT *A, const NodeT *B) const { 908 if (A == B) 909 return false; 910 911 // Cast away the const qualifiers here. This is ok since 912 // this function doesn't actually return the values returned 913 // from getNode. 914 return dominates(getNode(const_cast<NodeT *>(A)), 915 getNode(const_cast<NodeT *>(B))); 916 } 917 918 } // end namespace llvm 919 920 #endif // LLVM_SUPPORT_GENERICDOMTREE_H 921