3.6.8 switch 语句

3.6.8 switch 语句

switch（开关）语句可以根据一个整数索引值进行多重分支（multiway branching）。在处理具有多种可能结果的测试时，这种语句特别有用。它们不仅提高了 C 代码的可读性，而且通过使用跳转表（jump table）这种数据结构使得实现更加高效。跳转表是一个数组，表项 i 是一个代码段的地址，这个代码段实现当开关索引值等于 i 时程序应该采取的动作。程序代码用开关索引值来执行一个跳转表内的数组引用，确定跳转指令的目标。和使用一组很长的 if-else 语句相比，使用跳转表的优点是执行开关语句的时间与开关情况的数量无关。GCC 根据开关情况的数量和开关情况值的稀疏程度来翻译开关语句。当开关情况数量比较多（例如 4 个以上），并且值的范围跨度比较小时，就会使用跳转表。

图 3-22a 是一个 C 语言 switch 语句的示例。这个例子有些非常有意思的特征，包括情况标号（case label）跨过一个不连续的区域（对于情况 101 和 105 没有标号），有些情况有多个标号（情况 104 和 106），而有些情况则会落入其他情况之中（情况 102），因为对应该情况的代码段没有以 break 语句结尾。

图 3-23 是编译 switch_eg 时产生的汇编代码。这段代码的行为用 C 语言来描述就是图 3-22b 中的过程 switch_eg_impl。这段代码使用了 GCC 提供的对跳转表的支持，这是对 C 语言的扩展。数组 jt 包含 7 个表项，每个都是一个代码块的地址。这些位置由代码中的标号定义，在 jt 的表项中由代码指针指明，由标号加上“&&”前缀组成。（回想运算符 & 创建一个指向数据值的指针。在做这个扩展时，GCC 的作者们创造了一个新的运算符 &&，这个运算符创建一个指向代码位置的指针。）建议你研究一下 C 语言过程 switch_eg_impl，以及它与汇编代码版本之间的关系。

void switch_eg(long x, long n, long *dest)
{
    long val = x;

    switch (n) {
    case 100:
        val *= 13;
        break;

    case 102:
        val += 10;
        /* Fall through */

    case 103:
        val += 11;
        break;

    case 104:
    case 106:
        val *= val;
        break;

    default:
        val = 0;
    }
    *dest = val;
}

a）switch 语句

1  void switch_eg_impl(long x, long n,
2                      long *dest)
3  {
4      /* Table of code pointers */
5      static void *jt[7] = {
6          &&loc_A, &&loc_def, &&loc_B,
7          &&loc_C, &&loc_D, &&loc_def,
8          &&loc_D
9      };
10     unsigned long index = n - 100;
11     long val;
12
13     if (index > 6)
14         goto loc_def;
15     /* Multiway branch */
16     goto *jt[index];
17
18 loc_A:     /* Case 100 */
19     val = x * 13;
20     goto done;
21 loc_B:     /* Case 102 */
22     x = x + 10;
23     /* Fall through */
24 loc_C:     /* Case 103 */
25     val = x + 11;
26     goto done;
27 loc_D:     /* Cases 104, 106 */
28     val = x * x;
29     goto done;
30 loc_def:   /* Default case */
31     val = 0;
32 done:
33     *dest = val;
34 }

b）翻译到扩展的 C 语言

图 3-22　switch 语句示例以及翻译到扩展的 C 语言。该翻译给出了跳转表 jt 的结构，以及如何访问它。作为对 C 语言的扩展，GCC 支持这样的表

原始的 C 代码有针对值 100、102～104 和 106 的情况，但是开关变量 n 可以是任意整数。编译器首先将 n 减去 100，把取值范围移到 0 和 6 之间，创建一个新的程序变量，在我们的 C 版本中称为 index。补码表示的负数会映射成无符号表示的大正数，利用这一事实，将 index 看作无符号值，从而进一步简化了分支的可能性。因此可以通过测试 index 是否大于 6 来判定 index 是否在 0～6 的范围之外。在 C 和汇编代码中，根据 index 的值，有五个不同的跳转位置：loc_A（在汇编代码中标识为 .L3）、loc_B（.L5）、loc_C（.L6）、loc_D（.L7）和 loc_def（.L8），最后一个是默认的目的地址。每个标号都标识一个实现某个情况分支的代码块。在 C 和汇编代码中，程序都是将 index 和 6 做比较，如果大于 6 就跳转到默认的代码处。

void switch_eg(long x, long n, long *dest)
x in %rdi, n in %rsi, dest in %rdx

1  switch_eg:
2      subq  $100, %rsi             Compute index = n-100
3      cmpq  $6, %rsi               Compare index:6
4      ja    .L8                    If >, goto loc_def
5      jmp   *.L4(,%rsi,8)          Goto *jt[index]
6  .L3:                             loc_A:
7      leaq  (%rdi,%rdi,2), %rax    3*x
8      leaq  (%rdi,%rax,4), %rdi    val = 13*x
9      jmp   .L2                    Goto done
10 .L5:                             loc_B:
11     addq  $10, %rdi              x = x + 10
12 .L6:                             loc_C:
13     addq  $11, %rdi              val = x + 11
14     jmp   .L2                    Goto done
15 .L7:                             loc_D:
16     imulq %rdi, %rdi             val = x * x
17     jmp   .L2                    Goto done
18 .L8:                             loc_def:
19     movl  $0, %edi               val = 0
20 .L2:                             done:
21     movq  %rdi, (%rdx)           *dest = val
22     ret                          Return

图 3-23　图 3-22 中 switch 语句示例的汇编代码

