編譯原理第十一章

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

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

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

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

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

6、推。，其余類型可類推。10op 包括一般計算機上常見的一些運算符，如包括一般計算機上常見的一些運算符，如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ù)據(jù)比比較較情情況況把把機機器器內(nèi)內(nèi)部部特特征征寄寄存存器器 CT 置置成成相相應(yīng)應(yīng)狀狀態(tài)態(tài)。 CT 占占兩兩個個二二進進位位

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í)行效率，目標代碼生成是不難的，不考慮代碼的執(zhí)行效率，目標代碼生成是不難的，：A:=(B+C)*D+E翻譯為四元式：翻譯為四元式：T1:=B+CT2:=T1*DT3:=T2+EA:=T3 11.3 一個簡單代碼生成器一個簡單代碼生成器13G假設(shè)

8、只有一個寄存器可供使用假設(shè)只有一個寄存器可供使用目標代碼：目標代碼： 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四元式的中間代碼變換成目標代碼，并在一個基本塊四元式的中間代碼變換成目標代碼，并在一個基本塊的范圍內(nèi)考慮如何充分利用寄存

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

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

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

12、本塊出口到基本塊入口由后向前由后向前依次處理各個四元依次處理各個四元式。對每一個四元式式。對每一個四元式i: A:=B op C，依次執(zhí)行下面的步，依次執(zhí)行下面的步驟：驟： 1) 把符號表中變量把符號表中變量A的待用信息和活躍信息附加到的待用信息和活躍信息附加到四元式四元式i上；上； 2) 把符號表中把符號表中A的待用信息和活躍信息分別置為的待用信息和活躍信息分別置為“非待用非待用”和和“非活躍非活躍”； 3) 把符號表中變量把符號表中變量B和和C的待用信息和活躍信息附加的待用信息和活躍信息附加到四元式到四元式i上；上； 4) 把符號表中把符號表中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)(,) 序號序號 四元式四元式 左值左值 左操作數(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為了在代碼生成中進行寄存器分配，要隨時掌握各寄存為了在代碼生成中進行寄存器分配，要隨時掌握各寄存器的情況：空閑？已分配給某個器的情況：空閑？已分配給某個(幾個幾個)變量？變量？n寄存器描述數(shù)組寄存器描述數(shù)組RVALUE動態(tài)記錄各寄存器的使用信息動態(tài)記錄各寄存器的使用信息RVALUER=A,B每當指令要引用某變量時，如果該變量的現(xiàn)行值已在某每當指令要引用某變量時，如果該變量的現(xiàn)行值已在某寄存器中，可直接使用寄存器，而不必訪

15、存。寄存器中，可直接使用寄存器，而不必訪存。n變量地址描述數(shù)組變量地址描述數(shù)組AVALUE動態(tài)記錄各變量現(xiàn)行值的存放位置動態(tài)記錄各變量現(xiàn)行值的存放位置AVALUEA=R1, R2, A22n補充說明：補充說明：因為寄存器的分配是局限于基本塊范圍之內(nèi)的，一旦因為寄存器的分配是局限于基本塊范圍之內(nèi)的，一旦處理完基本塊中所有四元式，對現(xiàn)行值在寄存器中的處理完基本塊中所有四元式，對現(xiàn)行值在寄存器中的每個變量，如果它在基本塊之后是活躍的，則要把它每個變量，如果它在基本塊之后是活躍的，則要把它存在寄存器中的值存放到它的主存單元中。存在寄存器中的值存放到它的主存單元中。要特別強調(diào)的是，對形如：要特別強調(diào)的是

16、，對形如：A:=B的四元式，如果的四元式，如果B的的現(xiàn)行值在某寄存器現(xiàn)行值在某寄存器Ri中，則無須生成目標代碼，只須中，則無須生成目標代碼，只須在在RVALUE(Ri)中增加一個中增加一個A，(即把即把Ri同時分配給同時分配給B和和A)，并把，并把AVALUE(A)改為改為Ri 。23n代碼生成算法：代碼生成算法：對每個四元式對每個四元式: 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)，返回一個寄存器返回一個寄存器R，用作存，用作存放放A的寄存器。的寄存器。

17、 2. 利用利用AVALUEB和和AVALUEC，確定，確定B和和C現(xiàn)行值的現(xiàn)行值的存放位置存放位置B和和C。如果其現(xiàn)行值在寄存器中，則把寄存。如果其現(xiàn)行值在寄存器中，則把寄存器取作器取作B和和C 3. 如果如果BR，則生成目標代碼：，則生成目標代碼： LD R, B op R, C 否則生成目標代碼否則生成目標代碼 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) 返回一個用來存放返回一個用來存放A的值的寄存器的值的寄存器1 如果如果B的現(xiàn)行值在某個寄存器的現(xiàn)行值在某個寄存器Ri中，中，RVALUERi中只中只包含包含B，此外，或者，此外，或者B與與A是同一個標識符是同一個標識符，或者，或者B的的現(xiàn)行值在執(zhí)行四元式現(xiàn)行值在執(zhí)行四元式A:=B op C之后不

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