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