編譯方法、技術(shù)與實踐課件：中間代碼生成（二）

中間代碼生成(二)?中間表示?類型與聲明?表達(dá)式的翻譯?控制流與回填運行時刻環(huán)境?靜態(tài)類型檢查和中間代碼生成的過程都可以用語法制導(dǎo)的翻譯來描述和實現(xiàn)?對于抽象語法樹這種中間表示的生成，

第五章已經(jīng)介紹過編譯器前端的邏輯結(jié)構(gòu)?每條指令右側(cè)最多有一個運算符O

一般情況可以寫成x=y

op

z?允許的運算分量O

名字：源程序中的名字作為三地址代碼的地址O

常量：源程序中出現(xiàn)或生成的常量O

編譯器生成的臨時變量三地址代碼(1)?指令集合

(1)O

運算/賦值指令：x=y

op

z

x

=opyO復(fù)制指令：x=yO

無條件轉(zhuǎn)移指令：gotoLO

條件轉(zhuǎn)移指令：if

x

goto

L

ifFalsexgoto

LO

條件轉(zhuǎn)移指令：if

x

relop

ygotoL三地址代碼(2)?指令集合(2)O

過程調(diào)用/返回?param

x1//設(shè)置參數(shù)?

paramx2?

…?

paramxn?call

p,n//調(diào)用子過程p，n為參數(shù)個數(shù)O

帶下標(biāo)的復(fù)制指令：x=y[i]x[i]=y?注意：i表示離開數(shù)組位置第i個字節(jié)，而不是數(shù)組的第i個元素O

地址/指針賦值指令：三地址代碼(3)?

x=&yx=*y*x=y?語句O

do

i=i+1;while(a[i]<v)；三地址代碼實例?在實現(xiàn)時，可以使用四元式/三元式/間接三元式來表示三地址指令?四元式：可以實現(xiàn)為紀(jì)錄(或結(jié)構(gòu))?格式(字段)：op

arg1arg2resultO

op:運算符的內(nèi)部編碼O

arg1,arg2,result是地址O

x=y+z+y

z

x?單目運算符不使用arg2?param運算不使用arg2和result?條件轉(zhuǎn)移/非條件轉(zhuǎn)移將目標(biāo)標(biāo)號放在result字段三地址指令的四元式表示方法?賦值語句：a=b*-c+b*-c四元式的例子?三元式(triple)op

arg1arg2?使用三元式的位置來引用三元式的運算結(jié)果?x[i]=y需要拆分為兩個三元式O

求x[i]的地址，然后再賦值?x=y

op

z需要拆分為(這里？是編號)O

(?)op

y

zO

=x

??問題：在優(yōu)化時經(jīng)常需要移動/刪除/添加三元式，導(dǎo)致三元式的移動三元式表示三元式的例子?包含了一個指向三元式的指針的列表?我們可以對這個列表進(jìn)行操作，完成優(yōu)化功能；操作時不需要修改三元式中的參數(shù)間接三元式?SSA中的所有賦值都是針對不同名的變量?對于同一個變量在不同路徑中定值的情況，可以使用φ函數(shù)來合并不同的定值O

if(flag)x=-1;else

x=1;y

=x*aO

if(flag)x1=-1;else

x2

=1;x3=φ(x1,x2)；靜態(tài)單賦值(SSA)y=x3*a?語法樹中，公共子表達(dá)式每出現(xiàn)一次，就有一個對應(yīng)的子樹?表達(dá)式的有向無環(huán)圖(Directed

AcyclicGraph,DAG)能夠指出表達(dá)式中的公共子表達(dá)式，更簡潔地表示表達(dá)式表達(dá)式的有向無環(huán)圖?可以用和構(gòu)造抽象語法樹一樣的SDD來構(gòu)造DAG構(gòu)造?

不同的處理O

在函數(shù)Leaf和Node每次被調(diào)用時，構(gòu)造新節(jié)點前先檢查是否已存在同樣的節(jié)點，如果已經(jīng)存在，則返回這個已有的節(jié)點DAG構(gòu)造?

構(gòu)造過程示例?中間表示?類型與聲明?表達(dá)式的翻譯?控制流與回填運行時刻環(huán)境?類型檢查(TypeChecking)O

利用一組規(guī)則來檢查運算分量的類型和運算符的預(yù)期類型是否匹配?類型信息的用途O

查錯、確定名字需要的內(nèi)存空間、計算數(shù)組元素的地址、類型轉(zhuǎn)換、選擇正確的運算符?主要內(nèi)容O

確定名字的類型O

