LLVM（Haskell製）を使用した大規模算術

Question

前のquestionに対する答えは、HaskellがplusWord2#をllvm.uadd.with.overflowと表していることを示しています。私は、x86 ADCの命令の仕組みのように、キャリーを長く追加することを検討しています。この命令は2つの引数を追加するだけでなく、キャリービットの内容も追加します。

一つは、次のように長い番号を追加することができる：

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; 

ノートからの抜粋です。これらの操作のうちの1つだけが運ぶことができるので、その後の運搬で十分である。

明らかに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コードになりビットをレジスタに入れてから、キャリービットを自分自身に追加するだけでなく、2つの数値を加算することで、1つではなく1つの命令につき3つまたは4つの命令が得られます。

私は、llvm.uadd.with.overflowを組み合わせて、多倍長算術演算を実装するためにx86上でADC命令のチェーンを作成する方法を知りました。効率的な長い追加を生成したLLVMコードを入手した場合、Haskellのコードから直接効率的に追加するために、Haskellの原始関数に変換することができることを期待していました。

注：私はもちろん、インラインアセンブリまたはGMPを呼び出すためにHaskellのFFIを使用することができますが、それはインライン化停止すると、私は小さな（すなわち< = 256ビットのためのインラインコードに比べて比較的遅いことが疑われる

）オペランド。

私は「打ち鳴らす」の __builtin_addc、二つの数が、キャリービットだけでなくかかりますが、GHCが打ち鳴らす経由してコンパイルされませんので、私はこれがどのように表示されていない3つの引数の追加の形を持っていることを発見しました

有用。

Answer 1

正しいことは、__builtin_addcを使用するときにClangによって形成されたのと同じパターンを使用して、LLVMのIRであなたのHaskellフロントエンドがあなたの運搬算術を表していることを確認することです。

しかし、今日はLLVMで良いコードを生成するとは思わないでください。このような簡単なパターンのためにx86上で現在生成されている絶対に恐ろしいコードについては、http://llvm.org/PR20748を参照してください。しかし、一度そのバグが修正されたら、あなたが望む生成コードを取得する必要があります。