第八章代碼生成本章內(nèi)容一個簡單的代碼生成算法涉及存儲管理，指令選擇，寄存器分配和計算次序選擇等基本問題前端代碼優(yōu)化器中間代碼源程序代碼生成器中間代碼目標程序

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

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

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

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

代碼生成器的設(shè)計中的問題 若不考慮目標程序的效率，指令的選擇是直截了當?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ì)量的代碼

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

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

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

a:=b+c d:=a+e的代碼如下MOV b, R0ADD c, R0MOV R0, aMOV a, R0 --多余的指令ADD e, R0 MOV R0, d

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

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

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

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

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

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

目標機器8.2.1目標機器的指令系統(tǒng)選擇可作為幾種微機代表的寄存器機器四字節(jié)組成一個字，有n個通用寄存器R0,R1,…,Rn-1。二地址指令

op 源，目的 MOV {源傳到目的} ADD {源加到目的} SUB {目的減去源}

目標機器地址模式和它們的匯編語言形式及附加代價模式 形式 地址 附加代價絕對地址 M M 1寄存器 R R 0變址 c(R) c+contents(R) 1間接寄存器*R contents(R) 0間接變址

*c(R) contents(c+contents(R))1直接量 #c c 1

目標機器指令實例

MOV R0, M

MOV 4(R0), M

contents(4+contents(R0)) MOV *4(R0), M

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

MOV #1, R0

目標機器8.2.2指令的代價 指令代價取成1加上它的源和目的地址模式的附加代價 指令 代價

MOVR0，R1 1

MOVR5，M 2

ADD#1， R3 2

SUB4(R0),*12(R1) 3

目標機器a:=b+c， a、b和c都靜態(tài)分配內(nèi)存單元 MOVb,R0 ADDc,R0 代價=6 MOVR0,a

目標機器a:=b+c， a、b和c都靜態(tài)分配內(nèi)存單元 MOVb,R0 ADDc,R0 代價=6 MOVR0,a MOVb,a ADDc,a 代價=6

目標機器a:=b+c， a、b和c都靜態(tài)分配內(nèi)存單元若R0，R1和R2分別含a，b和c的地址，則 MOV*R1,*R0 ADD*R2,*R0 代價=2

目標機器a:=b+c， a、b和c都靜態(tài)分配內(nèi)存單元若R0，R1和R2分別含a，b和c的地址，則 MOV*R1,*R0 ADD*R2,*R0 代價=2若R1和R2分別含b和c的值，并且b的值在這個賦值后不再需要，則 ADDR2,R1 MOVR1,a 代價=3

基本塊和流圖怎樣為三地址語句序列生成目標代碼？begin |(1) prod:=0 prod:=0; |(2) i:=1 i:=1; |(3) t1:=4*i dobegin |(4) t2:=a[t1] prod:=prod+a[i]*b[i];|(5) t3:=4*i i:=i+1 |(6) t4:=b[t3] endwhilei<=20 |(7) t5:=t2*t4

end |(8) t6:=prod+t5 |(9) prod:=t6 |(10) t7:=i+1 |(11) i:=t7

|(12) ifi<=20goto(3)

基本塊和流圖8.3.1基本塊基本塊：連續(xù)的語句序列，控制流從它的開始進入，并從它的末尾離開再用有向邊表示基本塊之間的控制流信息，就能得到程序的流圖

基本塊和流圖三地址語句序列的劃分基本塊首先確定所有的入口語句序列的第一個語句是入口語句能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)到的語句是入口語句緊跟在條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句后面的語句是入口語句每個入口語句到下一個入口語句之前的語句序列構(gòu)成一個基本塊

基本塊和流圖(1) prod:=0(2) i:=1(3) t1:=4*i(4) t2:=a[t1](5) t3:=4*i(6) t4:=b[t3](7) t5:=t2*t4

(8) t6:=prod+t5(9) prod:=t6(10) t7:=i+1(11) i:=t7(12) ifi<=20goto(3)(1)prod:=0(2)i:=1(3)t1:=4*i(4)t2:=a[t1](5)t3:=4*I(6)t4:=b[t3](7)t5:=t2*t4(8)t6:=prod+t5(9)prod:=t6(10)t7:=i+1(11)i:=t7(12)ifi<=20goto(3)B1B2

基本塊和流圖8.3.2基本塊的變換三地址語句x:=y+z引用y和z并對x定值一個名字的值在基本塊的某一點以后還要引用的話，我們說這個名字在該點是活躍的基本塊的等價兩個基本塊計算一組同樣的表達式這些表達式的值分別代表同樣的活躍名字的值有很多等價變換可用于基本塊局部變換全局變換

基本塊和流圖刪除局部公共子表達式 a:=b+c a:=b+c b:=ad b:=ad c:=b+c c:=b+c d:=ad d:=b刪除死代碼定值x:=y+z以后不再引用，則稱x為死變量

基本塊和流圖交換相鄰的獨立語句 t1:=b

+c t2:=x

+y t2:=x

+y t1:=b

+c當且僅當x和y都不是t1，b和c都不是t2

代數(shù)變換 x:=x+0 可以刪除

x:=x*1 可以刪除

x:=y**2 改成x:=y*y

基本塊和流圖8.3.3流圖 把控制流信息加到基本塊集合，形成一個有向圖來表示程序

首結(jié)點、前驅(qū)、后繼

基本塊和流圖什么是循環(huán)?所有結(jié)點是強連通的唯一的循環(huán)入口外循環(huán)和內(nèi)循環(huán)prod:=0i:=1t1:=4*it2:=a[t1]t3:=4*It4:=b[t3]t5:=t2*t4t6:=prod+t5prod:=t6t7:=i+1i:=t7ifi<=20gotoB2B1B2

