編譯原理與技術(shù)講義 第10章 目標(biāo)代碼生成

1、編譯原理與技術(shù)第10章 目標(biāo)代碼生成 青島大學(xué)信息工程學(xué)院主要內(nèi)容代碼生成器設(shè)計(jì)的基本問題 虛擬計(jì)算機(jī)模型 語(yǔ)法制導(dǎo)的目標(biāo)代碼生成 基本塊和待用信息 一個(gè)簡(jiǎn)單代碼生成器代碼生成技術(shù)小結(jié) 編譯原理與技術(shù)210.1 代碼生成器設(shè)計(jì)的基本問題 代碼生成在整個(gè)編譯過程的位置符號(hào)表代碼生成中間代碼生成與優(yōu)化語(yǔ)法樹目標(biāo)程序中間代碼中間代碼語(yǔ)義分析中間代碼編譯原理與技術(shù)310.1 代碼生成器設(shè)計(jì)的基本問題目標(biāo)程序 絕對(duì)機(jī)器代碼，程序所有的內(nèi)存地址，特別是程序的起始地址，在編譯時(shí)都已經(jīng)固定。這種代碼的優(yōu)點(diǎn)是裝入機(jī)器后就可以立即執(zhí)行，對(duì)于小程序可以快速編譯和運(yùn)行?？芍囟ㄎ粰C(jī)器代碼（可重定位目標(biāo)模塊），代碼裝入內(nèi)

2、存的起始地址可以任意改變。一組可重定位的若干目標(biāo)模塊，經(jīng)過連接和裝配后才可以運(yùn)行。盡管這些工作增加了程序運(yùn)行的代價(jià)，但是，可重定位機(jī)器代碼的優(yōu)點(diǎn)是靈活性。這種技術(shù)允許程序分模塊編寫，獨(dú)立地編譯成目標(biāo)模塊，并且從目標(biāo)模塊庫(kù)中調(diào)用其它已經(jīng)編譯好的模塊，便于程序開發(fā)。通常，可重定位機(jī)器代碼中包含可重定位信息和連接信息。如果目標(biāo)代碼是匯編語(yǔ)言程序，還需要匯編后才能運(yùn)行。只要地址可以由偏移址及符號(hào)表中的其它信息計(jì)算得到，代碼生成器就可以產(chǎn)生程序中名字的絕對(duì)地址或可重定位地址。這樣生成代碼的好處是不用生成二進(jìn)制的機(jī)器代碼，而是產(chǎn)生符號(hào)指令并用宏機(jī)制來幫助產(chǎn)生機(jī)器代碼，使得代碼生成過程變得容易。為了可讀性，

3、本章采用匯編語(yǔ)言作為目標(biāo)語(yǔ)言。編譯原理與技術(shù)410.1 代碼生成器設(shè)計(jì)的基本問題指令選擇一個(gè)編譯程序可以看成是一個(gè)轉(zhuǎn)換系統(tǒng)，它把源程序轉(zhuǎn)換成等價(jià)的目標(biāo)代碼，也就是說，對(duì)源語(yǔ)言種各種語(yǔ)言結(jié)構(gòu)，依據(jù)語(yǔ)義確定相應(yīng)的目標(biāo)代碼結(jié)構(gòu)，即確定源語(yǔ)言于目標(biāo)語(yǔ)言之間的對(duì)應(yīng)關(guān)系，確保正確實(shí)現(xiàn)語(yǔ)義。顯然，能否建立這樣的關(guān)系直接影響到編譯程序的質(zhì)量。目標(biāo)機(jī)器指令系統(tǒng)的性質(zhì)決定了指令選擇的難以程度，指令系統(tǒng)的一致性和完備性直接影響到這種對(duì)應(yīng)關(guān)系的建立。如果目標(biāo)機(jī)器能一致地支持各種數(shù)據(jù)類型和尋址方式，不需特別處理例外，這種對(duì)應(yīng)關(guān)系的建立就容易得多。指令執(zhí)行速度和機(jī)器特點(diǎn)對(duì)產(chǎn)生目標(biāo)代碼的質(zhì)量也十分重要。顯然，如果指令集合豐

