图着色寄存器分配算法（Graph Coloring）

概述

图着色寄存器分配算法（Graph Coloring）是编译器后端将无限虚拟寄存器映射到有限物理寄存器的经典方法。

下面通过一个完整的例子，展示该算法中的构造冲突图、接合（Coalescing）、简化（Simplify）、溢出（Spill）、选择（Select）等关键步骤。

示例设定

物理寄存器数量：K = 3（例如：R1, R2, R3）

虚拟寄存器集合：v1, v2, v3, v4, v5, v6

冲突关系(两个虚拟寄存器不能使用同一物理寄存器)

• v1 与 v2、v3 冲突
• v2 与 v1、v3、v4 冲突
• v3 与 v1、v2、v5 冲突
• v4 与 v2、v5、v6 冲突
• v5 与 v3、v4、v6 冲突
• v6 与 v4、v5 冲突

移动指令：假设存在v6 = v4（表示 v6 由 v4 复制而来，在接合阶段可以考虑合并）

阶段1：构造冲突图

每个虚拟寄存器为节点，冲突为无向边。初始图如下（ASCII 表示）：

v1 / \ v2--v3 | | v4--v5 \ / v6

边集：

• v1–v2, v1–v3
• v2–v3, v2–v4
• v3–v5
• v4–v5, v4–v6
• v5–v6

节点度数：

• v1:2
• v2:3,
• v3:3
• v4:3
• v5:3
• v6:2

阶段2：接合(Coalescing)

接合的目的是合并移动指令中相关联的节点（例如v6 = v4），从而消除不必要的复制。

合并前需要检查合并后的节点是否会违反 K 可着色性（即合并后图中是否会出现度数 ≥ K 的节点过多导致溢出风险）。

这里我们采用 Briggs 保守合并策略：合并后新节点的邻居数 < K 才允许合并。

合并v4和v6（因为存在移动指令v6 = v4）：

• 原 v4 的邻居：v2, v5, v6
• 原 v6 的邻居：v4, v5
  合并后新节点v46的邻居为 {v2, v5}（去重），度数为 2 < K = 3，因此可以安全合并。

合并图变为:

v1 / \ v2--v3 | v46--v5

其中 v46 的度数为 2（v2 和 v5），v5 度数降为 2（v3 和 v46），v2 度数降为 2（v1 和 v46）。

阶段3：简化(Simplify)

反复移除度数 < K 的节点并压入栈，直到图为空或剩余节点度数均 ≥ K。

第1轮：度数 < 3 的节点有 v1(2), v46(2), v5(2), v2(2), v3(2) —— 全部小于3。

任选一个移除，例如移除 v1：

• 移除 v1，压栈 [v1]；邻边删除，v2 度数降为 1（只剩 v46）。

第2轮：剩余节点 v2(1), v3(2), v46(2), v5(2) — 全部 ❤️。

移除 v2：

• 压栈 [v1, v2]；删除 v2 后，v46 度数降为 1（只剩 v5）

第3轮：剩余 v3(2), v46(1), v5(2) — 全部 ❤️。

移除 v3：

• 压栈 [v1, v2, v3]；v5 度数降为 1（只剩 v46）

第4轮：剩余 v46(1), v5(1) — 全部 ❤️。

移除 v46：

• 压栈 [v1, v2, v3, v46]；v5 度数降为 0。

第5轮：移除 v5：

• 压栈 [v1, v2, v3, v46, v5]

所有节点均已移除，没有发生溢出。

阶段4：选择（Select）

从栈中依次弹出节点，尝试分配一个不同于其所有邻居颜色的物理寄存器（颜色）。假设物理寄存器为 R1、R2、R3。

弹出 v5：邻居已分配集合为空 → 分配 R1。

弹出 v46：邻居有 v5(R1) → 可分配 R2。

弹出 v3：邻居有 v1(未分配), v2(未分配), v5(R1) → 避开 R1，可分配 R2（R2 与 v46 不冲突，但 v3 与 v46 无直接边，且 v46 不在邻居中），实际邻居只有 v5(R1)，所以分配 R2 或 R3。我们选 R2。

弹出 v2：邻居有 v1(未分配), v46(R2) → 避开 R2，可分配 R1（或 R3）。

弹出 v1：邻居有 v2(R1), v3(R2) → 避开 R1,R2，只能分配 R3。

最终分配结果：

• v1 → R3
• v2 → R1
• v3 → R2
• v46 (即原 v4,v6) → R2
• v5 → R1

阶段5：溢出（Spill）示例

假设我们未使用接合，且初始图中存在无法简化的节点（例如增加冲突使图无法 3-着色）。

为了展示溢出，我们修改冲突：增加一条边 v2–v5，使图更密集。

新图：

v1 / \ v2--v3 |\ | | \ | v4--v5 \ / v6

此时度数：v1:2, v2:4, v3:3, v4:3, v5:4, v6:2。

简化过程：

• 可移除 v1（度2）和 v6（度2），压栈。
• 剩余 v2(4), v3(3), v4(3), v5(4) — 全部 ≥3，无法继续简化，需要选择一个节点溢出（即将其值保存在内存中，后续用加载/存储代替）。

选择溢出节点（通常选度数高、估算溢出代价小的），例如 v2。

将 v2 标记为溢出，并从图中移除（假设其值不再参与冲突）。移除 v2 后，剩余节点度数可能降低，继续简化。

溢出节点的处理是图着色算法的核心：如果选择阶段无法给该节点分配颜色，就真正将其溢出，并在代码中插入加载/存储，然后重新进行整个分配过程。

阶段6：接合与溢出的关系

接合可以合并移动指令，减少节点数量，但也可能增加节点度数，导致原本可着色的图变得不可着色。

因此保守的接合策略（如Briggs）只在合并后新节点度数 < K 时才执行，以避免引入溢出。

图示汇总(文本版)

初始冲突图

v1 / \ v2---v3 | | v4---v5 \ / v6

接合后(合并v4 合 v6)

v1 / \ v2---v3 \ v46---v5

简化过程(移除顺序)

• 移除 v1 → 剩余 v2,v3,v46,v5
• 移除 v2 → 剩余 v3,v46,v5
• 移除 v3 → 剩余 v46,v5
• 移除 v46 → 剩余 v5
• 移除 v5 → 栈：[v1, v2, v3, v46, v5]

选择过程(颜色分配)

• 弹出 v5 → R1
• 弹出 v46 → R2
• 弹出 v3 → R2（与 v5 冲突，但与 v46 不冲突）
• 弹出 v2 → R1（避开 v46 的 R2）
• 弹出 v1 → R3（避开 v2 的 R1 和 v3 的 R2）

最终着色图（节点旁标注颜色）：

v1(R3) / \ v2(R1) v3(R2) \ v46(R2)---v5(R1)

总结

图着色寄存器分配通过将虚拟寄存器映射为物理寄存器，利用冲突图进行全局优化。

其关键步骤包括：

• 构造冲突图：记录无法共享同一物理寄存器的节点对。
• 接合：合并移动指令相关节点，减少复制。
• 简化与溢出：反复移除低度数节点，若无则选择节点溢出。
• 选择：为节点分配颜色，若失败则实际溢出并重新分配。