switch的编译过程

这篇文章很早之前就想写了。虽然说内容基本上只是来自我为讨论课准备的ppt，但毕竟自己花了一些时间研究的内容，而且在网上也没有搜到相关内容，不留下来总感觉有些可惜。而且在讨论课后老师让我写一篇文档，说不定还能成为折磨下一届的学弟学妹们的题目（

尽管在上上周就考完期末，但之后一直爽打剑星，外加还在整租房子的事，因此是一直拖到了今天，终于是想着不能再拖下去了。

说起来想写的东西还是挺多的，到现在连关于自己都还没有写。果然还是得定一个期限，不然说不定拖着拖着就再也没有更新了，毕竟DDL才是人类第一生产力

使用的编译器的版本为：

gcc：x86-64 gcc 14.2
clang：x86-64 clang 20.1.0
msvc: x64 msvc v19.40 VS17.10

如无特殊说明，默认使用的编译器为gcc，在compiler explorer网站进行编译。

1. 跳转表的基本原理
#

关于跳转表, 其实用一个例子就可以解释清楚：

int main() {
    int i = 0, j = 0;
    switch (i) {
        case 1:
            j += 1;
        case 2:
            j += 2;
            break;
        case 3:
            j += 3;
            break;
        case 4:
            j += 4;
            break;
        case 5:
            j += 5;
            break;
        case 6:
            j += 6;
            break;
        default:
            j += 10;
            break;
    }
    return 0;
}

main:
        pushq   %rbp
        movq    %rsp, %rbp
        movl    $0, -8(%rbp)
        movl    $0, -4(%rbp)
        cmpl    $6, -8(%rbp)
        ja      .L2
        movl    -8(%rbp), %eax
        movq    .L4(,%rax,8), %rax
        jmp     *%rax
.L4:
        .quad   .L2
        .quad   .L9
        .quad   .L8
        .quad   .L7
        .quad   .L6
        .quad   .L5
        .quad   .L3
.L9:
        addl    $1, -4(%rbp)
.L8:
        addl    $2, -4(%rbp)
        jmp     .L10
.L7:
        addl    $3, -4(%rbp)
        jmp     .L10
.L6:
        addl    $4, -4(%rbp)
        jmp     .L10
.L5:
        addl    $5, -4(%rbp)
        jmp     .L10
.L3:
        addl    $6, -4(%rbp)
        jmp     .L10
.L2:
        addl    $10, -4(%rbp)
        nop
.L10:
        movl    $0, %eax
        popq    %rbp
        ret

以上两段代码分别是一个简单的switch示例以及编译后的结果。.L4的内容实际上就是跳转表。本质上跳转表就是一个数组，其索引就是switch中case的范围，而每一项储存了对应代码段的地址。

在 CS:APP 中其实就已经介绍过switch语句会使用跳转表来进行优化（P159），而在书中也提到了switch相对于if-else所拥有的优点：执行分支语句的时间与分支数量无关。相比于逐个检查一长串的if-else语句，使用跳转表直接进行跳转显然是更高效的选择。

更本质的来说，其核心思想仍然是几乎所有算法都会用到的——空间和时间的相互转换，跳转表显然可以理解为一个利用空间换时间的例子。

2. 跳转表生成的条件
#

2.1 分支数量
#

跳转表不是但凡使用switch就会出现，比如只有两个分支的情况，用一个if-else就能解决的问题，再去生成跳转表显然就得不偿失了。

对于不同编译器，其生成跳转表的最小分支数量是不同的，我测试了以下三个编译器创建跳转表的最小数目：

clang：4
gcc：5
msvc：6

2.2 分支范围
#

跳转表的索引是根据case的范围决定的，如果在这个范围内绝大部分的分支都是default，使用跳转表会产生不必要的代价，例如下面的例子：

int main() {
    int i = 0, j = 0;
    switch (i) {
        case 1:
            j += 1;
        case 2:
            j += 2;
            break;
        case 3:
            j += 3;
            break;
        case 4:
            j += 4;
            break;
        case 10:
            j += 5;
            break;
        default:
            j += 10;
            break;
    }
    return 0;
}

