中間代碼生成課件

第六章中間代碼生成趙建華南京大學(xué)計(jì)算機(jī)系第六章中間代碼生成趙建華本章內(nèi)容中間代碼表示抽象語法樹三地址代碼：x=yopz靜態(tài)類型檢查類型檢查（typechecking）語法分析之后的抽象語法(syntax)檢查，比如break的位置，goto的目標(biāo)….中間代碼生成本章內(nèi)容中間代碼表示編譯器前端的邏輯結(jié)構(gòu)編譯器前端的邏輯結(jié)構(gòu)三地址代碼（1）每條指令右側(cè)最多有一個(gè)運(yùn)算符一般情況可以寫成x

=

yopz允許的運(yùn)算分量：名字：源程序中的名字作為三地址代碼的地址常量：源程序中出現(xiàn)或生成的常量編譯器生成的臨時(shí)變量三地址代碼（1）每條指令右側(cè)最多有一個(gè)運(yùn)算符三地址代碼（2）指令集合（1）運(yùn)算/賦值指令：x=yopz x

=

opy復(fù)制指令：x=y無條件轉(zhuǎn)移指令：gotoL條件轉(zhuǎn)移指令：ifxgotoL ifFalsexgotoL條件轉(zhuǎn)移指令：ifxrelopygotoL三地址代碼（2）指令集合（1）三地址代碼（3）指令集合（2）過程調(diào)用/返回：paramx1 //設(shè)置參數(shù)paramx2…paramxncallp,n //調(diào)用子過程p，n為參數(shù)個(gè)數(shù)帶下標(biāo)的復(fù)制指令：x=y[i]

x[i]=y注意：i表示離開數(shù)組位置第i個(gè)字節(jié)，而不是數(shù)組的第i個(gè)元素地址/指針賦值指令：x=&y x=*y *x=y三地址代碼（3）指令集合（2）例子語句doi=i+1;while(a[i]<v)；例子語句三地址指令的四元式表示方法在實(shí)現(xiàn)時(shí)，可以使用四元式/三元式/間接三元式來表示三地址指令四元式：可以實(shí)現(xiàn)為紀(jì)錄（或結(jié)構(gòu)）格式（字段）： op arg1 arg2 resultop:運(yùn)算符的內(nèi)部編碼arg1,arg2,result是地址x=y+z +yzx單目運(yùn)算符不使用arg2param運(yùn)算不使用arg2和result條件轉(zhuǎn)移/非條件轉(zhuǎn)移將目標(biāo)標(biāo)號放在result字段三地址指令的四元式表示方法在實(shí)現(xiàn)時(shí)，可以使用四元式/三元式/四元式的例子賦值語句：a=b*-c+b*-c四元式的例子賦值語句：a=b*-c+b*-c三元式表示三元式（triple） op arg1 arg2使用三元式的位置來引用三元式的運(yùn)算結(jié)果x[i]=y需要拆分為兩個(gè)三元式求x[i]的地址，然后再賦值x=yopz需要拆分為（這里？是編號）(?) op y z = x ?問題：在優(yōu)化時(shí)經(jīng)常需要移動(dòng)/刪除/添加三元式，導(dǎo)致三元式的移動(dòng)。三元式表示三元式（triple） op arg1 arg2三元式的例子a=b*-c+b*-c三元式的例子a=b*-c+b*-c間接三元式包含了一個(gè)指向三元式的指針的列表我們可以對這個(gè)列表進(jìn)行操作，完成優(yōu)化功能；操作時(shí)不需要修改三元式中的參數(shù)。間接三元式包含了一個(gè)指向三元式的指針的列表靜態(tài)單賦值（SSA）SSA中的所有賦值都是針對不同名的變量對于同一個(gè)變量在不同路徑中定值的情況，可以使用φ函數(shù)來合并不同的定值if(flag)x=-1;elsex=1; y=x*aif(flag)x1=-1;elsex2=1;

x3=φ(x1,x2)；y=x3*a靜態(tài)單賦值（SSA）SSA中的所有賦值都是針對不同名的變量類型和聲明類型檢查(TypeChecking)利用一組規(guī)則來檢查運(yùn)算分量的類型和運(yùn)算符的預(yù)期類型是否匹配。類型信息的用途查錯(cuò)、確定名字需要的內(nèi)存空間、計(jì)算數(shù)組元素的地址、類型轉(zhuǎn)換、選擇正確的運(yùn)算符本節(jié)的內(nèi)容確定名字的類型，變量的存儲空間布局（相對地址）類型和聲明類型檢查(TypeChecking)類型表達(dá)式類型表達(dá)式（type

