mitsunari@cybozu labs

問題編はこちらのx86カルトクイズです．

Q1

lea    eax, [eax + eax*8]
lea    eax, [eax + eax*4]

45 = 9 * 5 = (8 + 1) * (4 + 1)を利用する．乗算命令が速くなったとはいえ，まだadd/sub/shift/leaの組み合わせを使った方が速いことが多い．

Q2

cdq
xor    eax, edx
sub    eax, edx

条件分岐は可能な限り使わない．次の二つの恒等式

-x = x ^ (-1) - (-1)
 x = x ^ 0 - 0

と

unsigned int m = (x < 0) ? -1 : 0

を組み合わせることで絶対値を

unsigned int m = x >> 31;
return x ^ m - m;

と実現する．ここでmを取得する部分は

mov    edx, eax
sar    edx, 31

であるが，これに限り32bit除算の準備のために用意されたcdqを使うことができる．

cdq ⇔ edx = eax < 0 ? -1 : 0

P4系ではどちらも同じμOPに分解されるがcdqの方がコードサイズは小さくてすむ．

Q3

/* 3.1 */
.label:
...
shr    eax, 1
shr    eax, 1
jnz    .label

Core系では二つの1bitシフトに分割したほうが速くなることがある．それまでのP4では分割しない方がよい．
P4以前では分割しない方がよい．また8倍までの左シフトに対してはshlよりもaddを使った方がよいことが多い．

3.2はdecに変えない方がよい．sub ecx, 1とdec ecxの違いはecx == 0のとき前者はCF(キャリーフラグ) = 1となるが，後者はCFが変化しない点にある．そのためdec/incはフラグに対してパーシャルレジスタストールを起こし遅くなる．バイト長が長くなるがsub/addを使うべきである．

Q4

処理内容は変わらないが，前者のコードが8B 0C 45 00000000と7byteなのに対して，後者は8B 0C 00と3byteですむ．アドレス生成回路としてもシフトが使われるか，加算が使われるかの差があるかもしれない．NASMでは前者のニーモニックを記述しても自動的に後者に変換される．XbyakでもReg32.optimize()において同様の処理を行っている．

Q5

整数として加算するのでxm0の値は0x3fc00000，floatとしては12.0である．

Q6

整数として0x01800000の加算は，xのfloatとしての指数部に3を足すことになる．したがって一般にこの操作はxのfloatとしての値を8倍することになる．これはFLT_MIN(= 0x00800000) <= |x| <= FLT_MAX(= 0x7f7fffff) / 8の範囲で正しい．

通常ならmulss xm0, [_8f]を使うが，padddの方がレイテンシが短い．ただし0は0ではなくFLT_MIN * 4になる．またデノーマル数(0 < |x| < FLT_MIN)，あるいは処理後がオーバーフローする(FLT_MAX/8 < |x|)ときも値が異なることに注意する．

Q7

mov    edx, [esp+4]
bsr    eax, edx
cmovz  eax, edx
ret

bsr命令は入力値edxが0のとき出力値eaxが不定となる仕様であるため単純には使えない．
そのため

    mov    eax, [esp+4]
    test   eax, eax
    jz     .skip
    bsr    eax, eax
    jmp    .exit
.skip:
    mov    eax, [0の時の特殊値]
.exit:

という形にしたくなる．が，bsrは入力値が0のときZF(ゼロフラグ)を1にする．これを利用すれば，ZF == 1のときのみ移動する条件付き移動命令cmovzを使って

    mov    edx, [esp+4]
    bsr    eax, edx
    cmovz  eax, [0の時の特殊値]

とできる．更に特殊値が0ならば答えのように短くできる．

Q8

Windowsではespの指す部分がコミットされていない場合，アクセスがあった時点で4KB単位でコミットされる．その際コミット領域が連続している必要がある．したがって確実にコミットさせるために

sub    esp, 8192
mov   [esp+4096], eax ; dummy write
mov   [esp], eax
add    esp, 8192

などのように4KBずつアクセス(readでも可)しておく必要がある．

Q9

floatからintへのキャストがボトルネックとなる．

通常使う四捨五入では0.5は常に切り上げとなる．そのため統計的にわずかであるが演算結果が大きくなってしまう．これを防ぐために浮動小数から整数へのデフォルトの変換命令は0.5を偶数方向に丸める四捨五入を採用している．たとえば1.5は2，2.5は2，3.5は4となる．

だがこの仕様はCの常に0方向に切り捨てる仕様と相容れない．そのためキャストごとにFPUの制御モードを変更する必要があり，そのコストが非常に大きい．

FPUの場合

cwOrg dw ; デフォルトのFPU制御ワード
cwTrunc dw ; cwOrg |= (3 << 10) ; truncate to 0
 