其跳转表如下：

.L4:
        .quad   .L2
        .quad   .L8
        .quad   .L7
        .quad   .L6
        .quad   .L5
        .quad   .L2
        .quad   .L2
        .quad   .L2
        .quad   .L2
        .quad   .L2
        .quad   .L3

因为跳转表是作为数组储存case范围里每个值应该跳转的地址，那么对于每个不属于case中的值都需要分配到default分支，即例子中的.quad .L2

如果将case 10改为case 41，其主要汇编代码如下所示：

main:
        pushq   %rbp
        movq    %rsp, %rbp
        movl    $0, -8(%rbp)
        movl    $0, -4(%rbp)
        cmpl    $41, -8(%rbp)
        je      .L2
        cmpl    $41, -8(%rbp)
        jg      .L3
        cmpl    $4, -8(%rbp)
        je      .L4
        cmpl    $4, -8(%rbp)
        jg      .L3
        cmpl    $3, -8(%rbp)
        je      .L5
        cmpl    $3, -8(%rbp)
        jg      .L3
        cmpl    $1, -8(%rbp)
        je      .L6
        cmpl    $2, -8(%rbp)
        je      .L7
        jmp     .L3

当前case的范围是41-1=40，而非default分支的数量仅仅有5个。如果此时仍然使用跳转表，那么将有7/8的跳转表项都是.quad .L2。因此编译器无法承受跳转表的代价，而是使用了if-else的编译方式。

如果再将case 41改为case 40，又会出现跳转表。因此对于gcc，如果使用跳转表，在范围内的非default分支数量的比例要大于1/8。

3. 更多switch编译的优化
#

如标题所写，这篇文章是关于switch的编译，而不仅仅是跳转表。除去跳转表，还有一些很有趣的案例值得了解。

3.1 非线性索引
#

仍然是通过例子就可以理解：

int main() {
    int i = 0, j = 0;
    switch (i) {
        case 1:
            j += 1;
            break;
        case 2:
            j += 2;
            break;
        case 3:
            j += 3;
            break;
        case 4:
            j += 4;
            break;
        case 5:
            j += 5;
            break;
        case 101:
            j += 11;
            break;
        case 102:
            j += 12;
            break;
        case 103:
            j += 13;
            break;
        case 104:
            j += 14;
            break;
        case 105:
            j += 15;
            break;
        default:
            j += 10;
            break;
    }
    return 0;
}

部分汇编代码：

main:
        pushq   %rbp
        movq    %rsp, %rbp
        movl    $0, -4(%rbp)
        movl    $0, -8(%rbp)
        cmpl    $5, -4(%rbp)
        jg      .L2
        cmpl    $0, -4(%rbp)
        jg      .L3
        jmp     .L4
.L17:
        movl    -4(%rbp), %eax
        subl    $101, %eax
        cmpl    $4, %eax
        ja      .L4
        movl    %eax, %eax
        movq    .L6(,%rax,8), %rax
        jmp     *%rax
.L6:
        .quad   .L10
        .quad   .L9
        .quad   .L8
        .quad   .L7
        .quad   .L5
.L3:
        cmpl    $5, -4(%rbp)
        ja      .L4
        movl    -4(%rbp), %eax
        movq    .L12(,%rax,8), %rax
        jmp     *%rax
.L12:
        .quad   .L4
        .quad   .L16
        .quad   .L15
        .quad   .L14
        .quad   .L13
        .quad   .L11
.L2:
        cmpl    $105, -4(%rbp)
        jg      .L4
        cmpl    $101, -4(%rbp)
        jge     .L17
        jmp     .L4

简单来讲，就是编译器会根据case的范围来生成多个跳转表。

3.2 Switch to Lookup
#

在使用-O2优化参数后，编译器会根据case中的代码有一些进一步的优化，例如以下代码：

