● (大域的)データフロー解析

* 流れグラフ

    基本ブロックをnodeとし、
    基本ブロック間の制御関係をedgeとするグラフを、
    流れグラフという。

    プログラムの開始点を含むブロックを開始ブロックという。

    図10.5
	        B1┌────────┐
	          │i := m-1        │
	          │j := n          │
	          │t1:= 4*n        │
	          │v := 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 │
	｜        └────────┘
	｜           ｜           ＼
	｜           ↓            ↓
	｜  B5┌─────┐  B6┌──────┐
	｜    │t6:= 4*i  │    │t11:=4*i    │
	｜    │x := a[t6]│    │x :=a[t11]  │
	｜    │t7:= 4*i  │    │t12:=4*i    │
	｜    │t8:= 4*j  │    │t13:=4*n    │
	｜    │t9:= a[t8]│    │t14:=a[t13] │
	｜    │t10:=4*j  │    │a[t12]:=t14 │
	｜    │a[t10]:=x │    │t15:=4*n    │
	｜    │goto B2   │    │a[t15]:=x   │
	｜    └─────┘    └──────┘
	｜         ／
	 ＼＿＿＿／
		
* 到達定義 (p.743)

    B: 基本ブロック

    gen[B]:  Bの中で生成され、
	     Bの終わりに到達する定義の集合

    kill[B]: Bによって消滅する定義の集合

    Bが一つの文のみからなる場合:

	  ┌──────┐
	B:│d: a := b+c │
	  └──────┘

	gen[B]  = ｛d｝
	kill[B] = Ｄa -｛d｝

	Ｄa: (中間)コードの中の変数aの定義の全体

    Bが複数の文からなる場合:

	  ┌──────┐
	B:│            │
	  │     B1     │
	  │            │
	  ├──────┤
	  │            │
	  │     B2     │
	  │            │
	  └──────┘

	gen[B]  = gen[B2]  ∪ (gen[B1]  - kill[B2])
	kill[B] = kill[B2] ∪ (kill[B1] - gen[B2])

    gen[B]とkill[B]は、以上の性質に従って、
    ブロックを上から順にスキャンすれば求められる。

    in[B]:  Bの先頭に到達する定義の集合
    out[B]: Bの終わりに到達する定義の集合

    in[B]とout[B]はどうやって求めるのか？ (p.750)

    例:

	    a := b+c;
	    if ... then ... else a := d+e;


		d: a := b+c
		   ／  ＼
		 ／      ＼
                 ＼      a := d+e
		   ＼    ／
		     ＼／
		    dはここに到達する
    到達可能性 --- 何らかの経路を通って到達すればよい。
                   (控え目な判断)


	P1    P2    P3
	 ＼   ｜   ／	  
	   ＼ ｜ ／	  
	    ↓↓↓
	  ┌───┐
	  │  B   │
	  └───┘


    (p.761)

	in[B]  = ∪  out[P]
	       PはBの
	       先行ブロック

	out[B] = gen[B] ∪ (in[B] - kill[B])


    in[B]とout[B]が満たすべき等式 --- データの流れ方程式

	前進型       合併型
	^^^^^^	     ^^^^^^
	inから       ∪を使う
	outを求める


	∀B in[B]=φ とする
	∀B out[B]を求める
	∀B in[B]を求める
	∀B out[B]を求める
	    ...
	    ...
	変化がなくなったらやめる


    アルゴリズム10.2 到達定義 (p.762)

	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]も単調に増加する。
    従って、いつかは変化しなくなる(定義の全体が有限だから)。

    ループの実行回数の上限 --- グラフのノード数
    (∵一回ループを回れば定義は一つの辺を伝搬する)
    例(p.764):

		  ┌─────┐
		  │d1: i:=m-1│
		B1│d2: j:=n  │		gen[B1]  = ｛d1,d2,d3｝
		  │d3: a:=u1 │		kill[B1] = ｛d4,d5,d6,d7｝
		  └─────┘
		        ｜
		        ↓
		  ┌─────┐		gen[B2]  = ｛d4,d5｝
		B2│d4: i:=i+1│		kill[B2] = ｛d1,d2,d7｝
		  │d5: j:=j-1│←┐
		  └─────┘  ｜
                     ／ ｜        ｜
                   ／   ｜        ｜
	          ↓    ｜        ｜
	  ┌─────┐｜        ｜		gen[B3]  = ｛d6｝
	B3│d6: a:=u2 │｜        ｜		kill[B3] = ｛d3｝
	  └─────┘｜        ｜
	           ＼   ｜        ｜
	             ＼ ｜        ｜
	              ↓↓        ｜
		  ┌─────┐  ｜		gen[B4]  = ｛d7｝
		B4│d7: i:=u3 │─┘		kill[B4] = ｛d1,d4｝
		  └─────┘


	in[B1]	｛｝		｛｝		｛｝
	out[B1]	｛d1,d2,d3｝	｛d1,d2,d3｝	｛d1,d2,d3｝
	in[B2]	｛｝		｛d1,d2,d3,d7｝	｛d1,d2,d3,d5,d6,d7｝
	out[B2]	｛d4,d5｝	｛d3,d4,d5｝	｛d3,d4,d5,d6｝
	in[B3]	｛｝		｛d4,d5｝	｛d3,d4,d5｝
	out[B3]	｛d6｝		｛d4,d5,d6｝	｛d4,d5,d6｝
	in[B4]	｛｝		｛d4,d5,d6｝	｛d3,d4,d5,d6｝
	out[B4]	｛d7｝		｛d5,d6,d7｝	｛d3,d5,d6,d7｝

	in[B1]	｛｝
	out[B1]	｛d1,d2,d3｝
	in[B2]	｛d1,d2,d3,d5,d6,d7｝
	out[B2]	｛d3,d4,d5,d6｝
	in[B3]	｛d3,d4,d5,d6｝
	out[B3]	｛d4,d5,d6｝
	in[B4]	｛d3,d4,d5,d6｝
	out[B4]	｛d3,d5,d6,d7｝
    例:

		┌─────┐
		│          │
		│    B1    │
		│          │
		└─────┘
	              ｜
	         ＿   ｜
	       ／  ＼ ｜
	     ／	    ↓↓
	    ｜	┌─────┐
	    ｜	│          │
	    ｜	│    B     │
	    ｜	│          │
	    ｜  └─────┘
            ｜     ／ ｜
             ＼＿／   ｜
	              ↓


	in[B]  = out[B1] ∪ gen[B]
	out[B] = gen[B] ∪ (in[B] - kill[B])
