目標(biāo)代碼生成課件

目標(biāo)代碼一般有以下三種形式：（1）能夠立即執(zhí)行的機器語言代碼，所有地址均已定位。（2）待裝配的機器語言模塊。當(dāng)需要執(zhí)行時，由連接裝入程序把它們和某些運行程序連接起來，轉(zhuǎn)換成能執(zhí)行的機器語言代碼。（3）匯編語言代碼，尚需經(jīng)過匯編程序匯編，轉(zhuǎn)換成可執(zhí)行的機器語言代碼。11.1基本問題11.1.1

目標(biāo)程序可執(zhí)行目標(biāo)模塊可重定位目標(biāo)模塊允許程序模塊分別編譯調(diào)用其它先前編譯好的程序模塊匯編語言程序免去編譯器重復(fù)匯編器的工作從教學(xué)角度，增加可讀性11.1

代碼生成器的設(shè)計中的問題11.1.2

指令的選擇 目標(biāo)機器指令系統(tǒng)的性質(zhì)決定了指令選擇的難易程度，指令系統(tǒng)的統(tǒng)一性和完備性是重要的因素 指令的速度和機器特點是另一些重要的因素11.1

代碼生成器的設(shè)計中的問題 若不考慮目標(biāo)程序的效率，指令的選擇是直截了當(dāng)?shù)?。三地址語句x:=y+z（x，y和z都是靜態(tài)分配）

MOV y, R0 /*把y裝入寄存器R0*/ ADD z, R0 /*z加到R0上*/ MOV R0, x /*把R0存入x中*/逐個語句地產(chǎn)生代碼，常常得到低質(zhì)量的代碼

11.1

代碼生成器的設(shè)計中的問題語句序列

a:=b+c d:=a+e的代碼如下MOV b, R0ADD c, R0MOV R0, aMOV a, R0ADD e, R0 MOV R0, d 11.1

代碼生成器的設(shè)計中的問題語句序列

a:=b+c d:=a+e的代碼如下MOV b, R0ADD c, R0MOV R0, aMOV a, R0 --多余的指令A(yù)DD e, R0 MOV R0, d 11.1

代碼生成器的設(shè)計中的問題語句序列

a:=b+c d:=a+e的代碼如下MOV b, R0ADD c, R0MOV R0, aMOV a, R0 --多余的指令A(yù)DD e, R0 --若a不再使用，第三條也MOV R0, d 多余11.1

代碼生成器的設(shè)計中的問題11.1.3寄存器分配 運算對象處于寄存器中的指令通常比運算對象處于內(nèi)存的指令要短一些，執(zhí)行也快一些寄存器分配

選擇駐留在寄存器中的一組變量寄存器指派

挑選變量要駐留的具體寄存器11.1

代碼生成器的設(shè)計中的問題11.1.4計算次序的選擇 某種計算次序可能會比其它次序需要較少的寄存器來保存中間結(jié)果11.2

目標(biāo)機器模型11.2.1目標(biāo)機器的指令系統(tǒng)采用模型機作為目標(biāo)機器二地址指令

op 目的,源 LD {源傳到目的} ADD {源加到目的} SUB {目的減去源}11.2

目標(biāo)機器模型指令實例

LD R0, M

ST R0,MSTR0,4(R1)

contents(4+contents(R1)) LDR0, *4(R0)

contents(contents(4+contents(R0)))

LD R0, #111.3

一個簡單的代碼生成器依次考慮基本塊的每個語句，為其產(chǎn)生代碼假定三地址語句的每種算符都有對應(yīng)的目標(biāo)機器算符假定計算結(jié)果留在寄存器中盡可能長的時間,

