实现switch语句并进行binary search优化

djh 发布于

最后更新于

准备

先前，我正在用C语言实现一个简单的基本支持C89标准但是还支持少数几个C99标准和GNU C标准的C语言编译器，其中需要实现switch语句。

在开始进行switch实现之前，我需要简单描述一下switch的语法。

通常的swtich语法类似于如下结构：

1
2
3
4
5
6
7
switch(<expression>){
    case <constant-int-expr>:
        <statement>
    <...>
    default:
        <statement>
}

但是其实switch的ANSI C（新版本在此语法上变化应该不大，所以直接采用这个版本，虽然比较老，但是我是先找到完整的ANSI C的语法格式才开始写的编译器）标准语法格式如下：

1
switch ( <expression> ) <statement>

前文中的case <constant-expression>: <statement>实际上属于<labeled-statement>这个non-terminal symbol的一个production body，在ANSI C下，这一推导式完整格式为

1
2
3
<labeled-statement> ::= <identifier> : <statement>
                      | case <constant-expression> : <statement>
                      | default : <statement>

由于这种语法设计的特殊性，导致switch实际上完全支持这类扭曲写法

1
2
3
4
5
6
switch(a){
    for(;i<10;i++){
      case 2: a ++;
    }
    case 3: a += 3;
    }

这一神奇格式也被于Duff’s device，当然，这个东西在当下是否有用并非本文内容，故不做讨论。

为了能实现这个代码，需要给switch的ast中添加一些新的属性。完整定义如下

1
2
3
4
5
6
7
struct _switch {
    struct astn *cond;
    struct astn *body;
    struct dynarray case_refs;
    struct astn *default_ref;
    LLVMBasicBlockRef break_block;
} _switch;

其中的case_refs与default_ref分别用于存储case们和default的指针。dynarray是我自己实现的一个数据结构，稍微有些类似于C++中的std::vector<void*>。break_block会在switch的codegen阶段设置，用于在switch body中出现break语句时跳出switch。

另外，在实现parser对token流解析时，当解析到到switch语句后，会给parser添加一个指明当前switch的上下文属性，在随后解析到case标签的语句时可以将此case语句添加到switch的ast中，方便switch追踪case。

1
2
3
4
5
6
7
8
9
10
11
12
13
// p -> parser结构体
// 解析switch
parser_consume(p);
sel = ast_new(ast_statement_switch);
parser_consume_with(p, '(');
sel->_switch.cond = parse_expression(p);
parser_consume_with(p, ')');
astn prev_switch_scope = p->switch_scope;
astn prev_break_scope = p->break_scope;
p->break_scope = p->switch_scope = sel;
sel->_switch.body = parse_statement(p);
p->switch_scope = prev_switch_scope; // here
p->break_scope = prev_break_scope;

我们可以看到除了给parser设置一个switch_scope外，我们其实还做了很多事情，由于break可以中断switch的fallthough特性（一般情况下break是用于迭代表达式中执行中断迭代操作的），此时break就不仅可能用于中断switch的fallthough，还能用于中断迭代表达式的迭代。而C语言的语法又是支持嵌套的，所以需要暂存和恢复break_scope和switch_scope。

接下来，在解析<labeled-statement>中，当遇到case和default时，需要专门查找parser的上下文，将这两种<labeled-statement>添加到switch的ast的附加属性中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// label是<constant-expression>,经过求值后通过label->primary.v._int可取出long类型的值
astn ls = ast_new(ast_statement_labeled);
ls->labeled_statement.type = label_type;
ls->labeled_statement.label_value = label;
ls->labeled_statement.stmt = stmt;
if (label_type == TOK_KW_CASE) {
  if (parse_statement_labeled_case_check_duplicate(p, label)) {
    compiler_error(p->lexer, "duplicate case label:%ld",
                   label->primary.v._int);
  }
  if (!p->switch_scope) {
    compiler_error(p->lexer, "case label not in switch statement");
  }
  log_trace("add case label:%ld", label->primary.v._int);
  dynarray_add(&p->switch_scope->_switch.case_refs, &ls); // here
} else if (label_type == TOK_KW_DEFAULT) {
  if (!p->switch_scope) {
    compiler_error(p->lexer, "default label not in switch statement");
  } else if (p->switch_scope->_switch.default_ref) {
    compiler_error(p->lexer, "duplicate default label");
  }
  log_trace("setting default label");
  p->switch_scope->_switch.default_ref = ls; // here
}
return ls;

