其实编译器本身也是个程序而程序总得有别的程序来编译它。一旦你决定用这门语言自己写一个编译器最经典的死锁就出现了编译器要跑起来才能编译代码可它自己还没被编译出来得先有另一个编译器来编译它。这个循环就是编译器圈著名的鸡生蛋问题。破解的方法正是自举bootstrapping而落到工程上就是标题里这三个动作先做一棵种子编译器再做二次编译最后用字节级对拍收口。这篇文章记录的是我自己折腾的一门微型语言myl的完整自举过程。我会把种子编译器该怎么做小、三次构建的命令长什么样、为什么字节级对拍比功能测试更硬、以及我在这个过程中踩过的几个大坑全部摊开来讲。适合正在写解析器或目标代码生成的朋友也适合对可复现构建reproducible builds感兴趣的人。你不需要事先懂编译原理太多我会把每个为什么要这样做都解释清楚。1. 自举到底在解决什么问题1.1 鸡生蛋还是蛋生鸡先把这个困境描述得更精确一点。假设你设计了一门新语言myl编译器的源码是用myl自己写的。一份myl源码要变成可执行文件必须经过mylc这个编译器的处理可是mylc本身就是这份源码编译出来的东西它还不存在。你于是陷入一个死锁要运行编译器先得有编译器。现实世界里破这个死锁的办法只有一条找一棵外部跳板。也就是暂时放弃完全用myl写编译器的执念先拿一门已经能运行的语言——比如 C——写一个非常小的编译器它只要能完成一件事把myl源码转成机器码。不求性能、不求完整、不求优雅够用就行。这个又小又糙的跳板就是种子编译器。打个比方这就像造船。你要造一艘能继续造出更多工业船的母船总得先从手工作坊里敲出第一艘简陋的船哪怕它漏水、跑得慢但它能把你送上远航的起点。种子编译器就是这样一艘工业母船。1.2 三次编译形成的信任链现在我们把整个链路拆开看每一层具体在干什么。假设编译器源码一共有四个文件lexer.myl、parser.myl、codegen.myl、main.myl我们把它们统称SRC。构建过程按顺序是这样的T0种子编译器。它是一份 C 源码seedc.c由系统里的 GCC 编译成可执行文件seedc。T1第一次编译。seedc读取SRC产出可执行文件mylc-stage1。这是myl历史上第一个用自己语言编译出来的编译器自举在这里正式发生。T2第二次编译。mylc-stage1再次读取同一份SRC产出mylc-stage2。T3第三次编译。mylc-stage2又一次读取同一份SRC产出mylc-stage3。然后重点来了我们不拿 T1 和 T2 比而是拿 T2 和 T3 比。为什么因为 T1 是种子编译器生成的种子的代码生成策略大概率很粗糙而mylc-stage1是完整编译器两者生成的机器码可能只是行为等价字节上并不一样这是正常的。真正有意义的是 T2 和 T3 的关系T3 是 T2 自己编译出来的自己如果这两个文件逐字节完全相同说明编译器到达了自己的不动点——它编译自己时产出完全稳定每一代之间没有任何漂移。这是判断自举成功最经典的判据。提示字节一致是一个非常强的结论。它证明的不光是编译器能编译自己还包括这份编译器在编译自己源码时行为完全可复现。后面我会专门讲对拍怎么做以及哪些因素会破坏字节一致。1.3 现实世界里的大项目怎么自举这套思路不是玩具实验几乎所有主流自举编译器都在跑同一条链路只是规模和工具链复杂得多。项目种子来源自举方式GCC系统自带的宿主 C 编译器三阶段 bootstrapmake bootstrap跑完三层后对 stage2 和 stage3 的 .o 文件用cmp逐字节比较GoGo 1.4最后一个用 C 写的版本用 C 编译器构建 Go 1.4再用它构建用 Go 写的 1.5现代版本则用GOROOT_BOOTSTRAP指定的旧 Go 作为种子Rust前一个稳定版的rustcstage0 编译源码得到 stage1stage1 再编译得到 stage2工具链和标准库分层构建TCC宿主 C 编译器Tiny C Compiler 体量极小自举路径很直接SBCL宿主 Lisp 实现用宿主 Lisp 跑一个交叉编译器在目标环境上生成第一个 SBCL注意一个共性任何自举项目都绕不开一个外部信任锚点也就是种子从哪来。种子本身的正确性无法由自举证明它能证明的是从种子之后整条链路的每一代都保持一致。说白了自举解决的是工程一致性问题不是数学正确性问题。这也是为什么对拍、测试集、可复现构建这些配套手段必须跟上。2. 种子编译器选型、设计与验证2.1 种子的边界只做必须做的事写种子编译器最大的误区是一上来就想把语言特性做全。我最初给myl设计了闭包、泛型、异常处理结果种子光实现这些就写了大几千行而且调试痛苦到怀疑人生。后来我把设计砍到能用就好整数运算、数组、指针、结构体、函数、if/while/return、简单的print系统调用封装。种子编译器就能在 2600 行 C 代码里完成所有工作。因为种子的核心目标只有一个能编译自托管源码。所以边界应该按这个原则划定语言层自托管源码里出现的语法特性种子必须全部支持自托管源码没用到但语言文档里存在的高级特性种子可以一概不实现。换句话说让编译器源码迁就种子而不是让种子迁就语言梦想。代码生成层不要写寄存器分配器。所有表达式按栈机方式求值中间结果一律压栈函数参数也走栈传递。性能差一点无所谓正确性好调试最重要。运行时层编译产物直接调用 libc 的函数做输出和内存分配链接时交给系统cc即可。省去自己维护运行时库的负担。这一个减法省下的工作量是决定性的。栈机式代码生成虽然生成的代码又慢又啰嗦但每条语句的栈平衡逻辑非常直观出 bug 时一眼能看出来。2.2 用 C 写一个最小可用编译器mylc_seed.c的内部结构非常经典就是典型的四段式手写词法分析器把源码切成 token递归下降解析器把 token 流变成解析结果符号表记录函数和全局变量代码生成器直接边解析边发射 x86-64 ATT 汇编。拿myl源码里最常见的整数加法举例代码生成部分长这样/* 生成一条加法指令把栈上两个操作数弹出相加后压回 */ static void gen_add(void) { printf(\tpopq %%rax\n); printf(\tpopq %%rcx\n); printf(\taddq %%rcx, %%rax\n); printf(\tpushq %%rax\n); }这就是栈机式代码生成的典型形态中间结果全部住在运行时栈上编译器本身不需要维护哪些寄存器被占用。表达式a b * 2的生成过程就是先发射a的压栈代码、b的压栈代码、2的压栈代码再发射乘法最后发射加法。每次运算都从栈里消费操作数、把结果留在栈顶。为了让种子具备自我诊断能力我在种子里加了几组命令行开关--dump-asm把生成的汇编打出来--trace-parse打印递归下降的进入和退出--version确认当前跑的是哪个构建产物。这几个开关在后面排查二次编译问题时帮了大忙。2.3 动手之前先规划测试集很多人在种子上写完就急着自举结果自举失败后根本分不清是种子 bug、解析器 bug 还是代码生成 bug。正确顺序是先建立独立测试集再谈自举。我的做法是在tests/下放了一批小用例每个用例有明确期望输出tests/ arith.myl # 整数四则运算与取模 ctrl.myl # if / while / break func.myl # 函数调用与返回值 ptr.myl # 指针与数组下标 recur.myl # 递归求斐波那契然后用一个脚本把每个用例编译、运行、比对期望输出#!/usr/bin/env bash # tests/check_tests.sh —— 用指定的编译器跑测试集 CC$1 FAIL0 for t in tests/*.myl; do name$(basename $t .myl) $CC $t -o /tmp/t_${name} out$(/tmp/t_${name}) exp$(cat tests/${name}.expected) if [ $out ! $exp ]; then echo FAIL $name: got $out, want $exp FAIL1 fi done [ $FAIL -eq 0 ] echo ALL TESTS PASS这里有个必须反复强调的观点自举本身只能证明一致性不能证明正确性。就算 T2 和 T3 字节一样它们也可能是一对优雅地共享同一个错误的坏编译器。所以种子必须先通过独立设计的 golden 测试确认行为符合预期再让 T1、T2、T3 去对拍。测试集是正确性的根字节对拍是稳定性的根两个根缺一个都不行。3. 二次编译三阶段构建的操作细节3.1 完整构建流程的命令假设仓库目录结构如下myl/ seed/seedc.c src/lexer.myl src/parser.myl src/codegen.myl src/main.myl build/三阶段构建的完整命令是cd /work/myl mkdir -p build # Stage 0用系统 gcc 构建种子编译器 gcc -O0 -fno-ident -o build/seedc seed/seedc.c ./build/seedc --version # Stage 1种子编译自托管源码得到第一个自举编译器 ./build/seedc src/lexer.myl src/parser.myl src/codegen.myl src/main.myl \ -o build/mylc-stage1 ./build/mylc-stage1 --version # Stage 2自举编译器编译自己的源码 ./build/mylc-stage1 src/lexer.myl src/parser.myl src/codegen.myl src/main.myl \ -o build/mylc-stage2 ./build/mylc-stage2 --version # Stage 3再来一次 ./build/mylc-stage2 src/lexer.myl src/parser.myl src/codegen.myl src/main.myl \ -o build/mylc-stage3 ./build/mylc-stage3 --version第一次看到build/mylc-stage1 --version正常输出版本号时我极其兴奋——这意味着myl已经能编译自己了。但千万别急着庆祝后面还有字节级对拍这一关。而且请注意每一条编译器调用的参数必须完全一致包括源码顺序、-o路径。任何一处不同产物都可能天然不同对拍就失去了意义。3.2 构建脚本里的确定性设置手工敲命令容易漏我强烈建议把所有步骤收进一个bootstrap.sh并且把确定性写死在脚本里#!/usr/bin/env bash # bootstrap.sh —— 三阶段自举 字节对拍 set -euo pipefail cd $(dirname $0) readonly SRCsrc/lexer.myl src/parser.myl src/codegen.myl src/main.myl # 固定种子编译参数避免宿主 gcc 版本差异引发困惑 gcc -O0 -fno-ident -Wall -Werror -o build/seedc seed/seedc.c ./build/seedc $SRC -o build/mylc-stage1 ./build/mylc-stage1 $SRC -o build/mylc-stage2 ./build/mylc-stage2 $SRC -o build/mylc-stage3 echo hashes sha256sum build/mylc-stage1 build/mylc-stage2 build/mylc-stage3 echo byte comparison cmp build/mylc-stage2 build/mylc-stage3 echo BOOTSTRAP OK几个细节解释一下SRC变量写出具体文件名而不是用src/*.myl。因为 shell 的 glob 扩展虽然默认按字典序可一旦有人改了文件名或加了文件顺序就可能变产物的函数排放顺序也随之变。显式列表最稳。-O0是给种子用的降低种子二进制被宿主编译器优化出诡异行为的概率。种子慢一点无所谓反正它只工作在自举的最初几分钟。-fno-ident抑制 GCC 往目标文件里写版本标识字符串这个字符串会影响字节对拍。虽然用同一台机器的同一个 gcc 时它是一致的但规范化处理会让对拍结果更干净。链接我最后是直接走cc驱动的。如果不想看到 ELF 里多出来的 build-id 之类的元数据可以追加-Wl,--build-idnone。3.3 为什么要多跑一遍第三阶段只跑一次自举拿到 T1不能回答一个关键问题T1 是不是一个合格的编译器更具体地说T1 是种子编译出来的如果种子里某个指令的生成有偏差这种偏差会全部遗传给 T1。而 T1 在编译自己源码时可能恰好绕过了那个偏差对应的路径于是看起来一切正常实际上编译器已经被污染了。多跑一遍让 T2 编译出 T3意义就完全不同了。T2 是完整编译器自己生成的T3 是 T2 的又一次自复制。如果 T2 和 T3 字节相同意味着 T1 和 T2 在编译编译器源码这个特定输入上行为完全一致。用公式表达就是T1(SRC) T2(SRC)而 T2 T3(SRC)所以整个链条在自指问题上达到不动点。注意字节一致不等于种子绝对正确它只证明自举链路稳定。想要证明编译器符合语言规范必须靠前面说过的 golden 测试集。字节对拍提供的是可信trustworthinessgolden 测试提供的是正确correctness两者是互相补充的关系。4. 字节级对拍如何证明自举成功4.1 对拍什么、怎么对拍对拍这个词最早来自信息学竞赛圈的调试玩法写一个朴素程序和优化程序喂同一组随机数据比较两边输出是否一致。把这套思路搬到编译世界就是给 stage2 和 stage3 喂同一份编译器源码比较它们吐出来的产物是否一致。最直接的手段是哈希$ sha256sum build/mylc-stage2 build/mylc-stage3 b50e8e18d6e2c5b3a9f2fd5d6c4a7e1e038c2f1d2b8a9c4f1f0d0a1b2c3d4e5f build/mylc-stage2 b50e8e18d6e2c5b3a9f2fd5d6c4a7e1e038c2f1d2b8a9c4f1f0d0a1b2c3d4e5f build/mylc-stage3两串哈希一致说明文件大概率相同。想进一步确认或者说想看看差异到底在哪用cmp$ cmp build/mylc-stage2 build/mylc-stage3 # 无输出 文件逐字节完全一致 $ cmp -l build/mylc-stage2 build/mylc-stage3 # 有输出时每行列出不同字节的偏移八进制和两个文件的字节值如果编译器在构建时会输出多个文件目标文件、汇编、可执行文件那就对整个目录做对拍$ (cd build/stage2 find . -type f -exec sha256sum {} \; | sort) /tmp/hash-stage2.txt $ (cd build/stage3 find . -type f -exec sha256sum {} \; | sort) /tmp/hash-stage3.txt $ diff /tmp/hash-stage2.txt /tmp/hash-stage3.txt注意排序那一步find的输出顺序依赖于目录遍历顺序不排序的话即使内容一样 diff 也会报差异亲测踩过。4.2 从字节一致到行为一致字节一致是强条件但它只能覆盖同样的输入同样的产物这一个点。完整的多级对拍我建议这样搭第一层哈希与字节比较。快速判断 stage2 和 stage3 在自编译下产出的文件是否完全相同。第二层汇编级对拍。我给mylc加了-S选项只输出汇编不链接。这样可以把代码生成和链接剥离开单独对比前端和代码生成器的行为$ ./build/mylc-stage2 -S src/codegen.myl -o /tmp/cg_stage2.s $ ./build/mylc-stage3 -S src/codegen.myl -o /tmp/cg_stage3.s $ diff -u /tmp/cg_stage2.s /tmp/cg_stage3.s如果汇编一致但最终可执行文件不一致问题大概率出在链接端如果汇编都不一致那就是代码生成器内部行为漂移了需要回溯到 T1 阶段排查。第三层行为级对拍。字节不同只能说明不一致不能说明谁对谁错。用 stage2 和 stage3 分别编译测试集再运行对比 stdout、stderr 和退出码#!/usr/bin/env bash # tests/diff_test.sh —— stage2 与 stage3 的行为对拍 set -u S2../build/mylc-stage2 S3../build/mylc-stage3 FAIL0 for t in tests/*.myl; do name$(basename $t .myl) $S2 $t -o /tmp/diff_${name}_2 $S3 $t -o /tmp/diff_${name}_3 /tmp/diff_${name}_2 /tmp/diff_${name}_2.out 21; r2$? /tmp/diff_${name}_3 /tmp/diff_${name}_3.out 21; r3$? if ! diff -q /tmp/diff_${name}_2.out /tmp/diff_${name}_3.out /dev/null || [ $r2 -ne $r3 ]; then echo FAIL $name (exit: $r2 vs $r3) FAIL1 fi done [ $FAIL -eq 0 ] echo ALL BEHAVIOR TESTS PASS这套三级体系下来字节一致性和行为一致性都能被持续验证任何一个环节回归都能快速定位到具体层次。4.3 破坏字节一致性的六个常见坑我在跑对拍时反复被下面这些问题坑过整理成速查表坑现象解决办法源码里用了__DATE__/__TIME__宏两次编译产物总差几个字节自举实验阶段直接禁用这两个宏或把构建时间固定编译器把__FILE__绝对路径写进产物换目录构建后产物全变统一相对路径编译路径上不带构建机器信息符号表用了无序哈希表每次构建符号输出顺序随机用数组保存插入顺序查找另建映射链接器写入.comment/ build-id两文件尾部固定偏移总不同加-fno-ident、-Wl,--build-idnone源文件用*.myl通配符且文件较多顺序依赖 shell难以稳定复现显式写出源文件列表并行构建但脚本不严谨中间文件被覆盖或写乱seed / stage 构建串行执行这里特别展开说说符号表这个坑因为它最隐蔽。如果你在编译器里用类似unordered_map的结构保存函数和全局变量输出符号时直接遍历它那么每次运行时哈希桶的迭代顺序都可能不一样。同样的源码、同样的编译器、同样的参数产物却每次都在变对拍直接失败。解决办法很简单按源码中出现的先后顺序把符号存进数组查找时再用哈希表辅助。这样输出的符号顺序永远稳定。4.4 进阶思考种子本身可信吗讲到这里有经验的朋友可能会想到编译圈那个著名的思想实验Ken Thompson 的 Reflections on Trusting Trust。它说的是一个恶意编译器能在编译自己时把自己的后门悄无声息地复制进下一代而且你无论怎么重编译都清除不掉这个后门因为每一次重编译都由带后门的编译器自己执行。这时候 T2 等于 T3 也没用——你比较的是同一血统的两个后代它们共享同一个祖先的缺陷。对抗这种攻击的思路是用不同来源的种子做双独立编译diverse double-compilation分别用两个互不相关的种子编译器构建同一个源码然后对拍产物。只有两个独立谱系产出的字节一致单点信任链才算被打断。我在实践阶段没有完整做这件事但对这套方法的价值印象很深。至少它提醒我种子编译器的代码必须自己一行行读熟、吃透它是整个信任链的根节点。5. 常见问题与排查技巧实录5.1 常见问题速查表这是我自举实验中真正遇到过的故障整理成表方便大家对照现象可能原因处理办法stage2 编译自己时直接段错误代码生成错误常见为运行时栈不平衡或栈帧分配不足对目标文件加-S导出汇编人肉检查关键函数入口/出口的push、pop是否配对stage2 和 stage3 字节总不一致符号表顺序不稳定或路径/时间戳被嵌入用cmp -l找到不同偏移再用readelf -S看差异属于哪个 ELF 段stage1 能编译测试集却编译不了自己测试集没覆盖编译器源码用到的语法特性让编译器的自托管源码尽量使用已验证的子集缺口处补自举专用测试编译产物运行起来死循环解析器没吃掉某个 token或 while 条件生成错误开--trace-parse看递归下降是否卡在同一个规则上cmp -l差异集中在文件尾部基本是 ELF 元数据节.comment、.note链接时加--build-idnone编译时加-fno-ident换个目录重新构建产物全变源码或构建脚本里混入绝对路径统一用相对路径必要时用SOURCE_DATE_EPOCH固定时间戳多文件编译报重复定义编译器对声明 vs 定义处理不一致检查符号表里函数和全局变量的插入逻辑多文件时是否重复注册字节一致但两个编译器行为各不相同编译器存在依赖未定义行为的代码生成路径单独跑行为级对拍缩小到具体测试用例再人工读汇编5.2 让调试不再盲人摸象自举调试最痛苦的是一旦出问题你根本不知道是种子的 bug、解析器的 bug、代码生成器的 bug还是环境差异导致的。我的经验是先建立三个调试抓手再开始盲搜。第一是给编译器加足够的 trace 开关。--dump-asm能看最终汇编--trace-parse能看解析过程--dump-symbols能看符号表内容。没有这些开关出了问题只能盯着段错误猜效率极低。第二是制定最小复现策略。当 stage2 编译自己失败时我会在src/里注释掉一个函数或一个语法分支重新跑一遍三阶段。通过二分法定位到是哪个文件、哪个功能触发了失败。这个手法和大项目里用git bisect定位回归是一个思路先缩小范围再讨论修复。第三是保存金标准汇编。在自举稳定之后把tests/里每个用例的-S输出提交进仓库作为 golden 文件。以后任何一次代码生成器的改动都可以用diff直接看到影响范围。这一步的收益在后期迭代编译器时是巨大的——它能让你在改完寄存器分配策略后瞬间知道哪些用例的汇编发生了变化。5.3 我的实操心得与建议整个实验做下来我最想分享三条心得。第一条把减法做在前面。我最初设计myl的时候总想面面俱到闭包、泛型、模式匹配全都要。结果种子编译器写了不到一半我就意识到每多一个语言特性种子就要多实现一整套对应的编译逻辑。砍掉高级特性之后种子只用 2600 行 C 就撑起了整个自举闭环。如果你也想做类似实验请一定先把语言子集压到最小数组、指针、结构体、函数、if/while、整数运算足够了。第二条字节级对拍必须脚本化并挂进持续集成。我把bootstrap.sh和check_tests.sh组合成一个make check-bootstrap目标每次修改编译器源码后一键跑完三阶段构建和所有对拍。后面有几次我改动符号表实现差点引入顺序不稳定的问题就是靠这条命令立刻抓出来的。对拍不是一次性的仪式它是每次迭代的守门员。第三条把小实验跑通了再去看大项目你会豁然开朗。做完myl的自举之后我再回去读 GCC 的 bootstrap 脚本、Go 的GOROOT_BOOTSTRAP机制突然就理解了它们为什么要那样设计。自举是一条放眼所有语言编译器都贯通的工程链路小语言让你看清骨架大项目教你怎么把骨架长出血肉。我在实际跑通cmp无输出、两个sha256完全一致那天对着终端愣了好几秒。那种感觉不是测试全绿能比的——你看到的是一个编译器用自己把自己完整复制了出来每一代都分毫不差。后来再做任何跟工具链相关的项目我都会下意识保留一个字节级对拍的环节因为它是判断系统是否真的稳定最诚实的一把尺子。如果你也打算动手实验我把最大的经验浓缩成两句话种子尽量小测试尽量全。剩下的事就是让编译器安静地编译它自己。