为什么编译器要在寄存器分配中构造图？

Question

我一直在研究寄存器分配，并想知道为什么当有更好的方法可以做到时，他们都从实时寄存器列表中构建图表。我认为他们可以做到的方式是当活动寄存器超过可用寄存器的数量时，寄存器可能会溢出。这是一个示例（伪组装）：

## ldi: load immediate
## addr: add registers and store in arg 2
## store: store memory at offset from stack pointer
.text
    main:
        # live registers: {}
        ldi    %t0, 12             # t0 = 12
        # live registers: {t0}
        ldi    %t1, 8              # t1 = 8
        # live registers: {t0, t1}
        addr   %t0, %t1            # t1 = t0 + t1
        # live registers: {t1}
        store  -4(%sp), %t1        # -4(%sp) = t1
        # live registers: {}
        exit

我已经在汇编代码中列出了实时寄存器。现在，所有的教程和文本都从这里构建了干扰图，等等。但不是这样（正如我上面提到的），他们可以查看活动寄存器。例如，如果这是一台单1寄存器机器，那么当活动寄存器是 时{t0, t1}，我们将不得不选择一个寄存器来溢出。我觉得这比构建一个图形并做所有其他事情来检查我们是否必须溢出寄存器要简单得多。我知道无知不是全球性的（一定有人想到了这一点并认为它不合适），所以我在这里没有看到什么？

Answer 1

构建图形不是必需的，例如线性扫描算法避免构建图形。显然，它被 V8 和 HotSpot 等 JIT 编译器使用，因为它速度快，但其权衡是不太理想的决策。

线性扫描比寄存器用完时的单次通过和溢出更复杂。相反，您会找到有效范围并检查它们何时重叠。即使有一些分支和循环，这也可以做一个不错的工作。

我想如果您不聪明地让分支的任何一侧使用相同的临时寄存器以及线性扫描所做的那种分析，那么您的简单算法可能会在分支代码中严重退化。正如@supercat 所说，并非所有代码都是直线。 即便如此，关于溢出什么的 LRU 决定也不是最优的。您是一名编译器，您可以提前查看接下来要使用的寄存器正在做什么。

此外，您还需要提前查看结果是否/如何使用，除非您根本不打算进行优化。例如，x++; x++;应该编译与x+=2添加指令相同，而不是两个单独的 add-1 操作。因此，您需要某种数据结构来表示程序逻辑，而不仅仅是一次性将其转换为 asm。（除非您正在编写一个真正的一次性编译器，例如tcc.）

请注意，许多编译器的目标是好的代码，而不仅仅是正确的代码，这意味着最小化溢出/重新加载，尤其是在循环携带的依赖链上。即使在分支代码中也能很好地处理分配。这就是静态单分配 (SSA) 图的用处，以及何时在循环外提升或接收计算或内存访问的智能。

相关： 寄存器分配和溢出，简单的方法？有一些关于寄存器分配算法的更多细节，编译器：针对复杂分支/跳转的寄存器分配也有一些论文链接。

Answer 2

对于直线代码，仅仅考虑寄存器溢出可能没问题，但许多程序都包含循环。虽然循环中的寄存器效率通常比直线代码更重要，但寄存器溢出模型很难处理值在接近结束时需要在循环的一部分中处于活动状态的情况，并保持活动状态直到执行达到某个靠近开始的地方，但不需要留在中间。在寄存器溢出模型下，一个值可能会在循环开始时保存在寄存器中，而在循环结束时保存在不同的寄存器中。图形着色将确保两者都被分配相同的“颜色”[即放置在相同的寄存器中]。