BOLT：二进制优化器

2024-03-12 11:58:08　　点击量：

BOLT:一种实用的数据中心及其它场景的二进制优化器

随着计算不断向数据中心发展，大规模应用程序的性能优化最近变得更加重要。数据中心应用程序通常非常庞大和复杂，这使得代码布局成为提高其性能的重要优化。这促使最近研究了在编译时和链接时改进代码布局的实用技术。尽管链接后优化器在过去取得了一些成功，但最近没有任何工作探讨其在现代数据中心应用中的好处。

在本文中，我们介绍了BOLT（Binary Optimization and Layout Tool.），一个建立在LLVM框架之上的链接后优化器。利用基于样本的分析，BOLT提高了现实世界应用程序的性能，即使是使用反馈驱动优化（FDO）和链接时间优化（LTO）构建的高度优化的二进制文件也是如此。我们证明了链接后性能的改进是对传统编译器优化的补充，即使后者是在整个程序级别和存在profile文件信息的情况下进行的。我们在Facebook数据中心工作负载和开源编译器上对BOLT进行了评估。对于数据中心应用，BOLT在配置文件引导的功能重新排序和LTO的基础上实现了高达8.0%的性能加速。对于GCC和Clang编译器，我们的评估显示，BOLT在FDO和LTO的基础上将其二进制文件的速度提高了20.4%，如果在没有FDO和LTEO的情况下构建二进制文件，则可提高52.1%。

字节PGO优化经验：https://juejin.cn/post/7187660471384670267

鉴于数据中心规模庞大，优化其工作负载最近引起了人们的极大兴趣。现代数据中心应用程序往往是非常庞大和复杂的程序。由于这些应用程序的代码量太大，因此优化代码位置对于提高其性能非常重要。

数据中心应用程序的大尺寸和性能瓶颈使其成为反馈驱动优化（FDO）的良好目标，也称为Profiling引导优化（PGO），尤其是代码布局。同时，这些应用程序的巨大规模也给将FDO应用于它们带来了可扩展性挑战。基于instrumentation的profiling产生大量的内存和计算性能成本，通常使从生产系统收集准确的profiling变得不切实际。为了简化部署并提高采用率，希望有一个系统可以从正常生产环境中运行的未经修改的二进制文件中获得FDO的profiling数据。这可以通过使用基于样本的Profile文件来实现，这使得能够以最低的操作复杂性收集高质量的配置文件。这是Ispike[21]、AutoFDO[6]和HFSort[25]等工具所采用的方法。同样的原理也被用作本文中提出的BOLT工具的基础。

通过采样获得的profiling数据可以在编译链中修改为多个点。使用profiling文件数据的点可以从编译时间（例如AutoFDO[6]）到链接时间（例如LIPO[18]和HFSort[25]），再到链接后时间（例如Ispike[21]）而变化。通常，在编译链中，profiling文件信息插入得越早，其影响的可能性就越大，因为更多的阶段和优化可以从这些信息中受益。这一好处推动了最近关于编译时和链接时FDO技术的工作。同时，链路后优化，过去是由Spike[8]、Etch[28]、FDPR[11]和Ispike[21]等一系列专有工具探索的，近年来没有引起太多关注。我们认为，对后链接优化缺乏兴趣是由于民间传说和直觉，即这种方法较差，因为profiling文件数据在编译链中注入得很晚。

在本文中，我们证明了上述直觉是不正确的。我们在这项工作中利用的重要见解是，尽管在编译链中较早地注入profiling文件数据可以通过更多的优化来使用它，但稍后注入这些数据可以更准确地使用信息，以实现更好的代码布局。事实上，AutoFDO的主要挑战之一是将在二进制级别收集的profiling文件数据映射回编译器的中间表示[6]。在用于生成收集profile文件数据的二进制文件的原始编译中，在发出机器代码之前，编译器和链接器会对代码进行许多优化。在二进制级别操作的链接后优化器中，这个问题要简单得多，从而可以更准确地使用profiling文件数据。这种准确性对于诸如代码布局之类的低级优化尤其重要。

我们在我们构建的名为BOLT的静态二进制优化器的上下文中演示了上述发现。BOLT是一个现代的、可重定目标的二进制优化器，构建在LLVM编译器基础设施之上[16]。我们对大型实际应用程序的实验评估表明，BOLT可以在FDO和LTO的基础上提高高达20.41%的性能。此外，我们的分析表明，这种改进主要是由于在二进制级别更准确地使用了基于样本的配置文件数据，从而改进了代码布局。

总体而言，本文做出了以下贡献：

1.它描述了在LLVM基础设施之上构建的现代开源链接后优化器的设计。1

2.它从经验上证明，与基于编译器的方法相比，链接后优化器能够更好地利用基于样本的评测数据来改进代码布局。

3.它表明编译时间、链接时间和链接后时间FDO都不能取代其他FDO，而是互补的。

本文组织如下。第2节介绍了使用基于样本的分析和静态二进制优化来提高大规模应用程序性能的情况。然后，第3节描述了BOLT二进制优化器的体系结构，然后在第4节中描述BOLT实现的优化，并在第5节中讨论了分析技术。第6节介绍了BOLT的评估以及与其他技术的比较。最后，第7节讨论了相关工作，第8节对论文进行了总结。

在本节中，我们将介绍BOLT使用的链接后优化方法。

图表 1 编译管道示例和改进样本profile数据的各种替代方案