變量的存儲空間布局(相對地址)類型和聲明?類型系統(tǒng)O

給每一個組成部分賦予一個類型表達(dá)式O

通過一組邏輯規(guī)則來表示這些類型表達(dá)式必須滿足的條件?可發(fā)現(xiàn)錯誤、提高代碼效率、確定臨時變量的大小…類型檢查和轉(zhuǎn)換?類型綜合O

根據(jù)子表達(dá)式的類型構(gòu)造出表達(dá)式的類型if

f的類型為st

t且x的類型為sthen

f(x)的類型為t?類型推導(dǎo)O

根據(jù)語言結(jié)構(gòu)的使用方式來確定該結(jié)構(gòu)的類型：if

f(x)是一個表達(dá)式then對于某些類型α,β；f的類型為αtβ且x的類類型系統(tǒng)的分類型為α?假設(shè)在表達(dá)式x*i中，x為浮點數(shù)、i為整數(shù)，則結(jié)果應(yīng)該是浮點數(shù)O

x和i使用不同的二進(jìn)制表示方式O

浮點*和整數(shù)*使用不同的指令?t1=(float)i?t2=xfmult1?類型轉(zhuǎn)換比較簡單時的SDDO

E

t

E1+E2{if(E1.type=integer

and

E2.type=integer)E.type

=integer;else

if(E1.type=float

and

E2.type=integer)E.type

=float;}O

這個規(guī)則沒有考慮生成類型轉(zhuǎn)換代碼類型轉(zhuǎn)換?編譯器自動完成的轉(zhuǎn)換為隱式轉(zhuǎn)換，程序員用代碼指定的轉(zhuǎn)換為顯式轉(zhuǎn)換類型的widening和narrowing?函數(shù)Max求的是兩個參數(shù)在拓寬層次結(jié)構(gòu)中

的最小公共祖先?Widen函數(shù)已經(jīng)生成了

必要的類型轉(zhuǎn)換代碼處理類型轉(zhuǎn)換的SDT?通過查看參數(shù)來解決函數(shù)重載問題?E

t

f(E1){if

f.typeset={si

t

ti

|1<=i<=k}

andE1.type=skthen

E.type=

tk函數(shù)/運算符的重載}?類型表達(dá)式(type

expression)：表示類型的結(jié)構(gòu)O

基本類型O

類名O

類型構(gòu)造算子作用于類型?array[數(shù)字，類型表達(dá)式]?record[字段/類型對的列表](可以用符號表表示)O

函數(shù)類型構(gòu)造算子t

：參數(shù)類型t結(jié)果類型O笛卡爾積：sX

tO

可以包含取值為類型表達(dá)式的變量類型表達(dá)式?類型例子O

元素個數(shù)為3X4的二維數(shù)組O

數(shù)組的元素的記錄類型O

該記錄類型中包含兩個字段:

x和y,其類型分別是float和integer?類型表達(dá)式O

array[3,

array[4,record[(x,float),(y,integer)]]]類型表達(dá)式的例子?不同的語言有不同的類型等價的定義?結(jié)構(gòu)等價O

或者它們是相同的基本類型O

或者是相同的構(gòu)造算子作用于結(jié)構(gòu)等價的類型而得到的。O

或者一個類型是另一個類型表達(dá)式的名字?名等價O

類型名僅僅代表其自身類型等價?變量的類型可以確定變量需要的內(nèi)存O

即類型的寬度O

可變大小的數(shù)據(jù)結(jié)構(gòu)只需要考慮指針?函數(shù)的局部變量總是分配在連續(xù)的區(qū)間O

因此給每個變量分配一個相對于這個區(qū)間開始處的相對地址?變量的類型信息保存在符號表中局部變量名的存儲布局計算類型和寬度的SDT?綜合屬性：type,width?全局變量t和w用于將類型和寬度信息從B傳遞到C

t

εO

相當(dāng)于C的繼承屬性，因為總是通過拷貝來傳遞，所以在SDT中只賦值一次，也可以把t和w替換為C.t和C.w計算類型和寬度的SDT?綜合屬性：type,width?全局變量t和w用于將類型和寬度信息從B傳遞到C→εO

相當(dāng)于C的繼承屬性，因為總是通過拷貝來傳遞，所以在SDT中只賦值一次，也可以把t和w替換為C.t和C.w計算類型和寬度的SDTSDT運行的例子?輸入：int[2][3]?含義O

D生成一個聲明列表O

T生成不同的類型O

B生成基本類型int/floatO

C表示分量，生成[num]序列O

注意record中包含了各個字段的聲明，字段聲明

