编译原理课程笔记 - Chapter 4 目标代码生成

#目标代码生成

#任务

中间代码 --> 代码生成器 --> 目标程序
                ^
                |
              符号表

#目标代码的三种形式

1. 能立即执行的机器码(所有地址已经定位)
2. 待装配的机器语言模块(连接装入后即可执行)
3. 汇编语言代码(经汇编程序汇编后即可执行)

此处选择汇编语言

#目标机器模型

此处假设目标计算机:

1. 具有多个通用寄存器, 可以用来运算, 也可以用来取地址
2. 支持四种指令形式
   1. 直接地址型 OP R, M - R OP M => R
   2. 寄存器型 OP Ri, Rj - Ri OP Rj => Ri
   3. 变址型 OP Ri, c(Rj) - Ri OP (Rj+c) => Ri
   4. 间接型
      1. OP Ri, (M) - R OP (M) => R
      2. OP Ri, (Rj) - Ri OP (Rj) => Ri
      3. OP Ri, (c(Rj)) - Ri OP ((Rj+c)) => Ri

OP 可以是 ADD,SUB,MUL,DIV 等

#简单代码生成器

思路: 代码生成器在生成每一条指令时, 必须要知道每个寄存器中存储的是什么, 以及每个变量存储到什么位置

方法:

1. 引入待用信息
2. 寄存器描述数组
3. 变量地址描述数组

#待用信息

待用信息

• 在基本块中, 四元式 i 对 A 定值, 四元式 j 对 A 取值, 且 i,j 之间无再对 A 定值, 则称 j 是 i 的变量 A 的待用信息

活跃信息

• 基本块中的一个名字在某个给定点之后仍被引用, 则称该名字在给定点是活跃的

修改符号表

• 记录待用信息和活跃信息
• 表示: (待用信息[i/^],活跃信息[y/^])

变量名	待用/活跃信息栏
A	(…, …)
B	(…, …)
…	(…, …)

计算待用和活跃信息

1. 开始时, 所有变量均为非待用, 根据基本块之后是否活跃填写活跃或非活跃
2. 逆序遍历每个四元式i
   1. 把A的引用信息附加到四元式i左值上
   2. A的引用信息附加(^,^)
   3. 把B,C的引用信息附加到四元式i上
   4. B,C的引用信息附加(^,^)

例:

T1:=B-C
T2:=A*T1
T3:=D+1
T4:=E-F
T5:=T3*T4
W:=T2/T5

序号	四元式	左值	左操作数	右操作数
(6)	W:=T2/T5	(^,y)	(,)	(,)
(5)	T5:=T3*T4	(6,y)	(,)	(,)
(4)	T4:=E-F	(3,y)	(,)	(,)
(3)	T3:=D+1	(3,y)	(,)	(,)
(2)	T2:=A*T1	(6,y)	(,)	(,)
(1)	T1:=B-C	(2,y)	(,)	(,)

变量名	待用/活跃信息栏
T5	(,)->(6,y)->(,)
T4	(,)->(3,y)->(,)
T3	(,)->(3,y)->(,)
T2	(,)->(6,y)->(,)
T1	(,)->(2,y)->(,)
W	(,y)->(,^)
F	(,)->(4,y)
E	(,)->(4,y)
D	(,)->(3,y)
C	(,)->(1,y)
B	(,)->(1,y)
A	(,)->(2,y)

#寄存器分配算法

寄存器描述和地址描述

• 寄存器描述数组RVALUE
  • 记录寄存器内存储的变量, 可以是多个
  • RVALUE[R1]={A,B}
• 变量地址描述数组AVALUE
  • 记录变量存储的位置(寄存器/内存)
  • AVALUE[A]={R1,R2,A}

代码生成算法

• 对于四元式A:=B op C, 依次执行

