インライン展開
インライン展開(インラインてんかい、英: inline expansion または 英: inlining)とは、コンパイラによる最適化手法の1つで、関数を呼び出す側に呼び出される関数のコードを展開し、関数への制御転送をしないようにする手法。これにより関数呼び出しに伴うオーバーヘッドを削減する。特に小さくて頻繁に呼ばれる関数では効果的であり、呼び出し側にそのコードを展開することで定数畳み込みなどのさらなる最適化を施せる可能性が生じる。問題点はバイナリコードが一般に肥大化する結果を招く点であり、参照の局所性を損なうほどだったり、リソースの限界を超えると性能がかえって悪化することになる。
関数型言語の世界では、インライン展開をβ変換とも呼び、関数型言語の理論的基盤となっているラムダ計算の用語としてよく使われる。
実装
[編集]コンパイラがある関数をインライン展開するとしたとき、それを実施するのは一般に単純である。インライン展開は通常高レベルな中間表現(例えば抽象構文木)の段階で行われるが、言語間のクロス・インライン展開の場合は低レベルな中間表現でインライン展開を行う。いずれにしても、引数を単純に計算して、それを何らかの変数に格納し、関数の本体を呼び出し側に展開する。
インライン展開はリンク時に行うこともでき、例えばライブラリ関数などのソースが手元にない関数のインライン展開に使われる。実行時には動的プロファイリング情報を採取することでどの関数をインライン展開すべきかを決定することができる(Javaの HotSpot コンパイラなど)。
以下にC言語のソースについて「人間の手」でインライン展開を試みた例を示す:
int pred(int x) {
if (x == 0)
return 0;
else
return x - 1;
}
- インライン展開前:
int f(int y) {
return pred(y) + pred(0) + pred(y + 1);
}
- インライン展開後:
int f(int y) {
int temp = 0;
if (y == 0) temp += 0; else temp += y - 1;
if (0 == 0) temp += 0; else temp += 0 - 1;
if ((y + 1) == 0) temp += 0; else temp += (y + 1) - 1;
return temp;
}
これは単なる例である。実際のC言語ではパラメータ付きマクロやインライン関数機能を使ってコンパイラ(あるいはプリプロセッサ)にこのような変換をさせる。以下では、このコードに施せる最適化についても説明する。
利点
[編集]インライン展開は関数呼び出しのオーバヘッドを削減する最適化手法であるが、「変換を可能にする」手法としても重要である。例えば、関数本体を呼び出し側でインライン展開したとき、その呼び出し時の引数が定数であったら、そのコードは最適化によって大幅に変換可能となる。また、関数の中で引数をチェックして分岐している部分があったとき、引数が定数であることがコンパイル時に分かっていれば、分岐の通らない方のコードはデッドコード削除の対象となる。ループ内での呼び出しだった場合、その関数内にループ不変な文があれば、ループ内不変式移動が可能となる。さらに変数は帰納的変数除去の対象となるかもしれない。
上掲のC言語の例にも、最適化できる部分がある。次のような段階を踏んで最適化を行う:
temp += 0
は何もしていないので、削除できる。0 == 0
という条件式は常に真なので、if 文の then 部は省略できる。(y + 1) == 0
という条件式はy == -1
と等価である。(y + 1) - 1
という式は単にy
となる。y
とy + 1
が同時にゼロには決してならない。したがって、三方向への分岐を残さなければならない。
最適化を施した関数は以下のようになる:
int f(int y) {
if (y == 0)
return y; /* or return 0 */
else if (y == -1)
return y - 1; /* or return -2 */
else
return y + y - 1;
}
欠点
[編集]インライン展開は性能を悪化させるような問題もいくつか存在する。
- 組み込みシステムなど、コードのサイズが速度よりも重要な場合、インライン展開はごく小さい関数以外では使用できない。
- コードサイズの増加によって、コードによってはキャッシュメモリに収まらなくなる場合があり、キャッシュミスによる性能低下を引き起こす。
- インライン展開された部分で使う変数が加わることでレジスタの消費が増えると、場合によってはレジスタが足りなくなり、新たなメモリアクセスが増えてしまう。(レジスタ割り付け)
- 言語によってはコードの可読性が落ちる。
- 言語によってはプログラムがプロシージャの引数に付加的仮定をすることを可能にするかもしれないが、インライン展開されているとそれが不可能になる。
- コードサイズが大きくなりすぎると、メモリサイズなどのリソース限界を超えてしまうことがあり、動作不能になったり、スラッシングを起こしたりする。
一般にコンパイラはこれらの問題点を意識していて、性能が向上すると予測される関数だけをインライン展開するよう努力する。
また、性能ではなくデバッグに支障のある問題も存在する。
- 関数をインライン展開してしまうとブレークポイントを関数(callee側)にセットしても、その場所には制御が移らないため、ブレークしない。デバッグ時、注意が必要である。
展開対象の選択と言語サポート
[編集]多くのコンパイラは効果があるならインライン展開を積極的に行う。これにより実行ファイルは大きくなるが、メモリの大容量化がCPU性能向上を上回るようになって、これがより効果的となったのである。このような自動インライン展開は、一般に関数自体が小さい関数型言語やオブジェクト指向言語では、従来からの最適化手法を使うためにも重要である。
命令型プログラミング言語では、関数(ルーチン)が比較的大きいため、インライン展開の方針も異なる。通常明示された関数かキーとなる関数のみをインライン展開し、言語の機能であるインライン関数や、ソースレベルの機能であるパラメータ付きマクロを使う。いずれにしてもプログラマがインライン展開すべき関数を指定するのだが、コンパイラは指定された関数をインライン展開できない(しない)場合もある。
関連項目
[編集]外部リンク
[編集]- "Eliminating Virtual Function Calls in C++ Programs" by Gerald Aigner and Urs Hölzle
- "Reducing Indirect Function Call Overhead In C++ Programs" by Brad Calder and Dirk Grumwald
- ALTO - A Link-Time Optimizer for the DEC Alpha
- "Advanced techniques" by John R. Levine
- "Inlining Semantics for Subroutines which are Recursive" by Henry G. Baker
- "Whole Program Optimization with Visual C++ .NET" by Brandon Bray