和變量聲明的文法一致?文法聲明?除了確定類型和類型寬度，還有什么語義需要處理？O

符號表中的位置聲明序列的SDT?在處理一個過程/函數(shù)時，局部變量應(yīng)該放到單獨的符號表中去?這些變量的內(nèi)存布局獨立O

相對地址從0開始O

假設(shè)變量的放置和聲明的順序相同?SDT的處理方法O

變量offset記錄當(dāng)前可用的相對地址O每“分配”一個變量，offset的值增加相應(yīng)的值?top.put(id.lexeme,T.type,offset)O

在當(dāng)前符號表(位于棧頂)中創(chuàng)建符號表條目，記錄標(biāo)識符的類型，偏移量聲明序列的SDT

(1)?我們可以把offset看作D的繼承屬性O(shè)

D.offset表示D中第一個變量的相對地址O

P

t

{D.offset=0}

DO

D

t

T

id;{D1.offset=D.offset

+T.width;}

D1聲明序列的SDT

(2)?Ttrecord‘{‘D‘}’?為每個記錄創(chuàng)建單獨的符號表O

首先創(chuàng)建一個新的符號表，壓到棧頂O

然后處理對應(yīng)于字段聲明的D，字段都被加入到新符號表中O最后根據(jù)棧頂?shù)姆柋順?gòu)造出record類型表達(dá)式；

符號表出棧記錄字段的處理?中間表示?類型與聲明?表達(dá)式的翻譯?控制流與回填運行時刻環(huán)境?將表達(dá)式翻譯成三地址指令序列?表達(dá)式的SDDO

屬性code表示代碼O

addr表示存放表達(dá)式結(jié)果的地址

(臨時變量)O

new

Temp()可以生成一個臨時變量O

gen(…)生成一個指令表達(dá)式代碼的SDD表達(dá)式代碼的SDD?主屬性code滿足增量式翻譯的條件?

注意O

top.get(…)從棧頂符號表開始，逐個向下尋找id的信息O

這里的gen發(fā)出相應(yīng)的代碼增量式翻譯方案?數(shù)組元素存儲在一塊連續(xù)的存儲空間中，以方便快速的訪問它們?n個數(shù)組元素是0,1,…,n-1進(jìn)行順序編號的?假設(shè)每個數(shù)組元素寬度是w，那么數(shù)組A的第i個元素的開始地址為base+i*w,base是A[0]的相對地址。?推廣到二維或多維數(shù)組。A[i1][i2]表示第i1行第i2個

元素。假設(shè)一行的寬度是w1

，同一行中每個元素

的寬度是w2

，

A[i1][i2]的相對地址是base+i1

*w1+i2

*w2?

對于k維數(shù)組A[i1][i2]…[ik]，推廣Obase+i1

*w1+i2

*w2+…+ik

*wk數(shù)組元素的尋址?根據(jù)第j維上的數(shù)組元素的個數(shù)nj和該數(shù)組每個元素的寬度w進(jìn)行計算的，如二維數(shù)組A[i1][i2]的地址base+(i1

*n2+i2)*w?于k維數(shù)組A[i1][i2]…[ik]的地址base+((…(i1

*n2+i2)*n3+i3)…)*nk+ik)*w?有時下標(biāo)不一定從0開始，比如一維數(shù)組編號low,low+1,…,high，此時base是A[low]的相對地址。計算A[i]的地址變成base+(i-low)*w?預(yù)先計算技術(shù)O

改寫成i*w+c的形式，其中c=base-low*w可以在編譯時刻預(yù)先計算出來，計算A[i]的相對地址只要計算i*w再加上c就可以了數(shù)組元素的尋址(續(xù))

?按行存放策略和按列存放策略可以推廣到多維數(shù)組中數(shù)組元素的尋址(續(xù))?上述地址的計算是按行存放的?為數(shù)組引用生成代碼要解決的主要問題O

數(shù)組引用的文法和地址計算相關(guān)聯(lián)?假定數(shù)組編號從0開始，基于寬度來計算相對地址?數(shù)組引用相關(guān)文法O

非終結(jié)符號L生成一個數(shù)組名字加上一個下標(biāo)表達(dá)式序列數(shù)組引用的翻譯?非終結(jié)符號L的三個綜合屬性O(shè)

L.addr指示一個臨時變量，計算數(shù)組引用的偏移量O

L.array是一個指向數(shù)組名字對應(yīng)的符號表條

目的指針，L.array.base為該數(shù)組的基地址O

L.type是L生成的子數(shù)組的類型，對于任何數(shù)

