第十二章代碼生成

第12章代碼生成代碼生成:

中間代碼作為輸入

特定機(jī)器的機(jī)器語言或匯編語言作為輸出，這樣的轉(zhuǎn)換程序稱為代碼生成器，1如果用‘op’表示運(yùn)算符，用‘M’表示內(nèi)存單元，用變量名表示該變量所在的單元，‘C’表示常量，‘*’表示間址方式存取，指令形式表(P278表12.2)。opRi,M

opRi,Rj

opRi,c(Rj)

opRi,*M

opRi,*Rj

opRi,*c(Rj)(Ri)op(M)

Ri

(Ri)op(Rj)

Ri

(Ri)op((Rj)+c)

Ri

(Ri)op((M))

Ri

(Ri)op((Rj))

Ri

(Ri)op(((Rj)+c))

Ri2指令意義指令意義LDRi,B

STRi,B

JX

CMPA,B把B單元的內(nèi)容取到寄存器Ri，即(B)

Ri。

把寄存器Ri的內(nèi)容存到B單元，即(Ri)

B。

無條件轉(zhuǎn)向X單元。

把A單元和B單元的值進(jìn)行比較，并根據(jù)比較情況把機(jī)器內(nèi)部特征寄存器CT置成相應(yīng)狀態(tài)。CT占兩個(gè)二進(jìn)位。根據(jù)A<B或A=B或A>B分別置CT為0或1或2。J<X

J≤X

J=X

J≠X

J>X

J≥X如CT=0轉(zhuǎn)X單元。

如CT=0或CT=1轉(zhuǎn)X單元。

如CT=1轉(zhuǎn)X單元。

如CT≠1轉(zhuǎn)X單元。

如CT=2轉(zhuǎn)X單元。

如CT=2或CT=1轉(zhuǎn)X單元。

3一個(gè)簡(jiǎn)單的代碼生成器

它以四元式的代碼作為輸入，將其轉(zhuǎn)換成目標(biāo)代碼。它在基本塊內(nèi)如何充分利用寄存器提高目標(biāo)代碼的運(yùn)行效率？

寄存器分配的原則（P276）①當(dāng)生成某變量的目標(biāo)代碼時(shí)，盡量讓變量的值或計(jì)算結(jié)果保留在寄存器中直到寄存器不夠分配時(shí)為止，這樣引用變量值時(shí)可減少對(duì)內(nèi)存的存取次數(shù)，以提高運(yùn)行速度。

②當(dāng)?shù)交緣K出口時(shí)，將變量的值存放在內(nèi)存中，這樣從基本塊外入口的變量值都在內(nèi)存中。

③對(duì)于在一個(gè)基本塊內(nèi)后邊不再被引用的變量所占用的寄存器應(yīng)盡早釋放，以提高寄存器的利用效率。

4例:設(shè)一高級(jí)語言的語句為：A:=(B+C)*D+E翻譯成中間代碼為:T1:=B+CT2:=T1*DA:=T2+E問目標(biāo)代碼是什么5目標(biāo)代碼:LDR,BADDR,CSTR,T1LDR,T1MULR,DSTR,T2LDR,T2ADDR,ESTR,A中間代碼為:T1:=B+CT2:=T1*DA:=T2+E如果不考慮代碼的效率，我們可以翻譯為如下代碼：6從正確性看,沒有問題,但卻有很多冗余,因?yàn)門1,T2為臨時(shí)變量,出了基本快后將不會(huì)引用,因此,(3)(4)(6)(7)均可省掉,考慮到效率和充分利用寄存器的問題,目標(biāo)代碼變?yōu)?LDR,BADDR,CMULR,DADDR,ESTR,AA:=(B+C)*D+E為了能夠這樣做，代碼生成器必須了解一些信息：在產(chǎn)生T2:=T1*D對(duì)應(yīng)的目標(biāo)代碼時(shí)，為了省去STR,T1,就必須知道出了基本塊后T1不會(huì)再利用。為了省去指令LDR,T1,就必須知道T1的值已經(jīng)在R中。原目標(biāo)代碼:LDR,BADDR,CSTR,T1LDR,T1MULR,DSTR,T2LDR,T2ADDR,ESTR,A中間代碼為:T1:=B+CT2:=T1*DA:=T2+E7在一個(gè)基本塊內(nèi)考慮如何充分利用寄存器：l盡可能地讓該變量的值保留在寄存器中l(wèi)盡可能引用變量在寄存器中的值待用信息：若在一個(gè)基本塊中，變量A在四元式i中被定值，在i后面的四元式j(luò)中要引用A值，且從i到j(luò)之間沒有其它對(duì)A的定值點(diǎn)，稱j是四元式i中對(duì)變量A的待用信息或稱下次引用信息，同時(shí)也稱A是活躍的。若A被多處引用，則可構(gòu)成待用信息鏈與活躍信息鏈?？蓮幕緣K的出口由后向前掃描，對(duì)每個(gè)變量建立相應(yīng)的待用信息鏈和活躍變量信息鏈。

