1、1編譯原理編譯原理第十一章第十一章 目標(biāo)代碼生成目標(biāo)代碼生成王金偉計(jì)算機(jī)與信息工程學(xué)院天津師范大學(xué)2詞法分析器詞法分析器語法分析器語法分析器中間代碼生成器中間代碼生成器優(yōu)化段優(yōu)化段源程序源程序單詞符號(hào)單詞符號(hào)語法單位語法單位四元式四元式表表格格管管理理出出錯(cuò)錯(cuò)處處理理目標(biāo)代碼生成器目標(biāo)代碼生成器四元式四元式目標(biāo)代碼目標(biāo)代碼3n代碼生成代碼生成是把語法分析后或優(yōu)化后的中間代碼變換成目是把語法分析后或優(yōu)化后的中間代碼變換成目標(biāo)代碼。標(biāo)代碼。n目標(biāo)代碼一般有以下三種形式：目標(biāo)代碼一般有以下三種形式：能夠立即執(zhí)行的機(jī)器語言代碼能夠立即執(zhí)行的機(jī)器語言代碼，所有地址已經(jīng)定位；，所有地址已經(jīng)定位；待裝配的機(jī)

2、器語言模塊待裝配的機(jī)器語言模塊。執(zhí)行時(shí)，由連接裝配程序把。執(zhí)行時(shí)，由連接裝配程序把它們和某些運(yùn)行程序連接起來，轉(zhuǎn)換成能執(zhí)行的機(jī)器它們和某些運(yùn)行程序連接起來，轉(zhuǎn)換成能執(zhí)行的機(jī)器語言代碼；語言代碼；匯編語言代碼匯編語言代碼。尚須經(jīng)過匯編程序匯編，轉(zhuǎn)換成可執(zhí)。尚須經(jīng)過匯編程序匯編，轉(zhuǎn)換成可執(zhí)行的機(jī)器語言代碼。行的機(jī)器語言代碼。4n代碼生成著重考慮的問題：代碼生成著重考慮的問題：如何使生成的目標(biāo)代碼較短；如何使生成的目標(biāo)代碼較短；如何充分利用計(jì)算機(jī)的寄存器，減少目標(biāo)代碼中訪如何充分利用計(jì)算機(jī)的寄存器，減少目標(biāo)代碼中訪問存貯單元的次數(shù)。問存貯單元的次數(shù)。如何充分利用計(jì)算機(jī)的指令系統(tǒng)的特點(diǎn)。如何充分利用計(jì)

3、算機(jī)的指令系統(tǒng)的特點(diǎn)。511.1 基本問題基本問題 n代碼生成器的輸入代碼生成器的輸入 代碼生成器的輸入包括源程序的中間表示，以及符號(hào)代碼生成器的輸入包括源程序的中間表示，以及符號(hào)表中的信息，代碼生成器可以利用符號(hào)表中的信息來表中的信息，代碼生成器可以利用符號(hào)表中的信息來決定在中間代碼中的名字所指示的數(shù)據(jù)對(duì)象的運(yùn)行時(shí)決定在中間代碼中的名字所指示的數(shù)據(jù)對(duì)象的運(yùn)行時(shí)地址。地址。類型檢查，假定已經(jīng)作過必要的類型檢查，在必要的類型檢查，假定已經(jīng)作過必要的類型檢查，在必要的地方已經(jīng)加上了類型轉(zhuǎn)換操作，并已檢測(cè)出一些明顯地方已經(jīng)加上了類型轉(zhuǎn)換操作，并已檢測(cè)出一些明顯的語義錯(cuò)誤。代碼生成階段就可以假設(shè)它的輸

