mitsunari@cybozu labs

前置きが長くなりましたが，x86(IA-32)について説明を始めます．他のCPUでも概ね似たようなものですが，アセンブリ言語(asm)を記述するときに最低限必要な知識は概ね次の四つです．

• アドレス
• レジスタ
• インストラクションポインタ
• スタック

順次説明します．

アドレス

メモリを読み書きするには場所を指定する必要があります．その場所のことをアドレスといいます．32bitOSでは通常32bitの絶対値(0～4294967295)で指定します．主にC/C++におけるstaticな変数やglobalな変数を扱うときに利用します．仮想メモリや物理メモリなどの話はとりあえず無視してかまいません．必要だと思われたときに勉強してください．

レジスタ

CPU内部で利用できる変数のことです．32bit整数を格納する汎用レジスタ，浮動小数を格納するFPUレジスタ，SIMD命令で扱われるMMX/SSEレジスタなどがあります．このうち汎用レジスタが最低限必要なものです．汎用レジスタは8個あり，eax, ebx, ecx, edx, esi, edi, ebp, espと名前も役割も決まっています．当面はこの8個のレジスタのみを意識するだけで十分です．というか8個しかありません．通常の言語では変数名は自由につけられ，しかも好きなだけ使えるのとは大違いです．

インストラクションポインタ

CPUがまさに今実行しているアドレスです．命令を実行するごとに自動的に次の命令が格納されているアドレスを指すようになります．条件分岐や関数呼び出しなどはインストラクションポインタを変更することで実現されます．

スタック

メモリの一部は，スタック形式(FILO:最初に格納したものは最後に取り出せるデータ形)で扱われる領域として定義されおり，その部分を指します．主にC/C++における局所変数を扱うときに利用されます．スタック領域はある特定値(環境によって異なります)から0に向かう方向に伸びます．0になってしまうとスタックを使い切りスタックオーバーフローとなります．そのスタック領域の先頭アドレスは汎用レジスタespに格納されています(多分Extended Stack Pointerの略)．そのためスタックを操作するにはespを扱うことになります．

要はCPUがやっているのは，メモリをレジスタに読みこんで演算し，結果をメモリ/レジスタに格納する，結果によってインストラクションポインタを変更する．これだけです．アセンブリ言語で開発するということはこれらの手続きを一つ一つ丁寧に記述するということです．難しいのではなく，面倒なのですね．

さて，"Hello Xbyak!"を解説します．

    push((int)"Hello Xbyak!"); // (C1)
    call((int)puts); // (C2)
    add(esp, 4); // (C3)
    ret(); // (C4)

このプログラムはCでいうところの

void hello()
{
    puts("Hello Xbyak!");
}

と同じです(関数名は関係ないですがとりあえずhelloとします)．

C1.

文字列"Hello Xbyak!"はメモリ上のstaticな領域に格納されています．これをputsの引数として与えるには，そのアドレスをスタック領域に保存します．なぜスタック領域に保存するのかについては今後説明します．とりあえずここでは関数の引数はスタックに格納する必要があることを覚えてください．

そして，データをスタック領域に保存するにはpush命令を使います．intにキャストしているのはXbyakの文法のせいです．つまりこの行は"Hello Xbyak!"が格納されたアドレスをスタック領域に確保することを意味します．スタックで述べたようにスタック領域は0に向かいますので，pushするとespの値が4(byte)減ります．デバッガでpushの前後でespの値が4減っていることを確認してください．

C2.

引数がスタック領域に確保にされたのでCのputs関数を呼び出します．Xbyakの文法上，intにキャストしています．この行が実行されるとコンソールに文字列が表示されていることをデバッガで確認してください．

C3.

C1でスタック領域に引数を渡したので，このままではスタック領域は4byte減ったままになります．スタックは貴重です．この関数ではもうこの領域は使いませんから開放する必要があります．espに4を足してスタック領域を基に戻しましょう．add esp, 4はC表記のesp += 4;と同じです．

C4.

hello()関数を抜けて元のmain()関数に戻ります．そのためにはret命令を使います．デバッガでこの命令を実行するとmainに戻ることを確認してください．

以下にgdbで追いかけたときのログを表示します．実際に自分でも実行してみると理解しやすいでしょう．

(gdb) al
0x804b190:      push   0x804a756
0x804b195:      call   0x8048710 <puts@plt>
0x804b19a:      add    esp,0x4
0x804b19d:      ret
(gdb) p $esp
$1 = (void *) 0xbffff2ac      // (*)
(gdb) si
0x0804b195 in ?? ()           // (C1)を実行した
(gdb) p $esp
$2 = (void *) 0xbffff2a8      // (*)に比べてespの値が4減っている
(gdb) ni                      // (C2)callを実行する
Hello Xbyak!                  // 文字列が表示された
0x0804b19a in ?? ()
(gdb) si
0x0804b19d in ?? ()           // (C3)を実行
(gdb) p $esp
$3 = (void *) 0xbffff2ac      // espの値が(*)に戻った
(gdb) ni
main () at t.cpp:19
19              return 0;

