寄存器着色与溢出

复习

　　有了冲突图，寄存器分配就变成了“用有限的颜色给图上色”。可现实很骨感：寄存器往往不够用。

　　给冲突图着色时，可能出现一种情况：当前的颜色数量（寄存器数），怎么都塞不下这张图——总有一个节点，它的邻居们已经把可用的颜色用光了，没色可分。

　　这时候，编译器不能“摆烂”，而要采取措施：把一部分变量从寄存器里请出去，放到内存（栈）里。 这个动作，就叫溢出（spilling）。

　　被“溢出”的变量，平时存在内存中；要用到它时，先从内存读进一个临时寄存器，用完再写回去。

　　它带来的变化很直接：

　　所以，溢出不是免费的。编译器会尽量挑那些“用途少、不常访问”的变量去溢出，把代价降到最低。选谁溢出，本身也是一个小优化问题。

　　你大概已经看出来了：溢出本质上是一次用时间换空间（更准确地说，是用访存的时间，换寄存器的紧张）。

　　寄存器快但少，内存慢但多。当“快资源”不够时，就用“慢资源”来补——这和缓存、虚拟内存的套路如出一辙。整部教程里，这种“稀缺资源不足时用富余资源顶上”的思路，反复出现。

　　着色完成后，每个变量就都拿到了具体的寄存器（或确定要溢出到内存）。接下来要落的，就是函数调用时那块栈怎么摆——也就是栈帧。

思考题 1

　　为什么会出现“寄存器溢出”？

思考题 2

　　溢出本质上是一种怎样的交换？

　　因为寄存器数量有限，而冲突图可能需要比可用寄存器更多的“颜色”。当着色时某个节点无法找到与邻居都不同的颜色，就说明寄存器不够，必须把部分变量移出寄存器、暂存到内存。

　　它是用时间换空间：寄存器快但数量少，内存慢但容量大。寄存器不足时，把部分变量放到内存，每次访问多一次读写（花时间），从而缓解寄存器的紧张。这与缓存、虚拟内存的思路一致。

设计师 | 南国微雪