4、入是沒的語義錯(cuò)誤。代碼生成階段就可以假設(shè)它的輸入是沒有錯(cuò)誤的。有錯(cuò)誤的。6n目標(biāo)程序目標(biāo)程序 絕對(duì)機(jī)器代碼、可再定位機(jī)器語言、匯編語言絕對(duì)機(jī)器代碼、可再定位機(jī)器語言、匯編語言采用匯編代碼作為目標(biāo)語言采用匯編代碼作為目標(biāo)語言 n指令選擇指令選擇一個(gè)有著豐富指令集的機(jī)器可以為一個(gè)給定的操作提供一個(gè)有著豐富指令集的機(jī)器可以為一個(gè)給定的操作提供幾種實(shí)現(xiàn)方法。幾種實(shí)現(xiàn)方法。a:=a+1nINC a nLD R0, a ADD R0, #1 ST R0, a 7n寄存器分配寄存器分配 在寄存器分配期間，為程序的某一點(diǎn)在寄存器分配期間，為程序的某一點(diǎn)選擇駐留在寄存器選擇駐留在寄存器中的一組變量中的一組變量。

5、在隨后的寄存器指派階段，在隨后的寄存器指派階段，挑出變量將要駐留的具體寄挑出變量將要駐留的具體寄存器存器。n計(jì)算順序選擇計(jì)算順序選擇影響目標(biāo)代碼的有效性。影響目標(biāo)代碼的有效性。811.2 目標(biāo)機(jī)器模型目標(biāo)機(jī)器模型 n考慮一個(gè)抽象的計(jì)算機(jī)模型考慮一個(gè)抽象的計(jì)算機(jī)模型具有多個(gè)通用寄存器，他們既可以作為累加器，也可具有多個(gè)通用寄存器，他們既可以作為累加器，也可以作為變址器。以作為變址器。運(yùn)算必須在某個(gè)寄存器中進(jìn)行。運(yùn)算必須在某個(gè)寄存器中進(jìn)行。含有四種類型的指令形式含有四種類型的指令形式9如果如果op是一目運(yùn)行符，則是一目運(yùn)行符，則“op Ri, M”的意的意義為：義為：op（M） Ri，其余類型可類

6、推。，其余類型可類推。10op 包括一般計(jì)算機(jī)上常見的一些運(yùn)算符，如包括一般計(jì)算機(jī)上常見的一些運(yùn)算符，如ADD加加SUB減減MUL乘乘DIV除除11指指 令令意意 義義LD Ri, B把把 B 單單元元的的內(nèi)內(nèi)容容取取到到寄寄存存器器 R，即即（B） RiST Ri, B把把寄寄存存器器 Ri的的內(nèi)內(nèi)容容存存到到 B 單單元元，即即（Ri） BJ X無無條條件件轉(zhuǎn)轉(zhuǎn)向向 X 單單元元CMP A, B 把把 A 單單元元和和 B 單單元元的的值值進(jìn)進(jìn)行行比比較較，并并根根據(jù)據(jù)比比較較情情況況把把機(jī)機(jī)器器內(nèi)內(nèi)部部特特征征寄寄存存器器 CT 置置成成相相應(yīng)應(yīng)狀狀態(tài)態(tài)。 CT 占占兩兩個(gè)個(gè)二二進(jìn)進(jìn)位位

7、。 根根據(jù)據(jù) AB分分別別置置 CT 為為 0 或或 1 或或 2。J X如如 CT=0 轉(zhuǎn)轉(zhuǎn) X 單單元元J X如如 CT=0 或或 CT=1 轉(zhuǎn)轉(zhuǎn) X 單單元元J X如如 CT=1 轉(zhuǎn)轉(zhuǎn) X 單單元元J X如如 CT1 轉(zhuǎn)轉(zhuǎn) X 單單元元J X如如 CT=2 轉(zhuǎn)轉(zhuǎn) X 單單元元J X如如 CT=2 或或 CT=1 轉(zhuǎn)轉(zhuǎn) X 單單元元12n不考慮代碼的執(zhí)行效率，目標(biāo)代碼生成是不難的，不考慮代碼的執(zhí)行效率，目標(biāo)代碼生成是不難的，：A:=(B+C)*D+E翻譯為四元式：翻譯為四元式：T1:=B+CT2:=T1*DT3:=T2+EA:=T3 11.3 一個(gè)簡(jiǎn)單代碼生成器一個(gè)簡(jiǎn)單代碼生成器13G假設(shè)

