ここではJavaを解析した際の CallGraph から取得できる情報について説明する

基本的なクラス

CGNode クラス: CallGraphのnode情報

(package: com.ibm.wala.ipa.callgraph)

CallGraph において、1つのメソッドは1つの CGNode として表現される

このとき、1つのメソッドで異なるcontextを持つものは別々の CGNode として表現される

CallGraph に含まれる全ての CGNode は CallGraph#iterator() により取得できる

CallGraph callGraph = builder.makeCallGraph(options, null);
for(CGNode node : callGraph) {
  System.out.println(node.iindex);       // nodeのid
  System.out.println(node.getMethod());  // CGNodeに紐づくメソッド情報(IMethodクラス)
  System.out.println(node.getContext()); // CGNodeに紐づくcontext情報(Contextクラス)
}

IR クラス: メソッドの中間表現情報

(package: com.ibm.wala.ssa)

1つの CGNode には１つの IR が紐づいている

IR クラスはコードの中間表現(Intermediate Representation)の情報を含んでいる

IR ir = node.getIR();
SSAInstruction[] insts = ir.getInstructions(); // 中間表現命令のリスト
SymbolTable symbolTable = ir.getSymbolTable(); // 変数や定数の情報
SSACFG cfg = ir.getControlFlowGraph();         // 制御フローの情報

SSAInstruction クラス: 中間表現の命令1単位の情報

(package: com.ibm.wala.ssa)

1つの中間表現命令は SSAInstruction 1つで表現される

命令には様々な種類があり、それぞれ SSAInstruction の派生クラスで表現される

SymbolTable クラス: 変数や定数等の情報

(package: com.ibm.wala.ssa)

中間表現における変数や定数等の情報は SymbolTable で表現される

中間表現命令を正しく文字列として出力するためには SSAInstruction#toString() に SymbolTable を渡す必要がある

