Sherfiter's wiki for fun

第 10 章 · 目标代码生成与迷你编译器实战

收官章把前九章的零件拼成一台真的编译器:IR 进,汇编出, gcc 能链接,程序能跑。本章先讲代码生成的核心问题(指令选择、寄存器分配),然后给出完整实战:一个算术语言(变量、赋值、if、while)从源码到 x86-64 的全程,最后是学习路线图。

10.1 代码生成三件套

从 IR 到汇编,三个子问题:

指令选择:每种 IR 操作选哪条机器指令。朴素做法一对一(tac 的 t = a+b → mov+add),高级做法用树模式匹配(一撮 IR 树匹配一条寻址模式最强的指令,如 lea rax,[rdi+rsi*4] 一条顶四条,计组课第 10 章见过的编译器魔法)。x86 的 CISC 指令集让指令选择成为「选最短最快等价序列」的搜索。

寄存器分配:IR 假设无限寄存器,真机器只有 16 个(计组课第 4 章)。经典算法图着色:把「同一时刻活跃的变量」连边(活跃变量分析,第 9 章),给图着色(变量→寄存器),颜色数不够就把某些变量**溢出(spill)**到栈上(用前 load、用后 store)。

指令调度:利用流水线(计组课第 6 章),把会 stall 的指令隔开,-load-use 冒泡的填法(数据结构课没有,计组第 6 章有)。

三件套的顺序通常是指令选择 → 寄存器分配 → 调度,每次变换都可能给下一步新的机会(所以现代编译器跑多轮)。

10.2 迷你编译器全景:从源码到可执行

目标语言 mini:变量、算术、赋值、if/else、while、print。前九章的成果全部接上:

词法(第 2 章)→ 语法(第 3 章)→ AST(第 5 章)→ 语义检查(第 6 章)
    → IR 生成(第 7 章)→ 常量折叠(第 9 章)→ 指令选择(本章)→ x86-64

代码生成的落点(简化版,每变量一个栈槽,不搞寄存器分配 —— 但第 9 章活跃变量分析的结论可以指导「哪些变量值得进寄存器」的朴素分配):

// 表达式:结果放在 rax(计组课第 10 章的返回值约定)
void gen_expr(const Node *n) {
    switch (n->kind) {
        case ND_NUM:  emit("mov eax, %d", n->value); break;
        case ND_VAR:  emit("mov eax, [rbp-%d]", slot(n)); break;
        case ND_ADD:
            gen_expr(n->lhs);
            emit("push rax");            // 左值入栈保护
            gen_expr(n->rhs);
            emit("mov ecx, eax");
            emit("pop rax");             // 取回左值
            emit("add eax, ecx");
            break;
    }
}
// 语句:while → 标签 + 条件跳转(第 7 章 IR 的汇编直译)
void gen_stmt(const Node *n) {
    switch (n->kind) {
        case ND_IF: {
            int id = new_label();
            gen_cond(n->cond, id);       // 条件不成立跳 else
            gen_stmt(n->then);
            emit("jmp .Lend%d", id);
            emit(".Lelse%d:", id);
            gen_stmt(n->els);
            emit(".Lend%d:", id);
            break;
        }
    }
}

编译主流程(全程串起九章):

int main(int argc, char **argv) {
    tokenize(read_file(argv[1]));    // 第 2 章
    Node *ast = program();           // 第 3/5 章
    check(ast);                      // 第 6 章:符号表 + 类型
    gen_data(); gen_code(ast);       // 第 7/10 章:IR → 汇编
    return 0;
}

产出的汇编文件交给 gcc 汇编链接:gcc out.s -o mini,然后跑起来。看着自己写的语言跑通第一个程序,是这门课最值得珍藏的时刻。

10.3 验证与调试:编译器的编译器测试

编译器是「吃代码吐代码」的程序,测试策略:golden test——对每个样例程序,存一份期望输出,CI 里逐个编译运行对比。调试顺序从上往下:token 对不对(打印 token 流)→ AST 对不对(打印树/DOT,第 5 章)→ IR 对不对(打印 TAC)→ 汇编对不对(和 gcc -O0 的输出对照思路)。每层有独立的可检查产物,这是编译器作为管道的可调试性红利;哪层断的,看哪层的打印,不要隔着三层猜。

10.4 学习路线图

走出本课后,进阶的三条路:

  • 动手派:读《Crafting Interpreters》做 clox(C 版字节码解释器,和本课实验互补:它走「字节码 + 栈机」路线),再啃 chibicc 源码(几千行的真 C 编译器,可读性极佳);
  • 工具派:学 LLVM IR 与 opt pass 接口,写一个自己的优化 pass(如死代码删除),体会工业级 IR 的设计;
  • 应用派:把编译技术用回本行——数据库的 SQL 引擎、模板引擎、规则引擎、代码生成器,第 2、3、9 章的技术原样迁移。

常见错误

  • 表达式求值的 push/pop 不平衡。gen_expr 每层 push 一次,子表达式不是叶子时少 push,栈错位后面全崩;每个 case 过一遍「进出栈配平」。
  • 标签不唯一。if 嵌套 if 标签重名,跳错位置;标签计数器是全局的,永不重置。
  • 栈没对齐就 call。System V 要求 call 前 rsp 16 对齐(计组课第 10 章),不对齐在调用 printf 等库函数时崩溃(movaps 段错误),经典坑。
  • 只在「正例」上测试。错误输入(未声明变量、类型错、除零)的路径不测,交付的编译器遇到真实代码即崩;第 6 章的错误恢复也要测。

练习

  1. 动手:完成 10.2 的迷你编译器:实现变量赋值、if/else、while、print 语句,写三个测试程序(阶乘、斐波那契、九九表)编译运行,gcc 链接跑通。
  2. 动手:给你的编译器加一个「朴素寄存器分配」:局部变量按第 9 章活跃分析,不重叠的共用栈槽,对比优化前后帧大小(用第 8 章的布局方法算)。
  3. 动手:golden test 框架:目录里放 *.mini + *.expect,脚本逐个编译运行对比输出,故意改坏一个 case 验证框架会报警。
  4. 思考:本课的编译器把每个变量放栈上,性能远差于 gcc -O2。列出三个差距(寄存器分配、循环优化、指令选择),按「实现难度 ÷ 收益」排序,挑一个你下一步真想实现的,写出伪码。
豫ICP备2026027944号