[LLVMdev] Bignum development

[Bill Hart]

On 12 June 2010 00:51, Eli Friedman <eli.friedman at gmail.com> wrote:
> 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.

Roger that.

>
>>>> 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; }

Ah, I looked for this last night for some time. I tried uint128_t,
u_int128_t, uint128, int128, everything you can imagine... except of
course .... that. Should've read the manual.

Damn, it does do this in one mul for unsigned multiplication! I feel
embarrassed now. The stupid thing is I actually know this is what
happens in gcc 4.4.x when you do something like the above in C. I
should've thought of this.

That totally solves my "problem".

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

... using GMP? Right. Good plan. Been there, done that.

Going to work on a project which for the time being is called bsdnt
(virtually vaporware at this stage). Definitely don't want to just
replicate GMP with a BSD license. We're interested in parallel code
and lots of other goodies. Implementing on top of LLVM is (probably)
perfect for this.

>
>>>> 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.

What is i1? Sorry for the really daft question. These short
abbreviations are sometimes hard to look up.....

>
>> 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.

OK. Thanks. That's interesting to know. I'll see if I can now get a
better understanding of the evolution of this.

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

Sure. I'm mainly thinking of LLVM's stated aim of "offering support
for other non-C languages", which is (a paraphrase of) what you have
somewhere, listed in the open projects on the LLVM site. It occurs to
me that bignum support is one thing that many languages require, but
currently have to use GMP for. If your language is BSD licensed
though, that is out of the question, hence some pretty poor bignum
implementations out there (I mean relatively speaking
performance-wise).

There are obviously numerous ways we might use LLVM to aid development
of "bsdnt". I'll keep exploring those options. It sounds like, for the
time being, analysing existing code output and looking for ways to
improve it on certain arches is perhaps one way we may be of
assistance.

By the way, the LLVM website is absolutely spectacular. The attention
to detail is amazing. There were some things that I found oddly
difficult to find, and I am still mystified why I googled for such a
long time for something like LLVM (days of googling, not minutes) and
didn't hit upon it. I wonder if I simply overlooked it because I
thought it was "just" a JIT or virtual machine.

Heh, ever thought of putting lots of terms like, "faster than C",
"high level assembly language", "lower level than C", "modern compiler
back end", "better than gcc's RTL", "similar to RTL", etc. on the
site, to make things more visible to a certain class of google
searches. (Better than gcc, faster than gcc, BSD licensed C compiler,
beats gcc in the programming language shootout - heh, naughty me). :-)

Like the /. article today. Congrats!!

Bill.

>
> -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.
>