SCEVCouldNotCompute

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,

::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, >::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

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

David Greene 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,
>::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