コンパイラ最適化

コンパイラ最適化（コンパイラさいてきか、英語: Compiler optimization）では、コンピュータ・プログラムの最適化に関する話題のうち、もっぱらコンパイラに関係するものに関して説明する。最も一般的な要求はプログラムの実行時間を最小化することであり、その次に使用するメモリ量を最小化することである。また、携帯可能なコンピュータが増えるにつれて、消費電力を最小化するという最適化も生まれてきた。

一部のコード最適化問題はNP完全問題であることが示されている。実際には、プログラマがコンパイラによる最適化の完了を待てる時間の上限なども考慮してコンパイラ最適化を実装する（最適化はCPU時間とメモリを多大に使用する）。かつては、コンピュータのメモリ実装量も実行できる最適化を制限する要因だった。

コンパイラメーカによっては、「コンパイラの最適化の能力が売り上げや評判に大きく影響する」と信じている場合があり、そういう信念に従って「最適化コンパイラ」と銘打つことがある。少なくとも、同程度にバグが無いコンパイラ同士であれば、という前提の範囲内なら、最適化の能力が高いほうが魅力的と言えるであろう。

最適化の種類

最適化はソース言語（プログラミング言語）に近い表現の中間語に対して行う高水準最適化と、機械語に近い表現の中間語に対して適用される低水準最適化に分類される。

最適化技法はその「スコープ」で分類できる。スコープは文単位からプログラム全体まで様々である。一般にスコープの狭い技法の方が広いものより実装が容易だが、効果は小さい。スコープとしては以下のようなものがある:

のぞき穴的最適化: コンパイラが機械語を生成した後で行われる最適化。この場合、（ちょうどのぞき穴から見るように）隣接する数命令だけに注目し、その命令列をより短く、場合によっては1命令に置換できないか検討する。例えば、何らかの値に2をかけている場合、シフト命令や加算命令（自分自身を加算する）に置き換えた方が高速化できる場合がある（これは演算子強度低減でもある）。
ループ最適化（英語版）: ループを構成する文のブロック（例えばfor文）に対して最適化を行う（ループ不変量コード移動など）。プログラムの実行時間の大部分は何らかのループ内であることが多いため、ループ最適化は性能に重大な影響を与える可能性がある。
局所最適化、プロシージャ内最適化: 1つの関数定義内の情報だけを考慮する最適化。解析の手間が削減される（時間とメモリ使用量が節約される）が、大域変数やその関数内で他の関数を呼び出している箇所について最悪の場合を想定する必要がある（手続き外についての情報がないため）。
プロシージャ間最適化、プログラム全体の最適化: プログラムのソースコード全体を解析する最適化。より多くの情報が得られるため、さらに効率的な最適化が可能。新しい技法も適用可能である。例えばインライン展開技法を使えば、関数呼び出しを関数そのものと置き換えることになる。

スコープによる分類のほかに、以下の2つの最適化の分類がある:

プログラミング言語非依存とプログラミング言語依存: 多くの高級言語の構文要素や抽象化は共通である。分岐 (if, switch, case)、ループ (for, while, repeat...until, do...while)、カプセル化（構造体、オブジェクト）などがある。この特徴を利用して言語に依存しない最適化技法を利用できる。しかし、言語によってはある種の最適化が容易だったり、逆に難しかったりする。例えば、C言語やC++はポインタがあるため、配列アクセスの最適化が困難である。逆に、一部の言語では関数が副作用を持つことができない。このため、同じ引数で同じ関数を何度も呼び出す場合、コンパイラはこれを最適化して一回だけその関数を呼び出して、後はその結果を再利用することができる。
マシン (CPU) 非依存とマシン依存: 抽象的な概念（ループ、オブジェクト、構造体など）に関する最適化はコンパイラが対象としているマシンとは関係なく実施できる。しかし、効果的な最適化の多くは対象プラットフォーム特有の機能を考慮したものであることが多い。

マシン依存の最適化の具体例を示す。レジスタに0を設定する最もシンプルな方法は、命令内で 0 という定数（イミディエート値）をレジスタに設定することである。別のより技巧的な方法では、レジスタを自分自身とのXORの演算結果で置き換える方法がある。どちらの方法を利用するかはコンパイラ次第である。多くのRISCの場合、どちらの方法でも命令長と実行時間に違いはない。インテル x86系などでは、XORを使った方法がより短く速い。これはイミディエート値をデコードする必要がなく、内部のimmediate operand registerを使わないため。またXOR命令がレジスタの依存関係によってパイプライン停止を招くことがあるが、自分自身のXORではパイプラインは停止しない。

