【導讀】編譯時刻為改進目標程序的質(zhì)量而進行的各項工。空間效率和時間效率有時是一對矛盾，有時不能。為優(yōu)化的努力必須是值得的。令優(yōu)化，無用指令消除等。歸納變量刪除，計算強度削減。控制流分析的主要目的是分析出程序的循環(huán)結(jié)構(gòu)。獲得和使用情況的數(shù)據(jù)流信息?；緣K中，控制流是由第一個四元式進入，到達最后一個四元式離開。以所有的基本塊為節(jié)點集合。有B1到B2的邊當且僅當：。B1的最后一個四元式有條件或無條件地轉(zhuǎn)移。B2是緊緊跟隨在B1后面的四元式，且B1的最。公共子表達式刪除

　　

【正文】 y的效果是 x和 y的值相等。如果某個引用 y的四元式運行的時候， x和 y的值一定相等。那么我們可以使用對 y的引用來替代對 x的引用。這樣做有時可以消除復制四元式 = x y。 消除復制四元式的條件 ? 對于復制四元式 d: = x y，如果對 y對應于 d點的一切引用點 u滿足下列條件，那么我們可以刪除 d，并且在這些引用點上用對 x的引用代替對 y的引用。 ? 此定義點是 d到達 u的唯一的 y的定義。 ? 從 d到達 u的路徑（可以包含圈和多個 u，但是不包含多個 d）上，沒有對 x的定義。 ? 這兩個條件實際上是說，當程序運行到達 u點的時候， x和 y的值總是相等。 記號 ? C_GEN[B]：在基本塊 B中的所有復制四元式 = x y，并且從該四元式開始到 B的出口， x和 y都沒有再定義。 ? C_KILL[B]：包含了所有在流圖中出現(xiàn)并且滿足下列條件的復制四元式 = x y： B中存在對 x或者 y的定義，并且之后在沒有復制四元式 = x y出現(xiàn)。 ? C_IN[B]：表示在 B的入口點，有效的復制四元式 = x y的集合，也就是到達入口的路徑上都要經(jīng)過 = x y并且之后沒有對 x或者 y定義。 ? C_OUT[B]：表示在 B的出口點有效的復制四元式的集合。 數(shù)據(jù)流方程 ? C_OUT[B] = C_GEN[B] ∪(C_IN[B] C_KILL[B]) ? C_IN[B] = ∩E_OUT[p] ；其中 B不等于 B1， p是 B的前驅(qū)。 ? C_IN[B1] = 空集。 ? 其中 C_GEN[B]和 C_IN[B]可以直接從流圖得到，所以在方程中作為已知量處理。 ? 求解方法和可用表達式的求解相同。 復制傳播算法 ? 對于每個復制四元式 d: = x y執(zhí)行下列步驟。 ? 找出該 y定義所能夠到達的那些對 y的引用。 ? 確定是否對于每個這樣的 y， d都在 C_IN[B]中， B是包含這個引用的基本塊，而且 B中該引用的前面沒有 x或者 y的定義。 ? 如果 d滿足條件 (2)，刪除 d，且把步驟 1中找到的的對 y的引用用 x代替。 復制傳播算法的例子 = x y * y 2 t = x y * y 3 t2 + x 1 y 循環(huán)優(yōu)化的例子 (原始流圖） B2 m 1 t1 = t1 i = n j * 4 n t2 =[] A t2 t3 = t3 v + i 1 t4 = t4 i * 4 i t5 =[] A t5 t6 t9 v B3 j 1 t7 = t7 j * 4 j t8 =[] A t8 t9 t9 v B3 = i j B6 * 4 i t10 =[] A t10 t11 = t11 x * 4 i t12 []= A t12 t13 … … … … i j B2 * 4 i t18 =[] A t18 t19 = t19 x * 4 i t20 []= A t20 t21 * 4 n t22 =[] A t22 t23 amp。= t23 t21 t21 * 4 n t24 []= A t24 t25 amp。= x t25 t25 B1 B3 B4 B5 B6 B7 尋找回邊以及自然循環(huán) ? 回邊有： B2?B2, B3?B3, B6?B2。 ? B2?B2對應的循環(huán)是 {B2} ? B3?B3對應的循環(huán)是 {B3} ? B6?B2對應的循環(huán)是 {B2,B3,B4,B5,B6} ? 刪除回邊之后，得到的圖是無回路的，所以這個流圖是可歸納流圖。 尋找公共子表達式 ? 4*i：在 B5， B7入口處可用 (U1)。 ? A[4*i]：在 B5， B7的入口處可用 (U2)。 ? 4*j：在 B5的入口處可用 (U3)。 ? A[4*j]：在 B5的入口處可用 (U4)。 ? 4*n：在 B7的入口處可用 (U5)。 ? A[4*n]：在 B7的入口處可用 (U6)。 公共子表達式的優(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。= t23 t21 t21 = u5 t24 []= A t24 t25 amp。= x t25 t25 B1 B3 B4 B5 B6 B7 尋找歸納變量 ? 基本歸納變量有 i， j。 ? 歸納變量有： ? u1： i族， (i, 4, 0) ? u2： j族， (j, 4, 0) ? 如果分析得更加深入，會發(fā)現(xiàn) []= 四元式得到的地址也是歸納變量。但是，由于我們不考慮對間接賦值的優(yōu)化，同時地址的處理也不在范圍之內(nèi)，所以我們沒有列出。 歸納變量的優(yōu)化 m 1 t1 = t1 i = n j * 4 n u5 = u5 t2 =[] A t2 u6 = u6 t3 = t3 v * 4 i u1 * 4 j u3 + i 1 t4 = t4 i + u1 4 u1 =[] A u1 u2 = u2 t6 t9 v B3 j 1 t7 = t7 j u3 4 u3 =[] A u3 u4 = u4 t9 t9 v B3 = u1 u3 B6 = u2 t11 = t11 x = u1 t12 []= A t12 t13 … … … … u1 u3 B2 = u2 t19 = t19 x = u1 t20 []= A t20 t21 = u5 t22 = u6 t23 amp。= t23 t21 t21 = u5 t24 []= A t24 t25 amp。= x t25 t25 B1 B3 B4 B5 B6 B7 優(yōu)化結(jié)果 m 1 t1 = t1 i = n j * 4 n u5 = u5 t2 =[] A t2 u6 = u6 t3 = t3 v * 4 i u1 * 4 j u3 + u1 4 u1 =[] A u1 u2 = u2 t6 t9 v B3 u3 4 u3 =[] A u3 u4 = u4 t9 t9 v B3 = u1 u3 B6 = u2 t11 = t11 x = u1 t12 []= A t12 t13 … … … … u1 u3 B2 = u2 t19 = t19 x = u1 t20 []= A t20 t21 = u5 t22 = u6 t23 amp。= t23 t21 t21 = u5 t24 []= A t24 t25 amp。= x t25 t25 B1 B3 B4 B5 B6 B7 窺孔優(yōu)化 ? 是指對代碼局部進行改進的簡單有效的技術(shù)。只考慮目標代碼中的指令序列，把可能的指令序列替換成為更短更快的指令。 ? 冗余指令刪除。 ? 控制流優(yōu)化 ? 代數(shù)化簡 ? 特殊指令使用 冗余指令刪除 ? 多余存取指令的刪除： ? MOV b R0 ? ADD c R0 ? MOV R0 a ? MOV a R0 ? SUB d R0 ? MOV R0 c ? 第四條指令沒有任何效果，可以刪除。 ? 如果有標號轉(zhuǎn)向第四條指令，則不可以刪除。 冗余指令刪除 ? 無用代碼刪除： ? 將不會被執(zhí)行的代碼刪除。 ? 如果目標代碼中有無條件轉(zhuǎn)移指令，且其后的指令標號，那么后面的指令可以刪除。 ? 產(chǎn)生無用代碼的原因可以是調(diào)試信息，或者優(yōu)化的結(jié)果。 ? 對于條件轉(zhuǎn)移指令，如果其條件永遠成立或者永遠不成立，可以轉(zhuǎn)換成為等價的無條件轉(zhuǎn)移指令。 控制流優(yōu)化 ? 在代碼中出現(xiàn)轉(zhuǎn)移指令到轉(zhuǎn)移指令的情況時，某些條件下可以使用一個轉(zhuǎn)移指令來代替。 ? 轉(zhuǎn)移到轉(zhuǎn)移 ? GOTO L1。 ? … … ? L1: GOTO L2。 ? 顯然第一個轉(zhuǎn)移指令可以替代為 GOTO L2. ? 如果在沒有其他的指令轉(zhuǎn)移到 L1，那么第二個指令可以被刪除。 控制流優(yōu)化（續(xù)） ? 轉(zhuǎn)移到條件轉(zhuǎn)移： ? L0: GOTO L1 …