第9章目標代碼生成

1、 第第 9 章章 目標代碼及其生成目標代碼及其生成 目標代碼生成目標代碼生成是編譯的最后一個階段，其功能表示如下：是編譯的最后一個階段，其功能表示如下：目標生成目標生成中間代碼中間代碼目標代碼目標代碼符號表符號表其中：其中：中間代碼中間代碼 逆波蘭式，三元式，四元式，語義樹；逆波蘭式，三元式，四元式，語義樹；目標代碼目標代碼 機器語言，匯編語言，機器語言，匯編語言，符符 號號 表表 變量的語義詞典，變量的語義詞典，9.1 目標代碼生成的基本問題目標代碼生成的基本問題9.3 多寄存器下的目標代碼生成算法多寄存器下的目標代碼生成算法內(nèi)容內(nèi)容提要提要9.2 一個簡單代碼生成器設計一個簡單代碼生成器設

2、計9.1 目標代碼生成的基本問題目標代碼生成的基本問題. 目標代碼選擇問題目標代碼選擇問題v 虛擬機及其指令系統(tǒng)：虛擬機及其指令系統(tǒng)： 大多數(shù)編譯程序不產(chǎn)生絕對地址的機器代碼，而是大多數(shù)編譯程序不產(chǎn)生絕對地址的機器代碼，而是以以匯編語言程序匯編語言程序作為輸出，使代碼生成階段變得容易。作為輸出，使代碼生成階段變得容易。 此外，此外，指令集的選擇指令集的選擇以及以及指令的執(zhí)行速度指令的執(zhí)行速度問題都問題都是是重要因素重要因素。為了使算法具有通用性，這里采用的是：。為了使算法具有通用性，這里采用的是： 虛擬機寄存器虛擬機寄存器 R0 , R1 , , Rn-1 虛擬機指令系統(tǒng)虛擬機指令系統(tǒng) 指令的

3、基本形式：指令的基本形式：op Ri , Rj/M操作碼操作碼變量的內(nèi)變量的內(nèi)存地址存地址含義：含義： Ri = (Ri) op (Rj)Ri = (Ri) op (M)或或【注注】若若 op 為單目運算，則含義是：為單目運算，則含義是：Ri = op(Rj/M)9.1 目標代碼生成的基本問題目標代碼生成的基本問題(續(xù)續(xù)1) 常用的指令：常用的指令：LD Ri, Rj/M Ri = (Rj/M)ST Ri, Rj/M Rj/M =(Ri)FJ Ri, M 若若 (Ri)=false 則轉則轉 MTJ Ri, M 若若 (Ri)=true 則轉則轉 MJMP _, M 無條件轉無條件轉 MADD

4、 Ri, Rj/M Ri =(Ri) + (Rj/M)SUB Ri, Rj/M Ri =(Ri) - - (Rj/M)MUL Ri, Rj/M Ri =(Ri) * * (Rj/M)DIV Ri, Rj/M Ri =(Ri) / (Rj/M)此外還有下述此外還有下述 操作碼操作碼 op ：LT(),EQ(=),LE(=),NE(!=)AND(&),OR(|),NO(!)取、存取、存轉轉 向向算術算術運算運算關系、邏關系、邏輯運算輯運算9.1 目標代碼生成的基本問題目標代碼生成的基本問題(續(xù)續(xù)2).活躍變量與非活躍變量活躍變量與非活躍變量1. 變量的定義點和應用點變量的定義點和應用點 設

