[LLVMdev] SCEVCouldNotCompute

[Nick Lewycky]

David Greene wrote:
> 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.

Right, LLVM 2.3 miscalculated the induction variable in pathological 
cases. The only time it will ever expand the width of the variable is if 
it can't be computed without doing so. Except in truly *special* 
pathological cases, it will only produce width+1 which codegens to 
width-sized math plus carry bit.

> 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?

Sure, I'll be happy to take a look at it!

Nick

>                                            -Dave
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>