注册分配

在编译器优化中，注册分配是将本地自动变量和表达结果分配给有限数量的处理器寄存器的过程。

寄存器分配可以通过基本块（本地寄存器分配），整个功能/过程（全局寄存器分配）或通过CALL-GRAPH（概要寄存器寄存器分配）遍历的功能边界进行。每个功能/过程完成时，调用约定可能需要插入每个呼叫站点周围的保存/还原。

情境

原则

在最常见的体系结构中的不同数量的标量寄存器
建筑学	32位	64位
手臂	15	31
英特尔X86	8	16
mips	32	32
电源/PowerPC	32	32
RISC-V	16/32	32
Sparc	31	31

在许多编程语言中，程序员可以使用任意数量的变量。计算机可以快速读取和写入CPU中的寄存器，因此当CPU寄存器中有更多变量时，计算机程序运行得更快。另外，有时访问寄存器的代码更紧凑，因此代码较小，如果使用寄存器而不是内存，则可以更快地获取。但是，寄存器的数量有限。因此，当编译器将代码转换为机器语言时，它必须决定如何将变量分配给CPU中有限数量的寄存器。

并非所有变量都在使用（或“实时”）同时使用，因此，在程序的寿命中，可以使用给定寄存器来容纳不同的变量。但是，在不损坏其中一个变量的情况下，不能同时将两个正在使用的变量分配给同一寄存器。如果没有足够的寄存器容纳所有变量，则可能会将某些变量移到RAM 。此过程称为“溢出”寄存器。在程序的寿命中，变量可以溢出和存储在寄存器中：然后将此变量视为“拆分”。访问RAM比访问寄存器要慢得多，因此编译的程序运行速度较慢。因此，优化编译器旨在将尽可能多的变量分配给寄存器。高“寄存器压力”是一个技术术语，这意味着需要更多的溢出和重新加载；它由Braun等人定义。作为“指令同时实时变量的数量”。

此外，一些计算机设计缓存经常被访问的寄存器。因此，可以通过将相同的寄存器分配给一个源和目的地来进一步优化程序 move 尽可能的说明。如果编译器使用中间表示，例如静态单分配形式（SSA），这一点尤其重要。特别是，当SSA未完全优化时，它可以人为地生成其他 move 指示。

注册分配的组件

因此，注册分配包括选择在运行时存储变量的位置，即内部或外部寄存器。如果要在寄存器中存储该变量，则分配器需要确定将存储该变量的寄存器。最终，另一个挑战是确定变量应保持在同一位置的持续时间。

注册分配器无视所选分配策略，可以依靠一组核心行动来应对这些挑战。这些行动可以分为几个不同的类别：

移动插入: 此操作包括增加寄存器之间的移动指令数量，即在其一生中将变量生存在不同的寄存器中，而不是一个。这发生在分裂的实时方法中。
溢出: 此操作包括将变量存储到内存而不是寄存器中。
任务: 此操作包括将寄存器分配给变量。
合并: 此操作包括限制寄存器之间的移动数，从而限制了指令总数。例如，通过识别不同方法的变量实时，并将其存储在整个生命中。

许多注册分配方法对一个或多个特定类别的动作进行了优化。

注册分配中提出的常见问题

注册分配提出了几个问题，可以通过不同的寄存器分配方法解决（或避免）。三个最常见的问题被确定为以下：

混音: 在某些架构中，将值分配给一个寄存器可能会影响另一个寄存器的值：这称为混叠。例如， X86体系结构具有四个通用32位寄存器，也可以用作16位或8位寄存器。在这种情况下，将32位值分配给EAX寄存器将影响AL寄存器的值。

预彩: 这个问题是一种迫使某些变量分配给特定寄存器的行为。例如，在PowerPC 调用约定中，参数通常在R3-R10中传递，并且返回值在R3中传递。

NP问题: Chaitin等。表明寄存器分配是NP完整问题。他们通过证明可以构建程序，以使程序的寄存器分配（代表节点和代表可用颜色的机器寄存器的寄存器分配）将图形分配问题减少到寄存器分配问题，将其用于该程序的颜色。原始图。由于图形着色是NP硬性问题，并且注册分配在NP中，因此证明了该问题的NP完整性。

注册分配技术

注册分配可以通过基本的代码块进行：据说是“本地”，并首先由Horwitz等人提到。由于基本块不包含分支，因此分配过程被认为是快速的，因为控制流图的管理寄存器分配中的合并点揭示了自身耗时的操作。但是，这种方法被认为不像“全局”方法一样优化代码，该方法在整个编译单元（例如一种方法或过程）中运行。

图形分配

