1、1第八章第八章 目標代碼生成目標代碼生成一一 概述概述 1 目標代碼的形式目標代碼的形式 (1)能立即執行的目標代碼；能立即執行的目標代碼；(2)待裝配的浮動目標代碼待裝配的浮動目標代碼;(3)匯編語言目標代碼匯編語言目標代碼. 2 目標代碼生成原則目標代碼生成原則 (1) 生成的目標代碼短而高效生成的目標代碼短而高效;(2) 充分利用寄存器充分利用寄存器,減少訪問內存的次數減少訪問內存的次數.2二二 計算機模型計算機模型 假設計算機只有四種類型的機器指令假設計算機只有四種類型的機器指令: 指令類型指令類型 指令形式指令形式意義意義直接地址型直接地址型 op Ri,M(Ri)op(M) Ri寄

2、存器型寄存器型 op Ri,Rj(Ri)op(Rj) Ri變址型變址型 op Ri,C(Rj)(Ri)op(Rj)+C) Ri間址型間址型 op Ri,*M(Ri)op(M) Ri op Ri,*Rj(Ri)op(Rj) Ri op Ri,* C(Rj) (Ri)op(Rj)+C) Ri3三三 代碼生成器及輔助信息代碼生成器及輔助信息 基本思想基本思想: 當生成計算某變量值的目標代碼時當生成計算某變量值的目標代碼時,盡量讓該變量盡量讓該變量的值保存在某個寄存器中的值保存在某個寄存器中,直到該寄存器要用來存放其它變量的值直到該寄存器要用來存放其它變量的值或者基本塊結束之前不再引用該變量的值或者基

3、本塊結束之前不再引用該變量的值,才把該變量的值存放才把該變量的值存放到存儲器中到存儲器中. 為了能知道某變量的值是否在寄存器中為了能知道某變量的值是否在寄存器中,在那個寄存器中在那個寄存器中,是是否該送回內存中等否該送回內存中等,需要一些輔助信息需要一些輔助信息.1 待用信息待用信息 當翻譯到四元式當翻譯到四元式 A:=B op C 時時,我們需要知道基本塊內后面我們需要知道基本塊內后面的四元式是否還引用的四元式是否還引用 A B C ,是哪些四元式引用是哪些四元式引用? 定義定義: 設四元式設四元式(i) 對對A定值且到達四元式定值且到達四元式( j) ,四元式四元式 ( j) 中引用中引用

4、 A ,則稱則稱 j 是四元式是四元式 i 的變量的變量A 的的待用信息待用信息; 滿足上述定義滿足上述定義 的所有的所有 j, 構成了構成了 A 的的待用信息集待用信息集.4采用如下方式表示待用信息集采用如下方式表示待用信息集,為每個四元式建立一個如下的表項為每個四元式建立一個如下的表項: 定值名定值名 指針指針 引用名引用名1 指針指針 引用名引用名2 指針指針 A * B * C * A * B Nil C Nil 通過鏈表把通過鏈表把 A 的所有待用信息連接起來的所有待用信息連接起來.當執行到當執行到 A:=B op C時時,就可以檢查待用信息鏈就可以檢查待用信息鏈,確定確定 A B

5、C 在該四元式之后是否還引在該四元式之后是否還引用用(若為若為 Nil ,表示不再引用表示不再引用, 此時此時,應將非活躍變量的寄存器釋放應將非活躍變量的寄存器釋放,存入內存中存入內存中).52 寄存器描述寄存器描述 假設系統可以使用的寄存器為假設系統可以使用的寄存器為: R1,R2,.,Rn 每個寄存器都需要描述是否被占用每個寄存器都需要描述是否被占用,被哪些變量占用被哪些變量占用?假設假設 RVALUE Ri 為集合類型為集合類型,用于描述寄存器用于描述寄存器 Ri 的使用情況的使用情況,也即哪些變量同時占用了也即哪些變量同時占用了 Ri.3 變量描述變量描述 在翻譯過程中在翻譯過程中,應

6、了解基本塊中的每個變量的存儲狀況應了解基本塊中的每個變量的存儲狀況,確定確定變量的值是在寄存器中還是在內存中變量的值是在寄存器中還是在內存中? 假設假設 AVALUE A 為集合類型為集合類型,用于描述變量用于描述變量 的存儲情況的存儲情況:AVALUE A= Ri A的有效值在寄存器中的有效值在寄存器中; M A的有效值在內存中的有效值在內存中; Ri,M 均有效均有效.64 代碼生成算法代碼生成算法 下面下面,僅討論一般情形僅討論一般情形 A:=B op C 的代碼翻譯的代碼翻譯, GetReg( A:= B op C) 函數返回一個寄存器函數返回一個寄存器 R ,存放變量存放變量 A的值

7、的值. 代碼生成算法代碼生成算法: (對四元式對四元式 A:= B op C) (1) 令令 R = GetReg( A:= B op C) ; (2) 由由 AVALUE A , AVALUE B 確定確定 變量變量 B C 值的有值的有 效存儲位置效存儲位置 B,C (3) 若若 B=R 生成生成 機器指令機器指令 op B,C 否則否則 生成機器指令生成機器指令 mov R,B op R,C 若若 B=R ,則刪除則刪除 AVALUE B 中的中的 R ; 若若 C=R ,則刪除則刪除 AVALUE C 中的中的 R; 令令 AVALUE A = R ; RVALUE R = A ;7

8、(4) 若若 B 的值在基本塊內不再引用的值在基本塊內不再引用,且且 AVALUE B= Ri 則產生目標指令則產生目標指令 : mov Ri,B; 刪除刪除 AVALUE B 中的中的 Ri; 刪除刪除 RVALUE Ri 中的中的 B; /釋放寄存器釋放寄存器 Ri. (5) 若若 C 的值在基本塊內不再引用的值在基本塊內不再引用,且且 AVALUE C= Ri 則產生目標指令則產生目標指令 : mov Ri,C; 刪除刪除 AVALUE C 中的中的 Ri; 刪除刪除 RVALUE Ri 中的中的 C; /釋放寄存器釋放寄存器 Ri. (6) 返回返回8 5 GetReg( A:= B op C) 算法算法(1) 若若 B 的值在的值在 R 中中, 且且 RVALUER 只含只含 B,且且 ( A=B 或或 B 的值在基本塊內不再引用并且的值在基本塊內不再引用并且 B 的值已存的值已存 入內存中入內存中) 則則 return (R);(2) 否則否則,若有尚未分配的若有尚未分配的 R 則則 return(R);(3) 否則