寄存器分配Spill和Split

前两天又大概看了一下经典的寄存器分配。

在编译器的后端，指令选择之后，需要进行寄存器的分配。经典的寄存器分配算法是图染色算法。这个算法大概是这样的：首先，需要分析程序中的符号寄存器/值的活跃期；对于每一个值/活跃期都对应与图中的一个结点。在图中，两个结点之间存在边表示这两个结点代表的活跃期是有冲突的。也就是说，这两个结点对应的值在某些时刻是同时存在的。一个更加精确的定义是：如果结点A代表的活跃期被定义的时候，结点B代表的活跃期还没有结束，那么A和B之间存在冲突。以上两个定义事实上并不等价，定义二更加精确，定义一会引入一些本来不会冲突的“冲突”。

上面构造的这个图叫做冲突图。下面，就是用K种颜色给这个冲突图进行图染色。如果K等于目标机器的物理寄存器的数目，并且这个图可以被K种颜色染色，那么，我们将每一种颜色对应一个物理寄存器，就得到了一个寄存器分配方案。

然而，图染色问题是NP难的。

第一个用图染色算法实现了全局寄存器分配的人是Chaintin，好像是IBM的一个家伙（呵呵，当年的IBM好牛呀）。他给出了一个算法。对于图G，如果其中存在一个结点v，v的度小于k，那么，图G可以被k染色，当且仅当G-v可以被k染色。这个定理很容易证明。

根据这个定理，首先在G中找一个度数小于k的结点v，将它从图中删去，同时删去它的边。不断地重复这个过程。直到图变成空图或者图中所有的结点的度数都大于k。

如果图变成了空图，我们就找到了一种G的k染色。只要按照删除结点的相反的顺序依次将结点染色就行了，染色的时候要保证，每一个结点的颜色和它的邻居都不同（这一点可以做到，因为每一个被添加结点的度数都小于k，所以一定存在给它的颜色）。

如果图没有变成空图，那么这个图可能可以被K染色，可能不可以。一半采取的办法就是，从图中选择一个活跃期，表记将要将它转存到主存，并将它对应的结点从图中删除。然后继续下去。直到图变成空图。
如果在染色的时候发现，某个被表记的结点的确不能被染色，那就只好生成一些spill code将它存到主存了。选择这种结点的启发式规则一般是“spill代价/度数”最小的结点。也就是说，我们希望表记的结点spill时代价尽量小，同时删掉它时，可以删掉更多的边。

最简单的spill算法是这样的：对于某个被选择spill的活跃期，在其每一个定义之后插入一条store指令，在其每一个使用之前插入一个load指令。显然，这个算法会插入大量的冗余的store和load。
Spilling的时候，Chaintin给出的一些启发式规则来减少插入的代码：
1、如果某个活跃期的使用，该活跃期对应的值很容易计算，那么使用时就重新计算，而不要从主存载入；
2、如果一个活跃期的某个使用和其对应的定义很“近”，那么这个使用不应该从主存载入；
3、如果某个活跃期的相邻两个使用的距离很“近”，那么第二个使用不应该重新载入；
4、如果某个活跃期的所有的使用都离定义很近，那么这个活跃期不应该被spill。
其中，“近”的意思是指，同一活跃期的两次引用之间没有其它活跃期的终止。也就是说，两次引用之间，没有由于其它活跃期的终止而引入的额外的寄存器资源（这样有些spill就不应该进行，否则会引起进一步的spill）。

事实上，这些启发式规则的确减少了一些冗余代码，但还是有很多没有被删掉。

于是，就有人提出了interference region spill的概念。他指出，在原来的Spill方法中，一个生存期要么完全没有spill，要么完全spill了。而事实上，对于冲突的生存期，只要spill冲突的那一部分就行了。例如，A和B冲突，A覆盖的范围是1到5,B覆盖的范围是3到7,并且我们选择spill B。事实上，没有必要给B的每一个定义之后插入store，每一个使用之前插入load。真正冲突的区域只有3到5.对于B的定义，如果该定义可以大刀3-5的区域内，才需要插入store，否则不用，并且，对于B的使用，如果在3-5的区域内，之前才用插入一条load，如果在5之后，我们只要在5之后的某个地方插入一条load，将B重新load回寄存器，后面所有的使用，都不必再插入load了。当然，并不是所有的情况下，IR都要比完全spill的效果好。所以，实现的时候，通常会看看这两种策略那个更好，就采用那个。这样实现的spill动态spill code会平均降低33.6%，最多的降低了70%多。

另外一个为了降低spill代价的策略是Split Live Range。就是将一个大的活跃期分裂成若干个小的活跃期。期望这些小的活跃期可以被分配到寄存器中。在这个策略中，作者首先讨论了在什么情况下做这样做会得到好处，从而引入了包含图的概念。其实，在上面一种区域Spill的策略中，就是把一个大的活跃期分成若干个小的活跃期，没有冲突的部分被当成一个活跃期分配到寄存器中。这里的作者指出，并不是所有的冲突都可以用这种方法得到好处的。有些冲突，即使将大的活跃区分裂了，得到的小的活跃期仍然会和原来冲突的活跃期冲突。如果，一个活跃期的使用或定义处，和它冲突的活跃期有效，那么，即便将前者分成了小的活跃期，包含那个使用或定义的小活跃期仍然和原来的活跃期冲突。如果这个时候寄存器是不够的，那么寄存器仍然不够。所以作者通过包含图引入了完全包含的概念。A完全包含B，是指A的每一个定义都在B的每一个定义之前，A的活跃期长于B的活跃期，并且，在B的活跃期中没有对A的使用。这样，A就可以被分裂成两个活跃期，一个在B之前，一个在B之后。具体的方法是，在A的每一个定义之后，B的定义之前插入一条store，在B的生存期结束之后插入一个load。同样，并不是每一种情况使用split都有利。它的实现可以达到的效果和IR类似。

在优化编译器中，寄存器分配应该是一个比较重要的部分。但是，图染色是NP难的问题，我们就需要一些启发式的规则来解这个问题。而当图染色不能成功的时候，spill的策略就至关重要了。好的spill策略和坏的spill策略效果会差很多（程序的性能大概会差10%-18%左右吧）。