【正文】 83 ?樹重寫規(guī)則可表示為： label:pattern[{cost}][={action}] ?label是與文法規(guī)則左邊的非終結(jié)符相對(duì)應(yīng)的標(biāo)識(shí)符 ?pattern為樹模式 ?cost部分是由代碼生成程序執(zhí)行的 C代碼。如圖 可以分別為 2－可著色的和 3－可著色的，但卻不能利用這 種規(guī)則進(jìn)行修剪： 68 69 （ 2）消極試探法： ?消極試探法是通過(guò)排除圖中 degree≥R的結(jié)點(diǎn)以對(duì)第一種 方法進(jìn)行推廣 ?基本原理： 因?yàn)槟硞€(gè)結(jié)點(diǎn)具有 R或更多的相鄰結(jié)點(diǎn)，這些 相鄰結(jié)點(diǎn)并不需要所有的均具有不同的顏色 ,進(jìn)一步地說(shuō) , 它們并一定能用完 R種顏色 ?通過(guò)從圖中反復(fù)查找度小于 R的結(jié)點(diǎn)，開始對(duì)圖進(jìn)行著色 ?選擇一個(gè) degree≥R的結(jié)點(diǎn)消極地放入棧中，選擇原則： 根據(jù)其 spill cost值除以其目前的度，所得的值最小的結(jié)點(diǎn) 優(yōu)先級(jí)最高 70 三 .示例 ?如圖 ，代碼片斷中使用了符號(hào)寄存器： 71 ?假設(shè)可供分配使用的寄存器為 r2 、 r r4，分別為其建 立干擾圖和相鄰矩陣，如圖 ： 72 ?由于符號(hào)寄存器 s1在退出塊 B1時(shí)， s0從其定義點(diǎn)之后都不 再是活躍的，因此它們的 spill開銷值都為無(wú)窮大，如圖 ： 73 ?符號(hào)寄存器 s1無(wú)相鄰結(jié)點(diǎn)，首先將其先放入棧中。利用相鄰列表，盡量給每個(gè)結(jié)點(diǎn)著色， 且使沒有兩個(gè)相鄰的結(jié)點(diǎn)具有同樣的顏色。 代碼生成概述 ?代碼生成 是把經(jīng)過(guò)語(yǔ)法分析或優(yōu)化后的中間代碼轉(zhuǎn)換成 特定目標(biāo)機(jī)的機(jī)器語(yǔ)言或匯編語(yǔ)言，這樣的轉(zhuǎn)換程序稱 為 代碼生成程序 ?衡量目標(biāo)代碼的質(zhì)量主要從占用 空間 和執(zhí)行 效率 兩個(gè)方 面綜合考慮 第十二章 代碼生成 4 一 .代碼生成程序在編譯系統(tǒng)中的位置 ?代碼生成程序在編譯系統(tǒng)中的位置如圖 ： 5 ?目標(biāo)代碼一般有 3種形式 ： （ 1）能夠立即執(zhí)行的機(jī)器語(yǔ)言代碼，所有地址均已定位 （ 2）待裝配的機(jī)器語(yǔ)言模塊，當(dāng)需要執(zhí)行時(shí)，由連接裝入 程序把它們和某些運(yùn)行程序連接起來(lái)，轉(zhuǎn)換成能執(zhí)行的機(jī) 器語(yǔ)言代碼 （ 3）匯編語(yǔ)言代碼，尚需經(jīng)過(guò)匯編程序匯編，轉(zhuǎn)換成可執(zhí) 行的機(jī)器語(yǔ)言代碼 6 二 .設(shè)計(jì)代碼生成程序的基本問(wèn)題 ： ?代碼生成程序的輸入由前端所產(chǎn)生的中間表示和符號(hào)表 中的信息組成 ?代碼生成程序可以利用符號(hào)表中的信息來(lái)決定中間代碼 中的名字所指示的數(shù)據(jù)對(duì)象的運(yùn)行時(shí)地址 7 ： ?所謂指令選擇 ，是指尋找一個(gè)合適的目標(biāo)機(jī)指令序列以 實(shí)現(xiàn)給定的中間表示 ?例如，對(duì)中間代碼 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í)行速度和代碼序列的長(zhǎng)度 ?例如，如果目標(biāo)機(jī)器有“加 1”指令（ INC），那么代碼 a:=a+1用 INC a實(shí)現(xiàn)是最有效的，而不是用以下的指令序 列實(shí)現(xiàn)： ?LD R0,a ?ADD R0,1 ?ST R0,a 9 ?指令選擇的基本原則： （ 1）減少產(chǎn)生代碼的尺寸 （ 2）減少目標(biāo)代碼的執(zhí)行時(shí)間 （ 3）降低目標(biāo)代碼的能耗 這三者在某些情況下有可能會(huì)出現(xiàn)沖突，在具體選擇 的過(guò)程中應(yīng)做折中考慮 10 ： ?寄存器分配的工作是確定在程序的哪個(gè)點(diǎn)將哪些變量或 中間量的值放在寄存器中比較有益 ?將經(jīng)常使用的操作數(shù)保存在寄存器中是比較有利的 ? 一些目標(biāo)機(jī)可能具有不同類型的寄存器，對(duì)寄存器使用 的一致性方面也存在一定的約束 11 ?寄存器的使用可以分成： （ 1）分配階段：為程序的某一點(diǎn)選擇駐留在寄存器中的一 組變量 （ 2）指派階段：挑出變量將要駐留的具體寄存器，即寄存 器賦值 12 ?寄存器分配原則： （ 1）生成某變量的目標(biāo)對(duì)象值時(shí)，盡量讓變量的值或計(jì)算 結(jié)果保留在寄存器中直到寄存器不夠分配為止 （ 2）當(dāng)?shù)交緣K出口時(shí)，將變量的值存放在內(nèi)存中 （ 3）在同一基本塊內(nèi)后面不再被引用的變量所占用的寄存 器應(yīng)遲早釋放，以提高寄存器的利用率 13 ?例如，考慮圖 ，它們僅有的區(qū) 別是第 2個(gè)語(yǔ)句的算符不同，其最短代碼序列在圖 給出： 14 15 ： ?指令調(diào)度是指確定程序指令的執(zhí)行順序 ?例如，若在 MIPS 4KC上計(jì)算表示式 (a+b)+c，可用表 ，它們的主要不同在于指令 順序和寄存器的賦值： 16 17 167。對(duì)每個(gè)符號(hào)寄存器，計(jì)算將其 spill到內(nèi) 存后又將其重新存入到寄存器中的開銷 49 （ 6）干擾圖的修剪。 4個(gè) web如下 所示： ?web Components ?w1 def x in B2, def x in B3, use x in B4, use x in B5 ?w2 def x in B5, use x in B6 ?w3 def y in B2, use y in B4 ?w4 def y in B1, use y in B3 ?利用 web代替變量名的主要好處在于，可以區(qū)分程序中具 有相同命名但表示不同意義的變量，以方便寄存器的分配 53 ： ?在干擾圖中，每個(gè)實(shí)際寄存器和每個(gè) web分別為干擾圖的 一個(gè)結(jié)點(diǎn) ?與某個(gè)結(jié)點(diǎn)相連的邊數(shù)，稱為該結(jié)點(diǎn)的度 degree ?圖 4個(gè) web間的干擾圖如圖 ： 54 ?若所有的寄存器是同構(gòu)的，則沒有必要將寄存器包括在干 擾圖中 ?若目標(biāo)機(jī)有兩個(gè)以上的專用寄存器集合，則對(duì)這兩類寄存 器的分配可以分開處理，這樣可以減少干擾圖的復(fù)雜性， 并使之具有較少的限制 55 ?對(duì)干擾圖所占用空間和訪問(wèn)時(shí)間進(jìn)行折中考慮，采用下述 兩種表示方法： （ 1）相鄰矩陣表示法： ?相鄰矩陣 AdjMtx[2..nwebs,1..nwebs1]是一個(gè)低三角矩陣 , 其中，矩陣的行與列分別表示干擾圖中的結(jié)點(diǎn) ?若第 i個(gè)寄存器與第 j個(gè)寄存器是相鄰的，則 AdjMtx[max(i,j),min(i,j)]的值為真，否則為假 ?矩陣表示實(shí)現(xiàn)了干擾圖的快速建立，同時(shí)，能快速確定某 兩個(gè)結(jié)點(diǎn)是否是相鄰