【正文】 ? … … ? L1: GOTO L2。 ? 產(chǎn)生無(wú)用代碼的原因可以是調(diào)試信息，或者優(yōu)化的結(jié)果。 ? 控制流優(yōu)化 ? 代數(shù)化簡(jiǎn) ? 特殊指令使用 冗余指令刪除 ? 多余存取指令的刪除： ? MOV b R0 ? ADD c R0 ? MOV R0 a ? MOV a R0 ? SUB d R0 ? MOV R0 c ? 第四條指令沒(méi)有任何效果，可以刪除。= t23 t21 t21 = u5 t24 []= A t24 t25 amp。但是，由于我們不考慮對(duì)間接賦值的優(yōu)化，同時(shí)地址的處理也不在范圍之內(nèi)，所以我們沒(méi)有列出。 公共子表達(dá)式的優(yōu)化 m 1 t1 = t1 i = n j * 4 n u5 = u5 t2 =[] A t2 u6 = u6 t3 = t3 v + i 1 t4 = t4 i * 4 i u1 = u1 t5 =[] A t5 u2 = u2 t6 t9 v B3 j 1 t7 = t7 j * 4 j u3 = u3 t8 =[] A t8 u4 = u4 t9 t9 v B3 = i j B6 = u1 t10 = u2 t11 = t11 x * 4 i t12 []= A t12 t13 … … … … i j B2 = u1 t18 = u2 t19 = t19 x = u1 t20 []= A t20 t21 = u5 t22 = u6 t23 amp。 ? 4*j：在 B5的入口處可用 (U3)。= x t25 t25 B1 B3 B4 B5 B6 B7 尋找回邊以及自然循環(huán) ? 回邊有： B2?B2, B3?B3, B6?B2。 ? 確定是否對(duì)于每個(gè)這樣的 y， d都在 C_IN[B]中， B是包含這個(gè)引用的基本塊，而且 B中該引用的前面沒(méi)有 x或者 y的定義。 ? 其中 C_GEN[B]和 C_IN[B]可以直接從流圖得到，所以在方程中作為已知量處理。 ? C_IN[B]：表示在 B的入口點(diǎn)，有效的復(fù)制四元式 = x y的集合，也就是到達(dá)入口的路徑上都要經(jīng)過(guò) = x y并且之后沒(méi)有對(duì) x或者 y定義。 ? 從 d到達(dá) u的路徑（可以包含圈和多個(gè) u，但是不包含多個(gè) d）上，沒(méi)有對(duì) x的定義。那么我們可以使用對(duì) y的引用來(lái)替代對(duì) x的引用。 ? 通過(guò)復(fù)制四元式傳播的變量大多數(shù)是臨時(shí)變量。 ? 把步驟 1中找到的四元式 op x y t用下列四元式代替： op x y u和 = u t。 ? 如果有四元式 op x y z，且在四元式前，表達(dá)式 x op y可用，那么我們可以用下面的方法優(yōu)化：在前面不同的地方計(jì)算 x op y時(shí)，把值記錄到同一個(gè)臨時(shí)變量 u里面。 ? 步驟 2：考慮對(duì) j的賦值 = t j。 ? relop i x B修改為 relop i c*x+d B。 歸納變量的刪除 ? 有些歸納變量的作用就是控制循環(huán)的次數(shù)。使得在循環(huán)開(kāi)始的時(shí)候 , t=c*i+t。 歸納變量的計(jì)算強(qiáng)度削弱算法 ? 對(duì)于每個(gè)基本歸納變量 i，對(duì)其族中的每個(gè)歸納變量 j(i, c, d)執(zhí)行下列步驟： ? 建立新的臨時(shí)變量 t。 k對(duì)應(yīng)的三元式可以確定。對(duì)應(yīng)于每個(gè)基本歸納變量的三元組如 (i,1,0)。 printf(“%i”, j)。 ? 對(duì)于 i族的歸納變量 (i,C1, C2)，要求循環(huán)內(nèi)部對(duì)此變量進(jìn)行定值的時(shí)候，一定是賦給C1*i+C2。 循環(huán)不變式外提的例子 = 1 i = 0 k 1) + i 1 k 2) * 2 k t u v B3 + u 1 u v 1 v = v 20 B5 = i j = 1 i = 0 k u v B3 + u 1 u v 1 v = v 20 B5 = i j 1)+ i 1 k 2)* 2 k t 關(guān)于歸納變量的優(yōu)化 ? 基本歸納變量：如果循環(huán)中，對(duì)于 i的定值只有形狀如 i = i + c的定值，那么 i稱為循環(huán)的基本歸納變量。（反例：情況 3） 外提算法 ? 步驟 1：尋找一切不變四元式。 首節(jié)點(diǎn) 首節(jié)點(diǎn) 前置節(jié)點(diǎn) 代碼外提不合法的情況（ 1） = 1 i u v B3 = 2 i + u 1 u v 1 v = v 20 B5 = i j = 1 i u v B3 + u 1 u v 1 v = v 20 B5 = i j = 2 i 代碼外提不合法的情況（ 2） = 1 i = 3 i u v B3 = 2 i + u 1 u v 1 v = v 20 B5 = i j = 1 i = 3 i u v B3 = 2 i + u 1 u v 1 v = v 20 B5 = i j 代碼外提不合法的情況（ 3） = 1 i = 0 k u v B3 = i k + u 1 u = 2 i v 1 v = v 20 B5 = i j = 1 i = 0 k = 2 i u v B3 = i k + u 1 u v 1 v = v 20 B5 = i j 不變四元式外提的條件 ? 不變四元式 op x y z可以外提的條件： ? Q坐在的基本塊節(jié)點(diǎn)是循環(huán)所有出口節(jié)點(diǎn)的必經(jīng)節(jié)點(diǎn)。 ? 說(shuō)明：一個(gè)四元式的是不變的，當(dāng)且僅當(dāng)其分量在循環(huán)中是不變的。 ? 在迭代的過(guò)程種， E_OUT[Bi]的值逐漸縮小直到穩(wěn)定。 i=n 。（ 2） ? 一個(gè)表達(dá)式在某個(gè)基本塊的出口點(diǎn)可用，或者該表達(dá)式是由它的產(chǎn)生的；或者該表達(dá)式在入口點(diǎn)可用，且沒(méi)有被注銷掉。 ? 掃描完所有的四元式之后， EK就是所求的E_KILL[B]。 E_GEN[B]的計(jì)算 ? 對(duì)于一個(gè)基本塊 B， E_GEN[B]的計(jì)算過(guò)程如下： ? 初始設(shè)置： E_GEN[B]=空； ? 順序掃描每個(gè)四元式： ? 對(duì)于四元式 op x y z，把 x op y加入E_GEN[B]， ? 從 E_GEN[B]中刪除和 z相關(guān)的表達(dá)式。 ? E_GEN[B]：基本塊 B所產(chǎn)生的可用表達(dá)式的集合。 ? 表達(dá)式的產(chǎn)生：如果某個(gè)基本塊 B對(duì) x op y進(jìn)行計(jì)算，而以后沒(méi)有重新定義 x或 y，則稱 B產(chǎn)生表達(dá)式 x op y。 ? 表達(dá)式可用的直觀意義：在點(diǎn) p上， x op y已經(jīng)在之前被計(jì)算過(guò)，不需要重新計(jì)算。 i++) { L_OUT[Bi]=U L_IN[s]。 ? 第二個(gè)方程表示： ? 在 B的某個(gè)后繼中會(huì)使用該后繼的入口處的值，那么他其實(shí)也可能使用 B的出口處的值。 活躍變量數(shù)據(jù)流方程 ? L_IN[B] = L_USE[B] U(L_OUT[B]L_DEF[B]) ? L_OUT[B] = U L_IN[s]，其中 s遍歷 B的所有后繼。 ? L_OUT[B]: 是在基本塊 B的出口點(diǎn)的活躍變量集。如果某個(gè)變量的值在以后不被引用，那么該復(fù)制四元式可以被消除。 ? IN[B4]={d3,d4,d5,d6}。 ? IN[B2]={d1,d2,d3,d5,d6,d7}。 IN[B3]={d4,d5}。 oldout = OUT[B]。 change = TRUE。 到達(dá)定義數(shù)據(jù)流方程 ? IN[B] = ∪ OUT[p] where p is in P[B] ? OUT[B] = GEN[B] U (IN[B]KILL[B]) ? 其中： ? GEN[B]可以從基本塊中求出：使用 DAG圖就可以得到。 ? P[B]： B的所有前驅(qū)基本塊的集合。 ? 顯然，通過(guò)變量 x在引用點(diǎn) u的 ud鏈，可以判斷 x是否循環(huán)不變的。 ? 引用點(diǎn) ：引用某個(gè)變量 x的四元式的位置稱為 x的引用點(diǎn)。 ? 沒(méi)有 goto語(yǔ)句的結(jié)構(gòu)化程序的流圖總是可歸約的。此時(shí)把兩個(gè)循環(huán)合并。此時(shí)算法不能得到自然循環(huán)。 for m的每個(gè)前驅(qū)節(jié)點(diǎn) p {if p is_not_in loop then {loop += p。 輸出 : 回邊對(duì)應(yīng)的自然循環(huán) . ? 算法 : 設(shè)置 loop={N,M}。 ? 用節(jié)點(diǎn)的集合表示自然循環(huán)。 回邊和自然循環(huán) ? 定義 假定流圖中存在兩個(gè)節(jié)點(diǎn) M和 N滿足 M dom N。 ? m為 n的前驅(qū)， n為 m的后繼。但是代碼的優(yōu)化是針對(duì)四元式序列的，所以識(shí)別循環(huán)必須針對(duì)流圖進(jìn)行。 ? 下標(biāo)變量中的下標(biāo)表達(dá)式是循環(huán)控制變量的線性表達(dá)式。 v2++) { … *D2… 。 v1v1f。 ? 每次外層循環(huán)體運(yùn)行結(jié)束之前，將 d1的值增加 C1’。 ? 將 i1,i2,i3的表達(dá)式代入 d的表達(dá)式，可以得到d=C0’+C1’*V1+C2’*V2. 下標(biāo)變量計(jì)算強(qiáng)度的削減（例子） ? 顯然，在上面的例子中，每次內(nèi)循環(huán) d的值增加 C2’；每次外循環(huán) , d的值增加 C1’（但是 V2被重置）。 v2v2f。 ? 當(dāng)滿足某些情況的時(shí)候，地址的計(jì)算可以使用加法來(lái)代替乘法。 計(jì)算強(qiáng)度削弱 ? 在刪除歸納變量的過(guò)程中 ,已經(jīng)將一些乘法運(yùn)算轉(zhuǎn)換成為加法運(yùn)算。 ? 如果在一個(gè)循環(huán)中有多個(gè)歸納變量，歸納變量的個(gè)數(shù)往往可以減少，甚至減少到 1個(gè)。 ? i作為計(jì)數(shù)器。 i = 1。 n360/(5*i)?？赡軐?duì)于更加外層的循環(huán)，它就不是循環(huán)不變式。 printf(“Area is %f”, S)?？梢孕薷某绦蛉缦拢? ? C= 10/360*pi*r*r*n。 n36。 ? 如果按照前面講的代碼生成方案，每一次循環(huán)都講計(jì)算一次。= 13: B2 x 從 DAG圖到四元式序列 ? * 4 i t10 (3) ? =[] A t10 t11 (5) ? := t11 x (5) ? []= A t10 t13 (6) ? * 4 j t14 (8) ? =[] A t14 t15 (9) ? amp。 ? 如果節(jié)點(diǎn)的標(biāo)識(shí)符重包含多個(gè)附加標(biāo)識(shí)符 z1,z2,… ,zk時(shí)： ? 若是葉子節(jié)點(diǎn)，標(biāo)記為 z，生成一系列四元式 ? = z z1 ? = z z2 ? … … … ? = z zn ? 不是葉子節(jié)點(diǎn)，生成四元式序列： ? = z z2 ? … … …