【正文】 ?寄存器分配 ?計算順序 代碼生成器設(shè)計中的問題 ?輸入 ? 前端生成的源代碼的 IR(中間表示形式）及符號表信息 ? 中間表示形式的選擇 ? 四元式、三元式、字節(jié)代碼、堆棧機(jī)代碼、后綴表示、抽象語法樹、 DAG圖、 … ?輸出 ? RISC、 CISC； ? 可重定向代碼、匯編語言 代碼生成器設(shè)計中的問題 ?指令選擇 ?代碼生成器將中間表示形式映射為目標(biāo)機(jī)代碼 ?映射的復(fù)雜性由下列因素決定： ?IR的層次 ? 高：用代碼模板翻譯，但代碼質(zhì)量不高，需優(yōu)化 ? 低：利用低層次細(xì)節(jié)生成更高效的代碼 ?指令集體系結(jié)構(gòu)本身的特性 ?期望的目標(biāo)代碼質(zhì)量 代碼生成器設(shè)計中的問題 ?指令選擇 ?映射的復(fù)雜性由下列因素決定： ?IR的層次 ?指令集體系結(jié)構(gòu)本身的特性 ? 指令的統(tǒng)一性、完整性 ? 指令速度和機(jī)器慣用語 (idioms) ?期望的目標(biāo)代碼質(zhì)量 代碼生成器設(shè)計中的問題 ?指令選擇 ?映射的復(fù)雜性由下列因素決定： ?IR的層次 ?指令集體系結(jié)構(gòu)本身的特性 ?期望的目標(biāo)代碼質(zhì)量 ? 同一 IR程序可用不同代碼序列實現(xiàn)，它們的代價不同 ?示例： a=a+1可實現(xiàn)為兩種 ?INC a ?LD R0,a ?ADD R0,R0,1 ?ST a， R0 目標(biāo)機(jī)模型 ?本書使用三地址機(jī)器模型，指令如下： ? 加載 ? LD dst, addr；把地址 addr中的內(nèi)容加載到 dst所指寄存器。 ? 入口到第一條指令有一條邊 ? 從任何可能最后執(zhí)行的基本塊到出口有一條邊 流圖繪制舉例 流圖的例子 ?因跳轉(zhuǎn)而生成的邊 ? B3?B3 ? B4?B2 ? B6?B6 ?因為順序而生成的邊 ? 其它 循環(huán) ?程序的大部分運(yùn)行時間花費(fèi)在循環(huán)上 ?因此循環(huán)是識別的重點 ?循環(huán)的定義 ? 循環(huán) L是一個結(jié)點集合 ? 存在一個循環(huán)入口（ loop entry）節(jié)點，其唯一的前驅(qū)可以是循環(huán) L之外的結(jié)點 ? 其余結(jié)點都存在到達(dá) L的入口的非空路徑，且路徑都在 L中。 代碼生成器 ?根據(jù)三地址序列生成指令 ? 假設(shè)：每個三地址指令只有一個對應(yīng)的機(jī)器指令 ? 有一組寄存器用于計算基本塊內(nèi)部的值； ?主要目標(biāo) ? 盡量減少加載和保存指令，即最大限度利用寄存器； ?寄存器主要使用方法 ? 執(zhí)行運(yùn)算時，運(yùn)算分量必須放在寄存器中； ? 用于臨時變量 ? 存放全局的值 ? 進(jìn)行運(yùn)行時刻管理（比如：棧頂指針） 算法基本思想及數(shù)據(jù)結(jié)構(gòu) ?盡可能留 ? 依次考慮各個指令，盡可能把值保留在寄存器中，以減少寄存器 /內(nèi)存之間的數(shù)據(jù)交換 ?盡可能用 ? 為一個三地址指令生成機(jī)器指令時，只有當(dāng)運(yùn)算分量不在寄存器中時，才從內(nèi)存載入； ? 盡量保證寄存器中值不被使用時，才把它覆蓋掉。 L1: goto L2 若沒有跳轉(zhuǎn)到 L1的指令，且指令 L1: goto L2之前是一個無條件跳轉(zhuǎn)指令，則 L1該行指令可刪除。殺誰？ ? 全殺 !! 從 DAG到基本塊 ?重構(gòu)的方法 ? 對每個結(jié)點構(gòu)造一個三地址語句來計算對應(yīng)的值 ? 結(jié)果應(yīng)該盡量賦給一個活躍的變量 ?一般為出口活躍，如果不確定則假設(shè)所有非臨時變量都出口活躍 ? 如果結(jié)點有多個關(guān)聯(lián)的變量，則需要用復(fù)制語句進(jìn)行賦值。 ? 簡單的說， Q活躍就是指 Q定義的值被使用過。 尋址模式 ?變量 x：指向分配 x的內(nèi)存位置 ?a(r)：地址是 a的左值加上 r中的值 （可類比一維數(shù)組方便記憶） ?constant(r)：寄存器中內(nèi)容加上前面的常數(shù)即其地址； （可類比一維數(shù)組方便記憶） ?*r：寄存器 r的內(nèi)容為其地址 ?*constant(r)： r中內(nèi)容加上常量的和所指地址中存放的值為其地址 （可類比一維數(shù)組方便記憶） ?常量 constant56 例子 ?x=yz ? LD R1, y //R1=y ? LD R2, z //R2=x ? SUB R1, R1, R2 //R1=R1R2 ? ST x, R1 //x=R1 ?b=a[i] ? LR R1, i //R1=i ? MUL R1, R1, 8 //R1=R1*8 ? LD R2, a(R1) //R2=contents(a+contents(R1)) ? ST b, R2 //b = R2 程序及指令代價 ?不同的目的有不同的度量 ? 最短編譯時間、目標(biāo)程序大小、運(yùn)行時間、能耗