第10講--目標(biāo)生成

1、第十講第十講 目標(biāo)代碼生成目標(biāo)代碼生成u目標(biāo)代碼的形式目標(biāo)代碼的形式u抽象機(jī)模型抽象機(jī)模型u簡單代碼生成器簡單代碼生成器u寄存器分配寄存器分配CompilerPrinciples2源程序編譯前端中間代碼代碼優(yōu)化中間代碼代碼生成器目標(biāo)程序符 號 表 代碼生成器的位置代碼生成器的位置編譯程序的最后一個階段的工作是生成目標(biāo)代碼，它以源程編譯程序的最后一個階段的工作是生成目標(biāo)代碼，它以源程序的中間代碼作為輸入，以等價的目標(biāo)代碼作為輸出。序的中間代碼作為輸入，以等價的目標(biāo)代碼作為輸出。CompilerPrinciples3 代碼生成器的輸入包括中間代碼和符號表中的信息，輸出的目標(biāo)代碼一般有以下三種形式：

2、 （1）能獨(dú)立執(zhí)行的機(jī)器語言代碼，所有地址均已定位。 （2）待裝配的機(jī)器語言模塊。當(dāng)需要執(zhí)行時，由連接裝入程序把它們和某些運(yùn)行程序連接起來，轉(zhuǎn)換成能執(zhí)行的機(jī)器語言代碼。 （3）匯編語言代碼，尚須經(jīng)過匯編程序匯編，轉(zhuǎn)換成可執(zhí)行的機(jī)器代碼。 CompilerPrinciples4 代碼生成器的設(shè)計細(xì)節(jié)要依賴于目標(biāo)語言和操作系統(tǒng)，因此必須考慮以下問題: 1.如何使生成的目標(biāo)代碼較短； 2.如何充分利用計算機(jī)的寄存器，減少目標(biāo)代碼中訪問存儲單元的次數(shù)； 3.計算順序的選擇； 4.充分利用目標(biāo)計算機(jī)的指令系統(tǒng)的特點(diǎn)。 這些問題都直接影響到生成的代碼的質(zhì)量（速度和大小）。v 這里我們不打算針對某臺具體機(jī)器

3、談代碼生成，只是通過一個抽象的目標(biāo)機(jī)器模型來說明如何生成有效的代碼。CompilerPrinciples51.1.抽象機(jī)模型抽象機(jī)模型v 我們這兒使用的機(jī)器具有多個通用寄存器，它們既可以做累加器，也可作為變址器。這臺機(jī)器含有如下四種類型的指令：類型指令形式意義直接地址型 op op R Ri i,M,M( (R Ri i)op(M)op(M) ) R Ri i寄存器型op op R Ri i,R,Rj j( (R Ri i)op(R)op(Rj j) ) R Ri i變址型op op R Ri i,c(R,c(Rj j) )( (R Ri i)op(R)op(Rj j)+c)+c) ) R R

4、i i間接型op op R Ri i, ,* *M M( (R Ri i)op(M)op(M) ) R Ri iop op R Ri i, ,* *R Rj j( (R Ri i)op(R)op(Rj j) ) R Ri iop op R Ri i, ,* *c(Rc(Rj j) )( (R Ri i)op(R)op(Rj j)+c)+c) ) R Ri iCompilerPrinciples6v 以上指令中的運(yùn)算符op包括一般計算機(jī)上常見的一些運(yùn)算符，如ADD,SUB,MUL,DIV等。現(xiàn)將某些指令的意義說明如下：指令意義LD Ri,B把B單元的內(nèi)容取到寄存器Ri中ST Ri,B把寄存器Ri