最適化に影響する要因

対象マシン

適用可能かつ適用すべき最適化の選択は対象マシンの性格に依存する。場合によってはマシン依存の要因をパラメータ化可能であり、マシンを指定するパラメータによってコードに適用する最適化を変えることもできる。GCCは、そのような手法を採用している例である。

対象CPUのアーキテクチャ

CPUのレジスタ本数: レジスタが多ければ多いほど、性能の最適化が容易になる場合がある。レジスタが多ければ局所変数をコールスタック上ではなくレジスタに割り当てられる割合がより高くなる。一時的な結果をレジスタに残すことでメモリの読み書きをする回数を減らすことができる。
RISCとCISC: CISC命令セットの命令長は可変であることが多く、命令数も多く、各命令の実行間隔も一定していない。RISC命令セットでは命令長が固定で、アドレッシングモードもCISCより少なく、各命令は一定間隔で実行される（実行時間は必ずしも一定ではない）。同じ処理をコード化したときの多様さはCISCの方がRISCより豊富である。コンパイラは各命令や命令の組み合わせによるコストを考慮してコード生成する（命令選択）。
パイプライン: パイプラインは、CPUを機能分割して工場の生産ラインのように並べたものと言える。基本的なパイプラインのステージは、命令の読み込み、命令のデコード、演算、メモリアクセス、レジスタへの格納である。これにより、CPUの各部が異なる命令の異なる処理をすることが可能となる。すなわち、ある命令の演算を行っているとき、同時に別の命令をデコード可能である。パイプラインのあるステージにある命令がもっと先のステージにある未完了の命令の結果を必要とするとき、パイプラインハザードが発生する。ハザードはパイプラインの停止（ストール）を招き、ハザードが解決されるまでCPUは処理を遅延させる。; コンパイラは依存関係を持つ命令群を実行結果に影響しないよう注意しながら再配置を行い、ストールが起こりにくくする。
機能ユニットの数: 一部のCPUは複数のALUやFPUを備えており、複数の命令を同時に実行できる。同時に実行できる命令の種類には制限があることもあり、各ユニットが実行できる命令の種類も制限がある。これらにはパイプライン衝突と同様の問題が存在する。; コンパイラはこのような場合も命令をうまく配置して、各機能ユニットがなるべく常に動作するようにスケジュールできる。

対象マシンのアーキテクチャ

キャッシュメモリサイズとタイプ（ダイレクトマップ、n-wayセットアソシアティブ、フルアソシアティブ）: インライン展開やループ展開などの手法はコードのサイズを増大させ、参照の局所性を損なう。頻繁に実行されるコードの塊がキャッシュに収まらなくなると、性能は劇的に低下する。フルアソシアティブでないキャッシュではキャッシュ上での衝突が発生しやすい。
キャッシュ/メモリ間転送レート: これによりコンパイラはキャッシュミスした場合のペナルティの度合いを知ることができる。このような情報を必要とするのは、主に一部の特殊なアプリケーションである。

生成されたコードの用途

デバッグ: プログラマは、アプリケーション開発の最中に頻繁にコンパイルを行うため、コンパイルは高速でなければならない。このため、最適化の大部分はデバッグ中には実施されない。また、デバッグ中のコードはデバッガでステップ実行されたりするので、命令を並べ替えるような最適化を行うと、デバッグが困難になる（ある命令がソースコードのどの部分に相当するかわかりにくくなる）。もっとも、コンパイラ最適化を行うことで発生する障害もまれにあり、その場合は最適化されたコードで何とかデバッグするしかない。
汎用目的: パッケージソフトウェアは一般に命令セットが同じCPUを搭載した各種マシン上で実行されることが予想される。それらマシンはタイミングやメモリなどの特性が異なる。そのため、コードを特定のCPU向けに最適化することはできず、最も一般的なCPU向けに最適化しつつ、他のCPUでもそれなりの性能で動作するようにする。
特殊目的: 特定のマシン上で動作することが決まっているソフトウェアでは、そのマシン向けに最適化できる。例えば、並列コンピュータやベクトル計算機向けの並列化コンパイラなどがある。

各種最適化

コンパイラ最適化を大きく捉えれば、以下のような目的があり、これらは時には互いに矛盾する。

