第十講

目標(biāo)代碼生成目標(biāo)代碼的形式抽象機(jī)模型簡(jiǎn)單代碼生成器寄存器分配1CompilerPrinciples源程序編譯前端中間代碼代碼優(yōu)化中間代碼代碼生成器目標(biāo)程序符號(hào)表

代碼生成器的位置編譯程序的最后一個(gè)階段的工作是生成目標(biāo)代碼，它以源程序的中間代碼作為輸入，以等價(jià)的目標(biāo)代碼作為輸出。2CompilerPrinciples代碼生成器的輸入包括中間代碼和符號(hào)表中的信息，輸出的目標(biāo)代碼一般有以下三種形式：（1）能獨(dú)立執(zhí)行的機(jī)器語(yǔ)言代碼，所有地址均已定位。（2）待裝配的機(jī)器語(yǔ)言模塊。當(dāng)需要執(zhí)行時(shí)，由連接裝入程序把它們和某些運(yùn)行程序連接起來(lái)，轉(zhuǎn)換成能執(zhí)行的機(jī)器語(yǔ)言代碼。（3）匯編語(yǔ)言代碼，尚須經(jīng)過(guò)匯編程序匯編，轉(zhuǎn)換成可執(zhí)行的機(jī)器代碼。

3CompilerPrinciples代碼生成器的設(shè)計(jì)細(xì)節(jié)要依賴于目標(biāo)語(yǔ)言和操作系統(tǒng)，因此必須考慮以下問(wèn)題:1.如何使生成的目標(biāo)代碼較短；2.如何充分利用計(jì)算機(jī)的寄存器，減少目標(biāo)代碼中訪問(wèn)存儲(chǔ)單元的次數(shù)；3.計(jì)算順序的選擇；4.充分利用目標(biāo)計(jì)算機(jī)的指令系統(tǒng)的特點(diǎn)。這些問(wèn)題都直接影響到生成的代碼的質(zhì)量（速度和大?。?。這里我們不打算針對(duì)某臺(tái)具體機(jī)器談代碼生成，只是通過(guò)一個(gè)抽象的目標(biāo)機(jī)器模型來(lái)說(shuō)明如何生成有效的代碼。4CompilerPrinciples§1.抽象機(jī)模型我們這兒使用的機(jī)器具有多個(gè)通用寄存器，它們既可以做累加器，也可作為變址器。這臺(tái)機(jī)器含有如下四種類型的指令：5CompilerPrinciples

以上指令中的運(yùn)算符op包括一般計(jì)算機(jī)上常見(jiàn)的一些運(yùn)算符，如ADD,SUB,MUL,DIV等。現(xiàn)將某些指令的意義說(shuō)明如下：6CompilerPrinciples例：

STR0,M將寄存器R0的內(nèi)容存入存儲(chǔ)單元M中;STR0,4(R1)將R0中的值存入(4+(R1))所指單元;LDR0,*4(R1)將(4+(R1))之值所指單元的內(nèi)容裝入R0中;LDR0,#1將常數(shù)1裝入寄存器R0中；7CompilerPrinciples§2.簡(jiǎn)單代碼生成器這兒介紹一個(gè)簡(jiǎn)單代碼生成器，它依次將每條中間代碼變換成目標(biāo)代碼，并且在一個(gè)基本塊范圍內(nèi)考慮如何充分利用寄存器的問(wèn)題?；舅枷耄涸谝粋€(gè)基本塊內(nèi)，當(dāng)生成計(jì)算某個(gè)變量的值的目標(biāo)代碼時(shí)，盡可能地使該值保留在寄存器中——即不編出把該變量的值送主存單元的指令，這樣后繼的目標(biāo)代碼盡可能地引用變量在寄存器中的值，而減少對(duì)主存的訪問(wèn)。而在基本塊結(jié)束時(shí)，因?yàn)橐粋€(gè)基本塊可能有幾個(gè)后繼，而且每個(gè)后繼亦可能有幾個(gè)前驅(qū)，所以此時(shí)應(yīng)把寄存器中的變量值存到主存單元，以使后繼基本塊能取到該變量的值。8CompilerPrinciples

