Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- GenericDomTreeConstruction.h - Dominator Calculation ------*- C++ -*-==//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

/// \file

///

/// Generic dominator tree construction - this file provides routines to

/// construct immediate dominator information for a flow-graph based on the

/// Semi-NCA algorithm described in this dissertation:

///

///   [1] Linear-Time Algorithms for Dominators and Related Problems

///   Loukas Georgiadis, Princeton University, November 2005, pp. 21-23:

///   ftp://ftp.cs.princeton.edu/reports/2005/737.pdf

///

/// Semi-NCA algorithm runs in O(n^2) worst-case time but usually slightly

/// faster than Simple Lengauer-Tarjan in practice.

///

/// O(n^2) worst cases happen when the computation of nearest common ancestors

/// requires O(n) average time, which is very unlikely in real world. If this

/// ever turns out to be an issue, consider implementing a hybrid algorithm

/// that uses SLT to perform full constructions and SemiNCA for incremental

/// updates.

///

/// The file uses the Depth Based Search algorithm to perform incremental

/// updates (insertion and deletions). The implemented algorithm is based on

/// this publication:

///

///   [2] An Experimental Study of Dynamic Dominators

///   Loukas Georgiadis, et al., April 12 2016, pp. 5-7, 9-10:

///   https://arxiv.org/pdf/1604.02711.pdf

///

//===----------------------------------------------------------------------===//

#ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H

#define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/DenseSet.h"

#include "llvm/ADT/DepthFirstIterator.h"

#include "llvm/ADT/PointerIntPair.h"

#include "llvm/ADT/SmallPtrSet.h"

#include "llvm/Support/Debug.h"

#include "llvm/Support/GenericDomTree.h"

#include <optional>

#include <queue>

#define DEBUG_TYPE "dom-tree-builder"

namespace llvm {

namespace DomTreeBuilder {

template <typename DomTreeT>

struct SemiNCAInfo {

  using NodePtr = typename DomTreeT::NodePtr;

  using NodeT = typename DomTreeT::NodeType;

  using TreeNodePtr = DomTreeNodeBase<NodeT> *;

  using RootsT = decltype(DomTreeT::Roots);

  static constexpr bool IsPostDom = DomTreeT::IsPostDominator;

  using GraphDiffT = GraphDiff<NodePtr, IsPostDom>;

  // Information record used by Semi-NCA during tree construction.

  struct InfoRec {

    unsigned DFSNum = 0;

    unsigned Parent = 0;

    unsigned Semi = 0;

    NodePtr Label = nullptr;

    NodePtr IDom = nullptr;

    SmallVector<NodePtr, 2> ReverseChildren;

  };

  // Number to node mapping is 1-based. Initialize the mapping to start with

  // a dummy element.

  std::vector<NodePtr> NumToNode = {nullptr};

  DenseMap<NodePtr, InfoRec> NodeToInfo;

  using UpdateT = typename DomTreeT::UpdateType;

  using UpdateKind = typename DomTreeT::UpdateKind;

  struct BatchUpdateInfo {

    // Note: Updates inside PreViewCFG are already legalized.

    BatchUpdateInfo(GraphDiffT &PreViewCFG, GraphDiffT *PostViewCFG = nullptr)

        : PreViewCFG(PreViewCFG), PostViewCFG(PostViewCFG),

          NumLegalized(PreViewCFG.getNumLegalizedUpdates()) {}

    // Remembers if the whole tree was recalculated at some point during the

    // current batch update.

    bool IsRecalculated = false;

    GraphDiffT &PreViewCFG;

    GraphDiffT *PostViewCFG;

    const size_t NumLegalized;

  };

  BatchUpdateInfo *BatchUpdates;

  using BatchUpdatePtr = BatchUpdateInfo *;

  // If BUI is a nullptr, then there's no batch update in progress.

  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}

  void clear() {

    NumToNode = {nullptr}; // Restore to initial state with a dummy start node.

    NodeToInfo.clear();

    // Don't reset the pointer to BatchUpdateInfo here -- if there's an update

    // in progress, we need this information to continue it.

  }

  template <bool Inversed>

  static SmallVector<NodePtr, 8> getChildren(NodePtr N, BatchUpdatePtr BUI) {

    if (BUI)

      return BUI->PreViewCFG.template getChildren<Inversed>(N);

    return getChildren<Inversed>(N);

  }

