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 のクエリを使えます。これらは、それぞれ直接の呼び出し先または呼び出し元だけを取得するからです。

次: 独自のアナライザを書く