通常の場合を最適化: 分岐において、より通る確率が高い経路がわかる場合、そちらを優先的に最適化した方が全体として性能が向上する。
冗長性の除去: 既に計算されている結果を再利用することで、再計算する無駄を省く。
コードを小さくする: 不要な計算や計算途中の値を削除する。CPU、キャッシュ、メモリをなるべく使わないようにすることで高速化させる。
分岐を少なくする: なるべく制御構造を単純化する。分岐は命令のプリフェッチを乱すため、性能低下の原因となる。
局所性: 時間的に近接してアクセスされるコードやデータはメモリ上で空間的にも近接していれば、空間的局所性を増大させることができる。
メモリ階層を考慮: メモリへのアクセスは（CPU性能に比較して）益々高価につくようになってきており、これはキャッシュメモリも程度は違うが同様である。そのため、頻繁に使用するものはまずレジスタに置き、次にキャッシュ、それでも足りない場合は主記憶、さらにはディスクとなるようメモリ階層を考慮した最適化をする。
自動並列化: 配置を最適化することで並列に複数の計算が行えるようにする。これには命令レベル、メモリレベル、スレッドレベルの並列化がある。; マルチプロセッサ上でプログラムを複数のスレッドで動作するように変換する。
より精密な情報を得るため: コンパイラがより精密な情報を得られれば、各種最適化技法を適用できるようになる。

ループ最適化

主にループを操作する最適化技法として、以下のものがある。

帰納変数解析: ループ内の変数がループ変数の簡単な式で計算されている場合（例えば、j:= i*4）、ループ変数の更新時に同時にその変数も更新できる（例で言えば、i:=i+1 なら j:=j+4）。これは一種の演算子強度低減であり、同時にループ変数を他に使っていないならデッドコード削除も伴う。この情報は境界検査除去（後述）や依存関係解析などにも利用される。
ループ分裂/分散: 1つのループを複数の同じインデックス範囲のループに分割する（各ループにはオリジナルのループ内の処理の一部が入る）。ループ内で参照されるデータとループ内のコードの両面で参照の局所性を高める。
ループ融合/結合: ループ回数が同じである複数のループをまとめることでループによるオーバーヘッドを低減する。
ループ転置: whileループを等価なdo/whileやrepeat/untilループに変換することで条件比較回数を減らす。通常、ループの前に条件文を追加する必要があり、コードのサイズは増大するが、命令パイプラインをスムーズにする効果がある場合もある。また、コンパイル時に初期条件が明確で、かつ副作用の問題もない場合、最初の条件文を除去できる。
ループ交換: 入れ子になったループで、内側のループと外側のループを入れ替える。ループ変数群が配列のインデックスであった場合、この最適化で参照の局所性を高めることができる場合もある（配列の並び方に依存する）。
ループ不変量コード移動: 毎回、ある値がループ内で計算されていて、毎回同じ値である場合、それをループの前に1回だけ計算することで最適化する。配列についてのループでアドレスを計算する式などで特に有効である。全てのコードがループの外で計算できるわけではないので、ループ転置と合わせて実施するのが一般的である。
入れ子ループ最適化: 行列の乗算などはメモリアクセスが多く、キャッシュヒット率も悪い。入れ子ループ最適化では、ループ交換などの技法を使ってキャッシュヒット率を向上させる。
ループ反転: ループ変数の値の変化する順序を反転させる（例えば、0 から 10 だったものを 10 から 0 にする）。これは微妙な最適化であり、依存関係解析を省く効果があったり、他の最適化が可能になるなどの効果が期待できる。
ループ展開: ループの中身のコードを複数回配置してループ条件のチェック回数を減らしたり、分岐回数を減らすことによってオーバーヘッドを低減させる。ループを完全に展開すればオーバーヘッドはゼロになるが、コンパイル時にループ回数が明確になっていなければならない。
ループ分割: 1つのループを複数に分割するが、各ループの中身は同じで、ループ変数の範囲が異なるようにする。例えば、一般にループの1回目の実行では各種処理が余分に必要となっている場合がある。これを1回目だけ分割してみると、その後のループでは各種最適化が可能となる場合がある。
ループと条件文の入れ替え（Loop unswitching）: ループ内の条件文を外に追い出して、条件文の then 部と else 部に元のループのコピーを置く。並列性を高めるなどの効果がある。

データフロー最適化

データフロー最適化はデータフロー解析に基づいて行われ、あるデータの特性が制御フローグラフ内の制御エッジでどのように伝播されるかによるもの。以下のような技法がある。

