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

1、編譯原理與技術(shù)第10章 目標(biāo)代碼生成 青島大學(xué)信息工程學(xué)院主要內(nèi)容代碼生成器設(shè)計(jì)的基本問題 虛擬計(jì)算機(jī)模型 語法制導(dǎo)的目標(biāo)代碼生成 基本塊和待用信息 一個簡單代碼生成器代碼生成技術(shù)小結(jié) 編譯原理與技術(shù)210.1 代碼生成器設(shè)計(jì)的基本問題 代碼生成在整個編譯過程的位置符號表代碼生成中間代碼生成與優(yōu)化語法樹目標(biāo)程序中間代碼中間代碼語義分析中間代碼編譯原理與技術(shù)310.1 代碼生成器設(shè)計(jì)的基本問題目標(biāo)程序 絕對機(jī)器代碼，程序所有的內(nèi)存地址，特別是程序的起始地址，在編譯時都已經(jīng)固定。這種代碼的優(yōu)點(diǎn)是裝入機(jī)器后就可以立即執(zhí)行，對于小程序可以快速編譯和運(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)模塊庫中調(diào)用其它已經(jīng)編譯好的模塊，便于程序開發(fā)。通常，可重定位機(jī)器代碼中包含可重定位信息和連接信息。如果目標(biāo)代碼是匯編語言程序，還需要匯編后才能運(yùn)行。只要地址可以由偏移址及符號表中的其它信息計(jì)算得到，代碼生成器就可以產(chǎn)生程序中名字的絕對地址或可重定位地址。這樣生成代碼的好處是不用生成二進(jìn)制的機(jī)器代碼，而是產(chǎn)生符號指令并用宏機(jī)制來幫助產(chǎn)生機(jī)器代碼，使得代碼生成過程變得容易。為了可讀性，

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

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

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

