寄存器分配之图着色算法

type

status

date

slug

summary

寄存器分配

llvm-ir默认寄存器的个数是无限的，但是，落实到物理机上的对应架构，就必须想办法把这些假设的无限寄存器映射到有限的寄存器上（实在处理不了的就丢内存，称为spilling），总之，需要有算法实现寄存器的合理分配。图着色就是其中一种。

(本文内容主要参考现代编译原理 C语言描述（虎书）)

什么是图着色

着色问题说的是，给定一个图，求解用K种颜色能否涂完整张图，保证每个节点都有且仅有一个颜色并且相邻的节点颜色不同。这个问题是一个经典的NP完全问题（通俗点说就是求解时没有行之有效的算法，只能枚举或采用投机一点的枚举，但给定一个解却很容易判断是否正确的问题），对于寄存器分配，同一个时间仍在同时存在的变量就像是“冲突的节点”，在图中只需要用一条边连接。每一种颜色就代表一个寄存器位置。

建图

利用数据流分析方法，计算在每个程序点中同时活跃的临时变量集合。由该集合的每一对临时变量形成一条边并加入到冲突图中，重复该过程直到程序的每一个节点都完成这一过程

简化

假设寄存器个数为K个，那么考虑一个图G，如果存在一个节点m的边数小于K，那么对于图G-{m}如果能K着色，那么图G显然也可以进行K着色（m的邻接点即使颜色各不相同也有空余颜色可以染给m）。那么我们就可以以这个思想为突破口构建一种基于递归的化简问题的算法：删除图中度数小于K的节点，将其压入栈中（后面我们还会反序使用节点的删除序列），然后再次遍历，再删去新的度数小于K的节点，直到将问题规模化简到图为空或者出现下面“溢出”模块所描述的情况。

溢出

当简化过程中的G只包含≥K的度数的节点时，就不能简单地使用上文提到的化简算法了于是就需要将程序运行期间的某个变量移动到存储器而非寄存器中。如果我们假定这个被溢出的节点将来不会与图中的其他节点发生冲突，就可以将这个节点从图中删除并压入栈中（含有这种假定的溢出处理成为“乐观着色”），并继续尝试简化。

选择

到了真正去处理染色问题的时候了，从一个空的图开始，重复地将栈顶元素添加到图中，由于简化的规则限制，如果栈顶结点是通过简化过程被压入栈中的，那么它被添加到图中时至少有一种颜色可以使用。但是，如果是溢出过程压栈的节点，我们并不能保证它绝对可着色或绝对不可着色（邻接的节点不少于K≠邻接的颜色不少于K），因此此时可以遍历这个潜在溢出节点的颜色，如果少于K钟代表这个节点实际上并没有溢出，而如果真的已经被使用了K种不同颜色，我们将这个节点标记为“真溢出”并不赋予它任何颜色，继续进行选择过程，直到识别了所有的真溢出。

重新处理

如果选择阶段存在“真溢出”的节点，我们就认为他们在程序执行过程中位于存储器而非寄存器中，但是，调用它们时，仍然需要有新的临时变量去保存真溢出变量的从开始调用到结束调用的值。从某种意义上说，我们是将原来的“真溢出”变量的作用域破碎成了几个具有较小活跃范围的新的临时变量。在这种情况下构建新图并再跑一遍这个过程，称为迭代一次，通过反复迭代（虎书上说大约一到两次）就可以得到没有溢出的可以K着色的冲突图了。

图着色中的合并

节点合并

冲突图中存在类似j&b的情况，两个临时变量通过传送指令（MOVE）链接（称其为“传送有关节点”），但是彼此并不具备冲突关系，那么我们实际上可以将存在这种关系的两个变量合并在一起作为冲突图中的新节点并删去这个传送指令，这个新结点的边是之前两个被合并节点的并集。

如果贸然的进行合并，可能会出现原图可以进行K着色而合并后的图不能的情况（毕竟合并时会删去两个节点，并添加一个度数不小于两节点度数中较大值的节点）。如果真的合并出这样的结果，很明显是与优化背道而驰的，因此我们可以通过演绎论证去~~批判性地、辩证地、有选择地~~去合并一些节点，这些策略被称为“保守的合并策略”：