我們知道，任何一臺(tái)計(jì)算機(jī)的通用寄存器個(gè)數(shù)是有限的，不可能、也沒(méi)必要給每個(gè)變量固定地分配一個(gè)寄存器。也就是說(shuō)，對(duì)于在基本塊內(nèi)不再使用的變量所占用的寄存器要及時(shí)釋放，這樣一來(lái)，每當(dāng)翻譯一條中間代碼A:=BopC時(shí)，必須預(yù)先知道A,B,C是否還會(huì)在該基本塊中被引用，以及要引用到哪些中間代碼為止。為此，我們引入以下術(shù)語(yǔ)：

9CompilerPrinciples一、待用信息

在一個(gè)基本塊中，若四元式i對(duì)A定值，四元式j(luò)要引用A的值，而從i到j(luò)之間再?zèng)]有A的其他定值，那么，我們稱四元式j(luò)為i的關(guān)于變量A的待用信息。

注意：這里我們僅對(duì)基本塊內(nèi)考慮待用信息，一個(gè)變量在基本塊的后繼中是否被引用，可從活躍變量信息得知。

為了取得每個(gè)變量在基本塊內(nèi)的待用信息，可從基本塊的出口由后向前掃描，對(duì)每個(gè)變量建立相應(yīng)的待用信息鏈和活躍變量信息鏈。10CompilerPrinciples如果不進(jìn)行數(shù)據(jù)流分析，我們可以認(rèn)為所有臨時(shí)變量都不能跨基本塊引用，于是基本塊中的所有臨時(shí)變量均認(rèn)為是基本塊出口之后非活躍的，而所有非臨時(shí)變量均認(rèn)為是基本塊出口之后的活躍變量。

同時(shí)在符號(hào)表中增加“待用信息”欄和“活躍信息”欄，于是可按如下方法計(jì)算變量的待用信息：11CompilerPrinciples算法步驟：(1)開(kāi)始時(shí)從基本塊入口依次掃描四元式，把基本塊中各變量的符號(hào)表登記項(xiàng)中的待用信息欄填為“非待用”，并根據(jù)該變量在基本塊出口之后是不是活躍的，把其中的活躍信息欄填為“活躍”或“非活躍”。(2)從基本塊出口到基本塊入口由后向前依次處理每個(gè)四元式，對(duì)i:A:=BopC執(zhí)行：

①把符號(hào)表中變量A的待用信息和活躍信息附加到中間代碼i上；②把符號(hào)表中A的待用信息和活躍信息分別置為“非待用”和“非活躍”；（因?yàn)樵趇中對(duì)A的定值只能在i以后的四元式中引用，所以對(duì)在i之前的四元式來(lái)說(shuō)，A是不活躍也不待用的。）12CompilerPrinciples③把符號(hào)表中變量B和C的待用信息和活躍信息附加到中間代碼i上；④把符號(hào)表中B和C的待用信息置為i，活躍信息置為“活躍”。上述步驟執(zhí)行過(guò)后，通過(guò)符號(hào)表和附加在各個(gè)四元式上的待用信息就建立起一個(gè)鏈，該鏈指出了某個(gè)變量在基本塊內(nèi)的各個(gè)引用位置。要注意的是，上面的各步驟次序不能顛倒，因?yàn)锽和C也可能是A。如果四元式為A:=opB或A:=B，這些步驟也是一樣的，只是不涉及到C而已。13CompilerPrinciples14CompilerPrinciples15CompilerPrinciples二、寄存器描述和地址描述

