編譯程序原理與實現：第10章 目標代碼生成

1、詞法分析語法分析語義分析中間代碼優(yōu)化中間代碼生成目標代碼生成分析合成第十章 目標代碼生成目標代碼生成概述目標語言四元式到目標指令的翻譯*寄存器分配*臨時變量地址分配目標代碼生成概述目標代碼生成器主要任務: 將中間代碼轉換成等價的目標機指令(包括計算指令和管理AR的指令等)，同時完成變量的地址分配,寄存器分配。輸入：中間代碼/TokenList/AST+符號表輸出（多種形式可選）：絕對機器代碼：執(zhí)行速度快，缺乏靈活性可重定位機器代碼：可分模塊編譯，需連接和裝入匯編代碼：生成的匯編代碼還要經過匯編程序匯編才可運行虛擬機的代碼：增加可移植性，需要虛擬機的解釋器衡量目標代碼質量的標準在保證語義相等的情

2、況下，生成的目標指令的條數越少和執(zhí)行速度越快一種目標機器語言目標地址形式假設: C是常量, R是寄存器, d是偏移量, A是絕對地址(內存地址)表示方法: (R)代表R地址對應的內容;立即式: #C - C是值寄存器式: R - R本身就是一個地址;變址式: dR - d+(R) , R的內容加上偏移d得到的地址絕對式: A - A本身是一個地址值間接寄存器: *R - (R), R的內容對應的地址間接變址: *dR - (d+(R), R的內容加上偏移d后得到的地址的內容;從抽象地址到目標地址 (C語言)(0, off, dir)(0, off, indir)(1, off, dir)(1,

3、 off, indir)(-1, off, dir)(-1, off, indir)抽象地址形式offgp* offgp(off+InitOff)sp*(off+InitOff) sp(off+InitOff)sp*(off+InitOff) sp目標地址計算一種目標機器語言指令格式 (依賴于具體的目標機器),寄存器在最后(與教材不同)Op #C, R （立即-寄存器）含義是 C 與 (R)做op操作后,結果送到 R對應地址中;Op dR1, R2 （存儲器-寄存器）含義是 (R1)+d) 和(R2)做op操作后,結果送到 R2對應地址中;Op R1, R2 （寄存器-寄存器）含義是 (R1)

4、 和(R2)做op操作后,結果送到 R2對應地址中;Op &A, R ( 絕對地址 - 寄存器)含義是 (A) 和(R)做op操作后,結果送到 R對應地址中;一種目標機器語言基本指令集合 ：Load Source, R -從Source 讀出送入RStore Target, R -將R的內容送入TargetAdd Source, R -R+Source結果 送入RJmp(0/1), label - 跳轉到label對應的地址 IN R - 輸入值到ROUT R -輸出R的值LEA A, R - A的地址送給R從四元式生成目標代碼四元式種類運算型: (OP, A, B , T)賦值: (ASSI

5、G, A, size, B)跳轉和標號(JUMP, -,-, L)和(LABEL, -,-, L) (WHILE,-,-,-),(THEN,t,-,-),(ELSE,-,-,-),函數相關(ENTRY, Lf, size, level)(ENDFUNC, _, _,_)參數傳遞(VALACT/VARACT, X, offset, size)(CALL,Lf, true, t)(RETURN, -,-,t)運算型目標代碼生成(OP,A, B,T)的代碼生成算法要點(不考慮優(yōu)化)確定 A, B 和 T 的目標地址, 記為A.addr, B.addr和T.addr;找到一個可用的寄存器R, 生成如下

6、目標代碼Load A.addr, ROp* B.addr, RStore T.addr, R例子(ADDI, a, b, t), 其中 a:(0, 2, dir); b:(1, 2, indir), t: (-1, 5, dir)a的目標地址: 2gpb的目標地址: *(2+InitOff)spt的目標地址: (5+InitOff)spLoad 2gp, RAdd *(2+InitOff)sp, RStore (5+InitOff)sp, R(ASSIG, A, size, B )的代碼生成 size = 1算法要點：求A和B的地址。申請寄存器RA, 生成(Load A.addr, RA)指令

7、,生成指令(Store B.addr, RA);(ASSIG, t, 1, f), 其中 t:(-1, 5, dir); f:(1, 2, indir)t的目標地址: (5+InitOff)spf的目標地址: *(2+InitOff)spLoad (5+InitOff)sp, RStore *(2+InitOff)sp, RSize!=1,MOVEB A.addr, B.addr, n 標號和JUMP的代碼生成思想：遇到(LABEL,L)時，不生成代碼，保留（L,Pc）,Pc為當前代碼下一條指令；當遇到（JUMP, L）時，則生成對應的轉向指令（Jmp, Pc）關鍵問題：可能出現標號使用在前定

