1、第十三章 代碼優(yōu)化,針對 SPEC2000中l(wèi)ucas和mcf 施加不同級別的編譯優(yōu)化后的運行結(jié)果（編譯器Alpha Compiler）,全局寄存器分配,指令調(diào)度,代碼內(nèi)聯(lián),有保護的代碼內(nèi)聯(lián),局部子表達式刪除,消除數(shù)組邊界檢查,消除空指針檢查,下面的優(yōu)化合理嗎？,int foo(int a) int count = 0 ; for(int i = 1 ; i=100 ; i+) count += i ; return a + count ; ,int foo(int a) return a + 5050 ; ,優(yōu)化方法的分類1：,與機器無關的優(yōu)化技術 數(shù)據(jù)流分析 常量傳播 公共子表達式刪除 死

2、代碼刪除 循環(huán)交換 代碼內(nèi)聯(lián)等等,與機器相關的優(yōu)化技術 面向超標量超流水線架構、VLIW或者EPIC架構的指令調(diào)度方法 面向SMP架構的同步負載優(yōu)化方法 面向SIMD、MIMD或者SPMD架構的數(shù)據(jù)級并行優(yōu)化方法等,優(yōu)化方法的分類2：,局部優(yōu)化技術 基本塊內(nèi) 例如，局部公共子表達式刪除 全局優(yōu)化技術 函數(shù)/過程內(nèi) 跨越基本塊 例如，全局數(shù)據(jù)流分析 跨函數(shù)優(yōu)化技術 整個程序 例如，跨函數(shù)別名分析 ，逃逸分析 等,賦值語句：a=b*(-c) + b*(-c),=,a,+,*,b,-,c,*,b,-,c,語法樹,=,+,*,b,-,c,DAG圖,a,13.1.1 基本塊的DAG圖表示,13.1.2

3、消除局部公共子表達式,t1 := - c t2 := b * t1 t3 := - c t4 := b * t3 t5 := t2 + t4 a := t5,t1 := - c t2 := b * t1 t3 := - c t4 := b * t3 t5 := t2 + t2 (t4) a := t5,c := c + 1 ?,建立DAG圖，例1,t1 := - c t2 := b * t1 t3 := - c t4 := b * t3 t5 := t2 + t4 a := t5,a,t1,t2,t3,t4,t5,node(x),t1 := - c t2 := b * t1 c := t1 t

4、3 := - c t4 := b * t3 t5 := c + t4 a := t5,a,t1,t2,t3,t4,t5,node(x),c,建立DAG圖，例2,13.1.3 數(shù)組、指針及函數(shù)調(diào)用,當中間代碼序列中出現(xiàn)了數(shù)組成員、指針或函數(shù)調(diào)用時，算法13.1需要作出一定的調(diào)整，否則將得出不正確的優(yōu)化結(jié)果,(1)x = ai aj = y z = ai,(2)x = *p *q = y z = *p,13.1.4從DAG圖重新導出中間代碼,a,+,*,b,-,c,t1,t2,t3,t4,t5,t1 := -c,t2 := b * t1,a := t2 + t2,從DAG圖重新導出中間代碼,t1

5、= a + b t2 = c + d t3 = e t2 t4 = t1 t3,(2) t2 = c + d t3 = e t2 t1 = a + b t4 = t1 t3,t1 = a + b t2 = c + d t3 = e t2 t4 = t1 t3,(2)t2 = c + d t3 = e t2 t1 = a + b t4 = t1 t3,mov eax, a; t1 = a + b add eax, b mov edx, c; t2 = c + d add edx, d mov ESP+08H, eax; t3 = e t2 mov eax, e sub eax, edx mov

6、ESP+0CH, edx; t4 = t1 t3 mov edx, ESP+08H sub edx, eax,mov eax, c; t2 = c + d add eax, d mov edx, e; t3 = e t2 sub edx, eax mov ESP+0CH, eax; t1 = a + b mov eax, a add eax, b mov ESP+08H, eax; t4 = t1 t3 sub eax, edx,算法13.2 從DAG導出中間代碼的啟發(fā)式算法,輸入：DAG圖 輸出：中間代碼序列 方法： 初始化一個放置DAG圖中間節(jié)點的隊列。 如果DAG圖中還有中間節(jié)點未進入隊

