编译程序原理与实现：第10章 目标代码生成

1、词法分析语法分析语义分析中间代码优化中间代码生成目标代码生成分析合成第十章 目标代码生成目标代码生成概述目标语言四元式到目标指令的翻译*寄存器分配*临时变量地址分配目标代码生成概述目标代码生成器主要任务: 将中间代码转换成等价的目标机指令(包括计算指令和管理AR的指令等)，同时完成变量的地址分配,寄存器分配。输入：中间代码/TokenList/AST+符号表输出（多种形式可选）：绝对机器代码：执行速度快，缺乏灵活性可重定位机器代码：可分模块编译，需连接和装入汇编代码：生成的汇编代码还要经过汇编程序汇编才可运行虚拟机的代码：增加可移植性，需要虚拟机的解释器衡量目标代码质量的标准在保证语义相等的情

2、况下，生成的目标指令的条数越少和执行速度越快一种目标机器语言目标地址形式假设: 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)的代码生成算法要点(不考虑优化)确定 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,-,-,- 循环语句的代码生成While循环特有的四元式 (WHILE,-,-,-) - 标记循环结构的开始，对应(LABEL,-,-,startL), 不生成代码，ar1入栈S (DO, t, -, -) - 是循环体的开始，判断循环条件表达式是否成 立，不成立则发生跳转， 生成(Load t, R) (Jmp0 ar2, R),ar2入栈S (ENDWHILE,-,-,-) - 标记循环体结束，转

10、向循环开始，重新判断循环条件是否成立 回填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内容 转向相应过程体 过程/函数返回时： 传递返回值 恢复寄存器的状态 释放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:保存静态区的首地址;pc: 指令计数器; 过程活动记录动态链地址返回地址返回值临时变量形参局部变量空间大小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)保存动态链地址修改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保存动态链地址修改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原因: 没有考虑当前变量是否已经在某个寄存 器中; 没有考虑优化!寄存器分配寄存器分配应遵循的原则：寄存器优先原则：即变量的值尽可能的存放在寄存器中寄存器活跃原则：即变量的值至少有下一次的引用时才分配寄存器寄存器多载原则：即一个寄存器中可能存放多个变量的值。典型的例子是通过赋值操作的结果。源变量和被赋值的变量共用一个寄存器RegisterAlloc() ：完成寄存器分配工作，成功返回可用的寄存器;运算型目标代码生成(ADDI, A, B, t)的代码生成算法要点(考虑优化)（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单元内