Superoptimization とは

超最適化は、1つのループフリーシーケンスの命令に対して最適なコードシーケンスを自動的に見つけるプロセスです。これは、コンパイラと呼ばれる一種のコンピュータソフトウェアによって実行されます。実世界のコンパイラは、一般に真に最適なコードを生成することはできません。ほとんどの標準的なコンパイラの最適化はコードを部分的に改善するだけですが、スーパーオプティマイザの目標は最適なシーケンスであるカノニカルフォームを見つけることです。
スーパーオプティマイゼーションという用語は、1987年の論文Superoptimizer:最小のプログラムを見て、Henry Massalinによって最初に作成されました。 1992年、GNU Superoptimizer(GSO)はGNUコンパイラ・コレクション(GCC)に統合するために開発されました。後の作業はこれらのアイデアをさらに発展させ、拡張した。 2001年、Compaqの調査によるDenaliプロジェクトで、目標指向の超最適化が実証されました。 2006年には、バース大学でのTOAST(Total Set Optimization)プロジェクトでの超最適化にanswer set宣言プログラミングを使用し、汎用最適化オプティマイザを自動的に生成するために超最適化を使用しました。
典型的には、有効化された命令シーケンスの空間内で徹底したブルートフォース探索によって超最適化が実行される。これはコストのかかる方法であるため、汎用コンパイラでは実用的ではありません。それでも、パフォーマンス重視の内部ループの最適化に役立つことが示されています。