A-A+

Helping compiler help you : Ispike, BOLT

2022年03月12日 编程 评论 1 条 阅读 805 次

《BOLT: A Practical Binary Optimizer for Data Centers and Beyond》 CGO 2019

《Ispike: A Post-link Optimizer for the IntelR ItaniumR Architectur》 CGO 2004

 

Helping compiler help you

现在数据中心跑的程序二进制文件普遍都比较大而且代码逻辑比较复杂,因此编译过程的优化在很多情况下能够显著提升性能。编译优化是一种 helping compiler help you的方式。

编译优化常见的几种优化技术,如LTO (Link Time Optimization), FDO (Feedback-Driven Optimizations)。LTO是指在link阶段可以获得之前的编译阶段看不到的全局信息,有机会进行一些inline、死代码删除等等优化。FDO (Feedback-Driven Optimizations),也叫 PGO (Profile-Guarded Optimizations) 是指将获取二进制运行时的profile信息并作为反馈对编译过程进行优化。

本文介绍两个具体的案例,Ispike和BOLT。

 

Ispike

《Ispike: a post-link optimizer for the Intel Itanium archi-tecture》 CGO 2004

Profile数据获取有两种方式:一种是通过插装(instrumentation)的方式,这种方式会对运行性能有比较大的影响,而且消耗比较多的内存;另一种方式是基于采样,利用CPU内置的performance counter等信息。

例如Ispike就是一种基于采样的FDO优化工具。

Ispike针对Intel Itanium架构的CPU (IPF, Itanium Processor Family)。IPF支持workload characterization profiling和instruction-level profiling,前者包括多达100个event及其cycle信息,后者包括分支预测、i/d cache/TLB mis等信息。

Ispike的主要目标是优化内存延迟,包括指令和数据两方面的内存延迟,主要优化手段是加强局部化和prefetch。

 

第一个优化手段:Code Layout优化:通过提高局部性、提升cache line利用率、消除cache冲突来提高I-Cache性能;降低控制流变化;减少活跃代码页帧数量以提交iTLB命中率。几种优化算法如图示。

第二个优化手段:Instruction Prefetching:软件可控的指令预取包括两种方式streaming prefetching 和 hint prefetching。前者指通过IPF的br many 指令预取连续若干cache line,后者是通过brp.few target_add或者brp.many获取一个或两个cache line。

第三个优化手段:Data Layout:普通data很难重新排布,这里仅针对statically allocated数据(例如全局变量、常量、switch语句target addr、函数地址等)进行重排布。根据数据访问频率或者访问相关性进行排布。

第四个优化手段:Data Prefetching:采用stride-based prefetching。基于IPF的Data Event Address Register (D-EAR) 采样miss处信息,例如<pc, daddr, lat> 即PC指针值、数据地址、延迟。为了降低采样开销,这里采用两阶段方式,skipping阶段每隔100miss进行一次采样,inspection阶段每1miss进行一次采样。两阶段的效果控制了采样频率。然后分析一组daddr的间隔,取最小公约数作为stride大小。之后再对load指令进行 d*stride adead的地址预取。

其他优化:包括inline、死代码删除、branch forwarding、load/store forward、GTO-acess优化。其中GOT-access优化是指:访问全局变量时需要先访问Global Offset Table和保留寄存器gp然后拿到全局变量地址才能访问,优化为gp+常量方式,前提是GOT的入口不变。

 

 

BOLT

《BOLT: A Practical Binary Optimizer for Data Centers and Beyond》 CGO 2019

如前文所述,FDO是将运行时的profile信息对进行编译优化。

一般而言,对于编译过程链来讲,越早使用profile信息,优化收益越大,因为更多的编译阶段可以依据该信息进行优化。也正因此,Post-link阶段优化关注的人较少。但实际上越早用profile虽然更多阶段可以使用,但越晚用对代码排布的优化越精确。

BOLT是一个直接修改二进制文件来优化的解决方案,采用的也是基于采样的方式。

BOLT的几个技术要点

A. 工具渐进式开发

一开始只支持少量类型的函数优化,也只支持x86-64 Linux ELF,然后慢慢扩展优化范围。

B. 重新定位模式

BOLT希望最终能够重排所有函数。一种支持重排所有函数的方法是借助relocation records信息(很多链接器可以通过选项支持),但像PIC (position independent code)、有单个文件内部课件的局部函数等等还不行。所以还是需要反汇编。

C. Rewriting Pipeline

BOLT通过符号表和ABI function frame information来识别函数入口和范围,然后读取debug info 反汇编代码,继而构建每个函数的CFG (control flow graph) 表示(LLVM MCInst对象可以支持生成CFG),借助profile信息进行优化,最后生成新的二进制文件。

D. C++ Exceptions and Debug Information

BOLT能够读取DWARF信息。

BOLT优化

BOLT的优化包含很多轮,有些优化手段可以再次应用,如图。

Pass 1 指移除NOP、repz retq的repz。

Pass 2/6 指相同代码折叠,如果有两处代码完全一样,则只需要一份代码即可。

Pass 3 指针对类似C++虚函数调用的类似场景,优化为比较指令+条件分支+最热分支的直接调用和inline。

Pass 4/9 指针对小范围局部代码进行优化,包括删除冗余load/store、常量折叠、强度削弱(如*2换成左移)、优化为特殊指令等等。

Pass 5 simplify-ro-loads是指读取RO section的变量时,可以把load指令优化为立即数load指令。但这样虽然可以提高d-cache效率但可能会影响i-cache,具体是否执行该优化还要看指令是否变大了。

Pass 7 移除PLT(Procedure Link Table)间接调用。

Pass 8 指按照代码热度,调整代码排布,达到热路径执行完全fall-through的效果。

Pass 10 删除不可达代码(死代码)。

Pass 11 修复基本快结束指令,主要是适配CFG和代码重排。

Pass 12 函数位置重排优化 (HFSort技术),有助于提升i-tlb的效率。

Pass 13 条件尾调用优化。

Pass 14/15 优化寄存器溢出。

其他

LBR很重要。

测试结果的一个直观例子,从图中可以直观看到代码调整的效果。

 

 

 

1 条留言  访客:0 条  博主:0 条   引用: 1 条

来自外部的引用: 1 条

  • 浅谈性能分析 LoopJump's Blog

给我留言