5、的內(nèi)容存到單元B中J X無條件轉(zhuǎn)到X單元CMP A,B比較A,B單元的值，并根據(jù)AB分別將內(nèi)部特征寄存器CT置成相應(yīng)狀態(tài):0,1或2J X如CT=0(即A X如CT=2，轉(zhuǎn)X單元J X如CT1，轉(zhuǎn)X單元CompilerPrinciples7v例： ST R0,M 將寄存器R0的內(nèi)容存入存儲單元M中; ST R0,4(R1) 將R0中的值存入(4+(R1)所指單元; LD R0,*4(R1) 將(4+(R1)之值所指單元的內(nèi)容裝入R0中; LD R0,#1 將常數(shù)1裝入寄存器R0中；CompilerPrinciples82.2.簡單代碼生成器簡單代碼生成器v 這兒介紹一個簡單代碼生成器，它依次將

6、每條中間代碼變換成目標(biāo)代碼，并且在一個基本塊范圍內(nèi)考慮如何充分利用寄存器的問題。v 基本思想：在一個基本塊內(nèi)，當(dāng)生成計算某個變量的值的目標(biāo)代碼時，盡可能地使該值保留在寄存器中即不編出把該變量的值送主存單元的指令，這樣后繼的目標(biāo)代碼盡可能地引用變量在寄存器中的值，而減少對主存的訪問。而在基本塊結(jié)束時，因?yàn)橐粋€基本塊可能有幾個后繼，而且每個后繼亦可能有幾個前驅(qū)，所以此時應(yīng)把寄存器中的變量值存到主存單元，以使后繼基本塊能取到該變量的值。CompilerPrinciples9v 我們知道，任何一臺計算機(jī)的通用寄存器個數(shù)是有限的，不可能、也沒必要給每個變量固定地分配一個寄存器。也就是說，對于在基本塊內(nèi)不

7、再使用的變量所占用的寄存器要及時釋放，這樣一來，每當(dāng)翻譯一條中間代碼A:=B op C時，必須預(yù)先知道A,B,C是否還會在該基本塊中被引用，以及要引用到哪些中間代碼為止。為此，我們引入以下術(shù)語： CompilerPrinciples10 一、待用信息一、待用信息 在一個基本塊中，若四元式i對A定值，四元式j(luò)要引用A的值，而從i到j(luò)之間再沒有A的其他定值，那么，我們稱四元式j(luò)為i的關(guān)于變量A的待用信息。 注意：這里我們僅對基本塊內(nèi)考慮待用信息，一個變量在基本塊的后繼中是否被引用，可從活躍變量信息得知。 為了取得每個變量在基本塊內(nèi)的待用信息，可從基本塊的出口由后向前掃描，對每個變量建立相應(yīng)的待用信

8、息鏈和活躍變量信息鏈。 CompilerPrinciples11v 如果不進(jìn)行數(shù)據(jù)流分析，我們可以認(rèn)為所有臨時變量都不能跨基本塊引用，于是基本塊中的所有臨時變量均認(rèn)為是基本塊出口之后非活躍的，而所有非臨時變量均認(rèn)為是基本塊出口之后的活躍變量。 同時在符號表中增加“待用信息”欄和“活躍信息”欄， 于是可按如下方法計算變量的待用信息：NAMENAMEWAITWAITLIVELIVET1T1i iY YCompilerPrinciples12v算法步驟： (1)開始時從基本塊入口依次掃描四元式，把基本塊中各變量的符號表登記項(xiàng)中的待用信息欄填為“非待用”，并根據(jù)該變量在基本塊出口之后是不是活躍的，把其

9、中的活躍信息欄填為“活躍”或“非活躍”。 (2)從基本塊出口到基本塊入口由后向前依次處理每個四元式，對i: A:=B op C執(zhí)行： 把符號表中變量把符號表中變量A A的待用信息和活躍信息附加的待用信息和活躍信息附加到中間代碼到中間代碼i i上；上； 把符號表中把符號表中A A的待用信息和活躍信息分別置為的待用信息和活躍信息分別置為“非待用非待用”和和“非活躍非活躍”；（因?yàn)樵?；（因?yàn)樵趇 i中對中對A A的定值的定值只能在只能在i i以后的四元式中引用，所以對在以后的四元式中引用，所以對在i i之前的四之前的四元式來說，元式來說，A A是不活躍也不待用的。）是不活躍也不待用的。）Compil

10、erPrinciples13 把符號表中變量把符號表中變量B B和和C C的待用信息和活躍信息附的待用信息和活躍信息附加到中間代碼加到中間代碼i i上；上； 把符號表中把符號表中B B和和C C的待用信息置為的待用信息置為i i，活躍信息，活躍信息置為置為“活躍活躍”。v 上述步驟執(zhí)行過后，通過符號表和附加在各個四元式上的待用信息就建立起一個鏈，該鏈指出了某個變量在基本塊內(nèi)的各個引用位置。v 要注意的是，上面的各步驟次序不能顛倒，因?yàn)锽和C也可能是A。如果四元式為A:=op B或A:=B，這些步驟也是一樣的，只是不涉及到C而已。CompilerPrinciples14例例： 若若用用 A，B，

