元数据卡
- 前置知识：第7章（语义分析与中间代码）
- 预计时间：55 分钟
- 核心难度：进阶
- 阅读模式：高度专注（建议 55 分钟+）
- 完成标志：能解释寄存器分配的基本冲突图着色法，能列举 3 种常见的局部优化方法，理解 JIT 的核心思想
咒术高塔的顶层。你面前摆着一件终极武器——从源代码到机器码的全部工具链摊在桌上。但馆长只做了一件事：拿起一把剪刀，把中间代码上多余的枝叶修剪得干干净净。他说："这最后一步，是把精心构造的骨架装进机器的神经里，路上还要尽量多丢一些行李。"
你的进度
你从前端走过了词法分析、语法分析、语义分析和中间代码生成。现在你手上有一条流畅的中间代码序列（TAC/SSA），它语义正确，但冗余——成堆的临时变量、未用的赋值、多余的计算。最后两件事：优化这条代码，然后生成目标机器码。
你的任务
这一章你完成编译器后端的两大核心：产生目标代码和提升代码质量。你学习寄存器分配的基本策略（图着色法），掌握几种常见的局部（基本块内）和全局优化技术（常量折叠、公共子表达式消除、死代码消除、循环优化），最后理解现代编译器如何把所有这些组合起来，以及 JIT 编译器如何改变"先编译再运行"的传统模式。
破局 · 溯源
你的 TAC 生成器输出这样的代码：
t0 = a + b
t1 = t0 + c
t2 = a + b
t3 = t2 + d
t4 = t3 + t1它正确但浪费：a + b 算了两遍。你尝试修改前面的阶段来避免这个重复——但你不总能事先知道什么会被重复计算。而且用掉了一堆临时变量——t0 到 t4 总共 5 个"寄存器"，但在真实硬件上你可能只有 16 个通用寄存器。
你需要两件事：减少指令数量（优化）和把无数临时变量映射到有限硬件寄存器（寄存器分配）。
一、局部优化——在基本块内动手
基本块（Basic Block）是"只有一条入口、一条出口"的连续指令序列。优化的基本单位首先在基本块内。
常量折叠（Constant Folding）：如果操作数是常量，直接计算。
t0 = 3 * 4 + 2 → t0 = 14常量传播（Constant Propagation）：如果某个变量必定是常量，把它的所有引用替换为常量。
x = 5
y = x + 3 → y = 8公共子表达式消除（CSE, Common Subexpression Elimination）：如果同一个表达式出现在多个地方且操作数没变过，只算一次。
t1 = a + b t1 = a + b
t2 = a * c t2 = a * c
t3 = a + b → t3 = t1
t4 = t3 + d t4 = t1 + d死代码消除（Dead Code Elimination）：如果一个变量的值后续不再被使用，删掉计算它的指令。
t1 = a + b // t1 在后面没被使用——删掉
t2 = a * c
ret t2 // 只用到 t2拷贝传播（Copy Propagation）：如果 x = y 之后没有修改过 y，把 x 替换为 y。
x = y
z = x + 1 → z = y + 1二、寄存器分配——图着色法
寄存器分配是把无限多的虚拟寄存器（t0, t1, ...）映射到有限数目的物理寄存器（r0, r1, ..., r15）的过程。经典方法是图着色法（Graph Coloring）：
- 为每个虚拟寄存器建一个节点
- 如果两个虚拟寄存器在同一时刻都"活着"（活跃），它们不能共享同一个物理寄存器——在它们之间画一条边（冲突边）
- 得到的图就是寄存器冲突图
- 用 K 种颜色（K = 可用寄存器数）给图着色——如果相邻节点颜色相同，就冲突了
- 如果某个节点无法着色（没可用颜色），就把它的值溢出（Spill）到内存——临时存到栈上
假设有 3 个物理寄存器可用（K=3），冲突图如下：
t0 --- t1
| /
| /
t2
着色：
t0 = r0
t1 = r1
t2 = r2 ← 无冲突，三个寄存器都用了
如果再有 t3 且和所有节点冲突——溢出到栈。这是一个 NP 难问题（见第4章），所以实际实现使用启发式，在质量和速度之间平衡。LLVM 使用的是一种基于优先级排序的贪婪分配器：按"活跃区间长度"排序，尽量把短命变量挤进寄存器。
三、全局优化——跨越基本块
超过基本块范围的优化需要更复杂的分析。最典型的全局优化是数据流分析——在控制流图上传播属性。
到达定值（Reaching Definitions）：每个使用点之前，变量的最后一次赋值发生在哪里。这是所有全局优化的基础。
循环优化中的循环不变代码外提（Loop Invariant Code Motion）：如果某个表达式在循环的每次迭代中都算出一样的值，把它提到循环外面。
// 优化前
for (i = 0; i < 100; i++) {
x = 2 * PI; // PI 在循环内不变
a[i] = a[i] + x;
}
// 优化后
x = 2 * PI;
for (i = 0; i < 100; i++) {
a[i] = a[i] + x;
}强度削弱（Strength Reduction）：把开销大的运算转换为开销小的。比如循环中每次加 1（i = i + 1）比 i = i * 2 便宜。乘法可以变成加法、左移等。
四、目标代码生成——从 IR 到汇编
最后一步：把优化后的中间代码转换成目标机器的汇编指令。主要工作是指令选择（Instruction Selection）——每个三地址码模式对应一个或一组目标指令序列。
TAC: t1 = a + b
x86-64: mov eax, [a]
add eax, [b]
mov [t1], eax
ARM64: ldr w0, [sp, #a_offset]
ldr w1, [sp, #b_offset]
add w2, w0, w1
str w2, [sp, #t1_offset]指令选择的过程可以看作树模式匹配——你的 AST 子树（现在是 TAC 模式）要匹配到目标机器指令模板。LLVM 使用一种叫 SelectionDAG 的表示来做。
五、JIT 编译器
AOT（Ahead-of-Time）编译在第7章说的流水线是完整的。但还有一种JIT（Just-In-Time）编译器，在程序运行时才编译热点代码。
JIT 的核心直觉：很多代码只在某些路径上执行过，之前不需要编译。但某些函数频繁执行，JIT 检测到热点后，把它从解释执行切换到编译执行。Java 的 HotSpot VM、V8 的 TurboFan、LuaJIT 都是这样工作的。
JIT 编译器通常用渐进式编译策略：
源代码 → 字节码/解释执行
→ 基线编译器（快速，少量优化）
→ 优化编译器（慢，大量优化，应用 SSA、寄存器分配等）JIT 可以比 AOT 做得更好，因为运行时可以获得实际运行时信息——分支概率、类型分布（对于动态语言）、调用频率。这些信息可以让 JIT 做出 AOT 编译时无法确定的优化决策。
第一层：够用——看懂编译器的输出
你不用自己实现这些，但你应该能在编译器的输出中认出优化成果。用 gcc -O2 -S example.c 查看汇编输出，比较 -O0 和 -O2 的差异——你会发现 -O2 版本短了，临时变量少了，有些操作直接并入了。
第二层：深入——"优化不能改变程序语义"的铁律
无论做多少优化，编译器必须保证优化后的代码和原始代码在所有可观察行为上一致。这个约束叫"as-if"规则。编译器不能：对浮点数随意重新排序（因为精度不同）、对 volatile 变量做 CSE、在外部 printf 的副作用未确定时删除它。违反这个铁律，优化就变成了 bug 制造器。
常见陷阱
陷阱1：以为优化等级越高程序越快。 -O3 包含一些可能增加代码大小或产生负面影响的优化（比如循环展开和函数内联）。在嵌入式系统或缓存紧张的场景中，-Os（优化体积）可能比 -O3 更快。
陷阱2：忽视浮点运算的不可交换性。 x + y 不总是等于 y + x（浮点精度问题），所以编译器一般不对浮点数重新排序。如果你想允许浮点重排，用 -ffast-math——但可能有精度损失。
陷阱3：认为局部优化就够了。 没有全局数据流分析，局部优化只能看见基本块内的情况——很多跨块优化机会白白浪费。比如一个变量在基本块 1 中赋值，在基本块 3 中最后一次使用，中间块 2 不修改它——没有全局分析你就无法删除块 1 后段的无用赋值。
通关挑战
热身（5分钟）： 对下面这段 TAC，逐个应用常量折叠、死代码消除、公共子表达式消除（CSE）和拷贝传播：
t0 = 2 + 3 t1 = a + b t2 = t0 * 4 x = t2 y = a + b t3 = x + y ret t3挑战（30分钟）： 用你喜欢的语言实现一个最小化的寄存器分配器（图着色法，K=4）：输入是一个函数的 TAC 序列，输出是寄存器分配结果（哪些变量分配到哪些寄存器，哪些溢出到栈）。你不需要处理复杂的控制流——只处理线性代码。
观察： 选一个小的 C 程序，分别用
gcc -O0 -S、gcc -O1 -S、gcc -O2 -S编译，对比生成的汇编代码长度和指令数量。你能看到 CSE、常量折叠或循环优化的痕迹吗？
旅人笔记
编译器后端在两个约束间博弈：拥有无限可能（大量优化）和受限于铁律（语义等价）。寄存器分配把虚寄存器映射到物理寄存器；常量折叠、CSE、死代码消除、循环不变式外提等优化使代码更高效；JIT 在运行时利用实际信息做远超 AOT 的优化。
下一站预告
你走出了咒术高塔，馆长说："你懂咒语了。" 下一卷，你带着对"计算"的深刻理解，走进数据预言厅——从代码驱动的系统到数据驱动的决策，那是数据处理与数据科学的世界。