跳转至

Register Allocation

约 3181 个字 预计阅读时间 16 分钟

在上一章中,我们成功根据活跃性分析的结果,构造出了冲突图.在这里,我们要学习的就是如何利用冲突图,完成寄存器分配.

我们知道,寄存器分配实际上是一个图着色问题.这个问题是NPC的,所以我们利用一个近似算法来解决.

Coloring by Simplification

该算法分为四步:

  1. Build
  2. Simplify

  3. Spill

  4. Select

Build

这一步没什么好说的,就是根据活跃度分析构造冲突图

Simplify

考虑有\(k\)个寄存器可用,也就是我们可以用\(k\)种颜色给冲突图着色.如果图中存在度数小于\(k\)的节点,那么该节点肯定可以被着色.

核心原理

对于任意度数小于 \(k\) 的节点 \(v\)：

  1. 我们可以安全地将其从冲突图中移除，并推入一个专门的栈（Stack）中。

  2. 如果剩下的子图 \(G' = G - \{v\}\) 是可 \(k\)-着色的，那么当最后把 \(v\) 从栈中弹出并重建时，由于它在图中的邻居数小于 \(k\)，即便它的邻居都已经着色完毕，也必然至少剩有一种颜色可以安全地分配给 \(v\)。

Simplify 具体步骤

我们通过以下迭代步骤来不断简化冲突图：

  • 第一步：寻找与压栈
    在冲突图中寻找一个度数小于 \(k\) 的节点，将其及其所有关联的边从图中移除，并将该节点压入栈中。

  • 第二步：更新邻居度数
    删除节点后，与其相连的邻居节点的度数均会减 1。这可能会使原本度数 \(\ge k\) 的节点度数降到 \(k\) 以下，变成新的可简化节点。

  • 第三步：循环至分支点
    重复上述步骤，直到：

    • 图被完全简化为空：说明整个图是可 \(k\)-着色的，直接进入 Select 阶段。
    • 图未空但所有剩余节点度数均 \(\ge k\)：无法继续简化，算法被迫进入 Spill 阶段。

Spill

Spill 核心原理

如果所有剩余节点的度数均 \(\ge k\)，那么我们必须选择一个节点“牺牲”并移出图，以便继续 Simplify，为其他节点腾出空间。

关键点：选择 Spill Candidate 不等于最后一定真的 Spill

这是一种乐观（Optimistic）的简化假设。我们现在只是乐观地假定它未来会放到内存中（因此它暂时不占用寄存器），然后将它从冲突图中移除并压栈，以降低其邻居的度数，从而使 Simplify 能够继续进行下去。

正如 Briggs 改进版算法中的名言所说：

Do we really have to do that? Not always.

当后续进入反向弹栈（Select）阶段真正开始分配寄存器颜色时：

  • 乐观成功（没有真正 Spill）：如果该节点被弹出并重建时，由于其邻居节点可能共用了同一种颜色，导致 \(k\) 个物理寄存器并没有被占满，那么它依然能找到一个可用寄存器，此时它就免于了真正 Spill 的命运。
  • 被迫溢出（真正 Spill）：只有当它被弹出时，发现所有的 \(k\) 个寄存器真的都被它的邻居们占满了，它才不得不真正分配到内存里。

真实溢出的开销

一旦一个变量最终被迫发生了真实 Spill，编译器必须改写中间代码。在原来使用该变量的位置，插入与内存交互的访问指令：

  • 读取前：在使用该变量前，先将其从内存 load 到一个临时寄存器中。
  • 修改后：在修改该变量的值后，立即 store 写回内存。

由于内存访问的速度远慢于寄存器，且插入了大量的 load / store 额外指令，因此 Spill 的代价非常高昂。

Select

在这一步中,我们重建冲突图并为每个节点分配寄存器颜色,依次将节点从栈中弹出（Pop）并放回图中进行染色。

节点的两种弹出情况

当节点从栈中被弹出并重新放回冲突图时，根据其在 Simplify 阶段被压栈的缘由，分为两类情况：

  • 普通的 Simplified 节点
    如果该节点是因为度数小于 \(k\) 而被压栈的，那么当它被弹出并重新加入冲突图时，必定能够为其分配到一个可用的颜色（。
  • 潜在溢出的 Spill 候选节点
    如果是作为度数大于等于 \(k\) 的潜在溢出节点 \(n\)（Spill Candidate）被压栈的，当它弹出并被重新放回图里时，无法保证它一定是可以染色的。

对于 Spill 候选节点 \(n\)，我们需要检查它在图中已被染色的邻居节点：

  • 结局一：发生实际溢出（Actual Spill）
    如果 \(n\) 的邻居已经占用了全部 \(k\) 种不同的颜色，那么 \(n\) 将无法被着色。我们将其判定为实际溢出（Actual Spill）。在这一步中不为其分配任何颜色，但需要继续完成 Select 阶段，以便找出可能存在的其他实际溢出节点。
  • 结局二：乐观着色成功（Optimistic Coloring）
    如果 \(n\) 的邻居所染的不同颜色数量小于 \(k\)（即使 \(n\) 在原图里的度数可能很大，但部分邻居共用了同一种颜色），那么我们依然可以为 \(n\) 选择一个未被其邻居占用的空闲颜色。此时 \(n\) 就避免了被真正溢出，这种技术被称为乐观着色（Optimistic Coloring）。

Coalescing

Coalescing（寄存器合并 / 节点合并） 是一种用于消除多余MOVE的关键优化技术。

合并的核心原理

如果一条传送指令（MOVE）的源操作数（Source）和目的操作数（Destination）在冲突图中没有冲突边（No edge）：

我们可以安全地直接消除这条 MOVE 指令,并将源节点和目的节点合并为一个新节点。

这样两个临时变量将共用同一个物理寄存器，使得原本的传送操作变成了一个自赋值的空操作（如 r <- r），在后续代码生成中被彻底省去，从而减少了指令数量并加快了程序运行速度。

新节点连接规则

当源节点和目的节点被合并后，它们在冲突图中的表示会融合成一个单一的综合节点。这个新节点的冲突边集合，是原本被替换的两个节点的冲突边集合的并集（Union）。

\[\text{Edges}(\text{Coalesced Node}) = \text{Edges}(\text{Source}) \cup \text{Edges}(\text{Destination})\]

这意味着，任何原本与源节点冲突的节点，或者与目的节点冲突的节点，都将与合并后的新节点发生冲突。

然而,Coalescing听上去很美好,但是reckless的Coalescing可能会导致原来可着色的冲突图反而无法着色.

因此,我们希望回答一个问题,什么样的Coalescing是safe的呢?

下面,我们将介绍两个充分不必要的条件:

  • Briggs

  • George

这意味着满足这两个条件中的一个的Coalescing是safe的,但是都不满足的不一定是unsafe的.

Briggs

节点a和b通过move指令形成关联,如果它们合并后的节点有少于\(K\)个重要节点的邻居,那么它们可以合并

所谓重要节点(Significant Node),也就是度数大于等于\(K\)的节点.

George

a和b可以合并,当对于a的每个邻居t,满足:

  • t同样也是b的邻居

  • 或者,t不是重要节点

在引入了Coalescing后,我们必须重新介绍图着色的过程.

Note

  1. Build： 构造冲突图，并把节点分为两类：

    • Move-related：跟某个 MOVE 指令相关的节点（即是 MOVE 的源或目的操作数）。

    • Non-move-related：普通的、不涉及任何 MOVE 的节点。

  2. Simplify： 每次挑一个度数 \(< K\) 的 Non-move-related 节点从图里删掉，并压入栈中。（注意：此处不会碰 Move-related 节点，留给后面 Coalesce 去尝试合并。）

  3. Coalesce： 对 Simplify 之后的图尝试进行保守合并。若合并成功，对应的 MOVE 指令被安全消除。 合并出的新节点若不再涉及其他 MOVE，它就退化为 Non-move-related 节点，可以重新参与 Simplify。 Simplify 和 Coalesce 交替往复运行，直到图里只剩下度数 \(\ge K\) 的节点或 Move-related 节点。

  4. Freeze： 如果 Simplify 和 Coalesce 均无法继续推进（陷入僵局），就寻找一个度数 \(< K\) 的 Move-related 节点，冻结所有与之关联的 MOVE 指令（即彻底放弃合并这些 MOVE 的希望）。这些被冻结的节点自此被视为一般的 Non-move-related 节点，随后重新恢复 Simplify 和 Coalesce 的迭代。

  5. Spill： 如果图里所有剩余节点度数都 \(\ge K\)，我们只能挑选一个度数较大的节点作为 Spill Candidate，将其移出图并压栈，以此降低其邻居节点的度数，好让 Simplify 能够继续。

  6. Select： 按相反顺序弹栈并尝试为节点上色。 如果弹出来的 Spill Candidate 在放回图里时，发现其所有邻居已经占满了全部 \(K\) 种寄存器颜色，则发生 Actual Spill。此时不为其分配颜色，但在 Select 阶段结束后改写代码（插入 load/store 内存访问指令），并重新构建冲突图从头开始跑整个算法。

Precolored Nodes

前面讨论的节点大多是普通临时变量,它们最后染成哪个颜色都可以.但真实机器里有一批寄存器不能这么随便处理:比如参数寄存器、返回值寄存器、栈指针、帧指针等.这些寄存器在调用约定里已经有固定含义,所以在冲突图里会先放入一批已经染好颜色的节点,这就是 Precolored Nodes.

预着色节点需要注意的地方

预着色节点可以理解成“已经分配好的物理寄存器节点”.

  • 每个物理寄存器对应一个预着色节点.

  • 不同物理寄存器不能分配成同一个寄存器,所以这些预着色节点之间要两两连边.

  • 它们不能被 Simplify 删除,也不能被 Spill 到内存.

  • 普通临时变量仍然可以使用这些颜色,前提是它不和对应的预着色节点冲突.

因此,Simplify/Coalesce/Spill 实际上是在处理那些尚未确定位置的普通节点.等普通节点都被压栈或处理完之后,图中自然会剩下这些已经固定颜色的预着色节点.

一个容易出问题的点是:预着色节点不能 spill,所以不能让它们的 live range 变得太长.常见做法是在需要使用特殊寄存器的边界处插入 MOVE,尽快把值搬到普通临时变量里.这样后面的图着色器还有选择空间:

  • 如果寄存器压力不大,这个普通临时变量可以和对应的预着色节点 Coalesce,MOVE 最后会被消掉.
  • 如果寄存器压力很大,spill 的会是普通临时变量,而不是机器规定必须存在的物理寄存器.

例如 r7 是一个 callee-save 寄存器.编译器可能在函数入口生成一个临时变量 t231 来保存 r7 的旧值,在函数出口再把它恢复回去.如果压力小,t231 和 r7 可以合并;如果压力大,真正被拿去 spill 的也只能是 t231,不能是 r7 本身.

Caller-Save 和 Callee-Save

对不跨越函数调用的变量,放进 caller-save 寄存器通常更合适.因为调用发生时这个变量已经不活跃了,不需要额外保存.

对跨越函数调用的变量,更希望放进 callee-save 寄存器.否则每次调用前后都要由 caller 负责保存和恢复,代价会比较高.

但这也会改变冲突图.假设变量 \(x\) 在一次函数调用前后都活跃:

  1. \(x\) 会和所有 caller-save 的预着色节点冲突,因为调用可能破坏这些寄存器.
  2. 如果为了保护 callee-save 寄存器引入了类似 t231 的保存临时变量,\(x\) 也可能和这些临时变量冲突.
  3. 于是 \(x\) 的度数会明显变大,更容易被选成 spill candidate.

评论