第八章代碼生成

1、第八章 代碼生成南京大學(xué)計(jì)算機(jī)系趙建華代碼生成器的位置 根據(jù)中間表示生成代碼 代碼生成器之前可能有一個(gè)優(yōu)化組件 代碼生成器的三個(gè)任務(wù) 指令選擇：選擇適當(dāng)?shù)闹噶顚?shí)現(xiàn)IR語句 寄存器分配和指派：把哪個(gè)值放在哪個(gè)寄存器中 指令排序：按照什么順序安排指令執(zhí)行主要內(nèi)容 要解決的問題 機(jī)器模型 靜態(tài)/棧式數(shù)據(jù)區(qū)分配 基本塊相關(guān)的代碼生成 簡單的代碼生成算法 窺孔優(yōu)化要解決的問題 正確性：正確的機(jī)器指令 易于實(shí)現(xiàn)、測試和維護(hù) 輸入IR的選擇 四元式、三元式、字節(jié)代碼、堆棧機(jī)代碼、后綴表示、抽象語法樹、DAG圖、 輸出 RISC、CISC； 可重定向代碼、匯編語言目標(biāo)機(jī)模型 使用三地址機(jī)器的模型 指令 加載：

2、LD dst, addr；把地址addr中的內(nèi)容加載到dst所指寄存器。addr：內(nèi)存地址/寄存器 保存：ST x, r；把寄存器r中的內(nèi)容保存到x中。 計(jì)算：OP dst, src1, src2；把src1和scr2中的值運(yùn)算后將結(jié)果存放到dst中。 無條件跳轉(zhuǎn)：BR L；控制流轉(zhuǎn)向標(biāo)號(hào)L的指令 條件跳轉(zhuǎn)：Bcond r, L；對(duì)r中的值進(jìn)行測試，如果為真則轉(zhuǎn)向L。尋址模式 變量x：指向分配x的內(nèi)存位置 a(r)：地址是a的左值加上r中的值 constant(r)：寄存器中內(nèi)容加上前面的常數(shù)即其地址； *r：寄存器r的內(nèi)容為其地址 *constant(r)：r中內(nèi)容加上常量所指地址中存放的值

3、為其地址 常量#constant例子 x=y-z LDR1, y/R1=y LDR2, z/R2=x SUB R1, R1, R2/R1=R1-R2 STx, R1/x=R1 b=ai LRR1, I/R1=i MULR1, R1, 8/R1=R1*8 LDR2, a(R1)/R2=contents(a+contents(R1) STb, R2/b = R2程序及指令的代價(jià) 不同的目的有不同的度量 最短編譯時(shí)間、目標(biāo)程序大小、運(yùn)行時(shí)間、能耗 不可判定一個(gè)目標(biāo)程序是否最優(yōu) 我們假設(shè)：每個(gè)指令有固定的代價(jià)，設(shè)定為1加上運(yùn)算分量尋址模式的代價(jià) LD R0, R1；代價(jià)為1 LD R0, M；代價(jià)是2

4、 LD R1, *100(R2)；代價(jià)為2目標(biāo)代碼中的地址 如何將IR中的名字轉(zhuǎn)換成為目標(biāo)代碼中的地址 不同的區(qū)域中的名字采用不同的尋址方式。 如何為過程調(diào)用和返回生成代碼 靜態(tài)分配 棧式分配活動(dòng)記錄的靜態(tài)分配 每個(gè)過程靜態(tài)地分配一個(gè)數(shù)據(jù)區(qū)域，開始位置用staticArea表示 call callee的實(shí)現(xiàn) STcallee.staticArea, #here+20/存放返回地址 BRcallee.codeArea Callee中的語句return BR*callee.staticArea例子 三地址代碼 action1 call p action 2 halt/p的代碼 action3 re

5、turn 活動(dòng)記錄棧式分配 寄存器SP指向棧頂 第一個(gè)過程（main）初始化棧區(qū) 過程調(diào)用指令序列 ADD SP, SP, #caller.recordSize/增加棧指針 ST 0(SP), #here+16/保存返回地址 BR callee.codeArea/轉(zhuǎn)移到被調(diào)用者 返回指令序列 BR *0(SP)/被調(diào)用者執(zhí)行，返回調(diào)用者 SUP SP, SP, #caller.recordSize /調(diào)用者減低棧指針例子名字的運(yùn)行時(shí)刻地址 在三地址語句中使用名字（實(shí)際上是指向符號(hào)表?xiàng)l目）來引用變量 語句x=0 如果x分配在靜態(tài)區(qū)域，且靜態(tài)區(qū)開始位置為static。 static12 = 0ST

