[llvm-dev] Generating Big Num addition code which uses ADC (add with carry) instructions

[David Jones via llvm-dev]

This might "just work" on many targets by using the appropriate integral
type.

e.g. on x86_64, something like

%a = add i128 %b, %c

will lower to

add rax,rbx
adc rcx,rdx

Some caveats, based on my experience with LLVM 3.3, so things may have
changed by then:

- Not all targets support operations on integers wider than the "native
width". e.g. on x86_64, trying to multiply i256 x i256 will net you an
assert. I believe i128 x i128 is handled, perhaps by a function call, but
nothing larger.
- At least on x86_64, everything is fully unrolled. So adding i2048 + i2048
will generate an ADD and 31 ADC instructions, with no looping. This makes
sense for "small" multiprecision integers, but can get silly as things get
wider.

In my project, I am using i128 in a few places (add, subtract, shift) to
get efficient code, and relying on my own library functions for anything
wider.


On Mon, Nov 9, 2015 at 11:46 PM, Clinton Mead via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> I'm trying to work out LLVM code which generates something similar to the
> following when adding large multiword numbers stored as separate words:
>
> ADD x1 x1
> ADC x2 y2
> ADC x3 y3
>
> etc, where such a three argument add like ADC on x86 (which includes a
> carry in the addition) is available as a machine op.
>
> The background to this is that I'm trying to implement fast multiword
> addition in Haskell, which can compile via LLVM, so I thought if I knew
> what LLVM code generates the ideal assembly I can work backwards and use
> the appropriate Haskell prim-ops.
>
> Of course one can use GMP, but I'd suspect with two-four word additions
> the loss of inlining opportunities and the cost of the external call would
> be greater than the addition itself. So it would be great to be able to
> work out how to do it in LLVM and then either implement it with current GHC
> or add an extra GHC prim-op which allows GHC to access the appropriate LLVM
> code.
>
> Sorry I don't know much about LLVM besides my brief readings of the docs,
> and I've posted here because I couldn't find an llvm-users list. There's a
> clang-users list, but I didn't think that would be appropriate because GHC
> compiles via LLVM directly, not via clang.
>
> Any help or guidance appreciated.
>
> Clinton
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20151110/54bcc17a/attachment.html>