Atlas の力を引き出す (6): コールグラフ

前回の記事では、Atlas が基盤となる制御フロー解析とデータフロー解析をどのように行うかを解説しています。この記事では、Atlas におけるコールグラフを扱います。コールグラフはソフトウェア解析の重要な構成要素であり、コードベース内の関数またはメソッドの間の呼び出し関係を表します。依存関係を理解し、性能上のボトルネックを特定し、再帰を検出し、デッドコードを見つけるために不可欠です。レガシーシステムをリファクタリングする場合でも、性能を最適化する場合でも、潜在的な脆弱性を解析する場合でも、コールグラフはソフトウェアがどのように動作するかをより深く理解するための基盤となる手段です。

Atlas は、インデックス済みのコードベースから呼び出し関係を自動的に抽出し、関数間の相互作用を明確に示すコールグラフを生成します。Atlas が特に強力なのは、これらのコールグラフを必要な精度まで精緻化できることです。たとえば、より深い知見を得るために、Variable Type Analysis のような高度なアルゴリズムを実装できます。これは、強力な Atlas クエリ言語によって可能になります。

この記事では、Atlas におけるコールグラフの基本に焦点を当て、Atlas がコールグラフをどのように表現し、どのように可視化し、どのように処理するかを説明します。

Atlas における呼び出し関係

Atlas は、呼び出し関係を種類 XCSG.Call のエッジで表します。関数 f が関数 g を呼び出す場合、Atlas での表現は、関数 f と g を表す種類 XCSG.Function の 2 つのノードになります。

Atlas におけるコールグラフの例です。関数 dskqopt が関数 resched、ready、freebuf を呼び出し、関数 dskenq が dskqopt を呼び出すことを示しています。dskqopt と freebuf の間のエッジにあるラベル 4 に注目してください。これは、dskqopt 内に freebuf への呼び出し（コールサイト）が 4 つあることを意味します。

Atlas は、呼び出しの多重度、すなわち関数 g が関数 f から何回呼び出されるかも捉えます。言い換えると、コールサイトがいくつあるかです。可視化すると、これはエッジのラベルとして表示されます。言うまでもなく、これは Atlas が呼び出し文と、呼び出される関数との関係も抽出して保存しているためです。

Atlas は「invoke」関係も捉えます。この図は、Atlas がコールサイトをその対象関数へどのように結び付けるかを示しています。

Atlas は、呼び出し文の内部にデータフローのノードを作ります（Atlas が制御フローとデータフローをどのように表現するかについては、こちらをご参照下さい）。このノードの種類は XCSG.CallSite です。このノードは、呼び出しの対象関数を表す関数ノードに接続されます。このエッジの種類は XCSG.InvokedFunction です。関数ポインターを使って呼び出している場合、エッジの種類は XCSG.InvokedPointer となり、関数ポインターを表すノードに接続されます。関数ポインターは、Atlas のデータフローと組み合わせた独自の解析器を書くことで、その後に解決できます。

コールグラフの可視化

Atlas には、コールグラフを可視化する便利な方法が 2 つあります。「Call」Smart View を使う方法と、Atlas Shell で簡単なクエリを書く方法です。

「Call」Smart View を使うには、Atlas の Smart View 画面を開き、「Call」オプションを選択します。そこからソースコードへ移動し、解析したい関数名をクリックします。Smart View には、呼び出し元（その関数を呼び出す関数）と呼び出し先（その関数が呼び出す関数）の両方が表示されます。呼び出し関係を 1 ステップずつ順に展開することもでき、グラフを対話的に調べやすくなります。この方法は、コードの呼び出し構造をすばやく理解するのに最適です。

Atlas Shell は、コールグラフ解析のための簡単なクエリを手早くスクリプトとして書く強力なツールです。Atlas は呼び出し関係をグラフとして表すため、単純な走査クエリで目的のコールグラフを取得できます。

たとえば、次のクエリは、特定の関数 foo を根とする呼び出し木の全体を取得します。

universe.edges(XCSG.Call).forward(functions("foo"))

このクエリは、foo が呼び出すすべての関数と、それらが呼び出す関数とを、その先まで含めて返します。関数の呼び出し関係がどこまで及ぶかを調べる直接的な方法であり、お使いのコードベースをより深く解析するための有用な手法です。

同様に、逆方向のクエリを使うと、特定の関数の呼び出し元をすべて取得できます。たとえば、次のとおりです。

universe.edges(XCSG.Call).reverse(functions("foo"))

このクエリは、foo を呼び出すすべての関数と、その呼び出し元の連鎖を返します。

コールグラフを段階的に調べたい場合、Atlas には forwardStep() と reverseStep() のクエリがあります。これらを使うと、グラフを 1 ステップずつ走査し、それぞれ関数の直接の呼び出し先、または直接の呼び出し元だけを取得できます。この方法は、対象を絞った解析を行う場合や、大規模で複雑なコールグラフを扱う場合に特に有用です。

以上が、Atlas におけるコールグラフの基本です。強力なクエリ言語を用いることで、Atlas はデッドコード検出や再帰検出のような高度な解析を可能にします。これらの機能は、お使いのコードを理解し最適化するうえで、尽きることのない可能性を開きます。これらのより高度な解析については、今後の記事で解説します。どうぞお待ちください。

同様に、逆方向のクエリを使うと、目的の関数の呼び出し元を取得できます。コールグラフを 1 ステップずつ調べたい場合は、forwardStep または reverseStep のクエリを使えます。これらは、それぞれ直接の呼び出し先または呼び出し元だけを取得するからです。

次: 独自の解析器を書く