6、 112 #0 如果x分配在棧區(qū)，且相對(duì)地址為12，則 ST 12(SP) #0基本塊和流圖 中間代碼的流圖表示法 中間代碼劃分成為基本塊(basic block)。 控制流只能從第一個(gè)指令進(jìn)入 除基本塊的最后一個(gè)指令外，控制流不會(huì)跳轉(zhuǎn)/停機(jī) 流圖的結(jié)點(diǎn)是基本塊。流圖的邊指明了哪些基本塊可以跟在一個(gè)基本塊之后運(yùn)行 流圖可以作為優(yōu)化的基礎(chǔ) 它指出了基本塊之間的控制流 可以根據(jù)流圖了解到一個(gè)值是否會(huì)被使用等信息劃分基本塊的算法 輸入：三地址指令序列 輸出：基本塊的列表 方法： 確定leader指令（基本塊的第一個(gè)指令） 第一個(gè)三地址指令 任意一個(gè)條件或無條件轉(zhuǎn)移指令的目標(biāo)指令 緊跟在一個(gè)條件/無條

7、件轉(zhuǎn)移指令之后的指令 確定基本塊 每個(gè)首指令對(duì)應(yīng)于一個(gè)基本塊：從首指令開始到下一個(gè)首指令基本塊劃分的例子 第一個(gè)指令 1 跳轉(zhuǎn)指令的目標(biāo) 3、2、13 跳轉(zhuǎn)指令的下一條指令 10、12 基本塊： 1-1；2-2；3-9；10-11； 12-12；13-17后續(xù)使用信息 變量值的使用 三地址語句i向x賦值、如果j的運(yùn)算分量為x，且從i開始有一條路徑到達(dá)j，且路徑上沒有對(duì)x賦值，那么j就使用了i處計(jì)算得到的x的值。 我們說x在語句i后的程序點(diǎn)上活躍 即在程序執(zhí)行完語句i的時(shí)刻，x中存放的值將被后面的語句使用 不活躍是指變量中存放的值不會(huì)被使用，而不是變量不會(huì)被使用； 這些信息可以用于代碼生成 如果

8、x在i處不活躍，且x占用了一個(gè)寄存器，我們可以把這個(gè)寄存器用于其它目的。確定基本塊中的活躍性、后續(xù)使用 輸入：基本塊B，開始時(shí)B的所有非臨時(shí)變量都是活躍的； 輸出：各個(gè)語句i上的變量的活躍性、后續(xù)使用信息 方法： 從B的最后一個(gè)語句開始反向掃描 對(duì)于每個(gè)語句i：x=y+z。 令語句i和x、y、z的當(dāng)前活躍性信息/使用信息關(guān)聯(lián) 設(shè)置x為不活躍、無后續(xù)使用 設(shè)置y和z為活躍，并指明它們的下一次使用為語句i例子 假設(shè)i,j,a不是臨時(shí)變量。它們?cè)诔隹谔幓钴S，其余變量不活躍 在8之前的程序點(diǎn)上，i,j,a仍然活躍；且j在8上被使用 在7之前的程序點(diǎn)上，i,j,a,t4活躍；且t4被7使用； 在6之前的

9、程序點(diǎn)上，i,j,a,t3活躍，t4不活躍，t3被6使用； 在5之前的程序點(diǎn)上，i,j,a,t2活躍，t3不活躍； 在4之前的程序點(diǎn)上，流圖的構(gòu)造 流圖的頂點(diǎn)是基本塊 兩個(gè)頂點(diǎn)B和C之間有一條有向邊 iff 基本塊C的第一個(gè)指令可能在B的最后一個(gè)指令之后執(zhí)行。 存在邊的原因： 從B的結(jié)尾指令是一條跳轉(zhuǎn)到C的開頭的條件/無條件語句 在原來的序列中，C緊跟在B之后，且B的結(jié)尾不是無條件跳轉(zhuǎn)語句 我們稱B是C的前驅(qū)，C是B的后繼 入口，出口結(jié)點(diǎn) 流圖中額外添加的邊，不對(duì)應(yīng)于中間代碼（基本塊）對(duì)應(yīng) 入口到第一條指令有一條邊 從任何可能最后執(zhí)行的基本塊到出口有一條邊流圖的例子 因跳轉(zhuǎn)而生成的邊 B3B3

