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