Cranelift，第2部分：编译器效率，CFG和分支窥孔优化器

这篇文章是有关Cranelift的三部分系列文章中的第二篇。在第一篇文章中，我描述了Cranelift及其替代后台代码生成基础结构的项目的上下文，并详细说明了指令选择问题以及如何解决它。剩下的两篇文章将深入探讨一些有趣的工程问题。

在本文中，我想更深入地探讨我们工作中的编译器性能方面。 （在下一篇文章中，我们将探讨正确性。）我可以谈论编译速度的许多有趣方面，但是一个特别困难的问题是控制流的处理：我们如何将Wasm级别的结构化控制流转换为控制流在IR级别绘制图形，最后在机器代码级别以线性指令流分支？

有效地进行此翻译需要仔细注意整个过程的结构，当一个人可以完全消除一类工作时，最大的胜利就来了。我们将如何将传统降低设计中的几次通过（临界边缘分割，块排序，冗余块消除，分支松弛，分支目标分辨率）组合为在其他通过（降低CLIF或Cranelift IR）时会发生的内联变换，转换为机器专用的IR；然后再转换为二进制发射）。

这篇文章基本上描述了MachBuffer，这是一个“智能机器代码缓冲区”，它了解分支并在发出分支时即时编辑它们，以及BlockLoweringOrder，它使我们能够以最终的基本块顺序降低代码，并使用splitcritical通过遍历从未实现的隐式图来隐式插入边。这项工作主要在Cranelift PR＃1718中完成，在CPU密集型基准（bz2）上，编译时性能提高了约10％，编译+运行时性能提高了约25％。

在讨论其中任何一项之前，我们需要查看控制流程图（CFG）！ CFG是几乎所有现代编译器中使用的基本数据结构。简而言之，它代表执行（即程序控制）如何流经指令，使用图形节点表示指令的线性序列，并使用图形边缘表示分支指令处所有可能的控制流转移。

在上一篇文章中了解的指令选择过程结束时，我们将一个函数主体简化为包含基本块的VCode。基本块是连续的指令序列，除了结尾处没有出站分支，除了开头没有其他入站分支。换句话说，它是“直线”代码：执行总是从顶部开始，一直到结束。下面显示了一个由四个基本块组成的示例控制流图（CFG）：

控制流图是供编译器使用的出色数据结构。通过将执行流程明确地显示为图形边缘，而不是按处理器中的处理顺序按顺序对指令进行推理，可以更轻松地执行许多分析。例如，由于CFG使遍历所有可能的控制流变得容易，因此可以轻松解决数据流分析问题。程序的基于图的表示形式还允许更轻松地移动和插入代码：操作显式图比解释隐式控制流（例如，由于未采用条件分支导致的失败）容易出错。最后，图形表示法排除了块排序的问题，这对性能可能很重要。我们可以通过选择如何序列化graphnodes（块）来分别解决这个问题。由于这些原因，大多数编译器IR（包括Cranelift的CLIF和VCode）都基于CFG。

（历史记录：控制流图是由已故的Frances Allen发明的，他在很大程度上建立了现代编译器使用的算法基础。她的论文“优化转换目录” 1基本上涵盖了当今使用的所有重要优化，非常值得一读。）

为了在指令级别上表示CFG的块末分支，我们可以使用双向分支：这是在某些条件为true时分支到一个基本块目标，在条件为false时分支到另一个基本块目标的指令。 （基本块也可以以简单的无条件单目标分支结尾。）我们在上面编写了诸如ifr0，L1，L2之类的分支。这意味着将根据r0中的值在块L0之后执行L1或L2。 2

但是，CPU很少有这样的双向分支指令。取而代之的是，普通ISA中的条件控制流几乎总是带有带有失败的条件分支。这是一条指令，如果满足某些条件，则转移到另一个位置；否则，不执行任何操作，并允许顺序执行。出于多种原因，这更适合于硬件实现：编码一个目标要比两个目标更容易（对于某些分支，跳转的目标可能相距很远，并且指令具有有限的可用位），通常是这种情况无论如何，编译器可以立即放置后续块之一。

