守株阁

第 15 篇的数组使用了 malloc 和 free 的直接配对：一个变量持有一块堆内存，作用域结束时释放。字符串让事情变得更复杂。两个变量可以指向同一份字符串——把 a 赋给 b 时，复制整块内存太浪费，让两者共享同一份数据更合理。但共享引入了新问题：a 退出作用域时，b 可能还活着。直接释放会导致悬垂指针；不释放又会泄漏。引用计数解决这个矛盾，而且不需要垃圾回收器。 堆上的字符串表示 Sprout 字符串存放在堆上，布局固定为三个部分： 123┌──────────────┬──────────────┬──────────────────────┐│ refcount: i64│ byte_len: i64│ bytes: u8 ... │└──────────────┴──────────────┴──────────────────────┘ refcount 记录有多少个变量指向这块内存。byte_len 是字节数组的长度。bytes 存放 UTF-8 编码的内容。 Sprout 按字节长度计量字符串，不提供按字符索引的操作。"Hello, ...

到第 14 篇为止，Sprout 程序中每个值都能装进一个寄存器：i64 是 64 位整数，bool 是 1 位逻辑值。函数参数和返回值通过寄存器传递，局部变量在 SSA 里就是虚拟寄存器。这套方案处理标量足够了，但程序需要处理一组数据时——排序、统计、批量输入——单个寄存器放不下。 本篇引入数组，它是 Sprout 的第一个堆分配类型。数组有可变长度，住在堆上，索引时必须检查边界。围绕它展开的问题不止语法：分配多大的内存、用什么布局存放长度和元素、怎样在运行时拦截越界、大小计算本身会不会溢出。 数组的内存布局 数组变量本身是一个指针，指向堆上分配的连续内存块。这块内存的头部存放元素个数，紧随其后是元素本身。Sprout 目前只有 i64 元素类型，每个元素 8 字节，长度字段也用 i64 存储。 1234567堆块起始地址 p┌──────────┬──────────┬──────────┬───┬──────────┐│ length │ elem[0] │ elem[1] │ … │ elem[n-1]││ (i64) │ (i64) │ (i64...

第 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 对应没有有意义返回值的表达式（赋值、打印调用等）。后续加入数组和结构体时，这个枚举会扩展，但三种基础值从本篇开始就固定下来。 环境：栈帧与变量绑定 解释器需要知道每个变量当前的值。环境用一组栈帧表示，每个...