图形分配是解决寄存器分配的主要方法。它是Chaitin等人首先提出的。在这种方法中，图中的节点表示活范围（变量，临时性，虚拟/符号寄存器），它们是注册分配的候选者。边缘连接的现场范围，即干涉的现场范围，即至少在一个程序点同时生活的现场范围。然后，寄存器分配减少到图形着色问题，其中将颜色（寄存器）分配给节点，以使边缘连接的两个节点无法接收相同的颜色。

使用Livices分析，可以构建干扰图。干涉图是一个无向图，其中节点是程序变量，用于建模变量不能分配给同一寄存器。

原则

Chaitin风格的图形寄存器分配器中的主要阶段是：

Renumber ：在源程序中发现实时范围信息。
构建：构建干涉图。
Cocece ：合并通过复制说明相关的非交流变量的实时范围。
溢出成本：计算每个变量的溢出成本。这评估了将变量映射到内存对最终程序速度的影响。
简化：在推论图中构建节点的排序
溢出代码：插入溢出说明，IE负载和存储以在寄存器和内存之间的通勤值。
选择：将寄存器分配给每个变量。

缺点和进一步的改进

图形分配具有三个主要缺点。首先，它依赖于图形色（ NP完整问题）来确定哪些变量溢出。找到最小的着色图确实是NP完整的问题。其次，除非使用实时划分，否则驱逐的变量到处都溢出：在变量定义之后，尽早插入商店说明；负载说明分别插入较晚，就在变量使用之前。第三，一个未溢出的变量在整个生命周期中都保存在同一寄存器中。

另一方面，单个寄存器名称可能出现在多个寄存器类中，其中一组是一组寄存器名称，在特定角色中可以互换。然后，多个寄存器名称可能是单个硬件寄存器的别名。最后，图形着色是一种用于分配寄存器的侵略性技术，但是由于使用干扰图而在计算上很昂贵，它的最差案例大小可能在实时范围的数量上是二次的。图形寄存器分配的传统表述隐含地假设了一个非重叠的通用寄存器的单个银行，并且不处理不规则的建筑特征，例如重叠寄存器对，特殊用途寄存器和多个寄存器银行。

Briggs等人发现了后来改进Chaitin风格的图形色彩方法：这被称为保守的合并。这种改进增加了一个标准，可以决定何时可以合并两个实时范围。主要是，除了非交流要求之外，只有两个变量才能合并，如果它们的合并不会导致进一步的溢出。 Briggs等。引入了Chaitin的作品的第二个改进，这种作品具有偏见的着色。偏见的着色试图将图形色素中的相同颜色分配给与复制相关的实时范围。

线性扫描

线性扫描是另一种全局寄存器分配方法。它是由Poletto等人提出的。在1999年。在这种方法中，代码没有变成图形。取而代之的是，所有变量均已线性扫描以确定其活范围，表示为间隔。一旦弄清楚所有变量的实时范围，时间就会按时间顺序遍历。尽管这种遍历可以帮助识别现场范围干扰的变量，但没有构建干扰图，并且变量以贪婪的方式分配。

这种方法的动机是速度。在生成代码的执行时间方面，而是在代码生成中所花费的时间。通常，标准的图形着色方法会产生质量代码，但具有明显的开销，使用的图形着色算法具有二次成本。由于此功能，线性扫描是当前在多个JIT编译器中使用的方法，例如Hotspot Client Compiler ， V8 ， Jikes RVM和Android Runtime（ART）。 Hotspot服务器编译器为其出色代码使用图形着色。

虚拟程式码

这描述了Poletto等人首先提出的算法，其中：

r是可用寄存器的数量。
Active是列表，按增加终点的顺序排序，实时间隔重叠当前点并放置在寄存器中。

LinearScanRegisterAllocation
    active ← {}
    for each live interval i, in order of increasing start point do
        ExpireOldIntervals(i)
        if length(active) = R then
            SpillAtInterval(i)
        else
            register[i] ← a register removed from pool of free registers
            add i to active, sorted by increasing end point
ExpireOldIntervals(i)
    for each interval j in active, in order of increasing end point do
        if endpoint[j] ≥ startpoint[i] then
            return 
        remove j from active
        add register[j] to pool of free registers
SpillAtInterval(i)
    spill ← last interval in active
    if endpoint[spill] > endpoint[i] then
        register[i] ← register[spill]
        location[spill] ← new stack location
        remove spill from active
        add i to active, sorted by increasing end point
    else
        location[i] ← new stack location

缺点和进一步的改进

但是，线性扫描显示两个主要缺点。首先，由于其贪婪的方面，它不考虑终身孔，即“不需要变量的值的范围”。此外，溢出的变量将在整个一生中溢出。

