前のページ 1/4 次のページ

コンパイラ最適化(こんぱいらさいてきか、)とは、実行ファイルを効率化し、実行時間やメモリ使用量などを最小化するようコンパイラの出力を調整する処理である。最も一般的な要求はプログラムの実行時間を最小化することであり、その次に使用するメモリ量を最小化することである。また、携帯可能なコンピュータが増えるにつれて、消費電力を最小化するという最適化も生まれてきた。

一部のコード最適化問題は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より豊富である。コンパイラは各命令や命令の組み合わせによるコストを考慮してコード生成する(命令選択)。

; パイプライン

: パイプラインは、ALUを機能分割して工場の生産ラインのように並べたものと言える。これにより、ALUの各部が異なる命令の異なる処理をすることが可能となる。命令のデコード、アドレスのデコード、メモリフェッチ、レジスタフェッチ、計算、レジスタへの格納などである。ある命令がレジスタへの格納ステージにあるとき、同時に別の命令がレジスタフェッチのステージにあるということになる。パイプラインのあるステージにある命令がもっと先のステージにある未完了の命令の結果を必要とするとき、パイプライン衝突が発生する。パイプライン衝突はパイプラインの停止(ストール)を招き、衝突が解決されるまでCPUは何もできなくなる。

: コンパイラは命令をスケジュールあるいは再配置して、パイプラインの停止が起こりにくくなるようにできる。

; 機能ユニットの数

: 一部のCPUは複数のALUやFPUを備えており、複数の命令を同時に実行できる。同時に実行できる命令の種類には制限があることもあり、各ユニットが実行できる命令の種類も制限がある。これらにはパイプライン衝突と同様の問題が存在する。

: コンパイラはこのような場合も命令をうまく配置して、各機能ユニットがなるべく常に動作するようにスケジュールできる。

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

; キャッシュメモリサイズとタイプ(ダイレクトマップ、n-wayセットアソシアティブ、フルアソシアティブ)

: インライン展開やループ展開などの手法はコードのサイズを増大させ、参照の局所性を損なう。頻繁に実行されるコードの塊がキャッシュに収まらなくなると、性能は劇的に低下する。フルアソシアティブでないキャッシュではキャッシュ上での衝突が発生しやすい。

前のページ 1/4 次のページ

・コンパイラ最適化 page1

・コンパイラ最適化 page2

・コンパイラ最適化 page3

・コンパイラ最適化 page4