8、義在后，則需要構造轉向標號鏈，進行回填。中間代碼(JUMP, L)(JUMP, L)(JUMP,L)(LABEL,L)目標代碼Pc:標號地址表： P1:(Jmp , nil )(0, L, P1)Pi:(Jmp, P1 )(0, L, Pi)Pk:(Jmp, Pi )(0, L, Pk)(1, L, Pc)PcPcPc1 條件語句四元式的代碼生成條件語句特有的四元式：(THEN, t, -, -) - (Load t, R) (Jmp0 ar1, R),ar1入棧S(ELSE,-,-,-) - (Jmp ar2) , 回填給ar1, ar2入棧S(ENDIF,-,-,-) -回填ar2(有el

9、se分支) 或回填ar1(沒有else分支) if e then s1 else s2 endife.CodeThen, t, -,-S1.codeElse, -,-,-S2.codeEndif,-,-,- 循環(huán)語句的代碼生成While循環(huán)特有的四元式 (WHILE,-,-,-) - 標記循環(huán)結構的開始，對應(LABEL,-,-,startL), 不生成代碼，ar1入棧S (DO, t, -, -) - 是循環(huán)體的開始，判斷循環(huán)條件表達式是否成 立，不成立則發(fā)生跳轉， 生成(Load t, R) (Jmp0 ar2, R),ar2入棧S (ENDWHILE,-,-,-) - 標記循環(huán)體結束，轉

10、向循環(huán)開始，重新判斷循環(huán)條件是否成立 回填ar2, 生成(Jmp ar1)(WHILE, -, -,-)E.code(DO, t, -,-)S.code(ENDWHILE,-,-,-)過程/函數代碼生成(1)相關四元式：(VALACT , a, off, size ) , (VARACT , a, off, size ) (CALL, Lf, true/false, result ) (RETURN, -,-,t/-) (ENTRY, Lf, size, Level ) (ENDFUNC, -,-,-)(2) 過函調用時，需要加入一些目標代碼，用于完成如下工作： 申請新AR空間 參數傳遞 填寫

11、某些AR內容 轉向相應過程體 過程/函數返回時： 傳遞返回值 恢復寄存器的狀態(tài) 釋放AR 按照返回地址返回 (3)參數傳遞的代碼：sp:當前AR的首地址；top:棧頂指針： （VALACT, c, offset, 1） : c是常量值 (VALACT, a, offset, 1) : a是變量 參數傳遞的目標代碼生成 Load #c, RStore (offset+InitOff)top,RLoad a.addr, R Store (offset+InitOff)top, R將a.addr里面的值放入R (3)參數傳遞的代碼：sp:當前AR的首地址；top:棧頂指針： (VARACT, a,

