第十一章 目標代碼生成

1、第十一章 目標代碼生成詞法分析器詞法分析器語法分析器語法分析器中間代碼生成器中間代碼生成器優(yōu)化段優(yōu)化段源程序源程序單詞符號單詞符號語法單位語法單位四元式四元式表表格格管管理理出出錯錯處處理理目標代碼生成器目標代碼生成器四元式四元式目標代碼目標代碼內容線索n基本問題基本問題n目標機器模型目標機器模型 n一個簡單的代碼生成器一個簡單的代碼生成器代碼生成n代碼生成器代碼生成器代碼生成器的輸入包括源程序的中間表示，以代碼生成器的輸入包括源程序的中間表示，以及符號表中的信息及符號表中的信息n利用符號表信息決定數據對象運行時地址利用符號表信息決定數據對象運行時地址n類型檢查類型檢查編譯前端編譯前端代碼優(yōu)化

2、代碼優(yōu)化代碼生成器代碼生成器符號表符號表目標代碼生成n代碼生成代碼生成是把語義分析后或優(yōu)化后的中間是把語義分析后或優(yōu)化后的中間代碼變換成目標代碼。代碼變換成目標代碼。n代碼生成著重考慮的問題代碼生成著重考慮的問題如何使生成的目標代碼較短；如何使生成的目標代碼較短；如何充分利用計算機的寄存器，減少目標代碼如何充分利用計算機的寄存器，減少目標代碼中訪問存貯單元的次數。中訪問存貯單元的次數。如何充分利用計算機的指令系統的特點。如何充分利用計算機的指令系統的特點。基本問題n目標代碼一般有以下三種形式：目標代碼一般有以下三種形式：能夠立即執(zhí)行的機器語言代碼能夠立即執(zhí)行的機器語言代碼，所有地址已經，所有地

3、址已經定位；定位；待裝配的機器語言模塊待裝配的機器語言模塊。執(zhí)行時，由連接裝配。執(zhí)行時，由連接裝配程序把它們和某些運行程序連接起來，轉換成程序把它們和某些運行程序連接起來，轉換成能執(zhí)行的機器語言代碼；能執(zhí)行的機器語言代碼；匯編語言代碼匯編語言代碼。尚須經過匯編程序匯編，轉換。尚須經過匯編程序匯編，轉換成可執(zhí)行的機器語言代碼。成可執(zhí)行的機器語言代碼。基本問題 n指令選擇指令選擇一致性和完整性一致性和完整性指令速度和機器用語指令速度和機器用語a:=a+1nINC a /*實現最有效實現最有效*/nLD R0, a /*將將a放入寄存器放入寄存器R0*/ ADD R0, #1 /*1與與R0相加相加

4、*/ ST R0, a /*R0的值存入的值存入a*/基本問題 n寄存器分配寄存器分配 在寄存器分配期間，為程序的某一點選擇駐留在寄存器分配期間，為程序的某一點選擇駐留在寄存器中的一組變量。在寄存器中的一組變量。在隨后的寄存器指派階段，挑出變量將要駐留在隨后的寄存器指派階段，挑出變量將要駐留的具體寄存器。的具體寄存器。最優(yōu)寄存器指派是最優(yōu)寄存器指派是NP完全問題完全問題n計算順序選擇計算順序選擇 內容線索基本問題基本問題n目標機器模型目標機器模型 n一個簡單的代碼生成器一個簡單的代碼生成器目標機器模型 n考慮一個抽象的計算機模型考慮一個抽象的計算機模型具有多個通用寄存器，他們既可以作為累加器，

5、具有多個通用寄存器，他們既可以作為累加器，也可以作為變址器。也可以作為變址器。運算必須在某個寄存器中進行。運算必須在某個寄存器中進行。含有四種類型的指令形式含有四種類型的指令形式類類 型型指令形式指令形式意義意義(設設 op 是二目運是二目運算符算符)直接地址型直接地址型op Ri, M(Ri) op (M) Ri寄存器型寄存器型op Ri, Rj(Ri) op (Rj) Ri變址型變址型op Ri, c(Rj)(Ri) op (Ri)+c) Ri間接型間接型op Ri, *Mop Ri, *Rjop Ri, *c(Rj) (Ri) op (M) Ri(Ri) op (Rj) Ri(Ri) o

6、p (Rj)+c) Ri如果如果op是一目運行符，則是一目運行符，則“op Ri, M”的意的意義為：義為：op（M） Ri，其余類型可類推。，其余類型可類推。op 包括一般計算機上常見的一些運算符，如包括一般計算機上常見的一些運算符，如ADD加加SUB減減MUL乘乘DIV除除指指 令令意意 義義LD Ri, B把把 B 單元的內容取到寄存器單元的內容取到寄存器 R，即，即（B） RiST Ri, B把寄存器把寄存器 Ri的內容存到的內容存到 B 單元，即單元，即（Ri） BJ X無條件轉向無條件轉向 X 單元單元CMP A, B 把把 A 單元和單元和 B 單元的值進行比較，并根據比較單元的

