1、第第7 7章章 目標代碼生成目標代碼生成 第第7章章 目標代碼生成目標代碼生成 7.1 一個簡單代碼生成器一個簡單代碼生成器 7.2 匯編指令到機器代碼的翻譯概述匯編指令到機器代碼的翻譯概述 第第7 7章章 目標代碼生成目標代碼生成 7.1 一個簡單代碼生成器一個簡單代碼生成器 我們首先介紹一個簡單的代碼生成器，此生成我們首先介紹一個簡單的代碼生成器，此生成器依次把每條中間代碼變換成目標代碼，并且在一器依次把每條中間代碼變換成目標代碼，并且在一個基本塊范圍內考慮如何充分利用寄存器的問題。個基本塊范圍內考慮如何充分利用寄存器的問題。一方面，在基本塊中，當生成計算某變量值的目標一方面，在基本塊中，

2、當生成計算某變量值的目標代碼時，盡可能地讓該變量的值保留在寄存器中代碼時，盡可能地讓該變量的值保留在寄存器中(即不編出把該變量的值存到內存單元的指令即不編出把該變量的值存到內存單元的指令)，直，直到該寄存器必須用來存放其它變量的值或已達基本到該寄存器必須用來存放其它變量的值或已達基本塊出口為止；另一方面，后續的目標代碼盡可能地塊出口為止；另一方面，后續的目標代碼盡可能地引用變量在寄存器中的值而不訪問內存。引用變量在寄存器中的值而不訪問內存。 第第7 7章章 目標代碼生成目標代碼生成 例如，一例如，一C語言語句為語言語句為A=(B+C)*D+E，把它翻，把它翻譯為四元式譯為四元式G： T1=B+

3、C T2=T1*D A=T2+E 如果不考慮代碼的效率，可以簡單地把每條中如果不考慮代碼的效率，可以簡單地把每條中間代碼間代碼(四元式四元式)映射成若干條目標指令，如將映射成若干條目標指令，如將x=y+z映射為：映射為： MOV AX, y /*AX為寄存器為寄存器*/ ADD AX, z MOV x, AX其中，其中，x、y、z均為數據區的內存變量。均為數據區的內存變量。第第7 7章章 目標代碼生成目標代碼生成 這樣，上述四元式代碼序列這樣，上述四元式代碼序列G就可翻譯為：就可翻譯為：(1) MOV AX, B (2) ADD AX, C(3) MOV T1, AX(4) MOV AX, T

4、1 (5) MUL AX, D(6) MOV T2, AX(7) MOV AX, T2(8) ADD AX, E (9) MOV A, AX 第第7 7章章 目標代碼生成目標代碼生成 雖然從正確性來看，這種翻譯不存在問題，雖然從正確性來看，這種翻譯不存在問題，但它卻存在冗余。在上述指令序列中，但它卻存在冗余。在上述指令序列中，(4)和和(7)兩兩條指令是多余的；而條指令是多余的；而T1、T2均是中間代碼生成時均是中間代碼生成時產生的臨時變量，它們在出了基本塊后將不再使產生的臨時變量，它們在出了基本塊后將不再使用，故用，故(3)、(6)兩條指令也可刪去。所以，在考慮兩條指令也可刪去。所以，在考慮

5、了效率和充分使用寄存器之后，應生成如下代碼：了效率和充分使用寄存器之后，應生成如下代碼：(1) MOV AX, B (2) ADD AX, C(3) MUL AX, D(4) ADD AX, E (5) MOV A, AX第第7 7章章 目標代碼生成目標代碼生成 為了實現這一目的，代碼生成器就必須了解一些為了實現這一目的，代碼生成器就必須了解一些信息：在產生信息：在產生T2=T1*D對應的目標代碼時，為了省去對應的目標代碼時，為了省去指令指令MOV AX, T1，就必須知道，就必須知道T1的當前值已在寄存的當前值已在寄存器器AX中；為了省去中；為了省去MOV T1, AX，就必須知道出了基，就

6、必須知道出了基本塊后本塊后T1不再被引用。不再被引用。 第第7 7章章 目標代碼生成目標代碼生成 7.1.1 待用信息與活躍信息待用信息與活躍信息 在一個基本塊內的目標代碼中，為了提高寄存在一個基本塊內的目標代碼中，為了提高寄存器的使用效率，應將基本塊內還要被引用的值盡可器的使用效率，應將基本塊內還要被引用的值盡可能地保留在寄存器中，而將基本塊內不再被引用的能地保留在寄存器中，而將基本塊內不再被引用的變量所占用的寄存器盡早釋放。每當翻譯一條四元變量所占用的寄存器盡早釋放。每當翻譯一條四元式如式如A=B op C時，需要知道在基本塊中還有哪些四時，需要知道在基本塊中還有哪些四元式要對變量元式要對

7、變量A、B、C進行引用，為此，需要收集進行引用，為此，需要收集一些待用信息。在一個基本塊中，四元式一些待用信息。在一個基本塊中，四元式i對變量對變量A定值，如果定值，如果i后面的四元式后面的四元式j要引用要引用A且從且從i到到j的四元的四元式沒有其它對式沒有其它對A的定值點，則稱的定值點，則稱j是四元式是四元式i中對變量中對變量A的待用信息，同時也稱的待用信息，同時也稱A是活躍的；如果是活躍的；如果A被多處被多處引用，則構成了引用，則構成了A的待用信息鏈與活躍信息鏈。的待用信息鏈與活躍信息鏈。第第7 7章章 目標代碼生成目標代碼生成 為了取得每個變量在基本塊內的待用信息和為了取得每個變量在基本

