Chapter 11: Register Allocation

图着色解决寄存器分配

NP-Compelete 问题

Build

构建冲突图（Chapter 10）

Simplify

如何简化冲突图

• K - number of machine register
• 删去邻居数小于 K 的结点（必定能被 K-1 个邻居的颜色之外的颜色着色）
• 删除了一些结点后，又有一些新的结点可以被删除，直到成为空图
• 剩下的结点度数都 >= K - Spill（may more than once）

邻居数 >= K 的结点 - significant degree node

Spill

Spill - 把一些结点存到内存中

• 乐观着色 - 如果邻居的颜色总数 < K，可以找到一个颜色给溢出结点，不会真正溢出
• 反之 actual spill

Select

按顺序 pop 出来着色

• 如果发现 actual spill，需要重写程序，回到 Build

Coalescing

合并

• Move 指令的源节点和目标结点可以合并，用一个寄存器
• Problem - 新结点的度数可能增加，可能会增大 K 的值
• 安全合并 - 不会减少图的可着色性

---

安全合并策略

• Briggs
  • 尝试合并 a, b
  • 看 a, b 的有 >= K 个结点的邻居
  • 如果这种邻居的个数 < K，则 safe
  • 原因：insignificant nodes 可以先删去，可以找到一个颜色给 a&b
• George
  • 对于 a 的每个邻居 t
  • 要么 t 也和 b 有一条边（合并成一条）
  • 或 t degree < K（可以提前删）
  • 则 a, b 合并安全

对于非预着色结点，使用 Briggs，

对预着色结点使用 george，此时总是把另一个结点看成 a

图着色流程

Precolored Nodes

提前分配颜色的结点（如 FP），不能删去