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