編譯原理 代碼生成2

1、代碼生成 代碼生成 代碼生成的輸入 各種中間代碼形式 目標代碼與目標機器模型 簡單的代碼生成器 基本塊dag圖及代碼生成 目標代碼 絕對地址目標代碼 可重定位的目標 linker/loader 匯編代碼 assembler 目標機器模型 指令形式 op 源，目的 尋址模式 絕對地址：op m, r r op (m)r 寄存器：op r1,r2 r2 op r1 r2 變址：op r1,c(r2) (c+r2) op r1 (c+r2) 間接變址、間接寄存器 直接量 op $c, r r + c r 簡單代碼生成器 寄存器描述 記錄寄存器的使用情況，即某寄存器中存放 的是哪（些）個名字（變量）的

2、值。 名字地址描述 名字（變量）的當前值的存放場所，如放在 寄存器或主存（數(shù)據(jù)區(qū)）或者棧里等。 簡單代碼生成器（續(xù)） 代碼生成算法 對基本塊中三地址代碼，p： x := y op z， 1）調(diào)用函數(shù)getreg( )，返回存放計算結果的場所l（一般 為寄存器r，也可能是存儲單元）； 2）若y的值不在l中，產(chǎn)生指令：mov y, l （查y的名字地 址描述獲得y值的存放場所y）； 3）產(chǎn)生指令：op z，l （ z是z值的存放場所），修改x的 名字描述和相關寄存器描述； 4）若y和/或z在p之后不再引用、出口不活躍且其值在寄存 器中，則修改其相應寄存器和名字地址描述； 5）在塊出口處，將所有活躍

3、名字值刷新到相應存儲單元。 簡單代碼生成器（續(xù)） 函數(shù)getreg（p：x := y op z）： 返回計算結果存放場所l， 1）若某寄存器r僅含y的值且p后不再引用和不活 躍，則返回r；（好處是可以省掉裝載y值的指 令mov y，l） 2）返回某個空閑寄存器r； 3）若x必須使用寄存器，則此時“搶占”某個寄 存器r。 查看r的描述，如果名字a的值在r中 則產(chǎn)生轉儲指令mov r,ma （ma：a的存儲單 元），并修改相應的描述；（關鍵是如何搶占 及剝奪哪些名字的寄存器使用權） 4）使用x的存儲單元 e.g.1 簡單代碼生成 三地址碼序列： t := a b u := a + c v := t

4、 + u w:= v + u 可用寄存器r0，r1 初始，名字a、b和c的值均在相應存儲單元中 tac目標代碼reg name t:=a-bmov a, r0 sub b, r0 r0含t t在r0 u:=a+c mov a, r1 r0含t t在r0 add c, r1 r1含u u在r1 v:=t+u add r1, r0 r0含v v在r0 r1含u u在r1 w:=v+u add r1, r0 r0含w w在r0 e.g.1 簡單代碼生成 其它語句的代碼生成 語句 i 在ri i 在mi i 在棧中 a := bi mov b(ri),r mov mi,r mov si(bp),r m

