コールグラフ
コールグラフ (マルチグラフとも呼ばれる) とは、コンピュータプログラムのサブルーチン同士の呼び出し関係を表現した有向グラフである。具体的には、各ノードが手続きを表現し、各エッジ(f,g)は手続きfが手続きgを呼び出すことを示す。従って、循環したグラフは再帰的な関数呼び出しを示す。
コールグラフはプログラムの初歩的な解析の結果であり、プログラムを人間が可読なものにするため、あるいはたとえば手続き間の変数の追跡を行う解析といった発展的な解析のための基礎として用いることができる。コールグラフの簡単な利用方法は、一度も呼び出されない関数を見つけることである。
コールグラフは 動的でも静的でもありうる。動的なコールグラフはプログラムの実行結果の記録、たとえばプロファイラの出力である。従って、動的なコールグラフは正確であるが、プログラムの一度の実行結果を記述できるのみである。正確な静的コールグラフは非決定論的であり、静的なコールグラフ抽出の アルゴリズムは一般的に過剰な見積もりに基づいている。つまり、実際に生じる各呼び出し関係もグラフ内に表現されるが、プログラムの実際の動作では一度も生じないいくつかの呼び出し関係も表現される。
コールグラフは正確さによって異なる形で表現することができる。