10、 B4B2 B6B6 因?yàn)轫樞蚨傻倪?其它循環(huán) 程序的大部分運(yùn)行時(shí)間花費(fèi)在循環(huán)上 因此循環(huán)是識(shí)別的重點(diǎn) 循環(huán)的定義 循環(huán)L是一個(gè)結(jié)點(diǎn)集合 存在一個(gè)循環(huán)入口（loop entry）結(jié)點(diǎn)。是唯一的、前驅(qū)可以在循環(huán)L之外的結(jié)點(diǎn)，到達(dá)其余結(jié)點(diǎn)的路徑必然先進(jìn)國這個(gè)入口結(jié)點(diǎn)； 其余結(jié)點(diǎn)都存在到達(dá)入口結(jié)點(diǎn)的非空路徑，且路徑都在L中。循環(huán)的例子 循環(huán) B3 B6 B2,B3,B4 對(duì)于B2,B3,B4的解釋 B2為入口結(jié)點(diǎn) B1，B5，B6不在循環(huán)內(nèi)的理由 到達(dá)B1可不經(jīng)過B2 B5，B6沒有到達(dá)B2的結(jié)點(diǎn)基本塊的優(yōu)化 針對(duì)基本塊的優(yōu)化可以有很好的效果 基本塊中各個(gè)指令要么都執(zhí)行，要么都不執(zhí)行 基本塊可以

11、用DAG圖表示 每個(gè)變量對(duì)應(yīng)于DAG圖的結(jié)點(diǎn)，代表初始值； 每個(gè)語句s有一個(gè)相關(guān)的結(jié)點(diǎn)N，代表計(jì)算得到的值 N的子結(jié)點(diǎn)對(duì)應(yīng)于（其運(yùn)算分量當(dāng)前值的）其它語句。 結(jié)點(diǎn)N的標(biāo)號(hào)是s的運(yùn)算符 N和一組變量關(guān)聯(lián)，表示s是在此基本塊內(nèi)最晚對(duì)它們定值的語句。 輸出結(jié)點(diǎn)：結(jié)點(diǎn)對(duì)應(yīng)的變量在基本塊出口處活躍 從DAG圖，我們可以知道各個(gè)變量最后的值和初始值的關(guān)系；DAG圖的構(gòu)造 為基本塊中出現(xiàn)的每個(gè)變量建立結(jié)點(diǎn)（表示初始值），各變量和相應(yīng)結(jié)點(diǎn)關(guān)聯(lián) 順序掃描各個(gè)三地址指令，進(jìn)行如下處理： 如果指令為x=y op z 為這個(gè)指令建立結(jié)點(diǎn)N，標(biāo)號(hào)為op； N的子結(jié)點(diǎn)為y、z當(dāng)前關(guān)聯(lián)的結(jié)點(diǎn)； 令x和N關(guān)聯(lián)； 如果指令為x

12、=y； 不建立新結(jié)點(diǎn)； 設(shè)y關(guān)聯(lián)到N，那么x現(xiàn)在也關(guān)聯(lián)到N 掃描結(jié)束后，對(duì)于所有在出口處活躍的變量x，將x所關(guān)聯(lián)的結(jié)點(diǎn)設(shè)置為輸出結(jié)點(diǎn)例子 指令序列 a=b+c b=a-d c=b+c 過程： 結(jié)點(diǎn)b0，c0和d0對(duì)應(yīng)于b，c和d的初始值；它們和相應(yīng)結(jié)點(diǎn)關(guān)聯(lián)； a=b+c: 構(gòu)造第一個(gè)加法結(jié)點(diǎn)，a與之關(guān)聯(lián) b=a-d：構(gòu)造減法結(jié)點(diǎn)，b與之關(guān)聯(lián) c=b+c：構(gòu)造第二個(gè)加法結(jié)點(diǎn)，c與之關(guān)聯(lián)（注意第一個(gè)子結(jié)點(diǎn)對(duì)應(yīng)于減法結(jié)點(diǎn)） 如果還有第四條指令c=a，流圖會(huì)如何處理？DAG的作用 DAG圖描述了基本塊運(yùn)行時(shí)各變量的值（和初始值）之間的關(guān)系。 我們可以以DAG為基礎(chǔ)，對(duì)代碼進(jìn)行轉(zhuǎn)換 消除局部公共子表達(dá)式

