编译入门那些事儿(5):Jump Table 优化介绍
发表于 2023/08/22
0
基本概念
Jump Table即跳转表,它可以理解为一个数组,如下图所示,数组的每一项存储一个目标地址,外部代码通过不同的索引从跳转表获取对应表项,得到目标地址,实现一个间接跳转或者间接调用。跳表的应用非常广泛,比如在操作系统中用于存储系统调用和库函数,在一些计算机体系结构中也会采用跳表做中断处理。本文主要介绍跳转表在编译器中的应用。
简单案例
在C语言中,最直观的使用跳转表的例子就是访问函数指针数组并调用对应函数。函数原型如下:
typedef void (*func_ptr) (void);
void func1();
void func2();
void func3();
void func4();
void test(int argv) {
func_ptr jt[4] = {func1, func2, func3, func4};
jt[argv]();
}
采用LLVM编译器指定AArch64架构O2编译以上代码,会生成如下汇编,其中 .L__const.test(int).jt 代表一个跳转表,它包含4个表项,每个表项用于存储目标函数地址。程序通过 ldr 指令访问跳转表,获取目标函数地址,并通过 br 指令实现函数的间接调用。
test(int): // @test(int)
adrp x8, .L__const.test(int).jt
add x8, x8, :lo12:.L__const.test(int).jt
ldr x0, [x8, w0, sxtw #3]
br x0
.L__const.test(int).jt:
.xword _Z5func1v
.xword _Z5func2v
.xword _Z5func3v
.xword _Z5func4v
多路分支优化
1. 优化简介
在LLVM编译器中,存在一种将switch多路分支控制结构转化为跳转表的技术。合适的条件下将多个比较跳转转化为跳转表可以提高运行效率,该优化默认开启。
int func(int a, int b) {
int c;
switch (a) {
case 1:
c = b + 1;
break;
case 2:
c = b - 2;
break;
case 3:
c = b | 3;
break;
case 4:
c = b & 4;
break;
default:
break;
}
return c;
}
以上面的代码为例,这是一个典型的switch多路分支控制结构。如果不启用jump table优化,编译器会将其转化为一系列比较和跳转指令。如果启用jump table优化,编译器会在函数内构造一个跳转表,通过变量a索引到目标机器代码块,其生成的关键汇编如下:
...
// %bb.1: // %entry
adrp x9, .LJTI0_0
add x9, x9, :lo12:.LJTI0_0
ldr x8, [x9, x8, lsl #3]
br x8
.LBB0_2: // %sw.bb
...
.LBB0_3:
...
.LBB0_4: // %sw.bb1
...
.LBB0_5: // %sw.bb2
...
.LBB0_6: // %sw.bb3
...
.LJTI0_0:
.xword .LBB0_2
.xword .LBB0_4
.xword .LBB0_5
.xword .LBB0_6
2. Jump Table识别
(1)Switch群组类型
编译器前端将switch语句转化为LLVM IR SwitchInst,每一个SwitchInst包含比较变量、default BB、case value、Dest BB。如下所示:
switch i32 %6, label %22 [
i32 1, label %7
i32 2, label %10
i32 3, label %13
i32 4, label %16
]
在指令选择阶段构建SelectionDAG时,根据用户选项、case value分布、目标架构特性等因素对每一个SwitchInst做分析,最终将一个switch拆分成多个群组,这里将每一个群组称为一个cluster。cluster分为如下3类:
类型 | 说明 |
---|---|
CC_Range |
单个或多个连续case value对应同一目标BB |
CC_JumpTable |
多个case value对应多个目标BB,且适合做成跳转表 |
CC_BitTests |
多个case value对应多个目标BB,且适合通过比特检测映射到目标BB |
(2)基本条件
多路分支结构转化为跳转表并不一定都会获得良好的效果。主要原因如下:
a. 跳转表将直接跳转转化为间接跳转,可能会导致branch miss率增高。除此之外还会增加访问跳转表的指令。因此在分支较少时,原本仅需要简单的比较指令和少量跳转指令即可到达目标地址,没有必要转化为跳转表。
b. 跳转表需要为case值范围内的所有值创建一个表项,如果case值很稀疏,则表中存放的大部分地址都是defaultBB,会造成CodeSize膨胀。
因此,一个cluster适合转化为CC_JumpTable必须同时满足如下条件:
a. 选项支持:用户没有开启 -fno-jump-tables 选项。
b. 后端架构支持:后端架构支持跳转表相关的SDNode。
c. 排除比特检测场景:如果目标BB数较少,且case value差值在机器位宽之内,则可以根据目标BB数和比较次数评估是否适合转化为比特检测模式。如果可以做成,则优先转化为比特检测类型。
d. clusters个数评估:如果clusters个数较少,则分支数较少,没有必要转化为跳转表,因此必须满足个数>=阈值。
e. case value密度评估:如果case value值密度太低,会导致跳转表中存储的大部分地址为default BB,利用率较低,产生不合理的空间开销。密度评估条件:
其中,CaseRange:case value之间的最大差值。
CaseNumber:case value个数。
MinDensity:密度阈值。Os/Oz优化等级下更关注CodeSize,密度要求更高。
(3) 算法实现
a. 初始化clusters
首先定义一个vector clusters用于存储cluster群组,将每个case当成CC_Range类型存储到clusters中,每一个case value对应一个目标BB,同时记录该case在switch内部的Branch Probability。
将clusters按照case value值升序排序,如果存在连续多个case value映射到同一个目标BB,则将这几个cluster合并成一个CC_Range类的cluster。
b. 剥离Branch Probability最大的case
选取Branch Probability最大的cluster,如果它的占比大于等于阈值,则将该cluster从switch中剥离出去。Branch Probability默认是控制流图静态分析结果,如果有PGO信息,会根据PGO信息计算。该优化有利于性能提升。
说明:Oz场景为了更小的CodeSize,不做该优化。
c. 识别跳转表
如果满足3.2.2中描述的基本条件,则将clusters合并为一个CC_JumpTable类型的cluster,在function内创建一个跳转表,并创建MBB实现对跳转表的访问和间隔跳转。
如果上述条件不满足,在非O0优化等级下,尝试在clusters中寻找能够转化为跳转表的子集,也就是将clusters拆分成多个分区,每个分区包含一个或多个cluster。LLVM参考了《Correction to 'Producing Good Code for the Case Statement'》论文,通过时间复杂度O(N^2)的动态规划算法寻找到最优拆分法。下面简单介绍下该算法。
①数据结构
假设clusters包含N个元素,从N-1开始到0结束依次计算当前元素到最后一个元素之间的最小分区数,由于第i个元素对应的最小分区数依赖于其后面元素的计算结果,因此创建三个数组存储每次的计算结果:
1)MinPartitions[i]:存储Clusters[i..N-1]的最小分区数。
2)LastElement[i]:存储从i开始的分区的最后一个元素。
3)PartitionsScore[i]:存储该拆分法对应的评分。
②评估模型
1)单个cluster:仅需要一个判断语句,开销小,评分最高,设为2;
2)多个cluster:
I. cluster个数较少:仅需要较少的条件判断,评分设为1;
II. cluster个数略大,但是没有达到跳转表的个数阈值:需要较多的条件判断,评分最低,设为0;
III. cluster个数达到跳转表个数阈值:约等于少量条件判断,评分设为1。
③边界状态
1)MinPartitions[N-1] = 1
2)LastElement[N-1] = N - 1
3)PartitionsScore[N-1] = 2
④状态转移方程
假设将cluster[i...j]作为一个分区:
⑤整体流程
N-1的边界状态是一个不变量,因此外层循环将i从N-2遍历到0,每次迭代的目的是为clusters[i...N-1]寻找最小分区数并记录其分数。
最差的情况是将clusters[i]作为独立的分区,先将该分区法对应的结果保存到三个数组中。
内层循环将j从N-1遍历到i+1,每次迭代尝试将clusters[i...j]作为一个分区,评判该分区是否为当前最优拆分法。首先判断该分区是否满足跳转表的密度要求,如果不满足则表示该分区不可能转化为跳转表且无可拓展性,则跳过该拆分法。否则通过状态转移方程计算该拆分法对应的结果,最终得到从i到N-1的最优分区法:
1)如果MinPartitions_tmp > MinPartitions[i],则跳过该拆分法;
2)如果MinPartitions_tmp < MinPartitions[i],则更新结果到三个数组中;
3)如果MinPartitions_tmp == MinPartitions[i],且PartitionsScore_tmp > PartitionsScore[i],则更新结果到三个数组中。
最终,从cluster[0]开始,根据LastElement的结果依次将能够做成跳转表的分区合并成CC_JumpTable类的cluster。
3. 选项介绍
该优化过程中涉及到以下几个选项,用户可以通过调整这些选项,得到理想的性能和CodeSize需求。
选项 | 说明 |
---|---|
-fno-jump-tables |
关闭优化 |
-switch-peel-threshold |
阈值,用于剥离Branch Probability最大case,默认为66 |
-min-jump-table-entries |
clusters个数阈值,默认为4 |
-optsize-jump-table-density |
Os/Oz优化等级下的密度阈值,默认为40 |
-jump-table-density |
其余优化等级下的密度阈值,默认为10 |
跳转表压缩
LLVM编译器针对跳转表定义了6种类型,该类型是指跳转表中每个entry所包含的symbol类型。
类型 | 说明 |
---|---|
EK_BlockAddress |
存储目标的绝对地址,non-pic模式下采用 |
EK_GPRel64BlockAddress |
pic模式,后端架构支持gp relative 64指令 |
EK_GPRel32BlockAddress |
pic模式,后端架构支持gp relative 32指令 |
EK_LabelDifference32 |
pic模式,存储目标BB相对于Jump Table的相对地址 |
EK_Inline |
将Jump Table inline到Block内 |
EK_Custom32 |
存储32bit值,具体实现由后端钩子LowerCustomJumpTableEntry定义。该类型由后端架构定制实现。 |
默认情况,non-pic模式下采用EK_BlockAddress类型。pic模式下如果架构支持gp relative32指令,则选择EK_GPRel32BlockAddress,否则选择EK_LabelDifference32。
后端架构也可以自定义其行为,比如Arm选择EK_Inline类型将跳转表inline到Block内。RISCV64在non-pic模式下small code model时采用EK_Custom32,用于减少CodeSize。
以EK_BlockAddress类型为例,在64架构下,跳转表的每个entry占据8byte。如果entry数量很大,跳转表会占据不小的内存空间,因此AArch64引入了压缩跳转表技术。该优化加在branch relaxation pass之后,尝试将BB绝对地址转化为Block之间的相对地址,在4字节对其模式下,将相对地址进一步压缩,最终可以实现entry大小为4byte/2byte/1byte,最理想情况下可以将跳转表压缩至原来的1/8,从而降低CodeSize,如下图所示。
总结
本文简单介绍了Jump Table的基本概念,以及跳转表在编译器中的常见应用。重点介绍了LLVM中将switch语句转化为跳转表的优化技术,详细描述了该优化的基本条件和算法实现。在此基础上,介绍了编译器提供的一系列选项,用户可以通过调整这些选项得到理想收益。最后,简单介绍了跳转表中存储符号的类型以及LLVM中针对CodeSize优化的跳转表压缩技术。
参考
1. https://github.com/llvm/llvm-project
2. https://courses.cs.washington.edu/courses/cse351/17sp/lectures/CSE351-L10-asm-IV_17sp-ink.pdf
本页内容