switch case

1/7

GCC中对switch-case语句的处理方法

GCC中对switch-case语句的处理主要是在stmt.c中的expand_case(treeexp)函

数中进行的。参数为一个tree变量，其tree_code为SWITCH_EXPR.

用到的主要数据结构为：

structcase_node

{

structcase_node*left;/*Leftsoninbinarytree*/

structcase_node*right;/*Rightsoninbinarytree;alsonodechain*/

structcase_node*parent;/*Parentofnodeinbinarytree*/

treelow;/*Lowestindexvalueforthislabel*/

treehigh;/*Highestindexvalueforthislabel*/

treecode_label;/*Labeltojumptowhennodematches*/

};

每一个case_node结构体表示一个switch分支，每一个分支有可能对应着多个

case，low和high表示的是这些case中的最小值和最大值，如果只有一个case，

则二者相同；code_label是该分支对应的标号，以便跳转时使用；left,right和parent

存贮的是前后分支的信息。

在switch-case语句中，是用一个包含多个case_node的向量来储存所有的分

支信息的，default分支在最后一个，前面的按顺序排列，每一个node的right成

员表示下一个分支。

Switch-case语句的输出格式有三种：

a.以位测试和分支的形式输出，这种形式很少见；

b.以比较和跳转的形式输出；

c.先产生一个包含分支标号列表的标号，再以该标号+偏移的方式跳转，这

种形式与b相比代码量会少一些；

expand_case(treeexp)函数通过一个“range”变量来控制语句用以上哪

2/7

种方式进行输出，range表示的是所有分支的所有case中，最大值和最小值

的范围，也就是差值。另外还有两个变量count和uniq与range一起配合

控制输出。函数expand_case(treeexp)可以分为两大部分，第一大部分是计

算得到count、uniq以及range的值；第二大部分是根据这几个值来绝对用

a,b,c哪种方式来输出以及具体的处理方法。

首先，我们来看一下函数的第一大部分，count、uniq以及range的值

是如何得到的。expand_case会读取exp中的分支信息，通过宏

SWITCH_LABELS(exp)可以获得该switch-case语句中所有的分支信息，返

回的结果为一个向量，令

vec=SWITCH_LABELS(exp);

vec为一个CASE_LABEL_EXPR的向量树，每一个向量成员都表示一个

分支，通过TREE_VEC_LENGTH(vec)可以获得分支的个数，

TREE_VEC_ELT(vec,i)可以访问每一个分支，CASE_LOW和CASE_HIGH

可以分别得到每一个分支的最小和最大的case值。首先逐个读取vec，通过

add_case_node()函数将所有分支以链表的形式储存在一个case_node*

case_list的向量链表中,前一个分支的right成员指向后一个分支；接下来通

过一个for循环读取case_list中所有分支，为了计算range，用两个变量

minval和maxval来记录所有case中的最大值和最小值，通过相减得到

range，并且在该过程中也得到count和uniq的值：

在这个for循环中，首先将第一个分支的最小值和最大值分别赋给minval

和maxval，然后对于每一个分支，都将minval和其最小值比较，如果其最

小值比minval还要小，就将改值赋给minval；同样也对maxval进行这样的

处理，这样到最后minval和maxval的值就是所有case中的最小值和最大值，

通过maxval-minval得到range值；uniq的值较为简单，表示的就是独立分

支的个数，而与case的数目无关；count的值计算稍微复杂些，如果每个分

支都有一个case，则count相应的加1，而如果分支对应着有两个及两个以

上的case，则count就要加2，可以理解为，count表示是否存在多个case

对应着一个标号的情况，如果count>uniq，则说明该情况存在。

3/7

………

case1:case1:case1:

a=b+c;case2:case2:

break;a=b+c;case3:

…break;a=b+c;

…break;

eg1.1eg1.2eg1.3

eg1.1中只有一个case，所以count只加1，而eg1.2和eg1.3中，都对

应着多个case，最大值和最小值不同，所以count都要加2。

这样通过这个for循环，minval,maxval,range,count和uniq都得到了。

一般情况下，range>0,count>=uniq。

接下来是函数的第二大部分，通过以上这几个值的比较来确定最终使用

哪种形式来进行输出：

一、如果分支比较少，一般不超过3个，并且每个分支都有两个以

上的case，也就是uniq<=3,count>=2*uniq,这种情况下就会

采取a方案进行输出，通过位测试和跳转来完成，通过左移以

