概要：
- ブランチレスは最良の選択ではないかもしれません。
- インライン asm は他のいくつかの最適化を無効にします。最初に他のソースの変更を試してください。たとえば
? :、分岐なしでコンパイルすることが多く、整数 0/1 としてブール値も使用します。
- inline-asm を使用する場合は、asm ブロックの外側でコンパイラが生成するコードを効率的にするために、制約も最適化してください。
- 全体は
cmp %[b], %[a]/で実行可能adc %[k],%[k]です。 手書きのコードはコンパイラが生成するものよりも悪いですが、定数伝播/ CSE /インライン化によってこのコードが(部分的に)最適化されなかった場合、小規模では打ち負かされます。
コンパイラが分岐コードを生成し、プロファイリングがそれが間違った選択であったことを示す場合 (Linux の && などで、その命令での分岐ミスのカウントが多い)perf record -ebranch-misses ./my_program、perf reportはい、分岐のないコードを取得するために何かをする必要があります。
(分岐は、予測可能であれば利点となる可能性があります。分岐とは、使用するコードの順不同の実行を意味し、待機して準備が整う必要はありません。LLVM は最近(k<<1) + 1、x86 コード生成をデフォルトでより分岐させるパッチをマージしました。最新の x86 CPU には非常に強力な分岐予測機能があるため. Clang/LLVM ナイトリー ビルド (そのパッチを適用) は、少なくともループ外のスタンドアロン関数では、この C ソースに対して依然として分岐なしを選択します)。ab
これがバイナリ検索の場合、同じ検索が頻繁に行われない限り、ブランチレスはおそらく良い戦略です。(分岐 + 投機的実行は、クリティカル パスから離れた制御依存関係があることを意味します。
プロファイルに基づく最適化を使用してコンパイルすると、ほとんどの場合、どの分岐が一方通行になるかに関するランタイム情報がコンパイラーに提供されます。予測が不十分な分岐と、全体的に両方のパスをたどるが単純なパターンを持つ分岐との違いをまだ認識していない可能性があります。(または、グローバル ヒストリに基づいて予測可能です。最新のブランチ プレディクタ デザインの多くは、ブランチ ヒストリに基づいてインデックスを作成するため、最後のいくつかのブランチがどのように進んだかによって、現在のブランチに使用されるテーブル エントリが決まります。)
関連: gcc 最適化フラグ -O3 はコードを遅くします -O2は、並べ替えられた配列がループ内の条件に対してほぼ完全な分岐予測を行い、gcc -O3(プロファイルに基づく最適化を使用しない) 分岐のないコードがデータ依存性のボトルネックになるケースを示します。使用からcmov。しかし-O3 -fprofile-use、分岐コードを作成します。(また、それを別の方法で記述すると、自動ベクトル化も向上する低レイテンシーのブランチレス コードが作成されます。)
(k<<1) + (a<b)インライン asm は、たとえば、他の人が提案したように書くことによって、必要な asm を作成するためにコンパイラを手に入れることができない場合、最後の手段にする必要があります。
インラインasmは、多くの最適化、最も明白な定数伝播を打ち負かします（gccが定数をインラインasmコードのブロック外のレジスタに移動する他の回答に見られるように）。 https://gcc.gnu.org/wiki/DontUseInlineAsm .
コンパイラが一部/すべての変数に対して定数値を持っている場合、純粋な C バージョンを使用するためになどを使用することもできますがif(__builtin_constant_p(a))、それはより多くの作業です。__builtin_constant_p()(また、関数のインライン化の前に評価されるClang ではうまく機能しません。)
それでも（入力がコンパイル時の定数ではない場合に限定すると）、コンパイラに全範囲のオプションを与えることはできません。状況に応じて異なる命令を使用したい場合、あなたはうんざりしますが、ここでは多代替制約を使用して柔軟性のほとんどを明らかにすることができaますbのcmp。
通常は、インライン asm を使用するよりも、コンパイラに最適に近いコードを作成させる方が適切です。Inline-asm は、一時的な結果を再利用したり、命令を分散させて他のコンパイラ生成コードと混合したりするコンパイラの機能を破壊します。(命令のスケジューリングは、x86 では順不同で実行されるため大した問題ではありませんが、それでもなお.)
そのasmはかなりがらくたです。分岐ミスが多い場合は、分岐実装よりも優れていますが、分岐のない実装の方がはるかに優れています。
あなたa<bは署名されていない比較です（あなたは、署名されsetbていない以下の条件を使用しています）。したがって、比較結果はキャリーフラグにあります。x86 には add-with-carry 命令があります。なお、k<<1は と同じものですk+k。
したがって、必要な asm (コンパイラ生成またはインライン asm を使用) は次のとおりです。
# k in %rax, a in %rdi, b in %rsi for this example
cmp %rsi, %rdi # CF = (a < b) = the carry-out from edi - esi
adc %rax, %rax # eax = (k<<1) + CF = (k<<1) + (a < b)
コンパイラはaddorleaを 1 だけ左シフトするのに十分に賢く、一部はadcの代わりに使用できるほど賢くsetb、両方を組み合わせることができません。
レジスター引数と戻り値を使用して関数を作成することは、多くの場合、コンパイラーが何を行うかを確認する良い方法ですが、別のレジスターで結果を生成することを強制します。(こちらの Q&Aと Matt Godbolt の CppCon2017 トークも参照してください: 「私のコンパイラは最近何をしてくれましたか? コンパイラのふたを外す」</a>)。
// I also tried a version where k is a function return value,
// or where k is a global, so it's in the same register.
unsigned funcarg(unsigned a, unsigned b, unsigned k) {
if( a < b )
k = (k<<1) + 1;
else
k = (k<<1);
return k;
}
Godbolt コンパイラーの explorerと、他のいくつかのバージョン。(unsignedこのバージョンで使用したaddlのは、asm にあったためです。使用unsigned longすると、xor-zeroing 以外のすべてが 64 ビット レジスタになります。(xor %eax,%eaxこれは、RAX をゼロにするための最良の方法です。)
# gcc7.2 -O3 When it can keep the value in the same reg, uses add instead of lea
leal (%rdx,%rdx), %eax #, <retval>
cmpl %esi, %edi # b, a
adcl $0, %eax #, <retval>
ret
#clang 6.0 スナップショット -O3 xorl %eax, %eax cmpl %esi, %edi setb %al leal (%rax,%rdx,2), %eax retq
# ICC18、gcc と同じだが MOV の保存に失敗する addl %edx, %edx #14.16 cmpl %esi, %edi #17.12 adcl $0, %edx #17.12 movl %edx, %eax #17.12 ret #17.12
MSVC は、手持ちなしではブランチレス コードを作成できない唯一のコンパイラです。(上記の clang(k<<1) + ( a < b );とまったく同じxor/ cmp/ setb/leaシーケンスが得られます (ただし、Windows x86-64 呼び出し規約を使用します)。
funcarg PROC ; x86-64 MSVC CL19 -Ox
lea eax, DWORD PTR [r8*2+1]
cmp ecx, edx
jb SHORT $LN3@funcarg
lea eax, DWORD PTR [r8+r8] ; conditionally jumped over
$LN3@funcarg:
ret 0
インライン asm
他の回答は、実装の問題をかなりうまくカバーしています。インライン asm でアセンブラー エラーをデバッグするには、asm テンプレートが埋められた状態で、コンパイラーがアセンブラーに何を供給しているかを確認するために使用gcc -O3 -S -fverbose-asmaddl %rax, %ecxします。
この最適化された実装では、複数の代替制約を使用して、コンパイラがcmp $imm, r/m、cmp r/m, r、またはcmp r, r/mCMP のいずれかの形式を選択できるようにします。オペコードではなく、可能なメモリオペランドがどちら側に含まれているかによって物事を分割する2つの代替手段を使用しました。 "rme"(rmi)に似"g"ていますが、32 ビット符号拡張即値に限定されます)。
unsigned long inlineasm(unsigned long a, unsigned long b, unsigned long k)
{
__asm__("cmpq %[b], %[a] \n\t"
"adc %[k],%[k]"
: /* outputs */ [k] "+r,r" (k)
: /* inputs */ [a] "r,rm" (a), [b] "rme,re" (b)
: /* clobbers */ "cc"); // "cc" clobber is implicit for x86, but it doesn't hurt
return k;
}
これを、さまざまなコンテキストでインライン化する呼び出し元と共に Godbolt に配置しました。gcc7.2-O3は、スタンドアロン バージョン (レジスタ引数を使用) に期待することを行います。
inlineasm:
movq %rdx, %rax # k, k
cmpq %rsi, %rdi # b, a
adc %rax,%rax # k
ret
他の呼び出し元にインライン化することで、制約がどの程度うまく機能するかを確認できます。
unsigned long call_with_mem(unsigned long *aptr) {
return inlineasm(*aptr, 5, 4);
}
# gcc
movl $4, %eax #, k
cmpq $55555, (%rdi) #, *aptr_3(D)
adc %rax,%rax # k
ret
より大きな即値でmovabs、レジスターに入ります。(ただし"i"or"g"制約があると、gcc はアセンブルしないコードを出力するか、定数を切り捨てて、cmpq に大きな即値定数を使用しようとします。)
純粋な C から得られるものを比較します。
unsigned long call_with_mem_nonasm(unsigned long *aptr) {
return handhold(*aptr, 5, 4);
}
# gcc -O3
xorl %eax, %eax # tmp93
cmpq $4, (%rdi) #, *aptr_3(D)
setbe %al #, tmp93
addq $8, %rax #, k
ret
adc $8, %raxなしsetcのほうがよかったかもしれませんが、__builtin_constant_p()onなしではインライン asm からそれを得ることができませんk。
clang は、mem の代替があればそれを選択することが多いため、次のようにします: /facepalm. インライン asm を使用しないでください。
inlineasm: # clang 5.0
movq %rsi, -8(%rsp)
cmpq -8(%rsp), %rdi
adcq %rdx, %rdx
movq %rdx, %rax
retq
ところで、比較加算へのシフトを最適化するつもりがない限り、コンパイラにk<<1入力として要求することができますし、そうすべきでした。