这样，我们就完成了switch的parse过程，可以进行codegen过程了。

最简单的顺序codegen

相似的代码化表示逻辑

以如下代码为例

1
2
3
4
5
6
7
8
switch(<expr>){
  case 1: <statement>
  case 2: <statement>
  case 3: <statement>
  default: <statement>
}
SWITCH_AFTER:
<statement>

类似于

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
T v = expr;
/* 一个循环生成的单位起始 */
if(v == 1) goto CASE_1;
else 
/* 一个循环生成的单位结束 */
if(v == 2) goto CASE_2;
else if(v == 3) goto CASE_3;
else goto DEFAULT;
CASE_1:
  <statement>
  goto CASE_2;
CASE_2:
  <statement>
  goto CASE_3;
CASE_3:
  <statement>
  goto SWITCH_AFTER;
DEFAULT:
  <statement>
  goto SWITCH_AFTER;
SWITCH_AFTER:
  ...

如果没有default，则为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
T v = expr;
if(v == 1) goto CASE_1;
else if(v == 2) goto CASE_2;
else if(v == 3) goto CASE_3;
else goto SWITCH_AFTER:
CASE_1:
  <statement>
  goto SWITCH_AFTER;
CASE_2:
  <statement>
  goto SWITCH_AFTER;
CASE_3:
  <statement>
  goto SWITCH_AFTER;
SWITCH_AFTER:
  ...

具体构建过程

我们使用LLVM作为后端，因此需要

  1. 构建BasicBlock
  2. 构建跳转到cond block的指令
  3. 生成switch body

无论是一般的算法，还是二分查找优化的switch算法，主要修改的地方都是对cond处理的代码块，其他地方基本不会发生变化，因此我们可以对算法进行封装，并在执行算法之前将builder定位到cond块以简化流程。最后将builder定位到switch after块以正确保证下一步的代码生成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LLVMBasicBlockRef switch_body =
    LLVMAppendBasicBlockInContext(b->context, b->fn, "switch_body");
LLVMBasicBlockRef switch_after =
    LLVMAppendBasicBlockInContext(b->context, b->fn, "switch_after");
LLVMBasicBlockRef switch_cond =
    LLVMAppendBasicBlockInContext(b->context, b->fn, "switch_cond");
LLVMBuildBr(b->builder, switch_cond);
n->_switch.break_block = switch_after; // set break block for break in switch body statment
// create switch body first to avoid getting empty basic block in cond block processing
LLVMPositionBuilderAtEnd(b->builder, switch_body);
build_statement(b, n->_switch.body);
LLVMBuildBr(b->builder, switch_after);
  LLVMPositionBuilderAtEnd(b->builder, switch_cond);
  build_statement_switch_algo_ordered(b, n, switch_after); // here
  LLVMPositionBuilderAtEnd(b->builder, switch_after);

我们在算法开始时构建表达式求值的语句，并且为了方便检查，我们在算法开始时会将所有case排序。

1
2
3
4
5
typed_value cond_val = build_expression(b, n->_switch.cond);
astn cond_val_base_type =
    build_type_chain_get_base_type(&cond_val->type_chain);
qsort(n->_switch.case_refs.data, n->_switch.case_refs.used,
      n->_switch.case_refs.item_size, build_statement_switch_case_ref_cmp);

我们使用qsort进行排序，case_refs的类型在之前已经提及：dynarray，其用一段连续的空间来存储数据，因此可以借用qsort进行排序。调用qsort时传入了一个自己定义的函数build_statement_switch_case_ref_cmp来进行比较。

1
2
3
4
5
6
7
8
9
10
11
static int build_statement_switch_case_ref_cmp(const void *a, const void *b) {
  astn *case_ref_a = (astn *)a;
  astn *case_ref_b = (astn *)b;
  assert((*case_ref_a)->labeled_statement.label_value->type ==
         ast_expr_primary);
  assert((*case_ref_b)->labeled_statement.label_value->type ==
         ast_expr_primary);
  long case_v_a = (*case_ref_a)->labeled_statement.label_value->primary.v._int;
  long case_v_b = (*case_ref_b)->labeled_statement.label_value->primary.v._int;
  return case_v_a - case_v_b;
}