13、 消除死代碼 對(duì)語句重新排序 重新排序運(yùn)算分量的順序局部公共子表達(dá)式 局部公共子表達(dá)式的發(fā)現(xiàn) 建立某個(gè)結(jié)點(diǎn)M之前，首先檢查是否存在一個(gè)結(jié)點(diǎn)N，它和M具有相同的運(yùn)算符和子結(jié)點(diǎn)（順序也相同）。 如果存在，則不需要生成新的結(jié)點(diǎn)，用N代表M； 例如： a=b+c b=a-d c=b+c d=a-d 注意：兩個(gè)b+c實(shí)際上并不是公共子表達(dá)式消除死代碼 在DAG圖上消除沒有附加活躍變量的根結(jié)點(diǎn)（沒有父結(jié)點(diǎn)的結(jié)點(diǎn)），即消除死代碼 如果圖中c、e不是活躍變量，則可以刪除標(biāo)號(hào)為e、c的結(jié)點(diǎn)。應(yīng)用代數(shù)恒等式的優(yōu)化 消除計(jì)算步驟 x+0=0+x=xx-0=x x*1=1*x=xx/1=x 降低計(jì)算強(qiáng)度 X2=x*x

14、2*x=x+x 常量合并 2*3.14可以用6.28替換 實(shí)現(xiàn)這些優(yōu)化時(shí)，只需要在DAG圖上尋找特定的模式數(shù)組引用 注意：aj可能改變ai的值，因此不能和普通的運(yùn)算符一樣構(gòu)造相應(yīng)的結(jié)點(diǎn) x=ai aj=y z=ai 從數(shù)組取值的運(yùn)算x=ai對(duì)應(yīng)于=的結(jié)點(diǎn)，x作為這個(gè)結(jié)點(diǎn)的標(biāo)號(hào)之一； 對(duì)數(shù)組賦值的運(yùn)算對(duì)應(yīng)于=的結(jié)點(diǎn)；沒有關(guān)聯(lián)的變量、且殺死所有依賴于a的變量；數(shù)組引用的DAG的例子 設(shè)a是數(shù)組，b是指針 b=12+a x=bi bj=y 注意a是被殺死的結(jié)點(diǎn)的孫結(jié)點(diǎn) 一個(gè)結(jié)點(diǎn)被殺死，意味著它不能被復(fù)用 考慮再有指令m=bi?指針賦值/過程調(diào)用 通過指針進(jìn)行取值/賦值：x=*p *q=y。最粗略地估

15、計(jì)： x使用了任意變量，因此無法消除死代碼 而*q=y對(duì)任意變量賦值，因此殺死了全部其他結(jié)點(diǎn) 可以通過（全局/局部）指針分析部分解決這個(gè)問題； 過程調(diào)用也類似，必須安全地假設(shè)它 使用了可訪問范圍內(nèi)的所有變量 修改了可訪問范圍內(nèi)的所有變量從DAG到基本塊 重構(gòu)的方法 每個(gè)結(jié)點(diǎn)構(gòu)造一個(gè)三地址語句，計(jì)算對(duì)應(yīng)的值 結(jié)果應(yīng)該盡量賦給一個(gè)活躍的變量 如果結(jié)點(diǎn)有多個(gè)關(guān)聯(lián)的變量，則需要用復(fù)制語句進(jìn)行賦值。重組基本塊的例子 根據(jù)DAG構(gòu)造是結(jié)點(diǎn)產(chǎn)生的順序 a=b+c d=a-d b=d c=d+c重組的規(guī)則 重組時(shí)應(yīng)該注意求值的順序 指令的順序必須遵守DAG中結(jié)點(diǎn)的順序 對(duì)數(shù)組的賦值必須跟在所有原來在它之前的賦