4、富的目標(biāo)機(jī)器對(duì)于某種操作可提供集中處理的時(shí)候，應(yīng)該選擇效率高、執(zhí)行速度快的一種。 編譯原理與技術(shù)510.1 代碼生成器設(shè)計(jì)的基本問題寄存器選擇 計(jì)算機(jī)存儲(chǔ)單元之間通常都是通過寄存器聯(lián)系。寄存器可以保存計(jì)算的中間結(jié)果，而且運(yùn)算對(duì)象在寄存器的指令一般都比運(yùn)算對(duì)象在內(nèi)存的指令要短且運(yùn)算的快。因此，充分合理地利用寄存器對(duì)生成高質(zhì)量的代碼十分重要。對(duì)于寄存器的使用，應(yīng)該考慮程序中的哪些變量駐留在寄存器中、駐留多長(zhǎng)時(shí)間。進(jìn)一步，哪個(gè)變量駐留在哪個(gè)寄存器。這些問題可以劃分成兩個(gè)子問題：在寄存器分配期間，為程序的某一點(diǎn)選擇駐留在寄存器中的一組變量；在隨后的寄存器指派階段，選擇變量要駐留的具體寄存器。選擇最優(yōu)的

5、寄存器指派方案極其困難，從數(shù)學(xué)以上講，這是一個(gè)NP完全問題。如果考慮到目標(biāo)機(jī)器的硬件、操作系統(tǒng)對(duì)寄存器使用的一些要求時(shí)，這個(gè)問題就變得更加復(fù)雜。 編譯原理與技術(shù)610.1 代碼生成器設(shè)計(jì)的基本問題計(jì)算順序的選擇計(jì)算執(zhí)行的順序會(huì)影響目標(biāo)代碼的質(zhì)量。改變運(yùn)算的執(zhí)行順序可以減少需要用來保存中間結(jié)果的寄存器的個(gè)數(shù)，從而提高代碼的效率。計(jì)算順序最優(yōu)選擇也是一個(gè)非常困難的問題，一個(gè)NP完全問題。本書不討論求值順序問題，簡(jiǎn)單地就按照源程序或中間代碼生成的順序生成目標(biāo)代碼。 編譯原理與技術(shù)710.2 虛擬計(jì)算機(jī)模型 作為目標(biāo)代碼生成階段地址分配的依據(jù) 這個(gè)目標(biāo)計(jì)算機(jī)模型具有n個(gè)通用寄存器R0，R1，Rn-1，

6、它們既可以作為累加器，也可以作為變址器。假設(shè)目標(biāo)機(jī)器按字節(jié)編址，4個(gè)字接組成一個(gè)字。我們用op表示運(yùn)算符，用字母M表示內(nèi)存單元，用字母C表示常量，用星號(hào)*表示間址方式存取。這臺(tái)機(jī)器指令的一般形式為操作碼 op 源數(shù)據(jù)域，目的數(shù)據(jù)域的二地址指令，表示源數(shù)據(jù)域和目的據(jù)域經(jīng)過op運(yùn)算以后的結(jié)果存到目的數(shù)據(jù)域。編譯原理與技術(shù)810.2 虛擬計(jì)算機(jī)模型指令按照地址模式分為四類，見表10.1類型指令形式含義（假設(shè)op是二元運(yùn)算符）直接地址型op M，Ri(M) op (Ri ) Ri寄存器型op Ri，Rj(Ri ) op (Rj ) Rj變址型op C(Ri)，Rj(Ri)+C) op (Ri ) Rj

7、間接型op M， Ri(M ) op (Ri ) Riop Ri，Rj，(Ri) op (Rj) Rjop C(Ri)，Rj，(Ri )+C) op (Rj) Rj立即數(shù)C常數(shù)C如果op是一元運(yùn)算符，則指令“op M，Ri”的含義為： op (M ) Ri，其余類型可以類推。上述指令中的運(yùn)算符（操作碼op）包括一般計(jì)算機(jī)上常見的一些運(yùn)算符，如加法ADD、減法SUB、負(fù)號(hào)NEG、乘法MUL、除法DIV、加1 INC、減1 DEC以及邏輯運(yùn)算AND、NOT、OR等等。 編譯原理與技術(shù)910.2 虛擬計(jì)算機(jī)模型當(dāng)用作源或目的時(shí)，內(nèi)存單元M和寄存器R都代表自身，例如，指令MOV R1, M采用直接地址