基本塊和流圖8.3.4下次引用信息 為每個三地址語句x:=yopz決定x、y和z的下次引用信息

i: x:=yopz ... 沒有對x的賦值

j: …:=x…... 沒有對x的賦值

k: …:=…x

基本塊和流圖8.3.4下次引用信息 為每個三地址語句x:=yopz決定x、y和z的下次引用信息

i: x:=yopz ... 沒有對x的賦值

j: …:=x…... 沒有對x的賦值

k: …:=…x

基本塊和流圖對每個基本塊從最后一個語句反向掃描到第一個語句，可以得到下次引用信息

i: x:=yopz ... 沒有對x的賦值

j: …:=x…... 沒有對x的賦值

k: …:=…x

基本塊和流圖對每個基本塊從最后一個語句反向掃描到第一個語句，可以得到下次引用信息

i: x:=yopz ... 沒有對x的賦值

j: …:=x…... 沒有對x的賦值

k: …:=…x利用下次引用信息，可以壓縮臨時變量需要的空間

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

除非：該寄存器要用于其它計算，或者到基本塊結(jié)束

一個簡單的代碼生成器在沒有收集全局信息前，暫且以基本塊為單位來生成代碼prod:=0i:=1t1:=4*it2:=a[t1]t3:=4*It4:=b[t3]t5:=t2*t4t6:=prod+t5prod:=t6t7:=i+1i:=t7ifi<=20gotoB2B1B2

一個簡單的代碼生成器8.4.1寄存器描述和地址描述例：對a:=b+c如果寄存器Ri含b，Rj含c，且b此后不再活躍產(chǎn)生ADDRj,Ri，結(jié)果a在Ri中如果Ri含b，但c在內(nèi)存單元，b仍然不再活躍產(chǎn)生ADDc,Ri，或者MOVc,Rj ADDRj,Ri若c的值以后還要用,第二種代碼比較有吸引力

一個簡單的代碼生成器在代碼生成過程中，需要跟蹤寄存器的內(nèi)容和名字的地址寄存器描述記住每個寄存器當前存的是什么在任何一點，每個寄存器保存若干個(包括零個)名字的值名字的地址描述記住運行時每個名字的當前值可以在哪個場所找到這個場所可以是寄存器、棧單元、內(nèi)存地址、甚至是它們的某個集合這些信息可以存于符號表中這兩個描述在代碼生成過程中是變化的。

一個簡單的代碼生成器

代碼生成算法對每個三地址語句x:=yopz調(diào)用函數(shù)getreg決定放yopz計算結(jié)果的場所L查看y的地址描述,確定y值當前的一個場所y.如果y的值還不在L中，產(chǎn)生指令MOVy，L產(chǎn)生指令opz，L，其中z是z的當前場所之一如果y和/或z的當前值不再引用，在塊的出口也不活躍，并且還在寄存器中，那么修改寄存器描述

一個簡單的代碼生成器

寄存器選擇函數(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在基本塊中不再引用，或者找不到適當?shù)谋徽加眉拇嫫?，選擇x的內(nèi)存單元作為L。

一個簡單的代碼生成器賦值語句d:=(ab)+(ac)+(ac)編譯產(chǎn)生三地址語句序列： t1:=ab t2:=ac t3:=t1+t2 d:=t3+t2

一個簡單的代碼生成器語

句

生成的代碼

寄存器描述名字地址描述

寄存器空

t1:=ab

MOVa,R0SUBb,R0

R0含t1

t1在R0中

t2:=acMOVa,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)存中

一個簡單的代碼生成器前三條指令可以修改，使執(zhí)行代價降低MOVa,R0 MOVa,R0SUBb,R0 MOVR0，R1MOVa,R1 SUBb,R0SUBc,R1 SUBc,R1... ...

一個簡單的代碼生成器

為變址和指針語句產(chǎn)生代碼 變址與指針運算的三地址語句的處理和二元算符的處理相同

一個簡單的代碼生成器

條件語句實現(xiàn)條件轉(zhuǎn)移有兩種方式根據(jù)寄存器的值是否為下面六個條件之一進行分支：負、零、正、非負、非零和非正用條件碼來表示計算的結(jié)果或裝入寄存器的值是負、零還是正

一個簡單的代碼生成器根據(jù)寄存器的值是否為下面六個條件之一進行分支：負、零、正、非負、非零和非正例如：ifx<ygotoz把x減y的值存入寄存器R，如果R的值為負，則跳到z

一個簡單的代碼生成器用條件碼的例子ifx<ygotoz x:=y+z的實現(xiàn)： ifx<0gotozCMP x, y 的實現(xiàn)：CJ< z MOV y， R0 ADD z， R0 MOV R0，x CJ< z本章要點代碼生成器設(shè)計中的主要問題：存儲管理、計算次序的選擇、寄存器的分配、指令的選擇等。目標機器幾種常用的地址模式和一些常用的指令?；緣K和程序流圖。簡單的代碼生成算法。

例題1在SPARC/SUNOS上，經(jīng)某編譯器編譯，程序的結(jié)果是120。把第10行的abs(1)改成1的話，則程序結(jié)果是1intfact(){ staticinti=5; if(i==0){return(1);} else{i=i-1;return((i+abs(1))*fact());}}main(){ printf("factorof5=%d\n",fact());}例題2下面的程序在X86/Linux機器上編譯后的運行結(jié)果是7，而在SPARC/SUNOS機器上編譯后的運行結(jié)果是6。試分析運行結(jié)果不同的原因。main(){ longi; i=0; printf("%ld\n",(++i)+(++i)+(++i));}例題2按一般的代碼生成，i=i+1的計算結(jié)果保留在寄存器中，因此這三個i=i+1的計算次序不會影響最終的結(jié)果。結(jié)果應