編譯原理 第十章 代碼生成

1、第十章 代碼生成v代碼生成概述代碼生成概述v構造代碼生成程序的幾種方法構造代碼生成程序的幾種方法代碼生成概述v代碼生成階段v構造代碼生成程序要考慮的因素v一個簡單的代碼生成程序的構造代碼生成器的位置代碼生成器的輸入中間代碼符號表中的信息編譯前端代碼優(yōu)化代碼生成器符號表目標程序源程序中間代碼中間代碼代碼生成器(程序)的位置代碼生成器v目標代碼一般有三種形式：能夠立即執(zhí)行的機器語言代碼，所有地址均已定位待裝配的機器語言模塊。當需要執(zhí)行時，由連接裝入程序把它們和某些運行程序連接起來，轉換成能執(zhí)行的機器語言代碼匯編語言代碼。尚需經(jīng)過匯編程序匯編，轉換成可執(zhí)行的機器語言代碼構造代碼生成器所要考慮的主要問

2、題v代碼生成所要考慮的主要問題如何使生成的目標代碼較短 如何充分利用計算機的寄存器，減少目標代碼中訪問存儲單元的次數(shù)返回代碼生成的主要成份v指令選擇尋找一個合適的目標機指令以實現(xiàn)給定的中間表示v寄存器分配確定在程序的哪個點將哪些值放在寄存器中比較有益v指令調度確定程序指令的執(zhí)行順序v三者的關系指令選擇v如：中間代碼a:=a+1: 實現(xiàn)1：INCa 實現(xiàn)2：LDR0，a ADD R0, #1 ST R0，av主要功能多數(shù)CPU的指令集合具有冗余性。指令選擇器選擇其中之一以產(chǎn)生最好的代碼。v指令選擇的基本原則減小產(chǎn)生代碼的尺寸減小目標代碼的執(zhí)行時間目標機器的地址方式地址方式匯編形式地址增加的開銷直

3、接地址方式MM1寄存器方式RR0間接寄存器方式*Rcontents(R)1索引方式c(R)c+contents(R)1間接索引方式*c(R)contents(c+contents(R)2每條指令的執(zhí)行代價=每條指令訪問主存單元次數(shù)+1a:=b+c1. MOV b, R0ADDc,R0cost=6MOV R0, a2.MOV b,aADD c,acost=6 假定R0, R1和R2中分別存放了a, b和c的地址, 采用:3.MOV *R1,*R0ADD*R2,*R0cost=6 假定R1和R2中分別包含b和c的值, 并且b的值在這個賦值以后不再需要, 則還可有4.ADDR2,R1MOV R1,a

4、cost=3寄存器分配v指令在寄存器中訪問操作數(shù)的開銷要比在內存中訪問小。且許多指令不能直接訪問內存。應將經(jīng)常使用的操作數(shù)保存在寄存器中。寄存器是比較稀少的資源，程序所需要的寄存器要比可用的寄存器多。寄存器分配負責確定在程序的哪個點將哪些值放在寄存器中比較有益。v寄存器的分配可以分成兩個子問題：在寄存器分配期間，為程序的某一點選擇駐留在寄存器中的一組變量；在隨后的寄存器指派階段，挑出變量將要駐留的具體寄存器。寄存器分配原則v盡量讓變量的值或計算結果保留在寄存器。這樣，訪問變量值時可減少對內存的存取次數(shù)，以提高運行速度；v當?shù)交緣K出口時，將變量的值存放在內存中，因為一個基本塊可能有多個后繼結點

5、或多個前驅結點，同一變量名在不同前驅結點的基本塊內出口前存放的R可能不同，或沒有定值，所以應在出口前把寄存器的內容放在內存中，這樣從基本塊外入口的變量值都在內存中；v在同一基本塊內后邊不再被引用的變量所占用的寄存器應盡早釋放，以提高寄存器的利用率。寄存器分配與寄存器賦值v寄存器分配確定在程序的某個點將哪些值放在寄存器中v寄存器賦值確定分配有寄存器的值應該在哪個寄存器中。由于一些目標機可能具有不同類型的寄存器，因此，對寄存器使用的一致性方面也存在著一定的約束。圖12.27指令調度v對具有流水線限制的體系結構，這個階段是必須的。如：RISC體系結構一個通用的流水線限制為：從內存中取入寄存器中的值在

