最小のプログラムを探る：スーパーオプティマイザーの世界

Superoptimizer – A Look at the Smallest Program

本稿は、与えられた関数に対して最小のプログラムを自動的に見つける「スーパーオプティマイザー」の概念を解説する。1980年代に発表されたこの古典的な論文は、ブルートフォース探索によって、人間が設計したプログラムよりも小さなプログラムを発見できることを示した。具体例として、符号反転や最大値計算などの関数に対する最小プログラムの発見過程を紹介し、スーパーオプティマイザーがプログラムのサイズと実行速度のトレードオフをどのように扱うかを説明する。また、この手法の限界と、現代のコンパイラ最適化やプログラム合成への影響についても考察する。