# Register Allocation

目标：

• Map temporaries to registers
• Preserve program semantics
• Optimize performance

# 图着色算法

冲突图是一个无向图，冲突图中，每个节点是一个变量（寄存器分配的候选对象）。
如果两个变量在同一时刻是活跃的（live），它们就有冲突边（interference edge），表示它们不能被分配到同一个寄存器
冲突信息可以用矩阵或者图来表示

# 冲突图构建

我们从一个中间代码的指令出发，根据 live-out（就是 out 集合）添加冲突边：

1. 非 move 指令（不是 a := b 这种）
   比如 a := b1 + b2
   对于每个 bn 和 a 之间都添加冲突边
   比如下面这个例子：
   
   可以看到有 ab ac 同时 live 了，所以为 a 和 b，a 和 c 添加冲突边
2. move 指令
   对于 move 指令，不添加冲突边：
   比如对于第 2 条指令 d ← a，out [2] = {a, e}，那么只对 d 和 e 添加冲突边，对 d 和 a 不添加
   但如果 move 之后又对 d 重新赋值了，那么还是要添加上 d 和 a 之间的冲突边

# 冲突图着色

Vertex Coloring: 给图中的顶点着色，使得图中没有边连接相同颜色的顶点
K-Coloring: 颜色数小于 K

# Kempe 简化

如果图中有一个节点 n 的度数 <K（也就是它的冲突数少于寄存器数），那我们可以 “临时删掉” 这个节点，并递归给剩下的图上色。之后再把这个节点加回来，它一定可以找到一个合法颜色。

如果图中所有节点的度数都 ≥ K，那就可能要进入溢出（spill）处理
算法步骤：

1. build: 画冲突图
2. simplify the nodes with insignificant degree: 选取 degree < k 的节点，压栈
3. select (or color) while rebuilding the graph: 出栈，分配颜色
   A vertex such that its degree < k is always k-colorable
   Remove such vertices and push them to a stack until the graph becomes empty
   移除顶点的同时移除相关边

# Coalescing

遵循两种策略：

• Briggs Criteria: 如果将节点 a 和 b 合并后得到的新节点 ab ，其相邻节点中 degree >= K 的节点（significant-degree neighbors）的数量 小于 K，则可以合并
• George Criteria: 如果对节点 a 和 b ，对于 a 的每一个邻居 t ， 满足二者其中之一，就能合并：
  • t 本来就和 b 有冲突
  • t 的 degree < K

整体流程：

• 为什么要 simplify non-move-related node: 保留 move-related 的后续可以合并
• freeze: 当我们遇到两个变量 a ← b 有 move 指令，但现在还不能安全合并，我们又不想立刻 spill，于是我们 “冻结” 这条 move 指令：不再试图合并 a 和 b，而是让其中一个变成非 move 相关（non-move-related），进入 Simplify 阶段继续处理
• spill 规则：优先移除不被经常使用、degree 大的节点
  • 实际溢出的 priority 计算，对于节点 a：

$$priority(t) = \frac{(use + def outside loop) + loop_num * (use + def inside loop)}{D}$$