8、只有一個(gè)寄存器可供使用假設(shè)只有一個(gè)寄存器可供使用目標(biāo)代碼：目標(biāo)代碼： LD R0，BADD R0 ，CST R0 ，T1假設(shè)假設(shè)T1，T2，T3在基本塊之在基本塊之后不再引用后不再引用:LD R0，BADD R0，CMUL R0，DADD R0，EST R0，A 四元式四元式T1:=B+CT3:=T2+ET2:=T1*DA:=T3 LD R0 ，T1MUL R0，DST R0 ，T2LD R0 ，T2ADD R0 ，EST R0 ，T3LD R0，T3 ST R0 ，A14n四元式的中間代碼變換成目標(biāo)代碼，并在一個(gè)基本塊四元式的中間代碼變換成目標(biāo)代碼，并在一個(gè)基本塊的范圍內(nèi)考慮如何充分利用寄存

9、器：的范圍內(nèi)考慮如何充分利用寄存器：盡可能留盡可能留：在生成計(jì)算某變量值的目標(biāo)代碼時(shí)，盡在生成計(jì)算某變量值的目標(biāo)代碼時(shí)，盡可能讓該變量保留在寄存器中。可能讓該變量保留在寄存器中。盡可能用：盡可能用：后續(xù)的目標(biāo)代碼盡可能引用變量在寄存后續(xù)的目標(biāo)代碼盡可能引用變量在寄存器中的值，而不訪問內(nèi)存。器中的值，而不訪問內(nèi)存。及時(shí)騰空及時(shí)騰空：在離開基本塊時(shí)，把存在寄存器中的現(xiàn)：在離開基本塊時(shí)，把存在寄存器中的現(xiàn)行的值放到主存中。行的值放到主存中。1511.3.1 待用信息待用信息n如果在一個(gè)基本塊內(nèi)，四元式如果在一個(gè)基本塊內(nèi)，四元式i對(duì)對(duì)A定值，四元式定值，四元式j(luò)要引要引用用A值，而從值，而從i到到j(luò)之

10、間沒有之間沒有A的其他定值，那么，我們的其他定值，那么，我們稱稱j是四元式是四元式i的變量的變量A的的待用信息待用信息。（即下一個(gè)引用點(diǎn)）。（即下一個(gè)引用點(diǎn)）i: A:=B op Cj: D:=A op En假設(shè)在變量的符號(hào)表登記項(xiàng)中含有記錄待用信息和活假設(shè)在變量的符號(hào)表登記項(xiàng)中含有記錄待用信息和活躍信息的欄。躍信息的欄。16n待用信息和活躍信息的表示：待用信息和活躍信息的表示：1 (x,x)表示變量的待用信息和活躍信息。其中表示變量的待用信息和活躍信息。其中i表示待用表示待用信息，信息，y表示活躍，表示活躍，表示非待用和非活躍；表示非待用和非活躍；2 在符號(hào)表中，在符號(hào)表中，(x，x)(x，

11、x)表示后面的符號(hào)對(duì)代替前表示后面的符號(hào)對(duì)代替前面的符號(hào)對(duì)；面的符號(hào)對(duì)；3 不特別說明，所有說明變量在基本塊出口之后均為非不特別說明，所有說明變量在基本塊出口之后均為非活躍變量。活躍變量。17n計(jì)算待用信息和活躍信息的算法步驟：計(jì)算待用信息和活躍信息的算法步驟：1. 開始時(shí)，把基本塊中各變量的符號(hào)表登記項(xiàng)中的待用開始時(shí)，把基本塊中各變量的符號(hào)表登記項(xiàng)中的待用信息欄填為信息欄填為“非待用非待用”，并根據(jù)該變量在基本塊出口，并根據(jù)該變量在基本塊出口之后是不是活躍的，把其中的活躍信息欄填為之后是不是活躍的，把其中的活躍信息欄填為“活躍活躍”或或“非活躍非活躍”；182. 從基本塊出口到基本塊入口從基