反馈驱动优化（FDO）已被证明有助于增加代码优化在各种系统中的影响（例如[6，9，13，18，24]）。该领域的早期开发依赖于基于instrumentation的profiling分析，这需要应用程序的特殊检测构建来收集概要数据。这种方法有两个缺点。首先，它使构建过程复杂化，因为它需要对概要文件集合进行特殊的构建。其次，插装通常会导致非常大的CPU和内存开销。这些开销通常使插入指令的二进制文件不适合在实际生产环境中运行。

为了增加FDO在生产环境中的采用，最近的工作研究了基于样本分析的FDO风格技术[6，7，25]。这些技术依赖于使用现代CPU中可用的硬件配置文件计数器（如英特尔的最后分支记录（LBR）[15]）进行更便宜的采样，而不是instrumentation。这种方法更具吸引力，不仅因为它不需要特殊的应用程序构建，还因为配置文件收集开销可以忽略不计。通过解决基于instrumentation的FDO技术的两个主要缺点，基于样本的分析增加了在复杂的真实世界生产系统中采用FDO风格的技术[6，25]。出于同样的实际原因，我们选择在这项工作中使用基于样本的评测。

基于示例的profile文件数据可以在编译管道的各个级别上加以利用。图1显示了将源代码转换为机器代码的通用编译管道。如图1所示，profile文件数据可以在不同的程序表示级别注入，从源代码到编译器的中间表示（IR），到链接器，再到链接后优化器。通常，任何FDO工具的设计者都面临以下权衡。一方面，在管道中较早地注入配置文件数据可以使管道中的更多优化从这些数据中受益。另一方面，由于基于样本的配置文件数据必须在二进制级别上收集，因此级别越接近该表示，数据映射回该级别的程序表示的准确性就越高。因此，链接后二进制优化器允许以最大的准确性使用配置文件数据。

图表 2 示例显示了将二进制级别的事件映射回高级代码表示的挑战。

AutoFDO[6]将profile文件数据回溯到编译器的中间表示（IR）中。Chen等人[7]量化了profile文件数据的精度，即使在GCC编译器中以合理的低级别表示对profile文件数据进行改造也会损失该精度。他们量化了profile数据的准确率为84.1%，通过该工作中描述的一些技术，他们能够将准确率提高到92.9%。

图2中的示例说明了将二进制级别的性能事件映射回更高级别的表示的困难。在本例中，函数bar和bazcall函数foo都被内联在两个调用程序中。函数foo在第（02）行包含if语句的一个条件分支。对于像这样的前向分支，在现代处理器上，使最常见的后续分支是fall-through是有利的，这可以带来更好的分支预测和指令缓存位置。这意味着，当foo内联到bar中时，块B1应该放在B2之前，但当内联到baz中时，这些块应该按相反的顺序放置。当在二进制级别对该程序进行分析时，将对与第（02）行中的if对应的两个分支进行分析，一个在bar内，另一个在baz内。假设函数bar和baz在运行时执行的次数相同。然后，当将分支频率映射回图2中的源代码时，可以得出结论，第（02）行的分支有50%的机会同时分支到B1和B2。而且，在bar和baz中内联foo之后，编译器将无法判断在每种情况下什么布局是最好的。请注意，尽管在执行函数内联后，可以通过将profile文件数据注入较低级别的表示来缓解此问题，但如果foo是在与bar和baz不同的模块中声明的，则这并不能解决问题，因为在这种情况下，内联要到链接时才能发生。

由于我们最初开发BOLT的动机是改进大规模数据中心应用程序，其中代码布局起着重要作用，因此链接后二进制优化器非常有吸引力。传统的代码布局技术高度依赖于准确的分支频率[26]，使用不准确的profile文件数据实际上会导致性能下降[7]。尽管如此，正如我们前面提到的，在非常低的级别提供profile文件信息会阻止编译管道中的早期优化利用这些信息。因此，使用这种方法，我们想要从profile文件数据中受益的任何优化都需要在二进制级别上应用。幸运的是，代码布局算法相对简单，易于在二进制级别应用。

上面概述的二进制级优化器的好处可以静态地或动态地利用。我们之所以选择静态方法，有两个原因。第一个是方法的简单性。第二是没有运行时开销。尽管动态二进制优化器在过去取得了一些成功（例如，Dynamo[2]、DynamoRIO[5]、StarDBT[29]），但这些系统会产生大量开销，这与提高目标应用程序整体性能的主要目标背道而驰。换言之，这些系统需要表现得非常好，才能恢复其开销并实现净性能胜利。不幸的是，由于它们需要保持较低的开销，这些系统通常必须实现更快、次优的代码优化。这对采用动态二进制优化器来说是一个普遍的挑战，因为它们不适合所有应用程序，如果调整不好，很容易降低性能。与静态优化器相比，动态二进制优化器的主要好处是能够处理动态生成和自修改的代码。

大规模数据中心二进制文件可能包含来自多种源代码语言（包括汇编语言）的超过100MB的代码。在本节中，我们将讨论我们为在该场景中操作而创建的BOLT二进制优化器的设计。

我们通过逐步增加其二进制代码覆盖率来开发BOLT。起初，BOLT只能优化有限的一组函数的代码布局。随着时间的推移，通过增加对更复杂函数的支持，代码覆盖率逐渐增加。即使在今天，BOLT仍然能够在处理和优化其他函数的同时保持二进制中的一些函数不变，保守地跳过违反其当前假设的代码。

