ピープホールの最適化

ピープホール最適化は、ピープホールまたはウィンドウと呼ばれるコンパイラによって生成された命令の小さなセットに対して実行される最適化手法であり、 ^[1]^[2]命令を、より優れたパフォーマンスを持つ論理的に同等のセットに置き換えます。

例えば：

レジスタをスタックにプッシュし、すぐに値をレジスタに戻す代わりに、両方の命令を削除します。
xを2倍する代わりに、x + x
浮動小数点レジスタを8倍する代わりに、浮動小数点レジスタの指数に3を加算する

ピープホール最適化という用語は、1965年にウィリアム・マーシャル・マッキーマンによって導入されました。^[3]

代替品

ピープホール最適化の代替には、以下のものが含まれますが、これらに限定されるわけではありません。^[4]

ヌルシーケンス – 無駄な操作を削除する
操作を組み合わせる – 複数の操作を1つの同等の操作に置き換える
代数法則 – 代数法則を使用して命令を簡略化または並べ替える
特殊ケース命令 – 特殊なオペランドケース用に設計された命令を使用する
アドレスモード操作 – アドレスモードを使用してコードを簡素化する

実装

現代のコンパイラはパターンマッチングアルゴリズムを使用してピープホール最適化を実装することが多い。^[5]

例

遅い命令を速い命令に置き換える

次のJava バイトコード:

ロード 1
ロード 1
マル

より高速に実行できる次のコードに置き換えることができます。

ロード 1
重複
マル

ほとんどのピープホール最適化と同様に、これは異なる命令の相対的な効率に基づいています。この場合、 (スタックdupの先頭を複製してプッシュする) は、 (ローカル変数をロードしてスタックにプッシュする) よりも効率的であることがわかっており、そのように想定されています。aload

冗長なコードの削除

次のソースコード:

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命令を生成するとします。

 プッシュAFプッシュBCプッシュDEプッシュHLコール_ADDRポップHLポップDEポップBCポップAF

連続した 2 つのサブルーチン呼び出しがあった場合、次のようになります。

 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

同じレジスタに対する POP regs の後の PUSH のシーケンスは、一般的に冗長です。冗長な場合は、ピープホール最適化によってこれらの命令が削除されます。この例では、これにより別の冗長な POP/PUSH ペアがピープホールに出現し、これらが順に削除されます。サブルーチン _ADDR2 が以前のレジスタ値に依存しないと仮定すると、上記の例の冗長コードをすべて削除すると、最終的に次のコードが残ります。

 プッシュAFプッシュBCプッシュDEプッシュHLコール_ADDR1コール_ADDR2ポップHLポップDEポップBCポップAF

参照

オブジェクトコード最適化装置、一般的なアルゴリズムの効率性に関する議論
Capex Corporation – IBM Cobol用の初期のメインフレームオブジェクトコードオプティマイザであるCOBOL オプティマイザを製造しました。
スーパー最適化
Digital Research XLT86、最適化アセンブリソースツーソースコンパイラ

参考文献

^ Muchnick, Steven Stanley ( 1997-08-15 ). 高度なコンパイラの設計と実装。Academic Press / Morgan Kaufmann。ISBN 978-1-55860-320-2。
^ ディック・グルーン;アンリ・バル;ジェイコブス、セリエル。ランゲンドーエン、公園 (2012-07-20)。最新のコンパイラ設計 (第 2 版)。ワイリー/ジョン・ワイリー・アンド・サンズ株式会社ISBN 978-0-471-97697-4。
^ McKeeman, William Marshall (1965 年 7 月). 「ピープホール最適化」. Communications of the ACM . 8 (7): 443–444. doi : 10.1145/364995.365000 . S2CID 9529633.
^ Fischer, Charles N.; Cytron, Ron K.; LeBlanc, Jr., Richard J. (2010). コンパイラの作成(PDF) . Addison-Wesley . ISBN 978-0-13-606705-4. 2018年7月3日時点のオリジナル（PDF）からアーカイブ。2018年7月2日閲覧。
^ Aho, Alfred Vaino ; Lam, Monica Sin-Ling ; Sethi, Ravi ; Ullman, Jeffrey David (2007). 「第 8.9.2 章入力ツリーのタイリングによるコード生成」。コンパイラ – 原理、テクニック、ツール(PDF) (第 2 版)。Pearson Education。p . 540。2018年 6 月 10 日のオリジナルからアーカイブ(PDF) 。2018 年 7 月 2 日取得。

外部リンク

Christopher W. Fraser による copt 汎用ピープホール最適化ツール
原論文

ウィクショナリーの「ピープホール最適化」の辞書定義

[Muchnick_1997-1] Muchnick, Steven Stanley ( 1997-08-15 ). 高度なコンパイラの設計と実装。Academic Press / Morgan Kaufmann。ISBN 978-1-55860-320-2。

[Grune_2012-2] ディック・グルーン;アンリ・バル;ジェイコブス、セリエル。ランゲンドーエン、公園 (2012-07-20)。最新のコンパイラ設計 (第 2 版)。ワイリー/ジョン・ワイリー・アンド・サンズ株式会社ISBN 978-0-471-97697-4。

[McKeeman_1965-3] McKeeman, William Marshall (1965 年 7 月). 「ピープホール最適化」. Communications of the ACM . 8 (7): 443–444. doi : 10.1145/364995.365000 . S2CID 9529633.

[Fischer_2010-4] Fischer, Charles N.; Cytron, Ron K.; LeBlanc, Jr., Richard J. (2010). コンパイラの作成(PDF) . Addison-Wesley . ISBN 978-0-13-606705-4. 2018年7月3日時点のオリジナル（PDF）からアーカイブ。2018年7月2日閲覧。

[Aho_2007-5] Aho, Alfred Vaino ; Lam, Monica Sin-Ling ; Sethi, Ravi ; Ullman, Jeffrey David (2007). 「第 8.9.2 章入力ツリーのタイリングによるコード生成」。コンパイラ – 原理、テクニック、ツール(PDF) (第 2 版)。Pearson Education。p . 540。2018年 6 月 10 日のオリジナルからアーカイブ(PDF) 。2018 年 7 月 2 日取得。