LCOV - code coverage report
Current view: top level - include/llvm/Support - GenericDomTreeConstruction.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 436 533 81.8 %
Date: 2018-07-13 00:08:38 Functions: 158 253 62.5 %
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    10185294 : 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    31820717 :   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       67074 :   struct BatchUpdateInfo {
      75             :     SmallVector<UpdateT, 4> Updates;
      76             :     using NodePtrAndKind = PointerIntPair<NodePtr, 1, UpdateKind>;
      77             : 
      78             :     // In order to be able to walk a CFG that is out of sync with the CFG
      79             :     // DominatorTree last knew about, use the list of updates to reconstruct
      80             :     // previous CFG versions of the current CFG. For each node, we store a set
      81             :     // of its virtually added/deleted future successors and predecessors.
      82             :     // Note that these children are from the future relative to what the
      83             :     // DominatorTree knows about -- using them to gets us some snapshot of the
      84             :     // CFG from the past (relative to the state of the CFG).
      85             :     DenseMap<NodePtr, SmallVector<NodePtrAndKind, 4>> FutureSuccessors;
      86             :     DenseMap<NodePtr, SmallVector<NodePtrAndKind, 4>> FuturePredecessors;
      87             :     // Remembers if the whole tree was recalculated at some point during the
      88             :     // current batch update.
      89             :     bool IsRecalculated = false;
      90             :   };
      91             : 
      92             :   BatchUpdateInfo *BatchUpdates;
      93             :   using BatchUpdatePtr = BatchUpdateInfo *;
      94             : 
      95             :   // If BUI is a nullptr, then there's no batch update in progress.
      96    15277941 :   SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
      97             : 
      98       17180 :   void clear() {
      99       17180 :     NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
     100       17180 :     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       17180 :   }
     104             : 
     105             :   template <bool Inverse>
     106             :   struct ChildrenGetter {
     107             :     using ResultTy = SmallVector<NodePtr, 8>;
     108             : 
     109     8263141 :     static ResultTy Get(NodePtr N, std::integral_constant<bool, false>) {
     110     8263141 :       auto RChildren = reverse(children<NodePtr>(N));
     111     8263141 :       return ResultTy(RChildren.begin(), RChildren.end());
     112             :     }
     113             : 
     114      712767 :     static ResultTy Get(NodePtr N, std::integral_constant<bool, true>) {
     115             :       auto IChildren = inverse_children<NodePtr>(N);
     116      712767 :       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    14643271 :     static ResultTy Get(NodePtr N, BatchUpdatePtr BUI) {
     126     8975908 :       ResultTy Res = Get(N, Tag());
     127             :       // If there's no batch update in progress, simply return node's children.
     128    14643271 :       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     2446851 :       auto &FutureChildren = (Inverse != IsPostDom) ? BUI->FuturePredecessors
     134             :                                                     : BUI->FutureSuccessors;
     135     2446851 :       auto FCIt = FutureChildren.find(N);
     136     2446851 :       if (FCIt == FutureChildren.end()) return Res;
     137             : 
     138     2179510 :       for (auto ChildAndKind : FCIt->second) {
     139      827271 :         const NodePtr Child = ChildAndKind.getPointer();
     140             :         const UpdateKind UK = ChildAndKind.getInt();
     141             : 
     142             :         // Reverse-apply the future update.
     143      827271 :         if (UK == UpdateKind::Insert) {
     144             :           // If there's an insertion in the future, it means that the edge must
     145             :           // exist in the current CFG, but was not present in it before.
     146             :           assert(llvm::find(Res, Child) != Res.end()
     147             :                  && "Expected child not found in the CFG");
     148             :           Res.erase(std::remove(Res.begin(), Res.end(), Child), Res.end());
     149             :           LLVM_DEBUG(dbgs() << "\tHiding edge " << BlockNamePrinter(N) << " -> "
     150             :                             << BlockNamePrinter(Child) << "\n");
     151             :         } else {
     152             :           // If there's an deletion in the future, it means that the edge cannot
     153             :           // exist in the current CFG, but existed in it before.
     154             :           assert(llvm::find(Res, Child) == Res.end() &&
     155             :                  "Unexpected child found in the CFG");
     156             :           LLVM_DEBUG(dbgs() << "\tShowing virtual edge " << BlockNamePrinter(N)
     157             :                             << " -> " << BlockNamePrinter(Child) << "\n");
     158      511229 :           Res.push_back(Child);
     159             :         }
     160             :       }
     161             : 
     162             :       return Res;
     163             :     }
     164             :   };
     165             : 
     166             :   NodePtr getIDom(NodePtr BB) const {
     167     6149960 :     auto InfoIt = NodeToInfo.find(BB);
     168     6149960 :     if (InfoIt == NodeToInfo.end()) return nullptr;
     169             : 
     170     6149960 :     return InfoIt->second.IDom;
     171             :   }
     172             : 
     173     6149960 :   TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT) {
     174    12299920 :     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             :         .get();
     188             :   }
     189             : 
     190     6157094 :   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     5231385 :   unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,
     217             :                   unsigned AttachToNum) {
     218             :     assert(V);
     219    10462770 :     SmallVector<NodePtr, 64> WorkList = {V};
     220     5231385 :     if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum;
     221             : 
     222    19021027 :     while (!WorkList.empty()) {
     223    13789642 :       const NodePtr BB = WorkList.pop_back_val();
     224             :       auto &BBInfo = NodeToInfo[BB];
     225             : 
     226             :       // Visited nodes always have positive DFS numbers.
     227    13789640 :       if (BBInfo.DFSNum != 0) continue;
     228    12990510 :       BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
     229    12990510 :       BBInfo.Label = BB;
     230    12990510 :       NumToNode.push_back(BB);
     231             : 
     232             :       constexpr bool Direction = IsReverse != IsPostDom;  // XOR.
     233    47899338 :       for (const NodePtr Succ :
     234             :            ChildrenGetter<Direction>::Get(BB, BatchUpdates)) {
     235    10959157 :         const auto SIT = NodeToInfo.find(Succ);
     236             :         // Don't visit nodes more than once but remember to collect
     237             :         // ReverseChildren.
     238    13275600 :         if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
     239     2316443 :           if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
     240     4717343 :           continue;
     241             :         }
     242             : 
     243     8782338 :         if (!Condition(BB, Succ)) continue;
     244             : 
     245             :         // It's fine to add Succ to the map, because we know that it will be
     246             :         // visited later.
     247             :         auto &SuccInfo = NodeToInfo[Succ];
     248     8558257 :         WorkList.push_back(Succ);
     249     8558257 :         SuccInfo.Parent = LastNum;
     250     8558257 :         SuccInfo.ReverseChildren.push_back(BB);
     251             :       }
     252             :     }
     253             : 
     254     5231385 :     return LastNum;
     255             :   }
     256             : 
     257     8995750 :   NodePtr eval(NodePtr VIn, unsigned LastLinked) {
     258     8995750 :     auto &VInInfo = NodeToInfo[VIn];
     259     8995750 :     if (VInInfo.DFSNum < LastLinked)
     260     7226222 :       return VIn;
     261             : 
     262             :     SmallVector<NodePtr, 32> Work;
     263             :     SmallPtrSet<NodePtr, 32> Visited;
     264             : 
     265     1769528 :     if (VInInfo.Parent >= LastLinked)
     266      712211 :       Work.push_back(VIn);
     267             : 
     268     7589593 :     while (!Work.empty()) {
     269     5820065 :       NodePtr V = Work.back();
     270             :       auto &VInfo = NodeToInfo[V];
     271    11640130 :       NodePtr VAncestor = NumToNode[VInfo.Parent];
     272             : 
     273             :       // Process Ancestor first
     274    11640130 :       if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) {
     275     2553927 :         Work.push_back(VAncestor);
     276     5820065 :         continue;
     277             :       }
     278             :       Work.pop_back();
     279             : 
     280             :       // Update VInfo based on Ancestor info
     281     3266138 :       if (VInfo.Parent < LastLinked)
     282      712211 :         continue;
     283             : 
     284             :       auto &VAInfo = NodeToInfo[VAncestor];
     285     2553927 :       NodePtr VAncestorLabel = VAInfo.Label;
     286     2553927 :       NodePtr VLabel = VInfo.Label;
     287     5107854 :       if (NodeToInfo[VAncestorLabel].Semi < NodeToInfo[VLabel].Semi)
     288     2330533 :         VInfo.Label = VAncestorLabel;
     289     2553927 :       VInfo.Parent = VAInfo.Parent;
     290             :     }
     291             : 
     292     1769528 :     return VInInfo.Label;
     293             :   }
     294             : 
     295             :   // This function requires DFS to be run before calling it.
     296     4381448 :   void runSemiNCA(DomTreeT &DT, const unsigned MinLevel = 0) {
     297     8762896 :     const unsigned NextDFSNum(NumToNode.size());
     298             :     // Initialize IDoms to spanning tree parents.
     299    27701308 :     for (unsigned i = 1; i < NextDFSNum; ++i) {
     300    23319860 :       const NodePtr V = NumToNode[i];
     301    11659930 :       auto &VInfo = NodeToInfo[V];
     302    23319860 :       VInfo.IDom = NumToNode[VInfo.Parent];
     303             :     }
     304             : 
     305             :     // Step #1: Calculate the semidominators of all vertices.
     306    11659930 :     for (unsigned i = NextDFSNum - 1; i >= 2; --i) {
     307    14556964 :       NodePtr W = NumToNode[i];
     308     7278482 :       auto &WInfo = NodeToInfo[W];
     309             : 
     310             :       // Initialize the semi dominator to point to the parent node.
     311     7278482 :       WInfo.Semi = WInfo.Parent;
     312    25269982 :       for (const auto &N : WInfo.ReverseChildren) {
     313     8995750 :         if (NodeToInfo.count(N) == 0)  // Skip unreachable predecessors.
     314           0 :           continue;
     315             : 
     316     8995750 :         const TreeNodePtr TN = DT.getNode(N);
     317             :         // Skip predecessors whose level is above the subtree we are processing.
     318     3118046 :         if (TN && TN->getLevel() < MinLevel)
     319           0 :           continue;
     320             : 
     321    17991500 :         unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi;
     322    10635415 :         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    18938412 :     for (unsigned i = 2; i < NextDFSNum; ++i) {
     331    14556964 :       const NodePtr W = NumToNode[i];
     332     7278482 :       auto &WInfo = NodeToInfo[W];
     333    14556964 :       const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;
     334     7278482 :       NodePtr WIDomCandidate = WInfo.IDom;
     335    14061392 :       while (NodeToInfo[WIDomCandidate].DFSNum > SDomNum)
     336     3391455 :         WIDomCandidate = NodeToInfo[WIDomCandidate].IDom;
     337             : 
     338     7278482 :       WInfo.IDom = WIDomCandidate;
     339             :     }
     340     4381448 :   }
     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     1393992 :   void addVirtualRoot() {
     348             :     assert(IsPostDom && "Only postdominators have a virtual root");
     349             :     assert(NumToNode.size() == 1 && "SNCAInfo must be freshly constructed");
     350             : 
     351     2787984 :     auto &BBInfo = NodeToInfo[nullptr];
     352     1393992 :     BBInfo.DFSNum = BBInfo.Semi = 1;
     353     1393992 :     BBInfo.Label = nullptr;
     354             : 
     355     2787984 :     NumToNode.push_back(nullptr);  // NumToNode[1] = nullptr;
     356     1393992 :   }
     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     1406197 :   static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI) {
     362             :     assert(N && "N must be a valid node");
     363     2812394 :     return !ChildrenGetter<false>::Get(N, BUI).empty();
     364             :   }
     365             : 
     366             :   static NodePtr GetEntryNode(const DomTreeT &DT) {
     367             :     assert(DT.Parent && "Parent not set");
     368             :     return GraphTraits<typename DomTreeT::ParentPtr>::getEntryNode(DT.Parent);
     369             :   }
     370             : 
     371             :   // Finds all roots without relaying on the set of roots already stored in the
     372             :   // tree.
     373             :   // We define roots to be some non-redundant set of the CFG nodes
     374      695155 :   static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI) {
     375             :     assert(DT.Parent && "Parent pointer is not set");
     376             :     RootsT Roots;
     377             : 
     378             :     // For dominators, function entry CFG node is always a tree root node.
     379             :     if (!IsPostDom) {
     380     7311715 :       Roots.push_back(GetEntryNode(DT));
     381             :       return Roots;
     382             :     }
     383             : 
     384     1390310 :     SemiNCAInfo SNCA(BUI);
     385             : 
     386             :     // PostDominatorTree always has a virtual root.
     387      695155 :     SNCA.addVirtualRoot();
     388             :     unsigned Num = 1;
     389             : 
     390             :     LLVM_DEBUG(dbgs() << "\t\tLooking for trivial roots\n");
     391             : 
     392             :     // Step #1: Find all the trivial roots that are going to will definitely
     393             :     // remain tree roots.
     394             :     unsigned Total = 0;
     395             :     // It may happen that there are some new nodes in the CFG that are result of
     396             :     // the ongoing batch update, but we cannot really pretend that they don't
     397             :     // exist -- we won't see any outgoing or incoming edges to them, so it's
     398             :     // fine to discover them here, as they would end up appearing in the CFG at
     399             :     // some point anyway.
     400     3116866 :     for (const NodePtr N : nodes(DT.Parent)) {
     401     1403165 :       ++Total;
     402             :       // If it has no *successors*, it is definitely a root.
     403     1403165 :       if (!HasForwardSuccessors(N, BUI)) {
     404      751173 :         Roots.push_back(N);
     405             :         // Run DFS not to walk this part of CFG later.
     406      751173 :         Num = SNCA.runDFS(N, Num, AlwaysDescend, 1);
     407             :         LLVM_DEBUG(dbgs() << "Found a new trivial root: " << BlockNamePrinter(N)
     408             :                           << "\n");
     409             :         LLVM_DEBUG(dbgs() << "Last visited node: "
     410             :                           << BlockNamePrinter(SNCA.NumToNode[Num]) << "\n");
     411             :       }
     412             :     }
     413             : 
     414             :     LLVM_DEBUG(dbgs() << "\t\tLooking for non-trivial roots\n");
     415             : 
     416             :     // Step #2: Find all non-trivial root candidates. Those are CFG nodes that
     417             :     // are reverse-unreachable were not visited by previous DFS walks (i.e. CFG
     418             :     // nodes in infinite loops).
     419             :     bool HasNonTrivialRoots = false;
     420             :     // Accounting for the virtual exit, see if we had any reverse-unreachable
     421             :     // nodes.
     422      695155 :     if (Total + 1 != Num) {
     423             :       HasNonTrivialRoots = true;
     424             :       // Make another DFS pass over all other nodes to find the
     425             :       // reverse-unreachable blocks, and find the furthest paths we'll be able
     426             :       // to make.
     427             :       // Note that this looks N^2, but it's really 2N worst case, if every node
     428             :       // is unreachable. This is because we are still going to only visit each
     429             :       // unreachable node once, we may just visit it in two directions,
     430             :       // depending on how lucky we get.
     431             :       SmallPtrSet<NodePtr, 4> ConnectToExitBlock;
     432       10538 :       for (const NodePtr I : nodes(DT.Parent)) {
     433             :         if (SNCA.NodeToInfo.count(I) == 0) {
     434             :           LLVM_DEBUG(dbgs()
     435             :                      << "\t\t\tVisiting node " << BlockNamePrinter(I) << "\n");
     436             :           // Find the furthest away we can get by following successors, then
     437             :           // follow them in reverse.  This gives us some reasonable answer about
     438             :           // the post-dom tree inside any infinite loop. In particular, it
     439             :           // guarantees we get to the farthest away point along *some*
     440             :           // path. This also matches the GCC's behavior.
     441             :           // If we really wanted a totally complete picture of dominance inside
     442             :           // this infinite loop, we could do it with SCC-like algorithms to find
     443             :           // the lowest and highest points in the infinite loop.  In theory, it
     444             :           // would be nice to give the canonical backedge for the loop, but it's
     445             :           // expensive and does not always lead to a minimal set of roots.
     446             :           LLVM_DEBUG(dbgs() << "\t\t\tRunning forward DFS\n");
     447             : 
     448        1515 :           const unsigned NewNum = SNCA.runDFS<true>(I, Num, AlwaysDescend, Num);
     449        3030 :           const NodePtr FurthestAway = SNCA.NumToNode[NewNum];
     450             :           LLVM_DEBUG(dbgs() << "\t\t\tFound a new furthest away node "
     451             :                             << "(non-trivial root): "
     452             :                             << BlockNamePrinter(FurthestAway) << "\n");
     453        1515 :           ConnectToExitBlock.insert(FurthestAway);
     454        1515 :           Roots.push_back(FurthestAway);
     455             :           LLVM_DEBUG(dbgs() << "\t\t\tPrev DFSNum: " << Num << ", new DFSNum: "
     456             :                             << NewNum << "\n\t\t\tRemoving DFS info\n");
     457       10891 :           for (unsigned i = NewNum; i > Num; --i) {
     458        9376 :             const NodePtr N = SNCA.NumToNode[i];
     459             :             LLVM_DEBUG(dbgs() << "\t\t\t\tRemoving DFS info for "
     460             :                               << BlockNamePrinter(N) << "\n");
     461        4688 :             SNCA.NodeToInfo.erase(N);
     462             :             SNCA.NumToNode.pop_back();
     463             :           }
     464             :           const unsigned PrevNum = Num;
     465             :           LLVM_DEBUG(dbgs() << "\t\t\tRunning reverse DFS\n");
     466        1515 :           Num = SNCA.runDFS(FurthestAway, Num, AlwaysDescend, 1);
     467        1515 :           for (unsigned i = PrevNum + 1; i <= Num; ++i)
     468             :             LLVM_DEBUG(dbgs() << "\t\t\t\tfound node "
     469             :                               << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
     470             :         }
     471             :       }
     472             :     }
     473             : 
     474             :     LLVM_DEBUG(dbgs() << "Total: " << Total << ", Num: " << Num << "\n");
     475             :     LLVM_DEBUG(dbgs() << "Discovered CFG nodes:\n");
     476             :     LLVM_DEBUG(for (size_t i = 0; i <= Num; ++i) dbgs()
     477             :                << i << ": " << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
     478             : 
     479             :     assert((Total + 1 == Num) && "Everything should have been visited");
     480             : 
     481             :     // Step #3: If we found some non-trivial roots, make them non-redundant.
     482        1378 :     if (HasNonTrivialRoots) RemoveRedundantRoots(DT, BUI, Roots);
     483             : 
     484             :     LLVM_DEBUG(dbgs() << "Found roots: ");
     485             :     LLVM_DEBUG(for (auto *Root
     486             :                     : Roots) dbgs()
     487             :                << BlockNamePrinter(Root) << " ");
     488             :     LLVM_DEBUG(dbgs() << "\n");
     489             : 
     490             :     return Roots;
     491             :   }
     492             : 
     493             :   // This function only makes sense for postdominators.
     494             :   // We define roots to be some set of CFG nodes where (reverse) DFS walks have
     495             :   // to start in order to visit all the CFG nodes (including the
     496             :   // reverse-unreachable ones).
     497             :   // When the search for non-trivial roots is done it may happen that some of
     498             :   // the non-trivial roots are reverse-reachable from other non-trivial roots,
     499             :   // which makes them redundant. This function removes them from the set of
     500             :   // input roots.
     501        1378 :   static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI,
     502             :                                    RootsT &Roots) {
     503             :     assert(IsPostDom && "This function is for postdominators only");
     504             :     LLVM_DEBUG(dbgs() << "Removing redundant roots\n");
     505             : 
     506        2756 :     SemiNCAInfo SNCA(BUI);
     507             : 
     508       10034 :     for (unsigned i = 0; i < Roots.size(); ++i) {
     509             :       auto &Root = Roots[i];
     510             :       // Trivial roots are always non-redundant.
     511        2426 :       if (!HasForwardSuccessors(Root, BUI)) continue;
     512             :       LLVM_DEBUG(dbgs() << "\tChecking if " << BlockNamePrinter(Root)
     513             :                         << " remains a root\n");
     514        1515 :       SNCA.clear();
     515             :       // Do a forward walk looking for the other roots.
     516        1515 :       const unsigned Num = SNCA.runDFS<true>(Root, 0, AlwaysDescend, 0);
     517             :       // Skip the start node and begin from the second one (note that DFS uses
     518             :       // 1-based indexing).
     519        4219 :       for (unsigned x = 2; x <= Num; ++x) {
     520        2866 :         const NodePtr N = SNCA.NumToNode[x];
     521             :         // If we wound another root in a (forward) DFS walk, remove the current
     522             :         // root from the set of roots, as it is reverse-reachable from the other
     523             :         // one.
     524        1433 :         if (llvm::find(Roots, N) != Roots.end()) {
     525             :           LLVM_DEBUG(dbgs() << "\tForward DFS walk found another root "
     526             :                             << BlockNamePrinter(N) << "\n\tRemoving root "
     527             :                             << BlockNamePrinter(Root) << "\n");
     528             :           std::swap(Root, Roots.back());
     529             :           Roots.pop_back();
     530             : 
     531             :           // Root at the back takes the current root's place.
     532             :           // Start the next loop iteration with the same index.
     533          81 :           --i;
     534          81 :           break;
     535             :         }
     536             :       }
     537             :     }
     538        1378 :   }
     539             : 
     540             :   template <typename DescendCondition>
     541      698837 :   void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
     542             :     if (!IsPostDom) {
     543             :       assert(DT.Roots.size() == 1 && "Dominators should have a singe root");
     544     3660216 :       runDFS(DT.Roots[0], 0, DC, 0);
     545             :       return;
     546             :     }
     547             : 
     548      698837 :     addVirtualRoot();
     549             :     unsigned Num = 1;
     550     1462218 :     for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0);
     551             :   }
     552             : 
     553     4350505 :   static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) {
     554     4350505 :     auto *Parent = DT.Parent;
     555             :     DT.reset();
     556     4350505 :     DT.Parent = Parent;
     557     8701010 :     SemiNCAInfo SNCA(nullptr);  // Since we are rebuilding the whole tree,
     558             :                                 // there's no point doing it incrementally.
     559             : 
     560             :     // Step #0: Number blocks in depth-first order and initialize variables used
     561             :     // in later stages of the algorithm.
     562     5045325 :     DT.Roots = FindRoots(DT, nullptr);
     563      694820 :     SNCA.doFullDFSWalk(DT, AlwaysDescend);
     564             : 
     565     4350505 :     SNCA.runSemiNCA(DT);
     566     4350505 :     if (BUI) {
     567        4798 :       BUI->IsRecalculated = true;
     568             :       LLVM_DEBUG(
     569             :           dbgs() << "DomTree recalculated, skipping future batch updates\n");
     570             :     }
     571             : 
     572     4350505 :     if (DT.Roots.empty()) return;
     573             : 
     574             :     // Add a node for the root. If the tree is a PostDominatorTree it will be
     575             :     // the virtual exit (denoted by (BasicBlock *) nullptr) which postdominates
     576             :     // all real exits (including multiple exit blocks, infinite loops).
     577     4350505 :     NodePtr Root = IsPostDom ? nullptr : DT.Roots[0];
     578             : 
     579    13051515 :     DT.RootNode = (DT.DomTreeNodes[Root] =
     580             :                        llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
     581             :         .get();
     582     4350505 :     SNCA.attachNewSubtree(DT, DT.RootNode);
     583             :   }
     584             : 
     585     4363494 :   void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {
     586             :     // Attach the first unreachable block to AttachTo.
     587    13090482 :     NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
     588             :     // Loop over all of the discovered blocks in the function...
     589    29727918 :     for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
     590    21000930 :       NodePtr W = NumToNode[i];
     591             :       LLVM_DEBUG(dbgs() << "\tdiscovered a new reachable node "
     592             :                         << BlockNamePrinter(W) << "\n");
     593             : 
     594             :       // Don't replace this with 'count', the insertion side effect is important
     595    21000930 :       if (DT.DomTreeNodes[W]) continue;  // Haven't calculated this node yet?
     596             : 
     597     6149960 :       NodePtr ImmDom = getIDom(W);
     598             : 
     599             :       // Get or calculate the node for the immediate dominator.
     600     6149960 :       TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
     601             : 
     602             :       // Add a new tree node for this BasicBlock, and link it as a child of
     603             :       // IDomNode.
     604    12299920 :       DT.DomTreeNodes[W] = IDomNode->addChild(
     605             :           llvm::make_unique<DomTreeNodeBase<NodeT>>(W, IDomNode));
     606             :     }
     607     4363494 :   }
     608             : 
     609       17954 :   void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) {
     610       53862 :     NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
     611     2354838 :     for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
     612     2318930 :       const NodePtr N = NumToNode[i];
     613             :       const TreeNodePtr TN = DT.getNode(N);
     614             :       assert(TN);
     615     1159465 :       const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom);
     616     1159465 :       TN->setIDom(NewIDom);
     617             :     }
     618       17954 :   }
     619             : 
     620             :   // Helper struct used during edge insertions.
     621       58495 :   struct InsertionInfo {
     622             :     using BucketElementTy = std::pair<unsigned, TreeNodePtr>;
     623             :     struct DecreasingLevel {
     624             :       bool operator()(const BucketElementTy &First,
     625             :                       const BucketElementTy &Second) const {
     626             :         return First.first > Second.first;
     627             :       }
     628             :     };
     629             : 
     630             :     std::priority_queue<BucketElementTy, SmallVector<BucketElementTy, 8>,
     631             :         DecreasingLevel>
     632             :         Bucket;  // Queue of tree nodes sorted by level in descending order.
     633             :     SmallDenseSet<TreeNodePtr, 8> Affected;
     634             :     SmallDenseMap<TreeNodePtr, unsigned, 8> Visited;
     635             :     SmallVector<TreeNodePtr, 8> AffectedQueue;
     636             :     SmallVector<TreeNodePtr, 8> VisitedNotAffectedQueue;
     637             :   };
     638             : 
     639       28950 :   static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
     640             :                          const NodePtr From, const NodePtr To) {
     641             :     assert((From || IsPostDom) &&
     642             :            "From has to be a valid CFG node or a virtual root");
     643             :     assert(To && "Cannot be a nullptr");
     644             :     LLVM_DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> "
     645             :                       << BlockNamePrinter(To) << "\n");
     646         161 :     TreeNodePtr FromTN = DT.getNode(From);
     647             : 
     648       27489 :     if (!FromTN) {
     649             :       // Ignore edges from unreachable nodes for (forward) dominators.
     650             :       if (!IsPostDom) return;
     651             : 
     652             :       // The unreachable node becomes a new root -- a tree node for it.
     653             :       TreeNodePtr VirtualRoot = DT.getNode(nullptr);
     654             :       FromTN =
     655           6 :           (DT.DomTreeNodes[From] = VirtualRoot->addChild(
     656             :                llvm::make_unique<DomTreeNodeBase<NodeT>>(From, VirtualRoot)))
     657             :               .get();
     658           3 :       DT.Roots.push_back(From);
     659             :     }
     660             : 
     661       27492 :     DT.DFSInfoValid = false;
     662             : 
     663             :     const TreeNodePtr ToTN = DT.getNode(To);
     664       14503 :     if (!ToTN)
     665       12989 :       InsertUnreachable(DT, BUI, FromTN, To);
     666             :     else
     667       14503 :       InsertReachable(DT, BUI, FromTN, ToTN);
     668             :   }
     669             : 
     670             :   // Determines if some existing root becomes reverse-reachable after the
     671             :   // insertion. Rebuilds the whole tree if that situation happens.
     672         209 :   static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
     673             :                                          const TreeNodePtr From,
     674             :                                          const TreeNodePtr To) {
     675             :     assert(IsPostDom && "This function is only for postdominators");
     676             :     // Destination node is not attached to the virtual root, so it cannot be a
     677             :     // root.
     678           0 :     if (!DT.isVirtualRoot(To->getIDom())) return false;
     679             : 
     680         198 :     auto RIt = llvm::find(DT.Roots, To->getBlock());
     681          99 :     if (RIt == DT.Roots.end())
     682             :       return false;  // To is not a root, nothing to update.
     683             : 
     684             :     LLVM_DEBUG(dbgs() << "\t\tAfter the insertion, " << BlockNamePrinter(To)
     685             :                       << " is no longer a root\n\t\tRebuilding the tree!!!\n");
     686             : 
     687          84 :     CalculateFromScratch(DT, BUI);
     688             :     return true;
     689             :   }
     690             : 
     691             :   // Updates the set of roots after insertion or deletion. This ensures that
     692             :   // roots are the same when after a series of updates and when the tree would
     693             :   // be built from scratch.
     694         223 :   static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI) {
     695             :     assert(IsPostDom && "This function is only for postdominators");
     696             : 
     697             :     // The tree has only trivial roots -- nothing to update.
     698         223 :     if (std::none_of(DT.Roots.begin(), DT.Roots.end(), [BUI](const NodePtr N) {
     699             :           return HasForwardSuccessors(N, BUI);
     700         606 :         }))
     701         208 :       return;
     702             : 
     703             :     // Recalculate the set of roots.
     704          26 :     auto Roots = FindRoots(DT, BUI);
     705          44 :     if (DT.Roots.size() != Roots.size() ||
     706             :         !std::is_permutation(DT.Roots.begin(), DT.Roots.end(), Roots.begin())) {
     707             :       // The roots chosen in the CFG have changed. This is because the
     708             :       // incremental algorithm does not really know or use the set of roots and
     709             :       // can make a different (implicit) decision about which node within an
     710             :       // infinite loop becomes a root.
     711             : 
     712             :       LLVM_DEBUG(dbgs() << "Roots are different in updated trees\n"
     713             :                         << "The entire tree needs to be rebuilt\n");
     714             :       // It may be possible to update the tree without recalculating it, but
     715             :       // we do not know yet how to do it, and it happens rarely in practise.
     716          11 :       CalculateFromScratch(DT, BUI);
     717             :       return;
     718             :     }
     719             :   }
     720             : 
     721             :   // Handles insertion to a node already in the dominator tree.
     722       37029 :   static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
     723             :                               const TreeNodePtr From, const TreeNodePtr To) {
     724             :     LLVM_DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock())
     725             :                       << " -> " << BlockNamePrinter(To->getBlock()) << "\n");
     726       25539 :     if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return;
     727             :     // DT.findNCD expects both pointers to be valid. When From is a virtual
     728             :     // root, then its CFG block pointer is a nullptr, so we have to 'compute'
     729             :     // the NCD manually.
     730             :     const NodePtr NCDBlock =
     731       73788 :         (From->getBlock() && To->getBlock())
     732       73839 :             ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock())
     733             :             : nullptr;
     734             :     assert(NCDBlock || DT.isPostDominator());
     735             :     const TreeNodePtr NCD = DT.getNode(NCDBlock);
     736             :     assert(NCD);
     737             : 
     738             :     LLVM_DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n");
     739       36945 :     const TreeNodePtr ToIDom = To->getIDom();
     740             : 
     741             :     // Nothing affected -- NCA property holds.
     742             :     // (Based on the lemma 2.5 from the second paper.)
     743       36945 :     if (NCD == To || NCD == ToIDom) return;
     744             : 
     745             :     // Identify and collect affected nodes.
     746       23398 :     InsertionInfo II;
     747             :     LLVM_DEBUG(dbgs() << "Marking " << BlockNamePrinter(To)
     748             :                       << " as affected\n");
     749             :     II.Affected.insert(To);
     750       11699 :     const unsigned ToLevel = To->getLevel();
     751             :     LLVM_DEBUG(dbgs() << "Putting " << BlockNamePrinter(To)
     752             :                       << " into a Bucket\n");
     753       11699 :     II.Bucket.push({ToLevel, To});
     754             : 
     755       36415 :     while (!II.Bucket.empty()) {
     756       12358 :       const TreeNodePtr CurrentNode = II.Bucket.top().second;
     757           0 :       const unsigned  CurrentLevel = CurrentNode->getLevel();
     758             :       II.Bucket.pop();
     759             :       LLVM_DEBUG(dbgs() << "\tAdding to Visited and AffectedQueue: "
     760             :                         << BlockNamePrinter(CurrentNode) << "\n");
     761             : 
     762       12358 :       II.Visited.insert({CurrentNode, CurrentLevel});
     763       12358 :       II.AffectedQueue.push_back(CurrentNode);
     764             : 
     765             :       // Discover and collect affected successors of the current node.
     766       12358 :       VisitInsertion(DT, BUI, CurrentNode, CurrentLevel, NCD, II);
     767             :     }
     768             : 
     769             :     // Finish by updating immediate dominators and levels.
     770       11699 :     UpdateInsertion(DT, BUI, NCD, II);
     771             :   }
     772             : 
     773             :   // Visits an affected node and collect its affected successors.
     774       12358 :   static void VisitInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
     775             :                              const TreeNodePtr TN, const unsigned RootLevel,
     776             :                              const TreeNodePtr NCD, InsertionInfo &II) {
     777           0 :     const unsigned NCDLevel = NCD->getLevel();
     778             :     LLVM_DEBUG(dbgs() << "Visiting " << BlockNamePrinter(TN) << ",  RootLevel "
     779             :                       << RootLevel << "\n");
     780             : 
     781       24716 :     SmallVector<TreeNodePtr, 8> Stack = {TN};
     782             :     assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!");
     783             : 
     784             :     SmallPtrSet<TreeNodePtr, 8> Processed;
     785             : 
     786             :     do {
     787             :       TreeNodePtr Next = Stack.pop_back_val();
     788             :       LLVM_DEBUG(dbgs() << " Next: " << BlockNamePrinter(Next) << "\n");
     789             : 
     790     1008178 :       for (const NodePtr Succ :
     791             :            ChildrenGetter<IsPostDom>::Get(Next->getBlock(), BUI)) {
     792      288561 :         const TreeNodePtr SuccTN = DT.getNode(Succ);
     793             :         assert(SuccTN && "Unreachable successor found at reachable insertion");
     794           0 :         const unsigned SuccLevel = SuccTN->getLevel();
     795             : 
     796             :         LLVM_DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
     797             :                           << ", level = " << SuccLevel << "\n");
     798             : 
     799             :         // Do not process the same node multiple times.
     800      288561 :         if (Processed.count(Next) > 0)
     801       70350 :           continue;
     802             : 
     803             :         // Succ dominated by subtree From -- not affected.
     804             :         // (Based on the lemma 2.5 from the second paper.)
     805      288560 :         if (SuccLevel > RootLevel) {
     806             :           LLVM_DEBUG(dbgs() << "\t\tDominated by subtree From\n");
     807      273518 :           if (II.Visited.count(SuccTN) != 0) {
     808             :             LLVM_DEBUG(dbgs() << "\t\t\talready visited at level "
     809             :                               << II.Visited[SuccTN] << "\n\t\t\tcurrent level "
     810             :                               << RootLevel << ")\n");
     811             : 
     812             :             // A node can be necessary to visit again if we see it again at
     813             :             // a lower level than before.
     814       70368 :             if (II.Visited[SuccTN] >= RootLevel)
     815       70348 :               continue;
     816             :           }
     817             : 
     818             :           LLVM_DEBUG(dbgs() << "\t\tMarking visited not affected "
     819             :                             << BlockNamePrinter(Succ) << "\n");
     820      203170 :           II.Visited.insert({SuccTN, RootLevel});
     821      203170 :           II.VisitedNotAffectedQueue.push_back(SuccTN);
     822      203170 :           Stack.push_back(SuccTN);
     823       15042 :         } else if ((SuccLevel > NCDLevel + 1) &&
     824        1022 :             II.Affected.count(SuccTN) == 0) {
     825             :           LLVM_DEBUG(dbgs() << "\t\tMarking affected and adding "
     826             :                             << BlockNamePrinter(Succ) << " to a Bucket\n");
     827             :           II.Affected.insert(SuccTN);
     828         659 :           II.Bucket.push({SuccLevel, SuccTN});
     829             :         }
     830             :       }
     831             : 
     832      215528 :       Processed.insert(Next);
     833      215528 :     } while (!Stack.empty());
     834       12358 :   }
     835             : 
     836             :   // Updates immediate dominators and levels after insertion.
     837       11699 :   static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
     838             :                               const TreeNodePtr NCD, InsertionInfo &II) {
     839             :     LLVM_DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n");
     840             : 
     841       36415 :     for (const TreeNodePtr TN : II.AffectedQueue) {
     842             :       LLVM_DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN)
     843             :                         << ") = " << BlockNamePrinter(NCD) << "\n");
     844       12358 :       TN->setIDom(NCD);
     845             :     }
     846             : 
     847             :     UpdateLevelsAfterInsertion(II);
     848          87 :     if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
     849       11699 :   }
     850             : 
     851             :   static void UpdateLevelsAfterInsertion(InsertionInfo &II) {
     852             :     LLVM_DEBUG(
     853             :         dbgs() << "Updating levels for visited but not affected nodes\n");
     854             : 
     855      418039 :     for (const TreeNodePtr TN : II.VisitedNotAffectedQueue) {
     856             :       LLVM_DEBUG(dbgs() << "\tlevel(" << BlockNamePrinter(TN) << ") = ("
     857             :                         << BlockNamePrinter(TN->getIDom()) << ") "
     858             :                         << TN->getIDom()->getLevel() << " + 1\n");
     859      203170 :       TN->UpdateLevel();
     860             :     }
     861             :   }
     862             : 
     863             :   // Handles insertion to previously unreachable nodes.
     864       12989 :   static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
     865             :                                 const TreeNodePtr From, const NodePtr To) {
     866             :     LLVM_DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From)
     867             :                       << " -> (unreachable) " << BlockNamePrinter(To) << "\n");
     868             : 
     869             :     // Collect discovered edges to already reachable nodes.
     870             :     SmallVector<std::pair<NodePtr, TreeNodePtr>, 8> DiscoveredEdgesToReachable;
     871             :     // Discover and connect nodes that became reachable with the insertion.
     872       12989 :     ComputeUnreachableDominators(DT, BUI, To, From, DiscoveredEdgesToReachable);
     873             : 
     874             :     LLVM_DEBUG(dbgs() << "Inserted " << BlockNamePrinter(From)
     875             :                       << " -> (prev unreachable) " << BlockNamePrinter(To)
     876             :                       << "\n");
     877             : 
     878             :     // Used the discovered edges and inset discovered connecting (incoming)
     879             :     // edges.
     880       57939 :     for (const auto &Edge : DiscoveredEdgesToReachable) {
     881             :       LLVM_DEBUG(dbgs() << "\tInserting discovered connecting edge "
     882             :                         << BlockNamePrinter(Edge.first) << " -> "
     883             :                         << BlockNamePrinter(Edge.second) << "\n");
     884       44950 :       InsertReachable(DT, BUI, DT.getNode(Edge.first), Edge.second);
     885             :     }
     886       12989 :   }
     887             : 
     888             :   // Connects nodes that become reachable with an insertion.
     889       12989 :   static void ComputeUnreachableDominators(
     890             :       DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root,
     891             :       const TreeNodePtr Incoming,
     892             :       SmallVectorImpl<std::pair<NodePtr, TreeNodePtr>>
     893             :           &DiscoveredConnectingEdges) {
     894             :     assert(!DT.getNode(Root) && "Root must not be reachable");
     895             : 
     896             :     // Visit only previously unreachable nodes.
     897       12989 :     auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From,
     898      589855 :                                                                   NodePtr To) {
     899             :       const TreeNodePtr ToTN = DT.getNode(To);
     900       22475 :       if (!ToTN) return true;
     901             : 
     902       44950 :       DiscoveredConnectingEdges.push_back({From, ToTN});
     903       22475 :       return false;
     904             :     };
     905             : 
     906       25978 :     SemiNCAInfo SNCA(BUI);
     907       12989 :     SNCA.runDFS(Root, 0, UnreachableDescender, 0);
     908       12989 :     SNCA.runSemiNCA(DT);
     909       12989 :     SNCA.attachNewSubtree(DT, Incoming);
     910             : 
     911             :     LLVM_DEBUG(dbgs() << "After adding unreachable nodes\n");
     912       12989 :   }
     913             : 
     914       38639 :   static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
     915             :                          const NodePtr From, const NodePtr To) {
     916             :     assert(From && To && "Cannot disconnect nullptrs");
     917             :     LLVM_DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> "
     918             :                       << BlockNamePrinter(To) << "\n");
     919             : 
     920             : #ifndef NDEBUG
     921             :     // Ensure that the edge was in fact deleted from the CFG before informing
     922             :     // the DomTree about it.
     923             :     // The check is O(N), so run it only in debug configuration.
     924             :     auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) {
     925             :       auto Successors = ChildrenGetter<IsPostDom>::Get(Of, BUI);
     926             :       return llvm::find(Successors, SuccCandidate) != Successors.end();
     927             :     };
     928             :     (void)IsSuccessor;
     929             :     assert(!IsSuccessor(To, From) && "Deleted edge still exists in the CFG!");
     930             : #endif
     931             : 
     932             :     const TreeNodePtr FromTN = DT.getNode(From);
     933             :     // Deletion in an unreachable subtree -- nothing to do.
     934       36284 :     if (!FromTN) return;
     935             : 
     936             :     const TreeNodePtr ToTN = DT.getNode(To);
     937       36284 :     if (!ToTN) {
     938             :       LLVM_DEBUG(
     939             :           dbgs() << "\tTo (" << BlockNamePrinter(To)
     940             :                  << ") already unreachable -- there is no edge to delete\n");
     941             :       return;
     942             :     }
     943             : 
     944       36284 :     const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);
     945             :     const TreeNodePtr NCD = DT.getNode(NCDBlock);
     946             : 
     947             :     // If To dominates From -- nothing to do.
     948       36284 :     if (ToTN != NCD) {
     949       36155 :       DT.DFSInfoValid = false;
     950             : 
     951           0 :       const TreeNodePtr ToIDom = ToTN->getIDom();
     952             :       LLVM_DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
     953             :                         << BlockNamePrinter(ToIDom) << "\n");
     954             : 
     955             :       // To remains reachable after deletion.
     956             :       // (Based on the caption under Figure 4. from the second paper.)
     957       36155 :       if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN))
     958       14977 :         DeleteReachable(DT, BUI, FromTN, ToTN);
     959             :       else
     960       21178 :         DeleteUnreachable(DT, BUI, ToTN);
     961             :     }
     962             : 
     963         136 :     if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
     964             :   }
     965             : 
     966             :   // Handles deletions that leave destination nodes reachable.
     967       14977 :   static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
     968             :                               const TreeNodePtr FromTN,
     969             :                               const TreeNodePtr ToTN) {
     970             :     LLVM_DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN)
     971             :                       << " -> " << BlockNamePrinter(ToTN) << "\n");
     972             :     LLVM_DEBUG(dbgs() << "\tRebuilding subtree\n");
     973             : 
     974             :     // Find the top of the subtree that needs to be rebuilt.
     975             :     // (Based on the lemma 2.6 from the second paper.)
     976       14977 :     const NodePtr ToIDom =
     977             :         DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock());
     978             :     assert(ToIDom || DT.isPostDominator());
     979             :     const TreeNodePtr ToIDomTN = DT.getNode(ToIDom);
     980             :     assert(ToIDomTN);
     981           0 :     const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom();
     982             :     // Top of the subtree to rebuild is the root node. Rebuild the tree from
     983             :     // scratch.
     984       14977 :     if (!PrevIDomSubTree) {
     985             :       LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
     986        4140 :       CalculateFromScratch(DT, BUI);
     987        4140 :       return;
     988             :     }
     989             : 
     990             :     // Only visit nodes in the subtree starting at To.
     991           0 :     const unsigned Level = ToIDomTN->getLevel();
     992      961041 :     auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {
     993           0 :       return DT.getNode(To)->getLevel() > Level;
     994      475102 :     };
     995             : 
     996             :     LLVM_DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN)
     997             :                       << "\n");
     998             : 
     999       21674 :     SemiNCAInfo SNCA(BUI);
    1000       10837 :     SNCA.runDFS(ToIDom, 0, DescendBelow, 0);
    1001             :     LLVM_DEBUG(dbgs() << "\tRunning Semi-NCA\n");
    1002       10837 :     SNCA.runSemiNCA(DT, Level);
    1003       10837 :     SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
    1004             :   }
    1005             : 
    1006             :   // Checks if a node has proper support, as defined on the page 3 and later
    1007             :   // explained on the page 7 of the second paper.
    1008       31034 :   static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI,
    1009             :                                const TreeNodePtr TN) {
    1010             :     LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN)
    1011             :                       << "\n");
    1012       62812 :     for (const NodePtr Pred :
    1013             :          ChildrenGetter<!IsPostDom>::Get(TN->getBlock(), BUI)) {
    1014             :       LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
    1015       10077 :       if (!DT.getNode(Pred)) continue;
    1016             : 
    1017       10077 :       const NodePtr Support =
    1018             :           DT.findNearestCommonDominator(TN->getBlock(), Pred);
    1019             :       LLVM_DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
    1020       10077 :       if (Support != TN->getBlock()) {
    1021             :         LLVM_DEBUG(dbgs() << "\t" << BlockNamePrinter(TN)
    1022             :                           << " is reachable from support "
    1023             :                           << BlockNamePrinter(Support) << "\n");
    1024             :         return true;
    1025             :       }
    1026             :     }
    1027             : 
    1028       21178 :     return false;
    1029             :   }
    1030             : 
    1031             :   // Handle deletions that make destination node unreachable.
    1032             :   // (Based on the lemma 2.7 from the second paper.)
    1033       21178 :   static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
    1034             :                                 const TreeNodePtr ToTN) {
    1035             :     LLVM_DEBUG(dbgs() << "Deleting unreachable subtree "
    1036             :                       << BlockNamePrinter(ToTN) << "\n");
    1037             :     assert(ToTN);
    1038             :     assert(ToTN->getBlock());
    1039             : 
    1040             :     if (IsPostDom) {
    1041             :       // Deletion makes a region reverse-unreachable and creates a new root.
    1042             :       // Simulate that by inserting an edge from the virtual root to ToTN and
    1043             :       // adding it as a new root.
    1044             :       LLVM_DEBUG(dbgs() << "\tDeletion made a region reverse-unreachable\n");
    1045             :       LLVM_DEBUG(dbgs() << "\tAdding new root " << BlockNamePrinter(ToTN)
    1046             :                         << "\n");
    1047         102 :       DT.Roots.push_back(ToTN->getBlock());
    1048          51 :       InsertReachable(DT, BUI, DT.getNode(nullptr), ToTN);
    1049       14010 :       return;
    1050             :     }
    1051             : 
    1052             :     SmallVector<NodePtr, 16> AffectedQueue;
    1053             :     const unsigned Level = ToTN->getLevel();
    1054             : 
    1055             :     // Traverse destination node's descendants with greater level in the tree
    1056             :     // and collect visited nodes.
    1057     1210191 :     auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
    1058      582302 :       const TreeNodePtr TN = DT.getNode(To);
    1059             :       assert(TN);
    1060      582302 :       if (TN->getLevel() > Level) return true;
    1061       24460 :       if (llvm::find(AffectedQueue, To) == AffectedQueue.end())
    1062       14308 :         AffectedQueue.push_back(To);
    1063             : 
    1064             :       return false;
    1065             :     };
    1066             : 
    1067       28244 :     SemiNCAInfo SNCA(BUI);
    1068       21127 :     unsigned LastDFSNum =
    1069             :         SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0);
    1070             : 
    1071             :     TreeNodePtr MinNode = ToTN;
    1072             : 
    1073             :     // Identify the top of the subtree to rebuild by finding the NCD of all
    1074             :     // the affected nodes.
    1075       49743 :     for (const NodePtr N : AffectedQueue) {
    1076             :       const TreeNodePtr TN = DT.getNode(N);
    1077       14308 :       const NodePtr NCDBlock =
    1078             :           DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock());
    1079             :       assert(NCDBlock || DT.isPostDominator());
    1080             :       const TreeNodePtr NCD = DT.getNode(NCDBlock);
    1081             :       assert(NCD);
    1082             : 
    1083             :       LLVM_DEBUG(dbgs() << "Processing affected node " << BlockNamePrinter(TN)
    1084             :                         << " with NCD = " << BlockNamePrinter(NCD)
    1085             :                         << ", MinNode =" << BlockNamePrinter(MinNode) << "\n");
    1086       27109 :       if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD;
    1087             :     }
    1088             : 
    1089             :     // Root reached, rebuild the whole tree from scratch.
    1090       21127 :     if (!MinNode->getIDom()) {
    1091             :       LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
    1092        1238 :       CalculateFromScratch(DT, BUI);
    1093        1238 :       return;
    1094             :     }
    1095             : 
    1096             :     // Erase the unreachable subtree in reverse preorder to process all children
    1097             :     // before deleting their parent.
    1098     1094899 :     for (unsigned i = LastDFSNum; i > 0; --i) {
    1099     1075010 :       const NodePtr N = SNCA.NumToNode[i];
    1100             :       const TreeNodePtr TN = DT.getNode(N);
    1101             :       LLVM_DEBUG(dbgs() << "Erasing node " << BlockNamePrinter(TN) << "\n");
    1102             : 
    1103      537505 :       EraseNode(DT, TN);
    1104             :     }
    1105             : 
    1106             :     // The affected subtree start at the To node -- there's no extra work to do.
    1107       19889 :     if (MinNode == ToTN) return;
    1108             : 
    1109             :     LLVM_DEBUG(dbgs() << "DeleteUnreachable: running DFS with MinNode = "
    1110             :                       << BlockNamePrinter(MinNode) << "\n");
    1111             :     const unsigned MinLevel = MinNode->getLevel();
    1112             :     const TreeNodePtr PrevIDom = MinNode->getIDom();
    1113             :     assert(PrevIDom);
    1114        7117 :     SNCA.clear();
    1115             : 
    1116             :     // Identify nodes that remain in the affected subtree.
    1117     1618455 :     auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) {
    1118             :       const TreeNodePtr ToTN = DT.getNode(To);
    1119     1611338 :       return ToTN && ToTN->getLevel() > MinLevel;
    1120             :     };
    1121        7117 :     SNCA.runDFS(MinNode->getBlock(), 0, DescendBelow, 0);
    1122             : 
    1123             :     LLVM_DEBUG(dbgs() << "Previous IDom(MinNode) = "
    1124             :                       << BlockNamePrinter(PrevIDom) << "\nRunning Semi-NCA\n");
    1125             : 
    1126             :     // Rebuild the remaining part of affected subtree.
    1127        7117 :     SNCA.runSemiNCA(DT, MinLevel);
    1128        7117 :     SNCA.reattachExistingSubtree(DT, PrevIDom);
    1129             :   }
    1130             : 
    1131             :   // Removes leaf tree nodes from the dominator tree.
    1132      537505 :   static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
    1133             :     assert(TN);
    1134             :     assert(TN->getNumChildren() == 0 && "Not a tree leaf");
    1135             : 
    1136      537505 :     const TreeNodePtr IDom = TN->getIDom();
    1137             :     assert(IDom);
    1138             : 
    1139             :     auto ChIt = llvm::find(IDom->Children, TN);
    1140             :     assert(ChIt != IDom->Children.end());
    1141             :     std::swap(*ChIt, IDom->Children.back());
    1142             :     IDom->Children.pop_back();
    1143             : 
    1144     1075010 :     DT.DomTreeNodes.erase(TN->getBlock());
    1145      537505 :   }
    1146             : 
    1147             :   //~~
    1148             :   //===--------------------- DomTree Batch Updater --------------------------===
    1149             :   //~~
    1150             : 
    1151       11367 :   static void ApplyUpdates(DomTreeT &DT, ArrayRef<UpdateT> Updates) {
    1152       11367 :     const size_t NumUpdates = Updates.size();
    1153       11367 :     if (NumUpdates == 0)
    1154         188 :       return;
    1155             : 
    1156             :     // Take the fast path for a single update and avoid running the batch update
    1157             :     // machinery.
    1158       11363 :     if (NumUpdates == 1) {
    1159         184 :       const auto &Update = Updates.front();
    1160         184 :       if (Update.getKind() == UpdateKind::Insert)
    1161           0 :         DT.insertEdge(Update.getFrom(), Update.getTo());
    1162             :       else
    1163           0 :         DT.deleteEdge(Update.getFrom(), Update.getTo());
    1164             : 
    1165             :       return;
    1166             :     }
    1167             : 
    1168       22358 :     BatchUpdateInfo BUI;
    1169       11179 :     LegalizeUpdates(Updates, BUI.Updates);
    1170             : 
    1171             :     const size_t NumLegalized = BUI.Updates.size();
    1172       11179 :     BUI.FutureSuccessors.reserve(NumLegalized);
    1173       11179 :     BUI.FuturePredecessors.reserve(NumLegalized);
    1174             : 
    1175             :     // Use the legalized future updates to initialize future successors and
    1176             :     // predecessors. Note that these sets will only decrease size over time, as
    1177             :     // the next CFG snapshots slowly approach the actual (current) CFG.
    1178      183439 :     for (UpdateT &U : BUI.Updates) {
    1179      258390 :       BUI.FutureSuccessors[U.getFrom()].push_back({U.getTo(), U.getKind()});
    1180      258390 :       BUI.FuturePredecessors[U.getTo()].push_back({U.getFrom(), U.getKind()});
    1181             :     }
    1182             : 
    1183             :     LLVM_DEBUG(dbgs() << "About to apply " << NumLegalized << " updates\n");
    1184             :     LLVM_DEBUG(if (NumLegalized < 32) for (const auto &U
    1185             :                                            : reverse(BUI.Updates)) dbgs()
    1186             :                << '\t' << U << "\n");
    1187             :     LLVM_DEBUG(dbgs() << "\n");
    1188             : 
    1189             :     // If the DominatorTree was recalculated at some point, stop the batch
    1190             :     // updates. Full recalculations ignore batch updates and look at the actual
    1191             :     // CFG.
    1192      142501 :     for (size_t i = 0; i < NumLegalized && !BUI.IsRecalculated; ++i)
    1193       65661 :       ApplyNextUpdate(DT, BUI);
    1194             :   }
    1195             : 
    1196             :   // This function serves double purpose:
    1197             :   // a) It removes redundant updates, which makes it easier to reverse-apply
    1198             :   //    them when traversing CFG.
    1199             :   // b) It optimizes away updates that cancel each other out, as the end result
    1200             :   //    is the same.
    1201             :   //
    1202             :   // It relies on the property of the incremental updates that says that the
    1203             :   // order of updates doesn't matter. This allows us to reorder them and end up
    1204             :   // with the exact same DomTree every time.
    1205             :   //
    1206             :   // Following the same logic, the function doesn't care about the order of
    1207             :   // input updates, so it's OK to pass it an unordered sequence of updates, that
    1208             :   // doesn't make sense when applied sequentially, eg. performing double
    1209             :   // insertions or deletions and then doing an opposite update.
    1210             :   //
    1211             :   // In the future, it should be possible to schedule updates in way that
    1212             :   // minimizes the amount of work needed done during incremental updates.
    1213       11181 :   static void LegalizeUpdates(ArrayRef<UpdateT> AllUpdates,
    1214             :                               SmallVectorImpl<UpdateT> &Result) {
    1215             :     LLVM_DEBUG(dbgs() << "Legalizing " << AllUpdates.size() << " updates\n");
    1216             :     // Count the total number of inserions of each edge.
    1217             :     // Each insertion adds 1 and deletion subtracts 1. The end number should be
    1218             :     // one of {-1 (deletion), 0 (NOP), +1 (insertion)}. Otherwise, the sequence
    1219             :     // of updates contains multiple updates of the same kind and we assert for
    1220             :     // that case.
    1221             :     SmallDenseMap<std::pair<NodePtr, NodePtr>, int, 4> Operations;
    1222       11181 :     Operations.reserve(AllUpdates.size());
    1223             : 
    1224      183469 :     for (const auto &U : AllUpdates) {
    1225          14 :       NodePtr From = U.getFrom();
    1226             :       NodePtr To = U.getTo();
    1227             :       if (IsPostDom) std::swap(From, To);  // Reverse edge for postdominators.
    1228             : 
    1229      172288 :       Operations[{From, To}] += (U.getKind() == UpdateKind::Insert ? 1 : -1);
    1230             :     }
    1231             : 
    1232             :     Result.clear();
    1233       11181 :     Result.reserve(Operations.size());
    1234      194638 :     for (auto &Op : Operations) {
    1235       86138 :       const int NumInsertions = Op.second;
    1236             :       assert(std::abs(NumInsertions) <= 1 && "Unbalanced operations!");
    1237       86138 :       if (NumInsertions == 0) continue;
    1238       86136 :       const UpdateKind UK =
    1239             :           NumInsertions > 0 ? UpdateKind::Insert : UpdateKind::Delete;
    1240      172272 :       Result.push_back({UK, Op.first.first, Op.first.second});
    1241             :     }
    1242             : 
    1243             :     // Make the order consistent by not relying on pointer values within the
    1244             :     // set. Reuse the old Operations map.
    1245             :     // In the future, we should sort by something else to minimize the amount
    1246             :     // of work needed to perform the series of updates.
    1247      183469 :     for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) {
    1248             :       const auto &U = AllUpdates[i];
    1249             :       if (!IsPostDom)
    1250       85921 :         Operations[{U.getFrom(), U.getTo()}] = int(i);
    1251             :       else
    1252         237 :         Operations[{U.getTo(), U.getFrom()}] = int(i);
    1253             :     }
    1254             : 
    1255             :     llvm::sort(Result.begin(), Result.end(),
    1256     1266066 :                [&Operations](const UpdateT &A, const UpdateT &B) {
    1257     1267417 :                  return Operations[{A.getFrom(), A.getTo()}] >
    1258      423373 :                         Operations[{B.getFrom(), B.getTo()}];
    1259      844044 :                });
    1260       11181 :   }
    1261             : 
    1262       65661 :   static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) {
    1263             :     assert(!BUI.Updates.empty() && "No updates to apply!");
    1264             :     UpdateT CurrentUpdate = BUI.Updates.pop_back_val();
    1265             :     LLVM_DEBUG(dbgs() << "Applying update: " << CurrentUpdate << "\n");
    1266             : 
    1267             :     // Move to the next snapshot of the CFG by removing the reverse-applied
    1268             :     // current update. Since updates are performed in the same order they are
    1269             :     // legalized it's sufficient to pop the last item here.
    1270      131322 :     auto &FS = BUI.FutureSuccessors[CurrentUpdate.getFrom()];
    1271             :     assert(FS.back().getPointer() == CurrentUpdate.getTo() &&
    1272             :            FS.back().getInt() == CurrentUpdate.getKind());
    1273             :     FS.pop_back();
    1274       65661 :     if (FS.empty()) BUI.FutureSuccessors.erase(CurrentUpdate.getFrom());
    1275             : 
    1276      131322 :     auto &FP = BUI.FuturePredecessors[CurrentUpdate.getTo()];
    1277             :     assert(FP.back().getPointer() == CurrentUpdate.getFrom() &&
    1278             :            FP.back().getInt() == CurrentUpdate.getKind());
    1279             :     FP.pop_back();
    1280       65661 :     if (FP.empty()) BUI.FuturePredecessors.erase(CurrentUpdate.getTo());
    1281             : 
    1282       65661 :     if (CurrentUpdate.getKind() == UpdateKind::Insert)
    1283       28362 :       InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
    1284             :     else
    1285       37299 :       DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
    1286       65661 :   }
    1287             : 
    1288             :   //~~
    1289             :   //===--------------- DomTree correctness verification ---------------------===
    1290             :   //~~
    1291             : 
    1292             :   // Check if the tree has correct roots. A DominatorTree always has a single
    1293             :   // root which is the function's entry node. A PostDominatorTree can have
    1294             :   // multiple roots - one for each node with no successors and for infinite
    1295             :   // loops.
    1296             :   // Running time: O(N).
    1297         654 :   bool verifyRoots(const DomTreeT &DT) {
    1298         654 :     if (!DT.Parent && !DT.Roots.empty()) {
    1299           0 :       errs() << "Tree has no parent but has roots!\n";
    1300           0 :       errs().flush();
    1301             :       return false;
    1302             :     }
    1303             : 
    1304             :     if (!IsPostDom) {
    1305         345 :       if (DT.Roots.empty()) {
    1306           0 :         errs() << "Tree doesn't have a root!\n";
    1307           0 :         errs().flush();
    1308             :         return false;
    1309             :       }
    1310             : 
    1311         345 :       if (DT.getRoot() != GetEntryNode(DT)) {
    1312           0 :         errs() << "Tree's root is not its parent's entry node!\n";
    1313           0 :         errs().flush();
    1314             :         return false;
    1315             :       }
    1316             :     }
    1317             : 
    1318         309 :     RootsT ComputedRoots = FindRoots(DT, nullptr);
    1319        1308 :     if (DT.Roots.size() != ComputedRoots.size() ||
    1320             :         !std::is_permutation(DT.Roots.begin(), DT.Roots.end(),
    1321             :                              ComputedRoots.begin())) {
    1322           0 :       errs() << "Tree has different roots than freshly computed ones!\n";
    1323           0 :       errs() << "\tPDT roots: ";
    1324           0 :       for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", ";
    1325           0 :       errs() << "\n\tComputed roots: ";
    1326           0 :       for (const NodePtr N : ComputedRoots)
    1327           0 :         errs() << BlockNamePrinter(N) << ", ";
    1328           0 :       errs() << "\n";
    1329           0 :       errs().flush();
    1330             :       return false;
    1331             :     }
    1332             : 
    1333             :     return true;
    1334             :   }
    1335             : 
    1336             :   // Checks if the tree contains all reachable nodes in the input graph.
    1337             :   // Running time: O(N).
    1338         654 :   bool verifyReachability(const DomTreeT &DT) {
    1339         654 :     clear();
    1340         309 :     doFullDFSWalk(DT, AlwaysDescend);
    1341             : 
    1342        7818 :     for (auto &NodeToTN : DT.DomTreeNodes) {
    1343             :       const TreeNodePtr TN = NodeToTN.second.get();
    1344           0 :       const NodePtr BB = TN->getBlock();
    1345             : 
    1346             :       // Virtual root has a corresponding virtual CFG node.
    1347         309 :       if (DT.isVirtualRoot(TN)) continue;
    1348             : 
    1349        6201 :       if (NodeToInfo.count(BB) == 0) {
    1350           0 :         errs() << "DomTree node " << BlockNamePrinter(BB)
    1351             :                << " not found by DFS walk!\n";
    1352           0 :         errs().flush();
    1353             : 
    1354           0 :         return false;
    1355             :       }
    1356             :     }
    1357             : 
    1358        7818 :     for (const NodePtr N : NumToNode) {
    1359       13365 :       if (N && !DT.getNode(N)) {
    1360           0 :         errs() << "CFG node " << BlockNamePrinter(N)
    1361             :                << " not found in the DomTree!\n";
    1362           0 :         errs().flush();
    1363             : 
    1364             :         return false;
    1365             :       }
    1366             :     }
    1367             : 
    1368             :     return true;
    1369             :   }
    1370             : 
    1371             :   // Check if for every parent with a level L in the tree all of its children
    1372             :   // have level L + 1.
    1373             :   // Running time: O(N).
    1374         654 :   static bool VerifyLevels(const DomTreeT &DT) {
    1375        7818 :     for (auto &NodeToTN : DT.DomTreeNodes) {
    1376             :       const TreeNodePtr TN = NodeToTN.second.get();
    1377           0 :       const NodePtr BB = TN->getBlock();
    1378        6510 :       if (!BB) continue;
    1379             : 
    1380           0 :       const TreeNodePtr IDom = TN->getIDom();
    1381        6546 :       if (!IDom && TN->getLevel() != 0) {
    1382           0 :         errs() << "Node without an IDom " << BlockNamePrinter(BB)
    1383           0 :                << " has a nonzero level " << TN->getLevel() << "!\n";
    1384           0 :         errs().flush();
    1385             : 
    1386           0 :         return false;
    1387             :       }
    1388             : 
    1389       12057 :       if (IDom && TN->getLevel() != IDom->getLevel() + 1) {
    1390           0 :         errs() << "Node " << BlockNamePrinter(BB) << " has level "
    1391           0 :                << TN->getLevel() << " while its IDom "
    1392           0 :                << BlockNamePrinter(IDom->getBlock()) << " has level "
    1393           0 :                << IDom->getLevel() << "!\n";
    1394           0 :         errs().flush();
    1395             : 
    1396             :         return false;
    1397             :       }
    1398             :     }
    1399             : 
    1400         654 :     return true;
    1401             :   }
    1402             : 
    1403             :   // Check if the computed DFS numbers are correct. Note that DFS info may not
    1404             :   // be valid, and when that is the case, we don't verify the numbers.
    1405             :   // Running time: O(N log(N)).
    1406         654 :   static bool VerifyDFSNumbers(const DomTreeT &DT) {
    1407         654 :     if (!DT.DFSInfoValid || !DT.Parent)
    1408             :       return true;
    1409             : 
    1410           1 :     const NodePtr RootBB = IsPostDom ? nullptr : DT.getRoots()[0];
    1411             :     const TreeNodePtr Root = DT.getNode(RootBB);
    1412             : 
    1413           0 :     auto PrintNodeAndDFSNums = [](const TreeNodePtr TN) {
    1414           0 :       errs() << BlockNamePrinter(TN) << " {" << TN->getDFSNumIn() << ", "
    1415           0 :              << TN->getDFSNumOut() << '}';
    1416           0 :     };
    1417             : 
    1418             :     // Verify the root's DFS In number. Although DFS numbering would also work
    1419             :     // if we started from some other value, we assume 0-based numbering.
    1420           1 :     if (Root->getDFSNumIn() != 0) {
    1421           0 :       errs() << "DFSIn number for the tree root is not:\n\t";
    1422           0 :       PrintNodeAndDFSNums(Root);
    1423           0 :       errs() << '\n';
    1424           0 :       errs().flush();
    1425             :       return false;
    1426             :     }
    1427             : 
    1428             :     // For each tree node verify if children's DFS numbers cover their parent's
    1429             :     // DFS numbers with no gaps.
    1430           7 :     for (const auto &NodeToTN : DT.DomTreeNodes) {
    1431             :       const TreeNodePtr Node = NodeToTN.second.get();
    1432             : 
    1433             :       // Handle tree leaves.
    1434           8 :       if (Node->getChildren().empty()) {
    1435           6 :         if (Node->getDFSNumIn() + 1 != Node->getDFSNumOut()) {
    1436           0 :           errs() << "Tree leaf should have DFSOut = DFSIn + 1:\n\t";
    1437           0 :           PrintNodeAndDFSNums(Node);
    1438           0 :           errs() << '\n';
    1439           0 :           errs().flush();
    1440           0 :           return false;
    1441             :         }
    1442             : 
    1443           3 :         continue;
    1444             :       }
    1445             : 
    1446             :       // Make a copy and sort it such that it is possible to check if there are
    1447             :       // no gaps between DFS numbers of adjacent children.
    1448             :       SmallVector<TreeNodePtr, 8> Children(Node->begin(), Node->end());
    1449             :       llvm::sort(Children.begin(), Children.end(),
    1450             :                  [](const TreeNodePtr Ch1, const TreeNodePtr Ch2) {
    1451           0 :                    return Ch1->getDFSNumIn() < Ch2->getDFSNumIn();
    1452             :                  });
    1453             : 
    1454           2 :       auto PrintChildrenError = [Node, &Children, PrintNodeAndDFSNums](
    1455           0 :           const TreeNodePtr FirstCh, const TreeNodePtr SecondCh) {
    1456             :         assert(FirstCh);
    1457             : 
    1458           0 :         errs() << "Incorrect DFS numbers for:\n\tParent ";
    1459           0 :         PrintNodeAndDFSNums(Node);
    1460             : 
    1461           0 :         errs() << "\n\tChild ";
    1462           0 :         PrintNodeAndDFSNums(FirstCh);
    1463             : 
    1464           0 :         if (SecondCh) {
    1465           0 :           errs() << "\n\tSecond child ";
    1466           0 :           PrintNodeAndDFSNums(SecondCh);
    1467             :         }
    1468             : 
    1469           0 :         errs() << "\nAll children: ";
    1470           0 :         for (const TreeNodePtr Ch : Children) {
    1471           0 :           PrintNodeAndDFSNums(Ch);
    1472           0 :           errs() << ", ";
    1473             :         }
    1474             : 
    1475           0 :         errs() << '\n';
    1476           0 :         errs().flush();
    1477           0 :       };
    1478             : 
    1479           4 :       if (Children.front()->getDFSNumIn() != Node->getDFSNumIn() + 1) {
    1480           0 :         PrintChildrenError(Children.front(), nullptr);
    1481           0 :         return false;
    1482             :       }
    1483             : 
    1484           6 :       if (Children.back()->getDFSNumOut() + 1 != Node->getDFSNumOut()) {
    1485           0 :         PrintChildrenError(Children.back(), nullptr);
    1486           0 :         return false;
    1487             :       }
    1488             : 
    1489           2 :       for (size_t i = 0, e = Children.size() - 1; i != e; ++i) {
    1490           8 :         if (Children[i]->getDFSNumOut() + 1 != Children[i + 1]->getDFSNumIn()) {
    1491           0 :           PrintChildrenError(Children[i], Children[i + 1]);
    1492           0 :           return false;
    1493             :         }
    1494             :       }
    1495             :     }
    1496             : 
    1497           1 :     return true;
    1498             :   }
    1499             : 
    1500             :   // The below routines verify the correctness of the dominator tree relative to
    1501             :   // the CFG it's coming from.  A tree is a dominator tree iff it has two
    1502             :   // properties, called the parent property and the sibling property.  Tarjan
    1503             :   // and Lengauer prove (but don't explicitly name) the properties as part of
    1504             :   // the proofs in their 1972 paper, but the proofs are mostly part of proving
    1505             :   // things about semidominators and idoms, and some of them are simply asserted
    1506             :   // based on even earlier papers (see, e.g., lemma 2).  Some papers refer to
    1507             :   // these properties as "valid" and "co-valid".  See, e.g., "Dominators,
    1508             :   // directed bipolar orders, and independent spanning trees" by Loukas
    1509             :   // Georgiadis and Robert E. Tarjan, as well as "Dominator Tree Verification
    1510             :   // and Vertex-Disjoint Paths " by the same authors.
    1511             : 
    1512             :   // A very simple and direct explanation of these properties can be found in
    1513             :   // "An Experimental Study of Dynamic Dominators", found at
    1514             :   // https://arxiv.org/abs/1604.02711
    1515             : 
    1516             :   // The easiest way to think of the parent property is that it's a requirement
    1517             :   // of being a dominator.  Let's just take immediate dominators.  For PARENT to
    1518             :   // be an immediate dominator of CHILD, all paths in the CFG must go through
    1519             :   // PARENT before they hit CHILD.  This implies that if you were to cut PARENT
    1520             :   // out of the CFG, there should be no paths to CHILD that are reachable.  If
    1521             :   // there are, then you now have a path from PARENT to CHILD that goes around
    1522             :   // PARENT and still reaches CHILD, which by definition, means PARENT can't be
    1523             :   // a dominator of CHILD (let alone an immediate one).
    1524             : 
    1525             :   // The sibling property is similar.  It says that for each pair of sibling
    1526             :   // nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each
    1527             :   // other.  If sibling LEFT dominated sibling RIGHT, it means there are no
    1528             :   // paths in the CFG from sibling LEFT to sibling RIGHT that do not go through
    1529             :   // LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of
    1530             :   // RIGHT, not a sibling.
    1531             : 
    1532             :   // It is possible to verify the parent and sibling properties in
    1533             :   // linear time, but the algorithms are complex. Instead, we do it in a
    1534             :   // straightforward N^2 and N^3 way below, using direct path reachability.
    1535             : 
    1536             :   // Checks if the tree has the parent property: if for all edges from V to W in
    1537             :   // the input graph, such that V is reachable, the parent of W in the tree is
    1538             :   // an ancestor of V in the tree.
    1539             :   // Running time: O(N^2).
    1540             :   //
    1541             :   // This means that if a node gets disconnected from the graph, then all of
    1542             :   // the nodes it dominated previously will now become unreachable.
    1543         654 :   bool verifyParentProperty(const DomTreeT &DT) {
    1544        7818 :     for (auto &NodeToTN : DT.DomTreeNodes) {
    1545             :       const TreeNodePtr TN = NodeToTN.second.get();
    1546           0 :       const NodePtr BB = TN->getBlock();
    1547       12711 :       if (!BB || TN->getChildren().empty()) continue;
    1548             : 
    1549             :       LLVM_DEBUG(dbgs() << "Verifying parent property of node "
    1550             :                         << BlockNamePrinter(TN) << "\n");
    1551        3383 :       clear();
    1552       22236 :       doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) {
    1553       20574 :         return From != BB && To != BB;
    1554       20574 :       });
    1555             : 
    1556        3383 :       for (TreeNodePtr Child : TN->getChildren())
    1557        4511 :         if (NodeToInfo.count(Child->getBlock()) != 0) {
    1558           0 :           errs() << "Child " << BlockNamePrinter(Child)
    1559           0 :                  << " reachable after its parent " << BlockNamePrinter(BB)
    1560             :                  << " is removed!\n";
    1561           0 :           errs().flush();
    1562             : 
    1563             :           return false;
    1564             :         }
    1565             :     }
    1566             : 
    1567         654 :     return true;
    1568             :   }
    1569             : 
    1570             :   // Check if the tree has sibling property: if a node V does not dominate a
    1571             :   // node W for all siblings V and W in the tree.
    1572             :   // Running time: O(N^3).
    1573             :   //
    1574             :   // This means that if a node gets disconnected from the graph, then all of its
    1575             :   // siblings will now still be reachable.
    1576         654 :   bool verifySiblingProperty(const DomTreeT &DT) {
    1577        7818 :     for (auto &NodeToTN : DT.DomTreeNodes) {
    1578             :       const TreeNodePtr TN = NodeToTN.second.get();
    1579           0 :       const NodePtr BB = TN->getBlock();
    1580       12711 :       if (!BB || TN->getChildren().empty()) continue;
    1581             : 
    1582             :       const auto &Siblings = TN->getChildren();
    1583        7894 :       for (const TreeNodePtr N : Siblings) {
    1584        4511 :         clear();
    1585           0 :         NodePtr BBN = N->getBlock();
    1586       36639 :         doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) {
    1587       34593 :           return From != BBN && To != BBN;
    1588       34593 :         });
    1589             : 
    1590        4511 :         for (const TreeNodePtr S : Siblings) {
    1591        7321 :           if (S == N) continue;
    1592             : 
    1593        2810 :           if (NodeToInfo.count(S->getBlock()) == 0) {
    1594           0 :             errs() << "Node " << BlockNamePrinter(S)
    1595           0 :                    << " not reachable when its sibling " << BlockNamePrinter(N)
    1596             :                    << " is removed!\n";
    1597           0 :             errs().flush();
    1598             : 
    1599             :             return false;
    1600             :           }
    1601             :         }
    1602             :       }
    1603             :     }
    1604             : 
    1605         654 :     return true;
    1606             :   }
    1607             : 
    1608             :   // Check if the given tree is the same as a freshly computed one for the same
    1609             :   // Parent.
    1610             :   // Running time: O(N^2), but faster in practise (same as tree construction).
    1611             :   //
    1612             :   // Note that this does not check if that the tree construction algorithm is
    1613             :   // correct and should be only used for fast (but possibly unsound)
    1614             :   // verification.
    1615         656 :   static bool IsSameAsFreshTree(const DomTreeT &DT) {
    1616         656 :     DomTreeT FreshTree;
    1617         656 :     FreshTree.recalculate(*DT.Parent);
    1618         656 :     const bool Different = DT.compare(FreshTree);
    1619             : 
    1620         656 :     if (Different) {
    1621           4 :       errs() << (DT.isPostDominator() ? "Post" : "")
    1622           2 :              << "DominatorTree is different than a freshly computed one!\n"
    1623             :              << "\tCurrent:\n";
    1624           2 :       DT.print(errs());
    1625           2 :       errs() << "\n\tFreshly computed tree:\n";
    1626           2 :       FreshTree.print(errs());
    1627           2 :       errs().flush();
    1628             :     }
    1629             : 
    1630        1312 :     return !Different;
    1631             :   }
    1632             : };
    1633             : 
    1634             : template <class DomTreeT>
    1635     2488044 : void Calculate(DomTreeT &DT) {
    1636     4345032 :   SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, nullptr);
    1637     2488044 : }
    1638             : 
    1639             : template <class DomTreeT>
    1640         588 : void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
    1641             :                 typename DomTreeT::NodePtr To) {
    1642             :   if (DT.isPostDominator()) std::swap(From, To);
    1643         588 :   SemiNCAInfo<DomTreeT>::InsertEdge(DT, nullptr, From, To);
    1644         588 : }
    1645             : 
    1646             : template <class DomTreeT>
    1647        1340 : void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
    1648             :                 typename DomTreeT::NodePtr To) {
    1649             :   if (DT.isPostDominator()) std::swap(From, To);
    1650        1340 :   SemiNCAInfo<DomTreeT>::DeleteEdge(DT, nullptr, From, To);
    1651        1340 : }
    1652             : 
    1653             : template <class DomTreeT>
    1654       11367 : void ApplyUpdates(DomTreeT &DT,
    1655             :                   ArrayRef<typename DomTreeT::UpdateType> Updates) {
    1656       11367 :   SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, Updates);
    1657       11367 : }
    1658             : 
    1659             : template <class DomTreeT>
    1660         656 : bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) {
    1661        1312 :   SemiNCAInfo<DomTreeT> SNCA(nullptr);
    1662             : 
    1663             :   // Simplist check is to compare against a new tree. This will also
    1664             :   // usefully print the old and new trees, if they are different.
    1665         656 :   if (!SNCA.IsSameAsFreshTree(DT))
    1666             :     return false;
    1667             : 
    1668             :   // Common checks to verify the properties of the tree. O(N log N) at worst
    1669        1962 :   if (!SNCA.verifyRoots(DT) || !SNCA.verifyReachability(DT) ||
    1670        1962 :       !SNCA.VerifyLevels(DT) || !SNCA.VerifyDFSNumbers(DT))
    1671             :     return false;
    1672             : 
    1673             :   // Extra checks depending on VerificationLevel. Up to O(N^3)
    1674         654 :   if (VL == DomTreeT::VerificationLevel::Basic ||
    1675             :       VL == DomTreeT::VerificationLevel::Full)
    1676         654 :     if (!SNCA.verifyParentProperty(DT))
    1677             :       return false;
    1678         654 :   if (VL == DomTreeT::VerificationLevel::Full)
    1679         654 :     if (!SNCA.verifySiblingProperty(DT))
    1680             :       return false;
    1681             : 
    1682             :   return true;
    1683             : }
    1684             : 
    1685             : }  // namespace DomTreeBuilder
    1686             : }  // namespace llvm
    1687             : 
    1688             : #undef DEBUG_TYPE
    1689             : 
    1690             : #endif

Generated by: LCOV version 1.13