How to optimize for the Pentium
family of the microprocessors (In Japanese)

1. はじめに

このマニュアルの情報は、私自身の調査と試験に基づいており、さまざまな人たちから受け取った情報で補足されている。このマニュアルのために追加情報を私に送ってくれた人々に感謝したい。このマニュアルは他の情報源に比べて理解しやすく正確で、他に見られない細かい事項をたくさん含んでいる。この情報を使えば、あなたは多くの場合に、あるコード片が正確に何クロックサイクルかかるのか計算することができるようになる。私はこのマニュアルに含まれている情報のすべてが正しいとは主張しない。いくつかのタイミング等は正確に測定することが困難あるいは不可能で、また私には、インテルのマニュアルの著者が持っているような技術的な内部情報を見る手段がない。

このマニュアルでは次の様なバージョンのPentiumプロセッサについて議論する。

    略称            名前
    ------------------------------------------------
    PPlain          plain old Pentium (without MMX)
    PMMX            Pentium with MMX
    PPro            Pentium Pro
    PII             Pentium II(CeleronとXeonを含む)
    PIII            Pentium III(変種を含む)
    ------------------------------------------------

アセンブリ言語の文法はMASM5.10に従っている。公式なX86のアセンブリ言語は存在しないが、大部分のアセンブラがMASM5.10互換モードを持っているため、あなたが手にすることのできる事実上の標準に最も近い。しかしながら、私はMASM5.10の使用をお勧めしない。というのは、32ビットモードにおいて深刻なバグがあるからである。TASMか若しくはより新しいバージョンのMASMをお勧めする。

このマニュアルの中のいくつかの注釈はインテルに対する批判と映るかもしれない。しかし、他のメーカーの方が優れているという意味に取らないでいただきたい。ペンティアム・マイクロプロセッサ・ファミリーは、おそらくどの競争メーカーよりも速いと思われ、またそのように証明されており、良い試験結果がある。こういった理由により、他の競争メーカーについては、私や他のいかなる人の似たような独自の調査もされたことはない。

アセンブリ言語でのプログラミングは、高級言語よりはるかに難しい。バグを生成するのは容易であり、その発見はたいへん困難である。ここで警告である! 読者は既にアセンブリ言語の経験があると仮定する。もしそうでなければ、複雑な最適化を始める前に、どうかアセンブリ言語に関する本を何か読んで、プログラミングの経験を得てほしい。

PPlain、PMMXチップのハードウェア設計は、一般的な最適化方法を使ったというよりはむしろ、いくつかのよく使われる命令やその組合せに特に最適化された、多くの特徴を持っている。その結果、ソフトウェアをこの設計向きに最適化するのはかなり複雑で、多くの例外があるが、相当な性能向上が可能かもしれない。PPro、PII、PIIIプロセッサはたいそう異なった設計となっており、プロセッサは命令をアウト・オブ・オーダー実行することにより、かなりの最適化作業の面倒をみている。しかし、これらのプロセッサのより複雑な設計は多くの潜在的なボトルネックを作り出しており、これらのプロセッサ向けに手で最適化することにより多くの利益があるかもしれない。

コードをアセンブリ言語に変換する前に、使っているアルゴリズムが最適であることを確認してほしい。コード片をアセンブラコードに直すよりアルゴリズムを改良したほうがずっとよい結果になることがしばしばある。

次に、プログラムの決定的に重要な部分を同定しなければならない。しばしば、99%以上のCPU時間がプログラムの最も内側のループで消費されている。この場合、そのループだけを最適化し、それ以外はすべて高級言語のままにしておくべきである。アセンブラプログラマの中には、プログラムの誤った部分を最適化するのにエネルギーを浪費し、努力の主な効果が、プログラムのデバッグや保守を難しくしただけという人もいる!

もしプログラムの決定的に重要な部分がどこか明らかでなければ、プロファイラを使ってみつけるとよい。もしボトルネックがディスクアクセスであるとわかったら、アセンブリプログラミングに行くのではなくて、ディスクアクセスをシーケンシャルに行うようにプログラムを変更して、ディスクのキャッシングを改良するとよい。もしボトルネックがグラフィクスの出力なら、グラフィクスの手続きを呼ぶ回数を減らす方法を探すとよい。

高級言語のコンパイラのいくつかは特定のプロセッサ向けの比較的よい最適化を提供しているが、手でさらに最適化することは、普通もっと良い性能を生み出すことができる。

どうか私にプログラミングの質問を送らないでほしい。私はあなたの宿題をするつもりはない。

ナノ秒狩りの幸運を祈る!

2. 文献

3. 高級言語からアセンブリ言語の関数を呼ぶには

関数の呼び出し方法と名前の変換はたいそう複雑である。多数の異なる呼び出し方法があり、コンパイラのブランドが異なればこの点で互換性がない。アセンブリ言語のサブルーチンをC++から呼び出そうとしているなら、整合性と互換性の点から最もよい方法は、関数を extern "C" と _cdecl で宣言することである。アセンブリ言語のコードは、アンダースコア(_)が先頭についた関数名を持ち、外部名の大文字小文字を区別する(オプション -mx)ようにアセンブルされるはずである。

オーバーロード関数や、オーバーロード演算子、メンバ関数その他のC++特有の機能を使うには、まずC++でコーディングし、正しいリンク情報と呼び出し規約を得るためにC++ソースをアセンブリ言語に翻訳する必要がある。細部については、各々のメーカーのコンパイラ毎に異なる。アセンブリ関数を extern "C" と _cdecl で宣言することなしに異なったコンパイラで呼び出し可能にするには、各々のコンパイラ毎に外部参照名を与える必要がある。例えば、オーバーロードされた square 関数を次に示す。

  ; int square (int x);
  SQUARE_I PROC NEAR             ; 整数２乗関数
  @square$qi LABEL NEAR          ; Borland コンパイラのためのリンク名
  ?square@@YAHH@Z LABEL NEAR     ; Microsoft コンパイラのためのリンク名
  _square__Fi LABEL NEAR         ; Gnu コンパイラのためのリンク名
  PUBLIC @square$qi, ?square@@YAHH@Z, _square__Fi
          MOV     EAX, [ESP+4]
          IMUL    EAX
          RET
  SQUARE_I ENDP

  ; double square (double x);
  SQUARE_D PROC NEAR             ; 倍精度浮動小数点２乗関数
  @square$qd LABEL NEAR          ; Borland コンパイラのためのリンク名
  ?square@@YANN@Z LABEL NEAR     ; Microsoft コンパイラのためのリンク名
  _square__Fd LABEL NEAR         ; Gnu コンパイラのためのリンク名
  PUBLIC @square$qd, ?square@@YANN@Z, _square__Fd
          FLD     QWORD PTR [ESP+4]
          FMUL    ST(0), ST(0)
          RET
  SQUARE_D ENDP

パラメータの渡し方は呼び出し規約に依存する。

    呼び出し規約　  スタック上のパラメータの順序　 パラメータの消去
      _cdecl　　　 最初のパラメータは下位アドレス   　呼び出し側
      _stdcall　　 最初のパラメータは下位アドレス   　サブルーチン
      _fastcall　　コンパイラによる　　　　　　　   　サブルーチン
      _pascal　　　最初のパラメータは上位アドレス　   サブルーチン

32ビットモードのWindows、C++または他の言語の場合
整数の戻り値はEAXレジスタ、浮動小数点の戻り値はST(0)である。レジスタEAX, ECX, EDX(EBXは除く)は手続きによって破壊されるかもしれない。すなわちすべての他のレジスタはどこかに保存し、しかる後に復元しなければならない。セグメントレジスタは一時的にも破壊してはならない。フラットセグメントを指すすべてのCS, DS, ESとSSがそうである。FSはオペレーティング・システムによって使われる。GSは使われないが、予約されている。フラグは以下の制約下で変化する可能性がある。方向フラグは初期値0である。方向フラグは一時的にセットされるかもしれないが、いかなる呼び出しまたは戻る前にも、クリアされていなければならない。浮動小数点レジスタ・スタックは手続きの始まりにおいて空でなければならない。但しST(0)が戻り値として用いられる場合を除く。MMXレジスタは手続きによって破壊される可能性があり、浮動小数点レジスタを用いるかもしれないすべての手続きから戻る前と呼び出す前に、EMMSによって同様にクリアされるかもしれない。XMMレジスタ・パラメータの渡し方と戻り値はインテルのアプリケーションノートの589ページに書かれている。手続きはレジスタEBX, ESI, EDI, EBPに頼ることもあり、すべてのセグメントレジスタは他の手続きを呼んでも変化しない。

4. デバッグと確認

高級言語で書かれたテストプログラムのサブルーチンが動くようになったら、アセンブリ言語に翻訳する準備ができたことになる。

これで最適化を始めることができる。変更をするたびにコードをテストプログラム上 で走らせて、正しく動くか見るべきである。

すべてのバージョンに番号をつけて保存せよ。そうすれば、テストプログラムではつかまらなかった(間違った番地に書き込んでしまうような)エラーを見つけた場合に戻ってテストし直せる。

5. メモリモデル

6. アラインメント

                      アラインメント     アラインメント
    オペランドサイズ   PPlainとPMMX     PPro、PIIとPIII
    ------------------------------------------------------
    1  (byte)              1                   1
    2  (word)              2                   2
    4  (dword)             4                   4
    6  (fword)             4                   8
    8  (qword)             8                   8
    10 (tbyte)             8                  16
    16 (oword)         利用不可               16
    ------------------------------------------------------

PPlainとPMMAXにおいては、ミスアラインされたデータのアクセスは最低3クロックサイクル余計にかかる。キャッシュラインの境界をまたぐと、ペナルティはさらに高くなる。

PPro, PIIとPIIIにおいては、ミスアラインされたデータがキャッシュライン境界をまたぐ時、6-12クロック余計にかかる。16バイトよりも小さいミスアラインされたオペランドでも32バイト境界をまたがなければ、ペナルティはない。

8または16バイトでアラインされたDWORDのスタックは、問題となることがある。よくある方法は、アラインされたフレームポインタを用意することである。アラインされたローカルデータを持つ関数は次のようなものであろう。

_FuncWithAlign PROC NEAR
        PUSH    EBP                        ; 始まりのコード
        MOV     EBP, ESP
        AND     EBP, -8                    ; フレームポインタを8バイトでアラインする
        FLD     DWORD PTR [ESP+8]          ; 関数パラメータ
        SUB     ESP, LocalSpace + 4        ; ローカル領域の確保
        FSTP    QWORD PTR [EBP-LocalSpace] ; アラインされた領域に何か書き込む
        ...
        ADD     ESP, LocalSpace + 4        ; 終わりのコード ESPの復元
        POP     EBP                        ; (PPlain/PMMXでAGIストールが起きる)
        RET
_FuncWithAlign ENDP

7. キャッシュ

データキャッシュはそれぞれ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とPIIIは四つある。

この結果、キャッシュは、番地のビット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クロックサイクルしかかからない(初回を除いて)。たいへん考慮に値する改良である!

既に述べたように、PMMX, PIIとPIIIは同じセット値を持つ四つのキャッシュラインを持てるように、四ウェイのキャッシュを備えている(あるインテルの説明書は誤ってPIIのキャッシュは二ウェイだと述べている)。

データの番地が同じキャッシュ値かどうか決めるのは、特に異なるセグメントに散らばっているときは、たいへん難しいかもしれない。この種の問題を避ける最もよい方法は、プログラムの決定的に重要な部分で使われるすべてのデータをキャッシュより大きくない一つの連続したブロックか、キャッシュのサイズの半分以下の二つのブロック(例えば静的データで一つのブロック、スタック上のデータで一つのブロック)に入れることである。これでキャッシュラインはきっと最適に使われるようになるだろう。

コードの決定的に重要な部分が大きなデータ構造やランダムなデータ番地をアクセスするなら、すべてのよく使う変数(カウンタ、ポインタ、制御変数など)を一つの連続した4kバイト以下のブロックに入れて、ランダムなデータをアクセスするための、キャッシュラインの完全なセットがあるようにしたいかもしれない。たぶんサブルーチンの引数や戻り番地のためのスタックスペースは結局必要なので、最もよいのは、よく使う静的データをスタック上の動的変数にコピーし、変更があったものは決定的に重要なループの外でコピーし戻すことである。

一次キャッシュにないデータ項目を読むことは、キャッシュライン全体を二次キャッシュから満たすことになる。これはだいたい200ns(つまり100MHzシステムでは20クロック、200MHzシステムでは40クロック)かかるが、最初に読みたかったバイトは50〜100nsで利用可能になる。データ項目が二次キャッシュにもない場合、200〜300nsの遅れが生ずる。DRAMのページ境界をまたぐと、この遅れは多少長くなる(DRAMのページサイズは、4または8MBの72ピンRAMモジュールで1KB、16または32MBモジュールで2KBである)。

