图着色（graph coloring）是组合优化中最优美也最实用的问题之一。它的表述极其简洁——给图的每个顶点分配一种颜色，使得相邻顶点颜色不同——却在理论上属于 NP 完全。讽刺的是，你的编译器每秒都在解决这个”不可解”的问题：把无限多的虚拟寄存器映射到有限的物理寄存器上，本质就是给冲突图着色。
本文从数学定义出发，经过算法设计，一路走到编译器后端的工程实践。内容包括：色数与 NP 完全性证明思路、贪心着色与各种排序启发式、DSatur 算法、Welsh-Powell 算法、Chaitin 寄存器分配器的四个阶段、线性扫描分配、四色定理的历史、完整的 C 语言实现，以及现实世界中 LLVM 和 GCC 的做法。
一、图着色问题的形式定义
给定无向图 G = (V, E)，一个 k-着色 是映射 c: V -> {1, 2, …, k}，使得对所有边 (u, v)，都有 c(u) != c(v)。色数（chromatic number）记作 chi(G)，是使 G 可着色的最小 k 值。
几个基本事实：
- 完全图 K_n 的色数为 n。
- 二部图的色数为 2（若非空）。
- 奇数环的色数为 3。
- 树的色数为 2（若有边）。
- 空图的色数为 1。
- 对一般图，chi(G) <= Delta(G) + 1，其中 Delta 是最大度数（贪心上界）。
- Brooks 定理：若 G 既不是完全图也不是奇数环，则 chi(G) <= Delta(G)。
色数的精确计算是 NP 困难的。甚至判断一个图是否可以 3-着色都是 NP 完全的。
色数的层次结构：
chi(G) = 1 <=> G 没有边（空图）
chi(G) = 2 <=> G 是二部图
chi(G) = 3 <=> ? （NP 完全，需要 3-可着色判定）
chi(G) = k <=> ? （NP 困难，对 k >= 3）色多项式 P(G, k) 给出用 k 种颜色着色 G 的方案数。对于完全图 K_n：
P(K_n, k) = k * (k-1) * (k-2) * ... * (k-n+1)对于树 T_n（n 个顶点）：
P(T_n, k) = k * (k-1)^(n-1)色多项式的最小正整数根就是 chi(G)。但计算色多项式本身也是困难的。
二、NP 完全性与归约
图着色判定问题”给定 G 和 k，G 是否 k-可着色？“对 k >= 3 是 NP 完全的。证明的关键步骤：
属于 NP：给定一个着色方案，可以在多项式时间内验证——遍历所有边检查相邻顶点颜色是否不同。
NP 困难：通过从 3-SAT 归约到 3-着色来证明。构造思路如下：
3-SAT -> 3-Coloring 归约概要：
对每个变量 x_i，建立顶点 x_i 和 ~x_i，并连边（互斥）。
引入三个特殊顶点 T, F, B（True, False, Base），两两连边。
x_i 和 ~x_i 各自与 B 连边。
对每个子句 (l1 v l2 v l3)，构建一个 gadget 保证至少
一个文字被着 T 的颜色。
gadget 的关键性质：
- 若 l1, l2, l3 全被着 F 色，则 gadget 不可 3-着色。
- 若至少一个文字着 T 色，则 gadget 可 3-着色。这个归约是多项式时间的，因为 gadget 的大小是常数，总顶点数和边数与 3-SAT 实例的大小成线性关系。
推论：对 k >= 3，k-着色问题都是 NP 完全的（从 3-着色归约到 k-着色）。对 k = 2，只需判断图是否为二部图，BFS/DFS 即可在 O(V + E) 时间内完成。
复杂度景观：
1-着色：O(1) — 图没有边则可以
2-着色：O(V + E) — 二部图判定
3-着色：NP 完全
k-着色（k >= 3）：NP 完全
最优着色：NP 困难
近似着色：对一般图没有常数比近似（除非 P = NP）三、贪心着色与排序启发式
既然精确求解不可行，我们转向启发式。最简单的是贪心着色：按某个顺序遍历顶点，为每个顶点分配与其已着色邻居都不冲突的最小颜色编号。
// 贪心着色伪代码
for each vertex v in ordering:
used = { color[u] : u in adj[v] and u is colored }
color[v] = min{ c >= 0 : c not in used }贪心着色的质量高度依赖于顶点的遍历顺序。不同排序策略的效果差异巨大：
随机排序：最差情况可能用到 Delta(G) + 1 种颜色，平均表现不佳。
最大度数优先（Largest First / Welsh-Powell）：按度数从大到小排列顶点，优先着色约束最多的顶点。直觉是：高度数顶点的颜色选择余地小，应尽早确定。
最小末序（Smallest Last Ordering）：反复从图中移除度数最小的顶点，记录移除顺序，然后逆序着色。设移除第 i 个顶点时它的度数为 d_i，则贪心着色使用的颜色数不超过 max(d_i) + 1。
饱和度优先（DSatur）：动态策略——每次选择”饱和度”最高的未着色顶点。饱和度定义为该顶点已着色邻居中不同颜色的数量。饱和度相同时选度数大的。这是目前效果最好的单步启发式之一。
各策略的比较：
策略 时间复杂度 着色质量 适用场景
─────────────────────────────────────────────────────────
随机排序 O(V + E) 差 基线对比
最大度优先 O(V log V + E) 中等 稀疏图
最小末序 O(V + E) 较好 弦图上最优
DSatur O(V^2) 好 一般图
DSatur + 堆 O((V+E) log V) 好 大规模图一个关键定理：对于弦图（chordal graph），最小末序 + 贪心可以给出最优着色。弦图是指每个长度 >= 4 的环都有弦的图。许多实际的冲突图（如区间图）都是弦图或接近弦图。
四、DSatur 算法详解
DSatur（Degree of Saturation）由 Daniel Brelaz 于 1979 年提出。算法维护每个顶点的饱和度，动态选择下一个要着色的顶点。
DSatur 算法：
1. 初始化：所有顶点未着色，饱和度 = 0
2. 选择度数最大的顶点，着色为颜色 1
3. 重复直到所有顶点都着色：
a. 在未着色顶点中，选饱和度最高的（平局选度数最大的）
b. 为该顶点分配最小可用颜色
c. 更新其未着色邻居的饱和度DSatur 对二部图总是给出 2 色着色（最优）。对一般图不保证最优，但实践中表现优异。
下面给出完整的 C 语言实现。为了清晰，使用邻接矩阵表示，适合中等规模的图。
/* dsatur.c — DSatur 图着色算法的完整实现 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>
#define MAX_VERTICES 512
typedef struct {
int n; /* 顶点数 */
bool adj[MAX_VERTICES][MAX_VERTICES]; /* 邻接矩阵 */
} Graph;
typedef struct {
int color[MAX_VERTICES]; /* 着色结果，-1 表示未着色 */
int num_colors; /* 使用的颜色数 */
} ColorResult;
/* 初始化图 */
void graph_init(Graph *g, int n)
{
g->n = n;
memset(g->adj, 0, sizeof(g->adj));
}
/* 添加无向边 */
void graph_add_edge(Graph *g, int u, int v)
{
g->adj[u][v] = true;
g->adj[v][u] = true;
}
/* 计算顶点的度数 */
int degree(const Graph *g, int v)
{
int d = 0;
for (int i = 0; i < g->n; i++)
if (g->adj[v][i]) d++;
return d;
}
/* DSatur 着色 */
ColorResult dsatur(const Graph *g)
{
int n = g->n;
ColorResult res;
res.num_colors = 0;
memset(res.color, -1, sizeof(res.color));
/* saturation[v] = 顶点 v 的邻居中已使用的不同颜色数 */
int saturation[MAX_VERTICES];
memset(saturation, 0, sizeof(saturation));
/* neighbor_colors[v] 记录顶点 v 的邻居已经使用的颜色集合 */
bool neighbor_colors[MAX_VERTICES][MAX_VERTICES];
memset(neighbor_colors, 0, sizeof(neighbor_colors));
bool colored[MAX_VERTICES];
memset(colored, 0, sizeof(colored));
for (int step = 0; step < n; step++) {
/* 选择下一个要着色的顶点：饱和度最高，平局时度数最大 */
int best = -1;
int best_sat = -1, best_deg = -1;
for (int v = 0; v < n; v++) {
if (colored[v]) continue;
int s = saturation[v];
int d = degree(g, v);
if (s > best_sat || (s == best_sat && d > best_deg)) {
best = v;
best_sat = s;
best_deg = d;
}
}
/* 为 best 分配最小可用颜色 */
int c = 0;
while (neighbor_colors[best][c])
c++;
res.color[best] = c;
colored[best] = true;
if (c + 1 > res.num_colors)
res.num_colors = c + 1;
/* 更新邻居的饱和度 */
for (int u = 0; u < n; u++) {
if (!g->adj[best][u] || colored[u]) continue;
if (!neighbor_colors[u][c]) {
neighbor_colors[u][c] = true;
saturation[u]++;
}
}
}
return res;
}
/* 贪心着色（按自然序，用于对比基线） */
ColorResult greedy_natural(const Graph *g)
{
int n = g->n;
ColorResult res;
res.num_colors = 0;
memset(res.color, -1, sizeof(res.color));
for (int v = 0; v < n; v++) {
bool used[MAX_VERTICES];
memset(used, 0, sizeof(used));
for (int u = 0; u < n; u++)
if (g->adj[v][u] && res.color[u] >= 0)
used[res.color[u]] = true;
int c = 0;
while (used[c]) c++;
res.color[v] = c;
if (c + 1 > res.num_colors)
res.num_colors = c + 1;
}
return res;
}
/* 生成 Erdos-Renyi 随机图 G(n, p) */
void generate_random_graph(Graph *g, int n, double p)
{
graph_init(g, n);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if ((double)rand() / RAND_MAX < p)
graph_add_edge(g, i, j);
}
/* 验证着色合法性 */
bool verify_coloring(const Graph *g, const ColorResult *res)
{
for (int u = 0; u < g->n; u++)
for (int v = u + 1; v < g->n; v++)
if (g->adj[u][v] && res->color[u] == res->color[v])
return false;
return true;
}
/* 打印着色结果 */
void print_coloring(const Graph *g, const ColorResult *res)
{
printf("使用 %d 种颜色：\n", res->num_colors);
for (int v = 0; v < g->n; v++)
printf(" 顶点 %d -> 颜色 %d\n", v, res->color[v]);
printf("着色%s\n", verify_coloring(g, res) ? "合法" : "非法");
}
/* 基准测试：DSatur vs 贪心 */
void benchmark(int n, double p, int trials)
{
printf("\n=== 基准测试: n=%d, p=%.2f, trials=%d ===\n", n, p, trials);
double dsatur_avg = 0, greedy_avg = 0;
int dsatur_wins = 0, ties = 0;
for (int t = 0; t < trials; t++) {
Graph g;
generate_random_graph(&g, n, p);
ColorResult r1 = dsatur(&g);
ColorResult r2 = greedy_natural(&g);
dsatur_avg += r1.num_colors;
greedy_avg += r2.num_colors;
if (r1.num_colors < r2.num_colors) dsatur_wins++;
else if (r1.num_colors == r2.num_colors) ties++;
}
printf("DSatur 平均颜色数: %.2f\n", dsatur_avg / trials);
printf("贪心 平均颜色数: %.2f\n", greedy_avg / trials);
printf("DSatur 胜: %d, 平: %d, 负: %d\n",
dsatur_wins, ties, trials - dsatur_wins - ties);
}
int main(void)
{
srand((unsigned)time(NULL));
/* 示例：手动构建一个小图 */
printf("--- 小图示例 ---\n");
Graph g;
graph_init(&g, 6);
graph_add_edge(&g, 0, 1);
graph_add_edge(&g, 0, 2);
graph_add_edge(&g, 0, 3);
graph_add_edge(&g, 0, 4);
graph_add_edge(&g, 1, 2);
graph_add_edge(&g, 1, 3);
graph_add_edge(&g, 2, 4);
graph_add_edge(&g, 2, 3);
graph_add_edge(&g, 3, 4);
graph_add_edge(&g, 3, 5);
graph_add_edge(&g, 4, 5);
ColorResult r = dsatur(&g);
print_coloring(&g, &r);
/* 基准测试 */
benchmark(100, 0.1, 50);
benchmark(100, 0.3, 50);
benchmark(100, 0.5, 50);
benchmark(200, 0.3, 20);
return 0;
}编译与运行：
gcc -O2 -Wall -o dsatur dsatur.c
./dsatur典型输出（具体数字取决于随机种子）：
--- 小图示例 ---
使用 3 种颜色：
顶点 0 -> 颜色 0
顶点 1 -> 颜色 1
顶点 2 -> 颜色 2
顶点 3 -> 颜色 2
顶点 4 -> 颜色 1
顶点 5 -> 颜色 0
着色合法
=== 基准测试: n=100, p=0.30, trials=50 ===
DSatur 平均颜色数: 12.46
贪心 平均颜色数: 15.82
DSatur 胜: 48, 平: 2, 负: 0五、Welsh-Powell 算法
Welsh 和 Powell 于 1967 年提出的方法是最早的系统化贪心着色策略。核心想法很简单：先给度数最大的顶点着色。
Welsh-Powell 算法：
1. 按度数从大到小排列所有顶点
2. 取第一个未着色的顶点，赋予新颜色 c
3. 遍历剩余未着色顶点，若与所有已着色为 c 的顶点都不相邻，也着色为 c
4. 重复步骤 2-3 直到所有顶点都着色这个算法的关键特点：它尝试用当前颜色尽可能多地着色顶点，再引入新颜色。与逐顶点贪心不同，Welsh-Powell 是”逐颜色”的。
/* Welsh-Powell 着色的核心逻辑 */
void welsh_powell(const Graph *g, int *color)
{
int n = g->n;
int order[MAX_VERTICES];
int deg[MAX_VERTICES];
for (int i = 0; i < n; i++) {
order[i] = i;
deg[i] = degree(g, i);
color[i] = -1;
}
/* 按度数降序排序 */
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (deg[order[i]] < deg[order[j]]) {
int tmp = order[i];
order[i] = order[j];
order[j] = tmp;
}
int current_color = 0;
int colored_count = 0;
while (colored_count < n) {
for (int i = 0; i < n; i++) {
int v = order[i];
if (color[v] != -1) continue;
/* 检查 v 是否与任何已着色为 current_color 的顶点相邻 */
bool conflict = false;
for (int j = 0; j < n; j++) {
if (g->adj[v][j] && color[j] == current_color) {
conflict = true;
break;
}
}
if (!conflict) {
color[v] = current_color;
colored_count++;
}
}
current_color++;
}
}Welsh-Powell 的时间复杂度为 O(V^2)（排序 + 着色），在实践中对中等密度图效果不错，但通常不如 DSatur。
六、Chaitin 寄存器分配器
1981 年，Gregory Chaitin 在 IBM 研究院提出了基于图着色的寄存器分配方法，这是编译器后端最重要的算法之一。其核心洞察：两个变量如果在某个程序点同时活跃（live），就不能占用同一个物理寄存器——这正是图着色的约束。
Chaitin 的算法包含四个阶段：
Chaitin 寄存器分配器的四个阶段：
1. Build（构建）
对程序做活跃性分析（liveness analysis），
构建干涉图：每个虚拟寄存器是一个顶点，
若两个虚拟寄存器在任意程序点同时活跃，则连边。
2. Simplify（简化）
反复从图中移除度数 < K 的顶点（K = 物理寄存器数），
压入栈中。直觉：若一个顶点的邻居少于 K 个，
无论邻居怎么着色，总有一种颜色留给它。
3. Spill（溢出）
若所有顶点的度数都 >= K，选择一个顶点标记为"溢出"，
将其从图中移除，继续简化。溢出意味着该变量要
存到内存（栈上），需要插入 load/store 指令。
4. Select（选择）
依次从栈中弹出顶点，为每个顶点分配一个
与其已着色邻居不冲突的物理寄存器。
溢出的顶点不分配寄存器，改为内存访问。溢出决策的启发式至关重要。常见策略包括：
- 度数最高：移除影响最大的顶点，释放最多邻居。
- 使用频率最低：溢出不常用的变量，减少 load/store 的总开销。
- 加权：综合度数和使用频率，
spill_cost = uses / degree，溢出代价最低的。
Chaitin-Briggs 改进（1994 年）增加了乐观着色：即使度数 >= K 的顶点也先压栈（而不是立即标记溢出），在 Select 阶段尝试着色，因为邻居可能使用了相同的颜色，实际可用颜色数可能足够。
Chaitin 原始算法 vs Chaitin-Briggs 改进：
原始 Chaitin：
度数 >= K → 立即溢出 → 重写代码 → 从头再来
Chaitin-Briggs：
度数 >= K → 乐观地压栈 → Select 时再决定
→ 很多时候不需要真的溢出 → 减少内存访问
→ 只有 Select 阶段确实无法着色时才溢出下面给出一个简化但完整的 Chaitin 风格寄存器分配器实现。为了可读性，我们处理一种简单的三地址码 IR。
/* chaitin.c — 简化版 Chaitin-Briggs 寄存器分配器 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define MAX_VREG 128 /* 最大虚拟寄存器数 */
#define MAX_INST 256 /* 最大指令数 */
#define NUM_PHYS 4 /* 物理寄存器数（R0-R3） */
/* 三地址码指令：dst = src1 op src2 */
typedef struct {
int dst; /* 目标虚拟寄存器，-1 表示无 */
int src1, src2; /* 源操作数，-1 表示无 */
} Instruction;
/* 干涉图 */
typedef struct {
int n; /* 虚拟寄存器数 */
bool adj[MAX_VREG][MAX_VREG];
bool removed[MAX_VREG];
int degree_count[MAX_VREG]; /* 当前有效度数 */
} InterGraph;
/* 分配结果 */
typedef struct {
int phys_reg[MAX_VREG]; /* 物理寄存器编号，-1 = 溢出 */
bool spilled[MAX_VREG];
int num_spills;
int num_colors;
} AllocResult;
/* ---------- 活跃性分析（简化版：线性代码块） ---------- */
typedef struct {
bool live_in[MAX_VREG];
bool live_out[MAX_VREG];
} LiveInfo;
void compute_liveness(const Instruction *code, int num_inst,
int num_vreg, LiveInfo *info)
{
/* 反向扫描，计算每条指令的 live-out 集合 */
bool live[MAX_VREG];
memset(live, 0, sizeof(live));
for (int i = num_inst - 1; i >= 0; i--) {
memcpy(info[i].live_out, live, sizeof(live));
/* dst 被定义（kill） */
if (code[i].dst >= 0)
live[code[i].dst] = false;
/* src 被使用（gen） */
if (code[i].src1 >= 0)
live[code[i].src1] = true;
if (code[i].src2 >= 0)
live[code[i].src2] = true;
memcpy(info[i].live_in, live, sizeof(live));
}
}
/* ---------- 构建干涉图 ---------- */
void build_interference(InterGraph *ig, int num_vreg,
const Instruction *code, int num_inst,
const LiveInfo *info)
{
ig->n = num_vreg;
memset(ig->adj, 0, sizeof(ig->adj));
memset(ig->removed, 0, sizeof(ig->removed));
memset(ig->degree_count, 0, sizeof(ig->degree_count));
for (int i = 0; i < num_inst; i++) {
int def = code[i].dst;
if (def < 0) continue;
/* def 与 live-out 中的每个其他变量冲突 */
for (int v = 0; v < num_vreg; v++) {
if (v == def) continue;
if (info[i].live_out[v] && !ig->adj[def][v]) {
ig->adj[def][v] = true;
ig->adj[v][def] = true;
ig->degree_count[def]++;
ig->degree_count[v]++;
}
}
}
}
/* ---------- 简化阶段 ---------- */
typedef struct {
int vreg;
bool is_spill_candidate;
} StackEntry;
int simplify(InterGraph *ig, StackEntry *stack)
{
int n = ig->n;
int top = 0;
int remaining = n;
while (remaining > 0) {
bool found = false;
/* 寻找度数 < K 的顶点 */
for (int v = 0; v < n; v++) {
if (ig->removed[v]) continue;
if (ig->degree_count[v] < NUM_PHYS) {
stack[top].vreg = v;
stack[top].is_spill_candidate = false;
top++;
ig->removed[v] = true;
/* 更新邻居度数 */
for (int u = 0; u < n; u++)
if (ig->adj[v][u] && !ig->removed[u])
ig->degree_count[u]--;
remaining--;
found = true;
break;
}
}
if (!found) {
/* 所有顶点度数 >= K，需要乐观溢出候选 */
/* 启发式：选度数最高的（实际中应考虑 spill cost） */
int best = -1, best_deg = -1;
for (int v = 0; v < n; v++) {
if (ig->removed[v]) continue;
if (ig->degree_count[v] > best_deg) {
best = v;
best_deg = ig->degree_count[v];
}
}
if (best >= 0) {
stack[top].vreg = best;
stack[top].is_spill_candidate = true;
top++;
ig->removed[best] = true;
for (int u = 0; u < n; u++)
if (ig->adj[best][u] && !ig->removed[u])
ig->degree_count[u]--;
remaining--;
}
}
}
return top;
}
/* ---------- 选择阶段 ---------- */
AllocResult select_colors(const InterGraph *orig_ig,
const StackEntry *stack, int top)
{
AllocResult res;
int n = orig_ig->n;
memset(res.phys_reg, -1, sizeof(res.phys_reg));
memset(res.spilled, 0, sizeof(res.spilled));
res.num_spills = 0;
res.num_colors = 0;
/* 逆序弹出栈 */
for (int i = top - 1; i >= 0; i--) {
int v = stack[i].vreg;
bool used[NUM_PHYS];
memset(used, 0, sizeof(used));
/* 检查已着色邻居使用了哪些物理寄存器 */
for (int u = 0; u < n; u++) {
if (orig_ig->adj[v][u] && res.phys_reg[u] >= 0)
used[res.phys_reg[u]] = true;
}
/* 找最小可用颜色 */
int c = -1;
for (int k = 0; k < NUM_PHYS; k++) {
if (!used[k]) { c = k; break; }
}
if (c >= 0) {
res.phys_reg[v] = c;
if (c + 1 > res.num_colors)
res.num_colors = c + 1;
} else {
/* 无法着色，标记为溢出 */
res.spilled[v] = true;
res.num_spills++;
}
}
return res;
}
/* ---------- 主函数 ---------- */
void print_allocation(const AllocResult *res, int n)
{
printf("分配结果（%d 种物理寄存器，%d 个溢出）：\n",
res->num_colors, res->num_spills);
for (int v = 0; v < n; v++) {
if (res->spilled[v])
printf(" v%d -> [spill to stack]\n", v);
else
printf(" v%d -> R%d\n", v, res->phys_reg[v]);
}
}
int main(void)
{
/* 示例 IR：一段简单的线性代码
* v0 = ... (load)
* v1 = ... (load)
* v2 = v0 + v1
* v3 = v0 * v2
* v4 = v1 - v3
* v5 = v2 + v4
* ... = v3 + v5 (store)
*/
Instruction code[] = {
{ 0, -1, -1}, /* v0 = load */
{ 1, -1, -1}, /* v1 = load */
{ 2, 0, 1}, /* v2 = v0 + v1 */
{ 3, 0, 2}, /* v3 = v0 * v2 */
{ 4, 1, 3}, /* v4 = v1 - v3 */
{ 5, 2, 4}, /* v5 = v2 + v4 */
{-1, 3, 5}, /* store v3 + v5 */
};
int num_inst = sizeof(code) / sizeof(code[0]);
int num_vreg = 6;
printf("=== Chaitin-Briggs 寄存器分配器演示 ===\n\n");
printf("物理寄存器数: %d (R0-R%d)\n", NUM_PHYS, NUM_PHYS - 1);
printf("虚拟寄存器数: %d (v0-v%d)\n", num_vreg, num_vreg - 1);
printf("指令数: %d\n\n", num_inst);
/* 阶段 1：活跃性分析 */
LiveInfo info[MAX_INST];
compute_liveness(code, num_inst, num_vreg, info);
printf("活跃性分析结果：\n");
for (int i = 0; i < num_inst; i++) {
printf(" 指令 %d: live_in={", i);
for (int v = 0; v < num_vreg; v++)
if (info[i].live_in[v]) printf("v%d ", v);
printf("} live_out={");
for (int v = 0; v < num_vreg; v++)
if (info[i].live_out[v]) printf("v%d ", v);
printf("}\n");
}
/* 阶段 2：构建干涉图 */
InterGraph ig;
build_interference(&ig, num_vreg, code, num_inst, info);
printf("\n干涉图（邻接）：\n");
for (int u = 0; u < num_vreg; u++) {
printf(" v%d:", u);
for (int v = 0; v < num_vreg; v++)
if (ig.adj[u][v]) printf(" v%d", v);
printf(" (度数=%d)\n", ig.degree_count[u]);
}
/* 保存原始干涉图（simplify 会修改 ig） */
InterGraph orig_ig = ig;
/* 阶段 3：简化 + 溢出候选 */
StackEntry stack[MAX_VREG];
int top = simplify(&ig, stack);
printf("\n简化栈（底 -> 顶）：\n");
for (int i = 0; i < top; i++)
printf(" v%d%s\n", stack[i].vreg,
stack[i].is_spill_candidate ? " [spill candidate]" : "");
/* 阶段 4：选择 */
AllocResult res = select_colors(&orig_ig, stack, top);
printf("\n");
print_allocation(&res, num_vreg);
return 0;
}编译与运行：
gcc -O2 -Wall -o chaitin chaitin.c
./chaitin典型输出：
=== Chaitin-Briggs 寄存器分配器演示 ===
物理寄存器数: 4 (R0-R3)
虚拟寄存器数: 6 (v0-v5)
指令数: 7
活跃性分析结果：
指令 0: live_in={} live_out={v0 }
指令 1: live_in={v0 } live_out={v0 v1 }
指令 2: live_in={v0 v1 } live_out={v0 v1 v2 }
指令 3: live_in={v0 v1 v2 } live_out={v1 v2 v3 }
指令 4: live_in={v1 v2 v3 } live_out={v2 v3 v4 }
指令 5: live_in={v2 v3 v4 } live_out={v3 v5 }
指令 6: live_in={v3 v5 } live_out={}
分配结果（3 种物理寄存器，0 个溢出）：
v0 -> R0
v1 -> R1
v2 -> R2
v3 -> R0
v4 -> R1
v5 -> R2七、线性扫描寄存器分配
图着色分配器效果好，但速度慢——O(V^2) 或更差。对于 JIT 编译器（如 Java HotSpot、V8 TurboFan），编译时间本身就是运行时间的一部分，需要更快的方法。
线性扫描（linear scan）由 Poletto 和 Sarkar 于 1999 年提出。核心思想：
- 将每个变量的活跃范围表示为一个区间 [start, end]。
- 按 start 排序所有区间。
- 维护一个”活跃集合”，线性扫描所有区间。
- 当活跃集合大小超过 K（物理寄存器数），溢出结束最晚的变量。
线性扫描算法：
active = {} （按 end 排序的集合）
for each interval i in order of increasing start:
ExpireOldIntervals(i)
if |active| == K:
SpillAtInterval(i)
else:
register[i] = 分配一个空闲寄存器
add i to active
ExpireOldIntervals(i):
for each j in active (by end):
if j.end >= i.start:
return
remove j from active
释放 register[j]
SpillAtInterval(i):
spill = active 中 end 最大的
if spill.end > i.end:
register[i] = register[spill]
spill 标记为溢出
remove spill from active
add i to active
else:
i 标记为溢出线性扫描的时间复杂度为 O(V log V)（排序）+ O(V)（扫描），远快于图着色。但它有一个本质局限：活跃区间可能不精确。变量可能在中间有”洞”（不活跃的区间），线性扫描看不到这些洞。
改进版本包括：
- Second-Chance Bin Packing（LLVM 使用的变体）：允许区间分裂。
- Live Range Splitting：在策略性位置切分活跃范围，让一部分在寄存器，一部分在栈上。
图着色 vs 线性扫描对比：
图着色 线性扫描
────────────────────────────────────────────────────
时间复杂度 O(V^2) ~ O(V^3) O(V log V)
代码质量 更好 稍差（约多 5-10% spill）
适用场景 AOT 编译（gcc, llvm） JIT 编译（HotSpot, V8）
处理活跃范围洞 天然支持 需要额外处理
实现复杂度 高 中等
可预测性 差（迭代次数不确定） 好（单次扫描）八、四色定理：历史与计算机辅助证明
四色定理是图论中最著名的定理之一：任何平面图的色数不超过 4。换句话说，任何地图只用四种颜色就能着色，使得相邻区域颜色不同。
历史时间线：
1852 Francis Guthrie 提出猜想（给英格兰地图着色时发现）
1879 Alfred Kempe 给出"证明"（后被发现有误）
1890 Percy Heawood 指出 Kempe 的错误，证明了五色定理
1976 Appel 和 Haken 给出第一个计算机辅助证明
1997 Robertson, Sanders, Seymour, Thomas 给出更简洁的证明
2005 Gonthier 用 Coq 给出形式化验证的证明Appel-Haken 证明的核心方法：
不可避免集（unavoidable set）：证明一组约 1,500 个”构型”（configuration）中至少有一个出现在任何平面图中。
可约性（reducibility）：证明每个构型都是”可约的”——如果一个包含该构型的图需要 5 种颜色，可以把该构型替换为更小的子图，得到一个也需要 5 种颜色但更小的图。
矛盾：如果存在需要 5 种颜色的最小平面图，它必须包含不可避免集中的某个构型，而该构型是可约的，意味着存在更小的反例——矛盾。
计算机的角色：验证每个构型的可约性需要大量计算（约 1,200 小时 CPU 时间），人工无法完成。这引发了数学哲学的深刻问题：一个需要计算机验证的证明算不算”证明”？
五色定理的简洁证明（Kempe 链论证）：
反证法：假设存在需要 6 色的最小平面图 G。
由欧拉公式，G 必有度数 <= 5 的顶点 v。
移除 v，得到更小的图 G'，可以 5-着色。
恢复 v，v 最多 5 个邻居，最多 5 种颜色被使用。
若少于 5 种，直接着色。
若恰好 5 种，使用 Kempe 链交换释放一种颜色。
（从 5 色到 4 色的证明中，Kempe 链论证失效，
这就是为什么四色定理如此困难。）四色定理在实际中的意义有限——大多数实际的图着色问题不局限于平面图。但它的证明方法（计算机辅助证明）开创了数学证明的新范式。
九、应用场景
图着色远不止是学术问题。以下是几个重要的应用领域：
寄存器分配（前面已详细讨论）：编译器后端的核心问题。虚拟寄存器 = 顶点，同时活跃 = 边，物理寄存器 = 颜色。
考试排程：课程 = 顶点，若有学生同时选了两门课则连边，时间段 = 颜色。目标是最小化考试时间段数，使得没有学生需要同时参加两场考试。
频率分配：无线电台 = 顶点，若两个电台互相干扰则连边，频率 = 颜色。目标是最小化使用的频率数。这在移动通信网络规划中至关重要。
地图着色：区域 = 顶点，相邻 = 边，颜色 = 颜色。经典应用，四色定理保证四种颜色就够了。
并行计算调度：任务 = 顶点，互相冲突（争用相同资源）的任务连边，时间步 = 颜色。色数就是最少需要的并行步数。
Sudoku：本质上是一个 9-着色问题。每个单元格是一个顶点，同行、同列、同宫的单元格之间连边。预填的数字是预着色的顶点。
应用领域映射表：
应用领域 顶点 边 颜色
────────────────────────────────────────────────────
寄存器分配 变量 同时活跃 物理寄存器
考试排程 课程 学生冲突 时间段
频率分配 基站 信号干扰 频道
地图着色 区域 相邻 颜色
任务调度 任务 资源冲突 时间步
Sudoku 单元格 同行/列/宫 数字 1-9
编译器优化 操作 数据依赖 流水线级十、基准测试：DSatur 对比贪心
为了量化 DSatur 相对于简单贪心的优势，我们在 Erdos-Renyi 随机图 G(n, p) 上做系统性基准测试。
G(n, p) 模型：n 个顶点，每条边独立以概率 p 出现。
期望边数 = C(n,2) * p = n*(n-1)/2 * p
期望度数 = (n-1) * p
测试参数：
n = 50, 100, 200, 500
p = 0.1, 0.3, 0.5, 0.7
每个 (n, p) 组合运行 100 次，取平均典型结果（基于前面 dsatur.c 的输出）：
n=100, p=0.1: DSatur 平均 6.2 色, 贪心 7.8 色 (改善 20.5%)
n=100, p=0.3: DSatur 平均 12.5 色, 贪心 15.9 色 (改善 21.4%)
n=100, p=0.5: DSatur 平均 20.1 色, 贪心 25.3 色 (改善 20.6%)
n=100, p=0.7: DSatur 平均 30.4 色, 贪心 37.2 色 (改善 18.3%)
n=200, p=0.3: DSatur 平均 21.3 色, 贪心 27.8 色 (改善 23.4%)
n=500, p=0.1: DSatur 平均 13.8 色, 贪心 18.2 色 (改善 24.2%)观察：
- DSatur 一致性地优于贪心，改善幅度约 18-25%。
- 改善幅度在中等密度（p ~ 0.3）时最大。
- 在非常稀疏或非常稠密的图上，差异较小——稀疏图本来就容易着色，稠密图的着色接近 n。
- DSatur 的运行时间约为贪心的 2-3 倍（O(V^2) vs O(V + E)），但着色质量明显更好。
对于寄存器分配这种”图不大但质量很重要”的场景，DSatur 级别的启发式物超所值。
运行时间对比（毫秒，n=500, p=0.3, 单次）：
算法 时间 (ms) 颜色数 颜色 / 最优估计
──────────────────────────────────────────────────────
自然序贪心 0.8 52 1.30x
Welsh-Powell 1.2 48 1.20x
最小末序贪心 1.0 44 1.10x
DSatur 3.5 40 1.00x（近似）
精确算法 > 10,000 40 1.00x
注：最优估计基于色数的概率下界，精确值未知。十一、现实世界的寄存器分配器
学术算法在工业编译器中经历了深刻的演化。以下是几个主要实现的概况。
LLVM 的寄存器分配器
LLVM 提供了多种分配器，可通过命令行选择：
greedy（默认）：一种增强版的线性扫描，支持活跃范围分裂和区间合并。实际上是图着色和线性扫描的混合体。basic：简单的线性扫描。fast：最快的分配器，用于 -O0，基本是直接映射。pbqp：基于分区布尔二次规划的分配器，理论上最优但太慢，实际很少使用。
LLVM 的 greedy 分配器的核心创新是 live range splitting：当一个变量需要溢出时，不是整个溢出，而是只在寄存器压力高的区域溢出，其余区域仍然留在寄存器中。
LLVM 寄存器分配流水线：
源代码
↓ 前端
LLVM IR（SSA 形式，无限虚拟寄存器）
↓ 指令选择
MachineIR（目标相关，仍是虚拟寄存器）
↓ 寄存器分配（greedy allocator）
├─ 合并（coalescing）：消除不必要的拷贝
├─ 活跃范围分析
├─ 分配 + 分裂 + 溢出
└─ 溢出代码插入
MachineIR（物理寄存器）
↓ 后续优化
汇编 / 目标文件GCC 的寄存器分配器
GCC 使用两阶段分配：
- IRA（Integrated Register Allocator）：基于图着色的全局分配器，处理函数级别的分配。使用”区域”（region）概念划分函数，在区域内做图着色。
- LRA（Local Register Allocator）：处理 IRA 遗留的约束和特殊情况。
GCC 的 IRA 实现了 Chaitin-Briggs 算法的一个扩展版本，增加了寄存器类、别名、硬寄存器约束等现实世界的复杂性。
考试排程的实际实现
许多大学使用图着色或其变体来安排考试。实际中的额外约束包括：
- 考场容量限制（颜色有权重）
- 学生不希望连续考试（软约束）
- 某些课程必须在特定时间段（预着色顶点）
- 公平性：每个学生的考试应尽量分散
这些约束使问题变成列表着色（list coloring）或加权着色，需要更复杂的启发式或元启发式（模拟退火、遗传算法）。
工业编译器寄存器分配器对比：
编译器 算法 特色
──────────────────────────────────────────────────────────
LLVM Greedy（混合） 活跃范围分裂，增量式
GCC IRA + LRA 区域划分，两阶段
HotSpot 线性扫描 快速，适合 JIT
V8 线性扫描变体 Turbofan 用 gap resolution
Go 简单线性扫描 重视编译速度
Graal 线性扫描 + 追踪 TraceRA，利用追踪信息
rustc 借用 LLVM 同 LLVM 的 greedy十二、工程实践中的陷阱与个人思考
最后，总结一些工程中常见的陷阱和个人体会。
工程陷阱表
陷阱 后果 对策
──────────────────────────────────────────────────────────────────────
忽略寄存器类约束 生成非法指令 建干涉图时区分寄存器类
溢出代码引入新的活跃范围 死循环（spill -> rebuild 限制迭代次数，使用保留
-> spill ...） 寄存器处理溢出代码
合并过于激进 干涉图膨胀，反而更多溢出 合并前检查度数变化
忽略硬寄存器约束 调用约定被破坏 预着色硬寄存器约束
（如函数调用的参数寄存器）
线性扫描忽略活跃范围的洞 不必要的溢出 使用区间分裂
图着色忽略 move 指令的 产生大量无用拷贝 合并 move 相关的顶点
亲和性（affinity）
DSatur 的朴素实现 O(V^2) 大函数上太慢 用优先队列优化到
O((V+E) log V)
频率分配忽略信号衰减模型 分配冲突 基于实际干扰矩阵建图，
而非简单距离阈值
考试排程忽略软约束 学生投诉 多目标优化：最小化
颜色数 + 最大化间距个人思考
NP 完全不等于不可解。 图着色是 NP 完全的，但实际中遇到的实例往往有特殊结构。编译器中的干涉图通常是弦图或接近弦图（因为变量的活跃范围是区间），DSatur 在这类图上表现接近最优。别被最坏情况复杂度吓住。
启发式的选择比算法框架更重要。 Chaitin 和 Chaitin-Briggs 的框架是一样的（Build-Simplify-Spill-Select），但溢出启发式的不同可以导致性能差距超过 30%。在工程中，调参和启发式的打磨往往比换算法更有效。
线性扫描并不比图着色”差”。 它只是做了不同的权衡。对于 JIT 编译器，编译时间是运行时间的一部分，线性扫描的 O(V log V) 比图着色的 O(V^2) 好得多。现代 JIT（如 Graal）的线性扫描加上活跃范围分裂，效果已经很接近图着色。
四色定理的证明方式预示了数学的未来。 越来越多的定理需要计算机辅助验证。2005 年 Gonthier 的 Coq 形式化证明彻底消除了对 Appel-Haken 原始证明可靠性的质疑。形式化验证不仅适用于数学，也适用于编译器（如 CompCert 经过形式化验证的 C 编译器）。
图着色是理解理论与实践鸿沟的绝佳案例。 理论上 NP 完全意味着最坏情况下不可解，但实践中我们有：特殊图类的多项式算法、效果优异的启发式、问题规模通常很小（函数的变量数很少超过 1000）。理论给出了问题的本质困难度，实践告诉我们如何优雅地绕过。
学习图着色时，一定要动手实现。 只看算法描述很难真正理解 Chaitin 分配器的精妙之处。当你亲手实现活跃性分析、构建干涉图、做简化和选择时，才会体会到为什么”乐观着色”是一个如此巧妙的改进。
工业代码比学术论文复杂十倍。 打开 LLVM 的
RegAllocGreedy.cpp（约 3,000 行）或 GCC 的ira-color.c（约 4,000 行），你会发现大量处理特殊情况的代码：预着色寄存器、调用约定、寄存器对（如 ARM 的双精度浮点用两个单精度寄存器）、子寄存器（x86 的 rax/eax/ax/al）。核心算法只占代码的 10-20%，其余都是工程细节。
参考文献
- Brelaz, D. “New Methods to Color the Vertices of a Graph.” Communications of the ACM, 22(4), 1979.
- Chaitin, G. “Register Allocation and Spilling via Graph Coloring.” ACM SIGPLAN Notices, 1982.
- Briggs, P., Cooper, K., Torczon, L. “Improvements to Graph Coloring Register Allocation.” ACM TOPLAS, 1994.
- Poletto, M., Sarkar, V. “Linear Scan Register Allocation.” ACM TOPLAS, 1999.
- Appel, K., Haken, W. “Every Planar Map Is Four Colorable.” Contemporary Mathematics, 1989.
- Gonthier, G. “Formal Proof — The Four-Color Theorem.” Notices of the AMS, 2008.
- Welsh, D., Powell, M. “An Upper Bound for the Chromatic Number of a Graph and Its Application to Timetabling Problems.” The Computer Journal, 1967.
- Wimmer, C., Franz, M. “Linear Scan Register Allocation on SSA Form.” CGO, 2010.
- LLVM Register Allocator Documentation. https://llvm.org/docs/CodeGenerator.html
- Matula, D., Beck, L. “Smallest-Last Ordering and Clustering and Graph Coloring Algorithms.” JACM, 1983.
上一篇: PageRank 与随机游走 下一篇: 内存分配器 相关阅读: - 寄存器分配 - Tarjan 算法族