expression）：表示類型的結(jié)構(gòu)基本類型類名類型構(gòu)造算子作用于類型array[數(shù)字，類型表達(dá)式]record[字段/類型對的列表]（可以用符號表表示）函數(shù)類型構(gòu)造算子：參數(shù)類型結(jié)果類型笛卡爾積：sXt可以包含取值為類型表達(dá)式的變量類型表達(dá)式類型表達(dá)式（typeexpression）：表示類型表達(dá)式的例子類型例子元素個(gè)數(shù)為3X4的二維數(shù)組數(shù)組的元素的記錄類型該記錄類型中包含兩個(gè)字段:

x和y,其類型分別是float和integer類型表達(dá)式array[3,array[4,record[(x,float),(y,float)]]類型表達(dá)式的例子類型例子類型等價(jià)不同的語言有不同的類型等價(jià)的定義結(jié)構(gòu)等價(jià)或者它們是相同的基本類型或者是相同的構(gòu)造算子作用于結(jié)構(gòu)等價(jià)的類型而得到的?；蛘咭粋€(gè)類型是另一個(gè)類型表達(dá)式的名字名等價(jià)類型名僅僅代表其自身類型等價(jià)不同的語言有不同的類型等價(jià)的定義聲明文法DTid;D|εTBC|record‘{’D‘}’Cint|floatCε|[num]C含義：D生成一系列聲明；T生成不同的類型；B生成基本類型int/float；C表示分量，生成[num]序列；注意record中包含了各個(gè)字段的聲明。字段聲明和變量聲明的文法一致。聲明文法局部變量的存儲布局變量的類型可以確定變量需要的內(nèi)存即類型的寬度可變大小的數(shù)據(jù)結(jié)構(gòu)只需要考慮指針函數(shù)的局部變量總是分配在連續(xù)的區(qū)間；因此給每個(gè)變量分配一個(gè)相對于這個(gè)區(qū)間開始處的相對地址變量的類型信息保存在符號表中；局部變量的存儲布局變量的類型可以確定變量需要的內(nèi)存計(jì)算T的類型和寬度的SDT綜合屬性：type,width全局變量t和w用于將類型和寬度信息從B傳遞到Cε相當(dāng)于C的繼承屬性，因?yàn)榭偸峭ㄟ^拷貝來傳遞，所以在SDT中只賦值一次。也可以把t和w替換為C.t和C.w計(jì)算T的類型和寬度的SDT綜合屬性：type,widthSDT運(yùn)行的例子輸入：int[2][3]SDT運(yùn)行的例子輸入：int[2][3]作用域和符號表在具有語句塊概念的編程語言中，標(biāo)識符x在最內(nèi)層的x聲明的作用域中。每個(gè)作用域?qū)?yīng)于一個(gè)符號表；多個(gè)符號表形成樹狀結(jié)構(gòu)。在語義分析時(shí)，通過棧來存放當(dāng)前符號表及其祖先。作用域和符號表在具有語句塊概念的編程語言中，標(biāo)識符x在最內(nèi)層聲明序列的SDT（1）在處理一個(gè)過程/函數(shù)時(shí)，局部變量應(yīng)該放到單獨(dú)的符號表中去；這些變量的內(nèi)存布局獨(dú)立相對地址從0開始；假設(shè)變量的放置和聲明的順序相同；SDT的處理方法變量offset記錄當(dāng)前可用的相對地址；每“分配”一個(gè)變量，offset的值增加相應(yīng)的值top.put(id.lexeme,T.type,offset)在當(dāng)前符號表(位于棧頂)中創(chuàng)建符號表?xiàng)l目，記錄標(biāo)識符的類型，偏移量聲明序列的SDT（1）在處理一個(gè)過程/函數(shù)時(shí)，局部變量應(yīng)該放聲明序列的SDT（2）我們可以把offset看作D的繼承屬性D.offset表示D中第一個(gè)變量的相對地址P{D.offset=0}DDTid;{D1.offset=D.offset+T.width;}D1聲明序列的SDT（2）我們可以把offset看作D的繼承屬性記錄字段的處理Trecord‘{‘D‘}’為每個(gè)記錄創(chuàng)建單獨(dú)的符號表首先創(chuàng)建一個(gè)新的符號表，壓到棧頂；然后處理對應(yīng)于字段聲明的D，字段都被加入到新符號表中；最后根據(jù)棧頂?shù)姆柋順?gòu)造出record類型表達(dá)式；符號表出棧記錄字段的處理Trecord‘{‘D‘}’表達(dá)式代碼的SDD將表達(dá)式翻譯成三地址指令序列表達(dá)式的SDD屬性code表示代碼addr表示存放表達(dá)式結(jié)果的地址（臨時(shí)變量）newTemp()可以生成一個(gè)臨時(shí)變量gen(…)生成一個(gè)指令表達(dá)式代碼的SDD將表達(dá)式翻譯成三地址指令序列增量式翻譯方案主屬性code滿足增量式翻譯的條件。注意：top.get(…)從棧頂符號表開始，逐個(gè)向下尋找id的信息。這里的gen發(fā)出相應(yīng)的代碼增量式翻譯方案主屬性code滿足增量式翻譯的條件。數(shù)組元素的尋址假設(shè)數(shù)組元素被存放在連續(xù)的存儲空間中。元素從0到n-1編號，第i個(gè)元素的地址為base+i*wK維數(shù)組的尋址：假設(shè)數(shù)組按行存放，即首先存放A[0][i2]…[ik]，然后存放A[1][i2]…[ik]，…A[i1][i2]…[ik]的地址base+i1*w1+i2*w2+…+ik*wk或者base+((…((i1*n2+i2)*n3+i3)…)*nk+ik)*w其中：base、w、i、n的值可以從符號表中找到。數(shù)組元素的尋址假設(shè)數(shù)組元素被存放在連續(xù)的存儲空間中。新的文法產(chǎn)生式數(shù)組元素L：LL[E]|id[E]以數(shù)組元素為左部的賦值：SL=E;數(shù)組元素作為表達(dá)式中的因子：ELL的代碼計(jì)算偏移量，將結(jié)果存放于L.addr所指的臨時(shí)變量中綜合屬性array記錄了相應(yīng)數(shù)組的信息：元素類型，基地址，…新的文法產(chǎn)生式數(shù)組元素L：LL[E]|id[E]數(shù)組元素作為因子L的代碼只計(jì)算了偏移量；數(shù)組元素的存放地址應(yīng)該根據(jù)偏移量進(jìn)一步計(jì)算，即L的數(shù)組基址加上偏移量使用三地址指令x=a[i]數(shù)組元素作為因子L的代碼只計(jì)算了偏移量；數(shù)組元素作為賦值左部使用三地址指令a[i]=x數(shù)組元素作為賦值左部使用三地址指令a[i]=x例子表達(dá)式：c+a[i][j]例子表達(dá)式：c+a[i][j]類型檢查和轉(zhuǎn)換類型系統(tǒng)：給每一個(gè)組成部分賦予一個(gè)類型表達(dá)式通過一組邏輯規(guī)則來表示這些類型表達(dá)式必須滿足的條件可發(fā)現(xiàn)錯(cuò)誤、提高代碼效率、確定臨時(shí)變量的大小、…類型檢查和轉(zhuǎn)換類型系統(tǒng)：類型系統(tǒng)的分類類型綜合根據(jù)子表達(dá)式的類型構(gòu)造出表達(dá)式的類型if