; ループ前
fldcw    [cwTrunc] ; 丸めモードを0への切り捨てに変更する
; ループ内
fistp    dword [...]
; ループ後
fldcw    [cwOrg] ; デフォルトモードに復元

SSEの場合

mxcsrOrg dd ; デフォルトのMXCSRレジスタ
mxcsrTrunc dd msxcrOrg |= (3 << 11) ; truncate to 0
; ループ前
ldmscsr    [mxcsrTrunc] ; 丸めモードを0への切り捨てに変更する
; ループ内
cvtps2pi [...] ; float x 2 → int x 2
; ループ後
ldmxcsr    [mxcsrOrg] ; デフォルトモードに復元

ただし，FPU制御ワードの変更に比べてmscsrの変更はコストが大きい．ループが小さい場合はSSEを使わずFPUで閉じた方がよいケースもある．

SSE2の場合

cvttps2piを使えばMSCSRレジスタを変更することなく切り捨てを行える

SSE3搭載CPUでFPUを使う場合

fisttpを使えばFPU制御ワードを変更することなく切り捨てを行える

Q10

xに対してxを超えない最大の2巾の指数を求めるにはQ7のbsrを使えばよい．
今回はx>0が保証されているため例外処理は不要である．ループアンロールなどはここではしない．

proc log2A
    mov   edx, [esp+4]
    mov   eax, [esp+8]
    mov   ecx, [esp+12]
    push  ebx
.lp:
    mov   ebx, [eax]
    add   eax, byte 4
    bsr   ebx, ebx
    mov   [edx], ebx
    add   edx, byte 4
    sub   ecx, byte 1
    jnz   .lp
    pop   ebx
    ret

またxを2^e * f(1 <= f < 2)という形で考えると，bsrはeを求めることに相当する．したがってxをdoubleに変換し，その指数部を取り出す方法もある．doubleの仮数部は11bit，指数部は52bitなので52(=32+20)bit右シフトした後，1023を引けばよい．bsrはレイテンシが大きいのでこちらの方が速い．

_1023   dd 1023, 1023, 1023, 1023
 
proc log2B
    mov        edx, [esp+4]
    mov        eax, [esp+8]
    mov        ecx, [esp+12]
.lp:
    cvtpi2pd   xm0, [eax]      ; [D1_H:D1_L:D0_H:D0_L]
    cvtpi2pd   xm1, [eax+8]    ; [D3_H:D3_L:D2_H:D2_L]
    add        eax, 16
    shufps     xm0, xm1, (3 * 64 + 1 * 16 + 3 * 4 + 1)
                               ; [D3_H:D2_H:D1_H:D0_H]
                               ; 32bit右シフト相当
    psrld      xm0, 20         ; 20bit右シフト
    psubd      xm0, [_1023]
    movaps     [edx], xm0
    add        edx, 16
    sub        ecx, byte 4
    jnz        .lp
    ret

なお，もし0 < x < (1 << 23)という条件があるならばdoubleではなくfloatに変換することで更に効率よく処理を行える．floatの仮数部は8bit，指数部は23bitなので23bit右シフトした後，127を引けばよい．

_127 dd 127, 127, 127, 127
 
proc    log2C
    mov        edx, [esp+4]
    mov        eax, [esp+8]
    mov        ecx, [esp+12]
.lp:
    cvtpi2ps   xm0, [eax]      ; [*:*:F1:F0]
    cvtpi2ps   xm1, [eax + 8]  ; [*:*:F3:F2]
    punpckldq  xm0, xm1        ; [F3:F2:F1:F0]
    add        eax, 16
    psrld      xm0, 23
    psubd      xm0, [_127]
    movaps     [edx], xm0
    add        edx, 16
    sub        ecx, byte 4
    jnz        .lp
    ret

よく「アセンブラを使っても最近の最適化コンパイラに勝てない」という意見が聞かれるが，それは単に「自分では確認せず，おうむ返しをしている」か，「コンパイラと同じ(or それ以下の)コードを書いている」かのどちらかであろう．もちろん「コストに見合わない」こともあるがそれはまた別の話である．

一般に最適化ではQ6, 7, 10のような，コンパイラで自動生成されることのない部分を考慮しつつ，さぼれるだけさぼれるロジックを考える．そしてそういうロジックを自在に記述するためにアセンブリ言語やイントリンジック関数を使う．実際，これらのテクニックは音声や動画のコーデックの開発でしばしば使われる．その際Q3などの知識がクリティカルとなることはまずない．瑣末な知識を覚えるよりも(無論覚えるに越したことはない --- 実践に暗記は必要である)，常に代替ロジックが無いかを考える方がよりよいコードに繋がると思う．