8、尋址方式，將寄存器R1的內(nèi)容存入內(nèi)存單元M。MOV 4(R1)，M采用變址尋址方式，把寄存器R1的偏移4的單元的內(nèi)容存入內(nèi)存單元M，即表中(4+R1) M。表中的間接變址尋址方式用前綴表示。例如，指令MOV 4(R1)，R2把地址(4+(R1)中內(nèi)容所指單元的內(nèi)容裝入寄存器R2中。常數(shù)用前綴#表示，下面的指令采用立即數(shù)尋址方式，把常數(shù)10裝入寄存器R1：MOV #10, R1指令意義指令意義MOV M， Ri把M單元的內(nèi)容存到寄存器Ri，即(M) RiCJ X 如CT=0或CT=1 轉(zhuǎn)到X單元J X無條件轉(zhuǎn)移到內(nèi)存單元XCJ X如CT=2 轉(zhuǎn)到X單元CMP M, N比較內(nèi)存單元M和N的值，根據(jù)

9、結(jié)果在機(jī)器內(nèi)部特征寄存器CT中設(shè)置相應(yīng)的狀態(tài)值：MN時(shí)CT2CJ X如CT=2或CT=1 轉(zhuǎn)到X單元CJ = X如CT=1 轉(zhuǎn)到X單元CJ X 如CT1 轉(zhuǎn)到X單元CJX如CT=0 轉(zhuǎn)到X單元編譯原理與技術(shù)1010.3 語(yǔ)法制導(dǎo)的目標(biāo)代碼生成 利用屬性文法和語(yǔ)法制導(dǎo)技術(shù)，直接產(chǎn)生目標(biāo)代碼?；驹砗图夹g(shù)同第9章介紹的語(yǔ)法制導(dǎo)的中間代碼翻譯類似，只是產(chǎn)生的目標(biāo)語(yǔ)言是機(jī)器指令。本節(jié)只討論如何用翻譯模式把源程序語(yǔ)言的簡(jiǎn)單賦值語(yǔ)句和表達(dá)式翻譯成目標(biāo)代碼，文法如下：S id : = EE E1 + E2 | E1 E2 | E1| ( E1) | idB B1 and B2 | B1 or B2 | n

10、ot B1| ( B1) | id1 relop id2 | true | false為了簡(jiǎn)單起見，這個(gè)算術(shù)表達(dá)式E只有加法、乘法與取負(fù)運(yùn)算，不包含數(shù)組、記錄等復(fù)雜的結(jié)構(gòu)的訪問，布爾表達(dá)式B只包括了三個(gè)邏輯運(yùn)算符和關(guān)系運(yùn)算符。文法表達(dá)式文法是二義性的，解決文法二義性的原則采用通常意義的優(yōu)先級(jí)和結(jié)合性。下面的翻譯模式把目標(biāo)代碼寫在了文法的屬性code中，所使用的函數(shù)、變量和屬性等與第9章的相同。 編譯原理與技術(shù)1110.3 語(yǔ)法制導(dǎo)的目標(biāo)代碼生成（1）S id : = Ep := lookup();if p = nil then error else S.code := E.cod

11、e | gencode( MOV, E.place, p)（2）E E1 + E2E.place := newtemp;E.code := E1.code | E2.code |gencode (MOV, E1.place, E.place) |gencode (ADD, E2.place, E.place)；（3）E E1 * E2E.place := newtemp;E.code := E1.code | E2.code |gencode (MOV, E1.place, E.place) |gencode (MUL, E2.place, E.place)； 編譯原理與技術(shù)1210.3 語(yǔ)法

12、制導(dǎo)的目標(biāo)代碼生成（4）E E1E.place := newtemp;E.code := E1.code | gencode (MOV, E1.place, E.place)；gencode (NEG, E.place)；（5）E (E1) E.place := E1.place;E.code := E1.code ;（6）E idp := lookup ();if p = nil then error else E.place := p; E.code := ;編譯原理與技術(shù)1310.3 語(yǔ)法制導(dǎo)的目標(biāo)代碼生成在下面布爾表達(dá)式的翻譯中，我們對(duì)布爾表達(dá)式的求值翻譯采用了短路法。其

13、中J| relop.op表示各種條件的轉(zhuǎn)移指令（表10.2）。（7）B B1 and B2B1.true := newlabel;B1.false := B.false;B2.true := B.true;B2.false := B.false;B.code := B1.code | gencode (B1.true, :) | B2.code（8）B B1 or B2B1.true := B.true;B1.false := newlabel;B2.true := B.true;B2.false := B.false;B.code := B1.code | gencode (B1.false

14、, :) | B2.code（9）B B1B1.true := B.false;B2.false := B.true;B.code := B1.code 編譯原理與技術(shù)1410.3 語(yǔ)法制導(dǎo)的目標(biāo)代碼生成（10）B (B1) B1.true := B.true;B2.false := B.false;B.code := B1.code ;（11）B id1 relop id2 t := newtemp;B.code := gencode (MOV, id1.place, t) |gencode (CMP, t, id2.place) |gencode (CJ| relop.op, B.true

15、) |gencode (J, B.false) （12）B truegencode (J, B.true)（13）B falsegencode (J, B. false)編譯原理與技術(shù)1510.3 語(yǔ)法制導(dǎo)的目標(biāo)代碼生成例10.1 把布爾表達(dá)式ad翻譯成目標(biāo)代碼。按照上述翻譯模式得到的機(jī)器指令如下：MOV a,t1CMPt2,bCJB.trueJB.false其中B.true和B.false需要應(yīng)用這個(gè)布爾條件的語(yǔ)句確定。編譯原理與技術(shù)1610.3 語(yǔ)法制導(dǎo)的目標(biāo)代碼生成本節(jié)介紹的翻譯技術(shù)可以應(yīng)用在簡(jiǎn)單語(yǔ)言的編譯器中，不適合許多大型實(shí)際的程序設(shè)計(jì)語(yǔ)言。主要原因包括：（1）從語(yǔ)義分析直接生成目標(biāo)

16、代碼有許多局限性，例如，由于目標(biāo)代碼于機(jī)器特性緊密相關(guān)，不利于代碼的移植和優(yōu)化，更好的策略是先產(chǎn)生某種直接代碼，然后再翻譯成目標(biāo)指令序列；（2）在上面的翻譯模式中，多處用到了產(chǎn)生臨時(shí)變量的函數(shù)newtemp，沒有充分考慮目標(biāo)機(jī)器體系結(jié)構(gòu)中的寄存器以及變量值的使用關(guān)系，而且過多的臨時(shí)變量名還會(huì)造成存儲(chǔ)分配與寄存器分配的問題。編譯原理與技術(shù)1710.4 基本塊和待用信息基本塊及其構(gòu)造 對(duì)于給定的程序，我們通常把它劃分為一系列的基本塊，根據(jù)程序的控制流把這些基本塊連接起來，形成程序流圖。在逐步完成各個(gè)基本塊的代碼生成之后，就生成了整個(gè)程序的目標(biāo)代碼?；緣K是指程序中一順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)

