x86-64のフラグと条件分岐を完全に理解する
CMPとTEST、符号付き・符号なし条件、ブランチレスコードの意味と注意点
x86-64のフラグと条件分岐を完全に理解する
本ブログの記事は講義を目的として作成しています。 例はIntel構文を使います。性能は対象CPUと実際の入力分布で測定してください。
cmp eax, edxは結果を保存しないのに、続くjlはなぜ大小を判断できるのか。同じ0xFFFFFFFFが-1にも4,294,967,295にも見えるのはなぜか。答えはRFLAGSと、そのフラグをsigned・unsignedのどちらで解釈するかにある。
主な状態フラグ
| フラグ | 意味 |
|---|---|
ZF | 結果が0 |
CF | unsignedのcarry/borrow |
SF | 結果の最上位ビット |
OF | signed範囲のoverflow |
PF | 結果下位バイトのparity |
通常の条件分岐では特にZF、CF、SF、OFを組み合わせる。
cmpとtest
cmp rax, rdx概念的にrax-rdxを計算し、値を捨ててフラグだけ更新する。
cmp eax, 10
je equal_ten
jl signed_less_than_ten分岐は「直前のcmp」に文法的に結び付いているわけではない。間にフラグを変更する命令があれば、その新しいフラグを読む。
cmp eax, 10
add ecx, 1
jl somewhere ; cmpではなくaddのフラグtestは結果を捨てるandのように働く。
test rax, rax
jz is_zero
test eax, 1
jnz is_oddzero検査やbit mask検査に使われ、CFとOFを0にする。
equalityと大小比較
equal/not equalはsignednessに依存しない。
| 条件 | 分岐 |
|---|---|
| equal / zero | je / jz |
| not equal / nonzero | jne / jnz |
大小は分ける。
| 意味 | signed | unsigned |
|---|---|---|
| left < right | jl | jb |
| left <= right | jle | jbe |
| left > right | jg | ja |
| left >= right | jge | jae |
mov eax, 0FFFFFFFFh
cmp eax, 1
jl signed_less ; -1 < 1なのでtrue
jb unsigned_below ; 4294967295 < 1ではないレジスタにはsigned型タグがない。同じ比較フラグをどの条件で読むかが違う。
CFとOF
8ビットで0xFF+1=0x00はunsigned carryだが、signedでは-1+1=0で正常である。0x7F+1=0x80はunsigned 128として正常だが、signed 127+1はoverflowする。
add al, 1
jc unsigned_overflow
jo signed_overflowC/C++のunsignedはmodulo演算だが、signed overflowは未定義動作である。CPUのOFが言語仕様を定義するわけではない。
incとdecはCFを保持するため、add 1と全フラグが同じではない。
setccとcmovcc
xor eax, eax
cmp edi, esi
setl al
retsigned edi < esiを0または1にする。setccは1バイトだけ書くので上位を明示的に整理する。
cmp eax, edx
cmovl eax, edx条件移動は制御フローを分けず値を選ぶ。ただしdependency chainを長くすることがあり、常にbranchより速いわけではない。
branchlessは自動的に高速ではない
現代CPUは分岐予測を行う。予測しやすいjccは安価である。入力が不規則で両経路が短い場合はsetcc、cmovcc、maskが有利なこともある。実際の分岐分布、misprediction、各経路の仕事量、増えた命令と依存、compiler出力を対象CPUで測る。
ループとshort-circuit
xor eax, eax
xor edx, edx
loop_test:
cmp rdx, rsi
jae loop_done
add eax, [rdi + rdx*4]
inc rdx
jmp loop_test
loop_done:
retjaeはunsignedのi >= countである。最適化によりrotation、unrolling、vectorizationで形は変わる。
if (p != nullptr && p->ready) use(p);test rcx, rcx
jz done
cmp byte ptr [rcx + READY_OFFSET], 0
je done
call use
done:最初の分岐がnull dereferenceを防ぐ。順序も安全性の一部である。
jump table
sub eax, 3
cmp eax, 4
ja default_case
jmp qword ptr [table + rax*8]範囲をunsignedで確認してからtableによる間接分岐を行う。範囲検査はtable外アクセスを防ぐ重要な契約である。
呼び出しを越えてフラグを期待しない
cmp eax, edx
call helper
jl old_result ; helperがフラグを変更できる必要なら呼び出し前に0/1へ変換するか、呼び出し後に再比較する。
まとめ
cmpとtestは結果を保存せずフラグを作る。equalはZF、大小はsignedのSF/OFとunsignedのCF/ZFを区別する。最も近いcmpを探すだけでなく、最後にフラグを定義した命令、条件のsignedness、各edgeで可能な入力範囲を追跡する。