19｜怎么实现一个更好的寄存器分配算法：原理篇
宫文学
你好，我是宫文学。
到目前为止，我们的语言已经能够生成机器码了，并且性能确实还挺高的。不过我们也知道，现在我们采用的寄存器分配算法呀，还是很初级的。
那这个初级的寄存器分配算法会遇到什么问题呢？我们还有更优化的分配寄存器的思路吗？
当然是有的。接下来的这两节课，我们就会来回答这两个问题，我会带你从原理到实操，理解和实现一个更好的算法，叫做线性扫描算法，让寄存器的分配获得更好的优化效果。
首先，我们来分析一下当前寄存器分配算法的局限性。
初级算法的不足
在前两节课中，我们实现了一个初级的寄存器分配算法。这个算法的特点呢，是主要的数据都保存在内存的栈桢中，包括参数和本地变量。而临时变量，则是映射到寄存器，从而保证各类运算指令的合法性，因为像加减乘数这种运算，不能两个操作数都是内存地址。
这个算法有什么不足呢？你可以暂停一会儿，先自己想一下，大概有两点。
我们现在来揭晓答案。
第一点不足在生成的代码性能上。
你知道，我们做编译的目标，是要让生成的代码的性能最高，但这个算法在这方面显然是不合格的。因为参数和本地变量都是从内存中访问的，这会导致代码的性能大大降低。
第二点不足就在对需要 Caller 保护的寄存器的处理上。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
线性扫描算法优化寄存器分配，提高代码性能。文章分析了初级算法局限性，提出根据变量生存期动态分配寄存器，实现寄存器复用，减少寄存器占用。优化思路能有效提高代码性能，更高效利用寄存器资源。介绍了算法实现原理和变量活跃性分析的重要性。通过对变量活跃性分析，准确知晓每个变量生存期，进行寄存器分配。深入浅出地介绍了寄存器分配算法原理和实现过程，为读者提供清晰思路和技术细节。线性扫描算法可能得到非最优解，需要考虑最优解算法思路及其复杂性。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《手把手带你写一门编程语言》，新⼈⾸单¥59
《手把手带你写一门编程语言》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(2)
- 最新
- 精选
qinsi线性扫描算法本质是一种贪心算法。通常来说贪心算法得出的是局部最优解，不一定是全局最优。不过文中的线性扫描算法描述比较简单，并没有提及最优化的目标（使用的寄存器最少？寄存器的利用率最高？spill和reload次数最少？）以及选择空闲寄存器的策略是什么。针对不同的优化目标，选择空闲寄存器的策略或许会有不同？ 看到下一讲中的例子想到一种情况。比如有这样的代码： let x = ... if (...) { ... = x ... } else { ... } ... = x ... 活跃性分析会认为在整个if语句中变量x都是活跃的。但其实在else语句块中并不需要x，x所占用的寄存器或许就可以给else中的临时变量使用。如果最优化的目标是使用最少的寄存器的话，这里就是一个可以被进一步优化的点。不过我觉得这个是活跃性分析算法的问题，合并了不同代码块中同一个变量的不同生存期。更精确的分析应该还是要对不同变量之间的依赖关系建图。2021-09-222
ifelse
学习打卡2022-09-19归属地：浙江
收起评论
