无侵入的代码和产物优化：二进制优化与Profile预测-每日运维

背景信息

编译优化手段及其缺陷

目前广泛使用的优化手段主要发生在：

源代码和中间产物（IR）层面，如编译优化（参考编译过程与编译优化基础概念：以C语言为例）

链接时优化（link time optimisation, LTO）在链接时将项目当作whole-program，允许编译优化组件进一步对IR进行优化。

基于剖析（profiling）的优化，一般需要对程序进行插桩（源代码或二进制）、运行、收集性能数据（如不常访问的函数、分支、cache miss等），然后基于性能数据（profile）对指令进行优化和重排，从而减少cache miss、提高产物性能，这个过程又被称为feedback-guided optimisation （FGO）或profile-guided optimisation（PGO）。

Profile data可以在编译的各个阶段指导优化

上述方式的主要缺点有：

针对源代码和中间产物的编译优化，往往需要获得项目的源代码，并重新进行编译。为了达到最好的编译效果，可能需要重复几次编译过程，同时对于大型项目来说，编译过程较为耗时。

编译优化往往只针对单个源文件及其产生的object，多个object进行链接后的结果没有进一步优化。

对于无法获得源代码的第三方已编译的库，即使我们拥有更好的优化手段，也无法再次进行编译优化。

对于PGO 而言，收集profile的过程非常消耗内存和计算资源，且每次重新编译后都要重新运行收集profile，整个PGO过程较为耗时，而且对profile的收集方法非常敏感。

一些概念

空间局部性（spatial locality）

空间局部性是指需要连续访问的cache或程序指令的空间位置，离得越紧，程序性能越好，因为减少了miss时的重定向的性能损耗。在本文中，我们指的主要是指令的空间局部性。

We call spatial locality a measure of the distance between the virtual memory addresses of two consecutively executed instructions of a program. Instructions that are located at close memory addresses are said to have high spatial locality. If instructions tend to be executed together in time (for instance, if the execution of an instruction succeeds the execution of another), then it is desirable that they have high spatial locality. In this way, they are likely to be fetched in the same cache line, via one single memory access.

常见的提高空间局部性的方法有：

将caller（调用函数的函数），callee（被调函数）按顺序挨个放在一起；

将倾向于一起按顺序执行的bb（basic blocks）放在一起（连续的内存地址）。这一类问题往往出现在分支结构中：我们希望将更大概率被执行的branch（由bb组成）放在前面。这一类问题又被称为basic-block placement problem。举个例子：

(a) 一个以CFG表示的有分支的程序片段（黑框中的文字为branch被选择执行的频率）；(b)和(c)表示了两种不同的placement，cost分别为1+2+98+100=201和1+2+2+100=105。本土取自Vespa的论文

cost的计算方法：如果一个从bb_i到bb_j的概率（顺序执行则为0）

Profiling

在本文中，profiling是指（通常在待优化程序运行时）收集CFG的边和边被选择执行的概率的过程。

profiling分为动态和静态两种方式：

动态（dynamic profiling）：在运行时观测待优化程序并收集信息

instrumentation-based需要插桩、重编译程序

sample-based依赖于硬件支持，通过硬件的performance counter收集指令的执行频率。通常没有instrumentation-based准确，但是不需要插桩和重编译，在没有待优化程序源代码的情况下可以直接对binary进行信息采集。

静态（static profiling）：通过分析程序代码，预估branch概率。无需运行程序。

最早的工作（Smith，1981）基于一个观察：在循环中可以继续循环的语句更倾向于被执行。

逐渐的，人们开始总结代码特征，提出每种特征的代码，哪些branch有更高概率被执行。

机器学习方法最早在1997年（Calder et.al，1997）被使用。

本文调研工作的贡献

针对以上问题，本文主要介绍两种新的、对生产过程无侵入的优化方式：

BOLT：对二进制产物进行优化，优点：无需项目源代码，可在编译优化后的产物上进行再次优化。

Vespa：无需运行程序而是通过预测手段获得profile，基于profile对产物进行优化。

二进制优化 - BOLT

Panchenko, M., Auler, R., Nell, B. and Ottoni, G., 2019, February. Bolt: a practical binary optimizer for data centers and beyond. In 2019 IEEE/ACM International Symposium on Code Generation and Optimization (CGO) (pp. 2-14). IEEE.

Blog post: engineering.fb.com/2018/06/19/…

BOLT全称Binary Optimisation and Layout Tool，顾名思义，BOLT是在二进制产物层面，通过对指令进行重布局，从而提升cache命中率和提高分支预测能力，从而对应用的性能进行优化。

总结

BOLT基于LLVM构建

在大型实际应用上，BOLT可在FDO和LTO的基础上再次提升20.4%的性能。

BOLT依赖于采样的profile data

Motivation

如何收集profile data？SBF

FDO的缺陷：依赖插桩、插桩后的版本消耗太大CPU和内存资源

SBF（Sample-based profiling）的优势：无需插桩（使用现代CPU的硬件profile counter）、硬件profile收集基本没有overhead

优化时机的选取？在binary层优化

一方面，在编译流程中越早使用profile信息，越有利于让后续流程都能受益。

另一方面，在哪个层面收集的profile信息，用于优化哪个层面就会更加准确。

SBF收集的信息很难map回higher-level representation。

