从零编写现代编译器 12 - SSA 构造与 phi 节点
第 09 篇用 alloca/load/store 把可变变量映射到栈内存。这种做法能让代码生成跑起来，但优化器看到的是一堆内存操作，无法直接判断哪些 load 读的是同一个值。常量传播要穿透内存别名分析，复杂度远超必要。 SSA（Static Single Assignment）要求每个变量恰好被定义一次。当同一个变量在不同路径上获得不同值时，合流处放一个 phi 节点完成合并。优化器只需沿定义-使用链就能追踪值的流动。本篇从第 10–11 篇的 CFG 和支配关系出发，构造 SSA 并替换掉第 09 篇的临时内存形式。 数据结构变化：从变量到值 第 10 篇的 Block 只存储无类型的指令列表和终结符，块参数用 (VarId, Ty) 表示——还是以变量为中心的视角： 1234567// 第 10 篇的 Blockpub struct Block { pub id: BlockId, pub params: Vec<(VarId, Ty)>, pub body: Vec<Inst>, pub terminator:...
从零编写现代编译器 11 - 支配关系、活跃变量与数据流
第 10 篇建立了控制流图——基本块是节点，跳转和分支是边。结构搭好了，但编译器还不能回答两个关键问题。第一：在分支合流的位置，变量的值从哪条路径来？这个问题决定了 phi 节点的放置（第 12 篇的主题）。第二：某个变量在某个位置之后是否还会被读取？如果不会，它占用的寄存器可以释放，对它的赋值也可以删除。 回答第一个问题需要支配关系分析（dominance analysis），回答第二个问题需要活跃变量分析（liveness analysis）。两者都属于数据流分析的范畴，共享同一个计算框架：在 CFG 上反复传播信息，直到所有块的信息集合不再变化——这个终止状态叫做不动点（fixed point）。 什么是支配 从 CFG 的入口块出发，如果到达块 B 的每一条路径都必须经过块 A，就说 A 支配（dominate）B，记作 A dom B。这个定义有几个直接推论。入口块支配所有块，因为任何路径都从入口开始。每个块都支配自身，因为"经过自身"这个条件平凡成立。如果 A 支配 B 且 B 支配 C，那么 A 也支配 C——支配关系具有传递性。 严格支配（s...
从零编写现代编译器 10 - 基本块、跳转与 CFG
第 09 篇用 alloca/load/store 把可变变量映射到 LLVM IR 的栈槽，if/else 和 while 通过 LLVM 的基本块和条件跳转来实现。程序跑起来了，但控制流完全藏在 LLVM 里——我们自己的编译器看到的仍然是一棵 HIR 树，无法对分支和循环做任何分析。第 11–12 篇要构造 SSA，前提是程序已经被拆成显式的基本块和跳转。本篇就来做这件事。 什么是基本块 基本块（basic block）是一段顺序执行的指令序列，满足两个约束： 控制流只能从第一条指令进入。不存在从外部跳到块中间的边。 控制流只能从最后一条指令离开。这条指令叫做终结指令（terminator），它要么跳转到另一个块，要么从函数返回。块内其余指令不改变控制流。 换句话说，基本块要么整体执行，要么整体不执行。这个性质让后续的数据流分析可以把整个块当作一个节点处理，而不必逐条指令跟踪控制流。 终结指令只有三种形式就够了： 无条件跳转：执行完本块，跳到目标块继续。 条件分支：根据一个布尔值，跳到两个目标块之一。 返回：离开当前函数，把值交给调用者。 一个块如果没有终结指令，...
从零编写现代编译器 09 - 条件、循环和可执行程序
第 08 篇让编译器支持了函数定义和调用，递归与前向引用都已经工作。但每个函数体仍然是一条直线——从第一条语句顺序执行到最后一条，中间没有任何分支或重复。写不出 if，写不出 while，程序能做的事极其有限。 本篇加入条件分支和循环，让 Sprout 成为一门图灵完备的语言。完成后，sum_to(10) 将编译成本机程序并输出 55。 if/else 进入 AST 和 HIR if 的语法结构包含三部分：条件表达式、then 分支、可选的 else 分支。条件必须是 bool 类型，类型检查器直接拒绝整数条件。 1234567fn abs_diff(a: i64, b: i64) -> i64 { if a > b { return a - b; } else { return b - a; }} AST 节点记录条件、then 块和 else 块。降低到 Typed HIR 时，条件必须为 Bool，两个分支按语句处理。当前 if 只作为语句；将来作为表达式...
从零编写现代编译器 08 - 函数调用、递归和返回值
到第 07 篇为止，所有 Sprout 程序都只有一个 main 函数。表达式、变量、类型检查和参考解释器都工作正常，但程序无法把逻辑拆分成多个独立部分。本篇加入函数声明、函数调用、递归和一个内置的运行时打印函数，让 Sprout 开始像一门真正的编程语言。 签名收集：先扫描，再检查 函数之间可以互相调用，调用可能发生在被调用函数的定义之前。如果类型检查器从上到下逐个处理函数体，遇到一个尚未见过的函数名就只能报错。这不是我们想要的行为。 解决办法是分两趟处理。第一趟只扫描所有 fn 声明的签名——函数名、参数列表和返回类型——把它们记录到一张全局签名表里。第二趟才进入每个函数体做类型检查。这时签名表已经完整，任何函数都可以调用任何其他函数，包括自身。 12345678910111213// 第一趟：收集签名for decl in &program.functions { let sig = Signature { params: decl.params.iter().map(|p| (p.name, p.ty)).collect(...
从零编写现代编译器 07 - 用参考解释器固定语言语义
第 06 篇完成了类型检查，1 + 2 能通过检查，true + 1 被拒绝。但类型检查只回答"这个程序有没有类型错误"，不回答"这个程序执行后结果是什么"。编译器目前还没有任何部分说 1 + 2 的结果是 3。 本篇在 Typed HIR 上直接建一个参考解释器。它递归遍历节点，维护变量环境，按确定的规则求值，把结果打印出来。这个解释器将成为整个系列的语义基准：后续编译器生成本机代码后，任何测试用例只要和解释器的输出不一致，就说明降低、优化或代码生成出了错。 值的表示 解释器执行 HIR 节点后产生值。当前语言只有三种类型，值的表示对应地简单： 12345enum Val { I64(i64), Bool(bool), Unit,} I64 携带 64 位有符号整数，Bool 携带布尔值，Unit 对应没有有意义返回值的表达式（赋值、打印调用等）。后续加入数组和结构体时，这个枚举会扩展，但三种基础值从本篇开始就固定下来。 环境：栈帧与变量绑定 解释器需要知道每个变量当前的值。环境用一组栈帧表示，每个...
从零编写现代编译器 06 - 类型检查与 Typed HIR
第 05 篇完成了名称解析：每个变量引用都绑定到了确切的定义。但编译器仍然不知道 x + y 是在做整数加法还是布尔运算。这篇给 AST 中的每个表达式节点分配类型，产出一棵全新的中间表示——Typed HIR。类型检查不通过的程序将被拦在代码生成之前。 类型的表示 Sprout 当前只有三种值类型和一个内部哨兵： 123456enum Ty { I64, Bool, Unit, Error,} I64 对应 64 位有符号整数，Bool 对应布尔值，Unit 是没有有意义返回值时使用的类型。Error 不是语言中可写的类型，它只在类型检查发现错误时注入节点，防止一处错误沿表达式树向上引发大量连锁报告。如果操作数之一已经是 Error，类型检查器直接把结果也标为 Error，不再重复报错。 自底向上的类型检查 类型检查器遍历名称已解析的 AST，对每个表达式节点计算类型。过程是自底向上的：先确定叶子节点的类型，再根据操作符的规则推导父节点。 字面量。 整数字面量的类型是 I64，true 和 false 的类型是 Bool。 二元运算...
从零编写现代编译器 05 - 名字、作用域与可变变量
第 04 篇构建了 AST，表达式和语句有了树形结构。但 AST 中的名字只是字符串。两个不同作用域里都叫 x 的变量，在树上看起来完全一样——解析器不关心它们指向谁。如果直接把字符串传给后续阶段，类型检查器和代码生成器就必须各自重复"这个 x 到底是哪个 x"的查找逻辑。 本篇在 AST 之上增加一趟名称解析。遍历语法树，维护一个作用域栈，给每个声明分配唯一的定义 ID，把每个名字引用绑定到对应的定义。完成后，后续阶段只需要查 ID，不再处理裸字符串。 DefId 与符号表 每个变量声明得到一个编译期唯一编号 DefId。它是符号表的索引，整数类型，可以复制、比较、打印，不携带字符串。 123456789101112131415161718192021222324252627282930#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]pub struct DefId(pub u32);#[derive(Debug)]pub struct DefInfo { pub name: String...
从零编写现代编译器 04 - 表达式解析与错误恢复
第 03 篇给了编译器完整的词法分析器和源码位置。解析器已经能识别函数定义和 return 语句，但 return 后面那个表达式还只能接受单个整数字面量。return 1 + 2 * 3; 在当前解析器面前会直接报错——它不知道运算符是什么，更不知道 * 应该比 + 先结合。这一篇要解决这个问题：用 Pratt 解析实现一个完整的表达式解析器，正确处理优先级和结合性，并在遇到语法错误时恢复到可继续解析的状态。 优先级表 表达式里运算符的优先级决定了 AST 的形状。1 + 2 * 3 应该解析为 1 + (2 * 3) 而不是 (1 + 2) * 3。Sprout 语言的优先级从低到高： 优先级 运算符 结合性 说明 1 || 左结合 逻辑或，短路 2 && 左结合 逻辑与，短路 3 == != 左结合 相等比较 4 < > <= >= 左结合 大小比较 5 + - 左结合 加减 6 * / 左结合 乘除 7 一元 - ! 前缀 取负、逻辑非 所有二元运算符都是左结合。a + b + c 解析...
从零编写现代编译器 03 - 语句解析：let、赋值和分号
上一篇把源码拆成了 Token 序列。一行 let mut x: i64 = 0; 经过词法分析后变成 Let、Mut、Ident("x")、Colon、Ident("i64")、Assign、Int(0)、Semi 这样一串扁平记号。但 Token 序列不包含结构信息——编译器还不知道这是一条变量声明、一条赋值还是一条返回语句。这一篇的任务是把 Token 流解析成结构化的语句节点：let 声明、赋值、return 和块。 语句的文法 先用一组产生式把 Sprout 当前支持的语句写下来。这里只处理语句层面，表达式的优先级和结合性留给第 04 篇。 12345678910111213stmt → let_stmt | assign_stmt | return_stmt | expr_stmtlet_stmt → "let" ["mut"] IDENT ":" type "=" exp...
