//===- GenericDomTreeConstruction.h - Dominator Calculation ------*- C++ -*-==//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
/// \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:
///
/// 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
///
/// This implements the O(n*log(n)) versions of EVAL and LINK, because it turns
/// out that the theoretically slower O(n*log(n)) implementation is actually
/// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs.
///
/// The file uses the Depth Based Search algorithm to perform incremental
/// updates (insertion and deletions). The implemented algorithm is based on
/// this publication:
///
/// 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 <queue>
#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"
#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;
// 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;
struct BatchUpdateInfo {
SmallVector<UpdateT, 4> Updates;
using NodePtrAndKind = PointerIntPair<NodePtr, 1, UpdateKind>;
// In order to be able to walk a CFG that is out of sync with the CFG
// DominatorTree last knew about, use the list of updates to reconstruct
// previous CFG versions of the current CFG. For each node, we store a set
// of its virtually added/deleted future successors and predecessors.
// Note that these children are from the future relative to what the
// DominatorTree knows about -- using them to gets us some snapshot of the
// CFG from the past (relative to the state of the CFG).
DenseMap<NodePtr, SmallDenseSet<NodePtrAndKind, 4>> FutureSuccessors;
DenseMap<NodePtr, SmallDenseSet<NodePtrAndKind, 4>> FuturePredecessors;
// Remembers if the whole tree was recalculated at some point during the
// current batch update.
bool IsRecalculated = false;
};
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 Inverse>
struct ChildrenGetter {
using ResultTy = SmallVector<NodePtr, 8>;
static ResultTy Get(NodePtr N, std::integral_constant<bool, false>) {
auto RChildren = reverse(children<NodePtr>(N));
return ResultTy(RChildren.begin(), RChildren.end());
}
static ResultTy Get(NodePtr N, std::integral_constant<bool, true>) {
auto IChildren = inverse_children<NodePtr>(N);
return ResultTy(IChildren.begin(), IChildren.end());
}
using Tag = std::integral_constant<bool, Inverse>;
// The function below is the core part of the batch updater. It allows the
// Depth Based Search algorithm to perform incremental updates in lockstep
// with updates to the CFG. We emulated lockstep CFG updates by getting its
// next snapshots by reverse-applying future updates.
static ResultTy Get(NodePtr N, BatchUpdatePtr BUI) {
ResultTy Res = Get(N, Tag());
// If there's no batch update in progress, simply return node's children.
if (!BUI) return Res;
// CFG children are actually its *most current* children, and we have to
// reverse-apply the future updates to get the node's children at the
// point in time the update was performed.
auto &FutureChildren = (Inverse != IsPostDom) ? BUI->FuturePredecessors
: BUI->FutureSuccessors;
auto FCIt = FutureChildren.find(N);
if (FCIt == FutureChildren.end()) return Res;
for (auto ChildAndKind : FCIt->second) {
const NodePtr Child = ChildAndKind.getPointer();
const UpdateKind UK = ChildAndKind.getInt();
// Reverse-apply the future update.
if (UK == UpdateKind::Insert) {
// If there's an insertion in the future, it means that the edge must
// exist in the current CFG, but was not present in it before.
assert(llvm::find(Res, Child) != Res.end()
&& "Expected child not found in the CFG");
Res.erase(std::remove(Res.begin(), Res.end(), Child), Res.end());
DEBUG(dbgs() << "\tHiding edge " << BlockNamePrinter(N) << " -> "
<< BlockNamePrinter(Child) << "\n");
} else {
// If there's an deletion in the future, it means that the edge cannot
// exist in the current CFG, but existed in it before.
assert(llvm::find(Res, Child) == Res.end() &&
"Unexpected child found in the CFG");
DEBUG(dbgs() << "\tShowing virtual edge " << BlockNamePrinter(N)
<< " -> " << BlockNamePrinter(Child) << "\n");
Res.push_back(Child);
}
}
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.DomTreeNodes[BB] = IDomNode->addChild(
llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode)))
.get();
}
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;
}
};
// 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.
template <bool IsReverse = false, typename DescendCondition>
unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,
unsigned AttachToNum) {
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.
for (const NodePtr Succ :
ChildrenGetter<Direction>::Get(BB, BatchUpdates)) {
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;
}
NodePtr eval(NodePtr VIn, unsigned LastLinked) {
auto &VInInfo = NodeToInfo[VIn];
if (VInInfo.DFSNum < LastLinked)
return VIn;
SmallVector<NodePtr, 32> Work;
SmallPtrSet<NodePtr, 32> Visited;
if (VInInfo.Parent >= LastLinked)
Work.push_back(VIn);
while (!Work.empty()) {
NodePtr V = Work.back();
auto &VInfo = NodeToInfo[V];
NodePtr VAncestor = NumToNode[VInfo.Parent];
// Process Ancestor first
if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) {
Work.push_back(VAncestor);
continue;
}
Work.pop_back();
// Update VInfo based on Ancestor info
if (VInfo.Parent < LastLinked)
continue;
auto &VAInfo = NodeToInfo[VAncestor];
NodePtr VAncestorLabel = VAInfo.Label;
NodePtr VLabel = VInfo.Label;
if (NodeToInfo[VAncestorLabel].Semi < NodeToInfo[VLabel].Semi)
VInfo.Label = VAncestorLabel;
VInfo.Parent = VAInfo.Parent;
}
return VInInfo.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.
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)].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 !ChildrenGetter<false>::Get(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;
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);
DEBUG(dbgs() << "Found a new trivial root: " << BlockNamePrinter(N)
<< "\n");
DEBUG(dbgs() << "Last visited node: "
<< BlockNamePrinter(SNCA.NumToNode[Num]) << "\n");
}
}
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;
// 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.
SmallPtrSet<NodePtr, 4> ConnectToExitBlock;
for (const NodePtr I : nodes(DT.Parent)) {
if (SNCA.NodeToInfo.count(I) == 0) {
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.
DEBUG(dbgs() << "\t\t\tRunning forward DFS\n");
const unsigned NewNum = SNCA.runDFS<true>(I, Num, AlwaysDescend, Num);
const NodePtr FurthestAway = SNCA.NumToNode[NewNum];
DEBUG(dbgs() << "\t\t\tFound a new furthest away node "
<< "(non-trivial root): "
<< BlockNamePrinter(FurthestAway) << "\n");
ConnectToExitBlock.insert(FurthestAway);
Roots.push_back(FurthestAway);
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];
DEBUG(dbgs() << "\t\t\t\tRemoving DFS info for "
<< BlockNamePrinter(N) << "\n");
SNCA.NodeToInfo.erase(N);
SNCA.NumToNode.pop_back();
}
const unsigned PrevNum = Num;
DEBUG(dbgs() << "\t\t\tRunning reverse DFS\n");
Num = SNCA.runDFS(FurthestAway, Num, AlwaysDescend, 1);
for (unsigned i = PrevNum + 1; i <= Num; ++i)
DEBUG(dbgs() << "\t\t\t\tfound node "
<< BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
}
}
}
DEBUG(dbgs() << "Total: " << Total << ", Num: " << Num << "\n");
DEBUG(dbgs() << "Discovered CFG nodes:\n");
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);
DEBUG(dbgs() << "Found roots: ");
DEBUG(for (auto *Root : Roots) dbgs() << BlockNamePrinter(Root) << " ");
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");
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;
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::find(Roots, N) != Roots.end()) {
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;
SemiNCAInfo SNCA(nullptr); // Since we are rebuilding the whole tree,
// there's no point doing it incrementally.
// Step #0: Number blocks in depth-first order and initialize variables used
// in later stages of the algorithm.
DT.Roots = FindRoots(DT, nullptr);
SNCA.doFullDFSWalk(DT, AlwaysDescend);
SNCA.runSemiNCA(DT);
if (BUI) {
BUI->IsRecalculated = true;
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.DomTreeNodes[Root] =
llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
.get();
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];
DEBUG(dbgs() << "\tdiscovered a new reachable node "
<< BlockNamePrinter(W) << "\n");
// 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.DomTreeNodes[W] = IDomNode->addChild(
llvm::make_unique<DomTreeNodeBase<NodeT>>(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 {
using BucketElementTy = std::pair<unsigned, TreeNodePtr>;
struct DecreasingLevel {
bool operator()(const BucketElementTy &First,
const BucketElementTy &Second) const {
return First.first > Second.first;
}
};
std::priority_queue<BucketElementTy, SmallVector<BucketElementTy, 8>,
DecreasingLevel>
Bucket; // Queue of tree nodes sorted by level in descending order.
SmallDenseSet<TreeNodePtr, 8> Affected;
SmallDenseSet<TreeNodePtr, 8> Visited;
SmallVector<TreeNodePtr, 8> AffectedQueue;
SmallVector<TreeNodePtr, 8> VisitedNotAffectedQueue;
};
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");
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.DomTreeNodes[From] = VirtualRoot->addChild(
llvm::make_unique<DomTreeNodeBase<NodeT>>(From, VirtualRoot)))
.get();
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;
auto RIt = llvm::find(DT.Roots, To->getBlock());
if (RIt == DT.Roots.end())
return false; // To is not a root, nothing to update.
DEBUG(dbgs() << "\t\tAfter the insertion, " << BlockNamePrinter(To)
<< " is no longer a root\n\t\tRebuilding the tree!!!\n");
CalculateFromScratch(DT, BUI);
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 (std::none_of(DT.Roots.begin(), DT.Roots.end(), [BUI](const NodePtr N) {
return HasForwardSuccessors(N, BUI);
}))
return;
// Recalculate the set of roots.
DT.Roots = FindRoots(DT, BUI);
for (const NodePtr R : DT.Roots) {
const TreeNodePtr TN = DT.getNode(R);
// A CFG node was selected as a tree root, but the corresponding tree node
// is not connected to the virtual root. 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 nodes within an infinite loop
// becomes a root.
if (DT.isVirtualRoot(TN->getIDom())) {
DEBUG(dbgs() << "Root " << BlockNamePrinter(R)
<< " is not virtual root's child\n"
<< "The entire tree needs to be rebuilt\n");
// It should be possible to rotate the subtree instead of recalculating
// the whole tree, but this situation happens extremely rarely in
// practice.
CalculateFromScratch(DT, BUI);
return;
}
}
}
// Handles insertion to a node already in the dominator tree.
static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
const TreeNodePtr From, const TreeNodePtr To) {
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);
DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n");
const TreeNodePtr ToIDom = To->getIDom();
// Nothing affected -- NCA property holds.
// (Based on the lemma 2.5 from the second paper.)
if (NCD == To || NCD == ToIDom) return;
// Identify and collect affected nodes.
InsertionInfo II;
DEBUG(dbgs() << "Marking " << BlockNamePrinter(To) << " as affected\n");
II.Affected.insert(To);
const unsigned ToLevel = To->getLevel();
DEBUG(dbgs() << "Putting " << BlockNamePrinter(To) << " into a Bucket\n");
II.Bucket.push({ToLevel, To});
while (!II.Bucket.empty()) {
const TreeNodePtr CurrentNode = II.Bucket.top().second;
II.Bucket.pop();
DEBUG(dbgs() << "\tAdding to Visited and AffectedQueue: "
<< BlockNamePrinter(CurrentNode) << "\n");
II.Visited.insert(CurrentNode);
II.AffectedQueue.push_back(CurrentNode);
// Discover and collect affected successors of the current node.
VisitInsertion(DT, BUI, CurrentNode, CurrentNode->getLevel(), NCD, II);
}
// Finish by updating immediate dominators and levels.
UpdateInsertion(DT, BUI, NCD, II);
}
// Visits an affected node and collect its affected successors.
static void VisitInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
const TreeNodePtr TN, const unsigned RootLevel,
const TreeNodePtr NCD, InsertionInfo &II) {
const unsigned NCDLevel = NCD->getLevel();
DEBUG(dbgs() << "Visiting " << BlockNamePrinter(TN) << "\n");
SmallVector<TreeNodePtr, 8> Stack = {TN};
assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!");
do {
TreeNodePtr Next = Stack.pop_back_val();
for (const NodePtr Succ :
ChildrenGetter<IsPostDom>::Get(Next->getBlock(), BUI)) {
const TreeNodePtr SuccTN = DT.getNode(Succ);
assert(SuccTN && "Unreachable successor found at reachable insertion");
const unsigned SuccLevel = SuccTN->getLevel();
DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
<< ", level = " << SuccLevel << "\n");
// Succ dominated by subtree From -- not affected.
// (Based on the lemma 2.5 from the second paper.)
if (SuccLevel > RootLevel) {
DEBUG(dbgs() << "\t\tDominated by subtree From\n");
if (II.Visited.count(SuccTN) != 0)
continue;
DEBUG(dbgs() << "\t\tMarking visited not affected "
<< BlockNamePrinter(Succ) << "\n");
II.Visited.insert(SuccTN);
II.VisitedNotAffectedQueue.push_back(SuccTN);
Stack.push_back(SuccTN);
} else if ((SuccLevel > NCDLevel + 1) &&
II.Affected.count(SuccTN) == 0) {
DEBUG(dbgs() << "\t\tMarking affected and adding "
<< BlockNamePrinter(Succ) << " to a Bucket\n");
II.Affected.insert(SuccTN);
II.Bucket.push({SuccLevel, SuccTN});
}
}
} while (!Stack.empty());
}
// Updates immediate dominators and levels after insertion.
static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
const TreeNodePtr NCD, InsertionInfo &II) {
DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n");
for (const TreeNodePtr TN : II.AffectedQueue) {
DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN)
<< ") = " << BlockNamePrinter(NCD) << "\n");
TN->setIDom(NCD);
}
UpdateLevelsAfterInsertion(II);
if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
}
static void UpdateLevelsAfterInsertion(InsertionInfo &II) {
DEBUG(dbgs() << "Updating levels for visited but not affected nodes\n");
for (const TreeNodePtr TN : II.VisitedNotAffectedQueue) {
DEBUG(dbgs() << "\tlevel(" << BlockNamePrinter(TN) << ") = ("
<< BlockNamePrinter(TN->getIDom()) << ") "
<< TN->getIDom()->getLevel() << " + 1\n");
TN->UpdateLevel();
}
}
// Handles insertion to previously unreachable nodes.
static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
const TreeNodePtr From, const NodePtr To) {
DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From)
<< " -> (unreachable) " << BlockNamePrinter(To) << "\n");
// Collect discovered edges to already reachable nodes.
SmallVector<std::pair<NodePtr, TreeNodePtr>, 8> DiscoveredEdgesToReachable;
// Discover and connect nodes that became reachable with the insertion.
ComputeUnreachableDominators(DT, BUI, To, From, DiscoveredEdgesToReachable);
DEBUG(dbgs() << "Inserted " << BlockNamePrinter(From)
<< " -> (prev unreachable) " << BlockNamePrinter(To) << "\n");
// Used the discovered edges and inset discovered connecting (incoming)
// edges.
for (const auto &Edge : DiscoveredEdgesToReachable) {
DEBUG(dbgs() << "\tInserting discovered connecting edge "
<< BlockNamePrinter(Edge.first) << " -> "
<< BlockNamePrinter(Edge.second) << "\n");
InsertReachable(DT, BUI, DT.getNode(Edge.first), Edge.second);
}
}
// Connects nodes that become reachable with an insertion.
static void ComputeUnreachableDominators(
DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root,
const TreeNodePtr Incoming,
SmallVectorImpl<std::pair<NodePtr, TreeNodePtr>>
&DiscoveredConnectingEdges) {
assert(!DT.getNode(Root) && "Root must not be reachable");
// Visit only previously unreachable nodes.
auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From,
NodePtr To) {
const TreeNodePtr ToTN = DT.getNode(To);
if (!ToTN) return true;
DiscoveredConnectingEdges.push_back({From, ToTN});
return false;
};
SemiNCAInfo SNCA(BUI);
SNCA.runDFS(Root, 0, UnreachableDescender, 0);
SNCA.runSemiNCA(DT);
SNCA.attachNewSubtree(DT, Incoming);
DEBUG(dbgs() << "After adding unreachable nodes\n");
}
static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
const NodePtr From, const NodePtr To) {
assert(From && To && "Cannot disconnect nullptrs");
DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> "
<< BlockNamePrinter(To) << "\n");
#ifndef NDEBUG
// Ensure that the edge was in fact deleted from the CFG before informing
// the DomTree about it.
// The check is O(N), so run it only in debug configuration.
auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) {
auto Successors = ChildrenGetter<IsPostDom>::Get(Of, BUI);
return llvm::find(Successors, SuccCandidate) != Successors.end();
};
(void)IsSuccessor;
assert(!IsSuccessor(To, From) && "Deleted edge still exists in the CFG!");
#endif
const TreeNodePtr FromTN = DT.getNode(From);
// Deletion in an unreachable subtree -- nothing to do.
if (!FromTN) return;
const TreeNodePtr ToTN = DT.getNode(To);
if (!ToTN) {
DEBUG(dbgs() << "\tTo (" << BlockNamePrinter(To)
<< ") already unreachable -- there is no edge to delete\n");
return;
}
const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);
const TreeNodePtr NCD = DT.getNode(NCDBlock);
// To dominates From -- nothing to do.
if (ToTN == NCD) return;
DT.DFSInfoValid = false;
const TreeNodePtr ToIDom = ToTN->getIDom();
DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
<< BlockNamePrinter(ToIDom) << "\n");
// To remains reachable after deletion.
// (Based on the caption under Figure 4. from the second paper.)
if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN))
DeleteReachable(DT, BUI, FromTN, ToTN);
else
DeleteUnreachable(DT, BUI, ToTN);
if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
}
// Handles deletions that leave destination nodes reachable.
static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
const TreeNodePtr FromTN,
const TreeNodePtr ToTN) {
DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN) << " -> "
<< BlockNamePrinter(ToTN) << "\n");
DEBUG(dbgs() << "\tRebuilding subtree\n");
// Find the top of the subtree that needs to be rebuilt.
// (Based on the lemma 2.6 from the second paper.)
const NodePtr ToIDom =
DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock());
assert(ToIDom || DT.isPostDominator());
const TreeNodePtr ToIDomTN = DT.getNode(ToIDom);
assert(ToIDomTN);
const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom();
// Top of the subtree to rebuild is the root node. Rebuild the tree from
// scratch.
if (!PrevIDomSubTree) {
DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
CalculateFromScratch(DT, BUI);
return;
}
// Only visit nodes in the subtree starting at To.
const unsigned Level = ToIDomTN->getLevel();
auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {
return DT.getNode(To)->getLevel() > Level;
};
DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN) << "\n");
SemiNCAInfo SNCA(BUI);
SNCA.runDFS(ToIDom, 0, DescendBelow, 0);
DEBUG(dbgs() << "\tRunning Semi-NCA\n");
SNCA.runSemiNCA(DT, Level);
SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
}
// Checks if a node has proper support, as defined on the page 3 and later
// explained on the page 7 of the second paper.
static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI,
const TreeNodePtr TN) {
DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN) << "\n");
for (const NodePtr Pred :
ChildrenGetter<!IsPostDom>::Get(TN->getBlock(), BUI)) {
DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
if (!DT.getNode(Pred)) continue;
const NodePtr Support =
DT.findNearestCommonDominator(TN->getBlock(), Pred);
DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
if (Support != TN->getBlock()) {
DEBUG(dbgs() << "\t" << BlockNamePrinter(TN)
<< " is reachable from support "
<< BlockNamePrinter(Support) << "\n");
return true;
}
}
return false;
}
// Handle deletions that make destination node unreachable.
// (Based on the lemma 2.7 from the second paper.)
static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
const TreeNodePtr ToTN) {
DEBUG(dbgs() << "Deleting unreachable subtree " << BlockNamePrinter(ToTN)
<< "\n");
assert(ToTN);
assert(ToTN->getBlock());
if (IsPostDom) {
// Deletion makes a region reverse-unreachable and creates a new root.
// Simulate that by inserting an edge from the virtual root to ToTN and
// adding it as a new root.
DEBUG(dbgs() << "\tDeletion made a region reverse-unreachable\n");
DEBUG(dbgs() << "\tAdding new root " << BlockNamePrinter(ToTN) << "\n");
DT.Roots.push_back(ToTN->getBlock());
InsertReachable(DT, BUI, DT.getNode(nullptr), ToTN);
return;
}
SmallVector<NodePtr, 16> AffectedQueue;
const unsigned Level = ToTN->getLevel();
// Traverse destination node's descendants with greater level in the tree
// and collect visited nodes.
auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
const TreeNodePtr TN = DT.getNode(To);
assert(TN);
if (TN->getLevel() > Level) return true;
if (llvm::find(AffectedQueue, To) == AffectedQueue.end())
AffectedQueue.push_back(To);
return false;
};
SemiNCAInfo SNCA(BUI);
unsigned LastDFSNum =
SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0);
TreeNodePtr MinNode = ToTN;
// Identify the top of the subtree to rebuild by finding the NCD of all
// the affected nodes.
for (const NodePtr N : AffectedQueue) {
const TreeNodePtr TN = DT.getNode(N);
const NodePtr NCDBlock =
DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock());
assert(NCDBlock || DT.isPostDominator());
const TreeNodePtr NCD = DT.getNode(NCDBlock);
assert(NCD);
DEBUG(dbgs() << "Processing affected node " << BlockNamePrinter(TN)
<< " with NCD = " << BlockNamePrinter(NCD)
<< ", MinNode =" << BlockNamePrinter(MinNode) << "\n");
if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD;
}
// Root reached, rebuild the whole tree from scratch.
if (!MinNode->getIDom()) {
DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
CalculateFromScratch(DT, BUI);
return;
}
// Erase the unreachable subtree in reverse preorder to process all children
// before deleting their parent.
for (unsigned i = LastDFSNum; i > 0; --i) {
const NodePtr N = SNCA.NumToNode[i];
const TreeNodePtr TN = DT.getNode(N);
DEBUG(dbgs() << "Erasing node " << BlockNamePrinter(TN) << "\n");
EraseNode(DT, TN);
}
// The affected subtree start at the To node -- there's no extra work to do.
if (MinNode == ToTN) return;
DEBUG(dbgs() << "DeleteUnreachable: running DFS with MinNode = "
<< BlockNamePrinter(MinNode) << "\n");
const unsigned MinLevel = MinNode->getLevel();
const TreeNodePtr PrevIDom = MinNode->getIDom();
assert(PrevIDom);
SNCA.clear();
// Identify nodes that remain in the affected subtree.
auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) {
const TreeNodePtr ToTN = DT.getNode(To);
return ToTN && ToTN->getLevel() > MinLevel;
};
SNCA.runDFS(MinNode->getBlock(), 0, DescendBelow, 0);
DEBUG(dbgs() << "Previous IDom(MinNode) = " << BlockNamePrinter(PrevIDom)
<< "\nRunning Semi-NCA\n");
// Rebuild the remaining part of affected subtree.
SNCA.runSemiNCA(DT, MinLevel);
SNCA.reattachExistingSubtree(DT, PrevIDom);
}
// Removes leaf tree nodes from the dominator tree.
static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
assert(TN);
assert(TN->getNumChildren() == 0 && "Not a tree leaf");
const TreeNodePtr IDom = TN->getIDom();
assert(IDom);
auto ChIt = llvm::find(IDom->Children, TN);
assert(ChIt != IDom->Children.end());
std::swap(*ChIt, IDom->Children.back());
IDom->Children.pop_back();
DT.DomTreeNodes.erase(TN->getBlock());
}
//~~
//===--------------------- DomTree Batch Updater --------------------------===
//~~
static void ApplyUpdates(DomTreeT &DT, ArrayRef<UpdateT> Updates) {
const size_t NumUpdates = Updates.size();
if (NumUpdates == 0)
return;
// Take the fast path for a single update and avoid running the batch update
// machinery.
if (NumUpdates == 1) {
const auto &Update = Updates.front();
if (Update.getKind() == UpdateKind::Insert)
DT.insertEdge(Update.getFrom(), Update.getTo());
else
DT.deleteEdge(Update.getFrom(), Update.getTo());
return;
}
BatchUpdateInfo BUI;
LegalizeUpdates(Updates, BUI.Updates);
const size_t NumLegalized = BUI.Updates.size();
BUI.FutureSuccessors.reserve(NumLegalized);
BUI.FuturePredecessors.reserve(NumLegalized);
// Use the legalized future updates to initialize future successors and
// predecessors. Note that these sets will only decrease size over time, as
// the next CFG snapshots slowly approach the actual (current) CFG.
for (UpdateT &U : BUI.Updates) {
BUI.FutureSuccessors[U.getFrom()].insert({U.getTo(), U.getKind()});
BUI.FuturePredecessors[U.getTo()].insert({U.getFrom(), U.getKind()});
}
DEBUG(dbgs() << "About to apply " << NumLegalized << " updates\n");
DEBUG(if (NumLegalized < 32) for (const auto &U
: reverse(BUI.Updates)) dbgs()
<< '\t' << U << "\n");
DEBUG(dbgs() << "\n");
// If the DominatorTree was recalculated at some point, stop the batch
// updates. Full recalculations ignore batch updates and look at the actual
// CFG.
for (size_t i = 0; i < NumLegalized && !BUI.IsRecalculated; ++i)
ApplyNextUpdate(DT, BUI);
}
// This function serves double purpose:
// a) It removes redundant updates, which makes it easier to reverse-apply
// them when traversing CFG.
// b) It optimizes away updates that cancel each other out, as the end result
// is the same.
//
// It relies on the property of the incremental updates that says that the
// order of updates doesn't matter. This allows us to reorder them and end up
// with the exact same DomTree every time.
//
// Following the same logic, the function doesn't care about the order of
// input updates, so it's OK to pass it an unordered sequence of updates, that
// doesn't make sense when applied sequentially, eg. performing double
// insertions or deletions and then doing an opposite update.
//
// In the future, it should be possible to schedule updates in way that
// minimizes the amount of work needed done during incremental updates.
static void LegalizeUpdates(ArrayRef<UpdateT> AllUpdates,
SmallVectorImpl<UpdateT> &Result) {
DEBUG(dbgs() << "Legalizing " << AllUpdates.size() << " updates\n");
// Count the total number of inserions of each edge.
// Each insertion adds 1 and deletion subtracts 1. The end number should be
// one of {-1 (deletion), 0 (NOP), +1 (insertion)}. Otherwise, the sequence
// of updates contains multiple updates of the same kind and we assert for
// that case.
SmallDenseMap<std::pair<NodePtr, NodePtr>, int, 4> Operations;
Operations.reserve(AllUpdates.size());
for (const auto &U : AllUpdates) {
NodePtr From = U.getFrom();
NodePtr To = U.getTo();
if (IsPostDom) std::swap(From, To); // Reverse edge for postdominators.
Operations[{From, To}] += (U.getKind() == UpdateKind::Insert ? 1 : -1);
}
Result.clear();
Result.reserve(Operations.size());
for (auto &Op : Operations) {
const int NumInsertions = Op.second;
assert(std::abs(NumInsertions) <= 1 && "Unbalanced operations!");
if (NumInsertions == 0) continue;
const UpdateKind UK =
NumInsertions > 0 ? UpdateKind::Insert : UpdateKind::Delete;
Result.push_back({UK, Op.first.first, Op.first.second});
}
// Make the order consistent by not relying on pointer values within the
// set. Reuse the old Operations map.
// In the future, we should sort by something else to minimize the amount
// of work needed to perform the series of updates.
for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) {
const auto &U = AllUpdates[i];
if (!IsPostDom)
Operations[{U.getFrom(), U.getTo()}] = int(i);
else
Operations[{U.getTo(), U.getFrom()}] = int(i);
}
std::sort(Result.begin(), Result.end(),
[&Operations](const UpdateT &A, const UpdateT &B) {
return Operations[{A.getFrom(), A.getTo()}] >
Operations[{B.getFrom(), B.getTo()}];
});
}
static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) {
assert(!BUI.Updates.empty() && "No updates to apply!");
UpdateT CurrentUpdate = BUI.Updates.pop_back_val();
DEBUG(dbgs() << "Applying update: " << CurrentUpdate << "\n");
// Move to the next snapshot of the CFG by removing the reverse-applied
// current update.
auto &FS = BUI.FutureSuccessors[CurrentUpdate.getFrom()];
FS.erase({CurrentUpdate.getTo(), CurrentUpdate.getKind()});
if (FS.empty()) BUI.FutureSuccessors.erase(CurrentUpdate.getFrom());
auto &FP = BUI.FuturePredecessors[CurrentUpdate.getTo()];
FP.erase({CurrentUpdate.getFrom(), CurrentUpdate.getKind()});
if (FP.empty()) BUI.FuturePredecessors.erase(CurrentUpdate.getTo());
if (CurrentUpdate.getKind() == UpdateKind::Insert)
InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
else
DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
}
//~~
//===--------------- DomTree correctness verification ---------------------===
//~~
// Check if the tree has correct roots. A DominatorTree always has a single
// root which is the function's entry node. A PostDominatorTree can have
// multiple roots - one for each node with no successors and for infinite
// loops.
bool verifyRoots(const DomTreeT &DT) {
if (!DT.Parent && !DT.Roots.empty()) {
errs() << "Tree has no parent but has roots!\n";
errs().flush();
return false;
}
if (!IsPostDom) {
if (DT.Roots.empty()) {
errs() << "Tree doesn't have a root!\n";
errs().flush();
return false;
}
if (DT.getRoot() != GetEntryNode(DT)) {
errs() << "Tree's root is not its parent's entry node!\n";
errs().flush();
return false;
}
}
RootsT ComputedRoots = FindRoots(DT, nullptr);
if (DT.Roots.size() != ComputedRoots.size() ||
!std::is_permutation(DT.Roots.begin(), DT.Roots.end(),
ComputedRoots.begin())) {
errs() << "Tree has different roots than freshly computed ones!\n";
errs() << "\tPDT roots: ";
for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", ";
errs() << "\n\tComputed roots: ";
for (const NodePtr N : ComputedRoots)
errs() << BlockNamePrinter(N) << ", ";
errs() << "\n";
errs().flush();
return false;
}
return true;
}
// Checks if the tree contains all reachable nodes in the input graph.
bool verifyReachability(const DomTreeT &DT) {
clear();
doFullDFSWalk(DT, AlwaysDescend);
for (auto &NodeToTN : DT.DomTreeNodes) {
const TreeNodePtr TN = NodeToTN.second.get();
const NodePtr BB = TN->getBlock();
// Virtual root has a corresponding virtual CFG node.
if (DT.isVirtualRoot(TN)) continue;
if (NodeToInfo.count(BB) == 0) {
errs() << "DomTree node " << BlockNamePrinter(BB)
<< " not found by DFS walk!\n";
errs().flush();
return false;
}
}
for (const NodePtr N : NumToNode) {
if (N && !DT.getNode(N)) {
errs() << "CFG node " << BlockNamePrinter(N)
<< " not found in the DomTree!\n";
errs().flush();
return false;
}
}
return true;
}
// Check if for every parent with a level L in the tree all of its children
// have level L + 1.
static bool VerifyLevels(const DomTreeT &DT) {
for (auto &NodeToTN : DT.DomTreeNodes) {
const TreeNodePtr TN = NodeToTN.second.get();
const NodePtr BB = TN->getBlock();
if (!BB) continue;
const TreeNodePtr IDom = TN->getIDom();
if (!IDom && TN->getLevel() != 0) {
errs() << "Node without an IDom " << BlockNamePrinter(BB)
<< " has a nonzero level " << TN->getLevel() << "!\n";
errs().flush();
return false;
}
if (IDom && TN->getLevel() != IDom->getLevel() + 1) {
errs() << "Node " << BlockNamePrinter(BB) << " has level "
<< TN->getLevel() << " while its IDom "
<< BlockNamePrinter(IDom->getBlock()) << " has level "
<< IDom->getLevel() << "!\n";
errs().flush();
return false;
}
}
return true;
}
// Check if the computed DFS numbers are correct. Note that DFS info may not
// be valid, and when that is the case, we don't verify the numbers.
static bool VerifyDFSNumbers(const DomTreeT &DT) {
if (!DT.DFSInfoValid || !DT.Parent)
return true;
const NodePtr RootBB = IsPostDom ? nullptr : DT.getRoots()[0];
const TreeNodePtr Root = DT.getNode(RootBB);
auto PrintNodeAndDFSNums = [](const TreeNodePtr TN) {
errs() << BlockNamePrinter(TN) << " {" << TN->getDFSNumIn() << ", "
<< TN->getDFSNumOut() << '}';
};
// Verify the root's DFS In number. Although DFS numbering would also work
// if we started from some other value, we assume 0-based numbering.
if (Root->getDFSNumIn() != 0) {
errs() << "DFSIn number for the tree root is not:\n\t";
PrintNodeAndDFSNums(Root);
errs() << '\n';
errs().flush();
return false;
}
// For each tree node verify if children's DFS numbers cover their parent's
// DFS numbers with no gaps.
for (const auto &NodeToTN : DT.DomTreeNodes) {
const TreeNodePtr Node = NodeToTN.second.get();
// Handle tree leaves.
if (Node->getChildren().empty()) {
if (Node->getDFSNumIn() + 1 != Node->getDFSNumOut()) {
errs() << "Tree leaf should have DFSOut = DFSIn + 1:\n\t";
PrintNodeAndDFSNums(Node);
errs() << '\n';
errs().flush();
return false;
}
continue;
}
// Make a copy and sort it such that it is possible to check if there are
// no gaps between DFS numbers of adjacent children.
SmallVector<TreeNodePtr, 8> Children(Node->begin(), Node->end());
std::sort(Children.begin(), Children.end(),
[](const TreeNodePtr Ch1, const TreeNodePtr Ch2) {
return Ch1->getDFSNumIn() < Ch2->getDFSNumIn();
});
auto PrintChildrenError = [Node, &Children, PrintNodeAndDFSNums](
const TreeNodePtr FirstCh, const TreeNodePtr SecondCh) {
assert(FirstCh);
errs() << "Incorrect DFS numbers for:\n\tParent ";
PrintNodeAndDFSNums(Node);
errs() << "\n\tChild ";
PrintNodeAndDFSNums(FirstCh);
if (SecondCh) {
errs() << "\n\tSecond child ";
PrintNodeAndDFSNums(SecondCh);
}
errs() << "\nAll children: ";
for (const TreeNodePtr Ch : Children) {
PrintNodeAndDFSNums(Ch);
errs() << ", ";
}
errs() << '\n';
errs().flush();
};
if (Children.front()->getDFSNumIn() != Node->getDFSNumIn() + 1) {
PrintChildrenError(Children.front(), nullptr);
return false;
}
if (Children.back()->getDFSNumOut() + 1 != Node->getDFSNumOut()) {
PrintChildrenError(Children.back(), nullptr);
return false;
}
for (size_t i = 0, e = Children.size() - 1; i != e; ++i) {
if (Children[i]->getDFSNumOut() + 1 != Children[i + 1]->getDFSNumIn()) {
PrintChildrenError(Children[i], Children[i + 1]);
return false;
}
}
}
return true;
}
// The below routines verify the correctness of the dominator tree relative to
// the CFG it's coming from. A tree is a dominator tree iff it has two
// properties, called the parent property and the sibling property. Tarjan
// and Lengauer prove (but don't explicitly name) the properties as part of
// the proofs in their 1972 paper, but the proofs are mostly part of proving
// things about semidominators and idoms, and some of them are simply asserted
// based on even earlier papers (see, e.g., lemma 2). Some papers refer to
// these properties as "valid" and "co-valid". See, e.g., "Dominators,
// directed bipolar orders, and independent spanning trees" by Loukas
// Georgiadis and Robert E. Tarjan, as well as "Dominator Tree Verification
// and Vertex-Disjoint Paths " by the same authors.
// A very simple and direct explanation of these properties can be found in
// "An Experimental Study of Dynamic Dominators", found at
// https://arxiv.org/abs/1604.02711
// The easiest way to think of the parent property is that it's a requirement
// of being a dominator. Let's just take immediate dominators. For PARENT to
// be an immediate dominator of CHILD, all paths in the CFG must go through
// PARENT before they hit CHILD. This implies that if you were to cut PARENT
// out of the CFG, there should be no paths to CHILD that are reachable. If
// there are, then you now have a path from PARENT to CHILD that goes around
// PARENT and still reaches CHILD, which by definition, means PARENT can't be
// a dominator of CHILD (let alone an immediate one).
// The sibling property is similar. It says that for each pair of sibling
// nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each
// other. If sibling LEFT dominated sibling RIGHT, it means there are no
// paths in the CFG from sibling LEFT to sibling RIGHT that do not go through
// LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of
// RIGHT, not a sibling.
// It is possible to verify the parent and sibling properties in
// linear time, but the algorithms are complex. Instead, we do it in a
// straightforward N^2 and N^3 way below, using direct path reachability.
// Checks if the tree has the parent property: if for all edges from V to W in
// the input graph, such that V is reachable, the parent of W in the tree is
// an ancestor of V in the tree.
//
// This means that if a node gets disconnected from the graph, then all of
// the nodes it dominated previously will now become unreachable.
bool verifyParentProperty(const DomTreeT &DT) {
for (auto &NodeToTN : DT.DomTreeNodes) {
const TreeNodePtr TN = NodeToTN.second.get();
const NodePtr BB = TN->getBlock();
if (!BB || TN->getChildren().empty()) continue;
DEBUG(dbgs() << "Verifying parent property of node "
<< BlockNamePrinter(TN) << "\n");
clear();
doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) {
return From != BB && To != BB;
});
for (TreeNodePtr Child : TN->getChildren())
if (NodeToInfo.count(Child->getBlock()) != 0) {
errs() << "Child " << BlockNamePrinter(Child)
<< " reachable after its parent " << BlockNamePrinter(BB)
<< " is removed!\n";
errs().flush();
return false;
}
}
return true;
}
// Check if the tree has sibling property: if a node V does not dominate a
// node W for all siblings V and W in the tree.
//
// This means that if a node gets disconnected from the graph, then all of its
// siblings will now still be reachable.
bool verifySiblingProperty(const DomTreeT &DT) {
for (auto &NodeToTN : DT.DomTreeNodes) {
const TreeNodePtr TN = NodeToTN.second.get();
const NodePtr BB = TN->getBlock();
if (!BB || TN->getChildren().empty()) continue;
const auto &Siblings = TN->getChildren();
for (const TreeNodePtr N : Siblings) {
clear();
NodePtr BBN = N->getBlock();
doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) {
return From != BBN && To != BBN;
});
for (const TreeNodePtr S : Siblings) {
if (S == N) continue;
if (NodeToInfo.count(S->getBlock()) == 0) {
errs() << "Node " << BlockNamePrinter(S)
<< " not reachable when its sibling " << BlockNamePrinter(N)
<< " is removed!\n";
errs().flush();
return false;
}
}
}
}
return true;
}
};
template <class DomTreeT>
void Calculate(DomTreeT &DT) {
SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, nullptr);
}
template <class DomTreeT>
void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
typename DomTreeT::NodePtr To) {
if (DT.isPostDominator()) std::swap(From, To);
SemiNCAInfo<DomTreeT>::InsertEdge(DT, nullptr, From, To);
}
template <class DomTreeT>
void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
typename DomTreeT::NodePtr To) {
if (DT.isPostDominator()) std::swap(From, To);
SemiNCAInfo<DomTreeT>::DeleteEdge(DT, nullptr, From, To);
}
template <class DomTreeT>
void ApplyUpdates(DomTreeT &DT,
ArrayRef<typename DomTreeT::UpdateType> Updates) {
SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, Updates);
}
template <class DomTreeT>
bool Verify(const DomTreeT &DT) {
SemiNCAInfo<DomTreeT> SNCA(nullptr);
return SNCA.verifyRoots(DT) && SNCA.verifyReachability(DT) &&
SNCA.VerifyLevels(DT) && SNCA.verifyParentProperty(DT) &&
SNCA.verifySiblingProperty(DT) && SNCA.VerifyDFSNumbers(DT);
}
} // namespace DomTreeBuilder
} // namespace llvm
#undef DEBUG_TYPE
#endif