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

第七章目標(biāo)代碼生成2023/12/26第七章目標(biāo)代碼生成(2)待裝配的機器語言模塊，其地址均為相對地址，所以不能直接執(zhí)行。當(dāng)需要執(zhí)行時由連接裝配程序把它們與其它運行程序和庫函數(shù)連接起來，裝配成可執(zhí)行的機器語言代碼，如PC機中后綴為?.OBJ的文件都屬于待裝配的模塊(文件)。(3)匯編語言程序，必須通過匯編程序的匯編方可轉(zhuǎn)換成可執(zhí)行的機器語言代碼，如PC機中后綴為?.ASM的文件即為匯編語言程序。第七章目標(biāo)代碼生成一個高級語言程序的目標(biāo)代碼要經(jīng)常、反復(fù)使用，因此代碼生成要著重考慮兩個問題：一是如何使生成的目標(biāo)代碼較短，二是如何充分利用計算機的寄存器以減少目標(biāo)代碼中訪問存儲單元的次數(shù)。生成的目標(biāo)代碼越短，寄存器的利用越充分，目標(biāo)代碼的質(zhì)量也就越高。設(shè)計一個代碼生成器需要考慮具體的機器結(jié)構(gòu)、指令格式、字長及寄存器個數(shù)和種類，并且與指令的語義和所用的操作系統(tǒng)、存儲管理等都密切相關(guān)。第七章目標(biāo)代碼生成7.1一個簡單代碼生成器一個簡單的代碼生成器，此生成器依次把每條中間代碼變換成目標(biāo)代碼，并且在一個基本塊范圍內(nèi)考慮如何充分利用寄存器的問題。一方面，在基本塊中，當(dāng)生成計算某變量值的目標(biāo)代碼時，盡可能地讓該變量的值保留在寄存器中(即不編出把該變量的值存到內(nèi)存單元的指令)，直到該寄存器必須用來存放其它變量的值或已達基本塊出口為止；另一方面，后續(xù)的目標(biāo)代碼盡可能地引用變量在寄存器中的值而不訪問內(nèi)存。第七章目標(biāo)代碼生成如一C語言語句A=(B+C)*D+E，翻譯為四元式G： T1=B+C T2=T1*D A=T2+E如果不考慮代碼的效率，可以簡單地把每條中間代碼(四元式)映射成若干條目標(biāo)指令，如將x=y+z映射為 MOVAX,y/*AX為寄存器*/ ADDAX,z MOVx,AX其中，x、y、z均為數(shù)據(jù)區(qū)的內(nèi)存變量。第七章目標(biāo)代碼生成上述四元式代碼序列G可翻譯為(1)?MOVAX,B(2)?ADDAX,C(3)?MOVT1,AX(4)?MOVAX,T1

