09-寄存器分配

• 时间复杂度：$O(n)$ 或 $O(\log n)$

• 当变量都活跃时，不能分配到同一个寄存器

Local Register Allocation

• 块内范围进行分配

• 变量的活跃期：从第一次出现开始，到最后一次出现的前一条指令结束

• MAXLIVE：当前指令下最大的活跃变量数

  • MAXLIVE <= n：可以方便地分配寄存器

  • MAXLIVE > n：“溢出 spill” 寄存器满，增加LD/ST指令，将值暂存入内存，待下次需要用时取出

Global Register Allocation

• Local 层面的分配无法复用块间的相同值

图着色算法概述

• 将图着色为 $k$ 种颜色，$k$ 为寄存器数

• 边上的节点不能同色

• 通过活跃范围建立干涉图

  • 节点：变量（虚拟寄存器）

  • 边：变量间的干涉关系，即有交集的活跃范围

• NP 完全问题，需要启发式算法

• 若需要超过 $k$ 种颜色，则需要将变量存入内存

Chaitin 算法

• 度 $\lt k$ 的节点永远是$k$可着色的（肯定能找到一种合适的颜色）

• 将以上节点去除，存入栈中，直到图变为空后

• 从栈顶依次取出节点，进行着色

• 若图非空且没有度 $\lt k$ 的节点

  • 选择某个节点进入溢出列表，从图中去除

  • 继续重复上述操作

• 若溢出列表非空，需插入LD/ST指令，随后重新构建干涉图并分配

Chaitin-Briggs 算法

• 边数$\ge k$不一定没办法着色

• 延迟溢出：出现溢出时先挑一个节点入栈，等到后续出栈时确定是否有可用颜色

  • 若无可用颜色再执行溢出操作

• 好处：无需溢出列表，减少访存指令的插入

选取溢出对象

• 最小化开销

• 选取最大度的节点：可以减少最多的边数

• 不要溢出马上使用的变量

• Splitting live ranges

  • 虽然每个时间段寄存器的数量不超过 $k$，但由于变量的活跃范围重叠，导致寄存器不足

  • 解决方法：将活跃范围分割成多个小的活跃范围，使得每个小的活跃范围都能被着色

• Coalescing virtual registers

  • 将存在赋值关系的变量合并

  • 可能会带来负面作用：两个节点对外的度数相加大于 $k$，导致无法着色