16、值/求值操作之后 對(duì)數(shù)組元素的求值必須跟在所有原來在它之前的賦值指令之后 對(duì)變量的使用必須跟在所有原來在它之前的過程調(diào)用和指針間接賦值之后 任何過程調(diào)用或者指針間接賦值必須跟在原來在它之前的變量求值之后。 總的來說，我們必須保證：如果兩個(gè)指令之間可能相互影響，那么他們的順序就不應(yīng)該改變。代碼生成器 根據(jù)三地址指令序列生成機(jī)器指令 假設(shè)：每個(gè)三地址指令只有一個(gè)對(duì)應(yīng)的機(jī)器指令 有一組寄存器用于計(jì)算基本塊內(nèi)部的值； 主要的目標(biāo)是盡量減少加載和保存指令，即最大限度利用寄存器； 寄存器的使用方法 執(zhí)行運(yùn)算時(shí)，運(yùn)算分量必須放在寄存器中； 用于臨時(shí)變量 存放全局的值 進(jìn)行運(yùn)行時(shí)刻管理（比如：棧頂指針）算法的

17、基本思想的數(shù)據(jù)結(jié)構(gòu) 依次考慮各三地址指令，盡可能把值保留在寄存器中，以減少寄存器/內(nèi)存之間的數(shù)據(jù)交換 為一個(gè)三地址指令生成機(jī)器指令時(shí)， 只有當(dāng)運(yùn)算分量不在寄存器中時(shí)，才從內(nèi)存載入； 盡量保證只有當(dāng)寄存器中的值不被使用時(shí)，才把它覆蓋掉。 數(shù)據(jù)結(jié)構(gòu)：記錄各個(gè)值對(duì)應(yīng)的位置 寄存器描述符：跟蹤各個(gè)寄存器都存放了哪些變量的當(dāng)前值； 地址描述符：某個(gè)變量的當(dāng)前值存放在哪個(gè)或哪些位置(包括內(nèi)存位置和寄存器）上；代碼生成算法（1） 重要子函數(shù)：getReg(I) 根據(jù)寄存器描述符和地址描述符、數(shù)據(jù)流信息，為三地址指令I(lǐng)選擇最佳的寄存器； 得到的機(jī)器指令的質(zhì)量依賴于getReg函數(shù)選取寄存器的算法； 代碼生成算

18、法逐個(gè)處理三地址指令代碼生成算法（2） x=y+z 調(diào)用getReg(x=y+z)，為x,y,z選擇寄存器Rx,Ry,Rz 查Ry的寄存器描述符，如果y不在Ry中則生成指令：LD Ry y(y表示存放y值的當(dāng)前位置) 類似地，確定是否生成LD Rz,z 生成指令A(yù)DD Rx, Ry, Rz 復(fù)制語句：x=y getReg(x=y)總是為x和y選擇相同的寄存器 如果y不在Ry中，生成機(jī)器指令LD Ry, y 基本塊的收尾 如果變量x在出口處活躍，且x現(xiàn)在不在內(nèi)存，那么生成指令ST x, Rx。代碼生成算法（3） 代碼生成同時(shí)更新寄存器和地址描述符 處理普通指令時(shí)生成LD R x R的寄存器描述符

19、：只包含x x的地址描述符：R作為新位置加入到x的位置集合中 從任何不同于x的變量的地址描述符中刪除R ST x, R 修改x的地址描述符，包含自己的內(nèi)存位置代碼生成算法（4） ADD Rx, Ry, Rz Rx的寄存器描述符只包含x x的地址描述符只包含Rx（不包含x的內(nèi)存位置?。?從任何不同于x的變量的地址描述符中刪除Rx。 處理x=y時(shí)， 如果生成LD Ry y，按照第一個(gè)規(guī)則處理； 把x加入到Ry的寄存器描述符中（Ry存放了x和y的當(dāng)前值）； 修改x的地址描述符，使它只包含Ry。例子（1） a、b、c、d在出口處活躍 t、u、v是局部臨時(shí)變量t = a - bu = a cv = t + ua = dd = v + u例子（2）例子（3）getReg函數(shù)（1） getReg的目標(biāo)：減少LD/ST指令 任務(wù)：為運(yùn)算分量和結(jié)果分配寄存器 為運(yùn)算分量分配寄存器 如果已經(jīng)在某個(gè)寄存器中，不需要進(jìn)行處理，選擇這個(gè)寄存器； 如果不在寄存器中，且有