第七章目標代碼生成2023/12/26第七章目標代碼生成(2)待裝配的機器語言模塊，其地址均為相對地址，所以不能直接執行。當需要執行時由連接裝配程序把它們與其它運行程序和庫函數連接起來，裝配成可執行的機器語言代碼，如PC機中后綴為?.OBJ的文件都屬于待裝配的模塊(文件)。(3)匯編語言程序，必須通過匯編程序的匯編方可轉換成可執行的機器語言代碼，如PC機中后綴為?.ASM的文件即為匯編語言程序。第七章目標代碼生成一個高級語言程序的目標代碼要經常、反復使用，因此代碼生成要著重考慮兩個問題：一是如何使生成的目標代碼較短，二是如何充分利用計算機的寄存器以減少目標代碼中訪問存儲單元的次數。生成的目標代碼越短，寄存器的利用越充分，目標代碼的質量也就越高。設計一個代碼生成器需要考慮具體的機器結構、指令格式、字長及寄存器個數和種類，并且與指令的語義和所用的操作系統、存儲管理等都密切相關。第七章目標代碼生成7.1一個簡單代碼生成器一個簡單的代碼生成器，此生成器依次把每條中間代碼變換成目標代碼，并且在一個基本塊范圍內考慮如何充分利用寄存器的問題。一方面，在基本塊中，當生成計算某變量值的目標代碼時，盡可能地讓該變量的值保留在寄存器中(即不編出把該變量的值存到內存單元的指令)，直到該寄存器必須用來存放其它變量的值或已達基本塊出口為止；另一方面，后續的目標代碼盡可能地引用變量在寄存器中的值而不訪問內存。第七章目標代碼生成如一C語言語句A=(B+C)*D+E，翻譯為四元式G： T1=B+C T2=T1*D A=T2+E如果不考慮代碼的效率，可以簡單地把每條中間代碼(四元式)映射成若干條目標指令，如將x=y+z映射為 MOVAX,y/*AX為寄存器*/ ADDAX,z MOVx,AX其中，x、y、z均為數據區的內存變量。第七章目標代碼生成上述四元式代碼序列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第七章目標代碼生成從正確性來看，這種翻譯不存在問題，但卻存在冗余。指令序列中的(4)和(7)兩條指令是多余的；而T1、T2均是中間代碼生成時產生的臨時變量，它們在出了基本塊后將不再使用，故(3)、(6)兩條指令也可刪去。因此，在考慮了效率和充分使用寄存器之后，應生成如下代碼：(1)?MOVAX,B(2)?ADDAX,C(3)?MULAX,D(4)?ADDAX,E(5)?MOVA,AX為了實現這一目的，代碼生成器就必須了解一些信息：在產生T2=T1*D對應的目標代碼時，為了省去指令MOVAX,T1，就必須知道T1的當前值已在寄存器AX中；為了省去MOVT1,AX，就必須知道出了基本塊后T1不再被引用。第七章目標代碼生成7.1.1待用信息與活躍信息在一個基本塊內的目標代碼中，為了提高寄存器的使用效率，應將基本塊內還要被引用的值盡可能地保留在寄存器中，而將基本塊內不再被引用的變量所占用的寄存器盡早釋放。每當翻譯一條四元式如A=BopC時，需要知道在基本塊中還有哪些四元式要對變量A、B、C進行引用，為此，需要收集一些待用信息。 在一個基本塊中，四元式i對變量A定值，如果i后面的四元式j要引用A且從i到j的四元式沒有其它對A的定值點，則稱j是四元式i中對變量A的待用信息，同時也稱A是活躍的。如果A被多處引用，則構成了A的待用信息鏈與活躍信息鏈。第七章目標代碼生成 為了取得每個變量在基本塊內的待用信息和活躍信息，可從基本塊的出口由后向前掃描，對每個變量建立相應的待用信息鏈與活躍信息鏈。 如果沒有進行數據流分析并且臨時變量不允許跨基本塊引用，則把基本塊中的臨時變量均看作基本塊出口之后的非活躍變量，而把所有的非臨時變量均看作基本塊出口之后的活躍變量。 如果某些臨時變量能夠跨基本塊使用，則把這些臨時變量也看成基本塊出口之后的活躍變量。第七章目標代碼生成假設變量的符號表內有待用信息和活躍信息欄，則計算變量待用信息的算法如下：(1)首先將基本塊中各變量的符號表的待用信息欄置為“非待用”，對活躍信息欄則根據該變量在基本塊出口之后是否活躍而將該欄中的信息置為“活躍”或“非活躍”。(2)從基本塊出口到基本塊入口由后向前依次處理各四元式。對每個四元式i：A=BopC依次執行以下步驟：第七章目標代碼生成①把符號表中變量A的待用信息和活躍信息附加到四元式i上；②把符號表中變量A的待用信息和活躍信息分別置為“非待用”和“非活躍”；③把符號表中變量B和C的待用信息和活躍信息附加到四元式i上；④把符號表中變量B和C的待用信息置為i，活躍信息置為“活躍”。注意：以上①～④次序不能顛倒，如果四元式出現A=opB或者A=B形式，則以上執行步驟完全相同，只是其中不涉及變量C。第七章目標代碼生成例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為中間變量。試求各變量的待用信息鏈和活躍信息鏈。[解答]我們根據計算變量待用信息的算法得到各變量的待用信息鏈和活躍信息鏈如表7.1所示。表中的“F”表示“非待用”或“非活躍”，“L”表示“活躍”，(1)～(4)分別表示基本塊中的四個四元式。待用信息鏈和活躍信息鏈的每列從左到右為每行從后向前掃描一個四元式時相應變量的信息變化情況(空白處表示沒有變化)。第七章目標代碼生成第七章目標代碼生成待用信息和活躍信息在四元式上的標記如下(每個變量都先去掉待用信息鏈和活躍信息鏈最右的值，然后由右向左依次引用所出現的值)：(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第七章目標代碼生成7.1.2代碼生成算法為了在代碼生成中進行寄存器分配，需要隨時掌握各寄存器的使用情況，即它是處于空閑狀態還是已分配給某個變量或已分配給某幾個變量。通常用一個寄存器描述數組RVALUE動態地記錄各寄存器的當前狀況，并用寄存器Ri的編號作為它的下標。此外，還需建立一個變量地址描述數組AVALUE來記錄各變量現行值存放的位置，即其是在某寄存器中還是在某內存單元中，或者同時存在于某寄存器和某內存單元中，可以有如下表示：RVALUE[Ri]={A} /*寄存器Ri分配給變量A*/RVALUE[Ri]={A,B} /*寄存器Ri分配給變量A和B*/RVALUE[Ri]={} /*未分配*/AVALUE[A]={A} /*表示A的值在內存中*/AVALUE[A]={Ri} /*表示A的值在寄存器Ri中*/AVALUE[A]={Ri,A}/*表示A的值既在寄存器Ri中又在內存中*/第七章目標代碼生成假設基本塊中每個四元式的形式都是A=BopC，則代碼生成算法是對每個四元式i：A=BopC執行下述步驟：(1)調用函數GETREG(i：A=BopC)返回存放A值結果的寄存器R。(2)通過地址描述數組AVALUE[B]和AVALUE[C]確定出變量B和變量C的現行值存放位置B'和C'；如果是存放在寄存器中，則把寄存器取作B'和C'。(3)如果B'≠R，則生成目標代碼： MOVR,B' opR,C'否則生成目標代碼： opR,C'如果B'或C'為R，則刪除AVALUE[B]或AVALUE[C]中的R。第七章目標代碼生成(4)令AVALUE[A]={R}并令RVALUE[R]={A}，表示變量A的現行值只在R中且R中的值只代表A的現行值。(5)如果B和C的現行值在基本塊中不再被引用，它們也不是基本塊出口之后的活躍變量且它們的現行值存放在寄存器Rk中，則刪除RVALUE[Rk]中的B和C以及AVALUE[B]中的Rk，使寄存器Rk不再為B和C所占用。第七章目標代碼生成函數GETREG(i：A=BopC)用來得到存放A的當前值的寄存器R；其算法如下：(1)如果B的現行值在某寄存器Ri中，且該寄存器只包含B的值，或者B和A是同一標識符，或者B在該四元式之后不再被引用，則選取Ri為所需寄存器并轉(4)。(2)如有尚未分配的寄存器，則從中選取一個Ri為所需寄存器并轉(4)。(3)從已分配的寄存器中選取一個Ri為所需寄存器R。選取原則為：占用Ri的變量的值也同時放在內存中，或者該值在基本塊中要在最遠的位置才會引用到。這樣，對寄存器Ri所含的變量和變量在內存中的情況必須先做如下調整：第七章目標代碼生成對RVALUE[Ri]中的每一個變量M，如果M不是A或者M既是A又是C卻不是B，而B又不在RVALUE[Ri]中，則：①如果AVALUE[Ri]中不包含M，則生成目標代碼MOVM,Ri；②當M不是A時，如果M是B或者M是C且同時B也在RVALUE[Ri]中，則令AVALUE[M]={M,R}，否則令AVALUE[M]={M}；③刪除RVALUE[Ri]中的M。(4)給出R，返回。第七章目標代碼生成例7.2對例7.1，假設只有AX和BX是可用寄存器，用代碼生成算法生成目標代碼及其相應的RVALUE和AVALUE。[解答]用代碼生成算法生成的目標代碼及其相應的RVALUE和AVALUE，如表7.2所示。第七章目標代碼生成第七章目標代碼生成對其它形式的四元式也可仿照上述算法生成其目標代碼。這里特別要指出的是，對形如A=B的復寫，如果B的現行值在某寄存器Ri中，那么無需生成目標代碼，只需在RVALUE[Ri]中增加一個A(即把Ri同時分配給B和A)，把AVALUE[A]改為Ri；而且如果其后B不再被引用，還可把RVALUE[Ri]中的B和AVALUE[B]中的Ri刪除。第七章目標代碼生成處理完基本塊中所有的四元式后，對現行只在某寄存器中的每個變量，如果它在基本塊出口之后是活躍的，則要用MOV指令把它在寄存器中的值存放到數據區以它命名的內存單元中。為進行這一工作，我們利用寄存器描述數組RVALUE來決定其中哪些變量的現行值在寄存器中，再利用地址描述數組AVALUE來決定其中哪些變量的現行值尚不在其內存單元中，最后利用活躍變量信息來決定其中哪些變量是活躍的。例如，由例7.2的表7.2查RVALUE欄可知：U和D的值在寄存器中，而從AVALUE欄知U和D的值都不在內存單元中，如果D在基本塊出口之后是活躍變量，則在表7.2所生成的目標代碼后面還要生成一條目標代碼： MOVD,AX第七章目標代碼生成7.1.3寄存器分配第七章目標代碼生成7.1.4源程序到目標代碼生成示例以PC機的匯編語言作為目標代碼，假定可用的寄存器為AX、BX、CX和DX，則一C語言源程序轉換為四元式代碼序列，然后再轉換為目標代碼程序(轉換中不考慮優化)的結果如下：(1)?C語言源程序(局部)：while(a>b){if(m>=n)a=a+1;elsewhile(k==h)x=x+2;m=n+x*(m+y);}第七章目標代碼生成(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)第七章目標代碼生成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)第七章目標代碼生成(3)目標代碼程序?(匯編語言程序)：;File:compile.asm;************************************datasegment;定義數據段 h DW kDW m DW n DW x DW y DW a DW b DWdataends;數據段定義結束;************************************第七章目標代碼生成codesegment ;定義代碼段mainprocfar ;程序的執行部分assumcs:code,ds:datastart:pushdssubbx,bxpushbxmovbx,data ;設置DS段為當前數據段movds,bx第七章目標代碼生成;語句翻譯由此開始：100:movAX,acmpAX,bjg102101:mp117102:movAX,mcmpAX,njge104103:jmp107104:movAX,a