diff options
author | Chris Lattner <sabre@nondot.org> | 2006-08-02 00:14:16 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2006-08-02 00:14:16 +0000 |
commit | 880ddb018a4bdcff00d35f28988d9eddb557b8e6 (patch) | |
tree | 19bf505b84218913aa06bad8e3521ab5515da736 /lib/Analysis/LoopInfo.cpp | |
parent | d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfe (diff) | |
download | external_llvm-880ddb018a4bdcff00d35f28988d9eddb557b8e6.zip external_llvm-880ddb018a4bdcff00d35f28988d9eddb557b8e6.tar.gz external_llvm-880ddb018a4bdcff00d35f28988d9eddb557b8e6.tar.bz2 |
Speed up Loop::isLCSSAForm by using a binary search and single-entry cache.
This reduces LCSSA pass time from 1.5s to 0.96s when run on eon in release+asserts mode.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29464 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Analysis/LoopInfo.cpp')
-rw-r--r-- | lib/Analysis/LoopInfo.cpp | 20 |
1 files changed, 14 insertions, 6 deletions
diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp index 49162a6..0ea5133 100644 --- a/lib/Analysis/LoopInfo.cpp +++ b/lib/Analysis/LoopInfo.cpp @@ -480,10 +480,15 @@ Value *Loop::getTripCount() const { } /// isLCSSAForm - Return true if the Loop is in LCSSA form -bool Loop::isLCSSAForm() const { - for (Loop::block_iterator BB = block_begin(), E = block_end(); - BB != E; ++BB) { - for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I) +bool Loop::isLCSSAForm() const { + // Sort the blocks vector so that we can use binary search to do quick + // lookups. + std::vector<BasicBlock*> LoopBBs(block_begin(), block_end()); + std::sort(LoopBBs.begin(), LoopBBs.end()); + + for (unsigned i = 0, e = LoopBBs.size(); i != e; ++i) { + BasicBlock *BB = LoopBBs[i]; + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI) { BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); @@ -492,9 +497,12 @@ bool Loop::isLCSSAForm() const { UserBB = p->getIncomingBlock(OperandNo/2); } - if (!contains(UserBB)) { + // Check the current block, as a fast-path. Most values are used in the + // same block they are defined in. + if (UserBB != BB && + // Otherwise, binary search LoopBBs for this block. + !std::binary_search(LoopBBs.begin(), LoopBBs.end(), UserBB)) return false; - } } } |