処理の流れに関連したFindBugsプラグインを作る2

前回残したTODOの消化。

• 今の理解が正しいなら、各BasicBlockごとにFactを計算しておいてあとでmeetさせるという話になるので、この辺りのロジックを読めば決着は付くだろう。

結論から言うと、当時の理解は正しかった。
ただすべてのBasicBlockのFactを計算しておいてmeetさせる、のではなく、Edgeの流入先BasicBlockのFactを計算するために流入元BasicBlockのFactをmeetさせるという流れだった。calculate all→meet every factではなく、calculate→meet→calculate→meet...という感じ。以下に詳細を述べる。

DataflowAnalysis#meetInto()はDataflow#execute()から呼び出される。meetInto周りのexecuteメソッドの概要はだいたいこんな感じ。

Fact start = analysis.getStartFact(block);
analysis.makeFactTop(start);

Iterator<Edge> predEdgeIter = logicalPredecessorEdgeIterator(block);
while (predEdgeIter.hasNext()) {
  Edge edge = predEdgeIter.next();
  BasicBlock logicalPred = isForwards ? edge.getSource() : edge.getTarget();
  Fact predFact = analysis.getResultFact(logicalPred); // Get the predecessor result fact

  Fact edgeFact = analysis.createFact();
  analysis.copy(predFact, edgeFact); // edgeFact = predFact

  analysis.edgeTransfer(edge, edgeFact);
  analysis.meetInto(edgeFact, edge, start);
}

これはつまり（ForwardのDataflowだと仮定して）ひとつのBasicBlock（Aとする）に流入しているEdgeそれぞれについてEdgeの根本（ひとつ前のBasicBlockのこと、ここでは上流BasicBlockと呼ぶ）のResultFact*1をAのStartFactとmeetさせているということ。AのStartFactはmakeFactTop()メソッドでTopに初期化されていることに注意。

この時点で、startはすべての上流BasicBlockのFactをTopにmeetさせたものになっている。meetの結果がひとつでもBottomになっていれば、このstartもBottomになるだろう。

これでAのStartFactが求められたので、次にAのResultFactを呼び出すことになる。これは単純にtransfer()を呼び出すだけ。

Fact result = analysis.getResultFact(block);
analysis.transfer(block, null, start, result);

以上の流れより、以下の疑問も説明できる。

• BasicAbstractDataflowAnalysis#getStartFactがなんで再帰的に前のBasicBlockを辿らないでいいんだろうという疑問。
  • そもそも、なんでgetStartFactとgetResultFactの実装が同じなんだろう……？

Dataflow#getXxxFact()は状態を記録するためのFactインスタンスを作成する役割を担うもので、そのインスタンスを期待される状態に変更するのはDataflow#getXxxFact()ではなくDataflow#execute()ですね、ということ。

getメソッドの中で結果を遅延初期化するのではなく、getメソッドが記憶領域確保に特化しているイメージ。うーんメソッド名が私には直感的でないかも。

*1:predFact変数の中身＝edgeFact変数の中身。たぶん防御的コピーしている