#include <stdio.h>

int main() {
    int i, j = 0;
    scanf("%d", &i);
    switch (i) {
        case 1:
            j += 1;
            break;
        case 2:
            j += 2;
            break;
        case 3:
            j += 3;
            break;
        case 4:
            j += 4;
            break;
        case 10:
            j += 5;
            break;
        default:
            j += 10;
            break;
    }
    printf("j = %d\n", j);
    return 0;
}

main:
        subq    $24, %rsp
        movl    $.LC0, %edi
        xorl    %eax, %eax
        leaq    12(%rsp), %rsi
        call    __isoc99_scanf
        movl    12(%rsp), %eax
        movl    $10, %esi
        subl    $1, %eax
        cmpl    $9, %eax
        ja      .L2
        movl    CSWTCH.2(,%rax,4), %esi
.L2:
        movl    $.LC1, %edi
        xorl    %eax, %eax
        call    printf
        xorl    %eax, %eax
        addq    $24, %rsp
        ret
CSWTCH.2:
        .long   1
        .long   2
        .long   3
        .long   4
        .long   10
        .long   10
        .long   10
        .long   10
        .long   10
        .long   5

对于每一个case，其代码仅仅对j进行了简单的赋值，那么每个case的区别就仅限于值的不同，而操作都是一致的。因此编译器将原本的跳转表（Jump Table）优化为了查值表（Lookup Table）。

这种优化有两个方面的优点：

从代码体积上来看，跳转表由于仅仅储存的是每个case执行的代码块的地址，因此每个地址还要有具体的操作；而查找表就仅储存了不同的值，而赋值只需要通过统一的指令，也就是movl CSWTCH.2(,%rax,4), %esi完成，减少了代码大小。
而从流水线角度来看，查找表避免了控制流的改变，而仅仅涉及到数据流的改变，因此避免了预测失败的惩罚，对于分支预测有显著的优势。

为什么这里要使用scanf和printf？

因为更激进的编译选项会利用未定义行为尽可能地优化代码。这里也有一些有意思的行为，如果注释掉scanf，汇编代码会变成这个样子：

.LC0:
        .string "j = %d\n"
main:
        subq    $8, %rsp
        movl    $10, %esi
        movl    $.LC0, %edi
        xorl    %eax, %eax
        call    printf
        xorl    %eax, %eax
        addq    $8, %rsp
        ret

使用了未初始化的变量i作为case的条件时，编译器会默认switch的结果一定是default，因此可以看到汇编代码中直接movl $10, %esi作为printf的参数。

而再如果注释掉printf，那么汇编代码会更加简洁：

main:
        xorl    %eax, %eax
        ret

此时在编译器看来，这个函数真正有效的代码仅有一条：return 0。因此编译时仅需要将%eax清零作为返回值即可。

3.3 Bittest
#

以下两种优化是当初我在制作ppt的时候无意中发现的，这个例子是这样的：

#include <stdio.h>

int main() {
    int i, j = 0;
    scanf("%d", &i);
    switch (i) {
        case 3:
            j += 6;
            break;
        case 9:
            j += 6;
            break;
        case 39:
            j += 6;
            break;
        case 233:
            j += 6;
            break;
        case 2333:
            j += 6;
            break;
        case 3939:
            j += 6;
            break;
        case 23333:
            j += 6;
            break;
        default:
            j += 13;
            break;
    }
    printf("j = %d\n", j);
    return 0;
}

而汇编代码看上去则十分不寻常：

main:
        subq    $24, %rsp
        movl    $.LC0, %edi
        xorl    %eax, %eax
        leaq    12(%rsp), %rsi
        call    __isoc99_scanf
        movl    12(%rsp), %eax
        cmpl    $233, %eax
        je      .L8
        jle     .L12
        cmpl    $3939, %eax
        je      .L8
        cmpl    $23333, %eax
        je      .L8
        movl    $13, %esi
        cmpl    $2333, %eax
        je      .L8
