これを行う組み込み関数があります: _addcarry_u64。ただし、Visual StudioとICC (少なくとも VS 2013 と 2015、ICC 13 と ICC 15) のみがこれを効率的に実行します。Clang 3.7 および GCC 5.2 は、この組み込み関数を使用して効率的なコードを生成しません。
さらに、Clang には、これを実行すると思われる組み込みの がありますが、__builtin_addcll効率的なコードも生成されません。
Visual Studio がこれを行う理由は、64 ビット モードでのインライン アセンブリが許可されていないため、コンパイラが組み込み関数を使用してこれを行う方法を提供する必要があるためです (ただし、Microsoft はこれを実装するのに時間がかかりました)。
したがって、Visual Studio では_addcarry_u64. ICC を使用する _addcarry_u64か、インライン アセンブリを使用します。Clang と GCC では、インライン アセンブリを使用します。
Broadwell マイクロアーキテクチャ以降、2 つの新しい命令があることに注意してください:adcxおよび_addcarryx_u64adox組み込み関数でアクセスできます。これらの組み込み関数に関する Intel のドキュメントは、以前はコンパイラによって生成されたアセンブリとは異なっていましたが、現在はドキュメントが正しいようです。ただし、Visual Studio は依然として with のみを生成するように見えますが、ICC はとwith this 組み込みの両方を生成します。しかし、ICC は両方の命令を生成しますが、最適なコード (ICC 15) を生成しないため、インライン アセンブリが必要です。adcx_addcarryx_u64adcxadox
個人的には、これを行うために C/C++ の非標準機能 (インライン アセンブリや組み込み関数など) が必要であるという事実は C/C++ の弱点だと思いますが、他の人は同意しないかもしれません。このadc命令は、1979 年から x86 命令セットに含まれています。C/C++ コンパイラが必要なタイミングを最適に判断できることに息をのむことはありませんadc。など__int128の組み込み型を使用できますが、組み込みではないより大きな型が必要な場合は、インライン アセンブリや組み込み関数などの非標準の C/C++ 機能を使用する必要があります。
これを行うためのインライン アセンブリ コードに関しては、キャリー フラグを使用したマルチワード加算で、レジスタ内の 8 つの 64 ビット整数に対する 256 ビット加算のソリューションを既に投稿しました。
これが再投稿されたコードです。
#define ADD256(X1, X2, X3, X4, Y1, Y2, Y3, Y4) \
__asm__ __volatile__ ( \
"addq %[v1], %[u1] \n" \
"adcq %[v2], %[u2] \n" \
"adcq %[v3], %[u3] \n" \
"adcq %[v4], %[u4] \n" \
: [u1] "+&r" (X1), [u2] "+&r" (X2), [u3] "+&r" (X3), [u4] "+&r" (X4) \
: [v1] "r" (Y1), [v2] "r" (Y2), [v3] "r" (Y3), [v4] "r" (Y4))
メモリから値を明示的にロードしたい場合は、次のようなことができます
//uint64_t dst[4] = {1,1,1,1};
//uint64_t src[4] = {1,2,3,4};
asm (
"movq (%[in]), %%rax\n"
"addq %%rax, %[out]\n"
"movq 8(%[in]), %%rax\n"
"adcq %%rax, 8%[out]\n"
"movq 16(%[in]), %%rax\n"
"adcq %%rax, 16%[out]\n"
"movq 24(%[in]), %%rax\n"
"adcq %%rax, 24%[out]\n"
: [out] "=m" (dst)
: [in]"r" (src)
: "%rax"
);
これにより、ICC の次の関数とほぼ同じアセンブリが生成されます
void add256(uint256 *x, uint256 *y) {
unsigned char c = 0;
c = _addcarry_u64(c, x->x1, y->x1, &x->x1);
c = _addcarry_u64(c, x->x2, y->x2, &x->x2);
c = _addcarry_u64(c, x->x3, y->x3, &x->x3);
_addcarry_u64(c, x->x4, y->x4, &x->x4);
}
私は GCC インライン アセンブリ (または一般的なインライン アセンブリ - 通常は NASM などのアセンブラを使用) の経験が限られているため、より優れたインライン アセンブリ ソリューションがあるかもしれません。
だから私が探しているのは、任意の長さに一般化できるコードです
この質問に答えるために、テンプレート メタ プログラミングを使用した別のソリューションを紹介します。これと同じトリックをループ展開に使用しました。これにより、ICC で最適なコードが生成されます。Clang または GCC が_addcarry_u64効率的に実装される場合、これは適切な一般的な解決策になります。
#include <x86intrin.h>
#include <inttypes.h>
#define LEN 4 // N = N*64-bit add e.g. 4=256-bit add, 3=192-bit add, ...
static unsigned char c = 0;
template<int START, int N>
struct Repeat {
static void add (uint64_t *x, uint64_t *y) {
c = _addcarry_u64(c, x[START], y[START], &x[START]);
Repeat<START+1, N>::add(x,y);
}
};
template<int N>
struct Repeat<LEN, N> {
static void add (uint64_t *x, uint64_t *y) {}
};
void sum_unroll(uint64_t *x, uint64_t *y) {
Repeat<0,LEN>::add(x,y);
}
ICCからの組立
xorl %r10d, %r10d #12.13
movzbl c(%rip), %eax #12.13
cmpl %eax, %r10d #12.13
movq (%rsi), %rdx #12.13
adcq %rdx, (%rdi) #12.13
movq 8(%rsi), %rcx #12.13
adcq %rcx, 8(%rdi) #12.13
movq 16(%rsi), %r8 #12.13
adcq %r8, 16(%rdi) #12.13
movq 24(%rsi), %r9 #12.13
adcq %r9, 24(%rdi) #12.13
setb %r10b
メタ プログラミングはアセンブラの基本的な機能であるため、C と C++ (テンプレート メタ プログラミング ハックを除く) にも解決策がありません (D 言語には解決策があります)。
上記で使用した、メモリを参照するインライン アセンブリは、関数でいくつかの問題を引き起こしていました。これは、よりうまく機能するように見える新しいバージョンです
void foo(uint64_t *dst, uint64_t *src)
{
__asm (
"movq (%[in]), %%rax\n"
"addq %%rax, (%[out])\n"
"movq 8(%[in]), %%rax\n"
"adcq %%rax, 8(%[out])\n"
"movq 16(%[in]), %%rax\n"
"addq %%rax, 16(%[out])\n"
"movq 24(%[in]), %%rax\n"
"adcq %%rax, 24(%[out])\n"
:
: [in] "r" (src), [out] "r" (dst)
: "%rax"
);
}