13.2 寄存器分配：图着色与线性扫描
指令选择通常产生大量虚拟寄存器，但机器只有少量物理寄存器。寄存器分配（register allocation）要在满足活跃区间重叠、固定寄存器、函数调用和 calling convention 约束的前提下，把虚拟值映射到物理位置。无法留在寄存器中的值会 spill 到栈槽。
分配器消费第 12 章的活跃性结果。如果两个虚拟值在同一程序点同时 live，它们就互相干涉，不能占据同一个物理寄存器。
干涉图与着色
干涉图为每个虚拟寄存器建立节点，在同时活跃的值之间连边。若有 K 个物理寄存器，问题就变成使用 K 种颜色给图着色，相邻节点颜色必须不同。
精确图着色成本很高，编译器通常采用启发式算法：
1. 反复移除度数小于 K 的节点并压栈；
2. 若没有这种节点，根据成本与度数选择潜在 spill；
3. 逆序弹栈，分配一个邻居尚未使用的颜色；
4. 若没有可用颜色，就 spill 并重写函数。
预着色节点表示固定机器寄存器。call 会通过可能被 callee 覆盖的 caller-saved 寄存器，与跨调用活跃值形成约束。整数、向量、predicate 等寄存器类通常形成分离或部分重叠的着色问题。
合并 copy 与选择 spill
%b = copy %a 是理想 coalescing 候选：若 %a、%b 不干涉，把二者分到同一寄存器即可删除 copy。过于激进的合并会让剩余图更难着色，因此算法会在合并前使用保守测试。
spill 选择也不是简单挑“度数最高”。深层循环里频繁使用的值每次 reload 都很贵；可廉价重算的值则可以 rematerialize，而不是从栈加载。成本通常综合使用频率、循环深度、活跃区间长度和目标寻址模式。
插入 spill load/store 后，活跃性与干涉关系都会改变，因此要再次分配。重写必须避免新临时值继续 spill 所造成的无限循环。
线性扫描分配
线性扫描（linear scan）把虚拟值表示成指令顺序上的活跃区间 [start, end]，按 start 排序处理，并维护按 end 排序的 active set：
- 新区间开始前，先释放已经结束的 active 区间；
- 有空闲寄存器就直接分配；
- 否则依据 end 或 next-use 等策略，spill 新区间或某个 active 区间。
线性扫描速度快，适合 JIT；图着色允许更高编译成本时，往往得到更好分配。生产级分配器还会 split live range，在 call 或压力峰值周围建立不同区间，并允许同一值在不同区域使用不同物理寄存器，由 copy 连接。
验证分配结果
分配后，每个虚拟寄存器都必须被替换；每条指令的 register class、fixed register 和 tied operand 约束都要满足；任何干涉值不得共享物理寄存器。spill slot 的尺寸与对齐必须合法，跨调用活跃值必须依据 caller/callee-save 规则幸存。
实用 checker 可以符号执行 machine instructions，追踪每个物理寄存器与 spill slot 应装着哪个值。测试应覆盖高压力循环、call、二地址指令、预着色参数、异常边与带 hole 的活跃区间。