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