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() = default; 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 (as long as it is done in a deterministic fashion). The 532 /// batch updater is also able to detect sequences of zero and exactly one 533 /// update -- it's optimized to do less work in these 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 ordered sequence of updates to perform. The current CFG 542 /// 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 ordered sequence of updates to perform. The current CFG 551 /// and the reverse of these updates provides the pre-view of the CFG. 552 /// \param PostViewUpdates An ordered 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 append_range(AllUpdates, PostViewUpdates); 568 GraphDiff<NodePtr, IsPostDom> PreViewCFG(AllUpdates, 569 /*ReverseApplyUpdates=*/true); 570 GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates); 571 DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, &PostViewCFG); 572 } 573 } 574 575 /// Inform the dominator tree about a CFG edge insertion and update the tree. 576 /// 577 /// This function has to be called just before or just after making the update 578 /// on the actual CFG. There cannot be any other updates that the dominator 579 /// tree doesn't know about. 580 /// 581 /// Note that for postdominators it automatically takes care of inserting 582 /// a reverse edge internally (so there's no need to swap the parameters). 583 /// 584 void insertEdge(NodeT *From, NodeT *To) { 585 assert(From); 586 assert(To); 587 assert(From->getParent() == Parent); 588 assert(To->getParent() == Parent); 589 DomTreeBuilder::InsertEdge(*this, From, To); 590 } 591 592 /// Inform the dominator tree about a CFG edge deletion and update the tree. 593 /// 594 /// This function has to be called just after making the update on the actual 595 /// CFG. An internal functions checks if the edge doesn't exist in the CFG in 596 /// DEBUG mode. There cannot be any other updates that the 597 /// dominator tree doesn't know about. 598 /// 599 /// Note that for postdominators it automatically takes care of deleting 600 /// a reverse edge internally (so there's no need to swap the parameters). 601 /// 602 void deleteEdge(NodeT *From, NodeT *To) { 603 assert(From); 604 assert(To); 605 assert(From->getParent() == Parent); 606 assert(To->getParent() == Parent); 607 DomTreeBuilder::DeleteEdge(*this, From, To); 608 } 609 610 /// Add a new node to the dominator tree information. 611 /// 612 /// This creates a new node as a child of DomBB dominator node, linking it 613 /// into the children list of the immediate dominator. 614 /// 615 /// \param BB New node in CFG. 616 /// \param DomBB CFG node that is dominator for BB. 617 /// \returns New dominator tree node that represents new CFG node. 618 /// 619 DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) { 620 assert(getNode(BB) == nullptr && "Block already in dominator tree!"); 621 DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB); 622 assert(IDomNode && "Not immediate dominator specified for block!"); 623 DFSInfoValid = false; 624 return createChild(BB, IDomNode); 625 } 626 627 /// Add a new node to the forward dominator tree and make it a new root. 628 /// 629 /// \param BB New node in CFG. 630 /// \returns New dominator tree node that represents new CFG node. 631 /// 632 DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) { 633 assert(getNode(BB) == nullptr && "Block already in dominator tree!"); 634 assert(!this->isPostDominator() && 635 "Cannot change root of post-dominator tree"); 636 DFSInfoValid = false; 637 DomTreeNodeBase<NodeT> *NewNode = createNode(BB); 638 if (Roots.empty()) { 639 addRoot(BB); 640 } else { 641 assert(Roots.size() == 1); 642 NodeT *OldRoot = Roots.front(); 643 auto &OldNode = DomTreeNodes[OldRoot]; 644 OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot])); 645 OldNode->IDom = NewNode; 646 OldNode->UpdateLevel(); 647 Roots[0] = BB; 648 } 649 return RootNode = NewNode; 650 } 651 652 /// changeImmediateDominator - This method is used to update the dominator 653 /// tree information when a node's immediate dominator changes. 654 /// 655 void changeImmediateDominator(DomTreeNodeBase<NodeT> *N, 656 DomTreeNodeBase<NodeT> *NewIDom) { 657 assert(N && NewIDom && "Cannot change null node pointers!"); 658 DFSInfoValid = false; 659 N->setIDom(NewIDom); 660 } 661 662 void changeImmediateDominator(NodeT *BB, NodeT *NewBB) { 663 changeImmediateDominator(getNode(BB), getNode(NewBB)); 664 } 665 666 /// eraseNode - Removes a node from the dominator tree. Block must not 667 /// dominate any other blocks. Removes node from its immediate dominator's 668 /// children list. Deletes dominator node associated with basic block BB. 669 void eraseNode(NodeT *BB) { 670 DomTreeNodeBase<NodeT> *Node = getNode(BB); 671 assert(Node && "Removing node that isn't in dominator tree."); 672 assert(Node->isLeaf() && "Node is not a leaf node."); 673 674 DFSInfoValid = false; 675 676 // Remove node from immediate dominator's children list. 677 DomTreeNodeBase<NodeT> *IDom = Node->getIDom(); 678 if (IDom) { 679 const auto I = find(IDom->Children, Node); 680 assert(I != IDom->Children.end() && 681 "Not in immediate dominator children set!"); 682 // I am no longer your child... 683 IDom->Children.erase(I); 684 } 685 686 DomTreeNodes.erase(BB); 687 688 if (!IsPostDom) return; 689 690 // Remember to update PostDominatorTree roots. 691 auto RIt = llvm::find(Roots, BB); 692 if (RIt != Roots.end()) { 693 std::swap(*RIt, Roots.back()); 694 Roots.pop_back(); 695 } 696 } 697 698 /// splitBlock - BB is split and now it has one successor. Update dominator 699 /// tree to reflect this change. 700 void splitBlock(NodeT *NewBB) { 701 if (IsPostDominator) 702 Split<Inverse<NodeT *>>(NewBB); 703 else 704 Split<NodeT *>(NewBB); 705 } 706 707 /// print - Convert to human readable form 708 /// 709 void print(raw_ostream &O) const { 710 O << "=============================--------------------------------\n"; 711 if (IsPostDominator) 712 O << "Inorder PostDominator Tree: "; 713 else 714 O << "Inorder Dominator Tree: "; 715 if (!DFSInfoValid) 716 O << "DFSNumbers invalid: " << SlowQueries << " slow queries."; 717 O << "\n"; 718 719 // The postdom tree can have a null root if there are no returns. 720 if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1); 721 O << "Roots: "; 722 for (const NodePtr Block : Roots) { 723 Block->printAsOperand(O, false); 724 O << " "; 725 } 726 O << "\n"; 727 } 728 729 public: 730 /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking 731 /// dominator tree in dfs order. 732 void updateDFSNumbers() const { 733 if (DFSInfoValid) { 734 SlowQueries = 0; 735 return; 736 } 737 738 SmallVector<std::pair<const DomTreeNodeBase<NodeT> *, 739 typename DomTreeNodeBase<NodeT>::const_iterator>, 740 32> WorkStack; 741 742 const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode(); 743 assert((!Parent || ThisRoot) && "Empty constructed DomTree"); 744 if (!ThisRoot) 745 return; 746 747 // Both dominators and postdominators have a single root node. In the case 748 // case of PostDominatorTree, this node is a virtual root. 749 WorkStack.push_back({ThisRoot, ThisRoot->begin()}); 750 751 unsigned DFSNum = 0; 752 ThisRoot->DFSNumIn = DFSNum++; 753 754 while (!WorkStack.empty()) { 755 const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first; 756 const auto ChildIt = WorkStack.back().second; 757 758 // If we visited all of the children of this node, "recurse" back up the 759 // stack setting the DFOutNum. 760 if (ChildIt == Node->end()) { 761 Node->DFSNumOut = DFSNum++; 762 WorkStack.pop_back(); 763 } else { 764 // Otherwise, recursively visit this child. 765 const DomTreeNodeBase<NodeT> *Child = *ChildIt; 766 ++WorkStack.back().second; 767 768 WorkStack.push_back({Child, Child->begin()}); 769 Child->DFSNumIn = DFSNum++; 770 } 771 } 772 773 SlowQueries = 0; 774 DFSInfoValid = true; 775 } 776 777 /// recalculate - compute a dominator tree for the given function 778 void recalculate(ParentType &Func) { 779 Parent = &Func; 780 DomTreeBuilder::Calculate(*this); 781 } 782 783 void recalculate(ParentType &Func, ArrayRef<UpdateType> Updates) { 784 Parent = &Func; 785 DomTreeBuilder::CalculateWithUpdates(*this, Updates); 786 } 787 788 /// verify - checks if the tree is correct. There are 3 level of verification: 789 /// - Full -- verifies if the tree is correct by making sure all the 790 /// properties (including the parent and the sibling property) 791 /// hold. 792 /// Takes O(N^3) time. 793 /// 794 /// - Basic -- checks if the tree is correct, but compares it to a freshly 795 /// constructed tree instead of checking the sibling property. 796 /// Takes O(N^2) time. 797 /// 798 /// - Fast -- checks basic tree structure and compares it with a freshly 799 /// constructed tree. 800 /// Takes O(N^2) time worst case, but is faster in practise (same 801 /// as tree construction). 802 bool verify(VerificationLevel VL = VerificationLevel::Full) const { 803 return DomTreeBuilder::Verify(*this, VL); 804 } 805 806 void reset() { 807 DomTreeNodes.clear(); 808 Roots.clear(); 809 RootNode = nullptr; 810 Parent = nullptr; 811 DFSInfoValid = false; 812 SlowQueries = 0; 813 } 814 815 protected: 816 void addRoot(NodeT *BB) { this->Roots.push_back(BB); } 817 818 DomTreeNodeBase<NodeT> *createChild(NodeT *BB, DomTreeNodeBase<NodeT> *IDom) { 819 return (DomTreeNodes[BB] = IDom->addChild( 820 std::make_unique<DomTreeNodeBase<NodeT>>(BB, IDom))) 821 .get(); 822 } 823 824 DomTreeNodeBase<NodeT> *createNode(NodeT *BB) { 825 return (DomTreeNodes[BB] = 826 std::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)) 827 .get(); 828 } 829 830 // NewBB is split and now it has one successor. Update dominator tree to 831 // reflect this change. 832 template <class N> 833 void Split(typename GraphTraits<N>::NodeRef NewBB) { 834 using GraphT = GraphTraits<N>; 835 using NodeRef = typename GraphT::NodeRef; 836 assert(std::distance(GraphT::child_begin(NewBB), 837 GraphT::child_end(NewBB)) == 1 && 838 "NewBB should have a single successor!"); 839 NodeRef NewBBSucc = *GraphT::child_begin(NewBB); 840 841 SmallVector<NodeRef, 4> PredBlocks(children<Inverse<N>>(NewBB)); 842 843 assert(!PredBlocks.empty() && "No predblocks?"); 844 845 bool NewBBDominatesNewBBSucc = true; 846 for (auto Pred : children<Inverse<N>>(NewBBSucc)) { 847 if (Pred != NewBB && !dominates(NewBBSucc, Pred) && 848 isReachableFromEntry(Pred)) { 849 NewBBDominatesNewBBSucc = false; 850 break; 851 } 852 } 853 854 // Find NewBB's immediate dominator and create new dominator tree node for 855 // NewBB. 856 NodeT *NewBBIDom = nullptr; 857 unsigned i = 0; 858 for (i = 0; i < PredBlocks.size(); ++i) 859 if (isReachableFromEntry(PredBlocks[i])) { 860 NewBBIDom = PredBlocks[i]; 861 break; 862 } 863 864 // It's possible that none of the predecessors of NewBB are reachable; 865 // in that case, NewBB itself is unreachable, so nothing needs to be 866 // changed. 867 if (!NewBBIDom) return; 868 869 for (i = i + 1; i < PredBlocks.size(); ++i) { 870 if (isReachableFromEntry(PredBlocks[i])) 871 NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]); 872 } 873 874 // Create the new dominator tree node... and set the idom of NewBB. 875 DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom); 876 877 // If NewBB strictly dominates other blocks, then it is now the immediate 878 // dominator of NewBBSucc. Update the dominator tree as appropriate. 879 if (NewBBDominatesNewBBSucc) { 880 DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc); 881 changeImmediateDominator(NewBBSuccNode, NewBBNode); 882 } 883 } 884 885 private: 886 bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A, 887 const DomTreeNodeBase<NodeT> *B) const { 888 assert(A != B); 889 assert(isReachableFromEntry(B)); 890 assert(isReachableFromEntry(A)); 891 892 const unsigned ALevel = A->getLevel(); 893 const DomTreeNodeBase<NodeT> *IDom; 894 895 // Don't walk nodes above A's subtree. When we reach A's level, we must 896 // either find A or be in some other subtree not dominated by A. 897 while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel) 898 B = IDom; // Walk up the tree 899 900 return B == A; 901 } 902 903 /// Wipe this tree's state without releasing any resources. 904 /// 905 /// This is essentially a post-move helper only. It leaves the object in an 906 /// assignable and destroyable state, but otherwise invalid. 907 void wipe() { 908 DomTreeNodes.clear(); 909 RootNode = nullptr; 910 Parent = nullptr; 911 } 912 }; 913 914 template <typename T> 915 using DomTreeBase = DominatorTreeBase<T, false>; 916 917 template <typename T> 918 using PostDomTreeBase = DominatorTreeBase<T, true>; 919 920 // These two functions are declared out of line as a workaround for building 921 // with old (< r147295) versions of clang because of pr11642. 922 template <typename NodeT, bool IsPostDom> 923 bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A, 924 const NodeT *B) const { 925 if (A == B) 926 return true; 927 928 // Cast away the const qualifiers here. This is ok since 929 // this function doesn't actually return the values returned 930 // from getNode. 931 return dominates(getNode(const_cast<NodeT *>(A)), 932 getNode(const_cast<NodeT *>(B))); 933 } 934 template <typename NodeT, bool IsPostDom> 935 bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates( 936 const NodeT *A, const NodeT *B) const { 937 if (A == B) 938 return false; 939 940 // Cast away the const qualifiers here. This is ok since 941 // this function doesn't actually return the values returned 942 // from getNode. 943 return dominates(getNode(const_cast<NodeT *>(A)), 944 getNode(const_cast<NodeT *>(B))); 945 } 946 947 } // end namespace llvm 948 949 #endif // LLVM_SUPPORT_GENERICDOMTREE_H 950