本文作者：东灯

原标题：用 MoonBit 做静态分析：从分析简单语言到 MCIL

一、前言

你是否曾在编写代码时，对那些能未卜先知的工具感到好奇？当C/C++编译器警告你“变量可能未初始化”，或Type的IDE提示某个对象“可能为空”，它们并不是运行了你的程序，而仅仅是“扫描”了你的源代码，就精准地预见到了潜在的运行时风险。这背后隐藏的，正是编程世界中一项强大而优雅的技术——静态分析。

然而，对于大多数应用程序开发者而言，编译器和静态分析工具的运作原理仿佛一个神秘的黑匣子。我们受益于它们，却不一定理解其内在的设计逻辑与通用模式。

本文旨在为你揭开这层神秘面纱。无论你是会写普通应用程序的程序员，还是对程序底层原理感兴趣的探索者，我们都将一同踏上旅程，从零开始理解：为什么看似正确的代码会被分析工具“挑刺”？这些工具是如何从繁杂的语法结构中提取出可分析的逻辑的？更重要的是，它们为什么都采用了类似的设计哲学？

我们将以MCIL（MoonBit C Intermediate Language） 这一成熟的分析框架作为最终案例，展示MoonBit这一新兴的AI原生编程语言，如何优雅地用于C语言的静态分析工作，探究它在高性能、资源受限场景下的独特潜力。

跟随本文的指引，你不仅将掌握静态分析的核心思想，更能理解其设计与实现的普适性规律。让我们一同探索，如何让机器“看懂”代码的意图，并提前发现那些隐藏的缺陷。

二、我们要做什么

让我先展示最终的效果。假设有这样一段代码：

varx

vary=input

ify>0{

x=y+ 1

}

returnx

这是一门我们自己设计的简单语言。它支持变量声明、赋值、if条件语句、while循环和 return语句，而且所有块都在函数作用域中，没有块级作用域。

这段代码有一个 bug：变量 x只在 if的 then 分支里被赋值了，else 分支是空的。如果 y <= 0，程序会走 else 分支，这时候 x从来没有被赋值，但 return x却要使用它的值。这就是“使用未初始化变量”的错误，但是因为在编译器的层面，这段代码在逻辑上/类型上是正确的。

我们要写的静态分析器能够自动检测这种问题。更重要的是，我们会理解为什么静态分析器要这样设计，以及这种设计如何让分析变得既简单又强大。

三、从源码到 AST：词法分析与语法分析

在开始静态分析之前，我们需要先把源代码变成结构化的数据。这个过程分两步：词法分析和语法分析。

• 语法分析器（Parser）把 Token 流变成抽象语法树（AST）。AST 是程序的树形表示，体现了代码的层次结构。我们使用递归下降的方法：为每种语法成分写一个解析函数，函数之间相互调用。处理运算符优先级时，为每个优先级层写一个函数，低优先级的函数调用高优先级的函数。

我们的 AST 定义如下：

// 表达式

enumExpr{

Int(Int) // 整数: 0, 42

Var(String) // 变量: x, y

BinOp(BinOp, Expr, Expr) // 二元运算: x + 1

Call(String, Array[Expr]) // 函数调用: input

Not(Expr) // 逻辑非: !x

}

// 语句

enumStmt{

VarDecl(String, Expr?) // 变量声明: var x 或 var x = 0

Assign(String, Expr) // 赋值: x = 1

If(Expr, Array[Stmt], Array[Stmt]) // if-else

While(Expr, Array[Stmt]) // while 循环

Return(Expr) // 返回

}

我们之前的代码就会被这样解析为 AST：

完整的 Lexer/Parser 代码我们将会在文章结尾的仓库链接中提供，大约 400 行。这部分不是本文的重点——我们关心的是拿到 AST 之后怎么做分析。

四、编译器与静态分析器的关系

继续之前，让我们先看一下整体的图景。传统编译器和静态分析器走的是两条不同的路，但它们有共同的起点：

编译器和静态分析器共享从源代码到 IR 的前半段流程。区别在于 IR 之后：编译器继续往下走，最终生成可执行文件；静态分析器则“切断”了这条路，转而去分析 IR 本身，输出的是警告和错误报告，而不是机器码。

