编译器自举实战：从种子到字节级对拍的完整记录

如果你自己写过一个编译器大概率对这个场景不陌生编译器源码里到处都是“我希望这里能有个很高级的语法糖”但你又很清楚一旦你用了它就永远无法自举。编译器自举说的就是让一个编译器去编译自己的源码那个最初用别的语言写出来、用来启动第一轮编译的编译器叫种子编译器等编译器能编译自己之后再用新编译器把源码重新编一遍叫二次编译把两轮产物逐字节对比叫字节级对拍。我最近用一个小型 C 子集编译器 sbcc 完整走了一遍这条链中间炸了无数次也留下不少可以直接抄作业的套路。今天就把这份实战记录整理出来。这套东西适合在写编译器、解释器、语言工具链的人参考尤其是想验证“我的编译器是不是真的够自洽”的人。可能你不做编译器但如果你对软件构建的可复现性、可信工具链感兴趣这篇也能帮你理解为什么有些项目宁可让构建过程慢一倍也要保证输出字节可复现。1. 自举这事到底在解决什么1.1 鸡生蛋的问题和种子的意义编译器不是凭空长出来的。要编译 C 代码你得先有一个能编译 C 代码的程序。那第一个 C 编译器怎么来的早期做法是先用别的语言写一个低级编译器再用它去编译真正的编译器。这个“先凑合能用”的版本就是种子编译器。放到我的项目里sbcc 是这样一个链条我用宿主机的 gcc 写了一个非常小的 C 编译器这就是 stage0种子。stage0 去编译 sbcc 的完整源码得到 stage1。stage1 再去编译同一份源码得到 stage2。比较 stage1 和 stage2。这里面的关键是“同一份源码”。如果编译器真的只依赖源码里定义的那些行为那么 stage1 和 stage2 在字节级别应该几乎一致。如果不一致说明编译器里面有隐藏的不确定性或者某些功能只有在第一次编译时碰巧正常后面就会被自己坑到。编译器的自举本质上是在说一件事编译器不只是能编译别的程序它有资格成为自己依赖链的一部分。一个不能自举的编译器总归是“寄宿”在别的工具链上的。能自举之后它才算真正独立。1.2 为什么不能编译一次就完事有人会问既然种子编译器已经能把源码编译成可执行文件了那直接用这个可执行文件不就行了为什么还要二次编译、三次编译我第一次做的时候也是这种想法。直到我发现stage0 和 stage1 的构建方式不一样stage0 是 gcc 编出来的它会带上 gcc 的某些头文件展开方式、默认宏、栈对齐策略stage1 是 sbcc 自己编出来的处理同一段源码的时候解析器对某些语法的接受程度可能和 gcc 不同。举一个最简单的例子。假如 sbcc 源码里写了int *p;而 sbcc 自己的解析器对*前后的空白处理有 bug那么 stage1 在编译这段代码时可能把它解析成乘法直接拒绝掉。这种问题在“编译别的程序”时可能永远测不出来但在“编译自己”时一定会暴露。因为你拿到的源码恰恰是用宿主编译器验证过的语法而你自己的编译器要去逐字解析同一份文件任何一个宽严不一致都会导致二次编译失败。所以二次编译不是仪式感它是对编译器正确性最残酷的回归测试。1.3 历史视角TCC、chibicc 和可复现构建玩过 C 编译器的人多少都听说过 TCCTinyCC它整个编译器加链接器大概十万行而且能用非常快的速度自举。chibicc 是另一个知名教学项目用大约几千行 C 实现了能编译自身的编译器作者在 README 里直接把自举作为一个测试项。这些项目传递出来的经验是自举需要刻意设计语言子集而不是事后再补。编译器一旦能自举后续对语法、类型系统、ABI 的改动都有了一个“安全网”。字节级可复现构建是自举之上更进一步的目标。我这次选择的是“尽可能小”的路线源码大概 3000 行 C目标平台 x86-64 Linux不支持结构体嵌套、不支持 switch、不支持float但支持指针、数组、全局变量、函数调用和基本的控制流。为什么砍掉这些因为自举编译器有个铁律你只能在源码里使用你能编译的语言功能。你要是想用 switch那你的编译器必须支持 switch你要是想用 float那你的解析器、代码生成、调用约定都得处理浮点寄存器。功能越多自举越难。2. 实验设计编译器到底怎么“长出”自己2.1 语言子集选型少即是多我定义了一个叫 S 语言的小型子集然后要求 sbcc 的源码只能用 S 语言写。这个约束一开始让我很难受因为我在写编译器时总是习惯性地想用switch、for、goto。结果全都要改成if-else和while。S 语言支持这些特性说明基础类型int、char、指针运算符加减乘除、取模、位运算、逻辑运算、关系运算、赋值控制流if-else、while、for、return函数支持递归最多 6 个参数符合 x86-64 SysV ABI数组一维数组可以用来做字符串字面量池指针指针运算、解引用、取地址全局变量支持初始化器不支持的东西就很明显了没有struct没有union没有enum没有switch没有float没有long long没有const。这意味着写编译器的内部数据结构时我得用“全局数组 偏移量”来模拟结构体或者用并行数组token_kind[token_count]、token_value[token_count]。这种设计的好处是解析器和代码生成器的实现会变得非常直白。没有复杂的 AST 节点类型一个节点就是一个 int 标记配上一个 int 数值。坏处是代码可读性下降但为了自举成功这是值得的。2.2 目标机选择x86-64 的最小子集我的 sbcc 直接生成 x86-64 汇编不经过中间表示不做寄存器分配所有局部变量都放栈上。寄存器只用于临时计算和函数调用传参。这种策略很像 1980 年代早期编译器的做法简单、粗暴、正确性优先。x86-64 的 SysV ABI 规定函数参数用rdi, rsi, rdx, rcx, r8, r9传递更多的参数用栈传递返回值放rax。我让 S 语言最多支持 6 个参数就是为了避免处理栈上参数对齐的麻烦。代码生成的一个关键点表达式求值用“栈机”模式。比如a b * c会生成mov rax, [rbp-8] ; a push rax mov rax, [rbp-16] ; b push rax mov rax, [rbp-24] ; c pop rbx ; b imul rax, rbx ; b * c pop rbx ; a add rax, rbx ; a ...性能非常差但生成逻辑极其容易验证。对自举来说性能不是问题正确性才是。2.3 编译器内部的三个模块我的 sbcc 分成三段词法分析器把源码切成 tokentoken 类型有类型、标识符、数字、符号、文件结束。递归下降解析器把 token 流变成表达式树和语句列表边解析边生成代码。代码生成器直接输出汇编文本文件再用系统 as 和 ld 汇编链接。没有独立语法树的做法省了很多内存管理也让我在写的时候不用处理malloc的释放问题。所有动态内存都用静态数组上限写死比如 token 数组最多 100 万个符号表最多 65536 个。超出就报错。这也算自举编译器的一个实践技巧能用静态数组就别用malloc。不然你在 3000 行代码里处理内存泄漏自举会变成噩梦。3. 核心实现哪些代码是自举的关键3.1 词法分析器空白、注释和 EOF 的坑词法分析器最容易出错的地方是文件结束和换行处理。我用一个全局变量cur保存当前字符用get_char()和unget_char()维护一个单字符回溯。int get_char(void) { if (src_pos src_len) return EOF; return src[src_pos]; } void unget_char(void) { if (src_pos 0) src_pos--; }单字符回溯足够处理、--、、||这种双字符 token。反而是“注释最后字符后直接到 EOF”这个场景我踩了坑注释/* ... */结束后如果紧跟文件结束我的代码会把 EOF 误判为一个普通字符。修复方式是每次读 EOF 时停下来而不是继续循环。token 结构很简单用并行数组int token_kind[MAX_TOKENS]; int token_val[MAX_TOKENS];token_val 对于数字就是整数值对于标识符就是符号表下标。这种设计在自举时不会遇到“结构体 self-reference”的问题因为压根没有结构体。3.2 递归下降解析器运算符优先级递归下降解析器是整套编译器的灵魂。我实现了 14 个优先级级别从逗号、赋值、三元、逻辑或、逻辑与、按位或、异或、与、相等、关系、移位、加减、乘除、一元。这里有一个常见误区很多教学编译器只处理 - * /就结束但 S 语言必须支持位运算和移位因为编译器内部经常用1 12这种表达式计算页对齐、用 0xFF取字节值。如果你不支持这些编译器源码就得用一堆除法乘法来模拟代码量立刻膨胀。优先级函数我统一写成parse_expr(int min_prec)的形式遇到优先级比min_prec低的运算符就返回否则继续解析右侧。这样可以避免一个优先级一个函数的重复代码。int parse_expr(int min_prec) { int lhs parse_unary(); while (1) { int bin_op cur_token; int prec bin_prec(bin_op); if (prec min_prec) break; next_token(); int rhs parse_expr(prec 1); emit_binop(bin_op, lhs, rhs); lhs new_temp(); } return lhs; }3.3 代码生成x86-64 的栈帧布局每个函数入口我生成push rbp mov rbp, rsp sub rsp, frame_size帧大小由函数体里所有局部变量和临时变量的总和决定。我在解析阶段先统计变量数量再生成序言。这意味着两遍处理第一遍扫描参数列表分配栈槽第二遍解析函数体生成指令。参数寄存器怎么存到栈上规则是前 6 个参数分别mov [rbp-offset], rdi等等。参数在符号表里记为“局部变量”偏移量为负数。局部变量按声明顺序递减分配。调用函数时我生成mov rax, arg1 push rax mov rax, arg2 push rax call func add rsp, arg_count * 8这里有个细节传递给被调用函数的第 7 个及以上参数如果用栈被调用函数并不知道栈上有几个参数是自己该用的所以我干脆禁止超过 6 个参数。S 语言函数定义和函数调用的自举检查里就有一条参数个数大于 6直接编译报错。4. 自举流程从种子到二次编译的完整记录4.1 构建目录与 makefile 设计项目目录结构很简单sbcc/ src/ sbcc.c # 完整源码S 语言写死 stage0/ sbcc_stage0 # 用宿主 gcc 编译 sbcc.c 得到的种子编译器 stage1/ sbcc_stage1 # stage0 编译 sbcc.c 得到 stage2/ sbcc_stage2 # stage1 编译 sbcc.c 得到 test/ sample.cmakefile 里的核心目标是这样stage0/sbcc_stage0: src/sbcc.c gcc -stdc99 -O0 -o $ $ stage1/sbcc_stage1: src/sbcc.c stage0/sbcc_stage0 ./stage0/sbcc_stage0 $ -o $ stage2/sbcc_stage2: src/sbcc.c stage1/sbcc_stage1 ./stage1/sbcc_stage1 $ -o $ bootstrap-check: stage1/sbcc_stage1 stage2/sbcc_stage2 cmp stage1/sbcc_stage1 stage2/sbcc_stage2编译命令伪装成./sbcc input.c -o output实际上内部会调用/usr/bin/as和/usr/bin/ld完成汇编和链接。4.2 第一次自举现场记录我记得很清楚第一次跑make bootstrap-check的时候阶段输出是这样的$ make stage1/sbcc_stage1 gcc -stdc99 -O0 -o stage0/sbcc_stage0 src/sbcc.c ./stage0/sbcc_stage0 src/sbcc.c -o stage1/sbcc_stage1 Parsing OK, code generated. Assembling... Linking... OK $ make stage2/sbcc_stage2 ./stage1/sbcc_stage1 src/sbcc.c -o stage2/sbcc_stage2 Parsing OK, code generated. Assembling... Linking... OK $ cmp stage1/sbcc_stage1 stage2/sbcc_stage2 $ echo $? 0cmp返回 0 意味着两个文件一模一样。当时我还不太信又跑了一次sha1sum看到两个哈希完全一致才算放心。那种感觉很难形容一个由 gcc 生成的编译器和由它自己生成的编译器在编译同一份源码时产物竟然逐字节一致。这说明这个编译器的行为已经完全由源码决定宿主编译器 gcc 的某些“性格”没有泄漏进来。4.3 为什么 stage0 和 stage1 不需要字节一致注意我只比较 stage1 和 stage2不比较 stage0 和 stage1。因为 stage0 是 gcc 生成的gcc 和 sbcc 的代码生成策略不一样stage0 和 stage1 不可能一致。真正能证明“自举成功”的是 stage1 和 stage2 一致。如果把比较范围扩大你会看到很多差异来自编译器内部环境变量、时间戳、文件路径、链接器版本。这些差异不是编译器的错而是构建系统的信息泄漏。stage2 和 stage3 之间如果有差异才需要警惕。我做过一个实验在 stage2 已有之后再用 stage2 编译一次得到 stage3然后比较 stage2 和 stage3。理想情况下它们也应该一致。如果 stage2 和 stage3 不一致说明编译器在重复运行时不稳定这种不稳定大多来自未初始化的变量、哈希表遍历顺序、或者依赖了环境变量。5. 字节级对拍验证自举的终极手段5.1 对拍到底在比什么字节级对拍说的就是把两个编译产物视为纯字节流逐个字节比较。它能发现的问题非常底层指令顺序不同比如两个阶段的编译器对同一个表达式生成了不同顺序的 push/pop。常量编码不同比如1被编码成 4 字节还是 8 字节。符号表顺序不同链接进可执行文件的符号名、节区排列顺序不一致。栈帧大小不同说明变量分配逻辑有偏差这是严重 bug。最常见的三种原因是符号表用qsort但没有稳定排序哈希表遍历顺序取决于插入顺序编译器运行时读取环境变量影响了输出。5.2 对拍命令清单我平时会准备几条命令一步一步排查# 1. 先看整体是否一致 sha1sum stage1/sbcc_stage1 stage2/sbcc_stage2 # 2. 如果不一致看第一个不同字节的偏移 cmp -l stage1/sbcc_stage1 stage2/sbcc_stage2 | head # 3. 看汇编输出差异需要先让编译器保留 .s 文件 diff (stage1/sbcc_stage1 src/sbcc.c -S) (stage2/sbcc_stage2 src/sbcc.c -S) | head # 4. 反汇编对比过滤掉地址后比较指令序列 objdump -d stage1/sbcc_stage1 | awk {$1; print} stage1.dis objdump -d stage2/sbcc_stage2 | awk {$1; print} stage2.dis diff stage1.dis stage2.dis | head第 4 条命令很实用ELF 文件里函数地址、全局变量地址可能不同但指令助记符序列应该一样。去掉地址列之后 diff就能过滤掉“合法但不影响行为”的地址差异。5.3 字节一致不等于行为一致这里要泼一盆冷水字节级对拍通过只能说明两个编译器在“给定输入”下产生了相同的输出。它不能保证编译器在所有输入下行为一致。我见过一个编译器对0和NULL的处理不同但对拍用的源码里刚好没有触发那条路径所以对拍通过但实际编译其他程序时崩了。所以对拍只是自举链里的一环不是终点。更完整的测试应该是测试项目的字节级对拍验证构建确定性普通测试用例集验证功能正确性编译自身后再编译自身验证编译器对自身的处理没有特殊化用不同优化等级自举验证不依赖未定义行为6. 实战中踩过的坑和排查思路6.1 stage1 拒绝编译自身源码最常遇到的坑就是gcc 能编译 sbcc.c但 stage0 生成的 sbcc_stage1 在编译 sbcc.c 时报错。我遇到过一个经典问题源码里写了for (;;)而我的解析器在处理空条件时要求必须有;但for (;;)的两个分号之间是空 token解析器把第二个分号之前当成了条件执行到;时发现 token 类型不对直接报错。修复方式很朴素parse_for里判断;之后如果下一个 token 还是;就表示条件为空直接把条件表达式设为常量 1。从这里学到的经验是写编译器的时候要经常“用自己编自己”来测试。你觉得理所当然的语法在实现里可能就是 bug。6.2 指针运算的符号扩展问题S 语言里指针减法是一个大坑。比如p - q在 C 语义里结果除以元素大小。但 sbcc 的int*相减我一开始做成mov rax, [p] sub rax, [q] sar rax, 2如果两个指针本身是负数低地址减法的结果可能被错误符号扩展。这个问题只有在我让编译器管理堆栈时才会出现某些局部区域用高位地址某些用低位地址两个地址相减会出现正负混淆。定位这个问题时我把所有sub指令都打印出来用一个小脚本统计哪些sub紧跟在mov之后目标操作数恰好是[rbp-x]和[rbp-y]。然后人工检查是不是指针相减。6.3 栈帧大小计算错误导致二次编译崩溃还有一次stage1 编出了 sbcc_stage2但 sbcc_stage2 编译任何程序都段错误。这就比较邪门了因为两个阶段的源码相同stage2 应该是从 stage1 正常生成的。排查过程让我记忆犹新。我打开反汇编发现 sbcc_stage2 的main函数序言里sub rsp, 0x...的栈帧大小比 stage1 少了一个字节对齐上来的 8 字节。原因是我在代码生成器里计算帧大小时把“压栈保存参数”和“局部变量分配”分成两步但局部变量分配时漏算了函数调用时的临时变量槽位。这个 bug 在 gcc 编译 stage0 时没暴露因为 gcc 生成的代码对栈帧大小没有那么敏感但 stage0 编出的 sbcc_stage1其运行时栈布局恰好踩到了边界导致call指令返回地址被覆盖。这次事故让我定下一条规则每次调整代码生成器后先跑一遍自举链再跑测试用例集。自举链不是可选步骤它是代码生成器质量的门禁。6.4 对拍通过但功能仍不对的特例有一种情况很坑stage1 和 stage2 完全一致但两者都是错的。比如我把加法生成了减法对拍当然一致因为两份可执行文件是一模一样的错法。这时候只能靠外部的测试用例不能靠对拍。所以我维护了一个tests/目录大概 50 个测试用例覆盖循环、递归、指针运算、数组下标、函数参数、全局变量初始化。每次自举成功之后我会把 stage1 和 stage2 分别拿去跑这一套测试对比两者的输出。如果 stage1 和 stage2 的输出一致但和预期不同那就是编译器本身有逻辑错误需要去查代码生成不能靠重复自举发现。7. 做自举编译器的一点心得和建议7.1 尽早把自举流程放进 Makefile我最后悔的是没有从第一天就把自举流程写进 makefile。一开始只是拿一堆测试用例验证功能直到某天我突然想“如果它能编自己会怎样”才手动跑起来。结果一跑就崩而且崩在完全没有想到的角落。建议任何编译器的 maintainer都从 v0.1 开始加入一个bootstrap目标。一旦你能自举每次改动后跑一遍能立刻发现问题。自举就变成了一个巨大的集成测试。7.2 字节级对拍不是目的确定性才是我现在不会特别执着于 stage1 和 stage2 是否逐字节一致。我更关心“差异是怎么产生的”。如果两个二进制文件相差几十个字节我会去看那些差异是不是来自构建 ID、文件路径、符号顺序。如果是那就接受如果不是那就要排查。其实很多时候字节级差异来自链接器而不是编译器。链接器可能把节区顺序排得不同或者插入了.comment段里的编译时间。所以对拍前我经常用strip和objcopy去掉元信息段再比这样能更快聚焦到真正的代码差异。strip stage1/sbcc_stage1 stage1_stripped strip stage2/sbcc_stage2 stage2_stripped cmp stage1_stripped stage2_stripped7.3 不要贪多功能子集越小越好做自举编译器最大的诱惑是想要支持很多功能。我今天加一个float明天加一个struct后天加一个switch每加一个功能自举链的复杂度就上一个大台阶。因为编译器源码必须用这些新功能重新实现内部逻辑。我的建议是先做到能自举的最小核心比如 int、指针、数组、函数、递归、控制流。自举稳定之后再逐步扩展功能每扩展完一个立刻跑一遍自举和对拍。这样能维持一个随时可用的“安全基线”。7.4 最后一个小技巧在排查自举链问题时我有一个保留节目修改编译器源码里的一个常量比如把某个默认阈值从 100 改成 200然后重新自举。如果这个修改能正确传导到 stage1、stage2说明编译器的常量传播没有坏如果 stage2 还是 100说明某个地方发生了“代码生成把立即数写死”的错误。这个技巧帮我抓到过至少两个深度 bug。做编译器自举本质上就是让编译器不断咬住自己尾巴转圈。这个过程既折磨人又让人上瘾。每次看到cmp返回 0我都会有一种真实的踏实感这东西没骗我它真的知道自己长什么样。