[LLVMdev] Bignum development

[Eli Friedman]

On Fri, Jun 11, 2010 at 3:28 PM, Bill Hart <goodwillhart at googlemail.com> wrote:
> Hi Eli,
>
> On 11 June 2010 22:44, Eli Friedman <eli.friedman at gmail.com> wrote:
>> On Fri, Jun 11, 2010 at 10:37 AM, Bill Hart <goodwillhart at googlemail.com> wrote:
>>> a) What plans are there to support addition, subtraction,
>>> multiplication, division, shifting, logical not and other logic ops
>>> for >= 64/128 bits (machine word size, whatever)? The documentation
>>> mentions integers of millions of bits....
>>
>> Pretty much everything besides muliplication and division should work
>> at any width; the result is generally not especially efficient,
>> though.
>
> OK, I only tried multiplication last night when I first had a decent
> fiddle (been marking exams, so haven't had much time to really get
> dirty hands, sorry).
>
> Of course efficiency is imperative for bignum stuff as it underpins
> absolutely behemoth projects like Sage (http://www.sagemath.org).
> Every cycle counts, so to speak. One cycle per limb difference in
> multiplication makes a nearly 40% difference in absolutely everything
> for literally many thousands of developers!

Right; improvements are definitely welcome here; you might want to
take a look at what we currently generate here, though, to see what
improvements are most necessary.

>>> b) Would it be desirable to add primitives for retrieving both the low
>>> and high half of a multiplication and optimisations to combine where
>>> wide multiplications are available on the chip?
>>
>> This should already work where applicable; for example, the following
>> C code gives an appropriately optimized result on x86-32:
>>
>> int a(int x, int y) { return ((long long)x)*y >> 32; }
>>
>
> Right. I'll take a closer look at that, but I don't think it is what I mean.
>
> I'm specifically talking about x86_64 and returning the high 64 bits
> of a 64x64 bit multiply. I don't think this is done, or done
> efficiently in LLVM currently. Or I might be missing something.

Should work the same as the previous example; try the following on x86-64:
long long a(long long x, long long y) { return ((__int128_t)x)*y >> 64; }

> A basic operation in bignum stuff is addmul_1, i.e. multiply a
> multiple precision integer with a single "limb" (machine word) and add
> the resulting multiple precision result to another bignum. This is not
> best achieved by doing lots of wide multiplies, dealing with carries,
> then adding. On AMD x86_64 we get 2.5 cycles per limb in direct
> assembly for addmul_1 (actually achieving the maximum retirement rate
> for macro ops on AMD), but more like 10 cycles per limb with C. Even
> the assembly version of addmul_1 is not efficient enough for a
> multiplication basecase though, where you essentially need the whole
> basecase multiplication done in assembly!
>
> It is this assembly basecase which I would like to be able to code
> directly in LLVM assembly.

Hmm... might be interesting, but you'll likely get much better
practical results by just

>>> c) I want to ask something about retrieving the carry or borrow from
>>> an addition or subtraction and using it in an ADC or SBB..... not sure
>>> what to ask.....
>>
>> LLVM automatically expands wide addition/subtraction with ADC/SBB.
>> There's no other general way to write something which optimizes to an
>> ADC/SBB, at least at the moment.  What do you want here?
>
> I should take a look at what happens for a multiprecision
> addition/subtraction before I answer that one. I merely assumed that
> this also only worked up to 128 bits on x86_64 as per multiplication.

It should work at any width (although once you get to extremely wide
integers, the number of spills makes the code get messy).

Also, this isn't something we do at the moment, but it's would be
possible to teach the backend to transform code using the i1 output of
llvm.uadd.with.overflow into an ADC, etc.

>>
>>> d) Are you guys at all interested in supporting languages that provide
>>> multiprecision arithmetic? I have a vague notion that I'd like to sign
>>> on to help with that (and may be able to bring some other experienced
>>> devels with me if there was some interest).
>>
>> By that, you mean languages that provide arbitrary-width integers?
>
> Right. E.g. Haskell, python, ECL, many others.
>
>> You can already support that by lowering such operations to calls to a
>> multi-precision library instead of IR operations in your frontend.
>
> Indeed that is what they do.... currently. :-)
>
> I work on the bignum libraries though, not language front ends. So, I
> want to know how to implement a bignum library using LLVM. At the
> moment, I can't get close enough to the machine to do anything
> efficient. These libraries usually have large amounts of assembly, not
> C. But LLVM is so capable, I think we've been doing this wrong all
> along. Instead of writing assembly for each machine, we should be
> using LLVM assembly code and writing part of the bignum library on the
> "other side" of this interface.
>
> If you have time, check out the cminusminus language reference. They
> had a bits1 type for flags, like carry from addition, and a mulhi and
> mullo instruction. Now cminusminus never took off and died an untimely
> death (largely because they wrote it in some bizarre ML in my
> opinion), but from a bignum point of view, they got this one minor
> detail right.

Hmm... LLVM currently uses i1 pretty extensively, and you can express
equivalents of mulhi/mullo as mentioned above.

> There's a few ways this could be done though. I mean, imagine if LLVM
> optimised around bignum calls by say breaking bignum calls up into
> more basic primitives and rearranging and coallescing those, etc. I'm
> not saying it *should* do that. It would be a multi-year effort, and
> probably a large grant application to do it (I'm seriously toying with
> the idea...). But I am interested to know what the existing intentions
> of the LLVM devs are for supporting arbitrary precision stuff, as it
> seemed, at least at first blush, as though something non-trivial may
> have been planned all along.
>
> It interested me greatly when I noticed you had these intn types for
> an arbitrary number of bits, and it almost made me think there was
> some planning had gone into supporting arbitrary precision arithmetic
> as basic instructions in the LLVM. Bizarre, but not stupid, perhaps.

There really isn't any grand plan here; LLVM switched a while back
from named integer types to a generalized integer type as part of a
large type-system rewrite; the types were left unrestricted just
because there wasn't any particular reason to restrict them.  The
support for such types has gradually improved since then.  And most
recently, we've started generating such types in the optimizers to
allow transforming complex structures into SSA form.

There have really only been sporadic queries about practical support
for real multi-precision arithmetic, but we'd welcome any
improvements.

-Eli

> The reason this is not stupid is that parallel architectures,
> especially GPU like ones could well be set up to offer bignum
> capabilities. There it really may make sense to offer them as a low
> level primitive. But if there, then why not elsewhere.
>
> Sorry for the rambling. I just want to convey that I don't have some
> specific set plan in mind. I'm really just interested in understanding
> the original thought that went into these intn types, and why they are
> there. I think that in order to really be of any help to LLVM, I need
> to understand what the original design goals were in this regard.
>
>> It
>> would be an interesting experiment to write a pass which converts IR
>> operations which are too wide to calls to a multi-precision library,
>> though.
>
> Yes, very interesting indeed!!
>
> Bill.