コールグラフ

コールグラフ (マルチグラフとも呼ばれる) とは、コンピュータプログラムのサブルーチン同士の呼び出し関係を表現した有向グラフである。具体的には、各ノードが手続きを表現し、各エッジ(f,g)は手続きfが手続きgを呼び出すことを示す。従って、循環したグラフは再帰的な関数呼び出しを示す。 コールグラフはプログラムの初歩的な解析の結果であり、プログラムを人間が可読なものにするため、あるいはたとえば手続き間の変数の追跡を行う解析といった発展的な解析のための基礎として用いることができる。コールグラフの簡単な利用方法は、一度も呼び出されない関数を見つけることである。 コールグラフは 動的でも静的でもありうる。動的なコールグラフはプログラムの実行結果の記録、たとえばプロファイラの出力である。従って、動的なコールグラフは正確であるが、プログラムの一度の実行結果を記述できるのみである。正確な静的コールグラフはであり、静的なコールグラフ抽出のアルゴリズムは一般的に過剰な見積もりに基づいている。つまり、実際に生じる各呼び出し関係もグラフ内に表現されるが、プログラムの実際の動作では一度も生じないいくつかの呼び出し関係も表現される。 コールグラフは正確さによって異なる形で表現することができる。より正確なコールグラフは長い計算時間と大きなメモリ消費量を代償として、たとえばプロファイラの出力結果などの形式により、実際のプログラムの振る舞いより正確に見積もることができるよう表現することができる。最も正確なコールグラフは「コンテキストを理解した」コールグラフ、すなわち各手続きについて手続きが呼び出されるコールスタックごとに別々のノードを持つようにしたものである。完全に「コンテキストを理解した」コールグラフは生成に膨大なメモリを消費するが計算は簡単に行うことができる。大規模なプログラムでは計算時間がかかりすぎるため、完全に「コンテキストを理解した」コールグラフを静的に求めることはできない。最も正確さが低いコールグラフは「コンテキストを理解しない」ものであり、各手続きについてノードを一つしか持たない。 動的なディスパッチを備えるJavaやC++などの言語では、静的なコールグラフを正確に求めるためにはエイリアス解析の結果を必要とする。逆に言えば、正確なエイリアスを求めるためにはコールグラフが必要である。静的な解析システムは二つを同時に求めることで、この相互に相手を必要とする問題(無限後退)を解決する。 コールグラフという用語はコンパイラやバイナリ変換のコミュニティでよく用いられる。