.L2:
        movl    $.LC1, %edi
        xorl    %eax, %eax
        call    printf
        xorl    %eax, %eax
        addq    $24, %rsp
        ret
.L12:
        leal    -3(%rax), %edx
        cmpl    $36, %edx
        ja      .L6
        movabsq $549755814408, %rdx
        btq     %rax, %rdx
        jnc     .L6
.L8:
        movl    $6, %esi
        jmp     .L2
.L6:
        movl    $13, %esi
        jmp     .L2

最引人注意的是movabsq $549755814408, %rdx这条指令，它将一个奇怪的立即数存入edx中，通过观察其下一条指令为btq %rax, %rdx，即bit test，这给了我们一些线索。

将这个立即数写成二进制是这样的：1000000000000000000000000000001000001000，如果将最低位看作第零位，那么它值为1的位刚好分别是3，9，39，此时这个数的作用也就一目了然了。

3.4 判定树
#

由于这个例子中，case 3，9，39都使用了位测试，因此判定树优化并不典型，因此采用一个新的例子：

#include <stdio.h>

void handle(int x) {
    switch (x) {
        case 5:   puts("low-5"); break;
        case 103: puts("alpha"); break;
        case 205: puts("beta"); break;
        case 4096: puts("gamma"); break;
        case 7000: puts("delta"); break;
        case 10000: puts("omega"); break;
        default: puts("unknown"); break;
    }
}

handle(int):
        cmpl    $4096, %edi
        je      .L2
        jg      .L3
        cmpl    $103, %edi
        je      .L4
        cmpl    $205, %edi
        je      .L5
        cmpl    $5, %edi
        jne     .L7
        movl    $.LC0, %edi
        jmp     puts
.L3:
        cmpl    $7000, %edi
        je      .L8
        cmpl    $10000, %edi
        jne     .L7
        movl    $.LC5, %edi
        jmp     puts
.L7:
        movl    $.LC6, %edi
        jmp     puts
.L8:
        movl    $.LC4, %edi
        jmp     puts
.L5:
        movl    $.LC2, %edi
        jmp     puts
.L4:
        movl    $.LC1, %edi
        jmp     puts
.L2:
        movl    $.LC3, %edi
        jmp     puts

在这个例子中可以很明显的看出，判断时首先对中点4096进行比较，如果大于4096则跳转到.L3继续比较7000和10000，否则仍然是先比较中点103，再然后是205和5。

事实上，编译器会首先对case中的值进行排序，此时分支判断本质上就相当于有序序列中查找目标元素。因此使用二分查找就是一个非常自然的想法，这便是判定树优化的核心思想。

4. LLVM 源码
#

通过阅读编译器源代码，可以详细的了解编译switch的具体过程。这里使用的是LLVM进行分析，具体代码可以在LLVM或llvm-project中查看。

根据代码中的注释：

// Split Clusters into minimum number of dense partitions. The algorithm uses
// the same idea as Kannan & Proebsting "Correction to 'Producing Good Code
// for the Case Statement'" (1994), but builds the MinPartitions array in
// reverse order to make it easier to reconstruct the partitions in ascending
// order. In the choice between two optimal partitionings, it picks the one
// which yields more jump tables. The algorithm is described in
// https://arxiv.org/pdf/1910.02351v2

可以得知其采用的算法出自Correction to ‘Producing Good Code for the Case Statement’

4.1 最小跳转表划分
#

首先，对于前文提到的分支范围对生成跳转表的影响，我们需要对其中的一些概念重新定义。

我们将所有有效分支(即非default的case)排序, 并将这个有序数组记作 $caseitem$. 显然, $caseitem$ 的长度 $n$ 即为所有case的数量.

随后, 我们引入一个新的概念: 密度(density). 记 $d(i,j)$ 为 $caseitem[i]$ 和 $caseitem[j]$ 之间的有效分支的比例, 其计算方式如下: \[d(i,j)=\frac{j-i+1}{caseitem[j]-caseitem[i]+1}\]

