编译入门那些事儿（5）：Jump Table 优化介绍

1. 基本概念

Jump Table即跳转表，它可以理解为一个数组，如下图所示，数组的每一项存储一个目标地址，外部代码通过不同的索引从跳转表获取对应表项，得到目标地址，实现一个间接跳转或者间接调用。跳表的应用非常广泛，比如在操作系统中用于存储系统调用和库函数，在一些计算机体系结构中也会采用跳表做中断处理。本文主要介绍跳转表在编译器中的应用。

2. 简单案例

在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  

3. 多路分支优化

3.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

3.2 Jump Table识别

3.2.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类：

3.2.2 基本条件

多路分支结构转化为跳转表并不一定都会获得良好的效果。主要原因如下：

• 跳转表将直接跳转转化为间接跳转，可能会导致branch miss率增高。除此之外还会增加访问跳转表的指令。因此在分支较少时，原本仅需要简单的比较指令和少量跳转指令即可到达目标地址，没有必要转化为跳转表。
• 跳转表需要为case值范围内的所有值创建一个表项，如果case值很稀疏，则表中存放的大部分地址都是defaultBB，会造成CodeSize膨胀。

因此，一个cluster适合转化为CC_JumpTable必须同时满足如下条件：

• 选项支持：用户没有开启 -fno-jump-tables 选项。
• 后端架构支持：后端架构支持跳转表相关的SDNode。
• 排除比特检测场景：如果目标BB数较少，且case value差值在机器位宽之内，则可以根据目标BB数和比较次数评估是否适合转化为比特检测模式。如果可以做成，则优先转化为比特检测类型。
• clusters个数评估：如果clusters个数较少，则分支数较少，没有必要转化为跳转表，因此必须满足个数>=阈值。
• case value密度评估：如果case value值密度太低，会导致跳转表中存储的大部分地址为default BB，利用率较低，产生不合理的空间开销。密度评估条件：

其中，CaseRange：case value之间的最大差值。

CaseNumber：case value个数。

MinDensity：密度阈值。Os/Oz优化等级下更关注CodeSize，密度要求更高。

3.2.3  算法实现

1、初始化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。

2、剥离Branch Probability最大的case

选取Branch Probability最大的cluster，如果它的占比大于等于阈值，则将该cluster从switch中剥离出去。Branch Probability默认是控制流图静态分析结果，如果有PGO信息，会根据PGO信息计算。该优化有利于性能提升。

说明：Oz场景为了更小的CodeSize，不做该优化。

3、识别跳转表

如果满足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)的动态规划算法寻找到最优拆分法。下面简单介绍下该算法。

（1）数据结构

假设clusters包含N个元素，从N-1开始到0结束依次计算当前元素到最后一个元素之间的最小分区数，由于第i个元素对应的最小分区数依赖于其后面元素的计算结果，因此创建三个数组存储每次的计算结果：

• MinPartitions[i]：存储Clusters[i..N-1]的最小分区数。
• LastElement[i]：存储从i开始的分区的最后一个元素。
• PartitionsScore[i]：存储该拆分法对应的评分。

（2）评估模型

• 单个cluster：仅需要一个判断语句，开销小，评分最高，设为2；
• 多个cluster:
• cluster个数较少：仅需要较少的条件判断，评分设为1；
• cluster个数略大，但是没有达到跳转表的个数阈值：需要较多的条件判断，评分最低，设为0；
• cluster个数达到跳转表个数阈值：约等于少量条件判断，评分设为1。

（3）边界状态

• MinPartitions[N-1] = 1
• LastElement[N-1] = N - 1
• PartitionsScore[N-1] = 2

（4）状态转移方程

假设将cluster[i...j]作为一个分区：

（5）整体流程

N-1的边界状态是一个不变量，因此外层循环将i从N-2遍历到0，每次迭代的目的是为clusters[i...N-1]寻找最小分区数并记录其分数。

最差的情况是将clusters[i]作为独立的分区，先将该分区法对应的结果保存到三个数组中。

内层循环将j从N-1遍历到i+1，每次迭代尝试将clusters[i...j]作为一个分区，评判该分区是否为当前最优拆分法。首先判断该分区是否满足跳转表的密度要求，如果不满足则表示该分区不可能转化为跳转表且无可拓展性，则跳过该拆分法。否则通过状态转移方程计算该拆分法对应的结果，最终得到从i到N-1的最优分区法：

• 如果MinPartitions_tmp > MinPartitions[i]，则跳过该拆分法；
• 如果MinPartitions_tmp < MinPartitions[i]，则更新结果到三个数组中；
• 如果MinPartitions_tmp == MinPartitions[i]，且PartitionsScore_tmp > PartitionsScore[i]，则更新结果到三个数组中。

最终，从cluster[0]开始，根据LastElement的结果依次将能够做成跳转表的分区合并成CC_JumpTable类的cluster。

3.3 选项介绍

该优化过程中涉及到以下几个选项，用户可以通过调整这些选项，得到理想的性能和CodeSize需求。

4. 跳转表压缩

LLVM编译器针对跳转表定义了6种类型，该类型是指跳转表中每个entry所包含的symbol类型。

默认情况，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，如下图所示。

5. 总结

本文简单介绍了Jump Table的基本概念，以及跳转表在编译器中的常见应用。重点介绍了LLVM中将switch语句转化为跳转表的优化技术，详细描述了该优化的基本条件和算法实现。在此基础上，介绍了编译器提供的一系列选项，用户可以通过调整这些选项得到理想收益。最后，简单介绍了跳转表中存储符号的类型以及LLVM中针对CodeSize优化的跳转表压缩技术。

6. 参考

1. https://github.com/llvm/llvm-project
2. 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
4. https://reviews.llvm.org/D32564

作者：朱春燕
文章来源：毕昇编译

推荐阅读

• 南开提出 Range-View | 激光雷达技术新进展在自动驾驶等多任务中的应用
• IEEE 754 Floating NaN在深度学习计算中的行为
• ​手机端智能体Mobile-Agent开源，人人都可以拥有手机端超级助理
• 编译入门那些事儿（4）：MLIR概述

更多嵌入式AI干货请关注嵌入式AI专栏。欢迎添加极术小姐姐微信（id:aijishu20)加入技术交流群，请备注研究方向。