17、入口語(yǔ)句和一個(gè)出口語(yǔ)句?；緣K運(yùn)行時(shí)只能從其入口語(yǔ)句進(jìn)入，從出口語(yǔ)句退出。例如，下面的三地址代碼組成了一個(gè)基本塊：t 1 := a * at2 := a * bt3 := a * t2t4 := t1 * t3t5 := t4 + t2編譯原理與技術(shù)1810.4 基本塊和待用信息算法10.1 劃分基本塊輸入： 三地址語(yǔ)句序列輸出： 基本塊列表，每個(gè)三地址語(yǔ)句僅在基本塊中。（1）找出三地址代碼中各個(gè)基本塊的入口語(yǔ)句，它們是：程序的第一個(gè)語(yǔ)句，或者條件語(yǔ)句活無條件語(yǔ)句的轉(zhuǎn)移目標(biāo)語(yǔ)句，或者緊跟在條件語(yǔ)句之后的語(yǔ)句。（2）對(duì)每一個(gè)入口語(yǔ)句，它所在的基本塊就是由它開始到下一個(gè)入口語(yǔ)句之前、或者到一轉(zhuǎn)移語(yǔ)

18、句之前、或到程序結(jié)束的所有語(yǔ)句。凡是未被納入某一基本塊的語(yǔ)句，都是程序控制流無法到達(dá)的語(yǔ)句，因而也是不會(huì)被執(zhí)行的語(yǔ)句，可以把它們刪除。編譯原理與技術(shù)1910.4 基本塊和待用信息例 10.2：考慮下面計(jì)算長(zhǎng)度為20的兩個(gè)向量的點(diǎn)積的程序段，如圖10.2。begin prod := 0; index := ; do begin prod := prod + aindex*bindex; index := index + 1; end while index = 10;end 圖10.2 計(jì)算點(diǎn)積的程序在虛擬機(jī)器上執(zhí)行這個(gè)計(jì)算的三地址代碼序列如圖10.3。(1)prod := 0(2)index