今回はアドレス，レジスタとスタック，puts("Hello Xbyak!")の中身を説明しました．次回はサンプルプログラムの説明を続けます．

Cからasm，逆にasmからCを呼び出すために必要な手続きを呼び出し規約といいます．たとえば前回puts()を使う際に，文字列のポインタをpushしましたが，そういう手続きのことです．
x86での規約は大きく分けて3種類あり，細かい部分についてはコンパイラ依存であることも多く，注意が必要です．しかし，ほぼすべてのコンパイラで共通である規約は簡単で覚えやすく，しかも移植性が高くなります．計算処理などOSに依存しにくい部分ではその規約のみに従って記述すれば，Windows/Linux/Macで同一のソースとすることができメンテナンスもしやすくなります．

まずは基本の規約(cdecl)をしっかりと使いこなし，必要になってから他のその他の規約を学べばよいでしょう．詳細は呼出規約(Wikipedia)などを参考にしてください．拙文でも多少触れています．

汎用性の高い規約

Cとasmとの間で呼び出しあう関数は次の規約に従ってください．

• C++での関数宣言にはextern "C"をつける．
• 引数の型はvoid, int(32bit)，またはポインタのみとする．構造体，浮動小数は扱わない．
• 返り値はvoid, int，またはポインタのみとする．

このルールさえ守って記述すれば大抵のコンパイラやOSで問題なく動作させることができます．

たとえば

double func(double a, double b);

とするよりは

void func(double *out, const double *a, const double *b);

とすれば移植性が高くなるということです(もちろんasmとのやりとりが必要な部分のみです)．原理的に後者の方がやや遅くなる可能性がありますが，高速化を目的とした処理では通常，関数内に大きなループが存在するため，この二つの差が問題になるケースはまずありません．逆に，問題になるぐらいならその前後の処理も含めてasmの対象したほうがよい可能性が高いです．

呼び出す側の規約

次に上記規約を満たす関数(func)があったときに，funcをasmから呼び出す手続きについて述べます．asmでは次の規約に従って関数を呼び出してください．

• funcの引数を右側からpushする．
• call funcする(Xbyakではcall(int(func));)．
• 引数の数 x 4だけespを大きくする．
• 関数の返り値はeaxに入っている．void型の場合はeaxの値は不定．

たとえば

int func0(int a, char *b, double *c);

の場合は

push(ポインタcの値);
push(ポインタbの値);
push(aの値);
call(int(func0));
add(esp, 3 * 4); /* 引数が3個なので3 * 4 */

とします．引数がなければpushとaddは省略できます．たとえば

void func();

の場合は

call(int(func));

となります．

呼び出される側の規約

Cから呼び出される関数は次の規約に従ってください．

• 返り値はeaxに代入する(返り値がvoidならeaxの値は不定)．
• 汎用レジスタのうちebx, esi, edi, ebp, espの値は関数を抜けるときに呼び出されたときの状態に戻す．ecx, edxの値を保存する必要はない．
• ret();で関数から戻る．

このとき，関数の引数は「esp + 左から引数が何番目にあるか(1オリジン) * 4」のアドレスに格納されています．

関数の引数についてもう少し詳しく説明します．例としてfunc0()を考えましょう．

func0の呼び出し手続きに従ってfunc0が呼ばれたときのスタックの状況を考えます．c, b, aと順にpushされたのでスタックには大きい方から小さい方へc, b, aと並んでいるはずです．ということは

esp + 8 : c
esp + 4 : b
esp + 0 : a

なのでしょうか．実はちょっと違いまして，callを実行したとき，こっそりと実行していた命令の次の命令の先頭アドレスがスタックに格納されています．つまり正解は

esp + 12: c
esp + 8 : b
esp + 4 : a
esp + 0 : 次の命令のアドレス

となります．デバッガで確認してみましょう．

extern "C" void func(int a, int b, int c)
{
}
 
int main()
{
    func(1, 2, 3);
}

をfuncのところでステップ実行してみます．下記はcallを実行する直前でのレジスタとスタックの状況です．スタック領域に1, 2, 3が格納されていることを確認してください．

<asm>
00401B97   push        3
00401B99   push        2
00401B9B   push        1
00401B9D   call        @ILT+1400(func) (0040157d)
00401BA2   add         esp,0Ch
 
<レジスタ>
 EAX = CCCCCCCC EBX = 7FFDF000 ECX = 00000000 EDX = 00371538
 ESI = 00000000 EDI = 0012FF70
 EIP = 00401B9D ESP = 0012FADC EBP = 0012FF80 EFL = 00000212
 
