Appearance
目标代码生成
概念
目标代码生成是把优化完的中间代码落成机器能执行的东西。
它要做三件事，缺一不可：
| 事情 | 回答的问题 | 名字 |
|---|---|---|
| 指令选择 | 这段 IR 用哪几条机器指令实现 | instruction selection |
| 寄存器分配 | 每个值放在哪个寄存器里 | register allocation |
| 指令调度 | 这些指令按什么顺序排 | instruction scheduling |
为什么是三件事而不是一件：三者互相牵制——选了指令才知道需要几个寄存器，寄存器不够就得改指令序列，改了顺序又可能影响流水线。所以真实的编译器反复迭代这三步，而不是一次做完。
产物按"走多远"分三种：
| 产物 | 谁生成 | 例子 |
|---|---|---|
| 汇编文本 | 编译器后端 | add.s |
| 可重定位目标文件 | 汇编器 | add.o（ELF，ET_REL） |
| 内存中的机器码 | 链接器 + 装载器 | 进程里的 .text |
这三种形态与 lang/20-steps.md、lang/21-elf.md、lang/24-image.md 讲的三级产物一一对应。
原理
一、指令选择
同一段 IR 可以有好几种机器指令实现，选哪种决定了快慢：
| IR | 方案 A | 方案 B |
|---|---|---|
t = x * 4 | mul $t, $x, 4 | sll $t, $x, 2 |
t = x + 1 | addu $t, $x, 1 | addiu $t, $x, 1 |
两种主流做法：
- 树覆盖（tree covering）：把 IR 表达成树，用指令的"模式"去覆盖树，追求覆盖后总代价最小——可以用动态规划求出最优解。
- 宏展开：为每种 IR 指令写一小段固定模板，一一替换。实现简单，但生成的代码不是最优。
二、寄存器分配
寄存器是最稀缺的资源（MIPS32 只有 32 个，除去专用寄存器后能自由用的更少），而值可能有几百个。所以必须把"值"映射到"寄存器"。
先要知道哪些值在同一时刻同时活着——这就是活跃变量分析（上一章讲过，它是后向分析），把每个值的活跃区间画出来。
两种分配算法：
| 算法 | 思路 | 特点 |
|---|---|---|
| 图着色 | 同时活的两个值连一条边，给图着色；颜色 = 寄存器 | 质量好，NP 完全，工程上用启发式近似 |
| 线性扫描 | 按活跃区间的起点排序，顺序分配，冲突就溢出 | 快，质量略差，被 JIT 广泛采用 |
寄存器不够时怎么办：把某个值溢出（spill）到栈上——用的时候 lw 取回来，不用了 sw 写回去。每一次溢出，都换来两次访存。
表达式树的形状会改变寄存器需求，这可以用 Sethi-Ullman 标号算出来：
一棵结点 t：
t 是叶子 -> label(t) = 1
两棵子树标号相等 -> label(t) = 该标号 + 1 （两个结果要同时留住）
两棵子树标号不等 -> label(t) = 较大的那个 （先算大的，小的挤剩下的寄存器）规则的含义：如果左右子树一样"难"，就必须同时留住两个中间结果，寄存器需求加一；如果一边更难，就先算难的那边，算完后寄存器被释放，另一边可以复用。
三、指令调度
排指令顺序的目的是填满流水线的空档。MIPS 的两个经典现象：
| 现象 | 原因 | 调度对策 |
|---|---|---|
| load 延迟 | lw 的数据要一拍后才可用 | 把与它无关的指令插到中间 |
| 分支延迟槽 | 分支指令后一拍仍会执行下一条 | 把一条本来就要执行的指令搬进延迟槽 |
MIPS 的分支延迟槽是架构层面的约定：beq 后面的那条指令无论跳不跳都会执行。所以调度器要挑一条"两条路都会做、且不破坏依赖"的指令塞进去；如果找不到，就填一条 nop。
四、窥孔优化
生成完代码之后，再拿一个小窗口（比如连续 3 条指令）滑动一遍，专门消掉这种"翻译腔"：
| 模式 | 优化成 |
|---|---|
sw $t, 0($sp) 紧跟 lw $t, 0($sp) | 删掉 lw（刚存过又读回来） |
addu $t, $t, 0 | 删掉 |
j L 紧跟 L: | 删掉 j |
窥孔优化的性价比极高：规则写起来就几行，却能显著提升代码质量——它是"局部模式匹配"的最小版本。
示例
例 1：算出一棵树需要几个寄存器（C）
#include <stdio.h>
/* 表达式树 ((a + b) * (c - d)) + e
结点 0 是根；L[n] = -1 表示叶子 */
static const char *OP[9] = {"+", "*", "+", "", "", "-", "", "", ""};
static const char *LEAF[9] = {"", "", "", "a", "b", "", "c", "d", "e"};
static int L[9] = {1, 2, 3, -1, -1, 6, -1, -1, -1};
static int R[9] = {8, 5, 4, -1, -1, 7, -1, -1, -1};
static int lab[9];
static int label(int n) {
if (L[n] < 0) return 1; /* 叶子 */
int a = label(L[n]), b = label(R[n]);
return (a == b) ? a + 1 : (a > b ? a : b); /* 相等则 +1，否则取大 */
}
static void tree_str(int n, char *out) { /* 把子树打印成一行 */
if (L[n] < 0) { sprintf(out, "%s", LEAF[n]); return; }
char l[40], r[40];
tree_str(L[n], l);
tree_str(R[n], r);
sprintf(out, "(%s %s %s)", l, OP[n], r);
}
int main(void) {
for (int n = 0; n < 9; n++) lab[n] = label(n);
printf("=== ((a+b)*(c-d))+e 的 Sethi-Ullman 标号 ===\n");
printf(" 结点 子树 标号\n");
int order[9] = {3, 4, 2, 6, 7, 5, 1, 8, 0}; /* 由叶到根 */
for (int k = 0; k < 9; k++) {
int n = order[k];
char s[40];
tree_str(n, s);
printf(" %-4d %-18s %d\n", n, s, lab[n]);
}
int leaves = 0, inner = 0;
for (int n = 0; n < 9; n++) (L[n] < 0 ? leaves : inner)++;
printf("=== 代码量估算 ===\n");
printf(" 叶子 %d 个 -> %d 条 lw\n", leaves, leaves);
printf(" 内部结点 %d 个 -> %d 条运算\n", inner, inner);
printf(" 合计 %d 条指令；峰值同时需要 %d 个寄存器\n", leaves + inner, lab[0]);
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
预期输出：
=== ((a+b)*(c-d))+e 的 Sethi-Ullman 标号 ===
结点 子树 标号
3 a 1
4 b 1
2 (a + b) 2
6 c 1
7 d 1
5 (c - d) 2
1 ((a + b) * (c - d)) 3
8 e 1
0 (((a + b) * (c - d)) + e) 3
=== 代码量估算 ===
叶子 5 个 -> 5 条 lw
内部结点 4 个 -> 4 条运算
合计 9 条指令；峰值同时需要 3 个寄存器按这个结论生成的 MIPS32 汇编（目标就是 lang/* 系列用的那套指令集）：
asm
lw $t0, a
lw $t1, b
addu $t0, $t0, $t1 # $t0 = a + b
lw $t1, c
lw $t2, d
subu $t1, $t1, $t2 # $t1 = c - d
mul $t0, $t0, $t1 # $t0 = (a + b) * (c - d)
lw $t1, e
addu $t0, $t0, $t1 # $t0 = ...... + e三条说明：
- 9 条指令、5 次访存，与上表的估算一致；
$t0 / $t1 / $t2三个寄存器就够了，一点不用溢出。 mul是伪指令：MIPS32 真正的乘法是mult+mflo，汇编器会展开成两条。"写出来是 1 条、跑起来是 2 条"是汇编层常见的错觉。addu而不是add：本例只做地址与数值加减，不需要溢出陷阱；add会在溢出时抛异常（见lang/03-arith.md）。
例 2：寄存器不够时会多花多少（Python 对照）
def pad(s, w):
"""按显示宽度补空格：中文算 2 列"""
return s + " " * max(0, w - sum(2 if ord(c) > 0x2000 else 1 for c in s))
# ---- ① Sethi-Ullman 标号：算一棵表达式树需要几个寄存器 ----
def label(t):
if not isinstance(t, tuple):
return 1
a = label(t[1])
b = label(t[2])
return a + 1 if a == b else max(a, b)
E1 = ("+", ("*", ("+", "a", "b"), ("-", "c", "d")), "e") # (a+b)*(c-d)+e
E2 = ("+", "a", ("+", "b", ("+", "c", "d"))) # a+(b+(c+d))
E3 = ("+", ("+", "a", "b"), ("+", "c", "d")) # (a+b)+(c+d)
E4 = ("+", ("*", "a", "b"), ("*", "c", "d")) # a*b+c*d
E5 = ("+", "a", ("*", "b", "c")) # a+b*c
E6 = ("+", ("+", ("+", "a", "b"), "c"), "d") # ((a+b)+c)+d
CASES = [
("(a + b) * (c - d) + e", E1),
("a + (b + (c + d))", E2),
("(a + b) + (c + d)", E3),
("a * b + c * d", E4),
("a + b * c", E5),
("((a + b) + c) + d", E6),
]
print("=== Sethi-Ullman 标号：表达式树需要几个寄存器 ===")
print(" " + pad("表达式", 26) + "需要的寄存器数")
for nm, e in CASES:
print(" " + pad(nm, 26) + str(label(e)))
print(" 规则：两棵子树标号相等 -> 父结点 = 标号 + 1（要同时留住两个结果）；")
print(" 不等 -> 父结点 = 较大的那个（先算大的，小的挤在剩下的寄存器里算）")
# ---- ② 固定一段 IR 与其活区间 ----
IR = [
(1, "t1", "b + c"),
(2, "t2", "d + e"),
(3, "t3", "t1 * t2"),
(4, "t4", "a + t3"),
(5, "ret", "t4"),
]
INTERV = {"t1": (1, 3), "t2": (2, 3), "t3": (3, 4), "t4": (4, 5)}
print()
print("=== 待分配的 IR 块与其活区间 ===")
print(" " + pad("序号", 6) + pad("IR", 18) + "活区间")
for i, d, e in IR:
iv = INTERV.get(d)
print(" " + pad(str(i), 6) + pad(d + " = " + e, 18)
+ ("[%d, %d]" % iv if iv else "-"))
print(" 变量 b/c/d/e/a 常驻内存，只有临时量 t1..t4 需要寄存器")
# ---- ③ 线性扫描分配：k 个寄存器 -> 溢出几次 ----
def alloc(k):
active, free = [], list(range(k))
spilled, stores, loads = set(), 0, 0
for v in sorted(INTERV, key=lambda x: (INTERV[x][0], x)):
s, e = INTERV[v]
active = [(a, en, r) for (a, en, r) in active if en >= s]
used = {r for (_, _, r) in active}
free = [r for r in range(k) if r not in used]
if free:
r = free[0]
else:
far = max(active, key=lambda x: INTERV[x[0]][1])
if INTERV[far[0]][1] > e:
spilled.add(far[0])
stores += 1 # 把 far 写回栈
active = [x for x in active if x[0] != far[0]]
r = far[2]
else:
spilled.add(v)
stores += 1 # 新值直接落栈
loads += 1 # 用它时再取回
r = 0
active.append((v, e, r))
return sorted(spilled), stores, loads
print()
print("=== 线性扫描分配结果 ===")
print(" " + pad("寄存器数 k", 12) + pad("溢出的临时量", 18)
+ pad("spill 存", 10) + pad("reload 取", 10) + "总访存次数")
for k in range(1, 5):
sp, st, ld = alloc(k)
mem = 4 + st + ld + 1 # 4 次取变量 + spill 存取 + 1 次回写 t4
print(" " + pad(str(k), 12) + pad(",".join(sp) if sp else "无", 18)
+ pad(str(st), 10) + pad(str(ld), 10) + str(mem))
print()
print("=== 结论 ===")
sp2, st2, ld2 = alloc(2)
sp3, st3, ld3 = alloc(3)
print(" k = 2：溢出 %d 个（%s），多 %d 次访存"
% (len(sp2), ",".join(sp2), st2 + ld2))
print(" k = 3：溢出 %d 个，只做 4 次取变量 + 1 次回写 = 5 次访存"
% len(sp3))
peak = max(sum(1 for v in INTERV if INTERV[v][0] <= i <= INTERV[v][1])
for i in range(1, 6))
print(" 峰值同时活 %d 个临时量（第 3 条 IR 上 t1/t2/t3 同时在用）" % peak)
print(" 寄存器不够 -> 溢出到栈 -> 访存变多，这就是“寄存器压力”的代价")
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
预期输出：
=== Sethi-Ullman 标号：表达式树需要几个寄存器 ===
表达式 需要的寄存器数
(a + b) * (c - d) + e 3
a + (b + (c + d)) 2
(a + b) + (c + d) 3
a * b + c * d 3
a + b * c 2
((a + b) + c) + d 2
规则：两棵子树标号相等 -> 父结点 = 标号 + 1（要同时留住两个结果）；
不等 -> 父结点 = 较大的那个（先算大的，小的挤在剩下的寄存器里算）
=== 待分配的 IR 块与其活区间 ===
序号 IR 活区间
1 t1 = b + c [1, 3]
2 t2 = d + e [2, 3]
3 t3 = t1 * t2 [3, 4]
4 t4 = a + t3 [4, 5]
5 ret = t4 -
变量 b/c/d/e/a 常驻内存，只有临时量 t1..t4 需要寄存器
=== 线性扫描分配结果 ===
寄存器数 k 溢出的临时量 spill 存 reload 取 总访存次数
1 t2,t3,t4 3 3 11
2 t3 1 1 7
3 无 0 0 5
4 无 0 0 5
=== 结论 ===
k = 2：溢出 1 个（t3），多 2 次访存
k = 3：溢出 0 个，只做 4 次取变量 + 1 次回写 = 5 次访存
峰值同时活 3 个临时量（第 3 条 IR 上 t1/t2/t3 同时在用）
寄存器不够 -> 溢出到栈 -> 访存变多，这就是“寄存器压力”的代价三条结论：
a + (b + (c + d))只要 2 个寄存器，(a + b) + (c + d)却要 3 个——两者算的是同一个值，只是括号的位置不同。这就是 Sethi-Ullman 规则里"子树标号相等才 +1"的直接后果。- k = 3 是这道题的分水岭：峰值同时活 3 个临时量，所以 k ≥ 3 时一次溢出都没有；
k = 2时溢出 1 个，访存从 5 次涨到 7 次（+40%）。 - k = 4 与 k = 3 完全一样：寄存器多到超过"峰值压力"就没有额外收益。分配器的目标不是"用光寄存器"，而是"压到峰值以下"。
考点
考点
1. 三件事的名字与职责（必背）
指令选择（用哪条指令）、寄存器分配（值放哪）、指令调度（顺序怎么排）。
2. 两种寄存器分配算法
| 项 | 图着色 | 线性扫描 |
|---|---|---|
| 依据 | 同时活则连边 | 活跃区间 |
| 复杂度 | NP 完全，用启发式 | 线性，很快 |
| 质量 | 好 | 略差 |
| 用于 | 静态编译器 | JIT、大函数快速编译 |
3. Sethi-Ullman 规则（能算）
叶子 = 1；左右相等 → +1；不等 → 取较大。它给的是"这棵树最少需要几个寄存器"，不是"用了几个"。
4. 高频陷阱
mul是伪指令：mul、li、la、move在 MIPS32 里都不是真指令，汇编器要展开成 2 条或 1 条真指令。add与addu的差别只在"溢出是否抛异常"，结果位型相同；addiu的u表示"不抛异常"，不是无符号。- 溢出（spill）的代价是两次访存（一次存、一次取），不是一次。
- 分支延迟槽里的指令无论跳不跳都会执行——把有副作用的指令填进去就是 bug。
- "寄存器越多越快"不成立：超过峰值压力就没有收益；而指令 Cache 是有限的，代码膨胀反而会变慢。
- 目标代码生成之后还有一步窥孔优化，所以"后端只有三件事"是简化的说法。
5. 后端三板斧与前面几章的对应
| 后端动作 | 依据的信息 | 哪一章讲过 |
|---|---|---|
| 指令选择 | IR 的运算类型 | lang/03-arith.md |
| 寄存器分配 | 活跃变量分析 | 本章 + soft/04-optimize.md |
| 指令调度 | 流水线延迟 | arch 流水线篇 |
小结
- 目标代码生成 = 指令选择 + 寄存器分配 + 指令调度，三件事互相牵制，要反复迭代。
- 寄存器分配的关键输入是活跃变量分析；不够就把值溢出到栈，代价是两次访存。
- Sethi-Ullman 标号告诉你一棵表达式树最少要几个寄存器——括号的位置会改变寄存器需求。
- 窥孔优化在生成之后再加一遍，专治"翻译腔"。
回到主线：lang/20-steps.md 把整条链拆成四步，编译器内部的六小步里，词法（soft/01）、语法（soft/02）、语义与中间代码（soft/03）、优化（soft/04）加本章的代码生成（soft/05），正好铺满。上一章把 IR 改少了、改便宜了；本章把它落成了真正的汇编——它马上就会被汇编器变成 lang/21-elf.md 里的可重定位目标文件，再被链接器拼成 lang/22-link.md 里的可执行文件。编译原理这一条线到这里收束：你从"编译器把 C 变成汇编"这句话出发，现在能自己说出这五个阶段各自在干什么、产物长什么样。
下一篇：关系模型与关系代数
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。