Treeadd has a for loop from 0 to 100 that scalar-evolution isn't able to
determine the bounds of. Attached is a patch that handles the unusual
case where the exit branch indirectly leads back to the loop header.
It didn't cause any miscompiles in llvm-test (excl. External) and I did
a count of how many loops it was able to predict before and after this
patch:
Before:
predictable loop count: 4904 (21%)
not predictable: 18359 (79%)
After:
predictable loop count: 4679 (24%)
not predictable: 14877 (76%)
The total varies because the loop optimizations must request the loop
count from scalar evolution. It's not clear to me why -- perhaps the
loops were canonicalized earlier.
Nick
Index: lib/Analysis/ScalarEvolution.cpp
===================================================================
--- lib/Analysis/ScalarEvolution.cpp (revision 40066)
+++ lib/Analysis/ScalarEvolution.cpp (working copy)
@@ -1607,9 +1607,30 @@
// could be done to handle more cases here.
if (ExitBr->getSuccessor(0) != L->getHeader() &&
ExitBr->getSuccessor(1) != L->getHeader() &&
- ExitBr->getParent() != L->getHeader())
- return UnknownValue;
-
+ ExitBr->getParent() != L->getHeader()) {
+
+ // If we can show that there is no inner cycle in the loop then we know
+ // that the execution count must equal the branch count.
+
+ if (!L->getSubLoops().empty() || L->getBlocks().size() >= 64)
+ return UnknownValue;
+
+ SmallVector<BasicBlock *, 64> Queue(1, L->getHeader());
+
+ do {
+ BasicBlock *BB = Queue.back();
+ Queue.pop_back();
+
+ // Blocks in the loop can't have successors outside the loop.
+ for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
+ if (*I == L->getHeader())
+ return UnknownValue;
+ if (*I != ExitBr->getParent())
+ Queue.push_back(*I);
+ }
+ } while (!Queue.empty());
+ }
+
ICmpInst *ExitCond = dyn_cast<ICmpInst>(ExitBr->getCondition());
// If its not an integer comparison then compute it the hard way.
_______________________________________________
llvm-commits mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