Briggs策略：

方法：只选择合并后邻接高度数节点（度数大于等于K地节点）数目小于K的两点进行合并

论证：简化过程会将低度数节点全都移走，与少于K个高度数节点连接的新节点自然也可以移走，不会影响结果。

George策略：

方法：a、b可以合并，当且仅当a的邻接点要么与b冲突，要么度数小于K

论证：如果不合并，简化时a的低度数节点会被移走，如果合并，合并后的节点a&b中来自a的低度数节点仍然会被移走，可见合并后的效果至少不会比不合并差。

带有节点合并功能的图着色算法设计：

建图：建图时将节点分为“传送有关”与“传送无关”两类。

简化：每次删除并压栈低度数的传送无关节点。

合并：对简化过的图实行“保守的合并策略”，如果合并产生的新节点不再与传送有关，那么就可以用于下一轮简化，重复简化与合并直到仅剩高度数节点或传送有关节点。

冻结：如果简化、合并都不能进行且程序未停机，寻找一个低度数的传送有关节点并删去所有关于它的传送关系（视为放弃与这个变量有关的合并），然后标记为传送无关继续进行简化-合并。

溢出、选择、重新处理均与普通图着色无区别。

特别的，部分不冲突节点的传送关系随着合并后可能变成冲突节点的传送关系，此时也不能进行合并优化，需要删去这个传送关系。称之为“受抑制的传送关系”

如果应用合并时发现了溢出，那我们需要让“可着色”优先于“可合并”（毕竟溢出一个节点整个程序就得重新跑至少一遍…），怎么办？~~难办就别办了~~ 我们需要忽略掉所有已经完成的合并从头开始跑这个程序。这样至少不会因为合并增加溢出数量。或者，先尝试合并，发现第一个潜在溢出时忽略所有合并。

溢出合并

如果一对被溢出的节点之间也有符合类似上述情况的，也可以通过合并的方式进行操作，并且由于这些变量已经确定是放在存储器而非寄存器中，他们的合并策略只需要从快从简就好，没有必要去遵循“保守的合并策略”了。（具体内容没太看懂……）

预着色问题

预着色的引入

有一些指令需要特定的机器寄存器，此时我们不能按照常规的处理临时变量的形式去处理这类特殊的节点（颜色固定就肯定不能再用随便一种没人用的颜色敷衍过去了，也不可能把寄存器丢进存储器…）。好在，每个寄存器（颜色）在冲突图中只有一个预着色节点（因为一个寄存器在任何时刻都不可能保存两个值）。并且如果不发生冲突，这些预着色的节点也可以与其他的临时变量进行合并，临时变量也可以使用与预着色节点一样的颜色（前提还是不发生冲突）。如果要做等效的话，机器寄存器对应的节点的度应为“无限大”。着色算法处理预着色冲突图时，只有将图化简到只含有预着色节点才能进入选择阶段。

由于预着色节点过于硬气的性质，我们不能让它一直活跃并占用着特定的寄存器，一种行之有效的方式是用一个临时变量在过程的入口将预着色寄存器的值复制(MOVE)下来，并在过程出口时还原(MOVE)。如果这个临时变量在过程中溢出了也没有关系，而如果没有溢出，我们也可以通过合并的方式将它与预着色寄存器合回去。

Caller-Saved、Callee-Saved

对于局部变量和不跨函数调用的临时变量，可以分配到Caller-Saved寄存器中，这样调用其他过程就可以不去考虑这些变量的存放问题了。而对于跨函数调用的临时变量，则需要保存在Callee-Saved寄存器中保存，并且只需要在调用过程的开头备份一次（称负责记录的这些临时变量为副本变量），在调用过程的结尾还原现场就可以了。

对于一个具体的跨函数调用的临时变量x，他会与所有Caller-Saved中的预着色寄存器冲突，也会与Callee的所有副本变量冲突，因此大概率会导致一个溢出，但是变量x由于是跨过程调用活跃的，可能在后续代码中会频繁使用，而副本变量使用次数低，因此在常规的溢出节点选择策略（最少使用、最大度数、最小生命周期），副本变量会比x更优先溢出。

含有预着色的图着色问题分析实例

（参考虎书173页，整个模拟过程太长了就不写了qwq）