7、列，則執(zhí)行步驟3，否則執(zhí)行步驟5 選取一個尚未進入隊列，但其所有父節(jié)點均已進入隊列的中間節(jié)點n，將其加入隊列；或選取沒有父節(jié)點的中間節(jié)點，將其加入隊列 如果n的最左子節(jié)點符合步驟3的條件，將其加入隊列；并沿著當前節(jié)點的最左邊，循環(huán)訪問其最左子節(jié)點，最左子節(jié)點的最左子節(jié)點等，將符合步驟3條件的中間節(jié)點依次加入隊列；如果出現(xiàn)不符合步驟3條件的最左子節(jié)點，執(zhí)行步驟2 將中間節(jié)點隊列逆序輸出，便得到中間節(jié)點的計算順序，將其整理成中間代碼序列,算法13.2 從DAG導出中間代碼的啟發(fā)式算法,中間節(jié)點隊列：,1、初始化一個放置DAG圖中間節(jié)點的隊列,2、如果DAG圖中還有中間節(jié)點未進入隊列， 則執(zhí)行步驟3

8、，否則執(zhí)行步驟5。,3、選取一個尚未進入隊列，但其所有父節(jié)點 均已進入隊列的中間節(jié)點n，將其加入隊列； 或選取沒有父節(jié)點的中間節(jié)點，將其加入隊列,t4,4、如果n的最左子節(jié)點符合步驟3的條件，將 其加入隊列；并沿著當前節(jié)點的最左邊，循環(huán) 訪問其最左子節(jié)點，最左子節(jié)點的最左子節(jié)點 等，將符合步驟3條件的中間節(jié)點依次加入隊列； 如果出現(xiàn)不符合步驟3條件的最左子節(jié)點， 執(zhí)行步驟2。,t1,5、將中間節(jié)點隊列逆序輸出，便得到中間節(jié) 點的計算順序，將其整理成中間代碼序列,t3,t2,13.1.5 窺孔優(yōu)化,窺孔優(yōu)化關注在目標指令的一個較短的序列上，通常稱其為“窺孔” 通過刪除其中的冗余代碼，或者用更高效

9、簡潔的新代碼來替代其中的部分代碼，達到提升目標代碼質(zhì)量的目的,mov EAX, ESP+08H mov ESP+08H, EAX,jmp B2 B2: ,13.2 全局優(yōu)化13.2.1 數(shù)據(jù)流分析,編譯器需要了解一些非常重要的信息，例如： 某個變量在某個特定的執(zhí)行點（語句前后）是否還“存活” 某個變量的值，是在什么地方定義的 某個變量在某一執(zhí)行點上被定義的值，可能在哪些其他執(zhí)行點被使用,數(shù)據(jù)流分析方程,outS = gens (inS killS) S代表某條語句（也可以是基本塊，或者語句集合，或者基本塊集合等） outS代表在該語句末尾得到的數(shù)據(jù)流信息 genS代表該語句本身產(chǎn)生的數(shù)據(jù)流信息

10、 inS代表進入該語句時的數(shù)據(jù)流信息 killS代表該語句注銷的數(shù)據(jù)流信息,數(shù)據(jù)流方程求解過程中的3個關鍵因素,當前語句產(chǎn)生和注銷的信息取決于需要解決的具體問題 ：可以由inS定義outS，也可以反向定義，由outS定義inS 由于數(shù)據(jù)是沿著程序的執(zhí)行路徑，也就是控制流路徑流動，因此數(shù)據(jù)流分析的結(jié)果受到程序控制結(jié)構的影響 代碼中出現(xiàn)的諸如過程調(diào)用、指針訪問以及數(shù)組成員訪問等操作，對定義和求解一個數(shù)據(jù)流方程都會帶來不同程度的困難,到達定義（reaching definition）分析,在程序的某個靜態(tài)點p，例如某條中間代碼之前或者之后，某個變量可能出現(xiàn)的值都是在哪里被定義的？ 在p處對該變量的引

11、用，取得的值是否在d處定義？ 如果從定義點d出發(fā)，存在一條路徑達到p，并且在該路徑上，不存在對該變量的其他定義語句 如果路徑上存在對該變量的其他賦值語句，那么路徑上的前一個定義點就被路徑上的后一個定義點“殺死”，或者消除了,genB1 = d1, d2, d3 killB1 = d5, d6, d7, d8,genB3 = d4, d5 killB3 = d1, d6,genB2 = killB2 = ,genB4 = d6 killB4 = d1, d5,genB5 = d7, d8 killB5 = d2, d3,入口,d1: x = a d2: y = b d3: i = 0,cmp i

