summaryrefslogtreecommitdiffstats
path: root/llvm
diff options
context:
space:
mode:
Diffstat (limited to 'llvm')
-rw-r--r--llvm/include/llvm/Support/GenericDomTreeConstruction.h135
1 files changed, 77 insertions, 58 deletions
diff --git a/llvm/include/llvm/Support/GenericDomTreeConstruction.h b/llvm/include/llvm/Support/GenericDomTreeConstruction.h
index a5d6afd0bd8..3aad8664c9a 100644
--- a/llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ b/llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -27,8 +27,11 @@
#include "llvm/ADT/DepthFirstIterator.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 {
@@ -62,11 +65,13 @@ struct SemiNCAInfo {
SmallVector<NodePtr, 2> ReverseChildren;
};
- std::vector<NodePtr> NumToNode;
+ // 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;
void clear() {
- NumToNode.clear();
+ NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
NodeToInfo.clear();
}
@@ -177,44 +182,41 @@ struct SemiNCAInfo {
return VInInfo.Label;
}
- template <typename NodeType>
- void runSemiNCA(DomTreeT &DT, unsigned NumBlocks) {
- // Step #1: Number blocks in depth-first order and initialize variables used
- // in later stages of the algorithm.
- const unsigned N = doFullDFSWalk(DT, AlwaysDescend);
-
- // 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() && N != NumBlocks);
-
+ void runSemiNCA(DomTreeT &DT, const unsigned MinLevel = 0) {
+ const unsigned NextDFSNum(NumToNode.size());
// Initialize IDoms to spanning tree parents.
- for (unsigned i = 1; i <= N; ++i) {
+ for (unsigned i = 1; i < NextDFSNum; ++i) {
const NodePtr V = NumToNode[i];
auto &VInfo = NodeToInfo[V];
VInfo.IDom = NumToNode[VInfo.Parent];
}
- // Step #2: Calculate the semidominators of all vertices.
- for (unsigned i = N; i >= 2; --i) {
+ // 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)) { // Only if this predecessor is reachable!
- unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi;
- if (SemiU < WInfo.Semi)
- WInfo.Semi = SemiU;
- }
+ 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 #3: Explicitly define the immediate dominator of each vertex.
+ // 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 <= N; ++i) {
+ for (unsigned i = 2; i < NextDFSNum; ++i) {
const NodePtr W = NumToNode[i];
auto &WInfo = NodeToInfo[W];
const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;
@@ -224,6 +226,36 @@ struct SemiNCAInfo {
WInfo.IDom = WIDomCandidate;
}
+ }
+
+ template <typename DescendCondition>
+ unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
+ unsigned Num = 0;
+
+ if (DT.Roots.size() > 1) {
+ auto &BBInfo = NodeToInfo[nullptr];
+ BBInfo.DFSNum = BBInfo.Semi = ++Num;
+ BBInfo.Label = nullptr;
+
+ NumToNode.push_back(nullptr); // NumToNode[n] = V;
+ }
+
+ if (DT.isPostDominator()) {
+ for (auto *Root : DT.Roots) Num = runDFS<true>(Root, Num, DC, 1);
+ } else {
+ assert(DT.Roots.size() == 1);
+ Num = runDFS<false>(DT.Roots[0], Num, DC, Num);
+ }
+
+ return Num;
+ }
+
+ void calculateFromScratch(DomTreeT &DT, const unsigned NumBlocks) {
+ // Step #0: Number blocks in depth-first order and initialize variables used
+ // in later stages of the algorithm.
+ const unsigned LastDFSNum = doFullDFSWalk(DT, AlwaysDescend);
+
+ runSemiNCA(DT);
if (DT.Roots.empty()) return;
@@ -231,25 +263,33 @@ struct SemiNCAInfo {
// one exit block, or it may be the virtual exit (denoted by
// (BasicBlock *)0) which postdominates all real exits if there are multiple
// exit blocks, or an infinite loop.
+ // 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] =
- llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
- .get();
+ DT.RootNode = (DT.DomTreeNodes[Root] =
+ llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
+ .get();
+ attachNewSubtree(DT, DT.RootNode);
+ }
- // Loop over all of the reachable blocks in the function...
- for (unsigned i = 2; i <= N; ++i) {
+ 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() << "\tdiscovereed a new reachable node ");
+ DEBUG(PrintBlockOrNullptr(dbgs(), W));
+ DEBUG(dbgs() << "\n");
// Don't replace this with 'count', the insertion side effect is important
- if (DT.DomTreeNodes[W])
- continue; // Haven't calculated this node yet?
+ if (DT.DomTreeNodes[W]) continue; // Haven't calculated this node yet?
NodePtr ImmDom = getIDom(W);
- assert(ImmDom || DT.DomTreeNodes[nullptr]);
-
// Get or calculate the node for the immediate dominator
TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
@@ -260,29 +300,6 @@ struct SemiNCAInfo {
}
}
- template <typename DescendCondition>
- unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
- unsigned Num = 0;
- NumToNode.push_back(nullptr);
-
- if (DT.Roots.size() > 1) {
- auto &BBInfo = NodeToInfo[nullptr];
- BBInfo.DFSNum = BBInfo.Semi = ++Num;
- BBInfo.Label = nullptr;
-
- NumToNode.push_back(nullptr); // NumToNode[n] = V;
- }
-
- if (DT.isPostDominator()) {
- for (auto *Root : DT.Roots) Num = runDFS<true>(Root, Num, DC, 1);
- } else {
- assert(DT.Roots.size() == 1);
- Num = runDFS<false>(DT.Roots[0], Num, DC, Num);
- }
-
- return Num;
- }
-
static void PrintBlockOrNullptr(raw_ostream &O, NodePtr Obj) {
if (!Obj)
O << "nullptr";
@@ -514,7 +531,7 @@ void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT,
static_assert(std::is_pointer<NodePtr>::value,
"NodePtr should be a pointer type");
SemiNCAInfo<typename std::remove_pointer<NodePtr>::type> SNCA;
- SNCA.template runSemiNCA<NodeT>(DT, GraphTraits<FuncT *>::size(&F));
+ SNCA.calculateFromScratch(DT, GraphTraits<FuncT *>::size(&F));
}
template <class NodeT>
@@ -532,4 +549,6 @@ bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT) {
} // namespace DomTreeBuilder
} // namespace llvm
+#undef DEBUG_TYPE
+
#endif
OpenPOWER on IntegriCloud