跳转至

Register Allocation：寄存器分配

约 1256 个字 3 张图片 预计阅读时间 4 分钟

这一部分作用不言而喻。我们的目标是：

  • 产生正确的代码，将变量分配到 <=k 个寄存器中
  • 最小化 load 与 store 数量，并且最小化 spill 到内存中的空间
  • 分配过程要高效

有两种方法：

  • 图着色法：效果好，效率稍差
  • 线性扫描：效率更高，且有着相近的效果

下文重点介绍图着色法。

1. 通过“简化”来着色

值得一提的是寄存器分配是个 NP 完全问题，所以这里的图染色法也是一个近似，且是线性时间的近似。其基本流程是 build -> simplify -> spill -> select。

1.1 Build

就是构建干扰图。

1.2 Simplify

使用一种简单的假设来着色。大前提：机器的寄存器数量为 K。

  • 假设干扰图 G 包含一个节点 m，这个节点的邻居少于 K 个
    • 则通过删掉这个节点获得新图 G' = G - {m}
    • 如果 G' 可以被着色，则 G 也可以被着色
  • 这实际上形成了一个基于栈（或者说递归）的着色算法
    • 重复去除邻居数量小于 K 的节点，都把它们 push 到栈中
    • 每次删除都会减少一部分节点的邻居数量，提供更多 simplify 的机会
    • 直到图中只剩下 significant degree 的节点（即邻居数量 >= K 的节点）或者什么都不剩下

1.3 Spill

如果图中只剩下 significant degree 的节点，则需要进行 spill。

  • 可能选择一些节点，让其值放进内存中而不是寄存器中
  • Optimistic Coloring
    • 一个乐观的估计：被 spilled 的节点不与剩下的节点相互干扰
    • 从而可以被移除并 push 到栈中，然后继续 simplify
    • 这些节点可能是 potential spill，后续可能会发现其也是可以放进寄存器的

1.4 Select

这一步为节点着色。

  • 从空图开始，一步一步把栈顶的节点 pop 出来并分配颜色
  • 如果 pop 出的这个节点是刚才 spill 操作 push 进去的，这个节点不能保证被着色
    • 如果说这个节点的邻居数量小于 K 个节点，那就可以被着色，也就不是一个 actual spill
    • 反之就是一个 actual spill，不为其上色而是 continue

如果在 select 阶段，不能为某些节点上色，则程序需要被重写：

  • 每次用这些 actual spill 的节点之前，需要从内存中 load 其值
  • 每次用这些 actual spill 的节点之后，需要 store 其值到内存中

这样之后，一个 spill 的变量会转换为多个活跃性较短的变量，这些变量也可能会与其他变量发生干扰。

  • 这就需要重新构建干扰图，重新进行 simplify 和 select
  • 直到 simplify 可以在没有 spill 的情况下完成
  • 这可能需要多次迭代，一般情况下一到两次就可以完成

image.png

2. 合并 Coalalescing

2.1 定义

如果 MOVE 指令的两边没有干扰，这个 MOVE 就可以被消掉。这样，src 和 dst 的节点就被合并成一个新的节点，边就是 src 和 dst 的边的并集。

为什么合并？因为合并可能带来 coloring 的机会。

但是合并也存在问题：

  • 新的节点的 edges 更多
  • 原来的 k-colorable 图可能就不是 k-colorable 了

所以我们需要进行保守的合并，也即检查确认安全后合并。安全的意思就是合并操作不会把原来的图变成一个非 k-colorable 的图。

如何检查安全性呢？有两个准则：Briggs 和 George。

2.2 Briggs 准则

定义 significant degree 的节点为满足 degree >= k 的节点。

如果合并后的节点拥有少于 K 个 significant degree 的邻居，则合并是安全的。

2.3 George 准则

两个节点 a 和 b，如果对于 a 的每个邻居 t：

  • 要么 t 已经与 b 干扰
  • 要么 t 是 insignificant degree 的节点（即 degree < k）

则合并是安全的。

2.4 包含合并的寄存器分配过程

image.png

  1. Build
    • 构建干扰图
    • 每个节点分为 move-related 和 non-move-related
      • move-related 节点是指那些通过 MOVE 指令连接的节点
  2. Simplify
    • 移除邻居数量小于 K 的 non-move-related 节点
  3. Coalesce
    • 合并 move-related 节点
    • 如果合并后某个节点不是 move-related，就可以进行下一轮的 simplify
    • 一直重复 simplify 和 coalesce，直到图中只剩下 significant degree 或者是 move-related 的节点
  4. Freeze
    • 如果没有使用 simpilfy 或 coalesce，我们去看 low degree 的 move-related 节点
      • 实际上放弃了合并的希望
      • 导致这个节点（可能还有与其相关的其他节点）被认为是 non-move-related
    • 然后再进行 simplify 和 coalesce
  5. Spill
    • 如果没有 low-degree 节点，就选择一个做 potential spill
  6. Select
    • 选择栈顶的节点进行着色
    • 如果是 potential spill 的节点，则不着色而是继续

3. 预填色 Precolored Nodes

有些寄存器是 special purpose 的：

  • 参数寄存器
  • 帧指针
  • 返回值等等

这些寄存器是被预先填色的：

  • 一个颜色只能有一个 precolored node
  • precolored nodes 之间互相干扰

需要注意的是：

  • 可以为一个普通临时变量分配一个 precolored node 的颜色，只要它们之间没有干扰
  • 不可以 simplify precolored nodes
  • precolored nodes 不能被 spill
    • 前端有义务将其活跃度缩短
    • 给个例子
    • image.png

区分 caller-saved 和 callee-saved 寄存器

活跃度不跨越 procedure call 的寄存器一般是 caller-saved 寄存器；需要跨越 procedure call 的寄存器一般是 callee-saved 寄存器。