8. 初めての実行と繰り返し実行の比較

9. 番地生成インターロック(AGI) (PPlain and PMMX)

    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とPIIIには、メモリー読み出しとLEA命令にはAGIストールはないが、メモリ書き込みにはAGIストールが存在する。 これは、連続したコードが書き込みの終了を待つのでない限り、さほど問題にならない。

10. 整数命令のペアリング(PPlain and PMMX)

10.1 完全なペアリング

PPlainでは、プリフィックスつき命令は、near条件分岐を除いてUパイプでのみ実行可能である。

PMMXでは、オペランドサイズ、アドレスサイズ、0FHのプリフィックスつき命令は、どちらのパイプでも実行可能であるが、一方、セグメント、リピート、ロックプリフィックスつき命令はUパイプでしか実行できない。

8. 変位と即値の両方を持つ命令は、PPlainではペアにできず、PMMXでは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      ; ペアにできる

不完全なペアリングは次のような場合に起きる。

ここで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ビットモードを使うことである。

11. 複雑な命令を単純な命令に分割(PPlain and PMMX)

例:

    ADD [mem1],EAX / ADD [mem2],EBX    ; 5クロックサイクル

    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とPIIIでは、分割された命令がより小さなμ-OPSを生成しない限り必要ない。

12. プリフィックス(PPlain and PMMX)

13. PPro, PIIとPIIIのパイプラインの概要

命令コードはコードキャッシュから、アラインされた16バイトかたまりとして、16バイトのかたまり二つを保持できるダブルバッファに取り込まれる。命令はダブルバッファからデコーダへブロックとして移される。このブロックを ifetchブロック(instruction fetch block)と呼ぼうと思う。ifetchブロックは普通16バイト長だが、アラインされていない。ダブルバッファの用途は、16バイト境界(すなわち番地が16で割り切れる)をまたぐ命令のデコードを可能にすることである。

ifetchブロックは命令長デコーダへ移され、これは各々の命令の始まりと終わりを決定する。次に命令デコーダへ移される。各々のクロックサイクル毎に三つの命令をデコードするために、三つのデコーダがある。同じクロックサイクル内でデコードされる最高三つまでの命令グループは、デコードグループと呼ばれる。

デコーダは命令をマイクロオペシーション、略してμ-OPSへと翻訳する。簡単な命令は一つのμ-OPSを生成するが、その一方でもっと複雑な命令はいくつかのμ-OPSを生成するかもしれない。例えば、命令 ADD EAX,[MEM] は二つのμ-OPSを生成する。一つはソースオペランドをメモリから読み、もう一つは加算を実行する。命令をμ-OPSへと分割する目的は、システム中の後の取り扱いをより効率的にするためである。

三つのデコーダはD0、D1、そしてD2と呼ばれる。D0はすべての命令を扱うことができる一方、D1とD2は一つのμ-OPSを生成する簡単な命令のみ扱える。

デコーダから来たμ-OPSは、短いキューを通して、レジスタ・アロケーション・テーブル(RAT)へと移される。μ-OPSは後に常置レジスタ(EAX, EBXなど)に書かれることになるテンポラリレジスタ上で実行される。RATの目的は、μ-OPSにどのテンポラリレジスタを使うか知らせることと、レジスタ・リネーミング(後述)を可能にすることである。

RATの後、μ-OPSはリオーダ・バッファ(ROB)へと送られる。ROBの用途は、アウト・オブ・オーダー実行をすることにある。μ-OPSは、必要とするオペランドが利用可能となるまでリザベーション・ステーションに止まる。もし前に生成されたμ-OPSがまだ終了してないことが原因で一つのμ-OPSが遅らされると、ROBは時間を稼ぐために今実行できる他のμ-OPSを探すかもしれない。

実行の準備ができたμ-OPSは、実行ユニットへ送られ、五つのポートへ振り分けられる。ポート0と1は演算命令、ジャンプ等を扱うことができる。ポート2はメモリからの読み込みをすべて担当し、ポート3はメモリへの書き込みのための番地を生成し、ポート4はメモリへの書き込みを行う。

命令の実行が終了すると、ROB内でリタイアの準備ができた印が付けられる。そしてそれはリタイアメント・ステーションへと送られる。ここでμ-OPSによって使われたテンポラリレジスタは常置レジスタに書かれる。μ-OPSはアウト・オブ・オーダー実行をしてもよいが、それらは順序よくリタイアしなければならない。

次の章では、パイプラインの各々の段階でのスループットを最適化する方法の詳細について述べるつもりである。

14. 命令のデコード(PPro, PII and PIII)

デコーダはクロックサイクル当たり三つの命令を扱うことができるが、それは特定の条件に合致した時に限られる。デコーダD0は1クロックサイクル当たり四つまでのμ-OPSを生成する命令を扱うことができる。デコーダD1とD2は一つのμ-OPSを生成する命令しか扱うことができず、それらの命令長が8バイトを超えてはならない。

同じクロックサイクルで二つあるいは三つの命令をデコードできる規則を簡単に要約してみよう。

• 最初の命令(D0)が四つを超えるμ-OPSを生成しないこと。
• 二番目と三番目の命令は各々一つを超えるμ-OPSを生成しないこと。
• 二番目と三番目の命令長は各々8バイトを超えないこと。
• 命令が同じ16バイトのifetchブロックに収まっていなければならない(これについては次の章を参照のこと)。

生成されるμ-OPSの数が四つを超える命令のデコードには、2以上のクロックサイクルを必要とし、この間他の命令を並列にデコードすることはできない。

この規則に従うと、デコードグループの最初の命令が四つのμ-OPSを生成し、次の二つが各々一つのμ-OPSを生成したとすると、デコーダは1クロックサイクル当たり最大六つのμ-OPSを生成できることになる。最小は1クロックサイクル当たり二つのμ-OPSを生成する場合で、すべての命令が二つのμ-OPSを生成する時、D1とD2は全く使われない。

最大のスループットを得るために、命令を4-1-1型に従って並べることをお勧めする。二つ〜四つのμ-OPSを生成する命令の間には簡単な一つのμ-OPSを生成する命令を二つ、デコード時間を増やさないという意味においてはただで挿入できる。例えば

    MOV     EBX, [MEM1]     ; 1μ-OPS (D0)
    INC     EBX             ; 1μ-OPS (D1)
    ADD     EAX, [MEM2]     ; 2μ-OPS (D0)
    ADD     [MEM3], EAX     ; 4μ-OPS (D0)

この例ではデコードに3クロックサイクル要している。命令を並べ替え、二つのデコードクループに分けることにより、1クロックサイクル稼ぐことができる。

    ADD     EAX, [MEM2]     ; 2μ-OPS (D0)
    MOV     EBX, [MEM1]     ; 1μ-OPS (D1)
    INC     EBX             ; 1μ-OPS (D2)
    ADD     [MEM3], EAX     ; 4μ-OPS (D0)

今やデコーダは2クロックサイクルで八つのμ-OPSを生成し、それは多分満足のいくものである。その後のパイプライン内のステージでは1クロックサイクル当たり三つのμ-OPSしか扱うことができないので、デコード速度がそれより速ければ、デコードがボトルネックにならないと考えられる。しかしながら、次の章で述べるように命令取り込み機構の複雑さがデコードの足かせとなることがあるので、安全のために1クロックサイクル当たりのμ-OPSの生成速度が三つを超えるように狙いを定めたいと思うだろう。

15. 命令の取り込み (PPro, PII and PIII)

16. レジスタ・リネーミング (PPro, PII and PIII)

16.1 依存関係の解消

         MOV EAX, [MEM1]
         IMUL EAX, 6
         MOV [MEM2], EAX
         MOV EAX, [MEM3]
         INC EAX
         MOV [MEM4], EAX

ここで、最初の三つの命令からはどんな結果も必要としないという意味において、最後の三つの命令は最初の三つの命令と独立しているので。初期のプロセッサで最適化するためには、最後の三つの命令にEAXと異なるレジスタを使用し、命令を並べ替えて、最後の三つの命令が最初の三つの命令と並列に実行されるようにしなければならなかっただろう。PPro、PIIとPIIIプロセッサではこれを自動的に行ってくれる。EAXに書き込む度に、新しいテンポラリレジスタが割り当てられる。この結果、MOV EAX,[MEM3]命令は先の命令に依存しなくなる。アウト・オブ・オーダー実行により、[MEM]への移動は、遅いIMUL命令より先に終わるだろう。

レジスタ・リネーミングは完全に自動的に行われる。命令がレジスタに書き込む度に、常置レジスタの代わりに新しいテンポラリレジスタが割り当てられる。レジスタからの読み出しと書き込みの両方を行う命令もリネーミングの原因となる。例えば、上のINC EAX命令は、一つのテンポラリレジスタを入力用に、もう一つのテンポラリレジスタを出力用に割り当てる。これはもちろん独立性を損なうことはない。しかし、後に説明するように、連続したレジスタの読み出しには、いくつかの重要な点がある。

すべての一般用レジスタ、即ちスタックポインタ、フラグ、浮動小数点レジスタ、MMXレジスタ、XMMレジスタとセグメントレジスタはリネームできる。コントロールレジスタと浮動小数点ステータスレジスタはリネームできない。これが、これらのレジスタの使用が遅い原因である。40個の万能テンポラリレジスタがあるので、すべてのテンポラリレジスタを使い切ってしまうことはありそうにない。

レジスタを0にする一般的な方法は、XOR EAX,EAXまたはSUB EAX,EAXである。これらの命令は先に入っていた値と独立とは見なされない。先にある遅い命令への依存を取り除くには、MOV EAX,0命令を使えばよい。

レジスタ・リネーミングはレジスタ・エイリアス・テーブル(RAT)とリオーダ・バッファ(ROB)によって制御される。デコーダからのμ-OPSはキューを通ってRATへ送られる。そしてROBとリザベーション・ステーションへと送られる。RATは1クロックサイクル当たり三つのμ-OPSを扱うことができる。これは、マイクロプロセッサのスループットは、平均して1クロックサイクル当たり三つのμ-OPSを超えられないということである。

リネーミングの数の実際的な制限はない。RATは1クロックサイクル当たり三つのレジスタをリネームでき、同じレジスタであっても1クロックサイクルに三回リネームできる。

17. アウト・オブ・オーダー実行 (PPro, PII and PIII)

メモリへの書き込みは、他の書き込みと比べてアウト・オブ・オーダー実行することはできない。四つの書き込みバッファがあるので、多くのキャッシュ・ミスやキャッシュされていないメモリに書き込んでいることが予期されるならば、四つの書き込みを同時に行い、次の四つの書き込みの前にプロセッサに何か他の仕事を確実にさせるようにスケジュールすることを勧める。メモリの読み出しと他の命令は、IN命令、OUT命令、その他のシリアル化命令を除いてアウト・オブ・オーダー実行できる。

コードがメモリへの書き込みをし、そのすぐ後に同じ番地から読み出しをする場合、読み出しは誤って書き込みよりも先に実行されることがある。というのは、ROBは並べ替えをしている時はメモリの番地がわからないからである。このエラーは書き込み番地が計算される時に検出され、読み出し動作(これは投機実行であった)は再実行されなければならない。このペナルティはおおよそ3クロックである。このペナルティを避ける唯一の方法は、同じ番地のメモリへの書き込みと引き続く読み出しの間に実行ユニットに他の仕事を確実にさせることである。

18. リタイアメント (PPro, PII and PIII)

リタイアメント・ステーションは1クロックサイクル当たり三つのμ-OPSを扱うことができる。RAT内でスループットは既に1クロック当たり三つのμ-OPSに制限されているので、これは問題に見えないかもしれない。しかし、リタイアメントは二つの理由のためにまだなおボトルネックになりうる。まず、命令は順序正しくリタイアしなければならない。μ-OPSをアウト・オブ・オーダー実行すると、順序に従ったすべての先行するμ-OPSがリタイアしないと、リタイアできない。二番目の制限は、ジャンプ命令はリタイアメント・ステーションの三つのスロットの内最も最初にリタイアしなければならないことである。丁度次の命令がD0だけに収まる場合D1とD2デコーダが空になるように、次のリタイアするμ-OPSがジャンプ命令で取られるとリタイアメント・ステーション内の後の二つのスロットが空になる。これは、μ-OPSの数が3で割り切れない命令を持つ小さなループの場合重大である。

リオーダ・バッファ(ROB)内の全てのμ-OPSはリタイアするまでとどまる。ROBは40個のμ-OPSを保持できる。これは長い遅延を伴う命令または遅い命令の間に実行できる命令の数を制限する。除算が終了する前にROBはリタイアを待つ実行されたμ-OPSで満たされる。除算が終了、リタイアした時にのみ、連続するμ-OPSはリタイアを開始できる。というのはリタイアは順序に従って実行されるからである。