組類型t，其寬度由t.width給出，t.elem給出其數(shù)組元素的類型數(shù)組引用生成代碼的翻譯方案數(shù)組引用生成代碼的翻譯方案核心是確定數(shù)組引用的地址?

基于數(shù)組引用的翻譯方案，表達(dá)式c+a[i][j]的注釋語法樹及三地址代碼序列?假設(shè)a是一個2*3的整數(shù)數(shù)組，c、i、j都是整數(shù)O

那么a的類型是array(2,array(3,integer)),a的寬度是24O

a[i]的類型是array(3,integer)，寬度是12O

a[i][j]的類型是整型數(shù)組引用翻譯示例?中間表示?類型與聲明?表達(dá)式的翻譯?控制流與回填運行時刻環(huán)境?if-else語句，while語句?翻譯目標(biāo)：控制流語句翻譯?if-else語句，while語句?需要將語句的翻譯和布爾表達(dá)式的翻譯結(jié)合在一起?布爾表達(dá)式是被用作語句中改變控制流的條件表達(dá)式，通常用來O

改變控制流。布爾表達(dá)式的值由程序到達(dá)的某個位置隱含地指出。O

計算邏輯值?？梢允褂脦в羞壿嬤\算符的三地址指令進(jìn)行求值。?布爾表達(dá)式的使用意圖要根據(jù)其語法上下文確定O

跟在關(guān)鍵字if后面的表達(dá)式用來改變控制流O

一個賦值語句右部的表達(dá)式用來計算一個邏輯值O

可以使用兩個不同的非終結(jié)符號或其它方法來區(qū)分這兩種使用控制流語句翻譯?將布爾運算符作用在布爾變量或關(guān)系表達(dá)式上，構(gòu)成布爾表

達(dá)式?引入新的非終結(jié)符號B表示布爾表達(dá)式?布爾運算符:&&、||、

!?關(guān)系表達(dá)式E1rel

E2?關(guān)系運算符：<、<=、=、!=、>、>=?其中布爾運算符&&和||是左結(jié)合的，優(yōu)先級||最低，其次是&&，！最高?表示布爾表達(dá)式的文法布爾表達(dá)式?B1||B2,B1為真，則不用求B2也能斷定整個表達(dá)式為真?B1&&B2,B1為假，則整個表達(dá)式肯定為假?如果某些程序設(shè)計語言允許這種高效的求值方式，則編譯器可以優(yōu)化布爾表達(dá)式的求值過程，只要已經(jīng)求值部分足以確定整個表達(dá)式的值就可以了。布爾表達(dá)式的高效求值?布爾運算符&&、||、!被翻譯成跳轉(zhuǎn)指令。

由跳轉(zhuǎn)位置隱含的指出布爾表達(dá)式的值。?if(x<100||x>200&&x!=y)x=0;短路(跳轉(zhuǎn))代碼?B和S有綜合屬性code，表示翻譯得到的三地址代碼。?B的繼承屬性true和false

，S的繼承屬性next，表示跳轉(zhuǎn)

的位置。?

S.true是一個地址，用于存放了B為真時控制流轉(zhuǎn)向的指令標(biāo)號，S.false同理?S.next也是一個地址，用于存放緊跟在S代碼之后的指控制流語句翻譯?

語句及文法令標(biāo)號?B和S有綜合屬性code，表示翻譯得到的三地址代碼。?B的繼承屬性true和false

，S的繼承屬性next，表示跳轉(zhuǎn)控制流語句翻譯?

語句及文法的位置。?幾個核心函數(shù)回顧：O

newlabel

函數(shù)：生成一個用于存放標(biāo)號的臨

時變量L，返回變量地址；O

label(X)函數(shù)：將下一條指令的標(biāo)號復(fù)制給參控制流語句翻譯分析數(shù)X；翻譯S→if(B)S1,創(chuàng)建B.true標(biāo)號，并指向S1的第一條指令。

翻譯S→if(B)S1else

S2,B為

真時，跳轉(zhuǎn)到S1代碼的第一條指令；當(dāng)B為假時跳轉(zhuǎn)到S2代碼的第一條指令。然后，控制流從S1或S2轉(zhuǎn)到緊跟在S的代碼后面的三地址指令，該指令由繼承屬性S.next指定。while語句中有個begin局部變量……控制流語句翻譯分析????布爾表達(dá)式B被翻譯成三地址

指令，生成的條件或無條件轉(zhuǎn)

移指令反映B的值。B→E1

rel

E2，直接翻譯成三地址比較指令，跳轉(zhuǎn)到正確位置。B→B1||B2,如果B1為真，B

一定為真，所以B1.true和B.true相同。如果B1為假，那