8、塊內的待用信息和活躍信息，可從基本塊的出口由后向前掃描，對活躍信息，可從基本塊的出口由后向前掃描，對每個變量建立相應的待用信息鏈與活躍信息鏈。每個變量建立相應的待用信息鏈與活躍信息鏈。如果沒有進行數據流分析并且臨時變量不允許跨如果沒有進行數據流分析并且臨時變量不允許跨基本塊引用，則把基本塊中的臨時變量均看作基基本塊引用，則把基本塊中的臨時變量均看作基本塊出口之后的非活躍變量，而把所有的非臨時本塊出口之后的非活躍變量，而把所有的非臨時變量均看作基本塊出口之后的活躍變量。如果某變量均看作基本塊出口之后的活躍變量。如果某些臨時變量能夠跨基本塊使用，則把這些臨時變些臨時變量能夠跨基本塊使用，則把這些臨

9、時變量也看成基本塊出口之后的活躍變量。量也看成基本塊出口之后的活躍變量。第第7 7章章 目標代碼生成目標代碼生成 假設變量的符號表內有待用信息和活躍信息欄，假設變量的符號表內有待用信息和活躍信息欄，則計算變量待用信息的算法如下：則計算變量待用信息的算法如下： (1) 首先將基本塊中各變量的符號表的待用信息首先將基本塊中各變量的符號表的待用信息欄置為欄置為“非待用非待用”，對活躍信息欄則根據該變量在，對活躍信息欄則根據該變量在基本塊出口之后是否活躍而將該欄中的信息置為基本塊出口之后是否活躍而將該欄中的信息置為“活躍活躍”或或“非活躍非活躍”。 (2) 從基本塊出口到基本塊入口由后向前依次處從基本

10、塊出口到基本塊入口由后向前依次處理各四元式。對每個四元式理各四元式。對每個四元式i：A=B op C依次執行依次執行以下步驟：以下步驟：第第7 7章章 目標代碼生成目標代碼生成 把符號表中變量把符號表中變量A的待用信息和活躍信息附加的待用信息和活躍信息附加到四元式到四元式i上；上； 把符號表中變量把符號表中變量A的待用信息和活躍信息分別的待用信息和活躍信息分別置為置為“非待用非待用”和和“非活躍非活躍”； 把符號表中變量把符號表中變量B和和C的待用信息和活躍信息的待用信息和活躍信息附加到四元式附加到四元式i上；上； 把符號表中把符號表中B和和C的待用信息置為的待用信息置為i，活躍信息，活躍信息

11、置為置為“活躍活躍”。第第7 7章章 目標代碼生成目標代碼生成 例例7.1 考察基本塊：考察基本塊： (1) T=AB (2) U=AC (3) V=T+U (4) D=V+U 其中，其中，A、B、C、D為變量，為變量，T、U、V為中為中間變量，試求各變量的待用信息鏈和活躍信息鏈。間變量，試求各變量的待用信息鏈和活躍信息鏈。第第7 7章章 目標代碼生成目標代碼生成 解答解答 我們根據計算變量待用信息的算法得到我們根據計算變量待用信息的算法得到各變量的待用信息鏈和活躍信息鏈如表各變量的待用信息鏈和活躍信息鏈如表7.1所示。所示。表中的表中的“F”表示表示“非待用非待用”或或“非活躍非活躍”，“L

12、”表示表示“活躍活躍”，(1)(4)分別表示基本塊中的四分別表示基本塊中的四個四元式。待用信息鏈和活躍信息鏈的每列從左個四元式。待用信息鏈和活躍信息鏈的每列從左到右為每行從后向前掃描一個四元式時相應變量到右為每行從后向前掃描一個四元式時相應變量的信息變化情況的信息變化情況(空白處表示沒有變化空白處表示沒有變化)。第第7 7章章 目標代碼生成目標代碼生成 表7.1 例7.1的待用信息鏈和活躍信息鏈變量名待 用 信 息活 躍 信 息初值待 用 信 息 鏈初值活 躍 信 息 鏈TF (3) FF LLFAF (2)(1)L LBF (1)L LCF (2) L L UF(4)(3)F FLLF VF

13、(4)F FLF DFF LF 第第7 7章章 目標代碼生成目標代碼生成 待用信息和活躍信息在四元式上的標記如下：待用信息和活躍信息在四元式上的標記如下： (1) T(3)L=A(2)LBFL (2) U(3)L=AFLCFL (3) V(4)L=TFF+U(4)L (4) DFL=VFF+UFF 第第7 7章章 目標代碼生成目標代碼生成 7.1.2 代碼生成算法代碼生成算法 為了在代碼生成中進行寄存器分配，需要隨時為了在代碼生成中進行寄存器分配，需要隨時掌握各寄存器的使用情況，即它是處于空閑狀態還掌握各寄存器的使用情況，即它是處于空閑狀態還是已分配給某個變量或已分配給某幾個變量。通常是已分配

14、給某個變量或已分配給某幾個變量。通常用一個寄存器描述數組用一個寄存器描述數組RVALUE動態地記錄各寄存動態地記錄各寄存器的當前狀況，并用寄存器器的當前狀況，并用寄存器Ri的編號作為它的下標。的編號作為它的下標。此外，還需建立一個變量地址描述數組此外，還需建立一個變量地址描述數組AVALUE來來記錄各變量現行值存放的位置，即其是在某寄存器記錄各變量現行值存放的位置，即其是在某寄存器中還是在某內存單元中，或者同時存在于某寄存器中還是在某內存單元中，或者同時存在于某寄存器和某內存單元中，可以有如下表示：和某內存單元中，可以有如下表示：第第7 7章章 目標代碼生成目標代碼生成 RVALUERi=A