IR ir = node.getIR();
SymbolTable symbolTable = ir.getSymbolTable();
for(SSAInstruction inst : ir.getInstructions() {
  System.out.println(inst.iindex); // 中間表現命令のid
  // 中間表現命令の表示
  System.out.println(inst != null ? inst.toString(symbolTable) : null);
}

ISSABasicBlock インタフェース: 中間表現における基本ブロック1単位の情報

(package: com.ibm.wala.ssa)

メソッド内の中間表現命令は基本ブロック単位で分けられており、 ISSABasicBlock で表現される

このインタフェースには、どの範囲の中間表現命令がこの基本ブロックに含まれるかの情報が含まれる

IR ir = node.getIR();
// IR#getBlocks()で全ての基本ブロックが取得できる
for(ISSABasicBlock bblock : Iterator2Iterable.make(ir.getBlocks())) {
  System.out.printf("basic block %d (%d - %d)\n",
      bblock.getNumber(),                // 基本ブロックのid
      bblock.getFirstInstructionIndex(), // 始めの命令id
      bblock.getLastInstructionIndex()   // 最後の命令id
      );
}

ここで利用している Iterator2Iterable.make() は Iterator オブジェクトを Iterable オブジェクトに変換でき、 foreachが簡単にできるWALAの補助メソッドである

SSACFG クラス: 制御フローの情報

(package: com.iiiibm.wala.ssa)

制御フロー情報は SSACFG で表現されている

基本ブロック間の関係が含まれており SSACFG#getSuccNodes() 等で取得できる

IR ir = node.getIR();
// IRに紐づく制御フロー情報
SSACFG cfg = ir.getControlFlowGraph();
for(ISSABasicBlock bblock : Iterator2Iterable.make(ir.getBlocks())) {
  for(ISSABasicBlock sblock : Iterator2Iterable.make(cfg.getSuccNodes(bblock))) {
    // 基本ブロック間の関係を基本ブロックidで取得
    System.out.printf("BasicBlock %s -> %s\n", bblock.getNumber(), sblock.getNumber());
  }
}

WALAにおける中間表現

中間表現の変数

中間表現中では、基本的にSSA(静的単一代入)形式で表現される

SSAで表現できないもの(フィールド等)については、SSA形式に変換されずそのままの形で表現される

ローカル変数

ローカル変数はSSA形式で表現でき、中間表現中では"v(番号)"という形で表現されている

この番号(WALAではValueNumberという)は命令のidと同じ扱いであり、 IR#getInstructions() において変数のほうが多くなり命令が含まれないValueNumberが存在することもある
(配列の位置は命令のidと対応しており、命令のないidの SSAInstruction は null になっている)

フィールド代入・参照

フィールド代入・参照は、どのオブジェクト の どのフィールド(名) という形で表現される

この表現には SSAInstruction の派生クラス SSAPutInstruction クラス または SSAGetInstruction クラスとして表現される

変数の中間表現の例

解析対象プログラム: VariableSample.java
class VariableSample() {
  public int foo = 10;

  // (v1は"this")
  public void hoge() {
    // inst: v4 = getstatic < Application, Ljava/lang/System, out, <Application,Ljava/io/PrintStream> >
    // => 静的フィールドの参照: v4 = System.out
    // inst: invokevirtual < Application, Ljava/io/PrintStream, println(I)V > v4,v3:#27 @7 exception:v5
    // => メソッド呼出: v4.printf(v3)
    int bar = 27; // => barは"v3" (定数)
    System.out.println(bar);

    // inst: putfield v1.< Application, LVariableSample, foo, <Primordial,I> > = v6:#25
    // => フィールド代入: v1.foo = 25
    foo = 25;

    // inst: v7 = getstatic < Application, Ljava/lang/System, out, <Application,Ljava/io/PrintStream> >
    // inst: v8 = getfield < Application, LVariableSample, foo, <Primordial,I> > v1
    // => フィールド参照: v8 = v1.foo
    // inst: invokevirtual < Application, Ljava/io/PrintStream, println(I)V > v7,v8 @23 exception:v9
    System.out.println(foo);

    // inst: return
  }
  public static void main(String[] args) { new VariableSample().hoge(); }
}

φ関数とπ関数

SSA形式における φ関数 や π関数 は ir.iteratePhis() や ir.iteratePis() で取得できる

これらの命令にはidが割り当てられていない(idが-1になる)

IR ir;
SymbolTable symbolTable = ir.getSymbolTable();
for(SSAInstruction phi : Iterator2Iterable.make(ir.iteratePhis())) {
  System.out.printf("phi: %s\n", phi.toString(symbolTable));
}
for(SSAInstruction pi : Iterator2Iterable.make(ir.iteratePis())) {
  System.out.printf("pi: %s\n", pi.toString(symbolTable));
}

メソッドの引数

メソッドに渡される引数にはValueNumberが割り当てられている

割り当てられているValueNumberは SymbolTable#getParameter() で取得でき、
引数の数は SymbolTable#getNumberOfParameters() で取得できる

この中間表現における、静的でないメソッドの引数の第一引数(つまり"v1")には"this"が渡される

静的メソッドは、メソッドの引数のみになる

SymbolTable symbolTable;
for(int i=0; i<symbolTable.getNumberOfParameters(); ++i) {
  System.out.printf("getParameter(%d) = v%d\n", i, symbolTable.getParameter(i));
}

中間表現の定数

プログラムの定数についても、ValueNumberの1つの値として表現されている

ValueNumberが定数かどうかは SymbolTable#isConstant() や SymbolTable#isStringConstant() 等で判定でき、
定数の値は SymbolTable#getValue() や SymbolTable#getStringValue() 等で取得できる

SymbolTable symbolTable;
// "v10"の文字列定数判定
if(symbolTable.isStringConstant(10)) {
  // "v10"の文字列定数取得
  String value = symbolTable.getStringValue(10);
}

命令の参照・代入関係 (def-use関係)

1つの命令において、参照・代入されるValueNumberの情報は def-use情報として保持されている

ある命令において定義(def)するValueNumberは SSAInstruction#getDef() で取得でき、
その数は SSAInstruction#getNumberOfDefs() で取得できる

また、同様に参照(use)するValueNumberは SSAInstruction#getUse() で取得でき、
その数は SSAInstruction#getNumberofUses() で取得できる

SSAInstruction inst;
for(int i=0; i<inst.getNumberOfDefs(); ++i) {
  System.out.printf("getDef(%d) = v%d\n", i, inst.getDef(i));
}
for(int i=0; i<inst.getNumberOfUses(); ++i) {
  System.out.printf("getUse(%d) = v%d\n", i, inst.getUse(i));
}

中間表現とソースコードの対応関係

ある中間表現 SSAInstruction がソースコードのどこに対応するかは IMethod#getSourcePosition() を利用することで取得できる

SSAInstruction inst;
if(inst.iindex != -1) {
  IMethod.SourcePosition sp = node.getMethod().getSourcePosition(inst.iindex);
  if(sp != null) {
    // 中間表現命令が対応する開始行を取得
    System.out.printf("%s (FirstLine: %d)\n", inst.toString(symbolTable), sp.getFirstLine());
  }
}

メソッド間の呼び出し関係

CallGraph内の CGNode は呼び出し関係で繋がっている

呼び出し先・呼び出し元の CGNode

CGNode#getSuccNodes() と CGNode#getPredNodes() で呼び出し先・呼び出し元の CGNode が取得できる

CGNode node;
// 呼び出し先のCGNodeを取得
for(CGNode succNode : Iterator2Iterable.make(callGraph.getSuccNodes(node))) {
  System.out.printf("succ nodes %s\n", succNode.getMethod());
}
// 呼び出し元のCGNodeを取得
for(CGNode predNode : Iterator2Iterable.make(callGraph.getPredNodes(node))) {
  System.out.printf("pred nodes %s\n", predNode.getMethod());
}

メソッドを呼び出す中間表現命令

CGNode の呼び出しを行う中間表現命令を取得するには CallGraph#getPossibleSites() を利用する

このメソッドで CallSiteReference インスタンスが取得できるため、 あとは呼び出し元の CGNode に含まれる IR#getCalls() で取得できる

SSAAbstractInvokeInstruction クラスは SSAInstruction の派生クラスである

IR ir = node.getIR();
SymbolTable symbolTable = ir.getSymbolTable();
for(CGNode succNode : Iterator2Iterable.make(callGraph.getSuccNodes(node))) {
  // node --> succNode となる CallSiteReference を取得
  for(CallSiteReference callSite : Iterator2Iterable.make(callGraph.getPossibleSites(node, succNode))) {
    // CallSiteReference に対応する呼び出し命令を取得
    SSAAbstractInvokeInstruction[] invokes = ir.getCalls(callSite);
    for(SSAAbstractInvokeInstruction invoke : invokes) {
      System.out.printf("invoke: %s\n", invoke.toString(symbolTable));
    }
  }
}

逆に中間表現命令から呼び出し先の CGNode を取得するためには、 SSAAbstractInvokeInstruction#getCallSite() から CallSiteReference を取得し、 CallGraph#getPossibleTargets() で取得する

SSAAbstractInvokeInstruction invoke;
// 呼び出し命令に対応する1つの CallSiteReference を取得
CallSiteReference callSite = invoke.getCallSite();
for(CGNode targetNode : callGraph.getPossibleTargets(node, callSite)) {
  System.out.printf("target node %s\n", targetNode.getMethod());
}