第八章代碼生成

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

2、LD dst, addr；把地址addr中的內(nèi)容加載到dst所指寄存器。addr：內(nèi)存地址/寄存器 保存：ST x, r；把寄存器r中的內(nèi)容保存到x中。 計算：OP dst, src1, src2；把src1和scr2中的值運算后將結(jié)果存放到dst中。 無條件跳轉(zhuǎn)：BR L；控制流轉(zhuǎn)向標號L的指令 條件跳轉(zhuǎn)：Bcond r, L；對r中的值進行測試，如果為真則轉(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程序及指令的代價 不同的目的有不同的度量 最短編譯時間、目標程序大小、運行時間、能耗 不可判定一個目標程序是否最優(yōu) 我們假設：每個指令有固定的代價，設定為1加上運算分量尋址模式的代價 LD R0, R1；代價為1 LD R0, M；代價是2

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

5、turn 活動記錄棧式分配 寄存器SP指向棧頂 第一個過程（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)用者減低棧指針例子名字的運行時刻地址 在三地址語句中使用名字（實際上是指向符號表條目）來引用變量 語句x=0 如果x分配在靜態(tài)區(qū)域，且靜態(tài)區(qū)開始位置為static。 static12 = 0ST

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

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

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

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

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

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

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

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

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

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

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

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

18、法逐個處理三地址指令代碼生成算法（2） x=y+z 調(diào)用getReg(x=y+z)，為x,y,z選擇寄存器Rx,Ry,Rz 查Ry的寄存器描述符，如果y不在Ry中則生成指令：LD Ry y(y表示存放y值的當前位置) 類似地，確定是否生成LD Rz,z 生成指令ADD Rx, Ry, Rz 復制語句：x=y getReg(x=y)總是為x和y選擇相同的寄存器 如果y不在Ry中，生成機器指令LD Ry, y 基本塊的收尾 如果變量x在出口處活躍，且x現(xiàn)在不在內(nèi)存，那么生成指令ST x, Rx。代碼生成算法（3） 代碼生成同時更新寄存器和地址描述符 處理普通指令時生成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時， 如果生成LD Ry y，按照第一個規(guī)則處理； 把x加入到Ry的寄存器描述符中（Ry存放了x和y的當前值）； 修改x的地址描述符，使它只包含Ry。例子（1） a、b、c、d在出口處活躍 t、u、v是局部臨時變量t = a - bu = a cv = t + ua = dd = v + u例子（2）例子（3）getReg函數(shù)（1） getReg的目標：減少LD/ST指令 任務：為運算分量和結(jié)果分配寄存器 為運算分量分配寄存器 如果已經(jīng)在某個寄存器中，不需要進行處理，選擇這個寄存器； 如果不在寄存器中，且有