寄存器分配

定义

寄存器分配(Register Allocation)是编译器后端的关键环节:中间代码假定可用寄存器无限多,而真实 CPU 只有十几到几十个物理寄存器,需要把虚拟寄存器映射到物理寄存器,放不下的变量「溢出」(spill)到内存。

经典方法

图着色法由 Chaitin 提出:构造冲突图,同时活跃的变量之间连边,给图着色使相邻节点颜色不同,颜色数即寄存器数;无法着色时选择代价最低的变量溢出并重试。

其他方法

线性扫描(Linear Scan)按变量活跃区间贪心分配,速度快,适合 JIT 编译器,曾被 HotSpot、V8 采用;LLVM 使用基于优先级的贪心分配器。

影响

寄存器分配质量直接决定访存次数,是影响生成代码性能最显著的后端优化之一。