GenericDomTreeConstruction.h revision 328381
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 47namespace llvm { 48namespace DomTreeBuilder { 49 50template <typename DomTreeT> 51struct 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, SmallDenseSet<NodePtrAndKind, 4>> FutureSuccessors; 86 DenseMap<NodePtr, SmallDenseSet<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 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 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 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 DEBUG(dbgs() << "Found a new trivial root: " << BlockNamePrinter(N) 408 << "\n"); 409 DEBUG(dbgs() << "Last visited node: " 410 << BlockNamePrinter(SNCA.NumToNode[Num]) << "\n"); 411 } 412 } 413 414 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 DEBUG(dbgs() << "\t\t\tVisiting node " << BlockNamePrinter(I) 435 << "\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 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 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 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 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 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 DEBUG(dbgs() << "\t\t\t\tfound node " 469 << BlockNamePrinter(SNCA.NumToNode[i]) << "\n"); 470 } 471 } 472 } 473 474 DEBUG(dbgs() << "Total: " << Total << ", Num: " << Num << "\n"); 475 DEBUG(dbgs() << "Discovered CFG nodes:\n"); 476 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 DEBUG(dbgs() << "Found roots: "); 485 DEBUG(for (auto *Root : Roots) dbgs() << BlockNamePrinter(Root) << " "); 486 DEBUG(dbgs() << "\n"); 487 488 return Roots; 489 } 490 491 // This function only makes sense for postdominators. 492 // We define roots to be some set of CFG nodes where (reverse) DFS walks have 493 // to start in order to visit all the CFG nodes (including the 494 // reverse-unreachable ones). 495 // When the search for non-trivial roots is done it may happen that some of 496 // the non-trivial roots are reverse-reachable from other non-trivial roots, 497 // which makes them redundant. This function removes them from the set of 498 // input roots. 499 static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI, 500 RootsT &Roots) { 501 assert(IsPostDom && "This function is for postdominators only"); 502 DEBUG(dbgs() << "Removing redundant roots\n"); 503 504 SemiNCAInfo SNCA(BUI); 505 506 for (unsigned i = 0; i < Roots.size(); ++i) { 507 auto &Root = Roots[i]; 508 // Trivial roots are always non-redundant. 509 if (!HasForwardSuccessors(Root, BUI)) continue; 510 DEBUG(dbgs() << "\tChecking if " << BlockNamePrinter(Root) 511 << " remains a root\n"); 512 SNCA.clear(); 513 // Do a forward walk looking for the other roots. 514 const unsigned Num = SNCA.runDFS<true>(Root, 0, AlwaysDescend, 0); 515 // Skip the start node and begin from the second one (note that DFS uses 516 // 1-based indexing). 517 for (unsigned x = 2; x <= Num; ++x) { 518 const NodePtr N = SNCA.NumToNode[x]; 519 // If we wound another root in a (forward) DFS walk, remove the current 520 // root from the set of roots, as it is reverse-reachable from the other 521 // one. 522 if (llvm::find(Roots, N) != Roots.end()) { 523 DEBUG(dbgs() << "\tForward DFS walk found another root " 524 << BlockNamePrinter(N) << "\n\tRemoving root " 525 << BlockNamePrinter(Root) << "\n"); 526 std::swap(Root, Roots.back()); 527 Roots.pop_back(); 528 529 // Root at the back takes the current root's place. 530 // Start the next loop iteration with the same index. 531 --i; 532 break; 533 } 534 } 535 } 536 } 537 538 template <typename DescendCondition> 539 void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) { 540 if (!IsPostDom) { 541 assert(DT.Roots.size() == 1 && "Dominators should have a singe root"); 542 runDFS(DT.Roots[0], 0, DC, 0); 543 return; 544 } 545 546 addVirtualRoot(); 547 unsigned Num = 1; 548 for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0); 549 } 550 551 static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) { 552 auto *Parent = DT.Parent; 553 DT.reset(); 554 DT.Parent = Parent; 555 SemiNCAInfo SNCA(nullptr); // Since we are rebuilding the whole tree, 556 // there's no point doing it incrementally. 557 558 // Step #0: Number blocks in depth-first order and initialize variables used 559 // in later stages of the algorithm. 560 DT.Roots = FindRoots(DT, nullptr); 561 SNCA.doFullDFSWalk(DT, AlwaysDescend); 562 563 SNCA.runSemiNCA(DT); 564 if (BUI) { 565 BUI->IsRecalculated = true; 566 DEBUG(dbgs() << "DomTree recalculated, skipping future batch updates\n"); 567 } 568 569 if (DT.Roots.empty()) return; 570 571 // Add a node for the root. If the tree is a PostDominatorTree it will be 572 // the virtual exit (denoted by (BasicBlock *) nullptr) which postdominates 573 // all real exits (including multiple exit blocks, infinite loops). 574 NodePtr Root = IsPostDom ? nullptr : DT.Roots[0]; 575 576 DT.RootNode = (DT.DomTreeNodes[Root] = 577 llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr)) 578 .get(); 579 SNCA.attachNewSubtree(DT, DT.RootNode); 580 } 581 582 void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) { 583 // Attach the first unreachable block to AttachTo. 584 NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock(); 585 // Loop over all of the discovered blocks in the function... 586 for (size_t i = 1, e = NumToNode.size(); i != e; ++i) { 587 NodePtr W = NumToNode[i]; 588 DEBUG(dbgs() << "\tdiscovered a new reachable node " 589 << BlockNamePrinter(W) << "\n"); 590 591 // Don't replace this with 'count', the insertion side effect is important 592 if (DT.DomTreeNodes[W]) continue; // Haven't calculated this node yet? 593 594 NodePtr ImmDom = getIDom(W); 595 596 // Get or calculate the node for the immediate dominator. 597 TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT); 598 599 // Add a new tree node for this BasicBlock, and link it as a child of 600 // IDomNode. 601 DT.DomTreeNodes[W] = IDomNode->addChild( 602 llvm::make_unique<DomTreeNodeBase<NodeT>>(W, IDomNode)); 603 } 604 } 605 606 void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) { 607 NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock(); 608 for (size_t i = 1, e = NumToNode.size(); i != e; ++i) { 609 const NodePtr N = NumToNode[i]; 610 const TreeNodePtr TN = DT.getNode(N); 611 assert(TN); 612 const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom); 613 TN->setIDom(NewIDom); 614 } 615 } 616 617 // Helper struct used during edge insertions. 618 struct InsertionInfo { 619 using BucketElementTy = std::pair<unsigned, TreeNodePtr>; 620 struct DecreasingLevel { 621 bool operator()(const BucketElementTy &First, 622 const BucketElementTy &Second) const { 623 return First.first > Second.first; 624 } 625 }; 626 627 std::priority_queue<BucketElementTy, SmallVector<BucketElementTy, 8>, 628 DecreasingLevel> 629 Bucket; // Queue of tree nodes sorted by level in descending order. 630 SmallDenseSet<TreeNodePtr, 8> Affected; 631 SmallDenseMap<TreeNodePtr, unsigned, 8> Visited; 632 SmallVector<TreeNodePtr, 8> AffectedQueue; 633 SmallVector<TreeNodePtr, 8> VisitedNotAffectedQueue; 634 }; 635 636 static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI, 637 const NodePtr From, const NodePtr To) { 638 assert((From || IsPostDom) && 639 "From has to be a valid CFG node or a virtual root"); 640 assert(To && "Cannot be a nullptr"); 641 DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> " 642 << BlockNamePrinter(To) << "\n"); 643 TreeNodePtr FromTN = DT.getNode(From); 644 645 if (!FromTN) { 646 // Ignore edges from unreachable nodes for (forward) dominators. 647 if (!IsPostDom) return; 648 649 // The unreachable node becomes a new root -- a tree node for it. 650 TreeNodePtr VirtualRoot = DT.getNode(nullptr); 651 FromTN = 652 (DT.DomTreeNodes[From] = VirtualRoot->addChild( 653 llvm::make_unique<DomTreeNodeBase<NodeT>>(From, VirtualRoot))) 654 .get(); 655 DT.Roots.push_back(From); 656 } 657 658 DT.DFSInfoValid = false; 659 660 const TreeNodePtr ToTN = DT.getNode(To); 661 if (!ToTN) 662 InsertUnreachable(DT, BUI, FromTN, To); 663 else 664 InsertReachable(DT, BUI, FromTN, ToTN); 665 } 666 667 // Determines if some existing root becomes reverse-reachable after the 668 // insertion. Rebuilds the whole tree if that situation happens. 669 static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, 670 const TreeNodePtr From, 671 const TreeNodePtr To) { 672 assert(IsPostDom && "This function is only for postdominators"); 673 // Destination node is not attached to the virtual root, so it cannot be a 674 // root. 675 if (!DT.isVirtualRoot(To->getIDom())) return false; 676 677 auto RIt = llvm::find(DT.Roots, To->getBlock()); 678 if (RIt == DT.Roots.end()) 679 return false; // To is not a root, nothing to update. 680 681 DEBUG(dbgs() << "\t\tAfter the insertion, " << BlockNamePrinter(To) 682 << " is no longer a root\n\t\tRebuilding the tree!!!\n"); 683 684 CalculateFromScratch(DT, BUI); 685 return true; 686 } 687 688 // Updates the set of roots after insertion or deletion. This ensures that 689 // roots are the same when after a series of updates and when the tree would 690 // be built from scratch. 691 static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI) { 692 assert(IsPostDom && "This function is only for postdominators"); 693 694 // The tree has only trivial roots -- nothing to update. 695 if (std::none_of(DT.Roots.begin(), DT.Roots.end(), [BUI](const NodePtr N) { 696 return HasForwardSuccessors(N, BUI); 697 })) 698 return; 699 700 // Recalculate the set of roots. 701 DT.Roots = FindRoots(DT, BUI); 702 for (const NodePtr R : DT.Roots) { 703 const TreeNodePtr TN = DT.getNode(R); 704 // A CFG node was selected as a tree root, but the corresponding tree node 705 // is not connected to the virtual root. This is because the incremental 706 // algorithm does not really know or use the set of roots and can make a 707 // different (implicit) decision about which nodes within an infinite loop 708 // becomes a root. 709 if (TN && !DT.isVirtualRoot(TN->getIDom())) { 710 DEBUG(dbgs() << "Root " << BlockNamePrinter(R) 711 << " is not virtual root's child\n" 712 << "The entire tree needs to be rebuilt\n"); 713 // It should be possible to rotate the subtree instead of recalculating 714 // the whole tree, but this situation happens extremely rarely in 715 // practice. 716 CalculateFromScratch(DT, BUI); 717 return; 718 } 719 } 720 } 721 722 // Handles insertion to a node already in the dominator tree. 723 static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI, 724 const TreeNodePtr From, const TreeNodePtr To) { 725 DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock()) 726 << " -> " << BlockNamePrinter(To->getBlock()) << "\n"); 727 if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return; 728 // DT.findNCD expects both pointers to be valid. When From is a virtual 729 // root, then its CFG block pointer is a nullptr, so we have to 'compute' 730 // the NCD manually. 731 const NodePtr NCDBlock = 732 (From->getBlock() && To->getBlock()) 733 ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock()) 734 : nullptr; 735 assert(NCDBlock || DT.isPostDominator()); 736 const TreeNodePtr NCD = DT.getNode(NCDBlock); 737 assert(NCD); 738 739 DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n"); 740 const TreeNodePtr ToIDom = To->getIDom(); 741 742 // Nothing affected -- NCA property holds. 743 // (Based on the lemma 2.5 from the second paper.) 744 if (NCD == To || NCD == ToIDom) return; 745 746 // Identify and collect affected nodes. 747 InsertionInfo II; 748 DEBUG(dbgs() << "Marking " << BlockNamePrinter(To) << " as affected\n"); 749 II.Affected.insert(To); 750 const unsigned ToLevel = To->getLevel(); 751 DEBUG(dbgs() << "Putting " << BlockNamePrinter(To) << " into a Bucket\n"); 752 II.Bucket.push({ToLevel, To}); 753 754 while (!II.Bucket.empty()) { 755 const TreeNodePtr CurrentNode = II.Bucket.top().second; 756 const unsigned CurrentLevel = CurrentNode->getLevel(); 757 II.Bucket.pop(); 758 DEBUG(dbgs() << "\tAdding to Visited and AffectedQueue: " 759 << BlockNamePrinter(CurrentNode) << "\n"); 760 761 II.Visited.insert({CurrentNode, CurrentLevel}); 762 II.AffectedQueue.push_back(CurrentNode); 763 764 // Discover and collect affected successors of the current node. 765 VisitInsertion(DT, BUI, CurrentNode, CurrentLevel, NCD, II); 766 } 767 768 // Finish by updating immediate dominators and levels. 769 UpdateInsertion(DT, BUI, NCD, II); 770 } 771 772 // Visits an affected node and collect its affected successors. 773 static void VisitInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, 774 const TreeNodePtr TN, const unsigned RootLevel, 775 const TreeNodePtr NCD, InsertionInfo &II) { 776 const unsigned NCDLevel = NCD->getLevel(); 777 DEBUG(dbgs() << "Visiting " << BlockNamePrinter(TN) << ", RootLevel " 778 << RootLevel << "\n"); 779 780 SmallVector<TreeNodePtr, 8> Stack = {TN}; 781 assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!"); 782 783 SmallPtrSet<TreeNodePtr, 8> Processed; 784 785 do { 786 TreeNodePtr Next = Stack.pop_back_val(); 787 DEBUG(dbgs() << " Next: " << BlockNamePrinter(Next) << "\n"); 788 789 for (const NodePtr Succ : 790 ChildrenGetter<IsPostDom>::Get(Next->getBlock(), BUI)) { 791 const TreeNodePtr SuccTN = DT.getNode(Succ); 792 assert(SuccTN && "Unreachable successor found at reachable insertion"); 793 const unsigned SuccLevel = SuccTN->getLevel(); 794 795 DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ) << ", level = " 796 << SuccLevel << "\n"); 797 798 // Do not process the same node multiple times. 799 if (Processed.count(Next) > 0) 800 continue; 801 802 // Succ dominated by subtree From -- not affected. 803 // (Based on the lemma 2.5 from the second paper.) 804 if (SuccLevel > RootLevel) { 805 DEBUG(dbgs() << "\t\tDominated by subtree From\n"); 806 if (II.Visited.count(SuccTN) != 0) { 807 DEBUG(dbgs() << "\t\t\talready visited at level " 808 << II.Visited[SuccTN] << "\n\t\t\tcurrent level " 809 << RootLevel << ")\n"); 810 811 // A node can be necessary to visit again if we see it again at 812 // a lower level than before. 813 if (II.Visited[SuccTN] >= RootLevel) 814 continue; 815 } 816 817 DEBUG(dbgs() << "\t\tMarking visited not affected " 818 << BlockNamePrinter(Succ) << "\n"); 819 II.Visited.insert({SuccTN, RootLevel}); 820 II.VisitedNotAffectedQueue.push_back(SuccTN); 821 Stack.push_back(SuccTN); 822 } else if ((SuccLevel > NCDLevel + 1) && 823 II.Affected.count(SuccTN) == 0) { 824 DEBUG(dbgs() << "\t\tMarking affected and adding " 825 << BlockNamePrinter(Succ) << " to a Bucket\n"); 826 II.Affected.insert(SuccTN); 827 II.Bucket.push({SuccLevel, SuccTN}); 828 } 829 } 830 831 Processed.insert(Next); 832 } while (!Stack.empty()); 833 } 834 835 // Updates immediate dominators and levels after insertion. 836 static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, 837 const TreeNodePtr NCD, InsertionInfo &II) { 838 DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n"); 839 840 for (const TreeNodePtr TN : II.AffectedQueue) { 841 DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN) 842 << ") = " << BlockNamePrinter(NCD) << "\n"); 843 TN->setIDom(NCD); 844 } 845 846 UpdateLevelsAfterInsertion(II); 847 if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI); 848 } 849 850 static void UpdateLevelsAfterInsertion(InsertionInfo &II) { 851 DEBUG(dbgs() << "Updating levels for visited but not affected nodes\n"); 852 853 for (const TreeNodePtr TN : II.VisitedNotAffectedQueue) { 854 DEBUG(dbgs() << "\tlevel(" << BlockNamePrinter(TN) << ") = (" 855 << BlockNamePrinter(TN->getIDom()) << ") " 856 << TN->getIDom()->getLevel() << " + 1\n"); 857 TN->UpdateLevel(); 858 } 859 } 860 861 // Handles insertion to previously unreachable nodes. 862 static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, 863 const TreeNodePtr From, const NodePtr To) { 864 DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From) 865 << " -> (unreachable) " << BlockNamePrinter(To) << "\n"); 866 867 // Collect discovered edges to already reachable nodes. 868 SmallVector<std::pair<NodePtr, TreeNodePtr>, 8> DiscoveredEdgesToReachable; 869 // Discover and connect nodes that became reachable with the insertion. 870 ComputeUnreachableDominators(DT, BUI, To, From, DiscoveredEdgesToReachable); 871 872 DEBUG(dbgs() << "Inserted " << BlockNamePrinter(From) 873 << " -> (prev unreachable) " << BlockNamePrinter(To) << "\n"); 874 875 // Used the discovered edges and inset discovered connecting (incoming) 876 // edges. 877 for (const auto &Edge : DiscoveredEdgesToReachable) { 878 DEBUG(dbgs() << "\tInserting discovered connecting edge " 879 << BlockNamePrinter(Edge.first) << " -> " 880 << BlockNamePrinter(Edge.second) << "\n"); 881 InsertReachable(DT, BUI, DT.getNode(Edge.first), Edge.second); 882 } 883 } 884 885 // Connects nodes that become reachable with an insertion. 886 static void ComputeUnreachableDominators( 887 DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root, 888 const TreeNodePtr Incoming, 889 SmallVectorImpl<std::pair<NodePtr, TreeNodePtr>> 890 &DiscoveredConnectingEdges) { 891 assert(!DT.getNode(Root) && "Root must not be reachable"); 892 893 // Visit only previously unreachable nodes. 894 auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From, 895 NodePtr To) { 896 const TreeNodePtr ToTN = DT.getNode(To); 897 if (!ToTN) return true; 898 899 DiscoveredConnectingEdges.push_back({From, ToTN}); 900 return false; 901 }; 902 903 SemiNCAInfo SNCA(BUI); 904 SNCA.runDFS(Root, 0, UnreachableDescender, 0); 905 SNCA.runSemiNCA(DT); 906 SNCA.attachNewSubtree(DT, Incoming); 907 908 DEBUG(dbgs() << "After adding unreachable nodes\n"); 909 } 910 911 static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI, 912 const NodePtr From, const NodePtr To) { 913 assert(From && To && "Cannot disconnect nullptrs"); 914 DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> " 915 << BlockNamePrinter(To) << "\n"); 916 917#ifndef NDEBUG 918 // Ensure that the edge was in fact deleted from the CFG before informing 919 // the DomTree about it. 920 // The check is O(N), so run it only in debug configuration. 921 auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) { 922 auto Successors = ChildrenGetter<IsPostDom>::Get(Of, BUI); 923 return llvm::find(Successors, SuccCandidate) != Successors.end(); 924 }; 925 (void)IsSuccessor; 926 assert(!IsSuccessor(To, From) && "Deleted edge still exists in the CFG!"); 927#endif 928 929 const TreeNodePtr FromTN = DT.getNode(From); 930 // Deletion in an unreachable subtree -- nothing to do. 931 if (!FromTN) return; 932 933 const TreeNodePtr ToTN = DT.getNode(To); 934 if (!ToTN) { 935 DEBUG(dbgs() << "\tTo (" << BlockNamePrinter(To) 936 << ") already unreachable -- there is no edge to delete\n"); 937 return; 938 } 939 940 const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To); 941 const TreeNodePtr NCD = DT.getNode(NCDBlock); 942 943 // If To dominates From -- nothing to do. 944 if (ToTN != NCD) { 945 DT.DFSInfoValid = false; 946 947 const TreeNodePtr ToIDom = ToTN->getIDom(); 948 DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom " 949 << BlockNamePrinter(ToIDom) << "\n"); 950 951 // To remains reachable after deletion. 952 // (Based on the caption under Figure 4. from the second paper.) 953 if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN)) 954 DeleteReachable(DT, BUI, FromTN, ToTN); 955 else 956 DeleteUnreachable(DT, BUI, ToTN); 957 } 958 959 if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI); 960 } 961 962 // Handles deletions that leave destination nodes reachable. 963 static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI, 964 const TreeNodePtr FromTN, 965 const TreeNodePtr ToTN) { 966 DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN) << " -> " 967 << BlockNamePrinter(ToTN) << "\n"); 968 DEBUG(dbgs() << "\tRebuilding subtree\n"); 969 970 // Find the top of the subtree that needs to be rebuilt. 971 // (Based on the lemma 2.6 from the second paper.) 972 const NodePtr ToIDom = 973 DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock()); 974 assert(ToIDom || DT.isPostDominator()); 975 const TreeNodePtr ToIDomTN = DT.getNode(ToIDom); 976 assert(ToIDomTN); 977 const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom(); 978 // Top of the subtree to rebuild is the root node. Rebuild the tree from 979 // scratch. 980 if (!PrevIDomSubTree) { 981 DEBUG(dbgs() << "The entire tree needs to be rebuilt\n"); 982 CalculateFromScratch(DT, BUI); 983 return; 984 } 985 986 // Only visit nodes in the subtree starting at To. 987 const unsigned Level = ToIDomTN->getLevel(); 988 auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) { 989 return DT.getNode(To)->getLevel() > Level; 990 }; 991 992 DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN) << "\n"); 993 994 SemiNCAInfo SNCA(BUI); 995 SNCA.runDFS(ToIDom, 0, DescendBelow, 0); 996 DEBUG(dbgs() << "\tRunning Semi-NCA\n"); 997 SNCA.runSemiNCA(DT, Level); 998 SNCA.reattachExistingSubtree(DT, PrevIDomSubTree); 999 } 1000 1001 // Checks if a node has proper support, as defined on the page 3 and later 1002 // explained on the page 7 of the second paper. 1003 static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI, 1004 const TreeNodePtr TN) { 1005 DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN) << "\n"); 1006 for (const NodePtr Pred : 1007 ChildrenGetter<!IsPostDom>::Get(TN->getBlock(), BUI)) { 1008 DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n"); 1009 if (!DT.getNode(Pred)) continue; 1010 1011 const NodePtr Support = 1012 DT.findNearestCommonDominator(TN->getBlock(), Pred); 1013 DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n"); 1014 if (Support != TN->getBlock()) { 1015 DEBUG(dbgs() << "\t" << BlockNamePrinter(TN) 1016 << " is reachable from support " 1017 << BlockNamePrinter(Support) << "\n"); 1018 return true; 1019 } 1020 } 1021 1022 return false; 1023 } 1024 1025 // Handle deletions that make destination node unreachable. 1026 // (Based on the lemma 2.7 from the second paper.) 1027 static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, 1028 const TreeNodePtr ToTN) { 1029 DEBUG(dbgs() << "Deleting unreachable subtree " << BlockNamePrinter(ToTN) 1030 << "\n"); 1031 assert(ToTN); 1032 assert(ToTN->getBlock()); 1033 1034 if (IsPostDom) { 1035 // Deletion makes a region reverse-unreachable and creates a new root. 1036 // Simulate that by inserting an edge from the virtual root to ToTN and 1037 // adding it as a new root. 1038 DEBUG(dbgs() << "\tDeletion made a region reverse-unreachable\n"); 1039 DEBUG(dbgs() << "\tAdding new root " << BlockNamePrinter(ToTN) << "\n"); 1040 DT.Roots.push_back(ToTN->getBlock()); 1041 InsertReachable(DT, BUI, DT.getNode(nullptr), ToTN); 1042 return; 1043 } 1044 1045 SmallVector<NodePtr, 16> AffectedQueue; 1046 const unsigned Level = ToTN->getLevel(); 1047 1048 // Traverse destination node's descendants with greater level in the tree 1049 // and collect visited nodes. 1050 auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) { 1051 const TreeNodePtr TN = DT.getNode(To); 1052 assert(TN); 1053 if (TN->getLevel() > Level) return true; 1054 if (llvm::find(AffectedQueue, To) == AffectedQueue.end()) 1055 AffectedQueue.push_back(To); 1056 1057 return false; 1058 }; 1059 1060 SemiNCAInfo SNCA(BUI); 1061 unsigned LastDFSNum = 1062 SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0); 1063 1064 TreeNodePtr MinNode = ToTN; 1065 1066 // Identify the top of the subtree to rebuild by finding the NCD of all 1067 // the affected nodes. 1068 for (const NodePtr N : AffectedQueue) { 1069 const TreeNodePtr TN = DT.getNode(N); 1070 const NodePtr NCDBlock = 1071 DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock()); 1072 assert(NCDBlock || DT.isPostDominator()); 1073 const TreeNodePtr NCD = DT.getNode(NCDBlock); 1074 assert(NCD); 1075 1076 DEBUG(dbgs() << "Processing affected node " << BlockNamePrinter(TN) 1077 << " with NCD = " << BlockNamePrinter(NCD) 1078 << ", MinNode =" << BlockNamePrinter(MinNode) << "\n"); 1079 if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD; 1080 } 1081 1082 // Root reached, rebuild the whole tree from scratch. 1083 if (!MinNode->getIDom()) { 1084 DEBUG(dbgs() << "The entire tree needs to be rebuilt\n"); 1085 CalculateFromScratch(DT, BUI); 1086 return; 1087 } 1088 1089 // Erase the unreachable subtree in reverse preorder to process all children 1090 // before deleting their parent. 1091 for (unsigned i = LastDFSNum; i > 0; --i) { 1092 const NodePtr N = SNCA.NumToNode[i]; 1093 const TreeNodePtr TN = DT.getNode(N); 1094 DEBUG(dbgs() << "Erasing node " << BlockNamePrinter(TN) << "\n"); 1095 1096 EraseNode(DT, TN); 1097 } 1098 1099 // The affected subtree start at the To node -- there's no extra work to do. 1100 if (MinNode == ToTN) return; 1101 1102 DEBUG(dbgs() << "DeleteUnreachable: running DFS with MinNode = " 1103 << BlockNamePrinter(MinNode) << "\n"); 1104 const unsigned MinLevel = MinNode->getLevel(); 1105 const TreeNodePtr PrevIDom = MinNode->getIDom(); 1106 assert(PrevIDom); 1107 SNCA.clear(); 1108 1109 // Identify nodes that remain in the affected subtree. 1110 auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) { 1111 const TreeNodePtr ToTN = DT.getNode(To); 1112 return ToTN && ToTN->getLevel() > MinLevel; 1113 }; 1114 SNCA.runDFS(MinNode->getBlock(), 0, DescendBelow, 0); 1115 1116 DEBUG(dbgs() << "Previous IDom(MinNode) = " << BlockNamePrinter(PrevIDom) 1117 << "\nRunning Semi-NCA\n"); 1118 1119 // Rebuild the remaining part of affected subtree. 1120 SNCA.runSemiNCA(DT, MinLevel); 1121 SNCA.reattachExistingSubtree(DT, PrevIDom); 1122 } 1123 1124 // Removes leaf tree nodes from the dominator tree. 1125 static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) { 1126 assert(TN); 1127 assert(TN->getNumChildren() == 0 && "Not a tree leaf"); 1128 1129 const TreeNodePtr IDom = TN->getIDom(); 1130 assert(IDom); 1131 1132 auto ChIt = llvm::find(IDom->Children, TN); 1133 assert(ChIt != IDom->Children.end()); 1134 std::swap(*ChIt, IDom->Children.back()); 1135 IDom->Children.pop_back(); 1136 1137 DT.DomTreeNodes.erase(TN->getBlock()); 1138 } 1139 1140 //~~ 1141 //===--------------------- DomTree Batch Updater --------------------------=== 1142 //~~ 1143 1144 static void ApplyUpdates(DomTreeT &DT, ArrayRef<UpdateT> Updates) { 1145 const size_t NumUpdates = Updates.size(); 1146 if (NumUpdates == 0) 1147 return; 1148 1149 // Take the fast path for a single update and avoid running the batch update 1150 // machinery. 1151 if (NumUpdates == 1) { 1152 const auto &Update = Updates.front(); 1153 if (Update.getKind() == UpdateKind::Insert) 1154 DT.insertEdge(Update.getFrom(), Update.getTo()); 1155 else 1156 DT.deleteEdge(Update.getFrom(), Update.getTo()); 1157 1158 return; 1159 } 1160 1161 BatchUpdateInfo BUI; 1162 LegalizeUpdates(Updates, BUI.Updates); 1163 1164 const size_t NumLegalized = BUI.Updates.size(); 1165 BUI.FutureSuccessors.reserve(NumLegalized); 1166 BUI.FuturePredecessors.reserve(NumLegalized); 1167 1168 // Use the legalized future updates to initialize future successors and 1169 // predecessors. Note that these sets will only decrease size over time, as 1170 // the next CFG snapshots slowly approach the actual (current) CFG. 1171 for (UpdateT &U : BUI.Updates) { 1172 BUI.FutureSuccessors[U.getFrom()].insert({U.getTo(), U.getKind()}); 1173 BUI.FuturePredecessors[U.getTo()].insert({U.getFrom(), U.getKind()}); 1174 } 1175 1176 DEBUG(dbgs() << "About to apply " << NumLegalized << " updates\n"); 1177 DEBUG(if (NumLegalized < 32) for (const auto &U 1178 : reverse(BUI.Updates)) dbgs() 1179 << '\t' << U << "\n"); 1180 DEBUG(dbgs() << "\n"); 1181 1182 // If the DominatorTree was recalculated at some point, stop the batch 1183 // updates. Full recalculations ignore batch updates and look at the actual 1184 // CFG. 1185 for (size_t i = 0; i < NumLegalized && !BUI.IsRecalculated; ++i) 1186 ApplyNextUpdate(DT, BUI); 1187 } 1188 1189 // This function serves double purpose: 1190 // a) It removes redundant updates, which makes it easier to reverse-apply 1191 // them when traversing CFG. 1192 // b) It optimizes away updates that cancel each other out, as the end result 1193 // is the same. 1194 // 1195 // It relies on the property of the incremental updates that says that the 1196 // order of updates doesn't matter. This allows us to reorder them and end up 1197 // with the exact same DomTree every time. 1198 // 1199 // Following the same logic, the function doesn't care about the order of 1200 // input updates, so it's OK to pass it an unordered sequence of updates, that 1201 // doesn't make sense when applied sequentially, eg. performing double 1202 // insertions or deletions and then doing an opposite update. 1203 // 1204 // In the future, it should be possible to schedule updates in way that 1205 // minimizes the amount of work needed done during incremental updates. 1206 static void LegalizeUpdates(ArrayRef<UpdateT> AllUpdates, 1207 SmallVectorImpl<UpdateT> &Result) { 1208 DEBUG(dbgs() << "Legalizing " << AllUpdates.size() << " updates\n"); 1209 // Count the total number of inserions of each edge. 1210 // Each insertion adds 1 and deletion subtracts 1. The end number should be 1211 // one of {-1 (deletion), 0 (NOP), +1 (insertion)}. Otherwise, the sequence 1212 // of updates contains multiple updates of the same kind and we assert for 1213 // that case. 1214 SmallDenseMap<std::pair<NodePtr, NodePtr>, int, 4> Operations; 1215 Operations.reserve(AllUpdates.size()); 1216 1217 for (const auto &U : AllUpdates) { 1218 NodePtr From = U.getFrom(); 1219 NodePtr To = U.getTo(); 1220 if (IsPostDom) std::swap(From, To); // Reverse edge for postdominators. 1221 1222 Operations[{From, To}] += (U.getKind() == UpdateKind::Insert ? 1 : -1); 1223 } 1224 1225 Result.clear(); 1226 Result.reserve(Operations.size()); 1227 for (auto &Op : Operations) { 1228 const int NumInsertions = Op.second; 1229 assert(std::abs(NumInsertions) <= 1 && "Unbalanced operations!"); 1230 if (NumInsertions == 0) continue; 1231 const UpdateKind UK = 1232 NumInsertions > 0 ? UpdateKind::Insert : UpdateKind::Delete; 1233 Result.push_back({UK, Op.first.first, Op.first.second}); 1234 } 1235 1236 // Make the order consistent by not relying on pointer values within the 1237 // set. Reuse the old Operations map. 1238 // In the future, we should sort by something else to minimize the amount 1239 // of work needed to perform the series of updates. 1240 for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) { 1241 const auto &U = AllUpdates[i]; 1242 if (!IsPostDom) 1243 Operations[{U.getFrom(), U.getTo()}] = int(i); 1244 else 1245 Operations[{U.getTo(), U.getFrom()}] = int(i); 1246 } 1247 1248 std::sort(Result.begin(), Result.end(), 1249 [&Operations](const UpdateT &A, const UpdateT &B) { 1250 return Operations[{A.getFrom(), A.getTo()}] > 1251 Operations[{B.getFrom(), B.getTo()}]; 1252 }); 1253 } 1254 1255 static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) { 1256 assert(!BUI.Updates.empty() && "No updates to apply!"); 1257 UpdateT CurrentUpdate = BUI.Updates.pop_back_val(); 1258 DEBUG(dbgs() << "Applying update: " << CurrentUpdate << "\n"); 1259 1260 // Move to the next snapshot of the CFG by removing the reverse-applied 1261 // current update. 1262 auto &FS = BUI.FutureSuccessors[CurrentUpdate.getFrom()]; 1263 FS.erase({CurrentUpdate.getTo(), CurrentUpdate.getKind()}); 1264 if (FS.empty()) BUI.FutureSuccessors.erase(CurrentUpdate.getFrom()); 1265 1266 auto &FP = BUI.FuturePredecessors[CurrentUpdate.getTo()]; 1267 FP.erase({CurrentUpdate.getFrom(), CurrentUpdate.getKind()}); 1268 if (FP.empty()) BUI.FuturePredecessors.erase(CurrentUpdate.getTo()); 1269 1270 if (CurrentUpdate.getKind() == UpdateKind::Insert) 1271 InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo()); 1272 else 1273 DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo()); 1274 } 1275 1276 //~~ 1277 //===--------------- DomTree correctness verification ---------------------=== 1278 //~~ 1279 1280 // Check if the tree has correct roots. A DominatorTree always has a single 1281 // root which is the function's entry node. A PostDominatorTree can have 1282 // multiple roots - one for each node with no successors and for infinite 1283 // loops. 1284 bool verifyRoots(const DomTreeT &DT) { 1285 if (!DT.Parent && !DT.Roots.empty()) { 1286 errs() << "Tree has no parent but has roots!\n"; 1287 errs().flush(); 1288 return false; 1289 } 1290 1291 if (!IsPostDom) { 1292 if (DT.Roots.empty()) { 1293 errs() << "Tree doesn't have a root!\n"; 1294 errs().flush(); 1295 return false; 1296 } 1297 1298 if (DT.getRoot() != GetEntryNode(DT)) { 1299 errs() << "Tree's root is not its parent's entry node!\n"; 1300 errs().flush(); 1301 return false; 1302 } 1303 } 1304 1305 RootsT ComputedRoots = FindRoots(DT, nullptr); 1306 if (DT.Roots.size() != ComputedRoots.size() || 1307 !std::is_permutation(DT.Roots.begin(), DT.Roots.end(), 1308 ComputedRoots.begin())) { 1309 errs() << "Tree has different roots than freshly computed ones!\n"; 1310 errs() << "\tPDT roots: "; 1311 for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", "; 1312 errs() << "\n\tComputed roots: "; 1313 for (const NodePtr N : ComputedRoots) 1314 errs() << BlockNamePrinter(N) << ", "; 1315 errs() << "\n"; 1316 errs().flush(); 1317 return false; 1318 } 1319 1320 return true; 1321 } 1322 1323 // Checks if the tree contains all reachable nodes in the input graph. 1324 bool verifyReachability(const DomTreeT &DT) { 1325 clear(); 1326 doFullDFSWalk(DT, AlwaysDescend); 1327 1328 for (auto &NodeToTN : DT.DomTreeNodes) { 1329 const TreeNodePtr TN = NodeToTN.second.get(); 1330 const NodePtr BB = TN->getBlock(); 1331 1332 // Virtual root has a corresponding virtual CFG node. 1333 if (DT.isVirtualRoot(TN)) continue; 1334 1335 if (NodeToInfo.count(BB) == 0) { 1336 errs() << "DomTree node " << BlockNamePrinter(BB) 1337 << " not found by DFS walk!\n"; 1338 errs().flush(); 1339 1340 return false; 1341 } 1342 } 1343 1344 for (const NodePtr N : NumToNode) { 1345 if (N && !DT.getNode(N)) { 1346 errs() << "CFG node " << BlockNamePrinter(N) 1347 << " not found in the DomTree!\n"; 1348 errs().flush(); 1349 1350 return false; 1351 } 1352 } 1353 1354 return true; 1355 } 1356 1357 // Check if for every parent with a level L in the tree all of its children 1358 // have level L + 1. 1359 static bool VerifyLevels(const DomTreeT &DT) { 1360 for (auto &NodeToTN : DT.DomTreeNodes) { 1361 const TreeNodePtr TN = NodeToTN.second.get(); 1362 const NodePtr BB = TN->getBlock(); 1363 if (!BB) continue; 1364 1365 const TreeNodePtr IDom = TN->getIDom(); 1366 if (!IDom && TN->getLevel() != 0) { 1367 errs() << "Node without an IDom " << BlockNamePrinter(BB) 1368 << " has a nonzero level " << TN->getLevel() << "!\n"; 1369 errs().flush(); 1370 1371 return false; 1372 } 1373 1374 if (IDom && TN->getLevel() != IDom->getLevel() + 1) { 1375 errs() << "Node " << BlockNamePrinter(BB) << " has level " 1376 << TN->getLevel() << " while its IDom " 1377 << BlockNamePrinter(IDom->getBlock()) << " has level " 1378 << IDom->getLevel() << "!\n"; 1379 errs().flush(); 1380 1381 return false; 1382 } 1383 } 1384 1385 return true; 1386 } 1387 1388 // Check if the computed DFS numbers are correct. Note that DFS info may not 1389 // be valid, and when that is the case, we don't verify the numbers. 1390 static bool VerifyDFSNumbers(const DomTreeT &DT) { 1391 if (!DT.DFSInfoValid || !DT.Parent) 1392 return true; 1393 1394 const NodePtr RootBB = IsPostDom ? nullptr : DT.getRoots()[0]; 1395 const TreeNodePtr Root = DT.getNode(RootBB); 1396 1397 auto PrintNodeAndDFSNums = [](const TreeNodePtr TN) { 1398 errs() << BlockNamePrinter(TN) << " {" << TN->getDFSNumIn() << ", " 1399 << TN->getDFSNumOut() << '}'; 1400 }; 1401 1402 // Verify the root's DFS In number. Although DFS numbering would also work 1403 // if we started from some other value, we assume 0-based numbering. 1404 if (Root->getDFSNumIn() != 0) { 1405 errs() << "DFSIn number for the tree root is not:\n\t"; 1406 PrintNodeAndDFSNums(Root); 1407 errs() << '\n'; 1408 errs().flush(); 1409 return false; 1410 } 1411 1412 // For each tree node verify if children's DFS numbers cover their parent's 1413 // DFS numbers with no gaps. 1414 for (const auto &NodeToTN : DT.DomTreeNodes) { 1415 const TreeNodePtr Node = NodeToTN.second.get(); 1416 1417 // Handle tree leaves. 1418 if (Node->getChildren().empty()) { 1419 if (Node->getDFSNumIn() + 1 != Node->getDFSNumOut()) { 1420 errs() << "Tree leaf should have DFSOut = DFSIn + 1:\n\t"; 1421 PrintNodeAndDFSNums(Node); 1422 errs() << '\n'; 1423 errs().flush(); 1424 return false; 1425 } 1426 1427 continue; 1428 } 1429 1430 // Make a copy and sort it such that it is possible to check if there are 1431 // no gaps between DFS numbers of adjacent children. 1432 SmallVector<TreeNodePtr, 8> Children(Node->begin(), Node->end()); 1433 std::sort(Children.begin(), Children.end(), 1434 [](const TreeNodePtr Ch1, const TreeNodePtr Ch2) { 1435 return Ch1->getDFSNumIn() < Ch2->getDFSNumIn(); 1436 }); 1437 1438 auto PrintChildrenError = [Node, &Children, PrintNodeAndDFSNums]( 1439 const TreeNodePtr FirstCh, const TreeNodePtr SecondCh) { 1440 assert(FirstCh); 1441 1442 errs() << "Incorrect DFS numbers for:\n\tParent "; 1443 PrintNodeAndDFSNums(Node); 1444 1445 errs() << "\n\tChild "; 1446 PrintNodeAndDFSNums(FirstCh); 1447 1448 if (SecondCh) { 1449 errs() << "\n\tSecond child "; 1450 PrintNodeAndDFSNums(SecondCh); 1451 } 1452 1453 errs() << "\nAll children: "; 1454 for (const TreeNodePtr Ch : Children) { 1455 PrintNodeAndDFSNums(Ch); 1456 errs() << ", "; 1457 } 1458 1459 errs() << '\n'; 1460 errs().flush(); 1461 }; 1462 1463 if (Children.front()->getDFSNumIn() != Node->getDFSNumIn() + 1) { 1464 PrintChildrenError(Children.front(), nullptr); 1465 return false; 1466 } 1467 1468 if (Children.back()->getDFSNumOut() + 1 != Node->getDFSNumOut()) { 1469 PrintChildrenError(Children.back(), nullptr); 1470 return false; 1471 } 1472 1473 for (size_t i = 0, e = Children.size() - 1; i != e; ++i) { 1474 if (Children[i]->getDFSNumOut() + 1 != Children[i + 1]->getDFSNumIn()) { 1475 PrintChildrenError(Children[i], Children[i + 1]); 1476 return false; 1477 } 1478 } 1479 } 1480 1481 return true; 1482 } 1483 1484 // The below routines verify the correctness of the dominator tree relative to 1485 // the CFG it's coming from. A tree is a dominator tree iff it has two 1486 // properties, called the parent property and the sibling property. Tarjan 1487 // and Lengauer prove (but don't explicitly name) the properties as part of 1488 // the proofs in their 1972 paper, but the proofs are mostly part of proving 1489 // things about semidominators and idoms, and some of them are simply asserted 1490 // based on even earlier papers (see, e.g., lemma 2). Some papers refer to 1491 // these properties as "valid" and "co-valid". See, e.g., "Dominators, 1492 // directed bipolar orders, and independent spanning trees" by Loukas 1493 // Georgiadis and Robert E. Tarjan, as well as "Dominator Tree Verification 1494 // and Vertex-Disjoint Paths " by the same authors. 1495 1496 // A very simple and direct explanation of these properties can be found in 1497 // "An Experimental Study of Dynamic Dominators", found at 1498 // https://arxiv.org/abs/1604.02711 1499 1500 // The easiest way to think of the parent property is that it's a requirement 1501 // of being a dominator. Let's just take immediate dominators. For PARENT to 1502 // be an immediate dominator of CHILD, all paths in the CFG must go through 1503 // PARENT before they hit CHILD. This implies that if you were to cut PARENT 1504 // out of the CFG, there should be no paths to CHILD that are reachable. If 1505 // there are, then you now have a path from PARENT to CHILD that goes around 1506 // PARENT and still reaches CHILD, which by definition, means PARENT can't be 1507 // a dominator of CHILD (let alone an immediate one). 1508 1509 // The sibling property is similar. It says that for each pair of sibling 1510 // nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each 1511 // other. If sibling LEFT dominated sibling RIGHT, it means there are no 1512 // paths in the CFG from sibling LEFT to sibling RIGHT that do not go through 1513 // LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of 1514 // RIGHT, not a sibling. 1515 1516 // It is possible to verify the parent and sibling properties in 1517 // linear time, but the algorithms are complex. Instead, we do it in a 1518 // straightforward N^2 and N^3 way below, using direct path reachability. 1519 1520 1521 // Checks if the tree has the parent property: if for all edges from V to W in 1522 // the input graph, such that V is reachable, the parent of W in the tree is 1523 // an ancestor of V in the tree. 1524 // 1525 // This means that if a node gets disconnected from the graph, then all of 1526 // the nodes it dominated previously will now become unreachable. 1527 bool verifyParentProperty(const DomTreeT &DT) { 1528 for (auto &NodeToTN : DT.DomTreeNodes) { 1529 const TreeNodePtr TN = NodeToTN.second.get(); 1530 const NodePtr BB = TN->getBlock(); 1531 if (!BB || TN->getChildren().empty()) continue; 1532 1533 DEBUG(dbgs() << "Verifying parent property of node " 1534 << BlockNamePrinter(TN) << "\n"); 1535 clear(); 1536 doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) { 1537 return From != BB && To != BB; 1538 }); 1539 1540 for (TreeNodePtr Child : TN->getChildren()) 1541 if (NodeToInfo.count(Child->getBlock()) != 0) { 1542 errs() << "Child " << BlockNamePrinter(Child) 1543 << " reachable after its parent " << BlockNamePrinter(BB) 1544 << " is removed!\n"; 1545 errs().flush(); 1546 1547 return false; 1548 } 1549 } 1550 1551 return true; 1552 } 1553 1554 // Check if the tree has sibling property: if a node V does not dominate a 1555 // node W for all siblings V and W in the tree. 1556 // 1557 // This means that if a node gets disconnected from the graph, then all of its 1558 // siblings will now still be reachable. 1559 bool verifySiblingProperty(const DomTreeT &DT) { 1560 for (auto &NodeToTN : DT.DomTreeNodes) { 1561 const TreeNodePtr TN = NodeToTN.second.get(); 1562 const NodePtr BB = TN->getBlock(); 1563 if (!BB || TN->getChildren().empty()) continue; 1564 1565 const auto &Siblings = TN->getChildren(); 1566 for (const TreeNodePtr N : Siblings) { 1567 clear(); 1568 NodePtr BBN = N->getBlock(); 1569 doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) { 1570 return From != BBN && To != BBN; 1571 }); 1572 1573 for (const TreeNodePtr S : Siblings) { 1574 if (S == N) continue; 1575 1576 if (NodeToInfo.count(S->getBlock()) == 0) { 1577 errs() << "Node " << BlockNamePrinter(S) 1578 << " not reachable when its sibling " << BlockNamePrinter(N) 1579 << " is removed!\n"; 1580 errs().flush(); 1581 1582 return false; 1583 } 1584 } 1585 } 1586 } 1587 1588 return true; 1589 } 1590}; 1591 1592template <class DomTreeT> 1593void Calculate(DomTreeT &DT) { 1594 SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, nullptr); 1595} 1596 1597template <class DomTreeT> 1598void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, 1599 typename DomTreeT::NodePtr To) { 1600 if (DT.isPostDominator()) std::swap(From, To); 1601 SemiNCAInfo<DomTreeT>::InsertEdge(DT, nullptr, From, To); 1602} 1603 1604template <class DomTreeT> 1605void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, 1606 typename DomTreeT::NodePtr To) { 1607 if (DT.isPostDominator()) std::swap(From, To); 1608 SemiNCAInfo<DomTreeT>::DeleteEdge(DT, nullptr, From, To); 1609} 1610 1611template <class DomTreeT> 1612void ApplyUpdates(DomTreeT &DT, 1613 ArrayRef<typename DomTreeT::UpdateType> Updates) { 1614 SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, Updates); 1615} 1616 1617template <class DomTreeT> 1618bool Verify(const DomTreeT &DT) { 1619 SemiNCAInfo<DomTreeT> SNCA(nullptr); 1620 return SNCA.verifyRoots(DT) && SNCA.verifyReachability(DT) && 1621 SNCA.VerifyLevels(DT) && SNCA.verifyParentProperty(DT) && 1622 SNCA.verifySiblingProperty(DT) && SNCA.VerifyDFSNumbers(DT); 1623} 1624 1625} // namespace DomTreeBuilder 1626} // namespace llvm 1627 1628#undef DEBUG_TYPE 1629 1630#endif 1631