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