diff options
author | Chris Lattner <sabre@nondot.org> | 2007-08-04 23:48:07 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2007-08-04 23:48:07 +0000 |
commit | 0a5f83c22cc5d1fe24e57aadde9399fa90eb5c98 (patch) | |
tree | d74b2bec4e988640e62405cf2386b454483b412b | |
parent | f12f8def399c80aa283783ca406434ee2f80b49f (diff) | |
download | external_llvm-0a5f83c22cc5d1fe24e57aadde9399fa90eb5c98.zip external_llvm-0a5f83c22cc5d1fe24e57aadde9399fa90eb5c98.tar.gz external_llvm-0a5f83c22cc5d1fe24e57aadde9399fa90eb5c98.tar.bz2 |
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
-rw-r--r-- | include/llvm/Analysis/Dominators.h | 15 | ||||
-rw-r--r-- | include/llvm/Analysis/PostDominators.h | 2 | ||||
-rw-r--r-- | lib/Analysis/PostDominators.cpp | 13 | ||||
-rw-r--r-- | lib/VMCore/Dominators.cpp | 29 |
4 files changed, 31 insertions, 28 deletions
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index f0b4672..0740f72 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -23,6 +23,7 @@ #include "llvm/Pass.h" #include <set> +#include "llvm/ADT/DenseMap.h" namespace llvm { @@ -103,7 +104,7 @@ class DominatorTreeBase : public DominatorBase { protected: void reset(); - typedef std::map<BasicBlock*, DomTreeNode*> DomTreeNodeMapType; + typedef DenseMap<BasicBlock*, DomTreeNode*> DomTreeNodeMapType; DomTreeNodeMapType DomTreeNodes; DomTreeNode *RootNode; @@ -120,7 +121,7 @@ protected: InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){} }; - std::map<BasicBlock*, BasicBlock*> IDoms; + DenseMap<BasicBlock*, BasicBlock*> IDoms; // Vertex - Map the DFS number to the BasicBlock* std::vector<BasicBlock*> Vertex; @@ -141,8 +142,8 @@ protected: /// block. This is the same as using operator[] on this class. /// inline DomTreeNode *getNode(BasicBlock *BB) const { - DomTreeNodeMapType::const_iterator i = DomTreeNodes.find(BB); - return (i != DomTreeNodes.end()) ? i->second : 0; + DomTreeNodeMapType::const_iterator I = DomTreeNodes.find(BB); + return I != DomTreeNodes.end() ? I->second : 0; } inline DomTreeNode *operator[](BasicBlock *BB) const { @@ -302,9 +303,9 @@ private: BasicBlock *Eval(BasicBlock *v); void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo); inline BasicBlock *getIDom(BasicBlock *BB) const { - std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB); - return I != IDoms.end() ? I->second : 0; - } + DenseMap<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB); + return I != IDoms.end() ? I->second : 0; + } }; //===------------------------------------- diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h index 091925e..5841da3 100644 --- a/include/llvm/Analysis/PostDominators.h +++ b/include/llvm/Analysis/PostDominators.h @@ -45,7 +45,7 @@ private: void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo); inline BasicBlock *getIDom(BasicBlock *BB) const { - std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB); + DenseMap<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB); return I != IDoms.end() ? I->second : 0; } }; 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 @@ static RegisterPass<PostDominatorTree> 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 @@ void PostDominatorTree::calculate(Function &F) { // 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 @@ void DominatorTree::Compress(BasicBlock *VIn) { 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 @@ void DominatorTree::Compress(BasicBlock *VIn) { } 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 @@ void DominatorTree::calculate(Function& F) { // 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); - - // 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); - } + DomTreeNode *BBNode = DomTreeNodes[I]; + if (BBNode) continue; // Haven't calculated this node yet? + + // 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 @@ void DominatorTree::calculate(Function& F) { 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) |