大域的データフロー解析

大域的データフロー解析
• 流れグラフ
基本ブロックをnodeとし、
基本ブロック間の制御関係をedgeとするグラフを、
流れグラフという。
• 開始ブロック
プログラムの開始点を含むブロック
B1
B5
t6:= 4*i
x := a[t6]
t7:= 4*i
t8:= 4*j
t9:= a[t8]
t10:=4*j
a[t10]:=x
goto B2
i :=
j :=
t1:=
v :=
m-1
n
4*n
a[t1]
B2
i := i+1
t2:= 4*i
t3:= a[t2]
if t3<v goto B2
B3
i := j-1
t4:= 4*i
t5:= a[t4]
if t5<v goto B3
B4
if i>=j goto B6
B6
t11:=4*i
x :=a[t11]
t12:=4*i
t13:=4*n
t14:=a[t13]
a[t12]:=t14
t15:=4*n
a[t15]:=x
到達定義
• B: 基本ブロック
• gen[B]
Bの中で生成され、
Bの終わりに到達する定義の集合
つまり、それ以降に同じ変数への定義はない。
• kill[B]
Bによって消滅する定義の集合
つまり、Bの中で定義される変数への定義で、
gen[B]に含まれないものの集合
B1
B5
t6:= 4*i
x := a[t6]
t7:= 4*i
t8:= 4*j
t9:= a[t8]
t10:=4*j
a[t10]:=x
goto B2
i :=
j :=
t1:=
v :=
m-1
n
4*n
a[t1]
B2
i := i+1
t2:= 4*i
t3:= a[t2]
if t3<v goto B2
B3
i := j-1
t4:= 4*i
t5:= a[t4]
if t5<v goto B3
B4
if i>=j goto B6
kill[B3]
gen[B3]
B6
t11:=4*i
x :=a[t11]
t12:=4*i
t13:=4*n
t14:=a[t13]
a[t12]:=t14
t15:=4*n
a[t15]:=x
到達定義
• in[B]
Bの先頭に到達する定義の集合
• out[B]
Bの終わりに到達する定義の集合
• in[B]とout[B]はどうやって求めるのか？
• 到達可能性
何らかの経路を通って到達すればよい。
(控え目な判断)
B1
B5
t6:= 4*i
x := a[t6]
t7:= 4*i
t8:= 4*j
t9:= a[t8]
t10:=4*j
a[t10]:=x
goto B2
i :=
j :=
t1:=
v :=
m-1
n
4*n
a[t1]
B2
i := i+1
t2:= 4*i
t3:= a[t2]
if t3<v goto B2
in[B2]
B3
i := j-1
t4:= 4*i
t5:= a[t4]
if t5<v goto B3
B6
B4
if i>=j goto B6
t11:=4*i
x :=a[t11]
t12:=4*i
t13:=4*n
t14:=a[t13]
a[t12]:=t14
t15:=4*n
a[t15]:=x
データの流れ方程式
• in[B]とout[B]が満たすべき等式
in[B] = ∪ out[P]
PはBの先行ブロック
out[B] = gen[B] ∪ (in[B] - kill[B])
• 前進型
inからoutを求める。
• 合併型
∪を使う
アルゴリズム（到達定義）
for ∀B do out[B] := gen[B]
change := true
while change do
change := false
for ∀B do
in[B] := ∪ out[P]
oldout := out[B]
out[B] := gen[B] ∪ (in[B] - kill[B])
if out[B]≠oldout then
change := true
アルゴリズム（到達定義）
• あらゆる実行経路を考えている。
• 定義が次第に遠くへ伝搬される。
• in[B]もout[B]も単調に増加する。
• 従って、いつかは変化しなくなる
(定義の全体が有限だから)。
d1: i:=m-1
d2: j:=n
d3: a:=u1
d4: i:=i+1
d5: j:=j-1
d6: a:=u2
d7: i:=u3
d1: i:=m-1
d2: j:=n
d3: a:=u1
d4: i:=i+1
d5: j:=j-1
d1,d2,d3
d4,d5
d6: a:=u2
d6
d7: i:=u3
d7
d1: i:=m-1
d2: j:=n
d3: a:=u1
d4: i:=i+1
d5: j:=j-1
d1,d2,d3
d1,d2,d3,d7
d4,d5,d3
d4,d5
d6: a:=u2
d6,d4,d5
d7: i:=u3
d4,d5,d6
d7,d5,d6
d1: i:=m-1
d2: j:=n
d3: a:=u1
d4: i:=i+1
d5: j:=j-1
d1,d2,d3
d1,d2,d3,d7,d5,d6
d4,d5,d3,d6
d4,d5,d3
d6: a:=u2
d6,d4,d5
d7: i:=u3
d4,d5,d6,d3
d7,d5,d6,d3
d1: i:=m-1
d2: j:=n
d3: a:=u1
d4: i:=i+1
d5: j:=j-1
d1,d2,d3
d1,d2,d3,d7,d5,d6
d4,d5,d3,d6
d4,d5,d3,d6
d6: a:=u2
d6,d4,d5
d7: i:=u3
d4,d5,d6,d3
d7,d5,d6,d3
利用可能な式
B1 t1 := 4*i
B2
?
B3 t2 := 4*i
• ?が i:=... を含まなければ、
B1の4*iはB3で利用可能。
• ?が i:=... を含んでいても、
その後で4*iが計算されればよい。
利用可能な式
• e_gen[B]
ブロックBで計算され、
Bの終わりで利用可能な式の集合
• e_kill[B]
ブロックBで消滅させられる式の集合
例えば、y+zという式は、
yまたはzが定義され、
その下にy+zがなければ消滅する。
利用可能な式
• out[B]
ブロックBの終わりで利用可能な式の集合
• in[B]
ブロックBの先頭で利用可能な式の集合
• 流れ方程式
out[B] = e_gen[B] ∪ (in[B] - e_kill[B])
in[B] = ∩ out[P]
(Bは開始節でない)
in[B] = φ
(Bは開始節)
• 前進
• 集合積
アルゴリズム（利用可能な式）
in[B1] := φ; out[B1] := e_gen[B1]
for B1 と異なる B do
in[B] := U; out[B] := U - e_kill[B];
while 変化がある間 do
for B1 と異なる B do
in[B] := ∩
out[P];
PはBの先行ブロック
out[B] := e_gen[B] ∪ (in[B] - e_kill[B]);
U : プログラムに現れる式の全体
B1: 開始ブロック
生きている変数
• 流れ方程式
in[B] = use[B] ∪ (out[B] - def[B])
out[B] = ∪ in[S]
SはBの後続ブロック
• use[B]
定義より前にBで使われる変数の集合
• def[B]
Bで定義される変数の集合(使われる前に定義され
る)
• 後進
• 合併

Download Report