19、:= 1t1 := 4*index /* 字長(zhǎng)是4個(gè)字節(jié) */(4)t2 := a t1 /* 計(jì)算aindex */(5)t3 := 4*index(6)t4 := b t1 /* 計(jì)算bindex *(7)t5 := t3 * t4(8)t6 := prod + t5(9)prod := t6(10)t7 := index + 1(11)index := t7(12)if index = 20 goto (3)編譯原理與技術(shù)2010.4 基本塊和待用信息我們運(yùn)用算法10.1來決定圖10.3的基本塊。按照算法的規(guī)則語(yǔ)句（1）是入口語(yǔ)句，按照規(guī)則語(yǔ)句（3）是條件轉(zhuǎn)移的目標(biāo)語(yǔ)句，也是入口語(yǔ)句；按

20、照規(guī)則跟隨語(yǔ)句（12）的是入口語(yǔ)句。所以，語(yǔ)句(1)和(2)組成了一個(gè)基本塊，以語(yǔ)句(3)開始的程序的其它語(yǔ)句組成了第二個(gè)基本塊。在虛擬機(jī)器上執(zhí)行這個(gè)計(jì)算的三地址代碼序列如圖10.3。(1)prod := 0(2)index := 1t1 := 4*index /* 字長(zhǎng)是4個(gè)字節(jié) */(4)t2 := a t1 /* 計(jì)算aindex */(5)t3 := 4*index(6)t4 := b t1 /* 計(jì)算bindex *(7)t5 := t3 * t4(8)t6 := prod + t5(9)prod := t6(10)t7 := index + 1(11)index := t7(12)

21、if index = 20 goto (3)編譯原理與技術(shù)2110.4 基本塊和待用信息例 10.3 考慮下面求最大公因子的三地址代碼，求出所有基本塊。(1) read X(2) read Y(3) R := X mod Y(4) if R = 0 goto (8)(5) X := Y(6) Y := R(7) goto (3)(8) write Y按照定義，可以找到四條入口語(yǔ)句（1）、（3）、（5）和（8）。然后，構(gòu)造的四個(gè)基本塊如下：基本塊B1基本塊B2基本塊B3基本塊B4(1) read X(2) read Y(3) R := X mod Y(4) if R = 0 goto (8)(5

22、) X := Y(6) Y := R(7) goto (3)(8) write Y編譯原理與技術(shù)2210.4 基本塊和待用信息流圖把程序控制流的信息增加到基本塊的集合，形成一個(gè)有向圖來表示程序，這樣的有向圖叫做流圖。每個(gè)流圖以基本塊為結(jié)點(diǎn)，其中包含了程序第一條語(yǔ)句的基本塊稱為起始結(jié)點(diǎn)。如果在程序的某個(gè)執(zhí)行序列中，基本塊Bj緊跟在基本塊Bi之后執(zhí)行，則從Bi到Bj有一條有向邊。也就是，若：有一個(gè)條件或無條件轉(zhuǎn)移語(yǔ)句作為Bi的最后一條語(yǔ)句轉(zhuǎn)移到Bj的第一條語(yǔ)句，或者按照程序的正文序列，Bj緊跟在Bi之后，而且Bi的最后一條語(yǔ)句不是一個(gè)無條件轉(zhuǎn)移語(yǔ)句。那么，塊Bi到Bj有一條有向邊。我們稱Bi是Bj

23、的前驅(qū)，Bj是Bi的后繼。編譯原理與技術(shù)2310.4 基本塊和待用信息例10.4 對(duì)例10.2中的程序構(gòu)造的流圖如圖10.4所示。B1是初始結(jié)點(diǎn)，在B2中的最后一個(gè)跳轉(zhuǎn)語(yǔ)句改成了跳轉(zhuǎn)到B1。prod := 0index := 1B1B2t1 := 4*indext2 := a t1t3 := 4*indext4 := b t1t5 := t3 * t4t6 := prod + t5prod := t6t7 := index + 1index := t7if index = 20 goto B1編譯原理與技術(shù)2410.4 基本塊和待用信息例10.5：對(duì)例10.3中的程序構(gòu)造的流圖如圖10.5所示

24、。(1) read X(2) read Y5）X := Y6）Y := R7）gogo (3)3) R := X mod Y(4) if R = 0 gogo (8)8）write XB1B2B3B4編譯原理與技術(shù)2510.4 基本塊和待用信息待用信息 如果三地址代碼i對(duì)變量A通過賦值語(yǔ)句定值（即存在一個(gè)賦值語(yǔ)句(i) A := E），中間代碼j要用A作為運(yùn)算對(duì)象（引用A的值），存在一個(gè)控制可以從語(yǔ)句i到j(luò)的路徑，并且這條路徑中沒有對(duì)A的其它賦值，那么就稱中間代碼j引用了A在中間代碼i的定值，稱中間代碼j是中間代碼i中對(duì)變量A的待用信息或下次引用信息，同時(shí)稱A在語(yǔ)句i是活躍變量。編譯原理與技術(shù)

25、2610.4 基本塊和待用信息我們?yōu)橐粋€(gè)基本塊內(nèi)的每個(gè)三地址語(yǔ)句x := a op b中的所有變量確定待用信息。 為了得到一個(gè)基本塊內(nèi)每個(gè)變量的待用信息和活躍信息，可以從基本塊的出口由后向前逐句掃描每條語(yǔ)句對(duì)每個(gè)變量建立相應(yīng)的待用信息鏈和活躍變量信息鏈。為了簡(jiǎn)化處理，我們對(duì)于基本塊內(nèi)的變量分為下列兩中情況處理：對(duì)沒有經(jīng)過數(shù)據(jù)流分析（見11.5的介紹）且三地址代碼生成的臨時(shí)變量不允許在基本塊外使用，那么就認(rèn)為這些臨時(shí)變量在基本塊出口處都是不活躍的；如果某些臨時(shí)變量可以在本基本塊之外引用，則把它們看作基本塊之后的活躍變量，同時(shí)也把基本塊的非臨時(shí)變量均看作是基本塊之后的活躍變量。編譯原理與技術(shù)271

26、0.4 基本塊和待用信息算法10.2 計(jì)算待用信息輸入： 基本塊的三地址語(yǔ)句序列輸出： 基本塊中所有變量的待用信息和活躍信息初始化：把基本塊中每個(gè)變量在符號(hào)表登記項(xiàng)中的待用信息填為“非待用”；根據(jù)每個(gè)變量在出口之后是否活躍，在活躍信息欄填上“活躍”或“非活躍”。從基本塊出口語(yǔ)句到入口語(yǔ)句由后向前依次處理每個(gè)中間代碼。對(duì)每個(gè)形式為i: A := B op C的代碼，以此執(zhí)行下列步驟：把符號(hào)表中變量A的待用信息和活躍信息附加到中間代碼i上；把符號(hào)表中變量A的待用信息欄和活躍信息欄分別設(shè)置為“非待用”和“非活躍”；（因?yàn)樵趇中對(duì)A的定值只能在i之后才能引用，對(duì)i之前的語(yǔ)句而言A既不是活躍的也不可待用

27、）把符號(hào)表中變量B和C的待用信息和活躍信息附加到中間代碼i上；把符號(hào)表中變量B和C的待用信息設(shè)置為i，活躍信息均設(shè)置為“活躍”。編譯原理與技術(shù)2810.4 基本塊和待用信息例10.6 對(duì)于下列基本塊，假設(shè)變量D在基本塊之后活躍，計(jì)算所有變量的待用信息。(1) T := A B(2) U := A C(3) V := TU(4) D := VU用F表示“非待用”和“非活躍”，用L表示“活躍”，用序號(hào)表示待用信息（即下一個(gè)引用點(diǎn)），用二元對(duì)表示變量的待用信息和活躍信息，其中X取指為F或L，表10.3顯示了符號(hào)表中待用信息和活躍信息，表10.4顯示了中間代碼上的待用信息和活躍信息。對(duì)表10.3中的每

28、一個(gè)變量，把其二元對(duì)從左到右連接起來，就得到了變量的待用信息和活躍信息變化。編譯原理與技術(shù)2910.4 基本塊和待用信息表10.3 例10.4的符號(hào)表中待用和活躍信息變量名待用信息和活躍信息 初值處理（4）處理（3）處理（2）處理（1）ABCDTUV編譯原理與技術(shù)3010.4 基本塊和待用信息表10.4 例10.4的中間代碼的待用和活躍信息序號(hào)中間代碼左值左操作數(shù)右操作數(shù)(1)T := A B(2)U := A C(3)V := TU(4)D := VU編譯原理與技術(shù)3110.5 一個(gè)簡(jiǎn)單代碼生成器 本節(jié)要介紹一個(gè)簡(jiǎn)單的代碼生成器，它依次考慮每條語(yǔ)句以及如何在一個(gè)基本塊范圍內(nèi)充分利用寄存器的問

29、題，生成目標(biāo)代碼，并根據(jù)產(chǎn)生的代碼修改寄存器的使用情況。為了簡(jiǎn)單起見，假定計(jì)算結(jié)果盡量常時(shí)間地留在寄存器中，只有在下面兩種情況下才把它存入內(nèi)存：（1）如果需要此寄存器用于其它計(jì)算；（2）正好在轉(zhuǎn)移或標(biāo)號(hào)語(yǔ)句之前。條件（2）暗示在基本塊的結(jié)尾必須把所有的計(jì)算結(jié)果都保存起來。原因是，離開一個(gè)基本塊后，可能進(jìn)入幾個(gè)不同基本塊中的一個(gè)，或者進(jìn)入一個(gè)還可以從其它基本塊進(jìn)入的基本塊。在這兩種情況下，就認(rèn)為基本塊引用的某個(gè)數(shù)據(jù)在入口點(diǎn)一定處在某個(gè)寄存器中是不妥的。因此，為了不免可能出先的錯(cuò)誤，本節(jié)介紹的簡(jiǎn)單代碼生成算法在離開基本塊時(shí)，存儲(chǔ)所有的東西。編譯原理與技術(shù)3210.5 一個(gè)簡(jiǎn)單代碼生成器通過一個(gè)簡(jiǎn)單

30、的例子來說明要介紹的簡(jiǎn)單代碼生成算法的一些問題。對(duì)三地址語(yǔ)句 a:= b + c，我們可以生成一條簡(jiǎn)單的指令A(yù)DD Rj, Ri（1）把結(jié)果留在Ri。但是，可以生成這條簡(jiǎn)單指令的前提是：Rj包含了c，Ri 包含了b，而且它以后不再被引用了。如果Ri 包含了b，而c在內(nèi)存中（假設(shè)就用c表示內(nèi)存單元），我們可以產(chǎn)生：ADDc,Ri（2）或者M(jìn)OVc, Rj（3）ADDRj,Ri同樣要求b不再被引用了。從機(jī)器指令執(zhí)行的時(shí)間上講，使用寄存器比使用內(nèi)存單元要快。但是，任何機(jī)器的寄存器數(shù)量?jī)?yōu)先，而且某些寄存器還有特殊通途，不能作為通用寄存器使用。而且，還要考慮到存入寄存器額名字的值今后是否還要引用。所以，

31、判定翻譯模板代碼優(yōu)劣的因素很多、很復(fù)雜。但從本例而言，代碼（1）的執(zhí)行速度最快，但是，要求的條件也最多。代碼（2）的執(zhí)行速度由于要訪問內(nèi)存（c的值），比代碼（1）慢，但是比（3）要快，而且，代碼（1）和（2）都是一條指令，占用較少的內(nèi)存。然而，如果以后肯定要使用c的值，翻譯（3）比（2）更有吸引力，因?yàn)閏的值已經(jīng)在一個(gè)寄存器Rj中。 編譯原理與技術(shù)3310.5 一個(gè)簡(jiǎn)單代碼生成器寄存器和地址的描述 為了在代碼生成的過程中合理地分配寄存器，需要隨時(shí)掌握每個(gè)寄存器的使用情況，了解它是否空閑，還是已經(jīng)分配給某個(gè)或某幾個(gè)變量。使用一個(gè)數(shù)組RVALUE來動(dòng)態(tài)地記錄寄存器的這些信息，這個(gè)數(shù)組稱作寄存器描述

32、數(shù)組。用寄存器Ri的編號(hào)值作為寄存器描述數(shù)組的RVALUE下標(biāo)，數(shù)組元素值是一個(gè)或多個(gè)變量名。另外，一個(gè)變量的值可以存儲(chǔ)在寄存器中，也可以存放在內(nèi)存，或者同時(shí)存放在寄存器和內(nèi)存中。在代碼生成過程中，每當(dāng)生成的指令要涉及到引用某個(gè)變量的值時(shí)，若它已經(jīng)在某個(gè)寄存器，我們希望直接引用該變量在寄存器中的值，以便提高代代碼的執(zhí)行速度。使用一個(gè)稱作變量地址描述數(shù)AVALUE來動(dòng)態(tài)地記錄每個(gè)變量當(dāng)前值的存放位置，這個(gè)數(shù)組的下標(biāo)就用變量名。 編譯原理與技術(shù)3410.5 一個(gè)簡(jiǎn)單代碼生成器寄存器和地址的描述幾個(gè)例子：RVALUER1 = A, B 表示R1存儲(chǔ)的是變量A和B的值A(chǔ)VALUEA =A表示變量A的值

33、只存放在內(nèi)存中AVALUEA = R1, A表示變量A的值同時(shí)存放在寄存器R1和內(nèi)存中AVALUEB = R1表示變量B的值只存放在寄存器R1內(nèi)編譯原理與技術(shù)3510.5 一個(gè)簡(jiǎn)單代碼生成器寄存器的分配原則 當(dāng)生成某變量的目標(biāo)代碼時(shí)，盡可能讓變量的值或計(jì)算結(jié)果駐留在寄存器中，除非該寄存器必須用來存放其它變量的值而不得不放棄其中的內(nèi)容；達(dá)到基本塊出口時(shí)，將變量的值存放到內(nèi)存中，以便后續(xù)基本塊的代碼可以繼續(xù)引用其值；一個(gè)基本塊后不再引用的變量所占用的寄存器應(yīng)該盡早釋放出來，以提高寄存器的使用率。為了在一個(gè)基本塊內(nèi)的目標(biāo)代碼中讓寄存器得到充分利用，需要把基本塊內(nèi)還要被引用的變量值盡可能地保存在寄存器

34、中，而把基本塊內(nèi)不再被引用的變量所占的寄存器盡早地釋放掉。在代碼生成的過程中，需要不斷地為程序中的變量選擇寄存器。 編譯原理與技術(shù)3610.5 一個(gè)簡(jiǎn)單代碼生成器算法10.3 寄存器選擇函數(shù)GETREG輸入： 中間代碼i: A := B op C輸出： 一個(gè)用來存放變量A的值的寄存器Rfor 每個(gè)AVALUEB中的Ri doif (RVALUERi= =B)& (B= =A | B在該語(yǔ)句之后不會(huì)在被引用) then return Ri;/ 即語(yǔ)句i的附加信息中，B的待用和活躍信息為“非待用”和“非活躍”if (存在Ri & RVALUERi = = ) then return Ri;按照下列

35、原則，從已經(jīng)分配的寄存器中選擇一個(gè)寄存器Ri：占用寄存器Ri的變量，或者其值同時(shí)也存儲(chǔ)在內(nèi)存，或者它在基本塊的最遠(yuǎn)處引用或不被引用。for 每個(gè)RVALUEB中的M do if (M != A | (M= =A & M= =C &(M!= B & B不屬于RVALUERi) then if (M不屬于AVALUEM) then 生成目標(biāo)代碼MOV Ri, M; / 把Ri的值存入內(nèi)存MAVALUEM = AVALUEM Ri if (M != B | ( M= =C & B屬于RVALUERi) then AVALUEM = M, B else AVALUEM = M RVALUE Ri =

36、RVALUE Ri Mreturn Ri編譯原理與技術(shù)3710.5 一個(gè)簡(jiǎn)單代碼生成器代碼生成算法 本節(jié)介紹一個(gè)簡(jiǎn)單代碼生成算法。不失一般性，假設(shè)中間代碼的形式為A := B op C，對(duì)于其它形式的中間代碼，可以仿照算法10.4完成。這個(gè)算法調(diào)用了算法10.3和10.2，需要待用信息的目的就是決定是否釋放這寫變量所占用的寄存器。 編譯原理與技術(shù)3810.5 一個(gè)簡(jiǎn)單代碼生成器算法10.4 簡(jiǎn)單代碼生成算法輸入： 基本塊BBn，每條中間代碼形式為i: A := B op C輸出： 目標(biāo)代碼for (j=1; j n; j+) / 調(diào)用寄存器選擇函數(shù)GETREG(i: A := B op C)得

37、到一個(gè)存放A值的寄存器R； R = getreg (BBj); B = AVALUEB; C = AVALUEC; / 到B和C的存放位置B和C if (B= =R) 生成目標(biāo)代碼op R, C else生成目標(biāo)代碼 MOV B, R op R, C /* 修改寄存器描述數(shù)組和地址描述數(shù)組，釋放B和C所占用的寄存器，使A只在寄存器R且獨(dú)占寄存器R */ if (B= =R) AVALUEB = AVALUEB R； if (C= =R) AVALUEC = AVALUEC R； AVALUEA = R; RVALUER = A; /* 若B或C不再被引用，就釋放B或C占用的每一個(gè)寄存器*/ If (B不再被引用) RVALUERi = RVALUERi B; AVALUEB = AVALUEB Ri If (C不再被引用) RVALUERi = RVALUERi C; AVALUEC = AVALUEC Ri 編譯原理與技術(shù)3910.5 一個(gè)簡(jiǎn)單代碼生成器例10.7 對(duì)于例10.6的三地址代碼：(1) T := A B(2) U := A C(3) V := TU(4) D := VU中間代碼目標(biāo)代碼RVALUEAVALUET := A BMOV A, R0SUB B, R0R0含TT在R0U := A CMOV