编译后端笔记-图着色法-1

图着色法-细节

函数活跃寄存器计算

这部分内容简单来说，就是对每个函数计算其各个基本块的活跃出入寄存器，也就是进入和离开基本块时，需要保持活跃（其值有意义/有用）的寄存器。

首先，我们遍历每个基本块，先计算其内部的依赖关系。简便起见use，我们倒序遍历基本块内的指令，并维护两个集合：def 和 live_use，分别代表“该基本块中新定义了的寄存器”与“该基本块中未定义但使用了其值的寄存器”，注意这里定义实际上指的是重新赋值。然后，在遍历过程中，对每一条指令，如果该指令为寄存器赋值（即对于该指令的 dst 寄存器），则该寄存器在当前位置一定是新定义了的，一定不是未定义但使用的，就从 live_use 中移除，向 def 加入。类似的，如果该指令使用了某寄存器值（即对于该指令的 src 寄存器），则该寄存器在当前位置一定是未定义但被使用，一定不是新定义的，从 def 中移除，向 live_use 中加入。注意到有的指令可能有寄存器同时在 def 和 src 中，由于我们是倒序遍历，因此应该按上述叙述顺序判断并处理。

这时，容易注意到所有的 live_use 都是满足我们对 live_in 要求的寄存器，因此赋值 live_in = live_use，但是这里的 live_in 还不全，需要后续处理。

为了处理 live_out，即计算哪些基本块新定义的寄存器是后续需要被使用到的寄存器，我们定义一个队列，存储基本块到寄存器的使用关系，每个 std::pair 代表某个块新定义了某个寄存器。我们将所有当前基本块 live_use 的寄存器和该块一起推入队列。

然后我们遍历队列，每次取队列头元素，获取当前块和当前块使用（但未定义）的某个寄存器，对于该块的所有前继基本块，如果前继的 live_out 中没有当前这个寄存器，则将其加入。这里需要判断一件事——有可能该寄存器也不是这个块定义的，如果不是，则需要将这个前继块和该寄存器再次推入队列，并为这个块的 live_in 记录下这个寄存器。

建图

在计算了各个基本块的出入活跃寄存器后，就可以开始建图了。我们使用邻接表存图，具体来说，使用如下的数据结构存储：

1 2	std::vector<char> appeared; std::vector<std::set<int>> edges;

两个动态数组的大小都是寄存器最大值。其中前者是一个记录某寄存器值是否出现在本函数中的布尔值数组，由于一些 C++ 特性，使用 char 类型。后者则是用于存边的，其内层是记录某寄存器和哪个寄存器有连边的集合，使用集合是为了保证不重复处理。

建图过程中，由于前面我们已经计算了基本块之间的活跃关系，现在我们只需要遍历每一个基本块，处理块内的寄存器活跃关系并连边即可。

在遍历每个基本块时，我们记录一个动态数组 live，存储“当前”的活跃寄存器，因为我们是对所有指令倒序遍历的，因此该数组的初始值为 live_out，即基本块结束时仍需要活跃的寄存器。

首先，基本块结束时所有的需要活跃的寄存器一定是互斥的（互相冲突的，不能存储在相同寄存器中的，后同），因此首先需要对它们两两连边。因此我们设置一个空的动态数组 tmp，将所有的 live 中的寄存器推入。

其次，我们需要将最后一条语句中的 dst 寄存器也推入 tmp 中，保证它和其他 live_out 的寄存器的互斥关系，原因后面解释。

这时，tmp 中就存下了所有“在基本块结束时”互斥的寄存器，我们对其中的寄存器两两加边即可（注：图是无向图，所有的加边都是双向边）。

然后就可以开始倒序遍历每条指令了。我们在遍历过程中不断维护 live 数组，具体来说，每当倒序遍历到一条新指令，这条指令如果对某寄存器进行了修改（即对于指令的 dst 寄存器来说），则该 dst 寄存器就不再 live，从 live 中移除。反之，如果使用了某寄存器的值（即对于指令的 src 寄存器来说），则此时（和从此时开始一直往前到该寄存器被定义，即被作为 dst）的这个 src 寄存器，就是活跃的，也就是说其值需要被保留，和其他所有的活跃寄存器互斥，将 src 和所有的 live 中寄存器连边，并将 src 推入 live 即可。

这样一来，我们就处理好了所有的 src 寄存器之间的互斥关系，但是还需要处理 dst 和 src 之间的互斥关系。注意到：同语句的 src 和 dst 是不互斥的，因为比如 add s0, s0, s1 这种操作（即只要后续不再使用 src 的原值，则完全可以使用相同的 src 和 dst，在人工写汇编时也会常常这么做以实现 += 等效果）但是每一条语句的 dst 和这之后的所有 src （准确来说是所有活跃寄存器）是互斥的，这很容易理解，比如下列语句：

1
2
3

addi %1, %2, 100 // 1
mul %5, %3, %4 // 2
mul %2, %1, %1 // 3

语句 2 中的 %5 和 %1 应当是互斥的，因为后面还需要用到 %1 的值，如果给 %1 和 %5 分配相同的寄存器，则后续语句 3 时使用 %1 时就得不到正确的值了，因为在语句 2 处被修改了。因此我们对上一句的 dst 寄存器和当前的所有 live 中的寄存器加边，保证其互斥。这里很容易发现，由于这样只能处理到第一条到倒数第二条语句的 dst，因为是对每条语句的“上一条”进行处理，因此最后一条语句的 dst 就没被处理，这也是前述处理最后一条语句 dst 的原因。

最后，在每条指令开始遍历时新建一个空数组，将所有的当前的新活跃寄存器和上条语句的 dst 一同推入数组，并对数组中的元素两两建边即可。