「目标代码生成」

1. 代码生成概述

一句话总结： 代码生成把优化后的 IR 翻译成目标机指令，是编译器后端与具体架构打交道的地方。

代码生成是编译器后端的第一道工序，输入是经过优化的 IR，输出是汇编或机器指令。它要解决四个互相关联的问题：选择哪些指令表达运算（指令选择）、把无限多的虚拟变量放进有限的物理寄存器（寄存器分配）、如何排布函数调用时的栈与寄存器（调用约定）、以及如何利用指令级并行（指令调度）。各环节相互制约，常需反复权衡。

1.1 正确性基准

代码生成的正确性是一切优化的前提：每条 IR 指令都必须翻译成目标指令序列，栈偏移与寄存器保存要与 ABI 一致，条件跳转的目标要经过重定位校验。编译器团队常用差分测试把同一程序交给参考编译器与本编译器编译，对比输出与运行结果，任何差异都可能是代码生成的缺陷。

IR:                x86-64 汇编:
  t1 = a + b        movl a(%rbp), %eax
  x  = t1 * 4       addl b(%rbp), %eax
                    shll $2, %eax
                    movl %eax, x(%rbp)

代码生成器的正确性要求每种 IR 指令都有对应的目标指令序列，且栈偏移、寄存器保存等约定与调用方完全一致。后端常按架构抽象出目标机描述，一个编译器支持多目标时复用大部分 IR 优化逻辑，仅后端分叉。这是 GCC 与 LLVM 多后端架构的基本分工。

2. 指令选择

一句话总结： 指令选择把 IR 运算映射到目标指令，复杂指令通过树模式匹配一次性覆盖多条运算。

目标指令往往能一次完成多个操作，例如 x86 的 add 指令可以同时完成地址计算与加法，或 lea 一条指令完成乘加。指令选择的常用形式是把 IR 表示为表达式树，用树模式匹配寻找覆盖整棵树的指令序列。自上而下的匹配可能产生冗余搬移，动态规划能保证最优覆盖。

// 指令选择: 对表达式树做模式匹配
// 模式: ADD(t1, MUL(t2, CONST(4)))
// 匹配到 x86 的 lea: lea (t2 * 4), t1 形式的寻址

struct Node { int op; Node *l, *r; };

Cost select(Node *n, Machine *m) {
    if (n->op == OP_CONST) return 1;           // mov imm
    if (n->op == OP_MUL && is_pow2(n->r))
        return 1 + select(n->l, m);            // shl
    if (n->op == OP_ADD && n->l->op == OP_MUL
        && is_pow2(n->l->r))
        return 1 + select(n->l->l, m);         // lea
    return 2 + select(n->l, m) + select(n->r, m);
}

LLVM 的 SelectionDAG 把指令选择建模为有向无环图上的模式匹配，通过 tablegen 描述指令集，自动生成匹配代码。指令选择的关键是覆盖完整：每条 IR 运算都必须映射到目标指令，缺失时退化为指令序列展开。复杂指令（如带寻址的加载）若被拆成多条简单指令，通常还能被后端的窥孔优化重新合并。

3. 寄存器分配

一句话总结： 寄存器分配把程序中的虚拟寄存器映射到物理寄存器，不够时溢出到内存。

程序用到的变量数量通常远超物理寄存器，寄存器分配决定哪些变量长期驻留寄存器、哪些临时溢出到栈。分配的目标是最小化访存开销并满足指令的寄存器约束（例如某些指令要求操作数在特定寄存器）。实现上先构建冲突图：两个虚拟寄存器若在同一程序点都活跃，则不能在同一个物理寄存器上，冲突图中相邻节点必须分配不同颜色。

