diff options
author | Wan Xiaofei <xiaofei.wan@intel.com> | 2013-10-26 03:08:02 +0000 |
---|---|---|
committer | Wan Xiaofei <xiaofei.wan@intel.com> | 2013-10-26 03:08:02 +0000 |
commit | 887f9c5ec15582aec34aa6c28955d01e4e9961e2 (patch) | |
tree | bd8ce8148a4f3a444b2ea0ffa51579a94fa9bb07 /lib/Transforms/Utils | |
parent | f7ca7c2a09d4fa03d29fbb1fd1358a285b3c6e2e (diff) | |
download | llvm-887f9c5ec15582aec34aa6c28955d01e4e9961e2.tar.gz llvm-887f9c5ec15582aec34aa6c28955d01e4e9961e2.tar.bz2 llvm-887f9c5ec15582aec34aa6c28955d01e4e9961e2.tar.xz |
Quick look-up for block in loop.
This patch implements quick look-up for block in loop by maintaining a hash set for blocks.
It improves the efficiency of loop analysis a lot, the biggest improvement could be 5-6%(458.sjeng).
Below are the compilation time for our benchmark in llc before & after the patch.
Benchmark llc - trunk llc - patched
401.bzip2 0.339081 100.00% 0.329657 102.86%
403.gcc 19.853966 100.00% 19.605466 101.27%
429.mcf 0.049823 100.00% 0.048451 102.83%
433.milc 0.514898 100.00% 0.510217 100.92%
444.namd 1.109328 100.00% 1.103481 100.53%
445.gobmk 4.988028 100.00% 4.929114 101.20%
456.hmmer 0.843871 100.00% 0.825865 102.18%
458.sjeng 0.754238 100.00% 0.714095 105.62%
464.h264ref 2.9668 100.00% 2.90612 102.09%
471.omnetpp 4.556533 100.00% 4.511886 100.99%
bitmnp01 0.038168 100.00% 0.0357 106.91%
idctrn01 0.037745 100.00% 0.037332 101.11%
libquake2 3.78689 100.00% 3.76209 100.66%
libquake_ 2.251525 100.00% 2.234104 100.78%
linpack 0.033159 100.00% 0.032788 101.13%
matrix01 0.045319 100.00% 0.043497 104.19%
nbench 0.333161 100.00% 0.329799 101.02%
tblook01 0.017863 100.00% 0.017666 101.12%
ttsprk01 0.054337 100.00% 0.053057 102.41%
Reviewer : Andrew Trick <atrick@apple.com>, Hal Finkel <hfinkel@anl.gov>
Approver : Andrew Trick <atrick@apple.com>
Test : Pass make check-all & llvm test-suite
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193460 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Transforms/Utils')
-rw-r--r-- | lib/Transforms/Utils/LCSSA.cpp | 15 |
1 files changed, 2 insertions, 13 deletions
diff --git a/lib/Transforms/Utils/LCSSA.cpp b/lib/Transforms/Utils/LCSSA.cpp index 2d1b166c21..f15e8d5927 100644 --- a/lib/Transforms/Utils/LCSSA.cpp +++ b/lib/Transforms/Utils/LCSSA.cpp @@ -55,7 +55,6 @@ namespace { DominatorTree *DT; LoopInfo *LI; ScalarEvolution *SE; - std::vector<BasicBlock*> LoopBlocks; PredIteratorCache PredCache; Loop *L; @@ -82,11 +81,6 @@ namespace { // Check the special guarantees that LCSSA makes. assert(L->isLCSSAForm(*DT) && "LCSSA form not preserved!"); } - - /// inLoop - returns true if the given block is within the current loop - bool inLoop(BasicBlock *B) const { - return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B); - } }; } @@ -129,11 +123,6 @@ bool LCSSA::runOnLoop(Loop *TheLoop, LPPassManager &LPM) { if (ExitBlocks.empty()) return false; - // Speed up queries by creating a sorted vector of blocks. - LoopBlocks.clear(); - LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); - array_pod_sort(LoopBlocks.begin(), LoopBlocks.end()); - // Look at all the instructions in the loop, checking to see if they have uses // outside the loop. If so, rewrite those uses. bool MadeChange = false; @@ -198,7 +187,7 @@ bool LCSSA::ProcessInstruction(Instruction *Inst, if (PHINode *PN = dyn_cast<PHINode>(U)) UserBB = PN->getIncomingBlock(UI); - if (InstBB != UserBB && !inLoop(UserBB)) + if (InstBB != UserBB && !L->contains(UserBB)) UsesToRewrite.push_back(&UI.getUse()); } @@ -244,7 +233,7 @@ bool LCSSA::ProcessInstruction(Instruction *Inst, // If the exit block has a predecessor not within the loop, arrange for // the incoming value use corresponding to that predecessor to be // rewritten in terms of a different LCSSA PHI. - if (!inLoop(*PI)) + if (!L->contains(*PI)) UsesToRewrite.push_back( &PN->getOperandUse( PN->getOperandNumForIncomingValue(PN->getNumIncomingValues()-1))); |