暂存器配置

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

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

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

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

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

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学