続いた。でもいい題材が思いつかなかったので、条件分岐とかがいいかなあと思いじゃあfizzbazzでいいか、となった。
その1はここにある。アセンブリ解読 その1 - in neuro
文字列を使うのが（アセンブリだと）アレなのでフラグを返すことにする。
#include <stdint.h> uint8_t fizzbazz(const int32_t n) { uint8_t retval = 0; if (n % 3 == 0) retval ^= 1; if (n % 5 == 0) retval ^= 2; return retval; }
3のみの倍数なら1、5のみの倍数なら2、両方の倍数なら3が返るはず。
とりあえず20くらいまで見て確認してみる。
#include "fizzbazz.c" #include <stdio.h> int main(void) { for(int32_t i=1; i<=20; ++i) printf("%d: %d\n", i, fizzbazz(i)); return 0; }
1: 0 2: 0 3: 1 4: 0 5: 2 6: 1 7: 0 8: 0 9: 1 10: 2 11: 0 12: 1 13: 0 14: 0 15: 3 16: 0 17: 0 18: 1 19: 0 20: 2
はい。じゃあ逆アセンブルしよう。
$ gcc -std=c99 -pedantic -O0 -c fizzbazz.c && objdump -d fizzbazz.o
fizzbazz.o: file format elf64-x86-64 Disassembly of section .text: 0000000000000000 <fizzbazz>: 0: push %rbp 1: mov %rsp,%rbp 4: mov %edi,-0x14(%rbp) 7: movb $0x0,-0x1(%rbp) b: mov -0x14(%rbp),%ecx e: mov $0x55555556,%edx 13: mov %ecx,%eax 15: imul %edx 17: mov %ecx,%eax 19: sar $0x1f,%eax 1c: sub %eax,%edx 1e: mov %edx,%eax 20: mov %eax,%edx 22: add %edx,%edx 24: add %eax,%edx 26: mov %ecx,%eax 28: sub %edx,%eax 2a: test %eax,%eax 2c: jne 32 <fizzbazz+0x32> 2e: xorb $0x1,-0x1(%rbp) 32: mov -0x14(%rbp),%ecx 35: mov $0x66666667,%edx 3a: mov %ecx,%eax 3c: imul %edx 3e: sar %edx 40: mov %ecx,%eax 42: sar $0x1f,%eax 45: sub %eax,%edx 47: mov %edx,%eax 49: mov %eax,%edx 4b: shl $0x2,%edx 4e: add %eax,%edx 50: mov %ecx,%eax 52: sub %edx,%eax 54: test %eax,%eax 56: jne 5c <fizzbazz+0x5c> 58: xorb $0x2,-0x1(%rbp) 5c: movzbl -0x1(%rbp),%eax 60: pop %rbp 61: retq
むむっ、思ったより長い。高級(?)言語の便利さを思い知る。まあまたゆっくり読んでいこう。
最初と最後がprologueとepilogueなのは変わらない。本体を見ていこう。4: mov %edi -0x14(%rbp)でスタックに引数をおいている。何故こんな場所に置くのだろう。ただの32bit整数なのだが。まあでも何にせよ置いたことは確かなので次を読もう。7: movb $0x0 -0x1(%rbp)はretvalの初期化だ。即値0を1byteとしてスタックに書き込んでいる。movbのbは1byteを意味しているらしい。前回
X86アセンブラ/GASでの文法 - Wikibooksで見た。
最後に出てくる
5c: movzbl -0x1(%rbp),%eax
は、8bitとしてレジスタに書き込む命令を使ってretvalを8bit整数として返却値レジスタに書き込んでいるのだ。ということは剰余計算と分岐はこの間で2つ行われていることになる。
if(n % 3 == 0) retval ^= 1;
なので以下の部分が最初のmoduloと分岐を担っているのだろう。後半でも似たような命令のパターンがあり、2つの分岐部分に対応しているものと思われる。
b: mov -0x14(%rbp),%ecx e: mov $0x55555556,%edx 13: mov %ecx,%eax 15: imul %edx 17: mov %ecx,%eax 19: sar $0x1f,%eax 1c: sub %eax,%edx 1e: mov %edx,%eax 20: mov %eax,%edx 22: add %edx,%edx 24: add %eax,%edx 26: mov %ecx,%eax 28: sub %edx,%eax 2a: test %eax,%eax 2c: jne 32 <fizzbazz+0x32> 2e: xorb $0x1,-0x1(%rbp) 32: ...
大まかな構造はわかった。では中身をわかるところから解読していこう。
最初と最後はわかりやすい。最初の行は引数をレジスタへロードしているだけだ。次の行も即値をレジスタにロードしているだけなのだが、この値の意味がよくわからない。三行目は引数の値を多分一時的に使うのであろうeaxにコピーしている。
最後の演算は返却値へのbitwise-xor代入^=なので、3の倍数になっていた場合の分岐先だ。その一行前が<fizzbazz+32>へのジャンプなので、ここで条件を確認して満たしていなかったら2e:の行は飛ばされるということになる。jneはZFがnot equal、つまりfalse(0)ならジャンプするはずなので、ここまでで3の倍数だったらZFが1になるような処理をしてきているはずだ。しばらくは後ろから読んだほうがわかりやすいかもしれない。
b: mov -0x14(%rbp),%ecx ; スタック上の引数をecxレジスタへコピー e: mov $0x55555556,%edx ; 謎の値をedxへロード 13: mov %ecx,%eax ; 引数をeaxにもコピー 15: imul %edx 17: mov %ecx,%eax 19: sar $0x1f,%eax 1c: sub %eax,%edx 1e: mov %edx,%eax 20: mov %eax,%edx 22: add %edx,%edx 24: add %eax,%edx 26: mov %ecx,%eax 28: sub %edx,%eax 2a: test %eax,%eax 2c: jne 32 <fizzbazz+0x32> ; ZFが0なら次の行を飛ばす 2e: xorb $0x1,-0x1(%rbp) ; 即値0x1をretvalへ1バイト値としてxor 32: ...
なら2a: test %eax,%eaxがZFレジスタを変更しているに違いない。test命令を調べたところ（参考：
TEST (x86 instruction) - Wikipediaと
assembly - The point of test %eax %eax - Stack Overflow
）、bitwise andを行い、結果が0ならZFが1になることがわかった。つまり、ここではeaxの値が0なら、ZFが1になり、ジャンプしない、つまり3の倍数だということになる。
直近でeaxが変更されているのはその上の行で、eaxからedxの値が引かれている。つまり、%eax == %edxなら3の倍数ということになる。
その他の簡単な命令もさらっと解釈してしまおう。この部分で剰余を計算しているはずだ。とてもそうは見えないけれど。
b: mov -0x14(%rbp),%ecx ; スタック上の引数をecxレジスタへコピー e: mov $0x55555556,%edx ; 謎の値をedxへロード 13: mov %ecx,%eax ; 引数をeaxにもコピー 15: imul %edx ; ? 17: mov %ecx,%eax ; ecxの値（引数）をeaxにコピー 19: sar $0x1f,%eax ; ? 1c: sub %eax,%edx ; edxからeaxの値を引く 1e: mov %edx,%eax ; edxの値をeaxにコピー 20: mov %eax,%edx ; eaxの値をedxにコピー(?) 22: add %edx,%edx ; edxの値を2倍する(自分に足しこむ) 24: add %eax,%edx ; eaxの値をedxに足しこむ 26: mov %ecx,%eax ; ecx（引数）をeaxに代入する 28: sub %edx,%eax ; eaxの値からedxの値を引く 2a: test %eax,%eax ; eaxの値が0なら（%eax==%edx）ZFを1にする 2c: jne 32 <fizzbazz+0x32> ; ZFが0なら次の行を飛ばす 2e: xorb $0x1,-0x1(%rbp) ; 即値0x1をretvalへ1バイト値としてxor 32: ...
2つ知らない命令がある。imulは掛け算かと思ったがオペランドが1つしかないのでよくわからない。調べてみると、
X86アセンブラ/算術演算命令 - Wikibooks
のように、eaxの値を掛けて下位をeaxに、上位をedxに書き込むらしい。このときedxには謎のマジックナンバーが、eaxには引数が入っている。
ところで、0x55555555というのは、3倍すると0xffffffffになるのではないか。10進では3333とかに対応するということだろうか（この対応関係は感覚的なものだ）。
かのマジックナンバーはこれより1大きいので、3倍したとき0x100000002になるだろう。これは桁があふれるのでedxに0x1が、eaxに0x2が入ることになる。
このedxは概ね3で割った商になっているはずだ。その直後にeaxは引数で上書きされているので、ここは割り算の結果、商が欲しかったのだとわかる。
div命令を使わなかった理由はわからないが、遅いと聞いたことがあるのでそれだろうか。
なんとなく想像がついてきた。この段階でもう一度後ろの方を解釈しなおしてみよう。
1e: mov %edx,%eax ; edxの値をeaxにコピー 20: mov %eax,%edx ; eaxの値をedxにコピー(?) 22: add %edx,%edx ; edxを2倍する 24: add %eax,%edx ; eaxの値（2倍する前のedx）をedxに足す（3倍になった） 26: mov %ecx,%eax ; eaxに引数を代入する 28: sub %edx,%eax ; 引数からedxの値を引く 2a: test %eax,%eax ; eaxが0なら（つまりedx == 引数）ZFを1にする 2c: jne 32 <fizzbazz+0x32> ; ZFが0なら次の行を飛ばす 2e: xorb $0x1,-0x1(%rbp) ; 即値0x1をretvalへ1バイト値としてxor 32: ...
これは、3で割った商に3をかけて、それが最初の数と等しいかどうかで倍数判定をしているのではないか。そのために商が必要だったのだ。だとするとedxには1e:時点で3で割った結果が入っていることになる。
わからなかったもう一つの命令を調べてみよう。sarは算術右シフトだ。符号ビットは固定される。最初に書いた関数がint32_tを取っていたのでこうなったのだろうか。
ただ、0x1fが31でここで32bit整数を使っているので、正の数は0になり、負の数は-1になる。思い出して欲しいのだが、商を得るために使っていた手法を負の数に使うと-1や-2などについては-1になり、-3に対して行うと-2が得られる。
つまり結果が-1だけ大きくなる。続く1c: sub %eax,%edxがここの帳尻を合わせているのだろう。正の数ならどうせ0なので影響はない。
ここで言っていることはわかりにくいので計算結果を書いておく。
edx eax 0x55555556 * -3(0xfffffffd) = 0xfffffffefffffffe => 0xfffffffe 0xfffffffe 0x55555556 * -2(0xfffffffe) = 0xffffffff55555554 => 0xffffffff 0x55555554 0x55555556 * -1(0xffffffff) = 0xffffffffaaaaaaaa => 0xffffffff 0xaaaaaaaa 0x55555556 * 0(0x00000000) = 0x0 => 0x0 0x0 0x55555556 * 1(0x00000001) = 0x55555556 => 0x0 0x55555556 0x55555556 * 2(0x00000002) = 0xaaaaaaac => 0x0 0xaaaaaaac 0x55555556 * 3(0x00000003) = 0x100000002 => 0x1 0x2
というわけでこの部分を前から追いかけて行こう。一対一対応で書くのをやめて、意味を書いていく。
b: mov -0x14(%rbp),%ecx ; スタック上の引数をecxレジスタへコピー e: mov $0x55555556,%edx ; (0x100000002 / 3)をedxへロード 13: mov %ecx,%eax ; 引数をeaxにコピー 15: imul %edx ; 3で割った商（正の数なら。負なら-1大きい）をedxへ 17: mov %ecx,%eax ; 引数をeaxにコピー 19: sar $0x1f,%eax ; 引数が正の値なら0を、負なら-1をeaxに 1c: sub %eax,%edx ; edxからeaxの値を引いて正負に依らず商を合わせる 1e: mov %edx,%eax ; 3で割った商をeaxにコピー 20: mov %eax,%edx ; 3で割った商をedxにコピー(二度目?) 22: add %edx,%edx ; 3で割った商を2倍 24: add %eax,%edx ; 商を足して3で割った商の3倍を計算 26: mov %ecx,%eax ; 引数をeaxに代入 28: sub %edx,%eax ; 引数から引数を3で割った商の3倍を減算 2a: test %eax,%eax ; n - (n/3)*3 == 0ならZFを1にする 2c: jne 32 <fizzbazz+0x32> ; ZFが0なら次の行を飛ばす 2e: xorb $0x1,-0x1(%rbp) ; 即値0x1をretvalへ1バイト値としてxor 32: ...
ようやくちゃんとmodが計算されていることがわかった。
if (n % 5 == 0) retval ^= 2;
残った方は5に対して同様のことをやっているはずだ。
32: mov -0x14(%rbp),%ecx 35: mov $0x66666667,%edx 3a: mov %ecx,%eax 3c: imul %edx 3e: sar %edx 40: mov %ecx,%eax 42: sar $0x1f,%eax 45: sub %eax,%edx 47: mov %edx,%eax 49: mov %eax,%edx 4b: shl $0x2,%edx 4e: add %eax,%edx 50: mov %ecx,%eax 52: sub %edx,%eax 54: test %eax,%eax 56: jne 5c <fizzbazz+0x5c> 58: xorb $0x2,-0x1(%rbp) 5c: ...
確かに骨格は同じだ。だが少しだけやっていることが違う。ざっと解釈していこう。
今度のマジックナンバーは、掛け算によってこうなる。
0x66666667 * -5(0xfffffffb) = 0xfffffffdfffffffd 0x66666667 * -4(0xfffffffc) = 0xfffffffe66666664 0x66666667 * -3(0xfffffffd) = 0xfffffffecccccccb 0x66666667 * -2(0xfffffffe) = 0xffffffff33333332 0x66666667 * -1(0xffffffff) = 0xffffffff99999999 0x66666667 * 0(0x00000000) = 0x0 0x66666667 * 1(0x00000001) = 0x66666667 0x66666667 * 2(0x00000002) = 0xccccccce 0x66666667 * 3(0x00000003) = 0x133333335 0x66666667 * 4(0x00000004) = 0x19999999c 0x66666667 * 5(0x00000005) = 0x200000003 ... 0x66666667 * 10(0x0000000a) = 0x400000006
やはり商が計算できる。ただ、上位ビットを2で割らなければならないようだが。
命令を読んでいく。
32: mov -0x14(%rbp),%ecx ; スタックに積んだ引数をecxへロード 35: mov $0x66666667,%edx ; マジックナンバーをedxへロード 3a: mov %ecx,%eax ; eaxへ引数を代入 3c: imul %edx ; edxとeaxの積の上位をedxへ、下位をeaxへ 3e: sar %edx ; edxを右シフトして2で割る（正なら商、負なら商-1を得る） 40: mov %ecx,%eax ; eaxへ引数を代入 42: sar $0x1f,%eax ; 31回の右シフトで符号によって0か-1を得る 45: sub %eax,%edx ; edxから先の値を引いて完全な商を得る 47: mov %edx,%eax ; 商をeaxへコピー 49: mov %eax,%edx ; 商をedxへコピー（movでデータは壊れないはずでは?） 4b: shl $0x2,%edx ; 2回左シフトして商を4倍する 4e: add %eax,%edx ; 商の4倍に商を足して5倍を作る 50: mov %ecx,%eax ; eaxへ引数を代入 52: sub %edx,%eax ; 引数から商の5倍を引く 54: test %eax,%eax ; 結果が0ならZFを1に 56: jne 5c <fizzbazz+0x5c> ; ZFが0なら次の行を飛ばす 58: xorb $0x2,-0x1(%rbp) ; 即値2をretvalへxor代入する 5c: ...
大まかな流れがわかっているだけでこんなにも読みやすくなるというのも驚きだ。やっていることがほぼわかってしまった。
2つの剰余と分岐の部分、そして最初と最後の引数のロードや一時変数の確保、返却値の書き込みがわかったので、このアセンブリコードが何をしているのかがわかった。長いので全体をまた書くのはやめておく。
-Ofast
では最適化でどうなるか見よう。
fizzbazz.o: file format elf64-x86-64 Disassembly of section .text: 0000000000000000 <fizzbazz>: 0: mov %edi,%eax 2: mov $0x55555556,%edx 7: mov %edi,%esi 9: imul %edx b: sar $0x1f,%esi e: sub %esi,%edx 10: lea (%rdx,%rdx,2),%eax 13: mov $0x66666667,%edx 18: cmp %eax,%edi 1a: mov %edi,%eax 1c: sete %cl 1f: imul %edx 21: mov %ecx,%eax 23: xor $0x2,%eax 26: sar %edx 28: sub %esi,%edx 2a: lea (%rdx,%rdx,4),%edx 2d: cmp %edx,%edi 2f: cmove %eax,%ecx 32: mov %ecx,%eax 34: retq
凄く短い。そしてprologueとepirogueがなくなった。スタックを使わない気なのだろう。見覚えのあるマジックナンバーや命令があるので概ね同じことをしているのがわかるが、簡潔になっている。そして、知らない命令がある。調べつつ埋めよう。 前回と今回で触れた本とサイトの他に、インラインアセンブラで学ぶアセンブリ言語 第3回 (1/3)：CodeZine（コードジン）と、 Intel Instruction Set、あと Tips IA32（x86）命令一覧を参考にした。
0000000000000000 <fizzbazz>: 0: mov %edi,%eax ; 引数をeaxレジスタへコピー 2: mov $0x55555556,%edx ; マジックナンバーをedxへ 7: mov %edi,%esi ; 引数をesiへコピー 9: imul %edx ; マジックナンバーと引数を掛け算 b: sar $0x1f,%esi ; 31回右シフトで0か-1を作り、esiに置く e: sub %esi,%edx ; esiを引いて商を得る 10: lea (%rdx,%rdx,2),%eax ; edx（商）をアドレス（64bit）と読み替えて ; 自身の2倍と足したアドレス（3倍）をeaxへ 13: mov $0x66666667,%edx ; edxへ今度は5で割るための定数を代入 18: cmp %eax,%edi ; eax（商の3倍）をedi（引数）と比較 ; 一致していればZFがtrueになる 1a: mov %edi,%eax ; 引数をeaxへコピー 1c: sete %cl ; ZFがtrueならcl（ecxの下位8bit）の値を1に 1f: imul %edx ; 定数と引数の積の上位ビットをedxへ 21: mov %ecx,%eax ; ecxの内容（mod3の結果）をeaxへコピー 23: xor $0x2,%eax ; eaxと即値2のxorをeaxへ 26: sar %edx ; edxをビットシフトによって2で割る 28: sub %esi,%edx ; 正負に応じた値（b:からの使い回し）を ; edxから引いて商を得る 2a: lea (%rdx,%rdx,4),%edx ; アドレス演算によってedxの値を5倍する 2d: cmp %edx,%edi ; 商の5倍と引数を比較 2f: cmove %eax,%ecx ; 一致していたら先のxorの結果をecxへコピー ; 一致していなかった場合ecxは1c:で ; 設定された時のまま 32: mov %ecx,%eax ; ecxの内容を返却値へコピー 34: retq
剰余演算の部分はあまり変わっていない。何倍かにする部分がアドレス演算になっているくらいだ。これは前回の記事でも見た現象だ。
ただ、分岐の部分が結構変わっている。cmp命令を使い、その結果のフラグレジスタを使って、seteやcmoveが用いられている。
この辺りを重点的に見ていこう。n%3==0なら、1c: sete %clによってecxレジスタの下位の値が1になる。その後、その値が21: mov %ecx %eaxの部分でeaxへコピーされ、eaxの方に23: xor $0x2,%eaxと変更が加えられている。
このxorはなんだろうか。eaxの値は条件によって、
if (n%3 == 0) eax == 0b0001; else eax == 0b0000;
になっているだろう。そこへ即値2をxorするのだから、
n%3 == 0 n%3 != 0 0b0001 0b0000 xor 0b0010 xor 0b0010 ---------- ---------- 0b0011 0b0010
になる。つまりここで既に(n%5==0)だったときの結果を作っておいてあるわけだ。気が早い。
そして、2f: cmove %eax %ecxで、2d: cmpの結果によってecxの値を必要なら更新し、32: mov %ecx %eaxで更新したecxの値をeaxへ代入して返却しているのだ。
ここで、少し「ecxとeaxの使い方逆転させたら命令数減らせるのでは？」と思った。最後のmovをなくせるのではないかと。途中でecxとeaxの役割を交換すれば、最後の32: mov %ecx,%eaxをなくせるのではないか。
で、少し試してみたのだが、1f: imul %edxの部分が曲者だった。ここでeaxを使うので、sete clのところをsete alにしてしまうと結果が変わる。では計算の順序を変えてseteを後にすれば、と思ったが、imulがフラグレジスタを書き換える可能性がある。1オペランドの時はしないのでは、と思ったが、もしかするとコンパイラがこういうやり方をしているのはimulの後にEFLAGSが無事である保証がないからなのかもしれない。では別のレジスタを使ってはどうか、とも思ったが殆どの汎用レジスタは使われている。本にはrbxレジスタは変更不可と書かれているし実際今回のコードで使われていないので書き換えるわけにはいかないのだろう。また、スタックを使うとメモリアクセスが生じるので本末転倒だ。いかなL1キャッシュといえどレジスタアクセスよりは遅いだろうと予想され、また最適化したときにスタックを使わないようになっていることからもその予想の正しさが窺える。
とりあえず今回はこれで終えておこう。条件分岐の例を一つ読めるようになった。また、最適化を掛けるとコンパイラが簡単な整数演算をアドレス演算に切り替えるとか、スタックを使わなくなるとか、最適化なしでも剰余演算でdivを使わず謎のマジックナンバーを（最適化なしでも）使うなどの面白い現象がいくつか見られたので満足だ。古い時代に最適化は後にしろと言われていたのは、こういうことが起きたからなのかなと思ったりしてみる。
次があるとしたら、単純な関数、条件分岐ときたので、ループにしよう。ちょっと間が開くかも知れないが。