(5)?MULAX,D(6)?MOVT2,AX(7)?MOVAX,T2(8)?ADDAX,E(9)?MOVA,AX第七章目標(biāo)代碼生成從正確性來看，這種翻譯不存在問題，但卻存在冗余。指令序列中的(4)和(7)兩條指令是多余的；而T1、T2均是中間代碼生成時產(chǎn)生的臨時變量，它們在出了基本塊后將不再使用，故(3)、(6)兩條指令也可刪去。因此，在考慮了效率和充分使用寄存器之后，應(yīng)生成如下代碼：(1)?MOVAX,B(2)?ADDAX,C(3)?MULAX,D(4)?ADDAX,E(5)?MOVA,AX為了實現(xiàn)這一目的，代碼生成器就必須了解一些信息：在產(chǎn)生T2=T1*D對應(yīng)的目標(biāo)代碼時，為了省去指令MOVAX,T1，就必須知道T1的當(dāng)前值已在寄存器AX中；為了省去MOVT1,AX，就必須知道出了基本塊后T1不再被引用。第七章目標(biāo)代碼生成7.1.1待用信息與活躍信息在一個基本塊內(nèi)的目標(biāo)代碼中，為了提高寄存器的使用效率，應(yīng)將基本塊內(nèi)還要被引用的值盡可能地保留在寄存器中，而將基本塊內(nèi)不再被引用的變量所占用的寄存器盡早釋放。每當(dāng)翻譯一條四元式如A=BopC時，需要知道在基本塊中還有哪些四元式要對變量A、B、C進行引用，為此，需要收集一些待用信息。 在一個基本塊中，四元式i對變量A定值，如果i后面的四元式j(luò)要引用A且從i到j(luò)的四元式?jīng)]有其它對A的定值點，則稱j是四元式i中對變量A的待用信息，同時也稱A是活躍的。如果A被多處引用，則構(gòu)成了A的待用信息鏈與活躍信息鏈。第七章目標(biāo)代碼生成 為了取得每個變量在基本塊內(nèi)的待用信息和活躍信息，可從基本塊的出口由后向前掃描，對每個變量建立相應(yīng)的待用信息鏈與活躍信息鏈。 如果沒有進行數(shù)據(jù)流分析并且臨時變量不允許跨基本塊引用，則把基本塊中的臨時變量均看作基本塊出口之后的非活躍變量，而把所有的非臨時變量均看作基本塊出口之后的活躍變量。 如果某些臨時變量能夠跨基本塊使用，則把這些臨時變量也看成基本塊出口之后的活躍變量。第七章目標(biāo)代碼生成假設(shè)變量的符號表內(nèi)有待用信息和活躍信息欄，則計算變量待用信息的算法如下：(1)首先將基本塊中各變量的符號表的待用信息欄置為“非待用”，對活躍信息欄則根據(jù)該變量在基本塊出口之后是否活躍而將該欄中的信息置為“活躍”或“非活躍”。(2)從基本塊出口到基本塊入口由后向前依次處理各四元式。對每個四元式i：A=BopC依次執(zhí)行以下步驟：第七章目標(biāo)代碼生成①把符號表中變量A的待用信息和活躍信息附加到四元式i上；②把符號表中變量A的待用信息和活躍信息分別置為“非待用”和“非活躍”；③把符號表中變量B和C的待用信息和活躍信息附加到四元式i上；④把符號表中變量B和C的待用信息置為i，活躍信息置為“活躍”。注意：以上①～④次序不能顛倒，如果四元式出現(xiàn)A=opB或者A=B形式，則以上執(zhí)行步驟完全相同，只是其中不涉及變量C。第七章目標(biāo)代碼生成例7.1考察基本塊： (1)?T=A?B (2)?U=A?C (3)?V=T+U (4)?D=V+U其中，A、B、C、D為變量，T、U、V為中間變量。試求各變量的待用信息鏈和活躍信息鏈。[解答]我們根據(jù)計算變量待用信息的算法得到各變量的待用信息鏈和活躍信息鏈如表7.1所示。表中的“F”表示“非待用”或“非活躍”，“L”表示“活躍”，(1)～(4)分別表示基本塊中的四個四元式。待用信息鏈和活躍信息鏈的每列從左到右為每行從后向前掃描一個四元式時相應(yīng)變量的信息變化情況(空白處表示沒有變化)。第七章目標(biāo)代碼生成第七章目標(biāo)代碼生成待用信息和活躍信息在四元式上的標(biāo)記如下(每個變量都先去掉待用信息鏈和活躍信息鏈最右的值，然后由右向左依次引用所出現(xiàn)的值)：(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第七章目標(biāo)代碼生成7.1.2代碼生成算法為了在代碼生成中進行寄存器分配，需要隨時掌握各寄存器的使用情況，即它是處于空閑狀態(tài)還是已分配給某個變量或已分配給某幾個變量。通常用一個寄存器描述數(shù)組RVALUE動態(tài)地記錄各寄存器的當(dāng)前狀況，并用寄存器Ri的編號作為它的下標(biāo)。此外，還需建立一個變量地址描述數(shù)組AVALUE來記錄各變量現(xiàn)行值存放的位置，即其是在某寄存器中還是在某內(nèi)存單元中，或者同時存在于某寄存器和某內(nèi)存單元中，可以有如下表示：RVALUE[Ri]={A} /*寄存器Ri分配給變量A*/RVALUE[Ri]={A,B} /*寄存器Ri分配給變量A和B*/RVALUE[Ri]={} /*未分配*/AVALUE[A]={A} /*表示A的值在內(nèi)存中*/AVALUE[A]={Ri} /*表示A的值在寄存器Ri中*/AVALUE[A]={Ri,A}/*表示A的值既在寄存器Ri中又在內(nèi)存中*/第七章目標(biāo)代碼生成假設(shè)基本塊中每個四元式的形式都是A=BopC，則代碼生成算法是對每個四元式i：A=BopC執(zhí)行下述步驟：(1)調(diào)用函數(shù)GETREG(i：A=BopC)返回存放A值結(jié)果的寄存器R。(2)通過地址描述數(shù)組AVALUE[B]和AVALUE[C]確定出變量B和變量C的現(xiàn)行值存放位置B'和C'；如果是存放在寄存器中，則把寄存器取作B'和C'。(3)如果B'≠R，則生成目標(biāo)代碼： MOVR,B' opR,C'否則生成目標(biāo)代碼： opR,C'如果B'或C'為R，則刪除AVALUE[B]或AVALUE[C]中的R。第七章目標(biāo)代碼生成(4)令A(yù)VALUE[A]={R}并令RVALUE[R]={A}，表示變量A的現(xiàn)行值只在R中且R中的值只代表A的現(xiàn)行值。(5)如果B和C的現(xiàn)行值在基本塊中不再被引用，它們也不是基本塊出口之后的活躍變量且它們的現(xiàn)行值存放在寄存器Rk中，則刪除RVALUE[Rk]中的B和C以及AVALUE[B]中的Rk，使寄存器Rk不再為B和C所占用。第七章目標(biāo)代碼生成函數(shù)GETREG(i：A=BopC)用來得到存放A的當(dāng)前值的寄存器R；其算法如下：(1)如果B的現(xiàn)行值在某寄存器Ri中，且該寄存器只包含B的值，或者B和A是同一標(biāo)識符，或者B在該四元式之后不再被引用，則選取Ri為所需寄存器并轉(zhuǎn)(4)。(2)如有尚未分配的寄存器，則從中選取一個Ri為所需寄存器并轉(zhuǎn)(4)。(3)從已分配的寄存器中選取一個Ri為所需寄存器R。選取原則為：占用Ri的變量的值也同時放在內(nèi)存中，或者該值在基本塊中要在最遠的位置才會引用到。這樣，對寄存器Ri所含的變量和變量在內(nèi)存中的情況必須先做如下調(diào)整：第七章目標(biāo)代碼生成對RVALUE[Ri]中的每一個變量M，如果M不是A或者M既是A又是C卻不是B，而B又不在RVALUE[Ri]中，則：①如果AVALUE[Ri]中不包含M，則生成目標(biāo)代碼MOVM,Ri；②當(dāng)M不是A時，如果M是B或者M是C且同時B也在RVALUE[Ri]中，則令A(yù)VALUE[M]={M,R}，否則令A(yù)VALUE[M]={M}；③刪除RVALUE[Ri]中的M。(4)給出R，返回。第七章目標(biāo)代碼生成例7.2對例7.1，假設(shè)只有AX和BX是可用寄存器，用代碼生成算法生成目標(biāo)代碼及其相應(yīng)的RVALUE和AVALUE。[解答]用代碼生成算法生成的目標(biāo)代碼及其相應(yīng)的RVALUE和AVALUE，如表7.2所示。第七章目標(biāo)代碼生成第七章目標(biāo)代碼生成對其它形式的四元式也可仿照上述算法生成其目標(biāo)代碼。這里特別要指出的是，對形如A=B的復(fù)寫，如果B的現(xiàn)行值在某寄存器Ri中，那么無需生成目標(biāo)代碼，只需在RVALUE[Ri]中增加一個A(即把Ri同時分配給B和A)，把AVALUE[A]改為Ri；而且如果其后B不再被引用，還可把RVALUE[Ri]中的B和AVALUE[B]中的Ri刪除。第七章目標(biāo)代碼生成處理完基本塊中所有的四元式后，對現(xiàn)行只在某寄存器中的每個變量，如果它在基本塊出口之后是活躍的，則要用MOV指令把它在寄存器中的值存放到數(shù)據(jù)區(qū)以它命名的內(nèi)存單元中。為進行這一工作，我們利用寄存器描述數(shù)組RVALUE來決定其中哪些變量的現(xiàn)行值在寄存器中，再利用地址描述數(shù)組AVALUE來決定其中哪些變量的現(xiàn)行值尚不在其內(nèi)存單元中，最后利用活躍變量信息來決定其中哪些變量是活躍的。例如，由例7.2的表7.2查RVALUE欄可知：U和D的值在寄存器中，而從AVALUE欄知U和D的值都不在內(nèi)存單元中，如果D在基本塊出口之后是活躍變量，則在表7.2所生成的目標(biāo)代碼后面還要生成一條目標(biāo)代碼： MOVD,AX第七章目標(biāo)代碼生成7.1.3寄存器分配第七章目標(biāo)代碼生成7.1.4源程序到目標(biāo)代碼生成示例以PC機的匯編語言作為目標(biāo)代碼，假定可用的寄存器為AX、BX、CX和DX，則一C語言源程序轉(zhuǎn)換為四元式代碼序列，然后再轉(zhuǎn)換為目標(biāo)代碼程序(轉(zhuǎn)換中不考慮優(yōu)化)的結(jié)果如下：(1)?C語言源程序(局部)：while(a>b){if(m>=n)a=a+1;elsewhile(k==h)x=x+2;m=n+x*(m+y);}第七章目標(biāo)代碼生成(2)四元式代碼序列：100(j>,a,b,102)101(j,_,_,117)102(j>=,m,n,104)103(j,_,_,107)104(+,a,1,T1)105(=,T1,_,a)106(j,_,_,112)107(j=,k,h,109)108(j,_,_,112)第七章目標(biāo)代碼生成109(+,x,2,T2)110(=,T2,_,x)111(j,_,_,107)112(+,m,y,T3)113(*,x,T3,T4)114(+,n,T4,T5)115(=,T5,_,m)116(j,_,_,100)第七章目標(biāo)代碼生成(3)目標(biāo)代碼程序?(匯編語言程序)：;File:compile.asm;************************************datasegment;定義數(shù)據(jù)段 h DW kDW m DW n DW x DW y DW a DW b DWdataends;數(shù)據(jù)段定義結(jié)束;************************************第七章目標(biāo)代碼生成codesegment ;定義代碼段mainprocfar ;程序的執(zhí)行部分assumcs:code,ds:datastart:pushdssubbx,bxpushbxmovbx,data ;設(shè)置DS段為當(dāng)前數(shù)據(jù)段movds,bx第七章目標(biāo)代碼生成;語句翻譯由此開始：100:movAX,acmpAX,bjg102101:mp117102:movAX,mcmpAX,njge104103:jmp107104:movAX,a