【正文】 的代碼生成程序的開發(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 二 .設(shè)計代碼生成程序的基本問題 ： ?代碼生成程序的輸入由前端所產(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)沖突，在具體選擇 的過程中應(yīng)做折中考慮 10 ： ?寄存器分配的工作是確定在程序的哪個點將哪些變量或 中間量的值放在寄存器中比較有益 ?將經(jīng)常使用的操作數(shù)保存在寄存器中是比較有利的 ? 一些目標機可能具有不同類型的寄存器，對寄存器使用 的一致性方面也存在一定的約束 11 ?寄存器的使用可以分成： （ 1）分配階段：為程序的某一點選擇駐留在寄存器中的一 組變量 （ 2）指派階段：挑出變量將要駐留的具體寄存器，即寄存 器賦值 12 ?寄存器分配原則： （ 1）生成某變量的目標對象值時，盡量讓變量的值或計算 結(jié)果保留在寄存器中直到寄存器不夠分配為止 （ 2）當?shù)交緣K出口時，將變量的值存放在內(nèi)存中 （ 3）在同一基本塊內(nèi)后面不再被引用的變量所占用的寄存 器應(yīng)遲早釋放，以提高寄存器的利用率 13 ?例如，考慮圖 ，它們僅有的區(qū) 別是第 2個語句的算符不同，其最短代碼序列在圖 給出： 14 15 ： ?指令調(diào)度是指確定程序指令的執(zhí)行順序 ?例如，若在 MIPS 4KC上計算表示式 (a+b)+c，可用表 ，它們的主要不同在于指令 順序和寄存器的賦值： 16 17 167。 幾種常用的代碼生成程序的開發(fā)方法 一 .解釋性代碼生成法 ?解釋性代碼生成文法 是建立一個代碼生成專用語言，用這 種語言以宏定義、子程序等形式描述代碼生成過程 ?通過這些宏定義和子程序把中間語言解釋為目標代碼 ?這種方法使機器描述與代碼生成算法結(jié)合在一起，與機器 的聯(lián)系直接反映在算法中 ?機器描述是通過過程的形式提供的，如采用把源程序映像 成兩地址代碼序列的方法進行代碼生成過程中，對加法的 代碼生成算法如下： 37 ?macro ADD x,y ?if type of x=integer and type of y=integer ?then IADD x,y ?else if type of x=float and type of y=float ?then FADD x,y ?else error 38 ?其中含有對 IADD與 FADD的宏調(diào)用，以生成目標機上的 整數(shù)和浮點數(shù)加法指令，如對 IBM360機， IADD可寫為： ?macro ADD a,b ?from a in R1,b in R2 ?emit (AR a,b) result in R1 ?from a in R,b in M ?emit(A a,b) result in R ?from a in M,b in R ?emit(A b,a) result in R 39 ?這種算法的局限性在于： （ 1）由于目標機的多樣性、尋址方式、指令的差異等等， 給中間代碼的設(shè)計帶來困難 （ 2）代碼生成語言與機器密切相關(guān)，可移植性受到限制 （ 3）目標機的描述與代碼生成算法混在一起，當描述改變 時，勢必引起算法的改變 （ 4）需進行指令的選擇、指令的排序等低層次的繁瑣工作 ，產(chǎn)生的目標代碼質(zhì)量依賴于設(shè)計者的經(jīng)驗和能力 （ 5）代碼生成的視野有限，雖可進行一定范圍的優(yōu)化，但 對協(xié)調(diào)上下文有關(guān)的優(yōu)化較困難 40 二 .模式匹配代碼生成法 ?模式匹配代碼生成方法是把對機器的描述與代碼生成的算 法分開 ?而對在解釋性代碼生成方法中，所需做的較繁重的具體情 況分析的解釋工作用模式匹配來代替 41 ?也就是建立一個代碼生成用的機器描述語言，用以形式地 描述目標機的資源、指令及其語義等有關(guān)信息 ?代碼生成程序根據(jù)這些信息，自動地把中間語言程序翻譯 成目標機的匯編語言或機器代碼 ?但在這種方法中，需通過形式描述的模式如實地反應(yīng)機器 的特性，這并不是一件容易的事，而且進行模式匹配時耗 費時間很長，其目標代碼的質(zhì)量也不太理想 42 三 .表驅(qū)動代碼生成法 ?表驅(qū)動代碼生成方法 ，實質(zhì)上是模式匹配代碼生成方法的 更進一步自動化，它是模仿從語法描述構(gòu)造表和表驅(qū)動的 一種語法分析方法 ?首先，把對目標機的形式化描述進行預(yù)加工轉(zhuǎn)換成代碼生 成表 ?然后，用表驅(qū)動的代碼生成程序，來驅(qū)動代碼生成表 ?最后，把中間語言的內(nèi)部表示翻譯成目標機的匯編代碼 ?也就是說， 它