寄存器分配（图着色）

🪑 变量多，寄存器少——谁”坐”寄存器？

CPU 的寄存器数量有限（x86-64 有 16 个通用寄存器，ARM64 有 31 个）。但一个程序可能有成百上千个变量。

寄存器分配（Register Allocation） 决定：哪些变量放在极快的寄存器中，哪些”溢出”到较慢的栈内存。

🏪 **类比：星巴克的座位”

星巴克有 20 个座位（寄存器），但有 100 个顾客（变量）。

• 谁”配”坐座位？→ 谁用得更频繁、更迫切
• 坐不下的人怎么办？→ 打包带走（溢出到内存）
• 如果坐着的某个人很久没动（长时间不使用）→ 请他把座位让给更需要的人

寄存器分配做的就是”谁坐座位、谁打包带走”的决策。

---

🔧 图着色算法

图着色是寄存器分配最经典的算法——1979 年由 Chaitin 提出，今天 LLVM、GCC 等主流编译器仍在使用。

第 1 步：构建干扰图

两个变量如果”同时活跃”，就在它们之间画一条边——表示它们不能共享同一个寄存器。

# 干扰图的构建逻辑
# 如果变量 x 和 y 在某个时刻都"活着"——它们冲突

# 代码：a = b + c; d = a * e
# 活跃分析结果：
# b 和 c 在加法前活着 → b 和 c 冲突
# a 在加法后、乘法前活着 → a 与 b、c 不冲突（b、c 已经用完了）
# d 在乘法后活着 → d 与 a 冲突

interference_graph = {
    "a": {"d", "e"},
    "b": {"c", "e"},
    "c": {"b"},
    "d": {"a", "e"},
    "e": {"a", "b", "d"},
}

第 2 步：着色

把颜色分配给每个节点——相邻节点不能同色。颜色数量 = 可用寄存器数量。

干扰图：
   b ─── c
   │     │
   e ─── a ─── d

可用颜色：R, G, B（3 个寄存器）
着色方案：
  a → R    b → G    c → B    d → G    e → B

检查：相邻的 a(R) 和 e(B) 颜色不同 ✅
     相邻的 b(G) 和 e(B) 颜色不同 ✅
     ...

第 3 步：溢出

如果颜色不够用——某些变量必须”溢出”到栈内存。

如果只有 2 个可用寄存器——无法用 2 种颜色给上图着色
→ 选择一个变量（通常选使用最少的）溢出到内存
→ 从干扰图中去掉它 → 重新着色

---

📊 寄存器 vs 内存的速度差异

存储位置	访问延迟	相对速度
寄存器	~0.3 ns	⚡ 最快
L1 缓存	~1 ns	次快
L2 缓存	~4 ns	中等
主存（RAM）	~50 ns	🐢 慢 ~150 倍

一次”溢出”到内存意味着每次访问该变量要等 50+ ns——这就是为什么好的寄存器分配对性能至关重要。

---

📝 小结

概念	一句话
寄存器分配	决定哪个变量放寄存器——“座位分配”问题
干扰图	两个变量同时活跃→冲突→不能共享寄存器
图着色	给干扰图的节点分配颜色(寄存器)，相邻节点不能同色
溢出（Spill）	寄存器不够用时——变量存到栈内存
重要性	寄存器比内存快 ~150 倍——好的分配可以大幅提升性能

为什么先学这个？ 分配好寄存器后，进入基本优化（常量折叠、死代码消除）。