haskell - 使用 LLVM(来自 Haskell)的大数算术

Question

对我之前的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#原始操作意味着我不需要进行愚蠢的比较来获取进位位，因此我在 Haskell 中实现了 GMP 通用代码，如下所示:

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 代码将进位位保存到寄存器中，然后将进位位本身相加，并将两个数字相加，从而导致每个字有 3 或 4 条指令，而不是 1 条。

所以我想知道如何组合 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 上为这样的简单模式生成的绝对可怕的代码。但是一旦修复了该错误，您就应该获得所需的生成代码。