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

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

不需要构建图形，例如 Linear Scan算法避免构建图。显然，它被 V8 和 HotSpot 等 JIT 编译器使用，因为它速度快，但其代价是不太理想的决策。
线性扫描比寄存器用完时的单次通过和溢出更复杂。相反，您会找到有效范围并检查它们何时重叠。即使有一些分支和循环，这也可以做一个不错的工作。
我想如果你不聪明地让分支的任何一侧使用相同的临时寄存器，以及线性扫描所做的那种分析，你的简单算法可能会在分支代码中严重退化。正如@supercat 所说，并非所有代码都是直线。 即便如此，关于溢出什么的 LRU 决定也不是最佳的 .您是一名编译器，您可以提前查看接下来要使用的寄存器正在做什么。
此外，您还需要提前查看结果是否/如何使用，除非您根本不打算进行优化。例如x++; x++;应该与 x+=2 编译相同添加指令，而不是两个单独的 add-1 操作。因此，您需要某种数据结构来表示程序逻辑，而不仅仅是一次性将其转换为 asm。 (除非您正在编写真正的一次性编译器，如 tcc 。)
请注意，许多编译器的目标是好的代码，而不仅仅是正确的代码 ，这意味着最小化溢出/重新加载，尤其是在循环携带的依赖链上。即使在分支代码中也能很好地处理分配。这就是静态单分配 (SSA) 图的用处，以及在何时从循环中提升或接收计算或内存访问的智能。
有关的:
Register allocation and spilling, the easy way?有更多关于寄存器分配算法的细节，还有 Compilers: Register Allocation Against Complex Branching/Jumps有一些论文链接。