第8章 代码生成

代码生成将中间表示（IR）转换为目标机器代码，是编译器的后端核心阶段。

8.1 中间代码和用于代码生成的数据结构

常见中间代码形式

形式 特点 示例
三地址码 每指令最多三个地址 t = a + b
三元式 地址为指令序号 (+, a, b) → (1)
四元式 显式结果地址 (+, a, b, t)
P-代码 栈式虚拟机指令 lod, str, add
抽象语法树 树形结构 直接遍历生成代码

三地址码示例

原表达式：a[index] = 4 + 2

三地址码：
t1 = 4 + 2
t2 = index * 2      （假设字节编址）
t3 = a + t2
*t3 = t1

优化后：
t1 = index * 2
a[t1] = 6

P-代码示例

lod  I, 0, 0     ; 将局部变量压栈
ldc  I, 6         ; 将常量 6 压栈
sto  I, 0, 0     ; 出栈并存储

8.2 基本代码生成技术

将代码视为合成属性

  • 代码可视为字符串形式的综合属性
  • 通过在语法树上进行后序遍历逐步生成

寄存器分配

  • 方法一：将所有临时变量存在内存，需要时加载。简单但低效
  • 方法二：将活跃值尽量保留在寄存器中，高效但复杂
  • 寄存器溢出（spill）：当寄存器不足时，将值临时存回内存

临时变量管理

  • 栈式临时变量分配：每次需要临时变量时 push，使用后 pop
  • 基于寄存器的临时变量：尽可能用寄存器代替内存

8.3 数据结构引用的代码生成

数组元素地址计算

行主序（Row-major）—— C 风格

A[i][j] 的地址 = 基址 + (i × 列数 + j) × 元素大小

列主序（Column-major）—— FORTRAN 风格

A[i][j] 的地址 = 基址 + (j × 行数 + i) × 元素大小

记录/结构体字段访问

  • 每个字段的相对偏移在编译时已知
  • 访问形式：base + field_offset
  • 嵌套结构：逐层偏移叠加

8.4 控制语句和逻辑表达式的代码生成

if-else 语句

if (x > 0)
    then_part
else
    else_part

↓ 生成代码

    CMP x, 0
    JLE else_label
    then_part 的代码
    JMP end_label
else_label:
    else_part 的代码
end_label:

while 循环

while (x > 0)
    body

↓ 生成代码

loop_label:
    CMP x, 0
    JLE end_label
    body 的代码
    JMP loop_label
end_label:

repeat-until 循环

repeat body until (x > 0)

↓ 生成代码

loop_label:
    body 的代码
    CMP x, 0
    JGT loop_label

短循环布尔求值

  • 对于 if (a > 0 && b < 10)：如果 a > 0 为假，跳过 b < 10 的求值
  • 通过控制流（条件跳转）而非算术求值实现

8.5 过程和函数调用的代码生成

函数入口和出口

函数定义：
    entry_label:  ; 入口标号
    保存活动记录
    执行函数体
    返回值处理
    恢复活动记录
    return         ; 返回指令

调用序列代码

调用点：
    计算并传递参数
    保存返回地址
    跳转到入口标号

接受返回值：
    从指定位置获取返回值

8.6 商用编译器案例研究

  • Borland C++（80x86）：使用寄存器窗口、复杂指令选择
  • Sun SPARC 编译器：使用寄存器窗口、延迟槽（delay slot）
  • GCC 编译器：RTL（Register Transfer Language）作为中间表示

8.7 TM 机（Tiny Machine）

基本结构

  • 8 个通用寄存器（R0~R7）
  • R6 = 帧指针（FP），R7 = 程序计数器（PC）
  • 只读指令存储 + 数据存储

常用指令集

指令 格式 作用
LDC LDC r, c(r0) 装入常量：r = c
LD LD r, c(r1) 从内存装入：r = M[r1 + c]
LDA LDA r, c(r1) 装入地址：r = r1 + c
ST ST r, c(r1) 存储：M[r1 + c] = r
ADD ADD r1, r2, r3 r1 = r2 + r3
SUB SUB r1, r2, r3 r1 = r2 - r3
MUL MUL r1, r2, r3 r1 = r2 * r3
JEQ JEQ r1, c(r2) 若 r1 == 0 则跳转
JLT JLT r1, c(r2) 若 r1 < 0 则跳转
JMP JMP c(r2) 无条件跳转
HALT HALT 停机
IN IN r, c(r1) 输入
OUT OUT r, c(r1) 输出

8.8 TINY 语言的代码生成器

  • 文件结构：code.h / code.c（代码生成实用程序）+ cgen.h / cgen.c（主代码生成）
  • 遍历语法树，为每个节点生成 TM 指令
  • 使用 emitComment()、emitRO()、emitRM() 等实用函数

8.9 代码优化技术

优化分类

优化类型 说明 示例
常量合并 编译时计算常量表达式 4 + 2 → 6
常量传播 常量变量替换为值 x = 4; y = x + 2 → y = 6
死代码消除 删除不可达代码 return 1; x = 2; → 删除 x = 2
公共子表达式消除 避免重复计算 a + b 多次出现 → 计算一次复用
循环不变式外提 将循环内不变计算移出循环 for(i) { x = a*b; ... } → 计算一次
寄存器分配 常用值保持在寄存器 图着色算法
窥孔优化 相邻几条指令的局部改进 JMP L1; L1: → 删除

基本块和流图

  • 基本块（Basic Block）：单入口单出口的连续指令序列
  • 流图（Flow Graph）：以基本块为节点的控制流图
  • DAG（有向无环图）：用于基本块内的优化，识别公共子表达式

8.10 TINY 代码生成器的简单优化

两个主要低效来源

  1. 寄存器使用不充分：从不使用 R2、R3、R4
  2. 布尔值的不必要计算：测试生成 0/1 后再判断

优化方法

  1. 寄存器存放临时变量：用寄存器替代内存中的临时变量位置
  2. 无值跳转：直接在控制流中判断条件，不生成布尔常量
  3. 寄存器保存变量：将 TM 寄存器用于变量存储（需引用计数分析）

考试重点

★★★ 第一梯队

考点 典型题型
数组地址计算 行主序公式的应用
TM 指令序列 将表达式/赋值翻译为 TM 指令

★★☆ 第二梯队

考点 典型题型
控制语句的代码生成 if-else、while 的标号跳转逻辑
中间代码形式 三地址码/P-代码的转换
常量合并和常量传播 优化题

★☆☆ 第三梯队

考点 典型题型
基本块划分 优化基础
中间表示的作用 分离前端和后端
代码生成中各个击破的策略 概念