编译原理学习笔记0：寄存器分配算法概述

univasity 2024-01-24 发布于法国

展开全文

0.引子

最近重新正在重新阅读虎书，同时也在观看Compiler SIG技术沙龙，这个系列的博文会主要主要用来记录过程中所学。

1.寄存器分配问题概述：

1.1 寄存器在编译器中所扮演的角色

现代计算机中的存储主要遵循金字塔结构，即I/O速度越快的存储资源所提供的存储空间反而越小。寄存器作为目前存储系统中I/O速度最快的存储资源，其数量相对稀少。现代编译器在编译程序的时候，往往会尽可能将临时变量分配入寄存器当，从而加快这些变量的读取速度。

1.2 寄存器分配所面对的问题与寄存器调度算法

寄存器分配所面对可以被概括为如何通过较少的资源满足较多的使用需求。在未设置寄存器分配算法的编译器的Translate，canon和codegen阶段，编译器会默认cpu内部的寄存器是无限的，在实际的系统操作层面上，变量会被先被分配到数量无限的虚拟寄存器当中，之后再被映射到物理寄存器当中。在一些中大型项目当中，映射到虚拟寄存器上的变量的数量会远远超过物理寄存器的数量，而超出物理寄存器可以容纳范围的虚拟寄存器将会被映射到I/O速度较慢的内存当中，寄存器调度算法的主要作用就是如何合理的将不同的变量分配入寄存器当中，尽可能减少映射到内存的情况发生。值得留意的是，寄存器分配算法可以说是整个编译器优化算法中最为重要的一种算法，主要原因有以下两点：

优化提升显著：由于寄存器的I/O时间往往明显优于其他的存储资源，故此经过此类优化后的编译器在性能上的提升是十分显著的。
有效性强：寄存器分配算法不同于其他算法，其在几乎所有情况下都可以提升编译器的性能，而非只能在某些情况下提升性能，而在另一些情况下降低性能。

2.寄存器分配算法的分类：

寄存器分配算法的种类有很多，在实际的生产环境下往往会在一个编译器中使用多种寄存器分配算法，或者是多种寄存器分配算法的融合。本次的概述主要介绍三类寄存器分配算法。

2.1 基于图着色的寄存器分配算法：

基于图着色的分配算法是目前最早的一类寄存器分配算法，其主要的思路将寄存器分配问题转换为图着色问题。值得留意的是，基于图着色的寄存器分配算法需要满足以下两条公理论

对于任何程序P，其都可以基于P进行活跃分析，构建其干涉图G=（V,E）
对于任意给定的无向图G=（V，E），都存在一个程序p，进行活跃分析所得的干涉图正好是图G。

简而言之就是干涉图G和程序P存在一个双射的关系，

在具体实现上，其通过活跃性分析，构建一个干涉图，干涉图的具体形式为一无向图G=（V，E），当任意两个寄存器存在干涉的时候（即两个寄存器不可以被分配到一个寄存器中），由该程序所导出的干涉图中的两个结点会存在一条边，由此将寄存器分配问题转换为了K-着色问题。即我们需要使用K种颜色对干涉图进行着色，而这个问题也可以等价为，至少需要用K个寄存器来存放程序种的变量。以下是一个complier SIG技术沙龙中的例子

值得留意的是，传统的基于图着色的寄存器分配算法在实际生产环境下的应用较少，其主要的原因在于基于图着色的寄存器分配算法往往需要额外的存储空间来生成图结构，同时在算法实行过程主要采取多次迭代的方式来确认最后的分配结果，耗时较长。关于这一方面的详细资讯可以看看llvm的一个汇报，链接：/devmtg/2011…

2.2 线性扫描算法：

线性扫描算法是目前实际生产环境中使用最多的寄存器分配算法之一。其主要的优势在于较低的时间复杂度。其主要的思路是通过活跃性分析对不同变量的活跃区间进行分析，从而得到每一个变量的活跃性区间，从而实现寄存器分配。具体的实现可以参见以下的例子，下面给出了一个控制流图，线性扫描算法的第一步是先对控制流图中的每一个语句进行编号：

此时我们可以进行活跃性分析，分别得出N，S，I的活跃性区间，活跃性区间主要表达形式为[变量首次使用行号，变量最后一次使用行号], 活跃性区间的图形化表示如下

针对上面得出的活跃性区间，需要进行一个从左到右扫描，每当扫描到一个新的变量出现时，我们就为其分配一个新的寄存器。于此同时，每当扫描到一个变量的活跃区间结束时，我们就对其寄存器进行回收。

从上面的例子当中我们不难发现，线性扫描算法只需要对已活跃性区间进行一次扫描，就可以完成对寄存器的分配，其在实践复杂度上的优势非常明显。在下图中我们可以看到基于线性扫描的寄存器分配算法和基于图着色的寄存器分配算法的效果对比

2.3.基于弦图的寄存器分配算法：

基于弦图的寄存器分配算法可以被视为基于图着色的一种优化，基于图着色的寄存器分配算法相同，通过程序映射到干涉图的方式将寄存器分配问题转换为图着色问题，当时其通过弦图的性质减少了传统的图着色算法的迭代过程，从而减少了实践复杂度。值得留意的是。基于弦图的寄存器分配算法的使用前提是通过该编译器编译的大部分程序所映射出的干涉图为弦图。

要了解这个算法，我们首先要知道什么是弦图，弦图简单来说就是在任何无向图G中，任何长度大于4的环，其中必有两个结点是相联

基于弦图的寄存器分配算法的优化主要来自于弦图的一种性质：完美消去序列，在弦图我们可以通过逐个消去结点，然后进行着色，则一定会得到一个最优的着色方案。从而不必通过迭代的方式对干涉图进行着色。

其大致可以被分为以下两步：

解决弦图的完美消除序列：在弦图中，完美消除序列是一个节点的排列，满足任意节点的邻居在序列中是连续的。首先，从弦图中选择一个没有邻居的节点，将其加入完美消除序列。然后，对剩余的节点进行递归，每次选择一个没有邻居的节点加入序列，直到所有节点都加入完美消除序列。
分配寄存器：根据完美消除序列的顺序，依次处理每个节点。对于每个节点，根据它和已分配寄存器的节点的冲突关系，选择一个未被使用的寄存器分配给它。

基于弦图的寄存器分配算法主要存在的问题是并非每个干涉图都是弦图，如果当前的干涉图P并非是一个弦图，那么就只能回归到传统的寄存器分配算法中了。