12、本塊出口到基本塊入口由后向前由后向前依次處理各個(gè)四元依次處理各個(gè)四元式。對(duì)每一個(gè)四元式式。對(duì)每一個(gè)四元式i: A:=B op C，依次執(zhí)行下面的步，依次執(zhí)行下面的步驟：驟： 1) 把符號(hào)表中變量把符號(hào)表中變量A的待用信息和活躍信息附加到的待用信息和活躍信息附加到四元式四元式i上；上； 2) 把符號(hào)表中把符號(hào)表中A的待用信息和活躍信息分別置為的待用信息和活躍信息分別置為“非待用非待用”和和“非活躍非活躍”； 3) 把符號(hào)表中變量把符號(hào)表中變量B和和C的待用信息和活躍信息附加的待用信息和活躍信息附加到四元式到四元式i上；上； 4) 把符號(hào)表中把符號(hào)表中B和和C的待用信息均置為的待用信息均置為i，活

13、躍信息，活躍信息均置為均置為“活躍活躍”。19：基本塊：基本塊1.T:=A-B2.U:=A-C3.V:=T+U4.W:=V+U設(shè)設(shè)W是基本塊出口之后的活躍變量。是基本塊出口之后的活躍變量。建立待用信息鏈表與活躍變量信息鏈表如下：建立待用信息鏈表與活躍變量信息鏈表如下：20(4)W:=V+U(3)V:=T+U(2)U:=A-C(1)T:=A-B(,y)(,)(,)(4,y)(,)(4,y)(3,y)(,)(,) (3,y)(2,y)(,) 序號(hào)序號(hào) 四元式四元式 左值左值 左操作數(shù)左操作數(shù) 右操作數(shù)右操作數(shù)變量名變量名初始狀態(tài)初始狀態(tài)信息鏈信息鏈(待用待用/活躍信息欄活躍信息欄) (3,y) (

14、,) (2,y) (1,y) (1,y) (2,y) (4,y) (,) (3,y)T(,)A(,)B(,)C(,)U(,)V(,)W (,y) (,) (4,y) (,)21為了在代碼生成中進(jìn)行寄存器分配，要隨時(shí)掌握各寄存為了在代碼生成中進(jìn)行寄存器分配，要隨時(shí)掌握各寄存器的情況：空閑？已分配給某個(gè)器的情況：空閑？已分配給某個(gè)(幾個(gè)幾個(gè))變量？變量？n寄存器描述數(shù)組寄存器描述數(shù)組RVALUE動(dòng)態(tài)記錄各寄存器的使用信息動(dòng)態(tài)記錄各寄存器的使用信息RVALUER=A,B每當(dāng)指令要引用某變量時(shí)，如果該變量的現(xiàn)行值已在某每當(dāng)指令要引用某變量時(shí)，如果該變量的現(xiàn)行值已在某寄存器中，可直接使用寄存器，而不必訪

15、存。寄存器中，可直接使用寄存器，而不必訪存。n變量地址描述數(shù)組變量地址描述數(shù)組AVALUE動(dòng)態(tài)記錄各變量現(xiàn)行值的存放位置動(dòng)態(tài)記錄各變量現(xiàn)行值的存放位置AVALUEA=R1, R2, A22n補(bǔ)充說明：補(bǔ)充說明：因?yàn)榧拇嫫鞯姆峙涫蔷窒抻诨緣K范圍之內(nèi)的，一旦因?yàn)榧拇嫫鞯姆峙涫蔷窒抻诨緣K范圍之內(nèi)的，一旦處理完基本塊中所有四元式，對(duì)現(xiàn)行值在寄存器中的處理完基本塊中所有四元式，對(duì)現(xiàn)行值在寄存器中的每個(gè)變量，如果它在基本塊之后是活躍的，則要把它每個(gè)變量，如果它在基本塊之后是活躍的，則要把它存在寄存器中的值存放到它的主存單元中。存在寄存器中的值存放到它的主存單元中。要特別強(qiáng)調(diào)的是，對(duì)形如：要特別強(qiáng)調(diào)的是