7、值進行比較，并根據比較情況把機器內部特征寄存器情況把機器內部特征寄存器 CT 置成相應狀置成相應狀態(tài)。態(tài)。 CT 占兩個二進位。 根據占兩個二進位。 根據 AB分別置分別置 CT 為為 0 或或 1 或或 2。J X如如 CT=0 轉轉 X 單元單元J X如如 CT=0 或或 CT=1 轉轉 X 單元單元J X如如 CT=1 轉轉 X 單元單元J X如如 CT1 轉轉 X 單元單元J X如如 CT=2 轉轉 X 單元單元J X如如 CT=2 或或 CT=1 轉轉 X 單元單元內容線索基本問題基本問題目標機器模型目標機器模型 n一個簡單的代碼生成器一個簡單的代碼生成器n不考慮代碼的執(zhí)行效率，目標

8、代碼生成不考慮代碼的執(zhí)行效率，目標代碼生成是不難的，例如：是不難的，例如：A:=(B+C)*D+E翻譯為四元式：翻譯為四元式：T1:=B+CT2:=T1*DT3:=T2+EA:=T3 一個簡單代碼生成器假設只有一個寄存器可供使用假設只有一個寄存器可供使用目標代碼：目標代碼： LD R0，BADD R0 ，CST R0 ，T1假設假設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 R

9、0 ，T2ADD R0 ，EST R0 ，T3LD R0，T3 ST R0 ，A一個簡單代碼生成器n四元式的中間代碼變換成目標代碼，并在一個四元式的中間代碼變換成目標代碼，并在一個基本塊的范圍內考慮如何充分利用寄存器：基本塊的范圍內考慮如何充分利用寄存器：盡可能留盡可能留：在生成計算某變量值的目標代碼：在生成計算某變量值的目標代碼時，盡可能讓該變量保留在寄存器中。時，盡可能讓該變量保留在寄存器中。盡可能用盡可能用：后續(xù)的目標代碼盡可能引用變量：后續(xù)的目標代碼盡可能引用變量在寄存器中的值，而不訪問內存。在寄存器中的值，而不訪問內存。及時騰空及時騰空：在離開基本塊時，把存在寄存器：在離開基本塊時，

10、把存在寄存器中的現行的值放到主存中。中的現行的值放到主存中。待用信息n如果在一個基本塊內，四元式如果在一個基本塊內，四元式i對對A定值，定值，四元式四元式j要引用要引用A值，而從值，而從i到到j之間沒有之間沒有A的其他定值，那么，我們稱的其他定值，那么，我們稱j是四元式是四元式i的的變量變量A的的待用信息待用信息。（即下一個引用點）。（即下一個引用點）i: A:=B op Cj: D:=A op En假設在變量的符號表登記項中含有記錄假設在變量的符號表登記項中含有記錄待用信息和活躍信息的欄。待用信息和活躍信息的欄。待用信息和活躍信息的表示待用信息和活躍信息的表示1 (x,x)表示變量的待用信息

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

12、出口之后是不是并根據該變量在基本塊出口之后是不是活躍的，把其中的活躍信息欄填為活躍的，把其中的活躍信息欄填為“活活躍躍”或或“非活躍非活躍”；2. 從基本塊出口到基本塊入口從基本塊出口到基本塊入口由后向前由后向前依次處依次處理各個四元式。對每一個四元式理各個四元式。對每一個四元式i: A:=B op C，依次執(zhí)行下面的步驟：，依次執(zhí)行下面的步驟： 1) 把符號表中變量把符號表中變量A的待用信息和活躍信息的待用信息和活躍信息附加到四元式附加到四元式i上；上； 2) 把符號表中把符號表中A的待用信息和活躍信息分別的待用信息和活躍信息分別置為置為“非待用非待用”和和“非活躍非活躍”； 3) 把符號表

13、中變量把符號表中變量B和和C的待用信息和活躍的待用信息和活躍信息附加到四元式信息附加到四元式i上；上； 4) 把符號表中把符號表中B和和C的待用信息均置為的待用信息均置為i，活，活躍信息均置為躍信息均置為“活躍活躍”。例：基本塊例：基本塊1. T:=A-B2. U:=A-C3. V:=T+U4. W:=V+U設設W是基本塊出口之后的活躍變量。是基本塊出口之后的活躍變量。建立待用信息鏈表與活躍變量信息鏈表如下：建立待用信息鏈表與活躍變量信息鏈表如下：n附加在四元式上的待用/活躍信息表：(4)W:=V+U(3)V:=T+U(2)U:=A-C(1)T:=A-B(,y)(,)(,)(4,y)(,)(4

14、,y)(3,y)(,)(,) (3,y)(2,y)(,) 序號序號 四元式四元式 左值左值 左操作數左操作數 右操作數右操作數變量名變量名初始狀態(tài)初始狀態(tài)信息鏈信息鏈(待用待用/活躍信息欄活躍信息欄) (3,y) (,) (2,y) (1,y) (1,y) (2,y) (4,y) (,) (3,y)T(,)A(,)B(,)C(,)U(,)V(,)W (,y) (,) (4,y) (,)寄存器描述和地址描述n寄存器描述數組寄存器描述數組RVALUE動態(tài)記錄各寄存器的使用信息動態(tài)記錄各寄存器的使用信息 例：例：RVALUER=A,Bn變量地址描述數組變量地址描述數組AVALUE動態(tài)記錄各變量現行值