15、/*寄存器寄存器Ri分配給變量分配給變量A*/RVALUERi=A,B /*寄存器寄存器Ri分配給變量分配給變量A和和B*/RVALUERi= /*未分配未分配*/AVALUEA=A /*表示表示A的值在內存中的值在內存中*/AVALUEA=Ri /*表示表示A的值在寄存器的值在寄存器Ri中中*/AVALUEA= Ri ,A /*表示表示A的值既在寄存器的值既在寄存器Ri中中又在內存中又在內存中*/第第7 7章章 目標代碼生成目標代碼生成 為了簡單起見，假設基本塊中每個四元式的形為了簡單起見，假設基本塊中每個四元式的形式都是式都是A=B op C，則代碼生成算法是對每個四元式，則代碼生成算法是

16、對每個四元式 i：A=B op C 執行下述步驟：執行下述步驟： (1) 調用函數調用函數GETREG (i：A=B op C)返回存放返回存放A值值結果的寄存器結果的寄存器R。 (2) 通過地址描述數組通過地址描述數組AVALUE B和和AVALUE C確確定出變量定出變量B和變量和變量C的現行值存放位置的現行值存放位置B和和C；如果；如果是存放在寄存器中，則把寄存器取作是存放在寄存器中，則把寄存器取作B和和C。 (3) 如果如果BR，則生成目標代碼：，則生成目標代碼： MOV R, B op R, C 否則生成目標代碼：否則生成目標代碼： op R, C 如果如果B或或C為為R，則刪除，則

17、刪除AVALUE B或或AVALUE C中的中的R。第第7 7章章 目標代碼生成目標代碼生成 (4) 令令AVALUEA=R并令并令RVALUER=A，表示，表示變量變量A的現行值只在的現行值只在R中且中且R中的值只代表中的值只代表A的現行的現行值。值。 (5) 如果如果B和和C的現行值在基本塊中不再被引用，它們的現行值在基本塊中不再被引用，它們也不是基本塊出口之后的活躍變量且它們的現行值也不是基本塊出口之后的活躍變量且它們的現行值存放在寄存器存放在寄存器Rk中，則刪除中，則刪除RVALUE Rk中的中的B和和C以及以及AVALUE B中的中的Rk，使寄存器，使寄存器Rk不再為不再為B和和C所

18、占用。所占用。第第7 7章章 目標代碼生成目標代碼生成 函數函數GETREG(i：A=B op C)用來得到存放用來得到存放A的的當前值的寄存器當前值的寄存器R；其算法如下：；其算法如下： (1) 如果如果B的現行值在某寄存器的現行值在某寄存器Ri中，且該寄存器只中，且該寄存器只包含包含B的值，或者的值，或者B和和A是同一標識符，或者是同一標識符，或者B在該在該四元式之后不再被引用，則選取四元式之后不再被引用，則選取Ri為所需寄存器并為所需寄存器并轉轉(4)。 (2) 如有尚未分配的寄存器，則從中選取一個如有尚未分配的寄存器，則從中選取一個Ri為所為所需寄存器并轉需寄存器并轉(4)。 (3)

19、從已分配的寄存器中選取一個從已分配的寄存器中選取一個Ri為所需寄存器為所需寄存器R。選取原則為：占用選取原則為：占用Ri的變量的值也同時放在內存中，的變量的值也同時放在內存中，或者該值在基本塊中要在最遠的位置才會引用到。或者該值在基本塊中要在最遠的位置才會引用到。這樣，對寄存器這樣，對寄存器Ri所含的變量和變量在內存中的情所含的變量和變量在內存中的情況必須先做如下調整：況必須先做如下調整：第第7 7章章 目標代碼生成目標代碼生成 對對RVALUE Ri中的每一個變量中的每一個變量M，如果，如果M不是不是A或者或者M既是既是A又是又是C卻不是卻不是B，而，而B又不在又不在RVALUE Ri中，則

20、：中，則： 如果如果AVALUE Ri中不包含中不包含M，則生成目標，則生成目標代碼代碼MOV M, Ri ； 當當M不是不是A時，如果時，如果M是是B或者或者M是是C且同時且同時B 也 在也 在 RVA L U E Ri 中 ， 則 令中 ， 則 令 AVA L U E M=M,R，否則令，否則令AVALUE M=M； 刪除刪除RVALUE Ri中的中的M； (4) 給出給出R，返回。，返回。第第7 7章章 目標代碼生成目標代碼生成 表表7.2 例例7.2的目標代碼的目標代碼四元式四元式目標代碼目標代碼RVALUEAVALUET=ABMOV AX, ASUB AX, BAX含有含有TT在在A

21、X中中U=ACMOV BX, ASUB BX, CAX含有含有TBX含有含有UT在在AX中中U在在BX中中V=T+UADD AX, BXAX含有含有VBX含有含有UV在在AX中中U在在BX中中D=V+UADD AX, BXAX含有含有DD在在AX中中例例7.2 對例對例7.1，假設只有，假設只有AX和和BX是可用寄存器，用是可用寄存器，用代碼生成算法生成目標代碼和相應的代碼生成算法生成目標代碼和相應的RVALUE和和AVALUE。 解答解答 用代碼生成算法生成的目標代碼和相應的用代碼生成算法生成的目標代碼和相應的RVALUE及及AVALUE如表如表7.2所示。所示。第第7 7章章 目標代碼生成