16、，對(duì)形如：A:=B的四元式，如果的四元式，如果B的的現(xiàn)行值在某寄存器現(xiàn)行值在某寄存器Ri中，則無須生成目標(biāo)代碼，只須中，則無須生成目標(biāo)代碼，只須在在RVALUE(Ri)中增加一個(gè)中增加一個(gè)A，(即把即把Ri同時(shí)分配給同時(shí)分配給B和和A)，并把，并把AVALUE(A)改為改為Ri 。23n代碼生成算法：代碼生成算法：對(duì)每個(gè)四元式對(duì)每個(gè)四元式: i: A:=B op C，依次執(zhí)行：，依次執(zhí)行： 1. 以四元式以四元式: i: A:=B op C 為參數(shù)，為參數(shù)，調(diào)用函數(shù)過程調(diào)用函數(shù)過程GETREG(i: A:=B op C)，返回一個(gè)寄存器返回一個(gè)寄存器R，用作存，用作存放放A的寄存器。的寄存器。

17、 2. 利用利用AVALUEB和和AVALUEC，確定，確定B和和C現(xiàn)行值的現(xiàn)行值的存放位置存放位置B和和C。如果其現(xiàn)行值在寄存器中，則把寄存。如果其現(xiàn)行值在寄存器中，則把寄存器取作器取作B和和C 3. 如果如果BR，則生成目標(biāo)代碼：，則生成目標(biāo)代碼： LD R, B op R, C 否則生成目標(biāo)代碼否則生成目標(biāo)代碼 op R, C 如果如果B或或C為為R，則刪除，則刪除AVALUEB或或AVALUEC中的中的R。24 4. 令令A(yù)VALUEA=R, RVALUER=A。 5. 若若B或或C的現(xiàn)行值在基本塊中不再被引用，也不是基本塊的現(xiàn)行值在基本塊中不再被引用，也不是基本塊出口之后的活躍變量，

18、且其現(xiàn)行值在某寄存器出口之后的活躍變量，且其現(xiàn)行值在某寄存器Rk中，則刪中，則刪除除RVALUERk中的中的B或或C以及以及AVALUEB或或AVALUEC 中的中的Rk ，使得該寄存器不再為，使得該寄存器不再為B或或C占用。占用。25n寄存器分配：寄存器分配：GETREG(i: A:=B op C) 返回一個(gè)用來存放返回一個(gè)用來存放A的值的寄存器的值的寄存器1 如果如果B的現(xiàn)行值在某個(gè)寄存器的現(xiàn)行值在某個(gè)寄存器Ri中，中，RVALUERi中只中只包含包含B，此外，或者，此外，或者B與與A是同一個(gè)標(biāo)識(shí)符是同一個(gè)標(biāo)識(shí)符，或者，或者B的的現(xiàn)行值在執(zhí)行四元式現(xiàn)行值在執(zhí)行四元式A:=B op C之后不

19、會(huì)再引用之后不會(huì)再引用，則，則選取選取Ri為所需要的寄存器為所需要的寄存器R，并轉(zhuǎn)，并轉(zhuǎn)4；2 如果有尚未分配的寄存器，則從中選取一個(gè)如果有尚未分配的寄存器，則從中選取一個(gè)Ri為所需為所需要的寄存器要的寄存器R，并轉(zhuǎn)，并轉(zhuǎn)4；1 盡可能用盡可能用B獨(dú)占的寄存器獨(dú)占的寄存器2 盡可能用空閑寄存器盡可能用空閑寄存器3 搶占用非空閑寄存器搶占用非空閑寄存器263 從已分配的寄存器中選取一個(gè)從已分配的寄存器中選取一個(gè)Ri為所需要的寄存器為所需要的寄存器R。最好使得最好使得Ri滿足以下條件：滿足以下條件： 占用占用Ri的變量的值也同時(shí)存放在該變量的貯存單元中，的變量的值也同時(shí)存放在該變量的貯存單元中，或者在基本塊中要在最遠(yuǎn)的將來才會(huì)引用到或不會(huì)引或者在基本塊中要在最遠(yuǎn)的將來才會(huì)引用到或不會(huì)引用到。用到。要不要為要不要為Ri中的變量生成存數(shù)指令？中的變量生成存數(shù)指令？1 盡可能用盡可能用B獨(dú)占的寄存器獨(dú)占的寄存器2 盡可能用空閑寄存器盡可