Dan Gohman wrote:
>>>Would it be too intrusive to ask ScalarEvolution to use a
>>>PostDominanceFrontier for this?
>>
>>No, that's what I implemented at first. Unfortunately, it doesn't cover
>>all the possible cases (specifically, it broke 2007-01-06-TripCount.ll).
>>
>>In 2007-01-06-TripCount.ll there's two "loops" sharing one loop header.
>>The first runs from header -> exit -> A -> header and the other is
>>header -> B -> A -> header. I was testing exit postdom header, which it
>>does, but that didn't catch this case where the transform is still
>>unsafe.
>>
>>If you think I merely had my test wrong, please let me know what you
>>think it ought to be and I'll implement it and see.
>
> I do think you merely had the wrong test. The post-dominance frontiers
> are needed here.
>
> Running -analyze -postdomfrontier on 2007-01-06-TripCount.ll gives this:
>
> Printing analysis 'Post-Dominance Frontier Construction' for function 'test':
> DomFrontier for BB %bb is: %bb2 %cond_next
> DomFrontier for BB %bb2 is: %bb2 %cond_next
> DomFrontier for BB %cond_true is: %bb2
> DomFrontier for BB %cond_next is: %cond_next
> DomFrontier for BB %bb6 is:
> DomFrontier for BB %return is:
> DomFrontier for BB %entry is:
>
> It looks like %bb2 is the loop header, and %cond_next is the block that
> contains the exit branch. The frontier sets for these two blocks are
> different, so they're not control-equivalent, and that disqualifies the
> loop for what ScalarEvolution is doing here.
Cool! I've implemented that (patch attached) and it works for both
treeadd and TripCount.
Here's the numbers:
Original:
predicted: 4874 (21%)
not predicted: 18361 (79%)
PDF test only:
predicted: 4865 (21%)
not predicted: 18372 (79%)
There was one other consequence of that change. PDF entries only exist
for nodes that postdominate the exit. One could have a countable loop
that preceeds an infinite loop, and it would no longer be analyzed.
I was going to just have it refuse to analyze that case, but it occured
to me that event loops and such work this way, and it could cause a real
problem for real code. So I thought I'd try keeping it.
Both tests:
predicted: 4881 (21%)
not predicted: 18354 (79%)
I'm not sure why, but it doesn't seem as promising as the previous test
I had. Could it be that when comparing the PDF I should ignore blocks
that are not part of the loop?
Nick
Index: lib/Analysis/ScalarEvolution.cpp
===================================================================
--- lib/Analysis/ScalarEvolution.cpp (revision 40483)
+++ lib/Analysis/ScalarEvolution.cpp (working copy)
@@ -60,6 +60,7 @@
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "scalar-evolution"
+#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
@@ -1111,6 +1112,9 @@
///
LoopInfo &LI;
+ /// PDF - The PostDominanceFrontier for the function are currently analyzing.
+ PostDominanceFrontier &PDF;
+
/// UnknownValue - This SCEV is used to represent unknown trip counts and
/// things.
SCEVHandle UnknownValue;
@@ -1131,8 +1135,8 @@
std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue;
public:
- ScalarEvolutionsImpl(Function &f, LoopInfo &li)
- : F(f), LI(li), UnknownValue(new SCEVCouldNotCompute()) {}
+ ScalarEvolutionsImpl(Function &f, LoopInfo &li, PostDominanceFrontier &pdf)
+ : F(f), LI(li), PDF(pdf), UnknownValue(new SCEVCouldNotCompute()) {}
/// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
/// expression and create a new one.
@@ -1600,15 +1604,30 @@
// time through the loop. If not, then the execution count of the branch will
// not be equal to the trip count of the loop.
//
- // Currently we check for this by checking to see if the Exit branch goes to
- // the loop header. If so, we know it will always execute the same number of
- // times as the loop. We also handle the case where the exit block *is* the
- // loop header. This is common for un-rotated loops. More extensive analysis
- // 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;
+ // If the entries in the PostDominanceFrontier are equivalent, then the blocks
+ // have the equivalent control flow.
+
+ PostDominanceFrontier::iterator HeaderPDF = PDF.find(L->getHeader());
+ PostDominanceFrontier::iterator ExitBrPDF = PDF.find(ExitBr->getParent());
+
+ if (HeaderPDF == PDF.end() || ExitBrPDF == PDF.end()) {
+
+ // If the loop is followed by an infinite loop, the PDF won't have an entry
+ // for these blocks. We handle this by testing if the Exit branch goes to
+ // the loop header. If so, we know it will always execute the same number
+ // of times as the loop. We also handle the case where the exit block *is*
+ // the loop header. This is common for un-rotated loops. More extensive
+ // analysis 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;
+
+ } else {
+ if (HeaderPDF->second != ExitBrPDF->second)
+ return UnknownValue;
+ }
ICmpInst *ExitCond = dyn_cast<ICmpInst>(ExitBr->getCondition());
@@ -2546,7 +2565,8 @@
//===----------------------------------------------------------------------===//
bool ScalarEvolution::runOnFunction(Function &F) {
- Impl = new ScalarEvolutionsImpl(F, getAnalysis<LoopInfo>());
+ Impl = new ScalarEvolutionsImpl(F, getAnalysis<LoopInfo>(),
+ getAnalysis<PostDominanceFrontier>());
return false;
}
@@ -2558,6 +2578,7 @@
void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequiredTransitive<LoopInfo>();
+ AU.addRequired<PostDominanceFrontier>();
}
SCEVHandle ScalarEvolution::getSCEV(Value *V) const {
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
