スーパー最適化

スーパー最適化とは、コンパイラがループのない命令シーケンスの最適なシーケンスを自動的に見つけるプロセスです。現実世界のコンパイラは一般に真に最適なコードを生成することはできず、ほとんどの標準的なコンパイラ最適化はコードを部分的にしか改善しませんが、スーパー最適化の目的は最適なシーケンス、つまり標準形式を見つけることです。スーパー最適化を使用すると、見逃された機会を強調表示して人間が追加のルールを記述できるようにすることで、従来の最適化を改善できます。

スーパー最適化という用語は、1987 年の論文「スーパーオプティマイザー: 最小のプログラム」でAlexia Massalinによって初めて使用されました。^[1] 「プログラム最適化」というラベルは、最適化ではなく改善のみを目的とする分野に付けられました。この誤った名称により、Massalin は自分のシステムをスーパーオプティマイザーと呼ばざるを得ませんでしたが、これは実際には最適なプログラムを見つけるためのオプティマイザーです。^[2]

1992年に、GNUスーパーオプティマイザ（GSO）がGNUコンパイラコレクション（GCC）に統合するために開発されました。^{[3] [4]}その後の作業でこれらのアイデアがさらに発展し、拡張されました。

従来、スーパー最適化は有効な命令シーケンスの空間で徹底的なブルートフォース検索によって実行されます。これはコストのかかる方法であり、汎用コンパイラではほとんど実用的ではありません。しかし、パフォーマンスが重要な内部ループを最適化するのに役立つことが示されています。また、 SMTソルバーを使用して問題にアプローチすることも可能であり、検索効率が大幅に向上します（ただし、基本ブロックよりも複雑な入力には対応できません）。^[5]

2001年、コンパック研究所のデナリプロジェクトで目標指向型スーパー最適化が実証されました。^[6] 2006年には、バース大学のTOAST ( Total Optimisation using Answer Set Technology )プロジェクト^[7]で、回答セット 宣言型プログラミングがスーパー最適化に適用されました。^{[8] [9]}

スーパー最適化は、汎用のピープホール最適化装置を自動的に生成するために使用できます。^[10]

いくつかのスーパーオプティマイザーは無料でダウンロードできます。

• x86 ファミリの命令セットの場合:
  • GNUスーパーオプティマイザ（superopt）^[11]（GSO）（1992）^{[3] [4]} – 他の多くのISAもサポート
  • STOKE ^[12]はx86-64 x86アセンブリ言語用の確率的最適化装置^[13]である。
• ARMの場合:
  • 無制限スーパーオプティマイザ^[5]はLLVM IRをARMv7-Aアセンブリに変換する
• 組み込みシステムの場合:
  • PICマイクロコントローラスーパーオプティマイザ（2003）^{[14] [15]}
  • Embecosm (2014)によるAVRの実現可能性調査、GSOに基づく^{[16] [17]}
• JVMの場合:
  • Java仮想マシン用Clojureスーパーオプティマイザー（2012）^[18]
• LLVM IRの場合:
  • souper ^[19] LLVM中間言語プログラム用のスーパーオプティマイザー。
• WebAssemblyの場合
  • スランプ^[20]は、スーパー最適化に基づくWASMプログラムのスーパー最適化を提供する。

• ピープホールの最適化
• デッドコードの除去
• メタコンパイル