为什么编译器在寄存器分配中构造一个图？
Why do compilers construct a graph in register allocation?
我一直在研究寄存器分配，想知道为什么他们都从实时寄存器列表构建图表，而有更好的方法来做这件事。我认为他们可以做到的方式是当活动寄存器超过可用寄存器的数量时，寄存器可能会溢出。这是一个例子（伪汇编）：
## 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} 时，我们将不得不选择一个寄存器来溢出。我觉得这比构建图形并执行所有其他操作来检查我们是否必须溢出寄存器要简单得多。我知道无知不是全球性的（一定有人想到了这一点并认为它不合适），所以我在这里没有看到什么？
仅仅考虑寄存器溢出对于直线代码来说可能没问题，但许多程序都包含循环。虽然循环中的寄存器效率通常比直线代码更重要，但寄存器溢出模型很难处理这样的情况：值需要在接近结束的部分循环中有效，并保持有效直到执行到某个值靠近开头的地方，但不需要留在中间。在寄存器溢出模型下，一个值可能会在循环开始时保存在一个寄存器中，而在接近结束时保存在另一个寄存器中。图着色将确保两者都被分配相同的“颜色”[即放在同一个寄存器中。
构建图不是必需的，例如 Linear Scan 算法避免构建图。显然它被 V8 和 HotSpot 等 JIT 编译器使用，因为它速度很快，但权衡的是做出不太理想的决策。
当您 运行 超出寄存器时，线性扫描比单次扫描和溢出更复杂。相反，您会找到有效范围并检查它们何时重叠。即使有一些分支和循环，这也可以做得不错。
我想如果您不聪明地让分支的任一侧使用相同的临时寄存器以及线性扫描所做的那种分析，那么您的简单算法可能会在分支代码中严重退化。正如@supercat 所说，并非所有代码都是直线的。 即便如此，关于溢出内容的 LRU 决策也不是最优的。你是编译器，你可以提前看看接下来要使用的寄存器。
此外，您还需要提前查看 if/how 结果是否已被使用，除非您根本不打算进行优化。例如x++; x++; 应该像 x+=2 一样编译成一个加法指令，而不是两个单独的 add-1 操作。因此，您需要某种数据结构来表示程序逻辑，而不仅仅是一次性将其动态转换为 asm。 （除非你正在编写一个像 tcc 这样真正的一次性编译器。）
请注意，许多编译器的目标是好的代码，而不仅仅是正确的代码，这意味着最小化spill/reload，尤其是在循环携带的依赖链上。即使在分支代码中也能很好地处理分配。这就是静态单一赋值 (SSA) 图有用的地方，同时还可以智能地判断何时将计算或内存访问提升或下沉到循环之外。
相关：
Register allocation and spilling, the easy way? has some more detail about register allocation algorithms, also Compilers: Register Allocation Against Complex Branching/Jumps 有一些论文链接。
我一直在研究寄存器分配，想知道为什么他们都从实时寄存器列表构建图表，而有更好的方法来做这件事。我认为他们可以做到的方式是当活动寄存器超过可用寄存器的数量时，寄存器可能会溢出。这是一个例子（伪汇编）：
## 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} 时，我们将不得不选择一个寄存器来溢出。我觉得这比构建图形并执行所有其他操作来检查我们是否必须溢出寄存器要简单得多。我知道无知不是全球性的（一定有人想到了这一点并认为它不合适），所以我在这里没有看到什么？
仅仅考虑寄存器溢出对于直线代码来说可能没问题，但许多程序都包含循环。虽然循环中的寄存器效率通常比直线代码更重要，但寄存器溢出模型很难处理这样的情况：值需要在接近结束的部分循环中有效，并保持有效直到执行到某个值靠近开头的地方，但不需要留在中间。在寄存器溢出模型下，一个值可能会在循环开始时保存在一个寄存器中，而在接近结束时保存在另一个寄存器中。图着色将确保两者都被分配相同的“颜色”[即放在同一个寄存器中。
构建图不是必需的，例如 Linear Scan 算法避免构建图。显然它被 V8 和 HotSpot 等 JIT 编译器使用，因为它速度很快，但权衡的是做出不太理想的决策。
当您 运行 超出寄存器时，线性扫描比单次扫描和溢出更复杂。相反，您会找到有效范围并检查它们何时重叠。即使有一些分支和循环，这也可以做得不错。
我想如果您不聪明地让分支的任一侧使用相同的临时寄存器以及线性扫描所做的那种分析，那么您的简单算法可能会在分支代码中严重退化。正如@supercat 所说，并非所有代码都是直线的。 即便如此，关于溢出内容的 LRU 决策也不是最优的。你是编译器，你可以提前看看接下来要使用的寄存器。
此外，您还需要提前查看 if/how 结果是否已被使用，除非您根本不打算进行优化。例如x++; x++; 应该像 x+=2 一样编译成一个加法指令，而不是两个单独的 add-1 操作。因此，您需要某种数据结构来表示程序逻辑，而不仅仅是一次性将其动态转换为 asm。 （除非你正在编写一个像 tcc 这样真正的一次性编译器。）
请注意，许多编译器的目标是好的代码，而不仅仅是正确的代码，这意味着最小化spill/reload，尤其是在循环携带的依赖链上。即使在分支代码中也能很好地处理分配。这就是静态单一赋值 (SSA) 图有用的地方，同时还可以智能地判断何时将计算或内存访问提升或下沉到循环之外。
相关： Register allocation and spilling, the easy way? has some more detail about register allocation algorithms, also Compilers: Register Allocation Against Complex Branching/Jumps 有一些论文链接。