最初的实现以x86 64 Linux ELF二进制文件为目标，完全依赖ELF符号表来指导二进制内容识别。通过这样做，BOLT能够在现有的函数边界内优化代码布局。当BOLT不能完全自信地重建给定函数的控制流图时，它只会保持函数不变。

由于代码布局优化的性质，有效代码大小可能会由于以下几个原因而增加。首先，这可能是由于冷路径上分支数量的增加。其次，x86的条件分支指令有一个特殊之处，如果到目的地的（带符号）偏移量适合8位，则它占用2个字节，而对于32位偏移量，则占用6个字节。自然地，将冷代码移得更远会显示出增加热代码大小的趋势。如果优化后的函数不适合原始函数的分配空间，BOLT将拆分冷代码并将其移动到新创建的ELF段。请注意，这种函数拆分是非自愿的，除了允许代码拉直优化之外，没有提供任何额外的好处，因为BOLT没有填充拆分点和下一个函数之间的空闲空间。

后来增加了第二种更雄心勃勃的模式，通过改变二进制中所有函数的位置来操作。虽然考虑了多种方法，但最明显和最直接的方法是依靠链接器在可执行文件中记录和保存的重新定位。BFD和Gold链接器都提供了这样的选项（--emit relocas）。然而，即使有了这个选项，仍然有一些信息缺失。一个例子是链接器删除的PIC跳转表的相对偏移量。其他示例是一些即使对链接器也不可见的重定位，例如单个编译单元内本地函数的跨函数引用（它们由编译器内部处理）。因此，为了检测和修复此类引用，在尝试重新排列二进制中的函数之前，正确地反汇编所有代码是很重要的。尽管如此，随着迁移，获得对代码重写的完全控制的工作变得容易多了。处理重定位使BOLT能够更改二进制和拆分函数体中函数的顺序，以进一步提高代码的局部性。

由于链接器可以访问重定位，因此可以将它们用于类似的二进制优化。然而，仅x86 Linux就有多个开源链接器，哪一个链接器用于任何特定的应用程序取决于许多情况，这些情况也可能随着时间的推移而变化。因此，为了促进该工具的采用，我们选择编写一个独立的链接后优化器，而不是绑定到特定的链接器。

分析任意二进制并定位代码和数据并非易事。事实上，在一般情况下，精确分解机器代码的问题是不可决定的。在实践中，可用的信息不仅仅是一个入口点，BOLT依赖于正确的ELF符号表信息来进行代码发现。由于BOLT使用64位Linux二进制文件，ABI需要包含函数边界的函数框架信息。虽然BOLT可能依赖于这些信息，但通常情况下，在汇编中编写的函数会省略框架信息。因此，我们决定在可用时使用符号表和帧信息的混合方法。

图表 3 显示BOLT的二进制重写管道的图。

图3显示了BOLT重写步骤的示意图。函数发现是第一步，将函数名称绑定到地址。稍后，将检索调试信息和profile文件数据，以便可以开始对各个函数进行反汇编。

BOLT使用LLVM编译器基础设施[16]来处理二进制文件的反汇编和修改。LLVM非常适合BOLT有几个原因。首先，LLVM有一个很好的模块化设计，可以相对轻松地开发基于其基础设施的工具。其次，LLVM支持多个目标体系结构，这使得可以轻松地重新定位工具。为了说明这一点，ARM架构的工作原型在不到一个月的时间内实现了。除了汇编程序和反汇编程序之外，LLVM的许多其他组件在构建BOLT时也被证明是有用的。总的来说，这个使用LLVM的决定效果很好。LLVM基础设施实现了一个健壮且易于重定目标的二进制优化器的快速实现。

如图3所示，重写流水线的下一步是为每个函数构建控制流图（CFG）表示。CFG是使用LLVM的Tablegen生成的反汇编程序提供的MCInst对象构建的。BOLT通过分析在反汇编过程中遇到的任何分支指令来重建控制流信息。然后，在CFG表示中，BOLT运行其优化管道，第4节对此进行了详细解释。对于BOLT，我们在MCInst中添加了一个通用注释机制，以便于进行某些优化，例如作为记录数据流信息的一种方式。最后的步骤包括发出函数，并使用LLVM的运行时动态链接器（为LLVM JIT系统创建）来解析函数和本地符号（如基本块）之间的引用。最后，用新的内容重写二进制，同时更新ELF结构以反映新的大小。

表格 1 transformations序列在BOLT优化管道中的应用

BOLT能够识别DWARF[10]信息，并对其进行更新，以反映重写过程中执行的代码修改和重新定位。

图4显示了CFG转储的一个示例，演示了BOLT对函数的前两个基本块（带有C++异常和throw语句）的二进制文件的内部表示。该功能非常小，总共只有五个基本块，每个基本块都可以自由地重新定位到另一个位置，除了入口点。DWARF调用帧信息（CFI）指令的占位符用于注释帧状态更改的位置（例如，当堆栈指针前进时）。BOLT基于这些注释为新的二进制文件重建所有CFI，以便在引发异常时框架展开器能够正常工作。偏移量0x00000010处的callq指令可能引发异常，并具有指定的着陆板，如其旁边显示的着陆板注释所示（处理程序：.LLP0；操作：1）。行上的最后一个注释指示每个机器级指令的源行原点。

BOLT运行带有代码转换或分析的过程，类似于编译器。BOLT还配备了数据流分析框架，将信息提供给需要它的通道。这使BOLT能够检查给定程序点的寄存器活跃度，Ispike[21]也使用了这一技术。有些通行证是独立于体系结构的，而另一些则不是。在本节中，我们将讨论应用于Intel x86 64目标的过程。