共通式削除（common sub-expression elimination）: 例えば、(a+b)-(a+b)/4という式があったとき、(a+b) は2回出現する。共通式削除では、(a+b) がこの間に変化しないと判断し、1回だけ計算するよう最適化する。
定数畳み込み（constant folding）と定数伝播（constant propagation）: 定数からなる式（例えば、3 + 5）をコンパイル時に計算結果（8）と置き換えてしまう。最近の言語処理系ではほとんど必ず行われる。
帰納変数の認識と除去
エイリアス分類とポインタ解析: ポインタのある言語では、変数をポインタを通じて参照・操作する可能性があるため、最適化が難しい。このため、どのポインタがどの変数のエイリアス（別名）であるかを識別することで無関係のポインタを無視する最適化を行う。

静的単一代入形(SSA)ベースの最適化

以下の最適化は、プログラムを静的単一代入(SSA)と呼ばれる形式に変換した上で行われる。SSA では各変数への代入が一箇所だけで行われる。場合によってはSSAに変換しないで最適化を施すこともあるが、ここに挙げる最適化技法はSSAと共に用いることで最も効果を発揮する。他の節に挙げた最適化技法でも、SSA に適用可能であるものが多い。

大域値番号付け（英: Global Value Numbering）; プログラムの値グラフを作成して冗長性を除去し、等価な式で計算される値を特定する。大域値番号付けは共通式削除ではできない冗長性の除去が可能である。逆に共通式削除でしかできない冗長性の除去もある。
疎な条件分岐を考慮した定数伝播（英: sparse conditional constant propagation）; 定数伝播、定数畳み込み、デッドコード削除を変化がなくなるまで繰り返し実施するのとほぼ同じ最適化であるが、より効率的である。この最適化はプログラムを記号的に実行し、同時に定数値を伝播させ、到達できない部分を制御フローグラフから削除する。

コード生成での最適化

レジスタ割り当て: 最も頻繁に使われる変数はレジスタに割り当てて、高速にアクセスできるようにする。どの変数をレジスタに置くべきかを決定するために、干渉グラフ（英: interference-graph）を作成する。各変数をノードで表し、同時に使われる2変数の間を線で結ぶ。このグラフにチャイティンのアルゴリズムなどを適用して色をつけ、同じ色数となった変数をレジスタに割り当てる。色付けが失敗して、同じ色数の変数の一部がレジスタに割り当てられなくなった場合、色付けを再試行する。
命令選択: 豊富なアドレッシングモードのあるCISCアーキテクチャでは、同じ操作を行う複数の方法が存在することが多く、各手法で命令は全く異なる。命令選択では、低レベルな中間表現を命令に置き換える際にどの命令にするのが最も効率的かを判断して選択する。例えば、MC68000系のプロセッサでは、"lea 25(a1,d5*4), a0" といった複雑なアドレッシングモードが使われ、1命令でかなり複雑な演算が行われる。
命令スケジューリング: 命令スケジューリングはパイプライン化プロセッサでは重要な最適化技法であり、パイプラインハザードの発生を最小にするため、プログラムの意味を変えない範囲での命令の並べ替えによって行う。
再実体化 (Rematerialization): メモリからロードせずに再計算を行うことで実行時間を節約する。これはレジスタ割り当ての最適化と同時に行われる。再計算コストとメモリアクセスコストのトレードオフによって選択される。
計算の再配置: 線形計画に基づいて計算を再配置することで参照の局所性を向上させたり、並列性を引き出したりする。
CPU固有命令の使用: 拡張命令（MMXやSSE等）を使う機械語を生成する。代わりに、それらに対応していないCPU上では動作しなくなる。

関数型言語での最適化

ここで挙げる最適化技法は関数型言語以外にも適用可能な場合が多いが、LISPやMLといった関数型言語向けに開発された技法である。

再帰呼び出し除去

再帰にはコストがかかる。関数呼び出しはコールスタックを使用し、引数を渡すオーバーヘッドがかかり、命令キャッシュがフラッシュされてしまう。末尾再帰アルゴリズムは単純な繰り返しに変換でき、関数呼び出しのオーバーヘッドを除去できる。末尾再帰除去とも呼ぶ。
データ構造融合: Haskell などの関数型言語でのデータ構造の特徴として、一時的なデータ構造を作成・使用する複数の再帰関数を結合することができ、データ構造構築にかかる時間を省くことができる。
ラムダ計算からコンビネータ論理への変換: 大抵の関数型言語は、計算モデルとしてラムダ計算を採用している。しかし、ラムダ計算での式の評価は非常に複雑であり、計算機に大きな負荷をかけてしまう。対照的に、コンビネータ論理の式の評価は置換という概念が存在しないため、はるかに簡単であり計算負荷を軽減することが出来る。