12、, 100,d4: z = a * 10 d5: x = x + y cmp x, z,d6: x = x - y,d7: y = y + 1 d8: i = i + 1,出口,B1,B2,B3,B4,B5,Bexit,基本塊B的到達定義數(shù)據(jù)流方程,outB = genB ( inB killB ) inB為進入基本塊時的數(shù)據(jù)流信息 killB = killd1 killd2 killdn，d1dn依次為基本塊中的語句 genB = gendn (gend(n-1) killdn) (gend(n-2) killd(n-1) killdn)(gend1 - killd2 killd3- kil

13、ldn),例：,d1: a = b + 1 d2: a = b + 2,outB = genB ( inB killB ) inB為進入基本塊時的數(shù)據(jù)流信息 killB = killd1 killd2 killdn，d1dn依次為基本塊中的語句 genB = gendn (gend(n-1) killdn) (gend(n-2) killd(n-1) killdn)(gend1 - killd2 killd3- killdn),killB = killd1 killd2 = d2 d1 = d1, d2,genB = gend2 (gend1 killd2) = d2 (d1 d1) = d2

14、,outB = genB ( inB killB ) = d2 (inB - d1, d2),算法13.3 基本塊的到達定義數(shù)據(jù)流分析,輸入：程序流圖，且基本塊的kill集合和gen集合已經(jīng)計算完畢 輸出：每個基本塊入口和出口處的in和out集合，即inB和outB 方法： 將包括代表流圖出口基本塊Bexit的所有基本塊的out集合，初始化為空集。 根據(jù)方程inB = B的前驅(qū)基本塊PoutP，outB = genB ( inB killB )，為每個基本塊B依次計算集合inB和outB。如果某個基本塊計算得到的outB與該基本塊此前計算得出的outB不同，則循環(huán)執(zhí)行步驟2，直到所有基本塊的o

15、utB集合不再產(chǎn)生變化為止。,例：到達定義數(shù)據(jù)流分析,入口,d1: x = a d2: y = b d3: i = 0,cmp i, 100,d4: z = a * 10 d5: x = x + y cmp x, z,d6: x = x - y,d7: y = y + 1 d8: i = i + 1,出口,B1,B2,B3,B4,B5,Bexit,genB1 = d1, d2, d3 killB1 = d5, d6, d7, d8,genB3 = d4, d5 killB3 = d1, d6,genB2 = killB2 = ,genB4 = d6 killB4 = d1, d5,genB5

16、= d7, d8 killB5 = d2, d3,inB = B的前驅(qū)基本塊PoutP outB = genB ( inB killB ),inB1 = , outB1 = d1, d2, d3 B2的前驅(qū)為B1和B5 inB2 = d1, d2, d3, outB2 = d1, d2, d3 B3的前驅(qū)為B2 inB3 = d1, d2, d3, outB3 = d2, d3, d4, d5 B4的前驅(qū)為B3 inB4 = d2, d3, d4, d5, outB4 = d2, d3, d4, d6 B5的前驅(qū)為B3和B4 inB5 = d2, d3, d4, d5, d6, outB5 =

17、 d4, d5, d6, d7, d8 Bexit的前驅(qū)為B2，inBexit = d1, d2, d3,inB1 = , outB1 = d1, d2, d3 inB2 = d1, d2, d3, d4, d5, d6, d7, d8, outB2 = d1, d2, d3, d4, d5, d6, d7, d8 inB3 = d1, d2, d3, d4, d5, d6, d7, d8, outB3 = d2, d3, d4, d5, d7, d8 inB4 = d2, d3, d4, d5, d7, d8, outB4 = d2, d3, d4, d6, d7, d8 inB5 = d2

18、, d3, d4, d5, d6, d7, d8, outB5 = d4, d5, d6, d7, d8 inBexit = d1, d2, d3, d4, d5, d6, d7, d8,13.2.2 活躍變量分析,變量x在某個執(zhí)行點p是活躍的 在流圖中沿著從p開始的某條路經(jīng)中可能引用變量在p點的值 數(shù)據(jù)流方程如下： inB = useB (outB defB) outB = B的后繼基本塊P inP defB ：變量在B中被定義（賦值）先于任何對它們的使用 useB ：變量在B中被使用先于任何對它們的定義,與到達定義分析的區(qū)別,采用useB代表當前基本塊新生成的數(shù)據(jù)流信息 采用defB代表當

