編譯原理課件：第12章 代碼生成

1第12章代碼生成

代碼生成:

中間代碼作為輸入

特定機器的機器語言或匯編語言作為輸出，這樣的轉換程序稱為代碼生成器，2如果用‘op’表示運算符，用‘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))

Ri3指令意義指令意義LDRi,B

STRi,B

JX

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

Ri。

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

B。

無條件轉向X單元。

把A單元和B單元的值進行比較，并根據(jù)比較情況把機器內(nèi)部特征寄存器CT置成相應狀態(tài)。CT占兩個二進位。根據(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轉X單元。

如CT=0或CT=1轉X單元。

如CT=1轉X單元。

如CT≠1轉X單元。

如CT=2轉X單元。

如CT=2或CT=1轉X單元。

4一個簡單的代碼生成器

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

寄存器分配的原則（P276）當生成某變量的目標代碼時，盡量讓變量的值或計算結果保留在寄存器中直到寄存器不夠分配時為止，這樣引用變量值時可減少對內(nèi)存的存取次數(shù)，以提高運行速度。當?shù)交緣K出口時，將變量的值存放在內(nèi)存中，這樣從基本塊外入口的變量值都在內(nèi)存中.對于在一個基本塊內(nèi)后邊不再被引用的變量所占用的寄存器應盡早釋放，以提高寄存器的利用效率。5例:設一高級語言的語句為：A:=(B+C)*D+E翻譯成中間代碼為:T1:=B+CT2:=T1*DA:=T2+E問目標代碼是什么?6目標代碼:LDR,BADDR,CSTR,T1LDR,T1MULR,DSTR,T2LDR,T2ADDR,ESTR,A中間代碼為:T1:=B+CT2:=T1*DA:=T2+E如果不考慮代碼的效率，我們可以翻譯為如下代碼：7從正確性看,沒有問題,但卻有很多冗余,因為T1,T2為臨時變量,出了基本快后將不會引用,因此,(3)(4)(6)(7)均可省掉,考慮到效率和充分利用寄存器的問題,目標代碼變?yōu)?LDR,BADDR,CMULR,DADDR,ESTR,A為了能夠這樣做，代碼生成器必須了解一些信息：在產(chǎn)生T2:=T1*D對應的目標代碼時，為了省去STR,T1,就必須知道出了基本塊后T1不會再利用。為了省去指令LDR,T1,就必須知道T1的值已經(jīng)在R中。原目標代碼:LDR,BADDR,CSTR,T1LDR,T1MULR,DSTR,T2LDR,T2ADDR,ESTR,AA:=(B+C)*D+E中間代碼為:T1:=B+CT2:=T1*DA:=T2+E8在一個基本塊內(nèi)考慮如何充分利用寄存器：l盡可能地讓該變量的值保留在寄存器中l(wèi)盡可能引用變量在寄存器中的值

待用信息：若在一個基本塊中，變量A在四元式i中被定值，在i后面的四元式j中要引用A值，且從i到j之間沒有其它對A的定值點，稱j是四元式i中對變量A的待用信息或稱下次引用信息，同時也稱A是活躍的。若A被多處引用，則可構成待用信息鏈與活躍信息鏈。可從基本塊的出口由后向前掃描，對每個變量建立相應的待用信息鏈和活躍變量信息鏈。9對各基本塊的符號表中的“待用信息”欄和“活躍信息”欄置初值.，符號表中增加“待用信息”欄和“活躍信息”欄見P280表12.4計算待用信息的算法：把“待用信息”欄置“非待用”，對“活躍信息”欄按在基本塊出口處是否為活躍而置成“活躍”或“非活躍”。這里假定變量都是活躍的，臨時變量都是非活躍的。10

從基本塊出口到入口由后向前依次處理每個四元式。對每個四元式i:A:=BopC，依次執(zhí)行下述步驟：