  template <bool Inversed>

  static SmallVector<NodePtr, 8> getChildren(NodePtr N) {

    using DirectedNodeT =

        std::conditional_t<Inversed, Inverse<NodePtr>, NodePtr>;

    auto R = children<DirectedNodeT>(N);

    SmallVector<NodePtr, 8> Res(detail::reverse_if<!Inversed>(R));

    // Remove nullptr children for clang.

    llvm::erase_value(Res, nullptr);

    return Res;

  }

  NodePtr getIDom(NodePtr BB) const {

    auto InfoIt = NodeToInfo.find(BB);

    if (InfoIt == NodeToInfo.end()) return nullptr;

    return InfoIt->second.IDom;

  }

  TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT) {

    if (TreeNodePtr Node = DT.getNode(BB)) return Node;

    // Haven't calculated this node yet?  Get or calculate the node for the

    // immediate dominator.

    NodePtr IDom = getIDom(BB);

    assert(IDom || DT.DomTreeNodes[nullptr]);

    TreeNodePtr IDomNode = getNodeForBlock(IDom, DT);

    // Add a new tree node for this NodeT, and link it as a child of

    // IDomNode

    return DT.createChild(BB, IDomNode);

  }

  static bool AlwaysDescend(NodePtr, NodePtr) { return true; }

  struct BlockNamePrinter {

    NodePtr N;

    BlockNamePrinter(NodePtr Block) : N(Block) {}

    BlockNamePrinter(TreeNodePtr TN) : N(TN ? TN->getBlock() : nullptr) {}

    friend raw_ostream &operator<<(raw_ostream &O, const BlockNamePrinter &BP) {

      if (!BP.N)

        O << "nullptr";

      else

        BP.N->printAsOperand(O, false);

      return O;

    }

  };

  using NodeOrderMap = DenseMap<NodePtr, unsigned>;

  // Custom DFS implementation which can skip nodes based on a provided

  // predicate. It also collects ReverseChildren so that we don't have to spend

  // time getting predecessors in SemiNCA.

  //

  // If IsReverse is set to true, the DFS walk will be performed backwards

  // relative to IsPostDom -- using reverse edges for dominators and forward

  // edges for postdominators.

  //

  // If SuccOrder is specified then in this order the DFS traverses the children

  // otherwise the order is implied by the results of getChildren().

  template <bool IsReverse = false, typename DescendCondition>

  unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,

                  unsigned AttachToNum,

