編譯原理-第十章-代碼優(yōu)化

/第十章代碼優(yōu)化某些編譯程序在中間代碼或目標(biāo)代碼生成之后要對生成的代碼進(jìn)行優(yōu)化。所謂優(yōu)化，實(shí)質(zhì)上是對代碼進(jìn)行等價(jià)變換，使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同，而運(yùn)行速度加大或占用存儲空間少，或兩者都有。優(yōu)化可在編譯的不同階段進(jìn)行，對同一階段，涉及的程序范圍也不同，在同一范圍內(nèi)，可進(jìn)行多種優(yōu)化。一般，優(yōu)化工作階段可在中間代碼生成之后和（或）目標(biāo)代碼生成之后進(jìn)行。中間代碼的優(yōu)化是對中間代碼進(jìn)行等價(jià)變換。目標(biāo)代碼的優(yōu)化是在目標(biāo)代碼生成之后進(jìn)行的，因?yàn)樯傻哪繕?biāo)代碼對應(yīng)于具體的計(jì)算機(jī)，因此，這一類優(yōu)化在很大程度上依賴于具體的機(jī)器，我們不做詳細(xì)討論。另外依據(jù)優(yōu)化所涉及的程序范圍，又可分為局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化三個(gè)不同的級別。局部優(yōu)化指的是在只有一個(gè)入口、一個(gè)出口的基本程序塊上進(jìn)行的優(yōu)化。循環(huán)優(yōu)化對循環(huán)中的代碼進(jìn)行的優(yōu)化。全局優(yōu)化是在整個(gè)程序范圍內(nèi)進(jìn)行的優(yōu)化。本章重點(diǎn)：局部優(yōu)化基本塊的DAG表示第一節(jié)優(yōu)化技術(shù)簡介為了說明問題，我們來看下面這個(gè)例子，源程序是：P:=0ForI:=1to20doP:=P+A[I]*B[I];經(jīng)過編譯得到的中間代碼如圖10-1-1所示，這個(gè)程序段由B1和B2兩個(gè)部分組成，B2是一個(gè)循環(huán)，假定機(jī)器按字節(jié)編址。那么，對于這個(gè)中間代碼段，可進(jìn)行如下這些優(yōu)化。1、刪除多余運(yùn)算（刪除公共子表達(dá)式）優(yōu)化的目的在于使目標(biāo)代碼執(zhí)行速度較快。圖10-1-1中間代碼（3）和（6）中都有4＊I的運(yùn)算，而從（3）到（6）沒有對I賦值，顯然，兩次計(jì)算機(jī)的值是相等的。所以，（6）的運(yùn)算是多余的。我們可以把（6）變換成：T4:=T1。這種優(yōu)化稱為刪除多余運(yùn)算或稱為刪除公共子表達(dá)式。 B B1B2圖10-1-1中間代碼段(1)P:=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)P:=P+T7(11)I:=I+1(12)ifI≤20goto(3)2、代碼外提減少循環(huán)中代碼總數(shù)的一個(gè)重要辦法是代碼外提。這種變換把循環(huán)不變運(yùn)算，即其結(jié)果獨(dú)立于循環(huán)執(zhí)行次數(shù)的表達(dá)式，提到循環(huán)的前面。使之只在循環(huán)外計(jì)算一次，上例中，我們可以把（4）和（7）提到循環(huán)外。經(jīng)過刪除多余運(yùn)算和代碼外提后，代碼變成圖10-1-2。 B1B2圖10-1-3強(qiáng)度削弱(1)P:=0(2)I:=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)P:=P+T7(11)I:=I+1(3′)T1:=T1+4(12)ifI≤20goto(5) B1B2圖10-1-2刪除公共子表達(dá)式和代碼外提(1)P:=0(2)I:=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)P:=P+T7(11)I:=I+1(12)ifI≤20goto(3)3、強(qiáng)度削弱強(qiáng)度削弱的思想是把強(qiáng)度大的運(yùn)算換算成強(qiáng)度小的運(yùn)算。例如把乘法運(yùn)算換成加法運(yùn)算等等。在圖10-1-2的循環(huán)中，每循環(huán)一次，I的值增1，T1的值與I保持線性關(guān)系，每次總是增加4。因此，我們可以把循環(huán)中計(jì)算T1值的乘法運(yùn)算變換成在循環(huán)前進(jìn)行一次乘法運(yùn)算，而在循環(huán)中將其變換成加法運(yùn)算。變換后如圖10-1-3所示。4、變換循環(huán)控制條件圖10-1-3的代碼中，I和T1始終保持T1=4*I的線性關(guān)系，這樣可以把（12）的循環(huán)控制條件I≤20變換成T1≤80，這樣整個(gè)程序的運(yùn)行結(jié)果不變。這種變換稱為變換循環(huán)控制條件。經(jīng)過這一變換后，循環(huán)中I的值在循環(huán)后不會被引用，四元式（11）可以從循環(huán)中刪除，這就是我們的目的所在。5、合并已知量與復(fù)寫傳播圖10-1-3中，四元式（3）計(jì)算4*I時(shí)，I必為1。所以（3）中的4*I的兩個(gè)運(yùn)算對象都是編碼時(shí)的已知量，可在編譯時(shí)計(jì)算出它的值，即（3）可變?yōu)門1=4這種變換稱為合并已知量。圖10-1-3中，（6）把T1的值復(fù)寫到T4中，四元式（8）要引用T4的值，而（6）到（8）之間未改變T4和T1的值，則（8）改為T6:=T5[T1]，之后運(yùn)算結(jié)果保持不變。這種變換稱為復(fù)寫傳播。圖10-1-3經(jīng)過變換循環(huán)控制條件，合并已知量和復(fù)寫傳播等變換后，變?yōu)閳D10-1-4。 B1B2圖10-1-4(1)P:=0(2)I:=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)P:=P+T7(11)I:=I+1(3′)T1:=T1+4(12)ifI≤80goto(5) B1B2圖10-1-5刪除無用賦值(1)P:=0(4)T2:=addr(A)－4(7)T5:=addr(B)－4(3)T1:=4(5)T3:=T2[T1](8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(3′)T1:=T1+4(12)ifI≤80goto(5)6、刪除無用賦值在圖11.5中，（6）對T4賦值，但T4未被引用；另外，（2）和（11）對I賦6、刪除無用賦值在圖10-1-4中，（6）對T4賦值，但T4未被引用；另外，（2）和（11）對I賦值，但只有（11）引用I。所以，只要程序中其它地方不需要引用T4和I，則（6），（2）和（11）對程序的運(yùn)行結(jié)果無任何作用。我們稱之為無用賦值，無用賦值可以從程序中刪除，如圖10-1-5所示（設(shè)（6）（2）（11）為無用賦值）。比較圖10-1-1和圖10-1-5可看出，經(jīng)過優(yōu)化后的代碼的執(zhí)行效率提高了很多。當(dāng)然，實(shí)現(xiàn)這些優(yōu)化的代價(jià)也是很大的。第二節(jié)局部優(yōu)化我們所說的局部優(yōu)化是指基本塊內(nèi)的優(yōu)化，所謂基本塊，是指程序中一順序執(zhí)行語句序列，其中只有一個(gè)入口語句和一個(gè)出口語句。執(zhí)行時(shí)只能從其入口語句進(jìn)入，從其出口語句退出。對于一個(gè)給定的程序，我們可以把它劃分為一系列的基本塊。在各基本塊的范圍內(nèi)分別進(jìn)行優(yōu)化。一、基本塊的劃分在介紹基本塊的構(gòu)造之前，我們先定義基本塊的入口語句，所謂入口語句，嚴(yán)格地說來就是：1、程序的第一語句；或者，2、條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句的轉(zhuǎn)移目標(biāo)語句；或者，3、緊跟在條件轉(zhuǎn)移語句后面的語句。有了入口語句的概念之后，我們就可以給出劃分中間代碼（四元式程序）為基本塊的算法，其步驟如下：1、求出四元式程序中各個(gè)基本塊的入口語句。2、對每一入口語句，構(gòu)造其所屬的基本塊。它是由該入口語句到下一入口語句（不包括下一入口語句），或到一轉(zhuǎn)移語句（包括該轉(zhuǎn)移語句），或到一停語句（包括該停語句）之間的語句序列組成的。3、凡未被納入某一基本塊的語句、都是程序中控制流程無法到達(dá)的語句，因而也是不會被執(zhí)行到的語句，我們可以把它們刪除。我們?nèi)砸陨弦还?jié)所述的例子來說明，對于圖10-1-1中的代碼段，由規(guī)則1，語句（1）是入口語句，由規(guī)則2，語句（3）是入口語句。由規(guī)則3，跟隨語句（12）的語句是入口語句，這樣，語句（1）和（2）構(gòu)成一個(gè)基本塊，語句（3）—（12）構(gòu)成一個(gè)基本塊，也即圖10-1-1中的B1和B2。二、基本塊的變換很多變換可作用于基本塊而不改變它計(jì)算的表達(dá)式集合，這樣的變換對改進(jìn)代碼的質(zhì)量是很有用的。有兩類重要的局部等價(jià)變換可用于基本塊，它們是保結(jié)構(gòu)的變換和代數(shù)變換?；緣K的主要保結(jié)構(gòu)變換是1、刪除公共子表達(dá)式2、刪除無用代碼3、重新命名臨時(shí)變量4、交換語句次序?qū)τ?和2，我們在第一節(jié)已經(jīng)討論過，在此簡單討論一下3和4。重新命名臨時(shí)變量：假如有語句t:=b+c，其中t是臨時(shí)變量。如果把這個(gè)語句改為u:=b+c，其中u是新的臨時(shí)變量，并且把這個(gè)t的所有引用改成u，那么基本塊的運(yùn)算結(jié)果不變。交換語句次序：如果基本塊有兩個(gè)相鄰的語句：t1:=b+ct2:=x+y當(dāng)且僅當(dāng)x和y都不是t1，b和c都不是t2時(shí)我們可以交換這兩個(gè)語句的次序。有許多代數(shù)變換可以把基本塊計(jì)算的表達(dá)式集合變換成代數(shù)等價(jià)的集合。其中有用的變換是那些可以簡化表達(dá)式或用較快運(yùn)算代替較慢運(yùn)算的變換。例如：x:=x+0或x:=x*1這樣的語句可以從基本塊中刪除而不改變它計(jì)算的表達(dá)式集合，又如x:=y**2的指數(shù)算符通常要用函數(shù)調(diào)用來實(shí)現(xiàn)，使用代數(shù)變換，這個(gè)語句可由快速、等價(jià)的語句x:=y*y來代替。第三節(jié)基本塊的DAG表示n1n1n2n3n4n1n2n3n5n4n6n7n8n9圖10-3-1有向圖圖10-3-2DAG先將我們所需使用的DAG作一說明。在一個(gè)有向圖中，我們稱任一有向邊ni→nj（或表示為有序?qū)Γ╪i,nj））中的結(jié)點(diǎn)ni為結(jié)點(diǎn)nj的前驅(qū)（父結(jié)），結(jié)點(diǎn)nj為結(jié)點(diǎn)ni的后繼（子結(jié)）。又稱任一有向邊序列n1→n2,n2→n3,…,nk—1→nk為從結(jié)點(diǎn)n1到結(jié)點(diǎn)nk的一條通路。如果其中n1=nk，則稱通路為環(huán)路。該結(jié)點(diǎn)序列也記為（n1,n2,…,nk）。例如，圖10-3-1中有向圖的通路（n2,n2）和（n3,n4,n3）就是環(huán)路。如果有向圖中任一通路都不是環(huán)路，則稱該有向圖為無環(huán)路有向圖，簡稱DAG。圖10-3-2的有向圖就是一個(gè)DAG。在DAG中，如果（n1,n2,…,nk）是其中一條通路，則稱結(jié)點(diǎn)n1為結(jié)點(diǎn)nk的祖先，結(jié)點(diǎn)nk為結(jié)點(diǎn)n1的后代。我們這一節(jié)中要用到的有向圖，是一種其結(jié)點(diǎn)帶有下述標(biāo)記或附加信息的DAG：1、圖的葉結(jié)點(diǎn)，即無后繼的結(jié)點(diǎn)，以一標(biāo)識符（變量名）或常數(shù)作為標(biāo)記，表示該結(jié)點(diǎn)代表該變量或常數(shù)的值。如果葉結(jié)點(diǎn)用來代表某變量A的位置，則用addr（A）作為該結(jié)點(diǎn)的標(biāo)記。通常把葉結(jié)點(diǎn)上作為標(biāo)記的標(biāo)識符加上下標(biāo)0，以表示它是該變量的初值。2、圖的內(nèi)部結(jié)點(diǎn)，即有后繼的結(jié)點(diǎn)以一運(yùn)算符作為標(biāo)記，表示該結(jié)點(diǎn)代表應(yīng)用該運(yùn)算符對其后繼結(jié)點(diǎn)所代表的值進(jìn)行運(yùn)算的結(jié)果。3、圖中各個(gè)結(jié)點(diǎn)上可能附加一個(gè)或多個(gè)標(biāo)識符，表示這些變量具有該結(jié)點(diǎn)所代表的值。上述這種DAG可用來描述計(jì)算過程，又稱描述計(jì)算過程的DAG。在以下的討論中，我們簡稱DAG。下面討論基本塊的DAG表示與構(gòu)造。一個(gè)基本塊，可用一個(gè)DAG來表示。下面（圖10-3-3）列出各種四元式及相對應(yīng)的DAG的結(jié)點(diǎn)形式。圖中ni為結(jié)點(diǎn)編號，結(jié)點(diǎn)下面的符號（運(yùn)算符、標(biāo)識符或常數(shù)）是各結(jié)點(diǎn)的標(biāo)記，各結(jié)點(diǎn)右邊的標(biāo)識符是結(jié)點(diǎn)的附加標(biāo)識符。四元式 DAG結(jié)點(diǎn)opBAnopBAn1An2Bn1（1）A：=opB（op，B，—，A）CCn2opAn3Bn1（2）A：=BopC（op，B，C，A）=[]=[]Cn2An3Bn1（3）A：=B[C]（=[]，B[C]，—，A）