6、它們既可以作為累加器，也可以作為變址器。假設(shè)目標(biāo)機(jī)器按字節(jié)編址，4個字接組成一個字。我們用op表示運(yùn)算符，用字母M表示內(nèi)存單元，用字母C表示常量，用星號*表示間址方式存取。這臺機(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ù)號NEG、乘法MUL、除法DIV、加1 INC、減1 DEC以及邏輯運(yùn)算AND、NOT、OR等等。 編譯原理與技術(shù)910.2 虛擬計(jì)算機(jī)模型當(dāng)用作源或目的時，內(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時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 語法制導(dǎo)的目標(biāo)代碼生成 利用屬性文法和語法制導(dǎo)技術(shù)，直接產(chǎn)生目標(biāo)代碼?；驹砗图夹g(shù)同第9章介紹的語法制導(dǎo)的中間代碼翻譯類似，只是產(chǎn)生的目標(biāo)語言是機(jī)器指令。本節(jié)只討論如何用翻譯模式把源程序語言的簡單賦值語句和表達(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為了簡單起見，這個算術(shù)表達(dá)式E只有加法、乘法與取負(fù)運(yùn)算，不包含數(shù)組、記錄等復(fù)雜的結(jié)構(gòu)的訪問，布爾表達(dá)式B只包括了三個邏輯運(yùn)算符和關(guān)系運(yùn)算符。文法表達(dá)式文法是二義性的，解決文法二義性的原則采用通常意義的優(yōu)先級和結(jié)合性。下面的翻譯模式把目標(biāo)代碼寫在了文法的屬性code中，所使用的函數(shù)、變量和屬性等與第9章的相同。 編譯原理與技術(shù)1110.3 語法制導(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 語法

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

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

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

18、句之前、或到程序結(jié)束的所有語句。凡是未被納入某一基本塊的語句，都是程序控制流無法到達(dá)的語句，因而也是不會被執(zhí)行的語句，可以把它們刪除。編譯原理與技術(shù)1910.4 基本塊和待用信息例 10.2：考慮下面計(jì)算長度為20的兩個向量的點(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í)行這個計(jì)算的三地址代碼序列如圖10.3。(1)prod := 0(2)index

19、:= 1t1 := 4*index /* 字長是4個字節(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ī)則語句（1）是入口語句，按照規(guī)則語句（3）是條件轉(zhuǎn)移的目標(biāo)語句，也是入口語句；按

20、照規(guī)則跟隨語句（12）的是入口語句。所以，語句(1)和(2)組成了一個基本塊，以語句(3)開始的程序的其它語句組成了第二個基本塊。在虛擬機(jī)器上執(zhí)行這個計(jì)算的三地址代碼序列如圖10.3。(1)prod := 0(2)index := 1t1 := 4*index /* 字長是4個字節(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按照定義，可以找到四條入口語句（1）、（3）、（5）和（8）。然后，構(gòu)造的四個基本塊如下：基本塊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 基本塊和待用信息流圖把程序控制流的信息增加到基本塊的集合，形成一個有向圖來表示程序，這樣的有向圖叫做流圖。每個流圖以基本塊為結(jié)點(diǎn)，其中包含了程序第一條語句的基本塊稱為起始結(jié)點(diǎn)。如果在程序的某個執(zhí)行序列中，基本塊Bj緊跟在基本塊Bi之后執(zhí)行，則從Bi到Bj有一條有向邊。也就是，若：有一個條件或無條件轉(zhuǎn)移語句作為Bi的最后一條語句轉(zhuǎn)移到Bj的第一條語句，或者按照程序的正文序列，Bj緊跟在Bi之后，而且Bi的最后一條語句不是一個無條件轉(zhuǎn)移語句。那么，塊Bi到Bj有一條有向邊。我們稱Bi是Bj

23、的前驅(qū)，Bj是Bi的后繼。編譯原理與技術(shù)2310.4 基本塊和待用信息例10.4 對例10.2中的程序構(gòu)造的流圖如圖10.4所示。B1是初始結(jié)點(diǎn)，在B2中的最后一個跳轉(zhuǎn)語句改成了跳轉(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：對例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對變量A通過賦值語句定值（即存在一個賦值語句(i) A := E），中間代碼j要用A作為運(yùn)算對象（引用A的值），存在一個控制可以從語句i到j(luò)的路徑，并且這條路徑中沒有對A的其它賦值，那么就稱中間代碼j引用了A在中間代碼i的定值，稱中間代碼j是中間代碼i中對變量A的待用信息或下次引用信息，同時稱A在語句i是活躍變量。編譯原理與技術(shù)

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

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

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

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

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

30、的例子來說明要介紹的簡單代碼生成算法的一些問題。對三地址語句 a:= b + c，我們可以生成一條簡單的指令A(yù)DD Rj, Ri（1）把結(jié)果留在Ri。但是，可以生成這條簡單指令的前提是：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í)行的時間上講，使用寄存器比使用內(nèi)存單元要快。但是，任何機(jī)器的寄存器數(shù)量優(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)在一個寄存器Rj中。 編譯原理與技術(shù)3310.5 一個簡單代碼生成器寄存器和地址的描述 為了在代碼生成的過程中合理地分配寄存器，需要隨時掌握每個寄存器的使用情況，了解它是否空閑，還是已經(jīng)分配給某個或某幾個變量。使用一個數(shù)組RVALUE來動態(tài)地記錄寄存器的這些信息，這個數(shù)組稱作寄存器描述

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

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

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

35、原則，從已經(jīng)分配的寄存器中選擇一個寄存器Ri：占用寄存器Ri的變量，或者其值同時也存儲在內(nèi)存，或者它在基本塊的最遠(yuǎn)處引用或不被引用。for 每個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 一個簡單代碼生成器代碼生成算法 本節(jié)介紹一個簡單代碼生成算法。不失一般性，假設(shè)中間代碼的形式為A := B op C，對于其它形式的中間代碼，可以仿照算法10.4完成。這個算法調(diào)用了算法10.3和10.2，需要待用信息的目的就是決定是否釋放這寫變量所占用的寄存器。 編譯原理與技術(shù)3810.5 一個簡單代碼生成器算法10.4 簡單代碼生成算法輸入： 基本塊BBn，每條中間代碼形式為i: A := B op C輸出： 目標(biāo)代碼for (j=1; j n; j+) / 調(diào)用寄存器選擇函數(shù)GETREG(i: A := B op C)得

37、到一個存放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占用的每一個寄存器*/ If (B不再被引用) RVALUERi = RVALUERi B; AVALUEB = AVALUEB Ri If (C不再被引用) RVALUERi = RVALUERi C; AVALUEC = AVALUEC Ri 編譯原理與技術(shù)3910.5 一個簡單代碼生成器例10.7 對于例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