データーフロー解析について
1. 到達定義(reaching definition)
ある変数ｘに対する代入を行う可能性があるとき、その文を「ｘの定義」(definition)と呼ぶ。また、ある変数ｘの値を参照する可能性があるとき、その文を「ｘの参照」と呼ぶ。ここでは、直接の代入文や参照文意外に、関数や手続き呼び出し文中や引数としての定義や参照、ポインタや同値(Alias)による定義や参照も考慮する必要がある。
ある定義ｄがフローグラフ中のポイントｐ（ある文の直前や直後）に到達する(reach)とは、ある実行経路で、ｄからｐに至る経路があって、途中でｄを殺す(kill)文がないことをいう。（ｄが変数ｘの定義とすると、ｐに至る途中でｘへの代入文がない）
例：略
入力のデータによって、一般にif文などによって実行経路が変わりうる。したがって、到達するか否かは、入力データに依存する。通常データフロー解析では、どのような入力に対しても、「安全な」答えを出す必要がある。そのために控えめな仮定、一つでも到達するような経路があるならば、どのような入力に対しても常に到達する、を設ける。
ある文の集合ｓに対して新たに生まれる定義の集合をgen(s)、ｓによって殺される定義の集合をkill(s)で表す。プログラムの基本的な構造に対して、到達する定義の集合がどのように変わるかを、以下に示す。in(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
このプログラムは停止する。なぜか？
例：略
到達定義は、いろいろな用途に利用できる。たとえば、不要な命令の削除、文や式の移動など。
２ プログラムスライス
プログラム依存グラフ ―――― 制御依存辺（実行の有無の支配関係）
データ依存辺（定義参照関係；到達）
プログラム文の頂点
ある頂点ｓのある変数ｘのプログラムスライス
「ｓから制御依存辺、ｘのデータ依存辺をさかのぼって到達可能な頂点の集合」
ｓのｘに影響を与える全てのプログラムの断片を集めたもの
そのｘだけを計算するのに必要なプログラム、 ―――＞プログラムの部品化
デバッグ