--- title: 编译入门那些事儿（5）：Jump Table 优化介绍-官方技术文章-鲲鹏社区 description: 本文主要介绍了Jump Table的基本概念以及跳转表在编译器中的常见应用。 keywords: Jump,编译入门那些,事儿,Table,优化介绍,官方技术文章,鲲鹏社区,基本概念 url: https://www.hikunpeng.com/developer/techArticles/20230830-2?envFlag=1 section: (其他) --- # 编译入门那些事儿（5）：Jump Table 优化介绍-官方技术文章-鲲鹏社区 URL: https://www.hikunpeng.com/developer/techArticles/20230830-2?envFlag=1 描述: 本文主要介绍了Jump Table的基本概念以及跳转表在编译器中的常见应用。 关键词: Jump,编译入门那些,事儿,Table,优化介绍,官方技术文章,鲲鹏社区,基本概念 官方技术文章 [了解详情](https://www.hikunpeng.com/zh/developer/techArticles) 编译入门那些事儿（5）：Jump Table 优化介绍 编译入门那些事儿（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 [了解详情](https://github.com/llvm/llvm-project) 2.https://courses.cs.washington.edu/courses/cse351/17sp/lectures/CSE351-L10-asm-IV_17sp-ink.pdf [了解详情](https://courses.cs.washington.edu/courses/cse351/17sp/lectures/CSE351-L10-asm-IV_17sp-ink.pdf) 3.http://syrcose.ispras.ru/2007/files/2007_02_talk.pdf [了解详情](http://syrcose.ispras.ru/2007/files/2007_02_talk.pdf) 4.https://reviews.llvm.org/D32564 [了解详情](https://reviews.llvm.org/D32564) 本页内容