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