5、ov b(r),r mov b(r),r ai := b mov b,a(ri) mov mi,r mov si(bp),r mov b,a(r) mov b,a(r) si是i在棧中偏移，bp是當前活動記錄基址。 指針操作語句：a := * b *a := b 轉移語句 goto x jmp x if x op y goto z 根據(jù)寄存器內(nèi)容是否滿足以下條件： 負、零、正、非負、非零、非正 如 if x y goto z : y x r 判別r非負（實施轉移） 根據(jù)條件碼轉移 如 if x x則轉z at i = 0; /printf(%ldn, (i=i+1)+(i=i+1)+(i=i+

6、1); case 1 /printf(%ldn, (+i)+(+i)+(+i); case 2 /printf(%ldn, (i+)+(i+)+(i+); case 3 return 0; case 1 case 2 case 3 movl $0,-4(%ebp) movl -4(%ebp),%edx incl %edx movl %edx,%eax movl %eax,-4(%ebp) movl -4(%ebp),%edx incl %edx movl %edx,%ecx movl %ecx,-4(%ebp) addl %ecx,%eax movl -4(%ebp),%edx incl %e

7、dx movl %edx,%ecx movl %ecx,-4(%ebp) addl %ecx,%eax pushl %eax pushl $.lc0 call printf movl $0,-4(%ebp) incl -4(%ebp) incl -4(%ebp) movl -4(%ebp),%eax movl -4(%ebp),%edx addl %edx,%eax incl -4(%ebp) addl -4(%ebp),%eax pushl %eax pushl $.lc0 call printf movl $0,-4(%ebp) movl -4(%ebp),%eax movl -4(%eb

8、p),%edx addl %edx,%eax movl %eax,%edx addl -4(%ebp),%edx pushl %edx incl -4(%ebp) incl -4(%ebp) incl -4(%ebp) pushl $.lc0 call printf 基本塊的dag圖示 基本塊內(nèi)優(yōu)化變換 合并已知量 刪除冗余運算公共子表達式 刪除死代碼 基本塊dag構造 （不考慮別名、數(shù)組或指針） 對于每條語句：x := y op z （1）分別尋找代表y或z的當前值的結點，若沒有 的話，構造它們的初始結點； （2）利用已有的算符op的結點或新建一個op結點 （左、右子樹分別標記為y和z），將

9、x標記在旁邊； （3）如果x在其他結點邊上有標記（x0 x的初始值 除外），則去除這個標記； （4）x := y ，不必建立新結點而將x標記在y對應的 結點旁。 基本塊dag構造 4 i0 * t1 (1)t1 := 4 * i (2)t2 := a t1 (3)t3 := 4 * i (4)t4 := b t3 (5)t5 := t2 * t4 (6)t6 := prod + t5 (7)prod := t6 (8)t7 := i + 1 (9)i := t7 (10)if i = 20 goto (1) 基本塊dag構造 (1)t1 := 4 * i (2)t2 := a t1 (3)t3

10、 := 4 * i (4)t4 := b t3 (5)t5 := t2 * t4 (6)t6 := prod + t5 (7)prod := t6 (8)t7 := i + 1 (9)i := t7 (10)if i = 20 goto (1) 4 i0 *t1 a =t2 基本塊dag構造 (1)t1 := 4 * i (2)t2 := a t1 (3)t3 := 4 * i (4)t4 := b t3 (5)t5 := t2 * t4 (6)t6 := prod + t5 (7)prod := t6 (8)t7 := i + 1 (9)i := t7 (10)if i = 20 goto

11、(1) 4 i0 * t1,t3 a =t2 基本塊dag構造 (1)t1 := 4 * i (2)t2 := a t1 (3)t3 := 4 * i (4)t4 := b t3 (5)t5 := t2 * t4 (6)t6 := prod + t5 (7)prod := t6 (8)t7 := i + 1 (9)i := t7 (10)if i = 20 goto (1) 4 i0 * t1,t3 a =t2 b =t4 基本塊dag構造 (1)t1 := 4 * i (2)t2 := a t1 (3)t3 := 4 * i (4)t4 := b t3 (5)t5 := t2 * t4 (6

12、)t6 := prod + t5 (7)prod := t6 (8)t7 := i + 1 (9)i := t7 (10)if i = 20 goto (1) 4 i0 * t1,t3 a =t2 b =t4 *t5 基本塊dag構造 (1)t1 := 4 * i (2)t2 := a t1 (3)t3 := 4 * i (4)t4 := b t3 (5)t5 := t2 * t4 (6)t6 := prod + t5 (7)prod := t6 (8)t7 := i + 1 (9)i := t7 (10)if i = 20 goto (1) 4 i0 * t1,t3 a =t2 b =t4

13、*t5 + prod0 t6 基本塊dag構造 (1)t1 := 4 * i (2)t2 := a t1 (3)t3 := 4 * i (4)t4 := b t3 (5)t5 := t2 * t4 (6)t6 := prod + t5 (7)prod := t6 (8)t7 := i + 1 (9)i := t7 (10)if i = 20 goto (1) 4 i0 * t1,t3 a =t2 b =t4 *t5 + prod0 t6,prod 基本塊dag構造 (1)t1 := 4 * i (2)t2 := a t1 (3)t3 := 4 * i (4)t4 := b t3 (5)t5 :

14、= t2 * t4 (6)t6 := prod + t5 (7)prod := t6 (8)t7 := i + 1 (9)i := t7 (10)if i = 20 goto (1) 4 i0 * t1,t3 a =t2 b =t4 *t5 + prod0 t6,prod 1 + t7 基本塊dag構造 (1)t1 := 4 * i (2)t2 := a t1 (3)t3 := 4 * i (4)t4 := b t3 (5)t5 := t2 * t4 (6)t6 := prod + t5 (7)prod := t6 (8)t7 := i + 1 (9)i := t7 (10)if i = 20

15、 goto (1) 4 i0 * t1,t3 a =t2 b =t4 *t5 + prod0 t6,prod 1 + t7,i 基本塊dag構造 (1)t1 := 4 * i (2)t2 := a t1 (3)t3 := 4 * i (4)t4 := b t3 (5)t5 := t2 * t4 (6)t6 := prod + t5 (7)prod := t6 (8)t7 := i + 1 (9)i := t7 (10)if i = 20 goto (1) 4 i0 * t1,t3 a =t2 b =t4 *t5 + prod0 t6,prod 1 + t7,i20 = (1) 基本塊dag構造

16、 (1)t1 := 4 * i (2)t2 := a t1 (3)t3 := 4 * i (4)t4 := b t3 (5)t5 := t2 * t4 (6)t6 := prod + t5 (7)prod := t6 (8)t7 := i + 1 (9)i := t7 (10)if i = 20 goto (1) (1)t1 := 4 * i (2)t2 := a t1 (3)t4 := b t1 (4)t5 := t2 * t4 (5)prod := prod + t5 (6)i := i + 1 (7)if i = 20 goto (1) dag優(yōu)化后 特殊情況下（副作用）注銷節(jié)點 f數(shù)組元素 f指針訪問 f過程調(diào)用 f多變量共享存貯 基本塊dag構造 基本塊dag構造 x := a i a j := y z := a i x := a i z := x a j := y dag優(yōu)化后 但如果 在 i=j 且 ai y時，變換前后語義不等價。 解決方案：在構造a i 或a j 時，注銷所有=或= 節(jié)點，即不利用已有節(jié)點（做為公共子表達式）， 而構造一個新的節(jié)點。 由dag生成代碼 dag中節(jié)點重