8對(duì)各基本塊的符號(hào)表中的“待用信息”欄和“活躍信息”欄置初值，即把“待用信息”欄置“非待用”，對(duì)“活躍信息”欄按在基本塊出口處是否為活躍而置成“活躍”或“非活躍”。這里假定變量都是活躍的，臨時(shí)變量都是非活躍的。符號(hào)表中增加“待用信息”欄和“活躍信息”欄見P280

表12.4計(jì)算待用信息的算法：9

從基本塊出口到入口由后向前依次處理每個(gè)四元式。對(duì)每個(gè)四元式i:A:=BopC，依次執(zhí)行下述步驟：a)把符號(hào)表中變量A的待用信息和活躍信息附加到四元式上。b)把符號(hào)表中變量A的待用信息欄和活躍信息欄分別置為“非待用”和“非活躍”。（變量定義時(shí)為非活躍、非待用）由于在i中對(duì)A的定值只能在i以后的四元式才能引用，因而對(duì)i以前的四元式來說，A是不活躍也不可能是待用的。c)把符號(hào)表中變量B和C的待用信息和活躍信息附加到四元式i上。d)把符號(hào)表中變量B和C的待用信息欄置為“i”，活躍信息欄置為“活躍”。（使用時(shí)為待用、活躍）注意，以上a)和b)，c)和d)的次序不能顛倒。

10若用A，B，C和D表示變量，用T，U，V表示中間變量，有四元式如下：(1)T:=A-B(2)U:=A-C(3)V:=T+U(4)D:=V+U其名字表中的待用信息和活躍信息如下表，用“F”表示“非待用”或“非活躍”，用“L”表示活躍。(1)(2)(3)(4)表示四元式序號(hào)。例：1112

RVALUE[Ri]={A,C}表示Ri的現(xiàn)行值是變量A，C的值

AVALUE[A]={A}表示A的值在內(nèi)存中

AVALUE[A]={Ri,A}表示A的值既在寄存器Ri中又在內(nèi)存中

AVALUE[A]={Ri}表示變量A的值在寄存器Ri中代碼生成算法

為了在代碼生成中能有效地分配寄存器，還需隨時(shí)掌握各寄存器的使用情況。用一個(gè)數(shù)組RVALUE來描述(記錄)每個(gè)寄存器當(dāng)前的狀況，是處于空閑狀態(tài)還是被某個(gè)或某幾個(gè)變量占用（若程序中含有復(fù)寫，就會(huì)出現(xiàn)最后一種情況）；用數(shù)組AVALUE[M]表示變量的存放情況。因此一個(gè)變量的值可能存放在寄存器中或存放在內(nèi)存中，也可能既在寄存器中又在內(nèi)存中。

13基本塊的代碼生成算法對(duì)每個(gè)四元式i:A:=BopC，依次執(zhí)行下述步驟：（1）以四元式i:A:=BopC為參數(shù)，調(diào)用過程

getreg(i:A:=BopC)。從getreg返回時(shí)，得到一寄存器

