編譯原理第5版-課件 第7章代碼優(yōu)化

本章主要介紹：優(yōu)化基本概念基本塊內(nèi)的局部優(yōu)化第7章代碼優(yōu)化2025/2/191什么是代碼優(yōu)化？對程序?qū)嵤└鞣N等價變換,使得變換后程序能生成高效率的目標(biāo)代碼。高效率的目標(biāo)代碼是指：目標(biāo)代碼占用的存儲空間少目標(biāo)代碼運行時間短代碼優(yōu)化的原則1.等價原則：保證等價性。2.有效原則：有明顯的效果。3.合算原則：較低的代價取得較好的優(yōu)化效果。7.1優(yōu)化概述2025/2/192代碼優(yōu)化的種類：根據(jù)是否涉及具體的計算機(jī)分為:與機(jī)器有關(guān)的優(yōu)化(優(yōu)化工作主要在目標(biāo)代碼級上進(jìn)行)

對寄存器的優(yōu)化

多處理機(jī)的優(yōu)化

特殊指令的優(yōu)化等與機(jī)器無關(guān)的優(yōu)化(優(yōu)化工作主要在中間代碼級上進(jìn)行)7.1優(yōu)化概述2025/2/193根據(jù)優(yōu)化對象所涉及的程序范圍分為:局部優(yōu)化循環(huán)優(yōu)化全局優(yōu)化局部優(yōu)化：局限于程序基本塊范圍內(nèi)的一種優(yōu)化。

合并已知量

刪除公共子表達(dá)式(刪除多余的運算)

刪除無用賦值循環(huán)優(yōu)化:是指對循環(huán)中的代碼進(jìn)行優(yōu)化。

代碼外提

刪除歸納變量

強(qiáng)度削弱全局優(yōu)化:是在整個程序范圍內(nèi)進(jìn)行的優(yōu)化,需進(jìn)行數(shù)據(jù)流分析,花費代價很高。7.1優(yōu)化概述2025/2/194S=0；for(i=1;i<=20;i++)S=S+A[i]*B[i]；優(yōu)化處理例如設(shè)有一個計算兩個向量內(nèi)積的源程序段:7.1優(yōu)化概述2025/2/195說明:<A[I]>=<A[1]>+I－1=addr(A)－1+Iaddr(A)－1

T2地址計算的不變部分I

