このページは、Agner Fogさんによる同名のマニュアルの、藤波順久による日本語訳です。原文(英語)の著作権はAgner Fogさんにあります。また、日本語訳中の「私」とは、Agner Fogさんのことです。原文は
http://announce.com/agner/assem/assem.html
を参照してください。
このページは、現在更新中であり、原文の古い版(1997-03-16)に基づいている章がいくつかあります。
このマニュアルは他の情報源に比べて理解しやすく正確で、他に見られない細かい事項をたくさん含んでいる。この情報を使えば、あなたは多くの場合に、あるコード片が正確に何クロックサイクルかかるのか計算することができるようになる。
このマニュアルでは次のようなバージョンのPentiumプロセッサについて議論する。
略称 名前 ------------------------------------------------ PPlain plain old Pentium (without MMX) PMMX Pentium with MMX PPro Pentium Pro PII Pentium II ------------------------------------------------
このマニュアルの情報は、私自身の調査と試験に基づいており、さまざまな人たちから受け取った情報で補足されている。このマニュアルのために追加情報を私に送ってくれた人々に感謝したい。これまでの私の調査はPPlainとPMMXしかカバーしていない。PProとPIIについては簡単に記述されているだけである。
アセンブリ言語でのプログラミングは、高級言語よりはるかに難しい。バグを生成するのは容易であり、その発見はたいへん困難である。ここで警告である! 読者は既にアセンブリ言語の経験があると仮定する。もしそうでなければ、複雑な最適化を始める前に、どうかアセンブリ言語に関する本を何か読んで、プログラミングの経験を得てほしい。
Pentiumチップのハードウェア設計は、一般的な最適化方法を使ったというよりはむしろ、いくつかのよく使われる命令やその組合せに特に最適化された、多くの特徴を持っている。その結果、ソフトウェアをこの設計向きに最適化するのはかなり複雑で、多くの例外があるが、相当な性能向上が可能かもしれない。
コードをアセンブリ言語に変換する前に、使っているアルゴリズムが最適であることを確認してほしい。コード片をアセンブラコードに直すよりアルゴリズムを改良したほうがずっとよい結果になることがしばしばある。
次に、プログラムの決定的に重要な部分を同定しなければならない。しばしば、99%以上のCPU時間がプログラムの最も内側のループで消費されている。この場合、そのループだけを最適化し、それ以外はすべて高級言語のままにしておくべきである。アセンブラプログラマの中には、プログラムの誤った部分を最適化するのにエネルギーを浪費し、努力の主な効果が、プログラムのデバッグや保守を難しくしただけという人もいる!
もしプログラムの決定的に重要な部分がどこか明らかでなければ、プロファイラを使ってみつけるとよい。もしボトルネックがディスクアクセスであるとわかったら、アセンブリプログラミングに行くのではなくて、ディスクアクセスをシーケンシャルに行うようにプログラムを変更して、ディスクのキャッシングを改良するとよい。もしボトルネックがグラフィクスの出力なら、グラフィクスの手続きを呼ぶ回数を減らす方法を探すとよい。
高級言語のコンパイラのいくつかは比較的よいPentium向けの最適化を提供しており、手でさらに最適化することは、最も決定的なコード片に対して(または娯楽のため)以外はその努力に見合わないかもしれない。
どうか私にプログラミングの質問を送らないでほしい。私はあなたの宿題をするつもりはない。
ナノ秒狩りの幸運を祈る!
PS. 私は故意に「optimization」を間違って綴っている。なぜなら、「optimation」のほうが発音に最適だからである。
文献のURLは頻繁に変わるので、ここで紹介しない。
http://www.intel.com/sites/developer/search.htmの検索機能を使うか、
http://announce.com/agner/assemからリンクをたどることで、必要な文書を見つけることができる。
いくつかの文書は.PDF形式である。.PDFファイルを見たり印刷したりするソフトウェアを持っていなければ、www.adobe.comからAcrobatファイルリーダをダウンロードすればよい。
特定のアプリケーションを最適化するためにMMX命令を使うことは、アプリケーションノートのいくつかで述べられている。MMX命令セットはいろいろなマニュアルやチュートリアルで述べられている。
インテル以外にも有用な情報源がたくさんある。これらはニュースグループcomp.lang.asm.x86のFAQにリストされている。シェアウェアのエディタASMEDITには、すべての命令コードなどをカバーするオンラインヘルプがある。ASMEDITは
http://www.inf.tu-dresden.de/~ok3/asmedit.htmlから得られる。
インタネットのリソースについては
http://announce.com/agner/assem/からリンクをたどってほしい。
高級言語で書いたサブルーチンがテストプログラムと共に動くようになったら、そのコードをアセンブリ言語に直す準備ができたことになる。インラインアセンブラを使ってもよいし、サブルーチン全体をアセンブリ言語で書いて、リンクしてもよい。後者を選んだ場合、高級言語のコードを直接アセンブリ言語に変換できるコンパイラを使うことを勧める。これであなたは確実に、関数呼び出し法を正しくできる。たいていのC++コンパイラはこれができる。(最近のバージョンのマイクロソフトvisual C++はできない。バージョン9以前のCL.EXEを使うとよい)。
関数の呼び出しの方法と名前の変換はたいそう複雑である。多数の異なる呼び出し規約があり、コンパイラのブランドが異なればこの点で互換性がない。アセンブリ言語のサブルーチンをC++から呼び出そうとしているなら、整合性と互換性の点から最もよい方法は、関数を extern "C" と _cdecl で宣言することである。アセンブリ言語のコードは、アンダースコア(_)が先頭についた関数名を持ち、外部名の大文字小文字を区別する(オプション -mx)ようにアセンブルされるはずである。引数はスタックに逆順に積まれ、最初の引数が最下位の番地に来る。引数は呼び出された関数ではなく呼び出し側がスタックから取り除く。戻り値はレジスタeaxまたはst(0)にはいる。関数は、eax,ecx,edx(16ビットモードではax,bx,cx,dx,es)を除いて、使うレジスタをすべて保存し、戻る前に復元する。もし、名前の変換や別の呼び出し規約が必要なら、アセンブリ言語のコードを正しくするために、高級言語をアセンブリ言語に変換できるコンパイラを使わなければならない。
これで最適化を始めることができる。変更をするたびにコードをテストプログラム上で走らせて、正しく動くか見るべきである。
すべてのバージョンに番号をつけて保存せよ。そうすれば、テストプログラムではつかまらなかった(間違った番地に書き込んでしまうような)エラーを見つけた場合に戻ってテストし直せる。
プログラムの最も決定的な部分の速度を23章で述べる方法でテストせよ。コードが期待に比べてはっきり遅ければ、最もありそうな理由は、キャッシュミス(6章)、オペランドのミスアラインメント(5章)、最初の実行のペナルティー(9章)、分岐予測ミス(12章)である。
アラインメント アラインメント オペランドサイズ PPlainとPMMX PProとPII -------------------------------------------------- 1 (byte) 1 1 2 (word) 番地 MOD 4 < 3 2 4 (dword) 4 4 6 (fword) 4 8 8 (qword) 8 8 10 (tbyte) 8 16 --------------------------------------------------ミスアラインされたデータのアクセスは最低3クロックサイクル余計にかかる。キャッシュラインの境界をまたぐと、ペナルティーはさらに高くなる。
PPlainとPMMXで走らせるときにはコードをアラインする必要はないが、PProとPIIで最適な性能を得るために、サブルーチンやループの入口を16でアラインしてもよい。
データキャッシュはそれぞれ32バイトのライン256個または512個から成る。キャッシュされていないデータ項目を読むたびに、プロセッサはキャッシュライン全体をメモリから読む。キャッシュラインは常に32で割り切れる物理番地にアラインされている。32で割り切れる番地から1バイト読んでしまえば、続く31バイトはほとんど追加コストなしで読み書きできる。互いに近く使われるデータ項目を32バイトのアラインされたメモリブロックにまとめることで、この利点を活用できる。もし、例えば二つの配列をアクセスするループがあるなら、二つの配列をインターリーブして一つの配列にすればよい。そうすると、いっしょに使われるデータをいっしょに格納できる。
もし配列や他のデータ構造のサイズが32バイトの倍数なら、なるべく32でアラインするべきである。
キャッシュはset-associativeである。その意味は、キャッシュラインには、任意のメモリ番地を割り当てられるわけではないということである。各キャッシュラインには7ビットのセット値があって、物理RAM番地のビット5から11とマッチする(ビット0〜4はキャッシュラインの32バイトを定義する)。PPlainとPProは、128セット値のそれぞれについて二つのキャッシュラインを持つため、どんなRAM番地も割り当てられる可能性のあるキャッシュラインは二つである。PMMXとPIIは四つある。
この結果、キャッシュは、番地のビット5〜11の値が同じなら、たかだか二つまたは四つの異なるデータブロックしか保持できない。二つの番地が同じセット値を持つかどうかは次の方法で決められる。各番地の下5ビットを0にし、32で割り切れる値を得よ。二つの切り捨てた番地の差が4096(=1000H)の倍数なら、二つの番地は同じセット値を持つ。
このことを次のコード片を使って例示しよう。ここでESIは32で割り切れる番地を保持しているとする。
AGAIN: MOV EAX, [ESI]
MOV EBX, [ESI + 13*4096 + 4]
MOV ECX, [ESI + 20*4096 + 28]
DEC EDX
JNZ AGAIN
ここで使われている三つの番地は、切り捨てた番地の差が4096の倍数なので、同じセット値を持つ。このループはPPlainとPProではたいへん悲惨なふるまいをする。ECXを読むとき、適当なセット値を持つ空きキャッシュラインがないので、プロセッサは二つのキャッシュラインのうち最近使われてないほう(EAXのために使われたもの)を採用し、そのキャッシュラインを [ESI + 20*4096] から [ESI + 20*4096 + 31] までのデータで満たしてECXを読む。次に、EAXを読むとき、EAXのための値を保持していたキャッシュラインは今は破棄されていることに気づく。それで、最も近くに使われたのでないキャッシュラインを採用し、それはEBXの値を保持しているものである。以下同様である。これではキャッシュミスしか起きず、ループは60クロックサイクルとかかかる。もし第3行を変更して
MOV ECX, [ESI + 20*4096 + 32]とすれば、32バイト境界を越えたので、最初の2行と同じセット値ではなくなり、3つの番地のそれぞれに問題なくキャッシュラインを割り当てられる。ループは今は3クロックサイクルしかかからない(初回を除いて)。たいへん考慮に値する改良である!
データの番地が同じキャッシュ値かどうか決めるのは、特に異なるセグメントに散らばっているときは、たいへん難しいかもしれない。この種の問題を避ける最もよい方法は、プログラムの決定的に重要な部分で使われるすべてのデータをキャッシュより大きくない一つの連続したブロックか、キャッシュのサイズの半分以下の二つのブロック(例えば静的データで一つのブロック、スタック上のデータで一つのブロック)に入れることである。これでキャッシュラインはきっと最適に使われるようになるだろう。
コードの決定的に重要な部分が大きなデータ構造やランダムなデータ番地をアクセスするなら、すべてのよく使う変数(カウンタ、ポインタ、制御変数など)を一つの連続した4kバイト以下のブロックに入れて、ランダムなデータをアクセスするための、キャッシュラインの完全なセットがあるようにしたいかもしれない。たぶんサブルーチンの引数や戻り番地のためのスタックスペースは結局必要なので、最もよいのは、よく使う静的データをスタック上の動的変数にコピーし、変更があったものは決定的に重要なループの外でコピーし戻すことである。
レベル1キャッシュにないデータ項目を読むことは、キャッシュライン全体をレベル2キャッシュから満たすことになる。これはだいたい200ns(つまり100MHzシステムでは20クロック、200MHzシステムでは40クロック)かかるが、最初に読みたかったバイトは50〜100nsで利用可能になる。データ項目がレベル2キャッシュにもない場合、200〜300nsの遅れが生ずる。DRAMのページ境界をまたぐと、この遅れは多少長くなる(DRAMのページサイズは、4MBの72ピンRAMモジュールで1KB、16MBモジュールで2KBである)。
レベル1キャッシュにない番地に書いたときには、PPlainとPMMXでは、その値はそのままレベル2キャッシュかRAMに行く(レベル2キャッシュがどう設定されているかによる)。これはだいたい100nsかかる。もし8回かそれ以上同じ32バイトメモリブロックに書き、そこから読むことがなく、ブロックがレベル1キャッシュにないならば、そのブロックから最初にダミーの読み込みをしてキャッシュラインにロードするほうが有利かもしれない。同じブロックへの引き続く書き込みはすべて、キャッシュに行き、それは1クロックサイクルしかかからない。これは、書き込みミスで常にキャッシュラインをロードする、PProやPIIでは必要ない。PPlainとPMMXでは、同じ番地に繰り返し書き、その間に読まないと、ときどき小さなペナルティーがある。
書き込みミスを減らす別の方法は、整数のレジスタを使って4バイトを一度に書く代わりに、QWORDオペランドのFILD / FISTPを使って8バイトを一度に書くことである。遅いFILDとFISTP命令の余分なコストは書き込みが半分ですむことで補償される。しかし、この方法が有利なのはPPlainとPMMXだけであり、しかも転送先がレベル1キャッシュにない場合に限る。この方法は19章で説明する。PProまたはPIIを持っているなら、8バイトを一度に移動するには、もちろん浮動小数点命令ではなくMMX命令を使えばよい。
PPlainは二つの書き込みバッファを持っており、PMMXは四つ、PProとPIIは八つである。PMMXでは、キャッシュされていないメモリに対して最大四つまでの未完了の書き込みがあっても、引き続く命令を遅らせることはない。
スタック領域はキャッシュにあることがたいへん多いので、一時データはスタックに格納すると便利である。しかしながらDWORDサイズのスタックにQWORDデータを格納したり、WORDサイズのスタックにDWORDデータを格納する場合は、アラインメントの問題の可能性があることを認識するべきである。
もし二つのデータ構造の寿命の範囲が重ならない場合、キャッシュの効率を上げるために同じRAM領域を使うかもしれない。これは一時変数をスタックに割り付けるという日常習慣と整合性がある。
一時データをレジスタに格納することはもちろんもっと効率的である。レジスタは希少なリソースなので、スタックのデータをアクセスするのに[EBP]ではなく[ESP]を使い、EBPを他の目的のために空けたいかもしれない。ESPの値はPUSHやPOPをするたびに変化することを忘れないでほしい(16ビットWindowsでは、ESPを使うことはできない。タイマ割り込みがコード中の予測できない場所でESPの上位ワードを変更する)。
コード用には別のキャッシュがあり、それはデータキャッシュと似ている。コードキャッシュのサイズは、PPlainとPProで8KB、PMMXとPIIで16KBである。コードの決定的に重要な部分(最も内側のループ)がキャッシュに収まることは重要である。よく使われるコード片やいっしょに使われるルーチンはなるべく互いに近くに格納するべきである。めったに使われない分岐や手続きはコードの下のほうかどこか別の場所に離しておくべきである。
例: ADD EBX,4 / MOV EAX,[EBX] ; AGIストールこの例のストールは ADD EBX,4 と MOV EAX,[EBX] の間に何か他の命令をはさむか、コードを次のように書き換えることで取り除ける。
MOV EAX,[EBX+4] / ADD EBX,4
ESPを暗黙に番地指定に使う、PUSH、POP、CALL、RETのような命令でも、MOV、ADD、SUBのような命令で先立つクロックサイクル中にESPが変更された場合は、AGIストールが発生する。PPlainとPMMXはスタック操作の後のESPの値を予想する特別な回路を持つため、PUSH、POP、CALLでESPを変更した後のAGIによる遅れはない。RETの後のAGIストールは、ESPに足す即値を持つ場合に限ってある。
例: ADD ESP,4 / POP ESI ; AGIストール POP EAX / POP ESI ; ストールなし、ペア MOV ESP,EBP / RET ; AGIストール CALL L1 / L1: MOV EAX,[ESP+8] ; ストールなし RET / POP EAX ; ストールなし RET 8 / POP EAX ; AGIストール
LEA命令も、先立つクロックサイクルで変更された、ベースまたはインデックスレジスタを使う場合、AGIストールを受ける。
例: INC ESI / LEA EAX,[EBX+4*ESI] ; AGIストール
PProとPIIには、AGIストールはない。
MOV レジスタ、メモリ、または即値を、レジスタ、またはメモリへ PUSH レジスタ、または即値 POP レジスタ LEA, NOP INC, DEC, ADD, SUB, CMP, AND, OR, XOR TESTのいくつかの形式(段落17.3を参照)次の命令はUパイプでのみペアにできる。
ADC, SBB SHR, SAR, SHL, SAL 回数は即値 ROR, ROL, RCR, RCL 回数は即値の1次の命令はどちらのパイプでも実行できるが、ペアにできるのはVパイプの時だけである。
near call, shortまたはnearジャンプ, shortまたはnear条件ジャンプ他のすべての整数命令はUパイプでのみ実行可能であり、ペアにできない。
連続する二つの命令は次の条件が満たされたときペアにできる。
例:
MOV EAX, EBX / MOV ECX, EAX ; 書き込み後読み込み、ペアにできない
MOV EAX, 1 / MOV EAX, 2 ; 書き込み後書き込み、ペアにできない
MOV EBX, EAX / MOV EAX, 2 ; 読み込み後書き込み、ペアOK
MOV EBX, EAX / MOV ECX, EAX ; 読み込み後読み込み、ペアOK
MOV EBX, EAX / INC EAX ; 読み込み後読み書き、ペアOK
例:
MOV AL, BL / MOV AH, 0 ; 同じレジスタの異なる部分への書き込み
; ペアにできない
例:
SHR EAX,4 / INC EBX ; ペアOK
例:
CMP EAX, 2 / JA LabelBigger ; ペアOK
PUSH + PUSH, PUSH + CALL, POP + POP
PPlainでは、プリフィックスつき命令は、near条件ジャンプを除いてUパイプでのみ実行可能である。
PMMXでは、オペランドサイズ、アドレスサイズ、0FHのプリフィックスつき命令は、どちらのパイプでも実行可能であるが、一方、セグメント、リピート、ロックプリフィックスつき命令はUパイプでしか実行できない。
MOV DWORD PTR DS:[1000], 0 ; ペアにできないかUパイプのみ
CMP BYTE PTR [EBX+8], 1 ; ペアにできないかUパイプのみ
CMP BYTE PTR [EBX], 1 ; ペアにできる
CMP BYTE PTR [EBX+8], AL ; ペアにできる
(PMMXにおける、変位と即値の両方を持つ命令の別の問題は、そのような命令は7バイトより長くなるかもしれないことで、それは、13章で説明するように、1クロックサイクルで1命令しかデコードできないことを意味する。)
この四つの理由のため、ループ中のコード片が最初に実行されるときには、次回以降より一般にずっと時間がかかる。
コードキャッシュに収まらないようなループがあると、キャッシュから実行されることはないので、9.1と9.2のペナルティーを毎回に受けることになる。だから、ループを再構成してキャッシュに収まるように務めるべきである。
ループ中にジャンプやブランチが多い場合、9.3のペナルティーを毎回に受けるかもしれない。
同様に、データキャッシュに取って大きすぎるデータをループが繰り返しアクセスする場合、毎回キャッシュミスのペナルティーを受ける。
不完全なペアリングは次のような場合に起きる。
MOV AL, [ESI] / MOV BL, [ESI+1]二つのオペランドは同じDWORD内にあるので、同時には実行できない。このペアは2クロックサイクルかかる。
MOV AL, [ESI+3] / MOV BL, [ESI+4]ここでは二つのオペランドはDWORD境界の両側にあるので、完全にペアになれ、1クロックサイクルしかかからない。
例:
MOV [ESI], EAX / MOV [ESI+32000], EBX ; 不完全なペアリング
MOV [ESI], EAX / MOV [ESI+32004], EBX ; 完全なペアリング
ペアにできる整数命令で、メモリにアクセスしないものは、予測ミスしたジャンプを除いて、実行に1クロックサイクルかかる。メモリから、またはメモリへのMOV命令は、データ領域がキャッシュにあって適当にアラインされていれば、やはり1クロックサイクルしかかからない。スケールされたインデックスレジスタのような複雑な番地指定モードの使用に速度のペナルティーはない。
ペアにできる整数命令で、メモリから読み、何らかの計算をし、結果をレジスタやフラグに格納するものは、2クロックサイクルかかる。
ペアにできる整数命令で、メモリから読み、何らかの計算をし、結果をメモリに書き戻すものは、3クロックサイクルかかる(read/modify/write命令)。
消費するクロックサイクル数は次の表のようになる。
| 二番目の命令
| MOV or read/ read/modify/
最初の命令 | register only modify write
----------------------|----------------------------------------------
MOV or register only | 1 2 3
read/modify | 2 2 3
read/modify/write | 3 4 5
----------------------|-----------------------------------------------
例: ADD [mem1], EAX / ADD EBX, [mem2] ; 4クロックサイクル ADD EBX, [mem2] / ADD [mem1], EAX ; 3クロックサイクル
不完全なペアリングを避けるためには、どの命令がUパイプに、どの命令がVパイプに行くかを知らなければならない。これは、次のようにすればわかる。コードを逆方向に見て行って、ペアにできない、一方のパイプでしかペアにできない、または8章の規則のどれかのためにペアにできない命令をさがせばよい。
不完全なペアリングはたいてい、命令の順序を変更することで避けられる。
例:
L1: MOV EAX,[ESI]
MOV EBX,[ESI]
INC ECX
ここで二つのMOV命令は同じメモリ位置をアクセスするので、不完全なペアを形成する。この命令列は3クロックサイクルかかる。命令の順番を変えて、 INC ECX がMOV命令のどちらかとペアになるようにすれば、改良できる。
L2: MOV EAX,OFFSET A
XOR EBX,EBX
INC EBX
MOV ECX,[EAX]
JMP L1
ペア INC EBX / MOV ECX,[EAX] は、後者の命令にAGIストールがあるため、不完全である。この命令列は4クロックかかる。NOPまたは他の命令を挿入して、 MOV ECX,[EAX] が代わりに JMP L1 とペアになるようにすれば、命令列は3クロックしかかからない。
次の例は16ビットモードで、SPが4で割り切れると仮定する。
L3: PUSH AX
PUSH BX
PUSH CX
PUSH DX
CALL FUNC
ここでPUSH命令は二つの不完全なペアを形成する。なぜなら、各ペアの両方のオペランドがメモリの同じDWORDに行くからである。 PUSH BX は PUSH CX と完全なペアになれたかもしれない(DWORD境界の両側に行くから)のに、すでに PUSH AX とペアになってしまっているので、そうはならない。命令列は、従って、5クロックサイクルかかる。もしNOPか他の命令を挿入して、 PUSH BX が PUSH CX と、 PUSH DX が CALL FUNC とペアになるようにすれば、命令列は3クロックしかかからない。問題を解決する別の方法は、SPが必ず4で割り切れないようにすることである。16ビットモードでSPが4で割り切れるかどうか知るのは困難なので、この問題を避ける最もよい方法は、32ビットモードを使うことである。
例: ADD [mem1],EAX / ADD [mem2],EBX ; 5クロックサイクルこのコードは3クロックサイクルしかかからない命令列に分割できる。
MOV ECX,[mem1] / MOV EDX,[mem2] ADD ECX,EAX / ADD EDX,EBX MOV [mem1],ECX / MOV [mem2],EDX
同様に、ペアにできない命令を、ペアにできる命令に分割してもよい。
PUSH [mem1] / PUSH [mem2] ; ペアにできないこれを分割して
MOV EAX,[mem1] / MOV EBX,[mem2] / PUSH EAX / PUSH EBX ; すべてペアになる
ペアにできない命令で、より単純なペアにできる命令に分割できる、他の例:
CDQ を分割して MOV EDX,EAX / SAR EDX,31 NOT EAX の代わりに XOR EAX,-1 NEG EAX を分割して XOR EAX,-1 / INC EAX MOVZX EAX,BYTE PTR [mem] を分割して XOR EAX,EAX / MOV AL,BYTE PTR [mem] JECXZ を分割して TEST ECX,ECX / JZ LOOP を分割して DEC ECX / JNZ XLAT の代わりに MOV AL,[EBX+EAX]
もし命令を分割することで速度が改良されなければ、コードサイズを縮小するために、複雑な、またはペアにできない命令をそのままにしてもよい。命令の分割は、PProとPIIでは必要ない。
予測は、各分岐またはジャンプ命令の履歴を格納して、各命令の以前の実行履歴から予測を行う、 Branch Target Buffer (BTB)に基づいて行われる。BTBは、新しいエントリが擬似ランダム置換方式で割り当てられるようなset-associativeキャッシュと似た構成になっている。
コードを最適化するとき、予測ミスのペナルティーの数を最小にすることが重要である。これには、分岐予測がどのように働くかよく理解することが要求される。
分岐予測機構についてはインテルのマニュアルにも、また他のどこでも正確には書かれていない。だから私は、たいへん詳細な記述をここで与える。この情報は私自身の調査に基づいている(PPlainでは Karki Jitendra Bahadur の助けもあった)。
以下で私は、「制御移行命令」という言葉を、IP(instruction pointer)を変更するどんな命令についても、条件つき、無条件、直接、間接、near、far、ジャンプ、コール、リターンを含めて、使うことにする。これらすべての命令が予測を使う。
PPlainは branch target buffer (BTB)を持ち、それは256個までのジャンプ命令の情報を保存できる。BTBはウェイあたり64エントリの4ウェイset-associativeキャッシュと似た構成になっている。これの意味するところは、BTBは同じセット値を持つエントリをたった4つしか保持できないということである。データキャッシュと違って、BTBは擬似ランダム置換アルゴリズムを使っており、最近使われてないほうの、同じセット値のエントリを置き換えるわけでは必ずしもない。セット値がどのように計算されるかは後で述べる。各BTBエントリはジャンプ先の番地と、4つの異なる値をとる予測の状態を格納する。
状態0: 強 分岐しない 状態1: 弱 分岐しない 状態2: 弱 分岐する 状態3: 強 分岐する分岐命令は状態2と3ではジャンプすると、0と1では通り抜けると予測される。状態遷移は2ビットカウンタのように働き、分岐すると状態は1増え、通り抜けると1減る。カウンタはラップアラウンドせず飽和するので、0を超えて減ったり、3を超えて増えたりしない。理想的には、これはまずまずよい予測になるだろう。なぜなら、予測が変化する前に分岐命令は、よくする動作から2回はずれなければならないからである。
しかし、状態0が「使われていないBTBエントリ」も意味するという事実により、この機構には妥協がある。だから、状態0のBTBエントリは、BTBエントリがないのと同じである。分岐命令はBTBエントリを持たない場合通り抜けると予測されるので、これは筋が通っている。ほとんど分岐しない分岐命令はほとんどの時間、BTBエントリの場所を取らないので、これはBTBの使用効率を改良する。
ここで、もしジャンプする命令がBTBエントリを持たなければ、新しいBTBエントリが生成され、これはいつでも状態3にセットされる。これは、状態0から状態1に行くのは不可能であることを意味する(後に議論する非常に特別な場合を除く)。状態0からは、分岐した場合は状態3にしか行けない。分岐が通り抜けた場合、BTBにはいらないままになる。
これは深刻な、設計の欠陥である。状態0のエントリを捨て、新しいエントリをいつでも状態3にセットすることで設計者は、無条件ジャンプやよく分岐する条件ジャンプの初回のペナルティーを少なくすることを優先し、これが機構の背後にある基本アイデアに対して重大な妥協をしていて、最も内側の小さいループの性能を落としていることを無視したようだ。この欠陥の帰結は、たいてい通り抜ける分岐命令は、たいてい分岐する分岐命令の3倍も予測ミスがあるということである。
この非対称性を考慮に入れて、分岐命令は分岐するほうが多くなるように構成するとよい。
例えばこのif-then-else構造を考えてみよう。
TEST EAX,EAX
JZ A
<枝1>
JMP E
A: <枝2>
E:
もし枝1が枝2より多く実行され、枝2が続けて2回実行されることがめったになければ、二つの枝を交換して、分岐命令が通り抜けるよりジャンプするほうが多いようにすることで、分岐予測ミスを3分の1にまで減らすことができる。
TEST EAX,EAX
JNZ A
<枝2>
JMP E
A: <枝1>
E:
(これは、インテルのマニュアルやチュートリにある勧めとは逆である。分岐予測の非対称性に気づいていないようである。しかし、後者の例が優れていることを示すのはたやすい。)
だが、最もよく実行される枝を最初に置く理由もあるかもしれない。
これらの考慮は、しかしながら、小さく決定的に重要なループに関してはウェイトは小さいので、やはり、分布の偏った枝の構成は、分岐命令が分岐するほうが多いようにすることを勧める。ただし、枝2の実行頻度があまりに小さくて、予測ミスが問題にならないときを除く。
同様に、ループの条件テストの分岐命令は、この例のように、なるべく最後に来るように構成するべきである。
MOV ECX, [N]
L: MOV [EDI],EAX
ADD EDI,4
DEC ECX
JNZ L
もしNが大きければ、JNZ命令は分岐するほうが多く、続けて2回通り抜けることはない。
1回おきに分岐が起きる状況を考えてみよう。最初にジャンプしたとき、BTBエントリは状態3に行き、その後状態2と3に交互に行くだろう。これはいつもジャンプすると予測され、50%の予測ミスとなる。今これがこの規則的なパターンからはずれ、1回余計に通り抜けたとしよう。ジャンプのパターンは、0がとばない、1がとぶの意味だとして、
01010100101010101010101
^
増えた通り抜けは^で示してある。このできごとの後では、BTBエントリは状態1と2に交互に行き、100%の予測ミスとなる。この不運なモードはまた0101パターンからはずれるまで続く。これがこの分岐予測機構で最も悪い場合である。
例:
SHR EAX,1
MOV EBX,[ESI]
CMP EAX,EBX
JB L
ここで、SHRはMOVと、CMPはJBとペアになる。従って、 JB L についてのBTBエントリは、 SHR EAX,1 命令の番地につく。このBTBエントリに出会ったとき、それが状態2か3なら、PentiumはBTBエントリから分岐先の番地を読み、ラベルL以降の命令をパイプラインにロードする。これは分岐命令がデコードされる前に起きるので、PentiumはこれをするときBTBの情報だけに頼っている。
命令は、初回に実行されるときにはめったにペアにならないことを、ここで思い出すかもしれない(段落9.2参照)。上の命令がペアにならなければ、BTBエントリはCMP命令の番地につくであろう。そして、次回の実行で命令がペアになるときには、このエントリは誤りになるだろう。しかしながら、多くの場合、PPlainは十分賢く、ペアになる機会を利用しなかったものがあるときには、BTBエントリを作らないので、2回目の実行まではBTBエントリはできず、だから、3回目の実行までは予測はされないだろう(一つおきに1バイト命令があるような、稀な場合では、2番目の実行では無効になるようなBTBエントリが最初の実行でできるかもしれないが、それならエントリのついている命令はVパイプに行くので、それは無視されてペナルティーを与えない。BTBエントリが読まれるのは、それがUパイプの命令の番地についているときだけである)。
BTBエントリは、それがつく番地のビット0〜5に等しいセット値で見分けられる。ビット6〜31はタグとしてBTBに格納される。64の倍数だけ離れた番地は同じセット値を持つ。同じセット値を持つBTBエントリは4つまでしか作れない。制御移行命令のセット値が競合するかどうかチェックしたいなら、前の命令ペアのUパイプ命令のアドレスのビット0〜5を比べなければならない。これはたいへんあきあきするし、誰かがやっていると聞いたこともない。この仕事をあなたの代わりにやってくれるような、利用可能なツールはない。
連続する制御移行命令の問題はこれだけではない。別の問題は、BTBエントリと、それが属する制御移行命令の間に、もう一つの分岐命令を置けることである。最初の分岐命令がどこか別の場所にジャンプすると、奇妙なことが起きるかもしれない。この例を考えてみよう。
SHR EAX,1
MOV EBX,[ESI]
CMP EAX,EBX
JB L1
JMP L2
L1: MOV EAX,EBX
INC EBX
JB L1 が通り抜けるとき、 CMP EAX,EBX の番地につけられた、 JMP L2 のためのBTBエントリができる。しかし、後で JB L1 が分岐したとき何が起きるだろうか。 JMP L2 のためのBTBエントリが読まれるとき、プロセッサは次の命令ペアが制御移行命令を含んでいないことを知らないので、実際には命令ペア MOV EAX,EBX / INC EBX がL2にジャンプすると予測する。ジャンプでない命令がジャンプすると予測したときのペナルティーは3クロックサイクルである。 JMP L2 のためのBTBエントリは、何かジャンプしないものに適用されたために、その状態が1減らされる。もしL1に行き続けるなら、 JMP L2 のためのBTBエントリは状態1、そして0まで減らされて、次に JMP L2 が実行されるまでこの問題は姿を消すだろう。
ジャンプでない命令をジャンプすると予測するペナルティーは、L1へのジャンプが予測されたときのみ発生する。 JB L1 が予測とはずれてジャンプする場合は、パイプラインがフラッシュされ、間違ったジャンプ先のL2はロードされないので、ジャンプでない命令をジャンプすると予測したペナルティーは見えないが、 JMP L2 のBTBエントリの状態はやはり減らされる。
今、 INC EBX 命令を別の制御移行命令で置き換えてみよう。この三番目の制御移行命令は JMP L2 命令と同じBTBエントリを使い、誤ったジャンプ先を予測するペナルティーを受ける可能性がある(たまたまジャンプ先が同じL2である場合を除いて)。
要約すると、連続するジャンプは、次のような問題につながる可能性がある。
そろそろこれを説明する例を挙げるころである。
CALL P
TEST EAX,EAX
JZ L2
L1: MOV [EDI],EBX
ADD EDI,4
DEC EAX
JNZ L1
L2: CALL P
これはなかなかよい、普通のコード片に見える。関数呼び出しと、回数が0のときは迂回されるループと、別の関数呼び出しである。あなたはこのプログラムにいくつの問題を見つけ出せるだろうか。
まず、関数Pが交互に二つの異なる場所から呼ばれることに注意しよう。これはPからの戻り先が毎回変わることを意味する。その結果、Pからのリターンはいつも予測ミスする。
今、EAXが0だと仮定しよう。すると、予測ミスしたPからのリターンはパイプラインフラッシュを起こしているので、L2へのジャンプはそのジャンプ先をロードしない。次に、 JZ L2 がパイプラインフラッシュを起こしたので、二番目の CALL P も分岐先のロードに失敗する。これが、最初のジャンプが予測ミスしたために、連続したジャンプの鎖が繰り返しパイプラインフラッシュを引き起こす状況である。 JZ L2 のためのBTBエントリはPのリターン命令の番地に格納される。このBTBエントリは二番目の CALL P の後に来るものが何であっても誤って適用されるが、予測ミスした二番目のリターンによってパイプラインがフラッシュされるので、ペナルティーを与えない。
今度は、次回、EAXが0以外の値だったら何が起きるか見てみよう。フラッシュによって JZ L2 はいつでも通り抜けると予想される。二番目の CALL P は TEST EAX,EAX の番地にBTBエントリを持つ。このエントリはMOV/ADDのペアに誤って適用され、Pにジャンプすると予測するだろう。これはフラッシュを起こし、 JNZ L1 がそのジャンプ先をロードするのを妨げる。もし以前ここに来たことがあるのなら、二番目の CALL P は DEC EAX の番地にもう一つのBTBエントリを持つ。ループの2,3回目の繰り返しにおいて、このエントリもMOV/ADDのペアに誤って適用される(状態が1か0に減らされるまで)。2回目の繰り返しでは、 JNZ L1 によるフラッシュが誤ったジャンプ先のロードを止めるので、これはペナルティーを起こさないが、3回目の繰り返しではペナルティーを起こす。引き続くループの繰り返しではペナルティーはないが、出るときに、 JNZ L1 が予測ミスする。CALL P のためのBTBエントリが、何回か誤って適用されたために、すでに破壊されているという事実がなければ、これによるフラッシュは、今度は CALL P がジャンプ先をロードするのを妨げただろう。
すべての連続するジャンプを分けるためにいくつかNOPを入れることで、このコードを改良できる。
CALL P
TEST EAX,EAX
NOP
JZ L2
L1: MOV [EDI],EBX
ADD EDI,4
DEC EAX
JNZ L1
L2: NOP
NOP
CALL P
余分なNOPは2クロックサイクルかかるが、ずっと多くを節約する。さらに、 JZ L2 はUパイプに移動し、予測ミスしたときのペナルティーが4から3に減っている。残る唯一の問題は、Pからのリターンがいつも予測ミスすることである。この問題はPの呼び出しをインラインマクロで置き換えることによってのみ解決できる(もしコードキャッシュが十分なら)。
この例から学ぶべき教訓は、いつも注意深く、連続するジャンプを探して、NOPをいくつか挿入すると時間を節約できるかどうか考えるべきであるということである。ループの出口やいろいろな場所から呼ばれる手続きからのリターンなど、予測ミスが避けられない状況を特に認識するべきである。NOPの代わりに挿入する有効なものがあるのなら、もちろんそうするべきである。
多方向分岐(case文)は、分岐命令の木か、ジャンプする番地のリストで実装されるだろう。分岐命令の木を使うことを選ぶのなら、連続する分岐を分けるためにNOPかほかの命令を含めなければならない。PPlainでは従って、ジャンプする番地のリストがよい解かもしれない。ジャンプする番地のリストはデータセグメントに置くべきである。決してデータをコードセグメントに置くな!
例:
JZ L1
MOV EAX,1
L1: MOV EBX,2
MOV ECX,3
JC L2
もし、 JZ L1 が通り抜けると、 MOV EAX,1 は MOV EBX,2 とペアになり、 MOV ECX,3 は JC L2 とペアになる。 JC L2 のためのBTBエントリは MOV EAX,1 の番地につくことになる。 JZ L1 が分岐したときには、 MOV EBX,2 は MOV ECX,3 とペアになり、 JC L2 はペアにならず、BTBエントリは MOV EBX,2 につくことになる。このように JC L2 には二つのBTBエントリができる。最初のエントリはゼロフラグが降りているとき、もう一つは立っているときに使われる。これは実は好都合かもしれない。なぜなら、二つの分岐命令に相関があるなら、二番目の分岐命令の予測可能性を向上させるからである。例えば、このコード列の前にCMP命令があると仮定しよう。すると、ゼロフラグとキャリーフラグが両方同時に立つことは決してないと確信できる。ゼロフラグが立っていると、 JC L2 は必ず通り抜けるので、 MOV EBX,2 に JC L2 のための二番目のBTBエントリはつかず、 JZ L1 が分岐したときは JC L2 の予測ミスはない。このトリックを利用できる状況は、しかしながら稀である。というのは、L1をキャリーフラグを全くテストしない別の枝に持って行ったほうがましだからである。
PProとPIIの branch target buffer は512個のエントリを持つ。これがどのようなセットで構成されているかの情報を私は持っていない。
PProとPIIはどんな制御移行命令でもそれが最初に実行されたときにBTBエントリを割り当てる。PMMXはそれが最初にジャンプしたときに割り当てる。PMMXでは、決してジャンプしない分岐命令はBTBには入らずにいる。そして一度ジャンプしたら、もう決して再びジャンプしなくても、それはBTBにとどまるのである。
エントリは、同じセット値を持つ別の制御移行命令がBTBエントリを必要としたときに、BTBから押し出されることもある。
PProとPIIでは、長いパイプラインのせいで、予測ミスのペナルティーは非常に高い。予測ミスは普通、10〜20クロックサイクルかかる。そのため、PProとPIIで走らせるときには、予測のうまくいかない分岐を意識しておくことは非常に重要である。
このメカニズムは、 T.-Y. Yeh と Y. N. Patt の発明した、いわゆる「2レベル適応型分岐予測スキーム」である。これはPPlainについて上で説明したのと同種の(ただし非対称性の欠陥はない)2ビットカウンタに基づいている。カウンタはジャンプが分岐したときは増加し、分岐しなかったときは減少する。3より上、0より下にラップアラウンドはしない。対応するカウンタが状態2か3のときは、分岐命令は分岐すると予測され、状態0か1のときは、通り抜けると予測される。今、各BTBエントリに対してこのようなカウンタを16個持つことで、劇的な改良が得られる。その分岐命令の最後の4回の実行の履歴に基づいて16個のカウンタのうちの一つが選ばれる。例えば、分岐命令が一度ジャンプし、3回通り抜けたらなら、履歴ビットとして1000(1=ジャンプした、0=ジャンプしなかった)を持つ。これはカウンタ8(1000は2進数としてみると8)を次回の予測として使い、その後カウンタ8を更新する。
もし列1000の後にくるのがいつも1なら、カウンタ8はすぐに一番上の状態(状態3)に達し、1000の後はいつも1が来るだろうと予測する。予測が変化するには、このパターンから2回はずれる必要がある。繰り返しパターン100010001000は、カウンタ8を状態3に、カウンタ1,2,4を状態0にし、他の12個のカウンタは使わない。
周期 パターン
-----------------------------------------------------------------------------
1 - 5 すべて
6 000011, 000101, 000111, 001011
7 0000101, 0000111, 0001011
8 00001011, 00001111, 00010011, 00010111, 00101101
9 000010011, 000010111, 000100111, 000101101
10 0000100111, 0000101101, 0000101111, 0000110111, 0001010011,
0001011101
11 00001001111, 00001010011, 00001011101, 00010100111
12 000010100111, 000010111101, 000011010111, 000100110111,
000100111011
13 0000100110111, 0000100111011, 0000101001111
14 00001001101111, 00001001111011, 00010011010111, 00010011101011
00010110011101, 00010110100111
15 000010011010111, 000010011101011, 000010100110111, 000010100111011
000010110011101, 000010110100111, 000010111010011, 000011010010111
16 0000100110101111, 0000100111101011, 0000101100111101,
0000101101001111
-----------------------------------------------------------------------------
この表を読むとき、次のことを知っているべきである。あるパターンが正しく予測できるなら、同じパターンを反転したもの(後ろ向きに読んだもの)も、また、同じパターンの全ビットを反転したものも正しく予測できる。
例: 表にはこのパターンがある: 0001011 パターンを反転すると: 1101000 全ビットを反転すると: 1110100 両方同時にやると: 0010111これら四つのパターンはすべて認識できる。パターンを一つ左に回転すると、0010110になる。これはもちろん新しいパターンではなく、同じパターンの相がずれたものである。表の中のあるパターンから反転したり、ビット反転したり、回転したりして導出できるパターンもすべて認識できる。簡潔にするために、これらはリストされていない。(リストはPMMXで実験的に得られた)。
BTBエントリが割り当てられた後、パターン認識機構が規則的な繰り返しパターンを学習するのに2周期かかる。学習期間での予測ミスのパターンには再現性がない。これはたぶん、BTBエントリには割り当てに先立って何かが入っているからだろう。BTBエントリはランダムに割り当てられるので、最初の学習期間の間に何が起きているか予測できる可能性はほとんどない。
例:
0001110001110001110001011100011100011100010111000
^ ^
この列で0はジャンプしない、1はジャンプすることを表す。分岐予測機構は繰り返される列が000111であることを学習する。最初の不規則性は、^でしるしをつけた、予期できない0である。0010,0101,1011の後に何が来るかはまだ学習していないので、この0の後の3つのジャンプは予測ミスする可能性がある。同じ種類の不規則性1回か2回の後では、分岐予測機構は0010の後に1、0101の後に1、1011の後に1が来ることを学習してしまう。その意味は、同じ種類の不規則性高々2回で、この種の不規則性を予測ミス1回だけで扱えるように学習してしまうということである。
二つの異なる規則的なパターンが交互に起きるときも、予測機構はたいへん有効である。例えば、000111というパターン(周期6)が何度も繰り返され、次にパターン01(周期2)が何度も、そして000111のパターンにもどるとすると、分岐予測機構は000111のパターンを再学習する必要はない。なぜなら、000111の列で使われるカウンタは、01の列ではいじらないからである。二つのパターンが2〜3回交替した後では、パターンの切り替え毎にたった1回だけの予測ミスで、パターンの変化も扱えるように学習してしまう。
000001000001000001
^^ ^^ ^^
ab ab ab
である。列0000の後には交互に、aの場所では0が、bの場所では1がくる。これはカウンタ0に影響し、毎回状態が上下する。もしカウンタ0がたまたま状態0で始まったら、状態0と1を交互に繰り返す。これは場所bで予測ミスすることになる。もしカウンタ0がたまたま3で始まったら、状態2と3を交互に繰り返し、場所aで予測ミスを起こす。最も悪い場合は状態2で始まったときである。カウンタ0は状態1と2を交互に繰り返し、場所aとbの両方で予測ミスが起きるという不運な成り行きとなる。(これは12.1.1節の終わりで説明したPPlainの最悪の場合と同類である)。この四つの状況のどれになるかは、この分岐へ割り当てる前の、BTBエントリの履歴による。ランダム割り当て法のため、これは制御できない。
原理的には、カウンタを望みの状態に持っていくように特別に設計された初期分岐列を与えることで、1周期で2回の予測ミスが起きる最悪の状況を避けることは可能である。しかしながら、そのようなアプローチは勧められない。なぜなら、コードをだいぶ余計に複雑にするひつようがあるし、カウンタに込めた情報は何であれ、タイマ割り込みやタスクスイッチの間に失われてしまいがちだからである。
ジャンプする/しない 予測ミスの割合 --------------------------------------- 0.001/0.999 0.001001 0.01/0.99 0.0101 0.05/0.95 0.0525 0.10/0.90 0.110 0.15/0.85 0.171 0.20/0.80 0.235 0.25/0.75 0.300 0.30/0.70 0.362 0.35/0.65 0.418 0.40/0.60 0.462 0.45/0.55 0.490 0.50/0.50 0.500 ---------------------------------------
プロセッサは、規則性の全然ない列の中で繰り返しパターンを見つけようとし続けるので、予測ミスの割合は、パターン認識なしでなるであろう割合より少し高い。
PMMXでループが「きつい」ふるまいをするかどうか知るためには、次のようなおおざっぱなやり方に従うとよい: ループ中の命令数を数えよ。もしそれが6以下なら、ループはきついふるまいをする。7命令より多ければ、パターン認識は普通に働くと、かなり確信してよい。不思議なことに、各命令が何クロックサイクルかかるか、ストールがあるか、ペアになるかどうかは関係ない。複雑な整数命令も変わりない。複雑な整数命令をたくさん含んでいて、きついふるまいをするループもあり得る。複雑な整数命令とは、ペアにできない整数命令でいつでも2クロックサイクル以上かかるもののことである。複雑な浮動小数点命令やMMX命令もまた1と数える。このおおざっぱな方法は発見的なもので、完全に信頼できるものではないことに気をつけてほしい。重要な場合には、自分でテストしたいかもしれない。PMMXでは、分岐予測ミスを数えるのに性能モニタカウンタの35H(PProとPIIでは0C5H)が使える。分岐予測は、割り当てに先立つBTBエントリの履歴に依存するかもしれないので、テストの結果は完全に決定的ではないかもしれない。
PProとPIIのきついループについては、正確な実験的情報を持っていない。
この機構が確かに正しく働くようにするために、すべてのコールとリターンが対応しているようにしなければならない。速度が決定的なところでは、リターンを実行しないでサブルーチンから飛び出したり、リターンを間接ジャンプとして使ったりは決してしてはいけない。
PMMXでは、RSBは四つのエントリしか保持できない。RSBが空のときには、リターン命令は間接ジャンプと同じように、つまり、前回と同じジャンプ先に行くと予測される。サブルーチンが4段より深くネストするときは、最も内側の4段がRSBを使い、それより外側からのリターンでは、新しいコールがない限り、単純な予測機構を使う。RSBを使っているリターン命令もBTBエントリを専有する。
RSBの四つのエントリは多くないと思うかもしれないが、おそらく十分である。4段より深いサブルーチンのネスティングはたしかに珍しくはないが、速度については、最も深い部分だけが問題になる。
PProとPIIのRSBの大きさについての情報は持っていない。
いつでも通り抜ける分岐命令はBTBエントリを持たない。いったん分岐すると直ちに、それはBTBに入り、何度通り抜けてもそこにとどまる。制御移行命令がBTBから出られるのは、他の制御移行命令にBTBエントリを盗られて押し出されたときだけである。
その直後の番地にジャンプするような制御移行命令は、BTBエントリを得ない。
例:
JMP SHORT LL
LL:
この命令はBTBエントリを得ることは決してなく、そのためいつでも予測ミスのペナルティーがある。???
制御移行命令のBTBエントリは、命令の最後のバイトの番地のビット2〜31で同定される。二つの制御移行命令が接近し過ぎて番地のビット0〜1しか違わないと、BTBエントリを共有する問題が起きる。
例:
CALL P
JNC SHORT L
もし、CALL命令の最後のバイトとJNC命令の最後のバイトがメモリの同じDWORDにはいっていると、ペナルティーがある。アセンブラの出力リストを見て、二つの番地がDWORD境界で分離されているかどうかを見なければならない。(DWORD境界とは、4で割り切れる番地のことである)。
この問題を解決するには、いろいろな方法がある。
CALL P
MOV EAX,EAX ; 安全にするための、2バイトの詰め物
JNC SHORT L
もしPPlainでも問題を回避したいなら、代わりにNOPを二つ入れてペアリングを防ぐようにせよ(12.1.3節参照)。
RET命令はわずか1バイト長なので、この問題が特に起きやすい。
JNZ NEXT
RET
ここでは最大3バイトの詰め物が必要である。
JNZ NEXT
NOP
MOV EAX,EAX
RET
FUNC1 PROC NEAR
NOP ; コールの後のコールを避ける
NOP
CALL FUNC2
CALL FUNC3
NOP ; リターンの後のリターンを避ける
RET
FUNC1 ENDP
一つのNOPではCALLとペアになってしまうので、 CALL FUNC2 の前には二つのNOPが必要である。RETはペアになれないので、RETの前は一つのNOPで十分である。リターンの後のCALLにはペナルティーがないので、二つのCALL命令の間にNOPは必要ない。(PPlainではここにも二つのNOPが必要である)。
コールの連鎖のペナルティーは、同じサブルーチンが二つ以上の場所から呼ばれるときだけ起きる(おそらくRSBの更新が必要なため)。リターンの連鎖はいつでもペナルティーがある。コールの後のジャンプには時々小さなストールがあるが、コールの後のリターン、リターンの後のコール、ジャンプの後のジャンプとコールとリターン、リターンの後のジャンプには、ペナルティーはない。
コードを再構成して、完全には予測できない分岐パターンを完全に予測できる別のパターンで置き換えたいと思うかもしれない。例えば、いつでも20回実行されるループを考えてみよう。ループの末尾の条件ジャンプは19回分岐し、20回目には毎回通り抜ける。このパターンは規則的であるが、パターン認識機構では認識できない。これを4回と5回のネストしたループにするか、ループを4回伸ばして5回実行するかして、認識できるパターンだけにすることができる。この種の複雑なスキームは、PProとPIIのような予測ミスが非常に高価なプロセッサでだけ余計なコストに見合う価値がある。これより大きいループ回数では、たった一つの予測ミスについて何かする理由は何もない。
CWD
XOR EAX,EDX
SUB EAX,EDX
(PPlainとPMMXでは、CWDの代わりに MOV EDX,EAX / SAR EDX,31 を使う)。
キャリーフラグはこの種のトリックには特に役に立つ。
値が0ならキャリーを立てる: CMP [value],1 値が0でなければキャリーを立てる: XOR EAX,EAX / CMP EAX,[value] キャリーならカウンタを増やす: ADC EAX,0 キャリーが立つたびにビットをセットする: RCL EAX,1 キャリーが立っているならビットマスクを生成する: SBB EAX,EAX 任意の条件でビットをセットする: SETcond AL 任意の条件で8ビットをセットする: SETNcond AL / DEC AL (最後の例では、条件を反転するのを忘れないように)
この例は、二つの符号なし数の小さいほうを見つける: if (b < a) a = b;
SUB EBX,EAX
SBB ECX,ECX
AND ECX,EBX
ADD EAX,ECX
この例は二つの数の一つを選ぶ: if (a != 0) a = b; else a = c;
CMP EAX,1
SBB EAX,EAX
XOR ECX,EBX
AND EAX,ECX
XOR EAX,EBX
このようなトリックが余分なコードに見合うかどうかは、条件ジャンプがどれだけ予測できるか、分岐のないコードで増えたペアリングの機会を利用できるかどうか、そして、連続するジャンプのペナルティーを受けるようなジャンプが直後にあるかどうかによる。
PProとPIIプロセッサは、特に分岐を避けることを意図した、条件つきMOV命令を持っている。これらのプロセッサでだけ走るようなコードでは、予測のうまくいかない分岐は可能ならすべて条件つきMOVで置き換えるべきである。
PPlainでは、near条件ジャンプの0Fhプリフィックスを除いて、デコードの遅れは各プリフィックスあたり1クロックサイクルである。
PMMXでは、0Fhプリフィックスについてのデコードの遅れはない。セグメントとリピートプリフィックスはデコードに1クロック余計にかかる。アドレスとオペランドサイズプリフィックスはデコードに2クロック余計にかかる。最初の命令がセグメントかリピートプリフィックスを持っているか、プリフィックスを持たず、二番目の命令がプリフィックスを持たないなら、PMMXはクロックサイクルあたり2命令デコードできる。アドレスまたはオペランドプリフィックスを持つ命令は、PMMXでは単独でしかデコードできない。二つ以上のプリフィックスを持つ命令は各プリフィックスについて1クロック余計にかかる。
アドレスサイズプリフィックスは32ビットモードを使うことで避けられる。セグメントプリフィックスは、32ビットモードでは、フラットメモリモデルを使うことで避けられる。オペランドサイズプリフィックスは、32ビットモードでは、8ビットと32ビットの整数だけを使うことで避けられる。
プリフィックスが避けられない場所では、先行する命令が実行に2クロック以上かかるなら、デコードの遅れはマスクされるかもしれない。PPlainのための規則は次の通りである。実行(デコードではない)にNクロックサイクルかかる任意の命令は、次の二つ(ときには三つ)の命令または命令ペアのN-1個のプリフィックスのデコードの遅れに「影を落とす」ことができる。言い換えれば、命令の実行にかかる余分なクロックは、それぞれ後の命令のプリフィックス一つをデコードするのに使えるということである。この影落とし効果は予測できた分岐をも越えて拡張される。2クロックサイクル以上かかる命令、AGIストール、キャッシュミス、ミスアラインメント、そのほか、デコードの遅れや分岐予測ミスを除くどんな理由によってでも遅れる命令は何でも、影落とし効果を持つ。
PMMXは、同様の影落とし効果をもつが、その機構は異なる。デコードされた命令は透過な first-in-first-out (FIFO) バッファに格納され、バッファは4つまでの命令を保持できる。FIFOバッファに命令がある限り、遅れはない。バッファが空のときは、命令はデコードされるとすぐに実行される。命令が実行されるよりデコードされるのが速いとき、つまり、ペアにならない、または複数サイクルの命令があるときに、バッファは満たされる。命令がデコードされるより実行されるのが速いとき、つまり、プリフィックスによるデコードの遅れがあるとき、FIFOバッファは空になる。予測ミスした分岐の後は、FIFOバッファは空である。二番目の命令はプリフィックスなしで、どちらの命令も7バイトより長くないという前提で、FIFOバッファはクロックサイクルあたり2命令を受け取れる。二つの実行パイプライン(UとV)は、クロックサイクルあたりそれぞれFIFOバッファから1命令を受け取れる。
例: CLD / REP MOVSDCLD命令は2クロックサイクルかかり、従ってREPプリフィックスのデコードの遅れに影を落とす。もしCLD命令が REP MOVSD から遠くにあったとしたら、コードはもう1クロックサイクルかかっていただろう。
CMP DWORD PTR [EBX],0 / MOV EAX,0 / SETNZ ALCMP命令はここではread/modify命令なので、2クロックサイクルかかる。SETNZ命令の0FhプリフィックスはCMP命令の第2クロックサイクルの間にデコードされるので、PPlainではデコードの遅れは隠される(PMMXは0FHのデコードの遅れはない)。
アドレスとデータの定数は、32ビットコードでは4バイトかかるが16ビットコードでは2バイトしかかからないので、普通は、32ビットコードは16ビットコードより大きい。しかしながら、16ビットコードには、プリフィックスや、隣り合うワードを同時にアクセスするときの問題(10章参照)のような他のペナルティーがある。コードのサイズを減らす別の方法を以下で議論する。
ジャンプの番地、データの番地、データ定数はどれも、符号拡張されるバイトで表現できるなら、つまり、-128から+127までの範囲なら、少ないスペースですむ。
ジャンプの番地については、これの意味は、短いジャンプはコードが2バイトしかかからないが、一方、127バイトを越えるジャンプは無条件ジャンプなら5バイト、条件ジャンプなら6バイトかかるということである。
同様に、データの番地がポインタと-128から+127までの変位で表現できるなら、少ないスペースですむ。
例: MOV EBX,DS:[100000] / ADD EBX,DS:[100004] ; 12バイト これを縮小して: MOV EAX,100000 / MOV EBX,[EAX] / ADD EBX,[EAX+4] ; 10バイトポインタを使うのは、それを何度も使うほど有利になる。だから、データをスタックに格納し、EBPまたはESPをポインタとして使うことは、もちろんデータがポインタから127バイト以内であるという前提で、静的メモリと絶対番地を使うことに比べて、コードを小さくする。一時データの読み書きにPUSHとPOPを使うことは、さらにもっと有利である。
データ定数も-128から+127の間にあれば少ないスペースですむ。即値をもつ多くの命令は、オペランドが符号拡張されるバイトであるような短い形式を持つ。
例: PUSH 200 ; 5バイト PUSH 100 ; 2バイト ADD EBX,128 ; 6バイト SUB EBX,-128 ; 3バイト
短い形式のない即値つき命令で最も重要なのは、MOVである。
例: MOV EAX, 1 ; 5バイト これは次のように変えるとよい: XOR EAX,EAX / INC EAX ; 3バイト または PUSH 1 / POP EAX ; 3バイト
4バイトの即値オペランドを持つMOVは、MOVの前のレジスタの値がわかっていれば、算術演算命令で置き換えるとよいことがある。
例:
MOV [mem1],0 ; 10バイト
MOV [mem2],-1 ; 10バイト
MOV EAX,100 ; 5バイト
MOV EBX,150 ; 5バイト
これは次のように変更するとよい:
XOR EAX,EAX ; 2バイト
MOV [mem1],EAX ; 5バイト
DEC EAX ; 1バイト
MOV [mem2],EAX ; 5バイト
ADD EAX,101 ; 3バイト
LEA EBX,[EAX+50] ; 3バイト
LEA命令のAGIストールに気をつけてほしい。
もし同じ定数を2回以上使うなら、もちろんレジスタにロードするのがよい。
例: MOV DWORD PTR [EBX],0 / MOV DWORD PTR [EBX+4],0 ; 13バイト XOR EAX,EAX / MOV [EBX],EAX / MOV [EBX+4],EAX ; 7バイト
異なる命令は異なる長さを持つことも考慮してよい。次の命令は1バイトしかかからず、従ってたいへん魅力的である。
PUSH reg, POP reg, INC reg32, DEC reg328ビットレジスタのINCとDECは2バイトかかるので、 INC EAX は INC AL より短い。
XCHG EAX,reg も1バイトの命令で、従って MOV EAX,reg より少ないスペースですむが、遅いし、ペアにできない。
いくつかの命令は、アキュームレータを使ったほうが、他のレジスタを使うより1バイト少なくてすむ。
例: MOV EAX,DS:[100000] は MOV EBX,DS:[100000] より短い ADD EAX,1000 は ADD EBX,1000 より短いポインタを使う命令は、(ESPでない)ベースポインタと変位だけのときは、スケールつきインデックスレジスタを持つときや、ベースポインタとインデックスレジスタを持つときや、ベースポインタとしてESPを持つときと比べて、1バイト短くてすむ。
例: MOV EAX,[array][EBX] は MOV EAX,[array][EBX*4] より小さい MOV EAX,[EBP+12] は MOV EAX,[ESP+12] より小さいEBPをベースポインタとして持ち、変位やインデックスがない命令は、他のレジスタと比べて1バイト多くかかる(訳注: インデックスつきの場合も、他のレジスタと比べて1バイト多くかかる)。
MOV EAX,[EBX] は MOV EAX,[EBP] より小さいが MOV EAX,[EBX+4] は MOV EAX,[EBP+4] と同じサイズ
たいがいの浮動小数点命令はペアにできないが、多くはパイプラインにできる。つまり、前の命令が終わる前に命令を開始できる。
例: FADD ST(1),ST(0) ; クロックサイクル1-3 FADD ST(2),ST(0) ; クロックサイクル2-4 FADD ST(3),ST(0) ; クロックサイクル3-5 FADD ST(4),ST(0) ; クロックサイクル4-6
明らかに、二番目の命令が最初の命令の結果を必要としていたら、二つの命令がオーバーラップできない。ほとんどすべての浮動小数点命令は、スタックレジスタのトップであるST(0)に関わるので、命令を前の命令の結果に依存しないようにできる可能性はあまり多くないように見える。この問題の解決策は、レジスタリネーミングである。FXCH命令は、本当は二つのレジスタの内容を交換するのではない。名前を交換するだけである。レジスタスタックをpushまたはpopする命令もリネーミングによって動作する。Pentiumでは、浮動小数点レジスタリネーミングはたいそう最適化されており、レジスタの使用中でもリネーム可能である。レジスタリネーミングは決してストールを起こさない―同じくロックサイクルでレジスタを2回以上リネームすることさえできる。例えば、FLDまたはFCOMPPをFXCHとペアにしたときである。
FXCH命令の適切な使用によって、浮動小数点コードで多くのオーバーラップを達成できる。
例: FLD [a1] ; クロックサイクル1 FADD [a2] ; クロックサイクル2-4 FLD [b1] ; クロックサイクル3 FADD [b2] ; クロックサイクル4-6 FLD [c1] ; クロックサイクル5 FADD [c2] ; クロックサイクル6-8 FXCH ST(2) ; クロックサイクル6 FADD [a3] ; クロックサイクル7-9 FXCH ST(1) ; クロックサイクル7 FADD [b3] ; クロックサイクル8-10 FXCH ST(2) ; クロックサイクル8 FADD [c3] ; クロックサイクル9-11 FXCH ST(1) ; クロックサイクル9 FADD [a4] ; クロックサイクル10-12 FXCH ST(2) ; クロックサイクル10 FADD [b4] ; クロックサイクル11-13 FXCH ST(1) ; クロックサイクル11 FADD [c4] ; クロックサイクル12-14 FXCH ST(2) ; クロックサイクル12上の例では、三つの独立なスレッドをインターリーブしている。各FADDは3クロックサイクルかかり、新しいFADDを各クロックサイクルで開始できる。FADDを'a'スレッドで開始したら、'a'スレッドに戻る前に、二つの新しいFADD命令を'b'と'c'のスレッドで開始する時間がある。このため、3つ毎のFADD命令が同じスレッドに属する。望みのスレッドに属するレジスタをST(0)に持ってくるのに、FXCH命令を毎回使っている。上の例からわかるように、これは規則的なパターンを生成するが、FXCH命令の繰り返しの周期が2あるのに対して、スレッドの周期は3であることに注意してほしい。これはたいそう混乱を招くので、どのレジスタがどこにあるか知るためには、「コンピュータを再生」しなければならない。
FADD,FSUB,FMUL,FILDのすべてのバージョンは3クロックサイクルかかり、オーバーラップ可能である。そのため、これらの命令は上に示した方法でスケジューリングできる。メモリオペランドがレベル1キャッシュにあって適切にアラインされていれば、メモリオペランドはレジスタオペランドより時間がかかることはない。
これまでにあなたは、例外のある規則に慣れてきたに違いない。そして、オーバーラップの規則も例外ではない。FMUL命令を別のFMUL命令の1クロックサイクル後に始めることはできない。FMULの回路が完全にはパイプライン化されていないからである。別の命令を二つのFMULの間に入れることを勧める。
例: FLD [a1] ; クロックサイクル1 FLD [b1] ; クロックサイクル2 FLD [c1] ; クロックサイクル3 FXCH ST(2) ; クロックサイクル3 FMUL [a2] ; クロックサイクル4-6 FXCH ; クロックサイクル4 FMUL [b2] ; クロックサイクル5-7 (ストール) FXCH ST(2) ; クロックサイクル5 FMUL [c2] ; クロックサイクル7-9 (ストール) FXCH ; クロックサイクル7 FSTP [a3] ; クロックサイクル8-9 FXCH ; クロックサイクル10 (ペアにならない) FSTP [b3] ; クロックサイクル11-12 FSTP [c3] ; クロックサイクル13-14ここで、 FMUL [b2] の前と FMUL [c2] の前では、先立つクロックサイクルで別のFMULが始まっているので、ストールを受ける。このコードは、FMULの間にFLD命令を置くことで改良できる:
FLD [a1] ; クロックサイクル1 FMUL [a2] ; クロックサイクル2-4 FLD [b1] ; クロックサイクル3 FMUL [b2] ; クロックサイクル4-6 FLD [c1] ; クロックサイクル5 FMUL [c2] ; クロックサイクル6-8 FXCH ST(2) ; クロックサイクル6 FSTP [a3] ; クロックサイクル7-8 FSTP [b3] ; クロックサイクル9-10 FSTP [c3] ; クロックサイクル11-12他の場合には、FADD,FSUBまたは他の何でもいいからFMULの間に入れてストールを避ければよい。
浮動小数点命令をオーバーラップさせることはもちろん、インターリーブ可能な独立したスレッドがいくつかあることを必要とする。もし、一つの大きな式しか実行するものがないなら、式の各部分を並列に計算して、オーバーラップを実現してもよい。もし、例えば、六つの数を足したいのなら、演算を三つの数から成る二つのスレッドに分けて、二つのスレッドを最後に足せばよい。
FLD [a] ; クロックサイクル1 FADD [b] ; クロックサイクル2-4 FLD [c] ; クロックサイクル3 FADD [d] ; クロックサイクル4-6 FXCH ; クロックサイクル4 FADD [e] ; クロックサイクル5-7 FXCH ; クロックサイクル5 FADD [f] ; クロックサイクル7-9 (ストール) FADD ; クロックサイクル10-12 (ストール)FADD [f] は FADD [d] の結果を待っているので、その前で1クロックのストールを受ける。また、最後のFADDは FADD [f] の結果を待っているので、2クロックのストールを受ける。後者のストールは整数命令をいくつか詰めることで隠せるが、最初のストールは、ここに整数命令を入れるとFXCHがペアにできなくなるので、隠せない。
最初のストールは、二つではなく三つのスレッドを持つことで避けられるが、余計なFLDを要するので、少なくとも足す数が八つないと、スレッドを二つから三つにすることで何も節約できない。
浮動小数点命令のすべてがオーバーラップできるわけではない。いくつかの浮動小数点命令は、引き続く浮動小数点命令よりも整数命令のほうが多くオーバーラップできる。FDIV命令は、例えば、39クロックサイクルかかる。最初を除くすべてのクロックサイクルは整数命令とオーバーラップできるが、浮動小数点命令とは最後の2クロックしかオーバーラップできない。
例: FDIV ; クロックサイクル1-39 (Uパイプ) FXCH ; クロックサイクル1-2 (Vパイプ、不完全なペア) SHR EAX,1 ; クロックサイクル3 (Uパイプ) INC EBX ; クロックサイクル3 (Vパイプ) CMC ; クロックサイクル3-4 (ペアにできない) FADD [x] ; クロックサイクル38-40 (Uパイプ、f.p.ユニット解放を待つ) FXCH ; クロックサイクル38 (Vパイプ) FMUL [y] ; クロックサイクル40-42 (Uパイプ、FDIVの結果を待つ)最初のFXCH命令はFDIVとペアになるが、浮動小数点命令が続かないため余計なクロックがかかる。 SHR / INC ペアはFDIVが終わる前に始まるが、FXCH命令が終わるまで待たなければならない。新しい浮動小数点命令はFDIVの最後の2クロックサイクルでしか実行できないので、FADDはクロック38まで待たなければならない。2番目のFXCHはFADDとペアになる。FMULは割り算の結果を使うので、FDIVが終わるのを待たなければならない。
整数とのオーバーラップの長い浮動小数点命令の後に入れるものが他になければ、プログラムの後のほうで必要だと期待される番地からの、ダミーの読み出しを置いて、必ずそれがレベル1キャッシュに入るようにしてもよい。
例:
FDIV QWORD PTR [EBX]
CMP [ESI],EAX
FMUL QWORD PTR [ESI]
ここでは整数のオーバーラップを、FDIV命令の計算中に、[ESI]にある値をあらかじめキャッシュに入れておくために使っている(CMPの結果は気にしない)。
21章に浮動小数点命令の完全なリストと、何とペアになったりオーバーラップできたりするかが示してある。
算術演算ユニットはパイプライン中で読み込みユニットの一つ後のステップにあるので、浮動小数点命令にメモリオペランドを使うことに対するペナルティーはない。これのトレードオフは浮動小数点データをメモリに格納するときに現れる。メモリへのFSTまたはFSTP命令は実行ステージで2クロックサイクルかかるが、1クロック前にデータを必要とするので、格納する値が1クロック前に準備できていないと1クロックのストールを受ける。これはAGIストールと同様である。
例: FLD [a1] ; クロックサイクル1 FADD [a2] ; クロックサイクル2-4 FLD [b1] ; クロックサイクル3 FADD [b2] ; クロックサイクル4-6 FXCH ; クロックサイクル4 FSTP [a3] ; クロックサイクル6-7 FSTP [b3] ; クロックサイクル8-9FSTP [a3] は、 FADD [a2] の結果が先立つクロックサイクルで準備できていないので、ストールする。多くの場合、浮動小数点コードを四つのスレッドでスケジュールするか、整数命令をいくつか間にはさむことなく、この型のストールを隠すことはできない。FST(P)命令の実行ステージの2クロックは、引き続く命令とペアにしたりオーバーラップしたりすることはできない。
FIADD,FISUB,FIMUL,FIDIV,FICOMのような整数オペランドを持つ命令は、オーバーラップを改良するためにより簡単な命令に分割するとよい。
例: FILD [a] ; クロックサイクル1-3 FIMUL [b] ; クロックサイクル4-9 を分割して: FILD [a] ; クロックサイクル1-3 FILD [b] ; クロックサイクル2-4 FMUL ; クロックサイクル5-7この例では、二つのFILD命令をオーバーラップさせることで2クロックを節約する。
【訳注】これは誤りで、実際には分割しなくても、FIMULはFILDと2クロックオーバーラップして実行される。
ループはたいてい、何回繰り返すかを制御するカウンタを持ち、しばしば、各繰り返しで一つの要素を読むか書くかする配列アクセスを含む。私は例として、配列から整数を読み、各整数の符号を変更し、結果を別の配列に格納する手続きを選んだ。
この手続きのC言語のコードは次のようになるだろう:
void ChangeSign (int * A, int * B, int N) {
int i;
for (i=0; i<N; i++) B[i] = -A[i];}
アセンブラに翻訳すると、このような手続きを書くだろう:
例1:
_ChangeSign PROCEDURE NEAR
PUSH ESI
PUSH EDI
A EQU DWORD PTR [ESP+12]
B EQU DWORD PTR [ESP+16]
N EQU DWORD PTR [ESP+20]
MOV ECX, [N]
JECXZ L2
MOV ESI, [A]
MOV EDI, [B]
CLD
L1: LODSD
NEG EAX
STOSD
LOOP L1
L2: POP EDI
POP ESI
RET ; (Cの呼出規則では余分なpopは不要)
_ChangeSign ENDP
これはうまい答えのように見えるが、遅くてペアにできない命令を含んでいるので、最適ではない。すべてのデータがレベル1キャッシュにある場合、繰り返し当たり11クロックサイクルかかる。
例2:
MOV ECX, [N]
MOV ESI, [A]
TEST ECX, ECX
JZ SHORT L2
MOV EDI, [B]
L1: MOV EAX, [ESI] ; u
XOR EBX, EBX ; v (ペアになる)
ADD ESI, 4 ; u
SUB EBX, EAX ; v (ペアになる)
MOV [EDI], EBX ; u
ADD EDI, 4 ; v (ペアになる)
DEC ECX ; u
JNZ L1 ; v (ペアになる)
L2:
ここではペアにできる命令だけを使い、すべてペアになるように命令をスケジュールした。今や繰り返し当たり4クロックしかかからない。NEG命令を分割することなく同じ速度を得ることはできただろうが、他のペアにできない命令は分割が必要である。
例3:
MOV ESI, [A]
MOV EDI, [B]
MOV ECX, [N]
XOR EDX, EDX
TEST ECX, ECX
JZ SHORT L2
L1: MOV EAX, [ESI+4*EDX] ; u
NEG EAX ; u
MOV [EDI+4*EDX], EAX ; u
INC EDX ; v (ペアになる)
CMP EDX, ECX ; u
JB L1 ; v (ペアになる)
L2:
カウンタと添字に同じレジスタを使うことで、ループ本体の命令が少なくなるが、ペアにできない命令が二つあるので、まだ4クロックサイクルかかる。
例4:
MOV ESI, [A]
MOV EAX, [N]
MOV EDI, [B]
XOR ECX, ECX
LEA ESI, [ESI+4*EAX] ; 配列Aの終わりを指す
SUB ECX, EAX ; -N
LEA EDI, [EDI+4*EAX] ; 配列Bの終わりを指す
JZ SHORT L2
L1: MOV EAX, [ESI+4*ECX] ; u
NEG EAX ; u
MOV [EDI+4*ECX], EAX ; u
INC ECX ; v (ペアになる)
JNZ L1 ; u
L2:
今やループ本体は5命令まで減ったが、ペアリングがうまくいっていないので、まだ4クロックかかる。(もし配列の番地と大きさが定数なら、ESIの代わりにA+SIZE A、EDIの代わりにB+SIZE Bを使うことでレジスタを二つ節約できる)。今度は、ペアリングがどれくらい改良できるか見てみよう。
例5:
MOV EAX, [N]
XOR ECX, ECX
SHL EAX, 2 ; 4 * N
JZ SHORT L3
MOV ESI, [A]
MOV EDI, [B]
SUB ECX, EAX ; - 4 * N
ADD ESI, EAX ; 配列Aの終わりを指す
ADD EDI, EAX ; 配列Bの終わりを指す
JMP SHORT L2
L1: MOV [EDI+ECX-4], EAX ; u
L2: MOV EAX, [ESI+ECX] ; v (ペアになる)
XOR EAX, -1 ; u
ADD ECX, 4 ; v (ペアになる)
INC EAX ; u
JNC L1 ; v (ペアになる)
MOV [EDI+ECX-4], EAX
L3:
ここではEAXの符号反転を計算するのに異なる方法を使った。私がこの方法を使っている理由は、INC命令のきたないトリックを使えるからである。ADDはキャリーフラグを変えるが、INCは変えない。ループカウンタを増やすのには、INCの代わりにADDを使い、ゼロフラグの代わりにキャリーフラグをテストしている。これでキャリーフラグに影響なく INC EAX をはさむことが可能になる。 INC EAX の代わりに LEA EAX,[EAX+1] を使ってもよかったと思うかもしれない。それは少なくともどのフラグも変えないが、LEA命令はAGIを起こすだろうから最適解ではない。
ここでは完全なペアリングが達成できており、ループは今や3クロックサイクルしかかからない。ループカウンタを1増やす(例4のように)か、4増やす(例5のように)かは趣味の問題である。ループのタイミングに違いはない。
例6:
MOV ESI, [A]
MOV EAX, [N]
MOV EDI, [B]
XOR ECX, ECX
LEA ESI, [ESI+4*EAX] ; 配列Aの終わりを指す
SUB ECX, EAX ; -N
LEA EDI, [EDI+4*EAX] ; 配列Bの終わりを指す
JZ SHORT L3
XOR EBX, EBX
MOV EAX, [ESI+4*ECX]
INC ECX
JZ SHORT L2
L1: SUB EBX, EAX ; u
MOV EAX, [ESI+4*ECX] ; v (ペアになる)
MOV [EDI+4*ECX-4], EBX ; u
INC ECX ; v (ペアになる)
MOV EBX, 0 ; u
JNZ L1 ; v (ペアになる)
L2: SUB EBX, EAX
MOV [EDI+4*ECX-4], EBX
L3:
ここでは、最初の値を格納する前に2番目の値を読み始め、これはもちろんペアリングの機会を改良する。ペアリングを改良するためではなく、AGIを避けるために、 MOV EBX,0 命令を INC ECX と JNZ L1 の間に置く。
例7:
MOV ESI, [A]
MOV EAX, [N]
MOV EDI, [B]
XOR ECX, ECX
LEA ESI, [ESI+4*EAX] ; 配列Aの終わりを指す
SUB ECX, EAX ; -N
LEA EDI, [EDI+4*EAX] ; 配列Bの終わりを指す
JZ SHORT L2
TEST AL,1 ; Nが奇数かどうか調べる
JZ SHORT L1
MOV EAX, [ESI+4*ECX] ; Nが奇数なら、その半端を処理する
NEG EAX
MOV [EDI+4*ECX], EAX
INC ECX ; カウンタを偶数にする
JZ SHORT L2 ; N = 1
L1: MOV EAX, [ESI+4*ECX] ; u
MOV EBX, [ESI+4*ECX+4] ; v (ペアになる)
NEG EAX ; u
NEG EBX ; u
MOV [EDI+4*ECX], EAX ; u
MOV [EDI+4*ECX+4], EBX ; v (ペアになる)
ADD ECX, 2 ; u
JNZ L1 ; v (ペアになる)
L2:
今度は二つの操作を並列に行い、これは最高のペアリング機会を提供する。ループは偶数回の操作しかできないので、Nが奇数かどうかテストして、もしそうならループの外で1回分の操作をしなければならない。
このループは最初のMOV命令でAGIがある。先立つクロックサイクルでECXが増やされるからである。それでループは2回分の操作に6クロックサイクルかかる。
例8:
MOV ESI, [A]
MOV EAX, [N]
MOV EDI, [B]
XOR ECX, ECX
LEA ESI, [ESI+4*EAX] ; 配列Aの終わりを指す
SUB ECX, EAX ; -N
LEA EDI, [EDI+4*EAX] ; 配列Aの終わりを指す
JZ SHORT L3
TEST AL,1 ; Nが奇数かどうか調べる
JZ SHORT L2
MOV EAX, [ESI+4*ECX] ; Nが奇数なら、その半端を処理する
NEG EAX ; ペアリングの機会はない
MOV [EDI+4*ECX-4], EAX
INC ECX ; カウンタを偶数にする
JNZ SHORT L2
NOP ; JNZ L2 が予測できないなら、NOPを追加
NOP
JMP SHORT L3 ; N = 1
L1: NEG EAX ; u
NEG EBX ; u
MOV [EDI+4*ECX-8], EAX ; u
MOV [EDI+4*ECX-4], EBX ; v (ペアになる)
L2: MOV EAX, [ESI+4*ECX] ; u
MOV EBX, [ESI+4*ECX+4] ; v (ペアになる)
ADD ECX, 2 ; u
JNZ L1 ; v (ペアになる)
NEG EAX
NEG EBX
MOV [EDI+4*ECX-8], EAX
MOV [EDI+4*ECX-4], EBX
L3:
トリックは、ループカウンタを添字として使わない命令ペアを見つけ、ループを再構成して、前のクロックサイクルでカウンタが増えるようにすることである。今や二つの操作で5クロックサイクルまで減り、可能な最高に近くなった。
データのキャッシングが決定的に重要なら、AとBの配列を結合して、一つの構造を持った配列にし、各B[i]が対応するA[i]の直後に来るようにすることで、速度をさらに改良できるだろう。構造を持った配列が少なくとも8でアラインされていれば、B[i]はいつもA[i]と同じキャッシュラインに入るので、B[i]に書くときにキャッシュミスは決してない。これはもちろんプログラムの他の部分とトレードオフがあるので、利益に対してコストを比べなければならない。
ループを過剰に伸ばすことの欠点は次の通りである:
次の例はバイトの配列のすべての要素に2を加える。
例9:
MOV ESI, [A] ; バイト配列の番地
MOV ECX, [N] ; バイト配列中の要素数
TEST ECX, ECX ; Nが0かどうかテスト
JZ SHORT L2
MOV EAX, [ESI] ; 最初の4バイトを読む
L1: MOV EBX, EAX ; EBXにコピー
AND EAX, 7F7F7F7FH ; EAXの各バイトの下位7ビット
XOR EBX, EAX ; EBXの各バイトの最上位ビットを得る
ADD EAX, 02020202H ; 望みの値を4バイトすべてに加える
XOR EBX, EAX ; 再びビットを組み合わせる
MOV EAX, [ESI+4] ; 次の4バイトを読む
MOV [ESI], EBX ; 結果を格納する
ADD ESI, 4 ; ポインタを増やす
SUB ECX, 4 ; ループカウンタを減らす
JA L1 ; ループ
L2:
このループは4バイト毎に5クロックサイクルかかる。配列はもちろん4でアラインされているべきである。もし配列の要素数が4で割り切れなければ、少し余分なバイト数を後で埋め合せることで、長さを4で割り切れるようにすればよい。このループはいつでも配列の最後を読みすぎるので、一般保護例外を避けるために、必ず配列をセグメントの終わりには置かないようにするべきである。
各バイトの最上位ビットをマスクして、加算時に各バイトから次のバイトへのキャリーがあるかもしれないのを避けていることに注意してほしい。私は最上位ビットを戻すのに、ADDの代わりにXORを使って、キャリーを避けている。 ADD ESI,4 命令は、例4のようにループカウンタを添字に使うようにすれば避けることができただろう。しかしながら、これだとループ本体の命令数が奇数になるので、ペアにならない命令ができてループは依然として5クロックかかるだろう。分岐命令をペアにしないと、分岐が予測ミスしたときに最後の操作の後で1クロック節約できるが、配列の最後へのポインタを設定し、-Nを計算するための準備のコードで余分なクロックサイクルを消費しなければならないため、二つの方法はちょうど同じ速さになる。ここで示した方法は最も簡単で最も短い。
次の例は、最初の0のバイトを探すことで、0で終わる文字列の長さを調べる。これは REP SCASB を使うより速い。
例10:
STRLEN PROC NEAR
MOV EAX,[ESP+4] ; ポインタを得る
MOV EDX,7
ADD EDX,EAX ; pointer+7 (最後に使う)
PUSH EBX
MOV EBX,[EAX] ; 最初の4バイトを読む
ADD EAX,4 ; ポインタを増やす
L1: LEA ECX,[EBX-01010101H] ; 各バイトから1を引く
XOR EBX,-1 ; すべてのバイトを反転する
AND ECX,EBX ; これら二つのAND
MOV EBX,[EAX] ; 次の4バイトを読む
ADD EAX,4 ; ポインタを増やす
AND ECX,80808080H ; 符号ビットをすべてテスト
JZ L1 ; 0のバイトはない、ループを続ける
TEST ECX,00008080H ; 最初の二つのバイトをテスト
JNZ SHORT L2
SHR ECX,16 ; 最初の二つのバイトにない
ADD EAX,2
L2: SHL CL,1 ; 分岐を避けるためキャリーフラグを使う
POP EBX
SBB EAX,EDX ; 長さを計算
RET ; (Pascalなら RET 4)
STRLEN ENDP
ここでまた、ペアリングを改良するために、ある操作の最後を次の操作の最初とオーバーラップさせる方法を使った。比較的少ない回数しかループは繰り返されないだろうから、ループを伸ばすことはしなかった。コードはいつでも文字列の終わりを読み過ぎてしまうので、文字列はセグメントの終わりに置くべきでない。
ループ本体には奇数個の命令があり、そのためペアになっていないものが一つある。他の命令でなく分岐命令をペアにさせないことは、分岐が予測ミスしたときに1クロックサイクル節約できるという利点がある。
TEST ECX,00008080 命令はペアにできない。代わりにペアにできる命令 OR CH,CL を使うこともできたが、そうすると連続する分岐のペナルティーを避けるためにNOPか何かを入れなければならないだろう。 OR CH,CL の別の問題は、PProまたはPIIで部分レジスタストールを起こすだろうことである。それで私はペアにできないTEST命令を選んだ。
4バイトを同時に扱うのはかなり難しくなり得る。コードでは、バイトが0のとき、そのときに限り、0でない値を生成する式を使っている。これが4バイトすべてを一つの操作で調べることを可能にしている。このアルゴリズムはすべてのバイトから1を引く操作を含んでいる(LEA命令で)。引き算の前では、前の例のように最上位ビットをマスクすることはしなかったので、引き算は次のバイトへのボローを生成するかもしれないが、それはバイトが0のときに限る。そしてこれは、まさに我々が、次のバイトが何であるか気にしない状況である。もし逆方向に探すのなら、0を検出後にDWORDを読み直し、4バイトすべてを調べて最後の0を見つけるか、BSWAP命令を使ってバイト順序を逆転させなければならないだろう。
0以外のバイト値を探したいのなら、4バイトすべてを探している値でXORし、上の0を探す方法を使えばよい。
配列のすべてのバイトに2を足す問題に戻ると、次のようにMMX命令の利点を生かすことができる。
例11:
.data
ALIGN 8
ADDENTS DQ 0202020202020202h ; 加えるバイト値8回
A DD ? ; バイト配列の番地
N DD ? ; 繰り返し回数
.code
MOV ESI, [A]
MOV ECX, [N]
MOVQ MM2, [ADDENTS]
JMP SHORT L2
; ループの先頭
L1: MOVQ [ESI-8], MM0 ; 結果を格納
L2: MOVQ MM0, MM2 ; 被加算数をロード
PADDB MM0, [ESI] ; 8バイトを1操作で足す
ADD ESI, 8
DEC ECX
JNZ L1
MOVQ [ESI-8], MM0 ; 最後の結果を格納
EMMS
格納命令はループ制御命令の後に移動して、格納のストールを避けている。
PADDB命令は ADD ESI,8 とペアにならないので、このループは4クロックかかる。(メモリアクセスをするMMX命令は、MMXでない命令や、メモリアクセスをするもう一つのMMX命令とはペアになれない)。ECXを添字にすることで、 ADD ESI,8 を取り除くこともできるが、AGIストールが起きる。
ループのオーバーヘッドは考慮に値するので、ループを伸ばしたい。
例12:
.data
ALIGN 8
ADDENTS DQ 0202020202020202h ; 加えるバイト値8回
A DD ? ; バイト配列の番地
N DD ? ; 繰り返し回数
.code
MOVQ MM2, [ADDENTS]
MOV ESI, [A]
MOV ECX, [N]
MOVQ MM0, MM2
MOVQ MM1, MM2
L3: PADDB MM0, [ESI]
PADDB MM1, [ESI+8]
MOVQ [ESI], MM0
MOVQ MM0, MM2
MOVQ [ESI+8], MM1
MOVQ MM1, MM2
ADD ESI, 16
DEC ECX
JNZ L3
EMMS
この伸ばしたループは繰り返し毎に16バイトを加算するために6クロックかかる。PADD命令はペアにならない。二つのスレッドを交互に使って格納のストールを避けている。
後ですぐに浮動小数点命令を使う場合、MMX命令を使うことには高いペナルティーがあるので、例9のように32ビットレジスタを使いたい状況は依然としてあるだろう。
次のC言語のコードを考えてみよう:
int i, n; double * X; double * Y; double DA; for (i=0; i<n; i++) Y[i] = Y[i] - DA * X[i];このコード片(DAXPYと呼ばれる)は、線型方程式を解く鍵であるため、広く研究されてきた。
例13:
DSIZE = 8 ; データサイズ
MOV EAX, [N] ; 要素数
MOV ESI, [X] ; Xへのポインタ
MOV EDI, [Y] ; Yへのポインタ
XOR ECX, ECX
LEA ESI, [ESI+DSIZE*EAX] ; Xの終わりを指す
SUB ECX, EAX ; -N
LEA EDI, [EDI+DSIZE*EAX] ; Yの終わりを指す
JZ SHORT L3 ; N = 0 のテスト
FLD DSIZE PTR [DA]
FMUL DSIZE PTR [ESI+DSIZE*ECX] ; DA * X[0]
JMP SHORT L2 ; ループに飛び込む
L1: FLD DSIZE PTR [DA]
FMUL DSIZE PTR [ESI+DSIZE*ECX] ; DA * X[i]
FXCH ; 前の結果を得る
FSTP DSIZE PTR [EDI+DSIZE*ECX-DSIZE] ; Y[i] に格納
L2: FSUBR DSIZE PTR [EDI+DSIZE*ECX] ; Y[i] から引く
INC ECX ; 添字を増加
JNZ L1 ; ループ
FSTP DSIZE PTR [EDI+DSIZE*ECX-DSIZE] ; 最後の結果を格納
L3:
ここでは例6と同じ方法―ループカウンタを添字のレジスタとして使い、負の値から0まで数える方法―を使っている。また、ある操作の最後は次の最初とオーバーラップする。
浮動小数点操作のインターリーブは、ここでは完全にうまくいっている。FMULとFSUBRの間の2クロックのストールを、前の結果のFSTPが埋めている。FSUBRとFSTPの間の3クロックのストールを、ループのオーバーヘッドと次の操作の最初の2命令が埋めている。添字が増加した後の最初のクロックサイクルで、添字に依存しない唯一のパラメタを読むことで、AGIストールを避けている。
この解は操作当たり6クロックサイクルかかり、インテルの公表しているループを伸ばした解より良い!
例14:
DSIZE = 8 ; データサイズ
IF DSIZE EQ 4
SHIFTCOUNT = 2
ELSE
SHIFTCOUNT = 3
ENDIF
MOV EAX, [N] ; 要素数
MOV ECX, 3*DSIZE ; カウンタのバイアス
SHL EAX, SHIFTCOUNT ; DSIZE*N
JZ L4 ; N = 0
MOV ESI, [X] ; Xへのポインタ
SUB ECX, EAX ; (3-N)*DSIZE
MOV EDI, [Y] ; Yへのポインタ
SUB ESI, ECX ; 終わりへのポインタ - バイアス
SUB EDI, ECX
TEST ECX, ECX
FLD DSIZE PTR [ESI+ECX] ; 最初のX
JNS SHORT L2 ; 操作は4回未満
L1: ; main loop
FMUL DSIZE PTR [DA]
FLD DSIZE PTR [ESI+ECX+DSIZE]
FMUL DSIZE PTR [DA]
FXCH
FSUBR DSIZE PTR [EDI+ECX]
FXCH
FLD DSIZE PTR [ESI+ECX+2*DSIZE]
FMUL DSIZE PTR [DA]
FXCH
FSUBR DSIZE PTR [EDI+ECX+DSIZE]
FXCH ST(2)
FSTP DSIZE PTR [EDI+ECX]
FSUBR DSIZE PTR [EDI+ECX+2*DSIZE]
FXCH
FSTP DSIZE PTR [EDI+ECX+DSIZE]
FLD DSIZE PTR [ESI+ECX+3*DSIZE]
FXCH
FSTP DSIZE PTR [EDI+ECX+2*DSIZE]
ADD ECX, 3*DSIZE
JS L1 ; ループ
L2: FMUL DSIZE PTR [DA] ; 残りの操作を済ませる
FSUBR DSIZE PTR [EDI+ECX]
SUB ECX, 2*DSIZE ; ポインタのバイアスを変える
JZ SHORT L3 ; 済んでいる
FLD DSIZE PTR [DA] ; 次の操作を始める
FMUL DSIZE PTR [ESI+ECX+3*DSIZE]
FXCH
FSTP DSIZE PTR [EDI+ECX+2*DSIZE]
FSUBR DSIZE PTR [EDI+ECX+3*DSIZE]
ADD ECX, 1*DSIZE
JZ SHORT L3 ; 済んでいる
FLD DSIZE PTR [DA]
FMUL DSIZE PTR [ESI+ECX+3*DSIZE]
FXCH
FSTP DSIZE PTR [EDI+ECX+2*DSIZE]
FSUBR DSIZE PTR [EDI+ECX+3*DSIZE]
ADD ECX, 1*DSIZE
L3: FSTP DSIZE PTR [EDI+ECX+2*DSIZE]
L4:
私がループを3回伸ばす方法を見せているのは、それを勧めるためではなくそれがいかに難しいかを警告するためである! このようなことをするときは、コードのデバッグや検証のためにけっこうな時間を使うことを覚悟してほしい。めんどうをみなければならない問題がいくつかある。ほとんどの場合、巻き込み(つまり、各実行の終わりで終わっていない操作があり、それは次の実行で終わる)を使わなければ、4回未満で伸ばした浮動小数点ループからすべてのストールを取り除くことはできない。上のメインループの最後のFLDは、次の実行の最初の命令である。ここでは、例9と例10のように、配列の終わりを読み過ぎて、最後に余分な値を捨てるという解答をするのは、たいへん魅力的だろう。しかし、配列の後のメモリ位置が正当な浮動小数点数を含んでいない場合、余分な値を読むことで、デノーマルオペランド例外が発生するため、浮動小数点ループでは、これは勧められない。これを避けるためには、少なくとももう一つの操作をメインループの後でしなければならない。
伸ばしたループの外でする操作の数は、通常は、Nを操作の数、Rを伸ばす数として、 N MODULO R になるだろう。しかし巻き込んだループの場合は、上で述べた理由のために、もう一回、つまり (N-1) MODULO R + 1 回しなければならない。
通常は、メインループの前で余分な操作をするほうが望ましいだろうが、ここでは二つの理由によって、後でしなければならない。一つの理由は、巻き込みで残されたオペランドのめんどうを見ることである。もう一つの理由は、Rが2の冪でない場合、余分な操作の回数を計算するには、Rでの除算が必要であり、除算は時間がかかるからである。ループの後で余分な操作をすると、除算が節約できる。
次の問題は、どのようにループカウンタにバイアスをつけて、正しいときに符号が変わるようにするかを計算することと、このバイアスを補償するようにベースポインタを調整することである。最後の問題は、すべてのNの値について、巻き込みで残った操作が、必ず正しく扱えるようにしなければならないことである。
1〜3回の操作をする結びのコードは、別のループとして実装してもよかったが、分岐予測ミスのコストが追加されるだろうから、上の解のほうが速い。 3回伸ばすのがどんなに難しいかやってみせることで怖がらせてしまったので、今度は4回伸ばすとずっと簡単であることを見せよう。
例15:
DSIZE = 8 ; データサイズ
MOV EAX, [N] ; 要素数
MOV ESI, [X] ; Xへのポインタ
MOV EDI, [Y] ; Yへのポインタ
XOR ECX, ECX
LEA ESI, [ESI+DSIZE*EAX] ; Xの終わりを指す
SUB ECX, EAX ; -N
LEA EDI, [EDI+DSIZE*EAX] ; Yの終わりを指す
TEST AL,1 ; Nが奇数か調べる
JZ SHORT L1
FLD DSIZE PTR [DA] ; 半端な操作をする
FMUL DSIZE PTR [ESI+DSIZE*ECX]
FSUBR DSIZE PTR [EDI+DSIZE*ECX]
INC ECX ; カウンタを調整
FSTP DSIZE PTR [EDI+DSIZE*ECX-DSIZE]
L1: TEST AL,2 ; さらに2回分操作するか調べる
JZ L2
FLD DSIZE PTR [DA] ; N MOD 4 = 2 か 3 なのでもう2回する
FMUL DSIZE PTR [ESI+DSIZE*ECX]
FLD DSIZE PTR [DA]
FMUL DSIZE PTR [ESI+DSIZE*ECX+DSIZE]
FXCH
FSUBR DSIZE PTR [EDI+DSIZE*ECX]
FXCH
FSUBR DSIZE PTR [EDI+DSIZE*ECX+DSIZE]
FXCH
FSTP DSIZE PTR [EDI+DSIZE*ECX]
FSTP DSIZE PTR [EDI+DSIZE*ECX+DSIZE]
ADD ECX, 2 ; カウンタは4で割り切れる
L2: TEST ECX, ECX
JZ L4 ; もう操作はない
L3: ; main loop:
FLD DSIZE PTR [DA]
FLD DSIZE PTR [ESI+DSIZE*ECX]
FMUL ST,ST(1)
FLD DSIZE PTR [ESI+DSIZE*ECX+DSIZE]
FMUL ST,ST(2)
FLD DSIZE PTR [ESI+DSIZE*ECX+2*DSIZE]
FMUL ST,ST(3)
FXCH ST(2)
FSUBR DSIZE PTR [EDI+DSIZE*ECX]
FXCH ST(3)
FMUL DSIZE PTR [ESI+DSIZE*ECX+3*DSIZE]
FXCH
FSUBR DSIZE PTR [EDI+DSIZE*ECX+DSIZE]
FXCH ST(2)
FSUBR DSIZE PTR [EDI+DSIZE*ECX+2*DSIZE]
FXCH
FSUBR DSIZE PTR [EDI+DSIZE*ECX+3*DSIZE]
FXCH ST(3)
FSTP DSIZE PTR [EDI+DSIZE*ECX]
FSTP DSIZE PTR [EDI+DSIZE*ECX+2*DSIZE]
FSTP DSIZE PTR [EDI+DSIZE*ECX+DSIZE]
FSTP DSIZE PTR [EDI+DSIZE*ECX+3*DSIZE]
ADD ECX, 4 ; 添字を4増加
JNZ L3 ; ループ
L4:
普通は4回伸ばすとストールのない解を見つけるのはまったく簡単である。メインループの外でする余分な操作の数は N MODULO 4 であり、単にNの下位2ビットを調べることで、除算なしで簡単に計算できる。ループカウンタの扱いを簡単にするために、余分な操作はメインループの後ではなく前に行う。
ループを伸ばすことのトレードオフは、ループの外の余分な操作が不完全なオーバーラップと分岐予測ミスのために遅く、増大したコードサイズのために初回のペナルティーが高くなることである。
一般的なお勧めとしては、Nが大きいか、伸ばすことなくループを巻き込んだときにストールを十分除去できなければ、決定的に重要な整数ループは2回、浮動小数点ループは4回伸ばすべきだと言っておこう。
例: LEA EAX,[EBX+8*ECX-1000]は
MOV EAX,ECX / SHL EAX,3 / ADD EAX,EBX / SUB EAX,1000よりずっと速い。LEA命令はまた、フラグを変化させない加算あるいはシフトをするために使うこともできる。転送元と先のワードサイズは同じでなくてもよいので、 LEA EAX,[BX] は、 MOVZX EAX,BX の有用な置き換えである。
しかしながら、PPlainとPMMXでは、LEA命令は、前のクロックサイクルで変更されたベースレジスタまたはインデックスレジスタを使うと、AGIストールを受けることに、気をつけなければならない。
PPlainとPMMXでは、LEA命令はVパイプでペアにでき、シフト命令はできないので、Vパイプで命令を実行したいときに1、2または3でのシフトの置き換えに使ってもよい。
この32ビットプロセッサには、スケールされたインデックスレジスタ以外何もないような、文献に記されたアドレシングモードはない。そのため、 LEA EAX,[EAX*2] のような命令は、実際には4バイトの即値の変位をつけて、 LEA EAX,[EAX*2+00000000] としてコード化される。代わりに LEA EAX,[EAX+EAX] またはさらに良くして ADD EAX,EAX と書くことで、命令のサイズを縮小できる。後者のコードはAGIの遅れがない。もしたまたま値が0であるような(ループの後のループカウンタのような)レジスタがあれば、それをベースレジスタとして使ってコードサイズを縮小することもできる。
LEA EAX,[EBX*4] ; 7バイト LEA EAX,[ECX+EBX*4] ; 3バイト
MOV [mydata], EAX MOV EBX, EAX
この問題は、ベースレジスタやインデックスレジスタを持てず、転送元としてアキュームレータしか使えない、MOV命令の短い形でのみ起きる。別のレジスタを使う、命令を並べ変える、ポインタを使う、あるいはMOV命令の一般形を直にコード化することで、この問題を避けられる。
32ビットモードでは、 MOV [mem],EAX の一般形は次のように書ける。
DB 89H, 05H DD OFFSET DS:mem
16ビットモードでは、 MOV [mem],AX の一般形は次のように書ける。
DB 89H, 06H DW OFFSET DS:mem
(E)AXの代わりにALを使うには、89Hを88Hで置き換える。
このバグはMMX版でも直っていない。
TEST レジスタ,レジスタ と TEST レジスタ,メモリ はいつでもペアにできる。
例: TEST ECX,ECX ; ペアにできる TEST [mem],EBX ; ペアにできる TEST EDX,256 ; ペアにできない TEST DWORD PTR [EBX],8000H ; ペアにできないペアにできるようにするには、次の方法のどれかを使う。
MOV EAX,[EBX] / TEST EAX,8000H MOV EDX,[EBX] / AND EDX,8000H MOV AL,[EBX+1] / TEST AL,80H MOV AL,[EBX+1] / TEST AL,AL ; (結果はサインフラグ)キャリーフラグにシフトすることでビットをテストすることも可能である。
MOV EAX,[EBX] / SHR EAX,16 ; (結果はキャリーフラグ)
(このペアにできないことの原因はおそらく、この2バイト命令の最初のバイトが、何か他のペアにできない命令と同じで、プロセッサはペア可能性を決めるときに2番目のバイトもチェックする余裕がないことだろう。)
リピートつきのストリング命令は、概ね最適である。可能ならいつでもDWORD版を使い、必ず転送元と転送先の両方を4でアラインする。
REP MOVSDは、転送先がレベル1キャッシュにあるときは、データブロックを転送する最も速い方法である。代わりの方法については19章を参照してほしい。REP MOVS命令がワードを転送先に書く間、同じクロックサイクルで次のワードを転送元から読むことに注意してほしい。規則10.3によれば、この二つの番地のビット2〜4が同じなら、キャッシュバンク競合が起きる。言い換えれば、ESI+(ワードサイズ)-EDIが32で割り切れれば、繰り返し毎に1クロック余計なペナルティーを受ける。キャッシュバンク競合を避ける最も簡単な方法は、DWORD版を使い、転送元と転送先を両方とも8でアラインすることである。最適化されたコードでは、たとえ16ビットモードでも、決してMOVSBとMOVSWを使ってはならない。
REP STOSDは、転送先がキャッシュにあるときは、最適である。
REP LODS、REP SCAS、REP CMPSは最適ではなく、ループで置き換えてもよい。REP SCASBの代わりについては16章の例10を参照してほしい。REP CMPSは、ESIとEDIのビット2〜4が同じなら、キャッシュバンク競合を受ける。
次のコードは BSR ECX,EAX をエミュレートする。
TEST EAX,EAX
JZ SHORT BS1
MOV DWORD PTR [TEMP],EAX
MOV DWORD PTR [TEMP+4],0
FILD QWORD PTR [TEMP]
FSTP QWORD PTR [TEMP]
WAIT ; WAITは古いプロセッサとの互換性のためだけに必要
MOV ECX, DWORD PTR [TEMP+4]
SHR ECX,20 ; 指数部を分離
SUB ECX,3FFH ; 調整
TEST EAX,EAX ; ゼロフラグを降ろす
BS1:
次のコードは BSF ECX,EAX をエミュレートする。
TEST EAX,EAX
JZ SHORT BS2
XOR ECX,ECX
MOV DWORD PTR [TEMP+4],ECX
SUB ECX,EAX
AND EAX,ECX
MOV DWORD PTR [TEMP],EAX
FILD QWORD PTR [TEMP]
FSTP QWORD PTR [TEMP]
WAIT ; WAITは前のプロセッサとの互換性のためだけに必要
MOV ECX, DWORD PTR [TEMP+4]
SHR ECX,20
SUB ECX,3FFH
TEST EAX,EAX ; ゼロフラグを降ろす
BS2:
これらのエミュレーションコードはPProとPIIで使うべきではない。ビットスキャン命令は1または2クロックしかかからないし、上に示したエミュレーションコードには、部分メモリストールが二つある。
例: IMUL EAX,10 は MOV EBX,EAX / ADD EAX,EAX / SHL EBX,3 / ADD EAX,EBX または LEA EAX,[EAX+4*EAX] / ADD EAX,EAX で置き換えられる。
PPlainとPMMXでは、浮動小数点乗算は整数乗算より高速だが、普通は、浮動小数点乗算を使うことによる時間の節約より、整数を浮動小数点数に変換し、結果を変換し戻すのり使う時間のほうが多い。例外は乗算の数に比べて変換の数が少ないときである。MMX乗算は速いが、16ビットオペランドしか使えない。
定数による除算は逆数を掛けることでできる。 q = x/d を計算するには、まず逆数 f = 2^r / dを計算する(ただしrは2進の小数点(位取り点)を定義)。次に、xにfを掛け、右にrだけシフトする。rの最大値は、bをdの2進での桁数-1として、32+bである。(bは 2^b <= d となる最大の整数である)。被除数xの値の最大範囲をカバーするには r = 32+b を使う。
この方法は、丸め誤差を補償するために洗練する必要がある。次のアルゴリズムは、符号なし整数の切り捨て除算の正しい結果、つまりDIV命令のしているのと同じものを与える。
b = dの有効ビット数 - 1 r = 32 + b f = 2^r / d fが整数なら、dは2の冪: 場合Aに行く。 fが整数でないなら、fの小数部が0.5未満か調べる。 fの小数部 < 0.5: 場合Bに行く。 fの小数部 > 0.5: 場合Cに行く。 場合A: (d = 2^b) 結果 = x SHR b 場合B: (fの小数部 < 0.5) fを最も近い整数に丸める 結果 = ((x+1) * f) SHR r 場合C: (fの小数部 > 0.5) fを最も近い整数に丸める result = (x * f) SHR r
例: 5で割りたいとする。 5 = 00000101b. b = 有効2進桁数 - 1 = 2 r = 32+2 = 34 f = 2^34 / 5 = 3435973836.8 = 0CCCCCCCC.CCC...(16進) 小数部は1/2より大きい: 場合Cを使う。 fを切り上げて0CCCCCCCDhとする。
このコードはEAXを5で割って、結果をEDXに返す:
MOV EDX,0CCCCCCCDh
MUL EDX
SHR EDX,2
乗算後、EDXには積を32ビット右にシフトしたものが入っている。r=34なので、もう2だけシフトしなければならない。10で割るには、最後の行を SHR EDX,3 に変えるだけでよい。
場合Bでは、次のようになるだろう:
INC EAX
MOV EDX,f
MUL EDX
SHR EDX,b
このコードはすべてのxの値、ただし、INC命令のオーバーフローで0になってしまう0FFFFFFFFHを除く、でうまく動く。もしx=0FFFFFFFFHになり得るのなら、コードを変更して次のようにする:
MOV EDX,f
ADD EAX,1
JC DOVERFL
MUL EDX
DOVERFL:SHR EDX,b
xの値が限られているのなら、rの小さい値、つまり桁数の少ないものを使ってもよい。rの小さい値を使う理由はいくつかある。
この場合のxの最大値は少なくとも2^(r-b)であり、時にはもっと大きい。コードが正しく動くxの最大値をちょうど知りたいなら、系統的なテストをしなければならない。
段落17.9で説明したように、遅い乗算を速い命令で置き換えたいかもしれない。
次の例はEAXを10で割って結果をEAXに返す。私はr=19の代わりにr=17を選んだ。たまたま最適化しやすいコードになり、xの同じ範囲をカバーするからである。
f = 2^17 / 10 = 3333h, 場合B: q = (x+1)*3333h:
LEA EBX,[EAX+2*EAX+3]
LEA ECX,[EAX+2*EAX+3]
SHL EBX,4
MOV EAX,ECX
SHL ECX,8
ADD EAX,EBX
SHL EBX,8
ADD EAX,ECX
ADD EAX,EBX
SHR EAX,17
系統的なテストでは、このコードはx<10004Hとなるすべてのxで正しく動くことが示された。
次のコードは、同じ除数でのたくさんの除算(符号なし、切り捨て)のしかたを示す。最初に、除数を指定して逆数を計算するためにSET_DIVISORを呼び、次に同じ除数で割る各値についてDIVIDE_FIXEDを呼ぶ。
.data
RECIPROCAL_DIVISOR DD ? ; 除数の逆数を丸めたもの
CORRECTION DD ? ; 場合A: -1, 場合B: 1, 場合C: 0
BSHIFT DD ? ; 除数のビット数 - 1
.code
SET_DIVISOR PROC NEAR ; EAXに除数
PUSH EBX
MOV EBX,EAX
BSR ECX,EAX ; b = 除数のビット数 - 1
MOV EDX,1
JZ ERROR ; エラー: 除数は0
SHL EDX,CL ; 2^b
MOV [BSHIFT],ECX ; bを保存
CMP EAX,EDX
MOV EAX,0
JE SHORT CASE_A ; 除数は2の冪
DIV EBX ; 2^(32+b) / d
SHR EBX,1 ; 除数 / 2
XOR ECX,ECX
CMP EDX,EBX ; 余りと除数/2を比較
SETBE CL ; 場合Bなら1
MOV [CORRECTION],ECX ; 丸め誤差の補正
XOR ECX,1
ADD EAX,ECX ; 場合Cなら1を加算
MOV [RECIPROCAL_DIVISOR],EAX ; 除数の逆数を丸めたもの
POP EBX
RET
CASE_A: MOV [CORRECTION],-1 ; 場合Aであることを覚えておく
POP EBX
RET
SET_DIVISOR ENDP
DIVIDE_FIXED PROC NEAR ; EAXに被除数、結果はEAX
MOV EDX,[CORRECTION]
MOV ECX,[BSHIFT]
TEST EDX,EDX
JS SHORT DSHIFT ; 除数は2の冪
ADD EAX,EDX ; 丸め誤差の補正
JC SHORT DOVERFL ; オーバーフローの補正
MUL [RECIPROCAL_DIVISOR] ; 除数の逆数を掛ける
MOV EAX,EDX
DSHIFT: SHR EAX,CL ; 桁の調整
RET
DOVERFL:MOV EAX,[RECIPROCAL_DIVISOR] ; 被除数 = 0FFFFFFFFH
SHR EAX,CL ; シフトで除算
RET
DIVIDE_FIXED ENDP
このコードは、 0 <= x < 2^32, 0 < d < 2^32 についてDIV命令と同じ結果を与える。
注意: x < 0FFFFFFFFH であると確信できるなら、 JC DOVERFL とそのジャンプ先は不要である。
2の冪であることがほとんど起きず、最適化に値しないならば、DSHIFTへのジャンプを除いて、代わりに場合Aのときは CORRECTION = 0 で乗算をするようにしてもよい。
もし除数が頻繁に変わって、SET_DIVISORに最適化が必要なら、BSR命令を段落17.7で与えたコードで置き換えてもよい。
浮動小数点除算と整数除算を並列に行って時間を節約することも可能である。
例: A = A1 / A2; B = B1 / B2
FILD [B1]
FILD [B2]
MOV EAX, [A1]
MOV EBX, [A2]
CDQ
FDIV
DIV EBX
FISTP [B]
MOV [A], EAX
(浮動小数点制御ワードを望みの丸め方法に設定したか確かめよ)
いつも除算の数を最小にしようとするべきであることは明らかである。定数による浮動小数点除算や、同じ値による繰り返し除算はもちろん逆数の乗算で行うべきである。しかし除算の数を少なくできる状況は他にもたくさんある。例えば、 if (A/B > C)... はBが正なら if (A > B*C)... に、Bが負ならその逆に書き換えられる。
A/B + C/D は (A*D + C*B) / (B*D) に書き換えられる。
もし整数除算を使っているなら、式を書き換えると丸め誤差が異なることを知っているべきである。
例:
b.1. FISTP [mem32]
WAIT ; 整数ユニットで結果を読む前に
MOV EAX,[mem32] ; 浮動小数点ユニットが書き込むのを待つ
b.2. FILD [mem32]
WAIT ; 整数ユニットで上書きする前に
MOV [mem32],EAX ; 浮動小数点ユニットが値を読むのを待つ
b.3. FLD QWORD PTR [ESP]
WAIT ; 偶発的なハードウェア割り込みがスタックの値を
ADD ESP,8 ; 読まれる前に上書きするのを防ぐ
aについて:
aの働きは、古い8087以外のプロセッサには決して必要ない。コードを8087互換にしたいのでなければ、アセンブラに対して上位プロセッサを指定することで、このWAITを入れないように告げるべきである。8087浮動小数点エミュレータもWAIT命令を挿入する。従って、必要なければ、エミュレーションコードを生成しないようにアセンブラに告げるべきである。
bについて:
メモリアクセスを調整するWAIT命令は、8087と80287では絶対必要だが、Pentiumではそうではない。80387と80486で必要かどうかはあまりはっきりしない。私は何回かこれらのインテルプロセッサ上でテストを行ったが、インテルのマニュアルには、FNSTSWとFNSTCWの後を除いてこの目的のWAITは必要と書いてあるにもかかわらず、インテルのどの32ビットプロセッサでも、WAITを省くことによるエラーを発生させることはできなかった。32ビットコードを書いているときでさえ、メモリアクセスを調整するWAIT命令を省くことは100%安全ではない。なぜなら、コードは287コプロセッサつきの80386メインプロセッサで走るかもしれず、そのときはWAITが必要だからである。しかも、私はすべてのハードウェアとソフトウェアの組合せを試したわけではないので、このWAITの必要な、他の状況があるかもしれない。
どんな32ビットプロセッサ(インテル以外のプロセッサも含む)でもコードが確かに動くようにしたいのなら、安全のためにこのWAITを入れることを勧める。
cについて:
アセンブラは、次に示す命令: FCLEX, FINIT, FSAVE, FSTCW, FSTENV, FSTSW の前に、この目的のためのWAITを自動的に入れる。このWAITはFNCLEXなどのように書くことで省ける。私のテストでは、WAITなしのこれらの命令でも、80387ではFNCLEXとFNINITを除いて例外の際に割り込みを生成するので、ほとんどの場合WAITは必要ない。(割り込みからのIRETがFN..命令を指すか次の命令を指すかについて不整合がある)。
他の浮動小数点命令もほとんどすべて、以前の浮動小数点命令がマスクされていない例外ビットをセットしていれば、割り込みを生成するので、例外は遅かれ早かれいずれ検出される傾向にある。プログラムの最後の浮動小数点命令の後にWAITを入れて、すべての例外を確かにつかまえるようにしてもよい。
例外が正確にどこで発生したかを知って、その状況から回復できるようにしたいのなら、WAITはやはり必要である。例えば上のb.3のコードを考えてみよう。ここのFLDが生成する例外から回復できるようにしたいなら、 ADD ESP,8 の後の割り込みはロードされる値を上書きしてしまうので、WAITが必要である。
FLD [a] FCOMP [b] FSTSW AX SAHF JB ASmallerThanB
FSTSW AX の代わりに FNSTSW AX を使い、ペアにできないSAHFを使う代わりにAHを直接テストすることで、このコードを改良できる。(TASM Version 3.0 は FNSTSW AX 命令にバグがある)
FLD [a] FCOMP [b] FNSTSW AX SHR AH,1 JC ASmallerThanBゼロかどうか、または等しいかどうかテストする:
FTST FNSTSW AX AND AH,40H JNZ IsZero ; (ゼロフラグは反転している!)大きいかどうかテストする:
FLD [a] FCOMP [b] FNSTSW AX AND AH,41H JZ AGreaterThanB
TEST AH,41H は、ペアにできないので使ってはいけない。 TEST EAX,4100H は、PProとPIIで部分レジスタストールを起こすので使ってはいけない。
PPlainとPMMXでは、FNSTSW命令はどんな浮動小数点命令の後でも4クロック遅れる(おそらくステータスワードがパイプラインからリアイアするのを待っているからだろう)。このFCOMからFNSTSWまでのレイテンシーを整数命令で埋められるなら、FNSTSW命令は6クロックではなく2クロックしかかからない。この場合、必ずWAITプリフィックスのないバージョンを使うようにせよ。
時には、18章で述べるように、浮動小数点の値の比較に整数命令を使うほうが速い。
CまたはC++のコードがコンパイルされると、浮動小数点数を整数に変換するのは切り捨てで行うが、他の浮動小数点演算では丸めを行うので、FLDCW命令をたくさん生成する。アセンブリ言語に変換された後で、可能な場所では切り捨ての代わりに丸めを使ったり、中で切り捨てが必要なループからFLDCWを外に移動したりすることで、コードを改良できる。
一つのレジスタを解放する最も速い方法は、 FSTP ST である。
二つのレジスタを解放する最も速い方法は、 FCOMPP である。
FFREEを使うことは勧められない。
FISTP DWORD PTR [TEMP]
MOV EAX, [TEMP]
代わりの方法として次のものがある。
.DATA
ALIGN 8
TEMP DQ ?
MAGIC DD 59C00000H ; 2^51 + 2^52 の浮動小数点表現
.CODE
FADD [MAGIC]
FSTP QWORD PTR [TEMP]
MOV EAX, DWORD PTR [TEMP]
「マジックナンバー」 2^51 + 2^52 を加えることは、-2^31と+2^31の間のどんな整数も、倍精度浮動小数点数として格納されるときに下位32ビットに整合されるという効果がある。ゼロ方向に切り捨てるのを除くすべての丸め方法で、FISTPと結果は同じである。制御ワードが切り捨てを指定しているときと、オーバーフローの場合は、結果はFISTPと異なる。古いプロセッサとの互換性のためにWAIT命令が必要かもしれない。段落17.11を参照せよ。
この方法はFISTPを使うより速くはないが、FADDとFSTPの間に3クロックの空きがあって、他の命令で埋められるかもしれないので、よりうまいスケジューリングの機会を提供する。同じ操作で数を2の冪で掛けたり割ったりするのを、マジックナンバーに逆の操作をすることで行える。マジックナンバーに数を加えておくことで、定数の加算もできるが、このときマジックナンバーは倍精度にしなければならない。
例: FLD QWORD PTR [ESI] / FSTP QWORD PTR [EDI] を変更して MOV EAX,[ESI] / MOV EBX,[ESI+4] / MOV [EDI],EAX / MOV [EDI+4],EBX にする。前者のコードは4クロックかかるが、後者は2クロックである。
浮動小数点値がゼロかどうかテスト:
浮動小数点値のゼロは普通、32ビットまたは64ビットのゼロで表されるが、これには落とし穴がある。符号ビットがセットされているかもしれない! マイナスゼロは有効な浮動小数点数とみなされ、プロセッサは実際、例えば負の数とゼロを掛けると符号ビットがセットされたゼロを生成する。だから、浮動小数点数がゼロかどうかテストしたいなら、符号ビットをテストしないようにするべきである。
例: FLD DWORD PTR [EBX] / FTST / FNSTSW AX / AND AH,40H / JNZ IsZero代わりに整数命令を使って、符号ビットをシフトで追い出そう。
MOV EAX,[EBX] / ADD EAX,EAX / JZ IsZero前者のコードは9クロックかかるが、後者はたった2クロックである。 浮動小数点数が倍精度(QWORD)なら、ビット32-62だけ調べればよい。もしそれらがゼロなら、もし普通の浮動小数点数なら下位半分もゼロなのである。
負かどうかテスト:
符号ビットがセットされていて、少なくとも一つの他のビットがセットされていれば、浮動小数点数は負である。
例: MOV EAX,[NumberToTest] / CMP EAX,80000000H / JA IsNegative
符号ビットの操作:
浮動小数点数の符号を変えるには、単に符号ビットを反転させればよい。
例: XOR BYTE PTR [a] + (TYPE a) - 1, 80H
同様に、単に符号ビットをANDするだけで浮動小数点数の絶対値が得られる。
数の比較:
浮動小数点数は、符号ビットを除いて、整数命令で浮動小数点数を比較できるようなユニークな形式で格納される。二つの浮動小数点数が通常の数で正であると確信できるなら、単に整数として比較してよい。
例: FLD [a] / FCOMP [b] / FNSTSW AX / AND AH,1 / JNZ ASmallerThanB を変更して MOV EAX,[a] / MOV EBX,[b] / CMP EAX,EBX / JB ASmallerThanB にする。この方法は、二つの数が同じ精度で、どちらの数の符号ビットもセットされていないと確信できるときだけうまくいく。
もし負の数かもしれないときは、負の数を二の補数に変換して、符号つき比較をしなければならない。
MOV EAX, [a]
MOV EBX, [b]
MOV ECX, EAX
MOV EDX, EBX
SAR ECX, 31 ; 符号ビットをコピー
AND EAX, 7FFFFFFFH ; 符号ビットを除去
SAR EDX, 31
AND EBX, 7FFFFFFFH
XOR EAX, ECX ; 符号ビットがセットされていたら、二の補数にする
XOR EBX, EDX
SUB EAX, ECX
SUB EBX, EDX
CMP EAX, EBX
JL ASmallerThanB ; 符号つき比較
この方法は通常の浮動小数点数すべて(-0を含む)でうまくいく。
FILD QWORD PTR [ESI] / FISTP QWORD PTR [EDI]これは転送先がキャッシュにないときのみ有利である。PPlainで、データブロックをキャッシュされていないメモリに移動する最適な方法は、次の通りである。
TOP: FILD QWORD PTR [ESI]
FILD QWORD PTR [ESI+8]
FXCH
FISTP QWORD PTR [EDI]
FISTP QWORD PTR [EDI+8]
ADD ESI, 16
ADD EDI, 16
DEC ECX
JNZ TOP
転送元と先はもちろん8でアラインされているべきである。遅いFILDとFISTP命令で使われる余分な時間は、書き込み操作の数が半分でよいという事実によって補償される。この方法はPPlainとPMMXにおいてのみ、そして転送先がレベル1キャッシュにないときのみ、有利であることに注意せよ。他のすべてのプロセッサでは、REP MOVSDを使うほうが速い。
MMXプロセッサでは、8バイトを一度に移動するにはMMX命令を使うほうが速い。
TOP: MOVQ MM0,[ESI]
MOVQ [EDI],MM0
ADD ESI,8
ADD EDI,8
DEC ECX
JNZ TOP
キャッシュミスが予期されるなら、このループを伸ばしたりさらに最適化したりする必要は全くない。なぜなら、ここでは命令の実行ではなくメモリアクセスがボトルネックだからである。
PMMXでは、MMX乗算命令は整数乗算より速く、クロックサイクルあたり1回の乗算のスループットでパイプライン動作できるので、16ビット精度でよいのなら、これがPMMXで高速に乗算を行う最良の解決策かもしれない。 整数乗算は、PProとPIIでは浮動小数点乗算より速い。
クロックサイクル:
数字は最小値である。キャッシュミスやミスアラインメントや例外により、クロックカウントはだいぶ増大する。
ペア可能性:
u=Uパイプでペアにできる, v=Vパイプでペアにできる, uv=どちらのパイプでもペアにできる, np=ペアにできない
Opcode Operands Clock cycles Pairability ---------------------------------------------------------------------------- NOP 1 uv MOV r/m, r/m/i 1 uv MOV r/m, sr 1 np MOV sr , r/m >= 2 b) np MOV m , accum 1 uv h) XCHG (E)AX, r 2 np XCHG r , r 3 np XCHG r , m >15 np XLAT 4 np PUSH r/i 1 uv POP r 1 uv PUSH m 2 np POP m 3 np PUSH sr 1 b) np POP sr >= 3 b) np PUSHF 3-5 np POPF 4-6 np PUSHA POPA 5-9 i) np PUSHAD POPAD 5 np LAHF SAHF 2 np MOVSX MOVZX r, r/m 3 a) np LEA r/m 1 uv LDS LES LFS LGS LSS m 4 c) np ADD SUB AND OR XOR r , r/i 1 uv ADD SUB AND OR XOR r , m 2 uv ADD SUB AND OR XOR m , r/i 3 uv ADC SBB r , r/i 1 u ADC SBB r , m 2 u ADC SBB m , r/i 3 u CMP r , r/i 1 uv CMP m , r/i 2 uv TEST r , r 1 uv TEST m , r 2 uv TEST r , i 1 f) TEST m , i 2 np INC DEC r 1 uv INC DEC m 3 uv NEG NOT r/m 1/3 np MUL IMUL r8/r16/m8/m16 11 np MUL IMUL all other versions 9 d) np DIV r8/m8 17 np DIV r16/m16 25 np DIV r32/m32 41 np IDIV r8/m8 22 np IDIV r16/m16 30 np IDIV r32/m32 46 np CBW CWDE 3 np CWD CDQ 2 np SHR SHL SAR SAL r , i 1 u SHR SHL SAR SAL m , i 3 u SHR SHL SAR SAL r/m, CL 4/5 np ROR ROL RCR RCL r/m, 1 1/3 u ROR ROL r/m, i(><1) 1/3 np ROR ROL r/m, CL 4/5 np RCR RCL r/m, i(><1) 8/10 np RCR RCL r/m, CL 7/9 np SHLD SHRD r, i/CL 4 a) np SHLD SHRD m, i/CL 5 a) np BT r, r/i 4 a) np BT m, i 4 a) np BT m, r 9 a) np BTR BTS BTC r, r/i 7 a) np BTR BTS BTC m, i 8 a) np BTR BTS BTC m, r 14 a) np BSF BSR r , r/m 7-73 a) np SETcc r/m 1/2 a) np JMP CALL short/near 1 e) v JMP CALL far >= 3 e) np conditional jump short/near 1/4/5/6 e) v CALL JMP r/m 2/5 e) np RETN 2/5 e) np RETN i 3/6 e) np RETF 4/7 e) np RETF i 5/8 e) np J(E)CXZ short 4-11 e) np LOOP short 5-10 e) np BOUND r , m 8 np CLC STC CMC CLD STD 2 np CLI STI 6-9 np LODS 2 np REP LODS 7+3*n g) np STOS 3 np REP STOS 10+n g) np MOVS 4 np REP MOVS 12+n g) np SCAS 4 np REP(N)E SCAS 9+4*n g) np CMPS 5 np REP(N)E CMPS 8+4*n g) np BSWAP 1 a) np CPUID 13-16 a) np RDTSC 6/8 a) j) np ----------------------------------------------------------------------------注:
クロックサイクル:
数字は最小値である。キャッシュミス、ミスアラインメント、デノーマルオペランドや例外により、クロックカウントはだいぶ増大する。
ペア可能性:
+=FXCHとペアにできる, np=FXCHとペアにできない
i-ov:
整数命令とのオーバーラップ。i-ov=4とは、最後の4クロックサイクルが引き続く整数命令とオーバーラップできることを意味する。
fp-ov:
浮動小数点命令とのオーバーラップ。fp-ov=2とは、最後の2クロックサイクルが引き続く浮動小数点命令とオーバーラップできることを意味する。(WAITは、ここでは浮動小数点命令と考える)
Opcode Operand Clock cycles Pairability i-ov fp-ov ----------------------------------------------------------------------------- FLD r/m32/m64 1 + 0 0 FLD m80 3 np 0 0 FBLD m80 48-58 np 0 0 FST(P) r 1 np 0 0 FST(P) m32/m64 2 m) np 0 0 FST(P) m80 3 m) np 0 0 FBSTP m80 148-154 np 0 0 FILD m 3 np 2 2 FIST(P) m 6 np 0 0 FLDZ FLD1 2 np 0 0 FLDPI FLDL2E etc. 5 np 0 0 FNSTSW AX/m16 6 q) np 0 0 FLDCW m16 8 np 0 0 FNSTCW m16 2 np 0 0 FADD(P) r/m 3 + 2 2 FSUB(R)(P) r/m 3 + 2 2 FMUL(P) r/m 3 + 2 2 n) FDIV(R)(P) r/m 19/33/39 p) + 38 o) 2 FCHS FABS 1 + 0 0 FCOM(P)(P) FUCOM r/m 1 + 0 0 FIADD FISUB(R) m 6 np 2 2 FIMUL m 6 np 2 2 FIDIV(R) m 22/36/42 p) np 38 o) 2 FICOM m 4 np 0 0 FTST 1 np 0 0 FXAM 17-21 np 4 0 FPREM 16-64 np 2 2 FPREM1 20-70 np 2 2 FRNDINT 9-20 np 0 0 FSCALE 20-32 np 5 0 FXTRACT 12-66 np 0 0 FSQRT 70 np 69 o) 2 FSIN FCOS 16-126 np 2 2 FSINCOS 17-137 np 2 2 F2XM1 13-57 np 2 2 FYL2X 22-111 np 2 2 FYL2XP1 22-103 np 2 2 FPATAN 19-134 np 2 2 FPTAN 17-173 np 36 o) 0 FNOP 2 np 0 0 FXCH r 1 np 0 0 FINCSTP FDECSTP 2 np 0 0 FFREE r 2 np 0 0 FNCLEX 6-9 np 0 0 FNINIT 12-22 np 0 0 FNSAVE m 124-300 np 0 0 FRSTOR m 70-95 np 0 0 WAIT 1 np 0 0 -----------------------------------------------------------------------------注:
EMMS命令は1クロックサイクルしかかからないが、EMMSの後の最初の浮動小数点命令は約58クロック余分にかかるし、浮動小数点命令の後の最初のMMX命令は約38クロック余分にかかる。PMMXでは、EMMS命令の後のMMX命令にはペナルティーはないが、PIIではペナルティーの可能性がある。
MMX演算ユニットはパイプライン中でロードユニットの1ステップ後にあるので、MMX命令でメモリオペランドを使うことにペナルティーはない。しかし、MMXレジスタからメモリまたは32ビットレジスタにデータを格納するときはペナルティーがある。データは1クロック先立って準備されていなければならない。これは浮動小数点ストア命令と同様である。
EMMSを除くすべてのMMX命令は、どちらのパイプでもペアにできる。MMX命令のペアリング規則は段落8.10に書かれている。
以下のプログラムはコード片の実行にかかるクロックサイクル数を測るのに便利である。プログラムはテストされるコードを10回実行し、10個のクロックカウントを格納する。PPlainとPMMXでは、プログラムは16ビットと32ビットの両方のモードで使用可能である。
ITER EQU 10 ; 繰り返し回数
OVERHEAD EQU 15 ; PPlainは15、PMMXは17
RDTSC MACRO ; RDTSC命令を定義
DB 0FH,31H
ENDM
.DATA ; データセグメント
ALIGN 4
COUNTER DD 0 ; ループカウンタ
TICS DD 0 ; クロックの一時格納場所
RESULTLIST DD ITER DUP (0) ; テスト結果のリスト
.CODE ; コードセグメント
BEGIN: MOV [COUNTER],0 ; ループカウンタをリセット
TESTLOOP: ; テストループ
;**************** ここでいろんな初期化をする: ************************
FINIT
;**************** 初期化終わり ************************
RDTSC ; クロックカウンタを読む
MOV [TICS],EAX ; カウンタを保存
CLD ; ペアにできない詰めもの
REPT 8
NOP ; 影落とし効果を避けるための、8つのNOP
ENDM
;**************** ここにテストしたい命令を置く: ************************
FLDPI ; これはただの例
FSQRT
RCR EBX,10
FSTP ST
;********************* テストしたい命令の終わり ************************
CLC ; 影を持つ、ペアにできない詰めもの
RDTSC ; 再びカウンタを読む
SUB EAX,[TICS] ; 差を計算
SUB EAX,OVERHEAD ; 詰めものなどに使われるクロックを引く
MOV EDX,[COUNTER] ; ループカウンタ
MOV [RESULTLIST][EDX],EAX ; 結果を表に格納
ADD EDX,TYPE RESULTLIST ; カウンタを増やす
MOV [COUNTER],EDX ; カウンタを格納
CMP EDX,ITER * (TYPE RESULTLIST)
JB TESTLOOP ; ITER回繰り返し
; RESULTLISTにはいっている値を読み出すコードをここに挿入
テストされるコード片の前後にある「詰めもの」の命令は、PPlainで整合性のある結果を得るために入れてある。CLDは、初回と引き続く回でペアリングが必ず同じになるようにするために挿入された、ペアにできない命令である。PPlainで、先行する命令の影に隠れて、テストされるコードのどんなプリフィックスもデコードされないように、8つのNOPが挿入されている。ここでは1バイト命令を使って、初回と引き続く回で同じペアリングが得られるようにした。テストされるコードの後のCLCは、RDTSCの0FHプリフィックスをデコードできる影を持つ、ペアにできない命令で、このためプリフィックスのデコードは、PPlainでテストされるコードの影落とし効果に依存しない。
PMMXでは、FIFO命令バッファを空にしたいならテストする命令の前に XOR EAX,EAX / CPUID を挿入するとよいし、FIFOバッファをいっぱいにしたいなら、何か時間のかかる命令(例えばCLIやAAD)を挿入するとよい。
PProとPIIでは、RDTSCが他と並列に実行されないように、CPUIDのような直列化する命令を各RDTSCの前後に置かなければならない。(CPUIDは直列化命令である。つまり、パイプラインをフラッシュして、進む前にペンディングしている操作がすべて完了するのを待つ。これはテストの目的には便利である。CPUIDは引き続く命令のプリフィックスをデコードできる影を持たない。)
RDTSC命令はPPlainとPMMXの仮想モードでは実行できないので、DOSのプログラムを走らせているなら、リアルモードにしなければならない。(ブート中にF8を押して、「Safe モード(コマンドプロンプトのみ)」または、「bypass startup files」を選ぶ)。
Pentiumプロセッサは特別な性能モニタ用のカウンタを持っており、キャッシュミス、ミスアラインメント、AGIストールなどのようなできごとを数えることができる。性能モニタ用カウンタの使い方についてはこのマニュアルではカバーしないが、MMXテクノロジ・デベロッパーズ・マニュアルに書かれている。
例:
MOV EAX,[ESI]
INC EAX
MOV [EDI],EAX
MOV EAX,[ESI+4]
INC EAX
MOV [EDI+4],EAX
この場合、動的プロセッサは、二つの計算が並列に実行できるように、後半の3命令に異なる物理レジスタを使用し、EAXにリネームするのである。[ESI]がキャッシュミスし、[ESI+]がキャッシュヒットした場合、後半の計算が先に完了する。論理レジスタ名より多くの物理レジスタがあるので、レジスタが足りないときには、この自動レジスタリネーミングを利用できる。
動的プロセッサにはしかし、欠点もある。最も重要なのは、予測ミスしたジャンプは非常に高価(10〜20クロックサイクル!)であることである。この問題を補償するため、動的プロセッサは、ある状況のもとで条件ジャンプの代わりに使える、条件つき移動命令を持っている。
もう一つの欠点は、部分レジスタストールと部分メモリストールである。レジスタの一部に書いた後でレジスタ全体を使うことは、PProとPIIに重大な遅れを生む。
例: MOV AL,[EBX] / MOV ECX,EAXこのペナルティーは MOV ZX EAX,BYTE PTR [EBX] を使うか、最初にレジスタ全体をゼロにすることで避けられる。
XOR EAX,EAX / MOV AL,[EBX] / MOV ECX,EAX動的プロセッサは、レジスタが自分自身とXORされるという組み合わせを認識して、部分レジスタストールを避けるように特別に設計されている。これはPentiumとPentiumProプロセッサの両方で動作するコードを書くのに望ましい方法である。プロセッサは、次の予測ミスした分岐か、割り込みまで、レジスタが自分自身とXORされたことを覚えている。
プロセッサが、異なる供給元からのデータをレジスタの異なる部分に入れて合わせることが必要なときにはいつでも、部分レジスタストールが起きる。
例:
MOV AL, [mem1]
MOV AH, [mem2]
MOV [mem3], AX
これは次のように変更するべき:
MOVZX EAX, BYTE PTR [mem1]
MOVZX EBX, BYTE PTR [mem2]
SHL EBX, 8
OR EAX, EBX
MOV [mem3], AX
プロセッサが二つの異なる供給元からのビットを一つのレジスタに合わせなければならないときはいつでも、部分レジスタストールが発生する。これはフラグレジスタでも起きる。
SAHF
JL XX
SAHFはフラグビットのいくつかに書き込むが、オーバーフローフラグには書き込まない。JL命令はサインフラグとオーバーフローフラグの両方をよむので、SAHFのサインフラグと、SAHFの前のオーバーフローフラグを合わせなければならない。これは部分レジスタストールを与える。同じことは、ADDのようなフラグを変更する命令の後にPUSHFまたはPUSHFDが続くときにも起きる。PUSHFDはフラグレジスタの32ビットすべてをよむが、ADD命令はこれらのうち6つにしか書き込まないので、ここでも部分ストールが起きる。
同じメモリを異なるデータサイズで番地づけるときには、メモリ操作も部分ストールを起こす。
例: MOV [ESI],AL / MOV EBX,[ESI]この状況は、部分レジスタストールと同じである: 最初の命令がESIの指すDWORDの最初のバイトに書き、2番目の命令が4バイト読む。DWORDをEBXに読み込むためには、ALからのバイトをメモリからの残り3バイトと合わせなければならない。
これは部分メモリストールを与えない:
MOV [ESI],EAX / MOV BL,[ESI]しかしこれは与える:
MOV [ESI],EAX / MOV BL,[ESI+1]この状況は部分レジスタストールと似ていない。ここでの規則は、書き込んだものの一部を読むことは、アラインメントが同じでないときに部分ストールを起こすということである。
3番目の種類のストールは、CLでシフトまたはローテートした後どのフラグビットを調べても起きる。
これら3種類のストールは、間に別の命令をはさむことでマスクできる。 この文書で述べている最適化の大部分は、インテル以外のプロセッサを含め、他のプロセッサに対して負の影響は少しだけ、あるいは全くないが、知っておくべき問題がいくつかある。
レジスタの一部に書き込んだ後でレジスタ全体を使うことは、80486では中程度の遅れを生み、PentiumProとPentiumIIでは重大な遅れを生む。これは部分レジスタストールと呼ばれる。
例: MOV AL,[EBX] / MOV ECX,EAXこのペナルティーは、レジスタ全体をゼロにすることで避けられる。
XOR EAX,EAX / MOV AL,[EBX] / MOV ECX,EAXまたは、MOVZX EAX,BYTE PTR [EBX] を使う。 同様のペナルティーは、同じメモリを異なるデータサイズで番地づけるときにも起きる。
例: MOV [ESI],EAX / MOV BL,[ESI]
浮動小数点命令のPentium向けスケジューリングは、しばしばたくさんの余計なFXCH命令を要する。これは古いマイクロプロセッサの実行を遅くするが、PentiumProやインテル以外の進んだプロセッサではそうではない。
PentiumMMXとPentiumIIプロセッサで使えるMMX命令は、超並列の整数計算にたいへん便利である。
PentiumProの最も有利な点は、最適化の多く―命令の並べ変えや、複雑な命令を単純な命令に分割すること―をあなたに代わってやってくれることである。しかし、完全に最適化されたコードでは、二つのプロセッサの違いは小さくなる。
二つのプロセッサは、基本的に同じ数の実行ユニットを持つため、スループットは同じに近いはずである。PProはメモリの読み書きのための分離されたユニットを持ち、三つの操作を、そのうち一つがメモリ読み込みなら、同時に行えるが、一方、Pentiumのように二つのメモリ読み込みや書き込みを同時に実行することは、できない。
PProは以下の点でPentiumよりよい。
この結果Pentium Proは、完全に最適化されていて、多くの予測できない分岐を持ち、自然な並列性のほとんどあるいは全くない浮動小数点コードがたくさんあるコードでは、実はPentiumより遅いかもしれない。他の場合はたいてい、PProのほうが速い。
どちらのプロセッサの欠点もたいてい、注意深い最適化と32ビットフラットモードの使用で回避できる。しかし、PProに置ける予測ミスしたジャンプの問題は、条件つきMOV命令を代わりに使える場合以外は、避けることができない。
コードに以前のプロセッサでの互換性を持たせたいなら、MMXおよびPentiumProプロセッサの新しい命令を利用することは、問題を引き起こすことになる。解決策は、コードのいくつかのバージョンを、それぞれ特定のプロセッサ向けに最適化して、書くことであろう。プログラムは自動的にどのプロセッサが走っているか検出し、適当なバージョンのコードを選ぶべきである。このような複雑なアプローチはもちろん、プログラムの最も決定的な部分にだけ必要である。