Register Allocation⚓︎

寄存器分配器(register allocator) 的任务是将众多的临时变量分配给少量的寄存器。

• 将 MOVE 指令的源和目标分配到同一寄存器，以便删除该 MOVE 指令

实现方法：

• （通过活跃性分析）推导干扰图(interference graph)
• 对干扰图进行着色(color)，每个颜色对应一个寄存器，并确保两个相邻节点不同色

Coloring by Simplification⚓︎

因为图着色是 NP 完全问题，所以寄存器分配也是 NP 完全问题。不过利用线性时间的近似算法也能产生不错的结果，该算法分为以下几个阶段：

1. 构建(build) 干扰图（通过活跃性分析）：

   

   • 每个节点代表一个临时值
   • 边 (t1, t2) 表示一对不能分配到同一寄存器的临时值，最常见的原因是 t1 和 t2 同时活跃

2. 简化(simplify)：使用简单的启发式方法 (heuristic) 为图着色（假设有 K 个寄存器）

   
   • 移除邻居数 < K 的节点 b，得到图 G'
   • 如果 G' 可以用 K 种颜色着色，那么 G 也可以（因为 b 的邻居数 < K，b 不会采用 K 个颜色之外的颜色）
   • 这自然引出了一种基于栈（或递归）的着色算法：
     • 反复移除（并压入栈）度数小于 K 的节点
     • 每次这样的简化会降低其他节点的度数，从而带来更多简化的机会

3. 溢出(spill)：在简化过程中的某个时刻，图 G 所有节点的度数均很大（度数 >= K）

   
   • 此时在图中随机（并不一定）选择某个节点，该节点需存储在内存（可以直接放在当前栈帧中）而非寄存器中
   • 一种乐观近似：被溢出的节点不会与图中剩余的任何其他节点产生冲突，因此剩下的节点可以继续被移除并压入栈中，简化过程可以继续进行
   • 为了在选择阶段为被溢出的节点上色，需要重写程序：每次使用（读取）前从内存中加载（LOAD）它们，并在每次定义（写入）后将其存回（STORE）
   • 可能的溢出节点选择的启发式策略：
     • 溢出冲突最多的临时变量
     • 溢出定义和使用较少的临时变量
     • 避免内层循环的溢出
   例子

   假如只有 3 个寄存器。在简化过程中，干扰图的情况如下所示。可以看到 f 有 4 个邻居，因此需要将其溢出。

   

   重写后的程序：

   

   虽然复用相同的寄存器 f 是 OK 的，但这并不是最优的。更好的做法是尽量采用不同的寄存器名，因为可以用到不同的颜色。溢出后，更新后的活跃性信息如下所示：

   

   可以看到，f 的活跃范围被划分为若干个更小的范围，从而降低干扰，减少图中的邻居数。新的干扰图如下：

   

4. 选择(select)：重建图并为节点分配颜色

   • 当我们在图中添加一个简化节点时，必须为其分配一种颜色
   • 当通过溢出启发式算法被推入潜在溢出节点 n 被弹出时，无法保证它是可着色的
   • 如果 n 的邻居已经被 K 种不同颜色着色，则发生实际溢出(actual spill)，此时不分配任何颜色，而是继续选择阶段以识别其他的实际溢出
   • 如果 n 的邻居被少于 K 种颜色着色，我们可以为 n 着色，且不会发生实际溢出，这种技术被称为乐观着色(optimistic coloring)

例子

例 1 例 2

没有涉及到溢出步骤的简单情况：

<div align=center markdown>

![type:video](images/C1/15.mp4){: style='width: 80%'}

</div>

Coalescing⚓︎

如果 MOVE 指令的源和目标之间在干扰图中没有边，那么该 MOVE 指令可以被消除。源和目标节点合并(coalesce) 为一个新节点，其边是所替换节点边的并集。

被引入的节点比被移除的节点受到更多限制，因为它包含了边的并集。在合并前可用 K 种颜色着色的图，但若合并不当，可能无法继续 K- 着色了。

我们希望仅在安全的条件下进行合并，即合并不会导致图不可着色。以下两种策略都是安全的：

