編譯原理第11章

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

1、寄存器分配期間:為程序選擇一組要駐留在寄存器中的變量；

2、寄存器指派階段:為變量指派具體寄存器；五、選擇計(jì)算順序§11.1基本問題§11.2目標(biāo)機(jī)器模型一、多個(gè)通用寄存器：也可做累加器和變址器；二、指令類型：三、操作碼op：ADD(加)、SUB(減)、MUL(乘)、DIV(除)；§11.2目標(biāo)機(jī)器模型四、基本指令：

1、LDRi,B:

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

2、STRi,B:

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

3、JX:

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

4、CMPA,B:

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

5、JopX:

根據(jù)CT的狀態(tài)轉(zhuǎn)向X單元（op為<、≤、=、≠、>、≥）；§11.2目標(biāo)機(jī)器模型§11.3一個(gè)簡單的代碼生成器一、功能：依次把每條中間代碼轉(zhuǎn)換成目標(biāo)代碼，并在基本塊內(nèi)考慮充分利用寄存器等問題；例：§11.3一個(gè)簡單的代碼生成器二、待用信息

1、含義：某變量被定值后，將在何處被引用；

2、獲取待用信息的方法：從基本塊的出口由后向前掃描，對每個(gè)變量建立待用信息鏈和活躍變量信息鏈；

3、記錄待用信息和活躍信息：符號(hào)表增待用信息和活躍信息欄；

4、計(jì)算變量待用信息和活躍信息的算法：

§11.3一個(gè)簡單的代碼生成器例：計(jì)算變量的待用信息和活躍信息§11.3一個(gè)簡單的代碼生成器三、寄存器描述和地址描述

1、寄存器描述數(shù)組RValue：記錄寄存器使用情況(空閑或已分配)2、變量地址描述數(shù)組AValue：記錄各變量現(xiàn)行值的存放位置(在寄存器或內(nèi)存單元)；四、基本塊內(nèi)代碼生成算法

對塊內(nèi)每個(gè)中間代碼i:A:=BopC，依次執(zhí)行：§11.3一個(gè)簡單的代碼生成器過程GetReg算法(參數(shù)為i:A:=BopC,返回存放A值的寄存器R)§11.3一個(gè)簡單的代碼生成器基本塊內(nèi)代碼生成算法流程圖：§10.1概述修改RValue和AValue流程圖:§10.1概述例：中間代碼目標(biāo)代碼RValueAValueT:=A–BLDR0,ASUBR0,BR0含有TT在R0中U:=A–CLDR1,ASUBR1,CR0含有TR1含有UT在R0中U在R1中V:=T+UADDR0,R1R0含有VR1含有UV在R0中U在R1中W:=V+UADDR0,R1R0含有WW在R0中§11.3一個(gè)簡單的代碼生成器§11.4寄存器分配一、問題引入：如何有效的利用寄存器；

1、基本塊內(nèi)：①運(yùn)算對象的值在寄存器中,則把該寄存器作為操作數(shù)地址；②盡可能把各變量的現(xiàn)行值保存在寄存器中；③基本塊中不再引用的變量所占用的寄存器及早釋放；

2、循環(huán)內(nèi)：按執(zhí)行代價(jià)把寄存器固定分配給幾個(gè)變量單獨(dú)使用；二、指令的執(zhí)行代價(jià)

1、定義：指令的執(zhí)行代價(jià)=指令訪問內(nèi)存單元的次數(shù)+12、例：opRi,Ri執(zhí)行代價(jià)為1； opRi,M執(zhí)行代價(jià)為2；

opRi,*Ri執(zhí)行代價(jià)為2； opRi,*M執(zhí)行代價(jià)為33、應(yīng)用：對循環(huán)中每個(gè)變量計(jì)算把某寄存器分配給它時(shí)執(zhí)行代價(jià)能節(jié)省多少，以決定寄存器的固定分配方案；§11.4寄存器分配三、計(jì)算節(jié)省的執(zhí)行代價(jià)（相對于原算法）1、變量在基本塊中被定值時(shí)，其值才存放在寄存器中→寄存器固定分配給某變量:則變量在塊中被定值前每引用一次就少訪問一次內(nèi)存（節(jié)省執(zhí)行代價(jià)1）；2、若變量在基本塊內(nèi)被定值且在塊出口之后活躍，則出基本塊時(shí)要把在寄存器中的值存放到內(nèi)存單元→寄存器固定分配給變量:則出基本塊時(shí)無須把值寫回內(nèi)存單元(節(jié)省執(zhí)行代價(jià)2)；3、由1、2得到如下公式(對循環(huán)L中的變量M,若固定分它一寄存器,

則每循環(huán)一次節(jié)省的執(zhí)行代價(jià)）：其中：USE(M,B)=基本塊B中對M定值前引用M的次數(shù)；

1(如M在B中被定值且在B出口之后活躍)LIVE=0(其它情況)§11.4寄存器分配例：按減少執(zhí)行代價(jià)的原則，為循環(huán)中的變量分配固定寄存器

(有三個(gè)可用寄存器R0、R1、R2)對變量a:

USE(a,B1)=0；

USE(a,B2)=1；

USE(a,B3)=1；

USE(a,B4)=0；

LIVE(a,B1)=1；

LIVE(a,B2)=0；

LIVE(a,B3)=0；

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