22、目標代碼生成 對其它形式的四元式也可仿照上述算法生成其對其它形式的四元式也可仿照上述算法生成其目標代碼。這里特別要指出的是，對形如目標代碼。這里特別要指出的是，對形如A=B的復的復寫，如果寫，如果B的現行值在某寄存器的現行值在某寄存器Ri中，那么無需生中，那么無需生成目標代碼，只需在成目標代碼，只需在RVALUE Ri中增加一個中增加一個A(即即把把Ri同時分配給同時分配給B和和A)，把，把AVALUE A改為改為Ri；而；而且如果其后且如果其后B不再被引用，還可把不再被引用，還可把RVALUE Ri中的中的B和和AVALUE B中的中的Ri刪除。刪除。 處理完基本塊中所有的四元式后，對現行只

23、在處理完基本塊中所有的四元式后，對現行只在某寄存器中的每個變量，如果它在基本塊出口之后某寄存器中的每個變量，如果它在基本塊出口之后是活躍的，則要用是活躍的，則要用MOV指令把它在寄存器中的值存指令把它在寄存器中的值存放到數據區以它命名的內存單元中。放到數據區以它命名的內存單元中。 第第7 7章章 目標代碼生成目標代碼生成 為進行這一工作，我們利用寄存器描述數組為進行這一工作，我們利用寄存器描述數組RVALUE來決定其中哪些變量的現行值在寄存器中，來決定其中哪些變量的現行值在寄存器中，再利用地址描述數組再利用地址描述數組AVALUE來決定其中哪些變量來決定其中哪些變量的現行值尚不在其內存單元中，

24、最后利用活躍變量的現行值尚不在其內存單元中，最后利用活躍變量信息來決定其中哪些變量是活躍的。例如，由例信息來決定其中哪些變量是活躍的。例如，由例7.2的表的表7.2查查RVALUE欄可知：欄可知：U和和D的值在寄存器中，的值在寄存器中，而從而從AVALUE欄知欄知U和和D的值都不在內存單元中，的值都不在內存單元中，又由例又由例7.1表表7.1知，知，D在基本塊出口之后是活躍變量，在基本塊出口之后是活躍變量，所以，在表所以，在表7.2所生成的目標代碼后面還要生成一條所生成的目標代碼后面還要生成一條目標代碼：目標代碼： MOV D, AX第第7 7章章 目標代碼生成目標代碼生成 7.1.3 寄存器

25、分配寄存器分配 由于寄存器數量有限，為了生成更有效的目標由于寄存器數量有限，為了生成更有效的目標代碼，就必須考慮如何更有效地利用寄存器。為此，代碼，就必須考慮如何更有效地利用寄存器。為此，我們定義指令的執行代價如下：我們定義指令的執行代價如下：每條指令的執行代價每條指令的執行代價=每條指令訪問內存單元次數每條指令訪問內存單元次數+1 假定在循環中，某寄存器固定分配給某變量使假定在循環中，某寄存器固定分配給某變量使用，那么對循環中的每個基本塊，相對于原簡單代用，那么對循環中的每個基本塊，相對于原簡單代碼生成算法所生成的目標代碼，所節省的執行代價碼生成算法所生成的目標代碼，所節省的執行代價可用下述

26、方法計算：可用下述方法計算：第第7 7章章 目標代碼生成目標代碼生成 (1) 在原代碼生成算法中，僅當變量在基本塊中在原代碼生成算法中，僅當變量在基本塊中被定值時，其值才存放在寄存器中。現在把寄存器被定值時，其值才存放在寄存器中。現在把寄存器固定分配給某變量使用，當該變量在基本塊中被定固定分配給某變量使用，當該變量在基本塊中被定值前，每引用它一次就可以少訪問一次內存，則執值前，每引用它一次就可以少訪問一次內存，則執行代價節省行代價節省1。 (2) 在原代碼生成算法中，如果某變量在基本塊在原代碼生成算法中，如果某變量在基本塊中被定值且在基本塊出口之后是活躍的，則出基本中被定值且在基本塊出口之后是

27、活躍的，則出基本塊時要把它在寄存器中的值存放到內存單元中。現塊時要把它在寄存器中的值存放到內存單元中。現在把寄存器固定分配給某變量使用，出基本塊時就在把寄存器固定分配給某變量使用，出基本塊時就無需把它的值存放到其內存單元中，則執行代價節無需把它的值存放到其內存單元中，則執行代價節省省2。第第7 7章章 目標代碼生成目標代碼生成 因此，對循環因此，對循環L中的變量中的變量M，如果分配一個寄存，如果分配一個寄存器給它專用，那么每執行循環一次，其執行代價的器給它專用，那么每執行循環一次，其執行代價的節省數可用下式計算：節省數可用下式計算： 其中其中,USE(M, B)=基本塊基本塊B中對中對M定值前

28、引用定值前引用M的次數的次數 1 如果如果M在基本塊在基本塊B中被定值中被定值 LIVE(M,B)= 且在且在B的出口之后是活躍的的出口之后是活躍的 0 其它情況其它情況 BL USE(M,B)+2*LIVE(M,B) 第第7 7章章 目標代碼生成目標代碼生成 例例7.3 一代碼序列及程序流圖如圖一代碼序列及程序流圖如圖71所示。假所示。假定各基本塊出口之后的活躍變量均為定各基本塊出口之后的活躍變量均為a、b、c，循，循環中的固定寄存器為環中的固定寄存器為AX、BX，則將，則將AX、BX固定固定分配給循環中哪兩個變量可使執行代價節省得最多？分配給循環中哪兩個變量可使執行代價節省得最多？第第7