19. パーシャル・ストール (PPro, PII and PIII)

19.1 パーシャル・レジスタ・ストール

        MOV AL, BYTE PTR [M8]
        MOV EBX, EAX            ; パーシャル・レジスタ・ストール

これは5〜6クロックの遅延を伴う。この理由は、ALにテンポラリレジスタが割り当てられるからである(AHとは独立するように)。実行ユニットはALとEAXの残りの値とを結合できるようになる前に、ALへの書き込みがリタイアするまで待たなければならない。ストールはコードを次のように替えることによって避けられる。

        MOVZX EBX, BYTE PTR [MEM8]
        AND EAX, 0FFFFFF00h
        OR EBX, EAX

もちろんパーシャル・ストールは、パーシャル・レジスタに書いた後に別の命令を挿入することによって避けることもできる。これはフルサイズのレジスタを読む前に、リタイアまでの時間を稼ぐためである。

違うサイズのデータ(8, 16, そして32ビット)を混ぜる時はいつも、パーシャル・ストールが起きることに気を付けておくべきである。

        MOV BH, 0
        ADD BX, AX              ; ストールあり
        INC EBX                 ; ストールあり

フルサイズのレジスタ、またはより大きなサイズでレジスタに書き込んだ後でパーシャル・レジスタを読み出しても、ストールは生じない。

        MOV EAX, [MEM32]
        ADD BL, AL              ; ストールなし
        ADD BH, AH              ; ストールなし
        MOV CX, AX              ; ストールなし
        MOV DX, BX              ; ストールあり

パーシャル・レジスタ・ストールを避ける最も簡単な方法は、いつもフルサイズのレジスタを用い、より小さなメモリ・オペランドより読み出す時にMOVZXまたはMOVSXを用いることである。これらの命令はPPro, PIIとPIIIでは速いが、初期のプロセッサでは遅い。それゆえ、すべてのプロセッサで適度にコードが働くようにしたい場合の妥協案を示す。MOVZX EAX,BYTE PTR [M8]の代わりに以下のようにすればよい。

        XOR EAX, EAX
        MOV AL, BYTE PTR [M8]

この組み合わせはPPro, PIIとPIIIで、後でEAXから読み出す場合にパーシャル・レジスタ・ストールを避ける特別な場合である。秘訣は、レジスタ自身でXORを取れば、レジスタには空というタグが付けられる所にある。プロセッサはEAXの上位24ビットがゼロであることを覚えており、パーシャル・ストールは避けることができる。この機構は一定の組み合わせの時のみ働く。

        XOR EAX, EAX
        MOV AL, 3
        MOV EBX, EAX            ; ストールなし

        XOR AH, AH
        MOV AL, 3
        MOV BX, AX              ; ストールなし

        XOR EAX, EAX
        MOV AH, 3
        MOV EBX, EAX            ; ストールあり

        SUB EBX, EBX
        MOV BL, DL
        MOV ECX, EBX            ; ストールなし

        MOV EBX, 0
        MOV BL, DL
        MOV ECX, EBX            ; ストールあり

        MOV BL, DL
        XOR EBX, EBX            ; ストールなし

レジスタをゼロにするのに、レジスタそれ自身から減算することはXORを実行するのに等しいが、MOV命令を用いてゼロにした場合はストールを妨げることはできない。

XORをループの外に置くことができる。

        XOR EAX, EAX
        MOV ECX, 100
LL:     MOV AL, [ESI]
        MOV [EDI], EAX          ; ストールなし
        INC ESI
        ADD EDI, 4
        DEC ECX
        JNZ LL

プロセッサは割り込み、分岐予測ミス、シリアル化イベントが起きない限り、EAXの上位24ビットがゼロであることを覚えている。

レジスタ全体をプッシュするかもしれないサブルーチンを呼び出す前に、パーシャル・レジスタをすべて中和することを覚えておくべきである。

        ADD BL, AL
        MOV [MEM8], BL
        XOR EBX, EBX            ; BLを中和する
        CALL _HighLevelFunction

大部分の高級言語の手続きは、上で述べたようにBLレジスタを中和しておかないと、パーシャル・レジスタ・ストールを生じるようなEBXレジスタのプッシュを、手続きの最初で行う。

レジスタをXORでゼロにする手法は、それより前の命令との依存性を断ち切ることはできない。

        DIV EBX
        MOV [MEM], EAX
        MOV EAX, 0              ; 依存性を断ち切る
        XOR EAX, EAX            ; パーシャル・レジスタ・ストールを妨げる
        MOV AL, CL
        ADD EBX, EAX

EAXを二回ゼロにすることは無駄に見えるかもしれないが、MOV EAX,0なしでは、最後の命令は遅いDIV命令が終わるまで待たなければならず、XOR EAX,EAXなしではパーシャル・レジスタ・ストールが生じる。

FNSTSW AX命令は特別である。32ビットモードではEAX全体に書き込むように振る舞う。実際は、このようなことを32ビットモードで行っている:

    AND EAX,0FFFF0000h / FNSTSW TEMP / OR EAX,TEMP

これゆえ、32ビットモードではこの命令の後でEAXから読み出してもパーシャル・レジスタ・ストールは生じない。

    FNSTSW AX / MOV EBX,EAX         ; 16ビットモード時のみストールあり
    MOV AX,0  / FNSTSW AX           ; 32ビットモード時のみストールあり

        CMP EAX, EBX
        INC ECX
        JBE XX          ; パーシャル・フラグ・ストール

JBE命令はキャリーフラグとゼロフラグの両方を読む。INC命令はゼロフラグを変化させるが、キャリーフラグを変化させない。JBE命令は、CMP命令からのキャリーフラグとINC命令からのゼロフラグを結合できるまで、前の二つの命令がリタイアするのを待たなければならない。この状態は意図的なフラグの組み合わせというよりはむしろバグである可能性が高い。これを修正するには、INC ECXをADD ECX,1に替えればよい。似たようなパーシャル・フラグ・ストールの原因となるバグは、SAHF / JL XXである。JL命令はサインフラグとオーバーフローフラグを調べるが、SAHF命令はオーバーフローフラグを変化させない。これを修正するには、JL XXをJS XXに替えればよい。

思いがけいことに(インテルの説明書で述べられていることに反して)、フラグビットのいくつかを変更する命令の後で、変更しなかったフラグビットだけを読んだ時に、パーシャル・フラグ・ストールを受けることがある。

        CMP EAX, EBX
        INC ECX
        JC  XX          ; パーシャル・フラグ・ストール

しかし、変更したビットのみを読めばこれは起きない。

        CMP EAX, EBX
        INC ECX
        JE  XX          ; ストールなし

パーシャル・フラグ・ストールは多くのまたはすべてのフラグビットを読んだ時に起きやすい。すなわち、LAHF, PUSHF, PUSHFDである。次の命令群は、LAHF, PUSHF(D)命令が後に置かれた時にパーシャル・フラグ・ストールを起こしやすい。INC, DEC, TEST, ビットテスト、ビットスキャン、CLC, STC, CMC, CLD, STD, CLI, STI, MUL, IMUL、そしてすべてのシフトと回転命令である。次の命令群はパーシャル・フラグ・ストールの原因とはならない。AND, OR, XOR, ADD, ADC, SUB, SBB, CMP, NEG命令。TEST命令とAND命令は、定義によればフラグに全く同じ動作をするにも関わらず、振る舞いが異なるのは奇妙である。フラグの値をストアする際に、ストールを避けるため、LAHF命令やPUSHF(D)命令の替わりにSETcc命令を用いてもよい。

例:

    INC EAX   / PUSHFD      ; ストールあり
    ADD EAX,1 / PUSHFD      ; ストールなし

    SHR EAX,1 / PUSHFD      ; ストールあり
    SHR EAX,1 / OR EAX,EAX / PUSHFD   ; ストールなし

    TEST EBX,EBX / LAHF     ; ストールあり
    AND  EBX,EBX / LAHF     ; ストールなし
    TEST EBX,EBX / SETZ AL  ; ストールなし

    CLC / SETZ AL           ; ストールあり
    CLD / SETZ AL           ; ストールなし

パーシャル・フラグ・ストールのペナルティはおおよそ4クロックである。

    SHR EAX,1 / JZ XX                ; ストールなし
    SHR EAX,2 / JZ XX                ; ストールあり
    SHR EAX,2 / OR EAX,EAX / JZ XX   ; ストールなし

    SHR EAX,5 / JC XX                ; ストールあり
    SHR EAX,4 / SHR EAX,1 / JC XX    ; ストールなし

    SHR EAX,CL / JZ XX               ; CL = 1でもストールあり
    SHRD EAX,EBX,1 / JZ XX           ; ストールあり
    ROL EBX,8 / JC XX                ; ストールあり

これらのストールのペナルティはおおよそ4クロックである。

        MOV BYTE PTR [ESI], AL
        MOV EBX, DWORD PTR [ESI]        ; パーシャル・メモリ・ストール

ここでプロセッサはALから書かれたバイトと、次の3バイトを結合するためにストールが起きる。3バイトは前からメモリにあった値で、EBXに読み込むために4バイト得るために必要である。このペナルティはおおよそ7〜8クロックである。

パーシャル・レジスタ・ストールに似ていないが、より大きなサイズのオペランドを書いたあと、その一部分を違う番地で始まる所から読めば、パーシャル・メモリ・ストールが起きる。

        MOV DWORD PTR [ESI], EAX
        MOV BL, BYTE PTR [ESI]          ; ストールなし
        MOV BH, BYTE PTR [ESI+1]        ; ストールあり

このストールは、最後の行をMOV BH,AHで置き換えれば避けることができる。しかし、次のような状況は解決できない。

        FISTP QWORD PTR [EDI]
        MOV EAX, DWORD PTR [EDI]
        MOV EDX, DWORD PTR [EDI+4]      ; ストールあり

面白いことに、書き込みと読み出しが全く異なる番地の場合もパーシャル・メモリ・ストールが起きることがある。これは、同じセット値を持つ異なるキャッシュ・バンクに対して起こる。

        MOV BYTE PTR [ESI], AL
        MOV EBX, DWORD PTR [ESI+4092]   ; ストールなし
        MOV ECX, DWORD PTR [ESI+4096]   ; ストールあり

20. 依存の連鎖 (PPro, PII and PIII)

例:

   MOV EAX, [MEM1]
   ADD EAX, [MEM2]
   ADD EAX, [MEM3]
   ADD EAX, [MEM4]
   MOV [MEM5], EAX

この例では、ADD命令は各々二つのμ-OPSを生成する。一つはメモリからの読み出し(ポート2)、もう一つは加算(ポート0または1)である。読み出しμ-OPSはアウト・オブ・オーダー実行できるが、加算のμ-OPSは前のμ-OPSが終了するまで待たなければならない。この依存関係の連続はそんなに長い実行時間を必要としない。というのは各々の加算は1クロックしかかからないからである。しかしこれが乗算のような遅い命令、またはもっと悪い場合、例えば除算などなら、依存の連鎖を壊すためにぜひとも何らかの手を打たなければならない。これには、多数のアキュムレータを使う方法がある。

   MOV EAX, [MEM1]         ; 最初の連鎖のスタート
   MOV EBX, [MEM2]         ; 他のアキュムレータによる連鎖のスタート
   IMUL EAX, [MEM3]
   IMUL EBX, [MEM4]
   IMUL EAX, EBX           ; 最後に連鎖を結合する
   MOV [MEM5], EAX

ここで、二番目のIMUL命令は最初の命令が終了する前に始めることができる。IMUL命令が4クロックかかり、完全にパイプライン化されているので、4つまでのアキュムレータを使ってよい。

除算はパイプライン化されていないので、除算の連鎖に同じ手を使うことはできない。しかしもちろんすべての除数を掛け合わせて最後に一度だけ割ってよい。

浮動小数点命令は整数命令より長い遅延があるため、ぜひとも長い浮動小数点の依存の連鎖を壊すべきである。

   FLD [MEM1]         ; 最初の連鎖のスタート
   FLD [MEM2]         ; 異なるアキュムレータによる二番目の連鎖のスタート
   FADD [MEM3]
   FXCH
   FADD [MEM4]
   FXCH
   FADD [MEM5]
   FADD               ; 最後に連鎖を結合する
   FSTP [MEM6]

このために多くのFXCH命令が必要であるが、心配はない。これは安価である。FXCH命令はRATの中でレジスタ・リネーミングによって解決される。それで実行ユニットに何らのロードもない。もっとも、FXCHはRAT, ROB, リタイアメント・ステーションで1μ-OPSとして数えられる。

