【正文】 1 第十二章 代碼生成 ?第一節(jié) 代碼生成概述 ?第二節(jié) 一個簡單的代碼生成程序 ?第三節(jié) 幾種常用的代碼生成程序的開發(fā)方法 ?第四節(jié) 全局寄存器分配（圖著色法） ?第五節(jié) 代碼生成程序的自動化構(gòu)造 2 知識結(jié)構(gòu) 3 167。 代碼生成概述 ?代碼生成 是把經(jīng)過語法分析或優(yōu)化后的中間代碼轉(zhuǎn)換成 特定目標機的機器語言或匯編語言，這樣的轉(zhuǎn)換程序稱 為 代碼生成程序 ?衡量目標代碼的質(zhì)量主要從占用 空間 和執(zhí)行 效率 兩個方 面綜合考慮 第十二章 代碼生成 4 一 .代碼生成程序在編譯系統(tǒng)中的位置 ?代碼生成程序在編譯系統(tǒng)中的位置如圖 ： 5 ?目標代碼一般有 3種形式 ： （ 1）能夠立即執(zhí)行的機器語言代碼，所有地址均已定位 （ 2）待裝配的機器語言模塊，當需要執(zhí)行時，由連接裝入 程序把它們和某些運行程序連接起來，轉(zhuǎn)換成能執(zhí)行的機 器語言代碼 （ 3）匯編語言代碼，尚需經(jīng)過匯編程序匯編，轉(zhuǎn)換成可執(zhí) 行的機器語言代碼 6 二 .設計代碼生成程序的基本問題 ： ?代碼生成程序的輸入由前端所產(chǎn)生的中間表示和符號表 中的信息組成 ?代碼生成程序可以利用符號表中的信息來決定中間代碼 中的名字所指示的數(shù)據(jù)對象的運行時地址 7 ： ?所謂指令選擇 ，是指尋找一個合適的目標機指令序列以 實現(xiàn)給定的中間表示 ?例如，對中間代碼 x:=y+z，其中 x,y,z均為靜態(tài)分配的變 量，可以翻譯成下述代碼序列： ?LD R0,y /*將 y放入寄存器 R0*/ ?ADD R0,z /*將 z與 R0相加 */ ?ST R0,x /*將 R0的值存入 x*/ 8 ?生成代碼的質(zhì)量取決于它的執(zhí)行速度和代碼序列的長度 ?例如，如果目標機器有“加 1”指令（ INC），那么代碼 a:=a+1用 INC a實現(xiàn)是最有效的，而不是用以下的指令序 列實現(xiàn)： ?LD R0,a ?ADD R0,1 ?ST R0,a 9 ?指令選擇的基本原則： （ 1）減少產(chǎn)生代碼的尺寸 （ 2）減少目標代碼的執(zhí)行時間 （ 3）降低目標代碼的能耗 這三者在某些情況下有可能會出現(xiàn)沖突，在具體選擇 的過程中應做折中考慮 10 ： ?寄存器分配的工作是確定在程序的哪個點將哪些變量或 中間量的值放在寄存器中比較有益 ?將經(jīng)常使用的操作數(shù)保存在寄存器中是比較有利的 ? 一些目標機可能具有不同類型的寄存器，對寄存器使用 的一致性方面也存在一定的約束 11 ?寄存器的使用可以分成： （ 1）分配階段：為程序的某一點選擇駐留在寄存器中的一 組變量 （ 2）指派階段：挑出變量將要駐留的具體寄存器，即寄存 器賦值 12 ?寄存器分配原則： （ 1）生成某變量的目標對象值時，盡量讓變量的值或計算 結(jié)果保留在寄存器中直到寄存器不夠分配為止 （ 2）當?shù)交緣K出口時，將變量的值存放在內(nèi)存中 （ 3）在同一基本塊內(nèi)后面不再被引用的變量所占用的寄存 器應遲早釋放，以提高寄存器的利用率 13 ?例如，考慮圖 ，它們僅有的區(qū) 別是第 2個語句的算符不同，其最短代碼序列在圖 給出： 14 15 ： ?指令調(diào)度是指確定程序指令的執(zhí)行順序 ?例如，若在 MIPS 4KC上計算表示式 (a+b)+c，可用表 ，它們的主要不同在于指令 順序和寄存器的賦值： 16 17 167。 一個簡單的代碼生成程序 一 .計算機模型 ?假定一臺 M計算機具有 n+1個通用寄存器為 R0,R1,?,R n， 它們既可作為累加器又可作為變址器 ?如果用 op表示運算符，用 M表示內(nèi)存單元，用變量名表示 該變量所在的單元， C表示常量， *表示間址方式存取 18 ?指令形式可包含以下四種類型，見表 ： ?若 op是一目運算符，則 op Ri,M的意義為： op(M) Ri ?以上指令中的 op包括一般計算機上常見的一些運算符 j 19 ?某些指令的意義說明如表 ： 20 二 .待用信息鏈表法 ?若在一個基本塊中，變量 A在四元式 i中被定值，在 i后面 的四元式 j中要引用 A值，且從 i到 j之間沒有其他對 A的定 值點，這時稱 j是四元式 i中對變量 A的 待用信息 或稱 下次 引用信息 ，同時也 稱 A是活躍的 ，若 A被多處引用則可構(gòu) 成 待用信息鏈 與 活躍信息鏈 ?為了得到在一個基本塊內(nèi)每個變量的待用信息和活躍信 息，可以從基本塊出口的四元式開始 由后向前 掃描，為 每個變量名建立相應的待用信息鏈和活躍變量信息鏈 21 ?考慮到處理的方便，假定對基本塊中的變量 在出口處都是 活躍 的，而 對基本塊內(nèi)的臨時變量可分為兩種情況處理： ①對于沒有經(jīng)過數(shù)據(jù)流分析，且中間代碼生成的算法中不允 許在基本塊外引用的臨時變量，則這些臨時變量在基本塊 出口處都認為是不活躍的 ②如果中間代碼生成時的算法允許某些臨時變量在基本塊外 引用時，則假定這些臨時變量被認為是活躍的 22 ?在變量的符號表的記錄項中設定了待用信息和活躍信息的 欄目，其算法步驟如下： （ 1）對各基本塊的符號表中的“ 待用信息 ”欄置“ 非待用”， 對“ 活躍信息 ”欄，按在基本塊出中處是否為活躍而置成“活 躍”或“非活躍”，假定 外部變量 都是 活躍 的， 臨時變量 都是 非活躍 的 23 （ 2） 從后向前 依次處理每個四元式 i ： A:=B op C，在符號 表中依次執(zhí)行下述步驟： ① A的待用信息和活躍信息附加到 i上 ② 把 A置成 非待用 F和 非活躍 F ③ B和 C的待用信息和活躍信息附加到 i上 ④ 把 B和 C待用信息 置為 i， 活躍信息 置成 活躍 L 24 ?例如，四元式如下： (A,B,C,D是變量， T,U,V是中間變量 ) (1)T:=AB (2)U:=AC (3)V:=T+U (4)D:=V+U 25 變量 待用信息 活躍信息 初值 待用信息鏈 初值 活躍信息鏈 A B C D T U V 表 待用信息鏈和活躍信息鏈 L L F F F F F F F F F L L (4) (4)