29、7章章 目標代碼生成目標代碼生成 (1) abc(2) da4(3) eab(4) fce(5) bbc(6) cbf(7) if bc goto (10)B1B5(8) bbc(9) fbfB2B3(10) aaf(11) if af goto (3)(12) haltB4圖圖71 程序流圖程序流圖第第7 7章章 目標代碼生成目標代碼生成 解答解答 (1) 考慮變量考慮變量a的情況：基本塊的情況：基本塊B2中沒有對中沒有對a進行定值，且引用的次數為進行定值，且引用的次數為1(e=ab)；基本塊；基本塊B3沒沒有對有對a進行定值，也沒有引用進行定值，也沒有引用a；基本塊；基本塊B4對對a進行了

30、進行了定值，并且定值前引用的次數為定值，并且定值前引用的次數為1(a=af)。根據執。根據執行代價節省數的計算公式得到：行代價節省數的計算公式得到： USE(a,B2)=1； LIVE(a,B2)=0； USE(a,B3)=0； LIVE(a,B3)=0； USE(a,B4)=1； LIVE(a,B4)=1； 因此，變量因此，變量a在一次循環中執行代價的節省總數為：在一次循環中執行代價的節省總數為：USE(a,B)+2*LIVE(a,B)BL=1+0+1+2*(0+0+1)=4第第7 7章章 目標代碼生成目標代碼生成 (2) 對于變量對于變量b有：有：USE(b,B2)=2； LIVE(b,B

31、2)=1；USE(b,B3)=1； LIVE(b,B3)=1；USE(b,B4)=0； LIVE(b,B4)=0；因此，變量因此，變量b在一次循環中執行代價的節省總數為：在一次循環中執行代價的節省總數為：USE(b,B)+2*LIVE(b,B)BL=2+1+0+2*(1+1+0)=7第第7 7章章 目標代碼生成目標代碼生成 (3) 對于變量對于變量c有：有：USE(c,B2)=2； LIVE(c,B2)=1；USE(c,B3)=1； LIVE(c,B3)=0；USE(c,B4)=1； LIVE(c,B4)=0；因此，變量因此，變量c在一次循環中執行代價的節省總數為：在一次循環中執行代價的節省總

32、數為：USE(c,B)+2*LIVE(c,B)BL=2+1+1+2*(1+0+0)=6第第7 7章章 目標代碼生成目標代碼生成 7.1.4 源程序到目標代碼生成示例源程序到目標代碼生成示例 我們以我們以PC機的匯編語言作為目標代碼，且假機的匯編語言作為目標代碼，且假定可用的寄存器為定可用的寄存器為AX、BX、CX和和DX，則一，則一C語語言源程序轉換為四元式代碼序列，然后再轉換為言源程序轉換為四元式代碼序列，然后再轉換為目標代碼程序目標代碼程序(轉換中不考慮優化轉換中不考慮優化)的結果如下：的結果如下：第第7 7章章 目標代碼生成目標代碼生成 (1) C語言源程序語言源程序(局部局部)whil

33、e (ab)if (m=n) a=a+1;elsewhile (k=h)x=x+2;m=n+x*(m+y);第第7 7章章 目標代碼生成目標代碼生成 (2) 四元式代碼序列四元式代碼序列100 (j, a, b, 102)101 (j, _, _, 117 )102 (j=, m, n, 104)103 (j, _, _, 107 )104 (+, a, 1, T1)105 (=, T1, _ , a )106 (j, _, _, 112)107(j=, k, h, 109 )108 (j, _, _, 112)109 (+, x , 2, T2 )110 (=, T2, _ , x )111

34、 (j, _, _, 107 )112 (+, m, y, T3)113 (*, x, T3, T4 )114 (+, n , T4, T5)115 (=, T5, _ , m )116 (j , _, _, 100)第第7 7章章 目標代碼生成目標代碼生成 (3) 目標代碼程序目標代碼程序(匯編語言程序匯編語言程序); File: compile.asm; *data segment ; 定義數據段定義數據段 h DW k DW m DW n DW x DW y DW a DW b DWdata ends ; 數據段定義結束數據段定義結束第第7 7章章 目標代碼生成目標代碼生成 ; *cod

35、e segment ; 定義代碼段定義代碼段main proc far ; 程序的執行部分程序的執行部分assum cs:code, ds:datastart: push dssubbx, bxpush bxmov bx, data ; 設置設置DS段為當前數據段段為當前數據段mov ds, bx; 語句翻譯由此開始：語句翻譯由此開始：100: mov AX, a cmp AX, b jg 102第第7 7章章 目標代碼生成目標代碼生成 101: mp 117102: mov AX, mcmp AX, njge 104103: jmp 107104: mov AX, aadd AX, 1D10

36、5: mov BX, AXmov a, BX ; 跳出基本塊前保存寄存器中已跳出基本塊前保存寄存器中已改變的變量值改變的變量值106: jmp 112107: movAX, k第第7 7章章 目標代碼生成目標代碼生成 cmp AX, hje 109108: jmp 112109: mov AX, xadd AX, 2D110: mov BX, AXmov x, BX ; 跳出基本塊前保存寄存器中已跳出基本塊前保存寄存器中已改變的變量值改變的變量值111: jmp 107112: mov AX, madd AX, y 113: mul x第第7 7章章 目標代碼生成目標代碼生成 114: mov

37、 BX, nadd BX, AX115: mov CX, BXmov m, CX ; 跳出基本塊前保存寄存器中已跳出基本塊前保存寄存器中已改變的變量值改變的變量值116: jmp 100117: retmain endpcode ends ; 代碼段定義結束代碼段定義結束end start第第7 7章章 目標代碼生成目標代碼生成 *7.2 匯編指令到機器代碼的翻譯概述匯編指令到機器代碼的翻譯概述 雖然我們已經在雖然我們已經在微機原理微機原理或或匯編語匯編語言程序設計言程序設計課程中學習了課程中學習了8086/8088指令系統，指令系統，但那是從掌握匯編語言和微機的原理及使用的但那是從掌握匯編語