依存の連鎖が長い時は三つのアキュムレータが必要になる。

        FLD [MEM1]              ; 最初の連鎖のスタート
        FLD [MEM2]              ; 二番目の連鎖のスタート
        FLD [MEM3]              ; 三番目の連鎖のスタート
        FADD [MEM4]             ; 三番目の連鎖
        FXCH ST(1)
        FADD [MEM5]             ; 二番目の連鎖
        FXCH ST(2)
        FADD [MEM6]             ; 最初の連鎖
        FXCH ST(1)
        FADD [MEM7]             ; 三番目の連鎖
        FXCH ST(2)
        FADD [MEM8]             ; 二番目の連鎖
        FXCH ST(1)
        FADD                    ; 最初と三番目の連鎖の結合
        FADD                    ; 二番目の連鎖の結合
        FSTP [MEM9]

即値をメモリに書き込んだ直後に読み出すのは避けよ。

        MOV [TEMP], EAX
        MOV EBX, [TEMP]

直前のメモリの書き込みが終了する前に同じメモリ番地から読もうとする試みにはペナルティがある。上の例で、最後の命令をMOV EBX,EAXに変えるか、または間に何か別の命令を挟むとよい。

整数レジスタから浮動小数点レジスタへと変換する、またはその逆の、メモリに中間データを書き込むことが避けられない一つの状況がある。例えば

        MOV EAX, [MEM1]
        ADD EAX, [MEM2]
        MOV [TEMP], EAX
        FILD [TEMP]

TEMPへの書き込みとTEMPからの読み出しの間に何も入れないならば、EAXの替わりに浮動小数点レジスタを使うことを考えてもよい。

        FILD [MEM1]
        FIADD [MEM2]

連続したジャンプ、呼び出し、復帰もまた依存の連鎖と考えられる。これらの命令のスループットは2クロック当たり1ジャンプである。それゆえ、ジャンプ命令の間にプロセッサに何か他のことをさせるのが望ましい。

21. ボトルネックを探す (PPro, PII and PIII)

コードのキャッシュ・ミスが予測されるなら、コードのよく使われる部分が一緒になるように再構築するとよい。

22. ジャンプと分岐 (すべてのプロセッサ)

予測は、各分岐またはジャンプ命令の履歴を格納して、各命令の以前の実行履歴から予測を行う、 Branch Target Buffer (BTB)に基づいて行われる。BTBは、新しいエントリが擬似ランダム置換方式で割り当てられるようなset-associativeキャッシュと似た構成になっている。

コードを最適化するとき、予測ミスのペナルティの数を最小にすることが重要である。これには、分岐予測がどのように働くかよく理解することが要求される。

分岐予測機構についてはインテルのマニュアルにも、また他のどこでも正確には書かれていない。だから私は、たいへん詳細な記述をここで与える。この情報は私自身の調査に基づいている(PPlainでは Karki Jitendra Bahadur の助けもあった)。

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:

(これは、インテルのマニュアルやチュートリにある勧めとは逆である。)

だが、最もよく実行される枝を最初に置く理由もあるかもしれない。

1. めったに実行されない枝をコードの最後に置くことで、コードキャッシュの使用効率を上げることができる。
2. めったに分岐しない分岐命令はたいていはBTBにはいらずにいて、BTBの使用効率を上げる可能性がある。
3. 他の分岐命令によってBTBから追い出されてしまった分岐命令は、分岐しないと予測される。
4. 分岐予測の非対称性は、PPlainにだけある。

これらの考慮は、しかしながら、小さく決定的に重要なループに関してはウェイトは小さいので、やはり、分布の偏った枝の構成は、分岐命令が分岐するほうが多いようにすることを勧める。ただし、枝2の実行頻度があまりに小さくて、予測ミスが問題にならないときを除く。

同様に、ループの条件テストの分岐命令は、この例のように、なるべく最後に来るように構成するべきである。

        MOV ECX, [N]
L:      MOV [EDI],EAX
        ADD EDI,4
        DEC ECX
        JNZ L

もしNが大きければ、JNZ命令は分岐するほうが多く、続けて2回通り抜けることはない。

連続する制御移行命令の問題はこれだけではない。別の問題は、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である場合を除いて)。

要約すると、連続するジャンプは、次のような問題につながる可能性がある。

• 先行する予測ミスした制御移行命令によりパイプラインがフラッシュされているときに、ジャンプ先のロードに失敗。
• ジャンプでない命令に誤って適用され、ジャンプすると予測してしまうBTBエントリ。
• 上の結果、誤って適用されたBTBエントリはその状態を減らされ、後でそれの属するジャンプの予測ミスにつながるかもしれない。無条件ジャンプであっても、この理由により通り抜けると予測され得る。
• 二つの制御移行命令が同じBTBエントリを共有し、誤ったジャンプ先の予測につながる。

この混乱はすべて、たくさんのペナルティを与えるので、うまく予測できない制御移行命令のすぐ後またはジャンプ先に、ジャンプを含む命令ペアを置くことは、絶対に避けるべきである。

そろそろこれを説明する例を挙げるころである。

        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では従って、ジャンプする番地のリストがよい解かもしれない。ジャンプする番地のリストはデータセグメントに置くべきである。決してデータをコードセグメントに置くな!

22.1.4 きついループ(PPlain)

22.2 PMMX、PPro、PII、PIIIの分岐予測

22.2.1 BTBの構成(PMMX, PPro PII and PIII)

PPro、PIIとPIIIの branch target buffer は512個のエントリを持ち、それは16ウェイ×32セットの構成になっている。各エントリは、それの属する制御移行命令の最後のバイトのビット4〜31で特定される。ビット4〜8がセットを定義し、BTBに入れられたすべてのビットがタグとなる。512バイト離れた制御移行命令同士は同じセット値を持つので、時には互いに相手をBTBから押し出したりする。セット毎に16のウェイがあるので、これはそんなには起きないだろう。

PPro、PIIとPIIIはどんな制御移行命令でもそれが最初に実行されたときにBTBエントリを割り当てる。PMMXはそれが最初にジャンプしたときに割り当てる。PMMXでは、決してジャンプしない分岐命令はBTBには入らずにいる。そして一度ジャンプしたら、もう決して再びジャンプしなくても、それはBTBにとどまるのである。

エントリは、同じセット値を持つ別の制御移行命令がBTBエントリを必要としたときに、BTBから押し出されることもある。

22.2.2 予測ミスのペナルティ(PMMX, PPro, PII and PIII)

PPro、PIIとPIIIでは、長いパイプラインのせいで、予測ミスのペナルティは非常に高い。予測ミスは普通、10〜20クロックサイクルかかる。そのため、PPro、PIIとPIIIで走らせるときには、予測のうまくいかない分岐を意識しておくことは非常に重要である。

22.2.3 条件ジャンプのパターン認識(PMMX, PPro, PII and PIII)

このメカニズムは、 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個のカウンタは使わない。

22.2.4 完全に予測できるパターン(PMMX, PPro, PII and PIII)

周期       パターン
-----------------------------------------------------------------------------
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

BTBエントリが割り当てられた後、パターン認識機構が規則的な繰り返しパターンを学習するのに2周期かかる。学習期間での予測ミスのパターンには再現性がない。これはたぶん、BTBエントリには割り当てに先立って何かが入っているからだろう。BTBエントリはランダムに割り当てられるので、最初の学習期間の間に何が起きているか予測できる可能性はほとんどない。

22.2.5 規則的なパターンからのはずれの扱い(PMMX, PPro, PII and PIII)

例:
0001110001110001110001011100011100011100010111000
                      ^                   ^

二つの異なる規則的なパターンが交互に起きるときも、予測機構はたいへん有効である。例えば、000111というパターン(周期6)が何度も繰り返され、次にパターン01(周期2)が何度も、そして000111のパターンにもどるとすると、分岐予測機構は000111のパターンを再学習する必要はない。なぜなら、000111の列で使われるカウンタは、01の列ではいじらないからである。二つのパターンが2〜3回交替した後では、パターンの切り替え毎にたった1回だけの予測ミスで、パターンの変化も扱えるように学習してしまう。

22.2.6 完全には予測できないパターン(PMMX, PPro, PII and PIII)

000001000001000001
    ^^    ^^    ^^
    ab    ab    ab

        CDQ
        XOR EAX,EDX
        SUB EAX,EDX

キャリーフラグはこの種のトリックには特に役に立つ。

値が0ならキャリーを立てる:  CMP [VALUE],1
値が0でなければキャリーを立てる:  XOR EAX,EAX / CMP EAX,[VALUE]
キャリーならカウンタを増やす:  ADC EAX,0
キャリーが立つたびにビットをセットする:  RCL EAX,1
キャリーが立っているならビットマスクを生成する:  SBB EAX,EAX
任意の条件でビットをセットする:  SETcond AL
任意の条件ですべてのビットをセットする:  XOR EAX,EAX / SETNcond AL / DEC EAX
(最後の例では、条件を反転するのを忘れないように)

この例は、二つの符号なし数の小さいほうを見つける: 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

このようなトリックが余分なコードに見合うかどうかは、条件ジャンプがどれだけ予測できるか、そして、連続するジャンプのペナルティを受けるようなジャンプが直後にあるかどうかによる。

23. コードサイズの縮小 (すべてのプロセッサ)

24. 浮動小数点コードのスケジューリング (PPlain and PMMX)

• 最初の命令(Uパイプで実行される)はFLD,FADD,FSUB,FMUL,FDIV,FCOM,FCHSまたはFABSでなければならない。
• 二番目の命令(Vパイプで実行される)はFXCHでなければならない。
• FXCHに続く命令は浮動小数点命令でなければならない。そうでないとFXCHは不完全にペアになり、余計なクロックサイクルを使う。

たいがいの浮動小数点命令はペアにできないが、多くはパイプラインにできる。つまり、前の命令が終わる前に命令を開始できる。例:

    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,FSUB,FMUL,FILDのすべてのバージョンは3クロックサイクルかかり、オーバーラップ可能である。そのため、これらの命令は上に示した方法でスケジューリングできる。メモリオペランドが一次キャッシュにあって適切にアラインされていれば、メモリオペランドはレジスタオペランドより時間がかかることはない。

これまでにあなたは、例外のある規則に慣れてきたに違いない。そして、オーバーラップの規則も例外ではない。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

    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の結果を待つ)

整数とのオーバーラップの長い浮動小数点命令の後に入れるものが他になければ、プログラムの後のほうで必要だと期待される番地からの、ダミーの読み出しを置いて、必ずそれが一次キャッシュに入るようにしてもよい。例:

    FDIV    QWORD PTR [EBX]
    CMP     [ESI],EAX
    FMUL    QWORD PTR [ESI]

ここでは整数のオーバーラップを、FDIV命令の計算中に、[ESI]にある値をあらかじめキャッシュに入れておくために使っている(CMPの結果は気にしない)。

25. ループの最適化 (すべてのプロセッサ)

この手続きのC言語のコードは次のようになるだろう。

void ChangeSign (int * A, int * B, int N) {
  int i;
  for (i=0; i<N; i++) B[i] = -A[i];}

アセンブラに翻訳すると、このような手続きを書くだろう。

例1.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

ペアにできる命令だけを使う (PPlain and PMMX)

例1.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:

カウンタと添字に同じレジスタを使う (PPlain and PMMX)

例1.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:

カウンタを0で終わりにする (PPlain and PMMX)

例1.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:

計算をループのオーバーヘッドとペアにする (PPlain and PMMX)

例1.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:

ここでは完全なペアリングが達成できており、ループは今や3クロックサイクルしかかからない。 ループカウンタを1増やす(例1.4のように)か、4増やす(例1.5のように)かは趣味の問題である。ループのタイミングに違いはない。

一つの操作の最後を次の操作の始めとオーバーラップさせる (PPlain and PMMX)

例1.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 の間に置く。

ループを伸ばす (PPlain and PMMX)

例1.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クロックサイクルかかる。

AGIを除くためにループを再構成する (PPlain and PMMX)

例1.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回を超えて伸ばす (PPlain and PMMX)

ループを過剰に伸ばすことの欠点は次の通りである:

1. Rを伸ばす回数とすると、 N MODULO R を計算して、 N MODULO R 回の操作をメインループの前か後で行い、残りの操作の数をRで割り切れるようにする必要がある。これは余分なコードと予測しにくい分岐を要する。ループ本体ももちろん大きくなる。
2. コード片は普通、初めて実行されるときに非常に多くの時間がかかり、初回実行のペナルティはコードが多くなればなるほど、特にNが小さいとき、大きくなる。
3. 過剰なコードサイズはコードキャッシュの利用率を下げる。

