編譯原理：第九章目標(biāo)代碼生成(1)

1、 目標(biāo)生成是編譯的最后一個階段，其功能可表示如下：第 9 章 目標(biāo)代碼及其生成目標(biāo)生成中間代碼目標(biāo)代碼符號表其中：中間代碼 - 逆波蘭式，三元式，四元式，語義樹；目標(biāo)代碼 - 機器語言，匯編語言，符 號 表 - 變量的語義詞典，9.1 目標(biāo)代碼生成的基本問題9.2 四元式的目標(biāo)代碼生成算法內(nèi)容提要9.3 一個簡單代碼生成器設(shè)計9.1 目標(biāo)代碼生成的基本問題9.1.1 目標(biāo)代碼選擇 虛擬機及其指令系統(tǒng)： 大多數(shù)編譯程序不產(chǎn)生絕對地址的機器代碼，而是以匯編語言程序作為輸出使代碼生成階段變得容易。此外，指令集的選擇以及指令的執(zhí)行速度問題都是重要因素。為了使算法具有通用性，這里采用的是： 虛擬機寄存器

2、 R0 , R1 , , Rn-1 虛擬機指令系統(tǒng) 指令的基本形式：op Ri , Rk/M操作碼變量的內(nèi)存地址含義：Ri:= (Ri)op(Rk)Ri:= (Ri)op(M)或【注】若 op 為單目運算，則op Ri , Rk/M含義是：Ri:= op(Rk/M) 常用的指令：LD Ri,Rk/M Ri:= (Rk/M)ST Ri,Rk/M Rk/M:=(Ri)FJ Ri, M 若 (Ri)=false 則轉(zhuǎn) MTJ Ri, M 若 (Ri)=true 則轉(zhuǎn) MJMP _, M 無條件轉(zhuǎn) MADD Ri,Rk/M Ri:=(Ri)+(Rk/M)SUB Ri,Rk/M Ri:=(Ri)-(Rk

3、/M)MUL Ri,Rk/M Ri:=(Ri)*(Rk/M)DIV Ri,Rk/M Ri:=(Ri)/(Rk/M)此外還有下述 操作碼 op ：LT(),EQ(=),LE(=),NE(!=)AND(&),OR(|),NO(!)取、存轉(zhuǎn) 向算術(shù)運算邏輯運算 四元式目標(biāo)代碼翻譯示例：【例9.1】( + a b t1 )( - t1 d t2 )SUB R0,dLD R0,a ADD R0,b【例9.2】( + a b t1 )( - c d t2 )LD R1,cLD R0,a ADD R0,b( * t1 t2 t3 )SUB R1,dMUL R0,R1討論 為了精簡代碼，四元式結(jié)果變量值并不急

4、于存儲! 例9.1中的t1的值，系統(tǒng)如何知道是在寄存器R0中？ 例9.2存在寄存器分配問題，顯然，若t2仍然占用寄存器R0,則t1值將丟掉!9.1.2 變量的活躍信息. 變量的定義點和應(yīng)用點 設(shè)有四元式：q( B C A )B,C的應(yīng)用點(q)A的定義點(q). 活躍變量與非活躍變量【活躍變量】一個變量從某時刻(q)起,到下一個定義點止，其間若有應(yīng)用點，則稱該變量在q是活躍的(y),否則稱該變量在q是非活躍的(n)。 【注】我們是在一個基本塊內(nèi)討論變量的活躍信息的，為了處理方便，假定： 臨時變量在基本塊出口后是非活躍的(n)； 非臨時變量在基本塊出口后是活躍的(y)； 【例9.3】求下述基本塊

