We've upgraded to llvm 2.4 and we're hitting an assert in SCEV:
llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h:669: RetVal
llvm::SCEVVisitor<SC,
RetVal>::visitCouldNotCompute(llvm::SCEVCouldNotCompute*) [with SC =
llvm::SCEVExpander, RetVal = llvm::Value*]: Assertion `0 &&
"Invalid use of
SCEVCouldNotCompute!"' failed.
This happens in SCEVExpander::visitAddRecExpr where we drop down
to this code:
// If this is a chain of recurrences, turn it into a closed form, using the
// folders, then expandCodeFor the closed form. This allows the folders to
// simplify the expression without having to build a bunch of special code
// into this folder.
SCEVHandle IH = SE.getUnknown(I); // Get I as a "symbolic" SCEV.
SCEVHandle V = S->evaluateAtIteration(IH, SE);
//cerr << "Evaluated: " << *this << "\n
to: " << *V << "\n";
return expand(V);
SCEVAddRecExpr::evaluateAtIteration trips up because a binomial coefficient
requires 65 bits to calculate. There's a big FIXME there:
// FIXME: Temporary hack to avoid generating integers that are too wide.
// Although, it's not completely clear how to determine how much
// widening is safe; for example, on X86, we can't really widen
// beyond 64 because we need to be able to do multiplication
// that's CalculationBits wide, but on X86-64, we can safely widen up to
// 128 bits.
if (CalculationBits > 64)
return new SCEVCouldNotCompute();
As an experiment I applied revision 62958 which gets rid of the fixme.
Codegen then asserts that it doesn't know how to do i128 arithmetic (on
x86-64). I tried applying revision 57709 to no avail.
I would like to just avoid getting into this FIXME situation altogether.
Given that this particular test works with llvm 2.3, I suspect that SCEV got
a little smarter, just smart enough to get itself into trouble on this test.
Unfortunately, I'm not familiar enough with SCEV and SCEVExpander
specifically
to know how to bypass binomial coefficient expansion. What should happen in
SCEVExpander::visitAddRecExpr to avoid it?
Thanks.
-Dave
David Greene wrote:> We've upgraded to llvm 2.4 and we're hitting an assert in SCEV: > > llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h:669: RetVal > llvm::SCEVVisitor<SC, > RetVal>::visitCouldNotCompute(llvm::SCEVCouldNotCompute*) [with SC = > llvm::SCEVExpander, RetVal = llvm::Value*]: Assertion `0 && "Invalid use of > SCEVCouldNotCompute!"' failed. > > This happens in SCEVExpander::visitAddRecExpr where we drop down > to this code: > > // If this is a chain of recurrences, turn it into a closed form, using the > // folders, then expandCodeFor the closed form. This allows the folders to > // simplify the expression without having to build a bunch of special code > // into this folder. > SCEVHandle IH = SE.getUnknown(I); // Get I as a "symbolic" SCEV. > > SCEVHandle V = S->evaluateAtIteration(IH, SE); > //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; > > return expand(V); > > SCEVAddRecExpr::evaluateAtIteration trips up because a binomial coefficient > requires 65 bits to calculate. There's a big FIXME there: > > // FIXME: Temporary hack to avoid generating integers that are too wide. > // Although, it's not completely clear how to determine how much > // widening is safe; for example, on X86, we can't really widen > // beyond 64 because we need to be able to do multiplication > // that's CalculationBits wide, but on X86-64, we can safely widen up to > // 128 bits. > if (CalculationBits > 64) > return new SCEVCouldNotCompute(); > > As an experiment I applied revision 62958 which gets rid of the fixme. > Codegen then asserts that it doesn't know how to do i128 arithmetic (on > x86-64). I tried applying revision 57709 to no avail. > > I would like to just avoid getting into this FIXME situation altogether. > Given that this particular test works with llvm 2.3, I suspect that SCEV got > a little smarter, just smart enough to get itself into trouble on this test. > > Unfortunately, I'm not familiar enough with SCEV and SCEVExpander specifically > to know how to bypass binomial coefficient expansion. What should happen in > SCEVExpander::visitAddRecExpr to avoid it?Take a look at llvm.org/PR2857. Did the patch there make it into LLVM 2.4 or no? Nick> Thanks. > > -Dave > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
On Friday 27 February 2009 00:50, Nick Lewycky wrote:> David Greene wrote: > > We've upgraded to llvm 2.4 and we're hitting an assert in SCEV: > > > > llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h:669: RetVal > > llvm::SCEVVisitor<SC, > > RetVal>::visitCouldNotCompute(llvm::SCEVCouldNotCompute*) [with SC > > llvm::SCEVExpander, RetVal = llvm::Value*]: Assertion `0 && "Invalid use > > of SCEVCouldNotCompute!"' failed. > > > > This happens in SCEVExpander::visitAddRecExpr where we drop down > > to this code: > > > > // If this is a chain of recurrences, turn it into a closed form, using > > the // folders, then expandCodeFor the closed form. This allows the > > folders to // simplify the expression without having to build a bunch of > > special code // into this folder. > > SCEVHandle IH = SE.getUnknown(I); // Get I as a "symbolic" SCEV. > > > > SCEVHandle V = S->evaluateAtIteration(IH, SE); > > //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; > > > > return expand(V); > > > > SCEVAddRecExpr::evaluateAtIteration trips up because a binomial > > coefficient requires 65 bits to calculate. There's a big FIXME there: > > > > // FIXME: Temporary hack to avoid generating integers that are too > > wide. // Although, it's not completely clear how to determine how much // > > widening is safe; for example, on X86, we can't really widen // beyond 64 > > because we need to be able to do multiplication > > // that's CalculationBits wide, but on X86-64, we can safely widen up > > to // 128 bits. > > if (CalculationBits > 64) > > return new SCEVCouldNotCompute(); > > > > As an experiment I applied revision 62958 which gets rid of the fixme. > > Codegen then asserts that it doesn't know how to do i128 arithmetic (on > > x86-64). I tried applying revision 57709 to no avail. > > > > I would like to just avoid getting into this FIXME situation altogether. > > Given that this particular test works with llvm 2.3, I suspect that SCEV > > got a little smarter, just smart enough to get itself into trouble on > > this test. > > > > Unfortunately, I'm not familiar enough with SCEV and SCEVExpander > > specifically to know how to bypass binomial coefficient expansion. What > > should happen in SCEVExpander::visitAddRecExpr to avoid it? > > Take a look at llvm.org/PR2857. Did the patch there make it into LLVM > 2.4 or no?Yes, I think so. I think what's happening is that our optimizer is giving LLVM something it's never seen before. It turns out I "fixed" the problem by reverting to LLVM 2.3 behavior and truncating the calculations to 64 bits. In some very exotic cases this could cause problems related to overflow but since these are induction variables that should almost never happen. Longer-term, I'm worried about this expansion to i128 arithmetic. There should be no need. It's an induction variable and if it was computable in 64 bits before there should be no need to widen to 128 bits. I don't want to experience any slowdowns. Now that we have our 2.4 merge done I'm going to take my bugpoint-reduced testcase over to 2.5/trunk and see what happens. If it produces 128 bit arithmetic I'll consider it a bug and file a PR with the testcase. Sound reasonable? -Dave