switch the DomTreeNodes and IDoms maps in idom/postidom to a
DenseMap instead of an std::map. This speeds up postdomtree
by about 25% and domtree by about 23%. It also speeds up clients,
for example, domfrontier by 11%, mem2reg by 4% and ADCE by 6%.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40826 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
index 1188cff..e3169a5 100644
--- a/lib/Analysis/PostDominators.cpp
+++ b/lib/Analysis/PostDominators.cpp
@@ -28,7 +28,7 @@
F("postdomtree", "Post-Dominator Tree Construction", true);
unsigned PostDominatorTree::DFSPass(BasicBlock *V, InfoRec &VInfo,
- unsigned N) {
+ unsigned N) {
std::vector<std::pair<BasicBlock *, InfoRec *> > workStack;
std::set<BasicBlock *> visited;
workStack.push_back(std::make_pair(V, &VInfo));
@@ -111,13 +111,18 @@
// Step #0: Scan the function looking for the root nodes of the post-dominance
// relationships. These blocks, which have no successors, end with return and
// unwind instructions.
- for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
- if (succ_begin(I) == succ_end(I)) {
- Instruction *Insn = I->getTerminator();
+ for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
+ TerminatorInst *Insn = I->getTerminator();
+ if (Insn->getNumSuccessors() == 0) {
// Unreachable block is not a root node.
if (!isa<UnreachableInst>(Insn))
Roots.push_back(I);
}
+
+ // Prepopulate maps so that we don't get iterator invalidation issues later.
+ IDoms[I] = 0;
+ DomTreeNodes[I] = 0;
+ }
Vertex.push_back(0);
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index 91b422c..9b36e1d 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -212,8 +212,7 @@
std::vector<BasicBlock *> Work;
std::set<BasicBlock *> Visited;
- InfoRec &VInInfo = Info[VIn];
- BasicBlock *VInAncestor = VInInfo.Ancestor;
+ BasicBlock *VInAncestor = Info[VIn].Ancestor;
InfoRec &VInVAInfo = Info[VInAncestor];
if (VInVAInfo.Ancestor != 0)
@@ -233,7 +232,7 @@
}
Work.pop_back();
- // Update VINfo based on Ancestor info
+ // Update VInfo based on Ancestor info
if (VAInfo.Ancestor == 0)
continue;
BasicBlock *VAncestorLabel = VAInfo.Label;
@@ -366,17 +365,16 @@
// Loop over all of the reachable blocks in the function...
for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
if (BasicBlock *ImmDom = getIDom(I)) { // Reachable block.
- DomTreeNode *&BBNode = DomTreeNodes[I];
- if (!BBNode) { // Haven't calculated this node yet?
- // Get or calculate the node for the immediate dominator
- DomTreeNode *IDomNode = getNodeForBlock(ImmDom);
+ DomTreeNode *BBNode = DomTreeNodes[I];
+ if (BBNode) continue; // Haven't calculated this node yet?
- // Add a new tree node for this BasicBlock, and link it as a child of
- // IDomNode
- DomTreeNode *C = new DomTreeNode(I, IDomNode);
- DomTreeNodes[I] = C;
- BBNode = IDomNode->addChild(C);
- }
+ // Get or calculate the node for the immediate dominator
+ DomTreeNode *IDomNode = getNodeForBlock(ImmDom);
+
+ // Add a new tree node for this BasicBlock, and link it as a child of
+ // IDomNode
+ DomTreeNode *C = new DomTreeNode(I, IDomNode);
+ DomTreeNodes[I] = IDomNode->addChild(C);
}
// Free temporary memory used to construct idom's
@@ -387,8 +385,7 @@
updateDFSNumbers();
}
-void DominatorTreeBase::updateDFSNumbers()
-{
+void DominatorTreeBase::updateDFSNumbers() {
int dfsnum = 0;
// Iterate over all nodes in depth first order.
for (unsigned i = 0, e = Roots.size(); i != e; ++i)