手把手带你写一门编程语言
宫文学
北京原点代码 CEO
7235 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 49 讲
起步篇:让一门超简单的语言跑起来 (21讲)
结束语 (1讲)
手把手带你写一门编程语言
15
15
1.0x
00:00/00:00
登录|注册

19|怎么实现一个更好的寄存器分配算法:原理篇

你好,我是宫文学。
到目前为止,我们的语言已经能够生成机器码了,并且性能确实还挺高的。不过我们也知道,现在我们采用的寄存器分配算法呀,还是很初级的。
那这个初级的寄存器分配算法会遇到什么问题呢?我们还有更优化的分配寄存器的思路吗?
当然是有的。接下来的这两节课,我们就会来回答这两个问题,我会带你从原理到实操,理解和实现一个更好的算法,叫做线性扫描算法,让寄存器的分配获得更好的优化效果。
首先,我们来分析一下当前寄存器分配算法的局限性。

初级算法的不足

在前两节课中,我们实现了一个初级的寄存器分配算法。这个算法的特点呢,是主要的数据都保存在内存的栈桢中,包括参数和本地变量。而临时变量,则是映射到寄存器,从而保证各类运算指令的合法性,因为像加减乘数这种运算,不能两个操作数都是内存地址。
这个算法有什么不足呢?你可以暂停一会儿,先自己想一下,大概有两点。
我们现在来揭晓答案。
第一点不足在生成的代码性能上。
你知道,我们做编译的目标,是要让生成的代码的性能最高,但这个算法在这方面显然是不合格的。因为参数和本地变量都是从内存中访问的,这会导致代码的性能大大降低。
第二点不足就在对需要 Caller 保护的寄存器的处理上。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《手把手带你写一门编程语言》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(2)

  • 最新
  • 精选
  • qinsi
    线性扫描算法本质是一种贪心算法。通常来说贪心算法得出的是局部最优解,不一定是全局最优。不过文中的线性扫描算法描述比较简单,并没有提及最优化的目标(使用的寄存器最少?寄存器的利用率最高?spill和reload次数最少?)以及选择空闲寄存器的策略是什么。针对不同的优化目标,选择空闲寄存器的策略或许会有不同? 看到下一讲中的例子想到一种情况。比如有这样的代码: let x = ... if (...) { ... = x ... } else { ... } ... = x ... 活跃性分析会认为在整个if语句中变量x都是活跃的。但其实在else语句块中并不需要x,x所占用的寄存器或许就可以给else中的临时变量使用。如果最优化的目标是使用最少的寄存器的话,这里就是一个可以被进一步优化的点。不过我觉得这个是活跃性分析算法的问题,合并了不同代码块中同一个变量的不同生存期。更精确的分析应该还是要对不同变量之间的依赖关系建图。
    2
  • ifelse
    学习打卡
    归属地:浙江
收起评论
显示
设置
留言
2
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部