LLVM优化基础概述

发布时间 2023-05-23 05:18:22作者: 吴建明wujianming
下图是2012年LLVM获得“ACM Software System Award 2012”奖项时的介绍图,这张图简明扼要的展示了LLVM的整体架构。
各种语言经过前端编译后,生成LLVM IR,然后,在link-time执行一些过程间的分析优化,这一块是LLVM很重要的一部分,过程间分析,既要兼顾
多种语言,同时,又要保留高层次的类型信息来执行过程间的优化。从前端编译到后端优化,到链接时以及运行时都有相关优化在里面。
编译优化其实在各个阶段都存在,只是LLVM将其打通了,什么别名分析,数据流分析,公共子表达式消除,循环优化,寄存器分配和链接时的相关
优化,这些景点的后端分析,都可以在其上实现。另外,运行时通过收集profiling信息,对LLVM Code优化,并重新编译成native code,同时,
“Automatic Pool Allocation”这种黑科技竟然都可以实现,基于LLVM IR,还可以实现多种GC算法。
将优化分为5个阶段:编译时优化,链接时优化,装载时优化,运行时优化,以及闲时优化。
编译时优化
包括一些经典的编译优化知识,在特定语言的编译前端,将源码编译成LLVM IR时,可以执行一些相关的优化,这些优化操作可以分为3部分。
1)执行语言相关的优化。例如,“optimizing closures in languages with higher-order function”。
2)将源码翻译成LLVM Code,保留可能多的类型信息,例如,结构体,指针,或者列表等信息。
3)在单个模块内部,可以调用LLVM针对全局不看过,或者工程间的优化。

 编译前端没有不要非得将编译结果构造成SSA形式,LLVM可以进行stack promotion操作,只要局部变量地址没有逃出当前函数作用域,就可以将栈上分配的变量分配在寄存器上,毕竟寄存器是没有显示地址的。

LLVM也可以将结构体对象或者列表映射在寄存器上,用于构造LLVM IR所要求的SSA形式。编译器对structure或者说是memory layout的优化都是很难的一块。
虚函数决议与尾递归优化也可以推迟到LLVM code阶段,有些虚函数调用决议是完全可以在编译器期间解决的,使用一个call(jmp)指令就可以了。尾递归优化比较通用,基本上所有编程语言都有这样的需求,尾递归优化可以减少对栈(即内存)的消耗,也避免了创建stack frame或者销毁stack frame的开销。
链接时的优化
LLVM IR目标文件进行链接时,进行一些过程间或者跨文件的分析优化。link-time是首次能够见到程序全貌的阶段,在这个阶段可以做很多激进的优化,如虚表或者typeinfo是否能够真正的优化删除(如果虚表或者typeinfo没有在程序中实用的话,仅限于完整程序,所以,函数的定义可见)。LLVM的链接时优化如下图所示:

 LLVM在链接时所做的最激进的优化,莫过于DSA和APA。在DSA分析中,借助于LLVM比较充足的type information,在指针分析的基础上,可以构造出整个内存对象的连接关系图。然后对这个图进行分析,得到内存对象的连接模式,将连接比较紧密的结构对象,例如树、链表等结构体分配在自定义的一格连续分配的内存池中。这样可以少维护很多内存块,并且大大提高空间locality,相应的提高cache命中率。

APA(Automatic Pool Allocation)能够将堆上分配的链接形式的结构体,分配在连续的内存池中,这种做法是通过将内存分配函数替换为自定义池
分配函数实现的,示意图如下所示:

 另外一些在链接阶段进行的分析,包括调用图构建,Mod/Ref分析,以及一些过程间的分析,例如函数inline,死全局变量删除(dead global elimination),死实参删除(dead argument),常量传播,列表边界检查消除(array bounds check elimination),简单结构体域重排(structure field reordering),以及Automatic Pool Allocation。

 
参考文献链接