その他の最適化

境界検査除去: Javaのような言語では、配列にアクセスする際に常に指定されたインデックスが、配列の範囲内に収まっているかどうか実行時にチェックが行われる。このチェックは、科学技術計算のような性能が重視されるアプリケーションでは性能を悪化させてしまう。境界検査除去は、チェックを安全な局面で除去するものである。例えば、ループ変数が配列のインデックスとして使われている場合、ほとんどの境界検査は除去できる。
分岐オフセット最適化（マシン非依存）: 分岐先に到達できる最短の分岐ディスプレースメントを選択する。
ブロック再配置: 基本ブロック（入り口と出口がそれぞれ1つしかないコードの塊。途中分岐しないブロック）を並べ替えて条件分岐命令を減らしたり、参照の局所性を向上させたりする。
デッドコード削除: プログラムの動作に影響を与えない命令群（例えば、使われていない定義）などを削除する。これによりコードのサイズを縮小し、不要な計算をしないようにする。
不変式のくくり出し: 条件文のthen部とelse部に同じ式がある場合、その計算を条件式の外で1回だけ行うようにする。同様に、定数の変数への代入のような式がループ内にある場合、ループ内で何度実施しても効果は同じであるため、それをループの外にくくり出すことができる（ループ不変量コード移動）。全体冗長性除去（Total Redundancy Elimination）。より強力な最適化として部分冗長性除去 (Partial Redundancy Elimination) がある。
分岐スレッディング (jump threading): GCCの持つ最適化技法。条件分岐の条件が同じものや正反対のものを検出した場合、2番目の分岐先に繋ぎ合わせる。
演算子強度低減: 複雑でコストのかかる操作（演算）をより単純で等価なものに置き換える最適化。帰納変数解析（前述）により、ループ内のループ変数に依存した変数についてこれが行える。のぞき穴的最適化の一部もここに分類される。例えば、定数による除算を逆数の乗算に置き換えたり、乗算をビットシフトと加算で置き換えたり、（CISCの場合）大きな命令を同等機能の小さな命令に置き換えたりする。; x = y * 2 → x = y << 1 （乗算をビットシフトへ）; x += 1 → x++ （加算をインクリメントへ）; など
キャッシュ上の衝突の削減: ページ内のデータの配置を変え、時間的に近接してアクセスされるデータがキャッシュ上の同じ位置に来ないようにする。
スタックを使用する深さを削減: 式の構文木を構成しなおして、式の評価に必要とされるリソースを最小化する。
条件式の並べ替え: 複数の条件式が論理積や論理和で並んでいるとき、単純な条件式（変数と何かを比較するなど）を先に評価して、次に複雑な条件式（何らかの関数呼び出しを伴うものなど）を評価するようにした方が一般には効率がよい。これは遅延評価を補う技法だが、各条件式が互いに依存している場合は実施できない。最小評価の意味論がこれをさらに難しくする。

プロシージャ間最適化

プロシージャ間最適化はプログラム全体を対象とするもので、プロシージャの境界やファイルの境界を越えた最適化である。プロシージャ間で関係する部分に働き、局所的な最適化と大域的な最適化の協調によって行われる。主なプロシージャ間最適化としては、インライン展開、プロシージャ間デッドコード削除、プロシージャ間定数伝播、プロシージャ再配置などがある。通常、最適化の前にプロシージャ間解析が必要であり、プロシージャ間エイリアス解析、配列アクセス解析、コールグラフ構築などがある。

プロシージャ間最適化は最近の ^[いつ?]商用コンパイラ（SGI、インテル、マイクロソフト、サン・マイクロシステムズ）にはほとんど備わっている。GCCには長い間^[いつ?]プロシージャ間最適化がないことが弱点とされていた。^{[独自研究?]}しかし、現在ではプロシージャ間最適化を実装している。その他のオープンソースのコンパイラでプロシージャ間最適化を備えたものとして Open64 がある。こちらは研究用や商用にも利用されている。

プロシージャ間最適化（およびそのための解析）には時間とメモリを要するため、デフォルトでは実施しない設定になっているコンパイラが多い。ユーザーは明示的にオプションを指定して最適化することを指示しなければならない。

