AI原生語言MoonBit遇上靜態分析，迸發高性能、資源受限場景下的獨特潛力

本文作者：東燈

原標題：用 MoonBit 做靜態分析：從分析簡單語言到 MCIL

一、前言

你是否曾在編寫代碼時，對那些能未卜先知的工具感到好奇？當C/C++編譯器警告你“變量可能未初始化”，或TypeScript的IDE提示某個對象“可能為空”，它們并不是運行了你的程序，而僅僅是“掃描”了你的源代碼，就精準地預見到了潛在的運行時風險。這背后隱藏的，正是編程世界中一項強大而優雅的技術——靜態分析。

然而，對于大多數應用程序開發者而言，編譯器和靜態分析工具的運作原理仿佛一個神秘的黑匣子。我們受益于它們，卻不一定理解其內在的設計邏輯與通用模式。

本文旨在為你揭開這層神秘面紗。無論你是會寫普通應用程序的程序員，還是對程序底層原理感興趣的探索者，我們都將一同踏上旅程，從零開始理解：為什么看似正確的代碼會被分析工具“挑刺”？這些工具是如何從繁雜的語法結構中提取出可分析的邏輯的？更重要的是，它們為什么都采用了類似的設計哲學？

我們將以MCIL（MoonBit C Intermediate Language） 這一成熟的分析框架作為最終案例，展示MoonBit這一新興的AI原生編程語言，如何優雅地用于C語言的靜態分析工作，探究它在高性能、資源受限場景下的獨特潛力。

跟隨本文的指引，你不僅將掌握靜態分析的核心思想，更能理解其設計與實現的普適性規律。讓我們一同探索，如何讓機器“看懂”代碼的意圖，并提前發現那些隱藏的缺陷。

二、我們要做什么

讓我先展示最終的效果。假設有這樣一段代碼：

    
      
      
      var x
var 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 {
  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、用“ 基本塊 ”取代嵌套的控制結構

基本塊是一段順序執行的代碼，中間沒有分支，也沒有跳轉目標。換句話說，如果你開始執行一個基本塊的第一條指令，你一定會順序執行到最后一條指令，不會中途跳走，也不會有別的地方跳進來。

基本塊之間用顯式的跳轉連接。比如：

    
      
      
      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 語言的一些簡單靜態分析的實例：

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 實現得快）。

在這篇文章中，我們學習了靜態分析的基本流程：從源代碼經過詞法分析、語法分析得到 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