1.寄存器描述：建立一個(gè)編譯用的寄存器描述數(shù)組RVALUE，它動(dòng)態(tài)地記錄著各寄存器的使用情況：空閑，還是分配給某個(gè)變量或某幾個(gè)變量。2.地址描述：建立一個(gè)變量地址描述數(shù)組AVALUE，它動(dòng)態(tài)地記錄各變量現(xiàn)行值的存放位置：是在某寄存器中，還是在某個(gè)主存單元中，或者即在寄存器中又在主存中。有了以上的準(zhǔn)備工作后，我們就可以著手進(jìn)行一個(gè)基本塊的代碼生成了。16CompilerPrinciples三、基本塊的代碼生成算法為簡(jiǎn)單起見(jiàn)，只考慮形如A:=BopC的四元式序列。對(duì)每個(gè)四元式i:A:=BopC，依次執(zhí)行下述步驟：1.以四元式i:A:=BopC為參數(shù)，調(diào)用過(guò)程getreg(i:A:=BopC)。從getreg返回時(shí)，得到一寄存器R，用它作存放A現(xiàn)行值的寄存器；2.利用AVALUE[B]和AVALUE[C]，確定出B和C現(xiàn)行值存放位置B′和C′；Getreg()是一個(gè)函數(shù)過(guò)程，詳見(jiàn)P316。17CompilerPrinciples3.如B′≠R，則生成目標(biāo)代碼LDR,B′opR,C′否則，生成目標(biāo)代碼opR，C′；如B′或C′為R，則刪除AVALUE[B]或AVALUE[C]中的R4.令A(yù)VALUE[A]={R}，并令RVALUE[R]={A}，以表示變量A的現(xiàn)行值只在R中并且R中的值只代表A的現(xiàn)行值；5.如B或C的現(xiàn)行值在基本塊中不再被引用，它們也不是基本塊出口之后的活躍變量（由四元式i上的附加信息知道），并且其現(xiàn)行值在某個(gè)寄存器Rk中，則刪除RVALUE[Rk]中的B或C以及AVALUE[B]或AVALUE[C]中的Rk，使該寄存器不再為B或C所占用。18CompilerPrinciples例，對(duì)于計(jì)算D:=(A-B)+(A-C)+(A-C)的四元式：T:=A-BU:=A-CV:=T+UD:=V+U

假設(shè)只有R0,R1兩個(gè)可用寄存器，則生成目標(biāo)如下：19CompilerPrinciples

在處理完基本塊中所有代碼后，對(duì)現(xiàn)行值只在某個(gè)寄存器中的變量M，如果它在基本塊出口之后是活躍的，則必須把它存到主存中去，上例中的最后一條指令STR0,D就是如此。以上所談簡(jiǎn)單代碼生成器的構(gòu)造中，對(duì)寄存器的使用我們已經(jīng)談了幾個(gè)基本原則：每生成一條目標(biāo)代碼時(shí)，如果操作數(shù)在寄存器則用寄存器作操作數(shù)地址，不用的寄存器要盡早釋放等。那么，如何才能更有效的使用寄存器呢？下面我們就來(lái)討論一下這個(gè)問(wèn)題。20CompilerPrinciples§3.寄存器分配現(xiàn)在我們將考慮范圍從基本塊擴(kuò)大到循環(huán)，因?yàn)槌绦蛑袌?zhí)行次數(shù)最多的部分是循環(huán)。同時(shí)，我們不把寄存器平均分配給各個(gè)變量使用，而是從可用的寄存器中化出一部分，固定分配給那些在循環(huán)中要訪問(wèn)主存單元的變量。為此，再引入一個(gè)新術(shù)語(yǔ)：

