【文章內(nèi)容簡(jiǎn)介】 } 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 0000 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 數(shù)據(jù)流分析介紹 IN [B] OUT [B] B1 000 0000 111 0000 B2 111 0000 001 1100 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 數(shù)據(jù)流分析介紹 IN [B] OUT [B] B1 000 0000 111 0000 B2 111 0000 001 1100 B3 001 1100 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 數(shù)據(jù)流分析介紹 IN [B] OUT [B] B1 000 0000 111 0000 B2 111 0000 001 1100 B3 001 1100 000 1110 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 數(shù)據(jù)流分析介紹 IN [B] OUT [B] B1 000 0000 111 0000 B2 111 0000 001 1100 B3 001 1100 000 1110 B4 001 1110 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 數(shù)據(jù)流分析介紹 IN [B] OUT [B] B1 000 0000 111 0000 B2 111 0000 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 數(shù)據(jù)流分析介紹 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 數(shù)據(jù)流分析介紹 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: 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 0111 001 1110 B3 001 1110 000 1110 B4 001 1110 001 0111 不再繼續(xù)演示迭代計(jì)算 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ù)流分析介紹 ? 到達(dá) 定值數(shù)據(jù)流等式是 正向 的方程 OUT [B] = gen [B] ? (IN [B] ? kill [B]) IN [B] = ?P是 B的前驅(qū) OUT [P] 某些數(shù)據(jù)流等式是 反向 的 ? 到達(dá) 定值數(shù)據(jù)流等式的合流運(yùn)算是求并集 IN [B] = ?P是 B的前驅(qū) OUT [P] 某些數(shù)據(jù)流等式的合流運(yùn)算是求交集 ? 對(duì)到達(dá) 定值數(shù)據(jù)流方程，迭代求它的最小解 某些數(shù)據(jù)流方程可能需要求最大解 數(shù)據(jù)流分析介紹 數(shù)據(jù)流分析模式 ? 數(shù)據(jù)流值 – 數(shù)據(jù)流分析總把程序點(diǎn)和數(shù)據(jù)流值聯(lián)系起來(lái) – 數(shù)據(jù)流值代表在程序點(diǎn)能觀測(cè)到的所有可能程序狀態(tài)集合的一個(gè)抽象 – 語(yǔ)句 s前后兩點(diǎn)數(shù)據(jù)流值用 IN[s]和 OUT[s]來(lái)表示 – 數(shù)據(jù)流問(wèn)題就是通過(guò) 基于語(yǔ)句語(yǔ)義的約束 （遷移函數(shù)）和 基于控制流的約束 來(lái)尋找所有語(yǔ)句 s的IN[s]和 OUT[s] 的一個(gè)解 數(shù)據(jù)流分析介紹 數(shù)據(jù)流分析模式 ? 遷移函數(shù) f – 語(yǔ)句前后兩點(diǎn)的數(shù)據(jù)流值受該語(yǔ)句的語(yǔ)義約束 – 若 沿執(zhí)行路徑正向傳播，則 OUT[s] = fs(IN[s]) – 若沿執(zhí)行路徑逆向傳播，則 IN[s] = fs(OUT[s]) 若基本塊 B由語(yǔ)句 s1, s2, …, sn依次組成，則 – IN[si+1] = OUT[si], i = 1, 2, …, n?1（逆向 … ） – fB = fn ? . . . ? f2 ? f1 (逆向 fB = f1 ? . . . ? fn 1 ? fn ) – OUT[B] = fB (IN[B]) (逆向 IN[B] = fB (OUT[B]) ) 數(shù)據(jù)流分析介紹 數(shù)據(jù)流分析模式 ? 控制流約束 – 正向傳播 IN[B] = ? P是 B的前驅(qū) OUT[P]（可能用 ?） – 逆向傳播 OUT[B] = ? S是 B的后繼 IN[S] （可能用 ?） ? 約束方程組的解通常不是唯一的 – 求解的目標(biāo)是要找到滿足這兩組約束（控制流約束和遷移約束）的最 “ 精確 ” 解 數(shù)據(jù)流分析介紹 活躍變量 ? 定義 – x的值在 p點(diǎn)開始的某條執(zhí)行路徑上被引用，則說(shuō)x在 p點(diǎn)活躍，否則稱 x在 p點(diǎn)已經(jīng)死亡 – IN[B]： 塊 B開始點(diǎn)的活躍變量集合 – OUT[B]： 塊 B結(jié)束點(diǎn)的活躍變量集合 – useB： 塊 B中有引用且在引用前無(wú)定值的變量集 – defB： 塊 B中有定值的變量集 ? 應(yīng)用 – 一種重要應(yīng)用就是基本塊的寄存器分配 數(shù)據(jù)流分析介紹 活躍變量 ? 例 – use[B2] = { i, j } – def[B2] = { i, j } 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ù)流分析介紹 活躍變量 ? 活躍變量數(shù)據(jù)流等式 – IN [B] = useB ? (OUT [B] ? defB ) – OUT[B] = ? S是 B