现在，如果我们只想要一个工作正常的编译器，而不是双向分支，就没什么问题了

br_if分支到L1或掉到无条件的goto。但这在许多情况下不是那么有效。考虑一下如果我们按L0，L2，L1，L3的顺序布置基本块会发生什么：

L0：... br_if r0，L1转到L2 L2：...转到L3 L1：...转到L3 L3：...返回

有两个冗余的无条件分支（goto指令），每个分支都无用地分支到以下指令。我们可以删除它们，而不会造成不良影响，可以利用它而不是失败，或者允许执行从一个块的结尾直接开始到下一个块的开始：

L0：... br_if r0，L1 // **否则落入L2 ** L2：...转到L3 L1：... // **始终落入L3 ** L3：...返回

这似乎是一个很容易解决的问题：我们只需要识别分支何时冗余并删除它，对吗？是的，但是在某些情况下我们可以做得更好。我们将在下面更深入地探讨这个问题！

到目前为止，我们已经以人工扫描的方式编写了机器指令，并使用标签引用了指令流中的位置。但是，在硬件级别上，这些标签不存在；相反，机器代码分支包含目标地址（通常被编码为与分支指令的相对偏移量）。换句话说，我们看不到goto L3，而是goto +32。

当从指令结构列表中发出机器代码时，这会引起一些复杂性。在最基本的层次上，我们必须将标签解析为偏移量，然后适当地修补分支。这类似于链接程序的工作（但比链接程序的工作低）：我们在确定放置位置后将符号解析为具体值，然后根据重定位来编辑代码以引用这些符号。换句话说，无论何时发出分支，我们都会做一个记录（在MachBackend中的位置，或“标签使用”），以便以后返回并使用解析的标签偏移量对其进行修补。

出现第二个更有趣的问题是因为并非所有分支指令都必须引用所有可能的标签！作为一个具体示例，在AArch64上，条件分支的范围为±1 MB，无条件分支的范围为±128 MB。这是出于指令编码的考虑：特别是指令大小固定的ISA（例如ARM，MIPS和RISC V），对于嵌入在指令字中的立即跳转偏移，可用的机器字不到完整位。 （指令本身总是一个机器字宽，并且我们还需要一些用于操作码和条件代码的位！）在x86上，我们有一个不同原因的限制：可变宽度编码允许一个字节的偏移量（允许± 128字节范围）或四字节偏移量（允许±2 GB范围）。

为了建立到遥远标签的分支，然后，在某些计算机上，我们需要使用与指令选择器默认选择不同的另一种分支，或者需要通过将原始分支定位到另一个分支来使用间接形式，后者为特殊形式。前者很棘手，因为在降低所有代码并计算位置之前，我们不知道目标是否在范围内。因此，我们需要乐观地或悲观地将下支行分别设为最短或最长的形式，并可能稍后再切换。更糟的是，当我们编辑分支以使用更短或更长时间的形式时，它们的长度可能会发生变化，从而使其他目标移入或移出范围；在最通用的解决方案中，这是一个“定点问题”，我们在其中进行迭代，直到不再发生任何更改为止。

到目前为止，我们已经有了产生正确机器代码的方法。为了发出两个目标分支的最终代码，我们可以发出条件跟随的无条件分支机器指令。为了正确解析分支目标，我们可以假定任何目标都可以在内存中的任何位置，并且始终使用分支的长格式；那么我们只需要最后一次通过，然后在我们知道偏移量的情况下填写它们即可。

但是，我们可以做得更好！下面，我将描述四个问题以及传统上解决这些问题的方式。

上面我们描述了一旦确定确定基本块将出现在最终二进制文件中的顺序，分支穿透就如何允许我们省略一些无条件分支。尤其是将r0，label_if_true，label_if_false的双向分支简单降低到两个单向分支

具有完全冗余且无用的goto！通常，如果下一个指令是branchtarget，则可以删除该分支。

但是，在有些更复杂的情况下，我们也可以找到一些改进。考虑上述内容的反向版本：

