概述图着色寄存器分配算法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–v3v2–v3, v2–v4v3–v5v4–v5, v4–v6v5–v6节点度数v1:2v2:3,v3:3v4:3v5:3v6: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 的度数为 2v2 和 v5v5 度数降为 2v3 和 v46v2 度数降为 2v1 和 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可分配 R2R2 与 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 → R3v2 → R1v3 → R2v46 (即原 v4,v6) → R2v5 → 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)总结图着色寄存器分配通过将虚拟寄存器映射为物理寄存器利用冲突图进行全局优化。其关键步骤包括构造冲突图记录无法共享同一物理寄存器的节点对。接合合并移动指令相关节点减少复制。简化与溢出反复移除低度数节点若无则选择节点溢出。选择为节点分配颜色若失败则实际溢出并重新分配。
图着色寄存器分配算法（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–v3v2–v3, v2–v4v3–v5v4–v5, v4–v6v5–v6节点度数v1:2v2:3,v3:3v4:3v5:3v6: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 的度数为 2v2 和 v5v5 度数降为 2v3 和 v46v2 度数降为 2v1 和 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可分配 R2R2 与 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 → R3v2 → R1v3 → R2v46 (即原 v4,v6) → R2v5 → 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)总结图着色寄存器分配通过将虚拟寄存器映射为物理寄存器利用冲突图进行全局优化。其关键步骤包括构造冲突图记录无法共享同一物理寄存器的节点对。接合合并移动指令相关节点减少复制。简化与溢出反复移除低度数节点若无则选择节点溢出。选择为节点分配颜色若失败则实际溢出并重新分配。
