編譯原理第5版-課件 第9章 目標代碼生成 2025

編譯程序最后一個階段是目標代碼生成。它通常在語義分析后或者優(yōu)化后的中間代碼上進行，并將中間代碼轉(zhuǎn)化為等價的目標代碼。本章主要介紹簡單代碼生成器的設(shè)計和構(gòu)造方法第9章目標代碼生成編譯程序的最終目的是將源程序翻譯成等價的目標程序，為了達到此目的，編譯程序除了對源程序進行詞法分析、語法分析和語義分析外，還必需將語義分析后或者優(yōu)化后的中間代碼轉(zhuǎn)換為等價的目標代碼。9.1概述一.目標代碼生成的任務9.1概述代碼生成器目標代碼程序中間代碼程序代碼生成器的輸入除中間代碼外還包括符號表中的信息，生成的目標代碼一般有如下三種形式1.能夠立即執(zhí)行的機器語言代碼，它們通常存放在固定的存儲區(qū)中，編譯后可直接執(zhí)行。2.待裝配的機器語言模塊，當需要執(zhí)行時，由連接裝配程序把它們與另外一些運行子程序連接起來，組合成可執(zhí)行的機器語言代碼。3.匯編語言程序，必須通過匯編程序匯編成可執(zhí)行的機器語言代碼。9.1概述二.設(shè)計代碼生成器時要著重考慮目標代碼的質(zhì)量衡量目標代碼的質(zhì)量1.存儲空間:生成的目標代碼短。2.執(zhí)行效率:充分利用寄存器，減少訪問存儲單元的次數(shù)。9.1概述具體設(shè)計一個代碼生成器需要考慮機器結(jié)構(gòu)、系統(tǒng)指令格式等方面的問題。由于計算機體系結(jié)構(gòu)和操作系統(tǒng)的多樣性，我們在這里不做具體介紹，僅僅以一個假想的計算機模型為例，簡單討論代碼生成的基本原理。9.2假想計算機模型簡單代碼生成器功能依次把四元式變換成目標代碼，并在一個基本塊內(nèi)考慮如何充分利用寄存器。在設(shè)計代碼生成器時，為考慮充分利用寄存器，我們須要考慮下面兩點：9.3簡單代碼生成器1.給出寄存器的分配原則（1）把基本塊內(nèi)還要使用的變量的值盡可能地保存在寄存器中；（2）在基本塊內(nèi)，把不再使用的變量所占用的寄存器及時釋放掉；（3）當?shù)交緣K出口時，將變量的值存放在內(nèi)存中。9.3簡單代碼生成器當翻譯一個四元式如A=BopC時，我們需要知道在基本塊中還有哪些四元式要對變量A、B、C進行引用。2.建立每個變量的待用信息和活躍信息（1）待用信息9.3簡單代碼生成器例

(i)A=T1

(j)T2=AOPX (j)為四元式(i)變量A的待用信息9.3簡單代碼生成器A在(i)定值A(chǔ)在(j)引用(2)活躍變量 基本塊中所有的非臨時變量均看作基本塊出口之后的活躍變量，臨時變量根據(jù)其在基本塊出口之后是否被引用來確定它是否為活躍變量。9.3簡單代碼生成器(3)計算變量待用信息和活躍信息的算法：

輸入：基本塊及其入口語句號和出口語句號輸出：附加待用信息和活躍信息的基本塊9.3簡單代碼生成器算法的步驟假設(shè)變量的符號表內(nèi)有待用信息和活躍信息欄（1）將符號表中每個變量的待用信息欄初始化為“非待用”，對活躍信息欄則根據(jù)該變量在基本塊出口之后是否活躍，將該欄中的信息置為“活躍”或“非活躍”。

