Register Allocation⚓︎

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

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

实现方法：

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

Coloring by Simplification⚓︎

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

• 构建(build) 干扰图（通过活跃性分析）：
  • 每个节点代表一个临时值
  • 边 (t1, t2) 表示一对不能分配到同一寄存器的临时值，最常见的原因是 t1 和 t2 同时活跃

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

  

  

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

• 溢出(spill)：在简化过程中的某个时刻，图 G 仅包含具有度数较大的节点（即度 >= K 的节点）

  
  • 我们在图中选择某个节点，并决定在程序执行期间将其表示在内存中，而非寄存器中
  • 但不一定要这么做
  • 对溢出效果的一种乐观近似：被溢出的节点不会与图中剩余的任何其他节点产生冲突
  • 因此这些节点可以被移除并压入栈中，简化过程继续进行

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

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

如果选择阶段无法为某些节点找到颜色，则必须重写程序，以便在每次使用前从内存中加载（LOAD）它们，并在每次定义后将其存回（STORE）。因此，一个溢出的临时变量将变成若干个具有极小活跃范围的新临时变量，这些新临时变量可能与图中其他临时变量发生冲突。所以需在此重写后的程序上重复该算法。此过程迭代进行，直到简化成功且不再出现溢出。实践中通常一两次迭代就足够了。

例子

Coalescing⚓︎

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

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

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

• Briggs

  • 节点 a 和 b 可以被合并，如果合并后的节点 ab 具有少于 K 个的大度数的邻居（即具有 ≥ K 条边）
  • 这种合并保证不会将一个 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。将它们移除后，得到：

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

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

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

Precolored Nodes⚓︎

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

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

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

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

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

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

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

例子

评论区