11、C，D表表示示變變量量，用用 T，U，V表表示示中中間間變變量量，有有四四元元式式如如下下：（1） T:=A-B（2） U:=A-C（3） V:=T+U（4） D:=V+U其其名名字字表表中中的的待待用用信信息息和和活活躍躍信信息息如如下下表表，用用“F”表表示示“非非待待用用”“非非活活躍躍”，用用“L”表表示示活活躍躍。(1)(2)(3)(4)表表示示四四元元式式序序號號。CompilerPrinciples15待待用用信信息息和和活活躍躍信信息息 待待用用信信息息 活活躍躍信信息息變變量量名名初初值值 待待用用信信息息鏈鏈初初值值 活活躍躍信信息息鏈鏈A F(2)(1) L L LB F

12、(1) L LC F(2) L LD F F L FT F(3) F F L FU F(4)(3) F F L L FV F(4) F F L F表表中中“待待用用信信息息鏈鏈”與與“活活躍躍信信息息鏈鏈”的的每每列列從從左左至至右右為為每每從從后后向向前前掃掃描描一一個個四四元元式式時時相相應(yīng)應(yīng)變變量量的的信信息息變變化化情情況況，空空白白處處為為沒沒變變化化。待待用用信信息息和和活活躍躍信信息息在在四四元元式式上上的的標(biāo)標(biāo)記記如如下下所所示示：(1) T(3)L:=A(2)L-BFL(2) U(3)L:=AFL-CFL(3) V(4)L:=TFF+U(4)L(4) DFL:=VFF+UFF

13、CompilerPrinciples16 二、寄存器描述和地址描述二、寄存器描述和地址描述 1.寄存器描述：建立一個編譯用的寄存器描述數(shù)組RVALUE，它動態(tài)地記錄著各寄存器的使用情況：空閑，還是分配給某個變量或某幾個變量。 2.地址描述：建立一個變量地址描述數(shù)組AVALUE，它動態(tài)地記錄各變量現(xiàn)行值的存放位置：是在某寄存器中，還是在某個主存單元中，或者即在寄存器中又在主存中。 有了以上的準(zhǔn)備工作后，我們就可以著手進(jìn)行一個基本塊的代碼生成了。CompilerPrinciples17 三、三、基本塊的代碼生成算法基本塊的代碼生成算法 為簡單起見，只考慮形如A:=B op C的四元式序列。對每個四

14、元式i: A:=B op C，依次執(zhí)行下述步驟： 1.以四元式i: A:=B op C為參數(shù)，調(diào)用過程getreg(i: A:=B op C)。從getreg返回時，得到一寄存器R，用它作存放A現(xiàn)行值的寄存器； 2.利用AVALUEB和AVALUEC，確定出B和C現(xiàn)行值存放位置B和C； Getreg()是一個函數(shù)過程，詳見P316。 CompilerPrinciples18 3.如BR，則生成目標(biāo)代碼 LD R,B op R,C 否則，生成目標(biāo)代碼 op R，C ； 如B或C為R，則刪除AVALUEB或AVALUEC中的R 4.令A(yù)VALUEA=R，并令RVALUER=A，以表示變量A的現(xiàn)行值

15、只在R中并且R中的值只代表A的現(xiàn)行值； 5.如B或C的現(xiàn)行值在基本塊中不再被引用，它們也不是基本塊出口之后的活躍變量（由四元式i上的附加信息知道），并且其現(xiàn)行值在某個寄存器Rk中，則刪除RVALUERk中的B或C以及AVALUEB或AVALUEC中的Rk，使該寄存器不再為B或C所占用。CompilerPrinciples19v例，對于計算D:=(A-B)+(A-C)+(A-C)D:=(A-B)+(A-C)+(A-C)的四元式： T:=A-B U:=A-C V:=T+U D:=V+UT:=A-B U:=A-C V:=T+U D:=V+U 假設(shè)只有R0,R1兩個可用寄存器，則生成目標(biāo)如下：語句目標(biāo)

16、代碼 寄存器描述器地址描述器T:=ABLD R0,ASUB R0,BR0包含TT在R0中U:=ACLD R1,ASUB R1,CR0包含TR1包含UT在R0中U在R1中V:=TUADD R0,R1R0包含VR1包含UV在R0中U在R1中D:=VUADD R0,R1ST R0,DR0包含DD在R0中D在R0中和存儲器中CompilerPrinciples20v 在處理完基本塊中所有代碼后，對現(xiàn)行值只在某個寄存器中的變量M，如果它在基本塊出口之后是活躍的，則必須把它存到主存中去，上例中的最后一條指令ST R0,D就是如此。v 以上所談簡單代碼生成器的構(gòu)造中，對寄存器的使用我們已經(jīng)談了幾個基本原則：