• Briggs：节点 a 和 b 可以被合并，如果合并后的节点 ab 的大度数（边数 >= K）邻居个数 < K

  • 简化阶段会从图中移除所有小度数的节点
  • 合并后的节点将仅与那些具有大度数的邻居相邻
  • 少于 K 个大度数的邻居 => 简化阶段可以将合并后的节点从图中移除

• George

  • 如果对于节点 a 的每个邻居 t，t 已经与 b 冲突或 t 的度数不大，则节点 a 和 b 可以合并
  • 这种合并是安全的原因：
    • 如果 t 已经与 b 冲突，那么 (a, t) 和 (b, t) 将合并为 (ab, t)，不会导致度的增加
    • 如果 t 的度数不大，那么 t 将在简化阶段被移除，也不会导致度的增加

考虑合并操作后，着色步骤也要进行调整：

合并、简化和溢出过程应交替进行，直到图为空

1. 构建：

   • 构造干扰图
   • 将每个节点分类为与移动相关或与移动无关，其中与移动相关的节点是指作为 MOVE 指令的源或目的地的节点

2. 简化：每次从图中移除一个小度数（小于 K）且与移动无关的节点

3. 合并(coalesce)：

   • 对简化后的图执行保守合并
   • 合并后的节点不再是移动相关的，并且将可用于下一轮简化
   • 重复简化和合并步骤，直到只剩下大度数或移动相关的节点

4. 固定(freeze)：

   • 如果既不能简化也不能合并，我们就寻找一个小度数的移动相关节点，并定住与该节点相关的移动

     • 我们放弃合并这些移动的希望
     • 这些节点被视为非移动相关节点

   • 简化与合并操作继续进行

5. 溢出：若没有小度数节点，则选择一个大度数节点作为潜在的溢出对象，并将其压入栈中

6. 选择：
   • 弹出整个栈，分配颜色
   • 如果有实际溢出，则重建图

例子

接着前面的例子，其中节点 b、c、d 和 j 是仅有的与移动相关的节点。简化阶段使用的初始工作列表必须只包含非移动相关的节点（K=4），即 f, g, h。将 g, h, k 移除后，得到：

如果此时调用一轮合并，不难发现 c 和 d 确实是可合并的（K=4）

另外还可以将 b 和 j 合并。之后就没有更多的移动相关节点了，因此不能再进行合并了。

简化阶段可以再调用一次，以移除所有剩余的节点。一种可能的颜色分配如下所示：

Precolored Nodes⚓︎

有些寄存器用于特殊用途，比如参数寄存器、帧指针、返回值寄存器等。对于每个此类寄存器，使用永久绑定到该寄存器的特定临时变量（例如 FP），而这些临时变量是预着色的(precolored)。

• 每种颜色只有一个预着色节点
• 所有预着色节点彼此冲突

通常，只要普通临时变量与预着色寄存器不冲突，就可以赋予其与预着色寄存器相同的颜色。标准调用约定的寄存器可以在过程内部作为临时变量重用。因此我们不能简化预着色节点，也不应将预着色节点溢出到内存。

着色算法通过调用简化、合并和溢出操作，直到只剩下预着色节点为止。由于预着色节点不会溢出，前端必须小心地保持它们的活跃范围较短：通过生成 MOVE 指令来在预着色节点之间移动值。

假设 r7 是一个被调用者保存的寄存器：

如果此函数中存在寄存器压力（即对寄存器的高需求），则 t231 将会溢出；否则，t231 将与 r7 合并，并且 MOVE 指令将被消除。

1
2
3
4
5
6
7
8

foo() {
    t = ...
    ... = ... t ...
    s = ...
    f()
    g()
    ... = ... s ...
}

如果一个变量 x 在过程调用期间处于活跃状态，那么它将与所有调用者保存（预着色）寄存器冲突，并且与为被调用者保存寄存器创建的所有新临时变量（例如 t231）冲突，因此溢出发生。使用常见的溢出代价启发式方法，即溢出度数高但使用次数少的节点。

例子

评论区