【正文】 ut[B2]=transB2({(q,c)})={(p, c), (q, a)} out[B3]=transB3({(q,c)})={(p, a), (q, c)} out[B4]=transB4({(p, a), (p, c), (q, a), (q, c)})= {(p, a), (q, a), (q, c)} out[B5]=transB5({(p, a), (q, a), (q, c)})= {(p, a), (p, c), (q, a), (q, c)} q := amp。a177。 c， c為非 0整數(shù)， p、 q為指針，則若s之前 q指向數(shù)組，緊跟 s之后 p也指向同一數(shù)組，否則 p無意義 3. s： p=q，緊跟 s之后， p指向 s之前 q所指向的變量 指針指向規(guī)則（續(xù)） 4. 若對 p進行其他形式的賦值， p不能指向任何對象 5. 對其他變量進行賦值，不會影響 p指向哪個變量（無多重指針） ? in[B]：在塊 B的入口點，指針 p指向的變量的集合 ——序?qū)?(p, a)的集合 ? out[B]：含義類似 in[B] trans函數(shù) ? transB：將 in[B]作為參數(shù)，計算出 out[B] ? 對單條語句計算，組合起來即可 ? transB計算規(guī)則： 1. a為數(shù)組，語句 s是 p=amp。a177。a，則緊跟 s之后， p只能指向a。 j 其中 b為常數(shù)， j為歸納變量 若 j為基本歸納變量，則 k屬于 i族，三元組根據(jù)賦值語句得出，如第一種情況為 (j, b, 0) 若 j不是基本歸納變量，假定它屬于 i族，則要求： a) 在循環(huán) L中對 j的唯一賦值和對 k的賦值之間沒有對 i的賦值 b) 循環(huán)外沒有 j的定義可到達 k 則由 j的三元組 (i, c, d)可得到 k的三元組，如第一種情況為 (i, b * c, b * d) 例 i族： t2: (i, 4, 0) j族： t4: (j, 4, 0) i := 1 j := n t1 := 4 * n v := a[t1] B1 i := i + 1 t2 := 4 * i t3 := a[t2] if t3 v goto B2 j := j 1 t4 := 4 * j t5 := a[t4] if t5 v goto B2 if i = j goto B6 B2 B3 B4 B6 B5 算法 強度削弱 輸入：計算了到達定義和歸納變量族的循環(huán) L 輸出：強度削弱后的循環(huán) 方法： 依次考慮每個基本歸納變量 i，對 i族中每個歸納變量 j（其三元組為 (i, c, d)），執(zhí)行以下步驟： 1. 建立新變量 s，但若 j1和 j2具有同樣三元組，只建立一個新變量 2. 用 j := s代替對 j的賦值 3. 在 L中緊跟在每個賦值語句 i := i + n之后（ n為常量），添加語句： s := s + c*n， c*n為常量 4. 在前置節(jié)點添加： s := c * i + d 例 i := 1 j := n t1 := 4 * n v := a[t1] B1 i := i + 1 t2 := 4 * i t3 := a[t2] if t3 v goto B2 j := j 1 t4 := 4 * j t5 := a[t4] if t5 v goto B2 if i = j goto B6 B2 B3 B4 B6 B5 i := 1 j := n t1 := 4 * n v := a[t1] B1 i := i + 1 s2 := s2 + 4 t2 := s2 t3 := a[t2] if t3 v goto B2 j := j – 1 s4 := s4 4 t4 := s4 t5 := a[t4] if t5 v goto B2 if i = j goto B6 B2 B3 B4 B6 B5 s2 := 4 * i s4 := 4 * j 算法 歸納變量刪除 輸入：計算了到達定義信息、循環(huán)不變計算信息和活躍變量信息的循環(huán) L 輸出：刪除歸納變量 方法： 1. 考慮只用來計算其他歸納變量的基本歸納變量 i 取 i族中盡可能簡單的 j，如三元組 (i, c, d)中 c=1, d=0 假定 c為正數(shù)，則可將形如 if i relop x goto B的語句替換為： r := c*x r := r + d if j relop r goto B 其中 r是新臨時變量， if x relop i goto B的處理類似 算法 （續(xù)） 對于 if i1 relop i2 goto B， i1和 i2都是歸納變量的情況。這里要用到循環(huán)不變計算的信息，與基本歸納變量 i相關(guān)聯(lián)的三元組是 (i, 1, 0) 算法 （續(xù)） 2. 尋找循環(huán)中只有一次賦值的變量 k，賦值形式如下： k := j * b, k := j / b, k := j177。 3. 若滿足條件 2，則刪除 s，將對 x的引用替換為 y 循環(huán)不變量的檢測 ?循環(huán)不變計算 ? 循環(huán)中含有賦值 x := y + z ? y、 z的可能定義都在循環(huán)外部（或常數(shù)） ?可由 ud鏈獲取此類賦值 ?循環(huán)中還有 v := x + w， w的定義也都在外部 ——x+w也是循環(huán)不變計算 ?重復(fù)掃描 ? ud鏈結(jié)合 du鏈，避免重復(fù)掃描 算法 循環(huán)不變計算檢測 輸入：一組基本塊組成的循環(huán) L，每個基本塊包括一系列的三地址語句，已計算出 ud鏈 輸出：從進入 L到離開，每次都計算同樣值的三地址語句集合 方法： 1. 尋找這樣語句：運算對象為常數(shù)，或到達定義都在 L之外，將這些語句標記為“不變” 2. 重復(fù)步驟 3，直至沒有新語句標記為“不變” 3. 尋找這樣的語句：尚未標記，且其運算對象或是常數(shù)、或是到達定義在 L外、或是唯一的到達定義是 L中已標記為“不變”的語句，將找到的語句標記為“不變” 代碼外提 ? 一些循環(huán)不變語句可實施代碼外提 ? s： x := y + z可外提的條件： 1. s所在塊支配所有循環(huán)出口節(jié)點 2. 循環(huán)中無其他語句對 x賦值， x為臨時變量肯定滿足 3. 循環(huán)中 x的引用僅由 s到達， x是臨時變量一般都滿足 例 錯誤的代碼外提， B3不支配 B4 若循環(huán)不經(jīng)過 B3，結(jié)果錯誤 i := 1 B1 if u v goto B3 B2 v := v 1 if v = 20 goto B5 B4 j := i B5 i := 2 u := u + 1 B3 i := 2 B6 if u v goto B3 B2 v := v 1 if v = 20 goto B5 B4 j := i B5 u := u + 1 B3 i := 1 B1 例 i := 3滿足條件 1，但如果外提， B2?B3 ?B4 ?B2 ?B4 ?B5會導(dǎo)致錯誤 多個賦值語句必須滿足條件 2 i := 1 B1 i := 3 if u v goto B3 B2 v := v 1 if v = 20 goto B5 B4 j := i B5 i := 2 u := u + 1 B3 i := 3 B6 if u v goto B3 B2 v := v 1 if v = 20 goto B5 B4 j := i B5 i := 2 u := u + 1 B3 i := 1 B1 例 i := 2不能外提，因為對 k := i， i的定義可從B2到達，也可從 B3到達 若不經(jīng)過 B3，出現(xiàn)錯誤 i := 1 B1 if u v goto B3 B2 k := i v := v 1 if v = 20 goto B5 B4 j := i B5 i := 2 u := u + 1 B3 算法 代碼外提 輸入：計算了 ud鏈和支配節(jié)點信息的循環(huán) L 輸出：將某些語句外提至新增前置節(jié)點 方法： 1. 利用算法 2. 對步驟 1中找到的每個語句 s（定義 x），檢查： i. s所在塊支配 L的所有出口 ii. x在 L的其他地方?jīng)]有被定義 iii. L中所有 x的引用只能由 s中 x的定義到達 3. 按語句找到的順序，將滿足 3個條件的語句 s遷移到新創(chuàng)建的前置節(jié)點，但應(yīng)滿足：對 s中運算對象，在L中定義它的語句已經(jīng)遷移 可選的代碼外提方案 ?放寬條件 1 ?1‘. s所在塊支配 L的所有出口，或 x在循環(huán)之外沒有被引用 ?平均性能更好，但有時會增加運行時間，有時還可能導(dǎo)致錯誤 ?放寬 2i、 2ii、 2iii ?在前置節(jié)點添加 t:=x+y，將循環(huán)內(nèi) x:=y+z替換為 x:=t 代碼外提后數(shù)據(jù)流信息的維護 ? 代碼外提后， ud鏈信息不會發(fā)生改變 ——語句 s外提，原來能由它到達的仍可到達 ? 實現(xiàn)問題： s位置改變， ud鏈如何仍指向它？ 1. 二重指針方式 ? 一個指針 ps始終指向 s， ud鏈中保存指向 ps的指針， s移動，修改 ps的值即可 2. 一重指針 ? 結(jié)合 du鏈尋找引用位置，提高效率 歸納變量刪除 算法 輸入：計算了到達定義信息和循環(huán)不變計算信息的循環(huán) L 輸出：一組歸納變量，每個歸納變量與一個三元組 (i, c, d)相關(guān)聯(lián)，其中 i是 基本歸納變量 （循環(huán)中對 i的賦值只有唯一的 i := i 177。在遇到的每個塊中，對 y+z的最后一次計算就是到達 s的 y+z的計算 2. 創(chuàng)建新變量 u 3. 對 1找到的每個語句 w := y+z，改為 u := y+z。][out:][Bk i l leBinBg e neBoutBouto l do u tPBinPB??????的前綴 活躍變量分析 ?變量 x和點 p， x在 p點是活躍的 ? 從 p開始的路徑可以引用 x在 p點的值 ?影響代碼生成 ——寄存器的分配 ??SBSinBoutBd e fBoutBu s eBin的后繼][][])[][(][][???緊靠 B之前點的活躍變量集 緊靠 B之后的點活躍變量集 使用之前明確賦值的變量集 定義之前引用的變量集 算法 活躍變量分析算法 輸入：已計算 def和 use的流圖 輸出： out[B]，每個塊 B出口活躍變量集 方法： for 每個塊 B do in[B] := Φ。[_][(][_:][]。 while change do begin change := false。[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 ?與到達定義概念相似，可類似計算 可用表達式 ? 用途：檢測公共表達式 ? 塊生成的表達式集合的計算 ? 假定塊前的點沒有可用表