就要對B2求值。因此B1.false

指向B2的代碼開始的位置。B2

的真假出口分別等于B的真假

出口。……布爾表達(dá)式的控制流翻譯及分析????控制流語句及布爾表達(dá)式翻譯?布爾表達(dá)式翻譯，a<bif

a<b

goto

B.truegoto

B.false?控制流語句翻譯if(x<100||x>200&&x!=y)x=0;布爾表達(dá)式及控制流語句翻譯示例?在上面的例子中g(shù)otoL3是冗余的?X>200翻譯成

?可以替換成O

減少了一條goto指令O引入一個特殊標(biāo)號“fall”(穿越，fallthrough)，表示

不要生成任何跳轉(zhuǎn)指令。?S→if(B)S1

的新語義規(guī)則?對于if-else和while語句的規(guī)則也將B.true設(shè)為fall避免冗余的goto指令利用“穿越”修改布爾表達(dá)式的語義規(guī)則

注意B.true=fall時，還得為B1

.true

new一個labelB1

.false=if(B.false=fall)newlabel()else

B.falseB1

.true=fallB2

.true=B.trueB2

.false=B.falseB.code=if(B.false=fall)then

B1

.code||B2

.code||label(B1

.false)elseB1

.code||B2

.codeB

→B1&&B2帶“穿越”的語義規(guī)則使用標(biāo)號fall的控制流語句翻譯示例?if(x<100||x>200&&

x!=y)x=0;?改變控制流，跳轉(zhuǎn)O

剛剛前面重點討論，用非終結(jié)符號B表示此種功能的布爾表達(dá)式以示區(qū)別?

求值O

如x=true,x=a<b?統(tǒng)一處理O使用不同的代碼生成函數(shù)處理表達(dá)式的兩種角色。E.n對應(yīng)于抽象

語法樹上的表達(dá)式節(jié)點。兩個函數(shù)：?

jump,對于出現(xiàn)在S→while(E)S1中的E，調(diào)用E.n.jump(t,f)?

rvalue,對于出現(xiàn)在S→id=E中的E，在節(jié)點E.n上調(diào)用rvalue。如果E是算術(shù)表達(dá)式，按照算術(shù)表達(dá)式的翻譯生成代碼。如果E是布爾表達(dá)式，如E1&E2，首先為E生成跳轉(zhuǎn)代碼，然后在跳轉(zhuǎn)代碼的真假出口分別將true或false賦給一個新的臨時變量t。布爾表達(dá)式的兩個功能?賦值語句x=a<b&&c<d示例?為布爾表達(dá)式和控制流語句生成目標(biāo)代碼的關(guān)鍵問題：某些跳轉(zhuǎn)指令應(yīng)該跳轉(zhuǎn)到哪里?例如：if(B)SO

按照短路代碼的翻譯方法，B的代碼中有一些跳轉(zhuǎn)指令在B為假時執(zhí)行，O

這些跳轉(zhuǎn)指令的目標(biāo)應(yīng)該跳過S對應(yīng)的代碼,生成這些指令時，S的代碼尚未生成，因此目標(biāo)不確定O

通過語句的繼承屬性next來傳遞。需要第二趟處理?如何一趟處理完畢呢？回填(1)?基本思想O

記錄B的代碼中跳轉(zhuǎn)指令goto

S.next，if…gotoS.next的位置，但是不生成跳轉(zhuǎn)目標(biāo)O

這些位置被記錄到B的綜合屬性B.falseList中O

當(dāng)S.next的值已知時(即S的代碼生成完畢時)，把S.nextList中的所有指令的目標(biāo)都填上這個值?回填技術(shù)O

生成跳轉(zhuǎn)指令時暫時不指定跳轉(zhuǎn)目標(biāo)標(biāo)號，而是使用列表記錄這些不完整的指令O

等知道正確的目標(biāo)時再填寫目標(biāo)標(biāo)號O

每個列表中的指令都指向同一個目標(biāo)回填(2)?布爾表達(dá)式用于語句的控制流時，它總是在取值true時和取值false時分別跳轉(zhuǎn)到某個位置?引入兩個綜合屬性O(shè)

truelist

:包含跳轉(zhuǎn)指令(位置)的列表，這些指令在取值true時執(zhí)行O

falselist：包含跳轉(zhuǎn)指令(位置)的列表，這些指令在取值false時執(zhí)行?輔助函數(shù)O

Makelist(i)：創(chuàng)建一個只包含i的列表O

Merge(p1,p2)：將p1和p2指向的列表合并O

Backpatch(p,i)：將i