6、隨后的某幾個周期中是不能用的。在這期間，調不依賴于該取入值的指令來執(zhí)行是很重要的。v必須找一個指令（與被取值無關）在取指令之后立即執(zhí)行，如果找不到相應的指令，這些周期就會被浪費。不同在于指令順序和寄存器的賦值一個簡單的代碼生成器在一個基本塊范圍內考慮如何充分利用寄存器的問題：在一個基本塊范圍內考慮如何充分利用寄存器的問題：u盡可能地讓該變量的值保留在寄存器中盡可能地讓該變量的值保留在寄存器中u盡可能引用變量在寄存器中的值盡可能引用變量在寄存器中的值待用信息：若在一個基本塊中，變量待用信息：若在一個基本塊中，變量A在四元式在四元式i中被定值，中被定值，在在i后面的四元式后面的四元式j中要引用中要

7、引用A值，且從值，且從i到到j之間沒有其它對之間沒有其它對A的定值點，這時我們的定值點，這時我們稱稱 j是四元式是四元式i中對變量中對變量A的待用信息的待用信息，同時也同時也稱稱A是活躍的是活躍的，若，若A被多次引用則可構成待用信息鏈被多次引用則可構成待用信息鏈與活躍信息鏈。與活躍信息鏈?？蓮幕緣K的出口由后向前掃描，對每個變量建立相應的待可從基本塊的出口由后向前掃描，對每個變量建立相應的待用信息鏈和活躍變量信息鏈。用信息鏈和活躍變量信息鏈。計算待用信息的算法：計算待用信息的算法： 符號表中增加符號表中增加“待用信息待用信息”欄和欄和“活躍信息活躍信息”欄對各基本塊的欄對各基本塊的符號表中的符

8、號表中的“待用信息待用信息”欄和欄和“活躍信息活躍信息”欄置初值，即把欄置初值，即把“待用信息待用信息”欄置欄置“非待用非待用”，對，對“活躍信息活躍信息”欄按在基本塊欄按在基本塊出口處是否為活躍而置成出口處是否為活躍而置成“活躍活躍”或或“非活躍非活躍”。這里假定變。這里假定變量都是活躍的，臨時變量都是非活躍的。量都是活躍的，臨時變量都是非活躍的。從基本塊出口到基本塊入口由后向前依次處理每個四元式從基本塊出口到基本塊入口由后向前依次處理每個四元式i i， A:=B op CA:=B op C，依次執(zhí)行下述步驟：，依次執(zhí)行下述步驟：a)a)把符號表中變量把符號表中變量A A的待用信息和活躍信息

9、附加到四元式上。的待用信息和活躍信息附加到四元式上。b)b)把符號表中變量把符號表中變量A A的待用信息欄和活躍信息欄分別置為的待用信息欄和活躍信息欄分別置為“非待用非待用”和和“非活躍非活躍”。c)c)把符號表中變量把符號表中變量B B和和C C的待用信息和活躍信息附加到四元式的待用信息和活躍信息附加到四元式i i上。上。d)d)把符號表中變量把符號表中變量B B和和C C的待用信息欄置為的待用信息欄置為“i i”，活躍信息欄置為，活躍信息欄置為“活躍活躍”。注意，以上注意，以上a)a)、b)b)、c)c)和和d)d)的次序不能顛倒。的次序不能顛倒。四元式序列如下：四元式序列如下：(1) T

10、:=A-B(2) U:=A-C(3) V:=T+U(4) D:=V+U寄存器描述和地址描述 寄存器描述數(shù)組RVALUE和變量地址描述數(shù)組AVALUE使用之，先了解之R空閑A-RA、B、-RRVALUEAVALUER-AM-AR、M-A引用某變量值先了解其所在基本塊的代碼生成算法，假設只有A:=B op C的四元式序列1對每個四元式i: A:=B op C，依次執(zhí)行下述步驟： 調用過程getreg(i: A:=B op C) ，得到一寄存器R，用它存放A現(xiàn)行值； 利用AVALUEB和AVALUEC，確定出B和C現(xiàn)行值存放位置B和C； (1)如BR，則生成目標代碼 LD R，B op R，C 否則，生成目標代碼 op R，C 如B或C為R，則刪除AVALUEB或AVALUEC中的R (2)令AVALUEA=R，并令RVALUER=A； (3)如B或C的現(xiàn)行值在基本塊中不再被引用，它們也不是基本塊出口之后的活躍變量，并且其現(xiàn)行值在某個寄存器Rk中