接下来我们迭代cases_ref来生成对cond的判断和跳转，它的逻辑主要是：

  • 生成cond_val和每个case_v比较的cmp指令
  • 根据cmp结果跳转，如果结果为真，跳转到每个case对应的代码块，否则跳转到新块case_test_after（用于兼容SSA格式IR）
  • 调整builder的位置到case_test_after块。
  • 迭代cases_ref
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
astn *case_ref;
dynarray_foreach(&n->_switch.case_refs, case_ref) {
  long case_v = (*case_ref)->labeled_statement.label_value->primary.v._int;
  LLVMValueRef case_cmp =
      LLVMBuildICmp(b->builder, LLVMIntEQ, cond_val->v,
                    LLVMConstInt(build_type_base_type_convert_to_llvm(
                                      b, cond_val_base_type),
                                  case_v, 1),
                    "case_cmp");
  LLVMBasicBlockRef case_test_after =
      LLVMAppendBasicBlockInContext(b->context, b->fn, "case_test_after");
  LLVMBuildCondBr(b->builder, case_cmp,
                  (*case_ref)->labeled_statement.start_block,
                  case_test_after);
  LLVMPositionBuilderAtEnd(b->builder, case_test_after);
}

迭代完成后，此时cond的值和所有的case都不同，因此还需要生成跳入default或跳出switch块。

1
2
3
4
5
6
astn _default = n->_switch.default_ref;
if (_default) {
  LLVMBuildBr(b->builder, _default->labeled_statement.start_block);
} else {
  LLVMBuildBr(b->builder, switch_after);
}

我们在构建case和default这种<labeled-statement>时，会设置自己的start_block属性，用于随后构建switch的cond时候进行跳转使用。这也是需要先构建switch的body再构建cond求值的原因。

二分查找优化codegen

相似的代码化表示逻辑

以如下代码为例

1
2
3
4
5
6
7
8
9
10
switch(<expr>){
  case 1: <statement>
  case 2: <statement>
  case 3: <statement>
  case 4: <statement>
  case 5: <statement>
  default: <statement>
}
SWITCH_AFTER:
<statement>

类似于

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
T v = <expr>;
/*递归生成主体起始*/
if(v == 3) goto CASE_3;
else goto CASE_EQ_3_AFTER;
CASE_EQ_3_AFTER:
if(v < 3) goto CASE_LT_3_AFTER;
else goto CASE_GT_3_AFTER;
CASE_LT_3_AFTER:
/*递归生成主体结束*/
if(v == 2) goto CASE_2;
else goto CASE_EQ_2_AFTER;
CASE_EQ_2_AFTER:
if(v < 2) goto CASE_LT_2_AFTER;
else goto CASE_GT_2_AFTER;
CASE_GT_2_AFTER:
goto CASE_DEFAULT;
CASE_LT_2_AFTER:
if(v == 1) goto CASE_1;
else goto CASE_EQ_1_AFTER;
CASE_EQ_1_AFTER:
if(v < 1) goto CASE_LT_1_AFTER;
else goto CASE_GT_1_AFTER;
CASE_GT_1_AFTER:
goto CASE_DEFAULT;

CASE_GT_3_AFTER:
if(v == 4) goto CASE_4;
else goto CASE_EQ_4_AFTER;
CASE_EQ_4_AFTER:
if(v < 4) goto CASE_LT_4_AFTER;
else goto CASE_GT_4_AFTER;
CASE_LT_4_AFTER;
goto CASE_DEFAULT;
CASE_GT_4_AFTER:
if(v == 5) goto CASE_5;
else goto CASE_5_AFTER;
CASE_5_AFTER:
if(v < 5) goto CASE_LT_5_AFTER;
else goto CASE_GT_5_AFTER;
CASE_GT_5_AFTER:
goto CASE_DEFAULT;
CASE_LT_5_AFTER:
goto CASE_DEFAULT;

CASE_DEFAULT:
  ...

在此，不列出没有default的情况，写起来太累了，它基本只是将CASE_DEFAULT替换成SWITCH_AFTER。

具体构建过程

在分析构建过程之前，我们先看一看二分查找的实现代码，二分查找优化算法的生成是在此基础上实现的。

1
2
3
4
5
6
7
8
9
10
int binary_search(int arr[], int lo, int hi, int v){
  if(lo > hi) return -1;
  int mid = lo + (hi - lo) / 2;
  // 不使用 (lw + hi) / 2 避免溢出，毕竟这不是理想情况下的数学
  if(arr[mid] == v) return mid;
  else if(arr[mid] < v) lo = mid + 1;
  else hi = mid - 1;

  return binary_search(arr, lo, hi, v);
}