我们的目标是将 $caseitem$ 建立一个划分, 其中每个分区将作为子跳转表, 我们将其称作 $cluster$. 例如在前文中提到的例子: $caseitem=[1,2,3,4,5,101,102,103,104,105]$ 就应该被划分为两个 $cluster$, 即 $1-5$ 和 $101-105$.

对于 $caseitem$ 中的每一项 $i$, 我们记 $minClusters[i]$ 为从 $1$ 到 $i$ 中最少需要的 $cluster$ 数量, 其中对于每一个 $cluster$ 其密度均需要大于一个规定的阈值 $\theta$. 并且规定 $minClusters[0]=0$.

此时问题转化为求 $minClusters[n]$, 这个问题可以通过一个十分简单的动态规划完成：\[minClusters[i]=\min\limits_{\substack{0 \leq k < i\ d(k+1,i) \geq \theta}} minClusters[k]+1\]

其思路也不难理解：假设当前遍历到第 $i$ 项，那么只要某一项 $k$ 满足 $d(k+1,i) \geq \theta$, 我们就可以将 $(k+1,…,i)$建立为一个新的 $cluster$, 那么此时通过 $minClusters[k]+1$ 维护最小值即可.

下面给出了其伪代码，通过两层循环容易看出其时间复杂度为 $O(n^2)$

为什么论文的题目为"Correction to ‘Producing Good Code for the Case Statement’"？
最初这个问题在"Producing Good Code for the Case Statement"中被认为是一个NP完全问题，而这篇论文仅用了一页纸就更正了这个问题————直接给出了一个 $O(n^2)$ 的算法

4.2 进一步优化
#

在实际实现中，LLVM代码还参考了Clustering case statements for indirect branch predictors，这篇论文使用了逆序的方法来遍历 $minClusters$, 此时对于每一项 $i$ , 在其最小值发生更新时我们可以记录 $lastElement[i]=j$, 即代表以 $i$ 起始的 $cluster$ 最远可以到达 $j$, 这样在循环结束后仅需通过以下步骤：

i = 0;
do {
    j = lastElement[i];
    partitions.push(i, j); // closed range [i, j]
    i = j + 1;
} while (i < N - 1)

即可获取具体的划分。关于其详细算法可以参看原论文。

这篇论文虽然是说将原本 $O(n^2)$ 的算法优化到了 $O(nlogn)$ , 但其使用的方法仅仅是新加入了一个限制：跳转表的最大数目为一个常数 $L$ , 此时在计算时的复杂度就变为了 $O(LN)$ , 而总的复杂度则为排序时的 $O(nlogn)$ 。我个人认为这是一个比较取巧的优化，并没有什么实际意义。LLVM同样也仅仅借鉴了其逆序计算的部分。

4.3 findJumpTables
#

在了解原理后，便可以阅读源代码了。其核心函数原型如下：

void SwitchCG::SwitchLowering::findJumpTables(CaseClusterVector &Clusters,
                                              const SwitchInst *SI,
                                              std::optional<SDLoc> SL,
                                              MachineBasicBlock *DefaultMBB,
                                              ProfileSummaryInfo *PSI,
                                              BlockFrequencyInfo *BFI);

其架构与第二篇论文的算法基本一致，改动一是删去了最大数目的限制，二是加入了PartitionsScore用来处理多个划分的情况。

if (TLI->isSuitableForJumpTable(SI, NumCases, Range, PSI, BFI)) {
    CaseCluster JTCluster;
    if (buildJumpTable(Clusters, 0, N - 1, SI, SL, DefaultMBB, JTCluster)) {
        Clusters[0] = JTCluster;
        Clusters.resize(1);
        return;
    }
}

首先在具体计算前先对边界情况进行处理，即整个范围都符合构建跳转表的条件，此时直接返回即可。

SmallVector<unsigned, 8> MinPartitions(N);
SmallVector<unsigned, 8> LastElement(N);
SmallVector<unsigned, 8> PartitionsScore(N);

