Page MenuHomePhabricator
Differential D35597 Diff 108329 llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h

Changeset View

Standalone View

View Options

llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h

Show First 20 Lines • Show All 125 Lines • ▼ Show 20 Lines friend raw_ostream &operator<<(raw_ostream &O, const BlockNamePrinter &BP) {
return O; return O;
} }
}; };
// Custom DFS implementation which can skip nodes based on a provided // Custom DFS implementation which can skip nodes based on a provided
// predicate. It also collects ReverseChildren so that we don't have to spend // predicate. It also collects ReverseChildren so that we don't have to spend
// time getting predecessors in SemiNCA. // time getting predecessors in SemiNCA.
template <bool Inverse, typename DescendCondition> template <typename DescendCondition>
unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition, unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,
unsigned AttachToNum) { unsigned AttachToNum) {
assert(V); assert(V);
SmallVector<NodePtr, 64> WorkList = {V}; SmallVector<NodePtr, 64> WorkList = {V};
if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum; if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum;
while (!WorkList.empty()) { while (!WorkList.empty()) {
const NodePtr BB = WorkList.pop_back_val(); const NodePtr BB = WorkList.pop_back_val();
auto &BBInfo = NodeToInfo[BB]; auto &BBInfo = NodeToInfo[BB];
// Visited nodes always have positive DFS numbers. // Visited nodes always have positive DFS numbers.
if (BBInfo.DFSNum != 0) continue; if (BBInfo.DFSNum != 0) continue;
BBInfo.DFSNum = BBInfo.Semi = ++LastNum; BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
BBInfo.Label = BB; BBInfo.Label = BB;
NumToNode.push_back(BB); NumToNode.push_back(BB);
for (const NodePtr Succ : ChildrenGetter<NodePtr, Inverse>::Get(BB)) { for (const NodePtr Succ : ChildrenGetter<NodePtr, IsPostDom>::Get(BB)) {
const auto SIT = NodeToInfo.find(Succ); const auto SIT = NodeToInfo.find(Succ);
// Don't visit nodes more than once but remember to collect // Don't visit nodes more than once but remember to collect
// RerverseChildren. // RerverseChildren.
if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) { if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
if (Succ != BB) SIT->second.ReverseChildren.push_back(BB); if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
continue; continue;
} }
▲ Show 20 Lines • Show All 95 Lines • ▼ Show 20 Lines for (unsigned i = 2; i < NextDFSNum; ++i) {
WInfo.IDom = WIDomCandidate; WInfo.IDom = WIDomCandidate;
} }
} }
template <typename DescendCondition> template <typename DescendCondition>
unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) { unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
unsigned Num = 0; unsigned Num = 0;
if (DT.Roots.size() > 1) { // If the DT is a PostDomTree, always add a virtual root.
if (IsPostDom) {
auto &BBInfo = NodeToInfo[nullptr]; auto &BBInfo = NodeToInfo[nullptr];
BBInfo.DFSNum = BBInfo.Semi = ++Num; BBInfo.DFSNum = BBInfo.Semi = ++Num;
BBInfo.Label = nullptr; BBInfo.Label = nullptr;
NumToNode.push_back(nullptr); // NumToNode[n] = V; NumToNode.push_back(nullptr); // NumToNode[n] = V;
} }
if (DT.isPostDominator()) { const unsigned InitialNum = Num;
for (auto *Root : DT.Roots) Num = runDFS<true>(Root, Num, DC, 1); for (auto *Root : DT.Roots) Num = runDFS(Root, Num, DC, InitialNum);
} else {
assert(DT.Roots.size() == 1);
Num = runDFS<false>(DT.Roots[0], Num, DC, Num);
}
return Num; return Num;
} }
void calculateFromScratch(DomTreeT &DT, const unsigned NumBlocks) { static void FindAndAddRoots(DomTreeT &DT) {
assert(DT.Parent && "Parent pointer is not set");
using TraitsTy = GraphTraits<typename DomTreeT::ParentPtr>;
if (!IsPostDom) {
// Dominators have a single root that is the function's entry.
NodeT *entry = TraitsTy::getEntryNode(DT.Parent);
DT.addRoot(entry);
} else {
// Initialize the roots list for PostDominators.
for (auto *Node : nodes(DT.Parent))
if (TraitsTy::child_begin(Node) == TraitsTy::child_end(Node))
DT.addRoot(Node);
}
}
void calculateFromScratch(DomTreeT &DT) {
// Step #0: Number blocks in depth-first order and initialize variables used // Step #0: Number blocks in depth-first order and initialize variables used
// in later stages of the algorithm. // in later stages of the algorithm.
const unsigned LastDFSNum = doFullDFSWalk(DT, AlwaysDescend); FindAndAddRoots(DT);
doFullDFSWalk(DT, AlwaysDescend);
runSemiNCA(DT); runSemiNCA(DT);
if (DT.Roots.empty()) return; if (DT.Roots.empty()) return;
// Add a node for the root. This node might be the actual root, if there is // Add a node for the root. If the tree is a PostDominatorTree it will be
// one exit block, or it may be the virtual exit (denoted by // the virtual exit (denoted by (BasicBlock *) nullptr) which postdominates
// (BasicBlock *)0) which postdominates all real exits if there are multiple // all real exits (including multiple exit blocks, infinite loops).
// exit blocks, or an infinite loop. NodePtr Root = IsPostDom ? nullptr : DT.Roots[0];
// It might be that some blocks did not get a DFS number (e.g., blocks of
// infinite loops). In these cases an artificial exit node is required.
const bool MultipleRoots = DT.Roots.size() > 1 || (DT.isPostDominator() &&
LastDFSNum != NumBlocks);
NodePtr Root = !MultipleRoots ? DT.Roots[0] : nullptr;
DT.RootNode = (DT.DomTreeNodes[Root] = DT.RootNode = (DT.DomTreeNodes[Root] =
llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr)) llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
.get(); .get();
attachNewSubtree(DT, DT.RootNode); attachNewSubtree(DT, DT.RootNode);
} }
void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) { void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {
▲ Show 20 Lines • Show All 211 Lines • ▼ Show 20 Lines auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From,
const TreeNodePtr ToTN = DT.getNode(To); const TreeNodePtr ToTN = DT.getNode(To);
if (!ToTN) return true; if (!ToTN) return true;
DiscoveredConnectingEdges.push_back({From, ToTN}); DiscoveredConnectingEdges.push_back({From, ToTN});
return false; return false;
}; };
SemiNCAInfo SNCA; SemiNCAInfo SNCA;
SNCA.runDFS<IsPostDom>(Root, 0, UnreachableDescender, 0); SNCA.runDFS(Root, 0, UnreachableDescender, 0);
SNCA.runSemiNCA(DT); SNCA.runSemiNCA(DT);
SNCA.attachNewSubtree(DT, Incoming); SNCA.attachNewSubtree(DT, Incoming);
DEBUG(dbgs() << "After adding unreachable nodes\n"); DEBUG(dbgs() << "After adding unreachable nodes\n");
DEBUG(DT.print(dbgs())); DEBUG(DT.print(dbgs()));
} }
// Checks if the tree contains all reachable nodes in the input graph. // Checks if the tree contains all reachable nodes in the input graph.
▲ Show 20 Lines • Show All 98 Lines • ▼ Show 20 Lines static void DeleteReachable(DomTreeT &DT, const TreeNodePtr FromTN,
const unsigned Level = ToIDomTN->getLevel(); const unsigned Level = ToIDomTN->getLevel();
auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) { auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {
return DT.getNode(To)->getLevel() > Level; return DT.getNode(To)->getLevel() > Level;
}; };
DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN) << "\n"); DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN) << "\n");
SemiNCAInfo SNCA; SemiNCAInfo SNCA;
SNCA.runDFS<IsPostDom>(ToIDom, 0, DescendBelow, 0); SNCA.runDFS(ToIDom, 0, DescendBelow, 0);
DEBUG(dbgs() << "\tRunning Semi-NCA\n"); DEBUG(dbgs() << "\tRunning Semi-NCA\n");
SNCA.runSemiNCA(DT, Level); SNCA.runSemiNCA(DT, Level);
SNCA.reattachExistingSubtree(DT, PrevIDomSubTree); SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
} }
// Checks if a node has proper support, as defined on the page 3 and later // Checks if a node has proper support, as defined on the page 3 and later
// explained on the page 7 of the second paper. // explained on the page 7 of the second paper.
static bool HasProperSupport(DomTreeT &DT, const TreeNodePtr TN) { static bool HasProperSupport(DomTreeT &DT, const TreeNodePtr TN) {
Show All 37 Lines auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
if (llvm::find(AffectedQueue, To) == AffectedQueue.end()) if (llvm::find(AffectedQueue, To) == AffectedQueue.end())
AffectedQueue.push_back(To); AffectedQueue.push_back(To);
return false; return false;
}; };
SemiNCAInfo SNCA; SemiNCAInfo SNCA;
unsigned LastDFSNum = unsigned LastDFSNum =
SNCA.runDFS<IsPostDom>(ToTN->getBlock(), 0, DescendAndCollect, 0); SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0);
TreeNodePtr MinNode = ToTN; TreeNodePtr MinNode = ToTN;
// Identify the top of the subtree to rebuilt by finding the NCD of all // Identify the top of the subtree to rebuilt by finding the NCD of all
// the affected nodes. // the affected nodes.
for (const NodePtr N : AffectedQueue) { for (const NodePtr N : AffectedQueue) {
const TreeNodePtr TN = DT.getNode(N); const TreeNodePtr TN = DT.getNode(N);
const NodePtr NCDBlock = const NodePtr NCDBlock =
Show All 35 Lines static void DeleteUnreachable(DomTreeT &DT, const TreeNodePtr ToTN) {
assert(PrevIDom); assert(PrevIDom);
SNCA.clear(); SNCA.clear();
// Identify nodes that remain in the affected subtree. // Identify nodes that remain in the affected subtree.
auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) { auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) {
const TreeNodePtr ToTN = DT.getNode(To); const TreeNodePtr ToTN = DT.getNode(To);
return ToTN && ToTN->getLevel() > MinLevel; return ToTN && ToTN->getLevel() > MinLevel;
}; };
SNCA.runDFS<IsPostDom>(MinNode->getBlock(), 0, DescendBelow, 0); SNCA.runDFS(MinNode->getBlock(), 0, DescendBelow, 0);
DEBUG(dbgs() << "Previous IDom(MinNode) = " << BlockNamePrinter(PrevIDom) DEBUG(dbgs() << "Previous IDom(MinNode) = " << BlockNamePrinter(PrevIDom)
<< "\nRunning Semi-NCA\n"); << "\nRunning Semi-NCA\n");
// Rebuild the remaining part of affected subtree. // Rebuild the remaining part of affected subtree.
SNCA.runSemiNCA(DT, MinLevel); SNCA.runSemiNCA(DT, MinLevel);
SNCA.reattachExistingSubtree(DT, PrevIDom); SNCA.reattachExistingSubtree(DT, PrevIDom);
} }
▲ Show 20 Lines • Show All 184 Lines • ▼ Show 20 Lines for (auto &NodeToTN : DT.DomTreeNodes) {
} }
} }
} }
return true; return true;
} }
}; };
template <class DomTreeT>
template <class DomTreeT, class FuncT> void Calculate(DomTreeT &DT) {
void Calculate(DomTreeT &DT, FuncT &F) {
SemiNCAInfo<DomTreeT> SNCA; SemiNCAInfo<DomTreeT> SNCA;
SNCA.calculateFromScratch(DT, GraphTraits<FuncT *>::size(&F)); SNCA.calculateFromScratch(DT);
} }
template <class DomTreeT> template <class DomTreeT>
void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
typename DomTreeT::NodePtr To) { typename DomTreeT::NodePtr To) {
if (DT.isPostDominator()) std::swap(From, To); if (DT.isPostDominator()) std::swap(From, To);
SemiNCAInfo<DomTreeT>::InsertEdge(DT, From, To); SemiNCAInfo<DomTreeT>::InsertEdge(DT, From, To);
} }
Show All 22 Lines