contrib/llvm/include/llvm/Support/GenericDomTreeConstruction.h

   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 /// upates (insertion and deletions). The implemented algorithm is based on this
  25 /// 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/DenseSet.h"
  38 #include "llvm/ADT/DepthFirstIterator.h"
  39 #include "llvm/ADT/SmallPtrSet.h"
  40 #include "llvm/Support/Debug.h"
  41 #include "llvm/Support/GenericDomTree.h"
  42
  43 #define DEBUG_TYPE "dom-tree-builder"
  44
  45 namespace llvm {
  46 namespace DomTreeBuilder {
  47
  48 template <typename NodePtr, bool Inverse>
  49 struct ChildrenGetter {
  50   static auto Get(NodePtr N) -> decltype(reverse(children<NodePtr>(N))) {
  51     return reverse(children<NodePtr>(N));
  52   }
  53 };
  54
  55 template <typename NodePtr>
  56 struct ChildrenGetter<NodePtr, true> {
  57   static auto Get(NodePtr N) -> decltype(inverse_children<NodePtr>(N)) {
  58     return inverse_children<NodePtr>(N);
  59   }
  60 };
  61
  62 template <typename DomTreeT>
  63 struct SemiNCAInfo {
  64   using NodePtr = typename DomTreeT::NodePtr;
  65   using NodeT = typename DomTreeT::NodeType;
  66   using TreeNodePtr = DomTreeNodeBase<NodeT> *;
  67   static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
  68
  69   // Information record used by Semi-NCA during tree construction.
  70   struct InfoRec {
  71     unsigned DFSNum = 0;
  72     unsigned Parent = 0;
  73     unsigned Semi = 0;
  74     NodePtr Label = nullptr;
  75     NodePtr IDom = nullptr;
  76     SmallVector<NodePtr, 2> ReverseChildren;
  77   };
  78
  79   // Number to node mapping is 1-based. Initialize the mapping to start with
  80   // a dummy element.
  81   std::vector<NodePtr> NumToNode = {nullptr};
  82   DenseMap<NodePtr, InfoRec> NodeToInfo;
  83
  84   void clear() {
  85     NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
  86     NodeToInfo.clear();
  87   }
  88
  89   NodePtr getIDom(NodePtr BB) const {
  90     auto InfoIt = NodeToInfo.find(BB);
  91     if (InfoIt == NodeToInfo.end()) return nullptr;
  92
  93     return InfoIt->second.IDom;
  94   }
  95
  96   TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT) {
  97     if (TreeNodePtr Node = DT.getNode(BB)) return Node;
  98
  99     // Haven't calculated this node yet?  Get or calculate the node for the
 100     // immediate dominator.
 101     NodePtr IDom = getIDom(BB);
 102
 103     assert(IDom || DT.DomTreeNodes[nullptr]);
 104     TreeNodePtr IDomNode = getNodeForBlock(IDom, DT);
 105
 106     // Add a new tree node for this NodeT, and link it as a child of
 107     // IDomNode
 108     return (DT.DomTreeNodes[BB] = IDomNode->addChild(
 109         llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode)))
 110         .get();
 111   }
 112
 113   static bool AlwaysDescend(NodePtr, NodePtr) { return true; }
 114
 115   struct BlockNamePrinter {
 116     NodePtr N;
 117
 118     BlockNamePrinter(NodePtr Block) : N(Block) {}
 119     BlockNamePrinter(TreeNodePtr TN) : N(TN ? TN->getBlock() : nullptr) {}
 120
 121     friend raw_ostream &operator<<(raw_ostream &O, const BlockNamePrinter &BP) {
 122       if (!BP.N)
 123         O << "nullptr";
 124       else
 125         BP.N->printAsOperand(O, false);
 126
 127       return O;
 128     }
 129   };
 130
 131   // Custom DFS implementation which can skip nodes based on a provided
 132   // predicate. It also collects ReverseChildren so that we don't have to spend
 133   // time getting predecessors in SemiNCA.
 134   template <bool Inverse, typename DescendCondition>
 135   unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,
 136                   unsigned AttachToNum) {
 137     assert(V);
 138     SmallVector<NodePtr, 64> WorkList = {V};
 139     if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum;
 140
 141     while (!WorkList.empty()) {
 142       const NodePtr BB = WorkList.pop_back_val();
 143       auto &BBInfo = NodeToInfo[BB];
 144
 145       // Visited nodes always have positive DFS numbers.
 146       if (BBInfo.DFSNum != 0) continue;
 147       BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
 148       BBInfo.Label = BB;
 149       NumToNode.push_back(BB);
 150
 151       for (const NodePtr Succ : ChildrenGetter<NodePtr, Inverse>::Get(BB)) {
 152         const auto SIT = NodeToInfo.find(Succ);
 153         // Don't visit nodes more than once but remember to collect
 154         // RerverseChildren.
 155         if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
 156           if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
 157           continue;
 158         }
 159
 160         if (!Condition(BB, Succ)) continue;
 161
 162         // It's fine to add Succ to the map, because we know that it will be
 163         // visited later.
 164         auto &SuccInfo = NodeToInfo[Succ];
 165         WorkList.push_back(Succ);
 166         SuccInfo.Parent = LastNum;
 167         SuccInfo.ReverseChildren.push_back(BB);
 168       }
 169     }
 170
 171     return LastNum;
 172   }
 173
 174   NodePtr eval(NodePtr VIn, unsigned LastLinked) {
 175     auto &VInInfo = NodeToInfo[VIn];
 176     if (VInInfo.DFSNum < LastLinked)
 177       return VIn;
 178
 179     SmallVector<NodePtr, 32> Work;
 180     SmallPtrSet<NodePtr, 32> Visited;
 181
 182     if (VInInfo.Parent >= LastLinked)
 183       Work.push_back(VIn);
 184
 185     while (!Work.empty()) {
 186       NodePtr V = Work.back();
 187       auto &VInfo = NodeToInfo[V];
 188       NodePtr VAncestor = NumToNode[VInfo.Parent];
 189
 190       // Process Ancestor first
 191       if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) {
 192         Work.push_back(VAncestor);
 193         continue;
 194       }
 195       Work.pop_back();
 196
 197       // Update VInfo based on Ancestor info
 198       if (VInfo.Parent < LastLinked)
 199         continue;
 200
 201       auto &VAInfo = NodeToInfo[VAncestor];
 202       NodePtr VAncestorLabel = VAInfo.Label;
 203       NodePtr VLabel = VInfo.Label;
 204       if (NodeToInfo[VAncestorLabel].Semi < NodeToInfo[VLabel].Semi)
 205         VInfo.Label = VAncestorLabel;
 206       VInfo.Parent = VAInfo.Parent;
 207     }
 208
 209     return VInInfo.Label;
 210   }
 211
 212   // This function requires DFS to be run before calling it.
 213   void runSemiNCA(DomTreeT &DT, const unsigned MinLevel = 0) {
 214     const unsigned NextDFSNum(NumToNode.size());
 215     // Initialize IDoms to spanning tree parents.
 216     for (unsigned i = 1; i < NextDFSNum; ++i) {
 217       const NodePtr V = NumToNode[i];
 218       auto &VInfo = NodeToInfo[V];
 219       VInfo.IDom = NumToNode[VInfo.Parent];
 220     }
 221
 222     // Step #1: Calculate the semidominators of all vertices.
 223     for (unsigned i = NextDFSNum - 1; i >= 2; --i) {
 224       NodePtr W = NumToNode[i];
 225       auto &WInfo = NodeToInfo[W];
 226
 227       // Initialize the semi dominator to point to the parent node.
 228       WInfo.Semi = WInfo.Parent;
 229       for (const auto &N : WInfo.ReverseChildren) {
 230         if (NodeToInfo.count(N) == 0)  // Skip unreachable predecessors.
 231           continue;
 232
 233         const TreeNodePtr TN = DT.getNode(N);
 234         // Skip predecessors whose level is above the subtree we are processing.
 235         if (TN && TN->getLevel() < MinLevel)
 236           continue;
 237
 238         unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi;
 239         if (SemiU < WInfo.Semi) WInfo.Semi = SemiU;
 240       }
 241     }
 242
 243     // Step #2: Explicitly define the immediate dominator of each vertex.
 244     //          IDom[i] = NCA(SDom[i], SpanningTreeParent(i)).
 245     // Note that the parents were stored in IDoms and later got invalidated
 246     // during path compression in Eval.
 247     for (unsigned i = 2; i < NextDFSNum; ++i) {
 248       const NodePtr W = NumToNode[i];
 249       auto &WInfo = NodeToInfo[W];
 250       const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;
 251       NodePtr WIDomCandidate = WInfo.IDom;
 252       while (NodeToInfo[WIDomCandidate].DFSNum > SDomNum)
 253         WIDomCandidate = NodeToInfo[WIDomCandidate].IDom;
 254
 255       WInfo.IDom = WIDomCandidate;
 256     }
 257   }
 258
 259   template <typename DescendCondition>
 260   unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
 261     unsigned Num = 0;
 262
 263     if (DT.Roots.size() > 1) {
 264       auto &BBInfo = NodeToInfo[nullptr];
 265       BBInfo.DFSNum = BBInfo.Semi = ++Num;
 266       BBInfo.Label = nullptr;
 267
 268       NumToNode.push_back(nullptr);  // NumToNode[n] = V;
 269     }
 270
 271     if (DT.isPostDominator()) {
 272       for (auto *Root : DT.Roots) Num = runDFS<true>(Root, Num, DC, 1);
 273     } else {
 274       assert(DT.Roots.size() == 1);
 275       Num = runDFS<false>(DT.Roots[0], Num, DC, Num);
 276     }
 277
 278     return Num;
 279   }
 280
 281   void calculateFromScratch(DomTreeT &DT, const unsigned NumBlocks) {
 282     // Step #0: Number blocks in depth-first order and initialize variables used
 283     // in later stages of the algorithm.
 284     const unsigned LastDFSNum = doFullDFSWalk(DT, AlwaysDescend);
 285
 286     runSemiNCA(DT);
 287
 288     if (DT.Roots.empty()) return;
 289
 290     // Add a node for the root.  This node might be the actual root, if there is
 291     // one exit block, or it may be the virtual exit (denoted by
 292     // (BasicBlock *)0) which postdominates all real exits if there are multiple
 293     // exit blocks, or an infinite loop.
 294     // It might be that some blocks did not get a DFS number (e.g., blocks of
 295     // infinite loops). In these cases an artificial exit node is required.
 296     const bool MultipleRoots = DT.Roots.size() > 1 || (DT.isPostDominator() &&
 297                                                        LastDFSNum != NumBlocks);
 298     NodePtr Root = !MultipleRoots ? DT.Roots[0] : nullptr;
 299
 300     DT.RootNode = (DT.DomTreeNodes[Root] =
 301                        llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
 302         .get();
 303     attachNewSubtree(DT, DT.RootNode);
 304   }
 305
 306   void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {
 307     // Attach the first unreachable block to AttachTo.
 308     NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
 309     // Loop over all of the discovered blocks in the function...
 310     for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
 311       NodePtr W = NumToNode[i];
 312       DEBUG(dbgs() << "\tdiscovered a new reachable node "
 313                    << BlockNamePrinter(W) << "\n");
 314
 315       // Don't replace this with 'count', the insertion side effect is important
 316       if (DT.DomTreeNodes[W]) continue;  // Haven't calculated this node yet?
 317
 318       NodePtr ImmDom = getIDom(W);
 319
 320       // Get or calculate the node for the immediate dominator
 321       TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
 322
 323       // Add a new tree node for this BasicBlock, and link it as a child of
 324       // IDomNode
 325       DT.DomTreeNodes[W] = IDomNode->addChild(
 326           llvm::make_unique<DomTreeNodeBase<NodeT>>(W, IDomNode));
 327     }
 328   }
 329
 330   void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) {
 331     NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
 332     for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
 333       const NodePtr N = NumToNode[i];
 334       const TreeNodePtr TN = DT.getNode(N);
 335       assert(TN);
 336       const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom);
 337       TN->setIDom(NewIDom);
 338     }
 339   }
 340
 341   // Helper struct used during edge insertions.
 342   struct InsertionInfo {
 343     using BucketElementTy = std::pair<unsigned, TreeNodePtr>;
 344     struct DecreasingLevel {
 345       bool operator()(const BucketElementTy &First,
 346                       const BucketElementTy &Second) const {
 347         return First.first > Second.first;
 348       }
 349     };
 350
 351     std::priority_queue<BucketElementTy, SmallVector<BucketElementTy, 8>,
 352         DecreasingLevel>
 353         Bucket;  // Queue of tree nodes sorted by level in descending order.
 354     SmallDenseSet<TreeNodePtr, 8> Affected;
 355     SmallDenseSet<TreeNodePtr, 8> Visited;
 356     SmallVector<TreeNodePtr, 8> AffectedQueue;
 357     SmallVector<TreeNodePtr, 8> VisitedNotAffectedQueue;
 358   };
 359
 360   static void InsertEdge(DomTreeT &DT, const NodePtr From, const NodePtr To) {
 361     assert(From && To && "Cannot connect nullptrs");
 362     DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> "
 363                  << BlockNamePrinter(To) << "\n");
 364     const TreeNodePtr FromTN = DT.getNode(From);
 365
 366     // Ignore edges from unreachable nodes.
 367     if (!FromTN) return;
 368
 369     DT.DFSInfoValid = false;
 370
 371     const TreeNodePtr ToTN = DT.getNode(To);
 372     if (!ToTN)
 373       InsertUnreachable(DT, FromTN, To);
 374     else
 375       InsertReachable(DT, FromTN, ToTN);
 376   }
 377
 378   // Handles insertion to a node already in the dominator tree.
 379   static void InsertReachable(DomTreeT &DT, const TreeNodePtr From,
 380                               const TreeNodePtr To) {
 381     DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock())
 382                  << " -> " << BlockNamePrinter(To->getBlock()) << "\n");
 383     const NodePtr NCDBlock =
 384         DT.findNearestCommonDominator(From->getBlock(), To->getBlock());
 385     assert(NCDBlock || DT.isPostDominator());
 386     const TreeNodePtr NCD = DT.getNode(NCDBlock);
 387     assert(NCD);
 388
 389     DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n");
 390     const TreeNodePtr ToIDom = To->getIDom();
 391
 392     // Nothing affected -- NCA property holds.
 393     // (Based on the lemma 2.5 from the second paper.)
 394     if (NCD == To || NCD == ToIDom) return;
 395
 396     // Identify and collect affected nodes.
 397     InsertionInfo II;
 398     DEBUG(dbgs() << "Marking " << BlockNamePrinter(To) << " as affected\n");
 399     II.Affected.insert(To);
 400     const unsigned ToLevel = To->getLevel();
 401     DEBUG(dbgs() << "Putting " << BlockNamePrinter(To) << " into a Bucket\n");
 402     II.Bucket.push({ToLevel, To});
 403
 404     while (!II.Bucket.empty()) {
 405       const TreeNodePtr CurrentNode = II.Bucket.top().second;
 406       II.Bucket.pop();
 407       DEBUG(dbgs() << "\tAdding to Visited and AffectedQueue: "
 408                    << BlockNamePrinter(CurrentNode) << "\n");
 409       II.Visited.insert(CurrentNode);
 410       II.AffectedQueue.push_back(CurrentNode);
 411
 412       // Discover and collect affected successors of the current node.
 413       VisitInsertion(DT, CurrentNode, CurrentNode->getLevel(), NCD, II);
 414     }
 415
 416     // Finish by updating immediate dominators and levels.
 417     UpdateInsertion(DT, NCD, II);
 418   }
 419
 420   // Visits an affected node and collect its affected successors.
 421   static void VisitInsertion(DomTreeT &DT, const TreeNodePtr TN,
 422                              const unsigned RootLevel, const TreeNodePtr NCD,
 423                              InsertionInfo &II) {
 424     const unsigned NCDLevel = NCD->getLevel();
 425     DEBUG(dbgs() << "Visiting " << BlockNamePrinter(TN) << "\n");
 426
 427     assert(TN->getBlock());
 428     for (const NodePtr Succ :
 429         ChildrenGetter<NodePtr, IsPostDom>::Get(TN->getBlock())) {
 430       const TreeNodePtr SuccTN = DT.getNode(Succ);
 431       assert(SuccTN && "Unreachable successor found at reachable insertion");
 432       const unsigned SuccLevel = SuccTN->getLevel();
 433
 434       DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
 435                    << ", level = " << SuccLevel << "\n");
 436
 437       // Succ dominated by subtree From -- not affected.
 438       // (Based on the lemma 2.5 from the second paper.)
 439       if (SuccLevel > RootLevel) {
 440         DEBUG(dbgs() << "\t\tDominated by subtree From\n");
 441         if (II.Visited.count(SuccTN) != 0) continue;
 442
 443         DEBUG(dbgs() << "\t\tMarking visited not affected "
 444                      << BlockNamePrinter(Succ) << "\n");
 445         II.Visited.insert(SuccTN);
 446         II.VisitedNotAffectedQueue.push_back(SuccTN);
 447         VisitInsertion(DT, SuccTN, RootLevel, NCD, II);
 448       } else if ((SuccLevel > NCDLevel + 1) && II.Affected.count(SuccTN) == 0) {
 449         DEBUG(dbgs() << "\t\tMarking affected and adding "
 450                      << BlockNamePrinter(Succ) << " to a Bucket\n");
 451         II.Affected.insert(SuccTN);
 452         II.Bucket.push({SuccLevel, SuccTN});
 453       }
 454     }
 455   }
 456
 457   // Updates immediate dominators and levels after insertion.
 458   static void UpdateInsertion(DomTreeT &DT, const TreeNodePtr NCD,
 459                               InsertionInfo &II) {
 460     DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n");
 461
 462     for (const TreeNodePtr TN : II.AffectedQueue) {
 463       DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN)
 464                    << ") = " << BlockNamePrinter(NCD) << "\n");
 465       TN->setIDom(NCD);
 466     }
 467
 468     UpdateLevelsAfterInsertion(II);
 469   }
 470
 471   static void UpdateLevelsAfterInsertion(InsertionInfo &II) {
 472     DEBUG(dbgs() << "Updating levels for visited but not affected nodes\n");
 473
 474     for (const TreeNodePtr TN : II.VisitedNotAffectedQueue) {
 475       DEBUG(dbgs() << "\tlevel(" << BlockNamePrinter(TN) << ") = ("
 476                    << BlockNamePrinter(TN->getIDom()) << ") "
 477                    << TN->getIDom()->getLevel() << " + 1\n");
 478       TN->UpdateLevel();
 479     }
 480   }
 481
 482   // Handles insertion to previously unreachable nodes.
 483   static void InsertUnreachable(DomTreeT &DT, const TreeNodePtr From,
 484                                 const NodePtr To) {
 485     DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From)
 486                  << " -> (unreachable) " << BlockNamePrinter(To) << "\n");
 487
 488     // Collect discovered edges to already reachable nodes.
 489     SmallVector<std::pair<NodePtr, TreeNodePtr>, 8> DiscoveredEdgesToReachable;
 490     // Discover and connect nodes that became reachable with the insertion.
 491     ComputeUnreachableDominators(DT, To, From, DiscoveredEdgesToReachable);
 492
 493     DEBUG(dbgs() << "Inserted " << BlockNamePrinter(From)
 494                  << " -> (prev unreachable) " << BlockNamePrinter(To) << "\n");
 495
 496     DEBUG(DT.print(dbgs()));
 497
 498     // Used the discovered edges and inset discovered connecting (incoming)
 499     // edges.
 500     for (const auto &Edge : DiscoveredEdgesToReachable) {
 501       DEBUG(dbgs() << "\tInserting discovered connecting edge "
 502                    << BlockNamePrinter(Edge.first) << " -> "
 503                    << BlockNamePrinter(Edge.second) << "\n");
 504       InsertReachable(DT, DT.getNode(Edge.first), Edge.second);
 505     }
 506   }
 507
 508   // Connects nodes that become reachable with an insertion.
 509   static void ComputeUnreachableDominators(
 510       DomTreeT &DT, const NodePtr Root, const TreeNodePtr Incoming,
 511       SmallVectorImpl<std::pair<NodePtr, TreeNodePtr>>
 512       &DiscoveredConnectingEdges) {
 513     assert(!DT.getNode(Root) && "Root must not be reachable");
 514
 515     // Visit only previously unreachable nodes.
 516     auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From,
 517                                                                   NodePtr To) {
 518       const TreeNodePtr ToTN = DT.getNode(To);
 519       if (!ToTN) return true;
 520
 521       DiscoveredConnectingEdges.push_back({From, ToTN});
 522       return false;
 523     };
 524
 525     SemiNCAInfo SNCA;
 526     SNCA.runDFS<IsPostDom>(Root, 0, UnreachableDescender, 0);
 527     SNCA.runSemiNCA(DT);
 528     SNCA.attachNewSubtree(DT, Incoming);
 529
 530     DEBUG(dbgs() << "After adding unreachable nodes\n");
 531     DEBUG(DT.print(dbgs()));
 532   }
 533
 534   // Checks if the tree contains all reachable nodes in the input graph.
 535   bool verifyReachability(const DomTreeT &DT) {
 536     clear();
 537     doFullDFSWalk(DT, AlwaysDescend);
 538
 539     for (auto &NodeToTN : DT.DomTreeNodes) {
 540       const TreeNodePtr TN = NodeToTN.second.get();
 541       const NodePtr BB = TN->getBlock();
 542
 543       // Virtual root has a corresponding virtual CFG node.
 544       if (DT.isVirtualRoot(TN)) continue;
 545
 546       if (NodeToInfo.count(BB) == 0) {
 547         errs() << "DomTree node " << BlockNamePrinter(BB)
 548                << " not found by DFS walk!\n";
 549         errs().flush();
 550
 551         return false;
 552       }
 553     }
 554
 555     for (const NodePtr N : NumToNode) {
 556       if (N && !DT.getNode(N)) {
 557         errs() << "CFG node " << BlockNamePrinter(N)
 558                << " not found in the DomTree!\n";
 559         errs().flush();
 560
 561         return false;
 562       }
 563     }
 564
 565     return true;
 566   }
 567
 568   static void DeleteEdge(DomTreeT &DT, const NodePtr From, const NodePtr To) {
 569     assert(From && To && "Cannot disconnect nullptrs");
 570     DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> "
 571                  << BlockNamePrinter(To) << "\n");
 572
 573 #ifndef NDEBUG
 574     // Ensure that the edge was in fact deleted from the CFG before informing
 575     // the DomTree about it.
 576     // The check is O(N), so run it only in debug configuration.
 577     auto IsSuccessor = [](const NodePtr SuccCandidate, const NodePtr Of) {
 578       auto Successors = ChildrenGetter<NodePtr, IsPostDom>::Get(Of);
 579       return llvm::find(Successors, SuccCandidate) != Successors.end();
 580     };
 581     (void)IsSuccessor;
 582     assert(!IsSuccessor(To, From) && "Deleted edge still exists in the CFG!");
 583 #endif
 584
 585     const TreeNodePtr FromTN = DT.getNode(From);
 586     // Deletion in an unreachable subtree -- nothing to do.
 587     if (!FromTN) return;
 588
 589     const TreeNodePtr ToTN = DT.getNode(To);
 590     assert(ToTN && "To already unreachable -- there is no edge to delete");
 591     const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);
 592     const TreeNodePtr NCD = DT.getNode(NCDBlock);
 593
 594     // To dominates From -- nothing to do.
 595     if (ToTN == NCD) return;
 596
 597     const TreeNodePtr ToIDom = ToTN->getIDom();
 598     DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
 599                  << BlockNamePrinter(ToIDom) << "\n");
 600
 601     // To remains reachable after deletion.
 602     // (Based on the caption under Figure 4. from the second paper.)
 603     if (FromTN != ToIDom || HasProperSupport(DT, ToTN))
 604       DeleteReachable(DT, FromTN, ToTN);
 605     else
 606       DeleteUnreachable(DT, ToTN);
 607   }
 608
 609   // Handles deletions that leave destination nodes reachable.
 610   static void DeleteReachable(DomTreeT &DT, const TreeNodePtr FromTN,
 611                               const TreeNodePtr ToTN) {
 612     DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN) << " -> "
 613                  << BlockNamePrinter(ToTN) << "\n");
 614     DEBUG(dbgs() << "\tRebuilding subtree\n");
 615
 616     // Find the top of the subtree that needs to be rebuilt.
 617     // (Based on the lemma 2.6 from the second paper.)
 618     const NodePtr ToIDom =
 619         DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock());
 620     assert(ToIDom || DT.isPostDominator());
 621     const TreeNodePtr ToIDomTN = DT.getNode(ToIDom);
 622     assert(ToIDomTN);
 623     const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom();
 624     // Top of the subtree to rebuild is the root node. Rebuild the tree from
 625     // scratch.
 626     if (!PrevIDomSubTree) {
 627       DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
 628       DT.recalculate(*DT.Parent);
 629       return;
 630     }
 631
 632     // Only visit nodes in the subtree starting at To.
 633     const unsigned Level = ToIDomTN->getLevel();
 634     auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {
 635       return DT.getNode(To)->getLevel() > Level;
 636     };
 637
 638     DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN) << "\n");
 639
 640     SemiNCAInfo SNCA;
 641     SNCA.runDFS<IsPostDom>(ToIDom, 0, DescendBelow, 0);
 642     DEBUG(dbgs() << "\tRunning Semi-NCA\n");
 643     SNCA.runSemiNCA(DT, Level);
 644     SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
 645   }
 646
 647   // Checks if a node has proper support, as defined on the page 3 and later
 648   // explained on the page 7 of the second paper.
 649   static bool HasProperSupport(DomTreeT &DT, const TreeNodePtr TN) {
 650     DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN) << "\n");
 651     for (const NodePtr Pred :
 652         ChildrenGetter<NodePtr, !IsPostDom>::Get(TN->getBlock())) {
 653       DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
 654       if (!DT.getNode(Pred)) continue;
 655
 656       const NodePtr Support =
 657           DT.findNearestCommonDominator(TN->getBlock(), Pred);
 658       DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
 659       if (Support != TN->getBlock()) {
 660         DEBUG(dbgs() << "\t" << BlockNamePrinter(TN)
 661                      << " is reachable from support "
 662                      << BlockNamePrinter(Support) << "\n");
 663         return true;
 664       }
 665     }
 666
 667     return false;
 668   }
 669
 670   // Handle deletions that make destination node unreachable.
 671   // (Based on the lemma 2.7 from the second paper.)
 672   static void DeleteUnreachable(DomTreeT &DT, const TreeNodePtr ToTN) {
 673     DEBUG(dbgs() << "Deleting unreachable subtree " << BlockNamePrinter(ToTN)
 674                  << "\n");
 675     assert(ToTN);
 676     assert(ToTN->getBlock());
 677
 678     SmallVector<NodePtr, 16> AffectedQueue;
 679     const unsigned Level = ToTN->getLevel();
 680
 681     // Traverse destination node's descendants with greater level in the tree
 682     // and collect visited nodes.
 683     auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
 684       const TreeNodePtr TN = DT.getNode(To);
 685       assert(TN);
 686       if (TN->getLevel() > Level) return true;
 687       if (llvm::find(AffectedQueue, To) == AffectedQueue.end())
 688         AffectedQueue.push_back(To);
 689
 690       return false;
 691     };
 692
 693     SemiNCAInfo SNCA;
 694     unsigned LastDFSNum =
 695         SNCA.runDFS<IsPostDom>(ToTN->getBlock(), 0, DescendAndCollect, 0);
 696
 697     TreeNodePtr MinNode = ToTN;
 698
 699     // Identify the top of the subtree to rebuilt by finding the NCD of all
 700     // the affected nodes.
 701     for (const NodePtr N : AffectedQueue) {
 702       const TreeNodePtr TN = DT.getNode(N);
 703       const NodePtr NCDBlock =
 704           DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock());
 705       assert(NCDBlock || DT.isPostDominator());
 706       const TreeNodePtr NCD = DT.getNode(NCDBlock);
 707       assert(NCD);
 708
 709       DEBUG(dbgs() << "Processing affected node " << BlockNamePrinter(TN)
 710                    << " with NCD = " << BlockNamePrinter(NCD)
 711                    << ", MinNode =" << BlockNamePrinter(MinNode) << "\n");
 712       if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD;
 713     }
 714
 715     // Root reached, rebuild the whole tree from scratch.
 716     if (!MinNode->getIDom()) {
 717       DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
 718       DT.recalculate(*DT.Parent);
 719       return;
 720     }
 721
 722     // Erase the unreachable subtree in reverse preorder to process all children
 723     // before deleting their parent.
 724     for (unsigned i = LastDFSNum; i > 0; --i) {
 725       const NodePtr N = SNCA.NumToNode[i];
 726       const TreeNodePtr TN = DT.getNode(N);
 727       DEBUG(dbgs() << "Erasing node " << BlockNamePrinter(TN) << "\n");
 728
 729       EraseNode(DT, TN);
 730     }
 731
 732     // The affected subtree start at the To node -- there's no extra work to do.
 733     if (MinNode == ToTN) return;
 734
 735     DEBUG(dbgs() << "DeleteUnreachable: running DFS with MinNode = "
 736                  << BlockNamePrinter(MinNode) << "\n");
 737     const unsigned MinLevel = MinNode->getLevel();
 738     const TreeNodePtr PrevIDom = MinNode->getIDom();
 739     assert(PrevIDom);
 740     SNCA.clear();
 741
 742     // Identify nodes that remain in the affected subtree.
 743     auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) {
 744       const TreeNodePtr ToTN = DT.getNode(To);
 745       return ToTN && ToTN->getLevel() > MinLevel;
 746     };
 747     SNCA.runDFS<IsPostDom>(MinNode->getBlock(), 0, DescendBelow, 0);
 748
 749     DEBUG(dbgs() << "Previous IDom(MinNode) = " << BlockNamePrinter(PrevIDom)
 750                  << "\nRunning Semi-NCA\n");
 751
 752     // Rebuild the remaining part of affected subtree.
 753     SNCA.runSemiNCA(DT, MinLevel);
 754     SNCA.reattachExistingSubtree(DT, PrevIDom);
 755   }
 756
 757   // Removes leaf tree nodes from the dominator tree.
 758   static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
 759     assert(TN);
 760     assert(TN->getNumChildren() == 0 && "Not a tree leaf");
 761
 762     const TreeNodePtr IDom = TN->getIDom();
 763     assert(IDom);
 764
 765     auto ChIt = llvm::find(IDom->Children, TN);
 766     assert(ChIt != IDom->Children.end());
 767     std::swap(*ChIt, IDom->Children.back());
 768     IDom->Children.pop_back();
 769
 770     DT.DomTreeNodes.erase(TN->getBlock());
 771   }
 772
 773   //~~
 774   //===--------------- DomTree correctness verification ---------------------===
 775   //~~
 776
 777   // Check if for every parent with a level L in the tree all of its children
 778   // have level L + 1.
 779   static bool VerifyLevels(const DomTreeT &DT) {
 780     for (auto &NodeToTN : DT.DomTreeNodes) {
 781       const TreeNodePtr TN = NodeToTN.second.get();
 782       const NodePtr BB = TN->getBlock();
 783       if (!BB) continue;
 784
 785       const TreeNodePtr IDom = TN->getIDom();
 786       if (!IDom && TN->getLevel() != 0) {
 787         errs() << "Node without an IDom " << BlockNamePrinter(BB)
 788                << " has a nonzero level " << TN->getLevel() << "!\n";
 789         errs().flush();
 790
 791         return false;
 792       }
 793
 794       if (IDom && TN->getLevel() != IDom->getLevel() + 1) {
 795         errs() << "Node " << BlockNamePrinter(BB) << " has level "
 796                << TN->getLevel() << " while its IDom "
 797                << BlockNamePrinter(IDom->getBlock()) << " has level "
 798                << IDom->getLevel() << "!\n";
 799         errs().flush();
 800
 801         return false;
 802       }
 803     }
 804
 805     return true;
 806   }
 807
 808   // Checks if for every edge From -> To in the graph
 809   //     NCD(From, To) == IDom(To) or To.
 810   bool verifyNCD(const DomTreeT &DT) {
 811     clear();
 812     doFullDFSWalk(DT, AlwaysDescend);
 813
 814     for (auto &BlockToInfo : NodeToInfo) {
 815       auto &Info = BlockToInfo.second;
 816
 817       const NodePtr From = NumToNode[Info.Parent];
 818       if (!From) continue;
 819
 820       const NodePtr To = BlockToInfo.first;
 821       const TreeNodePtr ToTN = DT.getNode(To);
 822       assert(ToTN);
 823
 824       const NodePtr NCD = DT.findNearestCommonDominator(From, To);
 825       const TreeNodePtr NCDTN = DT.getNode(NCD);
 826       const TreeNodePtr ToIDom = ToTN->getIDom();
 827       if (NCDTN != ToTN && NCDTN != ToIDom) {
 828         errs() << "NearestCommonDominator verification failed:\n\tNCD(From:"
 829                << BlockNamePrinter(From) << ", To:" << BlockNamePrinter(To)
 830                << ") = " << BlockNamePrinter(NCD)
 831                << ",\t (should be To or IDom[To]: " << BlockNamePrinter(ToIDom)
 832                << ")\n";
 833         errs().flush();
 834
 835         return false;
 836       }
 837     }
 838
 839     return true;
 840   }
 841
 842   // The below routines verify the correctness of the dominator tree relative to
 843   // the CFG it's coming from.  A tree is a dominator tree iff it has two
 844   // properties, called the parent property and the sibling property.  Tarjan
 845   // and Lengauer prove (but don't explicitly name) the properties as part of
 846   // the proofs in their 1972 paper, but the proofs are mostly part of proving
 847   // things about semidominators and idoms, and some of them are simply asserted
 848   // based on even earlier papers (see, e.g., lemma 2).  Some papers refer to
 849   // these properties as "valid" and "co-valid".  See, e.g., "Dominators,
 850   // directed bipolar orders, and independent spanning trees" by Loukas
 851   // Georgiadis and Robert E. Tarjan, as well as "Dominator Tree Verification
 852   // and Vertex-Disjoint Paths " by the same authors.
 853
 854   // A very simple and direct explanation of these properties can be found in
 855   // "An Experimental Study of Dynamic Dominators", found at
 856   // https://arxiv.org/abs/1604.02711
 857
 858   // The easiest way to think of the parent property is that it's a requirement
 859   // of being a dominator.  Let's just take immediate dominators.  For PARENT to
 860   // be an immediate dominator of CHILD, all paths in the CFG must go through
 861   // PARENT before they hit CHILD.  This implies that if you were to cut PARENT
 862   // out of the CFG, there should be no paths to CHILD that are reachable.  If
 863   // there are, then you now have a path from PARENT to CHILD that goes around
 864   // PARENT and still reaches CHILD, which by definition, means PARENT can't be
 865   // a dominator of CHILD (let alone an immediate one).
 866
 867   // The sibling property is similar.  It says that for each pair of sibling
 868   // nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each
 869   // other.  If sibling LEFT dominated sibling RIGHT, it means there are no
 870   // paths in the CFG from sibling LEFT to sibling RIGHT that do not go through
 871   // LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of
 872   // RIGHT, not a sibling.
 873
 874   // It is possible to verify the parent and sibling properties in
 875   // linear time, but the algorithms are complex. Instead, we do it in a
 876   // straightforward N^2 and N^3 way below, using direct path reachability.
 877
 878
 879   // Checks if the tree has the parent property: if for all edges from V to W in
 880   // the input graph, such that V is reachable, the parent of W in the tree is
 881   // an ancestor of V in the tree.
 882   //
 883   // This means that if a node gets disconnected from the graph, then all of
 884   // the nodes it dominated previously will now become unreachable.
 885   bool verifyParentProperty(const DomTreeT &DT) {
 886     for (auto &NodeToTN : DT.DomTreeNodes) {
 887       const TreeNodePtr TN = NodeToTN.second.get();
 888       const NodePtr BB = TN->getBlock();
 889       if (!BB || TN->getChildren().empty()) continue;
 890
 891       clear();
 892       doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) {
 893         return From != BB && To != BB;
 894       });
 895
 896       for (TreeNodePtr Child : TN->getChildren())
 897         if (NodeToInfo.count(Child->getBlock()) != 0) {
 898           errs() << "Child " << BlockNamePrinter(Child)
 899                  << " reachable after its parent " << BlockNamePrinter(BB)
 900                  << " is removed!\n";
 901           errs().flush();
 902
 903           return false;
 904         }
 905     }
 906
 907     return true;
 908   }
 909
 910   // Check if the tree has sibling property: if a node V does not dominate a
 911   // node W for all siblings V and W in the tree.
 912   //
 913   // This means that if a node gets disconnected from the graph, then all of its
 914   // siblings will now still be reachable.
 915   bool verifySiblingProperty(const DomTreeT &DT) {
 916     for (auto &NodeToTN : DT.DomTreeNodes) {
 917       const TreeNodePtr TN = NodeToTN.second.get();
 918       const NodePtr BB = TN->getBlock();
 919       if (!BB || TN->getChildren().empty()) continue;
 920
 921       const auto &Siblings = TN->getChildren();
 922       for (const TreeNodePtr N : Siblings) {
 923         clear();
 924         NodePtr BBN = N->getBlock();
 925         doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) {
 926           return From != BBN && To != BBN;
 927         });
 928
 929         for (const TreeNodePtr S : Siblings) {
 930           if (S == N) continue;
 931
 932           if (NodeToInfo.count(S->getBlock()) == 0) {
 933             errs() << "Node " << BlockNamePrinter(S)
 934                    << " not reachable when its sibling " << BlockNamePrinter(N)
 935                    << " is removed!\n";
 936             errs().flush();
 937
 938             return false;
 939           }
 940         }
 941       }
 942     }
 943
 944     return true;
 945   }
 946 };
 947
 948
 949 template <class DomTreeT, class FuncT>
 950 void Calculate(DomTreeT &DT, FuncT &F) {
 951   SemiNCAInfo<DomTreeT> SNCA;
 952   SNCA.calculateFromScratch(DT, GraphTraits<FuncT *>::size(&F));
 953 }
 954
 955 template <class DomTreeT>
 956 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
 957                 typename DomTreeT::NodePtr To) {
 958   if (DT.isPostDominator()) std::swap(From, To);
 959   SemiNCAInfo<DomTreeT>::InsertEdge(DT, From, To);
 960 }
 961
 962 template <class DomTreeT>
 963 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
 964                 typename DomTreeT::NodePtr To) {
 965   if (DT.isPostDominator()) std::swap(From, To);
 966   SemiNCAInfo<DomTreeT>::DeleteEdge(DT, From, To);
 967 }
 968
 969 template <class DomTreeT>
 970 bool Verify(const DomTreeT &DT) {
 971   SemiNCAInfo<DomTreeT> SNCA;
 972   return SNCA.verifyReachability(DT) && SNCA.VerifyLevels(DT) &&
 973          SNCA.verifyNCD(DT) && SNCA.verifyParentProperty(DT) &&
 974          SNCA.verifySiblingProperty(DT);
 975 }
 976
 977 }  // namespace DomTreeBuilder
 978 }  // namespace llvm
 979
 980 #undef DEBUG_TYPE
 981
 982 #endif