diff options
author | Chris Lattner <sabre@nondot.org> | 2007-08-05 00:02:00 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2007-08-05 00:02:00 +0000 |
commit | e93e31198109b03b8c22296a1500839e95d59b5f (patch) | |
tree | 39918f01f62924b019b26ac28e1dcdacbc1c61f5 /lib/VMCore/Dominators.cpp | |
parent | 0a5f83c22cc5d1fe24e57aadde9399fa90eb5c98 (diff) | |
download | external_llvm-e93e31198109b03b8c22296a1500839e95d59b5f.zip external_llvm-e93e31198109b03b8c22296a1500839e95d59b5f.tar.gz external_llvm-e93e31198109b03b8c22296a1500839e95d59b5f.tar.bz2 |
Switch the internal "Info" map from an std::map to a DenseMap. This
speeds up idom by about 45% and postidom by about 33%.
Some extra precautions must be taken not to invalidate densemap iterators.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40827 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/VMCore/Dominators.cpp')
-rw-r--r-- | lib/VMCore/Dominators.cpp | 12 |
1 files changed, 5 insertions, 7 deletions
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 9b36e1d..bb780c5 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -146,12 +146,12 @@ void DominatorTree::splitBlock(BasicBlock *NewBB) { } } -unsigned DominatorTree::DFSPass(BasicBlock *V, InfoRec &VInfo, - unsigned N) { +unsigned DominatorTree::DFSPass(BasicBlock *V, unsigned N) { // This is more understandable as a recursive algorithm, but we can't use the // recursive algorithm due to stack depth issues. Keep it here for // documentation purposes. #if 0 + InfoRec &VInfo = Info[Roots[i]]; VInfo.Semi = ++N; VInfo.Label = V; @@ -164,7 +164,7 @@ unsigned DominatorTree::DFSPass(BasicBlock *V, InfoRec &VInfo, InfoRec &SuccVInfo = Info[*SI]; if (SuccVInfo.Semi == 0) { SuccVInfo.Parent = V; - N = DFSPass(*SI, SuccVInfo, N); + N = DFSPass(*SI, N); } } #else @@ -313,7 +313,7 @@ void DominatorTree::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){ #endif } -void DominatorTree::calculate(Function& F) { +void DominatorTree::calculate(Function &F) { BasicBlock* Root = Roots[0]; // Add a node for the root... @@ -323,9 +323,7 @@ void DominatorTree::calculate(Function& F) { // Step #1: Number blocks in depth-first order and initialize variables used // in later stages of the algorithm. - unsigned N = 0; - for (unsigned i = 0, e = Roots.size(); i != e; ++i) - N = DFSPass(Roots[i], Info[Roots[i]], 0); + unsigned N = DFSPass(Root, 0); for (unsigned i = N; i >= 2; --i) { BasicBlock *W = Vertex[i]; |