rop

ropCn2(S)n3Bn1（4）ifBropCgoto(s)(jrop,B,C,(S))DDB[]=Cn3(S)90()n4n2n1N1(S)90()（5）D[C]：=B（[]=，B，—，D[C]）（6）goto(s)(j，—，—，(S))圖10-3-3四元式與DAG結(jié)點(diǎn)接著給出一種構(gòu)造基本的DAG算法。假設(shè)DAG各結(jié)點(diǎn)信息將用某種適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)來存放。并設(shè)有一個(gè)標(biāo)識符（包括常數(shù)）與結(jié)點(diǎn)的對應(yīng)表。NODE（A）是描述這種對應(yīng)關(guān)系的一個(gè)函數(shù)，它的值或者是一個(gè)結(jié)點(diǎn)的編號n，或者無定義。前一個(gè)情況代表DAG中存在一個(gè)結(jié)點(diǎn)n,A是其上的標(biāo)記或附加標(biāo)識符。我們把圖10-3-3中各形式的四元式按其對應(yīng)結(jié)點(diǎn)的后繼個(gè)數(shù)分為四類。其中，四元式（0）稱為0型，（1）稱為1型；（2）和（3）稱為2型；（5）稱為3型。對于3型四元式，由于對數(shù)組元素賦值的情形需特殊考慮，因此暫不討論，對四元式（6）也不涉及，下面是僅含0,1,2型四元式的基本塊的DAG構(gòu)造算法。首先，DAG為空。對基本塊的每一四元式，依次執(zhí)行：1、如果NODE（B）無定義，則構(gòu)造一標(biāo)記為B的葉結(jié)點(diǎn)并定義NODE（B）為這個(gè)結(jié)點(diǎn)；如果當(dāng)前四元式是0型，則記NODE（B）的值為n，轉(zhuǎn)4。如果當(dāng)前四元式是1型，則轉(zhuǎn)2．（１）。如果當(dāng)前四元式是2型，則：（1）如果NODE（C）無定義，則構(gòu)造一標(biāo)記為C的葉結(jié)點(diǎn)并定義NODE（C）為這個(gè)結(jié)點(diǎn)，（2）轉(zhuǎn)2．（2）。2、（1）如果NODE（B）的標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則轉(zhuǎn)2（3），否則轉(zhuǎn)3．（１）。（2）如果NODE（B）和NODE（C）都是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則轉(zhuǎn)2．（4），否則轉(zhuǎn)3．（2）。（3）執(zhí)行opB（即合并已知量），令得到的新常數(shù)為P。如果NODE（B）是處理當(dāng)前四元式時(shí)新構(gòu)造出來的結(jié)點(diǎn)，則刪除它。如果NODE（P）無定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點(diǎn)n。置NODE（P）=n，轉(zhuǎn)4．。3、（1）檢查DAG中是否已有一結(jié)點(diǎn)，其唯一后繼為NODE（B），且標(biāo)記為op（即找公共子表達(dá)式）。如果沒有，則構(gòu)造該結(jié)點(diǎn)，否則就把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n，轉(zhuǎn)4.。（2）檢查DAG中是否已有一結(jié)點(diǎn)，其左后繼為NODE（B），右后繼為NODE（C），且標(biāo)記為op（即找公共子表達(dá)式）。如果沒有，則構(gòu)造該結(jié)點(diǎn)n，否則就把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n。轉(zhuǎn)4．。4、如果NODE（A）無定義，則把A附加在結(jié)點(diǎn)n上并令NODE（A）=n；否則先把A從NODE（A）結(jié)點(diǎn)上的附加標(biāo)識符集中刪除（注意，如果NODE（A）是葉結(jié)點(diǎn)，則其標(biāo)記A不刪除），把A附加到新結(jié)點(diǎn)n上并令NODE（A）=n。轉(zhuǎn)處理下一四元式。例1試構(gòu)造以下基本塊G的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*T6r=+R=+3.14=+3.14=+6.28=+r=+R=+3.14=+3.14=+6.28=+3.14=+6.28=+T1=++=+T2n5n3n4T0=+n1n2T1=+T0=+n1n2T0=+n1(a)(b)(c)TT2r=+3.14=+6.28=+T1=++=+T0=+n1n2T1=+n43.14=+6.28=+T1=+T0=+n1n2R=+r=+n3n4*=+T2A,Bn6n5+=+T2An5*=+n6R=+n3(d)(e)*=+r*=+r=+3.14=+6.28=+T1=++=+T0=+n1n2T1=+n4(f)(g)3.14=+6.28=+T1,T3=+T0=+n1n2R=+r=+n4*=+T2,T4A,Bn6n5+=+T2A,Bn5n6T1,T3=+R=+n3n3T0T1,T3+－T6T2,T4*n8n5n7*rn4Rn33.14n16.28n2A,B,T5n6(j)A,B,T5T0T1,T3+T6*n6rRn36.28n2－3.14n1n4T2,T4n7n5(i)A,B,T5T1,T3+*n6rRn36.28n23.14n1n4T2,T4n5(h)T0T0圖10-3-4由四元式構(gòu)造的DAG第四節(jié)代碼生成概述代碼生成是把經(jīng)過語法分析或優(yōu)化后的中間代碼作為輸入，將其轉(zhuǎn)換成特定機(jī)器的機(jī)器語言或匯編語言作為輸出，這樣的轉(zhuǎn)換程序稱為代碼生成器，因此，代碼生成器的構(gòu)造與輸入的中間代碼形式和輸出的目標(biāo)代碼的機(jī)器結(jié)構(gòu)密切相關(guān)。特別是高級語言和計(jì)算機(jī)的多種多樣性為代碼生成的理論研究和實(shí)現(xiàn)技術(shù)帶來很大的復(fù)雜性。由于一個(gè)高級程序設(shè)計(jì)語言的目標(biāo)代碼需反復(fù)使用，因而，代碼生成器的設(shè)計(jì)要著重考慮目標(biāo)代碼的質(zhì)量問題。衡量目標(biāo)代碼的質(zhì)量主要從占用空間和執(zhí)行效率兩個(gè)方面綜合考慮。到底產(chǎn)生什么樣的目標(biāo)代碼取決于具體的機(jī)器結(jié)構(gòu)、指令格式、字長及寄存器的個(gè)數(shù)和種類，并與指令的語義和所用操作系統(tǒng)、存儲管理等都密切相關(guān)。目標(biāo)代碼的執(zhí)行效率在很大程度上依賴于寄存器的使用。第五節(jié)習(xí)題一、單項(xiàng)選擇題1、優(yōu)化可生成 的目標(biāo)代碼。 a．運(yùn)行時(shí)間較短 b．占用存儲空間較小c．運(yùn)行時(shí)間短但占用內(nèi)存空間大 d．運(yùn)行時(shí)間短且占用存儲空間小2、下列 優(yōu)化方法不是針對循優(yōu)化進(jìn)行的。 a．強(qiáng)度削弱 b．刪除歸納變量 c．刪除多余運(yùn)算 d．代碼外提3、基本塊內(nèi)的優(yōu)化為 。 a．代碼外提，刪除歸納變量 b．刪除多余運(yùn)算，刪除無用賦值c．強(qiáng)度削弱，代碼外提 d．循環(huán)展開，循環(huán)合并4、關(guān)于必經(jīng)結(jié)點(diǎn)的二元關(guān)系，下列敘述中不正確的是 。 a．滿足自反性 b．滿足傳遞性 c．滿足反對稱性 d．滿足對稱性5、對一個(gè)基本塊來說， 是正確的。 a．只有一個(gè)入口語句和一個(gè)出口語句 b．有一個(gè)入口語句和多個(gè)出口語句c．有多個(gè)入口語句和一個(gè)出口語句 d．有多個(gè)入口語句和多個(gè)出口語句6、在程序流圖中，我們稱具有下述性質(zhì) 的結(jié)點(diǎn)序列為一個(gè)循環(huán)。 a．它們是非連通的且只有一個(gè)入口結(jié)點(diǎn) b．它們是強(qiáng)連通的但有多個(gè)入口結(jié)點(diǎn)c．它們是非連通的但有多個(gè)入口結(jié)點(diǎn) d．它們是強(qiáng)連通的且只有一個(gè)入口結(jié)點(diǎn)7、 不可能是目標(biāo)代碼。 a．匯編指令代碼 b．可重定位指令代碼 c．絕對指令代碼 d．中間代碼[解答]1、優(yōu)化的目的是使目