编译原理与实践：全局寄存器分配技巧

为了更加有效地使用寄存器，将从全局来考虑如何分配寄存器。通过前面的学习已经知道，在每个基本块的结尾，活跃变量的值要被保存到内存单元中，后续基本块引用时还需重新加载。如果活跃变量被频繁地使用，频繁地加载和回写，势必会大大降低代码执行速度，因此，考虑为频繁使用的活跃变量指定一些固定的寄存器。就程序而言，大部分执行时间都花在循环上，因此，考虑给每个循环中的很活跃的变量指派相应的寄存器，而将剩余的寄存器用于存放基本块中局部变量的值。

以各变量在循环内需要访问内存单元的次数为标准来判断哪些变量最为活跃，并定义“指令的执行代价”的概念：一条指令的执行代价等于该指令访问内存单元次数加1。

例9.4 目标代码片段及其执行代价如表9-8所示。

表9-8　目标代码片段及其执行代价

根据每一条指令的执行代价，可以计算出给循环中各变量分配寄存器之后对降低执行代价的贡献度，并依此排序，把可用的寄存器固定分配给节省执行代价最多的变量使用，从而使有限数量的寄存器充分利用起来。

在循环中给某变量固定分配一个寄存器使用，那么，对于循环中各个基本块，与原有的简单代码生成算法所生成的目标代码相比，所节省的执行代价可按下述方法进行计算：

（1）把寄存器固定分配给那些在基本块中被定值的变量，而不是在定值时才分配。这样做，可有效减少基本块中变量定值前引用时访问内存的次数。定值前每引用一次，执行代价就节省1。

（2）把寄存器固定分配给那些在基本块出口之后的活跃变量，因此，没有必要再把它在寄存器中的值存放到内存单元中，从而避免了对内存单元的访问，执行代价就节省2。

按照上述方法，给循环W中某变量X固定分配一个寄存器，则循环每执行一次，节省的执行代价数S可用公式（9.1）进行计算。

其中：

函数Refer（X，B）记录的是基本块B中对X定值前引用X的次数。

函数Live（X，B）记录在基本块B中被定值的X在B的出口之后是否活跃。若X是活跃变量，则函数返回1，否则返回0。

A是变量执行概率。由于循环每执行一次，各个基本块不一定都会执行到，而且每一次循环，执行到的基本块还可能不相同，因此，循环中的每个基本块的执行频率可能不同。于是，对于基本块中的某个变量X，给它设置一个参与全部循环的概率A（A的取值在0～1之间）。为简单起见，A常常取为1，表示每循环一次，各个基本块都要执行一次。

公式中之所以减去4，是因为：在循环入口时，把活跃变量X的值从内存单元取到寄存器，其执行代价为2；在循环出口时，把活跃变量X的现行值从寄存器中存放到它的内存单元中，其执行代价也是2。这两处的执行代价合计为4，要减去。有时，也可以不这样做，毕竟上述执行代价在整个循环中只要计算一次，这与公式每循环一次就要计算一次相比，可以忽略不计。

分配寄存器时，先使用公式9.1计算出循环中各变量所节省的执行代价数S，然后排序，将寄存器固定分配给S较大的变量即可。

寄存器分配后，就可以使用代码生成算法来生成目标代码。由于寄存器的分配策略发生了变化，因此，目标代码生成算法也要做相应调整，具体如下：

（1）循环中的目标代码，凡涉及已固定分配到寄存器的变量，就用分配给它的寄存器来表示。

（2）如果其中某些变量在循环入口之前是活跃的，那么在循环入口之前，要生成把它们的值分别取到相应寄存器中的目标代码。(www.xing528.com)

（3）如果其中某些变量在循环出口之后是活跃的，那么在循环出口之后，要分别生成目标代码，把它们在寄存器中的值存放到内存单元中。

（4）在循环中每个基本块的出口，对未固定分配到寄存器的变量，仍按以前的算法生成目标代码，把它们在寄存器中的值存放到内存单元中。

例9.5 某程序的最内层循环如图9-1所示，箭头表示其中的转移指令。假设寄存器R0、Rl和R2将被固定指派给循环中某三个变量使用，各基本块入口之前和出口之后的活跃变量均已列在图中相应基本块的上方和下方。使用公式（9.1）计算各变量的S值，并据此来分配寄存器，同时，生成该循环的目标代码。

图9-1　程序循环示意图

利用公式（9.1）计算各变量的S值：

各变量在基本块中的定值前引用情况及出口后活跃情况如表9-9所示。

表9-9　基本块中的变量定值前引用情况及出口后活跃情况

各变量的S值如表9-10所示。

表9-10　将寄存器固定分配给各变量后的节省的代价

按照各变量S值的大小，把寄存器R0分配给D，R1分配给B；R2随机分配给A、E、F中的某一个，假设是A。寄存器R0、R1、R2固定分配给D、B、A后，它们在循环中不能另作他用。其余变量如需使用寄存器，只能从余下的寄存器中分配。

按照调整后的目标代码生成算法可将图9-1的中间代码翻译为图9-2中的目标代码。

图9-2　目标代码

寄存器的分配原则也不是一成不变的，可以做些调整。比如，对那些固定分配给寄存器的变量，如果它在循环中某个基本块出口之后不活跃，则考虑回收其寄存器，作为一般寄存器使用。对于外循环，也可以参照公式（9.1）进行寄存器的分配。