編譯原理-課件中文chapter

第八章

代

碼

生

成

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

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

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

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

指令的選擇

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

指令的速度和機器特點是另一些重要的因素8.1

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

8.1

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

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

多余8.1

代碼生成器的設(shè)計中的問題8.1.3寄存器分配

運算對象處于寄存器中的指令通常比運算對象處于內(nèi)存的指令要短一些，執(zhí)行也快一些寄存器分配

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

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

代碼生成器的設(shè)計中的問題8.1.4計算次序的選擇某種計算次序可能會比其它次序需要較少的寄存器來保存中間結(jié)果尋找最優(yōu)的計算次序是一個NP-C問題8.2

目

標

機

器

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

op 源，目的

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

目

標

機

器

地址模式和它們的匯編語言形式及附加代價模式 形式

地址

附加代價絕對地址 M M 1寄存器 R R 0變址 c(R) c+contents(R) 1間接寄存器

*R contents(R) 0間接變址

*c(R)contents(c+contents(R))1直接量 #c (常數(shù))c

18.2

目

標

機

器

指令實例

MOV R0, M

MOV 4(R0), M

把contents(4+contents(R0))放到地址為M的地方去 MOV *4(R0), M

把contents(contents(4+contents(R0)))放到地址為M的地方去

MOV #1, R08.2

目

標

機

器

8.2.2指令的代價

指令代價：

1＋源地址模式的附加代價＋目的地址模式的附加代價 指令

代價

MOVR0，R1 1

MOVR5，M 2

ADD#1，R3 2

SUB4(R0),*12(R1) 38.2

目

標

機

器

a:=b+c， a、b和c都靜態(tài)分配內(nèi)存單元 MOVb,R0 ADDc,R0 代價=6 MOVR0,a不同的存儲位置導(dǎo)致不同的目標代碼代價8.2

目

標

機

器

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

目

標

機

器

a:=b+c， a、b和c都靜態(tài)分配內(nèi)存單元若R0，R1和R2分別含a，b和c的地址，則 MOV*R1,*R0 ADD*R2,*R0 代價=28.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 代價=38.3

基本塊和流圖8.3.1基本塊基本塊：連續(xù)的語句序列，控制流從它的開始進入，并從它的末尾離開基本塊內(nèi)部沒有停止或者分支流圖:基本塊+控制流信息t1:=a*at2:=a*bt3:=2*t2

t4:=t1+t3t5:=b*bt6:=t4+t58.3

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

t1:=a*b….L1:t2=……gotoL1;t1=…8.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)(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)B1B28.3

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

基本塊和流圖刪除局部公共子表達式

a:=b+c a:=b+c b:=ad b:=ad c:=b+c c:=b+c d:=ad d:=b刪除死代碼定值x:=y+z以后不再引用，則稱x為死變量8.3

基本塊和流圖交換相鄰的獨立語句

t1:=b

+c t2