T1地址計算的可變部分用T2[T1]表示數(shù)組元素的地址若一個機(jī)器字有四個字節(jié),按字節(jié)編址:T1=4*IT2=addr(A)－4*1(1)S=0(2)I=1(3)T1=4*I(4)T2=addr(A)－4(5)T3=T2[T1](6)T4=4*I(7)T5=addr(B)－4(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B27.1優(yōu)化概述2025/2/196刪除公共子表達(dá)式

(刪除多余運算)公共子表達(dá)式是指在一個基本塊內(nèi)計算結(jié)果相同的子表達(dá)式。(1)S=0(2)I=1(3)T1=4*I(4)T2=addr(A)－4(5)T3=T2[T1](6)T4=4*I(7)T5=addr(B)－4(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B27.1優(yōu)化概述2025/2/197(1)S=0(2)I=1(3)T1=4*I(4)T2=addr(A)－4(5)T3=T2[T1](6)T4=4*I(7)T5=addr(B)－4(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B2(1)S=0(2)I=1(3)T1=4*I(4)T2=addr(A)－4(5)T3=T2[T1](6)T4=T1(7)T5=addr(B)－4(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B27.1優(yōu)化概述2025/2/1982.代碼外提是指將循環(huán)中的不變運算提到循環(huán)體之外。(1)S=0(2)I=1(3)T1=4*I(4)T2=addr(A)－4(5)T3=T2[T1](6)T4=T1(7)T5=addr(B)－4(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B27.1優(yōu)化概述2025/2/199(1)S=0(2)I=1(3)T1=4*I(4)T2=addr(A)－4(5)T3=T2[T1](6)T4=T1(7)T5=addr(B)－4(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B2(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B27.1優(yōu)化概述2025/2/1910(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B23.強(qiáng)度削弱是指在不改變運算結(jié)果的前提下，將程序中執(zhí)行時間長的運算替換成執(zhí)行時間短的運算。

對計算機(jī)上的二進(jìn)制算術(shù)運算，作加法一般比作乘法的速度快。7.1優(yōu)化概述2025/2/1911(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7I=I+1(3')T1=T1+4(12)ifI≤20goto(5)B1B2(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B27.1優(yōu)化概述2025/2/19124.變換循環(huán)控制條件

(刪除歸納變量)在B2中存在變量T與循環(huán)控制變量I保持線性關(guān)系，則可由T取代I,因此對三地址語句(12)中的循環(huán)控制條件I≤20T1≤80(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7I=I+1(3')T1=T1+4(12)ifI≤20goto(5)B1B27.1優(yōu)化概述2025/2/1913(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7I=I+1(3')T1=T1+4(12)ifI≤20goto(5)B1B2(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7

I=I+1×(3')T1=T1+4(12)ifT1≤80goto(5)B1B27.1優(yōu)化概述2025/2/19145.合并已知量已知量是指，常數(shù)或在編譯時就能確定其值的變量。合并已知量是指，若參加運算的兩個對象在編譯時都是已知量，則可以在編譯時直接計算出它們的運算結(jié)果，不必生成目標(biāo)。(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7I=I+1×(3')T1=T1+4(12)ifT1≤80goto(5)B1B27.1優(yōu)化概述2025/2/1915(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)

T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7I=I+1×(3')T1=T1+4(12)ifT1≤80goto(5)B1B2(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4(5)T3=T2[T1](6)T4=T1(8)

T6=T5[T4](9)T7=T3*T6(10)S=S+T7I=I+1(3')T1=T1+4(12)ifT1≤80goto(5)B1B27.1優(yōu)化概述2025/2/19166.復(fù)寫傳播是指盡量不引用那些在程序中僅僅只傳遞信息而不改變其值，也不影響其運行結(jié)果的變量。(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7I=I+1(3')T1=T1+4(12)ifT1≤80goto(5)B1B27.1優(yōu)化概述2025/2/1917(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4(5)T3=T2[T1](6)T4=T1×(8)T6=T5[T1](9)T7=T3*T6(10)S=S+T7I=I+1(3’)T1=T1+4(12)ifT1≤80goto(5)B1B2(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7I=I+1(3')T1=T1+4(12)ifT1≤80goto(5)B1B27.1優(yōu)化概述2025/2/19187.刪除無用賦值對賦值語句X=Y，若在程序的任何地方都不引用X，這時該語句執(zhí)行與否對程序運行結(jié)果沒有任何作用，這種語句稱為無用賦值語句，可以刪除。(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4(5)T3=T2[T1](6)T4=T1(8)T6=T5[T1](9)T7=T3*T6(10)S=S+T7I=I+1(3')T1=T1+4(12)ifT1≤80goto(5)B1B27.1優(yōu)化概述2025/2/19197.1優(yōu)化概述2025/2/1920(1)S=0I=1×(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4(5)T3=T2[T1](6)T4=T1×(8)T6=T5[T1](9)T7=T3*T6(10)S=S+T7I=I+1×(3')T1=T1+4(12)ifT1≤80goto(5)B1B2(5)T3=T2[T1](8)T6=T5[T1](9)T7=T3*T6(10)S=S+T7(3')T1=T1+4(12)ifT1≤80goto(5)(1)S=0(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4B1B2(5)T3=T2[T1](8)T6=T5[T1](9)T7=T3*T6(10)S=S+T7(3')T1=T1+4(12)ifT1≤80goto(5)(1)S=0(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4B1B2(1)S=0(2)I=1(3)T1=4*I(4)T2=addr(A)－4(5)T3=T2[T1](6)T4=4*I(7)T5=addr(B)－4(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B27.1優(yōu)化概述2025/2/1921局部優(yōu)化是指局限于程序基本塊范圍內(nèi)的一種優(yōu)化。入口語句四元式序列的第一個語句由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句緊跟在條件語句之后的語句出口語句下一個入口的前導(dǎo)語句轉(zhuǎn)移語句停語句7.2局部優(yōu)化2025/2/1922例劃分基本塊，構(gòu)造程序流圖。（1）readC （2）A=0 （3）B=1 （4）L1:A=A+B （5）ifB≥CgotoL2（6）B=B+1（7）gotoL1

（8）L2:writeA （9）halt（1）readC（2）A=0（3）B=1（4）L1:A=A+B（5）ifB≥CgotoL2（6）B=B+1（7）gotoL1（8）L2:writeA（9）halt7.2.1劃分基本塊的方法2025/2/1923利用DAG實現(xiàn)局部優(yōu)化的思想：首先對一個基本塊構(gòu)造一個DAG，然后按構(gòu)造結(jié)點的次序?qū)AG還原成四元式序列。DAG(無環(huán)路有向圖)n1n5n3n2n7n6n4n9n87.2.2基本塊的DAG表示2025/2/1924結(jié)點帶有標(biāo)記的DAG：n1Bn13.1416n1Addr(A)n3T1,T2n1Bn2COP7.2.2基本塊的DAG表示2025/2/1925基本塊的DAG表示：(1)A=Bn1AB(2)A=opBn2Bn1AOP(3)A=BopCn1Bn2Cn3Aop(4)A=B[C]n1Bn2Cn3A=[]四元式與DAG7.2.2基本塊的DAG表示2025/2/1926(5)ifBropCgoto(S)n1Bn2Cn3(S)rop(6)D[C]=Bn1n2n3DCB(7)Goto(S)n1(S)四元式與DAGn4[]=7.2.2基本塊的DAG表示2025/2/1927例構(gòu)造以下基本塊的DAG：(1)T0=3.14(2)T1=2*T0(3)T2=R+r(4)A=T1*T2(5)B=A(6)T3=2*T0(7)T4=R+r(8)T5=T3*T4(9)T6=R-r(10)B=T5*T6n1T03.14n1T03.14n2T16.28n3Rn4rn5T2+7.2.3利用DAG實現(xiàn)局部優(yōu)化2025/2/1928n1T03.14n2T16.28n3Rn4rn5T2+n6A*,B

，T3,T4,T57.2.3利用DAG實現(xiàn)局部優(yōu)化2025/2/1929例構(gòu)造以下基本塊的DAG：(1)T0=3.14(2)T1=2*T0(3)T2=R+r(4)A=T1*T2(5)B=A(6)T3=2*T0(7)T4=R+r(8)T5=T3*T4(9)T6=R-r(10)B=T5*T6n1T03.14n2T1,6.28n3Rn4rn5T2,+n6A,*B,T3T4T5n7T6-7.2.3利用DAG實現(xiàn)局部優(yōu)化2025/2/1930例構(gòu)造以下基本塊的DAG：(1)T0=3.14(2)T1=2*T0(3)T2=R+r(4)A=T1*T2(5)B=A(6)T3=2*T0(7)T4=R+r(8)T5=T3*T4(9)T6=R-r(10)B=T5*T6n1T03.14n2T1,6.28n3Rn4rn5T2,+n6A,*T3T4T5n7T6-n8B*7.2.3利用DAG實現(xiàn)局部優(yōu)化2025/2/1931例構(gòu)造以下基本塊的DAG：(1)T0=3.14(2)T1=2*T0(3)T2=R+r(4)A=T1*T2(5)B=A(6)T3=2*T0(7)T4=R+r(8)T5=T3*T4(9)T6=R-r(10)B=T5*T6(1)T0=3.14(2)T1=6.28(3)T3=6.28(4)T2=R+r(5)T4=T2(6)A=6.28*T2(7)T5=A(8)T6=R-r(9)B=A*T6n1T03.14n2T1,6.28n3Rn4rn5T2,+n6A,*T3T4T5n7T6-n8B*7.2.3利用DAG實現(xiàn)局部優(yōu)化2025/2/1932(1)T0=3.14(2)T1=6.28(3)T3=6.28(4)T2=R+r(5)T4=T2(6)A=6.28*T2(7)T5=A(8)T6=R-r(9)B=A*T6(1)T0=3.14(2)T1=2*T0(3)T2=R+r(4)A=T1*T2(5)B=A(6)T3=2*T0(7)T4=R+r(8)T5=T3*T4(9)T6=R-r(10)B=T5*T67.2.3利用DAG實現(xiàn)局部優(yōu)化2025/2/1933設(shè)優(yōu)化后的上述一組四元式序列為G'，G'較之優(yōu)化前的一組四元式G，不但代碼總數(shù)減少，而且對G中四元式(2)T1=2*T0和(6)T3=2*T0，在G'中已被優(yōu)化為T1=6.28，T3=6.28，這是合并已知量的結(jié)果；對G中四元式(5)B=A，直至在下一個B被賦值時都沒有被引用，7.2.3利用DAG實現(xiàn)局部優(yōu)化顯然是無用賦值，G'中已被刪除；對G中具有公共子表達(dá)式的四元式(3)T2=R+r，(7)T4=R+r，G'中被優(yōu)化為直接賦值T4=T2，避免了對公共子表達(dá)式R+r的重復(fù)計算。綜上所述，利用DAG可以很方便地進(jìn)行基本塊內(nèi)的優(yōu)化處理。7.2.3利用DAG實現(xiàn)局部優(yōu)化7.3循環(huán)優(yōu)化對循環(huán)語句,因為循環(huán)需要反復(fù)執(zhí)行，所以對循環(huán)實施優(yōu)化無疑會顯著提高目標(biāo)代碼的執(zhí)行效率。循環(huán)優(yōu)化包括：代碼外提強(qiáng)度削弱刪除歸納變量控制流程圖

一個程序的控制流程圖（簡稱為程序流圖或流圖）G是一個三元組

G=(N，n0，E)。其中：7.3.1程序流圖與循環(huán)N表示流圖的有限結(jié)點集，流圖中每一個結(jié)點對應(yīng)程序中的一個基本塊，因此，N實質(zhì)上就是一個程序的基本塊集。n0表示唯一的首結(jié)點，流圖的首結(jié)點是包含程序第一個語句的基本塊。E表示流圖的有向邊集。7.3.1程序流圖與循環(huán)為了找出流圖中的循環(huán)，需分析流圖中結(jié)點間的控制關(guān)系。因此引入必經(jīng)結(jié)點和必經(jīng)結(jié)點集的概念。7.3.2循環(huán)查找必經(jīng)結(jié)點在程序流圖中，對任意兩個結(jié)點a和b，若從流圖的首結(jié)點出發(fā)，到達(dá)a的任一通路都要經(jīng)過b，則稱b是a的必經(jīng)結(jié)點，記為bDOMa。7.3.2循環(huán)查找必經(jīng)結(jié)點集流圖中結(jié)點a的所有必經(jīng)結(jié)點的集合稱為結(jié)點a的必經(jīng)結(jié)點集，記為D(a)7.3.2循環(huán)查找求流圖中所有結(jié)點n的必經(jīng)結(jié)點集D(n)的算法思想：結(jié)點n∪n的所有前驅(qū)結(jié)點的必經(jīng)結(jié)點的交，即如果某結(jié)點d是結(jié)點n的所有前驅(qū)結(jié)點的必經(jīng)結(jié)點，則d為n的必經(jīng)結(jié)點。7.3.2循環(huán)查找流圖中各結(jié)點的必經(jīng)結(jié)點集：D(B1)={B1}D(B2)={B1,B2}D(B3)={B1,B2,B3}D(B4)={B1,B2,B3,B4}D(B5)={B1,B2,B3,B5}D(B6)={B1,B2,B3,B6}D(B7)={B1,B2,B7}D(B8)={B1,B2,B7,B8}B1B2B3B4B5B6B7B8例7.3.2循環(huán)查找求流圖中的回邊設(shè)a→b是流圖中的一條有向邊，若bDOMa，

則稱a→b是流圖中的一條回邊。7.3.2循環(huán)查找流圖中的回邊：因為B2DOMB7，所以B7→B2是流圖中的回邊，且是流圖中的唯一回邊。7.3.2循環(huán)查找B1B2B3B4B5B6B7B8求循環(huán)的算法思想：回邊n到d組成的循環(huán):d是循環(huán)的入口，n是循環(huán)的出口，循環(huán)出口n的前驅(qū)屬于循環(huán)，前驅(qū)不是d，再求前驅(qū),直到入口d為止。7.3.2循環(huán)查找流圖中的循環(huán)：由回邊B7→B2組成的循環(huán)是{B2,B3,B4,B5,B6,B7}7.3.2循環(huán)查找B1B2B3B4B5B6B7B8窺孔優(yōu)化方法是一種簡單有效地改進(jìn)代碼質(zhì)量的技術(shù)。主要包括：刪除冗余存取指令刪除不可達(dá)代碼控制流優(yōu)化