9 代码生成

约 1160 个字预计阅读时间 4 分钟

代码生成器主要完成了以下任务： - 指令选择

选择合适的 *目标机指令* 实现中间代码

寄存器分配与指派

value 应该放置在哪个 reg 中
指令排序

按照什么顺序执行指令可以提高效率

1 简单目标机模型

三地址机器模型
- 操作：加载、保存、运算、跳转 ...
- 内存按 Byte 寻址
- 具有 n 个通用寄存器 \(R_0,...,R_{n-1}\)
- 假设所有运算分量均为整数
- 指令之间可能存在标号

1.1 主要指令

加载指令 \(LD\ dst,\ addr\)
- \(LD\ r,\ x\) 将 addr = x 处的内容复制至 r
- \(LD\ r_1,\ r_2\) 将寄存器 r2 的内容复制至 r1
保存指令 \(SD\ x,\ r\)
运算指令 \(OP\ dst,\ src1,\ src2\)
无条件跳转 \(BR\ L\)，\(L\) 为指令标号
条件跳转 \(Bcond\ r,\ L\)，\(r\) 为寄存器

1.2 寻址模式

变量名 \(a\)
\(a(r)\)，\(a\) 为变量，\(r\) 为寄存器，表示 \(a+contents(r)\)
\(c(r)\)，\(c\) 为整数，\(r\) 为寄存器，表示 \(c+contents(r)\)
\(*r\) 表示寄存器中存放的是一个地址，即为 \(contents(contents(r))\)
\(*c(r)\) 表示 \(c+contents(r)\) 存放的是地址，即为 \(contents(c+contents(r))\)
\(\#c\) 给寄存器赋常数 => \(LD\ R_1,\ \#100 \rightarrow R_1=100\)

2 指令选择

2.1 运算语句

三地址语句 \(x=y-z\)，对应如下框架：

LD r1, y;       // 已经在寄存器中就可以删去
LD r2, z;
SUB r1, r1, r2; // r1 = r1 - r2 = y - z
ST x, r1;       // x = r1 = y - z（不需要存到内存就可以删去）

2.2 数组寻址语句

对于 \(b=a[i]\)，且每个属于元素占 8 Byte：

LD r1, i;
MUL r1, r1, 8; // r1 = 8 * i = offset
LD r2, a(r1);  // r2 = contents(a + offset) = a[i]
ST b, r2;      // b = r2 = a[i]

2.3 指针存取语句

对于 \(x=*p\)：

LD r1, p;
LD r2, 0(r1); // r2 = contents(0 + p)
ST x, r2;     // x = contents(0+p) = *p

对于\(*p=y\)：

LD r1, p;
LD r2, y;
ST 0(r1), r2;

2.4 条件跳转语句

对于 \(if\ x<y\ goto\ L\)：

LD r1, x;
LD r2, y;
SUB r1, r1, r2; // r1 = x - y
BLTZ r1, M;     // if r1<0 jump to M

2.5 过程调用与返回

静态存储分配

对于代码 \(call\ calleeFunc\)：

ST callee.staticArea, #here + 20; // 存放返回地址
// staticArea 即为 callee 活动记录起始位置（假装这里存了返回地址）
// #here + 20 指向 cur+2 处的指令

BR callee.codeArea; // 跳转至 callee 的代码区准备执行

对于 \(return\)，有 BR *callee.staticArea

栈式存储分配

对于调用语句

ADD sp, sp, #caller.recordSize; // 让 sp 指向 callee
ST 0(sp), #here + 16;           // 储存返回地址
BR callee.codeArea;

对于返回语句

callee:
    BR *0(sp); // 返回
caller:
    SUB sp, sp, #caller.recordSize; // 把 sp 挪回自己

3 寄存器选择

对于每个形如 \(I:x=y\ op\ z\) 的三地址指令： 1. 调用 getReg(I) 为 \(x,\ y,\ z\) 选择寄存器 2. 对于依赖：若 \(R_y\) 中存放的不是 \(y\)，生成 \(LD\ R_y,\ y'\)，\(y'\) 为任意存放 \(y\) 的内存地址 3. 生成目标指令 \(OP\ R_x,\ R_y,\ R_z\)

3.1 寄存器描述符与地址描述符

寄存器描述赋 Register Description

寄存器当前存放的是哪个变量的值
地址描述符 Address Description

运行时 每个 id 的当前值存放在哪个/哪些位置

可以是寄存器 / 栈单元 / 内存地址

可以放在符号表的对应 record 中
基本块结束处理

对于可能在出口处活跃的变量 \(x\)，若还没有被保存到内存中，则生成 \(ST\ x,\ R\)

其中 \(R\) 为当前保存 \(x\) 值的寄存器
描述符的更新
1. 对于 \(LD,\ R,\ x\)
  - 修改寄存器 \(R\) 的描述符 => 仅包含 \(x\)
  - 修改 \(x\) 的地址描述符 => 添加 \(R\)
  - 从任何 \(!x\) 的地址描述符中删除 \(R\)
2. 对于 \(OP\ R_x,\ R_y,\ R_z\)
  - 修改寄存器 \(R\) 的描述符 => 仅包含 \(x\)
  - 从任何 \(!R_x\) 的寄存器描述符中删除 \(x\)
  - 修改 \(x\) 的地址描述符 => 仅包含 \(R_x\)
  - 从任何 \(!x\) 的地址描述符中删除 \(R_x\)
3. 对于 \(ST\ x,\ R\)
  - 修改 \(x\) 的地址描述符 => 包含当前的内存地址
4. 对于复制语句 \(x=y\) ，若需要加载 \(y\)（\(LD\ R_y,\ y'\))：
  - 修改 \(R_y\) => 仅包含 \(y\)
  - 修改 \(y\) => 添加 \(R_y\)
  - 从任何 \(!y\) 中删除 \(R_y\)

3.2 getReg 函数设计

判断 \(y\) 是否存在于某个寄存器 \(R\) 中
- T：选择 \(R\)，结束
- F：Step 2
判断当前是否存在空闲寄存器
- T：选择空闲寄存器，结束
- F：Step 3
计算每个候选寄存器需要生成保存指令的数量，选择最少的，结束

3.3 寄存器费用计算

![[截屏2023-04-22 21.38.32.png]]

3.4 \(R_x\) 的选择

由于 \(x\) 的 newVal 正在被计算，因此 只存放了\(x\) 的寄存器时可以接受的（即使 \(R_x==R_y || R_x == R_z\)）
若 \(y\) 在该计算完成后 不再被使用，且 \(R_y\) 中仅保存了 \(y\) 的值，则可以选择 \(R_y\) 进行覆盖

4 窥孔优化

窥孔 peepHole 是程序上的一个滑动窗口
「窥孔优化」是指检查目标指令的窥孔，如果有可能就在窥孔内使用更快/更短的指令来替换窥孔中的部分指令序列

可以在中间代码生成后立刻进行窥孔优化

4.1 冗余指令删除

消除冗余的加载/保存指令

LD r0, b;
ADD r0, r0, c;
ST a, r0;
LD r0, a;  // => 在存储后马上读，没有标号就可以删除（否则可能存在跳转）
ADD r0, r0, e;
ST d, r0;

消除 不可达代码

紧跟在 无条件跳转 指令后的、不带标号 的指令是不可达的

    if debug == 1 goto L1
    goto L2 // 无条件跳转
L1: print debugging information
L2:

// 可以等价变换为如下形式
    if debug != 1 goto L2
    print debugging information
L2:

// 若在开头执行 debug = 0，则条件编程 0!=1 恒为 true，无条件跳转
    if 0!=1 goto L2;
    goto L2;

// 等价于
    goto L2;
    print debugging information; // 冗余
L2:

4.2 控制流优化

若出现 跳转至跳转指令 的指令，我们可以进行合并：

    if a < b goto L1;
L1: goto L2;

// 可以修改为
    if a < b goto L2;
L1: goto L2; // 如果没有别人跳到 L1，那么这行可以删除

4.3 代数优化

代数恒等式

=> 去掉 x = x + 0，x = x * 1 的弱智操作
强度削弱
- 用左右移位替代 *2 or /2
- 除数为 const 的浮点数除法可以用 \(*\frac{1}{const}\) 求近似值
使用特殊指令

用 INC 替代 +1 操作