17、每生成一條目標(biāo)代碼時，如果操作數(shù)在寄存器則用寄存器作操作數(shù)地址，不用的寄存器要盡早釋放等。那么，如何才能更有效的使用寄存器呢？下面我們就來討論一下這個問題。CompilerPrinciples213.3.寄存器分配寄存器分配v 現(xiàn)在我們將考慮范圍從基本塊擴(kuò)大到循環(huán)，因?yàn)槌绦蛑袌?zhí)行次數(shù)最多的部分是循環(huán)。同時，我們不把寄存器平均分配給各個變量使用，而是從可用的寄存器中化出一部分，固定分配給那些在循環(huán)中要訪問主存單元的變量。為此，再引入一個新術(shù)語： 1.指令的執(zhí)行代價：指令的執(zhí)行代價： 每條指令的執(zhí)行代價=訪問主存單元次數(shù)+1 例： op Ri,Rj 執(zhí)行代價為1 op Ri,M 執(zhí)行代價為2 op

18、 Ri,*Rj 執(zhí)行代價為2 op Ri,*M 執(zhí)行代價為3CompilerPrinciples22v 于是，我們可以對循環(huán)中每個變量計算一下，如果在循環(huán)中把某個寄存器固定分配給該變量使用，可以節(jié)省多少執(zhí)行代價。根據(jù)計算的結(jié)果，就可以把可用的幾個寄存器固定分配給節(jié)省執(zhí)行代價最多的變量，從而使這幾個寄存器發(fā)揮最大作用。下面，我們就介紹計算各變量執(zhí)行代價的算法。CompilerPrinciples23 2.計算節(jié)省的變量執(zhí)行代價：計算節(jié)省的變量執(zhí)行代價： (1)在原簡單代碼生成算法中，只有當(dāng)變量在基本塊中被定值時，其值才放在寄存器中，現(xiàn)在把寄存器固定分配某變量使用。因此，當(dāng)該變量在基本塊中被定值前

19、，每引用它一次就可以少訪問主存一次，執(zhí)行代價就節(jié)省1。 (2)在原代碼生成算法中，若某變量在基本塊中被定值且在基本塊出口之后是活躍的，則出基本塊時要把其值由寄存器存儲到主存單元；現(xiàn)在把寄存器固定分配該變量使用，就無須再往主存里放了。因此，執(zhí)行代價節(jié)省2。CompilerPrinciples24v 對循環(huán)L中某變量M，如果分配一個寄存器給它專用，那么每執(zhí)行循環(huán)一次，節(jié)省的執(zhí)行代價為： BLUSE(M,B)+2*LIVE(M,B) 其中： USE(M,B)表示在基本塊B中對M定值前引用M的次數(shù)，如果M在基本塊B中定值并且在B的出口之后是活躍的，則LIVE(M,B)=1，其它情況為0 。 注意，這兒

20、忽略了幾個因素： 如果M在循環(huán)入口之前是活躍的，在循環(huán)中還要給M分配一個固定寄存器，那么在循環(huán)入口處，必須先把M從主存單元中取到寄存器中，其代價為2；如果M在循環(huán)出口之后是活躍的，則還要存到主存去，也要花費(fèi)代價2。這些在公式計算時都略去了。CompilerPrinciples25 在每一次循環(huán)中，各個基本塊并不一定都能執(zhí)行到，在上述公式中這種情況也忽略了。 例：下圖代表某程序的最內(nèi)層循環(huán)，其中無條件轉(zhuǎn)移例：下圖代表某程序的最內(nèi)層循環(huán)，其中無條件轉(zhuǎn)移和條件轉(zhuǎn)移指令均改用箭頭來表示。各基本塊入口和條件轉(zhuǎn)移指令均改用箭頭來表示。各基本塊入口之前和出口之后的活躍變量已列在圖中。假定有三之前和出口之后的活躍變量已列在圖中。假定有三個通用寄存器個通用寄存器R0,R1和和R2，可以在循環(huán)中固定分配給可以在循環(huán)中固定分配給三個變量使用。現(xiàn)在，我們利用上述公式計算各變?nèi)齻€變量使用。現(xiàn)在，我們利用上述公式