f的類型為st且x的類型為sthen

f(x)的類型為t類型推導(dǎo)根據(jù)語言結(jié)構(gòu)的使用方式來確定該結(jié)構(gòu)的類型：iff(x)是一個(gè)表達(dá)式then對于某些類型α,β；f的類型為αβ且x的類型為α類型系統(tǒng)的分類類型綜合類型轉(zhuǎn)換假設(shè)在表達(dá)式x*i中，x為浮點(diǎn)數(shù)、i為整數(shù)，則結(jié)果應(yīng)該是浮點(diǎn)數(shù)x和i使用不同的二進(jìn)制表示方式浮點(diǎn)*和整數(shù)*使用不同的指令t1=(float)it2=xfmult1類型轉(zhuǎn)換比較簡單時(shí)的SDD：EE1+E2{if(E1.type=integerandE2.type=integer)E.type=integer;elseif

(E1.type=floatandE2.type=integer)E.type=float;}}這個(gè)規(guī)則沒有考慮生成類型轉(zhuǎn)換代碼類型轉(zhuǎn)換假設(shè)在表達(dá)式x*i中，x為浮點(diǎn)數(shù)、i為整數(shù)，則結(jié)果應(yīng)類型的widening和narrowingJava的類型轉(zhuǎn)換規(guī)則編譯器自動(dòng)完成的轉(zhuǎn)換為隱式轉(zhuǎn)換，程序員用代碼指定的轉(zhuǎn)換為顯式轉(zhuǎn)換。類型的widening和narrowingJava的類型轉(zhuǎn)換處理類型轉(zhuǎn)換的SDT函數(shù)Max求的是兩個(gè)參數(shù)在拓寬層次結(jié)構(gòu)中的最小公共祖先Widen函數(shù)已經(jīng)生成了必要的類型轉(zhuǎn)換代碼處理類型轉(zhuǎn)換的SDT函數(shù)Max求的是兩個(gè)參數(shù)在拓寬層次結(jié)構(gòu)中函數(shù)/運(yùn)算符的重載通過查看參數(shù)來解決函數(shù)重載問題Ef(E1)

