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