38、言和微機的原理及使用的角度來學習指令系統的。現在，我們從編譯的角度來學習指令系統的。現在，我們從編譯的角度來深入了解角度來深入了解8086/8088指令系統的設計特點指令系統的設計特點及實現方法。及實現方法。第第7 7章章 目標代碼生成目標代碼生成 8086/8088指令系統的編碼格式非常緊湊并指令系統的編碼格式非常緊湊并且靈活，其機器碼指令長度為且靈活，其機器碼指令長度為16個字節個字節(不不包括前綴包括前綴)，通常指令的第一字節為操作碼，通常指令的第一字節為操作碼，用以規定操作的類型；第二字節規定操作數的用以規定操作的類型；第二字節規定操作數的尋址方式。尋址方式。 典型的單操作數指令結構如

39、圖典型的單操作數指令結構如圖72所示。所示。第第7 7章章 目標代碼生成目標代碼生成 (a)次操作碼 r/m操作碼w mod操作碼reg(b)圖圖72 典型的單操作數指令典型的單操作數指令 第第7 7章章 目標代碼生成目標代碼生成 典型的雙操作數指令結構如圖典型的雙操作數指令結構如圖73所示。所示。regr/m操作碼dwmod圖圖73 典型的雙操作數指令典型的雙操作數指令第第7 7章章 目標代碼生成目標代碼生成 其中，其中，reg表示寄存器尋址代碼；表示寄存器尋址代碼；mod表示表示尋址方式代碼；尋址方式代碼；r/m表示寄存器或存儲器尋址表示寄存器或存儲器尋址方式方式(與與mod字段組合決定字

40、段組合決定)；d位表示指示操作位表示指示操作數的傳送方向，用于雙操作數指令；數的傳送方向，用于雙操作數指令；w位表示位表示字操作標志位。字操作標志位。d=0時，時，reg字段為源操作數，字段為源操作數，r/m和和mod字段為目的操作數；字段為目的操作數；d=1時，時，r/m和和mod字段為源操作數，字段為源操作數，reg字段為目的操作數。字段為目的操作數。w=0是字節操作指令；是字節操作指令；w=1是字操作指令。是字操作指令。第第7 7章章 目標代碼生成目標代碼生成 由于雙操作數指令只有一個由于雙操作數指令只有一個w位，因此，位，因此，兩個操作數要么都是兩個操作數要么都是8位，要么都是位，要么

41、都是16位。然位。然而，對于值很小的立即數操作來說，如果用而，對于值很小的立即數操作來說，如果用16位表示就有些浪費存儲空間了。為了減少這種位表示就有些浪費存儲空間了。為了減少這種情況下立即數所占用的字節數，情況下立即數所占用的字節數，8086/8088指令指令系統對諸如加法、減法和比較的立即數操作指系統對諸如加法、減法和比較的立即數操作指令設置了符號擴展位令設置了符號擴展位s，s位只對位只對16位操作數位操作數(w=1)有效，即：有效，即： 01 16位位(字字)操作，不進行符號擴展操作，不進行符號擴展 11 16位位(字字)操作，但立即數僅給出操作，但立即數僅給出 低低8位，應進行符號擴展

42、位，應進行符號擴展sw=第第7 7章章 目標代碼生成目標代碼生成 這樣對一些這樣對一些16位立即數操作指令，立即數的存位立即數操作指令，立即數的存儲僅是儲僅是8位的，節省了存儲空間和取指時間，只是位的，節省了存儲空間和取指時間，只是當當CPU執行該操作時再將立即數擴展為執行該操作時再將立即數擴展為16位。位。 8086/8088指令格式主要由操作碼域和操作指令格式主要由操作碼域和操作數域構成。操作碼域指出了該指令操作的類型，數域構成。操作碼域指出了該指令操作的類型，操作碼域中的操作碼域中的d、w位位(如果有的話如果有的話)隨傳送方向及隨傳送方向及字還是字節操作而變化字還是字節操作而變化,少量指

43、令存在著第二操作少量指令存在著第二操作碼。碼。8086/8088指令格式設計的精妙之處在于操作指令格式設計的精妙之處在于操作數域，根據尋址方式、傳送方向數域，根據尋址方式、傳送方向(d位位) 、字或字節、字或字節操作操作(w位位)決定了第二字節決定了第二字節(尋址方式字節尋址方式字節)中中mod字段、字段、r/m字段以及字段以及reg字段的取值及該條指令機字段的取值及該條指令機器碼的長度器碼的長度(須特別注意機器碼長度的確定須特別注意機器碼長度的確定)。第第7 7章章 目標代碼生成目標代碼生成 表7.3 尋址方式表mod=11 寄存器尋址MOD11 存儲器尋址，有效地址的計算r/mw=1w=0

44、modr/m00(不帶位移量)01(帶8位位移量D8)10(帶16位位移量D16)0 0 0AXAL000BX+SIBX+SI+D8BX+SI+D160 0 1CXCL001BX+DIBX+DI+D8BX+DI+D160 1 0DXDL010BP+SIBP+SI+ D8BP+SI+ D160 1 1BXBL011BP+DIBP+DI+ D8BP+DI+ D161 0 0SPAH100SISI+ D8SI+ D161 0 1BPCH101DIDI+ D8DI+ D161 1 0SIDH110D16(直接尋址)BP+ D8BP+ D161 1 1DIBH111BXBX+ D8BX+ D16第第7