                  const NodeOrderMap *SuccOrder = nullptr) {

    assert(V);

    SmallVector<NodePtr, 64> WorkList = {V};

    if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum;

    while (!WorkList.empty()) {

      const NodePtr BB = WorkList.pop_back_val();

      auto &BBInfo = NodeToInfo[BB];

      // Visited nodes always have positive DFS numbers.

      if (BBInfo.DFSNum != 0) continue;

      BBInfo.DFSNum = BBInfo.Semi = ++LastNum;

      BBInfo.Label = BB;

      NumToNode.push_back(BB);

      constexpr bool Direction = IsReverse != IsPostDom;  // XOR.

      auto Successors = getChildren<Direction>(BB, BatchUpdates);

      if (SuccOrder && Successors.size() > 1)

        llvm::sort(

            Successors.begin(), Successors.end(), [=](NodePtr A, NodePtr B) {

              return SuccOrder->find(A)->second < SuccOrder->find(B)->second;

            });

      for (const NodePtr Succ : Successors) {

        const auto SIT = NodeToInfo.find(Succ);

        // Don't visit nodes more than once but remember to collect

        // ReverseChildren.

        if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {

          if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);

          continue;

        }

        if (!Condition(BB, Succ)) continue;

        // It's fine to add Succ to the map, because we know that it will be

        // visited later.

        auto &SuccInfo = NodeToInfo[Succ];

        WorkList.push_back(Succ);

        SuccInfo.Parent = LastNum;

        SuccInfo.ReverseChildren.push_back(BB);

      }

    }

    return LastNum;

  }

  // V is a predecessor of W. eval() returns V if V < W, otherwise the minimum

  // of sdom(U), where U > W and there is a virtual forest path from U to V. The

  // virtual forest consists of linked edges of processed vertices.

  //

  // We can follow Parent pointers (virtual forest edges) to determine the

  // ancestor U with minimum sdom(U). But it is slow and thus we employ the path

  // compression technique to speed up to O(m*log(n)). Theoretically the virtual

  // forest can be organized as balanced trees to achieve almost linear

  // O(m*alpha(m,n)) running time. But it requires two auxiliary arrays (Size

  // and Child) and is unlikely to be faster than the simple implementation.

  //

  // For each vertex V, its Label points to the vertex with the minimal sdom(U)

  // (Semi) in its path from V (included) to NodeToInfo[V].Parent (excluded).

  NodePtr eval(NodePtr V, unsigned LastLinked,

               SmallVectorImpl<InfoRec *> &Stack) {

    InfoRec *VInfo = &NodeToInfo[V];

    if (VInfo->Parent < LastLinked)

      return VInfo->Label;

    // Store ancestors except the last (root of a virtual tree) into a stack.

    assert(Stack.empty());

    do {

      Stack.push_back(VInfo);

      VInfo = &NodeToInfo[NumToNode[VInfo->Parent]];

    } while (VInfo->Parent >= LastLinked);

    // Path compression. Point each vertex's Parent to the root and update its

    // Label if any of its ancestors (PInfo->Label) has a smaller Semi.

    const InfoRec *PInfo = VInfo;

    const InfoRec *PLabelInfo = &NodeToInfo[PInfo->Label];

    do {

      VInfo = Stack.pop_back_val();

      VInfo->Parent = PInfo->Parent;

      const InfoRec *VLabelInfo = &NodeToInfo[VInfo->Label];

      if (PLabelInfo->Semi < VLabelInfo->Semi)

        VInfo->Label = PInfo->Label;

      else

        PLabelInfo = VLabelInfo;

      PInfo = VInfo;

    } while (!Stack.empty());

    return VInfo->Label;

  }

  // This function requires DFS to be run before calling it.

  void runSemiNCA(DomTreeT &DT, const unsigned MinLevel = 0) {

    const unsigned NextDFSNum(NumToNode.size());

    // Initialize IDoms to spanning tree parents.

    for (unsigned i = 1; i < NextDFSNum; ++i) {

      const NodePtr V = NumToNode[i];

      auto &VInfo = NodeToInfo[V];

      VInfo.IDom = NumToNode[VInfo.Parent];

    }

    // Step #1: Calculate the semidominators of all vertices.

    SmallVector<InfoRec *, 32> EvalStack;

    for (unsigned i = NextDFSNum - 1; i >= 2; --i) {

      NodePtr W = NumToNode[i];

      auto &WInfo = NodeToInfo[W];

      // Initialize the semi dominator to point to the parent node.

      WInfo.Semi = WInfo.Parent;

      for (const auto &N : WInfo.ReverseChildren) {

        if (NodeToInfo.count(N) == 0)  // Skip unreachable predecessors.

          continue;

        const TreeNodePtr TN = DT.getNode(N);

        // Skip predecessors whose level is above the subtree we are processing.

        if (TN && TN->getLevel() < MinLevel)

          continue;

        unsigned SemiU = NodeToInfo[eval(N, i + 1, EvalStack)].Semi;

        if (SemiU < WInfo.Semi) WInfo.Semi = SemiU;

      }

    }

    // Step #2: Explicitly define the immediate dominator of each vertex.

    //          IDom[i] = NCA(SDom[i], SpanningTreeParent(i)).

    // Note that the parents were stored in IDoms and later got invalidated

    // during path compression in Eval.

    for (unsigned i = 2; i < NextDFSNum; ++i) {

      const NodePtr W = NumToNode[i];

      auto &WInfo = NodeToInfo[W];

      const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;

      NodePtr WIDomCandidate = WInfo.IDom;

      while (NodeToInfo[WIDomCandidate].DFSNum > SDomNum)

        WIDomCandidate = NodeToInfo[WIDomCandidate].IDom;

      WInfo.IDom = WIDomCandidate;

    }

  }

  // PostDominatorTree always has a virtual root that represents a virtual CFG

  // node that serves as a single exit from the function. All the other exits

  // (CFG nodes with terminators and nodes in infinite loops are logically

  // connected to this virtual CFG exit node).

  // This functions maps a nullptr CFG node to the virtual root tree node.

  void addVirtualRoot() {

    assert(IsPostDom && "Only postdominators have a virtual root");

    assert(NumToNode.size() == 1 && "SNCAInfo must be freshly constructed");

    auto &BBInfo = NodeToInfo[nullptr];

    BBInfo.DFSNum = BBInfo.Semi = 1;

    BBInfo.Label = nullptr;

    NumToNode.push_back(nullptr);  // NumToNode[1] = nullptr;

  }

  // For postdominators, nodes with no forward successors are trivial roots that

  // are always selected as tree roots. Roots with forward successors correspond

  // to CFG nodes within infinite loops.

  static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI) {

    assert(N && "N must be a valid node");

    return !getChildren<false>(N, BUI).empty();

  }

  static NodePtr GetEntryNode(const DomTreeT &DT) {

    assert(DT.Parent && "Parent not set");

    return GraphTraits<typename DomTreeT::ParentPtr>::getEntryNode(DT.Parent);

  }

  // Finds all roots without relaying on the set of roots already stored in the

  // tree.

  // We define roots to be some non-redundant set of the CFG nodes

  static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI) {

    assert(DT.Parent && "Parent pointer is not set");

    RootsT Roots;

    // For dominators, function entry CFG node is always a tree root node.

    if (!IsPostDom) {

      Roots.push_back(GetEntryNode(DT));

      return Roots;

    }

    SemiNCAInfo SNCA(BUI);

    // PostDominatorTree always has a virtual root.

    SNCA.addVirtualRoot();

    unsigned Num = 1;

    LLVM_DEBUG(dbgs() << "\t\tLooking for trivial roots\n");

    // Step #1: Find all the trivial roots that are going to will definitely

    // remain tree roots.

    unsigned Total = 0;

    // It may happen that there are some new nodes in the CFG that are result of

    // the ongoing batch update, but we cannot really pretend that they don't

    // exist -- we won't see any outgoing or incoming edges to them, so it's

    // fine to discover them here, as they would end up appearing in the CFG at

    // some point anyway.

    for (const NodePtr N : nodes(DT.Parent)) {

      ++Total;

      // If it has no *successors*, it is definitely a root.

      if (!HasForwardSuccessors(N, BUI)) {

        Roots.push_back(N);

        // Run DFS not to walk this part of CFG later.

        Num = SNCA.runDFS(N, Num, AlwaysDescend, 1);

        LLVM_DEBUG(dbgs() << "Found a new trivial root: " << BlockNamePrinter(N)

                          << "\n");

        LLVM_DEBUG(dbgs() << "Last visited node: "

                          << BlockNamePrinter(SNCA.NumToNode[Num]) << "\n");

      }

    }

    LLVM_DEBUG(dbgs() << "\t\tLooking for non-trivial roots\n");

    // Step #2: Find all non-trivial root candidates. Those are CFG nodes that

    // are reverse-unreachable were not visited by previous DFS walks (i.e. CFG

    // nodes in infinite loops).

    bool HasNonTrivialRoots = false;

    // Accounting for the virtual exit, see if we had any reverse-unreachable

    // nodes.

    if (Total + 1 != Num) {

      HasNonTrivialRoots = true;

      // SuccOrder is the order of blocks in the function. It is needed to make

      // the calculation of the FurthestAway node and the whole PostDomTree

      // immune to swap successors transformation (e.g. canonicalizing branch

      // predicates). SuccOrder is initialized lazily only for successors of

      // reverse unreachable nodes.

      std::optional<NodeOrderMap> SuccOrder;

      auto InitSuccOrderOnce = [&]() {

        SuccOrder = NodeOrderMap();

        for (const auto Node : nodes(DT.Parent))

          if (SNCA.NodeToInfo.count(Node) == 0)

            for (const auto Succ : getChildren<false>(Node, SNCA.BatchUpdates))

              SuccOrder->try_emplace(Succ, 0);

        // Add mapping for all entries of SuccOrder.

        unsigned NodeNum = 0;

        for (const auto Node : nodes(DT.Parent)) {

          ++NodeNum;

          auto Order = SuccOrder->find(Node);

          if (Order != SuccOrder->end()) {

            assert(Order->second == 0);

            Order->second = NodeNum;

          }

        }

      };

      // Make another DFS pass over all other nodes to find the

      // reverse-unreachable blocks, and find the furthest paths we'll be able

      // to make.

      // Note that this looks N^2, but it's really 2N worst case, if every node

      // is unreachable. This is because we are still going to only visit each

      // unreachable node once, we may just visit it in two directions,

      // depending on how lucky we get.

      for (const NodePtr I : nodes(DT.Parent)) {

        if (SNCA.NodeToInfo.count(I) == 0) {

          LLVM_DEBUG(dbgs()

                     << "\t\t\tVisiting node " << BlockNamePrinter(I) << "\n");

          // Find the furthest away we can get by following successors, then

          // follow them in reverse.  This gives us some reasonable answer about

          // the post-dom tree inside any infinite loop. In particular, it

          // guarantees we get to the farthest away point along *some*

          // path. This also matches the GCC's behavior.

          // If we really wanted a totally complete picture of dominance inside

          // this infinite loop, we could do it with SCC-like algorithms to find

          // the lowest and highest points in the infinite loop.  In theory, it

          // would be nice to give the canonical backedge for the loop, but it's

          // expensive and does not always lead to a minimal set of roots.

          LLVM_DEBUG(dbgs() << "\t\t\tRunning forward DFS\n");

          if (!SuccOrder)

            InitSuccOrderOnce();

          assert(SuccOrder);

          const unsigned NewNum =

              SNCA.runDFS<true>(I, Num, AlwaysDescend, Num, &*SuccOrder);

          const NodePtr FurthestAway = SNCA.NumToNode[NewNum];

          LLVM_DEBUG(dbgs() << "\t\t\tFound a new furthest away node "

                            << "(non-trivial root): "

                            << BlockNamePrinter(FurthestAway) << "\n");

          Roots.push_back(FurthestAway);

          LLVM_DEBUG(dbgs() << "\t\t\tPrev DFSNum: " << Num << ", new DFSNum: "

                            << NewNum << "\n\t\t\tRemoving DFS info\n");

          for (unsigned i = NewNum; i > Num; --i) {

            const NodePtr N = SNCA.NumToNode[i];

            LLVM_DEBUG(dbgs() << "\t\t\t\tRemoving DFS info for "

                              << BlockNamePrinter(N) << "\n");

            SNCA.NodeToInfo.erase(N);

            SNCA.NumToNode.pop_back();

          }

          const unsigned PrevNum = Num;

          LLVM_DEBUG(dbgs() << "\t\t\tRunning reverse DFS\n");

          Num = SNCA.runDFS(FurthestAway, Num, AlwaysDescend, 1);

          for (unsigned i = PrevNum + 1; i <= Num; ++i)

            LLVM_DEBUG(dbgs() << "\t\t\t\tfound node "

                              << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");

        }

      }

    }

    LLVM_DEBUG(dbgs() << "Total: " << Total << ", Num: " << Num << "\n");

    LLVM_DEBUG(dbgs() << "Discovered CFG nodes:\n");

    LLVM_DEBUG(for (size_t i = 0; i <= Num; ++i) dbgs()

               << i << ": " << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");

    assert((Total + 1 == Num) && "Everything should have been visited");

    // Step #3: If we found some non-trivial roots, make them non-redundant.

    if (HasNonTrivialRoots) RemoveRedundantRoots(DT, BUI, Roots);

    LLVM_DEBUG(dbgs() << "Found roots: ");

    LLVM_DEBUG(for (auto *Root

                    : Roots) dbgs()

               << BlockNamePrinter(Root) << " ");

    LLVM_DEBUG(dbgs() << "\n");

    return Roots;

  }

  // This function only makes sense for postdominators.

  // We define roots to be some set of CFG nodes where (reverse) DFS walks have

  // to start in order to visit all the CFG nodes (including the

  // reverse-unreachable ones).

  // When the search for non-trivial roots is done it may happen that some of

  // the non-trivial roots are reverse-reachable from other non-trivial roots,

  // which makes them redundant. This function removes them from the set of

  // input roots.

  static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI,

                                   RootsT &Roots) {

    assert(IsPostDom && "This function is for postdominators only");

    LLVM_DEBUG(dbgs() << "Removing redundant roots\n");

    SemiNCAInfo SNCA(BUI);

    for (unsigned i = 0; i < Roots.size(); ++i) {

      auto &Root = Roots[i];

      // Trivial roots are always non-redundant.

      if (!HasForwardSuccessors(Root, BUI)) continue;

      LLVM_DEBUG(dbgs() << "\tChecking if " << BlockNamePrinter(Root)

                        << " remains a root\n");

      SNCA.clear();

      // Do a forward walk looking for the other roots.

      const unsigned Num = SNCA.runDFS<true>(Root, 0, AlwaysDescend, 0);

      // Skip the start node and begin from the second one (note that DFS uses

      // 1-based indexing).

      for (unsigned x = 2; x <= Num; ++x) {

        const NodePtr N = SNCA.NumToNode[x];

        // If we wound another root in a (forward) DFS walk, remove the current

        // root from the set of roots, as it is reverse-reachable from the other

        // one.

        if (llvm::is_contained(Roots, N)) {

          LLVM_DEBUG(dbgs() << "\tForward DFS walk found another root "

                            << BlockNamePrinter(N) << "\n\tRemoving root "

                            << BlockNamePrinter(Root) << "\n");

          std::swap(Root, Roots.back());

          Roots.pop_back();

          // Root at the back takes the current root's place.

          // Start the next loop iteration with the same index.

          --i;

          break;

        }

      }

    }

  }

  template <typename DescendCondition>

  void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {

    if (!IsPostDom) {

      assert(DT.Roots.size() == 1 && "Dominators should have a singe root");

      runDFS(DT.Roots[0], 0, DC, 0);

      return;

    }

    addVirtualRoot();

    unsigned Num = 1;

    for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0);

  }

  static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) {

    auto *Parent = DT.Parent;

    DT.reset();

    DT.Parent = Parent;

    // If the update is using the actual CFG, BUI is null. If it's using a view,

    // BUI is non-null and the PreCFGView is used. When calculating from

    // scratch, make the PreViewCFG equal to the PostCFGView, so Post is used.

    BatchUpdatePtr PostViewBUI = nullptr;

    if (BUI && BUI->PostViewCFG) {

      BUI->PreViewCFG = *BUI->PostViewCFG;

      PostViewBUI = BUI;

    }

    // This is rebuilding the whole tree, not incrementally, but PostViewBUI is

    // used in case the caller needs a DT update with a CFGView.

    SemiNCAInfo SNCA(PostViewBUI);

    // Step #0: Number blocks in depth-first order and initialize variables used

    // in later stages of the algorithm.

    DT.Roots = FindRoots(DT, PostViewBUI);

    SNCA.doFullDFSWalk(DT, AlwaysDescend);

    SNCA.runSemiNCA(DT);

    if (BUI) {

      BUI->IsRecalculated = true;

      LLVM_DEBUG(

          dbgs() << "DomTree recalculated, skipping future batch updates\n");

    }

    if (DT.Roots.empty()) return;

    // Add a node for the root. If the tree is a PostDominatorTree it will be

    // the virtual exit (denoted by (BasicBlock *) nullptr) which postdominates

    // all real exits (including multiple exit blocks, infinite loops).

    NodePtr Root = IsPostDom ? nullptr : DT.Roots[0];

    DT.RootNode = DT.createNode(Root);

    SNCA.attachNewSubtree(DT, DT.RootNode);

  }

  void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {

    // Attach the first unreachable block to AttachTo.

    NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();

    // Loop over all of the discovered blocks in the function...

    for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {

      NodePtr W = NumToNode[i];

      // Don't replace this with 'count', the insertion side effect is important

      if (DT.DomTreeNodes[W]) continue;  // Haven't calculated this node yet?

      NodePtr ImmDom = getIDom(W);

      // Get or calculate the node for the immediate dominator.

      TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);

      // Add a new tree node for this BasicBlock, and link it as a child of

      // IDomNode.

      DT.createChild(W, IDomNode);

    }

  }

  void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) {

    NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();

    for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {

      const NodePtr N = NumToNode[i];

      const TreeNodePtr TN = DT.getNode(N);

      assert(TN);

      const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom);

      TN->setIDom(NewIDom);

    }

  }

  // Helper struct used during edge insertions.

  struct InsertionInfo {

    struct Compare {

      bool operator()(TreeNodePtr LHS, TreeNodePtr RHS) const {

        return LHS->getLevel() < RHS->getLevel();

      }

    };

    // Bucket queue of tree nodes ordered by descending level. For simplicity,

    // we use a priority_queue here.

    std::priority_queue<TreeNodePtr, SmallVector<TreeNodePtr, 8>,

                        Compare>

        Bucket;

    SmallDenseSet<TreeNodePtr, 8> Visited;

    SmallVector<TreeNodePtr, 8> Affected;

#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS

    SmallVector<TreeNodePtr, 8> VisitedUnaffected;

#endif

  };

  static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI,

                         const NodePtr From, const NodePtr To) {

    assert((From || IsPostDom) &&

           "From has to be a valid CFG node or a virtual root");

    assert(To && "Cannot be a nullptr");

    LLVM_DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> "

                      << BlockNamePrinter(To) << "\n");

    TreeNodePtr FromTN = DT.getNode(From);

    if (!FromTN) {

      // Ignore edges from unreachable nodes for (forward) dominators.

      if (!IsPostDom) return;

      // The unreachable node becomes a new root -- a tree node for it.

      TreeNodePtr VirtualRoot = DT.getNode(nullptr);

      FromTN = DT.createChild(From, VirtualRoot);

      DT.Roots.push_back(From);

    }

    DT.DFSInfoValid = false;

    const TreeNodePtr ToTN = DT.getNode(To);

    if (!ToTN)

      InsertUnreachable(DT, BUI, FromTN, To);

    else

      InsertReachable(DT, BUI, FromTN, ToTN);

  }

  // Determines if some existing root becomes reverse-reachable after the

  // insertion. Rebuilds the whole tree if that situation happens.

  static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,

                                         const TreeNodePtr From,

                                         const TreeNodePtr To) {

    assert(IsPostDom && "This function is only for postdominators");

    // Destination node is not attached to the virtual root, so it cannot be a

    // root.

    if (!DT.isVirtualRoot(To->getIDom())) return false;

    if (!llvm::is_contained(DT.Roots, To->getBlock()))

      return false;  // To is not a root, nothing to update.

    LLVM_DEBUG(dbgs() << "\t\tAfter the insertion, " << BlockNamePrinter(To)

                      << " is no longer a root\n\t\tRebuilding the tree!!!\n");

    CalculateFromScratch(DT, BUI);

    return true;

  }

  static bool isPermutation(const SmallVectorImpl<NodePtr> &A,

                            const SmallVectorImpl<NodePtr> &B) {

    if (A.size() != B.size())

      return false;

    SmallPtrSet<NodePtr, 4> Set(A.begin(), A.end());

    for (NodePtr N : B)

      if (Set.count(N) == 0)

        return false;

    return true;

  }

  // Updates the set of roots after insertion or deletion. This ensures that

  // roots are the same when after a series of updates and when the tree would

  // be built from scratch.

  static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI) {

    assert(IsPostDom && "This function is only for postdominators");

    // The tree has only trivial roots -- nothing to update.

    if (llvm::none_of(DT.Roots, [BUI](const NodePtr N) {

          return HasForwardSuccessors(N, BUI);

        }))

      return;

    // Recalculate the set of roots.

    RootsT Roots = FindRoots(DT, BUI);

    if (!isPermutation(DT.Roots, Roots)) {

      // The roots chosen in the CFG have changed. This is because the

      // incremental algorithm does not really know or use the set of roots and

      // can make a different (implicit) decision about which node within an

      // infinite loop becomes a root.

      LLVM_DEBUG(dbgs() << "Roots are different in updated trees\n"

                        << "The entire tree needs to be rebuilt\n");

      // It may be possible to update the tree without recalculating it, but

      // we do not know yet how to do it, and it happens rarely in practice.

      CalculateFromScratch(DT, BUI);

    }

  }

  // Handles insertion to a node already in the dominator tree.

  static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI,

                              const TreeNodePtr From, const TreeNodePtr To) {

    LLVM_DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock())

                      << " -> " << BlockNamePrinter(To->getBlock()) << "\n");

    if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return;

    // DT.findNCD expects both pointers to be valid. When From is a virtual

    // root, then its CFG block pointer is a nullptr, so we have to 'compute'

    // the NCD manually.

    const NodePtr NCDBlock =

        (From->getBlock() && To->getBlock())

            ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock())

            : nullptr;

    assert(NCDBlock || DT.isPostDominator());

    const TreeNodePtr NCD = DT.getNode(NCDBlock);

    assert(NCD);

    LLVM_DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n");

    const unsigned NCDLevel = NCD->getLevel();