rat 的寄存器分配器

📌 One-Sentence Summary

通过衡量各项特性的实际效果并剔除无效优化，作者用仅 584 行的高效优先级装箱分配器替换了原有的 1，392 行线性扫描寄存器分配器，不仅提升了编译速度，还生成了更优质的代码。

📝 Summary

作者详细介绍了重写其编译器后端「rat」中寄存器分配器的全过程：摒弃了原本臃肿的线性扫描实现，转而采用受 LLVM 贪心算法启发的精简版优先级装箱分配器，代码量仅 584 行。该分配器避开了寄存器驱逐、活跃区间拆分以及次级遍历等复杂机制，将分配流程简化为五个清晰的阶段：活跃区间计算、固定寄存器处理、合并、选择寄存器与溢出。在重写前进行的实证消融测试表明，诸如重新物化（Rematerialization）和乐观二次遍历等常备受推崇的特性，在实际场景中的收益微乎其微。相比之下，基于循环深度加权的优先级、副本合并以及活跃区间空隙等更简单的技术贡献了绝大部分的代码质量提升，同时使 SQLite 的编译时间缩短了 43%。

💡 Main Points

彻底简化并舍弃驱逐与区间拆分，依然能生成更优质的代码

工业级分配器通常包含复杂的寄存器驱逐和区间拆分逻辑。剔除这些特性后，代码量缩减了 58%，同时生成的指令数减少了 3.6%，存储指令减少了 22%。

位图设计自然满足了调用约定规范

通过将物理寄存器的可用性以及调用者保存寄存器建模为跨指令槽的位图，跨调用变量会自然落入空闲的被调用者保存寄存器中，无需编写额外的临时规则。

消融测试表明备受推崇的编译器优化往往收效甚微

在重写前对各项特性进行的单独测试显示，乐观二次遍历消耗了分配器 37% 的运行时间，却仅减少了 0.01% 的指令；而副本合并和生命周期空隙则贡献了近一半的整体收益。

按优先级排序的装箱策略有效平衡了跨循环深度的分配压力

根据循环深度加权的引用频率评估活跃区间，并结合区间长度的平方根进行归一化，确保了生命周期短的高频变量优先获得分配，同时避免长期运行的循环计数器陷入饥饿状态。

💬 Key Quotes

所以我测试了哪些部分真正有用，抛弃了其余部分，用 584 行代码编写了一个优先级装箱分配器。

在重写之前，我依次关闭了每个旧特性并测量了代码。这是该项目中最有价值的一个小时：

这给我的教训是：在迁移旧代码之前，务必先对其进行测量。旧分配器中的许多代码根本毫无作用。

📊 Article Meta

AI Screening： 90

Featured： Yes

Source： Hacker News

Author： Hacker News

Category： 软件编程

Language： 英文

Read Time： 11 min

Word Count： 2502

Tags：

编程与工程 , 性能优化 , 代码质量 , 后端开发 , 开发者工具