第十二章代碼生成-預(yù)覽頁(yè)
【正文】 性代碼生成文法 是建立一個(gè)代碼生成專用語(yǔ)言，用這 種語(yǔ)言以宏定義、子程序等形式描述代碼生成過(guò)程 ?通過(guò)這些宏定義和子程序把中間語(yǔ)言解釋為目標(biāo)代碼 ?這種方法使機(jī)器描述與代碼生成算法結(jié)合在一起，與機(jī)器 的聯(lián)系直接反映在算法中 ?機(jī)器描述是通過(guò)過(guò)程的形式提供的，如采用把源程序映像 成兩地址代碼序列的方法進(jìn)行代碼生成過(guò)程中，對(duì)加法的 代碼生成算法如下： 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 ?其中含有對(duì) IADD與 FADD的宏調(diào)用，以生成目標(biāo)機(jī)上的 整數(shù)和浮點(diǎn)數(shù)加法指令，如對(duì) IBM360機(jī)， IADD可寫(xiě)為： ?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）由于目標(biāo)機(jī)的多樣性、尋址方式、指令的差異等等， 給中間代碼的設(shè)計(jì)帶來(lái)困難 （ 2）代碼生成語(yǔ)言與機(jī)器密切相關(guān)，可移植性受到限制 （ 3）目標(biāo)機(jī)的描述與代碼生成算法混在一起，當(dāng)描述改變 時(shí)，勢(shì)必引起算法的改變 （ 4）需進(jìn)行指令的選擇、指令的排序等低層次的繁瑣工作 ，產(chǎn)生的目標(biāo)代碼質(zhì)量依賴于設(shè)計(jì)者的經(jīng)驗(yàn)和能力 （ 5）代碼生成的視野有限，雖可進(jìn)行一定范圍的優(yōu)化，但 對(duì)協(xié)調(diào)上下文有關(guān)的優(yōu)化較困難 40 二 .模式匹配代碼生成法 ?模式匹配代碼生成方法是把對(duì)機(jī)器的描述與代碼生成的算 法分開(kāi) ?而對(duì)在解釋性代碼生成方法中，所需做的較繁重的具體情 況分析的解釋工作用模式匹配來(lái)代替 41 ?也就是建立一個(gè)代碼生成用的機(jī)器描述語(yǔ)言，用以形式地 描述目標(biāo)機(jī)的資源、指令及其語(yǔ)義等有關(guān)信息 ?代碼生成程序根據(jù)這些信息，自動(dòng)地把中間語(yǔ)言程序翻譯 成目標(biāo)機(jī)的匯編語(yǔ)言或機(jī)器代碼 ?但在這種方法中，需通過(guò)形式描述的模式如實(shí)地反應(yīng)機(jī)器 的特性，這并不是一件容易的事，而且進(jìn)行模式匹配時(shí)耗 費(fèi)時(shí)間很長(zhǎng)，其目標(biāo)代碼的質(zhì)量也不太理想 42 三 .表驅(qū)動(dòng)代碼生成法 ?表驅(qū)動(dòng)代碼生成方法 ，實(shí)質(zhì)上是模式匹配代碼生成方法的 更進(jìn)一步自動(dòng)化，它是模仿從語(yǔ)法描述構(gòu)造表和表驅(qū)動(dòng)的 一種語(yǔ)法分析方法 ?首先，把對(duì)目標(biāo)機(jī)的形式化描述進(jìn)行預(yù)加工轉(zhuǎn)換成代碼生 成表 ?然后，用表驅(qū)動(dòng)的代碼生成程序，來(lái)驅(qū)動(dòng)代碼生成表 ?最后，把中間語(yǔ)言的內(nèi)部表示翻譯成目標(biāo)機(jī)的匯編代碼 ?也就是說(shuō)， 它是用一個(gè)代碼生成程序的生成器自動(dòng)地構(gòu)造 一個(gè)代碼生成程序 43 ?這種表驅(qū)動(dòng)代碼生成方法的 好處 是：容易使用和修改，并 且能較容易地為不同的計(jì)算機(jī)構(gòu)造適合于它們自己的代碼 生成程序 ?這樣將能增強(qiáng)編譯程序的可移植性和靈活性，但是它所生 成的目標(biāo)代碼的質(zhì)量，將依賴于機(jī)器描述的完善程序 ?最好的方法是用形式化的方法完善地描述一臺(tái)計(jì)算機(jī)，但 這并不是一件容易的事，因而這種方法有待進(jìn)一步改進(jìn)和 完善 44 167。從干擾圖的相鄰列表中排除結(jié)點(diǎn)及其 相應(yīng)的邊。若失敗，進(jìn)行下一步 （ 8）寄存器的 spill。該結(jié)點(diǎn)的度為為結(jié)點(diǎn) sj和 si度的并集 59 ?保證合并后為 R可著色的情況下，才進(jìn)行合并，為此需要 兩條安全策略： （ 1）若合并后所得結(jié)點(diǎn) (a,b)具有小于 R個(gè)度大于或等于 R的 鄰居，則結(jié)點(diǎn) a和結(jié)點(diǎn) b是可以合并的 （ 2）對(duì)結(jié)點(diǎn) a的每個(gè)鄰居 t,要么 t與結(jié)點(diǎn) b已是相互干擾的， 要么 t的度小于 R，則這種合并是安全的 60 ?寄存器合并是一種功能強(qiáng)大的變換，其主要作用在于： （ 1）簡(jiǎn)化編譯過(guò)程，如消除不必要的拷貝操作 （ 2）在過(guò)程調(diào)用之前，保證參數(shù)值被移到合適的寄存器中 （ 3）對(duì)源和目的操作數(shù)有特殊要求的機(jī)器指令，使其操作 數(shù)和結(jié)果在適當(dāng)?shù)奈恢? （ 4）對(duì)操作數(shù)或結(jié)果值需要使用寄存器對(duì)的指令，保證能 夠?yàn)槠浞峙浼拇嫫鲗?duì)，等等 61 ： ?spilling的結(jié)果可能會(huì)將一個(gè) web分解為兩個(gè)或多個(gè) web， 從而減少干擾圖中的干擾 ?例如 ,通過(guò)將圖 ,如圖 ： 62 63 ?這樣 web w1被分成 4個(gè) web: w w w w8： ?web Components ?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 ?w5 def x in B2, tmp x in B2 ?w6 def x in B3, tmp x in B3 ?w7 x tmp in B4, use x in B4 ?w8 x tmp in B5, use x in B5 64 ?所得的干擾圖如圖 ： 65 ?干擾圖的相鄰列表中每項(xiàng)有一個(gè)成分 spcost。干擾圖的修剪過(guò)程如 圖 ： 74 ?修剪后的干擾圖如圖 (a)所示，可以看出，結(jié)點(diǎn) s8的度 小于 3，也將其壓入棧中： s8 s9 s4 r4 r3 r2 s1 ?這時(shí)，所得的干擾圖如圖 (b)所示： ?在余下的干擾圖中，每個(gè)結(jié)點(diǎn)的度都大于或等于 3，只好 使用消極試探法，即把 s7放入棧中，這樣簡(jiǎn)化了干擾圖使 其變成如圖 (c)所示： ?進(jìn)而將 s5壓入棧中。 所得的代碼的片斷如圖 ： 77 78 ?重新為其建立干擾圖，如圖 ： 79 ?利用 degreeR規(guī)則對(duì)其進(jìn)行修剪，并將實(shí)際寄存器賦給與 之具有相同顏色的符號(hào)寄存器，所得的代碼片斷如圖 ： 80 167。若模式匹配成功且動(dòng)態(tài)規(guī)劃算法推 斷出該模式是整個(gè)樹(shù)的最小覆蓋的一部分，則可執(zhí)行。 108 第 12章 習(xí)題 第 1題：一個(gè)編譯程序的代碼生成要著重考慮哪些問(wèn)題 ? 第 2題：決定目標(biāo)代碼的因素有哪些？ 第 3題：為什么在代碼生成時(shí)要考慮充分利用寄存器？ 第 4題：寄存器分配的原則是什么？ 109 第 12章 作業(yè)題 P301： 1.
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1