LCOV - code coverage report
Current view: top level - include/llvm/Support - GenericDomTreeConstruction.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 432 535 80.7 %
Date: 2018-06-17 00:07:59 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    10314110 : 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    33684986 :   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       76698 :   struct BatchUpdateInfo {
      75             :     SmallVector<UpdateT, 4> Updates;
      76             :     using NodePtrAndKind = PointerIntPair<NodePtr, 1, UpdateKind>;
      77             : 
      78             :     // In order to be able to walk a CFG that is out of sync with the CFG
      79             :     // DominatorTree last knew about, use the list of updates to reconstruct
      80             :     // previous CFG versions of the current CFG. For each node, we store a set
      81             :     // of its virtually added/deleted future successors and predecessors.
      82             :     // Note that these children are from the future relative to what the
      83             :     // DominatorTree knows about -- using them to gets us some snapshot of the
      84             :     // CFG from the past (relative to the state of the CFG).
      85             :     DenseMap<NodePtr, SmallDenseSet<NodePtrAndKind, 4>> FutureSuccessors;
      86             :     DenseMap<NodePtr, SmallDenseSet<NodePtrAndKind, 4>> FuturePredecessors;
      87             :     // Remembers if the whole tree was recalculated at some point during the
      88             :     // current batch update.
      89             :     bool IsRecalculated = false;
      90             :   };
      91             : 
      92             :   BatchUpdateInfo *BatchUpdates;
      93             :   using BatchUpdatePtr = BatchUpdateInfo *;
      94             : 
      95             :   // If BUI is a nullptr, then there's no batch update in progress.
      96    15471164 :   SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
      97             : 
      98       18989 :   void clear() {
      99       18989 :     NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
     100       18989 :     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       18989 :   }
     104             : 
     105             :   template <bool Inverse>
     106             :   struct ChildrenGetter {
     107             :     using ResultTy = SmallVector<NodePtr, 8>;
     108             : 
     109     8992445 :     static ResultTy Get(NodePtr N, std::integral_constant<bool, false>) {
     110     8992445 :       auto RChildren = reverse(children<NodePtr>(N));
     111     8992444 :       return ResultTy(RChildren.begin(), RChildren.end());
     112             :     }
     113             : 
     114      715931 :     static ResultTy Get(NodePtr N, std::integral_constant<bool, true>) {
     115             :       auto IChildren = inverse_children<NodePtr>(N);
     116      715931 :       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    15341322 :     static ResultTy Get(NodePtr N, BatchUpdatePtr BUI) {
     126     9708376 :       ResultTy Res = Get(N, Tag());
     127             :       // If there's no batch update in progress, simply return node's children.
     128    15341321 :       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     2657520 :       auto &FutureChildren = (Inverse != IsPostDom) ? BUI->FuturePredecessors
     134             :                                                     : BUI->FutureSuccessors;
     135     2657520 :       auto FCIt = FutureChildren.find(N);
     136     2657520 :       if (FCIt == FutureChildren.end()) return Res;
     137             : 
     138     1368670 :       for (auto ChildAndKind : FCIt->second) {
     139      837745 :         const NodePtr Child = ChildAndKind.getPointer();
     140             :         const UpdateKind UK = ChildAndKind.getInt();
     141             : 
     142             :         // Reverse-apply the future update.
     143      837745 :         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      513541 :           Res.push_back(Child);
     159             :         }
     160             :       }
     161             : 
     162             :       return Res;
     163             :     }
     164             :   };
     165             : 
     166             :   NodePtr getIDom(NodePtr BB) const {
     167     6600912 :     auto InfoIt = NodeToInfo.find(BB);
     168     6600912 :     if (InfoIt == NodeToInfo.end()) return nullptr;
     169             : 
     170     6600912 :     return InfoIt->second.IDom;
     171             :   }
     172             : 
     173     6600912 :   TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT) {
     174    13201824 :     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     6657131 :   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     5297296 :   unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,
     217             :                   unsigned AttachToNum) {
     218             :     assert(V);
     219    10594593 :     SmallVector<NodePtr, 64> WorkList = {V};
     220     5297298 :     if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum;
     221             : 
     222    19806844 :     while (!WorkList.empty()) {
     223    14509548 :       const NodePtr BB = WorkList.pop_back_val();
     224             :       auto &BBInfo = NodeToInfo[BB];
     225             : 
     226             :       // Visited nodes always have positive DFS numbers.
     227    14509548 :       if (BBInfo.DFSNum != 0) continue;
     228    13642101 :       BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
     229    13642101 :       BBInfo.Label = BB;
     230    13642101 :       NumToNode.push_back(BB);
     231             : 
     232             :       constexpr bool Direction = IsReverse != IsPostDom;  // XOR.
     233    50835695 :       for (const NodePtr Succ :
     234             :            ChildrenGetter<Direction>::Get(BB, BatchUpdates)) {
     235    11775747 :         const auto SIT = NodeToInfo.find(Succ);
     236             :         // Don't visit nodes more than once but remember to collect
     237             :         // ReverseChildren.
     238    14240637 :         if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
     239     2464890 :           if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
     240     5028386 :           continue;
     241             :         }
     242             : 
     243     9464442 :         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     9212251 :         WorkList.push_back(Succ);
     249     9212251 :         SuccInfo.Parent = LastNum;
     250     9212251 :         SuccInfo.ReverseChildren.push_back(BB);
     251             :       }
     252             :     }
     253             : 
     254     5297296 :     return LastNum;
     255             :   }
     256             : 
     257     9784059 :   NodePtr eval(NodePtr VIn, unsigned LastLinked) {
     258     9784059 :     auto &VInInfo = NodeToInfo[VIn];
     259     9784059 :     if (VInInfo.DFSNum < LastLinked)
     260     7870636 :       return VIn;
     261             : 
     262             :     SmallVector<NodePtr, 32> Work;
     263             :     SmallPtrSet<NodePtr, 32> Visited;
     264             : 
     265     1913423 :     if (VInInfo.Parent >= LastLinked)
     266      763047 :       Work.push_back(VIn);
     267             : 
     268     8205026 :     while (!Work.empty()) {
     269     6291603 :       NodePtr V = Work.back();
     270             :       auto &VInfo = NodeToInfo[V];
     271    12583206 :       NodePtr VAncestor = NumToNode[VInfo.Parent];
     272             : 
     273             :       // Process Ancestor first
     274    12583206 :       if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) {
     275     2764278 :         Work.push_back(VAncestor);
     276     6291603 :         continue;
     277             :       }
     278             :       Work.pop_back();
     279             : 
     280             :       // Update VInfo based on Ancestor info
     281     3527325 :       if (VInfo.Parent < LastLinked)
     282      763047 :         continue;
     283             : 
     284             :       auto &VAInfo = NodeToInfo[VAncestor];
     285     2764278 :       NodePtr VAncestorLabel = VAInfo.Label;
     286     2764278 :       NodePtr VLabel = VInfo.Label;
     287     5528556 :       if (NodeToInfo[VAncestorLabel].Semi < NodeToInfo[VLabel].Semi)
     288     2531422 :         VInfo.Label = VAncestorLabel;
     289     2764278 :       VInfo.Parent = VAInfo.Parent;
     290             :     }
     291             : 
     292     1913423 :     return VInInfo.Label;
     293             :   }
     294             : 
     295             :   // This function requires DFS to be run before calling it.
     296     4451986 :   void runSemiNCA(DomTreeT &DT, const unsigned MinLevel = 0) {
     297     8903972 :     const unsigned NextDFSNum(NumToNode.size());
     298             :     // Initialize IDoms to spanning tree parents.
     299    29050190 :     for (unsigned i = 1; i < NextDFSNum; ++i) {
     300    24598204 :       const NodePtr V = NumToNode[i];
     301    12299102 :       auto &VInfo = NodeToInfo[V];
     302    24598204 :       VInfo.IDom = NumToNode[VInfo.Parent];
     303             :     }
     304             : 
     305             :     // Step #1: Calculate the semidominators of all vertices.
     306    12299102 :     for (unsigned i = NextDFSNum - 1; i >= 2; --i) {
     307    15694232 :       NodePtr W = NumToNode[i];
     308     7847116 :       auto &WInfo = NodeToInfo[W];
     309             : 
     310             :       // Initialize the semi dominator to point to the parent node.
     311     7847116 :       WInfo.Semi = WInfo.Parent;
     312    27415234 :       for (const auto &N : WInfo.ReverseChildren) {
     313     9784059 :         if (NodeToInfo.count(N) == 0)  // Skip unreachable predecessors.
     314           0 :           continue;
     315             : 
     316     9784059 :         const TreeNodePtr TN = DT.getNode(N);
     317             :         // Skip predecessors whose level is above the subtree we are processing.
     318     3442444 :         if (TN && TN->getLevel() < MinLevel)
     319           0 :           continue;
     320             : 
     321    19568118 :         unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi;
     322    11567416 :         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    20146218 :     for (unsigned i = 2; i < NextDFSNum; ++i) {
     331    15694232 :       const NodePtr W = NumToNode[i];
     332     7847116 :       auto &WInfo = NodeToInfo[W];
     333    15694232 :       const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;
     334     7847116 :       NodePtr WIDomCandidate = WInfo.IDom;
     335    15255576 :       while (NodeToInfo[WIDomCandidate].DFSNum > SDomNum)
     336     3704230 :         WIDomCandidate = NodeToInfo[WIDomCandidate].IDom;
     337             : 
     338     7847116 :       WInfo.IDom = WIDomCandidate;
     339             :     }
     340     4451986 :   }
     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     1377284 :   void addVirtualRoot() {
     348             :     assert(IsPostDom && "Only postdominators have a virtual root");
     349             :     assert(NumToNode.size() == 1 && "SNCAInfo must be freshly constructed");
     350             : 
     351     2754568 :     auto &BBInfo = NodeToInfo[nullptr];
     352     1377284 :     BBInfo.DFSNum = BBInfo.Semi = 1;
     353     1377284 :     BBInfo.Label = nullptr;
     354             : 
     355     2754568 :     NumToNode.push_back(nullptr);  // NumToNode[1] = nullptr;
     356     1377284 :   }
     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     1396071 :   static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI) {
     362             :     assert(N && "N must be a valid node");
     363     2792142 :     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      686813 :   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     7453904 :       Roots.push_back(GetEntryNode(DT));
     381             :       return Roots;
     382             :     }
     383             : 
     384     1373626 :     SemiNCAInfo SNCA(BUI);
     385             : 
     386             :     // PostDominatorTree always has a virtual root.
     387      686813 :     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     3089414 :     for (const NodePtr N : nodes(DT.Parent)) {
     401     1393056 :       ++Total;
     402             :       // If it has no *successors*, it is definitely a root.
     403     1393056 :       if (!HasForwardSuccessors(N, BUI)) {
     404      742662 :         Roots.push_back(N);
     405             :         // Run DFS not to walk this part of CFG later.
     406      742662 :         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      686813 :     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       10530 :       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       10889 :           for (unsigned i = NewNum; i > Num; --i) {
     458        9374 :             const NodePtr N = SNCA.NumToNode[i];
     459             :             LLVM_DEBUG(dbgs() << "\t\t\t\tRemoving DFS info for "
     460             :                               << BlockNamePrinter(N) << "\n");
     461        4687 :             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      690471 :   void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
     542             :     if (!IsPostDom) {
     543             :       assert(DT.Roots.size() == 1 && "Dominators should have a singe root");
     544     3731238 :       runDFS(DT.Roots[0], 0, DC, 0);
     545             :       return;
     546             :     }
     547             : 
     548      690471 :     addVirtualRoot();
     549             :     unsigned Num = 1;
     550     1445311 :     for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0);
     551             :   }
     552             : 
     553     4413285 :   static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) {
     554     4413285 :     auto *Parent = DT.Parent;
     555             :     DT.reset();
     556     4413285 :     DT.Parent = Parent;
     557     8826570 :     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     5099778 :     DT.Roots = FindRoots(DT, nullptr);
     563      686494 :     SNCA.doFullDFSWalk(DT, AlwaysDescend);
     564             : 
     565     4413284 :     SNCA.runSemiNCA(DT);
     566     4413285 :     if (BUI) {
     567        5244 :       BUI->IsRecalculated = true;
     568             :       LLVM_DEBUG(
     569             :           dbgs() << "DomTree recalculated, skipping future batch updates\n");
     570             :     }
     571             : 
     572     4413285 :     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     4413285 :     NodePtr Root = IsPostDom ? nullptr : DT.Roots[0];
     578             : 
     579    13239855 :     DT.RootNode = (DT.DomTreeNodes[Root] =
     580             :                        llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
     581             :         .get();
     582     4413285 :     SNCA.attachNewSubtree(DT, DT.RootNode);
     583             :   }
     584             : 
     585     4430234 :   void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {
     586             :     // Attach the first unreachable block to AttachTo.
     587    13290702 :     NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
     588             :     // Loop over all of the discovered blocks in the function...
     589    30888862 :     for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
     590    22028394 :       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    22028394 :       if (DT.DomTreeNodes[W]) continue;  // Haven't calculated this node yet?
     596             : 
     597     6600912 :       NodePtr ImmDom = getIDom(W);
     598             : 
     599             :       // Get or calculate the node for the immediate dominator.
     600     6600912 :       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    13201824 :       DT.DomTreeNodes[W] = IDomNode->addChild(
     605             :           llvm::make_unique<DomTreeNodeBase<NodeT>>(W, IDomNode));
     606             :     }
     607     4430234 :   }
     608             : 
     609       21752 :   void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) {
     610       65256 :     NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
     611     2613314 :     for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
     612     2569810 :       const NodePtr N = NumToNode[i];
     613             :       const TreeNodePtr TN = DT.getNode(N);
     614             :       assert(TN);
     615     1284905 :       const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom);
     616     1284905 :       TN->setIDom(NewIDom);
     617             :     }
     618       21752 :   }
     619             : 
     620             :   // Helper struct used during edge insertions.
     621       75655 :   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       34758 :   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         158 :     TreeNodePtr FromTN = DT.getNode(From);
     647             : 
     648       32712 :     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       32715 :     DT.DFSInfoValid = false;
     662             : 
     663             :     const TreeNodePtr ToTN = DT.getNode(To);
     664       15766 :     if (!ToTN)
     665       16949 :       InsertUnreachable(DT, BUI, FromTN, To);
     666             :     else
     667       15766 :       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         205 :   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         194 :     auto RIt = llvm::find(DT.Roots, To->getBlock());
     681          97 :     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          82 :     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         216 :   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         216 :     if (std::none_of(DT.Roots.begin(), DT.Roots.end(), [BUI](const NodePtr N) {
     699             :           return HasForwardSuccessors(N, BUI);
     700         589 :         }))
     701         201 :       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       42496 :   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       27570 :     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       84730 :         (From->getBlock() && To->getBlock())
     732       84779 :             ? 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       42414 :     const TreeNodePtr ToIDom = To->getIDom();
     740             : 
     741             :     // Nothing affected -- NCA property holds.
     742             :     // (Based on the lemma 2.5 from the second paper.)
     743       42414 :     if (NCD == To || NCD == ToIDom) return;
     744             : 
     745             :     // Identify and collect affected nodes.
     746       30262 :     InsertionInfo II;
     747             :     LLVM_DEBUG(dbgs() << "Marking " << BlockNamePrinter(To)
     748             :                       << " as affected\n");
     749             :     II.Affected.insert(To);
     750       15131 :     const unsigned ToLevel = To->getLevel();
     751             :     LLVM_DEBUG(dbgs() << "Putting " << BlockNamePrinter(To)
     752             :                       << " into a Bucket\n");
     753       15131 :     II.Bucket.push({ToLevel, To});
     754             : 
     755       48267 :     while (!II.Bucket.empty()) {
     756       16568 :       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       16568 :       II.Visited.insert({CurrentNode, CurrentLevel});
     763       16568 :       II.AffectedQueue.push_back(CurrentNode);
     764             : 
     765             :       // Discover and collect affected successors of the current node.
     766       16568 :       VisitInsertion(DT, BUI, CurrentNode, CurrentLevel, NCD, II);
     767             :     }
     768             : 
     769             :     // Finish by updating immediate dominators and levels.
     770       15131 :     UpdateInsertion(DT, BUI, NCD, II);
     771             :   }
     772             : 
     773             :   // Visits an affected node and collect its affected successors.
     774       16568 :   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       33136 :     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     1252456 :       for (const NodePtr Succ :
     791             :            ChildrenGetter<IsPostDom>::Get(Next->getBlock(), BUI)) {
     792      358631 :         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      358631 :         if (Processed.count(Next) > 0)
     801       87371 :           continue;
     802             : 
     803             :         // Succ dominated by subtree From -- not affected.
     804             :         // (Based on the lemma 2.5 from the second paper.)
     805      358630 :         if (SuccLevel > RootLevel) {
     806             :           LLVM_DEBUG(dbgs() << "\t\tDominated by subtree From\n");
     807      338398 :           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       87389 :             if (II.Visited[SuccTN] >= RootLevel)
     815       87369 :               continue;
     816             :           }
     817             : 
     818             :           LLVM_DEBUG(dbgs() << "\t\tMarking visited not affected "
     819             :                             << BlockNamePrinter(Succ) << "\n");
     820      251029 :           II.Visited.insert({SuccTN, RootLevel});
     821      251029 :           II.VisitedNotAffectedQueue.push_back(SuccTN);
     822      251029 :           Stack.push_back(SuccTN);
     823       20232 :         } else if ((SuccLevel > NCDLevel + 1) &&
     824        2067 :             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        1437 :           II.Bucket.push({SuccLevel, SuccTN});
     829             :         }
     830             :       }
     831             : 
     832      267597 :       Processed.insert(Next);
     833      267597 :     } while (!Stack.empty());
     834       16568 :   }
     835             : 
     836             :   // Updates immediate dominators and levels after insertion.
     837       15131 :   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       48267 :     for (const TreeNodePtr TN : II.AffectedQueue) {
     842             :       LLVM_DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN)
     843             :                         << ") = " << BlockNamePrinter(NCD) << "\n");
     844       16568 :       TN->setIDom(NCD);
     845             :     }
     846             : 
     847             :     UpdateLevelsAfterInsertion(II);
     848          85 :     if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
     849       15131 :   }
     850             : 
     851             :   static void UpdateLevelsAfterInsertion(InsertionInfo &II) {
     852             :     LLVM_DEBUG(
     853             :         dbgs() << "Updating levels for visited but not affected nodes\n");
     854             : 
     855      517189 :     for (const TreeNodePtr TN : II.VisitedNotAffectedQueue) {
     856             :       LLVM_DEBUG(dbgs() << "\tlevel(" << BlockNamePrinter(TN) << ") = ("
     857             :                         << BlockNamePrinter(TN->getIDom()) << ") "
     858             :                         << TN->getIDom()->getLevel() << " + 1\n");
     859      251029 :       TN->UpdateLevel();
     860             :     }
     861             :   }
     862             : 
     863             :   // Handles insertion to previously unreachable nodes.
     864       16949 :   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       16949 :     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       70311 :     for (const auto &Edge : DiscoveredEdgesToReachable) {
     881             :       LLVM_DEBUG(dbgs() << "\tInserting discovered connecting edge "
     882             :                         << BlockNamePrinter(Edge.first) << " -> "
     883             :                         << BlockNamePrinter(Edge.second) << "\n");
     884       53362 :       InsertReachable(DT, BUI, DT.getNode(Edge.first), Edge.second);
     885             :     }
     886       16949 :   }
     887             : 
     888             :   // Connects nodes that become reachable with an insertion.
     889       16949 :   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       16949 :     auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From,
     898      608873 :                                                                   NodePtr To) {
     899             :       const TreeNodePtr ToTN = DT.getNode(To);
     900       26681 :       if (!ToTN) return true;
     901             : 
     902       53362 :       DiscoveredConnectingEdges.push_back({From, ToTN});
     903       26681 :       return false;
     904             :     };
     905             : 
     906       33898 :     SemiNCAInfo SNCA(BUI);
     907       16949 :     SNCA.runDFS(Root, 0, UnreachableDescender, 0);
     908       16949 :     SNCA.runSemiNCA(DT);
     909       16949 :     SNCA.attachNewSubtree(DT, Incoming);
     910             : 
     911             :     LLVM_DEBUG(dbgs() << "After adding unreachable nodes\n");
     912       16949 :   }
     913             : 
     914       44968 :   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       42430 :     if (!FromTN) return;
     935             : 
     936             :     const TreeNodePtr ToTN = DT.getNode(To);
     937       42430 :     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       42430 :     const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);
     945             :     const TreeNodePtr NCD = DT.getNode(NCDBlock);
     946             : 
     947             :     // If To dominates From -- nothing to do.
     948       42430 :     if (ToTN != NCD) {
     949       42291 :       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       42291 :       if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN))
     958       16932 :         DeleteReachable(DT, BUI, FromTN, ToTN);
     959             :       else
     960       25359 :         DeleteUnreachable(DT, BUI, ToTN);
     961             :     }
     962             : 
     963         131 :     if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
     964             :   }
     965             : 
     966             :   // Handles deletions that leave destination nodes reachable.
     967       16932 :   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       16932 :     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       16932 :     if (!PrevIDomSubTree) {
     985             :       LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
     986        4229 :       CalculateFromScratch(DT, BUI);
     987        4229 :       return;
     988             :     }
     989             : 
     990             :     // Only visit nodes in the subtree starting at To.
     991           0 :     const unsigned Level = ToIDomTN->getLevel();
     992     1076159 :     auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {
     993           0 :       return DT.getNode(To)->getLevel() > Level;
     994      531728 :     };
     995             : 
     996             :     LLVM_DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN)
     997             :                       << "\n");
     998             : 
     999       25406 :     SemiNCAInfo SNCA(BUI);
    1000       12703 :     SNCA.runDFS(ToIDom, 0, DescendBelow, 0);
    1001             :     LLVM_DEBUG(dbgs() << "\tRunning Semi-NCA\n");
    1002       12703 :     SNCA.runSemiNCA(DT, Level);
    1003       12703 :     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       35553 :   static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI,
    1009             :                                const TreeNodePtr TN) {
    1010             :     LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN)
    1011             :                       << "\n");
    1012       71624 :     for (const NodePtr Pred :
    1013             :          ChildrenGetter<!IsPostDom>::Get(TN->getBlock(), BUI)) {
    1014             :       LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
    1015       10390 :       if (!DT.getNode(Pred)) continue;
    1016             : 
    1017       10390 :       const NodePtr Support =
    1018             :           DT.findNearestCommonDominator(TN->getBlock(), Pred);
    1019             :       LLVM_DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
    1020       10390 :       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       25359 :     return false;
    1029             :   }
    1030             : 
    1031             :   // Handle deletions that make destination node unreachable.
    1032             :   // (Based on the lemma 2.7 from the second paper.)
    1033       25359 :   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          98 :       DT.Roots.push_back(ToTN->getBlock());
    1048          49 :       InsertReachable(DT, BUI, DT.getNode(nullptr), ToTN);
    1049       16261 :       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     1249739 :     auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
    1058      597927 :       const TreeNodePtr TN = DT.getNode(To);
    1059             :       assert(TN);
    1060      597927 :       if (TN->getLevel() > Level) return true;
    1061       28575 :       if (llvm::find(AffectedQueue, To) == AffectedQueue.end())
    1062       17784 :         AffectedQueue.push_back(To);
    1063             : 
    1064             :       return false;
    1065             :     };
    1066             : 
    1067       34359 :     SemiNCAInfo SNCA(BUI);
    1068       25310 :     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       60878 :     for (const NodePtr N : AffectedQueue) {
    1076             :       const TreeNodePtr TN = DT.getNode(N);
    1077       17784 :       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       33995 :       if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD;
    1087             :     }
    1088             : 
    1089             :     // Root reached, rebuild the whole tree from scratch.
    1090       25310 :     if (!MinNode->getIDom()) {
    1091             :       LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
    1092        1582 :       CalculateFromScratch(DT, BUI);
    1093        1582 :       return;
    1094             :     }
    1095             : 
    1096             :     // Erase the unreachable subtree in reverse preorder to process all children
    1097             :     // before deleting their parent.
    1098     1125314 :     for (unsigned i = LastDFSNum; i > 0; --i) {
    1099     1101586 :       const NodePtr N = SNCA.NumToNode[i];
    1100             :       const TreeNodePtr TN = DT.getNode(N);
    1101             :       LLVM_DEBUG(dbgs() << "Erasing node " << BlockNamePrinter(TN) << "\n");
    1102             : 
    1103      550793 :       EraseNode(DT, TN);
    1104             :     }
    1105             : 
    1106             :     // The affected subtree start at the To node -- there's no extra work to do.
    1107       23728 :     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        9049 :     SNCA.clear();
    1115             : 
    1116             :     // Identify nodes that remain in the affected subtree.
    1117     1782849 :     auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) {
    1118             :       const TreeNodePtr ToTN = DT.getNode(To);
    1119     1773800 :       return ToTN && ToTN->getLevel() > MinLevel;
    1120             :     };
    1121        9049 :     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        9049 :     SNCA.runSemiNCA(DT, MinLevel);
    1128        9049 :     SNCA.reattachExistingSubtree(DT, PrevIDom);
    1129             :   }
    1130             : 
    1131             :   // Removes leaf tree nodes from the dominator tree.
    1132      550793 :   static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
    1133             :     assert(TN);
    1134             :     assert(TN->getNumChildren() == 0 && "Not a tree leaf");
    1135             : 
    1136      550793 :     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     1101586 :     DT.DomTreeNodes.erase(TN->getBlock());
    1145      550793 :   }
    1146             : 
    1147             :   //~~
    1148             :   //===--------------------- DomTree Batch Updater --------------------------===
    1149             :   //~~
    1150             : 
    1151       12857 :   static void ApplyUpdates(DomTreeT &DT, ArrayRef<UpdateT> Updates) {
    1152       12857 :     const size_t NumUpdates = Updates.size();
    1153       12857 :     if (NumUpdates == 0)
    1154          74 :       return;
    1155             : 
    1156             :     // Take the fast path for a single update and avoid running the batch update
    1157             :     // machinery.
    1158       12853 :     if (NumUpdates == 1) {
    1159          70 :       const auto &Update = Updates.front();
    1160          70 :       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       25566 :     BatchUpdateInfo BUI;
    1169       12783 :     LegalizeUpdates(Updates, BUI.Updates);
    1170             : 
    1171             :     const size_t NumLegalized = BUI.Updates.size();
    1172       12783 :     BUI.FutureSuccessors.reserve(NumLegalized);
    1173       12783 :     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      213663 :     for (UpdateT &U : BUI.Updates) {
    1179      200880 :       BUI.FutureSuccessors[U.getFrom()].insert({U.getTo(), U.getKind()});
    1180      200880 :       BUI.FuturePredecessors[U.getTo()].insert({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      168733 :     for (size_t i = 0; i < NumLegalized && !BUI.IsRecalculated; ++i)
    1193       77975 :       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       12785 :   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       12785 :     Operations.reserve(AllUpdates.size());
    1223             : 
    1224      213693 :     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      200908 :       Operations[{From, To}] += (U.getKind() == UpdateKind::Insert ? 1 : -1);
    1230             :     }
    1231             : 
    1232             :     Result.clear();
    1233       12785 :     Result.reserve(Operations.size());
    1234      226466 :     for (auto &Op : Operations) {
    1235      100448 :       const int NumInsertions = Op.second;
    1236             :       assert(std::abs(NumInsertions) <= 1 && "Unbalanced operations!");
    1237      100448 :       if (NumInsertions == 0) continue;
    1238      100446 :       const UpdateKind UK =
    1239             :           NumInsertions > 0 ? UpdateKind::Insert : UpdateKind::Delete;
    1240      200892 :       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      213693 :     for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) {
    1248             :       const auto &U = AllUpdates[i];
    1249             :       if (!IsPostDom)
    1250      100237 :         Operations[{U.getFrom(), U.getTo()}] = int(i);
    1251             :       else
    1252         231 :         Operations[{U.getTo(), U.getFrom()}] = int(i);
    1253             :     }
    1254             : 
    1255             :     llvm::sort(Result.begin(), Result.end(),
    1256     1393881 :                [&Operations](const UpdateT &A, const UpdateT &B) {
    1257     1395213 :                  return Operations[{A.getFrom(), A.getTo()}] >
    1258      465959 :                         Operations[{B.getFrom(), B.getTo()}];
    1259      929254 :                });
    1260       12785 :   }
    1261             : 
    1262       77975 :   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.
    1269      155950 :     auto &FS = BUI.FutureSuccessors[CurrentUpdate.getFrom()];
    1270       77975 :     FS.erase({CurrentUpdate.getTo(), CurrentUpdate.getKind()});
    1271       77975 :     if (FS.empty()) BUI.FutureSuccessors.erase(CurrentUpdate.getFrom());
    1272             : 
    1273      155950 :     auto &FP = BUI.FuturePredecessors[CurrentUpdate.getTo()];
    1274       77975 :     FP.erase({CurrentUpdate.getFrom(), CurrentUpdate.getKind()});
    1275       77975 :     if (FP.empty()) BUI.FuturePredecessors.erase(CurrentUpdate.getTo());
    1276             : 
    1277       77975 :     if (CurrentUpdate.getKind() == UpdateKind::Insert)
    1278       34310 :       InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
    1279             :     else
    1280       43665 :       DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
    1281       77975 :   }
    1282             : 
    1283             :   //~~
    1284             :   //===--------------- DomTree correctness verification ---------------------===
    1285             :   //~~
    1286             : 
    1287             :   // Check if the tree has correct roots. A DominatorTree always has a single
    1288             :   // root which is the function's entry node. A PostDominatorTree can have
    1289             :   // multiple roots - one for each node with no successors and for infinite
    1290             :   // loops.
    1291             :   // Running time: O(N).
    1292         617 :   bool verifyRoots(const DomTreeT &DT) {
    1293         617 :     if (!DT.Parent && !DT.Roots.empty()) {
    1294           0 :       errs() << "Tree has no parent but has roots!\n";
    1295           0 :       errs().flush();
    1296             :       return false;
    1297             :     }
    1298             : 
    1299             :     if (!IsPostDom) {
    1300         324 :       if (DT.Roots.empty()) {
    1301           0 :         errs() << "Tree doesn't have a root!\n";
    1302           0 :         errs().flush();
    1303             :         return false;
    1304             :       }
    1305             : 
    1306         324 :       if (DT.getRoot() != GetEntryNode(DT)) {
    1307           0 :         errs() << "Tree's root is not its parent's entry node!\n";
    1308           0 :         errs().flush();
    1309             :         return false;
    1310             :       }
    1311             :     }
    1312             : 
    1313         293 :     RootsT ComputedRoots = FindRoots(DT, nullptr);
    1314        1234 :     if (DT.Roots.size() != ComputedRoots.size() ||
    1315             :         !std::is_permutation(DT.Roots.begin(), DT.Roots.end(),
    1316             :                              ComputedRoots.begin())) {
    1317           0 :       errs() << "Tree has different roots than freshly computed ones!\n";
    1318           0 :       errs() << "\tPDT roots: ";
    1319           0 :       for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", ";
    1320           0 :       errs() << "\n\tComputed roots: ";
    1321           0 :       for (const NodePtr N : ComputedRoots)
    1322           0 :         errs() << BlockNamePrinter(N) << ", ";
    1323           0 :       errs() << "\n";
    1324           0 :       errs().flush();
    1325             :       return false;
    1326             :     }
    1327             : 
    1328             :     return true;
    1329             :   }
    1330             : 
    1331             :   // Checks if the tree contains all reachable nodes in the input graph.
    1332             :   // Running time: O(N).
    1333         617 :   bool verifyReachability(const DomTreeT &DT) {
    1334         617 :     clear();
    1335         293 :     doFullDFSWalk(DT, AlwaysDescend);
    1336             : 
    1337        7618 :     for (auto &NodeToTN : DT.DomTreeNodes) {
    1338             :       const TreeNodePtr TN = NodeToTN.second.get();
    1339           0 :       const NodePtr BB = TN->getBlock();
    1340             : 
    1341             :       // Virtual root has a corresponding virtual CFG node.
    1342         293 :       if (DT.isVirtualRoot(TN)) continue;
    1343             : 
    1344        6091 :       if (NodeToInfo.count(BB) == 0) {
    1345           0 :         errs() << "DomTree node " << BlockNamePrinter(BB)
    1346             :                << " not found by DFS walk!\n";
    1347           0 :         errs().flush();
    1348             : 
    1349           0 :         return false;
    1350             :       }
    1351             :     }
    1352             : 
    1353        7618 :     for (const NodePtr N : NumToNode) {
    1354       13092 :       if (N && !DT.getNode(N)) {
    1355           0 :         errs() << "CFG node " << BlockNamePrinter(N)
    1356             :                << " not found in the DomTree!\n";
    1357           0 :         errs().flush();
    1358             : 
    1359             :         return false;
    1360             :       }
    1361             :     }
    1362             : 
    1363             :     return true;
    1364             :   }
    1365             : 
    1366             :   // Check if for every parent with a level L in the tree all of its children
    1367             :   // have level L + 1.
    1368             :   // Running time: O(N).
    1369         617 :   static bool VerifyLevels(const DomTreeT &DT) {
    1370        7618 :     for (auto &NodeToTN : DT.DomTreeNodes) {
    1371             :       const TreeNodePtr TN = NodeToTN.second.get();
    1372           0 :       const NodePtr BB = TN->getBlock();
    1373        6384 :       if (!BB) continue;
    1374             : 
    1375           0 :       const TreeNodePtr IDom = TN->getIDom();
    1376        6415 :       if (!IDom && TN->getLevel() != 0) {
    1377           0 :         errs() << "Node without an IDom " << BlockNamePrinter(BB)
    1378           0 :                << " has a nonzero level " << TN->getLevel() << "!\n";
    1379           0 :         errs().flush();
    1380             : 
    1381           0 :         return false;
    1382             :       }
    1383             : 
    1384       11858 :       if (IDom && TN->getLevel() != IDom->getLevel() + 1) {
    1385           0 :         errs() << "Node " << BlockNamePrinter(BB) << " has level "
    1386           0 :                << TN->getLevel() << " while its IDom "
    1387           0 :                << BlockNamePrinter(IDom->getBlock()) << " has level "
    1388           0 :                << IDom->getLevel() << "!\n";
    1389           0 :         errs().flush();
    1390             : 
    1391             :         return false;
    1392             :       }
    1393             :     }
    1394             : 
    1395         617 :     return true;
    1396             :   }
    1397             : 
    1398             :   // Check if the computed DFS numbers are correct. Note that DFS info may not
    1399             :   // be valid, and when that is the case, we don't verify the numbers.
    1400             :   // Running time: O(N log(N)).
    1401         617 :   static bool VerifyDFSNumbers(const DomTreeT &DT) {
    1402         617 :     if (!DT.DFSInfoValid || !DT.Parent)
    1403             :       return true;
    1404             : 
    1405           1 :     const NodePtr RootBB = IsPostDom ? nullptr : DT.getRoots()[0];
    1406             :     const TreeNodePtr Root = DT.getNode(RootBB);
    1407             : 
    1408           0 :     auto PrintNodeAndDFSNums = [](const TreeNodePtr TN) {
    1409           0 :       errs() << BlockNamePrinter(TN) << " {" << TN->getDFSNumIn() << ", "
    1410           0 :              << TN->getDFSNumOut() << '}';
    1411           0 :     };
    1412             : 
    1413             :     // Verify the root's DFS In number. Although DFS numbering would also work
    1414             :     // if we started from some other value, we assume 0-based numbering.
    1415           1 :     if (Root->getDFSNumIn() != 0) {
    1416           0 :       errs() << "DFSIn number for the tree root is not:\n\t";
    1417           0 :       PrintNodeAndDFSNums(Root);
    1418           0 :       errs() << '\n';
    1419           0 :       errs().flush();
    1420             :       return false;
    1421             :     }
    1422             : 
    1423             :     // For each tree node verify if children's DFS numbers cover their parent's
    1424             :     // DFS numbers with no gaps.
    1425           7 :     for (const auto &NodeToTN : DT.DomTreeNodes) {
    1426             :       const TreeNodePtr Node = NodeToTN.second.get();
    1427             : 
    1428             :       // Handle tree leaves.
    1429           8 :       if (Node->getChildren().empty()) {
    1430           6 :         if (Node->getDFSNumIn() + 1 != Node->getDFSNumOut()) {
    1431           0 :           errs() << "Tree leaf should have DFSOut = DFSIn + 1:\n\t";
    1432           0 :           PrintNodeAndDFSNums(Node);
    1433           0 :           errs() << '\n';
    1434           0 :           errs().flush();
    1435           0 :           return false;
    1436             :         }
    1437             : 
    1438           3 :         continue;
    1439             :       }
    1440             : 
    1441             :       // Make a copy and sort it such that it is possible to check if there are
    1442             :       // no gaps between DFS numbers of adjacent children.
    1443             :       SmallVector<TreeNodePtr, 8> Children(Node->begin(), Node->end());
    1444             :       llvm::sort(Children.begin(), Children.end(),
    1445             :                  [](const TreeNodePtr Ch1, const TreeNodePtr Ch2) {
    1446           0 :                    return Ch1->getDFSNumIn() < Ch2->getDFSNumIn();
    1447             :                  });
    1448             : 
    1449           2 :       auto PrintChildrenError = [Node, &Children, PrintNodeAndDFSNums](
    1450           0 :           const TreeNodePtr FirstCh, const TreeNodePtr SecondCh) {
    1451             :         assert(FirstCh);
    1452             : 
    1453           0 :         errs() << "Incorrect DFS numbers for:\n\tParent ";
    1454           0 :         PrintNodeAndDFSNums(Node);
    1455             : 
    1456           0 :         errs() << "\n\tChild ";
    1457           0 :         PrintNodeAndDFSNums(FirstCh);
    1458             : 
    1459           0 :         if (SecondCh) {
    1460           0 :           errs() << "\n\tSecond child ";
    1461           0 :           PrintNodeAndDFSNums(SecondCh);
    1462             :         }
    1463             : 
    1464           0 :         errs() << "\nAll children: ";
    1465           0 :         for (const TreeNodePtr Ch : Children) {
    1466           0 :           PrintNodeAndDFSNums(Ch);
    1467           0 :           errs() << ", ";
    1468             :         }
    1469             : 
    1470           0 :         errs() << '\n';
    1471           0 :         errs().flush();
    1472           0 :       };
    1473             : 
    1474           4 :       if (Children.front()->getDFSNumIn() != Node->getDFSNumIn() + 1) {
    1475           0 :         PrintChildrenError(Children.front(), nullptr);
    1476           0 :         return false;
    1477             :       }
    1478             : 
    1479           6 :       if (Children.back()->getDFSNumOut() + 1 != Node->getDFSNumOut()) {
    1480           0 :         PrintChildrenError(Children.back(), nullptr);
    1481           0 :         return false;
    1482             :       }
    1483             : 
    1484           2 :       for (size_t i = 0, e = Children.size() - 1; i != e; ++i) {
    1485           8 :         if (Children[i]->getDFSNumOut() + 1 != Children[i + 1]->getDFSNumIn()) {
    1486           0 :           PrintChildrenError(Children[i], Children[i + 1]);
    1487           0 :           return false;
    1488             :         }
    1489             :       }
    1490             :     }
    1491             : 
    1492           1 :     return true;
    1493             :   }
    1494             : 
    1495             :   // The below routines verify the correctness of the dominator tree relative to
    1496             :   // the CFG it's coming from.  A tree is a dominator tree iff it has two
    1497             :   // properties, called the parent property and the sibling property.  Tarjan
    1498             :   // and Lengauer prove (but don't explicitly name) the properties as part of
    1499             :   // the proofs in their 1972 paper, but the proofs are mostly part of proving
    1500             :   // things about semidominators and idoms, and some of them are simply asserted
    1501             :   // based on even earlier papers (see, e.g., lemma 2).  Some papers refer to
    1502             :   // these properties as "valid" and "co-valid".  See, e.g., "Dominators,
    1503             :   // directed bipolar orders, and independent spanning trees" by Loukas
    1504             :   // Georgiadis and Robert E. Tarjan, as well as "Dominator Tree Verification
    1505             :   // and Vertex-Disjoint Paths " by the same authors.
    1506             : 
    1507             :   // A very simple and direct explanation of these properties can be found in
    1508             :   // "An Experimental Study of Dynamic Dominators", found at
    1509             :   // https://arxiv.org/abs/1604.02711
    1510             : 
    1511             :   // The easiest way to think of the parent property is that it's a requirement
    1512             :   // of being a dominator.  Let's just take immediate dominators.  For PARENT to
    1513             :   // be an immediate dominator of CHILD, all paths in the CFG must go through
    1514             :   // PARENT before they hit CHILD.  This implies that if you were to cut PARENT
    1515             :   // out of the CFG, there should be no paths to CHILD that are reachable.  If
    1516             :   // there are, then you now have a path from PARENT to CHILD that goes around
    1517             :   // PARENT and still reaches CHILD, which by definition, means PARENT can't be
    1518             :   // a dominator of CHILD (let alone an immediate one).
    1519             : 
    1520             :   // The sibling property is similar.  It says that for each pair of sibling
    1521             :   // nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each
    1522             :   // other.  If sibling LEFT dominated sibling RIGHT, it means there are no
    1523             :   // paths in the CFG from sibling LEFT to sibling RIGHT that do not go through
    1524             :   // LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of
    1525             :   // RIGHT, not a sibling.
    1526             : 
    1527             :   // It is possible to verify the parent and sibling properties in
    1528             :   // linear time, but the algorithms are complex. Instead, we do it in a
    1529             :   // straightforward N^2 and N^3 way below, using direct path reachability.
    1530             : 
    1531             :   // Checks if the tree has the parent property: if for all edges from V to W in
    1532             :   // the input graph, such that V is reachable, the parent of W in the tree is
    1533             :   // an ancestor of V in the tree.
    1534             :   // Running time: O(N^2).
    1535             :   //
    1536             :   // This means that if a node gets disconnected from the graph, then all of
    1537             :   // the nodes it dominated previously will now become unreachable.
    1538         617 :   bool verifyParentProperty(const DomTreeT &DT) {
    1539        7618 :     for (auto &NodeToTN : DT.DomTreeNodes) {
    1540             :       const TreeNodePtr TN = NodeToTN.second.get();
    1541           0 :       const NodePtr BB = TN->getBlock();
    1542       12475 :       if (!BB || TN->getChildren().empty()) continue;
    1543             : 
    1544             :       LLVM_DEBUG(dbgs() << "Verifying parent property of node "
    1545             :                         << BlockNamePrinter(TN) << "\n");
    1546        3349 :       clear();
    1547       22163 :       doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) {
    1548       20512 :         return From != BB && To != BB;
    1549       20512 :       });
    1550             : 
    1551        3349 :       for (TreeNodePtr Child : TN->getChildren())
    1552        4459 :         if (NodeToInfo.count(Child->getBlock()) != 0) {
    1553           0 :           errs() << "Child " << BlockNamePrinter(Child)
    1554           0 :                  << " reachable after its parent " << BlockNamePrinter(BB)
    1555             :                  << " is removed!\n";
    1556           0 :           errs().flush();
    1557             : 
    1558             :           return false;
    1559             :         }
    1560             :     }
    1561             : 
    1562         617 :     return true;
    1563             :   }
    1564             : 
    1565             :   // Check if the tree has sibling property: if a node V does not dominate a
    1566             :   // node W for all siblings V and W in the tree.
    1567             :   // Running time: O(N^3).
    1568             :   //
    1569             :   // This means that if a node gets disconnected from the graph, then all of its
    1570             :   // siblings will now still be reachable.
    1571         617 :   bool verifySiblingProperty(const DomTreeT &DT) {
    1572        7618 :     for (auto &NodeToTN : DT.DomTreeNodes) {
    1573             :       const TreeNodePtr TN = NodeToTN.second.get();
    1574           0 :       const NodePtr BB = TN->getBlock();
    1575       12475 :       if (!BB || TN->getChildren().empty()) continue;
    1576             : 
    1577             :       const auto &Siblings = TN->getChildren();
    1578        7808 :       for (const TreeNodePtr N : Siblings) {
    1579        4459 :         clear();
    1580           0 :         NodePtr BBN = N->getBlock();
    1581       36500 :         doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) {
    1582       34467 :           return From != BBN && To != BBN;
    1583       34467 :         });
    1584             : 
    1585        4459 :         for (const TreeNodePtr S : Siblings) {
    1586        7223 :           if (S == N) continue;
    1587             : 
    1588        2764 :           if (NodeToInfo.count(S->getBlock()) == 0) {
    1589           0 :             errs() << "Node " << BlockNamePrinter(S)
    1590           0 :                    << " not reachable when its sibling " << BlockNamePrinter(N)
    1591             :                    << " is removed!\n";
    1592           0 :             errs().flush();
    1593             : 
    1594             :             return false;
    1595             :           }
    1596             :         }
    1597             :       }
    1598             :     }
    1599             : 
    1600         617 :     return true;
    1601             :   }
    1602             : 
    1603             :   // Check if the given tree is the same as a freshly computed one for the same
    1604             :   // Parent.
    1605             :   // Running time: O(N^2), but faster in practise (same as tree construction).
    1606             :   //
    1607             :   // Note that this does not check if that the tree construction algorithm is
    1608             :   // correct and should be only used for fast (but possibly unsound)
    1609             :   // verification.
    1610         617 :   static bool IsSameAsFreshTree(const DomTreeT &DT) {
    1611         617 :     DomTreeT FreshTree;
    1612         617 :     FreshTree.recalculate(*DT.Parent);
    1613         617 :     const bool Different = DT.compare(FreshTree);
    1614             : 
    1615         617 :     if (Different) {
    1616           0 :       errs() << (DT.isPostDominator() ? "Post" : "")
    1617           0 :              << "DominatorTree is different than a freshly computed one!\n"
    1618             :              << "\tCurrent:\n";
    1619           0 :       DT.print(errs());
    1620           0 :       errs() << "\n\tFreshly computed tree:\n";
    1621           0 :       FreshTree.print(errs());
    1622           0 :       errs().flush();
    1623             :     }
    1624             : 
    1625        1234 :     return !Different;
    1626             :   }
    1627             : };
    1628             : 
    1629             : template <class DomTreeT>
    1630     2569265 : void Calculate(DomTreeT &DT) {
    1631     4407381 :   SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, nullptr);
    1632     2569265 : }
    1633             : 
    1634             : template <class DomTreeT>
    1635         448 : void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
    1636             :                 typename DomTreeT::NodePtr To) {
    1637             :   if (DT.isPostDominator()) std::swap(From, To);
    1638         448 :   SemiNCAInfo<DomTreeT>::InsertEdge(DT, nullptr, From, To);
    1639         448 : }
    1640             : 
    1641             : template <class DomTreeT>
    1642        1303 : void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
    1643             :                 typename DomTreeT::NodePtr To) {
    1644             :   if (DT.isPostDominator()) std::swap(From, To);
    1645        1303 :   SemiNCAInfo<DomTreeT>::DeleteEdge(DT, nullptr, From, To);
    1646        1303 : }
    1647             : 
    1648             : template <class DomTreeT>
    1649       12857 : void ApplyUpdates(DomTreeT &DT,
    1650             :                   ArrayRef<typename DomTreeT::UpdateType> Updates) {
    1651       12857 :   SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, Updates);
    1652       12857 : }
    1653             : 
    1654             : template <class DomTreeT>
    1655         617 : bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) {
    1656        1234 :   SemiNCAInfo<DomTreeT> SNCA(nullptr);
    1657             : 
    1658             :   // Simplist check is to compare against a new tree. This will also
    1659             :   // usefully print the old and new trees, if they are different.
    1660         617 :   if (!SNCA.IsSameAsFreshTree(DT))
    1661             :     return false;
    1662             : 
    1663             :   // Common checks to verify the properties of the tree. O(N log N) at worst
    1664        1851 :   if (!SNCA.verifyRoots(DT) || !SNCA.verifyReachability(DT) ||
    1665        1851 :       !SNCA.VerifyLevels(DT) || !SNCA.VerifyDFSNumbers(DT))
    1666             :     return false;
    1667             : 
    1668             :   // Extra checks depending on VerificationLevel. Up to O(N^3)
    1669         617 :   if (VL == DomTreeT::VerificationLevel::Basic ||
    1670             :       VL == DomTreeT::VerificationLevel::Full)
    1671         617 :     if (!SNCA.verifyParentProperty(DT))
    1672             :       return false;
    1673         617 :   if (VL == DomTreeT::VerificationLevel::Full)
    1674         617 :     if (!SNCA.verifySiblingProperty(DT))
    1675             :       return false;
    1676             : 
    1677             :   return true;
    1678             : }
    1679             : 
    1680             : }  // namespace DomTreeBuilder
    1681             : }  // namespace llvm
    1682             : 
    1683             : #undef DEBUG_TYPE
    1684             : 
    1685             : #endif

Generated by: LCOV version 1.13