导读：本篇为Moonbit团队向21CTO的投稿文章。Moonbit为国产编程语言，在性能上优于Rust和Go。以下是用它来做静态分析的内容，希望对大家有帮助。

一、前言

当你写 C/C++ 的时候，编译器会警告你“变量在使用前可能未初始化”。当你用 TypeScript 的时候，IDE 会告诉你“这个对象可能是 null”。你有没有想过，编译器/IDE 是怎么从一段编译正确的代码中发现 bug 的？它们并没有运行你的代码，只是“看”了一眼源码，就能发现潜在的问题。这就是静态分析的魔力。

如果你是一个会写普通应用程序的程序员，想要理解编译器和静态分析工具背后的原理，这篇文章就是为你准备的。读完之后，你不仅会理解这些工具是怎么工作的，还会明白为什么它们都采用类似的设计。同时在文章最后，我们也会看到一个成熟的静态分析框架——MCIL(MoonBit C Intermediate Language)，了解如何使用 MoonBit 做 C 语言的静态分析工作。

二、我们要做什么

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

var xvar y = input()if y > 0 {	x = y + 1}return x

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

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

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

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

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

• 词法分析器（Lexer）把字符流变成 Token 流。比如 var x = 0 会被识别成四个 Token：关键字 Var、标识符 Ident("x")、赋值符号 Eq、整数 IntLit(0)。词法分析器从头到尾扫描字符，跳过空白和注释，根据当前字符决定生成什么类型的 Token。

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

我们的 AST 定义如下：

// 表达式enum Expr{ 	Int(Int)           // 整数: 0, 42	Var(String)        // 变量: x, y	BinOp(		BinOp,		Expr,		Expr	) 	// 二元运算: x + 1	Call(String,Array[Expr])   // 函数调用: input()	Not(Expr)           // 逻辑非: !x}// 语句enum Stmt{	Var Decl(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、用“基本块”取代嵌套的控制结构

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

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

if cond {       ──▶    Block0: if cond goto Block1 else Block2
  A                    Block1: A; goto Block3
} else {               Block2: B; goto Block3
  B                    Block3: ...
}

while cond {    ──▶    Block0: goto Block1
  A                    Block1: if cond goto Block2 else Block3
}                      Block2: A; goto Block1    ← 向后跳转
                       Block3: ...

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

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

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

t1 = z * w
t2 = y + t1
x = t2

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

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

// 指令：三地址码格式
enum Instr {
BinOp(Operand, BinOp, Operand, Operand)  // dest = left op right
Copy(Operand, Operand)                    // dest = src
Call(Operand, String, Array[Operand])     // dest = func(args...)
}

// 终结指令：基本块的出口
enum Terminator {
CondBr(Operand, Int, Int)  // if cond goto block1 else block2
Goto(Int)                   // goto block
Return(Operand)             // return value
}

// 基本块
struct Block {
  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，直到工作表为空

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

struct ForwardConfig[T] {
  init : T                    // 入口的初始状态
  transfer : (Block, T) ->T  // 传递函数：入口状态 -> 出口状态
  merge : (T, T) ->T         // 合并函数：多个状态 -> 一个状态
  equal : (T, T) ->Bool      // 判断状态是否相等（用于检测不动点）
  copy : (T) ->T             // 复制状态（避免共享引用）
}

fn forward_dataflow[T](fun_ir : FunIR, config : ForwardConfig[T]) ->Result[T] {
  // 初始化每个块的状态
  // 迭代直到不动点
  // ...
}

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

七、前向分析 vs 后向分析

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

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

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

struct BackwardConfig[T] {
  init : T                    // 出口的初始状态
  transfer : (Block, T) ->T  // 传递函数：出口状态 -> 入口状态
  merge : (T, T) ->T         // 合并后继的状态
  equal : (T, T) ->Bool
  copy : (T) ->T
}

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

fn liveness_transfer(block : Block, out_state : LiveSet) ->LiveSet {
  let live = out_state.copy()
  // 从后向前处理指令（因为是后向分析）
  for i = block.instrs.length() - 1; i >= 0; i = i - 1 {
    let instr = block.instrs[i]
    // 先移除这条指令定义的变量
    match get_def(instr) { Some(v) => live.remove(v), None=> () }
    // 再加入这条指令使用的变量
    for v in get_uses(instr) { live.add(v) }
  }
  live
}

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

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

八、检测未初始化变量

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

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

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

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

for block in fun_ir.blocks {
  let mut defs = reaching.defs_in[block.id]
  for instr in block.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: Variable may be uninitialized: x (at Block 3, Return)

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

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

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

MCIL 和 MiniCIL 的架构是一样的：

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

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

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

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

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 实现得快）。

十、总结

在这篇文章中，我们学习了静态分析的基本流程：从源代码经过词法分析、语法分析得到 AST，再转换成基本块和显式跳转构成的 CFG，最后用数据流分析框架在 CFG 上迭代直到不动点。我们实现了活跃变量分析和未初始化变量检测作为例子，展示了该静态分析思想的通用性。

另外 CIL 其实已经是 200x 年代的产物了，在 2002 年《CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs》中第一次发表后，工具逐步成熟并公开发布，并开始被逐渐被应用于各种工业项目中，它相对精简，到现在仍然是学习静态分析的优秀例子。不过，随着编译器技术的发展，以 SSA（Static Single Assignment） 形式为核心的 LLVM/Clang 编译基础设施逐渐成熟，并在工业界成为事实标准，这类框架在统一中间表示、跨阶段优化以及代码生成方面展现出更强的通用性与扩展性，因而在实际工程中逐步取代了以 CIL 为代表的、主要面向单语言静态分析的中间表示工具。感兴趣的读者也可以自行拓展这方面内容，学习更加现代，更加强大的静态分析技术。

作者：宗恩

参考文献：

CIL 原论文：

《CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs》

Mini MoonBit C Intermediate Language(教学使用的代码)：

 https://github.com/Lampese/MiniCIL

MoonBit C Intermediate Language(MCIL)： 

https://github.com/Lampese/MCIL