32ビットレジスタで、複数の8または16ビットオペランドを同時に扱う

次の例はバイトの配列のすべての要素に2を加える。

例1.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:

各バイトの最上位ビットをマスクして、加算時に各バイトから次のバイトへのキャリーがあるかもしれないのを避けていることに注意してほしい。私は最上位ビットを戻すのに、ADDの代わりにXORを使って、キャリーを避けている。 ADD ESI,4 命令は、例1.4のようにループカウンタを添字に使うようにすれば避けることができただろう。しかしながら、これだとループ本体の命令数が奇数になるので、ペアにならない命令ができてループは依然として5クロックかかるだろう。分岐命令をペアにしないと、分岐が予測ミスしたときに最後の操作の後で1クロック節約できるが、配列の最後へのポインタを設定し、-Nを計算するための準備のコードで余分なクロックサイクルを消費しなければならないため、二つの方法はちょうど同じ速さになる。ここで示した方法は最も簡単で最も短い。

次の例は、最初の0のバイトを探すことで、0で終わる文字列の長さを調べる。これは REP SCASB を使うより速い。

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を探す方法を使えばよい。

MMX操作を含むループ (PMMX)

配列のすべてのバイトに2を足す問題に戻ると、次のようにMMX命令の利点を生かすことができる。

例1.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ストールが起きる。

ループのオーバーヘッドは考慮に値するので、ループを伸ばしたい。

例1.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命令を使うことには高いペナルティがあるので、例1.9のように32ビットレジスタを使いたい状況は依然としてあるだろう。

浮動小数点命令を含むループ (PPlain and PMMX)

次のC言語のコードを考えてみよう。

  int i, n;  double * X;  double * Y;  double DA;
  for (i=0; i<n; i++)  Y[i] = Y[i] - DA * X[i];

例1.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:

浮動小数点操作のインターリーブは、ここでは完全にうまくいっている。FMULとFSUBRの間の2クロックのストールを、前の結果のFSTPが埋めている。FSUBRとFSTPの間の3クロックのストールを、ループのオーバーヘッドと次の操作の最初の2命令が埋めている。添字が増加した後の最初のクロックサイクルで、添字に依存しない唯一のパラメタを読むことで、AGIストールを避けている。

この解は操作当たり6クロックサイクルかかり、インテルの公表しているループを伸ばした解より良い!

浮動小数点ループを伸ばす (PPlain and PMMX)

例1.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は、次の実行の最初の命令である。ここでは、例1.9と例1.10のように、配列の終わりを読み過ぎて、最後に余分な値を捨てるという解答をするのは、たいへん魅力的だろう。しかし、配列の後のメモリ位置が正当な浮動小数点数を含んでいない場合、余分な値を読むことで、デノーマルオペランド例外が発生するため、浮動小数点ループでは、これは勧められない。これを避けるためには、少なくとももう一つの操作をメインループの後でしなければならない。

伸ばしたループの外でする操作の数は、通常は、Nを操作の数、Rを伸ばす数として、 N MODULO R になるだろう。しかし巻き込んだループの場合は、上で述べた理由のために、もう一回、つまり (N-1) MODULO R + 1 回しなければならない。

通常は、メインループの前で余分な操作をするほうが望ましいだろうが、ここでは二つの理由によって、後でしなければならない。一つの理由は、巻き込みで残されたオペランドのめんどうを見ることである。もう一つの理由は、Rが2の冪でない場合、余分な操作の回数を計算するには、Rでの除算が必要であり、除算は時間がかかるからである。ループの後で余分な操作をすると、除算が節約できる。

次の問題は、どのようにループカウンタにバイアスをつけて、正しいときに符号が変わるようにするかを計算することと、このバイアスを補償するようにベースポインタを調整することである。最後の問題は、すべてのNの値について、巻き込みで残った操作が、必ず正しく扱えるようにしなければならないことである。

1〜3回の操作をする結びのコードは、別のループとして実装してもよかったが、分岐予測ミスのコストが追加されるだろうから、上の解のほうが速い。 3回伸ばすのがどんなに難しいかやってみせることで怖がらせてしまったので、今度は4回伸ばすとずっと簡単であることを見せよう。

例1.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回伸ばすべきだと言っておこう。

例2.3

        MOV     ECX, [N]
        MOV     ESI, [A]
        MOV     EDI, [B]
        LEA     ESI, [ESI+4*ECX]          ; 配列Aの最後を指す
        LEA     EDI, [EDI+4*ECX]          ; 配列Bの最後を指す
        NEG     ECX                       ; -N
        JZ      SHORT L2
ALIGN   16
L1:     MOV     EAX, [ESI+4*ECX]          ; len=3, p2rESIrECXwEAX
        NEG     EAX                       ; len=2, p01rwEAXwF
        MOV     [EDI+4*ECX], EAX          ; len=3, p4rEAX, p3rEDIrECX
        INC     ECX                       ; len=1, p01rwECXwF
        JNZ     L1                        ; len=2, p1rF
L2:

デコードについて。ループ中には二つのデコード・グループがあるのでデコードには2クロックかかる。

命令取り込みについて。ループは少なくとも16バイトの数よりも1クロックサイクル余計にかかる。この場合はコードが11バイトしかないので、すべてを1つのifetchブロックに入れることが可能である。ループの入り口を16バイト境界にアラインすることによって16バイトブロックが1つを超えないようにし、命令の取り込みを2クロックで可能にした。

レジスタ・リード・ストールについて。ESIとEDIはループ中では読み出されるが、変化しない。従ってこれは常置レジスタからの読み出しと数えられる。しかし同じ三つ組にはない。レジスタEAX, ECXとフラグはループ中で変化させられ、書き戻される前に読まれる。従って常置レジスタからの読み出しにはならない。結論として、レジスタ・リード・ストールは存在しない。

実行について。

port 0 または 1: 2μ-OPS
port 1: 1μ-OPS
port 2: 1μ-OPS
port 3: 1μ-OPS
port 4: 1μ-OPS

従って実行時間は1.5クロックである。

リタイアメントについて。6μ-OPSだから2クロックである。

結論は、このループは一回当たり2クロックサイクルかかる。

ESIとEDIの代わりに絶対番地を用いれば、ループは3クロックかかる。というのは、一つの16バイト・ブロックに収まらなくなるからである。

ループのアンロール (PPro, PII and PIII)

例2.7

        MOV     ESI, [A]         ; バイト配列の番地
        MOV     ECX, [N]         ; バイト配列の要素数
        JECXZ   L2
ALIGN   16
        DB   7  DUP (90H)        ; アラインメントの調整用の七つのNOP

 L1:    MOV     EAX, [ESI]       ; 4バイトの読み出し
        MOV     EBX, EAX         ; EBXにコピーする
        AND     EAX, 7F7F7F7FH   ; EAXの各々のバイトの下位7ビットを得る
        XOR     EBX, EAX         ; 各々のバイトの上位1ビットを得る
        ADD     EAX, 02020202H   ; 四つの全てのバイトに望まれる値を加算する
        XOR     EBX, EAX         ; ビットを再び結合する
        MOV     [ESI], EBX       ; 結果を書き込む
        ADD     ESI, 4           ; ポインタを増やす
        SUB     ECX, 4           ; ループカウンタを減らす
        JA      L1               ; ループする
L2:

このループは理想的には毎回4クロックかかるはずだが、依存の連鎖と難しいリオーダのためにいくぶん余計にかかる。PIIとPIIIではMMXレジスタを使用すれば同じことをより効率的に行えるだろう。

次の例はゼロで終わる文字列を、最初のバイトがゼロであることを探すことによって見つけるものである。これはREPNE SCASBを使うよりも速い。

_strlen PROC    NEAR
        PUSH    EBX
        MOV     EAX,[ESP+8]            ; 文字列のポインタを得る
        LEA     EDX,[EAX+3]            ; 最後に使われるポインタ+3
L1:     MOV     EBX,[EAX]              ; 最初の4バイトを読み出す
        ADD     EAX,4                  ; ポインタを増やす
        LEA     ECX,[EBX-01010101H]    ; 各々のバイトから1を減算する
        NOT     EBX                    ; すべてのバイトを反転する
        AND     ECX,EBX                ; これら二つのANDを取る
        AND     ECX,80808080H          ; すべての符号を調べる
        JZ      L1                     ; ゼロのバイトがなければループを続ける
        MOV     EBX,ECX
        SHR     EBX,16
        TEST    ECX,00008080H          ; 最初の2バイトを調べる
        CMOVZ   ECX,EBX                ; 最初の2バイトがゼロでなければ、右シフトする
        LEA     EBX,[EAX+2]
        CMOVZ   EAX,EBX
        SHL     CL,1                   ; 分岐を避けるためにキャリーフラグを使う
        SBB     EAX,EDX                ; 長さを計算する
        POP     EBX
        RET
_strlen ENDP

このループは毎回4バイトを調べ、3クロックずつかかる。文字列はもちろん4でアラインされていなければならない。コードは文字列の最後を超えて読むかもしれないので、文字列はセグメントの最後に置くべきでない。

例2.9

_strlen PROC    NEAR
        PUSH    EBX
        MOV     EAX,[ESP+8]
        LEA     EDX,[EAX+7]
        PXOR    MM0,MM0
L1:     MOVQ    MM1,[EAX]        ; len=3 p2rEAXwMM1
        ADD     EAX,8            ; len=3 p01rEAX
        PCMPEQB MM1,MM0          ; len=3 p01rMM0rMM1
        MOVD    EBX,MM1          ; len=3 p01rMM1wEBX
        PSRLQ   MM1,32           ; len=4 p1rMM1
        MOVD    ECX,MM1          ; len=3 p01rMM1wECX
        OR      ECX,EBX          ; len=2 p01rECXrEBXwF
        JZ      L1               ; len=2 p1rF
        MOVD    ECX,MM1
        TEST    EBX,EBX
        CMOVZ   EBX,ECX
        LEA     ECX,[EAX+4]
        CMOVZ   EAX,ECX
        MOV     ECX,EBX
        SHR     ECX,16
        TEST    BX,BX
        CMOVZ   EBX,ECX
        LEA     ECX,[EAX+2]
        CMOVZ   EAX,ECX
        SHR     BL,1
        SBB     EAX,EDX
        EMMS
        POP     EBX
        RET
_strlen ENDP

浮動小数点命令を含むループ (PPro, PII and PIII)

次のC言語のコードを考えよう。

  int i, n;  double * X;  double * Y;  double DA;
  for (i=0; i<n; i++)  Y[i] = Y[i] - DA * X[i];

例2.10

DSIZE   = 8                      ; データサイズ (4 または 8)
        MOV     ECX, [N]         ; 要素数
        MOV     ESI, [X]         ; Xへのポインタ
        MOV     EDI, [Y]         ; Yへのポインタ
        JECXZ   L2               ; Nが0かどうか調べる
        FLD     DSIZE PTR [DA]   ; ループの外でDAを読み出す
ALIGN   16
        DB    2 DUP (90H)        ; アラインメントのための二つのNOP
L1:     FLD     DSIZE PTR [ESI]  ; len=3 p2rESIwST0
        ADD     ESI,DSIZE        ; len=3 p01rESI
        FMUL    ST,ST(1)         ; len=2 p0rST0rST1
        FSUBR   DSIZE PTR [EDI]  ; len=3 p2rEDI, p0rST0
        FSTP    DSIZE PTR [EDI]  ; len=3 p4rST0, p3rEDI
        ADD     EDI,DSIZE        ; len=3 p01rEDI
        DEC     ECX              ; len=1 p01rECXwF
        JNZ     L1               ; len=2 p1rF
        FSTP    ST               ; DAを捨てる 
L2:

例2.11

DSIZE   = 8                                ; データサイズ (4 または 8)
        MOV     ECX, [N]                   ; 要素数
        MOV     ESI, [X]                   ; Xへのポインタ
        MOV     EDI, [Y]                   ; Yへのポインタ
        LEA     ESI, [ESI+DSIZE*ECX]       ; 配列の最後へのポインタ
        LEA     EDI, [EDI+DSIZE*ECX]       ; 配列の最後へのポインタ
        NEG     ECX                        ; -N
        JZ      SHORT L2                   ; Nが0かどうか調べる
        FLD     DSIZE PTR [DA]             ; ループの外でDAを調べる
ALIGN   16
L1:     FLD     DSIZE PTR [ESI+DSIZE*ECX]  ; len=3 p2rESIrECXwST0
        FMUL    ST,ST(1)                   ; len=2 p0rST0rST1
        FSUBR   DSIZE PTR [EDI+DSIZE*ECX]  ; len=3 p2rEDIrECX, p0rST0
        FSTP    DSIZE PTR [EDI+DSIZE*ECX]  ; len=3 p4rST0, p3rEDIrECX
        INC     ECX                        ; len=1 p01rECXwF
        JNZ     L1                         ; len=2 p1rF
        FSTP    ST                         ; DAを捨てる