45、7章章 目標代碼生成目標代碼生成 表7.4 寄存器表 寄存器尋址編碼寄存器段寄存器尋址編碼段寄存器w=1w=00 0 0AXAL0 0ES0 0 1CXCL0 1CS0 1 0DXDL1 0SS0 1 1BXBL1 1DS1 0 0SPAH 1 0 1BPCH1 1 0SIDH1 1 1DIBH第第7 7章章 目標代碼生成目標代碼生成 有了表有了表7.3和表和表7.4，我們就可以根據傳送方向位，我們就可以根據傳送方向位d、字或字節操作位字或字節操作位w的值以及所要求的尋址方式及參的值以及所要求的尋址方式及參加操作的寄存器或存儲器地址來構造由加操作的寄存器或存儲器地址來構造由mod、r/m和和r

46、eg字段組成的尋址方式字節并形成屬于操作數字段組成的尋址方式字節并形成屬于操作數域的其后各字節內容。例如，數據傳送類指令域的其后各字節內容。例如，數據傳送類指令MOV所允許出現的指令格式有：所允許出現的指令格式有： (1) 寄存器寄存器/存儲器存儲器 寄存器：寄存器： 1 0 0 0 1 0 d w mod reg r/m 第第7 7章章 目標代碼生成目標代碼生成 (2) 立即數立即數 寄存器寄存器/存儲器：存儲器：1 1 1 0 0 0 1 w mod 000 r/m data data if w=1 (3) 立即數立即數 寄存器寄存器:1 0 1 1 w reg data data if

47、w=1 (4) 存儲器存儲器 累加器：累加器： 1 0 1 0 0 0 d w addrlow addrhight 第第7 7章章 目標代碼生成目標代碼生成 (5) 累加器累加器 存儲器：存儲器： 1 0 1 0 0 0 1 w addrlow addrhight (6) 寄存器寄存器/存儲器存儲器 分段寄存器：分段寄存器：1 0 0 0 1 1 1 0 mod 0reg r/m (7) 分段寄存器分段寄存器 寄存器寄存器/存儲器：存儲器： 1 0 0 0 1 1 0 0 mod 0reg r/m 第第7 7章章 目標代碼生成目標代碼生成 對于寄存器對于寄存器/存儲器與寄存器之間的傳送命令可存

48、儲器與寄存器之間的傳送命令可以采用方式以采用方式(1)，如，如: MOV AX，BX ;(BX) AX 由于由于d位值不同，第二字節的編碼可以有兩種形式位值不同，第二字節的編碼可以有兩種形式: 當當d=0時，時，reg對應源操作數對應源操作數BX，即為，即為BX的編碼的編碼011；r/m對應目的操作數對應目的操作數AX，即為，即為AX的編的編碼碼000；此時；此時mod值為值為11，表示操作數為寄存器，表示操作數為寄存器，即即mod值和值和r/m值共同決定了這個操作數的類型是值共同決定了這個操作數的類型是寄存器并且是寄存器并且是AX(000)。因此該指令的機器碼如下。因此該指令的機器碼如下:

49、操作碼操作碼 d w mod reg r/m 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0第第7 7章章 目標代碼生成目標代碼生成 當當d=1時，時，reg對應目的操作數對應目的操作數AX，即為，即為AX的編碼的編碼000；r/m對應源操作數對應源操作數BX，即為，即為BX的編碼的編碼011；mod值指示寄存器應為值指示寄存器應為11；所以此時該指令的；所以此時該指令的機器碼如下機器碼如下: 操作碼操作碼 d w mod reg r/m 1 0 0 0 1 0 1 1 1 1 0 0 0 0 1 1第第7 7章章 目標代碼生成目標代碼生成 如果指令是寄存器與存儲器之間的傳送操

50、作，如果指令是寄存器與存儲器之間的傳送操作，例如：例如：MOV AX,BX+DI+1234H，則對應的機器，則對應的機器指令只能有一種形式。這是因為指令只能有一種形式。這是因為reg段只能表示寄段只能表示寄存器而無法表示存儲器，而存器而無法表示存儲器，而mod和和r/m字段的組合字段的組合根據根據mod域值既可以表示寄存器又可以表示存儲器，域值既可以表示寄存器又可以表示存儲器，故當操作數的一方是存儲器時就只能用故當操作數的一方是存儲器時就只能用mod和和r/m字段來表示了。究竟是將寄存器的內容傳送到存字段來表示了。究竟是將寄存器的內容傳送到存儲器還是將存儲器的內容傳送到寄存器，這取決儲器還是將

51、存儲器的內容傳送到寄存器，這取決于傳送方向位于傳送方向位d的值。的值。 第第7 7章章 目標代碼生成目標代碼生成 本條指令的存儲器地址通過查找表本條指令的存儲器地址通過查找表7.3可知，可知，mod值為值為10，r/m值為值為001；而由表；而由表7.4得知得知reg所對所對應的操作數應的操作數AX值為值為000，并且，并且d位值必須為位值必須為1才能保才能保證將證將mod和和r/m指定的內容送指定的內容送AX，所以此時該指令，所以此時該指令對應的機器碼為：對應的機器碼為： 操作碼操作碼 d w mod reg r/m 16位位移量位位移量 1 0 0 0 1 0 1 1 1 0 0 0 0

52、0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 0第第7 7章章 目標代碼生成目標代碼生成 對于立即數傳送到寄存器對于立即數傳送到寄存器/存儲器的操作可采用方存儲器的操作可采用方式式(2)，如：，如： MOV CL,12H ; 立即數立即數12HCL 這是一個字節傳送指令，即這是一個字節傳送指令，即w=0， 因 此， 因 此mod=11和和r/m=001表示寄存器表示寄存器CL，第三字節為立，第三字節為立即數即數12H，即該指令的機器碼如下：，即該指令的機器碼如下： 操作碼操作碼 w mod reg r/m 立即數立即數 1 1 0 0 0 1 1 0 1 1 0 0