执行 switch 语句的关键步骤是通过跳转表来访问代码位置。在 C 代码中是第 16 行，一条 goto 语句引用了跳转表 jt。GCC 支持计算 goto（computed goto），是对 C 语言的扩展。在我们的汇编代码版本中，类似的操作是在第 5 行，jmp 指令的操作数有前缀“*”，表明这是一个间接跳转，操作数指定一个内存位置，索引由寄存器 %rsi 给出，这个寄存器保存着 index 的值。（我们会在 3.8 节中看到如何将数组引用翻译成机器代码。）

C 代码将跳转表声明为一个有 7 个元素的数组，每个元素都是一个指向代码位置的指针。这些元素跨越 index 的值 0～6，对应于 n 的值 100～106。可以观察到，跳转表对重复情况的处理就是简单地对表项 4 和 6 用同样的代码标号（loc_D），而对于缺失的情况的处理就是对表项 1 和 5 使用默认情况的标号（loc_def）。

在汇编代码中，跳转表用以下声明表示，我们添加了一些注释：

1      .section    .rodata
2      .align 8                Align address to multiple of 8
3  .L4:
4      .quad .L3               Case 100: loc_A
5      .quad .L8               Case 101: loc_def
6      .quad .L5               Case 102: loc_B
7      .quad .L6               Case 103: loc_C
8      .quad .L7               Case 104: loc_D
9      .quad .L8               Case 105: loc_def
10     .quad .L7               Case 106: loc_D

这些声明表明，在叫做“.rodata”（只读数据，Read-Only Data）的目标代码文件的段中，应该有一组 7 个“四”字（8 个字节），每个字的值都是与指定的汇编代码标号（例如 .L3）相关联的指令地址。标号 .L4 标记出这个分配地址的起始。与这个标号相对应的地址会作为间接跳转（第 5 行）的基地址。

不同的代码块（C 标号 loc_A 到 loc_D 和 loc_def）实现了 switch 语句的不同分支。它们中的大多数只是简单地计算了 val 的值，然后跳转到函数的结尾。类似地，汇编代码块计算了寄存器 %rdi 中的值，并且跳转到函数结尾处由标号 .L2 指示的位置。只有情况标号 102 的代码不是这种模式的，正好说明在原始 C 代码中情况 102 会落到情况 103 中。具体处理如下：以标号 .L5 起始的汇编代码块中，在块结尾处没有 jmp 指令，这样代码就会继续执行下一个块。类似地，C 版本 switch_eg_impl 中以标号 loc_B 起始的块的结尾处也没有 goto 语句。

检查所有这些代码需要很仔细的研究，但是关键是领会使用跳转表是一种非常有效的实现多重分支的方法。在我们的例子中，程序可以只用一次跳转表引用就分支到 5 个不同的位置。甚至当 switch 语句有上百种情况的时候，也可以只用一次跳转表访问去处理。

练习题 3.30 下面的 C 函数省略了 switch 语句的主体。在 C 代码中，情况标号是不连续的，而有些情况有多个标号。

void switch2(long x, long *dest) {
    long val = 0;
    switch (x) {
        /* Body of switch statement omitted */
    }
    *dest = val;
}

在编译该函数时，GCC 为程序的初始部分生成了以下汇编代码，变量 x 在寄存器 %rdi 中：

void switch2(long x, long *dest)
x in %rdi

1  switch2:
2      addq $1, %rdi
3      cmpq $8, %rdi
4      ja   .L2
5      jmp  *.L4(,%rdi,8)

为跳转表生成以下代码：

1  .L4:
2      .quad .L9
3      .quad .L5
4      .quad .L6
5      .quad .L7
6      .quad .L2
7      .quad .L7
8      .quad .L8
9      .quad .L2
10     .quad .L5

根据上述信息回答下列问题：

A. switch 语句内情况标号的值分别是多少？

B. C 代码中哪些情况有多个标号？

练习题 3.31 对于一个通用结构的 C 函数 switcher：

void switcher(long a, long b, long c, long *dest)
{
    long val;
    switch(a) {
    case __________:        /* Case A */
        c = __________;
        /* Fall through */
    case __________:        /* Case B */
        val = __________;
        break;
    case __________:        /* Case C */
    case __________:        /* Case D */
        val = __________;
        break;
    case __________:        /* Case E */
        val = __________;
        break;
    default:
        val = __________;
    }
    *dest = val;
}

GCC 产生如图 3-24 所示的汇编代码和跳转表。

void switcher(long a, long b, long c, long *dest)
a in %rdi, b in %rsi, c in %rdx, dest in %rcx

1  switcher:
2      cmpq  $7, %rdi
3      ja    .L2
4      jmp   *.L4(,%rdi,8)
5      .section .rodata
6  .L7:
7      xorq  $15, %rsi
8      movq  %rsi, %rdx
9  .L3:
10     leaq  112(%rdx), %rdi
11     jmp   .L6
12 .L5:
13     leaq  (%rdx,%rsi), %rdi
14     salq  $2, %rdi
15     jmp   .L6
16 .L2:
17     movq  %rsi, %rdi
18 .L6:
19     movq  %rdi, (%rcx)
20     ret

a）代码

1  .L4:
2      .quad .L3
3      .quad .L2
4      .quad .L5
5      .quad .L2
6      .quad .L6
7      .quad .L7
8      .quad .L2
9      .quad .L5

b）跳转表

图 3-24　练习题 3.31 的汇编代码和跳转表

填写 C 代码中缺失的部分。除了情况标号 C 和 D 的顺序之外，将不同情况填入这个模板的方式是唯一的。