9.3簡單代碼生成器見表1（2）從基本塊出口到基本塊入口由后向前依次處理各四元式。對每個四元式i:A=BopC，依次執(zhí)行如下驟①把符號表中變量A的待用信息和活躍信息附加到四元式i上；②把符號表中變量A的待用信息欄和活躍信息欄分別置為“非待用”和“非活躍”；9.3簡單代碼生成器見表2見后③把符號表中變量B和C的待用信息和活躍信息附加到四元式i上；④把符號表中B和C的待用信息置為i，活躍信息置為“活躍”。注意，以上①、②、③、④次序不能顛倒。9.3簡單代碼生成器見后見表3我們根據(jù)上述算法得到待用信息鏈和活躍信息鏈如下：9.3簡單代碼生成器⑴T=A－B⑵U=A－C⑶V=T＋U⑷D=V＋U變量名待用信息活躍信息待用信息鏈活躍信息鏈初值初值TABCUVDFFFFFFFFLLLFFLF(3)(2)(1)(1)(2)(3)(4)F(4)FFLLFLLLFLLLFF返回1返回2返回3待用信息和活躍信息在四元式上的標記如下：⑴T⑶L=A⑵L-BFL⑵U⑶L=AFL-CFL⑶V⑷L=TFF+U⑷L⑷DFL=VFF+UFF9.3簡單代碼生成器返回3返回2在代碼生成中進行寄存器分配，我們需隨時掌握各寄存器的使用情況3.建立寄存器描述數(shù)組RVALUE，動態(tài)地記錄各寄存器的分配狀況9.3簡單代碼生成器RVALUE[R]={}{A}{A,B}分配給某變量A分配給變量A,B空閑4.建立變量地址描述數(shù)組AVALUE，動態(tài)地記錄各變量現(xiàn)行值的存放位置AVALUE[A]={R}{A}{A,R}A的現(xiàn)行值在寄存器R中A的現(xiàn)行值在內(nèi)存中A的現(xiàn)行值既在寄存器R中又在內(nèi)存中9.3簡單代碼生成器 有了上述對寄存器和地址的描述，我們可以給出一個簡單代碼生成算法。9.3簡單代碼生成器調(diào)用函數(shù)GETREG(i:A=BopC)得到存放A的現(xiàn)行值的寄存器R取變量B和C的現(xiàn)行值的存放位置B’和C’

B’AVALUE[B]C’AVALUE[C]B’=R?生成目標代碼

OPR,C’生成目標代碼

LDR,B’OPR,C’YN修改寄存器使用信息和地址描述信息 9.3簡單代碼生成器⑴T=A－B⑵U=A－C⑶V=T＋U⑷D=V＋ULDR0,ASUBR0,BLDR1,ASUBR1,CADDR0,R1

ADDR0,R1 現(xiàn)階段代碼生成器的自動生成器主要采用由形式描述進行驅(qū)動的技術(shù)，這種技術(shù)把目標機的每條指令的形式描述作為輸入，將表示計算的中間語言代碼與這種描述進行匹配來產(chǎn)生相應的指令。9.4代碼生成器的自動生成技術(shù) 形式描述技術(shù)的主要優(yōu)點是：把實現(xiàn)者從選擇計算給定構(gòu)造的代碼中解放出來，實現(xiàn)者只需要以形式化描述每條目標指令的精確意義，生成器將自動地查詢機器描述，找出為完成所需的計算的指令或指令串。9.4代碼生成器的自動生成技術(shù)1.目標代碼生成的任務

代碼生成一般是在語法分析后的中間代碼級上進行，其功能是將中間代碼轉(zhuǎn)換為目標代碼。本章小結(jié)2.目標代碼的形式本章小結(jié)（1）能夠立即執(zhí)行的機器語言代碼（2）待裝配的機器語言模塊（3）匯編語言代碼3.目標代碼生成需要考慮的基本問題本章小結(jié)(2)如何充分利用計算機的寄存器，減少目標代碼中訪問存儲單元的次數(shù)。(1)如何使生成的目標代碼最短；4.待用信息和活躍信息的概念本章小結(jié)(1)待用信息 (i)A