[LLVMdev] 65bit integer math

[David Greene]

On Monday 12 October 2009 22:22, Eli Friedman wrote:

> > Now I understand that llvm can have any length integer, but I consider
> > turning a 64bit mul into multiple 65 bit instructions to be a ‘bad’
> > optimization. This eventually expands to a 128bit multiply call(__multi3)
> > which I have absolutely no interest in supporting. So I’m wondering what
> > optimization might be the culprit here so I can disable it in this
> > situation.
>
> I'm pretty sure this is the fault of one of the loop passes (I forget
> which one off the top of my head).  

It's SCEV.  I have this very bit of code disabled in our tree for exactly the
reasons Micah gives.  Check out BinomialCoefficient is ScalarEvolution.cpp.

Here's the big hack we put in, which is just the code that used to be there
in 2.3:

  // We need at least W + T bits for the multiplication step
  // FIXME: A temporary hack; we round up the bitwidths
  // to the nearest power of 2 to be nice to the code generator.
  unsigned CalculationBits = 1U << Log2_32_Ceil(W + T);

  // Cray: Truncate to 64 bits.  It's what we did with LLVM 2.3 and
  // while it can create miscompilations in some cases if the
  // computation happens to overflow, it's no worse than what we did
  // before.
  if (CalculationBits > 64) {
    //return new SCEVCouldNotCompute();
    CalculationBits = 64;
    DEBUG(DOUT << "*** [dag] SEVERE WARNING: SCEV calculation truncated to 64 
                   bits, check for miscompilation! ***\n");
  }

I have never found a test where this actually causes a problem.  And we have
tens of thousands of tests.

It is very bad form to create wide arithmetic where none was there before.
This is one of the downfalls of SCEV but I consider it to be minor compared
to the benefits.

                                     -Dave