1.指令的執(zhí)行代價(jià)：每條指令的執(zhí)行代價(jià)=訪問(wèn)主存單元次數(shù)+1例：opRi,Rj執(zhí)行代價(jià)為1opRi,M執(zhí)行代價(jià)為2opRi,*Rj執(zhí)行代價(jià)為2opRi,*M執(zhí)行代價(jià)為321CompilerPrinciples于是，我們可以對(duì)循環(huán)中每個(gè)變量計(jì)算一下，如果在循環(huán)中把某個(gè)寄存器固定分配給該變量使用，可以節(jié)省多少執(zhí)行代價(jià)。根據(jù)計(jì)算的結(jié)果，就可以把可用的幾個(gè)寄存器固定分配給節(jié)省執(zhí)行代價(jià)最多的變量，從而使這幾個(gè)寄存器發(fā)揮最大作用。下面，我們就介紹計(jì)算各變量執(zhí)行代價(jià)的算法。22CompilerPrinciples2.計(jì)算節(jié)省的變量執(zhí)行代價(jià)：

(1)在原簡(jiǎn)單代碼生成算法中，只有當(dāng)變量在基本塊中被定值時(shí)，其值才放在寄存器中，現(xiàn)在把寄存器固定分配某變量使用。因此，當(dāng)該變量在基本塊中被定值前，每引用它一次就可以少訪問(wèn)主存一次，執(zhí)行代價(jià)就節(jié)省1。(2)在原代碼生成算法中，若某變量在基本塊中被定值且在基本塊出口之后是活躍的，則出基本塊時(shí)要把其值由寄存器存儲(chǔ)到主存單元；現(xiàn)在把寄存器固定分配該變量使用，就無(wú)須再往主存里放了。因此，執(zhí)行代價(jià)節(jié)省2。23CompilerPrinciples

對(duì)循環(huán)L中某變量M，如果分配一個(gè)寄存器給它專用，那么每執(zhí)行循環(huán)一次，節(jié)省的執(zhí)行代價(jià)為：

ΣB∈L[USE(M,B)+2*LIVE(M,B)]其中：USE(M,B)表示在基本塊B中對(duì)M定值前引用M的次數(shù)，如果M在基本塊B中定值并且在B的出口之后是活躍的，則LIVE(M,B)=1，其它情況為0。注意，這兒忽略了幾個(gè)因素：①如果M在循環(huán)入口之前是活躍的，在循環(huán)中還要給M分配一個(gè)固定寄存器，那么在循環(huán)入口處，必須先把M從主存單元中取到寄存器中，其代價(jià)為2；如果M在循環(huán)出口之后是活躍的，則還要存到主存去，也要花費(fèi)代價(jià)2。這些在公式計(jì)算時(shí)都略去了。24CompilerPrinciples②在每一次循環(huán)中，各個(gè)基本塊并不一定都能執(zhí)行到，在上述公式中這種情況也忽略了。

例：下圖代表某程序的最內(nèi)層循環(huán)，其中無(wú)條件轉(zhuǎn)移和條件轉(zhuǎn)移指令均改用箭頭來(lái)表示。各基本塊入口之前和出口之后的活躍變量已列在圖中。假定有三個(gè)通用寄存器R0,R1和R2，可以在循環(huán)中固定分配給三個(gè)變量使用?，F(xiàn)在，我們利用上述公式計(jì)算各變量的執(zhí)行代價(jià)節(jié)省數(shù)，然后取執(zhí)行代價(jià)節(jié)省數(shù)最高的三個(gè)變量來(lái)分配寄存器。(P319)25CompilerPrinciplesa:=b+cd:=d-be:=a+ff:=a-db:=d+fe:=a-cb:=d+cbcdfacdefacdecdefacdfcdefbcdefbdef是活躍變量bcdef是活躍變量B1B2B3B426CompilerPrinciples解：因?yàn)锽1中引用a前已對(duì)a定值，所以u(píng)se(a,B1)=0;在B2,B3中a被各引用一次，且在引用前未對(duì)a定值，所以u(píng)se(a,B2)=use(a,B3)=1;B4中未引用a，所以u(píng)se(a,B4)=0。因?yàn)閍在B1中被定值且a在B1出口是活躍的，a在B2,B3和B4出口后不是活躍的，所以：live(a,B1)=1live(a,B2)=live(a,B3)=live(a,B4)=0;則代價(jià)節(jié)省數(shù)為：1+1+2*1=4。