第9章 目標(biāo)代碼生成

1、 第九章 目標(biāo)代碼生成(1)生成目標(biāo)代碼的形式(2)簡單代碼生成器的 設(shè)計(jì)和構(gòu)造方法(1)生成目標(biāo)代碼的形式 目標(biāo)代碼分為兩類：機(jī)器語言代碼和匯編語言代碼，匯編語言代碼經(jīng)過匯編程序轉(zhuǎn)換成機(jī)器語言代碼。 機(jī)器語言代碼又可分為兩種：其一是能夠立即執(zhí)行的機(jī)器語言代碼，通常存放在固定的存儲區(qū)中。 其二是待裝配的機(jī)器語言模塊，當(dāng)需要執(zhí)行時由連接裝配程序把它們與庫函數(shù), 如C.lib、C.math等組合成可執(zhí)行的機(jī)器語言代碼。動態(tài)連接庫程序API（如Kernel32.dll）例外. 目標(biāo)代碼生成部分緊密地依賴于目標(biāo)機(jī)的指令系統(tǒng)，指令系統(tǒng)越豐富越容易生成目標(biāo)代碼。目標(biāo)機(jī)中一般有多個寄存器，包括累加器、計(jì)數(shù)器

2、、變址器等，寄存器 的分配問題是目標(biāo)代碼生成階段必須解決的重要問題。 目標(biāo)機(jī)目標(biāo)機(jī) 我們不考慮任何具體計(jì)算機(jī)，而是構(gòu)造一個有代表性的目標(biāo)機(jī)，引進(jìn)個別特殊指令，它們可能對應(yīng)80X86等匯編語言中的多條指令，如關(guān)系運(yùn)算指令。例如，有關(guān)系式XY，其目標(biāo)代碼結(jié)構(gòu)為： mov R，X ；把X讀入寄存器R中 LT R，Y ；與Y比較大小，結(jié)果在R中，True或False 這樣做的目的是為了統(tǒng)一關(guān)系運(yùn)算和邏輯運(yùn)算的處理。若用AND和OR分別表示按位邏輯乘和按位邏輯加，則邏輯式A AND B的目標(biāo)代碼如下： mov R，A AND R，B其執(zhí)行結(jié)果是在寄存器R中得到全0或全1的機(jī)器字，對于A OR B也有類似

3、的目標(biāo)代碼。 另外，目標(biāo)機(jī)有一特殊寄存器，它除了可做為一般的寄存器外，還具有這樣的特性，即當(dāng) JMP指令進(jìn)行轉(zhuǎn)移時同時把下一條指令的地址記入中。 目標(biāo)機(jī)指令的一般結(jié)構(gòu)為： R，A或 R，*A 其中：是操作碼，R是寄存器，A是地址部分，*A表示間接運(yùn)算，若用addr(A)表示形式地址A的操作地址，則其具體定義為： addr(M)=M ；M是內(nèi)存地址 addr(R)=R addr(R，L，X)=(R)+L)+X ； ; (d)表示地址d的內(nèi)容; 80 x86中使用 第三種形式可以分別采用變址尋址或相對變址尋址的目標(biāo)指令： mov R1，LR ；若X=0 mov R1，XR+L ；若X0例如，X的相

4、對地址為 i，則： addr(X)=(sp)+i下面是本章目標(biāo)代碼生成時用到的指令系統(tǒng)：種類 R，A或 R，*A 含義存 mov A，R (R)addrA取 mov R，A (addrA)R -實(shí) ADD R，A 數(shù) SUB R，A (R) (A)R運(yùn) MUL R，A算 DIV R，A-整數(shù) IADD R，A ISUB R，A (R) (A)R運(yùn)算 IMUL R，A- LT R，A關(guān) LE R，A (R) (A)成立系 EQ R，A 則trueR，否則falseR運(yùn) NE R，A算 GT R，A GE R，A-邏輯 AND R，A運(yùn)算 OR R，A (R) (A) R-轉(zhuǎn)向 TJMP R，A

5、(R)=ture則轉(zhuǎn)addrA FJMP R，A (R)=false則轉(zhuǎn)addrA操作 JMP -，A 無條件轉(zhuǎn)向addrA-轉(zhuǎn)實(shí) CONV R，A real(addrA)R-讀出地址 LDA R，A addrAR其中，轉(zhuǎn)向指令把下一條指令的地址送入特殊寄存器中。(2)簡單代碼生成器的設(shè)計(jì)和構(gòu)造方法待用信息與活躍信息待用信息與活躍信息 在一個基本塊內(nèi)的目標(biāo)代碼中，為了提高寄存器的使用效率，應(yīng)該把基本塊內(nèi)還要被引用的值盡可能地保留在寄存器中，而把基本塊內(nèi)不再被引用的變量所占用的寄存器盡早釋放。 當(dāng)由四元式生成相應(yīng)指令時，每翻譯一條四元式，如A=B op C時，需要知道在基本塊中還有哪些四元式要對

