当词法分析、语法分析、语义分析、三地址码生成、以及各种优化之后,就来到了编译器里最关键的一步:
这是一个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。

阿尔萨斯和吉安娜

如若转载,请注明出处:https://www.summeng.org/5110.html