【正文】 因此它不能到達 B B B6 d1: i := m – 1 d2: j := n d3: a := u1 d4: i := i + 1 d6: a := u2 B1 B2 B3 B4 B5 B6 d5: j := j 1 結(jié)構(gòu)化程序數(shù)據(jù)流分析 ?唯一的入口和出口 ?區(qū)域 ?包含首節(jié)點的一組節(jié)點，首節(jié)點支配其他所有節(jié)點 ?除了進入首節(jié)點的邊，其他邊都在區(qū)域內(nèi) 集中常見的語句結(jié)構(gòu) 數(shù)據(jù)流方程 ])[][(][][}{][}{][Sk i l lSinSg e nSoutdDSk i l ldSg e na??????d定義了 a——所有 a的定義（除了 b）全部被注銷 數(shù)據(jù)流方程（續(xù)） ][][][][][][])[][(][])[][(][][2121212212SoutSoutSoutSinSinSinSg e nSk i l lSk i l lk i l lSk i l lSg e nSg e nSg e n?????????S生成的定義： S1和 S2生成的定義，但 S1生成的應(yīng)去掉 S2中注銷的 數(shù)據(jù)流方程（續(xù)） ][][][][][][][][][][][][][21212121SoutSoutSoutSinSinSinSinSk i l lSk i l lSk i l lSg e nSg e nSg e n????????任何一個分支生成的定義，都會到達 S末尾 而在兩個分支都被注銷，才認(rèn)為是注銷 數(shù)據(jù)流方程（續(xù)） ][][][][][][][][][11111So u tSo u tSg e nSinSinSk i l lSk i l lSg e nSg e n?????循環(huán)可運行多次 ——S1生成的定義也應(yīng)認(rèn)為是其入口定義 數(shù)據(jù)流信息的保守估計 ? c)中 S2永遠(yuǎn)不被選中 ? gen[S] = gen[S1] ? kill[S] = kill[S1] ? 真實的 gen總是估算 gen的子集 ? 真實的 kill總是估算 kill的超集 ?是否影響數(shù)據(jù)流分析？ ? 過高估計定義集合并不嚴(yán)重 ? 安全的、保守的，不安全的 in和 out的計算 ? in—繼承屬性， out—依賴 in的綜合屬性 ? gen和 out的區(qū)別 ? 自底向上計算 gen和 kill，然后從表示完整程序的節(jié)點 S0開始計算 in和 out——in[S0]=Φ a) b) c) ])[][(][][ Sk i l lSinSg e nSout ?? ?][][],[][],[][ 2121 SoutSoutSoutSinSinSin ???][][][],[][],[][ 2121 SoutSoutSoutSinSinSinSin ???? 循環(huán)的處理 ?in[S1]不能簡單地用 in[S] ?in[S1]依賴 out[S1]，如何處理？ ? ?循環(huán)定義，仍未解決 ?解方程組 I = J∪ O O = G∪ (I – K) ][][][ 11 So u tSinSin ??])[][(][][ 1111 Sk i l lSinSg e nSout ?? ?循環(huán)的處理（續(xù)） ?從 O=Φ開始，進行迭代求解 ? I1 = J, O1 = G∪ (I1 – K) = G∪ (J – K) ? I2 = J∪ O1 = J∪ G∪ (JK) = J∪ G O2 = G∪ (I2 – K) = G∪ (J∪ G – K)= G∪ (J – K) ?因此 ?從 O=Φ開始為什么是安全的？ ][][][ 11 Sg e nSinSin ?? 集合的表示 ?位向量：集合運算 ?位運算 ?例 /* d1 */ i := m – 1。 /* d2 */ j := n。 /* d3 */ a := u1。 do /* d4 */ i := i + 1。 /* d5 */ j := j – 1。 if e1 then /* d6 */ a := u2。 else /* d7 */ i := u3。 while e2 例 （續(xù)） d7為 i賦值， d d4也是 ? gen={d7}, kill={d1, d4} ][][][][][][2121Sk i l lSk i l lSk i l lSge nSge nSge n????])[][(][])[][(][][212212Sge nSk i l lSk i l lk i l lSk i l lSge nSge nSge n??????實現(xiàn)策略 ? 局部到達定義 ?只保存基本塊開始點信息，需要時計算基本塊內(nèi)每個點的信息 ? 引用 定義鏈， ud鏈 ?列表：對每個變量引用，到達該引用的所有定義 ? 計算順序 ?方程給定的依賴關(guān)系，內(nèi)存分配 一般控制流 例 /* d1 */ i := m – 1。 /* d2 */ j := n。 /* d3 */ a := u1。 do /* d4 */ i := i + 1。 /* d5 */ j := j – 1。 if e1 then /* d6 */ a := u2。 else begin /* d7 */ i := u3。 break end while e2 gen？ {d6} d7后為 break，未到if語句結(jié)束點，在dowhile中才考慮 例 （續(xù)） ? do循環(huán)到達 break的結(jié)果 G、 K 到達 if之前 G=gen[S2]={d4,d5} K=kill[S2]={d1,d2,d7} 然后是語句序列， 用 S3表示左孩子 G:=gen[S3]∪ (Gkill[S3]) K:=kill[S3]∪ (Kgen[S3]) G={d5,d7} K={d1,d2,d4} 數(shù)據(jù)流方程迭代解 ? 任意流圖 ? in、 out的計算不依賴語法樹 ? 數(shù)據(jù)流方程的細(xì)節(jié)區(qū)別 1. 上一節(jié) ——前向方程， out計算依賴 in 存在后向方程， in的計算依賴 out 2. 多條邊進入塊 B，到達 B開始點的定義為每條路徑到達定義的并 ——聚合操作 聚合操作可為交集計算 ——全局可用表達式 到達定義的迭代計算 ?塊 B： out[B], gen[B], kill[B], in[B] ?匯聚操作為并 ?in[B]=Φ作為迭代起始 ])[][(][][][out][Bk i l lBinBg e nBoutPBinPB?????的前綴算法 到達定義的迭代計算 輸入：已計算出每個塊 B的 kill[B]、 gen[B]的流圖 輸出：每個塊 B的 in[B]和 out[B] 方法： 從“估計” in[B]=Φ開始，進行迭代計算，逐步收斂到 in和 out的期待值。用一個布爾變量change記錄每次迭代值 in是否發(fā)生變化（收斂）。 算法 （續(xù)） for 每個塊 B do out[B] := gen[B]。 change := true。 while change do begin change := false。 for 每個塊 B do begin if out[B] oldout then change := true。 end end ])。[][(][][]。[:]。[out:][Bk i l lBinBg e nBoutBouto l d o u tPBinPB??????的前綴例 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 d4: i := i + 1 d5: j := j 1 d6: a := u2 B1 B2 B3 B4 d7: i := u3 例 （續(xù)） 塊 B 初始 第 1遍 第 2遍 in[B] out [B] in[B] out [B] in[B] out [B] B1 000 0000 111 0000 000 0000 111 0000 000 0000 111 0000 B2 000 0000 000 1100 111 0011 001 1110 111 1111 001 1110 B3 000 0000 000 0010 001 1110 000 1110 001 1110 000 1110 B4 000 0000 000 0001 001 1110 001 0111 001 1110 001 0111 可用表達式 ?表達式 x+y在 p點可用（ available） ? 開始節(jié)點到 p的每條路徑都計算 x+y ? 最后一次計算后，再無對 x、 y的賦值 ?注銷（ kill） ? 塊對 x、 y賦值后沒有重新計算表達式 ?生成（ generate） ? 塊計算表達式后，沒有重新定義 x、 y ?與到達定義概念相似，可類似計算 可用表達式 ? 用途：檢測公共表達式 ? 塊生成的表達式集合的計算 ? 假定塊前的點沒有可用表達式 ? 點 p處表達式集合 A是可用的 ? q是 p之后的點，之間有語句 x := y + z ? 點 p處可用表達式的計算 1. 將表達式 y+z添加到 A中 2. 從 A中刪除任何含有 x的表達式 ? 注銷表達式集合的計算 ? y+z： y、 z在塊中定義， y+z不由該塊生成 例 語句 可用表達式 ...... 無 a := b + c ...... 僅 b+c b := a – d ...... 僅 ad c := b + c ...... 僅 ad d := a – d ...... 無 可用表達式的計算 ? in[B], out[B], e_gen[B], e_kill[B] ?聚合操作為交集 ? 所有前驅(qū)末尾都可用，表達式才在塊的開始可用 ?到達定義計算 ——―最小解”，空集開始逐漸增大 可用表達式計算 ——―最大解”，非常大的解開始逐漸減小 是開始塊不是開始塊的前驅(qū)11 ,][,][out][])[_][(][_][BBinBPBinBk i l leBinBg e neBoutPB???????例 e_gen[B2]: G e_kill[B2]: K out[B2]: Oj+1 = G∪ (Ij – K) in[B2]: Ij+1 = out[B1]∩ Oj+1 U: 表達式全集 I0 = U O1 = U – K I1 = out[B1] – K O2 = G∪ (out[B1] – K) B1 B2 I0 = Φ O1 = G I1 = out[B1]∩G O2 = G 算法 可用表達式計算 輸入：流圖 G，塊的 e_gen和 e_kill都已算出，開始塊 B1 輸出：每個塊的 in集合 方法： in[B1] := Φ out[B1] := e_gen[B1] for B B1 do out[B] := U – e_kill[B]。 change := true。 while change do begin change := false。 for B B1 do begin end end ])。[_][(][_:][]。[:。][out:][Bk i l leBinBg e neBoutBouto l do u tPBinPB??????的前綴 活躍變量分析 ?變量 x和點 p， x在 p點是活躍的 ? 從 p開始的路徑可以引用 x在 p點的值 ?影響代碼生成 ——寄存器的分配 ??SBSinBoutBd e fBoutBu s eBin的后繼][][])[][(][][???緊靠 B之前點的活躍變量集