使用LLVM的大数字运算(来自Haskell)

Question

对我之前的问题的回答表明Haskell表示plusWord2#为llvm.uadd.with.overflow.我希望使用进位进行长时间的添加,就像x86 ADC指令的工作方式一样.该指令不仅添加了两个参数,还添加了进位的内容.

然后可以添加如下的长数字:

ADD x1 y1
ADC x2 y2
ADC x3 y3
...

导致每个单词一个指令(忽略所需的任何周围移动等).

我查看了GMP库,以及它在通用C代码中如何进行长时间的添加.这是摘录自mpn/generic/add_n.c

sl = ul + vl;
cy1 = sl < ul;
rl = sl + cy;
cy2 = rl < sl;
cy = cy1 | cy2;

注意,它保存了原始加法和进位位加法的进位.这些操作中只有一个可以携带,因此或者之后的携带就足够了.

显然,GMP具有针对特定平台的特定汇编代码,但我认为通用代码是一个很好的基础,因为它可能被编写为编译成合理的代码.在plusWord2#原始的操作手段,我不需要做无聊的比较,以获得进位,所以我实现了GMP的通用代码就像在Haskell如下:

addWithCarry :: Word# -> Word# -> Word# -> (# Word#, Word# #)
addWithCarry x y c =
  let 
    (# c1, r1 #) = plusWord2# x y
    (# c2, r2 #) = plusWord2# r1 c
  in
    (# or# c1 c2, r2 #)

不幸的是,这导致x86代码将进位位保存到寄存器中,然后在其自身添加进位,并添加两个数字,从而导致每个字三个或四个指令而不是一个.

所以我想知道的是我如何结合llvm.uadd.with.overflow在x86上创建一系列ADC指令来实现多精度算术.如果我得到了产生有效长加法的LLVM代码,我希望我可以将它转换回Haskell原语操作,直接从Haskell代码生成有效的加法.

笔记:

我当然可以使用Haskell的FFI来调用内联汇编或GMP,但是这会停止内联,并且我怀疑与小型(即<= 256位)操作数的内联代码相比相对较慢.

我发现'clang'有__builtin_addc一个三个参数加法的形式,它不仅需要两个数字而且还有一个进位,但是GHC不能通过clang编译,所以我不知道它是如何有用的.

Answer 1

这里正确的做法是确保您的 Haskell 前端使用 Clang 在使用其 __builtin_addc 时形成的相同模式来表示 LLVM IR 中的携带算术。

然而，现在不要指望这能用 LLVM 生成良好的代码。请参阅http://llvm.org/PR20748，其中记录了我们目前在 x86 上为此类琐碎模式生成的绝对可怕的代码。但是一旦修复了该错误，您就应该获得所需的生成代码。