<スタック>
0012FADC  01 00 00 00 02 00 00 00 03 00 00 00 00 00 00 00
0012FAEC  00 00 00 00 00 F0 FD 7F CC CC CC CC CC CC CC CC
0012FAFC  CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC

ここでcallを実行します．

<レジスタ>
 EAX = CCCCCCCC EBX = 7FFDF000 ECX = 00000000 EDX = 00371538
 ESI = 00000000 EDI = 0012FF70
 EIP = 00401B30 ESP = 0012FAD8 EBP = 0012FF80 EFL = 00000212
 
<スタック>
0012FAD8  A2 1B 40 00 01 00 00 00 02 00 00 00 03 00 00 00
0012FAE8  00 00 00 00 00 00 00 00 00 F0 FD 7F CC CC CC CC
0012FAF8  CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC

espの値が4減ってスタック領域にcallの次の命令のアドレス0x00401ba2が格納されたことがわかります．ret()でfunc()を抜けるときに，この値を参照して帰るべき場所を決定します．そのとき自動的にespも4増えています．

今回は関数の呼び出し規約について説明しました．納得するまで何度もデバッガで確認するのがよいと思います．

x86の解説をいざ始めてみると，どうもblogという媒体はやりにくいので別ページで進めることにしました．すいません．まとめ直すまでしばらくお待ちください．あと基本的なことばかり続いたので，ちょっとマニアックネタに走ってみます．

というわけで突然ですがクイズです．そこそこ高い難易度に設定したつもりですが，いかがでしょう．初心者の方は全然分からなくても大丈夫です．あえて曖昧な記述をしている部分もあります．後半の答えは凄いものがあるといいなあ．あと，難問奇問募集中．

以下は断りがない限り，

• 環境は32bit OS上のPentium4以降のx86 CPU
• 関数の呼び出し規約は__cdecl
• 配列は16byte alignmentされていて複数の配列はオーバーラップしていない
• ループは4の倍数と仮定してよい

ものとします．CPUに依存する場合は明記してください．

Q1(5点)

符号なしeaxの値を45倍せよ．

Q2(6点)

次はgcc 4.2.0が出力した整数の絶対値を取得するコードである．全体のバイト長を短くせよ．

; input :  eax
; output:  eax
; destroy: edx
 
mov    edx, eax
sar    edx, 31
xor    eax, edx
sub    eax, edx

Q3(各4点)

次のコード片について高速化の余地があれば改良せよ．

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

/* 3.2 */
.label:
...
sub   ecx, byte 1
jnz    .label

*すいません，jzはjnzのtypoでした．

Q4(8点)

mov ecx, [eax*2]とmov ecx, [eax + eax]の違いは何か(hint:NASMの出力を見ても分からない)．

Q5(8点)

次のコードを実行したときのxm0の値は何か．答えは最下位32bitのみでよい．

magic dd 0x01800000
x dd 1.5 ; float
 
movss    xm0, [x]
paddd    xm0, [magic]

Q6(12点)

Q5についてxを入力ととらえたとき，通常の方法とこの方法を使った場合の利点と注意点を述べよ．

Q7(10点)

int getBit(unsigned int x)
{
    for (int i = 31; i >= 0; i--) {
        if (x & (1 << i)) return i;
    }
    return 0;
}

をbsrを使って最適化せよ．

Q8(8点)

Windows上で以下のコードは潜在的なバグがある．どこか．なお，espの値は十分大きいものとする．

sub    esp, 8192
mov    [esp], eax
add    esp, 8192

Q9(15点)

以下のコードのボトルネックはどこになると考えられるか．また高速化せよ．

/*
    -1 <= in[i] <= 1とする．
*/
void func(int *out, const float *in, int n)
{
    for (int i = 0; i < n; i++) {
        out[i] = int(in[i] * 32767);
    }
}

Q10(20点)

以下のコードを高速化せよ．ただしsrc[i] > 0 for all iとしてよい．

void log2(int *dest, const int *src, int n)
{
    for (int i = 0; i < n; i++) {
#if 0
          /* わずかな誤差で意図しない値になることがあったので修正 */
//        dest[i] = (int)(log(src[i]) / log(2));
#else
        int j;
        int x = src[i];
        for (j = -1; x > 0; j++) {
            x >>= 1;
        }
        dest[i] = j;
#endif
    }
}

問題編はこちらの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

[μOPでの挙動とパーシャルレジスタストール]

/* 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

[bsrの注意事項]

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におけるスタックの仕様]

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などの知識がクリティカルとなることはまずない．瑣末な知識を覚えるよりも(無論覚えるに越したことはない --- 実践に暗記は必要である)，常に代替ロジックが無いかを考える方がよりよいコードに繋がると思う．