L2:

26. 問題となりやすい命令

26.1 XCHG (すべてのプロセッサ)

REP MOVSDとREP STOSDは繰り返し回数がさほど小さくなければ大変速い。できればいつもDWORDを使うようにし、転送元と転送先が8で確実にアラインされているようにしなさい。

26.5 整数乗算命令 (すべてのプロセッサ)

a.古い8087プロセッサは、必ずコプロセッサが命令を受け取れるようにするため、すべての浮動小数点命令の前にWAIT命令を要求する。 b.WAIT命令は、浮動小数点ユニットと整数ユニットの間のメモリアクセスを調整するために使われる。例として

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が必要である。

FCOMI命令のないプロセッサでは、浮動小数点比較をする普通のやり方はこうである。

    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 は、PPlainとPMMXではペアにできないので使ってはいけない。

PPlainとPMMXでは、FNSTSW命令2クロックかかるが、浮動小数点命令の後では4クロック遅れる。おそらくステータスワードがパイプラインからリアイアするのを待っているからだろう。この遅延はステータスワードを変えられないFNOPの後でさえ起きる。整数命令の後ではそうではない。このFCOMからFNSTSWまでの遅延を整数命令で埋められるなら、整数命令とFNSTSW命令は4クロックしかかからない。FCOMの直後にペアにされたFXCHはFNSTSWを遅れさせない。不完全なペアリングの時でさえそうである。

    FCOM                  ; 1クロック
    FXCH                  ; 1〜2クロック (不完全なペアリング)
    INC DWORD PTR [EBX]   ; 3〜5クロック
    FNSTSW AX             ; 6〜7クロック

ここで、FTST命令はペアにできないので、FTST命令の代わりにFCOM命令を使いたいと思うかもしれない。FNSTSWの中にNが含まれていることを思い出して欲しい。FSTSW(N無し)は、さらに遅延を大きくするWAITプリフィックスを持っている。

    FISTP QWORD PTR [TEMP]
    FILD  QWORD PTR [TEMP]

|N| < 2⁷-1の場合は単精度を使える。

    MOV     EAX, [N]
    SHL     EAX, 23
    ADD     EAX, 3F800000H
    MOV     DWORD PTR [TEMP], EAX
    FLD     DWORD PTR [TEMP]

|N| < 2¹⁰-1の場合は倍精度を使える。

    MOV     EAX, [N]
    SHL     EAX, 20
    ADD     EAX, 3FF00000H
    MOV     DWORD PTR [TEMP], 0
    MOV     DWORD PTR [TEMP+4], EAX
    FLD     QWORD PTR [TEMP]

|N| < 2¹⁴-1の場合は倍々精度を使える。

    MOV     EAX, [N]
    ADD     EAX, 00003FFFH
    MOV     DWORD PTR [TEMP],   0
    MOV     DWORD PTR [TEMP+4], 80000000H
    MOV     DWORD PTR [TEMP+8], EAX
    FLD     TBYTE PTR [TEMP]

FSCALEはしばしばべき乗関数の計算に使われる。次のコードは遅いFRNDINT命令とFSCALE命令を用いないべき乗関数を示している。

; extern "C" long double _cdecl exp (double x);
_exp    PROC    NEAR
PUBLIC  _exp
        FLDL2E
        FLD     QWORD PTR [ESP+4]             ; x
        FMUL                                  ; z = x*log2(e)
        FIST    DWORD PTR [ESP+4]             ; round(z)
        SUB     ESP, 12
        MOV     DWORD PTR [ESP], 0
        MOV     DWORD PTR [ESP+4], 80000000H
        FISUB   DWORD PTR [ESP+16]            ; z - round(z)
        MOV     EAX, [ESP+16]
        ADD     EAX,3FFFH
        MOV     [ESP+8],EAX
        JLE     SHORT UNDERFLOW
        CMP     EAX,8000H
        JGE     SHORT OVERFLOW
        F2XM1
        FLD1
        FADD                                  ; 2^(z-round(z))
        FLD     TBYTE PTR [ESP]               ; 2^(round(z))
        ADD     ESP,12
        FMUL                                  ; 2^z = e^x
        RET

UNDERFLOW: 
        FSTP    ST
        FLDZ                                  ; 0を返す
        ADD     ESP,12        
        RET

OVERFLOW:
        PUSH    07F800000H                    ; 無限大
        FSTP    ST
        FLD     DWORD PTR [ESP]               ; 無限大を返す
        ADD     ESP,16
        RET

_exp    ENDP

    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  ; (結果はサインフラグ)

次のコードは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は古い80287プロセッサとの互換性を保つためだけに必要
        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は古い80287プロセッサとの互換性を保つためだけに必要
        MOV     ECX, DWORD PTR [TEMP+4]
        SHR     ECX,20
        SUB     ECX,3FFH
        TEST    EAX,EAX       ; ゼロフラグのクリア
BS2:

CまたはC++のコードがコンパイルされると、浮動小数点数を整数に変換するのは切り捨てで行うが、他の浮動小数点演算では丸めを行うので、FLDCW命令をたくさん生成する。アセンブリ言語に変換された後で、可能な場所では切り捨ての代わりに丸めを使ったり、中で切り捨てが必要なループからFLDCWを外に移動したりすることで、コードを改良できる。

27. 特別な話題

27.1 LEA命令 (すべてのプロセッサ)

    LEA EAX,[EBX+8*ECX-1000]

    MOV EAX,ECX / SHL EAX,3 / ADD EAX,EBX / SUB EAX,1000

しかしながら、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と書くことで、命令のサイズを縮小できる。後者のコードはPPlainとPMMXでAGIの遅れがない。もしたまたま値が0であるような(ループの後のループカウンタのような)レジスタがあれば、それをベースレジスタとして使ってコードサイズを縮小することもできる。

    LEA EAX,[EBX*4]     ; 7バイト
    LEA EAX,[ECX+EBX*4] ; 3バイト

定数による除算 (すべてのプロセッサ)

        SHR     EAX, N

        CDQ
        AND     EDX, (1 SHL N) -1  ; または  SHR EDX, 32-N
        ADD     EAX, EDX
        SAR     EAX, N

定数による除算は逆数を掛けることでできる。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命令のしているのと同じものを与える(この方法を開発したTerje Mathisenに感謝する)。

  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 = 2b)
  結果 = 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 = 234 / 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の小さい値を使う理由はいくつかある。

• r = 32 とすることで、最後の SHR EDX,b を避けられる。
• r = 16+b とすることで、64ビットではなく32ビットの結果を出す乗算命令を使うことができる。これはEDXレジスタを解放する。

    IMUL EAX,0CCCDh / SHR EAX,18
    

• INC EAX 命令を避けるために場合Bではなく場合Cになるようなrの値を選べる。

この場合のxの最大値は少なくとも2^r-bであり、時にはもっと大きい。コードが正しく動くxの最大値をちょうど知りたいなら、系統的なテストをしなければならない。

        FILD    [B1]
        FILD    [B2]
        MOV     EAX, [A1]
        MOV     EBX, [A2]
        CDQ
        FDIV
        DIV     EBX
        FISTP   [B]
        MOV     [A], EAX

高速除算のために逆数命令を使う (PIII)

        MOVAPS  XMM1, [DIVISORS]         ; 除数を読み出す
        RCPPS   XMM0, XMM1               ; 逆数の近似解
        MULPS   XMM1, XMM0               ; Newton-Raphson法
        MULPS   XMM1, XMM0
        ADDPS   XMM0, XMM0
        SUBPS   XMM0, XMM1
        MULPS   XMM0, [DIVIDENDS]        ; XMM0に解が求まる

この方法を整数の除算に用いたいなら、丸め誤差を調べなければならない。次のコードは四つの切り捨て除算をパックド形式の整数で行い、約42クロックサイクルかかる。これは、0 <= 被除数 < 7FFFFH かつ 0 < 除数 <= 7FFFFHの時に正確な結果を与える。

        MOVQ MM1, [DIVISORS]      ; 四つの除数を読み出す
        MOVQ MM2, [DIVIDENDS]     ; 四つの被除数を読み出す
        PUNPCKHWD MM4, MM1        ; 除数をDWORDにアンパックする
        PSRAD MM4, 16
        PUNPCKLWD MM3, MM1
        PSRAD MM3, 16
        CVTPI2PS XMM1, MM4        ; 除数を単精度浮動小数点数に変換(上位2オペランド)
        MOVLHPS XMM1, XMM1
        CVTPI2PS XMM1, MM3        ; 除数を単精度浮動小数点数に変換(下位2オペランド)
        PUNPCKHWD MM4, MM2        ; 被除数をDWORDにアンパックする
        PSRAD MM4, 16
        PUNPCKLWD MM3, MM2
        PSRAD MM3, 16
        CVTPI2PS XMM2, MM4        ; 被除数を単精度浮動小数点数に変換(上位2オペランド)
        MOVLHPS XMM2, XMM2
        CVTPI2PS XMM2, MM3        ; 被除数を単精度浮動小数点数に変換(下位2オペランド)
        RCPPS XMM0, XMM1          ; 除数の逆数の近似解
        MULPS XMM1, XMM0          ; Newton-Raphson法による精度向上
        PCMPEQW MM4, MM4          ; 合間に整数1を四つ作る
        PSRLW MM4, 15
        MULPS XMM1, XMM0
        ADDPS XMM0, XMM0
        SUBPS XMM0, XMM1          ; 23ビット精度の除数の逆数
        MULPS XMM0, XMM2          ; 被除数で乗算
        CVTTPS2PI MM0, XMM0       ; 下位二つの結果の切り捨て数
        MOVHLPS XMM0, XMM0
        CVTTPS2PI MM3, XMM0       ; 上位二つの結果の切り捨て数
        PACKSSDW MM0, MM3         ; 四つの結果をMM0にパックする
        MOVQ MM3, MM1             ; 結果を除数で乗算する
        PMULLW MM3, MM0           ; 丸め誤差をチェックする
        PADDSW MM0, MM4           ; 後の減算の補償として1を加算
        PADDSW MM3, MM1           ; 除数を加算。これは被除数より大きくなければならない
        PCMPGTW MM3, MM2          ; 小さすぎないか調べる
        PADDSW MM0, MM3           ; 小さすぎなければ1を加算
        MOVQ [QUOTIENTS], MM0     ; 四つの結果を書き込む

除算を避ける (すべてのプロセッサ)

A/B + C/D は (A*D + C*B) / (B*D) に書き換えられる。

もし整数除算を使っているなら、式を書き換えると丸め誤差が異なることを知っているべきである。

一つのレジスタを解放する最も速い方法は、FSTP ST である。二つのレジスタを解放する最も速い方法は、PPlainとPMMXにおいてはFCOMPPである。PPro, PIIとPIIIではFCOMPPまたは二回のFSTP STのどちらを使ってもよい。デコードの流れにぴったりくる方を選ぶ。

FFREEを使うことは勧められない。

PIIとPIIIではそのようなペナルティはない。EMMSの後の遅延は、最初の浮動小数点命令の前に整数命令を挟むことで隠せる。

        FISTP   DWORD PTR [TEMP]
        MOV     EAX, [TEMP]

    FLD QWORD PTR [ESI] / FSTP QWORD PTR [EDI]
    を変更して
    MOV EAX,[ESI] / MOV EBX,[ESI+4] / MOV [EDI],EAX / MOV [EDI+4],EBX
    にする。

浮動小数点値がゼロかどうかテスト

    FLD DWORD PTR [EBX] / FTST / FNSTSW AX / AND AH,40H / JNZ IsZero

    MOV EAX,[EBX] / ADD EAX,EAX / JZ IsZero