a)把符號表中變量A的待用信息和活躍信息附加到四元式上。b)把符號表中變量A的待用信息欄和活躍信息欄分別置為“非待用”和“非活躍”。（變量定義時為非活躍、非待用）由于在i中對A的定值只能在i以后的四元式才能引用，因而對i以前的四元式來說，A是不活躍也不可能是待用的。c)把符號表中變量B和C的待用信息和活躍信息附加到四元式i上。d)把符號表中變量B和C的待用信息欄置為“i”，活躍信息欄置為“活躍”。（使用時為待用、活躍）注意，以上a)和b)，c)和d)的次序不能顛倒11(1)T(3)L:=A(2)L-BFL(2)U(3)L:=AFL-CFL(3)V(4)L:=TFF+U(4)L(4)DFL:=VFF+UFF(1)T:=A-B(2)U:=A-C(3)V:=T+U(4)D:=V+U12

若用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)表示四元式序號。例：1314RVALUE[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ù)組RVALUE來描述(記錄)每個寄存器當前的狀況，是處于空閑狀態(tài)還是被某個或某幾個變量占用用數(shù)組AVALUE[M]表示變量的存放情況。因此一個變量的值可能存放在寄存器中或存放在內(nèi)存中，也可能既在寄存器中又在內(nèi)存中。

