のぞき穴的最適化

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

置換ルール

のぞき穴的最適化には一般に以下のような手法が用いられる。^[1]

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

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

例

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

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

実装

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

参考文献

^ Fischer, Charles N; Cytron, Ron K; LeBlanc, Richard J, Jr. (2010). Crafting a Compiler. Addison-Wesley. ISBN 978-0-13-606705-4 2 July 2018閲覧。
^ Aho, Alfred V; Lam, Monica S; Sethi, Ravi; Ullman, Jeffrey D (2007). “"8.9.2 Code Generation by Tiling an Input Tree"” (PDF). Compilers - Principles, Techniques, & Tools (second edition). Pearson Education. p. 540. オリジナルの10 June 2018時点におけるアーカイブ。 2 July 2018閲覧。

外部リンク

[1] Fischer, Charles N; Cytron, Ron K; LeBlanc, Richard J, Jr. (2010). Crafting a Compiler. Addison-Wesley. ISBN 978-0-13-606705-4 2 July 2018閲覧。

[2] Aho, Alfred V; Lam, Monica S; Sethi, Ravi; Ullman, Jeffrey D (2007). “"8.9.2 Code Generation by Tiling an Input Tree"” (PDF). Compilers - Principles, Techniques, & Tools (second edition). Pearson Education. p. 540. オリジナルの10 June 2018時点におけるアーカイブ。 2 July 2018閲覧。

[1]

[2]