除非：該寄存器要用于其它計算，或者到基本塊結(jié)束11.3一個簡單的代碼生成器以基本塊為單位來生成代碼A:=(B+C)*D+EAssign.exe生成中間代碼P313復(fù)習(xí)局部優(yōu)化285頁關(guān)于優(yōu)化的說明11.3一個簡單的代碼生成器以基本塊為單位來生成代碼A:=(B+C)*D+ET1:=B+CT2:=T1*DA:=T2+E該目標(biāo)代碼的缺點？應(yīng)該如何改進？(1)LDR0,B(2)ADDR0,C(3)STR0T1(4)LDR0,T1(5)MULR0,D(6)STR0,T2(7)LDR0,T2(8)ADDR0,E(9)STR0,A11.3一個簡單的代碼生成器1待用信息、寄存器描述和地址描述目的：把基本塊內(nèi)還要被引用的變量盡量保存在寄存器內(nèi)做法：需要收集待用信息演示DaiYongXinXi.exe代碼生成時需要動態(tài)的寄存器描述和地址描述11.3一個簡單的代碼生成器在代碼生成過程中，需要跟蹤寄存器的內(nèi)容和名字的地址寄存器描述記住每個寄存器當(dāng)前存的是什么在任何一點，每個寄存器保存若干個(包括零個)名字的值名字的地址描述記住運行時每個名字的當(dāng)前值可以在哪個場所找到這個場所可以是寄存器、棧單元、內(nèi)存地址、甚至是它們的某個集合這些信息可以存于符號表中這兩個描述在代碼生成過程中是變化的。11.3一個簡單的代碼生成器2簡單的代碼生成算法對每個三地址語句x:=yopz調(diào)用函數(shù)getreg決定放yopz計算結(jié)果的場所L查看y的地址描述,確定y值當(dāng)前的一個場所y

.如果y的值還不在L中，產(chǎn)生指令MOVy

，L產(chǎn)生指令opz

，L，其中z

是z的當(dāng)前場所之一如果y和/或z的當(dāng)前值不再引用，在塊的出口也不活躍，并且還在寄存器中，那么修改寄存器描述11.3一個簡單的代碼生成器寄存器選擇函數(shù)函數(shù)getreg返回保存x:=yopz的x值的場所L如果名字y在R中，這個R不含其它名字的值,并且在執(zhí)行x:=yopz后y不再有下次引用，那么返回這個R作為L。否則，返回一個空閑寄存器，如果有的話否則，如果x在塊中有下次引用，或者op是必須用寄存器的算符，那么找一個已被占用的寄存器R(可能產(chǎn)生MOVR，M指令，并修改M的描述)否則，如果x在基本塊中不再引用，或者找不到適當(dāng)?shù)谋徽加眉拇嫫?，選擇x的內(nèi)存單元作為L。

11.3一個簡單的代碼生成器語

句

生成的代碼

寄存器描述名字地址描述

寄存器空

t1:=a

b

MOVa,R0SUBb,R0

R0含t1

t1在R0中

t2:=a

cMOVa,R1SUBc,R1R0含t1R1含t2t1在R0中t2在R1中t3:=t1+t2

ADDR1,R0

R0含t3

R1含t2

t3在R0中t2在R1中

d:=t3+t2

ADDR1,R0

R0含dd在R0中

MOVR0,d

d在R0和內(nèi)存中

11.4寄存器分配為了生成更有效的目標(biāo)代碼，需要考慮的一個問題就是如何更有效地利用寄存器。盡可能把各變量的現(xiàn)行值保存在寄存器中，把基本塊不再引用的變量所占用的寄存器及早釋放出來

11.4寄存器分配指令的執(zhí)行代價

每條指令的執(zhí)行代價=每條指令訪問主存單元次數(shù)十l。例如：

opRj，Rj

執(zhí)行代價為1opRj，M

執(zhí)行代價為2opRj，*Rj

執(zhí)行代價為2opRj，*M執(zhí)行代價為3

11.5DAG的目標(biāo)代碼為了生成更有效的目標(biāo)代碼，要考慮的另一個問題是，對基本塊中中間代碼序列，我們應(yīng)按怎樣的次序來生成其目標(biāo)代碼呢？演示DagCodeGen.exeDagCodeGenFigure11.9.exe練習(xí)11.2DagCodeGenExercise11.2.exeCodeGenExercise11.2Original.exeCodeGenExercise11.2DAGSorted.exe11.6窺孔優(yōu)化窺孔優(yōu)化（peepholeoptimization）

窺孔優(yōu)化方法是通過考察一小段目標(biāo)指令（稱為窺孔）并把這些指令替換為更短和更快的一段指令，從而提高目標(biāo)代碼的質(zhì)量。11.6窺孔優(yōu)化幾種典型的窺孔優(yōu)化技術(shù)冗余存取