15基本塊的代碼生成算法對每個四元式i:A:=BopC，依次執(zhí)行下述步驟：以四元式i:A:=BopC為參數(shù)，調用過程getreg(i:A:=BopC)從getreg返回時，得到一寄存器R，用它作存放A現(xiàn)行值的寄存器利用AVALUE[B]和AVALUE[C]，確定出B和C現(xiàn)行值存放位置B`和C`，如果其現(xiàn)行值在寄存器中，則把寄存器取作B`和C`；如果B`≠R，則生成目標代碼：LDR，B`OPR,C`

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

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

對如何給出寄存器R，要用到四元式i上的待用信息，以使寄存器分配合理.對每個四元式的代碼生成都要調用函數(shù)GETREG。18GETREG分配寄存器的算法為：

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

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

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

所含的變量和變量在主存中的情況必須先做如下調整：即對RVALUE[Ri]中的每一變量M，如果M不是A且AVALUE[M]不包含M，則需完成以下處理。

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

b)如果M不是B，則令AVALUE[M]={M}，否則，令AVALUE[M]={M,Ri}。

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

④給出R，返回。RVALUE[Ri]={A,C}表示Ri的現(xiàn)行值是變量A，C的值AVALUE[A]={Ri,A}表示A的值既在寄存器Ri中又在內(nèi)存中20PL/0編譯程序的目標代碼結構和代碼生成

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

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

gen(sto,lev-level,adr)

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

lev：當前處理的過程層次

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

CX：為目標代碼code數(shù)組的下標指針23Code:array[0..cxmax]ofinstruction;p414fct=(lit,opr,lod,sto,cal,int,jmp,jpc)P413Instruction=packecrecordP413f:fct;l:0..levmaxa:0..amax;end;24CODE為一維數(shù)組，數(shù)組元素為記錄型數(shù)據(jù)。每一個記錄就是一條目標指令。CX為指令的指針，由0開始順序增加。實際上目標代碼的順序是內(nèi)層過程的排在前邊，主程序的目標代碼在最后。下面我們給出一個PL/0源程序和對應的目標程序的清單。在block入口處生成一條(jmp,0,0)指令，作為過程體入口指令，該指令的第3區(qū)域的'0'需分析到過程體入口時才返填。25

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轉向主程序入口(1)jmp02轉向過程p入口(2)int03過程p入口,為過程p開辟空間(3)lod13取變量b的值到棧頂(4)lit010取常數(shù)10到棧頂(5)opr02次棧頂與棧頂相加(6)sto14棧頂值送變量c中(7)opr00退棧并返回調用點(16)(8)int05主程序入口開辟5個棧空間(9)opr016從命令行讀入值置于棧頂(10)sto03將棧頂值存入變量b中(11)lod03將變量b的值取至棧頂(12)lit00將常數(shù)值0進棧(13)opr09次棧頂與棧頂是否不等(14)jpc024

等時轉(24)（條件不滿足轉）(15)cal02調用過程p(16)lit02常數(shù)值2進棧(17)lod04將變量c的值取至棧頂(18)opr04次棧頂與棧頂相乘(2*c)(19)opr014棧頂值輸出至屏幕(20)opr015換行(21)opr016從命令行讀取值到棧頂(22)sto03棧頂值送變量b中(23)jmp011無條件轉到循環(huán)入口(11)(24)opr00結束退棧IF語句的語義分析-結構變換、地址回填ifconditionthenstatement;conditionstatementVARb,c;READ(b);

ifb#0thenBEGIN

c:=5;WRITE(2*c);

END…

1int052opr0163sto034lod035lit006opr097jpc0148lit059sto0410lit0211lod0412opr0413opr014

14

…

condition目標代碼statement目標代碼IF語句的語義分析-結構變換、地址回填ifconditionthenstatement;caseIFSYM: GetSym();

CONDITION(); if(SYM==THENSYM)GetSym(); elseError(16);

CX1=CX;GEN(JPC,0,0);

STATEMENT();

CODE[CX1].A=CX; break;VARb,c;READ(b);

ifb#0thenBEGIN

c:=5;WRITE(2*c);

END…

1int052opr0163sto034lod035lit006opr097jpc0148lit059sto0410lit0211lod0412opr0413opr014

14

…

CX1=7CX=1428PL/0編譯程序的目標代碼生成是由GEN過程完成的，當語法分析正確,則調用目標代碼生成過程以生成與PL/0語句等價功能的目標代碼，直到編譯正常結束。注意：過程說明部分，變量和常量的說明都不產(chǎn)生目標代碼。

對分程序體入口的處理（見程序文本P424頁block的過程體）

begin(*block*)

dx:=3;

tx0:=tx;

（*保留當前table表指針值,實際為過程名在table表中的位置*）

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

gen(jmp,0,0);29錄過程在code的入口到table中的adr域如下表所示：

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

code[table[tx0].adr].a:=cx;tx0txtable[tx0].adr=cx31過程體入口時的處理table表格管理

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

withtable[tx0]do

begin

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

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

end;

請?zhí)貏e注意dx、tx、cx的作用和如何處理信息之間的連接關系。32CASEWHILESYM: CX1=CX;GetSym();//保留L1的地址

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

CX2=CX;GEN(JPC,0,0);//條件跳轉,L2待定, if(SYM==DOSYM)GetSym(); elseError(18); STATEMENT(FSYS,LEV,TX);//生成S的代碼

GEN(JMP,0,CX1)；//無條件跳轉,轉到L1 CODE[CX2].A=CX;//回填L2 break;switch(SYM){……WhileBDoSBFalseS轉L1L1：L2:CX1CX233條件語句的一般形式：IF條件BTHEN語句S1[ELSE語句S2]IfBThen0(false)S1

。

ElseL1：S2L2CX1CX234Switch(SYM){……caseIFSYM:GetSym();CONDITION(SymSetUnion(SymSetNew(THENSYM,DOSYM),FSYS),LEV,TX);{生成B的代碼}

if(SYM==THENSYM)GetSym();elseError(16);

GEN(JPC,0,0);

STATEMENT(SymSetUnion(SymSetNew(ELSESYM),FSYS),LEV,TX);

{生成S1的代碼}If()CODE[CX1].A=CXElse{CX2=CX;Gen（JMP，0，0）

;{轉向S2}

STATEMENT(SymSetUnion(SymSetNew(ELSESYM),FSYS),LEV,TX);

{生成S2的代碼}

；}break;……}

CX1=CX;SYM!=ELSECODE[CX1].A＝CXCODE[CX2].A＝CXIfBThen0(false)S1

。

ElseL1：S2L2CX1CX235解釋程序還定義了4個寄存器。

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

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

(3)T：棧頂寄存器。

(4)B：基址寄存器。指向每個過程被調用時，在數(shù)據(jù)區(qū)S中給它分配的數(shù)據(jù)段起始地址，也稱基地址。

當源程序經(jīng)過語法分析，如果未發(fā)現(xiàn)錯誤時，由編譯程序調用解釋程序,對目標代碼開始進行解釋執(zhí)行。36

P426

do{i=code[p];p++;switch(i.f){……caseOPR: switch(i.a){/*OPERATOR*/ {case0:/*RETURN*/t=b-1;p=S[t+3];b=S[t+2];break;case1:S[t]=-S[t];break;case2:t--;S[t]=S[t]+S[t+1];break; case3:t--;S[t]=S[t]-S[t+1];break; case4:t--;S[t]=S[t]*S[t+1];break;