[LLVMdev] 65bit integer math

[Villmow, Micah]

David,
 Thanks for helping me figure out exactly where to put the check. I was
trying to do modifications in other parts of that function and it wasn't
working very well. I've attached a patch that parameterizes this and
allows it to be set from the commandline instead of hardcoding it.

Would it be possible to get this patch pushed into the tree?

Thanks,
Micah

-----Original Message-----
From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu]
On Behalf Of David Greene
Sent: Tuesday, October 13, 2009 8:45 AM
To: llvmdev at cs.uiuc.edu
Subject: Re: [LLVMdev] 65bit integer math

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

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: ScalarEvolution.diff
Type: application/octet-stream
Size: 1112 bytes
Desc: ScalarEvolution.diff
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20091013/767d3e41/attachment.obj>