暂存器配置

在编译器最佳化的领域里，暂存器配置（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.