许多其他研究作品都在Poletto的线性扫描算法中进行了跟进。例如，Traub等人提出了一种称为第二次最终binpacking的算法，旨在生成质量更高的代码。在这种方法中，通过使用与标准线性扫描算法中使用的启发式不同的启发式方法，溢出的变量有机会在后来存储在寄存器中。该算法不使用实时间隔，而是依赖实时范围，这意味着如果需要溢出一个范围，则无需溢出与此变量相对应的所有其他范围。

线性扫描分配也适用于从SSA形式中利用：此中间表示的属性简化了分配算法，并允许直接计算生命周期。首先，旨在构建寿命间隔的数据流图分析所花费的时间减少，即由于变量是唯一的。因此，它会产生较短的实时间隔，因为每个新作业都对应于新的实时间隔。为了避免建模间隔和透明孔，罗杰斯展示了一种称为未来活性集的简化，该集合成功地删除了80％的说明的间隔。

重新布置

合并

在寄存器分配的背景下，合并是通过将这两个变量分配到同一位置来合并可变量到变量的移动操作的行为。合并操作发生在构建干扰图后进行。一旦两个节点结合在一起，一旦复制操作变得不必要，它们就必须获得相同的颜色并分配给同一寄存器。

进行合并可能会对干扰图的色彩能力产生正面和负面影响。例如，合并对图推断可着色性可能产生的负面影响是，当两个节点合并时，结果节点将与被聚集的边缘结合在一起。例如，当节点干扰两个节点合并时，合并对推理图形可着色的积极影响是通过一个节点降低的，从而降低了该节点的程度，从而改善了干扰图的整体色彩。

有几种可融合的启发式方法：

积极的结合: 它首先是由Chaitin原始寄存器分配器引入的。这种启发式旨在融合任何与副本相关的任何无关的节点。从消除复制的角度来看，这种启发式措施具有最好的结果。另一方面，侵略性结合可能会影响推理图的可着色性。
保守的合并: 它主要使用与侵略性聚结一样的启发式启发式，但仅当它不损害干涉图的可着色性时，它才会移动。
迭代合并: 它当时删除了一个特定的动作，同时保持图形的可着色性。
乐观的合并: 它基于侵略性的聚结，但是如果推论图可着色性损害，则它放弃了尽可能少的动作。

混合方法

混合分配

其他一些寄存器分配方法不限制一种技术来优化寄存器的使用。例如，Cavazos等人提出了一个解决方案，可以同时使用线性扫描和图形颜色算法。在这种方法中，一个或另一种解决方案之间的选择是动态确定的：首先，使用机器学习算法“离线”，即在运行时不在运行时，构建一个启发式函数，以确定需要使用哪种分配算法。然后在运行时使用启发式功能；鉴于代码行为，分配器可以在两种可用算法之一之间进行选择。

跟踪寄存器分配是Eisl等人最近开发的一种方法。该技术在本地处理分配：它依赖于动态分析数据来确定哪些分支将是给定控制流图中最常使用的分支。然后，它会删除一组“痕迹”（即代码段），其中合并点被忽略了，而不是最常用的分支。然后，分配器独立处理每个迹线。该方法可以视为混合动力，因为可以在不同轨迹之间使用不同的寄存器分配算法。

分配分配

分配分配是另一个结合不同方法的寄存器分配技术，通常被认为是相反的。例如，由于第一个启发式构建阶段是离线执行的，因此可以将混合分配技术视为拆分，并且启发式使用是在线执行的。 B. Diouf等人以同样的方式。提出了一种依赖于离线和在线行为的分配技术，即静态和动态汇编。在离线阶段，首先使用整数线性编程收集最佳溢出套件。然后，使用 compressAnnotation 依赖于先前确定的最佳溢出集的算法。根据离线阶段收集的数据，在线阶段将执行寄存器分配。

2007年，Bouchez等。也建议在不同阶段分配寄存器分配，具有一个专门用于溢出的一个阶段，并致力于着色和合并。

不同技术之间的比较

几个指标已用于评估一种寄存器分配技术对另一种寄存器的性能。注册分配通常具有处理代码质量（即迅速执行的代码）之间的权衡，并分析开销，即确定分析源代码以生成使用优化寄存器分配的代码所花费的时间。从这个角度来看，生成的代码和LIVICE分析所花费的时间的执行时间是比较不同技术的相关指标。

一旦选择了相关的指标，应通过反映现实世界应用的行为，或与算法想要解决的特定问题相关，应通过反映现实世界应用的行为来应用并与问题相关的指标。有关寄存器分配使用的最新文章，尤其是DACAPO基准套件。

也可以看看

Strahler编号，评估表达树所需的最小寄存器数量。
寄存器（关键字），C和C ++中的提示，以将变量放在寄存器中。
SETHI – Ullman算法，一种算法，用于产生最有效的寄存器分配，以评估单个表达式时，当评估表达式所需的寄存器数量超过了可用寄存器的数量。