及和特定的值进行按位与操作，再根据结果来进行跳转，这种

方案的代码量最少；

二、如果range的范围比较大，超过了10*count的范围，则会采取

b方案进行输出，这种方案将swicth的值与所有的case都进行

比较，如果相同则会跳转到相应的分支语句，这种输出方式逻

辑简单，就是单纯的比较跳转，但是相应的代码量较大；

三、其它情况都采取方案c进行输出，这种方式较为复杂。又分为

几种情况，但是都有一个共同的特征，就是会产生一个由每个

分支所对应的标号组成的一个标号列表，最终是通过标号列表

的标号位置+偏移的形式实现跳转。

在该情况下，如果最小值minval在0-3之间，那么minval被

重新赋值为0，range的值就是maxval；如果最小值不在0-3之

4/7

间，则minval不做改变，range的值仍为maxval–minval。

确定了range值之后，接下来调用函数try_tablejump()来进

行处理，首先将switch(x)中要比较的值x与minval相减，得到

一个index值，然后调用函数do_tablejump()进行实际的处理。

在do_tablejump()中，先将index和range作比较，如果index

大于range，说明该值不在case所包含的范围之内，因此直接

跳转到default分支；如果index不大于range，则有可能在case

范围之内。然后生成一个由标号列表首位置+index*4的一个位

置，该位置就是要跳转到的结果。

接下来剩余的工作就是来确定标号列表的内容了，首先这个

标号列表的第一个标号是minval所对应的分支标号，然后计算

所有case到minval的差，差是N的话，该case所对应的分支

就在列表的第N+1位，如果中间有空缺，则用default分支来填

充，由于每个case都是不一样的，因此它们与minval的差也都

是唯一的，所以可以通过差值来唯一索引到其对应的标号。因

此在do_tablejump()中，只要计算出要比较的值x和minval的

差index，则标号列表首位置+index*4就是其要跳转的分支标号，

这个标号对应的case值必然是和x相等的。如有以下语句：

5/7

每个分支所对应的标号是按照每个分支的low的值排序的，low

越大，对应的标号也越大。比如上面的default分支为L2，则case

-4对应的标号为L3，case1分支为L4，case5分支为L5，

7——L68——L7；而从上到下，每一个case与最小值-4的差

分别为:

case1:差值为5，因此列表的第6位为其对应的标号L4；

case7：差值为11，因此列表的第12位为其对应的标号L6；

case8：差值为12，因此列表的第13位为其对应的标号L7；

case5，10，11：差值分别为9，14，15，因此列表的第10、15、

16位都是其对应的标号L5；

除上面之外其它的列表位都是default分支对应的标号L2.

因此最终生成的标号列表内容为：

L8:

.longL3//case-4

.longL2//default

.longL2

6/7

.longL2

.longL2

.longL4//case1,与-4的差为5

.longL2

.longL2

.longL2

.longL5//case5,差为9

.longL2

.longL6//case7

.longL7//case8

.longL2

.longL5//case10

.longL5//case11

由于a=8，与最小值-4的差为12，因此直接用L8+12，得到

的就是与a相同的case所对应的分支，即最终要跳转的结果。

最后一点要说明的是，标号列表的输出有两种方式，一种是上面例子中列出

的，直接位置输出，这种形式中，标号列表是由各个标号直接组成的；第二种方

式为间接位置输出，标号列表的内容是各个标号到该标号列表的差：

L8：

.longL3-L8

.longL2-L8

…

使用哪种方式来输出是通过宏CASE_VECTOR_PC_RELATIVE来决定，其

值为0，则以绝对位置形式输出，如果为1，则为相对位置形式输出。这两种方

式所使用的输出宏是不一样的，绝对位置的输出宏为

ASM_OUTPUT_ADDR_VEC_ELT，相对位置的输出宏为

ASM_OUTPUT_ADDR_DIFF_ELT，这两个宏是不能共存的，也就是一个后端只

7/7

能采取其中一种方式来进行输出，我们的编译器采取的是绝对位置的方式来输

出。同时需要的注意的方面是，对于不同的输出方式，后端模板也不一样，在相

对位置方式中，由于标号列表中是减法得到的位置差，因此要得到标号位置，还

要首先进行一个加法得到标号的绝对位置，然后再进行跳转；而直接位置中就不

需要先进行加法这一步，直接跳转就可以了。

[文档可能无法思考全面，请浏览后下载，另外祝您生活愉快，工作顺利，万事如意!]