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