论文精读（五）

Propeller: A Profile Guided, Relinking Optimizer for Warehouse-Scale Applications

• 组会报告的稿子，同样懒得整理了，可结合PPT查看
• 今天我要讲的论文是“Propeller: A Profile Guided, Relinking Optimizer for Warehouse-Scale Applications”，是 Google 今年上半年在 ASPLOS 2023 上的一篇论文。总体上是 follow LLVM-BOLT 的一个工作，也算是少有的链接编译优化这个领域的顶会论文，之前也有同学提过这篇论文，不知道讲哪篇好，想来想去还是讲这篇论文，也可以让大家了解一下二进制编译优化
• 文章的整个逻辑围绕这三个问题，首先我们来看第一个问题。后链接优化器是什么，以及我们为什么需要一个后链接优化器
• PGO 优化很好，但是仍然留下了程序优化的空间
  • PGO 反馈编译优化大家应该不陌生，之前组会 gyh 讲过一个综述，也提到了这篇论文
  • 先建立一点量化的概念：PGO 优化一般能提供 10% 以上的性能提升，但也大致就是这个数量级
  • ThinLTO 是一个 LLVM 里类似链接的优化技术。链接的过程大家应该都大致了解，.c/.cpp文件编译为.o目标文件后，将这些目标文件和一些库合成一个可执行文件就是链接的过程。ThinLTO 是在 .bcLLVM-IR 字节码这个层级做类似“链接”的操作，并且进行优化。它能提供大致 3% 的性能提升。如果有了解过 NVCC 的链接时优化，会发现其实就是这个技术，因为 cicc 是基于 LLVM 的编译器，也很合理
  • PGO 最大的一个问题是 profile 映射回抽象结构时可能不准确，在 code layout 这个问题上也可能导致大致 3% 的性能损失
  • 还有我们通常意义上说的 PGO 也不能进行二进制层级的优化，比如下列几个：
    • 如果代码是对齐的，能更好地利用 DSB(Decoded Stream Buffer)
    • 利用 caller-callee 分析实现过程间寄存器溢出移除
    • 插入预取指令
• 接下来介绍后链接优化器
  • 和常规的 PGO 相比，首先它不用重新编译，可以直接在二进制层面进行编译优化
  • 它的工作流程是：反汇编，优化，再重新写回二进制文件
  • 因为它直接优化二进制文件，有很高的 profile 精度，所以 Layout/Branch 之类特别依赖 PGO 的优化就能有很好的效果
  • 因为直接在二进制上进行，所以一些特别细粒度的优化也可以做
• 第二个问题是，既然二进制优化这么好，目前 SOTA 的方案，其实也就是 BOLT 有什么问题呢？
• 我们来看看真正的软件 build 生产环境的内存限制
  • Google 分布式构建系统对于大多数进程有 12G 的内存限制
  • 谷歌浏览器利用 ThinLTO 构建的时候每个进程有 10G 的内存限制
  • 不知道大家对链接时的内存占用有没有概念，大家应该都源码编译过 LLVM，链接时内存占用一般不小，所以这是一个重要的问题
  • Debug Fission 和 ThinLTO 是优化大规模程序时使用的优化技术
• 但是 BOLT 不能很好地支持大规模的拓展
  • BOLT 是单进程多线程的优化器，随着代码大小增大，不能支持大规模的拓展
  • 因为是单进程，所以也不能很好地利用分布式构建系统
  • 因为没有合适的图，我就把实验部分的图直接放上来了，可以看到 BOLT 的内存占用还是高得离谱的
• BOLT 在反汇编和重写方面也有不少问题
  • 第一个是工程上，没有很好地嵌入进现有的工具链中，更像是一个独立的工具，这也导致了很多重复和兼容性的问题
  • 第二个是，BOLT 不支持 RSEQ，这个我是第一次听说，是 Linux 的一个特性，能够加速同步操作
  • 第三个是，一些密码学的模块有严格的完整性检查，不能被重写
  • 第四个是，BOLT 输入的二进制不能是 stripped，就是说不能没有 Debug 信息
• 总之 BOLT 有各种各样的问题，害得看本文的工作。本文是怎么支持大规模拓展的？
• 这里列了几个本文工作的设计哲学，大体上就是和前面攻击 BOLT 的点反着来
  • 为了减少内存占用，不进行反汇编，因为反汇编这个过程很难并行，并且使用分布式的操作，具体来说就是不进行二进制重写，而是重链接，但第二次编译 IR 时在 LLVM 后端使用后链接优化相关的变换，这些操作对分布式构建系统比较友好，而且第二次编译也将 IR 和目标文件 cache 住
  • 嵌入进现有的工具链中
  • 使用轻量级的程序分析
  • 具体优化目前只做了 code layout，还有其它优化正在做
• 这张图是整个流程，其实过程和 PGO 更像
• 细节上，本文引入了基本块段这个概念，来实现细粒度 code layout 优化。之前的实现大多基于函数调用，本文的粒度是基本块。这是论文举的两个例子，左边三个分别是原始代码布局，基于函数调用的优化，本文基于基本块的优化，可以看到如果粒度是函数，会分裂出新的基本块；右图是一个实现了过程间 layout 优化的例子，线越粗表示分支地越频繁，右边的函数调用跳转局部性更好，因此性能更好
• 接下来看看实验结果
  • 其实和 BOLT 的优化效果差不多，但优势是不会 crash
  • 内存占用这边优势就比较明显了，baseline 是 PGO + ThinLTO
• 最后这页 PPT 不是我写的，是官方演讲的一些想法，一些很细的点，不是论文里的内容，我就不展开来说了，作者认为后链接优化还有很多可做的地方
• 到这论文就分享完了，PPT 的内容大部分来自官方的演讲，所以论文的很多细节都没覆盖到，不过我估计大家可能也不太感兴趣很多链接的实现细节
• 个人观点
  • 我感觉这个工作可能是 Google 自己在 BOLT 落地的过程中遇到了困难，所以参考了 ThinLTO 的 idea 进行了一些尝试，其实最核心的点就是把后链接优化的层级往前移到了链接器这里，所以本文虽然一直在攻击 BOLT，我觉得严格来说本文其实不是后链接优化，更多是 ThinLTO 工作的优化，而且其实非常工程，看了演讲之后，我感觉这种讲故事的能力还是很值得我们学习
  • 其实它的效果主要还是减少运行时的内存占用，性能提升只有很少的数据，只有一张表，和几个段落，连图都没有放，而且其实提升比较低。。。我感觉数据不太好也很容易理解，因为本文 profile 的映射层级实际上还是 IR，肯定还是没有汇编级别准确，不过论文的侧重点也不仅是性能
  • 还有就是里面可能提到了一些别的二进制优化，虽然很多已经被 BOLT 实现地很好了，不知道有没有什么进一步优化的空间