R，用它作存放A現(xiàn)行值的寄存器；（2）利用AVALUE[B]和AVALUE[C]，確定出B和C現(xiàn)行值存放位置B`和C`，如果其現(xiàn)行值在寄存器中，則把寄存器取作B`和C`；（3）如果B`≠R，則生成目標(biāo)代碼：

LDR，B`OPR,C`

否則生成目標(biāo)代碼：OPR，C`,如果B`或C`為R，則刪除AVALUE[B]或AVALUE[C]中的R。（4）令A(yù)VALUE[A]={R}，并令RVALUE[R]={A}，以表示變量A的現(xiàn)行值只在R中并且R中的值只代表A的現(xiàn)行值；（5）如B或C的現(xiàn)行值在基本塊中不再被引用，它們也不是基本塊出口之后的活躍變量（由四元式i上的附加信息知道），并且其現(xiàn)行值在某個(gè)寄存器Rk中，則刪除RVALUE[Rk]中的B或C以及AVALUE[B]或

AVALUE[C]中的Rk，使該寄存器不再為B或C所占用。

14設(shè)GETREG是一個(gè)函數(shù)過程，它的參數(shù)是一個(gè)形如i:A:=BopC的四元式，每次調(diào)用GETREG(i:A:=BopC)則返回一個(gè)寄存器R，用以存放A的結(jié)果值。

對(duì)如何給出寄存器R，要用到四元式i上的待用信息，以使寄存器分配合理.

對(duì)每個(gè)四元式的代碼生成都要調(diào)用函數(shù)GETREG。

GETREG分配寄存器的算法為：

①如果B的現(xiàn)行值在某寄存器Ri中，該寄存器只包含B的值，且為下列兩種情況之一:或者B與A是同一標(biāo)識(shí)符;或B在該四元式后不會(huì)再被引用，則可選取Ri作為所需的寄存器R，并轉(zhuǎn)(4)。

②如果有尚未分配的寄存器，則從中選用一個(gè)Ri為所需的寄存器R，并轉(zhuǎn)(4)。

③從已分配的寄存器中選取一個(gè)Ri作為所需寄存器R，其選擇原則為：占用該寄存器的變量值同時(shí)在主存中，或在基本塊中引用的位置最遠(yuǎn)，這樣對(duì)寄存器Ri

所含的變量和變量在主存中的情況必須先做如下調(diào)整：即對(duì)RVALUE[Ri]中的每一變量M，

如果M不是A且AVALUE[M]不包含M，則需完成以下處理。

a)生成目標(biāo)代碼STRi,M;即把不是A的變量值由Ri中送入內(nèi)存中。

b)如果M不是B，則令A(yù)VALUE[M]={M}，否則，令A(yù)VALUE[M]={M,Ri}。

c)刪除RVALUE[Ri]中的M。

④給出R，返回。15PL/0編譯程序的目標(biāo)代碼結(jié)構(gòu)和代碼生成

目標(biāo)代碼類pcode是一種假想棧式計(jì)算機(jī)的匯編語言。指令格式：flaf 功能碼l 層次差（標(biāo)識(shí)符引用層減去定義層）a 根據(jù)不同的指令有所區(qū)別目標(biāo)指令見下頁見P23頁16指令功能表17代碼生成代碼生成是由過程GEN完成。P417GEN有3個(gè)參數(shù)，分別代表目標(biāo)代碼的功能碼，層差和位移量。例如

gen(opr,0,16);從命令行讀取值到棧頂

gen(sto,lev-level,adr)

將棧頂內(nèi)容送到變量單元中，

lev：當(dāng)前處理的過程層次

level：被引用變量或過程所在層次

CX：為目標(biāo)代碼code數(shù)組的下標(biāo)指針18Code:array[0..cxmax]ofinstruction;p414fct=(lit,opr,lod,sto,cal,int,jmp,jpc)P413Instruction=packecrecordP413f:fct;l:0..levmax

a:0..amax;end;19CODE為一維數(shù)組，數(shù)組元素為記錄型數(shù)據(jù)。每一個(gè)記錄就是一條目標(biāo)指令。CX為指令的指針，由0開始順序增加。實(shí)際上目標(biāo)代碼的順序是內(nèi)層過程的排在前邊，主程序的目標(biāo)代碼在最后。下面我們給出一個(gè)PL/0源程序和對(duì)應(yīng)的目標(biāo)程序的清單。20

consta=10;

varb,c;

procedurep;

begin

c:=b+a;

end;

begin

read(b);

whileb#0do

begin

callp;

write(2*c);

