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