53、0 0 0 1 0 0 0 1 0 0 1 0 第第7 7章章 目標代碼生成目標代碼生成 如果用方式如果用方式(3)實現該操作則更加簡單。由于此時實現該操作則更加簡單。由于此時w=0，reg=001，則該指令所對應的機器碼為：，則該指令所對應的機器碼為： 操作碼操作碼 w reg 立即數立即數 1 0 1 1 0 0 0 1 0 0 0 1 0 0 1 01 0 1 1 0 0 0 1 0 0 0 1 0 0 1 0 第第7 7章章 目標代碼生成目標代碼生成 與方式與方式(2)的機器碼相比節省了一個字節。的機器碼相比節省了一個字節。 下面，我們看一下立即數傳送到存儲器的操作，下面，我們看一下立

54、即數傳送到存儲器的操作，這種操作只能用方式這種操作只能用方式(2)實現，例如：實現，例如：MOV BX+DI+1234H, 5678H查表查表7.3可知：可知：mod=10，r/m=001；此時該指令對應的機器碼為：；此時該指令對應的機器碼為： 操作碼操作碼 dw mod reg r/m 16位位移量位位移量 16位立即數位立即數11000111 10000001 00110100 00010010 01111000 01010110第第7 7章章 目標代碼生成目標代碼生成 由由 mod=10可知，存儲器操作數還帶有可知，存儲器操作數還帶有16位位位位移量，這個移量，這個16位位移量是緊隨在機

55、器碼第二字節即位位移量是緊隨在機器碼第二字節即尋址方式字節之后的，所以位移量必須插到立即數尋址方式字節之后的，所以位移量必須插到立即數之前，以便形成存儲器的有效地址。注意，此時的之前，以便形成存儲器的有效地址。注意，此時的機器碼指令長度為機器碼指令長度為6個字節，這是個字節，這是8086/8088指令系指令系統中最長的機器碼指令形式。統中最長的機器碼指令形式。 通過機器碼指令的形成過程可知，機器碼指令通過機器碼指令的形成過程可知，機器碼指令的長度是由字或字節操作以及尋址方式決定的。這的長度是由字或字節操作以及尋址方式決定的。這一點對編譯來說很重要，因為在編譯過程中必須根一點對編譯來說很重要，因

56、為在編譯過程中必須根據源指令來確定形成的機器碼指令所應具有的字節據源指令來確定形成的機器碼指令所應具有的字節數數(即長度即長度)。第第7 7章章 目標代碼生成目標代碼生成 由由8086/8088指令系統的尋址方式和機器碼指令指令系統的尋址方式和機器碼指令的尋址方式字節即的尋址方式字節即mod、r/m和和reg字段可以看出：字段可以看出：雙操作數指令允許寄存器與寄存器、寄存器與存儲雙操作數指令允許寄存器與寄存器、寄存器與存儲器之間進行操作，此外還允許立即數到寄存器器之間進行操作，此外還允許立即數到寄存器/存儲存儲器的操作；但無法用器的操作；但無法用mod、r/m和和reg字段來同時表字段來同時表

57、示兩個存儲器的地址。如果允許存儲器到存儲器操示兩個存儲器的地址。如果允許存儲器到存儲器操作的指令出現，將會使機器碼指令變得更長、更復作的指令出現，將會使機器碼指令變得更長、更復雜。故此，雜。故此，8086/8088舍去了直接進行存儲器之間操舍去了直接進行存儲器之間操作的指令，使得機器指令更加簡潔有效。如果要實作的指令，使得機器指令更加簡潔有效。如果要實現存儲器到存儲器的操作，只需經過寄存器過渡：現存儲器到存儲器的操作，只需經過寄存器過渡：先進行存儲器到寄存器的操作，并將結果保存在寄先進行存儲器到寄存器的操作，并將結果保存在寄存器中，然后再使用一條由寄存器傳送到存儲器的存器中，然后再使用一條由寄

58、存器傳送到存儲器的指令操作即可。指令操作即可。第第7 7章章 目標代碼生成目標代碼生成 我們再看一下增量指令我們再看一下增量指令INC的處理。的處理。INC指指令可以采用的機器碼格式如下：令可以采用的機器碼格式如下： (1) 寄存器：寄存器： 0 1 0 0 0 reg (2) 寄存器寄存器/存儲器：存儲器： 1 0 0 0 1 0 d w mod 000 r/m 第第7 7章章 目標代碼生成目標代碼生成 01000100方式方式(1)為單操作數指令，由于為單操作數指令，由于reg字字段無法表示出是段無法表示出是8位寄存器還是位寄存器還是16位寄存器，因而位寄存器，因而系統規定它為系統規定它為

59、16位寄存器的操作，如位寄存器的操作，如 表表示為示為INC SP，而不是，而不是INC AH。 對對8位位(或或16位位)寄存器或存儲器進行寄存器或存儲器進行INC操作可操作可采用方式采用方式(2)，但，但16位寄存器的位寄存器的INC則最好按方式則最好按方式(1)翻譯成機器碼，這樣可節省一個字節空間。翻譯成機器碼，這樣可節省一個字節空間。 算術運算中的加法指令算術運算中的加法指令ADD可以采用的機器碼可以采用的機器碼格式如下：格式如下： (1) 寄存器寄存器/存儲器與寄存器相加，其結果送存儲器與寄存器相加，其結果送二者之一：二者之一：01000100第第7 7章章 目標代碼生成目標代碼生成 (2) 立即數與寄存器立即數與寄存器/存儲器相加，結果送寄存器存儲器相加，結果送寄存器/存儲器：存