大域的データフロー解析 流れグラフ 開始ブロック 基本ブロックをnodeとし、 基本ブロック間の制御関係をedgeとするグラフを、

Presentation on theme: "大域的データフロー解析 流れグラフ 開始ブロック 基本ブロックをnodeとし、 基本ブロック間の制御関係をedgeとするグラフを、"— Presentation transcript:

1 大域的データフロー解析 流れグラフ 開始ブロック 基本ブロックをnodeとし、 基本ブロック間の制御関係をedgeとするグラフを、
流れグラフという。 開始ブロック プログラムの開始点を含むブロック

2 B1 B2 B3 B5 B6 B4 i := m-1 j := n t1:= 4*n v := a[t1] i := i+1
t3:= a[t2] if t3<v goto B2 B3 B5 i := j-1 t4:= 4*i t5:= a[t4] if t5<v goto B3 B6 t6:= 4*i x := a[t6] t7:= 4*i t8:= 4*j t9:= a[t8] t10:=4*j a[t10]:=x goto B2 t11:=4*i x :=a[t11] t12:=4*i t13:=4*n t14:=a[t13] a[t12]:=t14 t15:=4*n a[t15]:=x B4 if i>=j goto B6

3 到達定義 B: 基本ブロック gen[B] kill[B] Bの中で生成され、 Bの終わりに到達する定義の集合
つまり、それ以降に同じ変数への定義はない。 kill[B] Bによって消滅する定義の集合 つまり、Bの中で定義される変数への定義で、 gen[B]に含まれないものの集合

4 B1 kill[B3] B2 gen[B3] B3 B5 B6 B4 i := m-1 j := n t1:= 4*n v := a[t1]
i := i+1 t2:= 4*i t3:= a[t2] if t3<v goto B2 gen[B3] B3 B5 i := j-1 t4:= 4*i t5:= a[t4] if t5<v goto B3 B6 t6:= 4*i x := a[t6] t7:= 4*i t8:= 4*j t9:= a[t8] t10:=4*j a[t10]:=x goto B2 t11:=4*i x :=a[t11] t12:=4*i t13:=4*n t14:=a[t13] a[t12]:=t14 t15:=4*n a[t15]:=x B4 if i>=j goto B6

5 到達定義 in[B] out[B] in[B]とout[B]はどうやって求めるのか？ 到達可能性 Bの先頭に到達する定義の集合
何らかの経路を通って到達すればよい。 (控え目な判断)

6 B1 B2 in[B2] B3 B5 B6 B4 i := m-1 j := n t1:= 4*n v := a[t1] i := i+1
t3:= a[t2] if t3<v goto B2 B3 B5 i := j-1 t4:= 4*i t5:= a[t4] if t5<v goto B3 B6 t6:= 4*i x := a[t6] t7:= 4*i t8:= 4*j t9:= a[t8] t10:=4*j a[t10]:=x goto B2 t11:=4*i x :=a[t11] t12:=4*i t13:=4*n t14:=a[t13] a[t12]:=t14 t15:=4*n a[t15]:=x B4 if i>=j goto B6

7 データの流れ方程式 in[B]とout[B]が満たすべき等式 前進型 合併型 in[B] = ∪ out[P] PはBの先行ブロック
out[B] = gen[B] ∪ (in[B] - kill[B]) 前進型 inからoutを求める。 合併型 ∪を使う

8 アルゴリズム（到達定義） 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

9 アルゴリズム（到達定義） あらゆる実行経路を考えている。 定義が次第に遠くへ伝搬される。 in[B]もout[B]も単調に増加する。
従って、いつかは変化しなくなる (定義の全体が有限だから)。

10 d1: i:=m-1 d2: j:=n d3: a:=u1 d4: i:=i+1 d5: j:=j-1 d6: a:=u2 d7: i:=u3

11 d1: i:=m-1 d2: j:=n d3: a:=u1 d1,d2,d3 d4: i:=i+1 d5: j:=j-1 d4,d5 d6: a:=u2 d6 d7: i:=u3 d7

12 d1: i:=m-1 d2: j:=n d3: a:=u1 d1,d2,d3 d1,d2,d3,d7 d4: i:=i+1 d5: j:=j-1 d4,d5,d3 d4,d5 d6: a:=u2 d6,d4,d5 d4,d5,d6 d7: i:=u3 d7,d5,d6

13 d1: i:=m-1 d2: j:=n d3: a:=u1 d1,d2,d3 d1,d2,d3,d7,d5,d6 d4: i:=i+1 d5: j:=j-1 d4,d5,d3,d6 d4,d5,d3 d6: a:=u2 d6,d4,d5 d4,d5,d6,d3 d7: i:=u3 d7,d5,d6,d3

14 d1: i:=m-1 d2: j:=n d3: a:=u1 d1,d2,d3 d1,d2,d3,d7,d5,d6 d4: i:=i+1 d5: j:=j-1 d4,d5,d3,d6 d4,d5,d3,d6 d6: a:=u2 d6,d4,d5 d4,d5,d6,d3 d7: i:=u3 d7,d5,d6,d3

15 利用可能な式 ?が i:=... を含まなければ、 B1の4*iはB3で利用可能。 ?が i:=... を含んでいても、
t1 := 4*i B2 ? B3 t2 := 4*i ?が i:=... を含まなければ、 B1の4*iはB3で利用可能。 ?が i:=... を含んでいても、 その後で4*iが計算されればよい。

16 利用可能な式 e_gen[B] e_kill[B] ブロックBで計算され、 Bの終わりで利用可能な式の集合
例えば、y+zという式は、 yまたはzが定義され、 その下にy+zがなければ消滅する。

17 利用可能な式 out[B] in[B] 流れ方程式 前進 集合積 ブロックBの終わりで利用可能な式の集合
out[B] = e_gen[B] ∪ (in[B] - e_kill[B]) in[B] = ∩ out[P] (Bは開始節でない) in[B] = φ (Bは開始節) 前進 集合積

18 アルゴリズム（利用可能な式） U : プログラムに現れる式の全体 B1: 開始ブロック
in[B1] := φ; out[B1] := e_gen[B1] for B1 と異なる B do in[B] := U; out[B] := U - e_kill[B]; while 変化がある間 do in[B] := ∩ out[P]; PはBの先行ブロック out[B] := e_gen[B] ∪ (in[B] - e_kill[B]); U : プログラムに現れる式の全体 B1: 開始ブロック

19 生きている変数 流れ方程式 use[B] def[B] 後進 合併 in[B] = use[B] ∪ (out[B] - def[B])
out[B] = ∪ in[S] SはBの後続ブロック use[B] 定義より前にBで使われる変数の集合 def[B] Bで定義される変数の集合(使われる前に定義される) 後進 合併