機械語ではマシンの挙動は理解できない
実のところ機械語はマシンに対する高レベルな挙動を示す命令であって実行を厳密に写像したものではない。（何を言っているんだわたしは？）
「マシン語ってどんな感じか知りたくなった方へ」という大人気のエントリと、ニコニコ動画を見て、昨今の最新マイクロプロセッサでは機械語がもはや機械の挙動と一対一に対応しなくなっちゃったのである、というツッコミをしたくなった。http://d.hatena.ne.jp/shi3z/20070913
「水野拓宏のTK-80講座」これが素敵すぎる。http://www.nicovideo.jp/watch/sm1048903
最近のプロセッサ(Pentium 4とかXeonとか)は機械語を機械が直接実行するのではなく（じゃあ、なんで機械語というだよというツッコミは諸般の事情で却下（ｗ））、機械語をμOPという機械語と一対Nに対応する命令に変換し実行するのである。JavaのJITみたいな感じである。
機械語を逐次的に解釈実行するのであれば、昔のマイクロプログラミングという、機械語を機械が直接実行するのではなく、マイクロプログラムというインタプリターによって逐次実行するのと変わらないので、機械語レベルのセマンティックスと実行の順序は変わらない。
昨今のプロセッサは、機械語をμOPというのに変換してそれを「並列」に実行しちゃうのである。（ここで、ふーんと思ったあなた、感動が足りません。ここはのけぞるところです）
並列に実行しちゃうことをOut of Order (OOO）実行とか言っちゃうのだけど、（厳密に言えばOOOは並列に実行することを含意していない。実行順が機械語の順番と違うことを言っているだけ）、それによって、ある命令列によって引き起こされる効果を、他の人が観察すると機械語と違う順序で観察されるのである。例えば、あるアドレス（X) にAレジスタの値を代入し、次のアドレス（X+1）にBレジスタの値を代入するなんていう命令列では、Aレジスタの値が代入されてからBレジスタの値が代入されるなどという順序は、プロセッサは保証していないのである。（ああああ〜）
さらに怖いことに、あるアドレス（X) の内容をAレジスタに入れて、それを別のアドレス（Y) に移動し、そしてそれをアドレスを増加しながらNバイト移動する、なんていう典型的なコード（イディオムと言ってもいい）は、X, X+1, X+2, …を A0, A1, A2, …へ移動し、その後、Y, Y+1, Y+2, …へ移動するみたいなμOPに変換され、OOOで並列に実行される。ここでA0, A1, A2,…ってなんだよということになるのだが、内部的なレジスタで機械語からはAレジスタと見えるものである。？？？なのだが、Aレジスタが内部的にはN個あって、それぞれ処理が独立であれば並列に実行可能なので、並列に実行されて、機械語的には、プロセッサがよきにはからって、プログラマにその挙動が観測されるのである。この内部的なレジスタをよきにはからって実行することを register renamingなどと呼ぶ。
Aレジスタがいくつの内部的なレジスタに対応するかはIntelのマニュアルには一切記されていない。昔のプロセッサにはregister renamingなんてものはなくて実直に一個一個実行していたのであるが、昨今のプロセッサでは性能向上のために山のように内部レジスタあるので、ループをアンローリングして、山のようにmov命令を繰り返すとそれに比例してスループットが上がるのが観測される。
例えば下記はarch/i386/lib/usercopy.c の __copy_user_zeroing_intel_nocache() からの抜粋である。EAXレジスタとEDXレジスタにfrom, from+4、の内容をコピーし、それto, to+4へコピーしている。（つまりfromで示されるアドレスの内容をtoで示されるアドレスへひたすらコピーしている）
EAXレジスタとEDXレジスタへの移動が並列に実行できるのはよいとして、from, from+8, from+16, from+24, from+32, from+40, from+48, from+56へのコピーも機械語的にはEAXレジスタという同じレジスタを利用しているにもかかわらず、OOOで同時並列でμOP的には実行されるのである。
+ "2: movl 0(%4), %%eax\n" + "21: movl 4(%4), %%edx\n" + " movnti %%eax, 0(%3)\n" + " movnti %%edx, 4(%3)\n" + "3: movl 8(%4), %%eax\n" + "31: movl 12(%4),%%edx\n" + " movnti %%eax, 8(%3)\n" + " movnti %%edx, 12(%3)\n" + "4: movl 16(%4), %%eax\n" + "41: movl 20(%4), %%edx\n" + " movnti %%eax, 16(%3)\n" + " movnti %%edx, 20(%3)\n" + "10: movl 24(%4), %%eax\n" + "51: movl 28(%4), %%edx\n" + " movnti %%eax, 24(%3)\n" + " movnti %%edx, 28(%3)\n" + "11: movl 32(%4), %%eax\n" + "61: movl 36(%4), %%edx\n" + " movnti %%eax, 32(%3)\n" + " movnti %%edx, 36(%3)\n" + "12: movl 40(%4), %%eax\n" + "71: movl 44(%4), %%edx\n" + " movnti %%eax, 40(%3)\n" + " movnti %%edx, 44(%3)\n" + "13: movl 48(%4), %%eax\n" + "81: movl 52(%4), %%edx\n" + " movnti %%eax, 48(%3)\n" + " movnti %%edx, 52(%3)\n" + "14: movl 56(%4), %%eax\n" + "91: movl 60(%4), %%edx\n" + " movnti %%eax, 56(%3)\n" + " movnti %%edx, 60(%3)\n"
このとき、いつキャッシュミスが発生し（それはμOPの実行を数百命令浪費する）、いつキャッシュヒットするかはプロセッサの状態によるので、後ろの命令が先の命令を追い越して先に実行するというのは通常に発生している。上の命令列のどれが最初に終了するかは、誰もわからないのである。（すげーな、これは）
こんなことは通常のプログラマのうかがい知れないところで実行されているのである。しかも誰もそんなことは教えてくれない。わたしも知らなかった。こーゆー実行の挙動は外部から、観測するしかないのである。
μOPがどのくらい同時実行されているかは各プロセッサ（Xeonとか）の実装に依存する。モデル番号とか怪しげな番号ごとに微妙に実装を変更しているようで、実装の違いはステッピングというさらに細かい単位で観測されるようである。Intelの中の人の情報によれば〜1000μOPを超えるらしいが定かではない。
OOOとregister renamingだけでも、機械語とμOPの挙動の差はあるのに、ジャンプ命令なんかは、その先の命令も投機的に実行しちゃうので、もうわけがわからないというのが実態である。投機的実行というのは、条件分岐のどっちかを実行するだろうとプロセッサが予測して、条件が真であるか偽であるか分からない状態で、どっちかに決めうちをして、あらかじめ実行してしまうのである。決めうちが成功すれば、既に実行しているので性能が向上してしまう。どう決めうちするかは、以前ジャンプした方へジャンプするだろうとか、結構アバウトな予測でも意外とうまくいったりするのである。
機械語の実行というのは、機械語をメモリから取り出し（これをフェッチという）、解釈し（デコードという）、実行し、PC（プログラムカウンタ）を一つ増やし、それを繰り返す、ということになる。ジャンプ命令の実行というのはPCを直接変更することに他ならない。ジャンプの場合、機械語をメモリから取り出すというのがあらかじめできなくなるので性能を出すために、どれだけ命令をプリフェッチできるかにかかっている。
ジャンプというのは数命令に一回程度発生し、命令のフェッチをパイプラインするためにできるだけジャンプ命令がないほうが性能向上に役立つのであるが(loop unrolling)、投機的実行はジャンプ命令があってもおかまいなしにがんがん行っちゃうという方法なのである。
ちなみに命令をデコードしてμOPに変更するのは、コストがかかるので、一度変更されたものはTC（トレースキャッシュ）と呼ばれる命令キャッシュに格納され、2度目以降はTCからμOPを直接実行する。そしてデコードされていない命令の実行は命令キャッシュミスを発生させて実行コストが非常に高くてうれしくない。閑話休題。
というようなことで昨今のプロセッサではメモリのコピーと言う非常に単純な操作ですら、外部からは命令の実行順を保障した形では観測できないのである。
シングルプロセッサでは、そーゆめんどうな事は、通常は観測できない。しかし、マルチコアになると、あるコアで書き込んだものを別のコアで利用するなんていうことが日常茶飯事で発生するのであるが、それについては別途なにがしかの方法が必要になってくるのである。
性能向上のためのバイナリハックのネタ満載の今日この頃である。
「メモリアクセスは遅い」http://blog.miraclelinux.com/yume/2007/09/post_b3bc.htmlというユメのチカラも参考にしてほしい。キャッシュのお話である。
http://blog.livedoor.jp/dankogai/archives/50910559.html マシン語読みの言語知らず/404 Blog Not Found あたりも。
注記：メモリ書き出しのオーダーについてかなりアバウトな記述をしたが、精密は議論はIntel® 64 Architecture Memory Ordering White Paper http://www.intel.com/products/processor/manuals/index.htm を参照のこと。
注記2： id:hyoshiok:20070918#p1 を記したので、参照のこと。