5、內(nèi)變量的活躍信息：x=(a+b)/(a*(a+b);i=a+b;【解】令 A(l)中的 l 為變量A 在某點的活躍信息(y/n)；則有四元式序列：(+ a b t1 )(* a t1 t3 )(/ t1 t3 x )(= t1 _ i )(+ a b t1 )(+ a b t2 )(* a t2 t3 )(/ t1 t3 t4 )(= t4 _ x )(+ a b t5 )(= t5 _ i )優(yōu)化后(+ a( ) b( ) t1( ) )(* a( ) t1( ) t3( ) )(/ t1( ) t3( ) x( ) )(= t1( ) _ i( ) ) 附有活躍信息的四元式：yyyyyyy

6、yynn. 基本塊內(nèi)活躍信息求解算法 支持: 在符號表上增設(shè)一個信息項（ L ） Lname活躍信息 四元式中變量 X 的附加信息項：X( L ) 取值： L=n/y(不活躍/活躍) ； 初值：基本塊內(nèi)各變量 SYMBLX( L )分別填寫：若 X為非臨時變量 則置 X( y ); 否則置 X( n ) 逆序掃描基本塊內(nèi)各四元式(設(shè)為 q:( B C A) ):執(zhí)行： QTq:A( L ):= SYMBLA( L ); SYMBLA( L ):=( n ); QTq:B,C( L ):= SYMBLB,C( L ); SYMBLB,C( L ):=( y ); 算法 活躍信息生成過程示例： 【

7、例9.4】基本塊內(nèi)下述四元式序列如下：QTq: q:( B( L ) C( L ) A( L )(+ a( ) b( ) t1( )(- c( ) d( ) t2( )(* t1( )t2( )t3( )(- a( ) t3( )t4( )(/ t1( ) 2 t5( ) (+ t4( )t5( ) x( ) y n n y n y y n y y n y y y y y yL abcdt1t2xt5t4t3SYMBLX( L )yyyynnynnnnyynynyynyynyynyy9.1.3 寄存器的分配問題 寄存器操作快且指令短，如何充分利用它？ 寄存器分配三原則：【主動釋放】如果B已經(jīng)在

8、寄存器Ri中，則選擇Ri: 若 B 活躍，則要保存B的值,方法是：若有空閑寄存器Rj,則生成指令 ST Ri,Rj；否則生成指令 ST Ri,B； 修改描述表：刪除 B,填寫 A?！具x空閑者】從空閑寄存器中選一 Ri；并把 A 填入描述表：。 【強迫釋放】剝奪一 Ri: 處理辦法同規(guī)則 。 設(shè)置描述表: RDL(R0,R1, Rn):即指明 當(dāng)前變量 x 值在寄存器R1中！如何為A分配寄存器？若可交換,則C也可! 用以記錄寄存器的當(dāng)前狀態(tài)：如 RDL.R1=x設(shè)當(dāng)前四元式： q: A = B C支持： 寄存器分配原則；活躍變量概念。 寄存器分配過程示例： 【例9.5】 設(shè)有三個寄存器：R0,R

9、1,R2 OBJp QTqR0R1RDLR2(+ a(y) b(y) t1(y)(- c(y) d(y) t2(y)(* t1(y)t2(n)x(y)(/ a(n) x(n) x(y)(= x(y) _ a(y)(= a(y) _ y(n)(- x(y)t1(n) y(y) LD R1,c SUB R1,dt1LD R0,a ADD R0,bt2ST R0,R2LD R1,axLD R1,aySUB R1,t111MUL R0,R1yxaDIV R1,R0ST R1,R0ST R0,R212【注】 一個變量在同一時刻只能占有一個寄存器! 基本塊出口時，寄存器中的活躍變量應(yīng)保存其值。t1t2xy

10、xya紅色變量為預(yù)分配!t1xx9.1.4 目標(biāo)代碼生成問題 目標(biāo)代碼生成是以基本塊為單位的，在生成目標(biāo)代碼時要注意如下三個問題： 基本塊開始時所有寄存器應(yīng)是空閑的；結(jié)束基本快時應(yīng)釋放所占用的寄存器。 一個變量被定值(被賦值)時，要分配一個寄存器 Ri保留其值，并且要填寫相應(yīng)的 描述表 RDL.Ri。 為了生成高效的目標(biāo)代碼，生成算法中要引用寄存器分配三原則和變量的活躍信息。QTq 四元式區(qū)；OBJp 目標(biāo)區(qū)；環(huán)境設(shè)置RDL(R0,R1, Rn) 寄存器狀態(tài)描述表；SEM(m) 語義棧(用于信息暫存)；【例9.6】單寄存器下表達(dá)式目標(biāo)代碼生成：R 寄存器；RDL 描述表；SEM 語義棧。設(shè) O

11、BJp QTqBSEMRDL(+ a(y) b(y) t1(y)(- c(y) d(y) t2(y)(* t1(y)t2(n)t3(y)(- a(y) t3(n)t4(y)(/ t1(n) 2 t5(y)(+ t4(n)t5(n) x(y)ST R,t1 LD R,ct1LD R,a ADD R,bt2SUB R,dMUL R,t1t3ST R,t3 LD R,aSUB R,t3t4ST R,t4 LD R,t11112DIV R,2t513ADD R,t4xt1t2t3t4t5x紅色變量為預(yù)分配!【例9.7】單寄存器下如：if(ab)x=(a+b)*c; ( a(y) b(y) t1(y)(

12、if t1(n) _ _ )(+ a(y) b(y) t2(y)(* t2(n) c(y) x(y)(el _ _ _ )(* a(y) b(y) t3(y)(- 5 t3(n) x(y)(ie _ _ _ )FJ R,？LD R,aLD R,aMUL R,cJMP_,？ ST R,t31213SUB R,t314ST R,x1515ST R,x11GT R,belse x=5-a*b;LD R,5條件語句目標(biāo)代碼生成：人工翻譯過程ADD R,bMUL R,bLD R,a待返填1待返填2返填時機1返填時機2(接上頁)如：if(ab)x=(a+b)*c;else x=5-a*b; OBJp QU

13、ATqBSEMRDL( a(y) b(y) t1(y)(if t1(y) _ _ )(+ a(y) b(y) t2(y)(* t2(n) c(y) x(y)(el _ _ _ )(* a(y) b(y) t3(y)(- 5 t3(y) x(y)(ie _ _ _ )FJ R,?t1LD R,at2LD R,a ADD R,bMUL R,cxJMP_,? LD R,a MUL R,bt3 ST R,t3 LD R,51213SUB R,t3x14ST R,x1515ST R,x11GT R,bt1t2xt3xSEM棧用于保存待返填地址!計算機的目標(biāo)代碼生成過程： 單寄存器下目標(biāo)代碼生成要點： 表達(dá)式四元式 q:( B C A ) 為 A 預(yù)分配寄存器，并在 RDL表中登記！ 賦值四元式 q:( = B _ A ) 為 A 預(yù)分配寄存器，然后編賦值指令 ！ 轉(zhuǎn)向四元式 q:( go B _ _ )， 先釋放寄存器,后編轉(zhuǎn)向指令,保存該地址于SEM棧中！ 【釋放寄存器】編存儲指令,保存占有寄存器的活躍變量值；通常發(fā)生在如下兩個時刻：目標(biāo)代碼生成是以單個四元式為單位進(jìn)行的！注 為結(jié)果變量申請寄存器時