9cc 的第一个可以实现自举(bootstrap)版本发布了。它是一个实现了 C99 的标准编译器,除了以下几个特性之外:

  1. 可变数组
  2. inline, register, restrict, volatile: 这些关键字都是程序员用来提示编译器做优化的,目前都被忽略。
  3. _Complex, _Imaginary: 这两个关键字是用来科学计算的,也被忽略。
  4. long double:目前跟 double 无异,而且标准并无强制。

除了上述特性,其他的都实现了。可以看到,上述特性其实并不影响使用,但实现起来不是几句代码的事情。后续版本或许会考虑吧,但至少目前重点不是这个 :-)

理论和实际


9cc 还是一个类似龙书上的传统的编译器,它的流程大概是这样的:

源文件 -> 预处理 -> 词法分析 -> 语法和语义分析 -> 中间代码生成 -> 代码生成

为何说它是传统的呢?因为现代的编译器虽然还是这么做,但设计方面却是大不一样了,现代编译器要考虑跟 IDE 的集成(代码高亮、补全、折叠等等),考虑输出更加人性化的错误提示,而错误处理确实是非常复杂的一块。最重要的是,由于 IDE 里,随便修改源文件,就要重新生成整个 AST,这对性能又有极高的要求。

因此,传统编译器中所追求的一趟式编译在此处显得苍白无力,只有多遍,编译器才能收集更多的信息,给出更加智能化的提示,而不是一出错就给一句简单粗暴的 syntax error at xxx.

例如,在传统的理论教科书里(如龙书),说到词法分析器,大都侧重于正则表达式匹配,以及如何使用甚至构建如 Lex 这样的自动工具。可是却对实现一个真正工业界级别的词法分析器无只言片语,还在用双缓冲区设定。9cc 一开始就是用双缓冲区的设定,无论源文件又多大,都可以以固定大小的缓冲区来分析,真是非常地节省内存呢!可是一遇到大文件(现在几千行的 C 源文件很常见,它们至少都是上百 KiB),性能就被 GCC 吊打,以约 16MiB 的 sqlite3.c 测试,差距竟然高达20倍!也就是说,9cc 做一次预处理要 2s,而 GCC 只要 0.1s !

震惊之余,我对 GCC 和 9cc 都进行了跟踪分析,最终发现,差距主要在读取文件上,GCC 调用了 100 次 read,而 9cc 就会调用 2000 多次!大家都知道,磁盘IO乃是性能瓶颈之所在。GCC 的做法是,无论源文件多大,都一次性读入到内存中,而 9cc 按照缓冲区大小读入,假设缓冲区大小是 4KiB,对于一个 16MiB 的文件,它就要读取 4096 次!

于是在 v0.2 中,我简单修改了下,采用了 GCC 这种简单的方法,这样后续的词法分析也会非常简单。因为双缓冲区还有一个致命的缺陷就是回退历史是有限制的。

GCC 这样的设计可谓是非常的务实的,在内存如此大的今天,特别是,编译器本身是跑一下就退出的程序,并不常驻内存,因此,耗费这点内存,换取的来的是更快速的实现,也是更好的实现。我在以前的一篇博文中也已经提及了,只是当时并无体会到这巨大的性能差距。

链接:词法分析器的设计和实现(C)

再谈词法分析器


词法分析器最核心的目标就是:,是的,而且要非常快!

如果达不到这一点,无论理论多么强大,代码多么优雅,都是毫无意义的摆设。

C 语言的词法分析器受到一个丑陋的威胁

C 语言里允许在行尾以字符 \ 作为连接符,连接下一行。

所以,本来你可以使用一个字符指针简单的一直前行直到下一个换行符出现,但是现在,你不得不处理这个情况,当你遇到换行符,你要判断下前一个字符是不是 \,如果是,则相当于你要同时忽略 \ 和 换行符。被这两个字符隔开的字符逻辑上是连续的。于是,事情就变得复杂了。

