コンパイラ最適化
メモリへのアクセスは(CPU性能に比較して)益々高価につくようになってきており、これはキャッシュメモリも程度は違うが同様である。そのため、頻繁に使用するものはまずレジスタに置き、次にキャッシュ、それでも足りない場合は主記憶、さらにはディスクとなるようメモリ階層を考慮した最適化をする。
式の構文木を構成しなおして、式の評価に必要とされるリソースを最小化する。
レジスタが多ければ多いほど、性能の最適化が容易になる場合がある。レジスタが多ければ局所変数をコールスタック上ではなくレジスタに割り当てられる割合がより高くなる。一時的な結果をレジスタに残すことでメモリの読み書きをする回数を減らすことができる。
抽象的な概念(ループ、オブジェクト、構造体など)に関する最適化はコンパイラが対象としているマシンとは関係なく実施できる。しかし、効果的な最適化の多くは対象プラットフォーム特有の機能を考慮したものであることが多い。
マシン依存の最適化の具体例を示す。レジスタに0を設定する最もシンプルな方法は、命令内で 0 という定数(イミディエート値)をレジスタに設定することである。別のより技巧的な方法では、レジスタを自分自身とのXORの演算結果で置き換える方法がある。どちらの方法を利用するかはコンパイラ次第である。多くのRISCの場合、どちらの方法でも命令長と実行時間に違いはない。インテルx86系などでは、XORを使った方法がより短く速い。これはイミディエート値をデコードする必要がなく、内部のimmediate operand registerを使わないため。またXOR命令がレジスタの依存関係によってパイプライン停止を招くことがあるが、自分自身のXORではパイプラインは停止しない。
入れ子になったループで、内側のループと外側のループを入れ替える。ループ変数群が配列のインデックスであった場合、この最適化で参照の局所性を高めることができる場合もある(配列の並び方に依存する)。
豊富なアドレッシングモードのあるCISCアーキテクチャでは、同じ操作を行う複数の方法が存在することが多く、各手法で命令は全く異なる。命令選択では、低レベルな中間表現を命令に置き換える際にどの命令にするのが最も効率的かを判断して選択する。例えば、MC68000系のプロセッサでは、"lea 25(a1,d5*4), a0" といった複雑なアドレッシングモードが使われ、1命令でかなり複雑な演算が行われる。
コンパイラ史の初期、コンパイラによる最適化は人間が手で書いたコードほどよいコードを生成しなかった。コンパイラ技術の進展と共に、コンパイラが人間のプログラマよりもよいコードを生成できるようになってきた。また、人間が最適化技法を駆使して書いたコードをさらに最適化できるオプティマイザも出現したほどである。RISCアーキテクチャやVLIWではコンパイラ最適化は効率的なコードを得るための鍵となっている。というのも、RISCの命令セットは小さく、人間がそれらのスケジュールを手で行ったり、効率的な結果を得るのは困難だからである。実際、それらアーキテクチャの性能はコンパイラの良し悪しに大きく左右される。
しかし、最適化コンパイラは完全ではない。コンパイラがあらゆるソースコードに対して最適なコードを生成することはできない。どんなソースコードに対しても最良の最適化を行うコンパイラの存在を仮定すれば、チューリングマシンの停止問題の解が導かれ、矛盾が生じる。よってそのようなコンパイラは存在しない。 さらに、最適化コンパイラ技術にはいくつかの現実的な問題が存在する。
最適化コンパイラは低レベルな局所的な修正を行う。逆に、高レベルでのソースプログラムの非効率さ(例えば、採用しているアルゴリズムの非効率さ)は修正されない。
最近のサードパーティのコンパイラは様々な要求に応えなければならない。そのため、それぞれをそれなりにこなすが、いずれについても最善を尽くしてはいない。
命令スケジューリングはパイプライン化プロセッサでは重要な最適化技法であり、パイプラインハザードの発生を最小にするため、プログラムの意味を変えない範囲での命令の並べ替えによって行う。