图着色：为什么编译器会把变量当成地图来涂色
一段程序里，变量看起来只是名字：
编译器处理这个问题时，会先问一个很朴素的问题：哪些变量不能住在同一个寄存器里？如果两个变量在同一段时间都还要被使用，它们就不能共用一个格子。于是编译器把每个变量画成一个点，如果两个变量“生命时间重叠”，就在它们之间连一条线。这样得到的东西叫干涉图，英文是 interference graph。
接下来事情突然变成了离散数学里的图着色：给每个点涂一种颜色，相邻的点不能同色。这里的“颜色”就是寄存器。如果 CPU 有 8 个可用寄存器，那就像只有 8 种颜色。能涂完，说明这些变量都能安排进寄存器；涂不完，就得把某些变量 spill 到内存里，程序会变慢。
这个视角的好处是，它把“变量怎么分配寄存器”这种看起来很工程的问题，压成了一个清楚的数据结构问题：点、边、颜色。坏代码会在一堆特殊情况里打补丁，好编译器会先把问题建模对。数据结构对了，后面的算法才有地方站。
难点在于，普通图着色本身是很难的，编译器不能为了分配寄存器慢慢算一个完美答案。所以真实编译器常用近似方法：先删掉容易处理的点，给剩下的图着色，再把点一个个放回来。
思考题：如果两个变量从来不会在同一时间被继续使用，它们能不能放在同一个寄存器里？
#CS
一段程序里，变量看起来只是名字：
a、b、temp。但到了机器真正执行时，CPU 不认识这些名字，它只认很少几个寄存器。寄存器可以理解成 CPU 手边最快的几个小格子，问题是格子太少，变量太多，谁能放进去，谁必须暂时放回内存？编译器处理这个问题时，会先问一个很朴素的问题：哪些变量不能住在同一个寄存器里？如果两个变量在同一段时间都还要被使用，它们就不能共用一个格子。于是编译器把每个变量画成一个点，如果两个变量“生命时间重叠”，就在它们之间连一条线。这样得到的东西叫干涉图，英文是 interference graph。
接下来事情突然变成了离散数学里的图着色：给每个点涂一种颜色，相邻的点不能同色。这里的“颜色”就是寄存器。如果 CPU 有 8 个可用寄存器，那就像只有 8 种颜色。能涂完，说明这些变量都能安排进寄存器；涂不完，就得把某些变量 spill 到内存里，程序会变慢。
这个视角的好处是，它把“变量怎么分配寄存器”这种看起来很工程的问题，压成了一个清楚的数据结构问题：点、边、颜色。坏代码会在一堆特殊情况里打补丁，好编译器会先把问题建模对。数据结构对了，后面的算法才有地方站。
难点在于，普通图着色本身是很难的，编译器不能为了分配寄存器慢慢算一个完美答案。所以真实编译器常用近似方法：先删掉容易处理的点，给剩下的图着色，再把点一个个放回来。
思考题：如果两个变量从来不会在同一时间被继续使用，它们能不能放在同一个寄存器里？
#CS
