【正文】 := x … 用 y代替 x的前提是： ? 語句 s是到達 u的唯一的 x定值 ? 從 s到 u的每條路徑，包括穿過 u若干次的路徑上，沒有對 y的賦值 復寫傳播 建立新的數(shù)據(jù)流分析方程來解決第二個前提 in [B] 和 out [B]： 復寫語句 s: x := y的集合 c_gen [B]： 出現(xiàn)在塊 B中的 s: x := y，且塊 B中該語句的后面沒有對 x或 y的定值 c_kill [B]： 不在塊 B中 的 s: x := y， 且 x或 y在塊 B中賦值 復寫傳播 建立新的數(shù)據(jù)流分析方程來解決第二個前提 in [B] 和 out [B]： 復寫語句 s: x := y的集合 c_gen [B]： 出現(xiàn)在塊 B中的 s: x := y ，且塊 B中該語句的后面沒有對 x或 y的定值 c_kill [B]： 不在塊 B中 的 s: x := y， 且 x或 y在塊 B中賦值 out [B] = c_gen [B] ? (in [B] ? c_kill [B]) in [B] = ? out [P] （ B不是初始塊） P是 B的前驅(qū) in[ B1 ] = ? （ B1是初始塊） 復寫傳播 c_gen [B1] = {x := y} c_gen [B3] = {x := z} c_kill [B1] = {x := z} c_kill [ B2] = {x := y} c_kill [B3] = {x := y} in [B1]= ?, in [B2] = in [B3] = out [B1] = {x := y} out [B2] =?, out [B3] = in [B4] = out [B4] = {x := z} in [B5] = out [B2] ? out [B4] = ? x := y := x := x y := x := z B4 B5 B3 B2 B1 尋找循環(huán)不變計算 輸入 循環(huán) L， 對 L的每個三地址語句，有 ud鏈可用。 全路徑數(shù)據(jù)流分析 數(shù)據(jù)流問題也可以用全路徑（ all path） 形式來解決，使所需的性質(zhì)在所有可能的路徑都滿足。 這種數(shù)據(jù)流問題被稱為任意路徑問題 。 OUT [Bi] : = ( IN[Bi] – KILL [Bi] ) ? GEN [Bi ] end end end en d 到達 定值的迭代算法 到達 定值的迭代算法 gen [B]： B中能到達 B的結(jié)束點的定值語句 kill [B]： 整個程序中決不會到達 B結(jié)束點的定值 in [B]： 能到達 B的開始點的定值集合 out [B]： 能到達 B的結(jié)束點的定值集合 兩組方程（根據(jù) gen和 kill求解 in和 out） in [ B ] = ? out [P] P是 B的前驅(qū) out [B] = gen [B]? (in [B] ? kill [B]) 定值的迭代算法 in [B] B1 000 0000 B2 000 0000 B3 000 0000 B4 000 0000 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i := m ?1 d2: j := n d3: a := u1 B1 B2 d7: i := u3 B4 d4: i := i + 1 d5: j := j ? 1 d6: a := u2 B3 定值的迭代算法 in [B] out [B] B1 000 0000 111 0000 B2 000 0000 000 1100 B3 000 0000 000 0010 B4 000 0000 000 0001 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i := m ?1 d2: j := n d3: a := u1 B1 B2 d7: i := u3 B4 d4: i := i + 1 d5: j := j ? 1 d6: a := u2 B3 定值的迭代算法 in [B] out [B] B1 000 0000 111 0000 B2 111 0001 000 1100 B3 000 0000 000 0010 B4 000 0000 000 0001 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i := m ?1 d2: j := n d3: a := u1 B1 B2 d7: i := u3 B4 d4: i := i + 1 d5: j := j ? 1 d6: a := u2 B3 定值的迭代算法 in [B] out [B] B1 000 0000 111 0000 B2 111 0001 001 1100 B3 000 0000 000 0010 B4 000 0000 000 0001 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i := m ?1 d2: j := n d3: a := u1 B1 B2 d7: i := u3 B4 d4: i := i + 1 d5: j := j ? 1 d6: a := u2 B3 定值的迭代算法 in [B] out [B] B1 000 0000 111 0000 B2 111 0001 001 1100 B3 001 1100 000 0010 B4 000 0000 000 0001 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i := m ?1 d2: j := n d3: a := u1 B1 B2 d7: i := u3 B4 d4: i := i + 1 d5: j := j ? 1 d6: a := u2 B3 定值的迭代算法 in [B] out [B] B1 000 0000 111 0000 B2 111 0001 001 1100 B3 001 1100 000 1110 B4 000 0000 000 0001 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i := m ?1 d2: j := n d3: a := u1 B1 B2 d7: i := u3 B4 d4: i := i + 1 d5: j := j ? 1 d6: a := u2 B3 全局數(shù)據(jù)流分析介紹 in [B] out [B] B1 000 0000 111 0000 B2 111 0001 001 1100 B3 001 1100 000 1110 B4 001 1110 000 0001 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i := m ?1 d2: j := n d3: a := u1 B1 B2 d7: i := u3 B4 d4: i := i + 1 d5: j := j ? 1 d6: a := u2 B3 定值的迭代算法 in [B] out [B] B1 000 0000 111 0000 B2 111 0001 001 1100 B3 001 1100 000 1110 B4 001 1110 001 0111 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i := m ?1 d2: j := n d3: a := u1 B1 B2 d7: i := u3 B4 d4: i := i + 1 d5: j := j ? 1 d6: a := u2 B3 定值的迭代算法 in [B] out [B] B1 000 0000 111 0000 B2 111 0111 001 1100 B3 001 1100 000 1110 B4 001 1110 001 0111 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i := m ?1 d2: j := n d3: a := u1 B1 B2 d7: i := u3 B4 d4: i := i + 1 d5: j := j ? 1 d6: a := u2 B3 定值的迭代算法 in [B] out [B] B1 000 0000 111 0000 B2 111 0111 001 1110 B3 001 1100 000 1110 B4 001 1110 001 0111 gen [B1] = {d1, d2, d3} kill [B1]={d4, d5, d6, d7} gen [B2] = {d4, d5} kill [B2] = {d1, d2, d7} gen [B3] = {d6} kill [B3] = {d3} gen [B4] = {d7} kill [B4] = {d1, d4} d1: i := m ?1 d2: j := n d3