寄存器配置

在编译器优化的领域里，寄存器配置（Register Allocation）的用途，在于使一个在较少寄存器数量的CPU可使用较大数量的变量，寄存器配置可使用在一个基本区段（Basic block）（区域寄存器配置）、函数或程序（全局寄存器配置）、或是透过Call Graph进行跨函数边域分析（跨程序寄存器配置），当完成每个函数或是程序，惯例上会要求每个调用函数的位置（Call site）必须插入存储或是还原。

简介

许多编程语言，程序员会有任意地配置过多变量的错误观念，然而在编译时，编译器必须决定在一个较小及有限寄存器的系统中如何分配这些变量，并非所有变量都是在同一时间执行，所以有些寄存器可能被分配超过一个变量。然而，两个被分配在同一寄存器的变量，若在同一时间使用，若是不破坏他的数值就无法被分配在相同的寄存器。无法被分配在相同的寄存器的变量必须被保留在随机存取存储器，在需要读取或写入时才会被加载，这个过程称之为溢出（spilling）。存储器存取速度比存取寄存器还慢，这会降低程序的执行速度，所以一个优化的编译器会尽可能的将更多的变量放置在寄存器。寄存器压力（Register pressure）这个词被使用在当硬件寄存器数量比起理想数量还少的状况，高压的情况通常代表会产生更多溢出以及更多重载的情况发生。

除此之外，程序可以被进一步的优化，只要可行，任何地方都能透过move指令来使一个寄存器的数值可以被移进移出，这在编译器中相当重要，这被使用在一些优化技术，例如静态单赋值形式，他会在中间码额外产生move指令。

图着色性的同构

透过活跃变量分析（Live variable analysis），编译器可以决定哪个变量的集合在同一时间是活跃的，也就是涉入move指令的变量。使用这些资讯，编译器可以建构一张图，使每个点（Vertex）在程序中代表一个独立的变量。当变量被同时使用时，则利用干扰边（Interference edges）链接两个节点，当变量同时涉入move指令时，则建立优先边（preference edges）。可以透过K-coloring用来解决寄存器配置的问题（K为寄存器可用的数量）。两个共享一个干扰边的节点不会被分配相同的颜色，而共享一个优先边的节点可能会被分配相同的颜色，有些节点可能一开始就会被上色，代表这些变量因为惯例或是模块间沟通的因素而必须留在某些特定的寄存器，图着色问题广义来说是NP完全问题，然而一个好的算法必须平衡性能以及代码的质量。

图着色技术是相当有效率，因为它不只考虑到变量的寄存器配置，还考虑在同时间执行的变量，逻辑上，如果变量V所有活跃的邻近变量可以被配置寄存器，那么通过V则可以访问到所有邻近的变量，所以这是一个递归的案例，目的是移除活跃变量集合中的变量。这个循环将持续进行，直到所有活跃变量都可以被配置，而其他的变量则溢出到存储器。

溢出

在多数的寄存器分配，每个变量会存在寄存器或是存储器，换句话说，如果一个变量无法被分配到一个寄存器，那么当这个变量要被使用时就会从存储器加载。一个溢出的变量（Spilled Variable）代表一个变量在存储器中而不在CPU的寄存器。举例来说，一个32位的变量溢出到存储器，他会获取32位的堆栈空间，而所有使用到这个变量的位置将会指到存储器，这样的变量的处理速度相较于寄存器的变量就会比较慢，所以要决定哪些变量必须溢出，就必须考虑到执行时间、代码占用空间以及资料空间等因素。

迭代寄存器接合

寄存器分配有很多类型，迭代寄存器接合（Iterated Register Coalescing，IRC）则是常用的一种，IRC是由LAL George及Andrew Appel在1996年提出，IRC基于一些原理所运作，第一，如果在图中存在无法被移动的节点，而这些与这些节点的连接的数量小于K，则这些图可以直接移除掉这些节点，因为一旦这些节点被加回去，则可以保证找到他们的颜色（简化）。第二，两个节点共享一个优先边，而他们邻近集合的连接总数小于K，那么这两个点可以被结合为一个节点（接合），如果上述两个步骤可以简化图，简化的程序在移动相关节点时（冻结时），可以再执行一次。最后，如果没有任何其他工作了，节点可以被标示为可能溢出并且从图中移除（溢出）。以上步骤用以减少图中节点的连接数，节点的连接数可能从大于K的情况降为低连接数，使节点可以被简化或是接合。这个阶段的算法被迭代，以确保简化及接合的质量。虚拟代码如下：

 function IRC_color g K :
 repeat
   if ∃v s.t. !moveRelated(v) ∧ degree(v) < K then simplify v
   else if ∃e s.t. cardinality(neighbors(first e) ∪ neighbors(second e)) < K then coalesce e
   else if ∃v s.t. moveRelated(v) then deletePreferenceEdges v
   else if ∃v s.t. !precolored(v) then spill v
   else return
 loop

在IRC中进行接合是相当稳定的，因为一个积极的接合可能会导致图的溢出，然而这同时启发了像是George coalescing接合了更多的节点，更可确保没有额外的溢出发生，Work-lists被使用在这个算法来确保每个IRC的迭代皆需要sub-quadratic time。

近期发展

利用图着色来改进的代码的效率虽然有效，但是配置的时间仍然很长，在静态编译的案例中，配置时间并不是那么被在意，但是在动态编译的案例中，例如即时编译（Just-in-time，JIT）编译器，快速的寄存器配置是很重要的，Poletto及Sarkar提出一个的有效技术线性扫描配置 （页面存档备份，存于互联网档案馆），这个技术仅需要一个阶段获取活跃变量的区间列表，较短生命周期区间的变量将会被分配到寄存器，而较长生命周期的变量将会被溢出，这个结果的性能平均只比图着色降低12%。

线性扫描算法的步骤如下：

1. 执行资料流程分析，用以获取活跃度资讯。持续纪录所有变量的活跃间隔于一个列表并以递减排序，这个间隔代表在这段时间内变量是活跃的，我们认为变量以及他们的间隔在这个算法中是可以交换的。
2. 反复通过活跃度的开始点，并且配置一个寄存器给每个活跃的变量
3. 在每个步骤维护一张在间隔内运作的列表，以活跃间隔的结束点进行排序（注意到插入有序的节点到一个平衡的二叉树，可使这张列表的维护成本为线性成本）。移除所有的逾期间隔，并且释放这些逾期的寄存器。
4. 当列表大小R，我们无法配置寄存器时，从运作列表中溢出间隔距离最远的点，并且分配给目前的间隔。如果目前的间隔是一个溢出的间隔，则不改变寄存器的分配。

Cooper及Dasgupta近期开发了一个有损的Chaitin-Briggs图着色算法，适用于JIT。有损代表这个算法所提出的干扰图并不是那么精确，这个优化减少了图建立的步骤，Chaitin-Briggs使它适合执行时期的编译。实验中显示，这个有损的寄存器配置比起线性扫描效率来得好。

理想的寄存器配置算法是基于Goodwin及Wilken所开发的线性规划算法，这些算法已经被Kong及Wilken延伸到更多架构。

最糟的情况是执行时间为指数，这个实验结果显示，实际的时间是典型的$O(n^{2.5})$。

在静态单赋值形式进行寄存器配置的可能，是近期研究所专注的项目，SSA形式程序的干扰图为弦图，可在多项式时间内进行着色。

参见

• Strahler number, the minimum number of registers needed to evaluate an expression tree.