1//===- GenericDomTreeConstruction.h - Dominator Calculation ------*- 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/// Generic dominator tree construction - this file provides routines to 11/// construct immediate dominator information for a flow-graph based on the 12/// Semi-NCA algorithm described in this dissertation: 13/// 14/// [1] Linear-Time Algorithms for Dominators and Related Problems 15/// Loukas Georgiadis, Princeton University, November 2005, pp. 21-23: 16/// ftp://ftp.cs.princeton.edu/reports/2005/737.pdf 17/// 18/// Semi-NCA algorithm runs in O(n^2) worst-case time but usually slightly 19/// faster than Simple Lengauer-Tarjan in practice. 20/// 21/// O(n^2) worst cases happen when the computation of nearest common ancestors 22/// requires O(n) average time, which is very unlikely in real world. If this 23/// ever turns out to be an issue, consider implementing a hybrid algorithm 24/// that uses SLT to perform full constructions and SemiNCA for incremental 25/// updates. 26/// 27/// The file uses the Depth Based Search algorithm to perform incremental 28/// updates (insertion and deletions). The implemented algorithm is based on 29/// this publication: 30/// 31/// [2] An Experimental Study of Dynamic Dominators 32/// Loukas Georgiadis, et al., April 12 2016, pp. 5-7, 9-10: 33/// https://arxiv.org/pdf/1604.02711.pdf 34/// 35//===----------------------------------------------------------------------===// 36 37#ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H 38#define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H 39 40#include "llvm/ADT/ArrayRef.h" 41#include "llvm/ADT/DenseSet.h" 42#include "llvm/ADT/DepthFirstIterator.h" 43#include "llvm/ADT/SmallPtrSet.h" 44#include "llvm/Support/Debug.h" 45#include "llvm/Support/GenericDomTree.h" 46#include <optional> 47#include <queue> 48 49#define DEBUG_TYPE "dom-tree-builder" 50 51namespace llvm { 52namespace DomTreeBuilder { 53 54template <typename DomTreeT> 55struct SemiNCAInfo { 56 using NodePtr = typename DomTreeT::NodePtr; 57 using NodeT = typename DomTreeT::NodeType; 58 using TreeNodePtr = DomTreeNodeBase<NodeT> *; 59 using RootsT = decltype(DomTreeT::Roots); 60 static constexpr bool IsPostDom = DomTreeT::IsPostDominator; 61 using GraphDiffT = GraphDiff<NodePtr, IsPostDom>; 62 63 // Information record used by Semi-NCA during tree construction. 64 struct InfoRec { 65 unsigned DFSNum = 0; 66 unsigned Parent = 0; 67 unsigned Semi = 0; 68 unsigned Label = 0; 69 NodePtr IDom = nullptr; 70 SmallVector<unsigned, 4> ReverseChildren; 71 }; 72 73 // Number to node mapping is 1-based. Initialize the mapping to start with 74 // a dummy element. 75 std::vector<NodePtr> NumToNode = {nullptr}; 76 DenseMap<NodePtr, InfoRec> NodeToInfo; 77 78 using UpdateT = typename DomTreeT::UpdateType; 79 using UpdateKind = typename DomTreeT::UpdateKind; 80 struct BatchUpdateInfo { 81 // Note: Updates inside PreViewCFG are already legalized. 82 BatchUpdateInfo(GraphDiffT &PreViewCFG, GraphDiffT *PostViewCFG = nullptr) 83 : PreViewCFG(PreViewCFG), PostViewCFG(PostViewCFG), 84 NumLegalized(PreViewCFG.getNumLegalizedUpdates()) {} 85 86 // Remembers if the whole tree was recalculated at some point during the 87 // current batch update. 88 bool IsRecalculated = false; 89 GraphDiffT &PreViewCFG; 90 GraphDiffT *PostViewCFG; 91 const size_t NumLegalized; 92 }; 93 94 BatchUpdateInfo *BatchUpdates; 95 using BatchUpdatePtr = BatchUpdateInfo *; 96 97 // If BUI is a nullptr, then there's no batch update in progress. 98 SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {} 99 100 void clear() { 101 NumToNode = {nullptr}; // Restore to initial state with a dummy start node. 102 NodeToInfo.clear(); 103 // Don't reset the pointer to BatchUpdateInfo here -- if there's an update 104 // in progress, we need this information to continue it. 105 } 106 107 template <bool Inversed> 108 static SmallVector<NodePtr, 8> getChildren(NodePtr N, BatchUpdatePtr BUI) { 109 if (BUI) 110 return BUI->PreViewCFG.template getChildren<Inversed>(N); 111 return getChildren<Inversed>(N); 112 } 113 114 template <bool Inversed> 115 static SmallVector<NodePtr, 8> getChildren(NodePtr N) { 116 using DirectedNodeT = 117 std::conditional_t<Inversed, Inverse<NodePtr>, NodePtr>; 118 auto R = children<DirectedNodeT>(N); 119 SmallVector<NodePtr, 8> Res(detail::reverse_if<!Inversed>(R)); 120 121 // Remove nullptr children for clang. 122 llvm::erase(Res, nullptr); 123 return Res; 124 } 125 126 NodePtr getIDom(NodePtr BB) const { 127 auto InfoIt = NodeToInfo.find(BB); 128 if (InfoIt == NodeToInfo.end()) return nullptr; 129 130 return InfoIt->second.IDom; 131 } 132 133 TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT) { 134 if (TreeNodePtr Node = DT.getNode(BB)) return Node; 135 136 // Haven't calculated this node yet? Get or calculate the node for the 137 // immediate dominator. 138 NodePtr IDom = getIDom(BB); 139 140 assert(IDom || DT.DomTreeNodes[nullptr]); 141 TreeNodePtr IDomNode = getNodeForBlock(IDom, DT); 142 143 // Add a new tree node for this NodeT, and link it as a child of 144 // IDomNode 145 return DT.createChild(BB, IDomNode); 146 } 147 148 static bool AlwaysDescend(NodePtr, NodePtr) { return true; } 149 150 struct BlockNamePrinter { 151 NodePtr N; 152 153 BlockNamePrinter(NodePtr Block) : N(Block) {} 154 BlockNamePrinter(TreeNodePtr TN) : N(TN ? TN->getBlock() : nullptr) {} 155 156 friend raw_ostream &operator<<(raw_ostream &O, const BlockNamePrinter &BP) { 157 if (!BP.N) 158 O << "nullptr"; 159 else 160 BP.N->printAsOperand(O, false); 161 162 return O; 163 } 164 }; 165 166 using NodeOrderMap = DenseMap<NodePtr, unsigned>; 167 168 // Custom DFS implementation which can skip nodes based on a provided 169 // predicate. It also collects ReverseChildren so that we don't have to spend 170 // time getting predecessors in SemiNCA. 171 // 172 // If IsReverse is set to true, the DFS walk will be performed backwards 173 // relative to IsPostDom -- using reverse edges for dominators and forward 174 // edges for postdominators. 175 // 176 // If SuccOrder is specified then in this order the DFS traverses the children 177 // otherwise the order is implied by the results of getChildren(). 178 template <bool IsReverse = false, typename DescendCondition> 179 unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition, 180 unsigned AttachToNum, 181 const NodeOrderMap *SuccOrder = nullptr) { 182 assert(V); 183 SmallVector<NodePtr, 64> WorkList = {V}; 184 NodeToInfo[V].Parent = AttachToNum; 185 186 while (!WorkList.empty()) { 187 const NodePtr BB = WorkList.pop_back_val(); 188 auto &BBInfo = NodeToInfo[BB]; 189 190 // Visited nodes always have positive DFS numbers. 191 if (BBInfo.DFSNum != 0) continue; 192 BBInfo.DFSNum = BBInfo.Semi = BBInfo.Label = ++LastNum; 193 NumToNode.push_back(BB); 194 195 constexpr bool Direction = IsReverse != IsPostDom; // XOR. 196 auto Successors = getChildren<Direction>(BB, BatchUpdates); 197 if (SuccOrder && Successors.size() > 1) 198 llvm::sort( 199 Successors.begin(), Successors.end(), [=](NodePtr A, NodePtr B) { 200 return SuccOrder->find(A)->second < SuccOrder->find(B)->second; 201 }); 202 203 for (const NodePtr Succ : Successors) { 204 const auto SIT = NodeToInfo.find(Succ); 205 // Don't visit nodes more than once but remember to collect 206 // ReverseChildren. 207 if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) { 208 if (Succ != BB) SIT->second.ReverseChildren.push_back(LastNum); 209 continue; 210 } 211 212 if (!Condition(BB, Succ)) continue; 213 214 // It's fine to add Succ to the map, because we know that it will be 215 // visited later. 216 auto &SuccInfo = NodeToInfo[Succ]; 217 WorkList.push_back(Succ); 218 SuccInfo.Parent = LastNum; 219 SuccInfo.ReverseChildren.push_back(LastNum); 220 } 221 } 222 223 return LastNum; 224 } 225 226 // V is a predecessor of W. eval() returns V if V < W, otherwise the minimum 227 // of sdom(U), where U > W and there is a virtual forest path from U to V. The 228 // virtual forest consists of linked edges of processed vertices. 229 // 230 // We can follow Parent pointers (virtual forest edges) to determine the 231 // ancestor U with minimum sdom(U). But it is slow and thus we employ the path 232 // compression technique to speed up to O(m*log(n)). Theoretically the virtual 233 // forest can be organized as balanced trees to achieve almost linear 234 // O(m*alpha(m,n)) running time. But it requires two auxiliary arrays (Size 235 // and Child) and is unlikely to be faster than the simple implementation. 236 // 237 // For each vertex V, its Label points to the vertex with the minimal sdom(U) 238 // (Semi) in its path from V (included) to NodeToInfo[V].Parent (excluded). 239 unsigned eval(unsigned V, unsigned LastLinked, 240 SmallVectorImpl<InfoRec *> &Stack, 241 ArrayRef<InfoRec *> NumToInfo) { 242 InfoRec *VInfo = NumToInfo[V]; 243 if (VInfo->Parent < LastLinked) 244 return VInfo->Label; 245 246 // Store ancestors except the last (root of a virtual tree) into a stack. 247 assert(Stack.empty()); 248 do { 249 Stack.push_back(VInfo); 250 VInfo = NumToInfo[VInfo->Parent]; 251 } while (VInfo->Parent >= LastLinked); 252 253 // Path compression. Point each vertex's Parent to the root and update its 254 // Label if any of its ancestors (PInfo->Label) has a smaller Semi. 255 const InfoRec *PInfo = VInfo; 256 const InfoRec *PLabelInfo = NumToInfo[PInfo->Label]; 257 do { 258 VInfo = Stack.pop_back_val(); 259 VInfo->Parent = PInfo->Parent; 260 const InfoRec *VLabelInfo = NumToInfo[VInfo->Label]; 261 if (PLabelInfo->Semi < VLabelInfo->Semi) 262 VInfo->Label = PInfo->Label; 263 else 264 PLabelInfo = VLabelInfo; 265 PInfo = VInfo; 266 } while (!Stack.empty()); 267 return VInfo->Label; 268 } 269 270 // This function requires DFS to be run before calling it. 271 void runSemiNCA() { 272 const unsigned NextDFSNum(NumToNode.size()); 273 SmallVector<InfoRec *, 8> NumToInfo = {nullptr}; 274 NumToInfo.reserve(NextDFSNum); 275 // Initialize IDoms to spanning tree parents. 276 for (unsigned i = 1; i < NextDFSNum; ++i) { 277 const NodePtr V = NumToNode[i]; 278 auto &VInfo = NodeToInfo[V]; 279 VInfo.IDom = NumToNode[VInfo.Parent]; 280 NumToInfo.push_back(&VInfo); 281 } 282 283 // Step #1: Calculate the semidominators of all vertices. 284 SmallVector<InfoRec *, 32> EvalStack; 285 for (unsigned i = NextDFSNum - 1; i >= 2; --i) { 286 auto &WInfo = *NumToInfo[i]; 287 288 // Initialize the semi dominator to point to the parent node. 289 WInfo.Semi = WInfo.Parent; 290 for (unsigned N : WInfo.ReverseChildren) { 291 unsigned SemiU = NumToInfo[eval(N, i + 1, EvalStack, NumToInfo)]->Semi; 292 if (SemiU < WInfo.Semi) WInfo.Semi = SemiU; 293 } 294 } 295 296 // Step #2: Explicitly define the immediate dominator of each vertex. 297 // IDom[i] = NCA(SDom[i], SpanningTreeParent(i)). 298 // Note that the parents were stored in IDoms and later got invalidated 299 // during path compression in Eval. 300 for (unsigned i = 2; i < NextDFSNum; ++i) { 301 auto &WInfo = *NumToInfo[i]; 302 assert(WInfo.Semi != 0); 303 const unsigned SDomNum = NumToInfo[WInfo.Semi]->DFSNum; 304 NodePtr WIDomCandidate = WInfo.IDom; 305 while (true) { 306 auto &WIDomCandidateInfo = NodeToInfo.find(WIDomCandidate)->second; 307 if (WIDomCandidateInfo.DFSNum <= SDomNum) 308 break; 309 WIDomCandidate = WIDomCandidateInfo.IDom; 310 } 311 312 WInfo.IDom = WIDomCandidate; 313 } 314 } 315 316 // PostDominatorTree always has a virtual root that represents a virtual CFG 317 // node that serves as a single exit from the function. All the other exits 318 // (CFG nodes with terminators and nodes in infinite loops are logically 319 // connected to this virtual CFG exit node). 320 // This functions maps a nullptr CFG node to the virtual root tree node. 321 void addVirtualRoot() { 322 assert(IsPostDom && "Only postdominators have a virtual root"); 323 assert(NumToNode.size() == 1 && "SNCAInfo must be freshly constructed"); 324 325 auto &BBInfo = NodeToInfo[nullptr]; 326 BBInfo.DFSNum = BBInfo.Semi = BBInfo.Label = 1; 327 328 NumToNode.push_back(nullptr); // NumToNode[1] = nullptr; 329 } 330 331 // For postdominators, nodes with no forward successors are trivial roots that 332 // are always selected as tree roots. Roots with forward successors correspond 333 // to CFG nodes within infinite loops. 334 static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI) { 335 assert(N && "N must be a valid node"); 336 return !getChildren<false>(N, BUI).empty(); 337 } 338 339 static NodePtr GetEntryNode(const DomTreeT &DT) { 340 assert(DT.Parent && "Parent not set"); 341 return GraphTraits<typename DomTreeT::ParentPtr>::getEntryNode(DT.Parent); 342 } 343 344 // Finds all roots without relaying on the set of roots already stored in the 345 // tree. 346 // We define roots to be some non-redundant set of the CFG nodes 347 static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI) { 348 assert(DT.Parent && "Parent pointer is not set"); 349 RootsT Roots; 350 351 // For dominators, function entry CFG node is always a tree root node. 352 if (!IsPostDom) { 353 Roots.push_back(GetEntryNode(DT)); 354 return Roots; 355 } 356 357 SemiNCAInfo SNCA(BUI); 358 359 // PostDominatorTree always has a virtual root. 360 SNCA.addVirtualRoot(); 361 unsigned Num = 1; 362 363 LLVM_DEBUG(dbgs() << "\t\tLooking for trivial roots\n"); 364 365 // Step #1: Find all the trivial roots that are going to will definitely 366 // remain tree roots. 367 unsigned Total = 0; 368 // It may happen that there are some new nodes in the CFG that are result of 369 // the ongoing batch update, but we cannot really pretend that they don't 370 // exist -- we won't see any outgoing or incoming edges to them, so it's 371 // fine to discover them here, as they would end up appearing in the CFG at 372 // some point anyway. 373 for (const NodePtr N : nodes(DT.Parent)) { 374 ++Total; 375 // If it has no *successors*, it is definitely a root. 376 if (!HasForwardSuccessors(N, BUI)) { 377 Roots.push_back(N); 378 // Run DFS not to walk this part of CFG later. 379 Num = SNCA.runDFS(N, Num, AlwaysDescend, 1); 380 LLVM_DEBUG(dbgs() << "Found a new trivial root: " << BlockNamePrinter(N) 381 << "\n"); 382 LLVM_DEBUG(dbgs() << "Last visited node: " 383 << BlockNamePrinter(SNCA.NumToNode[Num]) << "\n"); 384 } 385 } 386 387 LLVM_DEBUG(dbgs() << "\t\tLooking for non-trivial roots\n"); 388 389 // Step #2: Find all non-trivial root candidates. Those are CFG nodes that 390 // are reverse-unreachable were not visited by previous DFS walks (i.e. CFG 391 // nodes in infinite loops). 392 bool HasNonTrivialRoots = false; 393 // Accounting for the virtual exit, see if we had any reverse-unreachable 394 // nodes. 395 if (Total + 1 != Num) { 396 HasNonTrivialRoots = true; 397 398 // SuccOrder is the order of blocks in the function. It is needed to make 399 // the calculation of the FurthestAway node and the whole PostDomTree 400 // immune to swap successors transformation (e.g. canonicalizing branch 401 // predicates). SuccOrder is initialized lazily only for successors of 402 // reverse unreachable nodes. 403 std::optional<NodeOrderMap> SuccOrder; 404 auto InitSuccOrderOnce = [&]() { 405 SuccOrder = NodeOrderMap(); 406 for (const auto Node : nodes(DT.Parent)) 407 if (SNCA.NodeToInfo.count(Node) == 0) 408 for (const auto Succ : getChildren<false>(Node, SNCA.BatchUpdates)) 409 SuccOrder->try_emplace(Succ, 0); 410 411 // Add mapping for all entries of SuccOrder. 412 unsigned NodeNum = 0; 413 for (const auto Node : nodes(DT.Parent)) { 414 ++NodeNum; 415 auto Order = SuccOrder->find(Node); 416 if (Order != SuccOrder->end()) { 417 assert(Order->second == 0); 418 Order->second = NodeNum; 419 } 420 } 421 }; 422 423 // Make another DFS pass over all other nodes to find the 424 // reverse-unreachable blocks, and find the furthest paths we'll be able 425 // to make. 426 // Note that this looks N^2, but it's really 2N worst case, if every node 427 // is unreachable. This is because we are still going to only visit each 428 // unreachable node once, we may just visit it in two directions, 429 // depending on how lucky we get. 430 for (const NodePtr I : nodes(DT.Parent)) { 431 if (SNCA.NodeToInfo.count(I) == 0) { 432 LLVM_DEBUG(dbgs() 433 << "\t\t\tVisiting node " << BlockNamePrinter(I) << "\n"); 434 // Find the furthest away we can get by following successors, then 435 // follow them in reverse. This gives us some reasonable answer about 436 // the post-dom tree inside any infinite loop. In particular, it 437 // guarantees we get to the farthest away point along *some* 438 // path. This also matches the GCC's behavior. 439 // If we really wanted a totally complete picture of dominance inside 440 // this infinite loop, we could do it with SCC-like algorithms to find 441 // the lowest and highest points in the infinite loop. In theory, it 442 // would be nice to give the canonical backedge for the loop, but it's 443 // expensive and does not always lead to a minimal set of roots. 444 LLVM_DEBUG(dbgs() << "\t\t\tRunning forward DFS\n"); 445 446 if (!SuccOrder) 447 InitSuccOrderOnce(); 448 assert(SuccOrder); 449 450 const unsigned NewNum = 451 SNCA.runDFS<true>(I, Num, AlwaysDescend, Num, &*SuccOrder); 452 const NodePtr FurthestAway = SNCA.NumToNode[NewNum]; 453 LLVM_DEBUG(dbgs() << "\t\t\tFound a new furthest away node " 454 << "(non-trivial root): " 455 << BlockNamePrinter(FurthestAway) << "\n"); 456 Roots.push_back(FurthestAway); 457 LLVM_DEBUG(dbgs() << "\t\t\tPrev DFSNum: " << Num << ", new DFSNum: " 458 << NewNum << "\n\t\t\tRemoving DFS info\n"); 459 for (unsigned i = NewNum; i > Num; --i) { 460 const NodePtr N = SNCA.NumToNode[i]; 461 LLVM_DEBUG(dbgs() << "\t\t\t\tRemoving DFS info for " 462 << BlockNamePrinter(N) << "\n"); 463 SNCA.NodeToInfo.erase(N); 464 SNCA.NumToNode.pop_back(); 465 } 466 const unsigned PrevNum = Num; 467 LLVM_DEBUG(dbgs() << "\t\t\tRunning reverse DFS\n"); 468 Num = SNCA.runDFS(FurthestAway, Num, AlwaysDescend, 1); 469 for (unsigned i = PrevNum + 1; i <= Num; ++i) 470 LLVM_DEBUG(dbgs() << "\t\t\t\tfound node " 471 << BlockNamePrinter(SNCA.NumToNode[i]) << "\n"); 472 } 473 } 474 } 475 476 LLVM_DEBUG(dbgs() << "Total: " << Total << ", Num: " << Num << "\n"); 477 LLVM_DEBUG(dbgs() << "Discovered CFG nodes:\n"); 478 LLVM_DEBUG(for (size_t i = 0; i <= Num; ++i) dbgs() 479 << i << ": " << BlockNamePrinter(SNCA.NumToNode[i]) << "\n"); 480 481 assert((Total + 1 == Num) && "Everything should have been visited"); 482 483 // Step #3: If we found some non-trivial roots, make them non-redundant. 484 if (HasNonTrivialRoots) RemoveRedundantRoots(DT, BUI, Roots); 485 486 LLVM_DEBUG(dbgs() << "Found roots: "); 487 LLVM_DEBUG(for (auto *Root 488 : Roots) dbgs() 489 << BlockNamePrinter(Root) << " "); 490 LLVM_DEBUG(dbgs() << "\n"); 491 492 return Roots; 493 } 494 495 // This function only makes sense for postdominators. 496 // We define roots to be some set of CFG nodes where (reverse) DFS walks have 497 // to start in order to visit all the CFG nodes (including the 498 // reverse-unreachable ones). 499 // When the search for non-trivial roots is done it may happen that some of 500 // the non-trivial roots are reverse-reachable from other non-trivial roots, 501 // which makes them redundant. This function removes them from the set of 502 // input roots. 503 static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI, 504 RootsT &Roots) { 505 assert(IsPostDom && "This function is for postdominators only"); 506 LLVM_DEBUG(dbgs() << "Removing redundant roots\n"); 507 508 SemiNCAInfo SNCA(BUI); 509 510 for (unsigned i = 0; i < Roots.size(); ++i) { 511 auto &Root = Roots[i]; 512 // Trivial roots are always non-redundant. 513 if (!HasForwardSuccessors(Root, BUI)) continue; 514 LLVM_DEBUG(dbgs() << "\tChecking if " << BlockNamePrinter(Root) 515 << " remains a root\n"); 516 SNCA.clear(); 517 // Do a forward walk looking for the other roots. 518 const unsigned Num = SNCA.runDFS<true>(Root, 0, AlwaysDescend, 0); 519 // Skip the start node and begin from the second one (note that DFS uses 520 // 1-based indexing). 521 for (unsigned x = 2; x <= Num; ++x) { 522 const NodePtr N = SNCA.NumToNode[x]; 523 // If we wound another root in a (forward) DFS walk, remove the current 524 // root from the set of roots, as it is reverse-reachable from the other 525 // one. 526 if (llvm::is_contained(Roots, N)) { 527 LLVM_DEBUG(dbgs() << "\tForward DFS walk found another root " 528 << BlockNamePrinter(N) << "\n\tRemoving root " 529 << BlockNamePrinter(Root) << "\n"); 530 std::swap(Root, Roots.back()); 531 Roots.pop_back(); 532 533 // Root at the back takes the current root's place. 534 // Start the next loop iteration with the same index. 535 --i; 536 break; 537 } 538 } 539 } 540 } 541 542 template <typename DescendCondition> 543 void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) { 544 if (!IsPostDom) { 545 assert(DT.Roots.size() == 1 && "Dominators should have a singe root"); 546 runDFS(DT.Roots[0], 0, DC, 0); 547 return; 548 } 549 550 addVirtualRoot(); 551 unsigned Num = 1; 552 for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 1); 553 } 554 555 static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) { 556 auto *Parent = DT.Parent; 557 DT.reset(); 558 DT.Parent = Parent; 559 // If the update is using the actual CFG, BUI is null. If it's using a view, 560 // BUI is non-null and the PreCFGView is used. When calculating from 561 // scratch, make the PreViewCFG equal to the PostCFGView, so Post is used. 562 BatchUpdatePtr PostViewBUI = nullptr; 563 if (BUI && BUI->PostViewCFG) { 564 BUI->PreViewCFG = *BUI->PostViewCFG; 565 PostViewBUI = BUI; 566 } 567 // This is rebuilding the whole tree, not incrementally, but PostViewBUI is 568 // used in case the caller needs a DT update with a CFGView. 569 SemiNCAInfo SNCA(PostViewBUI); 570 571 // Step #0: Number blocks in depth-first order and initialize variables used 572 // in later stages of the algorithm. 573 DT.Roots = FindRoots(DT, PostViewBUI); 574 SNCA.doFullDFSWalk(DT, AlwaysDescend); 575 576 SNCA.runSemiNCA(); 577 if (BUI) { 578 BUI->IsRecalculated = true; 579 LLVM_DEBUG( 580 dbgs() << "DomTree recalculated, skipping future batch updates\n"); 581 } 582 583 if (DT.Roots.empty()) return; 584 585 // Add a node for the root. If the tree is a PostDominatorTree it will be 586 // the virtual exit (denoted by (BasicBlock *) nullptr) which postdominates 587 // all real exits (including multiple exit blocks, infinite loops). 588 NodePtr Root = IsPostDom ? nullptr : DT.Roots[0]; 589 590 DT.RootNode = DT.createNode(Root); 591 SNCA.attachNewSubtree(DT, DT.RootNode); 592 } 593 594 void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) { 595 // Attach the first unreachable block to AttachTo. 596 NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock(); 597 // Loop over all of the discovered blocks in the function... 598 for (size_t i = 1, e = NumToNode.size(); i != e; ++i) { 599 NodePtr W = NumToNode[i]; 600 601 // Don't replace this with 'count', the insertion side effect is important 602 if (DT.DomTreeNodes[W]) continue; // Haven't calculated this node yet? 603 604 NodePtr ImmDom = getIDom(W); 605 606 // Get or calculate the node for the immediate dominator. 607 TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT); 608 609 // Add a new tree node for this BasicBlock, and link it as a child of 610 // IDomNode. 611 DT.createChild(W, IDomNode); 612 } 613 } 614 615 void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) { 616 NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock(); 617 for (size_t i = 1, e = NumToNode.size(); i != e; ++i) { 618 const NodePtr N = NumToNode[i]; 619 const TreeNodePtr TN = DT.getNode(N); 620 assert(TN); 621 const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom); 622 TN->setIDom(NewIDom); 623 } 624 } 625 626 // Helper struct used during edge insertions. 627 struct InsertionInfo { 628 struct Compare { 629 bool operator()(TreeNodePtr LHS, TreeNodePtr RHS) const { 630 return LHS->getLevel() < RHS->getLevel(); 631 } 632 }; 633 634 // Bucket queue of tree nodes ordered by descending level. For simplicity, 635 // we use a priority_queue here. 636 std::priority_queue<TreeNodePtr, SmallVector<TreeNodePtr, 8>, 637 Compare> 638 Bucket; 639 SmallDenseSet<TreeNodePtr, 8> Visited; 640 SmallVector<TreeNodePtr, 8> Affected; 641#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS 642 SmallVector<TreeNodePtr, 8> VisitedUnaffected; 643#endif 644 }; 645 646 static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI, 647 const NodePtr From, const NodePtr To) { 648 assert((From || IsPostDom) && 649 "From has to be a valid CFG node or a virtual root"); 650 assert(To && "Cannot be a nullptr"); 651 LLVM_DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> " 652 << BlockNamePrinter(To) << "\n"); 653 TreeNodePtr FromTN = DT.getNode(From); 654 655 if (!FromTN) { 656 // Ignore edges from unreachable nodes for (forward) dominators. 657 if (!IsPostDom) return; 658 659 // The unreachable node becomes a new root -- a tree node for it. 660 TreeNodePtr VirtualRoot = DT.getNode(nullptr); 661 FromTN = DT.createChild(From, VirtualRoot); 662 DT.Roots.push_back(From); 663 } 664 665 DT.DFSInfoValid = false; 666 667 const TreeNodePtr ToTN = DT.getNode(To); 668 if (!ToTN) 669 InsertUnreachable(DT, BUI, FromTN, To); 670 else 671 InsertReachable(DT, BUI, FromTN, ToTN); 672 } 673 674 // Determines if some existing root becomes reverse-reachable after the 675 // insertion. Rebuilds the whole tree if that situation happens. 676 static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, 677 const TreeNodePtr From, 678 const TreeNodePtr To) { 679 assert(IsPostDom && "This function is only for postdominators"); 680 // Destination node is not attached to the virtual root, so it cannot be a 681 // root. 682 if (!DT.isVirtualRoot(To->getIDom())) return false; 683 684 if (!llvm::is_contained(DT.Roots, To->getBlock())) 685 return false; // To is not a root, nothing to update. 686 687 LLVM_DEBUG(dbgs() << "\t\tAfter the insertion, " << BlockNamePrinter(To) 688 << " is no longer a root\n\t\tRebuilding the tree!!!\n"); 689 690 CalculateFromScratch(DT, BUI); 691 return true; 692 } 693 694 static bool isPermutation(const SmallVectorImpl<NodePtr> &A, 695 const SmallVectorImpl<NodePtr> &B) { 696 if (A.size() != B.size()) 697 return false; 698 SmallPtrSet<NodePtr, 4> Set(A.begin(), A.end()); 699 for (NodePtr N : B) 700 if (Set.count(N) == 0) 701 return false; 702 return true; 703 } 704 705 // Updates the set of roots after insertion or deletion. This ensures that 706 // roots are the same when after a series of updates and when the tree would 707 // be built from scratch. 708 static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI) { 709 assert(IsPostDom && "This function is only for postdominators"); 710 711 // The tree has only trivial roots -- nothing to update. 712 if (llvm::none_of(DT.Roots, [BUI](const NodePtr N) { 713 return HasForwardSuccessors(N, BUI); 714 })) 715 return; 716 717 // Recalculate the set of roots. 718 RootsT Roots = FindRoots(DT, BUI); 719 if (!isPermutation(DT.Roots, Roots)) { 720 // The roots chosen in the CFG have changed. This is because the 721 // incremental algorithm does not really know or use the set of roots and 722 // can make a different (implicit) decision about which node within an 723 // infinite loop becomes a root. 724 725 LLVM_DEBUG(dbgs() << "Roots are different in updated trees\n" 726 << "The entire tree needs to be rebuilt\n"); 727 // It may be possible to update the tree without recalculating it, but 728 // we do not know yet how to do it, and it happens rarely in practice. 729 CalculateFromScratch(DT, BUI); 730 } 731 } 732 733 // Handles insertion to a node already in the dominator tree. 734 static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI, 735 const TreeNodePtr From, const TreeNodePtr To) { 736 LLVM_DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock()) 737 << " -> " << BlockNamePrinter(To->getBlock()) << "\n"); 738 if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return; 739 // DT.findNCD expects both pointers to be valid. When From is a virtual 740 // root, then its CFG block pointer is a nullptr, so we have to 'compute' 741 // the NCD manually. 742 const NodePtr NCDBlock = 743 (From->getBlock() && To->getBlock()) 744 ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock()) 745 : nullptr; 746 assert(NCDBlock || DT.isPostDominator()); 747 const TreeNodePtr NCD = DT.getNode(NCDBlock); 748 assert(NCD); 749 750 LLVM_DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n"); 751 const unsigned NCDLevel = NCD->getLevel(); 752 753 // Based on Lemma 2.5 from [2], after insertion of (From,To), v is affected 754 // iff depth(NCD)+1 < depth(v) && a path P from To to v exists where every 755 // w on P s.t. depth(v) <= depth(w) 756 // 757 // This reduces to a widest path problem (maximizing the depth of the 758 // minimum vertex in the path) which can be solved by a modified version of 759 // Dijkstra with a bucket queue (named depth-based search in [2]). 760 761 // To is in the path, so depth(NCD)+1 < depth(v) <= depth(To). Nothing 762 // affected if this does not hold. 763 if (NCDLevel + 1 >= To->getLevel()) 764 return; 765 766 InsertionInfo II; 767 SmallVector<TreeNodePtr, 8> UnaffectedOnCurrentLevel; 768 II.Bucket.push(To); 769 II.Visited.insert(To); 770 771 while (!II.Bucket.empty()) { 772 TreeNodePtr TN = II.Bucket.top(); 773 II.Bucket.pop(); 774 II.Affected.push_back(TN); 775 776 const unsigned CurrentLevel = TN->getLevel(); 777 LLVM_DEBUG(dbgs() << "Mark " << BlockNamePrinter(TN) << 778 "as affected, CurrentLevel " << CurrentLevel << "\n"); 779 780 assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!"); 781 782 while (true) { 783 // Unlike regular Dijkstra, we have an inner loop to expand more 784 // vertices. The first iteration is for the (affected) vertex popped 785 // from II.Bucket and the rest are for vertices in 786 // UnaffectedOnCurrentLevel, which may eventually expand to affected 787 // vertices. 788 // 789 // Invariant: there is an optimal path from `To` to TN with the minimum 790 // depth being CurrentLevel. 791 for (const NodePtr Succ : getChildren<IsPostDom>(TN->getBlock(), BUI)) { 792 const TreeNodePtr SuccTN = DT.getNode(Succ); 793 assert(SuccTN && 794 "Unreachable successor found at reachable insertion"); 795 const unsigned SuccLevel = SuccTN->getLevel(); 796 797 LLVM_DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ) 798 << ", level = " << SuccLevel << "\n"); 799 800 // There is an optimal path from `To` to Succ with the minimum depth 801 // being min(CurrentLevel, SuccLevel). 802 // 803 // If depth(NCD)+1 < depth(Succ) is not satisfied, Succ is unaffected 804 // and no affected vertex may be reached by a path passing through it. 805 // Stop here. Also, Succ may be visited by other predecessors but the 806 // first visit has the optimal path. Stop if Succ has been visited. 807 if (SuccLevel <= NCDLevel + 1 || !II.Visited.insert(SuccTN).second) 808 continue; 809 810 if (SuccLevel > CurrentLevel) { 811 // Succ is unaffected but it may (transitively) expand to affected 812 // vertices. Store it in UnaffectedOnCurrentLevel. 813 LLVM_DEBUG(dbgs() << "\t\tMarking visited not affected " 814 << BlockNamePrinter(Succ) << "\n"); 815 UnaffectedOnCurrentLevel.push_back(SuccTN); 816#ifndef NDEBUG 817 II.VisitedUnaffected.push_back(SuccTN); 818#endif 819 } else { 820 // The condition is satisfied (Succ is affected). Add Succ to the 821 // bucket queue. 822 LLVM_DEBUG(dbgs() << "\t\tAdd " << BlockNamePrinter(Succ) 823 << " to a Bucket\n"); 824 II.Bucket.push(SuccTN); 825 } 826 } 827 828 if (UnaffectedOnCurrentLevel.empty()) 829 break; 830 TN = UnaffectedOnCurrentLevel.pop_back_val(); 831 LLVM_DEBUG(dbgs() << " Next: " << BlockNamePrinter(TN) << "\n"); 832 } 833 } 834 835 // Finish by updating immediate dominators and levels. 836 UpdateInsertion(DT, BUI, NCD, II); 837 } 838 839 // Updates immediate dominators and levels after insertion. 840 static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, 841 const TreeNodePtr NCD, InsertionInfo &II) { 842 LLVM_DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n"); 843 844 for (const TreeNodePtr TN : II.Affected) { 845 LLVM_DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN) 846 << ") = " << BlockNamePrinter(NCD) << "\n"); 847 TN->setIDom(NCD); 848 } 849 850#if defined(LLVM_ENABLE_ABI_BREAKING_CHECKS) && !defined(NDEBUG) 851 for (const TreeNodePtr TN : II.VisitedUnaffected) 852 assert(TN->getLevel() == TN->getIDom()->getLevel() + 1 && 853 "TN should have been updated by an affected ancestor"); 854#endif 855 856 if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI); 857 } 858 859 // Handles insertion to previously unreachable nodes. 860 static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, 861 const TreeNodePtr From, const NodePtr To) { 862 LLVM_DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From) 863 << " -> (unreachable) " << BlockNamePrinter(To) << "\n"); 864 865 // Collect discovered edges to already reachable nodes. 866 SmallVector<std::pair<NodePtr, TreeNodePtr>, 8> DiscoveredEdgesToReachable; 867 // Discover and connect nodes that became reachable with the insertion. 868 ComputeUnreachableDominators(DT, BUI, To, From, DiscoveredEdgesToReachable); 869 870 LLVM_DEBUG(dbgs() << "Inserted " << BlockNamePrinter(From) 871 << " -> (prev unreachable) " << BlockNamePrinter(To) 872 << "\n"); 873 874 // Used the discovered edges and inset discovered connecting (incoming) 875 // edges. 876 for (const auto &Edge : DiscoveredEdgesToReachable) { 877 LLVM_DEBUG(dbgs() << "\tInserting discovered connecting edge " 878 << BlockNamePrinter(Edge.first) << " -> " 879 << BlockNamePrinter(Edge.second) << "\n"); 880 InsertReachable(DT, BUI, DT.getNode(Edge.first), Edge.second); 881 } 882 } 883 884 // Connects nodes that become reachable with an insertion. 885 static void ComputeUnreachableDominators( 886 DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root, 887 const TreeNodePtr Incoming, 888 SmallVectorImpl<std::pair<NodePtr, TreeNodePtr>> 889 &DiscoveredConnectingEdges) { 890 assert(!DT.getNode(Root) && "Root must not be reachable"); 891 892 // Visit only previously unreachable nodes. 893 auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From, 894 NodePtr To) { 895 const TreeNodePtr ToTN = DT.getNode(To); 896 if (!ToTN) return true; 897 898 DiscoveredConnectingEdges.push_back({From, ToTN}); 899 return false; 900 }; 901 902 SemiNCAInfo SNCA(BUI); 903 SNCA.runDFS(Root, 0, UnreachableDescender, 0); 904 SNCA.runSemiNCA(); 905 SNCA.attachNewSubtree(DT, Incoming); 906 907 LLVM_DEBUG(dbgs() << "After adding unreachable nodes\n"); 908 } 909 910 static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI, 911 const NodePtr From, const NodePtr To) { 912 assert(From && To && "Cannot disconnect nullptrs"); 913 LLVM_DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> " 914 << BlockNamePrinter(To) << "\n"); 915 916#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS 917 // Ensure that the edge was in fact deleted from the CFG before informing 918 // the DomTree about it. 919 // The check is O(N), so run it only in debug configuration. 920 auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) { 921 auto Successors = getChildren<IsPostDom>(Of, BUI); 922 return llvm::is_contained(Successors, SuccCandidate); 923 }; 924 (void)IsSuccessor; 925 assert(!IsSuccessor(To, From) && "Deleted edge still exists in the CFG!"); 926#endif 927 928 const TreeNodePtr FromTN = DT.getNode(From); 929 // Deletion in an unreachable subtree -- nothing to do. 930 if (!FromTN) return; 931 932 const TreeNodePtr ToTN = DT.getNode(To); 933 if (!ToTN) { 934 LLVM_DEBUG( 935 dbgs() << "\tTo (" << BlockNamePrinter(To) 936 << ") already unreachable -- there is no edge to delete\n"); 937 return; 938 } 939 940 const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To); 941 const TreeNodePtr NCD = DT.getNode(NCDBlock); 942 943 // If To dominates From -- nothing to do. 944 if (ToTN != NCD) { 945 DT.DFSInfoValid = false; 946 947 const TreeNodePtr ToIDom = ToTN->getIDom(); 948 LLVM_DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom " 949 << BlockNamePrinter(ToIDom) << "\n"); 950 951 // To remains reachable after deletion. 952 // (Based on the caption under Figure 4. from [2].) 953 if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN)) 954 DeleteReachable(DT, BUI, FromTN, ToTN); 955 else 956 DeleteUnreachable(DT, BUI, ToTN); 957 } 958 959 if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI); 960 } 961 962 // Handles deletions that leave destination nodes reachable. 963 static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI, 964 const TreeNodePtr FromTN, 965 const TreeNodePtr ToTN) { 966 LLVM_DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN) 967 << " -> " << BlockNamePrinter(ToTN) << "\n"); 968 LLVM_DEBUG(dbgs() << "\tRebuilding subtree\n"); 969 970 // Find the top of the subtree that needs to be rebuilt. 971 // (Based on the lemma 2.6 from [2].) 972 const NodePtr ToIDom = 973 DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock()); 974 assert(ToIDom || DT.isPostDominator()); 975 const TreeNodePtr ToIDomTN = DT.getNode(ToIDom); 976 assert(ToIDomTN); 977 const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom(); 978 // Top of the subtree to rebuild is the root node. Rebuild the tree from 979 // scratch. 980 if (!PrevIDomSubTree) { 981 LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n"); 982 CalculateFromScratch(DT, BUI); 983 return; 984 } 985 986 // Only visit nodes in the subtree starting at To. 987 const unsigned Level = ToIDomTN->getLevel(); 988 auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) { 989 return DT.getNode(To)->getLevel() > Level; 990 }; 991 992 LLVM_DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN) 993 << "\n"); 994 995 SemiNCAInfo SNCA(BUI); 996 SNCA.runDFS(ToIDom, 0, DescendBelow, 0); 997 LLVM_DEBUG(dbgs() << "\tRunning Semi-NCA\n"); 998 SNCA.runSemiNCA(); 999 SNCA.reattachExistingSubtree(DT, PrevIDomSubTree); 1000 } 1001 1002 // Checks if a node has proper support, as defined on the page 3 and later 1003 // explained on the page 7 of [2]. 1004 static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI, 1005 const TreeNodePtr TN) { 1006 LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN) 1007 << "\n"); 1008 auto TNB = TN->getBlock(); 1009 for (const NodePtr Pred : getChildren<!IsPostDom>(TNB, BUI)) { 1010 LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n"); 1011 if (!DT.getNode(Pred)) continue; 1012 1013 const NodePtr Support = DT.findNearestCommonDominator(TNB, Pred); 1014 LLVM_DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n"); 1015 if (Support != TNB) { 1016 LLVM_DEBUG(dbgs() << "\t" << BlockNamePrinter(TN) 1017 << " is reachable from support " 1018 << BlockNamePrinter(Support) << "\n"); 1019 return true; 1020 } 1021 } 1022 1023 return false; 1024 } 1025 1026 // Handle deletions that make destination node unreachable. 1027 // (Based on the lemma 2.7 from the [2].) 1028 static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, 1029 const TreeNodePtr ToTN) { 1030 LLVM_DEBUG(dbgs() << "Deleting unreachable subtree " 1031 << BlockNamePrinter(ToTN) << "\n"); 1032 assert(ToTN); 1033 assert(ToTN->getBlock()); 1034 1035 if (IsPostDom) { 1036 // Deletion makes a region reverse-unreachable and creates a new root. 1037 // Simulate that by inserting an edge from the virtual root to ToTN and 1038 // adding it as a new root. 1039 LLVM_DEBUG(dbgs() << "\tDeletion made a region reverse-unreachable\n"); 1040 LLVM_DEBUG(dbgs() << "\tAdding new root " << BlockNamePrinter(ToTN) 1041 << "\n"); 1042 DT.Roots.push_back(ToTN->getBlock()); 1043 InsertReachable(DT, BUI, DT.getNode(nullptr), ToTN); 1044 return; 1045 } 1046 1047 SmallVector<NodePtr, 16> AffectedQueue; 1048 const unsigned Level = ToTN->getLevel(); 1049 1050 // Traverse destination node's descendants with greater level in the tree 1051 // and collect visited nodes. 1052 auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) { 1053 const TreeNodePtr TN = DT.getNode(To); 1054 assert(TN); 1055 if (TN->getLevel() > Level) return true; 1056 if (!llvm::is_contained(AffectedQueue, To)) 1057 AffectedQueue.push_back(To); 1058 1059 return false; 1060 }; 1061 1062 SemiNCAInfo SNCA(BUI); 1063 unsigned LastDFSNum = 1064 SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0); 1065 1066 TreeNodePtr MinNode = ToTN; 1067 1068 // Identify the top of the subtree to rebuild by finding the NCD of all 1069 // the affected nodes. 1070 for (const NodePtr N : AffectedQueue) { 1071 const TreeNodePtr TN = DT.getNode(N); 1072 const NodePtr NCDBlock = 1073 DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock()); 1074 assert(NCDBlock || DT.isPostDominator()); 1075 const TreeNodePtr NCD = DT.getNode(NCDBlock); 1076 assert(NCD); 1077 1078 LLVM_DEBUG(dbgs() << "Processing affected node " << BlockNamePrinter(TN) 1079 << " with NCD = " << BlockNamePrinter(NCD) 1080 << ", MinNode =" << BlockNamePrinter(MinNode) << "\n"); 1081 if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD; 1082 } 1083 1084 // Root reached, rebuild the whole tree from scratch. 1085 if (!MinNode->getIDom()) { 1086 LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n"); 1087 CalculateFromScratch(DT, BUI); 1088 return; 1089 } 1090 1091 // Erase the unreachable subtree in reverse preorder to process all children 1092 // before deleting their parent. 1093 for (unsigned i = LastDFSNum; i > 0; --i) { 1094 const NodePtr N = SNCA.NumToNode[i]; 1095 const TreeNodePtr TN = DT.getNode(N); 1096 LLVM_DEBUG(dbgs() << "Erasing node " << BlockNamePrinter(TN) << "\n"); 1097 1098 EraseNode(DT, TN); 1099 } 1100 1101 // The affected subtree start at the To node -- there's no extra work to do. 1102 if (MinNode == ToTN) return; 1103 1104 LLVM_DEBUG(dbgs() << "DeleteUnreachable: running DFS with MinNode = " 1105 << BlockNamePrinter(MinNode) << "\n"); 1106 const unsigned MinLevel = MinNode->getLevel(); 1107 const TreeNodePtr PrevIDom = MinNode->getIDom(); 1108 assert(PrevIDom); 1109 SNCA.clear(); 1110 1111 // Identify nodes that remain in the affected subtree. 1112 auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) { 1113 const TreeNodePtr ToTN = DT.getNode(To); 1114 return ToTN && ToTN->getLevel() > MinLevel; 1115 }; 1116 SNCA.runDFS(MinNode->getBlock(), 0, DescendBelow, 0); 1117 1118 LLVM_DEBUG(dbgs() << "Previous IDom(MinNode) = " 1119 << BlockNamePrinter(PrevIDom) << "\nRunning Semi-NCA\n"); 1120 1121 // Rebuild the remaining part of affected subtree. 1122 SNCA.runSemiNCA(); 1123 SNCA.reattachExistingSubtree(DT, PrevIDom); 1124 } 1125 1126 // Removes leaf tree nodes from the dominator tree. 1127 static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) { 1128 assert(TN); 1129 assert(TN->getNumChildren() == 0 && "Not a tree leaf"); 1130 1131 const TreeNodePtr IDom = TN->getIDom(); 1132 assert(IDom); 1133 1134 auto ChIt = llvm::find(IDom->Children, TN); 1135 assert(ChIt != IDom->Children.end()); 1136 std::swap(*ChIt, IDom->Children.back()); 1137 IDom->Children.pop_back(); 1138 1139 DT.DomTreeNodes.erase(TN->getBlock()); 1140 } 1141 1142 //~~ 1143 //===--------------------- DomTree Batch Updater --------------------------=== 1144 //~~ 1145 1146 static void ApplyUpdates(DomTreeT &DT, GraphDiffT &PreViewCFG, 1147 GraphDiffT *PostViewCFG) { 1148 // Note: the PostViewCFG is only used when computing from scratch. It's data 1149 // should already included in the PreViewCFG for incremental updates. 1150 const size_t NumUpdates = PreViewCFG.getNumLegalizedUpdates(); 1151 if (NumUpdates == 0) 1152 return; 1153 1154 // Take the fast path for a single update and avoid running the batch update 1155 // machinery. 1156 if (NumUpdates == 1) { 1157 UpdateT Update = PreViewCFG.popUpdateForIncrementalUpdates(); 1158 if (!PostViewCFG) { 1159 if (Update.getKind() == UpdateKind::Insert) 1160 InsertEdge(DT, /*BUI=*/nullptr, Update.getFrom(), Update.getTo()); 1161 else 1162 DeleteEdge(DT, /*BUI=*/nullptr, Update.getFrom(), Update.getTo()); 1163 } else { 1164 BatchUpdateInfo BUI(*PostViewCFG, PostViewCFG); 1165 if (Update.getKind() == UpdateKind::Insert) 1166 InsertEdge(DT, &BUI, Update.getFrom(), Update.getTo()); 1167 else 1168 DeleteEdge(DT, &BUI, Update.getFrom(), Update.getTo()); 1169 } 1170 return; 1171 } 1172 1173 BatchUpdateInfo BUI(PreViewCFG, PostViewCFG); 1174 // Recalculate the DominatorTree when the number of updates 1175 // exceeds a threshold, which usually makes direct updating slower than 1176 // recalculation. We select this threshold proportional to the 1177 // size of the DominatorTree. The constant is selected 1178 // by choosing the one with an acceptable performance on some real-world 1179 // inputs. 1180 1181 // Make unittests of the incremental algorithm work 1182 if (DT.DomTreeNodes.size() <= 100) { 1183 if (BUI.NumLegalized > DT.DomTreeNodes.size()) 1184 CalculateFromScratch(DT, &BUI); 1185 } else if (BUI.NumLegalized > DT.DomTreeNodes.size() / 40) 1186 CalculateFromScratch(DT, &BUI); 1187 1188 // If the DominatorTree was recalculated at some point, stop the batch 1189 // updates. Full recalculations ignore batch updates and look at the actual 1190 // CFG. 1191 for (size_t i = 0; i < BUI.NumLegalized && !BUI.IsRecalculated; ++i) 1192 ApplyNextUpdate(DT, BUI); 1193 } 1194 1195 static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) { 1196 // Popping the next update, will move the PreViewCFG to the next snapshot. 1197 UpdateT CurrentUpdate = BUI.PreViewCFG.popUpdateForIncrementalUpdates(); 1198#if 0 1199 // FIXME: The LLVM_DEBUG macro only plays well with a modular 1200 // build of LLVM when the header is marked as textual, but doing 1201 // so causes redefinition errors. 1202 LLVM_DEBUG(dbgs() << "Applying update: "); 1203 LLVM_DEBUG(CurrentUpdate.dump(); dbgs() << "\n"); 1204#endif 1205 1206 if (CurrentUpdate.getKind() == UpdateKind::Insert) 1207 InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo()); 1208 else 1209 DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo()); 1210 } 1211 1212 //~~ 1213 //===--------------- DomTree correctness verification ---------------------=== 1214 //~~ 1215 1216 // Check if the tree has correct roots. A DominatorTree always has a single 1217 // root which is the function's entry node. A PostDominatorTree can have 1218 // multiple roots - one for each node with no successors and for infinite 1219 // loops. 1220 // Running time: O(N). 1221 bool verifyRoots(const DomTreeT &DT) { 1222 if (!DT.Parent && !DT.Roots.empty()) { 1223 errs() << "Tree has no parent but has roots!\n"; 1224 errs().flush(); 1225 return false; 1226 } 1227 1228 if (!IsPostDom) { 1229 if (DT.Roots.empty()) { 1230 errs() << "Tree doesn't have a root!\n"; 1231 errs().flush(); 1232 return false; 1233 } 1234 1235 if (DT.getRoot() != GetEntryNode(DT)) { 1236 errs() << "Tree's root is not its parent's entry node!\n"; 1237 errs().flush(); 1238 return false; 1239 } 1240 } 1241 1242 RootsT ComputedRoots = FindRoots(DT, nullptr); 1243 if (!isPermutation(DT.Roots, ComputedRoots)) { 1244 errs() << "Tree has different roots than freshly computed ones!\n"; 1245 errs() << "\tPDT roots: "; 1246 for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", "; 1247 errs() << "\n\tComputed roots: "; 1248 for (const NodePtr N : ComputedRoots) 1249 errs() << BlockNamePrinter(N) << ", "; 1250 errs() << "\n"; 1251 errs().flush(); 1252 return false; 1253 } 1254 1255 return true; 1256 } 1257 1258 // Checks if the tree contains all reachable nodes in the input graph. 1259 // Running time: O(N). 1260 bool verifyReachability(const DomTreeT &DT) { 1261 clear(); 1262 doFullDFSWalk(DT, AlwaysDescend); 1263 1264 for (auto &NodeToTN : DT.DomTreeNodes) { 1265 const TreeNodePtr TN = NodeToTN.second.get(); 1266 const NodePtr BB = TN->getBlock(); 1267 1268 // Virtual root has a corresponding virtual CFG node. 1269 if (DT.isVirtualRoot(TN)) continue; 1270 1271 if (NodeToInfo.count(BB) == 0) { 1272 errs() << "DomTree node " << BlockNamePrinter(BB) 1273 << " not found by DFS walk!\n"; 1274 errs().flush(); 1275 1276 return false; 1277 } 1278 } 1279 1280 for (const NodePtr N : NumToNode) { 1281 if (N && !DT.getNode(N)) { 1282 errs() << "CFG node " << BlockNamePrinter(N) 1283 << " not found in the DomTree!\n"; 1284 errs().flush(); 1285 1286 return false; 1287 } 1288 } 1289 1290 return true; 1291 } 1292 1293 // Check if for every parent with a level L in the tree all of its children 1294 // have level L + 1. 1295 // Running time: O(N). 1296 static bool VerifyLevels(const DomTreeT &DT) { 1297 for (auto &NodeToTN : DT.DomTreeNodes) { 1298 const TreeNodePtr TN = NodeToTN.second.get(); 1299 const NodePtr BB = TN->getBlock(); 1300 if (!BB) continue; 1301 1302 const TreeNodePtr IDom = TN->getIDom(); 1303 if (!IDom && TN->getLevel() != 0) { 1304 errs() << "Node without an IDom " << BlockNamePrinter(BB) 1305 << " has a nonzero level " << TN->getLevel() << "!\n"; 1306 errs().flush(); 1307 1308 return false; 1309 } 1310 1311 if (IDom && TN->getLevel() != IDom->getLevel() + 1) { 1312 errs() << "Node " << BlockNamePrinter(BB) << " has level " 1313 << TN->getLevel() << " while its IDom " 1314 << BlockNamePrinter(IDom->getBlock()) << " has level " 1315 << IDom->getLevel() << "!\n"; 1316 errs().flush(); 1317 1318 return false; 1319 } 1320 } 1321 1322 return true; 1323 } 1324 1325 // Check if the computed DFS numbers are correct. Note that DFS info may not 1326 // be valid, and when that is the case, we don't verify the numbers. 1327 // Running time: O(N log(N)). 1328 static bool VerifyDFSNumbers(const DomTreeT &DT) { 1329 if (!DT.DFSInfoValid || !DT.Parent) 1330 return true; 1331 1332 const NodePtr RootBB = IsPostDom ? nullptr : *DT.root_begin(); 1333 const TreeNodePtr Root = DT.getNode(RootBB); 1334 1335 auto PrintNodeAndDFSNums = [](const TreeNodePtr TN) { 1336 errs() << BlockNamePrinter(TN) << " {" << TN->getDFSNumIn() << ", " 1337 << TN->getDFSNumOut() << '}'; 1338 }; 1339 1340 // Verify the root's DFS In number. Although DFS numbering would also work 1341 // if we started from some other value, we assume 0-based numbering. 1342 if (Root->getDFSNumIn() != 0) { 1343 errs() << "DFSIn number for the tree root is not:\n\t"; 1344 PrintNodeAndDFSNums(Root); 1345 errs() << '\n'; 1346 errs().flush(); 1347 return false; 1348 } 1349 1350 // For each tree node verify if children's DFS numbers cover their parent's 1351 // DFS numbers with no gaps. 1352 for (const auto &NodeToTN : DT.DomTreeNodes) { 1353 const TreeNodePtr Node = NodeToTN.second.get(); 1354 1355 // Handle tree leaves. 1356 if (Node->isLeaf()) { 1357 if (Node->getDFSNumIn() + 1 != Node->getDFSNumOut()) { 1358 errs() << "Tree leaf should have DFSOut = DFSIn + 1:\n\t"; 1359 PrintNodeAndDFSNums(Node); 1360 errs() << '\n'; 1361 errs().flush(); 1362 return false; 1363 } 1364 1365 continue; 1366 } 1367 1368 // Make a copy and sort it such that it is possible to check if there are 1369 // no gaps between DFS numbers of adjacent children. 1370 SmallVector<TreeNodePtr, 8> Children(Node->begin(), Node->end()); 1371 llvm::sort(Children, [](const TreeNodePtr Ch1, const TreeNodePtr Ch2) { 1372 return Ch1->getDFSNumIn() < Ch2->getDFSNumIn(); 1373 }); 1374 1375 auto PrintChildrenError = [Node, &Children, PrintNodeAndDFSNums]( 1376 const TreeNodePtr FirstCh, const TreeNodePtr SecondCh) { 1377 assert(FirstCh); 1378 1379 errs() << "Incorrect DFS numbers for:\n\tParent "; 1380 PrintNodeAndDFSNums(Node); 1381 1382 errs() << "\n\tChild "; 1383 PrintNodeAndDFSNums(FirstCh); 1384 1385 if (SecondCh) { 1386 errs() << "\n\tSecond child "; 1387 PrintNodeAndDFSNums(SecondCh); 1388 } 1389 1390 errs() << "\nAll children: "; 1391 for (const TreeNodePtr Ch : Children) { 1392 PrintNodeAndDFSNums(Ch); 1393 errs() << ", "; 1394 } 1395 1396 errs() << '\n'; 1397 errs().flush(); 1398 }; 1399 1400 if (Children.front()->getDFSNumIn() != Node->getDFSNumIn() + 1) { 1401 PrintChildrenError(Children.front(), nullptr); 1402 return false; 1403 } 1404 1405 if (Children.back()->getDFSNumOut() + 1 != Node->getDFSNumOut()) { 1406 PrintChildrenError(Children.back(), nullptr); 1407 return false; 1408 } 1409 1410 for (size_t i = 0, e = Children.size() - 1; i != e; ++i) { 1411 if (Children[i]->getDFSNumOut() + 1 != Children[i + 1]->getDFSNumIn()) { 1412 PrintChildrenError(Children[i], Children[i + 1]); 1413 return false; 1414 } 1415 } 1416 } 1417 1418 return true; 1419 } 1420 1421 // The below routines verify the correctness of the dominator tree relative to 1422 // the CFG it's coming from. A tree is a dominator tree iff it has two 1423 // properties, called the parent property and the sibling property. Tarjan 1424 // and Lengauer prove (but don't explicitly name) the properties as part of 1425 // the proofs in their 1972 paper, but the proofs are mostly part of proving 1426 // things about semidominators and idoms, and some of them are simply asserted 1427 // based on even earlier papers (see, e.g., lemma 2). Some papers refer to 1428 // these properties as "valid" and "co-valid". See, e.g., "Dominators, 1429 // directed bipolar orders, and independent spanning trees" by Loukas 1430 // Georgiadis and Robert E. Tarjan, as well as "Dominator Tree Verification 1431 // and Vertex-Disjoint Paths " by the same authors. 1432 1433 // A very simple and direct explanation of these properties can be found in 1434 // "An Experimental Study of Dynamic Dominators", found at 1435 // https://arxiv.org/abs/1604.02711 1436 1437 // The easiest way to think of the parent property is that it's a requirement 1438 // of being a dominator. Let's just take immediate dominators. For PARENT to 1439 // be an immediate dominator of CHILD, all paths in the CFG must go through 1440 // PARENT before they hit CHILD. This implies that if you were to cut PARENT 1441 // out of the CFG, there should be no paths to CHILD that are reachable. If 1442 // there are, then you now have a path from PARENT to CHILD that goes around 1443 // PARENT and still reaches CHILD, which by definition, means PARENT can't be 1444 // a dominator of CHILD (let alone an immediate one). 1445 1446 // The sibling property is similar. It says that for each pair of sibling 1447 // nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each 1448 // other. If sibling LEFT dominated sibling RIGHT, it means there are no 1449 // paths in the CFG from sibling LEFT to sibling RIGHT that do not go through 1450 // LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of 1451 // RIGHT, not a sibling. 1452 1453 // It is possible to verify the parent and sibling properties in linear time, 1454 // but the algorithms are complex. Instead, we do it in a straightforward 1455 // N^2 and N^3 way below, using direct path reachability. 1456 1457 // Checks if the tree has the parent property: if for all edges from V to W in 1458 // the input graph, such that V is reachable, the parent of W in the tree is 1459 // an ancestor of V in the tree. 1460 // Running time: O(N^2). 1461 // 1462 // This means that if a node gets disconnected from the graph, then all of 1463 // the nodes it dominated previously will now become unreachable. 1464 bool verifyParentProperty(const DomTreeT &DT) { 1465 for (auto &NodeToTN : DT.DomTreeNodes) { 1466 const TreeNodePtr TN = NodeToTN.second.get(); 1467 const NodePtr BB = TN->getBlock(); 1468 if (!BB || TN->isLeaf()) 1469 continue; 1470 1471 LLVM_DEBUG(dbgs() << "Verifying parent property of node " 1472 << BlockNamePrinter(TN) << "\n"); 1473 clear(); 1474 doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) { 1475 return From != BB && To != BB; 1476 }); 1477 1478 for (TreeNodePtr Child : TN->children()) 1479 if (NodeToInfo.count(Child->getBlock()) != 0) { 1480 errs() << "Child " << BlockNamePrinter(Child) 1481 << " reachable after its parent " << BlockNamePrinter(BB) 1482 << " is removed!\n"; 1483 errs().flush(); 1484 1485 return false; 1486 } 1487 } 1488 1489 return true; 1490 } 1491 1492 // Check if the tree has sibling property: if a node V does not dominate a 1493 // node W for all siblings V and W in the tree. 1494 // Running time: O(N^3). 1495 // 1496 // This means that if a node gets disconnected from the graph, then all of its 1497 // siblings will now still be reachable. 1498 bool verifySiblingProperty(const DomTreeT &DT) { 1499 for (auto &NodeToTN : DT.DomTreeNodes) { 1500 const TreeNodePtr TN = NodeToTN.second.get(); 1501 const NodePtr BB = TN->getBlock(); 1502 if (!BB || TN->isLeaf()) 1503 continue; 1504 1505 for (const TreeNodePtr N : TN->children()) { 1506 clear(); 1507 NodePtr BBN = N->getBlock(); 1508 doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) { 1509 return From != BBN && To != BBN; 1510 }); 1511 1512 for (const TreeNodePtr S : TN->children()) { 1513 if (S == N) continue; 1514 1515 if (NodeToInfo.count(S->getBlock()) == 0) { 1516 errs() << "Node " << BlockNamePrinter(S) 1517 << " not reachable when its sibling " << BlockNamePrinter(N) 1518 << " is removed!\n"; 1519 errs().flush(); 1520 1521 return false; 1522 } 1523 } 1524 } 1525 } 1526 1527 return true; 1528 } 1529 1530 // Check if the given tree is the same as a freshly computed one for the same 1531 // Parent. 1532 // Running time: O(N^2), but faster in practice (same as tree construction). 1533 // 1534 // Note that this does not check if that the tree construction algorithm is 1535 // correct and should be only used for fast (but possibly unsound) 1536 // verification. 1537 static bool IsSameAsFreshTree(const DomTreeT &DT) { 1538 DomTreeT FreshTree; 1539 FreshTree.recalculate(*DT.Parent); 1540 const bool Different = DT.compare(FreshTree); 1541 1542 if (Different) { 1543 errs() << (DT.isPostDominator() ? "Post" : "") 1544 << "DominatorTree is different than a freshly computed one!\n" 1545 << "\tCurrent:\n"; 1546 DT.print(errs()); 1547 errs() << "\n\tFreshly computed tree:\n"; 1548 FreshTree.print(errs()); 1549 errs().flush(); 1550 } 1551 1552 return !Different; 1553 } 1554}; 1555 1556template <class DomTreeT> 1557void Calculate(DomTreeT &DT) { 1558 SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, nullptr); 1559} 1560 1561template <typename DomTreeT> 1562void CalculateWithUpdates(DomTreeT &DT, 1563 ArrayRef<typename DomTreeT::UpdateType> Updates) { 1564 // FIXME: Updated to use the PreViewCFG and behave the same as until now. 1565 // This behavior is however incorrect; this actually needs the PostViewCFG. 1566 GraphDiff<typename DomTreeT::NodePtr, DomTreeT::IsPostDominator> PreViewCFG( 1567 Updates, /*ReverseApplyUpdates=*/true); 1568 typename SemiNCAInfo<DomTreeT>::BatchUpdateInfo BUI(PreViewCFG); 1569 SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, &BUI); 1570} 1571 1572template <class DomTreeT> 1573void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, 1574 typename DomTreeT::NodePtr To) { 1575 if (DT.isPostDominator()) std::swap(From, To); 1576 SemiNCAInfo<DomTreeT>::InsertEdge(DT, nullptr, From, To); 1577} 1578 1579template <class DomTreeT> 1580void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, 1581 typename DomTreeT::NodePtr To) { 1582 if (DT.isPostDominator()) std::swap(From, To); 1583 SemiNCAInfo<DomTreeT>::DeleteEdge(DT, nullptr, From, To); 1584} 1585 1586template <class DomTreeT> 1587void ApplyUpdates(DomTreeT &DT, 1588 GraphDiff<typename DomTreeT::NodePtr, 1589 DomTreeT::IsPostDominator> &PreViewCFG, 1590 GraphDiff<typename DomTreeT::NodePtr, 1591 DomTreeT::IsPostDominator> *PostViewCFG) { 1592 SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, PreViewCFG, PostViewCFG); 1593} 1594 1595template <class DomTreeT> 1596bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) { 1597 SemiNCAInfo<DomTreeT> SNCA(nullptr); 1598 1599 // Simplist check is to compare against a new tree. This will also 1600 // usefully print the old and new trees, if they are different. 1601 if (!SNCA.IsSameAsFreshTree(DT)) 1602 return false; 1603 1604 // Common checks to verify the properties of the tree. O(N log N) at worst. 1605 if (!SNCA.verifyRoots(DT) || !SNCA.verifyReachability(DT) || 1606 !SNCA.VerifyLevels(DT) || !SNCA.VerifyDFSNumbers(DT)) 1607 return false; 1608 1609 // Extra checks depending on VerificationLevel. Up to O(N^3). 1610 if (VL == DomTreeT::VerificationLevel::Basic || 1611 VL == DomTreeT::VerificationLevel::Full) 1612 if (!SNCA.verifyParentProperty(DT)) 1613 return false; 1614 if (VL == DomTreeT::VerificationLevel::Full) 1615 if (!SNCA.verifySiblingProperty(DT)) 1616 return false; 1617 1618 return true; 1619} 1620 1621} // namespace DomTreeBuilder 1622} // namespace llvm 1623 1624#undef DEBUG_TYPE 1625 1626#endif 1627