enum PartitionScores : unsigned { NoTable = 0, Table = 1, FewCases = 1, SingleCase = 2 };

MinPartitions[N - 1] = 1;
LastElement[N - 1] = N - 1;
PartitionsScore[N - 1] = PartitionScores::SingleCase;

随后对计算所使用的变量进行初始化，MinPartitions和LastElement与第二篇论文中所使用的一致，即分别代表 $Clusters[i…N-1]$ 的最小划分数和从 $i$ 开始的划分的最后一个元素，而PartitionsScore则是LLVM用到的新优化，其具体用途会在之后解释。

for (int64_t i = N - 2; i >= 0; i--) {
    MinPartitions[i] = MinPartitions[i + 1] + 1;
    LastElement[i] = i;
    PartitionsScore[i] = PartitionsScore[i + 1] + PartitionScores::SingleCase;

    for (int64_t j = N - 1; j > i; j--) {
        Range = getJumpTableRange(Clusters, i, j);
        NumCases = getJumpTableNumCases(TotalCases, i, j);

        if (TLI->isSuitableForJumpTable(SI, NumCases, Range, PSI, BFI)) {
            unsigned NumPartitions = 1 + (j == N - 1 ? 0 : MinPartitions[j + 1]);
            unsigned Score = j == N - 1 ? 0 : PartitionsScore[j + 1];

            int64_t NumEntries = j - i + 1;
            if (NumEntries == 1)
                Score += PartitionScores::SingleCase;
            else if (NumEntries <= SmallNumberOfEntries)
                Score += PartitionScores::FewCases;
            else if (NumEntries >= MinJumpTableEntries)
                Score += PartitionScores::Table;

            if (NumPartitions < MinPartitions[i] || (NumPartitions == MinPartitions[i] && Score > PartitionsScore[i])) {
                MinPartitions[i] = NumPartitions;
                LastElement[i] = j;
                PartitionsScore[i] = Score;
            }
        }
    }
}

这里在第一层循环内，我们首先需要在遍历前将变量赋初值，此时将第 $i$ 项视作单独划分为一个cluster，因此MinPartitions[i]即为上一项加一，LastElement[i]则等于自身，这部分仍然与论文相同。而对于PartitionsScore[i]，由于是单独划分，所以是上一项加上SingleCase。

在第二层循环内，首先计算区间 $[i,j]$ 的Range范围和NumCase有效分支数，然后传入isSuitableForJumpTable判断是否符合生成跳转表的要求。当符合跳转表的要求时，就可以利用第 $j$ 项加一计算NumPartitions，以此来维护MinPartitions[i]的最小。

此时我们可以看出PartitionsScore[i]的用途，是在待更新的值等于当前最小值时（此时意味着第 $i$ 项可以被划分到多个cluster中）根据Score判断是否进行更新。Score的计算并不仅仅是第 $j$ 项加一，而是根据NumEntries即分支数量，加上不同的值。这些值的权重则由PartitionScores这个枚举决定，其中SingleCase的权重最大，因为单个Case并不需要进行判断，所以是最好的情况；而Table跳转表则被认为和FewCases是相同的权重；最差的情况则是NumEntries既不够多到MinJumpTableEntries生成跳转表，也不够少到小于SmallNumberOfEntries。

最后如果当前划分数小于MinPartitions[i]，或者虽然相等但是当前Score更大，则进行更新。

unsigned DstIndex = 0;
for (unsigned First = 0, Last; First < N; First = Last + 1) {
    Last = LastElement[First];
    unsigned NumClusters = Last - First + 1;

    CaseCluster JTCluster;
    if (NumClusters >= MinJumpTableEntries && buildJumpTable(Clusters, First, Last, SI, SL, DefaultMBB, JTCluster)) {
        Clusters[DstIndex++] = JTCluster;
    } else {
        for (unsigned I = First; I <= Last; ++I)
            std::memmove(&Clusters[DstIndex++], &Clusters[I], sizeof(Clusters[I]));
    }
}
Clusters.resize(DstIndex);

