編譯原理第11章

1、第十一章第十一章 目標(biāo)代碼生成目標(biāo)代碼生成介紹實(shí)現(xiàn)簡(jiǎn)單代碼生成器需要考慮的問題；介紹實(shí)現(xiàn)簡(jiǎn)單代碼生成器需要考慮的問題；寄存器分配的原則；寄存器分配的原則；使用待用信息鏈的代碼生成算法；使用待用信息鏈的代碼生成算法；按減少執(zhí)行代價(jià)的原則，為循環(huán)生成目標(biāo)代碼按減少執(zhí)行代價(jià)的原則，為循環(huán)生成目標(biāo)代碼11.1 基本問題基本問題 11.1 基本問題基本問題 一、代碼生成器在編譯程序中的位置：一、代碼生成器在編譯程序中的位置：二、代碼生成器的輸入：中間代碼及符號(hào)表信息；二、代碼生成器的輸入：中間代碼及符號(hào)表信息； 三、代碼生成器的輸出：目標(biāo)代碼（絕對(duì)機(jī)器代碼、可再定位機(jī)器三、代碼生成器的輸出：目標(biāo)代碼（絕

2、對(duì)機(jī)器代碼、可再定位機(jī)器 代碼、匯編語言代碼）；代碼、匯編語言代碼）； 四、寄存器分配四、寄存器分配 1 1、寄存器分配期間、寄存器分配期間: :為程序選擇一組要駐留在寄存器中的變量；為程序選擇一組要駐留在寄存器中的變量； 2 2、寄存器指派階段、寄存器指派階段: :為變量指派具體寄存器；為變量指派具體寄存器； 五、選擇計(jì)算順序五、選擇計(jì)算順序 11.2 目標(biāo)機(jī)器模型目標(biāo)機(jī)器模型 11.2 目標(biāo)機(jī)器模型目標(biāo)機(jī)器模型 一、多個(gè)通用寄存器：也可做累加器和變址器；一、多個(gè)通用寄存器：也可做累加器和變址器； 二、指令類型：二、指令類型： 三、操作碼三、操作碼opop：ADD(ADD(加加) )、SUB

3、(SUB(減減) )、MUL(MUL(乘乘) )、DIV(DIV(除除) )； 11.2 目標(biāo)機(jī)器模型目標(biāo)機(jī)器模型 四、基本指令：四、基本指令： 1 1、LD RiLD Ri , B: , B: 把把B B單元的內(nèi)容取到寄存器單元的內(nèi)容取到寄存器RiRi，即，即 ( B )( B )RiRi； 2 2、ST RiST Ri , B: , B: 把寄存器把寄存器RiRi的內(nèi)容存到的內(nèi)容存到B B單元，即單元，即 ( Ri)( Ri)B B； 3 3、J X: J X: 無條件轉(zhuǎn)向無條件轉(zhuǎn)向X X單元；單元； 4 4、CMP A , B: CMP A , B: 把把A A單元和單元和B B單元的值

4、進(jìn)行比較，并根據(jù)比較情況把機(jī)器內(nèi)部單元的值進(jìn)行比較，并根據(jù)比較情況把機(jī)器內(nèi)部 特征寄存器特征寄存器CTCT置成相應(yīng)狀態(tài)。置成相應(yīng)狀態(tài)。CTCT占兩個(gè)二進(jìn)位，根據(jù)占兩個(gè)二進(jìn)位，根據(jù)ABAB分別分別 置置CTCT為為0 0或或1 1或或2 2； 5 5、J op X: J op X: 根據(jù)根據(jù)CTCT的狀態(tài)轉(zhuǎn)向的狀態(tài)轉(zhuǎn)向X X單元單元 （opop為為 、）；）； 11.3一個(gè)簡(jiǎn)單的代碼生成器一個(gè)簡(jiǎn)單的代碼生成器 11.311.3一個(gè)簡(jiǎn)單的代碼生成器一個(gè)簡(jiǎn)單的代碼生成器 一、功能：依次把每條中間代碼轉(zhuǎn)換成目標(biāo)代碼，并在基本塊內(nèi)一、功能：依次把每條中間代碼轉(zhuǎn)換成目標(biāo)代碼，并在基本塊內(nèi) 考慮充分利用寄存

5、器等問題；考慮充分利用寄存器等問題； 例：例：11.3一個(gè)簡(jiǎn)單的代碼生成器一個(gè)簡(jiǎn)單的代碼生成器 二、待用信息二、待用信息 1 1、含義：某變量被定值后，將在何處被引用；、含義：某變量被定值后，將在何處被引用； 2 2、獲取待用信息的方法：從基本塊的出口由后向前掃描，對(duì)每、獲取待用信息的方法：從基本塊的出口由后向前掃描，對(duì)每 個(gè)變量建立待用信息鏈和活躍變量信息鏈；個(gè)變量建立待用信息鏈和活躍變量信息鏈； 3 3、記錄待用信息和活躍信息：符號(hào)表增待用信息和活躍信息欄；、記錄待用信息和活躍信息：符號(hào)表增待用信息和活躍信息欄； 4 4、計(jì)算變量待用信息和活躍信息的算法：計(jì)算變量待用信息和活躍信息的算法：