19、前基本塊消除的數(shù)據(jù)流信息 采用inB而不是outB來計算當前基本塊中的數(shù)據(jù)流信息 采用outB而不是inB來計算其它基本塊匯集到當前基本塊的數(shù)據(jù)流信息 在匯集數(shù)據(jù)流信息時，考慮的是后繼基本塊而不是前驅(qū)基本塊,到達定義分析： outB = genB ( inB killB ),活躍變量分析： inB = useB (outB defB),def和use,defB指的是在基本塊B中，在使用前被定義的變量集合 在引用改變量前已經(jīng)明確地對該變量進行了賦值 useB指的是在基本塊B中，在定義前被使用的變量集合 在該變量的任何定義之前對其引用,算法13.4 基本塊的活躍變量數(shù)據(jù)流分析,輸入：程序流圖，且基

20、本塊的use集合和def集合已經(jīng)計算完畢 輸出：每個基本塊入口和出口處的in和out集合，即inB和outB 方法： 將包括代表流圖出口基本塊Bexit在內(nèi)的所有基本塊的in集合，初始化為空集。 根據(jù)方程outB = B的后繼基本塊P inP，inB = useB (outB defB)，為每個基本塊B依次計算集合outB和inB。如果計算得到某個基本塊的inB與此前計算得出的該基本塊inB不同，則循環(huán)執(zhí)行步驟2，直到所有基本塊的inB集合不再產(chǎn)生變化為止。,for 每個基本塊B do inB = ; while 集合in發(fā)生變化 do for 每個基本塊B do begin outB = B

21、的所有后繼S inS inB = useB (outB defB) end,例,流圖,defB,useB,x, y, i,a, b,z,a, x, y,for 每個基本塊B do inB = ; while 集合in發(fā)生變化 do for 每個基本塊B do begin outB = B的所有后繼S inS inB = useB (outB defB) end,inB,outB,inB,outB,inB,outB,入口,d1: x = a d2: y = b d3: i = 0,cmp i, 100,d4: z = a * 10 d5: x = x + y cmp x, z,d6: x = x

22、 - y,d7: y = y + 1 d8: i = i + 1,出口,B1,B2,B3,B4,B5,Bexit,i,x, y,y, i,y, i,y, i,x, y, i,a,x,y,i,x, y, i,a,x,y,i,a,x,y,i,a,x,y,i,a, b,a,x,y,i,a, b,a,x,y,i,a,x,y,i,a,x,y,i,a,x,y,i,a,x,y,i,a,x,y,i,a,x,y,i,a,x,y,i,a,x,y,i,a, b,a,x,y,i,a,x,y,i,a,x,y,i,a,x,y,i,a,x,y,i,a,x,y,i,a,x,y,i,a,x,y,i,從活躍變量到?jīng)_突圖,流圖,入

23、口,d1: x = a d2: y = b d3: i = 0,cmp i, 100,d4: z = a * 10 d5: x = x + y cmp x, z,d6: x = x - y,d7: y = y + 1 d8: i = i + 1,出口,B1,B2,B3,B4,B5,Bexit,變量x, y, i：均定義于B1，在B2B5入口處均活躍。 注意，x在B3、B4中都被重新定義過，但x被定義前均被使用過，因此其在同一基本塊中發(fā)生在使用之前的定義僅余B1。變量y和i的情況類似。,變量a：在流圖中無定義點，在B1B5入口處均活躍。,變量b：在流圖中無定義點，在B1入口處活躍。,變量z：定義于B3，且僅在B3中被使用。,假設只有跨越基本塊活躍的變量才能分配到全局寄存器，并且活躍范圍重合的變量之間無法共享全局寄存器,13.2.3 定義-使用鏈、網(wǎng)和沖突圖,變量i在第一個循環(huán)中被定義和使用，執(zhí)行第二個循環(huán)前，i被重新定義和使用,變量a或變量b伴隨著變量i一同使用,變量i在第一個循環(huán)和第二個循環(huán)中，是否可以使用不同的全局寄存器？,活躍變量沖突的不同定義,活躍變量