編譯原理目標(biāo)代碼生成

《編譯原理目標(biāo)代碼生成》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第7章目標(biāo)代碼生成7.1一個簡單代碼生成器7.2匯編指令到機(jī)器代碼的翻譯概述7.1一個簡單代碼生成器我們首先介紹一個簡單的代碼生成器，此生成器依次把每條中間代碼變換成目標(biāo)代碼，并且在一個基本塊范圍內(nèi)考慮如何充分利用寄存器的問題。一方面，在基本塊中，當(dāng)生成計(jì)算某變量值的目標(biāo)代碼時，盡可能地讓該變量的值保留在寄存器中(即不編出把該變量的值存到內(nèi)存單元的指令)，直到該寄存器必須用來存放其它變量的值或已達(dá)基本塊出口為止；另一方面，后續(xù)的目標(biāo)代碼盡可能地引用變量在寄存器中的值而不訪問內(nèi)存。例如，一C語言語句為A=(B+C)*D+E，把它翻譯為四元式G

2、：T1=B+CT2=T1*DA=T2+E如果不考慮代碼的效率，可以簡單地把每條中間代碼(四元式)映射成若干條目標(biāo)指令，如將x=y+z映射為：MOVAX,y/*AX為寄存器*/ADDAX,zMOVx,AX其中，x、y、z均為數(shù)據(jù)區(qū)的內(nèi)存變量。這樣，上述四元式代碼序列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雖然從正確性來看，這種翻譯不存在問題，但它卻存在冗余。在上述指

3、令序列中，(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為了實(shí)現(xiàn)這一目的，代碼生成器就必須了解一些信息：在產(chǎn)生T2=T1*D對應(yīng)的目標(biāo)代碼時，為了省去指令MOVAX,T1，就必須知道T1的當(dāng)前值已在寄存器AX中；為了省去MOVT1,AX，就必須知道出了基本塊后T1不再被引用。7.1.

4、1待用信息與活躍信息在一個基本塊內(nèi)的目標(biāo)代碼中，為了提高寄存器的使用效率，應(yīng)將基本塊內(nèi)還要被引用的值盡可能地保留在寄存器中，而將基本塊內(nèi)不再被引用的變量所占用的寄存器盡早釋放。每當(dāng)翻譯一條四元式如A=BopC時，需要知道在基本塊中還有哪些四元式要對變量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的待用信息鏈與活躍信息鏈。為了取得每個變量在基本塊內(nèi)的

5、待用信息和活躍信息，可從基本塊的出口由后向前掃描，對每個變量建立相應(yīng)的待用信息鏈與活躍信息鏈。如果沒有進(jìn)行數(shù)據(jù)流分析并且臨時變量不允許跨基本塊引用，則把基本塊中的臨時變量均看作基本塊出口之后的非活躍變量，而把所有的非臨時變量均看作基本塊出口之后的活躍變量。如果某些臨時變量能夠跨基本塊使用，則把這些臨時變量也看成基本塊出口之后的活躍變量。假設(shè)變量的符號表內(nèi)有待用信息和活躍信息欄，則計(jì)算變量待用信息的算法如下：(1)首先將基本塊中各變量的符號表的待用信息欄置為“非待用”，對活躍信息欄則根據(jù)該變量在基本塊出口之后是否活躍而將該欄中的信息置為“活躍

6、”或“非活躍”。(2)從基本塊出口到基本塊入口由后向前依次處理各四元式。對每個四元式i：A=BopC依次執(zhí)行以下步驟：①把符號表中變量A的待用信息和活躍信息附加到四元式i上；②把符號表中變量A的待用信息和活躍信息分別置為“非待用”和“非活躍”；③把符號表中變量B和C的待用信息和活躍信息附加到四元式i上；④把符號表中B和C的待用信息置為i，活躍信息置為“活躍”。例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、]我們根據(jù)計(jì)算變量待用信息的算法得到各變量的待用信息鏈和活躍信息鏈如表7.1所示。表中的“F”表示“非待用”或“非活躍”，“L”表示“活躍”，(1)～(4)分別表示基本塊中的四個四元式。待用信息鏈和活躍信息鏈的每列從左到右為每行從后向前掃描一個四元式時相應(yīng)變量的信息變化情況(空白處表示沒有變化)。表7.1例7.1的待用信息鏈和活躍信息鏈變量名待用信息活躍信息初值待用信息鏈初值活躍信息鏈TF(3)FFLLFAF(2)(1)LLBF(1)LLCF(2)LLUF(4)(3)FFLLFVF(4)FFLFDFFLF待用信息和活躍信息在四元式上的標(biāo)記如

8、下：(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+UFF7.1.2代碼生成算法為了在代