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