指令寄存器在哪里(指令寄存器英文)

词法分析、语法分析、语义分析、三地址码生成、以及各种优化之后,就来到了编译器里最关键的一步:

指令选择寄存器分配。

这是一个NP问题。

当然我不需要解决NP难题,只需要给出一个尽量优化的可行解。

年轻的王子,欢迎来到诺森德[捂脸]

你已经没有了安多哈尔的清澈眼神,经历了斯坦索姆的悲剧,见过了吉安娜的转身,来到了冰天雪地的这里。

现在你只需要造一把霜之哀伤,打败那个长着翅膀的马尔甘尼斯,你就赢了[笑哭]

指令寄存器在哪里(指令寄存器英文)

真实的马尔甘尼斯不长那样,而是下图这样。

龙书里只是简单的提了一下,寄存器分配使用图的着色算法。

指令寄存器在哪里(指令寄存器英文)

龙书,只是一本编译器的入门书

具体怎么搞,还是得自己去想。

毕竟龙书只是一本编译器的入门书。

如果在RISC平台上,因为指令集不使用特殊寄存器,这个算法还要简单一些。

ARM的指令和寄存器的耦合度几乎没有,指令选择寄存器分配可以看作两个互不干扰的单独问题。

根据变量活跃情况分配寄存器,根据运算符选择指令集,就行了。

但是英特尔CPU偏偏是CISC平台,它的乘法、除法使用EAX和EDX,移位使用CL。

这种个别指令与个别寄存器绑定的设计,给寄存器分配带来了巨大的麻烦。

int a = 5, b = 3;

int c = a / b;

c += a;

这种含有除法运算的代码,咋办?

为什么C语言的书里都让你用移位代替乘法和除法?

就是乘法除法在底层并不好实现。

这种不好实现的起因,就是英特尔的别扭设计。

乘法除法指令与寄存器的耦合度太高了。

变量之间的关系可以做一个变量冲突图,然后对它进行K-着色(K是可用的寄存器数量)。

但除法指令对EAX和EDX的约束,该怎么加上去?

如果被除数不正好在EAX里,就要把它移到EAX里,这必然会导致溢出EAX之前的值(把它保存到内存)。

这肯定会导致额外的mov指令。

一个通用的、大范围的变量着色算法,才是最好的寄存器分配算法。

它可以在多行程序之间为使用频次高的变量选择合适的寄存器,尽量减少内存的读写。

指令寄存器在哪里(指令寄存器英文)

为了不在遇到除法的时候先保存EAX和EDX,我想了2天1夜,才想到可以把寄存器也加到变量冲突图里。

只要在着色时跳过它就行,因为寄存器本身自带着颜色(即寄存器的编号)。

没有分配寄存器的变量编号为-1,寄存器编号都是正整数,以作区分。

经过着色算法之后,如果变量的编号还是-1,说明没有多余的寄存器给它了。

再用到它时,可以临时溢出一个寄存器,把它从内存里加载起来。

因为英特尔是CISC计算机,加减乘除的指令都是可以直接读写内存的,有时候并不需要专门加载个寄存器。

具体什么情况,可以在生成汇编码时具体处理,尽量用1条指令解决。

乘法除法的特殊性,以及寄存器不够多时的溢出加载,变量图的着色算法只是一个寄存器的预分配。

在真生成汇编码时,还是要做轻微改动。

这个算法,也是编译器里最核心的算法。

它被升级的越好,内存读写次数越少,生成的汇编码的效率越高。

回想当年你刚学C语言时,打的那行hello world,以及你的那个疑问:

为什么会这样?

why is this ? !

我的王子,你后悔吗?

我是马尔甘尼斯,

欢迎来到编译器的诅咒之路[捂脸]

Principles, Techniques, and Tools

of Compiler。

指令寄存器在哪里(指令寄存器英文)

阿尔萨斯和吉安娜

本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 sumchina520@foxmail.com 举报,一经查实,本站将立刻删除。
如若转载,请注明出处:https://www.summeng.org/5110.html