{

if

f.typeset={siti|1<=i<=k}andE1.type=sk

then

E.type=tk

}函數(shù)/運(yùn)算符的重載通過查看參數(shù)來解決函數(shù)重載問題控制流的翻譯布爾表達(dá)式可以用于改變控制流/計(jì)算邏輯值。文法BB‖B|B&&B|!B|(B)|ErelE|true|false語義B1‖B2中B1為真時(shí)，不計(jì)算B2，整個(gè)表達(dá)式為真。因此，當(dāng)B1為真時(shí)應(yīng)該跳過B2的代碼。B1&&B2中B1為假時(shí)，不計(jì)算B2，整個(gè)表達(dá)式為假短路代碼通過跳轉(zhuǎn)指令實(shí)現(xiàn)控制流的處理邏輯運(yùn)算符本身不在代碼中出現(xiàn)；控制流的翻譯布爾表達(dá)式可以用于改變控制流/計(jì)算邏輯值。短路代碼的例子語句：if(x<100||x>200&&x!=y)x=0;代碼

if x<100 gotoL2

ifFalse x>200 gotoL1

ifFalse x!=y gotoL1L2:x=0L1:接下來的代碼注：當(dāng)x<100為真時(shí)，直接執(zhí)行x=0；所以執(zhí)行x>200時(shí)，x<100必然為假同理：計(jì)算x!=y時(shí)，x<100為假，而x>200為真短路代碼的例子語句：注：控制流語句的翻譯文法：B表示布爾表達(dá)式，S代表語句Sif(B)S1Sif(B)S1

elseS2Swhile(B)S1代碼的布局見右圖繼承屬性B.true：B為真的跳轉(zhuǎn)目標(biāo)B.false：B為假的跳轉(zhuǎn)目標(biāo)S.next：S執(zhí)行完畢時(shí)的跳轉(zhuǎn)目標(biāo)控制流語句的翻譯文法：B表示布爾表達(dá)式，S代表語句語法制導(dǎo)的定義（1）語法制導(dǎo)的定義（1）語法制導(dǎo)的定義（2）增量式生成代碼：Swhile( {begin=newlabel();B.true=newlabel;B.false=S.next;gen(begin‘:’)}

B)