目前我知道的有两种处理方法:

  1. 每次都调用类似 read_char 这样的函数来获取一个字符,read_char 里自己判断下这种情况。
  2. 遇到 \ 和 换行符时,把后面的字符全部向前移动两个字符,覆盖掉这两个字符,使得我们还是可以简单的使用一个字符指针不断前行。

可以预见的是,第一种方案代码看起来简洁,可是效率并不高。想象一下,对于一个正常大小的源文件,词法分析器被调用上百万次、上千万次,都是家常便饭。虽然 read_char 函数很简单,代码没几行,可是这上千万次的函数调用开销可不小。

GCC 使用的是第二个方案,原来我考虑到的,所有字符向前移动两个字符可能会带来更多开销。可是 GCC 对这个函数进行了优化,使用了 CPU 的高级指令如 Intel 的 SSE

这里简单介绍下 GCC 的处理,代码在 libcpp/lex.c 中 (cpp 是 C Preprocessor 的意思,不是 C Plus Plus)。GCC 把输入以行为单位来划分,_cpp_clean_line 函数就是处理这种情况的。上面所说的移动字符,也仅是对本行,而不是对整个缓冲区,再加上,使用 \ 一般都是宏定义出现的,其实不会非常多。大部分情况下,都只是简单的移动下字符指针。

汇编的语法


编译器教科书里不会有这个,一来是因为后端的语言并不一定是汇编,二是因为理论派不重视这个。然而,如果你想写后端,必须熟悉它。比如,必须查阅下 Intel 64 and IA-32 Manuals

由于 9cc 是在 Linux 下开发,所以使用的是 gas 的汇编,也就是 AT&T 的汇编,它跟 Intel 的最大差别在于左右操作数是相反的

Intel: mov dst, src
AT&T:  mov src, dst

另一个区别是寻址方式的写法:

Intel: [base + index * scale + disp]
AT&T:  disp(base, index, scale)

还有个区别就是操作符的大小:

Intel: push dword 33
AT&T:  pushl $33

也就是说,AT&T 会把大小以后缀方式写在操作符上。

总之,大概是这样的区别。如果说有优劣的话,当然是那些按照 Intel 的语法来的汇编器会好一些,因为在查阅文档和写代码之间不需要额外的脑力开销。

一趟 vs 多趟


前面稍稍提过了,早期由于计算机性能所限,加上没有现在这些功能庞大的 IDE,编译器的实现都追求一趟。典型的如 lcc,边语法分析边生成代码。打个类似的比喻,一趟式就相当于 XML 解析中的 SAX,而多趟式就相当于 DOM。很显然,一趟式虽然速度快,但是缺少多趟式的「全局观」,编译器掌握的上下文信息不够,难以提供有价值的信息。如果要与 IDE 整合,显然是不行的。

IDE 常见的功能有代码高亮、代码定义跳转、代码补全、代码折叠、智能的错误修复(能让你点击一下鼠标就插入正确的代码)。代码高亮不难,属于词法分析阶段。后面的几个功能都需要有 AST (Abstract Syntax Tree),问题在于,源文件时刻都被改动,这时候肯定要重新生成 AST,不然补全的信息可能就不对了。所以,效率又成为了问题,通常所有的文件都会被生成 AST 并保存在内存中(所以 IDE 很耗内存),为了不刷新整个 AST,需要其他各种技术来使得性能最高,这又是一个复杂的话题了。

常用数据结构对性能的影响


集合、散列表、向量、链表,这是会频繁用到的数据结构。它们的实现是直接影响到编译器的效率。龙书在这个方面没有着墨。《编译器设计》(Engineering a Compiler)在附录中倒是有专门提到这个,算是对龙书一个不错的补充。

下个小版本的目标


v0.3 将会以提高词法分析器的性能为目标,按照 GCC 的这种方案进行重构。至于语法分析和后端,是需要改动更大的,将会在更后面的版本更新。最好是把语法分析语义分析解耦,分成两趟。总之,我希望 v1.0 的时候就是终结的时候。