表1按顺序显示了每个单独的BOLT优化pass。例如，第一行在管道开始处显示条形图。请注意，Pass 1和Pass 4的重点是利用精确的目标体系结构信息来删除或更改一些指令。BOLT用于数据中心应用程序的一个用例是允许用户在指令空间中进行任何可选选择，以支持I-cache空间，例如删除对齐NOP和AMD友好的REPZ字节，或者使用较短版本的指令。我们的研究结果表明，对于大型应用程序，最好积极减少I缓存占用，除非这种变化会导致D缓存开销，因为缓存是数据中心空间中最受约束的资源之一。这解释了BOLT在读取输入二进制文件后丢弃所有NOP的策略。尽管compilergented alignment NOP通常是有用的，但它们所需的额外空间并没有得到回报，简单地将它们从二进制文件中剥离可以提供微小但可衡量的性能改进。

Pass2：BOLT具有相同的代码折叠（ICF）功能，以补充链接器所做的ICF优化。在二进制级别执行ICF的另一个好处是能够优化在没有-ffunction sections标志的情况下编译的函数和包含跳转表的函数。因此，BOLT能够折叠比连接体更多相同的功能。我们已经测量到HHVM二进制[1]的代码大小在链接器的ICF过程之上减少了约3%。

pass3（间接调用提升）、pass5（内联小函数）和pass7（PLT调用优化）利用调用频率信息消除函数调用或将其转换为性能更高的版本。我们注意到BOLT的函数内联是编译器在更高级别上执行的功能的有限版本。我们预计编译器将利用大多数内联机会（可能使用FDO）。BOLT的其余内联机会通常由更准确的配置文件数据、BOLT的间接呼叫促进（ICP）优化、跨模块性质或这些因素的组合暴露出来。[w(1]

Pass 6，加载指令的简化，通过从静态已知值（只读部分）中获取数据来探索一个棘手的折衷方案。在这些情况下，BOLT可以将加载转换为即时加载指令，从而减轻D高速缓存的压力，但可能会增加I高速缓存上的压力，因为数据现在被编码在指令流中。在这种情况下，BOLT的策略是，如果新的指令编码大于原始加载指令，则中止升级，即使这意味着要避免计算成本更高的加载指令。然而，我们发现这样的机会在我们的工作量中并不常见。

Pass 9，重新排序和拆分热/冷基本块，根据最频繁执行的路径重新排序基本块，因此最热的后续块很可能是一个故障，从而减少所采取的分支并缓解分支预测器单元的压力。

最后，Pass 13通过HFSort技术对函数进行重新排序[25]。这种优化主要提高了I-TLB的性能，但也在较小程度上有助于I-cache。结合pass 9，这些是BOLT中最有效的方法，因为它们直接优化了代码布局。

本节讨论了在尝试生成准确的profiling数据时，不同的基于样本的分析技术的陷阱和注意事项。

在最近的英特尔微处理器中，LBR是最后32个分支的列表。LBR对于轮廓引导优化很重要，不仅因为它们为关键边提供了准确的计数（即使使用完美的基本块计数轮廓[17]也无法推断），还因为它们使块布局算法对不良采样更有弹性。当评估几个不同的采样事件来收集BOLT的LBR时，我们发现即使对于不同的采样活动，LBR模式下的性能影响也是非常一致的。我们在Intel x86上用多个硬件事件收集LBR数据，包括失效的指令、执行的分支和循环，还用不同级别的基于事件的精确采样（PEBS）进行了实验[15]。在所有这些情况下，对于BOLT提供5.4%加速的工作负载，性能差异在1%以内。在非LBR模式下，与LBR相比，使用带有非理想算法的有偏事件来推断边缘计数可能会导致高达5%的性能损失，这意味着它几乎错过了所有的优化机会。一项调查表明，在本示例工作负载中，非LBR技术可以调整为比LBR差1%以下，但如果处理器中有LBR，则最好使用它来获得更高、更稳健的性能数字。我们还在第6.5节中评估了HHVM的这种影响。

图表 4 带有C++异常的函数的部分CFG转储。

使用LBR，在假设的最坏情况偏置场景中，一个函数中的所有样本都记录在同一个基本块中，BOLT将按照通往该块的路径的顺序排列块。这是一个不完整的布局，错过了后续块的排序，但它既不是无效的，也不是冷路径。相反，当试图用非LBR样本推断相同的边缘计数时，情况是单个热基本块的情况，而没有关于到达它的路径的信息。

在实践中，即使在LBR模式下，收集到的配置文件也有很多次是矛盾的，因为它指出前辈执行的比单个继任者多很多倍，以及其他违反流动方程的行为。2先前的工作[17，23]，其中包括在IBM的FDPR[12]中实现的技术，报告通过解决最小成本流（MCF[17]）的实例（图网络流问题）来处理重构边缘计数的问题。然而，这些报告早于LBR。LBR只存储获取的分支，因此当处理非常偏斜的数据（如上述情况）时，BOLT通过将所有剩余流量归因于LBR中自然缺失的未获取路径来满足流量方程，类似于Chen等人[7]。BOLT还受益于在静态编译器之后应用：为了应对不确定性，通过对直通路径施加权重，它信任静态编译器完成的原始布局。因此，程序跟踪需要显示大量的分支，这些分支与编译器所做的原始布局相矛盾，以说服BOLT重新排序块并更改原始直通路径。如果没有LBR，就不可能利用这一点：算法从对采取和未采取分支的猜测开始，而不确定采取的分支，即在LBR模式下被视为理所当然的分支，是真实的还是错误的边缘计数推断的结果。

BOLT使用HFSort[25]基于加权调用图执行函数重新排序。如果使用LBR，则直接从分支记录推断调用图的边权重，分支记录也可能包括函数调用和返回。然而，在没有LBR的情况下，BOLT仍然能够通过查看二进制文件中的直接调用并创建具有与包含相应调用指令的块中记录的样本数量相对应的权重的调用者-被调用者边来构建不完整的调用图。然而，这种方法不能将间接调用考虑在内。即使有这些限制，我们也没有观察到像使用非LBR模式进行基本块重新排序那样严重的性能损失（第6.5节）。

本节在各种场景中评估BOLT，包括Facebook服务器工作负载以及GCC和Clang开源编译器。在某些场景中，还提供了与GCC和Clang的PGO和LTO的比较。

本节中介绍的评估是在采用英特尔微处理器的基于Linux的服务器上进行的。

BOLT的影响是在Facebook数据中心内的五个二进制文件上测量的。第一个是HHVM[1]，这是一个PHP虚拟机，为Facebook和许多其他网站（包括百度和维基百科）的网络服务器提供动力。第二种是TAO[4]，这是一种高度分布式的内存数据缓存服务，用于存储Facebook的社交图。第三个是Proxygen，它是一个构建在同名开源库之上的集群负载均衡器[27]。最后，另外两个二进制文件实现了一个名为Multifeed的服务，该服务用于选择Facebook新闻提要中显示的内容。

在这次评估中，我们比较了BOLT对使用GCC构建的二进制文件和通过HFSort[25]进行的函数重新排序的性能影响。HHVM二进制文件专门使用LTO进行编译，以进一步提高其性能。不幸的是，无法与FDO和AutoFDO进行比较。FDO的困难是第2.1节中概述的在这些应用程序的正常生产环境中部署插入指令的二进制文件的常见困难。我们发现，我们的环境中最新版本的GCC（5.4.1版）对AutoFDO的支持并不稳定，这可能会导致内部编译器错误或与C++异常相关的运行时错误。然而，对于其他应用，BOLT和FDO之间的直接比较是可能的，结果如第6.2节所示。

图5显示了在我们的一组Facebook数据中心工作负载的HFSort之上应用BOLT的性能结果（在HHVM的情况下，也在LTO之上）。在所有情况下，BOLT的应用都导致了加速，HHVM的平均加速率为5.4%，最大加速率为8.0%。请注意，尽管HHVM包含大量未经BOLT优化的动态编译代码，但它在静态编译代码中花费的时间比在动态生成代码中花费更多。在这些应用程序中，HHVM具有最大的总代码大小，这使得它非常前端绑定，因此更适合BOLT实现的代码布局优化。

为了更好地了解BOLT的性能优势，我们对HHVM进行了更详细的性能分析。图6显示了BOLT对重要性能指标的改进，包括i-cache未命中、i-TLB未命中、分支未命中和LLC未命中。改进分支预测是BOLT进行的块布局优化的一个重要好处，对于HHVM来说，这一指标提高了11%。此外，提高局部性可以在整个缓存层次结构中获得更好的度量，特别是i-cache的第一级，它可以将未命中率降低18%。由于对跳转表进行了重新排序以进行位置和帧优化，第一级d缓存也可能有1%的小幅改进。观察到的TLB改进来自于将访问的指令和数据打包到更少的页面中。为了更好地说明如何改进缓存和TLB局部性，我们在第6.4节中介绍了地址空间访问的热图。

图表 5 BOLT为我们的一组Facebook数据中心工作负载提供了性能改进。

图表 6 HHVM微体系结构指标的改进。

图表 7 Clang的性能改进。

BOLT应该能够提高任何前端应用程序的性能，而不仅仅是数据中心工作负载。为了测试这个理论，我们在两个开源编译器上运行了BOLT：Clang和GCC。

图表 8 GCC的性能改进。与Clang不同的是，由于构建错误，我们没有使用LTO。

对于我们的Clang评估，我们使用了llvm、Clang和编译器rt开源存储库的release_60版分支[19]。我们首先构建了该编译器的引导发布版本。这个stage1编译器为我们的评估提供了一个基线。然后，我们构建了Clang，3的插入指令的版本，然后使用插装instrumentation的编译器使用默认选项再次构建Clang。收集的配置文件数据用于在启用LTO的情况下进行Clang的另一个构建。4在我们的图表中，这被称为PGO+LTO。

2个编译器中都与我们的训练输入（GCC的完整构建）一起进行了介绍。我们使用了带有选项的Linux perf工具：record -e cycles:u -j any,u。使用perf2bolt工具将perf中的配置文件转换为YAML格式（-w选项）。然后，该配置文件用于使用BOLT优化编译器二进制文件，并具有以下选项：

-b profile.yaml -reorder-blocks=cache+

-reorder-functions=hfsort+ -split-functions=3 -split-all-cold

-split-eh -dyno-stats -icf=1 -use-gnu-stack

然后使用这四个编译器来构建Clang，并测量总体构建时间以进行基准测试。对于上面的所有构建，我们使用了ninja而不是GNU make，对于所有基准测试，我们使用-j40 clang选项运行它们。我们选择只构建clang二进制文件（而不是完全构建），以最大限度地减少链接时间对评估的影响。

我们还选择了3个Clang/LLVM源文件，大小从小到大，并对这些文件进行了预处理，这样它们就可以在不查找标头依赖关系的情况下进行编译。我们使用的3个源文件是：

l input1: tools/clang/lib/CodeGen/CGVTT.cpp

l input2: lib/ExecutionEngine/Orc/OrcCBindings.cpp

l input3: lib/Target/X86/X86ISelLowering.cpp

然后使用-std=c++11 -O2选项对每个文件进行多次编译，并记录结果以用于基准测试。测试在具有32GiB RAM的双节点20核（带超线程的40核）IvyBridge（英特尔（R）至强（R）CPU E5-2680 v2@2.80GHz）系统上运行。

对于我们的GCC评估，我们使用了版本8.2.0。首先，GCC是使用默认的构建过程构建的。这个引导构建的结果就是我们的基线。其次，我们使用以下配置构建了一个PGO版本：

--enable-linker-build-id --enable-bootstrap

--enable-languages=c,c++ --with-gnu-as --with-gnu-ld

--disable-multilib

然后，使用makeprofiledbootstrap生成我们的GCC PGO版本。

由于BOLT与GCC函数拆分不兼容，我们不得不重复上面的构建，将BOOT CFLAGS=-O2 -g -fno重新排序块和分区传递给make命令。生成的编译器，准备被BOLTed，用于再次构建GCC（我们的训练输入），这次没有引导。然后，使用perf2bolt将概要文件记录并转换为YAML格式，并使用BOLT对cc1plus二进制文件进行优化，该选项与Clang使用的选项相同，随后将其复制到GCC的安装目录中。

所有4种不同类型的GCC编译器，2种没有BOLT，2种有BOLT，后来都用于使用默认配置构建Clang编译器。

图7和图8分别显示了Clang和GCC的实验结果。通过使用BOLT，我们观察到两个编译器都有了显著的改进。在GCC和PGO的基础上，BOLT在完成Clang的完整构建时提供了7.45%的加速。在拥有LTO和PGO的Clang之上，当完成Clang的完整构建时，可加速15.0%。

表2显示了BOLT在为基线和应用PGO+LTO优化Clang二进制文件时报告的一些统计数据。这些统计数据基于输入的配置文件数据。即使在PGO+LTO之上应用，BOLT在其中许多度量中也有非常显著的影响，尤其是那些影响代码局部性的度量。例如，我们看到BOLT比PGO+LTO减少了44.3%（比基线减少了69.8%），这显著提高了i-cache的位置性。

使用BOLT的-report-bad-layout选项，我们检查了Clang用LTO+PGO构建的二进制文件，以识别包含冷基本块和热基本块交错的频繁执行的函数。结合选项-print-debug-info和-update-debug-sections，这使我们能够跟踪这些块的来源。使用这种方法，我们分析了在最热门的函数中出现的这种次优代码布局。我们的分析表明，大多数此类情况都源于图2中示例中所示的函数内联。图10展示了其中一个二进制级别的函数。此函数包含3个基本块，每个块对应于不同源文件中的源代码。在图10中，块用它们的概要文件计数（ExecCount）进行了注释。对应于块LFT680413的源代码并不冷，但当内联在这个特定的调用站点中时，它是非常冷的。通过在二进制级别上操作并以profile文件数据为指导，BOLT可以很容易地识别这些低效率并改进代码布局。

图9显示了使用Facebook生产流量运行的HHVM的指令地址空间的热图。图9a显示了通过I-cache为常规二进制文件获取的地址，而图9b显示了用BOLT处理的HHVM的地址。

图表 9 HHVM二进制指令内存访问的热图，不带和带BOLT。热量是对数刻度的。

图9b展示了BOLT如何将热代码打包在一起，以使用大约4MB的空间，而不是原来的148.2MB的范围。密集的热区外仍有一些活动，但相对较冷。BOLT的函数重新排序过程忽略了这些函数，因为它们有一个间接的尾部调用。BOLT将它可以完全理解的函数标记为一种简单的机制，即使它没有完全处理所有函数，也可以对二进制进行操作。这些都是不简单的函数。

间接尾部调用对于静态二进制重写器来说更具挑战性，因为很难猜测目标是另一个函数还是同一函数的另一个基本块，这可能会影响CFG。BOLT保持这些功能不变。这也解释了在Y=1和16X20的热区中大约160KB的大冷块：这个冷块是一个大的非简单函数的一部分，它的CFG没有被BOLT完全处理，所以它不像其他函数那样被拆分。

函数拆分和重新排序对于将冷的基本块移出热区域非常重要，BOLT在HHVM二进制文件中的绝大多数函数上都使用了这些技术。其结果是频繁执行的代码紧密打包，如图9b的Y=1所示，这对I-cache和I-TLB非常有利。

并非所有CPU供应商都支持硬件机制来收集最后分支的跟踪信息，例如Intel CPU上的LBR。我们比较了将它们用于BOLT剖面与依赖于没有此类痕迹的普通样本的影响。

图11总结了我们在3种不同场景中对HHVM不同指标的评估：使用HFSort重新排序函数，重新排序基本块和应用其他优化，以及两者都有（所有优化都打开）。例如，第一个数据集显示，通过LBR实现更准确的分析，执行的指令的总体减少了0.35%。如图6所示，通过在HHVM上使用BOLT，总CPU时间改进约为8%。图11向我们展示了使用LBR大约占这些改进的2%。此外，与函数重新排序相比，对基本块布局优化的影响更为显著。原因是基本块重新排序需要在基本块级别进行更细粒度的分析，而没有LBR则很难获得。

二进制或链接后优化器在过去已经被广泛探索。二进制优化通常有两个不同的类别：静态和动态，在程序执行之前或程序执行期间操作。链接后优化器（如BOLT）是静态二进制优化器。用于原型设计和测试动态二进制优化的大型平台是用于同一主机的DynamoRIO[5]或用于仿真的QEMU[3]。尽管由于优化本身，用wins来克服虚拟机的开销是很有挑战性的，但这些工具在执行动态二进制检测以分析程序执行（如Pin[20]所做的）或调试（这是Valgrind[22]的主要目标）时是有用的。

静态二进制优化器通常专注于低级程序优化，优选地使用关于将运行程序的精确主机的信息。MAO[14]是一个使用微体系结构信息重写程序的例子，尽管它重写源代码级汇编，而不是二进制本身。当然，静态优化器往往是特定于体系结构的。Ispike[21]是英特尔开发的链接后优化器，用于针对安腾体系结构的特殊情况进行优化。Ispike还采用了类似于BOLT的块布局技术，这是Pettis和Hansen[26]的变体。然而，尽管支持特定于体系结构的通道，BOLT是在LLVM[16]之上构建的，以使其能够轻松地移植到其他体系结构。Ottoni和Maher[25]提出了一种基于动态调用图的增强函数重新排序技术。BOLT在其一个过程中实现了相同的算法。

profile文件信息最常用于增强编译器，以基于运行时信息优化代码，例如AutoFDO[6]。后者也在数据中心应用程序（如BOLT）的背景下进行了研究。尽管AutoFDO和BOLT之间的增益存在一些预期的重叠，但由于这两种工具都执行布局，在本文中，我们证明了FDO（而不仅仅是AutoFDO）和BOLT的增益是互补的，两种工具可以一起使用以获得最大性能。

数据中心应用程序的复杂性往往导致大型二进制文件往往表现出较差的CPU性能，这是由于多个重要硬件结构（包括缓存、TLB和分支预测器）面临巨大压力。为了应对提高此类应用程序性能的挑战，我们创建了一个名为BOLT的后链接优化器，它构建在LLVM基础设施之上。BOLT的主要目标是重新组织应用程序的代码，以减少它们对那些重要硬件结构施加的压力。BOLT通过一系列优化实现了这一目标，特别关注代码布局。本文的一个关键见解是，链接后优化器在基于评测的基础上执行这些优化方面处于特权地位，甚至超出了编译器所能实现的范围。

我们在Facebook数据中心应用程序中测试了我们的假设，并获得了2%至8%的改进。与概要文件引导的静态编译器不同，BOLT不需要将概要文件数据修改回源代码，从而使概要文件更加准确。尽管如此，链接后优化器比编译器具有更少的优化。我们表明，这两种策略的优势结合在一起，而不是完全重叠，这表明使用这两种方法可以为大型前端应用程序带来最高的效率。为了说明这一点，我们测量了两个开源编译器GCC和Clang的性能改进，这两个编译器的特点是依赖于指令缓存性能的大型代码库。总体而言，BOLT在LTO和FDO的基础上为Clang实现了15%的性能改进。

[1]Keith Adams, Jason Evans, Bertrand Maher, Guilherme Ottoni,

Andrew Paroski, Brett Simmers, Edwin Smith, and

Owen Yamauchi. 2014. The Hiphop Virtual Machine. In Proceedings

of the ACM International Conference on Object Oriented

Programming Systems Languages & Applications. 777–

790.

[2]Vasanth Bala, Evelyn Duesterwald, and Sanjeev Banerjia.

2000. Dynamo: A Transparent Dynamic Optimization System.

In Proceedings of the ACM SIGPLAN Conference on

Programming Language Design and Implementation. ACM,

1–12.

[3]F. Bellard. 2005. QEMU, a fast and portable dynamic translator.

In USENIX Annual Technical Conference.

[4]Nathan Bronson, Zach Amsden, George Cabrera, Prasad

Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo,

Sachin Kulkarni, Harry Li, Mark Marchukov, Dmitri

Petrov, Lovro Puzar, Yee Jiun Song, and Venkat Venkataramani.

2013. TAO: Facebook’s Distributed Data Store for the

Social Graph. In Proceedings of the USENIX Conference on

Annual Technical Conference. 49–60.

[5]Derek Bruening, Timothy Garnett, and Saman Amarasinghe.

2003. An infrastructure for adaptive dynamic optimization. In

Proceedings of the International Symposium on Code Generation

and Optimization. IEEE, 265–275.

[6]Dehao Chen, David Xinliang Li, and Tipp Moseley. 2016.

AutoFDO: Automatic Feedback-directed Optimization for

Warehouse-scale Applications. In Proceedings of the International Symposium on Code Generation and Optimization.

12–23.

[7]Dehao Chen, Neil Vachharajani, Robert Hundt, Xinliang Li,

Stephane Eranian,Wenguang Chen, andWeimin Zheng. 2013.

Taming hardware event samples for precise and versatile feedback

directed optimizations. IEEE Trans. Comput. 62, 2

(2013), 376–389.

[8]Robert Cohn, D. Goodwin, and P. G. Lowney. 1997. Optimizing

Alpha executables on Windows NT with Spike. Digital

Technical Journal 9, 4 (1997), 3–20.

[9]James C. Dehnert, Brian K. Grant, John P. Banning, Richard

Johnson, Thomas Kistler, Alexander Klaiber, and Jim Mattson.

2003. The Transmeta Code Morphing Software: Using

Speculation, Recovery, and Adaptive Retranslation to Address

Real-life Challenges. In Proceedings of the International Symposium

on Code Generation and Optimization. 15–24.

[10]DWARF Debugging Standards Committee. 2017. DWARF

Debugging Information Format version 5.

[11]Ealan A Henis, Gadi Haber, Moshe Klausner, and Alex Warshavsky.

1999. Feedback based post-link optimization for

large subsystems. In Workshop on Feedback Directed Optimization.

13–20.

[12]E. A. Henis, G. Haber, M. Klausner, and A.Warshavsky. 1999.

Feedback based postlink optimization for large subsystems.

In Proceedings of the 2nd workshop on Feedback Directed

Optimization. 13–20.

[13]Urs H¨olzle and David Ungar. 1994. Optimizing Dynamicallydispatched

Calls with Run-time Type Feedback. In Proceedings

of the ACM Conference on Programming Language Design

and Implementation. 326–336.

[14]Robert Hundt, Easwaran Raman, Martin Thuresson, and

Neil Vachharajani. 2011. MAO – An Extensible Microarchitectural

Optimizer. In Proceedings of the 9th Annual

IEEE/ACM International Symposium on Code Generation

and Optimization. IEEE Computer Society, 1–10.

Intel Corporation. 2011. IntelR 64 and IA-32 Architectures

Software Developer’s Manual. Number 325384-039US.

[16]Chris Lattner and Vikram Adve. 2004. LLVM: A Compilation

Framework for Lifelong Program Analysis & Transformation.

In Proceedings of the International Symposium on Code Generation

and Optimization. 75–86.

[17]Roy Levin. 2007. Complementing incomplete edge profile by

applying minimum cost circulation algorithms.

[18]Xinliang David Li, Raksit Ashok, and Robert Hundt. 2010.

Lightweight Feedback-Directed Cross-Module Optimization.

In Proceedings of the International Symposium on Code Generation

and Optimization. 53–61.

[19]LLVM Community. 2018. The LLVM open-source code

repositories. Web site:

http://llvm.org/releases.

[20]Chi-Keung Luk, Robert Cohn, Robert Muth, Harish Patil,

Artur Klauser, Geoff Lowney, Steven Wallace, Vijay Janapa

Reddi, and Kim Hazelwood. 2005. Pin: Building Customized

Program Analysis Tools with Dynamic Instrumentation. In

Proceedings of the 2005 ACM SIGPLAN Conference on Pro-gramming Language Design and Implementation. ACM, 190–

200.

[21]C-K Luk, Robert Muth, Harish Patil, Robert Cohn, and Geoff

Lowney. 2004. Ispike: a post-link optimizer for the Intel

Itanium architecture. In Proceedings of the International Symposium

on Code Generation and Optimization. IEEE, 15–26.

[22]Nicholas Nethercote and Julian Seward. 2007. Valgrind:

A Framework for Heavyweight Dynamic Binary Instrumentation.

In Proceedings of the 28th ACM SIGPLAN Conference

on Programming Language Design and Implementation.

ACM, 89–100.

[23]Diego Novillo. 2014. SamplePGO: The Power of Profile

Guided Optimizations Without the Usability Burden. In Proceedings

of the 2014 LLVM Compiler Infrastructure in HPC.

IEEE Press, 22–28.

[24]Guilherme Ottoni. 2018. HHVM JIT: A Profile-guided,

Region-based Compiler for PHP and Hack. In Proceedings of

the 39th ACM SIGPLAN Conference on Programming Language

Design and Implementation. ACM, 151–165.

[25]Guilherme Ottoni and Bertrand Maher. 2017. Optimizing

Function Placement for Large-scale Data-center Applications.

In Proceedings of the International Symposium on Code Generation

and Optimization. IEEE, 233–244.

gramming Language Design and Implementation. ACM, 190–

200.

[21]C-K Luk, Robert Muth, Harish Patil, Robert Cohn, and Geoff

Lowney. 2004. Ispike: a post-link optimizer for the Intel

Itanium architecture. In Proceedings of the International Symposium

on Code Generation and Optimization. IEEE, 15–26.

[22]Nicholas Nethercote and Julian Seward. 2007. Valgrind:

A Framework for Heavyweight Dynamic Binary Instrumentation.

In Proceedings of the 28th ACM SIGPLAN Conference

on Programming Language Design and Implementation.

ACM, 89–100.

[23]Diego Novillo. 2014. SamplePGO: The Power of Profile

Guided Optimizations Without the Usability Burden. In Proceedings

of the 2014 LLVM Compiler Infrastructure in HPC.

IEEE Press, 22–28.

[24]Guilherme Ottoni. 2018. HHVM JIT: A Profile-guided,

Region-based Compiler for PHP and Hack. In Proceedings of

the 39th ACM SIGPLAN Conference on Programming Language

Design and Implementation. ACM, 151–165.

[25]Guilherme Ottoni and Bertrand Maher. 2017. Optimizing

Function Placement for Large-scale Data-center Applications.

In Proceedings of the International Symposium on Code Generation

and Optimization. IEEE, 233–244.

[w(1]会增大codesize