两者共享同一个洞察：直接在 AST上工作很困难，转换成 IR之后会容易很多。这就是为什么 CIL（C Intermediate Language）这类框架存在——它们提供一种“分析友好”的中间表示，保留了源语言的语义，但结构上更容易分析。

1、为什么不能直接在 AST 上做分析？

直接在 AST 上做静态分析在理论上是可行的，但在实践中会极其痛苦。原因并不在于分析目标本身复杂，而在于 AST 将控制流隐含在语法结构之中：if、while、break、continue、提前 return等都会迫使分析代码显式模拟控制流的所有可能执行路径，并引入不动点迭代、路径合并等逻辑。结果是，分析器的复杂度迅速被语法细节主导，而不是由分析问题本身决定。更糟的是，这种写法几乎无法复用：即使“未初始化变量分析”和“空指针分析”在抽象上都是同一类数据流分析，它们在 AST 上的实现却必须重复编写几乎相同的控制流处理代码。因此，直接在 AST 上递归分析往往导致代码臃肿、易错、不可扩展，也缺乏统一的抽象层次。

五、CIL的核心思想：把控制流“拍平”

CIL（C Intermediate Language）是加州大学伯克利分校开发的一个 C 程序分析框架。它的核心思想很简单但很强大：不要在 AST 上做分析，而是先把 AST 转换成一种更适合分析的中间表示（IR）。

这个 IR 有两个关键特征：

1、用“基本块”取代嵌套的控制结构

基本块是一段顺序执行的代码，中间没有分支，也没有跳转目标。换句话说，如果你开始执行一个基本块的第一条指令，你一定会顺序执行到最后一条指令，不会中途跳走，也不会有别的地方跳进来。

基本块之间用显式的跳转连接。比如：

ifcond{ ──▶ Block0: ifcondgotoBlock1elseBlock2

ABlock1: A; gotoBlock3

} else{ Block2: B; gotoBlock3

BBlock3: ...

}

whilecond{ ──▶ Block0: gotoBlock1

ABlock1: ifcondgotoBlock2elseBlock3

} Block2: A; gotoBlock1← 向后跳转

Block3: ...

if变成条件跳转，while变成一个循环——Block2 执行完后跳回 Block1 重新检查条件。

2、用“三地址码”取代复杂的表达式

三地址码是一种简化的指令格式，每条指令最多涉及三个“地址”（变量）。比如 x = y + z * w这样的复合表达式，会被拆成：

t1=z* w

t2=y+ t1

x=t2

其中 t1、t2是编译器生成的临时变量。

在代码中，我们这样定义 IR：

// 指令：三地址码格式

enumInstr{

BinOp(Operand, BinOp, Operand, Operand) // dest = left op right

Copy(Operand, Operand) // dest = src

Call(Operand, String, Array[Operand]) // dest = func(args...)

}

// 终结指令：基本块的出口

enumTerminator{

CondBr(Operand, Int, Int) // if cond goto block1 else block2

Goto(Int) // goto block

Return(Operand) // return value

}

// 基本块

structBlock{

id: Int

instrs: Array[Instr] // 块内的指令序列

term: Terminator// 终结指令

preds: Array[Int] // 前驱块

succs: Array[Int] // 后继块

}

让我们看看之前的例子转换成 IR 之后长什么样：

现在控制流的结构一目了然。Block 0 是入口，执行完之后根据条件跳到 Block 1 或 Block 2。Block 1 和 Block 2 最后都跳到 Block 3，Block 3 返回。

这种结构有一个专门的名字：控制流图（Control Flow Graph，CFG）。图的节点是基本块，边是跳转关系。我们可以画出来：

六、数据流分析：在 CFG 上“流动”信息

有了 CFG，我们就可以用一种非常优雅的方式来做分析：让信息在图上“流动”。

以“未初始化变量检测”为例。我们想知道：在程序的每个点，哪些变量已经被定义过了？

我们可以这样在 CFG 上进行思考：

