编译器：针对复杂的寄存器分配 Branching/Jumps
Compilers: Register Allocation Against Complex Branching/Jumps
我对优化器及其工作方式感兴趣，尤其是在寄存器分配方面。我有一些编写高级解释器的背景，这些解释器不会费心生成高效的机器代码，所以围绕与解析、构造 AST 等相关的编译器构造的部分对我来说相当简单。
作为一个学习项目，我一直在尝试玩具编译器，它只比机器级别稍微高一点，主要区别在于它使用变量而不是寄存器。
我非常困惑的地方是低级优化器部分，特别是关于 IR 的寄存器分配以及它如何受到 branching/jumps 的影响，即使是最基本的启发式算法，不包括高级SSA 和 phi 节点等主题。
基本示例：
a = ...
b = ...
c = ...
d = ...
e = ...
f = ...
g = ...
jump_if x == 1, section1
jump_if x == 2, section2
jump_if x == 3, section3
etc
a = a + b - c * 2
jump end
section1:
; all kinds of stuff happens here with some of the above variables
jump end
section2:
; all kinds of stuff happens here with some of the above variables
jump end
section3:
; all kinds of stuff happens here with some of the above variables
jump section1 ; tricky branch!!!
end:
也许我们可以加入循环逻辑和各种其他分支，使这个例子更加复杂。
我不明白的是，如果我们将所有这些分支路径一起考虑而不是单独考虑每个路径，那么所有这些分支路径都可能会产生上述所有变量 'live'。
我似乎缺少某种基于堆栈的块结构，这样我们就可以拥有嵌套块，其中寄存器分配可以考虑最内层块及其外部块引用的变量并执行该寄存器分配在每个 block/branching 路径上分别进行启发式。
在更基于块的更高级别的 IR 中，推断分支路径似乎更容易，因为分支将被限制在块内，但是在机器之上稍微抽象的低级 IR 呢？具有完全不受约束的分支的级别，您可以在其中 jump/branch 到处都是？
我见过的大多数 IR 示例都是相当低级的机器代码抽象，因此它们似乎常常让我们对如何进行分支（例如：跳转表）的方式变得非常混乱，这种方式可能真的很难推断出这样的blocks/sections/paths.
人们通常如何处理这个问题？有没有一种算法和一个干净的 organization/code 设计可以分解所有可能的分支路径，给定允许如此灵活的低级代码 branches/jumps?
寄存器分配是一个长期存在的问题。在这方面已经有许多研究论文。这方面最近比较流行的算法是SSA和线性扫描寄存器分配。
静态单一赋值形式 (SSA) 在帮助寄存器分配方面获得了一定的普及。这个想法是将程序逻辑转换为一个变量，该变量只会被分配一次，并且每个变量都需要在使用之前进行分配。一般假设可以使用的寄存器数量是无限的。
一旦程序转换成SSA形式，就可以更容易地转换成寄存器分配。这可以在多项式时间内通过图形着色来完成（流行的编译器是 LLVM）。这是一个非常复杂的话题，要在这里讨论。我建议您阅读该领域的几篇论文。
Efficiently Computing Static Single Assignment Form and the Control Dependence Graph 作者：Ron Cytron 等。他是SSA地区的开拓者之一。
A Simple, Fast Dominance Algorithm 作者：Keith D. Cooper 等
如果您不想将 SSA 作为中间步骤来处理，您可能想看看 Massimiliano Poletto 的 Linear Scan Register Allocation。这种贪心算法用于许多非基于 LLVM 的编译器，包括 v8 和 JVM。
我对优化器及其工作方式感兴趣，尤其是在寄存器分配方面。我有一些编写高级解释器的背景，这些解释器不会费心生成高效的机器代码，所以围绕与解析、构造 AST 等相关的编译器构造的部分对我来说相当简单。
作为一个学习项目，我一直在尝试玩具编译器，它只比机器级别稍微高一点，主要区别在于它使用变量而不是寄存器。
我非常困惑的地方是低级优化器部分，特别是关于 IR 的寄存器分配以及它如何受到 branching/jumps 的影响，即使是最基本的启发式算法，不包括高级SSA 和 phi 节点等主题。
基本示例：
a = ...
b = ...
c = ...
d = ...
e = ...
f = ...
g = ...
jump_if x == 1, section1
jump_if x == 2, section2
jump_if x == 3, section3
etc
a = a + b - c * 2
jump end
section1:
; all kinds of stuff happens here with some of the above variables
jump end
section2:
; all kinds of stuff happens here with some of the above variables
jump end
section3:
; all kinds of stuff happens here with some of the above variables
jump section1 ; tricky branch!!!
end:
也许我们可以加入循环逻辑和各种其他分支，使这个例子更加复杂。
我不明白的是，如果我们将所有这些分支路径一起考虑而不是单独考虑每个路径，那么所有这些分支路径都可能会产生上述所有变量 'live'。
我似乎缺少某种基于堆栈的块结构，这样我们就可以拥有嵌套块，其中寄存器分配可以考虑最内层块及其外部块引用的变量并执行该寄存器分配在每个 block/branching 路径上分别进行启发式。
在更基于块的更高级别的 IR 中，推断分支路径似乎更容易，因为分支将被限制在块内，但是在机器之上稍微抽象的低级 IR 呢？具有完全不受约束的分支的级别，您可以在其中 jump/branch 到处都是？
我见过的大多数 IR 示例都是相当低级的机器代码抽象，因此它们似乎常常让我们对如何进行分支（例如：跳转表）的方式变得非常混乱，这种方式可能真的很难推断出这样的blocks/sections/paths.
人们通常如何处理这个问题？有没有一种算法和一个干净的 organization/code 设计可以分解所有可能的分支路径，给定允许如此灵活的低级代码 branches/jumps?
寄存器分配是一个长期存在的问题。在这方面已经有许多研究论文。这方面最近比较流行的算法是SSA和线性扫描寄存器分配。
静态单一赋值形式 (SSA) 在帮助寄存器分配方面获得了一定的普及。这个想法是将程序逻辑转换为一个变量，该变量只会被分配一次，并且每个变量都需要在使用之前进行分配。一般假设可以使用的寄存器数量是无限的。
一旦程序转换成SSA形式，就可以更容易地转换成寄存器分配。这可以在多项式时间内通过图形着色来完成（流行的编译器是 LLVM）。这是一个非常复杂的话题，要在这里讨论。我建议您阅读该领域的几篇论文。
Efficiently Computing Static Single Assignment Form and the Control Dependence Graph 作者：Ron Cytron 等。他是SSA地区的开拓者之一。
A Simple, Fast Dominance Algorithm 作者：Keith D. Cooper 等
如果您不想将 SSA 作为中间步骤来处理，您可能想看看 Massimiliano Poletto 的 Linear Scan Register Allocation。这种贪心算法用于许多非基于 LLVM 的编译器，包括 v8 和 JVM。