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

发表于 分类于 ， 阅读次数： 本文字数： 1.8k 阅读时长 ≈ 6 分钟

#目标代码生成

#任务

1
2
3
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的引用信息附加(^,^)

例:

1
2
3
4
5
6
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

1
2
3
4
5
6
T1:=B-C
T2:=A*T1
T3:=D+1
T4:=E-F
T5:=T3*T4
W:=T2/T5

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
【解答】该基本块的目标代码如下(指令后面为相应的注释)：
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存回对应单元即可*/