在计算完成后，依据LastElement，为符合条件（即分支数大于跳转表的最小数目）的区间建立跳转表。

4.4 跳转表生成条件
#

在前文中，我们通过样例测试了不同编译器生成跳转表的条件。而具体实现则正是findJumpTables函数中用到的isSuitableForJumpTable函数，其原型定义在LLVM和llvm-project中。

有关各个函数的详细信息，可以在TargetLoweringBase Class Reference中查看

bool TargetLoweringBase::isSuitableForJumpTable(const SwitchInst *SI,
                                                uint64_t NumCases,
                                                uint64_t Range,
                                                ProfileSummaryInfo *PSI,
                                                BlockFrequencyInfo *BFI) const {
  const bool OptForSize = llvm::shouldOptimizeForSize(SI->getParent(), PSI, BFI);
  const unsigned MinDensity = getMinimumJumpTableDensity(OptForSize);
  const unsigned MaxJumpTableSize = getMaximumJumpTableSize();

  return (OptForSize || Range <= MaxJumpTableSize) &&
         (NumCases * 100 >= Range * MinDensity);
}

在这个函数中检测了两个条件：分支数量小于最大值，且密度大于最小值。而分支数量的最小值则是在findJumpTables中检测的：NumClusters >= MinJumpTableEntries。在FIXME中也提到了这一点，并认为是一个不好的做法：

// FIXME: This option is only to test if the strict fp operation processed
// correctly by preventing mutating strict fp operation to normal fp operation
// during development. When the backend supports strict float operation, this
// option will be meaningless.

这些具体的阈值仍然是在TargetLoweringBase.cpp中定义的：

static cl::opt<bool> JumpIsExpensiveOverride(
    "jump-is-expensive", cl::init(false),
    cl::desc("Do not create extra branches to split comparison logic."),
    cl::Hidden);

static cl::opt<unsigned> MinimumJumpTableEntries
  ("min-jump-table-entries", cl::init(4), cl::Hidden,
   cl::desc("Set minimum number of entries to use a jump table."));

static cl::opt<unsigned> MaximumJumpTableSize
  ("max-jump-table-size", cl::init(UINT_MAX), cl::Hidden,
   cl::desc("Set maximum size of jump tables."));

/// Minimum jump table density for normal functions.
static cl::opt<unsigned>
    JumpTableDensity("jump-table-density", cl::init(10), cl::Hidden,
                     cl::desc("Minimum density for building a jump table in "
                              "a normal function"));

/// Minimum jump table density for -Os or -Oz functions.
static cl::opt<unsigned> OptsizeJumpTableDensity(
    "optsize-jump-table-density", cl::init(40), cl::Hidden,
    cl::desc("Minimum density for building a jump table in "
             "an optsize function"));

可以看到，min-jump-table-entries的默认值正好就是4，因此我们从源码的角度验证了测试的结论。而最大值默认达到了UINT_MAX，所以一般不会出现因为分支数量大于最大值而不生成跳转表，这也说明了第二篇论文的 $O(nlogn)$ 的复杂度并不实用。

至于密度则有两个不同的阈值，对于普通的函数，在密度，即有效分支数量的比例大于10%时即可生成，但如果启用了-Os或-Oz，即代码大小的优化，则密度要达到40%才可以生成。

5. 参考资料与延伸阅读
#

~~又拖了一周多，写的我相似~~

作者

TsukasaYatoki

仍然向往着那片青空

1. 跳转表的基本原理 #

2. 跳转表生成的条件 #

2.1 分支数量 #

2.2 分支范围 #

3. 更多switch编译的优化 #

3.1 非线性索引 #

3.2 Switch to Lookup #

3.3 Bittest #

3.4 判定树 #

4. LLVM 源码 #

4.1 最小跳转表划分 #

4.2 进一步优化 #

4.3 findJumpTables #

4.4 跳转表生成条件 #

5. 参考资料与延伸阅读 #