[LLVMdev] 65bit integer math

[Dan Gohman]

On Oct 12, 2009, at 9:42 PM, Jeffrey Yasskin wrote:

> On Mon, Oct 12, 2009 at 8:22 PM, Eli Friedman  
> <eli.friedman at gmail.com> wrote:
>> On Mon, Oct 12, 2009 at 6:15 PM, Villmow, Micah <Micah.Villmow at amd.com 
>> > wrote:
>>> I have a test case(attached as fc_long.ll) that when run through the
>>> optimizer produces 65bit integer math(fc_long-opt.ll).
>>>
>>>
>>>
>>> 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 worth noting that the
>> optimizer manages to eliminate the loop; computing the exit value of
>> one of the loop variables uses the wide multiply.
>
> It's -indvars. I ran mem2reg, instcombine, and simplifycfg on your
> input and got the attached file. I thought I could add "nuw nsw" to
> the arithmetic inside the loop to say that i65 is unnecessary, but
> that doesn't cause indvars to leave the arithmetic at i64. Is that a
> bug in indvars, or in SCEV, or is this just a natural limitation of
> SCEV?

LLVM's ScalarEvolution's handling of non-linear recurrences has much  
room
for improvement. The problem Micah describes sounds like the one
in lib/Analysis/README.txt.

Dan