{gen(B.true‘:’);S1.next=begin;}S1{gen(‘goto’begin);}語法制導(dǎo)的定義（2）增量式生成代碼：布爾表達(dá)式的控制流翻譯生成的代碼執(zhí)行時(shí)跳轉(zhuǎn)到兩個(gè)標(biāo)號之一。表達(dá)式的值為真時(shí)，跳轉(zhuǎn)到B.true表達(dá)式的值為假時(shí)，跳轉(zhuǎn)到B.falseB.true和B.false是兩個(gè)繼承屬性，根據(jù)B所在的上下文指向不同的位置如果B是if語句的條件表達(dá)式，分別指向then分支和else分支；如果沒有else分支，則指向if語句的下一條指令如果B是while語句的條件表達(dá)式，分別指向循環(huán)體的開頭和循環(huán)出口處；布爾表達(dá)式的控制流翻譯生成的代碼執(zhí)行時(shí)跳轉(zhuǎn)到兩個(gè)標(biāo)號之一。布爾表達(dá)式的代碼的SDD（1）布爾表達(dá)式的代碼的SDD（1）布爾表達(dá)式的代碼的SDD（2）布爾表達(dá)式的代碼的SDD（2）布爾表達(dá)式代碼的例子if(x<100||x>200&&x!=y)x=0;的代碼布爾表達(dá)式代碼的例子if(x<100||x>200布爾值和跳轉(zhuǎn)代碼程序中出現(xiàn)布爾表達(dá)式的目的可能就是求出它的值。比如x=a<b；處理方法：首先建立表達(dá)式的語法樹，然后根據(jù)表達(dá)式的不同角色來處理。文法：Sid=E;|if(E)S|while(E)S|SSEE‖E|E&&E|ErelE

|

…根據(jù)E的語法樹結(jié)點(diǎn)所在的位置：Swhile(E)S1中的E，生成跳轉(zhuǎn)代碼對于Sid=E，生成計(jì)算右值的代碼布爾值和跳轉(zhuǎn)代碼程序中出現(xiàn)布爾表達(dá)式的目的可能就是求出它的值回填（1）為布爾表達(dá)式和控制流語句生成目標(biāo)代碼的關(guān)鍵問題：某些跳轉(zhuǎn)指令應(yīng)該跳轉(zhuǎn)到哪里例如：if

(B)S按照短路代碼的翻譯方法，B的代碼中有一些跳轉(zhuǎn)指令在B為假時(shí)執(zhí)行，這些跳轉(zhuǎn)指令的目標(biāo)應(yīng)該跳過S對應(yīng)的代碼。生成這些指令時(shí)，S的代碼尚未生成，因此目標(biāo)不確定通過語句的繼承屬性next來傳遞。需要第二趟處理。如何一趟處理完畢呢？回填（1）為布爾表達(dá)式和控制流語句生成目標(biāo)代碼的關(guān)鍵問題：某回填（2）基本思想：記錄B的代碼中跳轉(zhuǎn)指令gotoS.next，if…gotoS.next的位置，但是不生成跳轉(zhuǎn)目標(biāo)。這些位置被記錄到B的綜合屬性B.falseList中；當(dāng)S.next的值已知時(shí)（即S的代碼生成完畢時(shí)），把B.nextList中的所有指令的目標(biāo)都填上這個(gè)值?；靥罴夹g(shù)：生成跳轉(zhuǎn)指令時(shí)暫時(shí)不指定跳轉(zhuǎn)目標(biāo)標(biāo)號，而是使用列表記錄這些不完整的指令；等知道正確的目標(biāo)時(shí)再填寫目標(biāo)標(biāo)號；每個(gè)列表中的指令都指向同一個(gè)目標(biāo)回填（2）基本思想：布爾表達(dá)式的回填翻譯（1）布爾表達(dá)式用于語句的控制流時(shí)，它總是在取值true時(shí)和取值false時(shí)分別跳轉(zhuǎn)到某個(gè)位置引入兩個(gè)綜合屬性truelist:包含跳轉(zhuǎn)指令（位置）的列表，這些指令在取值true時(shí)執(zhí)行falselist：包含跳轉(zhuǎn)指令（位置）的列表，這些指令在取值false時(shí)執(zhí)行輔助函數(shù)Makelist(i)Merge(p1,p2)Backpatch(p,i)布爾表達(dá)式的回填翻譯（1）布爾表達(dá)式用于語句的控制流時(shí)，它總布爾表達(dá)式的回填翻譯（2）布爾表達(dá)式的回填翻譯（2）回填和非回填方法的比較（1）B {B1.true=B.true,B1.false=newlabel();} B1|| {label(B1.false);B2.true=B.true;B2.false=B.false;} B2true/false屬性的賦值，在回填方案中對應(yīng)為相應(yīng)的list的賦值或者merge；原來生成label的地方，在回填方案中使用M來記錄相應(yīng)的代碼位置。M.inst的需要對英語相應(yīng)label的標(biāo)號；原方案生成的指令goto

B1.false，現(xiàn)在生成了gotoM.inst回填和