言語処理工学A 補助プリント2

データーフロー解析について

1. 到達定義(reaching definition)

ある変数xに対する代入を行う可能性があるとき、その文を「xの定義(definition)と呼ぶ。また、ある変数xの値を参照する可能性があるとき、その文を「xの参照」と呼ぶ。ここでは、直接の代入文や参照文意外に、関数や手続き呼び出し文中や引数としての定義や参照、ポインタや同値(Alias)による定義や参照も考慮する必要がある。

ある定義dがフローグラフ中のポイントp(ある文の直前や直後)に到達する(reach)とは、ある実行経路で、dからpに至る経路があって、途中でdを殺す(kill)文がないことをいう。(dが変数xの定義とすると、pに至る途中でxへの代入文がない)

例:略

入力のデータによって、一般にif文などによって実行経路が変わりうる。したがって、到達するか否かは、入力データに依存する。通常データフロー解析では、どのような入力に対しても、「安全な」答えを出す必要がある。そのために控えめな仮定、一つでも到達するような経路があるならば、どのような入力に対しても常に到達する、を設ける。

ある文の集合sに対して新たに生まれる定義の集合をgen(s)、sによって殺される定義の集合をkill(s)で表す。プログラムの基本的な構造に対して、到達する定義の集合がどのように変わるかを、以下に示す。in(s)はsの入り口での到達定義の集合、out(s)は出口での到達定義の集合。

s --- d: a:=b+c gen(s) = {d}

kill(s) = {変数aの定義} - {d}

out(s) = gen(s) (in(s) - kill(s))

s --- s1 ; s2 gen(s) = gen(s2) (gen(s1) - kill (s2))

kill(s) = kill(s2) (kill(s1) - gen(s2))

in(s1) = in(S) in(S2) = out(s1) out(S) = out(s2)

s --- s1 or s2 gen(s) = gen(s1) gen(s2)

kill(s) = kill(s1) kill(s2) 安全のための仮定

in(s1) = in(s) in(s2) = in(s) out(s) = out(s1)out(s2)

s --- loop of s1 gen(s) = gen(s1)

kill(s) = kill(s1)

in(s1) = in(s) out(s1) out(s) = out(s1)

このような規則に従ってプログラムの各文のin, out, kill, genの関係を示したものをデータフロー式と呼ぶ。このデータフロー式を満足させる値が、実際の到達定義集合となる。

この得られた到達定義集合は、一般に冗長である。実際にif文の条件文を良く考えれば決して起こらないような分岐のパターンについても安全のために考慮されている。しかし、分岐条件を理解して分岐パターンを見つけ出すのは至難である。このように分岐条件を考えずに、分岐文の構造のみを見て、プログラムの解析や理解をする手法を、interpretation freeと呼ぶ。

一般化

上記のを一般化すると、

in(B) = out(P)

P a predecessor of B

out(B) = gen(B) (in(B) - kill(B))

データフロー式の解き方

in(B)=φとする。

for each block B do out(B):=gen(B)

change:=true;

while change do begin

change:=false;

for each block B do begin

in(B):= out(P)

P a predecessor of B

oldout:=out(B);

out(B):=gen(B) (in(B) - kill(B));

if out(B) oldout then change:=true

end

end

このプログラムは停止する。なぜか?

例:略

到達定義は、いろいろな用途に利用できる。たとえば、不要な命令の削除、文や式の移動など。

プログラムスライス

プログラム依存グラフ ―――― 制御依存辺(実行の有無の支配関係)

データ依存辺(定義参照関係;到達)

プログラム文の頂点

ある頂点sのある変数xのプログラムスライス

「sから制御依存辺、xのデータ依存辺をさかのぼって到達可能な頂点の集合」

sのxに影響を与える全てのプログラムの断片を集めたもの

そのxだけを計算するのに必要なプログラム、 ―――>プログラムの部品化

デバッグ