Changes in directory llvm/lib/Analysis:
LoopInfo.cpp updated: 1.74 -> 1.75
---
Log message:
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.
---
Diffs of the changes: (+14 -6)
LoopInfo.cpp | 20 ++++++++++++++------
1 files changed, 14 insertions(+), 6 deletions(-)
Index: llvm/lib/Analysis/LoopInfo.cpp
diff -u llvm/lib/Analysis/LoopInfo.cpp:1.74 llvm/lib/Analysis/LoopInfo.cpp:1.75
--- llvm/lib/Analysis/LoopInfo.cpp:1.74 Tue Jun 13 15:45:22 2006
+++ llvm/lib/Analysis/LoopInfo.cpp Tue Aug 1 19:14:16 2006
@@ -480,10 +480,15 @@
}
/// 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 @@
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;
- }
}
}
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