def linear_scan(intervals, phys_regs):
    # 区间按起始点排序, 活跃区间不重叠即可复用寄存器
    active = []
    assignments = {}
    for itv in intervals:
        expire_old(active, itv.start, assignments)
        if len(active) < len(phys_regs):
            r = phys_regs[len(active)]
            assignments[itv.var] = r
            active.append(itv)
        else:
            # 无寄存器可用: 选择溢出代价最小的区间溢出
            spill = max(active, key=lambda i: i.end)
            if spill.end < itv.end:
                assignments[itv.var] = spill_slot()
                active.append(itv)
            else:
                assignments[spill.var] = spill_slot()
                active.remove(spill)
                r = phys_regs[len(active)]
                assignments[itv.var] = r
                active.append(itv)
    return assignments

图着色分配把问题归约为冲突图的图着色：k 个物理寄存器对应 k 种颜色，无法着色时选择溢出。溢出的变量访问替换为栈读写，可能引入新的冲突，因此需要迭代。线性扫描是 JIT 编译器常选的轻量方案，复杂度低、编译时间短，质量在多数场景足够。

3.1 溢出代价与分配迭代

分配器选择溢出对象时要考虑代价：被溢出变量每出现一次读写都要换成访存指令，使用频繁的变量溢出代价高。图着色分配常以溢出代价排序候选，选择代价最小者溢出。溢出会引入新的访存指令，可能改变活跃区间与冲突图，因此分配、溢出、重分配需要迭代收敛到稳定解。

def spill_cost(var, intervals):
    cost = 0
    for use in intervals[var].uses:
        cost += 1.0          # 每次使用读一次内存
    for d in intervals[var].defs:
        cost += 2.0          # 每次定义写回一次内存
    return cost

def allocate_with_spill(cfg, regs):
    for _ in range(MAX_ROUNDS):
        colors = graph_color(cfg, regs)
        if all_colored(colors):
            return colors
        var = min(spill_cost(v, intervals) for v in uncolored)
        insert_spill_code(var)
    return colors          # 极端情况接受残次分配

4. 活跃变量分析与图着色

一句话总结： 活跃区间决定冲突图边的有无，图着色在 k 色约束下给出寄存器映射与溢出方案。

活跃变量分析计算出每个变量活跃的程序点集合，一个变量的活跃区间从定义点延伸到最后一个使用点。若两个变量的活跃区间相交，它们就冲突。冲突图建好后做 k 着色：优先处理度数小于 k 的节点，将其压栈，最后尝试着色；剩余节点选择溢出，重复过程。

活跃区间示例:
  a: [1, 3)    b: [1, 5)    c: [3, 5)

冲突关系:
  a 与 b 冲突 (1-3 相交)
  b 与 c 冲突 (3-5 相交)
  a 与 c 不冲突 → 可共享寄存器

图着色的质量与冲突图精度直接相关，过度保守的活跃分析会制造虚假冲突，浪费寄存器。现代分配器如 LLVM 的 Greedy 分配器在区间图上做启发式分配，结合拆分（splitting）把长区间拆短以降低溢出代价。寄存器约束通过复制指令（coalescing）或约束边表达，把固定寄存器要求传导给分配器。

4.1 着色流程示例

以三个虚拟寄存器 r1 r2 r3 的冲突图为例：r1 与 r2 冲突、r2 与 r3 冲突、r1 与 r3 不冲突。若机器提供两个物理寄存器，图着色先弹出度数低的 r1 与 r3，r2 留下，然后反向着色：给 r2 分配寄存器 A，r3 分配 B，r1 复用 A，三色需求恰好被两色满足。这个弹栈顺序直接决定分配能否成功。

5. 栈帧布局与调用约定

一句话总结： 栈帧是函数调用的私有内存区域，调用约定规定参数传递、返回值与保存寄存器的责任方。

每个函数调用对应一个栈帧，存放局部变量、溢出变量、被保存寄存器与返回地址。栈帧布局要解决对齐、访问与帧指针选择。现代 ABI 多用寄存器传参（如 x86-64 用 rdi/rsi/rdx/rcx 传递前四个整数参数），减少内存访问。调用方负责保存调用者保存寄存器，被调用方负责保存被调用者保存寄存器。

