8.2 指令选择、ABI 与寄存器分配：把 IR 放进真实机器
走到高塔底层，无限虚拟值要塞进有限寄存器，抽象指令也要服从真实 CPU 和 ABI 的约束。
IR 可以假设无限虚拟值，目标 CPU 却只有有限寄存器、受约束的指令编码和固定调用约定。代码生成不是把每条 IR 指令查表替换，而是在多项相互影响的约束中选择一组合法机器操作。
本课目标
- 理解 legalization、指令选择和调度的职责；
- 说明 ABI 对参数、返回值、栈与寄存器的约束；
- 用 liveness 构造寄存器冲突；
- 比较图着色、线性扫描、spill 与 coalescing。
1. 目标描述不只是一张 opcode 表
目标后端需要知道：
- 寄存器类别、别名与保留寄存器；
- 指令操作数形状和立即数范围；
- 支持的数据类型和合法位宽；
- 寻址模式；
- 指令延迟、吞吐与代码大小；
- 调用约定、栈对齐与重定位；
- 原子和内存序映射。
同一 IR add i64 在 64 位目标上可能一条指令完成，在较窄目标上可能拆成多条带进位操作。
2. Legalization 先让操作可表示
IR 操作不一定被硬件原生支持。legalizer 可以：
- 扩展或拆分类型；
- 把操作展开成指令序列或运行库调用；
- 把非法立即数物化到寄存器；
- 将高层原子操作映射为目标序列。
例如目标没有整数除法指令时，可能调用 helper；目标没有 i128 加法时，可拆成两个 i64 与进位。
合法化时必须维持符号扩展、溢出、异常和原子性语义。能“算出差不多结果”的序列不够。
3. 指令选择是带成本的覆盖
IR：
t0 = mul x, 4
t1 = add base, t0
t2 = load t1某些目标可用带 scale 的寻址模式把乘法、加法和 load 合并。选择器可通过：
- 树/DAG 模式匹配；
- 动态规划最小成本覆盖；
- 表驱动重写；
- 全局或局部搜索。
成本不只看指令条数。代码大小、关键路径、微架构、寄存器压力和调度机会都可能改变最佳选择。
4. ABI 让独立编译单元能够协作
调用约定规定：
- 参数放在哪些寄存器或栈槽；
- 返回值怎样传递；
- 哪些寄存器由 caller/callee 保存；
- 栈指针、帧指针和对齐要求；
- 可变参数和聚合类型布局；
- 异常展开与调试元数据。
函数内部生成得再快，若破坏 callee-saved 寄存器或栈对齐，也会在跨函数调用时损坏状态。ABI 是外部可观察契约，不属于可自由优化的内部细节。
5. Liveness 是后向数据流
对基本块 $B$：
$$ LIVEOUT[B]=\bigcup_{S\in succ(B)}LIVEIN[S], $$
$$ LIVEIN[B]=USE[B]\cup(LIVEOUT[B]-DEF[B]). $$
若某值当前值会在未来路径使用，且在此之前没有重新定义，它就是 live。对 SSA，value 单定义使 def-use 清楚，但经过 φ、调用约束和机器指令 tied operands 后，物理分配仍复杂。
指令级逆向扫描可从块 live-out 开始：先移除当前定义，再加入当前使用。若两个虚拟寄存器的 live range 重叠，它们通常不能占同一物理寄存器。
6. 冲突图与图着色
每个虚拟寄存器是节点，同时活跃的值之间连边。$K$ 个可用寄存器对应 $K$ 色着色。
一般图着色困难，分配器使用启发式：
- 简化低度数节点；
- 选择潜在 spill 候选；
- 弹栈并尝试着色；
- 无色可用时插入 spill/reload，再重算。
真实机器还有预着色节点、寄存器类别、子寄存器别名、固定操作数和调用 clobber，远比普通 $K$ 色图丰富。
7. Spill 不是简单“放到栈上”
spill 会增加 load/store、栈帧与内存流量。选择候选时常考虑：
- 使用频率与循环深度；
- live range 长度；
- 重新计算是否比 reload 便宜；
- 可拆分 live range 的位置；
- 调用点跨越成本。
插入 spill 后会产生新临时值和活跃区间，可能需要再次分配。spill slot 也可在生命周期不重叠时复用。
8. Coalescing 与线性扫描
复制：
v2 = copy v1若 v1、v2 不冲突，可分到同一物理寄存器并删除 copy。过度 coalesce 会合并 live range、增加节点度数，反而导致 spill，所以要用保守准则。
线性扫描按 live interval 顺序快速分配，常用于编译时间敏感场景。它实现简单、速度快，但质量取决于区间构造、拆分和 spill 策略。图着色也不自动优于线性扫描；应对具体目标和工作负载衡量。
9. 指令调度与寄存器压力互相影响
调度把相互独立的指令重排，以隐藏延迟并遵守数据、内存与资源依赖。提前计算可能增加并行度，也会让结果活得更久，提升寄存器压力。
因此选择、调度、分配并非严格单向：后端可能在不同阶段重调度、拆分 live range，或使用压力感知成本。删除一条指令也不保证更快，关键路径和端口竞争可能更重要。
常见误区
- 一条 IR 指令对应一条机器指令：类型、寻址和目标能力会导致合并或展开。
- 寄存器不够就挑任意变量 spill：选择会显著影响运行成本和后续压力。
- 指令越少越快：延迟、吞吐、代码布局和缓存同样重要。
- 函数内部正确就够了：ABI、unwind 和调试信息也是代码生成契约。
练习
- 给一段直线 IR 计算逐指令 liveness 并画冲突图。
- 用 2 个物理寄存器分配三个 live range，比较两种 spill 选择。
- 为目标不支持
i128加法设计合法化序列。 - 列出一次函数调用前后 caller-saved 与 callee-saved 值的处理责任。
小结
目标代码生成要同时满足类型合法化、指令约束、ABI 和成本模型。liveness 把未来使用变成冲突关系，分配器再用有限物理寄存器、spill 与复制合并实现可执行布局。
下一课比较 AOT 与 JIT，重点不是“运行时编译更聪明”，而是画像、推测、守卫与反优化如何组成一份可撤销的性能决策。