diff options
author | Wan Xiaofei <xiaofei.wan@intel.com> | 2013-11-12 09:40:41 +0000 |
---|---|---|
committer | Wan Xiaofei <xiaofei.wan@intel.com> | 2013-11-12 09:40:41 +0000 |
commit | 3cda2d38851d73eec38d38a46462aaa65de4ef8e (patch) | |
tree | fd6f7e00831f7cc6f205446a05e776d0aee3d684 /lib/Analysis | |
parent | e26299d76e4b1ef0fa9bfc89d55dd1a28a1220f4 (diff) | |
download | external_llvm-3cda2d38851d73eec38d38a46462aaa65de4ef8e.zip external_llvm-3cda2d38851d73eec38d38a46462aaa65de4ef8e.tar.gz external_llvm-3cda2d38851d73eec38d38a46462aaa65de4ef8e.tar.bz2 |
Change data structure to memorize computed result in ScalarEvolution
Replace std::map with SmallVector to memorize the cached result since SCEV usually belongs to little Loop/BB
Linear scan on SmallVector is faster than std::map.
Code reviewer : Andrew Trick.
Test result : Pass Unit Test & LLVM Test Suite
401.bzip2 0.425721 0.419981 101.37%
403.gcc 24.53855 24.2667 101.12%
429.mcf 0.060847 0.059944 101.51%
433.milc 0.646009 0.636119 101.55%
444.namd 1.383928 1.370614 100.97%
445.gobmk 5.836575 5.800225 100.63%
450.soplex 1.911257 1.895963 100.81%
456.hmmer 1.039565 1.032534 100.68%
458.sjeng 0.897401 0.885567 101.34%
464.h264ref 3.645908 3.577991 101.90%
470.lbm 0.049456 0.048398 102.19%
471.omnetpp 5.638575 5.60435 100.61%
bitmnp01 0.045738 0.045291 100.99%
cjpegv2data 0.304359 0.302833 100.50%
idctrn01 0.046433 0.045763 101.46%
quake2 4.534416 4.4952 100.87%
quake 2.688566 2.659208 101.10%
xcsoar 12.42545 12.30385 100.99%
linpack 0.038739 0.03803 101.86%
matrix01 0.053564 0.0528 101.45%
nbench 0.402867 0.395803 101.78%
tblook01 0.021265 0.021015 101.19%
ttsprk01 0.066384 0.065566 101.25%
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194459 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Analysis')
-rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 64 |
1 files changed, 42 insertions, 22 deletions
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 9467823..37be5db 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -5059,15 +5059,21 @@ const SCEV *ScalarEvolution::ComputeExitCountExhaustively(const Loop *L, /// original value V is returned. const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) { // Check to see if we've folded this expression at this loop before. - std::map<const Loop *, const SCEV *> &Values = ValuesAtScopes[V]; - std::pair<std::map<const Loop *, const SCEV *>::iterator, bool> Pair = - Values.insert(std::make_pair(L, static_cast<const SCEV *>(0))); - if (!Pair.second) - return Pair.first->second ? Pair.first->second : V; - + SmallVector<std::pair<const Loop *, const SCEV *>, 2> &Values = ValuesAtScopes[V]; + for (unsigned u = 0; u < Values.size(); u++) { + if (Values[u].first == L) + return Values[u].second ? Values[u].second : V; + } + Values.push_back(std::make_pair(L, static_cast<const SCEV *>(0))); // Otherwise compute it. const SCEV *C = computeSCEVAtScope(V, L); - ValuesAtScopes[V][L] = C; + SmallVector<std::pair<const Loop *, const SCEV *>, 2> &Values2 = ValuesAtScopes[V]; + for (unsigned u = Values2.size(); u > 0; u--) { + if (Values2[u - 1].first == L) { + Values2[u - 1].second = C; + break; + } + } return C; } @@ -6727,7 +6733,7 @@ ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se) //===----------------------------------------------------------------------===// ScalarEvolution::ScalarEvolution() - : FunctionPass(ID), FirstUnknown(0) { + : FunctionPass(ID), ValuesAtScopes(64), LoopDispositions(64), BlockDispositions(64), FirstUnknown(0) { initializeScalarEvolutionPass(*PassRegistry::getPassRegistry()); } @@ -6865,14 +6871,21 @@ void ScalarEvolution::print(raw_ostream &OS, const Module *) const { ScalarEvolution::LoopDisposition ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) { - std::map<const Loop *, LoopDisposition> &Values = LoopDispositions[S]; - std::pair<std::map<const Loop *, LoopDisposition>::iterator, bool> Pair = - Values.insert(std::make_pair(L, LoopVariant)); - if (!Pair.second) - return Pair.first->second; - + SmallVector<std::pair<const Loop *, LoopDisposition>, 2> &Values = LoopDispositions[S]; + for (unsigned u = 0; u < Values.size(); u++) { + if (Values[u].first == L) + return Values[u].second; + } + Values.push_back(std::make_pair(L, LoopVariant)); LoopDisposition D = computeLoopDisposition(S, L); - return LoopDispositions[S][L] = D; + SmallVector<std::pair<const Loop *, LoopDisposition>, 2> &Values2 = LoopDispositions[S]; + for (unsigned u = Values2.size(); u > 0; u--) { + if (Values2[u - 1].first == L) { + Values2[u - 1].second = D; + break; + } + } + return D; } ScalarEvolution::LoopDisposition @@ -6964,14 +6977,21 @@ bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S, const Loop *L) { ScalarEvolution::BlockDisposition ScalarEvolution::getBlockDisposition(const SCEV *S, const BasicBlock *BB) { - std::map<const BasicBlock *, BlockDisposition> &Values = BlockDispositions[S]; - std::pair<std::map<const BasicBlock *, BlockDisposition>::iterator, bool> - Pair = Values.insert(std::make_pair(BB, DoesNotDominateBlock)); - if (!Pair.second) - return Pair.first->second; - + SmallVector<std::pair<const BasicBlock *, BlockDisposition>, 2> &Values = BlockDispositions[S]; + for (unsigned u = 0; u < Values.size(); u++) { + if (Values[u].first == BB) + return Values[u].second; + } + Values.push_back(std::make_pair(BB, DoesNotDominateBlock)); BlockDisposition D = computeBlockDisposition(S, BB); - return BlockDispositions[S][BB] = D; + SmallVector<std::pair<const BasicBlock *, BlockDisposition>, 2> &Values2 = BlockDispositions[S]; + for (unsigned u = Values2.size(); u > 0; u--) { + if (Values2[u - 1].first == BB) { + Values2[u - 1].second = D; + break; + } + } + return D; } ScalarEvolution::BlockDisposition |