12、offset ,1 ) 參數傳遞的目標代碼生成 a.addr RStore (offset+InitOff)top,RLEA a.addr, R（4）過程/函數調用 （CALL, Lf, true, result）* 保存寄存器當前內容LEA result.addr, R(Load R, Re_Valtop)(Load pc+2, Re_Atop) (JMP entry(f) )pc（5）過/函入口： （ENTRY, Lf , size, Level ）(Load, sp, DLtop ) -保留oldsp(Load, Level, Ltop ) -保留層數(C語言沒有必要)(Load, to

13、p, sp) -修改sp(ADD, size, top) -修改top （6）過/函出口： （ENDFUNC, -,-,-） 恢復寄存器內容 (Load sp, top）-top=sp (Load DLsp, sp ) -sp=CurrentAR.sp (Load Re_Atop,R) -按照返回地址返回 (JMP R) （7）返回語句： （RETURN, -,-,result）Load result.addr, R1Store Re_Valsp, R1 若沒有返回值： （RETURN, -,-,-）,則不生成代碼例子 #define n 2 int sum = 0; int fac(int

14、i) if (i=0) return 1; if (i0) return -1; return (i*fac(i-1); void main () sum = fac(n); (ENTRY, L1, 6 , 0)(EQ, i, 0, t2)(THEN, t2,_, _)(RETURN, _, _, 1)(ENDIF, - ,-, -)(ASSIG, 0, 1, sum)(LT, i, 0, t3)(THEN, t3,_, _)(RETURN, _, _, -1)(ENDIF, _, _, _) (-, i, 1, t4)(VALACT, t4,0, 1)(CALL, fac, true, t5

15、)(*, i, t5, t6)(RETURN, _, _, t6)(ENDFUNC, _, _ , _)(ENTRY, L4, 1 , 0)(VALACT,n,0, 1)(CALL, fac, true, t1)(ASSIG, t1, 1, sum)(ENDFUNC, _, _ , _)目標代碼生成四個寄存器sp :保存當前AR的首地址;top:保存當前棧頂地址;gp:保存靜態(tài)區(qū)的首地址;pc: 指令計數器; 過程活動記錄動態(tài)鏈地址返回地址返回值臨時變量形參局部變量空間大小spoffsetInitOff= 4P1: Load #0, RP2: Store 1gp, RP3: JmpP4:Loa

16、d sp, 0topP5:Load top, spP6:ADD #10, top (ENTRY, L1, 6 , 0)(EQ, i, 0, t2)(THEN, t2,_, _)(RETURN, _, _, 1)(ENDIF, _, _, _)(ASSIG, 0, 1, sum)保存動態(tài)鏈地址修改sp修改topP7: Load #0, RP8: EQ 4sp, RP9: Store 5sp, R P10: Load 5sp, RP11: Jmp0 P12: Load #1, RP13: Store *2sp, R P14P37P17: Load 6sp, RP18: Jmp0 (THEN, t3

17、,_, _)(RETURN, _, _, -1)(LT, i, 0, t3)P21P14: Load #0, RP15: LT 4sp, RP16: Store 6sp, R (ENDIF, _, _, _)P19: Load #-1, R P20: Store *2sp, R (-, i, 1, t4)(VALACT, t4,0, 1)(CALL, fac, true, t5)(*, i, t5, t6)(RETURN, _, _, t6)(ENDFUNC, _, _ , _)P21: Load 4sp, RP22: Sub #1 , RP23: Store 7sp, R P24: Load

18、 7sp, RP25: Store 4top, RP26: LEA 8sp, RP27: Load R, 2top)P26: Load pc+2, 1top P27: Jmp P4 P28: Load 4sp, RP29: Mul 8sp, RP30: Store 9sp, RP31: Load 9sp, RP32: Store *2sp, RP33:Load sp, topP34:Load 0sp, spP35:Load 1top,RP36:Jmp R修改top指針修改sp指針按照返回地址返回 (ENTRY, L4, 2 , 1)(VALACT,n,0, 1)(CALL, fac, true

19、, t1)(ASSIGN, t1, 1, sum)(ENDFUNC, _, _ , _)P37:Load sp, 0topP38:Load top, spP39:ADD #6, top保存動態(tài)鏈地址修改sp修改topP40: Load 0gp, RP41: Store 4top, RP42: LEA 5sp, RP43: Load R, 2topP44: Load pc+2, 1top P45: Jmp P4 P46: Load 5sp, RP47: Store 1gp, RP48:Load sp, topP49:Load 0sp, spP50:將返回地址存入寄存器P51:按照返回地址跳轉存在

20、問題出現這樣的代碼: Store a, R Load a, R原因: 沒有考慮當前變量是否已經在某個寄存 器中; 沒有考慮優(yōu)化!寄存器分配寄存器分配應遵循的原則：寄存器優(yōu)先原則：即變量的值盡可能的存放在寄存器中寄存器活躍原則：即變量的值至少有下一次的引用時才分配寄存器寄存器多載原則：即一個寄存器中可能存放多個變量的值。典型的例子是通過賦值操作的結果。源變量和被賦值的變量共用一個寄存器RegisterAlloc() ：完成寄存器分配工作，成功返回可用的寄存器;運算型目標代碼生成(ADDI, A, B, t)的代碼生成算法要點(考慮優(yōu)化)（1）求A,B的目標地址;（2）若A值不在寄存器，則申請寄存

21、器RA, 并生成(Load A.addr, RA )指令。 （3）若B在本條之后不活躍(不再使用)， 則產生指令(Add B.addr,RA), 否則產生 (Load B.addr,RB),(Add RB,RA).（4）令t駐留于RA(即不用將t存回內存)，RA的值就是t的值. ( ADDI, A, B, t ) B不在寄存器 且不活躍 B不在寄存器 且活躍 B在寄存器RB A不在寄存器 Load B, RB Add A, RB Load A, RA Load B, RB Add RB, RA Load A, RA Add RB, RA A在寄存器RA Add B, RA Load B, RB Add RB, RA Add RB, RA(+,A,B,T)代碼的幾種形式(ASSIG, A, n, B)）的代碼生成 注：當B為間接變量時，不是把A的值送入B的單元，而是送到B單元內