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