让GHC生成"Add With Carry(ADC)"指令

Question

这是一个代码,它将两个三联的未装箱的单词添加到一个新的三个未装箱的单词中,并且还返回任何溢出:

{-# LANGUAGE MagicHash #-}
{-# LANGUAGE UnboxedTuples #-}

import GHC.Prim(plusWord2#, Word#, or#)

longAdd :: 
  (# Word#, Word#, Word# #) -> 
  (# Word#, Word#, Word# #) -> 
  (# Word#, (# Word#, Word#, Word# #) #)

longAdd (# xl, xm, xh #) (# yl, ym, yh #) =     
  let
    plusWord3 x y c = 
      let 
        (# c1, r1 #) = plusWord2# x y
        (# c2, r2 #) = plusWord2# r1 c
      in
        (# plusWord# c1 c2, r2 #)
    (# cl, rl #) = plusWord2# xl yl
    (# cm, rm #) = plusWord3 xm ym cl
    (# ch, rh #) = plusWord3 xh yh cm     
  in
    (# ch, (# rl, rm, rh #) #)

问题是"plusWord3"的定义.理想情况下,这就像一个"adc"函数,它接受两个字和进位,并返回结果和一个新进位,因此生成的程序集如下所示:

add x1 y1
adc x2 y2
adc x3 y3

不幸的是GHC,无论是原生的还是通过LLVM,都会产生丑陋的汇编代码,包括将进位位保存到寄存器,然后通过单独的额外添加来读取它,而不仅仅是使用adc.我不想调用外部C函数来实现这一点,因为一旦你添加了调用开销,它可能不值得,我想留在Haskell中,所以代码可以在可能的情况下内联.但我也希望能够让编译器adc适当地生成指令.无论如何我能做到吗？

Answer 1

最可行和最有效的方法是直接在程序中调用primop.

使用FFI调用是最简单的方法,但正如您所指出的那样,由于FFI开销,它不是最有效的方式.

即使编译器支持你想要的指令并在某些程序中使用它,它也会很脆弱.程序中一些看似无辜的变化可能最终会产生不同的生成程序集,而这些程序集不会使用您想要的指令.

所以我的提议是:

1. 将所需的指令添加到X86代码生成器后端,如果它还没有.
2. 添加一个可直接转换为您要运行的指令的primop.首先要确保没有这样的primop存在.然后按照以下步骤操作:https://ghc.haskell.org/trac/ghc/wiki/AddingNewPrimitiveOperations
3. 你应该在GHC.Prim(http://hackage.haskell.org/package/ghc-prim/docs/GHC-Prim.html)中看到你的primop ,在你的程序中使用它.
4. 添加测试,提交补丁:)

Answer 2

我不熟悉低级编程,但在对Freenode的#ghc频道提出问题之后,我得到了一个指向addIntC#primop 的指针,它与LLVM有关llvm.sadd.with.overflow..我不确定llvm会把它编成什么.

GHC的本机代码似乎知道adc指令:X86/CodeGen.hs.但正如评论所说:

我们处理添加,但相当糟糕

编辑:你用文字工作.似乎LLVM后端在https://github.com/ghc/ghc/blob/2b7d9c2b96eb9da3cce7826df4a91c3426095528/compiler/llvmGen/LlvmCodeGen/CodeGen.hs#L737中编译MO_Add2(这是另一个名称plusWord2),相关的票证:https:// ghc.haskell.org/trac/ghc/ticket/9430llvm.uadd.with.overflow