[LLVMdev] Bignum development

Bill Hart goodwillhart at googlemail.com
Fri Jun 11 10:37:18 PDT 2010

Hi all,

After searching for a decent compiler backend for ages (google
sometimes isn't helpful), I recently stumbled upon LLVM. Woot!!

I work on bignum arithmetic (I'm a professional mathematician) and
have recently decided to switch from developing GPL'd bignum code to
BSD licensed code. (See http://www.mpir.org/ which I contributed to
for a while - a fork of GMP).

Please bear with me if these are stupid questions (I am a
mathematician and have only a glancing knowledge of compiler internals
- though not quite zero knowledge).

Looking through the language reference, I see you have an int type
which can be any number of bits. On x86_64, however, I see that mul
only "works" for up to 128 bits. In all cases it appears to return
only the low half of the product.

For addition, I still haven't understood the documentation well enough
to know whether a carry out from an int64 + int64 addition can be
retrieved, e.g. through a trap, and how to do ADC. There are also some
other primitives which might be useful for bignum....

Obviously many non-C languages have optimised bignum capabilities
these days, and you do NOT get good performance by writing such
primitives in C!!

Anyhow, to my questions:

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

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?

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

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

I did see APInt and understand the necessity of such a library for
constant folding etc. but my questions aren't specifically about that
(though perhaps I can help out there too, if anything still remains to
be done....) Specifically I am talking about providing so-called
"native" bignum support, i.e. highly optimised, riding on the bare
metal, type bignum stuff.

Please understand this is just an initial email to enquire about
current status, plans, etc, so I can gauge how my existing expertise
might or might not be of use.

Bill Hart.

P.S: I'm excited about finding LLVM. It is without a doubt one of the
most outstanding Open Source projects I have encountered to date!! But
you already knew that.

More information about the llvm-dev mailing list