インライン展開: あるコードがプロシージャを呼び出す場合、そのプロシージャ本体を呼び出し側コード内に展開する。これによりプロシージャ呼び出しのオーバーヘッドを低減し、同時に展開した部分にさらなる最適化を施すことが可能となる。しかし、プロシージャのコードが呼び出し側にコピーされるので、メモリ使用量は増える。一般にインライン展開は小さなプロシージャを何度も呼び出す場合に有効である。

最適化におけるプログラムの表現

コンパイラの最適化処理では、その処理内容に応じて各種表現を使い分けることが多い。以下に代表的な表現を示す。

抽象構文木 (abstract syntax tree): 入力プログラムに近い表現。インライン展開など高水準の最適化を適用する場合に利用する。
静的単一代入形式 (static single assignment form; SSA-form): 各変数の定義がプログラム中で1つのみになるように変換した形式。変数の定義・使用関係が明確化されるという利点がある。ループや条件文における定義値の合流を表現するため、Φ-関数 (phi-function) と呼ばれる特殊な関数を導入する。
3番地コード (three address code): 各文を1つの定義先、2つの参照先の3つ組で表現する形式。複雑な式が簡略化され、命令レベルの表現に近くなるという利点がある。
制御フローグラフ (control-flow graph): プログラムの制御の流れをグラフ表現した形式。類似の表現に、データの流れを表したデータフローグラフ (data-flow graph) などがある。
擬似命令 (pseudo-instruction): 仮想的な機械の命令。

最適化における問題

コンパイラ史の初期、コンパイラによる最適化は人間が手で書いたコードほどよいコードを生成しなかった。コンパイラ技術の進展と共に、コンパイラが人間のプログラマよりもよいコードを生成できるようになってきた。また、人間が最適化技法を駆使して書いたコードをさらに最適化できるオプティマイザも出現したほどである。RISCアーキテクチャやVLIWではコンパイラ最適化は効率的なコードを得るための鍵となっている。というのも、RISCの命令セットは小さく、人間がそれらのスケジュールを手で行ったり、効率的な結果を得るのは困難だからである。実際、それらアーキテクチャの性能はコンパイラの良し悪しに大きく左右される。

しかし、最適化コンパイラは完全ではない。コンパイラがあらゆるソースコードに対して最適なコードを生成することはできない。どんなソースコードに対しても最良の最適化を行うコンパイラの存在を仮定すれば、チューリングマシンの停止問題の解が導かれ、矛盾が生じる。よってそのようなコンパイラは存在しない。さらに、最適化コンパイラ技術にはいくつかの現実的な問題が存在する。

最適化コンパイラは低レベルな局所的な修正を行う。逆に、高レベルでのソースプログラムの非効率さ（例えば、採用しているアルゴリズムの非効率さ）は修正されない。
最近のサードパーティのコンパイラは様々な要求に応えなければならない。そのため、それぞれをそれなりにこなすが、いずれについても最善を尽くしてはいない。
コンパイラは、ある時点ではプログラム全体のごく一部しか見ないのが一般的である。せいぜい1つのモジュールを見る程度であり、一般にはプロシージャ単位でしか見ない。このため、重要な文脈的情報を見落とす可能性がある。
コンパイラ最適化のオーバーヘッドの制約。高度に最適化を行おうとすれば時間がかかる。プロシージャ間の最適化は、そういった意味で非常にコストがかかる。
コンパイラ最適化の各フェーズ間の相互作用。どのようにフェーズを組合わせるのが最適か、どういう順番で行えば時間を節約できるか、という問題がある。

最適化技法を改良する試みは続けられている。1つの試みとして「ポストパス」オプティマイザがある。これは最適化コンパイラの出力である実行ファイルに対してさらに最適化を行うツールである。コンパイラ最適化がプログラムの中間表現に対して作用するのに対して、ポストパス・オプティマイザはアセンブリ言語レベルに対して作用する。しかし、ポストパス・コンパイラにも限界がある。なぜなら、オリジナルのソースコードに存在していた情報の多くは、実行ファイルでは失われているからである。

プロセッサの性能向上はメモリの帯域幅の向上よりも激しい。そのため、たとえ余分な命令を実行しなければならないとしても、使用するメモリ帯域幅を削減するような最適化が有効になってきた。例えば、入れ子ループ最適化や再実体化がそのような最適化の例である。

外部リンク

NULLSTONE Optimization Categories - 主なコンパイラ最適化のカテゴリ
GCC optimizations - GCCに実装されている最適化について論じたレッドハットのページ
Optimization manuals by Agner Fog - x86系プロセッサとその機械語レベルの最適化についての文書
Assembly Optimization Tips by Mark Larson
Citations from CiteSeer