这里没有分支分支到其失败，因此可能会认为两个分支都是必要的。但是实际上，在大多数CPU架构上，所有条件分支的形式都是相反的。例如，可以将x86指令JE（如果相等则跳转）转换为JNE（如果不相等则跳转）。如果也允许编辑分支条件，则可以将以上内容重写为：

有时，经过优化后，除了最终的无条件分支外，基本块完全为空。当优化if或else块中的所有代码或将其移到函数体中的其他位置时，可能会发生这种情况。当插入块以分割临界边缘时，也会发生这种情况（请参见下文）。

因此，常见的优化是跳转线程：当一个分支直接指向另一个分支时，我们只需编辑第一个分支即可指向最终目标。概括地说，我们可以“遍历”任意数量的分支以消除中间步骤。例如：

请注意，中间分支未删除：它们可能仍然是其他分支的目标。从第一个分支开始时，我们将跳过它们。但是，如果我们知道未使用这些分支的其他方式，则可以删除它们，从而减小代码大小。

如上所述，“分支松弛”问题是我们必须为每个分支指令选择多种形式中的一种，每种形式都可能具有不同的范围（与当前程序计数器位置的最大距离）。这很复杂，因为所需范围取决于分支及其目标的最终位置，而分支的最终位置又取决于机器代码中指令的大小。但是其中一些指令本身就是分支。因此，我们具有循环依赖关系。

总会有某种方法可以分支到处理器地址空间中的任意位置，因此始终存在使用最坏情况的分支形式的琐碎但效率低下的解决方案。但是，我们通常可以做得更好，因为大多数分支的偏移量相对较小。

解决此问题的常用方法涉及“定点计算”：一个不断进行改进直到不遗余力的迭代循环。这就是分支放松的“放松”的来源：当我们发现目标在范围内时，我们修改分支指令以具有更优化的形式。然后，我们重新计算代码偏移量，看看是否可以启用其他松弛。只要分支范围和分支指令大小之间的关系是单调的（所需范围越小，指令越短），它将始终收敛到唯一的固定点；但是它可能很昂贵，并且如果我们希望代码编辑和/或偏移重新计算速度更快，则会涉及粘性数据结构设计问题。

由于多种原因，我们通常希望在控制流图中拆分临界边。关键边缘是指来自具有多个外边缘的块并到达具有多个内边缘的块的任何控制流传输边缘。每当程序遇到关键边缘时，有时我们都需要插入一些代码才能运行：例如，寄存器分配器可能需要“修正”机器状态，从而按目标块的预期在寄存器中移动值。考虑一下我们可以在哪里插入这样的代码：我们不能在跳转之前插入它，因为无论采用什么边缘，该代码都可以执行。同样，我们无法将其插入跳转目标，因为这将对目标块中的任何条目执行，而不仅仅是在特定边沿上转移。

解决方案是“分割”关键边缘：即创建一个新基本块，编辑分支以指向该块，然后在该块中创建一个到原始目标的无条件分支。这个基本块是我们可以插入所需的任何固定代码的地方，并且仅在控制流从一个特定块转移到另一个特定块时才执行。下图显示了临界边缘拆分：

有多种方法可以解决此问题：我们可以抢先分割每个关键优势；或者我们可以仅在需要插入代码时才拆分需求。后者需要就地编辑CFG，并且由于各种原因，我们宁愿避免这样做：它会使许多分析结果无效，并使数据结构复杂化。如果我们可以假设边缘已经被分割，那么对许多算法进行推理也要简单得多。但是，拆分每个边缘将留下许多空白块，因为我们通常不需要在边缘上插入任何固定代码。此外，拆分边缘还带来了将拆分块插入哪里的问题。如果我们采用最简单的方法并将其附加到函数的末尾，则可能会通过简化来显着减少分支落入的数量。将块放置在其前任或后继位置附近的智能启发式方法会更好。

解决所有这些问题的传统方法是将任务分解为多个遍，并使用这些遍执行就地编辑。例如，在LLVM中，IR可以简化为机器特定的形式（MachineBasicBlocks的MachineFunction），具有明确的布局概念和机器级别的分支指令。然后进行编辑，注意在布局更改时更新分支。