为什么要写成递归形式？因为方便将问题规约为更加简单的问题，代码比较好写。

二分查找逻辑上可以视作在一个完全平衡的二叉排序树上根据值的大小选择一条路径进行搜索。

而我们现在要做的并非查找，而是生成查找的代码，也就是说生成这个平衡二叉树本身，这意味着我们要生成所有路径，因此我们选择递归，生成这种风格代码比较简单。

接下来我们使用伪代码描述生成过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bsearch_codegen_algo(cases, low, high, cond_value, end_block){
  if(low > high) 构建跳转到`end_block`块的指令并停止生成过程

  mid = low + (high - low) / 2;
  构建指令：判断cond_value和mid对应的case值是否相等
  构建指令：根据测试结果，如果真，跳转到case值指向的块，如果假，跳转到`case_eq_%ld_after`块
  将builder定位到`case_eq_%ld_after`块
  构建指令：判断cond_value是否小于mid对应的case值
  构建指令：根据测试结果，如果真，跳转到`case_lt_%ld_after`块，如果假，跳转到`case_gt_%ld_after`块
  将builder定位到`case_lt_%ld_after`块
  递归调用 bsearch_codegen_algo(cases, low, mid - 1, cond_value, end_block)
  将builder定位到`case_gt_%ld_after`块
  递归调用 bsearch_codegen_algo(cases, mid + 1, high, cond_value, end_block)
}

这一过程类似于以下的对一颗平衡二叉树的生成过程：

  1. 生成当前节点
  2. 生成此节点的lhs
  3. 生成此节点的rhs

基于此，我们就实现了二分查找优化的switch语句。如果你想看具体实现，可以查看后文参考，我引用了我的仓库的链接。

总结和感悟

由于c标准支持很多我感觉十分扭曲难写的特性，比如非全局作用域的下的extern符号支持，传参时允许省略去符号，叠加函数格式声明导致产生类似于int F(int (int))等，导致代码越写越屎山，且最终放弃实现了很多功能，最终发现我可能现在更加缺乏代码组织能力。好在到最后磕磕绊绊地把大体写完了，tcc的testcase挑支持的功能来测试的话大部分都能通过。

对复杂语法的处理过程可以将其规约为较为简单的过程，从而降低理解的难度。另外，由于AST的存在，我认为编译器前端设计，尤其是语法树的构建，是十分符合以类概念为核心的面向对象风格代码组织的。

我是用C语言实现的C语言编译器前端，虽然它可以仿照那些语言级别支持面向对象的语言复现某些具有面向对象特色的代码组织，但终归心智负担较高，不如面向对象进行组织来的简单。在我实现codegen代码的后期，各种编译器的功能累加在一起后，所写的每一行代码，每一个新功能的心智负担都颇重，需要再三权衡是否能相对正确地将新功能集成在代码中。并在codegen阶段直接放弃了内存管理，只管分配不管回收。

正如我在某一篇知乎的帖子中刷到的：C语言或许更适合自底向上的模块化编写，同时保持每个模块本身实现起来较为简单，保证它的可读性。然后通过规范API，实现模块之间的可替换，最后像堆积木一样堆出来一座高塔。可能这才是目前情况下C语言在偏上层开发中最适合的生态位吧。总之下次写编译器相关的代码我多半不会大面积利用C语言了，复杂度高起来我这种刚入门的代码水平根本把持不住，还是需要其他外力控制一下，比如语言标准。

参考

djh

djh

此刻正是，摸鱼之时

71
2
95
NOTICE

如果你看到这个信息，你就看到了这个信息。

CATEGORIES
TAGS
BIOS android archlinux arduino arm asm bison bitcomet brainfuck c/c++ c11 c23 cheat_engine ci/cd clash conda cuda debian devops docker express fail2ban fastapi flex gcc gin git gitea golang hadoop hollow_knight ipc java jlink jupyter kaleidoscope keil latex linux lisp llvm log4js mariadb matplotlib msvc nasm nginx nodejs ntp onedrive opencv php posix pve python raidrive raspberry_pi_pico rdp rockylinux rom sdcc setuptools spark ssh stc89c52rc system_v systemd termux ubuntu unity vcvarsall_bat vps vs2022 vscode vue3 webdav windows wordpress wsl wsl2 yum 中文字体 加密 单片机 反向代理 大数据 应用 开发 移动开发 算法 编译原理 跳转表 链接 零刻 鸿蒙