浮動小数点数が倍精度(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        ; 符号つき比較

整数の乗算 (PPlain and PMMX)

PMMXでは、MMX乗算命令は整数乗算より速く、クロックサイクルあたり1回の乗算のスループットでパイプライン動作できるので、16ビット精度でよいのなら、これがPMMXで高速に乗算を行う最良の解決策かもしれない。

整数乗算は、PPro, PIIとPIIIでは浮動小数点乗算より速い。

整数除算 (PPlain and PMMX)

PPlainとPMMXでは浮動小数点命令は、転送先がキャッシュになければ、8バイトを一度に移動するにはより速い。

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においてのみ、そして転送先が一次キャッシュにないときのみ、有利であることに注意せよ。FLDとFSTP(Iを除く)を任意のビットパターンで使うことはできない。というのはデノーマル数を扱う際には遅くなり、あるビットパターンは変化しないという保証がないからである。

MMXプロセッサでは、転送先がキャッシュになければ、8バイトを一度に移動するにはMMX命令を使うほうが速い。

TOP:    MOVQ    MM0,[ESI]
        MOVQ    [EDI],MM0
        ADD     ESI,8
        ADD     EDI,8
        DEC     ECX
        JNZ     TOP

キャッシュミスが予期されるなら、このループをアンロールしたりさらに最適化したりする必要は全くない。なぜなら、ここでは命令の実行ではなくメモリアクセスがボトルネックだからである。

プロテクトモードで動作するオペレーティングシステム内で書き換えの許可を得るには、特別なシステムコールが必要である。16ビットWindowsではChangeSelector、32ビットWindowsではVirtualProtectとFlushInstructionCacheを呼ぶか、コードをデータセグメントに入れなければならない。

自己改変コードは良いプログラミング習慣とは考えられない。しかし、かなりの速度が稼げるならば、理由を正当化できるかもしれない。

; CPUID命令がわからないアセンブラのためのマクロ定義
CPUID   MACRO
        DB      0FH, 0A2H
ENDM

; C++ prototype:
; extern "C" long int DetectProcessor (void);

; return value: 
; bits 8-11 = ファミリー(PPlainとPMMXは5, PPro, PIIとPIIIは6)
; bit  0 = 浮動小数点命令サポート
; bit 15 = 条件移動命令とFCOMI命令サポート
; bit 23 = MMX命令サポート
; bit 25 = XMM命令サポート

_DetectProcessor PROC NEAR
PUBLIC  _DetectProcessor
        PUSH    EBX
        PUSH    ESI
        PUSH    EDI
        PUSH    EBP
        ; マイクロプロセッサがCPUID命令をサポートしているか調べる
        PUSHFD
        POP     EAX
        MOV     EBX, EAX
        XOR     EAX, 1 SHL 21    ; CPUIDのビットが変えられるか調べる
        PUSH    EAX
        POPFD
        PUSHFD
        POP     EAX
        XOR     EAX, EBX
        AND     EAX, 1 SHL 21
        JZ      SHORT DPEND      ; CPUID命令はサポートされていない
        XOR     EAX, EAX
        CPUID                    ; CPUID機能の結果を得る
        TEST    EAX, EAX
        JZ      SHORT DPEND      ; CPUID機能1はサポートされていない
        MOV     EAX, 1
        CPUID                    ; ファミリーと特徴を得る
        AND     EAX, 000000F00H  ; ファミリー
        AND     EDX, 0FFFFF0FFH  ; 特徴フラグ
        OR      EAX, EDX         ; ビットを結合
DPEND:  POP     EBP
        POP     EDI
        POP     ESI
        POP     EBX
        RET
_DetectProcessor ENDP

いくつかのオペレーティングシステムはXMM命令を許可していないことに気をつけなさい。オペレーティングシステムがXMM命令をサポートしているかどうか調べる方法についての情報はインテルのアプリケーションノートAP-900 "SSE拡張命令とオペレーティングシステムの見分け方 "で見つけられる。マイクロプロセッサの証明についての更なる情報はインテルのアプリケーションノートAP-485 "インテルプロセッサの証明とCPUID命令" で見つけられる。

28. 命令のタイミング (PPlain and PMMX)

28.1 整数命令 (PPlain and PMMX)

クロックサイクル:
数字は最小値である。キャッシュミスやミスアラインメントや例外により、クロックカウントはだいぶ増大する。

ペア可能性:
u=Uパイプでペアにできる, v=Vパイプでペアにできる, uv=どちらのパイプでもペアにできる, np=ペアにできない

オペコード             オペランド          クロックサイクル    ペア可能性
-------------------------------------------------------------------------
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は、ここでは浮動小数点命令と考える)

オペコード           オペランド クロックサイクル ペア可能性     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 s)      np             2      2
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                         65-100 r)      np             2      2
FSINCOS                           89-112 r)      np             2      2
F2XM1                              53-59 r)      np             2      2
FYL2X                                103 r)      np             2      2
FYL2XP1                              105 r)      np             2      2
FPTAN                            120-143 r)      np            36 o)   0
FPATAN                           112-134 r)      np             2      2

FNOP                                   1         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
-----------------------------------------------------------------------------

MMX命令のタイミングのリストは不要である。MMX乗算命令が3クロックかかる以外はすべて1クロックサイクルだからである。MMX乗算命令はオーバーラップしてパイプライン動作可能で、クロックサイクルあたり1乗算のスループットが得られる。

EMMS命令は1クロックサイクルしかかからないが、EMMSの後の最初の浮動小数点命令は約58クロック余分にかかるし、浮動小数点命令の後の最初のMMX命令は約38クロック余分にかかる。PMMXでは、EMMS命令の後のMMX命令にはペナルティはないが、PIIとPIIIでは小さなペナルティの可能性がある。

MMX演算ユニットはパイプライン中でロードユニットの1ステップ後にあるので、MMX命令でメモリオペランドを使うことにペナルティはない。しかし、MMXレジスタからメモリまたは32ビットレジスタにデータを格納するときはペナルティがある。データは1クロック先立って準備されていなければならない。これは浮動小数点ストア命令と同様である。

29. 命令タイミングとμ-OPSへの分解 (PPro, PII and PIII)

μ-OPS:
各々の実行ポートで命令が生成するμ-OPSの数
p0: ポート0: ALU, など
p1: ポート1: ALU, ジャンプ
p01: ポート0とポート1のうち、先に空になった方へ行ける命令
p2: ポート2: データの読み出し, など
p3: ポート3: データ書き込みのための番地生成
p4: ポート4: データ書き込み

遅延:
依存の連鎖中にある時、命令が生成する遅延。(これは実行ユニット中で費やされる時間とは違う。値は、それが正確に測定できないため、特にメモリオペランドがある状況では不正確である。)数は最小の値である。キャッシュミス、ミスアラインメント、そして例外はクロック数をかなり増大させる。浮動小数点のオペランドはノーマル数を仮定している。デノーマル数、NANと無限大は50〜150クロック増える。但し、XMM移動、シャッフルと論理命令を除く。

スループット:
いくつかの命令の最大のスループットは同じ種類である。例えば、FMUL命令のスループット1/2は、新しいFMUL命令が2クロック毎に発行できることを意味する。

オペコード           オペランド        μ-OPS             遅延     スループット
                                  p0 p1 p01 p2 p3 p4
-------------------------------------------------------------------------------
NOP                                     1                                    
MOV                  r,r/i              1                                    
MOV                  r,m                    1                                
MOV                  m,r/i                     1  1                          
MOV                  r,sr               1                                    
MOV                  m,sr               1      1  1                          
MOV                  sr,r         8  -  -                 5                  
MOV                  sr,m         7  -  -   1             8                  
MOVSX MOVZX          r,r                1                                    
MOVSX MOVZX          r,m                       1                             
CMOVcc               r,r          1     1                                    
CMOVcc               r,m          1     1   1                                
XCHG                 r,r                3                                    
XCHG                 r,m                4   1   1   1     high b)            
XLAT                                    1   1                                
PUSH                 r/i                1       1   1                        
POP                  r                  1   1                                
POP (E)SP                               2   1                                
PUSH                 m                  1   1   1   1                        
POP                  m                  5   1   1   1                        
PUSH                 sr                 2       1   1                        
POP                  sr                 8   1                                
PUSHF(D)                          3     11      1   1                        
POPF(D)                           10    6   1                                
PUSHA(D)                                2       8   8                        
POPA(D)                                 2   8                                
LAHF SAHF                               1                                    
LEA r,m                           1                       1 c)               
LDS LES LFS LGS LSS  m                  8   3                                
ADD SUB AND OR XOR   r,r/i              1                                    
ADD SUB AND OR XOR   r,m                1   1                                
ADD SUB AND OR XOR   m,r/i              1   1   1   1                        
ADC SBB              r,r/i              2                                    
ADC SBB              r,m                2   1                                
ADC SBB              m,r/i              3   1   1   1                        
CMP TEST             r,r/i              1                                    
CMP TEST             m,r/i              1   1                                
INC DEC NEG NOT      r                  1                                    
INC DEC NEG NOT      m                  1   1   1   1                        
AAS DAA DAS                          1                                       
AAD                               1     2                 4                  
AAM                               1  1  2                 15                 
MUL IMUL             r,(r),(i)    1                       4        1/1       
MUL IMUL             (r),m        1         1             4        1/1       
DIV IDIV             r8           2     1                 19       1/12      
DIV IDIV             r16          3     1                 23       1/21      
DIV IDIV             r32          3     1                 39       1/37      
DIV IDIV             m8           2     1   1             19       1/12      
DIV IDIV             m16          2     1   1             23       1/21      
DIV IDIV             m32          2     1   1             39       1/37      
CBW CWDE                                1                                    
CWD CDQ                           1                                          
SHR SHL SAR ROR ROL  r,i/CL       1                                          
SHR SHL SAR ROR ROL  m,i/CL       1         1   1   1                        
RCR RCL              r,1          1     1                                    
RCR RCL              r8,i/CL      4     4                                    
RCR RCL              r16/32,i/CL  3     3                                    
RCR RCL              m,1          1     2   1   1   1                        
RCR RCL              m8,i/CL      4     3   1   1   1                        
RCR RCL              m16/32,i/CL  4     2   1   1   1                        
SHLD SHRD            r,r,i/CL     2                                          
SHLD SHRD            m,r,i/CL     2     1   1   1   1                        
BT                   r,r/i              1                                    
BT                   m,r/i        1     6   1                                
BTR BTS BTC          r,r/i              1                                    
BTR BTS BTC          m,r/i        1     6   1   1   1                        
BSF BSR              r,r             1  1                                    
BSF BSR              r,m             1  1   1                                
SETcc                r                  1                                    
SETcc                m                  1       1   1                        
JMP                  short/near      1                             1/2       
JMP                  far          21 -  -   1                                
JMP                  r               1                             1/2       
JMP                  m(near)         1      1                      1/2       
JMP                  m(far)       21 -  -   2                                
conditional jump     short/near      1                             1/2       
CALL                 near            1  1       1   1              1/2       
CALL                 far          28 -  -   1   2   2                        
CALL                 r               1  2       1   1              1/2       
CALL                 m(near)         1  4   1   1   1              1/2       
CALL                 m (far)      28 -  -   2   2   2                        
RETN                                 1  2   1                      1/2       
RETN                 i               1  3   1                      1/2       
RETF                              23 -  -   3                                
RETF                 i            23 -  -   3                                
J(E)CXZ              short           1  1                                    
LOOP                 short        2  1  8                                    
LOOP(N)E             short        2  1  8                                    
ENTER                i,0                12      1   1                        
ENTER                a,b          ca. 18+4b     b-1 2b                       
LEAVE                                   2   1                                
BOUND                r,m          7     6   2                                
CLC STC CMC                             1                                    
CLD STD                                 4                                    
CLI                               9  -  -                                    
STI                               17 -  -                                    
INTO                                    5                                    
LODS                                        2                                
REP LODS                                10+6n                                
STOS                                        1   1   1                        
REP STOS                                ca. 5n a)   -                        
MOVS                                    1   3   1   1                        
REP MOVS                                ca. 6n a)   -                        
SCAS                                    1   2                                
REP(N)E SCAS                            12+7n                                
CMPS                                    4   2                                
REP(N)E CMPS                            12+9n                                
BSWAP                             1     1                                    
CPUID                             23-48                                      
RDTSC                             31 -  -                                    
IN                                18 -  -                 >300               
OUT                               18 -  -                 >300               
PREFETCHNTA  d)      m                      1                                
PREFETCHT0  d)       m                      1                                
PREFETCHT1  d)       m                      1                                
PREFETCHT2  d)       m                      1                                
SFENCE  d)                                      1   1              1/6       
-------------------------------------------------------------------------------

オペコード           オペランド        μ-OPS             遅延     スループット
                                  p0 p1 p01 p2 p3 p4
