LCOV - code coverage report
Current view: top level - include/llvm/Support - GenericDomTreeConstruction.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 498 553 90.1 %
Date: 2017-09-14 15:23:50 Functions: 153 237 64.6 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- GenericDomTreeConstruction.h - Dominator Calculation ------*- C++ -*-==//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : /// \file
      10             : ///
      11             : /// Generic dominator tree construction - This file provides routines to
      12             : /// construct immediate dominator information for a flow-graph based on the
      13             : /// Semi-NCA algorithm described in this dissertation:
      14             : ///
      15             : ///   Linear-Time Algorithms for Dominators and Related Problems
      16             : ///   Loukas Georgiadis, Princeton University, November 2005, pp. 21-23:
      17             : ///   ftp://ftp.cs.princeton.edu/reports/2005/737.pdf
      18             : ///
      19             : /// This implements the O(n*log(n)) versions of EVAL and LINK, because it turns
      20             : /// out that the theoretically slower O(n*log(n)) implementation is actually
      21             : /// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs.
      22             : ///
      23             : /// The file uses the Depth Based Search algorithm to perform incremental
      24             : /// updates (insertion and deletions). The implemented algorithm is based on
      25             : /// this publication:
      26             : ///
      27             : ///   An Experimental Study of Dynamic Dominators
      28             : ///   Loukas Georgiadis, et al., April 12 2016, pp. 5-7, 9-10:
      29             : ///   https://arxiv.org/pdf/1604.02711.pdf
      30             : ///
      31             : //===----------------------------------------------------------------------===//
      32             : 
      33             : #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
      34             : #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
      35             : 
      36             : #include <queue>
      37             : #include "llvm/ADT/ArrayRef.h"
      38             : #include "llvm/ADT/DenseSet.h"
      39             : #include "llvm/ADT/DepthFirstIterator.h"
      40             : #include "llvm/ADT/PointerIntPair.h"
      41             : #include "llvm/ADT/SmallPtrSet.h"
      42             : #include "llvm/Support/Debug.h"
      43             : #include "llvm/Support/GenericDomTree.h"
      44             : 
      45             : #define DEBUG_TYPE "dom-tree-builder"
      46             : 
      47             : namespace llvm {
      48             : namespace DomTreeBuilder {
      49             : 
      50             : template <typename DomTreeT>
      51    11528361 : struct SemiNCAInfo {
      52             :   using NodePtr = typename DomTreeT::NodePtr;
      53             :   using NodeT = typename DomTreeT::NodeType;
      54             :   using TreeNodePtr = DomTreeNodeBase<NodeT> *;
      55             :   using RootsT = decltype(DomTreeT::Roots);
      56             :   static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
      57             : 
      58             :   // Information record used by Semi-NCA during tree construction.
      59    57520128 :   struct InfoRec {
      60             :     unsigned DFSNum = 0;
      61             :     unsigned Parent = 0;
      62             :     unsigned Semi = 0;
      63             :     NodePtr Label = nullptr;
      64             :     NodePtr IDom = nullptr;
      65             :     SmallVector<NodePtr, 2> ReverseChildren;
      66             :   };
      67             : 
      68             :   // Number to node mapping is 1-based. Initialize the mapping to start with
      69             :   // a dummy element.
      70             :   std::vector<NodePtr> NumToNode = {nullptr};
      71             :   DenseMap<NodePtr, InfoRec> NodeToInfo;
      72             : 
      73             :   using UpdateT = typename DomTreeT::UpdateType;
      74       43248 :   struct BatchUpdateInfo {
      75             :     SmallVector<UpdateT, 4> Updates;
      76             :     using NodePtrAndKind = PointerIntPair<NodePtr, 1, UpdateKind>;
      77             : 
      78             :     // In order to be able to walk a CFG that is out of sync with the CFG
      79             :     // DominatorTree last knew about, use the list of updates to reconstruct
      80             :     // previous CFG versions of the current CFG. For each node, we store a set
      81             :     // of its virtually added/deleted future successors and predecessors.
      82             :     // Note that these children are from the future relative to what the
      83             :     // DominatorTree knows about -- using them to gets us some snapshot of the
      84             :     // CFG from the past (relative to the state of the CFG).
      85             :     DenseMap<NodePtr, SmallDenseSet<NodePtrAndKind, 4>> FutureSuccessors;
      86             :     DenseMap<NodePtr, SmallDenseSet<NodePtrAndKind, 4>> FuturePredecessors;
      87             :     // Remembers if the whole tree was recalculated at some point during the
      88             :     // current batch update.
      89             :     bool IsRecalculated = false;
      90             :   };
      91             : 
      92             :   BatchUpdateInfo *BatchUpdates;
      93             :   using BatchUpdatePtr = BatchUpdateInfo *;
      94             : 
      95             :   // If BUI is a nullptr, then there's no batch update in progress.
      96    19213935 :   SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
      97             : 
      98       10036 :   void clear() {
      99       20072 :     NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
     100       10036 :     NodeToInfo.clear();
     101             :     // Don't reset the pointer to BatchUpdateInfo here -- if there's an update
     102             :     // in progress, we need this information to continue it.
     103       10036 :   }
     104             : 
     105             :   template <bool Inverse>
     106             :   struct ChildrenGetter {
     107             :     using ResultTy = SmallVector<NodePtr, 8>;
     108             : 
     109     5482929 :     static ResultTy Get(NodePtr N, std::integral_constant<bool, false>) {
     110    19584423 :       auto RChildren = reverse(children<NodePtr>(N));
     111    25067352 :       return ResultTy(RChildren.begin(), RChildren.end());
     112             :     }
     113             : 
     114      577554 :     static ResultTy Get(NodePtr N, std::integral_constant<bool, true>) {
     115     4742980 :       auto IChildren = inverse_children<NodePtr>(N);
     116     4742980 :       return ResultTy(IChildren.begin(), IChildren.end());
     117             :     }
     118             : 
     119             :     using Tag = std::integral_constant<bool, Inverse>;
     120             : 
     121             :     // The function below is the core part of the batch updater. It allows the
     122             :     // Depth Based Search algorithm to perform incremental updates in lockstep
     123             :     // with updates to the CFG. We emulated lockstep CFG updates by getting its
     124             :     // next snapshots by reverse-applying future updates.
     125    10727274 :     static ResultTy Get(NodePtr N, BatchUpdatePtr BUI) {
     126    15394065 :       ResultTy Res = Get(N, Tag());
     127             :       // If there's no batch update in progress, simply return node's children.
     128    10727274 :       if (!BUI) return Res;
     129             : 
     130             :       // CFG children are actually its *most current* children, and we have to
     131             :       // reverse-apply the future updates to get the node's children at the
     132             :       // point in time the update was performed.
     133      264757 :       auto &FutureChildren = (Inverse != IsPostDom) ? BUI->FuturePredecessors
     134             :                                                     : BUI->FutureSuccessors;
     135      264757 :       auto FCIt = FutureChildren.find(N);
     136      529514 :       if (FCIt == FutureChildren.end()) return Res;
     137             : 
     138       29578 :       for (auto ChildAndKind : FCIt->second) {
     139        3746 :         const NodePtr Child = ChildAndKind.getPointer();
     140        3746 :         const UpdateKind UK = ChildAndKind.getInt();
     141             : 
     142             :         // Reverse-apply the future update.
     143        3746 :         if (UK == UpdateKind::Insert) {
     144             :           // If there's an insertion in the future, it means that the edge must
     145             :           // exist in the current CFG, but was not present in it before.
     146             :           assert(llvm::find(Res, Child) != Res.end()
     147             :                  && "Expected child not found in the CFG");
     148       14544 :           Res.erase(std::remove(Res.begin(), Res.end(), Child), Res.end());
     149             :           DEBUG(dbgs() << "\tHiding edge " << BlockNamePrinter(N) << " -> "
     150             :                        << BlockNamePrinter(Child) << "\n");
     151             :         } else {
     152             :           // If there's an deletion in the future, it means that the edge cannot
     153             :           // exist in the current CFG, but existed in it before.
     154             :           assert(llvm::find(Res, Child) == Res.end() &&
     155             :                  "Unexpected child found in the CFG");
     156             :           DEBUG(dbgs() << "\tShowing virtual edge " << BlockNamePrinter(N)
     157             :                        << " -> " << BlockNamePrinter(Child) << "\n");
     158         110 :           Res.push_back(Child);
     159             :         }
     160             :       }
     161             : 
     162             :       return Res;
     163             :     }
     164             :   };
     165             : 
     166             :   NodePtr getIDom(NodePtr BB) const {
     167     5215430 :     auto InfoIt = NodeToInfo.find(BB);
     168    10430860 :     if (InfoIt == NodeToInfo.end()) return nullptr;
     169             : 
     170     5215430 :     return InfoIt->second.IDom;
     171             :   }
     172             : 
     173     5215430 :   TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT) {
     174    10430860 :     if (TreeNodePtr Node = DT.getNode(BB)) return Node;
     175             : 
     176             :     // Haven't calculated this node yet?  Get or calculate the node for the
     177             :     // immediate dominator.
     178           0 :     NodePtr IDom = getIDom(BB);
     179             : 
     180             :     assert(IDom || DT.DomTreeNodes[nullptr]);
     181           0 :     TreeNodePtr IDomNode = getNodeForBlock(IDom, DT);
     182             : 
     183             :     // Add a new tree node for this NodeT, and link it as a child of
     184             :     // IDomNode
     185           0 :     return (DT.DomTreeNodes[BB] = IDomNode->addChild(
     186             :         llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode)))
     187           0 :         .get();
     188             :   }
     189             : 
     190     5862784 :   static bool AlwaysDescend(NodePtr, NodePtr) { return true; }
     191             : 
     192             :   struct BlockNamePrinter {
     193             :     NodePtr N;
     194             : 
     195           0 :     BlockNamePrinter(NodePtr Block) : N(Block) {}
     196           0 :     BlockNamePrinter(TreeNodePtr TN) : N(TN ? TN->getBlock() : nullptr) {}
     197             : 
     198           0 :     friend raw_ostream &operator<<(raw_ostream &O, const BlockNamePrinter &BP) {
     199           0 :       if (!BP.N)
     200           0 :         O << "nullptr";
     201             :       else
     202           0 :         BP.N->printAsOperand(O, false);
     203             : 
     204           0 :       return O;
     205             :     }
     206             :   };
     207             : 
     208             :   // Custom DFS implementation which can skip nodes based on a provided
     209             :   // predicate. It also collects ReverseChildren so that we don't have to spend
     210             :   // time getting predecessors in SemiNCA.
     211             :   //
     212             :   // If IsReverse is set to true, the DFS walk will be performed backwards
     213             :   // relative to IsPostDom -- using reverse edges for dominators and forward
     214             :   // edges for postdominators.
     215             :   template <bool IsReverse = false, typename DescendCondition>
     216     3965104 :   unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,
     217             :                   unsigned AttachToNum) {
     218             :     assert(V);
     219    11895312 :     SmallVector<NodePtr, 64> WorkList = {V};
     220     3965104 :     if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum;
     221             : 
     222    14092785 :     while (!WorkList.empty()) {
     223    10127681 :       const NodePtr BB = WorkList.pop_back_val();
     224    20255362 :       auto &BBInfo = NodeToInfo[BB];
     225             : 
     226             :       // Visited nodes always have positive DFS numbers.
     227    10127681 :       if (BBInfo.DFSNum != 0) continue;
     228     9491067 :       BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
     229     9491067 :       BBInfo.Label = BB;
     230     9491067 :       NumToNode.push_back(BB);
     231             : 
     232     9491067 :       constexpr bool Direction = IsReverse != IsPostDom;  // XOR.
     233    45822202 :       for (const NodePtr Succ :
     234             :            ChildrenGetter<Direction>::Get(BB, BatchUpdates)) {
     235     7857934 :         const auto SIT = NodeToInfo.find(Succ);
     236             :         // Don't visit nodes more than once but remember to collect
     237             :         // ReverseChildren.
     238    25252411 :         if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
     239     1678609 :           if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
     240     3373966 :           continue;
     241             :         }
     242             : 
     243     6248982 :         if (!Condition(BB, Succ)) continue;
     244             : 
     245             :         // It's fine to add Succ to the map, because we know that it will be
     246             :         // visited later.
     247    12325154 :         auto &SuccInfo = NodeToInfo[Succ];
     248     6162577 :         WorkList.push_back(Succ);
     249     6162577 :         SuccInfo.Parent = LastNum;
     250     6162577 :         SuccInfo.ReverseChildren.push_back(BB);
     251             :       }
     252             :     }
     253             : 
     254     7930208 :     return LastNum;
     255             :   }
     256             : 
     257     6761722 :   NodePtr eval(NodePtr VIn, unsigned LastLinked) {
     258    13523444 :     auto &VInInfo = NodeToInfo[VIn];
     259     6761722 :     if (VInInfo.DFSNum < LastLinked)
     260     5442369 :       return VIn;
     261             : 
     262     1319353 :     SmallVector<NodePtr, 32> Work;
     263     2638706 :     SmallPtrSet<NodePtr, 32> Visited;
     264             : 
     265     1319353 :     if (VInInfo.Parent >= LastLinked)
     266      526511 :       Work.push_back(VIn);
     267             : 
     268     5658532 :     while (!Work.empty()) {
     269     8678358 :       NodePtr V = Work.back();
     270     8678358 :       auto &VInfo = NodeToInfo[V];
     271     8678358 :       NodePtr VAncestor = NumToNode[VInfo.Parent];
     272             : 
     273             :       // Process Ancestor first
     274     8678358 :       if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) {
     275     1906334 :         Work.push_back(VAncestor);
     276     4339179 :         continue;
     277             :       }
     278     2432845 :       Work.pop_back();
     279             : 
     280             :       // Update VInfo based on Ancestor info
     281     2432845 :       if (VInfo.Parent < LastLinked)
     282      526511 :         continue;
     283             : 
     284     3812668 :       auto &VAInfo = NodeToInfo[VAncestor];
     285     1906334 :       NodePtr VAncestorLabel = VAInfo.Label;
     286     1906334 :       NodePtr VLabel = VInfo.Label;
     287     5719002 :       if (NodeToInfo[VAncestorLabel].Semi < NodeToInfo[VLabel].Semi)
     288     1711779 :         VInfo.Label = VAncestorLabel;
     289     1906334 :       VInfo.Parent = VAInfo.Parent;
     290             :     }
     291             : 
     292     1319353 :     return VInInfo.Label;
     293             :   }
     294             : 
     295             :   // This function requires DFS to be run before calling it.
     296     3328925 :   void runSemiNCA(DomTreeT &DT, const unsigned MinLevel = 0) {
     297     6657850 :     const unsigned NextDFSNum(NumToNode.size());
     298             :     // Initialize IDoms to spanning tree parents.
     299    12092216 :     for (unsigned i = 1; i < NextDFSNum; ++i) {
     300    17526582 :       const NodePtr V = NumToNode[i];
     301    17526582 :       auto &VInfo = NodeToInfo[V];
     302    17526582 :       VInfo.IDom = NumToNode[VInfo.Parent];
     303             :     }
     304             : 
     305             :     // Step #1: Calculate the semidominators of all vertices.
     306     8763291 :     for (unsigned i = NextDFSNum - 1; i >= 2; --i) {
     307    10868732 :       NodePtr W = NumToNode[i];
     308    10868732 :       auto &WInfo = NodeToInfo[W];
     309             : 
     310             :       // Initialize the semi dominator to point to the parent node.
     311     5434366 :       WInfo.Semi = WInfo.Parent;
     312    23064820 :       for (const auto &N : WInfo.ReverseChildren) {
     313    13523444 :         if (NodeToInfo.count(N) == 0)  // Skip unreachable predecessors.
     314           0 :           continue;
     315             : 
     316    13523444 :         const TreeNodePtr TN = DT.getNode(N);
     317             :         // Skip predecessors whose level is above the subtree we are processing.
     318      624438 :         if (TN && TN->getLevel() < MinLevel)
     319           0 :           continue;
     320             : 
     321    13523444 :         unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi;
     322     8076145 :         if (SemiU < WInfo.Semi) WInfo.Semi = SemiU;
     323             :       }
     324             :     }
     325             : 
     326             :     // Step #2: Explicitly define the immediate dominator of each vertex.
     327             :     //          IDom[i] = NCA(SDom[i], SpanningTreeParent(i)).
     328             :     // Note that the parents were stored in IDoms and later got invalidated
     329             :     // during path compression in Eval.
     330    14197657 :     for (unsigned i = 2; i < NextDFSNum; ++i) {
     331    10868732 :       const NodePtr W = NumToNode[i];
     332    10868732 :       auto &WInfo = NodeToInfo[W];
     333    16303098 :       const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;
     334     5434366 :       NodePtr WIDomCandidate = WInfo.IDom;
     335    18723683 :       while (NodeToInfo[WIDomCandidate].DFSNum > SDomNum)
     336     5236634 :         WIDomCandidate = NodeToInfo[WIDomCandidate].IDom;
     337             : 
     338     5434366 :       WInfo.IDom = WIDomCandidate;
     339             :     }
     340     3328925 :   }
     341             : 
     342             :   // PostDominatorTree always has a virtual root that represents a virtual CFG
     343             :   // node that serves as a single exit from the function. All the other exits
     344             :   // (CFG nodes with terminators and nodes in infinite loops are logically
     345             :   // connected to this virtual CFG exit node).
     346             :   // This functions maps a nullptr CFG node to the virtual root tree node.
     347     1027919 :   void addVirtualRoot() {
     348             :     assert(IsPostDom && "Only postdominators have a virtual root");
     349             :     assert(NumToNode.size() == 1 && "SNCAInfo must be freshly constructed");
     350             : 
     351     2055838 :     auto &BBInfo = NodeToInfo[nullptr];
     352     1027919 :     BBInfo.DFSNum = BBInfo.Semi = 1;
     353     1027919 :     BBInfo.Label = nullptr;
     354             : 
     355     2055838 :     NumToNode.push_back(nullptr);  // NumToNode[1] = nullptr;
     356     1027919 :   }
     357             : 
     358             :   // For postdominators, nodes with no forward successors are trivial roots that
     359             :   // are always selected as tree roots. Roots with forward successors correspond
     360             :   // to CFG nodes within infinite loops.
     361     1166862 :   static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI) {
     362             :     assert(N && "N must be a valid node");
     363     2333724 :     return !ChildrenGetter<false>::Get(N, BUI).empty();
     364             :   }
     365             : 
     366             :   static NodePtr GetEntryNode(const DomTreeT &DT) {
     367             :     assert(DT.Parent && "Parent not set");
     368     5620826 :     return GraphTraits<typename DomTreeT::ParentPtr>::getEntryNode(DT.Parent);
     369             :   }
     370             : 
     371             :   // Finds all roots without relaying on the set of roots already stored in the
     372             :   // tree.
     373             :   // We define roots to be some non-redundant set of the CFG nodes
     374      512014 :   static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI) {
     375             :     assert(DT.Parent && "Parent pointer is not set");
     376     3322137 :     RootsT Roots;
     377             : 
     378             :     // For dominators, function entry CFG node is always a tree root node.
     379             :     if (!IsPostDom) {
     380     5620246 :       Roots.push_back(GetEntryNode(DT));
     381             :       return Roots;
     382             :     }
     383             : 
     384     1024028 :     SemiNCAInfo SNCA(BUI);
     385             : 
     386             :     // PostDominatorTree always has a virtual root.
     387      512014 :     SNCA.addVirtualRoot();
     388      512014 :     unsigned Num = 1;
     389             : 
     390             :     DEBUG(dbgs() << "\t\tLooking for trivial roots\n");
     391             : 
     392             :     // Step #1: Find all the trivial roots that are going to will definitely
     393             :     // remain tree roots.
     394      512014 :     unsigned Total = 0;
     395             :     // It may happen that there are some new nodes in the CFG that are result of
     396             :     // the ongoing batch update, but we cannot really pretend that they don't
     397             :     // exist -- we won't see any outgoing or incoming edges to them, so it's
     398             :     // fine to discover them here, as they would end up appearing in the CFG at
     399             :     // some point anyway.
     400     3864354 :     for (const NodePtr N : nodes(DT.Parent)) {
     401     1164156 :       ++Total;
     402             :       // If it has no *successors*, it is definitely a root.
     403     1164156 :       if (!HasForwardSuccessors(N, BUI)) {
     404      563326 :         Roots.push_back(N);
     405             :         // Run DFS not to walk this part of CFG later.
     406      563326 :         Num = SNCA.runDFS(N, Num, AlwaysDescend, 1);
     407             :         DEBUG(dbgs() << "Found a new trivial root: " << BlockNamePrinter(N)
     408             :                      << "\n");
     409             :         DEBUG(dbgs() << "Last visited node: "
     410             :                      << BlockNamePrinter(SNCA.NumToNode[Num]) << "\n");
     411             :       }
     412             :     }
     413             : 
     414             :     DEBUG(dbgs() << "\t\tLooking for non-trivial roots\n");
     415             : 
     416             :     // Step #2: Find all non-trivial root candidates. Those are CFG nodes that
     417             :     // are reverse-unreachable were not visited by previous DFS walks (i.e. CFG
     418             :     // nodes in infinite loops).
     419      512014 :     bool HasNonTrivialRoots = false;
     420             :     // Accounting for the virtual exit, see if we had any reverse-unreachable
     421             :     // nodes.
     422      512014 :     if (Total + 1 != Num) {
     423        1163 :       HasNonTrivialRoots = true;
     424             :       // Make another DFS pass over all other nodes to find the
     425             :       // reverse-unreachable blocks, and find the furthest paths we'll be able
     426             :       // to make.
     427             :       // Note that this looks N^2, but it's really 2N worst case, if every node
     428             :       // is unreachable. This is because we are still going to only visit each
     429             :       // unreachable node once, we may just visit it in two directions,
     430             :       // depending on how lucky we get.
     431        2326 :       SmallPtrSet<NodePtr, 4> ConnectToExitBlock;
     432       16543 :       for (const NodePtr I : nodes(DT.Parent)) {
     433        5258 :         if (SNCA.NodeToInfo.count(I) == 0) {
     434             :           DEBUG(dbgs() << "\t\t\tVisiting node " << BlockNamePrinter(I)
     435             :                        << "\n");
     436             :           // Find the furthest away we can get by following successors, then
     437             :           // follow them in reverse.  This gives us some reasonable answer about
     438             :           // the post-dom tree inside any infinite loop. In particular, it
     439             :           // guarantees we get to the farthest away point along *some*
     440             :           // path. This also matches the GCC's behavior.
     441             :           // If we really wanted a totally complete picture of dominance inside
     442             :           // this infinite loop, we could do it with SCC-like algorithms to find
     443             :           // the lowest and highest points in the infinite loop.  In theory, it
     444             :           // would be nice to give the canonical backedge for the loop, but it's
     445             :           // expensive and does not always lead to a minimal set of roots.
     446             :           DEBUG(dbgs() << "\t\t\tRunning forward DFS\n");
     447             : 
     448        1269 :           const unsigned NewNum = SNCA.runDFS<true>(I, Num, AlwaysDescend, Num);
     449        2538 :           const NodePtr FurthestAway = SNCA.NumToNode[NewNum];
     450             :           DEBUG(dbgs() << "\t\t\tFound a new furthest away node "
     451             :                        << "(non-trivial root): "
     452             :                        << BlockNamePrinter(FurthestAway) << "\n");
     453        1269 :           ConnectToExitBlock.insert(FurthestAway);
     454        1269 :           Roots.push_back(FurthestAway);
     455             :           DEBUG(dbgs() << "\t\t\tPrev DFSNum: " << Num << ", new DFSNum: "
     456             :                        << NewNum << "\n\t\t\tRemoving DFS info\n");
     457        5089 :           for (unsigned i = NewNum; i > Num; --i) {
     458        7640 :             const NodePtr N = SNCA.NumToNode[i];
     459             :             DEBUG(dbgs() << "\t\t\t\tRemoving DFS info for "
     460             :                          << BlockNamePrinter(N) << "\n");
     461        3820 :             SNCA.NodeToInfo.erase(N);
     462        3820 :             SNCA.NumToNode.pop_back();
     463             :           }
     464        1269 :           const unsigned PrevNum = Num;
     465             :           DEBUG(dbgs() << "\t\t\tRunning reverse DFS\n");
     466        1269 :           Num = SNCA.runDFS(FurthestAway, Num, AlwaysDescend, 1);
     467        1269 :           for (unsigned i = PrevNum + 1; i <= Num; ++i)
     468             :             DEBUG(dbgs() << "\t\t\t\tfound node "
     469             :                          << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
     470             :         }
     471             :       }
     472             :     }
     473             : 
     474             :     DEBUG(dbgs() << "Total: " << Total << ", Num: " << Num << "\n");
     475             :     DEBUG(dbgs() << "Discovered CFG nodes:\n");
     476             :     DEBUG(for (size_t i = 0; i <= Num; ++i) dbgs()
     477             :           << i << ": " << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
     478             : 
     479             :     assert((Total + 1 == Num) && "Everything should have been visited");
     480             : 
     481             :     // Step #3: If we found some non-trivial roots, make them non-redundant.
     482        1163 :     if (HasNonTrivialRoots) RemoveRedundantRoots(DT, BUI, Roots);
     483             : 
     484             :     DEBUG(dbgs() << "Found roots: ");
     485             :     DEBUG(for (auto *Root : Roots) dbgs() << BlockNamePrinter(Root) << " ");
     486             :     DEBUG(dbgs() << "\n");
     487             : 
     488             :     return Roots;
     489             :   }
     490             : 
     491             :   // This function only makes sense for postdominators.
     492             :   // We define roots to be some set of CFG nodes where (reverse) DFS walks have
     493             :   // to start in order to visit all the CFG nodes (including the
     494             :   // reverse-unreachable ones).
     495             :   // When the search for non-trivial roots is done it may happen that some of
     496             :   // the non-trivial roots are reverse-reachable from other non-trivial roots,
     497             :   // which makes them redundant. This function removes them from the set of
     498             :   // input roots.
     499        1163 :   static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI,
     500             :                                    RootsT &Roots) {
     501             :     assert(IsPostDom && "This function is for postdominators only");
     502             :     DEBUG(dbgs() << "Removing redundant roots\n");
     503             : 
     504        2326 :     SemiNCAInfo SNCA(BUI);
     505             : 
     506        6578 :     for (unsigned i = 0; i < Roots.size(); ++i) {
     507        4252 :       auto &Root = Roots[i];
     508             :       // Trivial roots are always non-redundant.
     509        2126 :       if (!HasForwardSuccessors(Root, BUI)) continue;
     510             :       DEBUG(dbgs() << "\tChecking if " << BlockNamePrinter(Root)
     511             :                    << " remains a root\n");
     512        1269 :       SNCA.clear();
     513             :       // Do a forward walk looking for the other roots.
     514        1269 :       const unsigned Num = SNCA.runDFS<true>(Root, 0, AlwaysDescend, 0);
     515             :       // Skip the start node and begin from the second one (note that DFS uses
     516             :       // 1-based indexing).
     517        2305 :       for (unsigned x = 2; x <= Num; ++x) {
     518        2208 :         const NodePtr N = SNCA.NumToNode[x];
     519             :         // If we wound another root in a (forward) DFS walk, remove the current
     520             :         // root from the set of roots, as it is reverse-reachable from the other
     521             :         // one.
     522        1104 :         if (llvm::find(Roots, N) != Roots.end()) {
     523             :           DEBUG(dbgs() << "\tForward DFS walk found another root "
     524             :                        << BlockNamePrinter(N) << "\n\tRemoving root "
     525             :                        << BlockNamePrinter(Root) << "\n");
     526         204 :           std::swap(Root, Roots.back());
     527         136 :           Roots.pop_back();
     528             : 
     529             :           // Root at the back takes the current root's place.
     530             :           // Start the next loop iteration with the same index.
     531          68 :           --i;
     532          68 :           break;
     533             :         }
     534             :       }
     535             :     }
     536        1163 :   }
     537             : 
     538             :   template <typename DescendCondition>
     539      515905 :   void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
     540             :     if (!IsPostDom) {
     541             :       assert(DT.Roots.size() == 1 && "Dominators should have a singe root");
     542     5628510 :       runDFS(DT.Roots[0], 0, DC, 0);
     543             :       return;
     544             :     }
     545             : 
     546      515905 :     addVirtualRoot();
     547      515905 :     unsigned Num = 1;
     548     1547715 :     for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0);
     549             :   }
     550             : 
     551     3321540 :   static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) {
     552     3321540 :     auto *Parent = DT.Parent;
     553     3321540 :     DT.reset();
     554     3321540 :     DT.Parent = Parent;
     555     6643080 :     SemiNCAInfo SNCA(nullptr);  // Since we are rebuilding the whole tree,
     556             :                                 // there's no point doing it incrementally.
     557             : 
     558             :     // Step #0: Number blocks in depth-first order and initialize variables used
     559             :     // in later stages of the algorithm.
     560    12774453 :     DT.Roots = FindRoots(DT, nullptr);
     561     3321540 :     SNCA.doFullDFSWalk(DT, AlwaysDescend);
     562             : 
     563     3321540 :     SNCA.runSemiNCA(DT);
     564     3321540 :     if (BUI) {
     565        1889 :       BUI->IsRecalculated = true;
     566             :       DEBUG(dbgs() << "DomTree recalculated, skipping future batch updates\n");
     567             :     }
     568             : 
     569     3321540 :     if (DT.Roots.empty()) return;
     570             : 
     571             :     // Add a node for the root. If the tree is a PostDominatorTree it will be
     572             :     // the virtual exit (denoted by (BasicBlock *) nullptr) which postdominates
     573             :     // all real exits (including multiple exit blocks, infinite loops).
     574     6131373 :     NodePtr Root = IsPostDom ? nullptr : DT.Roots[0];
     575             : 
     576    16607700 :     DT.RootNode = (DT.DomTreeNodes[Root] =
     577             :                        llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
     578             :         .get();
     579     3321540 :     SNCA.attachNewSubtree(DT, DT.RootNode);
     580             :   }
     581             : 
     582     3325019 :   void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {
     583             :     // Attach the first unreachable block to AttachTo.
     584    11920554 :     NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
     585             :     // Loop over all of the discovered blocks in the function...
     586    15187008 :     for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
     587    17073940 :       NodePtr W = NumToNode[i];
     588             :       DEBUG(dbgs() << "\tdiscovered a new reachable node "
     589             :                    << BlockNamePrinter(W) << "\n");
     590             : 
     591             :       // Don't replace this with 'count', the insertion side effect is important
     592    25610910 :       if (DT.DomTreeNodes[W]) continue;  // Haven't calculated this node yet?
     593             : 
     594    10430860 :       NodePtr ImmDom = getIDom(W);
     595             : 
     596             :       // Get or calculate the node for the immediate dominator.
     597     5215430 :       TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
     598             : 
     599             :       // Add a new tree node for this BasicBlock, and link it as a child of
     600             :       // IDomNode.
     601    31292580 :       DT.DomTreeNodes[W] = IDomNode->addChild(
     602             :           llvm::make_unique<DomTreeNodeBase<NodeT>>(W, IDomNode));
     603             :     }
     604     3325019 :   }
     605             : 
     606        3906 :   void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) {
     607       15624 :     NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
     608      234133 :     for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
     609      452642 :       const NodePtr N = NumToNode[i];
     610      452642 :       const TreeNodePtr TN = DT.getNode(N);
     611             :       assert(TN);
     612      678963 :       const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom);
     613      226321 :       TN->setIDom(NewIDom);
     614             :     }
     615        3906 :   }
     616             : 
     617             :   // Helper struct used during edge insertions.
     618       49200 :   struct InsertionInfo {
     619             :     using BucketElementTy = std::pair<unsigned, TreeNodePtr>;
     620             :     struct DecreasingLevel {
     621             :       bool operator()(const BucketElementTy &First,
     622             :                       const BucketElementTy &Second) const {
     623             :         return First.first > Second.first;
     624             :       }
     625             :     };
     626             : 
     627             :     std::priority_queue<BucketElementTy, SmallVector<BucketElementTy, 8>,
     628             :         DecreasingLevel>
     629             :         Bucket;  // Queue of tree nodes sorted by level in descending order.
     630             :     SmallDenseSet<TreeNodePtr, 8> Affected;
     631             :     SmallDenseSet<TreeNodePtr, 8> Visited;
     632             :     SmallVector<TreeNodePtr, 8> AffectedQueue;
     633             :     SmallVector<TreeNodePtr, 8> VisitedNotAffectedQueue;
     634             :   };
     635             : 
     636       11148 :   static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
     637             :                          const NodePtr From, const NodePtr To) {
     638             :     assert((From || IsPostDom) &&
     639             :            "From has to be a valid CFG node or a virtual root");
     640             :     assert(To && "Cannot be a nullptr");
     641             :     DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> "
     642             :                  << BlockNamePrinter(To) << "\n");
     643       22296 :     TreeNodePtr FromTN = DT.getNode(From);
     644             : 
     645       11058 :     if (!FromTN) {
     646             :       // Ignore edges from unreachable nodes for (forward) dominators.
     647             :       if (!IsPostDom) return;
     648             : 
     649             :       // The unreachable node becomes a new root -- a tree node for it.
     650           3 :       TreeNodePtr VirtualRoot = DT.getNode(nullptr);
     651           3 :       FromTN =
     652          18 :           (DT.DomTreeNodes[From] = VirtualRoot->addChild(
     653             :                llvm::make_unique<DomTreeNodeBase<NodeT>>(From, VirtualRoot)))
     654             :               .get();
     655           3 :       DT.Roots.push_back(From);
     656             :     }
     657             : 
     658       11061 :     DT.DFSInfoValid = false;
     659             : 
     660       11061 :     const TreeNodePtr ToTN = DT.getNode(To);
     661        7582 :     if (!ToTN)
     662        3479 :       InsertUnreachable(DT, BUI, FromTN, To);
     663             :     else
     664        7582 :       InsertReachable(DT, BUI, FromTN, ToTN);
     665             :   }
     666             : 
     667             :   // Determines if some existing root becomes reverse-reachable after the
     668             :   // insertion. Rebuilds the whole tree if that situation happens.
     669         202 :   static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
     670             :                                          const TreeNodePtr From,
     671             :                                          const TreeNodePtr To) {
     672             :     assert(IsPostDom && "This function is only for postdominators");
     673             :     // Destination node is not attached to the virtual root, so it cannot be a
     674             :     // root.
     675         299 :     if (!DT.isVirtualRoot(To->getIDom())) return false;
     676             : 
     677         194 :     auto RIt = llvm::find(DT.Roots, To->getBlock());
     678          97 :     if (RIt == DT.Roots.end())
     679             :       return false;  // To is not a root, nothing to update.
     680             : 
     681             :     DEBUG(dbgs() << "\t\tAfter the insertion, " << BlockNamePrinter(To)
     682             :                  << " is no longer a root\n\t\tRebuilding the tree!!!\n");
     683             : 
     684          82 :     CalculateFromScratch(DT, BUI);
     685             :     return true;
     686             :   }
     687             : 
     688             :   // Updates the set of roots after insertion or deletion. This ensures that
     689             :   // roots are the same when after a series of updates and when the tree would
     690             :   // be built from scratch.
     691         205 :   static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI) {
     692             :     assert(IsPostDom && "This function is only for postdominators");
     693             : 
     694             :     // The tree has only trivial roots -- nothing to update.
     695         820 :     if (std::none_of(DT.Roots.begin(), DT.Roots.end(), [BUI](const NodePtr N) {
     696             :           return HasForwardSuccessors(N, BUI);
     697         580 :         }))
     698             :       return;
     699             : 
     700             :     // Recalculate the set of roots.
     701          66 :     DT.Roots = FindRoots(DT, BUI);
     702          66 :     for (const NodePtr R : DT.Roots) {
     703          22 :       const TreeNodePtr TN = DT.getNode(R);
     704             :       // A CFG node was selected as a tree root, but the corresponding tree node
     705             :       // is not connected to the virtual root. This is because the incremental
     706             :       // algorithm does not really know or use the set of roots and can make a
     707             :       // different (implicit) decision about which nodes within an infinite loop
     708             :       // becomes a root.
     709          44 :       if (DT.isVirtualRoot(TN->getIDom())) {
     710             :         DEBUG(dbgs() << "Root " << BlockNamePrinter(R)
     711             :                      << " is not virtual root's child\n"
     712             :                      << "The entire tree needs to be rebuilt\n");
     713             :         // It should be possible to rotate the subtree instead of recalculating
     714             :         // the whole tree, but this situation happens extremely rarely in
     715             :         // practice.
     716          22 :         CalculateFromScratch(DT, BUI);
     717          22 :         return;
     718             :       }
     719             :     }
     720             :   }
     721             : 
     722             :   // Handles insertion to a node already in the dominator tree.
     723        7750 :   static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
     724             :                               const TreeNodePtr From, const TreeNodePtr To) {
     725             :     DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock())
     726             :                  << " -> " << BlockNamePrinter(To->getBlock()) << "\n");
     727        3852 :     if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return;
     728             :     // DT.findNCD expects both pointers to be valid. When From is a virtual
     729             :     // root, then its CFG block pointer is a nullptr, so we have to 'compute'
     730             :     // the NCD manually.
     731        7668 :     const NodePtr NCDBlock =
     732       22908 :         (From->getBlock() && To->getBlock())
     733       15288 :             ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock())
     734             :             : nullptr;
     735             :     assert(NCDBlock || DT.isPostDominator());
     736        7668 :     const TreeNodePtr NCD = DT.getNode(NCDBlock);
     737             :     assert(NCD);
     738             : 
     739             :     DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n");
     740       15336 :     const TreeNodePtr ToIDom = To->getIDom();
     741             : 
     742             :     // Nothing affected -- NCA property holds.
     743             :     // (Based on the lemma 2.5 from the second paper.)
     744        7668 :     if (NCD == To || NCD == ToIDom) return;
     745             : 
     746             :     // Identify and collect affected nodes.
     747        8200 :     InsertionInfo II;
     748             :     DEBUG(dbgs() << "Marking " << BlockNamePrinter(To) << " as affected\n");
     749        4100 :     II.Affected.insert(To);
     750        8200 :     const unsigned ToLevel = To->getLevel();
     751             :     DEBUG(dbgs() << "Putting " << BlockNamePrinter(To) << " into a Bucket\n");
     752        8200 :     II.Bucket.push({ToLevel, To});
     753             : 
     754       13150 :     while (!II.Bucket.empty()) {
     755        4525 :       const TreeNodePtr CurrentNode = II.Bucket.top().second;
     756        4525 :       II.Bucket.pop();
     757             :       DEBUG(dbgs() << "\tAdding to Visited and AffectedQueue: "
     758             :                    << BlockNamePrinter(CurrentNode) << "\n");
     759        4525 :       II.Visited.insert(CurrentNode);
     760        4525 :       II.AffectedQueue.push_back(CurrentNode);
     761             : 
     762             :       // Discover and collect affected successors of the current node.
     763        9050 :       VisitInsertion(DT, BUI, CurrentNode, CurrentNode->getLevel(), NCD, II);
     764             :     }
     765             : 
     766             :     // Finish by updating immediate dominators and levels.
     767        4100 :     UpdateInsertion(DT, BUI, NCD, II);
     768             :   }
     769             : 
     770             :   // Visits an affected node and collect its affected successors.
     771        4525 :   static void VisitInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
     772             :                              const TreeNodePtr TN, const unsigned RootLevel,
     773             :                              const TreeNodePtr NCD, InsertionInfo &II) {
     774        4525 :     const unsigned NCDLevel = NCD->getLevel();
     775             :     DEBUG(dbgs() << "Visiting " << BlockNamePrinter(TN) << "\n");
     776             : 
     777       13575 :     SmallVector<TreeNodePtr, 8> Stack = {TN};
     778             :     assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!");
     779             : 
     780             :     do {
     781       64174 :       TreeNodePtr Next = Stack.pop_back_val();
     782             : 
     783      343426 :       for (const NodePtr Succ :
     784             :            ChildrenGetter<IsPostDom>::Get(Next->getBlock(), BUI)) {
     785       86730 :         const TreeNodePtr SuccTN = DT.getNode(Succ);
     786             :         assert(SuccTN && "Unreachable successor found at reachable insertion");
     787      173460 :         const unsigned SuccLevel = SuccTN->getLevel();
     788             : 
     789             :         DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
     790             :                      << ", level = " << SuccLevel << "\n");
     791             : 
     792             :         // Succ dominated by subtree From -- not affected.
     793             :         // (Based on the lemma 2.5 from the second paper.)
     794       86730 :         if (SuccLevel > RootLevel) {
     795             :           DEBUG(dbgs() << "\t\tDominated by subtree From\n");
     796      164120 :           if (II.Visited.count(SuccTN) != 0)
     797       22411 :             continue;
     798             : 
     799             :           DEBUG(dbgs() << "\t\tMarking visited not affected "
     800             :                        << BlockNamePrinter(Succ) << "\n");
     801      119298 :           II.Visited.insert(SuccTN);
     802       59649 :           II.VisitedNotAffectedQueue.push_back(SuccTN);
     803       59649 :           Stack.push_back(SuccTN);
     804        4670 :         } else if ((SuccLevel > NCDLevel + 1) &&
     805        1280 :             II.Affected.count(SuccTN) == 0) {
     806             :           DEBUG(dbgs() << "\t\tMarking affected and adding "
     807             :                        << BlockNamePrinter(Succ) << " to a Bucket\n");
     808         850 :           II.Affected.insert(SuccTN);
     809        1275 :           II.Bucket.push({SuccLevel, SuccTN});
     810             :         }
     811             :       }
     812       64174 :     } while (!Stack.empty());
     813        4525 :   }
     814             : 
     815             :   // Updates immediate dominators and levels after insertion.
     816        4100 :   static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
     817             :                               const TreeNodePtr NCD, InsertionInfo &II) {
     818             :     DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n");
     819             : 
     820       16825 :     for (const TreeNodePtr TN : II.AffectedQueue) {
     821             :       DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN)
     822             :                    << ") = " << BlockNamePrinter(NCD) << "\n");
     823        4525 :       TN->setIDom(NCD);
     824             :     }
     825             : 
     826        4100 :     UpdateLevelsAfterInsertion(II);
     827          84 :     if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
     828        4100 :   }
     829             : 
     830             :   static void UpdateLevelsAfterInsertion(InsertionInfo &II) {
     831             :     DEBUG(dbgs() << "Updating levels for visited but not affected nodes\n");
     832             : 
     833       71949 :     for (const TreeNodePtr TN : II.VisitedNotAffectedQueue) {
     834             :       DEBUG(dbgs() << "\tlevel(" << BlockNamePrinter(TN) << ") = ("
     835             :                    << BlockNamePrinter(TN->getIDom()) << ") "
     836             :                    << TN->getIDom()->getLevel() << " + 1\n");
     837       59649 :       TN->UpdateLevel();
     838             :     }
     839             :   }
     840             : 
     841             :   // Handles insertion to previously unreachable nodes.
     842        3479 :   static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
     843             :                                 const TreeNodePtr From, const NodePtr To) {
     844             :     DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From)
     845             :                  << " -> (unreachable) " << BlockNamePrinter(To) << "\n");
     846             : 
     847             :     // Collect discovered edges to already reachable nodes.
     848        6958 :     SmallVector<std::pair<NodePtr, TreeNodePtr>, 8> DiscoveredEdgesToReachable;
     849             :     // Discover and connect nodes that became reachable with the insertion.
     850        3479 :     ComputeUnreachableDominators(DT, BUI, To, From, DiscoveredEdgesToReachable);
     851             : 
     852             :     DEBUG(dbgs() << "Inserted " << BlockNamePrinter(From)
     853             :                  << " -> (prev unreachable) " << BlockNamePrinter(To) << "\n");
     854             : 
     855             :     // Used the discovered edges and inset discovered connecting (incoming)
     856             :     // edges.
     857       10557 :     for (const auto &Edge : DiscoveredEdgesToReachable) {
     858             :       DEBUG(dbgs() << "\tInserting discovered connecting edge "
     859             :                    << BlockNamePrinter(Edge.first) << " -> "
     860             :                    << BlockNamePrinter(Edge.second) << "\n");
     861         240 :       InsertReachable(DT, BUI, DT.getNode(Edge.first), Edge.second);
     862             :     }
     863        3479 :   }
     864             : 
     865             :   // Connects nodes that become reachable with an insertion.
     866        3479 :   static void ComputeUnreachableDominators(
     867             :       DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root,
     868             :       const TreeNodePtr Incoming,
     869             :       SmallVectorImpl<std::pair<NodePtr, TreeNodePtr>>
     870             :           &DiscoveredConnectingEdges) {
     871             :     assert(!DT.getNode(Root) && "Root must not be reachable");
     872             : 
     873             :     // Visit only previously unreachable nodes.
     874        3479 :     auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From,
     875         793 :                                                                   NodePtr To) {
     876         673 :       const TreeNodePtr ToTN = DT.getNode(To);
     877         120 :       if (!ToTN) return true;
     878             : 
     879         240 :       DiscoveredConnectingEdges.push_back({From, ToTN});
     880         120 :       return false;
     881             :     };
     882             : 
     883        6958 :     SemiNCAInfo SNCA(BUI);
     884        3479 :     SNCA.runDFS(Root, 0, UnreachableDescender, 0);
     885        3479 :     SNCA.runSemiNCA(DT);
     886        3479 :     SNCA.attachNewSubtree(DT, Incoming);
     887             : 
     888             :     DEBUG(dbgs() << "After adding unreachable nodes\n");
     889        3479 :   }
     890             : 
     891        6534 :   static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
     892             :                          const NodePtr From, const NodePtr To) {
     893             :     assert(From && To && "Cannot disconnect nullptrs");
     894             :     DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> "
     895             :                  << BlockNamePrinter(To) << "\n");
     896             : 
     897             : #ifndef NDEBUG
     898             :     // Ensure that the edge was in fact deleted from the CFG before informing
     899             :     // the DomTree about it.
     900             :     // The check is O(N), so run it only in debug configuration.
     901             :     auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) {
     902             :       auto Successors = ChildrenGetter<IsPostDom>::Get(Of, BUI);
     903             :       return llvm::find(Successors, SuccCandidate) != Successors.end();
     904             :     };
     905             :     (void)IsSuccessor;
     906             :     assert(!IsSuccessor(To, From) && "Deleted edge still exists in the CFG!");
     907             : #endif
     908             : 
     909        6534 :     const TreeNodePtr FromTN = DT.getNode(From);
     910             :     // Deletion in an unreachable subtree -- nothing to do.
     911        6501 :     if (!FromTN) return;
     912             : 
     913        6501 :     const TreeNodePtr ToTN = DT.getNode(To);
     914        6501 :     if (!ToTN) {
     915             :       DEBUG(dbgs() << "\tTo (" << BlockNamePrinter(To)
     916             :                    << ") already unreachable -- there is no edge to delete\n");
     917             :       return;
     918             :     }
     919             : 
     920        6501 :     const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);
     921        6501 :     const TreeNodePtr NCD = DT.getNode(NCDBlock);
     922             : 
     923             :     // To dominates From -- nothing to do.
     924        6501 :     if (ToTN == NCD) return;
     925             : 
     926        6414 :     const TreeNodePtr ToIDom = ToTN->getIDom();
     927             :     DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
     928             :                  << BlockNamePrinter(ToIDom) << "\n");
     929             : 
     930             :     // To remains reachable after deletion.
     931             :     // (Based on the caption under Figure 4. from the second paper.)
     932        6414 :     if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN))
     933        6109 :       DeleteReachable(DT, BUI, FromTN, ToTN);
     934             :     else
     935         305 :       DeleteUnreachable(DT, BUI, ToTN);
     936             : 
     937         121 :     if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
     938             :   }
     939             : 
     940             :   // Handles deletions that leave destination nodes reachable.
     941        6109 :   static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
     942             :                               const TreeNodePtr FromTN,
     943             :                               const TreeNodePtr ToTN) {
     944             :     DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN) << " -> "
     945             :                  << BlockNamePrinter(ToTN) << "\n");
     946             :     DEBUG(dbgs() << "\tRebuilding subtree\n");
     947             : 
     948             :     // Find the top of the subtree that needs to be rebuilt.
     949             :     // (Based on the lemma 2.6 from the second paper.)
     950       12218 :     const NodePtr ToIDom =
     951             :         DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock());
     952             :     assert(ToIDom || DT.isPostDominator());
     953        6109 :     const TreeNodePtr ToIDomTN = DT.getNode(ToIDom);
     954             :     assert(ToIDomTN);
     955        6109 :     const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom();
     956             :     // Top of the subtree to rebuild is the root node. Rebuild the tree from
     957             :     // scratch.
     958        6109 :     if (!PrevIDomSubTree) {
     959             :       DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
     960        2350 :       CalculateFromScratch(DT, BUI);
     961        2350 :       return;
     962             :     }
     963             : 
     964             :     // Only visit nodes in the subtree starting at To.
     965        3759 :     const unsigned Level = ToIDomTN->getLevel();
     966      526433 :     auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {
     967      522674 :       return DT.getNode(To)->getLevel() > Level;
     968      261337 :     };
     969             : 
     970             :     DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN) << "\n");
     971             : 
     972        7518 :     SemiNCAInfo SNCA(BUI);
     973        3759 :     SNCA.runDFS(ToIDom, 0, DescendBelow, 0);
     974             :     DEBUG(dbgs() << "\tRunning Semi-NCA\n");
     975        3759 :     SNCA.runSemiNCA(DT, Level);
     976        3759 :     SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
     977             :   }
     978             : 
     979             :   // Checks if a node has proper support, as defined on the page 3 and later
     980             :   // explained on the page 7 of the second paper.
     981        5171 :   static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI,
     982             :                                const TreeNodePtr TN) {
     983             :     DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN) << "\n");
     984       15963 :     for (const NodePtr Pred :
     985             :          ChildrenGetter<!IsPostDom>::Get(TN->getBlock(), BUI)) {
     986             :       DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
     987        5011 :       if (!DT.getNode(Pred)) continue;
     988             : 
     989        5011 :       const NodePtr Support =
     990             :           DT.findNearestCommonDominator(TN->getBlock(), Pred);
     991             :       DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
     992        5011 :       if (Support != TN->getBlock()) {
     993             :         DEBUG(dbgs() << "\t" << BlockNamePrinter(TN)
     994             :                      << " is reachable from support "
     995             :                      << BlockNamePrinter(Support) << "\n");
     996        4866 :         return true;
     997             :       }
     998             :     }
     999             : 
    1000         305 :     return false;
    1001             :   }
    1002             : 
    1003             :   // Handle deletions that make destination node unreachable.
    1004             :   // (Based on the lemma 2.7 from the second paper.)
    1005         305 :   static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
    1006             :                                 const TreeNodePtr ToTN) {
    1007             :     DEBUG(dbgs() << "Deleting unreachable subtree " << BlockNamePrinter(ToTN)
    1008             :                  << "\n");
    1009             :     assert(ToTN);
    1010             :     assert(ToTN->getBlock());
    1011             : 
    1012             :     if (IsPostDom) {
    1013             :       // Deletion makes a region reverse-unreachable and creates a new root.
    1014             :       // Simulate that by inserting an edge from the virtual root to ToTN and
    1015             :       // adding it as a new root.
    1016             :       DEBUG(dbgs() << "\tDeletion made a region reverse-unreachable\n");
    1017             :       DEBUG(dbgs() << "\tAdding new root " << BlockNamePrinter(ToTN) << "\n");
    1018          96 :       DT.Roots.push_back(ToTN->getBlock());
    1019          48 :       InsertReachable(DT, BUI, DT.getNode(nullptr), ToTN);
    1020         110 :       return;
    1021             :     }
    1022             : 
    1023         404 :     SmallVector<NodePtr, 16> AffectedQueue;
    1024         257 :     const unsigned Level = ToTN->getLevel();
    1025             : 
    1026             :     // Traverse destination node's descendants with greater level in the tree
    1027             :     // and collect visited nodes.
    1028        1353 :     auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
    1029         878 :       const TreeNodePtr TN = DT.getNode(To);
    1030             :       assert(TN);
    1031         878 :       if (TN->getLevel() > Level) return true;
    1032         218 :       if (llvm::find(AffectedQueue, To) == AffectedQueue.end())
    1033         199 :         AffectedQueue.push_back(To);
    1034             : 
    1035             :       return false;
    1036             :     };
    1037             : 
    1038         404 :     SemiNCAInfo SNCA(BUI);
    1039         257 :     unsigned LastDFSNum =
    1040             :         SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0);
    1041             : 
    1042         257 :     TreeNodePtr MinNode = ToTN;
    1043             : 
    1044             :     // Identify the top of the subtree to rebuild by finding the NCD of all
    1045             :     // the affected nodes.
    1046         970 :     for (const NodePtr N : AffectedQueue) {
    1047         199 :       const TreeNodePtr TN = DT.getNode(N);
    1048         398 :       const NodePtr NCDBlock =
    1049             :           DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock());
    1050             :       assert(NCDBlock || DT.isPostDominator());
    1051         199 :       const TreeNodePtr NCD = DT.getNode(NCDBlock);
    1052             :       assert(NCD);
    1053             : 
    1054             :       DEBUG(dbgs() << "Processing affected node " << BlockNamePrinter(TN)
    1055             :                    << " with NCD = " << BlockNamePrinter(NCD)
    1056             :                    << ", MinNode =" << BlockNamePrinter(MinNode) << "\n");
    1057         591 :       if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD;
    1058             :     }
    1059             : 
    1060             :     // Root reached, rebuild the whole tree from scratch.
    1061         257 :     if (!MinNode->getIDom()) {
    1062             :       DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
    1063          47 :       CalculateFromScratch(DT, BUI);
    1064          47 :       return;
    1065             :     }
    1066             : 
    1067             :     // Erase the unreachable subtree in reverse preorder to process all children
    1068             :     // before deleting their parent.
    1069        1042 :     for (unsigned i = LastDFSNum; i > 0; --i) {
    1070         832 :       const NodePtr N = SNCA.NumToNode[i];
    1071         416 :       const TreeNodePtr TN = DT.getNode(N);
    1072             :       DEBUG(dbgs() << "Erasing node " << BlockNamePrinter(TN) << "\n");
    1073             : 
    1074         416 :       EraseNode(DT, TN);
    1075             :     }
    1076             : 
    1077             :     // The affected subtree start at the To node -- there's no extra work to do.
    1078         210 :     if (MinNode == ToTN) return;
    1079             : 
    1080             :     DEBUG(dbgs() << "DeleteUnreachable: running DFS with MinNode = "
    1081             :                  << BlockNamePrinter(MinNode) << "\n");
    1082         147 :     const unsigned MinLevel = MinNode->getLevel();
    1083         147 :     const TreeNodePtr PrevIDom = MinNode->getIDom();
    1084             :     assert(PrevIDom);
    1085         147 :     SNCA.clear();
    1086             : 
    1087             :     // Identify nodes that remain in the affected subtree.
    1088        2513 :     auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) {
    1089        1183 :       const TreeNodePtr ToTN = DT.getNode(To);
    1090        3549 :       return ToTN && ToTN->getLevel() > MinLevel;
    1091             :     };
    1092         147 :     SNCA.runDFS(MinNode->getBlock(), 0, DescendBelow, 0);
    1093             : 
    1094             :     DEBUG(dbgs() << "Previous IDom(MinNode) = " << BlockNamePrinter(PrevIDom)
    1095             :                  << "\nRunning Semi-NCA\n");
    1096             : 
    1097             :     // Rebuild the remaining part of affected subtree.
    1098         147 :     SNCA.runSemiNCA(DT, MinLevel);
    1099         147 :     SNCA.reattachExistingSubtree(DT, PrevIDom);
    1100             :   }
    1101             : 
    1102             :   // Removes leaf tree nodes from the dominator tree.
    1103         416 :   static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
    1104             :     assert(TN);
    1105             :     assert(TN->getNumChildren() == 0 && "Not a tree leaf");
    1106             : 
    1107         832 :     const TreeNodePtr IDom = TN->getIDom();
    1108             :     assert(IDom);
    1109             : 
    1110         832 :     auto ChIt = llvm::find(IDom->Children, TN);
    1111             :     assert(ChIt != IDom->Children.end());
    1112        1248 :     std::swap(*ChIt, IDom->Children.back());
    1113         416 :     IDom->Children.pop_back();
    1114             : 
    1115         832 :     DT.DomTreeNodes.erase(TN->getBlock());
    1116         416 :   }
    1117             : 
    1118             :   //~~
    1119             :   //===--------------------- DomTree Batch Updater --------------------------===
    1120             :   //~~
    1121             : 
    1122        5406 :   static void ApplyUpdates(DomTreeT &DT, ArrayRef<UpdateT> Updates) {
    1123       10812 :     BatchUpdateInfo BUI;
    1124        5406 :     LegalizeUpdates(Updates, BUI.Updates);
    1125             : 
    1126        5406 :     const size_t NumLegalized = BUI.Updates.size();
    1127        5406 :     BUI.FutureSuccessors.reserve(NumLegalized);
    1128        5406 :     BUI.FuturePredecessors.reserve(NumLegalized);
    1129             : 
    1130             :     // Use the legalized future updates to initialize future successors and
    1131             :     // predecessors. Note that these sets will only decrease size over time, as
    1132             :     // the next CFG snapshots slowly approach the actual (current) CFG.
    1133       32477 :     for (UpdateT &U : BUI.Updates) {
    1134       97554 :       BUI.FutureSuccessors[U.getFrom()].insert({U.getTo(), U.getKind()});
    1135       97554 :       BUI.FuturePredecessors[U.getTo()].insert({U.getFrom(), U.getKind()});
    1136             :     }
    1137             : 
    1138             :     DEBUG(dbgs() << "About to apply " << NumLegalized << " updates\n");
    1139             :     DEBUG(if (NumLegalized < 32) for (const auto &U
    1140             :                                       : reverse(BUI.Updates)) dbgs()
    1141             :           << '\t' << U << "\n");
    1142             :     DEBUG(dbgs() << "\n");
    1143             : 
    1144             :     // If the DominatorTree was recalculated at some point, stop the batch
    1145             :     // updates. Full recalculations ignore batch updates and look at the actual
    1146             :     // CFG.
    1147       37582 :     for (size_t i = 0; i < NumLegalized && !BUI.IsRecalculated; ++i)
    1148       16088 :       ApplyNextUpdate(DT, BUI);
    1149        5406 :   }
    1150             : 
    1151             :   // This function serves double purpose:
    1152             :   // a) It removes redundant updates, which makes it easier to reverse-apply
    1153             :   //    them when traversing CFG.
    1154             :   // b) It optimizes away updates that cancel each other out, as the end result
    1155             :   //    is the same.
    1156             :   //
    1157             :   // It relies on the property of the incremental updates that says that the
    1158             :   // order of updates doesn't matter. This allows us to reorder them and end up
    1159             :   // with the exact same DomTree every time.
    1160             :   //
    1161             :   // Following the same logic, the function doesn't care about the order of
    1162             :   // input updates, so it's OK to pass it an unordered sequence of updates, that
    1163             :   // doesn't make sense when applied sequentially, eg. performing double
    1164             :   // insertions or deletions and then doing an opposite update.
    1165             :   //
    1166             :   // In the future, it should be possible to schedule updates in way that
    1167             :   // minimizes the amount of work needed done during incremental updates.
    1168        5408 :   static void LegalizeUpdates(ArrayRef<UpdateT> AllUpdates,
    1169             :                               SmallVectorImpl<UpdateT> &Result) {
    1170             :     DEBUG(dbgs() << "Legalizing " << AllUpdates.size() << " updates\n");
    1171             :     // Count the total number of inserions of each edge.
    1172             :     // Each insertion adds 1 and deletion subtracts 1. The end number should be
    1173             :     // one of {-1 (deletion), 0 (NOP), +1 (insertion)}. Otherwise, the sequence
    1174             :     // of updates contains multiple updates of the same kind and we assert for
    1175             :     // that case.
    1176       10816 :     SmallDenseMap<std::pair<NodePtr, NodePtr>, int, 4> Operations;
    1177        5408 :     Operations.reserve(AllUpdates.size());
    1178             : 
    1179       27089 :     for (const auto &U : AllUpdates) {
    1180       16273 :       NodePtr From = U.getFrom();
    1181       16273 :       NodePtr To = U.getTo();
    1182         241 :       if (IsPostDom) std::swap(From, To);  // Reverse edge for postdominators.
    1183             : 
    1184       48819 :       Operations[{From, To}] += (U.getKind() == UpdateKind::Insert ? 1 : -1);
    1185             :     }
    1186             : 
    1187        5408 :     Result.clear();
    1188        5408 :     Result.reserve(Operations.size());
    1189       48758 :     for (auto &Op : Operations) {
    1190       16267 :       const int NumInsertions = Op.second;
    1191             :       assert(std::abs(NumInsertions) <= 1 && "Unbalanced operations!");
    1192       16267 :       if (NumInsertions == 0) continue;
    1193       16265 :       const UpdateKind UK =
    1194             :           NumInsertions > 0 ? UpdateKind::Insert : UpdateKind::Delete;
    1195       32530 :       Result.push_back({UK, Op.first.first, Op.first.second});
    1196             :     }
    1197             : 
    1198             :     // Make the order consistent by not relying on pointer values within the
    1199             :     // set. Reuse the old Operations map.
    1200             :     // In the future, we should sort by something else to minimize the amount
    1201             :     // of work needed to perform the series of updates.
    1202       21681 :     for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) {
    1203       32546 :       const auto &U = AllUpdates[i];
    1204             :       if (!IsPostDom)
    1205       64128 :         Operations[{U.getFrom(), U.getTo()}] = int(i);
    1206             :       else
    1207         957 :         Operations[{U.getTo(), U.getFrom()}] = int(i);
    1208             :     }
    1209             : 
    1210       21632 :     std::sort(Result.begin(), Result.end(),
    1211       58839 :               [&Operations](const UpdateT &A, const UpdateT &B) {
    1212      117678 :                 return Operations[{A.getFrom(), A.getTo()}] >
    1213       98065 :                        Operations[{B.getFrom(), B.getTo()}];
    1214       39226 :               });
    1215        5408 :   }
    1216             : 
    1217       16088 :   static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) {
    1218             :     assert(!BUI.Updates.empty() && "No updates to apply!");
    1219       32176 :     UpdateT CurrentUpdate = BUI.Updates.pop_back_val();
    1220             :     DEBUG(dbgs() << "Applying update: " << CurrentUpdate << "\n");
    1221             : 
    1222             :     // Move to the next snapshot of the CFG by removing the reverse-applied
    1223             :     // current update.
    1224       32176 :     auto &FS = BUI.FutureSuccessors[CurrentUpdate.getFrom()];
    1225       80440 :     FS.erase({CurrentUpdate.getTo(), CurrentUpdate.getKind()});
    1226       32176 :     if (FS.empty()) BUI.FutureSuccessors.erase(CurrentUpdate.getFrom());
    1227             : 
    1228       32176 :     auto &FP = BUI.FuturePredecessors[CurrentUpdate.getTo()];
    1229       64352 :     FP.erase({CurrentUpdate.getFrom(), CurrentUpdate.getKind()});
    1230       44820 :     if (FP.empty()) BUI.FuturePredecessors.erase(CurrentUpdate.getTo());
    1231             : 
    1232       16088 :     if (CurrentUpdate.getKind() == UpdateKind::Insert)
    1233       10734 :       InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
    1234             :     else
    1235        5354 :       DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
    1236       16088 :   }
    1237             : 
    1238             :   //~~
    1239             :   //===--------------- DomTree correctness verification ---------------------===
    1240             :   //~~
    1241             : 
    1242             :   // Check if the tree has correct roots. A DominatorTree always has a single
    1243             :   // root which is the function's entry node. A PostDominatorTree can have
    1244             :   // multiple roots - one for each node with no successors and for infinite
    1245             :   // loops.
    1246         575 :   bool verifyRoots(const DomTreeT &DT) {
    1247         575 :     if (!DT.Parent && !DT.Roots.empty()) {
    1248           0 :       errs() << "Tree has no parent but has roots!\n";
    1249           0 :       errs().flush();
    1250             :       return false;
    1251             :     }
    1252             : 
    1253             :     if (!IsPostDom) {
    1254         290 :       if (DT.Roots.empty()) {
    1255           0 :         errs() << "Tree doesn't have a root!\n";
    1256           0 :         errs().flush();
    1257             :         return false;
    1258             :       }
    1259             : 
    1260         580 :       if (DT.getRoot() != GetEntryNode(DT)) {
    1261           0 :         errs() << "Tree's root is not its parent's entry node!\n";
    1262           0 :         errs().flush();
    1263             :         return false;
    1264             :       }
    1265             :     }
    1266             : 
    1267         865 :     RootsT ComputedRoots = FindRoots(DT, nullptr);
    1268        2300 :     if (DT.Roots.size() != ComputedRoots.size() ||
    1269        1150 :         !std::is_permutation(DT.Roots.begin(), DT.Roots.end(),
    1270             :                              ComputedRoots.begin())) {
    1271           0 :       errs() << "Tree has different roots than freshly computed ones!\n";
    1272           0 :       errs() << "\tPDT roots: ";
    1273           0 :       for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", ";
    1274           0 :       errs() << "\n\tComputed roots: ";
    1275           0 :       for (const NodePtr N : ComputedRoots)
    1276           0 :         errs() << BlockNamePrinter(N) << ", ";
    1277           0 :       errs() << "\n";
    1278           0 :       errs().flush();
    1279             :       return false;
    1280             :     }
    1281             : 
    1282             :     return true;
    1283             :   }
    1284             : 
    1285             :   // Checks if the tree contains all reachable nodes in the input graph.
    1286         575 :   bool verifyReachability(const DomTreeT &DT) {
    1287         575 :     clear();
    1288         575 :     doFullDFSWalk(DT, AlwaysDescend);
    1289             : 
    1290        1150 :     for (auto &NodeToTN : DT.DomTreeNodes) {
    1291       12272 :       const TreeNodePtr TN = NodeToTN.second.get();
    1292        6136 :       const NodePtr BB = TN->getBlock();
    1293             : 
    1294             :       // Virtual root has a corresponding virtual CFG node.
    1295        2843 :       if (DT.isVirtualRoot(TN)) continue;
    1296             : 
    1297       11702 :       if (NodeToInfo.count(BB) == 0) {
    1298           0 :         errs() << "DomTree node " << BlockNamePrinter(BB)
    1299             :                << " not found by DFS walk!\n";
    1300           0 :         errs().flush();
    1301             : 
    1302           0 :         return false;
    1303             :       }
    1304             :     }
    1305             : 
    1306        9011 :     for (const NodePtr N : NumToNode) {
    1307       12562 :       if (N && !DT.getNode(N)) {
    1308           0 :         errs() << "CFG node " << BlockNamePrinter(N)
    1309             :                << " not found in the DomTree!\n";
    1310           0 :         errs().flush();
    1311             : 
    1312             :         return false;
    1313             :       }
    1314             :     }
    1315             : 
    1316             :     return true;
    1317             :   }
    1318             : 
    1319             :   // Check if for every parent with a level L in the tree all of its children
    1320             :   // have level L + 1.
    1321         575 :   static bool VerifyLevels(const DomTreeT &DT) {
    1322        1150 :     for (auto &NodeToTN : DT.DomTreeNodes) {
    1323       12272 :       const TreeNodePtr TN = NodeToTN.second.get();
    1324        6136 :       const NodePtr BB = TN->getBlock();
    1325        6136 :       if (!BB) continue;
    1326             : 
    1327        5851 :       const TreeNodePtr IDom = TN->getIDom();
    1328        6141 :       if (!IDom && TN->getLevel() != 0) {
    1329           0 :         errs() << "Node without an IDom " << BlockNamePrinter(BB)
    1330           0 :                << " has a nonzero level " << TN->getLevel() << "!\n";
    1331           0 :         errs().flush();
    1332             : 
    1333           0 :         return false;
    1334             :       }
    1335             : 
    1336       16973 :       if (IDom && TN->getLevel() != IDom->getLevel() + 1) {
    1337           0 :         errs() << "Node " << BlockNamePrinter(BB) << " has level "
    1338           0 :                << TN->getLevel() << " while its IDom "
    1339           0 :                << BlockNamePrinter(IDom->getBlock()) << " has level "
    1340           0 :                << IDom->getLevel() << "!\n";
    1341           0 :         errs().flush();
    1342             : 
    1343             :         return false;
    1344             :       }
    1345             :     }
    1346             : 
    1347         575 :     return true;
    1348             :   }
    1349             : 
    1350             :   // Checks if for every edge From -> To in the graph
    1351             :   //     NCD(From, To) == IDom(To) or To.
    1352         575 :   bool verifyNCD(const DomTreeT &DT) {
    1353         575 :     clear();
    1354         575 :     doFullDFSWalk(DT, AlwaysDescend);
    1355             : 
    1356        7861 :     for (auto &BlockToInfo : NodeToInfo) {
    1357        6136 :       auto &Info = BlockToInfo.second;
    1358             : 
    1359       12272 :       const NodePtr From = NumToNode[Info.Parent];
    1360        6136 :       if (!From) continue;
    1361             : 
    1362        4687 :       const NodePtr To = BlockToInfo.first;
    1363        4687 :       const TreeNodePtr ToTN = DT.getNode(To);
    1364             :       assert(ToTN);
    1365             : 
    1366        4687 :       const NodePtr NCD = DT.findNearestCommonDominator(From, To);
    1367        4687 :       const TreeNodePtr NCDTN = DT.getNode(NCD);
    1368        4687 :       const TreeNodePtr ToIDom = ToTN->getIDom();
    1369        4687 :       if (NCDTN != ToTN && NCDTN != ToIDom) {
    1370           0 :         errs() << "NearestCommonDominator verification failed:\n\tNCD(From:"
    1371           0 :                << BlockNamePrinter(From) << ", To:" << BlockNamePrinter(To)
    1372           0 :                << ") = " << BlockNamePrinter(NCD)
    1373           0 :                << ",\t (should be To or IDom[To]: " << BlockNamePrinter(ToIDom)
    1374             :                << ")\n";
    1375           0 :         errs().flush();
    1376             : 
    1377           0 :         return false;
    1378             :       }
    1379             :     }
    1380             : 
    1381         575 :     return true;
    1382             :   }
    1383             : 
    1384             :   // The below routines verify the correctness of the dominator tree relative to
    1385             :   // the CFG it's coming from.  A tree is a dominator tree iff it has two
    1386             :   // properties, called the parent property and the sibling property.  Tarjan
    1387             :   // and Lengauer prove (but don't explicitly name) the properties as part of
    1388             :   // the proofs in their 1972 paper, but the proofs are mostly part of proving
    1389             :   // things about semidominators and idoms, and some of them are simply asserted
    1390             :   // based on even earlier papers (see, e.g., lemma 2).  Some papers refer to
    1391             :   // these properties as "valid" and "co-valid".  See, e.g., "Dominators,
    1392             :   // directed bipolar orders, and independent spanning trees" by Loukas
    1393             :   // Georgiadis and Robert E. Tarjan, as well as "Dominator Tree Verification
    1394             :   // and Vertex-Disjoint Paths " by the same authors.
    1395             : 
    1396             :   // A very simple and direct explanation of these properties can be found in
    1397             :   // "An Experimental Study of Dynamic Dominators", found at
    1398             :   // https://arxiv.org/abs/1604.02711
    1399             : 
    1400             :   // The easiest way to think of the parent property is that it's a requirement
    1401             :   // of being a dominator.  Let's just take immediate dominators.  For PARENT to
    1402             :   // be an immediate dominator of CHILD, all paths in the CFG must go through
    1403             :   // PARENT before they hit CHILD.  This implies that if you were to cut PARENT
    1404             :   // out of the CFG, there should be no paths to CHILD that are reachable.  If
    1405             :   // there are, then you now have a path from PARENT to CHILD that goes around
    1406             :   // PARENT and still reaches CHILD, which by definition, means PARENT can't be
    1407             :   // a dominator of CHILD (let alone an immediate one).
    1408             : 
    1409             :   // The sibling property is similar.  It says that for each pair of sibling
    1410             :   // nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each
    1411             :   // other.  If sibling LEFT dominated sibling RIGHT, it means there are no
    1412             :   // paths in the CFG from sibling LEFT to sibling RIGHT that do not go through
    1413             :   // LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of
    1414             :   // RIGHT, not a sibling.
    1415             : 
    1416             :   // It is possible to verify the parent and sibling properties in
    1417             :   // linear time, but the algorithms are complex. Instead, we do it in a
    1418             :   // straightforward N^2 and N^3 way below, using direct path reachability.
    1419             : 
    1420             : 
    1421             :   // Checks if the tree has the parent property: if for all edges from V to W in
    1422             :   // the input graph, such that V is reachable, the parent of W in the tree is
    1423             :   // an ancestor of V in the tree.
    1424             :   //
    1425             :   // This means that if a node gets disconnected from the graph, then all of
    1426             :   // the nodes it dominated previously will now become unreachable.
    1427         575 :   bool verifyParentProperty(const DomTreeT &DT) {
    1428        1150 :     for (auto &NodeToTN : DT.DomTreeNodes) {
    1429       12272 :       const TreeNodePtr TN = NodeToTN.second.get();
    1430        6136 :       const NodePtr BB = TN->getBlock();
    1431       11987 :       if (!BB || TN->getChildren().empty()) continue;
    1432             : 
    1433             :       DEBUG(dbgs() << "Verifying parent property of node "
    1434             :                    << BlockNamePrinter(TN) << "\n");
    1435        3201 :       clear();
    1436       24485 :       doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) {
    1437       19710 :         return From != BB && To != BB;
    1438       19710 :       });
    1439             : 
    1440       17073 :       for (TreeNodePtr Child : TN->getChildren())
    1441       12807 :         if (NodeToInfo.count(Child->getBlock()) != 0) {
    1442           0 :           errs() << "Child " << BlockNamePrinter(Child)
    1443           0 :                  << " reachable after its parent " << BlockNamePrinter(BB)
    1444             :                  << " is removed!\n";
    1445           0 :           errs().flush();
    1446             : 
    1447           0 :           return false;
    1448             :         }
    1449             :     }
    1450             : 
    1451         575 :     return true;
    1452             :   }
    1453             : 
    1454             :   // Check if the tree has sibling property: if a node V does not dominate a
    1455             :   // node W for all siblings V and W in the tree.
    1456             :   //
    1457             :   // This means that if a node gets disconnected from the graph, then all of its
    1458             :   // siblings will now still be reachable.
    1459         575 :   bool verifySiblingProperty(const DomTreeT &DT) {
    1460        1150 :     for (auto &NodeToTN : DT.DomTreeNodes) {
    1461       12272 :       const TreeNodePtr TN = NodeToTN.second.get();
    1462        6136 :       const NodePtr BB = TN->getBlock();
    1463       11987 :       if (!BB || TN->getChildren().empty()) continue;
    1464             : 
    1465             :       const auto &Siblings = TN->getChildren();
    1466        7470 :       for (const TreeNodePtr N : Siblings) {
    1467        4269 :         clear();
    1468        4269 :         NodePtr BBN = N->getBlock();
    1469       39736 :         doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) {
    1470       33199 :           return From != BBN && To != BBN;
    1471       33199 :         });
    1472             : 
    1473       23995 :         for (const TreeNodePtr S : Siblings) {
    1474        6919 :           if (S == N) continue;
    1475             : 
    1476        7950 :           if (NodeToInfo.count(S->getBlock()) == 0) {
    1477           0 :             errs() << "Node " << BlockNamePrinter(S)
    1478           0 :                    << " not reachable when its sibling " << BlockNamePrinter(N)
    1479             :                    << " is removed!\n";
    1480           0 :             errs().flush();
    1481             : 
    1482           0 :             return false;
    1483             :           }
    1484             :         }
    1485             :       }
    1486             :     }
    1487             : 
    1488         575 :     return true;
    1489             :   }
    1490             : };
    1491             : 
    1492             : template <class DomTreeT>
    1493     1939517 : void Calculate(DomTreeT &DT) {
    1494     3319039 :   SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, nullptr);
    1495     1939517 : }
    1496             : 
    1497             : template <class DomTreeT>
    1498         414 : void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
    1499             :                 typename DomTreeT::NodePtr To) {
    1500         414 :   if (DT.isPostDominator()) std::swap(From, To);
    1501         414 :   SemiNCAInfo<DomTreeT>::InsertEdge(DT, nullptr, From, To);
    1502         414 : }
    1503             : 
    1504             : template <class DomTreeT>
    1505        1180 : void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
    1506             :                 typename DomTreeT::NodePtr To) {
    1507        1180 :   if (DT.isPostDominator()) std::swap(From, To);
    1508        1180 :   SemiNCAInfo<DomTreeT>::DeleteEdge(DT, nullptr, From, To);
    1509        1180 : }
    1510             : 
    1511             : template <class DomTreeT>
    1512        5406 : void ApplyUpdates(DomTreeT &DT,
    1513             :                   ArrayRef<typename DomTreeT::UpdateType> Updates) {
    1514        5406 :   SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, Updates);
    1515        5406 : }
    1516             : 
    1517             : template <class DomTreeT>
    1518         575 : bool Verify(const DomTreeT &DT) {
    1519        1150 :   SemiNCAInfo<DomTreeT> SNCA(nullptr);
    1520        1150 :   return SNCA.verifyRoots(DT) && SNCA.verifyReachability(DT) &&
    1521         575 :          SNCA.VerifyLevels(DT) && SNCA.verifyNCD(DT) &&
    1522        1725 :          SNCA.verifyParentProperty(DT) && SNCA.verifySiblingProperty(DT);
    1523             : }
    1524             : 
    1525             : }  // namespace DomTreeBuilder
    1526             : }  // namespace llvm
    1527             : 
    1528             : #undef DEBUG_TYPE
    1529             : 
    1530             : #endif

Generated by: LCOV version 1.13