x86-64 栈帧布局（低地址在下）:
  [返回地址]          <- rsp 上方
  [被保存寄存器]
  [局部变量区]        <- 溢出变量
  [对齐填充]
  [参数区域]
  rbp -> 帧指针基址
  rsp -> 栈顶（动态变化）

栈帧偏移通常在函数编译时静态确定，便于代码生成直接引用。帧指针用于动态栈大小场景（变长数组、alloca），现代 ABI 默认允许省略以省出一个寄存器。调用约定错误会导致跨语言、跨库调用崩溃，是后端最隐蔽的兼容性陷阱，编译器的代码生成表必须与平台 ABI 严格一致。

6. 指令调度与窥孔优化

一句话总结： 指令调度重排独立指令以隐藏延迟，窥孔优化在局部窗口内合并与删减指令。

指令调度针对流水线延迟：加载指令有数拍延迟，调度器把后续的独立计算插到等待期间，避免停顿。调度需要依赖分析：真正有数据依赖的指令不可颠倒，无依赖的指令可以自由重排。列表调度是常用启发式：按优先级从就绪队列依次挑选发射。窥孔优化在相邻指令的小窗口内做模式替换，如删除冗余 mov、合并相邻 push、把寄存器到寄存器的拷贝折叠进运算。

def list_schedule(block, latency):
    ready = [i for i in block.instructions if not block.deps(i)]
    emitted = []
    while ready:
        i = max(ready, key=priority)     # 取最长关键路径
        ready.remove(i)
        emitted.append(i)
        for j in block.succ(i):
            block.deps[j].discard(i)
            if not block.deps[j]:
                ready.append(j)
    return emitted

指令调度要小心寄存器分配后的物理寄存器依赖与内存别名。窥孔优化的模式规模受窗口限制，但胜在实现简单、风险低。LLVM 的 Peephole 与 MachineSink 在目标指令层做类似工作。调度与分配的顺序问题（分配前调度 vs 分配后调度）是后端架构设计的常见争论点。

7. 平台相关细节

一句话总结： 目标平台的位数、寻址、浮点与内建函数等细节决定代码生成的最终形态。

不同架构在寄存器数量、寻址模式、立即数范围、分支延迟槽与浮点指令上差异巨大。RISC 指令定长、寻址简单，CISC 指令变长、寻址灵活。立即数超过范围的运算需分解为多条，条件分支要处理短跳与长跳的区别。浮点运算可能由协处理器或向量指令完成。平台还要处理原子操作、内存屏障与 SIMD 指令的发射。

RISC-V 立即数范围示例:
  addi 支持 12 位立即数, 超过需分两步:
    lui  t0, hi_20          # 高 20 位
    addi t0, t0, lo_12      # 低 12 位
  而 MIPS 立即数仅 16 位, 策略类似但位数不同

字节序影响多字节常量的表示，结构体对齐影响字段偏移计算。平台相关的内建函数（如位操作、加密指令）需要生成器给出专门映射。硬件缺陷与扩展（如 x86 的 unaligned 访问惩罚、ARM 的 predicated 指令）也会进入代码生成策略。多平台编译器把这些差异封装在目标描述文件中，让代码生成逻辑尽量共享。

7.1 内建函数与硬件扩展

平台内建函数把特定硬件能力映射为可调用入口，例如位反转、循环移位、加密指令与 SIMD 加载。代码生成器对内建函数发射专门指令，否则退化为指令序列。硬件扩展（SSE、AVX、NEON、SVE）需要在指令选择中引入向量类型与宽度信息，并处理寄存器宽度与对齐约束。

8. 总结

目标代码生成把抽象的 IR 落到具体的指令集，正确性依赖于对 ABI 与架构细节的精确把握。寄存器分配与指令选择的质量直接决定最终性能，也是后端工程师投入最多的领域。最后一站将把同样的 IR 技术用于解释器与 JIT 编译。

延伸阅读

• 词法分析器实现
• 语法分析与 AST 构建
• 语义分析与中间表示
• 中间代码优化
• 解释器与 JIT 编译