-------------------------------------------------------------------------------
FLD                  r            1                                           
FLD                  m32/64                 1             1                   
FLD                  m80          2         2                                 
FBLD                 m80          38        2                                 
FST(P)               r            1                                           
FST(P)               m32/m64                   1  1       1                   
FSTP                 m80          2            2  2                           
FBSTP                m80          165          2  2                           
FXCH                 r                                    0        3/1 f)     
FILD                 m            3         1             5                   
FIST(P)              m            2            1  1       5                   
FLDZ                              1                                           
FLD1 FLDPI FLDL2E etc.            2                                           
FCMOVcc              r            2                       2                   
FNSTSW               AX           3                       7                   
FNSTSW               m16          1            1  1                           
FLDCW                m16          1     1   1             10                  
FNSTCW               m16          1            1  1                           
FADD(P) FSUB(R)(P)   r            1                       3        1/1        
FADD(P) FSUB(R)(P)   m            1         1             3-4      1/1        
FMUL(P)              r            1                       5        1/2 g)     
FMUL(P)              m            1         1             5-6      1/2 g)     
FDIV(R)(P)           r            1                       38 h)    1/37       
FDIV(R)(P)           m            1         1             38 h)    1/37       
FABS                              1                                           
FCHS                              3                       2                   
FCOM(P) FUCOM        r            1                       1                   
FCOM(P) FUCOM        m            1         1             1                   
FCOMPP FUCOMPP                    1     1                 1                   
FCOMI(P) FUCOMI(P)   r            1                       1                   
FCOMI(P) FUCOMI(P)   m            1         1             1                   
FIADD FISUB(R)       m            6         1                                 
FIMUL                m            6         1                                 
FIDIV(R)             m            6         1                                 
FICOM(P)             m            6         1                                 
FTST                              1                       1                   
FXAM                              1                       2                   
FPREM                             23                                          
FPREM1                            33                                          
FRNDINT                           30                                          
FSCALE                            56                                          
FXTRACT                           15                                          
FSQRT                             1                       69       e,i)       
FSIN FCOS                         17-97 -                 27-103   e)         
FSINCOS                           18-110                  29-130   e)         
F2XM1                             17-48 -                 66       e)         
FYL2X                             36-54 -                 103      e)         
FYL2XP1                           31-53 -                 98-107   e)         
FPTAN                             21-102                  13-143   e)         
FPATAN                            25-86 -                 44-143   e)         
FNOP                              1                                           
FINCSTP FDECSTP                   1                                           
FFREE                r            1                                           
FFREEP               r            2                                           
FNCLEX                                  3                                     
FNINIT                            13 -  -                                     
FNSAVE                            141   -                                     
FRSTOR                            72 -  -                                     
WAIT                                    2                                     
-------------------------------------------------------------------------------

オペコード           オペランド        μ-OPS             遅延     スループット
                                  p0 p1 p01 p2 p3 p4
-------------------------------------------------------------------------------
MOVD MOVQ            r,r                1                          2/1        
MOVD MOVQ            r64,m32/64             1                      1/1        
MOVD MOVQ            m32/64,r64                1  1                1/1        
PADD PSUB PCMP       r64,r64            1                          1/1        
PADD PSUB PCMP       r64,m64            1   1                      1/1        
PMUL PMADD           r64,r64      1                       3        1/1        
PMUL PMADD           r64,m64      1         1             3        1/1        
PAND PANDN POR,                                                               
PXOR                 r64,r64            1                          2/1        
PAND PANDN POR,                                                               
PXOR                 r64,m64            1   1                      1/1        
PSRA PSRL PSLL       r64,r64/i       1                             1/1        
PSRA PSRL PSLL       r64,m64         1      1                      1/1        
PACK PUNPCK          r64,r64         1                             1/1        
PACK PUNPCK          r64,m64         1      1                      1/1        
EMMS                              11 -  -                 6 k)                
MASKMOVQ  d)         r64,r64            1      1  1       2-8      1/30-1/2   
PMOVMSKB  d)         r32,r64         1                    1        1/1        
MOVNTQ  d)           m64,r64                   1  1                1/30-1/1   
PSHUFW  d)           r64,r64,i       1                    1        1/1        
PSHUFW  d)           r64,m64,i       1      1             2        1/1        
PEXTRW  d)           r32,r64,i       1  1                 2        1/1        
PISRW  d)            r64,r32,i       1                    1        1/1        
PISRW  d)            r64,m16,i       1      1             2        1/1        
PAVGB PAVGW  d)      r64,r64            1                 1        2/1        
PAVGB PAVGW  d)      r64,m64            1   1             2        1/1        
PMINUB PMAXUB,
PMINSW PMAXSW  d)    r64,r64            1                 1        2/1        
PMINUB PMAXUB,
PMINSW PMAXSW  d)    r64,m64            1   1             2        1/1        
PMULHUW  d)          r64,r64      1                       3        1/1        
PMULHUW  d)          r64,m64      1         1             4        1/1        
PSADBW  d)           r64,r64      2     1                 5        1/2        
PSADBW  d)           r64,m64      2     1   1             6        1/2        
-------------------------------------------------------------------------------

オペコード           オペランド        μ-OPS             遅延     スループット
                                  p0 p1 p01 p2 p3 p4
-------------------------------------------------------------------------------
MOVAPS               r128,r128          2                 1        1/1        
MOVAPS               r128,m128              2             2        1/2        
MOVAPS               m128,r128                 2  2       3        1/2        
MOVUPS               r128,m128              4             2        1/4        
MOVUPS               m128,r128       1         4  4       3        1/4        
MOVSS                r128,r128          1                 1        1/1        
MOVSS                r128,m32           1   1             1        1/1        
MOVSS                m32,r128                  1  1       1        1/1        
MOVHPS MOVLPS        r128,m64           1                 1        1/1        
MOVHPS MOVLPS        m64,r128                  1  1       1        1/1        
MOVLHPS MOVHLPS      r128,r128          1                 1        1/1        
MOVMSKPS             r32,r128     1                       1        1/1        
MOVNTPS              m128,r128                 2  2                1/15-1/2   
CVTPI2PS             r128,r64        2                    3        1/1        
CVTPI2PS             r128,m64        2      1             4        1/2        
CVTPS2PI CVTTPS2PI   r64,r128        2                    3        1/1        
CVTPS2PI             r64,m128        1      2             4        1/1        
CVTSI2SS             r128,r32        2      1             4        1/2        
CVTSI2SS             r128,m32        2      2             5        1/2        
CVTSS2SI CVTTSS2SI   r32,r128        1      1             3        1/1        
CVTSS2SI             r32,m128        1      2             4        1/2        
ADDPS SUBPS          r128,r128       2                    3        1/2        
ADDPS SUBPS          r128,m128       2      2             3        1/2        
ADDSS SUBSS          r128,r128       1                    3        1/1        
ADDSS SUBSS          r128,m32        1      1             3        1/1        
MULPS                r128,r128    2                       4        1/2        
MULPS                r128,m128    2         2             4        1/2        
MULSS                r128,r128    1                       4        1/1        
MULSS                r128,m32     1         1             4        1/1        
DIVPS                r128,r128    2                       48       1/34       
DIVPS                r128,m128    2         2             48       1/34       
DIVSS                r128,r128    1                       18       1/17       
DIVSS                r128,m32     1         1             18       1/17       
ANDPS ANDNPS,
ORPS XORPS           r128,r128       2                    2        1/2        
ANDPS ANDNPS,
ORPS XORPS           r128,m128       2      2             2        1/2        
MAXPS MINPS          r128,r128       2                    3        1/2        
MAXPS MINPS          r128,m128       2      2             3        1/2        
MAXSS MINSS          r128,r128       1                    3        1/1        
MAXSS MINSS          r128,m32        1      1             3        1/1        
CMPccPS              r128,r128       2                    3        1/2        
CMPccPS              r128,m128       2      2             3        1/2        
CMPccSS              r128,r128       1      1             3        1/1        
CMPccSS              r128,m32        1      1             3        1/1        
COMISS UCOMISS       r128,r128       1                    1        1/1        
COMISS UCOMISS       r128,m32        1      1             1        1/1        
SQRTPS               r128,r128    2                       56       1/56       
SQRTPS               r128,m128    2         2             57       1/56       
SQRTSS               r128,r128    2                       30       1/28       
SQRTSS               r128,m32     2         1             31       1/28       
RSQRTPS              r128,r128    2                       2        1/2        
RSQRTPS              r128,m128    2         2             3        1/2        
RSQRTSS              r128,r128    1                       1        1/1        
RSQRTSS              r128,m32     1         1             2        1/1        
RCPPS                r128,r128    2                       2        1/2        
RCPPS                r128,m128    2         2             3        1/2        
RCPSS                r128,r128    1                       1        1/1        
RCPSS                r128,m32     1         1             2        1/1        
SHUFPS               r128,r128,i     2  1                 2        1/2        
SHUFPS               r128,m128,i     2      2             2        1/2        
UNPCKHPS UNPCKLPS    r128,r128       2  2                 3        1/2        
UNPCKHPS UNPCKLPS    r128,m128    2  2                    3        1/2        
LDMXCSR              m32          11 -  -                 15       1/15       
STMXCSR              m32          6  -  -                 7        1/9        
FXSAVE               m4096        116   -                 62                  
FXRSTOR              m4096        89 -  -                 68                  
-------------------------------------------------------------------------------

30. コードの速度のテスト

以下のプログラムはコード片の実行にかかるクロックサイクル数を測るのに便利である。プログラムはテストされるコードを10回実行し、10個のクロックカウントを格納する。PPlainとPMMXでは、プログラムは16ビットと32ビットの両方のモードのPPlainとPMMXで使用可能である。

;************   Test program for PPlain and PMMX:    ********************
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とPIIIでは、RDTSCが他と並列に実行されないように、CPUIDのようなシリアル化する命令を各RDTSCの前後に置かなければならない。(CPUIDはシリアル化命令である。つまり、パイプラインをフラッシュして、進む前にペンディングしている操作がすべて完了するのを待つ。これはテストの目的には便利である。CPUIDは引き続く命令のプリフィックスをデコードできる影を持たない。)

RDTSC命令はPPlainとPMMXの仮想モードでは実行できないので、DOSのプログラムを走らせているなら、リアルモードにしなければならない。(ブート中にF8を押して、「Safe モード(コマンドプロンプトのみ)」または、「bypass startup files」を選ぶ)。

31. いろいろなマイクロプロセッサの比較

                               PPlain PMMX   PPro   PII    PIII 
----------------------------------------------------------------------
コードキャッシュ(KB)           8      16     8      16     16
データキャッシュ(KB)           8      16     8      16     16
内蔵L2キャッシュ(KB)           0      0      256    512*)  512*)
MMX命令                        なし   あり   なし   あり   あり
XMM命令                        なし   なし   なし   なし   あり
条件移動命令                   なし   なし   あり   あり   あり
アウト・オブ・オーダー実行     なし   なし   あり   あり   あり
分岐予測                       劣る   優れる 優れる 優れる 優れる
BTBのサイズ                    256    256    512    512    512
RSBのサイズ                    0      4      16     16     16
分岐予測ミスのペナルティ       3〜4   4〜5   10〜20 10〜20 10〜20
パーシャル・レジスタ・ストール 0      0      5      5      5
FMULの遅延                     3      3      5      5      5
FMULのスループット             1/2    1/2    1/2    1/2    1/2
IMULの遅延                     9      9      4      4      4
IMULのスループット             1/9    1/9    1/1    1/1    1/1
----------------------------------------------------------------------

訳注: 翻訳時点では更にXeon(Coppermine)、PentiumIII(Coppermine)、Celeron(Coppermine)が存在する。CoppermineコアはXMM命令を持っている。

表の注釈
コードキャッシュの大きさはプログラムの重要な部分が小さなメモリ領域に限定されていない時に重要である。

データキャッシュの大きさは重要な部分でより大きなデータを扱うすべてのプログラムで重要である。

MMX命令とXMM命令は多量のデータを並列に扱う時、つまり音と画像の処理のプログラムに便利である。他のアプリケーションではMMX命令とXMM命令の利点を発揮することはできないかもしれない。

条件移動命令は条件分岐の予測の低下を避けるために便利である。

アウト・オブ・オーダー実行は実行速度、特に最適化されていないコードの速度を改善する。これは自動的な命令の並べ替えとレジスタ・リネーミングを含む。

条件分岐予測法が優れているプロセッサは簡単な繰り返しパターンを予測できる。優れた分岐予測は分岐予測ミスのペナルティが高価な時に最も重要である。

リターン・スタック・バッファ(RSB)はサブルーチンが交互に異なる場所から呼び出される時の予測を改善する。

パーシャル・レジスタ・ストールは混合したサイズ(8, 16, 32ビット)のデータの扱いを更に難しくする。

乗算命令の遅延は依存の連鎖がある時の処理時間である。1/2のスループットは、新規の乗算が2クロックサイクル毎に実行できるよう、実行ユニットがパイプライン化されていることを意味している。これは並列なデータを扱う速度を定める。

このドキュメントに書かれた大部分の最適化手法は他のプロセッサ(インテルではないプロセッサを含む)では大した害を与えない、または全く与えない。しかしながら何らかの問題があることに気がついていなさい。

PPlainとPMMXのための浮動小数点コードのスケジューリングはしばしば多くのFXCH命令を必要とする。これは古いマイクロプロセッサでは速度を低下させるが、ペンティアムファミリーと、進歩したインテルではないプロセッサではそういうことはない。