15、的存放位置動態(tài)記錄各變量現行值的存放位置 例：例：AVALUEA=R1, R2, An補充說明：補充說明：因為寄存器的分配是局限于基本塊范圍之因為寄存器的分配是局限于基本塊范圍之內的，一旦處理完基本塊中所有四元式，內的，一旦處理完基本塊中所有四元式，對現行值在寄存器中的每個變量，如果它對現行值在寄存器中的每個變量，如果它在基本塊之后是活躍的，則要把它存在寄在基本塊之后是活躍的，則要把它存在寄存器中的值存放到它的主存單元中。存器中的值存放到它的主存單元中。要特別強調的是，對形如：要特別強調的是，對形如：A:=B的四元式，的四元式，如果如果B的現行值在某寄存器的現行值在某寄存器Ri中，則無須生中，

16、則無須生成目標代碼，只須在成目標代碼，只須在RVALUE(Ri)中增加一中增加一個個A，(即把即把Ri同時分配給同時分配給B和和A)，并把，并把AVALUE(A)改為改為Ri 。代碼生成算法對每個四元式對每個四元式: i: A:=B op C，依次執(zhí)行：，依次執(zhí)行： 1. 以四元式以四元式: i: A:=B op C 為參數，為參數，調用函數過程調用函數過程GETREG(i: A:=B op C)，返回一個寄存器返回一個寄存器R，用，用作存放作存放A的寄存器。的寄存器。 2. 利用利用AVALUEB和和AVALUEC，確定，確定B和和C現行現行值的存放位置值的存放位置B和和C。如果其現行值在寄

17、存器。如果其現行值在寄存器中，則把寄存器取作中，則把寄存器取作B和和C3. 如果如果BR，則生成目標代碼：，則生成目標代碼： LD R, B op R, C 否則生成目標代碼否則生成目標代碼 op R, C 如果如果B或或C為為R，則刪除，則刪除AVALUEB或或AVALUEC中的中的R。4. 令令AVALUEA=R, RVALUER=A。5. 若若B或或C的現行值在基本塊中不再被引用，也不的現行值在基本塊中不再被引用，也不是基本塊出口之后的活躍變量，且其現行值在某是基本塊出口之后的活躍變量，且其現行值在某寄存器寄存器Rk中，則刪除中，則刪除RVALUERk中的中的B或或C以及以及AVALUE

18、B或或AVALUEC 中的中的Rk ，使得該寄存，使得該寄存器不再為器不再為B或或C占用。占用。n寄存器分配：寄存器分配：GETREG(i: A:=B op C) 返返回一個用來存放回一個用來存放A的值的寄存器的值的寄存器1 如 果如 果 B 的 現 行 值 在 某 個 寄 存 器的 現 行 值 在 某 個 寄 存 器 Ri中 ，中 ，RVALUERi中只包含中只包含B，此外，或者，此外，或者B與與A是是同一個標識符同一個標識符，或者，或者B的現行值在執(zhí)行四元式的現行值在執(zhí)行四元式A:=B op C之后不會再引用之后不會再引用，則選取，則選取Ri為所需為所需要的寄存器要的寄存器R，并轉，并轉4

19、；2 如果有尚未分配的寄存器，則從中選取一個如果有尚未分配的寄存器，則從中選取一個Ri為所需要的寄存器為所需要的寄存器R，并轉，并轉4；1 盡可能用盡可能用B獨占的寄存器獨占的寄存器2 盡可能用空閑寄存器盡可能用空閑寄存器3 搶占用非空閑寄存器搶占用非空閑寄存器3 從已分配的寄存器中選取一個從已分配的寄存器中選取一個Ri為所需要的寄為所需要的寄存器存器R。最好使得。最好使得Ri滿足以下條件：滿足以下條件： 占用占用Ri的變量的值也同時存放在該變量的貯存的變量的值也同時存放在該變量的貯存單元中，或者在基本塊中要在最遠的將來才會單元中，或者在基本塊中要在最遠的將來才會引用到或不會引用到。引用到或不會引用到。4. 要不要為要不要為Ri中的變量生成存數指令？中的變量生成存數指令？1 盡可能用盡可能用B所在的寄存器所在的寄存器2 盡可能用空閑寄存器盡可能用空閑寄存器3 搶占用非空閑寄存器搶占用非空閑寄存器4. 要不要為要不要為Ri中的變量中的變量V生成存數指令？生成存數指令？ （1）如果）如果V的地址描述數組的地址描述數組AVALUEV說說V還保還保存在存在R之外的其他地方，則不需要生成存數指之外的其他地