6、 11.3一個(gè)簡(jiǎn)單的代碼生成器一個(gè)簡(jiǎn)單的代碼生成器 例：計(jì)算變量的例：計(jì)算變量的 待用信息和待用信息和 活躍信息活躍信息11.3一個(gè)簡(jiǎn)單的代碼生成器一個(gè)簡(jiǎn)單的代碼生成器 三、寄存器描述和地址描述三、寄存器描述和地址描述 1 1、寄存器描述數(shù)組、寄存器描述數(shù)組RValueRValue：記錄寄存器使用情況：記錄寄存器使用情況( (空閑或已分配空閑或已分配) ) 2 2、變量地址描述數(shù)組、變量地址描述數(shù)組AValueAValue：記錄各變量現(xiàn)行值的存放位置：記錄各變量現(xiàn)行值的存放位置( (在在 寄存器或內(nèi)存單元寄存器或內(nèi)存單元) )； 四、四、基本塊內(nèi)代碼生成算法基本塊內(nèi)代碼生成算法 對(duì)塊內(nèi)每個(gè)中間

7、代碼對(duì)塊內(nèi)每個(gè)中間代碼 i: A:= B op Ci: A:= B op C，依次執(zhí)行：，依次執(zhí)行：11.3一個(gè)簡(jiǎn)單的代碼生成器一個(gè)簡(jiǎn)單的代碼生成器 過程過程GetRegGetReg算法算法( (參數(shù)為參數(shù)為i:Ai:A:=B op C ,:=B op C ,返回存放返回存放A A值的寄存器值的寄存器R) R) 10.1 概述概述基本塊內(nèi)代碼生成算法流程圖：基本塊內(nèi)代碼生成算法流程圖：10.1 概述概述修改修改RValue和和AValue流程圖流程圖 :11.3一個(gè)簡(jiǎn)單的代碼生成器一個(gè)簡(jiǎn)單的代碼生成器 例：例：中間代碼中間代碼目標(biāo)代碼目標(biāo)代碼RValueRValueAValueAValueT:

8、= A BT:= A BLD R0 , ALD R0 , ASUB R0 , B SUB R0 , B R0R0含有含有T TT T在在R0R0中中U:= A CU:= A CLD R1 , ALD R1 , ASUB R1 , CSUB R1 , CR0R0含有含有T TR1R1含有含有U UT T在在R0R0中中U U在在R1R1中中V:= T + UV:= T + UADD R0 , R1 ADD R0 , R1 R0R0含有含有V VR1R1含有含有U UV V在在R0R0中中U U在在R1R1中中W:= V + UW:= V + UADD R0 , R1ADD R0 , R1R0R0

9、含有含有W WW W在在R0R0中中11.4寄存器分配寄存器分配 11.4寄存器分配寄存器分配 一、問題引入：如何有效的利用寄存器；一、問題引入：如何有效的利用寄存器； 1 1、基本塊內(nèi)：、基本塊內(nèi)： 運(yùn)算對(duì)象的值在寄存器中運(yùn)算對(duì)象的值在寄存器中, ,則把該寄存器作為操作數(shù)地址；則把該寄存器作為操作數(shù)地址； 盡可能把各變量的現(xiàn)行值保存在寄存器中；盡可能把各變量的現(xiàn)行值保存在寄存器中； 基本塊中不再引用的變量所占用的寄存器及早釋放；基本塊中不再引用的變量所占用的寄存器及早釋放； 2 2、循環(huán)內(nèi)：、循環(huán)內(nèi)： 按執(zhí)行代價(jià)把寄存器固定分配給幾個(gè)變量單獨(dú)使用；按執(zhí)行代價(jià)把寄存器固定分配給幾個(gè)變量單獨(dú)使用

10、；二、指令的執(zhí)行代價(jià)二、指令的執(zhí)行代價(jià) 1 1、定義：指令的執(zhí)行代價(jià)、定義：指令的執(zhí)行代價(jià)= =指令訪問內(nèi)存單元的次數(shù)指令訪問內(nèi)存單元的次數(shù)+1 +1 2 2、例：、例：op Ri,Riop Ri,Ri執(zhí)行代價(jià)為執(zhí)行代價(jià)為1 1；op Ri,Mop Ri,M執(zhí)行代價(jià)為執(zhí)行代價(jià)為2 2； op Ri,op Ri,* *RiRi執(zhí)行代價(jià)為執(zhí)行代價(jià)為2 2；op Riop Ri, ,* *M M執(zhí)行代價(jià)為執(zhí)行代價(jià)為3 3 3 3、應(yīng)用：對(duì)循環(huán)中每個(gè)變量計(jì)算把某寄存器分配給它時(shí)執(zhí)行代、應(yīng)用：對(duì)循環(huán)中每個(gè)變量計(jì)算把某寄存器分配給它時(shí)執(zhí)行代 價(jià)能節(jié)省多少，以決定寄存器的固定分配方案；價(jià)能節(jié)省多少，以決定寄