5、有四元式：設有四元式：q( B C A )B,C的應用點的應用點(q)A的定義點的定義點(q)2. 活躍變量與非活躍變量活躍變量與非活躍變量【活躍變量活躍變量】一個一個變量變量從某時刻從某時刻(q)起起，到下一個到下一個定義點止，其間若定義點止，其間若有應用點有應用點，則稱該變量在，則稱該變量在q是活是活躍的躍的(y)，否則稱否則稱該該變量變量在在q是非活躍的是非活躍的(n)。 【注注】我們是在我們是在一個基本塊內(nèi)一個基本塊內(nèi)討論討論變量的活躍信息變量的活躍信息的，為了處理方便，假定：的，為了處理方便，假定：(1) 臨時變量在臨時變量在基本塊出口基本塊出口后后是非活躍的是非活躍的(n)； (2

6、) 非臨時變量在非臨時變量在基本塊出口基本塊出口后后是活躍的是活躍的(y)； 9.1 目標代碼生成的基本問題目標代碼生成的基本問題(續(xù)續(xù)3)【例例9.1】求下述基本塊內(nèi)變量的求下述基本塊內(nèi)變量的活躍信息活躍信息：x=(a+b)/(a*(a+b);i=a+b;【解解】令令 A(i)中的中的 i 為為變量變量A 在某點的在某點的活躍信息活躍信息(y/n)；則有四元式序列：則有四元式序列：(1) ( + a b t1 )(2) ( * a t1 t3 )(3) ( / t1 t3 x )(4) ( = t1 _ i )(1) ( + a b t1 )(2) ( + a b t2 )(3) (* a

7、t2 t3 )(4) ( / t1 t3 t4 )(5) ( = t4 _ x )(6) ( + a b t5 )(7) ( = t5 _ i )優(yōu)化后優(yōu)化后(1) (+ a(y) b (y) t1(y) )(2) (* a(y) t1(y) t3(y) )(3) (/ t1(y) t3(n) x(y) )(4) (= t1(n) _ i(y) ) 附有附有活躍信息活躍信息的四元式：的四元式：9.1 目標代碼生成的基本問題目標代碼生成的基本問題(續(xù)續(xù)4).寄存器的分配問題寄存器的分配問題 寄存器寄存器操作快操作快且且指令短指令短，如何充分利用它如何充分利用它？2. 寄存器寄存器分配規(guī)則分配規(guī)則

8、：設當前四元式：設當前四元式：q: A=B C(1)【主動釋放主動釋放】如果如果B已經(jīng)在寄存器已經(jīng)在寄存器Ri中，則選擇中，則選擇Ri: 若若 B 活躍活躍，則要保存，則要保存B的值，方法是：若有空閑的值，方法是：若有空閑寄存器寄存器Rj，則生成指令則生成指令 ST Ri,Rj； 否則生成指令否則生成指令 ST Ri,B； 修改修改描述表：描述表：在在Ri中刪除中刪除 B，填寫，填寫A。(2)【選空閑者選空閑者】從空閑寄存器中選一從空閑寄存器中選一 Ri； 并把并把 A 填入填入Ri的描述表中。的描述表中。 (3)【強迫釋放強迫釋放】剝奪一個剝奪一個 Ri，具體處理辦法同規(guī)則，具體處理辦法同規(guī)

9、則(1)。1. 設置設置描述表描述表，記錄記錄寄存器寄存器和和變量變量的當前狀態(tài)的當前狀態(tài)： 某個寄存器保留著哪個變量的值某個寄存器保留著哪個變量的值; 某個變量的值是在某寄存器中還是在內(nèi)存中。某個變量的值是在某寄存器中還是在內(nèi)存中。如何如何為為A分配分配寄存寄存器？器？若若 可交換可交換,則則C也可也可!9.1 目標代碼生成的基本問題目標代碼生成的基本問題(續(xù)續(xù)5) 目標代碼生成是以目標代碼生成是以基本塊為單位基本塊為單位的，在生成目標代的，在生成目標代碼時要注意如下三個問題：碼時要注意如下三個問題：(1) 基本塊基本塊開始開始時所有寄存器應是時所有寄存器應是空閑空閑的；基本塊的；基本塊結束

10、結束時應時應釋放釋放所占用的寄存器。所占用的寄存器。(2) 一個變量被賦值時，要分配一個一個變量被賦值時，要分配一個寄存器寄存器保留其值，保留其值，并且要填寫相應的并且要填寫相應的描述表描述表?！纠?.2】設有語句片斷：設有語句片斷：while (i10) x=(a*b)/(a+(a*b);i=x;i=1;. 目標代碼生成問題目標代碼生成問題(3) 為了生成為了生成高效的目標代碼高效的目標代碼，生成算法中要引用，生成算法中要引用寄存寄存器的分配原則器的分配原則和和變量的活躍信息。變量的活躍信息。 目標代碼生成示例：目標代碼生成示例：假定：有兩個可用寄存器假定：有兩個可用寄存器 R0,R1則從

11、四元式到目標代碼生成過程如下所示：則從四元式到目標代碼生成過程如下所示：描述表描述表while (i10) x=(a*b)/(i+(a*b);i=x;i=1; OBJp QTq R0 R1 內(nèi)存內(nèi)存BFJ R0, ? LD R0,i GT R0,10JMP _, LD R0,1 ST R0,iit1LD R0,a MUL R0,b t2ST R0,R1 ADD R0,i DIV R1,R0ST R1,x11 12t3xST R1,i13ix14t214ab(1) (= 1 _ i )(2) (wh _ _ _ )(3) ( i 10 t1 )(4) ( do t1 _ _ )(5) (* a

12、b t2 )(6) (+ i t2 t3 )(7) (/ t2 t3 x )(8) (= x _ i )(9) (we _ _ _ )(10)9.2 一個簡單代碼生成器設計一個簡單代碼生成器設計. 生成環(huán)境生成環(huán)境v 虛擬機虛擬機：單一寄存器：單一寄存器 R ; 指令形式指令形式 p:(op R , M )變量內(nèi)存地址變量內(nèi)存地址v 表、區(qū)和棧表、區(qū)和棧： SYMBLi 符號表；符號表； QTq 四元式區(qū)四元式區(qū)(附有變量的附有變量的活躍信息活躍信息)； OBJp 目標代碼區(qū)；目標代碼區(qū)； SEMm 語義棧語義棧(登記待登記待返填返填的目標地址的目標地址)；R = (R)op(M)含義：含義：

13、R = op(M)或或 CODE(op R,M;)(送代碼函數(shù)送代碼函數(shù))把目標代碼送目標區(qū)；把目標代碼送目標區(qū)； RDV 寄存器狀態(tài)變量；寄存器狀態(tài)變量；v 變量和函數(shù)變量和函數(shù)：RDV= 0 (R空閑空閑) ； RDV= X (R被被X占用占用)； 可送多個代碼可送多個代碼 BACK(pi,pj)(返填函數(shù)返填函數(shù))把地址把地址 pj 返填到地址返填到地址 pi 中；中；9.2 一個簡單代碼生成器設計一個簡單代碼生成器設計(續(xù)續(xù)1)開始開始預處理預處理取下一取下一基本塊基本塊取到了取到了變量變量活躍信息活躍信息生成生成取下一取下一四元式四元式：q基本塊基本塊出口出口結束結束結束處理結束處理

14、RDV=0執(zhí)行執(zhí)行q生成生成執(zhí)行執(zhí)行q生成生成yynn包括劃分包括劃分基本塊基本塊. 主控程序主控程序. 目標代碼生成算法目標代碼生成算法q 單寄存器下的目標代碼單寄存器下的目標代碼生成要點生成要點： 1.表達式四元式表達式四元式 q:( B C A ) 釋放寄存器，編運算指令，釋放寄存器，編運算指令，A不存儲但登記在不存儲但登記在RDV中！中！ 2.賦值四元式賦值四元式 q:( = B _ A ) 編取編取B(B在在R中則免，否則中則免，否則釋放寄存器釋放寄存器)、存、存A指令！指令！ 3.轉向四元式轉向四元式 q:( do B _ _ )， 釋放寄存器，編轉向指令，保存該地址于釋放寄存器，

15、編轉向指令，保存該地址于SEM棧中！棧中！ 【釋放寄存器釋放寄存器】編編存儲存儲指令，保存占有寄存器的指令，保存占有寄存器的活躍活躍變量變量值；通常發(fā)生在如下兩個時刻：值；通常發(fā)生在如下兩個時刻：目標代碼生成是以目標代碼生成是以單個四元式單個四元式為單位進行的！為單位進行的！注注(1) 為結果變量申請寄存器時為結果變量申請寄存器時(2) 基本塊出口時基本塊出口時. 目標代碼生成算法目標代碼生成算法(續(xù)續(xù)2) 1. 表達式四元式的目標代碼生成：表達式四元式的目標代碼生成： 設當前掃描的四元式設當前掃描的四元式 q: ( B C A) (1) 按檢索到的信息生成目標代碼：按檢索到的信息生成目標代碼

16、： 算符算符 對應對應的的操作碼操作碼 若若 RDV=0 則則 CODE( LD R,B ； R,C ); 若若 RDV=B 則則 若若 B(y) 則則 CODE( ST R,B ； R,C ); 否則否則 CODE( R,C ); 若若 RDV=C 且且 可交換可交換 則則 若若 C(y) 則則 CODE( ST R,C ； R,B ); 否則否則 CODE( R,B ); 若若 D(y) 則則 CODE( ST R,D ; LD R,B ; R,C );否則否則 CODE( LD R,B ; R,C );(2) 變量變量 A 申請寄存器申請寄存器 RDV = A ; 若若 RDV=D（上述

17、三種情況之外上述三種情況之外 ） 則則 如如 B+C OBJp QTqBSEMRDV. 目標代碼生成算法目標代碼生成算法(續(xù)續(xù)1)【例例9.3】設有賦值語句（四元式序列）：設有賦值語句（四元式序列）：x=a-(a+b)*(c-d)+(a+b)/2;ST R,t1 LD R,c t1(y)LD R,a ADD R,b(1) (+ a(y) b(y) t1(y)(2) (- c(y) d(y) t2(y)(3) (* t1(y) t2(n) t3(y)(4) (- a(y) t3(n) t4(y)(5) (/ t1(n) 2 t5(y)(6) (+ t4(n) t5(n) x(y) t2(y)SU

18、B R,dMUL R,t1 t3(y)ST R,t3 LD R,aSUB R,t3 t4(y)ST R,t4 LD R,t11112DIV R,2 t5(y)13ADD R,t4 x(y) 設當前四元式設當前四元式 q: (= B _ A). 目標代碼生成算法目標代碼生成算法(續(xù)續(xù)3)(1) 若若 RDV=0 則則 CODE( LD R,B ; ST R,A ); (2) 若若 RDV=B 則則 CODE( ST R,A );(3) 若若 RDV=D（D!=B ）則）則 若若 D(y) 則則 CODE( ST R,D ; LD R,B ; ST R,A ); 2. 賦值語句四元式的目標代碼生成

19、：賦值語句四元式的目標代碼生成：RDV =B RDV =B;否則否則 CODE( LD R,B ; ST R,A ); . 目標代碼生成算法目標代碼生成算法(續(xù)續(xù)4)【例例9.4】設有條件語句（四元式序列）：設有條件語句（四元式序列）：if(ab)x=(a+b)*c;else x=5-a*b; OBJp QTqBSEMRDVFJ R, ? t1(y)LD R,a GT R,bt2(y)LD R,a ADD R,bMUL R,cx(y)JMP_,? LD R,a MUL R,bt3(y) ST R,t3 LD R,51213SUB R,t3x(y)14ST R,x1515ST R,x 11nex

20、t (1) ( a(y) b(y) t1(y)(2) (if t1(n) _ _ )(3) (+ a(y) b(y) t2(y)(4) (* t2(n) c(y) x(y)(5) (el _ _ _ )(6) (* a(y) b(y) t3(y)(7) (- - 5 t3(n) x(y)(8) (ie _ _ _ ) (三三) 設當前四元式設當前四元式 q:( ie _ _ _ ) (二二) 設當前四元式設當前四元式 q:( el _ _ _ ). 目標代碼生成算法目標代碼生成算法(續(xù)續(xù)5)(3) 若若 RDV=D（D!=B） 則則 (1) 返填轉向地址返填轉向地址： POP(p);BACK(

21、p,p+2)v 返填轉向地址返填轉向地址： POP(p);BACK(p,p+1) 若若 D(y) 則則 CODE( ST R,D ; LD R,B ;FJ R,_ ); PUSH(p) ；RDV =0; 否則否則 CODE( LD R,B ;FJ R,_ ); (2) 編轉向指令編轉向指令：CODE( JMP _, _ ); PUSH(p) (一一) 設當前四元式設當前四元式 q:( if B _ _ )(1) 若若 RDV=0 則則 CODE( LD R,B ; FJ R,_ ); PUSH(p)； 3. 條件語句四元式的目標代碼生成：條件語句四元式的目標代碼生成：(2) 若若 RDV=B

22、則則 CODE( FJ R,_ ); PUSH(p)；RDV =0;SEM棧棧頂?shù)刂窂楉數(shù)刂窂椀降絧中中把地址把地址p+2填到填到p中中當前目標當前目標代碼編號代碼編號 back. 目標代碼生成算法目標代碼生成算法(續(xù)續(xù)6) OBJp QTqBSEMRDVFJ R, ? LD R,i LT R,10LD R,a MUL R,bST R,t2ST R,t3DIV R,t31414JMP _, 【例例9.5】設有循環(huán)語句（四元式序列）：設有循環(huán)語句（四元式序列）：while (i10) x=(a*b)/(i+(a*b);i=x;ADD R,i LD R,t2ST R,i11ST R,12xt1(y

23、)t2(y)x(y)t3(y)13(4) (* a(y) b(y) t2(y)(1) (wh _ _ _ )(2) ( i(y) 10 t1(y)(3) ( do t1(n) _ _ )(5) (+ i(y) t2(y) t3(y)(6) (/ t2(n) t3(n) x(y)(7) (= x(y) _ i(y)(8) (we _ _ _ )(9)next (一一) 設當前四元式設當前四元式 q:(wh _ _ _ )v 記住表達式入口地址：記住表達式入口地址： PUSH(p+1). 目標代碼生成算法目標代碼生成算法(續(xù)續(xù)7) 4. 循環(huán)語句四元式的目標代碼生成：循環(huán)語句四元式的目標代碼生成：

24、(二二) 設當前四元式設當前四元式 q:(do B _ _ )(1) 若若 RDV=0 則則 CODE( LD R,B ; FJ R,_ ); PUSH(p)； (2) 若若 RDV=B 則則 CODE( FJ R,_ ); PUSH(p); RDV =0;(3) 若若 RDV=D（D!=B） 則則 若若 D(y) 則則 CODE( ST R,D ; LD R,B ;FJ R,_ ); PUSH(p); RDV =0;否則否則 CODE( LD R,B ;FJ R,_ ); (三三) 設當前四元式設當前四元式 q:(we _ _ _ )(1) 返填轉向地址返填轉向地址： POP(p);BACK

25、(p,p+2);(2) 編轉向表達式入口指令編轉向表達式入口指令：POP(p);CODE(JMP _,p); back9.3.1 基本塊內(nèi)基本塊內(nèi)活躍信息活躍信息求解算法求解算法 支持支持: (1) 在符號表上增設兩個信息項（在符號表上增設兩個信息項（U,L）:LUname待用信息待用信息活躍信息活躍信息(2) 四元式中變量的附加信息項：四元式中變量的附加信息項：X(U,L) 取值：取值：U=n/q(不待用不待用/q待用待用),q為四元式序號；為四元式序號； 取值：取值：L=n/y(不活躍不活躍/活躍活躍) ；(1) 初值：基本塊內(nèi)各變量初值：基本塊內(nèi)各變量 SYMBLX(U,L)分別填寫：分

26、別填寫：若若 X為為非臨時變量非臨時變量 則置則置 X(n,y) , 否則置否則置 X(n,n)(2) 逆序逆序掃描基本塊內(nèi)各四元式掃描基本塊內(nèi)各四元式(設為設為 q:( B C A) ):執(zhí)行：執(zhí)行： QTq:A(U,L) = SYMBLA(U,L); SYMBLA(U,L) =(n,n); QTq:B,C(U,L) = SYMBLB,C(U,L); SYMBLB,C(U,L) =(q,y); 算法算法9.3 多寄存器下的目標代碼生成算法多寄存器下的目標代碼生成算法 L UXabcdt1t2xt5t4t3 9.3 多寄存器下的目標代碼生成算法多寄存器下的目標代碼生成算法(續(xù)續(xù)1) 【例例9.

27、6】基本塊內(nèi)下述四元基本塊內(nèi)下述四元式序列活躍信息生成過程：式序列活躍信息生成過程：QTq: q:( B(U,L) C(U,L) A(U,L)SYMBLX(U,L)(1) (+ a( , ) b( , ) t1( , )(2) (- c( , ) d( , ) t2( , )(3) (* t1( , ) t2( , ) t3( , )(4) (- a( , ) t3( , ) t4( , )(5) (/ t1( , ) 2 t5( , ) (6) (+ t4( , ) t5( , ) x( , )ynynynynnnnnynnnnnnnn ynnn nn n6y6y6 ynnn n5y6 yn

28、nn y4yn n4y4 ynn5 y3yn n3y3 ynnn y2yn y 2y3 ynn4 y1yn y1y9.3 多寄存器下的目標代碼生成算法多寄存器下的目標代碼生成算法(續(xù)續(xù)2) 支持支持: (1) 設置設置描述表描述表 RDLR1,R2,Rn;M，記錄寄存記錄寄存(2) 幾個變量可共享同一寄存器！如幾個變量可共享同一寄存器！如 RDL.Ri=X,Y;算法算法器器Ri，變量，變量X的的現(xiàn)行值狀態(tài)現(xiàn)行值狀態(tài)！9.3.2 寄存器分配函數(shù)寄存器分配函數(shù) GETR(q) 設當前掃描的四元式為設當前掃描的四元式為 q:( B C A ). 【主動釋放主動釋放】 若若 B(U,L)=( ,y)

29、且且 B RDL.M 則則 若有若有 RDL.Rj=，則則否則否則 CODE( ST Ri,B );RDL.Ri- -=B; RDL.M+=B; 否則否則 RDL.Ri- -=B;1. 若有若有Ri，使，使RDL.Ri=B ;則則 CODE( ST Ri,Rj );RDL.Ri- -=B;RDL.Rj=B; R=Ri;轉轉 .;刪除刪除B加入加入B存入存入B僅有僅有 2. 若有若有Ri，使，使 RDL.Ri=C 且且 可交換可交換，則，則 交換交換B,C(改變四元式改變四元式)；轉；轉 ;.【選空閑者選空閑者】若有若有RDL.Ri=,則則 R=Ri ;轉轉 ;.【強迫釋放強迫釋放】RDL.M- -=A; RETURN( R,B=LOCR(B);C=LOCR(C) ); 剝奪一個剝奪一個 Ri (剝奪條件是剝奪條件是 對對 每一個每一個DRDL.Ri： D( ,n) 或或 D(較大較大,y) , 或或 Ri中共享變量數(shù)最少中共享變量數(shù)最少,) 對每一個對每一個 DRDL.Ri:.【實施分配實施分配】 若若 D(U,L)=( ,y)且且 D RDL.M 則則 CODE( ST Ri,D ); RDL.Ri- -=D;RDL