• 在程序入口（Block 0 的开头），只有函数参数是“已定义”的，局部变量都是“未定义”的。

• 每条赋值语句会“产生”一个定义。比如 x = 0之后，x就变成“已定义”了。

• 每条赋值语句也会“杀死”之前的定义。比如 x = 1会让之前 x = 0的定义失效。

• 在控制流的汇合点（比如 Block 3 的开头），信息需要“合并”。Block 3 可能从 Block 1 到达，也可能从 Block 2 到达。如果一个变量在 Block 1 结尾是“已定义”的，但在 Block 2 结尾是“未定义”的，那么在 Block 3 开头它就是“可能未定义”的。

这就是数据流分析的基本思路。我们给每个基本块的入口和出口关联一个“状态”（在这个例子里，状态是“哪些变量已定义”的集合），然后定义：

1. 传递函数：给定一个块的入口状态，如何计算出口状态？就是模拟块内每条指令的效果。

2. 合并函数：当多条边汇合到一个点时，如何合并多个状态？比如取交集（“所有前驱都定义了才算定义”）或取并集（“任一前驱定义了就算定义”）。

接下来我们从入口开始，不断迭代，直到所有块的状态不再变化（达到“不动点”）。

这个过程可以用一个通用的算法框架来实现：

1. 把所有块加入工作表

2. 从工作表取出一个块

3. 根据前驱的状态和合并函数，计算这个块的入口状态

4. 根据传递函数，计算这个块的出口状态

5. 如果出口状态变了，把所有后继加入工作表

6. 重复 2-5，直到工作表为空

最后，我们可以把这个框架抽象成一个通用的函数，用户只需要提供传递函数和合并函数：

structForwardConfig[T] {

init: T// 入口的初始状态

transfer: (Block, T) ->T// 传递函数：入口状态 -> 出口状态

merge: (T, T) ->T// 合并函数：多个状态 -> 一个状态

equal: (T, T) ->Bool// 判断状态是否相等（用于检测不动点）

copy: (T) ->T// 复制状态（避免共享引用）

}

fnforward_dataflow[T](fun_ir: FunIR, config: ForwardConfig[T]) ->Result[T] {

// 初始化每个块的状态

// 迭代直到不动点

// ...

}

这个框架的美妙之处在于：不管你分析的是什么问题（未初始化变量、空指针、整数溢出……），只要能定义传递函数和合并函数，就能套用同一个框架，而不是手写多遍复杂的逻辑去适配很小的思维改动。

七、前向分析 vs 后向分析

刚才说的是“前向分析”（Forward Analysis）：信息从程序入口向出口流动。但有些分析天然是“后向”的（Backward Analysis）。

比如“活跃变量分析”（Liveness Analysis）：我们想知道在程序的每个点，哪些变量的值在之后还会被用到。这个问题要从程序出口往回看。如果一个变量在某点之后不再被使用，那它就是“死”的，之前对它的赋值就是无用的（死代码）。

后向分析和前向分析是对称的：信息从出口向入口流动，传递函数从“入口状态→出口状态”变成“出口状态→入口状态”，合并函数作用于后继而不是前驱。

structBackwardConfig[T] {

init: T// 出口的初始状态

transfer: (Block, T) ->T// 传递函数：出口状态 -> 入口状态

merge: (T, T) ->T// 合并后继的状态

equal: (T, T) ->Bool

copy: (T) ->T

}

活跃变量分析的传递函数这样写：

fnliveness_transfer(block: Block, out_state: LiveSet) ->LiveSet{

letlive=out_state.copy

// 从后向前处理指令（因为是后向分析）

fori=block.instrs.length- 1; i>=0; i=i- 1{

letinstr=block.instrs[i]

// 先移除这条指令定义的变量

matchget_def(instr) { Some(v) =>live.remove(v), None=>}

// 再加入这条指令使用的变量

forvinget_uses(instr) { live.add(v) }

}

live

}

为什么要“先移除定义，再加入使用”？我们不妨考虑 x = x + 1这条指令。在这条指令之前，x必须是活跃的（因为我们要读取它）。但在这条指令之后，x的旧值就不需要了（因为我们写入了新值）。所以在后向分析中，我们要先处理定义（消除活跃性），再处理使用（产生活跃性）。