11、存器的固定分配方案； 11.4寄存器分配寄存器分配 三、計(jì)算節(jié)省的執(zhí)行代價(jià)（相對(duì)于原算法）三、計(jì)算節(jié)省的執(zhí)行代價(jià)（相對(duì)于原算法） 1 1、變量在基本塊中被定值時(shí)，其值才存放在寄存器中、變量在基本塊中被定值時(shí)，其值才存放在寄存器中寄存器固寄存器固 定分配給某變量定分配給某變量: :則變量在塊中被定值前每引用一次就少訪問則變量在塊中被定值前每引用一次就少訪問 一次內(nèi)存（節(jié)省執(zhí)行代價(jià)一次內(nèi)存（節(jié)省執(zhí)行代價(jià)1 1）；）； 2 2、若變量在基本塊內(nèi)被定值且在塊出口之后活躍，則出基本塊時(shí)、若變量在基本塊內(nèi)被定值且在塊出口之后活躍，則出基本塊時(shí) 要把在寄存器中的值存放到內(nèi)存單元要把在寄存器中的值存放到內(nèi)存單

12、元寄存器固定分配給變寄存器固定分配給變 量量: :則出基本塊時(shí)無須把值寫回內(nèi)存單元?jiǎng)t出基本塊時(shí)無須把值寫回內(nèi)存單元( (節(jié)省執(zhí)行代價(jià)節(jié)省執(zhí)行代價(jià)2)2)； 3 3、由、由1 1、2 2得到如下公式得到如下公式( (對(duì)循環(huán)對(duì)循環(huán)L L中的變量中的變量M,M,若固定分它一寄存器若固定分它一寄存器, , 則每循環(huán)一次節(jié)省的執(zhí)行代價(jià)）：則每循環(huán)一次節(jié)省的執(zhí)行代價(jià)）：其中：其中：USE(M ,B)=USE(M ,B)=基本塊基本塊B B中對(duì)中對(duì)M M定值前引用定值前引用M M的次數(shù)；的次數(shù)； 1(1(如如M M在在B B中被定值且在中被定值且在B B出口之后活躍出口之后活躍) ) LIVE= LIVE=

13、 0( 0(其它情況其它情況) )LBBMLIVEBMUSE),(*2),(11.4寄存器分配寄存器分配 例：按減少執(zhí)行代價(jià)的原則，為循環(huán)中的變量分配固定寄存器例：按減少執(zhí)行代價(jià)的原則，為循環(huán)中的變量分配固定寄存器 ( (有三個(gè)可用寄存器有三個(gè)可用寄存器R0R0、R1R1、R2)R2)對(duì)變量對(duì)變量a:a: USE(a USE(a ,B1)=0 ,B1)=0； USE(aUSE(a ,B2)=1 ,B2)=1； USE(aUSE(a ,B3)=1 ,B3)=1； USE(aUSE(a ,B4)=0 ,B4)=0； LIVE(aLIVE(a ,B1)=1 ,B1)=1； LIVE(aLIVE(a

14、,B2)=0 ,B2)=0； LIVE(aLIVE(a ,B3)=0 ,B3)=0； LIVE(aLIVE(a ,B4)=0 ,B4)=0； 節(jié)省節(jié)省USE(a ,B)+2USE(a ,B)+2* *LIVE(aLIVE(a ,B)=1+1+2 ,B)=1+1+2* *1=4 1=4 對(duì)變量對(duì)變量b b、c c、d d、e e、f:f:分別節(jié)省分別節(jié)省6 6、3 3、6 6、4 4、4 4 于是，于是，R0R0分配給分配給d d，R1R1分配給分配給b b，R2R2可分配給可分配給aefaef中任一個(gè)；中任一個(gè)；11.4寄存器分配寄存器分配 四、生成循環(huán)的目標(biāo)代碼四、生成循環(huán)的目標(biāo)代碼 1 1、已固定分配寄存器的變量用、已固定分配寄存器的變量用 相應(yīng)寄存器表示；相應(yīng)寄存器表示； 2 2、若變量在循環(huán)入口前活躍、若變量在循環(huán)入口前活躍, ,則則 在入口前在入口前, ,生成把它們的值取生成把它們的值取 到相應(yīng)寄存器中的目標(biāo)代碼到相應(yīng)寄存器中的目標(biāo)代碼; ; 3