コンパイラ最適化

コンパイラ最適化（コンパイラさいてきか、）では、コンピュータ・プログラムの最適化に関する話題のうち、もっぱらコンパイラに関係するものに関して説明する。最も一般的な要求はプログラムの実行時間を最小化することであり、その次に使用するメモリ量を最小化することである。また、携帯可能なコンピュータが増えるにつれて、消費電力を最小化するという最適化も生まれてきた。
一部のコード最適化問題はNP完全問題であることが示されている。実際には、プログラマがコンパイラによる最適化の完了を待てる時間の上限なども考慮してコンパイラ最適化を実装する（最適化はCPU時間とメモリを多大に使用する）。かつては、コンピュータのメモリ実装量も実行できる最適化を制限する要因だった。
コンパイラメーカによっては、「コンパイラの最適化の能力が売り上げや評判に大きく影響する」と信じている場合があり、そういう信念に従って「最適化コンパイラ」と銘打つことがある。少なくとも、同程度にバグが無いコンパイラ同士であれば、という前提の範囲内なら、最適化の能力が高いほうが魅力的と言えるであろう。
最適化の種類.
最適化はソース言語（プログラミング言語）に近い表現の中間語に対して行う高水準最適化と、機械語に近い表現の中間語に対して適用される低水準最適化に分類される。
最適化技法はその「スコープ」で分類できる。スコープは文単位からプログラム全体まで様々である。一般にスコープの狭い技法の方が広いものより実装が容易だが、効果は小さい。スコープとしては以下のようなものがある:
スコープによる分類のほかに、以下の2つの最適化の分類がある:
マシン依存の最適化の具体例を示す。レジスタに0を設定する最もシンプルな方法は、命令内で 0 という定数（イミディエート値）をレジスタに設定することである。別のより技巧的な方法では、レジスタを自分自身とのXORの演算結果で置き換える方法がある。どちらの方法を利用するかはコンパイラ次第である。多くのRISCの場合、どちらの方法でも命令長と実行時間に違いはない。インテルx86系などでは、XORを使った方法がより短く速い。これはイミディエート値をデコードする必要がなく、内部のimmediate operand registerを使わないため。またXOR命令がレジスタの依存関係によってパイプライン停止を招くことがあるが、自分自身のXORではパイプラインは停止しない。
最適化に影響する要因.
対象マシン.
適用可能かつ適用すべき最適化の選択は対象マシンの性格に依存する。場合によってはマシン依存の要因をパラメータ化可能であり、マシンを指定するパラメータによってコードに適用する最適化を変えることもできる。GCCは、そのような手法を採用している例である。
各種最適化.
コンパイラ最適化を大きく捉えれば、以下のような目的があり、これらは時には互いに矛盾する。
ループ最適化.
主にループを操作する最適化技法として、以下のものがある。
データフロー最適化.
データフロー最適化はデータフロー解析に基づいて行われ、あるデータの特性が制御フローグラフ内の制御エッジでどのように伝播されるかによるもの。以下のような技法がある。
静的単一代入形(SSA)ベースの最適化.
以下の最適化は、プログラムを静的単一代入(SSA)と呼ばれる形式に変換した上で行われる。SSA では各変数への代入が一箇所だけで行われる。場合によってはSSAに変換しないで最適化を施すこともあるが、ここに挙げる最適化技法はSSAと共に用いることで最も効果を発揮する。他の節に挙げた最適化技法でも、SSA に適用可能であるものが多い。
関数型言語での最適化.
ここで挙げる最適化技法は関数型言語以外にも適用可能な場合が多いが、LISPやMLといった関数型言語向けに開発された技法である。
プロシージャ間最適化.
プロシージャ間最適化はプログラム全体を対象とするもので、プロシージャの境界やファイルの境界を越えた最適化である。プロシージャ間で関係する部分に働き、局所的な最適化と大域的な最適化の協調によって行われる。主なプロシージャ間最適化としては、インライン展開、プロシージャ間デッドコード削除、プロシージャ間定数伝播、プロシージャ再配置などがある。通常、最適化の前にプロシージャ間解析が必要であり、プロシージャ間エイリアス解析、配列アクセス解析、コールグラフ構築などがある。
プロシージャ間最適化は最近の 商用コンパイラ（SGI、インテル、マイクロソフト、サン・マイクロシステムズ）にはほとんど備わっている。しかし、現在ではプロシージャ間最適化を実装している。その他のオープンソースのコンパイラでプロシージャ間最適化を備えたものとして Open64 がある。こちらは研究用や商用にも利用されている。
プロシージャ間最適化（およびそのための解析）には時間とメモリを要するため、デフォルトでは実施しない設定になっているコンパイラが多い。ユーザーは明示的にオプションを指定して最適化することを指示しなければならない。
最適化におけるプログラムの表現.
コンパイラの最適化処理では、その処理内容に応じて各種表現を使い分けることが多い。以下に代表的な表現を示す。
最適化における問題.
コンパイラ史の初期、コンパイラによる最適化は人間が手で書いたコードほどよいコードを生成しなかった。コンパイラ技術の進展と共に、コンパイラが人間のプログラマよりもよいコードを生成できるようになってきた。また、人間が最適化技法を駆使して書いたコードをさらに最適化できるオプティマイザも出現したほどである。RISCアーキテクチャやVLIWではコンパイラ最適化は効率的なコードを得るための鍵となっている。というのも、RISCの命令セットは小さく、人間がそれらのスケジュールを手で行ったり、効率的な結果を得るのは困難だからである。実際、それらアーキテクチャの性能はコンパイラの良し悪しに大きく左右される。
しかし、最適化コンパイラは完全ではない。コンパイラがあらゆるソースコードに対して最適なコードを生成することはできない。どんなソースコードに対しても最良の最適化を行うコンパイラの存在を仮定すれば、チューリングマシンの停止問題の解が導かれ、矛盾が生じる。よってそのようなコンパイラは存在しない。
さらに、最適化コンパイラ技術にはいくつかの現実的な問題が存在する。
最適化技法を改良する試みは続けられている。1つの試みとして「ポストパス」オプティマイザがある。これは最適化コンパイラの出力である実行ファイルに対してさらに最適化を行うツールである。コンパイラ最適化がプログラムの中間表現に対して作用するのに対して、ポストパス・オプティマイザはアセンブリ言語レベルに対して作用する。しかし、ポストパス・コンパイラにも限界がある。なぜなら、オリジナルのソースコードに存在していた情報の多くは、実行ファイルでは失われているからである。
プロセッサの性能向上はメモリの帯域幅の向上よりも激しい。そのため、たとえ余分な命令を実行しなければならないとしても、使用するメモリ帯域幅を削減するような最適化が有効になってきた。例えば、入れ子ループ最適化や再実体化がそのような最適化の例である。