第十講

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

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

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

以上指令中的運算符op包括一般計算機上常見的一些運算符，如ADD,SUB,MUL,DIV等?，F(xiàn)將某些指令的意義說明如下：6CompilerPrinciples例：

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

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

9CompilerPrinciples一、待用信息

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

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

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

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

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

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

假設只有R0,R1兩個可用寄存器，則生成目標如下：19CompilerPrinciples

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

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

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

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

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

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