动态还是静态优化？静态优化

动态优化需要在运行时收集信息、操作layout，overhead很大

静态更适合这个场景，因为比较简单，没有运行时overhead

设计思路

初版设计

逐步提升binary code覆盖率

从只能优化一小部分函数的layout，到逐步支持更多的复杂函数

在不能很有信心地重构给定函数的CFG时，不触及这个函数

layout优化可能增加指令的数量

重定位模式（relocations mode）

可以重新排列binary中所有函数的位置

修改binary中函数的位置、将函数分割成多个函数来提升code locality

Pipeline重写

BOLT的binary重写pipeline

Function discovery：对于函数名和地址绑定的函数，BOLT提取debug信息和profile data以开始反汇编单个函数

BOLT依赖LLVM框架来处理binary的反汇编和修改：LLVM的模块化架构、支持多种机器架构（ARM版的BOLT的prototype版只用了一个月开发）。

CFG生成依赖LLVM的tablegen-generated反汇编器的MCInst。

C++异常处理和Debug信息

BOLT支持DWARF的debug信息，在重排代码时会相应地更新DWARF和异常处理。

BOLT的优化

BOLT：

使用pass概念，在code transformation和analysis时使用相应的优化pass。部分pass架构无关、部分架构依赖（architecture-dependent）

BOLT使用了一个数据流（Data flow）分析组件，供需要的pass使用

BOLT的Intel x86-64优化组件

BOLT为Intel x86-64架构开发的优化pass（有序）

针对AMD处理器的特殊优化

在Linker的基础上fold更多的函数（以HHVM为例，在linker的基础上多fold了3%的函数）

基于function call frequency，提升indirect call。llvm.org/devmtg/2015…

基于架构的一些简单的优化，如

删除从寄存器push到stack，没有修改又放回寄存器

将a + a优化成左移指令

将a_float * 8换成指数*3

简化load指令

再次2

类似3.www.intel.com/content/www…

基于executed paths的frequency，重排或拆分hot/cold basic blocks

再次4

删除不可达的bb

再次8

基于HFSort（）——重排函数顺序

Optimizing Function Placement for Large-Scale Data-Center Applications.pdf

简化条件语句的tail calls。en.wikipedia.org/wiki/Tail_c…

移除不必要的caller-saved寄存器溢出

将called-saved寄存器溢出移到被调用更近的位置

如何进行profiling

在intel的微处理器中，LBR是一个包含最后32个执行的branches的list。BOLT基于LBR进行profile data采集。

收益

Facebook

加速

细分优化

Clang和GCC

加速

细分优化

Thats' it!

VESPA

Moreira, A.A., Ottoni, G. and Quintão Pereira, F.M., 2021. VESPA: static profiling for binary optimization. Proceedings of the ACM on Programming Languages, 5(OOPSLA), pp.1-28.

Blog post: engineering.fb.com/2022/03/15/…

总结

基于机器学习进行profile预测，因为没有运行时的动态信息采集（dynamic profiler），本方法是一个static profiler

表现比dynamic profiler差很多，但是还是比编译器原生的优化好很多：比clang O3加速6%、减少10%的cache miss

实现上基于BOLT

Vespa的设计

举个例子：

(a)从程序（见总结-一些背景信息-空间局部性）中提取的一个代码片段；(b)特征提取；(c)特征向量；(d)一个简单的预测器；(e)预测的branch概率

在本例中，代码片段特征取自程序的syntax，需要记录的特征取自下表。特征被向量化后用于生成预测。

收益

benchmark选择：clang、GCC、MySQL、PostgreSQL

性能提升（over clang-O3）

L1 instruction cache miss的减少

Cache miss减少与性能提升的相关性

机器学习耗时

插桩：35.21s

profile收集：1036min

特征提取：29.75s

预处理与合并数据：179.84s

编码与训练：45.5min

总计：18h

应用耗时（用于生成binary的时间，以秒计）

That's it!

基于机器学习的PGO

总结

提出了一种新型的统计方法来推测branch概率：

Offline training：从大量有branch概率信息的binary采集数据、训练

编译器使用learned model来预测branch信息、做优化决策

嵌入了LLVM，替换了人工规则集

在应用中，省去了profiling采集的运行时间、对编译耗时几乎没有影响。

Motivation

设计

本方法主要是两步：离线学习和在线推理

离线学习

定义一个phase收集信息（branch、branch possibility），处理信息

编译时预测

特征采集

数据集：llvm-test-suite benchmarks, abseil, bash, box2d, bzip2, diffutils, distorm, fmt, fpm, graphviz, grep, hermes, jsonnlohmann, leveldb, liblinear, libpng, libuv, clang, lua, myhtml, oggvorbis, povray, python, sela, smallpt, sqlite, tscp, xxhash, z3

采集的特征包括：

模型训练

代码生成、概率推理

将训练完的模型转换成一个可以被嵌入编译器的C代码

在编译器运行时，branch信息被用于模型匹配、获得两个branch的概率。

收益

在benchmark中收集到了200MB的信息，训练后的模型大小2MB。生成的1k的预测代码。每秒可以查询预测25万次。

被编译项目的运行加速：

That's it!

无侵入的代码和产物优化：二进制优化与Profile预测

编译优化手段及其缺陷