计算可达性，并删除“死块”（不再可达的块）。 （也由LLVM中的BranchFolding完成。）

计算一个试图最小化跳跃距离的程序段顺序，并在可能的情况下在每个程序段之后直接放置至少一个后继程序。 （在LLVM中，为MachineBlockPlacementpass。）

使用此块顺序将来自CFG节点的代码线性化为单个机器指令流。 （在LLVM中，块最初被降低到MachineFunction中，然后由MachineBlockPlacement重新排序。）

假设每个分支的最坏情况下的大小，根据当前指令序列的机器代码大小计算块偏移。

扫描分支，检查块位置是否由于目标较近而允许格式较短。如果是这样，更新分支并重新计算块偏移。继续直到定点。 （在LLVM中，BranchRelaxation这样做。）

使用最终偏移量填写分支目标。分支现已准备就绪，可以发出机器代码。

显然，这是可行的，并且经过谨慎处理（尤其是在块放置启发法中），它将产生非常好的代码。但是上述步骤需要许多就地编辑。这既很慢（每次编辑代码时我们都要做一些工作），并且迫使我们使用允许进行此类编辑的ata结构（例如链表），这对IR上的所有其他操作都加了税。有没有更好的办法？

如果能够避免上述某些代码转换过程，那将是理想的；我们可以吗？事实证明，作为其他现有工作的一部分，一个人实际上可以完成上述所有工作：

我们可以提前确定最终的块顺序，并按此顺序降低CLIF到VCode的顺序，因此无需重新排序VCode。它已经线性化。我们还可以插入临界边缘拆分作为此降低操作的一部分。

在机器代码发出期间，我们可以通过流方法完成所有其他工作-反转条件，线程跳转，清除死块以及处理各种分支大小！关键的见解是，我们可以执行某种“窥孔优化”：我们可以立即删除并重新发射发射缓冲区尾部的分支。通过在单次发射扫描期间跟踪一些辅助状态，例如可达性，当前发射点处的标签，代码前面的未解析标签引用列表以及短距离分支的“最后期限”，我们可以做所有需要做的事情，而无需做任何事情在缓冲区末尾备份多个连续的分支。

作为上一篇文章中描述的指令选择管道的一部分，我们需要遍历CLIF中的基本块，并针对每个块将其代码降低为VCode指令。我们希望以与最终机器代码布局相同的顺序进行此迭代，这样我们以后就无需重新排序VCode。

降低算法所施加的唯一约束是weexamine在value defs之前使用value，这可以通过在其任何支配者之前访问块来确保。这就给我们如何降低工作留了很多自由。

如果这是整个问题，那么我们可以做一个遍历后遍历并完成它。实际上，这个问题还由于另一个因素而变得复杂：临界边缘分裂！

回想一下我们在上面描述的内容，我们必须先抢先分割所有关键边缘，否则必须找到一种以后进行就地编辑的方法。为了避免就地编辑的复杂性，我们选择将它们全部分割。请注意，就我们的CFG降低而言，这是便宜的，因为我们以后的分支优化将几乎免费地删除空块。 （随着块数的增加，寄存器分配器的分析可能会变得更加昂贵，但实际上，我们发现这并不是一个大问题。）

挑战在于在飞行中的正确位置生成这些块。为了生成降序，我们定义了一个虚拟图，该图从未实际实现，其节点由CLIF块和边（每个CLIF边变为裂边块）隐含，而其边仅由后继函数定义。为了生成降序，我们对虚拟图执行深度优先搜索，记录后序。保证可以根据需要在defs之前查看此postorder的用法。 DFSitself是一个很好的启发式块放置方法：它将趋向于将结构化控制流代码分组到其层次单元中。

该实现中还有其他细节，可确保我们仅分割关键边缘而不是所有边缘，并在生成降低的块时直接记录块后继信息，以便后续后端阶段无需重新计算，以及其他一些小的优化。

下图对此进行了说明，该图显示了CLIF级别CFG，该CFG级别已用分割边缘和合并的边缘块进行了转换，然后线性化了ata概念级别；

......