* 利用可能な式 (p.765)

    例:

		  ┌─────┐
		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がなければ消滅する。

	e_gen[B]=φ
	┌──────┐↓上からスキャン
	│            │↓
	│            │↓
	│  x := y+z  │↓	1. e_gen[B] := e_gen[B] ∪ ｛y+z｝
	│            │        2. e_gen[B] := e_gen[B] - ｛xを含む式｝
	│            │
	└──────┘


    out[B]: ブロックBの終わりで利用可能な式の集合
    in[B]:  ブロックBの先頭で利用可能な式の集合


	out[B] = e_gen[B] ∪ (in[B] - e_kill[B])

	in[B] = ∩ out[P]	(Bは開始節でない)
	in[B] = φ		(Bは開始節)


    前進  集合積
          ^^^^^^
          先行ブロックすべてて利用可能でないとダメ


    初期値

	out[B] := φ		(Bは開始節)
	out[B] := Ｕ- e_kill[B]	(Bは開始節でない)

	Ｕ: プログラムに現れる式の全体
* 生きている変数 (p.769)

    in[B]  = use[B] ∪ (out[B] - def[B])

    out[B] = ∪  in[S]            
           SはBの
           後続ブロック

	use[B]: 定義より前にBで使われる変数の集合
	def[B]: Bで定義される変数の集合
		(使われる前に定義される)


		┌───────┐  x ∈ use[B]
		│              │
		│              │
		│... := ...x...│
		│              │
		│              │
		│              │
		│x := y+z      │
		│              │
		│              │
		└───────┘


    後進  合併