超最適化

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

スーパー最適化という用語は、1987年の論文「Superoptimizer: A Look at the Smallest Program」でアレクシア・マサリンによって造語されました。^{[ 1 ]} 「プログラム最適化」という名称は、最適化を目指すのではなく、改善を目指す分野に与えられてきました。この誤った名称のため、マサリンは自身のシステムをスーパーオプティマイザーと呼ぶことを余儀なくされました。実際には、これは最適なプログラムを見つけるためのオプティマイザーです。^{[ 2 ]}

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

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

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

超最適化は、汎用的な覗き穴最適化ツールを自動的に生成するために使用できます。^{[ 10 ]}

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

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

• 覗き穴最適化
• デッドコードの削除
• メタコンパイル