对于合并函数，活跃变量分析使用并集：如果一个变量在任意一条出边上是活跃的，它在当前点就是活跃的。这是因为程序可能走任意一条分支，只要有可能被用到，变量就必须保持活跃。

八、检测未初始化变量

现在让我们来实现一个实用的分析：检测可能未初始化的变量。

思路是这样的：我们用“定值可达性分析”来跟踪每个程序点可能到达的变量定义。如果在某个点使用了一个变量，但没有任何定义能到达这个点，那就是未初始化使用。

定值可达性分析是前向的。每条赋值语句产生一个新定义，同时杀死同一变量的旧定义。在汇合点，多个分支的定义集合取并集（因为任意一条路径的定义都可能到达）。

有了定值可达性的信息，检测就很直接了：

forblockinfun_ir.blocks { letmutdefs=reaching.defs_in[block.id] forinstrinblock.instrs { // 检查使用的变量 for var in get_uses(instr) { if not(defs.has_def(var)) && not(is_param(var)) { warn("Variable may be uninitialized: " + var) } } // 更新定义 match get_def(instr) {Some(var) => defs = defs.update(var, current_def)None=> } }}

让我们在之前的例子上测试一下：

Warning: Variablemaybeuninitialized: x(atBlock3, Return)

太棒了！这就是我们想要的结果！

九、MCIL：真实的 C 语言分析

我们刚才教学使用的项目叫做 MiniCIL，是一个参考 CIL 项目编写的简易教学项目，它的 DSL 只有几种简单的语句。真正的 C 语言要复杂得多。而我们编写了一个CIL 的完整 MoonBit 实现：MCIL，它有能力处理完整的 C 语言，做非常复杂的静态分析工作。

MCIL 和 MiniCIL 的架构是一样的：

C源代码 → Lexer/Parser→ AST→ cabs2cil→ CILIR→ 分析

MCIL 的 Lexer 要处理 C 语言的所有 Token：sizeof、typedef、struct、->等等。Parser 要处理 C 语言的完整语法：函数指针、复合字面量、designated initializer、GCC 扩展等等。cabs2cil 转换要处理类型推导、隐式转换、常量折叠、作用域解析等等。

但是它们核心的分析框架和思想是相通的，理解了 MiniCIL，读 MCIL 的代码就会容易很多。

下面是一个 MCIL 做 C 语言的一些简单静态分析的实例：

1、C 语言分析会遇到的困难

如果有对 MCIL 感兴趣的读者，下面这几条 C 语言静态分析会遇到的主要困难对你非常重要：

1. 指针和别名：我们刚才的 DSL 只有简单变量，但 C 语言有指针。当你写 *p = 1的时候，你修改的是哪个变量？如果 p可能指向 x或 y，这条语句就可能修改两者中的任何一个。更糟糕的是，p和 q可能指向同一块内存（别名），修改 *p会影响 *q的值。跟踪指针的指向关系叫做别名分析，是静态分析中最困难的问题之一。

2. 过程间分析：我们教学中的分析只看单个函数。但当你调用 foo(x)的时候，foo会修改 x指向的内存吗？会释放它吗？如果只分析单个函数，这些信息都丢失了。过程间分析要构建调用图，跟踪函数之间的数据流。MCIL 实现了简单的过程间分析，可以检测 free(p)后对 p的使用。

3. 复杂的类型系统：C 语言的类型系统充满陷阱：数组退化成指针、函数指针的复杂语法、struct 的内存布局、union 的类型双关等等。MCIL 的 cabs2cil转换会处理这些，把它们规范化成统一的形式。比如，所有隐式类型转换都变成显式的 CastE，数组到指针的转换通过 StartOf表达。

4. C 语言的未定义行为：有符号整数溢出、空指针解引用、越界访问、use-after-free……C 标准把这些都定义为“未定义行为”（UB），编译器可以假设它们不会发生。静态分析工具要检测这些问题，但又不能太保守导致误报（因为有些逻辑可能偏偏就是用这种 UB 实现得快）。