[LLVMdev] SCEVCouldNotCompute

[David Greene]

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