read(b);

end

end.

(0)jmp08轉(zhuǎn)向主程序入口(1)jmp02轉(zhuǎn)向過程p入口(2)int03過程p入口,為過程p開辟空間(3)lod13取變量b的值到棧頂(4)lit010取常數(shù)10到棧頂(5)opr02次棧頂與棧頂相加(6)sto14棧頂值送變量c中(7)opr00退棧并返回調(diào)用點(diǎn)(16)(8)

int05主程序入口開辟5個(gè)?？臻g(9)opr016從命令行讀入值置于棧頂(10)sto03將棧頂值存入變量b中(11)lod03將變量b的值取至棧頂(12)lit00將常數(shù)值0進(jìn)棧(13)opr09次棧頂與棧頂是否不等(14)jpc024

等時(shí)轉(zhuǎn)(24)（條件不滿足轉(zhuǎn)）(15)cal02調(diào)用過程p(16)lit02常數(shù)值2進(jìn)棧(17)lod

04將變量c的值取至棧頂(18)opr04次棧頂與棧頂相乘(2*c)(19)opr014棧頂值輸出至屏幕(20)opr015換行(21)opr016從命令行讀取值到棧頂(22)sto

03棧頂值送變量b中(23)jmp011無條件轉(zhuǎn)到循環(huán)入口(11)(24)opr00結(jié)束退棧21PL/0編譯程序的目標(biāo)代碼生成是由GEN過程完成的，當(dāng)語法分析正確則調(diào)用目標(biāo)代碼生成過程以生成與PL/0語句等價(jià)功能的目標(biāo)代碼，直到編譯正常結(jié)束。除了過程說明部分外，變量和常量的說明都不產(chǎn)生目標(biāo)代碼。在block入口處生成一條(jmp,0,0)指令，作為過程體入口指令，該指令的第3區(qū)域的'0'需分析到過程體入口時(shí)才返填。對(duì)分程序體入口的處理（見程序文本P424頁block的過程體）

begin(*block*)

dx:=3;

tx0:=tx;（*保留當(dāng)前table表指針值,實(shí)際為過程名在table表中的位置*）

table[tx].adr:=cx;（*保留當(dāng)前code指針值到過程名的adr域*）

gen(jmp,0,0);

22錄過程在code的入口到table中的adr域如下表所示：

（*生成轉(zhuǎn)向過程體入口的指令，該指令的地址為cx已保留在過程名的adr域，真正的過程體入口地址，等生成過程體入口的指令時(shí)，將過程體入口返填（jmp,0,0）的第3區(qū)域，同時(shí)填到table[tx0].adr中*)tx0tx0:=tx;table[tx].adr:=cx;tx23table表格管理

code[table[tx0].adr].a:=cx;tx0tx24過程體入口時(shí)的處理

table表格管理

code[table[tx0].adr].a:=cx;（cx為過程入口地址，填寫在code中）

withtable[tx0]do

begin

adr:=cx;（table[tx0].adr=cx）

size:=dx;（table[tx0].size＝dx）

end;

請(qǐng)?zhí)貏e注意dx、tx、cx的作用和如何處理信息之間的連接關(guān)系。25

CASEWHILESYM: CX1=CX;GetSym();//保留L1的地址

CONDITION(SymSetAdd(DOSYM,FSYS),LEV,TX);//生成B的代碼

CX2=CX;GEN(JPC,0,0);//條件跳轉(zhuǎn),L2待定,

if(SYM==DOSYM)GetSym(); elseError(18); STATEMENT(FSYS,LEV,TX);//生成S的代碼

GEN(JMP,0,CX1)；//無條件跳轉(zhuǎn),轉(zhuǎn)到L1 CODE[CX2].A=CX;//回填L2 break;switch(SYM){……WhileBDoSBFalseS轉(zhuǎn)L1L1：L2:CX1CX226解釋程序還定義了4個(gè)寄存器。

(1)I：指令寄存器。存放著當(dāng)前正在解釋的一條目標(biāo)指令。

(2)P：程序地址寄存器。指向下一條要執(zhí)行的目標(biāo)程序的地址(相當(dāng)目標(biāo)程序CODE數(shù)組的下標(biāo))。

(3