1. 调用GETREG(i: A:=B op C)获取一个寄存器R
2. 查询AVALUE[B]和AVALUE[C], 如果在寄存器中, 假设是B'和C'
3. 如果B'≠R, 先把B加载到R中, 生成代码: LD R,B'
4. 进行运算, 生成代码: op R,C'
5. 更新描述信息
   1. 如果B'或C'是R, 就要把AVALUE中的记录删除
   2. 设置AVALUE[A]={R}, RVALUE[R]={A}
6. 如果B或C仍存储在某个寄存器中, 但后续不再被引用且不再活跃, 就从AVALUE和RVALUE中删除B和C的记录

寄存器分配原则

• 尽可能用 B 独占的寄存器
• 尽可能用空闲的寄存器
• 抢占用非空闲寄存器
  • Ri的值也存储在内存中
  • Ri最远才会用到

寄存器分配算法GETREG(i: A:=B op C)

1. 如果 B 独占某个寄存器

   • 如果AB是同一个标识符(即修改 B 的指令B:=B op C)
     • 返回B所在的寄存器
   • 如果B在后面不会再引用(非待用, 非活跃)
     • 返回B所在的寄存器

2. 如果有空闲寄存器, 返回空闲寄存器

3. 抢占一个寄存器Ri,

   • 对于Ri中存储的每一个变量M, 如果存储的不是A, 或者存储的是A == C != B且Ri中不存储B.(M==A && M==C && M!=B && B not in RVALUE[Ri])
     1. 如果M仅存储在Ri, 则要存到内存中: ST Ri, M
     2. 如果M == B, 或者M == C && B in RVALUE[Ri]中, 则令AVALUE[M]={M,R}, 否则令AVALUE[M]={M}
     3. 删除M在Ri中的记录, RVALUE[Ri].reLD e(M)
     4. 返回R

例:

寄存器: R0，R1；基本块出口活跃变量: W

T1:=B-C
T2:=A*T1
T3:=D+1
T4:=E-F
T5:=T3*T4
W:=T2/T5

答案:

【解答】该基本块的目标代码如下(指令后面为相应的注释)：
LD  R0, B  /* 取第一个空闲寄存器 R0 */
SUB R0, C  /* 运算结束后R0中为T1结果，内存中无该结果 */
LD  R1, A  /* 取一个空闲寄存器R1 */
MUL R1, R0 /* 运算结束后R1中为T2结果，内存中无该结果 */
LD  R0,D  /* 此时R0中结果T1已经没有引用点，且临时单元T1是非活跃的，所以，寄存器R0可作为空闲寄存器使用 */
ADD R0, 1 /* 运算结束后R0中为T3结果，内存中无该结果 */
ST  R1, T2  /*翻译四元式T4=E-F时，所有寄存器已经分配完毕，寄存器R0中存的T3和寄存器R1中存的T2都是有用的。由于T2的下一个引用点较T3的下一个引用点更远，所以暂时可将寄存器R1中的结果存回到内存的变量T2中，从而将寄存器R1空闲以备使用*/
LD  R1, E
SUB R1, F  /*运算结束后R1中为T4结果，内存中无该结果*/
MUL R0, R1 /*运算结束后R0中为T5结果，内存中无该结果。注意，该指令将寄存器R0中原来的结果T3冲掉了。可以这么做的原因是，T3在该指令后不再有引用点，且是非活跃变量*/
LD  R1, T2 /*此时R1中结果T4已经没有引用点，且临时单元T4是非活跃的，因此寄存器R1可作为空闲寄存器使用*/
DIV R1, R0
/*运算结束后R1中为W结果，内存中无该结果。此时所有指令部分已经翻译完毕*/
ST  R1, W
/*指令翻译完毕时，寄存器中存有最新的计算结果，必须将它们存回到内存相应的单元中去，否则，在翻译下一个基本块时，所有的寄存器被当成空闲的寄存器使用，从而造成计算结果的丢失。考虑到寄存器R0中的T5和寄存器R1中的W，临时单元T5是非活跃的，因此只要将结果W存回对应单元即可*/