守株阁

第 10–13 篇从零构建了 CFG、SSA、常量传播和无用代码删除。这些 pass 足够说明数据流分析的核心思路，但它们只覆盖了产品级优化器的极小一角。LLVM 经过二十余年的迭代，包含指令组合、循环展开、向量化、寄存器分配、指令选择等数百个 pass。本篇把自制 SSA 翻译成 LLVM IR 文本，接入这条管线，让 Sprout 程序获得真正的优化与本机代码生成。 从自制 SSA 到 LLVM IR 翻译的核心映射并不复杂。自制 SSA 里的每个值对应 LLVM IR 中一个 % 命名的虚拟寄存器；基本块参数翻译成 LLVM 的 phi 节点；Sprout 的 i64 直接映射为 LLVM 的 i64，bool 映射为 i1；函数签名翻译成 define 声明。 以 sum_to 为例，--emit=llvm 输出： 123456789101112131415161718define i64 @sum_to(i64 %n) {entry: br label %looploop: %sum = phi i64 [0, %entry], [%sum.next, ...

第 12 篇完成了 SSA 构造。每个值只有一个定义点，优化器可以沿定义链追踪数据流。程序已经具备了被分析的结构基础，但结构本身不减少指令数量。本篇实现第一批真正的优化：常量传播和无用代码删除，把 SSA 从"可分析的中间表示"变成"更精简的中间表示"。 常量折叠：编译期完成的算术 最直接的优化是常量折叠（constant folding）。如果一条算术指令的两个操作数都是编译期已知的常量，编译器直接计算结果，用一个常量值替换这条指令。 优化前的 SSA 片段： 12345v1 = const 3v2 = const 5v3 = add v1, v2v4 = mul v3, v3return v4 v1 和 v2 都是常量，add 的结果在编译期可以确定为 8。替换后 v3 变成 const 8，接着 mul v3, v3 的两个操作数也是常量，折叠为 64。三条算术指令最终变成一个常量返回。 SSA 的单定义性质让替换可靠——v1 在整个函数里只有一个定义点，所有使用 v1 的地方看到的值都是 3，不存在"某条路径上 v1 被...

第 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:...

第 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...

第 09 篇用 alloca/load/store 把可变变量映射到 LLVM IR 的栈槽，if/else 和 while 通过 LLVM 的基本块和条件跳转来实现。程序跑起来了，但控制流完全藏在 LLVM 里——我们自己的编译器看到的仍然是一棵 HIR 树，无法对分支和循环做任何分析。第 11–12 篇要构造 SSA，前提是程序已经被拆成显式的基本块和跳转。本篇就来做这件事。 什么是基本块 基本块（basic block）是一段顺序执行的指令序列，满足两个约束： 控制流只能从第一条指令进入。不存在从外部跳到块中间的边。 控制流只能从最后一条指令离开。这条指令叫做终结指令（terminator），它要么跳转到另一个块，要么从函数返回。块内其余指令不改变控制流。 换句话说，基本块要么整体执行，要么整体不执行。这个性质让后续的数据流分析可以把整个块当作一个节点处理，而不必逐条指令跟踪控制流。 终结指令只有三种形式就够了： 无条件跳转：执行完本块，跳到目标块继续。 条件分支：根据一个布尔值，跳到两个目标块之一。 返回：离开当前函数，把值交给调用者。 一个块如果没有终结指令，...

第 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 只作为语句；将来作为表达式...

到第 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(...

第 06 篇完成了类型检查，1 + 2 能通过检查，true + 1 被拒绝。但类型检查只回答"这个程序有没有类型错误"，不回答"这个程序执行后结果是什么"。编译器目前还没有任何部分说 1 + 2 的结果是 3。 本篇在 Typed HIR 上直接建一个参考解释器。它递归遍历节点，维护变量环境，按确定的规则求值，把结果打印出来。这个解释器将成为整个系列的语义基准：后续编译器生成本机代码后，任何测试用例只要和解释器的输出不一致，就说明降低、优化或代码生成出了错。 值的表示 解释器执行 HIR 节点后产生值。当前语言只有三种类型，值的表示对应地简单： 12345enum Val { I64(i64), Bool(bool), Unit,} I64 携带 64 位有符号整数，Bool 携带布尔值，Unit 对应没有有意义返回值的表达式（赋值、打印调用等）。后续加入数组和结构体时，这个枚举会扩展，但三种基础值从本篇开始就固定下来。 环境：栈帧与变量绑定 解释器需要知道每个变量当前的值。环境用一组栈帧表示，每个...

第 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。 二元运算...

第 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...