6、變量A、B、C進(jìn)行引用。為此需要收集一些待用信息。在一個基本塊中，四元式i對變量A定值定值，如果在i后面的四元式j(luò)要引用引用A，而從i到j(luò)中的四元式?jīng)]有其它對A的定值點(diǎn)，則稱j是四元式i中對變量A的待用信息，同時也稱A是活躍的。若A被多處引用可構(gòu)成待用信息鏈與活躍信息鏈。 A的活躍區(qū)間的活躍區(qū)間i, j。 為了取得每個變量在基本塊內(nèi)的待用信息與活躍信息，可從基本塊的出口由后向前掃從基本塊的出口由后向前掃描，對每個變量建立相應(yīng)的待用信息鏈與活描，對每個變量建立相應(yīng)的待用信息鏈與活躍信息鏈。躍信息鏈。如果沒有進(jìn)行數(shù)據(jù)流分析并且臨時變量不允許跨基本塊引用，則把基本塊中的臨時變量均看做基本塊出口之后的

7、非活躍變量。如果某些臨時變量能夠跨基本塊使用，則把這些臨時變量也看成基本塊出口之后的活躍變量。 計(jì)算變量待用信息的方法，P172代碼生成算法代碼生成算法 為了在代碼生成中進(jìn)行寄存器分配，需要隨時掌握各寄存器的使用情況，看它是處于空閑狀態(tài)還是已分配給某個變量或已分配給某幾個變量。 通常用一個寄存器描述數(shù)組Rvalue動態(tài)地記錄各寄存器的當(dāng)前狀況；建立一個變量地址描述數(shù)組Avalue來記錄各變量現(xiàn)行值存放的位置，看它是在某寄存器還是在某存儲單元中，或者既在寄存器中也在存儲器中。RvalueRi=A 分配給某變量ARvalueRi=A, B 分配給變量A，BRvalueRi= 未分配AvalueA=

8、A 表示A的值在內(nèi)存中AvalueA= Ri 表示A的值在寄存器Ri中AvalueA= Ri, A 表示A的值既在Ri中又在A中一個代碼生成的算法：一個代碼生成的算法： 考慮四元式（op，B，C，A） 算法對每條四元式 i: （op，B，C，A）依次執(zhí)行如下操作：(1)調(diào)用函數(shù)GetReg(i: (op, B, C, A)，返回存放A值結(jié)果的寄存器R； (2)通過AvalueB和AvalueC確定出變量B和變量C的現(xiàn)行值的存放位置B和C。如果是存放在寄存器中則把寄存器取作B和C (3)如果BR，則生成目標(biāo)代碼： mov R， B op R，C 否則生成目標(biāo)代碼： op R，C 如果B或C為R，

9、則刪除AvalueB和AvalueC中的R(4)令A(yù)valueA=R，并令RvalueR=A，以表示變量A的現(xiàn)行值只在R中，并且R中的值只代表A的現(xiàn)行值。(5)如果B和C的現(xiàn)行值在基本塊中不再被引用，它們也不是基本塊出口之后的活躍變量，并且它們的現(xiàn)行值存放在寄存器Rk中，則刪除RValueRk中的B和C以及AvalueB中的Rk。GetReg是一個函數(shù)，用來存放A的當(dāng)前值的寄存器R，算法如下（173）： (1)如果B的現(xiàn)行值在Ri中，且Ri只包含B的值，或者B和A是同一標(biāo)識符，或B在該四元式之后不再引用，則選取Ri為所需寄存器，轉(zhuǎn)(4)(2)如有尚未分配的寄存器，則從中選取一個Ri為所需寄存器

10、R，轉(zhuǎn)(4)(3)從已分配的寄存器中選取一個Ri為所需的寄存器R，選取原則為：占用Ri的變量的值也同時存放在主存中(D=R and D=symbol)，或者在基本塊中要在最遠(yuǎn)的位置才會引用到。 這樣，對寄存器Ri所含的變量和變量在主存中的情況必須先做如下調(diào)整： 對RvalueRi中的每一個變量M，如果M不是A(A準(zhǔn)備存放運(yùn)算結(jié)果,不需要保存)且AvalueM=M(說明M的值不在寄存器中)，則生成目標(biāo)代碼 mov M, Ri;如果M是B，則令A(yù)valueM=M, Ri，否則令A(yù)valueM=M;刪除RvalueRi中的M；(4)給出R，返回。 對于其它形式的四元式也可以仿照以上算法生成目標(biāo)代碼。

11、寄存器的分配寄存器的分配 由于寄存器數(shù)量有限，為了生成更有效的目標(biāo)代碼，就必須考慮如何更有效地利用寄存器的問題。直觀地講，寄存器的分配可以看做在計(jì)算一個表達(dá)式時，如何分配寄存器使得計(jì)算耗時最少。 這樣，寄存器分配問題可以描述為：有n個可用寄存器R1,R2,Rn，采用何種方法使計(jì)算表達(dá)式時使用的存取指令最少。假如不允許排列子表達(dá)式，并且每個值都必須先取到某個寄存器后才能使用，那么在對一個表達(dá)式進(jìn)行計(jì)算時，表達(dá)式中的某個變量A的值可能會處于以下3種狀態(tài)： (1)變量A已經(jīng)在寄存器Ri中，此時可直接從寄存器中讀取。(2)變量A在某存儲單元中，但是有可用寄存器。這種情況可以把該變量的值從存儲單元調(diào)入可用寄存器再進(jìn)行計(jì)算。(3) 變量A在某存儲單元中，并且沒有可用寄存器。 前兩種情況沒有寄存器使用沖突，可以直接使用寄存器。對于