のぞき穴的最適化

コンパイラ理論において、のぞき穴的最適化（のぞきあなてきさいてきか、）とはごく小さな特定の命令列に対して行われる最適化の一種である。この組は”peephole”または"window"と呼ばれる。のぞき穴的最適化はより短い、または高速な命令に置き換えられる命令を探すことによって行われる。

置換ルールのぞき穴的最適化には一般に以下のような手法が用いられる。

ヌルシーケンス‐無駄な命令の削除命令の結合‐複数の命令を等価なひとつの命令に置換代数法則の適用‐代数法則を用いることによる命令の簡略化または並べ替え特殊ケース命令‐特殊ケースのために設計された命令の使用アドレスモード操作‐コードの簡略化のためのアドレスモードの使用

この他にも様々なのぞき穴的最適化が存在する。

例

遅い命令を速いものに置換

... aload 1 aload 1 mul ... 上のJavaバイトコードは以下のように置き換えることができる。 ... aload 1 dup mul ... この手ののぞき穴的最適化は命令の効率性を仮定している。実際この場合はdup 命令（複製してそれをスタックトップに積む）がaload X命令（X というローカル変数を読み込みスタックに積む）よりも効率的だと仮定している。

冗長なコードの削除次に挙げる例では冗長なロード・ストア命令を削除する。 a = b + c; d = a + e; 上のコードを素直に実装すると以下のようになる。MOV b, R0 # bをレジスタにコピー ADD c, R0 # cをレジスタに加算。したがってレジスタの値はb+cになる MOV R0, a # レジスタの値をaにコピー MOV a, R0 # aをレジスタにコピー ADD e, R0 # eをレジスタに加算。したがってレジスタの値はa+e [(b+c)+e]になる MOV R0, d # レジスタの値をdにコピーしかしこのコードは以下のように最適化できる。MOV b, R0 # bをレジスタにコピー ADD c, R0 # cをレジスタに加算。したがってレジスタの値はb+cになる (a) MOV R0, a # レジスタの値をaにコピー ADD e, R0 # eをレジスタに加算。したがってレジスタの値はb+c+e [(a)+e]になる MOV R0, d # レジスタの値をdにコピー

冗長なスタック命令の削除コンパイラがサブルーチンの呼び出し前にレジスタの値をスタックへと退避させて呼び出し後に復元している場合、連続的なサブルーチンの呼び出しにおいて冗長なスタック命令が発生することがある。

コンパイラが以下のようなZ80向け命令列をプロシージャ呼び出しのたびに生成したとする。 PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR POP HL POP DE POP BC POP AF例えばサブルーチン呼び出しが２回ある場合は、以下のようになる。 PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR1 POP HL POP DE POP BC POP AF PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR2 POP HL POP DE POP BC POP AF一般にすぐ後でPUSHするレジスタをPOPする命令は冗長である。実際に冗長な命令だった場合、のぞき穴的最適化でこの命令は削除される。この例では、冗長な隣り合うPOP・PUSH命令が現れた場合、それらを順に削除していく。冗長なコードをすべて削除すると、最終的に以下のようなコードになる。 PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR1 CALL _ADDR2 POP HL POP DE POP BC POP AF

実装現代的アーキテクチャではさまざまなのぞき穴的最適化が可能であり、コンパイラプログラマーはパターンマッチングアルゴリズムを用いてこれを実装するのが基本的に適切である。

のぞき穴的最適化

Źródło i licencja