diff options
author | Chris Lattner <sabre@nondot.org> | 2007-03-04 04:06:39 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2007-03-04 04:06:39 +0000 |
commit | b1f5d8bf6f75612ef55aa343951c666e243ec2cd (patch) | |
tree | a1babe0dedca3415e5dfcfe0e8ebaffc5e2f0150 /lib/Analysis/LoopInfo.cpp | |
parent | ab8fea5283de0931e1da5dc91b4df2f734ba0206 (diff) | |
download | external_llvm-b1f5d8bf6f75612ef55aa343951c666e243ec2cd.zip external_llvm-b1f5d8bf6f75612ef55aa343951c666e243ec2cd.tar.gz external_llvm-b1f5d8bf6f75612ef55aa343951c666e243ec2cd.tar.bz2 |
Speed up Loop::isLCSSAForm by using a hash table instead of a sorted vector.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34900 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Analysis/LoopInfo.cpp')
-rw-r--r-- | lib/Analysis/LoopInfo.cpp | 16 |
1 files changed, 7 insertions, 9 deletions
diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp index 27f1750..ab71b88 100644 --- a/lib/Analysis/LoopInfo.cpp +++ b/lib/Analysis/LoopInfo.cpp @@ -22,6 +22,7 @@ #include "llvm/Support/CFG.h" #include "llvm/Support/Streams.h" #include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/SmallPtrSet.h" #include <algorithm> #include <ostream> using namespace llvm; @@ -565,25 +566,22 @@ Value *Loop::getTripCount() const { 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()); + SmallPtrSet<BasicBlock*, 16> LoopBBs(block_begin(), block_end()); - for (unsigned i = 0, e = LoopBBs.size(); i != e; ++i) { - BasicBlock *BB = LoopBBs[i]; + for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) { + BasicBlock *BB = *BI; 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(); - if (PHINode* p = dyn_cast<PHINode>(*UI)) { + if (PHINode *P = dyn_cast<PHINode>(*UI)) { unsigned OperandNo = UI.getOperandNo(); - UserBB = p->getIncomingBlock(OperandNo/2); + UserBB = P->getIncomingBlock(OperandNo/2); } // 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)) + if (UserBB != BB && !LoopBBs.count(UserBB)) return false; } } |