netail.net

_ 論文 ▲

プログラム依存グラフの計算簡略化のための方法を探して論文読み．

Mark Harman, Rob Hierons, Sebastian Danicic, Mike Laurence, John Howroyd and Chris Fox: Node Coarsening Calculi for Program Slicing.

8th IEEE Working Conference on Reverse Engineering (WCRE 2001). 2-5 October 2001, Stuttgart, Germany, 2001. Pages 25-34.

制御フローグラフに対して，隣接したノードを集約していくことでノード数を減らしていこうというもの．そのときに，一貫性を維持した中で一番良い結果を出すような方法を考えましょう，というもの．集約時に少しだけ不正確な結果が加わるが，それでも集約を重視するという姿勢．

R-Coarsening という手法をケーススタディ形式で紹介している．

Rb = ( I, D, d, R )
I = ノードのラベル集合
D = そのノードが実行されたときに必ず定義される変数
d = そのノードで定義されることがある変数（Dの要素もすべて含む）
R = 参照される変数

という四項組を定義して，

Assignment: v := f(R) --> Rb({f}, {v}, {v}, R) 
b1 = Rb(I1, D1, d1, R1), b2 = Rb(I2, D2, d2, R2) 

Sequence: b1;b2 
  --> Rb(I1∪I2, D1∪D2, d1∪d2, R1∪(R2-D1))
 
Conditional: if p(R) then b1 else b2 
  --> Rb({p}∪I1∪I2, D1∩D2, d1∪d2, R∪R1∪R2) 
  注: D = D1∩D2 なのは，if なので分岐の両方でも更新されるものだけということ.
 
Loop: while p(R') do b 
  --> Rb( {p}∪I,φ,d, R∪R') 

というようにルールを定義する．論文ではこれが一貫性があって，しかもできうる限りでは最適であるという証明も付属している．ただ，Minimalではない(スライス結果に関係ない文が含まれることがある）．

関連研究としてCFGのグラフ上での変換作業が載っていて，グラフ操作では不必要に不正確になる可能性があることに言及している．

ちなみに，この粗粒度化の方法自体の適用についてどのくらい時間がかかるかは不明．どのくらい粗粒度化するのかとかに依存か．制御フローグラフ構築時にいきなりこれを意識しながら作業すれば，そんなにコストはかからないかもしれない？

そのうち引用することになりそう．