[LLVMdev] SCEVCouldNotCompute

[Nick Lewycky]

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
>